Mercurial > 510Connectbot

comparison app/src/main/java/com/jcraft/jzlib/InfBlocks.java @ 438:d29cce60f393

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
migrate from Eclipse to Android Studio
author Carl Byington <carl@five-ten-sg.com>
date Thu, 03 Dec 2015 11:23:55 -0800
parents src/com/jcraft/jzlib/InfBlocks.java@46c2115ae1c8
children
comparison
equal deleted inserted replaced
437:208b31032318 438:d29cce60f393
1 /* -*-mode:java; c-basic-offset:2; -*- */
2 /*
3 Copyright (c) 2011 ymnk, JCraft,Inc. All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7
8 1. Redistributions of source code must retain the above copyright notice,
9 this list of conditions and the following disclaimer.
10
11 2. Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions and the following disclaimer in
13 the documentation and/or other materials provided with the distribution.
14
15 3. The names of the authors may not be used to endorse or promote products
16 derived from this software without specific prior written permission.
17
18 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
21 INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
25 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
27 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29 /*
30 * This program is based on zlib-1.1.3, so all credit should go authors
31 * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
32 * and contributors of zlib.
33 */
34
35 package com.jcraft.jzlib;
36
37 final class InfBlocks{
38 static final private int MANY=1440;
39
40 // And'ing with mask[n] masks the lower n bits
41 static final private int[] inflate_mask = {
42 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
43 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
44 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
45 0x00007fff, 0x0000ffff
46 };
47
48 // Table for deflate from PKZIP's appnote.txt.
49 static final int[] border = { // Order of the bit length code lengths
50 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
51 };
52
53 static final private int Z_OK=0;
54 static final private int Z_STREAM_END=1;
55 static final private int Z_NEED_DICT=2;
56 static final private int Z_ERRNO=-1;
57 static final private int Z_STREAM_ERROR=-2;
58 static final private int Z_DATA_ERROR=-3;
59 static final private int Z_MEM_ERROR=-4;
60 static final private int Z_BUF_ERROR=-5;
61 static final private int Z_VERSION_ERROR=-6;
62
63 static final private int TYPE=0; // get type bits (3, including end bit)
64 static final private int LENS=1; // get lengths for stored
65 static final private int STORED=2;// processing stored block
66 static final private int TABLE=3; // get table lengths
67 static final private int BTREE=4; // get bit lengths tree for a dynamic block
68 static final private int DTREE=5; // get length, distance trees for a dynamic block
69 static final private int CODES=6; // processing fixed or dynamic block
70 static final private int DRY=7; // output remaining window bytes
71 static final private int DONE=8; // finished last block, done
72 static final private int BAD=9; // ot a data error--stuck here
73
74 int mode; // current inflate_block mode
75
76 int left; // if STORED, bytes left to copy
77
78 int table; // table lengths (14 bits)
79 int index; // index into blens (or border)
80 int[] blens; // bit lengths of codes
81 int[] bb=new int[1]; // bit length tree depth
82 int[] tb=new int[1]; // bit length decoding tree
83
84 int[] bl=new int[1];
85 int[] bd=new int[1];
86
87 int[][] tl=new int[1][];
88 int[][] td=new int[1][];
89 int[] tli=new int[1]; // tl_index
90 int[] tdi=new int[1]; // td_index
91
92 private final InfCodes codes; // if CODES, current state
93
94 int last; // true if this block is the last block
95
96 // mode independent information
97 int bitk; // bits in bit buffer
98 int bitb; // bit buffer
99 int[] hufts; // single malloc for tree space
100 byte[] window; // sliding window
101 int end; // one byte after sliding window
102 int read; // window read pointer
103 int write; // window write pointer
104 private boolean check;
105
106 private final InfTree inftree=new InfTree();
107
108 private final ZStream z;
109
110 InfBlocks(ZStream z, int w){
111 this.z=z;
112 this.codes=new InfCodes(this.z, this);
113 hufts=new int[MANY*3];
114 window=new byte[w];
115 end=w;
116 this.check = (z.istate.wrap==0) ? false : true;
117 mode = TYPE;
118 reset();
119 }
120
121 void reset(){
122 if(mode==BTREE || mode==DTREE){
123 }
124 if(mode==CODES){
125 codes.free(z);
126 }
127 mode=TYPE;
128 bitk=0;
129 bitb=0;
130 read=write=0;
131 if(check){
132 z.adler.reset();
133 }
134 }
135
136 int proc(int r){
137 int t; // temporary storage
138 int b; // bit buffer
139 int k; // bits in bit buffer
140 int p; // input data pointer
141 int n; // bytes available there
142 int q; // output window write pointer
143 int m; // bytes to end of window or read pointer
144
145 // copy input/output information to locals (UPDATE macro restores)
146 {p=z.next_in_index;n=z.avail_in;b=bitb;k=bitk;}
147 {q=write;m=(int)(q<read?read-q-1:end-q);}
148
149 // process input based on current state
150 while(true){
151 switch (mode){
152 case TYPE:
153
154 while(k<(3)){
155 if(n!=0){
156 r=Z_OK;
157 }
158 else{
159 bitb=b; bitk=k;
160 z.avail_in=n;
161 z.total_in+=p-z.next_in_index;z.next_in_index=p;
162 write=q;
163 return inflate_flush(r);
164 };
165 n--;
166 b|=(z.next_in[p++]&0xff)<<k;
167 k+=8;
168 }
169 t = (int)(b & 7);
170 last = t & 1;
171
172 switch (t >>> 1){
173 case 0: // stored
174 {b>>>=(3);k-=(3);}
175 t = k & 7; // go to byte boundary
176
177 {b>>>=(t);k-=(t);}
178 mode = LENS; // get length of stored block
179 break;
180 case 1: // fixed
181 InfTree.inflate_trees_fixed(bl, bd, tl, td, z);
182 codes.init(bl[0], bd[0], tl[0], 0, td[0], 0);
183
184 {b>>>=(3);k-=(3);}
185
186 mode = CODES;
187 break;
188 case 2: // dynamic
189
190 {b>>>=(3);k-=(3);}
191
192 mode = TABLE;
193 break;
194 case 3: // illegal
195
196 {b>>>=(3);k-=(3);}
197 mode = BAD;
198 z.msg = "invalid block type";
199 r = Z_DATA_ERROR;
200
201 bitb=b; bitk=k;
202 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
203 write=q;
204 return inflate_flush(r);
205 }
206 break;
207 case LENS:
208
209 while(k<(32)){
210 if(n!=0){
211 r=Z_OK;
212 }
213 else{
214 bitb=b; bitk=k;
215 z.avail_in=n;
216 z.total_in+=p-z.next_in_index;z.next_in_index=p;
217 write=q;
218 return inflate_flush(r);
219 };
220 n--;
221 b|=(z.next_in[p++]&0xff)<<k;
222 k+=8;
223 }
224
225 if ((((~b) >>> 16) & 0xffff) != (b & 0xffff)){
226 mode = BAD;
227 z.msg = "invalid stored block lengths";
228 r = Z_DATA_ERROR;
229
230 bitb=b; bitk=k;
231 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
232 write=q;
233 return inflate_flush(r);
234 }
235 left = (b & 0xffff);
236 b = k = 0; // dump bits
237 mode = left!=0 ? STORED : (last!=0 ? DRY : TYPE);
238 break;
239 case STORED:
240 if (n == 0){
241 bitb=b; bitk=k;
242 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
243 write=q;
244 return inflate_flush(r);
245 }
246
247 if(m==0){
248 if(q==end&&read!=0){
249 q=0; m=(int)(q<read?read-q-1:end-q);
250 }
251 if(m==0){
252 write=q;
253 r=inflate_flush(r);
254 q=write;m=(int)(q<read?read-q-1:end-q);
255 if(q==end&&read!=0){
256 q=0; m=(int)(q<read?read-q-1:end-q);
257 }
258 if(m==0){
259 bitb=b; bitk=k;
260 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
261 write=q;
262 return inflate_flush(r);
263 }
264 }
265 }
266 r=Z_OK;
267
268 t = left;
269 if(t>n) t = n;
270 if(t>m) t = m;
271 System.arraycopy(z.next_in, p, window, q, t);
272 p += t; n -= t;
273 q += t; m -= t;
274 if ((left -= t) != 0)
275 break;
276 mode = last!=0 ? DRY : TYPE;
277 break;
278 case TABLE:
279
280 while(k<(14)){
281 if(n!=0){
282 r=Z_OK;
283 }
284 else{
285 bitb=b; bitk=k;
286 z.avail_in=n;
287 z.total_in+=p-z.next_in_index;z.next_in_index=p;
288 write=q;
289 return inflate_flush(r);
290 };
291 n--;
292 b|=(z.next_in[p++]&0xff)<<k;
293 k+=8;
294 }
295
296 table = t = (b & 0x3fff);
297 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
298 {
299 mode = BAD;
300 z.msg = "too many length or distance symbols";
301 r = Z_DATA_ERROR;
302
303 bitb=b; bitk=k;
304 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
305 write=q;
306 return inflate_flush(r);
307 }
308 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
309 if(blens==null || blens.length<t){
310 blens=new int[t];
311 }
312 else{
313 for(int i=0; i<t; i++){blens[i]=0;}
314 }
315
316 {b>>>=(14);k-=(14);}
317
318 index = 0;
319 mode = BTREE;
320 case BTREE:
321 while (index < 4 + (table >>> 10)){
322 while(k<(3)){
323 if(n!=0){
324 r=Z_OK;
325 }
326 else{
327 bitb=b; bitk=k;
328 z.avail_in=n;
329 z.total_in+=p-z.next_in_index;z.next_in_index=p;
330 write=q;
331 return inflate_flush(r);
332 };
333 n--;
334 b|=(z.next_in[p++]&0xff)<<k;
335 k+=8;
336 }
337
338 blens[border[index++]] = b&7;
339
340 {b>>>=(3);k-=(3);}
341 }
342
343 while(index < 19){
344 blens[border[index++]] = 0;
345 }
346
347 bb[0] = 7;
348 t = inftree.inflate_trees_bits(blens, bb, tb, hufts, z);
349 if (t != Z_OK){
350 r = t;
351 if (r == Z_DATA_ERROR){
352 blens=null;
353 mode = BAD;
354 }
355
356 bitb=b; bitk=k;
357 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
358 write=q;
359 return inflate_flush(r);
360 }
361
362 index = 0;
363 mode = DTREE;
364 case DTREE:
365 while (true){
366 t = table;
367 if(!(index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))){
368 break;
369 }
370
371 int[] h;
372 int i, j, c;
373
374 t = bb[0];
375
376 while(k<(t)){
377 if(n!=0){
378 r=Z_OK;
379 }
380 else{
381 bitb=b; bitk=k;
382 z.avail_in=n;
383 z.total_in+=p-z.next_in_index;z.next_in_index=p;
384 write=q;
385 return inflate_flush(r);
386 };
387 n--;
388 b|=(z.next_in[p++]&0xff)<<k;
389 k+=8;
390 }
391
392 if(tb[0]==-1){
393 //System.err.println("null...");
394 }
395
396 t=hufts[(tb[0]+(b&inflate_mask[t]))*3+1];
397 c=hufts[(tb[0]+(b&inflate_mask[t]))*3+2];
398
399 if (c < 16){
400 b>>>=(t);k-=(t);
401 blens[index++] = c;
402 }
403 else { // c == 16..18
404 i = c == 18 ? 7 : c - 14;
405 j = c == 18 ? 11 : 3;
406
407 while(k<(t+i)){
408 if(n!=0){
409 r=Z_OK;
410 }
411 else{
412 bitb=b; bitk=k;
413 z.avail_in=n;
414 z.total_in+=p-z.next_in_index;z.next_in_index=p;
415 write=q;
416 return inflate_flush(r);
417 };
418 n--;
419 b|=(z.next_in[p++]&0xff)<<k;
420 k+=8;
421 }
422
423 b>>>=(t);k-=(t);
424
425 j += (b & inflate_mask[i]);
426
427 b>>>=(i);k-=(i);
428
429 i = index;
430 t = table;
431 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
432 (c == 16 && i < 1)){
433 blens=null;
434 mode = BAD;
435 z.msg = "invalid bit length repeat";
436 r = Z_DATA_ERROR;
437
438 bitb=b; bitk=k;
439 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
440 write=q;
441 return inflate_flush(r);
442 }
443
444 c = c == 16 ? blens[i-1] : 0;
445 do{
446 blens[i++] = c;
447 }
448 while (--j!=0);
449 index = i;
450 }
451 }
452
453 tb[0]=-1;
454 {
455 bl[0] = 9; // must be <= 9 for lookahead assumptions
456 bd[0] = 6; // must be <= 9 for lookahead assumptions
457 t = table;
458 t = inftree.inflate_trees_dynamic(257 + (t & 0x1f),
459 1 + ((t >> 5) & 0x1f),
460 blens, bl, bd, tli, tdi, hufts, z);
461
462 if (t != Z_OK){
463 if (t == Z_DATA_ERROR){
464 blens=null;
465 mode = BAD;
466 }
467 r = t;
468
469 bitb=b; bitk=k;
470 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
471 write=q;
472 return inflate_flush(r);
473 }
474 codes.init(bl[0], bd[0], hufts, tli[0], hufts, tdi[0]);
475 }
476 mode = CODES;
477 case CODES:
478 bitb=b; bitk=k;
479 z.avail_in=n; z.total_in+=p-z.next_in_index;z.next_in_index=p;
480 write=q;
481
482 if ((r = codes.proc(r)) != Z_STREAM_END){
483 return inflate_flush(r);
484 }
485 r = Z_OK;
486 codes.free(z);
487
488 p=z.next_in_index; n=z.avail_in;b=bitb;k=bitk;
489 q=write;m=(int)(q<read?read-q-1:end-q);
490
491 if (last==0){
492 mode = TYPE;
493 break;
494 }
495 mode = DRY;
496 case DRY:
497 write=q;
498 r=inflate_flush(r);
499 q=write; m=(int)(q<read?read-q-1:end-q);
500 if (read != write){
501 bitb=b; bitk=k;
502 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
503 write=q;
504 return inflate_flush(r);
505 }
506 mode = DONE;
507 case DONE:
508 r = Z_STREAM_END;
509
510 bitb=b; bitk=k;
511 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
512 write=q;
513 return inflate_flush(r);
514 case BAD:
515 r = Z_DATA_ERROR;
516
517 bitb=b; bitk=k;
518 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
519 write=q;
520 return inflate_flush(r);
521
522 default:
523 r = Z_STREAM_ERROR;
524
525 bitb=b; bitk=k;
526 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
527 write=q;
528 return inflate_flush(r);
529 }
530 }
531 }
532
533 void free(){
534 reset();
535 window=null;
536 hufts=null;
537 //ZFREE(z, s);
538 }
539
540 void set_dictionary(byte[] d, int start, int n){
541 System.arraycopy(d, start, window, 0, n);
542 read = write = n;
543 }
544
545 // Returns true if inflate is currently at the end of a block generated
546 // by Z_SYNC_FLUSH or Z_FULL_FLUSH.
547 int sync_point(){
548 return mode == LENS ? 1 : 0;
549 }
550
551 // copy as much as possible from the sliding window to the output area
552 int inflate_flush(int r){
553 int n;
554 int p;
555 int q;
556
557 // local copies of source and destination pointers
558 p = z.next_out_index;
559 q = read;
560
561 // compute number of bytes to copy as far as end of window
562 n = (int)((q <= write ? write : end) - q);
563 if(n > z.avail_out) n = z.avail_out;
564 if(n!=0 && r == Z_BUF_ERROR) r = Z_OK;
565
566 // update counters
567 z.avail_out -= n;
568 z.total_out += n;
569
570 // update check information
571 if(check && n>0){
572 z.adler.update(window, q, n);
573 }
574
575 // copy as far as end of window
576 System.arraycopy(window, q, z.next_out, p, n);
577 p += n;
578 q += n;
579
580 // see if more to copy at beginning of window
581 if (q == end){
582 // wrap pointers
583 q = 0;
584 if (write == end)
585 write = 0;
586
587 // compute bytes to copy
588 n = write - q;
589 if (n > z.avail_out) n = z.avail_out;
590 if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
591
592 // update counters
593 z.avail_out -= n;
594 z.total_out += n;
595
596 // update check information
597 if(check && n>0){
598 z.adler.update(window, q, n);
599 }
600
601 // copy
602 System.arraycopy(window, q, z.next_out, p, n);
603 p += n;
604 q += n;
605 }
606
607 // update pointers
608 z.next_out_index = p;
609 read = q;
610
611 // done
612 return r;
613 }
614 }