site/j2s/JU/Tree.js

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