blob: 8c9f2049bc7be00b86e7237a7c91206c9dfabd02 [file] [log] [blame]
William Kurkianea869482019-04-09 15:16:11 -04001// 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}