1//go:build !amd64 || appengine || !gc || noasm 2// +build !amd64 appengine !gc noasm 3 4package s2 5 6import ( 7 "math/bits" 8) 9 10// encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It 11// assumes that the varint-encoded length of the decompressed bytes has already 12// been written. 13// 14// It also assumes that: 15// len(dst) >= MaxEncodedLen(len(src)) 16func encodeBlock(dst, src []byte) (d int) { 17 if len(src) < minNonLiteralBlockSize { 18 return 0 19 } 20 return encodeBlockGo(dst, src) 21} 22 23// encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It 24// assumes that the varint-encoded length of the decompressed bytes has already 25// been written. 26// 27// It also assumes that: 28// len(dst) >= MaxEncodedLen(len(src)) 29func encodeBlockBetter(dst, src []byte) (d int) { 30 return encodeBlockBetterGo(dst, src) 31} 32 33// encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It 34// assumes that the varint-encoded length of the decompressed bytes has already 35// been written. 36// 37// It also assumes that: 38// len(dst) >= MaxEncodedLen(len(src)) 39func encodeBlockBetterSnappy(dst, src []byte) (d int) { 40 return encodeBlockBetterSnappyGo(dst, src) 41} 42 43// encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It 44// assumes that the varint-encoded length of the decompressed bytes has already 45// been written. 46// 47// It also assumes that: 48// len(dst) >= MaxEncodedLen(len(src)) 49func encodeBlockSnappy(dst, src []byte) (d int) { 50 if len(src) < minNonLiteralBlockSize { 51 return 0 52 } 53 return encodeBlockSnappyGo(dst, src) 54} 55 56// emitLiteral writes a literal chunk and returns the number of bytes written. 57// 58// It assumes that: 59// dst is long enough to hold the encoded bytes 60// 0 <= len(lit) && len(lit) <= math.MaxUint32 61func emitLiteral(dst, lit []byte) int { 62 if len(lit) == 0 { 63 return 0 64 } 65 const num = 63<<2 | tagLiteral 66 i, n := 0, uint(len(lit)-1) 67 switch { 68 case n < 60: 69 dst[0] = uint8(n)<<2 | tagLiteral 70 i = 1 71 case n < 1<<8: 72 dst[1] = uint8(n) 73 dst[0] = 60<<2 | tagLiteral 74 i = 2 75 case n < 1<<16: 76 dst[2] = uint8(n >> 8) 77 dst[1] = uint8(n) 78 dst[0] = 61<<2 | tagLiteral 79 i = 3 80 case n < 1<<24: 81 dst[3] = uint8(n >> 16) 82 dst[2] = uint8(n >> 8) 83 dst[1] = uint8(n) 84 dst[0] = 62<<2 | tagLiteral 85 i = 4 86 default: 87 dst[4] = uint8(n >> 24) 88 dst[3] = uint8(n >> 16) 89 dst[2] = uint8(n >> 8) 90 dst[1] = uint8(n) 91 dst[0] = 63<<2 | tagLiteral 92 i = 5 93 } 94 return i + copy(dst[i:], lit) 95} 96 97// emitRepeat writes a repeat chunk and returns the number of bytes written. 98// Length must be at least 4 and < 1<<24 99func emitRepeat(dst []byte, offset, length int) int { 100 // Repeat offset, make length cheaper 101 length -= 4 102 if length <= 4 { 103 dst[0] = uint8(length)<<2 | tagCopy1 104 dst[1] = 0 105 return 2 106 } 107 if length < 8 && offset < 2048 { 108 // Encode WITH offset 109 dst[1] = uint8(offset) 110 dst[0] = uint8(offset>>8)<<5 | uint8(length)<<2 | tagCopy1 111 return 2 112 } 113 if length < (1<<8)+4 { 114 length -= 4 115 dst[2] = uint8(length) 116 dst[1] = 0 117 dst[0] = 5<<2 | tagCopy1 118 return 3 119 } 120 if length < (1<<16)+(1<<8) { 121 length -= 1 << 8 122 dst[3] = uint8(length >> 8) 123 dst[2] = uint8(length >> 0) 124 dst[1] = 0 125 dst[0] = 6<<2 | tagCopy1 126 return 4 127 } 128 const maxRepeat = (1 << 24) - 1 129 length -= 1 << 16 130 left := 0 131 if length > maxRepeat { 132 left = length - maxRepeat + 4 133 length = maxRepeat - 4 134 } 135 dst[4] = uint8(length >> 16) 136 dst[3] = uint8(length >> 8) 137 dst[2] = uint8(length >> 0) 138 dst[1] = 0 139 dst[0] = 7<<2 | tagCopy1 140 if left > 0 { 141 return 5 + emitRepeat(dst[5:], offset, left) 142 } 143 return 5 144} 145 146// emitCopy writes a copy chunk and returns the number of bytes written. 147// 148// It assumes that: 149// dst is long enough to hold the encoded bytes 150// 1 <= offset && offset <= math.MaxUint32 151// 4 <= length && length <= 1 << 24 152func emitCopy(dst []byte, offset, length int) int { 153 if offset >= 65536 { 154 i := 0 155 if length > 64 { 156 // Emit a length 64 copy, encoded as 5 bytes. 157 dst[4] = uint8(offset >> 24) 158 dst[3] = uint8(offset >> 16) 159 dst[2] = uint8(offset >> 8) 160 dst[1] = uint8(offset) 161 dst[0] = 63<<2 | tagCopy4 162 length -= 64 163 if length >= 4 { 164 // Emit remaining as repeats 165 return 5 + emitRepeat(dst[5:], offset, length) 166 } 167 i = 5 168 } 169 if length == 0 { 170 return i 171 } 172 // Emit a copy, offset encoded as 4 bytes. 173 dst[i+0] = uint8(length-1)<<2 | tagCopy4 174 dst[i+1] = uint8(offset) 175 dst[i+2] = uint8(offset >> 8) 176 dst[i+3] = uint8(offset >> 16) 177 dst[i+4] = uint8(offset >> 24) 178 return i + 5 179 } 180 181 // Offset no more than 2 bytes. 182 if length > 64 { 183 // Emit a length 60 copy, encoded as 3 bytes. 184 // Emit remaining as repeat value (minimum 4 bytes). 185 dst[2] = uint8(offset >> 8) 186 dst[1] = uint8(offset) 187 dst[0] = 59<<2 | tagCopy2 188 length -= 60 189 // Emit remaining as repeats, at least 4 bytes remain. 190 return 3 + emitRepeat(dst[3:], offset, length) 191 } 192 if length >= 12 || offset >= 2048 { 193 // Emit the remaining copy, encoded as 3 bytes. 194 dst[2] = uint8(offset >> 8) 195 dst[1] = uint8(offset) 196 dst[0] = uint8(length-1)<<2 | tagCopy2 197 return 3 198 } 199 // Emit the remaining copy, encoded as 2 bytes. 200 dst[1] = uint8(offset) 201 dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1 202 return 2 203} 204 205// emitCopyNoRepeat writes a copy chunk and returns the number of bytes written. 206// 207// It assumes that: 208// dst is long enough to hold the encoded bytes 209// 1 <= offset && offset <= math.MaxUint32 210// 4 <= length && length <= 1 << 24 211func emitCopyNoRepeat(dst []byte, offset, length int) int { 212 if offset >= 65536 { 213 i := 0 214 if length > 64 { 215 // Emit a length 64 copy, encoded as 5 bytes. 216 dst[4] = uint8(offset >> 24) 217 dst[3] = uint8(offset >> 16) 218 dst[2] = uint8(offset >> 8) 219 dst[1] = uint8(offset) 220 dst[0] = 63<<2 | tagCopy4 221 length -= 64 222 if length >= 4 { 223 // Emit remaining as repeats 224 return 5 + emitCopyNoRepeat(dst[5:], offset, length) 225 } 226 i = 5 227 } 228 if length == 0 { 229 return i 230 } 231 // Emit a copy, offset encoded as 4 bytes. 232 dst[i+0] = uint8(length-1)<<2 | tagCopy4 233 dst[i+1] = uint8(offset) 234 dst[i+2] = uint8(offset >> 8) 235 dst[i+3] = uint8(offset >> 16) 236 dst[i+4] = uint8(offset >> 24) 237 return i + 5 238 } 239 240 // Offset no more than 2 bytes. 241 if length > 64 { 242 // Emit a length 60 copy, encoded as 3 bytes. 243 // Emit remaining as repeat value (minimum 4 bytes). 244 dst[2] = uint8(offset >> 8) 245 dst[1] = uint8(offset) 246 dst[0] = 59<<2 | tagCopy2 247 length -= 60 248 // Emit remaining as repeats, at least 4 bytes remain. 249 return 3 + emitCopyNoRepeat(dst[3:], offset, length) 250 } 251 if length >= 12 || offset >= 2048 { 252 // Emit the remaining copy, encoded as 3 bytes. 253 dst[2] = uint8(offset >> 8) 254 dst[1] = uint8(offset) 255 dst[0] = uint8(length-1)<<2 | tagCopy2 256 return 3 257 } 258 // Emit the remaining copy, encoded as 2 bytes. 259 dst[1] = uint8(offset) 260 dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1 261 return 2 262} 263 264// matchLen returns how many bytes match in a and b 265// 266// It assumes that: 267// len(a) <= len(b) 268// 269func matchLen(a []byte, b []byte) int { 270 b = b[:len(a)] 271 var checked int 272 if len(a) > 4 { 273 // Try 4 bytes first 274 if diff := load32(a, 0) ^ load32(b, 0); diff != 0 { 275 return bits.TrailingZeros32(diff) >> 3 276 } 277 // Switch to 8 byte matching. 278 checked = 4 279 a = a[4:] 280 b = b[4:] 281 for len(a) >= 8 { 282 b = b[:len(a)] 283 if diff := load64(a, 0) ^ load64(b, 0); diff != 0 { 284 return checked + (bits.TrailingZeros64(diff) >> 3) 285 } 286 checked += 8 287 a = a[8:] 288 b = b[8:] 289 } 290 } 291 b = b[:len(a)] 292 for i := range a { 293 if a[i] != b[i] { 294 return int(i) + checked 295 } 296 } 297 return len(a) + checked 298} 299