home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Web / Utilities / wwwcount-2.3 / combine / lzwdec.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-19  |  5.2 KB  |  228 lines
  1. #include "combine.h"
  2. #include "defines.h"
  3. #include "errcds.h"
  4.  
  5. /*
  6. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  7. %                                                                             %
  8. %                                                                             %
  9. %                                                                             %
  10. %   L Z W D e c o d e I m a g e                                               %
  11. %                                                                             %
  12. %                                                                             %
  13. %                                                                             %
  14. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  15. %
  16. %  Function LZWDecodeImage uncompresses an image via LZW-coding.
  17. %
  18. %  The format of the LZWDecodeImage routine is:
  19. %
  20. %      status=LZWDecodeImage(image)
  21. %
  22. %  A description of each parameter follows:
  23. %
  24. %    o status:  Function LZWDecodeImage returns True if all the pixels are
  25. %      uncompressed without error, otherwise False.
  26. %
  27. %    o image: The address of a structure of type Image.
  28. %
  29. %
  30. */
  31. int LZWDecodeImage(image)
  32. Image
  33.   *image;
  34. {
  35. #define MaxStackSize  4096
  36. #define NullCode  (-1)
  37.  
  38.   int
  39.     available,
  40.     clear,
  41.     code_mask,
  42.     code_size,
  43.     end_of_information,
  44.     in_code,
  45.     old_code,
  46.     status;
  47.  
  48.   register int
  49.     bits,
  50.     code,
  51.     count,
  52.     i;
  53.  
  54.   register Runlength
  55.     *p;
  56.  
  57.   register unsigned char
  58.     *c;
  59.  
  60.   register unsigned int
  61.     datum;
  62.  
  63.   short
  64.     *prefix;
  65.  
  66.   unsigned char
  67.     data_size,
  68.     first,
  69.     *packet,
  70.     *pixel_stack,
  71.     *suffix,
  72.     *top_stack;
  73.   int
  74.     rc = 0;
  75.  
  76.   /*
  77.     Allocate decoder tables.
  78.   */
  79.   packet=(unsigned char *) malloc(256*sizeof(unsigned char));
  80.   prefix=(short *) malloc(MaxStackSize*sizeof(short));
  81.   suffix=(unsigned char *) malloc(MaxStackSize*sizeof(unsigned char));
  82.   pixel_stack=(unsigned char *) malloc((MaxStackSize+1)*sizeof(unsigned char));
  83.   if ((packet == (unsigned char *) NULL) ||
  84.       (prefix == (short *) NULL) ||
  85.       (suffix == (unsigned char *) NULL) ||
  86.       (pixel_stack == (unsigned char *) NULL))
  87.     return(MALLOC_FAILED);
  88.   /*
  89.     Initialize LZW data stream decoder.
  90.   */
  91.   data_size=fgetc(image->fp);
  92.   clear=1 << data_size;
  93.   end_of_information=clear+1;
  94.   available=clear+2;
  95.   old_code=NullCode;
  96.   code_size=data_size+1;
  97.   code_mask=(1 << code_size)-1;
  98.   for (code=0; code < clear; code++)
  99.   {
  100.     prefix[code]=0;
  101.     suffix[code]=code;
  102.   }
  103.   /*
  104.     Decode LZW pixel stream.
  105.   */
  106.   datum=0;
  107.   bits=0;
  108.   c=0;
  109.   count=0;
  110.   first=0;
  111.   top_stack=pixel_stack;
  112.   p=image->pixels;
  113.   for (i=0; i < image->packets; )
  114.   {
  115.     if (top_stack == pixel_stack)
  116.       {
  117.         if (bits < code_size)
  118.           {
  119.             /*
  120.               Load bytes until there is enough bits for a code.
  121.             */
  122.             if (count == 0)
  123.               {
  124.                 /*
  125.                   Read a new data block.
  126.                 */
  127.                 count=ReadDataBlock((char *) packet,image->fp);
  128.                 if (count <= 0)
  129.                   break;
  130.                 c=packet;
  131.               }
  132.             datum+=(*c) << bits;
  133.             bits+=8;
  134.             c++;
  135.             count--;
  136.             continue;
  137.           }
  138.         /*
  139.           Get the next code.
  140.         */
  141.         code=datum & code_mask;
  142.         datum>>=code_size;
  143.         bits-=code_size;
  144.         /*
  145.           Interpret the code
  146.         */
  147.         if ((code > available) || (code == end_of_information))
  148.           break;
  149.         if (code == clear)
  150.           {
  151.             /*
  152.               Reset decoder.
  153.             */
  154.             code_size=data_size+1;
  155.             code_mask=(1 << code_size)-1;
  156.             available=clear+2;
  157.             old_code=NullCode;
  158.             continue;
  159.           }
  160.         if (old_code == NullCode)
  161.           {
  162.             *top_stack++=suffix[code];
  163.             old_code=code;
  164.             first=code;
  165.             continue;
  166.           }
  167.         in_code=code;
  168.         if (code == available)
  169.           {
  170.             *top_stack++=first;
  171.             code=old_code;
  172.           }
  173.         while (code > clear)
  174.         {
  175.           *top_stack++=suffix[code];
  176.           code=prefix[code];
  177.         }
  178.         first=suffix[code];
  179.         /*
  180.           Add a new string to the string table,
  181.         */
  182.         if (available >= MaxStackSize)
  183.           break;
  184.         *top_stack++=first;
  185.         prefix[available]=old_code;
  186.         suffix[available]=first;
  187.         available++;
  188.         if (((available & code_mask) == 0) && (available < MaxStackSize))
  189.           {
  190.             code_size++;
  191.             code_mask+=available;
  192.           }
  193.         old_code=in_code;
  194.       }
  195.     /*
  196.       Pop a pixel off the pixel stack.
  197.     */
  198.     top_stack--;
  199.     p->index=(unsigned short) *top_stack;
  200.     p->length=0;
  201.     p++;
  202.     i++;
  203.   }
  204.   /*
  205.     Initialize any remaining color packets to a known color.
  206.   */
  207.   status=i == image->packets;
  208.   if (status == False)
  209.   {
  210.     rc=1;
  211.   }
  212.   for ( ; i < image->packets; i++)
  213.   {
  214.     p->index=0;
  215.     p->length=0;
  216.     p++;
  217.   }
  218.   SyncImage(image);
  219.   /*
  220.     Free decoder memory.
  221.   */
  222.   (void) free((char *) pixel_stack);
  223.   (void) free((char *) suffix);
  224.   (void) free((char *) prefix);
  225.   (void) free((char *) packet);
  226.   return(rc);
  227. }
  228.