home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / SHC.H < prev    next >
C/C++ Source or Header  |  1994-07-27  |  7KB  |  215 lines
  1. /* Copyright (C) 1992, 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. /* shc.h */
  20. /* Common definitions for filters using Huffman coding */
  21. /* Requires scommon.h */
  22.  
  23. #ifndef shc_INCLUDED
  24. #  define shc_INCLUDED
  25.  
  26. /*
  27.  * These definitions are valid for code lengths up to 16 bits
  28.  * and non-negative decoded values up to 15 bits.
  29.  *
  30.  * We define 3 different representations of the code: encoding tables,
  31.  * decoding tables (ditto), and a definition table which can be generated
  32.  * easily from frequency information and which in turn can easily generate
  33.  * the encoding and decoding tables.
  34.  *
  35.  * The definition table has two parts: a list of the number of i-bit
  36.  * codes for each i >= 1, and the decoded values corresponding to
  37.  * the code values in increasing lexicographic order (which will also
  38.  * normally be decreasing code frequency).  Calling these two lists
  39.  * L[1..M] and V[0..N-1] respectively, we have the following invariants:
  40.  *    - 1 <= M <= max_hc_length, N >= 2.
  41.  *    - L[0] = 0.
  42.  *    - for i=1..M, L[i] >= 0.
  43.  *    - sum(i=1..M: L[i]) = N.
  44.  *    - sum(i=1..M: L[i] * 2^-i) = 1.
  45.  *    - V[0..N-1] are a permutation of the integers 0..N-1.
  46.  */
  47. #define max_hc_length 16
  48. typedef struct hc_definition_s {
  49.     ushort *counts;            /* [0..M] */
  50.     uint num_counts;        /* M */
  51.     ushort *values;            /* [0..N-1] */
  52.     uint num_values;        /* N */
  53. } hc_definition;
  54.  
  55. /* ------ Common state ------ */
  56.  
  57. /*
  58.  * Define the common stream state for Huffman-coded filters.
  59.  * Invariants when writing:
  60.  *    0 <= bits_left <= hc_bits_size;
  61.  *    Only the leftmost (hc_bits_size - bits_left) bits of bits
  62.  *      contain valid data.
  63.  */
  64. #define stream_hc_state_common\
  65.     stream_state_common;\
  66.         /* The client sets the following before initialization. */\
  67.     bool FirstBitLowOrder;\
  68.         /* The following are updated dynamically. */\
  69.     uint bits;        /* most recent bits of input or */\
  70.                 /* current bits of output */\
  71.     int bits_left        /* # of valid low bits (input) or */\
  72.                 /* unused low bits (output) in above */
  73. typedef struct stream_hc_state_s {
  74.     stream_hc_state_common;
  75. } stream_hc_state;
  76.  
  77. #define hc_bits_size (arch_sizeof_int * 8)
  78. #define s_hce_init_inline(ss)\
  79.   ((ss)->bits = 0, (ss)->bits_left = hc_bits_size)
  80. #define s_hcd_init_inline(ss)\
  81.   ((ss)->bits = 0, (ss)->bits_left = 0)
  82.  
  83. /* Declare a table for reversing the bit order of each byte. */
  84. extern const byte sbits_reverse_bits[256];
  85.  
  86. /* ------ Encoding tables ------ */
  87.  
  88. /* Define the structure for the encoding tables. */
  89. typedef struct hce_code_s {
  90.     ushort code;
  91.     ushort code_length;
  92. } hce_code;
  93. #define hce_entry(c, len) { c, len }
  94.  
  95. typedef struct hce_table_s {
  96.     uint count;
  97.     hce_code *codes;
  98. } hce_table;
  99.  
  100. /* ------ Encoding utilities ------ */
  101.  
  102. /*
  103.  * Put a code on the output.  The client is responsible for ensuring
  104.  * that q does not exceed pw->limit.
  105.  */
  106.  
  107. #ifdef DEBUG
  108. #  define hc_print(rp)\
  109.     (gs_debug_c('W') ?\
  110.      (dprintf2("[W]0x%x,%d\n", (rp)->code, (rp)->code_length), 0) : 0)
  111. #else
  112. #  define hc_print(rp) 0
  113. #endif
  114.  
  115. byte *hc_put_code_proc(P3(stream_hc_state *, byte *, uint));
  116. #define hc_put_code(ss, q, cp)\
  117.   (hc_print(cp),\
  118.    (((ss)->bits_left -= (cp)->code_length) >= 0 ?\
  119.     (ss)->bits += (cp)->code << (ss)->bits_left :\
  120.     (q = hc_put_code_proc((stream_hc_state *)(ss), q, (cp)->code), 0)))
  121.  
  122. /*
  123.  * Force out the final bits to the output.
  124.  */
  125. byte *hc_put_last_bits(P2(stream_hc_state *, byte *));
  126.  
  127.  
  128. /* ------ Decoding tables ------ */
  129.  
  130. /*
  131.  * Define the structure for the decoding tables.
  132.  * First-level nodes are either leaves, which have
  133.  *    value = decoded value
  134.  *    code_length <= initial_bits
  135.  * or non-leaves, which have
  136.  *    value = the index of a sub-table
  137.  *    code_length = initial_bits + the number of additional dispatch bits
  138.  * Second-level nodes are always leaves, with
  139.  *    code_length = the actual number of bits in the code - initial_bits.
  140.  */
  141. #define hcd_value_error (-1)
  142.  
  143. typedef struct hcd_code_s {
  144.     short value;
  145.     ushort code_length;
  146. } hcd_code;
  147.  
  148. typedef struct hcd_table_s {
  149.     uint count;
  150.     uint initial_bits;
  151.     hcd_code *codes;
  152. } hcd_table;
  153.  
  154. /* Declare variables that hold the decoder state. */
  155. #define hcd_declare_state\
  156.     register const byte *p;\
  157.     const byte *rlimit;\
  158.     uint bits;\
  159.     int bits_left
  160.  
  161. /* Load the state from the stream. */
  162. /* Free variables: pr, ss, p, rlimit, bits, bits_left. */
  163. #define hcd_load_state()\
  164.     p = pr->ptr, rlimit = pr->limit,\
  165.     bits = ss->bits, bits_left = ss->bits_left
  166.  
  167. /* Store the state back in the stream. */
  168. /* Free variables: pr, ss, p, bits, bits_left. */
  169. #define hcd_store_state()\
  170.     pr->ptr = p,\
  171.     ss->bits = bits, ss->bits_left = bits_left
  172.  
  173. /* Macros to get blocks of bits from the input stream. */
  174. /* Invariants: 0 <= bits_left <= bits_size; */
  175. /* bits [bits_left-1..0] contain valid data. */
  176.  
  177. /* n must not be greater than 8. */
  178. #define hcd_bits_available(n)\
  179.   (bits_left >= (n) || rlimit - p > ((n) - bits_left - 1) >> 3)
  180. #define hcd_ensure_bits(n, outl)\
  181.   if ( bits_left < n ) hcd_more_bits(outl)
  182.  
  183. /* Load more bits into the buffer. */
  184. #define hcd_more_bits_1(outl)\
  185.   { int c;\
  186.     if ( p < rlimit ) c = *++p;\
  187.     else goto outl;\
  188.     if ( ss->FirstBitLowOrder ) c = sbits_reverse_bits[c];\
  189.     bits = (bits << 8) + c, bits_left += 8;\
  190.   }
  191. #if hc_bits_size == 16
  192. #  define hcd_more_bits(outl) hcd_more_bits_1(outl)
  193. #else                /* hc_bits_size >= 32 */
  194. #  define hcd_more_bits(outl)\
  195.   { if ( rlimit - p < 3 ) hcd_more_bits_1(outl)\
  196.     else\
  197.     { if ( ss->FirstBitLowOrder )\
  198.     bits = (bits << 24) + ((uint)sbits_reverse_bits[p[1]] << 16) + ((uint)sbits_reverse_bits[p[2]] << 8) + sbits_reverse_bits[p[3]];\
  199.       else\
  200.     bits = (bits << 24) + ((uint)p[1] << 16) + ((uint)p[2] << 8) + p[3];\
  201.       bits_left += 24, p += 3;\
  202.     }\
  203.   }
  204. #endif
  205.  
  206. #define hcd_peek_bits(n) ((bits >> (bits_left - (n))) & ((1 << (n)) - 1))
  207.  
  208. #define hcd_peek_var_bits(n)\
  209.   ((bits >> (bits_left - (n))) & sbits_peek_masks[n])
  210. extern const byte sbits_peek_masks[9];
  211.  
  212. #define hcd_skip_bits(n) (bits_left -= (n))
  213.  
  214. #endif                    /* shc_INCLUDED */
  215.