decode.go 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. // Copyright 2011 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. package snappy
  5. import (
  6. "encoding/binary"
  7. "errors"
  8. "io"
  9. )
  10. var (
  11. // ErrCorrupt reports that the input is invalid.
  12. ErrCorrupt = errors.New("snappy: corrupt input")
  13. // ErrTooLarge reports that the uncompressed length is too large.
  14. ErrTooLarge = errors.New("snappy: decoded block is too large")
  15. // ErrUnsupported reports that the input isn't supported.
  16. ErrUnsupported = errors.New("snappy: unsupported input")
  17. errUnsupportedCopy4Tag = errors.New("snappy: unsupported COPY_4 tag")
  18. errUnsupportedLiteralLength = errors.New("snappy: unsupported literal length")
  19. )
  20. // DecodedLen returns the length of the decoded block.
  21. func DecodedLen(src []byte) (int, error) {
  22. v, _, err := decodedLen(src)
  23. return v, err
  24. }
  25. // decodedLen returns the length of the decoded block and the number of bytes
  26. // that the length header occupied.
  27. func decodedLen(src []byte) (blockLen, headerLen int, err error) {
  28. v, n := binary.Uvarint(src)
  29. if n <= 0 || v > 0xffffffff {
  30. return 0, 0, ErrCorrupt
  31. }
  32. const wordSize = 32 << (^uint(0) >> 32 & 1)
  33. if wordSize == 32 && v > 0x7fffffff {
  34. return 0, 0, ErrTooLarge
  35. }
  36. return int(v), n, nil
  37. }
  38. // Decode returns the decoded form of src. The returned slice may be a sub-
  39. // slice of dst if dst was large enough to hold the entire decoded block.
  40. // Otherwise, a newly allocated slice will be returned.
  41. // It is valid to pass a nil dst.
  42. func Decode(dst, src []byte) ([]byte, error) {
  43. dLen, s, err := decodedLen(src)
  44. if err != nil {
  45. return nil, err
  46. }
  47. if len(dst) < dLen {
  48. dst = make([]byte, dLen)
  49. }
  50. var d, offset, length int
  51. for s < len(src) {
  52. switch src[s] & 0x03 {
  53. case tagLiteral:
  54. x := uint(src[s] >> 2)
  55. switch {
  56. case x < 60:
  57. s++
  58. case x == 60:
  59. s += 2
  60. if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
  61. return nil, ErrCorrupt
  62. }
  63. x = uint(src[s-1])
  64. case x == 61:
  65. s += 3
  66. if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
  67. return nil, ErrCorrupt
  68. }
  69. x = uint(src[s-2]) | uint(src[s-1])<<8
  70. case x == 62:
  71. s += 4
  72. if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
  73. return nil, ErrCorrupt
  74. }
  75. x = uint(src[s-3]) | uint(src[s-2])<<8 | uint(src[s-1])<<16
  76. case x == 63:
  77. s += 5
  78. if uint(s) > uint(len(src)) { // The uint conversions catch overflow from the previous line.
  79. return nil, ErrCorrupt
  80. }
  81. x = uint(src[s-4]) | uint(src[s-3])<<8 | uint(src[s-2])<<16 | uint(src[s-1])<<24
  82. }
  83. length = int(x + 1)
  84. if length <= 0 {
  85. return nil, errUnsupportedLiteralLength
  86. }
  87. if length > len(dst)-d || length > len(src)-s {
  88. return nil, ErrCorrupt
  89. }
  90. copy(dst[d:], src[s:s+length])
  91. d += length
  92. s += length
  93. continue
  94. case tagCopy1:
  95. s += 2
  96. if s > len(src) {
  97. return nil, ErrCorrupt
  98. }
  99. length = 4 + int(src[s-2])>>2&0x7
  100. offset = int(src[s-2])&0xe0<<3 | int(src[s-1])
  101. case tagCopy2:
  102. s += 3
  103. if s > len(src) {
  104. return nil, ErrCorrupt
  105. }
  106. length = 1 + int(src[s-3])>>2
  107. offset = int(src[s-2]) | int(src[s-1])<<8
  108. case tagCopy4:
  109. return nil, errUnsupportedCopy4Tag
  110. }
  111. if offset > d || length > len(dst)-d {
  112. return nil, ErrCorrupt
  113. }
  114. for end := d + length; d != end; d++ {
  115. dst[d] = dst[d-offset]
  116. }
  117. }
  118. if d != dLen {
  119. return nil, ErrCorrupt
  120. }
  121. return dst[:d], nil
  122. }
  123. // NewReader returns a new Reader that decompresses from r, using the framing
  124. // format described at
  125. // https://github.com/google/snappy/blob/master/framing_format.txt
  126. func NewReader(r io.Reader) *Reader {
  127. return &Reader{
  128. r: r,
  129. decoded: make([]byte, maxUncompressedChunkLen),
  130. buf: make([]byte, MaxEncodedLen(maxUncompressedChunkLen)+checksumSize),
  131. }
  132. }
  133. // Reader is an io.Reader that can read Snappy-compressed bytes.
  134. type Reader struct {
  135. r io.Reader
  136. err error
  137. decoded []byte
  138. buf []byte
  139. // decoded[i:j] contains decoded bytes that have not yet been passed on.
  140. i, j int
  141. readHeader bool
  142. }
  143. // Reset discards any buffered data, resets all state, and switches the Snappy
  144. // reader to read from r. This permits reusing a Reader rather than allocating
  145. // a new one.
  146. func (r *Reader) Reset(reader io.Reader) {
  147. r.r = reader
  148. r.err = nil
  149. r.i = 0
  150. r.j = 0
  151. r.readHeader = false
  152. }
  153. func (r *Reader) readFull(p []byte) (ok bool) {
  154. if _, r.err = io.ReadFull(r.r, p); r.err != nil {
  155. if r.err == io.ErrUnexpectedEOF {
  156. r.err = ErrCorrupt
  157. }
  158. return false
  159. }
  160. return true
  161. }
  162. // Read satisfies the io.Reader interface.
  163. func (r *Reader) Read(p []byte) (int, error) {
  164. if r.err != nil {
  165. return 0, r.err
  166. }
  167. for {
  168. if r.i < r.j {
  169. n := copy(p, r.decoded[r.i:r.j])
  170. r.i += n
  171. return n, nil
  172. }
  173. if !r.readFull(r.buf[:4]) {
  174. return 0, r.err
  175. }
  176. chunkType := r.buf[0]
  177. if !r.readHeader {
  178. if chunkType != chunkTypeStreamIdentifier {
  179. r.err = ErrCorrupt
  180. return 0, r.err
  181. }
  182. r.readHeader = true
  183. }
  184. chunkLen := int(r.buf[1]) | int(r.buf[2])<<8 | int(r.buf[3])<<16
  185. if chunkLen > len(r.buf) {
  186. r.err = ErrUnsupported
  187. return 0, r.err
  188. }
  189. // The chunk types are specified at
  190. // https://github.com/google/snappy/blob/master/framing_format.txt
  191. switch chunkType {
  192. case chunkTypeCompressedData:
  193. // Section 4.2. Compressed data (chunk type 0x00).
  194. if chunkLen < checksumSize {
  195. r.err = ErrCorrupt
  196. return 0, r.err
  197. }
  198. buf := r.buf[:chunkLen]
  199. if !r.readFull(buf) {
  200. return 0, r.err
  201. }
  202. checksum := uint32(buf[0]) | uint32(buf[1])<<8 | uint32(buf[2])<<16 | uint32(buf[3])<<24
  203. buf = buf[checksumSize:]
  204. n, err := DecodedLen(buf)
  205. if err != nil {
  206. r.err = err
  207. return 0, r.err
  208. }
  209. if n > len(r.decoded) {
  210. r.err = ErrCorrupt
  211. return 0, r.err
  212. }
  213. if _, err := Decode(r.decoded, buf); err != nil {
  214. r.err = err
  215. return 0, r.err
  216. }
  217. if crc(r.decoded[:n]) != checksum {
  218. r.err = ErrCorrupt
  219. return 0, r.err
  220. }
  221. r.i, r.j = 0, n
  222. continue
  223. case chunkTypeUncompressedData:
  224. // Section 4.3. Uncompressed data (chunk type 0x01).
  225. if chunkLen < checksumSize {
  226. r.err = ErrCorrupt
  227. return 0, r.err
  228. }
  229. buf := r.buf[:checksumSize]
  230. if !r.readFull(buf) {
  231. return 0, r.err
  232. }
  233. checksum := uint32(buf[0]) | uint32(buf[1])<<8 | uint32(buf[2])<<16 | uint32(buf[3])<<24
  234. // Read directly into r.decoded instead of via r.buf.
  235. n := chunkLen - checksumSize
  236. if !r.readFull(r.decoded[:n]) {
  237. return 0, r.err
  238. }
  239. if crc(r.decoded[:n]) != checksum {
  240. r.err = ErrCorrupt
  241. return 0, r.err
  242. }
  243. r.i, r.j = 0, n
  244. continue
  245. case chunkTypeStreamIdentifier:
  246. // Section 4.1. Stream identifier (chunk type 0xff).
  247. if chunkLen != len(magicBody) {
  248. r.err = ErrCorrupt
  249. return 0, r.err
  250. }
  251. if !r.readFull(r.buf[:len(magicBody)]) {
  252. return 0, r.err
  253. }
  254. for i := 0; i < len(magicBody); i++ {
  255. if r.buf[i] != magicBody[i] {
  256. r.err = ErrCorrupt
  257. return 0, r.err
  258. }
  259. }
  260. continue
  261. }
  262. if chunkType <= 0x7f {
  263. // Section 4.5. Reserved unskippable chunks (chunk types 0x02-0x7f).
  264. r.err = ErrUnsupported
  265. return 0, r.err
  266. }
  267. // Section 4.4 Padding (chunk type 0xfe).
  268. // Section 4.6. Reserved skippable chunks (chunk types 0x80-0xfd).
  269. if !r.readFull(r.buf[:chunkLen]) {
  270. return 0, r.err
  271. }
  272. }
  273. }