Mes documents/Visual Studio 2005/Projects/TES4ModTranslator/TES4ModTranslator/Zip/Compression/DeflaterHuffman.cs

Go to the documentation of this file.
00001 // DeflaterHuffman.cs
00002 //
00003 // Copyright (C) 2001 Mike Krueger
00004 // Copyright (C) 2004 John Reilly
00005 //
00006 // This file was translated from java, it was part of the GNU Classpath
00007 // Copyright (C) 2001 Free Software Foundation, Inc.
00008 //
00009 // This program is free software; you can redistribute it and/or
00010 // modify it under the terms of the GNU General Public License
00011 // as published by the Free Software Foundation; either version 2
00012 // of the License, or (at your option) any later version.
00013 //
00014 // This program is distributed in the hope that it will be useful,
00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017 // GNU General Public License for more details.
00018 //
00019 // You should have received a copy of the GNU General Public License
00020 // along with this program; if not, write to the Free Software
00021 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00022 //
00023 // Linking this library statically or dynamically with other modules is
00024 // making a combined work based on this library.  Thus, the terms and
00025 // conditions of the GNU General Public License cover the whole
00026 // combination.
00027 // 
00028 // As a special exception, the copyright holders of this library give you
00029 // permission to link this library with independent modules to produce an
00030 // executable, regardless of the license terms of these independent
00031 // modules, and to copy and distribute the resulting executable under
00032 // terms of your choice, provided that you also meet, for each linked
00033 // independent module, the terms and conditions of the license of that
00034 // module.  An independent module is a module which is not derived from
00035 // or based on this library.  If you modify this library, you may extend
00036 // this exception to your version of the library, but you are not
00037 // obligated to do so.  If you do not wish to do so, delete this
00038 // exception statement from your version.
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                                 //                              if (DeflaterConstants.DEBUGGING) {
00144                                 //                                      freqs[code]--;
00145                                 //                                      //        Console.Write("writeSymbol("+freqs.length+","+code+"): ");
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                                                 //Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
00162                                                 empty = false;
00163                                         }
00164                                 }
00165                                 
00166                                 if (!empty) {
00167                                         throw new SharpZipBaseException("!Empty");
00168                                 }
00169                                 //Console.WriteLine("checkEmpty suceeded!");
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                                 //                              if (DeflaterConstants.DEBUGGING) {
00194                                 //                                      //Console.WriteLine("buildCodes: "+freqs.Length);
00195                                 //                              }
00196                                 
00197                                 for (int bits = 0; bits < maxLength; bits++) {
00198                                         nextCode[bits] = code;
00199                                         code += bl_counts[bits] << (15 - bits);
00200                                         //                                      if (DeflaterConstants.DEBUGGING) {
00201                                         //                                              //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
00202                                         //                                                                +" nextCode: "+code);
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                                                 //                                              if (DeflaterConstants.DEBUGGING) {
00213                                                 //                                                              //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
00214                                                 //                                                                                +bits);
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                                 /* First calculate optimal bit lengths */
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                                                 /* A leaf node */
00247                                                 int bitLength = lengths[i];
00248                                                 bl_counts[bitLength - 1]++;
00249                                                 this.length[childs[2*i]] = (byte) lengths[i];
00250                                         }
00251                                 }
00252                                 
00253                                 //                              if (DeflaterConstants.DEBUGGING) {
00254                                 //                                      //Console.WriteLine("Tree "+freqs.Length+" lengths:");
00255                                 //                                      for (int i=0; i < numLeafs; i++) {
00256                                 //                                              //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
00257                                 //                                                                + " len: "+length[childs[2*i]]);
00258                                 //                                      }
00259                                 //                              }
00260                                 
00261                                 if (overflow == 0) {
00262                                         return;
00263                                 }
00264                                 
00265                                 int incrBitLen = maxLength - 1;
00266                                 do {
00267                                         /* Find the first bit length which could increase: */
00268                                         while (bl_counts[--incrBitLen] == 0)
00269                                                 ;
00270                                         
00271                                         /* Move this node one down and remove a corresponding
00272                                         * amount of overflow nodes.
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                                 /* We may have overshot above.  Move some nodes from maxLength to
00282                                 * maxLength-1 in that case.
00283                                 */
00284                                 bl_counts[maxLength-1] += overflow;
00285                                 bl_counts[maxLength-2] -= overflow;
00286                                 
00287                                 /* Now recompute all bit lengths, scanning in increasing
00288                                 * frequency.  It is simpler to reconstruct all lengths instead of
00289                                 * fixing only the wrong ones. This idea is taken from 'ar'
00290                                 * written by Haruhiko Okumura.
00291                                 *
00292                                 * The nodes were inserted with decreasing frequency into the childs
00293                                 * array.
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                                                         /* We found another leaf */
00302                                                         length[childs[childPtr]] = (byte) bits;
00303                                                         n--;
00304                                                 }
00305                                         }
00306                                 }
00307                                 //                              if (DeflaterConstants.DEBUGGING) {
00308                                 //                                      //Console.WriteLine("*** After overflow elimination. ***");
00309                                 //                                      for (int i=0; i < numLeafs; i++) {
00310                                 //                                              //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
00311                                 //                                                                + " len: "+length[childs[2*i]]);
00312                                 //                                      }
00313                                 //                              }
00314                         }
00315                         
00319                         public void BuildTree()
00320                         {
00321                                 int numSymbols = freqs.Length;
00322                                 
00323                                 /* heap is a priority queue, sorted by frequency, least frequent
00324                                 * nodes first.  The heap is a binary tree, with the property, that
00325                                 * the parent node is smaller than both child nodes.  This assures
00326                                 * that the smallest node is the first parent.
00327                                 *
00328                                 * The binary tree is encoded in an array:  0 is root node and
00329                                 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
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                                                 /* Insert n into heap */
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                                 /* We could encode a single literal with 0 bits but then we
00351                                 * don't see the literals.  Therefore we force at least two
00352                                 * literals to avoid this case.  We don't care about order in
00353                                 * this case, both literals get a 1 bit code.
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                                 /* Construct the Huffman tree by repeatedly combining the least two
00375                                 * frequent nodes.
00376                                 */
00377                                 do {
00378                                         int first = heap[0];
00379                                         int last  = heap[--heapLen];
00380                                         
00381                                         /* Propagate the hole to the leafs of the heap */
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                                         /* Now propagate the last element down along path.  Normally
00396                                         * it shouldn't go too deep.
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                                         /* Create a new node father of first and second */
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                                         /* Again, propagate the hole to the leafs */
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                                         /* Now propagate the new element down along path */
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;               /* max repeat count */
00461                                 int min_count;               /* min repeat count */
00462                                 int count;                   /* repeat count of the current code */
00463                                 int curlen = -1;             /* length of current code */
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;               /* max repeat count */
00509                                 int min_count;               /* min repeat count */
00510                                 int count;                   /* repeat count of the current code */
00511                                 int curlen = -1;             /* length of current code */
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                         /* See RFC 1951 3.2.6 */
00590                         /* Literal codes */
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                         /* Distant codes */
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                         //                      if (DeflaterConstants.DEBUGGING) {
00689                         //                              blTree.CheckEmpty();
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                                         //                                      if (DeflaterConstants.DEBUGGING) {
00703                                         //                                              Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
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                                         //                                      if (DeflaterConstants.DEBUGGING) {
00723                                         //                                              if (litlen > 32 && litlen < 127) {
00724                                         //                                                      Console.Write("("+(char)litlen+"): ");
00725                                         //                                              } else {
00726                                         //                                                      Console.Write("{"+litlen+"}: ");
00727                                         //                                              }
00728                                         //                                      }
00729                                         literalTree.WriteSymbol(litlen);
00730                                 }
00731                         }
00732                         //                      if (DeflaterConstants.DEBUGGING) {
00733                         //                              Console.Write("EOF: ");
00734                         //                      }
00735                         literalTree.WriteSymbol(EOF_SYMBOL);
00736                         //                      if (DeflaterConstants.DEBUGGING) {
00737                         //                              literalTree.CheckEmpty();
00738                         //                              distTree.CheckEmpty();
00739                         //                      }
00740                 }
00741                 
00749                 public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
00750                 {
00751                         //                      if (DeflaterConstants.DEBUGGING) {
00752                         //                              //Console.WriteLine("Flushing stored block "+ storedLength);
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                         /* Build trees */
00774                         literalTree.BuildTree();
00775                         distTree.BuildTree();
00776                         
00777                         /* Calculate bitlen frequency */
00778                         literalTree.CalcBLFreq(blTree);
00779                         distTree.CalcBLFreq(blTree);
00780                         
00781                         /* Build bitlen tree */
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                                 /* Force static trees */
00803                                 opt_len = static_len;
00804                         }
00805                         
00806                         if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
00807                                 /* Store Block */
00808                                 //                              if (DeflaterConstants.DEBUGGING) {
00809                                 //                                      //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
00810                                 //                                                        + " <= " + static_len);
00811                                 //                              }
00812                                 FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
00813                         } else if (opt_len == static_len) {
00814                                 /* Encode with static tree */
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                                 /* Encode with dynamic tree */
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                         //                      if (DeflaterConstants.DEBUGGING) {
00846                         //                              if (lit > 32 && lit < 127) {
00847                         //                                      //Console.WriteLine("("+(char)lit+")");
00848                         //                              } else {
00849                         //                                      //Console.WriteLine("{"+lit+"}");
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                         //                      if (DeflaterConstants.DEBUGGING) {
00867                         //                              //Console.WriteLine("["+dist+","+len+"]");
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 }

Generated on Fri Jun 23 21:50:04 2006 for OblivionModTranslator by  doxygen 1.4.6-NO