1 | /* |
2 | LZ4 HC - High Compression Mode of LZ4 |
3 | Copyright (C) 2011-2013, 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 | Note : this source file requires "lz4hc_encoder.h" |
36 | */ |
37 | |
38 | |
39 | //************************************** |
40 | // Memory routines |
41 | //************************************** |
42 | #include <stdlib.h> // calloc, free |
43 | #define ALLOCATOR(s) calloc(1,s) |
44 | #define FREEMEM free |
45 | #include <string.h> // memset, memcpy |
46 | #define MEM_INIT memset |
47 | |
48 | |
49 | //************************************** |
50 | // CPU Feature Detection |
51 | //************************************** |
52 | // 32 or 64 bits ? |
53 | #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \ |
54 | || defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \ |
55 | || defined(__64BIT__) || defined(_LP64) || defined(__LP64__) \ |
56 | || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) // Detects 64 bits mode |
57 | # define LZ4_ARCH64 1 |
58 | #else |
59 | # define LZ4_ARCH64 0 |
60 | #endif |
61 | |
62 | // Little Endian or Big Endian ? |
63 | // Overwrite the #define below if you know your architecture endianess |
64 | #if defined (__GLIBC__) |
65 | # include <endian.h> |
66 | # if (__BYTE_ORDER == __BIG_ENDIAN) |
67 | # define LZ4_BIG_ENDIAN 1 |
68 | # endif |
69 | #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN)) |
70 | # define LZ4_BIG_ENDIAN 1 |
71 | #elif defined(__sparc) || defined(__sparc__) \ |
72 | || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \ |
73 | || defined(__hpux) || defined(__hppa) \ |
74 | || defined(_MIPSEB) || defined(__s390__) |
75 | # define LZ4_BIG_ENDIAN 1 |
76 | #else |
77 | // Little Endian assumed. PDP Endian and other very rare endian format are unsupported. |
78 | #endif |
79 | |
80 | // Unaligned memory access is automatically enabled for "common" CPU, such as x86. |
81 | // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected |
82 | // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance |
83 | #if defined(__ARM_FEATURE_UNALIGNED) |
84 | # define LZ4_FORCE_UNALIGNED_ACCESS 1 |
85 | #endif |
86 | |
87 | // Define this parameter if your target system or compiler does not support hardware bit count |
88 | #if defined(_MSC_VER) && defined(_WIN32_WCE) // Visual Studio for Windows CE does not support Hardware bit count |
89 | # define LZ4_FORCE_SW_BITCOUNT |
90 | #endif |
91 | |
92 | |
93 | //************************************** |
94 | // Compiler Options |
95 | //************************************** |
96 | #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 |
97 | /* "restrict" is a known keyword */ |
98 | #else |
99 | # define restrict // Disable restrict |
100 | #endif |
101 | |
102 | #ifdef _MSC_VER |
103 | # define forceinline __forceinline |
104 | # include <intrin.h> // For Visual 2005 |
105 | # if LZ4_ARCH64 // 64-bits |
106 | # pragma intrinsic(_BitScanForward64) // For Visual 2005 |
107 | # pragma intrinsic(_BitScanReverse64) // For Visual 2005 |
108 | # else // 32-bits |
109 | # pragma intrinsic(_BitScanForward) // For Visual 2005 |
110 | # pragma intrinsic(_BitScanReverse) // For Visual 2005 |
111 | # endif |
112 | # pragma warning(disable : 4127) // disable: C4127: conditional expression is constant |
113 | # pragma warning(disable : 4701) // disable: C4701: potentially uninitialized local variable used |
114 | #else |
115 | # ifdef __GNUC__ |
116 | # define forceinline inline __attribute__((always_inline)) |
117 | # else |
118 | # define forceinline inline |
119 | # endif |
120 | #endif |
121 | |
122 | #ifdef _MSC_VER // Visual Studio |
123 | #define lz4_bswap16(x) _byteswap_ushort(x) |
124 | #else |
125 | #define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8))) |
126 | #endif |
127 | |
128 | |
129 | //************************************** |
130 | // Includes |
131 | //************************************** |
132 | #include "lz4hc.h" |
133 | #include "lz4.h" |
134 | |
135 | |
136 | //************************************** |
137 | // Basic Types |
138 | //************************************** |
139 | #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 |
140 | # include <stdint.h> |
141 | typedef uint8_t BYTE; |
142 | typedef uint16_t U16; |
143 | typedef uint32_t U32; |
144 | typedef int32_t S32; |
145 | typedef uint64_t U64; |
146 | #else |
147 | typedef unsigned char BYTE; |
148 | typedef unsigned short U16; |
149 | typedef unsigned int U32; |
150 | typedef signed int S32; |
151 | typedef unsigned long long U64; |
152 | #endif |
153 | |
154 | #if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS) |
155 | # define _PACKED __attribute__ ((packed)) |
156 | #else |
157 | # define _PACKED |
158 | #endif |
159 | |
160 | #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) |
161 | # ifdef __IBMC__ |
162 | # pragma pack(1) |
163 | # else |
164 | # pragma pack(push, 1) |
165 | # endif |
166 | #endif |
167 | |
168 | typedef struct _U16_S { U16 v; } _PACKED U16_S; |
169 | typedef struct _U32_S { U32 v; } _PACKED U32_S; |
170 | typedef struct _U64_S { U64 v; } _PACKED U64_S; |
171 | |
172 | #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) |
173 | # pragma pack(pop) |
174 | #endif |
175 | |
176 | #define A64(x) (((U64_S *)(x))->v) |
177 | #define A32(x) (((U32_S *)(x))->v) |
178 | #define A16(x) (((U16_S *)(x))->v) |
179 | |
180 | |
181 | //************************************** |
182 | // Constants |
183 | //************************************** |
184 | #define MINMATCH 4 |
185 | |
186 | #define DICTIONARY_LOGSIZE 16 |
187 | #define MAXD (1<<DICTIONARY_LOGSIZE) |
188 | #define MAXD_MASK ((U32)(MAXD - 1)) |
189 | #define MAX_DISTANCE (MAXD - 1) |
190 | |
191 | #define HASH_LOG (DICTIONARY_LOGSIZE-1) |
192 | #define HASHTABLESIZE (1 << HASH_LOG) |
193 | #define HASH_MASK (HASHTABLESIZE - 1) |
194 | |
195 | #define MAX_NB_ATTEMPTS 256 |
196 | |
197 | #define ML_BITS 4 |
198 | #define ML_MASK (size_t)((1U<<ML_BITS)-1) |
199 | #define RUN_BITS (8-ML_BITS) |
200 | #define RUN_MASK ((1U<<RUN_BITS)-1) |
201 | |
202 | #define COPYLENGTH 8 |
203 | #define LASTLITERALS 5 |
204 | #define MFLIMIT (COPYLENGTH+MINMATCH) |
205 | #define MINLENGTH (MFLIMIT+1) |
206 | #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) |
207 | |
208 | #define KB *(1U<<10) |
209 | #define MB *(1U<<20) |
210 | #define GB *(1U<<30) |
211 | |
212 | |
213 | //************************************** |
214 | // Architecture-specific macros |
215 | //************************************** |
216 | #if LZ4_ARCH64 // 64-bit |
217 | # define STEPSIZE 8 |
218 | # define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; |
219 | # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) |
220 | # define UARCH U64 |
221 | # define AARCH A64 |
222 | # define HTYPE U32 |
223 | # define INITBASE(b,s) const BYTE* const b = s |
224 | #else // 32-bit |
225 | # define STEPSIZE 4 |
226 | # define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4; |
227 | # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d); |
228 | # define UARCH U32 |
229 | # define AARCH A32 |
230 | //# define HTYPE const BYTE* |
231 | //# define INITBASE(b,s) const int b = 0 |
232 | # define HTYPE U32 |
233 | # define INITBASE(b,s) const BYTE* const b = s |
234 | #endif |
235 | |
236 | #if defined(LZ4_BIG_ENDIAN) |
237 | # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } |
238 | # define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; } |
239 | #else // Little Endian |
240 | # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } |
241 | # define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } |
242 | #endif |
243 | |
244 | |
245 | //************************************************************ |
246 | // Local Types |
247 | //************************************************************ |
248 | typedef struct |
249 | { |
250 | const BYTE* inputBuffer; |
251 | const BYTE* base; |
252 | const BYTE* end; |
253 | HTYPE hashTable[HASHTABLESIZE]; |
254 | U16 chainTable[MAXD]; |
255 | const BYTE* nextToUpdate; |
256 | } LZ4HC_Data_Structure; |
257 | |
258 | |
259 | //************************************** |
260 | // Macros |
261 | //************************************** |
262 | #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e); |
263 | #define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; } |
264 | #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG)) |
265 | #define HASH_VALUE(p) HASH_FUNCTION(A32(p)) |
266 | #define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base) |
267 | #define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK] |
268 | #define GETNEXT(p) ((p) - (size_t)DELTANEXT(p)) |
269 | |
270 | |
271 | //************************************** |
272 | // Private functions |
273 | //************************************** |
274 | #if LZ4_ARCH64 |
275 | |
276 | inline static int LZ4_NbCommonBytes (register U64 val) |
277 | { |
278 | #if defined(LZ4_BIG_ENDIAN) |
279 | # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
280 | unsigned long r = 0; |
281 | _BitScanReverse64( &r, val ); |
282 | return (int)(r>>3); |
283 | # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
284 | return (__builtin_clzll(val) >> 3); |
285 | # else |
286 | int r; |
287 | if (!(val>>32)) { r=4; } else { r=0; val>>=32; } |
288 | if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } |
289 | r += (!val); |
290 | return r; |
291 | # endif |
292 | #else |
293 | # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
294 | unsigned long r = 0; |
295 | _BitScanForward64( &r, val ); |
296 | return (int)(r>>3); |
297 | # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
298 | return (__builtin_ctzll(val) >> 3); |
299 | # else |
300 | 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 }; |
301 | return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58]; |
302 | # endif |
303 | #endif |
304 | } |
305 | |
306 | #else |
307 | |
308 | inline static int LZ4_NbCommonBytes (register U32 val) |
309 | { |
310 | #if defined(LZ4_BIG_ENDIAN) |
311 | # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
312 | unsigned long r; |
313 | _BitScanReverse( &r, val ); |
314 | return (int)(r>>3); |
315 | # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
316 | return (__builtin_clz(val) >> 3); |
317 | # else |
318 | int r; |
319 | if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } |
320 | r += (!val); |
321 | return r; |
322 | # endif |
323 | #else |
324 | # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
325 | unsigned long r; |
326 | _BitScanForward( &r, val ); |
327 | return (int)(r>>3); |
328 | # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
329 | return (__builtin_ctz(val) >> 3); |
330 | # else |
331 | 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 }; |
332 | return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; |
333 | # endif |
334 | #endif |
335 | } |
336 | |
337 | #endif |
338 | |
339 | |
340 | static inline int LZ4_InitHC (LZ4HC_Data_Structure* hc4, const BYTE* base) |
341 | { |
342 | MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); |
343 | MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); |
344 | hc4->nextToUpdate = base + 1; |
345 | hc4->base = base; |
346 | hc4->inputBuffer = base; |
347 | hc4->end = base; |
348 | return 1; |
349 | } |
350 | |
351 | |
352 | void* LZ4_createHC (const char* slidingInputBuffer) |
353 | { |
354 | void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure)); |
355 | LZ4_InitHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)slidingInputBuffer); |
356 | return hc4; |
357 | } |
358 | |
359 | |
360 | int LZ4_freeHC (void* LZ4HC_Data) |
361 | { |
362 | FREEMEM(LZ4HC_Data); |
363 | return (0); |
364 | } |
365 | |
366 | |
367 | // Update chains up to ip (excluded) |
368 | static forceinline void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) |
369 | { |
370 | U16* chainTable = hc4->chainTable; |
371 | HTYPE* HashTable = hc4->hashTable; |
372 | INITBASE(base,hc4->base); |
373 | |
374 | while(hc4->nextToUpdate < ip) |
375 | { |
376 | const BYTE* const p = hc4->nextToUpdate; |
377 | size_t delta = (p) - HASH_POINTER(p); |
378 | if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; |
379 | DELTANEXT(p) = (U16)delta; |
380 | HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base); |
381 | hc4->nextToUpdate++; |
382 | } |
383 | } |
384 | |
385 | |
386 | char* LZ4_slideInputBufferHC(void* LZ4HC_Data) |
387 | { |
388 | LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data; |
389 | U32 distance = (U32)(hc4->end - hc4->inputBuffer) - 64 KB; |
390 | distance = (distance >> 16) << 16; // Must be a multiple of 64 KB |
391 | LZ4HC_Insert(hc4, hc4->end - MINMATCH); |
392 | memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB); |
393 | hc4->nextToUpdate -= distance; |
394 | hc4->base -= distance; |
395 | if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB) // Avoid overflow |
396 | { |
397 | int i; |
398 | hc4->base += 1 GB; |
399 | for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB; |
400 | } |
401 | hc4->end -= distance; |
402 | return (char*)(hc4->end); |
403 | } |
404 | |
405 | |
406 | static forceinline size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit) |
407 | { |
408 | const BYTE* p1t = p1; |
409 | |
410 | while (p1t<matchlimit-(STEPSIZE-1)) |
411 | { |
412 | UARCH diff = AARCH(p2) ^ AARCH(p1t); |
413 | if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; } |
414 | p1t += LZ4_NbCommonBytes(diff); |
415 | return (p1t - p1); |
416 | } |
417 | if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; } |
418 | if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; } |
419 | if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++; |
420 | return (p1t - p1); |
421 | } |
422 | |
423 | |
424 | static forceinline int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos) |
425 | { |
426 | U16* const chainTable = hc4->chainTable; |
427 | HTYPE* const HashTable = hc4->hashTable; |
428 | const BYTE* ref; |
429 | INITBASE(base,hc4->base); |
430 | int nbAttempts=MAX_NB_ATTEMPTS; |
431 | size_t repl=0, ml=0; |
432 | U16 delta=0; // useless assignment, to remove an uninitialization warning |
433 | |
434 | // HC4 match finder |
435 | LZ4HC_Insert(hc4, ip); |
436 | ref = HASH_POINTER(ip); |
437 | |
438 | #define REPEAT_OPTIMIZATION |
439 | #ifdef REPEAT_OPTIMIZATION |
440 | // Detect repetitive sequences of length <= 4 |
441 | if ((U32)(ip-ref) <= 4) // potential repetition |
442 | { |
443 | if (A32(ref) == A32(ip)) // confirmed |
444 | { |
445 | delta = (U16)(ip-ref); |
446 | repl = ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; |
447 | *matchpos = ref; |
448 | } |
449 | ref = GETNEXT(ref); |
450 | } |
451 | #endif |
452 | |
453 | while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) |
454 | { |
455 | nbAttempts--; |
456 | if (*(ref+ml) == *(ip+ml)) |
457 | if (A32(ref) == A32(ip)) |
458 | { |
459 | size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; |
460 | if (mlt > ml) { ml = mlt; *matchpos = ref; } |
461 | } |
462 | ref = GETNEXT(ref); |
463 | } |
464 | |
465 | #ifdef REPEAT_OPTIMIZATION |
466 | // Complete table |
467 | if (repl) |
468 | { |
469 | const BYTE* ptr = ip; |
470 | const BYTE* end; |
471 | |
472 | end = ip + repl - (MINMATCH-1); |
473 | while(ptr < end-delta) |
474 | { |
475 | DELTANEXT(ptr) = delta; // Pre-Load |
476 | ptr++; |
477 | } |
478 | do |
479 | { |
480 | DELTANEXT(ptr) = delta; |
481 | HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); // Head of chain |
482 | ptr++; |
483 | } while(ptr < end); |
484 | hc4->nextToUpdate = end; |
485 | } |
486 | #endif |
487 | |
488 | return (int)ml; |
489 | } |
490 | |
491 | |
492 | static forceinline int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos) |
493 | { |
494 | U16* const chainTable = hc4->chainTable; |
495 | HTYPE* const HashTable = hc4->hashTable; |
496 | INITBASE(base,hc4->base); |
497 | const BYTE* ref; |
498 | int nbAttempts = MAX_NB_ATTEMPTS; |
499 | int delta = (int)(ip-startLimit); |
500 | |
501 | // First Match |
502 | LZ4HC_Insert(hc4, ip); |
503 | ref = HASH_POINTER(ip); |
504 | |
505 | while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) |
506 | { |
507 | nbAttempts--; |
508 | if (*(startLimit + longest) == *(ref - delta + longest)) |
509 | if (A32(ref) == A32(ip)) |
510 | { |
511 | #if 1 |
512 | const BYTE* reft = ref+MINMATCH; |
513 | const BYTE* ipt = ip+MINMATCH; |
514 | const BYTE* startt = ip; |
515 | |
516 | while (ipt<matchlimit-(STEPSIZE-1)) |
517 | { |
518 | UARCH diff = AARCH(reft) ^ AARCH(ipt); |
519 | if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; } |
520 | ipt += LZ4_NbCommonBytes(diff); |
521 | goto _endCount; |
522 | } |
523 | if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; } |
524 | if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; } |
525 | if ((ipt<matchlimit) && (*reft == *ipt)) ipt++; |
526 | _endCount: |
527 | reft = ref; |
528 | #else |
529 | // Easier for code maintenance, but unfortunately slower too |
530 | const BYTE* startt = ip; |
531 | const BYTE* reft = ref; |
532 | const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit); |
533 | #endif |
534 | |
535 | while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;} |
536 | |
537 | if ((ipt-startt) > longest) |
538 | { |
539 | longest = (int)(ipt-startt); |
540 | *matchpos = reft; |
541 | *startpos = startt; |
542 | } |
543 | } |
544 | ref = GETNEXT(ref); |
545 | } |
546 | |
547 | return longest; |
548 | } |
549 | |
550 | |
551 | |
552 | //************************************** |
553 | // Compression functions |
554 | //************************************** |
555 | |
556 | /* |
557 | int LZ4_compressHC( |
558 | const char* source, |
559 | char* dest, |
560 | int inputSize) |
561 | |
562 | Compress 'inputSize' bytes from 'source' into an output buffer 'dest'. |
563 | Destination buffer must be already allocated, and sized at a minimum of LZ4_compressBound(inputSize). |
564 | return : the number of bytes written in buffer 'dest' |
565 | */ |
566 | #define FUNCTION_NAME LZ4_compressHC |
567 | #include "lz4hc_encoder.h" |
568 | |
569 | |
570 | /* |
571 | int LZ4_compressHC_limitedOutput( |
572 | const char* source, |
573 | char* dest, |
574 | int inputSize, |
575 | int maxOutputSize) |
576 | |
577 | Compress 'inputSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'. |
578 | If it cannot achieve it, compression will stop, and result of the function will be zero. |
579 | return : the number of bytes written in buffer 'dest', or 0 if the compression fails |
580 | */ |
581 | #define FUNCTION_NAME LZ4_compressHC_limitedOutput |
582 | #define LIMITED_OUTPUT |
583 | #include "lz4hc_encoder.h" |
584 | |
585 | |