bundles/org.simantics.fastlz/src/org/simantics/fastlz/java/FastLZImpl.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2011 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.fastlz.java;
  13
  14
  15 /**
  16  * @author Tuukka Lehtonen
  17  */
  18 public class FastLZImpl {
  19
  20     /** 256 + 8 */
  21     private static final int     MAX_LEN                 = 264;
  22     private static final int     MAX_COPY                = 32;
  23     // For level 1 compression
  24     private static final int     MAX_DISTANCE            = 8192;
  25     // For level 2 compression
  26     private static final int     MAX_DISTANCE2           = 8191;
  27     private static final int     MAX_FARDISTANCE         = (65535 + MAX_DISTANCE2 - 1);
  28
  29     private static final boolean FASTLZ_SAFE             = false;
  30
  31     public static final int      FASTLZ_VERSION          = 0x000100;
  32
  33     public static final int      FASTLZ_VERSION_MAJOR    = 0;
  34     public static final int      FASTLZ_VERSION_MINOR    = 1;
  35     public static final int      FASTLZ_VERSION_REVISION = 0;
  36
  37     public static final String   FASTLZ_VERSION_STRING   = "0.1.0";
  38
  39     private static final int     HASH_LOG                = 13;
  40     private static final int     HASH_SIZE               = (1 << HASH_LOG);
  41     private static final int     HASH_MASK               = (HASH_SIZE - 1);
  42
  43     private static final int FASTLZ_READU16(byte[] array, int offset) {
  44         final int b0 = array[offset] & 0xff;
  45         final int b1 = array[offset + 1] & 0xff;
  46         return b0 | (b1 << 8);
  47     }
  48
  49     /**
  50      * @param array
  51      * @param offset
  52      * @return
  53      */
  54     private static final int HASH_FUNCTION(byte[] array, int offset) {
  55         final int b0 = array[offset] & 0xff;
  56         final int b1 = array[offset+1] & 0xff;
  57         final int b2 = array[offset+2] & 0xff;
  58         int v = b0 | (b1 << 8);
  59         final int v2 = b1 | (b2 << 8);
  60         v ^= v2 ^ (v >>> (16 - HASH_LOG));
  61         v &= HASH_MASK;
  62         return v;
  63     }
  64
  65     /**
  66       Compress a block of data in the input buffer and returns the size of
  67       compressed block. The size of input buffer is specified by length. The
  68       minimum input buffer size is 16.
  69
  70       The output buffer must be at least 5% larger than the input buffer
  71       and can not be smaller than 66 bytes.
  72
  73       If the input is not compressible, the return value might be larger than
  74       length (input buffer size).
  75
  76       The input buffer and the output buffer can not overlap.
  77     */
  78     public static int fastlz_compress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset) {
  79         /* for short block, choose fastlz1 */
  80         if (length < 65536)
  81           return fastlz1_compress(input, inputOffset, length, output, outputOffset);
  82
  83         /* else... */
  84         return fastlz2_compress(input, inputOffset, length, output, outputOffset);
  85     }
  86
  87     /**
  88       Decompress a block of compressed data and returns the size of the
  89       decompressed block. If error occurs, e.g. the compressed data is
  90       corrupted or the output buffer is not large enough, then 0 (zero)
  91       will be returned instead.
  92
  93       The input buffer and the output buffer can not overlap.
  94
  95       Decompression is memory safe and guaranteed not to write the output buffer
  96       more than what is specified in maxout.
  97      */
  98     public static int fastlz_decompress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset,
  99             int maxout) {
 100         // magic identifier for compression level
 101         int level = (((int) input[0] & 0xff) >>> 5) + 1;
 102
 103         if (level == 1)
 104           return fastlz1_decompress(input, inputOffset, length, output, outputOffset, maxout);
 105         if (level == 2)
 106           return fastlz2_decompress(input, inputOffset, length, output, outputOffset, maxout);
 107
 108         // unknown level, trigger error
 109         return 0;
 110     }
 111
 112     /**
 113       Compress a block of data in the input buffer and returns the size of
 114       compressed block. The size of input buffer is specified by length. The
 115       minimum input buffer size is 16.
 116
 117       The output buffer must be at least 5% larger than the input buffer
 118       and can not be smaller than 66 bytes.
 119
 120       If the input is not compressible, the return value might be larger than
 121       length (input buffer size).
 122
 123       The input buffer and the output buffer can not overlap.
 124
 125       Compression level can be specified in parameter level. At the moment,
 126       only level 1 and level 2 are supported.
 127       Level 1 is the fastest compression and generally useful for short data.
 128       Level 2 is slightly slower but it gives better compression ratio.
 129
 130       Note that the compressed data, regardless of the level, can always be
 131       decompressed using the function fastlz_decompress above.
 132     */
 133     public static int fastlz_compress_level(int level, byte[] input, int inputOffset, int length, byte[] output,
 134             int outputOffset) {
 135         if (level == 1)
 136             return fastlz1_compress(input, inputOffset, length, output, outputOffset);
 137         if (level == 2)
 138             return fastlz2_compress(input, inputOffset, length, output, outputOffset);
 139
 140         return 0;
 141     }
 142
 143
 144     private static int fastlz1_compress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset) {
 145         int ip = inputOffset;
 146         int ip_bound = inputOffset + length - 2;
 147         int ip_limit = inputOffset + length - 12;
 148         int op = outputOffset;
 149
 150         int[] htab = new int[HASH_SIZE];
 151         int hslot;
 152         int hval;
 153
 154         int copy;
 155
 156         // sanity check
 157         if(length < 4)
 158         {
 159             if(length != 0)
 160             {
 161                 // create literal copy only
 162                 output[op++] = (byte) (length-1);
 163                 ip_bound++;
 164                 while(ip <= ip_bound)
 165                     output[op++] = input[ip++];
 166                 return length+1;
 167             }
 168             else
 169                 return 0;
 170         }
 171
 172         // initializes hash table
 173         for (hslot = 0; hslot < HASH_SIZE; ++hslot)
 174             htab[hslot] = ip;
 175
 176         // we start with literal copy
 177         copy = 2;
 178         output[op++] = MAX_COPY-1;
 179         output[op++] = input[ip++];
 180         output[op++] = input[ip++];
 181
 182         // main loop
 183         while (ip < ip_limit) {
 184             int ref;
 185             int distance;
 186
 187             // minimum match length
 188             int len = 3;
 189
 190             // comparison starting-point
 191             int anchor = ip;
 192
 193             // find potential match
 194             hval = HASH_FUNCTION(input, ip);
 195             hslot = hval;
 196             ref = htab[hval];
 197
 198             // calculate distance to the match
 199             distance = anchor - ref;
 200
 201             // update hash table
 202             htab[hslot] = anchor;
 203
 204             // is this a match? check the first 3 bytes
 205             if (distance==0 ||
 206                     (distance >= MAX_DISTANCE) ||
 207                     input[ref++] != input[ip++] ||
 208                     input[ref++] != input[ip++] ||
 209                     input[ref++] != input[ip++])
 210             {
 211                 output[op++] = input[anchor++];
 212                 ip = anchor;
 213                 copy++;
 214                 if (copy == MAX_COPY) {
 215                     copy = 0;
 216                     output[op++] = MAX_COPY-1;
 217                 }
 218             } else {
 219                 // last matched byte
 220                 ip = anchor + len;
 221
 222                 // distance is biased
 223                 --distance;
 224
 225                 if(distance == 0) {
 226                     // zero distance means a run
 227                     byte x = input[ip - 1];
 228                     while (ip < ip_bound)
 229                         if (input[ref++] != x) break;
 230                         else ip++;
 231                 } else {
 232                     for (;;) {
 233                         // safe because the outer check against ip limit
 234                         if(input[ref++] != input[ip++]) break;
 235                         if(input[ref++] != input[ip++]) break;
 236                         if(input[ref++] != input[ip++]) break;
 237                         if(input[ref++] != input[ip++]) break;
 238                         if(input[ref++] != input[ip++]) break;
 239                         if(input[ref++] != input[ip++]) break;
 240                         if(input[ref++] != input[ip++]) break;
 241                         if(input[ref++] != input[ip++]) break;
 242                         while (ip < ip_bound)
 243                             if (input[ref++] != input[ip++]) break;
 244                         break;
 245                     }
 246                 }
 247
 248                 // if we have copied something, adjust the copy count
 249                 if (copy != 0)
 250                     // copy is biased, '0' means 1 byte copy
 251                     output[op-copy-1] = (byte)(copy-1);
 252                 else
 253                     // back, to overwrite the copy count
 254                     op--;
 255
 256                 // reset literal counter
 257                 copy = 0;
 258
 259                 // length is biased, '1' means a match of 3 bytes
 260                 ip -= 3;
 261                 len = ip - anchor;
 262
 263                 // encode the match
 264                 if (len > MAX_LEN - 2)
 265                     while (len > MAX_LEN - 2) {
 266                         output[op++] = (byte) ((7 << 5) + (distance >>> 8));
 267                         output[op++] = (byte) (MAX_LEN - 2 - 7 -2);
 268                         output[op++] = (byte) (distance & 0xff);
 269                         len -= MAX_LEN - 2;
 270                     }
 271
 272                 if (len < 7) {
 273                     output[op++] = (byte) ((len << 5) + (distance >>> 8));
 274                     output[op++] = (byte) (distance & 255);
 275                 } else {
 276                     output[op++] = (byte) ((7 << 5) + (distance >>> 8));
 277                     output[op++] = (byte) (len - 7);
 278                     output[op++] = (byte) (distance & 255);
 279                 }
 280
 281                 // update the hash at match boundary
 282                 hval = HASH_FUNCTION(input, ip);
 283                 htab[hval] = ip++;
 284                 hval = HASH_FUNCTION(input, ip);
 285                 htab[hval] = ip++;
 286
 287                 // assuming literal copy
 288                 output[op++] = MAX_COPY-1;
 289             }
 290         }
 291
 292         // left-over as literal copy
 293         ip_bound++;
 294         while (ip <= ip_bound) {
 295             output[op++] = input[ip++];
 296             copy++;
 297             if (copy == MAX_COPY) {
 298                 copy = 0;
 299                 output[op++] = MAX_COPY-1;
 300             }
 301         }
 302
 303         // if we have copied something, adjust the copy length
 304         if (copy != 0)
 305             output[op - copy - 1] = (byte) (copy - 1);
 306         else
 307             --op;
 308
 309         return op - outputOffset;
 310     }
 311
 312     private static int fastlz2_compress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset)
 313     {
 314         int ip = inputOffset;
 315         int ip_bound = ip + length - 2;
 316         int ip_limit = ip + length - 12;
 317         int op = outputOffset;
 318
 319         int[] htab = new int[HASH_SIZE];
 320         int hslot;
 321         int hval;
 322
 323         int copy;
 324
 325         // sanity check
 326         if (length < 4) {
 327             if (length != 0) {
 328                 // create literal copy only
 329                 output[op++] = (byte) (length - 1);
 330                 ip_bound++;
 331                 while(ip <= ip_bound)
 332                     output[op++] = input[ip++];
 333                 return length + 1;
 334             } else
 335                 return 0;
 336         }
 337
 338         // initializes hash table
 339         for (hslot = 0; hslot < HASH_SIZE; ++hslot)
 340             htab[hslot] = ip;
 341
 342         // we start with literal copy
 343         copy = 2;
 344         output[op++] = MAX_COPY-1;
 345         output[op++] = input[ip++];
 346         output[op++] = input[ip++];
 347
 348         // main loop
 349         while (ip < ip_limit) {
 350             int ref;
 351             int distance;
 352
 353             // minimum match length
 354             int len = 3;
 355
 356             // comparison starting-point
 357             int anchor = ip;
 358
 359             // check for a run
 360             if (input[ip] == input[ip-1] && FASTLZ_READU16(input, ip-1) == FASTLZ_READU16(input, ip+1)) {
 361                 distance = 1;
 362                 ip += 3;
 363                 ref = anchor - 1 + 3;
 364
 365                 // NOTE: cannot do this goto, so copied the code here from line 487
 366                 //goto match;
 367
 368                 // last matched byte
 369                 ip = anchor + len;
 370
 371                 // distance is biased
 372                 --distance;
 373
 374                 if (distance == 0) {
 375                     // zero distance means a run
 376                     byte x = input[ip - 1];
 377                     while (ip < ip_bound)
 378                         if (input[ref++] != x) break;
 379                         else ++ip;
 380                 } else {
 381                     for (;;) {
 382                         // safe because the outer check against ip limit
 383                         if(input[ref++] != input[ip++]) break;
 384                         if(input[ref++] != input[ip++]) break;
 385                         if(input[ref++] != input[ip++]) break;
 386                         if(input[ref++] != input[ip++]) break;
 387                         if(input[ref++] != input[ip++]) break;
 388                         if(input[ref++] != input[ip++]) break;
 389                         if(input[ref++] != input[ip++]) break;
 390                         if(input[ref++] != input[ip++]) break;
 391                         while (ip < ip_bound)
 392                             if (input[ref++] != input[ip++]) break;
 393                         break;
 394                     }
 395                 }
 396
 397                 // if we have copied something, adjust the copy count
 398                 if (copy != 0)
 399                     // copy is biased, '0' means 1 byte copy
 400                     output[op - copy - 1] = (byte) (copy - 1);
 401                 else
 402                     // back, to overwrite the copy count
 403                     --op;
 404
 405                 // reset literal counter
 406                 copy = 0;
 407
 408                 // length is biased, '1' means a match of 3 bytes
 409                 ip -= 3;
 410                 len = ip - anchor;
 411
 412                 // encode the match
 413                 if (distance < MAX_DISTANCE2) {
 414                     if (len < 7) {
 415                         output[op++] = (byte) ((len << 5) + (distance >>> 8));
 416                         output[op++] = (byte) (distance & 255);
 417                     } else {
 418                         output[op++] = (byte) ((7 << 5) + (distance >>> 8));
 419                         for (len -= 7; len >= 255; len -= 255)
 420                             output[op++] = (byte) 255;
 421                         output[op++] = (byte) len;
 422                         output[op++] = (byte) (distance & 255);
 423                     }
 424                 } else {
 425                     // far away, but not yet in the another galaxy...
 426                     if(len < 7) {
 427                         distance -= MAX_DISTANCE2;
 428                         output[op++] = (byte) ((len << 5) + 31);
 429                         output[op++] = (byte) 255;
 430                         output[op++] = (byte) (distance >>> 8);
 431                         output[op++] = (byte) (distance & 255);
 432                     } else {
 433                         distance -= MAX_DISTANCE2;
 434                         output[op++] = (byte) ((7 << 5) + 31);
 435                         for (len -=7; len >= 255; len -= 255)
 436                             output[op++] = (byte) 255;
 437                         output[op++] = (byte) len;
 438                         output[op++] = (byte) 255;
 439                         output[op++] = (byte) (distance >>> 8);
 440                         output[op++] = (byte) (distance & 255);
 441                     }
 442                 }
 443
 444                 // update the hash at match boundary
 445                 hval = HASH_FUNCTION(input, ip);
 446                 htab[hval] = ip++;
 447                 hval = HASH_FUNCTION(input, ip);
 448                 htab[hval] = ip++;
 449
 450                 // assuming literal copy
 451                 output[op++] = MAX_COPY-1;
 452
 453                 continue;
 454             }
 455
 456             // find potential match
 457             hval = HASH_FUNCTION(input, ip);
 458             hslot = hval;
 459             ref = htab[hval];
 460
 461             // calculate distance to the match
 462             distance = anchor - ref;
 463
 464             // update hash table
 465             htab[hslot] = anchor;
 466
 467             // is this a match? check the first 3 bytes
 468             if (distance==0 ||
 469                     (distance >= MAX_FARDISTANCE) ||
 470                     input[ref++] != input[ip++] ||
 471                     input[ref++] != input[ip++] ||
 472                     input[ref++] != input[ip++])
 473             {
 474                 output[op++] = input[anchor++];
 475                 ip = anchor;
 476                 copy++;
 477                 if (copy == MAX_COPY) {
 478                     copy = 0;
 479                     output[op++] = MAX_COPY-1;
 480                 }
 481             } else {
 482                 // far, needs at least 5-byte match
 483                 if (distance >= MAX_DISTANCE2) {
 484                     if (input[ip++] != input[ref++] || input[ip++] != input[ref++]) {
 485                         // LITERAL COPY, code copied from above
 486                         output[op++] = input[anchor++];
 487                         ip = anchor;
 488                         copy++;
 489                         if (copy == MAX_COPY) {
 490                             copy = 0;
 491                             output[op++] = MAX_COPY-1;
 492                         }
 493                         continue;
 494                     }
 495                     len += 2;
 496                 }
 497
 498                 // NOTE: all of the following code within this block is copied above
 499                 // to line 357
 500                 //match:
 501
 502                 // last matched byte
 503                 ip = anchor + len;
 504
 505                 // distance is biased
 506                 --distance;
 507
 508                 if (distance == 0) {
 509                     // zero distance means a run
 510                     byte x = input[ip - 1];
 511                     while (ip < ip_bound)
 512                         if (input[ref++] != x) break;
 513                         else ++ip;
 514                 } else {
 515                     for (;;) {
 516                         // safe because the outer check against ip limit
 517                         if(input[ref++] != input[ip++]) break;
 518                         if(input[ref++] != input[ip++]) break;
 519                         if(input[ref++] != input[ip++]) break;
 520                         if(input[ref++] != input[ip++]) break;
 521                         if(input[ref++] != input[ip++]) break;
 522                         if(input[ref++] != input[ip++]) break;
 523                         if(input[ref++] != input[ip++]) break;
 524                         if(input[ref++] != input[ip++]) break;
 525                         while (ip < ip_bound)
 526                             if (input[ref++] != input[ip++]) break;
 527                         break;
 528                     }
 529                 }
 530
 531                 // if we have copied something, adjust the copy count
 532                 if (copy != 0)
 533                     // copy is biased, '0' means 1 byte copy
 534                     output[op - copy - 1] = (byte) (copy - 1);
 535                 else
 536                     // back, to overwrite the copy count
 537                     --op;
 538
 539                 // reset literal counter
 540                 copy = 0;
 541
 542                 // length is biased, '1' means a match of 3 bytes
 543                 ip -= 3;
 544                 len = ip - anchor;
 545
 546                 // encode the match
 547                 if (distance < MAX_DISTANCE2) {
 548                     if (len < 7) {
 549                         output[op++] = (byte) ((len << 5) + (distance >>> 8));
 550                         output[op++] = (byte) (distance & 255);
 551                     } else {
 552                         output[op++] = (byte) ((7 << 5) + (distance >>> 8));
 553                         for (len -= 7; len >= 255; len -= 255)
 554                             output[op++] = (byte) 255;
 555                         output[op++] = (byte) len;
 556                         output[op++] = (byte) (distance & 255);
 557                     }
 558                 } else {
 559                     // far away, but not yet in the another galaxy...
 560                     if(len < 7) {
 561                         distance -= MAX_DISTANCE2;
 562                         output[op++] = (byte) ((len << 5) + 31);
 563                         output[op++] = (byte) 255;
 564                         output[op++] = (byte) (distance >>> 8);
 565                         output[op++] = (byte) (distance & 255);
 566                     } else {
 567                         distance -= MAX_DISTANCE2;
 568                         output[op++] = (byte) ((7 << 5) + 31);
 569                         for (len -=7; len >= 255; len -= 255)
 570                             output[op++] = (byte) 255;
 571                         output[op++] = (byte) len;
 572                         output[op++] = (byte) 255;
 573                         output[op++] = (byte) (distance >>> 8);
 574                         output[op++] = (byte) (distance & 255);
 575                     }
 576                 }
 577
 578                 // update the hash at match boundary
 579                 hval = HASH_FUNCTION(input, ip);
 580                 htab[hval] = ip++;
 581                 hval = HASH_FUNCTION(input, ip);
 582                 htab[hval] = ip++;
 583
 584                 // assuming literal copy
 585                 output[op++] = MAX_COPY-1;
 586             }
 587         }
 588
 589         // left-over as literal copy
 590         ip_bound++;
 591         while (ip <= ip_bound) {
 592             output[op++] = input[ip++];
 593             copy++;
 594             if (copy == MAX_COPY) {
 595                 copy = 0;
 596                 output[op++] = MAX_COPY-1;
 597             }
 598         }
 599
 600         // if we have copied something, adjust the copy length
 601         if (copy != 0)
 602             output[op-copy-1] = (byte) (copy - 1);
 603         else
 604             op--;
 605
 606         // marker for fastlz2
 607         output[outputOffset] |= (1 << 5);
 608
 609         return op - outputOffset;
 610     }
 611
 612     // ------------------------------------------------------------------------
 613
 614     private static int fastlz1_decompress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset,
 615             int maxout) {
 616         int ip = inputOffset;
 617         int ip_limit  = ip + length;
 618         int op = outputOffset;
 619         int op_limit = op + maxout;
 620         int ctrl = (int) input[ip++] & 31;
 621         boolean loop = true;
 622
 623         do {
 624             int ref = op;
 625             int len = ctrl >>> 5;
 626             int ofs = (ctrl & 31) << 8;
 627
 628             if (ctrl >= 32) {
 629                 len--;
 630                 ref -= ofs;
 631                 if (len == 7-1)
 632                     len += (int) input[ip++] & 0xff;
 633                 ref -= (int) input[ip++] & 0xff;
 634
 635                 if (FASTLZ_SAFE) {
 636                     if (op + len + 3 > op_limit)
 637                         return 0;
 638
 639                     if (ref-1 < outputOffset)
 640                         return 0;
 641                 }
 642
 643                 if (ip < ip_limit)
 644                     ctrl = (int) input[ip++] & 0xff;
 645                 else
 646                     loop = false;
 647
 648                 if (ref == op) {
 649                     // optimize copy for a run
 650                     byte b = output[ref-1];
 651                     output[op++] = b;
 652                     output[op++] = b;
 653                     output[op++] = b;
 654                     for(; len > 0; --len)
 655                         output[op++] = b;
 656                 } else {
 657                     /* copy from reference */
 658                     ref--;
 659                     output[op++] = output[ref++];
 660                     output[op++] = output[ref++];
 661                     output[op++] = output[ref++];
 662                     for (; len > 0; --len)
 663                         output[op++] = output[ref++];
 664                 }
 665             } else {
 666                 ctrl++;
 667                 if (FASTLZ_SAFE) {
 668                     if (op + ctrl > op_limit)
 669                         return 0;
 670                     if (ip + ctrl > ip_limit)
 671                         return 0;
 672                 }
 673
 674                 output[op++] = input[ip++];
 675                 for (--ctrl; ctrl > 0; --ctrl)
 676                     output[op++] = input[ip++];
 677
 678                 loop = ip < ip_limit;
 679                 if (loop)
 680                     ctrl = (int) input[ip++] & 0xff;
 681             }
 682         } while(loop);
 683
 684         return op - outputOffset;
 685     }
 686
 687     private static int fastlz2_decompress(byte[] input, int inputOffset, int length, byte[] output, int outputOffset,
 688             int maxout) {
 689         int ip = inputOffset;
 690         int ip_limit = ip + length;
 691         int op = outputOffset;
 692         int op_limit = op + maxout;
 693         int ctrl = (int) input[ip++] & 31;
 694         boolean loop = true;
 695
 696         do {
 697             int ref = op;
 698             int len = ctrl >>> 5;
 699             int ofs = (ctrl & 31) << 8;
 700
 701             if (ctrl >= 32) {
 702                 int code;
 703                 len--;
 704                 ref -= ofs;
 705                 if (len == 7-1) {
 706                     do {
 707                         code = (int) input[ip++] & 0xff;
 708                         len += code;
 709                     } while (code==255);
 710                 }
 711                 code = (int) input[ip++] & 0xff;
 712                 ref -= code;
 713
 714                 // match from 16-bit distance
 715                 if (code == 255) {
 716                     if (ofs == (31 << 8)) {
 717                         ofs = ((int) input[ip++] & 0xff) << 8;
 718                         ofs += (int) input[ip++] & 0xff;
 719                         ref = op - ofs - MAX_DISTANCE2;
 720                     }
 721                 }
 722
 723                 if (FASTLZ_SAFE) {
 724                     if (op + len + 3 > op_limit)
 725                         return 0;
 726
 727                     if (ref-1 < outputOffset)
 728                         return 0;
 729                 }
 730
 731                 if (ip < ip_limit)
 732                     ctrl = (int) input[ip++] & 0xff;
 733                 else
 734                     loop = false;
 735
 736                 if (ref == op) {
 737                     /* optimize copy for a run */
 738                     byte b = output[ref-1];
 739                     output[op++] = b;
 740                     output[op++] = b;
 741                     output[op++] = b;
 742                     for (; len > 0; --len)
 743                         output[op++] = b;
 744                 } else {
 745                     /* copy from reference */
 746                     --ref;
 747                     output[op++] = output[ref++];
 748                     output[op++] = output[ref++];
 749                     output[op++] = output[ref++];
 750                     for (; len > 0; --len)
 751                         output[op++] = output[ref++];
 752                 }
 753             } else {
 754                 ++ctrl;
 755                 if (FASTLZ_SAFE) {
 756                     if (op + ctrl > op_limit)
 757                         return 0;
 758                     if (ip + ctrl > ip_limit)
 759                         return 0;
 760                 }
 761
 762                 output[op++] = input[ip++];
 763                 for (--ctrl; ctrl > 0; --ctrl)
 764                     output[op++] = input[ip++];
 765
 766                 loop = ip < ip_limit;
 767                 if (loop)
 768                     ctrl = (int) input[ip++] & 0xff;
 769             }
 770         } while (loop);
 771
 772         return op - outputOffset;
 773     }
 774
 775 }