1// Copyright 2016 The Snappy-Go Authors. All rights reserved. 2// Copyright (c) 2019 Klaus Post. All rights reserved. 3// Use of this source code is governed by a BSD-style 4// license that can be found in the LICENSE file. 5 6//go:build (!amd64 && !arm64) || appengine || !gc || noasm 7// +build !amd64,!arm64 appengine !gc noasm 8 9package s2 10 11import ( 12 "fmt" 13 "strconv" 14) 15 16// decode writes the decoding of src to dst. It assumes that the varint-encoded 17// length of the decompressed bytes has already been read, and that len(dst) 18// equals that length. 19// 20// It returns 0 on success or a decodeErrCodeXxx error code on failure. 21func s2Decode(dst, src []byte) int { 22 const debug = false 23 if debug { 24 fmt.Println("Starting decode, dst len:", len(dst)) 25 } 26 var d, s, length int 27 offset := 0 28 29 // As long as we can read at least 5 bytes... 30 for s < len(src)-5 { 31 switch src[s] & 0x03 { 32 case tagLiteral: 33 x := uint32(src[s] >> 2) 34 switch { 35 case x < 60: 36 s++ 37 case x == 60: 38 s += 2 39 x = uint32(src[s-1]) 40 case x == 61: 41 s += 3 42 x = uint32(src[s-2]) | uint32(src[s-1])<<8 43 case x == 62: 44 s += 4 45 x = uint32(src[s-3]) | uint32(src[s-2])<<8 | uint32(src[s-1])<<16 46 case x == 63: 47 s += 5 48 x = uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24 49 } 50 length = int(x) + 1 51 if length > len(dst)-d || length > len(src)-s || (strconv.IntSize == 32 && length <= 0) { 52 return decodeErrCodeCorrupt 53 } 54 if debug { 55 fmt.Println("literals, length:", length, "d-after:", d+length) 56 } 57 58 copy(dst[d:], src[s:s+length]) 59 d += length 60 s += length 61 continue 62 63 case tagCopy1: 64 s += 2 65 length = int(src[s-2]) >> 2 & 0x7 66 toffset := int(uint32(src[s-2])&0xe0<<3 | uint32(src[s-1])) 67 if toffset == 0 { 68 if debug { 69 fmt.Print("(repeat) ") 70 } 71 // keep last offset 72 switch length { 73 case 5: 74 s += 1 75 length = int(uint32(src[s-1])) + 4 76 case 6: 77 s += 2 78 length = int(uint32(src[s-2])|(uint32(src[s-1])<<8)) + (1 << 8) 79 case 7: 80 s += 3 81 length = int(uint32(src[s-3])|(uint32(src[s-2])<<8)|(uint32(src[s-1])<<16)) + (1 << 16) 82 default: // 0-> 4 83 } 84 } else { 85 offset = toffset 86 } 87 length += 4 88 case tagCopy2: 89 s += 3 90 length = 1 + int(src[s-3])>>2 91 offset = int(uint32(src[s-2]) | uint32(src[s-1])<<8) 92 93 case tagCopy4: 94 s += 5 95 length = 1 + int(src[s-5])>>2 96 offset = int(uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24) 97 } 98 99 if offset <= 0 || d < offset || length > len(dst)-d { 100 return decodeErrCodeCorrupt 101 } 102 103 if debug { 104 fmt.Println("copy, length:", length, "offset:", offset, "d-after:", d+length) 105 } 106 107 // Copy from an earlier sub-slice of dst to a later sub-slice. 108 // If no overlap, use the built-in copy: 109 if offset > length { 110 copy(dst[d:d+length], dst[d-offset:]) 111 d += length 112 continue 113 } 114 115 // Unlike the built-in copy function, this byte-by-byte copy always runs 116 // forwards, even if the slices overlap. Conceptually, this is: 117 // 118 // d += forwardCopy(dst[d:d+length], dst[d-offset:]) 119 // 120 // We align the slices into a and b and show the compiler they are the same size. 121 // This allows the loop to run without bounds checks. 122 a := dst[d : d+length] 123 b := dst[d-offset:] 124 b = b[:len(a)] 125 for i := range a { 126 a[i] = b[i] 127 } 128 d += length 129 } 130 131 // Remaining with extra checks... 132 for s < len(src) { 133 switch src[s] & 0x03 { 134 case tagLiteral: 135 x := uint32(src[s] >> 2) 136 switch { 137 case x < 60: 138 s++ 139 case x == 60: 140 s += 2 141 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 142 return decodeErrCodeCorrupt 143 } 144 x = uint32(src[s-1]) 145 case x == 61: 146 s += 3 147 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 148 return decodeErrCodeCorrupt 149 } 150 x = uint32(src[s-2]) | uint32(src[s-1])<<8 151 case x == 62: 152 s += 4 153 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 154 return decodeErrCodeCorrupt 155 } 156 x = uint32(src[s-3]) | uint32(src[s-2])<<8 | uint32(src[s-1])<<16 157 case x == 63: 158 s += 5 159 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 160 return decodeErrCodeCorrupt 161 } 162 x = uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24 163 } 164 length = int(x) + 1 165 if length > len(dst)-d || length > len(src)-s || (strconv.IntSize == 32 && length <= 0) { 166 return decodeErrCodeCorrupt 167 } 168 if debug { 169 fmt.Println("literals, length:", length, "d-after:", d+length) 170 } 171 172 copy(dst[d:], src[s:s+length]) 173 d += length 174 s += length 175 continue 176 177 case tagCopy1: 178 s += 2 179 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 180 return decodeErrCodeCorrupt 181 } 182 length = int(src[s-2]) >> 2 & 0x7 183 toffset := int(uint32(src[s-2])&0xe0<<3 | uint32(src[s-1])) 184 if toffset == 0 { 185 if debug { 186 fmt.Print("(repeat) ") 187 } 188 // keep last offset 189 switch length { 190 case 5: 191 s += 1 192 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 193 return decodeErrCodeCorrupt 194 } 195 length = int(uint32(src[s-1])) + 4 196 case 6: 197 s += 2 198 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 199 return decodeErrCodeCorrupt 200 } 201 length = int(uint32(src[s-2])|(uint32(src[s-1])<<8)) + (1 << 8) 202 case 7: 203 s += 3 204 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 205 return decodeErrCodeCorrupt 206 } 207 length = int(uint32(src[s-3])|(uint32(src[s-2])<<8)|(uint32(src[s-1])<<16)) + (1 << 16) 208 default: // 0-> 4 209 } 210 } else { 211 offset = toffset 212 } 213 length += 4 214 case tagCopy2: 215 s += 3 216 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 217 return decodeErrCodeCorrupt 218 } 219 length = 1 + int(src[s-3])>>2 220 offset = int(uint32(src[s-2]) | uint32(src[s-1])<<8) 221 222 case tagCopy4: 223 s += 5 224 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 225 return decodeErrCodeCorrupt 226 } 227 length = 1 + int(src[s-5])>>2 228 offset = int(uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24) 229 } 230 231 if offset <= 0 || d < offset || length > len(dst)-d { 232 return decodeErrCodeCorrupt 233 } 234 235 if debug { 236 fmt.Println("copy, length:", length, "offset:", offset, "d-after:", d+length) 237 } 238 239 // Copy from an earlier sub-slice of dst to a later sub-slice. 240 // If no overlap, use the built-in copy: 241 if offset > length { 242 copy(dst[d:d+length], dst[d-offset:]) 243 d += length 244 continue 245 } 246 247 // Unlike the built-in copy function, this byte-by-byte copy always runs 248 // forwards, even if the slices overlap. Conceptually, this is: 249 // 250 // d += forwardCopy(dst[d:d+length], dst[d-offset:]) 251 // 252 // We align the slices into a and b and show the compiler they are the same size. 253 // This allows the loop to run without bounds checks. 254 a := dst[d : d+length] 255 b := dst[d-offset:] 256 b = b[:len(a)] 257 for i := range a { 258 a[i] = b[i] 259 } 260 d += length 261 } 262 263 if d != len(dst) { 264 return decodeErrCodeCorrupt 265 } 266 return 0 267} 268