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

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