← Back to branch summary

~holger-seelig/cobweb.js/trunk

« back to all changes in this revision

Viewing changes to src/lib/pako/benchmark/implementations/inflate-dankogai/rawinflate.js

  • Committer: Holger Seelig
  • Date: 2017-08-22 04:53:24 UTC
  • Revision ID: holger.seelig@yahoo.de-20170822045324-4of4xxgt79669gbt
Switched to npm.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/pako/benchmark/implementations/inflate-dankogai/rawinflate.js
 
1
/*
 
2
 * $Id: rawinflate.js,v 0.3 2013/04/09 14:25:38 dankogai Exp dankogai $
 
3
 *
 
4
 * GNU General Public License, version 2 (GPL-2.0)
 
5
 *   http://opensource.org/licenses/GPL-2.0
 
6
 * original:
 
7
 *   http://www.onicos.com/staff/iz/amuse/javascript/expert/inflate.txt
 
8
 */
 
9
 
 
10
(function(ctx){
 
11
 
 
12
/* Copyright (C) 1999 Masanao Izumo <iz@onicos.co.jp>
 
13
 * Version: 1.0.0.1
 
14
 * LastModified: Dec 25 1999
 
15
 */
 
16
 
 
17
/* Interface:
 
18
 * data = zip_inflate(src);
 
19
 */
 
20
 
 
21
/* constant parameters */
 
22
var zip_WSIZE = 32768;          // Sliding Window size
 
23
var zip_STORED_BLOCK = 0;
 
24
var zip_STATIC_TREES = 1;
 
25
var zip_DYN_TREES    = 2;
 
26
 
 
27
/* for inflate */
 
28
var zip_lbits = 9;              // bits in base literal/length lookup table
 
29
var zip_dbits = 6;              // bits in base distance lookup table
 
30
var zip_INBUFSIZ = 32768;       // Input buffer size
 
31
var zip_INBUF_EXTRA = 64;       // Extra buffer
 
32
 
 
33
/* variables (inflate) */
 
34
var zip_slide;
 
35
var zip_wp;                     // current position in slide
 
36
var zip_fixed_tl = null;        // inflate static
 
37
var zip_fixed_td;               // inflate static
 
38
var zip_fixed_bl, fixed_bd;     // inflate static
 
39
var zip_bit_buf;                // bit buffer
 
40
var zip_bit_len;                // bits in bit buffer
 
41
var zip_method;
 
42
var zip_eof;
 
43
var zip_copy_leng;
 
44
var zip_copy_dist;
 
45
var zip_tl, zip_td;     // literal/length and distance decoder tables
 
46
var zip_bl, zip_bd;     // number of bits decoded by tl and td
 
47
 
 
48
var zip_inflate_data;
 
49
var zip_inflate_pos;
 
50
 
 
51
 
 
52
/* constant tables (inflate) */
 
53
var zip_MASK_BITS = new Array(
 
54
    0x0000,
 
55
    0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
 
56
    0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff);
 
57
// Tables for deflate from PKZIP's appnote.txt.
 
58
var zip_cplens = new Array( // Copy lengths for literal codes 257..285
 
59
    3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
 
60
    35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0);
 
61
/* note: see note #13 above about the 258 in this list. */
 
62
var zip_cplext = new Array( // Extra bits for literal codes 257..285
 
63
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
 
64
    3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99); // 99==invalid
 
65
var zip_cpdist = new Array( // Copy offsets for distance codes 0..29
 
66
    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
 
67
    257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
 
68
    8193, 12289, 16385, 24577);
 
69
var zip_cpdext = new Array( // Extra bits for distance codes
 
70
    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
 
71
    7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
 
72
    12, 12, 13, 13);
 
73
var zip_border = new Array(  // Order of the bit length code lengths
 
74
    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15);
 
75
/* objects (inflate) */
 
76
 
 
77
var zip_HuftList = function() {
 
78
    this.next = null;
 
79
    this.list = null;
 
80
}
 
81
 
 
82
var zip_HuftNode = function() {
 
83
    this.e = 0; // number of extra bits or operation
 
84
    this.b = 0; // number of bits in this code or subcode
 
85
 
 
86
    // union
 
87
    this.n = 0; // literal, length base, or distance base
 
88
    this.t = null; // (zip_HuftNode) pointer to next level of table
 
89
}
 
90
 
 
91
var zip_HuftBuild = function(b, // code lengths in bits (all assumed <= BMAX)
 
92
                       n,       // number of codes (assumed <= N_MAX)
 
93
                       s,       // number of simple-valued codes (0..s-1)
 
94
                       d,       // list of base values for non-simple codes
 
95
                       e,       // list of extra bits for non-simple codes
 
96
                       mm       // maximum lookup bits
 
97
                   ) {
 
98
    this.BMAX = 16;   // maximum bit length of any code
 
99
    this.N_MAX = 288; // maximum number of codes in any set
 
100
    this.status = 0;    // 0: success, 1: incomplete table, 2: bad input
 
101
    this.root = null;   // (zip_HuftList) starting table
 
102
    this.m = 0;         // maximum lookup bits, returns actual
 
103
 
 
104
/* Given a list of code lengths and a maximum table size, make a set of
 
105
   tables to decode that set of codes.  Return zero on success, one if
 
106
   the given code set is incomplete (the tables are still built in this
 
107
   case), two if the input is invalid (all zero length codes or an
 
108
   oversubscribed set of lengths), and three if not enough memory.
 
109
   The code with value 256 is special, and the tables are constructed
 
110
   so that no bits beyond that code are fetched when that code is
 
111
   decoded. */
 
112
    {
 
113
        var a;                  // counter for codes of length k
 
114
        var c = new Array(this.BMAX+1); // bit length count table
 
115
        var el;                 // length of EOB code (value 256)
 
116
        var f;                  // i repeats in table every f entries
 
117
        var g;                  // maximum code length
 
118
        var h;                  // table level
 
119
        var i;                  // counter, current code
 
120
        var j;                  // counter
 
121
        var k;                  // number of bits in current code
 
122
        var lx = new Array(this.BMAX+1);        // stack of bits per table
 
123
        var p;                  // pointer into c[], b[], or v[]
 
124
        var pidx;               // index of p
 
125
        var q;                  // (zip_HuftNode) points to current table
 
126
        var r = new zip_HuftNode(); // table entry for structure assignment
 
127
        var u = new Array(this.BMAX); // zip_HuftNode[BMAX][]  table stack
 
128
        var v = new Array(this.N_MAX); // values in order of bit length
 
129
        var w;
 
130
        var x = new Array(this.BMAX+1);// bit offsets, then code stack
 
131
        var xp;                 // pointer into x or c
 
132
        var y;                  // number of dummy codes added
 
133
        var z;                  // number of entries in current table
 
134
        var o;
 
135
        var tail;               // (zip_HuftList)
 
136
 
 
137
        tail = this.root = null;
 
138
        for(i = 0; i < c.length; i++)
 
139
            c[i] = 0;
 
140
        for(i = 0; i < lx.length; i++)
 
141
            lx[i] = 0;
 
142
        for(i = 0; i < u.length; i++)
 
143
            u[i] = null;
 
144
        for(i = 0; i < v.length; i++)
 
145
            v[i] = 0;
 
146
        for(i = 0; i < x.length; i++)
 
147
            x[i] = 0;
 
148
 
 
149
        // Generate counts for each bit length
 
150
        el = n > 256 ? b[256] : this.BMAX; // set length of EOB code, if any
 
151
        p = b; pidx = 0;
 
152
        i = n;
 
153
        do {
 
154
            c[p[pidx]]++;       // assume all entries <= BMAX
 
155
            pidx++;
 
156
        } while(--i > 0);
 
157
        if(c[0] == n) { // null input--all zero length codes
 
158
            this.root = null;
 
159
            this.m = 0;
 
160
            this.status = 0;
 
161
            return;
 
162
        }
 
163
 
 
164
        // Find minimum and maximum length, bound *m by those
 
165
        for(j = 1; j <= this.BMAX; j++)
 
166
            if(c[j] != 0)
 
167
                break;
 
168
        k = j;                  // minimum code length
 
169
        if(mm < j)
 
170
            mm = j;
 
171
        for(i = this.BMAX; i != 0; i--)
 
172
            if(c[i] != 0)
 
173
                break;
 
174
        g = i;                  // maximum code length
 
175
        if(mm > i)
 
176
            mm = i;
 
177
 
 
178
        // Adjust last length count to fill out codes, if needed
 
179
        for(y = 1 << j; j < i; j++, y <<= 1)
 
180
            if((y -= c[j]) < 0) {
 
181
                this.status = 2;        // bad input: more codes than bits
 
182
                this.m = mm;
 
183
                return;
 
184
            }
 
185
        if((y -= c[i]) < 0) {
 
186
            this.status = 2;
 
187
            this.m = mm;
 
188
            return;
 
189
        }
 
190
        c[i] += y;
 
191
 
 
192
        // Generate starting offsets into the value table for each length
 
193
        x[1] = j = 0;
 
194
        p = c;
 
195
        pidx = 1;
 
196
        xp = 2;
 
197
        while(--i > 0)          // note that i == g from above
 
198
            x[xp++] = (j += p[pidx++]);
 
199
 
 
200
        // Make a table of values in order of bit lengths
 
201
        p = b; pidx = 0;
 
202
        i = 0;
 
203
        do {
 
204
            if((j = p[pidx++]) != 0)
 
205
                v[x[j]++] = i;
 
206
        } while(++i < n);
 
207
        n = x[g];                       // set n to length of v
 
208
 
 
209
        // Generate the Huffman codes and for each, make the table entries
 
210
        x[0] = i = 0;           // first Huffman code is zero
 
211
        p = v; pidx = 0;                // grab values in bit order
 
212
        h = -1;                 // no tables yet--level -1
 
213
        w = lx[0] = 0;          // no bits decoded yet
 
214
        q = null;                       // ditto
 
215
        z = 0;                  // ditto
 
216
 
 
217
        // go through the bit lengths (k already is bits in shortest code)
 
218
        for(; k <= g; k++) {
 
219
            a = c[k];
 
220
            while(a-- > 0) {
 
221
                // here i is the Huffman code of length k bits for value p[pidx]
 
222
                // make tables up to required level
 
223
                while(k > w + lx[1 + h]) {
 
224
                    w += lx[1 + h]; // add bits already decoded
 
225
                    h++;
 
226
 
 
227
                    // compute minimum size table less than or equal to *m bits
 
228
                    z = (z = g - w) > mm ? mm : z; // upper limit
 
229
                    if((f = 1 << (j = k - w)) > a + 1) { // try a k-w bit table
 
230
                        // too few codes for k-w bit table
 
231
                        f -= a + 1;     // deduct codes from patterns left
 
232
                        xp = k;
 
233
                        while(++j < z) { // try smaller tables up to z bits
 
234
                            if((f <<= 1) <= c[++xp])
 
235
                                break;  // enough codes to use up j bits
 
236
                            f -= c[xp]; // else deduct codes from patterns
 
237
                        }
 
238
                    }
 
239
                    if(w + j > el && w < el)
 
240
                        j = el - w;     // make EOB code end at table
 
241
                    z = 1 << j; // table entries for j-bit table
 
242
                    lx[1 + h] = j; // set table size in stack
 
243
 
 
244
                    // allocate and link in new table
 
245
                    q = new Array(z);
 
246
                    for(o = 0; o < z; o++) {
 
247
                        q[o] = new zip_HuftNode();
 
248
                    }
 
249
 
 
250
                    if(tail == null)
 
251
                        tail = this.root = new zip_HuftList();
 
252
                    else
 
253
                        tail = tail.next = new zip_HuftList();
 
254
                    tail.next = null;
 
255
                    tail.list = q;
 
256
                    u[h] = q;   // table starts after link
 
257
 
 
258
                    /* connect to last table, if there is one */
 
259
                    if(h > 0) {
 
260
                        x[h] = i;               // save pattern for backing up
 
261
                        r.b = lx[h];    // bits to dump before this table
 
262
                        r.e = 16 + j;   // bits in this table
 
263
                        r.t = q;                // pointer to this table
 
264
                        j = (i & ((1 << w) - 1)) >> (w - lx[h]);
 
265
                        u[h-1][j].e = r.e;
 
266
                        u[h-1][j].b = r.b;
 
267
                        u[h-1][j].n = r.n;
 
268
                        u[h-1][j].t = r.t;
 
269
                    }
 
270
                }
 
271
 
 
272
                // set up table entry in r
 
273
                r.b = k - w;
 
274
                if(pidx >= n)
 
275
                    r.e = 99;           // out of values--invalid code
 
276
                else if(p[pidx] < s) {
 
277
                    r.e = (p[pidx] < 256 ? 16 : 15); // 256 is end-of-block code
 
278
                    r.n = p[pidx++];    // simple code is just the value
 
279
                } else {
 
280
                    r.e = e[p[pidx] - s];       // non-simple--look up in lists
 
281
                    r.n = d[p[pidx++] - s];
 
282
                }
 
283
 
 
284
                // fill code-like entries with r //
 
285
                f = 1 << (k - w);
 
286
                for(j = i >> w; j < z; j += f) {
 
287
                    q[j].e = r.e;
 
288
                    q[j].b = r.b;
 
289
                    q[j].n = r.n;
 
290
                    q[j].t = r.t;
 
291
                }
 
292
 
 
293
                // backwards increment the k-bit code i
 
294
                for(j = 1 << (k - 1); (i & j) != 0; j >>= 1)
 
295
                    i ^= j;
 
296
                i ^= j;
 
297
 
 
298
                // backup over finished tables
 
299
                while((i & ((1 << w) - 1)) != x[h]) {
 
300
                    w -= lx[h];         // don't need to update q
 
301
                    h--;
 
302
                }
 
303
            }
 
304
        }
 
305
 
 
306
        /* return actual size of base table */
 
307
        this.m = lx[1];
 
308
 
 
309
        /* Return true (1) if we were given an incomplete table */
 
310
        this.status = ((y != 0 && g != 1) ? 1 : 0);
 
311
    } /* end of constructor */
 
312
}
 
313
 
 
314
 
 
315
/* routines (inflate) */
 
316
 
 
317
var zip_GET_BYTE = function() {
 
318
    if(zip_inflate_data.length == zip_inflate_pos)
 
319
        return -1;
 
320
    //return zip_inflate_data.charCodeAt(zip_inflate_pos++) & 0xff;
 
321
    return zip_inflate_data[zip_inflate_pos++];
 
322
}
 
323
 
 
324
var zip_NEEDBITS = function(n) {
 
325
    while(zip_bit_len < n) {
 
326
        zip_bit_buf |= zip_GET_BYTE() << zip_bit_len;
 
327
        zip_bit_len += 8;
 
328
    }
 
329
}
 
330
 
 
331
var zip_GETBITS = function(n) {
 
332
    return zip_bit_buf & zip_MASK_BITS[n];
 
333
}
 
334
 
 
335
var zip_DUMPBITS = function(n) {
 
336
    zip_bit_buf >>= n;
 
337
    zip_bit_len -= n;
 
338
}
 
339
 
 
340
var zip_inflate_codes = function(buff, off, size) {
 
341
    /* inflate (decompress) the codes in a deflated (compressed) block.
 
342
       Return an error code or zero if it all goes ok. */
 
343
    var e;              // table entry flag/number of extra bits
 
344
    var t;              // (zip_HuftNode) pointer to table entry
 
345
    var n;
 
346
 
 
347
    if(size == 0)
 
348
      return 0;
 
349
 
 
350
    // inflate the coded data
 
351
    n = 0;
 
352
    for(;;) {                   // do until end of block
 
353
        zip_NEEDBITS(zip_bl);
 
354
        t = zip_tl.list[zip_GETBITS(zip_bl)];
 
355
        e = t.e;
 
356
        while(e > 16) {
 
357
            if(e == 99)
 
358
                return -1;
 
359
            zip_DUMPBITS(t.b);
 
360
            e -= 16;
 
361
            zip_NEEDBITS(e);
 
362
            t = t.t[zip_GETBITS(e)];
 
363
            e = t.e;
 
364
        }
 
365
        zip_DUMPBITS(t.b);
 
366
 
 
367
        if(e == 16) {           // then it's a literal
 
368
            zip_wp &= zip_WSIZE - 1;
 
369
            buff[off + n++] = zip_slide[zip_wp++] = t.n;
 
370
            if(n == size)
 
371
                return size;
 
372
            continue;
 
373
        }
 
374
 
 
375
        // exit if end of block
 
376
        if(e == 15)
 
377
            break;
 
378
 
 
379
        // it's an EOB or a length
 
380
 
 
381
        // get length of block to copy
 
382
        zip_NEEDBITS(e);
 
383
        zip_copy_leng = t.n + zip_GETBITS(e);
 
384
        zip_DUMPBITS(e);
 
385
 
 
386
        // decode distance of block to copy
 
387
        zip_NEEDBITS(zip_bd);
 
388
        t = zip_td.list[zip_GETBITS(zip_bd)];
 
389
        e = t.e;
 
390
 
 
391
        while(e > 16) {
 
392
            if(e == 99)
 
393
                return -1;
 
394
            zip_DUMPBITS(t.b);
 
395
            e -= 16;
 
396
            zip_NEEDBITS(e);
 
397
            t = t.t[zip_GETBITS(e)];
 
398
            e = t.e;
 
399
        }
 
400
        zip_DUMPBITS(t.b);
 
401
        zip_NEEDBITS(e);
 
402
        zip_copy_dist = zip_wp - t.n - zip_GETBITS(e);
 
403
        zip_DUMPBITS(e);
 
404
 
 
405
        // do the copy
 
406
        while(zip_copy_leng > 0 && n < size) {
 
407
            zip_copy_leng--;
 
408
            zip_copy_dist &= zip_WSIZE - 1;
 
409
            zip_wp &= zip_WSIZE - 1;
 
410
            buff[off + n++] = zip_slide[zip_wp++]
 
411
                = zip_slide[zip_copy_dist++];
 
412
        }
 
413
 
 
414
        if(n == size)
 
415
            return size;
 
416
    }
 
417
 
 
418
    zip_method = -1; // done
 
419
    return n;
 
420
}
 
421
 
 
422
var zip_inflate_stored = function(buff, off, size) {
 
423
    /* "decompress" an inflated type 0 (stored) block. */
 
424
    var n;
 
425
 
 
426
    // go to byte boundary
 
427
    n = zip_bit_len & 7;
 
428
    zip_DUMPBITS(n);
 
429
 
 
430
    // get the length and its complement
 
431
    zip_NEEDBITS(16);
 
432
    n = zip_GETBITS(16);
 
433
    zip_DUMPBITS(16);
 
434
    zip_NEEDBITS(16);
 
435
    if(n != ((~zip_bit_buf) & 0xffff))
 
436
        return -1;                      // error in compressed data
 
437
    zip_DUMPBITS(16);
 
438
 
 
439
    // read and output the compressed data
 
440
    zip_copy_leng = n;
 
441
 
 
442
    n = 0;
 
443
    while(zip_copy_leng > 0 && n < size) {
 
444
        zip_copy_leng--;
 
445
        zip_wp &= zip_WSIZE - 1;
 
446
        zip_NEEDBITS(8);
 
447
        buff[off + n++] = zip_slide[zip_wp++] =
 
448
            zip_GETBITS(8);
 
449
        zip_DUMPBITS(8);
 
450
    }
 
451
 
 
452
    if(zip_copy_leng == 0)
 
453
      zip_method = -1; // done
 
454
    return n;
 
455
}
 
456
 
 
457
var zip_inflate_fixed = function(buff, off, size) {
 
458
    /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
 
459
       either replace this with a custom decoder, or at least precompute the
 
460
       Huffman tables. */
 
461
 
 
462
    // if first time, set up tables for fixed blocks
 
463
    if(zip_fixed_tl == null) {
 
464
        var i;                  // temporary variable
 
465
        var l = new Array(288); // length list for huft_build
 
466
        var h;  // zip_HuftBuild
 
467
 
 
468
        // literal table
 
469
        for(i = 0; i < 144; i++)
 
470
            l[i] = 8;
 
471
        for(; i < 256; i++)
 
472
            l[i] = 9;
 
473
        for(; i < 280; i++)
 
474
            l[i] = 7;
 
475
        for(; i < 288; i++)     // make a complete, but wrong code set
 
476
            l[i] = 8;
 
477
        zip_fixed_bl = 7;
 
478
 
 
479
        h = new zip_HuftBuild(l, 288, 257, zip_cplens, zip_cplext,
 
480
                              zip_fixed_bl);
 
481
        if(h.status != 0) {
 
482
            alert("HufBuild error: "+h.status);
 
483
            return -1;
 
484
        }
 
485
        zip_fixed_tl = h.root;
 
486
        zip_fixed_bl = h.m;
 
487
 
 
488
        // distance table
 
489
        for(i = 0; i < 30; i++) // make an incomplete code set
 
490
            l[i] = 5;
 
491
        zip_fixed_bd = 5;
 
492
 
 
493
        h = new zip_HuftBuild(l, 30, 0, zip_cpdist, zip_cpdext, zip_fixed_bd);
 
494
        if(h.status > 1) {
 
495
            zip_fixed_tl = null;
 
496
            alert("HufBuild error: "+h.status);
 
497
            return -1;
 
498
        }
 
499
        zip_fixed_td = h.root;
 
500
        zip_fixed_bd = h.m;
 
501
    }
 
502
 
 
503
    zip_tl = zip_fixed_tl;
 
504
    zip_td = zip_fixed_td;
 
505
    zip_bl = zip_fixed_bl;
 
506
    zip_bd = zip_fixed_bd;
 
507
    return zip_inflate_codes(buff, off, size);
 
508
}
 
509
 
 
510
var zip_inflate_dynamic = function(buff, off, size) {
 
511
    // decompress an inflated type 2 (dynamic Huffman codes) block.
 
512
    var i;              // temporary variables
 
513
    var j;
 
514
    var l;              // last length
 
515
    var n;              // number of lengths to get
 
516
    var t;              // (zip_HuftNode) literal/length code table
 
517
    var nb;             // number of bit length codes
 
518
    var nl;             // number of literal/length codes
 
519
    var nd;             // number of distance codes
 
520
    var ll = new Array(286+30); // literal/length and distance code lengths
 
521
    var h;              // (zip_HuftBuild)
 
522
 
 
523
    for(i = 0; i < ll.length; i++)
 
524
        ll[i] = 0;
 
525
 
 
526
    // read in table lengths
 
527
    zip_NEEDBITS(5);
 
528
    nl = 257 + zip_GETBITS(5);  // number of literal/length codes
 
529
    zip_DUMPBITS(5);
 
530
    zip_NEEDBITS(5);
 
531
    nd = 1 + zip_GETBITS(5);    // number of distance codes
 
532
    zip_DUMPBITS(5);
 
533
    zip_NEEDBITS(4);
 
534
    nb = 4 + zip_GETBITS(4);    // number of bit length codes
 
535
    zip_DUMPBITS(4);
 
536
    if(nl > 286 || nd > 30)
 
537
      return -1;                // bad lengths
 
538
 
 
539
    // read in bit-length-code lengths
 
540
    for(j = 0; j < nb; j++)
 
541
    {
 
542
        zip_NEEDBITS(3);
 
543
        ll[zip_border[j]] = zip_GETBITS(3);
 
544
        zip_DUMPBITS(3);
 
545
    }
 
546
    for(; j < 19; j++)
 
547
        ll[zip_border[j]] = 0;
 
548
 
 
549
    // build decoding table for trees--single level, 7 bit lookup
 
550
    zip_bl = 7;
 
551
    h = new zip_HuftBuild(ll, 19, 19, null, null, zip_bl);
 
552
    if(h.status != 0)
 
553
        return -1;      // incomplete code set
 
554
 
 
555
    zip_tl = h.root;
 
556
    zip_bl = h.m;
 
557
 
 
558
    // read in literal and distance code lengths
 
559
    n = nl + nd;
 
560
    i = l = 0;
 
561
    while(i < n) {
 
562
        zip_NEEDBITS(zip_bl);
 
563
        t = zip_tl.list[zip_GETBITS(zip_bl)];
 
564
        j = t.b;
 
565
        zip_DUMPBITS(j);
 
566
        j = t.n;
 
567
        if(j < 16)              // length of code in bits (0..15)
 
568
            ll[i++] = l = j;    // save last length in l
 
569
        else if(j == 16) {      // repeat last length 3 to 6 times
 
570
            zip_NEEDBITS(2);
 
571
            j = 3 + zip_GETBITS(2);
 
572
            zip_DUMPBITS(2);
 
573
            if(i + j > n)
 
574
                return -1;
 
575
            while(j-- > 0)
 
576
                ll[i++] = l;
 
577
        } else if(j == 17) {    // 3 to 10 zero length codes
 
578
            zip_NEEDBITS(3);
 
579
            j = 3 + zip_GETBITS(3);
 
580
            zip_DUMPBITS(3);
 
581
            if(i + j > n)
 
582
                return -1;
 
583
            while(j-- > 0)
 
584
                ll[i++] = 0;
 
585
            l = 0;
 
586
        } else {                // j == 18: 11 to 138 zero length codes
 
587
            zip_NEEDBITS(7);
 
588
            j = 11 + zip_GETBITS(7);
 
589
            zip_DUMPBITS(7);
 
590
            if(i + j > n)
 
591
                return -1;
 
592
            while(j-- > 0)
 
593
                ll[i++] = 0;
 
594
            l = 0;
 
595
        }
 
596
    }
 
597
 
 
598
    // build the decoding tables for literal/length and distance codes
 
599
    zip_bl = zip_lbits;
 
600
    h = new zip_HuftBuild(ll, nl, 257, zip_cplens, zip_cplext, zip_bl);
 
601
    if(zip_bl == 0)     // no literals or lengths
 
602
        h.status = 1;
 
603
    if(h.status != 0) {
 
604
        if(h.status == 1)
 
605
            ;// **incomplete literal tree**
 
606
        return -1;              // incomplete code set
 
607
    }
 
608
    zip_tl = h.root;
 
609
    zip_bl = h.m;
 
610
 
 
611
    for(i = 0; i < nd; i++)
 
612
        ll[i] = ll[i + nl];
 
613
    zip_bd = zip_dbits;
 
614
    h = new zip_HuftBuild(ll, nd, 0, zip_cpdist, zip_cpdext, zip_bd);
 
615
    zip_td = h.root;
 
616
    zip_bd = h.m;
 
617
 
 
618
    if(zip_bd == 0 && nl > 257) {   // lengths but no distances
 
619
        // **incomplete distance tree**
 
620
        return -1;
 
621
    }
 
622
 
 
623
    if(h.status == 1) {
 
624
        ;// **incomplete distance tree**
 
625
    }
 
626
    if(h.status != 0)
 
627
        return -1;
 
628
 
 
629
    // decompress until an end-of-block code
 
630
    return zip_inflate_codes(buff, off, size);
 
631
}
 
632
 
 
633
var zip_inflate_start = function() {
 
634
    var i;
 
635
 
 
636
    if(zip_slide == null)
 
637
        zip_slide = new Array(2 * zip_WSIZE);
 
638
    zip_wp = 0;
 
639
    zip_bit_buf = 0;
 
640
    zip_bit_len = 0;
 
641
    zip_method = -1;
 
642
    zip_eof = false;
 
643
    zip_copy_leng = zip_copy_dist = 0;
 
644
    zip_tl = null;
 
645
}
 
646
 
 
647
var zip_inflate_internal = function(buff, off, size) {
 
648
    // decompress an inflated entry
 
649
    var n, i;
 
650
 
 
651
    n = 0;
 
652
    while(n < size) {
 
653
        if(zip_eof && zip_method == -1)
 
654
            return n;
 
655
 
 
656
        if(zip_copy_leng > 0) {
 
657
            if(zip_method != zip_STORED_BLOCK) {
 
658
                // STATIC_TREES or DYN_TREES
 
659
                while(zip_copy_leng > 0 && n < size) {
 
660
                    zip_copy_leng--;
 
661
                    zip_copy_dist &= zip_WSIZE - 1;
 
662
                    zip_wp &= zip_WSIZE - 1;
 
663
                    buff[off + n++] = zip_slide[zip_wp++] =
 
664
                        zip_slide[zip_copy_dist++];
 
665
                }
 
666
            } else {
 
667
                while(zip_copy_leng > 0 && n < size) {
 
668
                    zip_copy_leng--;
 
669
                    zip_wp &= zip_WSIZE - 1;
 
670
                    zip_NEEDBITS(8);
 
671
                    buff[off + n++] = zip_slide[zip_wp++] = zip_GETBITS(8);
 
672
                    zip_DUMPBITS(8);
 
673
                }
 
674
                if(zip_copy_leng == 0)
 
675
                    zip_method = -1; // done
 
676
            }
 
677
            if(n == size)
 
678
                return n;
 
679
        }
 
680
 
 
681
        if(zip_method == -1) {
 
682
            if(zip_eof)
 
683
                break;
 
684
 
 
685
            // read in last block bit
 
686
            zip_NEEDBITS(1);
 
687
            if(zip_GETBITS(1) != 0)
 
688
                zip_eof = true;
 
689
            zip_DUMPBITS(1);
 
690
 
 
691
            // read in block type
 
692
            zip_NEEDBITS(2);
 
693
            zip_method = zip_GETBITS(2);
 
694
            zip_DUMPBITS(2);
 
695
            zip_tl = null;
 
696
            zip_copy_leng = 0;
 
697
        }
 
698
 
 
699
        switch(zip_method) {
 
700
          case 0: // zip_STORED_BLOCK
 
701
            i = zip_inflate_stored(buff, off + n, size - n);
 
702
            break;
 
703
 
 
704
          case 1: // zip_STATIC_TREES
 
705
            if(zip_tl != null)
 
706
                i = zip_inflate_codes(buff, off + n, size - n);
 
707
            else
 
708
                i = zip_inflate_fixed(buff, off + n, size - n);
 
709
            break;
 
710
 
 
711
          case 2: // zip_DYN_TREES
 
712
            if(zip_tl != null)
 
713
                i = zip_inflate_codes(buff, off + n, size - n);
 
714
            else
 
715
                i = zip_inflate_dynamic(buff, off + n, size - n);
 
716
            break;
 
717
 
 
718
          default: // error
 
719
            i = -1;
 
720
            break;
 
721
        }
 
722
 
 
723
        if(i == -1) {
 
724
            if(zip_eof)
 
725
                return 0;
 
726
            return -1;
 
727
        }
 
728
        n += i;
 
729
    }
 
730
    return n;
 
731
}
 
732
 
 
733
var zip_inflate = function(str) {
 
734
    var i, j;
 
735
 
 
736
    zip_inflate_start();
 
737
    zip_inflate_data = str;
 
738
    zip_inflate_pos = 0;
 
739
 
 
740
    var buff = new Array(1024);
 
741
    var aout = [];
 
742
    while((i = zip_inflate_internal(buff, 0, buff.length)) > 0) {
 
743
        var cbuf = new Array(i);
 
744
        for(j = 0; j < i; j++){
 
745
            cbuf[j] = String.fromCharCode(buff[j]);
 
746
        }
 
747
        aout[aout.length] = cbuf.join("");
 
748
    }
 
749
    zip_inflate_data = null; // G.C.
 
750
    return aout.join("");
 
751
}
 
752
 
 
753
if (! ctx.RawDeflate) ctx.RawDeflate = {};
 
754
ctx.RawDeflate.inflate = zip_inflate;
 
755
 
 
756
})(this);