CDE/cde/lib/DtHelp/il/iljpgenhuff.c

/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: iljpgenhuff.c /main/3 1995/10/23 15:57:13 rswiston $ */
/**---------------------------------------------------------------------
***	
***    (c)Copyright 1992 Hewlett-Packard Co.
***    
***                             RESTRICTED RIGHTS LEGEND
***    Use, duplication, or disclosure by the U.S. Government is subject to
***    restrictions as set forth in sub-paragraph (c)(1)(ii) of the Rights in
***    Technical Data and Computer Software clause in DFARS 252.227-7013.
***                             Hewlett-Packard Company
***                             3000 Hanover Street
***                             Palo Alto, CA 94304 U.S.A.
***    Rights for non-DOD U.S. Government Departments and Agencies are as set
***    forth in FAR 52.227-19(c)(1,2).
***
***-------------------------------------------------------------------*/

#include "iljpgencodeint.h"

    /*  Indexed by "i" = 0..255, table of # of bits required to store "i". */
static iljpgByte iljpgBitsNeeded[256] = {
    0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
    5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};

    /*  Internal representation of a Huffman table.  "size" and "code" are
        each indexed by the value to be encoded (0..255).  "size" is the
        # of used (low-order) bits in "code", and "code" contains the actual
        Huffman code.
    */
typedef struct {
    int                 size[257];          /* called "EHUFSI" in JPEG spec */
    int                 code[257];          /* called "EHUFCO" in JPEG spec */
    } iljpgEnhuffTableRec, *iljpgEnhuffTablePtr;

    /*  Data private to this file.  Pointed to by iljpgEncodePrivRec.pHuffPriv.
        Each entry in DC/ACTables[] corresponds to the same table entry in 
        iljpgDataRec (public view), but has been converted for faster access.
        The entry in compDC/ACTables[] are the table for that component.
    */
typedef struct {
    iljpgEnhuffTablePtr DCTables[4];
    iljpgEnhuffTablePtr ACTables[4];
    iljpgEnhuffTablePtr compDCTables[ILJPG_MAX_COMPS];
    iljpgEnhuffTablePtr compACTables[ILJPG_MAX_COMPS];
    int                 huffBits;           /* unflushed Huffman encoded bits */
    int                 nHuffBits;          /* # of bits in huffBits */
    } iljpgEnhuffRec, *iljpgEnhuffPtr;


    /*  -------------------- _iljpgBuildEnhuffTable -------------------------- */
    /*  Build and return a local optimized version of the given standard JPEG
        Huffman DC/AC table.
    */
    ILJPG_PRIVATE 
iljpgError _iljpgBuildEnhuffTable (
    iljpgPtr       pTableIn,
    iljpgEnhuffTablePtr    *ppTableOut          /* RETURNED */
    )
{
    iljpgEnhuffTablePtr pTable;
    int            i, j, nValues, value;
    int                     huffSize[257];      /* called "HUFFSIZE" in JPEG spec */
    int                     huffCode[257];      /* called "HUFFCODE" in JPEG spec */

        /*  Malloc space for internal table, return ptr to it */
    pTable = (iljpgEnhuffTablePtr)ILJPG_MALLOC_ZERO (sizeof (iljpgEnhuffTableRec));
    if (!pTable)
        return ILJPG_ERROR_ENCODE_MALLOC;
    *ppTableOut = pTable;

        /*  Fill in internal table, based on method described in C.2 (pg C-2)
            of the JPEG spec.  pTableIn points to the standard JPEG table:
            16 bytes of the # of codes of each size, followed by "n" bytes of
            the value to be associated with the codes, where "n" = sum of the
            first 16 bytes.
                First generate local size table as in C.2 of spec, leaving
            "pTableIn" pointing past first 16 bytes, to "HUFFVAL" in JPEG spec.
        */
    for (i = 1, nValues = 0; i <= 16; i++) {
        value = *pTableIn++;
        if ((value + nValues) > 256)            /* sum of first 16 bytes too large */
            return ILJPG_ERROR_ENCODE_DCAC_TABLE;
        while (value-- > 0)
            huffSize[nValues++] = i;
        }
    huffSize[nValues] = 0;                      /* "nValues" now "LASTK" in spec */

        /*  Generate HUFFCODE as in fig C.2 (pg C-3) of spec */
    i = j = 0;                                  /* i = "K"; j = "CODE" in spec */
    value = huffSize[0];                        /* "SI" in spec */
    while (TRUE) {
        do {
            huffCode[i] = j;
            i++;
            j++;
            } while (huffSize[i] == value);
        if (huffSize[i] == 0)                   /* terminating 0 seen; done */
            break;
        do {
            j <<= 1;
            value++;
            } while (huffSize[i] != value);
        }

        /*  Reorder values created above into final tables; fig C.3 (C-4) in spec */
    for (j = 0; j < nValues; j++) {             /* j = "K" in spec */
        i = pTableIn[j];
        pTable->code[i] = huffCode[j];
        pTable->size[i] = huffSize[j];
        }

    return 0;
}

    /*  -------------------- _iljpgEnhuffInit -------------------------- */
    /*  Called by iljpgEncodeInit() to init for Huffman encoding.
    */
    ILJPG_PRIVATE 
iljpgError _iljpgEnhuffInit (
    iljpgEncodePrivPtr      pPriv
    )
{
    iljpgEnhuffPtr pHuffPriv;
    iljpgDataPtr   pData;
    iljpgError              error;
    int            i;

        /*  Allocate Huffman private area and point to it in encode private */
    pData = pPriv->pData;
    pHuffPriv = (iljpgEnhuffPtr)ILJPG_MALLOC_ZERO (sizeof (iljpgEnhuffRec));
    if (!pHuffPriv)
        return ILJPG_ERROR_ENCODE_MALLOC;
    pPriv->pHuffPriv = (iljpgPtr)pHuffPriv;

        /*  For each of caller's DC/AC tables, build a local one for more
            efficient access and point to it in private.
        */
    for (i = 0; i < 4; i++) {
        if (pData->DCTables[i]) {
            if (error = _iljpgBuildEnhuffTable (pData->DCTables[i], 
                                                &pHuffPriv->DCTables[i]))
                return error;
            }
        if (pData->ACTables[i]) {
            if (error = _iljpgBuildEnhuffTable (pData->ACTables[i], 
                                                &pHuffPriv->ACTables[i]))
                return error;
            }
        }

        /*  For each component, point to DC/AC tables for that component */
    for (i = 0; i < pData->nComps; i++) {
        pHuffPriv->compDCTables[i] = pHuffPriv->DCTables[pData->comp[i].DCTableIndex];
        pHuffPriv->compACTables[i] = pHuffPriv->ACTables[pData->comp[i].ACTableIndex];
        }

    return 0;
}

                       
    /*  -------------------- _iljpgEnhuffCleanup -------------------------- */
    /*  Called by iljpgEncodeCleanup() to cleanup after Huffman encoding.
    */
    ILJPG_PRIVATE 
iljpgError _iljpgEnhuffCleanup (
    iljpgEncodePrivPtr  pPriv
    )
{
    iljpgEnhuffPtr      pHuffPriv;
    int                 i;

        /*  Free the Huffman encode private data including lookup tables */
    pHuffPriv = (iljpgEnhuffPtr)pPriv->pHuffPriv;
    if (pHuffPriv) {
        for (i = 0; i < 4; i++) {
            if (pHuffPriv->DCTables[i])
                ILJPG_FREE (pHuffPriv->DCTables[i]);
            if (pHuffPriv->ACTables[i])
                ILJPG_FREE (pHuffPriv->ACTables[i]);
            }
        ILJPG_FREE (pHuffPriv);
        }

    return 0;
}


    /*  -------------------- _iljpgPackHuffman -------------------------- */
    /*  Pack the list of (size, value) pairs (pointed to by "pHuff", with
        "nHuff" pairs in it), with output to "stream".
    */
static iljpgError _iljpgPackHuffman (
    iljpgEnhuffPtr      pHuffPriv,
    int       *pHuff,
    int        nHuff,
    ILJPG_ENCODE_STREAM stream
    )
{
    int        size, value, huffBits, nHuffBits;
    iljpgError          error;
    static int          sizeMasks[9] =     /* masks for lower "i" bits, indexed by i */
                            {0x0, 0x1, 0x3, 0x7, 0x0f, 0x1f, 0x3f, 0x7f, 0x0ff};

        /*  For each (size, value) pair, pack the lower "size" bits from "value" and
            write to the output stream.  Bits are packed with MSB first packing.
            "nHuffBits" (0..7!) bits are left from before in "huffBits", in the
            low-order bits.
            After any 0xff, write a 0, as per JPEG spec F.1.2.3 (pg F-7).
        */
    huffBits = pHuffPriv->huffBits;
    nHuffBits = pHuffPriv->nHuffBits;

    while (nHuff-- > 0) {
        size = *pHuff++;
        value = *pHuff++;
        while ((nHuffBits + size) >= 8) {       /* while a byte or more worth */
            nHuffBits = 8 - nHuffBits;          /* now # bits that fit in this byte */
            huffBits <<= nHuffBits;             /* move existing bits up to make room */
            size -= nHuffBits;                  /* # bits from value -= # bits written */
            huffBits |= (value >> size) &       /* or in upper unwritten bits */
                           sizeMasks[nHuffBits];
            if (!ILJPG_ENCODE_PUT_BYTE (stream, huffBits, error))
                return error;                   /* write a byte */
            if (((iljpgByte)huffBits) == ((iljpgByte)0xff))
                if (!ILJPG_ENCODE_PUT_BYTE (stream, 0, error))
                    return error;               /* write a 0 after any 0xff */
            nHuffBits = 0;                      /* all Huff bits written out */
            }
        if (size > 0) {                         /* bits (if any) fit in less than byte */
            huffBits <<= size;                  /* make room for bits from value */
            huffBits |= value & sizeMasks[size]; /* add lower "size" bits from value */
            nHuffBits += size;                  /* "size" more bits now written */
            }
        }   /* END while (size, value) pairs */

        /*  Save unwritten bits and count of same back into private */
    pHuffPriv->huffBits = huffBits;
    pHuffPriv->nHuffBits = nHuffBits;
    return 0;
}


    /*  -------------------- _iljpgEnhuffExecute -------------------------- */
    /*  Huffman encode an 8x8 block (already zig-zagged) from "pSrc" (array of
        64 ints) out to "stream", for component index "comp".  The DC component
        (pSrc[0]) must have already had the lastDC value subtracted from it.
    */
    ILJPG_PRIVATE 
iljpgError _iljpgEnhuffExecute (
    iljpgEncodePrivPtr  pPriv,
    int                 comp,
    int                *pSrc,
    ILJPG_ENCODE_STREAM stream
    )
{
    iljpgEnhuffPtr  pHuffPriv;
    iljpgEnhuffTablePtr    pTable;
    int             huff[4 * 64 + 10];  /* room for 64 * 2 pairs plus some slop */
    int   *pHuff;
    int    size, value, nACLeft, nZeros;
#   define ENHUFF(_value) { \
        *pHuff++ = pTable->size[_value]; \
        *pHuff++ = pTable->code[_value]; \
        }

        /*  Build a list of (size, value) pairs to Huffman encode in "huff", two
            per DC or AC coefficient, possibly less for AC due to zero run-lengths.
            Use pHuff to index thru it.  When done, go back thru list and encode it.
            This is done so that encoding can be done without a function call per encode,
            and without having to replicate long code all over the place.
        */
    pHuffPriv = (iljpgEnhuffPtr)pPriv->pHuffPriv;
    pHuff = huff;

        /*  Encode the first (DC) coefficient, which must already be the difference
            from the previous DC.  See section F.1.2.1 (pg F-3) of the JPEG spec.
            Write Huff code for size of DC, then Huff for DC value, -1 if value < 0.
        */
    pTable = pHuffPriv->compDCTables[comp]; /* use DC table for this component */
    value = *pSrc++;
    if (value < 0) {
        size = -value;
        value -= 1;
        }
    else size = value;
    if (size < 256)
         size = iljpgBitsNeeded[size];
    else size = iljpgBitsNeeded[size>>8] + 8;
    ENHUFF (size)                           /* write huff code for size of DC */
    *pHuff++ = size;                        /* write "size" bits of DC value */
    *pHuff++ = value;

        /*  Encode 63 ACs.  See section F.1.2.2 (pg F-4) of JPEG spec.
            Each AC is represented by 8 bits: RRRRSSSS, where RRRR is the offset
            from the previous non-zero AC - i.e. the # of zero ACs before this one.
            0xf0 = 16 zero ACs; 0 = end of block (EOB), meaning rest of ACs are zero.
            SSSS is the "size" of the AC.  For each AC (excluding zeros), Huff encode
            the 8 bit representation, then write "size" bits as in DC encoding.
        */
    pTable = pHuffPriv->compACTables[comp]; /* use AC table for all other components */
    nACLeft = 63;
    nZeros = 0;
    while (nACLeft-- > 0) {
        value = *pSrc++;
        if (value == 0)
            nZeros++;                       /* AC == 0: count it and continue */
        else {
            while (nZeros >= 16) {          /* AC != 0: flush out runs of 16 or more */
                nZeros -= 16;
                ENHUFF (0xf0)
                }
            if (value < 0)                  /* get SSSS = size of "value" */
                size = -value;
            else size = value;
            if (size < 256)
                 size = iljpgBitsNeeded[size];
            else size = iljpgBitsNeeded[size>>8] + 8;
            nZeros = (nZeros << 4) + size;  /* now have RRRRSSSS in "nZeros" */
            ENHUFF (nZeros)                 /* write huff code for RRRRSSSS */
            nZeros = 0;                     /* reset count of zeros */
            *pHuff++ = size;                /* write "size" bits of AC value */
            if (value < 0) value--;         /* -1 if < 0 */
            *pHuff++ = value;
            }   /* END AC != 0 */
        }       /* END one AC */

        /*  If any zeros were at end of block, write special EOB value (0) */
    if (nZeros > 0) {
        ENHUFF (0)
        }

        /*  Now bit encode all (size, value) pairs in "huff" array */
    return _iljpgPackHuffman (pHuffPriv, huff, (pHuff - huff) / 2, stream);
}


    /*  -------------------- _iljpgEnhuffFlush -------------------------- */
    /*  Flush out any bits left over from Huffman encoding.
    */
    ILJPG_PRIVATE 
iljpgError _iljpgEnhuffFlush (
    iljpgEncodePrivPtr  pPriv,
    ILJPG_ENCODE_STREAM stream
    )
{
    iljpgEnhuffPtr pHuffPriv;
    int        nHuffBits, huffBits;
    iljpgError          error;

        /*  If any bits left, flush them out.  Pad with binary 1's, and
            stuff a 0 after any 0xff, as per JPEG spec F.1.2.3 (pg F-7).
        */
    pHuffPriv = (iljpgEnhuffPtr)pPriv->pHuffPriv;
    nHuffBits = pHuffPriv->nHuffBits;
    if (nHuffBits > 0) {
        huffBits = pHuffPriv->huffBits;
        huffBits <<= (8 - nHuffBits);           /* move bits to upper bits of byte */
        huffBits |= (1 << (8 - nHuffBits)) - 1; /* or in all 1's in unused bits */
        pHuffPriv->nHuffBits = 0;               /* now no bits left to output */
        if (!ILJPG_ENCODE_PUT_BYTE (stream, huffBits, error))
            return error;                       /* write a byte */
        if (((iljpgByte)huffBits) == ((iljpgByte)0xff))
            if (!ILJPG_ENCODE_PUT_BYTE (stream, 0, error))
                return error;                   /* write a 0 after any 0xff */
        }

    return 0;
}