Mercurial > repos > SharpZipLib

comparison Zip/Compression/DeflaterHuffman.cs @ 1:94e25b786321

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Re #311: can't read ZIP file packed by Linux app Archive Manager/File Roller Initial commit of clean SharpZipLib 0860 source. Only change is build paths.
author IBBoard <dev@ibboard.co.uk>
date Sat, 30 Oct 2010 14:03:17 +0000
parents
children
comparison
equal deleted inserted replaced
0:d16ef17fa7bb 1:94e25b786321
1 // DeflaterHuffman.cs
2 //
3 // Copyright (C) 2001 Mike Krueger
4 // Copyright (C) 2004 John Reilly
5 //
6 // This file was translated from java, it was part of the GNU Classpath
7 // Copyright (C) 2001 Free Software Foundation, Inc.
8 //
9 // This program is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU General Public License
11 // as published by the Free Software Foundation; either version 2
12 // of the License, or (at your option) any later version.
13 //
14 // This program is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 // GNU General Public License for more details.
18 //
19 // You should have received a copy of the GNU General Public License
20 // along with this program; if not, write to the Free Software
21 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 //
23 // Linking this library statically or dynamically with other modules is
24 // making a combined work based on this library. Thus, the terms and
25 // conditions of the GNU General Public License cover the whole
26 // combination.
27 //
28 // As a special exception, the copyright holders of this library give you
29 // permission to link this library with independent modules to produce an
30 // executable, regardless of the license terms of these independent
31 // modules, and to copy and distribute the resulting executable under
32 // terms of your choice, provided that you also meet, for each linked
33 // independent module, the terms and conditions of the license of that
34 // module. An independent module is a module which is not derived from
35 // or based on this library. If you modify this library, you may extend
36 // this exception to your version of the library, but you are not
37 // obligated to do so. If you do not wish to do so, delete this
38 // exception statement from your version.
39
40 using System;
41
42 namespace ICSharpCode.SharpZipLib.Zip.Compression
43 {
44
45 /// <summary>
46 /// This is the DeflaterHuffman class.
47 ///
48 /// This class is <i>not</i> thread safe. This is inherent in the API, due
49 /// to the split of Deflate and SetInput.
50 ///
51 /// author of the original java version : Jochen Hoenicke
52 /// </summary>
53 public class DeflaterHuffman
54 {
55 const int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
56 const int LITERAL_NUM = 286;
57
58 // Number of distance codes
59 const int DIST_NUM = 30;
60 // Number of codes used to transfer bit lengths
61 const int BITLEN_NUM = 19;
62
63 // repeat previous bit length 3-6 times (2 bits of repeat count)
64 const int REP_3_6 = 16;
65 // repeat a zero length 3-10 times (3 bits of repeat count)
66 const int REP_3_10 = 17;
67 // repeat a zero length 11-138 times (7 bits of repeat count)
68 const int REP_11_138 = 18;
69
70 const int EOF_SYMBOL = 256;
71
72 // The lengths of the bit length codes are sent in order of decreasing
73 // probability, to avoid transmitting the lengths for unused bit length codes.
74 static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
75
76 static readonly byte[] bit4Reverse = {
77 0,
78 8,
79 4,
80 12,
81 2,
82 10,
83 6,
84 14,
85 1,
86 9,
87 5,
88 13,
89 3,
90 11,
91 7,
92 15
93 };
94
95 static short[] staticLCodes;
96 static byte[] staticLLength;
97 static short[] staticDCodes;
98 static byte[] staticDLength;
99
100 class Tree
101 {
102 #region Instance Fields
103 public short[] freqs;
104
105 public byte[] length;
106
107 public int minNumCodes;
108
109 public int numCodes;
110
111 short[] codes;
112 int[] bl_counts;
113 int maxLength;
114 DeflaterHuffman dh;
115 #endregion
116
117 #region Constructors
118 public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
119 {
120 this.dh = dh;
121 this.minNumCodes = minCodes;
122 this.maxLength = maxLength;
123 freqs = new short[elems];
124 bl_counts = new int[maxLength];
125 }
126
127 #endregion
128
129 /// <summary>
130 /// Resets the internal state of the tree
131 /// </summary>
132 public void Reset()
133 {
134 for (int i = 0; i < freqs.Length; i++) {
135 freqs[i] = 0;
136 }
137 codes = null;
138 length = null;
139 }
140
141 public void WriteSymbol(int code)
142 {
143 // if (DeflaterConstants.DEBUGGING) {
144 // freqs[code]--;
145 // // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
146 // }
147 dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
148 }
149
150 /// <summary>
151 /// Check that all frequencies are zero
152 /// </summary>
153 /// <exception cref="SharpZipBaseException">
154 /// At least one frequency is non-zero
155 /// </exception>
156 public void CheckEmpty()
157 {
158 bool empty = true;
159 for (int i = 0; i < freqs.Length; i++) {
160 if (freqs[i] != 0) {
161 //Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
162 empty = false;
163 }
164 }
165
166 if (!empty) {
167 throw new SharpZipBaseException("!Empty");
168 }
169 }
170
171 /// <summary>
172 /// Set static codes and length
173 /// </summary>
174 /// <param name="staticCodes">new codes</param>
175 /// <param name="staticLengths">length for new codes</param>
176 public void SetStaticCodes(short[] staticCodes, byte[] staticLengths)
177 {
178 codes = staticCodes;
179 length = staticLengths;
180 }
181
182 /// <summary>
183 /// Build dynamic codes and lengths
184 /// </summary>
185 public void BuildCodes()
186 {
187 int numSymbols = freqs.Length;
188 int[] nextCode = new int[maxLength];
189 int code = 0;
190
191 codes = new short[freqs.Length];
192
193 // if (DeflaterConstants.DEBUGGING) {
194 // //Console.WriteLine("buildCodes: "+freqs.Length);
195 // }
196
197 for (int bits = 0; bits < maxLength; bits++) {
198 nextCode[bits] = code;
199 code += bl_counts[bits] << (15 - bits);
200
201 // if (DeflaterConstants.DEBUGGING) {
202 // //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
203 // +" nextCode: "+code);
204 // }
205 }
206
207 #if DebugDeflation
208 if ( DeflaterConstants.DEBUGGING && (code != 65536) )
209 {
210 throw new SharpZipBaseException("Inconsistent bl_counts!");
211 }
212 #endif
213 for (int i=0; i < numCodes; i++) {
214 int bits = length[i];
215 if (bits > 0) {
216
217 // if (DeflaterConstants.DEBUGGING) {
218 // //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
219 // +bits);
220 // }
221
222 codes[i] = BitReverse(nextCode[bits-1]);
223 nextCode[bits-1] += 1 << (16 - bits);
224 }
225 }
226 }
227
228 public void BuildTree()
229 {
230 int numSymbols = freqs.Length;
231
232 /* heap is a priority queue, sorted by frequency, least frequent
233 * nodes first. The heap is a binary tree, with the property, that
234 * the parent node is smaller than both child nodes. This assures
235 * that the smallest node is the first parent.
236 *
237 * The binary tree is encoded in an array: 0 is root node and
238 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
239 */
240 int[] heap = new int[numSymbols];
241 int heapLen = 0;
242 int maxCode = 0;
243 for (int n = 0; n < numSymbols; n++) {
244 int freq = freqs[n];
245 if (freq != 0) {
246 // Insert n into heap
247 int pos = heapLen++;
248 int ppos;
249 while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
250 heap[pos] = heap[ppos];
251 pos = ppos;
252 }
253 heap[pos] = n;
254
255 maxCode = n;
256 }
257 }
258
259 /* We could encode a single literal with 0 bits but then we
260 * don't see the literals. Therefore we force at least two
261 * literals to avoid this case. We don't care about order in
262 * this case, both literals get a 1 bit code.
263 */
264 while (heapLen < 2) {
265 int node = maxCode < 2 ? ++maxCode : 0;
266 heap[heapLen++] = node;
267 }
268
269 numCodes = Math.Max(maxCode + 1, minNumCodes);
270
271 int numLeafs = heapLen;
272 int[] childs = new int[4 * heapLen - 2];
273 int[] values = new int[2 * heapLen - 1];
274 int numNodes = numLeafs;
275 for (int i = 0; i < heapLen; i++) {
276 int node = heap[i];
277 childs[2 * i] = node;
278 childs[2 * i + 1] = -1;
279 values[i] = freqs[node] << 8;
280 heap[i] = i;
281 }
282
283 /* Construct the Huffman tree by repeatedly combining the least two
284 * frequent nodes.
285 */
286 do {
287 int first = heap[0];
288 int last = heap[--heapLen];
289
290 // Propagate the hole to the leafs of the heap
291 int ppos = 0;
292 int path = 1;
293
294 while (path < heapLen) {
295 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
296 path++;
297 }
298
299 heap[ppos] = heap[path];
300 ppos = path;
301 path = path * 2 + 1;
302 }
303
304 /* Now propagate the last element down along path. Normally
305 * it shouldn't go too deep.
306 */
307 int lastVal = values[last];
308 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
309 heap[path] = heap[ppos];
310 }
311 heap[path] = last;
312
313
314 int second = heap[0];
315
316 // Create a new node father of first and second
317 last = numNodes++;
318 childs[2 * last] = first;
319 childs[2 * last + 1] = second;
320 int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
321 values[last] = lastVal = values[first] + values[second] - mindepth + 1;
322
323 // Again, propagate the hole to the leafs
324 ppos = 0;
325 path = 1;
326
327 while (path < heapLen) {
328 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
329 path++;
330 }
331
332 heap[ppos] = heap[path];
333 ppos = path;
334 path = ppos * 2 + 1;
335 }
336
337 // Now propagate the new element down along path
338 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
339 heap[path] = heap[ppos];
340 }
341 heap[path] = last;
342 } while (heapLen > 1);
343
344 if (heap[0] != childs.Length / 2 - 1) {
345 throw new SharpZipBaseException("Heap invariant violated");
346 }
347
348 BuildLength(childs);
349 }
350
351 /// <summary>
352 /// Get encoded length
353 /// </summary>
354 /// <returns>Encoded length, the sum of frequencies * lengths</returns>
355 public int GetEncodedLength()
356 {
357 int len = 0;
358 for (int i = 0; i < freqs.Length; i++) {
359 len += freqs[i] * length[i];
360 }
361 return len;
362 }
363
364 /// <summary>
365 /// Scan a literal or distance tree to determine the frequencies of the codes
366 /// in the bit length tree.
367 /// </summary>
368 public void CalcBLFreq(Tree blTree)
369 {
370 int max_count; /* max repeat count */
371 int min_count; /* min repeat count */
372 int count; /* repeat count of the current code */
373 int curlen = -1; /* length of current code */
374
375 int i = 0;
376 while (i < numCodes) {
377 count = 1;
378 int nextlen = length[i];
379 if (nextlen == 0) {
380 max_count = 138;
381 min_count = 3;
382 } else {
383 max_count = 6;
384 min_count = 3;
385 if (curlen != nextlen) {
386 blTree.freqs[nextlen]++;
387 count = 0;
388 }
389 }
390 curlen = nextlen;
391 i++;
392
393 while (i < numCodes && curlen == length[i]) {
394 i++;
395 if (++count >= max_count) {
396 break;
397 }
398 }
399
400 if (count < min_count) {
401 blTree.freqs[curlen] += (short)count;
402 } else if (curlen != 0) {
403 blTree.freqs[REP_3_6]++;
404 } else if (count <= 10) {
405 blTree.freqs[REP_3_10]++;
406 } else {
407 blTree.freqs[REP_11_138]++;
408 }
409 }
410 }
411
412 /// <summary>
413 /// Write tree values
414 /// </summary>
415 /// <param name="blTree">Tree to write</param>
416 public void WriteTree(Tree blTree)
417 {
418 int max_count; // max repeat count
419 int min_count; // min repeat count
420 int count; // repeat count of the current code
421 int curlen = -1; // length of current code
422
423 int i = 0;
424 while (i < numCodes) {
425 count = 1;
426 int nextlen = length[i];
427 if (nextlen == 0) {
428 max_count = 138;
429 min_count = 3;
430 } else {
431 max_count = 6;
432 min_count = 3;
433 if (curlen != nextlen) {
434 blTree.WriteSymbol(nextlen);
435 count = 0;
436 }
437 }
438 curlen = nextlen;
439 i++;
440
441 while (i < numCodes && curlen == length[i]) {
442 i++;
443 if (++count >= max_count) {
444 break;
445 }
446 }
447
448 if (count < min_count) {
449 while (count-- > 0) {
450 blTree.WriteSymbol(curlen);
451 }
452 } else if (curlen != 0) {
453 blTree.WriteSymbol(REP_3_6);
454 dh.pending.WriteBits(count - 3, 2);
455 } else if (count <= 10) {
456 blTree.WriteSymbol(REP_3_10);
457 dh.pending.WriteBits(count - 3, 3);
458 } else {
459 blTree.WriteSymbol(REP_11_138);
460 dh.pending.WriteBits(count - 11, 7);
461 }
462 }
463 }
464
465 void BuildLength(int[] childs)
466 {
467 this.length = new byte [freqs.Length];
468 int numNodes = childs.Length / 2;
469 int numLeafs = (numNodes + 1) / 2;
470 int overflow = 0;
471
472 for (int i = 0; i < maxLength; i++) {
473 bl_counts[i] = 0;
474 }
475
476 // First calculate optimal bit lengths
477 int[] lengths = new int[numNodes];
478 lengths[numNodes-1] = 0;
479
480 for (int i = numNodes - 1; i >= 0; i--) {
481 if (childs[2 * i + 1] != -1) {
482 int bitLength = lengths[i] + 1;
483 if (bitLength > maxLength) {
484 bitLength = maxLength;
485 overflow++;
486 }
487 lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
488 } else {
489 // A leaf node
490 int bitLength = lengths[i];
491 bl_counts[bitLength - 1]++;
492 this.length[childs[2*i]] = (byte) lengths[i];
493 }
494 }
495
496 // if (DeflaterConstants.DEBUGGING) {
497 // //Console.WriteLine("Tree "+freqs.Length+" lengths:");
498 // for (int i=0; i < numLeafs; i++) {
499 // //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
500 // + " len: "+length[childs[2*i]]);
501 // }
502 // }
503
504 if (overflow == 0) {
505 return;
506 }
507
508 int incrBitLen = maxLength - 1;
509 do {
510 // Find the first bit length which could increase:
511 while (bl_counts[--incrBitLen] == 0)
512 ;
513
514 // Move this node one down and remove a corresponding
515 // number of overflow nodes.
516 do {
517 bl_counts[incrBitLen]--;
518 bl_counts[++incrBitLen]++;
519 overflow -= 1 << (maxLength - 1 - incrBitLen);
520 } while (overflow > 0 && incrBitLen < maxLength - 1);
521 } while (overflow > 0);
522
523 /* We may have overshot above. Move some nodes from maxLength to
524 * maxLength-1 in that case.
525 */
526 bl_counts[maxLength-1] += overflow;
527 bl_counts[maxLength-2] -= overflow;
528
529 /* Now recompute all bit lengths, scanning in increasing
530 * frequency. It is simpler to reconstruct all lengths instead of
531 * fixing only the wrong ones. This idea is taken from 'ar'
532 * written by Haruhiko Okumura.
533 *
534 * The nodes were inserted with decreasing frequency into the childs
535 * array.
536 */
537 int nodePtr = 2 * numLeafs;
538 for (int bits = maxLength; bits != 0; bits--) {
539 int n = bl_counts[bits-1];
540 while (n > 0) {
541 int childPtr = 2*childs[nodePtr++];
542 if (childs[childPtr + 1] == -1) {
543 // We found another leaf
544 length[childs[childPtr]] = (byte) bits;
545 n--;
546 }
547 }
548 }
549 // if (DeflaterConstants.DEBUGGING) {
550 // //Console.WriteLine("*** After overflow elimination. ***");
551 // for (int i=0; i < numLeafs; i++) {
552 // //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
553 // + " len: "+length[childs[2*i]]);
554 // }
555 // }
556 }
557
558 }
559
560 #region Instance Fields
561 /// <summary>
562 /// Pending buffer to use
563 /// </summary>
564 public DeflaterPending pending;
565
566 Tree literalTree;
567 Tree distTree;
568 Tree blTree;
569
570 // Buffer for distances
571 short[] d_buf;
572 byte[] l_buf;
573 int last_lit;
574 int extra_bits;
575 #endregion
576
577 static DeflaterHuffman()
578 {
579 // See RFC 1951 3.2.6
580 // Literal codes
581 staticLCodes = new short[LITERAL_NUM];
582 staticLLength = new byte[LITERAL_NUM];
583
584 int i = 0;
585 while (i < 144) {
586 staticLCodes[i] = BitReverse((0x030 + i) << 8);
587 staticLLength[i++] = 8;
588 }
589
590 while (i < 256) {
591 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
592 staticLLength[i++] = 9;
593 }
594
595 while (i < 280) {
596 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
597 staticLLength[i++] = 7;
598 }
599
600 while (i < LITERAL_NUM) {
601 staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
602 staticLLength[i++] = 8;
603 }
604
605 // Distance codes
606 staticDCodes = new short[DIST_NUM];
607 staticDLength = new byte[DIST_NUM];
608 for (i = 0; i < DIST_NUM; i++) {
609 staticDCodes[i] = BitReverse(i << 11);
610 staticDLength[i] = 5;
611 }
612 }
613
614 /// <summary>
615 /// Construct instance with pending buffer
616 /// </summary>
617 /// <param name="pending">Pending buffer to use</param>
618 public DeflaterHuffman(DeflaterPending pending)
619 {
620 this.pending = pending;
621
622 literalTree = new Tree(this, LITERAL_NUM, 257, 15);
623 distTree = new Tree(this, DIST_NUM, 1, 15);
624 blTree = new Tree(this, BITLEN_NUM, 4, 7);
625
626 d_buf = new short[BUFSIZE];
627 l_buf = new byte [BUFSIZE];
628 }
629
630 /// <summary>
631 /// Reset internal state
632 /// </summary>
633 public void Reset()
634 {
635 last_lit = 0;
636 extra_bits = 0;
637 literalTree.Reset();
638 distTree.Reset();
639 blTree.Reset();
640 }
641
642 /// <summary>
643 /// Write all trees to pending buffer
644 /// </summary>
645 /// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
646 public void SendAllTrees(int blTreeCodes)
647 {
648 blTree.BuildCodes();
649 literalTree.BuildCodes();
650 distTree.BuildCodes();
651 pending.WriteBits(literalTree.numCodes - 257, 5);
652 pending.WriteBits(distTree.numCodes - 1, 5);
653 pending.WriteBits(blTreeCodes - 4, 4);
654 for (int rank = 0; rank < blTreeCodes; rank++) {
655 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
656 }
657 literalTree.WriteTree(blTree);
658 distTree.WriteTree(blTree);
659
660 #if DebugDeflation
661 if (DeflaterConstants.DEBUGGING) {
662 blTree.CheckEmpty();
663 }
664 #endif
665 }
666
667 /// <summary>
668 /// Compress current buffer writing data to pending buffer
669 /// </summary>
670 public void CompressBlock()
671 {
672 for (int i = 0; i < last_lit; i++) {
673 int litlen = l_buf[i] & 0xff;
674 int dist = d_buf[i];
675 if (dist-- != 0) {
676 // if (DeflaterConstants.DEBUGGING) {
677 // Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
678 // }
679
680 int lc = Lcode(litlen);
681 literalTree.WriteSymbol(lc);
682
683 int bits = (lc - 261) / 4;
684 if (bits > 0 && bits <= 5) {
685 pending.WriteBits(litlen & ((1 << bits) - 1), bits);
686 }
687
688 int dc = Dcode(dist);
689 distTree.WriteSymbol(dc);
690
691 bits = dc / 2 - 1;
692 if (bits > 0) {
693 pending.WriteBits(dist & ((1 << bits) - 1), bits);
694 }
695 } else {
696 // if (DeflaterConstants.DEBUGGING) {
697 // if (litlen > 32 && litlen < 127) {
698 // Console.Write("("+(char)litlen+"): ");
699 // } else {
700 // Console.Write("{"+litlen+"}: ");
701 // }
702 // }
703 literalTree.WriteSymbol(litlen);
704 }
705 }
706
707 #if DebugDeflation
708 if (DeflaterConstants.DEBUGGING) {
709 Console.Write("EOF: ");
710 }
711 #endif
712 literalTree.WriteSymbol(EOF_SYMBOL);
713
714 #if DebugDeflation
715 if (DeflaterConstants.DEBUGGING) {
716 literalTree.CheckEmpty();
717 distTree.CheckEmpty();
718 }
719 #endif
720 }
721
722 /// <summary>
723 /// Flush block to output with no compression
724 /// </summary>
725 /// <param name="stored">Data to write</param>
726 /// <param name="storedOffset">Index of first byte to write</param>
727 /// <param name="storedLength">Count of bytes to write</param>
728 /// <param name="lastBlock">True if this is the last block</param>
729 public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
730 {
731 #if DebugDeflation
732 // if (DeflaterConstants.DEBUGGING) {
733 // //Console.WriteLine("Flushing stored block "+ storedLength);
734 // }
735 #endif
736 pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
737 pending.AlignToByte();
738 pending.WriteShort(storedLength);
739 pending.WriteShort(~storedLength);
740 pending.WriteBlock(stored, storedOffset, storedLength);
741 Reset();
742 }
743
744 /// <summary>
745 /// Flush block to output with compression
746 /// </summary>
747 /// <param name="stored">Data to flush</param>
748 /// <param name="storedOffset">Index of first byte to flush</param>
749 /// <param name="storedLength">Count of bytes to flush</param>
750 /// <param name="lastBlock">True if this is the last block</param>
751 public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
752 {
753 literalTree.freqs[EOF_SYMBOL]++;
754
755 // Build trees
756 literalTree.BuildTree();
757 distTree.BuildTree();
758
759 // Calculate bitlen frequency
760 literalTree.CalcBLFreq(blTree);
761 distTree.CalcBLFreq(blTree);
762
763 // Build bitlen tree
764 blTree.BuildTree();
765
766 int blTreeCodes = 4;
767 for (int i = 18; i > blTreeCodes; i--) {
768 if (blTree.length[BL_ORDER[i]] > 0) {
769 blTreeCodes = i+1;
770 }
771 }
772 int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
773 literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
774 extra_bits;
775
776 int static_len = extra_bits;
777 for (int i = 0; i < LITERAL_NUM; i++) {
778 static_len += literalTree.freqs[i] * staticLLength[i];
779 }
780 for (int i = 0; i < DIST_NUM; i++) {
781 static_len += distTree.freqs[i] * staticDLength[i];
782 }
783 if (opt_len >= static_len) {
784 // Force static trees
785 opt_len = static_len;
786 }
787
788 if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
789 // Store Block
790
791 // if (DeflaterConstants.DEBUGGING) {
792 // //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
793 // + " <= " + static_len);
794 // }
795 FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
796 } else if (opt_len == static_len) {
797 // Encode with static tree
798 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
799 literalTree.SetStaticCodes(staticLCodes, staticLLength);
800 distTree.SetStaticCodes(staticDCodes, staticDLength);
801 CompressBlock();
802 Reset();
803 } else {
804 // Encode with dynamic tree
805 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
806 SendAllTrees(blTreeCodes);
807 CompressBlock();
808 Reset();
809 }
810 }
811
812 /// <summary>
813 /// Get value indicating if internal buffer is full
814 /// </summary>
815 /// <returns>true if buffer is full</returns>
816 public bool IsFull()
817 {
818 return last_lit >= BUFSIZE;
819 }
820
821 /// <summary>
822 /// Add literal to buffer
823 /// </summary>
824 /// <param name="literal">Literal value to add to buffer.</param>
825 /// <returns>Value indicating internal buffer is full</returns>
826 public bool TallyLit(int literal)
827 {
828 // if (DeflaterConstants.DEBUGGING) {
829 // if (lit > 32 && lit < 127) {
830 // //Console.WriteLine("("+(char)lit+")");
831 // } else {
832 // //Console.WriteLine("{"+lit+"}");
833 // }
834 // }
835 d_buf[last_lit] = 0;
836 l_buf[last_lit++] = (byte)literal;
837 literalTree.freqs[literal]++;
838 return IsFull();
839 }
840
841 /// <summary>
842 /// Add distance code and length to literal and distance trees
843 /// </summary>
844 /// <param name="distance">Distance code</param>
845 /// <param name="length">Length</param>
846 /// <returns>Value indicating if internal buffer is full</returns>
847 public bool TallyDist(int distance, int length)
848 {
849 // if (DeflaterConstants.DEBUGGING) {
850 // //Console.WriteLine("[" + distance + "," + length + "]");
851 // }
852
853 d_buf[last_lit] = (short)distance;
854 l_buf[last_lit++] = (byte)(length - 3);
855
856 int lc = Lcode(length - 3);
857 literalTree.freqs[lc]++;
858 if (lc >= 265 && lc < 285) {
859 extra_bits += (lc - 261) / 4;
860 }
861
862 int dc = Dcode(distance - 1);
863 distTree.freqs[dc]++;
864 if (dc >= 4) {
865 extra_bits += dc / 2 - 1;
866 }
867 return IsFull();
868 }
869
870
871 /// <summary>
872 /// Reverse the bits of a 16 bit value.
873 /// </summary>
874 /// <param name="toReverse">Value to reverse bits</param>
875 /// <returns>Value with bits reversed</returns>
876 public static short BitReverse(int toReverse)
877 {
878 return (short) (bit4Reverse[toReverse & 0xF] << 12 |
879 bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
880 bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
881 bit4Reverse[toReverse >> 12]);
882 }
883
884 static int Lcode(int length)
885 {
886 if (length == 255) {
887 return 285;
888 }
889
890 int code = 257;
891 while (length >= 8) {
892 code += 4;
893 length >>= 1;
894 }
895 return code + length;
896 }
897
898 static int Dcode(int distance)
899 {
900 int code = 0;
901 while (distance >= 4) {
902 code += 2;
903 distance >>= 1;
904 }
905 return code + distance;
906 }
907 }
908 }