Summary

Class:ICSharpCode.SharpZipLib.Zip.Compression.DeflaterHuffman
Assembly:ICSharpCode.SharpZipLib
File(s):C:\Users\Neil\Documents\Visual Studio 2015\Projects\icsharpcode\SZL_master\ICSharpCode.SharpZipLib\Zip\Compression\DeflaterHuffman.cs
Covered lines:349
Uncovered lines:9
Coverable lines:358
Total lines:865
Line coverage:97.4%
Branch coverage:91.1%

Metrics

MethodCyclomatic ComplexitySequence CoverageBranch Coverage
.cctor()6100100
.ctor(...)1100100
Reset()1100100
SendAllTrees(...)2100100
CompressBlock()6100100
FlushStoredBlock(...)3100100
FlushBlock(...)1310085.71
IsFull()1100100
TallyLit(...)1100100
TallyDist(...)4100100
BitReverse(...)1100100
Lcode(...)3100100
Dcode(...)2100100
.ctor(...)1100100
Reset()2100100
WriteSymbol(...)1100100
CheckEmpty()300
SetStaticCodes(...)1100100
BuildCodes()4100100
BuildTree()2198.5197.44
GetEncodedLength()2100100
CalcBLFreq(...)10100100
WriteTree(...)1191.1885.71
BuildLength(...)1310084

File(s)

C:\Users\Neil\Documents\Visual Studio 2015\Projects\icsharpcode\SZL_master\ICSharpCode.SharpZipLib\Zip\Compression\DeflaterHuffman.cs

#LineLine coverage
 1using System;
 2
 3namespace ICSharpCode.SharpZipLib.Zip.Compression
 4{
 5  /// <summary>
 6  /// This is the DeflaterHuffman class.
 7  ///
 8  /// This class is <i>not</i> thread safe.  This is inherent in the API, due
 9  /// to the split of Deflate and SetInput.
 10  ///
 11  /// author of the original java version : Jochen Hoenicke
 12  /// </summary>
 13  public class DeflaterHuffman
 14  {
 15    const int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
 16    const int LITERAL_NUM = 286;
 17
 18    // Number of distance codes
 19    const int DIST_NUM = 30;
 20    // Number of codes used to transfer bit lengths
 21    const int BITLEN_NUM = 19;
 22
 23    // repeat previous bit length 3-6 times (2 bits of repeat count)
 24    const int REP_3_6 = 16;
 25    // repeat a zero length 3-10 times  (3 bits of repeat count)
 26    const int REP_3_10 = 17;
 27    // repeat a zero length 11-138 times  (7 bits of repeat count)
 28    const int REP_11_138 = 18;
 29
 30    const int EOF_SYMBOL = 256;
 31
 32    // The lengths of the bit length codes are sent in order of decreasing
 33    // probability, to avoid transmitting the lengths for unused bit length codes.
 134    static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
 35
 136    static readonly byte[] bit4Reverse = {
 137      0,
 138      8,
 139      4,
 140      12,
 141      2,
 142      10,
 143      6,
 144      14,
 145      1,
 146      9,
 147      5,
 148      13,
 149      3,
 150      11,
 151      7,
 152      15
 153    };
 54
 55    static short[] staticLCodes;
 56    static byte[] staticLLength;
 57    static short[] staticDCodes;
 58    static byte[] staticDLength;
 59
 60    class Tree
 61    {
 62      #region Instance Fields
 63      public short[] freqs;
 64
 65      public byte[] length;
 66
 67      public int minNumCodes;
 68
 69      public int numCodes;
 70
 71      short[] codes;
 72      readonly int[] bl_counts;
 73      readonly int maxLength;
 74      DeflaterHuffman dh;
 75      #endregion
 76
 77      #region Constructors
 81978      public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
 79      {
 81980        this.dh = dh;
 81981        this.minNumCodes = minCodes;
 81982        this.maxLength = maxLength;
 81983        freqs = new short[elems];
 81984        bl_counts = new int[maxLength];
 81985      }
 86
 87      #endregion
 88
 89      /// <summary>
 90      /// Resets the internal state of the tree
 91      /// </summary>
 92      public void Reset()
 93      {
 62394894         for (int i = 0; i < freqs.Length; i++) {
 30920595          freqs[i] = 0;
 96        }
 276997        codes = null;
 276998        length = null;
 276999      }
 100
 101      public void WriteSymbol(int code)
 102      {
 103        //        if (DeflaterConstants.DEBUGGING) {
 104        //          freqs[code]--;
 105        //          //      Console.Write("writeSymbol("+freqs.length+","+code+"): ");
 106        //        }
 8298107        dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
 8298108      }
 109
 110      /// <summary>
 111      /// Check that all frequencies are zero
 112      /// </summary>
 113      /// <exception cref="SharpZipBaseException">
 114      /// At least one frequency is non-zero
 115      /// </exception>
 116      public void CheckEmpty()
 117      {
 0118        bool empty = true;
 0119         for (int i = 0; i < freqs.Length; i++) {
 0120          empty &= freqs[i] == 0;
 121        }
 122
 0123         if (!empty) {
 0124          throw new SharpZipBaseException("!Empty");
 125        }
 0126      }
 127
 128      /// <summary>
 129      /// Set static codes and length
 130      /// </summary>
 131      /// <param name="staticCodes">new codes</param>
 132      /// <param name="staticLengths">length for new codes</param>
 133      public void SetStaticCodes(short[] staticCodes, byte[] staticLengths)
 134      {
 474135        codes = staticCodes;
 474136        length = staticLengths;
 474137      }
 138
 139      /// <summary>
 140      /// Build dynamic codes and lengths
 141      /// </summary>
 142      public void BuildCodes()
 143      {
 3144        int numSymbols = freqs.Length;
 3145        int[] nextCode = new int[maxLength];
 3146        int code = 0;
 147
 3148        codes = new short[freqs.Length];
 149
 150        //        if (DeflaterConstants.DEBUGGING) {
 151        //          //Console.WriteLine("buildCodes: "+freqs.Length);
 152        //        }
 153
 80154         for (int bits = 0; bits < maxLength; bits++) {
 37155          nextCode[bits] = code;
 37156          code += bl_counts[bits] << (15 - bits);
 157
 158          //          if (DeflaterConstants.DEBUGGING) {
 159          //            //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
 160          //                              +" nextCode: "+code);
 161          //          }
 162        }
 163
 164#if DebugDeflation
 165        if ( DeflaterConstants.DEBUGGING && (code != 65536) )
 166        {
 167          throw new SharpZipBaseException("Inconsistent bl_counts!");
 168        }
 169#endif
 576170         for (int i = 0; i < numCodes; i++) {
 285171          int bits = length[i];
 285172           if (bits > 0) {
 173
 174            //            if (DeflaterConstants.DEBUGGING) {
 175            //                //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
 176            //                                  +bits);
 177            //            }
 178
 38179            codes[i] = BitReverse(nextCode[bits - 1]);
 38180            nextCode[bits - 1] += 1 << (16 - bits);
 181          }
 182        }
 3183      }
 184
 185      public void BuildTree()
 186      {
 1530187        int numSymbols = freqs.Length;
 188
 189        /* heap is a priority queue, sorted by frequency, least frequent
 190        * nodes first.  The heap is a binary tree, with the property, that
 191        * the parent node is smaller than both child nodes.  This assures
 192        * that the smallest node is the first parent.
 193        *
 194        * The binary tree is encoded in an array:  0 is root node and
 195        * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
 196        */
 1530197        int[] heap = new int[numSymbols];
 1530198        int heapLen = 0;
 1530199        int maxCode = 0;
 344760200         for (int n = 0; n < numSymbols; n++) {
 170850201          int freq = freqs[n];
 170850202           if (freq != 0) {
 203            // Insert n into heap
 81797204            int pos = heapLen++;
 205            int ppos;
 161994206             while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
 80197207              heap[pos] = heap[ppos];
 80197208              pos = ppos;
 209            }
 81797210            heap[pos] = n;
 211
 81797212            maxCode = n;
 213          }
 214        }
 215
 216        /* We could encode a single literal with 0 bits but then we
 217        * don't see the literals.  Therefore we force at least two
 218        * literals to avoid this case.  We don't care about order in
 219        * this case, both literals get a 1 bit code.
 220        */
 2077221         while (heapLen < 2) {
 547222           int node = maxCode < 2 ? ++maxCode : 0;
 547223          heap[heapLen++] = node;
 224        }
 225
 1530226        numCodes = Math.Max(maxCode + 1, minNumCodes);
 227
 1530228        int numLeafs = heapLen;
 1530229        int[] childs = new int[4 * heapLen - 2];
 1530230        int[] values = new int[2 * heapLen - 1];
 1530231        int numNodes = numLeafs;
 167748232         for (int i = 0; i < heapLen; i++) {
 82344233          int node = heap[i];
 82344234          childs[2 * i] = node;
 82344235          childs[2 * i + 1] = -1;
 82344236          values[i] = freqs[node] << 8;
 82344237          heap[i] = i;
 238        }
 239
 240        /* Construct the Huffman tree by repeatedly combining the least two
 241        * frequent nodes.
 242        */
 243        do {
 80814244          int first = heap[0];
 80814245          int last = heap[--heapLen];
 246
 247          // Propagate the hole to the leafs of the heap
 80814248          int ppos = 0;
 80814249          int path = 1;
 250
 507013251           while (path < heapLen) {
 426199252             if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) {
 191359253              path++;
 254            }
 255
 426199256            heap[ppos] = heap[path];
 426199257            ppos = path;
 426199258            path = path * 2 + 1;
 259          }
 260
 261          /* Now propagate the last element down along path.  Normally
 262          * it shouldn't go too deep.
 263          */
 80814264          int lastVal = values[last];
 103741265           while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) {
 22927266            heap[path] = heap[ppos];
 267          }
 80814268          heap[path] = last;
 269
 270
 80814271          int second = heap[0];
 272
 273          // Create a new node father of first and second
 80814274          last = numNodes++;
 80814275          childs[2 * last] = first;
 80814276          childs[2 * last + 1] = second;
 80814277          int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
 80814278          values[last] = lastVal = values[first] + values[second] - mindepth + 1;
 279
 280          // Again, propagate the hole to the leafs
 80814281          ppos = 0;
 80814282          path = 1;
 283
 507819284           while (path < heapLen) {
 427005285             if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) {
 193052286              path++;
 287            }
 288
 427005289            heap[ppos] = heap[path];
 427005290            ppos = path;
 427005291            path = ppos * 2 + 1;
 292          }
 293
 294          // Now propagate the new element down along path
 86039295           while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) {
 5225296            heap[path] = heap[ppos];
 297          }
 80814298          heap[path] = last;
 80814299         } while (heapLen > 1);
 300
 1530301         if (heap[0] != childs.Length / 2 - 1) {
 0302          throw new SharpZipBaseException("Heap invariant violated");
 303        }
 304
 1530305        BuildLength(childs);
 1530306      }
 307
 308      /// <summary>
 309      /// Get encoded length
 310      /// </summary>
 311      /// <returns>Encoded length, the sum of frequencies * lengths</returns>
 312      public int GetEncodedLength()
 313      {
 1530314        int len = 0;
 344760315         for (int i = 0; i < freqs.Length; i++) {
 170850316          len += freqs[i] * length[i];
 317        }
 1530318        return len;
 319      }
 320
 321      /// <summary>
 322      /// Scan a literal or distance tree to determine the frequencies of the codes
 323      /// in the bit length tree.
 324      /// </summary>
 325      public void CalcBLFreq(Tree blTree)
 326      {
 327        int max_count;               /* max repeat count */
 328        int min_count;               /* min repeat count */
 329        int count;                   /* repeat count of the current code */
 1020330        int curlen = -1;             /* length of current code */
 331
 1020332        int i = 0;
 26206333         while (i < numCodes) {
 25186334          count = 1;
 25186335          int nextlen = length[i];
 25186336           if (nextlen == 0) {
 2966337            max_count = 138;
 2966338            min_count = 3;
 2966339          } else {
 22220340            max_count = 6;
 22220341            min_count = 3;
 22220342             if (curlen != nextlen) {
 12628343              blTree.freqs[nextlen]++;
 12628344              count = 0;
 345            }
 346          }
 25186347          curlen = nextlen;
 25186348          i++;
 349
 129433350           while (i < numCodes && curlen == length[i]) {
 114222351            i++;
 114222352             if (++count >= max_count) {
 353              break;
 354            }
 355          }
 356
 25186357           if (count < min_count) {
 13100358            blTree.freqs[curlen] += (short)count;
 25186359           } else if (curlen != 0) {
 10711360            blTree.freqs[REP_3_6]++;
 12086361           } else if (count <= 10) {
 319362            blTree.freqs[REP_3_10]++;
 319363          } else {
 1056364            blTree.freqs[REP_11_138]++;
 365          }
 366        }
 1020367      }
 368
 369      /// <summary>
 370      /// Write tree values
 371      /// </summary>
 372      /// <param name="blTree">Tree to write</param>
 373      public void WriteTree(Tree blTree)
 374      {
 375        int max_count;               // max repeat count
 376        int min_count;               // min repeat count
 377        int count;                   // repeat count of the current code
 2378        int curlen = -1;             // length of current code
 379
 2380        int i = 0;
 42381         while (i < numCodes) {
 40382          count = 1;
 40383          int nextlen = length[i];
 40384           if (nextlen == 0) {
 14385            max_count = 138;
 14386            min_count = 3;
 14387          } else {
 26388            max_count = 6;
 26389            min_count = 3;
 26390             if (curlen != nextlen) {
 26391              blTree.WriteSymbol(nextlen);
 26392              count = 0;
 393            }
 394          }
 40395          curlen = nextlen;
 40396          i++;
 397
 266398           while (i < numCodes && curlen == length[i]) {
 226399            i++;
 226400             if (++count >= max_count) {
 401              break;
 402            }
 403          }
 404
 40405           if (count < min_count) {
 41406             while (count-- > 0) {
 10407              blTree.WriteSymbol(curlen);
 408            }
 40409           } else if (curlen != 0) {
 0410            blTree.WriteSymbol(REP_3_6);
 0411            dh.pending.WriteBits(count - 3, 2);
 9412           } else if (count <= 10) {
 4413            blTree.WriteSymbol(REP_3_10);
 4414            dh.pending.WriteBits(count - 3, 3);
 4415          } else {
 5416            blTree.WriteSymbol(REP_11_138);
 5417            dh.pending.WriteBits(count - 11, 7);
 418          }
 419        }
 2420      }
 421
 422      void BuildLength(int[] childs)
 423      {
 1530424        this.length = new byte[freqs.Length];
 1530425        int numNodes = childs.Length / 2;
 1530426        int numLeafs = (numNodes + 1) / 2;
 1530427        int overflow = 0;
 428
 40800429         for (int i = 0; i < maxLength; i++) {
 18870430          bl_counts[i] = 0;
 431        }
 432
 433        // First calculate optimal bit lengths
 1530434        int[] lengths = new int[numNodes];
 1530435        lengths[numNodes - 1] = 0;
 436
 329376437         for (int i = numNodes - 1; i >= 0; i--) {
 163158438           if (childs[2 * i + 1] != -1) {
 80814439            int bitLength = lengths[i] + 1;
 80814440             if (bitLength > maxLength) {
 2441              bitLength = maxLength;
 2442              overflow++;
 443            }
 80814444            lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
 80814445          } else {
 446            // A leaf node
 82344447            int bitLength = lengths[i];
 82344448            bl_counts[bitLength - 1]++;
 82344449            this.length[childs[2 * i]] = (byte)lengths[i];
 450          }
 451        }
 452
 453        //        if (DeflaterConstants.DEBUGGING) {
 454        //          //Console.WriteLine("Tree "+freqs.Length+" lengths:");
 455        //          for (int i=0; i < numLeafs; i++) {
 456        //            //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 457        //                              + " len: "+length[childs[2*i]]);
 458        //          }
 459        //        }
 460
 1530461         if (overflow == 0) {
 1528462          return;
 463        }
 464
 2465        int incrBitLen = maxLength - 1;
 466        do {
 467          // Find the first bit length which could increase:
 2468           while (bl_counts[--incrBitLen] == 0) {
 469          }
 470
 471          // Move this node one down and remove a corresponding
 472          // number of overflow nodes.
 473          do {
 2474            bl_counts[incrBitLen]--;
 2475            bl_counts[++incrBitLen]++;
 2476            overflow -= 1 << (maxLength - 1 - incrBitLen);
 2477           } while (overflow > 0 && incrBitLen < maxLength - 1);
 2478         } while (overflow > 0);
 479
 480        /* We may have overshot above.  Move some nodes from maxLength to
 481        * maxLength-1 in that case.
 482        */
 2483        bl_counts[maxLength - 1] += overflow;
 2484        bl_counts[maxLength - 2] -= overflow;
 485
 486        /* Now recompute all bit lengths, scanning in increasing
 487        * frequency.  It is simpler to reconstruct all lengths instead of
 488        * fixing only the wrong ones. This idea is taken from 'ar'
 489        * written by Haruhiko Okumura.
 490        *
 491        * The nodes were inserted with decreasing frequency into the childs
 492        * array.
 493        */
 2494        int nodePtr = 2 * numLeafs;
 32495         for (int bits = maxLength; bits != 0; bits--) {
 14496          int n = bl_counts[bits - 1];
 44497           while (n > 0) {
 30498            int childPtr = 2 * childs[nodePtr++];
 30499             if (childs[childPtr + 1] == -1) {
 500              // We found another leaf
 18501              length[childs[childPtr]] = (byte)bits;
 18502              n--;
 503            }
 504          }
 505        }
 506        //        if (DeflaterConstants.DEBUGGING) {
 507        //          //Console.WriteLine("*** After overflow elimination. ***");
 508        //          for (int i=0; i < numLeafs; i++) {
 509        //            //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 510        //                              + " len: "+length[childs[2*i]]);
 511        //          }
 512        //        }
 2513      }
 514
 515    }
 516
 517    #region Instance Fields
 518    /// <summary>
 519    /// Pending buffer to use
 520    /// </summary>
 521    public DeflaterPending pending;
 522
 523    Tree literalTree;
 524    Tree distTree;
 525    Tree blTree;
 526
 527    // Buffer for distances
 528    short[] d_buf;
 529    byte[] l_buf;
 530    int last_lit;
 531    int extra_bits;
 532    #endregion
 533
 534    static DeflaterHuffman()
 535    {
 536      // See RFC 1951 3.2.6
 537      // Literal codes
 1538      staticLCodes = new short[LITERAL_NUM];
 1539      staticLLength = new byte[LITERAL_NUM];
 540
 1541      int i = 0;
 145542       while (i < 144) {
 144543        staticLCodes[i] = BitReverse((0x030 + i) << 8);
 144544        staticLLength[i++] = 8;
 545      }
 546
 113547       while (i < 256) {
 112548        staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
 112549        staticLLength[i++] = 9;
 550      }
 551
 25552       while (i < 280) {
 24553        staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
 24554        staticLLength[i++] = 7;
 555      }
 556
 7557       while (i < LITERAL_NUM) {
 6558        staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
 6559        staticLLength[i++] = 8;
 560      }
 561
 562      // Distance codes
 1563      staticDCodes = new short[DIST_NUM];
 1564      staticDLength = new byte[DIST_NUM];
 62565       for (i = 0; i < DIST_NUM; i++) {
 30566        staticDCodes[i] = BitReverse(i << 11);
 30567        staticDLength[i] = 5;
 568      }
 1569    }
 570
 571    /// <summary>
 572    /// Construct instance with pending buffer
 573    /// </summary>
 574    /// <param name="pending">Pending buffer to use</param>
 273575    public DeflaterHuffman(DeflaterPending pending)
 576    {
 273577      this.pending = pending;
 578
 273579      literalTree = new Tree(this, LITERAL_NUM, 257, 15);
 273580      distTree = new Tree(this, DIST_NUM, 1, 15);
 273581      blTree = new Tree(this, BITLEN_NUM, 4, 7);
 582
 273583      d_buf = new short[BUFSIZE];
 273584      l_buf = new byte[BUFSIZE];
 273585    }
 586
 587    /// <summary>
 588    /// Reset internal state
 589    /// </summary>
 590    public void Reset()
 591    {
 923592      last_lit = 0;
 923593      extra_bits = 0;
 923594      literalTree.Reset();
 923595      distTree.Reset();
 923596      blTree.Reset();
 923597    }
 598
 599    /// <summary>
 600    /// Write all trees to pending buffer
 601    /// </summary>
 602    /// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
 603    public void SendAllTrees(int blTreeCodes)
 604    {
 1605      blTree.BuildCodes();
 1606      literalTree.BuildCodes();
 1607      distTree.BuildCodes();
 1608      pending.WriteBits(literalTree.numCodes - 257, 5);
 1609      pending.WriteBits(distTree.numCodes - 1, 5);
 1610      pending.WriteBits(blTreeCodes - 4, 4);
 38611       for (int rank = 0; rank < blTreeCodes; rank++) {
 18612        pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
 613      }
 1614      literalTree.WriteTree(blTree);
 1615      distTree.WriteTree(blTree);
 616
 617#if DebugDeflation
 618      if (DeflaterConstants.DEBUGGING) {
 619        blTree.CheckEmpty();
 620      }
 621#endif
 1622    }
 623
 624    /// <summary>
 625    /// Compress current buffer writing data to pending buffer
 626    /// </summary>
 627    public void CompressBlock()
 628    {
 16324629       for (int i = 0; i < last_lit; i++) {
 7924630        int litlen = l_buf[i] & 0xff;
 7924631        int dist = d_buf[i];
 7924632         if (dist-- != 0) {
 633          //          if (DeflaterConstants.DEBUGGING) {
 634          //            Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
 635          //          }
 636
 91637          int lc = Lcode(litlen);
 91638          literalTree.WriteSymbol(lc);
 639
 91640          int bits = (lc - 261) / 4;
 91641           if (bits > 0 && bits <= 5) {
 25642            pending.WriteBits(litlen & ((1 << bits) - 1), bits);
 643          }
 644
 91645          int dc = Dcode(dist);
 91646          distTree.WriteSymbol(dc);
 647
 91648          bits = dc / 2 - 1;
 91649           if (bits > 0) {
 70650            pending.WriteBits(dist & ((1 << bits) - 1), bits);
 651          }
 70652        } else {
 653          //          if (DeflaterConstants.DEBUGGING) {
 654          //            if (litlen > 32 && litlen < 127) {
 655          //              Console.Write("("+(char)litlen+"): ");
 656          //            } else {
 657          //              Console.Write("{"+litlen+"}: ");
 658          //            }
 659          //          }
 7833660          literalTree.WriteSymbol(litlen);
 661        }
 662      }
 663
 664#if DebugDeflation
 665      if (DeflaterConstants.DEBUGGING) {
 666        Console.Write("EOF: ");
 667      }
 668#endif
 238669      literalTree.WriteSymbol(EOF_SYMBOL);
 670
 671#if DebugDeflation
 672      if (DeflaterConstants.DEBUGGING) {
 673        literalTree.CheckEmpty();
 674        distTree.CheckEmpty();
 675      }
 676#endif
 238677    }
 678
 679    /// <summary>
 680    /// Flush block to output with no compression
 681    /// </summary>
 682    /// <param name="stored">Data to write</param>
 683    /// <param name="storedOffset">Index of first byte to write</param>
 684    /// <param name="storedLength">Count of bytes to write</param>
 685    /// <param name="lastBlock">True if this is the last block</param>
 686    public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
 687    {
 688#if DebugDeflation
 689      //      if (DeflaterConstants.DEBUGGING) {
 690      //        //Console.WriteLine("Flushing stored block "+ storedLength);
 691      //      }
 692#endif
 293693       pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
 293694      pending.AlignToByte();
 293695      pending.WriteShort(storedLength);
 293696      pending.WriteShort(~storedLength);
 293697      pending.WriteBlock(stored, storedOffset, storedLength);
 293698      Reset();
 293699    }
 700
 701    /// <summary>
 702    /// Flush block to output with compression
 703    /// </summary>
 704    /// <param name="stored">Data to flush</param>
 705    /// <param name="storedOffset">Index of first byte to flush</param>
 706    /// <param name="storedLength">Count of bytes to flush</param>
 707    /// <param name="lastBlock">True if this is the last block</param>
 708    public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
 709    {
 510710      literalTree.freqs[EOF_SYMBOL]++;
 711
 712      // Build trees
 510713      literalTree.BuildTree();
 510714      distTree.BuildTree();
 715
 716      // Calculate bitlen frequency
 510717      literalTree.CalcBLFreq(blTree);
 510718      distTree.CalcBLFreq(blTree);
 719
 720      // Build bitlen tree
 510721      blTree.BuildTree();
 722
 510723      int blTreeCodes = 4;
 3556724       for (int i = 18; i > blTreeCodes; i--) {
 1268725         if (blTree.length[BL_ORDER[i]] > 0) {
 510726          blTreeCodes = i + 1;
 727        }
 728      }
 510729      int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
 510730        literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
 510731        extra_bits;
 732
 510733      int static_len = extra_bits;
 292740734       for (int i = 0; i < LITERAL_NUM; i++) {
 145860735        static_len += literalTree.freqs[i] * staticLLength[i];
 736      }
 31620737       for (int i = 0; i < DIST_NUM; i++) {
 15300738        static_len += distTree.freqs[i] * staticDLength[i];
 739      }
 510740       if (opt_len >= static_len) {
 741        // Force static trees
 270742        opt_len = static_len;
 743      }
 744
 510745       if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
 746        // Store Block
 747
 748        //        if (DeflaterConstants.DEBUGGING) {
 749        //          //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
 750        //                            + " <= " + static_len);
 751        //        }
 272752        FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
 510753       } else if (opt_len == static_len) {
 754        // Encode with static tree
 237755         pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
 237756        literalTree.SetStaticCodes(staticLCodes, staticLLength);
 237757        distTree.SetStaticCodes(staticDCodes, staticDLength);
 237758        CompressBlock();
 237759        Reset();
 237760      } else {
 761        // Encode with dynamic tree
 1762         pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
 1763        SendAllTrees(blTreeCodes);
 1764        CompressBlock();
 1765        Reset();
 766      }
 1767    }
 768
 769    /// <summary>
 770    /// Get value indicating if internal buffer is full
 771    /// </summary>
 772    /// <returns>true if buffer is full</returns>
 773    public bool IsFull()
 774    {
 7208362775      return last_lit >= BUFSIZE;
 776    }
 777
 778    /// <summary>
 779    /// Add literal to buffer
 780    /// </summary>
 781    /// <param name="literal">Literal value to add to buffer.</param>
 782    /// <returns>Value indicating internal buffer is full</returns>
 783    public bool TallyLit(int literal)
 784    {
 785      //      if (DeflaterConstants.DEBUGGING) {
 786      //        if (lit > 32 && lit < 127) {
 787      //          //Console.WriteLine("("+(char)lit+")");
 788      //        } else {
 789      //          //Console.WriteLine("{"+lit+"}");
 790      //        }
 791      //      }
 3602142792      d_buf[last_lit] = 0;
 3602142793      l_buf[last_lit++] = (byte)literal;
 3602142794      literalTree.freqs[literal]++;
 3602142795      return IsFull();
 796    }
 797
 798    /// <summary>
 799    /// Add distance code and length to literal and distance trees
 800    /// </summary>
 801    /// <param name="distance">Distance code</param>
 802    /// <param name="length">Length</param>
 803    /// <returns>Value indicating if internal buffer is full</returns>
 804    public bool TallyDist(int distance, int length)
 805    {
 806      //      if (DeflaterConstants.DEBUGGING) {
 807      //        //Console.WriteLine("[" + distance + "," + length + "]");
 808      //      }
 809
 2828810      d_buf[last_lit] = (short)distance;
 2828811      l_buf[last_lit++] = (byte)(length - 3);
 812
 2828813      int lc = Lcode(length - 3);
 2828814      literalTree.freqs[lc]++;
 2828815       if (lc >= 265 && lc < 285) {
 25816        extra_bits += (lc - 261) / 4;
 817      }
 818
 2828819      int dc = Dcode(distance - 1);
 2828820      distTree.freqs[dc]++;
 2828821       if (dc >= 4) {
 2807822        extra_bits += dc / 2 - 1;
 823      }
 2828824      return IsFull();
 825    }
 826
 827
 828    /// <summary>
 829    /// Reverse the bits of a 16 bit value.
 830    /// </summary>
 831    /// <param name="toReverse">Value to reverse bits</param>
 832    /// <returns>Value with bits reversed</returns>
 833    public static short BitReverse(int toReverse)
 834    {
 712835      return (short)(bit4Reverse[toReverse & 0xF] << 12 |
 712836              bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
 712837              bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
 712838              bit4Reverse[toReverse >> 12]);
 839    }
 840
 841    static int Lcode(int length)
 842    {
 2919843       if (length == 255) {
 82844        return 285;
 845      }
 846
 2837847      int code = 257;
 3067848       while (length >= 8) {
 230849        code += 4;
 230850        length >>= 1;
 851      }
 2837852      return code + length;
 853    }
 854
 855    static int Dcode(int distance)
 856    {
 2919857      int code = 0;
 34328858       while (distance >= 4) {
 31409859        code += 2;
 31409860        distance >>= 1;
 861      }
 2919862      return code + distance;
 863    }
 864  }
 865}