snappy.go 2.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
  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 implements the snappy block-based compression format.
  5. // It aims for very high speeds and reasonable compression.
  6. //
  7. // The C++ snappy implementation is at https://github.com/google/snappy
  8. package snappy // import "github.com/golang/snappy"
  9. import (
  10. "hash/crc32"
  11. )
  12. /*
  13. Each encoded block begins with the varint-encoded length of the decoded data,
  14. followed by a sequence of chunks. Chunks begin and end on byte boundaries. The
  15. first byte of each chunk is broken into its 2 least and 6 most significant bits
  16. called l and m: l ranges in [0, 4) and m ranges in [0, 64). l is the chunk tag.
  17. Zero means a literal tag. All other values mean a copy tag.
  18. For literal tags:
  19. - If m < 60, the next 1 + m bytes are literal bytes.
  20. - Otherwise, let n be the little-endian unsigned integer denoted by the next
  21. m - 59 bytes. The next 1 + n bytes after that are literal bytes.
  22. For copy tags, length bytes are copied from offset bytes ago, in the style of
  23. Lempel-Ziv compression algorithms. In particular:
  24. - For l == 1, the offset ranges in [0, 1<<11) and the length in [4, 12).
  25. The length is 4 + the low 3 bits of m. The high 3 bits of m form bits 8-10
  26. of the offset. The next byte is bits 0-7 of the offset.
  27. - For l == 2, the offset ranges in [0, 1<<16) and the length in [1, 65).
  28. The length is 1 + m. The offset is the little-endian unsigned integer
  29. denoted by the next 2 bytes.
  30. - For l == 3, this tag is a legacy format that is no longer supported.
  31. */
  32. const (
  33. tagLiteral = 0x00
  34. tagCopy1 = 0x01
  35. tagCopy2 = 0x02
  36. tagCopy4 = 0x03
  37. )
  38. const (
  39. checksumSize = 4
  40. chunkHeaderSize = 4
  41. magicChunk = "\xff\x06\x00\x00" + magicBody
  42. magicBody = "sNaPpY"
  43. // https://github.com/google/snappy/blob/master/framing_format.txt says
  44. // that "the uncompressed data in a chunk must be no longer than 65536 bytes".
  45. maxUncompressedChunkLen = 65536
  46. // maxEncodedLenOfMaxUncompressedChunkLen equals
  47. // MaxEncodedLen(maxUncompressedChunkLen), but is hard coded to be a const
  48. // instead of a variable, so that obufLen can also be a const. Their
  49. // equivalence is confirmed by TestMaxEncodedLenOfMaxUncompressedChunkLen.
  50. maxEncodedLenOfMaxUncompressedChunkLen = 76490
  51. obufHeaderLen = len(magicChunk) + checksumSize + chunkHeaderSize
  52. obufLen = obufHeaderLen + maxEncodedLenOfMaxUncompressedChunkLen
  53. )
  54. const (
  55. chunkTypeCompressedData = 0x00
  56. chunkTypeUncompressedData = 0x01
  57. chunkTypePadding = 0xfe
  58. chunkTypeStreamIdentifier = 0xff
  59. )
  60. var crcTable = crc32.MakeTable(crc32.Castagnoli)
  61. // crc implements the checksum specified in section 3 of
  62. // https://github.com/google/snappy/blob/master/framing_format.txt
  63. func crc(b []byte) uint32 {
  64. c := crc32.Update(0, crcTable, b)
  65. return uint32(c>>15|c<<17) + 0xa282ead8
  66. }