snappy.go (2394B)
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 compression format. It aims for very 6 // high speeds and reasonable compression. 7 // 8 // There are actually two Snappy formats: block and stream. They are related, 9 // but different: trying to decompress block-compressed data as a Snappy stream 10 // will fail, and vice versa. The block format is the Decode and Encode 11 // functions and the stream format is the Reader and Writer types. 12 // 13 // The block format, the more common case, is used when the complete size (the 14 // number of bytes) of the original data is known upfront, at the time 15 // compression starts. The stream format, also known as the framing format, is 16 // for when that isn't always true. 17 // 18 // The canonical, C++ implementation is at https://github.com/google/snappy and 19 // it only implements the block format. 20 package snappy 21 22 /* 23 Each encoded block begins with the varint-encoded length of the decoded data, 24 followed by a sequence of chunks. Chunks begin and end on byte boundaries. The 25 first byte of each chunk is broken into its 2 least and 6 most significant bits 26 called l and m: l ranges in [0, 4) and m ranges in [0, 64). l is the chunk tag. 27 Zero means a literal tag. All other values mean a copy tag. 28 29 For literal tags: 30 - If m < 60, the next 1 + m bytes are literal bytes. 31 - Otherwise, let n be the little-endian unsigned integer denoted by the next 32 m - 59 bytes. The next 1 + n bytes after that are literal bytes. 33 34 For copy tags, length bytes are copied from offset bytes ago, in the style of 35 Lempel-Ziv compression algorithms. In particular: 36 - For l == 1, the offset ranges in [0, 1<<11) and the length in [4, 12). 37 The length is 4 + the low 3 bits of m. The high 3 bits of m form bits 8-10 38 of the offset. The next byte is bits 0-7 of the offset. 39 - For l == 2, the offset ranges in [0, 1<<16) and the length in [1, 65). 40 The length is 1 + m. The offset is the little-endian unsigned integer 41 denoted by the next 2 bytes. 42 - For l == 3, this tag is a legacy format that is no longer issued by most 43 encoders. Nonetheless, the offset ranges in [0, 1<<32) and the length in 44 [1, 65). The length is 1 + m. The offset is the little-endian unsigned 45 integer denoted by the next 4 bytes. 46 */