Summary

Class:ICSharpCode.SharpZipLib.BZip2.BZip2OutputStream
Assembly:ICSharpCode.SharpZipLib
File(s):C:\Users\Neil\Documents\Visual Studio 2015\Projects\icsharpcode\SZL_master\ICSharpCode.SharpZipLib\BZip2\BZip2OutputStream.cs
Covered lines:107
Uncovered lines:794
Coverable lines:901
Total lines:1793
Line coverage:11.8%
Branch coverage:3.6%

Metrics

MethodCyclomatic ComplexitySequence CoverageBranch Coverage
.ctor(...)1100100
.ctor(...)390.9160
Finalize()100
Seek(...)100
SetLength(...)100
ReadByte()100
Read(...)100
Write(...)600
WriteByte(...)400
Close()1100100
MakeMaps()300
WriteRun()700
Dispose(...)593.3355.56
Flush()1100100
Initialize()1100100
InitBlock()2100100
EndBlock()31040
EndCompression()1100100
BsSetStream(...)1100100
BsFinishedWithStream()2100100
BsW(...)2100100
BsPutUChar(...)1100100
BsPutint(...)1100100
BsPutIntVS(...)100
SendMTFValues()6700
MoveToFrontCodeAndSend()100
SimpleSort(...)1500
Vswap(...)200
QSort3(...)1700
MainSort()3200
RandomiseBlock()700
DoReversibleTransformation()600
FullGtU(...)1800
AllocateCompressStructures()410057.14
GenerateMTFValues()1400
Panic()100
HbMakeCodeLengths(...)2300
HbAssignCodes(...)400
Med3(...)400

File(s)

C:\Users\Neil\Documents\Visual Studio 2015\Projects\icsharpcode\SZL_master\ICSharpCode.SharpZipLib\BZip2\BZip2OutputStream.cs

#LineLine coverage
 1using System;
 2using System.IO;
 3using ICSharpCode.SharpZipLib.Checksum;
 4
 5namespace ICSharpCode.SharpZipLib.BZip2
 6{
 7  /// <summary>
 8  /// An output stream that compresses into the BZip2 format
 9  /// including file header chars into another stream.
 10  /// </summary>
 11  public class BZip2OutputStream : Stream
 12  {
 13    #region Constants
 14    const int SETMASK = (1 << 21);
 15    const int CLEARMASK = (~SETMASK);
 16    const int GREATER_ICOST = 15;
 17    const int LESSER_ICOST = 0;
 18    const int SMALL_THRESH = 20;
 19    const int DEPTH_THRESH = 10;
 20
 21    /*--
 22    If you are ever unlucky/improbable enough
 23    to get a stack overflow whilst sorting,
 24    increase the following constant and try
 25    again.  In practice I have never seen the
 26    stack go above 27 elems, so the following
 27    limit seems very generous.
 28    --*/
 29    const int QSORT_STACK_SIZE = 1000;
 30
 31    /*--
 32    Knuth's increments seem to work better
 33    than Incerpi-Sedgewick here.  Possibly
 34    because the number of elems to sort is
 35    usually small, typically <= 20.
 36    --*/
 137    readonly int[] increments = {
 138                          1, 4, 13, 40, 121, 364, 1093, 3280,
 139                          9841, 29524, 88573, 265720,
 140                          797161, 2391484
 141                        };
 42    #endregion
 43
 44    #region Constructors
 45    /// <summary>
 46    /// Construct a default output stream with maximum block size
 47    /// </summary>
 48    /// <param name="stream">The stream to write BZip data onto.</param>
 149    public BZip2OutputStream(Stream stream) : this(stream, 9)
 50    {
 151    }
 52
 53    /// <summary>
 54    /// Initialise a new instance of the <see cref="BZip2OutputStream"></see>
 55    /// for the specified stream, using the given blocksize.
 56    /// </summary>
 57    /// <param name="stream">The stream to write compressed data to.</param>
 58    /// <param name="blockSize">The block size to use.</param>
 59    /// <remarks>
 60    /// Valid block sizes are in the range 1..9, with 1 giving
 61    /// the lowest compression and 9 the highest.
 62    /// </remarks>
 163    public BZip2OutputStream(Stream stream, int blockSize)
 64    {
 165      BsSetStream(stream);
 66
 167      workFactor = 50;
 168       if (blockSize > 9) {
 069        blockSize = 9;
 70      }
 71
 172       if (blockSize < 1) {
 073        blockSize = 1;
 74      }
 175      blockSize100k = blockSize;
 176      AllocateCompressStructures();
 177      Initialize();
 178      InitBlock();
 179    }
 80    #endregion
 81
 82    #region Destructor
 83    /// <summary>
 84    /// Ensures that resources are freed and other cleanup operations
 85    /// are performed when the garbage collector reclaims the BZip2OutputStream.
 86    /// </summary>
 87    ~BZip2OutputStream()
 88    {
 089      Dispose(false);
 090    }
 91    #endregion
 92
 93    /// <summary>
 94    /// Get/set flag indicating ownership of underlying stream.
 95    /// When the flag is true <see cref="Close"></see> will close the underlying stream also.
 96    /// </summary>
 97    public bool IsStreamOwner {
 198      get { return isStreamOwner; }
 099      set { isStreamOwner = value; }
 100    }
 101
 102
 103    #region Stream overrides
 104    /// <summary>
 105    /// Gets a value indicating whether the current stream supports reading
 106    /// </summary>
 107    public override bool CanRead {
 108      get {
 0109        return false;
 110      }
 111    }
 112
 113    /// <summary>
 114    /// Gets a value indicating whether the current stream supports seeking
 115    /// </summary>
 116    public override bool CanSeek {
 117      get {
 0118        return false;
 119      }
 120    }
 121
 122    /// <summary>
 123    /// Gets a value indicating whether the current stream supports writing
 124    /// </summary>
 125    public override bool CanWrite {
 126      get {
 0127        return baseStream.CanWrite;
 128      }
 129    }
 130
 131    /// <summary>
 132    /// Gets the length in bytes of the stream
 133    /// </summary>
 134    public override long Length {
 135      get {
 0136        return baseStream.Length;
 137      }
 138    }
 139
 140    /// <summary>
 141    /// Gets or sets the current position of this stream.
 142    /// </summary>
 143    public override long Position {
 144      get {
 0145        return baseStream.Position;
 146      }
 147      set {
 0148        throw new NotSupportedException("BZip2OutputStream position cannot be set");
 149      }
 150    }
 151
 152    /// <summary>
 153    /// Sets the current position of this stream to the given value.
 154    /// </summary>
 155    /// <param name="offset">The point relative to the offset from which to being seeking.</param>
 156    /// <param name="origin">The reference point from which to begin seeking.</param>
 157    /// <returns>The new position in the stream.</returns>
 158    public override long Seek(long offset, SeekOrigin origin)
 159    {
 0160      throw new NotSupportedException("BZip2OutputStream Seek not supported");
 161    }
 162
 163    /// <summary>
 164    /// Sets the length of this stream to the given value.
 165    /// </summary>
 166    /// <param name="value">The new stream length.</param>
 167    public override void SetLength(long value)
 168    {
 0169      throw new NotSupportedException("BZip2OutputStream SetLength not supported");
 170    }
 171
 172    /// <summary>
 173    /// Read a byte from the stream advancing the position.
 174    /// </summary>
 175    /// <returns>The byte read cast to an int; -1 if end of stream.</returns>
 176    public override int ReadByte()
 177    {
 0178      throw new NotSupportedException("BZip2OutputStream ReadByte not supported");
 179    }
 180
 181    /// <summary>
 182    /// Read a block of bytes
 183    /// </summary>
 184    /// <param name="buffer">The buffer to read into.</param>
 185    /// <param name="offset">The offset in the buffer to start storing data at.</param>
 186    /// <param name="count">The maximum number of bytes to read.</param>
 187    /// <returns>The total number of bytes read. This might be less than the number of bytes
 188    /// requested if that number of bytes are not currently available, or zero
 189    /// if the end of the stream is reached.</returns>
 190    public override int Read(byte[] buffer, int offset, int count)
 191    {
 0192      throw new NotSupportedException("BZip2OutputStream Read not supported");
 193    }
 194
 195    /// <summary>
 196    /// Write a block of bytes to the stream
 197    /// </summary>
 198    /// <param name="buffer">The buffer containing data to write.</param>
 199    /// <param name="offset">The offset of the first byte to write.</param>
 200    /// <param name="count">The number of bytes to write.</param>
 201    public override void Write(byte[] buffer, int offset, int count)
 202    {
 0203       if (buffer == null) {
 0204        throw new ArgumentNullException(nameof(buffer));
 205      }
 206
 0207       if (offset < 0) {
 0208        throw new ArgumentOutOfRangeException(nameof(offset));
 209      }
 210
 0211       if (count < 0) {
 0212        throw new ArgumentOutOfRangeException(nameof(count));
 213      }
 214
 0215       if (buffer.Length - offset < count) {
 0216        throw new ArgumentException("Offset/count out of range");
 217      }
 218
 0219       for (int i = 0; i < count; ++i) {
 0220        WriteByte(buffer[offset + i]);
 221      }
 0222    }
 223
 224    /// <summary>
 225    /// Write a byte to the stream.
 226    /// </summary>
 227    /// <param name="value">The byte to write to the stream.</param>
 228    public override void WriteByte(byte value)
 229    {
 0230      int b = (256 + value) % 256;
 0231       if (currentChar != -1) {
 0232         if (currentChar == b) {
 0233          runLength++;
 0234           if (runLength > 254) {
 0235            WriteRun();
 0236            currentChar = -1;
 0237            runLength = 0;
 238          }
 0239        } else {
 0240          WriteRun();
 0241          runLength = 1;
 0242          currentChar = b;
 243        }
 0244      } else {
 0245        currentChar = b;
 0246        runLength++;
 247      }
 0248    }
 249
 250    /// <summary>
 251    /// End the current block and end compression.
 252    /// Close the stream and free any resources
 253    /// </summary>
 254    public override void Close()
 255    {
 1256      Dispose(true);
 1257      GC.SuppressFinalize(this);
 1258    }
 259
 260    #endregion
 261    void MakeMaps()
 262    {
 0263      nInUse = 0;
 0264       for (int i = 0; i < 256; i++) {
 0265         if (inUse[i]) {
 0266          seqToUnseq[nInUse] = (char)i;
 0267          unseqToSeq[i] = (char)nInUse;
 0268          nInUse++;
 269        }
 270      }
 0271    }
 272
 273    /// <summary>
 274    /// Get the number of bytes written to output.
 275    /// </summary>
 276    void WriteRun()
 277    {
 0278       if (last < allowableBlockSize) {
 0279        inUse[currentChar] = true;
 0280         for (int i = 0; i < runLength; i++) {
 0281          mCrc.Update(currentChar);
 282        }
 283
 0284         switch (runLength) {
 285          case 1:
 0286            last++;
 0287            block[last + 1] = (byte)currentChar;
 0288            break;
 289          case 2:
 0290            last++;
 0291            block[last + 1] = (byte)currentChar;
 0292            last++;
 0293            block[last + 1] = (byte)currentChar;
 0294            break;
 295          case 3:
 0296            last++;
 0297            block[last + 1] = (byte)currentChar;
 0298            last++;
 0299            block[last + 1] = (byte)currentChar;
 0300            last++;
 0301            block[last + 1] = (byte)currentChar;
 0302            break;
 303          default:
 0304            inUse[runLength - 4] = true;
 0305            last++;
 0306            block[last + 1] = (byte)currentChar;
 0307            last++;
 0308            block[last + 1] = (byte)currentChar;
 0309            last++;
 0310            block[last + 1] = (byte)currentChar;
 0311            last++;
 0312            block[last + 1] = (byte)currentChar;
 0313            last++;
 0314            block[last + 1] = (byte)(runLength - 4);
 0315            break;
 316        }
 317      } else {
 0318        EndBlock();
 0319        InitBlock();
 0320        WriteRun();
 321      }
 0322    }
 323
 324    /// <summary>
 325    /// Get the number of bytes written to the output.
 326    /// </summary>
 327    public int BytesWritten {
 0328      get { return bytesOut; }
 329    }
 330
 331    /// <summary>
 332    /// Releases the unmanaged resources used by the <see cref="BZip2OutputStream"/> and optionally releases the managed
 333    /// </summary>
 334    /// <param name="disposing">true to release both managed and unmanaged resources; false to release only unmanaged re
 335    override protected void Dispose(bool disposing)
 336    {
 337      try {
 1338        base.Dispose(disposing);
 1339         if (!disposed_) {
 1340          disposed_ = true;
 341
 1342           if (runLength > 0) {
 0343            WriteRun();
 344          }
 345
 1346          currentChar = -1;
 1347          EndBlock();
 1348          EndCompression();
 1349          Flush();
 350        }
 1351      } finally {
 1352         if (disposing) {
 1353           if (IsStreamOwner) {
 1354            baseStream.Close();
 355          }
 356        }
 1357      }
 1358    }
 359
 360    /// <summary>
 361    /// Flush output buffers
 362    /// </summary>
 363    public override void Flush()
 364    {
 1365      baseStream.Flush();
 1366    }
 367
 368    void Initialize()
 369    {
 1370      bytesOut = 0;
 1371      nBlocksRandomised = 0;
 372
 373      /*--- Write header `magic' bytes indicating file-format == huffmanised,
 374      followed by a digit indicating blockSize100k.
 375      ---*/
 376
 1377      BsPutUChar('B');
 1378      BsPutUChar('Z');
 379
 1380      BsPutUChar('h');
 1381      BsPutUChar('0' + blockSize100k);
 382
 1383      combinedCRC = 0;
 1384    }
 385
 386    void InitBlock()
 387    {
 1388      mCrc.Reset();
 1389      last = -1;
 390
 514391       for (int i = 0; i < 256; i++) {
 256392        inUse[i] = false;
 393      }
 394
 395      /*--- 20 is just a paranoia constant ---*/
 1396      allowableBlockSize = BZip2Constants.BaseBlockSize * blockSize100k - 20;
 1397    }
 398
 399    void EndBlock()
 400    {
 1401       if (last < 0) {       // dont do anything for empty files, (makes empty files compatible with original Bzip)
 1402        return;
 403      }
 404
 0405      blockCRC = unchecked((uint)mCrc.Value);
 0406      combinedCRC = (combinedCRC << 1) | (combinedCRC >> 31);
 0407      combinedCRC ^= blockCRC;
 408
 409      /*-- sort the block and establish position of original string --*/
 0410      DoReversibleTransformation();
 411
 412      /*--
 413      A 6-byte block header, the value chosen arbitrarily
 414      as 0x314159265359 :-).  A 32 bit value does not really
 415      give a strong enough guarantee that the value will not
 416      appear by chance in the compressed datastream.  Worst-case
 417      probability of this event, for a 900k block, is about
 418      2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
 419      For a compressed file of size 100Gb -- about 100000 blocks --
 420      only a 48-bit marker will do.  NB: normal compression/
 421      decompression do *not* rely on these statistical properties.
 422      They are only important when trying to recover blocks from
 423      damaged files.
 424      --*/
 0425      BsPutUChar(0x31);
 0426      BsPutUChar(0x41);
 0427      BsPutUChar(0x59);
 0428      BsPutUChar(0x26);
 0429      BsPutUChar(0x53);
 0430      BsPutUChar(0x59);
 431
 432      /*-- Now the block's CRC, so it is in a known place. --*/
 433      unchecked {
 0434        BsPutint((int)blockCRC);
 435      }
 436
 437      /*-- Now a single bit indicating randomisation. --*/
 0438       if (blockRandomised) {
 0439        BsW(1, 1);
 0440        nBlocksRandomised++;
 0441      } else {
 0442        BsW(1, 0);
 443      }
 444
 445      /*-- Finally, block's contents proper. --*/
 0446      MoveToFrontCodeAndSend();
 0447    }
 448
 449    void EndCompression()
 450    {
 451      /*--
 452      Now another magic 48-bit number, 0x177245385090, to
 453      indicate the end of the last block.  (sqrt(pi), if
 454      you want to know.  I did want to use e, but it contains
 455      too much repetition -- 27 18 28 18 28 46 -- for me
 456      to feel statistically comfortable.  Call me paranoid.)
 457      --*/
 1458      BsPutUChar(0x17);
 1459      BsPutUChar(0x72);
 1460      BsPutUChar(0x45);
 1461      BsPutUChar(0x38);
 1462      BsPutUChar(0x50);
 1463      BsPutUChar(0x90);
 464
 465      unchecked {
 1466        BsPutint((int)combinedCRC);
 467      }
 468
 1469      BsFinishedWithStream();
 1470    }
 471
 472    void BsSetStream(Stream stream)
 473    {
 1474      baseStream = stream;
 1475      bsLive = 0;
 1476      bsBuff = 0;
 1477      bytesOut = 0;
 1478    }
 479
 480    void BsFinishedWithStream()
 481    {
 2482       while (bsLive > 0) {
 1483        int ch = (bsBuff >> 24);
 1484        baseStream.WriteByte((byte)ch); // write 8-bit
 1485        bsBuff <<= 8;
 1486        bsLive -= 8;
 1487        bytesOut++;
 488      }
 1489    }
 490
 491    void BsW(int n, int v)
 492    {
 27493       while (bsLive >= 8) {
 13494        int ch = (bsBuff >> 24);
 13495        unchecked { baseStream.WriteByte((byte)ch); } // write 8-bit
 13496        bsBuff <<= 8;
 13497        bsLive -= 8;
 13498        ++bytesOut;
 499      }
 14500      bsBuff |= (v << (32 - bsLive - n));
 14501      bsLive += n;
 14502    }
 503
 504    void BsPutUChar(int c)
 505    {
 10506      BsW(8, c);
 10507    }
 508
 509    void BsPutint(int u)
 510    {
 1511      BsW(8, (u >> 24) & 0xFF);
 1512      BsW(8, (u >> 16) & 0xFF);
 1513      BsW(8, (u >> 8) & 0xFF);
 1514      BsW(8, u & 0xFF);
 1515    }
 516
 517    void BsPutIntVS(int numBits, int c)
 518    {
 0519      BsW(numBits, c);
 0520    }
 521
 522    void SendMTFValues()
 523    {
 0524      char[][] len = new char[BZip2Constants.GroupCount][];
 0525       for (int i = 0; i < BZip2Constants.GroupCount; ++i) {
 0526        len[i] = new char[BZip2Constants.MaximumAlphaSize];
 527      }
 528
 529      int gs, ge, totc, bt, bc, iter;
 0530      int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
 531      int nGroups;
 532
 0533      alphaSize = nInUse + 2;
 0534       for (int t = 0; t < BZip2Constants.GroupCount; t++) {
 0535         for (int v = 0; v < alphaSize; v++) {
 0536          len[t][v] = (char)GREATER_ICOST;
 537        }
 538      }
 539
 540      /*--- Decide how many coding tables to use ---*/
 0541       if (nMTF <= 0) {
 0542        Panic();
 543      }
 544
 0545       if (nMTF < 200) {
 0546        nGroups = 2;
 0547       } else if (nMTF < 600) {
 0548        nGroups = 3;
 0549       } else if (nMTF < 1200) {
 0550        nGroups = 4;
 0551       } else if (nMTF < 2400) {
 0552        nGroups = 5;
 0553      } else {
 0554        nGroups = 6;
 555      }
 556
 557      /*--- Generate an initial set of coding tables ---*/
 0558      int nPart = nGroups;
 0559      int remF = nMTF;
 0560      gs = 0;
 0561       while (nPart > 0) {
 0562        int tFreq = remF / nPart;
 0563        int aFreq = 0;
 0564        ge = gs - 1;
 0565         while (aFreq < tFreq && ge < alphaSize - 1) {
 0566          ge++;
 0567          aFreq += mtfFreq[ge];
 568        }
 569
 0570         if (ge > gs && nPart != nGroups && nPart != 1 && ((nGroups - nPart) % 2 == 1)) {
 0571          aFreq -= mtfFreq[ge];
 0572          ge--;
 573        }
 574
 0575         for (int v = 0; v < alphaSize; v++) {
 0576           if (v >= gs && v <= ge) {
 0577            len[nPart - 1][v] = (char)LESSER_ICOST;
 0578          } else {
 0579            len[nPart - 1][v] = (char)GREATER_ICOST;
 580          }
 581        }
 582
 0583        nPart--;
 0584        gs = ge + 1;
 0585        remF -= aFreq;
 586      }
 587
 0588      int[][] rfreq = new int[BZip2Constants.GroupCount][];
 0589       for (int i = 0; i < BZip2Constants.GroupCount; ++i) {
 0590        rfreq[i] = new int[BZip2Constants.MaximumAlphaSize];
 591      }
 592
 0593      int[] fave = new int[BZip2Constants.GroupCount];
 0594      short[] cost = new short[BZip2Constants.GroupCount];
 595      /*---
 596      Iterate up to N_ITERS times to improve the tables.
 597      ---*/
 0598       for (iter = 0; iter < BZip2Constants.NumberOfIterations; ++iter) {
 0599         for (int t = 0; t < nGroups; ++t) {
 0600          fave[t] = 0;
 601        }
 602
 0603         for (int t = 0; t < nGroups; ++t) {
 0604           for (int v = 0; v < alphaSize; ++v) {
 0605            rfreq[t][v] = 0;
 606          }
 607        }
 608
 0609        nSelectors = 0;
 0610        totc = 0;
 0611        gs = 0;
 0612        while (true) {
 613          /*--- Set group start & end marks. --*/
 0614           if (gs >= nMTF) {
 615            break;
 616          }
 0617          ge = gs + BZip2Constants.GroupSize - 1;
 0618           if (ge >= nMTF) {
 0619            ge = nMTF - 1;
 620          }
 621
 622          /*--
 623          Calculate the cost of this group as coded
 624          by each of the coding tables.
 625          --*/
 0626           for (int t = 0; t < nGroups; t++) {
 0627            cost[t] = 0;
 628          }
 629
 0630           if (nGroups == 6) {
 631            short cost0, cost1, cost2, cost3, cost4, cost5;
 0632            cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
 0633             for (int i = gs; i <= ge; ++i) {
 0634              short icv = szptr[i];
 0635              cost0 += (short)len[0][icv];
 0636              cost1 += (short)len[1][icv];
 0637              cost2 += (short)len[2][icv];
 0638              cost3 += (short)len[3][icv];
 0639              cost4 += (short)len[4][icv];
 0640              cost5 += (short)len[5][icv];
 641            }
 0642            cost[0] = cost0;
 0643            cost[1] = cost1;
 0644            cost[2] = cost2;
 0645            cost[3] = cost3;
 0646            cost[4] = cost4;
 0647            cost[5] = cost5;
 0648          } else {
 0649             for (int i = gs; i <= ge; ++i) {
 0650              short icv = szptr[i];
 0651               for (int t = 0; t < nGroups; t++) {
 0652                cost[t] += (short)len[t][icv];
 653              }
 654            }
 655          }
 656
 657          /*--
 658          Find the coding table which is best for this group,
 659          and record its identity in the selector table.
 660          --*/
 0661          bc = 999999999;
 0662          bt = -1;
 0663           for (int t = 0; t < nGroups; ++t) {
 0664             if (cost[t] < bc) {
 0665              bc = cost[t];
 0666              bt = t;
 667            }
 668          }
 0669          totc += bc;
 0670          fave[bt]++;
 0671          selector[nSelectors] = (char)bt;
 0672          nSelectors++;
 673
 674          /*--
 675          Increment the symbol frequencies for the selected table.
 676          --*/
 0677           for (int i = gs; i <= ge; ++i) {
 0678            ++rfreq[bt][szptr[i]];
 679          }
 680
 0681          gs = ge + 1;
 682        }
 683
 684        /*--
 685        Recompute the tables based on the accumulated frequencies.
 686        --*/
 0687         for (int t = 0; t < nGroups; ++t) {
 0688          HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
 689        }
 690      }
 691
 0692      rfreq = null;
 0693      fave = null;
 0694      cost = null;
 695
 0696       if (!(nGroups < 8)) {
 0697        Panic();
 698      }
 699
 0700       if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.GroupSize)))) {
 0701        Panic();
 702      }
 703
 704      /*--- Compute MTF values for the selectors. ---*/
 0705      char[] pos = new char[BZip2Constants.GroupCount];
 706      char ll_i, tmp2, tmp;
 707
 0708       for (int i = 0; i < nGroups; i++) {
 0709        pos[i] = (char)i;
 710      }
 711
 0712       for (int i = 0; i < nSelectors; i++) {
 0713        ll_i = selector[i];
 0714        int j = 0;
 0715        tmp = pos[j];
 0716         while (ll_i != tmp) {
 0717          j++;
 0718          tmp2 = tmp;
 0719          tmp = pos[j];
 0720          pos[j] = tmp2;
 721        }
 0722        pos[0] = tmp;
 0723        selectorMtf[i] = (char)j;
 724      }
 725
 0726      int[][] code = new int[BZip2Constants.GroupCount][];
 727
 0728       for (int i = 0; i < BZip2Constants.GroupCount; ++i) {
 0729        code[i] = new int[BZip2Constants.MaximumAlphaSize];
 730      }
 731
 732      /*--- Assign actual codes for the tables. --*/
 0733       for (int t = 0; t < nGroups; t++) {
 0734        minLen = 32;
 0735        maxLen = 0;
 0736         for (int i = 0; i < alphaSize; i++) {
 0737           if (len[t][i] > maxLen) {
 0738            maxLen = len[t][i];
 739          }
 0740           if (len[t][i] < minLen) {
 0741            minLen = len[t][i];
 742          }
 743        }
 0744         if (maxLen > 20) {
 0745          Panic();
 746        }
 0747         if (minLen < 1) {
 0748          Panic();
 749        }
 0750        HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
 751      }
 752
 753      /*--- Transmit the mapping table. ---*/
 0754      bool[] inUse16 = new bool[16];
 0755       for (int i = 0; i < 16; ++i) {
 0756        inUse16[i] = false;
 0757         for (int j = 0; j < 16; ++j) {
 0758           if (inUse[i * 16 + j]) {
 0759            inUse16[i] = true;
 760          }
 761        }
 762      }
 763
 0764       for (int i = 0; i < 16; ++i) {
 0765         if (inUse16[i]) {
 0766          BsW(1, 1);
 0767        } else {
 0768          BsW(1, 0);
 769        }
 770      }
 771
 0772       for (int i = 0; i < 16; ++i) {
 0773         if (inUse16[i]) {
 0774           for (int j = 0; j < 16; ++j) {
 0775             if (inUse[i * 16 + j]) {
 0776              BsW(1, 1);
 0777            } else {
 0778              BsW(1, 0);
 779            }
 780          }
 781        }
 782      }
 783
 784      /*--- Now the selectors. ---*/
 0785      BsW(3, nGroups);
 0786      BsW(15, nSelectors);
 0787       for (int i = 0; i < nSelectors; ++i) {
 0788         for (int j = 0; j < selectorMtf[i]; ++j) {
 0789          BsW(1, 1);
 790        }
 0791        BsW(1, 0);
 792      }
 793
 794      /*--- Now the coding tables. ---*/
 0795       for (int t = 0; t < nGroups; ++t) {
 0796        int curr = len[t][0];
 0797        BsW(5, curr);
 0798         for (int i = 0; i < alphaSize; ++i) {
 0799           while (curr < len[t][i]) {
 0800            BsW(2, 2);
 0801            curr++; /* 10 */
 802          }
 0803           while (curr > len[t][i]) {
 0804            BsW(2, 3);
 0805            curr--; /* 11 */
 806          }
 0807          BsW(1, 0);
 808        }
 809      }
 810
 811      /*--- And finally, the block data proper ---*/
 0812      selCtr = 0;
 0813      gs = 0;
 0814      while (true) {
 0815         if (gs >= nMTF) {
 816          break;
 817        }
 0818        ge = gs + BZip2Constants.GroupSize - 1;
 0819         if (ge >= nMTF) {
 0820          ge = nMTF - 1;
 821        }
 822
 0823         for (int i = gs; i <= ge; i++) {
 0824          BsW(len[selector[selCtr]][szptr[i]], code[selector[selCtr]][szptr[i]]);
 825        }
 826
 0827        gs = ge + 1;
 0828        ++selCtr;
 829      }
 0830       if (!(selCtr == nSelectors)) {
 0831        Panic();
 832      }
 0833    }
 834
 835    void MoveToFrontCodeAndSend()
 836    {
 0837      BsPutIntVS(24, origPtr);
 0838      GenerateMTFValues();
 0839      SendMTFValues();
 0840    }
 841
 842    void SimpleSort(int lo, int hi, int d)
 843    {
 844      int i, j, h, bigN, hp;
 845      int v;
 846
 0847      bigN = hi - lo + 1;
 0848       if (bigN < 2) {
 0849        return;
 850      }
 851
 0852      hp = 0;
 0853       while (increments[hp] < bigN) {
 0854        hp++;
 855      }
 0856      hp--;
 857
 0858       for (; hp >= 0; hp--) {
 0859        h = increments[hp];
 860
 0861        i = lo + h;
 862        while (true) {
 863          /*-- copy 1 --*/
 0864           if (i > hi)
 865            break;
 0866          v = zptr[i];
 0867          j = i;
 0868           while (FullGtU(zptr[j - h] + d, v + d)) {
 0869            zptr[j] = zptr[j - h];
 0870            j = j - h;
 0871             if (j <= (lo + h - 1))
 872              break;
 873          }
 0874          zptr[j] = v;
 0875          i++;
 876
 877          /*-- copy 2 --*/
 0878           if (i > hi) {
 879            break;
 880          }
 0881          v = zptr[i];
 0882          j = i;
 0883           while (FullGtU(zptr[j - h] + d, v + d)) {
 0884            zptr[j] = zptr[j - h];
 0885            j = j - h;
 0886             if (j <= (lo + h - 1)) {
 887              break;
 888            }
 889          }
 0890          zptr[j] = v;
 0891          i++;
 892
 893          /*-- copy 3 --*/
 0894           if (i > hi) {
 895            break;
 896          }
 0897          v = zptr[i];
 0898          j = i;
 0899           while (FullGtU(zptr[j - h] + d, v + d)) {
 0900            zptr[j] = zptr[j - h];
 0901            j = j - h;
 0902             if (j <= (lo + h - 1)) {
 903              break;
 904            }
 905          }
 0906          zptr[j] = v;
 0907          i++;
 908
 0909           if (workDone > workLimit && firstAttempt) {
 0910            return;
 911          }
 912        }
 913      }
 0914    }
 915
 916    void Vswap(int p1, int p2, int n)
 917    {
 0918      int temp = 0;
 0919       while (n > 0) {
 0920        temp = zptr[p1];
 0921        zptr[p1] = zptr[p2];
 0922        zptr[p2] = temp;
 0923        p1++;
 0924        p2++;
 0925        n--;
 926      }
 0927    }
 928
 929    void QSort3(int loSt, int hiSt, int dSt)
 930    {
 931      int unLo, unHi, ltLo, gtHi, med, n, m;
 932      int lo, hi, d;
 933
 0934      StackElement[] stack = new StackElement[QSORT_STACK_SIZE];
 935
 0936      int sp = 0;
 937
 0938      stack[sp].ll = loSt;
 0939      stack[sp].hh = hiSt;
 0940      stack[sp].dd = dSt;
 0941      sp++;
 942
 0943       while (sp > 0) {
 0944         if (sp >= QSORT_STACK_SIZE) {
 0945          Panic();
 946        }
 947
 0948        sp--;
 0949        lo = stack[sp].ll;
 0950        hi = stack[sp].hh;
 0951        d = stack[sp].dd;
 952
 0953         if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
 0954          SimpleSort(lo, hi, d);
 0955           if (workDone > workLimit && firstAttempt) {
 0956            return;
 957          }
 958          continue;
 959        }
 960
 0961        med = Med3(block[zptr[lo] + d + 1],
 0962               block[zptr[hi] + d + 1],
 0963               block[zptr[(lo + hi) >> 1] + d + 1]);
 964
 0965        unLo = ltLo = lo;
 0966        unHi = gtHi = hi;
 967
 0968        while (true) {
 0969          while (true) {
 0970             if (unLo > unHi) {
 971              break;
 972            }
 0973            n = ((int)block[zptr[unLo] + d + 1]) - med;
 0974             if (n == 0) {
 0975              int temp = zptr[unLo];
 0976              zptr[unLo] = zptr[ltLo];
 0977              zptr[ltLo] = temp;
 0978              ltLo++;
 0979              unLo++;
 0980              continue;
 981            }
 0982             if (n > 0) {
 983              break;
 984            }
 0985            unLo++;
 986          }
 987
 0988          while (true) {
 0989             if (unLo > unHi) {
 990              break;
 991            }
 0992            n = ((int)block[zptr[unHi] + d + 1]) - med;
 0993             if (n == 0) {
 0994              int temp = zptr[unHi];
 0995              zptr[unHi] = zptr[gtHi];
 0996              zptr[gtHi] = temp;
 0997              gtHi--;
 0998              unHi--;
 0999              continue;
 1000            }
 01001             if (n < 0) {
 1002              break;
 1003            }
 01004            unHi--;
 1005          }
 1006
 01007           if (unLo > unHi) {
 1008            break;
 1009          }
 1010
 1011          {
 01012            int temp = zptr[unLo];
 01013            zptr[unLo] = zptr[unHi];
 01014            zptr[unHi] = temp;
 01015            unLo++;
 01016            unHi--;
 1017          }
 1018        }
 1019
 01020         if (gtHi < ltLo) {
 01021          stack[sp].ll = lo;
 01022          stack[sp].hh = hi;
 01023          stack[sp].dd = d + 1;
 01024          sp++;
 01025          continue;
 1026        }
 1027
 01028        n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) : (unLo - ltLo);
 01029        Vswap(lo, unLo - n, n);
 01030        m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) : (gtHi - unHi);
 01031        Vswap(unLo, hi - m + 1, m);
 1032
 01033        n = lo + unLo - ltLo - 1;
 01034        m = hi - (gtHi - unHi) + 1;
 1035
 01036        stack[sp].ll = lo;
 01037        stack[sp].hh = n;
 01038        stack[sp].dd = d;
 01039        sp++;
 1040
 01041        stack[sp].ll = n + 1;
 01042        stack[sp].hh = m - 1;
 01043        stack[sp].dd = d + 1;
 01044        sp++;
 1045
 01046        stack[sp].ll = m;
 01047        stack[sp].hh = hi;
 01048        stack[sp].dd = d;
 01049        sp++;
 1050      }
 01051    }
 1052
 1053    void MainSort()
 1054    {
 1055      int i, j, ss, sb;
 01056      int[] runningOrder = new int[256];
 01057      int[] copy = new int[256];
 01058      bool[] bigDone = new bool[256];
 1059      int c1, c2;
 1060      int numQSorted;
 1061
 1062      /*--
 1063      In the various block-sized structures, live data runs
 1064      from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
 1065      set up the overshoot area for block.
 1066      --*/
 1067
 1068      //   if (verbosity >= 4) fprintf ( stderr, "        sort initialise ...\n" );
 01069       for (i = 0; i < BZip2Constants.OvershootBytes; i++) {
 01070        block[last + i + 2] = block[(i % (last + 1)) + 1];
 1071      }
 01072       for (i = 0; i <= last + BZip2Constants.OvershootBytes; i++) {
 01073        quadrant[i] = 0;
 1074      }
 1075
 01076      block[0] = (byte)(block[last + 1]);
 1077
 01078       if (last < 4000) {
 1079        /*--
 1080        Use simpleSort(), since the full sorting mechanism
 1081        has quite a large constant overhead.
 1082        --*/
 01083         for (i = 0; i <= last; i++) {
 01084          zptr[i] = i;
 1085        }
 01086        firstAttempt = false;
 01087        workDone = workLimit = 0;
 01088        SimpleSort(0, last, 0);
 01089      } else {
 01090        numQSorted = 0;
 01091         for (i = 0; i <= 255; i++) {
 01092          bigDone[i] = false;
 1093        }
 01094         for (i = 0; i <= 65536; i++) {
 01095          ftab[i] = 0;
 1096        }
 1097
 01098        c1 = block[0];
 01099         for (i = 0; i <= last; i++) {
 01100          c2 = block[i + 1];
 01101          ftab[(c1 << 8) + c2]++;
 01102          c1 = c2;
 1103        }
 1104
 01105         for (i = 1; i <= 65536; i++) {
 01106          ftab[i] += ftab[i - 1];
 1107        }
 1108
 01109        c1 = block[1];
 01110         for (i = 0; i < last; i++) {
 01111          c2 = block[i + 2];
 01112          j = (c1 << 8) + c2;
 01113          c1 = c2;
 01114          ftab[j]--;
 01115          zptr[ftab[j]] = i;
 1116        }
 1117
 01118        j = ((block[last + 1]) << 8) + (block[1]);
 01119        ftab[j]--;
 01120        zptr[ftab[j]] = last;
 1121
 1122        /*--
 1123        Now ftab contains the first loc of every small bucket.
 1124        Calculate the running order, from smallest to largest
 1125        big bucket.
 1126        --*/
 1127
 01128         for (i = 0; i <= 255; i++) {
 01129          runningOrder[i] = i;
 1130        }
 1131
 1132        int vv;
 01133        int h = 1;
 1134        do {
 01135          h = 3 * h + 1;
 01136         } while (h <= 256);
 1137        do {
 01138          h = h / 3;
 01139           for (i = h; i <= 255; i++) {
 01140            vv = runningOrder[i];
 01141            j = i;
 01142             while ((ftab[((runningOrder[j - h]) + 1) << 8] - ftab[(runningOrder[j - h]) << 8]) > (ftab[((vv) + 1) << 8] 
 01143              runningOrder[j] = runningOrder[j - h];
 01144              j = j - h;
 01145               if (j <= (h - 1)) {
 1146                break;
 1147              }
 1148            }
 01149            runningOrder[j] = vv;
 1150          }
 01151         } while (h != 1);
 1152
 1153        /*--
 1154        The main sorting loop.
 1155        --*/
 01156         for (i = 0; i <= 255; i++) {
 1157
 1158          /*--
 1159          Process big buckets, starting with the least full.
 1160          --*/
 01161          ss = runningOrder[i];
 1162
 1163          /*--
 1164          Complete the big bucket [ss] by quicksorting
 1165          any unsorted small buckets [ss, j].  Hopefully
 1166          previous pointer-scanning phases have already
 1167          completed many of the small buckets [ss, j], so
 1168          we don't have to sort them at all.
 1169          --*/
 01170           for (j = 0; j <= 255; j++) {
 01171            sb = (ss << 8) + j;
 01172             if (!((ftab[sb] & SETMASK) == SETMASK)) {
 01173              int lo = ftab[sb] & CLEARMASK;
 01174              int hi = (ftab[sb + 1] & CLEARMASK) - 1;
 01175               if (hi > lo) {
 01176                QSort3(lo, hi, 2);
 01177                numQSorted += (hi - lo + 1);
 01178                 if (workDone > workLimit && firstAttempt) {
 01179                  return;
 1180                }
 1181              }
 01182              ftab[sb] |= SETMASK;
 1183            }
 1184          }
 1185
 1186          /*--
 1187          The ss big bucket is now done.  Record this fact,
 1188          and update the quadrant descriptors.  Remember to
 1189          update quadrants in the overshoot area too, if
 1190          necessary.  The "if (i < 255)" test merely skips
 1191          this updating for the last bucket processed, since
 1192          updating for the last bucket is pointless.
 1193          --*/
 01194          bigDone[ss] = true;
 1195
 01196           if (i < 255) {
 01197            int bbStart = ftab[ss << 8] & CLEARMASK;
 01198            int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
 01199            int shifts = 0;
 1200
 01201             while ((bbSize >> shifts) > 65534) {
 01202              shifts++;
 1203            }
 1204
 01205             for (j = 0; j < bbSize; j++) {
 01206              int a2update = zptr[bbStart + j];
 01207              int qVal = (j >> shifts);
 01208              quadrant[a2update] = qVal;
 01209               if (a2update < BZip2Constants.OvershootBytes) {
 01210                quadrant[a2update + last + 1] = qVal;
 1211              }
 1212            }
 1213
 01214             if (!(((bbSize - 1) >> shifts) <= 65535)) {
 01215              Panic();
 1216            }
 1217          }
 1218
 1219          /*--
 1220          Now scan this big bucket so as to synthesise the
 1221          sorted order for small buckets [t, ss] for all t != ss.
 1222          --*/
 01223           for (j = 0; j <= 255; j++) {
 01224            copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
 1225          }
 1226
 01227           for (j = ftab[ss << 8] & CLEARMASK; j < (ftab[(ss + 1) << 8] & CLEARMASK); j++) {
 01228            c1 = block[zptr[j]];
 01229             if (!bigDone[c1]) {
 01230              zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
 01231              copy[c1]++;
 1232            }
 1233          }
 1234
 01235           for (j = 0; j <= 255; j++) {
 01236            ftab[(j << 8) + ss] |= SETMASK;
 1237          }
 1238        }
 1239      }
 01240    }
 1241
 1242    void RandomiseBlock()
 1243    {
 1244      int i;
 01245      int rNToGo = 0;
 01246      int rTPos = 0;
 01247       for (i = 0; i < 256; i++) {
 01248        inUse[i] = false;
 1249      }
 1250
 01251       for (i = 0; i <= last; i++) {
 01252         if (rNToGo == 0) {
 01253          rNToGo = (int)BZip2Constants.RandomNumbers[rTPos];
 01254          rTPos++;
 01255           if (rTPos == 512) {
 01256            rTPos = 0;
 1257          }
 1258        }
 01259        rNToGo--;
 01260         block[i + 1] ^= (byte)((rNToGo == 1) ? 1 : 0);
 1261        // handle 16 bit signed numbers
 01262        block[i + 1] &= 0xFF;
 1263
 01264        inUse[block[i + 1]] = true;
 1265      }
 01266    }
 1267
 1268    void DoReversibleTransformation()
 1269    {
 01270      workLimit = workFactor * last;
 01271      workDone = 0;
 01272      blockRandomised = false;
 01273      firstAttempt = true;
 1274
 01275      MainSort();
 1276
 01277       if (workDone > workLimit && firstAttempt) {
 01278        RandomiseBlock();
 01279        workLimit = workDone = 0;
 01280        blockRandomised = true;
 01281        firstAttempt = false;
 01282        MainSort();
 1283      }
 1284
 01285      origPtr = -1;
 01286       for (int i = 0; i <= last; i++) {
 01287         if (zptr[i] == 0) {
 01288          origPtr = i;
 01289          break;
 1290        }
 1291      }
 1292
 01293       if (origPtr == -1) {
 01294        Panic();
 1295      }
 01296    }
 1297
 1298    bool FullGtU(int i1, int i2)
 1299    {
 1300      int k;
 1301      byte c1, c2;
 1302      int s1, s2;
 1303
 01304      c1 = block[i1 + 1];
 01305      c2 = block[i2 + 1];
 01306       if (c1 != c2) {
 01307        return c1 > c2;
 1308      }
 01309      i1++;
 01310      i2++;
 1311
 01312      c1 = block[i1 + 1];
 01313      c2 = block[i2 + 1];
 01314       if (c1 != c2) {
 01315        return c1 > c2;
 1316      }
 01317      i1++;
 01318      i2++;
 1319
 01320      c1 = block[i1 + 1];
 01321      c2 = block[i2 + 1];
 01322       if (c1 != c2) {
 01323        return c1 > c2;
 1324      }
 01325      i1++;
 01326      i2++;
 1327
 01328      c1 = block[i1 + 1];
 01329      c2 = block[i2 + 1];
 01330       if (c1 != c2) {
 01331        return c1 > c2;
 1332      }
 01333      i1++;
 01334      i2++;
 1335
 01336      c1 = block[i1 + 1];
 01337      c2 = block[i2 + 1];
 01338       if (c1 != c2) {
 01339        return c1 > c2;
 1340      }
 01341      i1++;
 01342      i2++;
 1343
 01344      c1 = block[i1 + 1];
 01345      c2 = block[i2 + 1];
 01346       if (c1 != c2) {
 01347        return c1 > c2;
 1348      }
 01349      i1++;
 01350      i2++;
 1351
 01352      k = last + 1;
 1353
 1354      do {
 01355        c1 = block[i1 + 1];
 01356        c2 = block[i2 + 1];
 01357         if (c1 != c2) {
 01358          return c1 > c2;
 1359        }
 01360        s1 = quadrant[i1];
 01361        s2 = quadrant[i2];
 01362         if (s1 != s2) {
 01363          return s1 > s2;
 1364        }
 01365        i1++;
 01366        i2++;
 1367
 01368        c1 = block[i1 + 1];
 01369        c2 = block[i2 + 1];
 01370         if (c1 != c2) {
 01371          return c1 > c2;
 1372        }
 01373        s1 = quadrant[i1];
 01374        s2 = quadrant[i2];
 01375         if (s1 != s2) {
 01376          return s1 > s2;
 1377        }
 01378        i1++;
 01379        i2++;
 1380
 01381        c1 = block[i1 + 1];
 01382        c2 = block[i2 + 1];
 01383         if (c1 != c2) {
 01384          return c1 > c2;
 1385        }
 01386        s1 = quadrant[i1];
 01387        s2 = quadrant[i2];
 01388         if (s1 != s2) {
 01389          return s1 > s2;
 1390        }
 01391        i1++;
 01392        i2++;
 1393
 01394        c1 = block[i1 + 1];
 01395        c2 = block[i2 + 1];
 01396         if (c1 != c2) {
 01397          return c1 > c2;
 1398        }
 01399        s1 = quadrant[i1];
 01400        s2 = quadrant[i2];
 01401         if (s1 != s2) {
 01402          return s1 > s2;
 1403        }
 01404        i1++;
 01405        i2++;
 1406
 01407         if (i1 > last) {
 01408          i1 -= last;
 01409          i1--;
 1410        }
 01411         if (i2 > last) {
 01412          i2 -= last;
 01413          i2--;
 1414        }
 1415
 01416        k -= 4;
 01417        ++workDone;
 01418       } while (k >= 0);
 1419
 01420      return false;
 1421    }
 1422
 1423    void AllocateCompressStructures()
 1424    {
 11425      int n = BZip2Constants.BaseBlockSize * blockSize100k;
 11426      block = new byte[(n + 1 + BZip2Constants.OvershootBytes)];
 11427      quadrant = new int[(n + BZip2Constants.OvershootBytes)];
 11428      zptr = new int[n];
 11429      ftab = new int[65537];
 1430
 11431       if (block == null || quadrant == null || zptr == null || ftab == null) {
 1432        //    int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
 1433        //    compressOutOfMemory ( totalDraw, n );
 1434      }
 1435
 1436      /*
 1437      The back end needs a place to store the MTF values
 1438      whilst it calculates the coding tables.  We could
 1439      put them in the zptr array.  However, these values
 1440      will fit in a short, so we overlay szptr at the
 1441      start of zptr, in the hope of reducing the number
 1442      of cache misses induced by the multiple traversals
 1443      of the MTF values when calculating coding tables.
 1444      Seems to improve compression speed by about 1%.
 1445      */
 1446      //  szptr = zptr;
 1447
 1448
 11449      szptr = new short[2 * n];
 11450    }
 1451
 1452    void GenerateMTFValues()
 1453    {
 01454      char[] yy = new char[256];
 1455      int i, j;
 1456      char tmp;
 1457      char tmp2;
 1458      int zPend;
 1459      int wr;
 1460      int EOB;
 1461
 01462      MakeMaps();
 01463      EOB = nInUse + 1;
 1464
 01465       for (i = 0; i <= EOB; i++) {
 01466        mtfFreq[i] = 0;
 1467      }
 1468
 01469      wr = 0;
 01470      zPend = 0;
 01471       for (i = 0; i < nInUse; i++) {
 01472        yy[i] = (char)i;
 1473      }
 1474
 1475
 01476       for (i = 0; i <= last; i++) {
 1477        char ll_i;
 1478
 01479        ll_i = unseqToSeq[block[zptr[i]]];
 1480
 01481        j = 0;
 01482        tmp = yy[j];
 01483         while (ll_i != tmp) {
 01484          j++;
 01485          tmp2 = tmp;
 01486          tmp = yy[j];
 01487          yy[j] = tmp2;
 1488        }
 01489        yy[0] = tmp;
 1490
 01491         if (j == 0) {
 01492          zPend++;
 01493        } else {
 01494           if (zPend > 0) {
 01495            zPend--;
 01496            while (true) {
 01497               switch (zPend % 2) {
 1498                case 0:
 01499                  szptr[wr] = (short)BZip2Constants.RunA;
 01500                  wr++;
 01501                  mtfFreq[BZip2Constants.RunA]++;
 01502                  break;
 1503                case 1:
 01504                  szptr[wr] = (short)BZip2Constants.RunB;
 01505                  wr++;
 01506                  mtfFreq[BZip2Constants.RunB]++;
 1507                  break;
 1508              }
 01509               if (zPend < 2) {
 1510                break;
 1511              }
 01512              zPend = (zPend - 2) / 2;
 1513            }
 01514            zPend = 0;
 1515          }
 01516          szptr[wr] = (short)(j + 1);
 01517          wr++;
 01518          mtfFreq[j + 1]++;
 1519        }
 1520      }
 1521
 01522       if (zPend > 0) {
 01523        zPend--;
 01524        while (true) {
 01525           switch (zPend % 2) {
 1526            case 0:
 01527              szptr[wr] = (short)BZip2Constants.RunA;
 01528              wr++;
 01529              mtfFreq[BZip2Constants.RunA]++;
 01530              break;
 1531            case 1:
 01532              szptr[wr] = (short)BZip2Constants.RunB;
 01533              wr++;
 01534              mtfFreq[BZip2Constants.RunB]++;
 1535              break;
 1536          }
 01537           if (zPend < 2) {
 1538            break;
 1539          }
 01540          zPend = (zPend - 2) / 2;
 1541        }
 1542      }
 1543
 01544      szptr[wr] = (short)EOB;
 01545      wr++;
 01546      mtfFreq[EOB]++;
 1547
 01548      nMTF = wr;
 01549    }
 1550
 1551    static void Panic()
 1552    {
 01553      throw new BZip2Exception("BZip2 output stream panic");
 1554    }
 1555
 1556    static void HbMakeCodeLengths(char[] len, int[] freq, int alphaSize, int maxLen)
 1557    {
 1558      /*--
 1559      Nodes and heap entries run from 1.  Entry 0
 1560      for both the heap and nodes is a sentinel.
 1561      --*/
 1562      int nNodes, nHeap, n1, n2, j, k;
 1563      bool tooLong;
 1564
 01565      int[] heap = new int[BZip2Constants.MaximumAlphaSize + 2];
 01566      int[] weight = new int[BZip2Constants.MaximumAlphaSize * 2];
 01567      int[] parent = new int[BZip2Constants.MaximumAlphaSize * 2];
 1568
 01569       for (int i = 0; i < alphaSize; ++i) {
 01570        weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
 1571      }
 1572
 01573      while (true) {
 01574        nNodes = alphaSize;
 01575        nHeap = 0;
 1576
 01577        heap[0] = 0;
 01578        weight[0] = 0;
 01579        parent[0] = -2;
 1580
 01581         for (int i = 1; i <= alphaSize; ++i) {
 01582          parent[i] = -1;
 01583          nHeap++;
 01584          heap[nHeap] = i;
 01585          int zz = nHeap;
 01586          int tmp = heap[zz];
 01587           while (weight[tmp] < weight[heap[zz >> 1]]) {
 01588            heap[zz] = heap[zz >> 1];
 01589            zz >>= 1;
 1590          }
 01591          heap[zz] = tmp;
 1592        }
 01593         if (!(nHeap < (BZip2Constants.MaximumAlphaSize + 2))) {
 01594          Panic();
 1595        }
 1596
 01597         while (nHeap > 1) {
 01598          n1 = heap[1];
 01599          heap[1] = heap[nHeap];
 01600          nHeap--;
 01601          int zz = 1;
 01602          int yy = 0;
 01603          int tmp = heap[zz];
 01604          while (true) {
 01605            yy = zz << 1;
 01606             if (yy > nHeap) {
 1607              break;
 1608            }
 01609             if (yy < nHeap && weight[heap[yy + 1]] < weight[heap[yy]]) {
 01610              yy++;
 1611            }
 01612             if (weight[tmp] < weight[heap[yy]]) {
 1613              break;
 1614            }
 1615
 01616            heap[zz] = heap[yy];
 01617            zz = yy;
 1618          }
 01619          heap[zz] = tmp;
 01620          n2 = heap[1];
 01621          heap[1] = heap[nHeap];
 01622          nHeap--;
 1623
 01624          zz = 1;
 01625          yy = 0;
 01626          tmp = heap[zz];
 01627          while (true) {
 01628            yy = zz << 1;
 01629             if (yy > nHeap) {
 1630              break;
 1631            }
 01632             if (yy < nHeap && weight[heap[yy + 1]] < weight[heap[yy]]) {
 01633              yy++;
 1634            }
 01635             if (weight[tmp] < weight[heap[yy]]) {
 1636              break;
 1637            }
 01638            heap[zz] = heap[yy];
 01639            zz = yy;
 1640          }
 01641          heap[zz] = tmp;
 01642          nNodes++;
 01643          parent[n1] = parent[n2] = nNodes;
 1644
 01645          weight[nNodes] = (int)((weight[n1] & 0xffffff00) + (weight[n2] & 0xffffff00)) |
 01646            (int)(1 + (((weight[n1] & 0x000000ff) > (weight[n2] & 0x000000ff)) ? (weight[n1] & 0x000000ff) : (weight[n2]
 1647
 01648          parent[nNodes] = -1;
 01649          nHeap++;
 01650          heap[nHeap] = nNodes;
 1651
 01652          zz = nHeap;
 01653          tmp = heap[zz];
 01654           while (weight[tmp] < weight[heap[zz >> 1]]) {
 01655            heap[zz] = heap[zz >> 1];
 01656            zz >>= 1;
 1657          }
 01658          heap[zz] = tmp;
 1659        }
 01660         if (!(nNodes < (BZip2Constants.MaximumAlphaSize * 2))) {
 01661          Panic();
 1662        }
 1663
 01664        tooLong = false;
 01665         for (int i = 1; i <= alphaSize; ++i) {
 01666          j = 0;
 01667          k = i;
 01668           while (parent[k] >= 0) {
 01669            k = parent[k];
 01670            j++;
 1671          }
 01672          len[i - 1] = (char)j;
 01673          tooLong |= j > maxLen;
 1674        }
 1675
 01676         if (!tooLong) {
 1677          break;
 1678        }
 1679
 01680         for (int i = 1; i < alphaSize; ++i) {
 01681          j = weight[i] >> 8;
 01682          j = 1 + (j / 2);
 01683          weight[i] = j << 8;
 1684        }
 1685      }
 01686    }
 1687
 1688    static void HbAssignCodes(int[] code, char[] length, int minLen, int maxLen, int alphaSize)
 1689    {
 01690      int vec = 0;
 01691       for (int n = minLen; n <= maxLen; ++n) {
 01692         for (int i = 0; i < alphaSize; ++i) {
 01693           if (length[i] == n) {
 01694            code[i] = vec;
 01695            ++vec;
 1696          }
 1697        }
 01698        vec <<= 1;
 1699      }
 01700    }
 1701
 1702    static byte Med3(byte a, byte b, byte c)
 1703    {
 1704      byte t;
 01705       if (a > b) {
 01706        t = a;
 01707        a = b;
 01708        b = t;
 1709      }
 01710       if (b > c) {
 01711        t = b;
 01712        b = c;
 01713        c = t;
 1714      }
 01715       if (a > b) {
 01716        b = a;
 1717      }
 01718      return b;
 1719    }
 1720
 1721    struct StackElement
 1722    {
 1723      public int ll;
 1724      public int hh;
 1725      public int dd;
 1726    }
 1727
 1728    #region Instance Fields
 11729    bool isStreamOwner = true;
 1730
 1731    /*--
 1732    index of the last char in the block, so
 1733    the block size == last + 1.
 1734    --*/
 1735    int last;
 1736
 1737    /*--
 1738    index in zptr[] of original string after sorting.
 1739    --*/
 1740    int origPtr;
 1741
 1742    /*--
 1743    always: in the range 0 .. 9.
 1744    The current block size is 100000 * this number.
 1745    --*/
 1746    int blockSize100k;
 1747
 1748    bool blockRandomised;
 1749
 1750    int bytesOut;
 1751    int bsBuff;
 1752    int bsLive;
 11753    IChecksum mCrc = new BZip2Crc();
 1754
 11755    bool[] inUse = new bool[256];
 1756    int nInUse;
 1757
 11758    char[] seqToUnseq = new char[256];
 11759    char[] unseqToSeq = new char[256];
 1760
 11761    char[] selector = new char[BZip2Constants.MaximumSelectors];
 11762    char[] selectorMtf = new char[BZip2Constants.MaximumSelectors];
 1763
 1764    byte[] block;
 1765    int[] quadrant;
 1766    int[] zptr;
 1767    short[] szptr;
 1768    int[] ftab;
 1769
 1770    int nMTF;
 1771
 11772    int[] mtfFreq = new int[BZip2Constants.MaximumAlphaSize];
 1773
 1774    /*
 1775    * Used when sorting.  If too many long comparisons
 1776    * happen, we stop sorting, randomise the block
 1777    * slightly, and try again.
 1778    */
 1779    int workFactor;
 1780    int workDone;
 1781    int workLimit;
 1782    bool firstAttempt;
 1783    int nBlocksRandomised;
 1784
 11785    int currentChar = -1;
 1786    int runLength;
 1787    uint blockCRC, combinedCRC;
 1788    int allowableBlockSize;
 1789    Stream baseStream;
 1790    bool disposed_;
 1791    #endregion
 1792  }
 1793}