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 package snapref
6 7 // decode writes the decoding of src to dst. It assumes that the varint-encoded
8 // length of the decompressed bytes has already been read, and that len(dst)
9 // equals that length.
10 //
11 // It returns 0 on success or a decodeErrCodeXxx error code on failure.
12 func decode(dst, src []byte) int {
13 var d, s, offset, length int
14 for s < len(src) {
15 switch src[s] & 0x03 {
16 case tagLiteral:
17 x := uint32(src[s] >> 2)
18 switch {
19 case x < 60:
20 s++
21 case x == 60:
22 s += 2
23 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
24 return decodeErrCodeCorrupt
25 }
26 x = uint32(src[s-1])
27 case x == 61:
28 s += 3
29 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
30 return decodeErrCodeCorrupt
31 }
32 x = uint32(src[s-2]) | uint32(src[s-1])<<8
33 case x == 62:
34 s += 4
35 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
36 return decodeErrCodeCorrupt
37 }
38 x = uint32(src[s-3]) | uint32(src[s-2])<<8 | uint32(src[s-1])<<16
39 case x == 63:
40 s += 5
41 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
42 return decodeErrCodeCorrupt
43 }
44 x = uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24
45 }
46 length = int(x) + 1
47 if length <= 0 {
48 return decodeErrCodeUnsupportedLiteralLength
49 }
50 if length > len(dst)-d || length > len(src)-s {
51 return decodeErrCodeCorrupt
52 }
53 copy(dst[d:], src[s:s+length])
54 d += length
55 s += length
56 continue
57 58 case tagCopy1:
59 s += 2
60 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
61 return decodeErrCodeCorrupt
62 }
63 length = 4 + int(src[s-2])>>2&0x7
64 offset = int(uint32(src[s-2])&0xe0<<3 | uint32(src[s-1]))
65 66 case tagCopy2:
67 s += 3
68 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
69 return decodeErrCodeCorrupt
70 }
71 length = 1 + int(src[s-3])>>2
72 offset = int(uint32(src[s-2]) | uint32(src[s-1])<<8)
73 74 case tagCopy4:
75 s += 5
76 if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
77 return decodeErrCodeCorrupt
78 }
79 length = 1 + int(src[s-5])>>2
80 offset = int(uint32(src[s-4]) | uint32(src[s-3])<<8 | uint32(src[s-2])<<16 | uint32(src[s-1])<<24)
81 }
82 83 if offset <= 0 || d < offset || length > len(dst)-d {
84 return decodeErrCodeCorrupt
85 }
86 // Copy from an earlier sub-slice of dst to a later sub-slice.
87 // If no overlap, use the built-in copy:
88 if offset >= length {
89 copy(dst[d:d+length], dst[d-offset:])
90 d += length
91 continue
92 }
93 94 // Unlike the built-in copy function, this byte-by-byte copy always runs
95 // forwards, even if the slices overlap. Conceptually, this is:
96 //
97 // d += forwardCopy(dst[d:d+length], dst[d-offset:])
98 //
99 // We align the slices into a and b and show the compiler they are the same size.
100 // This allows the loop to run without bounds checks.
101 a := dst[d : d+length]
102 b := dst[d-offset:]
103 b = b[:len(a)]
104 for i := range a {
105 a[i] = b[i]
106 }
107 d += length
108 }
109 if d != len(dst) {
110 return decodeErrCodeCorrupt
111 }
112 return 0
113 }
114