code.grnet.gr Git - pithos-ms-client/blob - trunk/hammock/src/net35/ICSharpCode.SharpZipLib.Silverlight/Zip/Compression/DeflaterHuffman.cs

   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 using ICSharpCode.SharpZipLib.Silverlight.Zip.Compression;
  42
  43 namespace ICSharpCode.SharpZipLib.Silverlight.Zip.Compression
  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 readonly short[] staticLCodes;
  96         static readonly byte[]  staticLLength;
  97         static readonly short[] staticDCodes;
  98         static readonly byte[]  staticDLength;
  99
 100         class Tree
 101         {
 102             #region Instance Fields
 103             public readonly short[] freqs;
 104
 105             public byte[]  length;
 106
 107             public readonly int     minNumCodes;
 108
 109             public int     numCodes;
 110
 111             short[] codes;
 112             readonly int[]   bl_counts;
 113             readonly int     maxLength;
 114             readonly 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                 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             /// Set static codes and length
 152             /// </summary>
 153             /// <param name="staticCodes">new codes</param>
 154             /// <param name="staticLengths">length for new codes</param>
 155             public void SetStaticCodes(short[] staticCodes, byte[] staticLengths)
 156             {
 157                 codes = staticCodes;
 158                 length = staticLengths;
 159             }
 160
 161             /// <summary>
 162             /// Build dynamic codes and lengths
 163             /// </summary>
 164             public void BuildCodes()
 165             {
 166                 var nextCode = new int[maxLength];
 167                 var code = 0;
 168
 169                 codes = new short[freqs.Length];
 170
 171                 //                              if (DeflaterConstants.DEBUGGING) {
 172                 //                                      //Console.WriteLine("buildCodes: "+freqs.Length);
 173                 //                              }
 174
 175                 for (int bits = 0; bits < maxLength; bits++) {
 176                     nextCode[bits] = code;
 177                     code += bl_counts[bits] << (15 - bits);
 178
 179                     //                                  if (DeflaterConstants.DEBUGGING) {
 180                     //                                          //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
 181                     //                                                            +" nextCode: "+code);
 182                     //                                  }
 183                 }
 184                 for (int i=0; i < numCodes; i++) {
 185                     int bits = length[i];
 186                     if (bits > 0) {
 187
 188                         //                                              if (DeflaterConstants.DEBUGGING) {
 189                         //                                                              //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
 190                         //                                                                                +bits);
 191                         //                                              }
 192
 193                         codes[i] = BitReverse(nextCode[bits-1]);
 194                         nextCode[bits-1] += 1 << (16 - bits);
 195                     }
 196                 }
 197             }
 198
 199             public void BuildTree()
 200             {
 201                 int numSymbols = freqs.Length;
 202
 203                 /* heap is a priority queue, sorted by frequency, least frequent
 204                                 * nodes first.  The heap is a binary tree, with the property, that
 205                                 * the parent node is smaller than both child nodes.  This assures
 206                                 * that the smallest node is the first parent.
 207                                 *
 208                                 * The binary tree is encoded in an array:  0 is root node and
 209                                 * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
 210                                 */
 211                 var heap = new int[numSymbols];
 212                 var heapLen = 0;
 213                 var maxCode = 0;
 214                 for (var n = 0; n < numSymbols; n++) {
 215                     int freq = freqs[n];
 216                     if (freq == 0)
 217                     {
 218                         continue;
 219                     }
 220
 221                     // Insert n into heap
 222                     var pos = heapLen++;
 223                     int ppos;
 224                     while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
 225                         heap[pos] = heap[ppos];
 226                         pos = ppos;
 227                     }
 228                     heap[pos] = n;
 229
 230                     maxCode = n;
 231                 }
 232
 233                 /* We could encode a single literal with 0 bits but then we
 234                                 * don't see the literals.  Therefore we force at least two
 235                                 * literals to avoid this case.  We don't care about order in
 236                                 * this case, both literals get a 1 bit code.
 237                                 */
 238                 while (heapLen < 2) {
 239                     int node = maxCode < 2 ? ++maxCode : 0;
 240                     heap[heapLen++] = node;
 241                 }
 242
 243                 numCodes = Math.Max(maxCode + 1, minNumCodes);
 244
 245                 var numLeafs = heapLen;
 246                 var childs = new int[4 * heapLen - 2];
 247                 var values = new int[2 * heapLen - 1];
 248                 var numNodes = numLeafs;
 249                 for (var i = 0; i < heapLen; i++) {
 250                     var node = heap[i];
 251                     childs[2 * i]   = node;
 252                     childs[2 * i + 1] = -1;
 253                     values[i] = freqs[node] << 8;
 254                     heap[i] = i;
 255                 }
 256
 257                 /* Construct the Huffman tree by repeatedly combining the least two
 258                                 * frequent nodes.
 259                                 */
 260                 do {
 261                     int first = heap[0];
 262                     int last  = heap[--heapLen];
 263
 264                     // Propagate the hole to the leafs of the heap
 265                     int ppos = 0;
 266                     int path = 1;
 267
 268                     while (path < heapLen) {
 269                         if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
 270                             path++;
 271                         }
 272
 273                         heap[ppos] = heap[path];
 274                         ppos = path;
 275                         path = path * 2 + 1;
 276                     }
 277
 278                     /* Now propagate the last element down along path.  Normally
 279                                         * it shouldn't go too deep.
 280                                         */
 281                     int lastVal = values[last];
 282                     while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
 283                         heap[path] = heap[ppos];
 284                     }
 285                     heap[path] = last;
 286
 287
 288                     int second = heap[0];
 289
 290                     // Create a new node father of first and second
 291                     last = numNodes++;
 292                     childs[2 * last] = first;
 293                     childs[2 * last + 1] = second;
 294                     int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
 295                     values[last] = lastVal = values[first] + values[second] - mindepth + 1;
 296
 297                     // Again, propagate the hole to the leafs
 298                     ppos = 0;
 299                     path = 1;
 300
 301                     while (path < heapLen) {
 302                         if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
 303                             path++;
 304                         }
 305
 306                         heap[ppos] = heap[path];
 307                         ppos = path;
 308                         path = ppos * 2 + 1;
 309                     }
 310
 311                     // Now propagate the new element down along path
 312                     while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
 313                         heap[path] = heap[ppos];
 314                     }
 315                     heap[path] = last;
 316                 } while (heapLen > 1);
 317
 318                 if (heap[0] != childs.Length / 2 - 1) {
 319                     throw new SharpZipBaseException("Heap invariant violated");
 320                 }
 321
 322                 BuildLength(childs);
 323             }
 324
 325             /// <summary>
 326             /// Get encoded length
 327             /// </summary>
 328             /// <returns>Encoded length, the sum of frequencies * lengths</returns>
 329             public int GetEncodedLength()
 330             {
 331                 int len = 0;
 332                 for (int i = 0; i < freqs.Length; i++) {
 333                     len += freqs[i] * length[i];
 334                 }
 335                 return len;
 336             }
 337
 338             /// <summary>
 339             /// Scan a literal or distance tree to determine the frequencies of the codes
 340             /// in the bit length tree.
 341             /// </summary>
 342             public void CalcBLFreq(Tree blTree)
 343             {
 344                 var curlen = -1;             /* length of current code */
 345                 var i = 0;
 346
 347                 while (i < numCodes) {
 348                     var count = 1;                   /* repeat count of the current code */
 349                     int nextlen = length[i];
 350                     int max_count;               /* max repeat count */
 351                     int min_count;               /* min repeat count */
 352                     if (nextlen == 0) {
 353                         max_count = 138;
 354                         min_count = 3;
 355                     } else {
 356                         max_count = 6;
 357                         min_count = 3;
 358                         if (curlen != nextlen) {
 359                             blTree.freqs[nextlen]++;
 360                             count = 0;
 361                         }
 362                     }
 363                     curlen = nextlen;
 364                     i++;
 365
 366                     while (i < numCodes && curlen == length[i]) {
 367                         i++;
 368                         if (++count >= max_count) {
 369                             break;
 370                         }
 371                     }
 372
 373                     if (count < min_count) {
 374                         blTree.freqs[curlen] += (short)count;
 375                     } else if (curlen != 0) {
 376                         blTree.freqs[REP_3_6]++;
 377                     } else if (count <= 10) {
 378                         blTree.freqs[REP_3_10]++;
 379                     } else {
 380                         blTree.freqs[REP_11_138]++;
 381                     }
 382                 }
 383             }
 384
 385             /// <summary>
 386             /// Write tree values
 387             /// </summary>
 388             /// <param name="blTree">Tree to write</param>
 389             public void WriteTree(Tree blTree)
 390             {
 391                 var curlen = -1;             // length of current code
 392
 393                 var i = 0;
 394                 while (i < numCodes) {
 395                     var count = 1;                   // repeat count of the current code
 396                     int nextlen = length[i];
 397                     int max_count;               // max repeat count
 398                     int min_count;               // min repeat count
 399                     if (nextlen == 0) {
 400                         max_count = 138;
 401                         min_count = 3;
 402                     } else {
 403                         max_count = 6;
 404                         min_count = 3;
 405                         if (curlen != nextlen) {
 406                             blTree.WriteSymbol(nextlen);
 407                             count = 0;
 408                         }
 409                     }
 410                     curlen = nextlen;
 411                     i++;
 412
 413                     while (i < numCodes && curlen == length[i]) {
 414                         i++;
 415                         if (++count >= max_count) {
 416                             break;
 417                         }
 418                     }
 419
 420                     if (count < min_count) {
 421                         while (count-- > 0) {
 422                             blTree.WriteSymbol(curlen);
 423                         }
 424                     } else if (curlen != 0) {
 425                         blTree.WriteSymbol(REP_3_6);
 426                         dh.pending.WriteBits(count - 3, 2);
 427                     } else if (count <= 10) {
 428                         blTree.WriteSymbol(REP_3_10);
 429                         dh.pending.WriteBits(count - 3, 3);
 430                     } else {
 431                         blTree.WriteSymbol(REP_11_138);
 432                         dh.pending.WriteBits(count - 11, 7);
 433                     }
 434                 }
 435             }
 436
 437             void BuildLength(int[] childs)
 438             {
 439                 length = new byte [freqs.Length];
 440                 var numNodes = childs.Length / 2;
 441                 var numLeafs = (numNodes + 1) / 2;
 442                 var overflow = 0;
 443
 444                 for (var i = 0; i < maxLength; i++) {
 445                     bl_counts[i] = 0;
 446                 }
 447
 448                 // First calculate optimal bit lengths
 449                 var lengths = new int[numNodes];
 450                 lengths[numNodes-1] = 0;
 451
 452                 for (int i = numNodes - 1; i >= 0; i--) {
 453                     if (childs[2 * i + 1] != -1) {
 454                         int bitLength = lengths[i] + 1;
 455                         if (bitLength > maxLength) {
 456                             bitLength = maxLength;
 457                             overflow++;
 458                         }
 459                         lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
 460                     } else {
 461                         // A leaf node
 462                         var bitLength = lengths[i];
 463                         bl_counts[bitLength - 1]++;
 464                         length[childs[2*i]] = (byte) lengths[i];
 465                     }
 466                 }
 467
 468                 //                              if (DeflaterConstants.DEBUGGING) {
 469                 //                                      //Console.WriteLine("Tree "+freqs.Length+" lengths:");
 470                 //                                      for (int i=0; i < numLeafs; i++) {
 471                 //                                              //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 472                 //                                                                + " len: "+length[childs[2*i]]);
 473                 //                                      }
 474                 //                              }
 475
 476                 if (overflow == 0) {
 477                     return;
 478                 }
 479
 480                 int incrBitLen = maxLength - 1;
 481                 do {
 482                     // Find the first bit length which could increase:
 483                     while (bl_counts[--incrBitLen] == 0)
 484                     {
 485
 486                     }
 487
 488                     // Move this node one down and remove a corresponding
 489                     // number of overflow nodes.
 490                     do {
 491                         bl_counts[incrBitLen]--;
 492                         bl_counts[++incrBitLen]++;
 493                         overflow -= 1 << (maxLength - 1 - incrBitLen);
 494                     } while (overflow > 0 && incrBitLen < maxLength - 1);
 495                 } while (overflow > 0);
 496
 497                 /* We may have overshot above.  Move some nodes from maxLength to
 498                                 * maxLength-1 in that case.
 499                                 */
 500                 bl_counts[maxLength-1] += overflow;
 501                 bl_counts[maxLength-2] -= overflow;
 502
 503                 /* Now recompute all bit lengths, scanning in increasing
 504                                 * frequency.  It is simpler to reconstruct all lengths instead of
 505                                 * fixing only the wrong ones. This idea is taken from 'ar'
 506                                 * written by Haruhiko Okumura.
 507                                 *
 508                                 * The nodes were inserted with decreasing frequency into the childs
 509                                 * array.
 510                                 */
 511                 int nodePtr = 2 * numLeafs;
 512                 for (int bits = maxLength; bits != 0; bits--) {
 513                     int n = bl_counts[bits-1];
 514                     while (n > 0) {
 515                         int childPtr = 2*childs[nodePtr++];
 516                         if (childs[childPtr + 1] == -1) {
 517                             // We found another leaf
 518                             length[childs[childPtr]] = (byte) bits;
 519                             n--;
 520                         }
 521                     }
 522                 }
 523                 //                              if (DeflaterConstants.DEBUGGING) {
 524                 //                                      //Console.WriteLine("*** After overflow elimination. ***");
 525                 //                                      for (int i=0; i < numLeafs; i++) {
 526                 //                                              //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 527                 //                                                                + " len: "+length[childs[2*i]]);
 528                 //                                      }
 529                 //                              }
 530             }
 531
 532         }
 533
 534         #region Instance Fields
 535         /// <summary>
 536         /// Pending buffer to use
 537         /// </summary>
 538         public DeflaterPending pending;
 539
 540         readonly Tree literalTree;
 541         readonly Tree distTree;
 542         readonly Tree blTree;
 543
 544         // Buffer for distances
 545         readonly short[] d_buf;
 546         readonly byte[]  l_buf;
 547         int last_lit;
 548         int extra_bits;
 549         #endregion
 550
 551         static DeflaterHuffman()
 552         {
 553             // See RFC 1951 3.2.6
 554             // Literal codes
 555             staticLCodes = new short[LITERAL_NUM];
 556             staticLLength = new byte[LITERAL_NUM];
 557
 558             int i = 0;
 559             while (i < 144) {
 560                 staticLCodes[i] = BitReverse((0x030 + i) << 8);
 561                 staticLLength[i++] = 8;
 562             }
 563
 564             while (i < 256) {
 565                 staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
 566                 staticLLength[i++] = 9;
 567             }
 568
 569             while (i < 280) {
 570                 staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
 571                 staticLLength[i++] = 7;
 572             }
 573
 574             while (i < LITERAL_NUM) {
 575                 staticLCodes[i] = BitReverse((0x0c0 - 280 + i)  << 8);
 576                 staticLLength[i++] = 8;
 577             }
 578
 579             // Distance codes
 580             staticDCodes = new short[DIST_NUM];
 581             staticDLength = new byte[DIST_NUM];
 582             for (i = 0; i < DIST_NUM; i++) {
 583                 staticDCodes[i] = BitReverse(i << 11);
 584                 staticDLength[i] = 5;
 585             }
 586         }
 587
 588         /// <summary>
 589         /// Construct instance with pending buffer
 590         /// </summary>
 591         /// <param name="pending">Pending buffer to use</param>
 592         public DeflaterHuffman(DeflaterPending pending)
 593         {
 594             this.pending = pending;
 595
 596             literalTree = new Tree(this, LITERAL_NUM, 257, 15);
 597             distTree    = new Tree(this, DIST_NUM, 1, 15);
 598             blTree      = new Tree(this, BITLEN_NUM, 4, 7);
 599
 600             d_buf = new short[BUFSIZE];
 601             l_buf = new byte [BUFSIZE];
 602         }
 603
 604         /// <summary>
 605         /// Reset internal state
 606         /// </summary>
 607         public void Reset()
 608         {
 609             last_lit = 0;
 610             extra_bits = 0;
 611             literalTree.Reset();
 612             distTree.Reset();
 613             blTree.Reset();
 614         }
 615
 616         /// <summary>
 617         /// Write all trees to pending buffer
 618         /// </summary>
 619         /// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
 620         public void SendAllTrees(int blTreeCodes)
 621         {
 622             blTree.BuildCodes();
 623             literalTree.BuildCodes();
 624             distTree.BuildCodes();
 625             pending.WriteBits(literalTree.numCodes - 257, 5);
 626             pending.WriteBits(distTree.numCodes - 1, 5);
 627             pending.WriteBits(blTreeCodes - 4, 4);
 628             for (int rank = 0; rank < blTreeCodes; rank++) {
 629                 pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
 630             }
 631             literalTree.WriteTree(blTree);
 632             distTree.WriteTree(blTree);
 633         }
 634
 635         /// <summary>
 636         /// Compress current buffer writing data to pending buffer
 637         /// </summary>
 638         public void CompressBlock()
 639         {
 640             for (int i = 0; i < last_lit; i++) {
 641                 int litlen = l_buf[i] & 0xff;
 642                 int dist = d_buf[i];
 643                 if (dist-- != 0) {
 644                     //                                  if (DeflaterConstants.DEBUGGING) {
 645                     //                                          Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
 646                     //                                  }
 647
 648                     int lc = Lcode(litlen);
 649                     literalTree.WriteSymbol(lc);
 650
 651                     int bits = (lc - 261) / 4;
 652                     if (bits > 0 && bits <= 5) {
 653                         pending.WriteBits(litlen & ((1 << bits) - 1), bits);
 654                     }
 655
 656                     int dc = Dcode(dist);
 657                     distTree.WriteSymbol(dc);
 658
 659                     bits = dc / 2 - 1;
 660                     if (bits > 0) {
 661                         pending.WriteBits(dist & ((1 << bits) - 1), bits);
 662                     }
 663                 } else {
 664                     //                                  if (DeflaterConstants.DEBUGGING) {
 665                     //                                          if (litlen > 32 && litlen < 127) {
 666                     //                                                  Console.Write("("+(char)litlen+"): ");
 667                     //                                          } else {
 668                     //                                                  Console.Write("{"+litlen+"}: ");
 669                     //                                          }
 670                     //                                  }
 671                     literalTree.WriteSymbol(litlen);
 672                 }
 673             }
 674             literalTree.WriteSymbol(EOF_SYMBOL);
 675         }
 676
 677         /// <summary>
 678         /// Flush block to output with no compression
 679         /// </summary>
 680         /// <param name="stored">Data to write</param>
 681         /// <param name="storedOffset">Index of first byte to write</param>
 682         /// <param name="storedLength">Count of bytes to write</param>
 683         /// <param name="lastBlock">True if this is the last block</param>
 684         public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
 685         {
 686             pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
 687             pending.AlignToByte();
 688             pending.WriteShort(storedLength);
 689             pending.WriteShort(~storedLength);
 690             pending.WriteBlock(stored, storedOffset, storedLength);
 691             Reset();
 692         }
 693
 694         /// <summary>
 695         /// Flush block to output with compression
 696         /// </summary>
 697         /// <param name="stored">Data to flush</param>
 698         /// <param name="storedOffset">Index of first byte to flush</param>
 699         /// <param name="storedLength">Count of bytes to flush</param>
 700         /// <param name="lastBlock">True if this is the last block</param>
 701         public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
 702         {
 703             literalTree.freqs[EOF_SYMBOL]++;
 704
 705             // Build trees
 706             literalTree.BuildTree();
 707             distTree.BuildTree();
 708
 709             // Calculate bitlen frequency
 710             literalTree.CalcBLFreq(blTree);
 711             distTree.CalcBLFreq(blTree);
 712
 713             // Build bitlen tree
 714             blTree.BuildTree();
 715
 716             int blTreeCodes = 4;
 717             for (int i = 18; i > blTreeCodes; i--) {
 718                 if (blTree.length[BL_ORDER[i]] > 0) {
 719                     blTreeCodes = i+1;
 720                 }
 721             }
 722             int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
 723                           literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
 724                           extra_bits;
 725
 726             int static_len = extra_bits;
 727             for (int i = 0; i < LITERAL_NUM; i++) {
 728                 static_len += literalTree.freqs[i] * staticLLength[i];
 729             }
 730             for (int i = 0; i < DIST_NUM; i++) {
 731                 static_len += distTree.freqs[i] * staticDLength[i];
 732             }
 733             if (opt_len >= static_len) {
 734                 // Force static trees
 735                 opt_len = static_len;
 736             }
 737
 738             if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
 739                 // Store Block
 740
 741                 //                              if (DeflaterConstants.DEBUGGING) {
 742                 //                                      //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
 743                 //                                                        + " <= " + static_len);
 744                 //                              }
 745                 FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
 746             } else if (opt_len == static_len) {
 747                 // Encode with static tree
 748                 pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
 749                 literalTree.SetStaticCodes(staticLCodes, staticLLength);
 750                 distTree.SetStaticCodes(staticDCodes, staticDLength);
 751                 CompressBlock();
 752                 Reset();
 753             } else {
 754                 // Encode with dynamic tree
 755                 pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
 756                 SendAllTrees(blTreeCodes);
 757                 CompressBlock();
 758                 Reset();
 759             }
 760         }
 761
 762         /// <summary>
 763         /// Get value indicating if internal buffer is full
 764         /// </summary>
 765         /// <returns>true if buffer is full</returns>
 766         public bool IsFull()
 767         {
 768             return last_lit >= BUFSIZE;
 769         }
 770
 771         /// <summary>
 772         /// Add literal to buffer
 773         /// </summary>
 774         /// <param name="literal">Literal value to add to buffer.</param>
 775         /// <returns>Value indicating internal buffer is full</returns>
 776         public bool TallyLit(int literal)
 777         {
 778             //                  if (DeflaterConstants.DEBUGGING) {
 779             //                          if (lit > 32 && lit < 127) {
 780             //                                  //Console.WriteLine("("+(char)lit+")");
 781             //                          } else {
 782             //                                  //Console.WriteLine("{"+lit+"}");
 783             //                          }
 784             //                  }
 785             d_buf[last_lit] = 0;
 786             l_buf[last_lit++] = (byte)literal;
 787             literalTree.freqs[literal]++;
 788             return IsFull();
 789         }
 790
 791         /// <summary>
 792         /// Add distance code and length to literal and distance trees
 793         /// </summary>
 794         /// <param name="distance">Distance code</param>
 795         /// <param name="length">Length</param>
 796         /// <returns>Value indicating if internal buffer is full</returns>
 797         public bool TallyDist(int distance, int length)
 798         {
 799             //                  if (DeflaterConstants.DEBUGGING) {
 800             //                          //Console.WriteLine("[" + distance + "," + length + "]");
 801             //                  }
 802
 803             d_buf[last_lit]   = (short)distance;
 804             l_buf[last_lit++] = (byte)(length - 3);
 805
 806             int lc = Lcode(length - 3);
 807             literalTree.freqs[lc]++;
 808             if (lc >= 265 && lc < 285) {
 809                 extra_bits += (lc - 261) / 4;
 810             }
 811
 812             int dc = Dcode(distance - 1);
 813             distTree.freqs[dc]++;
 814             if (dc >= 4) {
 815                 extra_bits += dc / 2 - 1;
 816             }
 817             return IsFull();
 818         }
 819
 820
 821         /// <summary>
 822         /// Reverse the bits of a 16 bit value.
 823         /// </summary>
 824         /// <param name="toReverse">Value to reverse bits</param>
 825         /// <returns>Value with bits reversed</returns>
 826         public static short BitReverse(int toReverse)
 827         {
 828             return (short) (bit4Reverse[toReverse & 0xF] << 12 |
 829                             bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
 830                             bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
 831                             bit4Reverse[toReverse >> 12]);
 832         }
 833
 834         static int Lcode(int length)
 835         {
 836             if (length == 255) {
 837                 return 285;
 838             }
 839
 840             int code = 257;
 841             while (length >= 8) {
 842                 code += 4;
 843                 length >>= 1;
 844             }
 845             return code + length;
 846         }
 847
 848         static int Dcode(int distance)
 849         {
 850             int code = 0;
 851             while (distance >= 4) {
 852                 code += 2;
 853                 distance >>= 1;
 854             }
 855             return code + distance;
 856         }
 857     }
 858 }