Fossil SCM

fossil-scm / compat / zlib / examples / enough.c
Source Blame History 597 lines
7ef7284… drh 1 /* enough.c -- determine the maximum size of inflate's Huffman code tables over
adb9e8e… drh 2 * all possible valid and complete prefix codes, subject to a length limit.
6ea30fb… florian 3 * Copyright (C) 2007, 2008, 2012, 2018, 2024 Mark Adler
6ea30fb… florian 4 * Version 1.6 29 July 2024 Mark Adler
7ef7284… drh 5 */
7ef7284… drh 6
7ef7284… drh 7 /* Version history:
7ef7284… drh 8 1.0 3 Jan 2007 First version (derived from codecount.c version 1.4)
7ef7284… drh 9 1.1 4 Jan 2007 Use faster incremental table usage computation
7ef7284… drh 10 Prune examine() search on previously visited states
7ef7284… drh 11 1.2 5 Jan 2007 Comments clean up
7ef7284… drh 12 As inflate does, decrease root for short codes
7ef7284… drh 13 Refuse cases where inflate would increase root
7ef7284… drh 14 1.3 17 Feb 2008 Add argument for initial root table size
7ef7284… drh 15 Fix bug for initial root table size == max - 1
7ef7284… drh 16 Use a macro to compute the history index
bb4776e… jan.nijtmans 17 1.4 18 Aug 2012 Avoid shifts more than bits in type (caused endless loop!)
bb4776e… jan.nijtmans 18 Clean up comparisons of different types
bb4776e… jan.nijtmans 19 Clean up code indentation
adb9e8e… drh 20 1.5 5 Aug 2018 Clean up code style, formatting, and comments
adb9e8e… drh 21 Show all the codes for the maximum, and only the maximum
6ea30fb… florian 22 1.6 29 Jul 2024 Avoid use of uintmax_t
7ef7284… drh 23 */
7ef7284… drh 24
7ef7284… drh 25 /*
adb9e8e… drh 26 Examine all possible prefix codes for a given number of symbols and a
adb9e8e… drh 27 maximum code length in bits to determine the maximum table size for zlib's
adb9e8e… drh 28 inflate. Only complete prefix codes are counted.
7ef7284… drh 29
7ef7284… drh 30 Two codes are considered distinct if the vectors of the number of codes per
adb9e8e… drh 31 length are not identical. So permutations of the symbol assignments result
7ef7284… drh 32 in the same code for the counting, as do permutations of the assignments of
7ef7284… drh 33 the bit values to the codes (i.e. only canonical codes are counted).
7ef7284… drh 34
7ef7284… drh 35 We build a code from shorter to longer lengths, determining how many symbols
adb9e8e… drh 36 are coded at each length. At each step, we have how many symbols remain to
7ef7284… drh 37 be coded, what the last code length used was, and how many bit patterns of
7ef7284… drh 38 that length remain unused. Then we add one to the code length and double the
adb9e8e… drh 39 number of unused patterns to graduate to the next code length. We then
7ef7284… drh 40 assign all portions of the remaining symbols to that code length that
adb9e8e… drh 41 preserve the properties of a correct and eventually complete code. Those
7ef7284… drh 42 properties are: we cannot use more bit patterns than are available; and when
adb9e8e… drh 43 all the symbols are used, there are exactly zero possible bit patterns left
adb9e8e… drh 44 unused.
7ef7284… drh 45
7ef7284… drh 46 The inflate Huffman decoding algorithm uses two-level lookup tables for
adb9e8e… drh 47 speed. There is a single first-level table to decode codes up to root bits
adb9e8e… drh 48 in length (root == 9 for literal/length codes and root == 6 for distance
adb9e8e… drh 49 codes, in the current inflate implementation). The base table has 1 << root
adb9e8e… drh 50 entries and is indexed by the next root bits of input. Codes shorter than
adb9e8e… drh 51 root bits have replicated table entries, so that the correct entry is
adb9e8e… drh 52 pointed to regardless of the bits that follow the short code. If the code is
adb9e8e… drh 53 longer than root bits, then the table entry points to a second-level table.
adb9e8e… drh 54 The size of that table is determined by the longest code with that root-bit
adb9e8e… drh 55 prefix. If that longest code has length len, then the table has size 1 <<
adb9e8e… drh 56 (len - root), to index the remaining bits in that set of codes. Each
adb9e8e… drh 57 subsequent root-bit prefix then has its own sub-table. The total number of
adb9e8e… drh 58 table entries required by the code is calculated incrementally as the number
adb9e8e… drh 59 of codes at each bit length is populated. When all of the codes are shorter
adb9e8e… drh 60 than root bits, then root is reduced to the longest code length, resulting
adb9e8e… drh 61 in a single, smaller, one-level table.
7ef7284… drh 62
7ef7284… drh 63 The inflate algorithm also provides for small values of root (relative to
7ef7284… drh 64 the log2 of the number of symbols), where the shortest code has more bits
adb9e8e… drh 65 than root. In that case, root is increased to the length of the shortest
adb9e8e… drh 66 code. This program, by design, does not handle that case, so it is verified
adb9e8e… drh 67 that the number of symbols is less than 1 << (root + 1).
7ef7284… drh 68
7ef7284… drh 69 In order to speed up the examination (by about ten orders of magnitude for
7ef7284… drh 70 the default arguments), the intermediate states in the build-up of a code
adb9e8e… drh 71 are remembered and previously visited branches are pruned. The memory
7ef7284… drh 72 required for this will increase rapidly with the total number of symbols and
adb9e8e… drh 73 the maximum code length in bits. However this is a very small price to pay
7ef7284… drh 74 for the vast speedup.
7ef7284… drh 75
adb9e8e… drh 76 First, all of the possible prefix codes are counted, and reachable
7ef7284… drh 77 intermediate states are noted by a non-zero count in a saved-results array.
7ef7284… drh 78 Second, the intermediate states that lead to (root + 1) bit or longer codes
7ef7284… drh 79 are used to look at all sub-codes from those junctures for their inflate
adb9e8e… drh 80 memory usage. (The amount of memory used is not affected by the number of
7ef7284… drh 81 codes of root bits or less in length.) Third, the visited states in the
7ef7284… drh 82 construction of those sub-codes and the associated calculation of the table
7ef7284… drh 83 size is recalled in order to avoid recalculating from the same juncture.
7ef7284… drh 84 Beginning the code examination at (root + 1) bit codes, which is enabled by
7ef7284… drh 85 identifying the reachable nodes, accounts for about six of the orders of
adb9e8e… drh 86 magnitude of improvement for the default arguments. About another four
adb9e8e… drh 87 orders of magnitude come from not revisiting previous states. Out of
adb9e8e… drh 88 approximately 2x10^16 possible prefix codes, only about 2x10^6 sub-codes
7ef7284… drh 89 need to be examined to cover all of the possible table memory usage cases
7ef7284… drh 90 for the default arguments of 286 symbols limited to 15-bit codes.
7ef7284… drh 91
6ea30fb… florian 92 Note that unsigned long long is used for counting. It is quite easy to
adb9e8e… drh 93 exceed the capacity of an eight-byte integer with a large number of symbols
adb9e8e… drh 94 and a large maximum code length, so multiple-precision arithmetic would need
adb9e8e… drh 95 to replace the integer arithmetic in that case. This program will abort if
adb9e8e… drh 96 an overflow occurs. The big_t type identifies where the counting takes
adb9e8e… drh 97 place.
adb9e8e… drh 98
6ea30fb… florian 99 The unsigned long long type is also used for calculating the number of
6ea30fb… florian 100 possible codes remaining at the maximum length. This limits the maximum code
6ea30fb… florian 101 length to the number of bits in a long long minus the number of bits needed
6ea30fb… florian 102 to represent the symbols in a flat code. The code_t type identifies where
6ea30fb… florian 103 the bit-pattern counting takes place.
7ef7284… drh 104 */
7ef7284… drh 105
7ef7284… drh 106 #include <stdio.h>
7ef7284… drh 107 #include <stdlib.h>
7ef7284… drh 108 #include <string.h>
adb9e8e… drh 109 #include <stdarg.h>
7ef7284… drh 110 #include <assert.h>
7ef7284… drh 111
7ef7284… drh 112 #define local static
7ef7284… drh 113
adb9e8e… drh 114 // Special data types.
6ea30fb… florian 115 typedef unsigned long long big_t; // type for code counting
6ea30fb… florian 116 #define PRIbig "llu" // printf format for big_t
6ea30fb… florian 117 typedef big_t code_t; // type for bit pattern counting
adb9e8e… drh 118 struct tab { // type for been-here check
adb9e8e… drh 119 size_t len; // allocated length of bit vector in octets
adb9e8e… drh 120 char *vec; // allocated bit vector
7ef7284… drh 121 };
7ef7284… drh 122
7ef7284… drh 123 /* The array for saving results, num[], is indexed with this triplet:
7ef7284… drh 124
7ef7284… drh 125 syms: number of symbols remaining to code
7ef7284… drh 126 left: number of available bit patterns at length len
7ef7284… drh 127 len: number of bits in the codes currently being assigned
7ef7284… drh 128
7ef7284… drh 129 Those indices are constrained thusly when saving results:
7ef7284… drh 130
7ef7284… drh 131 syms: 3..totsym (totsym == total symbols to code)
7ef7284… drh 132 left: 2..syms - 1, but only the evens (so syms == 8 -> 2, 4, 6)
7ef7284… drh 133 len: 1..max - 1 (max == maximum code length in bits)
7ef7284… drh 134
adb9e8e… drh 135 syms == 2 is not saved since that immediately leads to a single code. left
7ef7284… drh 136 must be even, since it represents the number of available bit patterns at
adb9e8e… drh 137 the current length, which is double the number at the previous length. left
adb9e8e… drh 138 ends at syms-1 since left == syms immediately results in a single code.
7ef7284… drh 139 (left > sym is not allowed since that would result in an incomplete code.)
7ef7284… drh 140 len is less than max, since the code completes immediately when len == max.
7ef7284… drh 141
adb9e8e… drh 142 The offset into the array is calculated for the three indices with the first
adb9e8e… drh 143 one (syms) being outermost, and the last one (len) being innermost. We build
adb9e8e… drh 144 the array with length max-1 lists for the len index, with syms-3 of those
adb9e8e… drh 145 for each symbol. There are totsym-2 of those, with each one varying in
adb9e8e… drh 146 length as a function of sym. See the calculation of index in map() for the
adb9e8e… drh 147 index, and the calculation of size in main() for the size of the array.
7ef7284… drh 148
7ef7284… drh 149 For the deflate example of 286 symbols limited to 15-bit codes, the array
adb9e8e… drh 150 has 284,284 entries, taking up 2.17 MB for an 8-byte big_t. More than half
adb9e8e… drh 151 of the space allocated for saved results is actually used -- not all
adb9e8e… drh 152 possible triplets are reached in the generation of valid prefix codes.
7ef7284… drh 153 */
7ef7284… drh 154
7ef7284… drh 155 /* The array for tracking visited states, done[], is itself indexed identically
7ef7284… drh 156 to the num[] array as described above for the (syms, left, len) triplet.
7ef7284… drh 157 Each element in the array is further indexed by the (mem, rem) doublet,
7ef7284… drh 158 where mem is the amount of inflate table space used so far, and rem is the
adb9e8e… drh 159 remaining unused entries in the current inflate sub-table. Each indexed
7ef7284… drh 160 element is simply one bit indicating whether the state has been visited or
adb9e8e… drh 161 not. Since the ranges for mem and rem are not known a priori, each bit
7ef7284… drh 162 vector is of a variable size, and grows as needed to accommodate the visited
adb9e8e… drh 163 states. mem and rem are used to calculate a single index in a triangular
adb9e8e… drh 164 array. Since the range of mem is expected in the default case to be about
7ef7284… drh 165 ten times larger than the range of rem, the array is skewed to reduce the
adb9e8e… drh 166 memory usage, with eight times the range for mem than for rem. See the
adb9e8e… drh 167 calculations for offset and bit in been_here() for the details.
7ef7284… drh 168
7ef7284… drh 169 For the deflate example of 286 symbols limited to 15-bit codes, the bit
adb9e8e… drh 170 vectors grow to total 5.5 MB, in addition to the 4.3 MB done array itself.
7ef7284… drh 171 */
7ef7284… drh 172
adb9e8e… drh 173 // Type for a variable-length, allocated string.
adb9e8e… drh 174 typedef struct {
adb9e8e… drh 175 char *str; // pointer to allocated string
adb9e8e… drh 176 size_t size; // size of allocation
adb9e8e… drh 177 size_t len; // length of string, not including terminating zero
adb9e8e… drh 178 } string_t;
adb9e8e… drh 179
adb9e8e… drh 180 // Clear a string_t.
adb9e8e… drh 181 local void string_clear(string_t *s) {
adb9e8e… drh 182 s->str[0] = 0;
adb9e8e… drh 183 s->len = 0;
adb9e8e… drh 184 }
adb9e8e… drh 185
adb9e8e… drh 186 // Initialize a string_t.
adb9e8e… drh 187 local void string_init(string_t *s) {
adb9e8e… drh 188 s->size = 16;
adb9e8e… drh 189 s->str = malloc(s->size);
adb9e8e… drh 190 assert(s->str != NULL && "out of memory");
adb9e8e… drh 191 string_clear(s);
adb9e8e… drh 192 }
adb9e8e… drh 193
adb9e8e… drh 194 // Release the allocation of a string_t.
adb9e8e… drh 195 local void string_free(string_t *s) {
adb9e8e… drh 196 free(s->str);
adb9e8e… drh 197 s->str = NULL;
adb9e8e… drh 198 s->size = 0;
adb9e8e… drh 199 s->len = 0;
adb9e8e… drh 200 }
adb9e8e… drh 201
adb9e8e… drh 202 // Save the results of printf with fmt and the subsequent argument list to s.
adb9e8e… drh 203 // Each call appends to s. The allocated space for s is increased as needed.
adb9e8e… drh 204 local void string_printf(string_t *s, char *fmt, ...) {
adb9e8e… drh 205 va_list ap;
adb9e8e… drh 206 va_start(ap, fmt);
adb9e8e… drh 207 size_t len = s->len;
adb9e8e… drh 208 int ret = vsnprintf(s->str + len, s->size - len, fmt, ap);
adb9e8e… drh 209 assert(ret >= 0 && "out of memory");
adb9e8e… drh 210 s->len += ret;
adb9e8e… drh 211 if (s->size < s->len + 1) {
adb9e8e… drh 212 do {
adb9e8e… drh 213 s->size <<= 1;
adb9e8e… drh 214 assert(s->size != 0 && "overflow");
adb9e8e… drh 215 } while (s->size < s->len + 1);
adb9e8e… drh 216 s->str = realloc(s->str, s->size);
adb9e8e… drh 217 assert(s->str != NULL && "out of memory");
adb9e8e… drh 218 vsnprintf(s->str + len, s->size - len, fmt, ap);
adb9e8e… drh 219 }
adb9e8e… drh 220 va_end(ap);
adb9e8e… drh 221 }
adb9e8e… drh 222
adb9e8e… drh 223 // Globals to avoid propagating constants or constant pointers recursively.
adb9e8e… drh 224 struct {
adb9e8e… drh 225 int max; // maximum allowed bit length for the codes
adb9e8e… drh 226 int root; // size of base code table in bits
adb9e8e… drh 227 int large; // largest code table so far
adb9e8e… drh 228 size_t size; // number of elements in num and done
adb9e8e… drh 229 big_t tot; // total number of codes with maximum tables size
adb9e8e… drh 230 string_t out; // display of subcodes for maximum tables size
adb9e8e… drh 231 int *code; // number of symbols assigned to each bit length
adb9e8e… drh 232 big_t *num; // saved results array for code counting
adb9e8e… drh 233 struct tab *done; // states already evaluated array
adb9e8e… drh 234 } g;
adb9e8e… drh 235
adb9e8e… drh 236 // Index function for num[] and done[].
adb9e8e… drh 237 local inline size_t map(int syms, int left, int len) {
adb9e8e… drh 238 return ((size_t)((syms - 1) >> 1) * ((syms - 2) >> 1) +
adb9e8e… drh 239 (left >> 1) - 1) * (g.max - 1) +
adb9e8e… drh 240 len - 1;
adb9e8e… drh 241 }
adb9e8e… drh 242
adb9e8e… drh 243 // Free allocated space in globals.
adb9e8e… drh 244 local void cleanup(void) {
adb9e8e… drh 245 if (g.done != NULL) {
adb9e8e… drh 246 for (size_t n = 0; n < g.size; n++)
adb9e8e… drh 247 if (g.done[n].len)
adb9e8e… drh 248 free(g.done[n].vec);
adb9e8e… drh 249 g.size = 0;
adb9e8e… drh 250 free(g.done); g.done = NULL;
adb9e8e… drh 251 }
adb9e8e… drh 252 free(g.num); g.num = NULL;
adb9e8e… drh 253 free(g.code); g.code = NULL;
adb9e8e… drh 254 string_free(&g.out);
adb9e8e… drh 255 }
adb9e8e… drh 256
adb9e8e… drh 257 // Return the number of possible prefix codes using bit patterns of lengths len
adb9e8e… drh 258 // through max inclusive, coding syms symbols, with left bit patterns of length
adb9e8e… drh 259 // len unused -- return -1 if there is an overflow in the counting. Keep a
adb9e8e… drh 260 // record of previous results in num to prevent repeating the same calculation.
adb9e8e… drh 261 local big_t count(int syms, int left, int len) {
adb9e8e… drh 262 // see if only one possible code
7ef7284… drh 263 if (syms == left)
7ef7284… drh 264 return 1;
7ef7284… drh 265
adb9e8e… drh 266 // note and verify the expected state
adb9e8e… drh 267 assert(syms > left && left > 0 && len < g.max);
7ef7284… drh 268
adb9e8e… drh 269 // see if we've done this one already
adb9e8e… drh 270 size_t index = map(syms, left, len);
adb9e8e… drh 271 big_t got = g.num[index];
7ef7284… drh 272 if (got)
adb9e8e… drh 273 return got; // we have -- return the saved result
7ef7284… drh 274
adb9e8e… drh 275 // we need to use at least this many bit patterns so that the code won't be
adb9e8e… drh 276 // incomplete at the next length (more bit patterns than symbols)
adb9e8e… drh 277 int least = (left << 1) - syms;
7ef7284… drh 278 if (least < 0)
7ef7284… drh 279 least = 0;
7ef7284… drh 280
adb9e8e… drh 281 // we can use at most this many bit patterns, lest there not be enough
adb9e8e… drh 282 // available for the remaining symbols at the maximum length (if there were
adb9e8e… drh 283 // no limit to the code length, this would become: most = left - 1)
adb9e8e… drh 284 int most = (((code_t)left << (g.max - len)) - syms) /
adb9e8e… drh 285 (((code_t)1 << (g.max - len)) - 1);
adb9e8e… drh 286
adb9e8e… drh 287 // count all possible codes from this juncture and add them up
adb9e8e… drh 288 big_t sum = 0;
adb9e8e… drh 289 for (int use = least; use <= most; use++) {
adb9e8e… drh 290 got = count(syms - use, (left - use) << 1, len + 1);
7ef7284… drh 291 sum += got;
adb9e8e… drh 292 if (got == (big_t)-1 || sum < got) // overflow
adb9e8e… drh 293 return (big_t)-1;
7ef7284… drh 294 }
7ef7284… drh 295
adb9e8e… drh 296 // verify that all recursive calls are productive
7ef7284… drh 297 assert(sum != 0);
7ef7284… drh 298
adb9e8e… drh 299 // save the result and return it
adb9e8e… drh 300 g.num[index] = sum;
7ef7284… drh 301 return sum;
7ef7284… drh 302 }
7ef7284… drh 303
adb9e8e… drh 304 // Return true if we've been here before, set to true if not. Set a bit in a
adb9e8e… drh 305 // bit vector to indicate visiting this state. Each (syms,len,left) state has a
adb9e8e… drh 306 // variable size bit vector indexed by (mem,rem). The bit vector is lengthened
adb9e8e… drh 307 // as needed to allow setting the (mem,rem) bit.
adb9e8e… drh 308 local int been_here(int syms, int left, int len, int mem, int rem) {
adb9e8e… drh 309 // point to vector for (syms,left,len), bit in vector for (mem,rem)
adb9e8e… drh 310 size_t index = map(syms, left, len);
adb9e8e… drh 311 mem -= 1 << g.root; // mem always includes the root table
adb9e8e… drh 312 mem >>= 1; // mem and rem are always even
adb9e8e… drh 313 rem >>= 1;
adb9e8e… drh 314 size_t offset = (mem >> 3) + rem;
7ef7284… drh 315 offset = ((offset * (offset + 1)) >> 1) + rem;
adb9e8e… drh 316 int bit = 1 << (mem & 7);
adb9e8e… drh 317
adb9e8e… drh 318 // see if we've been here
adb9e8e… drh 319 size_t length = g.done[index].len;
adb9e8e… drh 320 if (offset < length && (g.done[index].vec[offset] & bit) != 0)
adb9e8e… drh 321 return 1; // done this!
adb9e8e… drh 322
adb9e8e… drh 323 // we haven't been here before -- set the bit to show we have now
adb9e8e… drh 324
adb9e8e… drh 325 // see if we need to lengthen the vector in order to set the bit
7ef7284… drh 326 if (length <= offset) {
adb9e8e… drh 327 // if we have one already, enlarge it, zero out the appended space
adb9e8e… drh 328 char *vector;
7ef7284… drh 329 if (length) {
7ef7284… drh 330 do {
7ef7284… drh 331 length <<= 1;
7ef7284… drh 332 } while (length <= offset);
adb9e8e… drh 333 vector = realloc(g.done[index].vec, length);
adb9e8e… drh 334 assert(vector != NULL && "out of memory");
adb9e8e… drh 335 memset(vector + g.done[index].len, 0, length - g.done[index].len);
adb9e8e… drh 336 }
adb9e8e… drh 337
adb9e8e… drh 338 // otherwise we need to make a new vector and zero it out
adb9e8e… drh 339 else {
adb9e8e… drh 340 length = 16;
adb9e8e… drh 341 while (length <= offset)
adb9e8e… drh 342 length <<= 1;
adb9e8e… drh 343 vector = calloc(length, 1);
adb9e8e… drh 344 assert(vector != NULL && "out of memory");
adb9e8e… drh 345 }
adb9e8e… drh 346
adb9e8e… drh 347 // install the new vector
adb9e8e… drh 348 g.done[index].len = length;
adb9e8e… drh 349 g.done[index].vec = vector;
adb9e8e… drh 350 }
adb9e8e… drh 351
adb9e8e… drh 352 // set the bit
adb9e8e… drh 353 g.done[index].vec[offset] |= bit;
7ef7284… drh 354 return 0;
7ef7284… drh 355 }
7ef7284… drh 356
adb9e8e… drh 357 // Examine all possible codes from the given node (syms, len, left). Compute
adb9e8e… drh 358 // the amount of memory required to build inflate's decoding tables, where the
adb9e8e… drh 359 // number of code structures used so far is mem, and the number remaining in
adb9e8e… drh 360 // the current sub-table is rem.
adb9e8e… drh 361 local void examine(int syms, int left, int len, int mem, int rem) {
adb9e8e… drh 362 // see if we have a complete code
7ef7284… drh 363 if (syms == left) {
adb9e8e… drh 364 // set the last code entry
adb9e8e… drh 365 g.code[len] = left;
7ef7284… drh 366
adb9e8e… drh 367 // complete computation of memory used by this code
7ef7284… drh 368 while (rem < left) {
7ef7284… drh 369 left -= rem;
adb9e8e… drh 370 rem = 1 << (len - g.root);
7ef7284… drh 371 mem += rem;
7ef7284… drh 372 }
7ef7284… drh 373 assert(rem == left);
7ef7284… drh 374
adb9e8e… drh 375 // if this is at the maximum, show the sub-code
adb9e8e… drh 376 if (mem >= g.large) {
adb9e8e… drh 377 // if this is a new maximum, update the maximum and clear out the
adb9e8e… drh 378 // printed sub-codes from the previous maximum
adb9e8e… drh 379 if (mem > g.large) {
adb9e8e… drh 380 g.large = mem;
adb9e8e… drh 381 string_clear(&g.out);
adb9e8e… drh 382 }
adb9e8e… drh 383
adb9e8e… drh 384 // compute the starting state for this sub-code
adb9e8e… drh 385 syms = 0;
adb9e8e… drh 386 left = 1 << g.max;
adb9e8e… drh 387 for (int bits = g.max; bits > g.root; bits--) {
adb9e8e… drh 388 syms += g.code[bits];
adb9e8e… drh 389 left -= g.code[bits];
adb9e8e… drh 390 assert((left & 1) == 0);
adb9e8e… drh 391 left >>= 1;
adb9e8e… drh 392 }
adb9e8e… drh 393
adb9e8e… drh 394 // print the starting state and the resulting sub-code to g.out
adb9e8e… drh 395 string_printf(&g.out, "<%u, %u, %u>:",
adb9e8e… drh 396 syms, g.root + 1, ((1 << g.root) - left) << 1);
adb9e8e… drh 397 for (int bits = g.root + 1; bits <= g.max; bits++)
adb9e8e… drh 398 if (g.code[bits])
adb9e8e… drh 399 string_printf(&g.out, " %d[%d]", g.code[bits], bits);
adb9e8e… drh 400 string_printf(&g.out, "\n");
adb9e8e… drh 401 }
adb9e8e… drh 402
adb9e8e… drh 403 // remove entries as we drop back down in the recursion
adb9e8e… drh 404 g.code[len] = 0;
adb9e8e… drh 405 return;
adb9e8e… drh 406 }
adb9e8e… drh 407
adb9e8e… drh 408 // prune the tree if we can
adb9e8e… drh 409 if (been_here(syms, left, len, mem, rem))
adb9e8e… drh 410 return;
adb9e8e… drh 411
adb9e8e… drh 412 // we need to use at least this many bit patterns so that the code won't be
adb9e8e… drh 413 // incomplete at the next length (more bit patterns than symbols)
adb9e8e… drh 414 int least = (left << 1) - syms;
7ef7284… drh 415 if (least < 0)
7ef7284… drh 416 least = 0;
7ef7284… drh 417
adb9e8e… drh 418 // we can use at most this many bit patterns, lest there not be enough
adb9e8e… drh 419 // available for the remaining symbols at the maximum length (if there were
adb9e8e… drh 420 // no limit to the code length, this would become: most = left - 1)
adb9e8e… drh 421 int most = (((code_t)left << (g.max - len)) - syms) /
adb9e8e… drh 422 (((code_t)1 << (g.max - len)) - 1);
adb9e8e… drh 423
adb9e8e… drh 424 // occupy least table spaces, creating new sub-tables as needed
adb9e8e… drh 425 int use = least;
7ef7284… drh 426 while (rem < use) {
7ef7284… drh 427 use -= rem;
adb9e8e… drh 428 rem = 1 << (len - g.root);
7ef7284… drh 429 mem += rem;
7ef7284… drh 430 }
7ef7284… drh 431 rem -= use;
7ef7284… drh 432
adb9e8e… drh 433 // examine codes from here, updating table space as we go
7ef7284… drh 434 for (use = least; use <= most; use++) {
adb9e8e… drh 435 g.code[len] = use;
adb9e8e… drh 436 examine(syms - use, (left - use) << 1, len + 1,
adb9e8e… drh 437 mem + (rem ? 1 << (len - g.root) : 0), rem << 1);
7ef7284… drh 438 if (rem == 0) {
adb9e8e… drh 439 rem = 1 << (len - g.root);
7ef7284… drh 440 mem += rem;
7ef7284… drh 441 }
7ef7284… drh 442 rem--;
7ef7284… drh 443 }
7ef7284… drh 444
adb9e8e… drh 445 // remove entries as we drop back down in the recursion
adb9e8e… drh 446 g.code[len] = 0;
adb9e8e… drh 447 }
adb9e8e… drh 448
adb9e8e… drh 449 // Look at all sub-codes starting with root + 1 bits. Look at only the valid
adb9e8e… drh 450 // intermediate code states (syms, left, len). For each completed code,
adb9e8e… drh 451 // calculate the amount of memory required by inflate to build the decoding
adb9e8e… drh 452 // tables. Find the maximum amount of memory required and show the codes that
adb9e8e… drh 453 // require that maximum.
adb9e8e… drh 454 local void enough(int syms) {
adb9e8e… drh 455 // clear code
adb9e8e… drh 456 for (int n = 0; n <= g.max; n++)
adb9e8e… drh 457 g.code[n] = 0;
adb9e8e… drh 458
adb9e8e… drh 459 // look at all (root + 1) bit and longer codes
adb9e8e… drh 460 string_clear(&g.out); // empty saved results
adb9e8e… drh 461 g.large = 1 << g.root; // base table
adb9e8e… drh 462 if (g.root < g.max) // otherwise, there's only a base table
adb9e8e… drh 463 for (int n = 3; n <= syms; n++)
adb9e8e… drh 464 for (int left = 2; left < n; left += 2) {
adb9e8e… drh 465 // look at all reachable (root + 1) bit nodes, and the
adb9e8e… drh 466 // resulting codes (complete at root + 2 or more)
adb9e8e… drh 467 size_t index = map(n, left, g.root + 1);
adb9e8e… drh 468 if (g.root + 1 < g.max && g.num[index]) // reachable node
adb9e8e… drh 469 examine(n, left, g.root + 1, 1 << g.root, 0);
adb9e8e… drh 470
adb9e8e… drh 471 // also look at root bit codes with completions at root + 1
adb9e8e… drh 472 // bits (not saved in num, since complete), just in case
adb9e8e… drh 473 if (g.num[index - 1] && n <= left << 1)
adb9e8e… drh 474 examine((n - left) << 1, (n - left) << 1, g.root + 1,
adb9e8e… drh 475 1 << g.root, 0);
adb9e8e… drh 476 }
adb9e8e… drh 477
adb9e8e… drh 478 // done
adb9e8e… drh 479 printf("maximum of %d table entries for root = %d\n", g.large, g.root);
adb9e8e… drh 480 fputs(g.out.str, stdout);
adb9e8e… drh 481 }
adb9e8e… drh 482
adb9e8e… drh 483 // Examine and show the total number of possible prefix codes for a given
adb9e8e… drh 484 // maximum number of symbols, initial root table size, and maximum code length
adb9e8e… drh 485 // in bits -- those are the command arguments in that order. The default values
adb9e8e… drh 486 // are 286, 9, and 15 respectively, for the deflate literal/length code. The
adb9e8e… drh 487 // possible codes are counted for each number of coded symbols from two to the
adb9e8e… drh 488 // maximum. The counts for each of those and the total number of codes are
a9e589c… florian 489 // shown. The maximum number of inflate table entries is then calculated across
adb9e8e… drh 490 // all possible codes. Each new maximum number of table entries and the
adb9e8e… drh 491 // associated sub-code (starting at root + 1 == 10 bits) is shown.
adb9e8e… drh 492 //
adb9e8e… drh 493 // To count and examine prefix codes that are not length-limited, provide a
adb9e8e… drh 494 // maximum length equal to the number of symbols minus one.
adb9e8e… drh 495 //
adb9e8e… drh 496 // For the deflate literal/length code, use "enough". For the deflate distance
adb9e8e… drh 497 // code, use "enough 30 6".
adb9e8e… drh 498 int main(int argc, char **argv) {
adb9e8e… drh 499 // set up globals for cleanup()
adb9e8e… drh 500 g.code = NULL;
adb9e8e… drh 501 g.num = NULL;
adb9e8e… drh 502 g.done = NULL;
adb9e8e… drh 503 string_init(&g.out);
adb9e8e… drh 504
adb9e8e… drh 505 // get arguments -- default to the deflate literal/length code
adb9e8e… drh 506 int syms = 286;
adb9e8e… drh 507 g.root = 9;
adb9e8e… drh 508 g.max = 15;
7ef7284… drh 509 if (argc > 1) {
7ef7284… drh 510 syms = atoi(argv[1]);
7ef7284… drh 511 if (argc > 2) {
adb9e8e… drh 512 g.root = atoi(argv[2]);
bb4776e… jan.nijtmans 513 if (argc > 3)
adb9e8e… drh 514 g.max = atoi(argv[3]);
bb4776e… jan.nijtmans 515 }
7ef7284… drh 516 }
adb9e8e… drh 517 if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) {
7ef7284… drh 518 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
bb4776e… jan.nijtmans 519 stderr);
7ef7284… drh 520 return 1;
7ef7284… drh 521 }
7ef7284… drh 522
adb9e8e… drh 523 // if not restricting the code length, the longest is syms - 1
adb9e8e… drh 524 if (g.max > syms - 1)
adb9e8e… drh 525 g.max = syms - 1;
adb9e8e… drh 526
adb9e8e… drh 527 // determine the number of bits in a code_t
adb9e8e… drh 528 int bits = 0;
adb9e8e… drh 529 for (code_t word = 1; word; word <<= 1)
adb9e8e… drh 530 bits++;
adb9e8e… drh 531
adb9e8e… drh 532 // make sure that the calculation of most will not overflow
adb9e8e… drh 533 if (g.max > bits || (code_t)(syms - 2) >= ((code_t)-1 >> (g.max - 1))) {
7ef7284… drh 534 fputs("abort: code length too long for internal types\n", stderr);
7ef7284… drh 535 return 1;
7ef7284… drh 536 }
7ef7284… drh 537
adb9e8e… drh 538 // reject impossible code requests
adb9e8e… drh 539 if ((code_t)(syms - 1) > ((code_t)1 << g.max) - 1) {
adb9e8e… drh 540 fprintf(stderr, "%d symbols cannot be coded in %d bits\n",
adb9e8e… drh 541 syms, g.max);
adb9e8e… drh 542 return 1;
adb9e8e… drh 543 }
adb9e8e… drh 544
adb9e8e… drh 545 // allocate code vector
adb9e8e… drh 546 g.code = calloc(g.max + 1, sizeof(int));
adb9e8e… drh 547 assert(g.code != NULL && "out of memory");
adb9e8e… drh 548
adb9e8e… drh 549 // determine size of saved results array, checking for overflows,
adb9e8e… drh 550 // allocate and clear the array (set all to zero with calloc())
adb9e8e… drh 551 if (syms == 2) // iff max == 1
adb9e8e… drh 552 g.num = NULL; // won't be saving any results
adb9e8e… drh 553 else {
adb9e8e… drh 554 g.size = syms >> 1;
adb9e8e… drh 555 int n = (syms - 1) >> 1;
adb9e8e… drh 556 assert(g.size <= (size_t)-1 / n && "overflow");
adb9e8e… drh 557 g.size *= n;
adb9e8e… drh 558 n = g.max - 1;
adb9e8e… drh 559 assert(g.size <= (size_t)-1 / n && "overflow");
adb9e8e… drh 560 g.size *= n;
adb9e8e… drh 561 g.num = calloc(g.size, sizeof(big_t));
adb9e8e… drh 562 assert(g.num != NULL && "out of memory");
adb9e8e… drh 563 }
adb9e8e… drh 564
adb9e8e… drh 565 // count possible codes for all numbers of symbols, add up counts
adb9e8e… drh 566 big_t sum = 0;
adb9e8e… drh 567 for (int n = 2; n <= syms; n++) {
adb9e8e… drh 568 big_t got = count(n, 2, 1);
adb9e8e… drh 569 sum += got;
adb9e8e… drh 570 assert(got != (big_t)-1 && sum >= got && "overflow");
adb9e8e… drh 571 }
adb9e8e… drh 572 printf("%"PRIbig" total codes for 2 to %d symbols", sum, syms);
adb9e8e… drh 573 if (g.max < syms - 1)
adb9e8e… drh 574 printf(" (%d-bit length limit)\n", g.max);
7ef7284… drh 575 else
7ef7284… drh 576 puts(" (no length limit)");
7ef7284… drh 577
adb9e8e… drh 578 // allocate and clear done array for been_here()
adb9e8e… drh 579 if (syms == 2)
adb9e8e… drh 580 g.done = NULL;
adb9e8e… drh 581 else {
adb9e8e… drh 582 g.done = calloc(g.size, sizeof(struct tab));
adb9e8e… drh 583 assert(g.done != NULL && "out of memory");
adb9e8e… drh 584 }
adb9e8e… drh 585
adb9e8e… drh 586 // find and show maximum inflate table usage
adb9e8e… drh 587 if (g.root > g.max) // reduce root to max length
adb9e8e… drh 588 g.root = g.max;
adb9e8e… drh 589 if ((code_t)syms < ((code_t)1 << (g.root + 1)))
adb9e8e… drh 590 enough(syms);
adb9e8e… drh 591 else
adb9e8e… drh 592 fputs("cannot handle minimum code lengths > root", stderr);
adb9e8e… drh 593
adb9e8e… drh 594 // done
7ef7284… drh 595 cleanup();
7ef7284… drh 596 return 0;
7ef7284… drh 597 }

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button