3
// Copyright (C) 2001 Mike Krueger
4
// Copyright (C) 2004 John Reilly
6
// This file was translated from java, it was part of the GNU Classpath
7
// Copyright (C) 2001 Free Software Foundation, Inc.
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.
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.
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.
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
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.
42
namespace Plupload.PngEncoder {
45
/// This is the DeflaterHuffman class.
47
/// This class is <i>not</i> thread safe. This is inherent in the API, due
48
/// to the split of Deflate and SetInput.
50
/// author of the original java version : Jochen Hoenicke
52
public class DeflaterHuffman {
53
const int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
54
const int LITERAL_NUM = 286;
56
// Number of distance codes
57
const int DIST_NUM = 30;
58
// Number of codes used to transfer bit lengths
59
const int BITLEN_NUM = 19;
61
// repeat previous bit length 3-6 times (2 bits of repeat count)
62
const int REP_3_6 = 16;
63
// repeat a zero length 3-10 times (3 bits of repeat count)
64
const int REP_3_10 = 17;
65
// repeat a zero length 11-138 times (7 bits of repeat count)
66
const int REP_11_138 = 18;
68
const int EOF_SYMBOL = 256;
70
// The lengths of the bit length codes are sent in order of decreasing
71
// probability, to avoid transmitting the lengths for unused bit length codes.
72
static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
74
static readonly byte[] bit4Reverse = {
93
static short[] staticLCodes;
94
static byte[] staticLLength;
95
static short[] staticDCodes;
96
static byte[] staticDLength;
99
#region Instance Fields
100
public short[] freqs;
102
public byte[] length;
104
public int minNumCodes;
115
public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength) {
117
this.minNumCodes = minCodes;
118
this.maxLength = maxLength;
119
freqs = new short[elems];
120
bl_counts = new int[maxLength];
126
/// Resets the internal state of the tree
128
public void Reset() {
129
for (int i = 0; i < freqs.Length; i++) {
136
public void WriteSymbol(int code) {
137
// if (DeflaterConstants.DEBUGGING) {
139
// // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
141
dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
145
/// Check that all frequencies are zero
147
/// <exception cref="SharpZipBaseException">
148
/// At least one frequency is non-zero
150
public void CheckEmpty() {
152
for (int i = 0; i < freqs.Length; i++) {
154
//Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
160
throw new Exception("!Empty");
165
/// Set static codes and length
167
/// <param name="staticCodes">new codes</param>
168
/// <param name="staticLengths">length for new codes</param>
169
public void SetStaticCodes(short[] staticCodes, byte[] staticLengths) {
171
length = staticLengths;
175
/// Build dynamic codes and lengths
177
public void BuildCodes() {
178
int numSymbols = freqs.Length;
179
int[] nextCode = new int[maxLength];
182
codes = new short[freqs.Length];
184
// if (DeflaterConstants.DEBUGGING) {
185
// //Console.WriteLine("buildCodes: "+freqs.Length);
188
for (int bits = 0; bits < maxLength; bits++) {
189
nextCode[bits] = code;
190
code += bl_counts[bits] << (15 - bits);
192
// if (DeflaterConstants.DEBUGGING) {
193
// //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
194
// +" nextCode: "+code);
199
if ( DeflaterConstants.DEBUGGING && (code != 65536) )
201
throw new SharpZipBaseException("Inconsistent bl_counts!");
204
for (int i = 0; i < numCodes; i++) {
205
int bits = length[i];
208
// if (DeflaterConstants.DEBUGGING) {
209
// //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
213
codes[i] = BitReverse(nextCode[bits - 1]);
214
nextCode[bits - 1] += 1 << (16 - bits);
219
public void BuildTree() {
220
int numSymbols = freqs.Length;
222
/* heap is a priority queue, sorted by frequency, least frequent
223
* nodes first. The heap is a binary tree, with the property, that
224
* the parent node is smaller than both child nodes. This assures
225
* that the smallest node is the first parent.
227
* The binary tree is encoded in an array: 0 is root node and
228
* the nodes 2*n+1, 2*n+2 are the child nodes of node n.
230
int[] heap = new int[numSymbols];
233
for (int n = 0; n < numSymbols; n++) {
236
// Insert n into heap
239
while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
240
heap[pos] = heap[ppos];
249
/* We could encode a single literal with 0 bits but then we
250
* don't see the literals. Therefore we force at least two
251
* literals to avoid this case. We don't care about order in
252
* this case, both literals get a 1 bit code.
254
while (heapLen < 2) {
255
int node = maxCode < 2 ? ++maxCode : 0;
256
heap[heapLen++] = node;
259
numCodes = Math.Max(maxCode + 1, minNumCodes);
261
int numLeafs = heapLen;
262
int[] childs = new int[4 * heapLen - 2];
263
int[] values = new int[2 * heapLen - 1];
264
int numNodes = numLeafs;
265
for (int i = 0; i < heapLen; i++) {
267
childs[2 * i] = node;
268
childs[2 * i + 1] = -1;
269
values[i] = freqs[node] << 8;
273
/* Construct the Huffman tree by repeatedly combining the least two
278
int last = heap[--heapLen];
280
// Propagate the hole to the leafs of the heap
284
while (path < heapLen) {
285
if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) {
289
heap[ppos] = heap[path];
294
/* Now propagate the last element down along path. Normally
295
* it shouldn't go too deep.
297
int lastVal = values[last];
298
while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) {
299
heap[path] = heap[ppos];
304
int second = heap[0];
306
// Create a new node father of first and second
308
childs[2 * last] = first;
309
childs[2 * last + 1] = second;
310
int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
311
values[last] = lastVal = values[first] + values[second] - mindepth + 1;
313
// Again, propagate the hole to the leafs
317
while (path < heapLen) {
318
if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) {
322
heap[ppos] = heap[path];
327
// Now propagate the new element down along path
328
while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) {
329
heap[path] = heap[ppos];
332
} while (heapLen > 1);
334
if (heap[0] != childs.Length / 2 - 1) {
335
throw new Exception("Heap invariant violated");
342
/// Get encoded length
344
/// <returns>Encoded length, the sum of frequencies * lengths</returns>
345
public int GetEncodedLength() {
347
for (int i = 0; i < freqs.Length; i++) {
348
len += freqs[i] * length[i];
354
/// Scan a literal or distance tree to determine the frequencies of the codes
355
/// in the bit length tree.
357
public void CalcBLFreq(Tree blTree) {
358
int max_count; /* max repeat count */
359
int min_count; /* min repeat count */
360
int count; /* repeat count of the current code */
361
int curlen = -1; /* length of current code */
364
while (i < numCodes) {
366
int nextlen = length[i];
373
if (curlen != nextlen) {
374
blTree.freqs[nextlen]++;
381
while (i < numCodes && curlen == length[i]) {
383
if (++count >= max_count) {
388
if (count < min_count) {
389
blTree.freqs[curlen] += (short) count;
390
} else if (curlen != 0) {
391
blTree.freqs[REP_3_6]++;
392
} else if (count <= 10) {
393
blTree.freqs[REP_3_10]++;
395
blTree.freqs[REP_11_138]++;
401
/// Write tree values
403
/// <param name="blTree">Tree to write</param>
404
public void WriteTree(Tree blTree) {
405
int max_count; // max repeat count
406
int min_count; // min repeat count
407
int count; // repeat count of the current code
408
int curlen = -1; // length of current code
411
while (i < numCodes) {
413
int nextlen = length[i];
420
if (curlen != nextlen) {
421
blTree.WriteSymbol(nextlen);
428
while (i < numCodes && curlen == length[i]) {
430
if (++count >= max_count) {
435
if (count < min_count) {
436
while (count-- > 0) {
437
blTree.WriteSymbol(curlen);
439
} else if (curlen != 0) {
440
blTree.WriteSymbol(REP_3_6);
441
dh.pending.WriteBits(count - 3, 2);
442
} else if (count <= 10) {
443
blTree.WriteSymbol(REP_3_10);
444
dh.pending.WriteBits(count - 3, 3);
446
blTree.WriteSymbol(REP_11_138);
447
dh.pending.WriteBits(count - 11, 7);
452
void BuildLength(int[] childs) {
453
this.length = new byte[freqs.Length];
454
int numNodes = childs.Length / 2;
455
int numLeafs = (numNodes + 1) / 2;
458
for (int i = 0; i < maxLength; i++) {
462
// First calculate optimal bit lengths
463
int[] lengths = new int[numNodes];
464
lengths[numNodes - 1] = 0;
466
for (int i = numNodes - 1; i >= 0; i--) {
467
if (childs[2 * i + 1] != -1) {
468
int bitLength = lengths[i] + 1;
469
if (bitLength > maxLength) {
470
bitLength = maxLength;
473
lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
476
int bitLength = lengths[i];
477
bl_counts[bitLength - 1]++;
478
this.length[childs[2 * i]] = (byte) lengths[i];
482
// if (DeflaterConstants.DEBUGGING) {
483
// //Console.WriteLine("Tree "+freqs.Length+" lengths:");
484
// for (int i=0; i < numLeafs; i++) {
485
// //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
486
// + " len: "+length[childs[2*i]]);
494
int incrBitLen = maxLength - 1;
496
// Find the first bit length which could increase:
497
while (bl_counts[--incrBitLen] == 0)
500
// Move this node one down and remove a corresponding
501
// number of overflow nodes.
503
bl_counts[incrBitLen]--;
504
bl_counts[++incrBitLen]++;
505
overflow -= 1 << (maxLength - 1 - incrBitLen);
506
} while (overflow > 0 && incrBitLen < maxLength - 1);
507
} while (overflow > 0);
509
/* We may have overshot above. Move some nodes from maxLength to
510
* maxLength-1 in that case.
512
bl_counts[maxLength - 1] += overflow;
513
bl_counts[maxLength - 2] -= overflow;
515
/* Now recompute all bit lengths, scanning in increasing
516
* frequency. It is simpler to reconstruct all lengths instead of
517
* fixing only the wrong ones. This idea is taken from 'ar'
518
* written by Haruhiko Okumura.
520
* The nodes were inserted with decreasing frequency into the childs
523
int nodePtr = 2 * numLeafs;
524
for (int bits = maxLength; bits != 0; bits--) {
525
int n = bl_counts[bits - 1];
527
int childPtr = 2 * childs[nodePtr++];
528
if (childs[childPtr + 1] == -1) {
529
// We found another leaf
530
length[childs[childPtr]] = (byte) bits;
535
// if (DeflaterConstants.DEBUGGING) {
536
// //Console.WriteLine("*** After overflow elimination. ***");
537
// for (int i=0; i < numLeafs; i++) {
538
// //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
539
// + " len: "+length[childs[2*i]]);
546
#region Instance Fields
548
/// Pending buffer to use
550
public DeflaterPending pending;
556
// Buffer for distances
563
static DeflaterHuffman() {
564
// See RFC 1951 3.2.6
566
staticLCodes = new short[LITERAL_NUM];
567
staticLLength = new byte[LITERAL_NUM];
571
staticLCodes[i] = BitReverse((0x030 + i) << 8);
572
staticLLength[i++] = 8;
576
staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
577
staticLLength[i++] = 9;
581
staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
582
staticLLength[i++] = 7;
585
while (i < LITERAL_NUM) {
586
staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
587
staticLLength[i++] = 8;
591
staticDCodes = new short[DIST_NUM];
592
staticDLength = new byte[DIST_NUM];
593
for (i = 0; i < DIST_NUM; i++) {
594
staticDCodes[i] = BitReverse(i << 11);
595
staticDLength[i] = 5;
600
/// Construct instance with pending buffer
602
/// <param name="pending">Pending buffer to use</param>
603
public DeflaterHuffman(DeflaterPending pending) {
604
this.pending = pending;
606
literalTree = new Tree(this, LITERAL_NUM, 257, 15);
607
distTree = new Tree(this, DIST_NUM, 1, 15);
608
blTree = new Tree(this, BITLEN_NUM, 4, 7);
610
d_buf = new short[BUFSIZE];
611
l_buf = new byte[BUFSIZE];
615
/// Reset internal state
617
public void Reset() {
626
/// Write all trees to pending buffer
628
/// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
629
public void SendAllTrees(int blTreeCodes) {
631
literalTree.BuildCodes();
632
distTree.BuildCodes();
633
pending.WriteBits(literalTree.numCodes - 257, 5);
634
pending.WriteBits(distTree.numCodes - 1, 5);
635
pending.WriteBits(blTreeCodes - 4, 4);
636
for (int rank = 0; rank < blTreeCodes; rank++) {
637
pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
639
literalTree.WriteTree(blTree);
640
distTree.WriteTree(blTree);
643
if (DeflaterConstants.DEBUGGING) {
650
/// Compress current buffer writing data to pending buffer
652
public void CompressBlock() {
653
for (int i = 0; i < last_lit; i++) {
654
int litlen = l_buf[i] & 0xff;
657
// if (DeflaterConstants.DEBUGGING) {
658
// Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
661
int lc = Lcode(litlen);
662
literalTree.WriteSymbol(lc);
664
int bits = (lc - 261) / 4;
665
if (bits > 0 && bits <= 5) {
666
pending.WriteBits(litlen & ((1 << bits) - 1), bits);
669
int dc = Dcode(dist);
670
distTree.WriteSymbol(dc);
674
pending.WriteBits(dist & ((1 << bits) - 1), bits);
677
// if (DeflaterConstants.DEBUGGING) {
678
// if (litlen > 32 && litlen < 127) {
679
// Console.Write("("+(char)litlen+"): ");
681
// Console.Write("{"+litlen+"}: ");
684
literalTree.WriteSymbol(litlen);
689
if (DeflaterConstants.DEBUGGING) {
690
Console.Write("EOF: ");
693
literalTree.WriteSymbol(EOF_SYMBOL);
696
if (DeflaterConstants.DEBUGGING) {
697
literalTree.CheckEmpty();
698
distTree.CheckEmpty();
704
/// Flush block to output with no compression
706
/// <param name="stored">Data to write</param>
707
/// <param name="storedOffset">Index of first byte to write</param>
708
/// <param name="storedLength">Count of bytes to write</param>
709
/// <param name="lastBlock">True if this is the last block</param>
710
public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock) {
712
// if (DeflaterConstants.DEBUGGING) {
713
// //Console.WriteLine("Flushing stored block "+ storedLength);
716
pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
717
pending.AlignToByte();
718
pending.WriteShort(storedLength);
719
pending.WriteShort(~storedLength);
720
pending.WriteBlock(stored, storedOffset, storedLength);
725
/// Flush block to output with compression
727
/// <param name="stored">Data to flush</param>
728
/// <param name="storedOffset">Index of first byte to flush</param>
729
/// <param name="storedLength">Count of bytes to flush</param>
730
/// <param name="lastBlock">True if this is the last block</param>
731
public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock) {
732
literalTree.freqs[EOF_SYMBOL]++;
735
literalTree.BuildTree();
736
distTree.BuildTree();
738
// Calculate bitlen frequency
739
literalTree.CalcBLFreq(blTree);
740
distTree.CalcBLFreq(blTree);
746
for (int i = 18; i > blTreeCodes; i--) {
747
if (blTree.length[BL_ORDER[i]] > 0) {
751
int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
752
literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
755
int static_len = extra_bits;
756
for (int i = 0; i < LITERAL_NUM; i++) {
757
static_len += literalTree.freqs[i] * staticLLength[i];
759
for (int i = 0; i < DIST_NUM; i++) {
760
static_len += distTree.freqs[i] * staticDLength[i];
762
if (opt_len >= static_len) {
763
// Force static trees
764
opt_len = static_len;
767
if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
770
// if (DeflaterConstants.DEBUGGING) {
771
// //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
772
// + " <= " + static_len);
774
FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
775
} else if (opt_len == static_len) {
776
// Encode with static tree
777
pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
778
literalTree.SetStaticCodes(staticLCodes, staticLLength);
779
distTree.SetStaticCodes(staticDCodes, staticDLength);
783
// Encode with dynamic tree
784
pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
785
SendAllTrees(blTreeCodes);
792
/// Get value indicating if internal buffer is full
794
/// <returns>true if buffer is full</returns>
795
public bool IsFull() {
796
return last_lit >= BUFSIZE;
800
/// Add literal to buffer
802
/// <param name="literal">Literal value to add to buffer.</param>
803
/// <returns>Value indicating internal buffer is full</returns>
804
public bool TallyLit(int literal) {
805
// if (DeflaterConstants.DEBUGGING) {
806
// if (lit > 32 && lit < 127) {
807
// //Console.WriteLine("("+(char)lit+")");
809
// //Console.WriteLine("{"+lit+"}");
813
l_buf[last_lit++] = (byte) literal;
814
literalTree.freqs[literal]++;
819
/// Add distance code and length to literal and distance trees
821
/// <param name="distance">Distance code</param>
822
/// <param name="length">Length</param>
823
/// <returns>Value indicating if internal buffer is full</returns>
824
public bool TallyDist(int distance, int length) {
825
// if (DeflaterConstants.DEBUGGING) {
826
// //Console.WriteLine("[" + distance + "," + length + "]");
829
d_buf[last_lit] = (short) distance;
830
l_buf[last_lit++] = (byte) (length - 3);
832
int lc = Lcode(length - 3);
833
literalTree.freqs[lc]++;
834
if (lc >= 265 && lc < 285) {
835
extra_bits += (lc - 261) / 4;
838
int dc = Dcode(distance - 1);
839
distTree.freqs[dc]++;
841
extra_bits += dc / 2 - 1;
848
/// Reverse the bits of a 16 bit value.
850
/// <param name="toReverse">Value to reverse bits</param>
851
/// <returns>Value with bits reversed</returns>
852
public static short BitReverse(int toReverse) {
853
return (short) (bit4Reverse[toReverse & 0xF] << 12 |
854
bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
855
bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
856
bit4Reverse[toReverse >> 12]);
859
static int Lcode(int length) {
865
while (length >= 8) {
869
return code + length;
872
static int Dcode(int distance) {
874
while (distance >= 4) {
878
return code + distance;
added
removed
debian/missing-sources/plupload-1.5.7/csharp/Plupload/PngEncoder/DeflaterHuffman.cs
