mcs/class/Compat.ICSharpCode.SharpZipLib/ICSharpCode.SharpZipLib/Zip/Compression/DeflaterEngine.cs

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