2 // (This file is the NZipLib sources with a crude benchmark class attached -
\r
3 // 2002-15-05 Dan Lewis <dihlewis@yahoo.co.uk>)
\r
4 // -------------------------------------------------------------------------
\r
7 // Copyright (C) 2001 Mike Krueger
\r
9 // This file was translated from java, it was part of the GNU Classpath
\r
10 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
12 // This program is free software; you can redistribute it and/or
\r
13 // modify it under the terms of the GNU General Public License
\r
14 // as published by the Free Software Foundation; either version 2
\r
15 // of the License, or (at your option) any later version.
\r
17 // This program is distributed in the hope that it will be useful,
\r
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
20 // GNU General Public License for more details.
\r
22 // You should have received a copy of the GNU General Public License
\r
23 // along with this program; if not, write to the Free Software
\r
24 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
26 // As a special exception, if you link this library with other files to
\r
27 // produce an executable, this library does not by itself cause the
\r
28 // resulting executable to be covered by the GNU General Public License.
\r
29 // This exception does not however invalidate any other reasons why the
\r
30 // executable file might be covered by the GNU General Public License.
\r
34 using NZlib.Streams;
\r
35 using NZlib.Checksums;
\r
36 using NZlib.Compression;
\r
39 static int Iterations = 1000;
\r
40 static int BlockSize = 1024;
\r
42 public static void Main (string [] args)
\r
44 if (args.Length == 0 || args.Length > 3) {
\r
45 Console.WriteLine ("Usage: zipmark FILE [ITERATIONS] [BLOCKSIZE]");
\r
49 string filename = args [0];
\r
50 FileInfo file = new FileInfo (filename);
\r
52 Console.WriteLine ("Couldn't find file {0}", filename);
\r
56 FileStream fs = file.OpenRead ();
\r
58 byte [] raw = new byte [file.Length];
\r
59 int count = fs.Read (raw, 0, (int)file.Length);
\r
62 if (count != file.Length) {
\r
63 Console.WriteLine ("Couldn't read file {0}", filename);
\r
67 Deflater def = new Deflater (Deflater.BEST_COMPRESSION, false);
\r
68 Inflater inf = new Inflater (false);
\r
70 // 1. Count deflated size
\r
72 int cooked_size = Deflate (def, raw, null);
\r
73 byte [] cooked = new byte [cooked_size];
\r
75 // 2. Deflate & Inflate
\r
77 if (args.Length > 1)
\r
78 Iterations = Int32.Parse (args [1]);
\r
79 if (args.Length > 2)
\r
80 BlockSize = Int32.Parse (args [2]);
\r
82 for (int i = 0; i < Iterations; ++ i) {
\r
83 Deflate (def, raw, cooked);
\r
84 Inflate (inf, cooked, raw);
\r
90 static int Deflate (Deflater def, byte [] src, byte [] dest)
\r
93 int offset, length, remain;
\r
96 dest = new byte [BlockSize];
\r
102 def.SetInput (src);
\r
105 while (!def.IsFinished) {
\r
106 if (def.IsNeedingInput)
\r
109 remain = Math.Min (dest.Length - offset, BlockSize);
\r
113 length = def.Deflate (dest, offset, remain);
\r
118 return def.TotalOut;
\r
121 static int Inflate (Inflater inf, byte [] src, byte [] dest)
\r
123 int offset, length, remain;
\r
126 inf.SetInput (src);
\r
129 while (!inf.IsNeedingInput) {
\r
130 remain = Math.Min (dest.Length - offset, BlockSize);
\r
134 length = inf.Inflate (dest, offset, remain);
\r
138 return inf.TotalOut;
\r
142 // ---------------------- NZipLib sources from here on --------------------------
\r
144 namespace NZlib.Compression {
\r
147 /// This is the Deflater class. The deflater class compresses input
\r
148 /// with the deflate algorithm described in RFC 1951. It has several
\r
149 /// compression levels and three different strategies described below.
\r
151 /// This class is <i>not</i> thread safe. This is inherent in the API, due
\r
152 /// to the split of deflate and setInput.
\r
154 /// author of the original java version : Jochen Hoenicke
\r
156 public class Deflater
\r
159 /// The best and slowest compression level. This tries to find very
\r
160 /// long and distant string repetitions.
\r
162 public static int BEST_COMPRESSION = 9;
\r
165 /// The worst but fastest compression level.
\r
167 public static int BEST_SPEED = 1;
\r
170 /// The default compression level.
\r
172 public static int DEFAULT_COMPRESSION = -1;
\r
175 /// This level won't compress at all but output uncompressed blocks.
\r
177 public static int NO_COMPRESSION = 0;
\r
180 /// The default strategy.
\r
182 public static int DEFAULT_STRATEGY = 0;
\r
186 /// This strategy will only allow longer string repetitions. It is
\r
187 /// useful for random data with a small character set.
\r
189 public static int FILTERED = 1;
\r
192 /// This strategy will not look for string repetitions at all. It
\r
193 /// only encodes with Huffman trees (which means, that more common
\r
194 /// characters get a smaller encoding.
\r
196 public static int HUFFMAN_ONLY = 2;
\r
199 /// The compression method. This is the only method supported so far.
\r
200 /// There is no need to use this constant at all.
\r
202 public static int DEFLATED = 8;
\r
205 * The Deflater can do the following state transitions:
\r
207 * (1) -> INIT_STATE ----> INIT_FINISHING_STATE ---.
\r
210 * (3)| SETDICT_STATE ---> SETDICT_FINISHING_STATE |(3)
\r
211 * \ | (3) | ,-------'
\r
214 * (1) -> BUSY_STATE ----> FINISHING_STATE
\r
218 * \_____________________________________/
\r
223 * (1) If we should produce a header we start in INIT_STATE, otherwise
\r
224 * we start in BUSY_STATE.
\r
225 * (2) A dictionary may be set only when we are in INIT_STATE, then
\r
226 * we change the state as indicated.
\r
227 * (3) Whether a dictionary is set or not, on the first call of deflate
\r
228 * we change to BUSY_STATE.
\r
229 * (4) -- intentionally left blank -- :)
\r
230 * (5) FINISHING_STATE is entered, when flush() is called to indicate that
\r
231 * there is no more INPUT. There are also states indicating, that
\r
232 * the header wasn't written yet.
\r
233 * (6) FINISHED_STATE is entered, when everything has been flushed to the
\r
234 * internal pending output buffer.
\r
235 * (7) At any time (7)
\r
239 private static int IS_SETDICT = 0x01;
\r
240 private static int IS_FLUSHING = 0x04;
\r
241 private static int IS_FINISHING = 0x08;
\r
243 private static int INIT_STATE = 0x00;
\r
244 private static int SETDICT_STATE = 0x01;
\r
245 // private static int INIT_FINISHING_STATE = 0x08;
\r
246 // private static int SETDICT_FINISHING_STATE = 0x09;
\r
247 private static int BUSY_STATE = 0x10;
\r
248 private static int FLUSHING_STATE = 0x14;
\r
249 private static int FINISHING_STATE = 0x1c;
\r
250 private static int FINISHED_STATE = 0x1e;
\r
251 private static int CLOSED_STATE = 0x7f;
\r
254 /// Compression level.
\r
259 /// should we include a header.
\r
261 private bool noHeader;
\r
264 // /// Compression strategy.
\r
266 // private int strategy;
\r
269 /// The current state.
\r
274 /// The total bytes of output written.
\r
276 private int totalOut;
\r
279 /// The pending output.
\r
281 private DeflaterPending pending;
\r
284 /// The deflater engine.
\r
286 private DeflaterEngine engine;
\r
289 /// Creates a new deflater with default compression level.
\r
291 public Deflater() : this(DEFAULT_COMPRESSION, false)
\r
297 /// Creates a new deflater with given compression level.
\r
299 /// <param name="lvl">
\r
300 /// the compression level, a value between NO_COMPRESSION
\r
301 /// and BEST_COMPRESSION, or DEFAULT_COMPRESSION.
\r
303 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
\r
304 public Deflater(int lvl) : this(lvl, false)
\r
310 /// Creates a new deflater with given compression level.
\r
312 /// <param name="lvl">
\r
313 /// the compression level, a value between NO_COMPRESSION
\r
314 /// and BEST_COMPRESSION.
\r
316 /// <param name="nowrap">
\r
317 /// true, if we should suppress the deflate header at the
\r
318 /// beginning and the adler checksum at the end of the output. This is
\r
319 /// useful for the GZIP format.
\r
321 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
\r
322 public Deflater(int lvl, bool nowrap)
\r
324 if (lvl == DEFAULT_COMPRESSION) {
\r
326 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
\r
327 throw new ArgumentOutOfRangeException("lvl");
\r
330 pending = new DeflaterPending();
\r
331 engine = new DeflaterEngine(pending);
\r
332 this.noHeader = nowrap;
\r
333 SetStrategy(DEFAULT_STRATEGY);
\r
340 /// Resets the deflater. The deflater acts afterwards as if it was
\r
341 /// just created with the same compression level and strategy as it
\r
344 public void Reset()
\r
346 state = (noHeader ? BUSY_STATE : INIT_STATE);
\r
353 /// Gets the current adler checksum of the data that was processed so far.
\r
357 return engine.Adler;
\r
362 /// Gets the number of input bytes processed so far.
\r
364 public int TotalIn {
\r
366 return engine.TotalIn;
\r
371 /// Gets the number of output bytes so far.
\r
373 public int TotalOut {
\r
380 /// Flushes the current input block. Further calls to deflate() will
\r
381 /// produce enough output to inflate everything in the current input
\r
382 /// block. This is not part of Sun's JDK so I have made it package
\r
383 /// private. It is used by DeflaterOutputStream to implement
\r
386 public void Flush()
\r
388 state |= IS_FLUSHING;
\r
392 /// Finishes the deflater with the current input block. It is an error
\r
393 /// to give more input after this method was called. This method must
\r
394 /// be called to force all bytes to be flushed.
\r
396 public void Finish()
\r
398 state |= IS_FLUSHING | IS_FINISHING;
\r
402 /// Returns true if the stream was finished and no more output bytes
\r
405 public bool IsFinished {
\r
407 return state == FINISHED_STATE && pending.IsFlushed;
\r
412 /// Returns true, if the input buffer is empty.
\r
413 /// You should then call setInput().
\r
414 /// NOTE: This method can also return true when the stream
\r
417 public bool IsNeedingInput {
\r
419 return engine.NeedsInput();
\r
424 /// Sets the data which should be compressed next. This should be only
\r
425 /// called when needsInput indicates that more input is needed.
\r
426 /// If you call setInput when needsInput() returns false, the
\r
427 /// previous input that is still pending will be thrown away.
\r
428 /// The given byte array should not be changed, before needsInput() returns
\r
430 /// This call is equivalent to <code>setInput(input, 0, input.length)</code>.
\r
432 /// <param name="input">
\r
433 /// the buffer containing the input data.
\r
435 /// <exception cref="System.InvalidOperationException">
\r
436 /// if the buffer was finished() or ended().
\r
438 public void SetInput(byte[] input)
\r
440 SetInput(input, 0, input.Length);
\r
444 /// Sets the data which should be compressed next. This should be
\r
445 /// only called when needsInput indicates that more input is needed.
\r
446 /// The given byte array should not be changed, before needsInput() returns
\r
449 /// <param name="input">
\r
450 /// the buffer containing the input data.
\r
452 /// <param name="off">
\r
453 /// the start of the data.
\r
455 /// <param name="len">
\r
456 /// the length of the data.
\r
458 /// <exception cref="System.InvalidOperationException">
\r
459 /// if the buffer was finished() or ended() or if previous input is still pending.
\r
461 public void SetInput(byte[] input, int off, int len)
\r
463 if ((state & IS_FINISHING) != 0) {
\r
464 throw new InvalidOperationException("finish()/end() already called");
\r
466 engine.SetInput(input, off, len);
\r
470 /// Sets the compression level. There is no guarantee of the exact
\r
471 /// position of the change, but if you call this when needsInput is
\r
472 /// true the change of compression level will occur somewhere near
\r
473 /// before the end of the so far given input.
\r
475 /// <param name="lvl">
\r
476 /// the new compression level.
\r
478 public void SetLevel(int lvl)
\r
480 if (lvl == DEFAULT_COMPRESSION) {
\r
482 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
\r
483 throw new ArgumentOutOfRangeException("lvl");
\r
487 if (level != lvl) {
\r
489 engine.SetLevel(lvl);
\r
494 /// Sets the compression strategy. Strategy is one of
\r
495 /// DEFAULT_STRATEGY, HUFFMAN_ONLY and FILTERED. For the exact
\r
496 /// position where the strategy is changed, the same as for
\r
497 /// setLevel() applies.
\r
499 /// <param name="stgy">
\r
500 /// the new compression strategy.
\r
502 public void SetStrategy(int stgy)
\r
504 if (stgy != DEFAULT_STRATEGY && stgy != FILTERED && stgy != HUFFMAN_ONLY) {
\r
505 throw new Exception();
\r
507 engine.Strategy = stgy;
\r
511 /// Deflates the current input block to the given array. It returns
\r
512 /// the number of bytes compressed, or 0 if either
\r
513 /// needsInput() or finished() returns true or length is zero.
\r
515 /// <param name="output">
\r
516 /// the buffer where to write the compressed data.
\r
518 public int Deflate(byte[] output)
\r
520 return Deflate(output, 0, output.Length);
\r
524 /// Deflates the current input block to the given array. It returns
\r
525 /// the number of bytes compressed, or 0 if either
\r
526 /// needsInput() or finished() returns true or length is zero.
\r
528 /// <param name="output">
\r
529 /// the buffer where to write the compressed data.
\r
531 /// <param name="offset">
\r
532 /// the offset into the output array.
\r
534 /// <param name="length">
\r
535 /// the maximum number of bytes that may be written.
\r
537 /// <exception cref="System.InvalidOperationException">
\r
538 /// if end() was called.
\r
540 /// <exception cref="System.ArgumentOutOfRangeException">
\r
541 /// if offset and/or length don't match the array length.
\r
543 public int Deflate(byte[] output, int offset, int length)
\r
545 int origLength = length;
\r
547 if (state == CLOSED_STATE) {
\r
548 throw new InvalidOperationException("Deflater closed");
\r
551 if (state < BUSY_STATE) {
\r
552 /* output header */
\r
553 int header = (DEFLATED +
\r
554 ((DeflaterConstants.MAX_WBITS - 8) << 4)) << 8;
\r
555 int level_flags = (level - 1) >> 1;
\r
556 if (level_flags < 0 || level_flags > 3) {
\r
559 header |= level_flags << 6;
\r
560 if ((state & IS_SETDICT) != 0) {
\r
561 /* Dictionary was set */
\r
562 header |= DeflaterConstants.PRESET_DICT;
\r
564 header += 31 - (header % 31);
\r
567 pending.WriteShortMSB(header);
\r
568 if ((state & IS_SETDICT) != 0) {
\r
569 int chksum = engine.Adler;
\r
570 engine.ResetAdler();
\r
571 pending.WriteShortMSB(chksum >> 16);
\r
572 pending.WriteShortMSB(chksum & 0xffff);
\r
575 state = BUSY_STATE | (state & (IS_FLUSHING | IS_FINISHING));
\r
579 int count = pending.Flush(output, offset, length);
\r
584 if (length == 0 || state == FINISHED_STATE) {
\r
588 if (!engine.Deflate((state & IS_FLUSHING) != 0, (state & IS_FINISHING) != 0)) {
\r
589 if (state == BUSY_STATE) {
\r
590 /* We need more input now */
\r
591 return origLength - length;
\r
592 } else if (state == FLUSHING_STATE) {
\r
593 if (level != NO_COMPRESSION) {
\r
594 /* We have to supply some lookahead. 8 bit lookahead
\r
595 * are needed by the zlib inflater, and we must fill
\r
596 * the next byte, so that all bits are flushed.
\r
598 int neededbits = 8 + ((-pending.BitCount) & 7);
\r
599 while (neededbits > 0) {
\r
600 /* write a static tree block consisting solely of
\r
603 pending.WriteBits(2, 10);
\r
607 state = BUSY_STATE;
\r
608 } else if (state == FINISHING_STATE) {
\r
609 pending.AlignToByte();
\r
610 /* We have completed the stream */
\r
612 int adler = engine.Adler;
\r
613 pending.WriteShortMSB(adler >> 16);
\r
614 pending.WriteShortMSB(adler & 0xffff);
\r
616 state = FINISHED_STATE;
\r
620 return origLength - length;
\r
624 /// Sets the dictionary which should be used in the deflate process.
\r
625 /// This call is equivalent to <code>setDictionary(dict, 0, dict.Length)</code>.
\r
627 /// <param name="dict">
\r
628 /// the dictionary.
\r
630 /// <exception cref="System.InvalidOperationException">
\r
631 /// if setInput () or deflate () were already called or another dictionary was already set.
\r
633 public void SetDictionary(byte[] dict)
\r
635 SetDictionary(dict, 0, dict.Length);
\r
639 /// Sets the dictionary which should be used in the deflate process.
\r
640 /// The dictionary should be a byte array containing strings that are
\r
641 /// likely to occur in the data which should be compressed. The
\r
642 /// dictionary is not stored in the compressed output, only a
\r
643 /// checksum. To decompress the output you need to supply the same
\r
644 /// dictionary again.
\r
646 /// <param name="dict">
\r
647 /// the dictionary.
\r
649 /// <param name="offset">
\r
650 /// an offset into the dictionary.
\r
652 /// <param name="length">
\r
653 /// the length of the dictionary.
\r
655 /// <exception cref="System.InvalidOperationException">
\r
656 /// if setInput () or deflate () were already called or another dictionary was already set.
\r
658 public void SetDictionary(byte[] dict, int offset, int length)
\r
660 if (state != INIT_STATE) {
\r
661 throw new InvalidOperationException();
\r
664 state = SETDICT_STATE;
\r
665 engine.SetDictionary(dict, offset, length);
\r
670 namespace NZlib.Compression {
\r
673 /// This class contains constants used for the deflater.
\r
675 public class DeflaterConstants
\r
677 public const bool DEBUGGING = false;
\r
679 public const int STORED_BLOCK = 0;
\r
680 public const int STATIC_TREES = 1;
\r
681 public const int DYN_TREES = 2;
\r
682 public const int PRESET_DICT = 0x20;
\r
684 public const int DEFAULT_MEM_LEVEL = 8;
\r
686 public const int MAX_MATCH = 258;
\r
687 public const int MIN_MATCH = 3;
\r
689 public const int MAX_WBITS = 15;
\r
690 public const int WSIZE = 1 << MAX_WBITS;
\r
691 public const int WMASK = WSIZE - 1;
\r
693 public const int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
\r
694 public const int HASH_SIZE = 1 << HASH_BITS;
\r
695 public const int HASH_MASK = HASH_SIZE - 1;
\r
696 public const int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
\r
698 public const int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
\r
699 public const int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
\r
701 public const int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
\r
702 public static int MAX_BLOCK_SIZE = Math.Min(65535, PENDING_BUF_SIZE-5);
\r
704 public const int DEFLATE_STORED = 0;
\r
705 public const int DEFLATE_FAST = 1;
\r
706 public const int DEFLATE_SLOW = 2;
\r
708 public static int[] GOOD_LENGTH = { 0, 4, 4, 4, 4, 8, 8, 8, 32, 32 };
\r
709 public static int[] MAX_LAZY = { 0, 4, 5, 6, 4,16, 16, 32, 128, 258 };
\r
710 public static int[] NICE_LENGTH = { 0, 8,16,32,16,32,128,128, 258, 258 };
\r
711 public static int[] MAX_CHAIN = { 0, 4, 8,32,16,32,128,256,1024,4096 };
\r
712 public static int[] COMPR_FUNC = { 0, 1, 1, 1, 1, 2, 2, 2, 2, 2 };
\r
716 namespace NZlib.Compression {
\r
718 public class DeflaterEngine : DeflaterConstants
\r
720 private static int TOO_FAR = 4096;
\r
723 // private byte[] buffer;
\r
724 private short[] head;
\r
725 private short[] prev;
\r
727 private int matchStart, matchLen;
\r
728 private bool prevAvailable;
\r
729 private int blockStart;
\r
730 private int strstart, lookahead;
\r
731 private byte[] window;
\r
733 private int strategy, max_chain, max_lazy, niceLength, goodLength;
\r
736 /// The current compression function.
\r
738 private int comprFunc;
\r
741 /// The input data for compression.
\r
743 private byte[] inputBuf;
\r
746 /// The total bytes of input read.
\r
748 private int totalIn;
\r
751 /// The offset into inputBuf, where input data starts.
\r
753 private int inputOff;
\r
756 /// The end offset of the input data.
\r
758 private int inputEnd;
\r
760 private DeflaterPending pending;
\r
761 private DeflaterHuffman huffman;
\r
764 /// The adler checksum
\r
766 private Adler32 adler;
\r
768 public DeflaterEngine(DeflaterPending pending)
\r
770 this.pending = pending;
\r
771 huffman = new DeflaterHuffman(pending);
\r
772 adler = new Adler32();
\r
774 window = new byte[2*WSIZE];
\r
775 head = new short[HASH_SIZE];
\r
776 prev = new short[WSIZE];
\r
778 /* We start at index 1, to avoid a implementation deficiency, that
\r
779 * we cannot build a repeat pattern at index 0.
\r
781 blockStart = strstart = 1;
\r
784 public void Reset()
\r
788 blockStart = strstart = 1;
\r
791 prevAvailable = false;
\r
792 matchLen = MIN_MATCH - 1;
\r
794 for (int i = 0; i < HASH_SIZE; i++) {
\r
798 for (int i = 0; i < WSIZE; i++) {
\r
803 public void ResetAdler()
\r
810 return (int)adler.Value;
\r
814 public int TotalIn {
\r
820 public int Strategy {
\r
829 public void SetLevel(int lvl)
\r
831 goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
\r
832 max_lazy = DeflaterConstants.MAX_LAZY[lvl];
\r
833 niceLength = DeflaterConstants.NICE_LENGTH[lvl];
\r
834 max_chain = DeflaterConstants.MAX_CHAIN[lvl];
\r
836 if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
\r
837 // if (DeflaterConstants.DEBUGGING) {
\r
838 // Console.WriteLine("Change from "+comprFunc +" to "
\r
839 // + DeflaterConstants.COMPR_FUNC[lvl]);
\r
841 switch (comprFunc) {
\r
842 case DEFLATE_STORED:
\r
843 if (strstart > blockStart) {
\r
844 huffman.FlushStoredBlock(window, blockStart,
\r
845 strstart - blockStart, false);
\r
846 blockStart = strstart;
\r
851 if (strstart > blockStart) {
\r
852 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
854 blockStart = strstart;
\r
858 if (prevAvailable) {
\r
859 huffman.TallyLit(window[strstart-1] & 0xff);
\r
861 if (strstart > blockStart) {
\r
862 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
864 blockStart = strstart;
\r
866 prevAvailable = false;
\r
867 matchLen = MIN_MATCH - 1;
\r
870 comprFunc = COMPR_FUNC[lvl];
\r
874 private void UpdateHash()
\r
876 // if (DEBUGGING) {
\r
877 // Console.WriteLine("updateHash: "+strstart);
\r
879 ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
\r
882 private int InsertString()
\r
885 int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
\r
887 // if (DEBUGGING) {
\r
888 // if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
\r
889 // (window[strstart + 1] << HASH_SHIFT) ^
\r
890 // (window[strstart + 2])) & HASH_MASK)) {
\r
891 // throw new Exception("hash inconsistent: "+hash+"/"
\r
892 // +window[strstart]+","
\r
893 // +window[strstart+1]+","
\r
894 // +window[strstart+2]+","+HASH_SHIFT);
\r
898 prev[strstart & WMASK] = match = head[hash];
\r
899 head[hash] = (short)strstart;
\r
901 return match & 0xffff;
\r
904 public void FillWindow()
\r
906 while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
\r
907 int more = 2*WSIZE - lookahead - strstart;
\r
909 /* If the window is almost full and there is insufficient lookahead,
\r
910 * move the upper half to the lower one to make room in the upper half.
\r
912 if (strstart >= WSIZE + MAX_DIST) {
\r
913 System.Array.Copy(window, WSIZE, window, 0, WSIZE);
\r
914 matchStart -= WSIZE;
\r
916 blockStart -= WSIZE;
\r
918 /* Slide the hash table (could be avoided with 32 bit values
\r
919 * at the expense of memory usage).
\r
921 for (int i = 0; i < HASH_SIZE; i++) {
\r
923 head[i] = m >= WSIZE ? (short) (m - WSIZE) : (short)0;
\r
928 if (more > inputEnd - inputOff) {
\r
929 more = inputEnd - inputOff;
\r
932 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
\r
933 adler.Update(inputBuf, inputOff, more);
\r
938 if (lookahead >= MIN_MATCH) {
\r
944 private bool FindLongestMatch(int curMatch)
\r
946 int chainLength = this.max_chain;
\r
947 int niceLength = this.niceLength;
\r
948 short[] prev = this.prev;
\r
949 int scan = this.strstart;
\r
951 int best_end = this.strstart + matchLen;
\r
952 int best_len = Math.Max(matchLen, MIN_MATCH - 1);
\r
954 int limit = Math.Max(strstart - MAX_DIST, 0);
\r
956 int strend = strstart + MAX_MATCH - 1;
\r
957 byte scan_end1 = window[best_end - 1];
\r
958 byte scan_end = window[best_end];
\r
960 /* Do not waste too much time if we already have a good match: */
\r
961 if (best_len >= this.goodLength) {
\r
965 /* Do not look for matches beyond the end of the input. This is necessary
\r
966 * to make deflate deterministic.
\r
968 if (niceLength > lookahead) {
\r
969 niceLength = lookahead;
\r
972 if (DeflaterConstants.DEBUGGING && strstart > 2*WSIZE - MIN_LOOKAHEAD) {
\r
973 throw new InvalidOperationException("need lookahead");
\r
977 if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
\r
978 throw new InvalidOperationException("future match");
\r
980 if (window[curMatch + best_len] != scan_end ||
\r
981 window[curMatch + best_len - 1] != scan_end1 ||
\r
982 window[curMatch] != window[scan] ||
\r
983 window[curMatch+1] != window[scan + 1]) {
\r
987 match = curMatch + 2;
\r
990 /* We check for insufficient lookahead only every 8th comparison;
\r
991 * the 256th check will be made at strstart+258.
\r
993 while (window[++scan] == window[++match] &&
\r
994 window[++scan] == window[++match] &&
\r
995 window[++scan] == window[++match] &&
\r
996 window[++scan] == window[++match] &&
\r
997 window[++scan] == window[++match] &&
\r
998 window[++scan] == window[++match] &&
\r
999 window[++scan] == window[++match] &&
\r
1000 window[++scan] == window[++match] && scan < strend) ;
\r
1002 if (scan > best_end) {
\r
1003 // if (DeflaterConstants.DEBUGGING && ins_h == 0)
\r
1004 // System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
\r
1005 matchStart = curMatch;
\r
1007 best_len = scan - strstart;
\r
1008 if (best_len >= niceLength) {
\r
1012 scan_end1 = window[best_end-1];
\r
1013 scan_end = window[best_end];
\r
1016 } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
\r
1018 matchLen = Math.Min(best_len, lookahead);
\r
1019 return matchLen >= MIN_MATCH;
\r
1022 public void SetDictionary(byte[] buffer, int offset, int length)
\r
1024 if (DeflaterConstants.DEBUGGING && strstart != 1) {
\r
1025 throw new InvalidOperationException("strstart not 1");
\r
1027 adler.Update(buffer, offset, length);
\r
1028 if (length < MIN_MATCH) {
\r
1031 if (length > MAX_DIST) {
\r
1032 offset += length - MAX_DIST;
\r
1033 length = MAX_DIST;
\r
1036 System.Array.Copy(buffer, offset, window, strstart, length);
\r
1040 while (--length > 0) {
\r
1045 blockStart = strstart;
\r
1048 private bool DeflateStored(bool flush, bool finish)
\r
1050 if (!flush && lookahead == 0) {
\r
1054 strstart += lookahead;
\r
1057 int storedLen = strstart - blockStart;
\r
1059 if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
\r
1060 (blockStart < WSIZE && storedLen >= MAX_DIST) || /* Block may move out of window */
\r
1062 bool lastBlock = finish;
\r
1063 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
\r
1064 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
\r
1065 lastBlock = false;
\r
1068 // if (DeflaterConstants.DEBUGGING) {
\r
1069 // Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
\r
1072 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
\r
1073 blockStart += storedLen;
\r
1074 return !lastBlock;
\r
1079 private bool DeflateFast(bool flush, bool finish)
\r
1081 if (lookahead < MIN_LOOKAHEAD && !flush) {
\r
1085 while (lookahead >= MIN_LOOKAHEAD || flush) {
\r
1086 if (lookahead == 0) {
\r
1087 /* We are flushing everything */
\r
1088 huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
\r
1089 blockStart = strstart;
\r
1094 if (lookahead >= MIN_MATCH &&
\r
1095 (hashHead = InsertString()) != 0 &&
\r
1096 strategy != Deflater.HUFFMAN_ONLY &&
\r
1097 strstart - hashHead <= MAX_DIST &&
\r
1098 FindLongestMatch(hashHead)) {
\r
1099 /* longestMatch sets matchStart and matchLen */
\r
1100 // if (DeflaterConstants.DEBUGGING) {
\r
1101 // for (int i = 0 ; i < matchLen; i++) {
\r
1102 // if (window[strstart+i] != window[matchStart + i]) {
\r
1103 // throw new Exception();
\r
1108 huffman.TallyDist(strstart - matchStart, matchLen);
\r
1110 lookahead -= matchLen;
\r
1111 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
\r
1112 while (--matchLen > 0) {
\r
1118 strstart += matchLen;
\r
1119 if (lookahead >= MIN_MATCH - 1) {
\r
1123 matchLen = MIN_MATCH - 1;
\r
1126 /* No match found */
\r
1127 huffman.TallyLit(window[strstart] & 0xff);
\r
1132 if (huffman.IsFull()) {
\r
1133 bool lastBlock = finish && lookahead == 0;
\r
1134 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
1136 blockStart = strstart;
\r
1137 return !lastBlock;
\r
1143 private bool DeflateSlow(bool flush, bool finish)
\r
1145 if (lookahead < MIN_LOOKAHEAD && !flush) {
\r
1149 while (lookahead >= MIN_LOOKAHEAD || flush) {
\r
1150 if (lookahead == 0) {
\r
1151 if (prevAvailable) {
\r
1152 huffman.TallyLit(window[strstart-1] & 0xff);
\r
1154 prevAvailable = false;
\r
1156 /* We are flushing everything */
\r
1157 if (DeflaterConstants.DEBUGGING && !flush) {
\r
1158 throw new Exception("Not flushing, but no lookahead");
\r
1160 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
1162 blockStart = strstart;
\r
1166 int prevMatch = matchStart;
\r
1167 int prevLen = matchLen;
\r
1168 if (lookahead >= MIN_MATCH) {
\r
1169 int hashHead = InsertString();
\r
1170 if (strategy != Deflater.HUFFMAN_ONLY && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead))
\r
1172 /* longestMatch sets matchStart and matchLen */
\r
1174 /* Discard match if too small and too far away */
\r
1175 if (matchLen <= 5 && (strategy == Deflater.FILTERED || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
\r
1176 matchLen = MIN_MATCH - 1;
\r
1181 /* previous match was better */
\r
1182 if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
\r
1183 // if (DeflaterConstants.DEBUGGING) {
\r
1184 // for (int i = 0 ; i < matchLen; i++) {
\r
1185 // if (window[strstart-1+i] != window[prevMatch + i])
\r
1186 // throw new Exception();
\r
1189 huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
\r
1194 if (lookahead >= MIN_MATCH) {
\r
1197 } while (--prevLen > 0);
\r
1200 prevAvailable = false;
\r
1201 matchLen = MIN_MATCH - 1;
\r
1203 if (prevAvailable) {
\r
1204 huffman.TallyLit(window[strstart-1] & 0xff);
\r
1206 prevAvailable = true;
\r
1211 if (huffman.IsFull()) {
\r
1212 int len = strstart - blockStart;
\r
1213 if (prevAvailable) {
\r
1216 bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
\r
1217 huffman.FlushBlock(window, blockStart, len, lastBlock);
\r
1218 blockStart += len;
\r
1219 return !lastBlock;
\r
1225 public bool Deflate(bool flush, bool finish)
\r
1230 bool canFlush = flush && inputOff == inputEnd;
\r
1231 // if (DeflaterConstants.DEBUGGING) {
\r
1232 // Console.WriteLine("window: ["+blockStart+","+strstart+","
\r
1233 // +lookahead+"], "+comprFunc+","+canFlush);
\r
1235 switch (comprFunc) {
\r
1236 case DEFLATE_STORED:
\r
1237 progress = DeflateStored(canFlush, finish);
\r
1239 case DEFLATE_FAST:
\r
1240 progress = DeflateFast(canFlush, finish);
\r
1242 case DEFLATE_SLOW:
\r
1243 progress = DeflateSlow(canFlush, finish);
\r
1246 throw new InvalidOperationException("unknown comprFunc");
\r
1248 } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
\r
1252 public void SetInput(byte[] buf, int off, int len)
\r
1254 if (inputOff < inputEnd) {
\r
1255 throw new InvalidOperationException("Old input was not completely processed");
\r
1258 int end = off + len;
\r
1260 /* We want to throw an ArrayIndexOutOfBoundsException early. The
\r
1261 * check is very tricky: it also handles integer wrap around.
\r
1263 if (0 > off || off > end || end > buf.Length) {
\r
1264 throw new ArgumentOutOfRangeException();
\r
1272 public bool NeedsInput()
\r
1274 return inputEnd == inputOff;
\r
1279 namespace NZlib.Compression {
\r
1282 /// This is the DeflaterHuffman class.
\r
1284 /// This class is <i>not</i> thread safe. This is inherent in the API, due
\r
1285 /// to the split of deflate and setInput.
\r
1287 /// author of the original java version : Jochen Hoenicke
\r
1289 public class DeflaterHuffman
\r
1291 private static int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
\r
1292 private static int LITERAL_NUM = 286;
\r
1293 private static int DIST_NUM = 30;
\r
1294 private static int BITLEN_NUM = 19;
\r
1295 private static int REP_3_6 = 16;
\r
1296 private static int REP_3_10 = 17;
\r
1297 private static int REP_11_138 = 18;
\r
1298 private static int EOF_SYMBOL = 256;
\r
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 };
\r
1301 private static byte[] bit4Reverse = {
\r
1321 public class Tree
\r
1323 public short[] freqs;
\r
1324 public short[] codes;
\r
1325 public byte[] length;
\r
1326 public int[] bl_counts;
\r
1327 public int minNumCodes, numCodes;
\r
1328 public int maxLength;
\r
1329 DeflaterHuffman dh;
\r
1331 public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
\r
1334 this.minNumCodes = minCodes;
\r
1335 this.maxLength = maxLength;
\r
1336 freqs = new short[elems];
\r
1337 bl_counts = new int[maxLength];
\r
1340 public void Reset()
\r
1342 for (int i = 0; i < freqs.Length; i++) {
\r
1349 public void WriteSymbol(int code)
\r
1351 // if (DeflaterConstants.DEBUGGING) {
\r
1353 // // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
\r
1355 dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
\r
1358 public void CheckEmpty()
\r
1360 bool empty = true;
\r
1361 for (int i = 0; i < freqs.Length; i++) {
\r
1362 if (freqs[i] != 0) {
\r
1363 Console.WriteLine("freqs["+i+"] == "+freqs[i]);
\r
1368 throw new Exception();
\r
1370 Console.WriteLine("checkEmpty suceeded!");
\r
1373 public void SetStaticCodes(short[] stCodes, byte[] stLength)
\r
1376 length = stLength;
\r
1379 public void BuildCodes()
\r
1381 int numSymbols = freqs.Length;
\r
1382 int[] nextCode = new int[maxLength];
\r
1384 codes = new short[freqs.Length];
\r
1386 // if (DeflaterConstants.DEBUGGING) {
\r
1387 // Console.WriteLine("buildCodes: "+freqs.Length);
\r
1390 for (int bits = 0; bits < maxLength; bits++) {
\r
1391 nextCode[bits] = code;
\r
1392 code += bl_counts[bits] << (15 - bits);
\r
1393 // if (DeflaterConstants.DEBUGGING) {
\r
1394 // Console.WriteLine("bits: "+(bits+1)+" count: "+bl_counts[bits]
\r
1395 // +" nextCode: "+code); // HACK : Integer.toHexString(
\r
1398 if (DeflaterConstants.DEBUGGING && code != 65536) {
\r
1399 throw new Exception("Inconsistent bl_counts!");
\r
1402 for (int i=0; i < numCodes; i++) {
\r
1403 int bits = length[i];
\r
1405 // if (DeflaterConstants.DEBUGGING) {
\r
1406 // Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+")," // HACK : Integer.toHexString(
\r
1409 codes[i] = BitReverse(nextCode[bits-1]);
\r
1410 nextCode[bits-1] += 1 << (16 - bits);
\r
1415 private void BuildLength(int[] childs)
\r
1417 this.length = new byte [freqs.Length];
\r
1418 int numNodes = childs.Length / 2;
\r
1419 int numLeafs = (numNodes + 1) / 2;
\r
1422 for (int i = 0; i < maxLength; i++) {
\r
1426 /* First calculate optimal bit lengths */
\r
1427 int[] lengths = new int[numNodes];
\r
1428 lengths[numNodes-1] = 0;
\r
1430 for (int i = numNodes - 1; i >= 0; i--) {
\r
1431 if (childs[2*i+1] != -1) {
\r
1432 int bitLength = lengths[i] + 1;
\r
1433 if (bitLength > maxLength) {
\r
1434 bitLength = maxLength;
\r
1437 lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
\r
1440 int bitLength = lengths[i];
\r
1441 bl_counts[bitLength - 1]++;
\r
1442 this.length[childs[2*i]] = (byte) lengths[i];
\r
1446 // if (DeflaterConstants.DEBUGGING) {
\r
1447 // Console.WriteLine("Tree "+freqs.Length+" lengths:");
\r
1448 // for (int i=0; i < numLeafs; i++) {
\r
1449 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
\r
1450 // + " len: "+length[childs[2*i]]);
\r
1454 if (overflow == 0) {
\r
1458 int incrBitLen = maxLength - 1;
\r
1460 /* Find the first bit length which could increase: */
\r
1461 while (bl_counts[--incrBitLen] == 0)
\r
1464 /* Move this node one down and remove a corresponding
\r
1465 * amount of overflow nodes.
\r
1468 bl_counts[incrBitLen]--;
\r
1469 bl_counts[++incrBitLen]++;
\r
1470 overflow -= 1 << (maxLength - 1 - incrBitLen);
\r
1471 } while (overflow > 0 && incrBitLen < maxLength - 1);
\r
1472 } while (overflow > 0);
\r
1474 /* We may have overshot above. Move some nodes from maxLength to
\r
1475 * maxLength-1 in that case.
\r
1477 bl_counts[maxLength-1] += overflow;
\r
1478 bl_counts[maxLength-2] -= overflow;
\r
1480 /* Now recompute all bit lengths, scanning in increasing
\r
1481 * frequency. It is simpler to reconstruct all lengths instead of
\r
1482 * fixing only the wrong ones. This idea is taken from 'ar'
\r
1483 * written by Haruhiko Okumura.
\r
1485 * The nodes were inserted with decreasing frequency into the childs
\r
1488 int nodePtr = 2 * numLeafs;
\r
1489 for (int bits = maxLength; bits != 0; bits--) {
\r
1490 int n = bl_counts[bits-1];
\r
1492 int childPtr = 2*childs[nodePtr++];
\r
1493 if (childs[childPtr + 1] == -1) {
\r
1494 /* We found another leaf */
\r
1495 length[childs[childPtr]] = (byte) bits;
\r
1500 // if (DeflaterConstants.DEBUGGING) {
\r
1501 // Console.WriteLine("*** After overflow elimination. ***");
\r
1502 // for (int i=0; i < numLeafs; i++) {
\r
1503 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
\r
1504 // + " len: "+length[childs[2*i]]);
\r
1509 public void BuildTree()
\r
1511 int numSymbols = freqs.Length;
\r
1513 /* heap is a priority queue, sorted by frequency, least frequent
\r
1514 * nodes first. The heap is a binary tree, with the property, that
\r
1515 * the parent node is smaller than both child nodes. This assures
\r
1516 * that the smallest node is the first parent.
\r
1518 * The binary tree is encoded in an array: 0 is root node and
\r
1519 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
\r
1521 int[] heap = new int[numSymbols];
\r
1524 for (int n = 0; n < numSymbols; n++) {
\r
1525 int freq = freqs[n];
\r
1527 /* Insert n into heap */
\r
1528 int pos = heapLen++;
\r
1530 while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
\r
1531 heap[pos] = heap[ppos];
\r
1540 /* We could encode a single literal with 0 bits but then we
\r
1541 * don't see the literals. Therefore we force at least two
\r
1542 * literals to avoid this case. We don't care about order in
\r
1543 * this case, both literals get a 1 bit code.
\r
1545 while (heapLen < 2) {
\r
1546 int node = maxCode < 2 ? ++maxCode : 0;
\r
1547 heap[heapLen++] = node;
\r
1550 numCodes = Math.Max(maxCode + 1, minNumCodes);
\r
1552 int numLeafs = heapLen;
\r
1553 int[] childs = new int[4*heapLen - 2];
\r
1554 int[] values = new int[2*heapLen - 1];
\r
1555 int numNodes = numLeafs;
\r
1556 for (int i = 0; i < heapLen; i++) {
\r
1557 int node = heap[i];
\r
1558 childs[2*i] = node;
\r
1559 childs[2*i+1] = -1;
\r
1560 values[i] = freqs[node] << 8;
\r
1564 /* Construct the Huffman tree by repeatedly combining the least two
\r
1568 int first = heap[0];
\r
1569 int last = heap[--heapLen];
\r
1571 /* Propagate the hole to the leafs of the heap */
\r
1574 while (path < heapLen) {
\r
1575 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
\r
1579 heap[ppos] = heap[path];
\r
1581 path = path * 2 + 1;
\r
1584 /* Now propagate the last element down along path. Normally
\r
1585 * it shouldn't go too deep.
\r
1587 int lastVal = values[last];
\r
1588 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
\r
1589 heap[path] = heap[ppos];
\r
1591 heap[path] = last;
\r
1594 int second = heap[0];
\r
1596 /* Create a new node father of first and second */
\r
1597 last = numNodes++;
\r
1598 childs[2*last] = first;
\r
1599 childs[2*last+1] = second;
\r
1600 int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
\r
1601 values[last] = lastVal = values[first] + values[second] - mindepth + 1;
\r
1603 /* Again, propagate the hole to the leafs */
\r
1606 while (path < heapLen) {
\r
1607 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
\r
1611 heap[ppos] = heap[path];
\r
1613 path = ppos * 2 + 1;
\r
1616 /* Now propagate the new element down along path */
\r
1617 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
\r
1618 heap[path] = heap[ppos];
\r
1620 heap[path] = last;
\r
1621 } while (heapLen > 1);
\r
1623 if (heap[0] != childs.Length / 2 - 1) {
\r
1624 throw new Exception("Weird!");
\r
1626 BuildLength(childs);
\r
1629 public int GetEncodedLength()
\r
1632 for (int i = 0; i < freqs.Length; i++) {
\r
1633 len += freqs[i] * length[i];
\r
1638 public void CalcBLFreq(Tree blTree)
\r
1640 int max_count; /* max repeat count */
\r
1641 int min_count; /* min repeat count */
\r
1642 int count; /* repeat count of the current code */
\r
1643 int curlen = -1; /* length of current code */
\r
1646 while (i < numCodes) {
\r
1648 int nextlen = length[i];
\r
1649 if (nextlen == 0) {
\r
1655 if (curlen != nextlen) {
\r
1656 blTree.freqs[nextlen]++;
\r
1663 while (i < numCodes && curlen == length[i]) {
\r
1665 if (++count >= max_count) {
\r
1670 if (count < min_count) {
\r
1671 blTree.freqs[curlen] += (short)count;
\r
1672 } else if (curlen != 0) {
\r
1673 blTree.freqs[REP_3_6]++;
\r
1674 } else if (count <= 10) {
\r
1675 blTree.freqs[REP_3_10]++;
\r
1677 blTree.freqs[REP_11_138]++;
\r
1682 public void WriteTree(Tree blTree)
\r
1684 int max_count; /* max repeat count */
\r
1685 int min_count; /* min repeat count */
\r
1686 int count; /* repeat count of the current code */
\r
1687 int curlen = -1; /* length of current code */
\r
1690 while (i < numCodes) {
\r
1692 int nextlen = length[i];
\r
1693 if (nextlen == 0) {
\r
1699 if (curlen != nextlen) {
\r
1700 blTree.WriteSymbol(nextlen);
\r
1707 while (i < numCodes && curlen == length[i]) {
\r
1709 if (++count >= max_count) {
\r
1714 if (count < min_count) {
\r
1715 while (count-- > 0) {
\r
1716 blTree.WriteSymbol(curlen);
\r
1719 else if (curlen != 0) {
\r
1720 blTree.WriteSymbol(REP_3_6);
\r
1721 dh.pending.WriteBits(count - 3, 2);
\r
1722 } else if (count <= 10) {
\r
1723 blTree.WriteSymbol(REP_3_10);
\r
1724 dh.pending.WriteBits(count - 3, 3);
\r
1726 blTree.WriteSymbol(REP_11_138);
\r
1727 dh.pending.WriteBits(count - 11, 7);
\r
1733 public DeflaterPending pending;
\r
1734 private Tree literalTree, distTree, blTree;
\r
1736 private short[] d_buf;
\r
1737 private byte[] l_buf;
\r
1738 private int last_lit;
\r
1739 private int extra_bits;
\r
1741 private static short[] staticLCodes;
\r
1742 private static byte[] staticLLength;
\r
1743 private static short[] staticDCodes;
\r
1744 private static byte[] staticDLength;
\r
1747 /// Reverse the bits of a 16 bit value.
\r
1749 public static short BitReverse(int value)
\r
1751 return (short) (bit4Reverse[value & 0xF] << 12
\r
1752 | bit4Reverse[(value >> 4) & 0xF] << 8
\r
1753 | bit4Reverse[(value >> 8) & 0xF] << 4
\r
1754 | bit4Reverse[value >> 12]);
\r
1758 static DeflaterHuffman()
\r
1760 /* See RFC 1951 3.2.6 */
\r
1761 /* Literal codes */
\r
1762 staticLCodes = new short[LITERAL_NUM];
\r
1763 staticLLength = new byte[LITERAL_NUM];
\r
1766 staticLCodes[i] = BitReverse((0x030 + i) << 8);
\r
1767 staticLLength[i++] = 8;
\r
1770 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
\r
1771 staticLLength[i++] = 9;
\r
1774 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
\r
1775 staticLLength[i++] = 7;
\r
1777 while (i < LITERAL_NUM) {
\r
1778 staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
\r
1779 staticLLength[i++] = 8;
\r
1782 /* Distant codes */
\r
1783 staticDCodes = new short[DIST_NUM];
\r
1784 staticDLength = new byte[DIST_NUM];
\r
1785 for (i = 0; i < DIST_NUM; i++) {
\r
1786 staticDCodes[i] = BitReverse(i << 11);
\r
1787 staticDLength[i] = 5;
\r
1791 public DeflaterHuffman(DeflaterPending pending)
\r
1793 this.pending = pending;
\r
1795 literalTree = new Tree(this, LITERAL_NUM, 257, 15);
\r
1796 distTree = new Tree(this, DIST_NUM, 1, 15);
\r
1797 blTree = new Tree(this, BITLEN_NUM, 4, 7);
\r
1799 d_buf = new short[BUFSIZE];
\r
1800 l_buf = new byte [BUFSIZE];
\r
1803 public void Reset()
\r
1807 literalTree.Reset();
\r
1812 private int L_code(int len)
\r
1819 while (len >= 8) {
\r
1823 return code + len;
\r
1826 private int D_code(int distance)
\r
1829 while (distance >= 4) {
\r
1833 return code + distance;
\r
1836 public void SendAllTrees(int blTreeCodes)
\r
1838 blTree.BuildCodes();
\r
1839 literalTree.BuildCodes();
\r
1840 distTree.BuildCodes();
\r
1841 pending.WriteBits(literalTree.numCodes - 257, 5);
\r
1842 pending.WriteBits(distTree.numCodes - 1, 5);
\r
1843 pending.WriteBits(blTreeCodes - 4, 4);
\r
1844 for (int rank = 0; rank < blTreeCodes; rank++) {
\r
1845 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
\r
1847 literalTree.WriteTree(blTree);
\r
1848 distTree.WriteTree(blTree);
\r
1849 // if (DeflaterConstants.DEBUGGING) {
\r
1850 // blTree.CheckEmpty();
\r
1854 public void CompressBlock()
\r
1856 for (int i = 0; i < last_lit; i++) {
\r
1857 int litlen = l_buf[i] & 0xff;
\r
1858 int dist = d_buf[i];
\r
1859 if (dist-- != 0) {
\r
1860 // if (DeflaterConstants.DEBUGGING) {
\r
1861 // Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
\r
1864 int lc = L_code(litlen);
\r
1865 literalTree.WriteSymbol(lc);
\r
1867 int bits = (lc - 261) / 4;
\r
1868 if (bits > 0 && bits <= 5) {
\r
1869 pending.WriteBits(litlen & ((1 << bits) - 1), bits);
\r
1872 int dc = D_code(dist);
\r
1873 distTree.WriteSymbol(dc);
\r
1875 bits = dc / 2 - 1;
\r
1877 pending.WriteBits(dist & ((1 << bits) - 1), bits);
\r
1880 // if (DeflaterConstants.DEBUGGING) {
\r
1881 // if (litlen > 32 && litlen < 127) {
\r
1882 // Console.Write("("+(char)litlen+"): ");
\r
1884 // Console.Write("{"+litlen+"}: ");
\r
1887 literalTree.WriteSymbol(litlen);
\r
1890 // if (DeflaterConstants.DEBUGGING) {
\r
1891 // Console.Write("EOF: ");
\r
1893 literalTree.WriteSymbol(EOF_SYMBOL);
\r
1894 // if (DeflaterConstants.DEBUGGING) {
\r
1895 // literalTree.CheckEmpty();
\r
1896 // distTree.CheckEmpty();
\r
1900 public void FlushStoredBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
\r
1902 // if (DeflaterConstants.DEBUGGING) {
\r
1903 // Console.WriteLine("Flushing stored block "+ stored_len);
\r
1905 pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1)
\r
1906 + (lastBlock ? 1 : 0), 3);
\r
1907 pending.AlignToByte();
\r
1908 pending.WriteShort(stored_len);
\r
1909 pending.WriteShort(~stored_len);
\r
1910 pending.WriteBlock(stored, stored_offset, stored_len);
\r
1914 public void FlushBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
\r
1916 literalTree.freqs[EOF_SYMBOL]++;
\r
1919 literalTree.BuildTree();
\r
1920 distTree.BuildTree();
\r
1922 /* Calculate bitlen frequency */
\r
1923 literalTree.CalcBLFreq(blTree);
\r
1924 distTree.CalcBLFreq(blTree);
\r
1926 /* Build bitlen tree */
\r
1927 blTree.BuildTree();
\r
1929 int blTreeCodes = 4;
\r
1930 for (int i = 18; i > blTreeCodes; i--) {
\r
1931 if (blTree.length[BL_ORDER[i]] > 0) {
\r
1932 blTreeCodes = i+1;
\r
1935 int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
\r
1936 literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
\r
1939 int static_len = extra_bits;
\r
1940 for (int i = 0; i < LITERAL_NUM; i++) {
\r
1941 static_len += literalTree.freqs[i] * staticLLength[i];
\r
1943 for (int i = 0; i < DIST_NUM; i++) {
\r
1944 static_len += distTree.freqs[i] * staticDLength[i];
\r
1946 if (opt_len >= static_len) {
\r
1947 /* Force static trees */
\r
1948 opt_len = static_len;
\r
1951 if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) {
\r
1953 // if (DeflaterConstants.DEBUGGING) {
\r
1954 // Console.WriteLine("Storing, since " + stored_len + " < " + opt_len
\r
1955 // + " <= " + static_len);
\r
1957 FlushStoredBlock(stored, stored_offset, stored_len, lastBlock);
\r
1958 } else if (opt_len == static_len) {
\r
1959 /* Encode with static tree */
\r
1960 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
\r
1961 literalTree.SetStaticCodes(staticLCodes, staticLLength);
\r
1962 distTree.SetStaticCodes(staticDCodes, staticDLength);
\r
1966 /* Encode with dynamic tree */
\r
1967 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
\r
1968 SendAllTrees(blTreeCodes);
\r
1974 public bool IsFull()
\r
1976 return last_lit + 16 >= BUFSIZE; // HACK: This was == 'last_lit == BUFSIZE', but errors occured with DeflateFast
\r
1979 public bool TallyLit(int lit)
\r
1981 // if (DeflaterConstants.DEBUGGING) {
\r
1982 // if (lit > 32 && lit < 127) {
\r
1983 // Console.WriteLine("("+(char)lit+")");
\r
1985 // Console.WriteLine("{"+lit+"}");
\r
1988 d_buf[last_lit] = 0;
\r
1989 l_buf[last_lit++] = (byte)lit;
\r
1990 literalTree.freqs[lit]++;
\r
1994 public bool TallyDist(int dist, int len)
\r
1996 // if (DeflaterConstants.DEBUGGING) {
\r
1997 // Console.WriteLine("["+dist+","+len+"]");
\r
2000 d_buf[last_lit] = (short)dist;
\r
2001 l_buf[last_lit++] = (byte)(len - 3);
\r
2003 int lc = L_code(len - 3);
\r
2004 literalTree.freqs[lc]++;
\r
2005 if (lc >= 265 && lc < 285) {
\r
2006 extra_bits += (lc - 261) / 4;
\r
2009 int dc = D_code(dist - 1);
\r
2010 distTree.freqs[dc]++;
\r
2012 extra_bits += dc / 2 - 1;
\r
2019 namespace NZlib.Compression {
\r
2022 /// This class stores the pending output of the Deflater.
\r
2024 /// author of the original java version : Jochen Hoenicke
\r
2026 public class DeflaterPending : PendingBuffer
\r
2028 public DeflaterPending() : base(DeflaterConstants.PENDING_BUF_SIZE)
\r
2034 namespace NZlib.Compression {
\r
2037 /// Inflater is used to decompress data that has been compressed according
\r
2038 /// to the "deflate" standard described in rfc1950.
\r
2040 /// The usage is as following. First you have to set some input with
\r
2041 /// <code>setInput()</code>, then inflate() it. If inflate doesn't
\r
2042 /// inflate any bytes there may be three reasons:
\r
2044 /// <li>needsInput() returns true because the input buffer is empty.
\r
2045 /// You have to provide more input with <code>setInput()</code>.
\r
2046 /// NOTE: needsInput() also returns true when, the stream is finished.
\r
2048 /// <li>needsDictionary() returns true, you have to provide a preset
\r
2049 /// dictionary with <code>setDictionary()</code>.</li>
\r
2050 /// <li>finished() returns true, the inflater has finished.</li>
\r
2052 /// Once the first output byte is produced, a dictionary will not be
\r
2053 /// needed at a later stage.
\r
2055 /// author of the original java version : John Leuner, Jochen Hoenicke
\r
2057 public class Inflater
\r
2060 /// Copy lengths for literal codes 257..285
\r
2062 private static int[] CPLENS = {
\r
2063 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
\r
2064 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
\r
2068 /// Extra bits for literal codes 257..285
\r
2070 private static int[] CPLEXT = {
\r
2071 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
\r
2072 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
\r
2076 /// Copy offsets for distance codes 0..29
\r
2078 private static int[] CPDIST = {
\r
2079 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
\r
2080 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
\r
2081 8193, 12289, 16385, 24577
\r
2085 /// Extra bits for distance codes
\r
2087 private static int[] CPDEXT = {
\r
2088 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
\r
2089 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
\r
2094 /// This are the state in which the inflater can be.
\r
2096 private const int DECODE_HEADER = 0;
\r
2097 private const int DECODE_DICT = 1;
\r
2098 private const int DECODE_BLOCKS = 2;
\r
2099 private const int DECODE_STORED_LEN1 = 3;
\r
2100 private const int DECODE_STORED_LEN2 = 4;
\r
2101 private const int DECODE_STORED = 5;
\r
2102 private const int DECODE_DYN_HEADER = 6;
\r
2103 private const int DECODE_HUFFMAN = 7;
\r
2104 private const int DECODE_HUFFMAN_LENBITS = 8;
\r
2105 private const int DECODE_HUFFMAN_DIST = 9;
\r
2106 private const int DECODE_HUFFMAN_DISTBITS = 10;
\r
2107 private const int DECODE_CHKSUM = 11;
\r
2108 private const int FINISHED = 12;
\r
2111 /// This variable contains the current state.
\r
2116 /// The adler checksum of the dictionary or of the decompressed
\r
2117 /// stream, as it is written in the header resp. footer of the
\r
2118 /// compressed stream.
\r
2119 /// Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
\r
2121 private int readAdler;
\r
2124 /// The number of bits needed to complete the current state. This
\r
2125 /// is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
\r
2126 /// DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
\r
2128 private int neededBits;
\r
2129 private int repLength, repDist;
\r
2130 private int uncomprLen;
\r
2133 /// True, if the last block flag was set in the last block of the
\r
2134 /// inflated stream. This means that the stream ends after the
\r
2135 /// current block.
\r
2137 private bool isLastBlock;
\r
2140 /// The total number of inflated bytes.
\r
2142 private int totalOut;
\r
2145 /// The total number of bytes set with setInput(). This is not the
\r
2146 /// value returned by getTotalIn(), since this also includes the
\r
2147 /// unprocessed input.
\r
2149 private int totalIn;
\r
2152 /// This variable stores the nowrap flag that was given to the constructor.
\r
2153 /// True means, that the inflated stream doesn't contain a header nor the
\r
2154 /// checksum in the footer.
\r
2156 private bool nowrap;
\r
2158 private StreamManipulator input;
\r
2159 private OutputWindow outputWindow;
\r
2160 private InflaterDynHeader dynHeader;
\r
2161 private InflaterHuffmanTree litlenTree, distTree;
\r
2162 private Adler32 adler;
\r
2165 /// Creates a new inflater.
\r
2167 public Inflater() : this(false)
\r
2172 /// Creates a new inflater.
\r
2174 /// <param name="nowrap">
\r
2175 /// true if no header and checksum field appears in the
\r
2176 /// stream. This is used for GZIPed input. For compatibility with
\r
2177 /// Sun JDK you should provide one byte of input more than needed in
\r
2180 public Inflater(bool nowrap)
\r
2182 this.nowrap = nowrap;
\r
2183 this.adler = new Adler32();
\r
2184 input = new StreamManipulator();
\r
2185 outputWindow = new OutputWindow();
\r
2186 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
\r
2190 /// Resets the inflater so that a new stream can be decompressed. All
\r
2191 /// pending input and output will be discarded.
\r
2193 public void Reset()
\r
2195 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
\r
2196 totalIn = totalOut = 0;
\r
2198 outputWindow.Reset();
\r
2200 litlenTree = null;
\r
2202 isLastBlock = false;
\r
2207 /// Decodes the deflate header.
\r
2210 /// false if more input is needed.
\r
2212 /// <exception cref="System.FormatException">
\r
2213 /// if header is invalid.
\r
2215 private bool DecodeHeader()
\r
2217 int header = input.PeekBits(16);
\r
2221 input.DropBits(16);
\r
2222 /* The header is written in "wrong" byte order */
\r
2223 header = ((header << 8) | (header >> 8)) & 0xffff;
\r
2224 if (header % 31 != 0) {
\r
2225 throw new FormatException("Header checksum illegal");
\r
2228 if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) {
\r
2229 throw new FormatException("Compression Method unknown");
\r
2232 /* Maximum size of the backwards window in bits.
\r
2233 * We currently ignore this, but we could use it to make the
\r
2234 * inflater window more space efficient. On the other hand the
\r
2235 * full window (15 bits) is needed most times, anyway.
\r
2236 int max_wbits = ((header & 0x7000) >> 12) + 8;
\r
2239 if ((header & 0x0020) == 0) { // Dictionary flag?
\r
2240 mode = DECODE_BLOCKS;
\r
2242 mode = DECODE_DICT;
\r
2249 /// Decodes the dictionary checksum after the deflate header.
\r
2252 /// false if more input is needed.
\r
2254 private bool DecodeDict()
\r
2256 while (neededBits > 0) {
\r
2257 int dictByte = input.PeekBits(8);
\r
2258 if (dictByte < 0) {
\r
2261 input.DropBits(8);
\r
2262 readAdler = (readAdler << 8) | dictByte;
\r
2269 /// Decodes the huffman encoded symbols in the input stream.
\r
2272 /// false if more input is needed, true if output window is
\r
2273 /// full or the current block ends.
\r
2275 /// <exception cref="System.FormatException">
\r
2276 /// if deflated stream is invalid.
\r
2278 private bool DecodeHuffman()
\r
2280 int free = outputWindow.GetFreeSpace();
\r
2281 while (free >= 258) {
\r
2284 case DECODE_HUFFMAN:
\r
2285 /* This is the inner loop so it is optimized a bit */
\r
2286 while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) {
\r
2287 outputWindow.Write(symbol);
\r
2288 if (--free < 258) {
\r
2292 if (symbol < 257) {
\r
2296 /* symbol == 256: end of block */
\r
2298 litlenTree = null;
\r
2299 mode = DECODE_BLOCKS;
\r
2305 repLength = CPLENS[symbol - 257];
\r
2306 neededBits = CPLEXT[symbol - 257];
\r
2307 } catch (Exception) {
\r
2308 throw new FormatException("Illegal rep length code");
\r
2310 goto case DECODE_HUFFMAN_LENBITS;/* fall through */
\r
2311 case DECODE_HUFFMAN_LENBITS:
\r
2312 if (neededBits > 0) {
\r
2313 mode = DECODE_HUFFMAN_LENBITS;
\r
2314 int i = input.PeekBits(neededBits);
\r
2318 input.DropBits(neededBits);
\r
2321 mode = DECODE_HUFFMAN_DIST;
\r
2322 goto case DECODE_HUFFMAN_DIST;/* fall through */
\r
2323 case DECODE_HUFFMAN_DIST:
\r
2324 symbol = distTree.GetSymbol(input);
\r
2329 repDist = CPDIST[symbol];
\r
2330 neededBits = CPDEXT[symbol];
\r
2331 } catch (Exception) {
\r
2332 throw new FormatException("Illegal rep dist code");
\r
2335 goto case DECODE_HUFFMAN_DISTBITS;/* fall through */
\r
2336 case DECODE_HUFFMAN_DISTBITS:
\r
2337 if (neededBits > 0) {
\r
2338 mode = DECODE_HUFFMAN_DISTBITS;
\r
2339 int i = input.PeekBits(neededBits);
\r
2343 input.DropBits(neededBits);
\r
2346 outputWindow.Repeat(repLength, repDist);
\r
2347 free -= repLength;
\r
2348 mode = DECODE_HUFFMAN;
\r
2351 throw new FormatException();
\r
2358 /// Decodes the adler checksum after the deflate stream.
\r
2361 /// false if more input is needed.
\r
2363 /// <exception cref="System.FormatException">
\r
2364 /// DataFormatException, if checksum doesn't match.
\r
2366 private bool DecodeChksum()
\r
2368 while (neededBits > 0) {
\r
2369 int chkByte = input.PeekBits(8);
\r
2370 if (chkByte < 0) {
\r
2373 input.DropBits(8);
\r
2374 readAdler = (readAdler << 8) | chkByte;
\r
2377 if ((int) adler.Value != readAdler) {
\r
2378 throw new FormatException("Adler chksum doesn't match: "
\r
2379 + (int)adler.Value
\r
2380 + " vs. " + readAdler);
\r
2387 /// Decodes the deflated stream.
\r
2390 /// false if more input is needed, or if finished.
\r
2392 /// <exception cref="System.FormatException">
\r
2393 /// DataFormatException, if deflated stream is invalid.
\r
2395 private bool Decode()
\r
2398 case DECODE_HEADER:
\r
2399 return DecodeHeader();
\r
2401 return DecodeDict();
\r
2402 case DECODE_CHKSUM:
\r
2403 return DecodeChksum();
\r
2405 case DECODE_BLOCKS:
\r
2406 if (isLastBlock) {
\r
2411 input.SkipToByteBoundary();
\r
2413 mode = DECODE_CHKSUM;
\r
2418 int type = input.PeekBits(3);
\r
2422 input.DropBits(3);
\r
2424 if ((type & 1) != 0) {
\r
2425 isLastBlock = true;
\r
2427 switch (type >> 1) {
\r
2428 case DeflaterConstants.STORED_BLOCK:
\r
2429 input.SkipToByteBoundary();
\r
2430 mode = DECODE_STORED_LEN1;
\r
2432 case DeflaterConstants.STATIC_TREES:
\r
2433 litlenTree = InflaterHuffmanTree.defLitLenTree;
\r
2434 distTree = InflaterHuffmanTree.defDistTree;
\r
2435 mode = DECODE_HUFFMAN;
\r
2437 case DeflaterConstants.DYN_TREES:
\r
2438 dynHeader = new InflaterDynHeader();
\r
2439 mode = DECODE_DYN_HEADER;
\r
2442 throw new FormatException("Unknown block type "+type);
\r
2446 case DECODE_STORED_LEN1: {
\r
2447 if ((uncomprLen = input.PeekBits(16)) < 0) {
\r
2450 input.DropBits(16);
\r
2451 mode = DECODE_STORED_LEN2;
\r
2453 goto case DECODE_STORED_LEN2; /* fall through */
\r
2454 case DECODE_STORED_LEN2: {
\r
2455 int nlen = input.PeekBits(16);
\r
2459 input.DropBits(16);
\r
2460 if (nlen != (uncomprLen ^ 0xffff)) {
\r
2461 throw new FormatException("broken uncompressed block");
\r
2463 mode = DECODE_STORED;
\r
2465 goto case DECODE_STORED;/* fall through */
\r
2466 case DECODE_STORED: {
\r
2467 int more = outputWindow.CopyStored(input, uncomprLen);
\r
2468 uncomprLen -= more;
\r
2469 if (uncomprLen == 0) {
\r
2470 mode = DECODE_BLOCKS;
\r
2473 return !input.IsNeedingInput;
\r
2476 case DECODE_DYN_HEADER:
\r
2477 if (!dynHeader.Decode(input)) {
\r
2481 litlenTree = dynHeader.BuildLitLenTree();
\r
2482 distTree = dynHeader.BuildDistTree();
\r
2483 mode = DECODE_HUFFMAN;
\r
2484 goto case DECODE_HUFFMAN; /* fall through */
\r
2485 case DECODE_HUFFMAN:
\r
2486 case DECODE_HUFFMAN_LENBITS:
\r
2487 case DECODE_HUFFMAN_DIST:
\r
2488 case DECODE_HUFFMAN_DISTBITS:
\r
2489 return DecodeHuffman();
\r
2493 throw new FormatException();
\r
2498 /// Sets the preset dictionary. This should only be called, if
\r
2499 /// needsDictionary() returns true and it should set the same
\r
2500 /// dictionary, that was used for deflating. The getAdler()
\r
2501 /// function returns the checksum of the dictionary needed.
\r
2503 /// <param name="buffer">
\r
2504 /// the dictionary.
\r
2506 /// <exception cref="System.InvalidOperationException">
\r
2507 /// if no dictionary is needed.
\r
2509 /// <exception cref="System.ArgumentException">
\r
2510 /// if the dictionary checksum is wrong.
\r
2512 public void SetDictionary(byte[] buffer)
\r
2514 SetDictionary(buffer, 0, buffer.Length);
\r
2518 /// Sets the preset dictionary. This should only be called, if
\r
2519 /// needsDictionary() returns true and it should set the same
\r
2520 /// dictionary, that was used for deflating. The getAdler()
\r
2521 /// function returns the checksum of the dictionary needed.
\r
2523 /// <param name="buffer">
\r
2524 /// the dictionary.
\r
2526 /// <param name="off">
\r
2527 /// the offset into buffer where the dictionary starts.
\r
2529 /// <param name="len">
\r
2530 /// the length of the dictionary.
\r
2532 /// <exception cref="System.InvalidOperationException">
\r
2533 /// if no dictionary is needed.
\r
2535 /// <exception cref="System.ArgumentException">
\r
2536 /// if the dictionary checksum is wrong.
\r
2538 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2539 /// if the off and/or len are wrong.
\r
2541 public void SetDictionary(byte[] buffer, int off, int len)
\r
2543 if (!IsNeedingDictionary) {
\r
2544 throw new InvalidOperationException();
\r
2547 adler.Update(buffer, off, len);
\r
2548 if ((int) adler.Value != readAdler) {
\r
2549 throw new ArgumentException("Wrong adler checksum");
\r
2552 outputWindow.CopyDict(buffer, off, len);
\r
2553 mode = DECODE_BLOCKS;
\r
2557 /// Sets the input. This should only be called, if needsInput()
\r
2560 /// <param name="buf">
\r
2563 /// <exception cref="System.InvalidOperationException">
\r
2564 /// if no input is needed.
\r
2566 public void SetInput(byte[] buf)
\r
2568 SetInput(buf, 0, buf.Length);
\r
2572 /// Sets the input. This should only be called, if needsInput()
\r
2575 /// <param name="buf">
\r
2578 /// <param name="off">
\r
2579 /// the offset into buffer where the input starts.
\r
2581 /// <param name="len">
\r
2582 /// the length of the input.
\r
2584 /// <exception cref="System.InvalidOperationException">
\r
2585 /// if no input is needed.
\r
2587 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2588 /// if the off and/or len are wrong.
\r
2590 public void SetInput(byte[] buf, int off, int len)
\r
2592 input.SetInput(buf, off, len);
\r
2597 /// Inflates the compressed stream to the output buffer. If this
\r
2598 /// returns 0, you should check, whether needsDictionary(),
\r
2599 /// needsInput() or finished() returns true, to determine why no
\r
2600 /// further output is produced.
\r
2602 /// <param name = "buf">
\r
2603 /// the output buffer.
\r
2606 /// the number of bytes written to the buffer, 0 if no further
\r
2607 /// output can be produced.
\r
2609 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2610 /// if buf has length 0.
\r
2612 /// <exception cref="System.FormatException">
\r
2613 /// if deflated stream is invalid.
\r
2615 public int Inflate(byte[] buf)
\r
2617 return Inflate(buf, 0, buf.Length);
\r
2621 /// Inflates the compressed stream to the output buffer. If this
\r
2622 /// returns 0, you should check, whether needsDictionary(),
\r
2623 /// needsInput() or finished() returns true, to determine why no
\r
2624 /// further output is produced.
\r
2626 /// <param name = "buf">
\r
2627 /// the output buffer.
\r
2629 /// <param name = "off">
\r
2630 /// the offset into buffer where the output should start.
\r
2632 /// <param name = "len">
\r
2633 /// the maximum length of the output.
\r
2636 /// the number of bytes written to the buffer, 0 if no further output can be produced.
\r
2638 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2639 /// if len is <= 0.
\r
2641 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2642 /// if the off and/or len are wrong.
\r
2644 /// <exception cref="System.FormatException">
\r
2645 /// if deflated stream is invalid.
\r
2647 public int Inflate(byte[] buf, int off, int len)
\r
2650 throw new ArgumentOutOfRangeException("len <= 0");
\r
2655 if (mode != DECODE_CHKSUM) {
\r
2656 /* Don't give away any output, if we are waiting for the
\r
2657 * checksum in the input stream.
\r
2659 * With this trick we have always:
\r
2660 * needsInput() and not finished()
\r
2661 * implies more output can be produced.
\r
2663 more = outputWindow.CopyOutput(buf, off, len);
\r
2664 adler.Update(buf, off, more);
\r
2673 } while (Decode() || (outputWindow.GetAvailable() > 0 &&
\r
2674 mode != DECODE_CHKSUM));
\r
2679 /// Returns true, if the input buffer is empty.
\r
2680 /// You should then call setInput().
\r
2681 /// NOTE: This method also returns true when the stream is finished.
\r
2683 public bool IsNeedingInput {
\r
2685 return input.IsNeedingInput;
\r
2690 /// Returns true, if a preset dictionary is needed to inflate the input.
\r
2692 public bool IsNeedingDictionary {
\r
2694 return mode == DECODE_DICT && neededBits == 0;
\r
2699 /// Returns true, if the inflater has finished. This means, that no
\r
2700 /// input is needed and no output can be produced.
\r
2702 public bool IsFinished {
\r
2704 return mode == FINISHED && outputWindow.GetAvailable() == 0;
\r
2709 /// Gets the adler checksum. This is either the checksum of all
\r
2710 /// uncompressed bytes returned by inflate(), or if needsDictionary()
\r
2711 /// returns true (and thus no output was yet produced) this is the
\r
2712 /// adler checksum of the expected dictionary.
\r
2715 /// the adler checksum.
\r
2717 public int Adler {
\r
2719 return IsNeedingDictionary ? readAdler : (int) adler.Value;
\r
2724 /// Gets the total number of output bytes returned by inflate().
\r
2727 /// the total number of output bytes.
\r
2729 public int TotalOut {
\r
2736 /// Gets the total number of processed compressed input bytes.
\r
2739 /// the total number of bytes of processed input bytes.
\r
2741 public int TotalIn {
\r
2743 return totalIn - RemainingInput;
\r
2748 /// Gets the number of unprocessed input. Useful, if the end of the
\r
2749 /// stream is reached and you want to further process the bytes after
\r
2750 /// the deflate stream.
\r
2753 /// the number of bytes of the input which were not processed.
\r
2755 public int RemainingInput {
\r
2757 return input.AvailableBytes;
\r
2763 namespace NZlib.Compression {
\r
2765 public class InflaterDynHeader
\r
2767 private const int LNUM = 0;
\r
2768 private const int DNUM = 1;
\r
2769 private const int BLNUM = 2;
\r
2770 private const int BLLENS = 3;
\r
2771 private const int LLENS = 4;
\r
2772 private const int DLENS = 5;
\r
2773 private const int LREPS = 6;
\r
2774 private const int DREPS = 7;
\r
2775 private const int FINISH = 8;
\r
2777 private byte[] blLens;
\r
2778 private byte[] litlenLens;
\r
2779 private byte[] distLens;
\r
2781 private InflaterHuffmanTree blTree;
\r
2784 private int lnum, dnum, blnum;
\r
2785 private int repBits;
\r
2786 private byte repeatedLen;
\r
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 };
\r
2791 public InflaterDynHeader()
\r
2795 public bool Decode(StreamManipulator input)
\r
2801 lnum = input.PeekBits(5);
\r
2806 input.DropBits(5);
\r
2807 litlenLens = new byte[lnum];
\r
2808 // System.err.println("LNUM: "+lnum);
\r
2810 goto case DNUM;/* fall through */
\r
2812 dnum = input.PeekBits(5);
\r
2817 input.DropBits(5);
\r
2818 distLens = new byte[dnum];
\r
2819 // System.err.println("DNUM: "+dnum);
\r
2821 goto case BLNUM;/* fall through */
\r
2823 blnum = input.PeekBits(4);
\r
2828 input.DropBits(4);
\r
2829 blLens = new byte[19];
\r
2831 // System.err.println("BLNUM: "+blnum);
\r
2833 goto case BLLENS;/* fall through */
\r
2835 while (ptr < blnum) {
\r
2836 int len = input.PeekBits(3);
\r
2840 input.DropBits(3);
\r
2841 // System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
\r
2842 blLens[BL_ORDER[ptr]] = (byte) len;
\r
2845 blTree = new InflaterHuffmanTree(blLens);
\r
2849 goto case LLENS;/* fall through */
\r
2851 while (ptr < lnum) {
\r
2852 int symbol = blTree.GetSymbol(input);
\r
2858 // System.err.println("litlenLens["+ptr+"]: "+symbol);
\r
2859 litlenLens[ptr++] = (byte) symbol;
\r
2861 case 16: /* repeat last len 3-6 times */
\r
2863 throw new Exception("Repeating, but no prev len");
\r
2866 // System.err.println("litlenLens["+ptr+"]: repeat");
\r
2867 repeatedLen = litlenLens[ptr-1];
\r
2869 for (int i = 3; i-- > 0; ) {
\r
2870 if (ptr >= lnum) {
\r
2871 throw new Exception();
\r
2873 litlenLens[ptr++] = repeatedLen;
\r
2877 case 17: /* repeat zero 3-10 times */
\r
2878 // System.err.println("litlenLens["+ptr+"]: zero repeat");
\r
2881 for (int i = 3; i-- > 0; ) {
\r
2882 if (ptr >= lnum) {
\r
2883 throw new Exception();
\r
2885 litlenLens[ptr++] = repeatedLen;
\r
2889 case 18: /* repeat zero 11-138 times */
\r
2890 // System.err.println("litlenLens["+ptr+"]: zero repeat");
\r
2893 for (int i = 11; i-- > 0; ) {
\r
2894 if (ptr >= lnum) {
\r
2895 throw new Exception();
\r
2897 litlenLens[ptr++] = repeatedLen;
\r
2905 goto case DLENS;/* fall through */
\r
2907 while (ptr < dnum) {
\r
2908 int symbol = blTree.GetSymbol(input);
\r
2914 distLens[ptr++] = (byte) symbol;
\r
2915 // System.err.println("distLens["+ptr+"]: "+symbol);
\r
2917 case 16: /* repeat last len 3-6 times */
\r
2919 throw new Exception("Repeating, but no prev len");
\r
2921 // System.err.println("distLens["+ptr+"]: repeat");
\r
2922 repeatedLen = distLens[ptr-1];
\r
2924 for (int i = 3; i-- > 0; ) {
\r
2925 if (ptr >= dnum) {
\r
2926 throw new Exception();
\r
2928 distLens[ptr++] = repeatedLen;
\r
2932 case 17: /* repeat zero 3-10 times */
\r
2933 // System.err.println("distLens["+ptr+"]: repeat zero");
\r
2936 for (int i = 3; i-- > 0; ) {
\r
2937 if (ptr >= dnum) {
\r
2938 throw new Exception();
\r
2940 distLens[ptr++] = repeatedLen;
\r
2944 case 18: /* repeat zero 11-138 times */
\r
2945 // System.err.println("distLens["+ptr+"]: repeat zero");
\r
2948 for (int i = 11; i-- > 0; ) {
\r
2949 if (ptr >= dnum) {
\r
2950 throw new Exception();
\r
2952 distLens[ptr++] = repeatedLen;
\r
2962 int count = input.PeekBits(repBits);
\r
2966 input.DropBits(repBits);
\r
2967 // System.err.println("litlenLens repeat: "+repBits);
\r
2968 while (count-- > 0) {
\r
2969 if (ptr >= lnum) {
\r
2970 throw new Exception();
\r
2972 litlenLens[ptr++] = repeatedLen;
\r
2979 int count = input.PeekBits(repBits);
\r
2983 input.DropBits(repBits);
\r
2984 while (count-- > 0) {
\r
2985 if (ptr >= dnum) {
\r
2986 throw new Exception();
\r
2988 distLens[ptr++] = repeatedLen;
\r
2997 public InflaterHuffmanTree BuildLitLenTree()
\r
2999 return new InflaterHuffmanTree(litlenLens);
\r
3002 public InflaterHuffmanTree BuildDistTree()
\r
3004 return new InflaterHuffmanTree(distLens);
\r
3009 namespace NZlib.Compression {
\r
3011 public class InflaterHuffmanTree
\r
3013 private static int MAX_BITLEN = 15;
\r
3014 private short[] tree;
\r
3016 public static InflaterHuffmanTree defLitLenTree, defDistTree;
\r
3018 static InflaterHuffmanTree()
\r
3021 byte[] codeLengths = new byte[288];
\r
3024 codeLengths[i++] = 8;
\r
3027 codeLengths[i++] = 9;
\r
3030 codeLengths[i++] = 7;
\r
3033 codeLengths[i++] = 8;
\r
3035 defLitLenTree = new InflaterHuffmanTree(codeLengths);
\r
3037 codeLengths = new byte[32];
\r
3040 codeLengths[i++] = 5;
\r
3042 defDistTree = new InflaterHuffmanTree(codeLengths);
\r
3043 } catch (Exception) {
\r
3044 throw new ApplicationException("InflaterHuffmanTree: static tree length illegal");
\r
3049 /// Constructs a Huffman tree from the array of code lengths.
\r
3051 /// <param name = "codeLengths">
\r
3052 /// the array of code lengths
\r
3054 public InflaterHuffmanTree(byte[] codeLengths)
\r
3056 BuildTree(codeLengths);
\r
3059 private void BuildTree(byte[] codeLengths)
\r
3061 int[] blCount = new int[MAX_BITLEN + 1];
\r
3062 int[] nextCode = new int[MAX_BITLEN + 1];
\r
3064 for (int i = 0; i < codeLengths.Length; i++) {
\r
3065 int bits = codeLengths[i];
\r
3071 int treeSize = 512;
\r
3072 for (int bits = 1; bits <= MAX_BITLEN; bits++) {
\r
3073 nextCode[bits] = code;
\r
3074 code += blCount[bits] << (16 - bits);
\r
3076 /* We need an extra table for bit lengths >= 10. */
\r
3077 int start = nextCode[bits] & 0x1ff80;
\r
3078 int end = code & 0x1ff80;
\r
3079 treeSize += (end - start) >> (16 - bits);
\r
3082 if (code != 65536) {
\r
3083 throw new Exception("Code lengths don't add up properly.");
\r
3085 /* Now create and fill the extra tables from longest to shortest
\r
3086 * bit len. This way the sub trees will be aligned.
\r
3088 tree = new short[treeSize];
\r
3089 int treePtr = 512;
\r
3090 for (int bits = MAX_BITLEN; bits >= 10; bits--) {
\r
3091 int end = code & 0x1ff80;
\r
3092 code -= blCount[bits] << (16 - bits);
\r
3093 int start = code & 0x1ff80;
\r
3094 for (int i = start; i < end; i += 1 << 7) {
\r
3095 tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
\r
3096 treePtr += 1 << (bits-9);
\r
3100 for (int i = 0; i < codeLengths.Length; i++) {
\r
3101 int bits = codeLengths[i];
\r
3105 code = nextCode[bits];
\r
3106 int revcode = DeflaterHuffman.BitReverse(code);
\r
3109 tree[revcode] = (short) ((i << 4) | bits);
\r
3110 revcode += 1 << bits;
\r
3111 } while (revcode < 512);
\r
3113 int subTree = tree[revcode & 511];
\r
3114 int treeLen = 1 << (subTree & 15);
\r
3115 subTree = -(subTree >> 4);
\r
3117 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
\r
3118 revcode += 1 << bits;
\r
3119 } while (revcode < treeLen);
\r
3121 nextCode[bits] = code + (1 << (16 - bits));
\r
3127 /// Reads the next symbol from input. The symbol is encoded using the
\r
3130 /// <param name="input">
\r
3131 /// input the input source.
\r
3134 /// the next symbol, or -1 if not enough input is available.
\r
3136 public int GetSymbol(StreamManipulator input)
\r
3138 int lookahead, symbol;
\r
3139 if ((lookahead = input.PeekBits(9)) >= 0) {
\r
3140 if ((symbol = tree[lookahead]) >= 0) {
\r
3141 input.DropBits(symbol & 15);
\r
3142 return symbol >> 4;
\r
3144 int subtree = -(symbol >> 4);
\r
3145 int bitlen = symbol & 15;
\r
3146 if ((lookahead = input.PeekBits(bitlen)) >= 0) {
\r
3147 symbol = tree[subtree | (lookahead >> 9)];
\r
3148 input.DropBits(symbol & 15);
\r
3149 return symbol >> 4;
\r
3151 int bits = input.AvailableBits;
\r
3152 lookahead = input.PeekBits(bits);
\r
3153 symbol = tree[subtree | (lookahead >> 9)];
\r
3154 if ((symbol & 15) <= bits) {
\r
3155 input.DropBits(symbol & 15);
\r
3156 return symbol >> 4;
\r
3162 int bits = input.AvailableBits;
\r
3163 lookahead = input.PeekBits(bits);
\r
3164 symbol = tree[lookahead];
\r
3165 if (symbol >= 0 && (symbol & 15) <= bits) {
\r
3166 input.DropBits(symbol & 15);
\r
3167 return symbol >> 4;
\r
3176 namespace NZlib.Compression {
\r
3179 /// This class is general purpose class for writing data to a buffer.
\r
3181 /// It allows you to write bits as well as bytes
\r
3182 /// Based on DeflaterPending.java
\r
3184 /// author of the original java version : Jochen Hoenicke
\r
3186 public class PendingBuffer
\r
3188 protected byte[] buf;
\r
3195 public PendingBuffer() : this( 4096 )
\r
3200 public PendingBuffer(int bufsize)
\r
3202 buf = new byte[bufsize];
\r
3205 public void Reset()
\r
3207 start = end = bitCount = 0;
\r
3210 public void WriteByte(int b)
\r
3212 if (DeflaterConstants.DEBUGGING && start != 0)
\r
3213 throw new Exception();
\r
3214 buf[end++] = (byte) b;
\r
3217 public void WriteShort(int s)
\r
3219 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3220 throw new Exception();
\r
3222 buf[end++] = (byte) s;
\r
3223 buf[end++] = (byte) (s >> 8);
\r
3226 public void WriteInt(int s)
\r
3228 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3229 throw new Exception();
\r
3231 buf[end++] = (byte) s;
\r
3232 buf[end++] = (byte) (s >> 8);
\r
3233 buf[end++] = (byte) (s >> 16);
\r
3234 buf[end++] = (byte) (s >> 24);
\r
3237 public void WriteBlock(byte[] block, int offset, int len)
\r
3239 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3240 throw new Exception();
\r
3242 System.Array.Copy(block, offset, buf, end, len);
\r
3246 public int BitCount {
\r
3252 public void AlignToByte()
\r
3254 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3255 throw new Exception();
\r
3257 if (bitCount > 0) {
\r
3258 buf[end++] = (byte) bits;
\r
3259 if (bitCount > 8) {
\r
3260 buf[end++] = (byte) (bits >> 8);
\r
3267 public void WriteBits(int b, int count)
\r
3269 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3270 throw new Exception();
\r
3272 // if (DeflaterConstants.DEBUGGING) {
\r
3273 // Console.WriteLine("writeBits("+b+","+count+")");
\r
3275 bits |= (uint)(b << bitCount);
\r
3276 bitCount += count;
\r
3277 if (bitCount >= 16) {
\r
3278 buf[end++] = (byte) bits;
\r
3279 buf[end++] = (byte) (bits >> 8);
\r
3285 public void WriteShortMSB(int s)
\r
3287 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3288 throw new Exception();
\r
3290 buf[end++] = (byte) (s >> 8);
\r
3291 buf[end++] = (byte) s;
\r
3294 public bool IsFlushed {
\r
3301 /// Flushes the pending buffer into the given output array. If the
\r
3302 /// output array is to small, only a partial flush is done.
\r
3304 /// <param name="output">
\r
3305 /// the output array;
\r
3307 /// <param name="offset">
\r
3308 /// the offset into output array;
\r
3310 /// <param name="length">
\r
3311 /// length the maximum number of bytes to store;
\r
3313 /// <exception name="ArgumentOutOfRangeException">
\r
3314 /// IndexOutOfBoundsException if offset or length are invalid.
\r
3316 public int Flush(byte[] output, int offset, int length)
\r
3318 if (bitCount >= 8) {
\r
3319 buf[end++] = (byte) bits;
\r
3323 if (length > end - start) {
\r
3324 length = end - start;
\r
3325 System.Array.Copy(buf, start, output, offset, length);
\r
3329 System.Array.Copy(buf, start, output, offset, length);
\r
3335 public byte[] ToByteArray()
\r
3337 byte[] ret = new byte[ end - start ];
\r
3338 System.Array.Copy(buf, start, ret, 0, ret.Length);
\r
3346 namespace NZlib.Checksums {
\r
3349 /// Computes Adler32 checksum for a stream of data. An Adler32
\r
3350 /// checksum is not as reliable as a CRC32 checksum, but a lot faster to
\r
3353 /// The specification for Adler32 may be found in RFC 1950.
\r
3354 /// ZLIB Compressed Data Format Specification version 3.3)
\r
3357 /// From that document:
\r
3359 /// "ADLER32 (Adler-32 checksum)
\r
3360 /// This contains a checksum value of the uncompressed data
\r
3361 /// (excluding any dictionary data) computed according to Adler-32
\r
3362 /// algorithm. This algorithm is a 32-bit extension and improvement
\r
3363 /// of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
\r
3366 /// Adler-32 is composed of two sums accumulated per byte: s1 is
\r
3367 /// the sum of all bytes, s2 is the sum of all s1 values. Both sums
\r
3368 /// are done modulo 65521. s1 is initialized to 1, s2 to zero. The
\r
3369 /// Adler-32 checksum is stored as s2*65536 + s1 in most-
\r
3370 /// significant-byte first (network) order."
\r
3372 /// "8.2. The Adler-32 algorithm
\r
3374 /// The Adler-32 algorithm is much faster than the CRC32 algorithm yet
\r
3375 /// still provides an extremely low probability of undetected errors.
\r
3377 /// The modulo on unsigned long accumulators can be delayed for 5552
\r
3378 /// bytes, so the modulo operation time is negligible. If the bytes
\r
3379 /// are a, b, c, the second sum is 3a + 2b + c + 3, and so is position
\r
3380 /// and order sensitive, unlike the first sum, which is just a
\r
3381 /// checksum. That 65521 is prime is important to avoid a possible
\r
3382 /// large class of two-byte errors that leave the check unchanged.
\r
3383 /// (The Fletcher checksum uses 255, which is not prime and which also
\r
3384 /// makes the Fletcher check insensitive to single byte changes 0 -
\r
3387 /// The sum s1 is initialized to 1 instead of zero to make the length
\r
3388 /// of the sequence part of s2, so that the length does not have to be
\r
3389 /// checked separately. (Any sequence of zeroes has a Fletcher
\r
3390 /// checksum of zero.)"
\r
3392 /// <see cref="NZlib.Streams.InflaterInputStream"/>
\r
3393 /// <see cref="NZlib.Streams.DeflaterOutputStream"/>
\r
3394 public sealed class Adler32 : IChecksum
\r
3397 /// largest prime smaller than 65536
\r
3399 readonly static uint BASE = 65521;
\r
3404 /// Returns the Adler32 data checksum computed so far.
\r
3406 public long Value {
\r
3408 return (long) checksum & 0xFFFFFFFFL;
\r
3413 /// Creates a new instance of the <code>Adler32</code> class.
\r
3414 /// The checksum starts off with a value of 1.
\r
3422 /// Resets the Adler32 checksum to the initial value.
\r
3424 public void Reset()
\r
3426 checksum = 1; //Initialize to 1
\r
3430 /// Updates the checksum with the byte b.
\r
3432 /// <param name="bval">
\r
3433 /// the data value to add. The high byte of the int is ignored.
\r
3435 public void Update(int bval)
\r
3437 //We could make a length 1 byte array and call update again, but I
\r
3438 //would rather not have that overhead
\r
3439 uint s1 = checksum & 0xFFFF;
\r
3440 uint s2 = checksum >> 16;
\r
3442 s1 = (s1 + ((uint)bval & 0xFF)) % BASE;
\r
3443 s2 = (s1 + s2) % BASE;
\r
3445 checksum = (s2 << 16) + s1;
\r
3449 /// Updates the checksum with the bytes taken from the array.
\r
3451 /// <param name="buffer">
\r
3452 /// buffer an array of bytes
\r
3454 public void Update(byte[] buffer)
\r
3456 Update(buffer, 0, buffer.Length);
\r
3460 /// Updates the checksum with the bytes taken from the array.
\r
3462 /// <param name="buf">
\r
3463 /// an array of bytes
\r
3465 /// <param name="off">
\r
3466 /// the start of the data used for this update
\r
3468 /// <param name="len">
\r
3469 /// the number of bytes to use for this update
\r
3471 public void Update(byte[] buf, int off, int len)
\r
3473 if (buf == null) {
\r
3474 throw new ArgumentNullException("buf");
\r
3477 if (off < 0 || len < 0 || off + len > buf.Length) {
\r
3478 throw new ArgumentOutOfRangeException();
\r
3481 //(By Per Bothner)
\r
3482 uint s1 = checksum & 0xFFFF;
\r
3483 uint s2 = checksum >> 16;
\r
3486 // We can defer the modulo operation:
\r
3487 // s1 maximally grows from 65521 to 65521 + 255 * 3800
\r
3488 // s2 maximally grows by 3800 * median(s1) = 2090079800 < 2^31
\r
3494 while (--n >= 0) {
\r
3495 s1 = s1 + (uint)(buf[off++] & 0xFF);
\r
3502 checksum = (s2 << 16) | s1;
\r
3507 namespace NZlib.Checksums {
\r
3510 /// Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
\r
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.
\r
3513 /// Polynomials over GF(2) are represented in binary, one bit per coefficient,
\r
3514 /// with the lowest powers in the most significant bit. Then adding polynomials
\r
3515 /// is just exclusive-or, and multiplying a polynomial by x is a right shift by
\r
3516 /// one. If we call the above polynomial p, and represent a byte as the
\r
3517 /// polynomial q, also with the lowest power in the most significant bit (so the
\r
3518 /// byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
\r
3519 /// where a mod b means the remainder after dividing a by b.
\r
3521 /// This calculation is done using the shift-register method of multiplying and
\r
3522 /// taking the remainder. The register is initialized to zero, and for each
\r
3523 /// incoming bit, x^32 is added mod p to the register if the bit is a one (where
\r
3524 /// x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
\r
3525 /// x (which is shifting right by one and adding x^32 mod p if the bit shifted
\r
3526 /// out is a one). We start with the highest power (least significant bit) of
\r
3527 /// q and repeat for all eight bits of q.
\r
3529 /// The table is simply the CRC of all possible eight bit values. This is all
\r
3530 /// the information needed to generate CRC's on data a byte at a time for all
\r
3531 /// combinations of CRC register values and incoming bytes.
\r
3533 public sealed class Crc32 : IChecksum
\r
3535 readonly static uint CrcSeed = 0xFFFFFFFF;
\r
3537 readonly static uint[] CrcTable = new uint[] {
\r
3538 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,
\r
3539 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,
\r
3540 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,
\r
3541 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
\r
3542 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,
\r
3543 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
\r
3544 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
\r
3545 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
\r
3546 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,
\r
3547 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,
\r
3548 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,
\r
3549 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
\r
3550 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,
\r
3551 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
\r
3552 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,
\r
3553 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
\r
3554 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
\r
3555 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
\r
3556 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,
\r
3557 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
\r
3558 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
\r
3559 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,
\r
3560 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,
\r
3561 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
\r
3562 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,
\r
3563 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,
\r
3564 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
\r
3565 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
\r
3566 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344,
\r
3567 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
\r
3568 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,
\r
3569 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
\r
3570 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,
\r
3571 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
\r
3572 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
\r
3573 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
\r
3574 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,
\r
3575 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,
\r
3576 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,
\r
3577 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
\r
3578 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,
\r
3579 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
\r
3580 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,
\r
3581 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
\r
3582 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,
\r
3583 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,
\r
3584 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,
\r
3585 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
\r
3586 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
\r
3587 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,
\r
3588 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,
\r
3593 /// The crc data checksum so far.
\r
3598 /// Returns the CRC32 data checksum computed so far.
\r
3600 public long Value {
\r
3607 /// Resets the CRC32 data checksum as if no update was ever called.
\r
3609 public void Reset()
\r
3615 /// Updates the checksum with the int bval.
\r
3617 /// <param name = "bval">
\r
3618 /// the byte is taken as the lower 8 bits of bval
\r
3620 public void Update(int bval)
\r
3623 crc = CrcTable[(crc ^ bval) & 0xFF] ^ (crc >> 8);
\r
3628 /// Updates the checksum with the bytes taken from the array.
\r
3630 /// <param name="buffer">
\r
3631 /// buffer an array of bytes
\r
3633 public void Update(byte[] buffer)
\r
3635 Update(buffer, 0, buffer.Length);
\r
3639 /// Adds the byte array to the data checksum.
\r
3641 /// <param name = "buf">
\r
3642 /// the buffer which contains the data
\r
3644 /// <param name = "off">
\r
3645 /// the offset in the buffer where the data starts
\r
3647 /// <param name = "len">
\r
3648 /// the length of the data
\r
3650 public void Update(byte[] buf, int off, int len)
\r
3652 if (buf == null) {
\r
3653 throw new ArgumentNullException("buf");
\r
3656 if (off < 0 || len < 0 || off + len > buf.Length) {
\r
3657 throw new ArgumentOutOfRangeException();
\r
3662 while (--len >= 0) {
\r
3663 crc = CrcTable[(crc ^ buf[off++]) & 0xFF] ^ (crc >> 8);
\r
3671 namespace NZlib.Checksums {
\r
3674 /// Interface to compute a data checksum used by checked input/output streams.
\r
3675 /// A data checksum can be updated by one byte or with a byte array. After each
\r
3676 /// update the value of the current checksum can be returned by calling
\r
3677 /// <code>getValue</code>. The complete checksum object can also be reset
\r
3678 /// so it can be used again with new data.
\r
3680 public interface IChecksum
\r
3683 /// Returns the data checksum computed so far.
\r
3690 /// Resets the data checksum as if no update was ever called.
\r
3695 /// Adds one byte to the data checksum.
\r
3697 /// <param name = "bval">
\r
3698 /// the data value to add. The high byte of the int is ignored.
\r
3700 void Update(int bval);
\r
3703 /// Updates the data checksum with the bytes taken from the array.
\r
3705 /// <param name="buffer">
\r
3706 /// buffer an array of bytes
\r
3708 void Update(byte[] buffer);
\r
3711 /// Adds the byte array to the data checksum.
\r
3713 /// <param name = "buf">
\r
3714 /// the buffer which contains the data
\r
3716 /// <param name = "off">
\r
3717 /// the offset in the buffer where the data starts
\r
3719 /// <param name = "len">
\r
3720 /// the length of the data
\r
3722 void Update(byte[] buf, int off, int len);
\r
3726 namespace NZlib.Streams {
\r
3729 /// Contains the output from the Inflation process.
\r
3730 /// We need to have a window so that we can refer backwards into the output stream
\r
3731 /// to repeat stuff.
\r
3733 /// author of the original java version : John Leuner
\r
3735 public class OutputWindow
\r
3737 private static int WINDOW_SIZE = 1 << 15;
\r
3738 private static int WINDOW_MASK = WINDOW_SIZE - 1;
\r
3740 private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
\r
3741 private int window_end = 0;
\r
3742 private int window_filled = 0;
\r
3744 public void Write(int abyte)
\r
3746 if (window_filled++ == WINDOW_SIZE) {
\r
3747 throw new InvalidOperationException("Window full");
\r
3749 window[window_end++] = (byte) abyte;
\r
3750 window_end &= WINDOW_MASK;
\r
3754 private void SlowRepeat(int rep_start, int len, int dist)
\r
3756 while (len-- > 0) {
\r
3757 window[window_end++] = window[rep_start++];
\r
3758 window_end &= WINDOW_MASK;
\r
3759 rep_start &= WINDOW_MASK;
\r
3763 public void Repeat(int len, int dist)
\r
3765 if ((window_filled += len) > WINDOW_SIZE) {
\r
3766 throw new InvalidOperationException("Window full");
\r
3769 int rep_start = (window_end - dist) & WINDOW_MASK;
\r
3770 int border = WINDOW_SIZE - len;
\r
3771 if (rep_start <= border && window_end < border) {
\r
3772 if (len <= dist) {
\r
3773 System.Array.Copy(window, rep_start, window, window_end, len);
\r
3774 window_end += len;
\r
3776 /* We have to copy manually, since the repeat pattern overlaps.
\r
3778 while (len-- > 0) {
\r
3779 window[window_end++] = window[rep_start++];
\r
3783 SlowRepeat(rep_start, len, dist);
\r
3787 public int CopyStored(StreamManipulator input, int len)
\r
3789 len = Math.Min(Math.Min(len, WINDOW_SIZE - window_filled), input.AvailableBytes);
\r
3792 int tailLen = WINDOW_SIZE - window_end;
\r
3793 if (len > tailLen) {
\r
3794 copied = input.CopyBytes(window, window_end, tailLen);
\r
3795 if (copied == tailLen) {
\r
3796 copied += input.CopyBytes(window, 0, len - tailLen);
\r
3799 copied = input.CopyBytes(window, window_end, len);
\r
3802 window_end = (window_end + copied) & WINDOW_MASK;
\r
3803 window_filled += copied;
\r
3807 public void CopyDict(byte[] dict, int offset, int len)
\r
3809 if (window_filled > 0) {
\r
3810 throw new InvalidOperationException();
\r
3813 if (len > WINDOW_SIZE) {
\r
3814 offset += len - WINDOW_SIZE;
\r
3815 len = WINDOW_SIZE;
\r
3817 System.Array.Copy(dict, offset, window, 0, len);
\r
3818 window_end = len & WINDOW_MASK;
\r
3821 public int GetFreeSpace()
\r
3823 return WINDOW_SIZE - window_filled;
\r
3826 public int GetAvailable()
\r
3828 return window_filled;
\r
3831 public int CopyOutput(byte[] output, int offset, int len)
\r
3833 int copy_end = window_end;
\r
3834 if (len > window_filled) {
\r
3835 len = window_filled;
\r
3837 copy_end = (window_end - window_filled + len) & WINDOW_MASK;
\r
3841 int tailLen = len - copy_end;
\r
3843 if (tailLen > 0) {
\r
3844 System.Array.Copy(window, WINDOW_SIZE - tailLen,
\r
3845 output, offset, tailLen);
\r
3846 offset += tailLen;
\r
3849 System.Array.Copy(window, copy_end - len, output, offset, len);
\r
3850 window_filled -= copied;
\r
3851 if (window_filled < 0) {
\r
3852 throw new InvalidOperationException();
\r
3857 public void Reset()
\r
3859 window_filled = window_end = 0;
\r
3864 namespace NZlib.Streams {
\r
3867 /// This class allows us to retrieve a specified amount of bits from
\r
3868 /// the input buffer, as well as copy big byte blocks.
\r
3870 /// It uses an int buffer to store up to 31 bits for direct
\r
3871 /// manipulation. This guarantees that we can get at least 16 bits,
\r
3872 /// but we only need at most 15, so this is all safe.
\r
3874 /// There are some optimizations in this class, for example, you must
\r
3875 /// never peek more then 8 bits more than needed, and you must first
\r
3876 /// peek bits before you may drop them. This is not a general purpose
\r
3877 /// class but optimized for the behaviour of the Inflater.
\r
3879 /// authors of the original java version : John Leuner, Jochen Hoenicke
\r
3881 public class StreamManipulator
\r
3883 private byte[] window;
\r
3884 private int window_start = 0;
\r
3885 private int window_end = 0;
\r
3887 private uint buffer = 0;
\r
3888 private int bits_in_buffer = 0;
\r
3891 /// Get the next n bits but don't increase input pointer. n must be
\r
3892 /// less or equal 16 and if you if this call succeeds, you must drop
\r
3893 /// at least n-8 bits in the next call.
\r
3896 /// the value of the bits, or -1 if not enough bits available. */
\r
3898 public int PeekBits(int n)
\r
3900 if (bits_in_buffer < n) {
\r
3901 if (window_start == window_end) {
\r
3904 buffer |= (uint)((window[window_start++] & 0xff |
\r
3905 (window[window_start++] & 0xff) << 8) << bits_in_buffer);
\r
3906 bits_in_buffer += 16;
\r
3908 return (int)(buffer & ((1 << n) - 1));
\r
3912 /// Drops the next n bits from the input. You should have called peekBits
\r
3913 /// with a bigger or equal n before, to make sure that enough bits are in
\r
3914 /// the bit buffer.
\r
3916 public void DropBits(int n)
\r
3919 bits_in_buffer -= n;
\r
3923 /// Gets the next n bits and increases input pointer. This is equivalent
\r
3924 /// to peekBits followed by dropBits, except for correct error handling.
\r
3927 /// the value of the bits, or -1 if not enough bits available.
\r
3929 public int GetBits(int n)
\r
3931 int bits = PeekBits(n);
\r
3939 /// Gets the number of bits available in the bit buffer. This must be
\r
3940 /// only called when a previous peekBits() returned -1.
\r
3943 /// the number of bits available.
\r
3945 public int AvailableBits {
\r
3947 return bits_in_buffer;
\r
3952 /// Gets the number of bytes available.
\r
3955 /// the number of bytes available.
\r
3957 public int AvailableBytes {
\r
3959 return window_end - window_start + (bits_in_buffer >> 3);
\r
3964 /// Skips to the next byte boundary.
\r
3966 public void SkipToByteBoundary()
\r
3968 buffer >>= (bits_in_buffer & 7);
\r
3969 bits_in_buffer &= ~7;
\r
3972 public bool IsNeedingInput {
\r
3974 return window_start == window_end;
\r
3979 /// Copies length bytes from input buffer to output buffer starting
\r
3980 /// at output[offset]. You have to make sure, that the buffer is
\r
3981 /// byte aligned. If not enough bytes are available, copies fewer
\r
3984 /// <param name="output">
\r
3987 /// <param name="offset">
\r
3988 /// the offset in the buffer.
\r
3990 /// <param name="length">
\r
3991 /// the length to copy, 0 is allowed.
\r
3994 /// the number of bytes copied, 0 if no byte is available.
\r
3996 public int CopyBytes(byte[] output, int offset, int length)
\r
3999 throw new ArgumentOutOfRangeException("length negative");
\r
4001 if ((bits_in_buffer & 7) != 0) {
\r
4002 /* bits_in_buffer may only be 0 or 8 */
\r
4003 throw new InvalidOperationException("Bit buffer is not aligned!");
\r
4007 while (bits_in_buffer > 0 && length > 0) {
\r
4008 output[offset++] = (byte) buffer;
\r
4010 bits_in_buffer -= 8;
\r
4014 if (length == 0) {
\r
4018 int avail = window_end - window_start;
\r
4019 if (length > avail) {
\r
4022 System.Array.Copy(window, window_start, output, offset, length);
\r
4023 window_start += length;
\r
4025 if (((window_start - window_end) & 1) != 0) {
\r
4026 /* We always want an even number of bytes in input, see peekBits */
\r
4027 buffer = (uint)(window[window_start++] & 0xff);
\r
4028 bits_in_buffer = 8;
\r
4030 return count + length;
\r
4033 public StreamManipulator()
\r
4037 public void Reset()
\r
4039 buffer = (uint)(window_start = window_end = bits_in_buffer = 0);
\r
4042 public void SetInput(byte[] buf, int off, int len)
\r
4044 if (window_start < window_end) {
\r
4045 throw new InvalidOperationException("Old input was not completely processed");
\r
4048 int end = off + len;
\r
4050 /* We want to throw an ArrayIndexOutOfBoundsException early. The
\r
4051 * check is very tricky: it also handles integer wrap around.
\r
4053 if (0 > off || off > end || end > buf.Length) {
\r
4054 throw new ArgumentOutOfRangeException();
\r
4057 if ((len & 1) != 0) {
\r
4058 /* We always want an even number of bytes in input, see peekBits */
\r
4059 buffer |= (uint)((buf[off++] & 0xff) << bits_in_buffer);
\r
4060 bits_in_buffer += 8;
\r
4064 window_start = off;
\r
projects / mono.git / blob