context: // BZip2Compressor.cs
  // ------------------------------------------------------------------
  //
  // Copyright (c) 2011 Dino Chiesa.
  // All rights reserved.
  //
  // This code module is part of DotNetZip, a zipfile class library.
  //
  // ------------------------------------------------------------------
  //
  // This code is licensed under the Microsoft Public License.
  // See the file License.txt for the license details.
  // More info on: http://dotnetzip.codeplex.com
  //
  // ------------------------------------------------------------------
  //
  // Last Saved: <2011-July-28 06:17:22>
  //
  // ------------------------------------------------------------------
  //
  // This module defines the BZip2Compressor class, which is a
  // BZIP2-compressing encoder.  It is used internally in the BZIP2
  // library, by the BZip2OutputStream class and its parallel variant,
  // ParallelBZip2OutputStream. This code was originally based on Apache
  // commons source code, and significantly modified.  The license below
  // applies to the original Apache code and to this modified variant.
  //
  // ------------------------------------------------------------------
  
  
  /*
   * Licensed to the Apache Software Foundation (ASF) under one
   * or more contributor license agreements.  See the NOTICE file
   * distributed with this work for additional information
   * regarding copyright ownership.  The ASF licenses this file
   * to you under the Apache License, Version 2.0 (the
   * "License"); you may not use this file except in compliance
   * with the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing,
   * software distributed under the License is distributed on an
   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   * KIND, either express or implied.  See the License for the
   * specific language governing permissions and limitations
   * under the License.
   */
  
  /*
   * This package is based on the work done by Keiron Liddle, Aftex Software
   * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
   * great code.
   */
  
  
  //
  // Design notes:
  //
  // This class performs BZip2 compression. It is derived from the
  // BZip2OutputStream from the Apache commons source code, but is
  // significantly modified from that code. While the Apache class is a
  // stream that compresses, this particular class simply performs
  // compression.  It follows a Manager pattern. It manages an internal
  // buffer for uncompressed data; callers place data into the buffer
  // using the Fill() method. This class then compresses the data and
  // writes the compressed form out, via the CompressAndWrite() method.
  // Because BZip2 uses byte-shredding, this class relies on a BitWriter,
  // and not a .NET Stream, to emit its output.  (*Think of the BitWriter
  // class as an Adapter that enables Bit-oriented output to a standard
  // byte-oriented .NET stream.)
  //
  // This class exists to support the two distinct output streams that
  // perform BZip2 compression: BZip2OutputStream and
  // ParallelBZip2OutputStream. These streams rely on BZip2Compressor to
  // provide the encoder/compression logic.  This code has been derived
  // from the bzip2 output stream in the Apache commons library; it has
  // been significantly modified from that form, in order to provide a
  // single compressor that could support both types of streams.
  //
  // In a bz2 file or stream, there is never any bit padding except for 0..7
  // bits in the final byte in the file. Successive compressed blocks in a
  // .bz2 file are not byte-aligned.
  //
  //
  
  using System;
  using System.IO;
  
  // flymake: csc.exe /t:module BZip2InputStream.cs BZip2OutputStream.cs Rand.cs BCRC32.cs @@FILE@@
  
  namespace AL.Utils.Ionic.BZip2
  {
      internal class BZip2Compressor
      {
          private int blockSize100k;  // 0...9
          private int currentByte = -1;
          private int runLength = 0;
          private int last;  // index into the block of the last char processed
          private int outBlockFillThreshold;
          private CompressionState cstate;
          private readonly AL.Utils.Ionic.Crc.CRC32 crc = new AL.Utils.Ionic.Crc.CRC32(true);
          BitWriter bw;
          int runs;
  
          /*
           * The following three vars are used when sorting. If too many long
           * comparisons happen, we stop sorting, randomise the block slightly, and
           * try again. I think this wrinkle in the implementation was removed from
           * a later rev of the C-language bzip, not sure. -DPC 24 Jul 2011
           *
           */
          private int workDone;
          private int workLimit;
          private bool firstAttempt;
          private bool blockRandomised;
          private int origPtr;
  
          private int nInUse;
          private int nMTF;
  
          private static readonly int SETMASK = (1 << 21);
          private static readonly int CLEARMASK = (~SETMASK);
          private static readonly byte GREATER_ICOST = 15;
          private static readonly byte LESSER_ICOST = 0;
          private static readonly int SMALL_THRESH = 20;
          private static readonly int DEPTH_THRESH = 10;
          private static readonly int WORK_FACTOR = 30;
  
          /**
           * Knuth's increments seem to work better than Incerpi-Sedgewick here.
           * Possibly because the number of elems to sort is usually small, typically
           * &lt;= 20.
           */
          private static readonly int[] increments = { 1, 4, 13, 40, 121, 364, 1093, 3280,
                                                       9841, 29524, 88573, 265720, 797161,
                                                       2391484 };
  
          /// <summary>
          ///   BZip2Compressor writes its compressed data out via a BitWriter. This
          ///   is necessary because BZip2 does byte shredding.
          /// </summary>
          public BZip2Compressor(BitWriter writer)
              : this(writer, BZip2.MaxBlockSize)
          {
          }
  
          public BZip2Compressor(BitWriter writer, int blockSize)
          {
              this.blockSize100k = blockSize;
              this.bw = writer;
  
              // 20 provides a margin of slop (not to say "Safety"). The maximum
              // size of an encoded run in the output block is 5 bytes, so really, 5
              // bytes ought to do, but this is a margin of slop found in the
              // original bzip code. Not sure if important for decoding
              // (decompressing).  So we'll leave the slop.
              this.outBlockFillThreshold = (blockSize * BZip2.BlockSizeMultiple) - 20;
              this.cstate = new CompressionState(blockSize);
              Reset();
          }
  
  
          void Reset()
          {
              // initBlock();
              this.crc.Reset();
              this.currentByte = -1;
              this.runLength = 0;
              this.last = -1;
              for (int i = 256; --i >= 0;)
                  this.cstate.inUse[i] = false;
              //bw.Reset();  xxx? want this?  no no no
          }
  
  
          public int BlockSize
          {
              get { return this.blockSize100k; }
          }
  
          public uint Crc32
          {
              get; private set;
          }
  
          public int AvailableBytesOut
          {
              get; private set;
          }
  
          /// <summary>
          ///   The number of uncompressed bytes being held in the buffer.
          /// </summary>
          /// <remarks>
          ///   <para>
          ///     I am thinking this may be useful in a Stream that uses this
          ///     compressor class. In the Close() method on the stream it could
          ///     check this value to see if anything has been written at all.  You
          ///     may think the stream could easily track the number of bytes it
          ///     wrote, which would eliminate the need for this. But, there is the
          ///     case where the stream writes a complete block, and it is full, and
          ///     then writes no more. In that case the stream may want to check.
          ///   </para>
          /// </remarks>
          public int UncompressedBytes
          {
              get { return this.last + 1; }
          }
  
  
          /// <summary>
          ///   Accept new bytes into the compressor data buffer
          /// </summary>
          /// <remarks>
          ///   <para>
          ///     This method does the first-level (cheap) run-length encoding, and
          ///     stores the encoded data into the rle block.
          ///   </para>
          /// </remarks>
          public int Fill(byte[] buffer, int offset, int count)
          {
              if (this.last >= this.outBlockFillThreshold)
                  return 0; // We're full, I tell you!
  
              int bytesWritten = 0;
              int limit = offset + count;
              int rc;
  
              // do run-length-encoding until block is full
              do
              {
                  rc = write0(buffer[offset++]);
                  if (rc > 0) bytesWritten++;
              } while (offset < limit && rc == 1);
  
              return bytesWritten;
          }
  
  
  
          /// <summary>
          ///   Process one input byte into the block.
          /// </summary>
          ///
          /// <remarks>
          ///   <para>
          ///     To "process" the byte means to do the run-length encoding.
          ///     There are 3 possible return values:
          ///
          ///        0 - the byte was not written, in other words, not
          ///            encoded into the block. This happens when the
          ///            byte b would require the start of a new run, and
          ///            the block has no more room for new runs.
          ///
          ///        1 - the byte was written, and the block is not full.
          ///
          ///        2 - the byte was written, and the block is full.
          ///
          ///   </para>
          /// </remarks>
          /// <returns>0 if the byte was not written, non-zero if written.</returns>
          private int write0(byte b)
          {
              bool rc;
              // there is no current run in progress
              if (this.currentByte == -1)
              {
                  this.currentByte = b;
                  this.runLength++;
                  return 1;
              }
  
              // this byte is the same as the current run in progress
              if (this.currentByte == b)
              {
                  if (++this.runLength > 254)
                  {
                      rc = AddRunToOutputBlock(false);
                      this.currentByte = -1;
                      this.runLength = 0;
                      return (rc) ? 2 : 1;
                  }
                  return 1; // not full
              }
  
              // This byte requires a new run.
              // Put the prior run into the Run-length-encoded block,
              // and try to start a new run.
              rc = AddRunToOutputBlock(false);
  
              if (rc)
              {
                  this.currentByte = -1;
                  this.runLength = 0;
                  // returning 0 implies the block is full, and the byte was not written.
                  return 0;
              }
  
              // start a new run
              this.runLength = 1;
              this.currentByte = b;
              return 1;
          }
  
          /// <summary>
          ///   Append one run to the output block.
          /// </summary>
          ///
          /// <remarks>
          ///   <para>
          ///     This compressor does run-length-encoding before BWT and etc. This
          ///     method simply appends a run to the output block. The append always
          ///     succeeds. The return value indicates whether the block is full:
          ///     false (not full) implies that at least one additional run could be
          ///     processed.
          ///   </para>
          /// </remarks>
          /// <returns>true if the block is now full; otherwise false.</returns>
          private bool AddRunToOutputBlock(bool final)
          {
              runs++;
              /* add_pair_to_block ( EState* s ) */
              int previousLast = this.last;
  
              // sanity check only - because of the check done at the
              // bottom of this method, and the logic in write0(), this
              // should never ever happen.
              if (previousLast >= this.outBlockFillThreshold && !final)
              {
                  var msg = String.Format("block overrun(final={2}): {0} >= threshold ({1})",
                                          previousLast, this.outBlockFillThreshold, final);
                  throw new Exception(msg);
              }
  
              // NB: the index used here into block is always (last+2).  This is
              // because last is -1 based - the initial value is -1, a flag value
              // used to indicate that nothing has yet been written into the
              // block. The endBlock() fn tests for -1 to detect empty blocks. Also,
              // the first byte of block is used, during sorting, to hold block[last
              // +1], which is the final byte value that had been written into the
              // rle block. For those two reasons, the base offset from last is
              // always +2.
  
              byte b = (byte) this.currentByte;
              byte[] block = this.cstate.block;
              this.cstate.inUse[b] = true;
              int rl = this.runLength;
              this.crc.UpdateCRC(b, rl);
  
              switch (rl)
              {
                  case 1:
                      block[previousLast + 2] = b;
                      this.last = previousLast + 1;
                      break;
  
                  case 2:
                      block[previousLast + 2] = b;
                      block[previousLast + 3] = b;
                      this.last = previousLast + 2;
                      break;
  
                  case 3:
                      block[previousLast + 2] = b;
                      block[previousLast + 3] = b;
                      block[previousLast + 4] = b;
                      this.last = previousLast + 3;
                      break;
  
                  default:
                      rl -= 4;
                      this.cstate.inUse[rl] = true;
                      block[previousLast + 2] = b;
                      block[previousLast + 3] = b;
                      block[previousLast + 4] = b;
                      block[previousLast + 5] = b;
                      block[previousLast + 6] = (byte) rl;
                      this.last = previousLast + 5;
                      break;
              }
  
              // is full?
              return (this.last >= this.outBlockFillThreshold);
          }
  
  
          /// <summary>
          ///   Compress the data that has been placed (Run-length-encoded) into the
          ///   block. The compressed data goes into the CompressedBytes array.
          /// </summary>
          /// <remarks>
          ///   <para>
          ///     Side effects: 1.  fills the CompressedBytes array.  2. sets the
          ///     AvailableBytesOut property.
          ///   </para>
          /// </remarks>
          public void CompressAndWrite() // endBlock
          {
              if (this.runLength > 0)
                  AddRunToOutputBlock(true);
  
              this.currentByte = -1;
  
              // Console.WriteLine("  BZip2Compressor:CompressAndWrite (r={0} bcrc={1:X8})",
              //                   runs, this.crc.Crc32Result);
  
              // has any data been written?
              if (this.last == -1)
                  return; // no data; nothing to compress
  
              /* sort the block and establish posn of original string */
              blockSort();
  
              /*
               * A 6-byte block header, the value chosen arbitrarily as 0x314159265359
               * :-). A 32 bit value does not really give a strong enough guarantee
               * that the value will not appear by chance in the compressed
               * datastream. Worst-case probability of this event, for a 900k block,
               * is about 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48
               * bits. For a compressed file of size 100Gb -- about 100000 blocks --
               * only a 48-bit marker will do. NB: normal compression/ decompression
               * donot rely on these statistical properties. They are only important
               * when trying to recover blocks from damaged files.
               */
              this.bw.WriteByte(0x31);
              this.bw.WriteByte(0x41);
              this.bw.WriteByte(0x59);
              this.bw.WriteByte(0x26);
              this.bw.WriteByte(0x53);
              this.bw.WriteByte(0x59);
  
              this.Crc32 = (uint) this.crc.Crc32Result;
              this.bw.WriteInt(this.Crc32);
  
              /* Now a single bit indicating randomisation. */
              this.bw.WriteBits(1, (this.blockRandomised)?1U:0U);
  
              /* Finally, block's contents proper. */
              moveToFrontCodeAndSend();
  
              Reset();
          }
  
  
          private void randomiseBlock()
          {
              bool[] inUse = this.cstate.inUse;
              byte[] block = this.cstate.block;
              int lastShadow = this.last;
  
              for (int i = 256; --i >= 0;)
                  inUse[i] = false;
  
              int rNToGo = 0;
              int rTPos = 0;
              for (int i = 0, j = 1; i <= lastShadow; i = j, j++)
              {
                  if (rNToGo == 0)
                  {
                      rNToGo = (char) Rand.Rnums(rTPos);
                      if (++rTPos == 512)
                      {
                          rTPos = 0;
                      }
                  }
  
                  rNToGo--;
                  block[j] ^= (byte) ((rNToGo == 1) ? 1 : 0);
  
                  // handle 16 bit signed numbers
                  inUse[block[j] & 0xff] = true;
              }
  
              this.blockRandomised = true;
          }
  
          private void mainSort()
          {
              CompressionState dataShadow = this.cstate;
              int[] runningOrder = dataShadow.mainSort_runningOrder;
              int[] copy = dataShadow.mainSort_copy;
              bool[] bigDone = dataShadow.mainSort_bigDone;
              int[] ftab = dataShadow.ftab;
              byte[] block = dataShadow.block;
              int[] fmap = dataShadow.fmap;
              char[] quadrant = dataShadow.quadrant;
              int lastShadow = this.last;
              int workLimitShadow = this.workLimit;
              bool firstAttemptShadow = this.firstAttempt;
  
              // Set up the 2-byte frequency table
              for (int i = 65537; --i >= 0;)
              {
                  ftab[i] = 0;
              }
  
              /*
               * In the various block-sized structures, live data runs from 0 to
               * last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area
               * for block.
               */
              for (int i = 0; i < BZip2.NUM_OVERSHOOT_BYTES; i++)
              {
                  block[lastShadow + i + 2] = block[(i % (lastShadow + 1)) + 1];
              }
              for (int i = lastShadow + BZip2.NUM_OVERSHOOT_BYTES +1; --i >= 0;)
              {
                  quadrant[i] = '\0';
              }
              block[0] = block[lastShadow + 1];
  
              // Complete the initial radix sort:
  
              int c1 = block[0] & 0xff;
              for (int i = 0; i <= lastShadow; i++)
              {
                  int c2 = block[i + 1] & 0xff;
                  ftab[(c1 << 8) + c2]++;
                  c1 = c2;
              }
  
              for (int i = 1; i <= 65536; i++)
                  ftab[i] += ftab[i - 1];
  
              c1 = block[1] & 0xff;
              for (int i = 0; i < lastShadow; i++)
              {
                  int c2 = block[i + 2] & 0xff;
                  fmap[--ftab[(c1 << 8) + c2]] = i;
                  c1 = c2;
              }
  
              fmap[--ftab[((block[lastShadow + 1] & 0xff) << 8) + (block[1] & 0xff)]] = lastShadow;
  
              /*
               * Now ftab contains the first loc of every small bucket. Calculate the
               * running order, from smallest to largest big bucket.
               */
              for (int i = 256; --i >= 0;)
              {
                  bigDone[i] = false;
                  runningOrder[i] = i;
              }
  
              for (int h = 364; h != 1;)
              {
                  h /= 3;
                  for (int i = h; i <= 255; i++)
                  {
                      int vv = runningOrder[i];
                      int a = ftab[(vv + 1) << 8] - ftab[vv << 8];
                      int b = h - 1;
                      int j = i;
                      for (int ro = runningOrder[j - h]; (ftab[(ro + 1) << 8] - ftab[ro << 8]) > a; ro = runningOrder[j
                                                                                                                      - h])
                      {
                          runningOrder[j] = ro;
                          j -= h;
                          if (j <= b)
                          {
                              break;
                          }
                      }
                      runningOrder[j] = vv;
                  }
              }
  
              /*
               * The main sorting loop.
               */
              for (int i = 0; i <= 255; i++)
              {
                  /*
                   * Process big buckets, starting with the least full.
                   */
                  int ss = runningOrder[i];
  
                  // Step 1:
                  /*
                   * Complete the big bucket [ss] by quicksorting any unsorted small
                   * buckets [ss, j]. Hopefully previous pointer-scanning phases have
                   * already completed many of the small buckets [ss, j], so we don't
                   * have to sort them at all.
                   */
                  for (int j = 0; j <= 255; j++)
                  {
                      int sb = (ss << 8) + j;
                      int ftab_sb = ftab[sb];
                      if ((ftab_sb & SETMASK) != SETMASK)
                      {
                          int lo = ftab_sb & CLEARMASK;
                          int hi = (ftab[sb + 1] & CLEARMASK) - 1;
                          if (hi > lo)
                          {
                              mainQSort3(dataShadow, lo, hi, 2);
                              if (firstAttemptShadow
                                  && (this.workDone > workLimitShadow))
                              {
                                  return;
                              }
                          }
  
gt:                         ftab[sb] = ftab_sb | SETMASK;