1 /* Copyright (C) 2001-2006 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, modified 8 or distributed except as expressly authorized under the terms of that 9 license. Refer to licensing information at http://www.artifex.com/ 10 or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, 11 San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information. 12 */ 13 14 /* $Id: shc.h 8022 2007-06-05 22:23:38Z giles $ */ 15 /* Common definitions for filters using Huffman coding */ 16 17 #ifndef shc_INCLUDED 18 # define shc_INCLUDED 19 20 #include "gsbittab.h" 21 #include "scommon.h" 22 23 /* 24 * These definitions are valid for code lengths up to 16 bits 25 * and non-negative decoded values up to 15 bits. 26 * 27 * We define 3 different representations of the code: encoding tables, 28 * decoding tables, and a definition table which can be generated easily 29 * from frequency information and which in turn can easily generate 30 * the encoding and decoding tables. 31 * 32 * The definition table has two parts: a list of the number of i-bit 33 * codes for each i >= 1, and the decoded values corresponding to 34 * the code values in increasing lexicographic order (which will also 35 * normally be decreasing code frequency). Calling these two lists 36 * L[1..M] and V[0..N-1] respectively, we have the following invariants: 37 * - 1 <= M <= max_hc_length, N >= 2. 38 * - L[0] = 0. 39 * - for i=1..M, L[i] >= 0. 40 * - sum(i=1..M: L[i]) = N. 41 * - sum(i=1..M: L[i] * 2^-i) = 1. 42 * - V[0..N-1] are a permutation of the integers 0..N-1. 43 */ 44 #define max_hc_length 16 45 typedef struct hc_definition_s { 46 ushort *counts; /* [0..M] */ 47 uint num_counts; /* M */ 48 ushort *values; /* [0..N-1] */ 49 uint num_values; /* N */ 50 } hc_definition; 51 52 /* ------ Common state ------ */ 53 54 /* 55 * Define the common stream state for Huffman-coded filters. 56 * Invariants when writing: 57 * 0 <= bits_left <= hc_bits_size; 58 * Only the leftmost (hc_bits_size - bits_left) bits of bits 59 * contain valid data. 60 */ 61 #define stream_hc_state_common\ 62 stream_state_common;\ 63 /* The client sets the following before initialization. */\ 64 bool FirstBitLowOrder;\ 65 /* The following are updated dynamically. */\ 66 uint bits; /* most recent bits of input or */\ 67 /* current bits of output */\ 68 int bits_left /* # of valid low bits (input) or */\ 69 /* unused low bits (output) in above, */\ 70 /* 0 <= bits_left <= 7 */ 71 typedef struct stream_hc_state_s { 72 stream_hc_state_common; 73 } stream_hc_state; 74 75 #define hc_bits_size (arch_sizeof_int * 8) 76 #define s_hce_init_inline(ss)\ 77 ((ss)->bits = 0, (ss)->bits_left = hc_bits_size) 78 #define s_hcd_init_inline(ss)\ 79 ((ss)->bits = 0, (ss)->bits_left = 0) 80 81 /* ------ Encoding tables ------ */ 82 83 /* Define the structure for the encoding tables. */ 84 typedef struct hce_code_s { 85 ushort code; 86 ushort code_length; 87 } hce_code; 88 89 #define hce_entry(c, len) { c, len } 90 91 typedef struct hce_table_s { 92 uint count; 93 hce_code *codes; 94 } hce_table; 95 96 #define hce_bits_available(n)\ 97 (ss->bits_left >= (n) || wlimit - q > ((n) - ss->bits_left - 1) >> 3) 98 99 /* ------ Encoding utilities ------ */ 100 101 /* 102 * Put a code on the output. The client is responsible for ensuring 103 * that q does not exceed pw->limit. 104 */ 105 106 #ifdef DEBUG 107 # define hc_print_value(code, clen)\ 108 (gs_debug_c('W') ?\ 109 (dlprintf2("[W]0x%x,%d\n", code, clen), 0) : 0) 110 # define hc_print_value_then(code, clen) hc_print_value(code, clen), 111 #else 112 # define hc_print_value(code, clen) 0 113 # define hc_print_value_then(code, clen) /* */ 114 #endif 115 #define hc_print_code(rp) hc_print_value((rp)->code, (rp)->code_length) 116 117 /* Declare variables that hold the encoder state. */ 118 #define hce_declare_state\ 119 register uint bits;\ 120 register int bits_left 121 122 /* Load the state from the stream. */ 123 /* Free variables: ss, bits, bits_left. */ 124 #define hce_load_state()\ 125 bits = ss->bits, bits_left = ss->bits_left 126 127 /* Store the state back in the stream. */ 128 /* Free variables: ss, bits, bits_left. */ 129 #define hce_store_state()\ 130 ss->bits = bits, ss->bits_left = bits_left 131 132 /* Put a code on the stream. */ 133 void hc_put_code_proc(bool, byte *, uint); 134 135 #define hc_put_value(ss, q, code, clen)\ 136 (hc_print_value_then(code, clen)\ 137 ((bits_left -= (clen)) >= 0 ?\ 138 (bits += (code) << bits_left) :\ 139 (hc_put_code_proc((ss)->FirstBitLowOrder,\ 140 q += hc_bits_size >> 3,\ 141 (bits + ((code) >> -bits_left))),\ 142 bits = (code) << (bits_left += hc_bits_size)))) 143 #define hc_put_code(ss, q, cp)\ 144 hc_put_value(ss, q, (cp)->code, (cp)->code_length) 145 146 /* 147 * Force out the final bits to the output. 148 * Note that this does a store_state, but not a load_state. 149 */ 150 byte *hc_put_last_bits_proc(stream_hc_state *, byte *, uint, int); 151 152 #define hc_put_last_bits(ss, q)\ 153 hc_put_last_bits_proc(ss, q, bits, bits_left) 154 155 /* ------ Decoding tables ------ */ 156 157 /* 158 * Define the structure for the decoding tables. 159 * First-level nodes are either leaves, which have 160 * value = decoded value 161 * code_length <= initial_bits 162 * or non-leaves, which have 163 * value = the index of a sub-table 164 * code_length = initial_bits + the number of additional dispatch bits 165 * Second-level nodes are always leaves, with 166 * code_length = the actual number of bits in the code - initial_bits. 167 */ 168 169 typedef struct hcd_code_s { 170 short value; 171 ushort code_length; 172 } hcd_code; 173 174 typedef struct hcd_table_s { 175 uint count; 176 uint initial_bits; 177 hcd_code *codes; 178 } hcd_table; 179 180 /* Declare variables that hold the decoder state. */ 181 #define hcd_declare_state\ 182 register const byte *p;\ 183 const byte *rlimit;\ 184 uint bits;\ 185 int bits_left 186 187 /* Load the state from the stream. */ 188 /* Free variables: pr, ss, p, rlimit, bits, bits_left. */ 189 #define hcd_load_state()\ 190 p = pr->ptr,\ 191 rlimit = pr->limit,\ 192 bits = ss->bits,\ 193 bits_left = ss->bits_left 194 195 /* Store the state back in the stream. */ 196 /* Put back any complete bytes into the input buffer. */ 197 /* Free variables: pr, ss, p, bits, bits_left. */ 198 #define hcd_store_state()\ 199 pr->ptr = p -= (bits_left >> 3),\ 200 ss->bits = bits >>= (bits_left & ~7),\ 201 ss->bits_left = bits_left &= 7 202 203 /* Macros to get blocks of bits from the input stream. */ 204 /* Invariants: 0 <= bits_left <= bits_size; */ 205 /* bits [bits_left-1..0] contain valid data. */ 206 207 #define hcd_bits_available(n)\ 208 (bits_left >= (n) || rlimit - p > ((n) - bits_left - 1) >> 3) 209 /* For hcd_ensure_bits, n must not be greater than 8. */ 210 #define HCD_ENSURE_BITS_ELSE(n)\ 211 if (bits_left >= n)\ 212 DO_NOTHING;\ 213 else HCD_MORE_BITS_ELSE 214 #define hcd_ensure_bits(n, outl)\ 215 BEGIN HCD_ENSURE_BITS_ELSE(n) goto outl; END 216 217 /* Load more bits into the buffer. */ 218 #define HCD_MORE_BITS_1_ELSE\ 219 if (p < rlimit) {\ 220 int c = *++p;\ 221 \ 222 if (ss->FirstBitLowOrder)\ 223 c = byte_reverse_bits[c];\ 224 bits = (bits << 8) + c, bits_left += 8;\ 225 } else 226 #if hc_bits_size == 16 227 # define HCD_MORE_BITS_ELSE HCD_MORE_BITS_1_ELSE 228 #else /* hc_bits_size >= 32 */ 229 # define HCD_MORE_BITS_ELSE\ 230 if (rlimit - p >= 3) {\ 231 if (ss->FirstBitLowOrder)\ 232 bits = (bits << 24) + ((uint)byte_reverse_bits[p[1]] << 16) + ((uint)byte_reverse_bits[p[2]] << 8) + byte_reverse_bits[p[3]];\ 233 else\ 234 bits = (bits << 24) + ((uint)p[1] << 16) + ((uint)p[2] << 8) + p[3];\ 235 bits_left += 24, p += 3;\ 236 } else HCD_MORE_BITS_1_ELSE 237 #endif 238 #define hcd_more_bits(outl)\ 239 BEGIN HCD_MORE_BITS_ELSE goto outl; END 240 241 #define hcd_peek_bits(n) ((bits >> (bits_left - (n))) & ((1 << (n)) - 1)) 242 243 /* hcd_peek_var_bits requires bits_left <= 8. */ 244 #define hcd_peek_var_bits(n)\ 245 ((bits >> (bits_left - (n))) & byte_right_mask[n]) 246 247 /* hcd_peek_bits_left requires bits_left <= 8. */ 248 #define hcd_peek_bits_left()\ 249 (bits & byte_right_mask[bits_left]) 250 251 #define hcd_skip_bits(n) (bits_left -= (n)) 252 253 #endif /* shc_INCLUDED */ 254