]> Joshua Wise's Git repositories - dumload.git/blob - src/com/jcraft/jzlib/InfBlocks.java
Fix stray DOS line endings
[dumload.git] / src / com / jcraft / jzlib / InfBlocks.java
1 /* -*-mode:java; c-basic-offset:2; -*- */
2 /*
3 Copyright (c) 2000,2001,2002,2003 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   InfCodes codes=new InfCodes();      // if CODES, current state 
85
86   int last;            // true if this block is the last block 
87
88   // mode independent information 
89   int bitk;            // bits in bit buffer 
90   int bitb;            // bit buffer 
91   int[] hufts;         // single malloc for tree space 
92   byte[] window;       // sliding window 
93   int end;             // one byte after sliding window 
94   int read;            // window read pointer 
95   int write;           // window write pointer 
96   Object checkfn;      // check function 
97   long check;          // check on output 
98
99   InfTree inftree=new InfTree();
100
101   InfBlocks(ZStream z, Object checkfn, int w){
102     hufts=new int[MANY*3];
103     window=new byte[w];
104     end=w;
105     this.checkfn = checkfn;
106     mode = TYPE;
107     reset(z, null);
108   }
109
110   void reset(ZStream z, long[] c){
111     if(c!=null) c[0]=check;
112     if(mode==BTREE || mode==DTREE){
113     }
114     if(mode==CODES){
115       codes.free(z);
116     }
117     mode=TYPE;
118     bitk=0;
119     bitb=0;
120     read=write=0;
121
122     if(checkfn != null)
123       z.adler=check=z._adler.adler32(0L, null, 0, 0);
124   }
125
126   int proc(ZStream z, int r){
127     int t;              // temporary storage
128     int b;              // bit buffer
129     int k;              // bits in bit buffer
130     int p;              // input data pointer
131     int n;              // bytes available there
132     int q;              // output window write pointer
133     int m;              // bytes to end of window or read pointer
134
135     // copy input/output information to locals (UPDATE macro restores)
136     {p=z.next_in_index;n=z.avail_in;b=bitb;k=bitk;}
137     {q=write;m=(int)(q<read?read-q-1:end-q);}
138
139     // process input based on current state
140     while(true){
141       switch (mode){
142       case TYPE:
143
144         while(k<(3)){
145           if(n!=0){
146             r=Z_OK;
147           }
148           else{
149             bitb=b; bitk=k; 
150             z.avail_in=n;
151             z.total_in+=p-z.next_in_index;z.next_in_index=p;
152             write=q;
153             return inflate_flush(z,r);
154           };
155           n--;
156           b|=(z.next_in[p++]&0xff)<<k;
157           k+=8;
158         }
159         t = (int)(b & 7);
160         last = t & 1;
161
162         switch (t >>> 1){
163         case 0:                         // stored 
164           {b>>>=(3);k-=(3);}
165           t = k & 7;                    // go to byte boundary
166
167           {b>>>=(t);k-=(t);}
168           mode = LENS;                  // get length of stored block
169           break;
170         case 1:                         // fixed
171           {
172             int[] bl=new int[1];
173             int[] bd=new int[1];
174             int[][] tl=new int[1][];
175             int[][] td=new int[1][];
176
177             InfTree.inflate_trees_fixed(bl, bd, tl, td, z);
178             codes.init(bl[0], bd[0], tl[0], 0, td[0], 0, z);
179           }
180
181           {b>>>=(3);k-=(3);}
182
183           mode = CODES;
184           break;
185         case 2:                         // dynamic
186
187           {b>>>=(3);k-=(3);}
188
189           mode = TABLE;
190           break;
191         case 3:                         // illegal
192
193           {b>>>=(3);k-=(3);}
194           mode = BAD;
195           z.msg = "invalid block type";
196           r = Z_DATA_ERROR;
197
198           bitb=b; bitk=k; 
199           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
200           write=q;
201           return inflate_flush(z,r);
202         }
203         break;
204       case LENS:
205
206         while(k<(32)){
207           if(n!=0){
208             r=Z_OK;
209           }
210           else{
211             bitb=b; bitk=k; 
212             z.avail_in=n;
213             z.total_in+=p-z.next_in_index;z.next_in_index=p;
214             write=q;
215             return inflate_flush(z,r);
216           };
217           n--;
218           b|=(z.next_in[p++]&0xff)<<k;
219           k+=8;
220         }
221
222         if ((((~b) >>> 16) & 0xffff) != (b & 0xffff)){
223           mode = BAD;
224           z.msg = "invalid stored block lengths";
225           r = Z_DATA_ERROR;
226
227           bitb=b; bitk=k; 
228           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
229           write=q;
230           return inflate_flush(z,r);
231         }
232         left = (b & 0xffff);
233         b = k = 0;                       // dump bits
234         mode = left!=0 ? STORED : (last!=0 ? DRY : TYPE);
235         break;
236       case STORED:
237         if (n == 0){
238           bitb=b; bitk=k; 
239           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
240           write=q;
241           return inflate_flush(z,r);
242         }
243
244         if(m==0){
245           if(q==end&&read!=0){
246             q=0; m=(int)(q<read?read-q-1:end-q);
247           }
248           if(m==0){
249             write=q; 
250             r=inflate_flush(z,r);
251             q=write;m=(int)(q<read?read-q-1:end-q);
252             if(q==end&&read!=0){
253               q=0; m=(int)(q<read?read-q-1:end-q);
254             }
255             if(m==0){
256               bitb=b; bitk=k; 
257               z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
258               write=q;
259               return inflate_flush(z,r);
260             }
261           }
262         }
263         r=Z_OK;
264
265         t = left;
266         if(t>n) t = n;
267         if(t>m) t = m;
268         System.arraycopy(z.next_in, p, window, q, t);
269         p += t;  n -= t;
270         q += t;  m -= t;
271         if ((left -= t) != 0)
272           break;
273         mode = last!=0 ? DRY : TYPE;
274         break;
275       case TABLE:
276
277         while(k<(14)){
278           if(n!=0){
279             r=Z_OK;
280           }
281           else{
282             bitb=b; bitk=k; 
283             z.avail_in=n;
284             z.total_in+=p-z.next_in_index;z.next_in_index=p;
285             write=q;
286             return inflate_flush(z,r);
287           };
288           n--;
289           b|=(z.next_in[p++]&0xff)<<k;
290           k+=8;
291         }
292
293         table = t = (b & 0x3fff);
294         if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
295           {
296             mode = BAD;
297             z.msg = "too many length or distance symbols";
298             r = Z_DATA_ERROR;
299
300             bitb=b; bitk=k; 
301             z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
302             write=q;
303             return inflate_flush(z,r);
304           }
305         t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
306         if(blens==null || blens.length<t){
307           blens=new int[t];
308         }
309         else{
310           for(int i=0; i<t; i++){blens[i]=0;}
311         }
312
313         {b>>>=(14);k-=(14);}
314
315         index = 0;
316         mode = BTREE;
317       case BTREE:
318         while (index < 4 + (table >>> 10)){
319           while(k<(3)){
320             if(n!=0){
321               r=Z_OK;
322             }
323             else{
324               bitb=b; bitk=k; 
325               z.avail_in=n;
326               z.total_in+=p-z.next_in_index;z.next_in_index=p;
327               write=q;
328               return inflate_flush(z,r);
329             };
330             n--;
331             b|=(z.next_in[p++]&0xff)<<k;
332             k+=8;
333           }
334
335           blens[border[index++]] = b&7;
336
337           {b>>>=(3);k-=(3);}
338         }
339
340         while(index < 19){
341           blens[border[index++]] = 0;
342         }
343
344         bb[0] = 7;
345         t = inftree.inflate_trees_bits(blens, bb, tb, hufts, z);
346         if (t != Z_OK){
347           r = t;
348           if (r == Z_DATA_ERROR){
349             blens=null;
350             mode = BAD;
351           }
352
353           bitb=b; bitk=k; 
354           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
355           write=q;
356           return inflate_flush(z,r);
357         }
358
359         index = 0;
360         mode = DTREE;
361       case DTREE:
362         while (true){
363           t = table;
364           if(!(index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))){
365             break;
366           }
367
368           int[] h;
369           int i, j, c;
370
371           t = bb[0];
372
373           while(k<(t)){
374             if(n!=0){
375               r=Z_OK;
376             }
377             else{
378               bitb=b; bitk=k; 
379               z.avail_in=n;
380               z.total_in+=p-z.next_in_index;z.next_in_index=p;
381               write=q;
382               return inflate_flush(z,r);
383             };
384             n--;
385             b|=(z.next_in[p++]&0xff)<<k;
386             k+=8;
387           }
388
389           if(tb[0]==-1){
390             //System.err.println("null...");
391           }
392
393           t=hufts[(tb[0]+(b&inflate_mask[t]))*3+1];
394           c=hufts[(tb[0]+(b&inflate_mask[t]))*3+2];
395
396           if (c < 16){
397             b>>>=(t);k-=(t);
398             blens[index++] = c;
399           }
400           else { // c == 16..18
401             i = c == 18 ? 7 : c - 14;
402             j = c == 18 ? 11 : 3;
403
404             while(k<(t+i)){
405               if(n!=0){
406                 r=Z_OK;
407               }
408               else{
409                 bitb=b; bitk=k; 
410                 z.avail_in=n;
411                 z.total_in+=p-z.next_in_index;z.next_in_index=p;
412                 write=q;
413                 return inflate_flush(z,r);
414               };
415               n--;
416               b|=(z.next_in[p++]&0xff)<<k;
417               k+=8;
418             }
419
420             b>>>=(t);k-=(t);
421
422             j += (b & inflate_mask[i]);
423
424             b>>>=(i);k-=(i);
425
426             i = index;
427             t = table;
428             if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
429                 (c == 16 && i < 1)){
430               blens=null;
431               mode = BAD;
432               z.msg = "invalid bit length repeat";
433               r = Z_DATA_ERROR;
434
435               bitb=b; bitk=k; 
436               z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
437               write=q;
438               return inflate_flush(z,r);
439             }
440
441             c = c == 16 ? blens[i-1] : 0;
442             do{
443               blens[i++] = c;
444             }
445             while (--j!=0);
446             index = i;
447           }
448         }
449
450         tb[0]=-1;
451         {
452           int[] bl=new int[1];
453           int[] bd=new int[1];
454           int[] tl=new int[1];
455           int[] td=new int[1];
456           bl[0] = 9;         // must be <= 9 for lookahead assumptions
457           bd[0] = 6;         // must be <= 9 for lookahead assumptions
458
459           t = table;
460           t = inftree.inflate_trees_dynamic(257 + (t & 0x1f), 
461                                             1 + ((t >> 5) & 0x1f),
462                                             blens, bl, bd, tl, td, hufts, z);
463
464           if (t != Z_OK){
465             if (t == Z_DATA_ERROR){
466               blens=null;
467               mode = BAD;
468             }
469             r = t;
470
471             bitb=b; bitk=k; 
472             z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
473             write=q;
474             return inflate_flush(z,r);
475           }
476           codes.init(bl[0], bd[0], hufts, tl[0], hufts, td[0], z);
477         }
478         mode = CODES;
479       case CODES:
480         bitb=b; bitk=k;
481         z.avail_in=n; z.total_in+=p-z.next_in_index;z.next_in_index=p;
482         write=q;
483
484         if ((r = codes.proc(this, z, r)) != Z_STREAM_END){
485           return inflate_flush(z, r);
486         }
487         r = Z_OK;
488         codes.free(z);
489
490         p=z.next_in_index; n=z.avail_in;b=bitb;k=bitk;
491         q=write;m=(int)(q<read?read-q-1:end-q);
492
493         if (last==0){
494           mode = TYPE;
495           break;
496         }
497         mode = DRY;
498       case DRY:
499         write=q; 
500         r=inflate_flush(z, r); 
501         q=write; m=(int)(q<read?read-q-1:end-q);
502         if (read != write){
503           bitb=b; bitk=k; 
504           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
505           write=q;
506           return inflate_flush(z, r);
507         }
508         mode = DONE;
509       case DONE:
510         r = Z_STREAM_END;
511
512         bitb=b; bitk=k; 
513         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
514         write=q;
515         return inflate_flush(z, r);
516       case BAD:
517         r = Z_DATA_ERROR;
518
519         bitb=b; bitk=k; 
520         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
521         write=q;
522         return inflate_flush(z, r);
523
524       default:
525         r = Z_STREAM_ERROR;
526
527         bitb=b; bitk=k; 
528         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
529         write=q;
530         return inflate_flush(z, r);
531       }
532     }
533   }
534
535   void free(ZStream z){
536     reset(z, null);
537     window=null;
538     hufts=null;
539     //ZFREE(z, s);
540   }
541
542   void set_dictionary(byte[] d, int start, int n){
543     System.arraycopy(d, start, window, 0, n);
544     read = write = n;
545   }
546
547   // Returns true if inflate is currently at the end of a block generated
548   // by Z_SYNC_FLUSH or Z_FULL_FLUSH. 
549   int sync_point(){
550     return mode == LENS ? 1 : 0;
551   }
552
553   // copy as much as possible from the sliding window to the output area
554   int inflate_flush(ZStream z, int r){
555     int n;
556     int p;
557     int q;
558
559     // local copies of source and destination pointers
560     p = z.next_out_index;
561     q = read;
562
563     // compute number of bytes to copy as far as end of window
564     n = (int)((q <= write ? write : end) - q);
565     if (n > z.avail_out) n = z.avail_out;
566     if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
567
568     // update counters
569     z.avail_out -= n;
570     z.total_out += n;
571
572     // update check information
573     if(checkfn != null)
574       z.adler=check=z._adler.adler32(check, window, q, n);
575
576     // copy as far as end of window
577     System.arraycopy(window, q, z.next_out, p, n);
578     p += n;
579     q += n;
580
581     // see if more to copy at beginning of window
582     if (q == end){
583       // wrap pointers
584       q = 0;
585       if (write == end)
586         write = 0;
587
588       // compute bytes to copy
589       n = write - q;
590       if (n > z.avail_out) n = z.avail_out;
591       if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
592
593       // update counters
594       z.avail_out -= n;
595       z.total_out += n;
596
597       // update check information
598       if(checkfn != null)
599         z.adler=check=z._adler.adler32(check, window, q, n);
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 }
This page took 0.056711 seconds and 4 git commands to generate.