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