diff options
| -rw-r--r-- | lib/lz4.c | 3 | ||||
| -rw-r--r-- | lib/lz4hc.c | 90 | ||||
| -rw-r--r-- | tests/fuzzer.c | 102 |
3 files changed, 161 insertions, 34 deletions
@@ -247,6 +247,7 @@ static const int LZ4_minLength = (MFLIMIT+1); /*-************************************ * Types **************************************/ +#include <limits.h> #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) # include <stdint.h> 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 <limits.h> # 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); |