?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
**** Merged from MCS ****
[mono-project.git] / mcs / class / ICSharpCode.SharpZipLib / ICSharpCode.SharpZipLib / Zip / Compression / DeflaterEngine.cs
blobc543f8509808875aa9c8618b128a3d6652d3ff8b
1 // DeflaterEngine.cs
2 // Copyright (C) 2001 Mike Krueger
3 //
4 // This file was translated from java, it was part of the GNU Classpath
5 // Copyright (C) 2001 Free Software Foundation, Inc.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 //
17 // You should have received a copy of the GNU General Public License
18 // along with this program; if not, write to the Free Software
19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 using System;
39
40 using ICSharpCode.SharpZipLib.Checksums;
41
42 namespace ICSharpCode.SharpZipLib.Zip.Compression
43 {
44
45 public enum DeflateStrategy
46 {
47 // The default strategy.
48 Default = 0,
49
50 // This strategy will only allow longer string repetitions. It is
51 // useful for random data with a small character set.
52 Filtered = 1,
53
54 // This strategy will not look for string repetitions at all. It
55 // only encodes with Huffman trees (which means, that more common
56 // characters get a smaller encoding.
57 HuffmanOnly = 2
58 }
59
60 public class DeflaterEngine : DeflaterConstants
61 {
62 static int TOO_FAR = 4096;
63
64 int ins_h;
65 // private byte[] buffer;
66 short[] head;
67 short[] prev;
68
69 int matchStart, matchLen;
70 bool prevAvailable;
71 int blockStart;
72 int strstart, lookahead;
73 byte[] window;
74
75 DeflateStrategy strategy;
76 int max_chain, max_lazy, niceLength, goodLength;
77
78 /// <summary>
79 /// The current compression function.
80 /// </summary>
81 int comprFunc;
82
83 /// <summary>
84 /// The input data for compression.
85 /// </summary>
86 byte[] inputBuf;
87
88 /// <summary>
89 /// The total bytes of input read.
90 /// </summary>
91 int totalIn;
92
93 /// <summary>
94 /// The offset into inputBuf, where input data starts.
95 /// </summary>
96 int inputOff;
97
98 /// <summary>
99 /// The end offset of the input data.
100 /// </summary>
101 int inputEnd;
102
103 DeflaterPending pending;
104 DeflaterHuffman huffman;
105
106 /// <summary>
107 /// The adler checksum
108 /// </summary>
109 Adler32 adler;
110
111 public DeflaterEngine(DeflaterPending pending)
112 {
113 this.pending = pending;
114 huffman = new DeflaterHuffman(pending);
115 adler = new Adler32();
116
117 window = new byte[2 * WSIZE];
118 head = new short[HASH_SIZE];
119 prev = new short[WSIZE];
120
121 /* We start at index 1, to avoid a implementation deficiency, that
122 * we cannot build a repeat pattern at index 0.
123 */
124 blockStart = strstart = 1;
125 }
126
127 public void Reset()
128 {
129 huffman.Reset();
130 adler.Reset();
131 blockStart = strstart = 1;
132 lookahead = 0;
133 totalIn = 0;
134 prevAvailable = false;
135 matchLen = MIN_MATCH - 1;
136
137 for (int i = 0; i < HASH_SIZE; i++) {
138 head[i] = 0;
139 }
140
141 for (int i = 0; i < WSIZE; i++) {
142 prev[i] = 0;
143 }
144 }
145
146 public void ResetAdler()
147 {
148 adler.Reset();
149 }
150
151 public int Adler {
152 get {
153 return (int)adler.Value;
154 }
155 }
156
157 public int TotalIn {
158 get {
159 return totalIn;
160 }
161 }
162
163 public DeflateStrategy Strategy {
164 get {
165 return strategy;
166 }
167 set {
168 strategy = value;
169 }
170 }
171
172 public void SetLevel(int lvl)
173 {
174 goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
175 max_lazy = DeflaterConstants.MAX_LAZY[lvl];
176 niceLength = DeflaterConstants.NICE_LENGTH[lvl];
177 max_chain = DeflaterConstants.MAX_CHAIN[lvl];
178
179 if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
180 // if (DeflaterConstants.DEBUGGING) {
181 // //Console.WriteLine("Change from "+comprFunc +" to "
182 // + DeflaterConstants.COMPR_FUNC[lvl]);
183 // }
184 switch (comprFunc) {
185 case DEFLATE_STORED:
186 if (strstart > blockStart) {
187 huffman.FlushStoredBlock(window, blockStart,
188 strstart - blockStart, false);
189 blockStart = strstart;
190 }
191 UpdateHash();
192 break;
193 case DEFLATE_FAST:
194 if (strstart > blockStart) {
195 huffman.FlushBlock(window, blockStart, strstart - blockStart,
196 false);
197 blockStart = strstart;
198 }
199 break;
200 case DEFLATE_SLOW:
201 if (prevAvailable) {
202 huffman.TallyLit(window[strstart-1] & 0xff);
203 }
204 if (strstart > blockStart) {
205 huffman.FlushBlock(window, blockStart, strstart - blockStart, false);
206 blockStart = strstart;
207 }
208 prevAvailable = false;
209 matchLen = MIN_MATCH - 1;
210 break;
211 }
212 comprFunc = COMPR_FUNC[lvl];
213 }
214 }
215
216 void UpdateHash()
217 {
218 // if (DEBUGGING) {
219 // //Console.WriteLine("updateHash: "+strstart);
220 // }
221 ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
222 }
223
224 int InsertString()
225 {
226 short match;
227 int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
228
229 // if (DEBUGGING) {
230 // if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
231 // (window[strstart + 1] << HASH_SHIFT) ^
232 // (window[strstart + 2])) & HASH_MASK)) {
233 // throw new Exception("hash inconsistent: "+hash+"/"
234 // +window[strstart]+","
235 // +window[strstart+1]+","
236 // +window[strstart+2]+","+HASH_SHIFT);
237 // }
238 // }
239
240 prev[strstart & WMASK] = match = head[hash];
241 head[hash] = (short)strstart;
242 ins_h = hash;
243 return match & 0xffff;
244 }
245
246 void SlideWindow()
247 {
248 Array.Copy(window, WSIZE, window, 0, WSIZE);
249 matchStart -= WSIZE;
250 strstart -= WSIZE;
251 blockStart -= WSIZE;
252
253 /* Slide the hash table (could be avoided with 32 bit values
254 * at the expense of memory usage).
255 */
256 for (int i = 0; i < HASH_SIZE; ++i) {
257 int m = head[i] & 0xffff;
258 head[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
259 }
260
261 /* Slide the prev table. */
262 for (int i = 0; i < WSIZE; i++) {
263 int m = prev[i] & 0xffff;
264 prev[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
265 }
266 }
267
268 public void FillWindow()
269 {
270 /* If the window is almost full and there is insufficient lookahead,
271 * move the upper half to the lower one to make room in the upper half.
272 */
273 if (strstart >= WSIZE + MAX_DIST) {
274 SlideWindow();
275 }
276
277 /* If there is not enough lookahead, but still some input left,
278 * read in the input
279 */
280 while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
281 int more = 2 * WSIZE - lookahead - strstart;
282
283 if (more > inputEnd - inputOff) {
284 more = inputEnd - inputOff;
285 }
286
287 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
288 adler.Update(inputBuf, inputOff, more);
289
290 inputOff += more;
291 totalIn += more;
292 lookahead += more;
293 }
294
295 if (lookahead >= MIN_MATCH) {
296 UpdateHash();
297 }
298 }
299
300 bool FindLongestMatch(int curMatch)
301 {
302 int chainLength = this.max_chain;
303 int niceLength = this.niceLength;
304 short[] prev = this.prev;
305 int scan = this.strstart;
306 int match;
307 int best_end = this.strstart + matchLen;
308 int best_len = Math.Max(matchLen, MIN_MATCH - 1);
309
310 int limit = Math.Max(strstart - MAX_DIST, 0);
311
312 int strend = strstart + MAX_MATCH - 1;
313 byte scan_end1 = window[best_end - 1];
314 byte scan_end = window[best_end];
315
316 /* Do not waste too much time if we already have a good match: */
317 if (best_len >= this.goodLength) {
318 chainLength >>= 2;
319 }
320
321 /* Do not look for matches beyond the end of the input. This is necessary
322 * to make deflate deterministic.
323 */
324 if (niceLength > lookahead) {
325 niceLength = lookahead;
326 }
327
328 if (DeflaterConstants.DEBUGGING && strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
329 throw new InvalidOperationException("need lookahead");
330 }
331
332 do {
333 if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
334 throw new InvalidOperationException("future match");
335 }
336 if (window[curMatch + best_len] != scan_end ||
337 window[curMatch + best_len - 1] != scan_end1 ||
338 window[curMatch] != window[scan] ||
339 window[curMatch + 1] != window[scan + 1]) {
340 continue;
341 }
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] && scan < strend) ;
357
358 if (scan > best_end) {
359 // if (DeflaterConstants.DEBUGGING && ins_h == 0)
360 // System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
361 matchStart = curMatch;
362 best_end = scan;
363 best_len = scan - strstart;
364
365 if (best_len >= niceLength) {
366 break;
367 }
368
369 scan_end1 = window[best_end - 1];
370 scan_end = window[best_end];
371 }
372 scan = strstart;
373 } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
374
375 matchLen = Math.Min(best_len, lookahead);
376 return matchLen >= MIN_MATCH;
377 }
378
379 public void SetDictionary(byte[] buffer, int offset, int length)
380 {
381 if (DeflaterConstants.DEBUGGING && strstart != 1) {
382 throw new InvalidOperationException("strstart not 1");
383 }
384 adler.Update(buffer, offset, length);
385 if (length < MIN_MATCH) {
386 return;
387 }
388 if (length > MAX_DIST) {
389 offset += length - MAX_DIST;
390 length = MAX_DIST;
391 }
392
393 System.Array.Copy(buffer, offset, window, strstart, length);
394
395 UpdateHash();
396 --length;
397 while (--length > 0) {
398 InsertString();
399 strstart++;
400 }
401 strstart += 2;
402 blockStart = strstart;
403 }
404
405 bool DeflateStored(bool flush, bool finish)
406 {
407 if (!flush && lookahead == 0) {
408 return false;
409 }
410
411 strstart += lookahead;
412 lookahead = 0;
413
414 int storedLen = strstart - blockStart;
415
416 if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
417 (blockStart < WSIZE && storedLen >= MAX_DIST) || /* Block may move out of window */
418 flush) {
419 bool lastBlock = finish;
420 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
421 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
422 lastBlock = false;
423 }
424
425 // if (DeflaterConstants.DEBUGGING) {
426 // //Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
427 // }
428
429 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
430 blockStart += storedLen;
431 return !lastBlock;
432 }
433 return true;
434 }
435
436 private bool DeflateFast(bool flush, bool finish)
437 {
438 if (lookahead < MIN_LOOKAHEAD && !flush) {
439 return false;
440 }
441
442 while (lookahead >= MIN_LOOKAHEAD || flush) {
443 if (lookahead == 0) {
444 /* We are flushing everything */
445 huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
446 blockStart = strstart;
447 return false;
448 }
449
450 if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
451 /* slide window, as findLongestMatch need this.
452 * This should only happen when flushing and the window
453 * is almost full.
454 */
455 SlideWindow();
456 }
457
458 int hashHead;
459 if (lookahead >= MIN_MATCH &&
460 (hashHead = InsertString()) != 0 &&
461 strategy != DeflateStrategy.HuffmanOnly &&
462 strstart - hashHead <= MAX_DIST &&
463 FindLongestMatch(hashHead)) {
464 /* longestMatch sets matchStart and matchLen */
465 // if (DeflaterConstants.DEBUGGING) {
466 // for (int i = 0 ; i < matchLen; i++) {
467 // if (window[strstart+i] != window[matchStart + i]) {
468 // throw new Exception();
469 // }
470 // }
471 // }
472
473 // -jr- Hak hak hak this stops problems with fast/low compression and index out of range
474 if (huffman.TallyDist(strstart - matchStart, matchLen)) {
475 bool lastBlock = finish && lookahead == 0;
476 huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
477 blockStart = strstart;
478 }
479
480 lookahead -= matchLen;
481 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
482 while (--matchLen > 0) {
483 ++strstart;
484 InsertString();
485 }
486 ++strstart;
487 } else {
488 strstart += matchLen;
489 if (lookahead >= MIN_MATCH - 1) {
490 UpdateHash();
491 }
492 }
493 matchLen = MIN_MATCH - 1;
494 continue;
495 } else {
496 /* No match found */
497 huffman.TallyLit(window[strstart] & 0xff);
498 ++strstart;
499 --lookahead;
500 }
501
502 if (huffman.IsFull()) {
503 bool lastBlock = finish && lookahead == 0;
504 huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
505 blockStart = strstart;
506 return !lastBlock;
507 }
508 }
509 return true;
510 }
511
512 bool DeflateSlow(bool flush, bool finish)
513 {
514 if (lookahead < MIN_LOOKAHEAD && !flush) {
515 return false;
516 }
517
518 while (lookahead >= MIN_LOOKAHEAD || flush) {
519 if (lookahead == 0) {
520 if (prevAvailable) {
521 huffman.TallyLit(window[strstart-1] & 0xff);
522 }
523 prevAvailable = false;
524
525 /* We are flushing everything */
526 if (DeflaterConstants.DEBUGGING && !flush) {
527 throw new Exception("Not flushing, but no lookahead");
528 }
529 huffman.FlushBlock(window, blockStart, strstart - blockStart,
530 finish);
531 blockStart = strstart;
532 return false;
533 }
534
535 if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) {
536 /* slide window, as findLongestMatch need this.
537 * This should only happen when flushing and the window
538 * is almost full.
539 */
540 SlideWindow();
541 }
542
543 int prevMatch = matchStart;
544 int prevLen = matchLen;
545 if (lookahead >= MIN_MATCH) {
546 int hashHead = InsertString();
547 if (strategy != DeflateStrategy.HuffmanOnly && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead)) {
548 /* longestMatch sets matchStart and matchLen */
549
550 /* Discard match if too small and too far away */
551 if (matchLen <= 5 && (strategy == DeflateStrategy.Filtered || (matchLen == MIN_MATCH && 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 Exception();
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 }
573 } while (--prevLen > 0);
574 strstart ++;
575 lookahead--;
576 prevAvailable = false;
577 matchLen = MIN_MATCH - 1;
578 } else {
579 if (prevAvailable) {
580 huffman.TallyLit(window[strstart-1] & 0xff);
581 }
582 prevAvailable = true;
583 strstart++;
584 lookahead--;
585 }
586
587 if (huffman.IsFull()) {
588 int len = strstart - blockStart;
589 if (prevAvailable) {
590 len--;
591 }
592 bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
593 huffman.FlushBlock(window, blockStart, len, lastBlock);
594 blockStart += len;
595 return !lastBlock;
596 }
597 }
598 return true;
599 }
600
601 public bool Deflate(bool flush, bool finish)
602 {
603 bool progress;
604 do {
605 FillWindow();
606 bool canFlush = flush && inputOff == inputEnd;
607 // if (DeflaterConstants.DEBUGGING) {
608 // //Console.WriteLine("window: ["+blockStart+","+strstart+","
609 // +lookahead+"], "+comprFunc+","+canFlush);
610 // }
611 switch (comprFunc) {
612 case DEFLATE_STORED:
613 progress = DeflateStored(canFlush, finish);
614 break;
615 case DEFLATE_FAST:
616 progress = DeflateFast(canFlush, finish);
617 break;
618 case DEFLATE_SLOW:
619 progress = DeflateSlow(canFlush, finish);
620 break;
621 default:
622 throw new InvalidOperationException("unknown comprFunc");
623 }
624 } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
625 return progress;
626 }
627
628 public void SetInput(byte[] buf, int off, int len)
629 {
630 if (inputOff < inputEnd) {
631 throw new InvalidOperationException("Old input was not completely processed");
632 }
633
634 int end = off + len;
635
636 /* We want to throw an ArrayIndexOutOfBoundsException early. The
637 * check is very tricky: it also handles integer wrap around.
638 */
639 if (0 > off || off > end || end > buf.Length) {
640 throw new ArgumentOutOfRangeException();
641 }
642
643 inputBuf = buf;
644 inputOff = off;
645 inputEnd = end;
646 }
647
648 public bool NeedsInput()
649 {
650 return inputEnd == inputOff;
651 }
652 }
653 }
Mirror of the official Mono project git repository