00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 using System;
00041
00042 namespace ICSharpCode.SharpZipLib.Zip.Compression
00043 {
00044
00053 public class DeflaterHuffman
00054 {
00055 static int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
00056 static int LITERAL_NUM = 286;
00057 static int DIST_NUM = 30;
00058 static int BITLEN_NUM = 19;
00059 static int REP_3_6 = 16;
00060 static int REP_3_10 = 17;
00061 static int REP_11_138 = 18;
00062 static int EOF_SYMBOL = 256;
00063 static int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
00064
00065 static byte[] bit4Reverse = {
00066 0,
00067 8,
00068 4,
00069 12,
00070 2,
00071 10,
00072 6,
00073 14,
00074 1,
00075 9,
00076 5,
00077 13,
00078 3,
00079 11,
00080 7,
00081 15
00082 };
00083
00087 public class Tree
00088 {
00092 public short[] freqs;
00093
00097 public byte[] length;
00098
00102 public int minNumCodes;
00103
00107 public int numCodes;
00108
00109 short[] codes;
00110 int[] bl_counts;
00111 int maxLength;
00112 DeflaterHuffman dh;
00113
00117 public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
00118 {
00119 this.dh = dh;
00120 this.minNumCodes = minCodes;
00121 this.maxLength = maxLength;
00122 freqs = new short[elems];
00123 bl_counts = new int[maxLength];
00124 }
00125
00129 public void Reset()
00130 {
00131 for (int i = 0; i < freqs.Length; i++) {
00132 freqs[i] = 0;
00133 }
00134 codes = null;
00135 length = null;
00136 }
00137
00141 public void WriteSymbol(int code)
00142 {
00143
00144
00145
00146
00147 dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
00148 }
00149
00156 public void CheckEmpty()
00157 {
00158 bool empty = true;
00159 for (int i = 0; i < freqs.Length; i++) {
00160 if (freqs[i] != 0) {
00161
00162 empty = false;
00163 }
00164 }
00165
00166 if (!empty) {
00167 throw new SharpZipBaseException("!Empty");
00168 }
00169
00170 }
00171
00177 public void SetStaticCodes(short[] stCodes, byte[] stLength)
00178 {
00179 codes = stCodes;
00180 length = stLength;
00181 }
00182
00186 public void BuildCodes()
00187 {
00188 int numSymbols = freqs.Length;
00189 int[] nextCode = new int[maxLength];
00190 int code = 0;
00191 codes = new short[freqs.Length];
00192
00193
00194
00195
00196
00197 for (int bits = 0; bits < maxLength; bits++) {
00198 nextCode[bits] = code;
00199 code += bl_counts[bits] << (15 - bits);
00200
00201
00202
00203
00204 }
00205 if (DeflaterConstants.DEBUGGING && code != 65536) {
00206 throw new SharpZipBaseException("Inconsistent bl_counts!");
00207 }
00208
00209 for (int i=0; i < numCodes; i++) {
00210 int bits = length[i];
00211 if (bits > 0) {
00212
00213
00214
00215
00216 codes[i] = BitReverse(nextCode[bits-1]);
00217 nextCode[bits-1] += 1 << (16 - bits);
00218 }
00219 }
00220 }
00221
00222 void BuildLength(int[] childs)
00223 {
00224 this.length = new byte [freqs.Length];
00225 int numNodes = childs.Length / 2;
00226 int numLeafs = (numNodes + 1) / 2;
00227 int overflow = 0;
00228
00229 for (int i = 0; i < maxLength; i++) {
00230 bl_counts[i] = 0;
00231 }
00232
00233
00234 int[] lengths = new int[numNodes];
00235 lengths[numNodes-1] = 0;
00236
00237 for (int i = numNodes - 1; i >= 0; i--) {
00238 if (childs[2*i+1] != -1) {
00239 int bitLength = lengths[i] + 1;
00240 if (bitLength > maxLength) {
00241 bitLength = maxLength;
00242 overflow++;
00243 }
00244 lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
00245 } else {
00246
00247 int bitLength = lengths[i];
00248 bl_counts[bitLength - 1]++;
00249 this.length[childs[2*i]] = (byte) lengths[i];
00250 }
00251 }
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261 if (overflow == 0) {
00262 return;
00263 }
00264
00265 int incrBitLen = maxLength - 1;
00266 do {
00267
00268 while (bl_counts[--incrBitLen] == 0)
00269 ;
00270
00271
00272
00273
00274 do {
00275 bl_counts[incrBitLen]--;
00276 bl_counts[++incrBitLen]++;
00277 overflow -= 1 << (maxLength - 1 - incrBitLen);
00278 } while (overflow > 0 && incrBitLen < maxLength - 1);
00279 } while (overflow > 0);
00280
00281
00282
00283
00284 bl_counts[maxLength-1] += overflow;
00285 bl_counts[maxLength-2] -= overflow;
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295 int nodePtr = 2 * numLeafs;
00296 for (int bits = maxLength; bits != 0; bits--) {
00297 int n = bl_counts[bits-1];
00298 while (n > 0) {
00299 int childPtr = 2*childs[nodePtr++];
00300 if (childs[childPtr + 1] == -1) {
00301
00302 length[childs[childPtr]] = (byte) bits;
00303 n--;
00304 }
00305 }
00306 }
00307
00308
00309
00310
00311
00312
00313
00314 }
00315
00319 public void BuildTree()
00320 {
00321 int numSymbols = freqs.Length;
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331 int[] heap = new int[numSymbols];
00332 int heapLen = 0;
00333 int maxCode = 0;
00334 for (int n = 0; n < numSymbols; n++) {
00335 int freq = freqs[n];
00336 if (freq != 0) {
00337
00338 int pos = heapLen++;
00339 int ppos;
00340 while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
00341 heap[pos] = heap[ppos];
00342 pos = ppos;
00343 }
00344 heap[pos] = n;
00345
00346 maxCode = n;
00347 }
00348 }
00349
00350
00351
00352
00353
00354
00355 while (heapLen < 2) {
00356 int node = maxCode < 2 ? ++maxCode : 0;
00357 heap[heapLen++] = node;
00358 }
00359
00360 numCodes = Math.Max(maxCode + 1, minNumCodes);
00361
00362 int numLeafs = heapLen;
00363 int[] childs = new int[4*heapLen - 2];
00364 int[] values = new int[2*heapLen - 1];
00365 int numNodes = numLeafs;
00366 for (int i = 0; i < heapLen; i++) {
00367 int node = heap[i];
00368 childs[2*i] = node;
00369 childs[2*i+1] = -1;
00370 values[i] = freqs[node] << 8;
00371 heap[i] = i;
00372 }
00373
00374
00375
00376
00377 do {
00378 int first = heap[0];
00379 int last = heap[--heapLen];
00380
00381
00382 int ppos = 0;
00383 int path = 1;
00384
00385 while (path < heapLen) {
00386 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
00387 path++;
00388 }
00389
00390 heap[ppos] = heap[path];
00391 ppos = path;
00392 path = path * 2 + 1;
00393 }
00394
00395
00396
00397
00398 int lastVal = values[last];
00399 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
00400 heap[path] = heap[ppos];
00401 }
00402 heap[path] = last;
00403
00404
00405 int second = heap[0];
00406
00407
00408 last = numNodes++;
00409 childs[2*last] = first;
00410 childs[2*last+1] = second;
00411 int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
00412 values[last] = lastVal = values[first] + values[second] - mindepth + 1;
00413
00414
00415 ppos = 0;
00416 path = 1;
00417
00418 while (path < heapLen) {
00419 if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
00420 path++;
00421 }
00422
00423 heap[ppos] = heap[path];
00424 ppos = path;
00425 path = ppos * 2 + 1;
00426 }
00427
00428
00429 while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
00430 heap[path] = heap[ppos];
00431 }
00432 heap[path] = last;
00433 } while (heapLen > 1);
00434
00435 if (heap[0] != childs.Length / 2 - 1) {
00436 throw new SharpZipBaseException("Heap invariant violated");
00437 }
00438
00439 BuildLength(childs);
00440 }
00441
00446 public int GetEncodedLength()
00447 {
00448 int len = 0;
00449 for (int i = 0; i < freqs.Length; i++) {
00450 len += freqs[i] * length[i];
00451 }
00452 return len;
00453 }
00454
00458 public void CalcBLFreq(Tree blTree)
00459 {
00460 int max_count;
00461 int min_count;
00462 int count;
00463 int curlen = -1;
00464
00465 int i = 0;
00466 while (i < numCodes) {
00467 count = 1;
00468 int nextlen = length[i];
00469 if (nextlen == 0) {
00470 max_count = 138;
00471 min_count = 3;
00472 } else {
00473 max_count = 6;
00474 min_count = 3;
00475 if (curlen != nextlen) {
00476 blTree.freqs[nextlen]++;
00477 count = 0;
00478 }
00479 }
00480 curlen = nextlen;
00481 i++;
00482
00483 while (i < numCodes && curlen == length[i]) {
00484 i++;
00485 if (++count >= max_count) {
00486 break;
00487 }
00488 }
00489
00490 if (count < min_count) {
00491 blTree.freqs[curlen] += (short)count;
00492 } else if (curlen != 0) {
00493 blTree.freqs[REP_3_6]++;
00494 } else if (count <= 10) {
00495 blTree.freqs[REP_3_10]++;
00496 } else {
00497 blTree.freqs[REP_11_138]++;
00498 }
00499 }
00500 }
00501
00506 public void WriteTree(Tree blTree)
00507 {
00508 int max_count;
00509 int min_count;
00510 int count;
00511 int curlen = -1;
00512
00513 int i = 0;
00514 while (i < numCodes) {
00515 count = 1;
00516 int nextlen = length[i];
00517 if (nextlen == 0) {
00518 max_count = 138;
00519 min_count = 3;
00520 } else {
00521 max_count = 6;
00522 min_count = 3;
00523 if (curlen != nextlen) {
00524 blTree.WriteSymbol(nextlen);
00525 count = 0;
00526 }
00527 }
00528 curlen = nextlen;
00529 i++;
00530
00531 while (i < numCodes && curlen == length[i]) {
00532 i++;
00533 if (++count >= max_count) {
00534 break;
00535 }
00536 }
00537
00538 if (count < min_count) {
00539 while (count-- > 0) {
00540 blTree.WriteSymbol(curlen);
00541 }
00542 } else if (curlen != 0) {
00543 blTree.WriteSymbol(REP_3_6);
00544 dh.pending.WriteBits(count - 3, 2);
00545 } else if (count <= 10) {
00546 blTree.WriteSymbol(REP_3_10);
00547 dh.pending.WriteBits(count - 3, 3);
00548 } else {
00549 blTree.WriteSymbol(REP_11_138);
00550 dh.pending.WriteBits(count - 11, 7);
00551 }
00552 }
00553 }
00554 }
00555
00559 public DeflaterPending pending;
00560
00561 Tree literalTree, distTree, blTree;
00562
00563 short[] d_buf;
00564 byte[] l_buf;
00565 int last_lit;
00566 int extra_bits;
00567
00568 static short[] staticLCodes;
00569 static byte[] staticLLength;
00570 static short[] staticDCodes;
00571 static byte[] staticDLength;
00572
00578 public static short BitReverse(int toReverse)
00579 {
00580 return (short) (bit4Reverse[toReverse & 0xF] << 12 |
00581 bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
00582 bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
00583 bit4Reverse[toReverse >> 12]);
00584 }
00585
00586
00587 static DeflaterHuffman()
00588 {
00589
00590
00591 staticLCodes = new short[LITERAL_NUM];
00592 staticLLength = new byte[LITERAL_NUM];
00593 int i = 0;
00594 while (i < 144) {
00595 staticLCodes[i] = BitReverse((0x030 + i) << 8);
00596 staticLLength[i++] = 8;
00597 }
00598 while (i < 256) {
00599 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
00600 staticLLength[i++] = 9;
00601 }
00602 while (i < 280) {
00603 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
00604 staticLLength[i++] = 7;
00605 }
00606 while (i < LITERAL_NUM) {
00607 staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
00608 staticLLength[i++] = 8;
00609 }
00610
00611
00612 staticDCodes = new short[DIST_NUM];
00613 staticDLength = new byte[DIST_NUM];
00614 for (i = 0; i < DIST_NUM; i++) {
00615 staticDCodes[i] = BitReverse(i << 11);
00616 staticDLength[i] = 5;
00617 }
00618 }
00619
00624 public DeflaterHuffman(DeflaterPending pending)
00625 {
00626 this.pending = pending;
00627
00628 literalTree = new Tree(this, LITERAL_NUM, 257, 15);
00629 distTree = new Tree(this, DIST_NUM, 1, 15);
00630 blTree = new Tree(this, BITLEN_NUM, 4, 7);
00631
00632 d_buf = new short[BUFSIZE];
00633 l_buf = new byte [BUFSIZE];
00634 }
00635
00639 public void Reset()
00640 {
00641 last_lit = 0;
00642 extra_bits = 0;
00643 literalTree.Reset();
00644 distTree.Reset();
00645 blTree.Reset();
00646 }
00647
00648 int Lcode(int len)
00649 {
00650 if (len == 255) {
00651 return 285;
00652 }
00653
00654 int code = 257;
00655 while (len >= 8) {
00656 code += 4;
00657 len >>= 1;
00658 }
00659 return code + len;
00660 }
00661
00662 int Dcode(int distance)
00663 {
00664 int code = 0;
00665 while (distance >= 4) {
00666 code += 2;
00667 distance >>= 1;
00668 }
00669 return code + distance;
00670 }
00671
00675 public void SendAllTrees(int blTreeCodes)
00676 {
00677 blTree.BuildCodes();
00678 literalTree.BuildCodes();
00679 distTree.BuildCodes();
00680 pending.WriteBits(literalTree.numCodes - 257, 5);
00681 pending.WriteBits(distTree.numCodes - 1, 5);
00682 pending.WriteBits(blTreeCodes - 4, 4);
00683 for (int rank = 0; rank < blTreeCodes; rank++) {
00684 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
00685 }
00686 literalTree.WriteTree(blTree);
00687 distTree.WriteTree(blTree);
00688
00689
00690
00691 }
00692
00696 public void CompressBlock()
00697 {
00698 for (int i = 0; i < last_lit; i++) {
00699 int litlen = l_buf[i] & 0xff;
00700 int dist = d_buf[i];
00701 if (dist-- != 0) {
00702
00703
00704
00705
00706 int lc = Lcode(litlen);
00707 literalTree.WriteSymbol(lc);
00708
00709 int bits = (lc - 261) / 4;
00710 if (bits > 0 && bits <= 5) {
00711 pending.WriteBits(litlen & ((1 << bits) - 1), bits);
00712 }
00713
00714 int dc = Dcode(dist);
00715 distTree.WriteSymbol(dc);
00716
00717 bits = dc / 2 - 1;
00718 if (bits > 0) {
00719 pending.WriteBits(dist & ((1 << bits) - 1), bits);
00720 }
00721 } else {
00722
00723
00724
00725
00726
00727
00728
00729 literalTree.WriteSymbol(litlen);
00730 }
00731 }
00732
00733
00734
00735 literalTree.WriteSymbol(EOF_SYMBOL);
00736
00737
00738
00739
00740 }
00741
00749 public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
00750 {
00751
00752
00753
00754 pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
00755 pending.AlignToByte();
00756 pending.WriteShort(storedLength);
00757 pending.WriteShort(~storedLength);
00758 pending.WriteBlock(stored, storedOffset, storedLength);
00759 Reset();
00760 }
00761
00769 public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
00770 {
00771 literalTree.freqs[EOF_SYMBOL]++;
00772
00773
00774 literalTree.BuildTree();
00775 distTree.BuildTree();
00776
00777
00778 literalTree.CalcBLFreq(blTree);
00779 distTree.CalcBLFreq(blTree);
00780
00781
00782 blTree.BuildTree();
00783
00784 int blTreeCodes = 4;
00785 for (int i = 18; i > blTreeCodes; i--) {
00786 if (blTree.length[BL_ORDER[i]] > 0) {
00787 blTreeCodes = i+1;
00788 }
00789 }
00790 int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
00791 literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
00792 extra_bits;
00793
00794 int static_len = extra_bits;
00795 for (int i = 0; i < LITERAL_NUM; i++) {
00796 static_len += literalTree.freqs[i] * staticLLength[i];
00797 }
00798 for (int i = 0; i < DIST_NUM; i++) {
00799 static_len += distTree.freqs[i] * staticDLength[i];
00800 }
00801 if (opt_len >= static_len) {
00802
00803 opt_len = static_len;
00804 }
00805
00806 if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
00807
00808
00809
00810
00811
00812 FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
00813 } else if (opt_len == static_len) {
00814
00815 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
00816 literalTree.SetStaticCodes(staticLCodes, staticLLength);
00817 distTree.SetStaticCodes(staticDCodes, staticDLength);
00818 CompressBlock();
00819 Reset();
00820 } else {
00821
00822 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
00823 SendAllTrees(blTreeCodes);
00824 CompressBlock();
00825 Reset();
00826 }
00827 }
00828
00833 public bool IsFull()
00834 {
00835 return last_lit >= BUFSIZE;
00836 }
00837
00843 public bool TallyLit(int lit)
00844 {
00845
00846
00847
00848
00849
00850
00851
00852 d_buf[last_lit] = 0;
00853 l_buf[last_lit++] = (byte)lit;
00854 literalTree.freqs[lit]++;
00855 return IsFull();
00856 }
00857
00864 public bool TallyDist(int dist, int len)
00865 {
00866
00867
00868
00869
00870 d_buf[last_lit] = (short)dist;
00871 l_buf[last_lit++] = (byte)(len - 3);
00872
00873 int lc = Lcode(len - 3);
00874 literalTree.freqs[lc]++;
00875 if (lc >= 265 && lc < 285) {
00876 extra_bits += (lc - 261) / 4;
00877 }
00878
00879 int dc = Dcode(dist - 1);
00880 distTree.freqs[dc]++;
00881 if (dc >= 4) {
00882 extra_bits += dc / 2 - 1;
00883 }
00884 return IsFull();
00885 }
00886 }
00887 }