lz4 0.2.2 → 0.2.3
raw patch · 6 files changed
+2628/−1798 lines, 6 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- lz4.cabal +1/−1
- src/cbits/lz4.c +1247/−874
- src/cbits/lz4.h +306/−128
- src/cbits/lz4hc.c +892/−719
- src/cbits/lz4hc.h +173/−60
- tests/Properties.hs +9/−16
lz4.cabal view
@@ -1,5 +1,5 @@ name: lz4-version: 0.2.2+version: 0.2.3 synopsis: LZ4 compression for ByteStrings description: High level bindings to the LZ4 compression library.
src/cbits/lz4.c view
@@ -1,874 +1,1247 @@-/* - LZ4 - Fast LZ compression algorithm - Copyright (C) 2011-2012, Yann Collet. - BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following disclaimer - in the documentation and/or other materials provided with the - distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - You can contact the author at : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ -*/ - -//************************************** -// Tuning parameters -//************************************** -// MEMORY_USAGE : -// Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) -// Increasing memory usage improves compression ratio -// Reduced memory usage can improve speed, due to cache effect -// Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache -#define MEMORY_USAGE 14 - -// NOTCOMPRESSIBLE_DETECTIONLEVEL : -// Decreasing this value will make the algorithm skip faster data segments considered "incompressible" -// This may decrease compression ratio dramatically, but will be faster on incompressible data -// Increasing this value will make the algorithm search more before declaring a segment "incompressible" -// This could improve compression a bit, but will be slower on incompressible data -// The default value (6) is recommended -#define NOTCOMPRESSIBLE_DETECTIONLEVEL 6 - -// BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE : -// This will provide a small boost to performance for big endian cpu, but the resulting compressed stream will be incompatible with little-endian CPU. -// You can set this option to 1 in situations where data will remain within closed environment -// This option is useless on Little_Endian CPU (such as x86) -//#define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 - - - -//************************************** -// CPU Feature Detection -//************************************** -// 32 or 64 bits ? -#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) ) // Detects 64 bits mode -# define LZ4_ARCH64 1 -#else -# define LZ4_ARCH64 0 -#endif - -// Little Endian or Big Endian ? -// Overwrite the #define below if you know your architecture endianess -#if defined (__GLIBC__) -# include <endian.h> -# if (__BYTE_ORDER == __BIG_ENDIAN) -# define LZ4_BIG_ENDIAN 1 -# endif -#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN)) -# define LZ4_BIG_ENDIAN 1 -#elif defined(__sparc) || defined(__sparc__) \ - || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \ - || defined(__hpux) || defined(__hppa) \ - || defined(_MIPSEB) || defined(__s390__) -# define LZ4_BIG_ENDIAN 1 -#else -// Little Endian assumed. PDP Endian and other very rare endian format are unsupported. -#endif - -// Unaligned memory access is automatically enabled for "common" CPU, such as x86. -// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected -// If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance -#if defined(__ARM_FEATURE_UNALIGNED) -# define LZ4_FORCE_UNALIGNED_ACCESS 1 -#endif - -// Define this parameter if your target system or compiler does not support hardware bit count -#if defined(_MSC_VER) && defined(_WIN32_WCE) // Visual Studio for Windows CE does not support Hardware bit count -# define LZ4_FORCE_SW_BITCOUNT -#endif - - -//************************************** -// Compiler Options -//************************************** -#if __STDC_VERSION__ >= 199901L // C99 -/* "restrict" is a known keyword */ -#else -# define restrict // Disable restrict -#endif - -#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) - -#ifdef _MSC_VER // Visual Studio -# include <intrin.h> // For Visual 2005 -# if LZ4_ARCH64 // 64-bit -# pragma intrinsic(_BitScanForward64) // For Visual 2005 -# pragma intrinsic(_BitScanReverse64) // For Visual 2005 -# else -# pragma intrinsic(_BitScanForward) // For Visual 2005 -# pragma intrinsic(_BitScanReverse) // For Visual 2005 -# endif -#endif - -#ifdef _MSC_VER -# define lz4_bswap16(x) _byteswap_ushort(x) -#else -# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8))) -#endif - -#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__) -# define expect(expr,value) (__builtin_expect ((expr),(value)) ) -#else -# define expect(expr,value) (expr) -#endif - -#define likely(expr) expect((expr) != 0, 1) -#define unlikely(expr) expect((expr) != 0, 0) - - -//************************************** -// Includes -//************************************** -#include <stdlib.h> // for malloc -#include <string.h> // for memset -#include "lz4.h" - - -//************************************** -// Basic Types -//************************************** -#if defined(_MSC_VER) // Visual Studio does not support 'stdint' natively -# define BYTE unsigned __int8 -# define U16 unsigned __int16 -# define U32 unsigned __int32 -# define S32 __int32 -# define U64 unsigned __int64 -#else -# include <stdint.h> -# define BYTE uint8_t -# define U16 uint16_t -# define U32 uint32_t -# define S32 int32_t -# define U64 uint64_t -#endif - -#ifndef LZ4_FORCE_UNALIGNED_ACCESS -# pragma pack(push, 1) -#endif - -typedef struct _U16_S { U16 v; } U16_S; -typedef struct _U32_S { U32 v; } U32_S; -typedef struct _U64_S { U64 v; } U64_S; - -#ifndef LZ4_FORCE_UNALIGNED_ACCESS -# pragma pack(pop) -#endif - -#define A64(x) (((U64_S *)(x))->v) -#define A32(x) (((U32_S *)(x))->v) -#define A16(x) (((U16_S *)(x))->v) - - -//************************************** -// Constants -//************************************** -#define MINMATCH 4 - -#define HASH_LOG (MEMORY_USAGE-2) -#define HASHTABLESIZE (1 << HASH_LOG) -#define HASH_MASK (HASHTABLESIZE - 1) - -#define SKIPSTRENGTH (NOTCOMPRESSIBLE_DETECTIONLEVEL>2?NOTCOMPRESSIBLE_DETECTIONLEVEL:2) -#define STACKLIMIT 13 -#define HEAPMODE (HASH_LOG>STACKLIMIT) // Defines if memory is allocated into the stack (local variable), or into the heap (malloc()). -#define COPYLENGTH 8 -#define LASTLITERALS 5 -#define MFLIMIT (COPYLENGTH+MINMATCH) -#define MINLENGTH (MFLIMIT+1) - -#define MAXD_LOG 16 -#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) - -#define ML_BITS 4 -#define ML_MASK ((1U<<ML_BITS)-1) -#define RUN_BITS (8-ML_BITS) -#define RUN_MASK ((1U<<RUN_BITS)-1) - - -//************************************** -// Architecture-specific macros -//************************************** -#if LZ4_ARCH64 // 64-bit -# define STEPSIZE 8 -# define UARCH U64 -# define AARCH A64 -# define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; -# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) -# define LZ4_SECURECOPY(s,d,e) if (d<e) LZ4_WILDCOPY(s,d,e) -# define HTYPE U32 -# define INITBASE(base) const BYTE* const base = ip -#else // 32-bit -# define STEPSIZE 4 -# define UARCH U32 -# define AARCH A32 -# define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4; -# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d); -# define LZ4_SECURECOPY LZ4_WILDCOPY -# define HTYPE const BYTE* -# define INITBASE(base) const int base = 0 -#endif - -#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) -# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } -# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; } -#else // Little Endian -# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } -# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } -#endif - - -//************************************** -// Local structures -//************************************** -struct refTables -{ - HTYPE hashTable[HASHTABLESIZE]; -}; - - -//************************************** -// Macros -//************************************** -#define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG)) -#define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p)) -#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e); -#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=(d)+l; LZ4_WILDCOPY(s,d,e); d=e; } - - -//**************************** -// Private functions -//**************************** -#if LZ4_ARCH64 - -static inline int LZ4_NbCommonBytes (register U64 val) -{ -#if defined(LZ4_BIG_ENDIAN) - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanReverse64( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clzll(val) >> 3); - #else - int r; - if (!(val>>32)) { r=4; } else { r=0; val>>=32; } - if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } - r += (!val); - return r; - #endif -#else - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanForward64( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctzll(val) >> 3); - #else - 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 }; - return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58]; - #endif -#endif -} - -#else - -static inline int LZ4_NbCommonBytes (register U32 val) -{ -#if defined(LZ4_BIG_ENDIAN) - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanReverse( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clz(val) >> 3); - #else - int r; - if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } - r += (!val); - return r; - #endif -#else - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanForward( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctz(val) >> 3); - #else - 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 }; - return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; - #endif -#endif -} - -#endif - - - -//****************************** -// Compression functions -//****************************** - -// LZ4_compressCtx : -// ----------------- -// Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'. -// If it cannot achieve it, compression will stop, and result of the function will be zero. -// return : the number of bytes written in buffer 'dest', or 0 if the compression fails - -static inline int LZ4_compressCtx(void** ctx, - const char* source, - char* dest, - int isize, - int maxOutputSize) -{ -#if HEAPMODE - struct refTables *srt = (struct refTables *) (*ctx); - HTYPE* HashTable; -#else - HTYPE HashTable[HASHTABLESIZE] = {0}; -#endif - - const BYTE* ip = (BYTE*) source; - INITBASE(base); - const BYTE* anchor = ip; - const BYTE* const iend = ip + isize; - const BYTE* const mflimit = iend - MFLIMIT; -#define matchlimit (iend - LASTLITERALS) - - BYTE* op = (BYTE*) dest; - BYTE* const oend = op + maxOutputSize; - - int len, length; - const int skipStrength = SKIPSTRENGTH; - U32 forwardH; - - - // Init - if (isize<MINLENGTH) goto _last_literals; -#if HEAPMODE - if (*ctx == NULL) - { - srt = (struct refTables *) malloc ( sizeof(struct refTables) ); - *ctx = (void*) srt; - } - HashTable = (HTYPE*)(srt->hashTable); - memset((void*)HashTable, 0, sizeof(srt->hashTable)); -#else - (void) ctx; -#endif - - - // First Byte - HashTable[LZ4_HASH_VALUE(ip)] = ip - base; - ip++; forwardH = LZ4_HASH_VALUE(ip); - - // Main Loop - for ( ; ; ) - { - int findMatchAttempts = (1U << skipStrength) + 3; - const BYTE* forwardIp = ip; - const BYTE* ref; - BYTE* token; - - // Find a match - do { - U32 h = forwardH; - int step = findMatchAttempts++ >> skipStrength; - ip = forwardIp; - forwardIp = ip + step; - - if unlikely(forwardIp > mflimit) { goto _last_literals; } - - forwardH = LZ4_HASH_VALUE(forwardIp); - ref = base + HashTable[h]; - HashTable[h] = ip - base; - - } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip))); - - // Catch up - while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; } - - // Encode Literal length - length = (int)(ip - anchor); - token = op++; - if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) > oend) return 0; // Check output limit -#ifdef _MSC_VER - if (length>=(int)RUN_MASK) - { - int len = length-RUN_MASK; - *token=(RUN_MASK<<ML_BITS); - if (len>254) - { - do { *op++ = 255; len -= 255; } while (len>254); - *op++ = (BYTE)len; - memcpy(op, anchor, length); - op += length; - goto _next_match; - } - else - *op++ = (BYTE)len; - } - else *token = (length<<ML_BITS); -#else - if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } - else *token = (length<<ML_BITS); -#endif - - // Copy Literals - LZ4_BLINDCOPY(anchor, op, length); - -_next_match: - // Encode Offset - LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); - - // Start Counting - ip+=MINMATCH; ref+=MINMATCH; // MinMatch verified - anchor = ip; - while likely(ip<matchlimit-(STEPSIZE-1)) - { - UARCH diff = AARCH(ref) ^ AARCH(ip); - if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; } - ip += LZ4_NbCommonBytes(diff); - goto _endCount; - } - if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; } - if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; } - if ((ip<matchlimit) && (*ref == *ip)) ip++; -_endCount: - - // Encode MatchLength - len = (int)(ip - anchor); - if unlikely(op + (1 + LASTLITERALS) + (len>>8) > oend) return 0; // Check output limit - 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; } - else *token += len; - - // Test end of chunk - if (ip > mflimit) { anchor = ip; break; } - - // Fill table - HashTable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base; - - // Test next position - ref = base + HashTable[LZ4_HASH_VALUE(ip)]; - HashTable[LZ4_HASH_VALUE(ip)] = ip - base; - if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } - - // Prepare next loop - anchor = ip++; - forwardH = LZ4_HASH_VALUE(ip); - } - -_last_literals: - // Encode Last Literals - { - int lastRun = (int)(iend - anchor); - if (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) return 0; - if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } - else *op++ = (lastRun<<ML_BITS); - memcpy(op, anchor, iend - anchor); - op += iend-anchor; - } - - // End - return (int) (((char*)op)-dest); -} - - - -// Note : this function is valid only if isize < LZ4_64KLIMIT -#define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1)) -#define HASHLOG64K (HASH_LOG+1) -#define HASH64KTABLESIZE (1U<<HASHLOG64K) -#define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASHLOG64K)) -#define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p)) -static inline int LZ4_compress64kCtx(void** ctx, - const char* source, - char* dest, - int isize, - int maxOutputSize) -{ -#if HEAPMODE - struct refTables *srt = (struct refTables *) (*ctx); - U16* HashTable; -#else - U16 HashTable[HASH64KTABLESIZE] = {0}; -#endif - - const BYTE* ip = (BYTE*) source; - const BYTE* anchor = ip; - const BYTE* const base = ip; - const BYTE* const iend = ip + isize; - const BYTE* const mflimit = iend - MFLIMIT; -#define matchlimit (iend - LASTLITERALS) - - BYTE* op = (BYTE*) dest; - BYTE* const oend = op + maxOutputSize; - - int len, length; - const int skipStrength = SKIPSTRENGTH; - U32 forwardH; - - - // Init - if (isize<MINLENGTH) goto _last_literals; -#if HEAPMODE - if (*ctx == NULL) - { - srt = (struct refTables *) malloc ( sizeof(struct refTables) ); - *ctx = (void*) srt; - } - HashTable = (U16*)(srt->hashTable); - memset((void*)HashTable, 0, sizeof(srt->hashTable)); -#else - (void) ctx; -#endif - - - // First Byte - ip++; forwardH = LZ4_HASH64K_VALUE(ip); - - // Main Loop - for ( ; ; ) - { - int findMatchAttempts = (1U << skipStrength) + 3; - const BYTE* forwardIp = ip; - const BYTE* ref; - BYTE* token; - - // Find a match - do { - U32 h = forwardH; - int step = findMatchAttempts++ >> skipStrength; - ip = forwardIp; - forwardIp = ip + step; - - if (forwardIp > mflimit) { goto _last_literals; } - - forwardH = LZ4_HASH64K_VALUE(forwardIp); - ref = base + HashTable[h]; - HashTable[h] = (U16)(ip - base); - - } while (A32(ref) != A32(ip)); - - // Catch up - while ((ip>anchor) && (ref>(BYTE*)source) && (ip[-1]==ref[-1])) { ip--; ref--; } - - // Encode Literal length - length = (int)(ip - anchor); - token = op++; - if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) > oend) return 0; // Check output limit -#ifdef _MSC_VER - if (length>=(int)RUN_MASK) - { - int len = length-RUN_MASK; - *token=(RUN_MASK<<ML_BITS); - if (len>254) - { - do { *op++ = 255; len -= 255; } while (len>254); - *op++ = (BYTE)len; - memcpy(op, anchor, length); - op += length; - goto _next_match; - } - else - *op++ = (BYTE)len; - } - else *token = (length<<ML_BITS); -#else - if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } - else *token = (length<<ML_BITS); -#endif - - // Copy Literals - LZ4_BLINDCOPY(anchor, op, length); - -_next_match: - // Encode Offset - LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); - - // Start Counting - ip+=MINMATCH; ref+=MINMATCH; // MinMatch verified - anchor = ip; - while (ip<matchlimit-(STEPSIZE-1)) - { - UARCH diff = AARCH(ref) ^ AARCH(ip); - if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; } - ip += LZ4_NbCommonBytes(diff); - goto _endCount; - } - if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; } - if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; } - if ((ip<matchlimit) && (*ref == *ip)) ip++; -_endCount: - - // Encode MatchLength - len = (int)(ip - anchor); - if unlikely(op + (1 + LASTLITERALS) + (len>>8) > oend) return 0; // Check output limit - 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; } - else *token += len; - - // Test end of chunk - if (ip > mflimit) { anchor = ip; break; } - - // Fill table - HashTable[LZ4_HASH64K_VALUE(ip-2)] = (U16)(ip - 2 - base); - - // Test next position - ref = base + HashTable[LZ4_HASH64K_VALUE(ip)]; - HashTable[LZ4_HASH64K_VALUE(ip)] = (U16)(ip - base); - if (A32(ref) == A32(ip)) { token = op++; *token=0; goto _next_match; } - - // Prepare next loop - anchor = ip++; - forwardH = LZ4_HASH64K_VALUE(ip); - } - -_last_literals: - // Encode Last Literals - { - int lastRun = (int)(iend - anchor); - if (op + lastRun + 1 + (lastRun-RUN_MASK+255)/255 > oend) return 0; - if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } - else *op++ = (lastRun<<ML_BITS); - memcpy(op, anchor, iend - anchor); - op += iend-anchor; - } - - // End - return (int) (((char*)op)-dest); -} - - -int LZ4_compress_limitedOutput(const char* source, - char* dest, - int isize, - int maxOutputSize) -{ -#if HEAPMODE - void* ctx = malloc(sizeof(struct refTables)); - int result; - if (isize < LZ4_64KLIMIT) - result = LZ4_compress64kCtx(&ctx, source, dest, isize, maxOutputSize); - else result = LZ4_compressCtx(&ctx, source, dest, isize, maxOutputSize); - free(ctx); - return result; -#else - if (isize < (int)LZ4_64KLIMIT) return LZ4_compress64kCtx(NULL, source, dest, isize, maxOutputSize); - return LZ4_compressCtx(NULL, source, dest, isize, maxOutputSize); -#endif -} - - -int LZ4_compress(const char* source, - char* dest, - int isize) -{ - return LZ4_compress_limitedOutput(source, dest, isize, LZ4_compressBound(isize)); -} - - - - -//**************************** -// Decompression functions -//**************************** - -// Note : The decoding functions LZ4_uncompress() and LZ4_uncompress_unknownOutputSize() -// are safe against "buffer overflow" attack type. -// They will never write nor read outside of the provided output buffers. -// LZ4_uncompress_unknownOutputSize() also insures that it will never read outside of the input buffer. -// A corrupted input will produce an error result, a negative int, indicating the position of the error within input stream. - -int LZ4_uncompress(const char* source, - char* dest, - int osize) -{ - // Local Variables - const BYTE* restrict ip = (const BYTE*) source; - const BYTE* ref; - - BYTE* op = (BYTE*) dest; - BYTE* const oend = op + osize; - BYTE* cpy; - - unsigned token; - - size_t length; - size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; -#if LZ4_ARCH64 - size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; -#endif - - - // Main Loop - while (1) - { - // get runlength - token = *ip++; - if ((length=(token>>ML_BITS)) == RUN_MASK) { size_t len; for (;(len=*ip++)==255;length+=255){} length += len; } - - // copy literals - cpy = op+length; - if unlikely(cpy>oend-COPYLENGTH) - { - if (cpy != oend) goto _output_error; // Error : not enough place for another match (min 4) + 5 literals - memcpy(op, ip, length); - ip += length; - break; // EOF - } - LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy; - - // get offset - LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2; - if unlikely(ref < (BYTE* const)dest) goto _output_error; // Error : offset create reference outside destination buffer - - // get matchlength - if ((length=(token&ML_MASK)) == ML_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; } - - // copy repeated sequence - if unlikely((op-ref)<STEPSIZE) - { -#if LZ4_ARCH64 - size_t dec64 = dec64table[op-ref]; -#else - const int dec64 = 0; -#endif - op[0] = ref[0]; - op[1] = ref[1]; - op[2] = ref[2]; - op[3] = ref[3]; - op += 4, ref += 4; ref -= dec32table[op-ref]; - A32(op) = A32(ref); - op += STEPSIZE-4; ref -= dec64; - } else { LZ4_COPYSTEP(ref,op); } - cpy = op + length - (STEPSIZE-4); - if (cpy>oend-COPYLENGTH) - { - if (cpy > oend) goto _output_error; // Error : request to write beyond destination buffer - LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH)); - while(op<cpy) *op++=*ref++; - op=cpy; - if (op == oend) goto _output_error; // Check EOF (should never happen, since last 5 bytes are supposed to be literals) - continue; - } - LZ4_SECURECOPY(ref, op, cpy); - op=cpy; // correction - } - - // end of decoding - return (int) (((char*)ip)-source); - - // write overflow error detected -_output_error: - return (int) (-(((char*)ip)-source)); -} - - -int LZ4_uncompress_unknownOutputSize( - const char* source, - char* dest, - int isize, - int maxOutputSize) -{ - // Local Variables - const BYTE* restrict ip = (const BYTE*) source; - const BYTE* const iend = ip + isize; - const BYTE* ref; - - BYTE* op = (BYTE*) dest; - BYTE* const oend = op + maxOutputSize; - BYTE* cpy; - - size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; -#if LZ4_ARCH64 - size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; -#endif - - - // Main Loop - while (ip<iend) - { - unsigned token; - size_t length; - - // get runlength - token = *ip++; - if ((length=(token>>ML_BITS)) == RUN_MASK) { int s=255; while ((ip<iend) && (s==255)) { s=*ip++; length += s; } } - - // copy literals - cpy = op+length; - if ((cpy>oend-COPYLENGTH) || (ip+length>iend-COPYLENGTH)) - { - if (cpy > oend) goto _output_error; // Error : writes beyond output buffer - if (ip+length != iend) goto _output_error; // Error : LZ4 format requires to consume all input at this stage - memcpy(op, ip, length); - op += length; - break; // Necessarily EOF, due to parsing restrictions - } - LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy; - - // get offset - LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2; - if (ref < (BYTE* const)dest) goto _output_error; // Error : offset creates reference outside of destination buffer - - // get matchlength - if ((length=(token&ML_MASK)) == ML_MASK) { while (ip<iend) { int s = *ip++; length +=s; if (s==255) continue; break; } } - - // copy repeated sequence - if unlikely(op-ref<STEPSIZE) - { -#if LZ4_ARCH64 - size_t dec64 = dec64table[op-ref]; -#else - const int dec64 = 0; -#endif - op[0] = ref[0]; - op[1] = ref[1]; - op[2] = ref[2]; - op[3] = ref[3]; - op += 4, ref += 4; ref -= dec32table[op-ref]; - A32(op) = A32(ref); - op += STEPSIZE-4; ref -= dec64; - } else { LZ4_COPYSTEP(ref,op); } - cpy = op + length - (STEPSIZE-4); - if (cpy>oend-COPYLENGTH) - { - if (cpy > oend) goto _output_error; // Error : request to write outside of destination buffer - LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH)); - while(op<cpy) *op++=*ref++; - op=cpy; - if (op == oend) goto _output_error; // Check EOF (should never happen, since last 5 bytes are supposed to be literals) - continue; - } - LZ4_SECURECOPY(ref, op, cpy); - op=cpy; // correction - } - - // end of decoding - return (int) (((char*)op)-dest); - - // write overflow error detected -_output_error: - return (int) (-(((char*)ip)-source)); -} - +/*+ LZ4 - Fast LZ compression algorithm+ Copyright (C) 2011-2014, Yann Collet.+ BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++ Redistribution and use in source and binary forms, with or without+ modification, are permitted provided that the following conditions are+ met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.+ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following disclaimer+ in the documentation and/or other materials provided with the+ distribution.++ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+ OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++ You can contact the author at :+ - LZ4 source repository : http://code.google.com/p/lz4/+ - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c+*/++/**************************************+ Tuning parameters+**************************************/+/*+ * HEAPMODE :+ * Select how default compression functions will allocate memory for their hash table,+ * in memory stack (0:default, fastest), or in memory heap (1:requires memory allocation (malloc)).+ */+#define HEAPMODE 0+++/**************************************+ CPU Feature Detection+**************************************/+/* 32 or 64 bits ? */+#if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \+ || defined(__powerpc64__) || defined(__powerpc64le__) \+ || defined(__ppc64__) || defined(__ppc64le__) \+ || defined(__PPC64__) || defined(__PPC64LE__) \+ || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) /* Detects 64 bits mode */+# define LZ4_ARCH64 1+#else+# define LZ4_ARCH64 0+#endif++/*+ * Little Endian or Big Endian ?+ * Overwrite the #define below if you know your architecture endianess+ */+#include <stdlib.h> /* Apparently required to detect endianess */+#if defined (__GLIBC__)+# include <endian.h>+# if (__BYTE_ORDER == __BIG_ENDIAN)+# define LZ4_BIG_ENDIAN 1+# endif+#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))+# define LZ4_BIG_ENDIAN 1+#elif defined(__sparc) || defined(__sparc__) \+ || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \+ || defined(__hpux) || defined(__hppa) \+ || defined(_MIPSEB) || defined(__s390__)+# define LZ4_BIG_ENDIAN 1+#else+/* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */+#endif++/*+ * Unaligned memory access is automatically enabled for "common" CPU, such as x86.+ * For others CPU, such as ARM, the compiler may be more cautious, inserting unnecessary extra code to ensure aligned access property+ * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance+ */+#if defined(__ARM_FEATURE_UNALIGNED)+# define LZ4_FORCE_UNALIGNED_ACCESS 1+#endif++/* Define this parameter if your target system or compiler does not support hardware bit count */+#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */+# define LZ4_FORCE_SW_BITCOUNT+#endif++/*+ * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :+ * This option may provide a small boost to performance for some big endian cpu, although probably modest.+ * You may set this option to 1 if data will remain within closed environment.+ * This option is useless on Little_Endian CPU (such as x86)+ */++/* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */+++/**************************************+ Compiler Options+**************************************/+#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */+/* "restrict" is a known keyword */+#else+# define restrict /* Disable restrict */+#endif++#ifdef _MSC_VER /* Visual Studio */+# define FORCE_INLINE static __forceinline+# include <intrin.h> /* For Visual 2005 */+# if LZ4_ARCH64 /* 64-bits */+# pragma intrinsic(_BitScanForward64) /* For Visual 2005 */+# pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */+# else /* 32-bits */+# pragma intrinsic(_BitScanForward) /* For Visual 2005 */+# pragma intrinsic(_BitScanReverse) /* For Visual 2005 */+# endif+# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */+#else+# ifdef __GNUC__+# define FORCE_INLINE static inline __attribute__((always_inline))+# else+# define FORCE_INLINE static inline+# endif+#endif++#ifdef _MSC_VER /* Visual Studio */+# define lz4_bswap16(x) _byteswap_ushort(x)+#else+# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))+#endif++#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)++#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)+# define expect(expr,value) (__builtin_expect ((expr),(value)) )+#else+# define expect(expr,value) (expr)+#endif++#define likely(expr) expect((expr) != 0, 1)+#define unlikely(expr) expect((expr) != 0, 0)+++/**************************************+ Memory routines+**************************************/+#include <stdlib.h> /* malloc, calloc, free */+#define ALLOCATOR(n,s) calloc(n,s)+#define FREEMEM free+#include <string.h> /* memset, memcpy */+#define MEM_INIT memset+++/**************************************+ Includes+**************************************/+#include "lz4.h"+++/**************************************+ Basic Types+**************************************/+#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */+# include <stdint.h>+ typedef uint8_t BYTE;+ typedef uint16_t U16;+ typedef uint32_t U32;+ typedef int32_t S32;+ typedef uint64_t U64;+#else+ typedef unsigned char BYTE;+ typedef unsigned short U16;+ typedef unsigned int U32;+ typedef signed int S32;+ typedef unsigned long long U64;+#endif++#if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS)+# define _PACKED __attribute__ ((packed))+#else+# define _PACKED+#endif++#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)+# if defined(__IBMC__) || defined(__SUNPRO_C) || defined(__SUNPRO_CC)+# pragma pack(1)+# else+# pragma pack(push, 1)+# endif+#endif++typedef struct { U16 v; } _PACKED U16_S;+typedef struct { U32 v; } _PACKED U32_S;+typedef struct { U64 v; } _PACKED U64_S;+typedef struct {size_t v;} _PACKED size_t_S;++#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)+# if defined(__SUNPRO_C) || defined(__SUNPRO_CC)+# pragma pack(0)+# else+# pragma pack(pop)+# endif+#endif++#define A16(x) (((U16_S *)(x))->v)+#define A32(x) (((U32_S *)(x))->v)+#define A64(x) (((U64_S *)(x))->v)+#define AARCH(x) (((size_t_S *)(x))->v)+++/**************************************+ Constants+**************************************/+#define LZ4_HASHLOG (LZ4_MEMORY_USAGE-2)+#define HASHTABLESIZE (1 << LZ4_MEMORY_USAGE)+#define HASH_SIZE_U32 (1 << LZ4_HASHLOG)++#define MINMATCH 4++#define COPYLENGTH 8+#define LASTLITERALS 5+#define MFLIMIT (COPYLENGTH+MINMATCH)+static const int LZ4_minLength = (MFLIMIT+1);++#define KB *(1U<<10)+#define MB *(1U<<20)+#define GB *(1U<<30)++#define LZ4_64KLIMIT ((64 KB) + (MFLIMIT-1))+#define SKIPSTRENGTH 6 /* Increasing this value will make the compression run slower on incompressible data */++#define MAXD_LOG 16+#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)++#define ML_BITS 4+#define ML_MASK ((1U<<ML_BITS)-1)+#define RUN_BITS (8-ML_BITS)+#define RUN_MASK ((1U<<RUN_BITS)-1)+++/**************************************+ Structures and local types+**************************************/+typedef struct {+ U32 hashTable[HASH_SIZE_U32];+ U32 currentOffset;+ U32 initCheck;+ const BYTE* dictionary;+ const BYTE* bufferStart;+ U32 dictSize;+} LZ4_stream_t_internal;++typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive;+typedef enum { byPtr, byU32, byU16 } tableType_t;++typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;+typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;++typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;+typedef enum { full = 0, partial = 1 } earlyEnd_directive;+++/**************************************+ Architecture-specific macros+**************************************/+#define STEPSIZE sizeof(size_t)+#define LZ4_COPYSTEP(d,s) { AARCH(d) = AARCH(s); d+=STEPSIZE; s+=STEPSIZE; }+#define LZ4_COPY8(d,s) { LZ4_COPYSTEP(d,s); if (STEPSIZE<8) LZ4_COPYSTEP(d,s); }++#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))+# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }+# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }+#else /* Little Endian */+# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }+# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }+#endif+++/**************************************+ Macros+**************************************/+#define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */+#if LZ4_ARCH64 || !defined(__GNUC__)+# define LZ4_WILDCOPY(d,s,e) { do { LZ4_COPY8(d,s) } while (d<e); } /* at the end, d>=e; */+#else+# define LZ4_WILDCOPY(d,s,e) { if (likely(e-d <= 8)) LZ4_COPY8(d,s) else do { LZ4_COPY8(d,s) } while (d<e); }+#endif+++/****************************+ Private local functions+****************************/+#if LZ4_ARCH64++int LZ4_NbCommonBytes (register U64 val)+{+# if defined(LZ4_BIG_ENDIAN)+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r = 0;+ _BitScanReverse64( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_clzll(val) >> 3);+# else+ int r;+ if (!(val>>32)) { r=4; } else { r=0; val>>=32; }+ if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }+ r += (!val);+ return r;+# endif+# else+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r = 0;+ _BitScanForward64( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_ctzll(val) >> 3);+# else+ 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 };+ return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];+# endif+# endif+}++#else++int LZ4_NbCommonBytes (register U32 val)+{+# if defined(LZ4_BIG_ENDIAN)+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r = 0;+ _BitScanReverse( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_clz(val) >> 3);+# else+ int r;+ if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }+ r += (!val);+ return r;+# endif+# else+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r;+ _BitScanForward( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_ctz(val) >> 3);+# else+ 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 };+ return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];+# endif+# endif+}++#endif+++/********************************+ Compression functions+********************************/+int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); }++static int LZ4_hashSequence(U32 sequence, tableType_t tableType)+{+ if (tableType == byU16)+ return (((sequence) * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));+ else+ return (((sequence) * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));+}++static int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); }++static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)+{+ switch (tableType)+ {+ case byPtr: { const BYTE** hashTable = (const BYTE**) tableBase; hashTable[h] = p; break; }+ case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); break; }+ case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); break; }+ }+}++static void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)+{+ U32 h = LZ4_hashPosition(p, tableType);+ LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);+}++static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)+{+ if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }+ if (tableType == byU32) { U32* hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }+ { U16* hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */+}++static const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)+{+ U32 h = LZ4_hashPosition(p, tableType);+ return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);+}++static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimit)+{+ const BYTE* const pStart = pIn;++ while (likely(pIn<pInLimit-(STEPSIZE-1)))+ {+ size_t diff = AARCH(pRef) ^ AARCH(pIn);+ if (!diff) { pIn+=STEPSIZE; pRef+=STEPSIZE; continue; }+ pIn += LZ4_NbCommonBytes(diff);+ return (unsigned)(pIn - pStart);+ }+ if (sizeof(void*)==8) if ((pIn<(pInLimit-3)) && (A32(pRef) == A32(pIn))) { pIn+=4; pRef+=4; }+ if ((pIn<(pInLimit-1)) && (A16(pRef) == A16(pIn))) { pIn+=2; pRef+=2; }+ if ((pIn<pInLimit) && (*pRef == *pIn)) pIn++;++ return (unsigned)(pIn - pStart);+}+++static int LZ4_compress_generic(+ void* ctx,+ const char* source,+ char* dest,+ int inputSize,+ int maxOutputSize,++ limitedOutput_directive outputLimited,+ tableType_t tableType,+ dict_directive dict,+ dictIssue_directive dictIssue)+{+ LZ4_stream_t_internal* const dictPtr = (LZ4_stream_t_internal*)ctx;++ const BYTE* ip = (const BYTE*) source;+ const BYTE* base;+ const BYTE* lowLimit;+ const BYTE* const lowRefLimit = ip - dictPtr->dictSize;+ const BYTE* const dictionary = dictPtr->dictionary;+ const BYTE* const dictEnd = dictionary + dictPtr->dictSize;+ const size_t dictDelta = dictEnd - (const BYTE*)source;+ const BYTE* anchor = (const BYTE*) source;+ const BYTE* const iend = ip + inputSize;+ const BYTE* const mflimit = iend - MFLIMIT;+ const BYTE* const matchlimit = iend - LASTLITERALS;++ BYTE* op = (BYTE*) dest;+ BYTE* const olimit = op + maxOutputSize;++ const int skipStrength = SKIPSTRENGTH;+ U32 forwardH;+ size_t refDelta=0;++ /* Init conditions */+ if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */+ switch(dict)+ {+ case noDict:+ default:+ base = (const BYTE*)source;+ lowLimit = (const BYTE*)source;+ break;+ case withPrefix64k:+ base = (const BYTE*)source - dictPtr->currentOffset;+ lowLimit = (const BYTE*)source - dictPtr->dictSize;+ break;+ case usingExtDict:+ base = (const BYTE*)source - dictPtr->currentOffset;+ lowLimit = (const BYTE*)source;+ break;+ }+ if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0; /* Size too large (not within 64K limit) */+ if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */++ /* First Byte */+ LZ4_putPosition(ip, ctx, tableType, base);+ ip++; forwardH = LZ4_hashPosition(ip, tableType);++ /* Main Loop */+ for ( ; ; )+ {+ const BYTE* ref;+ BYTE* token;+ {+ const BYTE* forwardIp = ip;+ unsigned step=1;+ unsigned searchMatchNb = (1U << skipStrength);++ /* Find a match */+ do {+ U32 h = forwardH;+ ip = forwardIp;+ forwardIp += step;+ step = searchMatchNb++ >> skipStrength;+ //if (step>8) step=8; // required for valid forwardIp ; slows down uncompressible data a bit++ if (unlikely(forwardIp > mflimit)) goto _last_literals;++ ref = LZ4_getPositionOnHash(h, ctx, tableType, base);+ if (dict==usingExtDict)+ {+ if (ref<(const BYTE*)source)+ {+ refDelta = dictDelta;+ lowLimit = dictionary;+ }+ else+ {+ refDelta = 0;+ lowLimit = (const BYTE*)source;+ }+ }+ forwardH = LZ4_hashPosition(forwardIp, tableType);+ LZ4_putPositionOnHash(ip, h, ctx, tableType, base);++ } while ( ((dictIssue==dictSmall) ? (ref < lowRefLimit) : 0)+ || ((tableType==byU16) ? 0 : (ref + MAX_DISTANCE < ip))+ || (A32(ref+refDelta) != A32(ip)) );+ }++ /* Catch up */+ while ((ip>anchor) && (ref+refDelta > lowLimit) && (unlikely(ip[-1]==ref[refDelta-1]))) { ip--; ref--; }++ {+ /* Encode Literal length */+ unsigned litLength = (unsigned)(ip - anchor);+ token = op++;+ if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))+ return 0; /* Check output limit */+ if (litLength>=RUN_MASK)+ {+ int len = (int)litLength-RUN_MASK;+ *token=(RUN_MASK<<ML_BITS);+ for(; len >= 255 ; len-=255) *op++ = 255;+ *op++ = (BYTE)len;+ }+ else *token = (BYTE)(litLength<<ML_BITS);++ /* Copy Literals */+ { BYTE* end = op+litLength; LZ4_WILDCOPY(op,anchor,end); op=end; }+ }++_next_match:+ /* Encode Offset */+ LZ4_WRITE_LITTLEENDIAN_16(op, (U16)(ip-ref));++ /* Encode MatchLength */+ {+ unsigned matchLength;++ if ((dict==usingExtDict) && (lowLimit==dictionary))+ {+ const BYTE* limit;+ ref += refDelta;+ limit = ip + (dictEnd-ref);+ if (limit > matchlimit) limit = matchlimit;+ matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, limit);+ ip += MINMATCH + matchLength;+ if (ip==limit)+ {+ unsigned more = LZ4_count(ip, (const BYTE*)source, matchlimit);+ matchLength += more;+ ip += more;+ }+ }+ else+ {+ matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit);+ ip += MINMATCH + matchLength;+ }++ if (matchLength>=ML_MASK)+ {+ if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit)))+ return 0; /* Check output limit */+ *token += ML_MASK;+ matchLength -= ML_MASK;+ for (; matchLength >= 510 ; matchLength-=510) { *op++ = 255; *op++ = 255; }+ if (matchLength >= 255) { matchLength-=255; *op++ = 255; }+ *op++ = (BYTE)matchLength;+ }+ else *token += (BYTE)(matchLength);+ }++ anchor = ip;++ /* Test end of chunk */+ if (ip > mflimit) break;++ /* Fill table */+ LZ4_putPosition(ip-2, ctx, tableType, base);++ /* Test next position */+ ref = LZ4_getPosition(ip, ctx, tableType, base);+ if (dict==usingExtDict)+ {+ if (ref<(const BYTE*)source)+ {+ refDelta = dictDelta;+ lowLimit = dictionary;+ }+ else+ {+ refDelta = 0;+ lowLimit = (const BYTE*)source;+ }+ }+ LZ4_putPosition(ip, ctx, tableType, base);+ if ( ((dictIssue==dictSmall) ? (ref>=lowRefLimit) : 1)+ && (ref+MAX_DISTANCE>=ip)+ && (A32(ref+refDelta)==A32(ip)) )+ { token=op++; *token=0; goto _next_match; }++ /* Prepare next loop */+ forwardH = LZ4_hashPosition(++ip, tableType);+ }++_last_literals:+ /* Encode Last Literals */+ {+ int lastRun = (int)(iend - anchor);+ if ((outputLimited) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize))+ return 0; /* Check output limit */+ if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun >= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }+ else *op++ = (BYTE)(lastRun<<ML_BITS);+ memcpy(op, anchor, iend - anchor);+ op += iend-anchor;+ }++ /* End */+ return (int) (((char*)op)-dest);+}+++int LZ4_compress(const char* source, char* dest, int inputSize)+{+#if (HEAPMODE)+ void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */+#else+ U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */+#endif+ int result;++ if (inputSize < (int)LZ4_64KLIMIT)+ result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue);+ else+ result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);++#if (HEAPMODE)+ FREEMEM(ctx);+#endif+ return result;+}++int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)+{+#if (HEAPMODE)+ void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */+#else+ U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */+#endif+ int result;++ if (inputSize < (int)LZ4_64KLIMIT)+ result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue);+ else+ result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);++#if (HEAPMODE)+ FREEMEM(ctx);+#endif+ return result;+}+++/*****************************************+ Experimental : Streaming functions+*****************************************/++void* LZ4_createStream()+{+ void* lz4s = ALLOCATOR(4, LZ4_STREAMSIZE_U32);+ MEM_INIT(lz4s, 0, LZ4_STREAMSIZE);+ return lz4s;+}++int LZ4_free (void* LZ4_stream)+{+ FREEMEM(LZ4_stream);+ return (0);+}+++int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize)+{+ LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict;+ const BYTE* p = (const BYTE*)dictionary;+ const BYTE* const dictEnd = p + dictSize;+ const BYTE* base;++ LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */+ if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_stream_t_internal)); /* Uninitialized structure detected */++ if (dictSize < MINMATCH)+ {+ dict->dictionary = NULL;+ dict->dictSize = 0;+ return 1;+ }++ if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB;+ base = p - dict->currentOffset;+ dict->dictionary = p;+ dict->dictSize = (U32)(dictEnd - p);+ dict->currentOffset += dict->dictSize;++ while (p <= dictEnd-MINMATCH)+ {+ LZ4_putPosition(p, dict, byU32, base);+ p+=3;+ }++ return 1;+}+++void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)+{+ if ((LZ4_dict->currentOffset > 0x80000000) ||+ ((size_t)LZ4_dict->currentOffset > (size_t)src)) /* address space overflow */+ {+ /* rescale hash table */+ U32 delta = LZ4_dict->currentOffset - 64 KB;+ const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;+ int i;+ for (i=0; i<HASH_SIZE_U32; i++)+ {+ if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;+ else LZ4_dict->hashTable[i] -= delta;+ }+ LZ4_dict->currentOffset = 64 KB;+ if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;+ LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;+ }+}+++FORCE_INLINE int LZ4_compress_continue_generic (void* LZ4_stream, const char* source, char* dest, int inputSize,+ int maxOutputSize, limitedOutput_directive limit)+{+ LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_stream;+ const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;++ const BYTE* smallest = (const BYTE*) source;+ if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */+ if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;+ LZ4_renormDictT(streamPtr, smallest);++ /* Check overlapping input/dictionary space */+ {+ const BYTE* sourceEnd = (const BYTE*) source + inputSize;+ if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd))+ {+ streamPtr->dictSize = (U32)(dictEnd - sourceEnd);+ if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;+ if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;+ streamPtr->dictionary = dictEnd - streamPtr->dictSize;+ }+ }++ /* prefix mode : source data follows dictionary */+ if (dictEnd == (const BYTE*)source)+ {+ int result;+ if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))+ result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, dictSmall);+ else+ result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, noDictIssue);+ streamPtr->dictSize += (U32)inputSize;+ streamPtr->currentOffset += (U32)inputSize;+ return result;+ }++ /* external dictionary mode */+ {+ int result;+ if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))+ result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, dictSmall);+ else+ result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, noDictIssue);+ streamPtr->dictionary = (const BYTE*)source;+ streamPtr->dictSize = (U32)inputSize;+ streamPtr->currentOffset += (U32)inputSize;+ return result;+ }+}+++int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize)+{+ return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, 0, notLimited);+}++int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize)+{+ return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limitedOutput);+}+++// Hidden debug function, to force separate dictionary mode+int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)+{+ LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_dict;+ int result;+ const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;++ const BYTE* smallest = dictEnd;+ if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;+ LZ4_renormDictT((LZ4_stream_t_internal*)LZ4_dict, smallest);++ result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue);++ streamPtr->dictionary = (const BYTE*)source;+ streamPtr->dictSize = (U32)inputSize;+ streamPtr->currentOffset += (U32)inputSize;++ return result;+}+++int LZ4_saveDict (void* LZ4_dict, char* safeBuffer, int dictSize)+{+ LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict;+ const BYTE* previousDictEnd = dict->dictionary + dict->dictSize;++ if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */+ if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;++ memcpy(safeBuffer, previousDictEnd - dictSize, dictSize);++ dict->dictionary = (const BYTE*)safeBuffer;+ dict->dictSize = (U32)dictSize;++ return 1;+}++++/****************************+ Decompression functions+****************************/+/*+ * This generic decompression function cover all use cases.+ * It shall be instanciated several times, using different sets of directives+ * Note that it is essential this generic function is really inlined,+ * in order to remove useless branches during compilation optimisation.+ */+FORCE_INLINE int LZ4_decompress_generic(+ const char* source,+ char* dest,+ int inputSize,+ int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */++ int endOnInput, /* endOnOutputSize, endOnInputSize */+ int partialDecoding, /* full, partial */+ int targetOutputSize, /* only used if partialDecoding==partial */+ int dict, /* noDict, withPrefix64k, usingExtDict */+ const char* dictStart, /* only if dict==usingExtDict */+ int dictSize /* note : = 0 if noDict */+ )+{+ /* Local Variables */+ const BYTE* restrict ip = (const BYTE*) source;+ const BYTE* ref;+ const BYTE* const iend = ip + inputSize;++ BYTE* op = (BYTE*) dest;+ BYTE* const oend = op + outputSize;+ BYTE* cpy;+ BYTE* oexit = op + targetOutputSize;+ const BYTE* const lowLimit = (const BYTE*)dest - dictSize;++ const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;+//#define OLD+#ifdef OLD+ const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */+#else+ const size_t dec32table[] = {4-0, 4-3, 4-2, 4-3, 4-0, 4-0, 4-0, 4-0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */+#endif+ static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};++ const int checkOffset = (endOnInput) && (dictSize < (int)(64 KB));+++ /* Special cases */+ if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */+ if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */+ if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);+++ /* Main Loop */+ while (1)+ {+ unsigned token;+ size_t length;++ /* get runlength */+ token = *ip++;+ if ((length=(token>>ML_BITS)) == RUN_MASK)+ {+ unsigned s;+ do+ {+ s = *ip++;+ length += s;+ }+ while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));+ //if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error; /* overflow detection */+ if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error; /* quickfix issue 134 */+ if ((endOnInput) && (sizeof(void*)==4) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error; /* quickfix issue 134 */+ }++ /* copy literals */+ cpy = op+length;+ if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )+ || ((!endOnInput) && (cpy>oend-COPYLENGTH)))+ {+ if (partialDecoding)+ {+ if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */+ if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */+ }+ else+ {+ if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */+ if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */+ }+ memcpy(op, ip, length);+ ip += length;+ op += length;+ break; /* Necessarily EOF, due to parsing restrictions */+ }+ LZ4_WILDCOPY(op, ip, cpy); ip -= (op-cpy); op = cpy;++ /* get offset */+ LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;+ if ((checkOffset) && (unlikely(ref < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */++ /* get matchlength */+ if ((length=(token&ML_MASK)) == ML_MASK)+ {+ unsigned s;+ do+ {+ if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;+ s = *ip++;+ length += s;+ } while (s==255);+ //if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error; /* overflow detection */+ if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error; /* quickfix issue 134 */+ }++ /* check external dictionary */+ if ((dict==usingExtDict) && (ref < (BYTE* const)dest))+ {+ if (unlikely(op+length+MINMATCH > oend-LASTLITERALS)) goto _output_error;++ if (length+MINMATCH <= (size_t)(dest-(char*)ref))+ {+ ref = dictEnd - (dest-(char*)ref);+ memcpy(op, ref, length+MINMATCH);+ op += length+MINMATCH;+ }+ else+ {+ size_t copySize = (size_t)(dest-(char*)ref);+ memcpy(op, dictEnd - copySize, copySize);+ op += copySize;+ copySize = length+MINMATCH - copySize;+ if (copySize > (size_t)((char*)op-dest)) /* overlap */+ {+ BYTE* const cpy = op + copySize;+ const BYTE* ref = (BYTE*)dest;+ while (op < cpy) *op++ = *ref++;+ }+ else+ {+ memcpy(op, dest, copySize);+ op += copySize;+ }+ }+ continue;+ }++ /* copy repeated sequence */+ if (unlikely((op-ref)<(int)STEPSIZE))+ {+ const size_t dec64 = dec64table[(sizeof(void*)==4) ? 0 : op-ref];+ op[0] = ref[0];+ op[1] = ref[1];+ op[2] = ref[2];+ op[3] = ref[3];+#ifdef OLD+ op += 4, ref += 4; ref -= dec32table[op-ref];+ A32(op) = A32(ref);+ op += STEPSIZE-4; ref -= dec64;+#else+ ref += dec32table[op-ref];+ A32(op+4) = A32(ref);+ op += STEPSIZE; ref -= dec64;+#endif+ } else { LZ4_COPYSTEP(op,ref); }+ cpy = op + length - (STEPSIZE-4);++ if (unlikely(cpy>oend-COPYLENGTH-(STEPSIZE-4)))+ {+ if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last 5 bytes must be literals */+ if (op<oend-COPYLENGTH) LZ4_WILDCOPY(op, ref, (oend-COPYLENGTH));+ while(op<cpy) *op++=*ref++;+ op=cpy;+ continue;+ }+ LZ4_WILDCOPY(op, ref, cpy);+ op=cpy; /* correction */+ }++ /* end of decoding */+ if (endOnInput)+ return (int) (((char*)op)-dest); /* Nb of output bytes decoded */+ else+ return (int) (((char*)ip)-source); /* Nb of input bytes read */++ /* Overflow error detected */+_output_error:+ return (int) (-(((char*)ip)-source))-1;+}+++int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxOutputSize)+{+ return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, noDict, NULL, 0);+}++int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize)+{+ return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, partial, targetOutputSize, noDict, NULL, 0);+}++int LZ4_decompress_fast(const char* source, char* dest, int originalSize)+{+ return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 0);+}++/* streaming decompression functions */++//#define LZ4_STREAMDECODESIZE_U32 4+//#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int))+//typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t;+typedef struct+{+ const char* dictionary;+ int dictSize;+} LZ4_streamDecode_t_internal;++/*+ * If you prefer dynamic allocation methods,+ * LZ4_createStreamDecode()+ * provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure.+ */+void* LZ4_createStreamDecode()+{+ void* lz4s = ALLOCATOR(sizeof(U32), LZ4_STREAMDECODESIZE_U32);+ MEM_INIT(lz4s, 0, LZ4_STREAMDECODESIZE);+ return lz4s;+}++/*+ * LZ4_setDictDecode+ * Use this function to instruct where to find the dictionary+ * This function is not necessary if previous data is still available where it was decoded.+ * Loading a size of 0 is allowed (same effect as no dictionary).+ * Return : 1 if OK, 0 if error+ */+int LZ4_setDictDecode (void* LZ4_streamDecode, const char* dictionary, int dictSize)+{+ LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;+ lz4sd->dictionary = dictionary;+ lz4sd->dictSize = dictSize;+ return 1;+}++/*+*_continue() :+ These decoding functions allow decompression of multiple blocks in "streaming" mode.+ Previously decoded blocks must still be available at the memory position where they were decoded.+ If it's not possible, save the relevant part of decoded data into a safe buffer,+ and indicate where it stands using LZ4_setDictDecode()+*/+int LZ4_decompress_safe_continue (void* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)+{+ LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;+ int result;++ result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize);+ if (result <= 0) return result;+ if (lz4sd->dictionary + lz4sd->dictSize == dest)+ {+ lz4sd->dictSize += result;+ }+ else+ {+ lz4sd->dictionary = dest;+ lz4sd->dictSize = result;+ }++ return result;+}++int LZ4_decompress_fast_continue (void* LZ4_streamDecode, const char* source, char* dest, int originalSize)+{+ LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;+ int result;++ result = LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize);+ if (result <= 0) return result;+ if (lz4sd->dictionary + lz4sd->dictSize == dest)+ {+ lz4sd->dictSize += result;+ }+ else+ {+ lz4sd->dictionary = dest;+ lz4sd->dictSize = result;+ }++ return result;+}+++/*+Advanced decoding functions :+*_usingDict() :+ These decoding functions work the same as "_continue" ones,+ the dictionary must be explicitly provided within parameters+*/++int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)+{+ return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, dictStart, dictSize);+}++int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)+{+ return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, dictStart, dictSize);+}+++/***************************************************+ Obsolete Functions+***************************************************/+/*+These function names are deprecated and should no longer be used.+They are only provided here for compatibility with older user programs.+- LZ4_uncompress is totally equivalent to LZ4_decompress_fast+- LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe+*/+int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); }+int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); }+++/* Obsolete Streaming functions */++int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; }++void LZ4_init(LZ4_stream_t_internal* lz4ds, const BYTE* base)+{+ MEM_INIT(lz4ds, 0, LZ4_STREAMSIZE);+ lz4ds->bufferStart = base;+}++int LZ4_resetStreamState(void* state, const char* inputBuffer)+{+ if ((((size_t)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */+ LZ4_init((LZ4_stream_t_internal*)state, (const BYTE*)inputBuffer);+ return 0;+}++void* LZ4_create (const char* inputBuffer)+{+ void* lz4ds = ALLOCATOR(4, LZ4_STREAMSIZE_U32);+ LZ4_init ((LZ4_stream_t_internal*)lz4ds, (const BYTE*)inputBuffer);+ return lz4ds;+}++char* LZ4_slideInputBuffer (void* LZ4_Data)+{+ LZ4_stream_t_internal* lz4ds = (LZ4_stream_t_internal*)LZ4_Data;++ LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB);++ return (char*)(lz4ds->bufferStart + 64 KB);+}++/* Obsolete compresson functions using User-allocated state */++int LZ4_sizeofState() { return LZ4_STREAMSIZE; }++int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize)+{+ if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */+ MEM_INIT(state, 0, LZ4_STREAMSIZE);++ if (inputSize < (int)LZ4_64KLIMIT)+ return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue);+ else+ return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);+}++int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize)+{+ if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */+ MEM_INIT(state, 0, LZ4_STREAMSIZE);++ if (inputSize < (int)LZ4_64KLIMIT)+ return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue);+ else+ return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);+}++/* Obsolete streaming decompression functions */++int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)+{+ return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, NULL, 64 KB);+}++int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)+{+ return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 64 KB);+}
src/cbits/lz4.h view
@@ -1,128 +1,306 @@-/* - LZ4 - Fast LZ compression algorithm - Header File - Copyright (C) 2011-2012, Yann Collet. - BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following disclaimer - in the documentation and/or other materials provided with the - distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - You can contact the author at : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ -*/ -#pragma once - -#if defined (__cplusplus) -extern "C" { -#endif - - -//************************************** -// Compiler Options -//************************************** -#if defined(_MSC_VER) && !defined(__cplusplus) // Visual Studio -# define inline __inline // Visual is not C99, but supports some kind of inline -#endif - - -//**************************** -// Simple Functions -//**************************** - -int LZ4_compress (const char* source, char* dest, int isize); -int LZ4_uncompress (const char* source, char* dest, int osize); - -/* -LZ4_compress() : - Compresses 'isize' bytes from 'source' into 'dest'. - Destination buffer must be already allocated, - and must be sized to handle worst cases situations (input data not compressible) - Worst case size evaluation is provided by function LZ4_compressBound() - - isize : is the input size. Max supported value is ~1.9GB - return : the number of bytes written in buffer dest - - -LZ4_uncompress() : - osize : is the output size, therefore the original size - return : the number of bytes read in the source buffer - If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction - This function never writes outside of provided buffers, and never modifies input buffer. - note : destination buffer must be already allocated. - its size must be a minimum of 'osize' bytes. -*/ - - -//**************************** -// Advanced Functions -//**************************** - -static inline int LZ4_compressBound(int isize) { return ((isize) + ((isize)/255) + 16); } -#define LZ4_COMPRESSBOUND( isize) ((isize) + ((isize)/255) + 16) - -/* -LZ4_compressBound() : - Provides the maximum size that LZ4 may output in a "worst case" scenario (input data not compressible) - primarily useful for memory allocation of output buffer. - inline function is recommended for the general case, - but macro is also provided when results need to be evaluated at compile time (such as table size allocation). - - isize : is the input size. Max supported value is ~1.9GB - return : maximum output size in a "worst case" scenario - note : this function is limited by "int" range (2^31-1) -*/ - - -int LZ4_compress_limitedOutput (const char* source, char* dest, int isize, int maxOutputSize); - -/* -LZ4_compress_limitedOutput() : - Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'. - If it cannot achieve it, compression will stop, and result of the function will be zero. - This function never writes outside of provided output buffer. - - isize : is the input size. Max supported value is ~1.9GB - maxOutputSize : is the size of the destination buffer (which must be already allocated) - return : the number of bytes written in buffer 'dest' - or 0 if the compression fails -*/ - - -int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); - -/* -LZ4_uncompress_unknownOutputSize() : - isize : is the input size, therefore the compressed size - maxOutputSize : is the size of the destination buffer (which must be already allocated) - return : the number of bytes decoded in the destination buffer (necessarily <= maxOutputSize) - If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction - This function never writes beyond dest + maxOutputSize, and is therefore protected against malicious data packets - note : Destination buffer must be already allocated. - This version is slightly slower than LZ4_uncompress() -*/ - - -#if defined (__cplusplus) -} -#endif +/*+ LZ4 - Fast LZ compression algorithm+ Header File+ Copyright (C) 2011-2014, Yann Collet.+ BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++ Redistribution and use in source and binary forms, with or without+ modification, are permitted provided that the following conditions are+ met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.+ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following disclaimer+ in the documentation and/or other materials provided with the+ distribution.++ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+ OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++ You can contact the author at :+ - LZ4 source repository : http://code.google.com/p/lz4/+ - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c+*/+#pragma once++#if defined (__cplusplus)+extern "C" {+#endif+++/**************************************+ Version+**************************************/+#define LZ4_VERSION_MAJOR 1 /* for major interface/format changes */+#define LZ4_VERSION_MINOR 2 /* for minor interface/format changes */+#define LZ4_VERSION_RELEASE 0 /* for tweaks, bug-fixes, or development */+++/**************************************+ Tuning parameter+**************************************/+/*+ * LZ4_MEMORY_USAGE :+ * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)+ * Increasing memory usage improves compression ratio+ * Reduced memory usage can improve speed, due to cache effect+ * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache+ */+#define LZ4_MEMORY_USAGE 14+++/**************************************+ Simple Functions+**************************************/++int LZ4_compress (const char* source, char* dest, int inputSize);+int LZ4_decompress_safe (const char* source, char* dest, int compressedSize, int maxOutputSize);++/*+LZ4_compress() :+ Compresses 'inputSize' bytes from 'source' into 'dest'.+ Destination buffer must be already allocated,+ and must be sized to handle worst cases situations (input data not compressible)+ Worst case size evaluation is provided by function LZ4_compressBound()+ inputSize : Max supported value is LZ4_MAX_INPUT_VALUE+ return : the number of bytes written in buffer dest+ or 0 if the compression fails++LZ4_decompress_safe() :+ compressedSize : is obviously the source size+ maxOutputSize : is the size of the destination buffer, which must be already allocated.+ return : the number of bytes decoded in the destination buffer (necessarily <= maxOutputSize)+ If the destination buffer is not large enough, decoding will stop and output an error code (<0).+ If the source stream is detected malformed, the function will stop decoding and return a negative result.+ This function is protected against buffer overflow exploits :+ it never writes outside of output buffer, and never reads outside of input buffer.+ Therefore, it is protected against malicious data packets.+*/+++/*+Note :+ Should you prefer to explicitly allocate compression-table memory using your own allocation method,+ use the streaming functions provided below, simply reset the memory area between each call to LZ4_compress_continue()+*/+++/**************************************+ Advanced Functions+**************************************/+#define LZ4_MAX_INPUT_SIZE 0x7E000000 /* 2 113 929 216 bytes */+#define LZ4_COMPRESSBOUND(isize) ((unsigned int)(isize) > (unsigned int)LZ4_MAX_INPUT_SIZE ? 0 : (isize) + ((isize)/255) + 16)++/*+LZ4_compressBound() :+ Provides the maximum size that LZ4 may output in a "worst case" scenario (input data not compressible)+ primarily useful for memory allocation of output buffer.+ macro is also provided when result needs to be evaluated at compilation (such as stack memory allocation).++ isize : is the input size. Max supported value is LZ4_MAX_INPUT_SIZE+ return : maximum output size in a "worst case" scenario+ or 0, if input size is too large ( > LZ4_MAX_INPUT_SIZE)+*/+int LZ4_compressBound(int isize);+++/*+LZ4_compress_limitedOutput() :+ Compress 'inputSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.+ If it cannot achieve it, compression will stop, and result of the function will be zero.+ This function never writes outside of provided output buffer.++ inputSize : Max supported value is LZ4_MAX_INPUT_VALUE+ maxOutputSize : is the size of the destination buffer (which must be already allocated)+ return : the number of bytes written in buffer 'dest'+ or 0 if the compression fails+*/+int LZ4_compress_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize);+++/*+LZ4_decompress_fast() :+ originalSize : is the original and therefore uncompressed size+ return : the number of bytes read from the source buffer (in other words, the compressed size)+ If the source stream is malformed, the function will stop decoding and return a negative result.+ Destination buffer must be already allocated. Its size must be a minimum of 'originalSize' bytes.+ note : This function is a bit faster than LZ4_decompress_safe()+ It provides fast decompression and fully respect memory boundaries for properly formed compressed data.+ It does not provide full protection against intentionnally modified data stream.+ Use this function in a trusted environment (data to decode comes from a trusted source).+*/+int LZ4_decompress_fast (const char* source, char* dest, int originalSize);+++/*+LZ4_decompress_safe_partial() :+ This function decompress a compressed block of size 'compressedSize' at position 'source'+ into output buffer 'dest' of size 'maxOutputSize'.+ The function tries to stop decompressing operation as soon as 'targetOutputSize' has been reached,+ reducing decompression time.+ return : the number of bytes decoded in the destination buffer (necessarily <= maxOutputSize)+ Note : this number can be < 'targetOutputSize' should the compressed block to decode be smaller.+ Always control how many bytes were decoded.+ If the source stream is detected malformed, the function will stop decoding and return a negative result.+ This function never writes outside of output buffer, and never reads outside of input buffer. It is therefore protected against malicious data packets+*/+int LZ4_decompress_safe_partial (const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize);+++/***********************************************+ Experimental Streaming Compression Functions+***********************************************/++#define LZ4_STREAMSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8)+#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U32 * sizeof(unsigned int))+/*+ * LZ4_stream_t+ * information structure to track an LZ4 stream.+ * important : set this structure content to zero before first use !+ */+typedef struct { unsigned int table[LZ4_STREAMSIZE_U32]; } LZ4_stream_t;++/*+ * If you prefer dynamic allocation methods,+ * LZ4_createStream+ * provides a pointer (void*) towards an initialized LZ4_stream_t structure.+ * LZ4_free just frees it.+ */+void* LZ4_createStream();+int LZ4_free (void* LZ4_stream);+++/*+ * LZ4_loadDict+ * Use this function to load a static dictionary into LZ4_stream.+ * Any previous data will be forgotten, only 'dictionary' will remain in memory.+ * Loading a size of 0 is allowed (same effect as init).+ * Return : 1 if OK, 0 if error+ */+int LZ4_loadDict (void* LZ4_stream, const char* dictionary, int dictSize);++/*+ * LZ4_compress_continue+ * Compress data block 'source', using blocks compressed before as dictionary to improve compression ratio+ * Previous data blocks are assumed to still be present at their previous location.+ */+int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize);++/*+ * LZ4_compress_limitedOutput_continue+ * Same as before, but also specify a maximum target compressed size (maxOutputSize)+ * If objective cannot be met, compression exits, and returns a zero.+ */+int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize);++/*+ * LZ4_saveDict+ * If previously compressed data block is not guaranteed to remain at its previous memory location+ * save it into a safe place (char* safeBuffer)+ * Note : you don't need to call LZ4_loadDict() afterwards,+ * dictionary is immediately usable, you can therefore call again LZ4_compress_continue()+ * Return : 1 if OK, 0 if error+ * Note : any dictSize > 64 KB will be interpreted as 64KB.+ */+int LZ4_saveDict (void* LZ4_stream, char* safeBuffer, int dictSize);+++/************************************************+ Experimental Streaming Decompression Functions+************************************************/++#define LZ4_STREAMDECODESIZE_U32 4+#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int))+/*+ * LZ4_streamDecode_t+ * information structure to track an LZ4 stream.+ * important : set this structure content to zero before first use !+ */+typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t;++/*+ * If you prefer dynamic allocation methods,+ * LZ4_createStreamDecode()+ * provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure.+ * LZ4_free just frees it.+ */+void* LZ4_createStreamDecode();+int LZ4_free (void* LZ4_stream); /* yes, it's the same one as for compression */++/*+*_continue() :+ These decoding functions allow decompression of multiple blocks in "streaming" mode.+ Previously decoded blocks must still be available at the memory position where they were decoded.+ If it's not possible, save the relevant part of decoded data into a safe buffer,+ and indicate where it stands using LZ4_setDictDecode()+*/+int LZ4_decompress_safe_continue (void* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize);+int LZ4_decompress_fast_continue (void* LZ4_streamDecode, const char* source, char* dest, int originalSize);++/*+ * LZ4_setDictDecode+ * Use this function to instruct where to find the dictionary.+ * This function can be used to specify a static dictionary,+ * or to instruct where to find some previously decoded data saved into a different memory space.+ * Setting a size of 0 is allowed (same effect as no dictionary).+ * Return : 1 if OK, 0 if error+ */+int LZ4_setDictDecode (void* LZ4_streamDecode, const char* dictionary, int dictSize);+++/*+Advanced decoding functions :+*_usingDict() :+ These decoding functions work the same as+ a combination of LZ4_setDictDecode() followed by LZ4_decompress_x_continue()+ all together into a single function call.+ It doesn't use nor update an LZ4_streamDecode_t structure.+*/+int LZ4_decompress_safe_usingDict (const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize);+int LZ4_decompress_fast_usingDict (const char* source, char* dest, int originalSize, const char* dictStart, int dictSize);+++++/**************************************+ Obsolete Functions+**************************************/+/*+Obsolete decompression functions+These function names are deprecated and should no longer be used.+They are only provided here for compatibility with older user programs.+- LZ4_uncompress is the same as LZ4_decompress_fast+- LZ4_uncompress_unknownOutputSize is the same as LZ4_decompress_safe+*/+int LZ4_uncompress (const char* source, char* dest, int outputSize);+int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize);++/* Obsolete functions for externally allocated state; use streaming interface instead */+int LZ4_sizeofState(void);+int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize);+int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize);++/* Obsolete streaming functions; use new streaming interface whenever possible */+void* LZ4_create (const char* inputBuffer);+int LZ4_sizeofStreamState(void);+int LZ4_resetStreamState(void* state, const char* inputBuffer);+char* LZ4_slideInputBuffer (void* state);++/* Obsolete streaming decoding functions */+int LZ4_decompress_safe_withPrefix64k (const char* source, char* dest, int compressedSize, int maxOutputSize);+int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int originalSize);+++#if defined (__cplusplus)+}+#endif
src/cbits/lz4hc.c view
@@ -1,719 +1,892 @@-/* - LZ4 HC - High Compression Mode of LZ4 - Copyright (C) 2011-2012, Yann Collet. - BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following disclaimer - in the documentation and/or other materials provided with the - distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - You can contact the author at : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ -*/ - - -//************************************** -// CPU Feature Detection -//************************************** -// 32 or 64 bits ? -#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) ) // Detects 64 bits mode -# define LZ4_ARCH64 1 -#else -# define LZ4_ARCH64 0 -#endif - -// Little Endian or Big Endian ? -// Overwrite the #define below if you know your architecture endianess -#if defined (__GLIBC__) -# include <endian.h> -# if (__BYTE_ORDER == __BIG_ENDIAN) -# define LZ4_BIG_ENDIAN 1 -# endif -#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN)) -# define LZ4_BIG_ENDIAN 1 -#elif defined(__sparc) || defined(__sparc__) \ - || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \ - || defined(__hpux) || defined(__hppa) \ - || defined(_MIPSEB) || defined(__s390__) -# define LZ4_BIG_ENDIAN 1 -#else -// Little Endian assumed. PDP Endian and other very rare endian format are unsupported. -#endif - -// Unaligned memory access is automatically enabled for "common" CPU, such as x86. -// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected -// If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance -#if defined(__ARM_FEATURE_UNALIGNED) -# define LZ4_FORCE_UNALIGNED_ACCESS 1 -#endif - -// Define this parameter if your target system or compiler does not support hardware bit count -#if defined(_MSC_VER) && defined(_WIN32_WCE) // Visual Studio for Windows CE does not support Hardware bit count -# define LZ4_FORCE_SW_BITCOUNT -#endif - - -//************************************** -// Compiler Options -//************************************** -#if __STDC_VERSION__ >= 199901L // C99 - /* "restrict" is a known keyword */ -#else -# define restrict // Disable restrict -#endif - -#ifdef _MSC_VER -# define inline __inline // Visual is not C99, but supports some kind of inline -# define forceinline __forceinline -# include <intrin.h> // For Visual 2005 -# if LZ4_ARCH64 // 64-bit -# pragma intrinsic(_BitScanForward64) // For Visual 2005 -# pragma intrinsic(_BitScanReverse64) // For Visual 2005 -# else -# pragma intrinsic(_BitScanForward) // For Visual 2005 -# pragma intrinsic(_BitScanReverse) // For Visual 2005 -# endif -#else -# ifdef __GNUC__ -# define forceinline inline __attribute__((always_inline)) -# else -# define forceinline inline -# endif -#endif - -#ifdef _MSC_VER // Visual Studio -#define lz4_bswap16(x) _byteswap_ushort(x) -#else -#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8))) -#endif - - -//************************************** -// Includes -//************************************** -#include <stdlib.h> // calloc, free -#include <string.h> // memset, memcpy -#include "lz4hc.h" - -#define ALLOCATOR(s) calloc(1,s) -#define FREEMEM free -#define MEM_INIT memset - - -//************************************** -// Basic Types -//************************************** -#if defined(_MSC_VER) // Visual Studio does not support 'stdint' natively -#define BYTE unsigned __int8 -#define U16 unsigned __int16 -#define U32 unsigned __int32 -#define S32 __int32 -#define U64 unsigned __int64 -#else -#include <stdint.h> -#define BYTE uint8_t -#define U16 uint16_t -#define U32 uint32_t -#define S32 int32_t -#define U64 uint64_t -#endif - -#ifndef LZ4_FORCE_UNALIGNED_ACCESS -#pragma pack(push, 1) -#endif - -typedef struct _U16_S { U16 v; } U16_S; -typedef struct _U32_S { U32 v; } U32_S; -typedef struct _U64_S { U64 v; } U64_S; - -#ifndef LZ4_FORCE_UNALIGNED_ACCESS -#pragma pack(pop) -#endif - -#define A64(x) (((U64_S *)(x))->v) -#define A32(x) (((U32_S *)(x))->v) -#define A16(x) (((U16_S *)(x))->v) - - -//************************************** -// Constants -//************************************** -#define MINMATCH 4 - -#define DICTIONARY_LOGSIZE 16 -#define MAXD (1<<DICTIONARY_LOGSIZE) -#define MAXD_MASK ((U32)(MAXD - 1)) -#define MAX_DISTANCE (MAXD - 1) - -#define HASH_LOG (DICTIONARY_LOGSIZE-1) -#define HASHTABLESIZE (1 << HASH_LOG) -#define HASH_MASK (HASHTABLESIZE - 1) - -#define MAX_NB_ATTEMPTS 256 - -#define ML_BITS 4 -#define ML_MASK (size_t)((1U<<ML_BITS)-1) -#define RUN_BITS (8-ML_BITS) -#define RUN_MASK ((1U<<RUN_BITS)-1) - -#define COPYLENGTH 8 -#define LASTLITERALS 5 -#define MFLIMIT (COPYLENGTH+MINMATCH) -#define MINLENGTH (MFLIMIT+1) -#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) - - -//************************************** -// Architecture-specific macros -//************************************** -#if LZ4_ARCH64 // 64-bit -#define STEPSIZE 8 -#define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; -#define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) -#define UARCH U64 -#define AARCH A64 -#define HTYPE U32 -#define INITBASE(b,s) const BYTE* const b = s -#else // 32-bit -#define STEPSIZE 4 -#define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4; -#define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d); -#define UARCH U32 -#define AARCH A32 -#define HTYPE const BYTE* -#define INITBASE(b,s) const int b = 0 -#endif - -#if defined(LZ4_BIG_ENDIAN) -#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } -#define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; } -#else // Little Endian -#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } -#define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } -#endif - - -//************************************************************ -// Local Types -//************************************************************ -typedef struct -{ - const BYTE* base; - HTYPE hashTable[HASHTABLESIZE]; - U16 chainTable[MAXD]; - const BYTE* nextToUpdate; -} LZ4HC_Data_Structure; - - -//************************************** -// Macros -//************************************** -#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e); -#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; } -#define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG)) -#define HASH_VALUE(p) HASH_FUNCTION(A32(p)) -#define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base) -#define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK] -#define GETNEXT(p) ((p) - (size_t)DELTANEXT(p)) - - -//************************************** -// Private functions -//************************************** -#if LZ4_ARCH64 - -inline static int LZ4_NbCommonBytes (register U64 val) -{ -#if defined(LZ4_BIG_ENDIAN) - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanReverse64( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clzll(val) >> 3); - #else - int r; - if (!(val>>32)) { r=4; } else { r=0; val>>=32; } - if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } - r += (!val); - return r; - #endif -#else - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanForward64( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctzll(val) >> 3); - #else - 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 }; - return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58]; - #endif -#endif -} - -#else - -inline static int LZ4_NbCommonBytes (register U32 val) -{ -#if defined(LZ4_BIG_ENDIAN) - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r; - _BitScanReverse( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clz(val) >> 3); - #else - int r; - if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } - r += (!val); - return r; - #endif -#else - #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r; - _BitScanForward( &r, val ); - return (int)(r>>3); - #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctz(val) >> 3); - #else - 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 }; - return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; - #endif -#endif -} - -#endif - - -inline static int LZ4HC_Init (LZ4HC_Data_Structure* hc4, const BYTE* base) -{ - MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); - MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); - hc4->nextToUpdate = base + LZ4_ARCH64; - hc4->base = base; - return 1; -} - - -inline static void* LZ4HC_Create (const BYTE* base) -{ - void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure)); - - LZ4HC_Init ((LZ4HC_Data_Structure*)hc4, base); - return hc4; -} - - -inline static int LZ4HC_Free (void** LZ4HC_Data) -{ - FREEMEM(*LZ4HC_Data); - *LZ4HC_Data = NULL; - return (1); -} - - -// Update chains up to ip (excluded) -forceinline static void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) -{ - U16* chainTable = hc4->chainTable; - HTYPE* HashTable = hc4->hashTable; - INITBASE(base,hc4->base); - - while(hc4->nextToUpdate < ip) - { - const BYTE* p = hc4->nextToUpdate; - size_t delta = (p) - HASH_POINTER(p); - if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; - DELTANEXT(p) = (U16)delta; - HashTable[HASH_VALUE(p)] = (p) - base; - hc4->nextToUpdate++; - } -} - - -forceinline static size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit) -{ - const BYTE* p1t = p1; - - while (p1t<matchlimit-(STEPSIZE-1)) - { - UARCH diff = AARCH(p2) ^ AARCH(p1t); - if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; } - p1t += LZ4_NbCommonBytes(diff); - return (p1t - p1); - } - if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; } - if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; } - if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++; - return (p1t - p1); -} - - -forceinline static int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos) -{ - U16* const chainTable = hc4->chainTable; - HTYPE* const HashTable = hc4->hashTable; - const BYTE* ref; - INITBASE(base,hc4->base); - int nbAttempts=MAX_NB_ATTEMPTS; - size_t ml=0; - - // HC4 match finder - LZ4HC_Insert(hc4, ip); - ref = HASH_POINTER(ip); - -#if 1 - if (ref >= ip-4) // potential repetition - { - if (A32(ref) == A32(ip)) // confirmed - { - const U16 delta = (U16)(ip-ref); - const BYTE* ptr = ip; - const BYTE* end; - ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; - end = ip + ml - (MINMATCH-1); - while(ptr < end-delta) - { - DELTANEXT(ptr) = delta; // Pre-Load - ptr++; - } - do - { - DELTANEXT(ptr) = delta; - HashTable[HASH_VALUE(ptr)] = (ptr) - base; // Head of chain - ptr++; - } while(ptr < end); - hc4->nextToUpdate = end; - *matchpos = ref; - } - ref = GETNEXT(ref); - } -#endif - - while ((ref >= ip-MAX_DISTANCE) && (ref >= hc4->base) && (nbAttempts)) - { - nbAttempts--; - if (*(ref+ml) == *(ip+ml)) - if (A32(ref) == A32(ip)) - { - size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; - if (mlt > ml) { ml = mlt; *matchpos = ref; } - } - ref = GETNEXT(ref); - } - - return (int)ml; -} - - -forceinline 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) -{ - U16* const chainTable = hc4->chainTable; - HTYPE* const HashTable = hc4->hashTable; - INITBASE(base,hc4->base); - const BYTE* ref; - int nbAttempts = MAX_NB_ATTEMPTS; - int delta = (int)(ip-startLimit); - - // First Match - LZ4HC_Insert(hc4, ip); - ref = HASH_POINTER(ip); - - while ((ref >= ip-MAX_DISTANCE) && (ref >= hc4->base) && (nbAttempts)) - { - nbAttempts--; - if (*(startLimit + longest) == *(ref - delta + longest)) - if (A32(ref) == A32(ip)) - { -#if 1 - const BYTE* reft = ref+MINMATCH; - const BYTE* ipt = ip+MINMATCH; - const BYTE* startt = ip; - - while (ipt<matchlimit-(STEPSIZE-1)) - { - UARCH diff = AARCH(reft) ^ AARCH(ipt); - if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; } - ipt += LZ4_NbCommonBytes(diff); - goto _endCount; - } - if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; } - if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; } - if ((ipt<matchlimit) && (*reft == *ipt)) ipt++; -_endCount: - reft = ref; -#else - // Easier for code maintenance, but unfortunately slower too - const BYTE* startt = ip; - const BYTE* reft = ref; - const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit); -#endif - - while ((startt>startLimit) && (reft > hc4->base) && (startt[-1] == reft[-1])) {startt--; reft--;} - - if ((ipt-startt) > longest) - { - longest = (int)(ipt-startt); - *matchpos = reft; - *startpos = startt; - } - } - ref = GETNEXT(ref); - } - - return longest; -} - - -forceinline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE** anchor, int ml, const BYTE* ref) -{ - int length, len; - BYTE* token; - - // Encode Literal length - length = (int)(*ip - *anchor); - token = (*op)++; - if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; } - else *token = (length<<ML_BITS); - - // Copy Literals - LZ4_BLINDCOPY(*anchor, *op, length); - - // Encode Offset - LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref)); - - // Encode MatchLength - len = (int)(ml-MINMATCH); - 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; } - else *token += len; - - // Prepare next loop - *ip += ml; - *anchor = *ip; - - return 0; -} - - -//**************************** -// Compression CODE -//**************************** - -int LZ4_compressHCCtx(LZ4HC_Data_Structure* ctx, - const char* source, - char* dest, - int isize) -{ - const BYTE* ip = (const BYTE*) source; - const BYTE* anchor = ip; - const BYTE* const iend = ip + isize; - const BYTE* const mflimit = iend - MFLIMIT; - const BYTE* const matchlimit = (iend - LASTLITERALS); - - BYTE* op = (BYTE*) dest; - - int ml, ml2, ml3, ml0; - const BYTE* ref=NULL; - const BYTE* start2=NULL; - const BYTE* ref2=NULL; - const BYTE* start3=NULL; - const BYTE* ref3=NULL; - const BYTE* start0; - const BYTE* ref0; - - ip++; - - // Main Loop - while (ip < mflimit) - { - ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref)); - if (!ml) { ip++; continue; } - - // saved, in case we would skip too much - start0 = ip; - ref0 = ref; - ml0 = ml; - -_Search2: - if (ip+ml < mflimit) - ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2); - else ml2 = ml; - - if (ml2 == ml) // No better match - { - LZ4_encodeSequence(&ip, &op, &anchor, ml, ref); - continue; - } - - if (start0 < ip) - { - if (start2 < ip + ml0) // empirical - { - ip = start0; - ref = ref0; - ml = ml0; - } - } - - // Here, start0==ip - if ((start2 - ip) < 3) // First Match too small : removed - { - ml = ml2; - ip = start2; - ref =ref2; - goto _Search2; - } - -_Search3: - // Currently we have : - // ml2 > ml1, and - // ip1+3 <= ip2 (usually < ip1+ml1) - if ((start2 - ip) < OPTIMAL_ML) - { - int correction; - int new_ml = ml; - if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML; - if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH; - correction = new_ml - (int)(start2 - ip); - if (correction > 0) - { - start2 += correction; - ref2 += correction; - ml2 -= correction; - } - } - // Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) - - if (start2 + ml2 < mflimit) - ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3); - else ml3 = ml2; - - if (ml3 == ml2) // No better match : 2 sequences to encode - { - // ip & ref are known; Now for ml - if (start2 < ip+ml) ml = (int)(start2 - ip); - // Now, encode 2 sequences - LZ4_encodeSequence(&ip, &op, &anchor, ml, ref); - ip = start2; - LZ4_encodeSequence(&ip, &op, &anchor, ml2, ref2); - continue; - } - - if (start3 < ip+ml+3) // Not enough space for match 2 : remove it - { - if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 - { - if (start2 < ip+ml) - { - int correction = (int)(ip+ml - start2); - start2 += correction; - ref2 += correction; - ml2 -= correction; - if (ml2 < MINMATCH) - { - start2 = start3; - ref2 = ref3; - ml2 = ml3; - } - } - - LZ4_encodeSequence(&ip, &op, &anchor, ml, ref); - ip = start3; - ref = ref3; - ml = ml3; - - start0 = start2; - ref0 = ref2; - ml0 = ml2; - goto _Search2; - } - - start2 = start3; - ref2 = ref3; - ml2 = ml3; - goto _Search3; - } - - // OK, now we have 3 ascending matches; let's write at least the first one - // ip & ref are known; Now for ml - if (start2 < ip+ml) - { - if ((start2 - ip) < (int)ML_MASK) - { - int correction; - if (ml > OPTIMAL_ML) ml = OPTIMAL_ML; - if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH; - correction = ml - (int)(start2 - ip); - if (correction > 0) - { - start2 += correction; - ref2 += correction; - ml2 -= correction; - } - } - else - { - ml = (int)(start2 - ip); - } - } - LZ4_encodeSequence(&ip, &op, &anchor, ml, ref); - - ip = start2; - ref = ref2; - ml = ml2; - - start2 = start3; - ref2 = ref3; - ml2 = ml3; - - goto _Search3; - - } - - // Encode Last Literals - { - int lastRun = (int)(iend - anchor); - if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } - else *op++ = (lastRun<<ML_BITS); - memcpy(op, anchor, iend - anchor); - op += iend-anchor; - } - - // End - return (int) (((char*)op)-dest); -} - - -int LZ4_compressHC(const char* source, - char* dest, - int isize) -{ - void* ctx = LZ4HC_Create((const BYTE*)source); - int result = LZ4_compressHCCtx(ctx, source, dest, isize); - LZ4HC_Free (&ctx); - - return result; -} - - +/*+ LZ4 HC - High Compression Mode of LZ4+ Copyright (C) 2011-2014, Yann Collet.+ BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++ Redistribution and use in source and binary forms, with or without+ modification, are permitted provided that the following conditions are+ met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.+ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following disclaimer+ in the documentation and/or other materials provided with the+ distribution.++ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+ OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++ You can contact the author at :+ - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+ - LZ4 source repository : http://code.google.com/p/lz4/+*/++++/**************************************+ Tuning Parameter+**************************************/+#define LZ4HC_DEFAULT_COMPRESSIONLEVEL 8+++/**************************************+ Memory routines+**************************************/+#include <stdlib.h> /* calloc, free */+#define ALLOCATOR(s) calloc(1,s)+#define FREEMEM free+#include <string.h> /* memset, memcpy */+#define MEM_INIT memset+++/**************************************+ CPU Feature Detection+**************************************/+/* 32 or 64 bits ? */+#if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \+ || defined(__powerpc64__) || defined(__powerpc64le__) \+ || defined(__ppc64__) || defined(__ppc64le__) \+ || defined(__PPC64__) || defined(__PPC64LE__) \+ || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) /* Detects 64 bits mode */+# define LZ4_ARCH64 1+#else+# define LZ4_ARCH64 0+#endif++/*+ * Little Endian or Big Endian ?+ * Overwrite the #define below if you know your architecture endianess+ */+#include <stdlib.h> /* Apparently required to detect endianess */+#if defined (__GLIBC__)+# include <endian.h>+# if (__BYTE_ORDER == __BIG_ENDIAN)+# define LZ4_BIG_ENDIAN 1+# endif+#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))+# define LZ4_BIG_ENDIAN 1+#elif defined(__sparc) || defined(__sparc__) \+ || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \+ || defined(__hpux) || defined(__hppa) \+ || defined(_MIPSEB) || defined(__s390__)+# define LZ4_BIG_ENDIAN 1+#else+/* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */+#endif++/*+ * Unaligned memory access is automatically enabled for "common" CPU, such as x86.+ * For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected+ * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance+ */+#if defined(__ARM_FEATURE_UNALIGNED)+# define LZ4_FORCE_UNALIGNED_ACCESS 1+#endif++/* Define this parameter if your target system or compiler does not support hardware bit count */+#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */+# define LZ4_FORCE_SW_BITCOUNT+#endif+++/**************************************+ Compiler Options+**************************************/+#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */+/* "restrict" is a known keyword */+#else+# define restrict /* Disable restrict */+#endif++#ifdef _MSC_VER /* Visual Studio */+# define FORCE_INLINE static __forceinline+# include <intrin.h> /* For Visual 2005 */+# if LZ4_ARCH64 /* 64-bits */+# pragma intrinsic(_BitScanForward64) /* For Visual 2005 */+# pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */+# else /* 32-bits */+# pragma intrinsic(_BitScanForward) /* For Visual 2005 */+# pragma intrinsic(_BitScanReverse) /* For Visual 2005 */+# endif+# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */+# pragma warning(disable : 4701) /* disable: C4701: potentially uninitialized local variable used */+#else+# ifdef __GNUC__+# define FORCE_INLINE static inline __attribute__((always_inline))+# else+# define FORCE_INLINE static inline+# endif+#endif++#ifdef _MSC_VER /* Visual Studio */+# define lz4_bswap16(x) _byteswap_ushort(x)+#else+# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))+#endif+++/**************************************+ Includes+**************************************/+#include "lz4hc.h"+#include "lz4.h"+++/**************************************+ Basic Types+**************************************/+#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */+# include <stdint.h>+ typedef uint8_t BYTE;+ typedef uint16_t U16;+ typedef uint32_t U32;+ typedef int32_t S32;+ typedef uint64_t U64;+#else+ typedef unsigned char BYTE;+ typedef unsigned short U16;+ typedef unsigned int U32;+ typedef signed int S32;+ typedef unsigned long long U64;+#endif++#if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS)+# define _PACKED __attribute__ ((packed))+#else+# define _PACKED+#endif++#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)+# ifdef __IBMC__+# pragma pack(1)+# else+# pragma pack(push, 1)+# endif+#endif++typedef struct _U16_S { U16 v; } _PACKED U16_S;+typedef struct _U32_S { U32 v; } _PACKED U32_S;+typedef struct _U64_S { U64 v; } _PACKED U64_S;++#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)+# pragma pack(pop)+#endif++#define A64(x) (((U64_S *)(x))->v)+#define A32(x) (((U32_S *)(x))->v)+#define A16(x) (((U16_S *)(x))->v)+++/**************************************+ Constants+**************************************/+#define MINMATCH 4++#define DICTIONARY_LOGSIZE 16+#define MAXD (1<<DICTIONARY_LOGSIZE)+#define MAXD_MASK ((U32)(MAXD - 1))+#define MAX_DISTANCE (MAXD - 1)++#define HASH_LOG (DICTIONARY_LOGSIZE-1)+#define HASHTABLESIZE (1 << HASH_LOG)+#define HASH_MASK (HASHTABLESIZE - 1)++#define ML_BITS 4+#define ML_MASK (size_t)((1U<<ML_BITS)-1)+#define RUN_BITS (8-ML_BITS)+#define RUN_MASK ((1U<<RUN_BITS)-1)++#define COPYLENGTH 8+#define LASTLITERALS 5+#define MFLIMIT (COPYLENGTH+MINMATCH)+#define MINLENGTH (MFLIMIT+1)+#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)++#define KB *(1U<<10)+#define MB *(1U<<20)+#define GB *(1U<<30)+++/**************************************+ Architecture-specific macros+**************************************/+#if LZ4_ARCH64 /* 64-bit */+# define STEPSIZE 8+# define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8;+# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d)+# define AARCH A64+# define HTYPE U32+# define INITBASE(b,s) const BYTE* const b = s+#else /* 32-bit */+# define STEPSIZE 4+# define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4;+# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);+# define AARCH A32+# define HTYPE U32+# define INITBASE(b,s) const BYTE* const b = s+#endif++#if defined(LZ4_BIG_ENDIAN)+# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }+# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }+#else /* Little Endian */+# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }+# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }+#endif+++/**************************************+ Local Types+**************************************/+typedef struct+{+ const BYTE* inputBuffer;+ const BYTE* base;+ const BYTE* end;+ HTYPE hashTable[HASHTABLESIZE];+ U16 chainTable[MAXD];+ const BYTE* nextToUpdate;+} LZ4HC_Data_Structure;+++/**************************************+ Macros+**************************************/+#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);+#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }+#define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))+#define HASH_VALUE(p) HASH_FUNCTION(A32(p))+#define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base)+#define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK]+#define GETNEXT(p) ((p) - (size_t)DELTANEXT(p))+++/**************************************+ Private functions+**************************************/+#if LZ4_ARCH64++FORCE_INLINE int LZ4_NbCommonBytes (register U64 val)+{+#if defined(LZ4_BIG_ENDIAN)+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r = 0;+ _BitScanReverse64( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_clzll(val) >> 3);+# else+ int r;+ if (!(val>>32)) { r=4; } else { r=0; val>>=32; }+ if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }+ r += (!val);+ return r;+# endif+#else+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r = 0;+ _BitScanForward64( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_ctzll(val) >> 3);+# else+ 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 };+ return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];+# endif+#endif+}++#else++FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)+{+#if defined(LZ4_BIG_ENDIAN)+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r;+ _BitScanReverse( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_clz(val) >> 3);+# else+ int r;+ if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }+ r += (!val);+ return r;+# endif+#else+# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+ unsigned long r;+ _BitScanForward( &r, val );+ return (int)(r>>3);+# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+ return (__builtin_ctz(val) >> 3);+# else+ 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 };+ return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];+# endif+#endif+}++#endif+++int LZ4_sizeofStreamStateHC()+{+ return sizeof(LZ4HC_Data_Structure);+}++FORCE_INLINE void LZ4_initHC (LZ4HC_Data_Structure* hc4, const BYTE* base)+{+ MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));+ MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));+ hc4->nextToUpdate = base + 1;+ hc4->base = base;+ hc4->inputBuffer = base;+ hc4->end = base;+}++int LZ4_resetStreamStateHC(void* state, const char* inputBuffer)+{+ if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */+ LZ4_initHC((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer);+ return 0;+}+++void* LZ4_createHC (const char* inputBuffer)+{+ void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));+ LZ4_initHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer);+ return hc4;+}+++int LZ4_freeHC (void* LZ4HC_Data)+{+ FREEMEM(LZ4HC_Data);+ return (0);+}+++/* Update chains up to ip (excluded) */+FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)+{+ U16* chainTable = hc4->chainTable;+ HTYPE* HashTable = hc4->hashTable;+ INITBASE(base,hc4->base);++ while(hc4->nextToUpdate < ip)+ {+ const BYTE* const p = hc4->nextToUpdate;+ size_t delta = (p) - HASH_POINTER(p);+ if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;+ DELTANEXT(p) = (U16)delta;+ HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base);+ hc4->nextToUpdate++;+ }+}+++char* LZ4_slideInputBufferHC(void* LZ4HC_Data)+{+ LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data;+ U32 distance = (U32)(hc4->end - hc4->inputBuffer) - 64 KB;+ distance = (distance >> 16) << 16; /* Must be a multiple of 64 KB */+ LZ4HC_Insert(hc4, hc4->end - MINMATCH);+ memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB);+ hc4->nextToUpdate -= distance;+ hc4->base -= distance;+ if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB) /* Avoid overflow */+ {+ int i;+ hc4->base += 1 GB;+ for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB;+ }+ hc4->end -= distance;+ return (char*)(hc4->end);+}+++FORCE_INLINE size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit)+{+ const BYTE* p1t = p1;++ while (p1t<matchlimit-(STEPSIZE-1))+ {+ size_t diff = AARCH(p2) ^ AARCH(p1t);+ if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; }+ p1t += LZ4_NbCommonBytes(diff);+ return (p1t - p1);+ }+ if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; }+ if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; }+ if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++;+ return (p1t - p1);+}+++FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos, const int maxNbAttempts)+{+ U16* const chainTable = hc4->chainTable;+ HTYPE* const HashTable = hc4->hashTable;+ const BYTE* ref;+ INITBASE(base,hc4->base);+ int nbAttempts=maxNbAttempts;+ size_t repl=0, ml=0;+ U16 delta=0; /* useless assignment, to remove an uninitialization warning */++ /* HC4 match finder */+ LZ4HC_Insert(hc4, ip);+ ref = HASH_POINTER(ip);++#define REPEAT_OPTIMIZATION+#ifdef REPEAT_OPTIMIZATION+ /* Detect repetitive sequences of length <= 4 */+ if ((U32)(ip-ref) <= 4) /* potential repetition */+ {+ if (A32(ref) == A32(ip)) /* confirmed */+ {+ delta = (U16)(ip-ref);+ repl = ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;+ *matchpos = ref;+ }+ ref = GETNEXT(ref);+ }+#endif++ while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))+ {+ nbAttempts--;+ if (*(ref+ml) == *(ip+ml))+ if (A32(ref) == A32(ip))+ {+ size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;+ if (mlt > ml) { ml = mlt; *matchpos = ref; }+ }+ ref = GETNEXT(ref);+ }++#ifdef REPEAT_OPTIMIZATION+ /* Complete table */+ if (repl)+ {+ const BYTE* ptr = ip;+ const BYTE* end;++ end = ip + repl - (MINMATCH-1);+ while(ptr < end-delta)+ {+ DELTANEXT(ptr) = delta; /* Pre-Load */+ ptr++;+ }+ do+ {+ DELTANEXT(ptr) = delta;+ HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); /* Head of chain */+ ptr++;+ } while(ptr < end);+ hc4->nextToUpdate = end;+ }+#endif++ return (int)ml;+}+++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)+{+ U16* const chainTable = hc4->chainTable;+ HTYPE* const HashTable = hc4->hashTable;+ INITBASE(base,hc4->base);+ const BYTE* ref;+ int nbAttempts = maxNbAttempts;+ int delta = (int)(ip-startLimit);++ /* First Match */+ LZ4HC_Insert(hc4, ip);+ ref = HASH_POINTER(ip);++ while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))+ {+ nbAttempts--;+ if (*(startLimit + longest) == *(ref - delta + longest))+ if (A32(ref) == A32(ip))+ {+#if 1+ const BYTE* reft = ref+MINMATCH;+ const BYTE* ipt = ip+MINMATCH;+ const BYTE* startt = ip;++ while (ipt<matchlimit-(STEPSIZE-1))+ {+ size_t diff = AARCH(reft) ^ AARCH(ipt);+ if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }+ ipt += LZ4_NbCommonBytes(diff);+ goto _endCount;+ }+ if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }+ if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }+ if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;+_endCount:+ reft = ref;+#else+ /* Easier for code maintenance, but unfortunately slower too */+ const BYTE* startt = ip;+ const BYTE* reft = ref;+ const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit);+#endif++ while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;}++ if ((ipt-startt) > longest)+ {+ longest = (int)(ipt-startt);+ *matchpos = reft;+ *startpos = startt;+ }+ }+ ref = GETNEXT(ref);+ }++ return longest;+}+++typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive;++FORCE_INLINE int LZ4HC_encodeSequence (+ const BYTE** ip,+ BYTE** op,+ const BYTE** anchor,+ int matchLength,+ const BYTE* ref,+ limitedOutput_directive limitedOutputBuffer,+ BYTE* oend)+{+ int length;+ BYTE* token;++ /* Encode Literal length */+ length = (int)(*ip - *anchor);+ token = (*op)++;+ if ((limitedOutputBuffer) && ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > oend)) return 1; /* Check output limit */+ 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; }+ else *token = (BYTE)(length<<ML_BITS);++ /* Copy Literals */+ LZ4_BLINDCOPY(*anchor, *op, length);++ /* Encode Offset */+ LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));++ /* Encode MatchLength */+ length = (int)(matchLength-MINMATCH);+ if ((limitedOutputBuffer) && (*op + (1 + LASTLITERALS) + (length>>8) > oend)) return 1; /* Check output limit */+ 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; }+ else *token += (BYTE)(length);++ /* Prepare next loop */+ *ip += matchLength;+ *anchor = *ip;++ return 0;+}+++#define MAX_COMPRESSION_LEVEL 16+static int LZ4HC_compress_generic (+ void* ctxvoid,+ const char* source,+ char* dest,+ int inputSize,+ int maxOutputSize,+ int compressionLevel,+ limitedOutput_directive limit+ )+{+ LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid;+ const BYTE* ip = (const BYTE*) source;+ const BYTE* anchor = ip;+ const BYTE* const iend = ip + inputSize;+ const BYTE* const mflimit = iend - MFLIMIT;+ const BYTE* const matchlimit = (iend - LASTLITERALS);++ BYTE* op = (BYTE*) dest;+ BYTE* const oend = op + maxOutputSize;++ const int maxNbAttempts = compressionLevel > MAX_COMPRESSION_LEVEL ? 1 << MAX_COMPRESSION_LEVEL : compressionLevel ? 1<<(compressionLevel-1) : 1<<LZ4HC_DEFAULT_COMPRESSIONLEVEL;+ int ml, ml2, ml3, ml0;+ const BYTE* ref=NULL;+ const BYTE* start2=NULL;+ const BYTE* ref2=NULL;+ const BYTE* start3=NULL;+ const BYTE* ref3=NULL;+ const BYTE* start0;+ const BYTE* ref0;+++ /* Ensure blocks follow each other */+ if (ip != ctx->end) return 0;+ ctx->end += inputSize;++ ip++;++ /* Main Loop */+ while (ip < mflimit)+ {+ ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref), maxNbAttempts);+ if (!ml) { ip++; continue; }++ /* saved, in case we would skip too much */+ start0 = ip;+ ref0 = ref;+ ml0 = ml;++_Search2:+ if (ip+ml < mflimit)+ ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2, maxNbAttempts);+ else ml2 = ml;++ if (ml2 == ml) /* No better match */+ {+ if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;+ continue;+ }++ if (start0 < ip)+ {+ if (start2 < ip + ml0) /* empirical */+ {+ ip = start0;+ ref = ref0;+ ml = ml0;+ }+ }++ /* Here, start0==ip */+ if ((start2 - ip) < 3) /* First Match too small : removed */+ {+ ml = ml2;+ ip = start2;+ ref =ref2;+ goto _Search2;+ }++_Search3:+ /*+ * Currently we have :+ * ml2 > ml1, and+ * ip1+3 <= ip2 (usually < ip1+ml1)+ */+ if ((start2 - ip) < OPTIMAL_ML)+ {+ int correction;+ int new_ml = ml;+ if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;+ if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;+ correction = new_ml - (int)(start2 - ip);+ if (correction > 0)+ {+ start2 += correction;+ ref2 += correction;+ ml2 -= correction;+ }+ }+ /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */++ if (start2 + ml2 < mflimit)+ ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts);+ else ml3 = ml2;++ if (ml3 == ml2) /* No better match : 2 sequences to encode */+ {+ /* ip & ref are known; Now for ml */+ if (start2 < ip+ml) ml = (int)(start2 - ip);+ /* Now, encode 2 sequences */+ if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;+ ip = start2;+ if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;+ continue;+ }++ if (start3 < ip+ml+3) /* Not enough space for match 2 : remove it */+ {+ if (start3 >= (ip+ml)) /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */+ {+ if (start2 < ip+ml)+ {+ int correction = (int)(ip+ml - start2);+ start2 += correction;+ ref2 += correction;+ ml2 -= correction;+ if (ml2 < MINMATCH)+ {+ start2 = start3;+ ref2 = ref3;+ ml2 = ml3;+ }+ }++ if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;+ ip = start3;+ ref = ref3;+ ml = ml3;++ start0 = start2;+ ref0 = ref2;+ ml0 = ml2;+ goto _Search2;+ }++ start2 = start3;+ ref2 = ref3;+ ml2 = ml3;+ goto _Search3;+ }++ /*+ * OK, now we have 3 ascending matches; let's write at least the first one+ * ip & ref are known; Now for ml+ */+ if (start2 < ip+ml)+ {+ if ((start2 - ip) < (int)ML_MASK)+ {+ int correction;+ if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;+ if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;+ correction = ml - (int)(start2 - ip);+ if (correction > 0)+ {+ start2 += correction;+ ref2 += correction;+ ml2 -= correction;+ }+ }+ else+ {+ ml = (int)(start2 - ip);+ }+ }+ if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;++ ip = start2;+ ref = ref2;+ ml = ml2;++ start2 = start3;+ ref2 = ref3;+ ml2 = ml3;++ goto _Search3;++ }++ /* Encode Last Literals */+ {+ int lastRun = (int)(iend - anchor);+ if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */+ if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }+ else *op++ = (BYTE)(lastRun<<ML_BITS);+ memcpy(op, anchor, iend - anchor);+ op += iend-anchor;+ }++ /* End */+ return (int) (((char*)op)-dest);+}+++int LZ4_compressHC2(const char* source, char* dest, int inputSize, int compressionLevel)+{+ void* ctx = LZ4_createHC(source);+ int result;+ if (ctx==NULL) return 0;++ result = LZ4HC_compress_generic (ctx, source, dest, inputSize, 0, compressionLevel, noLimit);++ LZ4_freeHC(ctx);+ return result;+}++int LZ4_compressHC(const char* source, char* dest, int inputSize) { return LZ4_compressHC2(source, dest, inputSize, 0); }++int LZ4_compressHC2_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)+{+ void* ctx = LZ4_createHC(source);+ int result;+ if (ctx==NULL) return 0;++ result = LZ4HC_compress_generic (ctx, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);++ LZ4_freeHC(ctx);+ return result;+}++int LZ4_compressHC_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)+{+ return LZ4_compressHC2_limitedOutput(source, dest, inputSize, maxOutputSize, 0);+}+++/*****************************+ Using external allocation+*****************************/+int LZ4_sizeofStateHC() { return sizeof(LZ4HC_Data_Structure); }+++int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel)+{+ if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */+ LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);+ return LZ4HC_compress_generic (state, source, dest, inputSize, 0, compressionLevel, noLimit);+}++int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize)+{ return LZ4_compressHC2_withStateHC (state, source, dest, inputSize, 0); }+++int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)+{+ if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */+ LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);+ return LZ4HC_compress_generic (state, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);+}++int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize)+{ return LZ4_compressHC2_limitedOutput_withStateHC (state, source, dest, inputSize, maxOutputSize, 0); }+++/****************************+ Stream functions+****************************/++int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize)+{+ return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, 0, noLimit);+}++int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel)+{+ return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, compressionLevel, noLimit);+}++int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize)+{+ return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, 0, limitedOutput);+}++int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)+{+ return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);+}
src/cbits/lz4hc.h view
@@ -1,60 +1,173 @@-/* - LZ4 HC - High Compression Mode of LZ4 - Header File - Copyright (C) 2011-2012, Yann Collet. - BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following disclaimer - in the documentation and/or other materials provided with the - distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - You can contact the author at : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ -*/ -#pragma once - - -#if defined (__cplusplus) -extern "C" { -#endif - - -int LZ4_compressHC (const char* source, char* dest, int isize); - -/* -LZ4_compressHC : - return : the number of bytes in compressed buffer dest - note : destination buffer must be already allocated. - To avoid any problem, size it to handle worst cases situations (input data not compressible) - Worst case size evaluation is provided by function LZ4_compressBound() (see "lz4.h") -*/ - - -/* Note : -Decompression functions are provided within regular LZ4 source code (see "lz4.h") (BSD license) -*/ - - -#if defined (__cplusplus) -} -#endif +/*+ LZ4 HC - High Compression Mode of LZ4+ Header File+ Copyright (C) 2011-2014, Yann Collet.+ BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++ Redistribution and use in source and binary forms, with or without+ modification, are permitted provided that the following conditions are+ met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.+ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following disclaimer+ in the documentation and/or other materials provided with the+ distribution.++ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+ OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++ You can contact the author at :+ - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+ - LZ4 source repository : http://code.google.com/p/lz4/+*/+#pragma once+++#if defined (__cplusplus)+extern "C" {+#endif+++int LZ4_compressHC (const char* source, char* dest, int inputSize);+/*+LZ4_compressHC :+ return : the number of bytes in compressed buffer dest+ or 0 if compression fails.+ note : destination buffer must be already allocated.+ To avoid any problem, size it to handle worst cases situations (input data not compressible)+ Worst case size evaluation is provided by function LZ4_compressBound() (see "lz4.h")+*/++int LZ4_compressHC_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize);+/*+LZ4_compress_limitedOutput() :+ Compress 'inputSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.+ If it cannot achieve it, compression will stop, and result of the function will be zero.+ This function never writes outside of provided output buffer.++ inputSize : Max supported value is 1 GB+ maxOutputSize : is maximum allowed size into the destination buffer (which must be already allocated)+ return : the number of output bytes written in buffer 'dest'+ or 0 if compression fails.+*/+++int LZ4_compressHC2 (const char* source, char* dest, int inputSize, int compressionLevel);+int LZ4_compressHC2_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);+/*+ Same functions as above, but with programmable 'compressionLevel'.+ Recommended values are between 4 and 9, although any value between 0 and 16 will work.+ 'compressionLevel'==0 means use default 'compressionLevel' value.+ Values above 16 behave the same as 16.+ Equivalent variants exist for all other compression functions below.+*/++/* Note :+Decompression functions are provided within LZ4 source code (see "lz4.h") (BSD license)+*/+++/**************************************+ Using an external allocation+**************************************/+int LZ4_sizeofStateHC(void);+int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize);+int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize);++int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel);+int LZ4_compressHC2_limitedOutput_withStateHC(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);++/*+These functions are provided should you prefer to allocate memory for compression tables with your own allocation methods.+To know how much memory must be allocated for the compression tables, use :+int LZ4_sizeofStateHC();++Note that tables must be aligned for pointer (32 or 64 bits), otherwise compression will fail (return code 0).++The allocated memory can be provided to the compressions functions using 'void* state' parameter.+LZ4_compress_withStateHC() and LZ4_compress_limitedOutput_withStateHC() are equivalent to previously described functions.+They just use the externally allocated memory area instead of allocating their own (on stack, or on heap).+*/+++/**************************************+ Streaming Functions+**************************************/+/* Note : these streaming functions still follows the older model */+void* LZ4_createHC (const char* inputBuffer);+int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize);+int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize);+char* LZ4_slideInputBufferHC (void* LZ4HC_Data);+int LZ4_freeHC (void* LZ4HC_Data);++int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel);+int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);++/*+These functions allow the compression of dependent blocks, where each block benefits from prior 64 KB within preceding blocks.+In order to achieve this, it is necessary to start creating the LZ4HC Data Structure, thanks to the function :++void* LZ4_createHC (const char* inputBuffer);+The result of the function is the (void*) pointer on the LZ4HC Data Structure.+This pointer will be needed in all other functions.+If the pointer returned is NULL, then the allocation has failed, and compression must be aborted.+The only parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer.+The input buffer must be already allocated, and size at least 192KB.+'inputBuffer' will also be the 'const char* source' of the first block.++All blocks are expected to lay next to each other within the input buffer, starting from 'inputBuffer'.+To compress each block, use either LZ4_compressHC_continue() or LZ4_compressHC_limitedOutput_continue().+Their behavior are identical to LZ4_compressHC() or LZ4_compressHC_limitedOutput(),+but require the LZ4HC Data Structure as their first argument, and check that each block starts right after the previous one.+If next block does not begin immediately after the previous one, the compression will fail (return 0).++When it's no longer possible to lay the next block after the previous one (not enough space left into input buffer), a call to :+char* LZ4_slideInputBufferHC(void* LZ4HC_Data);+must be performed. It will typically copy the latest 64KB of input at the beginning of input buffer.+Note that, for this function to work properly, minimum size of an input buffer must be 192KB.+==> The memory position where the next input data block must start is provided as the result of the function.++Compression can then resume, using LZ4_compressHC_continue() or LZ4_compressHC_limitedOutput_continue(), as usual.++When compression is completed, a call to LZ4_freeHC() will release the memory used by the LZ4HC Data Structure.+*/++int LZ4_sizeofStreamStateHC(void);+int LZ4_resetStreamStateHC(void* state, const char* inputBuffer);++/*+These functions achieve the same result as :+void* LZ4_createHC (const char* inputBuffer);++They are provided here to allow the user program to allocate memory using its own routines.++To know how much space must be allocated, use LZ4_sizeofStreamStateHC();+Note also that space must be aligned for pointers (32 or 64 bits).++Once space is allocated, you must initialize it using : LZ4_resetStreamStateHC(void* state, const char* inputBuffer);+void* state is a pointer to the space allocated.+It must be aligned for pointers (32 or 64 bits), and be large enough.+The parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer.+The input buffer must be already allocated, and size at least 192KB.+'inputBuffer' will also be the 'const char* source' of the first block.++The same space can be re-used multiple times, just by initializing it each time with LZ4_resetStreamState().+return value of LZ4_resetStreamStateHC() must be 0 is OK.+Any other value means there was an error (typically, state is not aligned for pointers (32 or 64 bits)).+*/+++#if defined (__cplusplus)+}+#endif
tests/Properties.hs view
@@ -1,14 +1,12 @@-{-# LANGUAGE ViewPatterns, OverloadedStrings #-}+{-# LANGUAGE OverloadedStrings, ViewPatterns #-} module Main (main) where-import Test.Hspec-import Test.Hspec.QuickCheck-import Test.Hspec.HUnit-import Test.HUnit-import Test.QuickCheck-import Control.Applicative+import Control.Applicative+import Test.Hspec+import Test.Hspec.QuickCheck+import Test.QuickCheck +import Codec.Compression.LZ4 import qualified Data.ByteString.Char8 as S-import Codec.Compression.LZ4 main :: IO () main = hspec $ do@@ -27,20 +25,15 @@ prop "is pure (ultra)" $ prop_decompress_pure compressPlusHC decompressPlusHC describe "regression test" $ do let input = "\STXd\STX\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\vexample.com\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\ETX\NUL\NUL\NUL\NUL\NUL\NUL\NUL\SI\NUL\NUL\NUL\NUL\NUL\NUL\NUL\tWhirlpool\NUL\NUL\NUL\NUL\NUL\NUL\NUL\vexample.com\NUL\STXf\SOH\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\ffacebook.com\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\b\NUL\NUL\NUL\NUL\NUL\NUL\NUL\EOTSHA1\NUL\NUL\NUL\NUL\NUL\NUL\NUL\ffacebook.com\NUL\SOH\NUL\NUL\NUL\NUL\NUL\NUL\NUL\tgmail.com\SOH\NUL\NUL\NUL\NUL\NUL\NUL"- it "can compress an oddly full-of-NULLs string"- (TestCase $ assertEqual "odd string" (Just input) (return input >>=- compress >>= - decompress))- + it "can compress an oddly full-of-NULLs string" $ do+ (compress input >>= decompress) `shouldBe` Just input prop_compress_pure comp decomp (S.pack -> xs) = (comp xs) == (comp xs) prop_compression_id comp decomp (S.pack -> xs) =- maybe False (== xs) (comp xs >>= decomp) + maybe False (== xs) (comp xs >>= decomp) prop_decompress_pure comp decomp (S.pack -> xs) = let z = comp xs in (z >>= decomp) == (z >>= decomp)--