bundles/org.simantics.lz4/src/net/jpountz/lz4/LZ4HCJavaSafeCompressor.java

   1 // Auto-generated: DO NOT EDIT
   2
   3 package net.jpountz.lz4;
   4
   5 import static net.jpountz.lz4.LZ4Constants.*;
   6 import static net.jpountz.lz4.LZ4Utils.*;
   7
   8 import java.nio.ByteBuffer;
   9 import java.util.Arrays;
  10
  11 import net.jpountz.lz4.LZ4Utils.Match;
  12 import net.jpountz.util.ByteBufferUtils;
  13 import net.jpountz.util.SafeUtils;
  14
  15 /**
  16  * High compression compressor.
  17  */
  18 final class LZ4HCJavaSafeCompressor extends LZ4Compressor {
  19
  20   public static final LZ4Compressor INSTANCE = new LZ4HCJavaSafeCompressor();
  21
  22   private final int maxAttempts;
  23   final int compressionLevel;
  24
  25   LZ4HCJavaSafeCompressor() { this(DEFAULT_COMPRESSION_LEVEL); }
  26   LZ4HCJavaSafeCompressor(int compressionLevel) {
  27     this.maxAttempts = 1<<(compressionLevel-1);
  28     this.compressionLevel = compressionLevel;
  29   }
  30
  31   private class HashTable {
  32     static final int MASK = MAX_DISTANCE - 1;
  33     int nextToUpdate;
  34     private final int base;
  35     private final int[] hashTable;
  36     private final short[] chainTable;
  37
  38     HashTable(int base) {
  39       this.base = base;
  40       nextToUpdate = base;
  41       hashTable = new int[HASH_TABLE_SIZE_HC];
  42       Arrays.fill(hashTable, -1);
  43       chainTable = new short[MAX_DISTANCE];
  44     }
  45
  46     private int hashPointer(byte[] bytes, int off) {
  47       final int v = SafeUtils.readInt(bytes, off);
  48       return hashPointer(v);
  49     }
  50
  51     private int hashPointer(ByteBuffer bytes, int off) {
  52       final int v = ByteBufferUtils.readInt(bytes, off);
  53       return hashPointer(v);
  54     }
  55
  56     private int hashPointer(int v) {
  57       final int h = hashHC(v);
  58       return hashTable[h];
  59     }
  60
  61     private int next(int off) {
  62       return off - (chainTable[off & MASK] & 0xFFFF);
  63     }
  64
  65     private void addHash(byte[] bytes, int off) {
  66       final int v = SafeUtils.readInt(bytes, off);
  67       addHash(v, off);
  68     }
  69
  70     private void addHash(ByteBuffer bytes, int off) {
  71       final int v = ByteBufferUtils.readInt(bytes, off);
  72       addHash(v, off);
  73     }
  74
  75     private void addHash(int v, int off) {
  76       final int h = hashHC(v);
  77       int delta = off - hashTable[h];
  78       assert delta > 0 : delta;
  79       if (delta >= MAX_DISTANCE) {
  80         delta = MAX_DISTANCE - 1;
  81       }
  82       chainTable[off & MASK] = (short) delta;
  83       hashTable[h] = off;
  84     }
  85
  86     void insert(int off, byte[] bytes) {
  87       for (; nextToUpdate < off; ++nextToUpdate) {
  88         addHash(bytes, nextToUpdate);
  89       }
  90     }
  91
  92     void insert(int off, ByteBuffer bytes) {
  93       for (; nextToUpdate < off; ++nextToUpdate) {
  94         addHash(bytes, nextToUpdate);
  95       }
  96     }
  97
  98
  99
 100     boolean insertAndFindBestMatch(byte[] buf, int off, int matchLimit, Match match) {
 101       match.start = off;
 102       match.len = 0;
 103       int delta = 0;
 104       int repl = 0;
 105
 106       insert(off, buf);
 107
 108       int ref = hashPointer(buf, off);
 109
 110       if (ref >= off - 4 && ref <= off && ref >= base) { // potential repetition
 111         if (LZ4SafeUtils.readIntEquals(buf, ref, off)) { // confirmed
 112           delta = off - ref;
 113           repl = match.len = MIN_MATCH + LZ4SafeUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 114           match.ref = ref;
 115         }
 116         ref = next(ref);
 117       }
 118
 119       for (int i = 0; i < maxAttempts; ++i) {
 120         if (ref < Math.max(base, off - MAX_DISTANCE + 1) || ref > off) {
 121           break;
 122         }
 123         if (LZ4SafeUtils.readIntEquals(buf, ref, off)) {
 124           final int matchLen = MIN_MATCH + LZ4SafeUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 125           if (matchLen > match.len) {
 126             match.ref = ref;
 127             match.len = matchLen;
 128           }
 129         }
 130         ref = next(ref);
 131       }
 132
 133       if (repl != 0) {
 134         int ptr = off;
 135         final int end = off + repl - (MIN_MATCH - 1);
 136         while (ptr < end - delta) {
 137           chainTable[ptr & MASK] = (short) delta; // pre load
 138           ++ptr;
 139         }
 140         do {
 141           chainTable[ptr & MASK] = (short) delta;
 142           hashTable[hashHC(SafeUtils.readInt(buf, ptr))] = ptr;
 143           ++ptr;
 144         } while (ptr < end);
 145         nextToUpdate = end;
 146       }
 147
 148       return match.len != 0;
 149     }
 150
 151     boolean insertAndFindWiderMatch(byte[] buf, int off, int startLimit, int matchLimit, int minLen, Match match) {
 152       match.len = minLen;
 153
 154       insert(off, buf);
 155
 156       //final int delta = off - startLimit;
 157       int ref = hashPointer(buf, off);
 158       for (int i = 0; i < maxAttempts; ++i) {
 159         if (ref < Math.max(base, off - MAX_DISTANCE + 1) || ref > off) {
 160           break;
 161         }
 162         if (LZ4SafeUtils.readIntEquals(buf, ref, off)) {
 163           final int matchLenForward = MIN_MATCH +LZ4SafeUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 164           final int matchLenBackward = LZ4SafeUtils.commonBytesBackward(buf, ref, off, base, startLimit);
 165           final int matchLen = matchLenBackward + matchLenForward;
 166           if (matchLen > match.len) {
 167             match.len = matchLen;
 168             match.ref = ref - matchLenBackward;
 169             match.start = off - matchLenBackward;
 170           }
 171         }
 172         ref = next(ref);
 173       }
 174
 175       return match.len > minLen;
 176     }
 177
 178
 179     boolean insertAndFindBestMatch(ByteBuffer buf, int off, int matchLimit, Match match) {
 180       match.start = off;
 181       match.len = 0;
 182       int delta = 0;
 183       int repl = 0;
 184
 185       insert(off, buf);
 186
 187       int ref = hashPointer(buf, off);
 188
 189       if (ref >= off - 4 && ref <= off && ref >= base) { // potential repetition
 190         if (LZ4ByteBufferUtils.readIntEquals(buf, ref, off)) { // confirmed
 191           delta = off - ref;
 192           repl = match.len = MIN_MATCH + LZ4ByteBufferUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 193           match.ref = ref;
 194         }
 195         ref = next(ref);
 196       }
 197
 198       for (int i = 0; i < maxAttempts; ++i) {
 199         if (ref < Math.max(base, off - MAX_DISTANCE + 1) || ref > off) {
 200           break;
 201         }
 202         if (LZ4ByteBufferUtils.readIntEquals(buf, ref, off)) {
 203           final int matchLen = MIN_MATCH + LZ4ByteBufferUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 204           if (matchLen > match.len) {
 205             match.ref = ref;
 206             match.len = matchLen;
 207           }
 208         }
 209         ref = next(ref);
 210       }
 211
 212       if (repl != 0) {
 213         int ptr = off;
 214         final int end = off + repl - (MIN_MATCH - 1);
 215         while (ptr < end - delta) {
 216           chainTable[ptr & MASK] = (short) delta; // pre load
 217           ++ptr;
 218         }
 219         do {
 220           chainTable[ptr & MASK] = (short) delta;
 221           hashTable[hashHC(ByteBufferUtils.readInt(buf, ptr))] = ptr;
 222           ++ptr;
 223         } while (ptr < end);
 224         nextToUpdate = end;
 225       }
 226
 227       return match.len != 0;
 228     }
 229
 230     boolean insertAndFindWiderMatch(ByteBuffer buf, int off, int startLimit, int matchLimit, int minLen, Match match) {
 231       match.len = minLen;
 232
 233       insert(off, buf);
 234
 235       //final int delta = off - startLimit;
 236       int ref = hashPointer(buf, off);
 237       for (int i = 0; i < maxAttempts; ++i) {
 238         if (ref < Math.max(base, off - MAX_DISTANCE + 1) || ref > off) {
 239           break;
 240         }
 241         if (LZ4ByteBufferUtils.readIntEquals(buf, ref, off)) {
 242           final int matchLenForward = MIN_MATCH +LZ4ByteBufferUtils.commonBytes(buf, ref + MIN_MATCH, off + MIN_MATCH, matchLimit);
 243           final int matchLenBackward = LZ4ByteBufferUtils.commonBytesBackward(buf, ref, off, base, startLimit);
 244           final int matchLen = matchLenBackward + matchLenForward;
 245           if (matchLen > match.len) {
 246             match.len = matchLen;
 247             match.ref = ref - matchLenBackward;
 248             match.start = off - matchLenBackward;
 249           }
 250         }
 251         ref = next(ref);
 252       }
 253
 254       return match.len > minLen;
 255     }
 256
 257
 258   }
 259
 260   @Override
 261   public int compress(byte[] src, int srcOff, int srcLen, byte[] dest, int destOff, int maxDestLen) {
 262
 263     SafeUtils.checkRange(src, srcOff, srcLen);
 264     SafeUtils.checkRange(dest, destOff, maxDestLen);
 265
 266     final int srcEnd = srcOff + srcLen;
 267     final int destEnd = destOff + maxDestLen;
 268     final int mfLimit = srcEnd - MF_LIMIT;
 269     final int matchLimit = srcEnd - LAST_LITERALS;
 270
 271     int sOff = srcOff;
 272     int dOff = destOff;
 273     int anchor = sOff++;
 274
 275     final HashTable ht = new HashTable(srcOff);
 276     final Match match0 = new Match();
 277     final Match match1 = new Match();
 278     final Match match2 = new Match();
 279     final Match match3 = new Match();
 280
 281     main:
 282     while (sOff < mfLimit) {
 283       if (!ht.insertAndFindBestMatch(src, sOff, matchLimit, match1)) {
 284         ++sOff;
 285         continue;
 286       }
 287
 288       // saved, in case we would skip too much
 289       copyTo(match1, match0);
 290
 291       search2:
 292       while (true) {
 293         assert match1.start >= anchor;
 294         if (match1.end() >= mfLimit
 295             || !ht.insertAndFindWiderMatch(src, match1.end() - 2, match1.start + 1, matchLimit, match1.len, match2)) {
 296           // no better match
 297           dOff = LZ4SafeUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 298           anchor = sOff = match1.end();
 299           continue main;
 300         }
 301
 302         if (match0.start < match1.start) {
 303           if (match2.start < match1.start + match0.len) { // empirical
 304             copyTo(match0, match1);
 305           }
 306         }
 307         assert match2.start > match1.start;
 308
 309         if (match2.start - match1.start < 3) { // First Match too small : removed
 310           copyTo(match2, match1);
 311           continue search2;
 312         }
 313
 314         search3:
 315         while (true) {
 316           if (match2.start - match1.start < OPTIMAL_ML) {
 317             int newMatchLen = match1.len;
 318             if (newMatchLen > OPTIMAL_ML) {
 319               newMatchLen = OPTIMAL_ML;
 320             }
 321             if (match1.start + newMatchLen > match2.end() - MIN_MATCH) {
 322               newMatchLen = match2.start - match1.start + match2.len - MIN_MATCH;
 323             }
 324             final int correction = newMatchLen - (match2.start - match1.start);
 325             if (correction > 0) {
 326               match2.fix(correction);
 327             }
 328           }
 329
 330           if (match2.start + match2.len >= mfLimit
 331               || !ht.insertAndFindWiderMatch(src, match2.end() - 3, match2.start, matchLimit, match2.len, match3)) {
 332             // no better match -> 2 sequences to encode
 333             if (match2.start < match1.end()) {
 334               match1.len = match2.start - match1.start;
 335             }
 336             // encode seq 1
 337             dOff = LZ4SafeUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 338             anchor = sOff = match1.end();
 339             // encode seq 2
 340             dOff = LZ4SafeUtils.encodeSequence(src, anchor, match2.start, match2.ref, match2.len, dest, dOff, destEnd);
 341             anchor = sOff = match2.end();
 342             continue main;
 343           }
 344
 345           if (match3.start < match1.end() + 3) { // Not enough space for match 2 : remove it
 346             if (match3.start >= match1.end()) { // // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1
 347               if (match2.start < match1.end()) {
 348                 final int correction = match1.end() - match2.start;
 349                 match2.fix(correction);
 350                 if (match2.len < MIN_MATCH) {
 351                   copyTo(match3, match2);
 352                 }
 353               }
 354
 355               dOff = LZ4SafeUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 356               anchor = sOff = match1.end();
 357
 358               copyTo(match3, match1);
 359               copyTo(match2, match0);
 360
 361               continue search2;
 362             }
 363
 364             copyTo(match3, match2);
 365             continue search3;
 366           }
 367
 368           // OK, now we have 3 ascending matches; let's write at least the first one
 369           if (match2.start < match1.end()) {
 370             if (match2.start - match1.start < ML_MASK) {
 371               if (match1.len > OPTIMAL_ML) {
 372                 match1.len = OPTIMAL_ML;
 373               }
 374               if (match1.end() > match2.end() - MIN_MATCH) {
 375                 match1.len = match2.end() - match1.start - MIN_MATCH;
 376               }
 377               final int correction = match1.end() - match2.start;
 378               match2.fix(correction);
 379             } else {
 380               match1.len = match2.start - match1.start;
 381             }
 382           }
 383
 384           dOff = LZ4SafeUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 385           anchor = sOff = match1.end();
 386
 387           copyTo(match2, match1);
 388           copyTo(match3, match2);
 389
 390           continue search3;
 391         }
 392
 393       }
 394
 395     }
 396
 397     dOff = LZ4SafeUtils.lastLiterals(src, anchor, srcEnd - anchor, dest, dOff, destEnd);
 398     return dOff - destOff;
 399   }
 400
 401
 402   @Override
 403   public int compress(ByteBuffer src, int srcOff, int srcLen, ByteBuffer dest, int destOff, int maxDestLen) {
 404
 405     if (src.hasArray() && dest.hasArray()) {
 406       return compress(src.array(), srcOff + src.arrayOffset(), srcLen, dest.array(), destOff + dest.arrayOffset(), maxDestLen);
 407     }
 408     src = ByteBufferUtils.inNativeByteOrder(src);
 409     dest = ByteBufferUtils.inNativeByteOrder(dest);
 410
 411     ByteBufferUtils.checkRange(src, srcOff, srcLen);
 412     ByteBufferUtils.checkRange(dest, destOff, maxDestLen);
 413
 414     final int srcEnd = srcOff + srcLen;
 415     final int destEnd = destOff + maxDestLen;
 416     final int mfLimit = srcEnd - MF_LIMIT;
 417     final int matchLimit = srcEnd - LAST_LITERALS;
 418
 419     int sOff = srcOff;
 420     int dOff = destOff;
 421     int anchor = sOff++;
 422
 423     final HashTable ht = new HashTable(srcOff);
 424     final Match match0 = new Match();
 425     final Match match1 = new Match();
 426     final Match match2 = new Match();
 427     final Match match3 = new Match();
 428
 429     main:
 430     while (sOff < mfLimit) {
 431       if (!ht.insertAndFindBestMatch(src, sOff, matchLimit, match1)) {
 432         ++sOff;
 433         continue;
 434       }
 435
 436       // saved, in case we would skip too much
 437       copyTo(match1, match0);
 438
 439       search2:
 440       while (true) {
 441         assert match1.start >= anchor;
 442         if (match1.end() >= mfLimit
 443             || !ht.insertAndFindWiderMatch(src, match1.end() - 2, match1.start + 1, matchLimit, match1.len, match2)) {
 444           // no better match
 445           dOff = LZ4ByteBufferUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 446           anchor = sOff = match1.end();
 447           continue main;
 448         }
 449
 450         if (match0.start < match1.start) {
 451           if (match2.start < match1.start + match0.len) { // empirical
 452             copyTo(match0, match1);
 453           }
 454         }
 455         assert match2.start > match1.start;
 456
 457         if (match2.start - match1.start < 3) { // First Match too small : removed
 458           copyTo(match2, match1);
 459           continue search2;
 460         }
 461
 462         search3:
 463         while (true) {
 464           if (match2.start - match1.start < OPTIMAL_ML) {
 465             int newMatchLen = match1.len;
 466             if (newMatchLen > OPTIMAL_ML) {
 467               newMatchLen = OPTIMAL_ML;
 468             }
 469             if (match1.start + newMatchLen > match2.end() - MIN_MATCH) {
 470               newMatchLen = match2.start - match1.start + match2.len - MIN_MATCH;
 471             }
 472             final int correction = newMatchLen - (match2.start - match1.start);
 473             if (correction > 0) {
 474               match2.fix(correction);
 475             }
 476           }
 477
 478           if (match2.start + match2.len >= mfLimit
 479               || !ht.insertAndFindWiderMatch(src, match2.end() - 3, match2.start, matchLimit, match2.len, match3)) {
 480             // no better match -> 2 sequences to encode
 481             if (match2.start < match1.end()) {
 482               match1.len = match2.start - match1.start;
 483             }
 484             // encode seq 1
 485             dOff = LZ4ByteBufferUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 486             anchor = sOff = match1.end();
 487             // encode seq 2
 488             dOff = LZ4ByteBufferUtils.encodeSequence(src, anchor, match2.start, match2.ref, match2.len, dest, dOff, destEnd);
 489             anchor = sOff = match2.end();
 490             continue main;
 491           }
 492
 493           if (match3.start < match1.end() + 3) { // Not enough space for match 2 : remove it
 494             if (match3.start >= match1.end()) { // // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1
 495               if (match2.start < match1.end()) {
 496                 final int correction = match1.end() - match2.start;
 497                 match2.fix(correction);
 498                 if (match2.len < MIN_MATCH) {
 499                   copyTo(match3, match2);
 500                 }
 501               }
 502
 503               dOff = LZ4ByteBufferUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 504               anchor = sOff = match1.end();
 505
 506               copyTo(match3, match1);
 507               copyTo(match2, match0);
 508
 509               continue search2;
 510             }
 511
 512             copyTo(match3, match2);
 513             continue search3;
 514           }
 515
 516           // OK, now we have 3 ascending matches; let's write at least the first one
 517           if (match2.start < match1.end()) {
 518             if (match2.start - match1.start < ML_MASK) {
 519               if (match1.len > OPTIMAL_ML) {
 520                 match1.len = OPTIMAL_ML;
 521               }
 522               if (match1.end() > match2.end() - MIN_MATCH) {
 523                 match1.len = match2.end() - match1.start - MIN_MATCH;
 524               }
 525               final int correction = match1.end() - match2.start;
 526               match2.fix(correction);
 527             } else {
 528               match1.len = match2.start - match1.start;
 529             }
 530           }
 531
 532           dOff = LZ4ByteBufferUtils.encodeSequence(src, anchor, match1.start, match1.ref, match1.len, dest, dOff, destEnd);
 533           anchor = sOff = match1.end();
 534
 535           copyTo(match2, match1);
 536           copyTo(match3, match2);
 537
 538           continue search3;
 539         }
 540
 541       }
 542
 543     }
 544
 545     dOff = LZ4ByteBufferUtils.lastLiterals(src, anchor, srcEnd - anchor, dest, dOff, destEnd);
 546     return dOff - destOff;
 547   }
 548
 549
 550 }