]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.lz4/src/net/jpountz/lz4/LZ4HCJavaSafeCompressor.java
Listen to changes in page settings in DiagramSceneGraphProvider
[simantics/platform.git] / 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 }