Lines Matching defs:code
1 /* enough.c -- determine the maximum size of inflate's Huffman code tables over
19 Clean up code indentation
20 1.5 5 Aug 2018 Clean up code style, formatting, and comments
26 maximum code length in bits to determine the maximum table size for zlib's
31 in the same code for the counting, as do permutations of the assignments of
34 We build a code from shorter to longer lengths, determining how many symbols
36 be coded, what the last code length used was, and how many bit patterns of
37 that length remain unused. Then we add one to the code length and double the
38 number of unused patterns to graduate to the next code length. We then
39 assign all portions of the remaining symbols to that code length that
40 preserve the properties of a correct and eventually complete code. Those
51 pointed to regardless of the bits that follow the short code. If the code is
53 The size of that table is determined by the longest code with that root-bit
54 prefix. If that longest code has length len, then the table has size 1 <<
57 table entries required by the code is calculated incrementally as the number
59 than root bits, then root is reduced to the longest code length, resulting
63 the log2 of the number of symbols), where the shortest code has more bits
65 code. This program, by design, does not handle that case, so it is verified
69 the default arguments), the intermediate states in the build-up of a code
72 the maximum code length in bits. However this is a very small price to pay
83 Beginning the code examination at (root + 1) bit codes, which is enabled by
93 and a large maximum code length, so multiple-precision arithmetic would need
99 remaining at the maximum length. This limits the maximum code length to the
101 the symbols in a flat code. The code_t type identifies where the bit-pattern
115 typedef uintmax_t big_t; // type for code counting
125 syms: number of symbols remaining to code
131 syms: 3..totsym (totsym == total symbols to code)
133 len: 1..max - 1 (max == maximum code length in bits)
135 syms == 2 is not saved since that immediately leads to a single code. left
138 ends at syms-1 since left == syms immediately results in a single code.
139 (left > sym is not allowed since that would result in an incomplete code.)
140 len is less than max, since the code completes immediately when len == max.
226 int root; // size of base code table in bits
227 int large; // largest code table so far
231 int *code; // number of symbols assigned to each bit length
232 big_t *num; // saved results array for code counting
253 free(g.code); g.code = NULL;
262 // see if only one possible code
275 // we need to use at least this many bit patterns so that the code won't be
283 // no limit to the code length, this would become: most = left - 1)
359 // number of code structures used so far is mem, and the number remaining in
362 // see if we have a complete code
364 // set the last code entry
365 g.code[len] = left;
367 // complete computation of memory used by this code
375 // if this is at the maximum, show the sub-code
384 // compute the starting state for this sub-code
388 syms += g.code[bits];
389 left -= g.code[bits];
394 // print the starting state and the resulting sub-code to g.out
398 if (g.code[bits])
399 string_printf(&g.out, " %d[%d]", g.code[bits], bits);
404 g.code[len] = 0;
412 // we need to use at least this many bit patterns so that the code won't be
420 // no limit to the code length, this would become: most = left - 1)
435 g.code[len] = use;
446 g.code[len] = 0;
450 // intermediate code states (syms, left, len). For each completed code,
455 // clear code
457 g.code[n] = 0;
484 // maximum number of symbols, initial root table size, and maximum code length
486 // are 286, 9, and 15 respectively, for the deflate literal/length code. The
491 // associated sub-code (starting at root + 1 == 10 bits) is shown.
496 // For the deflate literal/length code, use "enough". For the deflate distance
497 // code, use "enough 30 6".
500 g.code = NULL;
505 // get arguments -- default to the deflate literal/length code
523 // if not restricting the code length, the longest is syms - 1
534 fputs("abort: code length too long for internal types\n", stderr);
538 // reject impossible code requests
545 // allocate code vector
546 g.code = calloc(g.max + 1, sizeof(int));
547 assert(g.code != NULL && "out of memory");
592 fputs("cannot handle minimum code lengths > root", stderr);