Lines Matching refs:root
12 As inflate does, decrease root for short codes
13 Refuse cases where inflate would increase root
14 1.3 17 Feb 2008 Add argument for initial root table size
15 Fix bug for initial root table size == max - 1
41 speed. There is a single first-level table to decode codes up to root bits
42 in length (root == 9 in the current inflate implementation). The table
43 has 1 << root entries and is indexed by the next root bits of input. Codes
44 shorter than root bits have replicated table entries, so that the correct
46 the code is longer than root bits, then the table entry points to a second-
48 that root-bit prefix. If that longest code has length len, then the table
49 has size 1 << (len - root), to index the remaining bits in that set of
50 codes. Each subsequent root-bit prefix then has its own sub-table. The
53 all of the codes are shorter than root bits, then root is reduced to the
56 The inflate algorithm also provides for small values of root (relative to
58 than root. In that case, root is increased to the length of the shortest
60 that the number of symbols is less than 2^(root + 1).
71 Second, the intermediate states that lead to (root + 1) bit or longer codes
74 codes of root bits or less in length.) Third, the visited states in the
77 Beginning the code examination at (root + 1) bit codes, which is enabled by
168 local int root; /* size of base code table in bits */
265 mem -= 1 << root;
291 length = 1 << (len - root);
317 the current sub-table is rem. Uses the globals max, code, root, large, and
333 rem = 1 << (len - root);
342 for (use = root + 1; use <= max; use++)
374 rem = 1 << (len - root);
383 mem + (rem ? 1 << (len - root) : 0), rem << 1);
385 rem = 1 << (len - root);
395 /* Look at all sub-codes starting with root + 1 bits. Look at only the valid
399 requires that maximum. Uses the globals max, root, and num. */
410 /* look at all (root + 1) bit and longer codes */
411 large = 1 << root; /* base table */
412 if (root < max) /* otherwise, there's only a base table */
416 /* look at all reachable (root + 1) bit nodes, and the
417 resulting codes (complete at root + 2 or more) */
418 index = INDEX(n, left, root + 1);
419 if (root + 1 < max && num[index]) /* reachable node */
420 examine(n, root + 1, left, 1 << root, 0);
422 /* also look at root bit codes with completions at root + 1
425 examine((n - left) << 1, root + 1, (n - left) << 1,
426 1 << root, 0);
435 maximum number of symbols, initial root table size, and maximum code length
442 associated sub-code (starting at root + 1 == 10 bits) is shown.
469 root = 9;
474 root = atoi(argv[2]);
479 if (argc > 4 || syms < 2 || root < 1 || max < 1) {
480 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
559 if (root > max) /* reduce root to max length */
560 root = max;
561 if (syms < ((code_t)1 << (root + 1)))
564 puts("cannot handle minimum code lengths > root");