From 4db6b03fceac50961a8f127aa2eda73d3373a1fe Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 20 May 2014 00:40:29 +0100 Subject: First version of Block Streaming API : LZ4_compress_usingDict() --- lz4.c | 537 ++++++++++++++++++++++++++++++++++++--------------- lz4.h | 144 +++++++------- programs/Makefile | 19 +- programs/fullbench.c | 68 ++++--- programs/fuzzer.c | 63 ++++-- programs/lz4.1 | 3 +- programs/lz4cli.c | 3 +- 7 files changed, 543 insertions(+), 294 deletions(-) diff --git a/lz4.c b/lz4.c index 8001edb..98a6ea8 100644 --- a/lz4.c +++ b/lz4.c @@ -35,15 +35,6 @@ 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 - -/* * 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)). @@ -118,7 +109,6 @@ #endif #ifdef _MSC_VER /* Visual Studio */ -# define FORCE_INLINE static __forceinline # include /* For Visual 2005 */ # if LZ4_ARCH64 /* 64-bits */ # pragma intrinsic(_BitScanForward64) /* For Visual 2005 */ @@ -128,15 +118,6 @@ # 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))) @@ -224,9 +205,9 @@ typedef struct {size_t v;} _PACKED size_t_S; /************************************** Constants **************************************/ -#define LZ4_HASHLOG (MEMORY_USAGE-2) -#define HASHTABLESIZE (1 << MEMORY_USAGE) -#define HASHNBCELLS4 (1 << LZ4_HASHLOG) +#define LZ4_HASHLOG (LZ4_MEMORY_USAGE-2) +#define HASHTABLESIZE (1 << LZ4_MEMORY_USAGE) +#define HASH_SIZE_U32 (1 << LZ4_HASHLOG) #define MINMATCH 4 @@ -255,16 +236,24 @@ static const int LZ4_minLength = (MFLIMIT+1); Structures and local types **************************************/ typedef struct { - U32 hashTable[HASHNBCELLS4]; + U32 hashTable[HASH_SIZE_U32]; const BYTE* bufferStart; const BYTE* base; const BYTE* nextBlock; } LZ4_Data_Structure; +typedef struct { + U32 hashTable[HASH_SIZE_U32]; + U32 currentOffset; + U32 initCheck; + const BYTE* dictionary; + U32 dictSize; +} LZ4_dict_t_internal; + typedef enum { notLimited = 0, limited = 1 } limitedOutput_directive; typedef enum { byPtr, byU32, byU16 } tableType_t; -typedef enum { noDict = 0, withPrefix64k = 1, withExtDict=2 } dict_directive; +typedef enum { noDict = 0, withPrefix64k = 1, usingDict = 2 } dict_directive; typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; typedef enum { full = 0, partial = 1 } earlyEnd_directive; @@ -289,12 +278,12 @@ typedef enum { full = 0, partial = 1 } earlyEnd_directive; /************************************** 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; */ +# define LZ4_WILDCOPY(d,s,e) { do { LZ4_COPY8(d,s) } while (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> ((MINMATCH*8)-(LZ4_HASHLOG+1))); @@ -379,9 +368,9 @@ FORCE_INLINE int LZ4_hashSequence(U32 sequence, tableType_t tableType) return (((sequence) * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG)); } -FORCE_INLINE int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); } +static int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); } -FORCE_INLINE void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase) +static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase) { switch (tableType) { @@ -391,27 +380,45 @@ FORCE_INLINE void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, t } } -FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) +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); } -FORCE_INLINE const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* 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 */ } -FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) +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(pInbase : (const BYTE*) source; + const BYTE* base; const BYTE* const lowLimit = ((dict==withPrefix64k) ? ((LZ4_Data_Structure*)ctx)->bufferStart : (const BYTE*)source); const BYTE* anchor = (const BYTE*) source; const BYTE* const iend = ip + inputSize; @@ -433,16 +440,27 @@ FORCE_INLINE int LZ4_compress_generic( BYTE* op = (BYTE*) dest; BYTE* const oend = op + maxOutputSize; - int length; const int skipStrength = SKIPSTRENGTH; U32 forwardH; /* Init conditions */ - if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ - if ((dict==withPrefix64k) && (ip != ((LZ4_Data_Structure*)ctx)->nextBlock)) return 0; /* must continue from end of previous block */ - if (dict==withPrefix64k) ((LZ4_Data_Structure*)ctx)->nextBlock=iend; /* do it now, due to potential early exit */ - if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0; /* Size too large (not within 64K limit) */ - if (inputSize (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ + switch(dict) + { + case noDict: + default: + base = (const BYTE*)source; break; + case withPrefix64k: + base =((LZ4_Data_Structure*)ctx)->base; + if (ip != ((LZ4_Data_Structure*)ctx)->nextBlock) return 0; /* must continue from end of previous block */ + ((LZ4_Data_Structure*)ctx)->nextBlock = iend; /* do it now, due to potential early exit */ + break; + case usingDict: + base = (const BYTE*)source - ((LZ4_dict_t_internal*)ctx)->currentOffset; break; + } + if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0; /* Size too large (not within 64K limit) */ + if (inputSize> skipStrength; U32 h = forwardH; - int step = findMatchAttempts++ >> skipStrength; ip = forwardIp; - forwardIp = ip + step; + forwardIp += step; - if (unlikely(forwardIp > mflimit)) { goto _last_literals; } - - forwardH = LZ4_hashPosition(forwardIp, tableType); ref = LZ4_getPositionOnHash(h, ctx, tableType, base); + if (unlikely(ip >= mflimit)) goto _last_literals; + forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx, tableType, base); } while ((ref + MAX_DISTANCE < ip) || (A32(ref) != A32(ip))); @@ -474,56 +491,50 @@ FORCE_INLINE int LZ4_compress_generic( /* Catch up */ while ((ip>anchor) && (ref > lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } - /* Encode Literal length */ - length = (int)(ip - anchor); - token = op++; - if ((limitedOutput) && (unlikely(op + length + (2 + 1 + LASTLITERALS) + (length/255) > oend))) return 0; /* Check output limit */ - if (length>=(int)RUN_MASK) { - int len = length-RUN_MASK; - *token=(RUN_MASK<= 255 ; len-=255) *op++ = 255; - *op++ = (BYTE)len; - } - else *token = (BYTE)(length< oend))) return 0; /* Check output limit */ + if (litLength>=RUN_MASK) + { + int len = (int)litLength-RUN_MASK; + *token=(RUN_MASK<= 255 ; len-=255) *op++ = 255; + *op++ = (BYTE)len; + } + else *token = (BYTE)(litLength<>8) > oend))) return 0; /* 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 >= 255) { length-=255; *op++ = 255; } - *op++ = (BYTE)length; + unsigned matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); + ip += matchLength + MINMATCH; + if (matchLength>=ML_MASK) + { + if ((limitedOutput) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ + *token += ML_MASK; + matchLength -= ML_MASK; + for (; matchLength > 509 ; matchLength-=510) { *op++ = 255; *op++ = 255; } + if (matchLength >= 255) { matchLength-=255; *op++ = 255; } + *op++ = (BYTE)matchLength; + } + else *token += (BYTE)(matchLength); } - else *token += (BYTE)(length); + + anchor = ip; /* Test end of chunk */ - if (ip > mflimit) { anchor = ip; break; } + if (ip > mflimit) break; /* Fill table */ LZ4_putPosition(ip-2, ctx, tableType, base); @@ -534,8 +545,7 @@ _endCount: if ((ref + MAX_DISTANCE >= ip) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } /* Prepare next loop */ - anchor = ip++; - forwardH = LZ4_hashPosition(ip, tableType); + forwardH = LZ4_hashPosition(++ip, tableType); } _last_literals: @@ -557,9 +567,9 @@ _last_literals: int LZ4_compress(const char* source, char* dest, int inputSize) { #if (HEAPMODE) - void* ctx = ALLOCATOR(HASHNBCELLS4, 4); /* Aligned on 4-bytes boundaries */ + void* ctx = ALLOCATOR(LZ4_DICTSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ #else - U32 ctx[1U<<(MEMORY_USAGE-2)] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ + U32 ctx[LZ4_DICTSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ #endif int result; @@ -577,9 +587,9 @@ int LZ4_compress(const char* source, char* dest, int inputSize) int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { #if (HEAPMODE) - void* ctx = ALLOCATOR(HASHNBCELLS4, 4); /* Aligned on 4-bytes boundaries */ + void* ctx = ALLOCATOR(LZ4_DICTSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ #else - U32 ctx[1U<<(MEMORY_USAGE-2)] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ + U32 ctx[LZ4_DICTSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ #endif int result; @@ -596,10 +606,10 @@ int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, in /***************************** - Using external allocation + User-allocated state *****************************/ -int LZ4_sizeofState() { return 1 << MEMORY_USAGE; } +int LZ4_sizeofState() { return LZ4_DICTSIZE; } int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize) @@ -626,87 +636,223 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* } -/**************************** - Stream functions -****************************/ +/*************************************** + Experimental : Streaming functions +***************************************/ -int LZ4_sizeofStreamState() +void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const char* source) { - return sizeof(LZ4_Data_Structure); + if ((source - LZ4_dict->currentOffset > source) + || (LZ4_dict->currentOffset > 0x80000000)) + { + /* rescale hash table */ + U32 delta = LZ4_dict->currentOffset - 64 KB; + int i; + for (i=0; ihashTable[i] < delta) LZ4_dict->hashTable[i]=0; + else LZ4_dict->hashTable[i] -= delta; + } + LZ4_dict->currentOffset = 64 KB; + } } -FORCE_INLINE void LZ4_init(LZ4_Data_Structure* lz4ds, const BYTE* base) -{ - MEM_INIT(lz4ds->hashTable, 0, sizeof(lz4ds->hashTable)); - lz4ds->bufferStart = base; - lz4ds->base = base; - lz4ds->nextBlock = base; -} -int LZ4_resetStreamState(void* state, const char* inputBuffer) +int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { - if ((((size_t)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */ - LZ4_init((LZ4_Data_Structure*)state, (const BYTE*)inputBuffer); - return 0; -} + LZ4_dict_t_internal* const streamPtr = (LZ4_dict_t_internal*)LZ4_dict; + const int maxOutputSize = 0; + const limitedOutput_directive limitedOutput = notLimited; + const tableType_t tableType = byU32; + U32 currentOffset; + const U32 dictSize = streamPtr->dictSize; + const BYTE* const dictionary = streamPtr->dictionary; -void* LZ4_create (const char* inputBuffer) -{ - void* lz4ds = ALLOCATOR(1, sizeof(LZ4_Data_Structure)); - LZ4_init ((LZ4_Data_Structure*)lz4ds, (const BYTE*)inputBuffer); - return lz4ds; -} + if (streamPtr->initCheck) return 0; /* structure not initialized */ + LZ4_renormDictT(streamPtr, source); + currentOffset = streamPtr->currentOffset; -int LZ4_free (void* LZ4_Data) -{ - FREEMEM(LZ4_Data); - return (0); -} + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += inputSize; + { + U32 ipIndex = currentOffset; + const BYTE* ip = (const BYTE*) source; + const BYTE* anchor = (const BYTE*) source; + const BYTE* const iend = ip + inputSize; + const BYTE* const base = (const BYTE*)source - currentOffset; + const BYTE* const dictEnd = dictionary + dictSize; + const BYTE* const dictBase = dictEnd - currentOffset; + const BYTE* const mflimit = iend - MFLIMIT; + const U32 indexLimit = ipIndex + inputSize - MFLIMIT; + const BYTE* const matchlimit = iend - LASTLITERALS; + + BYTE* op = (BYTE*) dest; + BYTE* const oend = op + maxOutputSize; + + const int skipStrength = SKIPSTRENGTH; + + /* Init conditions */ + if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ + if (inputSize> skipStrength; + h = LZ4_hashPosition(base + ipIndex, tableType); + refIndex = streamPtr->hashTable[h]; + streamPtr->hashTable[h] = ipIndex; + + if (unlikely(ipIndex > indexLimit)) goto _last_literals; + + ip = base + ipIndex; + if (refIndex < currentOffset) + { + ref = dictBase + refIndex; + lowLimit = dictionary; + } + else + { + ref = base + refIndex; + lowLimit = (const BYTE*)source; + } -char* LZ4_slideInputBuffer (void* LZ4_Data) -{ - LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data; - size_t delta = lz4ds->nextBlock - (lz4ds->bufferStart + 64 KB); + } while ((refIndex + MAX_DISTANCE < ipIndex) || (A32(ref) != A32(ip))); - if ( (lz4ds->base - delta > lz4ds->base) /* underflow control */ - || ((size_t)(lz4ds->nextBlock - lz4ds->base) > 0xE0000000) ) /* close to 32-bits limit */ - { - size_t deltaLimit = (lz4ds->nextBlock - 64 KB) - lz4ds->base; - int nH; + /* Catch up */ + while ((ip>anchor) && (ref>lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } + + { + /* Encode Literal length */ + unsigned litLength = (unsigned)(ip - anchor); + + token = op++; + if ((limitedOutput) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ + if (litLength>=RUN_MASK) + { + unsigned remaininglength = litLength - RUN_MASK; + *token=(RUN_MASK<= 255 ; remaininglength-=255) *op++ = 255; + *op++ = (BYTE)remaininglength; + } + else *token = (BYTE)(litLength << ML_BITS); + + /* Copy Literals */ + { BYTE* end=op+litLength; LZ4_WILDCOPY(op,anchor,end); op=end; } + } + + /* Encode Offset */ + LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ipIndex-refIndex)); + + /* Encode MatchLength */ + { + unsigned matchLength; + if (refIndex >= currentOffset) + matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); + else + { + matchLength = 0; + const BYTE* dicLimit = ip + (dictEnd - ref); + if (dicLimit > matchlimit) dicLimit = matchlimit; + matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, dicLimit); + if (ref + MINMATCH + matchLength == dictEnd) + matchLength += LZ4_count(ip+MINMATCH+matchLength, (const BYTE*)source, matchlimit); + } + ip += matchLength + MINMATCH; + if (matchLength>=ML_MASK) + { + if ((limitedOutput) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ + *token += ML_MASK; + matchLength -= ML_MASK; + for (; matchLength > 509 ; 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, streamPtr->hashTable, tableType, base); + } - for (nH=0; nH < HASHNBCELLS4; nH++) + _last_literals: + /* Encode Last Literals */ { - if ((size_t)(lz4ds->hashTable[nH]) < deltaLimit) lz4ds->hashTable[nH] = 0; - else lz4ds->hashTable[nH] -= (U32)deltaLimit; + int lastRun = (int)(iend - anchor); + if ((limitedOutput) && (((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<= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } + else *op++ = (BYTE)(lastRun<bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); - lz4ds->base = lz4ds->bufferStart; - lz4ds->nextBlock = lz4ds->base + 64 KB; - } - else - { - memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); - lz4ds->nextBlock -= delta; - lz4ds->base -= delta; - } - return (char*)(lz4ds->nextBlock); + /* End */ + return (int) (((char*)op)-dest); + } } -int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize) +int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) { - return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; + + dict->dictionary = (const BYTE*)dictionary; + dict->dictSize = (U32)dictSize; + if (dict->currentOffset < dict->dictSize) return 0; + return 1; } -int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize) + +int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) { - return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limited, byU32, withPrefix64k); + LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; + const BYTE* p = (const BYTE*)dictionary; + const BYTE* const dictEnd = p + dictSize; + const BYTE* base; + + LZ4_STATIC_ASSERT(LZ4_DICTSIZE >= sizeof(LZ4_dict_t_internal)); /* A compilation error here means LZ4_DICTSIZE is not large enough */ + if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_dict_t_internal)); + + if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB; + if (dictSize < MINMATCH) p = dictEnd; + 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; } + /**************************** Decompression functions ****************************/ @@ -716,7 +862,7 @@ int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, cha * 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( +int LZ4_decompress_generic( const char* source, char* dest, int inputSize, @@ -740,7 +886,7 @@ FORCE_INLINE int LZ4_decompress_generic( BYTE* cpy; BYTE* oexit = op + targetOutputSize; - const BYTE* const dictEnd = (dict==withExtDict) ? (const BYTE*)dictStart + dictSize : NULL; + const BYTE* const dictEnd = (dict==usingDict) ? (const BYTE*)dictStart + dictSize : NULL; const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */ static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; @@ -814,7 +960,7 @@ FORCE_INLINE int LZ4_decompress_generic( } /* check external dictionary */ - if ((dict==withExtDict) && (unlikely(ref < (BYTE* const)dest))) + if ((dict==usingDict) && (unlikely(ref < (BYTE* const)dest))) { if (unlikely(op+length+MINMATCH > oend-LASTLITERALS)) goto _output_error; @@ -830,7 +976,7 @@ FORCE_INLINE int LZ4_decompress_generic( memcpy(op, dictEnd - copySize, copySize); op += copySize; copySize = length+MINMATCH - copySize; - if (copySize > (size_t)((char*)op-dest)) + if (copySize > (size_t)((char*)op-dest)) /* overlap */ { BYTE* const cpy = op + copySize; const BYTE* ref = (BYTE*)dest; @@ -862,7 +1008,7 @@ FORCE_INLINE int LZ4_decompress_generic( if (unlikely(cpy>oend-COPYLENGTH-(STEPSIZE-4))) { if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last 5 bytes must be literals */ - LZ4_SECURECOPY(op, ref, (oend-COPYLENGTH)); + if (ophashTable, 0, sizeof(lz4ds->hashTable)); + lz4ds->bufferStart = base; + lz4ds->base = base; + lz4ds->nextBlock = 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_Data_Structure*)state, (const BYTE*)inputBuffer); + return 0; +} + +void* LZ4_create (const char* inputBuffer) +{ + void* lz4ds = ALLOCATOR(1, sizeof(LZ4_Data_Structure)); + LZ4_init ((LZ4_Data_Structure*)lz4ds, (const BYTE*)inputBuffer); + return lz4ds; +} + +int LZ4_free (void* LZ4_Data) +{ + FREEMEM(LZ4_Data); + return (0); +} + + +char* LZ4_slideInputBuffer (void* LZ4_Data) +{ + LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data; + size_t delta = lz4ds->nextBlock - (lz4ds->bufferStart + 64 KB); + + if ( (lz4ds->base - delta > lz4ds->base) /* underflow control */ + || ((size_t)(lz4ds->nextBlock - lz4ds->base) > 0xE0000000) ) /* close to 32-bits limit */ + { + size_t deltaLimit = (lz4ds->nextBlock - 64 KB) - lz4ds->base; + int nH; + + for (nH=0; nH < HASH_SIZE_U32; nH++) + { + if ((size_t)(lz4ds->hashTable[nH]) < deltaLimit) lz4ds->hashTable[nH] = 0; + else lz4ds->hashTable[nH] -= (U32)deltaLimit; + } + memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); + lz4ds->base = lz4ds->bufferStart; + lz4ds->nextBlock = lz4ds->base + 64 KB; + } + else + { + memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); + lz4ds->nextBlock -= delta; + lz4ds->base -= delta; + } + + return (char*)(lz4ds->nextBlock); +} + + +int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize) +{ + return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); +} + +int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize) +{ + return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limited, byU32, withPrefix64k); +} diff --git a/lz4.h b/lz4.h index 37bd282..5e695c7 100644 --- a/lz4.h +++ b/lz4.h @@ -28,8 +28,8 @@ 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/ + - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c */ #pragma once @@ -47,11 +47,16 @@ extern "C" { /************************************** - Compiler Options + Tuning parameter **************************************/ -#if (defined(__GNUC__) && defined(__STRICT_ANSI__)) || (defined(_MSC_VER) && !defined(__cplusplus)) /* Visual Studio */ -# define inline __inline /* Visual C is not C99, but supports some kind of inline */ -#endif +/* + * 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 /************************************** @@ -72,10 +77,14 @@ LZ4_compress() : or 0 if the compression fails LZ4_decompress_safe() : - maxOutputSize : is the size of the destination buffer (which must be already allocated) + 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 (never writes outside of output buffer, and never reads outside of input buffer). Therefore, it is protected against malicious data packets + 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. */ @@ -89,7 +98,6 @@ LZ4_decompress_safe() : 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, 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 @@ -143,11 +151,11 @@ int LZ4_decompress_safe_partial (const char* source, char* dest, int compressedS /* -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 : +The following functions are provided should you prefer to allocate table memory using your own allocation methods. int LZ4_sizeofState(); +provides the size to allocate for compression tables. -Note that tables must be aligned on 4-bytes boundaries, otherwise compression will fail (return code 0). +Tables must be aligned on 4-bytes boundaries, otherwise compression will fail (return code 0). The allocated memory can be provided to the compressions functions using 'void* state' parameter. LZ4_compress_withState() and LZ4_compress_limitedOutput_withState() are equivalent to previously described functions. @@ -159,67 +167,52 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* /************************************** - Streaming Functions + Experimental Streaming Functions **************************************/ -void* LZ4_create (const char* inputBuffer); -int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize); -int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize); -char* LZ4_slideInputBuffer (void* LZ4_Data); -int LZ4_free (void* LZ4_Data); +#define LZ4_DICTSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 6) +#define LZ4_DICTSIZE (LZ4_DICTSIZE_U32 * sizeof(unsigned int)) /* -These functions allow the compression of chained blocks, where each block benefits from prior 64 KB within preceding blocks. -In order to achieve this, it is necessary to start creating the LZ4 Data Structure, thanks to the function : - -void* LZ4_create (const char* inputBuffer); -The result of the function is the (void*) pointer on the LZ4 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_compress_continue() or LZ4_compress_limitedOutput_continue(). -Their behavior are identical to LZ4_compress() or LZ4_compress_limitedOutput(), -but require the LZ4 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_slideInputBuffer(void* LZ4_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_compress_continue() or LZ4_compress_limitedOutput_continue(), as usual. - -When compression is completed, a call to LZ4_free() will release the memory used by the LZ4 Data Structure. -*/ - + * LZ4_dict_t + * information structure to track an LZ4 stream + * set it to zero (memset()) before first use/ + */ +typedef struct { unsigned int table[LZ4_DICTSIZE_U32]; } LZ4_dict_t; /* -The following functions achieve the same result as : -void* LZ4_create (const char* inputBuffer); + * LZ4_compress_usingDict + * Compress data block 'source', using blocks compressed before (with the same function) to improve compression ratio + * Previous data blocks are assumed to still be present at their previous location. + */ +int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); +//int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize); -They are provided here to allow the user program to allocate memory using its own routines. +/* + * LZ4_setDictPos + * If previous data blocks cannot be guaranteed to remain at their previous location in memory + * save them into a safe place, and + * use this function to indicate where to find them. + * Return : 1 if OK, 0 if error + */ +int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); -To know how much space must be allocated, use LZ4_sizeofStreamState(); -Note also that space must be 4-bytes aligned. +/* + * LZ4_loadDict + * Use this function to load a static dictionary into LZ4_dict. + * It will be used to improve compression of next chained block. + * Return : 1 if OK, 0 if error + */ +int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); -Once space is allocated, you must initialize it using : LZ4_resetStreamState(void* state, const char* inputBuffer); -void* state is a pointer to the space allocated. -It must be aligned on 4-bytes boundaries, 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_resetStreamState() must be 0 is OK. -Any other value means there was an error (typically, pointer is not aligned on 4-bytes boundaries). +/* +*_usingDict() : + These decoding functions work the same as their "normal" versions, + but can also use up to 64KB of dictionary data (dictStart, dictSize) + to decode chained blocks. */ -int LZ4_sizeofStreamState(void); -int LZ4_resetStreamState(void* state, const char* inputBuffer); - +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); /* *_withPrefix64k() : @@ -233,28 +226,23 @@ int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int origi /************************************** - Experimental Functions -**************************************/ -/* -*_withDict() : - These decoding functions work the same as their "normal" versions, - but can also use up to 64KB of dictionary data - to decode chained blocks. -*/ -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 **************************************/ /* These functions are deprecated and should no longer be used. They are provided here for compatibility with existing user programs. */ -int LZ4_uncompress (const char* source, char* dest, int outputSize); -int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); +int LZ4_uncompress (const char* source, char* dest, int outputSize); +int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); + +/* Obsolete streaming functions */ +void* LZ4_create (const char* inputBuffer); +int LZ4_sizeofStreamState(void); +int LZ4_resetStreamState(void* state, const char* inputBuffer); +int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize); +int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize); +char* LZ4_slideInputBuffer (void* LZ4_Data); +int LZ4_free (void* LZ4_Data); #if defined (__cplusplus) diff --git a/programs/Makefile b/programs/Makefile index c0d6d15..a81a701 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -42,15 +42,6 @@ MANDIR=$(PREFIX)/share/man/man1 LZ4DIR=.. TEST_FILES = COPYING -TEST_TARGETS=test-32 test-64 - -# Minimize test target for Travis CI's Build Matrix -ifeq ($(LZ4_TRAVIS_CI_ENV),-m32) -TEST_TARGETS=test-32 -else ifeq ($(LZ4_TRAVIS_CI_ENV),-m64) -TEST_TARGETS=test-64 -endif - # Define *.exe as extension for Windows systems ifneq (,$(filter Windows%,$(OS))) @@ -115,11 +106,7 @@ uninstall: [ -f $(DESTDIR)$(MANDIR)/lz4cat.1 ] && rm -f $(DESTDIR)$(MANDIR)/lz4cat.1 @echo lz4 successfully uninstalled -test: $(TEST_TARGETS) - -test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 - -test-64: test-lz4 test-lz4c test-fullbench test-fuzzer +test: test-lz4 test-lz4c test-lz4c32 test-fullbench test-fullbench32 test-fuzzer test-fuzzer32 test-lz4: @@ -128,10 +115,10 @@ test-lz4c: test-lz4c32: test-fullbench: fullbench - ./fullbench --no-prompt $(TEST_FILES) + ./fullbench --no-prompt -i1 $(TEST_FILES) test-fullbench32: fullbench32 - ./fullbench32 --no-prompt $(TEST_FILES) + ./fullbench32 --no-prompt -i1 $(TEST_FILES) test-fuzzer: fuzzer ./fuzzer --no-prompt diff --git a/programs/fullbench.c b/programs/fullbench.c index 1200ca0..01b807c 100644 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -281,6 +281,21 @@ static inline int local_LZ4_compress_limitedOutput_continue(const char* in, char return LZ4_compress_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize)); } + +LZ4_dict_t LZ4_dict; +static inline void* local_LZ4_resetDictT(const char* fake) +{ + (void)fake; + memset(&LZ4_dict, 0, sizeof(LZ4_dict_t)); + return NULL; +} + +static inline int local_LZ4_compress_usingDict(const char* in, char* out, int inSize) +{ + return LZ4_compress_usingDict(&LZ4_dict, in, out, inSize); +} + + static void* stateLZ4HC; static inline int local_LZ4_compressHC_withStateHC(const char* in, char* out, int inSize) { @@ -344,15 +359,9 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) { int fileIdx=0; char* orig_buff; -# define NB_COMPRESSION_ALGORITHMS 12 +# define NB_COMPRESSION_ALGORITHMS 13 # define MINCOMPRESSIONCHAR '0' # define MAXCOMPRESSIONCHAR (MINCOMPRESSIONCHAR + NB_COMPRESSION_ALGORITHMS) - static char* compressionNames[] = { "LZ4_compress", "LZ4_compress_limitedOutput", - "LZ4_compress_withState", "LZ4_compress_limitedOutput_withState", - "LZ4_compress_continue", "LZ4_compress_limitedOutput_continue", - "LZ4_compressHC", "LZ4_compressHC_limitedOutput", - "LZ4_compressHC_withStateHC", "LZ4_compressHC_limitedOutput_withStateHC", - "LZ4_compressHC_continue", "LZ4_compressHC_limitedOutput_continue" }; double totalCTime[NB_COMPRESSION_ALGORITHMS] = {0}; double totalCSize[NB_COMPRESSION_ALGORITHMS] = {0}; # define NB_DECOMPRESSION_ALGORITHMS 7 @@ -465,29 +474,30 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) DISPLAY(" %s : \n", inFileName); // Compression Algorithms - for (cAlgNb=0; (cAlgNb < NB_COMPRESSION_ALGORITHMS) && (compressionTest); cAlgNb++) + for (cAlgNb=1; (cAlgNb <= NB_COMPRESSION_ALGORITHMS) && (compressionTest); cAlgNb++) { - char* cName = compressionNames[cAlgNb]; + char* compressorName; int (*compressionFunction)(const char*, char*, int); void* (*initFunction)(const char*) = NULL; double bestTime = 100000000.; - if ((compressionAlgo != ALL_COMPRESSORS) && (compressionAlgo != cAlgNb+1)) continue; + if ((compressionAlgo != ALL_COMPRESSORS) && (compressionAlgo != cAlgNb)) continue; switch(cAlgNb) { - case 0 : compressionFunction = LZ4_compress; break; - case 1 : compressionFunction = local_LZ4_compress_limitedOutput; break; - case 2 : compressionFunction = local_LZ4_compress_withState; break; - case 3 : compressionFunction = local_LZ4_compress_limitedOutput_withState; break; - case 4 : compressionFunction = local_LZ4_compress_continue; initFunction = LZ4_create; break; - case 5 : compressionFunction = local_LZ4_compress_limitedOutput_continue; initFunction = LZ4_create; break; - case 6 : compressionFunction = LZ4_compressHC; break; - case 7 : compressionFunction = local_LZ4_compressHC_limitedOutput; break; - case 8 : compressionFunction = local_LZ4_compressHC_withStateHC; break; - case 9 : compressionFunction = local_LZ4_compressHC_limitedOutput_withStateHC; break; - case 10: compressionFunction = local_LZ4_compressHC_continue; initFunction = LZ4_createHC; break; - case 11: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; break; + case 1 : compressionFunction = LZ4_compress; compressorName = "LZ4_compress"; break; + case 2 : compressionFunction = local_LZ4_compress_limitedOutput; compressorName = "LZ4_compress_limitedOutput"; break; + case 3 : compressionFunction = local_LZ4_compress_withState; compressorName = "LZ4_compress_withState"; break; + case 4 : compressionFunction = local_LZ4_compress_limitedOutput_withState; compressorName = "LZ4_compress_limitedOutput_withState"; break; + case 5 : compressionFunction = local_LZ4_compress_continue; initFunction = LZ4_create; compressorName = "LZ4_compress_continue"; break; + case 6 : compressionFunction = local_LZ4_compress_limitedOutput_continue; initFunction = LZ4_create; compressorName = "LZ4_compress_limitedOutput_continue"; break; + case 7 : compressionFunction = LZ4_compressHC; compressorName = "LZ4_compressHC"; break; + case 8 : compressionFunction = local_LZ4_compressHC_limitedOutput; compressorName = "LZ4_compressHC_limitedOutput"; break; + case 9 : compressionFunction = local_LZ4_compressHC_withStateHC; compressorName = "LZ4_compressHC_withStateHC"; break; + case 10: compressionFunction = local_LZ4_compressHC_limitedOutput_withStateHC; compressorName = "LZ4_compressHC_limitedOutput_withStateHC"; break; + case 11: compressionFunction = local_LZ4_compressHC_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_continue"; break; + case 12: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_limitedOutput_continue"; break; + case 13: compressionFunction = local_LZ4_compress_usingDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_usingDict"; break; default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; } @@ -496,7 +506,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) double averageTime; int milliTime; - PROGRESS("%1i-%-21.21s : %9i ->\r", loopNb, cName, (int)benchedSize); + PROGRESS("%1i-%-25.25s : %9i ->\r", loopNb, compressorName, (int)benchedSize); { size_t i; for (i=0; i %9i (%5.2f%%),%7.1f MB/s\r", loopNb, cName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + PROGRESS("%1i-%-25.25s : %9i -> %9i (%5.2f%%),%7.1f MB/s\r", loopNb, compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); } if (ratio<100.) - DISPLAY("%-23.23s : %9i -> %9i (%5.2f%%),%7.1f MB/s\n", cName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + DISPLAY("%-27.27s : %9i -> %9i (%5.2f%%),%7.1f MB/s\n", compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); else - DISPLAY("%-23.23s : %9i -> %9i (%5.1f%%),%7.1f MB/s\n", cName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + DISPLAY("%-27.27s : %9i -> %9i (%5.1f%%),%7.1f MB/s\n", compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); totalCTime[cAlgNb] += bestTime; totalCSize[cAlgNb] += cSize; @@ -536,7 +546,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) for (chunkNb=0; chunkNb 1) { int AlgNb; @@ -625,6 +636,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) DISPLAY("%-31.31s :%10llu -> %6.1f MB/s\n", dName, (long long unsigned int)totals, (double)totals/totalDTime[AlgNb]/1000.); } } +*/ if (BMK_pause) { printf("press enter...\n"); getchar(); } diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 1ea14f6..081f0df 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -187,7 +187,7 @@ int FUZ_SecurityTest() #define FUZ_MAX(a,b) (a>b?a:b) -int FUZ_test(U32 seed, int nbTests, double compressibility) { +int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { unsigned long long bytes = 0; unsigned long long cbytes = 0; unsigned long long hcbytes = 0; @@ -197,10 +197,10 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { char* decodedBuffer; # define FUZ_max LZ4_COMPRESSBOUND(LEN) unsigned int randState=seed; - int ret, attemptNb; + int ret, cycleNb; # define FUZ_CHECKTEST(cond, ...) if (cond) { printf("Test %i : ", testNb); printf(__VA_ARGS__); \ - printf(" (seed %u, cycle %i) \n", seed, attemptNb); goto _output_error; } -# define FUZ_DISPLAYTEST testNb++; no_prompt ? 0 : printf("%2i\b\b", testNb); + printf(" (seed %u, cycle %i) \n", seed, cycleNb); goto _output_error; } +# define FUZ_DISPLAYTEST { testNb++; no_prompt ? 0 : printf("%2i\b\b", testNb); } void* stateLZ4 = malloc(LZ4_sizeofState()); void* stateLZ4HC = malloc(LZ4_sizeofStateHC()); void* LZ4continue; @@ -213,8 +213,16 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { compressedBuffer = malloc(LZ4_compressBound(FUZ_MAX_BLOCK_SIZE)); decodedBuffer = malloc(FUZ_MAX_DICT_SIZE + FUZ_MAX_BLOCK_SIZE); + // move to startCycle + for (cycleNb = 0; cycleNb < startCycle; cycleNb++) + { + FUZ_rand(&randState); + FUZ_rand(&randState); + FUZ_rand(&randState); + } + // Test loop - for (attemptNb = 0; attemptNb < nbTests; attemptNb++) + for (cycleNb = startCycle; cycleNb < nbCycles; cycleNb++) { int testNb = 0; char* dict; @@ -224,11 +232,11 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { // note : promptThrottle is throtting stdout to prevent // Travis-CI's output limit (10MB) and false hangup detection. - const int step = FUZ_MAX(1, nbTests / 100); - const int promptThrottle = ((attemptNb % step) == 0); - if (!no_prompt || attemptNb == 0 || promptThrottle) + const int step = FUZ_MAX(1, nbCycles / 100); + const int promptThrottle = ((cycleNb % step) == 0); + if (!no_prompt || cycleNb == 0 || promptThrottle) { - printf("\r%7i /%7i - ", attemptNb, nbTests); + printf("\r%7i /%7i - ", cycleNb, nbCycles); if (no_prompt) fflush(stdout); } @@ -305,7 +313,7 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, blockSize+1); FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe failed despite amply sufficient space"); FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe did not regenerate original data"); - //FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_safe wrote more than target size"); // well, is that an issue ? + //FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_safe wrote more than (unknown) target size"); // well, is that an issue ? FUZ_CHECKTEST(decodedBuffer[blockSize+1], "LZ4_decompress_safe overrun specified output buffer size"); crcCheck = XXH32(decodedBuffer, blockSize, 0); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); @@ -409,6 +417,18 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_withPrefix64k corrupted decoded data"); + // Compress using dictionary + FUZ_DISPLAYTEST; + dict -= 9; + if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; + { + LZ4_dict_t LZ4dict; + memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + LZ4_loadDict(&LZ4dict, dict, dictSize); + blockContinueCompressedSize = LZ4_compress_usingDict(&LZ4dict, block, compressedBuffer, blockSize); + FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_usingDict failed"); + } + // Decompress with dictionary as external FUZ_DISPLAYTEST; decodedBuffer[blockSize] = 0; @@ -416,6 +436,13 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_usingDict did not read all compressed block input"); FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_fast_usingDict overrun specified output buffer size") crcCheck = XXH32(decodedBuffer, blockSize, 0); + if (crcCheck!=crcOrig) + { + int i=0; + while (block[i]==decodedBuffer[i]) i++; + printf("Wrong Byte at position %i/%i\n", i, blockSize); + + } FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data"); FUZ_DISPLAYTEST; @@ -455,7 +482,7 @@ int FUZ_test(U32 seed, int nbTests, double compressibility) { ccbytes += blockContinueCompressedSize; } - printf("\r%7i /%7i - ", attemptNb, nbTests); + printf("\r%7i /%7i - ", cycleNb, nbCycles); printf("all tests completed successfully \n"); printf("compression ratio: %0.3f%%\n", (double)cbytes/bytes*100); printf("HC compression ratio: %0.3f%%\n", (double)hcbytes/bytes*100); @@ -489,6 +516,7 @@ int FUZ_usage() DISPLAY( "Arguments :\n"); DISPLAY( " -i# : Nb of tests (default:%i) \n", NB_ATTEMPTS); DISPLAY( " -s# : Select seed (default:prompt user)\n"); + DISPLAY( " -t# : Select starting test number (default:0)\n"); DISPLAY( " -p# : Select compressibility in %% (default:%i%%)\n", FUZ_COMPRESSIBILITY_DEFAULT); DISPLAY( " -h : display help and exit\n"); return 0; @@ -502,6 +530,7 @@ int main(int argc, char** argv) { int seedset=0; int argNb; int nbTests = NB_ATTEMPTS; + int testNb = 0; int proba = FUZ_COMPRESSIBILITY_DEFAULT; // Check command line @@ -544,6 +573,16 @@ int main(int argc, char** argv) { argument++; } break; + case 't': + argument++; + testNb=0; + while ((*argument>='0') && (*argument<='9')) + { + testNb *= 10; + testNb += *argument - '0'; + argument++; + } + break; case 'p': argument++; proba=0; @@ -583,5 +622,5 @@ int main(int argc, char** argv) { if (nbTests<=0) nbTests=1; - return FUZ_test(seed, nbTests, ((double)proba) / 100); + return FUZ_test(seed, nbTests, testNb, ((double)proba) / 100); } diff --git a/programs/lz4.1 b/programs/lz4.1 index 298cbf6..6ae8d3c 100644 --- a/programs/lz4.1 +++ b/programs/lz4.1 @@ -64,6 +64,7 @@ following options .TP .B \-B# block size [4-7](default : 7) + B4= 64KB ; B5= 256KB ; B6= 1MB ; B7= 4MB .TP .B \-BD block dependency (improve compression ratio) @@ -84,4 +85,4 @@ following options Report bugs at:- https://code.google.com/p/lz4/ .SH AUTHOR -Yann Collet \ No newline at end of file +Yann Collet diff --git a/programs/lz4cli.c b/programs/lz4cli.c index 934c2bb..1c4e9de 100644 --- a/programs/lz4cli.c +++ b/programs/lz4cli.c @@ -405,9 +405,8 @@ int main(int argc, char** argv) case '7': { int B = argument[1] - '0'; - int S = 1 << (8 + 2*B); - BMK_SetBlocksize(S); blockSize = LZ4IO_setBlockSizeID(B); + BMK_SetBlocksize(blockSize); argument++; break; } -- cgit v0.12 From 7f92b091744ec0dd3b5aa8ca2bafadc459606ce8 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 20 May 2014 01:53:48 +0100 Subject: Fixed : compilation errors using Visual 2012 --- lz4.c | 5 +---- programs/fullbench.c | 34 +++++++++++++++++----------------- 2 files changed, 18 insertions(+), 21 deletions(-) mode change 100644 => 100755 lz4.c mode change 100644 => 100755 programs/fullbench.c diff --git a/lz4.c b/lz4.c old mode 100644 new mode 100755 index 98a6ea8..9a28d68 --- a/lz4.c +++ b/lz4.c @@ -492,10 +492,8 @@ int LZ4_compress_generic( while ((ip>anchor) && (ref > lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } { - unsigned litLength; - /* Encode Literal length */ - litLength = (ip - anchor); + unsigned litLength = (unsigned)(ip - anchor); token = op++; if ((limitedOutput) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ if (litLength>=RUN_MASK) @@ -768,7 +766,6 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); else { - matchLength = 0; const BYTE* dicLimit = ip + (dictEnd - ref); if (dicLimit > matchlimit) dicLimit = matchlimit; matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, dicLimit); diff --git a/programs/fullbench.c b/programs/fullbench.c old mode 100644 new mode 100755 index 01b807c..fe13d0b --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -254,103 +254,103 @@ static U64 BMK_GetFileSize(char* infilename) Benchmark function *********************************************************/ -static inline int local_LZ4_compress_limitedOutput(const char* in, char* out, int inSize) +static int local_LZ4_compress_limitedOutput(const char* in, char* out, int inSize) { return LZ4_compress_limitedOutput(in, out, inSize, LZ4_compressBound(inSize)); } static void* stateLZ4; -static inline int local_LZ4_compress_withState(const char* in, char* out, int inSize) +static int local_LZ4_compress_withState(const char* in, char* out, int inSize) { return LZ4_compress_withState(stateLZ4, in, out, inSize); } -static inline int local_LZ4_compress_limitedOutput_withState(const char* in, char* out, int inSize) +static int local_LZ4_compress_limitedOutput_withState(const char* in, char* out, int inSize) { return LZ4_compress_limitedOutput_withState(stateLZ4, in, out, inSize, LZ4_compressBound(inSize)); } static void* ctx; -static inline int local_LZ4_compress_continue(const char* in, char* out, int inSize) +static int local_LZ4_compress_continue(const char* in, char* out, int inSize) { return LZ4_compress_continue(ctx, in, out, inSize); } -static inline int local_LZ4_compress_limitedOutput_continue(const char* in, char* out, int inSize) +static int local_LZ4_compress_limitedOutput_continue(const char* in, char* out, int inSize) { return LZ4_compress_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize)); } LZ4_dict_t LZ4_dict; -static inline void* local_LZ4_resetDictT(const char* fake) +static void* local_LZ4_resetDictT(const char* fake) { (void)fake; memset(&LZ4_dict, 0, sizeof(LZ4_dict_t)); return NULL; } -static inline int local_LZ4_compress_usingDict(const char* in, char* out, int inSize) +static int local_LZ4_compress_usingDict(const char* in, char* out, int inSize) { return LZ4_compress_usingDict(&LZ4_dict, in, out, inSize); } static void* stateLZ4HC; -static inline int local_LZ4_compressHC_withStateHC(const char* in, char* out, int inSize) +static int local_LZ4_compressHC_withStateHC(const char* in, char* out, int inSize) { return LZ4_compressHC_withStateHC(stateLZ4HC, in, out, inSize); } -static inline int local_LZ4_compressHC_limitedOutput_withStateHC(const char* in, char* out, int inSize) +static int local_LZ4_compressHC_limitedOutput_withStateHC(const char* in, char* out, int inSize) { return LZ4_compressHC_limitedOutput_withStateHC(stateLZ4HC, in, out, inSize, LZ4_compressBound(inSize)); } -static inline int local_LZ4_compressHC_limitedOutput(const char* in, char* out, int inSize) +static int local_LZ4_compressHC_limitedOutput(const char* in, char* out, int inSize) { return LZ4_compressHC_limitedOutput(in, out, inSize, LZ4_compressBound(inSize)); } -static inline int local_LZ4_compressHC_continue(const char* in, char* out, int inSize) +static int local_LZ4_compressHC_continue(const char* in, char* out, int inSize) { return LZ4_compressHC_continue(ctx, in, out, inSize); } -static inline int local_LZ4_compressHC_limitedOutput_continue(const char* in, char* out, int inSize) +static int local_LZ4_compressHC_limitedOutput_continue(const char* in, char* out, int inSize) { return LZ4_compressHC_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize)); } -static inline int local_LZ4_decompress_fast(const char* in, char* out, int inSize, int outSize) +static int local_LZ4_decompress_fast(const char* in, char* out, int inSize, int outSize) { (void)inSize; LZ4_decompress_fast(in, out, outSize); return outSize; } -static inline int local_LZ4_decompress_fast_withPrefix64k(const char* in, char* out, int inSize, int outSize) +static int local_LZ4_decompress_fast_withPrefix64k(const char* in, char* out, int inSize, int outSize) { (void)inSize; LZ4_decompress_fast_withPrefix64k(in, out, outSize); return outSize; } -static inline int local_LZ4_decompress_fast_usingDict(const char* in, char* out, int inSize, int outSize) +static int local_LZ4_decompress_fast_usingDict(const char* in, char* out, int inSize, int outSize) { (void)inSize; LZ4_decompress_fast_usingDict(in, out, outSize, in - 65536, 65536); return outSize; } -static inline int local_LZ4_decompress_safe_usingDict(const char* in, char* out, int inSize, int outSize) +static int local_LZ4_decompress_safe_usingDict(const char* in, char* out, int inSize, int outSize) { (void)inSize; LZ4_decompress_safe_usingDict(in, out, inSize, outSize, in - 65536, 65536); return outSize; } -static inline int local_LZ4_decompress_safe_partial(const char* in, char* out, int inSize, int outSize) +static int local_LZ4_decompress_safe_partial(const char* in, char* out, int inSize, int outSize) { return LZ4_decompress_safe_partial(in, out, inSize, outSize - 5, outSize); } -- cgit v0.12 From 9ac680972a3c124e2e512f7202889c4d397c6f9b Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 20 May 2014 19:14:53 +0100 Subject: restored Travis Build Matrix --- programs/Makefile | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-) diff --git a/programs/Makefile b/programs/Makefile index a81a701..219684f 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -42,6 +42,18 @@ MANDIR=$(PREFIX)/share/man/man1 LZ4DIR=.. TEST_FILES = COPYING +TEST_TARGETS=test-64 test-32 +BENCH_NB=-i5 + +# Minimize test target for Travis CI's Build Matrix +ifeq ($(LZ4_TRAVIS_CI_ENV),-m32) +TEST_TARGETS=test-32 +BENCH_NB=-i1 +else ifeq ($(LZ4_TRAVIS_CI_ENV),-m64) +TEST_TARGETS=test-64 +BENCH_NB=-i1 +endif + # Define *.exe as extension for Windows systems ifneq (,$(filter Windows%,$(OS))) @@ -106,7 +118,11 @@ uninstall: [ -f $(DESTDIR)$(MANDIR)/lz4cat.1 ] && rm -f $(DESTDIR)$(MANDIR)/lz4cat.1 @echo lz4 successfully uninstalled -test: test-lz4 test-lz4c test-lz4c32 test-fullbench test-fullbench32 test-fuzzer test-fuzzer32 +test: $(TEST_TARGETS) + +test-64: test-lz4 test-lz4c test-fullbench test-fuzzer + +test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 test-lz4: @@ -115,10 +131,10 @@ test-lz4c: test-lz4c32: test-fullbench: fullbench - ./fullbench --no-prompt -i1 $(TEST_FILES) + ./fullbench --no-prompt $(BENCH_NB) $(TEST_FILES) test-fullbench32: fullbench32 - ./fullbench32 --no-prompt -i1 $(TEST_FILES) + ./fullbench32 --no-prompt $(BENCH_NB) $(TEST_FILES) test-fuzzer: fuzzer ./fuzzer --no-prompt -- cgit v0.12 From 8c38ddd7e67354aa3205ac8c03e5b8f78f567a48 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 20 May 2014 23:26:03 +0100 Subject: Introduce : LZ4_compress_limitedOutput_usingDict() --- lz4.c | 47 +++++++++++++++++++++++++++++------------------ lz4.h | 10 ++++++++-- programs/fullbench.c | 16 +++++++++++----- 3 files changed, 48 insertions(+), 25 deletions(-) diff --git a/lz4.c b/lz4.c index 9a28d68..f717ca9 100755 --- a/lz4.c +++ b/lz4.c @@ -250,7 +250,7 @@ typedef struct { U32 dictSize; } LZ4_dict_t_internal; -typedef enum { notLimited = 0, limited = 1 } limitedOutput_directive; +typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; typedef enum { byPtr, byU32, byU16 } tableType_t; typedef enum { noDict = 0, withPrefix64k = 1, usingDict = 2 } dict_directive; @@ -425,7 +425,7 @@ int LZ4_compress_generic( int inputSize, int maxOutputSize, - limitedOutput_directive limitedOutput, + limitedOutput_directive outputLimited, tableType_t tableType, dict_directive dict) { @@ -495,7 +495,7 @@ int LZ4_compress_generic( /* Encode Literal length */ unsigned litLength = (unsigned)(ip - anchor); token = op++; - if ((limitedOutput) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ + if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ if (litLength>=RUN_MASK) { int len = (int)litLength-RUN_MASK; @@ -519,7 +519,7 @@ _next_match: ip += matchLength + MINMATCH; if (matchLength>=ML_MASK) { - if ((limitedOutput) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ + if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ *token += ML_MASK; matchLength -= ML_MASK; for (; matchLength > 509 ; matchLength-=510) { *op++ = 255; *op++ = 255; } @@ -550,7 +550,7 @@ _last_literals: /* Encode Last Literals */ { int lastRun = (int)(iend - anchor); - if ((limitedOutput) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */ + 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<= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } else *op++ = (BYTE)(lastRun<dictSize; @@ -742,7 +742,7 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest unsigned litLength = (unsigned)(ip - anchor); token = op++; - if ((limitedOutput) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ + if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ if (litLength>=RUN_MASK) { unsigned remaininglength = litLength - RUN_MASK; @@ -775,7 +775,7 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest ip += matchLength + MINMATCH; if (matchLength>=ML_MASK) { - if ((limitedOutput) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ + if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ *token += ML_MASK; matchLength -= ML_MASK; for (; matchLength > 509 ; matchLength-=510) { *op++ = 255; *op++ = 255; } @@ -798,7 +798,7 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest /* Encode Last Literals */ { int lastRun = (int)(iend - anchor); - if ((limitedOutput) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */ + 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<= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } else *op++ = (BYTE)(lastRun< Date: Tue, 20 May 2014 23:36:27 +0100 Subject: Added : fuzzer code for LZ4_compress_limitedOutput_usingDict() --- programs/fuzzer.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-) diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 081f0df..4b19703 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -204,6 +204,7 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { void* stateLZ4 = malloc(LZ4_sizeofState()); void* stateLZ4HC = malloc(LZ4_sizeofStateHC()); void* LZ4continue; + LZ4_dict_t LZ4dict; U32 crcOrig, crcCheck; @@ -421,13 +422,22 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { FUZ_DISPLAYTEST; dict -= 9; if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; - { - LZ4_dict_t LZ4dict; - memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); - LZ4_loadDict(&LZ4dict, dict, dictSize); - blockContinueCompressedSize = LZ4_compress_usingDict(&LZ4dict, block, compressedBuffer, blockSize); - FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_usingDict failed"); - } + memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + LZ4_loadDict(&LZ4dict, dict, dictSize); + blockContinueCompressedSize = LZ4_compress_usingDict(&LZ4dict, block, compressedBuffer, blockSize); + FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_usingDict failed"); + + FUZ_DISPLAYTEST; + memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + LZ4_loadDict(&LZ4dict, dict, dictSize); + ret = LZ4_compress_limitedOutput_usingDict(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); + FUZ_CHECKTEST(ret>0, "LZ4_compress_limitedOutput_usingDict should fail : one missing byte for output buffer"); + + FUZ_DISPLAYTEST; + memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + LZ4_loadDict(&LZ4dict, dict, dictSize); + ret = LZ4_compress_limitedOutput_usingDict(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize); + FUZ_CHECKTEST(ret<=0, "LZ4_compress_limitedOutput_usingDict should work : enough size available within output buffer"); // Decompress with dictionary as external FUZ_DISPLAYTEST; -- cgit v0.12 From 4b43c2bd980a1582dc9dbf7fe7f0701c12cf5000 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 21 May 2014 19:46:36 +0100 Subject: Continuous streaming mode (automatic) --- Makefile | 2 +- lz4.c | 74 ++++++++++++++++++++++++++++++++++++++-------------- programs/fullbench.c | 9 ++++++- 3 files changed, 63 insertions(+), 22 deletions(-) diff --git a/Makefile b/Makefile index 11fa7b3..c80e02c 100644 --- a/Makefile +++ b/Makefile @@ -92,7 +92,7 @@ lz4programs: lz4.c lz4hc.c liblz4: lz4.c lz4hc.c @echo compiling static library @$(CC) $(CFLAGS) -c $^ - @ar rcs liblz4.a lz4.o lz4hc.o + @$(AR) rcs liblz4.a lz4.o lz4hc.o @echo compiling dynamic library @$(CC) $(CFLAGS) -shared $^ -fPIC $(SONAME_FLAGS) -o $@.$(SHARED_EXT_VER) @echo creating versioned links diff --git a/lz4.c b/lz4.c index f717ca9..00c2a64 100755 --- a/lz4.c +++ b/lz4.c @@ -418,7 +418,7 @@ static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimi } -int LZ4_compress_generic( +static int LZ4_compress_generic( void* ctx, const char* source, char* dest, @@ -638,10 +638,9 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* Experimental : Streaming functions *****************************************/ -void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const char* source) +void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict) { - if ((source - LZ4_dict->currentOffset > source) - || (LZ4_dict->currentOffset > 0x80000000)) + if (LZ4_dict->currentOffset > 0x80000000) { /* rescale hash table */ U32 delta = LZ4_dict->currentOffset - 64 KB; @@ -656,24 +655,20 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const char* source) } -static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, +static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize, - limitedOutput_directive outputLimited) + const limitedOutput_directive outputLimited, + const dict_directive dict) { LZ4_dict_t_internal* const streamPtr = (LZ4_dict_t_internal*)LZ4_dict; const tableType_t tableType = byU32; - U32 currentOffset; + const U32 currentOffset = streamPtr->currentOffset; const U32 dictSize = streamPtr->dictSize; const BYTE* const dictionary = streamPtr->dictionary; - if (streamPtr->initCheck) return 0; /* structure not initialized */ - - LZ4_renormDictT(streamPtr, source); - currentOffset = streamPtr->currentOffset; - streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += inputSize; + streamPtr->currentOffset += (U32)inputSize; { U32 ipIndex = currentOffset; @@ -721,7 +716,7 @@ static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, if (unlikely(ipIndex > indexLimit)) goto _last_literals; ip = base + ipIndex; - if (refIndex < currentOffset) + if ((dict==usingDict) && (refIndex < currentOffset)) { ref = dictBase + refIndex; lowLimit = dictionary; @@ -729,13 +724,13 @@ static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, else { ref = base + refIndex; - lowLimit = (const BYTE*)source; + if (dict==usingDict) lowLimit = (const BYTE*)source; } } while ((refIndex + MAX_DISTANCE < ipIndex) || (A32(ref) != A32(ip))); /* Catch up */ - while ((ip>anchor) && (ref>lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } + while ((ip>anchor) && ((dict==usingDict)?(ref>lowLimit):1) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } { /* Encode Literal length */ @@ -762,9 +757,7 @@ static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, /* Encode MatchLength */ { unsigned matchLength; - if (refIndex >= currentOffset) - matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); - else + if ((dict==usingDict) && (refIndex < currentOffset)) { const BYTE* dicLimit = ip + (dictEnd - ref); if (dicLimit > matchlimit) dicLimit = matchlimit; @@ -772,6 +765,10 @@ static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, if (ref + MINMATCH + matchLength == dictEnd) matchLength += LZ4_count(ip+MINMATCH+matchLength, (const BYTE*)source, matchlimit); } + else + { + matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); + } ip += matchLength + MINMATCH; if (matchLength>=ML_MASK) { @@ -811,6 +808,22 @@ static int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, } +static inline int LZ4_compress_usingDict_generic (LZ4_dict_t* LZ4_dict, + const char* source, char* dest, int inputSize, int maxOutputSize, + const limitedOutput_directive outputLimited) +{ + LZ4_dict_t_internal* const streamPtr = (LZ4_dict_t_internal*)LZ4_dict; + + if (streamPtr->initCheck) return 0; /* structure not initialized */ + LZ4_renormDictT(streamPtr); + + if ((streamPtr->dictionary + streamPtr->dictSize == (const BYTE*)source) && (streamPtr->dictSize >= 64 KB)) + return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, outputLimited, withPrefix64k); + else + return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, outputLimited, usingDict); +} + + int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, 0, notLimited); @@ -821,6 +834,12 @@ int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* sour return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput); } +// Debug function only, to measure performance differences +int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) +{ + return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, usingDict); +} + int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) { @@ -833,7 +852,22 @@ int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) } -int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) +int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize) +{ + LZ4_dict_t_internal* dict = (LZ4_dict_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->dictSize = (U32)dictSize; + + return 1; +} + + +int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) { LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; const BYTE* p = (const BYTE*)dictionary; diff --git a/programs/fullbench.c b/programs/fullbench.c index cc39b15..ef42c80 100755 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -300,6 +300,12 @@ static int local_LZ4_compress_limitedOutput_usingDict(const char* in, char* out, return LZ4_compress_limitedOutput_usingDict(&LZ4_dict, in, out, inSize, LZ4_compressBound(inSize)); } +int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); +static int local_LZ4_compress_forceDict(const char* in, char* out, int inSize) +{ + return LZ4_compress_forceDict(&LZ4_dict, in, out, inSize); +} + static void* stateLZ4HC; static int local_LZ4_compressHC_withStateHC(const char* in, char* out, int inSize) @@ -364,7 +370,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) { int fileIdx=0; char* orig_buff; -# define NB_COMPRESSION_ALGORITHMS 14 +# define NB_COMPRESSION_ALGORITHMS 15 # define MINCOMPRESSIONCHAR '0' # define MAXCOMPRESSIONCHAR (MINCOMPRESSIONCHAR + NB_COMPRESSION_ALGORITHMS) double totalCTime[NB_COMPRESSION_ALGORITHMS+1] = {0}; @@ -504,6 +510,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) case 12: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_limitedOutput_continue"; break; case 13: compressionFunction = local_LZ4_compress_usingDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_usingDict"; break; case 14: compressionFunction = local_LZ4_compress_limitedOutput_usingDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_limitedOutput_usingDict"; break; + case 15: compressionFunction = local_LZ4_compress_forceDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_forceDict"; break; default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; } -- cgit v0.12 From 971f61212292bab48ed5e9e5c7f69ece34380fcc Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Fri, 23 May 2014 21:01:55 +0100 Subject: speed optimization --- lz4.c | 31 +++++++++++++++++++++---------- 1 file changed, 21 insertions(+), 10 deletions(-) diff --git a/lz4.c b/lz4.c index 00c2a64..0d7f871 100755 --- a/lz4.c +++ b/lz4.c @@ -666,9 +666,17 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, const U32 dictSize = streamPtr->dictSize; const BYTE* const dictionary = streamPtr->dictionary; - streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; + if (dict == usingDict) + { + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + } + else + { + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + } { U32 ipIndex = currentOffset; @@ -697,19 +705,21 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, /* Main Loop */ for ( ; ; ) { - int searchMatchNb = (1U << skipStrength) - 1; + int searchMatchNb = (1U << skipStrength); const BYTE* ref; const BYTE* lowLimit; BYTE* token; U32 refIndex; - ipIndex = (U32)(ip - base); + U32 forwardH = LZ4_hashPosition(ip, tableType); + U32 forwardIpIndex = (U32)(ip - base); /* Find a match */ do { - U32 h; + U32 h = forwardH; + ipIndex = forwardIpIndex; + forwardIpIndex += searchMatchNb++ >> skipStrength; + forwardH = LZ4_hashPosition(base + forwardIpIndex, tableType); - ipIndex += searchMatchNb++ >> skipStrength; - h = LZ4_hashPosition(base + ipIndex, tableType); refIndex = streamPtr->hashTable[h]; streamPtr->hashTable[h] = ipIndex; @@ -767,7 +777,8 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, } else { - matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); + matchLength = base + ipIndex - ip; + matchLength += LZ4_count(base+ipIndex+MINMATCH, base+refIndex+MINMATCH, matchlimit); } ip += matchLength + MINMATCH; if (matchLength>=ML_MASK) @@ -834,7 +845,7 @@ int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* sour return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput); } -// Debug function only, to measure performance differences +// Hidden debug function, to force separate dictionary mode int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, usingDict); -- cgit v0.12 From 302e7e2f2bddc4a9d1ff108c0d9a5079a11b6ed0 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 27 May 2014 02:41:29 +0100 Subject: coalesced streaming compression code + speed optimization --- lz4.c | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 122 insertions(+), 10 deletions(-) diff --git a/lz4.c b/lz4.c index 0d7f871..da3bc49 100755 --- a/lz4.c +++ b/lz4.c @@ -429,9 +429,14 @@ static int LZ4_compress_generic( tableType_t tableType, dict_directive dict) { + LZ4_dict_t_internal* const dictPtr = (LZ4_dict_t_internal*)ctx; + const BYTE* ip = (const BYTE*) source; const BYTE* base; - const BYTE* const lowLimit = ((dict==withPrefix64k) ? ((LZ4_Data_Structure*)ctx)->bufferStart : (const BYTE*)source); + const BYTE* lowLimit; + 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; @@ -442,6 +447,7 @@ static int LZ4_compress_generic( const int skipStrength = SKIPSTRENGTH; U32 forwardH; + U16 delta=0; /* Init conditions */ //if (tableType==byPtr) tableType=byU32; @@ -450,14 +456,19 @@ static int LZ4_compress_generic( { case noDict: default: - base = (const BYTE*)source; break; + base = (const BYTE*)source; + lowLimit = (const BYTE*)source; + break; case withPrefix64k: base =((LZ4_Data_Structure*)ctx)->base; + lowLimit = ((LZ4_Data_Structure*)ctx)->bufferStart; if (ip != ((LZ4_Data_Structure*)ctx)->nextBlock) return 0; /* must continue from end of previous block */ ((LZ4_Data_Structure*)ctx)->nextBlock = iend; /* do it now, due to potential early exit */ break; case usingDict: - base = (const BYTE*)source - ((LZ4_dict_t_internal*)ctx)->currentOffset; break; + 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= mflimit)) goto _last_literals; + if (dict==usingDict) + { + delta = (U16)(ip-ref); + if (ref<(const BYTE*)source) + { + ref += dictDelta; + lowLimit = dictionary; + } + else lowLimit = (const BYTE*)source; + } + if (unlikely(ip > mflimit)) goto _last_literals; forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx, tableType, base); @@ -511,12 +532,32 @@ static int LZ4_compress_generic( _next_match: /* Encode Offset */ - LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); + if (dict==usingDict) LZ4_WRITE_LITTLEENDIAN_16(op, delta) + else LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); /* Encode MatchLength */ { - unsigned matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); - ip += matchLength + MINMATCH; + unsigned matchLength; + + if ((dict==usingDict) && (lowLimit==dictionary)) + { + const BYTE* 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) > oend))) return 0; /* Check output limit */ @@ -539,6 +580,16 @@ _next_match: /* Test next position */ ref = LZ4_getPosition(ip, ctx, tableType, base); + if (dict==usingDict) + { + delta = (U16)(ip-ref); + if (ref<(const BYTE*)source) + { + ref += dictDelta; + lowLimit = dictionary; + } + else lowLimit = (const BYTE*)source; + } LZ4_putPosition(ip, ctx, tableType, base); if ((ref + MAX_DISTANCE >= ip) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } @@ -689,6 +740,7 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, const BYTE* const mflimit = iend - MFLIMIT; const U32 indexLimit = ipIndex + inputSize - MFLIMIT; const BYTE* const matchlimit = iend - LASTLITERALS; + U32 forwardH; BYTE* op = (BYTE*) dest; BYTE* const oend = op + maxOutputSize; @@ -701,6 +753,7 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, /* First Byte */ if (ipIndex==0) ip++; + forwardH = LZ4_hashPosition(ip, tableType); /* Main Loop */ for ( ; ; ) @@ -710,7 +763,6 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, const BYTE* lowLimit; BYTE* token; U32 refIndex; - U32 forwardH = LZ4_hashPosition(ip, tableType); U32 forwardIpIndex = (U32)(ip - base); /* Find a match */ @@ -740,7 +792,7 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, } while ((refIndex + MAX_DISTANCE < ipIndex) || (A32(ref) != A32(ip))); /* Catch up */ - while ((ip>anchor) && ((dict==usingDict)?(ref>lowLimit):1) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } + while (((dict==usingDict)?(ref>lowLimit):1) && (ip>anchor) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } { /* Encode Literal length */ @@ -761,8 +813,9 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, { BYTE* end=op+litLength; LZ4_WILDCOPY(op,anchor,end); op=end; } } +_next_match: /* Encode Offset */ - LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ipIndex-refIndex)); + LZ4_WRITE_LITTLEENDIAN_16(op, (U16)(ipIndex-refIndex)); /* Encode MatchLength */ { @@ -800,6 +853,26 @@ static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, /* Fill table */ LZ4_putPosition(ip-2, streamPtr->hashTable, tableType, base); + + /* Test next position */ + ref = LZ4_getPosition(ip, streamPtr, tableType, base); + if ((dict==usingDict) && (ref= ip) + { + if ((dict==usingDict) && (refdictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + /* + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + */ + return result; +#endif } int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) { +#if 0 return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput); +#else + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingDict); + + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + /* + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + */ + return result; +#endif } // Hidden debug function, to force separate dictionary mode int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { +#if 0 return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, usingDict); +#else + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingDict); + + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + + return result; +#endif } -- cgit v0.12 From b636779b0e168c346b42e85af816ce37a8ed9880 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 2 Jun 2014 07:07:19 +0100 Subject: unified structure model --- lz4.c | 388 +++++++++++---------------------------------------- lz4.h | 28 ++-- programs/fullbench.c | 4 +- programs/fuzzer.c | 11 +- 4 files changed, 105 insertions(+), 326 deletions(-) diff --git a/lz4.c b/lz4.c index da3bc49..ec0f1b0 100755 --- a/lz4.c +++ b/lz4.c @@ -236,13 +236,6 @@ static const int LZ4_minLength = (MFLIMIT+1); Structures and local types **************************************/ typedef struct { - U32 hashTable[HASH_SIZE_U32]; - const BYTE* bufferStart; - const BYTE* base; - const BYTE* nextBlock; -} LZ4_Data_Structure; - -typedef struct { U32 hashTable[HASH_SIZE_U32]; U32 currentOffset; U32 initCheck; @@ -250,10 +243,15 @@ typedef struct { U32 dictSize; } LZ4_dict_t_internal; +typedef struct { + LZ4_dict_t_internal dict; + const BYTE* bufferStart; +} LZ4_Data_Structure; + typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; typedef enum { byPtr, byU32, byU16 } tableType_t; -typedef enum { noDict = 0, withPrefix64k = 1, usingDict = 2 } dict_directive; +typedef enum { noDict = 0, withPrefix64k = 1, usingExtDict = 2 } dict_directive; typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; typedef enum { full = 0, partial = 1 } earlyEnd_directive; @@ -450,7 +448,6 @@ static int LZ4_compress_generic( U16 delta=0; /* Init conditions */ - //if (tableType==byPtr) tableType=byU32; if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ switch(dict) { @@ -460,12 +457,11 @@ static int LZ4_compress_generic( lowLimit = (const BYTE*)source; break; case withPrefix64k: - base =((LZ4_Data_Structure*)ctx)->base; - lowLimit = ((LZ4_Data_Structure*)ctx)->bufferStart; - if (ip != ((LZ4_Data_Structure*)ctx)->nextBlock) return 0; /* must continue from end of previous block */ - ((LZ4_Data_Structure*)ctx)->nextBlock = iend; /* do it now, due to potential early exit */ + base = (const BYTE*)source - dictPtr->currentOffset; + lowLimit = (const BYTE*)source - 64 KB; + if (lowLimit < base) lowLimit = base; break; - case usingDict: + case usingExtDict: base = (const BYTE*)source - dictPtr->currentOffset; lowLimit = (const BYTE*)source; break; @@ -493,7 +489,7 @@ static int LZ4_compress_generic( forwardIp += step; ref = LZ4_getPositionOnHash(h, ctx, tableType, base); - if (dict==usingDict) + if (dict==usingExtDict) { delta = (U16)(ip-ref); if (ref<(const BYTE*)source) @@ -532,14 +528,14 @@ static int LZ4_compress_generic( _next_match: /* Encode Offset */ - if (dict==usingDict) LZ4_WRITE_LITTLEENDIAN_16(op, delta) + if (dict==usingExtDict) LZ4_WRITE_LITTLEENDIAN_16(op, delta) else LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); /* Encode MatchLength */ { unsigned matchLength; - if ((dict==usingDict) && (lowLimit==dictionary)) + if ((dict==usingExtDict) && (lowLimit==dictionary)) { const BYTE* limit = ip + (dictEnd-ref); if (limit > matchlimit) limit = matchlimit; @@ -580,7 +576,7 @@ _next_match: /* Test next position */ ref = LZ4_getPosition(ip, ctx, tableType, base); - if (dict==usingDict) + if (dict==usingExtDict) { delta = (U16)(ip-ref); if (ref<(const BYTE*)source) @@ -689,6 +685,39 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* Experimental : Streaming functions *****************************************/ +int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) +{ + LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; + const BYTE* p = (const BYTE*)dictionary; + const BYTE* const dictEnd = p + dictSize; + const BYTE* base; + + LZ4_STATIC_ASSERT(LZ4_DICTSIZE >= sizeof(LZ4_dict_t_internal)); /* A compilation error here means LZ4_DICTSIZE is not large enough */ + if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_dict_t_internal)); + + if (dictSize < MINMATCH) + { + dict->dictionary = (const BYTE*)dictionary-1; + 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_dict_t_internal* LZ4_dict) { if (LZ4_dict->currentOffset > 0x80000000) @@ -706,215 +735,10 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict) } -static inline int LZ4_compress_2_generic (LZ4_dict_t* LZ4_dict, - const char* source, char* dest, int inputSize, int maxOutputSize, - const limitedOutput_directive outputLimited, - const dict_directive dict) -{ - LZ4_dict_t_internal* const streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - const tableType_t tableType = byU32; - const U32 currentOffset = streamPtr->currentOffset; - const U32 dictSize = streamPtr->dictSize; - const BYTE* const dictionary = streamPtr->dictionary; - - if (dict == usingDict) - { - streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - } - else - { - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - } - - { - U32 ipIndex = currentOffset; - const BYTE* ip = (const BYTE*) source; - const BYTE* anchor = (const BYTE*) source; - const BYTE* const iend = ip + inputSize; - const BYTE* const base = (const BYTE*)source - currentOffset; - const BYTE* const dictEnd = dictionary + dictSize; - const BYTE* const dictBase = dictEnd - currentOffset; - const BYTE* const mflimit = iend - MFLIMIT; - const U32 indexLimit = ipIndex + inputSize - MFLIMIT; - const BYTE* const matchlimit = iend - LASTLITERALS; - U32 forwardH; - - BYTE* op = (BYTE*) dest; - BYTE* const oend = op + maxOutputSize; - - const int skipStrength = SKIPSTRENGTH; - - /* Init conditions */ - if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ - if (inputSize> skipStrength; - forwardH = LZ4_hashPosition(base + forwardIpIndex, tableType); - - refIndex = streamPtr->hashTable[h]; - streamPtr->hashTable[h] = ipIndex; - - if (unlikely(ipIndex > indexLimit)) goto _last_literals; - - ip = base + ipIndex; - if ((dict==usingDict) && (refIndex < currentOffset)) - { - ref = dictBase + refIndex; - lowLimit = dictionary; - } - else - { - ref = base + refIndex; - if (dict==usingDict) lowLimit = (const BYTE*)source; - } - - } while ((refIndex + MAX_DISTANCE < ipIndex) || (A32(ref) != A32(ip))); - - /* Catch up */ - while (((dict==usingDict)?(ref>lowLimit):1) && (ip>anchor) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } - - { - /* Encode Literal length */ - unsigned litLength = (unsigned)(ip - anchor); - - token = op++; - if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ - if (litLength>=RUN_MASK) - { - unsigned remaininglength = litLength - RUN_MASK; - *token=(RUN_MASK<= 255 ; remaininglength-=255) *op++ = 255; - *op++ = (BYTE)remaininglength; - } - 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)(ipIndex-refIndex)); - - /* Encode MatchLength */ - { - unsigned matchLength; - if ((dict==usingDict) && (refIndex < currentOffset)) - { - const BYTE* dicLimit = ip + (dictEnd - ref); - if (dicLimit > matchlimit) dicLimit = matchlimit; - matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, dicLimit); - if (ref + MINMATCH + matchLength == dictEnd) - matchLength += LZ4_count(ip+MINMATCH+matchLength, (const BYTE*)source, matchlimit); - } - else - { - matchLength = base + ipIndex - ip; - matchLength += LZ4_count(base+ipIndex+MINMATCH, base+refIndex+MINMATCH, matchlimit); - } - ip += matchLength + MINMATCH; - if (matchLength>=ML_MASK) - { - if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ - *token += ML_MASK; - matchLength -= ML_MASK; - for (; matchLength > 509 ; 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, streamPtr->hashTable, tableType, base); - - /* Test next position */ - ref = LZ4_getPosition(ip, streamPtr, tableType, base); - if ((dict==usingDict) && (ref= ip) - { - if ((dict==usingDict) && (ref (U32)maxOutputSize)) return 0; /* Check output limit */ - if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } - else *op++ = (BYTE)(lastRun<initCheck) return 0; /* structure not initialized */ - LZ4_renormDictT(streamPtr); - - if ((streamPtr->dictionary + streamPtr->dictSize == (const BYTE*)source) && (streamPtr->dictSize >= 64 KB)) - return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, outputLimited, withPrefix64k); - else - return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, outputLimited, usingDict); -} - - int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { -#if 0 - return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, 0, notLimited); -#else LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingDict); + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; @@ -924,16 +748,12 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest streamPtr->currentOffset += (U32)inputSize; */ return result; -#endif } int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) { -#if 0 - return LZ4_compress_usingDict_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput); -#else LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingDict); + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; @@ -943,35 +763,19 @@ int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* sour streamPtr->currentOffset += (U32)inputSize; */ return result; -#endif } // Hidden debug function, to force separate dictionary mode -int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) +int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { -#if 0 - return LZ4_compress_2_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, usingDict); -#else LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingDict); + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; streamPtr->currentOffset += (U32)inputSize; return result; -#endif -} - - -int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) -{ - LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; - - dict->dictionary = (const BYTE*)dictionary; - dict->dictSize = (U32)dictSize; - if (dict->currentOffset < dict->dictSize) return 0; - return 1; } @@ -984,34 +788,11 @@ int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize) if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize; memcpy(safeBuffer, previousDictEnd - dictSize, dictSize); - dict->dictSize = (U32)dictSize; - - return 1; -} - -int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) -{ - LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; - const BYTE* p = (const BYTE*)dictionary; - const BYTE* const dictEnd = p + dictSize; - const BYTE* base; - - LZ4_STATIC_ASSERT(LZ4_DICTSIZE >= sizeof(LZ4_dict_t_internal)); /* A compilation error here means LZ4_DICTSIZE is not large enough */ - if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_dict_t_internal)); + dict->dictionary = (const BYTE*)safeBuffer; + dict->dictSize = (U32)dictSize; - if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB; - if (dictSize < MINMATCH) p = dictEnd; - 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; - } + LZ4_renormDictT(dict); return 1; } @@ -1036,9 +817,9 @@ int LZ4_decompress_generic( int endOnInput, /* endOnOutputSize, endOnInputSize */ int partialDecoding, /* full, partial */ int targetOutputSize, /* only used if partialDecoding==partial */ - int dict, /* noDict, withPrefix64k, withExtDict */ - const char* dictStart, /* only if dict==withExtDict */ - int dictSize /* only if dict==withExtDict */ + int dict, /* noDict, withPrefix64k, usingExtDict */ + const char* dictStart, /* only if dict==usingExtDict */ + int dictSize /* only if dict==usingExtDict */ ) { /* Local Variables */ @@ -1051,7 +832,7 @@ int LZ4_decompress_generic( BYTE* cpy; BYTE* oexit = op + targetOutputSize; - const BYTE* const dictEnd = (dict==usingDict) ? (const BYTE*)dictStart + dictSize : NULL; + const BYTE* const dictEnd = (dict==usingExtDict) ? (const BYTE*)dictStart + dictSize : NULL; const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */ static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; @@ -1125,7 +906,7 @@ int LZ4_decompress_generic( } /* check external dictionary */ - if ((dict==usingDict) && (unlikely(ref < (BYTE* const)dest))) + if ((dict==usingExtDict) && (ref < (BYTE* const)dest)) { if (unlikely(op+length+MINMATCH > oend-LASTLITERALS)) goto _output_error; @@ -1206,7 +987,7 @@ int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compre 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, usingDict, dictStart, dictSize); + return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, dictStart, dictSize); } int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize) @@ -1230,7 +1011,7 @@ int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int origin 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, usingDict, dictStart, dictSize); + return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, dictStart, dictSize); } @@ -1253,10 +1034,8 @@ int LZ4_sizeofStreamState() void LZ4_init(LZ4_Data_Structure* lz4ds, const BYTE* base) { - MEM_INIT(lz4ds->hashTable, 0, sizeof(lz4ds->hashTable)); + MEM_INIT(lz4ds->dict.hashTable, 0, sizeof(lz4ds->dict.hashTable)); lz4ds->bufferStart = base; - lz4ds->base = base; - lz4ds->nextBlock = base; } int LZ4_resetStreamState(void* state, const char* inputBuffer) @@ -1283,40 +1062,33 @@ int LZ4_free (void* LZ4_Data) char* LZ4_slideInputBuffer (void* LZ4_Data) { LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data; - size_t delta = lz4ds->nextBlock - (lz4ds->bufferStart + 64 KB); - - if ( (lz4ds->base - delta > lz4ds->base) /* underflow control */ - || ((size_t)(lz4ds->nextBlock - lz4ds->base) > 0xE0000000) ) /* close to 32-bits limit */ - { - size_t deltaLimit = (lz4ds->nextBlock - 64 KB) - lz4ds->base; - int nH; - for (nH=0; nH < HASH_SIZE_U32; nH++) - { - if ((size_t)(lz4ds->hashTable[nH]) < deltaLimit) lz4ds->hashTable[nH] = 0; - else lz4ds->hashTable[nH] -= (U32)deltaLimit; - } - memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); - lz4ds->base = lz4ds->bufferStart; - lz4ds->nextBlock = lz4ds->base + 64 KB; - } - else - { - memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB); - lz4ds->nextBlock -= delta; - lz4ds->base -= delta; - } + LZ4_moveDict((LZ4_dict_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB); - return (char*)(lz4ds->nextBlock); + return (char*)(lz4ds->bufferStart + 64 KB); } int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize) { - return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; + int result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + + if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + + return result; } int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize) { - return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; + int result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); + + if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + + return result; } diff --git a/lz4.h b/lz4.h index b18599f..8a7db0c 100644 --- a/lz4.h +++ b/lz4.h @@ -175,11 +175,19 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* /* * LZ4_dict_t * information structure to track an LZ4 stream - * set it to zero (memset()) before first use/ + * use LZ4_loadDict() (or set it to zero) to init it before first use. */ typedef struct { unsigned int table[LZ4_DICTSIZE_U32]; } LZ4_dict_t; /* + * LZ4_loadDict + * Use this function to load a static dictionary into LZ4_dict. + * You can load a size of 0 to init an LZ4_dict_t structure + * Return : 1 if OK, 0 if error + */ +int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); + +/* * LZ4_compress_usingDict * Compress data block 'source', using blocks compressed before to improve compression ratio * Previous data blocks are assumed to still be present at their previous location. @@ -194,21 +202,13 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize); /* - * LZ4_setDictPos - * If previous data blocks cannot be guaranteed to remain at their previous location in memory - * save them into a safe place, and - * use this function to indicate where to find them. - * Return : 1 if OK, 0 if error - */ -int LZ4_setDictPos (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); - -/* - * LZ4_loadDict - * Use this function to load a static dictionary into LZ4_dict. - * It will be used to improve compression of next chained block. + * LZ4_moveDict + * If previous data block cannot be guaranteed to remain at its previous location in memory + * save it into a safe place (char* safeBuffer) + * before calling again LZ4_compress_usingDict() * Return : 1 if OK, 0 if error */ -int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); +int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize); /* diff --git a/programs/fullbench.c b/programs/fullbench.c index ef42c80..ae33330 100755 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -300,10 +300,10 @@ static int local_LZ4_compress_limitedOutput_usingDict(const char* in, char* out, return LZ4_compress_limitedOutput_usingDict(&LZ4_dict, in, out, inSize, LZ4_compressBound(inSize)); } -int LZ4_compress_forceDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); +int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); static int local_LZ4_compress_forceDict(const char* in, char* out, int inSize) { - return LZ4_compress_forceDict(&LZ4_dict, in, out, inSize); + return LZ4_compress_forceExtDict(&LZ4_dict, in, out, inSize); } diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 4b19703..56208d3 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -410,7 +410,14 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { ret = LZ4_decompress_fast_withPrefix64k(compressedBuffer, decodedBuffer+dictSize, blockSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_withPrefix64k did not read all compressed block input"); crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_withPrefix64k corrupted decoded data"); + if (crcCheck!=crcOrig) + { + int i=0; + while (block[i]==decodedBuffer[i]) i++; + printf("Wrong Byte at position %i/%i\n", i, blockSize); + + } + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_withPrefix64k corrupted decoded data (dict %i)", dictSize); FUZ_DISPLAYTEST; ret = LZ4_decompress_safe_withPrefix64k(compressedBuffer, decodedBuffer+dictSize, blockContinueCompressedSize, blockSize); @@ -453,7 +460,7 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { printf("Wrong Byte at position %i/%i\n", i, blockSize); } - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data"); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); FUZ_DISPLAYTEST; decodedBuffer[blockSize] = 0; -- cgit v0.12 From ec717699c7841b4471ee6566d80f4835ace8438b Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 2 Jun 2014 08:13:16 +0100 Subject: restored continuous streaming mode --- lz4.c | 51 +++++++++++++++++++++++++++++++++------------------ 1 file changed, 33 insertions(+), 18 deletions(-) diff --git a/lz4.c b/lz4.c index ec0f1b0..4c84e92 100755 --- a/lz4.c +++ b/lz4.c @@ -738,33 +738,48 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict) int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); + const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - /* - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - */ - return result; + if (dictEnd == (const BYTE*)source) + { + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } + + { + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } } int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict); + const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - /* - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - */ - return result; + if (dictEnd == (const BYTE*)source) + { + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } + + { + int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict); + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } } + // Hidden debug function, to force separate dictionary mode int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { -- cgit v0.12 From 1e053a290ab55af5d03eae209e9ee64f555670b7 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 3 Jun 2014 23:44:49 +0100 Subject: new test tool : datagen --- programs/Makefile | 29 ++++-- programs/datagen.c | 253 +++++++++++++++++++++++++++++++++++++++++++++++++++ programs/fullbench.c | 2 +- 3 files changed, 275 insertions(+), 9 deletions(-) create mode 100644 programs/datagen.c diff --git a/programs/Makefile b/programs/Makefile index 219684f..522850e 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -58,14 +58,16 @@ endif # Define *.exe as extension for Windows systems ifneq (,$(filter Windows%,$(OS))) EXT =.exe +VOID = nul else EXT = +VOID = /dev/null endif default: lz4 lz4c -all: lz4 lz4c lz4c32 fuzzer fuzzer32 fullbench fullbench32 +all: lz4 lz4c lz4c32 fullbench fullbench32 fuzzer fuzzer32 datagen lz4: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c $(CC) $(FLAGS) -DDISABLE_LZ4C_LEGACY_OPTIONS $^ -o $@$(EXT) @@ -76,22 +78,27 @@ lz4c : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c lz4c32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) +fullbench : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c + $(CC) $(FLAGS) $^ -o $@$(EXT) + +fullbench32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c + $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) + fuzzer : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fuzzer.c $(CC) $(FLAGS) $^ -o $@$(EXT) fuzzer32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fuzzer.c $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) -fullbench : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c +datagen : datagen.c $(CC) $(FLAGS) $^ -o $@$(EXT) -fullbench32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c - $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) clean: @rm -f core *.o \ lz4$(EXT) lz4c$(EXT) lz4c32$(EXT) \ - fuzzer$(EXT) fuzzer32$(EXT) fullbench$(EXT) fullbench32$(EXT) + fullbench$(EXT) fullbench32$(EXT) \ + fuzzer$(EXT) fuzzer32$(EXT) datagen$(EXT) @echo Cleaning completed @@ -124,11 +131,17 @@ test-64: test-lz4 test-lz4c test-fullbench test-fuzzer test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 -test-lz4: +test-lz4: lz4 datagen + ./datagen | ./lz4 | ./lz4 -vdq > $(VOID) + ./datagen -g256MB | ./lz4 -B4D | ./lz4 -vdq > $(VOID) + ./datagen -g6GB | ./lz4 -vqBD | ./lz4 -vdq > $(VOID) -test-lz4c: +test-lz4c: lz4c datagen -test-lz4c32: +test-lz4c32: lz4c32 datagen + ./datagen | ./lz4c32 | ./lz4c32 -vdq > $(VOID) + ./datagen -g256MB | ./lz4c32 -B4D | ./lz4c32 -vdq > $(VOID) + ./datagen -g6GB | ./lz4c32 -vqBD | ./lz4c32 -vdq > $(VOID) test-fullbench: fullbench ./fullbench --no-prompt $(BENCH_NB) $(TEST_FILES) diff --git a/programs/datagen.c b/programs/datagen.c new file mode 100644 index 0000000..05eb7f0 --- /dev/null +++ b/programs/datagen.c @@ -0,0 +1,253 @@ +/* + datagen.c - compressible data generator test tool + Copyright (C) Yann Collet 2012-2014 + GPL v2 License + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + + You can contact the author at : + - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html + - LZ4 source repository : http://code.google.com/p/lz4/ +*/ + +/************************************** + Remove Visual warning messages +**************************************/ +#define _CRT_SECURE_NO_WARNINGS // fgets + + +/************************************** + Includes +**************************************/ +//#include +#include // fgets, sscanf +#include // strcmp + + +/************************************** + Basic Types +**************************************/ +#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ +# include + 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 + + +/************************************** + Constants +**************************************/ +#ifndef LZ4_VERSION +# define LZ4_VERSION "rc118" +#endif + +#define KB *(1U<<10) +#define MB *(1U<<20) +#define GB *(1U<<30) + +#define CDG_SIZE_DEFAULT (64 KB) +#define CDG_SEED_DEFAULT 0 +#define CDG_COMPRESSIBILITY_DEFAULT 50 +#define PRIME1 2654435761U +#define PRIME2 2246822519U + + +/************************************** + Macros +**************************************/ +#define DISPLAY(...) fprintf(stderr, __VA_ARGS__) +#define DISPLAYLEVEL(l, ...) if (displayLevel>=l) { DISPLAY(__VA_ARGS__); } + + +/************************************** + Local Parameters +**************************************/ +static int no_prompt = 0; +static char* programName; +static int displayLevel = 2; + + +/********************************************************* + Fuzzer functions +*********************************************************/ + +#define CDG_rotl32(x,r) ((x << r) | (x >> (32 - r))) +static unsigned int CDG_rand(U32* src) +{ + U32 rand32 = *src; + rand32 *= PRIME1; + rand32 += PRIME2; + rand32 = CDG_rotl32(rand32, 13); + *src = rand32; + return rand32; +} + + +#define CDG_RAND15BITS ((CDG_rand(seed) >> 3) & 32767) +#define CDG_RANDLENGTH ( ((CDG_rand(seed) >> 7) & 3) ? (CDG_rand(seed) % 14) : (CDG_rand(seed) & 511) + 15) +#define CDG_RANDCHAR (((CDG_rand(seed) >> 9) & 63) + '0') +static void CDG_generate(U64 size, U32* seed, double proba) +{ + BYTE buff[128 KB + 1]; + U64 total=0; + U32 P32 = (U32)(32768 * proba); + U32 pos=0; + U32 genBlockSize = 128 KB; + + while (total < size) + { + if (size-total < 128 KB) genBlockSize = (U32)(size-total); + total += genBlockSize; + buff[genBlockSize] = 0; + *buff = CDG_RANDCHAR; + pos = 1; + while (pos pos) offset = pos; + if (pos + length > 128 KB ) length = 128 KB - pos; + ref = pos - offset; + d = pos + length; + while (pos < d) buff[pos++] = buff[ref++]; + } + else + { + // Literal (noise) + U32 d; + int length = CDG_RANDLENGTH; + if (pos + length > 128 KB) length = 128 KB - pos; + d = pos + length; + while (pos < d) buff[pos++] = CDG_RANDCHAR; + } + } + pos=0; + for (;pos+512<=genBlockSize;pos+=512) printf("%512.512s", buff+pos); + for (;pos='0') && (*argument<='9')) + { + size *= 10; + size += *argument - '0'; + argument++; + } + if (*argument=='K') { size <<= 10; argument++; } + if (*argument=='M') { size <<= 20; argument++; } + if (*argument=='G') { size <<= 30; argument++; } + if (*argument=='B') { argument++; } + break; + case 's': + argument++; + seed=0; + while ((*argument>='0') && (*argument<='9')) + { + seed *= 10; + seed += *argument - '0'; + argument++; + } + break; + case 'p': + argument++; + proba=0; + while ((*argument>='0') && (*argument<='9')) + { + proba *= 10; + proba += *argument - '0'; + argument++; + } + if (proba<0) proba=0; + if (proba>100) proba=100; + break; + case 'v': + displayLevel = 4; + break; + default: ; + } + } + + } + } + + // Get Seed + DISPLAYLEVEL(4, "Data Generator %s \n", LZ4_VERSION); + DISPLAYLEVEL(3, "Seed = %u \n", seed); + if (proba!=CDG_COMPRESSIBILITY_DEFAULT) DISPLAYLEVEL(3, "Compressibility : %i%%\n", proba); + + CDG_generate(size, &seed, ((double)proba) / 100); + + return 0; +} diff --git a/programs/fullbench.c b/programs/fullbench.c index ae33330..7249387 100755 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -581,7 +581,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) case 4: decompressionFunction = LZ4_decompress_safe_withPrefix64k; break; case 5: decompressionFunction = local_LZ4_decompress_safe_usingDict; break; case 6: decompressionFunction = local_LZ4_decompress_safe_partial; break; - default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; + default : DISPLAY("ERROR ! Bad decompression algorithm Id !! \n"); free(chunkP); return 1; } for (loopNb = 1; loopNb <= nbIterations; loopNb++) -- cgit v0.12 From 140e6e72ddb6fc5f7cd28ce0c8ec3812ef4a9c08 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 4 Jun 2014 22:34:48 +0100 Subject: Corrected : address space overflow in 32-bits mode --- lz4.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/lz4.c b/lz4.c index 4c84e92..0f1ee7a 100755 --- a/lz4.c +++ b/lz4.c @@ -718,9 +718,10 @@ int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) } -void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict) +void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const BYTE* src) { - if (LZ4_dict->currentOffset > 0x80000000) + if ((LZ4_dict->currentOffset > 0x80000000) || + (src - LZ4_dict->currentOffset > src)) /* address space overflow */ { /* rescale hash table */ U32 delta = LZ4_dict->currentOffset - 64 KB; @@ -731,6 +732,7 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict) else LZ4_dict->hashTable[i] -= delta; } LZ4_dict->currentOffset = 64 KB; + LZ4_dict->dictionary = src - 64 KB; } } @@ -807,7 +809,7 @@ int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize) dict->dictionary = (const BYTE*)safeBuffer; dict->dictSize = (U32)dictSize; - LZ4_renormDictT(dict); + LZ4_renormDictT(dict, (const BYTE*)safeBuffer); return 1; } @@ -1087,7 +1089,10 @@ char* LZ4_slideInputBuffer (void* LZ4_Data) int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; - int result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + int result; + + LZ4_renormDictT(streamPtr, (const BYTE*) source); + result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize += (U32)inputSize; @@ -1099,7 +1104,10 @@ int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int i int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; - int result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); + int result; + + LZ4_renormDictT(streamPtr, (const BYTE*) source); + result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize += (U32)inputSize; -- cgit v0.12 From c4f5b9de2a6483e4a2c962e2c7a0037fe42aee59 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Thu, 5 Jun 2014 01:59:19 +0100 Subject: Fixed (continued) : address space overflow in 32-bits mode --- lz4.c | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/lz4.c b/lz4.c index 0f1ee7a..cb5c3db 100755 --- a/lz4.c +++ b/lz4.c @@ -742,6 +742,10 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; + const BYTE* smallest = dictEnd; + if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; + LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_dict, smallest); + if (dictEnd == (const BYTE*)source) { int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); @@ -764,6 +768,10 @@ int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* sour LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; + const BYTE* smallest = dictEnd; + if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; + LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_dict, smallest); + if (dictEnd == (const BYTE*)source) { int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); -- cgit v0.12 From a79180f51dd2dbafca11588008116d288eca11f5 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 9 Jun 2014 01:01:04 +0100 Subject: New : valgrind memtest --- .travis.yml | 1 + Makefile | 10 ++-- lz4.c | 160 ++++++++++++++++++++++++++++++++++-------------------- lz4.h | 32 +++++++---- programs/Makefile | 15 +++-- programs/lz4cli.c | 2 +- programs/lz4io.c | 55 ++++++++----------- 7 files changed, 163 insertions(+), 112 deletions(-) diff --git a/.travis.yml b/.travis.yml index 2880427..472ca18 100644 --- a/.travis.yml +++ b/.travis.yml @@ -4,6 +4,7 @@ script: make test before_install: - sudo apt-get update -qq - sudo apt-get install -qq gcc-multilib + - sudo apt-get install -qq valgrind env: - LZ4_TRAVIS_CI_ENV=-m32 diff --git a/Makefile b/Makefile index c80e02c..ede6844 100644 --- a/Makefile +++ b/Makefile @@ -105,25 +105,25 @@ clean: @echo Cleaning completed -#make install option is reserved to Linux & OSX targets +#make install option is designed for Linux & OSX targets only ifneq (,$(filter $(shell uname),Linux Darwin)) install: liblz4 @install -d -m 755 $(DESTDIR)$(LIBDIR)/ $(DESTDIR)$(INCLUDEDIR)/ - @install -m 755 liblz4.a $(DESTDIR)$(LIBDIR)/liblz4.a @install -m 755 liblz4.$(SHARED_EXT_VER) $(DESTDIR)$(LIBDIR)/liblz4.$(SHARED_EXT_VER) @cp -a liblz4.$(SHARED_EXT_MAJOR) $(DESTDIR)$(LIBDIR) @cp -a liblz4.$(SHARED_EXT) $(DESTDIR)$(LIBDIR) - @install -m 755 lz4.h $(DESTDIR)$(INCLUDEDIR)/lz4.h - @install -m 755 lz4hc.h $(DESTDIR)$(INCLUDEDIR)/lz4hc.h + @install -m 644 liblz4.a $(DESTDIR)$(LIBDIR)/liblz4.a + @install -m 644 lz4.h $(DESTDIR)$(INCLUDEDIR)/lz4.h + @install -m 644 lz4hc.h $(DESTDIR)$(INCLUDEDIR)/lz4hc.h @echo lz4 static and shared library installed @cd $(PRGDIR); $(MAKE) -e install uninstall: - [ -x $(DESTDIR)$(LIBDIR)/liblz4.a ] && rm -f $(DESTDIR)$(LIBDIR)/liblz4.a rm -f $(DESTDIR)$(LIBDIR)/liblz4.$(SHARED_EXT) rm -f $(DESTDIR)$(LIBDIR)/liblz4.$(SHARED_EXT_MAJOR) [ -x $(DESTDIR)$(LIBDIR)/liblz4.$(SHARED_EXT_VER) ] && rm -f $(DESTDIR)$(LIBDIR)/liblz4.$(SHARED_EXT_VER) + [ -f $(DESTDIR)$(LIBDIR)/liblz4.a ] && rm -f $(DESTDIR)$(LIBDIR)/liblz4.a [ -f $(DESTDIR)$(INCLUDEDIR)/lz4.h ] && rm -f $(DESTDIR)$(INCLUDEDIR)/lz4.h [ -f $(DESTDIR)$(INCLUDEDIR)/lz4hc.h ] && rm -f $(DESTDIR)$(INCLUDEDIR)/lz4hc.h @echo lz4 libraries successfully uninstalled diff --git a/lz4.c b/lz4.c index cb5c3db..2b37c69 100755 --- a/lz4.c +++ b/lz4.c @@ -240,14 +240,10 @@ typedef struct { U32 currentOffset; U32 initCheck; const BYTE* dictionary; + const BYTE* bufferStart; U32 dictSize; } LZ4_dict_t_internal; -typedef struct { - LZ4_dict_t_internal dict; - const BYTE* bufferStart; -} LZ4_Data_Structure; - typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; typedef enum { byPtr, byU32, byU16 } tableType_t; @@ -415,7 +411,6 @@ static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimi return (unsigned)(pIn - pStart); } - static int LZ4_compress_generic( void* ctx, const char* source, @@ -445,7 +440,7 @@ static int LZ4_compress_generic( const int skipStrength = SKIPSTRENGTH; U32 forwardH; - U16 delta=0; + size_t delta=0; /* Init conditions */ if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ @@ -491,7 +486,7 @@ static int LZ4_compress_generic( ref = LZ4_getPositionOnHash(h, ctx, tableType, base); if (dict==usingExtDict) { - delta = (U16)(ip-ref); + delta = (ip-ref); if (ref<(const BYTE*)source) { ref += dictDelta; @@ -503,7 +498,9 @@ static int LZ4_compress_generic( forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx, tableType, base); - } while ((ref + MAX_DISTANCE < ip) || (A32(ref) != A32(ip))); + } while (((dict==usingExtDict) && (delta>MAX_DISTANCE)) || + ((dict!=usingExtDict) && (ref + MAX_DISTANCE < ip)) || + (A32(ref) != A32(ip)) ); /* Catch up */ while ((ip>anchor) && (ref > lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } @@ -578,7 +575,7 @@ _next_match: ref = LZ4_getPosition(ip, ctx, tableType, base); if (dict==usingExtDict) { - delta = (U16)(ip-ref); + delta = ip-ref; if (ref<(const BYTE*)source) { ref += dictDelta; @@ -587,7 +584,9 @@ _next_match: else lowLimit = (const BYTE*)source; } LZ4_putPosition(ip, ctx, tableType, base); - if ((ref + MAX_DISTANCE >= ip) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } + if ((((dict==usingExtDict) && (delta<=MAX_DISTANCE)) || + ((dict!=usingExtDict) && (ref + MAX_DISTANCE >= ip))) && + (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } /* Prepare next loop */ forwardH = LZ4_hashPosition(++ip, tableType); @@ -685,7 +684,21 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* Experimental : Streaming functions *****************************************/ -int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize) +void* LZ4_createStream() +{ + void* lz4s = ALLOCATOR(4, LZ4_DICTSIZE_U32); + MEM_INIT(lz4s, 0, LZ4_DICTSIZE); + 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_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; const BYTE* p = (const BYTE*)dictionary; @@ -732,12 +745,13 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const BYTE* src) else LZ4_dict->hashTable[i] -= delta; } LZ4_dict->currentOffset = 64 KB; - LZ4_dict->dictionary = src - 64 KB; + LZ4_dict->dictionary = LZ4_dict->dictionary + LZ4_dict->dictSize - 64 KB; + LZ4_dict->dictSize = 64 KB; } } -int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) +int LZ4_compress_usingDict (void* LZ4_dict, const char* source, char* dest, int inputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; @@ -763,7 +777,7 @@ int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest } } -int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) +int LZ4_compress_limitedOutput_usingDict (void* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; @@ -790,11 +804,71 @@ int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* sour } +int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize) +{ + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_stream; + const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; + + const BYTE* smallest = dictEnd; + if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; + LZ4_renormDictT(streamPtr, smallest); + + if (dictEnd == (const BYTE*)source) + { + int result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } + + { + int result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } +} + +int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize) +{ + LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_stream; + const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; + + const BYTE* smallest = dictEnd; + if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; + LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_stream, smallest); + + if (dictEnd == (const BYTE*)source) + { + int result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } + + { + int result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict); + streamPtr->dictionary = (const BYTE*)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } +} + + // Hidden debug function, to force separate dictionary mode int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); + 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_dict_t_internal*)LZ4_dict, smallest); + + result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; @@ -804,7 +878,7 @@ int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* d } -int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize) +int LZ4_moveDict (void* LZ4_dict, char* safeBuffer, int dictSize) { LZ4_dict_t_internal* dict = (LZ4_dict_t_internal*) LZ4_dict; const BYTE* previousDictEnd = dict->dictionary + dict->dictSize; @@ -1044,18 +1118,23 @@ int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSi Obsolete Functions **************************************/ /* -These functions are deprecated and should no longer be used. -They are provided here for compatibility with existing user programs. +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 sizeof(LZ4_Data_Structure); -} +typedef struct { + LZ4_dict_t_internal dict; + const BYTE* bufferStart; +} LZ4_Data_Structure; + +int LZ4_sizeofStreamState() { return sizeof(LZ4_Data_Structure); } void LZ4_init(LZ4_Data_Structure* lz4ds, const BYTE* base) { @@ -1077,12 +1156,6 @@ void* LZ4_create (const char* inputBuffer) return lz4ds; } -int LZ4_free (void* LZ4_Data) -{ - FREEMEM(LZ4_Data); - return (0); -} - char* LZ4_slideInputBuffer (void* LZ4_Data) { @@ -1094,32 +1167,3 @@ char* LZ4_slideInputBuffer (void* LZ4_Data) } -int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize) -{ - LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; - int result; - - LZ4_renormDictT(streamPtr, (const BYTE*) source); - result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); - - if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - - return result; -} - -int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize) -{ - LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_Data; - int result; - - LZ4_renormDictT(streamPtr, (const BYTE*) source); - result = LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); - - if (streamPtr->dictSize == 0) streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - - return result; -} diff --git a/lz4.h b/lz4.h index 8a7db0c..7e38a54 100644 --- a/lz4.h +++ b/lz4.h @@ -170,45 +170,54 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* Experimental Streaming Functions **************************************/ -#define LZ4_DICTSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 6) +#define LZ4_DICTSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8) #define LZ4_DICTSIZE (LZ4_DICTSIZE_U32 * sizeof(unsigned int)) /* * LZ4_dict_t - * information structure to track an LZ4 stream - * use LZ4_loadDict() (or set it to zero) to init it before first use. + * information structure to track an LZ4 stream. + * set it to zero, or use LZ4_loadDict() to init it before first use. */ typedef struct { unsigned int table[LZ4_DICTSIZE_U32]; } LZ4_dict_t; + +/* + * LZ4_createStream + * provides a pointer (void*) towards an initialized LZ4_dict_t structure + */ +void* LZ4_createStream(); +int LZ4_free (void* LZ4_stream); + /* * LZ4_loadDict * Use this function to load a static dictionary into LZ4_dict. * You can load a size of 0 to init an LZ4_dict_t structure * Return : 1 if OK, 0 if error */ -int LZ4_loadDict (LZ4_dict_t* LZ4_dict, const char* dictionary, int dictSize); +int LZ4_loadDict (void* LZ4_stream, const char* dictionary, int dictSize); /* * LZ4_compress_usingDict * Compress data block 'source', using blocks compressed before to improve compression ratio * Previous data blocks are assumed to still be present at their previous location. */ -int LZ4_compress_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); +int LZ4_compress_usingDict (void* LZ4_stream, const char* source, char* dest, int inputSize); /* * LZ4_compress_limitedOutput_usingDict * Same as before, but also specify a maximum target compressed size (maxOutputSize) * If it cannot be met, compression exits, and return a zero. */ -int LZ4_compress_limitedOutput_usingDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compress_limitedOutput_usingDict (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize); /* * LZ4_moveDict - * If previous data block cannot be guaranteed to remain at its previous location in memory + * If previously compressed data block is not guaranteed to remain at its previous memory location * save it into a safe place (char* safeBuffer) * before calling again LZ4_compress_usingDict() * Return : 1 if OK, 0 if error + * Note : any dictSize > 64 KB will be interpreted as 64KB. */ -int LZ4_moveDict (LZ4_dict_t* LZ4_dict, char* safeBuffer, int dictSize); +int LZ4_moveDict (void* LZ4_stream, char* safeBuffer, int dictSize); /* @@ -235,8 +244,10 @@ int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int origi Obsolete Functions **************************************/ /* -These functions are deprecated and should no longer be used. -They are provided here for compatibility with existing user programs. +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); int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); @@ -248,7 +259,6 @@ int LZ4_resetStreamState(void* state, const char* inputBuffer); int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize); int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize); char* LZ4_slideInputBuffer (void* LZ4_Data); -int LZ4_free (void* LZ4_Data); #if defined (__cplusplus) diff --git a/programs/Makefile b/programs/Makefile index 522850e..53e4eb2 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -127,21 +127,21 @@ uninstall: test: $(TEST_TARGETS) -test-64: test-lz4 test-lz4c test-fullbench test-fuzzer +test-64: test-lz4 test-lz4c test-fullbench test-fuzzer test-mem -test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 +test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 test-mem32 test-lz4: lz4 datagen ./datagen | ./lz4 | ./lz4 -vdq > $(VOID) ./datagen -g256MB | ./lz4 -B4D | ./lz4 -vdq > $(VOID) - ./datagen -g6GB | ./lz4 -vqBD | ./lz4 -vdq > $(VOID) + ./datagen -g6GB | ./lz4 -vqB5D | ./lz4 -vdq > $(VOID) test-lz4c: lz4c datagen test-lz4c32: lz4c32 datagen ./datagen | ./lz4c32 | ./lz4c32 -vdq > $(VOID) ./datagen -g256MB | ./lz4c32 -B4D | ./lz4c32 -vdq > $(VOID) - ./datagen -g6GB | ./lz4c32 -vqBD | ./lz4c32 -vdq > $(VOID) + ./datagen -g6GB | ./lz4c32 -vqB5D | ./lz4c32 -vdq > $(VOID) test-fullbench: fullbench ./fullbench --no-prompt $(BENCH_NB) $(TEST_FILES) @@ -155,5 +155,12 @@ test-fuzzer: fuzzer test-fuzzer32: fuzzer32 ./fuzzer32 --no-prompt +test-mem: lz4 datagen + ./datagen -g256M > tmp + valgrind ./lz4 -B4D -f tmp /dev/null + rm tmp + +test-mem32: lz4c32 datagen +# unfortunately, valgrind doesn't work with non-native binary. If someone knows how to valgrind-test a 32-bits exe on a 64-bits system... endif diff --git a/programs/lz4cli.c b/programs/lz4cli.c index 1c4e9de..e05a9a9 100644 --- a/programs/lz4cli.c +++ b/programs/lz4cli.c @@ -109,7 +109,7 @@ //**************************** #define COMPRESSOR_NAME "LZ4 Compression CLI" #ifndef LZ4_VERSION -# define LZ4_VERSION "v1.1.5" +# define LZ4_VERSION "v1.1.8" #endif #define AUTHOR "Yann Collet" #define WELCOME_MESSAGE "*** %s %i-bits %s, by %s (%s) ***\n", COMPRESSOR_NAME, (int)(sizeof(void*)*8), LZ4_VERSION, AUTHOR, __DATE__ diff --git a/programs/lz4io.c b/programs/lz4io.c index 05955cf..e035f01 100644 --- a/programs/lz4io.c +++ b/programs/lz4io.c @@ -365,17 +365,16 @@ int LZ4IO_compressFilename_Legacy(char* input_filename, char* output_filename, i } -static int compress_file_blockDependency(char* input_filename, char* output_filename, int compressionlevel) +static int compress_file_blockDependency2(char* input_filename, char* output_filename, int compressionlevel) { - void* (*initFunction) (const char*); + void* (*initFunction) (); int (*compressionFunction)(void*, const char*, char*, int, int); - char* (*translateFunction) (void*); int (*freeFunction) (void*); void* ctx; unsigned long long filesize = 0; unsigned long long compressedfilesize = 0; unsigned int checkbits; - char* in_buff, *in_start, *in_end; + char* in_buff, *in_blockStart, *in_end; char* out_buff; FILE* finput; FILE* foutput; @@ -384,24 +383,14 @@ static int compress_file_blockDependency(char* input_filename, char* output_file size_t sizeCheck, header_size; void* streamChecksumState=NULL; - // Init start = clock(); if ((displayLevel==2) && (compressionlevel>=3)) displayLevel=3; - if (compressionlevel>=3) - { - initFunction = LZ4_createHC; - compressionFunction = LZ4_compressHC_limitedOutput_continue; - translateFunction = LZ4_slideInputBufferHC; - freeFunction = LZ4_freeHC; - } - else - { - initFunction = LZ4_create; - compressionFunction = LZ4_compress_limitedOutput_continue; - translateFunction = LZ4_slideInputBuffer; - freeFunction = LZ4_free; - } + + initFunction = LZ4_createStream; + compressionFunction = LZ4_compress_limitedOutput_continue; + freeFunction = LZ4_free; + get_fileHandle(input_filename, output_filename, &finput, &foutput); blockSize = LZ4S_GetBlockSize_FromBlockId (blockSizeId); @@ -411,9 +400,9 @@ static int compress_file_blockDependency(char* input_filename, char* output_file in_buff = (char*)malloc(inputBufferSize); out_buff = (char*)malloc(blockSize+CACHELINE); if (!in_buff || !out_buff) EXM_THROW(31, "Allocation error : not enough memory"); - in_start = in_buff; in_end = in_buff + inputBufferSize; + in_blockStart = in_buff; in_end = in_buff + inputBufferSize; if (streamChecksum) streamChecksumState = XXH32_init(LZ4S_CHECKSUM_SEED); - ctx = initFunction(in_buff); + ctx = initFunction(); // Write Archive Header *(unsigned int*)out_buff = LITTLE_ENDIAN_32(LZ4S_MAGICNUMBER); // Magic Number, in Little Endian convention @@ -435,19 +424,20 @@ static int compress_file_blockDependency(char* input_filename, char* output_file { unsigned int outSize; unsigned int inSize; + // Read Block - if ((in_start+blockSize) > in_end) in_start = translateFunction(ctx); - inSize = (unsigned int) fread(in_start, (size_t)1, (size_t)blockSize, finput); + if ((in_blockStart+blockSize) > in_end) in_blockStart = in_buff; + inSize = (unsigned int) fread(in_blockStart, (size_t)1, (size_t)blockSize, finput); if( inSize==0 ) break; // No more input : end of compression filesize += inSize; DISPLAYLEVEL(3, "\rRead : %i MB ", (int)(filesize>>20)); - if (streamChecksum) XXH32_update(streamChecksumState, in_start, inSize); + if (streamChecksum) XXH32_update(streamChecksumState, in_blockStart, inSize); // Compress Block - outSize = compressionFunction(ctx, in_start, out_buff+4, inSize, inSize-1); + outSize = compressionFunction(ctx, in_blockStart, out_buff+4, inSize, inSize-1); if (outSize > 0) compressedfilesize += outSize+4; else compressedfilesize += inSize+4; if (blockChecksum) compressedfilesize+=4; - DISPLAYLEVEL(3, "\rRead : %i MB ==> %.2f%% ", (int)(filesize>>20), (double)compressedfilesize/filesize*100); + DISPLAYLEVEL(3, "==> %.2f%% ", (double)compressedfilesize/filesize*100); // Write Block if (outSize > 0) @@ -462,24 +452,23 @@ static int compress_file_blockDependency(char* input_filename, char* output_file sizeToWrite = 4 + outSize + (4*blockChecksum); sizeCheck = fwrite(out_buff, 1, sizeToWrite, foutput); if (sizeCheck!=(size_t)(sizeToWrite)) EXM_THROW(33, "Write error : cannot write compressed block"); - } else // Copy Original { * (unsigned int*) out_buff = LITTLE_ENDIAN_32(inSize|0x80000000); // Add Uncompressed flag sizeCheck = fwrite(out_buff, 1, 4, foutput); if (sizeCheck!=(size_t)(4)) EXM_THROW(34, "Write error : cannot write block header"); - sizeCheck = fwrite(in_start, 1, inSize, foutput); + sizeCheck = fwrite(in_blockStart, 1, inSize, foutput); if (sizeCheck!=(size_t)(inSize)) EXM_THROW(35, "Write error : cannot write block"); if (blockChecksum) { - unsigned int checksum = XXH32(in_start, inSize, LZ4S_CHECKSUM_SEED); + unsigned int checksum = XXH32(in_blockStart, inSize, LZ4S_CHECKSUM_SEED); * (unsigned int*) out_buff = LITTLE_ENDIAN_32(checksum); sizeCheck = fwrite(out_buff, 1, 4, foutput); if (sizeCheck!=(size_t)(4)) EXM_THROW(36, "Write error : cannot write block checksum"); } } - in_start += inSize; + in_blockStart += inSize; } // End of Stream mark @@ -537,12 +526,12 @@ int LZ4IO_compressFilename(char* input_filename, char* output_filename, int comp void* streamChecksumState=NULL; // Branch out - if (blockIndependence==0) return compress_file_blockDependency(input_filename, output_filename, compressionLevel); + if (blockIndependence==0) return compress_file_blockDependency2(input_filename, output_filename, compressionLevel); // Init start = clock(); if ((displayLevel==2) && (compressionLevel>=3)) displayLevel=3; - if (compressionLevel <= 3) compressionFunction = LZ4_compress_limitedOutput_local; + if (compressionLevel <= 3) compressionFunction = LZ4_compress_limitedOutput_local; else { compressionFunction = LZ4_compressHC2_limitedOutput; } get_fileHandle(input_filename, output_filename, &finput, &foutput); blockSize = LZ4S_GetBlockSize_FromBlockId (blockSizeId); @@ -587,7 +576,7 @@ int LZ4IO_compressFilename(char* input_filename, char* output_filename, int comp outSize = compressionFunction(in_buff, out_buff+4, (int)readSize, (int)readSize-1, compressionLevel); if (outSize > 0) compressedfilesize += outSize+4; else compressedfilesize += readSize+4; if (blockChecksum) compressedfilesize+=4; - DISPLAYLEVEL(3, "\rRead : %i MB ==> %.2f%% ", (int)(filesize>>20), (double)compressedfilesize/filesize*100); + DISPLAYLEVEL(3, "==> %.2f%% ", (double)compressedfilesize/filesize*100); // Write Block if (outSize > 0) -- cgit v0.12 From 598bde9a6914287686693013424ec4edf0433992 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 9 Jun 2014 02:42:39 +0100 Subject: converge towards LZ4_compress_continue() --- lz4.c | 53 ---------------------------------------------------- lz4.h | 22 +++++++++++----------- programs/fullbench.c | 38 ++----------------------------------- programs/fuzzer.c | 40 +++++++++++++++++++++++++-------------- 4 files changed, 39 insertions(+), 114 deletions(-) diff --git a/lz4.c b/lz4.c index 2b37c69..6eff9b9 100755 --- a/lz4.c +++ b/lz4.c @@ -751,59 +751,6 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const BYTE* src) } -int LZ4_compress_usingDict (void* LZ4_dict, const char* source, char* dest, int inputSize) -{ - LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - - const BYTE* smallest = dictEnd; - if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; - LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_dict, smallest); - - if (dictEnd == (const BYTE*)source) - { - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, withPrefix64k); - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - return result; - } - - { - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); - streamPtr->dictionary = (const BYTE*)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - return result; - } -} - -int LZ4_compress_limitedOutput_usingDict (void* LZ4_dict, const char* source, char* dest, int inputSize, int maxOutputSize) -{ - LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; - const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - - const BYTE* smallest = dictEnd; - if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; - LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_dict, smallest); - - if (dictEnd == (const BYTE*)source) - { - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k); - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - return result; - } - - { - int result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict); - 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) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_stream; diff --git a/lz4.h b/lz4.h index 7e38a54..5afc133 100644 --- a/lz4.h +++ b/lz4.h @@ -183,6 +183,7 @@ typedef struct { unsigned int table[LZ4_DICTSIZE_U32]; } LZ4_dict_t; /* * LZ4_createStream * provides a pointer (void*) towards an initialized LZ4_dict_t structure + * LZ4_free just frees it. */ void* LZ4_createStream(); int LZ4_free (void* LZ4_stream); @@ -190,30 +191,30 @@ int LZ4_free (void* LZ4_stream); /* * LZ4_loadDict * Use this function to load a static dictionary into LZ4_dict. - * You can load a size of 0 to init an LZ4_dict_t structure + * Loading a size of 0 is allowed and init the LZ4_dict_t structure. * Return : 1 if OK, 0 if error */ int LZ4_loadDict (void* LZ4_stream, const char* dictionary, int dictSize); /* - * LZ4_compress_usingDict + * LZ4_compress_continue * Compress data block 'source', using blocks compressed before to improve compression ratio * Previous data blocks are assumed to still be present at their previous location. */ -int LZ4_compress_usingDict (void* LZ4_stream, const char* source, char* dest, int inputSize); +int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize); /* - * LZ4_compress_limitedOutput_usingDict + * LZ4_compress_limitedOutput_continue * Same as before, but also specify a maximum target compressed size (maxOutputSize) * If it cannot be met, compression exits, and return a zero. */ -int LZ4_compress_limitedOutput_usingDict (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize); /* * LZ4_moveDict * If previously compressed data block is not guaranteed to remain at its previous memory location * save it into a safe place (char* safeBuffer) - * before calling again LZ4_compress_usingDict() + * before calling again LZ4_compress_continue() * Return : 1 if OK, 0 if error * Note : any dictSize > 64 KB will be interpreted as 64KB. */ @@ -240,14 +241,15 @@ int LZ4_decompress_safe_withPrefix64k (const char* source, char* dest, int compr int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int originalSize); + /************************************** 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 +- 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); @@ -256,9 +258,7 @@ int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isiz void* LZ4_create (const char* inputBuffer); int LZ4_sizeofStreamState(void); int LZ4_resetStreamState(void* state, const char* inputBuffer); -int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize); -int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize); -char* LZ4_slideInputBuffer (void* LZ4_Data); +char* LZ4_slideInputBuffer (void* state); #if defined (__cplusplus) diff --git a/programs/fullbench.c b/programs/fullbench.c index 7249387..23ca5b7 100755 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -290,16 +290,6 @@ static void* local_LZ4_resetDictT(const char* fake) return NULL; } -static int local_LZ4_compress_usingDict(const char* in, char* out, int inSize) -{ - return LZ4_compress_usingDict(&LZ4_dict, in, out, inSize); -} - -static int local_LZ4_compress_limitedOutput_usingDict(const char* in, char* out, int inSize) -{ - return LZ4_compress_limitedOutput_usingDict(&LZ4_dict, in, out, inSize, LZ4_compressBound(inSize)); -} - int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); static int local_LZ4_compress_forceDict(const char* in, char* out, int inSize) { @@ -370,9 +360,8 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) { int fileIdx=0; char* orig_buff; -# define NB_COMPRESSION_ALGORITHMS 15 +# define NB_COMPRESSION_ALGORITHMS 13 # define MINCOMPRESSIONCHAR '0' -# define MAXCOMPRESSIONCHAR (MINCOMPRESSIONCHAR + NB_COMPRESSION_ALGORITHMS) double totalCTime[NB_COMPRESSION_ALGORITHMS+1] = {0}; double totalCSize[NB_COMPRESSION_ALGORITHMS+1] = {0}; # define NB_DECOMPRESSION_ALGORITHMS 7 @@ -508,9 +497,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) case 10: compressionFunction = local_LZ4_compressHC_limitedOutput_withStateHC; compressorName = "LZ4_compressHC_limitedOutput_withStateHC"; break; case 11: compressionFunction = local_LZ4_compressHC_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_continue"; break; case 12: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_limitedOutput_continue"; break; - case 13: compressionFunction = local_LZ4_compress_usingDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_usingDict"; break; - case 14: compressionFunction = local_LZ4_compress_limitedOutput_usingDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_limitedOutput_usingDict"; break; - case 15: compressionFunction = local_LZ4_compress_forceDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_forceDict"; break; + case 13: compressionFunction = local_LZ4_compress_forceDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_forceDict"; break; default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; } @@ -630,27 +617,6 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) free(chunkP); } -/* - if (nbFiles > 1) - { - int AlgNb; - - DISPLAY(" ** TOTAL ** : \n"); - for (AlgNb = 0; (AlgNb < NB_COMPRESSION_ALGORITHMS) && (compressionTest); AlgNb ++) - { - char* cName = compressionNames[AlgNb]; - if ((compressionAlgo != ALL_COMPRESSORS) && (compressionAlgo != AlgNb)) continue; - DISPLAY("%-23.23s :%10llu ->%10llu (%5.2f%%), %6.1f MB/s\n", cName, (long long unsigned int)totals, (long long unsigned int)totalCSize[AlgNb], (double)totalCSize[AlgNb]/(double)totals*100., (double)totals/totalCTime[AlgNb]/1000.); - } - for (AlgNb = 0; (AlgNb < NB_DECOMPRESSION_ALGORITHMS) && (decompressionTest); AlgNb ++) - { - char* dName = decompressionNames[AlgNb]; - if ((decompressionAlgo != ALL_DECOMPRESSORS) && (decompressionAlgo != AlgNb)) continue; - DISPLAY("%-31.31s :%10llu -> %6.1f MB/s\n", dName, (long long unsigned int)totals, (double)totals/totalDTime[AlgNb]/1000.); - } - } -*/ - if (BMK_pause) { printf("press enter...\n"); getchar(); } return 0; diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 56208d3..608340c 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -83,11 +83,12 @@ #define DISPLAYLEVEL(l, ...) if (displayLevel>=l) { DISPLAY(__VA_ARGS__); } -//************************************** -// Local Parameters -//************************************** +/***************************************** + Local Parameters +*****************************************/ static int no_prompt = 0; static char* programName; +static int displayLevel = 2; /********************************************************* @@ -200,12 +201,13 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { int ret, cycleNb; # define FUZ_CHECKTEST(cond, ...) if (cond) { printf("Test %i : ", testNb); printf(__VA_ARGS__); \ printf(" (seed %u, cycle %i) \n", seed, cycleNb); goto _output_error; } -# define FUZ_DISPLAYTEST { testNb++; no_prompt ? 0 : printf("%2i\b\b", testNb); } +# define FUZ_DISPLAYTEST { testNb++; ((displayLevel<3) || no_prompt) ? 0 : printf("%2i\b\b", testNb); if (displayLevel==4) fflush(stdout); } void* stateLZ4 = malloc(LZ4_sizeofState()); void* stateLZ4HC = malloc(LZ4_sizeofStateHC()); void* LZ4continue; LZ4_dict_t LZ4dict; U32 crcOrig, crcCheck; + int displayRefresh; // Create compressible test buffer @@ -214,6 +216,15 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { compressedBuffer = malloc(LZ4_compressBound(FUZ_MAX_BLOCK_SIZE)); decodedBuffer = malloc(FUZ_MAX_DICT_SIZE + FUZ_MAX_BLOCK_SIZE); + // display refresh rate + switch(displayLevel) + { + case 0: displayRefresh = nbCycles+1; break; + case 1: displayRefresh=FUZ_MAX(1, nbCycles / 100); break; + case 2: displayRefresh=99; break; + default : displayRefresh=1; + } + // move to startCycle for (cycleNb = 0; cycleNb < startCycle; cycleNb++) { @@ -231,14 +242,10 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { int dictSize, blockSize, blockStart, compressedSize, HCcompressedSize; int blockContinueCompressedSize; - // note : promptThrottle is throtting stdout to prevent - // Travis-CI's output limit (10MB) and false hangup detection. - const int step = FUZ_MAX(1, nbCycles / 100); - const int promptThrottle = ((cycleNb % step) == 0); - if (!no_prompt || cycleNb == 0 || promptThrottle) + if ((cycleNb%displayRefresh) == 0) { printf("\r%7i /%7i - ", cycleNb, nbCycles); - if (no_prompt) fflush(stdout); + fflush(stdout); } // Select block to test @@ -431,19 +438,19 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); - blockContinueCompressedSize = LZ4_compress_usingDict(&LZ4dict, block, compressedBuffer, blockSize); + blockContinueCompressedSize = LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_usingDict failed"); FUZ_DISPLAYTEST; memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); - ret = LZ4_compress_limitedOutput_usingDict(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); + ret = LZ4_compress_limitedOutput_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); FUZ_CHECKTEST(ret>0, "LZ4_compress_limitedOutput_usingDict should fail : one missing byte for output buffer"); FUZ_DISPLAYTEST; memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); - ret = LZ4_compress_limitedOutput_usingDict(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize); + ret = LZ4_compress_limitedOutput_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_limitedOutput_usingDict should work : enough size available within output buffer"); // Decompress with dictionary as external @@ -535,6 +542,7 @@ int FUZ_usage() DISPLAY( " -s# : Select seed (default:prompt user)\n"); DISPLAY( " -t# : Select starting test number (default:0)\n"); DISPLAY( " -p# : Select compressibility in %% (default:%i%%)\n", FUZ_COMPRESSIBILITY_DEFAULT); + DISPLAY( " -v : verbose\n"); DISPLAY( " -h : display help and exit\n"); return 0; } @@ -561,7 +569,7 @@ int main(int argc, char** argv) { // Decode command (note : aggregated commands are allowed) if (argument[0]=='-') { - if (!strcmp(argument, "--no-prompt")) { no_prompt=1; seedset=1; continue; } + if (!strcmp(argument, "--no-prompt")) { no_prompt=1; seedset=1; displayLevel=1; continue; } while (argument[1]!=0) { @@ -570,6 +578,10 @@ int main(int argc, char** argv) { { case 'h': return FUZ_usage(); + case 'v': + argument++; + displayLevel=4; + break; case 'i': argument++; nbTests=0; -- cgit v0.12 From 426e7437e10719b215dc5aeb46e48bcf90ae3831 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 9 Jun 2014 02:49:20 +0100 Subject: removed old stream structure --- lz4.c | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) diff --git a/lz4.c b/lz4.c index 6eff9b9..c264cc3 100755 --- a/lz4.c +++ b/lz4.c @@ -1076,37 +1076,31 @@ int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, /* Obsolete Streaming functions */ -typedef struct { - LZ4_dict_t_internal dict; - const BYTE* bufferStart; -} LZ4_Data_Structure; +int LZ4_sizeofStreamState() { return LZ4_DICTSIZE; } -int LZ4_sizeofStreamState() { return sizeof(LZ4_Data_Structure); } - -void LZ4_init(LZ4_Data_Structure* lz4ds, const BYTE* base) +void LZ4_init(LZ4_dict_t_internal* lz4ds, const BYTE* base) { - MEM_INIT(lz4ds->dict.hashTable, 0, sizeof(lz4ds->dict.hashTable)); + MEM_INIT(lz4ds->hashTable, 0, LZ4_DICTSIZE); 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_Data_Structure*)state, (const BYTE*)inputBuffer); + LZ4_init((LZ4_dict_t_internal*)state, (const BYTE*)inputBuffer); return 0; } void* LZ4_create (const char* inputBuffer) { - void* lz4ds = ALLOCATOR(1, sizeof(LZ4_Data_Structure)); - LZ4_init ((LZ4_Data_Structure*)lz4ds, (const BYTE*)inputBuffer); + void* lz4ds = ALLOCATOR(4, LZ4_DICTSIZE_U32); + LZ4_init ((LZ4_dict_t_internal*)lz4ds, (const BYTE*)inputBuffer); return lz4ds; } - char* LZ4_slideInputBuffer (void* LZ4_Data) { - LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data; + LZ4_dict_t_internal* lz4ds = (LZ4_dict_t_internal*)LZ4_Data; LZ4_moveDict((LZ4_dict_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB); -- cgit v0.12 From 135f11b54ea8e9c257d17514edc16d4a392a0659 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 9 Jun 2014 16:46:03 +0100 Subject: Obsolete "external allocation" functions (convergence towards LZ4_compress_continue() ) --- lz4.c | 91 +++++++++++++++++++++++----------------------------- lz4.h | 48 +++++++++++++-------------- programs/fullbench.c | 6 ++-- programs/fuzzer.c | 8 ++--- 4 files changed, 70 insertions(+), 83 deletions(-) diff --git a/lz4.c b/lz4.c index c264cc3..d926393 100755 --- a/lz4.c +++ b/lz4.c @@ -611,9 +611,9 @@ _last_literals: int LZ4_compress(const char* source, char* dest, int inputSize) { #if (HEAPMODE) - void* ctx = ALLOCATOR(LZ4_DICTSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ + void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ #else - U32 ctx[LZ4_DICTSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ + U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ #endif int result; @@ -631,9 +631,9 @@ int LZ4_compress(const char* source, char* dest, int inputSize) int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { #if (HEAPMODE) - void* ctx = ALLOCATOR(LZ4_DICTSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ + void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ #else - U32 ctx[LZ4_DICTSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ + U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ #endif int result; @@ -649,45 +649,14 @@ int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, in } -/***************************** - User-allocated state -*****************************/ - -int LZ4_sizeofState() { return LZ4_DICTSIZE; } - - -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_sizeofState()); - - if (inputSize < (int)LZ4_64KLIMIT) - return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict); - else - return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict); -} - - -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_sizeofState()); - - if (inputSize < (int)LZ4_64KLIMIT) - return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict); - else - return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict); -} - - /***************************************** Experimental : Streaming functions *****************************************/ void* LZ4_createStream() { - void* lz4s = ALLOCATOR(4, LZ4_DICTSIZE_U32); - MEM_INIT(lz4s, 0, LZ4_DICTSIZE); + void* lz4s = ALLOCATOR(4, LZ4_STREAMSIZE_U32); + MEM_INIT(lz4s, 0, LZ4_STREAMSIZE); return lz4s; } @@ -705,7 +674,7 @@ int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize) const BYTE* const dictEnd = p + dictSize; const BYTE* base; - LZ4_STATIC_ASSERT(LZ4_DICTSIZE >= sizeof(LZ4_dict_t_internal)); /* A compilation error here means LZ4_DICTSIZE is not large enough */ + LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_dict_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_dict_t_internal)); if (dictSize < MINMATCH) @@ -805,7 +774,7 @@ int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, c // Hidden debug function, to force separate dictionary mode -int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize) +int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize) { LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_dict; int result; @@ -854,7 +823,7 @@ int LZ4_moveDict (void* LZ4_dict, char* safeBuffer, int dictSize) * Note that it is essential this generic function is really inlined, * in order to remove useless branches during compilation optimisation. */ -int LZ4_decompress_generic( +static int LZ4_decompress_generic( const char* source, char* dest, int inputSize, @@ -886,11 +855,10 @@ int LZ4_decompress_generic( /* Special cases */ (void)dictStart; (void)dictSize; - if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */ + 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) { @@ -902,11 +870,7 @@ int LZ4_decompress_generic( if ((length=(token>>ML_BITS)) == RUN_MASK) { unsigned s=255; - while (((endOnInput)?iphashTable, 0, LZ4_DICTSIZE); + MEM_INIT(lz4ds->hashTable, 0, LZ4_STREAMSIZE); lz4ds->bufferStart = base; } @@ -1093,7 +1057,7 @@ int LZ4_resetStreamState(void* state, const char* inputBuffer) void* LZ4_create (const char* inputBuffer) { - void* lz4ds = ALLOCATOR(4, LZ4_DICTSIZE_U32); + void* lz4ds = ALLOCATOR(4, LZ4_STREAMSIZE_U32); LZ4_init ((LZ4_dict_t_internal*)lz4ds, (const BYTE*)inputBuffer); return lz4ds; } @@ -1102,9 +1066,34 @@ char* LZ4_slideInputBuffer (void* LZ4_Data) { LZ4_dict_t_internal* lz4ds = (LZ4_dict_t_internal*)LZ4_Data; - LZ4_moveDict((LZ4_dict_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB); + LZ4_moveDict((LZ4_stream_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB); return (char*)(lz4ds->bufferStart + 64 KB); } +/* 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_sizeofState()); + + if (inputSize < (int)LZ4_64KLIMIT) + return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict); + else + return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict); +} + +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_sizeofState()); + + if (inputSize < (int)LZ4_64KLIMIT) + return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict); + else + return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict); +} diff --git a/lz4.h b/lz4.h index 5afc133..f2975d4 100644 --- a/lz4.h +++ b/lz4.h @@ -88,6 +88,13 @@ LZ4_decompress_safe() : */ +/* +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 **************************************/ @@ -150,39 +157,24 @@ LZ4_decompress_safe_partial() : int LZ4_decompress_safe_partial (const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize); -/* -The following functions are provided should you prefer to allocate table memory using your own allocation methods. -int LZ4_sizeofState(); -provides the size to allocate for compression tables. - -Tables must be aligned on 4-bytes boundaries, otherwise compression will fail (return code 0). - -The allocated memory can be provided to the compressions functions using 'void* state' parameter. -LZ4_compress_withState() and LZ4_compress_limitedOutput_withState() are equivalent to previously described functions. -They just use the externally allocated memory area instead of allocating their own one (on stack, or on heap). -*/ -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); - - /************************************** Experimental Streaming Functions **************************************/ -#define LZ4_DICTSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8) -#define LZ4_DICTSIZE (LZ4_DICTSIZE_U32 * sizeof(unsigned int)) +#define LZ4_STREAMSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8) +#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U32 * sizeof(unsigned int)) /* - * LZ4_dict_t + * LZ4_stream_t * information structure to track an LZ4 stream. * set it to zero, or use LZ4_loadDict() to init it before first use. */ -typedef struct { unsigned int table[LZ4_DICTSIZE_U32]; } LZ4_dict_t; +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_dict_t structure + * provides a pointer (void*) towards an initialized LZ4_stream_t structure. * LZ4_free just frees it. */ void* LZ4_createStream(); @@ -190,8 +182,8 @@ int LZ4_free (void* LZ4_stream); /* * LZ4_loadDict - * Use this function to load a static dictionary into LZ4_dict. - * Loading a size of 0 is allowed and init the LZ4_dict_t structure. + * Use this function to load a static dictionary into LZ4_stream. + * Loading a size of 0 is allowed and init the LZ4_stream_t structure. * Return : 1 if OK, 0 if error */ int LZ4_loadDict (void* LZ4_stream, const char* dictionary, int dictSize); @@ -246,13 +238,19 @@ int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int origi 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); +int LZ4_uncompress (const char* source, char* dest, int outputSize); +int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); + +/* Obsolete external allocation functions */ +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 */ void* LZ4_create (const char* inputBuffer); diff --git a/programs/fullbench.c b/programs/fullbench.c index 23ca5b7..154de78 100755 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -282,15 +282,15 @@ static int local_LZ4_compress_limitedOutput_continue(const char* in, char* out, } -LZ4_dict_t LZ4_dict; +LZ4_stream_t LZ4_dict; static void* local_LZ4_resetDictT(const char* fake) { (void)fake; - memset(&LZ4_dict, 0, sizeof(LZ4_dict_t)); + memset(&LZ4_dict, 0, sizeof(LZ4_stream_t)); return NULL; } -int LZ4_compress_forceExtDict (LZ4_dict_t* LZ4_dict, const char* source, char* dest, int inputSize); +int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize); static int local_LZ4_compress_forceDict(const char* in, char* out, int inSize) { return LZ4_compress_forceExtDict(&LZ4_dict, in, out, inSize); diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 608340c..d209fd3 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -205,7 +205,7 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { void* stateLZ4 = malloc(LZ4_sizeofState()); void* stateLZ4HC = malloc(LZ4_sizeofStateHC()); void* LZ4continue; - LZ4_dict_t LZ4dict; + LZ4_stream_t LZ4dict; U32 crcOrig, crcCheck; int displayRefresh; @@ -436,19 +436,19 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { FUZ_DISPLAYTEST; dict -= 9; if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; - memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + memset(&LZ4dict, 0, sizeof(LZ4_stream_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); blockContinueCompressedSize = LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_usingDict failed"); FUZ_DISPLAYTEST; - memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + memset(&LZ4dict, 0, sizeof(LZ4_stream_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); ret = LZ4_compress_limitedOutput_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); FUZ_CHECKTEST(ret>0, "LZ4_compress_limitedOutput_usingDict should fail : one missing byte for output buffer"); FUZ_DISPLAYTEST; - memset(&LZ4dict, 0, sizeof(LZ4_dict_t)); + memset(&LZ4dict, 0, sizeof(LZ4_stream_t)); LZ4_loadDict(&LZ4dict, dict, dictSize); ret = LZ4_compress_limitedOutput_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_limitedOutput_usingDict should work : enough size available within output buffer"); -- cgit v0.12 From f0e6bf45ca509851b51992ecf28b1415c2367440 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 9 Jun 2014 18:08:23 +0100 Subject: Improved compression speed in 64KB block mode --- lz4.c | 41 ++++++++++++++++++++++------------------- 1 file changed, 22 insertions(+), 19 deletions(-) diff --git a/lz4.c b/lz4.c index d926393..62e1f45 100755 --- a/lz4.c +++ b/lz4.c @@ -411,6 +411,7 @@ static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimi return (unsigned)(pIn - pStart); } + static int LZ4_compress_generic( void* ctx, const char* source, @@ -436,11 +437,11 @@ static int LZ4_compress_generic( const BYTE* const matchlimit = iend - LASTLITERALS; BYTE* op = (BYTE*) dest; - BYTE* const oend = op + maxOutputSize; + BYTE* const olimit = op + maxOutputSize; const int skipStrength = SKIPSTRENGTH; U32 forwardH; - size_t delta=0; + size_t refDelta=0; /* Init conditions */ if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ @@ -486,30 +487,31 @@ static int LZ4_compress_generic( ref = LZ4_getPositionOnHash(h, ctx, tableType, base); if (dict==usingExtDict) { - delta = (ip-ref); if (ref<(const BYTE*)source) { - ref += dictDelta; + refDelta = dictDelta; lowLimit = dictionary; } - else lowLimit = (const BYTE*)source; + else + { + refDelta = 0; + lowLimit = (const BYTE*)source; + } } if (unlikely(ip > mflimit)) goto _last_literals; forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx, tableType, base); - } while (((dict==usingExtDict) && (delta>MAX_DISTANCE)) || - ((dict!=usingExtDict) && (ref + MAX_DISTANCE < ip)) || - (A32(ref) != A32(ip)) ); + } while ( ((tableType==byU16)? 0 : (ref + MAX_DISTANCE < ip)) || (A32(ref+refDelta) != A32(ip)) ); /* Catch up */ - while ((ip>anchor) && (ref > lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; } + while ((ip>anchor) && (ref+refDelta > lowLimit) && (unlikely(ip[-1]==ref[refDelta-1]))) { ip--; ref--; } // refDelta costs some performance { /* Encode Literal length */ unsigned litLength = (unsigned)(ip - anchor); token = op++; - if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > oend))) return 0; /* Check output limit */ + 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; @@ -525,10 +527,10 @@ static int LZ4_compress_generic( _next_match: /* Encode Offset */ - if (dict==usingExtDict) LZ4_WRITE_LITTLEENDIAN_16(op, delta) - else LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); + LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref)); /* Encode MatchLength */ + ref += refDelta; { unsigned matchLength; @@ -553,7 +555,7 @@ _next_match: if (matchLength>=ML_MASK) { - if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > oend))) return 0; /* Check output limit */ + if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit))) return 0; /* Check output limit */ *token += ML_MASK; matchLength -= ML_MASK; for (; matchLength > 509 ; matchLength-=510) { *op++ = 255; *op++ = 255; } @@ -575,18 +577,19 @@ _next_match: ref = LZ4_getPosition(ip, ctx, tableType, base); if (dict==usingExtDict) { - delta = ip-ref; if (ref<(const BYTE*)source) { - ref += dictDelta; + refDelta = dictDelta; lowLimit = dictionary; } - else lowLimit = (const BYTE*)source; + else + { + refDelta = 0; + lowLimit = (const BYTE*)source; + } } LZ4_putPosition(ip, ctx, tableType, base); - if ((((dict==usingExtDict) && (delta<=MAX_DISTANCE)) || - ((dict!=usingExtDict) && (ref + MAX_DISTANCE >= ip))) && - (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; } + if ( (ref+MAX_DISTANCE>=ip) && (A32(ref+refDelta)==A32(ip)) ) { token=op++; *token=0; goto _next_match; } /* Prepare next loop */ forwardH = LZ4_hashPosition(++ip, tableType); -- cgit v0.12 From 661e4ddb78ce89d5de3ad0824e6abb161044aa06 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 10 Jun 2014 06:10:08 +0100 Subject: lz4io : reduced memory usage in streaming mode --- lz4.c | 55 +++++++++++++++++++++++++++++------------------------- programs/Makefile | 12 +++++++----- programs/datagen.c | 44 ++++++++++++++++++++++++++++++++++++------- programs/lz4io.c | 16 ++++++++++------ 4 files changed, 84 insertions(+), 43 deletions(-) diff --git a/lz4.c b/lz4.c index 62e1f45..beff5a7 100755 --- a/lz4.c +++ b/lz4.c @@ -472,40 +472,45 @@ static int LZ4_compress_generic( /* Main Loop */ for ( ; ; ) { - int searchMatchNb = (1U << skipStrength) + 3; const BYTE* forwardIp = ip; const BYTE* ref; BYTE* token; + { + int step=1; + int searchMatchNb = (1U << skipStrength) + 3; - /* Find a match */ - do { - int step = searchMatchNb++ >> skipStrength; - U32 h = forwardH; - ip = forwardIp; - forwardIp += step; + /* Find a match */ + do { + U32 h = forwardH; + ip = forwardIp; + forwardIp += step; + step = searchMatchNb++ >> skipStrength; + if (unlikely (step>8)) step=8; // slows down uncompressible data; required for valid forwardIp - ref = LZ4_getPositionOnHash(h, ctx, tableType, base); - if (dict==usingExtDict) - { - if (ref<(const BYTE*)source) - { - refDelta = dictDelta; - lowLimit = dictionary; - } - else + if (unlikely(ip > mflimit)) goto _last_literals; + + ref = LZ4_getPositionOnHash(h, ctx, tableType, base); + if (dict==usingExtDict) { - refDelta = 0; - lowLimit = (const BYTE*)source; + if (ref<(const BYTE*)source) + { + refDelta = dictDelta; + lowLimit = dictionary; + } + else + { + refDelta = 0; + lowLimit = (const BYTE*)source; + } } - } - if (unlikely(ip > mflimit)) goto _last_literals; - forwardH = LZ4_hashPosition(forwardIp, tableType); - LZ4_putPositionOnHash(ip, h, ctx, tableType, base); + forwardH = LZ4_hashPosition(forwardIp, tableType); + LZ4_putPositionOnHash(ip, h, ctx, tableType, base); - } while ( ((tableType==byU16)? 0 : (ref + MAX_DISTANCE < ip)) || (A32(ref+refDelta) != A32(ip)) ); + } while ( ((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--; } // refDelta costs some performance + while ((ip>anchor) && (ref+refDelta > lowLimit) && (unlikely(ip[-1]==ref[refDelta-1]))) { ip--; ref--; } { /* Encode Literal length */ @@ -558,7 +563,7 @@ _next_match: if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit))) return 0; /* Check output limit */ *token += ML_MASK; matchLength -= ML_MASK; - for (; matchLength > 509 ; matchLength-=510) { *op++ = 255; *op++ = 255; } + for (; matchLength >= 510 ; matchLength-=510) { *op++ = 255; *op++ = 255; } if (matchLength >= 255) { matchLength-=255; *op++ = 255; } *op++ = (BYTE)matchLength; } diff --git a/programs/Makefile b/programs/Makefile index 53e4eb2..9fb6cd9 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -133,15 +133,17 @@ test-32: test-lz4 test-lz4c32 test-fullbench32 test-fuzzer32 test-mem32 test-lz4: lz4 datagen ./datagen | ./lz4 | ./lz4 -vdq > $(VOID) - ./datagen -g256MB | ./lz4 -B4D | ./lz4 -vdq > $(VOID) - ./datagen -g6GB | ./lz4 -vqB5D | ./lz4 -vdq > $(VOID) + ./datagen -g256MB | ./lz4 -vqB4D | ./lz4 -vdq > $(VOID) + ./datagen -g6GB | ./lz4 -vqB5D | ./lz4 -vdq > $(VOID) test-lz4c: lz4c datagen -test-lz4c32: lz4c32 datagen +test-lz4c32: lz4c32 lz4 datagen ./datagen | ./lz4c32 | ./lz4c32 -vdq > $(VOID) - ./datagen -g256MB | ./lz4c32 -B4D | ./lz4c32 -vdq > $(VOID) - ./datagen -g6GB | ./lz4c32 -vqB5D | ./lz4c32 -vdq > $(VOID) + ./datagen | ./lz4c32 | ./lz4 -vdq > $(VOID) + ./datagen -g256MB | ./lz4c32 -vqB4D | ./lz4c32 -vdq > $(VOID) + ./datagen -g256MB | ./lz4c32 -vqB4D | ./lz4 -vdq > $(VOID) + ./datagen -g6GB | ./lz4c32 -vqB5D | ./lz4c32 -vdq > $(VOID) test-fullbench: fullbench ./fullbench --no-prompt $(BENCH_NB) $(TEST_FILES) diff --git a/programs/datagen.c b/programs/datagen.c index 05eb7f0..0109d54 100644 --- a/programs/datagen.c +++ b/programs/datagen.c @@ -109,30 +109,58 @@ static unsigned int CDG_rand(U32* src) #define CDG_RANDCHAR (((CDG_rand(seed) >> 9) & 63) + '0') static void CDG_generate(U64 size, U32* seed, double proba) { - BYTE buff[128 KB + 1]; + BYTE fullbuff[32 KB + 128 KB + 1]; + BYTE* buff = fullbuff + 32 KB; U64 total=0; U32 P32 = (U32)(32768 * proba); U32 pos=0; U32 genBlockSize = 128 KB; + // Build initial prefix + while (pos<32 KB) + { + // Select : Literal (char) or Match (within 32K) + if (CDG_RAND15BITS < P32) + { + // Copy (within 64K) + U32 d; + int ref; + int length = CDG_RANDLENGTH + 4; + U32 offset = CDG_RAND15BITS + 1; + if (offset > pos) offset = pos; + ref = pos - offset; + d = pos + length; + while (pos < d) fullbuff[pos++] = fullbuff[ref++]; + } + else + { + // Literal (noise) + U32 d; + int length = CDG_RANDLENGTH; + d = pos + length; + while (pos < d) fullbuff[pos++] = CDG_RANDCHAR; + } + } + + // Generate compressible data + pos = 0; while (total < size) { if (size-total < 128 KB) genBlockSize = (U32)(size-total); total += genBlockSize; buff[genBlockSize] = 0; - *buff = CDG_RANDCHAR; - pos = 1; + pos = 0; while (pos pos) offset = pos; - if (pos + length > 128 KB ) length = 128 KB - pos; + if (pos + length > genBlockSize ) length = genBlockSize - pos; ref = pos - offset; d = pos + length; while (pos < d) buff[pos++] = buff[ref++]; @@ -142,7 +170,7 @@ static void CDG_generate(U64 size, U32* seed, double proba) // Literal (noise) U32 d; int length = CDG_RANDLENGTH; - if (pos + length > 128 KB) length = 128 KB - pos; + if (pos + length > genBlockSize) length = genBlockSize - pos; d = pos + length; while (pos < d) buff[pos++] = CDG_RANDCHAR; } @@ -150,6 +178,8 @@ static void CDG_generate(U64 size, U32* seed, double proba) pos=0; for (;pos+512<=genBlockSize;pos+=512) printf("%512.512s", buff+pos); for (;pos in_end) in_blockStart = in_buff; inSize = (unsigned int) fread(in_blockStart, (size_t)1, (size_t)blockSize, finput); if( inSize==0 ) break; // No more input : end of compression filesize += inSize; @@ -468,7 +468,11 @@ static int compress_file_blockDependency2(char* input_filename, char* output_fil if (sizeCheck!=(size_t)(4)) EXM_THROW(36, "Write error : cannot write block checksum"); } } - in_blockStart += inSize; + { + size_t sizeToMove = 64 KB; + if (inSize < 64 KB) sizeToMove = inSize; + nextBlockFunction(ctx, in_blockStart - sizeToMove, sizeToMove); + } } // End of Stream mark -- cgit v0.12 From 3b92842904f656d4991179e58fd192b0457fe981 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Tue, 10 Jun 2014 21:45:25 +0100 Subject: improved compression ratio for long streams in 32 bits mode --- lz4.c | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-) diff --git a/lz4.c b/lz4.c index beff5a7..d2906aa 100755 --- a/lz4.c +++ b/lz4.c @@ -454,7 +454,7 @@ static int LZ4_compress_generic( break; case withPrefix64k: base = (const BYTE*)source - dictPtr->currentOffset; - lowLimit = (const BYTE*)source - 64 KB; + lowLimit = (const BYTE*)source - dictPtr->dictSize; if (lowLimit < base) lowLimit = base; break; case usingExtDict: @@ -687,7 +687,7 @@ int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize) if (dictSize < MINMATCH) { - dict->dictionary = (const BYTE*)dictionary-1; + dict->dictionary = NULL; dict->dictSize = 0; return 1; } @@ -711,7 +711,7 @@ int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize) void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const BYTE* src) { if ((LZ4_dict->currentOffset > 0x80000000) || - (src - LZ4_dict->currentOffset > src)) /* address space overflow */ + ((size_t)LZ4_dict->currentOffset > (size_t)src)) /* address space overflow */ { /* rescale hash table */ U32 delta = LZ4_dict->currentOffset - 64 KB; @@ -723,7 +723,7 @@ void LZ4_renormDictT(LZ4_dict_t_internal* LZ4_dict, const BYTE* src) } LZ4_dict->currentOffset = 64 KB; LZ4_dict->dictionary = LZ4_dict->dictionary + LZ4_dict->dictSize - 64 KB; - LZ4_dict->dictSize = 64 KB; + LZ4_dict->dictSize = 64 KB; } } @@ -733,8 +733,8 @@ int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_stream; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - const BYTE* smallest = dictEnd; - if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; + const BYTE* smallest = (const BYTE*) source; + if ((streamPtr->dictSize>0) && (smallest > dictEnd)) smallest = dictEnd; LZ4_renormDictT(streamPtr, smallest); if (dictEnd == (const BYTE*)source) @@ -759,9 +759,9 @@ int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, c LZ4_dict_t_internal* streamPtr = (LZ4_dict_t_internal*)LZ4_stream; const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; - const BYTE* smallest = dictEnd; - if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; - LZ4_renormDictT((LZ4_dict_t_internal*)LZ4_stream, smallest); + const BYTE* smallest = (const BYTE*) source; + if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd; + LZ4_renormDictT(streamPtr, smallest); if (dictEnd == (const BYTE*)source) { @@ -815,8 +815,6 @@ int LZ4_moveDict (void* LZ4_dict, char* safeBuffer, int dictSize) dict->dictionary = (const BYTE*)safeBuffer; dict->dictSize = (U32)dictSize; - LZ4_renormDictT(dict, (const BYTE*)safeBuffer); - return 1; } -- cgit v0.12 From 0c62103105143eaaf0fa5caae09e65318063a417 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 11 Jun 2014 21:40:16 +0100 Subject: restored LZ4 HC streaming mode --- lz4.c | 6 ++++-- lz4hc.c | 6 ++++-- programs/Makefile | 4 +++- programs/lz4io.c | 54 +++++++++++++++++++++++++++++++++++++++++++----------- 4 files changed, 54 insertions(+), 16 deletions(-) diff --git a/lz4.c b/lz4.c index d2906aa..e1bcb25 100755 --- a/lz4.c +++ b/lz4.c @@ -47,8 +47,9 @@ **************************************/ /* 32 or 64 bits ? */ #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \ - || defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \ - || defined(__64BIT__) || defined(_LP64) || defined(__LP64__) \ + || 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 @@ -59,6 +60,7 @@ * Little Endian or Big Endian ? * Overwrite the #define below if you know your architecture endianess */ +#include /* Apparently required to detect endianess */ #if defined (__GLIBC__) # include # if (__BYTE_ORDER == __BIG_ENDIAN) diff --git a/lz4hc.c b/lz4hc.c index e84de2b..6086749 100644 --- a/lz4hc.c +++ b/lz4hc.c @@ -54,8 +54,9 @@ **************************************/ /* 32 or 64 bits ? */ #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \ - || defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \ - || defined(__64BIT__) || defined(_LP64) || defined(__LP64__) \ + || 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 @@ -66,6 +67,7 @@ * Little Endian or Big Endian ? * Overwrite the #define below if you know your architecture endianess */ +#include /* Apparently required to detect endianess */ #if defined (__GLIBC__) # include # if (__BYTE_ORDER == __BIG_ENDIAN) diff --git a/programs/Makefile b/programs/Makefile index 9fb6cd9..35bfd06 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -158,8 +158,10 @@ test-fuzzer32: fuzzer32 ./fuzzer32 --no-prompt test-mem: lz4 datagen - ./datagen -g256M > tmp + ./datagen -g256MB > tmp valgrind ./lz4 -B4D -f tmp /dev/null + ./datagen -g16MB > tmp + valgrind ./lz4 -9 -B5D -f tmp /dev/null rm tmp test-mem32: lz4c32 datagen diff --git a/programs/lz4io.c b/programs/lz4io.c index a0dae68..650681b 100644 --- a/programs/lz4io.c +++ b/programs/lz4io.c @@ -365,12 +365,32 @@ int LZ4IO_compressFilename_Legacy(char* input_filename, char* output_filename, i } -static int compress_file_blockDependency2(char* input_filename, char* output_filename, int compressionlevel) +static void* LZ4IO_LZ4_createStream (const char* inputBuffer) { - void* (*initFunction) (); - int (*compressionFunction)(void*, const char*, char*, int, int); - int (*freeFunction) (void*); + (void)inputBuffer; + return LZ4_createStream(); +} + +static int LZ4IO_LZ4_compress_limitedOutput_continue (void* ctx, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) +{ + (void)compressionLevel; + return LZ4_compress_limitedOutput_continue(ctx, source, dest, inputSize, maxOutputSize); +} + +static int LZ4IO_LZ4_slideInputBufferHC (void* ctx, char* buffer, int size) +{ + (void)size; (void)buffer; + LZ4_slideInputBufferHC (ctx); + return 1; +} + + +static int compress_file_blockDependency(char* input_filename, char* output_filename, int compressionlevel) +{ + void* (*initFunction) (const char*); + int (*compressionFunction)(void*, const char*, char*, int, int, int); int (*nextBlockFunction) (void*, char*, int); + int (*freeFunction) (void*); void* ctx; unsigned long long filesize = 0; unsigned long long compressedfilesize = 0; @@ -388,10 +408,20 @@ static int compress_file_blockDependency2(char* input_filename, char* output_fil start = clock(); if ((displayLevel==2) && (compressionlevel>=3)) displayLevel=3; - initFunction = LZ4_createStream; - compressionFunction = LZ4_compress_limitedOutput_continue; - nextBlockFunction = LZ4_moveDict; - freeFunction = LZ4_free; + if (compressionlevel<3) + { + initFunction = LZ4IO_LZ4_createStream; + compressionFunction = LZ4IO_LZ4_compress_limitedOutput_continue; + nextBlockFunction = LZ4_moveDict; + freeFunction = LZ4_free; + } + else + { + initFunction = LZ4_createHC; + compressionFunction = LZ4_compressHC2_limitedOutput_continue; + nextBlockFunction = LZ4IO_LZ4_slideInputBufferHC; + freeFunction = LZ4_free; + } get_fileHandle(input_filename, output_filename, &finput, &foutput); blockSize = LZ4S_GetBlockSize_FromBlockId (blockSizeId); @@ -402,8 +432,9 @@ static int compress_file_blockDependency2(char* input_filename, char* output_fil out_buff = (char*)malloc(blockSize+CACHELINE); if (!in_buff || !out_buff) EXM_THROW(31, "Allocation error : not enough memory"); in_blockStart = in_buff + 64 KB; + if (compressionlevel>=3) in_blockStart = in_buff; if (streamChecksum) streamChecksumState = XXH32_init(LZ4S_CHECKSUM_SEED); - ctx = initFunction(); + ctx = initFunction(in_buff); // Write Archive Header *(unsigned int*)out_buff = LITTLE_ENDIAN_32(LZ4S_MAGICNUMBER); // Magic Number, in Little Endian convention @@ -434,7 +465,7 @@ static int compress_file_blockDependency2(char* input_filename, char* output_fil if (streamChecksum) XXH32_update(streamChecksumState, in_blockStart, inSize); // Compress Block - outSize = compressionFunction(ctx, in_blockStart, out_buff+4, inSize, inSize-1); + outSize = compressionFunction(ctx, in_blockStart, out_buff+4, inSize, inSize-1, compressionlevel); if (outSize > 0) compressedfilesize += outSize+4; else compressedfilesize += inSize+4; if (blockChecksum) compressedfilesize+=4; DISPLAYLEVEL(3, "==> %.2f%% ", (double)compressedfilesize/filesize*100); @@ -472,6 +503,7 @@ static int compress_file_blockDependency2(char* input_filename, char* output_fil size_t sizeToMove = 64 KB; if (inSize < 64 KB) sizeToMove = inSize; nextBlockFunction(ctx, in_blockStart - sizeToMove, sizeToMove); + if (compressionlevel>=3) in_blockStart = in_buff + 64 KB; } } @@ -530,7 +562,7 @@ int LZ4IO_compressFilename(char* input_filename, char* output_filename, int comp void* streamChecksumState=NULL; // Branch out - if (blockIndependence==0) return compress_file_blockDependency2(input_filename, output_filename, compressionLevel); + if (blockIndependence==0) return compress_file_blockDependency(input_filename, output_filename, compressionLevel); // Init start = clock(); -- cgit v0.12 From 1c5a6304a2ab4d8b8d3f30cc371df10e537431ae Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 11 Jun 2014 22:02:46 +0100 Subject: CLI : can select compression level > 9 --- lz4hc.h | 1 + programs/Makefile | 2 +- programs/lz4cli.c | 27 +++++++++++++-------------- 3 files changed, 15 insertions(+), 15 deletions(-) diff --git a/lz4hc.h b/lz4hc.h index b810978..deb2394 100644 --- a/lz4hc.h +++ b/lz4hc.h @@ -104,6 +104,7 @@ They just use the externally allocated memory area instead of allocating their o /************************************** 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); diff --git a/programs/Makefile b/programs/Makefile index 35bfd06..811dda2 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -165,6 +165,6 @@ test-mem: lz4 datagen rm tmp test-mem32: lz4c32 datagen -# unfortunately, valgrind doesn't work with non-native binary. If someone knows how to valgrind-test a 32-bits exe on a 64-bits system... +# unfortunately, valgrind doesn't seem to work with non-native binary. If someone knows how to do a valgrind-test on a 32-bits exe with a 64-bits system... endif diff --git a/programs/lz4cli.c b/programs/lz4cli.c index e05a9a9..fd2721d 100644 --- a/programs/lz4cli.c +++ b/programs/lz4cli.c @@ -344,6 +344,19 @@ int main(int argc, char** argv) if (*argument=='s') { displayLevel=1; continue; } // -s (silent mode) #endif // DISABLE_LZ4C_LEGACY_OPTIONS + if ((*argument>='0') && (*argument<='9')) + { + cLevel = 0; + while ((*argument >= '0') && (*argument <= '9')) + { + cLevel *= 10; + cLevel += *argument - '0'; + argument++; + } + argument--; + continue; + } + switch(argument[0]) { // Display help @@ -354,20 +367,6 @@ int main(int argc, char** argv) // Compression (default) case 'z': forceCompress = 1; break; - // Compression level - case '0': - case '1': - case '2': - case '3': - case '4': - case '5': - case '6': - case '7': - case '8': - case '9': - case 'A': /* non documented (hidden) */ - cLevel=*argument -'0'; break; - // Use Legacy format (for Linux kernel compression) case 'l': legacy_format=1; break; -- cgit v0.12