Uncompressing DEFLATE Data

posted by Stephan Brumme

The Most Common Compression Algorithm

Everyone knows the widespread ZIP file format. Some Windows users may have never heard of GZIP, but all Unix users did. 99% percent of all ZIPs are encoded with the so-called DEFLATE algorithm, specified as RFC 1951. The same holds true for PNG images, some PDFs, compressed HTTP data transfer and many more.

I wanted to have a C++ implementation without strange dependencies and weird pointer arithmentic. I wanted something like this:
#include "Inflate.h" std::vector<unsigned char> uncompressed = Inflate("filename.gz");
So I wrote my own DEFLATE decoder in pure C++/STL. It's reasonably fast - somewhere between 50 and 100 MByte/s (uncompressed data) - and compiles easily with Visual C++ and GCC (older version should be fine, too). Git users: scroll down to the repository link
Download  deflate-decoder.zip
Latest release: November 27, 2011, size: 25.2 kBytes

CRC32: 7caba0b2
MD5: 079bbc381743a0f64e29908548bfeed5
SHA1: 71a7be05c51bda6026184980580a775a9d5e8ef6
SHA256:8ffd911e74a4d378711816fb473dff8ed930a871d20275cfb11247eaf3384eba

Stay up-to-date:git clone http://create.stephan-brumme.com/deflate-decoder/.git

If you encounter any bugs/problems or have ideas for improving future versions, please write me an email: create@stephan-brumme.com

Changelog

Code Structure

The main class Inflate, which derives from std::vector<unsigned char> contains the DEFLATE decompression algorithm, accesses three helper classes: BinaryInputBuffer, HuffmanTree and Hash: These three helper classes are completely independent of each other. They have simple #includes such as string, vector and fstream.

However, you don't need to worry about them. They are automatically included by Inflate. An extremely simple replacement for the gunzip program looks like this:
hide Uncompress GZ files #include "Inflate.h" #include <iostream> #include <fstream> #include <ctime> #pragma warning (disable: 4996) // ctime unsafe int main(int argc, char* argv[]) { // file name via command-line if (argc != 2) { std::cout << "Syntax: uncompress file.gz" << std::endl; return 1; } const char* filename = argv[1]; // decompress std::cout << "Decompressing " << filename << " ..." << std::endl; clock_t startTime = clock(); Inflate decoded(filename); double duration = (clock() - startTime) / double(CLOCKS_PER_SEC); // no problem during decompression and checksum correct ? if (!decoded.isValid()) { std::cout << "!!! FAILED, error " << decoded.getError() << " (" << decoded.getErrorText() << ") !!!" << std::endl; return 2; } // write uncompressed data to disk std::string outputFilename = decoded.getFilename(); if (outputFilename.empty()) outputFilename = "decompressed.data"; std::ofstream output(outputFilename.c_str(), std::ios::binary); output.write((const char*)&decoded[0], decoded.size()); output.close(); // display some statistics time_t timestamp = decoded.getTimestamp(); std::cout << "file: " << decoded.getFilename() << ", timestamp: " << ctime(&timestamp) << std::endl << duration << "s => " << decoded.sizeCompressed()/(duration*1024*1024) << "MByte/s (gz), " << decoded.size() /(duration*1024*1024) << "MByte/s (raw)" << std::endl; return 0; }
Click show to make the classes' source code visible:
show Inflate.h // ////////////////////////////////////////////////////////// // Inflate.h // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #pragma once #pragma warning(disable: 4530) // exception handling disabled #include <vector> #include <string> #include "HuffmanTree.h" // HuffmanTree::Code class BinaryInputBuffer; /// decompress data previously crunshed with Deflate algorithm (GZ, PNG, ...) class Inflate : public std::vector<unsigned char> { public: /// decode a file explicit Inflate(const std::string& filename, bool isRawStream = false, bool checkCrc = true); /// decode a in-memory buffer Inflate(void* data, size_t numBytes, bool isRawStream = false, bool checkCrc = true); /// errors enum Error { Successful, NotStarted, Working, InvalidPointer, InvalidFile, InvalidHeaderID, InvalidCompressionAlgorithm, InvalidBlockMethod, InvalidData, InvalidCrc, FilesizeMismatch }; /// get error code Error getError() const { return _error; } /// error code translated to English (empty if Successful) const char* getErrorText() const; /// true, if everything is okay bool isValid() const { return _error == Successful; } /// original filename (empty if not present in GZip header) std::string getFilename() const { return _filename; } /// original filename (empty if not present in GZip header) std::string getComment() const { return _comment; } /// get timestamp (might be missing => 0) time_t getTimestamp() const { return _timestamp; } /// compression level (might be non-sense, depending on encoder) unsigned int getCompressionLevel() const { return _compressionLevel; } /// compressed size size_t sizeCompressed() const { return _sizeCompressed; } private: /// main decoder, does everything at once (invoked by constructor), true if successful bool load (BinaryInputBuffer& buffer, bool isRawStream, bool checkCrc); /// parse header, true if okay bool parseHeader (BinaryInputBuffer& buffer); /// decode block (any method), true if okay bool decodeBlock (BinaryInputBuffer& buffer, bool& isFinal); /// decode block (method 0), true if okay bool copyBlock (BinaryInputBuffer& buffer); /// decode block (method 1&2), true if okay bool inflateBlock(BinaryInputBuffer& buffer, const HuffmanTree& tree, const HuffmanTree& distanceTree); /// extract token from buffer, based on current Huffman tree HuffmanTree::Code nextToken(BinaryInputBuffer& buffer, const HuffmanTree& tree); /// error code Error _error; /// filename (as stored in header) std::string _filename; /// comment std::string _comment; /// timestamp time_t _timestamp; /// compression level unsigned int _compressionLevel; /// compressed size size_t _sizeCompressed; /// bytes parsed yet (for debugging) size_t _sizeParsed; /// default bitlength Huffman tree static HuffmanTree _defaultTree; /// default empty Huffman tree static HuffmanTree _emptyTree; };
show Inflate.cpp // ////////////////////////////////////////////////////////// // Inflate.cpp // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #include "Inflate.h" #include "BinaryInputBuffer.h" #include "Hash.h" #include <cassert> // some constants ... static const HuffmanTree::Code MaxBitLength = 288; static const HuffmanTree::Code MaxToken = 285; static const HuffmanTree::Code InvalidToken = 300; // statics ... HuffmanTree Inflate::_defaultTree = HuffmanTree::getDefaultTree(); HuffmanTree Inflate::_emptyTree; /// decode a file Inflate::Inflate(const std::string& filename, bool isRawStream, bool checkCrc) : std::vector<unsigned char>(), _error(NotStarted), _filename(), // filename stored in gzip ! _comment(), _timestamp(0), _compressionLevel(0), _sizeCompressed(0), _sizeParsed(0) { // open file BinaryInputBuffer buffer(filename); _sizeCompressed = buffer.size(); if (_sizeCompressed == 0) { _error = InvalidFile; return; } // ... and decode data load(buffer, isRawStream, checkCrc); } /// decode a in-memory buffer Inflate::Inflate(void* data, size_t numBytes, bool isRawStream, bool checkCrc) : std::vector<unsigned char>(), _error(NotStarted), _filename(), _comment(), _timestamp(0), _compressionLevel(0), _sizeCompressed(numBytes), _sizeParsed(0) { // check parameters assert(data && numBytes > 0); if (!data || numBytes == 0) { _error = InvalidPointer; return; } // wrap into a buffer BinaryInputBuffer buffer(data, numBytes); // ... and decode data load(buffer, isRawStream, checkCrc); } /// main decoder bool Inflate::load(BinaryInputBuffer& buffer, bool isRawStream, bool checkCrc) { _error = Working; // heuristic size_t uncompressedSize = buffer.getNumBitsLeft() / 5; // GZ header if (!isRawStream) { if (!parseHeader(buffer)) return false; // error codes are set by parseHeader // get uncompressed filesize uncompressedSize = buffer.at(buffer.size()-1) << 24; uncompressedSize += buffer.at(buffer.size()-2) << 16; uncompressedSize += buffer.at(buffer.size()-3) << 8; uncompressedSize += buffer.at(buffer.size()-4); } // pre-allocate memory reserve(std::min<size_t>(uncompressedSize, 64*1024*1024)); // update CRC32 on-the-fly unsigned int rollingCrc32 = 0; // intermediate hash size_t checkedCrc32 = 0; // bytes processed // start decompression bool isFinal = false; while (decodeBlock(buffer, isFinal)) { // update CRC if (!isRawStream && checkCrc) { size_t blockSize = size() - checkedCrc32; rollingCrc32 = Hash::crc32(&operator[](checkedCrc32), blockSize, rollingCrc32); checkedCrc32 += blockSize; } _sizeParsed = buffer.getNumBytesRead(); // done with decoding ? if (isFinal) break; } // aborted during block decoding ? if (!isFinal) { _error = InvalidData; _sizeParsed = buffer.getNumBytesRead(); return false; } // skip fill bits buffer.removeBits(buffer.getNumBitsLeft() % 8); // check data integrity if (!isRawStream && checkCrc) { // expected CRC if (rollingCrc32 != buffer.getInt()) { _error = InvalidCrc; _sizeParsed = buffer.getNumBytesRead(); return false; } // expected size if ((size() & 0xFFFFFFFF) != buffer.getInt()) { _error = FilesizeMismatch; _sizeParsed = buffer.getNumBytesRead(); return false; } } // great news ... _sizeParsed = buffer.getNumBytesRead(); _error = Successful; return true; } /// parse header bool Inflate::parseHeader(BinaryInputBuffer& buffer) { // GZ signature unsigned char id1 = buffer.getByte(); unsigned char id2 = buffer.getByte(); assert(id1 == 0x1F && id2 == 0x8B); if (id1 != 0x1F || id2 != 0x8B) { _error = InvalidHeaderID; _sizeParsed = buffer.getNumBytesRead(); return false; } // must be DEFLATE algorithm unsigned char algorithm = buffer.getByte(); assert(algorithm == 0x08); if (algorithm != 0x08) { _error = InvalidCompressionAlgorithm; _sizeParsed = buffer.getNumBytesRead(); return false; } // various flags unsigned char flags = buffer.getByte(); // timestamp _timestamp = time_t(buffer.getInt()); // compression level _compressionLevel = buffer.getByte(); // skip file system buffer.getByte(); // 0 - FAT (MS-DOS, OS/2, NT/Win32) // 1 - Amiga // 2 - VMS (or OpenVMS) // 3 - Unix // 4 - VM/CMS // 5 - Atari TOS // 6 - HPFS (OS/2, NT) // 7 - Macintosh // 8 - Z-System // 9 - CP/M // 10 - TOPS-20 // 11 - NTFS (NT) // 12 - QDOS // 13 - Acorn RISCOS // 255 - unknown // extras (unused) if (flags & 0x04) { unsigned numBytes = buffer.getWord(); while (numBytes--) buffer.getByte(); } // filename if (flags & 0x08) { _filename.clear(); char copy; while (0 != (copy = buffer.getByte())) _filename += copy; } // comment if (flags & 0x10) { char copy; while (0 != (copy = buffer.getByte())) _comment += copy; } // header CRC16 (unused) if (flags & 0x02) buffer.getWord(); return true; } /// decode block (any method), true if okay bool Inflate::decodeBlock (BinaryInputBuffer& buffer, bool& isFinal) { // block header isFinal = buffer.getBool(); size_t method = buffer.getBits(2); // raw block (uncompressed) if (method == 0) return copyBlock(buffer); // using static tree if (method == 1) return inflateBlock(buffer, _defaultTree, _emptyTree); // read dynamic tree if (method == 2) { // alphabet size size_t numLiterals = 257 + buffer.getBits(5); size_t numDistance = 1 + buffer.getBits(5); size_t numCodeLength = 4 + buffer.getBits(4); // read 19 codes defining bit lengths const size_t CodeLengths = 19; HuffmanTree::BitLengths codeLength(CodeLengths); static const unsigned char CodeLengthOrder[CodeLengths] = { 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15 }; for (size_t i = 0; i < numCodeLength; i++) codeLength[CodeLengthOrder[i]] = (unsigned char)buffer.getBits(3); HuffmanTree codeStrings(codeLength, HuffmanTree::Decoding); // read bit lengths themselves HuffmanTree::Code lastToken = 0; HuffmanTree::BitLengths bitLength; bitLength.reserve(MaxBitLength); while (bitLength.size() < numLiterals+numDistance) { HuffmanTree::Code token = nextToken(buffer, codeStrings); unsigned int howOften = 0; // single literal if (token < 16) { howOften = 1; lastToken = token; } // repeat last 3x-6x else if (token == 16) { howOften = 3 + buffer.getBits(2); } // 3x-10x zero else if (token == 17) { howOften = 3 + buffer.getBits(3); lastToken = 0; } else if (token == 18)// 11x-138x zero { howOften = 11 + buffer.getBits(7); lastToken = 0; } else { _error = InvalidData; _sizeParsed = buffer.getNumBytesRead(); return false; } // repeat lastTaken (howOften times) while (howOften--) bitLength.push_back((unsigned char)lastToken); } // fill up with zeros bitLength.resize(numLiterals+32, 0); // extract distance code lengths HuffmanTree::BitLengths distanceLength; for (size_t i = 0; i < 32; i++) distanceLength.push_back(bitLength[i + numLiterals]); // cut back, only literals bitLength.resize(numLiterals); // removed too much ? bitLength.resize(MaxBitLength, 0); // let's decode ! return inflateBlock(buffer, HuffmanTree(bitLength, HuffmanTree::Decoding), HuffmanTree(distanceLength, HuffmanTree::Decoding)); } // invalid method _error = InvalidBlockMethod; _sizeParsed = buffer.getNumBytesRead(); return false; } /// method 0 bool Inflate::copyBlock(BinaryInputBuffer& buffer) { // skip all bits until reaching next byte boundary buffer.removeBits(buffer.getNumBitsLeft() % 8); // 16 bit block length size_t length = buffer.getBits(16); // skip complementary block length size_t complement = buffer.getBits(16); if (length != 0xFFFF - complement) return false; // copy for (size_t i = 0; i < length; i++) push_back(buffer.getByte()); return true; } /// method 1&2 bool Inflate::inflateBlock(BinaryInputBuffer& buffer, const HuffmanTree& tree, const HuffmanTree& distanceTree) { // decode tokens HuffmanTree::Code token; while (HuffmanTree::EndOfBlock != (token = nextToken(buffer, tree))) { // simple literal ? if (token < HuffmanTree::EndOfBlock) { push_back((unsigned char)token); continue; } // error ? assert(token < InvalidToken); if (token == InvalidToken) { _error = InvalidData; _sizeParsed = buffer.getNumBytesRead(); return false; } // it's a (length,distance) pair token -= 257; // get length, maybe with extra bits static const unsigned short CopyLength[29] = { 3, /* 258 */ 4, /* 259 */ 5,/* 257 */ 6, /* 261 */ 7, /* 262 */ 8, /* 263 */ 9, /* 264 */ 10,/* 260 */ 11, /* 266 */ 13, /* 267 */ 15, /* 268 */ 17, /* 269 */ 19,/* 265 */ 23, /* 271 */ 27, /* 272 */ 31, /* 273 */ 35, /* 274 */ 43,/* 270 */ 51, /* 276 */ 59, /* 277 */ 67, /* 278 */ 83, /* 279 */ 99,/* 275 */ 115, /* 281 */ 131, /* 282 */ 163, /* 283 */ 195, /* 284 */ 227,/* 280 */ 258 };/* 285 */ size_t length = CopyLength[token]; static const unsigned char ExtraLengthBits[29] = { 0, /* 258 */ 0, /* 259 */ 0, /* 260 */ 0,/* 257 */ 0, /* 262 */ 0, /* 263 */ 0, /* 264 */ 0,/* 261 */ 1, /* 266 */ 1, /* 267 */ 1, /* 268 */ 1,/* 265 */ 2, /* 270 */ 2, /* 271 */ 2, /* 272 */ 2,/* 269 */ 3, /* 274 */ 3, /* 275 */ 3, /* 276 */ 3,/* 273 */ 4, /* 278 */ 4, /* 279 */ 4, /* 280 */ 4,/* 277 */ 5, /* 282 */ 5, /* 283 */ 5, /* 284 */ 5,/* 281 */ 0 };/* 285 */ unsigned char extraLength = ExtraLengthBits[token]; length += buffer.getBits(extraLength); // get distance HuffmanTree::Code distanceCode; if (distanceTree.empty()) { distanceCode = HuffmanTree::Code(Bits::reverse(buffer.getBits(5), 5)); // fixed tree } else { distanceCode = nextToken(buffer, distanceTree); // dynamic tree if (distanceCode == InvalidToken) { _error = InvalidData; _sizeParsed = buffer.getNumBytesRead(); return false; } } static const unsigned short CopyDistance[32] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577, 32769, 49153 };/* the last two are Deflate64 only */ size_t distance = CopyDistance[distanceCode]; static const unsigned char ExtraDistanceBits[32/2] = { 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };/* the last is Deflate64 only */ unsigned char moreBits = ExtraDistanceBits[distanceCode/2]; distance += buffer.getBits(moreBits); // byte-wise copy size_t offset = size() - distance; for (size_t i = 0; i < length; i++) { unsigned char copyByte = operator[](offset+i); push_back(copyByte); } } return true; } /// extract token from buffer, based on current Huffman tree HuffmanTree::Code Inflate::nextToken(BinaryInputBuffer& buffer, const HuffmanTree& tree) { // get bits HuffmanTree::Code compareTo = HuffmanTree::Code(buffer.peekBits(tree.getMaxBits())); // find matching code for (HuffmanTree::NumBits bits = tree.getInstantMaxBit(); bits <= tree.getMaxBits(); bits++) { // find leaf HuffmanTree::Code mask = (1 << bits) - 1; HuffmanTree::Leaf leaf = tree.getLeaf(compareTo & mask); // correct number of bits ? if (leaf.numBits <= bits) { // remove used bits buffer.removeBits(leaf.numBits); return leaf.code; } } // oops ? return InvalidToken; } /// error code translated to English (empty if Successful) const char* Inflate::getErrorText() const { switch (getError()) { case Successful: return ""; case NotStarted: return "Not Started Yet"; case Working: return "Working"; case InvalidPointer: return "Invalid Pointer"; case InvalidFile: return "Invalid/Missing File"; case InvalidHeaderID: return "Invalid Header ID (probably not a GZipped file)"; case InvalidCompressionAlgorithm: return "Invalid Compression Algorithm (data corrupted)"; case InvalidBlockMethod: return "Invalid Block Method (data corrupted)"; case InvalidData: return "Invalid Data"; case InvalidCrc: return "Invalid Crc (checksum error)"; case FilesizeMismatch: return "Filesize Mismatch (number of decoded bytes differs from expected)"; default: return "Unknown Error"; } }
show BinaryInputBuffer.h // ////////////////////////////////////////////////////////// // BinaryInputBuffer.h // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #pragma once #pragma warning (disable: 4530) // missing exception handling #include <string> #include <fstream> /// read file bit-wise class BinaryInputBuffer { public: /// default buffer size if not completely loaded into memory enum { CacheSize = 256 }; /// read from file (it's often faster to pre-load the complete file) explicit BinaryInputBuffer(const std::string& filename, bool preloadCompleteFile = false); /// already in memory BinaryInputBuffer(const void* buffer, size_t size); /// close file virtual ~BinaryInputBuffer(); /// get number of bytes read so far size_t getNumBytesRead() const; /// get number of bits left in the buffer size_t getNumBitsLeft() const; /// true, if no bits left bool empty() const; /// total size in bytes, don't care about how much is read or left size_t size() const; /// take a look at the next bits without modifying the buffer unsigned int peekBits (unsigned char numBits); /// increment buffer pointers/offsets void removeBits(unsigned char numBits); /// get the next bits and increment buffer pointers/offsets unsigned int getBits (unsigned char numBits); /// get 8 bits unsigned char getByte(); /// get 16 bits unsigned short getWord(); /// get 32 bits unsigned int getInt (); /// get a single bit bool getBool(); /// get a single bit BinaryInputBuffer& operator>>(bool& bit ) { bit = getBool(); return *this; } /// get 8 bits BinaryInputBuffer& operator>>(unsigned char& byte) { byte = getByte(); return *this; } /// get 16 bits BinaryInputBuffer& operator>>(unsigned short& word) { word = getWord(); return *this; } /// get 32 bits BinaryInputBuffer& operator>>(unsigned int& dword) { dword = getInt (); return *this; } /// read byte at offset, and immediately go back to position we were before unsigned char at(size_t offset); private: /// simple I/O buffering, faster than C lib's built-in functions unsigned char getBufferedByte(); /// bit/byte file stream std::ifstream _stream; /// total number of bytes in the stream size_t _size; /// total number of bytes read so far size_t _read; /// total bits left (initially, it's 8*_size) size_t _bitsLeft; /// store bits until next byte boundary unsigned int _bitBuffer; /// number of valid bits in _bitBuffer unsigned char _bitBufferSize; /// keep in memory ? bool _inMemory; /// new/delete allowed ? bool _hasCacheOwnership; /// buffer unsigned char* _cache; /// position of next byte size_t _cacheOffset; /// position beyond last valid byte size_t _cacheSize; };
show BinaryInputBuffer.cpp // ////////////////////////////////////////////////////////// // BinaryInputBuffer.cpp // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #include "BinaryInputBuffer.h" #pragma warning (disable: 4996) // fopen is unsafe #include <cassert> /// read from file BinaryInputBuffer::BinaryInputBuffer(const std::string& filename, bool preloadCompleteFile) : _stream(), _size(0), _read(0), _bitsLeft(0), _bitBuffer(0), _bitBufferSize(0), _inMemory(preloadCompleteFile), _hasCacheOwnership(true), _cache(NULL), _cacheOffset(0), _cacheSize(0) { assert(!filename.empty()); if (filename.empty()) return; _stream.open(filename.c_str(), std::ios::in | std::ios::binary); // open file if (!_stream) return; // get file size _stream.seekg(0, std::ios_base::end); _size = _stream.tellg(); _stream.seekg(0, std::ios_base::beg); // load first segment (or even the complete file) _cacheSize = _inMemory ? _size : size_t(CacheSize); _cache = new unsigned char[_cacheSize]; _stream.read((char*)_cache, _cacheSize); if (_inMemory) _stream.close(); // total number of bits _bitsLeft = 8 * _size; } /// already in memory BinaryInputBuffer::BinaryInputBuffer(const void* buffer, size_t size) : _stream(), _size(size), _read(0), _bitsLeft(8 * size), _bitBuffer(0), _bitBufferSize(0), _inMemory(true), _hasCacheOwnership(false), _cache((unsigned char*)buffer), _cacheOffset(0), _cacheSize(size) { assert(buffer); if (!buffer) _size = _bitsLeft = _cacheSize = 0; } /// close file BinaryInputBuffer::~BinaryInputBuffer() { if (_hasCacheOwnership) delete[] _cache; } /// get number of bytes read so far size_t BinaryInputBuffer::getNumBytesRead() const { return _read; } /// get number of bits left in the buffer size_t BinaryInputBuffer::getNumBitsLeft() const { return _bitsLeft; } /// true, if no bits left bool BinaryInputBuffer::empty() const { return _bitsLeft == 0; } /// total size in bytes, don't care about how much is read or left size_t BinaryInputBuffer::size() const { return _size; } /// take a look at the next bits without modifying the buffer unsigned int BinaryInputBuffer::peekBits(unsigned char numBits) { assert(numBits <= 16); // move 8 bits from stream to buffer while (_bitBufferSize < numBits) { // get one byte from stream and add to internal buffer unsigned int byte = getBufferedByte(); _bitBuffer |= byte << _bitBufferSize; _bitBufferSize += 8; } // return desired bits unsigned int bitMask = (1 << numBits) - 1; return _bitBuffer & bitMask; } /// get the next bits and increment buffer pointers/offsets unsigned int BinaryInputBuffer::getBits(unsigned char numBits) { unsigned int result = peekBits(numBits); removeBits(numBits); return result; } /// get 8 bits unsigned char BinaryInputBuffer::getByte() { return (unsigned char)getBits(8); } /// get 16 bits unsigned short BinaryInputBuffer::getWord() { unsigned short firstByte = getByte(); return firstByte | (getByte() << 8); } /// get 32 bits unsigned int BinaryInputBuffer::getInt() { assert(sizeof(unsigned int) == 4); unsigned int result = getByte(); result |= getByte() << 8; result |= getByte() << 16; result |= getByte() << 24; return result; } /// get a single bit bool BinaryInputBuffer::getBool() { return getBits(1) == 1; } /// increment buffer pointers/offsets void BinaryInputBuffer::removeBits(unsigned char numBits) { _bitBuffer >>= numBits; _bitBufferSize -= numBits; _bitsLeft -= numBits; } /// read byte at offset, and immediately go back to position we were before unsigned char BinaryInputBuffer::at(size_t offset) { // file already in memory ? if (_inMemory) return _cache[offset]; // current position std::streampos current = _stream.tellg(); // read byte char result; _stream.seekg(offset, std::ios_base::beg); _stream.get(result); // go back _stream.seekg(current, std::ios_base::beg); return (unsigned char)result; } /// simple I/O buffering, faster than C lib's built-in functions unsigned char BinaryInputBuffer::getBufferedByte() { // fill buffer if (_cacheOffset >= _cacheSize) { assert(_stream); assert(!_inMemory); _stream.read((char*)_cache, CacheSize); _cacheOffset = 0; } _read++; // single byte return _cache[_cacheOffset++]; }
show HuffmanTree.h // ////////////////////////////////////////////////////////// // HuffmanTree.h // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #pragma once #pragma warning (disable: 4530) // missing exception handling #include <vector> #include <cstddef> /// Huffman tree class HuffmanTree { public: /// store 16 bits (see MaxCodeLength) typedef unsigned short Code; /// code length in bits typedef unsigned char NumBits; /// dictionary entry struct Leaf { // empty/invalid entry Leaf() : code(0), numBits(0) {} // valid entry Leaf(Code code_, NumBits bits_) : code(code_), numBits(bits_) {} // code bits Code code; // length of code in bits NumBits numBits; }; /// dictionary typedef std::vector<Leaf> Dictionary; /// bits per code typedef std::vector<NumBits> BitLengths; /// max. bits per code static const NumBits MaxCodeLength = 15; /// default max. bit length of instant lookup codes static const NumBits InstantMaxBit = 10; /// marks end of a block static const Code EndOfBlock = 256; /// mapping direction enum Mapping { Encoding, Decoding }; /// empty tree HuffmanTree() : _leaves(), _minBits(MaxCodeLength), _maxBits(0), _instantMaxBit(0) {} /// build tree explicit HuffmanTree(const BitLengths& bitLengthMapping, Mapping direction = Decoding); /// true, if encoding bool isEncoding() const { return _isEncoding; } /// length of shortest code NumBits getMinBits() const { return _minBits; } /// length of longest code NumBits getMaxBits() const { return _maxBits; } /// current threshold for smallLeaves/leaves NumBits getInstantMaxBit() const { return _instantMaxBit; } /// true, if empty bool empty() const { return _leaves.empty(); } /// look up a leaf Leaf getLeaf(size_t index) const { return _leaves[index]; } /// return Deflate's default bitlength tree static HuffmanTree getDefaultTree(); private: /// true, if encoding bool _isEncoding; /// dictionary of all long codes/bits Dictionary _leaves; /// length of shortest code NumBits _minBits; /// length of longest code NumBits _maxBits; /// current threshold for smallLeaves/leaves NumBits _instantMaxBit; };
show HuffmanTree.cpp // ////////////////////////////////////////////////////////// // HuffmanTree.cpp // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #include "HuffmanTree.h" #include "Hash.h" // Bits::reverse #include <cassert> #include <algorithm> // std::min / std::max /// create new Huffman tree based on bit code lengths HuffmanTree::HuffmanTree(const BitLengths& bitLengthMapping, Mapping direction) : _isEncoding(direction == Encoding), _leaves(), _minBits(MaxCodeLength), _maxBits(0), _instantMaxBit(0) { // get frequencies of each bit length and ignore 0's Code bitLengthCount[MaxCodeLength] = {0}; for (size_t i = 0; i < bitLengthMapping.size(); i++) bitLengthCount[bitLengthMapping[i]]++; bitLengthCount[0] = 0; // shortest and longest codes _maxBits = 0; _minBits = MaxCodeLength; for (NumBits bits = 1; bits <= MaxCodeLength; bits++) { if (bitLengthCount[bits] == 0) continue; _minBits = std::min(_minBits, bits); _maxBits = std::max(_maxBits, bits); } _leaves.resize(1 << _maxBits); // smallest suitable cache _instantMaxBit = std::min(InstantMaxBit, _maxBits); Code instantMask = (1 << _instantMaxBit) - 1; // find bit code for first element of each bitLength group Code code = 0; Code nextCode[MaxCodeLength]; for (NumBits bits = _minBits; bits <= _maxBits; bits++) { code += bitLengthCount[bits-1]; code <<= 1; nextCode[bits] = code; } // create binary codes for each literal for (Code i = 0; i < bitLengthMapping.size(); i++) { NumBits bits = bitLengthMapping[i]; // unused literal ? if (bits == 0) continue; // get canonical code Code canonical = nextCode[bits]; nextCode[bits]++; /// reverse bit order assert(bits <= MaxCodeLength); Code reverse = Code(Bits::reverse((unsigned int)canonical, bits)); // store in encoding dictionary if (_isEncoding) { _leaves[i] = Leaf(reverse, bits); continue; } // store in decoding dictionary Leaf leaf = Leaf(i, bits); _leaves[reverse] = leaf; // replicate short codes ? if (bits <= _instantMaxBit) { // spread to all longer index positions Code step = 1 << bits; for (Code spread = reverse+step; spread <= instantMask; spread += step) _leaves[spread] = leaf; } } } /// return Deflate's default bitlength tree HuffmanTree HuffmanTree::getDefaultTree() { HuffmanTree::BitLengths defaultBitLengths(288, 0); size_t i = 0; for (; i < 144; i++) defaultBitLengths[i] = 8; for (; i < 256; i++) defaultBitLengths[i] = 9; for (; i < 280; i++) defaultBitLengths[i] = 7; for (; i < 288; i++) defaultBitLengths[i] = 8; return HuffmanTree(defaultBitLengths, HuffmanTree::Decoding); }
show Hash.h // ////////////////////////////////////////////////////////// // Hash.h // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #pragma once #include <cstddef> namespace Hash { /// compute CRC32 based on polynom 0xEDB88320L unsigned int crc32 (const void* data, size_t length, unsigned int previousCrc32 = 0); } namespace Bits { /// reverse bit order unsigned int reverse(unsigned int x, size_t numBits); }
show Hash.cpp // ////////////////////////////////////////////////////////// // Hash.cpp // Copyright (c) 2011 Stephan Brumme. All rights reserved. // #include "Hash.h" #include <cassert> namespace Hash { /// compute Adler32 hash /*unsigned int adler32(const void* data, size_t length, unsigned int previousAdler32) { if (!data || length == 0) return previousAdler32; const unsigned int AdlerModulo = 65521; unsigned int a = previousAdler32 & 0x0000FFFF; unsigned int b = previousAdler32 >> 16; const unsigned char* current = (unsigned char*) data; // unrolling const unsigned int Unrolling = 16; // more than 16 doesn't seem to make it faster ... while (length > Unrolling) { a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a += *current++; b += a; a %= AdlerModulo; b %= AdlerModulo; length -= Unrolling; } // remainder while (length--) { a += *current++; b += a; a %= AdlerModulo; b %= AdlerModulo; } return (b << 16) | a; }*/ /// look-up table for sbox hash static const unsigned int crc32Lookup[8][256] = { //// generated by a standard CRC32 table maker (crc32Lookup[0]) ... //const unsigned int Polynomial = 0xEDB88320; //for (unsigned int i = 0; i <= 0xFF; i++) //{ // unsigned int crc = i; // unsigned int numBits = 8; // while (numBits--) // crc = (crc >> 1) ^ ((crc & 1) * Polynomial); // crc32Lookup[0][i] = crc; //} //// ... and the following slicing-by-8 algorithm (from Intel): //// http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf //// http://sourceforge.net/projects/slicing-by-8/ //for (unsigned int i = 0; i <= 0xFF; i++) //{ // crc32Lookup[1][i] = (crc32Lookup[0][i] >> 8) ^ crc32Lookup[0][crc32Lookup[0][i] & 0xFF]; // crc32Lookup[2][i] = (crc32Lookup[1][i] >> 8) ^ crc32Lookup[0][crc32Lookup[1][i] & 0xFF]; // crc32Lookup[3][i] = (crc32Lookup[2][i] >> 8) ^ crc32Lookup[0][crc32Lookup[2][i] & 0xFF]; // crc32Lookup[4][i] = (crc32Lookup[3][i] >> 8) ^ crc32Lookup[0][crc32Lookup[3][i] & 0xFF]; // crc32Lookup[5][i] = (crc32Lookup[4][i] >> 8) ^ crc32Lookup[0][crc32Lookup[4][i] & 0xFF]; // crc32Lookup[6][i] = (crc32Lookup[5][i] >> 8) ^ crc32Lookup[0][crc32Lookup[5][i] & 0xFF]; // crc32Lookup[7][i] = (crc32Lookup[6][i] >> 8) ^ crc32Lookup[0][crc32Lookup[6][i] & 0xFF]; //} { 0x00000000,0x77073096,0xEE0E612C,0x990951BA,0x076DC419,0x706AF48F,0xE963A535,0x9E6495A3, 0x0EDB8832,0x79DCB8A4,0xE0D5E91E,0x97D2D988,0x09B64C2B,0x7EB17CBD,0xE7B82D07,0x90BF1D91, 0x1DB71064,0x6AB020F2,0xF3B97148,0x84BE41DE,0x1ADAD47D,0x6DDDE4EB,0xF4D4B551,0x83D385C7, 0x136C9856,0x646BA8C0,0xFD62F97A,0x8A65C9EC,0x14015C4F,0x63066CD9,0xFA0F3D63,0x8D080DF5, 0x3B6E20C8,0x4C69105E,0xD56041E4,0xA2677172,0x3C03E4D1,0x4B04D447,0xD20D85FD,0xA50AB56B, 0x35B5A8FA,0x42B2986C,0xDBBBC9D6,0xACBCF940,0x32D86CE3,0x45DF5C75,0xDCD60DCF,0xABD13D59, 0x26D930AC,0x51DE003A,0xC8D75180,0xBFD06116,0x21B4F4B5,0x56B3C423,0xCFBA9599,0xB8BDA50F, 0x2802B89E,0x5F058808,0xC60CD9B2,0xB10BE924,0x2F6F7C87,0x58684C11,0xC1611DAB,0xB6662D3D, 0x76DC4190,0x01DB7106,0x98D220BC,0xEFD5102A,0x71B18589,0x06B6B51F,0x9FBFE4A5,0xE8B8D433, 0x7807C9A2,0x0F00F934,0x9609A88E,0xE10E9818,0x7F6A0DBB,0x086D3D2D,0x91646C97,0xE6635C01, 0x6B6B51F4,0x1C6C6162,0x856530D8,0xF262004E,0x6C0695ED,0x1B01A57B,0x8208F4C1,0xF50FC457, 0x65B0D9C6,0x12B7E950,0x8BBEB8EA,0xFCB9887C,0x62DD1DDF,0x15DA2D49,0x8CD37CF3,0xFBD44C65, 0x4DB26158,0x3AB551CE,0xA3BC0074,0xD4BB30E2,0x4ADFA541,0x3DD895D7,0xA4D1C46D,0xD3D6F4FB, 0x4369E96A,0x346ED9FC,0xAD678846,0xDA60B8D0,0x44042D73,0x33031DE5,0xAA0A4C5F,0xDD0D7CC9, 0x5005713C,0x270241AA,0xBE0B1010,0xC90C2086,0x5768B525,0x206F85B3,0xB966D409,0xCE61E49F, 0x5EDEF90E,0x29D9C998,0xB0D09822,0xC7D7A8B4,0x59B33D17,0x2EB40D81,0xB7BD5C3B,0xC0BA6CAD, 0xEDB88320,0x9ABFB3B6,0x03B6E20C,0x74B1D29A,0xEAD54739,0x9DD277AF,0x04DB2615,0x73DC1683, 0xE3630B12,0x94643B84,0x0D6D6A3E,0x7A6A5AA8,0xE40ECF0B,0x9309FF9D,0x0A00AE27,0x7D079EB1, 0xF00F9344,0x8708A3D2,0x1E01F268,0x6906C2FE,0xF762575D,0x806567CB,0x196C3671,0x6E6B06E7, 0xFED41B76,0x89D32BE0,0x10DA7A5A,0x67DD4ACC,0xF9B9DF6F,0x8EBEEFF9,0x17B7BE43,0x60B08ED5, 0xD6D6A3E8,0xA1D1937E,0x38D8C2C4,0x4FDFF252,0xD1BB67F1,0xA6BC5767,0x3FB506DD,0x48B2364B, 0xD80D2BDA,0xAF0A1B4C,0x36034AF6,0x41047A60,0xDF60EFC3,0xA867DF55,0x316E8EEF,0x4669BE79, 0xCB61B38C,0xBC66831A,0x256FD2A0,0x5268E236,0xCC0C7795,0xBB0B4703,0x220216B9,0x5505262F, 0xC5BA3BBE,0xB2BD0B28,0x2BB45A92,0x5CB36A04,0xC2D7FFA7,0xB5D0CF31,0x2CD99E8B,0x5BDEAE1D, 0x9B64C2B0,0xEC63F226,0x756AA39C,0x026D930A,0x9C0906A9,0xEB0E363F,0x72076785,0x05005713, 0x95BF4A82,0xE2B87A14,0x7BB12BAE,0x0CB61B38,0x92D28E9B,0xE5D5BE0D,0x7CDCEFB7,0x0BDBDF21, 0x86D3D2D4,0xF1D4E242,0x68DDB3F8,0x1FDA836E,0x81BE16CD,0xF6B9265B,0x6FB077E1,0x18B74777, 0x88085AE6,0xFF0F6A70,0x66063BCA,0x11010B5C,0x8F659EFF,0xF862AE69,0x616BFFD3,0x166CCF45, 0xA00AE278,0xD70DD2EE,0x4E048354,0x3903B3C2,0xA7672661,0xD06016F7,0x4969474D,0x3E6E77DB, 0xAED16A4A,0xD9D65ADC,0x40DF0B66,0x37D83BF0,0xA9BCAE53,0xDEBB9EC5,0x47B2CF7F,0x30B5FFE9, 0xBDBDF21C,0xCABAC28A,0x53B39330,0x24B4A3A6,0xBAD03605,0xCDD70693,0x54DE5729,0x23D967BF, 0xB3667A2E,0xC4614AB8,0x5D681B02,0x2A6F2B94,0xB40BBE37,0xC30C8EA1,0x5A05DF1B,0x2D02EF8D }, { 0x00000000,0x191B3141,0x32366282,0x2B2D53C3,0x646CC504,0x7D77F445,0x565AA786,0x4F4196C7, 0xC8D98A08,0xD1C2BB49,0xFAEFE88A,0xE3F4D9CB,0xACB54F0C,0xB5AE7E4D,0x9E832D8E,0x87981CCF, 0x4AC21251,0x53D92310,0x78F470D3,0x61EF4192,0x2EAED755,0x37B5E614,0x1C98B5D7,0x05838496, 0x821B9859,0x9B00A918,0xB02DFADB,0xA936CB9A,0xE6775D5D,0xFF6C6C1C,0xD4413FDF,0xCD5A0E9E, 0x958424A2,0x8C9F15E3,0xA7B24620,0xBEA97761,0xF1E8E1A6,0xE8F3D0E7,0xC3DE8324,0xDAC5B265, 0x5D5DAEAA,0x44469FEB,0x6F6BCC28,0x7670FD69,0x39316BAE,0x202A5AEF,0x0B07092C,0x121C386D, 0xDF4636F3,0xC65D07B2,0xED705471,0xF46B6530,0xBB2AF3F7,0xA231C2B6,0x891C9175,0x9007A034, 0x179FBCFB,0x0E848DBA,0x25A9DE79,0x3CB2EF38,0x73F379FF,0x6AE848BE,0x41C51B7D,0x58DE2A3C, 0xF0794F05,0xE9627E44,0xC24F2D87,0xDB541CC6,0x94158A01,0x8D0EBB40,0xA623E883,0xBF38D9C2, 0x38A0C50D,0x21BBF44C,0x0A96A78F,0x138D96CE,0x5CCC0009,0x45D73148,0x6EFA628B,0x77E153CA, 0xBABB5D54,0xA3A06C15,0x888D3FD6,0x91960E97,0xDED79850,0xC7CCA911,0xECE1FAD2,0xF5FACB93, 0x7262D75C,0x6B79E61D,0x4054B5DE,0x594F849F,0x160E1258,0x0F152319,0x243870DA,0x3D23419B, 0x65FD6BA7,0x7CE65AE6,0x57CB0925,0x4ED03864,0x0191AEA3,0x188A9FE2,0x33A7CC21,0x2ABCFD60, 0xAD24E1AF,0xB43FD0EE,0x9F12832D,0x8609B26C,0xC94824AB,0xD05315EA,0xFB7E4629,0xE2657768, 0x2F3F79F6,0x362448B7,0x1D091B74,0x04122A35,0x4B53BCF2,0x52488DB3,0x7965DE70,0x607EEF31, 0xE7E6F3FE,0xFEFDC2BF,0xD5D0917C,0xCCCBA03D,0x838A36FA,0x9A9107BB,0xB1BC5478,0xA8A76539, 0x3B83984B,0x2298A90A,0x09B5FAC9,0x10AECB88,0x5FEF5D4F,0x46F46C0E,0x6DD93FCD,0x74C20E8C, 0xF35A1243,0xEA412302,0xC16C70C1,0xD8774180,0x9736D747,0x8E2DE606,0xA500B5C5,0xBC1B8484, 0x71418A1A,0x685ABB5B,0x4377E898,0x5A6CD9D9,0x152D4F1E,0x0C367E5F,0x271B2D9C,0x3E001CDD, 0xB9980012,0xA0833153,0x8BAE6290,0x92B553D1,0xDDF4C516,0xC4EFF457,0xEFC2A794,0xF6D996D5, 0xAE07BCE9,0xB71C8DA8,0x9C31DE6B,0x852AEF2A,0xCA6B79ED,0xD37048AC,0xF85D1B6F,0xE1462A2E, 0x66DE36E1,0x7FC507A0,0x54E85463,0x4DF36522,0x02B2F3E5,0x1BA9C2A4,0x30849167,0x299FA026, 0xE4C5AEB8,0xFDDE9FF9,0xD6F3CC3A,0xCFE8FD7B,0x80A96BBC,0x99B25AFD,0xB29F093E,0xAB84387F, 0x2C1C24B0,0x350715F1,0x1E2A4632,0x07317773,0x4870E1B4,0x516BD0F5,0x7A468336,0x635DB277, 0xCBFAD74E,0xD2E1E60F,0xF9CCB5CC,0xE0D7848D,0xAF96124A,0xB68D230B,0x9DA070C8,0x84BB4189, 0x03235D46,0x1A386C07,0x31153FC4,0x280E0E85,0x674F9842,0x7E54A903,0x5579FAC0,0x4C62CB81, 0x8138C51F,0x9823F45E,0xB30EA79D,0xAA1596DC,0xE554001B,0xFC4F315A,0xD7626299,0xCE7953D8, 0x49E14F17,0x50FA7E56,0x7BD72D95,0x62CC1CD4,0x2D8D8A13,0x3496BB52,0x1FBBE891,0x06A0D9D0, 0x5E7EF3EC,0x4765C2AD,0x6C48916E,0x7553A02F,0x3A1236E8,0x230907A9,0x0824546A,0x113F652B, 0x96A779E4,0x8FBC48A5,0xA4911B66,0xBD8A2A27,0xF2CBBCE0,0xEBD08DA1,0xC0FDDE62,0xD9E6EF23, 0x14BCE1BD,0x0DA7D0FC,0x268A833F,0x3F91B27E,0x70D024B9,0x69CB15F8,0x42E6463B,0x5BFD777A, 0xDC656BB5,0xC57E5AF4,0xEE530937,0xF7483876,0xB809AEB1,0xA1129FF0,0x8A3FCC33,0x9324FD72 }, { 0x00000000,0x01C26A37,0x0384D46E,0x0246BE59,0x0709A8DC,0x06CBC2EB,0x048D7CB2,0x054F1685, 0x0E1351B8,0x0FD13B8F,0x0D9785D6,0x0C55EFE1,0x091AF964,0x08D89353,0x0A9E2D0A,0x0B5C473D, 0x1C26A370,0x1DE4C947,0x1FA2771E,0x1E601D29,0x1B2F0BAC,0x1AED619B,0x18ABDFC2,0x1969B5F5, 0x1235F2C8,0x13F798FF,0x11B126A6,0x10734C91,0x153C5A14,0x14FE3023,0x16B88E7A,0x177AE44D, 0x384D46E0,0x398F2CD7,0x3BC9928E,0x3A0BF8B9,0x3F44EE3C,0x3E86840B,0x3CC03A52,0x3D025065, 0x365E1758,0x379C7D6F,0x35DAC336,0x3418A901,0x3157BF84,0x3095D5B3,0x32D36BEA,0x331101DD, 0x246BE590,0x25A98FA7,0x27EF31FE,0x262D5BC9,0x23624D4C,0x22A0277B,0x20E69922,0x2124F315, 0x2A78B428,0x2BBADE1F,0x29FC6046,0x283E0A71,0x2D711CF4,0x2CB376C3,0x2EF5C89A,0x2F37A2AD, 0x709A8DC0,0x7158E7F7,0x731E59AE,0x72DC3399,0x7793251C,0x76514F2B,0x7417F172,0x75D59B45, 0x7E89DC78,0x7F4BB64F,0x7D0D0816,0x7CCF6221,0x798074A4,0x78421E93,0x7A04A0CA,0x7BC6CAFD, 0x6CBC2EB0,0x6D7E4487,0x6F38FADE,0x6EFA90E9,0x6BB5866C,0x6A77EC5B,0x68315202,0x69F33835, 0x62AF7F08,0x636D153F,0x612BAB66,0x60E9C151,0x65A6D7D4,0x6464BDE3,0x662203BA,0x67E0698D, 0x48D7CB20,0x4915A117,0x4B531F4E,0x4A917579,0x4FDE63FC,0x4E1C09CB,0x4C5AB792,0x4D98DDA5, 0x46C49A98,0x4706F0AF,0x45404EF6,0x448224C1,0x41CD3244,0x400F5873,0x4249E62A,0x438B8C1D, 0x54F16850,0x55330267,0x5775BC3E,0x56B7D609,0x53F8C08C,0x523AAABB,0x507C14E2,0x51BE7ED5, 0x5AE239E8,0x5B2053DF,0x5966ED86,0x58A487B1,0x5DEB9134,0x5C29FB03,0x5E6F455A,0x5FAD2F6D, 0xE1351B80,0xE0F771B7,0xE2B1CFEE,0xE373A5D9,0xE63CB35C,0xE7FED96B,0xE5B86732,0xE47A0D05, 0xEF264A38,0xEEE4200F,0xECA29E56,0xED60F461,0xE82FE2E4,0xE9ED88D3,0xEBAB368A,0xEA695CBD, 0xFD13B8F0,0xFCD1D2C7,0xFE976C9E,0xFF5506A9,0xFA1A102C,0xFBD87A1B,0xF99EC442,0xF85CAE75, 0xF300E948,0xF2C2837F,0xF0843D26,0xF1465711,0xF4094194,0xF5CB2BA3,0xF78D95FA,0xF64FFFCD, 0xD9785D60,0xD8BA3757,0xDAFC890E,0xDB3EE339,0xDE71F5BC,0xDFB39F8B,0xDDF521D2,0xDC374BE5, 0xD76B0CD8,0xD6A966EF,0xD4EFD8B6,0xD52DB281,0xD062A404,0xD1A0CE33,0xD3E6706A,0xD2241A5D, 0xC55EFE10,0xC49C9427,0xC6DA2A7E,0xC7184049,0xC25756CC,0xC3953CFB,0xC1D382A2,0xC011E895, 0xCB4DAFA8,0xCA8FC59F,0xC8C97BC6,0xC90B11F1,0xCC440774,0xCD866D43,0xCFC0D31A,0xCE02B92D, 0x91AF9640,0x906DFC77,0x922B422E,0x93E92819,0x96A63E9C,0x976454AB,0x9522EAF2,0x94E080C5, 0x9FBCC7F8,0x9E7EADCF,0x9C381396,0x9DFA79A1,0x98B56F24,0x99770513,0x9B31BB4A,0x9AF3D17D, 0x8D893530,0x8C4B5F07,0x8E0DE15E,0x8FCF8B69,0x8A809DEC,0x8B42F7DB,0x89044982,0x88C623B5, 0x839A6488,0x82580EBF,0x801EB0E6,0x81DCDAD1,0x8493CC54,0x8551A663,0x8717183A,0x86D5720D, 0xA9E2D0A0,0xA820BA97,0xAA6604CE,0xABA46EF9,0xAEEB787C,0xAF29124B,0xAD6FAC12,0xACADC625, 0xA7F18118,0xA633EB2F,0xA4755576,0xA5B73F41,0xA0F829C4,0xA13A43F3,0xA37CFDAA,0xA2BE979D, 0xB5C473D0,0xB40619E7,0xB640A7BE,0xB782CD89,0xB2CDDB0C,0xB30FB13B,0xB1490F62,0xB08B6555, 0xBBD72268,0xBA15485F,0xB853F606,0xB9919C31,0xBCDE8AB4,0xBD1CE083,0xBF5A5EDA,0xBE9834ED }, { 0x00000000,0xB8BC6765,0xAA09C88B,0x12B5AFEE,0x8F629757,0x37DEF032,0x256B5FDC,0x9DD738B9, 0xC5B428EF,0x7D084F8A,0x6FBDE064,0xD7018701,0x4AD6BFB8,0xF26AD8DD,0xE0DF7733,0x58631056, 0x5019579F,0xE8A530FA,0xFA109F14,0x42ACF871,0xDF7BC0C8,0x67C7A7AD,0x75720843,0xCDCE6F26, 0x95AD7F70,0x2D111815,0x3FA4B7FB,0x8718D09E,0x1ACFE827,0xA2738F42,0xB0C620AC,0x087A47C9, 0xA032AF3E,0x188EC85B,0x0A3B67B5,0xB28700D0,0x2F503869,0x97EC5F0C,0x8559F0E2,0x3DE59787, 0x658687D1,0xDD3AE0B4,0xCF8F4F5A,0x7733283F,0xEAE41086,0x525877E3,0x40EDD80D,0xF851BF68, 0xF02BF8A1,0x48979FC4,0x5A22302A,0xE29E574F,0x7F496FF6,0xC7F50893,0xD540A77D,0x6DFCC018, 0x359FD04E,0x8D23B72B,0x9F9618C5,0x272A7FA0,0xBAFD4719,0x0241207C,0x10F48F92,0xA848E8F7, 0x9B14583D,0x23A83F58,0x311D90B6,0x89A1F7D3,0x1476CF6A,0xACCAA80F,0xBE7F07E1,0x06C36084, 0x5EA070D2,0xE61C17B7,0xF4A9B859,0x4C15DF3C,0xD1C2E785,0x697E80E0,0x7BCB2F0E,0xC377486B, 0xCB0D0FA2,0x73B168C7,0x6104C729,0xD9B8A04C,0x446F98F5,0xFCD3FF90,0xEE66507E,0x56DA371B, 0x0EB9274D,0xB6054028,0xA4B0EFC6,0x1C0C88A3,0x81DBB01A,0x3967D77F,0x2BD27891,0x936E1FF4, 0x3B26F703,0x839A9066,0x912F3F88,0x299358ED,0xB4446054,0x0CF80731,0x1E4DA8DF,0xA6F1CFBA, 0xFE92DFEC,0x462EB889,0x549B1767,0xEC277002,0x71F048BB,0xC94C2FDE,0xDBF98030,0x6345E755, 0x6B3FA09C,0xD383C7F9,0xC1366817,0x798A0F72,0xE45D37CB,0x5CE150AE,0x4E54FF40,0xF6E89825, 0xAE8B8873,0x1637EF16,0x048240F8,0xBC3E279D,0x21E91F24,0x99557841,0x8BE0D7AF,0x335CB0CA, 0xED59B63B,0x55E5D15E,0x47507EB0,0xFFEC19D5,0x623B216C,0xDA874609,0xC832E9E7,0x708E8E82, 0x28ED9ED4,0x9051F9B1,0x82E4565F,0x3A58313A,0xA78F0983,0x1F336EE6,0x0D86C108,0xB53AA66D, 0xBD40E1A4,0x05FC86C1,0x1749292F,0xAFF54E4A,0x322276F3,0x8A9E1196,0x982BBE78,0x2097D91D, 0x78F4C94B,0xC048AE2E,0xD2FD01C0,0x6A4166A5,0xF7965E1C,0x4F2A3979,0x5D9F9697,0xE523F1F2, 0x4D6B1905,0xF5D77E60,0xE762D18E,0x5FDEB6EB,0xC2098E52,0x7AB5E937,0x680046D9,0xD0BC21BC, 0x88DF31EA,0x3063568F,0x22D6F961,0x9A6A9E04,0x07BDA6BD,0xBF01C1D8,0xADB46E36,0x15080953, 0x1D724E9A,0xA5CE29FF,0xB77B8611,0x0FC7E174,0x9210D9CD,0x2AACBEA8,0x38191146,0x80A57623, 0xD8C66675,0x607A0110,0x72CFAEFE,0xCA73C99B,0x57A4F122,0xEF189647,0xFDAD39A9,0x45115ECC, 0x764DEE06,0xCEF18963,0xDC44268D,0x64F841E8,0xF92F7951,0x41931E34,0x5326B1DA,0xEB9AD6BF, 0xB3F9C6E9,0x0B45A18C,0x19F00E62,0xA14C6907,0x3C9B51BE,0x842736DB,0x96929935,0x2E2EFE50, 0x2654B999,0x9EE8DEFC,0x8C5D7112,0x34E11677,0xA9362ECE,0x118A49AB,0x033FE645,0xBB838120, 0xE3E09176,0x5B5CF613,0x49E959FD,0xF1553E98,0x6C820621,0xD43E6144,0xC68BCEAA,0x7E37A9CF, 0xD67F4138,0x6EC3265D,0x7C7689B3,0xC4CAEED6,0x591DD66F,0xE1A1B10A,0xF3141EE4,0x4BA87981, 0x13CB69D7,0xAB770EB2,0xB9C2A15C,0x017EC639,0x9CA9FE80,0x241599E5,0x36A0360B,0x8E1C516E, 0x866616A7,0x3EDA71C2,0x2C6FDE2C,0x94D3B949,0x090481F0,0xB1B8E695,0xA30D497B,0x1BB12E1E, 0x43D23E48,0xFB6E592D,0xE9DBF6C3,0x516791A6,0xCCB0A91F,0x740CCE7A,0x66B96194,0xDE0506F1 }, { 0x00000000,0x3D6029B0,0x7AC05360,0x47A07AD0,0xF580A6C0,0xC8E08F70,0x8F40F5A0,0xB220DC10, 0x30704BC1,0x0D106271,0x4AB018A1,0x77D03111,0xC5F0ED01,0xF890C4B1,0xBF30BE61,0x825097D1, 0x60E09782,0x5D80BE32,0x1A20C4E2,0x2740ED52,0x95603142,0xA80018F2,0xEFA06222,0xD2C04B92, 0x5090DC43,0x6DF0F5F3,0x2A508F23,0x1730A693,0xA5107A83,0x98705333,0xDFD029E3,0xE2B00053, 0xC1C12F04,0xFCA106B4,0xBB017C64,0x866155D4,0x344189C4,0x0921A074,0x4E81DAA4,0x73E1F314, 0xF1B164C5,0xCCD14D75,0x8B7137A5,0xB6111E15,0x0431C205,0x3951EBB5,0x7EF19165,0x4391B8D5, 0xA121B886,0x9C419136,0xDBE1EBE6,0xE681C256,0x54A11E46,0x69C137F6,0x2E614D26,0x13016496, 0x9151F347,0xAC31DAF7,0xEB91A027,0xD6F18997,0x64D15587,0x59B17C37,0x1E1106E7,0x23712F57, 0x58F35849,0x659371F9,0x22330B29,0x1F532299,0xAD73FE89,0x9013D739,0xD7B3ADE9,0xEAD38459, 0x68831388,0x55E33A38,0x124340E8,0x2F236958,0x9D03B548,0xA0639CF8,0xE7C3E628,0xDAA3CF98, 0x3813CFCB,0x0573E67B,0x42D39CAB,0x7FB3B51B,0xCD93690B,0xF0F340BB,0xB7533A6B,0x8A3313DB, 0x0863840A,0x3503ADBA,0x72A3D76A,0x4FC3FEDA,0xFDE322CA,0xC0830B7A,0x872371AA,0xBA43581A, 0x9932774D,0xA4525EFD,0xE3F2242D,0xDE920D9D,0x6CB2D18D,0x51D2F83D,0x167282ED,0x2B12AB5D, 0xA9423C8C,0x9422153C,0xD3826FEC,0xEEE2465C,0x5CC29A4C,0x61A2B3FC,0x2602C92C,0x1B62E09C, 0xF9D2E0CF,0xC4B2C97F,0x8312B3AF,0xBE729A1F,0x0C52460F,0x31326FBF,0x7692156F,0x4BF23CDF, 0xC9A2AB0E,0xF4C282BE,0xB362F86E,0x8E02D1DE,0x3C220DCE,0x0142247E,0x46E25EAE,0x7B82771E, 0xB1E6B092,0x8C869922,0xCB26E3F2,0xF646CA42,0x44661652,0x79063FE2,0x3EA64532,0x03C66C82, 0x8196FB53,0xBCF6D2E3,0xFB56A833,0xC6368183,0x74165D93,0x49767423,0x0ED60EF3,0x33B62743, 0xD1062710,0xEC660EA0,0xABC67470,0x96A65DC0,0x248681D0,0x19E6A860,0x5E46D2B0,0x6326FB00, 0xE1766CD1,0xDC164561,0x9BB63FB1,0xA6D61601,0x14F6CA11,0x2996E3A1,0x6E369971,0x5356B0C1, 0x70279F96,0x4D47B626,0x0AE7CCF6,0x3787E546,0x85A73956,0xB8C710E6,0xFF676A36,0xC2074386, 0x4057D457,0x7D37FDE7,0x3A978737,0x07F7AE87,0xB5D77297,0x88B75B27,0xCF1721F7,0xF2770847, 0x10C70814,0x2DA721A4,0x6A075B74,0x576772C4,0xE547AED4,0xD8278764,0x9F87FDB4,0xA2E7D404, 0x20B743D5,0x1DD76A65,0x5A7710B5,0x67173905,0xD537E515,0xE857CCA5,0xAFF7B675,0x92979FC5, 0xE915E8DB,0xD475C16B,0x93D5BBBB,0xAEB5920B,0x1C954E1B,0x21F567AB,0x66551D7B,0x5B3534CB, 0xD965A31A,0xE4058AAA,0xA3A5F07A,0x9EC5D9CA,0x2CE505DA,0x11852C6A,0x562556BA,0x6B457F0A, 0x89F57F59,0xB49556E9,0xF3352C39,0xCE550589,0x7C75D999,0x4115F029,0x06B58AF9,0x3BD5A349, 0xB9853498,0x84E51D28,0xC34567F8,0xFE254E48,0x4C059258,0x7165BBE8,0x36C5C138,0x0BA5E888, 0x28D4C7DF,0x15B4EE6F,0x521494BF,0x6F74BD0F,0xDD54611F,0xE03448AF,0xA794327F,0x9AF41BCF, 0x18A48C1E,0x25C4A5AE,0x6264DF7E,0x5F04F6CE,0xED242ADE,0xD044036E,0x97E479BE,0xAA84500E, 0x4834505D,0x755479ED,0x32F4033D,0x0F942A8D,0xBDB4F69D,0x80D4DF2D,0xC774A5FD,0xFA148C4D, 0x78441B9C,0x4524322C,0x028448FC,0x3FE4614C,0x8DC4BD5C,0xB0A494EC,0xF704EE3C,0xCA64C78C }, { 0x00000000,0xCB5CD3A5,0x4DC8A10B,0x869472AE,0x9B914216,0x50CD91B3,0xD659E31D,0x1D0530B8, 0xEC53826D,0x270F51C8,0xA19B2366,0x6AC7F0C3,0x77C2C07B,0xBC9E13DE,0x3A0A6170,0xF156B2D5, 0x03D6029B,0xC88AD13E,0x4E1EA390,0x85427035,0x9847408D,0x531B9328,0xD58FE186,0x1ED33223, 0xEF8580F6,0x24D95353,0xA24D21FD,0x6911F258,0x7414C2E0,0xBF481145,0x39DC63EB,0xF280B04E, 0x07AC0536,0xCCF0D693,0x4A64A43D,0x81387798,0x9C3D4720,0x57619485,0xD1F5E62B,0x1AA9358E, 0xEBFF875B,0x20A354FE,0xA6372650,0x6D6BF5F5,0x706EC54D,0xBB3216E8,0x3DA66446,0xF6FAB7E3, 0x047A07AD,0xCF26D408,0x49B2A6A6,0x82EE7503,0x9FEB45BB,0x54B7961E,0xD223E4B0,0x197F3715, 0xE82985C0,0x23755665,0xA5E124CB,0x6EBDF76E,0x73B8C7D6,0xB8E41473,0x3E7066DD,0xF52CB578, 0x0F580A6C,0xC404D9C9,0x4290AB67,0x89CC78C2,0x94C9487A,0x5F959BDF,0xD901E971,0x125D3AD4, 0xE30B8801,0x28575BA4,0xAEC3290A,0x659FFAAF,0x789ACA17,0xB3C619B2,0x35526B1C,0xFE0EB8B9, 0x0C8E08F7,0xC7D2DB52,0x4146A9FC,0x8A1A7A59,0x971F4AE1,0x5C439944,0xDAD7EBEA,0x118B384F, 0xE0DD8A9A,0x2B81593F,0xAD152B91,0x6649F834,0x7B4CC88C,0xB0101B29,0x36846987,0xFDD8BA22, 0x08F40F5A,0xC3A8DCFF,0x453CAE51,0x8E607DF4,0x93654D4C,0x58399EE9,0xDEADEC47,0x15F13FE2, 0xE4A78D37,0x2FFB5E92,0xA96F2C3C,0x6233FF99,0x7F36CF21,0xB46A1C84,0x32FE6E2A,0xF9A2BD8F, 0x0B220DC1,0xC07EDE64,0x46EAACCA,0x8DB67F6F,0x90B34FD7,0x5BEF9C72,0xDD7BEEDC,0x16273D79, 0xE7718FAC,0x2C2D5C09,0xAAB92EA7,0x61E5FD02,0x7CE0CDBA,0xB7BC1E1F,0x31286CB1,0xFA74BF14, 0x1EB014D8,0xD5ECC77D,0x5378B5D3,0x98246676,0x852156CE,0x4E7D856B,0xC8E9F7C5,0x03B52460, 0xF2E396B5,0x39BF4510,0xBF2B37BE,0x7477E41B,0x6972D4A3,0xA22E0706,0x24BA75A8,0xEFE6A60D, 0x1D661643,0xD63AC5E6,0x50AEB748,0x9BF264ED,0x86F75455,0x4DAB87F0,0xCB3FF55E,0x006326FB, 0xF135942E,0x3A69478B,0xBCFD3525,0x77A1E680,0x6AA4D638,0xA1F8059D,0x276C7733,0xEC30A496, 0x191C11EE,0xD240C24B,0x54D4B0E5,0x9F886340,0x828D53F8,0x49D1805D,0xCF45F2F3,0x04192156, 0xF54F9383,0x3E134026,0xB8873288,0x73DBE12D,0x6EDED195,0xA5820230,0x2316709E,0xE84AA33B, 0x1ACA1375,0xD196C0D0,0x5702B27E,0x9C5E61DB,0x815B5163,0x4A0782C6,0xCC93F068,0x07CF23CD, 0xF6999118,0x3DC542BD,0xBB513013,0x700DE3B6,0x6D08D30E,0xA65400AB,0x20C07205,0xEB9CA1A0, 0x11E81EB4,0xDAB4CD11,0x5C20BFBF,0x977C6C1A,0x8A795CA2,0x41258F07,0xC7B1FDA9,0x0CED2E0C, 0xFDBB9CD9,0x36E74F7C,0xB0733DD2,0x7B2FEE77,0x662ADECF,0xAD760D6A,0x2BE27FC4,0xE0BEAC61, 0x123E1C2F,0xD962CF8A,0x5FF6BD24,0x94AA6E81,0x89AF5E39,0x42F38D9C,0xC467FF32,0x0F3B2C97, 0xFE6D9E42,0x35314DE7,0xB3A53F49,0x78F9ECEC,0x65FCDC54,0xAEA00FF1,0x28347D5F,0xE368AEFA, 0x16441B82,0xDD18C827,0x5B8CBA89,0x90D0692C,0x8DD55994,0x46898A31,0xC01DF89F,0x0B412B3A, 0xFA1799EF,0x314B4A4A,0xB7DF38E4,0x7C83EB41,0x6186DBF9,0xAADA085C,0x2C4E7AF2,0xE712A957, 0x15921919,0xDECECABC,0x585AB812,0x93066BB7,0x8E035B0F,0x455F88AA,0xC3CBFA04,0x089729A1, 0xF9C19B74,0x329D48D1,0xB4093A7F,0x7F55E9DA,0x6250D962,0xA90C0AC7,0x2F987869,0xE4C4ABCC }, { 0x00000000,0xA6770BB4,0x979F1129,0x31E81A9D,0xF44F2413,0x52382FA7,0x63D0353A,0xC5A73E8E, 0x33EF4E67,0x959845D3,0xA4705F4E,0x020754FA,0xC7A06A74,0x61D761C0,0x503F7B5D,0xF64870E9, 0x67DE9CCE,0xC1A9977A,0xF0418DE7,0x56368653,0x9391B8DD,0x35E6B369,0x040EA9F4,0xA279A240, 0x5431D2A9,0xF246D91D,0xC3AEC380,0x65D9C834,0xA07EF6BA,0x0609FD0E,0x37E1E793,0x9196EC27, 0xCFBD399C,0x69CA3228,0x582228B5,0xFE552301,0x3BF21D8F,0x9D85163B,0xAC6D0CA6,0x0A1A0712, 0xFC5277FB,0x5A257C4F,0x6BCD66D2,0xCDBA6D66,0x081D53E8,0xAE6A585C,0x9F8242C1,0x39F54975, 0xA863A552,0x0E14AEE6,0x3FFCB47B,0x998BBFCF,0x5C2C8141,0xFA5B8AF5,0xCBB39068,0x6DC49BDC, 0x9B8CEB35,0x3DFBE081,0x0C13FA1C,0xAA64F1A8,0x6FC3CF26,0xC9B4C492,0xF85CDE0F,0x5E2BD5BB, 0x440B7579,0xE27C7ECD,0xD3946450,0x75E36FE4,0xB044516A,0x16335ADE,0x27DB4043,0x81AC4BF7, 0x77E43B1E,0xD19330AA,0xE07B2A37,0x460C2183,0x83AB1F0D,0x25DC14B9,0x14340E24,0xB2430590, 0x23D5E9B7,0x85A2E203,0xB44AF89E,0x123DF32A,0xD79ACDA4,0x71EDC610,0x4005DC8D,0xE672D739, 0x103AA7D0,0xB64DAC64,0x87A5B6F9,0x21D2BD4D,0xE47583C3,0x42028877,0x73EA92EA,0xD59D995E, 0x8BB64CE5,0x2DC14751,0x1C295DCC,0xBA5E5678,0x7FF968F6,0xD98E6342,0xE86679DF,0x4E11726B, 0xB8590282,0x1E2E0936,0x2FC613AB,0x89B1181F,0x4C162691,0xEA612D25,0xDB8937B8,0x7DFE3C0C, 0xEC68D02B,0x4A1FDB9F,0x7BF7C102,0xDD80CAB6,0x1827F438,0xBE50FF8C,0x8FB8E511,0x29CFEEA5, 0xDF879E4C,0x79F095F8,0x48188F65,0xEE6F84D1,0x2BC8BA5F,0x8DBFB1EB,0xBC57AB76,0x1A20A0C2, 0x8816EAF2,0x2E61E146,0x1F89FBDB,0xB9FEF06F,0x7C59CEE1,0xDA2EC555,0xEBC6DFC8,0x4DB1D47C, 0xBBF9A495,0x1D8EAF21,0x2C66B5BC,0x8A11BE08,0x4FB68086,0xE9C18B32,0xD82991AF,0x7E5E9A1B, 0xEFC8763C,0x49BF7D88,0x78576715,0xDE206CA1,0x1B87522F,0xBDF0599B,0x8C184306,0x2A6F48B2, 0xDC27385B,0x7A5033EF,0x4BB82972,0xEDCF22C6,0x28681C48,0x8E1F17FC,0xBFF70D61,0x198006D5, 0x47ABD36E,0xE1DCD8DA,0xD034C247,0x7643C9F3,0xB3E4F77D,0x1593FCC9,0x247BE654,0x820CEDE0, 0x74449D09,0xD23396BD,0xE3DB8C20,0x45AC8794,0x800BB91A,0x267CB2AE,0x1794A833,0xB1E3A387, 0x20754FA0,0x86024414,0xB7EA5E89,0x119D553D,0xD43A6BB3,0x724D6007,0x43A57A9A,0xE5D2712E, 0x139A01C7,0xB5ED0A73,0x840510EE,0x22721B5A,0xE7D525D4,0x41A22E60,0x704A34FD,0xD63D3F49, 0xCC1D9F8B,0x6A6A943F,0x5B828EA2,0xFDF58516,0x3852BB98,0x9E25B02C,0xAFCDAAB1,0x09BAA105, 0xFFF2D1EC,0x5985DA58,0x686DC0C5,0xCE1ACB71,0x0BBDF5FF,0xADCAFE4B,0x9C22E4D6,0x3A55EF62, 0xABC30345,0x0DB408F1,0x3C5C126C,0x9A2B19D8,0x5F8C2756,0xF9FB2CE2,0xC813367F,0x6E643DCB, 0x982C4D22,0x3E5B4696,0x0FB35C0B,0xA9C457BF,0x6C636931,0xCA146285,0xFBFC7818,0x5D8B73AC, 0x03A0A617,0xA5D7ADA3,0x943FB73E,0x3248BC8A,0xF7EF8204,0x519889B0,0x6070932D,0xC6079899, 0x304FE870,0x9638E3C4,0xA7D0F959,0x01A7F2ED,0xC400CC63,0x6277C7D7,0x539FDD4A,0xF5E8D6FE, 0x647E3AD9,0xC209316D,0xF3E12BF0,0x55962044,0x90311ECA,0x3646157E,0x07AE0FE3,0xA1D90457, 0x579174BE,0xF1E67F0A,0xC00E6597,0x66796E23,0xA3DE50AD,0x05A95B19,0x34414184,0x92364A30 }, { 0x00000000,0xCCAA009E,0x4225077D,0x8E8F07E3,0x844A0EFA,0x48E00E64,0xC66F0987,0x0AC50919, 0xD3E51BB5,0x1F4F1B2B,0x91C01CC8,0x5D6A1C56,0x57AF154F,0x9B0515D1,0x158A1232,0xD92012AC, 0x7CBB312B,0xB01131B5,0x3E9E3656,0xF23436C8,0xF8F13FD1,0x345B3F4F,0xBAD438AC,0x767E3832, 0xAF5E2A9E,0x63F42A00,0xED7B2DE3,0x21D12D7D,0x2B142464,0xE7BE24FA,0x69312319,0xA59B2387, 0xF9766256,0x35DC62C8,0xBB53652B,0x77F965B5,0x7D3C6CAC,0xB1966C32,0x3F196BD1,0xF3B36B4F, 0x2A9379E3,0xE639797D,0x68B67E9E,0xA41C7E00,0xAED97719,0x62737787,0xECFC7064,0x205670FA, 0x85CD537D,0x496753E3,0xC7E85400,0x0B42549E,0x01875D87,0xCD2D5D19,0x43A25AFA,0x8F085A64, 0x562848C8,0x9A824856,0x140D4FB5,0xD8A74F2B,0xD2624632,0x1EC846AC,0x9047414F,0x5CED41D1, 0x299DC2ED,0xE537C273,0x6BB8C590,0xA712C50E,0xADD7CC17,0x617DCC89,0xEFF2CB6A,0x2358CBF4, 0xFA78D958,0x36D2D9C6,0xB85DDE25,0x74F7DEBB,0x7E32D7A2,0xB298D73C,0x3C17D0DF,0xF0BDD041, 0x5526F3C6,0x998CF358,0x1703F4BB,0xDBA9F425,0xD16CFD3C,0x1DC6FDA2,0x9349FA41,0x5FE3FADF, 0x86C3E873,0x4A69E8ED,0xC4E6EF0E,0x084CEF90,0x0289E689,0xCE23E617,0x40ACE1F4,0x8C06E16A, 0xD0EBA0BB,0x1C41A025,0x92CEA7C6,0x5E64A758,0x54A1AE41,0x980BAEDF,0x1684A93C,0xDA2EA9A2, 0x030EBB0E,0xCFA4BB90,0x412BBC73,0x8D81BCED,0x8744B5F4,0x4BEEB56A,0xC561B289,0x09CBB217, 0xAC509190,0x60FA910E,0xEE7596ED,0x22DF9673,0x281A9F6A,0xE4B09FF4,0x6A3F9817,0xA6959889, 0x7FB58A25,0xB31F8ABB,0x3D908D58,0xF13A8DC6,0xFBFF84DF,0x37558441,0xB9DA83A2,0x7570833C, 0x533B85DA,0x9F918544,0x111E82A7,0xDDB48239,0xD7718B20,0x1BDB8BBE,0x95548C5D,0x59FE8CC3, 0x80DE9E6F,0x4C749EF1,0xC2FB9912,0x0E51998C,0x04949095,0xC83E900B,0x46B197E8,0x8A1B9776, 0x2F80B4F1,0xE32AB46F,0x6DA5B38C,0xA10FB312,0xABCABA0B,0x6760BA95,0xE9EFBD76,0x2545BDE8, 0xFC65AF44,0x30CFAFDA,0xBE40A839,0x72EAA8A7,0x782FA1BE,0xB485A120,0x3A0AA6C3,0xF6A0A65D, 0xAA4DE78C,0x66E7E712,0xE868E0F1,0x24C2E06F,0x2E07E976,0xE2ADE9E8,0x6C22EE0B,0xA088EE95, 0x79A8FC39,0xB502FCA7,0x3B8DFB44,0xF727FBDA,0xFDE2F2C3,0x3148F25D,0xBFC7F5BE,0x736DF520, 0xD6F6D6A7,0x1A5CD639,0x94D3D1DA,0x5879D144,0x52BCD85D,0x9E16D8C3,0x1099DF20,0xDC33DFBE, 0x0513CD12,0xC9B9CD8C,0x4736CA6F,0x8B9CCAF1,0x8159C3E8,0x4DF3C376,0xC37CC495,0x0FD6C40B, 0x7AA64737,0xB60C47A9,0x3883404A,0xF42940D4,0xFEEC49CD,0x32464953,0xBCC94EB0,0x70634E2E, 0xA9435C82,0x65E95C1C,0xEB665BFF,0x27CC5B61,0x2D095278,0xE1A352E6,0x6F2C5505,0xA386559B, 0x061D761C,0xCAB77682,0x44387161,0x889271FF,0x825778E6,0x4EFD7878,0xC0727F9B,0x0CD87F05, 0xD5F86DA9,0x19526D37,0x97DD6AD4,0x5B776A4A,0x51B26353,0x9D1863CD,0x1397642E,0xDF3D64B0, 0x83D02561,0x4F7A25FF,0xC1F5221C,0x0D5F2282,0x079A2B9B,0xCB302B05,0x45BF2CE6,0x89152C78, 0x50353ED4,0x9C9F3E4A,0x121039A9,0xDEBA3937,0xD47F302E,0x18D530B0,0x965A3753,0x5AF037CD, 0xFF6B144A,0x33C114D4,0xBD4E1337,0x71E413A9,0x7B211AB0,0xB78B1A2E,0x39041DCD,0xF5AE1D53, 0x2C8E0FFF,0xE0240F61,0x6EAB0882,0xA201081C,0xA8C40105,0x646E019B,0xEAE10678,0x264B06E6 } }; /// compute CRC32 based on polynom 0xEDB88320L (zlib's) unsigned int crc32(const void* data, size_t length, unsigned int previousCrc32) { const unsigned int* current = (unsigned int* ) data; unsigned int crc = ~previousCrc32; // same as previousCrc32 ^ 0xFFFFFFFF // process eight bytes at once while (length >= 8 )/*4*/ { unsigned int one = *current++ ^ crc; unsigned int two = *current++; crc = crc32Lookup[7][ one & 0xFF] ^ crc32Lookup[6][(one>> 8) & 0xFF] ^ crc32Lookup[5][(one>>16) & 0xFF] ^ crc32Lookup[4][ one>>24 ] ^ crc32Lookup[3][ two & 0xFF] ^ crc32Lookup[2][(two>> 8) & 0xFF] ^ crc32Lookup[1][(two>>16) & 0xFF] ^ crc32Lookup[0][ two>>24 ]; length -= 8; } const unsigned char* currentChar = (unsigned char*) current; // remaining 1 to 7 bytes (standard CRC table-based algorithm) while (length--) crc = (crc >> 8) ^ crc32Lookup[0][(crc & 0xFF) ^ *currentChar++]; return ~crc; // same as crc ^ 0xFFFFFFFF } } namespace Bits { /// reverse bit order unsigned int reverse(unsigned int x, size_t numBits) { static const unsigned char reverse8[256] = { 0x00,0x80,0x40,0xC0, 0x20,0xA0,0x60,0xE0, 0x10,0x90,0x50,0xD0, 0x30,0xB0,0x70,0xF0, 0x08,0x88,0x48,0xC8, 0x28,0xA8,0x68,0xE8, 0x18,0x98,0x58,0xD8, 0x38,0xB8,0x78,0xF8, 0x04,0x84,0x44,0xC4, 0x24,0xA4,0x64,0xE4, 0x14,0x94,0x54,0xD4, 0x34,0xB4,0x74,0xF4, 0x0C,0x8C,0x4C,0xCC, 0x2C,0xAC,0x6C,0xEC, 0x1C,0x9C,0x5C,0xDC, 0x3C,0xBC,0x7C,0xFC, 0x02,0x82,0x42,0xC2, 0x22,0xA2,0x62,0xE2, 0x12,0x92,0x52,0xD2, 0x32,0xB2,0x72,0xF2, 0x0A,0x8A,0x4A,0xCA, 0x2A,0xAA,0x6A,0xEA, 0x1A,0x9A,0x5A,0xDA, 0x3A,0xBA,0x7A,0xFA, 0x06,0x86,0x46,0xC6, 0x26,0xA6,0x66,0xE6, 0x16,0x96,0x56,0xD6, 0x36,0xB6,0x76,0xF6, 0x0E,0x8E,0x4E,0xCE, 0x2E,0xAE,0x6E,0xEE, 0x1E,0x9E,0x5E,0xDE, 0x3E,0xBE,0x7E,0xFE, 0x01,0x81,0x41,0xC1, 0x21,0xA1,0x61,0xE1, 0x11,0x91,0x51,0xD1, 0x31,0xB1,0x71,0xF1, 0x09,0x89,0x49,0xC9, 0x29,0xA9,0x69,0xE9, 0x19,0x99,0x59,0xD9, 0x39,0xB9,0x79,0xF9, 0x05,0x85,0x45,0xC5, 0x25,0xA5,0x65,0xE5, 0x15,0x95,0x55,0xD5, 0x35,0xB5,0x75,0xF5, 0x0D,0x8D,0x4D,0xCD, 0x2D,0xAD,0x6D,0xED, 0x1D,0x9D,0x5D,0xDD, 0x3D,0xBD,0x7D,0xFD, 0x03,0x83,0x43,0xC3, 0x23,0xA3,0x63,0xE3, 0x13,0x93,0x53,0xD3, 0x33,0xB3,0x73,0xF3, 0x0B,0x8B,0x4B,0xCB, 0x2B,0xAB,0x6B,0xEB, 0x1B,0x9B,0x5B,0xDB, 0x3B,0xBB,0x7B,0xFB, 0x07,0x87,0x47,0xC7, 0x27,0xA7,0x67,0xE7, 0x17,0x97,0x57,0xD7, 0x37,0xB7,0x77,0xF7, 0x0F,0x8F,0x4F,0xCF, 0x2F,0xAF,0x6F,0xEF, 0x1F,0x9F,0x5F,0xDF, 0x3F,0xBF,0x7F,0xFF }; assert(x < (unsigned int)(1 << numBits)); // fast lookup if it fits in a byte if (numBits == 8) return reverse8[(unsigned char)x]; if (numBits < 8) return reverse8[(unsigned char)x] >> (8 - numBits); // more than a byte, slower unsigned int result = 0; for (size_t i = 0; i < numBits; i++) { result <<= 1; result |= x & 1; x >>= 1; } return result; } }

What About DEFLATE Compression ?

The much more interesting part of the DEFLATE algorithm is compressing, not decompressing data. At the moment I'm working on an encoder with emphasis on compression ratio (speed might suffer). Stay tuned !
homepage