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 InfCodes{
38 
39   static final private int[] inflate_mask = {
40     0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
41     0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
42     0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
43     0x00007fff, 0x0000ffff
44   };
45 
46   static final private int Z_OK=0;
47   static final private int Z_STREAM_END=1;
48   static final private int Z_NEED_DICT=2;
49   static final private int Z_ERRNO=-1;
50   static final private int Z_STREAM_ERROR=-2;
51   static final private int Z_DATA_ERROR=-3;
52   static final private int Z_MEM_ERROR=-4;
53   static final private int Z_BUF_ERROR=-5;
54   static final private int Z_VERSION_ERROR=-6;
55 
56   // waiting for "i:"=input,
57   //             "o:"=output,
58   //             "x:"=nothing
59   static final private int START=0;  // x: set up for LEN
60   static final private int LEN=1;    // i: get length/literal/eob next
61   static final private int LENEXT=2; // i: getting length extra (have base)
62   static final private int DIST=3;   // i: get distance next
63   static final private int DISTEXT=4;// i: getting distance extra
64   static final private int COPY=5;   // o: copying bytes in window, waiting for space
65   static final private int LIT=6;    // o: got literal, waiting for output space
66   static final private int WASH=7;   // o: got eob, possibly still output waiting
67   static final private int END=8;    // x: got eob and all data flushed
68   static final private int BADCODE=9;// x: got error
69 
70   int mode;      // current inflate_codes mode
71 
72   // mode dependent information
73   int len;
74 
75   int[] tree; // pointer into tree
76   int tree_index=0;
77   int need;   // bits needed
78 
79   int lit;
80 
81   // if EXT or COPY, where and how much
82   int get;              // bits to get for extra
83   int dist;             // distance back to copy from
84 
85   byte lbits;           // ltree bits decoded per branch
86   byte dbits;           // dtree bits decoder per branch
87   int[] ltree;          // literal/length/eob tree
88   int ltree_index;      // literal/length/eob tree
89   int[] dtree;          // distance tree
90   int dtree_index;      // distance tree
91 
92   private final ZStream z;
93   private final InfBlocks s;
InfCodes(ZStream z, InfBlocks s)94   InfCodes(ZStream z, InfBlocks s){
95     this.z=z;
96     this.s=s;
97   }
98 
init(int bl, int bd, int[] tl, int tl_index, int[] td, int td_index)99   void init(int bl, int bd,
100 	   int[] tl, int tl_index,
101 	   int[] td, int td_index){
102     mode=START;
103     lbits=(byte)bl;
104     dbits=(byte)bd;
105     ltree=tl;
106     ltree_index=tl_index;
107     dtree = td;
108     dtree_index=td_index;
109     tree=null;
110   }
111 
proc(int r)112   int proc(int r){
113     int j;              // temporary storage
114     int[] t;            // temporary pointer
115     int tindex;         // temporary pointer
116     int e;              // extra bits or operation
117     int b=0;            // bit buffer
118     int k=0;            // bits in bit buffer
119     int p=0;            // input data pointer
120     int n;              // bytes available there
121     int q;              // output window write pointer
122     int m;              // bytes to end of window or read pointer
123     int f;              // pointer to copy strings from
124 
125     // copy input/output information to locals (UPDATE macro restores)
126     p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
127     q=s.write;m=q<s.read?s.read-q-1:s.end-q;
128 
129     // process input and output based on current state
130     while (true){
131       switch (mode){
132 	// waiting for "i:"=input, "o:"=output, "x:"=nothing
133       case START:         // x: set up for LEN
134 	if (m >= 258 && n >= 10){
135 
136 	  s.bitb=b;s.bitk=k;
137 	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
138 	  s.write=q;
139 	  r = inflate_fast(lbits, dbits,
140 			   ltree, ltree_index,
141 			   dtree, dtree_index,
142 			   s, z);
143 
144 	  p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
145 	  q=s.write;m=q<s.read?s.read-q-1:s.end-q;
146 
147 	  if (r != Z_OK){
148 	    mode = r == Z_STREAM_END ? WASH : BADCODE;
149 	    break;
150 	  }
151 	}
152 	need = lbits;
153 	tree = ltree;
154 	tree_index=ltree_index;
155 
156 	mode = LEN;
157       case LEN:           // i: get length/literal/eob next
158 	j = need;
159 
160 	while(k<(j)){
161 	  if(n!=0)r=Z_OK;
162 	  else{
163 
164 	    s.bitb=b;s.bitk=k;
165 	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
166 	    s.write=q;
167 	    return s.inflate_flush(r);
168 	  }
169 	  n--;
170 	  b|=(z.next_in[p++]&0xff)<<k;
171 	  k+=8;
172 	}
173 
174 	tindex=(tree_index+(b&inflate_mask[j]))*3;
175 
176 	b>>>=(tree[tindex+1]);
177 	k-=(tree[tindex+1]);
178 
179 	e=tree[tindex];
180 
181 	if(e == 0){               // literal
182 	  lit = tree[tindex+2];
183 	  mode = LIT;
184 	  break;
185 	}
186 	if((e & 16)!=0 ){          // length
187 	  get = e & 15;
188 	  len = tree[tindex+2];
189 	  mode = LENEXT;
190 	  break;
191 	}
192 	if ((e & 64) == 0){        // next table
193 	  need = e;
194 	  tree_index = tindex/3+tree[tindex+2];
195 	  break;
196 	}
197 	if ((e & 32)!=0){               // end of block
198 	  mode = WASH;
199 	  break;
200 	}
201 	mode = BADCODE;        // invalid code
202 	z.msg = "invalid literal/length code";
203 	r = Z_DATA_ERROR;
204 
205 	s.bitb=b;s.bitk=k;
206 	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
207 	s.write=q;
208 	return s.inflate_flush(r);
209 
210       case LENEXT:        // i: getting length extra (have base)
211 	j = get;
212 
213 	while(k<(j)){
214 	  if(n!=0)r=Z_OK;
215 	  else{
216 
217 	    s.bitb=b;s.bitk=k;
218 	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
219 	    s.write=q;
220 	    return s.inflate_flush(r);
221 	  }
222 	  n--; b|=(z.next_in[p++]&0xff)<<k;
223 	  k+=8;
224 	}
225 
226 	len += (b & inflate_mask[j]);
227 
228 	b>>=j;
229 	k-=j;
230 
231 	need = dbits;
232 	tree = dtree;
233 	tree_index=dtree_index;
234 	mode = DIST;
235       case DIST:          // i: get distance next
236 	j = need;
237 
238 	while(k<(j)){
239 	  if(n!=0)r=Z_OK;
240 	  else{
241 
242 	    s.bitb=b;s.bitk=k;
243 	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
244 	    s.write=q;
245 	    return s.inflate_flush(r);
246 	  }
247 	  n--; b|=(z.next_in[p++]&0xff)<<k;
248 	  k+=8;
249 	}
250 
251 	tindex=(tree_index+(b & inflate_mask[j]))*3;
252 
253 	b>>=tree[tindex+1];
254 	k-=tree[tindex+1];
255 
256 	e = (tree[tindex]);
257 	if((e & 16)!=0){               // distance
258 	  get = e & 15;
259 	  dist = tree[tindex+2];
260 	  mode = DISTEXT;
261 	  break;
262 	}
263 	if ((e & 64) == 0){        // next table
264 	  need = e;
265 	  tree_index = tindex/3 + tree[tindex+2];
266 	  break;
267 	}
268 	mode = BADCODE;        // invalid code
269 	z.msg = "invalid distance code";
270 	r = Z_DATA_ERROR;
271 
272 	s.bitb=b;s.bitk=k;
273 	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
274 	s.write=q;
275 	return s.inflate_flush(r);
276 
277       case DISTEXT:       // i: getting distance extra
278 	j = get;
279 
280 	while(k<(j)){
281 	  if(n!=0)r=Z_OK;
282 	  else{
283 
284 	    s.bitb=b;s.bitk=k;
285 	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
286 	    s.write=q;
287 	    return s.inflate_flush(r);
288 	  }
289 	  n--; b|=(z.next_in[p++]&0xff)<<k;
290 	  k+=8;
291 	}
292 
293 	dist += (b & inflate_mask[j]);
294 
295 	b>>=j;
296 	k-=j;
297 
298 	mode = COPY;
299       case COPY:          // o: copying bytes in window, waiting for space
300         f = q - dist;
301         while(f < 0){     // modulo window size-"while" instead
302           f += s.end;     // of "if" handles invalid distances
303 	}
304 	while (len!=0){
305 
306 	  if(m==0){
307 	    if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
308 	    if(m==0){
309 	      s.write=q; r=s.inflate_flush(r);
310 	      q=s.write;m=q<s.read?s.read-q-1:s.end-q;
311 
312 	      if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
313 
314 	      if(m==0){
315 		s.bitb=b;s.bitk=k;
316 		z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
317 		s.write=q;
318 		return s.inflate_flush(r);
319 	      }
320 	    }
321 	  }
322 
323 	  s.window[q++]=s.window[f++]; m--;
324 
325 	  if (f == s.end)
326             f = 0;
327 	  len--;
328 	}
329 	mode = START;
330 	break;
331       case LIT:           // o: got literal, waiting for output space
332 	if(m==0){
333 	  if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
334 	  if(m==0){
335 	    s.write=q; r=s.inflate_flush(r);
336 	    q=s.write;m=q<s.read?s.read-q-1:s.end-q;
337 
338 	    if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
339 	    if(m==0){
340 	      s.bitb=b;s.bitk=k;
341 	      z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
342 	      s.write=q;
343 	      return s.inflate_flush(r);
344 	    }
345 	  }
346 	}
347 	r=Z_OK;
348 
349 	s.window[q++]=(byte)lit; m--;
350 
351 	mode = START;
352 	break;
353       case WASH:           // o: got eob, possibly more output
354 	if (k > 7){        // return unused byte, if any
355 	  k -= 8;
356 	  n++;
357 	  p--;             // can always return one
358 	}
359 
360 	s.write=q; r=s.inflate_flush(r);
361 	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
362 
363 	if (s.read != s.write){
364 	  s.bitb=b;s.bitk=k;
365 	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
366 	  s.write=q;
367 	  return s.inflate_flush(r);
368 	}
369 	mode = END;
370       case END:
371 	r = Z_STREAM_END;
372 	s.bitb=b;s.bitk=k;
373 	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
374 	s.write=q;
375 	return s.inflate_flush(r);
376 
377       case BADCODE:       // x: got error
378 
379 	r = Z_DATA_ERROR;
380 
381 	s.bitb=b;s.bitk=k;
382 	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
383 	s.write=q;
384 	return s.inflate_flush(r);
385 
386       default:
387 	r = Z_STREAM_ERROR;
388 
389 	s.bitb=b;s.bitk=k;
390 	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
391 	s.write=q;
392 	return s.inflate_flush(r);
393       }
394     }
395   }
396 
397   void free(ZStream z){
398     //  ZFREE(z, c);
399   }
400 
401   // Called with number of bytes left to write in window at least 258
402   // (the maximum string length) and number of input bytes available
403   // at least ten.  The ten bytes are six bytes for the longest length/
404   // distance pair plus four bytes for overloading the bit buffer.
405 
406   int inflate_fast(int bl, int bd,
407 		   int[] tl, int tl_index,
408 		   int[] td, int td_index,
409 		   InfBlocks s, ZStream z){
410     int t;                // temporary pointer
411     int[] tp;             // temporary pointer
412     int tp_index;         // temporary pointer
413     int e;                // extra bits or operation
414     int b;                // bit buffer
415     int k;                // bits in bit buffer
416     int p;                // input data pointer
417     int n;                // bytes available there
418     int q;                // output window write pointer
419     int m;                // bytes to end of window or read pointer
420     int ml;               // mask for literal/length tree
421     int md;               // mask for distance tree
422     int c;                // bytes to copy
423     int d;                // distance back to copy from
424     int r;                // copy source pointer
425 
426     int tp_index_t_3;     // (tp_index+t)*3
427 
428     // load input, output, bit values
429     p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
430     q=s.write;m=q<s.read?s.read-q-1:s.end-q;
431 
432     // initialize masks
433     ml = inflate_mask[bl];
434     md = inflate_mask[bd];
435 
436     // do until not enough input or output space for fast loop
437     do {                          // assume called with m >= 258 && n >= 10
438       // get literal/length code
439       while(k<(20)){              // max bits for literal/length code
440 	n--;
441 	b|=(z.next_in[p++]&0xff)<<k;k+=8;
442       }
443 
444       t= b&ml;
445       tp=tl;
446       tp_index=tl_index;
447       tp_index_t_3=(tp_index+t)*3;
448       if ((e = tp[tp_index_t_3]) == 0){
449 	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
450 
451 	s.window[q++] = (byte)tp[tp_index_t_3+2];
452 	m--;
453 	continue;
454       }
455       do {
456 
457 	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
458 
459 	if((e&16)!=0){
460 	  e &= 15;
461 	  c = tp[tp_index_t_3+2] + ((int)b & inflate_mask[e]);
462 
463 	  b>>=e; k-=e;
464 
465 	  // decode distance base of block to copy
466 	  while(k<(15)){           // max bits for distance code
467 	    n--;
468 	    b|=(z.next_in[p++]&0xff)<<k;k+=8;
469 	  }
470 
471 	  t= b&md;
472 	  tp=td;
473 	  tp_index=td_index;
474           tp_index_t_3=(tp_index+t)*3;
475 	  e = tp[tp_index_t_3];
476 
477 	  do {
478 
479 	    b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
480 
481 	    if((e&16)!=0){
482 	      // get extra bits to add to distance base
483 	      e &= 15;
484 	      while(k<(e)){         // get extra bits (up to 13)
485 		n--;
486 		b|=(z.next_in[p++]&0xff)<<k;k+=8;
487 	      }
488 
489 	      d = tp[tp_index_t_3+2] + (b&inflate_mask[e]);
490 
491 	      b>>=(e); k-=(e);
492 
493 	      // do the copy
494 	      m -= c;
495 	      if (q >= d){                // offset before dest
496 		//  just copy
497 		r=q-d;
498 		if(q-r>0 && 2>(q-r)){
499 		  s.window[q++]=s.window[r++]; // minimum count is three,
500 		  s.window[q++]=s.window[r++]; // so unroll loop a little
501 		  c-=2;
502 		}
503 		else{
504 		  System.arraycopy(s.window, r, s.window, q, 2);
505 		  q+=2; r+=2; c-=2;
506 		}
507 	      }
508 	      else{                  // else offset after destination
509                 r=q-d;
510                 do{
511                   r+=s.end;          // force pointer in window
512                 }while(r<0);         // covers invalid distances
513 		e=s.end-r;
514 		if(c>e){             // if source crosses,
515 		  c-=e;              // wrapped copy
516 		  if(q-r>0 && e>(q-r)){
517 		    do{s.window[q++] = s.window[r++];}
518 		    while(--e!=0);
519 		  }
520 		  else{
521 		    System.arraycopy(s.window, r, s.window, q, e);
522 		    q+=e; r+=e; e=0;
523 		  }
524 		  r = 0;                  // copy rest from start of window
525 		}
526 
527 	      }
528 
529 	      // copy all or what's left
530 	      if(q-r>0 && c>(q-r)){
531 		do{s.window[q++] = s.window[r++];}
532 		while(--c!=0);
533 	      }
534 	      else{
535 		System.arraycopy(s.window, r, s.window, q, c);
536 		q+=c; r+=c; c=0;
537 	      }
538 	      break;
539 	    }
540 	    else if((e&64)==0){
541 	      t+=tp[tp_index_t_3+2];
542 	      t+=(b&inflate_mask[e]);
543 	      tp_index_t_3=(tp_index+t)*3;
544 	      e=tp[tp_index_t_3];
545 	    }
546 	    else{
547 	      z.msg = "invalid distance code";
548 
549 	      c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
550 
551 	      s.bitb=b;s.bitk=k;
552 	      z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
553 	      s.write=q;
554 
555 	      return Z_DATA_ERROR;
556 	    }
557 	  }
558 	  while(true);
559 	  break;
560 	}
561 
562 	if((e&64)==0){
563 	  t+=tp[tp_index_t_3+2];
564 	  t+=(b&inflate_mask[e]);
565 	  tp_index_t_3=(tp_index+t)*3;
566 	  if((e=tp[tp_index_t_3])==0){
567 
568 	    b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
569 
570 	    s.window[q++]=(byte)tp[tp_index_t_3+2];
571 	    m--;
572 	    break;
573 	  }
574 	}
575 	else if((e&32)!=0){
576 
577 	  c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
578 
579 	  s.bitb=b;s.bitk=k;
580 	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
581 	  s.write=q;
582 
583 	  return Z_STREAM_END;
584 	}
585 	else{
586 	  z.msg="invalid literal/length code";
587 
588 	  c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
589 
590 	  s.bitb=b;s.bitk=k;
591 	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
592 	  s.write=q;
593 
594 	  return Z_DATA_ERROR;
595 	}
596       }
597       while(true);
598     }
599     while(m>=258 && n>= 10);
600 
601     // not enough input or output--restore pointers and return
602     c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
603 
604     s.bitb=b;s.bitk=k;
605     z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
606     s.write=q;
607 
608     return Z_OK;
609   }
610 }
611