From e7fe105ac6ed02019d34731d2ba3aceb11b51bb1 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Sun, 27 Sep 2020 21:04:40 -0700 Subject: [PATCH] fix efficiency of LZ4_compress_HC_destSize() LZ4_compress_HC_destSize() had a tendency to discard its last match when this match overflowed specified dstBuffer limit. The impact is generally moderate, but occasionally huge, typically when this last match is very large (such as compressing a bunch of zeroes). Issue #784 fixed for both Chain and Opt implementations. Added a unit test suggested by @remittor checking this topic. --- lib/lz4.c | 3 +- lib/lz4hc.c | 90 ++++++++++++++++++++++++++++++++++++-------------- tests/fuzzer.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++----- 3 files changed, 161 insertions(+), 34 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 2222d53..c192d5b 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -247,6 +247,7 @@ static const int LZ4_minLength = (MFLIMIT+1); /*-************************************ * Types **************************************/ +#include #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) # include typedef uint8_t BYTE; @@ -256,7 +257,6 @@ static const int LZ4_minLength = (MFLIMIT+1); typedef uint64_t U64; typedef uintptr_t uptrval; #else -# include # if UINT_MAX != 4294967295UL # error "LZ4 code (when not C++ or C99) assumes that sizeof(int) == 4" # endif @@ -1192,6 +1192,7 @@ _last_literals: return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */ } } + DEBUGLOG(6, "Final literal run : %i literals", (int)lastRun); if (lastRun >= RUN_MASK) { size_t accumulator = lastRun - RUN_MASK; *op++ = RUN_MASK << ML_BITS; diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 687f87e..aefc95b 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -490,7 +490,9 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( /* Encode Literal length */ length = (size_t)(*ip - *anchor); - if ((limit) && ((*op + (length / 255) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */ + LZ4_STATIC_ASSERT(notLimited == 0); + /* Check output limit */ + if (limit && ((*op + (length / 255) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; if (length >= RUN_MASK) { size_t len = length - RUN_MASK; *token = (RUN_MASK << ML_BITS); @@ -511,7 +513,7 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( /* Encode MatchLength */ assert(matchLength >= MINMATCH); length = (size_t)matchLength - MINMATCH; - if ((limit) && (*op + (length / 255) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */ + if (limit && (*op + (length / 255) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */ if (length >= ML_MASK) { *token += ML_MASK; length -= ML_MASK; @@ -565,7 +567,7 @@ LZ4_FORCE_INLINE int LZ4HC_compress_hashChain ( /* init */ *srcSizePtr = 0; if (limit == fillOutput) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */ - if (inputSize < LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ + if (inputSize < LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ /* Main Loop */ while (ip <= mflimit) { @@ -637,7 +639,11 @@ _Search3: if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, ref, limit, oend)) goto _dest_overflow; ip = start2; optr = op; - if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml2, ref2, limit, oend)) goto _dest_overflow; + if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml2, ref2, limit, oend)) { + ml = ml2; + ref = ref2; + goto _dest_overflow; + } continue; } @@ -709,17 +715,18 @@ _Search3: _last_literals: /* Encode Last Literals */ { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ - size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; - size_t const totalSize = 1 + litLength + lastRunSize; + size_t llAdd = (lastRunSize + 255 - RUN_MASK) / 255; + size_t const totalSize = 1 + llAdd + lastRunSize; if (limit == fillOutput) oend += LASTLITERALS; /* restore correct value */ if (limit && (op + totalSize > oend)) { - if (limit == limitedOutput) return 0; /* Check output limit */ + if (limit == limitedOutput) return 0; /* adapt lastRunSize to fill 'dest' */ lastRunSize = (size_t)(oend - op) - 1; - litLength = (lastRunSize + 255 - RUN_MASK) / 255; - lastRunSize -= litLength; + llAdd = (lastRunSize + 256 - RUN_MASK) / 256; + lastRunSize -= llAdd; } - ip = anchor + lastRunSize; + DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize); + ip = ip + lastRunSize; /* can be != iend if limit==fillOutput */ if (lastRunSize >= RUN_MASK) { size_t accumulator = lastRunSize - RUN_MASK; @@ -739,9 +746,23 @@ _last_literals: _dest_overflow: if (limit == fillOutput) { + /* Assumption : ip, anchor, ml and ref must be set correctly */ + size_t const ll = (size_t)(ip - anchor); + size_t const ll_addbytes = (ll + 240) / 255; + size_t const ll_totalCost = 1 + ll_addbytes + ll; + BYTE* const maxLitPos = oend - 3; /* 2 for offset, 1 for token */ op = optr; /* restore correct out pointer */ + if (op + ll_totalCost <= maxLitPos) { + /* ll validated; now how many matches ? */ + size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost)); + size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255); + assert(maxMlSize < INT_MAX); assert(ml >= 0); + if ((size_t)ml > maxMlSize) ml = (int)maxMlSize; + LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, ref, notLimited, oend); + } goto _last_literals; } + /* compression failed */ return 0; } @@ -788,7 +809,8 @@ LZ4_FORCE_INLINE int LZ4HC_compress_generic_internal ( { lz4opt,16384,LZ4_OPT_NUM }, /* 12==LZ4HC_CLEVEL_MAX */ }; - DEBUGLOG(4, "LZ4HC_compress_generic(ctx=%p, src=%p, srcSize=%d)", ctx, src, *srcSizePtr); + DEBUGLOG(4, "LZ4HC_compress_generic(ctx=%p, src=%p, srcSize=%d, limit=%d)", + ctx, src, *srcSizePtr, limit); if (limit == fillOutput && dstCapacity < 1) return 0; /* Impossible to store anything */ if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size (too large or negative) */ @@ -1075,8 +1097,8 @@ static int LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr, limitedOutput_directive limit) { LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse; - DEBUGLOG(4, "LZ4_compressHC_continue_generic(ctx=%p, src=%p, srcSize=%d)", - LZ4_streamHCPtr, src, *srcSizePtr); + DEBUGLOG(5, "LZ4_compressHC_continue_generic(ctx=%p, src=%p, srcSize=%d, limit=%d)", + LZ4_streamHCPtr, src, *srcSizePtr, limit); assert(ctxPtr != NULL); /* auto-init if forgotten */ if (ctxPtr->base == NULL) LZ4HC_init_internal (ctxPtr, (const BYTE*) src); @@ -1303,6 +1325,8 @@ static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, BYTE* op = (BYTE*) dst; BYTE* opSaved = (BYTE*) dst; BYTE* oend = op + dstCapacity; + int ovml = MINMATCH; /* overflow - last sequence */ + const BYTE* ovref = NULL; /* init */ #ifdef LZ4HC_HEAPMODE @@ -1328,8 +1352,11 @@ static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, int const firstML = firstMatch.len; const BYTE* const matchPos = ip - firstMatch.off; opSaved = op; - if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), firstML, matchPos, limit, oend) ) /* updates ip, op and anchor */ + if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), firstML, matchPos, limit, oend) ) { /* updates ip, op and anchor */ + ovml = firstML; + ovref = matchPos; goto _dest_overflow; + } continue; } @@ -1471,7 +1498,7 @@ static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, best_off = opt[last_match_pos].off; cur = last_match_pos - best_mlen; - encode: /* cur, last_match_pos, best_mlen, best_off must be set */ +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 (last_match_pos=%i)", last_match_pos); @@ -1501,12 +1528,14 @@ static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, assert(ml >= MINMATCH); assert((offset >= 1) && (offset <= LZ4_DISTANCE_MAX)); opSaved = op; - if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, ip - offset, limit, oend) ) /* updates ip, op and anchor */ + if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, ip - offset, limit, oend) ) { /* updates ip, op and anchor */ + ovml = ml; + ovref = ip - offset; goto _dest_overflow; - } } + } } } } /* while (ip <= mflimit) */ - _last_literals: +_last_literals: /* Encode Last Literals */ { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; @@ -1541,14 +1570,27 @@ static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, retval = (int) ((char*)op-dst); goto _return_label; - _dest_overflow: - if (limit == fillOutput) { - op = opSaved; /* restore correct out pointer */ - goto _last_literals; +_dest_overflow: +if (limit == fillOutput) { + /* Assumption : ip, anchor, ovml and ovref must be set correctly */ + size_t const ll = (size_t)(ip - anchor); + size_t const ll_addbytes = (ll + 240) / 255; + size_t const ll_totalCost = 1 + ll_addbytes + ll; + BYTE* const maxLitPos = oend - 3; /* 2 for offset, 1 for token */ + op = opSaved; /* restore correct out pointer */ + if (op + ll_totalCost <= maxLitPos) { + /* ll validated; now how many matches ? */ + size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost)); + size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255); + assert(maxMlSize < INT_MAX); assert(ovml >= 0); + if ((size_t)ovml > maxMlSize) ovml = (int)maxMlSize; + LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ovml, ovref, notLimited, oend); } - _return_label: + goto _last_literals; +} +_return_label: #ifdef LZ4HC_HEAPMODE free(opt); #endif return retval; - } +} diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 1d8b5f6..e611bb4 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -1191,12 +1191,11 @@ static void FUZ_unitTests(int compressionLevel) /* LZ4 HC streaming tests */ { LZ4_streamHC_t sHC; /* statically allocated */ - U64 crcOrig; int result; LZ4_initStreamHC(&sHC, sizeof(sHC)); /* Allocation test */ - DISPLAYLEVEL(3, " Basic HC allocation : "); + DISPLAYLEVEL(3, "Basic HC allocation : "); { LZ4_streamHC_t* const sp = LZ4_createStreamHC(); FUZ_CHECKTEST(sp==NULL, "LZ4_createStreamHC() allocation failed"); LZ4_freeStreamHC(sp); @@ -1204,7 +1203,7 @@ static void FUZ_unitTests(int compressionLevel) DISPLAYLEVEL(3, " OK \n"); /* simple HC compression test */ - DISPLAYLEVEL(3, " Simple HC round-trip : "); + DISPLAYLEVEL(3, "Simple HC round-trip : "); { U64 const crc64 = XXH64(testInput, testCompressedSize, 0); LZ4_setCompressionLevel(&sHC, compressionLevel); result = LZ4_compress_HC_continue(&sHC, testInput, testCompressed, testCompressedSize, testCompressedSize-1); @@ -1219,7 +1218,7 @@ static void FUZ_unitTests(int compressionLevel) DISPLAYLEVEL(3, " OK \n"); /* long sequence test */ - DISPLAYLEVEL(3, " Long sequence HC test : "); + DISPLAYLEVEL(3, "Long sequence HC_destSize test : "); { size_t const blockSize = 1 MB; size_t const targetSize = 4116; /* size carefully selected to trigger an overflow */ void* const block = malloc(blockSize); @@ -1237,8 +1236,13 @@ static void FUZ_unitTests(int compressionLevel) assert(targetSize < INT_MAX); result = LZ4_compress_HC_destSize(&sHC, (const char*)block, (char*)dstBlock, &srcSize, (int)targetSize, 3); DISPLAYLEVEL(4, "cSize=%i; readSize=%i; ", result, srcSize); - FUZ_CHECKTEST(result!=4116, "LZ4_compress_HC_destSize() : compression must fill dstBuffer completely, but no more !"); - FUZ_CHECKTEST(((char*)dstBlock)[targetSize] != sentinel, "LZ4_compress_HC_destSize()") + FUZ_CHECKTEST(result != 4116, "LZ4_compress_HC_destSize() : " + "compression (%i->%i) must fill dstBuffer (%i) exactly", + srcSize, result, (int)targetSize); + FUZ_CHECKTEST(((char*)dstBlock)[targetSize] != sentinel, + "LZ4_compress_HC_destSize() overwrites dst buffer"); + FUZ_CHECKTEST(srcSize < 1045000, "LZ4_compress_HC_destSize() doesn't compress enough" + " (%i -> %i , expected > %i)", srcSize, result, 1045000); LZ4_resetStreamHC_fast(&sHC, 3); /* make sure the context is clean after the test */ free(block); @@ -1247,7 +1251,7 @@ static void FUZ_unitTests(int compressionLevel) DISPLAYLEVEL(3, " OK \n"); /* simple dictionary HC compression test */ - DISPLAYLEVEL(3, " HC dictionary compression test : "); + DISPLAYLEVEL(3, "HC dictionary compression test : "); { U64 const crc64 = XXH64(testInput + 64 KB, testCompressedSize, 0); LZ4_resetStreamHC_fast(&sHC, compressionLevel); LZ4_loadDictHC(&sHC, testInput, 64 KB); @@ -1316,6 +1320,7 @@ static void FUZ_unitTests(int compressionLevel) XXH64_reset(&crcNewState, 0); while (segStart + segSize < testInputSize) { + XXH64_hash_t crcOrig; XXH64_update(&crcOrigState, testInput + segStart, segSize); crcOrig = XXH64_digest(&crcOrigState); assert(segSize <= INT_MAX); @@ -1362,6 +1367,7 @@ static void FUZ_unitTests(int compressionLevel) while (iNext + messageSize < testCompressedSize) { int compressedSize; + XXH64_hash_t crcOrig; XXH64_update(&xxhOrig, testInput + iNext, messageSize); crcOrig = XXH64_digest(&xxhOrig); @@ -1376,7 +1382,7 @@ static void FUZ_unitTests(int compressionLevel) FUZ_CHECKTEST(result!=(int)messageSize, "ringBuffer : LZ4_decompress_safe_continue() test failed"); XXH64_update(&xxhNewSafe, testVerify + dNext, messageSize); - { U64 const crcNew = XXH64_digest(&xxhNewSafe); + { XXH64_hash_t const crcNew = XXH64_digest(&xxhNewSafe); FUZ_CHECKTEST(crcOrig!=crcNew, "LZ4_decompress_safe_continue() decompression corruption"); } assert(messageSize < INT_MAX); @@ -1384,7 +1390,7 @@ static void FUZ_unitTests(int compressionLevel) FUZ_CHECKTEST(result!=compressedSize, "ringBuffer : LZ4_decompress_fast_continue() test failed"); XXH64_update(&xxhNewFast, testVerify + dNext, messageSize); - { U64 const crcNew = XXH64_digest(&xxhNewFast); + { XXH64_hash_t const crcNew = XXH64_digest(&xxhNewFast); FUZ_CHECKTEST(crcOrig!=crcNew, "LZ4_decompress_fast_continue() decompression corruption"); } /* prepare next message */ @@ -1405,6 +1411,7 @@ static void FUZ_unitTests(int compressionLevel) */ { XXH64_state_t xxhOrig; XXH64_state_t xxhNewSafe, xxhNewFast; + XXH64_hash_t crcOrig; LZ4_streamDecode_t decodeStateSafe, decodeStateFast; const int maxMessageSizeLog = 12; const int maxMessageSize = 1 << maxMessageSizeLog; @@ -1501,8 +1508,85 @@ static void FUZ_unitTests(int compressionLevel) iNext = (FUZ_rand(&randState) & 65535); if (dNext + maxMessageSize > dBufferSize) dNext = 0; } + } /* Ring buffer test : Non synchronized decoder */ + } + + DISPLAYLEVEL(3, "LZ4_compress_HC_destSize : "); + /* encode congenerical sequence test for HC compressors */ + { LZ4_streamHC_t sHC; /* statically allocated */ + int const src_buf_size = 3 MB; + int const dst_buf_size = 6 KB; + int const payload = 0; + int const dst_step = 43; + int const dst_min_len = 33 + (FUZ_rand(&randState) % dst_step); + int const dst_max_len = 5000; + int slen, dlen; + char* sbuf1 = (char*)malloc(src_buf_size + 1); + char* sbuf2 = (char*)malloc(src_buf_size + 1); + char* dbuf1 = (char*)malloc(dst_buf_size + 1); + char* dbuf2 = (char*)malloc(dst_buf_size + 1); + + assert(dst_buf_size > dst_max_len); + if (!sbuf1 || !sbuf2 || !dbuf1 || !dbuf2) { + EXIT_MSG("not enough memory for FUZ_unitTests (destSize)"); + } + for (dlen = dst_min_len; dlen <= dst_max_len; dlen += dst_step) { + int src_len = (dlen - 10)*255 + 24; + if (src_len + 10 >= src_buf_size) break; /* END of check */ + for (slen = src_len - 3; slen <= src_len + 3; slen++) { + int srcsz1, srcsz2; + int dsz1, dsz2; + int res1, res2; + char const endchk = (char)0x88; + DISPLAYLEVEL(5, "slen = %i, ", slen); + + srcsz1 = slen; + memset(sbuf1, payload, slen); + memset(dbuf1, 0, dlen); + dbuf1[dlen] = endchk; + dsz1 = LZ4_compress_destSize(sbuf1, dbuf1, &srcsz1, dlen); + DISPLAYLEVEL(5, "LZ4_compress_destSize: %i bytes compressed into %i bytes, ", srcsz1, dsz1); + DISPLAYLEVEL(5, "last token : 0x%0X, ", dbuf1[dsz1 - 6]); + DISPLAYLEVEL(5, "last ML extra lenbyte : 0x%0X, \n", dbuf1[dsz1 - 7]); + FUZ_CHECKTEST(dbuf1[dlen] != endchk, "LZ4_compress_destSize() overwrite dst buffer !"); + FUZ_CHECKTEST(dsz1 <= 0, "LZ4_compress_destSize() compression failed"); + FUZ_CHECKTEST(dsz1 > dlen, "LZ4_compress_destSize() result larger than dst buffer !"); + FUZ_CHECKTEST(srcsz1 > slen, "LZ4_compress_destSize() read more than src buffer !"); + + res1 = LZ4_decompress_safe(dbuf1, sbuf1, dsz1, src_buf_size); + FUZ_CHECKTEST(res1 != srcsz1, "LZ4_compress_destSize() decompression failed!"); + + srcsz2 = slen; + memset(sbuf2, payload, slen); + memset(dbuf2, 0, dlen); + dbuf2[dlen] = endchk; + LZ4_resetStreamHC(&sHC, compressionLevel); + dsz2 = LZ4_compress_HC_destSize(&sHC, sbuf2, dbuf2, &srcsz2, dlen, compressionLevel); + DISPLAYLEVEL(5, "LZ4_compress_HC_destSize: %i bytes compressed into %i bytes, ", srcsz2, dsz2); + DISPLAYLEVEL(5, "last token : 0x%0X, ", dbuf2[dsz2 - 6]); + DISPLAYLEVEL(5, "last ML extra lenbyte : 0x%0X, \n", dbuf2[dsz2 - 7]); + FUZ_CHECKTEST(dbuf2[dlen] != endchk, "LZ4_compress_HC_destSize() overwrite dst buffer !"); + FUZ_CHECKTEST(dsz2 <= 0, "LZ4_compress_HC_destSize() compression failed"); + FUZ_CHECKTEST(dsz2 > dlen, "LZ4_compress_HC_destSize() result larger than dst buffer !"); + FUZ_CHECKTEST(srcsz2 > slen, "LZ4_compress_HC_destSize() read more than src buffer !"); + FUZ_CHECKTEST(dsz2 != dsz1, "LZ4_compress_HC_destSize() return incorrect result !"); + FUZ_CHECKTEST(srcsz2 != srcsz1, "LZ4_compress_HC_destSize() return incorrect src buffer size " + ": srcsz2(%i) != srcsz1(%i)", srcsz2, srcsz1); + FUZ_CHECKTEST(memcmp(dbuf2, dbuf1, (size_t)dsz2), "LZ4_compress_HC_destSize() return incorrect data into dst buffer !"); + + res2 = LZ4_decompress_safe(dbuf2, sbuf1, dsz2, src_buf_size); + FUZ_CHECKTEST(res2 != srcsz1, "LZ4_compress_HC_destSize() decompression failed!"); + + FUZ_CHECKTEST(memcmp(sbuf1, sbuf2, (size_t)res2), "LZ4_compress_HC_destSize() decompression corruption!"); + } } + free(sbuf1); + free(sbuf2); + free(dbuf1); + free(dbuf2); } + DISPLAYLEVEL(3, " OK \n"); + /* clean up */ free(testInput); -- 2.7.4