KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > jcraft > jzlib > InfBlocks


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 JavaDoc checkfn; // check function
97 long check; // check on output
98
99   InfTree inftree=new InfTree();
100
101   InfBlocks(ZStream z, Object JavaDoc 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 }
615
Popular Tags