home *** CD-ROM | disk | FTP | other *** search
/ Altsys Virtuoso 2.0K / virtuoso_20k.iso / DemoApps / Graphics / Viewers / ViewGif2 / Source / LZWDecoder.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-26  |  12.9 KB  |  398 lines
  1. /***************************************************************************/
  2. /* LZWDecode.c - source code for LZW decoding of GIF files           */
  3. /* Used in ViewGif2 Application                           */
  4. /* This is not very elegant code, but it allows the decoding to be broken  */
  5. /* up into arbitrary pieces, thus being nice to system resources       */
  6. /* January 1990   Carl F. Sutter                       */
  7. /***************************************************************************/
  8.  
  9. #include <stdio.h>
  10. #include <streams/streams.h>
  11.  
  12. /* some global data types and constants */
  13. #define    BYTE     unsigned char
  14. #define WORD      unsigned short
  15. #define DWORD   unsigned long
  16. #define BOOL    int
  17. #define TRUE    1
  18. #define FALSE    0
  19. #define MAXCODES 4096
  20.  
  21. /* LZW variables */
  22. WORD  wCodeClear;
  23. WORD  wCodeEOI;
  24. WORD  wCodeLength;
  25. WORD  wTablePointer;
  26. WORD  wCurrentTablePointerMax;
  27.  
  28. /* LZW stack implementation */
  29. BYTE  byStack[MAXCODES];
  30. WORD  wStackPointer;
  31. WORD  wFirstCode[MAXCODES];
  32. WORD  wSecondCode[MAXCODES];
  33.  
  34. BYTE        byCodeSize;
  35. long        lNumPixelsDecoded;
  36.  
  37. /* functions in this code */
  38. void StartLZW( BYTE byCodeSizeIn, NXStream *stream,
  39.                BYTE *byR, BYTE *byG, BYTE *byB, BYTE *byMap,
  40.                int width, int height, BOOL bInter );
  41. long ContinueLZW( int nNumCodes );
  42. void InitializeLZWTable( void );
  43. BOOL ReadNextCode( BOOL bInitialize, WORD *wCode );
  44. BOOL FillStack( WORD wCode );
  45. BOOL AddToTable( WORD wFirst, WORD wSecond );
  46. WORD FirstCode( WORD wCode );
  47. BOOL IsInTable( WORD wCode, BOOL *bResult );
  48. BOOL ReadNextDataByte( NXStream *stream, BYTE *byReturn );
  49. BOOL WriteStack( BYTE byStack[], WORD *wPointer,
  50.                  BYTE *byR, BYTE *byG, BYTE *byB, BYTE *byMap,
  51.                  int width, int height, BOOL bInter );
  52.  
  53.  
  54. /***************************************************************************/
  55. /* StartLZW - handle all initialization of the LZW dedcoder           */
  56. /***************************************************************************/
  57. void StartLZW( BYTE byCodeSizeIn, NXStream *stream,
  58.                BYTE *byR, BYTE *byG, BYTE *byB, BYTE *byMap,
  59.                int width, int height, BOOL bInter )
  60.    {
  61.    /* save input parameters */
  62.    byCodeSize = byCodeSizeIn;
  63.    
  64.    /* set the constant clear and EOI codes, and the pixel count */
  65.    wCodeClear = 1;
  66.    wCodeClear <<= byCodeSize;  /* Clear Code = 2^CodeSize */
  67.    wCodeEOI = wCodeClear + 1;
  68.    lNumPixelsDecoded = 0;
  69.  
  70.    /* initialize the following functions */
  71.    ReadNextCode( TRUE, NULL );
  72.    ReadNextDataByte( stream, NULL );
  73.    WriteStack( NULL, NULL, byR, byG, byB, byMap, width, height, bInter );
  74.  
  75.    /* set the LZW values in case the first code is not a clear code */
  76.    InitializeLZWTable();
  77.    } /* StartLZW 1/24/90 CFS */
  78.    
  79.  
  80. /***************************************************************************/
  81. /* ContinueLZW - keep decoding the LZW encoded data stream                 */
  82. /***************************************************************************/
  83. long ContinueLZW( int nNumCodes )
  84.    {
  85.    static WORD    wCode, wOldCode;
  86.    int        nNumCodesRead;
  87.    BOOL        bInTable;
  88.  
  89.    nNumCodesRead = 0;
  90.    while ( (nNumCodesRead < nNumCodes) && (ReadNextCode( FALSE, &wCode )) &&
  91.            (wCode != wCodeEOI) )
  92.       {
  93.       nNumCodesRead++;
  94.       if (wCode == wCodeClear)
  95.        {
  96.        InitializeLZWTable();
  97.          if (!ReadNextCode( FALSE, &wCode )) break;
  98.        if (wCode == wCodeEOI) break;
  99.          nNumCodesRead++;
  100.        if (!FillStack( wCode )) break;
  101.        }
  102.       else /* not clear code */
  103.        {
  104.        if (!IsInTable( wCode, &bInTable )) break;
  105.        if (bInTable)
  106.           {
  107.           if (!FillStack( wCode )) break;
  108.           if (!AddToTable( wOldCode, FirstCode( wCode ) )) break;
  109.           }
  110.        else /* code is not in table */
  111.           {
  112.           if (!FillStack( wOldCode )) break;
  113.           if (!FillStack( FirstCode( wOldCode ) )) break;
  114.           if (!AddToTable( wOldCode, FirstCode( wOldCode ) )) break;
  115.           }
  116.        } /* not clear code */
  117.       wOldCode = wCode;
  118.       } /* while loop */
  119.    
  120.    /* return value depends on clean codes up to EOI */
  121.    /* note: even if errors were found, some of the image may be OK */
  122.    if (wCode == wCodeEOI) return( 0 );
  123.    if (nNumCodesRead == nNumCodes) return( lNumPixelsDecoded );
  124.    /* else something went wrong, signal caller to quit */
  125.    return( -1 );   
  126.    } /* LZWDecode 10/16/89 CFS */
  127.    
  128.    
  129. /***************************************************************************/
  130. /* InitializeLZWTable - init the table and global pointers and counters    */
  131. /***************************************************************************/
  132. void InitializeLZWTable( void )
  133.    {
  134.    wCodeLength = byCodeSize + 1;
  135.    wCurrentTablePointerMax = 1;              /* wCurrentTablePointer =   */
  136.    wCurrentTablePointerMax <<= wCodeLength;  /* 2^wCodeLength            */
  137.    wTablePointer = wCodeEOI + 1;
  138.    } /* InitializeLZWTable 10/5/89 CFS */
  139.  
  140.  
  141. /***************************************************************************/
  142. /* ReadNextCode - get the next LZW code from the file                      */
  143. /***************************************************************************/
  144. BOOL ReadNextCode( BOOL bInitialize, WORD *wCode )
  145.    {
  146.    static WORD    wMask[] = { 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F,
  147.                 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF };
  148.    static DWORD    dwStorage;
  149.    static BYTE    byBitsAvail;
  150.    WORD        wNextCode;
  151.    BYTE        byNextByte;
  152.    
  153.    /* initialize if requested */
  154.    if (bInitialize == TRUE)
  155.       {
  156.       dwStorage = 0;
  157.       byBitsAvail = 0;
  158.       return( TRUE );
  159.       }
  160.  
  161.    /* get enough data in the storage variable to handle the request */
  162.    while ((WORD)byBitsAvail < wCodeLength)
  163.       {
  164.       if (!ReadNextDataByte( NULL, &byNextByte )) return( FALSE );
  165.       dwStorage |= (DWORD)byNextByte << (DWORD)byBitsAvail;
  166.       byBitsAvail += 8;
  167.       }
  168.  
  169.    /* now get the bits for the new code, and shift out the used bits */
  170.    wNextCode = (WORD)(dwStorage & (DWORD)wMask[wCodeLength - 1]);
  171.    dwStorage >>= (DWORD)wCodeLength;
  172.    byBitsAvail -= (BYTE)wCodeLength;
  173.    *wCode = wNextCode;
  174.    return( TRUE );
  175.    } /* ReadNextCode 10/5/89 CFS */
  176.  
  177.  
  178. /***************************************************************************/
  179. /* FillStack - start with the given code, and put colors on the stack      */
  180. /***************************************************************************/
  181. BOOL FillStack( WORD wCode )
  182.    {
  183.    wStackPointer = 0;
  184.  
  185.    /* check first whether the code is just a pixel color */
  186.    if (wCode < wCodeClear)
  187.       byStack[wStackPointer++] = (BYTE)wCode;
  188.       
  189.    /* make sure the code is in a valid range */
  190.    else if ((wCode <= wCodeEOI) || (wCode >= wTablePointer))
  191.       {
  192.       fprintf( stderr,
  193.          "ViewGif LZWDecode error - FillStack code is not a valid table entry.\n" );
  194.       return( FALSE );
  195.       }
  196.  
  197.    /* the code is from the table, trace the codes and collect pixels */
  198.    else 
  199.       {
  200.       while (wFirstCode[wCode] > wCodeClear)
  201.          {
  202.          byStack[wStackPointer++] = (BYTE)wSecondCode[wCode];
  203.          wCode = wFirstCode[wCode];
  204.          }
  205.       byStack[wStackPointer++] = (BYTE)wSecondCode[wCode];
  206.       byStack[wStackPointer++] = (BYTE)wFirstCode[wCode];
  207.       }
  208.    
  209.    /* all went well, so pop the stack of pixels into the bitmap buffers */
  210.    return( WriteStack( byStack, &wStackPointer,
  211.                        (BYTE *)NULL, (BYTE *)NULL, (BYTE *)NULL, (BYTE *)NULL,
  212.                (int)NULL, (int)NULL, (BOOL)NULL ) );
  213.    } /* FillStack 10/6/89 CFS */
  214.  
  215.  
  216. /***************************************************************************/
  217. /* AddToTable - add the code to the tables                                 */
  218. /***************************************************************************/
  219. BOOL AddToTable( WORD wFirst, WORD wSecond )
  220.    {
  221.    /* save data at the wTablePointer location */
  222.    wFirstCode[wTablePointer] = wFirst;
  223.    wSecondCode[wTablePointer] = wSecond;
  224.  
  225.    /* increment the table pointer */
  226.    wTablePointer++;
  227.    if (wTablePointer > MAXCODES)
  228.       {
  229.       fprintf( stderr, "ViewGif LZWDecode error - LZW table up to 4095\n" );
  230.       return( FALSE );
  231.       }
  232.  
  233.    /* if the table pointer is about to exceed the code length, up it */
  234.    if (wTablePointer == wCurrentTablePointerMax)
  235.       {
  236.       if (wCodeLength < 12) wCodeLength += 1;
  237.       wCurrentTablePointerMax = 1;              /* wCurrentTablePointer =   */
  238.       wCurrentTablePointerMax <<= wCodeLength;  /* 2^wCodeLength            */
  239.       }
  240.       
  241.    return( TRUE );
  242.    } /* AddToTable 10/6/89 CFS */
  243.  
  244.  
  245. /***************************************************************************/
  246. /* FirstCode - trace the code back to it's first pixel color               */
  247. /***************************************************************************/
  248. WORD FirstCode( WORD wCode )
  249.    {
  250.    /* check first whether the code is just a pixel color */
  251.    if (wCode < wCodeClear) return( wCode );
  252.  
  253.    /* if not, trace back the first codes until it is a color */
  254.    while (wFirstCode[wCode] > wCodeClear)
  255.       wCode = wFirstCode[wCode];
  256.    return( wFirstCode[wCode] );
  257.    } /* FirstCode 10/5/89 CFS */
  258.  
  259.  
  260. /***************************************************************************/
  261. /* IsInTable - return true if the code is a pixel color, or in the table   */
  262. /***************************************************************************/
  263. BOOL IsInTable( WORD wCode, BOOL *bResult )
  264.    {
  265.    /* check first whether the code is just a pixel color */
  266.    if (wCode < wCodeClear)
  267.       {
  268.       *bResult = TRUE;
  269.       return( TRUE );
  270.       }
  271.  
  272.    /* make sure the code is not a special one, or bigger than the */
  273.    /* next table entry */
  274.    if ((wCode <= wCodeEOI) || (wCode > wTablePointer))
  275.       {
  276.       fprintf( stderr,
  277.          "ViewGif LZWDecode error - IsInTable code is not a valid table entry.\n" );
  278.       return( FALSE );
  279.       }
  280.  
  281.    /* if the code will be the next table entry, OK, but return false */
  282.    if (wCode == wTablePointer)
  283.       {
  284.       *bResult = FALSE;
  285.       return( TRUE );
  286.       }
  287.  
  288.    /* finally, the code must be already in the table  EOI < code < TP */
  289.    *bResult = TRUE;
  290.    return( TRUE );
  291.    } /* IsInTable 10/5/89 CFS */
  292.    
  293.   
  294. /***************************************************************************/
  295. /* ReadNextDataByte - get the next image data byte from the file           */
  296. /***************************************************************************/
  297. BOOL ReadNextDataByte( NXStream *stream, BYTE *byReturn )
  298.    {
  299.    #define        MAX_BLOCK_SIZE 255
  300.    static BYTE         byBlockSize = 0;
  301.    static BYTE        byData[MAX_BLOCK_SIZE];
  302.    static NXStream    *fileStream;
  303.    static BYTE        byLeft;
  304.    int            nError;
  305.  
  306.    /* if the stream is not NULL, initialize this function */
  307.    if (stream != NULL)
  308.       {
  309.       byLeft = 0;
  310.       fileStream = stream;
  311.       return( TRUE );
  312.       }
  313.       
  314.    /* get the next block of data if necessary */
  315.    if (byLeft == 0)
  316.       {
  317.       nError = NXRead( fileStream, &byBlockSize, 1 );
  318.       if (nError <= 0)
  319.          {
  320.          fprintf( stderr,
  321.             "ViewGif2 LZWDecode error - ReadNextDataByte unexpected end of file.\n" );
  322.          return( FALSE );
  323.      }
  324.       byLeft = byBlockSize;
  325.       nError = NXRead( fileStream, byData, byBlockSize );
  326.       if (nError <= 0)
  327.          {
  328.          fprintf( stderr,
  329.             "ViewGif2 LZWDecode error - ReadNextDataByte unexpected end of file.\n" );
  330.      return( FALSE );
  331.      }
  332.       }
  333.    /* return the data byte and decrement the number left */
  334.    *byReturn = byData[byBlockSize - byLeft--];
  335.    return( TRUE );
  336.    } /* ReadNextDataByte 10/16/89 CFS */
  337.  
  338.  
  339. /***************************************************************************/
  340. /* WriteStack - pop the pixel stack and color in the pixels                */
  341. /***************************************************************************/
  342. BOOL WriteStack( BYTE byStack[], WORD *wPointer,
  343.                  BYTE *byR, BYTE *byG, BYTE *byB, BYTE *byMap,
  344.                  int width, int height, BOOL bInter )
  345.    {
  346.    static int        nLines[] = { 0, 4, 2, 1 };
  347.    static int        nJump[] =  { 8, 8, 4, 2 };
  348.    int            nColorIndex;
  349.    DWORD        dwDataIndex;
  350.  
  351.    static BYTE        *byDataR, *byDataG, *byDataB;
  352.    static BYTE        *byColorMap;
  353.    static int        nWidth, nHeight;
  354.    static BOOL        bInterlaced;
  355.    static DWORD        dwCurX, dwCurY;
  356.    static int        nCurInterlace;
  357.    
  358.    /* initialize the function if the stack is NULL */
  359.    if (byStack == NULL)
  360.       {
  361.       byDataR = byR;  byDataG = byG;  byDataB = byB;
  362.       byColorMap = byMap;
  363.       nWidth = width;  nHeight = height;
  364.       bInterlaced = bInter;
  365.       dwCurX = dwCurY = 0;
  366.       nCurInterlace = 0;
  367.       return( TRUE );
  368.       }
  369.  
  370.    while (*wPointer > 0)
  371.       {
  372.       (*wPointer)--;
  373.       lNumPixelsDecoded++;
  374.  
  375.       /* put the pixel color in the data arrays */
  376.       nColorIndex = (int)byStack[*wPointer] * 3;
  377.       dwDataIndex = dwCurY * (long)nWidth + dwCurX;
  378.       byDataR[dwDataIndex] = byColorMap[  nColorIndex];
  379.       byDataG[dwDataIndex] = byColorMap[++nColorIndex];
  380.       byDataB[dwDataIndex] = byColorMap[++nColorIndex];
  381.  
  382.       /* increment the counters */
  383.       if (++dwCurX == nWidth)
  384.          {
  385.          dwCurX = 0;
  386.          if (bInterlaced)
  387.         {
  388.         dwCurY += nJump[nCurInterlace];
  389.         if (dwCurY>=nHeight)
  390.            dwCurY = nLines[++nCurInterlace];
  391.         }
  392.      else dwCurY++;
  393.      }
  394.       }
  395.    return( TRUE );
  396.    } /* WriteStack 10/16/89 CFS */
  397.  
  398.