1 /////////////////////////////////////////////////////////////////////////// 2 // 3 // Copyright (c) 2009-2014 DreamWorks Animation LLC. 4 // 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are 9 // met: 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above 13 // copyright notice, this list of conditions and the following disclaimer 14 // in the documentation and/or other materials provided with the 15 // distribution. 16 // * Neither the name of DreamWorks Animation nor the names of 17 // its contributors may be used to endorse or promote products derived 18 // from this software without specific prior written permission. 19 // 20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 // 32 /////////////////////////////////////////////////////////////////////////// 33 34 #ifndef INCLUDED_IMF_FAST_HUF_H 35 #define INCLUDED_IMF_FAST_HUF_H 36 37 #include "ImfInt64.h" 38 #include "ImfNamespace.h" 39 40 OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_ENTER 41 42 // 43 // Alternative Canonical Huffman decoder: 44 // 45 // Canonical Huffman decoder based on 'On the Implementation of Minimum 46 // Redundancy Prefix Codes' by Moffat and Turpin - highly recommended 47 // reading as a good description of the problem space, as well as 48 // a fast decoding algorithm. 49 // 50 // The premise is that instead of working directly with the coded 51 // symbols, we create a new ordering based on the frequency of symbols. 52 // Less frequent symbols (and thus longer codes) are ordered earler. 53 // We're calling the values in this ordering 'Ids', as oppsed to 54 // 'Symbols' - which are the short values we eventually want decoded. 55 // 56 // With this new ordering, a few small tables can be derived ('base' 57 // and 'offset') which drive the decoding. To cut down on the 58 // linear scanning of these tables, you can add a small table 59 // to directly look up short codes (as you might in a traditional 60 // lookup-table driven decoder). 61 // 62 // The decoder is meant to be compatible with the encoder (and decoder) 63 // in ImfHuf.cpp, just faster. For ease of implementation, this decoder 64 // should only be used on compressed bitstreams >= 128 bits long. 65 // 66 67 class FastHufDecoder 68 { 69 public: 70 71 // 72 // Longest compressed code length that ImfHuf supports (58 bits) 73 // 74 75 static const int MAX_CODE_LEN = 58; 76 77 // 78 // Number of bits in our acceleration table. Should match all 79 // codes up to TABLE_LOOKUP_BITS in length. 80 // 81 82 static const int TABLE_LOOKUP_BITS = 12; 83 84 FastHufDecoder (const char*& table, 85 int numBytes, 86 int minSymbol, 87 int maxSymbol, 88 int rleSymbol); 89 90 ~FastHufDecoder (); 91 92 static bool enabled (); 93 94 void decode (const unsigned char *src, 95 int numSrcBits, 96 unsigned short *dst, 97 int numDstElems); 98 99 private: 100 101 void buildTables (Int64*, Int64*); 102 void refill (Int64&, int, Int64&, int&, const unsigned char *&, int&); 103 Int64 readBits (int, Int64&, int&, const char *&); 104 105 int _rleSymbol; // RLE symbol written by the encoder. 106 // This could be 65536, so beware 107 // when you use shorts to hold things. 108 109 int _numSymbols; // Number of symbols in the codebook. 110 111 unsigned char _minCodeLength; // Minimum code length, in bits. 112 unsigned char _maxCodeLength; // Maximum code length, in bits. 113 114 int *_idToSymbol; // Maps Ids to symbols. Ids are a symbol 115 // ordering sorted first in terms of 116 // code length, and by code within 117 // the same length. Ids run from 0 118 // to mNumSymbols-1. 119 120 Int64 _ljBase[MAX_CODE_LEN + 1]; // the 'left justified base' table. 121 // Takes base[i] (i = code length) 122 // and 'left justifies' it into an Int64 123 124 Int64 _ljOffset[MAX_CODE_LEN +1 ]; // There are some other terms that can 125 // be folded into constants when taking 126 // the 'left justified' decode path. This 127 // holds those constants, indexed by 128 // code length 129 130 // 131 // We can accelerate the 'left justified' processing by running the 132 // top TABLE_LOOKUP_BITS through a LUT, to find the symbol and code 133 // length. These are those acceleration tables. 134 // 135 // Even though our evental 'symbols' are ushort's, the encoder adds 136 // a symbol to indicate RLE. So with a dense code book, we could 137 // have 2^16+1 codes, so both mIdToSymbol and mTableSymbol need 138 // to be bigger than 16 bits. 139 // 140 141 int _tableSymbol[1 << TABLE_LOOKUP_BITS]; 142 unsigned char _tableCodeLen[1 << TABLE_LOOKUP_BITS]; 143 Int64 _tableMin; 144 }; 145 146 OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_EXIT 147 148 #endif 149