home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / g / gs252src.zip / GS252 / SLZWE.C < prev    next >
C/C++ Source or Header  |  1992-09-17  |  8KB  |  241 lines
  1. /* Copyright (C) 1991, 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* slzwe.c */
  21. /* LZW encoding filter */
  22. #include "stdio_.h"    /* includes std.h */
  23. #include "gdebug.h"
  24. #include "stream.h"
  25.  
  26. /* Imported procedures */
  27. extern int s_filter_write_flush(P1(stream *));
  28.  
  29. /********************************************************/
  30. /* LZW routines are based on:                */
  31. /* Dr. Dobbs Journal --- Oct. 1989.             */
  32. /* Article on LZW Data Compression by Mark R. Nelson     */
  33. /********************************************************/
  34.  
  35. /*
  36.  * This code implements enhancements to the LZW algorithm.
  37.  *
  38.  * At any moment during the encoding process, let S be the width of the
  39.  * output code in bits.  Let N = 1 << S.  Let M be the next code to be
  40.  * assigned; we know that N / 2 <= M < N.  The only possible codes that
  41.  * can appear in the output are 0 .. M-1.  Therefore, we can encode some
  42.  * of these with only S-1 bits.  Specifically, let D = N - M.  Then to
  43.  * output the code C (0 <= C < M):
  44.  *    If C < D, output C in S-1 bits.
  45.  *    if D <= C < N / 2, output C * 2 in S bits.
  46.  *    Otherwise (N / 2 <= C < M), output (C + N / 2 - M) * 2 + 1 in S bits.
  47.  */
  48.  
  49. /* Define the special codes */
  50. #define code_reset 256
  51. #define code_eod 257
  52. #define code_0 258            /* first assignable code */
  53.  
  54. /* ------ LZWEncode filter ------ */
  55.  
  56. typedef struct lzw_encode_s {
  57.     byte datum;            /* last byte of this code */
  58.     unsigned mark : 4;        /* (only need 1 bit) */
  59.     unsigned prefix : 12;        /* code for prefix of this code */
  60. } lzw_encode;
  61.  
  62. #define encode_max 3000        /* max # of codes, must be */
  63.                     /* > code_0 and <= 4095 */
  64. #define hash_size (encode_max  + encode_max / 4)
  65.  
  66. typedef struct lzw_encode_table_s {
  67.     lzw_encode encode[encode_max];
  68.     ushort hashed[hash_size];
  69. } lzw_encode_table;
  70.  
  71. /* Hashing function */
  72. #define encode_hash(code, chr)\
  73.   ((uint)((code) * 59 + (chr) * ((hash_size / 256) | 1)) % hash_size)
  74.  
  75. /* Export the table size */
  76. const uint s_LZWE_table_sizeof = sizeof(lzw_encode_table);
  77.  
  78. /* Internal routine to put a code onto the target stream. */
  79. /* Let S = s->lzws.code_size, M = s->lzws.next_code, N = 1 << M. */
  80. /* Relevant invariants: 9 <= S <= 12; N / 2 <= M < N; 0 <= code < M; */
  81. /* 1 <= s->lzws.bits_left <= 8; only the rightmost (8 - s->lzws.bits_left) */
  82. /* bits of s->lzws.bits contain valid data. */
  83. private void
  84. lzw_put_code(register stream *s, uint code)
  85. {    byte cb;
  86.     uint rep = code, size = s->lzws.code_size;
  87.     stream *strm = s->strm;
  88.     if ( s->lzws.enhanced )
  89.        {    lzw_encode *encode = s->lzws.encode_table->encode;
  90.         uint mcode = code;
  91.         lzw_encode *ep;
  92.         uint N = 1 << size, M = s->lzws.next_code;
  93.         /* Mark this code and all its prefixes. */
  94.         while ( !(ep = encode + mcode)->mark )
  95.            {    ep->mark = 1;
  96.             mcode = ep->prefix;
  97.            }
  98.         /* See if we can represent the code in S-1 bits. */
  99.         if ( code < N - M )
  100.             --size;        /* yes */
  101.         else if ( code < N / 2 )
  102.             rep <<= 1;    /* no, trailing 0 bit */
  103.         else            /* no, trailing 1 bit */
  104.             rep = (code + N / 2 - M) * 2 + 1;
  105.        }
  106.     cb = (s->lzws.bits << s->lzws.bits_left) +
  107.         (rep >> (size - s->lzws.bits_left));
  108. #ifdef DEBUG
  109. if ( gs_debug['w'] )
  110.    {    dprintf2("[w]writing 0x%x,%d", code, s->lzws.code_size);
  111.     if ( s->lzws.enhanced ) dprintf2(" -> 0x%x,%d", rep, size);
  112.     dputc('\n');
  113.    }
  114. #endif
  115.     sputc(strm, cb);
  116.     if ( (s->lzws.bits_left += 8 - size) <= 0 )
  117.        {    const byte cb1 = rep >> -s->lzws.bits_left;
  118.         sputc(strm, cb1);
  119.         s->lzws.bits_left += 8;
  120.        }
  121.     s->lzws.bits = rep;
  122. }
  123.  
  124. /* Internal routine to reset the encoding table */
  125. private void
  126. lzw_reset_encode(stream *s)
  127. {    register int c;
  128.     lzw_encode_table *table = s->lzws.encode_table;
  129.     lzw_put_code(s, code_reset);
  130.     s->lzws.next_code = code_0;
  131.     s->lzws.code_size = 9;
  132.     s->lzws.prev_code = code_eod;
  133.     for ( c = 0; c < hash_size; c++ )
  134.         table->hashed[c] = code_eod;
  135.     for ( c = 0; c < 256; c++ )
  136.        {    lzw_encode *ec = &table->encode[c];
  137.         register ushort *tc = &table->hashed[encode_hash(code_eod, c)];
  138.         while ( *tc != code_eod )
  139.           if ( ++tc == &table->hashed[hash_size] )
  140.             tc = &table->hashed[0];
  141.         *tc = c;
  142.         ec->datum = c, ec->prefix = code_eod, ec->mark = 1;
  143.        }
  144.     table->encode[code_eod].prefix = code_reset;    /* guarantee no match */
  145.     table->encode[code_eod].mark = 1;
  146.     table->encode[code_reset].mark = 1;
  147. }
  148.  
  149. /* Initialize LZWEncode filter */
  150. void
  151. s_LZWE_init(register stream *s, lzw_encode_table *table, int enhanced)
  152. {    s->lzws.bits_left = 8;
  153.     s->lzws.encode_table = table;
  154.     s->lzws.code_size = 9;        /* needed for reset code */
  155.     s->lzws.next_code = code_0;        /* ditto */
  156.     s->lzws.enhanced = enhanced;
  157.     lzw_reset_encode(s);
  158. }
  159.  
  160. /* Flush the buffer */
  161. private int
  162. s_LZWE_write_buf(register stream *s)
  163. {    register byte *p = s->cbuf;
  164.     byte *limit = s->cptr;
  165.     int code = s->lzws.prev_code;
  166.     lzw_encode_table *table = s->lzws.encode_table;
  167.     ushort *table_end = &table->hashed[hash_size];
  168.     int limit_code;
  169. #define set_limit_code()\
  170.   limit_code = (1 << s->lzws.code_size) - 1;\
  171.   if ( limit_code > encode_max ) limit_code = encode_max
  172.     set_limit_code();
  173.     while ( p <= limit )
  174.        {    byte c = *p;
  175.         ushort *tp;
  176.         for ( tp = &table->hashed[encode_hash(code, c)]; ; )
  177.            {    lzw_encode *ep = &table->encode[*tp];
  178.             if ( ep->prefix == code && ep->datum == c )
  179.                {    code = *tp;
  180.                 p++;
  181.                 break;
  182.                }
  183.             else if ( *tp != code_eod )
  184.                {    if ( ++tp == table_end )
  185.                   tp = &table->hashed[0]; /* wrap around */
  186.                }
  187.             else
  188.                {    /* end of recognized sequence */
  189.                 lzw_put_code(s, code);
  190.                 if ( s->lzws.next_code == limit_code )
  191.                    {    /* Reached power of 2 or limit. */
  192.                     /* Determine which. */
  193.                     if ( s->lzws.next_code == encode_max )
  194.                        {    lzw_reset_encode(s);
  195.                         set_limit_code();
  196.                         goto cx;
  197.                        }
  198.                     s->lzws.code_size++;
  199.                     set_limit_code();
  200.                    }
  201. #ifdef DEBUG
  202. if ( gs_debug['w'] )
  203.                 dprintf3("[w]encoding 0x%x=0x%x+%c\n",
  204.                          s->lzws.next_code, code, c);
  205. #endif
  206.                 *tp = s->lzws.next_code++;
  207.                 ep = &table->encode[*tp];
  208.                 ep->datum = c;
  209.                 ep->prefix = code;
  210.                 ep->mark = 0;
  211. cx:                code = code_eod;
  212.                 break;
  213.                }
  214.            }
  215.        }
  216.     s->lzws.prev_code = code;
  217.     s->cptr = s->cbuf - 1;
  218.     return 0;
  219. }
  220.  
  221. /* Close the stream */
  222. private int
  223. s_LZWE_close(register stream *s)
  224. {    (*s->procs.write_buf)(s);
  225.     if ( s->lzws.prev_code != code_eod )
  226.        {    lzw_put_code(s, s->lzws.prev_code);    /* put out final code */
  227.         /* Adjust next_code for the enhanced case. */
  228.         s->lzws.next_code++;
  229.        }
  230.     lzw_put_code(s, code_eod);
  231.     if ( s->lzws.bits_left < 8 )
  232.       sputc(s->strm, s->lzws.bits << s->lzws.bits_left);    /* final byte */
  233.     return s_std_close(s);
  234. }
  235.  
  236. /* Stream procedures */
  237. const stream_procs s_LZWE_procs =
  238.    {    s_std_noavailable, NULL, s_filter_write_flush, s_LZWE_close,
  239.     NULL, s_LZWE_write_buf
  240.    };
  241.