Debian Codegraph @

BLOSC/src/internal-complibs/lz4-r119/lz4hc.c

raw
1 /*
2 LZ4 HC - High Compression Mode of LZ4
3 Copyright (C) 2011-2014, Yann Collet.
4 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
8 met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above
13 copyright notice, this list of conditions and the following disclaimer
14 in the documentation and/or other materials provided with the
15 distribution.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 You can contact the author at :
30 - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
31 - LZ4 source repository : http://code.google.com/p/lz4/
32 */
33
34
35
36 /**************************************
37 Tuning Parameter
38 **************************************/
39 #define LZ4HC_DEFAULT_COMPRESSIONLEVEL 8
40
41
42 /**************************************
43 Memory routines
44 **************************************/
45 #include <stdlib.h> /* calloc, free */
46 #define ALLOCATOR(s) calloc(1,s)
47 #define FREEMEM free
48 #include <string.h> /* memset, memcpy */
49 #define MEM_INIT memset
50
51
52 /**************************************
53 CPU Feature Detection
54 **************************************/
55 /* 32 or 64 bits ? */
56 #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \
57 || defined(__powerpc64__) || defined(__powerpc64le__) \
58 || defined(__ppc64__) || defined(__ppc64le__) \
59 || defined(__PPC64__) || defined(__PPC64LE__) \
60 || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) /* Detects 64 bits mode */
61 # define LZ4_ARCH64 1
62 #else
63 # define LZ4_ARCH64 0
64 #endif
65
66 /*
67 * Little Endian or Big Endian ?
68 * Overwrite the #define below if you know your architecture endianess
69 */
70 #include <stdlib.h> /* Apparently required to detect endianess */
71 #if defined (__GLIBC__)
72 # include <endian.h>
73 # if (__BYTE_ORDER == __BIG_ENDIAN)
74 # define LZ4_BIG_ENDIAN 1
75 # endif
76 #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
77 # define LZ4_BIG_ENDIAN 1
78 #elif defined(__sparc) || defined(__sparc__) \
79 || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
80 || defined(__hpux) || defined(__hppa) \
81 || defined(_MIPSEB) || defined(__s390__)
82 # define LZ4_BIG_ENDIAN 1
83 #else
84 /* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */
85 #endif
86
87 /*
88 * Unaligned memory access is automatically enabled for "common" CPU, such as x86.
89 * For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected
90 * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance
91 */
92 #if defined(__ARM_FEATURE_UNALIGNED)
93 # define LZ4_FORCE_UNALIGNED_ACCESS 1
94 #endif
95
96 /* Define this parameter if your target system or compiler does not support hardware bit count */
97 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */
98 # define LZ4_FORCE_SW_BITCOUNT
99 #endif
100
101
102 /**************************************
103 Compiler Options
104 **************************************/
105 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */
106 /* "restrict" is a known keyword */
107 #else
108 # define restrict /* Disable restrict */
109 #endif
110
111 #ifdef _MSC_VER /* Visual Studio */
112 # define FORCE_INLINE static __forceinline
113 # include <intrin.h> /* For Visual 2005 */
114 # if LZ4_ARCH64 /* 64-bits */
115 # pragma intrinsic(_BitScanForward64) /* For Visual 2005 */
116 # pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */
117 # else /* 32-bits */
118 # pragma intrinsic(_BitScanForward) /* For Visual 2005 */
119 # pragma intrinsic(_BitScanReverse) /* For Visual 2005 */
120 # endif
121 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
122 # pragma warning(disable : 4701) /* disable: C4701: potentially uninitialized local variable used */
123 #else
124 # ifdef __GNUC__
125 # define FORCE_INLINE static inline __attribute__((always_inline))
126 # else
127 # define FORCE_INLINE static inline
128 # endif
129 #endif
130
131 #ifdef _MSC_VER /* Visual Studio */
132 # define lz4_bswap16(x) _byteswap_ushort(x)
133 #else
134 # define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
135 #endif
136
137
138 /**************************************
139 Includes
140 **************************************/
141 #include "lz4hc.h"
142 #include "lz4.h"
143
144
145 /**************************************
146 Basic Types
147 **************************************/
148 #if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */
149 # include <stdint.h>
150 typedef uint8_t BYTE;
151 typedef uint16_t U16;
152 typedef uint32_t U32;
153 typedef int32_t S32;
154 typedef uint64_t U64;
155 #else
156 typedef unsigned char BYTE;
157 typedef unsigned short U16;
158 typedef unsigned int U32;
159 typedef signed int S32;
160 typedef unsigned long long U64;
161 #endif
162
163 #if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS)
164 # define _PACKED __attribute__ ((packed))
165 #else
166 # define _PACKED
167 #endif
168
169 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
170 # ifdef __IBMC__
171 # pragma pack(1)
172 # else
173 # pragma pack(push, 1)
174 # endif
175 #endif
176
177 typedef struct _U16_S { U16 v; } _PACKED U16_S;
178 typedef struct _U32_S { U32 v; } _PACKED U32_S;
179 typedef struct _U64_S { U64 v; } _PACKED U64_S;
180
181 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
182 # pragma pack(pop)
183 #endif
184
185 #define A64(x) (((U64_S *)(x))->v)
186 #define A32(x) (((U32_S *)(x))->v)
187 #define A16(x) (((U16_S *)(x))->v)
188
189
190 /**************************************
191 Constants
192 **************************************/
193 #define MINMATCH 4
194
195 #define DICTIONARY_LOGSIZE 16
196 #define MAXD (1<<DICTIONARY_LOGSIZE)
197 #define MAXD_MASK ((U32)(MAXD - 1))
198 #define MAX_DISTANCE (MAXD - 1)
199
200 #define HASH_LOG (DICTIONARY_LOGSIZE-1)
201 #define HASHTABLESIZE (1 << HASH_LOG)
202 #define HASH_MASK (HASHTABLESIZE - 1)
203
204 #define ML_BITS 4
205 #define ML_MASK (size_t)((1U<<ML_BITS)-1)
206 #define RUN_BITS (8-ML_BITS)
207 #define RUN_MASK ((1U<<RUN_BITS)-1)
208
209 #define COPYLENGTH 8
210 #define LASTLITERALS 5
211 #define MFLIMIT (COPYLENGTH+MINMATCH)
212 #define MINLENGTH (MFLIMIT+1)
213 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
214
215 #define KB *(1U<<10)
216 #define MB *(1U<<20)
217 #define GB *(1U<<30)
218
219
220 /**************************************
221 Architecture-specific macros
222 **************************************/
223 #if LZ4_ARCH64 /* 64-bit */
224 # define STEPSIZE 8
225 # define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8;
226 # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d)
227 # define AARCH A64
228 # define HTYPE U32
229 # define INITBASE(b,s) const BYTE* const b = s
230 #else /* 32-bit */
231 # define STEPSIZE 4
232 # define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4;
233 # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);
234 # define AARCH A32
235 # define HTYPE U32
236 # define INITBASE(b,s) const BYTE* const b = s
237 #endif
238
239 #if defined(LZ4_BIG_ENDIAN)
240 # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
241 # define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }
242 #else /* Little Endian */
243 # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }
244 # define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }
245 #endif
246
247
248 /**************************************
249 Local Types
250 **************************************/
251 typedef struct
252 {
253 const BYTE* inputBuffer;
254 const BYTE* base;
255 const BYTE* end;
256 HTYPE hashTable[HASHTABLESIZE];
257 U16 chainTable[MAXD];
258 const BYTE* nextToUpdate;
259 } LZ4HC_Data_Structure;
260
261
262 /**************************************
263 Macros
264 **************************************/
265 #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);
266 #define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }
267 #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
268 #define HASH_VALUE(p) HASH_FUNCTION(A32(p))
269 #define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base)
270 #define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK]
271 #define GETNEXT(p) ((p) - (size_t)DELTANEXT(p))
272
273
274 /**************************************
275 Private functions
276 **************************************/
277 #if LZ4_ARCH64
278
279 FORCE_INLINE int LZ4_NbCommonBytes (register U64 val)
280 {
281 #if defined(LZ4_BIG_ENDIAN)
282 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
283 unsigned long r = 0;
284 _BitScanReverse64( &r, val );
285 return (int)(r>>3);
286 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
287 return (__builtin_clzll(val) >> 3);
288 # else
289 int r;
290 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
291 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
292 r += (!val);
293 return r;
294 # endif
295 #else
296 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
297 unsigned long r = 0;
298 _BitScanForward64( &r, val );
299 return (int)(r>>3);
300 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
301 return (__builtin_ctzll(val) >> 3);
302 # else
303 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
304 return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];
305 # endif
306 #endif
307 }
308
309 #else
310
311 FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)
312 {
313 #if defined(LZ4_BIG_ENDIAN)
314 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
315 unsigned long r;
316 _BitScanReverse( &r, val );
317 return (int)(r>>3);
318 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
319 return (__builtin_clz(val) >> 3);
320 # else
321 int r;
322 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
323 r += (!val);
324 return r;
325 # endif
326 #else
327 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
328 unsigned long r;
329 _BitScanForward( &r, val );
330 return (int)(r>>3);
331 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
332 return (__builtin_ctz(val) >> 3);
333 # else
334 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
335 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
336 # endif
337 #endif
338 }
339
340 #endif
341
342
343 int LZ4_sizeofStreamStateHC()
344 {
345 return sizeof(LZ4HC_Data_Structure);
346 }
347
348 FORCE_INLINE void LZ4_initHC (LZ4HC_Data_Structure* hc4, const BYTE* base)
349 {
350 MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
351 MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
352 hc4->nextToUpdate = base + 1;
353 hc4->base = base;
354 hc4->inputBuffer = base;
355 hc4->end = base;
356 }
357
358 int LZ4_resetStreamStateHC(void* state, const char* inputBuffer)
359 {
360 if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */
361 LZ4_initHC((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer);
362 return 0;
363 }
364
365
366 void* LZ4_createHC (const char* inputBuffer)
367 {
368 void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));
369 LZ4_initHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer);
370 return hc4;
371 }
372
373
374 int LZ4_freeHC (void* LZ4HC_Data)
375 {
376 FREEMEM(LZ4HC_Data);
377 return (0);
378 }
379
380
381 /* Update chains up to ip (excluded) */
382 FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)
383 {
384 U16* chainTable = hc4->chainTable;
385 HTYPE* HashTable = hc4->hashTable;
386 INITBASE(base,hc4->base);
387
388 while(hc4->nextToUpdate < ip)
389 {
390 const BYTE* const p = hc4->nextToUpdate;
391 size_t delta = (p) - HASH_POINTER(p);
392 if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
393 DELTANEXT(p) = (U16)delta;
394 HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base);
395 hc4->nextToUpdate++;
396 }
397 }
398
399
400 char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
401 {
402 LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data;
403 U32 distance = (U32)(hc4->end - hc4->inputBuffer) - 64 KB;
404 distance = (distance >> 16) << 16; /* Must be a multiple of 64 KB */
405 LZ4HC_Insert(hc4, hc4->end - MINMATCH);
406 memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB);
407 hc4->nextToUpdate -= distance;
408 hc4->base -= distance;
409 if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB) /* Avoid overflow */
410 {
411 int i;
412 hc4->base += 1 GB;
413 for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB;
414 }
415 hc4->end -= distance;
416 return (char*)(hc4->end);
417 }
418
419
420 FORCE_INLINE size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit)
421 {
422 const BYTE* p1t = p1;
423
424 while (p1t<matchlimit-(STEPSIZE-1))
425 {
426 size_t diff = AARCH(p2) ^ AARCH(p1t);
427 if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; }
428 p1t += LZ4_NbCommonBytes(diff);
429 return (p1t - p1);
430 }
431 if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; }
432 if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; }
433 if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++;
434 return (p1t - p1);
435 }
436
437
438 FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos, const int maxNbAttempts)
439 {
440 U16* const chainTable = hc4->chainTable;
441 HTYPE* const HashTable = hc4->hashTable;
442 const BYTE* ref;
443 INITBASE(base,hc4->base);
444 int nbAttempts=maxNbAttempts;
445 size_t repl=0, ml=0;
446 U16 delta=0; /* useless assignment, to remove an uninitialization warning */
447
448 /* HC4 match finder */
449 LZ4HC_Insert(hc4, ip);
450 ref = HASH_POINTER(ip);
451
452 #define REPEAT_OPTIMIZATION
453 #ifdef REPEAT_OPTIMIZATION
454 /* Detect repetitive sequences of length <= 4 */
455 if ((U32)(ip-ref) <= 4) /* potential repetition */
456 {
457 if (A32(ref) == A32(ip)) /* confirmed */
458 {
459 delta = (U16)(ip-ref);
460 repl = ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;
461 *matchpos = ref;
462 }
463 ref = GETNEXT(ref);
464 }
465 #endif
466
467 while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))
468 {
469 nbAttempts--;
470 if (*(ref+ml) == *(ip+ml))
471 if (A32(ref) == A32(ip))
472 {
473 size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;
474 if (mlt > ml) { ml = mlt; *matchpos = ref; }
475 }
476 ref = GETNEXT(ref);
477 }
478
479 #ifdef REPEAT_OPTIMIZATION
480 /* Complete table */
481 if (repl)
482 {
483 const BYTE* ptr = ip;
484 const BYTE* end;
485
486 end = ip + repl - (MINMATCH-1);
487 while(ptr < end-delta)
488 {
489 DELTANEXT(ptr) = delta; /* Pre-Load */
490 ptr++;
491 }
492 do
493 {
494 DELTANEXT(ptr) = delta;
495 HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); /* Head of chain */
496 ptr++;
497 } while(ptr < end);
498 hc4->nextToUpdate = end;
499 }
500 #endif
501
502 return (int)ml;
503 }
504
505
506 FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos, const int maxNbAttempts)
507 {
508 U16* const chainTable = hc4->chainTable;
509 HTYPE* const HashTable = hc4->hashTable;
510 INITBASE(base,hc4->base);
511 const BYTE* ref;
512 int nbAttempts = maxNbAttempts;
513 int delta = (int)(ip-startLimit);
514
515 /* First Match */
516 LZ4HC_Insert(hc4, ip);
517 ref = HASH_POINTER(ip);
518
519 while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))
520 {
521 nbAttempts--;
522 if (*(startLimit + longest) == *(ref - delta + longest))
523 if (A32(ref) == A32(ip))
524 {
525 #if 1
526 const BYTE* reft = ref+MINMATCH;
527 const BYTE* ipt = ip+MINMATCH;
528 const BYTE* startt = ip;
529
530 while (ipt<matchlimit-(STEPSIZE-1))
531 {
532 size_t diff = AARCH(reft) ^ AARCH(ipt);
533 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }
534 ipt += LZ4_NbCommonBytes(diff);
535 goto _endCount;
536 }
537 if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }
538 if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }
539 if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;
540 _endCount:
541 reft = ref;
542 #else
543 /* Easier for code maintenance, but unfortunately slower too */
544 const BYTE* startt = ip;
545 const BYTE* reft = ref;
546 const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit);
547 #endif
548
549 while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;}
550
551 if ((ipt-startt) > longest)
552 {
553 longest = (int)(ipt-startt);
554 *matchpos = reft;
555 *startpos = startt;
556 }
557 }
558 ref = GETNEXT(ref);
559 }
560
561 return longest;
562 }
563
564
565 typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive;
566
567 FORCE_INLINE int LZ4HC_encodeSequence (
568 const BYTE** ip,
569 BYTE** op,
570 const BYTE** anchor,
571 int matchLength,
572 const BYTE* ref,
573 limitedOutput_directive limitedOutputBuffer,
574 BYTE* oend)
575 {
576 int length;
577 BYTE* token;
578
579 /* Encode Literal length */
580 length = (int)(*ip - *anchor);
581 token = (*op)++;
582 if ((limitedOutputBuffer) && ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > oend)) return 1; /* Check output limit */
583 if (length>=(int)RUN_MASK) { int len; *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; }
584 else *token = (BYTE)(length<<ML_BITS);
585
586 /* Copy Literals */
587 LZ4_BLINDCOPY(*anchor, *op, length);
588
589 /* Encode Offset */
590 LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));
591
592 /* Encode MatchLength */
593 length = (int)(matchLength-MINMATCH);
594 if ((limitedOutputBuffer) && (*op + (1 + LASTLITERALS) + (length>>8) > oend)) return 1; /* Check output limit */
595 if (length>=(int)ML_MASK) { *token+=ML_MASK; length-=ML_MASK; for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (length > 254) { length-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)length; }
596 else *token += (BYTE)(length);
597
598 /* Prepare next loop */
599 *ip += matchLength;
600 *anchor = *ip;
601
602 return 0;
603 }
604
605
606 #define MAX_COMPRESSION_LEVEL 16
607 static int LZ4HC_compress_generic (
608 void* ctxvoid,
609 const char* source,
610 char* dest,
611 int inputSize,
612 int maxOutputSize,
613 int compressionLevel,
614 limitedOutput_directive limit
615 )
616 {
617 LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid;
618 const BYTE* ip = (const BYTE*) source;
619 const BYTE* anchor = ip;
620 const BYTE* const iend = ip + inputSize;
621 const BYTE* const mflimit = iend - MFLIMIT;
622 const BYTE* const matchlimit = (iend - LASTLITERALS);
623
624 BYTE* op = (BYTE*) dest;
625 BYTE* const oend = op + maxOutputSize;
626
627 const int maxNbAttempts = compressionLevel > MAX_COMPRESSION_LEVEL ? 1 << MAX_COMPRESSION_LEVEL : compressionLevel ? 1<<(compressionLevel-1) : 1<<LZ4HC_DEFAULT_COMPRESSIONLEVEL;
628 int ml, ml2, ml3, ml0;
629 const BYTE* ref=NULL;
630 const BYTE* start2=NULL;
631 const BYTE* ref2=NULL;
632 const BYTE* start3=NULL;
633 const BYTE* ref3=NULL;
634 const BYTE* start0;
635 const BYTE* ref0;
636
637
638 /* Ensure blocks follow each other */
639 if (ip != ctx->end) return 0;
640 ctx->end += inputSize;
641
642 ip++;
643
644 /* Main Loop */
645 while (ip < mflimit)
646 {
647 ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref), maxNbAttempts);
648 if (!ml) { ip++; continue; }
649
650 /* saved, in case we would skip too much */
651 start0 = ip;
652 ref0 = ref;
653 ml0 = ml;
654
655 _Search2:
656 if (ip+ml < mflimit)
657 ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2, maxNbAttempts);
658 else ml2 = ml;
659
660 if (ml2 == ml) /* No better match */
661 {
662 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
663 continue;
664 }
665
666 if (start0 < ip)
667 {
668 if (start2 < ip + ml0) /* empirical */
669 {
670 ip = start0;
671 ref = ref0;
672 ml = ml0;
673 }
674 }
675
676 /* Here, start0==ip */
677 if ((start2 - ip) < 3) /* First Match too small : removed */
678 {
679 ml = ml2;
680 ip = start2;
681 ref =ref2;
682 goto _Search2;
683 }
684
685 _Search3:
686 /*
687 * Currently we have :
688 * ml2 > ml1, and
689 * ip1+3 <= ip2 (usually < ip1+ml1)
690 */
691 if ((start2 - ip) < OPTIMAL_ML)
692 {
693 int correction;
694 int new_ml = ml;
695 if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
696 if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
697 correction = new_ml - (int)(start2 - ip);
698 if (correction > 0)
699 {
700 start2 += correction;
701 ref2 += correction;
702 ml2 -= correction;
703 }
704 }
705 /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */
706
707 if (start2 + ml2 < mflimit)
708 ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts);
709 else ml3 = ml2;
710
711 if (ml3 == ml2) /* No better match : 2 sequences to encode */
712 {
713 /* ip & ref are known; Now for ml */
714 if (start2 < ip+ml) ml = (int)(start2 - ip);
715 /* Now, encode 2 sequences */
716 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
717 ip = start2;
718 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;
719 continue;
720 }
721
722 if (start3 < ip+ml+3) /* Not enough space for match 2 : remove it */
723 {
724 if (start3 >= (ip+ml)) /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */
725 {
726 if (start2 < ip+ml)
727 {
728 int correction = (int)(ip+ml - start2);
729 start2 += correction;
730 ref2 += correction;
731 ml2 -= correction;
732 if (ml2 < MINMATCH)
733 {
734 start2 = start3;
735 ref2 = ref3;
736 ml2 = ml3;
737 }
738 }
739
740 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
741 ip = start3;
742 ref = ref3;
743 ml = ml3;
744
745 start0 = start2;
746 ref0 = ref2;
747 ml0 = ml2;
748 goto _Search2;
749 }
750
751 start2 = start3;
752 ref2 = ref3;
753 ml2 = ml3;
754 goto _Search3;
755 }
756
757 /*
758 * OK, now we have 3 ascending matches; let's write at least the first one
759 * ip & ref are known; Now for ml
760 */
761 if (start2 < ip+ml)
762 {
763 if ((start2 - ip) < (int)ML_MASK)
764 {
765 int correction;
766 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
767 if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
768 correction = ml - (int)(start2 - ip);
769 if (correction > 0)
770 {
771 start2 += correction;
772 ref2 += correction;
773 ml2 -= correction;
774 }
775 }
776 else
777 {
778 ml = (int)(start2 - ip);
779 }
780 }
781 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
782
783 ip = start2;
784 ref = ref2;
785 ml = ml2;
786
787 start2 = start3;
788 ref2 = ref3;
789 ml2 = ml3;
790
791 goto _Search3;
792
793 }
794
795 /* Encode Last Literals */
796 {
797 int lastRun = (int)(iend - anchor);
798 if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
799 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
800 else *op++ = (BYTE)(lastRun<<ML_BITS);
801 memcpy(op, anchor, iend - anchor);
802 op += iend-anchor;
803 }
804
805 /* End */
806 return (int) (((char*)op)-dest);
807 }
808
809
810 int LZ4_compressHC2(const char* source, char* dest, int inputSize, int compressionLevel)
811 {
812 void* ctx = LZ4_createHC(source);
813 int result;
814 if (ctx==NULL) return 0;
815
816 result = LZ4HC_compress_generic (ctx, source, dest, inputSize, 0, compressionLevel, noLimit);
817
818 LZ4_freeHC(ctx);
819 return result;
820 }
821
822 int LZ4_compressHC(const char* source, char* dest, int inputSize) { return LZ4_compressHC2(source, dest, inputSize, 0); }
823
824 int LZ4_compressHC2_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
825 {
826 void* ctx = LZ4_createHC(source);
827 int result;
828 if (ctx==NULL) return 0;
829
830 result = LZ4HC_compress_generic (ctx, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
831
832 LZ4_freeHC(ctx);
833 return result;
834 }
835
836 int LZ4_compressHC_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
837 {
838 return LZ4_compressHC2_limitedOutput(source, dest, inputSize, maxOutputSize, 0);
839 }
840
841
842 /*****************************
843 Using external allocation
844 *****************************/
845 int LZ4_sizeofStateHC() { return sizeof(LZ4HC_Data_Structure); }
846
847
848 int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel)
849 {
850 if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */
851 LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);
852 return LZ4HC_compress_generic (state, source, dest, inputSize, 0, compressionLevel, noLimit);
853 }
854
855 int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize)
856 { return LZ4_compressHC2_withStateHC (state, source, dest, inputSize, 0); }
857
858
859 int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
860 {
861 if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */
862 LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);
863 return LZ4HC_compress_generic (state, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
864 }
865
866 int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize)
867 { return LZ4_compressHC2_limitedOutput_withStateHC (state, source, dest, inputSize, maxOutputSize, 0); }
868
869
870 /****************************
871 Stream functions
872 ****************************/
873
874 int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize)
875 {
876 return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, 0, noLimit);
877 }
878
879 int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel)
880 {
881 return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, compressionLevel, noLimit);
882 }
883
884 int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize)
885 {
886 return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, 0, limitedOutput);
887 }
888
889 int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
890 {
891 return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
892 }