irc/TechBot/Compression/DeflaterEngine.cs

   1 // DeflaterEngine.cs
   2 // Copyright (C) 2001 Mike Krueger
   3 //
   4 // This file was translated from java, it was part of the GNU Classpath
   5 // Copyright (C) 2001 Free Software Foundation, Inc.
   6 //
   7 // This program is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU General Public License
   9 // as published by the Free Software Foundation; either version 2
  10 // of the License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this program; if not, write to the Free Software
  19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20 //
  21 // Linking this library statically or dynamically with other modules is
  22 // making a combined work based on this library.  Thus, the terms and
  23 // conditions of the GNU General Public License cover the whole
  24 // combination.
  25 //
  26 // As a special exception, the copyright holders of this library give you
  27 // permission to link this library with independent modules to produce an
  28 // executable, regardless of the license terms of these independent
  29 // modules, and to copy and distribute the resulting executable under
  30 // terms of your choice, provided that you also meet, for each linked
  31 // independent module, the terms and conditions of the license of that
  32 // module.  An independent module is a module which is not derived from
  33 // or based on this library.  If you modify this library, you may extend
  34 // this exception to your version of the library, but you are not
  35 // obligated to do so.  If you do not wish to do so, delete this
  36 // exception statement from your version.
  37
  38 using System;
  39
  40 using ICSharpCode.SharpZipLib.Checksums;
  41
  42 namespace ICSharpCode.SharpZipLib.Zip.Compression
  43 {
  44
  45         public enum DeflateStrategy
  46         {
  47                 // The default strategy.
  48                 Default  = 0,
  49
  50                 // This strategy will only allow longer string repetitions.  It is
  51                 // useful for random data with a small character set.
  52                 Filtered = 1,
  53
  54                 // This strategy will not look for string repetitions at all.  It
  55                 // only encodes with Huffman trees (which means, that more common
  56                 // characters get a smaller encoding.
  57                 HuffmanOnly = 2
  58         }
  59
  60         public class DeflaterEngine : DeflaterConstants
  61         {
  62                 static int TOO_FAR = 4096;
  63
  64                 int ins_h;
  65                 //              private byte[] buffer;
  66                 short[] head;
  67                 short[] prev;
  68
  69                 int    matchStart, matchLen;
  70                 bool   prevAvailable;
  71                 int    blockStart;
  72                 int    strstart, lookahead;
  73                 byte[] window;
  74
  75                 DeflateStrategy strategy;
  76                 int max_chain, max_lazy, niceLength, goodLength;
  77
  78                 /// <summary>
  79                 /// The current compression function.
  80                 /// </summary>
  81                 int comprFunc;
  82
  83                 /// <summary>
  84                 /// The input data for compression.
  85                 /// </summary>
  86                 byte[] inputBuf;
  87
  88                 /// <summary>
  89                 /// The total bytes of input read.
  90                 /// </summary>
  91                 int totalIn;
  92
  93                 /// <summary>
  94                 /// The offset into inputBuf, where input data starts.
  95                 /// </summary>
  96                 int inputOff;
  97
  98                 /// <summary>
  99                 /// The end offset of the input data.
 100                 /// </summary>
 101                 int inputEnd;
 102
 103                 DeflaterPending pending;
 104                 DeflaterHuffman huffman;
 105
 106                 /// <summary>
 107                 /// The adler checksum
 108                 /// </summary>
 109                 Adler32 adler;
 110
 111                 public DeflaterEngine(DeflaterPending pending)
 112                 {
 113                         this.pending = pending;
 114                         huffman = new DeflaterHuffman(pending);
 115                         adler = new Adler32();
 116
 117                         window = new byte[2 * WSIZE];
 118                         head   = new short[HASH_SIZE];
 119                         prev   = new short[WSIZE];
 120
 121                         /* We start at index 1, to avoid a implementation deficiency, that
 122                         * we cannot build a repeat pattern at index 0.
 123                         */
 124                         blockStart = strstart = 1;
 125                 }
 126
 127                 public void Reset()
 128                 {
 129                         huffman.Reset();
 130                         adler.Reset();
 131                         blockStart = strstart = 1;
 132                         lookahead = 0;
 133                         totalIn   = 0;
 134                         prevAvailable = false;
 135                         matchLen = MIN_MATCH - 1;
 136
 137                         for (int i = 0; i < HASH_SIZE; i++) {
 138                                 head[i] = 0;
 139                         }
 140
 141                         for (int i = 0; i < WSIZE; i++) {
 142                                 prev[i] = 0;
 143                         }
 144                 }
 145
 146                 public void ResetAdler()
 147                 {
 148                         adler.Reset();
 149                 }
 150
 151                 public int Adler {
 152                         get {
 153                                 return (int)adler.Value;
 154                         }
 155                 }
 156
 157                 public int TotalIn {
 158                         get {
 159                                 return totalIn;
 160                         }
 161                 }
 162
 163                 public DeflateStrategy Strategy {
 164                         get {
 165                                 return strategy;
 166                         }
 167                         set {
 168                                 strategy = value;
 169                         }
 170                 }
 171
 172                 public void SetLevel(int lvl)
 173                 {
 174                         goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
 175                         max_lazy   = DeflaterConstants.MAX_LAZY[lvl];
 176                         niceLength = DeflaterConstants.NICE_LENGTH[lvl];
 177                         max_chain  = DeflaterConstants.MAX_CHAIN[lvl];
 178
 179                         if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
 180                                 //                              if (DeflaterConstants.DEBUGGING) {
 181                                 //                                      //Console.WriteLine("Change from "+comprFunc +" to "
 182                                 //                                                        + DeflaterConstants.COMPR_FUNC[lvl]);
 183                                 //                              }
 184                                 switch (comprFunc) {
 185                                         case DEFLATE_STORED:
 186                                                 if (strstart > blockStart) {
 187                                                         huffman.FlushStoredBlock(window, blockStart,
 188                                                                 strstart - blockStart, false);
 189                                                         blockStart = strstart;
 190                                                 }
 191                                                 UpdateHash();
 192                                                 break;
 193                                         case DEFLATE_FAST:
 194                                                 if (strstart > blockStart) {
 195                                                         huffman.FlushBlock(window, blockStart, strstart - blockStart,
 196                                                                 false);
 197                                                         blockStart = strstart;
 198                                                 }
 199                                                 break;
 200                                         case DEFLATE_SLOW:
 201                                                 if (prevAvailable) {
 202                                                         huffman.TallyLit(window[strstart-1] & 0xff);
 203                                                 }
 204                                                 if (strstart > blockStart) {
 205                                                         huffman.FlushBlock(window, blockStart, strstart - blockStart, false);
 206                                                         blockStart = strstart;
 207                                                 }
 208                                                 prevAvailable = false;
 209                                                 matchLen = MIN_MATCH - 1;
 210                                                 break;
 211                                 }
 212                                 comprFunc = COMPR_FUNC[lvl];
 213                         }
 214                 }
 215
 216                 void UpdateHash()
 217                 {
 218                         //                      if (DEBUGGING) {
 219                         //                              //Console.WriteLine("updateHash: "+strstart);
 220                         //                      }
 221                         ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
 222                 }
 223
 224                 int InsertString()
 225                 {
 226                         short match;
 227                         int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
 228
 229                         //                      if (DEBUGGING) {
 230                         //                              if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
 231                         //                                            (window[strstart + 1] << HASH_SHIFT) ^
 232                         //                                            (window[strstart + 2])) & HASH_MASK)) {
 233                         //                                              throw new Exception("hash inconsistent: "+hash+"/"
 234                         //                                                                  +window[strstart]+","
 235                         //                                                                  +window[strstart+1]+","
 236                         //                                                                  +window[strstart+2]+","+HASH_SHIFT);
 237                         //                                      }
 238                         //                      }
 239
 240                         prev[strstart & WMASK] = match = head[hash];
 241                         head[hash] = (short)strstart;
 242                         ins_h = hash;
 243                         return match & 0xffff;
 244                 }
 245
 246                 void SlideWindow()
 247                 {
 248                         Array.Copy(window, WSIZE, window, 0, WSIZE);
 249                         matchStart -= WSIZE;
 250                         strstart   -= WSIZE;
 251                         blockStart -= WSIZE;
 252
 253                         /* Slide the hash table (could be avoided with 32 bit values
 254                          * at the expense of memory usage).
 255                          */
 256                         for (int i = 0; i < HASH_SIZE; ++i) {
 257                                 int m = head[i] & 0xffff;
 258                                 head[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
 259                         }
 260
 261                         /* Slide the prev table. */
 262                         for (int i = 0; i < WSIZE; i++) {
 263                                 int m = prev[i] & 0xffff;
 264                                 prev[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
 265                         }
 266                 }
 267
 268                 public void FillWindow()
 269                 {
 270                         /* If the window is almost full and there is insufficient lookahead,
 271                          * move the upper half to the lower one to make room in the upper half.
 272                          */
 273                         if (strstart >= WSIZE + MAX_DIST) {
 274                                 SlideWindow();
 275                         }
 276
 277                         /* If there is not enough lookahead, but still some input left,
 278                          * read in the input
 279                          */
 280                         while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
 281                                 int more = 2 * WSIZE - lookahead - strstart;
 282
 283                                 if (more > inputEnd - inputOff) {
 284                                         more = inputEnd - inputOff;
 285                                 }
 286
 287                                 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
 288                                 adler.Update(inputBuf, inputOff, more);
 289
 290                                 inputOff += more;
 291                                 totalIn  += more;
 292                                 lookahead += more;
 293                         }
 294
 295                         if (lookahead >= MIN_MATCH) {
 296                                 UpdateHash();
 297                         }
 298                 }
 299
 300                 bool FindLongestMatch(int curMatch)
 301                 {
 302                         int chainLength = this.max_chain;
 303                         int niceLength  = this.niceLength;
 304                         short[] prev    = this.prev;
 305                         int scan        = this.strstart;
 306                         int match;
 307                         int best_end = this.strstart + matchLen;
 308                         int best_len = Math.Max(matchLen, MIN_MATCH - 1);
 309
 310                         int limit = Math.Max(strstart - MAX_DIST, 0);
 311
 312                         int strend = strstart + MAX_MATCH - 1;
 313                         byte scan_end1 = window[best_end - 1];
 314                         byte scan_end  = window[best_end];
 315
 316                         /* Do not waste too much time if we already have a good match: */
 317                         if (best_len >= this.goodLength) {
 318                                 chainLength >>= 2;
 319                         }
 320
 321                         /* Do not look for matches beyond the end of the input. This is necessary
 322                         * to make deflate deterministic.
 323                         */
 324                         if (niceLength > lookahead) {
 325                                 niceLength = lookahead;
 326                         }
 327
 328                         if (DeflaterConstants.DEBUGGING && strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
 329                                 throw new InvalidOperationException("need lookahead");
 330                         }
 331
 332                         do {
 333                                 if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
 334                                         throw new InvalidOperationException("future match");
 335                                 }
 336                                 if (window[curMatch + best_len] != scan_end      ||
 337                                         window[curMatch + best_len - 1] != scan_end1 ||
 338                                         window[curMatch] != window[scan]             ||
 339                                         window[curMatch + 1] != window[scan + 1]) {
 340                                         continue;
 341                                 }
 342
 343                                 match = curMatch + 2;
 344                                 scan += 2;
 345
 346                                 /* We check for insufficient lookahead only every 8th comparison;
 347                                 * the 256th check will be made at strstart+258.
 348                                 */
 349                         while (window[++scan] == window[++match] &&
 350                                 window[++scan] == window[++match] &&
 351                                 window[++scan] == window[++match] &&
 352                                 window[++scan] == window[++match] &&
 353                                 window[++scan] == window[++match] &&
 354                                 window[++scan] == window[++match] &&
 355                                 window[++scan] == window[++match] &&
 356                                 window[++scan] == window[++match] && scan < strend) ;
 357
 358                                 if (scan > best_end) {
 359                                         //      if (DeflaterConstants.DEBUGGING && ins_h == 0)
 360                                         //        System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
 361                                         matchStart = curMatch;
 362                                         best_end = scan;
 363                                         best_len = scan - strstart;
 364
 365                                         if (best_len >= niceLength) {
 366                                                 break;
 367                                         }
 368
 369                                         scan_end1  = window[best_end - 1];
 370                                         scan_end   = window[best_end];
 371                                 }
 372                                 scan = strstart;
 373                         } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
 374
 375                         matchLen = Math.Min(best_len, lookahead);
 376                         return matchLen >= MIN_MATCH;
 377                 }
 378
 379                 public void SetDictionary(byte[] buffer, int offset, int length)
 380                 {
 381                         if (DeflaterConstants.DEBUGGING && strstart != 1) {
 382                                 throw new InvalidOperationException("strstart not 1");
 383                         }
 384                         adler.Update(buffer, offset, length);
 385                         if (length < MIN_MATCH) {
 386                                 return;
 387                         }
 388                         if (length > MAX_DIST) {
 389                                 offset += length - MAX_DIST;
 390                                 length = MAX_DIST;
 391                         }
 392
 393                         System.Array.Copy(buffer, offset, window, strstart, length);
 394
 395                         UpdateHash();
 396                         --length;
 397                         while (--length > 0) {
 398                                 InsertString();
 399                                 strstart++;
 400                         }
 401                         strstart += 2;
 402                         blockStart = strstart;
 403                 }
 404
 405                 bool DeflateStored(bool flush, bool finish)
 406                 {
 407                         if (!flush && lookahead == 0) {
 408                                 return false;
 409                         }
 410
 411                         strstart += lookahead;
 412                         lookahead = 0;
 413
 414                         int storedLen = strstart - blockStart;
 415
 416                         if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
 417                                 (blockStart < WSIZE && storedLen >= MAX_DIST) ||   /* Block may move out of window */
 418                                 flush) {
 419                                 bool lastBlock = finish;
 420                                 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
 421                                         storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
 422                                         lastBlock = false;
 423                                 }
 424
 425                                 //                              if (DeflaterConstants.DEBUGGING) {
 426                                 //                                      //Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
 427                                 //                              }
 428
 429                                 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
 430                                 blockStart += storedLen;
 431                                 return !lastBlock;
 432                         }
 433                         return true;
 434                 }
 435
 436                 private bool DeflateFast(bool flush, bool finish)
 437                 {
 438                         if (lookahead < MIN_LOOKAHEAD && !flush) {
 439                                 return false;
 440                         }
 441
 442                         while (lookahead >= MIN_LOOKAHEAD || flush) {
 443                                 if (lookahead == 0) {
 444                                         /* We are flushing everything */
 445                                         huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
 446                                         blockStart = strstart;
 447                                         return false;
 448                                 }
 449
 450                                 if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
 451                                         /* slide window, as findLongestMatch need this.
 452                                          * This should only happen when flushing and the window
 453                                          * is almost full.
 454                                          */
 455                                         SlideWindow();
 456                                 }
 457
 458                                 int hashHead;
 459                                 if (lookahead >= MIN_MATCH &&
 460                                         (hashHead = InsertString()) != 0 &&
 461                                         strategy != DeflateStrategy.HuffmanOnly &&
 462                                         strstart - hashHead <= MAX_DIST &&
 463                                         FindLongestMatch(hashHead)) {
 464                                         /* longestMatch sets matchStart and matchLen */
 465                                         //                                      if (DeflaterConstants.DEBUGGING) {
 466                                         //                                              for (int i = 0 ; i < matchLen; i++) {
 467                                         //                                                      if (window[strstart+i] != window[matchStart + i]) {
 468                                         //                                                              throw new Exception();
 469                                         //                                                      }
 470                                         //                                              }
 471                                         //                                      }
 472
 473                                         // -jr- Hak hak hak this stops problems with fast/low compression and index out of range
 474                                         if (huffman.TallyDist(strstart - matchStart, matchLen)) {
 475                                                 bool lastBlock = finish && lookahead == 0;
 476                                                 huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
 477                                                 blockStart = strstart;
 478                                         }
 479
 480                                         lookahead -= matchLen;
 481                                         if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
 482                                                 while (--matchLen > 0) {
 483                                                         ++strstart;
 484                                                         InsertString();
 485                                                 }
 486                                                 ++strstart;
 487                                         } else {
 488                                                 strstart += matchLen;
 489                                                 if (lookahead >= MIN_MATCH - 1) {
 490                                                         UpdateHash();
 491                                                 }
 492                                         }
 493                                         matchLen = MIN_MATCH - 1;
 494                                         continue;
 495                                 } else {
 496                                         /* No match found */
 497                                         huffman.TallyLit(window[strstart] & 0xff);
 498                                         ++strstart;
 499                                         --lookahead;
 500                                 }
 501
 502                                 if (huffman.IsFull()) {
 503                                         bool lastBlock = finish && lookahead == 0;
 504                                         huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
 505                                         blockStart = strstart;
 506                                         return !lastBlock;
 507                                 }
 508                         }
 509                         return true;
 510                 }
 511
 512                 bool DeflateSlow(bool flush, bool finish)
 513                 {
 514                         if (lookahead < MIN_LOOKAHEAD && !flush) {
 515                                 return false;
 516                         }
 517
 518                         while (lookahead >= MIN_LOOKAHEAD || flush) {
 519                                 if (lookahead == 0) {
 520                                         if (prevAvailable) {
 521                                                 huffman.TallyLit(window[strstart-1] & 0xff);
 522                                         }
 523                                         prevAvailable = false;
 524
 525                                         /* We are flushing everything */
 526                                         if (DeflaterConstants.DEBUGGING && !flush) {
 527                                                 throw new Exception("Not flushing, but no lookahead");
 528                                         }
 529                                         huffman.FlushBlock(window, blockStart, strstart - blockStart,
 530                                                 finish);
 531                                         blockStart = strstart;
 532                                         return false;
 533                                 }
 534
 535                                 if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) {
 536                                         /* slide window, as findLongestMatch need this.
 537                                          * This should only happen when flushing and the window
 538                                          * is almost full.
 539                                          */
 540                                         SlideWindow();
 541                                 }
 542
 543                                 int prevMatch = matchStart;
 544                                 int prevLen = matchLen;
 545                                 if (lookahead >= MIN_MATCH) {
 546                                         int hashHead = InsertString();
 547                                         if (strategy != DeflateStrategy.HuffmanOnly && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead)) {
 548                                                 /* longestMatch sets matchStart and matchLen */
 549
 550                                                 /* Discard match if too small and too far away */
 551                                                 if (matchLen <= 5 && (strategy == DeflateStrategy.Filtered || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
 552                                                         matchLen = MIN_MATCH - 1;
 553                                                 }
 554                                         }
 555                                 }
 556
 557                                 /* previous match was better */
 558                                 if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
 559                                         //                                      if (DeflaterConstants.DEBUGGING) {
 560                                         //                                              for (int i = 0 ; i < matchLen; i++) {
 561                                         //                                                      if (window[strstart-1+i] != window[prevMatch + i])
 562                                         //                                                              throw new Exception();
 563                                         //                                              }
 564                                         //                                      }
 565                                         huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
 566                                         prevLen -= 2;
 567                                         do {
 568                                                 strstart++;
 569                                                 lookahead--;
 570                                                 if (lookahead >= MIN_MATCH) {
 571                                                         InsertString();
 572                                                 }
 573                                         } while (--prevLen > 0);
 574                                         strstart ++;
 575                                         lookahead--;
 576                                         prevAvailable = false;
 577                                         matchLen = MIN_MATCH - 1;
 578                                 } else {
 579                                         if (prevAvailable) {
 580                                                 huffman.TallyLit(window[strstart-1] & 0xff);
 581                                         }
 582                                         prevAvailable = true;
 583                                         strstart++;
 584                                         lookahead--;
 585                                 }
 586
 587                                 if (huffman.IsFull()) {
 588                                         int len = strstart - blockStart;
 589                                         if (prevAvailable) {
 590                                                 len--;
 591                                         }
 592                                         bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
 593                                         huffman.FlushBlock(window, blockStart, len, lastBlock);
 594                                         blockStart += len;
 595                                         return !lastBlock;
 596                                 }
 597                         }
 598                         return true;
 599                 }
 600
 601                 public bool Deflate(bool flush, bool finish)
 602                 {
 603                         bool progress;
 604                         do {
 605                                 FillWindow();
 606                                 bool canFlush = flush && inputOff == inputEnd;
 607                                 //                              if (DeflaterConstants.DEBUGGING) {
 608                                 //                                      //Console.WriteLine("window: ["+blockStart+","+strstart+","
 609                                 //                                                        +lookahead+"], "+comprFunc+","+canFlush);
 610                                 //                              }
 611                                 switch (comprFunc) {
 612                                         case DEFLATE_STORED:
 613                                                 progress = DeflateStored(canFlush, finish);
 614                                                 break;
 615                                         case DEFLATE_FAST:
 616                                                 progress = DeflateFast(canFlush, finish);
 617                                                 break;
 618                                         case DEFLATE_SLOW:
 619                                                 progress = DeflateSlow(canFlush, finish);
 620                                                 break;
 621                                         default:
 622                                                 throw new InvalidOperationException("unknown comprFunc");
 623                                 }
 624                         } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
 625                         return progress;
 626                 }
 627
 628                 public void SetInput(byte[] buf, int off, int len)
 629                 {
 630                         if (inputOff < inputEnd) {
 631                                 throw new InvalidOperationException("Old input was not completely processed");
 632                         }
 633
 634                         int end = off + len;
 635
 636                         /* We want to throw an ArrayIndexOutOfBoundsException early.  The
 637                         * check is very tricky: it also handles integer wrap around.
 638                         */
 639                         if (0 > off || off > end || end > buf.Length) {
 640                                 throw new ArgumentOutOfRangeException();
 641                         }
 642
 643                         inputBuf = buf;
 644                         inputOff = off;
 645                         inputEnd = end;
 646                 }
 647
 648                 public bool NeedsInput()
 649                 {
 650                         return inputEnd == inputOff;
 651                 }
 652         }
 653 }