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