?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix some compiler warning that SUSE takes seriously.
[mono-project/dkf.git] / mono / benchmark / zipmark.cs
blob30e7037d6396979c362cc28b0e5e4587e5866439
1 // zipmark.cs
2 // (This file is the NZipLib sources with a crude benchmark class attached -
3 // 2002-15-05 Dan Lewis <dihlewis@yahoo.co.uk>)
4 // -------------------------------------------------------------------------
5 //
6 // NZipLib source:
7 // Copyright (C) 2001 Mike Krueger
8 //
9 // This file was translated from java, it was part of the GNU Classpath
10 // Copyright (C) 2001 Free Software Foundation, Inc.
11 //
12 // This program is free software; you can redistribute it and/or
13 // modify it under the terms of the GNU General Public License
14 // as published by the Free Software Foundation; either version 2
15 // of the License, or (at your option) any later version.
16 //
17 // This program is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // GNU General Public License for more details.
21 //
22 // You should have received a copy of the GNU General Public License
23 // along with this program; if not, write to the Free Software
24 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25 //
26 // As a special exception, if you link this library with other files to
27 // produce an executable, this library does not by itself cause the
28 // resulting executable to be covered by the GNU General Public License.
29 // This exception does not however invalidate any other reasons why the
30 // executable file might be covered by the GNU General Public License.
31
32 using System;
33 using System.IO;
34 using NZlib.Streams;
35 using NZlib.Checksums;
36 using NZlib.Compression;
37
38 class ZipMark {
39 static int Iterations = 1000;
40 static int BlockSize = 1024;
41
42 public static void Main (string [] args)
43 {
44 if (args.Length == 0 || args.Length > 3) {
45 Console.WriteLine ("Usage: zipmark FILE [ITERATIONS] [BLOCKSIZE]");
46 return;
47 }
48
49 string filename = args [0];
50 FileInfo file = new FileInfo (filename);
51 if (!file.Exists) {
52 Console.WriteLine ("Couldn't find file {0}", filename);
53 return;
54 }
55
56 FileStream fs = file.OpenRead ();
57
58 byte [] raw = new byte [file.Length];
59 int count = fs.Read (raw, 0, (int)file.Length);
60 fs.Close ();
61
62 if (count != file.Length) {
63 Console.WriteLine ("Couldn't read file {0}", filename);
64 return;
65 }
66
67 Deflater def = new Deflater (Deflater.BEST_COMPRESSION, false);
68 Inflater inf = new Inflater (false);
69
70 // 1. Count deflated size
71
72 int cooked_size = Deflate (def, raw, null);
73 byte [] cooked = new byte [cooked_size];
74
75 // 2. Deflate & Inflate
76
77 if (args.Length > 1)
78 Iterations = Int32.Parse (args [1]);
79 if (args.Length > 2)
80 BlockSize = Int32.Parse (args [2]);
81
82 for (int i = 0; i < Iterations; ++ i) {
83 Deflate (def, raw, cooked);
84 Inflate (inf, cooked, raw);
85 }
86
87 return;
88 }
89
90 static int Deflate (Deflater def, byte [] src, byte [] dest)
91 {
92 bool count;
93 int offset, length, remain;
94
95 if (dest == null) {
96 dest = new byte [BlockSize];
97 count = true;
98 } else
99 count = false;
100
101 def.Reset ();
102 def.SetInput (src);
103
104 offset = 0;
105 while (!def.IsFinished) {
106 if (def.IsNeedingInput)
107 def.Finish ();
108
109 remain = Math.Min (dest.Length - offset, BlockSize);
110 if (remain == 0)
111 break;
112
113 length = def.Deflate (dest, offset, remain);
114 if (!count)
115 offset += length;
116 }
117
118 return def.TotalOut;
119 }
120
121 static int Inflate (Inflater inf, byte [] src, byte [] dest)
122 {
123 int offset, length, remain;
124
125 inf.Reset ();
126 inf.SetInput (src);
127
128 offset = 0;
129 while (!inf.IsNeedingInput) {
130 remain = Math.Min (dest.Length - offset, BlockSize);
131 if (remain == 0)
132 break;
133
134 length = inf.Inflate (dest, offset, remain);
135 offset += length;
136 }
137
138 return inf.TotalOut;
139 }
140 }
141
142 // ---------------------- NZipLib sources from here on --------------------------
143
144 namespace NZlib.Compression {
145
146 /// <summary>
147 /// This is the Deflater class. The deflater class compresses input
148 /// with the deflate algorithm described in RFC 1951. It has several
149 /// compression levels and three different strategies described below.
150 ///
151 /// This class is <i>not</i> thread safe. This is inherent in the API, due
152 /// to the split of deflate and setInput.
153 ///
154 /// author of the original java version : Jochen Hoenicke
155 /// </summary>
156 public class Deflater
157 {
158 /// <summary>
159 /// The best and slowest compression level. This tries to find very
160 /// long and distant string repetitions.
161 /// </summary>
162 public static int BEST_COMPRESSION = 9;
163
164 /// <summary>
165 /// The worst but fastest compression level.
166 /// </summary>
167 public static int BEST_SPEED = 1;
168
169 /// <summary>
170 /// The default compression level.
171 /// </summary>
172 public static int DEFAULT_COMPRESSION = -1;
173
174 /// <summary>
175 /// This level won't compress at all but output uncompressed blocks.
176 /// </summary>
177 public static int NO_COMPRESSION = 0;
178
179 /// <summary>
180 /// The default strategy.
181 /// </summary>
182 public static int DEFAULT_STRATEGY = 0;
183
184
185 /// <summary>
186 /// This strategy will only allow longer string repetitions. It is
187 /// useful for random data with a small character set.
188 /// </summary>
189 public static int FILTERED = 1;
190
191 /// <summary>
192 /// This strategy will not look for string repetitions at all. It
193 /// only encodes with Huffman trees (which means, that more common
194 /// characters get a smaller encoding.
195 /// </summary>
196 public static int HUFFMAN_ONLY = 2;
197
198 /// <summary>
199 /// The compression method. This is the only method supported so far.
200 /// There is no need to use this constant at all.
201 /// </summary>
202 public static int DEFLATED = 8;
203
204 /*
205 * The Deflater can do the following state transitions:
206 *
207 * (1) -> INIT_STATE ----> INIT_FINISHING_STATE ---.
208 * / | (2) (5) |
209 * / v (5) |
210 * (3)| SETDICT_STATE ---> SETDICT_FINISHING_STATE |(3)
211 * \ | (3) | ,-------'
212 * | | | (3) /
213 * v v (5) v v
214 * (1) -> BUSY_STATE ----> FINISHING_STATE
215 * | (6)
216 * v
217 * FINISHED_STATE
218 * \_____________________________________/
219 * | (7)
220 * v
221 * CLOSED_STATE
222 *
223 * (1) If we should produce a header we start in INIT_STATE, otherwise
224 * we start in BUSY_STATE.
225 * (2) A dictionary may be set only when we are in INIT_STATE, then
226 * we change the state as indicated.
227 * (3) Whether a dictionary is set or not, on the first call of deflate
228 * we change to BUSY_STATE.
229 * (4) -- intentionally left blank -- :)
230 * (5) FINISHING_STATE is entered, when flush() is called to indicate that
231 * there is no more INPUT. There are also states indicating, that
232 * the header wasn't written yet.
233 * (6) FINISHED_STATE is entered, when everything has been flushed to the
234 * internal pending output buffer.
235 * (7) At any time (7)
236 *
237 */
238
239 private static int IS_SETDICT = 0x01;
240 private static int IS_FLUSHING = 0x04;
241 private static int IS_FINISHING = 0x08;
242
243 private static int INIT_STATE = 0x00;
244 private static int SETDICT_STATE = 0x01;
245 // private static int INIT_FINISHING_STATE = 0x08;
246 // private static int SETDICT_FINISHING_STATE = 0x09;
247 private static int BUSY_STATE = 0x10;
248 private static int FLUSHING_STATE = 0x14;
249 private static int FINISHING_STATE = 0x1c;
250 private static int FINISHED_STATE = 0x1e;
251 private static int CLOSED_STATE = 0x7f;
252
253 /// <summary>
254 /// Compression level.
255 /// </summary>
256 private int level;
257
258 /// <summary>
259 /// should we include a header.
260 /// </summary>
261 private bool noHeader;
262
263 // /// <summary>
264 // /// Compression strategy.
265 // /// </summary>
266 // private int strategy;
267
268 /// <summary>
269 /// The current state.
270 /// </summary>
271 private int state;
272
273 /// <summary>
274 /// The total bytes of output written.
275 /// </summary>
276 private int totalOut;
277
278 /// <summary>
279 /// The pending output.
280 /// </summary>
281 private DeflaterPending pending;
282
283 /// <summary>
284 /// The deflater engine.
285 /// </summary>
286 private DeflaterEngine engine;
287
288 /// <summary>
289 /// Creates a new deflater with default compression level.
290 /// </summary>
291 public Deflater() : this(DEFAULT_COMPRESSION, false)
292 {
293
294 }
295
296 /// <summary>
297 /// Creates a new deflater with given compression level.
298 /// </summary>
299 /// <param name="lvl">
300 /// the compression level, a value between NO_COMPRESSION
301 /// and BEST_COMPRESSION, or DEFAULT_COMPRESSION.
302 /// </param>
303 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
304 public Deflater(int lvl) : this(lvl, false)
305 {
306
307 }
308
309 /// <summary>
310 /// Creates a new deflater with given compression level.
311 /// </summary>
312 /// <param name="lvl">
313 /// the compression level, a value between NO_COMPRESSION
314 /// and BEST_COMPRESSION.
315 /// </param>
316 /// <param name="nowrap">
317 /// true, if we should suppress the deflate header at the
318 /// beginning and the adler checksum at the end of the output. This is
319 /// useful for the GZIP format.
320 /// </param>
321 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
322 public Deflater(int lvl, bool nowrap)
323 {
324 if (lvl == DEFAULT_COMPRESSION) {
325 lvl = 6;
326 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
327 throw new ArgumentOutOfRangeException("lvl");
328 }
329
330 pending = new DeflaterPending();
331 engine = new DeflaterEngine(pending);
332 this.noHeader = nowrap;
333 SetStrategy(DEFAULT_STRATEGY);
334 SetLevel(lvl);
335 Reset();
336 }
337
338
339 /// <summary>
340 /// Resets the deflater. The deflater acts afterwards as if it was
341 /// just created with the same compression level and strategy as it
342 /// had before.
343 /// </summary>
344 public void Reset()
345 {
346 state = (noHeader ? BUSY_STATE : INIT_STATE);
347 totalOut = 0;
348 pending.Reset();
349 engine.Reset();
350 }
351
352 /// <summary>
353 /// Gets the current adler checksum of the data that was processed so far.
354 /// </summary>
355 public int Adler {
356 get {
357 return engine.Adler;
358 }
359 }
360
361 /// <summary>
362 /// Gets the number of input bytes processed so far.
363 /// </summary>
364 public int TotalIn {
365 get {
366 return engine.TotalIn;
367 }
368 }
369
370 /// <summary>
371 /// Gets the number of output bytes so far.
372 /// </summary>
373 public int TotalOut {
374 get {
375 return totalOut;
376 }
377 }
378
379 /// <summary>
380 /// Flushes the current input block. Further calls to deflate() will
381 /// produce enough output to inflate everything in the current input
382 /// block. This is not part of Sun's JDK so I have made it package
383 /// private. It is used by DeflaterOutputStream to implement
384 /// flush().
385 /// </summary>
386 public void Flush()
387 {
388 state |= IS_FLUSHING;
389 }
390
391 /// <summary>
392 /// Finishes the deflater with the current input block. It is an error
393 /// to give more input after this method was called. This method must
394 /// be called to force all bytes to be flushed.
395 /// </summary>
396 public void Finish()
397 {
398 state |= IS_FLUSHING | IS_FINISHING;
399 }
400
401 /// <summary>
402 /// Returns true if the stream was finished and no more output bytes
403 /// are available.
404 /// </summary>
405 public bool IsFinished {
406 get {
407 return state == FINISHED_STATE && pending.IsFlushed;
408 }
409 }
410
411 /// <summary>
412 /// Returns true, if the input buffer is empty.
413 /// You should then call setInput().
414 /// NOTE: This method can also return true when the stream
415 /// was finished.
416 /// </summary>
417 public bool IsNeedingInput {
418 get {
419 return engine.NeedsInput();
420 }
421 }
422
423 /// <summary>
424 /// Sets the data which should be compressed next. This should be only
425 /// called when needsInput indicates that more input is needed.
426 /// If you call setInput when needsInput() returns false, the
427 /// previous input that is still pending will be thrown away.
428 /// The given byte array should not be changed, before needsInput() returns
429 /// true again.
430 /// This call is equivalent to <code>setInput(input, 0, input.length)</code>.
431 /// </summary>
432 /// <param name="input">
433 /// the buffer containing the input data.
434 /// </param>
435 /// <exception cref="System.InvalidOperationException">
436 /// if the buffer was finished() or ended().
437 /// </exception>
438 public void SetInput(byte[] input)
439 {
440 SetInput(input, 0, input.Length);
441 }
442
443 /// <summary>
444 /// Sets the data which should be compressed next. This should be
445 /// only called when needsInput indicates that more input is needed.
446 /// The given byte array should not be changed, before needsInput() returns
447 /// true again.
448 /// </summary>
449 /// <param name="input">
450 /// the buffer containing the input data.
451 /// </param>
452 /// <param name="off">
453 /// the start of the data.
454 /// </param>
455 /// <param name="len">
456 /// the length of the data.
457 /// </param>
458 /// <exception cref="System.InvalidOperationException">
459 /// if the buffer was finished() or ended() or if previous input is still pending.
460 /// </exception>
461 public void SetInput(byte[] input, int off, int len)
462 {
463 if ((state & IS_FINISHING) != 0) {
464 throw new InvalidOperationException("finish()/end() already called");
465 }
466 engine.SetInput(input, off, len);
467 }
468
469 /// <summary>
470 /// Sets the compression level. There is no guarantee of the exact
471 /// position of the change, but if you call this when needsInput is
472 /// true the change of compression level will occur somewhere near
473 /// before the end of the so far given input.
474 /// </summary>
475 /// <param name="lvl">
476 /// the new compression level.
477 /// </param>
478 public void SetLevel(int lvl)
479 {
480 if (lvl == DEFAULT_COMPRESSION) {
481 lvl = 6;
482 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
483 throw new ArgumentOutOfRangeException("lvl");
484 }
485
486
487 if (level != lvl) {
488 level = lvl;
489 engine.SetLevel(lvl);
490 }
491 }
492
493 /// <summary>
494 /// Sets the compression strategy. Strategy is one of
495 /// DEFAULT_STRATEGY, HUFFMAN_ONLY and FILTERED. For the exact
496 /// position where the strategy is changed, the same as for
497 /// setLevel() applies.
498 /// </summary>
499 /// <param name="stgy">
500 /// the new compression strategy.
501 /// </param>
502 public void SetStrategy(int stgy)
503 {
504 if (stgy != DEFAULT_STRATEGY && stgy != FILTERED && stgy != HUFFMAN_ONLY) {
505 throw new Exception();
506 }
507 engine.Strategy = stgy;
508 }
509
510 /// <summary>
511 /// Deflates the current input block to the given array. It returns
512 /// the number of bytes compressed, or 0 if either
513 /// needsInput() or finished() returns true or length is zero.
514 /// </summary>
515 /// <param name="output">
516 /// the buffer where to write the compressed data.
517 /// </param>
518 public int Deflate(byte[] output)
519 {
520 return Deflate(output, 0, output.Length);
521 }
522
523 /// <summary>
524 /// Deflates the current input block to the given array. It returns
525 /// the number of bytes compressed, or 0 if either
526 /// needsInput() or finished() returns true or length is zero.
527 /// </summary>
528 /// <param name="output">
529 /// the buffer where to write the compressed data.
530 /// </param>
531 /// <param name="offset">
532 /// the offset into the output array.
533 /// </param>
534 /// <param name="length">
535 /// the maximum number of bytes that may be written.
536 /// </param>
537 /// <exception cref="System.InvalidOperationException">
538 /// if end() was called.
539 /// </exception>
540 /// <exception cref="System.ArgumentOutOfRangeException">
541 /// if offset and/or length don't match the array length.
542 /// </exception>
543 public int Deflate(byte[] output, int offset, int length)
544 {
545 int origLength = length;
546
547 if (state == CLOSED_STATE) {
548 throw new InvalidOperationException("Deflater closed");
549 }
550
551 if (state < BUSY_STATE) {
552 /* output header */
553 int header = (DEFLATED +
554 ((DeflaterConstants.MAX_WBITS - 8) << 4)) << 8;
555 int level_flags = (level - 1) >> 1;
556 if (level_flags < 0 || level_flags > 3) {
557 level_flags = 3;
558 }
559 header |= level_flags << 6;
560 if ((state & IS_SETDICT) != 0) {
561 /* Dictionary was set */
562 header |= DeflaterConstants.PRESET_DICT;
563 }
564 header += 31 - (header % 31);
565
566
567 pending.WriteShortMSB(header);
568 if ((state & IS_SETDICT) != 0) {
569 int chksum = engine.Adler;
570 engine.ResetAdler();
571 pending.WriteShortMSB(chksum >> 16);
572 pending.WriteShortMSB(chksum & 0xffff);
573 }
574
575 state = BUSY_STATE | (state & (IS_FLUSHING | IS_FINISHING));
576 }
577
578 for (;;) {
579 int count = pending.Flush(output, offset, length);
580 offset += count;
581 totalOut += count;
582 length -= count;
583
584 if (length == 0 || state == FINISHED_STATE) {
585 break;
586 }
587
588 if (!engine.Deflate((state & IS_FLUSHING) != 0, (state & IS_FINISHING) != 0)) {
589 if (state == BUSY_STATE) {
590 /* We need more input now */
591 return origLength - length;
592 } else if (state == FLUSHING_STATE) {
593 if (level != NO_COMPRESSION) {
594 /* We have to supply some lookahead. 8 bit lookahead
595 * are needed by the zlib inflater, and we must fill
596 * the next byte, so that all bits are flushed.
597 */
598 int neededbits = 8 + ((-pending.BitCount) & 7);
599 while (neededbits > 0) {
600 /* write a static tree block consisting solely of
601 * an EOF:
602 */
603 pending.WriteBits(2, 10);
604 neededbits -= 10;
605 }
606 }
607 state = BUSY_STATE;
608 } else if (state == FINISHING_STATE) {
609 pending.AlignToByte();
610 /* We have completed the stream */
611 if (!noHeader) {
612 int adler = engine.Adler;
613 pending.WriteShortMSB(adler >> 16);
614 pending.WriteShortMSB(adler & 0xffff);
615 }
616 state = FINISHED_STATE;
617 }
618 }
619 }
620 return origLength - length;
621 }
622
623 /// <summary>
624 /// Sets the dictionary which should be used in the deflate process.
625 /// This call is equivalent to <code>setDictionary(dict, 0, dict.Length)</code>.
626 /// </summary>
627 /// <param name="dict">
628 /// the dictionary.
629 /// </param>
630 /// <exception cref="System.InvalidOperationException">
631 /// if setInput () or deflate () were already called or another dictionary was already set.
632 /// </exception>
633 public void SetDictionary(byte[] dict)
634 {
635 SetDictionary(dict, 0, dict.Length);
636 }
637
638 /// <summary>
639 /// Sets the dictionary which should be used in the deflate process.
640 /// The dictionary should be a byte array containing strings that are
641 /// likely to occur in the data which should be compressed. The
642 /// dictionary is not stored in the compressed output, only a
643 /// checksum. To decompress the output you need to supply the same
644 /// dictionary again.
645 /// </summary>
646 /// <param name="dict">
647 /// the dictionary.
648 /// </param>
649 /// <param name="offset">
650 /// an offset into the dictionary.
651 /// </param>
652 /// <param name="length">
653 /// the length of the dictionary.
654 /// </param>
655 /// <exception cref="System.InvalidOperationException">
656 /// if setInput () or deflate () were already called or another dictionary was already set.
657 /// </exception>
658 public void SetDictionary(byte[] dict, int offset, int length)
659 {
660 if (state != INIT_STATE) {
661 throw new InvalidOperationException();
662 }
663
664 state = SETDICT_STATE;
665 engine.SetDictionary(dict, offset, length);
666 }
667 }
668 }
669
670 namespace NZlib.Compression {
671
672 /// <summary>
673 /// This class contains constants used for the deflater.
674 /// </summary>
675 public class DeflaterConstants
676 {
677 public const bool DEBUGGING = false;
678
679 public const int STORED_BLOCK = 0;
680 public const int STATIC_TREES = 1;
681 public const int DYN_TREES = 2;
682 public const int PRESET_DICT = 0x20;
683
684 public const int DEFAULT_MEM_LEVEL = 8;
685
686 public const int MAX_MATCH = 258;
687 public const int MIN_MATCH = 3;
688
689 public const int MAX_WBITS = 15;
690 public const int WSIZE = 1 << MAX_WBITS;
691 public const int WMASK = WSIZE - 1;
692
693 public const int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
694 public const int HASH_SIZE = 1 << HASH_BITS;
695 public const int HASH_MASK = HASH_SIZE - 1;
696 public const int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
697
698 public const int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
699 public const int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
700
701 public const int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
702 public static int MAX_BLOCK_SIZE = Math.Min(65535, PENDING_BUF_SIZE-5);
703
704 public const int DEFLATE_STORED = 0;
705 public const int DEFLATE_FAST = 1;
706 public const int DEFLATE_SLOW = 2;
707
708 public static int[] GOOD_LENGTH = { 0, 4, 4, 4, 4, 8, 8, 8, 32, 32 };
709 public static int[] MAX_LAZY = { 0, 4, 5, 6, 4,16, 16, 32, 128, 258 };
710 public static int[] NICE_LENGTH = { 0, 8,16,32,16,32,128,128, 258, 258 };
711 public static int[] MAX_CHAIN = { 0, 4, 8,32,16,32,128,256,1024,4096 };
712 public static int[] COMPR_FUNC = { 0, 1, 1, 1, 1, 2, 2, 2, 2, 2 };
713 }
714 }
715
716 namespace NZlib.Compression {
717
718 public class DeflaterEngine : DeflaterConstants
719 {
720 private static int TOO_FAR = 4096;
721
722 private int ins_h;
723 // private byte[] buffer;
724 private short[] head;
725 private short[] prev;
726
727 private int matchStart, matchLen;
728 private bool prevAvailable;
729 private int blockStart;
730 private int strstart, lookahead;
731 private byte[] window;
732
733 private int strategy, max_chain, max_lazy, niceLength, goodLength;
734
735 /// <summary>
736 /// The current compression function.
737 /// </summary>
738 private int comprFunc;
739
740 /// <summary>
741 /// The input data for compression.
742 /// </summary>
743 private byte[] inputBuf;
744
745 /// <summary>
746 /// The total bytes of input read.
747 /// </summary>
748 private int totalIn;
749
750 /// <summary>
751 /// The offset into inputBuf, where input data starts.
752 /// </summary>
753 private int inputOff;
754
755 /// <summary>
756 /// The end offset of the input data.
757 /// </summary>
758 private int inputEnd;
759
760 private DeflaterPending pending;
761 private DeflaterHuffman huffman;
762
763 /// <summary>
764 /// The adler checksum
765 /// </summary>
766 private Adler32 adler;
767
768 public DeflaterEngine(DeflaterPending pending)
769 {
770 this.pending = pending;
771 huffman = new DeflaterHuffman(pending);
772 adler = new Adler32();
773
774 window = new byte[2*WSIZE];
775 head = new short[HASH_SIZE];
776 prev = new short[WSIZE];
777
778 /* We start at index 1, to avoid a implementation deficiency, that
779 * we cannot build a repeat pattern at index 0.
780 */
781 blockStart = strstart = 1;
782 }
783
784 public void Reset()
785 {
786 huffman.Reset();
787 adler.Reset();
788 blockStart = strstart = 1;
789 lookahead = 0;
790 totalIn = 0;
791 prevAvailable = false;
792 matchLen = MIN_MATCH - 1;
793
794 for (int i = 0; i < HASH_SIZE; i++) {
795 head[i] = 0;
796 }
797
798 for (int i = 0; i < WSIZE; i++) {
799 prev[i] = 0;
800 }
801 }
802
803 public void ResetAdler()
804 {
805 adler.Reset();
806 }
807
808 public int Adler {
809 get {
810 return (int)adler.Value;
811 }
812 }
813
814 public int TotalIn {
815 get {
816 return totalIn;
817 }
818 }
819
820 public int Strategy {
821 get {
822 return strategy;
823 }
824 set {
825 strategy = value;
826 }
827 }
828
829 public void SetLevel(int lvl)
830 {
831 goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
832 max_lazy = DeflaterConstants.MAX_LAZY[lvl];
833 niceLength = DeflaterConstants.NICE_LENGTH[lvl];
834 max_chain = DeflaterConstants.MAX_CHAIN[lvl];
835
836 if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
837 // if (DeflaterConstants.DEBUGGING) {
838 // Console.WriteLine("Change from "+comprFunc +" to "
839 // + DeflaterConstants.COMPR_FUNC[lvl]);
840 // }
841 switch (comprFunc) {
842 case DEFLATE_STORED:
843 if (strstart > blockStart) {
844 huffman.FlushStoredBlock(window, blockStart,
845 strstart - blockStart, false);
846 blockStart = strstart;
847 }
848 UpdateHash();
849 break;
850 case DEFLATE_FAST:
851 if (strstart > blockStart) {
852 huffman.FlushBlock(window, blockStart, strstart - blockStart,
853 false);
854 blockStart = strstart;
855 }
856 break;
857 case DEFLATE_SLOW:
858 if (prevAvailable) {
859 huffman.TallyLit(window[strstart-1] & 0xff);
860 }
861 if (strstart > blockStart) {
862 huffman.FlushBlock(window, blockStart, strstart - blockStart,
863 false);
864 blockStart = strstart;
865 }
866 prevAvailable = false;
867 matchLen = MIN_MATCH - 1;
868 break;
869 }
870 comprFunc = COMPR_FUNC[lvl];
871 }
872 }
873
874 private void UpdateHash()
875 {
876 // if (DEBUGGING) {
877 // Console.WriteLine("updateHash: "+strstart);
878 // }
879 ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
880 }
881
882 private int InsertString()
883 {
884 short match;
885 int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
886
887 // if (DEBUGGING) {
888 // if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
889 // (window[strstart + 1] << HASH_SHIFT) ^
890 // (window[strstart + 2])) & HASH_MASK)) {
891 // throw new Exception("hash inconsistent: "+hash+"/"
892 // +window[strstart]+","
893 // +window[strstart+1]+","
894 // +window[strstart+2]+","+HASH_SHIFT);
895 // }
896 // }
897
898 prev[strstart & WMASK] = match = head[hash];
899 head[hash] = (short)strstart;
900 ins_h = hash;
901 return match & 0xffff;
902 }
903
904 public void FillWindow()
905 {
906 while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
907 int more = 2*WSIZE - lookahead - strstart;
908
909 /* If the window is almost full and there is insufficient lookahead,
910 * move the upper half to the lower one to make room in the upper half.
911 */
912 if (strstart >= WSIZE + MAX_DIST) {
913 System.Array.Copy(window, WSIZE, window, 0, WSIZE);
914 matchStart -= WSIZE;
915 strstart -= WSIZE;
916 blockStart -= WSIZE;
917
918 /* Slide the hash table (could be avoided with 32 bit values
919 * at the expense of memory usage).
920 */
921 for (int i = 0; i < HASH_SIZE; i++) {
922 int m = head[i];
923 head[i] = m >= WSIZE ? (short) (m - WSIZE) : (short)0;
924 }
925 more += WSIZE;
926 }
927
928 if (more > inputEnd - inputOff) {
929 more = inputEnd - inputOff;
930 }
931
932 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
933 adler.Update(inputBuf, inputOff, more);
934 inputOff += more;
935 totalIn += more;
936 lookahead += more;
937
938 if (lookahead >= MIN_MATCH) {
939 UpdateHash();
940 }
941 }
942 }
943
944 private bool FindLongestMatch(int curMatch)
945 {
946 int chainLength = this.max_chain;
947 int niceLength = this.niceLength;
948 short[] prev = this.prev;
949 int scan = this.strstart;
950 int match;
951 int best_end = this.strstart + matchLen;
952 int best_len = Math.Max(matchLen, MIN_MATCH - 1);
953
954 int limit = Math.Max(strstart - MAX_DIST, 0);
955
956 int strend = strstart + MAX_MATCH - 1;
957 byte scan_end1 = window[best_end - 1];
958 byte scan_end = window[best_end];
959
960 /* Do not waste too much time if we already have a good match: */
961 if (best_len >= this.goodLength) {
962 chainLength >>= 2;
963 }
964
965 /* Do not look for matches beyond the end of the input. This is necessary
966 * to make deflate deterministic.
967 */
968 if (niceLength > lookahead) {
969 niceLength = lookahead;
970 }
971
972 if (DeflaterConstants.DEBUGGING && strstart > 2*WSIZE - MIN_LOOKAHEAD) {
973 throw new InvalidOperationException("need lookahead");
974 }
975
976 do {
977 if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
978 throw new InvalidOperationException("future match");
979 }
980 if (window[curMatch + best_len] != scan_end ||
981 window[curMatch + best_len - 1] != scan_end1 ||
982 window[curMatch] != window[scan] ||
983 window[curMatch+1] != window[scan + 1]) {
984 continue;
985 }
986
987 match = curMatch + 2;
988 scan += 2;
989
990 /* We check for insufficient lookahead only every 8th comparison;
991 * the 256th check will be made at strstart+258.
992 */
993 while (window[++scan] == window[++match] &&
994 window[++scan] == window[++match] &&
995 window[++scan] == window[++match] &&
996 window[++scan] == window[++match] &&
997 window[++scan] == window[++match] &&
998 window[++scan] == window[++match] &&
999 window[++scan] == window[++match] &&
1000 window[++scan] == window[++match] && scan < strend) ;
1001
1002 if (scan > best_end) {
1003 // if (DeflaterConstants.DEBUGGING && ins_h == 0)
1004 // System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
1005 matchStart = curMatch;
1006 best_end = scan;
1007 best_len = scan - strstart;
1008 if (best_len >= niceLength) {
1009 break;
1010 }
1011
1012 scan_end1 = window[best_end-1];
1013 scan_end = window[best_end];
1014 }
1015 scan = strstart;
1016 } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
1017
1018 matchLen = Math.Min(best_len, lookahead);
1019 return matchLen >= MIN_MATCH;
1020 }
1021
1022 public void SetDictionary(byte[] buffer, int offset, int length)
1023 {
1024 if (DeflaterConstants.DEBUGGING && strstart != 1) {
1025 throw new InvalidOperationException("strstart not 1");
1026 }
1027 adler.Update(buffer, offset, length);
1028 if (length < MIN_MATCH) {
1029 return;
1030 }
1031 if (length > MAX_DIST) {
1032 offset += length - MAX_DIST;
1033 length = MAX_DIST;
1034 }
1035
1036 System.Array.Copy(buffer, offset, window, strstart, length);
1037
1038 UpdateHash();
1039 --length;
1040 while (--length > 0) {
1041 InsertString();
1042 strstart++;
1043 }
1044 strstart += 2;
1045 blockStart = strstart;
1046 }
1047
1048 private bool DeflateStored(bool flush, bool finish)
1049 {
1050 if (!flush && lookahead == 0) {
1051 return false;
1052 }
1053
1054 strstart += lookahead;
1055 lookahead = 0;
1056
1057 int storedLen = strstart - blockStart;
1058
1059 if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
1060 (blockStart < WSIZE && storedLen >= MAX_DIST) || /* Block may move out of window */
1061 flush) {
1062 bool lastBlock = finish;
1063 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
1064 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
1065 lastBlock = false;
1066 }
1067
1068 // if (DeflaterConstants.DEBUGGING) {
1069 // Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
1070 // }
1071
1072 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
1073 blockStart += storedLen;
1074 return !lastBlock;
1075 }
1076 return true;
1077 }
1078
1079 private bool DeflateFast(bool flush, bool finish)
1080 {
1081 if (lookahead < MIN_LOOKAHEAD && !flush) {
1082 return false;
1083 }
1084
1085 while (lookahead >= MIN_LOOKAHEAD || flush) {
1086 if (lookahead == 0) {
1087 /* We are flushing everything */
1088 huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
1089 blockStart = strstart;
1090 return false;
1091 }
1092
1093 int hashHead;
1094 if (lookahead >= MIN_MATCH &&
1095 (hashHead = InsertString()) != 0 &&
1096 strategy != Deflater.HUFFMAN_ONLY &&
1097 strstart - hashHead <= MAX_DIST &&
1098 FindLongestMatch(hashHead)) {
1099 /* longestMatch sets matchStart and matchLen */
1100 // if (DeflaterConstants.DEBUGGING) {
1101 // for (int i = 0 ; i < matchLen; i++) {
1102 // if (window[strstart+i] != window[matchStart + i]) {
1103 // throw new Exception();
1104 // }
1105 // }
1106 // }
1107
1108 huffman.TallyDist(strstart - matchStart, matchLen);
1109
1110 lookahead -= matchLen;
1111 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
1112 while (--matchLen > 0) {
1113 ++strstart;
1114 InsertString();
1115 }
1116 ++strstart;
1117 } else {
1118 strstart += matchLen;
1119 if (lookahead >= MIN_MATCH - 1) {
1120 UpdateHash();
1121 }
1122 }
1123 matchLen = MIN_MATCH - 1;
1124 continue;
1125 } else {
1126 /* No match found */
1127 huffman.TallyLit(window[strstart] & 0xff);
1128 ++strstart;
1129 --lookahead;
1130 }
1131
1132 if (huffman.IsFull()) {
1133 bool lastBlock = finish && lookahead == 0;
1134 huffman.FlushBlock(window, blockStart, strstart - blockStart,
1135 lastBlock);
1136 blockStart = strstart;
1137 return !lastBlock;
1138 }
1139 }
1140 return true;
1141 }
1142
1143 private bool DeflateSlow(bool flush, bool finish)
1144 {
1145 if (lookahead < MIN_LOOKAHEAD && !flush) {
1146 return false;
1147 }
1148
1149 while (lookahead >= MIN_LOOKAHEAD || flush) {
1150 if (lookahead == 0) {
1151 if (prevAvailable) {
1152 huffman.TallyLit(window[strstart-1] & 0xff);
1153 }
1154 prevAvailable = false;
1155
1156 /* We are flushing everything */
1157 if (DeflaterConstants.DEBUGGING && !flush) {
1158 throw new Exception("Not flushing, but no lookahead");
1159 }
1160 huffman.FlushBlock(window, blockStart, strstart - blockStart,
1161 finish);
1162 blockStart = strstart;
1163 return false;
1164 }
1165
1166 int prevMatch = matchStart;
1167 int prevLen = matchLen;
1168 if (lookahead >= MIN_MATCH) {
1169 int hashHead = InsertString();
1170 if (strategy != Deflater.HUFFMAN_ONLY && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead))
1171 {
1172 /* longestMatch sets matchStart and matchLen */
1173
1174 /* Discard match if too small and too far away */
1175 if (matchLen <= 5 && (strategy == Deflater.FILTERED || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
1176 matchLen = MIN_MATCH - 1;
1177 }
1178 }
1179 }
1180
1181 /* previous match was better */
1182 if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
1183 // if (DeflaterConstants.DEBUGGING) {
1184 // for (int i = 0 ; i < matchLen; i++) {
1185 // if (window[strstart-1+i] != window[prevMatch + i])
1186 // throw new Exception();
1187 // }
1188 // }
1189 huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
1190 prevLen -= 2;
1191 do {
1192 strstart++;
1193 lookahead--;
1194 if (lookahead >= MIN_MATCH) {
1195 InsertString();
1196 }
1197 } while (--prevLen > 0);
1198 strstart ++;
1199 lookahead--;
1200 prevAvailable = false;
1201 matchLen = MIN_MATCH - 1;
1202 } else {
1203 if (prevAvailable) {
1204 huffman.TallyLit(window[strstart-1] & 0xff);
1205 }
1206 prevAvailable = true;
1207 strstart++;
1208 lookahead--;
1209 }
1210
1211 if (huffman.IsFull()) {
1212 int len = strstart - blockStart;
1213 if (prevAvailable) {
1214 len--;
1215 }
1216 bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
1217 huffman.FlushBlock(window, blockStart, len, lastBlock);
1218 blockStart += len;
1219 return !lastBlock;
1220 }
1221 }
1222 return true;
1223 }
1224
1225 public bool Deflate(bool flush, bool finish)
1226 {
1227 bool progress;
1228 do {
1229 FillWindow();
1230 bool canFlush = flush && inputOff == inputEnd;
1231 // if (DeflaterConstants.DEBUGGING) {
1232 // Console.WriteLine("window: ["+blockStart+","+strstart+","
1233 // +lookahead+"], "+comprFunc+","+canFlush);
1234 // }
1235 switch (comprFunc) {
1236 case DEFLATE_STORED:
1237 progress = DeflateStored(canFlush, finish);
1238 break;
1239 case DEFLATE_FAST:
1240 progress = DeflateFast(canFlush, finish);
1241 break;
1242 case DEFLATE_SLOW:
1243 progress = DeflateSlow(canFlush, finish);
1244 break;
1245 default:
1246 throw new InvalidOperationException("unknown comprFunc");
1247 }
1248 } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
1249 return progress;
1250 }
1251
1252 public void SetInput(byte[] buf, int off, int len)
1253 {
1254 if (inputOff < inputEnd) {
1255 throw new InvalidOperationException("Old input was not completely processed");
1256 }
1257
1258 int end = off + len;
1259
1260 /* We want to throw an ArrayIndexOutOfBoundsException early. The
1261 * check is very tricky: it also handles integer wrap around.
1262 */
1263 if (0 > off || off > end || end > buf.Length) {
1264 throw new ArgumentOutOfRangeException();
1265 }
1266
1267 inputBuf = buf;
1268 inputOff = off;
1269 inputEnd = end;
1270 }
1271
1272 public bool NeedsInput()
1273 {
1274 return inputEnd == inputOff;
1275 }
1276 }
1277 }
1278
1279 namespace NZlib.Compression {
1280
1281 /// <summary>
1282 /// This is the DeflaterHuffman class.
1283 ///
1284 /// This class is <i>not</i> thread safe. This is inherent in the API, due
1285 /// to the split of deflate and setInput.
1286 ///
1287 /// author of the original java version : Jochen Hoenicke
1288 /// </summary>
1289 public class DeflaterHuffman
1290 {
1291 private static int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
1292 private static int LITERAL_NUM = 286;
1293 private static int DIST_NUM = 30;
1294 private static int BITLEN_NUM = 19;
1295 private static int REP_3_6 = 16;
1296 private static int REP_3_10 = 17;
1297 private static int REP_11_138 = 18;
1298 private static int EOF_SYMBOL = 256;
1299 private static int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
1300
1301 private static byte[] bit4Reverse = {
1302 0,
1303 8,
1304 4,
1305 12,
1306 2,
1307 10,
1308 6,
1309 14,
1310 1,
1311 9,
1312 5,
1313 13,
1314 3,
1315 11,
1316 7,
1317 15
1318 };
1319
1320
1321 public class Tree
1322 {
1323 public short[] freqs;
1324 public short[] codes;
1325 public byte[] length;
1326 public int[] bl_counts;
1327 public int minNumCodes, numCodes;
1328 public int maxLength;
1329 DeflaterHuffman dh;
1330
1331 public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
1332 {
1333 this.dh = dh;
1334 this.minNumCodes = minCodes;
1335 this.maxLength = maxLength;
1336 freqs = new short[elems];
1337 bl_counts = new int[maxLength];
1338 }
1339
1340 public void Reset()
1341 {
1342 for (int i = 0; i < freqs.Length; i++) {
1343 freqs[i] = 0;
1344 }
1345 codes = null;
1346 length = null;
1347 }
1348
1349 public void WriteSymbol(int code)
1350 {
1351 // if (DeflaterConstants.DEBUGGING) {
1352 // freqs[code]--;
1353 // // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
1354 // }
1355 dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
1356 }
1357
1358 public void CheckEmpty()
1359 {
1360 bool empty = true;
1361 for (int i = 0; i < freqs.Length; i++) {
1362 if (freqs[i] != 0) {
1363 Console.WriteLine("freqs["+i+"] == "+freqs[i]);
1364 empty = false;
1365 }
1366 }
1367 if (!empty) {
1368 throw new Exception();
1369 }
1370 Console.WriteLine("checkEmpty suceeded!");
1371 }
1372
1373 public void SetStaticCodes(short[] stCodes, byte[] stLength)
1374 {
1375 codes = stCodes;
1376 length = stLength;
1377 }
1378
1379 public void BuildCodes()
1380 {
1381 int numSymbols = freqs.Length;
1382 int[] nextCode = new int[maxLength];
1383 int code = 0;
1384 codes = new short[freqs.Length];
1385
1386 // if (DeflaterConstants.DEBUGGING) {
1387 // Console.WriteLine("buildCodes: "+freqs.Length);
1388 // }
1389
1390 for (int bits = 0; bits < maxLength; bits++) {
1391 nextCode[bits] = code;
1392 code += bl_counts[bits] << (15 - bits);
1393 // if (DeflaterConstants.DEBUGGING) {
1394 // Console.WriteLine("bits: "+(bits+1)+" count: "+bl_counts[bits]
1395 // +" nextCode: "+code); // HACK : Integer.toHexString(
1396 // }
1397 }
1398 if (DeflaterConstants.DEBUGGING && code != 65536) {
1399 throw new Exception("Inconsistent bl_counts!");
1400 }
1401
1402 for (int i=0; i < numCodes; i++) {
1403 int bits = length[i];
1404 if (bits > 0) {
1405 // if (DeflaterConstants.DEBUGGING) {
1406 // Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+")," // HACK : Integer.toHexString(
1407 // +bits);
1408 // }
1409 codes[i] = BitReverse(nextCode[bits-1]);
1410 nextCode[bits-1] += 1 << (16 - bits);
1411 }
1412 }
1413 }
1414
1415 private void BuildLength(int[] childs)
1416 {
1417 this.length = new byte [freqs.Length];
1418 int numNodes = childs.Length / 2;
1419 int numLeafs = (numNodes + 1) / 2;
1420 int overflow = 0;
1421
1422 for (int i = 0; i < maxLength; i++) {
1423 bl_counts[i] = 0;
1424 }
1425
1426 /* First calculate optimal bit lengths */
1427 int[] lengths = new int[numNodes];
1428 lengths[numNodes-1] = 0;
1429
1430 for (int i = numNodes - 1; i >= 0; i--) {
1431 if (childs[2*i+1] != -1) {
1432 int bitLength = lengths[i] + 1;
1433 if (bitLength > maxLength) {
1434 bitLength = maxLength;
1435 overflow++;
1436 }
1437 lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
1438 } else {
1439 /* A leaf node */
1440 int bitLength = lengths[i];
1441 bl_counts[bitLength - 1]++;
1442 this.length[childs[2*i]] = (byte) lengths[i];
1443 }
1444 }
1445
1446 // if (DeflaterConstants.DEBUGGING) {
1447 // Console.WriteLine("Tree "+freqs.Length+" lengths:");
1448 // for (int i=0; i < numLeafs; i++) {
1449 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
1450 // + " len: "+length[childs[2*i]]);
1451 // }
1452 // }
1453
1454 if (overflow == 0) {
1455 return;
1456 }
1457
1458 int incrBitLen = maxLength - 1;
1459 do {
1460 /* Find the first bit length which could increase: */
1461 while (bl_counts[--incrBitLen] == 0)
1462 ;
1463
1464 /* Move this node one down and remove a corresponding
1465 * amount of overflow nodes.
1466 */
1467 do {
1468 bl_counts[incrBitLen]--;
1469 bl_counts[++incrBitLen]++;
1470 overflow -= 1 << (maxLength - 1 - incrBitLen);
1471 } while (overflow > 0 && incrBitLen < maxLength - 1);
1472 } while (overflow > 0);
1473
1474 /* We may have overshot above. Move some nodes from maxLength to
1475 * maxLength-1 in that case.
1476 */
1477 bl_counts[maxLength-1] += overflow;
1478 bl_counts[maxLength-2] -= overflow;
1479
1480 /* Now recompute all bit lengths, scanning in increasing
1481 * frequency. It is simpler to reconstruct all lengths instead of
1482 * fixing only the wrong ones. This idea is taken from 'ar'
1483 * written by Haruhiko Okumura.
1484 *
1485 * The nodes were inserted with decreasing frequency into the childs
1486 * array.
1487 */
1488 int nodePtr = 2 * numLeafs;
1489 for (int bits = maxLength; bits != 0; bits--) {
1490 int n = bl_counts[bits-1];
1491 while (n > 0) {
1492 int childPtr = 2*childs[nodePtr++];
1493 if (childs[childPtr + 1] == -1) {
1494 /* We found another leaf */
1495 length[childs[childPtr]] = (byte) bits;
1496 n--;
1497 }
1498 }
1499 }
1500 // if (DeflaterConstants.DEBUGGING) {
1501 // Console.WriteLine("*** After overflow elimination. ***");
1502 // for (int i=0; i < numLeafs; i++) {
1503 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
1504 // + " len: "+length[childs[2*i]]);
1505 // }
1506 // }
1507 }
1508
1509 public void BuildTree()
1510 {
1511 int numSymbols = freqs.Length;
1512
1513 /* heap is a priority queue, sorted by frequency, least frequent
1514 * nodes first. The heap is a binary tree, with the property, that
1515 * the parent node is smaller than both child nodes. This assures
1516 * that the smallest node is the first parent.
1517 *
1518 * The binary tree is encoded in an array: 0 is root node and
1519 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
1520 */
1521 int[] heap = new int[numSymbols];
1522 int heapLen = 0;
1523 int maxCode = 0;
1524 for (int n = 0; n < numSymbols; n++) {
1525 int freq = freqs[n];
1526 if (freq != 0) {
1527 /* Insert n into heap */
1528 int pos = heapLen++;
1529 int ppos;
1530 while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
1531 heap[pos] = heap[ppos];
1532 pos = ppos;
1533 }
1534 heap[pos] = n;
1535
1536 maxCode = n;
1537 }
1538 }
1539
1540 /* We could encode a single literal with 0 bits but then we
1541 * don't see the literals. Therefore we force at least two
1542 * literals to avoid this case. We don't care about order in
1543 * this case, both literals get a 1 bit code.
1544 */
1545 while (heapLen < 2) {
1546 int node = maxCode < 2 ? ++maxCode : 0;
1547 heap[heapLen++] = node;
1548 }
1549
1550 numCodes = Math.Max(maxCode + 1, minNumCodes);
1551
1552 int numLeafs = heapLen;
1553 int[] childs = new int[4*heapLen - 2];
1554 int[] values = new int[2*heapLen - 1];
1555 int numNodes = numLeafs;
1556 for (int i = 0; i < heapLen; i++) {
1557 int node = heap[i];
1558 childs[2*i] = node;
1559 childs[2*i+1] = -1;
1560 values[i] = freqs[node] << 8;
1561 heap[i] = i;
1562 }
1563
1564 /* Construct the Huffman tree by repeatedly combining the least two
1565 * frequent nodes.
1566 */
1567 do {
1568 int first = heap[0];
1569 int last = heap[--heapLen];
1570
1571 /* Propagate the hole to the leafs of the heap */
1572 int ppos = 0;
1573 int path = 1;
1574 while (path < heapLen) {
1575 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
1576 path++;
1577 }
1578
1579 heap[ppos] = heap[path];
1580 ppos = path;
1581 path = path * 2 + 1;
1582 }
1583
1584 /* Now propagate the last element down along path. Normally
1585 * it shouldn't go too deep.
1586 */
1587 int lastVal = values[last];
1588 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
1589 heap[path] = heap[ppos];
1590 }
1591 heap[path] = last;
1592
1593
1594 int second = heap[0];
1595
1596 /* Create a new node father of first and second */
1597 last = numNodes++;
1598 childs[2*last] = first;
1599 childs[2*last+1] = second;
1600 int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
1601 values[last] = lastVal = values[first] + values[second] - mindepth + 1;
1602
1603 /* Again, propagate the hole to the leafs */
1604 ppos = 0;
1605 path = 1;
1606 while (path < heapLen) {
1607 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
1608 path++;
1609 }
1610
1611 heap[ppos] = heap[path];
1612 ppos = path;
1613 path = ppos * 2 + 1;
1614 }
1615
1616 /* Now propagate the new element down along path */
1617 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
1618 heap[path] = heap[ppos];
1619 }
1620 heap[path] = last;
1621 } while (heapLen > 1);
1622
1623 if (heap[0] != childs.Length / 2 - 1) {
1624 throw new Exception("Weird!");
1625 }
1626 BuildLength(childs);
1627 }
1628
1629 public int GetEncodedLength()
1630 {
1631 int len = 0;
1632 for (int i = 0; i < freqs.Length; i++) {
1633 len += freqs[i] * length[i];
1634 }
1635 return len;
1636 }
1637
1638 public void CalcBLFreq(Tree blTree)
1639 {
1640 int max_count; /* max repeat count */
1641 int min_count; /* min repeat count */
1642 int count; /* repeat count of the current code */
1643 int curlen = -1; /* length of current code */
1644
1645 int i = 0;
1646 while (i < numCodes) {
1647 count = 1;
1648 int nextlen = length[i];
1649 if (nextlen == 0) {
1650 max_count = 138;
1651 min_count = 3;
1652 } else {
1653 max_count = 6;
1654 min_count = 3;
1655 if (curlen != nextlen) {
1656 blTree.freqs[nextlen]++;
1657 count = 0;
1658 }
1659 }
1660 curlen = nextlen;
1661 i++;
1662
1663 while (i < numCodes && curlen == length[i]) {
1664 i++;
1665 if (++count >= max_count) {
1666 break;
1667 }
1668 }
1669
1670 if (count < min_count) {
1671 blTree.freqs[curlen] += (short)count;
1672 } else if (curlen != 0) {
1673 blTree.freqs[REP_3_6]++;
1674 } else if (count <= 10) {
1675 blTree.freqs[REP_3_10]++;
1676 } else {
1677 blTree.freqs[REP_11_138]++;
1678 }
1679 }
1680 }
1681
1682 public void WriteTree(Tree blTree)
1683 {
1684 int max_count; /* max repeat count */
1685 int min_count; /* min repeat count */
1686 int count; /* repeat count of the current code */
1687 int curlen = -1; /* length of current code */
1688
1689 int i = 0;
1690 while (i < numCodes) {
1691 count = 1;
1692 int nextlen = length[i];
1693 if (nextlen == 0) {
1694 max_count = 138;
1695 min_count = 3;
1696 } else {
1697 max_count = 6;
1698 min_count = 3;
1699 if (curlen != nextlen) {
1700 blTree.WriteSymbol(nextlen);
1701 count = 0;
1702 }
1703 }
1704 curlen = nextlen;
1705 i++;
1706
1707 while (i < numCodes && curlen == length[i]) {
1708 i++;
1709 if (++count >= max_count) {
1710 break;
1711 }
1712 }
1713
1714 if (count < min_count) {
1715 while (count-- > 0) {
1716 blTree.WriteSymbol(curlen);
1717 }
1718 }
1719 else if (curlen != 0) {
1720 blTree.WriteSymbol(REP_3_6);
1721 dh.pending.WriteBits(count - 3, 2);
1722 } else if (count <= 10) {
1723 blTree.WriteSymbol(REP_3_10);
1724 dh.pending.WriteBits(count - 3, 3);
1725 } else {
1726 blTree.WriteSymbol(REP_11_138);
1727 dh.pending.WriteBits(count - 11, 7);
1728 }
1729 }
1730 }
1731 }
1732
1733 public DeflaterPending pending;
1734 private Tree literalTree, distTree, blTree;
1735
1736 private short[] d_buf;
1737 private byte[] l_buf;
1738 private int last_lit;
1739 private int extra_bits;
1740
1741 private static short[] staticLCodes;
1742 private static byte[] staticLLength;
1743 private static short[] staticDCodes;
1744 private static byte[] staticDLength;
1745
1746 /// <summary>
1747 /// Reverse the bits of a 16 bit value.
1748 /// </summary>
1749 public static short BitReverse(int value)
1750 {
1751 return (short) (bit4Reverse[value & 0xF] << 12
1752 | bit4Reverse[(value >> 4) & 0xF] << 8
1753 | bit4Reverse[(value >> 8) & 0xF] << 4
1754 | bit4Reverse[value >> 12]);
1755 }
1756
1757
1758 static DeflaterHuffman()
1759 {
1760 /* See RFC 1951 3.2.6 */
1761 /* Literal codes */
1762 staticLCodes = new short[LITERAL_NUM];
1763 staticLLength = new byte[LITERAL_NUM];
1764 int i = 0;
1765 while (i < 144) {
1766 staticLCodes[i] = BitReverse((0x030 + i) << 8);
1767 staticLLength[i++] = 8;
1768 }
1769 while (i < 256) {
1770 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
1771 staticLLength[i++] = 9;
1772 }
1773 while (i < 280) {
1774 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
1775 staticLLength[i++] = 7;
1776 }
1777 while (i < LITERAL_NUM) {
1778 staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
1779 staticLLength[i++] = 8;
1780 }
1781
1782 /* Distant codes */
1783 staticDCodes = new short[DIST_NUM];
1784 staticDLength = new byte[DIST_NUM];
1785 for (i = 0; i < DIST_NUM; i++) {
1786 staticDCodes[i] = BitReverse(i << 11);
1787 staticDLength[i] = 5;
1788 }
1789 }
1790
1791 public DeflaterHuffman(DeflaterPending pending)
1792 {
1793 this.pending = pending;
1794
1795 literalTree = new Tree(this, LITERAL_NUM, 257, 15);
1796 distTree = new Tree(this, DIST_NUM, 1, 15);
1797 blTree = new Tree(this, BITLEN_NUM, 4, 7);
1798
1799 d_buf = new short[BUFSIZE];
1800 l_buf = new byte [BUFSIZE];
1801 }
1802
1803 public void Reset()
1804 {
1805 last_lit = 0;
1806 extra_bits = 0;
1807 literalTree.Reset();
1808 distTree.Reset();
1809 blTree.Reset();
1810 }
1811
1812 private int L_code(int len)
1813 {
1814 if (len == 255) {
1815 return 285;
1816 }
1817
1818 int code = 257;
1819 while (len >= 8) {
1820 code += 4;
1821 len >>= 1;
1822 }
1823 return code + len;
1824 }
1825
1826 private int D_code(int distance)
1827 {
1828 int code = 0;
1829 while (distance >= 4) {
1830 code += 2;
1831 distance >>= 1;
1832 }
1833 return code + distance;
1834 }
1835
1836 public void SendAllTrees(int blTreeCodes)
1837 {
1838 blTree.BuildCodes();
1839 literalTree.BuildCodes();
1840 distTree.BuildCodes();
1841 pending.WriteBits(literalTree.numCodes - 257, 5);
1842 pending.WriteBits(distTree.numCodes - 1, 5);
1843 pending.WriteBits(blTreeCodes - 4, 4);
1844 for (int rank = 0; rank < blTreeCodes; rank++) {
1845 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
1846 }
1847 literalTree.WriteTree(blTree);
1848 distTree.WriteTree(blTree);
1849 // if (DeflaterConstants.DEBUGGING) {
1850 // blTree.CheckEmpty();
1851 // }
1852 }
1853
1854 public void CompressBlock()
1855 {
1856 for (int i = 0; i < last_lit; i++) {
1857 int litlen = l_buf[i] & 0xff;
1858 int dist = d_buf[i];
1859 if (dist-- != 0) {
1860 // if (DeflaterConstants.DEBUGGING) {
1861 // Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
1862 // }
1863
1864 int lc = L_code(litlen);
1865 literalTree.WriteSymbol(lc);
1866
1867 int bits = (lc - 261) / 4;
1868 if (bits > 0 && bits <= 5) {
1869 pending.WriteBits(litlen & ((1 << bits) - 1), bits);
1870 }
1871
1872 int dc = D_code(dist);
1873 distTree.WriteSymbol(dc);
1874
1875 bits = dc / 2 - 1;
1876 if (bits > 0) {
1877 pending.WriteBits(dist & ((1 << bits) - 1), bits);
1878 }
1879 } else {
1880 // if (DeflaterConstants.DEBUGGING) {
1881 // if (litlen > 32 && litlen < 127) {
1882 // Console.Write("("+(char)litlen+"): ");
1883 // } else {
1884 // Console.Write("{"+litlen+"}: ");
1885 // }
1886 // }
1887 literalTree.WriteSymbol(litlen);
1888 }
1889 }
1890 // if (DeflaterConstants.DEBUGGING) {
1891 // Console.Write("EOF: ");
1892 // }
1893 literalTree.WriteSymbol(EOF_SYMBOL);
1894 // if (DeflaterConstants.DEBUGGING) {
1895 // literalTree.CheckEmpty();
1896 // distTree.CheckEmpty();
1897 // }
1898 }
1899
1900 public void FlushStoredBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
1901 {
1902 // if (DeflaterConstants.DEBUGGING) {
1903 // Console.WriteLine("Flushing stored block "+ stored_len);
1904 // }
1905 pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1)
1906 + (lastBlock ? 1 : 0), 3);
1907 pending.AlignToByte();
1908 pending.WriteShort(stored_len);
1909 pending.WriteShort(~stored_len);
1910 pending.WriteBlock(stored, stored_offset, stored_len);
1911 Reset();
1912 }
1913
1914 public void FlushBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
1915 {
1916 literalTree.freqs[EOF_SYMBOL]++;
1917
1918 /* Build trees */
1919 literalTree.BuildTree();
1920 distTree.BuildTree();
1921
1922 /* Calculate bitlen frequency */
1923 literalTree.CalcBLFreq(blTree);
1924 distTree.CalcBLFreq(blTree);
1925
1926 /* Build bitlen tree */
1927 blTree.BuildTree();
1928
1929 int blTreeCodes = 4;
1930 for (int i = 18; i > blTreeCodes; i--) {
1931 if (blTree.length[BL_ORDER[i]] > 0) {
1932 blTreeCodes = i+1;
1933 }
1934 }
1935 int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
1936 literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
1937 extra_bits;
1938
1939 int static_len = extra_bits;
1940 for (int i = 0; i < LITERAL_NUM; i++) {
1941 static_len += literalTree.freqs[i] * staticLLength[i];
1942 }
1943 for (int i = 0; i < DIST_NUM; i++) {
1944 static_len += distTree.freqs[i] * staticDLength[i];
1945 }
1946 if (opt_len >= static_len) {
1947 /* Force static trees */
1948 opt_len = static_len;
1949 }
1950
1951 if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) {
1952 /* Store Block */
1953 // if (DeflaterConstants.DEBUGGING) {
1954 // Console.WriteLine("Storing, since " + stored_len + " < " + opt_len
1955 // + " <= " + static_len);
1956 // }
1957 FlushStoredBlock(stored, stored_offset, stored_len, lastBlock);
1958 } else if (opt_len == static_len) {
1959 /* Encode with static tree */
1960 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
1961 literalTree.SetStaticCodes(staticLCodes, staticLLength);
1962 distTree.SetStaticCodes(staticDCodes, staticDLength);
1963 CompressBlock();
1964 Reset();
1965 } else {
1966 /* Encode with dynamic tree */
1967 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
1968 SendAllTrees(blTreeCodes);
1969 CompressBlock();
1970 Reset();
1971 }
1972 }
1973
1974 public bool IsFull()
1975 {
1976 return last_lit + 16 >= BUFSIZE; // HACK: This was == 'last_lit == BUFSIZE', but errors occured with DeflateFast
1977 }
1978
1979 public bool TallyLit(int lit)
1980 {
1981 // if (DeflaterConstants.DEBUGGING) {
1982 // if (lit > 32 && lit < 127) {
1983 // Console.WriteLine("("+(char)lit+")");
1984 // } else {
1985 // Console.WriteLine("{"+lit+"}");
1986 // }
1987 // }
1988 d_buf[last_lit] = 0;
1989 l_buf[last_lit++] = (byte)lit;
1990 literalTree.freqs[lit]++;
1991 return IsFull();
1992 }
1993
1994 public bool TallyDist(int dist, int len)
1995 {
1996 // if (DeflaterConstants.DEBUGGING) {
1997 // Console.WriteLine("["+dist+","+len+"]");
1998 // }
1999
2000 d_buf[last_lit] = (short)dist;
2001 l_buf[last_lit++] = (byte)(len - 3);
2002
2003 int lc = L_code(len - 3);
2004 literalTree.freqs[lc]++;
2005 if (lc >= 265 && lc < 285) {
2006 extra_bits += (lc - 261) / 4;
2007 }
2008
2009 int dc = D_code(dist - 1);
2010 distTree.freqs[dc]++;
2011 if (dc >= 4) {
2012 extra_bits += dc / 2 - 1;
2013 }
2014 return IsFull();
2015 }
2016 }
2017 }
2018
2019 namespace NZlib.Compression {
2020
2021 /// <summary>
2022 /// This class stores the pending output of the Deflater.
2023 ///
2024 /// author of the original java version : Jochen Hoenicke
2025 /// </summary>
2026 public class DeflaterPending : PendingBuffer
2027 {
2028 public DeflaterPending() : base(DeflaterConstants.PENDING_BUF_SIZE)
2029 {
2030 }
2031 }
2032 }
2033
2034 namespace NZlib.Compression {
2035
2036 /// <summary>
2037 /// Inflater is used to decompress data that has been compressed according
2038 /// to the "deflate" standard described in rfc1950.
2039 ///
2040 /// The usage is as following. First you have to set some input with
2041 /// <code>setInput()</code>, then inflate() it. If inflate doesn't
2042 /// inflate any bytes there may be three reasons:
2043 /// <ul>
2044 /// <li>needsInput() returns true because the input buffer is empty.
2045 /// You have to provide more input with <code>setInput()</code>.
2046 /// NOTE: needsInput() also returns true when, the stream is finished.
2047 /// </li>
2048 /// <li>needsDictionary() returns true, you have to provide a preset
2049 /// dictionary with <code>setDictionary()</code>.</li>
2050 /// <li>finished() returns true, the inflater has finished.</li>
2051 /// </ul>
2052 /// Once the first output byte is produced, a dictionary will not be
2053 /// needed at a later stage.
2054 ///
2055 /// author of the original java version : John Leuner, Jochen Hoenicke
2056 /// </summary>
2057 public class Inflater
2058 {
2059 /// <summary>
2060 /// Copy lengths for literal codes 257..285
2061 /// </summary>
2062 private static int[] CPLENS = {
2063 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
2064 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
2065 };
2066
2067 /// <summary>
2068 /// Extra bits for literal codes 257..285
2069 /// </summary>
2070 private static int[] CPLEXT = {
2071 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
2072 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
2073 };
2074
2075 /// <summary>
2076 /// Copy offsets for distance codes 0..29
2077 /// </summary>
2078 private static int[] CPDIST = {
2079 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
2080 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
2081 8193, 12289, 16385, 24577
2082 };
2083
2084 /// <summary>
2085 /// Extra bits for distance codes
2086 /// </summary>
2087 private static int[] CPDEXT = {
2088 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
2089 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
2090 12, 12, 13, 13
2091 };
2092
2093 /// <summary>
2094 /// This are the state in which the inflater can be.
2095 /// </summary>
2096 private const int DECODE_HEADER = 0;
2097 private const int DECODE_DICT = 1;
2098 private const int DECODE_BLOCKS = 2;
2099 private const int DECODE_STORED_LEN1 = 3;
2100 private const int DECODE_STORED_LEN2 = 4;
2101 private const int DECODE_STORED = 5;
2102 private const int DECODE_DYN_HEADER = 6;
2103 private const int DECODE_HUFFMAN = 7;
2104 private const int DECODE_HUFFMAN_LENBITS = 8;
2105 private const int DECODE_HUFFMAN_DIST = 9;
2106 private const int DECODE_HUFFMAN_DISTBITS = 10;
2107 private const int DECODE_CHKSUM = 11;
2108 private const int FINISHED = 12;
2109
2110 /// <summary>
2111 /// This variable contains the current state.
2112 /// </summary>
2113 private int mode;
2114
2115 /// <summary>
2116 /// The adler checksum of the dictionary or of the decompressed
2117 /// stream, as it is written in the header resp. footer of the
2118 /// compressed stream.
2119 /// Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
2120 /// </summary>
2121 private int readAdler;
2122
2123 /// <summary>
2124 /// The number of bits needed to complete the current state. This
2125 /// is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
2126 /// DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
2127 /// </summary>
2128 private int neededBits;
2129 private int repLength, repDist;
2130 private int uncomprLen;
2131
2132 /// <summary>
2133 /// True, if the last block flag was set in the last block of the
2134 /// inflated stream. This means that the stream ends after the
2135 /// current block.
2136 /// </summary>
2137 private bool isLastBlock;
2138
2139 /// <summary>
2140 /// The total number of inflated bytes.
2141 /// </summary>
2142 private int totalOut;
2143
2144 /// <summary>
2145 /// The total number of bytes set with setInput(). This is not the
2146 /// value returned by getTotalIn(), since this also includes the
2147 /// unprocessed input.
2148 /// </summary>
2149 private int totalIn;
2150
2151 /// <summary>
2152 /// This variable stores the nowrap flag that was given to the constructor.
2153 /// True means, that the inflated stream doesn't contain a header nor the
2154 /// checksum in the footer.
2155 /// </summary>
2156 private bool nowrap;
2157
2158 private StreamManipulator input;
2159 private OutputWindow outputWindow;
2160 private InflaterDynHeader dynHeader;
2161 private InflaterHuffmanTree litlenTree, distTree;
2162 private Adler32 adler;
2163
2164 /// <summary>
2165 /// Creates a new inflater.
2166 /// </summary>
2167 public Inflater() : this(false)
2168 {
2169 }
2170
2171 /// <summary>
2172 /// Creates a new inflater.
2173 /// </summary>
2174 /// <param name="nowrap">
2175 /// true if no header and checksum field appears in the
2176 /// stream. This is used for GZIPed input. For compatibility with
2177 /// Sun JDK you should provide one byte of input more than needed in
2178 /// this case.
2179 /// </param>
2180 public Inflater(bool nowrap)
2181 {
2182 this.nowrap = nowrap;
2183 this.adler = new Adler32();
2184 input = new StreamManipulator();
2185 outputWindow = new OutputWindow();
2186 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
2187 }
2188
2189 /// <summary>
2190 /// Resets the inflater so that a new stream can be decompressed. All
2191 /// pending input and output will be discarded.
2192 /// </summary>
2193 public void Reset()
2194 {
2195 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
2196 totalIn = totalOut = 0;
2197 input.Reset();
2198 outputWindow.Reset();
2199 dynHeader = null;
2200 litlenTree = null;
2201 distTree = null;
2202 isLastBlock = false;
2203 adler.Reset();
2204 }
2205
2206 /// <summary>
2207 /// Decodes the deflate header.
2208 /// </summary>
2209 /// <returns>
2210 /// false if more input is needed.
2211 /// </returns>
2212 /// <exception cref="System.FormatException">
2213 /// if header is invalid.
2214 /// </exception>
2215 private bool DecodeHeader()
2216 {
2217 int header = input.PeekBits(16);
2218 if (header < 0) {
2219 return false;
2220 }
2221 input.DropBits(16);
2222 /* The header is written in "wrong" byte order */
2223 header = ((header << 8) | (header >> 8)) & 0xffff;
2224 if (header % 31 != 0) {
2225 throw new FormatException("Header checksum illegal");
2226 }
2227
2228 if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) {
2229 throw new FormatException("Compression Method unknown");
2230 }
2231
2232 /* Maximum size of the backwards window in bits.
2233 * We currently ignore this, but we could use it to make the
2234 * inflater window more space efficient. On the other hand the
2235 * full window (15 bits) is needed most times, anyway.
2236 int max_wbits = ((header & 0x7000) >> 12) + 8;
2237 */
2238
2239 if ((header & 0x0020) == 0) { // Dictionary flag?
2240 mode = DECODE_BLOCKS;
2241 } else {
2242 mode = DECODE_DICT;
2243 neededBits = 32;
2244 }
2245 return true;
2246 }
2247
2248 /// <summary>
2249 /// Decodes the dictionary checksum after the deflate header.
2250 /// </summary>
2251 /// <returns>
2252 /// false if more input is needed.
2253 /// </returns>
2254 private bool DecodeDict()
2255 {
2256 while (neededBits > 0) {
2257 int dictByte = input.PeekBits(8);
2258 if (dictByte < 0) {
2259 return false;
2260 }
2261 input.DropBits(8);
2262 readAdler = (readAdler << 8) | dictByte;
2263 neededBits -= 8;
2264 }
2265 return false;
2266 }
2267
2268 /// <summary>
2269 /// Decodes the huffman encoded symbols in the input stream.
2270 /// </summary>
2271 /// <returns>
2272 /// false if more input is needed, true if output window is
2273 /// full or the current block ends.
2274 /// </returns>
2275 /// <exception cref="System.FormatException">
2276 /// if deflated stream is invalid.
2277 /// </exception>
2278 private bool DecodeHuffman()
2279 {
2280 int free = outputWindow.GetFreeSpace();
2281 while (free >= 258) {
2282 int symbol;
2283 switch (mode) {
2284 case DECODE_HUFFMAN:
2285 /* This is the inner loop so it is optimized a bit */
2286 while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) {
2287 outputWindow.Write(symbol);
2288 if (--free < 258) {
2289 return true;
2290 }
2291 }
2292 if (symbol < 257) {
2293 if (symbol < 0) {
2294 return false;
2295 } else {
2296 /* symbol == 256: end of block */
2297 distTree = null;
2298 litlenTree = null;
2299 mode = DECODE_BLOCKS;
2300 return true;
2301 }
2302 }
2303
2304 try {
2305 repLength = CPLENS[symbol - 257];
2306 neededBits = CPLEXT[symbol - 257];
2307 } catch (Exception) {
2308 throw new FormatException("Illegal rep length code");
2309 }
2310 goto case DECODE_HUFFMAN_LENBITS;/* fall through */
2311 case DECODE_HUFFMAN_LENBITS:
2312 if (neededBits > 0) {
2313 mode = DECODE_HUFFMAN_LENBITS;
2314 int i = input.PeekBits(neededBits);
2315 if (i < 0) {
2316 return false;
2317 }
2318 input.DropBits(neededBits);
2319 repLength += i;
2320 }
2321 mode = DECODE_HUFFMAN_DIST;
2322 goto case DECODE_HUFFMAN_DIST;/* fall through */
2323 case DECODE_HUFFMAN_DIST:
2324 symbol = distTree.GetSymbol(input);
2325 if (symbol < 0) {
2326 return false;
2327 }
2328 try {
2329 repDist = CPDIST[symbol];
2330 neededBits = CPDEXT[symbol];
2331 } catch (Exception) {
2332 throw new FormatException("Illegal rep dist code");
2333 }
2334
2335 goto case DECODE_HUFFMAN_DISTBITS;/* fall through */
2336 case DECODE_HUFFMAN_DISTBITS:
2337 if (neededBits > 0) {
2338 mode = DECODE_HUFFMAN_DISTBITS;
2339 int i = input.PeekBits(neededBits);
2340 if (i < 0) {
2341 return false;
2342 }
2343 input.DropBits(neededBits);
2344 repDist += i;
2345 }
2346 outputWindow.Repeat(repLength, repDist);
2347 free -= repLength;
2348 mode = DECODE_HUFFMAN;
2349 break;
2350 default:
2351 throw new FormatException();
2352 }
2353 }
2354 return true;
2355 }
2356
2357 /// <summary>
2358 /// Decodes the adler checksum after the deflate stream.
2359 /// </summary>
2360 /// <returns>
2361 /// false if more input is needed.
2362 /// </returns>
2363 /// <exception cref="System.FormatException">
2364 /// DataFormatException, if checksum doesn't match.
2365 /// </exception>
2366 private bool DecodeChksum()
2367 {
2368 while (neededBits > 0) {
2369 int chkByte = input.PeekBits(8);
2370 if (chkByte < 0) {
2371 return false;
2372 }
2373 input.DropBits(8);
2374 readAdler = (readAdler << 8) | chkByte;
2375 neededBits -= 8;
2376 }
2377 if ((int) adler.Value != readAdler) {
2378 throw new FormatException("Adler chksum doesn't match: "
2379 + (int)adler.Value
2380 + " vs. " + readAdler);
2381 }
2382 mode = FINISHED;
2383 return false;
2384 }
2385
2386 /// <summary>
2387 /// Decodes the deflated stream.
2388 /// </summary>
2389 /// <returns>
2390 /// false if more input is needed, or if finished.
2391 /// </returns>
2392 /// <exception cref="System.FormatException">
2393 /// DataFormatException, if deflated stream is invalid.
2394 /// </exception>
2395 private bool Decode()
2396 {
2397 switch (mode) {
2398 case DECODE_HEADER:
2399 return DecodeHeader();
2400 case DECODE_DICT:
2401 return DecodeDict();
2402 case DECODE_CHKSUM:
2403 return DecodeChksum();
2404
2405 case DECODE_BLOCKS:
2406 if (isLastBlock) {
2407 if (nowrap) {
2408 mode = FINISHED;
2409 return false;
2410 } else {
2411 input.SkipToByteBoundary();
2412 neededBits = 32;
2413 mode = DECODE_CHKSUM;
2414 return true;
2415 }
2416 }
2417
2418 int type = input.PeekBits(3);
2419 if (type < 0) {
2420 return false;
2421 }
2422 input.DropBits(3);
2423
2424 if ((type & 1) != 0) {
2425 isLastBlock = true;
2426 }
2427 switch (type >> 1) {
2428 case DeflaterConstants.STORED_BLOCK:
2429 input.SkipToByteBoundary();
2430 mode = DECODE_STORED_LEN1;
2431 break;
2432 case DeflaterConstants.STATIC_TREES:
2433 litlenTree = InflaterHuffmanTree.defLitLenTree;
2434 distTree = InflaterHuffmanTree.defDistTree;
2435 mode = DECODE_HUFFMAN;
2436 break;
2437 case DeflaterConstants.DYN_TREES:
2438 dynHeader = new InflaterDynHeader();
2439 mode = DECODE_DYN_HEADER;
2440 break;
2441 default:
2442 throw new FormatException("Unknown block type "+type);
2443 }
2444 return true;
2445
2446 case DECODE_STORED_LEN1: {
2447 if ((uncomprLen = input.PeekBits(16)) < 0) {
2448 return false;
2449 }
2450 input.DropBits(16);
2451 mode = DECODE_STORED_LEN2;
2452 }
2453 goto case DECODE_STORED_LEN2; /* fall through */
2454 case DECODE_STORED_LEN2: {
2455 int nlen = input.PeekBits(16);
2456 if (nlen < 0) {
2457 return false;
2458 }
2459 input.DropBits(16);
2460 if (nlen != (uncomprLen ^ 0xffff)) {
2461 throw new FormatException("broken uncompressed block");
2462 }
2463 mode = DECODE_STORED;
2464 }
2465 goto case DECODE_STORED;/* fall through */
2466 case DECODE_STORED: {
2467 int more = outputWindow.CopyStored(input, uncomprLen);
2468 uncomprLen -= more;
2469 if (uncomprLen == 0) {
2470 mode = DECODE_BLOCKS;
2471 return true;
2472 }
2473 return !input.IsNeedingInput;
2474 }
2475
2476 case DECODE_DYN_HEADER:
2477 if (!dynHeader.Decode(input)) {
2478 return false;
2479 }
2480
2481 litlenTree = dynHeader.BuildLitLenTree();
2482 distTree = dynHeader.BuildDistTree();
2483 mode = DECODE_HUFFMAN;
2484 goto case DECODE_HUFFMAN; /* fall through */
2485 case DECODE_HUFFMAN:
2486 case DECODE_HUFFMAN_LENBITS:
2487 case DECODE_HUFFMAN_DIST:
2488 case DECODE_HUFFMAN_DISTBITS:
2489 return DecodeHuffman();
2490 case FINISHED:
2491 return false;
2492 default:
2493 throw new FormatException();
2494 }
2495 }
2496
2497 /// <summary>
2498 /// Sets the preset dictionary. This should only be called, if
2499 /// needsDictionary() returns true and it should set the same
2500 /// dictionary, that was used for deflating. The getAdler()
2501 /// function returns the checksum of the dictionary needed.
2502 /// </summary>
2503 /// <param name="buffer">
2504 /// the dictionary.
2505 /// </param>
2506 /// <exception cref="System.InvalidOperationException">
2507 /// if no dictionary is needed.
2508 /// </exception>
2509 /// <exception cref="System.ArgumentException">
2510 /// if the dictionary checksum is wrong.
2511 /// </exception>
2512 public void SetDictionary(byte[] buffer)
2513 {
2514 SetDictionary(buffer, 0, buffer.Length);
2515 }
2516
2517 /// <summary>
2518 /// Sets the preset dictionary. This should only be called, if
2519 /// needsDictionary() returns true and it should set the same
2520 /// dictionary, that was used for deflating. The getAdler()
2521 /// function returns the checksum of the dictionary needed.
2522 /// </summary>
2523 /// <param name="buffer">
2524 /// the dictionary.
2525 /// </param>
2526 /// <param name="off">
2527 /// the offset into buffer where the dictionary starts.
2528 /// </param>
2529 /// <param name="len">
2530 /// the length of the dictionary.
2531 /// </param>
2532 /// <exception cref="System.InvalidOperationException">
2533 /// if no dictionary is needed.
2534 /// </exception>
2535 /// <exception cref="System.ArgumentException">
2536 /// if the dictionary checksum is wrong.
2537 /// </exception>
2538 /// <exception cref="System.ArgumentOutOfRangeException">
2539 /// if the off and/or len are wrong.
2540 /// </exception>
2541 public void SetDictionary(byte[] buffer, int off, int len)
2542 {
2543 if (!IsNeedingDictionary) {
2544 throw new InvalidOperationException();
2545 }
2546
2547 adler.Update(buffer, off, len);
2548 if ((int) adler.Value != readAdler) {
2549 throw new ArgumentException("Wrong adler checksum");
2550 }
2551 adler.Reset();
2552 outputWindow.CopyDict(buffer, off, len);
2553 mode = DECODE_BLOCKS;
2554 }
2555
2556 /// <summary>
2557 /// Sets the input. This should only be called, if needsInput()
2558 /// returns true.
2559 /// </summary>
2560 /// <param name="buf">
2561 /// the input.
2562 /// </param>
2563 /// <exception cref="System.InvalidOperationException">
2564 /// if no input is needed.
2565 /// </exception>
2566 public void SetInput(byte[] buf)
2567 {
2568 SetInput(buf, 0, buf.Length);
2569 }
2570
2571 /// <summary>
2572 /// Sets the input. This should only be called, if needsInput()
2573 /// returns true.
2574 /// </summary>
2575 /// <param name="buf">
2576 /// the input.
2577 /// </param>
2578 /// <param name="off">
2579 /// the offset into buffer where the input starts.
2580 /// </param>
2581 /// <param name="len">
2582 /// the length of the input.
2583 /// </param>
2584 /// <exception cref="System.InvalidOperationException">
2585 /// if no input is needed.
2586 /// </exception>
2587 /// <exception cref="System.ArgumentOutOfRangeException">
2588 /// if the off and/or len are wrong.
2589 /// </exception>
2590 public void SetInput(byte[] buf, int off, int len)
2591 {
2592 input.SetInput(buf, off, len);
2593 totalIn += len;
2594 }
2595
2596 /// <summary>
2597 /// Inflates the compressed stream to the output buffer. If this
2598 /// returns 0, you should check, whether needsDictionary(),
2599 /// needsInput() or finished() returns true, to determine why no
2600 /// further output is produced.
2601 /// </summary>
2602 /// <param name = "buf">
2603 /// the output buffer.
2604 /// </param>
2605 /// <returns>
2606 /// the number of bytes written to the buffer, 0 if no further
2607 /// output can be produced.
2608 /// </returns>
2609 /// <exception cref="System.ArgumentOutOfRangeException">
2610 /// if buf has length 0.
2611 /// </exception>
2612 /// <exception cref="System.FormatException">
2613 /// if deflated stream is invalid.
2614 /// </exception>
2615 public int Inflate(byte[] buf)
2616 {
2617 return Inflate(buf, 0, buf.Length);
2618 }
2619
2620 /// <summary>
2621 /// Inflates the compressed stream to the output buffer. If this
2622 /// returns 0, you should check, whether needsDictionary(),
2623 /// needsInput() or finished() returns true, to determine why no
2624 /// further output is produced.
2625 /// </summary>
2626 /// <param name = "buf">
2627 /// the output buffer.
2628 /// </param>
2629 /// <param name = "off">
2630 /// the offset into buffer where the output should start.
2631 /// </param>
2632 /// <param name = "len">
2633 /// the maximum length of the output.
2634 /// </param>
2635 /// <returns>
2636 /// the number of bytes written to the buffer, 0 if no further output can be produced.
2637 /// </returns>
2638 /// <exception cref="System.ArgumentOutOfRangeException">
2639 /// if len is &lt;= 0.
2640 /// </exception>
2641 /// <exception cref="System.ArgumentOutOfRangeException">
2642 /// if the off and/or len are wrong.
2643 /// </exception>
2644 /// <exception cref="System.FormatException">
2645 /// if deflated stream is invalid.
2646 /// </exception>
2647 public int Inflate(byte[] buf, int off, int len)
2648 {
2649 if (len <= 0) {
2650 throw new ArgumentOutOfRangeException("len <= 0");
2651 }
2652 int count = 0;
2653 int more;
2654 do {
2655 if (mode != DECODE_CHKSUM) {
2656 /* Don't give away any output, if we are waiting for the
2657 * checksum in the input stream.
2658 *
2659 * With this trick we have always:
2660 * needsInput() and not finished()
2661 * implies more output can be produced.
2662 */
2663 more = outputWindow.CopyOutput(buf, off, len);
2664 adler.Update(buf, off, more);
2665 off += more;
2666 count += more;
2667 totalOut += more;
2668 len -= more;
2669 if (len == 0) {
2670 return count;
2671 }
2672 }
2673 } while (Decode() || (outputWindow.GetAvailable() > 0 &&
2674 mode != DECODE_CHKSUM));
2675 return count;
2676 }
2677
2678 /// <summary>
2679 /// Returns true, if the input buffer is empty.
2680 /// You should then call setInput().
2681 /// NOTE: This method also returns true when the stream is finished.
2682 /// </summary>
2683 public bool IsNeedingInput {
2684 get {
2685 return input.IsNeedingInput;
2686 }
2687 }
2688
2689 /// <summary>
2690 /// Returns true, if a preset dictionary is needed to inflate the input.
2691 /// </summary>
2692 public bool IsNeedingDictionary {
2693 get {
2694 return mode == DECODE_DICT && neededBits == 0;
2695 }
2696 }
2697
2698 /// <summary>
2699 /// Returns true, if the inflater has finished. This means, that no
2700 /// input is needed and no output can be produced.
2701 /// </summary>
2702 public bool IsFinished {
2703 get {
2704 return mode == FINISHED && outputWindow.GetAvailable() == 0;
2705 }
2706 }
2707
2708 /// <summary>
2709 /// Gets the adler checksum. This is either the checksum of all
2710 /// uncompressed bytes returned by inflate(), or if needsDictionary()
2711 /// returns true (and thus no output was yet produced) this is the
2712 /// adler checksum of the expected dictionary.
2713 /// </summary>
2714 /// <returns>
2715 /// the adler checksum.
2716 /// </returns>
2717 public int Adler {
2718 get {
2719 return IsNeedingDictionary ? readAdler : (int) adler.Value;
2720 }
2721 }
2722
2723 /// <summary>
2724 /// Gets the total number of output bytes returned by inflate().
2725 /// </summary>
2726 /// <returns>
2727 /// the total number of output bytes.
2728 /// </returns>
2729 public int TotalOut {
2730 get {
2731 return totalOut;
2732 }
2733 }
2734
2735 /// <summary>
2736 /// Gets the total number of processed compressed input bytes.
2737 /// </summary>
2738 /// <returns>
2739 /// the total number of bytes of processed input bytes.
2740 /// </returns>
2741 public int TotalIn {
2742 get {
2743 return totalIn - RemainingInput;
2744 }
2745 }
2746
2747 /// <summary>
2748 /// Gets the number of unprocessed input. Useful, if the end of the
2749 /// stream is reached and you want to further process the bytes after
2750 /// the deflate stream.
2751 /// </summary>
2752 /// <returns>
2753 /// the number of bytes of the input which were not processed.
2754 /// </returns>
2755 public int RemainingInput {
2756 get {
2757 return input.AvailableBytes;
2758 }
2759 }
2760 }
2761 }
2762
2763 namespace NZlib.Compression {
2764
2765 public class InflaterDynHeader
2766 {
2767 private const int LNUM = 0;
2768 private const int DNUM = 1;
2769 private const int BLNUM = 2;
2770 private const int BLLENS = 3;
2771 private const int LLENS = 4;
2772 private const int DLENS = 5;
2773 private const int LREPS = 6;
2774 private const int DREPS = 7;
2775 private const int FINISH = 8;
2776
2777 private byte[] blLens;
2778 private byte[] litlenLens;
2779 private byte[] distLens;
2780
2781 private InflaterHuffmanTree blTree;
2782
2783 private int mode;
2784 private int lnum, dnum, blnum;
2785 private int repBits;
2786 private byte repeatedLen;
2787 private int ptr;
2788
2789 private static int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
2790
2791 public InflaterDynHeader()
2792 {
2793 }
2794
2795 public bool Decode(StreamManipulator input)
2796 {
2797 decode_loop:
2798 for (;;) {
2799 switch (mode) {
2800 case LNUM:
2801 lnum = input.PeekBits(5);
2802 if (lnum < 0) {
2803 return false;
2804 }
2805 lnum += 257;
2806 input.DropBits(5);
2807 litlenLens = new byte[lnum];
2808 // System.err.println("LNUM: "+lnum);
2809 mode = DNUM;
2810 goto case DNUM;/* fall through */
2811 case DNUM:
2812 dnum = input.PeekBits(5);
2813 if (dnum < 0) {
2814 return false;
2815 }
2816 dnum++;
2817 input.DropBits(5);
2818 distLens = new byte[dnum];
2819 // System.err.println("DNUM: "+dnum);
2820 mode = BLNUM;
2821 goto case BLNUM;/* fall through */
2822 case BLNUM:
2823 blnum = input.PeekBits(4);
2824 if (blnum < 0) {
2825 return false;
2826 }
2827 blnum += 4;
2828 input.DropBits(4);
2829 blLens = new byte[19];
2830 ptr = 0;
2831 // System.err.println("BLNUM: "+blnum);
2832 mode = BLLENS;
2833 goto case BLLENS;/* fall through */
2834 case BLLENS:
2835 while (ptr < blnum) {
2836 int len = input.PeekBits(3);
2837 if (len < 0) {
2838 return false;
2839 }
2840 input.DropBits(3);
2841 // System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
2842 blLens[BL_ORDER[ptr]] = (byte) len;
2843 ptr++;
2844 }
2845 blTree = new InflaterHuffmanTree(blLens);
2846 blLens = null;
2847 ptr = 0;
2848 mode = LLENS;
2849 goto case LLENS;/* fall through */
2850 case LLENS:
2851 while (ptr < lnum) {
2852 int symbol = blTree.GetSymbol(input);
2853 if (symbol < 0) {
2854 return false;
2855 }
2856 switch (symbol) {
2857 default:
2858 // System.err.println("litlenLens["+ptr+"]: "+symbol);
2859 litlenLens[ptr++] = (byte) symbol;
2860 break;
2861 case 16: /* repeat last len 3-6 times */
2862 if (ptr == 0) {
2863 throw new Exception("Repeating, but no prev len");
2864 }
2865
2866 // System.err.println("litlenLens["+ptr+"]: repeat");
2867 repeatedLen = litlenLens[ptr-1];
2868 repBits = 2;
2869 for (int i = 3; i-- > 0; ) {
2870 if (ptr >= lnum) {
2871 throw new Exception();
2872 }
2873 litlenLens[ptr++] = repeatedLen;
2874 }
2875 mode = LREPS;
2876 goto decode_loop;
2877 case 17: /* repeat zero 3-10 times */
2878 // System.err.println("litlenLens["+ptr+"]: zero repeat");
2879 repeatedLen = 0;
2880 repBits = 3;
2881 for (int i = 3; i-- > 0; ) {
2882 if (ptr >= lnum) {
2883 throw new Exception();
2884 }
2885 litlenLens[ptr++] = repeatedLen;
2886 }
2887 mode = LREPS;
2888 goto decode_loop;
2889 case 18: /* repeat zero 11-138 times */
2890 // System.err.println("litlenLens["+ptr+"]: zero repeat");
2891 repeatedLen = 0;
2892 repBits = 7;
2893 for (int i = 11; i-- > 0; ) {
2894 if (ptr >= lnum) {
2895 throw new Exception();
2896 }
2897 litlenLens[ptr++] = repeatedLen;
2898 }
2899 mode = LREPS;
2900 goto decode_loop;
2901 }
2902 }
2903 ptr = 0;
2904 mode = DLENS;
2905 goto case DLENS;/* fall through */
2906 case DLENS:
2907 while (ptr < dnum) {
2908 int symbol = blTree.GetSymbol(input);
2909 if (symbol < 0) {
2910 return false;
2911 }
2912 switch (symbol) {
2913 default:
2914 distLens[ptr++] = (byte) symbol;
2915 // System.err.println("distLens["+ptr+"]: "+symbol);
2916 break;
2917 case 16: /* repeat last len 3-6 times */
2918 if (ptr == 0) {
2919 throw new Exception("Repeating, but no prev len");
2920 }
2921 // System.err.println("distLens["+ptr+"]: repeat");
2922 repeatedLen = distLens[ptr-1];
2923 repBits = 2;
2924 for (int i = 3; i-- > 0; ) {
2925 if (ptr >= dnum) {
2926 throw new Exception();
2927 }
2928 distLens[ptr++] = repeatedLen;
2929 }
2930 mode = DREPS;
2931 goto decode_loop;
2932 case 17: /* repeat zero 3-10 times */
2933 // System.err.println("distLens["+ptr+"]: repeat zero");
2934 repeatedLen = 0;
2935 repBits = 3;
2936 for (int i = 3; i-- > 0; ) {
2937 if (ptr >= dnum) {
2938 throw new Exception();
2939 }
2940 distLens[ptr++] = repeatedLen;
2941 }
2942 mode = DREPS;
2943 goto decode_loop;
2944 case 18: /* repeat zero 11-138 times */
2945 // System.err.println("distLens["+ptr+"]: repeat zero");
2946 repeatedLen = 0;
2947 repBits = 7;
2948 for (int i = 11; i-- > 0; ) {
2949 if (ptr >= dnum) {
2950 throw new Exception();
2951 }
2952 distLens[ptr++] = repeatedLen;
2953 }
2954 mode = DREPS;
2955 goto decode_loop;
2956 }
2957 }
2958 mode = FINISH;
2959 return true;
2960 case LREPS:
2961 {
2962 int count = input.PeekBits(repBits);
2963 if (count < 0) {
2964 return false;
2965 }
2966 input.DropBits(repBits);
2967 // System.err.println("litlenLens repeat: "+repBits);
2968 while (count-- > 0) {
2969 if (ptr >= lnum) {
2970 throw new Exception();
2971 }
2972 litlenLens[ptr++] = repeatedLen;
2973 }
2974 }
2975 mode = LLENS;
2976 goto decode_loop;
2977 case DREPS:
2978 {
2979 int count = input.PeekBits(repBits);
2980 if (count < 0) {
2981 return false;
2982 }
2983 input.DropBits(repBits);
2984 while (count-- > 0) {
2985 if (ptr >= dnum) {
2986 throw new Exception();
2987 }
2988 distLens[ptr++] = repeatedLen;
2989 }
2990 }
2991 mode = DLENS;
2992 goto decode_loop;
2993 }
2994 }
2995 }
2996
2997 public InflaterHuffmanTree BuildLitLenTree()
2998 {
2999 return new InflaterHuffmanTree(litlenLens);
3000 }
3001
3002 public InflaterHuffmanTree BuildDistTree()
3003 {
3004 return new InflaterHuffmanTree(distLens);
3005 }
3006 }
3007 }
3008
3009 namespace NZlib.Compression {
3010
3011 public class InflaterHuffmanTree
3012 {
3013 private static int MAX_BITLEN = 15;
3014 private short[] tree;
3015
3016 public static InflaterHuffmanTree defLitLenTree, defDistTree;
3017
3018 static InflaterHuffmanTree()
3019 {
3020 try {
3021 byte[] codeLengths = new byte[288];
3022 int i = 0;
3023 while (i < 144) {
3024 codeLengths[i++] = 8;
3025 }
3026 while (i < 256) {
3027 codeLengths[i++] = 9;
3028 }
3029 while (i < 280) {
3030 codeLengths[i++] = 7;
3031 }
3032 while (i < 288) {
3033 codeLengths[i++] = 8;
3034 }
3035 defLitLenTree = new InflaterHuffmanTree(codeLengths);
3036
3037 codeLengths = new byte[32];
3038 i = 0;
3039 while (i < 32) {
3040 codeLengths[i++] = 5;
3041 }
3042 defDistTree = new InflaterHuffmanTree(codeLengths);
3043 } catch (Exception) {
3044 throw new ApplicationException("InflaterHuffmanTree: static tree length illegal");
3045 }
3046 }
3047
3048 /// <summary>
3049 /// Constructs a Huffman tree from the array of code lengths.
3050 /// </summary>
3051 /// <param name = "codeLengths">
3052 /// the array of code lengths
3053 /// </param>
3054 public InflaterHuffmanTree(byte[] codeLengths)
3055 {
3056 BuildTree(codeLengths);
3057 }
3058
3059 private void BuildTree(byte[] codeLengths)
3060 {
3061 int[] blCount = new int[MAX_BITLEN + 1];
3062 int[] nextCode = new int[MAX_BITLEN + 1];
3063
3064 for (int i = 0; i < codeLengths.Length; i++) {
3065 int bits = codeLengths[i];
3066 if (bits > 0)
3067 blCount[bits]++;
3068 }
3069
3070 int code = 0;
3071 int treeSize = 512;
3072 for (int bits = 1; bits <= MAX_BITLEN; bits++) {
3073 nextCode[bits] = code;
3074 code += blCount[bits] << (16 - bits);
3075 if (bits >= 10) {
3076 /* We need an extra table for bit lengths >= 10. */
3077 int start = nextCode[bits] & 0x1ff80;
3078 int end = code & 0x1ff80;
3079 treeSize += (end - start) >> (16 - bits);
3080 }
3081 }
3082 if (code != 65536) {
3083 throw new Exception("Code lengths don't add up properly.");
3084 }
3085 /* Now create and fill the extra tables from longest to shortest
3086 * bit len. This way the sub trees will be aligned.
3087 */
3088 tree = new short[treeSize];
3089 int treePtr = 512;
3090 for (int bits = MAX_BITLEN; bits >= 10; bits--) {
3091 int end = code & 0x1ff80;
3092 code -= blCount[bits] << (16 - bits);
3093 int start = code & 0x1ff80;
3094 for (int i = start; i < end; i += 1 << 7) {
3095 tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
3096 treePtr += 1 << (bits-9);
3097 }
3098 }
3099
3100 for (int i = 0; i < codeLengths.Length; i++) {
3101 int bits = codeLengths[i];
3102 if (bits == 0) {
3103 continue;
3104 }
3105 code = nextCode[bits];
3106 int revcode = DeflaterHuffman.BitReverse(code);
3107 if (bits <= 9) {
3108 do {
3109 tree[revcode] = (short) ((i << 4) | bits);
3110 revcode += 1 << bits;
3111 } while (revcode < 512);
3112 } else {
3113 int subTree = tree[revcode & 511];
3114 int treeLen = 1 << (subTree & 15);
3115 subTree = -(subTree >> 4);
3116 do {
3117 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
3118 revcode += 1 << bits;
3119 } while (revcode < treeLen);
3120 }
3121 nextCode[bits] = code + (1 << (16 - bits));
3122 }
3123
3124 }
3125
3126 /// <summary>
3127 /// Reads the next symbol from input. The symbol is encoded using the
3128 /// huffman tree.
3129 /// </summary>
3130 /// <param name="input">
3131 /// input the input source.
3132 /// </param>
3133 /// <returns>
3134 /// the next symbol, or -1 if not enough input is available.
3135 /// </returns>
3136 public int GetSymbol(StreamManipulator input)
3137 {
3138 int lookahead, symbol;
3139 if ((lookahead = input.PeekBits(9)) >= 0) {
3140 if ((symbol = tree[lookahead]) >= 0) {
3141 input.DropBits(symbol & 15);
3142 return symbol >> 4;
3143 }
3144 int subtree = -(symbol >> 4);
3145 int bitlen = symbol & 15;
3146 if ((lookahead = input.PeekBits(bitlen)) >= 0) {
3147 symbol = tree[subtree | (lookahead >> 9)];
3148 input.DropBits(symbol & 15);
3149 return symbol >> 4;
3150 } else {
3151 int bits = input.AvailableBits;
3152 lookahead = input.PeekBits(bits);
3153 symbol = tree[subtree | (lookahead >> 9)];
3154 if ((symbol & 15) <= bits) {
3155 input.DropBits(symbol & 15);
3156 return symbol >> 4;
3157 } else {
3158 return -1;
3159 }
3160 }
3161 } else {
3162 int bits = input.AvailableBits;
3163 lookahead = input.PeekBits(bits);
3164 symbol = tree[lookahead];
3165 if (symbol >= 0 && (symbol & 15) <= bits) {
3166 input.DropBits(symbol & 15);
3167 return symbol >> 4;
3168 } else {
3169 return -1;
3170 }
3171 }
3172 }
3173 }
3174 }
3175
3176 namespace NZlib.Compression {
3177
3178 /// <summary>
3179 /// This class is general purpose class for writing data to a buffer.
3180 ///
3181 /// It allows you to write bits as well as bytes
3182 /// Based on DeflaterPending.java
3183 ///
3184 /// author of the original java version : Jochen Hoenicke
3185 /// </summary>
3186 public class PendingBuffer
3187 {
3188 protected byte[] buf;
3189 int start;
3190 int end;
3191
3192 uint bits;
3193 int bitCount;
3194
3195 public PendingBuffer() : this( 4096 )
3196 {
3197
3198 }
3199
3200 public PendingBuffer(int bufsize)
3201 {
3202 buf = new byte[bufsize];
3203 }
3204
3205 public void Reset()
3206 {
3207 start = end = bitCount = 0;
3208 }
3209
3210 public void WriteByte(int b)
3211 {
3212 if (DeflaterConstants.DEBUGGING && start != 0)
3213 throw new Exception();
3214 buf[end++] = (byte) b;
3215 }
3216
3217 public void WriteShort(int s)
3218 {
3219 if (DeflaterConstants.DEBUGGING && start != 0) {
3220 throw new Exception();
3221 }
3222 buf[end++] = (byte) s;
3223 buf[end++] = (byte) (s >> 8);
3224 }
3225
3226 public void WriteInt(int s)
3227 {
3228 if (DeflaterConstants.DEBUGGING && start != 0) {
3229 throw new Exception();
3230 }
3231 buf[end++] = (byte) s;
3232 buf[end++] = (byte) (s >> 8);
3233 buf[end++] = (byte) (s >> 16);
3234 buf[end++] = (byte) (s >> 24);
3235 }
3236
3237 public void WriteBlock(byte[] block, int offset, int len)
3238 {
3239 if (DeflaterConstants.DEBUGGING && start != 0) {
3240 throw new Exception();
3241 }
3242 System.Array.Copy(block, offset, buf, end, len);
3243 end += len;
3244 }
3245
3246 public int BitCount {
3247 get {
3248 return bitCount;
3249 }
3250 }
3251
3252 public void AlignToByte()
3253 {
3254 if (DeflaterConstants.DEBUGGING && start != 0) {
3255 throw new Exception();
3256 }
3257 if (bitCount > 0) {
3258 buf[end++] = (byte) bits;
3259 if (bitCount > 8) {
3260 buf[end++] = (byte) (bits >> 8);
3261 }
3262 }
3263 bits = 0;
3264 bitCount = 0;
3265 }
3266
3267 public void WriteBits(int b, int count)
3268 {
3269 if (DeflaterConstants.DEBUGGING && start != 0) {
3270 throw new Exception();
3271 }
3272 // if (DeflaterConstants.DEBUGGING) {
3273 // Console.WriteLine("writeBits("+b+","+count+")");
3274 // }
3275 bits |= (uint)(b << bitCount);
3276 bitCount += count;
3277 if (bitCount >= 16) {
3278 buf[end++] = (byte) bits;
3279 buf[end++] = (byte) (bits >> 8);
3280 bits >>= 16;
3281 bitCount -= 16;
3282 }
3283 }
3284
3285 public void WriteShortMSB(int s)
3286 {
3287 if (DeflaterConstants.DEBUGGING && start != 0) {
3288 throw new Exception();
3289 }
3290 buf[end++] = (byte) (s >> 8);
3291 buf[end++] = (byte) s;
3292 }
3293
3294 public bool IsFlushed {
3295 get {
3296 return end == 0;
3297 }
3298 }
3299
3300 /// <summary>
3301 /// Flushes the pending buffer into the given output array. If the
3302 /// output array is to small, only a partial flush is done.
3303 /// </summary>
3304 /// <param name="output">
3305 /// the output array;
3306 /// </param>
3307 /// <param name="offset">
3308 /// the offset into output array;
3309 /// </param>
3310 /// <param name="length">
3311 /// length the maximum number of bytes to store;
3312 /// </param>
3313 /// <exception name="ArgumentOutOfRangeException">
3314 /// IndexOutOfBoundsException if offset or length are invalid.
3315 /// </exception>
3316 public int Flush(byte[] output, int offset, int length)
3317 {
3318 if (bitCount >= 8) {
3319 buf[end++] = (byte) bits;
3320 bits >>= 8;
3321 bitCount -= 8;
3322 }
3323 if (length > end - start) {
3324 length = end - start;
3325 System.Array.Copy(buf, start, output, offset, length);
3326 start = 0;
3327 end = 0;
3328 } else {
3329 System.Array.Copy(buf, start, output, offset, length);
3330 start += length;
3331 }
3332 return length;
3333 }
3334
3335 public byte[] ToByteArray()
3336 {
3337 byte[] ret = new byte[ end - start ];
3338 System.Array.Copy(buf, start, ret, 0, ret.Length);
3339 start = 0;
3340 end = 0;
3341 return ret;
3342 }
3343 }
3344 }
3345
3346 namespace NZlib.Checksums {
3347
3348 /// <summary>
3349 /// Computes Adler32 checksum for a stream of data. An Adler32
3350 /// checksum is not as reliable as a CRC32 checksum, but a lot faster to
3351 /// compute.
3352 ///
3353 /// The specification for Adler32 may be found in RFC 1950.
3354 /// ZLIB Compressed Data Format Specification version 3.3)
3355 ///
3356 ///
3357 /// From that document:
3358 ///
3359 /// "ADLER32 (Adler-32 checksum)
3360 /// This contains a checksum value of the uncompressed data
3361 /// (excluding any dictionary data) computed according to Adler-32
3362 /// algorithm. This algorithm is a 32-bit extension and improvement
3363 /// of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
3364 /// standard.
3365 ///
3366 /// Adler-32 is composed of two sums accumulated per byte: s1 is
3367 /// the sum of all bytes, s2 is the sum of all s1 values. Both sums
3368 /// are done modulo 65521. s1 is initialized to 1, s2 to zero. The
3369 /// Adler-32 checksum is stored as s2*65536 + s1 in most-
3370 /// significant-byte first (network) order."
3371 ///
3372 /// "8.2. The Adler-32 algorithm
3373 ///
3374 /// The Adler-32 algorithm is much faster than the CRC32 algorithm yet
3375 /// still provides an extremely low probability of undetected errors.
3376 ///
3377 /// The modulo on unsigned long accumulators can be delayed for 5552
3378 /// bytes, so the modulo operation time is negligible. If the bytes
3379 /// are a, b, c, the second sum is 3a + 2b + c + 3, and so is position
3380 /// and order sensitive, unlike the first sum, which is just a
3381 /// checksum. That 65521 is prime is important to avoid a possible
3382 /// large class of two-byte errors that leave the check unchanged.
3383 /// (The Fletcher checksum uses 255, which is not prime and which also
3384 /// makes the Fletcher check insensitive to single byte changes 0 -
3385 /// 255.)
3386 ///
3387 /// The sum s1 is initialized to 1 instead of zero to make the length
3388 /// of the sequence part of s2, so that the length does not have to be
3389 /// checked separately. (Any sequence of zeroes has a Fletcher
3390 /// checksum of zero.)"
3391 /// </summary>
3392 /// <see cref="NZlib.Streams.InflaterInputStream"/>
3393 /// <see cref="NZlib.Streams.DeflaterOutputStream"/>
3394 public sealed class Adler32 : IChecksum
3395 {
3396 /// <summary>
3397 /// largest prime smaller than 65536
3398 /// </summary>
3399 readonly static uint BASE = 65521;
3400
3401 uint checksum;
3402
3403 /// <summary>
3404 /// Returns the Adler32 data checksum computed so far.
3405 /// </summary>
3406 public long Value {
3407 get {
3408 return (long) checksum & 0xFFFFFFFFL;
3409 }
3410 }
3411
3412 /// <summary>
3413 /// Creates a new instance of the <code>Adler32</code> class.
3414 /// The checksum starts off with a value of 1.
3415 /// </summary>
3416 public Adler32()
3417 {
3418 Reset();
3419 }
3420
3421 /// <summary>
3422 /// Resets the Adler32 checksum to the initial value.
3423 /// </summary>
3424 public void Reset()
3425 {
3426 checksum = 1; //Initialize to 1
3427 }
3428
3429 /// <summary>
3430 /// Updates the checksum with the byte b.
3431 /// </summary>
3432 /// <param name="bval">
3433 /// the data value to add. The high byte of the int is ignored.
3434 /// </param>
3435 public void Update(int bval)
3436 {
3437 //We could make a length 1 byte array and call update again, but I
3438 //would rather not have that overhead
3439 uint s1 = checksum & 0xFFFF;
3440 uint s2 = checksum >> 16;
3441
3442 s1 = (s1 + ((uint)bval & 0xFF)) % BASE;
3443 s2 = (s1 + s2) % BASE;
3444
3445 checksum = (s2 << 16) + s1;
3446 }
3447
3448 /// <summary>
3449 /// Updates the checksum with the bytes taken from the array.
3450 /// </summary>
3451 /// <param name="buffer">
3452 /// buffer an array of bytes
3453 /// </param>
3454 public void Update(byte[] buffer)
3455 {
3456 Update(buffer, 0, buffer.Length);
3457 }
3458
3459 /// <summary>
3460 /// Updates the checksum with the bytes taken from the array.
3461 /// </summary>
3462 /// <param name="buf">
3463 /// an array of bytes
3464 /// </param>
3465 /// <param name="off">
3466 /// the start of the data used for this update
3467 /// </param>
3468 /// <param name="len">
3469 /// the number of bytes to use for this update
3470 /// </param>
3471 public void Update(byte[] buf, int off, int len)
3472 {
3473 if (buf == null) {
3474 throw new ArgumentNullException("buf");
3475 }
3476
3477 if (off < 0 || len < 0 || off + len > buf.Length) {
3478 throw new ArgumentOutOfRangeException();
3479 }
3480
3481 //(By Per Bothner)
3482 uint s1 = checksum & 0xFFFF;
3483 uint s2 = checksum >> 16;
3484
3485 while (len > 0) {
3486 // We can defer the modulo operation:
3487 // s1 maximally grows from 65521 to 65521 + 255 * 3800
3488 // s2 maximally grows by 3800 * median(s1) = 2090079800 < 2^31
3489 int n = 3800;
3490 if (n > len) {
3491 n = len;
3492 }
3493 len -= n;
3494 while (--n >= 0) {
3495 s1 = s1 + (uint)(buf[off++] & 0xFF);
3496 s2 = s2 + s1;
3497 }
3498 s1 %= BASE;
3499 s2 %= BASE;
3500 }
3501
3502 checksum = (s2 << 16) | s1;
3503 }
3504 }
3505 }
3506
3507 namespace NZlib.Checksums {
3508
3509 /// <summary>
3510 /// Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
3511 /// x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
3512 ///
3513 /// Polynomials over GF(2) are represented in binary, one bit per coefficient,
3514 /// with the lowest powers in the most significant bit. Then adding polynomials
3515 /// is just exclusive-or, and multiplying a polynomial by x is a right shift by
3516 /// one. If we call the above polynomial p, and represent a byte as the
3517 /// polynomial q, also with the lowest power in the most significant bit (so the
3518 /// byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
3519 /// where a mod b means the remainder after dividing a by b.
3520 ///
3521 /// This calculation is done using the shift-register method of multiplying and
3522 /// taking the remainder. The register is initialized to zero, and for each
3523 /// incoming bit, x^32 is added mod p to the register if the bit is a one (where
3524 /// x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
3525 /// x (which is shifting right by one and adding x^32 mod p if the bit shifted
3526 /// out is a one). We start with the highest power (least significant bit) of
3527 /// q and repeat for all eight bits of q.
3528 ///
3529 /// The table is simply the CRC of all possible eight bit values. This is all
3530 /// the information needed to generate CRC's on data a byte at a time for all
3531 /// combinations of CRC register values and incoming bytes.
3532 /// </summary>
3533 public sealed class Crc32 : IChecksum
3534 {
3535 readonly static uint CrcSeed = 0xFFFFFFFF;
3536
3537 readonly static uint[] CrcTable = new uint[] {
3538 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,
3539 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,
3540 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,
3541 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
3542 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,
3543 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
3544 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
3545 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
3546 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,
3547 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,
3548 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,
3549 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
3550 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,
3551 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
3552 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,
3553 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
3554 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
3555 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
3556 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,
3557 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
3558 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
3559 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,
3560 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,
3561 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
3562 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,
3563 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,
3564 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
3565 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
3566 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344,
3567 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
3568 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,
3569 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
3570 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,
3571 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
3572 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
3573 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
3574 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,
3575 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,
3576 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,
3577 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
3578 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,
3579 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
3580 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,
3581 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
3582 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,
3583 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,
3584 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,
3585 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
3586 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
3587 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,
3588 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,
3589 0x2D02EF8D
3590 };
3591
3592 /// <summary>
3593 /// The crc data checksum so far.
3594 /// </summary>
3595 uint crc = 0;
3596
3597 /// <summary>
3598 /// Returns the CRC32 data checksum computed so far.
3599 /// </summary>
3600 public long Value {
3601 get {
3602 return (long)crc;
3603 }
3604 }
3605
3606 /// <summary>
3607 /// Resets the CRC32 data checksum as if no update was ever called.
3608 /// </summary>
3609 public void Reset()
3610 {
3611 crc = 0;
3612 }
3613
3614 /// <summary>
3615 /// Updates the checksum with the int bval.
3616 /// </summary>
3617 /// <param name = "bval">
3618 /// the byte is taken as the lower 8 bits of bval
3619 /// </param>
3620 public void Update(int bval)
3621 {
3622 crc ^= CrcSeed;
3623 crc = CrcTable[(crc ^ bval) & 0xFF] ^ (crc >> 8);
3624 crc ^= CrcSeed;
3625 }
3626
3627 /// <summary>
3628 /// Updates the checksum with the bytes taken from the array.
3629 /// </summary>
3630 /// <param name="buffer">
3631 /// buffer an array of bytes
3632 /// </param>
3633 public void Update(byte[] buffer)
3634 {
3635 Update(buffer, 0, buffer.Length);
3636 }
3637
3638 /// <summary>
3639 /// Adds the byte array to the data checksum.
3640 /// </summary>
3641 /// <param name = "buf">
3642 /// the buffer which contains the data
3643 /// </param>
3644 /// <param name = "off">
3645 /// the offset in the buffer where the data starts
3646 /// </param>
3647 /// <param name = "len">
3648 /// the length of the data
3649 /// </param>
3650 public void Update(byte[] buf, int off, int len)
3651 {
3652 if (buf == null) {
3653 throw new ArgumentNullException("buf");
3654 }
3655
3656 if (off < 0 || len < 0 || off + len > buf.Length) {
3657 throw new ArgumentOutOfRangeException();
3658 }
3659
3660 crc ^= CrcSeed;
3661
3662 while (--len >= 0) {
3663 crc = CrcTable[(crc ^ buf[off++]) & 0xFF] ^ (crc >> 8);
3664 }
3665
3666 crc ^= CrcSeed;
3667 }
3668 }
3669 }
3670
3671 namespace NZlib.Checksums {
3672
3673 /// <summary>
3674 /// Interface to compute a data checksum used by checked input/output streams.
3675 /// A data checksum can be updated by one byte or with a byte array. After each
3676 /// update the value of the current checksum can be returned by calling
3677 /// <code>getValue</code>. The complete checksum object can also be reset
3678 /// so it can be used again with new data.
3679 /// </summary>
3680 public interface IChecksum
3681 {
3682 /// <summary>
3683 /// Returns the data checksum computed so far.
3684 /// </summary>
3685 long Value {
3686 get;
3687 }
3688
3689 /// <summary>
3690 /// Resets the data checksum as if no update was ever called.
3691 /// </summary>
3692 void Reset();
3693
3694 /// <summary>
3695 /// Adds one byte to the data checksum.
3696 /// </summary>
3697 /// <param name = "bval">
3698 /// the data value to add. The high byte of the int is ignored.
3699 /// </param>
3700 void Update(int bval);
3701
3702 /// <summary>
3703 /// Updates the data checksum with the bytes taken from the array.
3704 /// </summary>
3705 /// <param name="buffer">
3706 /// buffer an array of bytes
3707 /// </param>
3708 void Update(byte[] buffer);
3709
3710 /// <summary>
3711 /// Adds the byte array to the data checksum.
3712 /// </summary>
3713 /// <param name = "buf">
3714 /// the buffer which contains the data
3715 /// </param>
3716 /// <param name = "off">
3717 /// the offset in the buffer where the data starts
3718 /// </param>
3719 /// <param name = "len">
3720 /// the length of the data
3721 /// </param>
3722 void Update(byte[] buf, int off, int len);
3723 }
3724 }
3725
3726 namespace NZlib.Streams {
3727
3728 /// <summary>
3729 /// Contains the output from the Inflation process.
3730 /// We need to have a window so that we can refer backwards into the output stream
3731 /// to repeat stuff.
3732 ///
3733 /// author of the original java version : John Leuner
3734 /// </summary>
3735 public class OutputWindow
3736 {
3737 private static int WINDOW_SIZE = 1 << 15;
3738 private static int WINDOW_MASK = WINDOW_SIZE - 1;
3739
3740 private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
3741 private int window_end = 0;
3742 private int window_filled = 0;
3743
3744 public void Write(int abyte)
3745 {
3746 if (window_filled++ == WINDOW_SIZE) {
3747 throw new InvalidOperationException("Window full");
3748 }
3749 window[window_end++] = (byte) abyte;
3750 window_end &= WINDOW_MASK;
3751 }
3752
3753
3754 private void SlowRepeat(int rep_start, int len, int dist)
3755 {
3756 while (len-- > 0) {
3757 window[window_end++] = window[rep_start++];
3758 window_end &= WINDOW_MASK;
3759 rep_start &= WINDOW_MASK;
3760 }
3761 }
3762
3763 public void Repeat(int len, int dist)
3764 {
3765 if ((window_filled += len) > WINDOW_SIZE) {
3766 throw new InvalidOperationException("Window full");
3767 }
3768
3769 int rep_start = (window_end - dist) & WINDOW_MASK;
3770 int border = WINDOW_SIZE - len;
3771 if (rep_start <= border && window_end < border) {
3772 if (len <= dist) {
3773 System.Array.Copy(window, rep_start, window, window_end, len);
3774 window_end += len;
3775 } else {
3776 /* We have to copy manually, since the repeat pattern overlaps.
3777 */
3778 while (len-- > 0) {
3779 window[window_end++] = window[rep_start++];
3780 }
3781 }
3782 } else {
3783 SlowRepeat(rep_start, len, dist);
3784 }
3785 }
3786
3787 public int CopyStored(StreamManipulator input, int len)
3788 {
3789 len = Math.Min(Math.Min(len, WINDOW_SIZE - window_filled), input.AvailableBytes);
3790 int copied;
3791
3792 int tailLen = WINDOW_SIZE - window_end;
3793 if (len > tailLen) {
3794 copied = input.CopyBytes(window, window_end, tailLen);
3795 if (copied == tailLen) {
3796 copied += input.CopyBytes(window, 0, len - tailLen);
3797 }
3798 } else {
3799 copied = input.CopyBytes(window, window_end, len);
3800 }
3801
3802 window_end = (window_end + copied) & WINDOW_MASK;
3803 window_filled += copied;
3804 return copied;
3805 }
3806
3807 public void CopyDict(byte[] dict, int offset, int len)
3808 {
3809 if (window_filled > 0) {
3810 throw new InvalidOperationException();
3811 }
3812
3813 if (len > WINDOW_SIZE) {
3814 offset += len - WINDOW_SIZE;
3815 len = WINDOW_SIZE;
3816 }
3817 System.Array.Copy(dict, offset, window, 0, len);
3818 window_end = len & WINDOW_MASK;
3819 }
3820
3821 public int GetFreeSpace()
3822 {
3823 return WINDOW_SIZE - window_filled;
3824 }
3825
3826 public int GetAvailable()
3827 {
3828 return window_filled;
3829 }
3830
3831 public int CopyOutput(byte[] output, int offset, int len)
3832 {
3833 int copy_end = window_end;
3834 if (len > window_filled) {
3835 len = window_filled;
3836 } else {
3837 copy_end = (window_end - window_filled + len) & WINDOW_MASK;
3838 }
3839
3840 int copied = len;
3841 int tailLen = len - copy_end;
3842
3843 if (tailLen > 0) {
3844 System.Array.Copy(window, WINDOW_SIZE - tailLen,
3845 output, offset, tailLen);
3846 offset += tailLen;
3847 len = copy_end;
3848 }
3849 System.Array.Copy(window, copy_end - len, output, offset, len);
3850 window_filled -= copied;
3851 if (window_filled < 0) {
3852 throw new InvalidOperationException();
3853 }
3854 return copied;
3855 }
3856
3857 public void Reset()
3858 {
3859 window_filled = window_end = 0;
3860 }
3861 }
3862 }
3863
3864 namespace NZlib.Streams {
3865
3866 /// <summary>
3867 /// This class allows us to retrieve a specified amount of bits from
3868 /// the input buffer, as well as copy big byte blocks.
3869 ///
3870 /// It uses an int buffer to store up to 31 bits for direct
3871 /// manipulation. This guarantees that we can get at least 16 bits,
3872 /// but we only need at most 15, so this is all safe.
3873 ///
3874 /// There are some optimizations in this class, for example, you must
3875 /// never peek more then 8 bits more than needed, and you must first
3876 /// peek bits before you may drop them. This is not a general purpose
3877 /// class but optimized for the behaviour of the Inflater.
3878 ///
3879 /// authors of the original java version : John Leuner, Jochen Hoenicke
3880 /// </summary>
3881 public class StreamManipulator
3882 {
3883 private byte[] window;
3884 private int window_start = 0;
3885 private int window_end = 0;
3886
3887 private uint buffer = 0;
3888 private int bits_in_buffer = 0;
3889
3890 /// <summary>
3891 /// Get the next n bits but don't increase input pointer. n must be
3892 /// less or equal 16 and if you if this call succeeds, you must drop
3893 /// at least n-8 bits in the next call.
3894 /// </summary>
3895 /// <returns>
3896 /// the value of the bits, or -1 if not enough bits available. */
3897 /// </returns>
3898 public int PeekBits(int n)
3899 {
3900 if (bits_in_buffer < n) {
3901 if (window_start == window_end) {
3902 return -1;
3903 }
3904 buffer |= (uint)((window[window_start++] & 0xff |
3905 (window[window_start++] & 0xff) << 8) << bits_in_buffer);
3906 bits_in_buffer += 16;
3907 }
3908 return (int)(buffer & ((1 << n) - 1));
3909 }
3910
3911 /// <summary>
3912 /// Drops the next n bits from the input. You should have called peekBits
3913 /// with a bigger or equal n before, to make sure that enough bits are in
3914 /// the bit buffer.
3915 /// </summary>
3916 public void DropBits(int n)
3917 {
3918 buffer >>= n;
3919 bits_in_buffer -= n;
3920 }
3921
3922 /// <summary>
3923 /// Gets the next n bits and increases input pointer. This is equivalent
3924 /// to peekBits followed by dropBits, except for correct error handling.
3925 /// </summary>
3926 /// <returns>
3927 /// the value of the bits, or -1 if not enough bits available.
3928 /// </returns>
3929 public int GetBits(int n)
3930 {
3931 int bits = PeekBits(n);
3932 if (bits >= 0) {
3933 DropBits(n);
3934 }
3935 return bits;
3936 }
3937
3938 /// <summary>
3939 /// Gets the number of bits available in the bit buffer. This must be
3940 /// only called when a previous peekBits() returned -1.
3941 /// </summary>
3942 /// <returns>
3943 /// the number of bits available.
3944 /// </returns>
3945 public int AvailableBits {
3946 get {
3947 return bits_in_buffer;
3948 }
3949 }
3950
3951 /// <summary>
3952 /// Gets the number of bytes available.
3953 /// </summary>
3954 /// <returns>
3955 /// the number of bytes available.
3956 /// </returns>
3957 public int AvailableBytes {
3958 get {
3959 return window_end - window_start + (bits_in_buffer >> 3);
3960 }
3961 }
3962
3963 /// <summary>
3964 /// Skips to the next byte boundary.
3965 /// </summary>
3966 public void SkipToByteBoundary()
3967 {
3968 buffer >>= (bits_in_buffer & 7);
3969 bits_in_buffer &= ~7;
3970 }
3971
3972 public bool IsNeedingInput {
3973 get {
3974 return window_start == window_end;
3975 }
3976 }
3977
3978 /// <summary>
3979 /// Copies length bytes from input buffer to output buffer starting
3980 /// at output[offset]. You have to make sure, that the buffer is
3981 /// byte aligned. If not enough bytes are available, copies fewer
3982 /// bytes.
3983 /// </summary>
3984 /// <param name="output">
3985 /// the buffer.
3986 /// </param>
3987 /// <param name="offset">
3988 /// the offset in the buffer.
3989 /// </param>
3990 /// <param name="length">
3991 /// the length to copy, 0 is allowed.
3992 /// </param>
3993 /// <returns>
3994 /// the number of bytes copied, 0 if no byte is available.
3995 /// </returns>
3996 public int CopyBytes(byte[] output, int offset, int length)
3997 {
3998 if (length < 0) {
3999 throw new ArgumentOutOfRangeException("length negative");
4000 }
4001 if ((bits_in_buffer & 7) != 0) {
4002 /* bits_in_buffer may only be 0 or 8 */
4003 throw new InvalidOperationException("Bit buffer is not aligned!");
4004 }
4005
4006 int count = 0;
4007 while (bits_in_buffer > 0 && length > 0) {
4008 output[offset++] = (byte) buffer;
4009 buffer >>= 8;
4010 bits_in_buffer -= 8;
4011 length--;
4012 count++;
4013 }
4014 if (length == 0) {
4015 return count;
4016 }
4017
4018 int avail = window_end - window_start;
4019 if (length > avail) {
4020 length = avail;
4021 }
4022 System.Array.Copy(window, window_start, output, offset, length);
4023 window_start += length;
4024
4025 if (((window_start - window_end) & 1) != 0) {
4026 /* We always want an even number of bytes in input, see peekBits */
4027 buffer = (uint)(window[window_start++] & 0xff);
4028 bits_in_buffer = 8;
4029 }
4030 return count + length;
4031 }
4032
4033 public StreamManipulator()
4034 {
4035 }
4036
4037 public void Reset()
4038 {
4039 buffer = (uint)(window_start = window_end = bits_in_buffer = 0);
4040 }
4041
4042 public void SetInput(byte[] buf, int off, int len)
4043 {
4044 if (window_start < window_end) {
4045 throw new InvalidOperationException("Old input was not completely processed");
4046 }
4047
4048 int end = off + len;
4049
4050 /* We want to throw an ArrayIndexOutOfBoundsException early. The
4051 * check is very tricky: it also handles integer wrap around.
4052 */
4053 if (0 > off || off > end || end > buf.Length) {
4054 throw new ArgumentOutOfRangeException();
4055 }
4056
4057 if ((len & 1) != 0) {
4058 /* We always want an even number of bytes in input, see peekBits */
4059 buffer |= (uint)((buf[off++] & 0xff) << bits_in_buffer);
4060 bits_in_buffer += 8;
4061 }
4062
4063 window = buf;
4064 window_start = off;
4065 window_end = end;
4066 }
4067 }
4068 }