1 /* Copyright (C) 1992, 1995, 1997, 1998 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: shc.h,v 1.5 2002/06/16 05:00:54 lpd Exp $ */ 18 /* Common definitions for filters using Huffman coding */ 19 20 #ifndef shc_INCLUDED 21 # define shc_INCLUDED 22 23 #include "gsbittab.h" 24 #include "scommon.h" 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, and a definition table which can be generated easily 32 * 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 /* 0 <= bits_left <= 7 */ 74 typedef struct stream_hc_state_s { 75 stream_hc_state_common; 76 } stream_hc_state; 77 78 #define hc_bits_size (arch_sizeof_int * 8) 79 #define s_hce_init_inline(ss)\ 80 ((ss)->bits = 0, (ss)->bits_left = hc_bits_size) 81 #define s_hcd_init_inline(ss)\ 82 ((ss)->bits = 0, (ss)->bits_left = 0) 83 84 /* ------ Encoding tables ------ */ 85 86 /* Define the structure for the encoding tables. */ 87 typedef struct hce_code_s { 88 ushort code; 89 ushort code_length; 90 } hce_code; 91 92 #define hce_entry(c, len) { c, len } 93 94 typedef struct hce_table_s { 95 uint count; 96 hce_code *codes; 97 } hce_table; 98 99 #define hce_bits_available(n)\ 100 (ss->bits_left >= (n) || wlimit - q > ((n) - ss->bits_left - 1) >> 3) 101 102 /* ------ Encoding utilities ------ */ 103 104 /* 105 * Put a code on the output. The client is responsible for ensuring 106 * that q does not exceed pw->limit. 107 */ 108 109 #ifdef DEBUG 110 # define hc_print_value(code, clen)\ 111 (gs_debug_c('W') ?\ 112 (dlprintf2("[W]0x%x,%d\n", code, clen), 0) : 0) 113 # define hc_print_value_then(code, clen) hc_print_value(code, clen), 114 #else 115 # define hc_print_value(code, clen) 0 116 # define hc_print_value_then(code, clen) /* */ 117 #endif 118 #define hc_print_code(rp) hc_print_value((rp)->code, (rp)->code_length) 119 120 /* Declare variables that hold the encoder state. */ 121 #define hce_declare_state\ 122 register uint bits;\ 123 register int bits_left 124 125 /* Load the state from the stream. */ 126 /* Free variables: ss, bits, bits_left. */ 127 #define hce_load_state()\ 128 bits = ss->bits, bits_left = ss->bits_left 129 130 /* Store the state back in the stream. */ 131 /* Free variables: ss, bits, bits_left. */ 132 #define hce_store_state()\ 133 ss->bits = bits, ss->bits_left = bits_left 134 135 /* Put a code on the stream. */ 136 void hc_put_code_proc(bool, byte *, uint); 137 138 #define hc_put_value(ss, q, code, clen)\ 139 (hc_print_value_then(code, clen)\ 140 ((bits_left -= (clen)) >= 0 ?\ 141 (bits += (code) << bits_left) :\ 142 (hc_put_code_proc((ss)->FirstBitLowOrder,\ 143 q += hc_bits_size >> 3,\ 144 (bits + ((code) >> -bits_left))),\ 145 bits = (code) << (bits_left += hc_bits_size)))) 146 #define hc_put_code(ss, q, cp)\ 147 hc_put_value(ss, q, (cp)->code, (cp)->code_length) 148 149 /* 150 * Force out the final bits to the output. 151 * Note that this does a store_state, but not a load_state. 152 */ 153 byte *hc_put_last_bits_proc(stream_hc_state *, byte *, uint, int); 154 155 #define hc_put_last_bits(ss, q)\ 156 hc_put_last_bits_proc(ss, q, bits, bits_left) 157 158 /* ------ Decoding tables ------ */ 159 160 /* 161 * Define the structure for the decoding tables. 162 * First-level nodes are either leaves, which have 163 * value = decoded value 164 * code_length <= initial_bits 165 * or non-leaves, which have 166 * value = the index of a sub-table 167 * code_length = initial_bits + the number of additional dispatch bits 168 * Second-level nodes are always leaves, with 169 * code_length = the actual number of bits in the code - initial_bits. 170 */ 171 172 typedef struct hcd_code_s { 173 short value; 174 ushort code_length; 175 } hcd_code; 176 177 typedef struct hcd_table_s { 178 uint count; 179 uint initial_bits; 180 hcd_code *codes; 181 } hcd_table; 182 183 /* Declare variables that hold the decoder state. */ 184 #define hcd_declare_state\ 185 register const byte *p;\ 186 const byte *rlimit;\ 187 uint bits;\ 188 int bits_left 189 190 /* Load the state from the stream. */ 191 /* Free variables: pr, ss, p, rlimit, bits, bits_left. */ 192 #define hcd_load_state()\ 193 p = pr->ptr,\ 194 rlimit = pr->limit,\ 195 bits = ss->bits,\ 196 bits_left = ss->bits_left 197 198 /* Store the state back in the stream. */ 199 /* Put back any complete bytes into the input buffer. */ 200 /* Free variables: pr, ss, p, bits, bits_left. */ 201 #define hcd_store_state()\ 202 pr->ptr = p -= (bits_left >> 3),\ 203 ss->bits = bits >>= (bits_left & ~7),\ 204 ss->bits_left = bits_left &= 7 205 206 /* Macros to get blocks of bits from the input stream. */ 207 /* Invariants: 0 <= bits_left <= bits_size; */ 208 /* bits [bits_left-1..0] contain valid data. */ 209 210 #define hcd_bits_available(n)\ 211 (bits_left >= (n) || rlimit - p > ((n) - bits_left - 1) >> 3) 212 /* For hcd_ensure_bits, n must not be greater than 8. */ 213 #define HCD_ENSURE_BITS_ELSE(n)\ 214 if (bits_left >= n)\ 215 DO_NOTHING;\ 216 else HCD_MORE_BITS_ELSE 217 #define hcd_ensure_bits(n, outl)\ 218 BEGIN HCD_ENSURE_BITS_ELSE(n) goto outl; END 219 220 /* Load more bits into the buffer. */ 221 #define HCD_MORE_BITS_1_ELSE\ 222 if (p < rlimit) {\ 223 int c = *++p;\ 224 \ 225 if (ss->FirstBitLowOrder)\ 226 c = byte_reverse_bits[c];\ 227 bits = (bits << 8) + c, bits_left += 8;\ 228 } else 229 #if hc_bits_size == 16 230 # define HCD_MORE_BITS_ELSE HCD_MORE_BITS_1_ELSE 231 #else /* hc_bits_size >= 32 */ 232 # define HCD_MORE_BITS_ELSE\ 233 if (rlimit - p >= 3) {\ 234 if (ss->FirstBitLowOrder)\ 235 bits = (bits << 24) + ((uint)byte_reverse_bits[p[1]] << 16) + ((uint)byte_reverse_bits[p[2]] << 8) + byte_reverse_bits[p[3]];\ 236 else\ 237 bits = (bits << 24) + ((uint)p[1] << 16) + ((uint)p[2] << 8) + p[3];\ 238 bits_left += 24, p += 3;\ 239 } else HCD_MORE_BITS_1_ELSE 240 #endif 241 #define hcd_more_bits(outl)\ 242 BEGIN HCD_MORE_BITS_ELSE goto outl; END 243 244 #define hcd_peek_bits(n) ((bits >> (bits_left - (n))) & ((1 << (n)) - 1)) 245 246 /* hcd_peek_var_bits requires bits_left <= 8. */ 247 #define hcd_peek_var_bits(n)\ 248 ((bits >> (bits_left - (n))) & byte_right_mask[n]) 249 250 /* hcd_peek_bits_left requires bits_left <= 8. */ 251 #define hcd_peek_bits_left()\ 252 (bits & byte_right_mask[bits_left]) 253 254 #define hcd_skip_bits(n) (bits_left -= (n)) 255 256 #endif /* shc_INCLUDED */ 257