4 using NZlib.Checksums;
\r
5 using NZlib.Compression;
\r
8 static int Iterations = 1000;
\r
9 static int BlockSize = 1024;
\r
11 public static void Main (string [] args)
\r
13 if (args.Length == 0 || args.Length > 3) {
\r
14 Console.WriteLine ("Usage: zipmark FILE [ITERATIONS] [BLOCKSIZE]");
\r
18 string filename = args [0];
\r
19 FileInfo file = new FileInfo (filename);
\r
21 Console.WriteLine ("Couldn't find file {0}", filename);
\r
25 FileStream fs = file.OpenRead ();
\r
27 byte [] raw = new byte [file.Length];
\r
28 int count = fs.Read (raw, 0, (int)file.Length);
\r
31 if (count != file.Length) {
\r
32 Console.WriteLine ("Couldn't read file {0}", filename);
\r
36 Deflater def = new Deflater (Deflater.BEST_COMPRESSION, false);
\r
37 Inflater inf = new Inflater (false);
\r
39 // 1. Count deflated size
\r
41 int cooked_size = Deflate (def, raw, null);
\r
42 byte [] cooked = new byte [cooked_size];
\r
44 // 2. Deflate & Inflate
\r
46 if (args.Length > 1)
\r
47 Iterations = Int32.Parse (args [1]);
\r
48 if (args.Length > 2)
\r
49 BlockSize = Int32.Parse (args [2]);
\r
51 for (int i = 0; i < Iterations; ++ i) {
\r
52 Deflate (def, raw, cooked);
\r
53 Inflate (inf, cooked, raw);
\r
59 static int Deflate (Deflater def, byte [] src, byte [] dest)
\r
62 int offset, length, remain;
\r
65 dest = new byte [BlockSize];
\r
74 while (!def.IsFinished) {
\r
75 if (def.IsNeedingInput)
\r
78 remain = Math.Min (dest.Length - offset, BlockSize);
\r
82 length = def.Deflate (dest, offset, remain);
\r
87 return def.TotalOut;
\r
90 static int Inflate (Inflater inf, byte [] src, byte [] dest)
\r
92 int offset, length, remain;
\r
98 while (!inf.IsNeedingInput) {
\r
99 remain = Math.Min (dest.Length - offset, BlockSize);
\r
103 length = inf.Inflate (dest, offset, remain);
\r
107 return inf.TotalOut;
\r
111 // ---------------------- NZipLib sources from here on --------------------------
\r
115 // Copyright (C) 2001 Mike Krueger
\r
117 // This file was translated from java, it was part of the GNU Classpath
\r
118 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
120 // This program is free software; you can redistribute it and/or
\r
121 // modify it under the terms of the GNU General Public License
\r
122 // as published by the Free Software Foundation; either version 2
\r
123 // of the License, or (at your option) any later version.
\r
125 // This program is distributed in the hope that it will be useful,
\r
126 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
127 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
128 // GNU General Public License for more details.
\r
130 // You should have received a copy of the GNU General Public License
\r
131 // along with this program; if not, write to the Free Software
\r
132 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
134 // As a special exception, if you link this library with other files to
\r
135 // produce an executable, this library does not by itself cause the
\r
136 // resulting executable to be covered by the GNU General Public License.
\r
137 // This exception does not however invalidate any other reasons why the
\r
138 // executable file might be covered by the GNU General Public License.
\r
140 namespace NZlib.Compression {
\r
143 /// This is the Deflater class. The deflater class compresses input
\r
144 /// with the deflate algorithm described in RFC 1951. It has several
\r
145 /// compression levels and three different strategies described below.
\r
147 /// This class is <i>not</i> thread safe. This is inherent in the API, due
\r
148 /// to the split of deflate and setInput.
\r
150 /// author of the original java version : Jochen Hoenicke
\r
152 public class Deflater
\r
155 /// The best and slowest compression level. This tries to find very
\r
156 /// long and distant string repetitions.
\r
158 public static int BEST_COMPRESSION = 9;
\r
161 /// The worst but fastest compression level.
\r
163 public static int BEST_SPEED = 1;
\r
166 /// The default compression level.
\r
168 public static int DEFAULT_COMPRESSION = -1;
\r
171 /// This level won't compress at all but output uncompressed blocks.
\r
173 public static int NO_COMPRESSION = 0;
\r
176 /// The default strategy.
\r
178 public static int DEFAULT_STRATEGY = 0;
\r
182 /// This strategy will only allow longer string repetitions. It is
\r
183 /// useful for random data with a small character set.
\r
185 public static int FILTERED = 1;
\r
188 /// This strategy will not look for string repetitions at all. It
\r
189 /// only encodes with Huffman trees (which means, that more common
\r
190 /// characters get a smaller encoding.
\r
192 public static int HUFFMAN_ONLY = 2;
\r
195 /// The compression method. This is the only method supported so far.
\r
196 /// There is no need to use this constant at all.
\r
198 public static int DEFLATED = 8;
\r
201 * The Deflater can do the following state transitions:
\r
203 * (1) -> INIT_STATE ----> INIT_FINISHING_STATE ---.
\r
206 * (3)| SETDICT_STATE ---> SETDICT_FINISHING_STATE |(3)
\r
207 * \ | (3) | ,-------'
\r
210 * (1) -> BUSY_STATE ----> FINISHING_STATE
\r
214 * \_____________________________________/
\r
219 * (1) If we should produce a header we start in INIT_STATE, otherwise
\r
220 * we start in BUSY_STATE.
\r
221 * (2) A dictionary may be set only when we are in INIT_STATE, then
\r
222 * we change the state as indicated.
\r
223 * (3) Whether a dictionary is set or not, on the first call of deflate
\r
224 * we change to BUSY_STATE.
\r
225 * (4) -- intentionally left blank -- :)
\r
226 * (5) FINISHING_STATE is entered, when flush() is called to indicate that
\r
227 * there is no more INPUT. There are also states indicating, that
\r
228 * the header wasn't written yet.
\r
229 * (6) FINISHED_STATE is entered, when everything has been flushed to the
\r
230 * internal pending output buffer.
\r
231 * (7) At any time (7)
\r
235 private static int IS_SETDICT = 0x01;
\r
236 private static int IS_FLUSHING = 0x04;
\r
237 private static int IS_FINISHING = 0x08;
\r
239 private static int INIT_STATE = 0x00;
\r
240 private static int SETDICT_STATE = 0x01;
\r
241 // private static int INIT_FINISHING_STATE = 0x08;
\r
242 // private static int SETDICT_FINISHING_STATE = 0x09;
\r
243 private static int BUSY_STATE = 0x10;
\r
244 private static int FLUSHING_STATE = 0x14;
\r
245 private static int FINISHING_STATE = 0x1c;
\r
246 private static int FINISHED_STATE = 0x1e;
\r
247 private static int CLOSED_STATE = 0x7f;
\r
250 /// Compression level.
\r
255 /// should we include a header.
\r
257 private bool noHeader;
\r
260 // /// Compression strategy.
\r
262 // private int strategy;
\r
265 /// The current state.
\r
270 /// The total bytes of output written.
\r
272 private int totalOut;
\r
275 /// The pending output.
\r
277 private DeflaterPending pending;
\r
280 /// The deflater engine.
\r
282 private DeflaterEngine engine;
\r
285 /// Creates a new deflater with default compression level.
\r
287 public Deflater() : this(DEFAULT_COMPRESSION, false)
\r
293 /// Creates a new deflater with given compression level.
\r
295 /// <param name="lvl">
\r
296 /// the compression level, a value between NO_COMPRESSION
\r
297 /// and BEST_COMPRESSION, or DEFAULT_COMPRESSION.
\r
299 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
\r
300 public Deflater(int lvl) : this(lvl, false)
\r
306 /// Creates a new deflater with given compression level.
\r
308 /// <param name="lvl">
\r
309 /// the compression level, a value between NO_COMPRESSION
\r
310 /// and BEST_COMPRESSION.
\r
312 /// <param name="nowrap">
\r
313 /// true, if we should suppress the deflate header at the
\r
314 /// beginning and the adler checksum at the end of the output. This is
\r
315 /// useful for the GZIP format.
\r
317 /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
\r
318 public Deflater(int lvl, bool nowrap)
\r
320 if (lvl == DEFAULT_COMPRESSION) {
\r
322 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
\r
323 throw new ArgumentOutOfRangeException("lvl");
\r
326 pending = new DeflaterPending();
\r
327 engine = new DeflaterEngine(pending);
\r
328 this.noHeader = nowrap;
\r
329 SetStrategy(DEFAULT_STRATEGY);
\r
336 /// Resets the deflater. The deflater acts afterwards as if it was
\r
337 /// just created with the same compression level and strategy as it
\r
340 public void Reset()
\r
342 state = (noHeader ? BUSY_STATE : INIT_STATE);
\r
349 /// Gets the current adler checksum of the data that was processed so far.
\r
353 return engine.Adler;
\r
358 /// Gets the number of input bytes processed so far.
\r
360 public int TotalIn {
\r
362 return engine.TotalIn;
\r
367 /// Gets the number of output bytes so far.
\r
369 public int TotalOut {
\r
376 /// Flushes the current input block. Further calls to deflate() will
\r
377 /// produce enough output to inflate everything in the current input
\r
378 /// block. This is not part of Sun's JDK so I have made it package
\r
379 /// private. It is used by DeflaterOutputStream to implement
\r
382 public void Flush()
\r
384 state |= IS_FLUSHING;
\r
388 /// Finishes the deflater with the current input block. It is an error
\r
389 /// to give more input after this method was called. This method must
\r
390 /// be called to force all bytes to be flushed.
\r
392 public void Finish()
\r
394 state |= IS_FLUSHING | IS_FINISHING;
\r
398 /// Returns true if the stream was finished and no more output bytes
\r
401 public bool IsFinished {
\r
403 return state == FINISHED_STATE && pending.IsFlushed;
\r
408 /// Returns true, if the input buffer is empty.
\r
409 /// You should then call setInput().
\r
410 /// NOTE: This method can also return true when the stream
\r
413 public bool IsNeedingInput {
\r
415 return engine.NeedsInput();
\r
420 /// Sets the data which should be compressed next. This should be only
\r
421 /// called when needsInput indicates that more input is needed.
\r
422 /// If you call setInput when needsInput() returns false, the
\r
423 /// previous input that is still pending will be thrown away.
\r
424 /// The given byte array should not be changed, before needsInput() returns
\r
426 /// This call is equivalent to <code>setInput(input, 0, input.length)</code>.
\r
428 /// <param name="input">
\r
429 /// the buffer containing the input data.
\r
431 /// <exception cref="System.InvalidOperationException">
\r
432 /// if the buffer was finished() or ended().
\r
434 public void SetInput(byte[] input)
\r
436 SetInput(input, 0, input.Length);
\r
440 /// Sets the data which should be compressed next. This should be
\r
441 /// only called when needsInput indicates that more input is needed.
\r
442 /// The given byte array should not be changed, before needsInput() returns
\r
445 /// <param name="input">
\r
446 /// the buffer containing the input data.
\r
448 /// <param name="off">
\r
449 /// the start of the data.
\r
451 /// <param name="len">
\r
452 /// the length of the data.
\r
454 /// <exception cref="System.InvalidOperationException">
\r
455 /// if the buffer was finished() or ended() or if previous input is still pending.
\r
457 public void SetInput(byte[] input, int off, int len)
\r
459 if ((state & IS_FINISHING) != 0) {
\r
460 throw new InvalidOperationException("finish()/end() already called");
\r
462 engine.SetInput(input, off, len);
\r
466 /// Sets the compression level. There is no guarantee of the exact
\r
467 /// position of the change, but if you call this when needsInput is
\r
468 /// true the change of compression level will occur somewhere near
\r
469 /// before the end of the so far given input.
\r
471 /// <param name="lvl">
\r
472 /// the new compression level.
\r
474 public void SetLevel(int lvl)
\r
476 if (lvl == DEFAULT_COMPRESSION) {
\r
478 } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
\r
479 throw new ArgumentOutOfRangeException("lvl");
\r
483 if (level != lvl) {
\r
485 engine.SetLevel(lvl);
\r
490 /// Sets the compression strategy. Strategy is one of
\r
491 /// DEFAULT_STRATEGY, HUFFMAN_ONLY and FILTERED. For the exact
\r
492 /// position where the strategy is changed, the same as for
\r
493 /// setLevel() applies.
\r
495 /// <param name="stgy">
\r
496 /// the new compression strategy.
\r
498 public void SetStrategy(int stgy)
\r
500 if (stgy != DEFAULT_STRATEGY && stgy != FILTERED && stgy != HUFFMAN_ONLY) {
\r
501 throw new Exception();
\r
503 engine.Strategy = stgy;
\r
507 /// Deflates the current input block to the given array. It returns
\r
508 /// the number of bytes compressed, or 0 if either
\r
509 /// needsInput() or finished() returns true or length is zero.
\r
511 /// <param name="output">
\r
512 /// the buffer where to write the compressed data.
\r
514 public int Deflate(byte[] output)
\r
516 return Deflate(output, 0, output.Length);
\r
520 /// Deflates the current input block to the given array. It returns
\r
521 /// the number of bytes compressed, or 0 if either
\r
522 /// needsInput() or finished() returns true or length is zero.
\r
524 /// <param name="output">
\r
525 /// the buffer where to write the compressed data.
\r
527 /// <param name="offset">
\r
528 /// the offset into the output array.
\r
530 /// <param name="length">
\r
531 /// the maximum number of bytes that may be written.
\r
533 /// <exception cref="System.InvalidOperationException">
\r
534 /// if end() was called.
\r
536 /// <exception cref="System.ArgumentOutOfRangeException">
\r
537 /// if offset and/or length don't match the array length.
\r
539 public int Deflate(byte[] output, int offset, int length)
\r
541 int origLength = length;
\r
543 if (state == CLOSED_STATE) {
\r
544 throw new InvalidOperationException("Deflater closed");
\r
547 if (state < BUSY_STATE) {
\r
548 /* output header */
\r
549 int header = (DEFLATED +
\r
550 ((DeflaterConstants.MAX_WBITS - 8) << 4)) << 8;
\r
551 int level_flags = (level - 1) >> 1;
\r
552 if (level_flags < 0 || level_flags > 3) {
\r
555 header |= level_flags << 6;
\r
556 if ((state & IS_SETDICT) != 0) {
\r
557 /* Dictionary was set */
\r
558 header |= DeflaterConstants.PRESET_DICT;
\r
560 header += 31 - (header % 31);
\r
563 pending.WriteShortMSB(header);
\r
564 if ((state & IS_SETDICT) != 0) {
\r
565 int chksum = engine.Adler;
\r
566 engine.ResetAdler();
\r
567 pending.WriteShortMSB(chksum >> 16);
\r
568 pending.WriteShortMSB(chksum & 0xffff);
\r
571 state = BUSY_STATE | (state & (IS_FLUSHING | IS_FINISHING));
\r
575 int count = pending.Flush(output, offset, length);
\r
580 if (length == 0 || state == FINISHED_STATE) {
\r
584 if (!engine.Deflate((state & IS_FLUSHING) != 0, (state & IS_FINISHING) != 0)) {
\r
585 if (state == BUSY_STATE) {
\r
586 /* We need more input now */
\r
587 return origLength - length;
\r
588 } else if (state == FLUSHING_STATE) {
\r
589 if (level != NO_COMPRESSION) {
\r
590 /* We have to supply some lookahead. 8 bit lookahead
\r
591 * are needed by the zlib inflater, and we must fill
\r
592 * the next byte, so that all bits are flushed.
\r
594 int neededbits = 8 + ((-pending.BitCount) & 7);
\r
595 while (neededbits > 0) {
\r
596 /* write a static tree block consisting solely of
\r
599 pending.WriteBits(2, 10);
\r
603 state = BUSY_STATE;
\r
604 } else if (state == FINISHING_STATE) {
\r
605 pending.AlignToByte();
\r
606 /* We have completed the stream */
\r
608 int adler = engine.Adler;
\r
609 pending.WriteShortMSB(adler >> 16);
\r
610 pending.WriteShortMSB(adler & 0xffff);
\r
612 state = FINISHED_STATE;
\r
616 return origLength - length;
\r
620 /// Sets the dictionary which should be used in the deflate process.
\r
621 /// This call is equivalent to <code>setDictionary(dict, 0, dict.Length)</code>.
\r
623 /// <param name="dict">
\r
624 /// the dictionary.
\r
626 /// <exception cref="System.InvalidOperationException">
\r
627 /// if setInput () or deflate () were already called or another dictionary was already set.
\r
629 public void SetDictionary(byte[] dict)
\r
631 SetDictionary(dict, 0, dict.Length);
\r
635 /// Sets the dictionary which should be used in the deflate process.
\r
636 /// The dictionary should be a byte array containing strings that are
\r
637 /// likely to occur in the data which should be compressed. The
\r
638 /// dictionary is not stored in the compressed output, only a
\r
639 /// checksum. To decompress the output you need to supply the same
\r
640 /// dictionary again.
\r
642 /// <param name="dict">
\r
643 /// the dictionary.
\r
645 /// <param name="offset">
\r
646 /// an offset into the dictionary.
\r
648 /// <param name="length">
\r
649 /// the length of the dictionary.
\r
651 /// <exception cref="System.InvalidOperationException">
\r
652 /// if setInput () or deflate () were already called or another dictionary was already set.
\r
654 public void SetDictionary(byte[] dict, int offset, int length)
\r
656 if (state != INIT_STATE) {
\r
657 throw new InvalidOperationException();
\r
660 state = SETDICT_STATE;
\r
661 engine.SetDictionary(dict, offset, length);
\r
665 // DeflaterConstants.cs
\r
666 // Copyright (C) 2001 Mike Krueger
\r
668 // This file was translated from java, it was part of the GNU Classpath
\r
669 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
671 // This program is free software; you can redistribute it and/or
\r
672 // modify it under the terms of the GNU General Public License
\r
673 // as published by the Free Software Foundation; either version 2
\r
674 // of the License, or (at your option) any later version.
\r
676 // This program is distributed in the hope that it will be useful,
\r
677 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
678 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
679 // GNU General Public License for more details.
\r
681 // You should have received a copy of the GNU General Public License
\r
682 // along with this program; if not, write to the Free Software
\r
683 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
685 // As a special exception, if you link this library with other files to
\r
686 // produce an executable, this library does not by itself cause the
\r
687 // resulting executable to be covered by the GNU General Public License.
\r
688 // This exception does not however invalidate any other reasons why the
\r
689 // executable file might be covered by the GNU General Public License.
\r
691 namespace NZlib.Compression {
\r
694 /// This class contains constants used for the deflater.
\r
696 public class DeflaterConstants
\r
698 public const bool DEBUGGING = false;
\r
700 public const int STORED_BLOCK = 0;
\r
701 public const int STATIC_TREES = 1;
\r
702 public const int DYN_TREES = 2;
\r
703 public const int PRESET_DICT = 0x20;
\r
705 public const int DEFAULT_MEM_LEVEL = 8;
\r
707 public const int MAX_MATCH = 258;
\r
708 public const int MIN_MATCH = 3;
\r
710 public const int MAX_WBITS = 15;
\r
711 public const int WSIZE = 1 << MAX_WBITS;
\r
712 public const int WMASK = WSIZE - 1;
\r
714 public const int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
\r
715 public const int HASH_SIZE = 1 << HASH_BITS;
\r
716 public const int HASH_MASK = HASH_SIZE - 1;
\r
717 public const int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
\r
719 public const int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
\r
720 public const int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
\r
722 public const int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
\r
723 public static int MAX_BLOCK_SIZE = Math.Min(65535, PENDING_BUF_SIZE-5);
\r
725 public const int DEFLATE_STORED = 0;
\r
726 public const int DEFLATE_FAST = 1;
\r
727 public const int DEFLATE_SLOW = 2;
\r
729 public static int[] GOOD_LENGTH = { 0, 4, 4, 4, 4, 8, 8, 8, 32, 32 };
\r
730 public static int[] MAX_LAZY = { 0, 4, 5, 6, 4,16, 16, 32, 128, 258 };
\r
731 public static int[] NICE_LENGTH = { 0, 8,16,32,16,32,128,128, 258, 258 };
\r
732 public static int[] MAX_CHAIN = { 0, 4, 8,32,16,32,128,256,1024,4096 };
\r
733 public static int[] COMPR_FUNC = { 0, 1, 1, 1, 1, 2, 2, 2, 2, 2 };
\r
736 // DeflaterEngine.cs
\r
737 // Copyright (C) 2001 Mike Krueger
\r
739 // This file was translated from java, it was part of the GNU Classpath
\r
740 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
742 // This program is free software; you can redistribute it and/or
\r
743 // modify it under the terms of the GNU General Public License
\r
744 // as published by the Free Software Foundation; either version 2
\r
745 // of the License, or (at your option) any later version.
\r
747 // This program is distributed in the hope that it will be useful,
\r
748 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
749 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
750 // GNU General Public License for more details.
\r
752 // You should have received a copy of the GNU General Public License
\r
753 // along with this program; if not, write to the Free Software
\r
754 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
756 // As a special exception, if you link this library with other files to
\r
757 // produce an executable, this library does not by itself cause the
\r
758 // resulting executable to be covered by the GNU General Public License.
\r
759 // This exception does not however invalidate any other reasons why the
\r
760 // executable file might be covered by the GNU General Public License.
\r
763 namespace NZlib.Compression {
\r
765 public class DeflaterEngine : DeflaterConstants
\r
767 private static int TOO_FAR = 4096;
\r
770 // private byte[] buffer;
\r
771 private short[] head;
\r
772 private short[] prev;
\r
774 private int matchStart, matchLen;
\r
775 private bool prevAvailable;
\r
776 private int blockStart;
\r
777 private int strstart, lookahead;
\r
778 private byte[] window;
\r
780 private int strategy, max_chain, max_lazy, niceLength, goodLength;
\r
783 /// The current compression function.
\r
785 private int comprFunc;
\r
788 /// The input data for compression.
\r
790 private byte[] inputBuf;
\r
793 /// The total bytes of input read.
\r
795 private int totalIn;
\r
798 /// The offset into inputBuf, where input data starts.
\r
800 private int inputOff;
\r
803 /// The end offset of the input data.
\r
805 private int inputEnd;
\r
807 private DeflaterPending pending;
\r
808 private DeflaterHuffman huffman;
\r
811 /// The adler checksum
\r
813 private Adler32 adler;
\r
815 public DeflaterEngine(DeflaterPending pending)
\r
817 this.pending = pending;
\r
818 huffman = new DeflaterHuffman(pending);
\r
819 adler = new Adler32();
\r
821 window = new byte[2*WSIZE];
\r
822 head = new short[HASH_SIZE];
\r
823 prev = new short[WSIZE];
\r
825 /* We start at index 1, to avoid a implementation deficiency, that
\r
826 * we cannot build a repeat pattern at index 0.
\r
828 blockStart = strstart = 1;
\r
831 public void Reset()
\r
835 blockStart = strstart = 1;
\r
838 prevAvailable = false;
\r
839 matchLen = MIN_MATCH - 1;
\r
841 for (int i = 0; i < HASH_SIZE; i++) {
\r
845 for (int i = 0; i < WSIZE; i++) {
\r
850 public void ResetAdler()
\r
857 return (int)adler.Value;
\r
861 public int TotalIn {
\r
867 public int Strategy {
\r
876 public void SetLevel(int lvl)
\r
878 goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
\r
879 max_lazy = DeflaterConstants.MAX_LAZY[lvl];
\r
880 niceLength = DeflaterConstants.NICE_LENGTH[lvl];
\r
881 max_chain = DeflaterConstants.MAX_CHAIN[lvl];
\r
883 if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
\r
884 // if (DeflaterConstants.DEBUGGING) {
\r
885 // Console.WriteLine("Change from "+comprFunc +" to "
\r
886 // + DeflaterConstants.COMPR_FUNC[lvl]);
\r
888 switch (comprFunc) {
\r
889 case DEFLATE_STORED:
\r
890 if (strstart > blockStart) {
\r
891 huffman.FlushStoredBlock(window, blockStart,
\r
892 strstart - blockStart, false);
\r
893 blockStart = strstart;
\r
898 if (strstart > blockStart) {
\r
899 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
901 blockStart = strstart;
\r
905 if (prevAvailable) {
\r
906 huffman.TallyLit(window[strstart-1] & 0xff);
\r
908 if (strstart > blockStart) {
\r
909 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
911 blockStart = strstart;
\r
913 prevAvailable = false;
\r
914 matchLen = MIN_MATCH - 1;
\r
917 comprFunc = COMPR_FUNC[lvl];
\r
921 private void UpdateHash()
\r
923 // if (DEBUGGING) {
\r
924 // Console.WriteLine("updateHash: "+strstart);
\r
926 ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
\r
929 private int InsertString()
\r
932 int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
\r
934 // if (DEBUGGING) {
\r
935 // if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
\r
936 // (window[strstart + 1] << HASH_SHIFT) ^
\r
937 // (window[strstart + 2])) & HASH_MASK)) {
\r
938 // throw new Exception("hash inconsistent: "+hash+"/"
\r
939 // +window[strstart]+","
\r
940 // +window[strstart+1]+","
\r
941 // +window[strstart+2]+","+HASH_SHIFT);
\r
945 prev[strstart & WMASK] = match = head[hash];
\r
946 head[hash] = (short)strstart;
\r
948 return match & 0xffff;
\r
951 public void FillWindow()
\r
953 while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
\r
954 int more = 2*WSIZE - lookahead - strstart;
\r
956 /* If the window is almost full and there is insufficient lookahead,
\r
957 * move the upper half to the lower one to make room in the upper half.
\r
959 if (strstart >= WSIZE + MAX_DIST) {
\r
960 System.Array.Copy(window, WSIZE, window, 0, WSIZE);
\r
961 matchStart -= WSIZE;
\r
963 blockStart -= WSIZE;
\r
965 /* Slide the hash table (could be avoided with 32 bit values
\r
966 * at the expense of memory usage).
\r
968 for (int i = 0; i < HASH_SIZE; i++) {
\r
970 head[i] = m >= WSIZE ? (short) (m - WSIZE) : (short)0;
\r
975 if (more > inputEnd - inputOff) {
\r
976 more = inputEnd - inputOff;
\r
979 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
\r
980 adler.Update(inputBuf, inputOff, more);
\r
985 if (lookahead >= MIN_MATCH) {
\r
991 private bool FindLongestMatch(int curMatch)
\r
993 int chainLength = this.max_chain;
\r
994 int niceLength = this.niceLength;
\r
995 short[] prev = this.prev;
\r
996 int scan = this.strstart;
\r
998 int best_end = this.strstart + matchLen;
\r
999 int best_len = Math.Max(matchLen, MIN_MATCH - 1);
\r
1001 int limit = Math.Max(strstart - MAX_DIST, 0);
\r
1003 int strend = strstart + MAX_MATCH - 1;
\r
1004 byte scan_end1 = window[best_end - 1];
\r
1005 byte scan_end = window[best_end];
\r
1007 /* Do not waste too much time if we already have a good match: */
\r
1008 if (best_len >= this.goodLength) {
\r
1009 chainLength >>= 2;
\r
1012 /* Do not look for matches beyond the end of the input. This is necessary
\r
1013 * to make deflate deterministic.
\r
1015 if (niceLength > lookahead) {
\r
1016 niceLength = lookahead;
\r
1019 if (DeflaterConstants.DEBUGGING && strstart > 2*WSIZE - MIN_LOOKAHEAD) {
\r
1020 throw new InvalidOperationException("need lookahead");
\r
1024 if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
\r
1025 throw new InvalidOperationException("future match");
\r
1027 if (window[curMatch + best_len] != scan_end ||
\r
1028 window[curMatch + best_len - 1] != scan_end1 ||
\r
1029 window[curMatch] != window[scan] ||
\r
1030 window[curMatch+1] != window[scan + 1]) {
\r
1034 match = curMatch + 2;
\r
1037 /* We check for insufficient lookahead only every 8th comparison;
\r
1038 * the 256th check will be made at strstart+258.
\r
1040 while (window[++scan] == window[++match] &&
\r
1041 window[++scan] == window[++match] &&
\r
1042 window[++scan] == window[++match] &&
\r
1043 window[++scan] == window[++match] &&
\r
1044 window[++scan] == window[++match] &&
\r
1045 window[++scan] == window[++match] &&
\r
1046 window[++scan] == window[++match] &&
\r
1047 window[++scan] == window[++match] && scan < strend) ;
\r
1049 if (scan > best_end) {
\r
1050 // if (DeflaterConstants.DEBUGGING && ins_h == 0)
\r
1051 // System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
\r
1052 matchStart = curMatch;
\r
1054 best_len = scan - strstart;
\r
1055 if (best_len >= niceLength) {
\r
1059 scan_end1 = window[best_end-1];
\r
1060 scan_end = window[best_end];
\r
1063 } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
\r
1065 matchLen = Math.Min(best_len, lookahead);
\r
1066 return matchLen >= MIN_MATCH;
\r
1069 public void SetDictionary(byte[] buffer, int offset, int length)
\r
1071 if (DeflaterConstants.DEBUGGING && strstart != 1) {
\r
1072 throw new InvalidOperationException("strstart not 1");
\r
1074 adler.Update(buffer, offset, length);
\r
1075 if (length < MIN_MATCH) {
\r
1078 if (length > MAX_DIST) {
\r
1079 offset += length - MAX_DIST;
\r
1080 length = MAX_DIST;
\r
1083 System.Array.Copy(buffer, offset, window, strstart, length);
\r
1087 while (--length > 0) {
\r
1092 blockStart = strstart;
\r
1095 private bool DeflateStored(bool flush, bool finish)
\r
1097 if (!flush && lookahead == 0) {
\r
1101 strstart += lookahead;
\r
1104 int storedLen = strstart - blockStart;
\r
1106 if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
\r
1107 (blockStart < WSIZE && storedLen >= MAX_DIST) || /* Block may move out of window */
\r
1109 bool lastBlock = finish;
\r
1110 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
\r
1111 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
\r
1112 lastBlock = false;
\r
1115 // if (DeflaterConstants.DEBUGGING) {
\r
1116 // Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
\r
1119 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
\r
1120 blockStart += storedLen;
\r
1121 return !lastBlock;
\r
1126 private bool DeflateFast(bool flush, bool finish)
\r
1128 if (lookahead < MIN_LOOKAHEAD && !flush) {
\r
1132 while (lookahead >= MIN_LOOKAHEAD || flush) {
\r
1133 if (lookahead == 0) {
\r
1134 /* We are flushing everything */
\r
1135 huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
\r
1136 blockStart = strstart;
\r
1141 if (lookahead >= MIN_MATCH &&
\r
1142 (hashHead = InsertString()) != 0 &&
\r
1143 strategy != Deflater.HUFFMAN_ONLY &&
\r
1144 strstart - hashHead <= MAX_DIST &&
\r
1145 FindLongestMatch(hashHead)) {
\r
1146 /* longestMatch sets matchStart and matchLen */
\r
1147 // if (DeflaterConstants.DEBUGGING) {
\r
1148 // for (int i = 0 ; i < matchLen; i++) {
\r
1149 // if (window[strstart+i] != window[matchStart + i]) {
\r
1150 // throw new Exception();
\r
1155 huffman.TallyDist(strstart - matchStart, matchLen);
\r
1157 lookahead -= matchLen;
\r
1158 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
\r
1159 while (--matchLen > 0) {
\r
1165 strstart += matchLen;
\r
1166 if (lookahead >= MIN_MATCH - 1) {
\r
1170 matchLen = MIN_MATCH - 1;
\r
1173 /* No match found */
\r
1174 huffman.TallyLit(window[strstart] & 0xff);
\r
1179 if (huffman.IsFull()) {
\r
1180 bool lastBlock = finish && lookahead == 0;
\r
1181 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
1183 blockStart = strstart;
\r
1184 return !lastBlock;
\r
1190 private bool DeflateSlow(bool flush, bool finish)
\r
1192 if (lookahead < MIN_LOOKAHEAD && !flush) {
\r
1196 while (lookahead >= MIN_LOOKAHEAD || flush) {
\r
1197 if (lookahead == 0) {
\r
1198 if (prevAvailable) {
\r
1199 huffman.TallyLit(window[strstart-1] & 0xff);
\r
1201 prevAvailable = false;
\r
1203 /* We are flushing everything */
\r
1204 if (DeflaterConstants.DEBUGGING && !flush) {
\r
1205 throw new Exception("Not flushing, but no lookahead");
\r
1207 huffman.FlushBlock(window, blockStart, strstart - blockStart,
\r
1209 blockStart = strstart;
\r
1213 int prevMatch = matchStart;
\r
1214 int prevLen = matchLen;
\r
1215 if (lookahead >= MIN_MATCH) {
\r
1216 int hashHead = InsertString();
\r
1217 if (strategy != Deflater.HUFFMAN_ONLY && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead))
\r
1219 /* longestMatch sets matchStart and matchLen */
\r
1221 /* Discard match if too small and too far away */
\r
1222 if (matchLen <= 5 && (strategy == Deflater.FILTERED || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
\r
1223 matchLen = MIN_MATCH - 1;
\r
1228 /* previous match was better */
\r
1229 if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
\r
1230 // if (DeflaterConstants.DEBUGGING) {
\r
1231 // for (int i = 0 ; i < matchLen; i++) {
\r
1232 // if (window[strstart-1+i] != window[prevMatch + i])
\r
1233 // throw new Exception();
\r
1236 huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
\r
1241 if (lookahead >= MIN_MATCH) {
\r
1244 } while (--prevLen > 0);
\r
1247 prevAvailable = false;
\r
1248 matchLen = MIN_MATCH - 1;
\r
1250 if (prevAvailable) {
\r
1251 huffman.TallyLit(window[strstart-1] & 0xff);
\r
1253 prevAvailable = true;
\r
1258 if (huffman.IsFull()) {
\r
1259 int len = strstart - blockStart;
\r
1260 if (prevAvailable) {
\r
1263 bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
\r
1264 huffman.FlushBlock(window, blockStart, len, lastBlock);
\r
1265 blockStart += len;
\r
1266 return !lastBlock;
\r
1272 public bool Deflate(bool flush, bool finish)
\r
1277 bool canFlush = flush && inputOff == inputEnd;
\r
1278 // if (DeflaterConstants.DEBUGGING) {
\r
1279 // Console.WriteLine("window: ["+blockStart+","+strstart+","
\r
1280 // +lookahead+"], "+comprFunc+","+canFlush);
\r
1282 switch (comprFunc) {
\r
1283 case DEFLATE_STORED:
\r
1284 progress = DeflateStored(canFlush, finish);
\r
1286 case DEFLATE_FAST:
\r
1287 progress = DeflateFast(canFlush, finish);
\r
1289 case DEFLATE_SLOW:
\r
1290 progress = DeflateSlow(canFlush, finish);
\r
1293 throw new InvalidOperationException("unknown comprFunc");
\r
1295 } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
\r
1299 public void SetInput(byte[] buf, int off, int len)
\r
1301 if (inputOff < inputEnd) {
\r
1302 throw new InvalidOperationException("Old input was not completely processed");
\r
1305 int end = off + len;
\r
1307 /* We want to throw an ArrayIndexOutOfBoundsException early. The
\r
1308 * check is very tricky: it also handles integer wrap around.
\r
1310 if (0 > off || off > end || end > buf.Length) {
\r
1311 throw new ArgumentOutOfRangeException();
\r
1319 public bool NeedsInput()
\r
1321 return inputEnd == inputOff;
\r
1325 // DeflaterHuffman.cs
\r
1326 // Copyright (C) 2001 Mike Krueger
\r
1328 // This file was translated from java, it was part of the GNU Classpath
\r
1329 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
1331 // This program is free software; you can redistribute it and/or
\r
1332 // modify it under the terms of the GNU General Public License
\r
1333 // as published by the Free Software Foundation; either version 2
\r
1334 // of the License, or (at your option) any later version.
\r
1336 // This program is distributed in the hope that it will be useful,
\r
1337 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
1338 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
1339 // GNU General Public License for more details.
\r
1341 // You should have received a copy of the GNU General Public License
\r
1342 // along with this program; if not, write to the Free Software
\r
1343 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
1345 // As a special exception, if you link this library with other files to
\r
1346 // produce an executable, this library does not by itself cause the
\r
1347 // resulting executable to be covered by the GNU General Public License.
\r
1348 // This exception does not however invalidate any other reasons why the
\r
1349 // executable file might be covered by the GNU General Public License.
\r
1351 namespace NZlib.Compression {
\r
1354 /// This is the DeflaterHuffman class.
\r
1356 /// This class is <i>not</i> thread safe. This is inherent in the API, due
\r
1357 /// to the split of deflate and setInput.
\r
1359 /// author of the original java version : Jochen Hoenicke
\r
1361 public class DeflaterHuffman
\r
1363 private static int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
\r
1364 private static int LITERAL_NUM = 286;
\r
1365 private static int DIST_NUM = 30;
\r
1366 private static int BITLEN_NUM = 19;
\r
1367 private static int REP_3_6 = 16;
\r
1368 private static int REP_3_10 = 17;
\r
1369 private static int REP_11_138 = 18;
\r
1370 private static int EOF_SYMBOL = 256;
\r
1371 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
1373 private static byte[] bit4Reverse = {
\r
1393 public class Tree
\r
1395 public short[] freqs;
\r
1396 public short[] codes;
\r
1397 public byte[] length;
\r
1398 public int[] bl_counts;
\r
1399 public int minNumCodes, numCodes;
\r
1400 public int maxLength;
\r
1401 DeflaterHuffman dh;
\r
1403 public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
\r
1406 this.minNumCodes = minCodes;
\r
1407 this.maxLength = maxLength;
\r
1408 freqs = new short[elems];
\r
1409 bl_counts = new int[maxLength];
\r
1412 public void Reset()
\r
1414 for (int i = 0; i < freqs.Length; i++) {
\r
1421 public void WriteSymbol(int code)
\r
1423 // if (DeflaterConstants.DEBUGGING) {
\r
1425 // // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
\r
1427 dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
\r
1430 public void CheckEmpty()
\r
1432 bool empty = true;
\r
1433 for (int i = 0; i < freqs.Length; i++) {
\r
1434 if (freqs[i] != 0) {
\r
1435 Console.WriteLine("freqs["+i+"] == "+freqs[i]);
\r
1440 throw new Exception();
\r
1442 Console.WriteLine("checkEmpty suceeded!");
\r
1445 public void SetStaticCodes(short[] stCodes, byte[] stLength)
\r
1448 length = stLength;
\r
1451 public void BuildCodes()
\r
1453 int numSymbols = freqs.Length;
\r
1454 int[] nextCode = new int[maxLength];
\r
1456 codes = new short[freqs.Length];
\r
1458 // if (DeflaterConstants.DEBUGGING) {
\r
1459 // Console.WriteLine("buildCodes: "+freqs.Length);
\r
1462 for (int bits = 0; bits < maxLength; bits++) {
\r
1463 nextCode[bits] = code;
\r
1464 code += bl_counts[bits] << (15 - bits);
\r
1465 // if (DeflaterConstants.DEBUGGING) {
\r
1466 // Console.WriteLine("bits: "+(bits+1)+" count: "+bl_counts[bits]
\r
1467 // +" nextCode: "+code); // HACK : Integer.toHexString(
\r
1470 if (DeflaterConstants.DEBUGGING && code != 65536) {
\r
1471 throw new Exception("Inconsistent bl_counts!");
\r
1474 for (int i=0; i < numCodes; i++) {
\r
1475 int bits = length[i];
\r
1477 // if (DeflaterConstants.DEBUGGING) {
\r
1478 // Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+")," // HACK : Integer.toHexString(
\r
1481 codes[i] = BitReverse(nextCode[bits-1]);
\r
1482 nextCode[bits-1] += 1 << (16 - bits);
\r
1487 private void BuildLength(int[] childs)
\r
1489 this.length = new byte [freqs.Length];
\r
1490 int numNodes = childs.Length / 2;
\r
1491 int numLeafs = (numNodes + 1) / 2;
\r
1494 for (int i = 0; i < maxLength; i++) {
\r
1498 /* First calculate optimal bit lengths */
\r
1499 int[] lengths = new int[numNodes];
\r
1500 lengths[numNodes-1] = 0;
\r
1502 for (int i = numNodes - 1; i >= 0; i--) {
\r
1503 if (childs[2*i+1] != -1) {
\r
1504 int bitLength = lengths[i] + 1;
\r
1505 if (bitLength > maxLength) {
\r
1506 bitLength = maxLength;
\r
1509 lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
\r
1512 int bitLength = lengths[i];
\r
1513 bl_counts[bitLength - 1]++;
\r
1514 this.length[childs[2*i]] = (byte) lengths[i];
\r
1518 // if (DeflaterConstants.DEBUGGING) {
\r
1519 // Console.WriteLine("Tree "+freqs.Length+" lengths:");
\r
1520 // for (int i=0; i < numLeafs; i++) {
\r
1521 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
\r
1522 // + " len: "+length[childs[2*i]]);
\r
1526 if (overflow == 0) {
\r
1530 int incrBitLen = maxLength - 1;
\r
1532 /* Find the first bit length which could increase: */
\r
1533 while (bl_counts[--incrBitLen] == 0)
\r
1536 /* Move this node one down and remove a corresponding
\r
1537 * amount of overflow nodes.
\r
1540 bl_counts[incrBitLen]--;
\r
1541 bl_counts[++incrBitLen]++;
\r
1542 overflow -= 1 << (maxLength - 1 - incrBitLen);
\r
1543 } while (overflow > 0 && incrBitLen < maxLength - 1);
\r
1544 } while (overflow > 0);
\r
1546 /* We may have overshot above. Move some nodes from maxLength to
\r
1547 * maxLength-1 in that case.
\r
1549 bl_counts[maxLength-1] += overflow;
\r
1550 bl_counts[maxLength-2] -= overflow;
\r
1552 /* Now recompute all bit lengths, scanning in increasing
\r
1553 * frequency. It is simpler to reconstruct all lengths instead of
\r
1554 * fixing only the wrong ones. This idea is taken from 'ar'
\r
1555 * written by Haruhiko Okumura.
\r
1557 * The nodes were inserted with decreasing frequency into the childs
\r
1560 int nodePtr = 2 * numLeafs;
\r
1561 for (int bits = maxLength; bits != 0; bits--) {
\r
1562 int n = bl_counts[bits-1];
\r
1564 int childPtr = 2*childs[nodePtr++];
\r
1565 if (childs[childPtr + 1] == -1) {
\r
1566 /* We found another leaf */
\r
1567 length[childs[childPtr]] = (byte) bits;
\r
1572 // if (DeflaterConstants.DEBUGGING) {
\r
1573 // Console.WriteLine("*** After overflow elimination. ***");
\r
1574 // for (int i=0; i < numLeafs; i++) {
\r
1575 // Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
\r
1576 // + " len: "+length[childs[2*i]]);
\r
1581 public void BuildTree()
\r
1583 int numSymbols = freqs.Length;
\r
1585 /* heap is a priority queue, sorted by frequency, least frequent
\r
1586 * nodes first. The heap is a binary tree, with the property, that
\r
1587 * the parent node is smaller than both child nodes. This assures
\r
1588 * that the smallest node is the first parent.
\r
1590 * The binary tree is encoded in an array: 0 is root node and
\r
1591 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
\r
1593 int[] heap = new int[numSymbols];
\r
1596 for (int n = 0; n < numSymbols; n++) {
\r
1597 int freq = freqs[n];
\r
1599 /* Insert n into heap */
\r
1600 int pos = heapLen++;
\r
1602 while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
\r
1603 heap[pos] = heap[ppos];
\r
1612 /* We could encode a single literal with 0 bits but then we
\r
1613 * don't see the literals. Therefore we force at least two
\r
1614 * literals to avoid this case. We don't care about order in
\r
1615 * this case, both literals get a 1 bit code.
\r
1617 while (heapLen < 2) {
\r
1618 int node = maxCode < 2 ? ++maxCode : 0;
\r
1619 heap[heapLen++] = node;
\r
1622 numCodes = Math.Max(maxCode + 1, minNumCodes);
\r
1624 int numLeafs = heapLen;
\r
1625 int[] childs = new int[4*heapLen - 2];
\r
1626 int[] values = new int[2*heapLen - 1];
\r
1627 int numNodes = numLeafs;
\r
1628 for (int i = 0; i < heapLen; i++) {
\r
1629 int node = heap[i];
\r
1630 childs[2*i] = node;
\r
1631 childs[2*i+1] = -1;
\r
1632 values[i] = freqs[node] << 8;
\r
1636 /* Construct the Huffman tree by repeatedly combining the least two
\r
1640 int first = heap[0];
\r
1641 int last = heap[--heapLen];
\r
1643 /* Propagate the hole to the leafs of the heap */
\r
1646 while (path < heapLen) {
\r
1647 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
\r
1651 heap[ppos] = heap[path];
\r
1653 path = path * 2 + 1;
\r
1656 /* Now propagate the last element down along path. Normally
\r
1657 * it shouldn't go too deep.
\r
1659 int lastVal = values[last];
\r
1660 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
\r
1661 heap[path] = heap[ppos];
\r
1663 heap[path] = last;
\r
1666 int second = heap[0];
\r
1668 /* Create a new node father of first and second */
\r
1669 last = numNodes++;
\r
1670 childs[2*last] = first;
\r
1671 childs[2*last+1] = second;
\r
1672 int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
\r
1673 values[last] = lastVal = values[first] + values[second] - mindepth + 1;
\r
1675 /* Again, propagate the hole to the leafs */
\r
1678 while (path < heapLen) {
\r
1679 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
\r
1683 heap[ppos] = heap[path];
\r
1685 path = ppos * 2 + 1;
\r
1688 /* Now propagate the new element down along path */
\r
1689 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
\r
1690 heap[path] = heap[ppos];
\r
1692 heap[path] = last;
\r
1693 } while (heapLen > 1);
\r
1695 if (heap[0] != childs.Length / 2 - 1) {
\r
1696 throw new Exception("Weird!");
\r
1698 BuildLength(childs);
\r
1701 public int GetEncodedLength()
\r
1704 for (int i = 0; i < freqs.Length; i++) {
\r
1705 len += freqs[i] * length[i];
\r
1710 public void CalcBLFreq(Tree blTree)
\r
1712 int max_count; /* max repeat count */
\r
1713 int min_count; /* min repeat count */
\r
1714 int count; /* repeat count of the current code */
\r
1715 int curlen = -1; /* length of current code */
\r
1718 while (i < numCodes) {
\r
1720 int nextlen = length[i];
\r
1721 if (nextlen == 0) {
\r
1727 if (curlen != nextlen) {
\r
1728 blTree.freqs[nextlen]++;
\r
1735 while (i < numCodes && curlen == length[i]) {
\r
1737 if (++count >= max_count) {
\r
1742 if (count < min_count) {
\r
1743 blTree.freqs[curlen] += (short)count;
\r
1744 } else if (curlen != 0) {
\r
1745 blTree.freqs[REP_3_6]++;
\r
1746 } else if (count <= 10) {
\r
1747 blTree.freqs[REP_3_10]++;
\r
1749 blTree.freqs[REP_11_138]++;
\r
1754 public void WriteTree(Tree blTree)
\r
1756 int max_count; /* max repeat count */
\r
1757 int min_count; /* min repeat count */
\r
1758 int count; /* repeat count of the current code */
\r
1759 int curlen = -1; /* length of current code */
\r
1762 while (i < numCodes) {
\r
1764 int nextlen = length[i];
\r
1765 if (nextlen == 0) {
\r
1771 if (curlen != nextlen) {
\r
1772 blTree.WriteSymbol(nextlen);
\r
1779 while (i < numCodes && curlen == length[i]) {
\r
1781 if (++count >= max_count) {
\r
1786 if (count < min_count) {
\r
1787 while (count-- > 0) {
\r
1788 blTree.WriteSymbol(curlen);
\r
1791 else if (curlen != 0) {
\r
1792 blTree.WriteSymbol(REP_3_6);
\r
1793 dh.pending.WriteBits(count - 3, 2);
\r
1794 } else if (count <= 10) {
\r
1795 blTree.WriteSymbol(REP_3_10);
\r
1796 dh.pending.WriteBits(count - 3, 3);
\r
1798 blTree.WriteSymbol(REP_11_138);
\r
1799 dh.pending.WriteBits(count - 11, 7);
\r
1805 public DeflaterPending pending;
\r
1806 private Tree literalTree, distTree, blTree;
\r
1808 private short[] d_buf;
\r
1809 private byte[] l_buf;
\r
1810 private int last_lit;
\r
1811 private int extra_bits;
\r
1813 private static short[] staticLCodes;
\r
1814 private static byte[] staticLLength;
\r
1815 private static short[] staticDCodes;
\r
1816 private static byte[] staticDLength;
\r
1819 /// Reverse the bits of a 16 bit value.
\r
1821 public static short BitReverse(int value)
\r
1823 return (short) (bit4Reverse[value & 0xF] << 12
\r
1824 | bit4Reverse[(value >> 4) & 0xF] << 8
\r
1825 | bit4Reverse[(value >> 8) & 0xF] << 4
\r
1826 | bit4Reverse[value >> 12]);
\r
1830 static DeflaterHuffman()
\r
1832 /* See RFC 1951 3.2.6 */
\r
1833 /* Literal codes */
\r
1834 staticLCodes = new short[LITERAL_NUM];
\r
1835 staticLLength = new byte[LITERAL_NUM];
\r
1838 staticLCodes[i] = BitReverse((0x030 + i) << 8);
\r
1839 staticLLength[i++] = 8;
\r
1842 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
\r
1843 staticLLength[i++] = 9;
\r
1846 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
\r
1847 staticLLength[i++] = 7;
\r
1849 while (i < LITERAL_NUM) {
\r
1850 staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
\r
1851 staticLLength[i++] = 8;
\r
1854 /* Distant codes */
\r
1855 staticDCodes = new short[DIST_NUM];
\r
1856 staticDLength = new byte[DIST_NUM];
\r
1857 for (i = 0; i < DIST_NUM; i++) {
\r
1858 staticDCodes[i] = BitReverse(i << 11);
\r
1859 staticDLength[i] = 5;
\r
1863 public DeflaterHuffman(DeflaterPending pending)
\r
1865 this.pending = pending;
\r
1867 literalTree = new Tree(this, LITERAL_NUM, 257, 15);
\r
1868 distTree = new Tree(this, DIST_NUM, 1, 15);
\r
1869 blTree = new Tree(this, BITLEN_NUM, 4, 7);
\r
1871 d_buf = new short[BUFSIZE];
\r
1872 l_buf = new byte [BUFSIZE];
\r
1875 public void Reset()
\r
1879 literalTree.Reset();
\r
1884 private int L_code(int len)
\r
1891 while (len >= 8) {
\r
1895 return code + len;
\r
1898 private int D_code(int distance)
\r
1901 while (distance >= 4) {
\r
1905 return code + distance;
\r
1908 public void SendAllTrees(int blTreeCodes)
\r
1910 blTree.BuildCodes();
\r
1911 literalTree.BuildCodes();
\r
1912 distTree.BuildCodes();
\r
1913 pending.WriteBits(literalTree.numCodes - 257, 5);
\r
1914 pending.WriteBits(distTree.numCodes - 1, 5);
\r
1915 pending.WriteBits(blTreeCodes - 4, 4);
\r
1916 for (int rank = 0; rank < blTreeCodes; rank++) {
\r
1917 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
\r
1919 literalTree.WriteTree(blTree);
\r
1920 distTree.WriteTree(blTree);
\r
1921 // if (DeflaterConstants.DEBUGGING) {
\r
1922 // blTree.CheckEmpty();
\r
1926 public void CompressBlock()
\r
1928 for (int i = 0; i < last_lit; i++) {
\r
1929 int litlen = l_buf[i] & 0xff;
\r
1930 int dist = d_buf[i];
\r
1931 if (dist-- != 0) {
\r
1932 // if (DeflaterConstants.DEBUGGING) {
\r
1933 // Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
\r
1936 int lc = L_code(litlen);
\r
1937 literalTree.WriteSymbol(lc);
\r
1939 int bits = (lc - 261) / 4;
\r
1940 if (bits > 0 && bits <= 5) {
\r
1941 pending.WriteBits(litlen & ((1 << bits) - 1), bits);
\r
1944 int dc = D_code(dist);
\r
1945 distTree.WriteSymbol(dc);
\r
1947 bits = dc / 2 - 1;
\r
1949 pending.WriteBits(dist & ((1 << bits) - 1), bits);
\r
1952 // if (DeflaterConstants.DEBUGGING) {
\r
1953 // if (litlen > 32 && litlen < 127) {
\r
1954 // Console.Write("("+(char)litlen+"): ");
\r
1956 // Console.Write("{"+litlen+"}: ");
\r
1959 literalTree.WriteSymbol(litlen);
\r
1962 // if (DeflaterConstants.DEBUGGING) {
\r
1963 // Console.Write("EOF: ");
\r
1965 literalTree.WriteSymbol(EOF_SYMBOL);
\r
1966 // if (DeflaterConstants.DEBUGGING) {
\r
1967 // literalTree.CheckEmpty();
\r
1968 // distTree.CheckEmpty();
\r
1972 public void FlushStoredBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
\r
1974 // if (DeflaterConstants.DEBUGGING) {
\r
1975 // Console.WriteLine("Flushing stored block "+ stored_len);
\r
1977 pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1)
\r
1978 + (lastBlock ? 1 : 0), 3);
\r
1979 pending.AlignToByte();
\r
1980 pending.WriteShort(stored_len);
\r
1981 pending.WriteShort(~stored_len);
\r
1982 pending.WriteBlock(stored, stored_offset, stored_len);
\r
1986 public void FlushBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
\r
1988 literalTree.freqs[EOF_SYMBOL]++;
\r
1991 literalTree.BuildTree();
\r
1992 distTree.BuildTree();
\r
1994 /* Calculate bitlen frequency */
\r
1995 literalTree.CalcBLFreq(blTree);
\r
1996 distTree.CalcBLFreq(blTree);
\r
1998 /* Build bitlen tree */
\r
1999 blTree.BuildTree();
\r
2001 int blTreeCodes = 4;
\r
2002 for (int i = 18; i > blTreeCodes; i--) {
\r
2003 if (blTree.length[BL_ORDER[i]] > 0) {
\r
2004 blTreeCodes = i+1;
\r
2007 int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
\r
2008 literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
\r
2011 int static_len = extra_bits;
\r
2012 for (int i = 0; i < LITERAL_NUM; i++) {
\r
2013 static_len += literalTree.freqs[i] * staticLLength[i];
\r
2015 for (int i = 0; i < DIST_NUM; i++) {
\r
2016 static_len += distTree.freqs[i] * staticDLength[i];
\r
2018 if (opt_len >= static_len) {
\r
2019 /* Force static trees */
\r
2020 opt_len = static_len;
\r
2023 if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) {
\r
2025 // if (DeflaterConstants.DEBUGGING) {
\r
2026 // Console.WriteLine("Storing, since " + stored_len + " < " + opt_len
\r
2027 // + " <= " + static_len);
\r
2029 FlushStoredBlock(stored, stored_offset, stored_len, lastBlock);
\r
2030 } else if (opt_len == static_len) {
\r
2031 /* Encode with static tree */
\r
2032 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
\r
2033 literalTree.SetStaticCodes(staticLCodes, staticLLength);
\r
2034 distTree.SetStaticCodes(staticDCodes, staticDLength);
\r
2038 /* Encode with dynamic tree */
\r
2039 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
\r
2040 SendAllTrees(blTreeCodes);
\r
2046 public bool IsFull()
\r
2048 return last_lit + 16 >= BUFSIZE; // HACK: This was == 'last_lit == BUFSIZE', but errors occured with DeflateFast
\r
2051 public bool TallyLit(int lit)
\r
2053 // if (DeflaterConstants.DEBUGGING) {
\r
2054 // if (lit > 32 && lit < 127) {
\r
2055 // Console.WriteLine("("+(char)lit+")");
\r
2057 // Console.WriteLine("{"+lit+"}");
\r
2060 d_buf[last_lit] = 0;
\r
2061 l_buf[last_lit++] = (byte)lit;
\r
2062 literalTree.freqs[lit]++;
\r
2066 public bool TallyDist(int dist, int len)
\r
2068 // if (DeflaterConstants.DEBUGGING) {
\r
2069 // Console.WriteLine("["+dist+","+len+"]");
\r
2072 d_buf[last_lit] = (short)dist;
\r
2073 l_buf[last_lit++] = (byte)(len - 3);
\r
2075 int lc = L_code(len - 3);
\r
2076 literalTree.freqs[lc]++;
\r
2077 if (lc >= 265 && lc < 285) {
\r
2078 extra_bits += (lc - 261) / 4;
\r
2081 int dc = D_code(dist - 1);
\r
2082 distTree.freqs[dc]++;
\r
2084 extra_bits += dc / 2 - 1;
\r
2090 // DeflaterPending.cs
\r
2091 // Copyright (C) 2001 Mike Krueger
\r
2093 // This file was translated from java, it was part of the GNU Classpath
\r
2094 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
2096 // This program is free software; you can redistribute it and/or
\r
2097 // modify it under the terms of the GNU General Public License
\r
2098 // as published by the Free Software Foundation; either version 2
\r
2099 // of the License, or (at your option) any later version.
\r
2101 // This program is distributed in the hope that it will be useful,
\r
2102 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
2103 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
2104 // GNU General Public License for more details.
\r
2106 // You should have received a copy of the GNU General Public License
\r
2107 // along with this program; if not, write to the Free Software
\r
2108 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
2110 // As a special exception, if you link this library with other files to
\r
2111 // produce an executable, this library does not by itself cause the
\r
2112 // resulting executable to be covered by the GNU General Public License.
\r
2113 // This exception does not however invalidate any other reasons why the
\r
2114 // executable file might be covered by the GNU General Public License.
\r
2117 namespace NZlib.Compression {
\r
2120 /// This class stores the pending output of the Deflater.
\r
2122 /// author of the original java version : Jochen Hoenicke
\r
2124 public class DeflaterPending : PendingBuffer
\r
2126 public DeflaterPending() : base(DeflaterConstants.PENDING_BUF_SIZE)
\r
2132 // Copyright (C) 2001 Mike Krueger
\r
2134 // This file was translated from java, it was part of the GNU Classpath
\r
2135 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
2137 // This program is free software; you can redistribute it and/or
\r
2138 // modify it under the terms of the GNU General Public License
\r
2139 // as published by the Free Software Foundation; either version 2
\r
2140 // of the License, or (at your option) any later version.
\r
2142 // This program is distributed in the hope that it will be useful,
\r
2143 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
2144 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
2145 // GNU General Public License for more details.
\r
2147 // You should have received a copy of the GNU General Public License
\r
2148 // along with this program; if not, write to the Free Software
\r
2149 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
2151 // As a special exception, if you link this library with other files to
\r
2152 // produce an executable, this library does not by itself cause the
\r
2153 // resulting executable to be covered by the GNU General Public License.
\r
2154 // This exception does not however invalidate any other reasons why the
\r
2155 // executable file might be covered by the GNU General Public License.
\r
2157 namespace NZlib.Compression {
\r
2160 /// Inflater is used to decompress data that has been compressed according
\r
2161 /// to the "deflate" standard described in rfc1950.
\r
2163 /// The usage is as following. First you have to set some input with
\r
2164 /// <code>setInput()</code>, then inflate() it. If inflate doesn't
\r
2165 /// inflate any bytes there may be three reasons:
\r
2167 /// <li>needsInput() returns true because the input buffer is empty.
\r
2168 /// You have to provide more input with <code>setInput()</code>.
\r
2169 /// NOTE: needsInput() also returns true when, the stream is finished.
\r
2171 /// <li>needsDictionary() returns true, you have to provide a preset
\r
2172 /// dictionary with <code>setDictionary()</code>.</li>
\r
2173 /// <li>finished() returns true, the inflater has finished.</li>
\r
2175 /// Once the first output byte is produced, a dictionary will not be
\r
2176 /// needed at a later stage.
\r
2178 /// author of the original java version : John Leuner, Jochen Hoenicke
\r
2180 public class Inflater
\r
2183 /// Copy lengths for literal codes 257..285
\r
2185 private static int[] CPLENS = {
\r
2186 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
\r
2187 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
\r
2191 /// Extra bits for literal codes 257..285
\r
2193 private static int[] CPLEXT = {
\r
2194 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
\r
2195 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
\r
2199 /// Copy offsets for distance codes 0..29
\r
2201 private static int[] CPDIST = {
\r
2202 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
\r
2203 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
\r
2204 8193, 12289, 16385, 24577
\r
2208 /// Extra bits for distance codes
\r
2210 private static int[] CPDEXT = {
\r
2211 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
\r
2212 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
\r
2217 /// This are the state in which the inflater can be.
\r
2219 private const int DECODE_HEADER = 0;
\r
2220 private const int DECODE_DICT = 1;
\r
2221 private const int DECODE_BLOCKS = 2;
\r
2222 private const int DECODE_STORED_LEN1 = 3;
\r
2223 private const int DECODE_STORED_LEN2 = 4;
\r
2224 private const int DECODE_STORED = 5;
\r
2225 private const int DECODE_DYN_HEADER = 6;
\r
2226 private const int DECODE_HUFFMAN = 7;
\r
2227 private const int DECODE_HUFFMAN_LENBITS = 8;
\r
2228 private const int DECODE_HUFFMAN_DIST = 9;
\r
2229 private const int DECODE_HUFFMAN_DISTBITS = 10;
\r
2230 private const int DECODE_CHKSUM = 11;
\r
2231 private const int FINISHED = 12;
\r
2234 /// This variable contains the current state.
\r
2239 /// The adler checksum of the dictionary or of the decompressed
\r
2240 /// stream, as it is written in the header resp. footer of the
\r
2241 /// compressed stream.
\r
2242 /// Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
\r
2244 private int readAdler;
\r
2247 /// The number of bits needed to complete the current state. This
\r
2248 /// is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
\r
2249 /// DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
\r
2251 private int neededBits;
\r
2252 private int repLength, repDist;
\r
2253 private int uncomprLen;
\r
2256 /// True, if the last block flag was set in the last block of the
\r
2257 /// inflated stream. This means that the stream ends after the
\r
2258 /// current block.
\r
2260 private bool isLastBlock;
\r
2263 /// The total number of inflated bytes.
\r
2265 private int totalOut;
\r
2268 /// The total number of bytes set with setInput(). This is not the
\r
2269 /// value returned by getTotalIn(), since this also includes the
\r
2270 /// unprocessed input.
\r
2272 private int totalIn;
\r
2275 /// This variable stores the nowrap flag that was given to the constructor.
\r
2276 /// True means, that the inflated stream doesn't contain a header nor the
\r
2277 /// checksum in the footer.
\r
2279 private bool nowrap;
\r
2281 private StreamManipulator input;
\r
2282 private OutputWindow outputWindow;
\r
2283 private InflaterDynHeader dynHeader;
\r
2284 private InflaterHuffmanTree litlenTree, distTree;
\r
2285 private Adler32 adler;
\r
2288 /// Creates a new inflater.
\r
2290 public Inflater() : this(false)
\r
2295 /// Creates a new inflater.
\r
2297 /// <param name="nowrap">
\r
2298 /// true if no header and checksum field appears in the
\r
2299 /// stream. This is used for GZIPed input. For compatibility with
\r
2300 /// Sun JDK you should provide one byte of input more than needed in
\r
2303 public Inflater(bool nowrap)
\r
2305 this.nowrap = nowrap;
\r
2306 this.adler = new Adler32();
\r
2307 input = new StreamManipulator();
\r
2308 outputWindow = new OutputWindow();
\r
2309 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
\r
2313 /// Resets the inflater so that a new stream can be decompressed. All
\r
2314 /// pending input and output will be discarded.
\r
2316 public void Reset()
\r
2318 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
\r
2319 totalIn = totalOut = 0;
\r
2321 outputWindow.Reset();
\r
2323 litlenTree = null;
\r
2325 isLastBlock = false;
\r
2330 /// Decodes the deflate header.
\r
2333 /// false if more input is needed.
\r
2335 /// <exception cref="System.FormatException">
\r
2336 /// if header is invalid.
\r
2338 private bool DecodeHeader()
\r
2340 int header = input.PeekBits(16);
\r
2344 input.DropBits(16);
\r
2345 /* The header is written in "wrong" byte order */
\r
2346 header = ((header << 8) | (header >> 8)) & 0xffff;
\r
2347 if (header % 31 != 0) {
\r
2348 throw new FormatException("Header checksum illegal");
\r
2351 if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) {
\r
2352 throw new FormatException("Compression Method unknown");
\r
2355 /* Maximum size of the backwards window in bits.
\r
2356 * We currently ignore this, but we could use it to make the
\r
2357 * inflater window more space efficient. On the other hand the
\r
2358 * full window (15 bits) is needed most times, anyway.
\r
2359 int max_wbits = ((header & 0x7000) >> 12) + 8;
\r
2362 if ((header & 0x0020) == 0) { // Dictionary flag?
\r
2363 mode = DECODE_BLOCKS;
\r
2365 mode = DECODE_DICT;
\r
2372 /// Decodes the dictionary checksum after the deflate header.
\r
2375 /// false if more input is needed.
\r
2377 private bool DecodeDict()
\r
2379 while (neededBits > 0) {
\r
2380 int dictByte = input.PeekBits(8);
\r
2381 if (dictByte < 0) {
\r
2384 input.DropBits(8);
\r
2385 readAdler = (readAdler << 8) | dictByte;
\r
2392 /// Decodes the huffman encoded symbols in the input stream.
\r
2395 /// false if more input is needed, true if output window is
\r
2396 /// full or the current block ends.
\r
2398 /// <exception cref="System.FormatException">
\r
2399 /// if deflated stream is invalid.
\r
2401 private bool DecodeHuffman()
\r
2403 int free = outputWindow.GetFreeSpace();
\r
2404 while (free >= 258) {
\r
2407 case DECODE_HUFFMAN:
\r
2408 /* This is the inner loop so it is optimized a bit */
\r
2409 while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) {
\r
2410 outputWindow.Write(symbol);
\r
2411 if (--free < 258) {
\r
2415 if (symbol < 257) {
\r
2419 /* symbol == 256: end of block */
\r
2421 litlenTree = null;
\r
2422 mode = DECODE_BLOCKS;
\r
2428 repLength = CPLENS[symbol - 257];
\r
2429 neededBits = CPLEXT[symbol - 257];
\r
2430 } catch (Exception) {
\r
2431 throw new FormatException("Illegal rep length code");
\r
2433 goto case DECODE_HUFFMAN_LENBITS;/* fall through */
\r
2434 case DECODE_HUFFMAN_LENBITS:
\r
2435 if (neededBits > 0) {
\r
2436 mode = DECODE_HUFFMAN_LENBITS;
\r
2437 int i = input.PeekBits(neededBits);
\r
2441 input.DropBits(neededBits);
\r
2444 mode = DECODE_HUFFMAN_DIST;
\r
2445 goto case DECODE_HUFFMAN_DIST;/* fall through */
\r
2446 case DECODE_HUFFMAN_DIST:
\r
2447 symbol = distTree.GetSymbol(input);
\r
2452 repDist = CPDIST[symbol];
\r
2453 neededBits = CPDEXT[symbol];
\r
2454 } catch (Exception) {
\r
2455 throw new FormatException("Illegal rep dist code");
\r
2458 goto case DECODE_HUFFMAN_DISTBITS;/* fall through */
\r
2459 case DECODE_HUFFMAN_DISTBITS:
\r
2460 if (neededBits > 0) {
\r
2461 mode = DECODE_HUFFMAN_DISTBITS;
\r
2462 int i = input.PeekBits(neededBits);
\r
2466 input.DropBits(neededBits);
\r
2469 outputWindow.Repeat(repLength, repDist);
\r
2470 free -= repLength;
\r
2471 mode = DECODE_HUFFMAN;
\r
2474 throw new FormatException();
\r
2481 /// Decodes the adler checksum after the deflate stream.
\r
2484 /// false if more input is needed.
\r
2486 /// <exception cref="System.FormatException">
\r
2487 /// DataFormatException, if checksum doesn't match.
\r
2489 private bool DecodeChksum()
\r
2491 while (neededBits > 0) {
\r
2492 int chkByte = input.PeekBits(8);
\r
2493 if (chkByte < 0) {
\r
2496 input.DropBits(8);
\r
2497 readAdler = (readAdler << 8) | chkByte;
\r
2500 if ((int) adler.Value != readAdler) {
\r
2501 throw new FormatException("Adler chksum doesn't match: "
\r
2502 + (int)adler.Value
\r
2503 + " vs. " + readAdler);
\r
2510 /// Decodes the deflated stream.
\r
2513 /// false if more input is needed, or if finished.
\r
2515 /// <exception cref="System.FormatException">
\r
2516 /// DataFormatException, if deflated stream is invalid.
\r
2518 private bool Decode()
\r
2521 case DECODE_HEADER:
\r
2522 return DecodeHeader();
\r
2524 return DecodeDict();
\r
2525 case DECODE_CHKSUM:
\r
2526 return DecodeChksum();
\r
2528 case DECODE_BLOCKS:
\r
2529 if (isLastBlock) {
\r
2534 input.SkipToByteBoundary();
\r
2536 mode = DECODE_CHKSUM;
\r
2541 int type = input.PeekBits(3);
\r
2545 input.DropBits(3);
\r
2547 if ((type & 1) != 0) {
\r
2548 isLastBlock = true;
\r
2550 switch (type >> 1) {
\r
2551 case DeflaterConstants.STORED_BLOCK:
\r
2552 input.SkipToByteBoundary();
\r
2553 mode = DECODE_STORED_LEN1;
\r
2555 case DeflaterConstants.STATIC_TREES:
\r
2556 litlenTree = InflaterHuffmanTree.defLitLenTree;
\r
2557 distTree = InflaterHuffmanTree.defDistTree;
\r
2558 mode = DECODE_HUFFMAN;
\r
2560 case DeflaterConstants.DYN_TREES:
\r
2561 dynHeader = new InflaterDynHeader();
\r
2562 mode = DECODE_DYN_HEADER;
\r
2565 throw new FormatException("Unknown block type "+type);
\r
2569 case DECODE_STORED_LEN1: {
\r
2570 if ((uncomprLen = input.PeekBits(16)) < 0) {
\r
2573 input.DropBits(16);
\r
2574 mode = DECODE_STORED_LEN2;
\r
2576 goto case DECODE_STORED_LEN2; /* fall through */
\r
2577 case DECODE_STORED_LEN2: {
\r
2578 int nlen = input.PeekBits(16);
\r
2582 input.DropBits(16);
\r
2583 if (nlen != (uncomprLen ^ 0xffff)) {
\r
2584 throw new FormatException("broken uncompressed block");
\r
2586 mode = DECODE_STORED;
\r
2588 goto case DECODE_STORED;/* fall through */
\r
2589 case DECODE_STORED: {
\r
2590 int more = outputWindow.CopyStored(input, uncomprLen);
\r
2591 uncomprLen -= more;
\r
2592 if (uncomprLen == 0) {
\r
2593 mode = DECODE_BLOCKS;
\r
2596 return !input.IsNeedingInput;
\r
2599 case DECODE_DYN_HEADER:
\r
2600 if (!dynHeader.Decode(input)) {
\r
2604 litlenTree = dynHeader.BuildLitLenTree();
\r
2605 distTree = dynHeader.BuildDistTree();
\r
2606 mode = DECODE_HUFFMAN;
\r
2607 goto case DECODE_HUFFMAN; /* fall through */
\r
2608 case DECODE_HUFFMAN:
\r
2609 case DECODE_HUFFMAN_LENBITS:
\r
2610 case DECODE_HUFFMAN_DIST:
\r
2611 case DECODE_HUFFMAN_DISTBITS:
\r
2612 return DecodeHuffman();
\r
2616 throw new FormatException();
\r
2621 /// Sets the preset dictionary. This should only be called, if
\r
2622 /// needsDictionary() returns true and it should set the same
\r
2623 /// dictionary, that was used for deflating. The getAdler()
\r
2624 /// function returns the checksum of the dictionary needed.
\r
2626 /// <param name="buffer">
\r
2627 /// the dictionary.
\r
2629 /// <exception cref="System.InvalidOperationException">
\r
2630 /// if no dictionary is needed.
\r
2632 /// <exception cref="System.ArgumentException">
\r
2633 /// if the dictionary checksum is wrong.
\r
2635 public void SetDictionary(byte[] buffer)
\r
2637 SetDictionary(buffer, 0, buffer.Length);
\r
2641 /// Sets the preset dictionary. This should only be called, if
\r
2642 /// needsDictionary() returns true and it should set the same
\r
2643 /// dictionary, that was used for deflating. The getAdler()
\r
2644 /// function returns the checksum of the dictionary needed.
\r
2646 /// <param name="buffer">
\r
2647 /// the dictionary.
\r
2649 /// <param name="off">
\r
2650 /// the offset into buffer where the dictionary starts.
\r
2652 /// <param name="len">
\r
2653 /// the length of the dictionary.
\r
2655 /// <exception cref="System.InvalidOperationException">
\r
2656 /// if no dictionary is needed.
\r
2658 /// <exception cref="System.ArgumentException">
\r
2659 /// if the dictionary checksum is wrong.
\r
2661 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2662 /// if the off and/or len are wrong.
\r
2664 public void SetDictionary(byte[] buffer, int off, int len)
\r
2666 if (!IsNeedingDictionary) {
\r
2667 throw new InvalidOperationException();
\r
2670 adler.Update(buffer, off, len);
\r
2671 if ((int) adler.Value != readAdler) {
\r
2672 throw new ArgumentException("Wrong adler checksum");
\r
2675 outputWindow.CopyDict(buffer, off, len);
\r
2676 mode = DECODE_BLOCKS;
\r
2680 /// Sets the input. This should only be called, if needsInput()
\r
2683 /// <param name="buf">
\r
2686 /// <exception cref="System.InvalidOperationException">
\r
2687 /// if no input is needed.
\r
2689 public void SetInput(byte[] buf)
\r
2691 SetInput(buf, 0, buf.Length);
\r
2695 /// Sets the input. This should only be called, if needsInput()
\r
2698 /// <param name="buf">
\r
2701 /// <param name="off">
\r
2702 /// the offset into buffer where the input starts.
\r
2704 /// <param name="len">
\r
2705 /// the length of the input.
\r
2707 /// <exception cref="System.InvalidOperationException">
\r
2708 /// if no input is needed.
\r
2710 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2711 /// if the off and/or len are wrong.
\r
2713 public void SetInput(byte[] buf, int off, int len)
\r
2715 input.SetInput(buf, off, len);
\r
2720 /// Inflates the compressed stream to the output buffer. If this
\r
2721 /// returns 0, you should check, whether needsDictionary(),
\r
2722 /// needsInput() or finished() returns true, to determine why no
\r
2723 /// further output is produced.
\r
2725 /// <param name = "buf">
\r
2726 /// the output buffer.
\r
2729 /// the number of bytes written to the buffer, 0 if no further
\r
2730 /// output can be produced.
\r
2732 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2733 /// if buf has length 0.
\r
2735 /// <exception cref="System.FormatException">
\r
2736 /// if deflated stream is invalid.
\r
2738 public int Inflate(byte[] buf)
\r
2740 return Inflate(buf, 0, buf.Length);
\r
2744 /// Inflates the compressed stream to the output buffer. If this
\r
2745 /// returns 0, you should check, whether needsDictionary(),
\r
2746 /// needsInput() or finished() returns true, to determine why no
\r
2747 /// further output is produced.
\r
2749 /// <param name = "buf">
\r
2750 /// the output buffer.
\r
2752 /// <param name = "off">
\r
2753 /// the offset into buffer where the output should start.
\r
2755 /// <param name = "len">
\r
2756 /// the maximum length of the output.
\r
2759 /// the number of bytes written to the buffer, 0 if no further output can be produced.
\r
2761 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2762 /// if len is <= 0.
\r
2764 /// <exception cref="System.ArgumentOutOfRangeException">
\r
2765 /// if the off and/or len are wrong.
\r
2767 /// <exception cref="System.FormatException">
\r
2768 /// if deflated stream is invalid.
\r
2770 public int Inflate(byte[] buf, int off, int len)
\r
2773 throw new ArgumentOutOfRangeException("len <= 0");
\r
2778 if (mode != DECODE_CHKSUM) {
\r
2779 /* Don't give away any output, if we are waiting for the
\r
2780 * checksum in the input stream.
\r
2782 * With this trick we have always:
\r
2783 * needsInput() and not finished()
\r
2784 * implies more output can be produced.
\r
2786 more = outputWindow.CopyOutput(buf, off, len);
\r
2787 adler.Update(buf, off, more);
\r
2796 } while (Decode() || (outputWindow.GetAvailable() > 0 &&
\r
2797 mode != DECODE_CHKSUM));
\r
2802 /// Returns true, if the input buffer is empty.
\r
2803 /// You should then call setInput().
\r
2804 /// NOTE: This method also returns true when the stream is finished.
\r
2806 public bool IsNeedingInput {
\r
2808 return input.IsNeedingInput;
\r
2813 /// Returns true, if a preset dictionary is needed to inflate the input.
\r
2815 public bool IsNeedingDictionary {
\r
2817 return mode == DECODE_DICT && neededBits == 0;
\r
2822 /// Returns true, if the inflater has finished. This means, that no
\r
2823 /// input is needed and no output can be produced.
\r
2825 public bool IsFinished {
\r
2827 return mode == FINISHED && outputWindow.GetAvailable() == 0;
\r
2832 /// Gets the adler checksum. This is either the checksum of all
\r
2833 /// uncompressed bytes returned by inflate(), or if needsDictionary()
\r
2834 /// returns true (and thus no output was yet produced) this is the
\r
2835 /// adler checksum of the expected dictionary.
\r
2838 /// the adler checksum.
\r
2840 public int Adler {
\r
2842 return IsNeedingDictionary ? readAdler : (int) adler.Value;
\r
2847 /// Gets the total number of output bytes returned by inflate().
\r
2850 /// the total number of output bytes.
\r
2852 public int TotalOut {
\r
2859 /// Gets the total number of processed compressed input bytes.
\r
2862 /// the total number of bytes of processed input bytes.
\r
2864 public int TotalIn {
\r
2866 return totalIn - RemainingInput;
\r
2871 /// Gets the number of unprocessed input. Useful, if the end of the
\r
2872 /// stream is reached and you want to further process the bytes after
\r
2873 /// the deflate stream.
\r
2876 /// the number of bytes of the input which were not processed.
\r
2878 public int RemainingInput {
\r
2880 return input.AvailableBytes;
\r
2885 // InflaterDynHeader.cs
\r
2886 // Copyright (C) 2001 Mike Krueger
\r
2888 // This file was translated from java, it was part of the GNU Classpath
\r
2889 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
2891 // This program is free software; you can redistribute it and/or
\r
2892 // modify it under the terms of the GNU General Public License
\r
2893 // as published by the Free Software Foundation; either version 2
\r
2894 // of the License, or (at your option) any later version.
\r
2896 // This program is distributed in the hope that it will be useful,
\r
2897 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
2898 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
2899 // GNU General Public License for more details.
\r
2901 // You should have received a copy of the GNU General Public License
\r
2902 // along with this program; if not, write to the Free Software
\r
2903 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
2905 // As a special exception, if you link this library with other files to
\r
2906 // produce an executable, this library does not by itself cause the
\r
2907 // resulting executable to be covered by the GNU General Public License.
\r
2908 // This exception does not however invalidate any other reasons why the
\r
2909 // executable file might be covered by the GNU General Public License.
\r
2911 namespace NZlib.Compression {
\r
2913 public class InflaterDynHeader
\r
2915 private const int LNUM = 0;
\r
2916 private const int DNUM = 1;
\r
2917 private const int BLNUM = 2;
\r
2918 private const int BLLENS = 3;
\r
2919 private const int LLENS = 4;
\r
2920 private const int DLENS = 5;
\r
2921 private const int LREPS = 6;
\r
2922 private const int DREPS = 7;
\r
2923 private const int FINISH = 8;
\r
2925 private byte[] blLens;
\r
2926 private byte[] litlenLens;
\r
2927 private byte[] distLens;
\r
2929 private InflaterHuffmanTree blTree;
\r
2932 private int lnum, dnum, blnum;
\r
2933 private int repBits;
\r
2934 private byte repeatedLen;
\r
2937 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
2939 public InflaterDynHeader()
\r
2943 public bool Decode(StreamManipulator input)
\r
2949 lnum = input.PeekBits(5);
\r
2954 input.DropBits(5);
\r
2955 litlenLens = new byte[lnum];
\r
2956 // System.err.println("LNUM: "+lnum);
\r
2958 goto case DNUM;/* fall through */
\r
2960 dnum = input.PeekBits(5);
\r
2965 input.DropBits(5);
\r
2966 distLens = new byte[dnum];
\r
2967 // System.err.println("DNUM: "+dnum);
\r
2969 goto case BLNUM;/* fall through */
\r
2971 blnum = input.PeekBits(4);
\r
2976 input.DropBits(4);
\r
2977 blLens = new byte[19];
\r
2979 // System.err.println("BLNUM: "+blnum);
\r
2981 goto case BLLENS;/* fall through */
\r
2983 while (ptr < blnum) {
\r
2984 int len = input.PeekBits(3);
\r
2988 input.DropBits(3);
\r
2989 // System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
\r
2990 blLens[BL_ORDER[ptr]] = (byte) len;
\r
2993 blTree = new InflaterHuffmanTree(blLens);
\r
2997 goto case LLENS;/* fall through */
\r
2999 while (ptr < lnum) {
\r
3000 int symbol = blTree.GetSymbol(input);
\r
3006 // System.err.println("litlenLens["+ptr+"]: "+symbol);
\r
3007 litlenLens[ptr++] = (byte) symbol;
\r
3009 case 16: /* repeat last len 3-6 times */
\r
3011 throw new Exception("Repeating, but no prev len");
\r
3014 // System.err.println("litlenLens["+ptr+"]: repeat");
\r
3015 repeatedLen = litlenLens[ptr-1];
\r
3017 for (int i = 3; i-- > 0; ) {
\r
3018 if (ptr >= lnum) {
\r
3019 throw new Exception();
\r
3021 litlenLens[ptr++] = repeatedLen;
\r
3025 case 17: /* repeat zero 3-10 times */
\r
3026 // System.err.println("litlenLens["+ptr+"]: zero repeat");
\r
3029 for (int i = 3; i-- > 0; ) {
\r
3030 if (ptr >= lnum) {
\r
3031 throw new Exception();
\r
3033 litlenLens[ptr++] = repeatedLen;
\r
3037 case 18: /* repeat zero 11-138 times */
\r
3038 // System.err.println("litlenLens["+ptr+"]: zero repeat");
\r
3041 for (int i = 11; i-- > 0; ) {
\r
3042 if (ptr >= lnum) {
\r
3043 throw new Exception();
\r
3045 litlenLens[ptr++] = repeatedLen;
\r
3053 goto case DLENS;/* fall through */
\r
3055 while (ptr < dnum) {
\r
3056 int symbol = blTree.GetSymbol(input);
\r
3062 distLens[ptr++] = (byte) symbol;
\r
3063 // System.err.println("distLens["+ptr+"]: "+symbol);
\r
3065 case 16: /* repeat last len 3-6 times */
\r
3067 throw new Exception("Repeating, but no prev len");
\r
3069 // System.err.println("distLens["+ptr+"]: repeat");
\r
3070 repeatedLen = distLens[ptr-1];
\r
3072 for (int i = 3; i-- > 0; ) {
\r
3073 if (ptr >= dnum) {
\r
3074 throw new Exception();
\r
3076 distLens[ptr++] = repeatedLen;
\r
3080 case 17: /* repeat zero 3-10 times */
\r
3081 // System.err.println("distLens["+ptr+"]: repeat zero");
\r
3084 for (int i = 3; i-- > 0; ) {
\r
3085 if (ptr >= dnum) {
\r
3086 throw new Exception();
\r
3088 distLens[ptr++] = repeatedLen;
\r
3092 case 18: /* repeat zero 11-138 times */
\r
3093 // System.err.println("distLens["+ptr+"]: repeat zero");
\r
3096 for (int i = 11; i-- > 0; ) {
\r
3097 if (ptr >= dnum) {
\r
3098 throw new Exception();
\r
3100 distLens[ptr++] = repeatedLen;
\r
3110 int count = input.PeekBits(repBits);
\r
3114 input.DropBits(repBits);
\r
3115 // System.err.println("litlenLens repeat: "+repBits);
\r
3116 while (count-- > 0) {
\r
3117 if (ptr >= lnum) {
\r
3118 throw new Exception();
\r
3120 litlenLens[ptr++] = repeatedLen;
\r
3127 int count = input.PeekBits(repBits);
\r
3131 input.DropBits(repBits);
\r
3132 while (count-- > 0) {
\r
3133 if (ptr >= dnum) {
\r
3134 throw new Exception();
\r
3136 distLens[ptr++] = repeatedLen;
\r
3145 public InflaterHuffmanTree BuildLitLenTree()
\r
3147 return new InflaterHuffmanTree(litlenLens);
\r
3150 public InflaterHuffmanTree BuildDistTree()
\r
3152 return new InflaterHuffmanTree(distLens);
\r
3156 // InflaterHuffmanTree.cs
\r
3157 // Copyright (C) 2001 Mike Krueger
\r
3159 // This file was translated from java, it was part of the GNU Classpath
\r
3160 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
3162 // This program is free software; you can redistribute it and/or
\r
3163 // modify it under the terms of the GNU General Public License
\r
3164 // as published by the Free Software Foundation; either version 2
\r
3165 // of the License, or (at your option) any later version.
\r
3167 // This program is distributed in the hope that it will be useful,
\r
3168 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
3169 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
3170 // GNU General Public License for more details.
\r
3172 // You should have received a copy of the GNU General Public License
\r
3173 // along with this program; if not, write to the Free Software
\r
3174 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
3176 // As a special exception, if you link this library with other files to
\r
3177 // produce an executable, this library does not by itself cause the
\r
3178 // resulting executable to be covered by the GNU General Public License.
\r
3179 // This exception does not however invalidate any other reasons why the
\r
3180 // executable file might be covered by the GNU General Public License.
\r
3182 namespace NZlib.Compression {
\r
3184 public class InflaterHuffmanTree
\r
3186 private static int MAX_BITLEN = 15;
\r
3187 private short[] tree;
\r
3189 public static InflaterHuffmanTree defLitLenTree, defDistTree;
\r
3191 static InflaterHuffmanTree()
\r
3194 byte[] codeLengths = new byte[288];
\r
3197 codeLengths[i++] = 8;
\r
3200 codeLengths[i++] = 9;
\r
3203 codeLengths[i++] = 7;
\r
3206 codeLengths[i++] = 8;
\r
3208 defLitLenTree = new InflaterHuffmanTree(codeLengths);
\r
3210 codeLengths = new byte[32];
\r
3213 codeLengths[i++] = 5;
\r
3215 defDistTree = new InflaterHuffmanTree(codeLengths);
\r
3216 } catch (Exception) {
\r
3217 throw new ApplicationException("InflaterHuffmanTree: static tree length illegal");
\r
3222 /// Constructs a Huffman tree from the array of code lengths.
\r
3224 /// <param name = "codeLengths">
\r
3225 /// the array of code lengths
\r
3227 public InflaterHuffmanTree(byte[] codeLengths)
\r
3229 BuildTree(codeLengths);
\r
3232 private void BuildTree(byte[] codeLengths)
\r
3234 int[] blCount = new int[MAX_BITLEN + 1];
\r
3235 int[] nextCode = new int[MAX_BITLEN + 1];
\r
3237 for (int i = 0; i < codeLengths.Length; i++) {
\r
3238 int bits = codeLengths[i];
\r
3244 int treeSize = 512;
\r
3245 for (int bits = 1; bits <= MAX_BITLEN; bits++) {
\r
3246 nextCode[bits] = code;
\r
3247 code += blCount[bits] << (16 - bits);
\r
3249 /* We need an extra table for bit lengths >= 10. */
\r
3250 int start = nextCode[bits] & 0x1ff80;
\r
3251 int end = code & 0x1ff80;
\r
3252 treeSize += (end - start) >> (16 - bits);
\r
3255 if (code != 65536) {
\r
3256 throw new Exception("Code lengths don't add up properly.");
\r
3258 /* Now create and fill the extra tables from longest to shortest
\r
3259 * bit len. This way the sub trees will be aligned.
\r
3261 tree = new short[treeSize];
\r
3262 int treePtr = 512;
\r
3263 for (int bits = MAX_BITLEN; bits >= 10; bits--) {
\r
3264 int end = code & 0x1ff80;
\r
3265 code -= blCount[bits] << (16 - bits);
\r
3266 int start = code & 0x1ff80;
\r
3267 for (int i = start; i < end; i += 1 << 7) {
\r
3268 tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
\r
3269 treePtr += 1 << (bits-9);
\r
3273 for (int i = 0; i < codeLengths.Length; i++) {
\r
3274 int bits = codeLengths[i];
\r
3278 code = nextCode[bits];
\r
3279 int revcode = DeflaterHuffman.BitReverse(code);
\r
3282 tree[revcode] = (short) ((i << 4) | bits);
\r
3283 revcode += 1 << bits;
\r
3284 } while (revcode < 512);
\r
3286 int subTree = tree[revcode & 511];
\r
3287 int treeLen = 1 << (subTree & 15);
\r
3288 subTree = -(subTree >> 4);
\r
3290 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
\r
3291 revcode += 1 << bits;
\r
3292 } while (revcode < treeLen);
\r
3294 nextCode[bits] = code + (1 << (16 - bits));
\r
3300 /// Reads the next symbol from input. The symbol is encoded using the
\r
3303 /// <param name="input">
\r
3304 /// input the input source.
\r
3307 /// the next symbol, or -1 if not enough input is available.
\r
3309 public int GetSymbol(StreamManipulator input)
\r
3311 int lookahead, symbol;
\r
3312 if ((lookahead = input.PeekBits(9)) >= 0) {
\r
3313 if ((symbol = tree[lookahead]) >= 0) {
\r
3314 input.DropBits(symbol & 15);
\r
3315 return symbol >> 4;
\r
3317 int subtree = -(symbol >> 4);
\r
3318 int bitlen = symbol & 15;
\r
3319 if ((lookahead = input.PeekBits(bitlen)) >= 0) {
\r
3320 symbol = tree[subtree | (lookahead >> 9)];
\r
3321 input.DropBits(symbol & 15);
\r
3322 return symbol >> 4;
\r
3324 int bits = input.AvailableBits;
\r
3325 lookahead = input.PeekBits(bits);
\r
3326 symbol = tree[subtree | (lookahead >> 9)];
\r
3327 if ((symbol & 15) <= bits) {
\r
3328 input.DropBits(symbol & 15);
\r
3329 return symbol >> 4;
\r
3335 int bits = input.AvailableBits;
\r
3336 lookahead = input.PeekBits(bits);
\r
3337 symbol = tree[lookahead];
\r
3338 if (symbol >= 0 && (symbol & 15) <= bits) {
\r
3339 input.DropBits(symbol & 15);
\r
3340 return symbol >> 4;
\r
3349 // PendingBuffer.cs
\r
3350 // Copyright (C) 2001 Mike Krueger
\r
3352 // This file was translated from java, it was part of the GNU Classpath
\r
3353 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
3355 // This program is free software; you can redistribute it and/or
\r
3356 // modify it under the terms of the GNU General Public License
\r
3357 // as published by the Free Software Foundation; either version 2
\r
3358 // of the License, or (at your option) any later version.
\r
3360 // This program is distributed in the hope that it will be useful,
\r
3361 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
3362 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
3363 // GNU General Public License for more details.
\r
3365 // You should have received a copy of the GNU General Public License
\r
3366 // along with this program; if not, write to the Free Software
\r
3367 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
3369 // As a special exception, if you link this library with other files to
\r
3370 // produce an executable, this library does not by itself cause the
\r
3371 // resulting executable to be covered by the GNU General Public License.
\r
3372 // This exception does not however invalidate any other reasons why the
\r
3373 // executable file might be covered by the GNU General Public License.
\r
3375 namespace NZlib.Compression {
\r
3378 /// This class is general purpose class for writing data to a buffer.
\r
3380 /// It allows you to write bits as well as bytes
\r
3381 /// Based on DeflaterPending.java
\r
3383 /// author of the original java version : Jochen Hoenicke
\r
3385 public class PendingBuffer
\r
3387 protected byte[] buf;
\r
3394 public PendingBuffer() : this( 4096 )
\r
3399 public PendingBuffer(int bufsize)
\r
3401 buf = new byte[bufsize];
\r
3404 public void Reset()
\r
3406 start = end = bitCount = 0;
\r
3409 public void WriteByte(int b)
\r
3411 if (DeflaterConstants.DEBUGGING && start != 0)
\r
3412 throw new Exception();
\r
3413 buf[end++] = (byte) b;
\r
3416 public void WriteShort(int s)
\r
3418 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3419 throw new Exception();
\r
3421 buf[end++] = (byte) s;
\r
3422 buf[end++] = (byte) (s >> 8);
\r
3425 public void WriteInt(int s)
\r
3427 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3428 throw new Exception();
\r
3430 buf[end++] = (byte) s;
\r
3431 buf[end++] = (byte) (s >> 8);
\r
3432 buf[end++] = (byte) (s >> 16);
\r
3433 buf[end++] = (byte) (s >> 24);
\r
3436 public void WriteBlock(byte[] block, int offset, int len)
\r
3438 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3439 throw new Exception();
\r
3441 System.Array.Copy(block, offset, buf, end, len);
\r
3445 public int BitCount {
\r
3451 public void AlignToByte()
\r
3453 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3454 throw new Exception();
\r
3456 if (bitCount > 0) {
\r
3457 buf[end++] = (byte) bits;
\r
3458 if (bitCount > 8) {
\r
3459 buf[end++] = (byte) (bits >> 8);
\r
3466 public void WriteBits(int b, int count)
\r
3468 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3469 throw new Exception();
\r
3471 // if (DeflaterConstants.DEBUGGING) {
\r
3472 // Console.WriteLine("writeBits("+b+","+count+")");
\r
3474 bits |= (uint)(b << bitCount);
\r
3475 bitCount += count;
\r
3476 if (bitCount >= 16) {
\r
3477 buf[end++] = (byte) bits;
\r
3478 buf[end++] = (byte) (bits >> 8);
\r
3484 public void WriteShortMSB(int s)
\r
3486 if (DeflaterConstants.DEBUGGING && start != 0) {
\r
3487 throw new Exception();
\r
3489 buf[end++] = (byte) (s >> 8);
\r
3490 buf[end++] = (byte) s;
\r
3493 public bool IsFlushed {
\r
3500 /// Flushes the pending buffer into the given output array. If the
\r
3501 /// output array is to small, only a partial flush is done.
\r
3503 /// <param name="output">
\r
3504 /// the output array;
\r
3506 /// <param name="offset">
\r
3507 /// the offset into output array;
\r
3509 /// <param name="length">
\r
3510 /// length the maximum number of bytes to store;
\r
3512 /// <exception name="ArgumentOutOfRangeException">
\r
3513 /// IndexOutOfBoundsException if offset or length are invalid.
\r
3515 public int Flush(byte[] output, int offset, int length)
\r
3517 if (bitCount >= 8) {
\r
3518 buf[end++] = (byte) bits;
\r
3522 if (length > end - start) {
\r
3523 length = end - start;
\r
3524 System.Array.Copy(buf, start, output, offset, length);
\r
3528 System.Array.Copy(buf, start, output, offset, length);
\r
3534 public byte[] ToByteArray()
\r
3536 byte[] ret = new byte[ end - start ];
\r
3537 System.Array.Copy(buf, start, ret, 0, ret.Length);
\r
3544 // Adler32.cs - Computes Adler32 data checksum of a data stream
\r
3545 // Copyright (C) 2001 Mike Krueger
\r
3547 // This file was translated from java, it was part of the GNU Classpath
\r
3548 // Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
\r
3550 // This program is free software; you can redistribute it and/or
\r
3551 // modify it under the terms of the GNU General Public License
\r
3552 // as published by the Free Software Foundation; either version 2
\r
3553 // of the License, or (at your option) any later version.
\r
3555 // This program is distributed in the hope that it will be useful,
\r
3556 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
3557 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
3558 // GNU General Public License for more details.
\r
3560 // You should have received a copy of the GNU General Public License
\r
3561 // along with this program; if not, write to the Free Software
\r
3562 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
3564 // As a special exception, if you link this library with other files to
\r
3565 // produce an executable, this library does not by itself cause the
\r
3566 // resulting executable to be covered by the GNU General Public License.
\r
3567 // This exception does not however invalidate any other reasons why the
\r
3568 // executable file might be covered by the GNU General Public License.
\r
3570 namespace NZlib.Checksums {
\r
3573 /// Computes Adler32 checksum for a stream of data. An Adler32
\r
3574 /// checksum is not as reliable as a CRC32 checksum, but a lot faster to
\r
3577 /// The specification for Adler32 may be found in RFC 1950.
\r
3578 /// ZLIB Compressed Data Format Specification version 3.3)
\r
3581 /// From that document:
\r
3583 /// "ADLER32 (Adler-32 checksum)
\r
3584 /// This contains a checksum value of the uncompressed data
\r
3585 /// (excluding any dictionary data) computed according to Adler-32
\r
3586 /// algorithm. This algorithm is a 32-bit extension and improvement
\r
3587 /// of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
\r
3590 /// Adler-32 is composed of two sums accumulated per byte: s1 is
\r
3591 /// the sum of all bytes, s2 is the sum of all s1 values. Both sums
\r
3592 /// are done modulo 65521. s1 is initialized to 1, s2 to zero. The
\r
3593 /// Adler-32 checksum is stored as s2*65536 + s1 in most-
\r
3594 /// significant-byte first (network) order."
\r
3596 /// "8.2. The Adler-32 algorithm
\r
3598 /// The Adler-32 algorithm is much faster than the CRC32 algorithm yet
\r
3599 /// still provides an extremely low probability of undetected errors.
\r
3601 /// The modulo on unsigned long accumulators can be delayed for 5552
\r
3602 /// bytes, so the modulo operation time is negligible. If the bytes
\r
3603 /// are a, b, c, the second sum is 3a + 2b + c + 3, and so is position
\r
3604 /// and order sensitive, unlike the first sum, which is just a
\r
3605 /// checksum. That 65521 is prime is important to avoid a possible
\r
3606 /// large class of two-byte errors that leave the check unchanged.
\r
3607 /// (The Fletcher checksum uses 255, which is not prime and which also
\r
3608 /// makes the Fletcher check insensitive to single byte changes 0 -
\r
3611 /// The sum s1 is initialized to 1 instead of zero to make the length
\r
3612 /// of the sequence part of s2, so that the length does not have to be
\r
3613 /// checked separately. (Any sequence of zeroes has a Fletcher
\r
3614 /// checksum of zero.)"
\r
3616 /// <see cref="NZlib.Streams.InflaterInputStream"/>
\r
3617 /// <see cref="NZlib.Streams.DeflaterOutputStream"/>
\r
3618 public sealed class Adler32 : IChecksum
\r
3621 /// largest prime smaller than 65536
\r
3623 readonly static uint BASE = 65521;
\r
3628 /// Returns the Adler32 data checksum computed so far.
\r
3630 public long Value {
\r
3632 return (long) checksum & 0xFFFFFFFFL;
\r
3637 /// Creates a new instance of the <code>Adler32</code> class.
\r
3638 /// The checksum starts off with a value of 1.
\r
3646 /// Resets the Adler32 checksum to the initial value.
\r
3648 public void Reset()
\r
3650 checksum = 1; //Initialize to 1
\r
3654 /// Updates the checksum with the byte b.
\r
3656 /// <param name="bval">
\r
3657 /// the data value to add. The high byte of the int is ignored.
\r
3659 public void Update(int bval)
\r
3661 //We could make a length 1 byte array and call update again, but I
\r
3662 //would rather not have that overhead
\r
3663 uint s1 = checksum & 0xFFFF;
\r
3664 uint s2 = checksum >> 16;
\r
3666 s1 = (s1 + ((uint)bval & 0xFF)) % BASE;
\r
3667 s2 = (s1 + s2) % BASE;
\r
3669 checksum = (s2 << 16) + s1;
\r
3673 /// Updates the checksum with the bytes taken from the array.
\r
3675 /// <param name="buffer">
\r
3676 /// buffer an array of bytes
\r
3678 public void Update(byte[] buffer)
\r
3680 Update(buffer, 0, buffer.Length);
\r
3684 /// Updates the checksum with the bytes taken from the array.
\r
3686 /// <param name="buf">
\r
3687 /// an array of bytes
\r
3689 /// <param name="off">
\r
3690 /// the start of the data used for this update
\r
3692 /// <param name="len">
\r
3693 /// the number of bytes to use for this update
\r
3695 public void Update(byte[] buf, int off, int len)
\r
3697 if (buf == null) {
\r
3698 throw new ArgumentNullException("buf");
\r
3701 if (off < 0 || len < 0 || off + len > buf.Length) {
\r
3702 throw new ArgumentOutOfRangeException();
\r
3705 //(By Per Bothner)
\r
3706 uint s1 = checksum & 0xFFFF;
\r
3707 uint s2 = checksum >> 16;
\r
3710 // We can defer the modulo operation:
\r
3711 // s1 maximally grows from 65521 to 65521 + 255 * 3800
\r
3712 // s2 maximally grows by 3800 * median(s1) = 2090079800 < 2^31
\r
3718 while (--n >= 0) {
\r
3719 s1 = s1 + (uint)(buf[off++] & 0xFF);
\r
3726 checksum = (s2 << 16) | s1;
\r
3730 // CRC32.cs - Computes CRC32 data checksum of a data stream
\r
3731 // Copyright (C) 2001 Mike Krueger
\r
3733 // This file was translated from java, it was part of the GNU Classpath
\r
3734 // Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
\r
3736 // This program is free software; you can redistribute it and/or
\r
3737 // modify it under the terms of the GNU General Public License
\r
3738 // as published by the Free Software Foundation; either version 2
\r
3739 // of the License, or (at your option) any later version.
\r
3741 // This program is distributed in the hope that it will be useful,
\r
3742 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
3743 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
3744 // GNU General Public License for more details.
\r
3746 // You should have received a copy of the GNU General Public License
\r
3747 // along with this program; if not, write to the Free Software
\r
3748 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
3750 // As a special exception, if you link this library with other files to
\r
3751 // produce an executable, this library does not by itself cause the
\r
3752 // resulting executable to be covered by the GNU General Public License.
\r
3753 // This exception does not however invalidate any other reasons why the
\r
3754 // executable file might be covered by the GNU General Public License.
\r
3756 namespace NZlib.Checksums {
\r
3759 /// Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
\r
3760 /// 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
3762 /// Polynomials over GF(2) are represented in binary, one bit per coefficient,
\r
3763 /// with the lowest powers in the most significant bit. Then adding polynomials
\r
3764 /// is just exclusive-or, and multiplying a polynomial by x is a right shift by
\r
3765 /// one. If we call the above polynomial p, and represent a byte as the
\r
3766 /// polynomial q, also with the lowest power in the most significant bit (so the
\r
3767 /// byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
\r
3768 /// where a mod b means the remainder after dividing a by b.
\r
3770 /// This calculation is done using the shift-register method of multiplying and
\r
3771 /// taking the remainder. The register is initialized to zero, and for each
\r
3772 /// incoming bit, x^32 is added mod p to the register if the bit is a one (where
\r
3773 /// x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
\r
3774 /// x (which is shifting right by one and adding x^32 mod p if the bit shifted
\r
3775 /// out is a one). We start with the highest power (least significant bit) of
\r
3776 /// q and repeat for all eight bits of q.
\r
3778 /// The table is simply the CRC of all possible eight bit values. This is all
\r
3779 /// the information needed to generate CRC's on data a byte at a time for all
\r
3780 /// combinations of CRC register values and incoming bytes.
\r
3782 public sealed class Crc32 : IChecksum
\r
3784 readonly static uint CrcSeed = 0xFFFFFFFF;
\r
3786 readonly static uint[] CrcTable = new uint[] {
\r
3787 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,
\r
3788 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,
\r
3789 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,
\r
3790 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
\r
3791 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,
\r
3792 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
\r
3793 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
\r
3794 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
\r
3795 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,
\r
3796 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,
\r
3797 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,
\r
3798 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
\r
3799 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,
\r
3800 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
\r
3801 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,
\r
3802 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
\r
3803 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
\r
3804 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
\r
3805 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,
\r
3806 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
\r
3807 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
\r
3808 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,
\r
3809 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,
\r
3810 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
\r
3811 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,
\r
3812 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,
\r
3813 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
\r
3814 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
\r
3815 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344,
\r
3816 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
\r
3817 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,
\r
3818 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
\r
3819 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,
\r
3820 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
\r
3821 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
\r
3822 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
\r
3823 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,
\r
3824 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,
\r
3825 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,
\r
3826 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
\r
3827 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,
\r
3828 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
\r
3829 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,
\r
3830 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
\r
3831 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,
\r
3832 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,
\r
3833 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,
\r
3834 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
\r
3835 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
\r
3836 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,
\r
3837 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,
\r
3842 /// The crc data checksum so far.
\r
3847 /// Returns the CRC32 data checksum computed so far.
\r
3849 public long Value {
\r
3856 /// Resets the CRC32 data checksum as if no update was ever called.
\r
3858 public void Reset()
\r
3864 /// Updates the checksum with the int bval.
\r
3866 /// <param name = "bval">
\r
3867 /// the byte is taken as the lower 8 bits of bval
\r
3869 public void Update(int bval)
\r
3872 crc = CrcTable[(crc ^ bval) & 0xFF] ^ (crc >> 8);
\r
3877 /// Updates the checksum with the bytes taken from the array.
\r
3879 /// <param name="buffer">
\r
3880 /// buffer an array of bytes
\r
3882 public void Update(byte[] buffer)
\r
3884 Update(buffer, 0, buffer.Length);
\r
3888 /// Adds the byte array to the data checksum.
\r
3890 /// <param name = "buf">
\r
3891 /// the buffer which contains the data
\r
3893 /// <param name = "off">
\r
3894 /// the offset in the buffer where the data starts
\r
3896 /// <param name = "len">
\r
3897 /// the length of the data
\r
3899 public void Update(byte[] buf, int off, int len)
\r
3901 if (buf == null) {
\r
3902 throw new ArgumentNullException("buf");
\r
3905 if (off < 0 || len < 0 || off + len > buf.Length) {
\r
3906 throw new ArgumentOutOfRangeException();
\r
3911 while (--len >= 0) {
\r
3912 crc = CrcTable[(crc ^ buf[off++]) & 0xFF] ^ (crc >> 8);
\r
3919 // IChecksum.cs - Interface to compute a data checksum
\r
3920 // Copyright (C) 2001 Mike Krueger
\r
3922 // This file was translated from java, it was part of the GNU Classpath
\r
3923 // Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
\r
3925 // This program is free software; you can redistribute it and/or
\r
3926 // modify it under the terms of the GNU General Public License
\r
3927 // as published by the Free Software Foundation; either version 2
\r
3928 // of the License, or (at your option) any later version.
\r
3930 // This program is distributed in the hope that it will be useful,
\r
3931 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
3932 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
3933 // GNU General Public License for more details.
\r
3935 // You should have received a copy of the GNU General Public License
\r
3936 // along with this program; if not, write to the Free Software
\r
3937 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
3939 // As a special exception, if you link this library with other files to
\r
3940 // produce an executable, this library does not by itself cause the
\r
3941 // resulting executable to be covered by the GNU General Public License.
\r
3942 // This exception does not however invalidate any other reasons why the
\r
3943 // executable file might be covered by the GNU General Public License.
\r
3945 namespace NZlib.Checksums {
\r
3948 /// Interface to compute a data checksum used by checked input/output streams.
\r
3949 /// A data checksum can be updated by one byte or with a byte array. After each
\r
3950 /// update the value of the current checksum can be returned by calling
\r
3951 /// <code>getValue</code>. The complete checksum object can also be reset
\r
3952 /// so it can be used again with new data.
\r
3954 public interface IChecksum
\r
3957 /// Returns the data checksum computed so far.
\r
3964 /// Resets the data checksum as if no update was ever called.
\r
3969 /// Adds one byte to the data checksum.
\r
3971 /// <param name = "bval">
\r
3972 /// the data value to add. The high byte of the int is ignored.
\r
3974 void Update(int bval);
\r
3977 /// Updates the data checksum with the bytes taken from the array.
\r
3979 /// <param name="buffer">
\r
3980 /// buffer an array of bytes
\r
3982 void Update(byte[] buffer);
\r
3985 /// Adds the byte array to the data checksum.
\r
3987 /// <param name = "buf">
\r
3988 /// the buffer which contains the data
\r
3990 /// <param name = "off">
\r
3991 /// the offset in the buffer where the data starts
\r
3993 /// <param name = "len">
\r
3994 /// the length of the data
\r
3996 void Update(byte[] buf, int off, int len);
\r
3999 // OutputWindow.cs
\r
4000 // Copyright (C) 2001 Mike Krueger
\r
4002 // This file was translated from java, it was part of the GNU Classpath
\r
4003 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
4005 // This program is free software; you can redistribute it and/or
\r
4006 // modify it under the terms of the GNU General Public License
\r
4007 // as published by the Free Software Foundation; either version 2
\r
4008 // of the License, or (at your option) any later version.
\r
4010 // This program is distributed in the hope that it will be useful,
\r
4011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
4012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
4013 // GNU General Public License for more details.
\r
4015 // You should have received a copy of the GNU General Public License
\r
4016 // along with this program; if not, write to the Free Software
\r
4017 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
4019 // As a special exception, if you link this library with other files to
\r
4020 // produce an executable, this library does not by itself cause the
\r
4021 // resulting executable to be covered by the GNU General Public License.
\r
4022 // This exception does not however invalidate any other reasons why the
\r
4023 // executable file might be covered by the GNU General Public License.
\r
4025 namespace NZlib.Streams {
\r
4028 /// Contains the output from the Inflation process.
\r
4029 /// We need to have a window so that we can refer backwards into the output stream
\r
4030 /// to repeat stuff.
\r
4032 /// author of the original java version : John Leuner
\r
4034 public class OutputWindow
\r
4036 private static int WINDOW_SIZE = 1 << 15;
\r
4037 private static int WINDOW_MASK = WINDOW_SIZE - 1;
\r
4039 private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
\r
4040 private int window_end = 0;
\r
4041 private int window_filled = 0;
\r
4043 public void Write(int abyte)
\r
4045 if (window_filled++ == WINDOW_SIZE) {
\r
4046 throw new InvalidOperationException("Window full");
\r
4048 window[window_end++] = (byte) abyte;
\r
4049 window_end &= WINDOW_MASK;
\r
4053 private void SlowRepeat(int rep_start, int len, int dist)
\r
4055 while (len-- > 0) {
\r
4056 window[window_end++] = window[rep_start++];
\r
4057 window_end &= WINDOW_MASK;
\r
4058 rep_start &= WINDOW_MASK;
\r
4062 public void Repeat(int len, int dist)
\r
4064 if ((window_filled += len) > WINDOW_SIZE) {
\r
4065 throw new InvalidOperationException("Window full");
\r
4068 int rep_start = (window_end - dist) & WINDOW_MASK;
\r
4069 int border = WINDOW_SIZE - len;
\r
4070 if (rep_start <= border && window_end < border) {
\r
4071 if (len <= dist) {
\r
4072 System.Array.Copy(window, rep_start, window, window_end, len);
\r
4073 window_end += len;
\r
4075 /* We have to copy manually, since the repeat pattern overlaps.
\r
4077 while (len-- > 0) {
\r
4078 window[window_end++] = window[rep_start++];
\r
4082 SlowRepeat(rep_start, len, dist);
\r
4086 public int CopyStored(StreamManipulator input, int len)
\r
4088 len = Math.Min(Math.Min(len, WINDOW_SIZE - window_filled), input.AvailableBytes);
\r
4091 int tailLen = WINDOW_SIZE - window_end;
\r
4092 if (len > tailLen) {
\r
4093 copied = input.CopyBytes(window, window_end, tailLen);
\r
4094 if (copied == tailLen) {
\r
4095 copied += input.CopyBytes(window, 0, len - tailLen);
\r
4098 copied = input.CopyBytes(window, window_end, len);
\r
4101 window_end = (window_end + copied) & WINDOW_MASK;
\r
4102 window_filled += copied;
\r
4106 public void CopyDict(byte[] dict, int offset, int len)
\r
4108 if (window_filled > 0) {
\r
4109 throw new InvalidOperationException();
\r
4112 if (len > WINDOW_SIZE) {
\r
4113 offset += len - WINDOW_SIZE;
\r
4114 len = WINDOW_SIZE;
\r
4116 System.Array.Copy(dict, offset, window, 0, len);
\r
4117 window_end = len & WINDOW_MASK;
\r
4120 public int GetFreeSpace()
\r
4122 return WINDOW_SIZE - window_filled;
\r
4125 public int GetAvailable()
\r
4127 return window_filled;
\r
4130 public int CopyOutput(byte[] output, int offset, int len)
\r
4132 int copy_end = window_end;
\r
4133 if (len > window_filled) {
\r
4134 len = window_filled;
\r
4136 copy_end = (window_end - window_filled + len) & WINDOW_MASK;
\r
4140 int tailLen = len - copy_end;
\r
4142 if (tailLen > 0) {
\r
4143 System.Array.Copy(window, WINDOW_SIZE - tailLen,
\r
4144 output, offset, tailLen);
\r
4145 offset += tailLen;
\r
4148 System.Array.Copy(window, copy_end - len, output, offset, len);
\r
4149 window_filled -= copied;
\r
4150 if (window_filled < 0) {
\r
4151 throw new InvalidOperationException();
\r
4156 public void Reset()
\r
4158 window_filled = window_end = 0;
\r
4162 // StreamManipulator.cs
\r
4163 // Copyright (C) 2001 Mike Krueger
\r
4165 // This file was translated from java, it was part of the GNU Classpath
\r
4166 // Copyright (C) 2001 Free Software Foundation, Inc.
\r
4168 // This program is free software; you can redistribute it and/or
\r
4169 // modify it under the terms of the GNU General Public License
\r
4170 // as published by the Free Software Foundation; either version 2
\r
4171 // of the License, or (at your option) any later version.
\r
4173 // This program is distributed in the hope that it will be useful,
\r
4174 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
4175 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
4176 // GNU General Public License for more details.
\r
4178 // You should have received a copy of the GNU General Public License
\r
4179 // along with this program; if not, write to the Free Software
\r
4180 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
\r
4182 // As a special exception, if you link this library with other files to
\r
4183 // produce an executable, this library does not by itself cause the
\r
4184 // resulting executable to be covered by the GNU General Public License.
\r
4185 // This exception does not however invalidate any other reasons why the
\r
4186 // executable file might be covered by the GNU General Public License.
\r
4188 namespace NZlib.Streams {
\r
4191 /// This class allows us to retrieve a specified amount of bits from
\r
4192 /// the input buffer, as well as copy big byte blocks.
\r
4194 /// It uses an int buffer to store up to 31 bits for direct
\r
4195 /// manipulation. This guarantees that we can get at least 16 bits,
\r
4196 /// but we only need at most 15, so this is all safe.
\r
4198 /// There are some optimizations in this class, for example, you must
\r
4199 /// never peek more then 8 bits more than needed, and you must first
\r
4200 /// peek bits before you may drop them. This is not a general purpose
\r
4201 /// class but optimized for the behaviour of the Inflater.
\r
4203 /// authors of the original java version : John Leuner, Jochen Hoenicke
\r
4205 public class StreamManipulator
\r
4207 private byte[] window;
\r
4208 private int window_start = 0;
\r
4209 private int window_end = 0;
\r
4211 private uint buffer = 0;
\r
4212 private int bits_in_buffer = 0;
\r
4215 /// Get the next n bits but don't increase input pointer. n must be
\r
4216 /// less or equal 16 and if you if this call succeeds, you must drop
\r
4217 /// at least n-8 bits in the next call.
\r
4220 /// the value of the bits, or -1 if not enough bits available. */
\r
4222 public int PeekBits(int n)
\r
4224 if (bits_in_buffer < n) {
\r
4225 if (window_start == window_end) {
\r
4228 buffer |= (uint)((window[window_start++] & 0xff |
\r
4229 (window[window_start++] & 0xff) << 8) << bits_in_buffer);
\r
4230 bits_in_buffer += 16;
\r
4232 return (int)(buffer & ((1 << n) - 1));
\r
4236 /// Drops the next n bits from the input. You should have called peekBits
\r
4237 /// with a bigger or equal n before, to make sure that enough bits are in
\r
4238 /// the bit buffer.
\r
4240 public void DropBits(int n)
\r
4243 bits_in_buffer -= n;
\r
4247 /// Gets the next n bits and increases input pointer. This is equivalent
\r
4248 /// to peekBits followed by dropBits, except for correct error handling.
\r
4251 /// the value of the bits, or -1 if not enough bits available.
\r
4253 public int GetBits(int n)
\r
4255 int bits = PeekBits(n);
\r
4263 /// Gets the number of bits available in the bit buffer. This must be
\r
4264 /// only called when a previous peekBits() returned -1.
\r
4267 /// the number of bits available.
\r
4269 public int AvailableBits {
\r
4271 return bits_in_buffer;
\r
4276 /// Gets the number of bytes available.
\r
4279 /// the number of bytes available.
\r
4281 public int AvailableBytes {
\r
4283 return window_end - window_start + (bits_in_buffer >> 3);
\r
4288 /// Skips to the next byte boundary.
\r
4290 public void SkipToByteBoundary()
\r
4292 buffer >>= (bits_in_buffer & 7);
\r
4293 bits_in_buffer &= ~7;
\r
4296 public bool IsNeedingInput {
\r
4298 return window_start == window_end;
\r
4303 /// Copies length bytes from input buffer to output buffer starting
\r
4304 /// at output[offset]. You have to make sure, that the buffer is
\r
4305 /// byte aligned. If not enough bytes are available, copies fewer
\r
4308 /// <param name="output">
\r
4311 /// <param name="offset">
\r
4312 /// the offset in the buffer.
\r
4314 /// <param name="length">
\r
4315 /// the length to copy, 0 is allowed.
\r
4318 /// the number of bytes copied, 0 if no byte is available.
\r
4320 public int CopyBytes(byte[] output, int offset, int length)
\r
4323 throw new ArgumentOutOfRangeException("length negative");
\r
4325 if ((bits_in_buffer & 7) != 0) {
\r
4326 /* bits_in_buffer may only be 0 or 8 */
\r
4327 throw new InvalidOperationException("Bit buffer is not aligned!");
\r
4331 while (bits_in_buffer > 0 && length > 0) {
\r
4332 output[offset++] = (byte) buffer;
\r
4334 bits_in_buffer -= 8;
\r
4338 if (length == 0) {
\r
4342 int avail = window_end - window_start;
\r
4343 if (length > avail) {
\r
4346 System.Array.Copy(window, window_start, output, offset, length);
\r
4347 window_start += length;
\r
4349 if (((window_start - window_end) & 1) != 0) {
\r
4350 /* We always want an even number of bytes in input, see peekBits */
\r
4351 buffer = (uint)(window[window_start++] & 0xff);
\r
4352 bits_in_buffer = 8;
\r
4354 return count + length;
\r
4357 public StreamManipulator()
\r
4361 public void Reset()
\r
4363 buffer = (uint)(window_start = window_end = bits_in_buffer = 0);
\r
4366 public void SetInput(byte[] buf, int off, int len)
\r
4368 if (window_start < window_end) {
\r
4369 throw new InvalidOperationException("Old input was not completely processed");
\r
4372 int end = off + len;
\r
4374 /* We want to throw an ArrayIndexOutOfBoundsException early. The
\r
4375 * check is very tricky: it also handles integer wrap around.
\r
4377 if (0 > off || off > end || end > buf.Length) {
\r
4378 throw new ArgumentOutOfRangeException();
\r
4381 if ((len & 1) != 0) {
\r
4382 /* We always want an even number of bytes in input, see peekBits */
\r
4383 buffer |= (uint)((buf[off++] & 0xff) << bits_in_buffer);
\r
4384 bits_in_buffer += 8;
\r
4388 window_start = off;
\r
projects / mono.git / blob