|
Packit |
0d464f |
///////////////////////////////////////////////////////////////////////////
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Copyright (c) 2009-2014 DreamWorks Animation LLC.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// All rights reserved.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Redistribution and use in source and binary forms, with or without
|
|
Packit |
0d464f |
// modification, are permitted provided that the following conditions are
|
|
Packit |
0d464f |
// met:
|
|
Packit |
0d464f |
// * Redistributions of source code must retain the above copyright
|
|
Packit |
0d464f |
// notice, this list of conditions and the following disclaimer.
|
|
Packit |
0d464f |
// * Redistributions in binary form must reproduce the above
|
|
Packit |
0d464f |
// copyright notice, this list of conditions and the following disclaimer
|
|
Packit |
0d464f |
// in the documentation and/or other materials provided with the
|
|
Packit |
0d464f |
// distribution.
|
|
Packit |
0d464f |
// * Neither the name of DreamWorks Animation nor the names of
|
|
Packit |
0d464f |
// its contributors may be used to endorse or promote products derived
|
|
Packit |
0d464f |
// from this software without specific prior written permission.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
Packit |
0d464f |
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
Packit |
0d464f |
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
|
Packit |
0d464f |
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
|
|
Packit |
0d464f |
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
|
Packit |
0d464f |
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
|
Packit |
0d464f |
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|
Packit |
0d464f |
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|
Packit |
0d464f |
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
Packit |
0d464f |
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
Packit |
0d464f |
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
///////////////////////////////////////////////////////////////////////////
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#include "ImfFastHuf.h"
|
|
Packit |
0d464f |
#include <Iex.h>
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#include <string.h>
|
|
Packit |
0d464f |
#include <assert.h>
|
|
Packit |
0d464f |
#include <math.h>
|
|
Packit |
0d464f |
#include <vector>
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
OPENEXR_IMF_INTERNAL_NAMESPACE_SOURCE_ENTER
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Adapted from hufUnpackEncTable -
|
|
Packit |
0d464f |
// We don't need to reconstruct the code book, just the encoded
|
|
Packit |
0d464f |
// lengths for each symbol. From the lengths, we can build the
|
|
Packit |
0d464f |
// base + offset tables. This should be a bit more efficient
|
|
Packit |
0d464f |
// for sparse code books.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// table - ptr to the start of the code length data. Will be
|
|
Packit |
0d464f |
// updated as we decode data
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// numBytes - size of the encoded table (I think)?
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// minSymbol - smallest symbol in the code book
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// maxSymbol - largest symbol in the code book.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// rleSymbol - the symbol to trigger RLE in the encoded bitstream
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
FastHufDecoder::FastHufDecoder
|
|
Packit |
0d464f |
(const char *&table,
|
|
Packit |
0d464f |
int numBytes,
|
|
Packit |
0d464f |
int minSymbol,
|
|
Packit |
0d464f |
int maxSymbol,
|
|
Packit |
0d464f |
int rleSymbol)
|
|
Packit |
0d464f |
:
|
|
Packit |
0d464f |
_rleSymbol (rleSymbol),
|
|
Packit |
0d464f |
_numSymbols (0),
|
|
Packit |
0d464f |
_minCodeLength (255),
|
|
Packit |
0d464f |
_maxCodeLength (0),
|
|
Packit |
0d464f |
_idToSymbol (0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// List of symbols that we find with non-zero code lengths
|
|
Packit |
0d464f |
// (listed in the order we find them). Store these in the
|
|
Packit |
0d464f |
// same format as the code book stores codes + lengths -
|
|
Packit |
0d464f |
// low 6 bits are the length, everything above that is
|
|
Packit |
0d464f |
// the symbol.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
std::vector<Int64> symbols;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// The 'base' table is the minimum code at each code length. base[i]
|
|
Packit |
0d464f |
// is the smallest code (numerically) of length i.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 base[MAX_CODE_LEN + 1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// The 'offset' table is the position (in sorted order) of the first id
|
|
Packit |
0d464f |
// of a given code lenght. Array is indexed by code length, like base.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 offset[MAX_CODE_LEN + 1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Count of how many codes at each length there are. Array is
|
|
Packit |
0d464f |
// indexed by code length, like base and offset.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
size_t codeCount[MAX_CODE_LEN + 1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i = 0; i <= MAX_CODE_LEN; ++i)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
codeCount[i] = 0;
|
|
Packit |
0d464f |
base[i] = 0xffffffffffffffffL;
|
|
Packit |
0d464f |
offset[i] = 0;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Count the number of codes, the min/max code lengths, the number of
|
|
Packit |
0d464f |
// codes with each length, and record symbols with non-zero code
|
|
Packit |
0d464f |
// length as we find them.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
const char *currByte = table;
|
|
Packit |
0d464f |
Int64 currBits = 0;
|
|
Packit |
0d464f |
int currBitCount = 0;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
const int SHORT_ZEROCODE_RUN = 59;
|
|
Packit |
0d464f |
const int LONG_ZEROCODE_RUN = 63;
|
|
Packit |
0d464f |
const int SHORTEST_LONG_RUN = 2 + LONG_ZEROCODE_RUN - SHORT_ZEROCODE_RUN;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (Int64 symbol = minSymbol; symbol <= maxSymbol; symbol++)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (currByte - table > numBytes)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Error decoding Huffman table "
|
|
Packit |
0d464f |
"(Truncated table data).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Next code length - either:
|
|
Packit |
0d464f |
// 0-58 (literal code length)
|
|
Packit |
0d464f |
// 59-62 (various lengths runs of 0)
|
|
Packit |
0d464f |
// 63 (run of n 0's, with n is the next 8 bits)
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 codeLen = readBits (6, currBits, currBitCount, currByte);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (codeLen == (Int64) LONG_ZEROCODE_RUN)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (currByte - table > numBytes)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Error decoding Huffman table "
|
|
Packit |
0d464f |
"(Truncated table data).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
int runLen = readBits (8, currBits, currBitCount, currByte) +
|
|
Packit |
0d464f |
SHORTEST_LONG_RUN;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (symbol + runLen > maxSymbol + 1)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Error decoding Huffman table "
|
|
Packit |
0d464f |
"(Run beyond end of table).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
symbol += runLen - 1;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else if (codeLen >= (Int64) SHORT_ZEROCODE_RUN)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
int runLen = codeLen - SHORT_ZEROCODE_RUN + 2;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (symbol + runLen > maxSymbol + 1)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Error decoding Huffman table "
|
|
Packit |
0d464f |
"(Run beyond end of table).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
symbol += runLen - 1;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else if (codeLen != 0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
symbols.push_back ((symbol << 6) | (codeLen & 63));
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (codeLen < _minCodeLength)
|
|
Packit |
0d464f |
_minCodeLength = codeLen;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (codeLen > _maxCodeLength)
|
|
Packit |
0d464f |
_maxCodeLength = codeLen;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
codeCount[codeLen]++;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i = 0; i < MAX_CODE_LEN; ++i)
|
|
Packit |
0d464f |
_numSymbols += codeCount[i];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
table = currByte;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Compute base - once we have the code length counts, there
|
|
Packit |
0d464f |
// is a closed form solution for this
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
double* countTmp = new double[_maxCodeLength+1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int l = _minCodeLength; l <= _maxCodeLength; ++l)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
countTmp[l] = (double)codeCount[l] *
|
|
Packit |
0d464f |
(double)(2 << (_maxCodeLength-l));
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int l = _minCodeLength; l <= _maxCodeLength; ++l)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
double tmp = 0;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int k =l + 1; k <= _maxCodeLength; ++k)
|
|
Packit |
0d464f |
tmp += countTmp[k];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
tmp /= (double)(2 << (_maxCodeLength - l));
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
base[l] = (Int64)ceil (tmp);
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
delete [] countTmp;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Compute offset - these are the positions of the first
|
|
Packit |
0d464f |
// id (not symbol) that has length [i]
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
offset[_maxCodeLength] = 0;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i= _maxCodeLength - 1; i >= _minCodeLength; i--)
|
|
Packit |
0d464f |
offset[i] = offset[i + 1] + codeCount[i + 1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Allocate and fill the symbol-to-id mapping. Smaller Ids should be
|
|
Packit |
0d464f |
// mapped to less-frequent symbols (which have longer codes). Use
|
|
Packit |
0d464f |
// the offset table to tell us where the id's for a given code
|
|
Packit |
0d464f |
// length start off.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
_idToSymbol = new int[_numSymbols];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 mapping[MAX_CODE_LEN + 1];
|
|
Packit |
0d464f |
for (int i = 0; i < MAX_CODE_LEN + 1; ++i)
|
|
Packit |
0d464f |
mapping[i] = -1;
|
|
Packit |
0d464f |
for (int i = _minCodeLength; i <= _maxCodeLength; ++i)
|
|
Packit |
0d464f |
mapping[i] = offset[i];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (std::vector<Int64>::const_iterator i = symbols.begin();
|
|
Packit |
0d464f |
i != symbols.end();
|
|
Packit |
0d464f |
++i)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
int codeLen = *i & 63;
|
|
Packit |
0d464f |
int symbol = *i >> 6;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (mapping[codeLen] >= _numSymbols)
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error "
|
|
Packit |
0d464f |
"(Invalid symbol in header).");
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
_idToSymbol[mapping[codeLen]] = symbol;
|
|
Packit |
0d464f |
mapping[codeLen]++;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
buildTables(base, offset);
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
FastHufDecoder::~FastHufDecoder()
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
delete[] _idToSymbol;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Static check if the decoder is enabled.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// ATM, I only have access to little endian hardware for testing,
|
|
Packit |
0d464f |
// so I'm not entirely sure that we are reading fom the bit stream
|
|
Packit |
0d464f |
// properly on BE.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// If you happen to have more obscure hardware, check that the
|
|
Packit |
0d464f |
// byte swapping in refill() is happening sensable, add an endian
|
|
Packit |
0d464f |
// check if needed, and fix the preprocessor magic here.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#define READ64(c) \
|
|
Packit |
0d464f |
((Int64)(c)[0] << 56) | ((Int64)(c)[1] << 48) | ((Int64)(c)[2] << 40) | \
|
|
Packit |
0d464f |
((Int64)(c)[3] << 32) | ((Int64)(c)[4] << 24) | ((Int64)(c)[5] << 16) | \
|
|
Packit |
0d464f |
((Int64)(c)[6] << 8) | ((Int64)(c)[7] )
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#ifdef __INTEL_COMPILER // ICC built-in swap for LE hosts
|
|
Packit |
0d464f |
#if defined (__i386__) || defined(__x86_64__)
|
|
Packit |
0d464f |
#undef READ64
|
|
Packit |
0d464f |
#define READ64(c) _bswap64 (*(const Int64*)(c))
|
|
Packit |
0d464f |
#endif
|
|
Packit |
0d464f |
#endif
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bool
|
|
Packit |
0d464f |
FastHufDecoder::enabled()
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
#if defined(__INTEL_COMPILER) || defined(__GNUC__)
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Enabled for ICC, GCC:
|
|
Packit |
0d464f |
// __i386__ -> x86
|
|
Packit |
0d464f |
// __x86_64__ -> 64-bit x86
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#if defined (__i386__) || defined(__x86_64__)
|
|
Packit |
0d464f |
return true;
|
|
Packit |
0d464f |
#else
|
|
Packit |
0d464f |
return false;
|
|
Packit |
0d464f |
#endif
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#elif defined (_MSC_VER)
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Enabled for Visual Studio:
|
|
Packit |
0d464f |
// _M_IX86 -> x86
|
|
Packit |
0d464f |
// _M_X64 -> 64bit x86
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#if defined (_M_IX86) || defined(_M_X64)
|
|
Packit |
0d464f |
return true;
|
|
Packit |
0d464f |
#else
|
|
Packit |
0d464f |
return false;
|
|
Packit |
0d464f |
#endif
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
#else
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Unknown compiler - Be safe and disable.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
return false;
|
|
Packit |
0d464f |
#endif
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Built the acceleration tables for lookups on the upper bits
|
|
Packit |
0d464f |
// as well as the 'LJ' tables.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
void
|
|
Packit |
0d464f |
FastHufDecoder::buildTables (Int64 *base, Int64 *offset)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Build the 'left justified' base table, by shifting base left..
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i = 0; i <= MAX_CODE_LEN; ++i)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (base[i] != 0xffffffffffffffffL)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
_ljBase[i] = base[i] << (64 - i);
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Unused code length - insert dummy values
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
_ljBase[i] = 0xffffffffffffffffL;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Combine some terms into a big fat constant, which for
|
|
Packit |
0d464f |
// lack of a better term we'll call the 'left justified'
|
|
Packit |
0d464f |
// offset table (because it serves the same function
|
|
Packit |
0d464f |
// as 'offset', when using the left justified base table.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i = 0; i <= MAX_CODE_LEN; ++i)
|
|
Packit |
0d464f |
_ljOffset[i] = offset[i] - (_ljBase[i] >> (64 - i));
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Build the acceleration tables for the lookups of
|
|
Packit |
0d464f |
// short codes ( <= TABLE_LOOKUP_BITS long)
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (Int64 i = 0; i < 1 << TABLE_LOOKUP_BITS; ++i)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
Int64 value = i << (64 - TABLE_LOOKUP_BITS);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
_tableSymbol[i] = 0xffff;
|
|
Packit |
0d464f |
_tableCodeLen[i] = 0;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int codeLen = _minCodeLength; codeLen <= _maxCodeLength; ++codeLen)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (_ljBase[codeLen] <= value)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
_tableCodeLen[i] = codeLen;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 id = _ljOffset[codeLen] + (value >> (64 - codeLen));
|
|
Packit |
0d464f |
if (id < _numSymbols)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
_tableSymbol[i] = _idToSymbol[id];
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error "
|
|
Packit |
0d464f |
"(Overrun).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
break;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Store the smallest value in the table that points to real data.
|
|
Packit |
0d464f |
// This should be the entry for the largest length that has
|
|
Packit |
0d464f |
// valid data (in our case, non-dummy _ljBase)
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
int minIdx = TABLE_LOOKUP_BITS;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
while (minIdx > 0 && _ljBase[minIdx] == 0xffffffffffffffffL)
|
|
Packit |
0d464f |
minIdx--;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (minIdx < 0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Error, no codes with lengths 0-TABLE_LOOKUP_BITS used.
|
|
Packit |
0d464f |
// Set the min value such that the table is never tested.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
_tableMin = 0xffffffffffffffffL;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
_tableMin = _ljBase[minIdx];
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// For decoding, we're holding onto 2 Int64's.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// The first (buffer), holds the next bits from the bitstream to be
|
|
Packit |
0d464f |
// decoded. For certain paths in the decoder, we only need TABLE_LOOKUP_BITS
|
|
Packit |
0d464f |
// valid bits to decode the next symbol. For other paths, we need a full
|
|
Packit |
0d464f |
// 64-bits to decode a symbol.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// When we need to refill 'buffer', we could pull bits straight from
|
|
Packit |
0d464f |
// the bitstream. But this is very slow and requires lots of book keeping
|
|
Packit |
0d464f |
// (what's the next bit in the next byte?). Instead, we keep another Int64
|
|
Packit |
0d464f |
// around that we use to refill from. While this doesn't cut down on the
|
|
Packit |
0d464f |
// book keeping (still need to know how many valid bits), it does cut
|
|
Packit |
0d464f |
// down on some of the bit shifting crazy and byte access.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// The refill Int64 (bufferBack) gets left-shifted after we've pulled
|
|
Packit |
0d464f |
// off bits. If we run out of bits in the input bit stream, we just
|
|
Packit |
0d464f |
// shift in 0's to bufferBack.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// The refill act takes numBits from the top of bufferBack and sticks
|
|
Packit |
0d464f |
// them in the bottom of buffer. If there arn't enough bits in bufferBack,
|
|
Packit |
0d464f |
// it gets refilled (to 64-bits) from the input bitstream.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
inline void
|
|
Packit |
0d464f |
FastHufDecoder::refill
|
|
Packit |
0d464f |
(Int64 &buffer,
|
|
Packit |
0d464f |
int numBits, // number of bits to refill
|
|
Packit |
0d464f |
Int64 &bufferBack, // the next 64-bits, to refill from
|
|
Packit |
0d464f |
int &bufferBackNumBits, // number of bits left in bufferBack
|
|
Packit |
0d464f |
const unsigned char *&currByte, // current byte in the bitstream
|
|
Packit |
0d464f |
int &currBitsLeft) // number of bits left in the bitsream
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Refill bits into the bottom of buffer, from the top of bufferBack.
|
|
Packit |
0d464f |
// Always top up buffer to be completely full.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
buffer |= bufferBack >> (64 - numBits);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (bufferBackNumBits < numBits)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
numBits -= bufferBackNumBits;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Refill all of bufferBack from the bitstream. Either grab
|
|
Packit |
0d464f |
// a full 64-bit chunk, or whatever bytes are left. If we
|
|
Packit |
0d464f |
// don't have 64-bits left, pad with 0's.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (currBitsLeft >= 64)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
bufferBack = READ64 (currByte);
|
|
Packit |
0d464f |
bufferBackNumBits = 64;
|
|
Packit |
0d464f |
currByte += sizeof (Int64);
|
|
Packit |
0d464f |
currBitsLeft -= 8 * sizeof (Int64);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
bufferBack = 0;
|
|
Packit |
0d464f |
bufferBackNumBits = 64;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 shift = 56;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
while (currBitsLeft > 0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
bufferBack |= ((Int64)(*currByte)) << shift;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
currByte++;
|
|
Packit |
0d464f |
shift -= 8;
|
|
Packit |
0d464f |
currBitsLeft -= 8;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// At this point, currBitsLeft might be negative, just because
|
|
Packit |
0d464f |
// we're subtracting whole bytes. To keep anyone from freaking
|
|
Packit |
0d464f |
// out, zero the counter.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (currBitsLeft < 0)
|
|
Packit |
0d464f |
currBitsLeft = 0;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
buffer |= bufferBack >> (64 - numBits);
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bufferBack = bufferBack << numBits;
|
|
Packit |
0d464f |
bufferBackNumBits -= numBits;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// We can have cases where the previous shift of bufferBack is << 64 -
|
|
Packit |
0d464f |
// in which case no shift occurs. The bit count math still works though,
|
|
Packit |
0d464f |
// so if we don't have any bits left, zero out bufferBack.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (bufferBackNumBits == 0)
|
|
Packit |
0d464f |
bufferBack = 0;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Read the next few bits out of a bitstream. Will be given a backing buffer
|
|
Packit |
0d464f |
// (buffer) that may still have data left over from previous reads
|
|
Packit |
0d464f |
// (bufferNumBits). Bitstream pointer (currByte) will be advanced when needed.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
inline Int64
|
|
Packit |
0d464f |
FastHufDecoder::readBits
|
|
Packit |
0d464f |
(int numBits,
|
|
Packit |
0d464f |
Int64 &buffer, // c
|
|
Packit |
0d464f |
int &bufferNumBits, // lc
|
|
Packit |
0d464f |
const char *&currByte) // in
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
while (bufferNumBits < numBits)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
buffer = (buffer << 8) | *(unsigned char*)(currByte++);
|
|
Packit |
0d464f |
bufferNumBits += 8;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bufferNumBits -= numBits;
|
|
Packit |
0d464f |
return (buffer >> bufferNumBits) & ((1 << numBits) - 1);
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Decode using a the 'One-Shift' strategy for decoding, with a
|
|
Packit |
0d464f |
// small-ish table to accelerate decoding of short codes.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// If possible, try looking up codes into the acceleration table.
|
|
Packit |
0d464f |
// This has a few benifits - there's no search involved; We don't
|
|
Packit |
0d464f |
// need an additional lookup to map id to symbol; we don't need
|
|
Packit |
0d464f |
// a full 64-bits (so less refilling).
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
void
|
|
Packit |
0d464f |
FastHufDecoder::decode
|
|
Packit |
0d464f |
(const unsigned char *src,
|
|
Packit |
0d464f |
int numSrcBits,
|
|
Packit |
0d464f |
unsigned short *dst,
|
|
Packit |
0d464f |
int numDstElems)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (numSrcBits < 128)
|
|
Packit |
0d464f |
throw Iex::InputExc ("Error choosing Huffman decoder implementation "
|
|
Packit |
0d464f |
"(insufficient number of bits).");
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Current position (byte/bit) in the src data stream
|
|
Packit |
0d464f |
// (after the first buffer fill)
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
const unsigned char *currByte = src + 2 * sizeof (Int64);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
numSrcBits -= 8 * 2 * sizeof (Int64);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// 64-bit buffer holding the current bits in the stream
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 buffer = READ64 (src);
|
|
Packit |
0d464f |
int bufferNumBits = 64;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// 64-bit buffer holding the next bits in the stream
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 bufferBack = READ64 ((src + sizeof (Int64)));
|
|
Packit |
0d464f |
int bufferBackNumBits = 64;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
int dstIdx = 0;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
while (dstIdx < numDstElems)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
int codeLen;
|
|
Packit |
0d464f |
int symbol;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Test if we can be table accelerated. If so, directly
|
|
Packit |
0d464f |
// lookup the output symbol. Otherwise, we need to fall
|
|
Packit |
0d464f |
// back to searching for the code.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// If we're doing table lookups, we don't really need
|
|
Packit |
0d464f |
// a re-filled buffer, so long as we have TABLE_LOOKUP_BITS
|
|
Packit |
0d464f |
// left. But for a search, we do need a refilled table.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (_tableMin <= buffer)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
int tableIdx = buffer >> (64 - TABLE_LOOKUP_BITS);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// For invalid codes, _tableCodeLen[] should return 0. This
|
|
Packit |
0d464f |
// will cause the decoder to get stuck in the current spot
|
|
Packit |
0d464f |
// until we run out of elements, then barf that the codestream
|
|
Packit |
0d464f |
// is bad. So we don't need to stick a condition like
|
|
Packit |
0d464f |
// if (codeLen > _maxCodeLength) in this inner.
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
codeLen = _tableCodeLen[tableIdx];
|
|
Packit |
0d464f |
symbol = _tableSymbol[tableIdx];
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (bufferNumBits < 64)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
refill (buffer,
|
|
Packit |
0d464f |
64 - bufferNumBits,
|
|
Packit |
0d464f |
bufferBack,
|
|
Packit |
0d464f |
bufferBackNumBits,
|
|
Packit |
0d464f |
currByte,
|
|
Packit |
0d464f |
numSrcBits);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bufferNumBits = 64;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Brute force search:
|
|
Packit |
0d464f |
// Find the smallest length where _ljBase[length] <= buffer
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
codeLen = TABLE_LOOKUP_BITS + 1;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
while (_ljBase[codeLen] > buffer && codeLen <= _maxCodeLength)
|
|
Packit |
0d464f |
codeLen++;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (codeLen > _maxCodeLength)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error "
|
|
Packit |
0d464f |
"(Decoded an invalid symbol).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
Int64 id = _ljOffset[codeLen] + (buffer >> (64 - codeLen));
|
|
Packit |
0d464f |
if (id < _numSymbols)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
symbol = _idToSymbol[id];
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error "
|
|
Packit |
0d464f |
"(Decoded an invalid symbol).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// Shift over bit stream, and update the bit count in the buffer
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
buffer = buffer << codeLen;
|
|
Packit |
0d464f |
bufferNumBits -= codeLen;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// If we recieved a RLE symbol (_rleSymbol), then we need
|
|
Packit |
0d464f |
// to read ahead 8 bits to know how many times to repeat
|
|
Packit |
0d464f |
// the previous symbol. Need to ensure we at least have
|
|
Packit |
0d464f |
// 8 bits of data in the buffer
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (symbol == _rleSymbol)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
if (bufferNumBits < 8)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
refill (buffer,
|
|
Packit |
0d464f |
64 - bufferNumBits,
|
|
Packit |
0d464f |
bufferBack,
|
|
Packit |
0d464f |
bufferBackNumBits,
|
|
Packit |
0d464f |
currByte,
|
|
Packit |
0d464f |
numSrcBits);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bufferNumBits = 64;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
int rleCount = buffer >> 56;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (dstIdx < 1)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error (RLE code "
|
|
Packit |
0d464f |
"with no previous symbol).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (dstIdx + rleCount > numDstElems)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error (Symbol run "
|
|
Packit |
0d464f |
"beyond expected output buffer length).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (rleCount <= 0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc("Huffman decode error"
|
|
Packit |
0d464f |
" (Invalid RLE length)");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
for (int i = 0; i < rleCount; ++i)
|
|
Packit |
0d464f |
dst[dstIdx + i] = dst[dstIdx - 1];
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
dstIdx += rleCount;
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
buffer = buffer << 8;
|
|
Packit |
0d464f |
bufferNumBits -= 8;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
else
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
dst[dstIdx] = symbol;
|
|
Packit |
0d464f |
dstIdx++;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
// refill bit stream buffer if we're below the number of
|
|
Packit |
0d464f |
// bits needed for a table lookup
|
|
Packit |
0d464f |
//
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (bufferNumBits < TABLE_LOOKUP_BITS)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
refill (buffer,
|
|
Packit |
0d464f |
64 - bufferNumBits,
|
|
Packit |
0d464f |
bufferBack,
|
|
Packit |
0d464f |
bufferBackNumBits,
|
|
Packit |
0d464f |
currByte,
|
|
Packit |
0d464f |
numSrcBits);
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
bufferNumBits = 64;
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
if (numSrcBits != 0)
|
|
Packit |
0d464f |
{
|
|
Packit |
0d464f |
throw Iex::InputExc ("Huffman decode error (Compressed data remains "
|
|
Packit |
0d464f |
"after filling expected output buffer).");
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
}
|
|
Packit |
0d464f |
|
|
Packit |
0d464f |
OPENEXR_IMF_INTERNAL_NAMESPACE_SOURCE_EXIT
|