summaryrefslogtreecommitdiff
path: root/src/static_libs
diff options
context:
space:
mode:
authorVincent Torri <vincent.torri@gmail.com>2012-11-01 16:58:56 +0000
committerVincent Torri <vincent.torri@gmail.com>2012-11-01 16:58:56 +0000
commit109efca5cb77a6260330e89856af05425429ea71 (patch)
tree2ac4c02a3abf59b44f77174a27f466f485e2bcf4 /src/static_libs
parent5b00d44ec6c847af582b2e31ec2fe0a28b8a3a51 (diff)
merge: move lz4 to src/static_libs/lz4 (same will hold for evas' linebreak), ignore++--
SVN revision: 78807
Diffstat (limited to 'src/static_libs')
-rw-r--r--src/static_libs/lz4/README7
-rw-r--r--src/static_libs/lz4/lz4.c863
-rw-r--r--src/static_libs/lz4/lz4.h117
-rw-r--r--src/static_libs/lz4/lz4hc.c671
-rw-r--r--src/static_libs/lz4/lz4hc.h60
5 files changed, 1718 insertions, 0 deletions
diff --git a/src/static_libs/lz4/README b/src/static_libs/lz4/README
new file mode 100644
index 0000000..0abb857
--- /dev/null
+++ b/src/static_libs/lz4/README
@@ -0,0 +1,7 @@
1This iz the lz4 tree copied in:
2 http://lz4.googlecode.com/svn/trunk
3by:
4 yann.collet.73@gmail.com
5Copyright/licensing info in source files here.
6
7this was from revsion 66.
diff --git a/src/static_libs/lz4/lz4.c b/src/static_libs/lz4/lz4.c
new file mode 100644
index 0000000..eeefa67
--- /dev/null
+++ b/src/static_libs/lz4/lz4.c
@@ -0,0 +1,863 @@
1/*
2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2012, 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// Tuning parameters
36//**************************************
37// MEMORY_USAGE :
38// Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
39// Increasing memory usage improves compression ratio
40// Reduced memory usage can improve speed, due to cache effect
41// Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache
42#define MEMORY_USAGE 14
43
44// NOTCOMPRESSIBLE_DETECTIONLEVEL :
45// Decreasing this value will make the algorithm skip faster data segments considered "incompressible"
46// This may decrease compression ratio dramatically, but will be faster on incompressible data
47// Increasing this value will make the algorithm search more before declaring a segment "incompressible"
48// This could improve compression a bit, but will be slower on incompressible data
49// The default value (6) is recommended
50#define NOTCOMPRESSIBLE_DETECTIONLEVEL 6
51
52// BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :
53// This will provide a small boost to performance for big endian cpu, but the resulting compressed stream will be incompatible with little-endian CPU.
54// You can set this option to 1 in situations where data will remain within closed environment
55// This option is useless on Little_Endian CPU (such as x86)
56//#define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1
57
58
59
60//**************************************
61// CPU Feature Detection
62//**************************************
63// 32 or 64 bits ?
64#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) ) // Detects 64 bits mode
65# define LZ4_ARCH64 1
66#else
67# define LZ4_ARCH64 0
68#endif
69
70// Little Endian or Big Endian ?
71// Note : overwrite the below #define if you know your architecture endianess
72#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) || ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))) )
73# define LZ4_BIG_ENDIAN 1
74#else
75// Little Endian assumed. PDP Endian and other very rare endian format are unsupported.
76#endif
77
78// Unaligned memory access is automatically enabled for "common" CPU, such as x86.
79// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected
80// If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance
81#if defined(__ARM_FEATURE_UNALIGNED)
82# define LZ4_FORCE_UNALIGNED_ACCESS 1
83#endif
84
85// Define this parameter if your target system or compiler does not support hardware bit count
86#if defined(_MSC_VER) && defined(_WIN32_WCE) // Visual Studio for Windows CE does not support Hardware bit count
87# define LZ4_FORCE_SW_BITCOUNT
88#endif
89
90
91//**************************************
92// Compiler Options
93//**************************************
94#if __STDC_VERSION__ >= 199901L // C99
95/* "restrict" is a known keyword */
96#else
97# define restrict // Disable restrict
98#endif
99
100#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
101
102#ifdef _MSC_VER // Visual Studio
103# define inline __forceinline // Visual is not C99, but supports some kind of inline
104# include <intrin.h> // For Visual 2005
105# if LZ4_ARCH64 // 64-bit
106# pragma intrinsic(_BitScanForward64) // For Visual 2005
107# pragma intrinsic(_BitScanReverse64) // For Visual 2005
108# else
109# pragma intrinsic(_BitScanForward) // For Visual 2005
110# pragma intrinsic(_BitScanReverse) // For Visual 2005
111# endif
112#endif
113
114#ifdef _MSC_VER
115# define lz4_bswap16(x) _byteswap_ushort(x)
116#else
117# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
118#endif
119
120#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
121# define expect(expr,value) (__builtin_expect ((expr),(value)) )
122#else
123# define expect(expr,value) (expr)
124#endif
125
126#define likely(expr) expect((expr) != 0, 1)
127#define unlikely(expr) expect((expr) != 0, 0)
128
129
130//**************************************
131// Includes
132//**************************************
133#include <stdlib.h> // for malloc
134#include <string.h> // for memset
135#include "lz4.h"
136
137
138//**************************************
139// Basic Types
140//**************************************
141#if defined(_MSC_VER) // Visual Studio does not support 'stdint' natively
142# define BYTE unsigned __int8
143# define U16 unsigned __int16
144# define U32 unsigned __int32
145# define S32 __int32
146# define U64 unsigned __int64
147#else
148# include <stdint.h>
149# define BYTE uint8_t
150# define U16 uint16_t
151# define U32 uint32_t
152# define S32 int32_t
153# define U64 uint64_t
154#endif
155
156#ifndef LZ4_FORCE_UNALIGNED_ACCESS
157# pragma pack(push, 1)
158#endif
159
160typedef struct _U16_S { U16 v; } U16_S;
161typedef struct _U32_S { U32 v; } U32_S;
162typedef struct _U64_S { U64 v; } U64_S;
163
164#ifndef LZ4_FORCE_UNALIGNED_ACCESS
165# pragma pack(pop)
166#endif
167
168#define A64(x) (((U64_S *)(x))->v)
169#define A32(x) (((U32_S *)(x))->v)
170#define A16(x) (((U16_S *)(x))->v)
171
172
173//**************************************
174// Constants
175//**************************************
176#define MINMATCH 4
177
178#define HASH_LOG (MEMORY_USAGE-2)
179#define HASHTABLESIZE (1 << HASH_LOG)
180#define HASH_MASK (HASHTABLESIZE - 1)
181
182#define SKIPSTRENGTH (NOTCOMPRESSIBLE_DETECTIONLEVEL>2?NOTCOMPRESSIBLE_DETECTIONLEVEL:2)
183#define STACKLIMIT 13
184#define HEAPMODE (HASH_LOG>STACKLIMIT) // Defines if memory is allocated into the stack (local variable), or into the heap (malloc()).
185#define COPYLENGTH 8
186#define LASTLITERALS 5
187#define MFLIMIT (COPYLENGTH+MINMATCH)
188#define MINLENGTH (MFLIMIT+1)
189
190#define MAXD_LOG 16
191#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
192
193#define ML_BITS 4
194#define ML_MASK ((1U<<ML_BITS)-1)
195#define RUN_BITS (8-ML_BITS)
196#define RUN_MASK ((1U<<RUN_BITS)-1)
197
198
199//**************************************
200// Architecture-specific macros
201//**************************************
202#if LZ4_ARCH64 // 64-bit
203# define STEPSIZE 8
204# define UARCH U64
205# define AARCH A64
206# define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8;
207# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d)
208# define LZ4_SECURECOPY(s,d,e) if (d<e) LZ4_WILDCOPY(s,d,e)
209# define HTYPE U32
210# define INITBASE(base) const BYTE* const base = ip
211#else // 32-bit
212# define STEPSIZE 4
213# define UARCH U32
214# define AARCH A32
215# define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4;
216# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);
217# define LZ4_SECURECOPY LZ4_WILDCOPY
218# define HTYPE const BYTE*
219# define INITBASE(base) const int base = 0
220#endif
221
222#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
223# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
224# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }
225#else // Little Endian
226# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }
227# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }
228#endif
229
230
231//**************************************
232// Local structures
233//**************************************
234struct refTables
235{
236 HTYPE hashTable[HASHTABLESIZE];
237};
238
239
240//**************************************
241// Macros
242//**************************************
243#define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
244#define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
245#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);
246#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=(d)+l; LZ4_WILDCOPY(s,d,e); d=e; }
247
248
249//****************************
250// Private functions
251//****************************
252#if LZ4_ARCH64
253
254static inline int LZ4_NbCommonBytes (register U64 val)
255{
256#if defined(LZ4_BIG_ENDIAN)
257 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
258 unsigned long r = 0;
259 _BitScanReverse64( &r, val );
260 return (int)(r>>3);
261 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
262 return (__builtin_clzll(val) >> 3);
263 #else
264 int r;
265 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
266 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
267 r += (!val);
268 return r;
269 #endif
270#else
271 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
272 unsigned long r = 0;
273 _BitScanForward64( &r, val );
274 return (int)(r>>3);
275 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
276 return (__builtin_ctzll(val) >> 3);
277 #else
278 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 };
279 return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];
280 #endif
281#endif
282}
283
284#else
285
286static inline int LZ4_NbCommonBytes (register U32 val)
287{
288#if defined(LZ4_BIG_ENDIAN)
289 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
290 unsigned long r = 0;
291 _BitScanReverse( &r, val );
292 return (int)(r>>3);
293 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
294 return (__builtin_clz(val) >> 3);
295 #else
296 int r;
297 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
298 r += (!val);
299 return r;
300 #endif
301#else
302 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
303 unsigned long r = 0;
304 _BitScanForward( &r, val );
305 return (int)(r>>3);
306 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
307 return (__builtin_ctz(val) >> 3);
308 #else
309 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 };
310 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
311 #endif
312#endif
313}
314
315#endif
316
317
318
319//******************************
320// Compression functions
321//******************************
322
323// LZ4_compressCtx :
324// -----------------
325// Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.
326// If it cannot achieve it, compression will stop, and result of the function will be zero.
327// return : the number of bytes written in buffer 'dest', or 0 if the compression fails
328
329static inline int LZ4_compressCtx(void** ctx,
330 const char* source,
331 char* dest,
332 int isize,
333 int maxOutputSize)
334{
335#if HEAPMODE
336 struct refTables *srt = (struct refTables *) (*ctx);
337 HTYPE* HashTable;
338#else
339 HTYPE HashTable[HASHTABLESIZE] = {0};
340#endif
341
342 const BYTE* ip = (BYTE*) source;
343 INITBASE(base);
344 const BYTE* anchor = ip;
345 const BYTE* const iend = ip + isize;
346 const BYTE* const mflimit = iend - MFLIMIT;
347#define matchlimit (iend - LASTLITERALS)
348
349 BYTE* op = (BYTE*) dest;
350 BYTE* const oend = op + maxOutputSize;
351
352 int len, length;
353 const int skipStrength = SKIPSTRENGTH;
354 U32 forwardH;
355
356
357 // Init
358 if (isize<MINLENGTH) goto _last_literals;
359#if HEAPMODE
360 if (*ctx == NULL)
361 {
362 srt = (struct refTables *) malloc ( sizeof(struct refTables) );
363 *ctx = (void*) srt;
364 }
365 HashTable = (HTYPE*)(srt->hashTable);
366 memset((void*)HashTable, 0, sizeof(srt->hashTable));
367#else
368 (void) ctx;
369#endif
370
371
372 // First Byte
373 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
374 ip++; forwardH = LZ4_HASH_VALUE(ip);
375
376 // Main Loop
377 for ( ; ; )
378 {
379 int findMatchAttempts = (1U << skipStrength) + 3;
380 const BYTE* forwardIp = ip;
381 const BYTE* ref;
382 BYTE* token;
383
384 // Find a match
385 do {
386 U32 h = forwardH;
387 int step = findMatchAttempts++ >> skipStrength;
388 ip = forwardIp;
389 forwardIp = ip + step;
390
391 if unlikely(forwardIp > mflimit) { goto _last_literals; }
392
393 forwardH = LZ4_HASH_VALUE(forwardIp);
394 ref = base + HashTable[h];
395 HashTable[h] = ip - base;
396
397 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
398
399 // Catch up
400 while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }
401
402 // Encode Literal length
403 length = (int)(ip - anchor);
404 token = op++;
405 if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) >= oend) return 0; // Check output limit
406#ifdef _MSC_VER
407 if (length>=(int)RUN_MASK)
408 {
409 int len = length-RUN_MASK;
410 *token=(RUN_MASK<<ML_BITS);
411 if (len>254)
412 {
413 do { *op++ = 255; len -= 255; } while (len>254);
414 *op++ = (BYTE)len;
415 memcpy(op, anchor, length);
416 op += length;
417 goto _next_match;
418 }
419 else
420 *op++ = (BYTE)len;
421 }
422 else *token = (length<<ML_BITS);
423#else
424 if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }
425 else *token = (length<<ML_BITS);
426#endif
427
428 // Copy Literals
429 LZ4_BLINDCOPY(anchor, op, length);
430
431_next_match:
432 // Encode Offset
433 LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));
434
435 // Start Counting
436 ip+=MINMATCH; ref+=MINMATCH; // MinMatch verified
437 anchor = ip;
438 while likely(ip<matchlimit-(STEPSIZE-1))
439 {
440 UARCH diff = AARCH(ref) ^ AARCH(ip);
441 if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }
442 ip += LZ4_NbCommonBytes(diff);
443 goto _endCount;
444 }
445 if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }
446 if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }
447 if ((ip<matchlimit) && (*ref == *ip)) ip++;
448_endCount:
449
450 // Encode MatchLength
451 len = (int)(ip - anchor);
452 if unlikely(op + (1 + LASTLITERALS) + (len>>8) >= oend) return 0; // Check output limit
453 if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }
454 else *token += len;
455
456 // Test end of chunk
457 if (ip > mflimit) { anchor = ip; break; }
458
459 // Fill table
460 HashTable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;
461
462 // Test next position
463 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
464 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
465 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }
466
467 // Prepare next loop
468 anchor = ip++;
469 forwardH = LZ4_HASH_VALUE(ip);
470 }
471
472_last_literals:
473 // Encode Last Literals
474 {
475 int lastRun = (int)(iend - anchor);
476 if (((char*)op - dest) + lastRun + 1 + ((lastRun-15)/255) >= maxOutputSize) return 0;
477 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
478 else *op++ = (lastRun<<ML_BITS);
479 memcpy(op, anchor, iend - anchor);
480 op += iend-anchor;
481 }
482
483 // End
484 return (int) (((char*)op)-dest);
485}
486
487
488
489// Note : this function is valid only if isize < LZ4_64KLIMIT
490#define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1))
491#define HASHLOG64K (HASH_LOG+1)
492#define HASH64KTABLESIZE (1U<<HASHLOG64K)
493#define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASHLOG64K))
494#define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p))
495static inline int LZ4_compress64kCtx(void** ctx,
496 const char* source,
497 char* dest,
498 int isize,
499 int maxOutputSize)
500{
501#if HEAPMODE
502 struct refTables *srt = (struct refTables *) (*ctx);
503 U16* HashTable;
504#else
505 U16 HashTable[HASH64KTABLESIZE] = {0};
506#endif
507
508 const BYTE* ip = (BYTE*) source;
509 const BYTE* anchor = ip;
510 const BYTE* const base = ip;
511 const BYTE* const iend = ip + isize;
512 const BYTE* const mflimit = iend - MFLIMIT;
513#define matchlimit (iend - LASTLITERALS)
514
515 BYTE* op = (BYTE*) dest;
516 BYTE* const oend = op + maxOutputSize;
517
518 int len, length;
519 const int skipStrength = SKIPSTRENGTH;
520 U32 forwardH;
521
522
523 // Init
524 if (isize<MINLENGTH) goto _last_literals;
525#if HEAPMODE
526 if (*ctx == NULL)
527 {
528 srt = (struct refTables *) malloc ( sizeof(struct refTables) );
529 *ctx = (void*) srt;
530 }
531 HashTable = (U16*)(srt->hashTable);
532 memset((void*)HashTable, 0, sizeof(srt->hashTable));
533#else
534 (void) ctx;
535#endif
536
537
538 // First Byte
539 ip++; forwardH = LZ4_HASH64K_VALUE(ip);
540
541 // Main Loop
542 for ( ; ; )
543 {
544 int findMatchAttempts = (1U << skipStrength) + 3;
545 const BYTE* forwardIp = ip;
546 const BYTE* ref;
547 BYTE* token;
548
549 // Find a match
550 do {
551 U32 h = forwardH;
552 int step = findMatchAttempts++ >> skipStrength;
553 ip = forwardIp;
554 forwardIp = ip + step;
555
556 if (forwardIp > mflimit) { goto _last_literals; }
557
558 forwardH = LZ4_HASH64K_VALUE(forwardIp);
559 ref = base + HashTable[h];
560 HashTable[h] = (U16)(ip - base);
561
562 } while (A32(ref) != A32(ip));
563
564 // Catch up
565 while ((ip>anchor) && (ref>(BYTE*)source) && (ip[-1]==ref[-1])) { ip--; ref--; }
566
567 // Encode Literal length
568 length = (int)(ip - anchor);
569 token = op++;
570 if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) >= oend) return 0; // Check output limit
571#ifdef _MSC_VER
572 if (length>=(int)RUN_MASK)
573 {
574 int len = length-RUN_MASK;
575 *token=(RUN_MASK<<ML_BITS);
576 if (len>254)
577 {
578 do { *op++ = 255; len -= 255; } while (len>254);
579 *op++ = (BYTE)len;
580 memcpy(op, anchor, length);
581 op += length;
582 goto _next_match;
583 }
584 else
585 *op++ = (BYTE)len;
586 }
587 else *token = (length<<ML_BITS);
588#else
589 if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }
590 else *token = (length<<ML_BITS);
591#endif
592
593 // Copy Literals
594 LZ4_BLINDCOPY(anchor, op, length);
595
596_next_match:
597 // Encode Offset
598 LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));
599
600 // Start Counting
601 ip+=MINMATCH; ref+=MINMATCH; // MinMatch verified
602 anchor = ip;
603 while (ip<matchlimit-(STEPSIZE-1))
604 {
605 UARCH diff = AARCH(ref) ^ AARCH(ip);
606 if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }
607 ip += LZ4_NbCommonBytes(diff);
608 goto _endCount;
609 }
610 if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }
611 if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }
612 if ((ip<matchlimit) && (*ref == *ip)) ip++;
613_endCount:
614
615 // Encode MatchLength
616 len = (int)(ip - anchor);
617 if unlikely(op + (1 + LASTLITERALS) + (len>>8) >= oend) return 0; // Check output limit
618 if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }
619 else *token += len;
620
621 // Test end of chunk
622 if (ip > mflimit) { anchor = ip; break; }
623
624 // Fill table
625 HashTable[LZ4_HASH64K_VALUE(ip-2)] = (U16)(ip - 2 - base);
626
627 // Test next position
628 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
629 HashTable[LZ4_HASH64K_VALUE(ip)] = (U16)(ip - base);
630 if (A32(ref) == A32(ip)) { token = op++; *token=0; goto _next_match; }
631
632 // Prepare next loop
633 anchor = ip++;
634 forwardH = LZ4_HASH64K_VALUE(ip);
635 }
636
637_last_literals:
638 // Encode Last Literals
639 {
640 int lastRun = (int)(iend - anchor);
641 if (((char*)op - dest) + lastRun + 1 + ((lastRun)>>8) >= maxOutputSize) return 0;
642 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
643 else *op++ = (lastRun<<ML_BITS);
644 memcpy(op, anchor, iend - anchor);
645 op += iend-anchor;
646 }
647
648 // End
649 return (int) (((char*)op)-dest);
650}
651
652
653int LZ4_compress_limitedOutput(const char* source,
654 char* dest,
655 int isize,
656 int maxOutputSize)
657{
658#if HEAPMODE
659 void* ctx = malloc(sizeof(struct refTables));
660 int result;
661 if (isize < LZ4_64KLIMIT)
662 result = LZ4_compress64kCtx(&ctx, source, dest, isize, maxOutputSize);
663 else result = LZ4_compressCtx(&ctx, source, dest, isize, maxOutputSize);
664 free(ctx);
665 return result;
666#else
667 if (isize < (int)LZ4_64KLIMIT) return LZ4_compress64kCtx(NULL, source, dest, isize, maxOutputSize);
668 return LZ4_compressCtx(NULL, source, dest, isize, maxOutputSize);
669#endif
670}
671
672
673int LZ4_compress(const char* source,
674 char* dest,
675 int isize)
676{
677 return LZ4_compress_limitedOutput(source, dest, isize, LZ4_compressBound(isize));
678}
679
680
681
682
683//****************************
684// Decompression functions
685//****************************
686
687// Note : The decoding functions LZ4_uncompress() and LZ4_uncompress_unknownOutputSize()
688// are safe against "buffer overflow" attack type.
689// They will never write nor read outside of the provided output buffers.
690// LZ4_uncompress_unknownOutputSize() also insures that it will never read outside of the input buffer.
691// A corrupted input will produce an error result, a negative int, indicating the position of the error within input stream.
692
693int LZ4_uncompress(const char* source,
694 char* dest,
695 int osize)
696{
697 // Local Variables
698 const BYTE* restrict ip = (const BYTE*) source;
699 const BYTE* restrict ref;
700
701 BYTE* restrict op = (BYTE*) dest;
702 BYTE* const oend = op + osize;
703 BYTE* cpy;
704
705 BYTE token;
706
707 int len, length;
708 size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};
709
710
711 // Main Loop
712 while (1)
713 {
714 // get runlength
715 token = *ip++;
716 if ((length=(token>>ML_BITS)) == RUN_MASK) { for (;(len=*ip++)==255;length+=255){} length += len; }
717
718 // copy literals
719 cpy = op+length;
720 if unlikely(cpy>oend-COPYLENGTH)
721 {
722 if (cpy > oend) goto _output_error; // Error : request to write beyond destination buffer
723 memcpy(op, ip, length);
724 ip += length;
725 break; // Necessarily EOF
726 }
727 LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;
728
729 // get offset
730 LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;
731 if (ref < (BYTE* const)dest) goto _output_error; // Error : offset create reference outside destination buffer
732
733 // get matchlength
734 if ((length=(token&ML_MASK)) == ML_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; }
735
736 // copy repeated sequence
737 if unlikely(op-ref<STEPSIZE)
738 {
739#if LZ4_ARCH64
740 size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};
741 size_t dec2 = dec2table[op-ref];
742#else
743 const int dec2 = 0;
744#endif
745 *op++ = *ref++;
746 *op++ = *ref++;
747 *op++ = *ref++;
748 *op++ = *ref++;
749 ref -= dec[op-ref];
750 A32(op)=A32(ref); op += STEPSIZE-4;
751 ref -= dec2;
752 } else { LZ4_COPYSTEP(ref,op); }
753 cpy = op + length - (STEPSIZE-4);
754 if (cpy>oend-COPYLENGTH)
755 {
756 if (cpy > oend) goto _output_error; // Error : request to write beyond destination buffer
757 LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));
758 while(op<cpy) *op++=*ref++;
759 op=cpy;
760 if (op == oend) break; // Check EOF (should never happen, since last 5 bytes are supposed to be literals)
761 continue;
762 }
763 LZ4_SECURECOPY(ref, op, cpy);
764 op=cpy; // correction
765 }
766
767 // end of decoding
768 return (int) (((char*)ip)-source);
769
770 // write overflow error detected
771_output_error:
772 return (int) (-(((char*)ip)-source));
773}
774
775
776int LZ4_uncompress_unknownOutputSize(
777 const char* source,
778 char* dest,
779 int isize,
780 int maxOutputSize)
781{
782 // Local Variables
783 const BYTE* restrict ip = (const BYTE*) source;
784 const BYTE* const iend = ip + isize;
785 const BYTE* restrict ref;
786
787 BYTE* restrict op = (BYTE*) dest;
788 BYTE* const oend = op + maxOutputSize;
789 BYTE* cpy;
790
791 size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};
792
793
794 // Main Loop
795 while (ip<iend)
796 {
797 BYTE token;
798 int length;
799
800 // get runlength
801 token = *ip++;
802 if ((length=(token>>ML_BITS)) == RUN_MASK) { int s=255; while ((ip<iend) && (s==255)) { s=*ip++; length += s; } }
803
804 // copy literals
805 cpy = op+length;
806 if ((cpy>oend-COPYLENGTH) || (ip+length>iend-COPYLENGTH))
807 {
808 if (cpy > oend) goto _output_error; // Error : request to write beyond destination buffer
809 if (ip+length > iend) goto _output_error; // Error : request to read beyond source buffer
810 memcpy(op, ip, length);
811 op += length;
812 ip += length;
813 if (ip<iend) goto _output_error; // Error : LZ4 format violation
814 break; // Necessarily EOF, due to parsing restrictions
815 }
816 LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;
817
818 // get offset
819 LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;
820 if (ref < (BYTE* const)dest) goto _output_error; // Error : offset creates reference outside of destination buffer
821
822 // get matchlength
823 if ((length=(token&ML_MASK)) == ML_MASK) { while (ip<iend) { int s = *ip++; length +=s; if (s==255) continue; break; } }
824
825 // copy repeated sequence
826 if unlikely(op-ref<STEPSIZE)
827 {
828#if LZ4_ARCH64
829 size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};
830 size_t dec2 = dec2table[op-ref];
831#else
832 const int dec2 = 0;
833#endif
834 *op++ = *ref++;
835 *op++ = *ref++;
836 *op++ = *ref++;
837 *op++ = *ref++;
838 ref -= dec[op-ref];
839 A32(op)=A32(ref); op += STEPSIZE-4;
840 ref -= dec2;
841 } else { LZ4_COPYSTEP(ref,op); }
842 cpy = op + length - (STEPSIZE-4);
843 if (cpy>oend-COPYLENGTH)
844 {
845 if (cpy > oend) goto _output_error; // Error : request to write outside of destination buffer
846 LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));
847 while(op<cpy) *op++=*ref++;
848 op=cpy;
849 if (op == oend) break; // Check EOF (should never happen, since last 5 bytes are supposed to be literals)
850 continue;
851 }
852 LZ4_SECURECOPY(ref, op, cpy);
853 op=cpy; // correction
854 }
855
856 // end of decoding
857 return (int) (((char*)op)-dest);
858
859 // write overflow error detected
860_output_error:
861 return (int) (-(((char*)ip)-source));
862}
863
diff --git a/src/static_libs/lz4/lz4.h b/src/static_libs/lz4/lz4.h
new file mode 100644
index 0000000..e3df7bd
--- /dev/null
+++ b/src/static_libs/lz4/lz4.h
@@ -0,0 +1,117 @@
1/*
2 LZ4 - Fast LZ compression algorithm
3 Header File
4 Copyright (C) 2011-2012, Yann Collet.
5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
9 met:
10
11 * Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above
14 copyright notice, this list of conditions and the following disclaimer
15 in the documentation and/or other materials provided with the
16 distribution.
17
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 You can contact the author at :
31 - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32 - LZ4 source repository : http://code.google.com/p/lz4/
33*/
34#pragma once
35
36#if defined (__cplusplus)
37extern "C" {
38#endif
39
40
41//****************************
42// Simple Functions
43//****************************
44
45int LZ4_compress (const char* source, char* dest, int isize);
46int LZ4_uncompress (const char* source, char* dest, int osize);
47
48/*
49LZ4_compress() :
50 Compresses 'isize' bytes from 'source' into 'dest'.
51 Destination buffer must be already allocated,
52 and must be sized to handle worst cases situations (input data not compressible)
53 Worst case size evaluation is provided by macro LZ4_compressBound()
54
55 isize : is the input size. Max supported value is ~1.9GB
56 return : the number of bytes written in buffer dest
57
58
59LZ4_uncompress() :
60 osize : is the output size, therefore the original size
61 return : the number of bytes read in the source buffer
62 If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction
63 This function never writes beyond dest + osize, and is therefore protected against malicious data packets
64 note : destination buffer must be already allocated.
65 its size must be a minimum of 'osize' bytes.
66*/
67
68
69//****************************
70// Advanced Functions
71//****************************
72
73#define LZ4_compressBound(isize) (isize + (isize/255) + 16)
74
75/*
76LZ4_compressBound() :
77 Provides the maximum size that LZ4 may output in a "worst case" scenario (input data not compressible)
78 primarily useful for memory allocation of output buffer.
79
80 isize : is the input size. Max supported value is ~1.9GB
81 return : maximum output size in a "worst case" scenario
82 note : this function is limited by "int" range (2^31-1)
83*/
84
85
86int LZ4_compress_limitedOutput (const char* source, char* dest, int isize, int maxOutputSize);
87
88/*
89LZ4_compress_limitedOutput() :
90 Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.
91 If it cannot achieve it, compression will stop, and result of the function will be zero.
92 This function never writes outside of provided output buffer.
93
94 isize : is the input size. Max supported value is ~1.9GB
95 maxOutputSize : is the size of the destination buffer (which must be already allocated)
96 return : the number of bytes written in buffer 'dest'
97 or 0 if the compression fails
98*/
99
100
101int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize);
102
103/*
104LZ4_uncompress_unknownOutputSize() :
105 isize : is the input size, therefore the compressed size
106 maxOutputSize : is the size of the destination buffer (which must be already allocated)
107 return : the number of bytes decoded in the destination buffer (necessarily <= maxOutputSize)
108 If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction
109 This function never writes beyond dest + maxOutputSize, and is therefore protected against malicious data packets
110 note : Destination buffer must be already allocated.
111 This version is slightly slower than LZ4_uncompress()
112*/
113
114
115#if defined (__cplusplus)
116}
117#endif
diff --git a/src/static_libs/lz4/lz4hc.c b/src/static_libs/lz4/lz4hc.c
new file mode 100644
index 0000000..2ab507e
--- /dev/null
+++ b/src/static_libs/lz4/lz4hc.c
@@ -0,0 +1,671 @@
1/*
2 LZ4 HC - High Compression Mode of LZ4
3 Copyright (C) 2011-2012, 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// CPU Feature Detection
37//**************************************
38// 32 or 64 bits ?
39#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) ) // Detects 64 bits mode
40#define LZ4_ARCH64 1
41#else
42#define LZ4_ARCH64 0
43#endif
44
45// Little Endian or Big Endian ?
46#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) || ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))) )
47#define LZ4_BIG_ENDIAN 1
48#else
49// Little Endian assumed. PDP Endian and other very rare endian format are unsupported.
50#endif
51
52// Unaligned memory access is automatically enabled for "common" CPU, such as x86.
53// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected
54// If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance
55#if defined(__ARM_FEATURE_UNALIGNED)
56#define LZ4_FORCE_UNALIGNED_ACCESS 1
57#endif
58
59
60//**************************************
61// Compiler Options
62//**************************************
63#if __STDC_VERSION__ >= 199901L // C99
64 /* "restrict" is a known keyword */
65#else
66#define restrict // Disable restrict
67#endif
68
69#ifdef _MSC_VER
70#define inline __forceinline // Visual is not C99, but supports some kind of inline
71#include <intrin.h> // For Visual 2005
72# if LZ4_ARCH64 // 64-bit
73# pragma intrinsic(_BitScanForward64) // For Visual 2005
74# pragma intrinsic(_BitScanReverse64) // For Visual 2005
75# else
76# pragma intrinsic(_BitScanForward) // For Visual 2005
77# pragma intrinsic(_BitScanReverse) // For Visual 2005
78# endif
79#endif
80
81#ifdef _MSC_VER // Visual Studio
82#define lz4_bswap16(x) _byteswap_ushort(x)
83#else
84#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
85#endif
86
87
88//**************************************
89// Includes
90//**************************************
91#include <stdlib.h> // calloc, free
92#include <string.h> // memset, memcpy
93#include "lz4hc.h"
94
95#define ALLOCATOR(s) calloc(1,s)
96#define FREEMEM free
97#define MEM_INIT memset
98
99
100//**************************************
101// Basic Types
102//**************************************
103#if defined(_MSC_VER) // Visual Studio does not support 'stdint' natively
104#define BYTE unsigned __int8
105#define U16 unsigned __int16
106#define U32 unsigned __int32
107#define S32 __int32
108#define U64 unsigned __int64
109#else
110#include <stdint.h>
111#define BYTE uint8_t
112#define U16 uint16_t
113#define U32 uint32_t
114#define S32 int32_t
115#define U64 uint64_t
116#endif
117
118#ifndef LZ4_FORCE_UNALIGNED_ACCESS
119#pragma pack(push, 1)
120#endif
121
122typedef struct _U16_S { U16 v; } U16_S;
123typedef struct _U32_S { U32 v; } U32_S;
124typedef struct _U64_S { U64 v; } U64_S;
125
126#ifndef LZ4_FORCE_UNALIGNED_ACCESS
127#pragma pack(pop)
128#endif
129
130#define A64(x) (((U64_S *)(x))->v)
131#define A32(x) (((U32_S *)(x))->v)
132#define A16(x) (((U16_S *)(x))->v)
133
134
135//**************************************
136// Constants
137//**************************************
138#define MINMATCH 4
139
140#define DICTIONARY_LOGSIZE 16
141#define MAXD (1<<DICTIONARY_LOGSIZE)
142#define MAXD_MASK ((U32)(MAXD - 1))
143#define MAX_DISTANCE (MAXD - 1)
144
145#define HASH_LOG (DICTIONARY_LOGSIZE-1)
146#define HASHTABLESIZE (1 << HASH_LOG)
147#define HASH_MASK (HASHTABLESIZE - 1)
148
149#define MAX_NB_ATTEMPTS 256
150
151#define ML_BITS 4
152#define ML_MASK (size_t)((1U<<ML_BITS)-1)
153#define RUN_BITS (8-ML_BITS)
154#define RUN_MASK ((1U<<RUN_BITS)-1)
155
156#define COPYLENGTH 8
157#define LASTLITERALS 5
158#define MFLIMIT (COPYLENGTH+MINMATCH)
159#define MINLENGTH (MFLIMIT+1)
160#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
161
162
163//**************************************
164// Architecture-specific macros
165//**************************************
166#if LZ4_ARCH64 // 64-bit
167#define STEPSIZE 8
168#define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8;
169#define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d)
170#define UARCH U64
171#define AARCH A64
172#define HTYPE U32
173#define INITBASE(b,s) const BYTE* const b = s
174#else // 32-bit
175#define STEPSIZE 4
176#define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4;
177#define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);
178#define UARCH U32
179#define AARCH A32
180#define HTYPE const BYTE*
181#define INITBASE(b,s) const int b = 0
182#endif
183
184#if defined(LZ4_BIG_ENDIAN)
185#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
186#define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }
187#else // Little Endian
188#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }
189#define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }
190#endif
191
192
193//************************************************************
194// Local Types
195//************************************************************
196typedef struct
197{
198 const BYTE* base;
199 HTYPE hashTable[HASHTABLESIZE];
200 U16 chainTable[MAXD];
201 const BYTE* nextToUpdate;
202} LZ4HC_Data_Structure;
203
204
205//**************************************
206// Macros
207//**************************************
208#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);
209#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }
210#define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
211#define HASH_VALUE(p) HASH_FUNCTION(*(U32*)(p))
212#define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base)
213#define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK]
214#define GETNEXT(p) ((p) - (size_t)DELTANEXT(p))
215#define ADD_HASH(p) { size_t delta = (p) - HASH_POINTER(p); if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; DELTANEXT(p) = (U16)delta; HashTable[HASH_VALUE(p)] = (p) - base; }
216
217
218//**************************************
219// Private functions
220//**************************************
221#if LZ4_ARCH64
222
223inline static int LZ4_NbCommonBytes (register U64 val)
224{
225#if defined(LZ4_BIG_ENDIAN)
226 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
227 unsigned long r = 0;
228 _BitScanReverse64( &r, val );
229 return (int)(r>>3);
230 #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
231 return (__builtin_clzll(val) >> 3);
232 #else
233 int r;
234 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
235 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
236 r += (!val);
237 return r;
238 #endif
239#else
240 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
241 unsigned long r = 0;
242 _BitScanForward64( &r, val );
243 return (int)(r>>3);
244 #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
245 return (__builtin_ctzll(val) >> 3);
246 #else
247 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 };
248 return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];
249 #endif
250#endif
251}
252
253#else
254
255inline static int LZ4_NbCommonBytes (register U32 val)
256{
257#if defined(LZ4_BIG_ENDIAN)
258 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
259 unsigned long r = 0;
260 _BitScanReverse( &r, val );
261 return (int)(r>>3);
262 #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
263 return (__builtin_clz(val) >> 3);
264 #else
265 int r;
266 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
267 r += (!val);
268 return r;
269 #endif
270#else
271 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
272 unsigned long r = 0;
273 _BitScanForward( &r, val );
274 return (int)(r>>3);
275 #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
276 return (__builtin_ctz(val) >> 3);
277 #else
278 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 };
279 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
280 #endif
281#endif
282}
283
284#endif
285
286
287inline static int LZ4HC_Init (LZ4HC_Data_Structure* hc4, const BYTE* base)
288{
289 MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
290 MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
291 hc4->nextToUpdate = base + LZ4_ARCH64;
292 hc4->base = base;
293 return 1;
294}
295
296
297inline static void* LZ4HC_Create (const BYTE* base)
298{
299 void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));
300
301 LZ4HC_Init (hc4, base);
302 return hc4;
303}
304
305
306inline static int LZ4HC_Free (void** LZ4HC_Data)
307{
308 FREEMEM(*LZ4HC_Data);
309 *LZ4HC_Data = NULL;
310 return (1);
311}
312
313
314inline static void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)
315{
316 U16* chainTable = hc4->chainTable;
317 HTYPE* HashTable = hc4->hashTable;
318 INITBASE(base,hc4->base);
319
320 while(hc4->nextToUpdate < ip)
321 {
322 ADD_HASH(hc4->nextToUpdate);
323 hc4->nextToUpdate++;
324 }
325}
326
327
328inline static int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos)
329{
330 U16* const chainTable = hc4->chainTable;
331 HTYPE* const HashTable = hc4->hashTable;
332 const BYTE* ref;
333 INITBASE(base,hc4->base);
334 int nbAttempts=MAX_NB_ATTEMPTS;
335 int ml=0;
336
337 // HC4 match finder
338 LZ4HC_Insert(hc4, ip);
339 ref = HASH_POINTER(ip);
340 while ((ref > (ip-MAX_DISTANCE)) && (nbAttempts))
341 {
342 nbAttempts--;
343 if (*(ref+ml) == *(ip+ml))
344 if (*(U32*)ref == *(U32*)ip)
345 {
346 const BYTE* reft = ref+MINMATCH;
347 const BYTE* ipt = ip+MINMATCH;
348
349 while (ipt<matchlimit-(STEPSIZE-1))
350 {
351 UARCH diff = AARCH(reft) ^ AARCH(ipt);
352 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }
353 ipt += LZ4_NbCommonBytes(diff);
354 goto _endCount;
355 }
356 if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }
357 if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }
358 if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;
359_endCount:
360
361 if (ipt-ip > ml) { ml = (int)(ipt-ip); *matchpos = ref; }
362 }
363 ref = GETNEXT(ref);
364 }
365
366 return ml;
367}
368
369
370inline static int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos)
371{
372 U16* const chainTable = hc4->chainTable;
373 HTYPE* const HashTable = hc4->hashTable;
374 INITBASE(base,hc4->base);
375 const BYTE* ref;
376 int nbAttempts = MAX_NB_ATTEMPTS;
377 int delta = (int)(ip-startLimit);
378
379 // First Match
380 LZ4HC_Insert(hc4, ip);
381 ref = HASH_POINTER(ip);
382
383 while ((ref > ip-MAX_DISTANCE) && (ref >= hc4->base) && (nbAttempts))
384 {
385 nbAttempts--;
386 if (*(startLimit + longest) == *(ref - delta + longest))
387 if (*(U32*)ref == *(U32*)ip)
388 {
389 const BYTE* reft = ref+MINMATCH;
390 const BYTE* ipt = ip+MINMATCH;
391 const BYTE* startt = ip;
392
393 while (ipt<matchlimit-(STEPSIZE-1))
394 {
395 UARCH diff = AARCH(reft) ^ AARCH(ipt);
396 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }
397 ipt += LZ4_NbCommonBytes(diff);
398 goto _endCount;
399 }
400 if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }
401 if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }
402 if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;
403_endCount:
404
405 reft = ref;
406 while ((startt>startLimit) && (reft > hc4->base) && (startt[-1] == reft[-1])) {startt--; reft--;}
407
408 if ((ipt-startt) > longest)
409 {
410 longest = (int)(ipt-startt);
411 *matchpos = reft;
412 *startpos = startt;
413 }
414 }
415 ref = GETNEXT(ref);
416 }
417
418 return longest;
419}
420
421
422inline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE** anchor, int ml, const BYTE* ref)
423{
424 int length, len;
425 BYTE* token;
426
427 // Encode Literal length
428 length = (int)(*ip - *anchor);
429 token = (*op)++;
430 if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; }
431 else *token = (length<<ML_BITS);
432
433 // Copy Literals
434 LZ4_BLINDCOPY(*anchor, *op, length);
435
436 // Encode Offset
437 LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));
438
439 // Encode MatchLength
440 len = (int)(ml-MINMATCH);
441 if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (len > 254) { len-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)len; }
442 else *token += len;
443
444 // Prepare next loop
445 *ip += ml;
446 *anchor = *ip;
447
448 return 0;
449}
450
451
452//****************************
453// Compression CODE
454//****************************
455
456int LZ4_compressHCCtx(LZ4HC_Data_Structure* ctx,
457 const char* source,
458 char* dest,
459 int isize)
460{
461 const BYTE* ip = (const BYTE*) source;
462 const BYTE* anchor = ip;
463 const BYTE* const iend = ip + isize;
464 const BYTE* const mflimit = iend - MFLIMIT;
465 const BYTE* const matchlimit = (iend - LASTLITERALS);
466
467 BYTE* op = (BYTE*) dest;
468
469 int ml, ml2, ml3, ml0;
470 const BYTE* ref=NULL;
471 const BYTE* start2=NULL;
472 const BYTE* ref2=NULL;
473 const BYTE* start3=NULL;
474 const BYTE* ref3=NULL;
475 const BYTE* start0;
476 const BYTE* ref0;
477
478 ip++;
479
480 // Main Loop
481 while (ip < mflimit)
482 {
483 ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref));
484 if (!ml) { ip++; continue; }
485
486 // saved, in case we would skip too much
487 start0 = ip;
488 ref0 = ref;
489 ml0 = ml;
490
491_Search2:
492 if (ip+ml < mflimit)
493 ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);
494 else ml2=ml;
495
496 if (ml2 == ml) // No better match
497 {
498 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);
499 continue;
500 }
501
502 if (start0 < ip)
503 {
504 if (start2 < ip + ml0) // empirical
505 {
506 ip = start0;
507 ref = ref0;
508 ml = ml0;
509 }
510 }
511
512 // Here, start0==ip
513 if ((start2 - ip) < 3) // First Match too small : removed
514 {
515 ml = ml2;
516 ip = start2;
517 ref =ref2;
518 goto _Search2;
519 }
520
521_Search3:
522 // Currently we have :
523 // ml2 > ml1, and
524 // ip1+3 <= ip2 (usually < ip1+ml1)
525 if ((start2 - ip) < OPTIMAL_ML)
526 {
527 int correction;
528 int new_ml = ml;
529 if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
530 if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
531 correction = new_ml - (int)(start2 - ip);
532 if (correction > 0)
533 {
534 start2 += correction;
535 ref2 += correction;
536 ml2 -= correction;
537 }
538 }
539 // Now, we have start2 = ip+new_ml, with new_ml=min(ml, OPTIMAL_ML=18)
540
541 if (start2 + ml2 < mflimit)
542 ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);
543 else ml3=ml2;
544
545 if (ml3 == ml2) // No better match : 2 sequences to encode
546 {
547 // ip & ref are known; Now for ml
548 if (start2 < ip+ml)
549 {
550 if ((start2 - ip) < OPTIMAL_ML)
551 {
552 int correction;
553 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
554 if (ip+ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
555 correction = ml - (int)(start2 - ip);
556 if (correction > 0)
557 {
558 start2 += correction;
559 ref2 += correction;
560 ml2 -= correction;
561 }
562 }
563 else
564 {
565 ml = (int)(start2 - ip);
566 }
567 }
568 // Now, encode 2 sequences
569 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);
570 ip = start2;
571 LZ4_encodeSequence(&ip, &op, &anchor, ml2, ref2);
572 continue;
573 }
574
575 if (start3 < ip+ml+3) // Not enough space for match 2 : remove it
576 {
577 if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1
578 {
579 if (start2 < ip+ml)
580 {
581 int correction = (int)(ip+ml - start2);
582 start2 += correction;
583 ref2 += correction;
584 ml2 -= correction;
585 if (ml2 < MINMATCH)
586 {
587 start2 = start3;
588 ref2 = ref3;
589 ml2 = ml3;
590 }
591 }
592
593 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);
594 ip = start3;
595 ref = ref3;
596 ml = ml3;
597
598 start0 = start2;
599 ref0 = ref2;
600 ml0 = ml2;
601 goto _Search2;
602 }
603
604 start2 = start3;
605 ref2 = ref3;
606 ml2 = ml3;
607 goto _Search3;
608 }
609
610 // OK, now we have 3 ascending matches; let's write at least the first one
611 // ip & ref are known; Now for ml
612 if (start2 < ip+ml)
613 {
614 if ((start2 - ip) < (int)ML_MASK)
615 {
616 int correction;
617 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
618 if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
619 correction = ml - (int)(start2 - ip);
620 if (correction > 0)
621 {
622 start2 += correction;
623 ref2 += correction;
624 ml2 -= correction;
625 }
626 }
627 else
628 {
629 ml = (int)(start2 - ip);
630 }
631 }
632 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);
633
634 ip = start2;
635 ref = ref2;
636 ml = ml2;
637
638 start2 = start3;
639 ref2 = ref3;
640 ml2 = ml3;
641
642 goto _Search3;
643
644 }
645
646 // Encode Last Literals
647 {
648 int lastRun = (int)(iend - anchor);
649 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
650 else *op++ = (lastRun<<ML_BITS);
651 memcpy(op, anchor, iend - anchor);
652 op += iend-anchor;
653 }
654
655 // End
656 return (int) (((char*)op)-dest);
657}
658
659
660int LZ4_compressHC(const char* source,
661 char* dest,
662 int isize)
663{
664 void* ctx = LZ4HC_Create((const BYTE*)source);
665 int result = LZ4_compressHCCtx(ctx, source, dest, isize);
666 LZ4HC_Free (&ctx);
667
668 return result;
669}
670
671
diff --git a/src/static_libs/lz4/lz4hc.h b/src/static_libs/lz4/lz4hc.h
new file mode 100644
index 0000000..cb74689
--- /dev/null
+++ b/src/static_libs/lz4/lz4hc.h
@@ -0,0 +1,60 @@
1/*
2 LZ4 HC - High Compression Mode of LZ4
3 Header File
4 Copyright (C) 2011-2012, Yann Collet.
5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
9 met:
10
11 * Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above
14 copyright notice, this list of conditions and the following disclaimer
15 in the documentation and/or other materials provided with the
16 distribution.
17
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 You can contact the author at :
31 - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32 - LZ4 source repository : http://code.google.com/p/lz4/
33*/
34#pragma once
35
36
37#if defined (__cplusplus)
38extern "C" {
39#endif
40
41
42int LZ4_compressHC (const char* source, char* dest, int isize);
43
44/*
45LZ4_compressHC :
46 return : the number of bytes in compressed buffer dest
47 note : destination buffer must be already allocated.
48 To avoid any problem, size it to handle worst cases situations (input data not compressible)
49 Worst case size evaluation is provided by function LZ4_compressBound() (see "lz4.h")
50*/
51
52
53/* Note :
54Decompression functions are provided within regular LZ4 source code (see "lz4.h") (BSD license)
55*/
56
57
58#if defined (__cplusplus)
59}
60#endif