Lines Matching refs:code
1 /* enough.c -- determine the maximum size of inflate's Huffman code tables over
21 maximum code length in bits to determine the maximum table size for zilb's
26 in the same code for the counting, as do permutations of the assignments of
29 We build a code from shorter to longer lengths, determining how many symbols
31 be coded, what the last code length used was, and how many bit patterns of
32 that length remain unused. Then we add one to the code length and double the
33 number of unused patterns to graduate to the next code length. We then
34 assign all portions of the remaining symbols to that code length that
35 preserve the properties of a correct and eventually complete code. Those
45 entry is pointed to regardless of the bits that follow the short code. If
46 the code is longer than root bits, then the table entry points to a second-
47 level table. The size of that table is determined by the longest code with
48 that root-bit prefix. If that longest code has length len, then the table
51 total number of table entries required by the code is calculated
54 longest code length, resulting in a single, smaller, one-level table.
57 the log2 of the number of symbols), where the shortest code has more bits
59 code. This program, by design, does not handle that case, so it is verified
63 the default arguments), the intermediate states in the build-up of a code
66 the maximum code length in bits. However this is a very small price to pay
77 Beginning the code examination at (root + 1) bit codes, which is enabled by
87 symbols and a large maximum code length, so multiple-precision arithmetic
94 code length to the number of bits in a long long minus the number of bits
95 needed to represent the symbols in a flat code. The code_t type identifies
107 typedef unsigned long long big_t; /* type for code counting */
116 syms: number of symbols remaining to code
122 syms: 3..totsym (totsym == total symbols to code)
124 len: 1..max - 1 (max == maximum code length in bits)
126 syms == 2 is not saved since that immediately leads to a single code. left
129 left ends at syms-1 since left == syms immediately results in a single code.
130 (left > sym is not allowed since that would result in an incomplete code.)
131 len is less than max, since the code completes immediately when len == max.
168 local int root; /* size of base code table in bits */
169 local int large; /* largest code table so far */
171 local int *code; /* number of symbols assigned to each bit length */
172 local big_t *num; /* saved results array for code counting */
178 /* Free allocated space. Uses globals code, num, and done. */
191 if (code != NULL)
192 free(code);
209 /* see if only one possible code */
222 /* we need to use at least this many bit patterns so that the code won't be
230 no limit to the code length, this would become: most = left - 1) */
316 number of code structures used so far is mem, and the number remaining in
317 the current sub-table is rem. Uses the globals max, code, root, large, and
325 /* see if we have a complete code */
327 /* set the last code entry */
328 code[len] = left;
330 /* complete computation of memory used by this code */
338 /* if this is a new maximum, show the entries used and the sub-code */
343 if (code[use])
344 printf("%d[%d] ", code[use], use);
350 code[len] = 0;
358 /* we need to use at least this many bit patterns so that the code won't be
366 no limit to the code length, this would become: most = left - 1) */
381 code[len] = use;
392 code[len] = 0;
396 intermediate code states (syms, left, len). For each completed code,
398 tables. Find the maximum amount of memory required and show the code that
406 /* clear code */
408 code[n] = 0;
435 maximum number of symbols, initial root table size, and maximum code length
437 values are 286, 9, and 15 respectively, for the deflate literal/length code.
442 associated sub-code (starting at root + 1 == 10 bits) is shown.
447 For the deflate literal/length code, use "enough". For the deflate distance
448 code, use "enough 30 6".
457 int syms; /* total number of symbols to code */
458 int n; /* number of symbols to code for this run */
463 code = NULL;
467 /* get arguments -- default to the deflate literal/length code */
485 /* if not restricting the code length, the longest is syms - 1 */
496 fputs("abort: code length too long for internal types\n", stderr);
500 /* reject impossible code requests */
507 /* allocate code vector */
508 code = calloc(max + 1, sizeof(int));
509 if (code == NULL) {
564 puts("cannot handle minimum code lengths > root");