imfhuf.cpp

对gif

	    unexpectedEndOfTable();

	Int64 l = hcode[im] = getBits (6, c, lc, p); // code length

	if (l == (Int64) LONG_ZEROCODE_RUN)
	{
	    if (p - *pcode > ni)
		unexpectedEndOfTable();

	    int zerun = getBits (8, c, lc, p) + SHORTEST_LONG_RUN;

	    if (im + zerun > iM + 1)
		tableTooLong();

	    while (zerun--)
		hcode[im++] = 0;

	    im--;
	}
	else if (l >= (Int64) SHORT_ZEROCODE_RUN)
	{
	    int zerun = l - SHORT_ZEROCODE_RUN + 2;

	    if (im + zerun > iM + 1)
		tableTooLong();

	    while (zerun--)
		hcode[im++] = 0;

	    im--;
	}
    }

    *pcode = (char *) p;

    hufCanonicalCodeTable (hcode);
}


//
// DECODING TABLE BUILDING
//

//
// Build a decoding hash table based on the encoding table hcode:
//	- short codes (<= HUF_DECBITS) are resolved with a single table access;
//	- long code entry allocations are not optimized, because long codes are
//	  unfrequent;
//	- decoding tables are used by hufDecode();
//

void
hufBuildDecTable
    (const Int64*	hcode,		// i : encoding table
     int		im,		// i : min index in hcode
     int		iM,		// i : max index in hcode
     HufDec *		hdecod)		//  o: (allocated by caller)
     					//     decoding table [HUF_DECSIZE]
{
    //
    // Init hashtable & loop on all codes
    //

    memset (hdecod, 0, sizeof (HufDec) * HUF_DECSIZE);

    for (; im <= iM; im++)
    {
	Int64 c = hufCode (hcode[im]);
	int l = hufLength (hcode[im]);

	if (c >> l)
	{
	    //
	    // Error: c is supposed to be an l-bit code,
	    // but c contains a value that is greater
	    // than the largest l-bit number.
	    //

	    invalidTableEntry();
	}

	if (l > HUF_DECBITS)
	{
	    //
	    // Long code: add a secondary entry
	    //

	    HufDec *pl = hdecod + (c >> (l - HUF_DECBITS));

	    if (pl->len)
	    {
		//
		// Error: a short code has already
		// been stored in table entry *pl.
		//

		invalidTableEntry();
	    }

	    pl->lit++;

	    if (pl->p)
	    {
		int *p = pl->p;
		pl->p = new int [pl->lit];

		for (int i = 0; i < pl->lit - 1; ++i)
		    pl->p[i] = p[i];

		delete [] p;
	    }
	    else
	    {
		pl->p = new int [1];
	    }

	    pl->p[pl->lit - 1]= im;
	}
	else if (l)
	{
	    //
	    // Short code: init all primary entries
	    //

	    HufDec *pl = hdecod + (c << (HUF_DECBITS - l));

	    for (Int64 i = 1 << (HUF_DECBITS - l); i > 0; i--, pl++)
	    {
		if (pl->len || pl->p)
		{
		    //
		    // Error: a short code or a long code has
		    // already been stored in table entry *pl.
		    //

		    invalidTableEntry();
		}

		pl->len = l;
		pl->lit = im;
	    }
	}
    }
}


//
// Free the long code entries of a decoding table built by hufBuildDecTable()
//

void
hufFreeDecTable (HufDec *hdecod)	// io: Decoding table
{
    for (int i = 0; i < HUF_DECSIZE; i++)
    {
	if (hdecod[i].p)
	{
	    delete [] hdecod[i].p;
	    hdecod[i].p = 0;
	}
    }
}


//
// ENCODING
//

inline void
outputCode (Int64 code, Int64 &c, int &lc, char *&out)
{
    outputBits (hufLength (code), hufCode (code), c, lc, out);
}


inline void
sendCode (Int64 sCode, int runCount, Int64 runCode,
	  Int64 &c, int &lc, char *&out)
{
    static const int RLMIN = 32; // min count to activate run-length coding

    if (runCount > RLMIN)
    {
	outputCode (sCode, c, lc, out);
	outputCode (runCode, c, lc, out);
	outputBits (8, runCount, c, lc, out);
    }
    else
    {
	while (runCount-- >= 0)
	    outputCode (sCode, c, lc, out);
    }
}


//
// Encode (compress) ni values based on the Huffman encoding table hcode:
//

int
hufEncode				// return: output size (in bits)
    (const Int64*  	    hcode,	// i : encoding table
     const unsigned short*  in,		// i : uncompressed input buffer
     const int     	    ni,		// i : input buffer size (in bytes)
     int           	    rlc,	// i : rl code
     char*         	    out)	//  o: compressed output buffer
{
    char *outStart = out;
    Int64 c = 0;	// bits not yet written to out
    int lc = 0;		// number of valid bits in c (LSB)
    int s = in[0];
    int cs = 0;

    //
    // Loop on input values
    //

    for (int i = 1; i < ni; i++)
    {
	//
	// Count same values or send code
	//

	if (s == in[i] && cs < 255)
	{
	    cs++;
	}
	else
	{
	    sendCode (hcode[s], cs, hcode[rlc], c, lc, out);
	    cs=0;
	}

	s = in[i];
    }

    //
    // Send remaining code
    //

    sendCode (hcode[s], cs, hcode[rlc], c, lc, out);

    if (lc)
	*out = (c << (8 - lc)) & 0xff;

    return (out - outStart) * 8 + lc;
}


//
// DECODING
//

//
// In order to force the compiler to inline them,
// getChar() and getCode() are implemented as macros
// instead of "inline" functions.
//

#define getChar(c, lc, in)			\
{						\
    c = (c << 8) | *(unsigned char *)(in++);	\
    lc += 8;					\
}


#define getCode(po, rlc, c, lc, in, out, oe)	\
{						\
    if (po == rlc)				\
    {						\
	if (lc < 8)				\
	    getChar(c, lc, in);			\
						\
	lc -= 8;				\
						\
	unsigned char cs = (c >> lc);		\
						\
	if (out + cs > oe)			\
	    tooMuchData();			\
						\
	unsigned short s = out[-1];		\
						\
	while (cs-- > 0)			\
	    *out++ = s;				\
    }						\
    else if (out < oe)				\
    {						\
	*out++ = po;				\
    }						\
    else					\
    {						\
	tooMuchData();				\
    }						\
}


//
// Decode (uncompress) ni bits based on encoding & decoding tables:
//

void
hufDecode
    (const Int64 * 	hcode,	// i : encoding table
     const HufDec * 	hdecod,	// i : decoding table
     const char* 	in,	// i : compressed input buffer
     int		ni,	// i : input size (in bits)
     int		rlc,	// i : run-length code
     int		no,	// i : expected output size (in bytes)
     unsigned short*	out)	//  o: uncompressed output buffer
{
    Int64 c = 0;
    int lc = 0;
    unsigned short * outb = out;
    unsigned short * oe = out + no;
    const char * ie = in + (ni + 7) / 8; // input byte size

    //
    // Loop on input bytes
    //

    while (in < ie)
    {
	getChar (c, lc, in);

	//
	// Access decoding table
	//

	while (lc >= HUF_DECBITS)
	{
	    const HufDec pl = hdecod[(c >> (lc-HUF_DECBITS)) & HUF_DECMASK];

	    if (pl.len)
	    {
		//
		// Get short code
		//

		lc -= pl.len;
		getCode (pl.lit, rlc, c, lc, in, out, oe);
	    }
	    else
	    {
		if (!pl.p)
		    invalidCode(); // wrong code

		//
		// Search long code
		//

		int j;

		for (j = 0; j < pl.lit; j++)
		{
		    int	l = hufLength (hcode[pl.p[j]]);

		    while (lc < l && in < ie)	// get more bits
			getChar (c, lc, in);

		    if (lc >= l)
		    {
			if (hufCode (hcode[pl.p[j]]) ==
				((c >> (lc - l)) & ((Int64(1) << l) - 1)))
			{
			    //
			    // Found : get long code
			    //

			    lc -= l;
			    getCode (pl.p[j], rlc, c, lc, in, out, oe);
			    break;
			}
		    }
		}

		if (j == pl.lit)
		    invalidCode(); // Not found
	    }
	}
    }

    //
    // Get remaining (short) codes
    //

    int i = (8 - ni) & 7;
    c >>= i;
    lc -= i;

    while (lc > 0)
    {
	const HufDec pl = hdecod[(c << (HUF_DECBITS - lc)) & HUF_DECMASK];

	if (pl.len)
	{
	    lc -= pl.len;
	    getCode (pl.lit, rlc, c, lc, in, out, oe);
	}
	else
	{
	    invalidCode(); // wrong (long) code
	}
    }

    if (out - outb != no)
	notEnoughData ();
}


void
countFrequencies (Int64 freq[HUF_ENCSIZE],
		  const unsigned short data[/*n*/],
		  int n)
{
    for (int i = 0; i < HUF_ENCSIZE; ++i)
	freq[i] = 0;

    for (int i = 0; i < n; ++i)
	++freq[data[i]];
}


void
writeUInt (char buf[4], unsigned int i)
{
    unsigned char *b = (unsigned char *) buf;

    b[0] = i;
    b[1] = i >> 8;
    b[2] = i >> 16;
    b[3] = i >> 24;
}


unsigned int
readUInt (const char buf[4])
{
    const unsigned char *b = (const unsigned char *) buf;

    return ( b[0]        & 0x000000ff) |
	   ((b[1] <<  8) & 0x0000ff00) |
	   ((b[2] << 16) & 0x00ff0000) |
	   ((b[3] << 24) & 0xff000000);
}

} // namespace


//
// EXTERNAL INTERFACE
//


int
hufCompress (const unsigned short raw[],
	     int nRaw,
	     char compressed[])
{
    if (nRaw == 0)
	return 0;

    AutoArray <Int64, HUF_ENCSIZE> freq;

    countFrequencies (freq, raw, nRaw);

    int im, iM;
    hufBuildEncTable (freq, &im, &iM);

    char *tableStart = compressed + 20;
    char *tableEnd   = tableStart;
    hufPackEncTable (freq, im, iM, &tableEnd);
    int tableLength = tableEnd - tableStart;

    char *dataStart = tableEnd;
    int nBits = hufEncode (freq, raw, nRaw, iM, dataStart);
    int dataLength = (nBits + 7) / 8;

    writeUInt (compressed,      im);
    writeUInt (compressed +  4, iM);
    writeUInt (compressed +  8, tableLength);
    writeUInt (compressed + 12, nBits);
    writeUInt (compressed + 16, 0);	// room for future extensions

    return dataStart + dataLength - compressed;
}


void
hufUncompress (const char compressed[],
	       int nCompressed,
	       unsigned short raw[],
	       int nRaw)
{
    if (nCompressed == 0)
    {
	if (nRaw != 0)
	    notEnoughData();

	return;
    }

    int im = readUInt (compressed);
    int iM = readUInt (compressed + 4);
    // int tableLength = readUInt (compressed + 8);
    int nBits = readUInt (compressed + 12);

    if (im < 0 || im >= HUF_ENCSIZE || iM < 0 || iM >= HUF_ENCSIZE)
	invalidTableSize();

    const char *ptr = compressed + 20;

    AutoArray <Int64, HUF_ENCSIZE> freq;
    AutoArray <HufDec, HUF_DECSIZE> hdec;

    hufUnpackEncTable (&ptr, nCompressed - (ptr - compressed), im, iM, freq);

    try
    {
	if (nBits > 8 * (nCompressed - (ptr - compressed)))
	    invalidNBits();

	hufBuildDecTable (freq, im, iM, hdec);
	hufDecode (freq, hdec, ptr, nBits, iM, nRaw, raw);
    }
    catch (...)
    {
	hufFreeDecTable (hdec);
	throw;
    }

    hufFreeDecTable (hdec);
}


} // namespace Imf