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