From efbebd2a9955c6a6eabc558f00643abb4690edac Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 6 May 2015 02:29:04 +0100 Subject: Added : LZ4_compress_destSize() --- lib/Makefile | 4 +- lib/lz4.c | 221 +++++++++++++++++++++++++++++++++++++++++++++++++++++- lib/lz4.h | 15 ++++ programs/fuzzer.c | 35 +++++++++ 4 files changed, 269 insertions(+), 6 deletions(-) diff --git a/lib/Makefile b/lib/Makefile index 8aa15de..ef671d3 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -31,7 +31,7 @@ # ################################################################ # Version numbers -VERSION ?= 128 +VERSION ?= 129 LIBVER_MAJOR=`sed -n '/define LZ4_VERSION_MAJOR/s/.*[[:blank:]]\([0-9][0-9]*\).*/\1/p' < lz4.h` LIBVER_MINOR=`sed -n '/define LZ4_VERSION_MINOR/s/.*[[:blank:]]\([0-9][0-9]*\).*/\1/p' < lz4.h` LIBVER_PATCH=`sed -n '/define LZ4_VERSION_RELEASE/s/.*[[:blank:]]\([0-9][0-9]*\).*/\1/p' < lz4.h` @@ -40,7 +40,7 @@ LIBVER=$(LIBVER_MAJOR).$(LIBVER_MINOR).$(LIBVER_PATCH) DESTDIR?= PREFIX ?= /usr/local CFLAGS ?= -O3 -CFLAGS += -I. -std=c99 -Wall -Wextra -Wundef -Wshadow -Wcast-align -Wstrict-prototypes -pedantic +CFLAGS += -I. -std=c99 -Wall -Wextra -Wundef -Wshadow -Wcast-align -Wcast-qual Wstrict-prototypes -pedantic LIBDIR?= $(PREFIX)/lib INCLUDEDIR=$(PREFIX)/include diff --git a/lib/lz4.c b/lib/lz4.c index c511456..55f2359 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -679,7 +679,7 @@ int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration) { #if (HEAPMODE) - void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t_internal)); /* malloc-calloc always properly aligned */ + void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ #else LZ4_stream_t ctx; void* ctxPtr = &ctx; @@ -715,9 +715,222 @@ int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int m } -/***************************************** -* Experimental : Streaming functions -*****************************************/ +/******************************** +* destSize variant +********************************/ + +static int LZ4_compress_destSize_generic( + void* const ctx, + const char* const src, + char* const dst, + int* const srcSizePtr, + const int targetDstSize, + const tableType_t tableType) +{ + const BYTE* ip = (const BYTE*) src; + const BYTE* base = (const BYTE*) src; + const BYTE* lowLimit = (const BYTE*) src; + const BYTE* anchor = ip; + const BYTE* const iend = ip + *srcSizePtr; + const BYTE* const mflimit = iend - MFLIMIT; + const BYTE* const matchlimit = iend - LASTLITERALS; + + BYTE* op = (BYTE*) dst; + BYTE* const oend = op + targetDstSize; + BYTE* const oMaxLit = op + targetDstSize - 2 /* offset */ - 8 /* because 8+MINMATCH==MFLIMIT */ - 1 /* token */; + BYTE* const oMaxMatch = op + targetDstSize - (LASTLITERALS + 1 /* token */); + BYTE* const oMaxSeq = oMaxLit - 1 /* token */; + + U32 forwardH; + + + /* Init conditions */ + if (targetDstSize < 1) return 0; /* Impossible to store anything */ + if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ + if ((tableType == byU16) && (*srcSizePtr>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */ + if (*srcSizePtr> LZ4_skipTrigger); + + if (unlikely(forwardIp > mflimit)) + goto _last_literals; + + match = LZ4_getPositionOnHash(h, ctx, tableType, base); + forwardH = LZ4_hashPosition(forwardIp, tableType); + LZ4_putPositionOnHash(ip, h, ctx, tableType, base); + + } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip)) + || (LZ4_read32(match) != LZ4_read32(ip)) ); + } + + /* Catch up */ + while ((ip>anchor) && (match > lowLimit) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; } + + { + /* Encode Literal length */ + unsigned litLength = (unsigned)(ip - anchor); + token = op++; + if (op + ((litLength+240)/255) + litLength > oMaxLit) + { + /* Not enough space for a last match */ + op--; + goto _last_literals; + } + if (litLength>=RUN_MASK) + { + unsigned len = litLength - RUN_MASK; + *token=(RUN_MASK<= 255 ; len-=255) *op++ = 255; + *op++ = (BYTE)len; + } + else *token = (BYTE)(litLength< oMaxMatch) + { + /* Match description too long : reduce it */ + matchLength = (15-1) + (oMaxMatch-op) * 255; + } + //printf("offset %5i, matchLength%5i \n", (int)(ip-match), matchLength + MINMATCH); + ip += MINMATCH + matchLength; + + if (matchLength>=ML_MASK) + { + *token += ML_MASK; + matchLength -= ML_MASK; + while (matchLength >= 255) { matchLength-=255; *op++ = 255; } + *op++ = (BYTE)matchLength; + } + else *token += (BYTE)(matchLength); + } + + anchor = ip; + + /* Test end of block */ + if (ip > mflimit) break; + if (op > oMaxSeq) break; + + /* Fill table */ + LZ4_putPosition(ip-2, ctx, tableType, base); + + /* Test next position */ + match = LZ4_getPosition(ip, ctx, tableType, base); + LZ4_putPosition(ip, ctx, tableType, base); + if ( (match+MAX_DISTANCE>=ip) + && (LZ4_read32(match)==LZ4_read32(ip)) ) + { token=op++; *token=0; goto _next_match; } + + /* Prepare next loop */ + forwardH = LZ4_hashPosition(++ip, tableType); + } + +_last_literals: + /* Encode Last Literals */ + { + size_t lastRunSize = (size_t)(iend - anchor); + if (op + 1 /* token */ + ((lastRunSize+240)/255) /* litLength */ + lastRunSize /* literals */ > oend) + { + /* adapt lastRunSize to fill 'dst' */ + lastRunSize = (oend-op) - 1; + lastRunSize -= (lastRunSize+240)/255; + } + ip = anchor + lastRunSize; + + if (lastRunSize >= RUN_MASK) + { + size_t accumulator = lastRunSize - RUN_MASK; + *op++ = RUN_MASK << ML_BITS; + for(; accumulator >= 255 ; accumulator-=255) *op++ = 255; + *op++ = (BYTE) accumulator; + } + else + { + *op++ = (BYTE)(lastRunSize<= LZ4_compressBound(*srcSizePtr)) /* compression success is guaranteed */ + { + return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1); + } + else + { + if (*srcSizePtr < LZ4_64Klimit) + return LZ4_compress_destSize_generic(state, src, dst, srcSizePtr, targetDstSize, byU16); + else + return LZ4_compress_destSize_generic(state, src, dst, srcSizePtr, targetDstSize, LZ4_64bits() ? byU32 : byPtr); + } +} + + +int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize) +{ +#if (HEAPMODE) + void* ctx = ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */ +#else + LZ4_stream_t ctxBody; + void* ctx = &ctxBody; +#endif + + int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize); + +#if (HEAPMODE) + FREEMEM(ctx); +#endif + return result; +} + + + +/******************************** +* Streaming functions +********************************/ LZ4_stream_t* LZ4_createStream(void) { diff --git a/lib/lz4.h b/lib/lz4.h index 00304d8..93388c2 100644 --- a/lib/lz4.h +++ b/lib/lz4.h @@ -140,6 +140,21 @@ int LZ4_compress_fast_extState (void* state, const char* source, char* dest, int /* +LZ4_compress_destSize() : + Reverse the logic, by compressing as much data as possible from 'source' buffer + into already allocated buffer 'dest' of size 'targetDestSize'. + This function either compresses the entire 'source' content into 'dest' if it's large enough, + or fill 'dest' buffer completely with as much data as possible from 'source'. + Original idea by WiredTiger team. + *sourceSizePtr : will be modified to indicate how many bytes where read from 'source' to fill 'dest'. + New value is necessarily <= old value. + return : Nb bytes written into 'dest' (necessarily <= targetDestSize) + or 0 if compression fails +*/ +int LZ4_compress_destSize (const char* source, char* dest, int* sourceSizePtr, int targetDestSize); + + +/* LZ4_decompress_fast() : originalSize : is the original and therefore uncompressed size return : the number of bytes read from the source buffer (in other words, the compressed size) diff --git a/programs/fuzzer.c b/programs/fuzzer.c index 9fd4648..6588290 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -396,6 +396,41 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c /* Compression tests */ + /* Test compression destSize */ + FUZ_DISPLAYTEST; + { + int srcSize = blockSize; + int targetSize = srcSize * ((FUZ_rand(&randState) & 127)+1) >> 7; + char endCheck = FUZ_rand(&randState) & 255; + compressedBuffer[targetSize] = endCheck; + ret = LZ4_compress_destSize(block, compressedBuffer, &srcSize, targetSize); + FUZ_CHECKTEST(ret > targetSize, "LZ4_compress_destSize() result larger than dst buffer !"); + FUZ_CHECKTEST(compressedBuffer[targetSize] != endCheck, "LZ4_compress_destSize() overwrite dst buffer !"); + FUZ_CHECKTEST(srcSize > blockSize, "LZ4_compress_destSize() fed more than src buffer !"); + DISPLAY("destSize : %7i/%7i; content%7i/%7i ", ret, targetSize, srcSize, blockSize); + if (targetSize>0) + { + FUZ_CHECKTEST((ret==0), "LZ4_compress_destSize() compression failed"); + /* check correctness */ + FUZ_DISPLAYTEST; + + crcOrig = XXH32(block, srcSize, 0); + compressedSize = ret; + endCheck = FUZ_rand(&randState) & 255; + decodedBuffer[srcSize] = endCheck; + ret = LZ4_decompress_safe(compressedBuffer, decodedBuffer, compressedSize, srcSize); + FUZ_CHECKTEST(ret<0, "LZ4_decompress_safe() failed on data compressed by LZ4_compress_destSize"); + FUZ_CHECKTEST(ret!=srcSize, "LZ4_decompress_safe() failed : did not fully decompressed data"); + FUZ_CHECKTEST(decodedBuffer[srcSize] != endCheck, "LZ4_decompress_safe() overwrite dst buffer !"); + crcCheck = XXH32(decodedBuffer, srcSize, 0); + FUZ_CHECKTEST(crcCheck!=crcOrig, "LZ4_decompress_safe() corrupted decoded data"); + + DISPLAY(" OK \n"); + } + else + DISPLAY(" \n"); + } + /* Test compression HC */ FUZ_DISPLAYTEST; ret = LZ4_compressHC(block, compressedBuffer, blockSize); -- cgit v0.12