vendor/github.com/golang/snappy/snappy.go

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