View Javadoc

1   // DeflaterEngine.java, created Mon Jul  8  4:06:18 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.ClassLib.Common.java.util.zip;
5   
6   /***
7    * DeflaterEngine
8    *
9    * @author  John Whaley <jwhaley@alum.mit.edu>
10   * @version $Id: DeflaterEngine.java 1451 2004-03-09 06:27:08Z jwhaley $
11   */
12  class DeflaterEngine implements DeflaterConstants {
13  
14      private static final int TOO_FAR = 4096;
15  
16      private int ins_h;
17      private byte[] buffer;
18  
19      /***
20       * Hashtable, hashing three characters to an index for window, so
21       * that window[index]..window[index+2] have this hash code.  
22       * Note that the array should really be unsigned short, so you need
23       * to and the values with 0xffff.
24       */
25      private short[] head;
26  
27      /***
28       * prev[index & WMASK] points to the previous index that has the
29       * same hash code as the string starting at index.  This way 
30       * entries with the same hash code are in a linked list.
31       * Note that the array should really be unsigned short, so you need
32       * to and the values with 0xffff.
33       */
34      private short[] prev;
35  
36      private int matchStart, matchLen;
37      private boolean prevAvailable;
38      private int blockStart;
39  
40      /***
41       * strstart points to the current character in window.
42       */
43      private int strstart;
44  
45      /***
46       * lookahead is the number of characters starting at strstart in
47       * window that are valid.
48       * So window[strstart] until window[strstart+lookahead-1] are valid
49       * characters.
50       */
51      private int lookahead;
52      /***
53       * This array contains the part of the uncompressed stream that 
54       * is of relevance.  The current character is indexed by strstart.
55       */
56      private byte[] window;
57  
58      private int strategy, max_chain, max_lazy, niceLength, goodLength;
59  
60      /*** The current compression function. */
61      private int comprFunc;
62  
63      /*** The input data for compression. */
64      private byte[] inputBuf;
65  
66      /*** The total bytes of input read. */
67      private int totalIn;
68  
69      /*** The offset into inputBuf, where input data starts. */
70      private int inputOff;
71  
72      /*** The end offset of the input data. */
73      private int inputEnd;
74  
75      private DeflaterPending pending;
76      private DeflaterHuffman huffman;
77  
78      /*** The adler checksum */
79      private Adler32 adler;
80  
81      /* DEFLATE ALGORITHM:
82       *
83       * The uncompressed stream is inserted into the window array.  When
84       * the window array is full the first half is thrown away and the
85       * second half is copied to the beginning.
86       *
87       * The head array is a hash table.  Three characters build a hash value
88       * and they the value points to the corresponding index in window of 
89       * the last string with this hash.  The prev array implements a
90       * linked list of matches with the same hash: prev[index & WMASK] points
91       * to the previous index with the same hash.
92       * 
93       * 
94       */
95      DeflaterEngine(DeflaterPending pending) {
96          this.pending = pending;
97          huffman = new DeflaterHuffman(pending);
98          adler = new Adler32();
99  
100         window = new byte[2 * WSIZE];
101         head = new short[HASH_SIZE];
102         prev = new short[WSIZE];
103 
104         /* We start at index 1, to avoid a implementation deficiency, that
105          * we cannot build a repeat pattern at index 0.
106          */
107         blockStart = strstart = 1;
108     }
109 
110     public void reset() {
111         huffman.reset();
112         adler.reset();
113         blockStart = strstart = 1;
114         lookahead = 0;
115         totalIn = 0;
116         prevAvailable = false;
117         matchLen = MIN_MATCH - 1;
118         for (int i = 0; i < HASH_SIZE; i++)
119             head[i] = 0;
120         for (int i = 0; i < WSIZE; i++)
121             prev[i] = 0;
122     }
123 
124     public final void resetAdler() {
125         adler.reset();
126     }
127 
128     public final int getAdler() {
129         int chksum = (int) adler.getValue();
130         return chksum;
131     }
132 
133     public final int getTotalIn() {
134         return totalIn;
135     }
136 
137     public final void setStrategy(int strat) {
138         strategy = strat;
139     }
140 
141     public void setLevel(int lvl) {
142         goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
143         max_lazy = DeflaterConstants.MAX_LAZY[lvl];
144         niceLength = DeflaterConstants.NICE_LENGTH[lvl];
145         max_chain = DeflaterConstants.MAX_CHAIN[lvl];
146 
147         if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
148             if (DeflaterConstants.DEBUGGING)
149                 System.err.println(
150                     "Change from "
151                         + comprFunc
152                         + " to "
153                         + DeflaterConstants.COMPR_FUNC[lvl]);
154             switch (comprFunc) {
155                 case DEFLATE_STORED :
156                     if (strstart > blockStart) {
157                         huffman.flushStoredBlock(
158                             window,
159                             blockStart,
160                             strstart - blockStart,
161                             false);
162                         blockStart = strstart;
163                     }
164                     updateHash();
165                     break;
166                 case DEFLATE_FAST :
167                     if (strstart > blockStart) {
168                         huffman.flushBlock(
169                             window,
170                             blockStart,
171                             strstart - blockStart,
172                             false);
173                         blockStart = strstart;
174                     }
175                     break;
176                 case DEFLATE_SLOW :
177                     if (prevAvailable)
178                         huffman.tallyLit(window[strstart - 1] & 0xff);
179                     if (strstart > blockStart) {
180                         huffman.flushBlock(
181                             window,
182                             blockStart,
183                             strstart - blockStart,
184                             false);
185                         blockStart = strstart;
186                     }
187                     prevAvailable = false;
188                     matchLen = MIN_MATCH - 1;
189                     break;
190             }
191             comprFunc = COMPR_FUNC[lvl];
192         }
193     }
194 
195     private final void updateHash() {
196         if (DEBUGGING)
197             System.err.println("updateHash: " + strstart);
198         ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
199     }
200 
201     /***
202      * Inserts the current string in the head hash and returns the previous
203      * value for this hash.
204      */
205     private final int insertString() {
206         short match;
207         int hash =
208             ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH - 1)])
209                 & HASH_MASK;
210 
211         if (DEBUGGING) {
212             if (hash
213                 != (((window[strstart] << (2 * HASH_SHIFT))
214                     ^ (window[strstart + 1] << HASH_SHIFT)
215                     ^ (window[strstart + 2]))
216                     & HASH_MASK))
217                 throw new InternalError(
218                     "hash inconsistent: "
219                         + hash
220                         + "/"
221                         + window[strstart]
222                         + ","
223                         + window[strstart
224                         + 1]
225                         + ","
226                         + window[strstart
227                         + 2]
228                         + ","
229                         + HASH_SHIFT);
230         }
231 
232         prev[strstart & WMASK] = match = head[hash];
233         head[hash] = (short) strstart;
234         ins_h = hash;
235         return match & 0xffff;
236     }
237 
238     private void slideWindow() {
239         System.arraycopy(window, WSIZE, window, 0, WSIZE);
240         matchStart -= WSIZE;
241         strstart -= WSIZE;
242         blockStart -= WSIZE;
243 
244         /* Slide the hash table (could be avoided with 32 bit values
245          * at the expense of memory usage).
246          */
247         for (int i = 0; i < HASH_SIZE; i++) {
248             int m = head[i] & 0xffff;
249             head[i] = m >= WSIZE ? (short) (m - WSIZE) : 0;
250         }
251 
252         /* Slide the prev table.
253          */
254         for (int i = 0; i < WSIZE; i++) {
255             int m = prev[i] & 0xffff;
256             prev[i] = m >= WSIZE ? (short) (m - WSIZE) : 0;
257         }
258     }
259 
260     /***
261      * Fill the window when the lookahead becomes insufficient.
262      * Updates strstart and lookahead.
263      *
264      * OUT assertions: strstart + lookahead &lt;= 2*WSIZE
265      *    lookahead &gt;= MIN_LOOKAHEAD or inputOff == inputEnd
266      */
267     private void fillWindow() {
268         /* If the window is almost full and there is insufficient lookahead,
269          * move the upper half to the lower one to make room in the upper half.
270          */
271         if (strstart >= WSIZE + MAX_DIST)
272             slideWindow();
273 
274         /* If there is not enough lookahead, but still some input left,
275          * read in the input
276          */
277         while (lookahead < DeflaterConstants.MIN_LOOKAHEAD
278             && inputOff < inputEnd) {
279             int more = 2 * WSIZE - lookahead - strstart;
280 
281             if (more > inputEnd - inputOff)
282                 more = inputEnd - inputOff;
283 
284             System.arraycopy(inputBuf, inputOff, window,
285                 strstart + lookahead, more);
286             adler.update(inputBuf, inputOff, more);
287             inputOff += more;
288             totalIn += more;
289             lookahead += more;
290         }
291 
292         if (lookahead >= MIN_MATCH)
293             updateHash();
294     }
295 
296     /***
297      * Find the best (longest) string in the window matching the 
298      * string starting at strstart.
299      *
300      * Preconditions:
301      *    strstart + MAX_MATCH &lt;= window.length.
302      *    
303      * @param curMatch  current match
304      */
305     private boolean findLongestMatch(int curMatch) {
306         int chainLength = this.max_chain;
307         int niceLength = this.niceLength;
308         short[] prev = this.prev;
309         int scan = this.strstart;
310         int match;
311         int best_end = this.strstart + matchLen;
312         int best_len = Math.max(matchLen, MIN_MATCH - 1);
313 
314         int limit = Math.max(strstart - MAX_DIST, 0);
315 
316         int strend = scan + MAX_MATCH - 1;
317         byte scan_end1 = window[best_end - 1];
318         byte scan_end = window[best_end];
319 
320         /* Do not waste too much time if we already have a good match: */
321         if (best_len >= this.goodLength)
322             chainLength >>= 2;
323 
324         /* Do not look for matches beyond the end of the input. This is necessary
325          * to make deflate deterministic.
326          */
327         if (niceLength > lookahead)
328             niceLength = lookahead;
329 
330         if (DeflaterConstants.DEBUGGING
331             && strstart > 2 * WSIZE - MIN_LOOKAHEAD)
332             throw new InternalError("need lookahead");
333 
334         do {
335             if (DeflaterConstants.DEBUGGING && curMatch >= strstart)
336                 throw new InternalError("future match");
337             if (window[curMatch + best_len] != scan_end
338                 || window[curMatch + best_len - 1] != scan_end1
339                 || window[curMatch] != window[scan]
340                 || window[curMatch + 1] != window[scan + 1])
341                 continue;
342 
343             match = curMatch + 2;
344             scan += 2;
345 
346             /* We check for insufficient lookahead only every 8th comparison;
347              * the 256th check will be made at strstart+258.
348              */
349             while (window[++scan] == window[++match]
350                 && window[++scan] == window[++match]
351                 && window[++scan] == window[++match]
352                 && window[++scan] == window[++match]
353                 && window[++scan] == window[++match]
354                 && window[++scan] == window[++match]
355                 && window[++scan] == window[++match]
356                 && window[++scan] == window[++match]
357                 && scan < strend);
358 
359             if (scan > best_end) {
360                 //      if (DeflaterConstants.DEBUGGING && ins_h == 0)
361                 //        System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
362                 matchStart = curMatch;
363                 best_end = scan;
364                 best_len = scan - strstart;
365                 if (best_len >= niceLength)
366                     break;
367 
368                 scan_end1 = window[best_end - 1];
369                 scan_end = window[best_end];
370             }
371             scan = strstart;
372         }
373         while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit
374             && --chainLength != 0);
375 
376         matchLen = Math.min(best_len, lookahead);
377         return matchLen >= MIN_MATCH;
378     }
379 
380     void setDictionary(byte[] buffer, int offset, int length) {
381         if (DeflaterConstants.DEBUGGING && strstart != 1)
382             throw new IllegalStateException("strstart not 1");
383         adler.update(buffer, offset, length);
384         if (length < MIN_MATCH)
385             return;
386         if (length > MAX_DIST) {
387             offset += length - MAX_DIST;
388             length = MAX_DIST;
389         }
390 
391         System.arraycopy(buffer, offset, window, strstart, length);
392 
393         updateHash();
394         length--;
395         while (--length > 0) {
396             insertString();
397             strstart++;
398         }
399         strstart += 2;
400         blockStart = strstart;
401     }
402 
403     private boolean deflateStored(boolean flush, boolean finish) {
404         if (!flush && lookahead == 0)
405             return false;
406 
407         strstart += lookahead;
408         lookahead = 0;
409 
410         int storedLen = strstart - blockStart;
411 
412         if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) /* Block is full */
413             || (blockStart < WSIZE
414                 && storedLen >= MAX_DIST) /* Block may move out of window */
415             || flush) {
416             boolean lastBlock = finish;
417             if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
418                 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
419                 lastBlock = false;
420             }
421 
422             if (DeflaterConstants.DEBUGGING)
423                 System.err.println(
424                     "storedBlock[" + storedLen + "," + lastBlock + "]");
425 
426             huffman.flushStoredBlock(window, blockStart, storedLen, lastBlock);
427             blockStart += storedLen;
428             return !lastBlock;
429         }
430         return true;
431     }
432 
433     private boolean deflateFast(boolean flush, boolean finish) {
434         if (lookahead < MIN_LOOKAHEAD && !flush)
435             return false;
436 
437         while (lookahead >= MIN_LOOKAHEAD || flush) {
438             if (lookahead == 0) {
439                 /* We are flushing everything */
440                 huffman.flushBlock(
441                     window,
442                     blockStart,
443                     strstart - blockStart,
444                     finish);
445                 blockStart = strstart;
446                 return false;
447             }
448 
449             if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
450                 /* slide window, as findLongestMatch need this.
451                  * This should only happen when flushing and the window
452                  * is almost full.
453                  */
454                 slideWindow();
455             }
456 
457             int hashHead;
458             if (lookahead >= MIN_MATCH
459                 && (hashHead = insertString()) != 0
460                 && strategy != Deflater.HUFFMAN_ONLY
461                 && strstart - hashHead <= MAX_DIST
462                 && findLongestMatch(hashHead)) {
463                 /* longestMatch sets matchStart and matchLen */
464                 if (DeflaterConstants.DEBUGGING) {
465                     for (int i = 0; i < matchLen; i++) {
466                         if (window[strstart + i] != window[matchStart + i])
467                             throw new InternalError();
468                     }
469                 }
470                 huffman.tallyDist(strstart - matchStart, matchLen);
471 
472                 lookahead -= matchLen;
473                 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
474                     while (--matchLen > 0) {
475                         strstart++;
476                         insertString();
477                     }
478                     strstart++;
479                 } else {
480                     strstart += matchLen;
481                     if (lookahead >= MIN_MATCH - 1)
482                         updateHash();
483                 }
484                 matchLen = MIN_MATCH - 1;
485                 continue;
486             } else {
487                 /* No match found */
488                 huffman.tallyLit(window[strstart] & 0xff);
489                 strstart++;
490                 lookahead--;
491             }
492 
493             if (huffman.isFull()) {
494                 boolean lastBlock = finish && lookahead == 0;
495                 huffman.flushBlock(
496                     window,
497                     blockStart,
498                     strstart - blockStart,
499                     lastBlock);
500                 blockStart = strstart;
501                 return !lastBlock;
502             }
503         }
504         return true;
505     }
506 
507     private boolean deflateSlow(boolean flush, boolean finish) {
508         if (lookahead < MIN_LOOKAHEAD && !flush)
509             return false;
510 
511         while (lookahead >= MIN_LOOKAHEAD || flush) {
512             if (lookahead == 0) {
513                 if (prevAvailable)
514                     huffman.tallyLit(window[strstart - 1] & 0xff);
515                 prevAvailable = false;
516 
517                 /* We are flushing everything */
518                 if (DeflaterConstants.DEBUGGING && !flush)
519                     throw new InternalError("Not flushing, but no lookahead");
520                 huffman.flushBlock(
521                     window,
522                     blockStart,
523                     strstart - blockStart,
524                     finish);
525                 blockStart = strstart;
526                 return false;
527             }
528 
529             if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) {
530                 /* slide window, as findLongestMatch need this.
531                  * This should only happen when flushing and the window
532                  * is almost full.
533                  */
534                 slideWindow();
535             }
536 
537             int prevMatch = matchStart;
538             int prevLen = matchLen;
539             if (lookahead >= MIN_MATCH) {
540                 int hashHead = insertString();
541                 if (strategy != Deflater.HUFFMAN_ONLY
542                     && hashHead != 0
543                     && strstart - hashHead <= MAX_DIST
544                     && findLongestMatch(hashHead)) {
545                     /* longestMatch sets matchStart and matchLen */
546 
547                     /* Discard match if too small and too far away */
548                     if (matchLen <= 5
549                         && (strategy == Deflater.FILTERED
550                             || (matchLen == MIN_MATCH
551                                 && strstart - matchStart > TOO_FAR))) {
552                         matchLen = MIN_MATCH - 1;
553                     }
554                 }
555             }
556 
557             /* previous match was better */
558             if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
559                 if (DeflaterConstants.DEBUGGING) {
560                     for (int i = 0; i < matchLen; i++) {
561                         if (window[strstart - 1 + i] != window[prevMatch + i])
562                             throw new InternalError();
563                     }
564                 }
565                 huffman.tallyDist(strstart - 1 - prevMatch, prevLen);
566                 prevLen -= 2;
567                 do {
568                     strstart++;
569                     lookahead--;
570                     if (lookahead >= MIN_MATCH)
571                         insertString();
572                 } while (--prevLen > 0);
573                 strstart++;
574                 lookahead--;
575                 prevAvailable = false;
576                 matchLen = MIN_MATCH - 1;
577             } else {
578                 if (prevAvailable)
579                     huffman.tallyLit(window[strstart - 1] & 0xff);
580                 prevAvailable = true;
581                 strstart++;
582                 lookahead--;
583             }
584 
585             if (huffman.isFull()) {
586                 int len = strstart - blockStart;
587                 if (prevAvailable)
588                     len--;
589                 boolean lastBlock =
590                     (finish && lookahead == 0 && !prevAvailable);
591                 huffman.flushBlock(window, blockStart, len, lastBlock);
592                 blockStart += len;
593                 return !lastBlock;
594             }
595         }
596         return true;
597     }
598 
599     public boolean deflate(boolean flush, boolean finish) {
600         boolean progress;
601         do {
602             fillWindow();
603             boolean canFlush = flush && inputOff == inputEnd;
604             if (DeflaterConstants.DEBUGGING)
605                 System.err.println(
606                     "window: ["
607                         + blockStart
608                         + ","
609                         + strstart
610                         + ","
611                         + lookahead
612                         + "], "
613                         + comprFunc
614                         + ","
615                         + canFlush);
616             switch (comprFunc) {
617                 case DEFLATE_STORED :
618                     progress = deflateStored(canFlush, finish);
619                     break;
620                 case DEFLATE_FAST :
621                     progress = deflateFast(canFlush, finish);
622                     break;
623                 case DEFLATE_SLOW :
624                     progress = deflateSlow(canFlush, finish);
625                     break;
626                 default :
627                     throw new InternalError();
628             }
629         } while (pending.isFlushed()
630             /* repeat while we have no pending output */
631             && progress); /* and progress was made */
632 
633         return progress;
634     }
635 
636     public void setInput(byte[] buf, int off, int len) {
637         if (inputOff < inputEnd)
638             throw new IllegalStateException("Old input was not completely processed");
639 
640         int end = off + len;
641 
642         /* We want to throw an ArrayIndexOutOfBoundsException early.  The
643          * check is very tricky: it also handles integer wrap around.  
644          */
645         if (0 > off || off > end || end > buf.length)
646             throw new ArrayIndexOutOfBoundsException();
647 
648         inputBuf = buf;
649         inputOff = off;
650         inputEnd = end;
651     }
652 
653     public final boolean needsInput() {
654         return inputEnd == inputOff;
655     }
656 }