From 20e969e5793aa6773593df8768d068a1ae13f746 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Mon, 5 Feb 2018 15:18:00 -0800 Subject: fuzzer: added low address compression test is expected to work on linux+gcc only. --- lib/lz4hc.c | 9 +++++---- lib/lz4hc.h | 8 ++++---- tests/fuzzer.c | 46 +++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 54 insertions(+), 9 deletions(-) diff --git a/lib/lz4hc.c b/lib/lz4hc.c index cface81..79cf651 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -856,16 +856,17 @@ int LZ4_resetStreamStateHC(void* state, char* inputBuffer) LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t*)state)->internal_donotuse; if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */ LZ4HC_init(ctx, (const BYTE*)inputBuffer); - ctx->inputBuffer = (BYTE*)inputBuffer; + ctx->inputBuffer = inputBuffer; return 0; } -void* LZ4_createHC (char* inputBuffer) +void* LZ4_createHC (const char* inputBuffer) { LZ4_streamHC_t* hc4 = (LZ4_streamHC_t*)ALLOCATOR(1, sizeof(LZ4_streamHC_t)); if (hc4 == NULL) return NULL; /* not enough memory */ LZ4HC_init (&hc4->internal_donotuse, (const BYTE*)inputBuffer); - hc4->internal_donotuse.inputBuffer = (BYTE*)inputBuffer; + assert(sizeof(size_t) == sizeof(void*)); + hc4->internal_donotuse.inputBuffer = (void*)(size_t)inputBuffer; /* ugly hack, circumvent -Wcast-qual */ return hc4; } @@ -889,5 +890,5 @@ char* LZ4_slideInputBufferHC(void* LZ4HC_Data) { LZ4HC_CCtx_internal* const hc4 = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse; int const dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB); - return (char*)(hc4->inputBuffer + dictSize); + return (char*)(hc4->inputBuffer) + dictSize; } diff --git a/lib/lz4hc.h b/lib/lz4hc.h index a7f77f9..7a25bee 100644 --- a/lib/lz4hc.h +++ b/lib/lz4hc.h @@ -148,7 +148,7 @@ typedef struct const uint8_t* end; /* next block here to continue on current prefix */ const uint8_t* base; /* All index relative to this position */ const uint8_t* dictBase; /* alternate base for extDict */ - uint8_t* inputBuffer; /* deprecated */ + void* inputBuffer; /* deprecated */ uint32_t dictLimit; /* below that point, need extDict */ uint32_t lowLimit; /* below that point, no more dict */ uint32_t nextToUpdate; /* index from which to continue dictionary update */ @@ -164,7 +164,7 @@ typedef struct const unsigned char* end; /* next block here to continue on current prefix */ const unsigned char* base; /* All index relative to this position */ const unsigned char* dictBase; /* alternate base for extDict */ - unsigned char* inputBuffer; /* deprecated */ + void* inputBuffer; /* deprecated */ unsigned int dictLimit; /* below that point, need extDict */ unsigned int lowLimit; /* below that point, no more dict */ unsigned int nextToUpdate; /* index from which to continue dictionary update */ @@ -206,8 +206,8 @@ LZ4_DEPRECATED("use LZ4_compress_HC_extStateHC() instead") LZ4LIB_API int LZ4_co LZ4_DEPRECATED("use LZ4_compress_HC_continue() instead") LZ4LIB_API int LZ4_compressHC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize); LZ4_DEPRECATED("use LZ4_compress_HC_continue() instead") LZ4LIB_API int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize); -/* Deprecated Streaming functions using older model; should no longer be used */ -LZ4_DEPRECATED("use LZ4_createStreamHC() instead") LZ4LIB_API void* LZ4_createHC (char* inputBuffer); +/* Deprecated Streaming functions; should no longer be used */ +LZ4_DEPRECATED("use LZ4_createStreamHC() instead") LZ4LIB_API void* LZ4_createHC (const char* inputBuffer); LZ4_DEPRECATED("use LZ4_saveDictHC() instead") LZ4LIB_API char* LZ4_slideInputBufferHC (void* LZ4HC_Data); LZ4_DEPRECATED("use LZ4_freeStreamHC() instead") LZ4LIB_API int LZ4_freeHC (void* LZ4HC_Data); LZ4_DEPRECATED("use LZ4_compress_HC_continue() instead") LZ4LIB_API int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel); diff --git a/tests/fuzzer.c b/tests/fuzzer.c index c134fe3..9415e94 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -240,6 +240,42 @@ _overflowError: } +#ifdef __unix__ /* is expected to be triggered on linux+gcc */ + +#include /* mmap */ + +static void* FUZ_createLowAddr(size_t size) +{ + void* const lowBuff = mmap((void*)(0x1000), size, + PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, + -1, 0); + DISPLAYLEVEL(2, "generating low buffer at address %p \n", lowBuff); + return lowBuff; +} + +static void FUZ_freeLowAddr(void* buffer, size_t size) +{ + if (munmap(buffer, size)) { + perror("fuzzer: freeing low address buffer"); + abort(); + } +} + +#else + +static void* FUZ_createLowAddr(size_t size) +{ + return malloc(size); +} + +static void FUZ_freeLowAddr(void* buffer, size_t size) +{ + (void)size; + free(buffer); +} + +#endif + /*! FUZ_findDiff() : * find the first different byte between buff1 and buff2. * presumes buff1 != buff2. @@ -266,6 +302,8 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c size_t const compressedBufferSize = LZ4_compressBound(FUZ_MAX_BLOCK_SIZE); char* const compressedBuffer = (char*)malloc(compressedBufferSize); char* const decodedBuffer = (char*)malloc(FUZ_MAX_DICT_SIZE + FUZ_MAX_BLOCK_SIZE); + size_t const labSize = 96 KB; + void* const lowAddrBuffer = FUZ_createLowAddr(labSize); void* const stateLZ4 = malloc(LZ4_sizeofState()); void* const stateLZ4HC = malloc(LZ4_sizeofStateHC()); LZ4_stream_t LZ4dict; @@ -306,7 +344,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c int const dictSizeRand = FUZ_rand(&randState) % FUZ_MAX_DICT_SIZE; int const dictSize = MIN(dictSizeRand, blockStart); int const compressionLevel = FUZ_rand(&randState) % (LZ4HC_CLEVEL_MAX+1); - char* const block = ((char*)CNBuffer) + blockStart; + const char* block = ((char*)CNBuffer) + blockStart; const char* dict = block - dictSize; int compressedSize, HCcompressedSize; int blockContinueCompressedSize; @@ -317,6 +355,11 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_displayUpdate(cycleNb); /* Compression tests */ + if ( ((FUZ_rand(&randState) & 63) == 2) + && ((size_t)blockSize < labSize) ) { + memcpy(lowAddrBuffer, block, blockSize); + block = lowAddrBuffer; + } /* Test compression destSize */ FUZ_DISPLAYTEST; @@ -705,6 +748,7 @@ _exit: free(CNBuffer); free(compressedBuffer); free(decodedBuffer); + FUZ_freeLowAddr(lowAddrBuffer, labSize); free(stateLZ4); free(stateLZ4HC); return result; -- cgit v0.12 From c3f0ed28ffa66fd7e28ec3b6dbbe95eb0974bfef Mon Sep 17 00:00:00 2001 From: test4973 Date: Wed, 21 Mar 2018 07:14:13 -0700 Subject: added low address fuzzer tests --- tests/Makefile | 3 +- tests/fuzzer.c | 113 +++++++++++++++++++++++++++++++-------------------------- 2 files changed, 63 insertions(+), 53 deletions(-) diff --git a/tests/Makefile b/tests/Makefile index ddc0d2e..34b8b24 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -35,7 +35,8 @@ PRGDIR := ../programs TESTDIR := versionsTest PYTHON ?= python3 -DEBUGFLAGS = -g -DLZ4_DEBUG=1 +DEBUGLEVEL?= 1 +DEBUGFLAGS = -g -DLZ4_DEBUG=$(DEBUGLEVEL) CFLAGS ?= -O3 # can select custom optimization flags. For example : CFLAGS=-O2 make CFLAGS += -Wall -Wextra -Wundef -Wcast-qual -Wcast-align -Wshadow \ -Wswitch-enum -Wdeclaration-after-statement -Wstrict-prototypes \ diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 9415e94..2b9b926 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -34,9 +34,13 @@ #define LZ4_DISABLE_DEPRECATE_WARNINGS + /*-************************************ * Dependencies **************************************/ +#ifdef __unix__ /* must be included before platform.h for MAP_ANONYMOUS */ +# include /* mmap */ +#endif #include "platform.h" /* _CRT_SECURE_NO_WARNINGS */ #include "util.h" /* U32 */ #include @@ -242,8 +246,6 @@ _overflowError: #ifdef __unix__ /* is expected to be triggered on linux+gcc */ -#include /* mmap */ - static void* FUZ_createLowAddr(size_t size) { void* const lowBuff = mmap((void*)(0x1000), size, @@ -276,6 +278,7 @@ static void FUZ_freeLowAddr(void* buffer, size_t size) #endif + /*! FUZ_findDiff() : * find the first different byte between buff1 and buff2. * presumes buff1 != buff2. @@ -316,10 +319,18 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c # 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>=4 ? printf("%2u\b\b", testNb), fflush(stdout) : 0; } +# define FUZ_DISPLAYTEST(...) { \ + testNb++; \ + if (g_displayLevel>=4) { \ + printf("\r%4u - %2u ", seed, testNb); \ + printf(" " __VA_ARGS__); \ + printf(" "); \ + fflush(stdout); \ + } } /* init */ + DISPLAYLEVEL(2, " g_displayLevel = %u \n", g_displayLevel); if(!CNBuffer || !compressedBuffer || !decodedBuffer) { DISPLAY("Not enough memory to start fuzzer tests"); goto _output_error; @@ -362,7 +373,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } /* Test compression destSize */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_destSize()"); { int srcSize = blockSize; int const targetSize = srcSize * ((FUZ_rand(&randState) & 127)+1) >> 7; char endCheck = FUZ_rand(&randState) & 255; @@ -377,7 +388,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c U32 const crcBase = XXH32(block, srcSize, 0); char const canary = FUZ_rand(&randState) & 255; FUZ_CHECKTEST((ret==0), "LZ4_compress_destSize() compression failed"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); compressedSize = ret; decodedBuffer[srcSize] = canary; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, srcSize); @@ -393,7 +404,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } } /* Test compression HC destSize */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC_destSize()"); { int srcSize = blockSize; int const targetSize = srcSize * ((FUZ_rand(&randState) & 127)+1) >> 7; char const endCheck = FUZ_rand(&randState) & 255; @@ -407,14 +418,12 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(ret > targetSize, "LZ4_compress_HC_destSize() result larger than dst buffer !"); FUZ_CHECKTEST(compressedBuffer[targetSize] != endCheck, "LZ4_compress_HC_destSize() overwrite dst buffer !"); FUZ_CHECKTEST(srcSize > blockSize, "LZ4_compress_HC_destSize() fed more than src buffer !"); - DISPLAYLEVEL(5, "LZ4_compress_HC_destSize(%i): destSize : %7i/%7i; content%7i/%7i ", - compressionLevel, ret, targetSize, srcSize, blockSize); if (targetSize>0) { /* check correctness */ U32 const crcBase = XXH32(block, srcSize, 0); char const canary = FUZ_rand(&randState) & 255; FUZ_CHECKTEST((ret==0), "LZ4_compress_HC_destSize() compression failed"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); compressedSize = ret; decodedBuffer[srcSize] = canary; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, srcSize); @@ -430,31 +439,31 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } } /* Test compression HC */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC()"); ret = LZ4_compress_HC(block, compressedBuffer, blockSize, (int)compressedBufferSize, compressionLevel); FUZ_CHECKTEST(ret==0, "LZ4_compress_HC() failed"); HCcompressedSize = ret; /* Test compression HC using external state */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC_extStateHC()"); ret = LZ4_compress_HC_extStateHC(stateLZ4HC, block, compressedBuffer, blockSize, (int)compressedBufferSize, compressionLevel); FUZ_CHECKTEST(ret==0, "LZ4_compress_HC_extStateHC() failed"); /* Test compression using external state */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_fast_extState()"); ret = LZ4_compress_fast_extState(stateLZ4, block, compressedBuffer, blockSize, (int)compressedBufferSize, 8); FUZ_CHECKTEST(ret==0, "LZ4_compress_fast_extState() failed"); /* Test compression */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_default()"); ret = LZ4_compress_default(block, compressedBuffer, blockSize, (int)compressedBufferSize); FUZ_CHECKTEST(ret==0, "LZ4_compress_default() failed"); compressedSize = ret; /* Decompression tests */ - /* Test decoding with output size being exactly what's necessary => must work */ - FUZ_DISPLAYTEST; + /* Test decoding with output size exactly correct => must work */ + FUZ_DISPLAYTEST("LZ4_decompress_fast() with exact output buffer"); ret = LZ4_decompress_fast(compressedBuffer, decodedBuffer, blockSize); FUZ_CHECKTEST(ret<0, "LZ4_decompress_fast failed despite correct space"); FUZ_CHECKTEST(ret!=compressedSize, "LZ4_decompress_fast failed : did not fully read compressed data"); @@ -462,19 +471,19 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast corrupted decoded data"); /* Test decoding with one byte missing => must fail */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("LZ4_decompress_fast() with output buffer 1-byte too short"); decodedBuffer[blockSize-1] = 0; ret = LZ4_decompress_fast(compressedBuffer, decodedBuffer, blockSize-1); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_fast should have failed, due to Output Size being too small"); FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_fast overrun specified output buffer"); /* Test decoding with one byte too much => must fail */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); ret = LZ4_decompress_fast(compressedBuffer, decodedBuffer, blockSize+1); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_fast should have failed, due to Output Size being too large"); /* Test decoding with output size exactly what's necessary => must work */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize] = 0; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, blockSize); FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe failed despite sufficient space"); @@ -484,7 +493,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); // Test decoding with more than enough output size => must work - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize] = 0; decodedBuffer[blockSize+1] = 0; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, blockSize+1); @@ -496,14 +505,14 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); // Test decoding with output size being one byte too short => must fail - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize-1] = 0; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, blockSize-1); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe should have failed, due to Output Size being one byte too short"); FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_safe overrun specified output buffer size"); // Test decoding with output size being 10 bytes too short => must fail - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); if (blockSize>10) { decodedBuffer[blockSize-10] = 0; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, blockSize-10); @@ -512,51 +521,51 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } // Test decoding with input size being one byte too short => must fail - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize-1, blockSize); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe should have failed, due to input size being one byte too short (blockSize=%i, ret=%i, compressedSize=%i)", blockSize, ret, compressedSize); // Test decoding with input size being one byte too large => must fail - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize] = 0; ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize+1, blockSize); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe should have failed, due to input size being too large"); FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_safe overrun specified output buffer size"); // Test partial decoding with target output size being max/2 => must work - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); ret = LZ4_decompress_safe_partial(compressedBuffer, decodedBuffer, compressedSize, blockSize/2, blockSize); FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe_partial failed despite sufficient space"); // Test partial decoding with target output size being just below max => must work - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); ret = LZ4_decompress_safe_partial(compressedBuffer, decodedBuffer, compressedSize, blockSize-3, blockSize); FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe_partial failed despite sufficient space"); /* Test Compression with limited output size */ /* Test compression with output size being exactly what's necessary (should work) */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_default() with output buffer just the right size"); ret = LZ4_compress_default(block, compressedBuffer, blockSize, compressedSize); FUZ_CHECKTEST(ret==0, "LZ4_compress_default() failed despite sufficient space"); /* Test compression with output size being exactly what's necessary and external state (should work) */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_fast_extState() with output buffer just the right size"); ret = LZ4_compress_fast_extState(stateLZ4, block, compressedBuffer, blockSize, compressedSize, 1); FUZ_CHECKTEST(ret==0, "LZ4_compress_fast_extState() failed despite sufficient space"); /* Test HC compression with output size being exactly what's necessary (should work) */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC() with output buffer just the right size"); ret = LZ4_compress_HC(block, compressedBuffer, blockSize, HCcompressedSize, compressionLevel); FUZ_CHECKTEST(ret==0, "LZ4_compress_HC() failed despite sufficient space"); /* Test HC compression with output size being exactly what's necessary (should work) */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC_extStateHC() with output buffer just the right size"); ret = LZ4_compress_HC_extStateHC(stateLZ4HC, block, compressedBuffer, blockSize, HCcompressedSize, compressionLevel); FUZ_CHECKTEST(ret==0, "LZ4_compress_HC_extStateHC() failed despite sufficient space"); /* Test compression with missing bytes into output buffer => must fail */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_default() with output buffer a bit too short"); { int missingBytes = (FUZ_rand(&randState) % 0x3F) + 1; if (missingBytes >= compressedSize) missingBytes = compressedSize-1; missingBytes += !missingBytes; /* avoid special case missingBytes==0 */ @@ -567,7 +576,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } /* Test HC compression with missing bytes into output buffer => must fail */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_HC() with output buffer a bit too short"); { int missingBytes = (FUZ_rand(&randState) % 0x3F) + 1; if (missingBytes >= HCcompressedSize) missingBytes = HCcompressedSize-1; missingBytes += !missingBytes; /* avoid special case missingBytes==0 */ @@ -583,7 +592,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c /*-******************/ /* Compress using dictionary */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_fast_continue() with dictionary of size %i", dictSize); { LZ4_stream_t LZ4_stream; LZ4_resetStream(&LZ4_stream); LZ4_compress_fast_continue (&LZ4_stream, dict, compressedBuffer, dictSize, (int)compressedBufferSize, 1); /* Just to fill hash tables */ @@ -592,7 +601,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } /* Decompress with dictionary as prefix */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_decompress_fast_usingDict() with dictionary as prefix"); memcpy(decodedBuffer, dict, dictSize); ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer+dictSize, blockSize, decodedBuffer, dictSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_usingDict did not read all compressed block input"); @@ -605,33 +614,33 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_decompress_safe_usingDict()"); ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer+dictSize, blockContinueCompressedSize, blockSize, decodedBuffer, dictSize); FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe_usingDict did not regenerate original data"); crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); /* Compress using External dictionary */ - FUZ_DISPLAYTEST; - dict -= (FUZ_rand(&randState) & 0xF) + 1; /* Separation, so it is an ExtDict */ + FUZ_DISPLAYTEST("test LZ4_compress_fast_continue(), with non-contiguous dictionary"); + dict -= (FUZ_rand(&randState) & 0xF) + 1; /* create space, so now dictionary is an ExtDict */ if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; LZ4_loadDict(&LZ4dict, dict, dictSize); blockContinueCompressedSize = LZ4_compress_fast_continue(&LZ4dict, block, compressedBuffer, blockSize, (int)compressedBufferSize, 1); FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_fast_continue failed"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_fast_continue() with dictionary but with an output buffer too short by one byte"); LZ4_loadDict(&LZ4dict, dict, dictSize); ret = LZ4_compress_fast_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize-1, 1); FUZ_CHECKTEST(ret>0, "LZ4_compress_fast_continue using ExtDict should fail : one missing byte for output buffer : %i written, %i buffer", ret, blockContinueCompressedSize); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST("test LZ4_compress_fast_continue() with dictionary loaded with LZ4_loadDict()"); LZ4_loadDict(&LZ4dict, dict, dictSize); ret = LZ4_compress_fast_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize, 1); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_compress_limitedOutput_compressed size is different (%i != %i)", ret, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_fast_continue should work : enough size available within output buffer"); /* Decompress with dictionary as external */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize] = 0; ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize, dict, dictSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_usingDict did not read all compressed block input"); @@ -640,7 +649,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c if (crcCheck!=crcOrig) FUZ_findDiff(block, decodedBuffer); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); - FUZ_DISPLAYTEST; + 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"); @@ -648,19 +657,19 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c crcCheck = XXH32(decodedBuffer, blockSize, 0); FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize-1] = 0; ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize-1, dict, dictSize); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_fast_usingDict should have failed : wrong original size (-1 byte)"); FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_fast_usingDict overrun specified output buffer size"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[blockSize-1] = 0; ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, blockSize-1, dict, dictSize); FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe_usingDict should have failed : not enough output size (-1 byte)"); FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_safe_usingDict overrun specified output buffer size"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); { U32 const missingBytes = (FUZ_rand(&randState) & 0xF) + 2; if ((U32)blockSize > missingBytes) { decodedBuffer[blockSize-missingBytes] = 0; @@ -670,7 +679,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } } /* Compress HC using External dictionary */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); dict -= (FUZ_rand(&randState) & 7); /* even bigger separation */ if (dict < (char*)CNBuffer) dict = (char*)CNBuffer; LZ4_resetStreamHC (&LZ4dictHC, compressionLevel); @@ -679,18 +688,18 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c blockContinueCompressedSize = LZ4_compress_HC_continue(&LZ4dictHC, block, compressedBuffer, blockSize, (int)compressedBufferSize); FUZ_CHECKTEST(blockContinueCompressedSize==0, "LZ4_compress_HC_continue failed"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); ret = LZ4_compress_HC_continue(&LZ4dictHC, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); FUZ_CHECKTEST(ret>0, "LZ4_compress_HC_continue using ExtDict should fail : one missing byte for output buffer (%i != %i)", ret, blockContinueCompressedSize); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); ret = LZ4_compress_HC_continue(&LZ4dictHC, block, compressedBuffer, blockSize, blockContinueCompressedSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_compress_HC_continue size is different (%i != %i)", ret, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_HC_continue should work : enough size available within output buffer"); - FUZ_DISPLAYTEST; + 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"); @@ -701,10 +710,10 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); /* Compress HC continue destSize */ - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); { int const availableSpace = (FUZ_rand(&randState) % blockSize) + 5; int consumedSize = blockSize; - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); LZ4_resetStreamHC (&LZ4dictHC, compressionLevel); LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); blockContinueCompressedSize = LZ4_compress_HC_continue_destSize(&LZ4dictHC, block, compressedBuffer, &consumedSize, availableSpace); @@ -713,7 +722,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(blockContinueCompressedSize > availableSpace, "LZ4_compress_HC_continue_destSize write overflow"); FUZ_CHECKTEST(consumedSize > blockSize, "LZ4_compress_HC_continue_destSize read overflow"); - FUZ_DISPLAYTEST; + FUZ_DISPLAYTEST(); decodedBuffer[consumedSize] = 0; ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, consumedSize, dict, dictSize); FUZ_CHECKTEST(ret!=consumedSize, "LZ4_decompress_safe_usingDict did not regenerate original data"); @@ -1118,13 +1127,13 @@ int main(int argc, const char** argv) return FUZ_usage(programName); case 'v': /* verbose mode */ - argument++; g_displayLevel++; + argument++; break; case 'p': /* pause at the end */ - argument++; use_pause=1; + argument++; break; case 'i': -- cgit v0.12 From 6d931b6a93100fe2cb4dafc032ff486c814d1fed Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 12:40:33 -0700 Subject: fixed lz4 compression starting at small address when using byU32 and byU16 modes --- lib/lz4.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--- tests/fuzzer.c | 2 +- 2 files changed, 68 insertions(+), 4 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 0fdbe5e..bcebc92 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -533,6 +533,20 @@ LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_ LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); } +/* LZ4_getIndexOnHash() : + * Index of match position registered in hash table. + * hash position must be calculated by using base+index, or dictBase+index. + * Assumption 1 : only valid if tableType == byU32 or byU16. + * Assumption 2 : h is presumed valid (within limits of hash table) + */ +static U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType) +{ + LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2); + if (tableType == byU32) { const U32* const hashTable = (const U32*) tableBase; assert(h < (1U << (LZ4_MEMORY_USAGE-2))); return hashTable[h]; } + if (tableType == byU16) { const U16* const hashTable = (const U16*) tableBase; assert(h < (1U << (LZ4_MEMORY_USAGE-1))); return hashTable[h]; } + assert(0); return 0; /* forbidden case */ +} + static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType, const BYTE* srcBase) { if (tableType == byPtr) { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; } @@ -598,7 +612,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( { const BYTE* ip = (const BYTE*) source; - size_t currentOffset = cctx->currentOffset; + size_t const currentOffset = cctx->currentOffset; const BYTE* base = (const BYTE*) source - currentOffset; const BYTE* lowLimit; @@ -650,7 +664,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( BYTE* token; /* Find a match */ - { const BYTE* forwardIp = ip; + if (tableType == byPtr) { + const BYTE* forwardIp = ip; unsigned step = 1; unsigned searchMatchNb = acceleration << LZ4_skipTrigger; do { @@ -687,6 +702,54 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0) || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) ); + + } else { /* byU32, byU16 */ + + const BYTE* forwardIp = ip; + unsigned step = 1; + unsigned searchMatchNb = acceleration << LZ4_skipTrigger; + do { + U32 const h = forwardH; + U32 const matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); + ip = forwardIp; + forwardIp += step; + step = (searchMatchNb++ >> LZ4_skipTrigger); + + if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; + assert(ip < mflimitPlusOne); + + if (dictDirective == usingDictCtx) { + if (matchIndex < currentOffset) { + /* there was no match, try the dictionary */ + match = LZ4_getPosition(ip, dictCtx->hashTable, byU32, dictBase); + refDelta = dictDelta; + lowLimit = dictLowLimit; + } else { + match = base + matchIndex; + refDelta = 0; + lowLimit = (const BYTE*)source; + } + } else if (dictDirective==usingExtDict) { + if (matchIndex < currentOffset) { + match = dictBase + matchIndex; + refDelta = dictDelta; + lowLimit = dictLowLimit; + } else { + match = base + matchIndex; + refDelta = 0; + lowLimit = (const BYTE*)source; + } + } else { /* single continuous memory segment */ + match = base + matchIndex; + refDelta = 0; + lowLimit = (const BYTE*)source; + } + forwardH = LZ4_hashPosition(forwardIp, tableType); + LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); + + } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0) + || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) + || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) ); } /* Catch up */ @@ -718,7 +781,8 @@ _next_match: /* Encode MatchLength */ { unsigned matchCode; - if ((dictDirective==usingExtDict || dictDirective==usingDictCtx) && lowLimit==dictionary) { + if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx) + && (lowLimit==dictionary) ) { const BYTE* limit; match += refDelta; limit = ip + (dictEnd-match); diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 2b9b926..0b7d54e 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -322,7 +322,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c # define FUZ_DISPLAYTEST(...) { \ testNb++; \ if (g_displayLevel>=4) { \ - printf("\r%4u - %2u ", seed, testNb); \ + printf("\r%4u - %2u ", cycleNb, testNb); \ printf(" " __VA_ARGS__); \ printf(" "); \ fflush(stdout); \ -- cgit v0.12 From 64a3e41acaf9e186937d32c9dd2dc104e5bc4a72 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 16:38:43 -0700 Subject: changed LZ4_compress_generic() logic to use indexes (U32) instead of Ptr. byPtr is still present. --- lib/lz4.c | 170 ++++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 100 insertions(+), 70 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index bcebc92..4b219d2 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -516,6 +516,18 @@ LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tab return LZ4_hash4(LZ4_read32(p), tableType); } +static void LZ4_putIndexOnHash(U32 index, U32 h, void* tableBase, tableType_t const tableType) +{ + switch (tableType) + { + default: /* fallthrough */ + case clearedTable: /* fallthrough */ + case byPtr: { /* illegal! */ assert(0); return; } + case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = index; return; } + case byU16: { U16* hashTable = (U16*) tableBase; assert(index < 65536); hashTable[h] = (U16)index; return; } + } +} + static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t const tableType, const BYTE* srcBase) { switch (tableType) @@ -612,8 +624,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( { const BYTE* ip = (const BYTE*) source; - size_t const currentOffset = cctx->currentOffset; - const BYTE* base = (const BYTE*) source - currentOffset; + size_t const startIndex = cctx->currentOffset; + const BYTE* base = (const BYTE*) source - startIndex; const BYTE* lowLimit; const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx; @@ -622,7 +634,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( const U32 dictSize = dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize; - const BYTE* const lowRefLimit = (const BYTE*) source - dictSize; + int const maybe_ext_memSegment = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx); + U32 const prefixIdxLimit = startIndex - dictSize; /* used when dictDirective == dictSmall */ const BYTE* const dictEnd = dictionary + dictSize; const BYTE* anchor = (const BYTE*) source; const BYTE* const iend = ip + inputSize; @@ -633,19 +646,20 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( * while a dictionary in the current context precedes the currentOffset */ const BYTE* dictBase = dictDirective == usingDictCtx ? (const BYTE*) source - dictCtx->currentOffset : - (const BYTE*) source - dictSize - currentOffset; - const ptrdiff_t dictDelta = dictionary ? dictEnd - (const BYTE*) source : 0; + (const BYTE*) source - dictSize - startIndex; const BYTE* dictLowLimit; BYTE* op = (BYTE*) dest; BYTE* const olimit = op + maxOutputSize; + U32 offset = 0; ptrdiff_t retval = 0; U32 forwardH; /* Init conditions */ if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported inputSize, too large (or negative) */ + if (tableType==byPtr) assert(dictDirective==noDict); /* only supported use case with byPtr */ lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0); dictLowLimit = dictionary ? dictionary : lowLimit; @@ -659,7 +673,6 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( /* Main Loop */ for ( ; ; ) { - ptrdiff_t refDelta = 0; const BYTE* match; BYTE* token; @@ -678,82 +691,65 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( assert(ip < mflimitPlusOne); match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base); - if (dictDirective == usingDictCtx) { - if (match < (const BYTE*)source) { - /* there was no match, try the dictionary */ - match = LZ4_getPosition(ip, dictCtx->hashTable, byU32, dictBase); - refDelta = dictDelta; - lowLimit = dictLowLimit; - } else { - refDelta = 0; - lowLimit = (const BYTE*)source; - } - } else if (dictDirective==usingExtDict) { - if (match < (const BYTE*)source) { - refDelta = dictDelta; - lowLimit = dictLowLimit; - } else { - refDelta = 0; - lowLimit = (const BYTE*)source; - } } forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); - } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0) - || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) - || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) ); + } while ( LZ4_read32(match) != LZ4_read32(ip) ); } else { /* byU32, byU16 */ const BYTE* forwardIp = ip; - unsigned step = 1; unsigned searchMatchNb = acceleration << LZ4_skipTrigger; do { U32 const h = forwardH; - U32 const matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); + U32 const current = forwardIp - base; + U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); + assert(matchIndex <= current); ip = forwardIp; - forwardIp += step; - step = (searchMatchNb++ >> LZ4_skipTrigger); + assert(searchMatchNb >= (1<> LZ4_skipTrigger); if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; assert(ip < mflimitPlusOne); if (dictDirective == usingDictCtx) { - if (matchIndex < currentOffset) { + if (matchIndex < startIndex) { /* there was no match, try the dictionary */ - match = LZ4_getPosition(ip, dictCtx->hashTable, byU32, dictBase); - refDelta = dictDelta; + matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); + match = dictBase + matchIndex; lowLimit = dictLowLimit; } else { match = base + matchIndex; - refDelta = 0; lowLimit = (const BYTE*)source; } } else if (dictDirective==usingExtDict) { - if (matchIndex < currentOffset) { + if (matchIndex < startIndex) { match = dictBase + matchIndex; - refDelta = dictDelta; lowLimit = dictLowLimit; } else { match = base + matchIndex; - refDelta = 0; lowLimit = (const BYTE*)source; } } else { /* single continuous memory segment */ match = base + matchIndex; - refDelta = 0; - lowLimit = (const BYTE*)source; } forwardH = LZ4_hashPosition(forwardIp, tableType); - LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); + LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); + + if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) continue; /* match outside of valid area */ + if ((tableType != byU16) && (matchIndex+MAX_DISTANCE < current)) continue; /* too far */ + if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE); /* too_far presumed impossible with byU16 */ - } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0) - || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) - || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) ); + if (LZ4_read32(match) == LZ4_read32(ip)) { + if (maybe_ext_memSegment) offset = current - matchIndex; + break; /* match found */ + } + + } while(1); } /* Catch up */ - while (((ip>anchor) & (match+refDelta > lowLimit)) && (unlikely(ip[-1]==match[refDelta-1]))) { ip--; match--; } + while (((ip>anchor) & (match > lowLimit)) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; } /* Encode Literals */ { unsigned const litLength = (unsigned)(ip - anchor); @@ -776,7 +772,13 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( _next_match: /* Encode Offset */ - LZ4_writeLE16(op, (U16)(ip-match)); op+=2; + if (maybe_ext_memSegment) { /* static test */ + assert(offset <= MAX_DISTANCE && offset > 0); + LZ4_writeLE16(op, (U16)offset); op+=2; + } else { + assert(ip-match <= MAX_DISTANCE); + LZ4_writeLE16(op, (U16)(ip - match)); op+=2; + } /* Encode MatchLength */ { unsigned matchCode; @@ -784,7 +786,6 @@ _next_match: if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx) && (lowLimit==dictionary) ) { const BYTE* limit; - match += refDelta; limit = ip + (dictEnd-match); if (limit > matchlimit) limit = matchlimit; matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit); @@ -799,6 +800,8 @@ _next_match: ip += MINMATCH + matchCode; } + DEBUGLOG(2,"matchLength:%7u ", matchCode+MINMATCH); + if ( outputLimited && /* Check output buffer overflow */ (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) ) goto _clean_up; @@ -825,34 +828,61 @@ _next_match: /* Fill table */ LZ4_putPosition(ip-2, cctx->hashTable, tableType, base); +#if 1 /* Test next position */ - match = LZ4_getPosition(ip, cctx->hashTable, tableType, base); - if (dictDirective == usingDictCtx) { - if (match < (const BYTE*)source) { - /* there was no match, try the dictionary */ - match = LZ4_getPosition(ip, dictCtx->hashTable, byU32, dictBase); - refDelta = dictDelta; - lowLimit = dictLowLimit; - } else { - refDelta = 0; - lowLimit = (const BYTE*)source; + if (tableType == byPtr) { + + match = LZ4_getPosition(ip, cctx->hashTable, tableType, base); + LZ4_putPosition(ip, cctx->hashTable, tableType, base); + if ( (match+MAX_DISTANCE >= ip) + && (LZ4_read32(match) == LZ4_read32(ip)) ) + { token=op++; *token=0; goto _next_match; } + + } else { /* byU32, byU16 */ + + U32 const h = LZ4_hashPosition(ip, tableType); + U32 const current = (U32)(ip-base); + U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); + assert(matchIndex < current); + if (dictDirective == usingDictCtx) { + if (match < (const BYTE*)source) { + /* there was no match, try the dictionary */ + matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); + match = dictBase + matchIndex; + } else { + match = base + matchIndex; + } + } else if (dictDirective==usingExtDict) { + if (match < (const BYTE*)source) { + match = dictBase + matchIndex; + } else { + match = base + matchIndex; + } + } else { /* single memory segment */ + match = base + matchIndex; } - } else if (dictDirective==usingExtDict) { - if (match < (const BYTE*)source) { - refDelta = dictDelta; - lowLimit = dictLowLimit; - } else { - refDelta = 0; - lowLimit = (const BYTE*)source; - } } - LZ4_putPosition(ip, cctx->hashTable, tableType, base); - if ( ((dictIssue==dictSmall) ? (match>=lowRefLimit) : 1) - && (match+MAX_DISTANCE>=ip) - && (LZ4_read32(match+refDelta)==LZ4_read32(ip)) ) - { token=op++; *token=0; goto _next_match; } + LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType); + if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1) + && ((tableType==byU16) ? 1 : (matchIndex+MAX_DISTANCE >= current)) + && (LZ4_read32(match) == LZ4_read32(ip)) ) { + token=op++; + *token=0; + if (maybe_ext_memSegment) + offset = current - matchIndex; + goto _next_match; + } + } /* Prepare next loop */ forwardH = LZ4_hashPosition(++ip, tableType); + +#else + + /* Prepare next loop */ + forwardH = LZ4_hashPosition(ip, tableType); + +#endif + } _last_literals: -- cgit v0.12 From f2a4d6ef37f653c21627274634d171af66126d5e Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 17:16:33 -0700 Subject: fixed immediate match search --- lib/lz4.c | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 4b219d2..8d8c1e8 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -624,7 +624,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( { const BYTE* ip = (const BYTE*) source; - size_t const startIndex = cctx->currentOffset; + U32 const startIndex = cctx->currentOffset; const BYTE* base = (const BYTE*) source - startIndex; const BYTE* lowLimit; @@ -645,8 +645,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( /* the dictCtx currentOffset is indexed on the start of the dictionary, * while a dictionary in the current context precedes the currentOffset */ const BYTE* dictBase = dictDirective == usingDictCtx ? - (const BYTE*) source - dictCtx->currentOffset : - (const BYTE*) source - dictSize - startIndex; + dictionary + dictSize - dictCtx->currentOffset : /* is it possible that dictCtx->currentOffset != dictCtx->dictSize ? */ + dictionary + dictSize - startIndex; const BYTE* dictLowLimit; BYTE* op = (BYTE*) dest; @@ -800,8 +800,6 @@ _next_match: ip += MINMATCH + matchCode; } - DEBUGLOG(2,"matchLength:%7u ", matchCode+MINMATCH); - if ( outputLimited && /* Check output buffer overflow */ (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) ) goto _clean_up; @@ -845,7 +843,7 @@ _next_match: U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); assert(matchIndex < current); if (dictDirective == usingDictCtx) { - if (match < (const BYTE*)source) { + if (matchIndex < startIndex) { /* there was no match, try the dictionary */ matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); match = dictBase + matchIndex; @@ -853,7 +851,7 @@ _next_match: match = base + matchIndex; } } else if (dictDirective==usingExtDict) { - if (match < (const BYTE*)source) { + if (matchIndex < startIndex) { match = dictBase + matchIndex; } else { match = base + matchIndex; -- cgit v0.12 From b4be1e0a743f2200eaf1c13d322c925b64b872e2 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 17:52:54 -0700 Subject: fixed byPtr match search --- lib/lz4.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/lz4.c b/lib/lz4.c index 8d8c1e8..5791556 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -694,7 +694,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base); - } while ( LZ4_read32(match) != LZ4_read32(ip) ); + } while ( (match+MAX_DISTANCE < ip) + || (LZ4_read32(match) != LZ4_read32(ip)) ); } else { /* byU32, byU16 */ -- cgit v0.12 From f4e06e28e6d285f7f145798d7dfe1cbe71ae1efa Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 18:29:42 -0700 Subject: fixed byPtr mode switch to byU32 when src address is < 64K note : byPtr is still useful in 32-bits, as it's about ~10% faster --- lib/lz4.c | 47 +++++++++++++++++++++++++---------------------- 1 file changed, 25 insertions(+), 22 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 5791556..4fb54f8 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -930,14 +930,14 @@ int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int if (inputSize < LZ4_64Klimit) { return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue, acceleration); } else { - const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; + const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32; return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); } } else { if (inputSize < LZ4_64Klimit) {; return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration); } else { - const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; + const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32; return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); } } @@ -951,7 +951,7 @@ int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int * performance when the context reset would otherwise be a significant part of * the cost of the compression, e.g., when the data to be compressed is small. */ -int LZ4_compress_fast_extState_noReset(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) +int LZ4_compress_fast_extState_noReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration) { LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse; if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; @@ -959,39 +959,39 @@ int LZ4_compress_fast_extState_noReset(void* state, const char* source, char* de ctx->dictSize = 0; ctx->dictCtx = NULL; - if (maxOutputSize >= LZ4_compressBound(inputSize)) { - if (inputSize < LZ4_64Klimit) { + if (dstCapacity >= LZ4_compressBound(srcSize)) { + if (srcSize < LZ4_64Klimit) { const tableType_t tableType = byU16; - LZ4_prepareTable(ctx, inputSize, tableType, noDict); + LZ4_prepareTable(ctx, srcSize, tableType, noDict); if (ctx->currentOffset) { - return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, tableType, noDict, dictSmall, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, dictSmall, acceleration); } else { - return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); } } else { - const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; - LZ4_prepareTable(ctx, inputSize, tableType, noDict); + const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; + LZ4_prepareTable(ctx, srcSize, tableType, noDict); if (ctx->currentOffset) { ctx->currentOffset += 64 KB; } - return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); } } else { - if (inputSize < LZ4_64Klimit) { + if (srcSize < LZ4_64Klimit) { const tableType_t tableType = byU16; - LZ4_prepareTable(ctx, inputSize, tableType, noDict); + LZ4_prepareTable(ctx, srcSize, tableType, noDict); if (ctx->currentOffset) { - return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, dictSmall, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration); } else { - return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); } } else { - const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; - LZ4_prepareTable(ctx, inputSize, tableType, noDict); + const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; + LZ4_prepareTable(ctx, srcSize, tableType, noDict); if (ctx->currentOffset) { ctx->currentOffset += 64 KB; } - return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); + return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); } } } @@ -1098,6 +1098,8 @@ static int LZ4_compress_destSize_generic( forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base); + DEBUGLOG(2, "match:%p , ip:%p", match, ip); + } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) || (LZ4_read32(match) != LZ4_read32(ip)) ); } @@ -1203,11 +1205,12 @@ static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */ return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1); } else { - if (*srcSizePtr < LZ4_64Klimit) + if (*srcSizePtr < LZ4_64Klimit) { return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, byU16); - else - return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, sizeof(void*)==8 ? byU32 : byPtr); - } + } else { + tableType_t const tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32; + return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, tableType); + } } } -- cgit v0.12 From 038a0d95bfe2d3a544aa2f5551998f6fd8bc0722 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 18:39:22 -0700 Subject: added low-memory address test to travis requires modification linux configuration (sudo) --- .travis.yml | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/.travis.yml b/.travis.yml index 466d55e..a446420 100644 --- a/.travis.yml +++ b/.travis.yml @@ -15,7 +15,7 @@ matrix: - os: linux sudo: false - env: Ubu=12.04cont Cmd='make -C tests test-frametest test-fuzzer' COMPILER=cc + env: Ubu=12.04cont Cmd='sudo sysctl -w vm.mmap_min_addr="4096" && make -C tests test-frametest test-fuzzer' COMPILER=cc - os: linux sudo: false @@ -59,7 +59,7 @@ matrix: - libc6-dev-i386 - gcc-multilib - - env: Ubu=14.04 Cmd='make -C tests test-frametest32 test-fuzzer32' COMPILER=cc + - env: Ubu=14.04 Cmd='sudo sysctl -w vm.mmap_min_addr="4096" && make -C tests test-frametest32 test-fuzzer32' COMPILER=cc dist: trusty sudo: required addons: -- cgit v0.12 From f9992fa37f1b0810c4d0a3e3e6a0eb4880168c57 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 5 Apr 2018 19:05:49 -0700 Subject: noticed a bug when re-using hash table ./fuzzer -vv -s4217 -t7518 --- lib/lz4.c | 7 ++++--- tests/fuzzer.c | 59 +++++++++++++++++++++++++++++----------------------------- 2 files changed, 33 insertions(+), 33 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 4fb54f8..54336c7 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -593,6 +593,9 @@ LZ4_FORCE_INLINE void LZ4_prepareTable( MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE); cctx->currentOffset = 0; cctx->tableType = clearedTable; + } else { + DEBUGLOG(4, "Re-use hash table (no reset)"); + //if (tableType == byU32) cctx->currentOffset += 64 KB; } } /* If the current offset is zero, we will never look in the external @@ -1098,8 +1101,6 @@ static int LZ4_compress_destSize_generic( forwardH = LZ4_hashPosition(forwardIp, tableType); LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base); - DEBUGLOG(2, "match:%p , ip:%p", match, ip); - } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) || (LZ4_read32(match) != LZ4_read32(ip)) ); } @@ -1371,7 +1372,7 @@ int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, ch LZ4_prepareTable(streamPtr, inputSize, tableType, usingDictCtx); result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration); } - } else { + } else { /* no dictCtx */ LZ4_prepareTable(streamPtr, inputSize, tableType, usingExtDict); if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) { result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration); diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 0b7d54e..8ffdb22 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -291,7 +291,7 @@ static void FUZ_findDiff(const void* buff1, const void* buff2) const BYTE* const b2 = (const BYTE*)buff2; size_t u = 0; while (b1[u]==b2[u]) u++; - DISPLAY("Wrong Byte at position %u \n", (unsigned)u); + DISPLAY("\nWrong Byte at position %u \n", (unsigned)u); } @@ -330,7 +330,6 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c /* init */ - DISPLAYLEVEL(2, " g_displayLevel = %u \n", g_displayLevel); if(!CNBuffer || !compressedBuffer || !decodedBuffer) { DISPLAY("Not enough memory to start fuzzer tests"); goto _output_error; @@ -360,7 +359,6 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c int compressedSize, HCcompressedSize; int blockContinueCompressedSize; U32 const crcOrig = XXH32(block, blockSize, 0); - U32 crcCheck; int ret; FUZ_displayUpdate(cycleNb); @@ -467,8 +465,9 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c ret = LZ4_decompress_fast(compressedBuffer, decodedBuffer, blockSize); FUZ_CHECKTEST(ret<0, "LZ4_decompress_fast failed despite correct space"); FUZ_CHECKTEST(ret!=compressedSize, "LZ4_decompress_fast failed : did not fully read compressed data"); - crcCheck = XXH32(decodedBuffer, blockSize, 0); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast corrupted decoded data"); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast corrupted decoded data"); + } /* Test decoding with one byte missing => must fail */ FUZ_DISPLAYTEST("LZ4_decompress_fast() with output buffer 1-byte too short"); @@ -489,8 +488,9 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe failed despite sufficient space"); FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe did not regenerate original data"); FUZ_CHECKTEST(decodedBuffer[blockSize], "LZ4_decompress_safe overrun specified output buffer size"); - crcCheck = XXH32(decodedBuffer, blockSize, 0); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); + } // Test decoding with more than enough output size => must work FUZ_DISPLAYTEST(); @@ -501,8 +501,9 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe did not regenerate original data"); //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"); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe corrupted decoded data"); + } // Test decoding with output size being one byte too short => must fail FUZ_DISPLAYTEST(); @@ -605,20 +606,17 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c memcpy(decodedBuffer, dict, dictSize); ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer+dictSize, blockSize, decodedBuffer, dictSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_usingDict did not read all compressed block input"); - crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); - if (crcCheck!=crcOrig) { - int i=0; - while (block[i]==decodedBuffer[i]) i++; - printf("Wrong Byte at position %i/%i\n", i, blockSize); - + { U32 const crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); + if (crcCheck!=crcOrig) FUZ_findDiff(block, decodedBuffer); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); } - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); FUZ_DISPLAYTEST("test LZ4_decompress_safe_usingDict()"); ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer+dictSize, blockContinueCompressedSize, blockSize, decodedBuffer, dictSize); FUZ_CHECKTEST(ret!=blockSize, "LZ4_decompress_safe_usingDict did not regenerate original data"); - crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + { U32 const crcCheck = XXH32(decodedBuffer+dictSize, blockSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + } /* Compress using External dictionary */ FUZ_DISPLAYTEST("test LZ4_compress_fast_continue(), with non-contiguous dictionary"); @@ -640,22 +638,24 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(ret<=0, "LZ4_compress_fast_continue should work : enough size available within output buffer"); /* Decompress with dictionary as external */ - FUZ_DISPLAYTEST(); + FUZ_DISPLAYTEST("test LZ4_decompress_fast_usingDict(): decoding %i bytes, dict(%p) of size %i", blockSize, dict, dictSize); decodedBuffer[blockSize] = 0; ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize, dict, dictSize); 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) FUZ_findDiff(block, decodedBuffer); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + if (crcCheck!=crcOrig) FUZ_findDiff(block, decodedBuffer); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize); + } 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); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + } FUZ_DISPLAYTEST(); decodedBuffer[blockSize-1] = 0; @@ -704,10 +704,10 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c 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) - FUZ_findDiff(block, decodedBuffer); - FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + { U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0); + if (crcCheck!=crcOrig) FUZ_findDiff(block, decodedBuffer); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data"); + } /* Compress HC continue destSize */ FUZ_DISPLAYTEST(); @@ -729,8 +729,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(decodedBuffer[consumedSize], "LZ4_decompress_safe_usingDict overrun specified output buffer size") { U32 const crcSrc = XXH32(block, consumedSize, 0); U32 const crcDst = XXH32(decodedBuffer, consumedSize, 0); - if (crcSrc!=crcDst) - FUZ_findDiff(block, decodedBuffer); + if (crcSrc!=crcDst) FUZ_findDiff(block, decodedBuffer); FUZ_CHECKTEST(crcSrc!=crcDst, "LZ4_decompress_safe_usingDict corrupted decoded data"); } } -- cgit v0.12 From cf2f06a6c5046ef7d576bc8ad210c3f2efe1f401 Mon Sep 17 00:00:00 2001 From: test4973 Date: Mon, 9 Apr 2018 17:08:17 -0700 Subject: fixed minor conversion warning ptr diff -> U32 --- lib/lz4.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/lz4.c b/lib/lz4.c index 3db37b0..a3c2860 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -717,9 +717,10 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( unsigned searchMatchNb = acceleration << LZ4_skipTrigger; do { U32 const h = forwardH; - U32 const current = forwardIp - base; + U32 const current = (U32)(forwardIp - base); U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType); assert(matchIndex <= current); + assert(forwardIp - base < (ptrdiff_t)(2 GB - 1)); ip = forwardIp; assert(searchMatchNb >= (1<> LZ4_skipTrigger); -- cgit v0.12 From ad7e040384d1835c097b0f727aeaa3d598a401b6 Mon Sep 17 00:00:00 2001 From: test4973 Date: Mon, 9 Apr 2018 20:38:00 -0700 Subject: fix minor conversion warning cast from void not implicit for C++ --- tests/fuzzer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 8ffdb22..2e3ee92 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -367,7 +367,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c if ( ((FUZ_rand(&randState) & 63) == 2) && ((size_t)blockSize < labSize) ) { memcpy(lowAddrBuffer, block, blockSize); - block = lowAddrBuffer; + block = (const char*)lowAddrBuffer; } /* Test compression destSize */ -- cgit v0.12 From 1838803948ceaf211b9e79fb405ef9b7340762ce Mon Sep 17 00:00:00 2001 From: test4973 Date: Wed, 11 Apr 2018 16:49:40 -0700 Subject: fixed LZ4_compress_fast_extState_fastReset() --- lib/lz4.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index d79b2cc..d564ddc 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -953,7 +953,7 @@ int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of * "correctly initialized"). */ -int LZ4_compress_fast_extState_fastReset(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) +int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration) { LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse; if (acceleration < 1) acceleration = ACCELERATION_DEFAULT; @@ -961,8 +961,7 @@ int LZ4_compress_fast_extState_fastReset(void* state, const char* source, char* if (dstCapacity >= LZ4_compressBound(srcSize)) { if (srcSize < LZ4_64Klimit) { const tableType_t tableType = byU16; - LZ4_prepareTable(ctx, inputSize, tableType); -LZ4_prepareTable>>> dev + LZ4_prepareTable(ctx, srcSize, tableType); if (ctx->currentOffset) { return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, dictSmall, acceleration); } else { @@ -970,13 +969,13 @@ LZ4_prepareTable>>> dev } } else { const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; - LZ4_prepareTable(ctx, inputSize, tableType); - return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); + LZ4_prepareTable(ctx, srcSize, tableType); + return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration); } } else { if (srcSize < LZ4_64Klimit) { const tableType_t tableType = byU16; - LZ4_prepareTable(ctx, inputSize, tableType); + LZ4_prepareTable(ctx, srcSize, tableType); if (ctx->currentOffset) { return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration); } else { @@ -984,8 +983,8 @@ LZ4_prepareTable>>> dev } } else { const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr; - LZ4_prepareTable(ctx, inputSize, tableType); - return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration); + LZ4_prepareTable(ctx, srcSize, tableType); + return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration); } } } -- cgit v0.12 From 8af32ce6f7109ecf5cd7d73527e0aba3a63b55e5 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 12 Apr 2018 07:25:40 -0700 Subject: modified a few traces for debug --- lib/lz4.c | 5 +++-- lib/lz4hc.c | 7 +++---- tests/fuzzer.c | 4 +++- 3 files changed, 9 insertions(+), 7 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index d564ddc..e4a68cd 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -594,7 +594,6 @@ LZ4_FORCE_INLINE void LZ4_prepareTable( cctx->tableType = clearedTable; } else { DEBUGLOG(4, "Re-use hash table (no reset)"); - //if (tableType == byU32) cctx->currentOffset += 64 KB; } } @@ -602,9 +601,11 @@ LZ4_FORCE_INLINE void LZ4_prepareTable( * than compressing without a gap. However, compressing with * currentOffset == 0 is faster still, so we preserve that case. */ + DEBUGLOG(2, "tableType=%u, currentOffset=%u", cctx->tableType, cctx->currentOffset); if (cctx->currentOffset != 0 && tableType == byU32) { cctx->currentOffset += 64 KB; } + DEBUGLOG(2, "currentOffset: %u", cctx->currentOffset); /* Finally, clear history */ cctx->dictCtx = NULL; @@ -1267,7 +1268,7 @@ int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) const BYTE* const dictEnd = p + dictSize; const BYTE* base; - DEBUGLOG(4, "LZ4_loadDict %p", LZ4_dict); + DEBUGLOG(4, "LZ4_loadDict (%p into %p)", dictionary, LZ4_dict); LZ4_prepareTable(dict, 0, tableType); diff --git a/lib/lz4hc.c b/lib/lz4hc.c index d05760b..111a09b 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -336,7 +336,7 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( U32 const mlAdd = (matchLength>=19) ? ((matchLength-19) / 255) + 1 : 0; U32 const cost = 1 + llAdd + ll + 2 + mlAdd; if (start==NULL) start = *anchor; /* only works for single segment */ - //g_debuglog_enable = (pos >= 2228) & (pos <= 2262); + /* g_debuglog_enable = (pos >= 2228) & (pos <= 2262); */ DEBUGLOG(6, "pos:%7u -- literals:%3u, match:%4i, offset:%5u, cost:%3u + %u", pos, (U32)(*ip - *anchor), matchLength, (U32)(*ip-match), @@ -1137,15 +1137,14 @@ static int LZ4HC_compress_optimal ( encode: /* cur, last_match_pos, best_mlen, best_off must be set */ assert(cur < LZ4_OPT_NUM); assert(last_match_pos >= 1); /* == 1 when only one candidate */ - DEBUGLOG(6, "reverse traversal, looking for shortest path") - DEBUGLOG(6, "last_match_pos = %i", last_match_pos); + DEBUGLOG(6, "reverse traversal, looking for shortest path (last_match_pos=%i)", last_match_pos); { int candidate_pos = cur; int selected_matchLength = best_mlen; int selected_offset = best_off; while (1) { /* from end to beginning */ int const next_matchLength = opt[candidate_pos].mlen; /* can be 1, means literal */ int const next_offset = opt[candidate_pos].off; - DEBUGLOG(6, "pos %i: sequence length %i", candidate_pos, selected_matchLength); + DEBUGLOG(7, "pos %i: sequence length %i", candidate_pos, selected_matchLength); opt[candidate_pos].mlen = selected_matchLength; opt[candidate_pos].off = selected_offset; selected_matchLength = next_matchLength; diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 2e3ee92..a650277 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -632,13 +632,15 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_CHECKTEST(ret>0, "LZ4_compress_fast_continue using ExtDict should fail : one missing byte for output buffer : %i written, %i buffer", ret, blockContinueCompressedSize); FUZ_DISPLAYTEST("test LZ4_compress_fast_continue() with dictionary loaded with LZ4_loadDict()"); + DISPLAYLEVEL(5, " compress %i bytes from buffer(%p) into dst(%p) using dict(%p) of size %i \n", blockSize, block, decodedBuffer, dict, dictSize); LZ4_loadDict(&LZ4dict, dict, dictSize); ret = LZ4_compress_fast_continue(&LZ4dict, block, compressedBuffer, blockSize, blockContinueCompressedSize, 1); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_compress_limitedOutput_compressed size is different (%i != %i)", ret, blockContinueCompressedSize); FUZ_CHECKTEST(ret<=0, "LZ4_compress_fast_continue should work : enough size available within output buffer"); /* Decompress with dictionary as external */ - FUZ_DISPLAYTEST("test LZ4_decompress_fast_usingDict(): decoding %i bytes, dict(%p) of size %i", blockSize, dict, dictSize); + FUZ_DISPLAYTEST("test LZ4_decompress_fast_usingDict() with dictionary as extDict"); + DISPLAYLEVEL(5, " decoding %i bytes from buffer(%p) using dict(%p) of size %i \n", blockSize, decodedBuffer, dict, dictSize); decodedBuffer[blockSize] = 0; ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize, dict, dictSize); FUZ_CHECKTEST(ret!=blockContinueCompressedSize, "LZ4_decompress_fast_usingDict did not read all compressed block input"); -- cgit v0.12 From db9aa785c51bbcae50c777e89fb537393bfca856 Mon Sep 17 00:00:00 2001 From: test4973 Date: Thu, 12 Apr 2018 16:12:21 -0700 Subject: fixed : counting matches which overlap extDict and prefix --- lib/lz4.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index e4a68cd..21892d3 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -601,11 +601,9 @@ LZ4_FORCE_INLINE void LZ4_prepareTable( * than compressing without a gap. However, compressing with * currentOffset == 0 is faster still, so we preserve that case. */ - DEBUGLOG(2, "tableType=%u, currentOffset=%u", cctx->tableType, cctx->currentOffset); if (cctx->currentOffset != 0 && tableType == byU32) { cctx->currentOffset += 64 KB; } - DEBUGLOG(2, "currentOffset: %u", cctx->currentOffset); /* Finally, clear history */ cctx->dictCtx = NULL; @@ -652,7 +650,6 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( const BYTE* dictBase = dictDirective == usingDictCtx ? dictionary + dictSize - dictCtx->currentOffset : /* is it possible that dictCtx->currentOffset != dictCtx->dictSize ? */ dictionary + dictSize - startIndex; - const BYTE* dictLowLimit; BYTE* op = (BYTE*) dest; BYTE* const olimit = op + maxOutputSize; @@ -665,7 +662,6 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( if (tableType==byPtr) assert(dictDirective==noDict); /* only supported use case with byPtr */ lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0); - dictLowLimit = dictionary ? dictionary : lowLimit; if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */ @@ -735,15 +731,16 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( /* there was no match, try the dictionary */ matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); match = dictBase + matchIndex; - lowLimit = dictLowLimit; + lowLimit = dictionary; } else { match = base + matchIndex; lowLimit = (const BYTE*)source; } } else if (dictDirective==usingExtDict) { if (matchIndex < startIndex) { + DEBUGLOG(7, "extDict candidate: matchIndex=%5u < startIndex=%5u", matchIndex, startIndex); match = dictBase + matchIndex; - lowLimit = dictLowLimit; + lowLimit = dictionary; } else { match = base + matchIndex; lowLimit = (const BYTE*)source; @@ -786,6 +783,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( /* Copy Literals */ LZ4_wildCopy(op, anchor, op+litLength); op+=litLength; + DEBUGLOG(6, "seq.start:%zi, literals=%u, match.start:%zi", anchor-(const BYTE*)source, litLength, ip-(const BYTE*)source); } _next_match: @@ -793,29 +791,33 @@ _next_match: if (maybe_ext_memSegment) { /* static test */ assert(offset <= MAX_DISTANCE && offset > 0); LZ4_writeLE16(op, (U16)offset); op+=2; + DEBUGLOG(6, " with offset=%u (ext if > %zi)", offset, ip - (const BYTE*)source); } else { assert(ip-match <= MAX_DISTANCE); LZ4_writeLE16(op, (U16)(ip - match)); op+=2; + DEBUGLOG(6, " with offset=%u (same segment)", (U32)(ip - match)); } /* Encode MatchLength */ { unsigned matchCode; if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx) - && (lowLimit==dictionary) ) { - const BYTE* limit; - limit = ip + (dictEnd-match); + && (lowLimit==dictionary) /* match within extDict */ ) { + const BYTE* limit = ip + (dictEnd-match); + assert(dictEnd > match); if (limit > matchlimit) limit = matchlimit; matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit); ip += MINMATCH + matchCode; if (ip==limit) { - unsigned const more = LZ4_count(ip, (const BYTE*)source, matchlimit); + unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit); matchCode += more; ip += more; } + DEBUGLOG(6, " with matchLength=%u starting in extDict", matchCode+MINMATCH); } else { matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit); ip += MINMATCH + matchCode; + DEBUGLOG(6, " with matchLength=%u", matchCode+MINMATCH); } if ( outputLimited && /* Check output buffer overflow */ @@ -865,14 +867,18 @@ _next_match: /* there was no match, try the dictionary */ matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32); match = dictBase + matchIndex; + lowLimit = dictionary; /* required for match length counter */ } else { match = base + matchIndex; + lowLimit = (const BYTE*)source; /* required for match length counter */ } } else if (dictDirective==usingExtDict) { if (matchIndex < startIndex) { match = dictBase + matchIndex; + lowLimit = dictionary; /* required for match length counter */ } else { match = base + matchIndex; + lowLimit = (const BYTE*)source; /* required for match length counter */ } } else { /* single memory segment */ match = base + matchIndex; @@ -885,6 +891,7 @@ _next_match: *token=0; if (maybe_ext_memSegment) offset = current - matchIndex; + DEBUGLOG(6, "seq.start:%zi, literals=%u, match.start:%zi", anchor-(const BYTE*)source, 0, ip-(const BYTE*)source); goto _next_match; } } -- cgit v0.12 From 98811d606808da9f59affd990670ba34e5a9bee2 Mon Sep 17 00:00:00 2001 From: Cyan4973 Date: Fri, 13 Apr 2018 00:59:27 -0700 Subject: added sudo rights for low-mem-address tests --- .travis.yml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/.travis.yml b/.travis.yml index a446420..0a876f9 100644 --- a/.travis.yml +++ b/.travis.yml @@ -14,7 +14,7 @@ matrix: env: Ubu=12.04cont Cmd='make -C tests test-lz4 test-lz4c test-fullbench' COMPILER=cc - os: linux - sudo: false + sudo: required env: Ubu=12.04cont Cmd='sudo sysctl -w vm.mmap_min_addr="4096" && make -C tests test-frametest test-fuzzer' COMPILER=cc - os: linux -- cgit v0.12 From 57afa36795f478d0f9b069ad19b578761e3fb16a Mon Sep 17 00:00:00 2001 From: Cyan4973 Date: Fri, 13 Apr 2018 01:01:54 -0700 Subject: compatibility with gcc-4.4 string.h version Someone found it would be a great idea to define there a global variable under the very generic name "index". Cause problem with shadow warnings, so no variable can be named "index" now ... Also : automatically update API manual --- doc/lz4_manual.html | 94 ++++++++++++++++++++++++++++++++++++++++------------- lib/lz4.c | 6 ++-- 2 files changed, 75 insertions(+), 25 deletions(-) diff --git a/doc/lz4_manual.html b/doc/lz4_manual.html index d14467f..f8639fe 100644 --- a/doc/lz4_manual.html +++ b/doc/lz4_manual.html @@ -15,8 +15,9 @@
  • Advanced Functions
  • Streaming Compression Functions
  • Streaming Decompression Functions
    • -
  • Private definitions
    • -
  • Obsolete Functions
    • +
  • Unstable declarations
    • +
  • Private definitions
    • +
  • Obsolete Functions

    • Introduction

    @@ -245,22 +246,80 @@ int LZ4_decompress_fast_usingDict (const char* src, char* dst, int originalSize,

    -

    Private definitions

    +
    Unstable declarations
    + Declarations in this section should be considered unstable.
+ Use at your own peril, etc., etc.
+ They may be removed in the future.
+ Their signatures may change.
+
    
+
+
    void LZ4_resetStream_fast (LZ4_stream_t* streamPtr);
+
      When an LZ4_stream_t is known to be in a internally coherent state,
+  it can often be prepared for a new compression with almost no work, only
+  sometimes falling back to the full, expensive reset that is always required
+  when the stream is in an indeterminate state (i.e., the reset performed by
+  LZ4_resetStream()).
+
+  LZ4_streams are guaranteed to be in a valid state when:
+  - returned from LZ4_createStream()
+  - reset by LZ4_resetStream()
+  - memset(stream, 0, sizeof(LZ4_stream_t))
+  - the stream was in a valid state and was reset by LZ4_resetStream_fast()
+  - the stream was in a valid state and was then used in any compression call
+    that returned success
+  - the stream was in an indeterminate state and was used in a compression
+    call that fully reset the state (LZ4_compress_fast_extState()) and that
+    returned success
+ 
+

    
+
+
    int LZ4_compress_fast_extState_fastReset (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration);
+
      A variant of LZ4_compress_fast_extState().
+
+  Using this variant avoids an expensive initialization step. It is only safe
+  to call if the state buffer is known to be correctly initialized already
+  (see above comment on LZ4_resetStream_fast() for a definition of "correctly
+  initialized"). From a high level, the difference is that this function
+  initializes the provided state with a call to LZ4_resetStream_fast() while
+  LZ4_compress_fast_extState() starts with a call to LZ4_resetStream().
+ 
+

    
+
+
    void LZ4_attach_dictionary(LZ4_stream_t *working_stream, const LZ4_stream_t *dictionary_stream);
+
      This is an experimental API that allows for the efficient use of a
+  static dictionary many times.
+
+  Rather than re-loading the dictionary buffer into a working context before
+  each compression, or copying a pre-loaded dictionary's LZ4_stream_t into a
+  working LZ4_stream_t, this function introduces a no-copy setup mechanism,
+  in which the working stream references the dictionary stream in-place.
+
+  Several assumptions are made about the state of the dictionary stream.
+  Currently, only streams which have been prepared by LZ4_loadDict() should
+  be expected to work.
+
+  Alternatively, the provided dictionary stream pointer may be NULL, in which
+  case any existing dictionary stream is unset.
+
+  If a dictionary is provided, it replaces any pre-existing stream history.
+  The dictionary contents are the only history that can be referenced and
+  logically immediately precede the data compressed in the first subsequent
+  compression call.
+
+  The dictionary will only remain attached to the working stream through the
+  first compression call, at the end of which it is cleared. The dictionary
+  stream (and source buffer) must remain in-place / accessible / unchanged
+  through the completion of the first compression call on the stream.
+ 
+

    
+
+
    Private definitions
      Do not use these definitions.
  They are exposed to allow static allocation of `LZ4_stream_t` and `LZ4_streamDecode_t`.
  Using these definitions will expose code to API and/or ABI break in future versions of the library.
 
    
 
 
    typedef struct {
-    uint32_t hashTable[LZ4_HASH_SIZE_U32];
-    uint32_t currentOffset;
-    uint32_t initCheck;
-    const uint8_t* dictionary;
-    uint8_t* bufferStart;   /* obsolete, used for slideInputBuffer */
-    uint32_t dictSize;
-} LZ4_stream_t_internal;
-

    
-
    typedef struct {
     const uint8_t* externalDict;
     size_t extDictSize;
     const uint8_t* prefixEnd;
@@ -268,15 +327,6 @@ int LZ4_decompress_fast_usingDict (const char* src, char* dst, int originalSize,
 } LZ4_streamDecode_t_internal;
 

    
 
    typedef struct {
-    unsigned int hashTable[LZ4_HASH_SIZE_U32];
-    unsigned int currentOffset;
-    unsigned int initCheck;
-    const unsigned char* dictionary;
-    unsigned char* bufferStart;   /* obsolete, used for slideInputBuffer */
-    unsigned int dictSize;
-} LZ4_stream_t_internal;
-

    
-
    typedef struct {
     const unsigned char* externalDict;
     size_t extDictSize;
     const unsigned char* prefixEnd;
@@ -311,7 +361,7 @@ union LZ4_streamDecode_u {
  
 

    
 
-
    Obsolete Functions
    
+
    Obsolete Functions
    
 
 
    #ifdef LZ4_DISABLE_DEPRECATE_WARNINGS
 #  define LZ4_DEPRECATED(message)   /* disable deprecation warnings */
diff --git a/lib/lz4.c b/lib/lz4.c
index 21892d3..f55e4e1 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -517,15 +517,15 @@ LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tab
     return LZ4_hash4(LZ4_read32(p), tableType);
 }
 
-static void LZ4_putIndexOnHash(U32 index, U32 h, void* tableBase, tableType_t const tableType)
+static void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType)
 {
     switch (tableType)
     {
     default: /* fallthrough */
     case clearedTable: /* fallthrough */
     case byPtr: { /* illegal! */ assert(0); return; }
-    case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = index; return; }
-    case byU16: { U16* hashTable = (U16*) tableBase; assert(index < 65536); hashTable[h] = (U16)index; return; }
+    case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; }
+    case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536); hashTable[h] = (U16)idx; return; }
     }
 }
 
-- 
cgit v0.12


From 54ec83ce1f62014398b76a441d1ff1212dad9604 Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Fri, 13 Apr 2018 02:10:53 -0700
Subject: fixed potential ptrdiff_t overflow (32-bits mode)

Also removed pointer comparison, which should solve #485
---
 lib/lz4.c | 25 +++++++++++--------------
 1 file changed, 11 insertions(+), 14 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index f55e4e1..c48aca4 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -1315,15 +1315,14 @@ void LZ4_attach_dictionary(LZ4_stream_t *working_stream, const LZ4_stream_t *dic
 }
 
 
-static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)
+static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize)
 {
-    if ((LZ4_dict->currentOffset > 0x80000000) ||
-        ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) {   /* address space overflow */
+    if (LZ4_dict->currentOffset + nextSize > 0x80000000) {   /* potential ptrdiff_t overflow (32-bits mode) */
         /* rescale hash table */
         U32 const delta = LZ4_dict->currentOffset - 64 KB;
         const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
         int i;
-        DEBUGLOG(4, "LZ4_renormDictT %p", LZ4_dict);
+        DEBUGLOG(4, "LZ4_renormDictT");
         for (i=0; ihashTable[i] < delta) LZ4_dict->hashTable[i]=0;
             else LZ4_dict->hashTable[i] -= delta;
@@ -1341,10 +1340,8 @@ int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, ch
     LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse;
     const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
 
-    const BYTE* smallest = (const BYTE*) source;
     if (streamPtr->initCheck) return 0;   /* Uninitialized structure detected */
-    if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;
-    LZ4_renormDictT(streamPtr, smallest);
+    LZ4_renormDictT(streamPtr, inputSize);   /* avoid index overflow */
     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
 
     /* Check overlapping input/dictionary space */
@@ -1377,7 +1374,7 @@ int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, ch
             if (inputSize > 4 KB) {
                 /* For compressing large blobs, it is faster to pay the setup
                  * cost to copy the dictionary's tables into the active context,
-                 * so that the compression loop is only looking in one table.
+                 * so that the compression loop is only looking into one table.
                  */
                 memcpy(streamPtr, streamPtr->dictCtx, sizeof(LZ4_stream_t));
                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
@@ -1398,8 +1395,8 @@ int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, ch
 }
 
 
-/* Hidden debug function, to force external dictionary mode */
-int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)
+/* Hidden debug function, to force-test external dictionary mode */
+int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize)
 {
     LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
     int result;
@@ -1407,16 +1404,16 @@ int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char*
 
     const BYTE* smallest = dictEnd;
     if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;
-    LZ4_renormDictT(streamPtr, smallest);
+    LZ4_renormDictT(streamPtr, srcSize);
 
     if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
-        result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, dictSmall, 1);
+        result = LZ4_compress_generic(streamPtr, source, dest, srcSize, 0, notLimited, byU32, usingExtDict, dictSmall, 1);
     } else {
-        result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
+        result = LZ4_compress_generic(streamPtr, source, dest, srcSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
     }
 
     streamPtr->dictionary = (const BYTE*)source;
-    streamPtr->dictSize = (U32)inputSize;
+    streamPtr->dictSize = (U32)srcSize;
 
     return result;
 }
-- 
cgit v0.12


From c40bac31d3886c2f69d0364823b6d6aaa972ee5b Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Fri, 13 Apr 2018 02:26:14 -0700
Subject: added comment on variables required after _next_match

---
 lib/lz4.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/lz4.c b/lib/lz4.c
index c48aca4..54d037c 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -787,6 +787,14 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
         }
 
 _next_match:
+        /* at this stage, the following variables must be correctly set :
+         * - ip : at start of LZ operation
+         * - match : at start of previous pattern occurence; can be within current prefix, or within extDict
+         * - offset : if maybe_ext_memSegment==1 (constant)
+         * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise
+         * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written
+         */
+
         /* Encode Offset */
         if (maybe_ext_memSegment) {   /* static test */
             assert(offset <= MAX_DISTANCE && offset > 0);
-- 
cgit v0.12


From d2bcfa31f525aaa11c2d248af0ba487791399c1f Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Fri, 13 Apr 2018 02:45:32 -0700
Subject: fixed minor unused variable warning

---
 lib/lz4.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index 54d037c..e8f9831 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -1408,10 +1408,7 @@ int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char*
 {
     LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
     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(streamPtr, srcSize);
 
     if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
-- 
cgit v0.12


From e9280647976ca468ab67ffbf3dd9c8e533fe23bf Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Mon, 16 Apr 2018 15:11:28 -0700
Subject: fixed gcc performance regression

---
 lib/lz4.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index e8f9831..c2012f6 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -660,6 +660,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
     /* Init conditions */
     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0;   /* Unsupported inputSize, too large (or negative) */
     if (tableType==byPtr) assert(dictDirective==noDict);      /* only supported use case with byPtr */
+    assert(acceleration >= 1);
 
     lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0);
 
@@ -712,6 +713,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
         } else {   /* byU32, byU16 */
 
             const BYTE* forwardIp = ip;
+            unsigned step = 1;
             unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
             do {
                 U32 const h = forwardH;
@@ -720,8 +722,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
                 assert(matchIndex <= current);
                 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1));
                 ip = forwardIp;
-                assert(searchMatchNb >= (1<> LZ4_skipTrigger);
+                forwardIp += step;
+                step = (searchMatchNb++ >> LZ4_skipTrigger);
 
                 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals;
                 assert(ip < mflimitPlusOne);
-- 
cgit v0.12


From 4aff9b10b56e44b2ff6326f611c3659565812d80 Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Mon, 16 Apr 2018 16:14:28 -0700
Subject: fixed fuzzer tests

which were modified in parallel within branc `dev`
---
 tests/fuzzer.c | 32 +++++++++++++++++---------------
 1 file changed, 17 insertions(+), 15 deletions(-)

diff --git a/tests/fuzzer.c b/tests/fuzzer.c
index 83ab50b..7721345 100644
--- a/tests/fuzzer.c
+++ b/tests/fuzzer.c
@@ -454,7 +454,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
         FUZ_CHECKTEST(ret==0, "LZ4_compress_fast_extState() failed");
 
         /* Test compression using fast reset external state*/
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         ret = LZ4_compress_fast_extState_fastReset(stateLZ4, block, compressedBuffer, blockSize, (int)compressedBufferSize, 8);
         FUZ_CHECKTEST(ret==0, "LZ4_compress_fast_extState_fastReset() failed");
 
@@ -687,7 +687,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
         }   }
 
         /* Compress using external dictionary stream */
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         {
             LZ4_stream_t LZ4_stream;
             int expectedSize;
@@ -713,13 +713,13 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
             FUZ_CHECKTEST(blockContinueCompressedSize != expectedSize, "LZ4_compress_fast_continue using extDictCtx produced different-sized output (%d expected vs %d actual)", expectedSize, blockContinueCompressedSize);
             FUZ_CHECKTEST(XXH32(compressedBuffer, blockContinueCompressedSize, 0) != expectedCrc, "LZ4_compress_fast_continue using extDictCtx produced different output");
 
-            FUZ_DISPLAYTEST;
+            FUZ_DISPLAYTEST();
             LZ4_resetStream(&LZ4_stream);
             LZ4_attach_dictionary(&LZ4_stream, &LZ4dict);
             ret = LZ4_compress_fast_continue(&LZ4_stream, block, compressedBuffer, blockSize, blockContinueCompressedSize-1, 1);
             FUZ_CHECKTEST(ret>0, "LZ4_compress_fast_continue using extDictCtx should fail : one missing byte for output buffer : %i written, %i buffer", ret, blockContinueCompressedSize);
 
-            FUZ_DISPLAYTEST;
+            FUZ_DISPLAYTEST();
             LZ4_resetStream(&LZ4_stream);
             LZ4_attach_dictionary(&LZ4_stream, &LZ4dict);
             ret = LZ4_compress_fast_continue(&LZ4_stream, block, compressedBuffer, blockSize, blockContinueCompressedSize, 1);
@@ -728,7 +728,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
             FUZ_CHECKTEST(ret != expectedSize, "LZ4_compress_fast_continue using extDictCtx produced different-sized output");
             FUZ_CHECKTEST(XXH32(compressedBuffer, ret, 0) != expectedCrc, "LZ4_compress_fast_continue using extDictCtx produced different output");
 
-            FUZ_DISPLAYTEST;
+            FUZ_DISPLAYTEST();
             LZ4_resetStream_fast(&LZ4_stream);
             LZ4_attach_dictionary(&LZ4_stream, &LZ4dict);
             ret = LZ4_compress_fast_continue(&LZ4_stream, block, compressedBuffer, blockSize, blockContinueCompressedSize, 1);
@@ -739,36 +739,38 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
         }
 
         /* Decompress with dictionary as external */
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         decodedBuffer[blockSize] = 0;
         ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize, dict, dictSize);
         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) FUZ_findDiff(block, decodedBuffer);
-        FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize);
+        {   U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0);
+            if (crcCheck!=crcOrig) FUZ_findDiff(block, decodedBuffer);
+            FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_fast_usingDict corrupted decoded data (dict %i)", dictSize);
+        }
 
-        FUZ_DISPLAYTEST;
+        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);
-        FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data");
+        {   U32 const crcCheck = XXH32(decodedBuffer, blockSize, 0);
+            FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe_usingDict corrupted decoded data");
+        }
 
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         decodedBuffer[blockSize-1] = 0;
         ret = LZ4_decompress_fast_usingDict(compressedBuffer, decodedBuffer, blockSize-1, dict, dictSize);
         FUZ_CHECKTEST(ret>=0, "LZ4_decompress_fast_usingDict should have failed : wrong original size (-1 byte)");
         FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_fast_usingDict overrun specified output buffer size");
 
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         decodedBuffer[blockSize-1] = 0;
         ret = LZ4_decompress_safe_usingDict(compressedBuffer, decodedBuffer, blockContinueCompressedSize, blockSize-1, dict, dictSize);
         FUZ_CHECKTEST(ret>=0, "LZ4_decompress_safe_usingDict should have failed : not enough output size (-1 byte)");
         FUZ_CHECKTEST(decodedBuffer[blockSize-1], "LZ4_decompress_safe_usingDict overrun specified output buffer size");
 
-        FUZ_DISPLAYTEST;
+        FUZ_DISPLAYTEST();
         {   U32 const missingBytes = (FUZ_rand(&randState) & 0xF) + 2;
             if ((U32)blockSize > missingBytes) {
                 decodedBuffer[blockSize-missingBytes] = 0;
-- 
cgit v0.12


From a3aeb34184e20d51616beccfcbbe7aade3cc3a64 Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Mon, 16 Apr 2018 16:54:03 -0700
Subject: fixed minor format warnings

---
 lib/lz4.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index c2012f6..980a5fd 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -785,7 +785,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
             /* Copy Literals */
             LZ4_wildCopy(op, anchor, op+litLength);
             op+=litLength;
-            DEBUGLOG(6, "seq.start:%zi, literals=%u, match.start:%zi", anchor-(const BYTE*)source, litLength, ip-(const BYTE*)source);
+            DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source));
         }
 
 _next_match:
@@ -801,7 +801,7 @@ _next_match:
         if (maybe_ext_memSegment) {   /* static test */
             assert(offset <= MAX_DISTANCE && offset > 0);
             LZ4_writeLE16(op, (U16)offset); op+=2;
-            DEBUGLOG(6, "                with offset=%u  (ext if > %zi)", offset, ip - (const BYTE*)source);
+            DEBUGLOG(6, "                with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
         } else  {
             assert(ip-match <= MAX_DISTANCE);
             LZ4_writeLE16(op, (U16)(ip - match)); op+=2;
@@ -901,7 +901,7 @@ _next_match:
                 *token=0;
                 if (maybe_ext_memSegment)
                     offset = current - matchIndex;
-                DEBUGLOG(6, "seq.start:%zi, literals=%u, match.start:%zi", anchor-(const BYTE*)source, 0, ip-(const BYTE*)source);
+                DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source));
                 goto _next_match;
             }
         }
-- 
cgit v0.12


From 444211d2599a2be59e3f50418b46ec2431288e9a Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Mon, 16 Apr 2018 17:15:02 -0700
Subject: edited a few traces for debugging

---
 lib/lz4.c      | 14 +++++++-------
 tests/fuzzer.c |  6 +++---
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index 980a5fd..dca4d69 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -588,12 +588,12 @@ LZ4_FORCE_INLINE void LZ4_prepareTable(
           || tableType == byPtr
           || inputSize >= 4 KB)
         {
-            DEBUGLOG(4, "Resetting table in %p", cctx);
+            DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", cctx);
             MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE);
             cctx->currentOffset = 0;
             cctx->tableType = clearedTable;
         } else {
-            DEBUGLOG(4, "Re-use hash table (no reset)");
+            DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)");
         }
     }
 
@@ -799,13 +799,13 @@ _next_match:
 
         /* Encode Offset */
         if (maybe_ext_memSegment) {   /* static test */
+            DEBUGLOG(6, "             with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
             assert(offset <= MAX_DISTANCE && offset > 0);
             LZ4_writeLE16(op, (U16)offset); op+=2;
-            DEBUGLOG(6, "                with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
         } else  {
+            DEBUGLOG(6, "             with offset=%u  (same segment)", (U32)(ip - match));
             assert(ip-match <= MAX_DISTANCE);
             LZ4_writeLE16(op, (U16)(ip - match)); op+=2;
-            DEBUGLOG(6, "                with offset=%u  (same segment)", (U32)(ip - match));
         }
 
         /* Encode MatchLength */
@@ -823,11 +823,11 @@ _next_match:
                     matchCode += more;
                     ip += more;
                 }
-                DEBUGLOG(6, "                with matchLength=%u starting in extDict", matchCode+MINMATCH);
+                DEBUGLOG(6, "             with matchLength=%u starting in extDict", matchCode+MINMATCH);
             } else {
                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
                 ip += MINMATCH + matchCode;
-                DEBUGLOG(6, "                with matchLength=%u", matchCode+MINMATCH);
+                DEBUGLOG(6, "             with matchLength=%u", matchCode+MINMATCH);
             }
 
             if ( outputLimited &&    /* Check output buffer overflow */
@@ -1259,7 +1259,7 @@ LZ4_stream_t* LZ4_createStream(void)
 
 void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
 {
-    DEBUGLOG(5, "LZ4_resetStream %p", LZ4_stream);
+    DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", LZ4_stream);
     MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t));
 }
 
diff --git a/tests/fuzzer.c b/tests/fuzzer.c
index 7721345..244cc4f 100644
--- a/tests/fuzzer.c
+++ b/tests/fuzzer.c
@@ -687,19 +687,19 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
         }   }
 
         /* Compress using external dictionary stream */
-        FUZ_DISPLAYTEST();
         {
             LZ4_stream_t LZ4_stream;
             int expectedSize;
             U32 expectedCrc;
 
+            FUZ_DISPLAYTEST("LZ4_compress_fast_continue() after LZ4_loadDict()");
             LZ4_loadDict(&LZ4dict, dict, dictSize);
             expectedSize = LZ4_compress_fast_continue(&LZ4dict, block, compressedBuffer, blockSize, (int)compressedBufferSize, 1);
             FUZ_CHECKTEST(expectedSize<=0, "LZ4_compress_fast_continue reference compression for extDictCtx should have succeeded");
             expectedCrc = XXH32(compressedBuffer, expectedSize, 0);
 
+            FUZ_DISPLAYTEST("LZ4_compress_fast_continue() after LZ4_attach_dictionary()");
             LZ4_loadDict(&LZ4dict, dict, dictSize);
-
             LZ4_resetStream(&LZ4_stream);
             LZ4_attach_dictionary(&LZ4_stream, &LZ4dict);
             blockContinueCompressedSize = LZ4_compress_fast_continue(&LZ4_stream, block, compressedBuffer, blockSize, (int)compressedBufferSize, 1);
@@ -713,7 +713,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c
             FUZ_CHECKTEST(blockContinueCompressedSize != expectedSize, "LZ4_compress_fast_continue using extDictCtx produced different-sized output (%d expected vs %d actual)", expectedSize, blockContinueCompressedSize);
             FUZ_CHECKTEST(XXH32(compressedBuffer, blockContinueCompressedSize, 0) != expectedCrc, "LZ4_compress_fast_continue using extDictCtx produced different output");
 
-            FUZ_DISPLAYTEST();
+            FUZ_DISPLAYTEST("LZ4_compress_fast_continue() after LZ4_attach_dictionary(), but output buffer is 1 byte too short");
             LZ4_resetStream(&LZ4_stream);
             LZ4_attach_dictionary(&LZ4_stream, &LZ4dict);
             ret = LZ4_compress_fast_continue(&LZ4_stream, block, compressedBuffer, blockSize, blockContinueCompressedSize-1, 1);
-- 
cgit v0.12


From da3b5ba6f0014564b7312511e441067ba9429733 Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Mon, 16 Apr 2018 23:59:42 -0700
Subject: fixed dictCtx compression

---
 lib/lz4.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index dca4d69..0590de4 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -602,6 +602,7 @@ LZ4_FORCE_INLINE void LZ4_prepareTable(
      * currentOffset == 0 is faster still, so we preserve that case.
      */
     if (cctx->currentOffset != 0 && tableType == byU32) {
+        DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset");
         cctx->currentOffset += 64 KB;
     }
 
@@ -636,8 +637,9 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
         dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary;
     const U32 dictSize =
         dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize;
+    const U32 dictDelta = usingDictCtx ? startIndex - dictCtx->currentOffset : 0;   /* make indexes in dictCtx comparable with index in current context */
 
-    int const maybe_ext_memSegment = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
+    int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
     U32 const prefixIdxLimit = startIndex - dictSize;   /* used when dictDirective == dictSmall */
     const BYTE* const dictEnd = dictionary + dictSize;
     const BYTE* anchor = (const BYTE*) source;
@@ -648,7 +650,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
     /* the dictCtx currentOffset is indexed on the start of the dictionary,
      * while a dictionary in the current context precedes the currentOffset */
     const BYTE* dictBase = dictDirective == usingDictCtx ?
-        dictionary + dictSize - dictCtx->currentOffset :   /* is it possible that dictCtx->currentOffset != dictCtx->dictSize ? */
+        dictionary + dictSize - dictCtx->currentOffset :   /* is it possible that dictCtx->currentOffset != dictCtx->dictSize ? Yes if the dictionary context is not reset */
         dictionary + dictSize - startIndex;
 
     BYTE* op = (BYTE*) dest;
@@ -657,6 +659,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
     U32 offset = 0;
     U32 forwardH;
 
+    DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, tableType=%u", inputSize, tableType);
     /* Init conditions */
     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0;   /* Unsupported inputSize, too large (or negative) */
     if (tableType==byPtr) assert(dictDirective==noDict);      /* only supported use case with byPtr */
@@ -731,8 +734,10 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
                 if (dictDirective == usingDictCtx) {
                     if (matchIndex < startIndex) {
                         /* there was no match, try the dictionary */
+                        assert(tableType == byU32);
                         matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
                         match = dictBase + matchIndex;
+                        matchIndex += dictDelta;   /* make dictCtx index comparable with current context */
                         lowLimit = dictionary;
                     } else {
                         match = base + matchIndex;
@@ -758,7 +763,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
                 if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE);     /* too_far presumed impossible with byU16 */
 
                 if (LZ4_read32(match) == LZ4_read32(ip)) {
-                    if (maybe_ext_memSegment) offset = current - matchIndex;
+                    if (maybe_extMem) offset = current - matchIndex;
                     break;   /* match found */
                 }
 
@@ -798,7 +803,7 @@ _next_match:
          */
 
         /* Encode Offset */
-        if (maybe_ext_memSegment) {   /* static test */
+        if (maybe_extMem) {   /* static test */
             DEBUGLOG(6, "             with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
             assert(offset <= MAX_DISTANCE && offset > 0);
             LZ4_writeLE16(op, (U16)offset); op+=2;
@@ -878,6 +883,7 @@ _next_match:
                     matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
                     match = dictBase + matchIndex;
                     lowLimit = dictionary;   /* required for match length counter */
+                    matchIndex += dictDelta;
                 } else {
                     match = base + matchIndex;
                     lowLimit = (const BYTE*)source;  /* required for match length counter */
@@ -899,8 +905,7 @@ _next_match:
               && (LZ4_read32(match) == LZ4_read32(ip)) ) {
                 token=op++;
                 *token=0;
-                if (maybe_ext_memSegment)
-                    offset = current - matchIndex;
+                if (maybe_extMem) offset = current - matchIndex;
                 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i", (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source));
                 goto _next_match;
             }
@@ -1285,7 +1290,7 @@ int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
     const BYTE* const dictEnd = p + dictSize;
     const BYTE* base;
 
-    DEBUGLOG(4, "LZ4_loadDict (%p into %p)", dictionary, LZ4_dict);
+    DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, dictionary, LZ4_dict);
 
     LZ4_prepareTable(dict, 0, tableType);
 
-- 
cgit v0.12


From 152064218361e5762fd67b5de425707fdc47095b Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Tue, 17 Apr 2018 15:29:17 -0700
Subject: fix matchIndex overflow

can happen with dictCtx
---
 lib/lz4.c | 16 ++++------------
 1 file changed, 4 insertions(+), 12 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index b426545..c799596 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -758,9 +758,9 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
                 forwardH = LZ4_hashPosition(forwardIp, tableType);
                 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
 
-                if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) continue;    /* match outside of valid area */
-                if ((tableType != byU16) && (matchIndex+MAX_DISTANCE < current)) continue;  /* too far */
-                if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE);     /* too_far presumed impossible with byU16 */
+                if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) continue;     /* match outside of valid area */
+                if ((tableType != byU16) && (current - matchIndex > MAX_DISTANCE)) continue; /* too far - note: works even if matchIndex overflows */
+                if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE);      /* too_far presumed impossible with byU16 */
 
                 if (LZ4_read32(match) == LZ4_read32(ip)) {
                     if (maybe_extMem) offset = current - matchIndex;
@@ -861,7 +861,6 @@ _next_match:
         /* Fill table */
         LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
 
-#if 1
         /* Test next position */
         if (tableType == byPtr) {
 
@@ -901,7 +900,7 @@ _next_match:
             }
             LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
             if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1)
-              && ((tableType==byU16) ? 1 : (matchIndex+MAX_DISTANCE >= current))
+              && ((tableType==byU16) ? 1 : (current - matchIndex <= MAX_DISTANCE))
               && (LZ4_read32(match) == LZ4_read32(ip)) ) {
                 token=op++;
                 *token=0;
@@ -914,13 +913,6 @@ _next_match:
         /* Prepare next loop */
         forwardH = LZ4_hashPosition(++ip, tableType);
 
-#else
-
-        /* Prepare next loop */
-        forwardH = LZ4_hashPosition(ip, tableType);
-
-#endif
-
     }
 
 _last_literals:
-- 
cgit v0.12


From 88cca1723e76c8f5031954ba07b28447c0cb55d8 Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Tue, 17 Apr 2018 16:18:37 -0700
Subject: fix dictDelta setting error

wrong test
---
 lib/lz4.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index c799596..e7553ed 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -637,7 +637,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic(
         dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary;
     const U32 dictSize =
         dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize;
-    const U32 dictDelta = usingDictCtx ? startIndex - dictCtx->currentOffset : 0;   /* make indexes in dictCtx comparable with index in current context */
+    const U32 dictDelta = (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0;   /* make indexes in dictCtx comparable with index in current context */
 
     int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
     U32 const prefixIdxLimit = startIndex - dictSize;   /* used when dictDirective == dictSmall */
-- 
cgit v0.12


From 5ad4599c5ad18d2408a6ccc545c45a36b99f0c6f Mon Sep 17 00:00:00 2001
From: Yann Collet 
Date: Tue, 17 Apr 2018 16:47:56 -0700
Subject: fixed LZ4_compress_fast_extState_fastReset() in 32-bit mode

---
 lib/lz4.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/lz4.c b/lib/lz4.c
index e7553ed..33aa5c7 100644
--- a/lib/lz4.c
+++ b/lib/lz4.c
@@ -983,7 +983,7 @@ int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst
                 return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
             }
         } else {
-            const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr;
+            const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32;
             LZ4_prepareTable(ctx, srcSize, tableType);
             return LZ4_compress_generic(ctx, src, dst, srcSize, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
         }
@@ -997,7 +997,7 @@ int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst
                 return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
             }
         } else {
-            const tableType_t tableType = (sizeof(void*)==8) ? byU32 : byPtr;
+            const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32;
             LZ4_prepareTable(ctx, srcSize, tableType);
             return LZ4_compress_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
         }
-- 
cgit v0.12