From 3dab5f476a2e5a0cd4cd9a859e94a5110abda23d Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 20 Oct 2014 01:08:21 +0100 Subject: LZ4 HC : External Dictionary compression : First implementation --- lz4hc.c | 135 +++++++++++++++++++++++++++++++++++------------------- lz4hc.h | 0 programs/fuzzer.c | 100 +++++++++++++++++++++++++++------------- 3 files changed, 156 insertions(+), 79 deletions(-) mode change 100644 => 100755 lz4hc.h diff --git a/lz4hc.c b/lz4hc.c index 5e204c6..72739a7 100644 --- a/lz4hc.c +++ b/lz4hc.c @@ -268,11 +268,10 @@ typedef struct #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d> ((MINMATCH*8)-HASH_LOG)) -#define HASH_VALUE(p) HASH_FUNCTION(A32(p)) -#define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base) #define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK] #define GETNEXT(p) ((p) - (size_t)DELTANEXT(p)) +static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(A32(ptr)); } /************************************** Private functions @@ -363,12 +362,12 @@ FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) U16* chainTable = hc4->chainTable; U32* HashTable = hc4->hashTable; const BYTE* const base = hc4->base; - const U32 target = ip - base; + const U32 target = (U32)(ip - base); U32 idx = hc4->nextToUpdate; while(idx < target) { - U32 h = HASH_VALUE(base+idx); + U32 h = LZ4HC_hashPtr(base+idx); size_t delta = idx - HashTable[h]; if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; chainTable[idx & 0xFFFF] = (U16)delta; @@ -398,10 +397,25 @@ static size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* co } -FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, - const BYTE* ip, const BYTE* iLimit, - const BYTE** matchpos, - const int maxNbAttempts) +static void LZ4HC_setExternalDict(LZ4HC_Data_Structure* ctxPtr, const BYTE* newBlock) +{ + if (ctxPtr->end >= ctxPtr->base + 4) + LZ4HC_Insert (ctxPtr, ctxPtr->end-3); // finish referencing dictionary content + // Note : need to handle risk of index overflow + // Use only one memory segment for dict, so any previous External Dict is lost at this stage + ctxPtr->lowLimit = ctxPtr->dictLimit; + ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); + ctxPtr->dictBase = ctxPtr->base; + ctxPtr->base = newBlock - ctxPtr->dictLimit; + ctxPtr->end = newBlock; + ctxPtr->nextToUpdate = ctxPtr->dictLimit; // reference table must skip to from beginning of block +} + + +FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, // Index table will be updated + const BYTE* ip, const BYTE* const iLimit, + const BYTE** matchpos, + const int maxNbAttempts) { U16* const chainTable = hc4->chainTable; U32* const HashTable = hc4->hashTable; @@ -409,24 +423,41 @@ FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* const dictBase = hc4->dictBase; const U32 dictLimit = hc4->dictLimit; U32 matchIndex; - const U32 idxLow = (ip-base) > 64 KB ? (ip - base) - 64 KB : 0; + const U32 idxLow = (ip-base) > 64 KB ? (U32)(ip - base) - 64 KB : 0; const BYTE* match; int nbAttempts=maxNbAttempts; size_t ml=0; /* HC4 match finder */ LZ4HC_Insert(hc4, ip); - matchIndex = HashTable[HASH_VALUE(ip)]; + matchIndex = HashTable[LZ4HC_hashPtr(ip)]; while ((matchIndex>idxLow) && (nbAttempts)) { nbAttempts--; - match = ((matchIndex= dictLimit) { - size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH; - if (mlt > ml) { ml = mlt; *matchpos = match; } + match = base + matchIndex; + if (*(match+ml) == *(ip+ml) + && (A32(match) == A32(ip))) + { + size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH; + if (mlt > ml) { ml = mlt; *matchpos = match; } + } + } + else + { + match = dictBase + matchIndex; + if (A32(match) == A32(ip)) + { + size_t mlt; + const BYTE* vLimit = ip + (dictLimit - matchIndex); + if (vLimit > iLimit) vLimit = iLimit; + mlt = LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH; + if ((ip+mlt == vLimit) && (vLimit < iLimit)) + mlt += LZ4HC_CommonLength(ip+mlt, base+dictLimit, iLimit); + if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; } // virtual matchpos + } } matchIndex -= chainTable[matchIndex & 0xFFFF]; } @@ -438,8 +469,8 @@ FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( LZ4HC_Data_Structure* hc4, const BYTE* ip, - const BYTE* startLimit, - const BYTE* matchlimit, + const BYTE* iLowLimit, + const BYTE* iHighLimit, int longest, const BYTE** matchpos, const BYTE** startpos, @@ -448,34 +479,57 @@ FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( U16* const chainTable = hc4->chainTable; U32* const HashTable = hc4->hashTable; const BYTE* const base = hc4->base; + const U32 dictLimit = hc4->dictLimit; + const U32 dictLowLimit = hc4->lowLimit; + const BYTE* const dictBase = hc4->dictBase; const BYTE* match; - int matchIndex; - const int idxLow = (ip-base) > 64 KB ? (ip-base) - 64 KB : 0; + U32 matchIndex; + const U32 idxLow = (ip-base) > 64 KB ? (U32)(ip-base) - 64 KB : 0; int nbAttempts = maxNbAttempts; - int delta = (int)(ip-startLimit); + int delta = (int)(ip-iLowLimit); /* First Match */ LZ4HC_Insert(hc4, ip); - matchIndex = HashTable[HASH_VALUE(ip)]; + matchIndex = HashTable[LZ4HC_hashPtr(ip)]; while ((matchIndex>idxLow) && (nbAttempts)) { nbAttempts--; - match = base + matchIndex; - if (*(startLimit + longest) == *(match - delta + longest)) - if (A32(match) == A32(ip)) + if (matchIndex >= dictLimit) { - const BYTE* startt = ip; - const BYTE* tmpMatch = match; - const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, matchlimit); + match = base + matchIndex; + if (*(iLowLimit + longest) == *(match - delta + longest)) + if (A32(match) == A32(ip)) + { + const BYTE* startt = ip; + const BYTE* tmpMatch = match; + const BYTE* const matchEnd = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, iHighLimit); - while ((startt>startLimit) && (tmpMatch > hc4->inputBuffer) && (startt[-1] == tmpMatch[-1])) {startt--; tmpMatch--;} + while ((startt>iLowLimit) && (tmpMatch > iLowLimit) && (startt[-1] == tmpMatch[-1])) {startt--; tmpMatch--;} - if ((ipt-startt) > longest) + if ((matchEnd-startt) > longest) + { + longest = (int)(matchEnd-startt); + *matchpos = tmpMatch; + *startpos = startt; + } + } + } + else + { + match = dictBase + matchIndex; + if (A32(match) == A32(ip)) { - longest = (int)(ipt-startt); - *matchpos = tmpMatch; - *startpos = startt; + size_t mlt; + int back=0; + const BYTE* vLimit = ip + (dictLimit - matchIndex); + if (vLimit > iHighLimit) vLimit = iHighLimit; + mlt = LZ4HC_CommonLength(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH; + if ((ip+mlt == vLimit) && (vLimit < iHighLimit)) + mlt += LZ4HC_CommonLength(ip+mlt, base+dictLimit, iHighLimit); + while ((ip+back > iLowLimit) && (matchIndex+back > dictLowLimit) && (ip[back-1] == match[back-1])) back--; + mlt -= back; + if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; } } } matchIndex -= chainTable[matchIndex & 0xFFFF]; @@ -485,19 +539,6 @@ FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( } -static void LZ4HC_setExternalDict(LZ4HC_Data_Structure* ctxPtr, const BYTE* newBlock) -{ - LZ4HC_Insert (ctxPtr, ctxPtr->end-3); // finish referencing dictionary content - // Use only one memory segment for dict, so any previous External Dict is lost at this stage - ctxPtr->lowLimit = ctxPtr->dictLimit; - ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); - ctxPtr->dictBase = ctxPtr->base; - ctxPtr->base = newBlock - ctxPtr->dictLimit; - ctxPtr->end = newBlock; - ctxPtr->nextToUpdate = ctxPtr->dictLimit; // reference table must skip to from beginning of block -} - - typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; FORCE_INLINE int LZ4HC_encodeSequence ( @@ -817,7 +858,7 @@ void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) { LZ4HC_init ((LZ4HC_Data_Structure*) LZ4_streamHCPtr, (const BYTE*) dictionary); - LZ4HC_Insert ((LZ4HC_Data_Structure*) LZ4_streamHCPtr, (const BYTE*)dictionary +(dictSize-3)); + if (dictSize >= 4) LZ4HC_Insert ((LZ4HC_Data_Structure*) LZ4_streamHCPtr, (const BYTE*)dictionary +(dictSize-3)); ((LZ4HC_Data_Structure*) LZ4_streamHCPtr)->end = (const BYTE*)dictionary + dictSize; return 1; } @@ -845,7 +886,7 @@ int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictS LZ4HC_Data_Structure* sp = (LZ4HC_Data_Structure*)LZ4_streamHCPtr; if (dictSize > 64 KB) dictSize = 64 KB; if (dictSize < 0) dictSize = 0; - if (dictSize > (sp->end - sp->base)) dictSize = sp->end - sp->base; + if (dictSize > (sp->end - sp->base)) dictSize = (int)(sp->end - sp->base); memcpy(safeBuffer, sp->end - dictSize, dictSize); LZ4_loadDictHC(LZ4_streamHCPtr, safeBuffer, dictSize); return dictSize; diff --git a/lz4hc.h b/lz4hc.h old mode 100644 new mode 100755 diff --git a/programs/fuzzer.c b/programs/fuzzer.c index cc73262..cf56251 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -263,7 +263,7 @@ _overflowError: } -static void FUZ_displayUpdate(int testNb) +static void FUZ_displayUpdate(unsigned testNb) { if ((FUZ_GetMilliSpan(g_time) > g_refreshRate) || (g_displayLevel>=3)) { @@ -274,7 +274,7 @@ static void FUZ_displayUpdate(int testNb) } -static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibility) +static int FUZ_test(U32 seed, const U32 nbCycles, const U32 startCycle, const double compressibility) { unsigned long long bytes = 0; unsigned long long cbytes = 0; @@ -283,15 +283,17 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili void* CNBuffer; char* compressedBuffer; char* decodedBuffer; -# define FUZ_max LZ4_COMPRESSBOUND(LEN) - 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++; g_displayLevel<3 ? 0 : printf("%2i\b\b", testNb); if (g_displayLevel==4) fflush(stdout); } +# define FUZ_max LZ4_COMPRESSBOUND(LEN) + int ret; + unsigned cycleNb; +# define FUZ_CHECKTEST(cond, ...) if (cond) { printf("Test %u : ", testNb); printf(__VA_ARGS__); \ + printf(" (seed %u, cycle %u) \n", seed, cycleNb); goto _output_error; } +# define FUZ_DISPLAYTEST { testNb++; g_displayLevel<3 ? 0 : printf("%2u\b\b", testNb); if (g_displayLevel==4) fflush(stdout); } void* stateLZ4 = malloc(LZ4_sizeofState()); void* stateLZ4HC = malloc(LZ4_sizeofStateHC()); void* LZ4continue; LZ4_stream_t LZ4dict; + LZ4_streamHC_t LZ4dictHC; U32 crcOrig, crcCheck; U32 coreRandState = seed; U32 randState = coreRandState ^ PRIME3; @@ -303,21 +305,19 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili // Create compressible test buffer CNBuffer = malloc(COMPRESSIBLE_NOISE_LENGTH); FUZ_fillCompressibleNoiseBuffer(CNBuffer, COMPRESSIBLE_NOISE_LENGTH, compressibility, &randState); - compressedBuffer = malloc(LZ4_compressBound(FUZ_MAX_BLOCK_SIZE)); - decodedBuffer = malloc(FUZ_MAX_DICT_SIZE + FUZ_MAX_BLOCK_SIZE); + compressedBuffer = (char*)malloc(LZ4_compressBound(FUZ_MAX_BLOCK_SIZE)); + decodedBuffer = (char*)malloc(FUZ_MAX_DICT_SIZE + FUZ_MAX_BLOCK_SIZE); // move to startCycle for (cycleNb = 0; cycleNb < startCycle; cycleNb++) { - // synd rand & dict - int dictSize, blockSize, blockStart; - char* dict; - char* block; - (void)FUZ_rand(&coreRandState); if (0) // some problems related to dictionary re-use; in this case, enable this loop { + int dictSize, blockSize, blockStart; + char* dict; + char* block; FUZ_displayUpdate(cycleNb); randState = coreRandState ^ PRIME3; blockSize = FUZ_rand(&randState) % FUZ_MAX_BLOCK_SIZE; @@ -338,7 +338,7 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili // Test loop for (cycleNb = startCycle; cycleNb < nbCycles; cycleNb++) { - int testNb = 0; + U32 testNb = 0; char* dict; char* block; int dictSize, blockSize, blockStart, compressedSize, HCcompressedSize; @@ -506,8 +506,8 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili // Compress using dictionary FUZ_DISPLAYTEST; LZ4continue = LZ4_create (dict); - LZ4_compress_continue (LZ4continue, dict, compressedBuffer, dictSize); // Just to fill hash tables - blockContinueCompressedSize = LZ4_compress_continue (LZ4continue, block, compressedBuffer, blockSize); + LZ4_compress_continue ((LZ4_stream_t*)LZ4continue, dict, compressedBuffer, dictSize); // Just to fill hash tables + blockContinueCompressedSize = LZ4_compress_continue ((LZ4_stream_t*)LZ4continue, block, compressedBuffer, blockSize); FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_continue failed"); free (LZ4continue); @@ -534,7 +534,7 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili // Compress using External dictionary FUZ_DISPLAYTEST; - dict -= 9; // Separation, so it is an ExtDict + dict -= (FUZ_rand(&randState) & 0xF) + 1; // Separation, so it is an ExtDict if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; LZ4_loadDict(&LZ4dict, dict, dictSize); blockContinueCompressedSize = LZ4_compress_continue(&LZ4dict, block, compressedBuffer, blockSize); @@ -563,7 +563,6 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili 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 (dict %i)", dictSize); @@ -588,23 +587,60 @@ static int FUZ_test(U32 seed, int nbCycles, int startCycle, double compressibili FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_safe_usingDict overrun specified output buffer size"); FUZ_DISPLAYTEST; - if (blockSize > 10) { - 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 : 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); + U32 missingBytes = (FUZ_rand(&randState) & 0xF) + 2; + if ((U32)blockSize > missingBytes) + { + decodedBuffer[blockSize-missingBytes] = 0; + ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, blockSize-missingBytes, dict, dictSize); + FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe_usingDict should have failed : output buffer too small (-%u byte)", missingBytes); + FUZ_CHECKTEST(decodedBuffer[blockSize-missingBytes], "LZ4_decompress_safe_usingDict overrun specified output buffer size (-%u byte) (blockSize=%i)", missingBytes, blockSize); + } + } + + // Compress HC using External dictionary + FUZ_DISPLAYTEST; + dict -= (FUZ_rand(&randState) & 7); // even bigger separation + if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; + LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); + blockContinueCompressedSize = LZ4_compressHC_continue(&LZ4dictHC, block, compressedBuffer, blockSize); + FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compressHC_continue failed"); + + FUZ_DISPLAYTEST; + LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); + ret = LZ4_compressHC_limitedOutput_continue(&LZ4dictHC, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); + FUZ_CHECKTEST(ret>0, "LZ4_compressHC_limitedOutput_continue using ExtDict should fail : one missing byte for output buffer"); + + FUZ_DISPLAYTEST; + LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); + ret = LZ4_compressHC_limitedOutput_continue(&LZ4dictHC, 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"); + + FUZ_DISPLAYTEST; + decodedBuffer[blockSize] = 0; + ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, blockSize, dict, dictSize); + FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe_usingDict did not regenerate original data"); + FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_safe_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_safe_usingDict corrupted decoded data"); - // Fill stats + // ***** End of tests *** // + // Fill stats bytes += blockSize; cbytes += compressedSize; hcbytes += HCcompressedSize; ccbytes += blockContinueCompressedSize; } - printf("\r%7i /%7i - ", cycleNb, nbCycles); + printf("\r%7u /%7u - ", 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); @@ -627,8 +663,8 @@ _output_error: } } -static const unsigned testInputSize = 128 KB; -static const unsigned testCompressedSize = 64 KB; +#define testInputSize (128 KB) +#define testCompressedSize (64 KB) static void FUZ_unitTests(void) { @@ -703,17 +739,17 @@ static void FUZ_unitTests(void) FUZ_CHECKTEST(crcOrig!=crcNew, "LZ4_decompress_safe() dictionary decompression corruption"); } - // remote dictionary compression test + // remote dictionary HC compression test crcOrig = XXH64(testInput + 64 KB, testCompressedSize, 0); LZ4_resetStreamHC(&sHC, 0); LZ4_loadDictHC(&sHC, testInput, 32 KB); result = LZ4_compressHC_limitedOutput_continue(&sHC, testInput + 64 KB, testCompressed, testCompressedSize, testCompressedSize-1); - //FUZ_CHECKTEST(result==0, "LZ4_compressHC_limitedOutput_continue() remote dictionary failed : result = %i", result); + FUZ_CHECKTEST(result==0, "LZ4_compressHC_limitedOutput_continue() remote dictionary failed : result = %i", result); result = LZ4_decompress_safe_usingDict(testCompressed, testVerify, result, testCompressedSize, testInput, 32 KB); - //FUZ_CHECKTEST(result!=(int)testCompressedSize, "LZ4_decompress_safe() dictionary decompression failed"); + FUZ_CHECKTEST(result!=(int)testCompressedSize, "LZ4_decompress_safe_usingDict() decompression failed following remote dictionary HC compression test"); crcNew = XXH64(testVerify, testCompressedSize, 0); - //FUZ_CHECKTEST(crcOrig!=crcNew, "LZ4_decompress_safe() dictionary decompression corruption"); + FUZ_CHECKTEST(crcOrig!=crcNew, "LZ4_decompress_safe_usingDict() decompression corruption"); } printf("All unit tests completed succesfully \n"); -- cgit v0.12