home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / SLZWD.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  11KB  |  367 lines
  1. /* Copyright (C) 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* slzwd.c */
  20. /* LZW decoding filter */
  21. #include "stdio_.h"    /* includes std.h */
  22. #include "gdebug.h"
  23. #include "strimpl.h"
  24. #include "slzwx.h"
  25.  
  26. /********************************************************/
  27. /* LZW routines are based on:                */
  28. /* Dr. Dobbs Journal --- Oct. 1989.             */
  29. /* Article on LZW Data Compression by Mark R. Nelson     */
  30. /********************************************************/
  31.  
  32. /* Define the special codes in terms of code_escape, which is */
  33. /* 1 << InitialCodeLength. */
  34. #define code_reset (code_escape + 0)
  35. #define code_eod (code_escape + 1)
  36. #define code_0 (code_escape + 2)        /* first assignable code */
  37.  
  38. struct lzw_decode_s {
  39.     byte datum;
  40.     byte len;            /* length of code */
  41.     ushort prefix;            /* code to be prefixed */
  42. };
  43. gs_private_st_simple(st_lzw_decode, lzw_decode, "lzw_decode");
  44. /* We can use a simple type as the element type, */
  45. /* because there are no pointers to enumerate or relocate. */
  46. #define st_lzw_decode_element st_lzw_decode
  47. #define lzw_decode_max 4096        /* must be 4096 */
  48.  
  49. /* The structure is exported for the encoding filter. */
  50. public_st_LZW_state();
  51.  
  52. #define ss ((stream_LZW_state *)st)
  53.  
  54. /* Initialize LZWDecode filter */
  55. private int
  56. s_LZWD_init(stream_state *st)
  57. {    register lzw_decode *dc;
  58.     register int i;
  59.     uint code_escape = 1 << ss->InitialCodeLength;
  60.     dc = gs_alloc_struct_array(st->memory, lzw_decode_max + 1,
  61.                    lzw_decode, &st_lzw_decode_element,
  62.                    "LZWDecode(init)");
  63.     if ( dc == 0 )
  64.         return ERRC;        /****** WRONG ******/
  65.     ss->bits_left = 0;
  66.     ss->bytes_left = 0;
  67.     ss->next_code = code_0;
  68.     ss->code_size = ss->InitialCodeLength + 1;
  69.     ss->prev_code = -1;
  70.     ss->copy_code = -1;
  71.     ss->table.decode = dc;
  72.     dc[code_reset].len = 255;
  73.     dc[code_eod].len = 255;
  74.     for ( i = 0; i < code_escape; i++, dc++ )
  75.         dc->datum = i, dc->len = 1, dc->prefix = code_eod;
  76.     return 0;
  77. }
  78.  
  79. /* Process a buffer */
  80. private int
  81. s_LZWD_process(stream_state *st, stream_cursor_read *pr,
  82.   stream_cursor_write *pw, bool last)
  83. {    register const byte *p = pr->ptr;
  84.     register byte *q = pw->ptr;
  85. #ifdef DEBUG
  86.     byte *q0 = q;
  87. #endif
  88.     const byte *rlimit = pr->limit;            /* constant pointer */
  89.     byte *wlimit = pw->limit;            /* constant pointer */
  90.     int status = 0;
  91.     int code = ss->copy_code;
  92.     int prev_code = ss->prev_code;
  93.     uint prev_len = ss->prev_len;
  94.     byte bits = ss->bits;
  95.     int bits_left = ss->bits_left;
  96.     int bytes_left = ss->bytes_left;
  97.     int code_size = ss->code_size;
  98.     int code_mask;
  99.     int switch_code;
  100.     int next_code = ss->next_code;
  101.     lzw_decode *table = ss->table.decode;        /* constant pointer */
  102.     lzw_decode *dc_next = table + next_code;    /* invariant */
  103.     lzw_decode *dc;
  104.     int code_escape = 1 << ss->InitialCodeLength;
  105.     int eod = code_eod;
  106.     bool low_order = ss->FirstBitLowOrder;
  107.     uint len;
  108.     int c;
  109.     byte b;
  110.     byte *q1;
  111.     if_debug2('w', "[w]process decode: code_size=%d next_code=%d\n",
  112.           code_size, next_code);
  113. #define set_code_size()\
  114.   code_mask = (1 << code_size) - 1,\
  115.   switch_code = code_mask + 1 - ss->EarlyChange
  116.     set_code_size();
  117.     if ( !ss->BlockData )
  118.       bytes_left = rlimit - p + 2;     /* never stop for bytes_left */
  119.     /* If we are in the middle of copying a string, */
  120.     /* do some more now. */
  121.     if ( code >= 0 )
  122.     {    int rlen = ss->copy_left;
  123.         int wlen = wlimit - q;
  124.         int n = len = min(rlen, wlen);
  125.         c = code;
  126.         ss->copy_left = rlen -= len;
  127.         if_debug3('W', "[W]copying 0x%x, %d byte(s) out of %d left\n",
  128.               code, len, rlen + len);
  129.         while ( rlen )
  130.             c = table[c].prefix,
  131.             rlen--;
  132.         q1 = q += len;
  133.         n = len;
  134.         while ( --n >= 0 )
  135.         {    *q1-- = (dc = &table[c])->datum;
  136.             c = dc->prefix;
  137.         }
  138.         if ( ss->copy_left )            /* more to do */
  139.         {    pw->ptr = q;
  140.             return 1;
  141.         }
  142.         ss->copy_code = -1;
  143.         len = ss->copy_len;
  144.         /* Retrieve the first byte of the code just copied. */
  145.         if ( c == eod )
  146.         {    /* We just copied the entire code, */
  147.             /* so the byte we want is immediately available. */
  148.             b = q1[1];
  149.         }
  150.         else
  151.         {    /* We have to scan to the beginning of the code. */
  152.             for ( ; c != eod; c = table[c].prefix )
  153.                 b = (byte)c;
  154.         }
  155.         goto add;
  156.     }
  157. top:    if ( code_size > bits_left )
  158.       {    if ( bytes_left == 0 )
  159.           {    if ( p == rlimit )
  160.               goto out;
  161.             bytes_left = *++p;
  162.             if_debug1('W', "[W]block count %d\n", bytes_left);
  163.             if ( bytes_left == 0 )
  164.               {    status = EOFC;
  165.                 goto out;
  166.               }
  167.             goto top;
  168.           }
  169.         if ( low_order )
  170.           code = bits >> (8 - bits_left);
  171.         else
  172.           code = (uint)bits << (code_size - bits_left);
  173.         if ( bits_left + 8 < code_size )
  174.           {    /* Need 2 more data bytes */
  175.             if ( bytes_left == 1 )
  176.               {    if ( rlimit - p < 3 )
  177.                   goto out;
  178.                 bytes_left = p[2];
  179.                 if_debug1('W', "[W]block count %d\n",
  180.                       bytes_left);
  181.                 if ( bytes_left == 0 )
  182.                   {    status = EOFC;
  183.                     goto out;
  184.                   }
  185.                 bytes_left++;
  186.                 bits = p[1];
  187.                 p++;
  188.               }
  189.             else
  190.               {    if ( rlimit - p < 2 )
  191.                   goto out;
  192.                 bits = p[1];
  193.               }
  194.             if ( low_order )
  195.               code += (uint)bits << bits_left;
  196.             else
  197.               code += (uint)bits << (code_size - 8 - bits_left);
  198.             bits_left += 8;
  199.             bits = p[2];
  200.             p += 2;
  201.             bytes_left -= 2;
  202.           }
  203.         else
  204.           {    if ( p == rlimit )
  205.               goto out;
  206.             bits = *++p;
  207.             bytes_left--;
  208.           }
  209.         if ( low_order )
  210.           code += (uint)bits << bits_left,
  211.           bits_left += 8 - code_size;
  212.         else
  213.           bits_left += 8 - code_size,
  214.           code += bits >> bits_left;
  215.       }
  216.     else
  217.       {    if ( low_order )
  218.           code = bits >> (8 - bits_left),
  219.           bits_left -= code_size;
  220.         else
  221.           bits_left -= code_size,
  222.           code = bits >> bits_left;
  223.       }
  224.     code &= code_mask;
  225.     if_debug2('W', "[W]reading 0x%x,%d\n", code, code_size);
  226.     /*
  227.      * There is an anomalous case where a code S is followed
  228.      * immediately by another occurrence of the S string.
  229.      * In this case, the next available code will be defined as
  230.      * S followed by the first character of S, and will be
  231.      * emitted immediately after the code S.  We have to
  232.      * recognize this case specially, by noting that the code is
  233.      * equal to next_code.
  234.      */
  235.     if ( code == next_code )
  236.     {    /* Fabricate the entry for the code.  It will be */
  237.         /* overwritten immediately, of course. */
  238.         for ( c = prev_code; c != eod; c = table[c].prefix )
  239.             dc_next->datum = c;
  240.         len = prev_len + 1;
  241.         dc_next->len = min(len, 255);
  242.         dc_next->prefix = prev_code;
  243.         if_debug3('w', "[w]decoding anomalous 0x%x=0x%x+%c\n",
  244.               next_code, prev_code, dc_next->datum);
  245.     }
  246. #ifdef DEBUG
  247.     else if ( code > next_code )
  248.     {    lprintf2("[W]code = %d > next_code = %d\n",
  249.              code, next_code);
  250.         status = ERRC;
  251.         goto out;
  252.     }
  253. #endif
  254.     /* See if there is enough room for the code. */
  255.     len = table[code].len;
  256.     if ( len == 255 )
  257.     {    /* Check for special code (reset or end). */
  258.         /* We set their lengths to 255 to avoid doing */
  259.         /* an extra check in the normal case. */
  260.         if ( code == code_reset )
  261.         {    if_debug1('w', "[w]reset: next_code was %d\n",
  262.                   next_code);
  263.             next_code = code_0;
  264.             dc_next = table + code_0;
  265.             code_size = ss->InitialCodeLength + 1;
  266.             set_code_size();
  267.             prev_code = -1;
  268.             goto top;
  269.         }
  270.         else if ( code == eod )
  271.         {    status = EOFC;
  272.             goto out;
  273.         }
  274.         /* The code length won't fit in a byte, */
  275.         /* compute it the hard way. */
  276.         for ( c = code, len = 0; c != eod; len++ )
  277.             c = table[c].prefix;
  278.         if_debug2('w', "[w]long code %d, length=%d\n", code, len);
  279.     }
  280.     if ( wlimit - q < len )
  281.     {    ss->copy_code = code;
  282.         ss->copy_left = ss->copy_len = len;
  283.         status = 1;
  284.         goto out;
  285.     }
  286.     /* Copy the string to the buffer (back to front). */
  287.     /* Optimize for short codes, which are the most frequent. */
  288.     dc = &table[code];
  289.     switch ( len )
  290.     {
  291.     default:
  292.     {    byte *q1 = q += len;
  293.         c = code;
  294.         do
  295.         {    *q1-- = (dc = &table[c])->datum;
  296.         }
  297.         while ( (c = dc->prefix) != eod );
  298.         b = q1[1];
  299.     }    break;
  300.     case 3:
  301.         q[3] = dc->datum;
  302.         dc = &table[dc->prefix];
  303.     case 2:
  304.         q[2] = dc->datum;
  305.         dc = &table[dc->prefix];
  306.     case 1:
  307.         q[1] = b = dc->datum;
  308.         q += len;
  309.     }
  310. add:    /* Add a new entry to the table */
  311.     if ( prev_code >= 0 )
  312.     {    /* Unfortunately, we have to check for next_code == */
  313.         /* lzw_decode_max every time: just checking at power */
  314.         /* of 2 boundaries stops us one code too soon. */
  315.         if ( next_code == lzw_decode_max )
  316.         {    status = ERRC;
  317.             goto out;
  318.         }
  319.         dc_next->datum = b;        /* added char of string */
  320.         dc_next->len = min(prev_len, 254) + 1;
  321.         dc_next->prefix = prev_code;
  322.         dc_next++;
  323.         if_debug4('W', "[W]adding 0x%x=0x%x+%c(%d)\n",
  324.               next_code, prev_code, b, min(len, 255));
  325.         if ( ++next_code == switch_code )
  326.         {    /* Crossed a power of 2. */
  327.             /* We have to make a strange special check for */
  328.             /* reaching the end of the code space. */
  329.             if ( next_code < lzw_decode_max - 1 )
  330.             {    code_size++;
  331.                 set_code_size();
  332.                 if_debug2('w', "[w]crossed power of 2: new code_size=%d, next_code=%d\n",
  333.                       code_size, next_code);
  334.             }
  335.         }
  336.     }
  337.     prev_code = code;
  338.     prev_len = len;
  339.     goto top;
  340. out:    pr->ptr = p;
  341.     pw->ptr = q;
  342.     ss->code_size = code_size;
  343.     ss->prev_code = prev_code;
  344.     ss->prev_len = prev_len;
  345.     ss->bits = bits;
  346.     ss->bits_left = bits_left;
  347.     ss->bytes_left = bytes_left;
  348.     ss->next_code = next_code;
  349.     if_debug3('w', "[w]decoded %d bytes, prev_code=%d, next_code=%d\n",
  350.           (int)(q - q0), prev_code, next_code);
  351.     return status;
  352. }
  353.  
  354. /* Release a LZW filter. */
  355. /* This is exported for the LZWEncode filter. */
  356. void
  357. s_LZW_release(stream_state *st)
  358. {    gs_free_object(st->memory, ss->table.decode, "LZW(close)");
  359. }
  360.  
  361. #undef ss
  362.  
  363. /* Stream template */
  364. const stream_template s_LZWD_template =
  365. {    &st_LZW_state, s_LZWD_init, s_LZWD_process, 3, 1, s_LZW_release
  366. };
  367.