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