site/j2s/JU/Tree.js

   1 Clazz.declarePackage ("JU");
   2 c$ = Clazz.decorateAsClass (function () {
   3 this.dyn_tree = null;
   4 this.max_code = 0;
   5 this.stat_desc = null;
   6 Clazz.instantialize (this, arguments);
   7 }, JU, "Tree");
   8 c$.d_code = Clazz.defineMethod (c$, "d_code",
   9 function (dist) {
  10 return ((dist) < 256 ? JU.Tree._dist_code[dist] : JU.Tree._dist_code[256 + ((dist) >>> 7)]);
  11 }, "~N");
  12 Clazz.defineMethod (c$, "gen_bitlen",
  13 function (s) {
  14 var tree = this.dyn_tree;
  15 var stree = this.stat_desc.static_tree;
  16 var extra = this.stat_desc.extra_bits;
  17 var base = this.stat_desc.extra_base;
  18 var max_length = this.stat_desc.max_length;
  19 var h;
  20 var n;
  21 var m;
  22 var bits;
  23 var xbits;
  24 var f;
  25 var overflow = 0;
  26 for (bits = 0; bits <= 15; bits++) s.bl_count[bits] = 0;
  27
  28 tree[s.heap[s.heap_max] * 2 + 1] = 0;
  29 for (h = s.heap_max + 1; h < 573; h++) {
  30 n = s.heap[h];
  31 bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
  32 if (bits > max_length) {
  33 bits = max_length;
  34 overflow++;
  35 }tree[n * 2 + 1] = bits;
  36 if (n > this.max_code) continue;
  37 s.bl_count[bits]++;
  38 xbits = 0;
  39 if (n >= base) xbits = extra[n - base];
  40 f = tree[n * 2];
  41 s.opt_len += f * (bits + xbits);
  42 if (stree != null) s.static_len += f * (stree[n * 2 + 1] + xbits);
  43 }
  44 if (overflow == 0) return;
  45 do {
  46 bits = max_length - 1;
  47 while (s.bl_count[bits] == 0) bits--;
  48
  49 s.bl_count[bits]--;
  50 s.bl_count[bits + 1] += 2;
  51 s.bl_count[max_length]--;
  52 overflow -= 2;
  53 } while (overflow > 0);
  54 for (bits = max_length; bits != 0; bits--) {
  55 n = s.bl_count[bits];
  56 while (n != 0) {
  57 m = s.heap[--h];
  58 if (m > this.max_code) continue;
  59 if (tree[m * 2 + 1] != bits) {
  60 s.opt_len += (bits - tree[m * 2 + 1]) * tree[m * 2];
  61 tree[m * 2 + 1] = bits;
  62 }n--;
  63 }
  64 }
  65 }, "JU.Deflate");
  66 Clazz.defineMethod (c$, "build_tree",
  67 function (s) {
  68 var tree = this.dyn_tree;
  69 var stree = this.stat_desc.static_tree;
  70 var elems = this.stat_desc.elems;
  71 var n;
  72 var m;
  73 var max_code = -1;
  74 var node;
  75 s.heap_len = 0;
  76 s.heap_max = 573;
  77 for (n = 0; n < elems; n++) {
  78 if (tree[n * 2] != 0) {
  79 s.heap[++s.heap_len] = max_code = n;
  80 s.depth[n] = 0;
  81 } else {
  82 tree[n * 2 + 1] = 0;
  83 }}
  84 while (s.heap_len < 2) {
  85 node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
  86 tree[node * 2] = 1;
  87 s.depth[node] = 0;
  88 s.opt_len--;
  89 if (stree != null) s.static_len -= stree[node * 2 + 1];
  90 }
  91 this.max_code = max_code;
  92 for (n = Clazz.doubleToInt (s.heap_len / 2); n >= 1; n--) s.pqdownheap (tree, n);
  93
  94 node = elems;
  95 do {
  96 n = s.heap[1];
  97 s.heap[1] = s.heap[s.heap_len--];
  98 s.pqdownheap (tree, 1);
  99 m = s.heap[1];
 100 s.heap[--s.heap_max] = n;
 101 s.heap[--s.heap_max] = m;
 102 tree[node * 2] = (tree[n * 2] + tree[m * 2]);
 103 s.depth[node] = (Math.max (s.depth[n], s.depth[m]) + 1);
 104 tree[n * 2 + 1] = tree[m * 2 + 1] = node;
 105 s.heap[1] = node++;
 106 s.pqdownheap (tree, 1);
 107 } while (s.heap_len >= 2);
 108 s.heap[--s.heap_max] = s.heap[1];
 109 this.gen_bitlen (s);
 110 JU.Tree.gen_codes (tree, max_code, s.bl_count);
 111 }, "JU.Deflate");
 112 c$.gen_codes = Clazz.defineMethod (c$, "gen_codes",
 113 function (tree, max_code, bl_count) {
 114 var code = 0;
 115 var bits;
 116 var n;
 117 JU.Tree.next_code[0] = 0;
 118 for (bits = 1; bits <= 15; bits++) {
 119 JU.Tree.next_code[bits] = code = ((code + bl_count[bits - 1]) << 1);
 120 }
 121 for (n = 0; n <= max_code; n++) {
 122 var len = tree[n * 2 + 1];
 123 if (len == 0) continue;
 124 tree[n * 2] = (JU.Tree.bi_reverse (JU.Tree.next_code[len]++, len));
 125 }
 126 }, "~A,~N,~A");
 127 c$.bi_reverse = Clazz.defineMethod (c$, "bi_reverse",
 128 function (code, len) {
 129 var res = 0;
 130 do {
 131 res |= code & 1;
 132 code >>>= 1;
 133 res <<= 1;
 134 } while (--len > 0);
 135 return res >>> 1;
 136 }, "~N,~N");
 137 Clazz.defineStatics (c$,
 138 "MAX_BITS", 15,
 139 "LITERALS", 256,
 140 "LENGTH_CODES", 29,
 141 "L_CODES", (286),
 142 "HEAP_SIZE", (573),
 143 "MAX_BL_BITS", 7,
 144 "END_BLOCK", 256,
 145 "REP_3_6", 16,
 146 "REPZ_3_10", 17,
 147 "REPZ_11_138", 18,
 148 "extra_lbits",  Clazz.newIntArray (-1, [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]),
 149 "extra_dbits",  Clazz.newIntArray (-1, [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13]),
 150 "extra_blbits",  Clazz.newIntArray (-1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7]),
 151 "bl_order",  Clazz.newByteArray (-1, [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]),
 152 "Buf_size", 16,
 153 "DIST_CODE_LEN", 512,
 154 "_dist_code",  Clazz.newByteArray (-1, [0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29]),
 155 "_length_code",  Clazz.newByteArray (-1, [0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28]),
 156 "base_length",  Clazz.newIntArray (-1, [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0]),
 157 "base_dist",  Clazz.newIntArray (-1, [0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576]),
 158 "next_code",  Clazz.newShortArray (16, 0));