home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Web / Utilities / wwwcount-2.3 / combine / lzwenc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-02  |  6.2 KB  |  278 lines
  1. /*
  2.  *    LZWEncodeImage()    -    description
  3.  *
  4.  *    RCS:
  5.  *        $Revision: 2.3 $
  6.  *        $Date: 1996/05/03 02:21:34 $
  7.  *
  8.  *    Security:
  9.  *        Unclassified
  10.  *
  11.  *    Description:
  12.  *        Taken from ImageMagick 3.3
  13.  *
  14.  *    Input Parameters:
  15.  *        type    identifier    description
  16.  *
  17.  *        text
  18.  *
  19.  *    Output Parameters:
  20.  *        type    identifier    description
  21.  *
  22.  *        text
  23.  *
  24.  *    Return Values:
  25.  *        value    description
  26.  *
  27.  *    Side Effects:
  28.  *        text
  29.  *
  30.  *    Limitations and Comments:
  31.  *        text
  32.  *
  33.  *    Development History:
  34.  *        when    who        why
  35.  */
  36. /*
  37. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  38. %                                                                             %
  39. %                                                                             %
  40. %                                                                             %
  41. %   L Z W E n c o d e I m a g e                                               %
  42. %                                                                             %
  43. %                                                                             %
  44. %                                                                             %
  45. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  46. %
  47. %  Function LZWEncodeImage compresses an image via LZW-coding.
  48. %
  49. %  The format of the LZWEncodeImage routine is:
  50. %
  51. %      status=LZWEncodeImage(image,data_size)
  52. %
  53. %  A description of each parameter follows:
  54. %
  55. %    o status:  Function LZWEncodeImage returns True if all the pixels are
  56. %      compressed without error, otherwise False.
  57. %
  58. %    o image: The address of a structure of type Image.
  59. %
  60. %
  61. */
  62.  
  63. #include "combine.h"
  64. #include "defines.h"
  65.  
  66. unsigned int LZWEncodeImage(image,data_size)
  67. Image
  68.   *image;
  69.  
  70. unsigned int
  71.   data_size;
  72. {
  73. #define MaxCode(number_bits)  ((1 << (number_bits))-1)
  74. #define MaxHashTable  5003
  75. #define MaxLZWBits  12
  76. #define MaxLZWTable  (1 << MaxLZWBits)
  77. #define LZWOutputCode(code) \
  78. { \
  79.   /*  \
  80.     Emit a code. \
  81.   */ \
  82.   if (bits > 0) \
  83.     datum|=((long) code << bits); \
  84.   else \
  85.     datum=(long) code; \
  86.   bits+=number_bits; \
  87.   while (bits >= 8)  \
  88.   { \
  89.     /*  \
  90.       Add a character to current packet. \
  91.     */ \
  92.     packet[byte_count++]=(unsigned char) (datum & 0xff); \
  93.     if (byte_count >= 254) \
  94.       { \
  95.         (void) fputc(byte_count,image->fp); \
  96.         (void) fwrite((char *) packet,1,byte_count,image->fp); \
  97.         byte_count=0; \
  98.       } \
  99.     datum>>=8; \
  100.     bits-=8; \
  101.   } \
  102.   if (free_code > max_code)  \
  103.     { \
  104.       number_bits++; \
  105.       if (number_bits == MaxLZWBits) \
  106.         max_code=MaxLZWTable; \
  107.       else \
  108.         max_code=MaxCode(number_bits); \
  109.     } \
  110. }
  111.  
  112.   int
  113.     bits,
  114.     byte_count,
  115.     next_pixel,
  116.     number_bits;
  117.  
  118.   long
  119.     datum;
  120.  
  121.   register int
  122.     displacement,
  123.     i,
  124.     j;
  125.  
  126.   register Runlength
  127.     *p;
  128.  
  129.   short
  130.     clear_code,
  131.     end_of_information_code,
  132.     free_code,
  133.     *hash_code,
  134.     *hash_prefix,
  135.     index,
  136.     max_code,
  137.     waiting_code;
  138.  
  139.   unsigned char
  140.     *packet,
  141.     *hash_suffix;
  142.  
  143.   /*
  144.     Uncompress image.
  145.   */
  146.   if (!UncompressImage(image))
  147.     return(False);
  148.   /*
  149.     Allocate encoder tables.
  150.   */
  151.   packet=(unsigned char *) malloc(256*sizeof(unsigned char));
  152.   hash_code=(short *) malloc(MaxHashTable*sizeof(short));
  153.   hash_prefix=(short *) malloc(MaxHashTable*sizeof(short));
  154.   hash_suffix=(unsigned char *) malloc(MaxHashTable*sizeof(unsigned char));
  155.   if ((packet == (unsigned char *) NULL) || (hash_code == (short *) NULL) ||
  156.       (hash_prefix == (short *) NULL) ||
  157.       (hash_suffix == (unsigned char *) NULL))
  158.     return(False);
  159.   /*
  160.     Initialize LZW encoder.
  161.   */
  162.   number_bits=data_size;
  163.   max_code=MaxCode(number_bits);
  164.   clear_code=((short) 1 << (data_size-1));
  165.   end_of_information_code=clear_code+1;
  166.   free_code=clear_code+2;
  167.   byte_count=0;
  168.   datum=0;
  169.   bits=0;
  170.   for (i=0; i < MaxHashTable; i++)
  171.     hash_code[i]=0;
  172.   LZWOutputCode(clear_code);
  173.   /*
  174.     Encode pixels.
  175.   */
  176.   p=image->pixels;
  177.   waiting_code=p->index;
  178.   for (i=1; i < (image->columns*image->rows); i++)
  179.   {
  180.     /*
  181.       Probe hash table.
  182.     */
  183.     p++;
  184.     index=p->index & 0xff;
  185.     j=(int) ((int) index << (MaxLZWBits-8))+waiting_code;
  186.     if (j >= MaxHashTable)
  187.       j-=MaxHashTable;
  188.     if (hash_code[j] > 0)
  189.       {
  190.         if ((hash_prefix[j] == waiting_code) && (hash_suffix[j] == index))
  191.           {
  192.             waiting_code=hash_code[j];
  193.             continue;
  194.           }
  195.         if (j == 0)
  196.           displacement=1;
  197.         else
  198.           displacement=MaxHashTable-j;
  199.         next_pixel=False;
  200.         for ( ; ; )
  201.         {
  202.           j-=displacement;
  203.           if (j < 0)
  204.             j+=MaxHashTable;
  205.           if (hash_code[j] == 0)
  206.             break;
  207.           if ((hash_prefix[j] == waiting_code) && (hash_suffix[j] == index))
  208.             {
  209.               waiting_code=hash_code[j];
  210.               next_pixel=True;
  211.               break;
  212.             }
  213.         }
  214.         if (next_pixel == True)
  215.           continue;
  216.       }
  217.     LZWOutputCode(waiting_code);
  218.     if (free_code < MaxLZWTable)
  219.       {
  220.         hash_code[j]=free_code++;
  221.         hash_prefix[j]=waiting_code;
  222.         hash_suffix[j]=index;
  223.       }
  224.     else
  225.       {
  226.         /*
  227.           Fill the hash table with empty entries.
  228.         */
  229.         for (j=0; j < MaxHashTable; j++)
  230.           hash_code[j]=0;
  231.         /*
  232.           Reset compressor and issue a clear code.
  233.         */
  234.         free_code=clear_code+2;
  235.         LZWOutputCode(clear_code);
  236.         number_bits=data_size;
  237.         max_code=MaxCode(number_bits);
  238.       }
  239.     waiting_code=index;
  240.   }
  241.   /*
  242.     Flush out the buffered code.
  243.   */
  244.   LZWOutputCode(waiting_code);
  245.   LZWOutputCode(end_of_information_code);
  246.   if (bits > 0)
  247.     {
  248.       /*
  249.         Add a character to current packet.
  250.       */
  251.       packet[byte_count++]=(unsigned char) (datum & 0xff);
  252.       if (byte_count >= 254)
  253.         {
  254.           (void) fputc(byte_count,image->fp);
  255.           (void) fwrite((char *) packet,1,byte_count,image->fp);
  256.           byte_count=0;
  257.         }
  258.     }
  259.   /*
  260.     Flush accumulated data.
  261.   */
  262.   if (byte_count > 0)
  263.     {
  264.       (void) fputc(byte_count,image->fp);
  265.       (void) fwrite((char *) packet,1,byte_count,image->fp);
  266.     }
  267.   /*
  268.     Free encoder memory.
  269.   */
  270.   (void) free((char *) hash_suffix);
  271.   (void) free((char *) hash_prefix);
  272.   (void) free((char *) hash_code);
  273.   (void) free((char *) packet);
  274.   if (i < image->packets)
  275.     return(False);
  276.   return(True);
  277. }
  278.