From 8d66dd7cd52c69d4542eb910bd8743ef95fa9d8c Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Sat, 21 Jun 2014 17:01:15 +0100 Subject: Fixed : using loadDict() with small dictionaries --- lz4.c | 73 ++++++++++++++++++++++++++++------------------------ programs/fullbench.c | 8 +++--- programs/fuzzer.c | 37 ++++++++++++++++++-------- 3 files changed, 69 insertions(+), 49 deletions(-) mode change 100755 => 100644 lz4.c mode change 100755 => 100644 programs/fullbench.c diff --git a/lz4.c b/lz4.c old mode 100755 new mode 100644 index 957b907..6385aec --- a/lz4.c +++ b/lz4.c @@ -259,7 +259,8 @@ typedef struct { typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; typedef enum { byPtr, byU32, byU16 } tableType_t; -typedef enum { noDict = 0, withPrefix64k, withPrefixSmall, usingExtDict, usingSmallDict } dict_directive; +typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; +typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; typedef enum { full = 0, partial = 1 } earlyEnd_directive; @@ -433,13 +434,15 @@ static int LZ4_compress_generic( limitedOutput_directive outputLimited, tableType_t tableType, - dict_directive dict) + dict_directive dict, + dictIssue_directive dictIssue) { LZ4_stream_t_internal* const dictPtr = (LZ4_stream_t_internal*)ctx; const BYTE* ip = (const BYTE*) source; const BYTE* base; const BYTE* lowLimit; + const BYTE* const lowRefLimit = ip - dictPtr->dictSize; const BYTE* const dictionary = dictPtr->dictionary; const BYTE* const dictEnd = dictionary + dictPtr->dictSize; const size_t dictDelta = dictEnd - (const BYTE*)source; @@ -465,12 +468,10 @@ static int LZ4_compress_generic( lowLimit = (const BYTE*)source; break; case withPrefix64k: - case withPrefixSmall: base = (const BYTE*)source - dictPtr->currentOffset; lowLimit = (const BYTE*)source - dictPtr->dictSize; break; case usingExtDict: - case usingSmallDict: base = (const BYTE*)source - dictPtr->currentOffset; lowLimit = (const BYTE*)source; break; @@ -503,7 +504,7 @@ static int LZ4_compress_generic( if (unlikely(forwardIp > mflimit)) goto _last_literals; ref = LZ4_getPositionOnHash(h, ctx, tableType, base); - if ((dict==usingExtDict) || (dict==usingSmallDict)) + if (dict==usingExtDict) { if (ref<(const BYTE*)source) { @@ -519,8 +520,7 @@ static int LZ4_compress_generic( forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx, tableType, base); - } while ( ((dict==withPrefixSmall) ? (ref < lowLimit) : 0) - || ((dict==usingSmallDict) && (refDelta) ? (ref < lowLimit) : 0) + } while ( ((dictIssue==dictSmall) ? (ref < lowRefLimit) : 0) || ((tableType==byU16) ? 0 : (ref + MAX_DISTANCE < ip)) || (A32(ref+refDelta) != A32(ip)) ); } @@ -532,7 +532,8 @@ static int LZ4_compress_generic( /* Encode Literal length */ unsigned litLength = (unsigned)(ip - anchor); token = op++; - if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit))) return 0; /* Check output limit */ + if ((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; @@ -543,12 +544,12 @@ static int LZ4_compress_generic( else *token = (BYTE)(litLength<=ML_MASK) { - if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit))) 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 >= 510 ; matchLength-=510) { *op++ = 255; *op++ = 255; } @@ -597,7 +599,7 @@ _next_match: /* Test next position */ ref = LZ4_getPosition(ip, ctx, tableType, base); - if ((dict==usingExtDict) || (dict==usingSmallDict)) + if (dict==usingExtDict) { if (ref<(const BYTE*)source) { @@ -611,8 +613,7 @@ _next_match: } } LZ4_putPosition(ip, ctx, tableType, base); - if ( ((dict==withPrefixSmall) ? (ref>=lowLimit) : 1) - && ((dict==usingSmallDict) && (refDelta) ? (ref>=lowLimit) : 1) + if ( ((dictIssue==dictSmall) ? (ref>=lowRefLimit) : 1) && (ref+MAX_DISTANCE>=ip) && (A32(ref+refDelta)==A32(ip)) ) { token=op++; *token=0; goto _next_match; } @@ -625,7 +626,8 @@ _last_literals: /* Encode Last Literals */ { int lastRun = (int)(iend - anchor); - if ((outputLimited) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */ + if ((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<currentOffset - 64 KB; + const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; int i; for (i=0; ihashTable[i] -= delta; } LZ4_dict->currentOffset = 64 KB; - LZ4_dict->dictionary = LZ4_dict->dictionary + LZ4_dict->dictSize - 64 KB; - LZ4_dict->dictSize = 64 KB; + if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB; + LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; } } @@ -777,9 +780,9 @@ FORCE_INLINE int LZ4_compress_continue_generic (void* LZ4_stream, const char* so { int result; if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) - result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefixSmall); + result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, dictSmall); else - result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k); + result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, noDictIssue); streamPtr->dictSize += (U32)inputSize; streamPtr->currentOffset += (U32)inputSize; return result; @@ -789,9 +792,9 @@ FORCE_INLINE int LZ4_compress_continue_generic (void* LZ4_stream, const char* so { int result; if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) - result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingSmallDict); + result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, dictSmall); else - result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict); + result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, noDictIssue); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; streamPtr->currentOffset += (U32)inputSize; @@ -822,7 +825,7 @@ int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; LZ4_renormDictT((LZ4_stream_t_internal*)LZ4_dict, smallest); - result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict); + result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue); streamPtr->dictionary = (const BYTE*)source; streamPtr->dictSize = (U32)inputSize; @@ -882,10 +885,10 @@ FORCE_INLINE int LZ4_decompress_generic( BYTE* const oend = op + outputSize; BYTE* cpy; BYTE* oexit = op + targetOutputSize; - const BYTE* const lowLimit = (const BYTE*) dest - dictSize; + const BYTE* const lowLimit = (const BYTE*)dest - dictSize; const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize; -#define OLD +//#define OLD #ifdef OLD const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */ #else @@ -893,6 +896,8 @@ FORCE_INLINE int LZ4_decompress_generic( #endif static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; + const int checkOffset = (endOnInput) && (dictSize < (int)(64 KB)); + /* Special cases */ if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */ @@ -942,7 +947,7 @@ FORCE_INLINE int LZ4_decompress_generic( /* get offset */ LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2; - if ((endOnInput) && (unlikely(ref < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */ + if ((checkOffset) && (unlikely(ref < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */ /* get matchlength */ if ((length=(token&ML_MASK)) == ML_MASK) @@ -1044,7 +1049,7 @@ int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSi int LZ4_decompress_fast(const char* source, char* dest, int originalSize) { - return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 64 KB); + return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 0); } /* streaming decompression functions */ @@ -1207,9 +1212,9 @@ int LZ4_compress_withState (void* state, const char* source, char* dest, int inp MEM_INIT(state, 0, LZ4_STREAMSIZE); if (inputSize < (int)LZ4_64KLIMIT) - return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict); + return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue); else - return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict); + return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); } int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize) @@ -1218,9 +1223,9 @@ int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* MEM_INIT(state, 0, LZ4_STREAMSIZE); if (inputSize < (int)LZ4_64KLIMIT) - return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict); + return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue); else - return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict); + return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); } /* Obsolete streaming decompression functions */ diff --git a/programs/fullbench.c b/programs/fullbench.c old mode 100755 new mode 100644 index 154de78..f8a85ef --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -506,7 +506,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) double averageTime; int milliTime; - PROGRESS("%1i-%-25.25s : %9i ->\r", loopNb, compressorName, (int)benchedSize); + PROGRESS("%1i-%-26.26s : %9i ->\r", loopNb, compressorName, (int)benchedSize); { size_t i; for (i=0; i %9i (%5.2f%%),%7.1f MB/s\r", loopNb, compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + PROGRESS("%1i-%-26.26s : %9i -> %9i (%5.2f%%),%7.1f MB/s\r", loopNb, compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); } if (ratio<100.) - DISPLAY("%-27.27s : %9i -> %9i (%5.2f%%),%7.1f MB/s\n", compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + DISPLAY("%-28.28s : %9i -> %9i (%5.2f%%),%7.1f MB/s\n", compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); else - DISPLAY("%-27.27s : %9i -> %9i (%5.1f%%),%7.1f MB/s\n", compressorName, (int)benchedSize, (int)cSize, ratio, (double)benchedSize / bestTime / 1000.); + DISPLAY("%-28.28s : %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; diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 6035213..dbf6c2f 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -210,6 +210,9 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { int displayRefresh; + // init + memset(&LZ4dict, 0, sizeof(LZ4dict)); + // Create compressible test buffer CNBuffer = malloc(COMPRESSIBLE_NOISE_LENGTH); FUZ_fillCompressibleNoiseBuffer(CNBuffer, COMPRESSIBLE_NOISE_LENGTH, compressibility, &randState); @@ -221,16 +224,30 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { { case 0: displayRefresh = nbCycles+1; break; case 1: displayRefresh=FUZ_MAX(1, nbCycles / 100); break; - case 2: displayRefresh=99; break; + case 2: displayRefresh=89; break; default : displayRefresh=1; } // move to startCycle for (cycleNb = 0; cycleNb < startCycle; cycleNb++) { - FUZ_rand(&randState); - FUZ_rand(&randState); - FUZ_rand(&randState); + // synd rand & dict + int dictSize, blockSize, blockStart; + char* dict; + char* block; + + blockSize = FUZ_rand(&randState) % FUZ_MAX_BLOCK_SIZE; + blockStart = FUZ_rand(&randState) % (COMPRESSIBLE_NOISE_LENGTH - blockSize); + dictSize = FUZ_rand(&randState) % FUZ_MAX_DICT_SIZE; + if (dictSize > blockStart) dictSize = blockStart; + block = ((char*)CNBuffer) + blockStart; + dict = block - dictSize; + LZ4_loadDict(&LZ4dict, dict, dictSize); + LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); + LZ4_loadDict(&LZ4dict, dict, dictSize); + LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); + LZ4_loadDict(&LZ4dict, dict, dictSize); + LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); } // Test loop @@ -432,25 +449,23 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_withPrefix64k corrupted decoded data"); - // Compress using dictionary + // Compress using External dictionary FUZ_DISPLAYTEST; - dict -= 9; + dict -= 9; // Separation, so it is an ExtDict if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; - 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_continue failed"); FUZ_DISPLAYTEST; - 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_continue should fail : one missing byte for output buffer"); + FUZ_CHECKTEST(ret>0, "LZ4_compress_limitedOutput_continue using ExtDict should fail : one missing byte for output buffer"); FUZ_DISPLAYTEST; - 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!=blockContinueCompressedSize, "LZ4_compress_limitedOutput_compressed size is different (%i != %i)", ret, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_limitedOutput_continue should work : enough size available within output buffer"); // Decompress with dictionary as external @@ -494,7 +509,7 @@ int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) { { decodedBuffer[blockSize-10] = 0; ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, blockSize-10, dict, dictSize); - FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe_usingDict should have failed : not enough output size (-10 byte)"); + FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe_usingDict should have failed : output buffer too small (-10 byte)"); FUZ_CHECKTEST(decodedBuffer[blockSize-10], "LZ4_decompress_safe_usingDict overrun specified output buffer size (-10 byte) (blockSize=%i)", blockSize); } -- cgit v0.12