/*
 * 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: ildecomplzw.c /main/5 1996/06/19 12:23:35 ageorge $ */
/**---------------------------------------------------------------------
***	
***    (c)Copyright 1991 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 <stdlib.h>

#include "ilint.h"
#include "ilpipelem.h"
#include "ildecomp.h"
#include "ilerrors.h"



/* ========================================================================
   Local definitions
   ======================================================================== */

#define     CLEAR_CODE          256
#define     END_OF_INFORMATION  257
#define     MAX_NODES           0x1000
#define     OKAY                1



/* ========================================================================
   Decompression private data type declaration
   ======================================================================== */

typedef struct {                            /* decode node structure       */
    unsigned short      value;              /* byte value of node          */
    short               previous;           /* previous string node index  */
    } ilDenodeRec, *ilDenodePtr;

typedef struct {                            /* private image information   */
    ilDenodePtr         denodes;            /* table/tree for decode nodes */
    ilPtr               pString;            /* ptr to string table */
    unsigned long       length;             /* number of bytes read        */
    unsigned int        nextNode;           /* next node to be used        */
    unsigned long       nDstLineBytes;      /* width of dst in bytes       */
    } ilDecompPrivRec, *ilDecompPrivPtr;


/* ========================================================================    
             
     -------------------- ilDecompLZWInit/Cleanup -------------------
        Allocate / deallocate buffers for LZW decompression.
   ======================================================================== */

static ilError ilDecompLZWInit(
    ilDecompPrivPtr  pPriv,
    ilImageInfo     *pSrcImage,
    ilImageInfo     *pDstImage
    )
{
    pPriv->denodes = (ilDenodePtr)NULL;
    pPriv->pString = (ilPtr)IL_MALLOC (MAX_NODES);
    if (!pPriv->pString) 
        return IL_ERROR_MALLOC;

    pPriv->denodes = (ilDenodePtr)IL_MALLOC (sizeof(ilDenodeRec) * MAX_NODES);
    if (!pPriv->denodes) {
        IL_FREE (pPriv->pString);
        pPriv->pString = (ilPtr)NULL;
        return IL_ERROR_MALLOC;
	    }

    return IL_OK;
}


static ilError ilDecompLZWCleanup (
    ilDecompPrivPtr  pPriv,
    ilBool           aborting
    )
{
    if (pPriv->pString) 
        IL_FREE (pPriv->pString);
    if (pPriv->denodes) 
        IL_FREE ((ilPtr)pPriv->denodes);
    return IL_OK;
}


/* ========================================================================    
             
        -------------------- ilCurrentBitsRead( ) -------------------
   Returns the number of bits per code word for the next node in the tree.

   ======================================================================== */

static int ilCurrentBitsRead (
    ilDecompPrivPtr pPriv
    )
{
    int   retval;
    int   node;

    node = pPriv->nextNode + 2;
    if (node <= (512 - 2)) retval = 9;
 
    else {
        if (node <= (1024 - 2)) retval = 10;
        else {
            if (node <= (2048 - 2)) retval = 11;
            else retval = 12;
        }
    }
    return retval;
}
/* End ilCurrentBitsRead() */



/* ========================================================================    

           -------------------- ilStringFromCode --------------------
   Using the code as the starting node in the decode tree this routine
   builds the string by traversing backwards up the tree.

   ======================================================================== */

static void ilStringFromCode(
    ilDecompPrivPtr     pPriv,
    unsigned int        code,       /* Code to look for string with.                    */
    ilPtr               pString,    /* Pointer to value for the length of the string    */
    unsigned int       *pcount      /* Pointer to location to place string at in memory */
    )

{
    unsigned int  index;
    int           node;
    ilDenodePtr   denodes = pPriv->denodes;

    if (code > 255) node = code - 2;    /* remove for extra codes */
    else node = code;
    index = 0;                          /* start at end of string */

    while (node != -1) {                /* build string backwards */
        pString[index++] = denodes[node].value;
        node = denodes[node].previous;
        }
    *pcount = index;
}




/* ========================================================================    

          -------------------- ilAddStringToTable --------------------
   Adds a new node to the decode table and links it back to the last code
   for the current string.
   ======================================================================== */

static void ilAddStringToTable (
    ilDecompPrivPtr pPriv,
    unsigned int    code,       /* Code for previous entry in table */ 
    unsigned char   khar        /* Value for new node               */               
    )

{
    ilDenodePtr   denodes = pPriv->denodes;

    denodes[pPriv->nextNode].value = khar;
    if (code < 256) denodes[pPriv->nextNode].previous = code;
    else denodes[pPriv->nextNode].previous = code - 2;
    pPriv->nextNode++;
}



/* ========================================================================    

       --------------------ilInitializeDecodeTable --------------------
      Allocates the decode table.  Initializes the table with the first 
      256 entries.

   ======================================================================== */

static ilError ilInitializeDecodeTable (
    ilDecompPrivPtr pPriv
    )
{
    unsigned int    i;
	
    for (i = 0;i < 256;i++) {
        pPriv->denodes[i].value = i;
        pPriv->denodes[i].previous = -1;
        }
    pPriv->nextNode = 256;
	
    for (i = 256;i < MAX_NODES;i++) {
        pPriv->denodes[i].value = 0;
        pPriv->denodes[i].previous = -1;
        }
    return IL_OK;
}


/* ========================================================================    

        -------------------- ilDecompLZWExecute() -------------------
    Routine defined in ilDecompLZW for executing LZW 
    decompression when the pipe gets executed.

   ======================================================================== */

static ilError ilDecompLZWExecute(
    ilExecuteData           *pData,
    unsigned long            dstLine,
    unsigned long           *pNLines
    )
{

/* ========================================================================
   ilDecompLZWExecute() definitions
   ======================================================================== */

    /*  Macro which returns whether a clear code exists at *_pByte: a clear code
        is 9 bits, = 256, or 0x80 in first byte and a zero in the upper bit of the next.
        Each strip must begin with a clear code; at end of strip, a search-ahead
        is done for the next clear code.
    */
#define IS_CLEAR_CODE(_pByte) ( (*(_pByte) == 0x80) && ((*(_pByte+1) & 0x80) == 0) )

    /* My defines */
    unsigned long       dstNBytes;              /* Number of destination image bytes per row                     */                    
    long                nLines;                 /* Number of lines per source image strip                        */  
    long                nBytesToGo;             /* Number of source image bytes left to unpack for current strip */  
    long                nDstLineBytesToGo;      /* Number of bytes left to write to this line of destination     */
    ilPtr      pSrcByte;               /* Pointer to source image data                                  */
    ilPtr      pDstByte;               /* Pointer to destination image data first byte                  */
    ilPtr               pSrcStart;              /* Pointer to initial src (comp) byte                            */
    ilPtr               pDstLine;               /* Pointer to destination image data first byte of each scanline */  
    ilDecompPrivPtr pPriv;             /* Pointer to private image data                                 */
    ilImagePlaneInfo   *pPlane;

    /* Greeley defines */
    unsigned int bitCount;
    unsigned int        numBits;
/* compatibility problem with long and unsigned long data fields */
    CARD32              bits;
    long                k;
    unsigned int code;
    unsigned int        oldCode = 0;
    unsigned int        stringCount = 0;
    ilError             status      = IL_OK;
    ilPtr               pString;
	

/* ========================================================================
   ilDecompLZWExecute() set up for decompression algorithm code           
   ======================================================================== */

    pPriv = (ilDecompPrivPtr)pData->pPrivate;
    nLines = *pNLines;
    if (nLines <= 0)    
        return IL_OK; 

    nBytesToGo = pData->compressed.nBytesToRead;   
    if (nBytesToGo <= 0)    
        return IL_OK; 

    pPlane = &pData->pSrcImage->plane[0];
    if (!pPlane->pPixels) return IL_ERROR_NULL_COMPRESSED_IMAGE;
    pSrcStart = pPlane->pPixels + pData->compressed.srcOffset; 
    pSrcByte = pSrcStart;

    pPlane = &pData->pDstImage->plane[0];
    dstNBytes = pPlane->nBytesPerRow;         
    pDstLine  = pPlane->pPixels + dstLine * dstNBytes;   


/* ========================================================================
   ilDecompLZWExecute() decompression algorithm code
   ======================================================================== */

    /* get ptr to 4k string buffer */
    pString = pPriv->pString;

    /* decode each line of compressed data into the destination image */
    pPriv->length   = 0;
    pPriv->nextNode = 256;    /* set to keep ref in ReadCode() call to CurrentBits2() from bombing */
    bits            = 0;
    bitCount        = 0;

        /*  Each strip must begin with a clear code; error if not. */
    if (!IS_CLEAR_CODE (pSrcByte))
        return IL_ERROR_COMPRESSED_DATA;

    while (nLines-- > 0)  {
        pDstByte          = pDstLine;
        pDstLine         += dstNBytes;
        nDstLineBytesToGo = pPriv->nDstLineBytes;

        while (nDstLineBytesToGo > 0) {

            if (stringCount == 0) {                         /* get another string */

/*  BEGIN ReadCode */
                if (bitCount < 16) {                        /* Get next byte(s) of encoded source image data */
                    if (--nBytesToGo < 0)
                        return IL_ERROR_COMPRESSED_DATA;
                    if (--nBytesToGo < 0) {
                        bits |= (*pSrcByte++ << (24 - bitCount));
                        bitCount += 8;
                        }
                    else {
                        bits |= (*pSrcByte++ << (24 - bitCount));
                        bits |= (*pSrcByte++ << (16 - bitCount));
                        bitCount += 16;
                        }
                    }
                numBits   = ilCurrentBitsRead (pPriv);
                code      = (unsigned short)(bits >> (32 - numBits));
                bits    <<= numBits;
                bitCount -= numBits;
/*  END ReadCode */

                if (code == END_OF_INFORMATION) 
                    goto xit;                               /* done, EXIT */
				
                if (code == CLEAR_CODE) {
                    if ((status = ilInitializeDecodeTable (pPriv)) != IL_OK) goto xit;

/*  BEGIN ReadCode */
                if (bitCount < 16) {                        /* Get next byte(s) of encoded source image data */
                    if (--nBytesToGo < 0)
                        return IL_ERROR_COMPRESSED_DATA;
                    if (--nBytesToGo < 0) {
                        bits |= (*pSrcByte++ << (24 - bitCount));
                        bitCount += 8;
                        }
                    else {
                        bits |= (*pSrcByte++ << (24 - bitCount));
                        bits |= (*pSrcByte++ << (16 - bitCount));
                        bitCount += 16;
                        }
                    }
                numBits   = ilCurrentBitsRead (pPriv);
                code      = (bits >> (32 - numBits));
                bits    <<= numBits;
                bitCount -= numBits;
/*  END ReadCode */

                    if (code == END_OF_INFORMATION) goto xit;
                    ilStringFromCode (pPriv, code, pString, &stringCount);
                    oldCode = code;
                }
                else {

                    if ((code < 256) || ((code - 2) < pPriv->nextNode)) {     /* code is in table */
                        ilStringFromCode (pPriv, code, pString, &stringCount);
                        ilAddStringToTable (pPriv, oldCode, pString[stringCount - 1]);
                        oldCode = code;
                    }

                    else {
                        ilStringFromCode (pPriv, oldCode, pString, &stringCount);
     
                        for (k = stringCount - 1; k >= 0; k--) pString[k + 1] = pString[k];
                        pString[0] = pString[stringCount];
                        stringCount++;
                        ilAddStringToTable (pPriv, oldCode, pString[0]);
                        oldCode = code;
                    }
                }
            }

                /*  Store one byte, subtract line byte count */
            *pDstByte++ = pString[--stringCount];
            nDstLineBytesToGo--;
        }
    }

xit:	
    return status;
}
  

/* ========================================================================

        -------------------- ilDecompLZW() --------------------
    Code entry point for LZW decompression.  This includes image descriptor
    parameter error checking and function calls for: strip handler
    initialization, adding the filter element to the pipe, pipe
    initialization, execution and destruction, decompression algorithm.....

   ======================================================================== */

IL_PRIVATE ilBool _ilDecompLZW (
    ilPipe              pipe,
    ilPipeInfo         *pinfo,                              
    ilImageDes         *pimdes,
    ilImageFormat      *pimformat
    )

{
    ilDstElementData    dstdata;
    ilDecompPrivPtr     pPriv;
    ilImageDes          des;
    ilImageFormat       format;
    long                bytesPerRow [IL_MAX_SAMPLES];

    dstdata.producerObject  =  (ilObject) NULL;
    des                     = *pimdes;
    des.compression         =  IL_UNCOMPRESSED;
    dstdata.pDes            =  &des;
    format                  = *pimformat;
    format.rowBitAlign      = (format.nBitsPerSample[0] == 1) ? 32 : 8;
    dstdata.pFormat         =  &format;
    dstdata.width           =  pinfo->width;
    dstdata.height          =  pinfo->height;
    dstdata.pPalette        =  pinfo->pPalette;
    dstdata.stripHeight     =  pinfo->stripHeight;
    dstdata.constantStrip   =  pinfo->constantStrip;

    pPriv = (ilDecompPrivPtr) ilAddPipeElement(pipe, IL_FILTER, sizeof(ilDecompPrivRec), 0,
                    (ilSrcElementData *)NULL, &dstdata, 
                    ilDecompLZWInit, ilDecompLZWCleanup, IL_NPF, ilDecompLZWExecute, NULL, 0);
    if (!pPriv) return FALSE;

        /*  Store info in *pPriv.  For nDstLineBytes, need minimum # of bytes uncompressed
            dst data would take - get bytes/row using rowBitAlign of 8 (packed).
        */
    format.rowBitAlign = 8;
    ilGetBytesPerRow (pimdes, &format, pinfo->width, bytesPerRow);
    pPriv->nDstLineBytes = bytesPerRow[0];

    return TRUE;
}

