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