1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/mini/src/main/java/org/apidesign/bck2brwsr/emul/zip/InfBlocks.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,616 @@
1.4 +/* -*-mode:java; c-basic-offset:2; -*- */
1.5 +/*
1.6 +Copyright (c) 2011 ymnk, JCraft,Inc. All rights reserved.
1.7 +
1.8 +Redistribution and use in source and binary forms, with or without
1.9 +modification, are permitted provided that the following conditions are met:
1.10 +
1.11 + 1. Redistributions of source code must retain the above copyright notice,
1.12 + this list of conditions and the following disclaimer.
1.13 +
1.14 + 2. Redistributions in binary form must reproduce the above copyright
1.15 + notice, this list of conditions and the following disclaimer in
1.16 + the documentation and/or other materials provided with the distribution.
1.17 +
1.18 + 3. The names of the authors may not be used to endorse or promote products
1.19 + derived from this software without specific prior written permission.
1.20 +
1.21 +THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
1.22 +INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
1.23 +FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
1.24 +INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
1.25 +INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.26 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
1.27 +OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
1.28 +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1.29 +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
1.30 +EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.31 + */
1.32 +/*
1.33 + * This program is based on zlib-1.1.3, so all credit should go authors
1.34 + * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
1.35 + * and contributors of zlib.
1.36 + */
1.37 +
1.38 +package org.apidesign.bck2brwsr.emul.zip;
1.39 +
1.40 +import org.apidesign.bck2brwsr.emul.lang.System;
1.41 +
1.42 +final class InfBlocks{
1.43 + static final private int MANY=1440;
1.44 +
1.45 + // And'ing with mask[n] masks the lower n bits
1.46 + static final private int[] inflate_mask = {
1.47 + 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
1.48 + 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
1.49 + 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
1.50 + 0x00007fff, 0x0000ffff
1.51 + };
1.52 +
1.53 + // Table for deflate from PKZIP's appnote.txt.
1.54 + static final int[] border = { // Order of the bit length code lengths
1.55 + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
1.56 + };
1.57 +
1.58 + static final private int Z_OK=0;
1.59 + static final private int Z_STREAM_END=1;
1.60 + static final private int Z_NEED_DICT=2;
1.61 + static final private int Z_ERRNO=-1;
1.62 + static final private int Z_STREAM_ERROR=-2;
1.63 + static final private int Z_DATA_ERROR=-3;
1.64 + static final private int Z_MEM_ERROR=-4;
1.65 + static final private int Z_BUF_ERROR=-5;
1.66 + static final private int Z_VERSION_ERROR=-6;
1.67 +
1.68 + static final private int TYPE=0; // get type bits (3, including end bit)
1.69 + static final private int LENS=1; // get lengths for stored
1.70 + static final private int STORED=2;// processing stored block
1.71 + static final private int TABLE=3; // get table lengths
1.72 + static final private int BTREE=4; // get bit lengths tree for a dynamic block
1.73 + static final private int DTREE=5; // get length, distance trees for a dynamic block
1.74 + static final private int CODES=6; // processing fixed or dynamic block
1.75 + static final private int DRY=7; // output remaining window bytes
1.76 + static final private int DONE=8; // finished last block, done
1.77 + static final private int BAD=9; // ot a data error--stuck here
1.78 +
1.79 + int mode; // current inflate_block mode
1.80 +
1.81 + int left; // if STORED, bytes left to copy
1.82 +
1.83 + int table; // table lengths (14 bits)
1.84 + int index; // index into blens (or border)
1.85 + int[] blens; // bit lengths of codes
1.86 + int[] bb=new int[1]; // bit length tree depth
1.87 + int[] tb=new int[1]; // bit length decoding tree
1.88 +
1.89 + int[] bl=new int[1];
1.90 + int[] bd=new int[1];
1.91 +
1.92 + int[][] tl=new int[1][];
1.93 + int[][] td=new int[1][];
1.94 + int[] tli=new int[1]; // tl_index
1.95 + int[] tdi=new int[1]; // td_index
1.96 +
1.97 + private final InfCodes codes; // if CODES, current state
1.98 +
1.99 + int last; // true if this block is the last block
1.100 +
1.101 + // mode independent information
1.102 + int bitk; // bits in bit buffer
1.103 + int bitb; // bit buffer
1.104 + int[] hufts; // single malloc for tree space
1.105 + byte[] window; // sliding window
1.106 + int end; // one byte after sliding window
1.107 + int read; // window read pointer
1.108 + int write; // window write pointer
1.109 + private boolean check;
1.110 +
1.111 + private final InfTree inftree=new InfTree();
1.112 +
1.113 + private final ZStream z;
1.114 +
1.115 + InfBlocks(ZStream z, int w){
1.116 + this.z=z;
1.117 + this.codes=new InfCodes(this.z, this);
1.118 + hufts=new int[MANY*3];
1.119 + window=new byte[w];
1.120 + end=w;
1.121 + this.check = (z.istate.wrap==0) ? false : true;
1.122 + mode = TYPE;
1.123 + reset();
1.124 + }
1.125 +
1.126 + void reset(){
1.127 + if(mode==BTREE || mode==DTREE){
1.128 + }
1.129 + if(mode==CODES){
1.130 + codes.free(z);
1.131 + }
1.132 + mode=TYPE;
1.133 + bitk=0;
1.134 + bitb=0;
1.135 + read=write=0;
1.136 + if(check){
1.137 + z.adler.reset();
1.138 + }
1.139 + }
1.140 +
1.141 + int proc(int r){
1.142 + int t; // temporary storage
1.143 + int b; // bit buffer
1.144 + int k; // bits in bit buffer
1.145 + int p; // input data pointer
1.146 + int n; // bytes available there
1.147 + int q; // output window write pointer
1.148 + int m; // bytes to end of window or read pointer
1.149 +
1.150 + // copy input/output information to locals (UPDATE macro restores)
1.151 + {p=z.next_in_index;n=z.avail_in;b=bitb;k=bitk;}
1.152 + {q=write;m=(int)(q<read?read-q-1:end-q);}
1.153 +
1.154 + // process input based on current state
1.155 + while(true){
1.156 + switch (mode){
1.157 + case TYPE:
1.158 +
1.159 + while(k<(3)){
1.160 + if(n!=0){
1.161 + r=Z_OK;
1.162 + }
1.163 + else{
1.164 + bitb=b; bitk=k;
1.165 + z.avail_in=n;
1.166 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.167 + write=q;
1.168 + return inflate_flush(r);
1.169 + };
1.170 + n--;
1.171 + b|=(z.next_in[p++]&0xff)<<k;
1.172 + k+=8;
1.173 + }
1.174 + t = (int)(b & 7);
1.175 + last = t & 1;
1.176 +
1.177 + switch (t >>> 1){
1.178 + case 0: // stored
1.179 + {b>>>=(3);k-=(3);}
1.180 + t = k & 7; // go to byte boundary
1.181 +
1.182 + {b>>>=(t);k-=(t);}
1.183 + mode = LENS; // get length of stored block
1.184 + break;
1.185 + case 1: // fixed
1.186 + InfTree.inflate_trees_fixed(bl, bd, tl, td, z);
1.187 + codes.init(bl[0], bd[0], tl[0], 0, td[0], 0);
1.188 +
1.189 + {b>>>=(3);k-=(3);}
1.190 +
1.191 + mode = CODES;
1.192 + break;
1.193 + case 2: // dynamic
1.194 +
1.195 + {b>>>=(3);k-=(3);}
1.196 +
1.197 + mode = TABLE;
1.198 + break;
1.199 + case 3: // illegal
1.200 +
1.201 + {b>>>=(3);k-=(3);}
1.202 + mode = BAD;
1.203 + z.msg = "invalid block type";
1.204 + r = Z_DATA_ERROR;
1.205 +
1.206 + bitb=b; bitk=k;
1.207 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.208 + write=q;
1.209 + return inflate_flush(r);
1.210 + }
1.211 + break;
1.212 + case LENS:
1.213 +
1.214 + while(k<(32)){
1.215 + if(n!=0){
1.216 + r=Z_OK;
1.217 + }
1.218 + else{
1.219 + bitb=b; bitk=k;
1.220 + z.avail_in=n;
1.221 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.222 + write=q;
1.223 + return inflate_flush(r);
1.224 + };
1.225 + n--;
1.226 + b|=(z.next_in[p++]&0xff)<<k;
1.227 + k+=8;
1.228 + }
1.229 +
1.230 + if ((((~b) >>> 16) & 0xffff) != (b & 0xffff)){
1.231 + mode = BAD;
1.232 + z.msg = "invalid stored block lengths";
1.233 + r = Z_DATA_ERROR;
1.234 +
1.235 + bitb=b; bitk=k;
1.236 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.237 + write=q;
1.238 + return inflate_flush(r);
1.239 + }
1.240 + left = (b & 0xffff);
1.241 + b = k = 0; // dump bits
1.242 + mode = left!=0 ? STORED : (last!=0 ? DRY : TYPE);
1.243 + break;
1.244 + case STORED:
1.245 + if (n == 0){
1.246 + bitb=b; bitk=k;
1.247 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.248 + write=q;
1.249 + return inflate_flush(r);
1.250 + }
1.251 +
1.252 + if(m==0){
1.253 + if(q==end&&read!=0){
1.254 + q=0; m=(int)(q<read?read-q-1:end-q);
1.255 + }
1.256 + if(m==0){
1.257 + write=q;
1.258 + r=inflate_flush(r);
1.259 + q=write;m=(int)(q<read?read-q-1:end-q);
1.260 + if(q==end&&read!=0){
1.261 + q=0; m=(int)(q<read?read-q-1:end-q);
1.262 + }
1.263 + if(m==0){
1.264 + bitb=b; bitk=k;
1.265 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.266 + write=q;
1.267 + return inflate_flush(r);
1.268 + }
1.269 + }
1.270 + }
1.271 + r=Z_OK;
1.272 +
1.273 + t = left;
1.274 + if(t>n) t = n;
1.275 + if(t>m) t = m;
1.276 + System.arraycopy(z.next_in, p, window, q, t);
1.277 + p += t; n -= t;
1.278 + q += t; m -= t;
1.279 + if ((left -= t) != 0)
1.280 + break;
1.281 + mode = last!=0 ? DRY : TYPE;
1.282 + break;
1.283 + case TABLE:
1.284 +
1.285 + while(k<(14)){
1.286 + if(n!=0){
1.287 + r=Z_OK;
1.288 + }
1.289 + else{
1.290 + bitb=b; bitk=k;
1.291 + z.avail_in=n;
1.292 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.293 + write=q;
1.294 + return inflate_flush(r);
1.295 + };
1.296 + n--;
1.297 + b|=(z.next_in[p++]&0xff)<<k;
1.298 + k+=8;
1.299 + }
1.300 +
1.301 + table = t = (b & 0x3fff);
1.302 + if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
1.303 + {
1.304 + mode = BAD;
1.305 + z.msg = "too many length or distance symbols";
1.306 + r = Z_DATA_ERROR;
1.307 +
1.308 + bitb=b; bitk=k;
1.309 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.310 + write=q;
1.311 + return inflate_flush(r);
1.312 + }
1.313 + t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
1.314 + if(blens==null || blens.length<t){
1.315 + blens=new int[t];
1.316 + }
1.317 + else{
1.318 + for(int i=0; i<t; i++){blens[i]=0;}
1.319 + }
1.320 +
1.321 + {b>>>=(14);k-=(14);}
1.322 +
1.323 + index = 0;
1.324 + mode = BTREE;
1.325 + case BTREE:
1.326 + while (index < 4 + (table >>> 10)){
1.327 + while(k<(3)){
1.328 + if(n!=0){
1.329 + r=Z_OK;
1.330 + }
1.331 + else{
1.332 + bitb=b; bitk=k;
1.333 + z.avail_in=n;
1.334 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.335 + write=q;
1.336 + return inflate_flush(r);
1.337 + };
1.338 + n--;
1.339 + b|=(z.next_in[p++]&0xff)<<k;
1.340 + k+=8;
1.341 + }
1.342 +
1.343 + blens[border[index++]] = b&7;
1.344 +
1.345 + {b>>>=(3);k-=(3);}
1.346 + }
1.347 +
1.348 + while(index < 19){
1.349 + blens[border[index++]] = 0;
1.350 + }
1.351 +
1.352 + bb[0] = 7;
1.353 + t = inftree.inflate_trees_bits(blens, bb, tb, hufts, z);
1.354 + if (t != Z_OK){
1.355 + r = t;
1.356 + if (r == Z_DATA_ERROR){
1.357 + blens=null;
1.358 + mode = BAD;
1.359 + }
1.360 +
1.361 + bitb=b; bitk=k;
1.362 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.363 + write=q;
1.364 + return inflate_flush(r);
1.365 + }
1.366 +
1.367 + index = 0;
1.368 + mode = DTREE;
1.369 + case DTREE:
1.370 + while (true){
1.371 + t = table;
1.372 + if(!(index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))){
1.373 + break;
1.374 + }
1.375 +
1.376 + int[] h;
1.377 + int i, j, c;
1.378 +
1.379 + t = bb[0];
1.380 +
1.381 + while(k<(t)){
1.382 + if(n!=0){
1.383 + r=Z_OK;
1.384 + }
1.385 + else{
1.386 + bitb=b; bitk=k;
1.387 + z.avail_in=n;
1.388 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.389 + write=q;
1.390 + return inflate_flush(r);
1.391 + };
1.392 + n--;
1.393 + b|=(z.next_in[p++]&0xff)<<k;
1.394 + k+=8;
1.395 + }
1.396 +
1.397 + if(tb[0]==-1){
1.398 + //System.err.println("null...");
1.399 + }
1.400 +
1.401 + t=hufts[(tb[0]+(b&inflate_mask[t]))*3+1];
1.402 + c=hufts[(tb[0]+(b&inflate_mask[t]))*3+2];
1.403 +
1.404 + if (c < 16){
1.405 + b>>>=(t);k-=(t);
1.406 + blens[index++] = c;
1.407 + }
1.408 + else { // c == 16..18
1.409 + i = c == 18 ? 7 : c - 14;
1.410 + j = c == 18 ? 11 : 3;
1.411 +
1.412 + while(k<(t+i)){
1.413 + if(n!=0){
1.414 + r=Z_OK;
1.415 + }
1.416 + else{
1.417 + bitb=b; bitk=k;
1.418 + z.avail_in=n;
1.419 + z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.420 + write=q;
1.421 + return inflate_flush(r);
1.422 + };
1.423 + n--;
1.424 + b|=(z.next_in[p++]&0xff)<<k;
1.425 + k+=8;
1.426 + }
1.427 +
1.428 + b>>>=(t);k-=(t);
1.429 +
1.430 + j += (b & inflate_mask[i]);
1.431 +
1.432 + b>>>=(i);k-=(i);
1.433 +
1.434 + i = index;
1.435 + t = table;
1.436 + if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
1.437 + (c == 16 && i < 1)){
1.438 + blens=null;
1.439 + mode = BAD;
1.440 + z.msg = "invalid bit length repeat";
1.441 + r = Z_DATA_ERROR;
1.442 +
1.443 + bitb=b; bitk=k;
1.444 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.445 + write=q;
1.446 + return inflate_flush(r);
1.447 + }
1.448 +
1.449 + c = c == 16 ? blens[i-1] : 0;
1.450 + do{
1.451 + blens[i++] = c;
1.452 + }
1.453 + while (--j!=0);
1.454 + index = i;
1.455 + }
1.456 + }
1.457 +
1.458 + tb[0]=-1;
1.459 + {
1.460 + bl[0] = 9; // must be <= 9 for lookahead assumptions
1.461 + bd[0] = 6; // must be <= 9 for lookahead assumptions
1.462 + t = table;
1.463 + t = inftree.inflate_trees_dynamic(257 + (t & 0x1f),
1.464 + 1 + ((t >> 5) & 0x1f),
1.465 + blens, bl, bd, tli, tdi, hufts, z);
1.466 +
1.467 + if (t != Z_OK){
1.468 + if (t == Z_DATA_ERROR){
1.469 + blens=null;
1.470 + mode = BAD;
1.471 + }
1.472 + r = t;
1.473 +
1.474 + bitb=b; bitk=k;
1.475 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.476 + write=q;
1.477 + return inflate_flush(r);
1.478 + }
1.479 + codes.init(bl[0], bd[0], hufts, tli[0], hufts, tdi[0]);
1.480 + }
1.481 + mode = CODES;
1.482 + case CODES:
1.483 + bitb=b; bitk=k;
1.484 + z.avail_in=n; z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.485 + write=q;
1.486 +
1.487 + if ((r = codes.proc(r)) != Z_STREAM_END){
1.488 + return inflate_flush(r);
1.489 + }
1.490 + r = Z_OK;
1.491 + codes.free(z);
1.492 +
1.493 + p=z.next_in_index; n=z.avail_in;b=bitb;k=bitk;
1.494 + q=write;m=(int)(q<read?read-q-1:end-q);
1.495 +
1.496 + if (last==0){
1.497 + mode = TYPE;
1.498 + break;
1.499 + }
1.500 + mode = DRY;
1.501 + case DRY:
1.502 + write=q;
1.503 + r=inflate_flush(r);
1.504 + q=write; m=(int)(q<read?read-q-1:end-q);
1.505 + if (read != write){
1.506 + bitb=b; bitk=k;
1.507 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.508 + write=q;
1.509 + return inflate_flush(r);
1.510 + }
1.511 + mode = DONE;
1.512 + case DONE:
1.513 + r = Z_STREAM_END;
1.514 +
1.515 + bitb=b; bitk=k;
1.516 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.517 + write=q;
1.518 + return inflate_flush(r);
1.519 + case BAD:
1.520 + r = Z_DATA_ERROR;
1.521 +
1.522 + bitb=b; bitk=k;
1.523 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.524 + write=q;
1.525 + return inflate_flush(r);
1.526 +
1.527 + default:
1.528 + r = Z_STREAM_ERROR;
1.529 +
1.530 + bitb=b; bitk=k;
1.531 + z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
1.532 + write=q;
1.533 + return inflate_flush(r);
1.534 + }
1.535 + }
1.536 + }
1.537 +
1.538 + void free(){
1.539 + reset();
1.540 + window=null;
1.541 + hufts=null;
1.542 + //ZFREE(z, s);
1.543 + }
1.544 +
1.545 + void set_dictionary(byte[] d, int start, int n){
1.546 + System.arraycopy(d, start, window, 0, n);
1.547 + read = write = n;
1.548 + }
1.549 +
1.550 + // Returns true if inflate is currently at the end of a block generated
1.551 + // by Z_SYNC_FLUSH or Z_FULL_FLUSH.
1.552 + int sync_point(){
1.553 + return mode == LENS ? 1 : 0;
1.554 + }
1.555 +
1.556 + // copy as much as possible from the sliding window to the output area
1.557 + int inflate_flush(int r){
1.558 + int n;
1.559 + int p;
1.560 + int q;
1.561 +
1.562 + // local copies of source and destination pointers
1.563 + p = z.next_out_index;
1.564 + q = read;
1.565 +
1.566 + // compute number of bytes to copy as far as end of window
1.567 + n = (int)((q <= write ? write : end) - q);
1.568 + if(n > z.avail_out) n = z.avail_out;
1.569 + if(n!=0 && r == Z_BUF_ERROR) r = Z_OK;
1.570 +
1.571 + // update counters
1.572 + z.avail_out -= n;
1.573 + z.total_out += n;
1.574 +
1.575 + // update check information
1.576 + if(check && n>0){
1.577 + z.adler.update(window, q, n);
1.578 + }
1.579 +
1.580 + // copy as far as end of window
1.581 + System.arraycopy(window, q, z.next_out, p, n);
1.582 + p += n;
1.583 + q += n;
1.584 +
1.585 + // see if more to copy at beginning of window
1.586 + if (q == end){
1.587 + // wrap pointers
1.588 + q = 0;
1.589 + if (write == end)
1.590 + write = 0;
1.591 +
1.592 + // compute bytes to copy
1.593 + n = write - q;
1.594 + if (n > z.avail_out) n = z.avail_out;
1.595 + if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
1.596 +
1.597 + // update counters
1.598 + z.avail_out -= n;
1.599 + z.total_out += n;
1.600 +
1.601 + // update check information
1.602 + if(check && n>0){
1.603 + z.adler.update(window, q, n);
1.604 + }
1.605 +
1.606 + // copy
1.607 + System.arraycopy(window, q, z.next_out, p, n);
1.608 + p += n;
1.609 + q += n;
1.610 + }
1.611 +
1.612 + // update pointers
1.613 + z.next_out_index = p;
1.614 + read = q;
1.615 +
1.616 + // done
1.617 + return r;
1.618 + }
1.619 +}