blob: 94a96c5d7b858acd337aee678134fe5d6407ca8b [file] [log] [blame]
Scott Bakered4efab2020-01-13 19:12:25 -08001// 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.
89 // If no overlap, use the built-in copy:
90 if offset > length {
91 copy(dst[d:d+length], dst[d-offset:])
92 d += length
93 continue
94 }
95
96 // Unlike the built-in copy function, this byte-by-byte copy always runs
97 // forwards, even if the slices overlap. Conceptually, this is:
98 //
99 // d += forwardCopy(dst[d:d+length], dst[d-offset:])
100 //
101 // We align the slices into a and b and show the compiler they are the same size.
102 // This allows the loop to run without bounds checks.
103 a := dst[d : d+length]
104 b := dst[d-offset:]
105 b = b[:len(a)]
106 for i := range a {
107 a[i] = b[i]
108 }
109 d += length
110 }
111 if d != len(dst) {
112 return decodeErrCodeCorrupt
113 }
114 return 0
115}