Lines Matching defs: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
46 speed. There is a single first-level table to decode codes up to root bits
47 in length (root == 9 for literal/length codes and root == 6 for distance
48 codes, in the current inflate implementation). The base table has 1 << root
49 entries and is indexed by the next root bits of input. Codes shorter than
50 root bits have replicated table entries, so that the correct entry is
52 longer than root bits, then the table entry points to a second-level table.
53 The size of that table is determined by the longest code with that root-bit
55 (len - root), to index the remaining bits in that set of codes. Each
56 subsequent root-bit prefix then has its own sub-table. The total number of
59 than root bits, then root is reduced to the longest code length, resulting
62 The inflate algorithm also provides for small values of root (relative to
64 than root. In that case, root is increased to the length of the shortest
66 that the number of symbols is less than 1 << (root + 1).
77 Second, the intermediate states that lead to (root + 1) bit or longer codes
80 codes of root bits or less in length.) Third, the visited states in the
83 Beginning the code examination at (root + 1) bit codes, which is enabled by
226 int root; // size of base code table in bits
311 mem -= 1 << g.root; // mem always includes the root table
370 rem = 1 << (len - g.root);
387 for (int bits = g.max; bits > g.root; bits--) {
396 syms, g.root + 1, ((1 << g.root) - left) << 1);
397 for (int bits = g.root + 1; bits <= g.max; bits++)
428 rem = 1 << (len - g.root);
437 mem + (rem ? 1 << (len - g.root) : 0), rem << 1);
439 rem = 1 << (len - g.root);
449 // Look at all sub-codes starting with root + 1 bits. Look at only the valid
459 // look at all (root + 1) bit and longer codes
461 g.large = 1 << g.root; // base table
462 if (g.root < g.max) // otherwise, there's only a base table
465 // look at all reachable (root + 1) bit nodes, and the
466 // resulting codes (complete at root + 2 or more)
467 size_t index = map(n, left, g.root + 1);
468 if (g.root + 1 < g.max && g.num[index]) // reachable node
469 examine(n, left, g.root + 1, 1 << g.root, 0);
471 // also look at root bit codes with completions at root + 1
474 examine((n - left) << 1, (n - left) << 1, g.root + 1,
475 1 << g.root, 0);
479 printf("maximum of %d table entries for root = %d\n", g.large, g.root);
484 // maximum number of symbols, initial root table size, and maximum code length
491 // associated sub-code (starting at root + 1 == 10 bits) is shown.
507 g.root = 9;
512 g.root = atoi(argv[2]);
517 if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) {
518 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
587 if (g.root > g.max) // reduce root to max length
588 g.root = g.max;
589 if ((code_t)syms < ((code_t)1 << (g.root + 1)))
592 fputs("cannot handle minimum code lengths > root", stderr);