1// Copyright 2016 The Snappy-Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// +build !amd64 appengine !gc noasm 6 7package snappy 8 9// decode writes the decoding of src to dst. It assumes that the varint-encoded 10// length of the decompressed bytes has already been read, and that len(dst) 11// equals that length. 12// 13// It returns 0 on success or a decodeErrCodeXxx error code on failure. 14func decode(dst, src []byte) int { 15 var d, s, offset, length int 16 for s < len(src) { 17 switch src[s] & 0x03 { 18 case tagLiteral: 19 x := uint32(src[s] >> 2) 20 switch { 21 case x < 60: 22 s++ 23 case x == 60: 24 s += 2 25 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 26 return decodeErrCodeCorrupt 27 } 28 x = uint32(src[s-1]) 29 case x == 61: 30 s += 3 31 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 32 return decodeErrCodeCorrupt 33 } 34 x = uint32(src[s-2]) | uint32(src[s-1])<<8 35 case x == 62: 36 s += 4 37 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 38 return decodeErrCodeCorrupt 39 } 40 x = uint32(src[s-3]) | uint32(src[s-2])<<8 | uint32(src[s-1])<<16 41 case x == 63: 42 s += 5 43 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 44 return decodeErrCodeCorrupt 45 } 46 x = uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24 47 } 48 length = int(x) + 1 49 if length <= 0 { 50 return decodeErrCodeUnsupportedLiteralLength 51 } 52 if length > len(dst)-d || length > len(src)-s { 53 return decodeErrCodeCorrupt 54 } 55 copy(dst[d:], src[s:s+length]) 56 d += length 57 s += length 58 continue 59 60 case tagCopy1: 61 s += 2 62 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 63 return decodeErrCodeCorrupt 64 } 65 length = 4 + int(src[s-2])>>2&0x7 66 offset = int(uint32(src[s-2])&0xe0<<3 | uint32(src[s-1])) 67 68 case tagCopy2: 69 s += 3 70 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 71 return decodeErrCodeCorrupt 72 } 73 length = 1 + int(src[s-3])>>2 74 offset = int(uint32(src[s-2]) | uint32(src[s-1])<<8) 75 76 case tagCopy4: 77 s += 5 78 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line. 79 return decodeErrCodeCorrupt 80 } 81 length = 1 + int(src[s-5])>>2 82 offset = int(uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24) 83 } 84 85 if offset <= 0 || d < offset || length > len(dst)-d { 86 return decodeErrCodeCorrupt 87 } 88 // Copy from an earlier sub-slice of dst to a later sub-slice. Unlike 89 // the built-in copy function, this byte-by-byte copy always runs 90 // forwards, even if the slices overlap. Conceptually, this is: 91 // 92 // d += forwardCopy(dst[d:d+length], dst[d-offset:]) 93 for end := d + length; d != end; d++ { 94 dst[d] = dst[d-offset] 95 } 96 } 97 if d != len(dst) { 98 return decodeErrCodeCorrupt 99 } 100 return 0 101} 102