code.grnet.gr Git - pithos-ms-client/blob - trunk/hammock/src/net35/ICSharpCode.SharpZipLib.Silverlight/BZip2/BZip2OutputStream.cs

   1 // BZip2OutputStream.cs
   2 //
   3 // Copyright (C) 2001 Mike Krueger
   4 //
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License
   7 // as published by the Free Software Foundation; either version 2
   8 // of the License, or (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18 //
  19 // Linking this library statically or dynamically with other modules is
  20 // making a combined work based on this library.  Thus, the terms and
  21 // conditions of the GNU General Public License cover the whole
  22 // combination.
  23 //
  24 // As a special exception, the copyright holders of this library give you
  25 // permission to link this library with independent modules to produce an
  26 // executable, regardless of the license terms of these independent
  27 // modules, and to copy and distribute the resulting executable under
  28 // terms of your choice, provided that you also meet, for each linked
  29 // independent module, the terms and conditions of the license of that
  30 // module.  An independent module is a module which is not derived from
  31 // or based on this library.  If you modify this library, you may extend
  32 // this exception to your version of the library, but you are not
  33 // obligated to do so.  If you do not wish to do so, delete this
  34 // exception statement from your version.
  35
  36 using System;
  37 using System.IO;
  38 using ICSharpCode.SharpZipLib.Silverlight.BZip2;
  39 using ICSharpCode.SharpZipLib.Silverlight.Checksums;
  40
  41 namespace ICSharpCode.SharpZipLib.Silverlight.BZip2
  42 {
  43     /// <summary>
  44     /// An output stream that compresses into the BZip2 format
  45     /// including file header chars into another stream.
  46     /// </summary>
  47     public class BZip2OutputStream : Stream
  48     {
  49         #region Constants
  50         const int SETMASK       = (1 << 21);
  51         const int CLEARMASK     = (~SETMASK);
  52         const int GREATER_ICOST = 15;
  53         const int LESSER_ICOST = 0;
  54         const int SMALL_THRESH = 20;
  55         const int DEPTH_THRESH = 10;
  56
  57         /*--
  58                 If you are ever unlucky/improbable enough
  59                 to get a stack overflow whilst sorting,
  60                 increase the following constant and try
  61                 again.  In practice I have never seen the
  62                 stack go above 27 elems, so the following
  63                 limit seems very generous.
  64                 --*/
  65         const int QSORT_STACK_SIZE = 1000;
  66
  67         /*--
  68                 Knuth's increments seem to work better
  69                 than Incerpi-Sedgewick here.  Possibly
  70                 because the number of elems to sort is
  71                 usually small, typically <= 20.
  72                 --*/
  73         readonly int[] increments = new int[] {
  74                                                   1, 4, 13, 40, 121, 364, 1093, 3280,
  75                                                   9841, 29524, 88573, 265720,
  76                                                   797161, 2391484
  77                                               };
  78         #endregion
  79
  80         #region Constructors
  81         /// <summary>
  82         /// Construct a default output stream with maximum block size
  83         /// </summary>
  84         /// <param name="stream">The stream to write BZip data onto.</param>
  85         public BZip2OutputStream(Stream stream) : this(stream, 9)
  86         {
  87         }
  88
  89         /// <summary>
  90         /// Initialise a new instance of the <see cref="BZip2OutputStream"></see>
  91         /// for the specified stream, using the given blocksize.
  92         /// </summary>
  93         /// <param name="stream">The stream to write compressed data to.</param>
  94         /// <param name="blockSize">The block size to use.</param>
  95         /// <remarks>
  96         /// Valid block sizes are in the range 1..9, with 1 giving
  97         /// the lowest compression and 9 the highest.
  98         /// </remarks>
  99         public BZip2OutputStream(Stream stream, int blockSize)
 100         {
 101             BsSetStream(stream);
 102
 103             workFactor = 50;
 104             if (blockSize > 9) {
 105                 blockSize = 9;
 106             }
 107
 108             if (blockSize < 1) {
 109                 blockSize = 1;
 110             }
 111             blockSize100k = blockSize;
 112             AllocateCompressStructures();
 113             Initialize();
 114             InitBlock();
 115         }
 116         #endregion
 117
 118         #region Destructor
 119         /// <summary>
 120         /// Ensures that resources are freed and other cleanup operations
 121         /// are performed when the garbage collector reclaims the BZip2OutputStream.
 122         /// </summary>
 123         ~BZip2OutputStream()
 124         {
 125             Dispose(false);
 126         }
 127         #endregion
 128
 129         /// <summary>
 130         /// Get/set flag indicating ownership of underlying stream.
 131         /// When the flag is true <see cref="Close"></see> will close the underlying stream also.
 132         /// </summary>
 133         public bool IsStreamOwner
 134         {
 135             get { return isStreamOwner; }
 136             set { isStreamOwner = value; }
 137         }
 138
 139
 140         #region Stream overrides
 141         /// <summary>
 142         /// Gets a value indicating whether the current stream supports reading
 143         /// </summary>
 144         public override bool CanRead
 145         {
 146             get {
 147                 return false;
 148             }
 149         }
 150
 151         /// <summary>
 152         /// Gets a value indicating whether the current stream supports seeking
 153         /// </summary>
 154         public override bool CanSeek {
 155             get {
 156                 return false;
 157             }
 158         }
 159
 160         /// <summary>
 161         /// Gets a value indicating whether the current stream supports writing
 162         /// </summary>
 163         public override bool CanWrite {
 164             get {
 165                 return baseStream.CanWrite;
 166             }
 167         }
 168
 169         /// <summary>
 170         /// Gets the length in bytes of the stream
 171         /// </summary>
 172         public override long Length {
 173             get {
 174                 return baseStream.Length;
 175             }
 176         }
 177
 178         /// <summary>
 179         /// Gets or sets the current position of this stream.
 180         /// </summary>
 181         public override long Position {
 182             get {
 183                 return baseStream.Position;
 184             }
 185             set {
 186                 throw new NotSupportedException("BZip2OutputStream position cannot be set");
 187             }
 188         }
 189
 190         /// <summary>
 191         /// Sets the current position of this stream to the given value.
 192         /// </summary>
 193         /// <param name="offset">The point relative to the offset from which to being seeking.</param>
 194         /// <param name="origin">The reference point from which to begin seeking.</param>
 195         /// <returns>The new position in the stream.</returns>
 196         public override long Seek(long offset, SeekOrigin origin)
 197         {
 198             throw new NotSupportedException("BZip2OutputStream Seek not supported");
 199         }
 200
 201         /// <summary>
 202         /// Sets the length of this stream to the given value.
 203         /// </summary>
 204         /// <param name="value">The new stream length.</param>
 205         public override void SetLength(long value)
 206         {
 207             throw new NotSupportedException("BZip2OutputStream SetLength not supported");
 208         }
 209
 210         /// <summary>
 211         /// Read a byte from the stream advancing the position.
 212         /// </summary>
 213         /// <returns>The byte read cast to an int; -1 if end of stream.</returns>
 214         public override int ReadByte()
 215         {
 216             throw new NotSupportedException("BZip2OutputStream ReadByte not supported");
 217         }
 218
 219         /// <summary>
 220         /// Read a block of bytes
 221         /// </summary>
 222         /// <param name="buffer">The buffer to read into.</param>
 223         /// <param name="offset">The offset in the buffer to start storing data at.</param>
 224         /// <param name="count">The maximum number of bytes to read.</param>
 225         /// <returns>The total number of bytes read. This might be less than the number of bytes
 226         /// requested if that number of bytes are not currently available, or zero
 227         /// if the end of the stream is reached.</returns>
 228         public override int Read(byte[] buffer, int offset, int count)
 229         {
 230             throw new NotSupportedException("BZip2OutputStream Read not supported");
 231         }
 232
 233         /// <summary>
 234         /// Write a block of bytes to the stream
 235         /// </summary>
 236         /// <param name="buffer">The buffer containing data to write.</param>
 237         /// <param name="offset">The offset of the first byte to write.</param>
 238         /// <param name="count">The number of bytes to write.</param>
 239         public override void Write(byte[] buffer, int offset, int count)
 240         {
 241             if ( buffer == null ) {
 242                 throw new ArgumentNullException("buffer");
 243             }
 244
 245             if ( offset < 0 )
 246             {
 247                 throw new ArgumentOutOfRangeException("offset");
 248             }
 249
 250             if ( count < 0 )
 251             {
 252                 throw new ArgumentOutOfRangeException("count");
 253             }
 254
 255             if ( buffer.Length - offset < count )
 256             {
 257                 throw new ArgumentException("Offset/count out of range");
 258             }
 259
 260             for (int i = 0; i < count; ++i) {
 261                 WriteByte(buffer[offset + i]);
 262             }
 263         }
 264
 265         /// <summary>
 266         /// Write a byte to the stream.
 267         /// </summary>
 268         /// <param name="value">The byte to write to the stream.</param>
 269         public override void WriteByte(byte value)
 270         {
 271             int b = (256 + value) % 256;
 272             if (currentChar != -1) {
 273                 if (currentChar == b) {
 274                     runLength++;
 275                     if (runLength > 254) {
 276                         WriteRun();
 277                         currentChar = -1;
 278                         runLength = 0;
 279                     }
 280                 } else {
 281                     WriteRun();
 282                     runLength = 1;
 283                     currentChar = b;
 284                 }
 285             } else {
 286                 currentChar = b;
 287                 runLength++;
 288             }
 289         }
 290
 291         /// <summary>
 292         /// End the current block and end compression.
 293         /// Close the stream and free any resources
 294         /// </summary>
 295         public override void Close()
 296         {
 297             Dispose(true);
 298             GC.SuppressFinalize(this);
 299         }
 300
 301         #endregion
 302         void MakeMaps()
 303         {
 304             nInUse = 0;
 305             for (int i = 0; i < 256; i++) {
 306                 if (inUse[i]) {
 307                     seqToUnseq[nInUse] = (char)i;
 308                     unseqToSeq[i] = (char)nInUse;
 309                     nInUse++;
 310                 }
 311             }
 312         }
 313
 314         /// <summary>
 315         /// Get the number of bytes written to output.
 316         /// </summary>
 317         void WriteRun()
 318         {
 319             if (last < allowableBlockSize) {
 320                 inUse[currentChar] = true;
 321                 for (int i = 0; i < runLength; i++) {
 322                     mCrc.Update(currentChar);
 323                 }
 324
 325                 switch (runLength) {
 326                     case 1:
 327                         last++;
 328                         block[last + 1] = (byte)currentChar;
 329                         break;
 330                     case 2:
 331                         last++;
 332                         block[last + 1] = (byte)currentChar;
 333                         last++;
 334                         block[last + 1] = (byte)currentChar;
 335                         break;
 336                     case 3:
 337                         last++;
 338                         block[last + 1] = (byte)currentChar;
 339                         last++;
 340                         block[last + 1] = (byte)currentChar;
 341                         last++;
 342                         block[last + 1] = (byte)currentChar;
 343                         break;
 344                     default:
 345                         inUse[runLength - 4] = true;
 346                         last++;
 347                         block[last + 1] = (byte)currentChar;
 348                         last++;
 349                         block[last + 1] = (byte)currentChar;
 350                         last++;
 351                         block[last + 1] = (byte)currentChar;
 352                         last++;
 353                         block[last + 1] = (byte)currentChar;
 354                         last++;
 355                         block[last + 1] = (byte)(runLength - 4);
 356                         break;
 357                 }
 358             } else {
 359                 EndBlock();
 360                 InitBlock();
 361                 WriteRun();
 362             }
 363         }
 364
 365         /// <summary>
 366         /// Get the number of bytes written to the output.
 367         /// </summary>
 368         public int BytesWritten
 369         {
 370             get { return bytesOut; }
 371         }
 372
 373         /// <summary>
 374         /// Releases the unmanaged resources used by the <see cref="BZip2OutputStream"/> and optionally releases the managed resources.
 375         /// </summary>
 376         /// <param name="disposing">true to release both managed and unmanaged resources; false to release only unmanaged resources.</param>
 377         override protected void Dispose(bool disposing)
 378         {
 379             try {
 380                 base.Dispose(disposing);
 381                 if( !disposed_ ) {
 382                     disposed_=true;
 383
 384                     if( runLength>0 ) {
 385                         WriteRun();
 386                     }
 387
 388                     currentChar=-1;
 389                     EndBlock();
 390                     EndCompression();
 391                     Flush();
 392                 }
 393             }
 394             finally {
 395                 if ( disposing ) {
 396                     if ( IsStreamOwner ) {
 397                         baseStream.Close();
 398                     }
 399                 }
 400             }
 401         }
 402
 403         /// <summary>
 404         /// Flush output buffers
 405         /// </summary>
 406         public override void Flush()
 407         {
 408             baseStream.Flush();
 409         }
 410
 411         void Initialize()
 412         {
 413             bytesOut = 0;
 414             nBlocksRandomised = 0;
 415
 416             /*--- Write header `magic' bytes indicating file-format == huffmanised,
 417                         followed by a digit indicating blockSize100k.
 418                         ---*/
 419
 420             BsPutUChar('B');
 421             BsPutUChar('Z');
 422
 423             BsPutUChar('h');
 424             BsPutUChar('0' + blockSize100k);
 425
 426             combinedCRC = 0;
 427         }
 428
 429         void InitBlock()
 430         {
 431             mCrc.Reset();
 432             last = -1;
 433
 434             for (int i = 0; i < 256; i++) {
 435                 inUse[i] = false;
 436             }
 437
 438             /*--- 20 is just a paranoia constant ---*/
 439             allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20;
 440         }
 441
 442         void EndBlock()
 443         {
 444             if (last < 0) {       // dont do anything for empty files, (makes empty files compatible with original Bzip)
 445                 return;
 446             }
 447
 448             blockCRC = unchecked((uint)mCrc.Value);
 449             combinedCRC = (combinedCRC << 1) | (combinedCRC >> 31);
 450             combinedCRC ^= blockCRC;
 451
 452             /*-- sort the block and establish position of original string --*/
 453             DoReversibleTransformation();
 454
 455             /*--
 456                         A 6-byte block header, the value chosen arbitrarily
 457                         as 0x314159265359 :-).  A 32 bit value does not really
 458                         give a strong enough guarantee that the value will not
 459                         appear by chance in the compressed datastream.  Worst-case
 460                         probability of this event, for a 900k block, is about
 461                         2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
 462                         For a compressed file of size 100Gb -- about 100000 blocks --
 463                         only a 48-bit marker will do.  NB: normal compression/
 464                         decompression do *not* rely on these statistical properties.
 465                         They are only important when trying to recover blocks from
 466                         damaged files.
 467                         --*/
 468             BsPutUChar(0x31);
 469             BsPutUChar(0x41);
 470             BsPutUChar(0x59);
 471             BsPutUChar(0x26);
 472             BsPutUChar(0x53);
 473             BsPutUChar(0x59);
 474
 475             /*-- Now the block's CRC, so it is in a known place. --*/
 476             unchecked {
 477                 BsPutint((int)blockCRC);
 478             }
 479
 480             /*-- Now a single bit indicating randomisation. --*/
 481             if (blockRandomised) {
 482                 BsW(1,1);
 483                 nBlocksRandomised++;
 484             } else {
 485                 BsW(1,0);
 486             }
 487
 488             /*-- Finally, block's contents proper. --*/
 489             MoveToFrontCodeAndSend();
 490         }
 491
 492         void EndCompression()
 493         {
 494             /*--
 495                         Now another magic 48-bit number, 0x177245385090, to
 496                         indicate the end of the last block.  (sqrt(pi), if
 497                         you want to know.  I did want to use e, but it contains
 498                         too much repetition -- 27 18 28 18 28 46 -- for me
 499                         to feel statistically comfortable.  Call me paranoid.)
 500                         --*/
 501             BsPutUChar(0x17);
 502             BsPutUChar(0x72);
 503             BsPutUChar(0x45);
 504             BsPutUChar(0x38);
 505             BsPutUChar(0x50);
 506             BsPutUChar(0x90);
 507
 508             unchecked {
 509                 BsPutint((int)combinedCRC);
 510             }
 511
 512             BsFinishedWithStream();
 513         }
 514
 515         void BsSetStream(Stream stream)
 516         {
 517             baseStream = stream;
 518             bsLive = 0;
 519             bsBuff = 0;
 520             bytesOut = 0;
 521         }
 522
 523         void BsFinishedWithStream()
 524         {
 525             while (bsLive > 0)
 526             {
 527                 int ch = (bsBuff >> 24);
 528                 baseStream.WriteByte((byte)ch); // write 8-bit
 529                 bsBuff <<= 8;
 530                 bsLive -= 8;
 531                 bytesOut++;
 532             }
 533         }
 534
 535         void BsW(int n, int v)
 536         {
 537             while (bsLive >= 8) {
 538                 int ch = (bsBuff >> 24);
 539                 unchecked{baseStream.WriteByte((byte)ch);} // write 8-bit
 540                 bsBuff <<= 8;
 541                 bsLive -= 8;
 542                 ++bytesOut;
 543             }
 544             bsBuff |= (v << (32 - bsLive - n));
 545             bsLive += n;
 546         }
 547
 548         void BsPutUChar(int c)
 549         {
 550             BsW(8, c);
 551         }
 552
 553         void BsPutint(int u)
 554         {
 555             BsW(8, (u >> 24) & 0xFF);
 556             BsW(8, (u >> 16) & 0xFF);
 557             BsW(8, (u >>  8) & 0xFF);
 558             BsW(8,  u        & 0xFF);
 559         }
 560
 561         void BsPutIntVS(int numBits, int c)
 562         {
 563             BsW(numBits, c);
 564         }
 565
 566         void SendMTFValues()
 567         {
 568             char[][] len = new char[BZip2Constants.N_GROUPS][];
 569             for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
 570                 len[i] = new char[BZip2Constants.MAX_ALPHA_SIZE];
 571             }
 572
 573             int gs, ge, totc, bt, bc, iter;
 574             int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
 575             int nGroups;
 576
 577             alphaSize = nInUse + 2;
 578             for (int t = 0; t < BZip2Constants.N_GROUPS; t++) {
 579                 for (int v = 0; v < alphaSize; v++) {
 580                     len[t][v] = (char)GREATER_ICOST;
 581                 }
 582             }
 583
 584             /*--- Decide how many coding tables to use ---*/
 585             if (nMTF <= 0) {
 586                 Panic();
 587             }
 588
 589             if (nMTF < 200) {
 590                 nGroups = 2;
 591             } else if (nMTF < 600) {
 592                 nGroups = 3;
 593             } else if (nMTF < 1200) {
 594                 nGroups = 4;
 595             } else if (nMTF < 2400) {
 596                 nGroups = 5;
 597             } else {
 598                 nGroups = 6;
 599             }
 600
 601             /*--- Generate an initial set of coding tables ---*/
 602             int nPart = nGroups;
 603             int remF  = nMTF;
 604             gs = 0;
 605             while (nPart > 0) {
 606                 int tFreq = remF / nPart;
 607                 int aFreq = 0;
 608                 ge = gs - 1;
 609                 while (aFreq < tFreq && ge < alphaSize - 1) {
 610                     ge++;
 611                     aFreq += mtfFreq[ge];
 612                 }
 613
 614                 if (ge > gs && nPart != nGroups && nPart != 1 && ((nGroups - nPart) % 2 == 1)) {
 615                     aFreq -= mtfFreq[ge];
 616                     ge--;
 617                 }
 618
 619                 for (int v = 0; v < alphaSize; v++) {
 620                     if (v >= gs && v <= ge) {
 621                         len[nPart - 1][v] = (char)LESSER_ICOST;
 622                     } else {
 623                         len[nPart - 1][v] = (char)GREATER_ICOST;
 624                     }
 625                 }
 626
 627                 nPart--;
 628                 gs = ge + 1;
 629                 remF -= aFreq;
 630             }
 631
 632             int[][] rfreq = new int[BZip2Constants.N_GROUPS][];
 633             for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
 634                 rfreq[i] = new int[BZip2Constants.MAX_ALPHA_SIZE];
 635             }
 636
 637             int[] fave = new int[BZip2Constants.N_GROUPS];
 638             short[] cost = new short[BZip2Constants.N_GROUPS];
 639             /*---
 640                         Iterate up to N_ITERS times to improve the tables.
 641                         ---*/
 642             for (iter = 0; iter < BZip2Constants.N_ITERS; ++iter) {
 643                 for (int t = 0; t < nGroups; ++t) {
 644                     fave[t] = 0;
 645                 }
 646
 647                 for (int t = 0; t < nGroups; ++t) {
 648                     for (int v = 0; v < alphaSize; ++v) {
 649                         rfreq[t][v] = 0;
 650                     }
 651                 }
 652
 653                 nSelectors = 0;
 654                 totc = 0;
 655                 gs   = 0;
 656                 while (true) {
 657                     /*--- Set group start & end marks. --*/
 658                     if (gs >= nMTF) {
 659                         break;
 660                     }
 661                     ge = gs + BZip2Constants.G_SIZE - 1;
 662                     if (ge >= nMTF) {
 663                         ge = nMTF - 1;
 664                     }
 665
 666                     /*--
 667                                         Calculate the cost of this group as coded
 668                                         by each of the coding tables.
 669                                         --*/
 670                     for (int t = 0; t < nGroups; t++) {
 671                         cost[t] = 0;
 672                     }
 673
 674                     if (nGroups == 6) {
 675                         short cost0, cost1, cost2, cost3, cost4, cost5;
 676                         cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
 677                         for (int i = gs; i <= ge; ++i) {
 678                             short icv = szptr[i];
 679                             cost0 += (short)len[0][icv];
 680                             cost1 += (short)len[1][icv];
 681                             cost2 += (short)len[2][icv];
 682                             cost3 += (short)len[3][icv];
 683                             cost4 += (short)len[4][icv];
 684                             cost5 += (short)len[5][icv];
 685                         }
 686                         cost[0] = cost0;
 687                         cost[1] = cost1;
 688                         cost[2] = cost2;
 689                         cost[3] = cost3;
 690                         cost[4] = cost4;
 691                         cost[5] = cost5;
 692                     } else {
 693                         for (int i = gs; i <= ge; ++i) {
 694                             short icv = szptr[i];
 695                             for (int t = 0; t < nGroups; t++) {
 696                                 cost[t] += (short)len[t][icv];
 697                             }
 698                         }
 699                     }
 700
 701                     /*--
 702                                         Find the coding table which is best for this group,
 703                                         and record its identity in the selector table.
 704                                         --*/
 705                     bc = 999999999;
 706                     bt = -1;
 707                     for (int t = 0; t < nGroups; ++t) {
 708                         if (cost[t] < bc) {
 709                             bc = cost[t];
 710                             bt = t;
 711                         }
 712                     }
 713                     totc += bc;
 714                     fave[bt]++;
 715                     selector[nSelectors] = (char)bt;
 716                     nSelectors++;
 717
 718                     /*--
 719                                         Increment the symbol frequencies for the selected table.
 720                                         --*/
 721                     for (int i = gs; i <= ge; ++i) {
 722                         ++rfreq[bt][szptr[i]];
 723                     }
 724
 725                     gs = ge+1;
 726                 }
 727
 728                 /*--
 729                                 Recompute the tables based on the accumulated frequencies.
 730                                 --*/
 731                 for (int t = 0; t < nGroups; ++t) {
 732                     HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
 733                 }
 734             }
 735
 736             rfreq = null;
 737             fave = null;
 738             cost = null;
 739
 740             if (!(nGroups < 8)) {
 741                 Panic();
 742             }
 743
 744             if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.G_SIZE)))) {
 745                 Panic();
 746             }
 747
 748             /*--- Compute MTF values for the selectors. ---*/
 749             char[] pos = new char[BZip2Constants.N_GROUPS];
 750             char ll_i, tmp2, tmp;
 751
 752             for (int i = 0; i < nGroups; i++) {
 753                 pos[i] = (char)i;
 754             }
 755
 756             for (int i = 0; i < nSelectors; i++) {
 757                 ll_i = selector[i];
 758                 int j = 0;
 759                 tmp = pos[j];
 760                 while (ll_i != tmp) {
 761                     j++;
 762                     tmp2 = tmp;
 763                     tmp = pos[j];
 764                     pos[j] = tmp2;
 765                 }
 766                 pos[0] = tmp;
 767                 selectorMtf[i] = (char)j;
 768             }
 769
 770             int[][] code = new int[BZip2Constants.N_GROUPS][];
 771
 772             for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
 773                 code[i] = new int[BZip2Constants.MAX_ALPHA_SIZE];
 774             }
 775
 776             /*--- Assign actual codes for the tables. --*/
 777             for (int t = 0; t < nGroups; t++) {
 778                 minLen = 32;
 779                 maxLen = 0;
 780                 for (int i = 0; i < alphaSize; i++) {
 781                     if (len[t][i] > maxLen) {
 782                         maxLen = len[t][i];
 783                     }
 784                     if (len[t][i] < minLen) {
 785                         minLen = len[t][i];
 786                     }
 787                 }
 788                 if (maxLen > 20) {
 789                     Panic();
 790                 }
 791                 if (minLen < 1) {
 792                     Panic();
 793                 }
 794                 HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
 795             }
 796
 797             /*--- Transmit the mapping table. ---*/
 798             bool[] inUse16 = new bool[16];
 799             for (int i = 0; i < 16; ++i) {
 800                 inUse16[i] = false;
 801                 for (int j = 0; j < 16; ++j) {
 802                     if (inUse[i * 16 + j]) {
 803                         inUse16[i] = true;
 804                     }
 805                 }
 806             }
 807
 808             for (int i = 0; i < 16; ++i) {
 809                 if (inUse16[i]) {
 810                     BsW(1,1);
 811                 } else {
 812                     BsW(1,0);
 813                 }
 814             }
 815
 816             for (int i = 0; i < 16; ++i) {
 817                 if (inUse16[i]) {
 818                     for (int j = 0; j < 16; ++j) {
 819                         if (inUse[i * 16 + j]) {
 820                             BsW(1,1);
 821                         } else {
 822                             BsW(1,0);
 823                         }
 824                     }
 825                 }
 826             }
 827
 828             /*--- Now the selectors. ---*/
 829             BsW(3, nGroups);
 830             BsW(15, nSelectors);
 831             for (int i = 0; i < nSelectors; ++i) {
 832                 for (int j = 0; j < selectorMtf[i]; ++j) {
 833                     BsW(1,1);
 834                 }
 835                 BsW(1,0);
 836             }
 837
 838             /*--- Now the coding tables. ---*/
 839             for (int t = 0; t < nGroups; ++t) {
 840                 int curr = len[t][0];
 841                 BsW(5, curr);
 842                 for (int i = 0; i < alphaSize; ++i) {
 843                     while (curr < len[t][i]) {
 844                         BsW(2, 2);
 845                         curr++; /* 10 */
 846                     }
 847                     while (curr > len[t][i]) {
 848                         BsW(2, 3);
 849                         curr--; /* 11 */
 850                     }
 851                     BsW (1, 0);
 852                 }
 853             }
 854
 855             /*--- And finally, the block data proper ---*/
 856             selCtr = 0;
 857             gs = 0;
 858             while (true) {
 859                 if (gs >= nMTF) {
 860                     break;
 861                 }
 862                 ge = gs + BZip2Constants.G_SIZE - 1;
 863                 if (ge >= nMTF) {
 864                     ge = nMTF - 1;
 865                 }
 866
 867                 for (int i = gs; i <= ge; i++) {
 868                     BsW(len[selector[selCtr]][szptr[i]], code[selector[selCtr]][szptr[i]]);
 869                 }
 870
 871                 gs = ge + 1;
 872                 ++selCtr;
 873             }
 874             if (!(selCtr == nSelectors)) {
 875                 Panic();
 876             }
 877         }
 878
 879         void MoveToFrontCodeAndSend ()
 880         {
 881             BsPutIntVS(24, origPtr);
 882             GenerateMTFValues();
 883             SendMTFValues();
 884         }
 885
 886         void SimpleSort(int lo, int hi, int d)
 887         {
 888             int i, j, h, bigN, hp;
 889             int v;
 890
 891             bigN = hi - lo + 1;
 892             if (bigN < 2) {
 893                 return;
 894             }
 895
 896             hp = 0;
 897             while (increments[hp] < bigN) {
 898                 hp++;
 899             }
 900             hp--;
 901
 902             for (; hp >= 0; hp--) {
 903                 h = increments[hp];
 904
 905                 i = lo + h;
 906                 while (true) {
 907                     /*-- copy 1 --*/
 908                     if (i > hi)
 909                         break;
 910                     v = zptr[i];
 911                     j = i;
 912                     while (FullGtU(zptr[j-h]+d, v+d)) {
 913                         zptr[j] = zptr[j-h];
 914                         j = j - h;
 915                         if (j <= (lo + h - 1))
 916                             break;
 917                     }
 918                     zptr[j] = v;
 919                     i++;
 920
 921                     /*-- copy 2 --*/
 922                     if (i > hi) {
 923                         break;
 924                     }
 925                     v = zptr[i];
 926                     j = i;
 927                     while (FullGtU ( zptr[j-h]+d, v+d )) {
 928                         zptr[j] = zptr[j-h];
 929                         j = j - h;
 930                         if (j <= (lo + h - 1)) {
 931                             break;
 932                         }
 933                     }
 934                     zptr[j] = v;
 935                     i++;
 936
 937                     /*-- copy 3 --*/
 938                     if (i > hi) {
 939                         break;
 940                     }
 941                     v = zptr[i];
 942                     j = i;
 943                     while (FullGtU ( zptr[j-h]+d, v+d)) {
 944                         zptr[j] = zptr[j-h];
 945                         j = j - h;
 946                         if (j <= (lo + h - 1)) {
 947                             break;
 948                         }
 949                     }
 950                     zptr[j] = v;
 951                     i++;
 952
 953                     if (workDone > workLimit && firstAttempt) {
 954                         return;
 955                     }
 956                 }
 957             }
 958         }
 959
 960         void Vswap(int p1, int p2, int n )
 961         {
 962             int temp = 0;
 963             while (n > 0) {
 964                 temp = zptr[p1];
 965                 zptr[p1] = zptr[p2];
 966                 zptr[p2] = temp;
 967                 p1++;
 968                 p2++;
 969                 n--;
 970             }
 971         }
 972
 973         void QSort3(int loSt, int hiSt, int dSt)
 974         {
 975             int unLo, unHi, ltLo, gtHi, med, n, m;
 976             int lo, hi, d;
 977             StackElement[] stack = new StackElement[QSORT_STACK_SIZE];
 978             for (int count = 0; count < QSORT_STACK_SIZE; count++) {
 979                 stack[count] = new StackElement();
 980             }
 981
 982             int sp = 0;
 983
 984             stack[sp].ll = loSt;
 985             stack[sp].hh = hiSt;
 986             stack[sp].dd = dSt;
 987             sp++;
 988
 989             while (sp > 0) {
 990                 if (sp >= QSORT_STACK_SIZE) {
 991                     Panic();
 992                 }
 993
 994                 sp--;
 995                 lo = stack[sp].ll;
 996                 hi = stack[sp].hh;
 997                 d = stack[sp].dd;
 998
 999                 if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
1000                     SimpleSort(lo, hi, d);
1001                     if (workDone > workLimit && firstAttempt) {
1002                         return;
1003                     }
1004                     continue;
1005                 }
1006
1007                 med = Med3(block[zptr[lo] + d + 1],
1008                            block[zptr[hi            ] + d  + 1],
1009                            block[zptr[(lo + hi) >> 1] + d + 1]);
1010
1011                 unLo = ltLo = lo;
1012                 unHi = gtHi = hi;
1013
1014                 while (true) {
1015                     while (true) {
1016                         if (unLo > unHi) {
1017                             break;
1018                         }
1019                         n = ((int)block[zptr[unLo]+d + 1]) - med;
1020                         if (n == 0) {
1021                             int temp = 0;
1022                             temp = zptr[unLo];
1023                             zptr[unLo] = zptr[ltLo];
1024                             zptr[ltLo] = temp;
1025                             ltLo++;
1026                             unLo++;
1027                             continue;
1028                         }
1029                         if (n >  0) {
1030                             break;
1031                         }
1032                         unLo++;
1033                     }
1034
1035                     while (true) {
1036                         if (unLo > unHi) {
1037                             break;
1038                         }
1039                         n = ((int)block[zptr[unHi]+d + 1]) - med;
1040                         if (n == 0) {
1041                             int temp = 0;
1042                             temp = zptr[unHi];
1043                             zptr[unHi] = zptr[gtHi];
1044                             zptr[gtHi] = temp;
1045                             gtHi--;
1046                             unHi--;
1047                             continue;
1048                         }
1049                         if (n <  0) {
1050                             break;
1051                         }
1052                         unHi--;
1053                     }
1054
1055                     if (unLo > unHi) {
1056                         break;
1057                     }
1058
1059                     {
1060                         int temp = zptr[unLo];
1061                         zptr[unLo] = zptr[unHi];
1062                         zptr[unHi] = temp;
1063                         unLo++;
1064                         unHi--;
1065                     }
1066                 }
1067
1068                 if (gtHi < ltLo) {
1069                     stack[sp].ll = lo;
1070                     stack[sp].hh = hi;
1071                     stack[sp].dd = d+1;
1072                     sp++;
1073                     continue;
1074                 }
1075
1076                 n = ((ltLo-lo) < (unLo-ltLo)) ? (ltLo-lo) : (unLo-ltLo);
1077                 Vswap(lo, unLo-n, n);
1078                 m = ((hi-gtHi) < (gtHi-unHi)) ? (hi-gtHi) : (gtHi-unHi);
1079                 Vswap(unLo, hi-m+1, m);
1080
1081                 n = lo + unLo - ltLo - 1;
1082                 m = hi - (gtHi - unHi) + 1;
1083
1084                 stack[sp].ll = lo;
1085                 stack[sp].hh = n;
1086                 stack[sp].dd = d;
1087                 sp++;
1088
1089                 stack[sp].ll = n + 1;
1090                 stack[sp].hh = m - 1;
1091                 stack[sp].dd = d+1;
1092                 sp++;
1093
1094                 stack[sp].ll = m;
1095                 stack[sp].hh = hi;
1096                 stack[sp].dd = d;
1097                 sp++;
1098             }
1099         }
1100
1101         void MainSort()
1102         {
1103             int i, j, ss, sb;
1104             int[] runningOrder = new int[256];
1105             int[] copy = new int[256];
1106             bool[] bigDone = new bool[256];
1107             int c1, c2;
1108             int numQSorted;
1109
1110             /*--
1111                         In the various block-sized structures, live data runs
1112                         from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
1113                         set up the overshoot area for block.
1114                         --*/
1115
1116             //   if (verbosity >= 4) fprintf ( stderr, "        sort initialise ...\n" );
1117             for (i = 0; i < BZip2Constants.NUM_OVERSHOOT_BYTES; i++) {
1118                 block[last + i + 2] = block[(i % (last + 1)) + 1];
1119             }
1120             for (i = 0; i <= last + BZip2Constants.NUM_OVERSHOOT_BYTES; i++) {
1121                 quadrant[i] = 0;
1122             }
1123
1124             block[0] = (byte)(block[last + 1]);
1125
1126             if (last < 4000) {
1127                 /*--
1128                                 Use simpleSort(), since the full sorting mechanism
1129                                 has quite a large constant overhead.
1130                                 --*/
1131                 for (i = 0; i <= last; i++) {
1132                     zptr[i] = i;
1133                 }
1134                 firstAttempt = false;
1135                 workDone = workLimit = 0;
1136                 SimpleSort(0, last, 0);
1137             } else {
1138                 numQSorted = 0;
1139                 for (i = 0; i <= 255; i++) {
1140                     bigDone[i] = false;
1141                 }
1142                 for (i = 0; i <= 65536; i++) {
1143                     ftab[i] = 0;
1144                 }
1145
1146                 c1 = block[0];
1147                 for (i = 0; i <= last; i++) {
1148                     c2 = block[i + 1];
1149                     ftab[(c1 << 8) + c2]++;
1150                     c1 = c2;
1151                 }
1152
1153                 for (i = 1; i <= 65536; i++) {
1154                     ftab[i] += ftab[i - 1];
1155                 }
1156
1157                 c1 = block[1];
1158                 for (i = 0; i < last; i++) {
1159                     c2 = block[i + 2];
1160                     j = (c1 << 8) + c2;
1161                     c1 = c2;
1162                     ftab[j]--;
1163                     zptr[ftab[j]] = i;
1164                 }
1165
1166                 j = ((block[last + 1]) << 8) + (block[1]);
1167                 ftab[j]--;
1168                 zptr[ftab[j]] = last;
1169
1170                 /*--
1171                                 Now ftab contains the first loc of every small bucket.
1172                                 Calculate the running order, from smallest to largest
1173                                 big bucket.
1174                                 --*/
1175
1176                 for (i = 0; i <= 255; i++) {
1177                     runningOrder[i] = i;
1178                 }
1179
1180                 int vv;
1181                 int h = 1;
1182                 do {
1183                     h = 3 * h + 1;
1184                 } while (h <= 256);
1185                 do {
1186                     h = h / 3;
1187                     for (i = h; i <= 255; i++) {
1188                         vv = runningOrder[i];
1189                         j = i;
1190                         while ((ftab[((runningOrder[j-h])+1) << 8] - ftab[(runningOrder[j-h]) << 8]) > (ftab[((vv)+1) << 8] - ftab[(vv) << 8])) {
1191                             runningOrder[j] = runningOrder[j-h];
1192                             j = j - h;
1193                             if (j <= (h - 1)) {
1194                                 break;
1195                             }
1196                         }
1197                         runningOrder[j] = vv;
1198                     }
1199                 } while (h != 1);
1200
1201                 /*--
1202                                 The main sorting loop.
1203                                 --*/
1204                 for (i = 0; i <= 255; i++) {
1205
1206                     /*--
1207                                         Process big buckets, starting with the least full.
1208                                         --*/
1209                     ss = runningOrder[i];
1210
1211                     /*--
1212                                         Complete the big bucket [ss] by quicksorting
1213                                         any unsorted small buckets [ss, j].  Hopefully
1214                                         previous pointer-scanning phases have already
1215                                         completed many of the small buckets [ss, j], so
1216                                         we don't have to sort them at all.
1217                                         --*/
1218                     for (j = 0; j <= 255; j++) {
1219                         sb = (ss << 8) + j;
1220                         if(!((ftab[sb] & SETMASK) == SETMASK)) {
1221                             int lo = ftab[sb] & CLEARMASK;
1222                             int hi = (ftab[sb+1] & CLEARMASK) - 1;
1223                             if (hi > lo) {
1224                                 QSort3(lo, hi, 2);
1225                                 numQSorted += (hi - lo + 1);
1226                                 if (workDone > workLimit && firstAttempt) {
1227                                     return;
1228                                 }
1229                             }
1230                             ftab[sb] |= SETMASK;
1231                         }
1232                     }
1233
1234                     /*--
1235                                         The ss big bucket is now done.  Record this fact,
1236                                         and update the quadrant descriptors.  Remember to
1237                                         update quadrants in the overshoot area too, if
1238                                         necessary.  The "if (i < 255)" test merely skips
1239                                         this updating for the last bucket processed, since
1240                                         updating for the last bucket is pointless.
1241                                         --*/
1242                     bigDone[ss] = true;
1243
1244                     if (i < 255) {
1245                         int bbStart  = ftab[ss << 8] & CLEARMASK;
1246                         int bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
1247                         int shifts   = 0;
1248
1249                         while ((bbSize >> shifts) > 65534) {
1250                             shifts++;
1251                         }
1252
1253                         for (j = 0; j < bbSize; j++) {
1254                             int a2update = zptr[bbStart + j];
1255                             int qVal = (j >> shifts);
1256                             quadrant[a2update] = qVal;
1257                             if (a2update < BZip2Constants.NUM_OVERSHOOT_BYTES) {
1258                                 quadrant[a2update + last + 1] = qVal;
1259                             }
1260                         }
1261
1262                         if (!(((bbSize-1) >> shifts) <= 65535)) {
1263                             Panic();
1264                         }
1265                     }
1266
1267                     /*--
1268                                         Now scan this big bucket so as to synthesise the
1269                                         sorted order for small buckets [t, ss] for all t != ss.
1270                                         --*/
1271                     for (j = 0; j <= 255; j++) {
1272                         copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
1273                     }
1274
1275                     for (j = ftab[ss << 8] & CLEARMASK; j < (ftab[(ss+1) << 8] & CLEARMASK); j++) {
1276                         c1 = block[zptr[j]];
1277                         if (!bigDone[c1]) {
1278                             zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
1279                             copy[c1] ++;
1280                         }
1281                     }
1282
1283                     for (j = 0; j <= 255; j++) {
1284                         ftab[(j << 8) + ss] |= SETMASK;
1285                     }
1286                 }
1287             }
1288         }
1289
1290         void RandomiseBlock()
1291         {
1292             int i;
1293             int rNToGo = 0;
1294             int rTPos  = 0;
1295             for (i = 0; i < 256; i++) {
1296                 inUse[i] = false;
1297             }
1298
1299             for (i = 0; i <= last; i++) {
1300                 if (rNToGo == 0) {
1301                     rNToGo = (int)BZip2Constants.rNums[rTPos];
1302                     rTPos++;
1303                     if (rTPos == 512) {
1304                         rTPos = 0;
1305                     }
1306                 }
1307                 rNToGo--;
1308                 block[i + 1] ^= (byte)((rNToGo == 1) ? 1 : 0);
1309                 // handle 16 bit signed numbers
1310                 block[i + 1] &= 0xFF;
1311
1312                 inUse[block[i + 1]] = true;
1313             }
1314         }
1315
1316         void DoReversibleTransformation()
1317         {
1318             workLimit = workFactor * last;
1319             workDone = 0;
1320             blockRandomised = false;
1321             firstAttempt = true;
1322
1323             MainSort();
1324
1325             if (workDone > workLimit && firstAttempt) {
1326                 RandomiseBlock();
1327                 workLimit = workDone = 0;
1328                 blockRandomised = true;
1329                 firstAttempt = false;
1330                 MainSort();
1331             }
1332
1333             origPtr = -1;
1334             for (int i = 0; i <= last; i++) {
1335                 if (zptr[i] == 0) {
1336                     origPtr = i;
1337                     break;
1338                 }
1339             }
1340
1341             if (origPtr == -1) {
1342                 Panic();
1343             }
1344         }
1345
1346         bool FullGtU(int i1, int i2)
1347         {
1348             int k;
1349             byte c1, c2;
1350             int s1, s2;
1351
1352             c1 = block[i1 + 1];
1353             c2 = block[i2 + 1];
1354             if (c1 != c2) {
1355                 return c1 > c2;
1356             }
1357             i1++;
1358             i2++;
1359
1360             c1 = block[i1 + 1];
1361             c2 = block[i2 + 1];
1362             if (c1 != c2) {
1363                 return c1 > c2;
1364             }
1365             i1++;
1366             i2++;
1367
1368             c1 = block[i1 + 1];
1369             c2 = block[i2 + 1];
1370             if (c1 != c2) {
1371                 return c1 > c2;
1372             }
1373             i1++;
1374             i2++;
1375
1376             c1 = block[i1 + 1];
1377             c2 = block[i2 + 1];
1378             if (c1 != c2) {
1379                 return c1 > c2;
1380             }
1381             i1++;
1382             i2++;
1383
1384             c1 = block[i1 + 1];
1385             c2 = block[i2 + 1];
1386             if (c1 != c2) {
1387                 return c1 > c2;
1388             }
1389             i1++;
1390             i2++;
1391
1392             c1 = block[i1 + 1];
1393             c2 = block[i2 + 1];
1394             if (c1 != c2) {
1395                 return c1 > c2;
1396             }
1397             i1++;
1398             i2++;
1399
1400             k = last + 1;
1401
1402             do {
1403                 c1 = block[i1 + 1];
1404                 c2 = block[i2 + 1];
1405                 if (c1 != c2) {
1406                     return c1 > c2;
1407                 }
1408                 s1 = quadrant[i1];
1409                 s2 = quadrant[i2];
1410                 if (s1 != s2) {
1411                     return s1 > s2;
1412                 }
1413                 i1++;
1414                 i2++;
1415
1416                 c1 = block[i1 + 1];
1417                 c2 = block[i2 + 1];
1418                 if (c1 != c2) {
1419                     return c1 > c2;
1420                 }
1421                 s1 = quadrant[i1];
1422                 s2 = quadrant[i2];
1423                 if (s1 != s2) {
1424                     return s1 > s2;
1425                 }
1426                 i1++;
1427                 i2++;
1428
1429                 c1 = block[i1 + 1];
1430                 c2 = block[i2 + 1];
1431                 if (c1 != c2) {
1432                     return c1 > c2;
1433                 }
1434                 s1 = quadrant[i1];
1435                 s2 = quadrant[i2];
1436                 if (s1 != s2) {
1437                     return s1 > s2;
1438                 }
1439                 i1++;
1440                 i2++;
1441
1442                 c1 = block[i1 + 1];
1443                 c2 = block[i2 + 1];
1444                 if (c1 != c2) {
1445                     return c1 > c2;
1446                 }
1447                 s1 = quadrant[i1];
1448                 s2 = quadrant[i2];
1449                 if (s1 != s2) {
1450                     return s1 > s2;
1451                 }
1452                 i1++;
1453                 i2++;
1454
1455                 if (i1 > last) {
1456                     i1 -= last;
1457                     i1--;
1458                 }
1459                 if (i2 > last) {
1460                     i2 -= last;
1461                     i2--;
1462                 }
1463
1464                 k -= 4;
1465                 ++workDone;
1466             } while (k >= 0);
1467
1468             return false;
1469         }
1470
1471         void AllocateCompressStructures()
1472         {
1473             int n = BZip2Constants.baseBlockSize * blockSize100k;
1474             block = new byte[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)];
1475             quadrant = new int[(n + BZip2Constants.NUM_OVERSHOOT_BYTES)];
1476             zptr = new int[n];
1477             ftab = new int[65537];
1478
1479             if (block == null || quadrant == null || zptr == null  || ftab == null) {
1480                 //              int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
1481                 //              compressOutOfMemory ( totalDraw, n );
1482             }
1483
1484             /*
1485                         The back end needs a place to store the MTF values
1486                         whilst it calculates the coding tables.  We could
1487                         put them in the zptr array.  However, these values
1488                         will fit in a short, so we overlay szptr at the
1489                         start of zptr, in the hope of reducing the number
1490                         of cache misses induced by the multiple traversals
1491                         of the MTF values when calculating coding tables.
1492                         Seems to improve compression speed by about 1%.
1493                         */
1494             //  szptr = zptr;
1495
1496
1497             szptr = new short[2 * n];
1498         }
1499
1500         void GenerateMTFValues()
1501         {
1502             char[] yy = new char[256];
1503             int  i, j;
1504             char tmp;
1505             char tmp2;
1506             int zPend;
1507             int wr;
1508             int EOB;
1509
1510             MakeMaps();
1511             EOB = nInUse+1;
1512
1513             for (i = 0; i <= EOB; i++) {
1514                 mtfFreq[i] = 0;
1515             }
1516
1517             wr = 0;
1518             zPend = 0;
1519             for (i = 0; i < nInUse; i++) {
1520                 yy[i] = (char) i;
1521             }
1522
1523
1524             for (i = 0; i <= last; i++) {
1525                 char ll_i;
1526
1527                 ll_i = unseqToSeq[block[zptr[i]]];
1528
1529                 j = 0;
1530                 tmp = yy[j];
1531                 while (ll_i != tmp) {
1532                     j++;
1533                     tmp2 = tmp;
1534                     tmp = yy[j];
1535                     yy[j] = tmp2;
1536                 }
1537                 yy[0] = tmp;
1538
1539                 if (j == 0) {
1540                     zPend++;
1541                 } else {
1542                     if (zPend > 0) {
1543                         zPend--;
1544                         while (true) {
1545                             switch (zPend % 2) {
1546                                 case 0:
1547                                     szptr[wr] = (short)BZip2Constants.RUNA;
1548                                     wr++;
1549                                     mtfFreq[BZip2Constants.RUNA]++;
1550                                     break;
1551                                 case 1:
1552                                     szptr[wr] = (short)BZip2Constants.RUNB;
1553                                     wr++;
1554                                     mtfFreq[BZip2Constants.RUNB]++;
1555                                     break;
1556                             }
1557                             if (zPend < 2) {
1558                                 break;
1559                             }
1560                             zPend = (zPend - 2) / 2;
1561                         }
1562                         zPend = 0;
1563                     }
1564                     szptr[wr] = (short)(j + 1);
1565                     wr++;
1566                     mtfFreq[j + 1]++;
1567                 }
1568             }
1569
1570             if (zPend > 0) {
1571                 zPend--;
1572                 while (true) {
1573                     switch (zPend % 2) {
1574                         case 0:
1575                             szptr[wr] = (short)BZip2Constants.RUNA;
1576                             wr++;
1577                             mtfFreq[BZip2Constants.RUNA]++;
1578                             break;
1579                         case 1:
1580                             szptr[wr] = (short)BZip2Constants.RUNB;
1581                             wr++;
1582                             mtfFreq[BZip2Constants.RUNB]++;
1583                             break;
1584                     }
1585                     if (zPend < 2) {
1586                         break;
1587                     }
1588                     zPend = (zPend - 2) / 2;
1589                 }
1590             }
1591
1592             szptr[wr] = (short)EOB;
1593             wr++;
1594             mtfFreq[EOB]++;
1595
1596             nMTF = wr;
1597         }
1598
1599         static void Panic()
1600         {
1601             throw new BZip2Exception("BZip2 output stream panic");
1602         }
1603
1604         static void HbMakeCodeLengths(char[] len, int[] freq, int alphaSize, int maxLen)
1605         {
1606             /*--
1607                         Nodes and heap entries run from 1.  Entry 0
1608                         for both the heap and nodes is a sentinel.
1609                         --*/
1610             int nNodes, nHeap, n1, n2, j, k;
1611             bool  tooLong;
1612
1613             int[] heap   = new int[BZip2Constants.MAX_ALPHA_SIZE + 2];
1614             int[] weight = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];
1615             int[] parent = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];
1616
1617             for (int i = 0; i < alphaSize; ++i)
1618             {
1619                 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
1620             }
1621
1622             while (true)
1623             {
1624                 nNodes = alphaSize;
1625                 nHeap = 0;
1626
1627                 heap[0] = 0;
1628                 weight[0] = 0;
1629                 parent[0] = -2;
1630
1631                 for (int i = 1; i <= alphaSize; ++i)
1632                 {
1633                     parent[i] = -1;
1634                     nHeap++;
1635                     heap[nHeap] = i;
1636                     int zz = nHeap;
1637                     int tmp = heap[zz];
1638                     while (weight[tmp] < weight[heap[zz >> 1]])
1639                     {
1640                         heap[zz] = heap[zz >> 1];
1641                         zz >>= 1;
1642                     }
1643                     heap[zz] = tmp;
1644                 }
1645                 if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE+2)))
1646                 {
1647                     Panic();
1648                 }
1649
1650                 while (nHeap > 1)
1651                 {
1652                     n1 = heap[1];
1653                     heap[1] = heap[nHeap];
1654                     nHeap--;
1655                     int zz = 1;
1656                     int yy = 0;
1657                     int tmp = heap[zz];
1658                     while (true)
1659                     {
1660                         yy = zz << 1;
1661                         if (yy > nHeap)
1662                         {
1663                             break;
1664                         }
1665                         if (yy < nHeap &&  weight[heap[yy+1]] < weight[heap[yy]])
1666                         {
1667                             yy++;
1668                         }
1669                         if (weight[tmp] < weight[heap[yy]])
1670                         {
1671                             break;
1672                         }
1673
1674                         heap[zz] = heap[yy];
1675                         zz = yy;
1676                     }
1677                     heap[zz] = tmp;
1678                     n2 = heap[1];
1679                     heap[1] = heap[nHeap];
1680                     nHeap--;
1681
1682                     zz = 1;
1683                     yy = 0;
1684                     tmp = heap[zz];
1685                     while (true)
1686                     {
1687                         yy = zz << 1;
1688                         if (yy > nHeap)
1689                         {
1690                             break;
1691                         }
1692                         if (yy < nHeap && weight[heap[yy+1]] < weight[heap[yy]])
1693                         {
1694                             yy++;
1695                         }
1696                         if (weight[tmp] < weight[heap[yy]])
1697                         {
1698                             break;
1699                         }
1700                         heap[zz] = heap[yy];
1701                         zz = yy;
1702                     }
1703                     heap[zz] = tmp;
1704                     nNodes++;
1705                     parent[n1] = parent[n2] = nNodes;
1706
1707                     weight[nNodes] = (int)((weight[n1] & 0xffffff00) + (weight[n2] & 0xffffff00)) |
1708                                      (int)(1 + (((weight[n1] & 0x000000ff) > (weight[n2] & 0x000000ff)) ? (weight[n1] & 0x000000ff) : (weight[n2] & 0x000000ff)));
1709
1710                     parent[nNodes] = -1;
1711                     nHeap++;
1712                     heap[nHeap] = nNodes;
1713
1714                     zz  = nHeap;
1715                     tmp = heap[zz];
1716                     while (weight[tmp] < weight[heap[zz >> 1]])
1717                     {
1718                         heap[zz] = heap[zz >> 1];
1719                         zz >>= 1;
1720                     }
1721                     heap[zz] = tmp;
1722                 }
1723                 if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2)))
1724                 {
1725                     Panic();
1726                 }
1727
1728                 tooLong = false;
1729                 for (int i = 1; i <= alphaSize; ++i)
1730                 {
1731                     j = 0;
1732                     k = i;
1733                     while (parent[k] >= 0)
1734                     {
1735                         k = parent[k];
1736                         j++;
1737                     }
1738                     len[i - 1] = (char)j;
1739                     if (j > maxLen)
1740                     {
1741                         tooLong = true;
1742                     }
1743                 }
1744
1745                 if (!tooLong)
1746                 {
1747                     break;
1748                 }
1749
1750                 for (int i = 1; i < alphaSize; ++i)
1751                 {
1752                     j = weight[i] >> 8;
1753                     j = 1 + (j / 2);
1754                     weight[i] = j << 8;
1755                 }
1756             }
1757         }
1758
1759         static void HbAssignCodes (int[] code, char[] length, int minLen, int maxLen, int alphaSize)
1760         {
1761             int vec = 0;
1762             for (int n = minLen; n <= maxLen; ++n)
1763             {
1764                 for (int i = 0; i < alphaSize; ++i)
1765                 {
1766                     if (length[i] == n)
1767                     {
1768                         code[i] = vec;
1769                         ++vec;
1770                     }
1771                 }
1772                 vec <<= 1;
1773             }
1774         }
1775
1776         static byte Med3(byte a, byte b, byte c )
1777         {
1778             byte t;
1779             if (a > b)
1780             {
1781                 t = a;
1782                 a = b;
1783                 b = t;
1784             }
1785             if (b > c)
1786             {
1787                 t = b;
1788                 b = c;
1789                 c = t;
1790             }
1791             if (a > b)
1792             {
1793                 b = a;
1794             }
1795             return b;
1796         }
1797
1798         class StackElement
1799         {
1800             public int ll;
1801             public int hh;
1802             public int dd;
1803         }
1804
1805         #region Instance Fields
1806         bool isStreamOwner = true;
1807
1808         /*--
1809                 index of the last char in the block, so
1810                 the block size == last + 1.
1811                 --*/
1812         int last;
1813
1814         /*--
1815                 index in zptr[] of original string after sorting.
1816                 --*/
1817         int origPtr;
1818
1819         /*--
1820                 always: in the range 0 .. 9.
1821                 The current block size is 100000 * this number.
1822                 --*/
1823         int blockSize100k;
1824
1825         bool blockRandomised;
1826
1827         int bytesOut;
1828         int bsBuff;
1829         int bsLive;
1830         IChecksum mCrc = new StrangeCRC();
1831
1832         bool[] inUse = new bool[256];
1833         int nInUse;
1834
1835         char[] seqToUnseq = new char[256];
1836         char[] unseqToSeq = new char[256];
1837
1838         char[] selector = new char[BZip2Constants.MAX_SELECTORS];
1839         char[] selectorMtf = new char[BZip2Constants.MAX_SELECTORS];
1840
1841         byte[]  block;
1842         int[]   quadrant;
1843         int[]   zptr;
1844         short[] szptr;
1845         int[]   ftab;
1846
1847         int nMTF;
1848
1849         int[] mtfFreq = new int[BZip2Constants.MAX_ALPHA_SIZE];
1850
1851         /*
1852                 * Used when sorting.  If too many long comparisons
1853                 * happen, we stop sorting, randomise the block
1854                 * slightly, and try again.
1855                 */
1856         int workFactor;
1857         int workDone;
1858         int workLimit;
1859         bool firstAttempt;
1860         int nBlocksRandomised;
1861
1862         int currentChar = -1;
1863         int runLength;
1864         uint blockCRC, combinedCRC;
1865         int allowableBlockSize;
1866         Stream baseStream;
1867         bool disposed_;
1868         #endregion
1869     }
1870 }
1871
1872 /* This file was derived from a file containing this license:
1873  *
1874  * This file is a part of bzip2 and/or libbzip2, a program and
1875  * library for lossless, block-sorting data compression.
1876  *
1877  * Copyright (C) 1996-1998 Julian R Seward.  All rights reserved.
1878  *
1879  * Redistribution and use in source and binary forms, with or without
1880  * modification, are permitted provided that the following conditions
1881  * are met:
1882  *
1883  * 1. Redistributions of source code must retain the above copyright
1884  * notice, this list of conditions and the following disclaimer.
1885  *
1886  * 2. The origin of this software must not be misrepresented; you must
1887  * not claim that you wrote the original software.  If you use this
1888  * software in a product, an acknowledgment in the product
1889  * documentation would be appreciated but is not required.
1890  *
1891  * 3. Altered source versions must be plainly marked as such, and must
1892  * not be misrepresented as being the original software.
1893  *
1894  * 4. The name of the author may not be used to endorse or promote
1895  * products derived from this software without specific prior written
1896  * permission.
1897  *
1898  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
1899  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
1900  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1901  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
1902  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1903  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
1904  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1905  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
1906  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1907  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1908  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1909  *
1910  * Java version ported by Keiron Liddle, Aftex Software <keiron@aftexsw.com> 1999-2001
1911  */