| 171 | }; |
| 172 | // creates code lengths from a frequency table |
| 173 | var hTree = function (d, mb) { |
| 174 | // Need extra info to make a tree |
| 175 | var t = []; |
| 176 | for (var i = 0; i < d.length; ++i) { |
| 177 | if (d[i]) t.push({ s: i, f: d[i] }); |
| 178 | } |
| 179 | var s = t.length; |
| 180 | var t2 = t.slice(); |
| 181 | if (!s) return { t: et, l: 0 }; |
| 182 | if (s == 1) { |
| 183 | var v = new u8(t[0].s + 1); |
| 184 | v[t[0].s] = 1; |
| 185 | return { t: v, l: 1 }; |
| 186 | } |
| 187 | t.sort(function (a, b) { |
| 188 | return a.f - b.f; |
| 189 | }); |
| 190 | // after i2 reaches last ind, will be stopped |
| 191 | // freq must be greater than largest possible number of symbols |
| 192 | t.push({ s: -1, f: 25001 }); |
| 193 | var l = t[0], |
| 194 | r = t[1], |
| 195 | i0 = 0, |
| 196 | i1 = 1, |
| 197 | i2 = 2; |
| 198 | t[0] = { s: -1, f: l.f + r.f, l: l, r: r }; |
| 199 | // efficient algorithm from UZIP.js |
| 200 | // i0 is lookbehind, i2 is lookahead - after processing two low-freq |
| 201 | // symbols that combined have high freq, will start processing i2 (high-freq, |
| 202 | // non-composite) symbols instead |
| 203 | // see https://reddit.com/r/photopea/comments/ikekht/uzipjs_questions/ |
| 204 | while (i1 != s - 1) { |
| 205 | l = t[t[i0].f < t[i2].f ? i0++ : i2++]; |
| 206 | r = t[i0 != i1 && t[i0].f < t[i2].f ? i0++ : i2++]; |
| 207 | t[i1++] = { s: -1, f: l.f + r.f, l: l, r: r }; |
| 208 | } |
| 209 | var maxSym = t2[0].s; |
| 210 | for (var i = 1; i < s; ++i) { |
| 211 | if (t2[i].s > maxSym) maxSym = t2[i].s; |
| 212 | } |
| 213 | // code lengths |
| 214 | var tr = new u16(maxSym + 1); |
| 215 | // max bits in tree |
| 216 | var mbt = ln(t[i1 - 1], tr, 0); |
| 217 | if (mbt > mb) { |
| 218 | // more algorithms from UZIP.js |
| 219 | // TODO: find out how this code works (debt) |
| 220 | // ind debt |
| 221 | var i = 0, |
| 222 | dt = 0; |
| 223 | // left cost |
| 224 | var lft = mbt - mb, |
| 225 | cst = 1 << lft; |
| 226 | t2.sort(function (a, b) { |
| 227 | return tr[b.s] - tr[a.s] || a.f - b.f; |
| 228 | }); |
| 229 | for (; i < s; ++i) { |
| 230 | var i2_1 = t2[i].s; |