diff options
author | Yann Collet <yann.collet.73@gmail.com> | 2014-09-23 09:00:55 (GMT) |
---|---|---|
committer | Yann Collet <yann.collet.73@gmail.com> | 2014-09-23 09:00:55 (GMT) |
commit | dc245be066cddb816a913289bfea2ab899b065ad (patch) | |
tree | ed96414c79da5f3f6985dc03b3bbc2c0a560e0da /programs | |
parent | 6e9183ba44a6863f99023c82e8d9752a8a0a92a6 (diff) | |
parent | 8c1ae998379bce4a0e719aaac43a777713ab5c00 (diff) | |
download | lz4-dc245be066cddb816a913289bfea2ab899b065ad.zip lz4-dc245be066cddb816a913289bfea2ab899b065ad.tar.gz lz4-dc245be066cddb816a913289bfea2ab899b065ad.tar.bz2 |
Merge pull request #27 from Cyan4973/dev
lz4frame
Diffstat (limited to 'programs')
-rw-r--r-- | programs/Makefile | 32 | ||||
-rw-r--r-- | programs/frametest.c | 668 | ||||
-rw-r--r-- | programs/fullbench.c | 124 | ||||
-rw-r--r-- | programs/fuzzer.c | 72 | ||||
-rw-r--r-- | programs/lz4cli.c | 8 | ||||
-rw-r--r-- | programs/lz4io.c | 2 | ||||
-rw-r--r-- | programs/xxhash.c | 806 | ||||
-rw-r--r-- | programs/xxhash.h | 168 |
8 files changed, 802 insertions, 1078 deletions
diff --git a/programs/Makefile b/programs/Makefile index a04c323..c653ec6 100644 --- a/programs/Makefile +++ b/programs/Makefile @@ -30,7 +30,7 @@ # fullbench32: Same as fullbench, but forced to compile in 32-bits mode # ########################################################################## -RELEASE=r122 +RELEASE=r123 DESTDIR?= PREFIX ?= /usr @@ -68,29 +68,32 @@ endif default: lz4 lz4c -all: lz4 lz4c lz4c32 fullbench fullbench32 fuzzer fuzzer32 datagen +all: lz4 lz4c lz4c32 fullbench fullbench32 fuzzer fuzzer32 frametest datagen -lz4: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c +lz4: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c bench.c lz4io.c lz4cli.c $(CC) $(FLAGS) -DDISABLE_LZ4C_LEGACY_OPTIONS $^ -o $@$(EXT) -lz4c : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c +lz4c : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c bench.c lz4io.c lz4cli.c $(CC) $(FLAGS) $^ -o $@$(EXT) -lz4c32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c bench.c xxhash.c lz4io.c lz4cli.c +lz4c32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c bench.c lz4io.c lz4cli.c $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) -fullbench : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c +fullbench : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/lz4frame.c $(LZ4DIR)/xxhash.c fullbench.c $(CC) $(FLAGS) $^ -o $@$(EXT) -fullbench32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fullbench.c +fullbench32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/lz4frame.c $(LZ4DIR)/xxhash.c fullbench.c $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) -fuzzer : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fuzzer.c +fuzzer : $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c fuzzer.c $(CC) $(FLAGS) $^ -o $@$(EXT) -fuzzer32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c xxhash.c fuzzer.c +fuzzer32: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c fuzzer.c $(CC) -m32 $(FLAGS) $^ -o $@$(EXT) +frametest: $(LZ4DIR)/lz4frame.c $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/xxhash.c frametest.c + $(CC) $(FLAGS) $^ -o $@$(EXT) + datagen : datagen.c $(CC) $(FLAGS) $^ -o $@$(EXT) @@ -99,7 +102,8 @@ clean: @rm -f core *.o \ lz4$(EXT) lz4c$(EXT) lz4c32$(EXT) \ fullbench$(EXT) fullbench32$(EXT) \ - fuzzer$(EXT) fuzzer32$(EXT) datagen$(EXT) + fuzzer$(EXT) fuzzer32$(EXT) \ + frametest$(EXT) datagen$(EXT) @echo Cleaning completed @@ -128,7 +132,7 @@ uninstall: [ -f $(DESTDIR)$(MANDIR)/lz4cat.1 ] && rm -f $(DESTDIR)$(MANDIR)/lz4cat.1 @echo lz4 successfully uninstalled -test-native: test-lz4 test-lz4c test-fullbench test-fuzzer test-mem +test-native: test-lz4 test-lz4c test-frame test-fullbench test-fuzzer test-mem test-force32: test-lz4c32 test-fullbench32 test-fuzzer32 test-mem32 @@ -165,7 +169,10 @@ test-fuzzer: fuzzer test-fuzzer32: fuzzer32 ./fuzzer32 --no-prompt -test-mem: lz4 datagen +test-frame: frametest + ./frametest + +test-mem: lz4 datagen frametest ./datagen -g16KB > tmp valgrind ./lz4 -9 -BD -f tmp /dev/null ./datagen -g16MB > tmp @@ -173,6 +180,7 @@ test-mem: lz4 datagen ./datagen -g256MB > tmp valgrind ./lz4 -B4D -f tmp /dev/null rm tmp + valgrind ./frametest -i100 test-mem32: lz4c32 datagen # unfortunately, valgrind doesn't seem to work with non-native binary. If someone knows how to do a valgrind-test on a 32-bits exe with a 64-bits system... diff --git a/programs/frametest.c b/programs/frametest.c new file mode 100644 index 0000000..3d19ef4 --- /dev/null +++ b/programs/frametest.c @@ -0,0 +1,668 @@ +/* + frameTest - test tool for lz4frame + Copyright (C) Yann Collet 2014 + GPL v2 License + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + + You can contact the author at : + - LZ4 source repository : http://code.google.com/p/lz4/ + - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c +*/ + +/************************************** + Compiler specific +**************************************/ +#define _CRT_SECURE_NO_WARNINGS // fgets +#ifdef _MSC_VER /* Visual Studio */ +# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ +# pragma warning(disable : 4146) /* disable: C4146: minus unsigned expression */ +#endif +#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) +#ifdef __GNUC__ +# pragma GCC diagnostic ignored "-Wmissing-braces" /* GCC bug 53119 : doesn't accept { 0 } as initializer (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53119) */ +# pragma GCC diagnostic ignored "-Wmissing-field-initializers" /* GCC bug 53119 : doesn't accept { 0 } as initializer (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53119) */ +#endif + + +/************************************** + Includes +**************************************/ +#include <stdlib.h> +#include <stdio.h> // fgets, sscanf +#include <sys/timeb.h> // timeb +#include <string.h> // strcmp +#include "lz4frame.h" +#include "xxhash.h" // XXH64 + + +/************************************** + Basic Types +**************************************/ +#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ +# include <stdint.h> +typedef uint8_t BYTE; +typedef uint16_t U16; +typedef uint32_t U32; +typedef int32_t S32; +typedef uint64_t U64; +#else +typedef unsigned char BYTE; +typedef unsigned short U16; +typedef unsigned int U32; +typedef signed int S32; +typedef unsigned long long U64; +#endif + + +/************************************** + Constants +**************************************/ +#ifndef LZ4_VERSION +# define LZ4_VERSION "" +#endif + +#define KB *(1U<<10) +#define MB *(1U<<20) +#define GB *(1U<<30) + +static const U32 nbTestsDefault = 128 KB; +#define COMPRESSIBLE_NOISE_LENGTH (2 MB) +#define FUZ_COMPRESSIBILITY_DEFAULT 50 +static const U32 prime1 = 2654435761U; +static const U32 prime2 = 2246822519U; + + + +/************************************** + Macros +**************************************/ +#define DISPLAY(...) fprintf(stderr, __VA_ARGS__) +#define DISPLAYLEVEL(l, ...) if (displayLevel>=l) { DISPLAY(__VA_ARGS__); } +#define DISPLAYUPDATE(l, ...) if (displayLevel>=l) { \ + if ((FUZ_GetMilliSpan(g_time) > refreshRate) || (displayLevel>=4)) \ + { g_time = FUZ_GetMilliStart(); DISPLAY(__VA_ARGS__); \ + if (displayLevel>=4) fflush(stdout); } } +static const U32 refreshRate = 150; +static U32 g_time = 0; + + +/***************************************** + Local Parameters +*****************************************/ +static U32 no_prompt = 0; +static char* programName; +static U32 displayLevel = 2; +static U32 pause = 0; + + +/********************************************************* + Fuzzer functions +*********************************************************/ +static U32 FUZ_GetMilliStart(void) +{ + struct timeb tb; + U32 nCount; + ftime( &tb ); + nCount = (U32) (((tb.time & 0xFFFFF) * 1000) + tb.millitm); + return nCount; +} + + +static U32 FUZ_GetMilliSpan(U32 nTimeStart) +{ + U32 nCurrent = FUZ_GetMilliStart(); + U32 nSpan = nCurrent - nTimeStart; + if (nTimeStart > nCurrent) + nSpan += 0x100000 * 1000; + return nSpan; +} + + + +# define FUZ_rotl32(x,r) ((x << r) | (x >> (32 - r))) +unsigned int FUZ_rand(unsigned int* src) +{ + U32 rand32 = *src; + rand32 *= prime1; + rand32 += prime2; + rand32 = FUZ_rotl32(rand32, 13); + *src = rand32; + return rand32 >> 5; +} + + +#define FUZ_RAND15BITS (FUZ_rand(seed) & 0x7FFF) +#define FUZ_RANDLENGTH ( (FUZ_rand(seed) & 3) ? (FUZ_rand(seed) % 15) : (FUZ_rand(seed) % 510) + 15) +static void FUZ_fillCompressibleNoiseBuffer(void* buffer, unsigned bufferSize, double proba, U32* seed) +{ + BYTE* BBuffer = (BYTE*)buffer; + unsigned pos = 0; + U32 P32 = (U32)(32768 * proba); + + // First Byte + BBuffer[pos++] = (BYTE)(FUZ_rand(seed)); + + while (pos < bufferSize) + { + // Select : Literal (noise) or copy (within 64K) + if (FUZ_RAND15BITS < P32) + { + // Copy (within 64K) + unsigned match, end; + unsigned length = FUZ_RANDLENGTH + 4; + unsigned offset = FUZ_RAND15BITS + 1; + if (offset > pos) offset = pos; + if (pos + length > bufferSize) length = bufferSize - pos; + match = pos - offset; + end = pos + length; + while (pos < end) BBuffer[pos++] = BBuffer[match++]; + } + else + { + // Literal (noise) + unsigned end; + unsigned length = FUZ_RANDLENGTH; + if (pos + length > bufferSize) length = bufferSize - pos; + end = pos + length; + while (pos < end) BBuffer[pos++] = (BYTE)(FUZ_rand(seed) >> 5); + } + } +} + + +static unsigned FUZ_highbit(U32 v32) +{ + unsigned nbBits = 0; + if (v32==0) return 0; + while (v32) + { + v32 >>= 1; + nbBits ++; + } + return nbBits; +} + + +int basicTests(U32 seed, double compressibility) +{ + int testResult = 0; + void* CNBuffer; + void* compressedBuffer; + void* decodedBuffer; + U32 randState = seed; + size_t cSize, testSize; + LZ4F_preferences_t prefs = { 0 }; + LZ4F_decompressionContext_t dCtx; + U64 crcOrig; + + // Create compressible test buffer + CNBuffer = malloc(COMPRESSIBLE_NOISE_LENGTH); + compressedBuffer = malloc(LZ4F_compressFrameBound(COMPRESSIBLE_NOISE_LENGTH, NULL)); + decodedBuffer = malloc(COMPRESSIBLE_NOISE_LENGTH); + FUZ_fillCompressibleNoiseBuffer(CNBuffer, COMPRESSIBLE_NOISE_LENGTH, compressibility, &randState); + crcOrig = XXH64(CNBuffer, COMPRESSIBLE_NOISE_LENGTH, 1); + + // Trivial tests : one-step frame + testSize = COMPRESSIBLE_NOISE_LENGTH; + DISPLAYLEVEL(3, "Using NULL preferences : \n"); + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, NULL), CNBuffer, testSize, NULL); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "Decompression test : \n"); + { + size_t decodedBufferSize = COMPRESSIBLE_NOISE_LENGTH; + size_t compressedBufferSize = cSize; + BYTE* op = (BYTE*)decodedBuffer; + BYTE* const oend = (BYTE*)decodedBuffer + COMPRESSIBLE_NOISE_LENGTH; + BYTE* ip = (BYTE*)compressedBuffer; + BYTE* const iend = (BYTE*)compressedBuffer + cSize; + U64 crcDest; + + LZ4F_errorCode_t errorCode = LZ4F_createDecompressionContext(&dCtx, LZ4F_VERSION); + if (LZ4F_isError(errorCode)) goto _output_error; + + DISPLAYLEVEL(3, "Single Block : \n"); + errorCode = LZ4F_decompress(dCtx, decodedBuffer, &decodedBufferSize, compressedBuffer, &compressedBufferSize, NULL); + crcDest = XXH64(decodedBuffer, COMPRESSIBLE_NOISE_LENGTH, 1); + if (crcDest != crcOrig) goto _output_error; + DISPLAYLEVEL(3, "Regenerated %i bytes \n", (int)decodedBufferSize); + + DISPLAYLEVEL(3, "Byte after byte : \n"); + while (ip < iend) + { + size_t oSize = oend-op; + size_t iSize = 1; + //DISPLAY("%7i \n", (int)(ip-(BYTE*)compressedBuffer)); + errorCode = LZ4F_decompress(dCtx, op, &oSize, ip, &iSize, NULL); + if (LZ4F_isError(errorCode)) goto _output_error; + op += oSize; + ip += iSize; + } + crcDest = XXH64(decodedBuffer, COMPRESSIBLE_NOISE_LENGTH, 1); + if (crcDest != crcOrig) goto _output_error; + DISPLAYLEVEL(3, "Regenerated %i bytes \n", (int)decodedBufferSize); + + errorCode = LZ4F_freeDecompressionContext(dCtx); + if (LZ4F_isError(errorCode)) goto _output_error; + } + + DISPLAYLEVEL(3, "Using 64 KB block : \n"); + prefs.frameInfo.blockSizeID = max64KB; + prefs.frameInfo.contentChecksumFlag = contentChecksumEnabled; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "without checksum : \n"); + prefs.frameInfo.contentChecksumFlag = noContentChecksum; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "Using 256 KB block : \n"); + prefs.frameInfo.blockSizeID = max256KB; + prefs.frameInfo.contentChecksumFlag = contentChecksumEnabled; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "Decompression test : \n"); + { + size_t decodedBufferSize = COMPRESSIBLE_NOISE_LENGTH; + unsigned maxBits = FUZ_highbit((U32)decodedBufferSize); + BYTE* op = (BYTE*)decodedBuffer; + BYTE* const oend = (BYTE*)decodedBuffer + COMPRESSIBLE_NOISE_LENGTH; + BYTE* ip = (BYTE*)compressedBuffer; + BYTE* const iend = (BYTE*)compressedBuffer + cSize; + U64 crcDest; + + LZ4F_errorCode_t errorCode = LZ4F_createDecompressionContext(&dCtx, LZ4F_VERSION); + if (LZ4F_isError(errorCode)) goto _output_error; + + DISPLAYLEVEL(3, "random segment sizes : \n"); + while (ip < iend) + { + unsigned nbBits = FUZ_rand(&randState) % maxBits; + size_t iSize = (FUZ_rand(&randState) & ((1<<nbBits)-1)) + 1; + size_t oSize = oend-op; + if (iSize > (size_t)(iend-ip)) iSize = iend-ip; + //DISPLAY("%7i : + %6i\n", (int)(ip-(BYTE*)compressedBuffer), (int)iSize); + errorCode = LZ4F_decompress(dCtx, op, &oSize, ip, &iSize, NULL); + if (LZ4F_isError(errorCode)) goto _output_error; + op += oSize; + ip += iSize; + } + crcDest = XXH64(decodedBuffer, COMPRESSIBLE_NOISE_LENGTH, 1); + if (crcDest != crcOrig) goto _output_error; + DISPLAYLEVEL(3, "Regenerated %i bytes \n", (int)decodedBufferSize); + + errorCode = LZ4F_freeDecompressionContext(dCtx); + if (LZ4F_isError(errorCode)) goto _output_error; + } + + DISPLAYLEVEL(3, "without checksum : \n"); + prefs.frameInfo.contentChecksumFlag = noContentChecksum; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "Using 1 MB block : \n"); + prefs.frameInfo.blockSizeID = max1MB; + prefs.frameInfo.contentChecksumFlag = contentChecksumEnabled; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "without checksum : \n"); + prefs.frameInfo.contentChecksumFlag = noContentChecksum; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "Using 4 MB block : \n"); + prefs.frameInfo.blockSizeID = max4MB; + prefs.frameInfo.contentChecksumFlag = contentChecksumEnabled; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAYLEVEL(3, "without checksum : \n"); + prefs.frameInfo.contentChecksumFlag = noContentChecksum; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(testSize, &prefs), CNBuffer, testSize, &prefs); + if (LZ4F_isError(cSize)) goto _output_error; + DISPLAYLEVEL(3, "Compressed %i bytes into a %i bytes frame \n", (int)testSize, (int)cSize); + + DISPLAY("Basic tests completed \n"); +_end: + free(CNBuffer); + free(compressedBuffer); + free(decodedBuffer); + return testResult; + +_output_error: + testResult = 1; + DISPLAY("Error detected ! \n"); + goto _end; +} + + +static void locateBuffDiff(const void* buff1, const void* buff2, size_t size, unsigned nonContiguous) +{ + int p=0; + BYTE* b1=(BYTE*)buff1; + BYTE* b2=(BYTE*)buff2; + if (nonContiguous) + { + DISPLAY("Non-contiguous output test (%i bytes)\n", (int)size); + return; + } + while (b1[p]==b2[p]) p++; + DISPLAY("Error at pos %i/%i : %02X != %02X \n", p, (int)size, b1[p], b2[p]); +} + + +static const U32 srcDataLength = 9 MB; /* needs to be > 2x4MB to test large blocks */ + +int fuzzerTests(U32 seed, unsigned nbTests, unsigned startTest, double compressibility) +{ + unsigned testResult = 0; + unsigned testNb = 0; + void* srcBuffer = NULL; + void* compressedBuffer = NULL; + void* decodedBuffer = NULL; + U32 coreRand = seed; + LZ4F_decompressionContext_t dCtx = NULL; + LZ4F_compressionContext_t cCtx = NULL; + size_t result; + XXH64_stateSpace_t xxh64; +# define CHECK(cond, ...) if (cond) { DISPLAY("Error => "); DISPLAY(__VA_ARGS__); \ + DISPLAY(" (seed %u, test nb %u) \n", seed, testNb); goto _output_error; } + + // Create buffers + result = LZ4F_createDecompressionContext(&dCtx, LZ4F_VERSION); + CHECK(LZ4F_isError(result), "Allocation failed (error %i)", (int)result); + result = LZ4F_createCompressionContext(&cCtx, LZ4F_VERSION); + CHECK(LZ4F_isError(result), "Allocation failed (error %i)", (int)result); + srcBuffer = malloc(srcDataLength); + CHECK(srcBuffer==NULL, "srcBuffer Allocation failed"); + compressedBuffer = malloc(LZ4F_compressFrameBound(srcDataLength, NULL)); + CHECK(compressedBuffer==NULL, "compressedBuffer Allocation failed"); + decodedBuffer = malloc(srcDataLength); + CHECK(decodedBuffer==NULL, "decodedBuffer Allocation failed"); + FUZ_fillCompressibleNoiseBuffer(srcBuffer, srcDataLength, compressibility, &coreRand); + + // jump to requested testNb + for (testNb =0; testNb < startTest; testNb++) (void)FUZ_rand(&coreRand); // sync randomizer + + // main fuzzer loop + for ( ; testNb < nbTests; testNb++) + { + U32 randState = coreRand ^ prime1; + unsigned BSId = 4 + (FUZ_rand(&randState) & 3); + unsigned BMId = FUZ_rand(&randState) & 1; + unsigned CCflag = FUZ_rand(&randState) & 1; + unsigned autoflush = (FUZ_rand(&randState) & 7) == 2; + LZ4F_preferences_t prefs = { 0 }; + LZ4F_compressOptions_t cOptions = { 0 }; + LZ4F_decompressOptions_t dOptions = { 0 }; + unsigned nbBits = (FUZ_rand(&randState) % (FUZ_highbit(srcDataLength-1) - 1)) + 1; + size_t srcSize = (FUZ_rand(&randState) & ((1<<nbBits)-1)) + 1; + size_t srcStart = FUZ_rand(&randState) % (srcDataLength - srcSize); + size_t cSize; + U64 crcOrig, crcDecoded; + + (void)FUZ_rand(&coreRand); // update rand seed + prefs.frameInfo.blockMode = BMId; + prefs.frameInfo.blockSizeID = BSId; + prefs.frameInfo.contentChecksumFlag = CCflag; + prefs.autoFlush = autoflush; + + DISPLAYUPDATE(2, "\r%5u ", testNb); + crcOrig = XXH64((BYTE*)srcBuffer+srcStart, (U32)srcSize, 1); + + if ((FUZ_rand(&randState)&0xF) == 2) + { + LZ4F_preferences_t* framePrefs = &prefs; + if ((FUZ_rand(&randState)&7) == 1) framePrefs = NULL; + cSize = LZ4F_compressFrame(compressedBuffer, LZ4F_compressFrameBound(srcSize, framePrefs), (char*)srcBuffer + srcStart, srcSize, framePrefs); + CHECK(LZ4F_isError(cSize), "LZ4F_compressFrame failed : error %i (%s)", (int)cSize, LZ4F_getErrorName(cSize)); + } + else + { + const BYTE* ip = (const BYTE*)srcBuffer + srcStart; + const BYTE* const iend = ip + srcSize; + BYTE* op = compressedBuffer; + BYTE* const oend = op + LZ4F_compressFrameBound(srcDataLength, NULL); + unsigned maxBits = FUZ_highbit((U32)srcSize); + result = LZ4F_compressBegin(cCtx, op, oend-op, &prefs); + CHECK(LZ4F_isError(result), "Compression header failed (error %i)", (int)result); + op += result; + while (ip < iend) + { + unsigned nbBitsSeg = FUZ_rand(&randState) % maxBits; + size_t iSize = (FUZ_rand(&randState) & ((1<<nbBitsSeg)-1)) + 1; + size_t oSize = oend-op; + unsigned forceFlush = ((FUZ_rand(&randState) & 3) == 1); + if (iSize > (size_t)(iend-ip)) iSize = iend-ip; + cOptions.stableSrc = ((FUZ_rand(&randState) & 3) == 1); + + result = LZ4F_compressUpdate(cCtx, op, oSize, ip, iSize, &cOptions); + CHECK(LZ4F_isError(result), "Compression failed (error %i)", (int)result); + op += result; + ip += iSize; + + if (forceFlush) + { + result = LZ4F_flush(cCtx, op, oend-op, &cOptions); + CHECK(LZ4F_isError(result), "Compression failed (error %i)", (int)result); + op += result; + } + } + result = LZ4F_compressEnd(cCtx, op, oend-op, &cOptions); + CHECK(LZ4F_isError(result), "Compression completion failed (error %i)", (int)result); + op += result; + cSize = op-(BYTE*)compressedBuffer; + } + + { + const BYTE* ip = compressedBuffer; + const BYTE* const iend = ip + cSize; + BYTE* op = decodedBuffer; + BYTE* const oend = op + srcDataLength; + unsigned maxBits = FUZ_highbit((U32)cSize); + unsigned nonContiguousDst = (FUZ_rand(&randState) & 3) == 1; + nonContiguousDst += FUZ_rand(&randState) & nonContiguousDst; /* 0=>0; 1=>1,2 */ + XXH64_resetState(&xxh64, 1); + while (ip < iend) + { + unsigned nbBitsI = (FUZ_rand(&randState) % (maxBits-1)) + 1; + unsigned nbBitsO = (FUZ_rand(&randState) % (maxBits)) + 1; + size_t iSize = (FUZ_rand(&randState) & ((1<<nbBitsI)-1)) + 1; + size_t oSize = (FUZ_rand(&randState) & ((1<<nbBitsO)-1)) + 2; + if (iSize > (size_t)(iend-ip)) iSize = iend-ip; + if (oSize > (size_t)(oend-op)) oSize = oend-op; + dOptions.stableDst = FUZ_rand(&randState) & 1; + if (nonContiguousDst==2) dOptions.stableDst = 0; + //if (ip == compressedBuffer+62073) DISPLAY("oSize : %i : pos %i \n", (int)oSize, (int)(op-(BYTE*)decodedBuffer)); + result = LZ4F_decompress(dCtx, op, &oSize, ip, &iSize, &dOptions); + //if (op+oSize >= (BYTE*)decodedBuffer+94727) DISPLAY("iSize : %i : pos %i \n", (int)iSize, (int)(ip-(BYTE*)compressedBuffer)); + //if ((int)result<0) DISPLAY("iSize : %i : pos %i \n", (int)iSize, (int)(ip-(BYTE*)compressedBuffer)); + if (result == (size_t)-ERROR_checksum_invalid) locateBuffDiff((BYTE*)srcBuffer+srcStart, decodedBuffer, srcSize, nonContiguousDst); + CHECK(LZ4F_isError(result), "Decompression failed (error %i:%s)", (int)result, LZ4F_getErrorName((LZ4F_errorCode_t)result)); + XXH64_update(&xxh64, op, (U32)oSize); + op += oSize; + ip += iSize; + op += nonContiguousDst; + if (nonContiguousDst==2) op = decodedBuffer; // overwritten destination + } + CHECK(result != 0, "Frame decompression failed (error %i)", (int)result); + crcDecoded = XXH64_intermediateDigest(&xxh64); + if (crcDecoded != crcOrig) locateBuffDiff((BYTE*)srcBuffer+srcStart, decodedBuffer, srcSize, nonContiguousDst); + CHECK(crcDecoded != crcOrig, "Decompression corruption"); + } + } + + DISPLAYLEVEL(2, "\rAll tests completed \n"); + +_end: + LZ4F_freeDecompressionContext(dCtx); + LZ4F_freeCompressionContext(cCtx); + free(srcBuffer); + free(compressedBuffer); + free(decodedBuffer); + + if (pause) + { + DISPLAY("press enter to finish \n"); + getchar(); + } + return testResult; + +_output_error: + testResult = 1; + goto _end; +} + + +int FUZ_usage(void) +{ + DISPLAY( "Usage :\n"); + DISPLAY( " %s [args]\n", programName); + DISPLAY( "\n"); + DISPLAY( "Arguments :\n"); + DISPLAY( " -i# : Nb of tests (default:%u) \n", nbTestsDefault); + DISPLAY( " -s# : Select seed (default:prompt user)\n"); + DISPLAY( " -t# : Select starting test number (default:0)\n"); + DISPLAY( " -p# : Select compressibility in %% (default:%i%%)\n", FUZ_COMPRESSIBILITY_DEFAULT); + DISPLAY( " -v : verbose\n"); + DISPLAY( " -h : display help and exit\n"); + return 0; +} + + +int main(int argc, char** argv) +{ + U32 seed=0; + int seedset=0; + int argNb; + int nbTests = nbTestsDefault; + int testNb = 0; + int proba = FUZ_COMPRESSIBILITY_DEFAULT; + int result=0; + + // Check command line + programName = argv[0]; + for(argNb=1; argNb<argc; argNb++) + { + char* argument = argv[argNb]; + + if(!argument) continue; // Protection if argument empty + + // Decode command (note : aggregated commands are allowed) + if (argument[0]=='-') + { + if (!strcmp(argument, "--no-prompt")) + { + no_prompt=1; + seedset=1; + displayLevel=1; + continue; + } + argument++; + + while (*argument!=0) + { + switch(*argument) + { + case 'h': + return FUZ_usage(); + case 'v': + argument++; + displayLevel=4; + break; + case 'q': + argument++; + displayLevel--; + break; + case 'i': + argument++; + nbTests=0; + while ((*argument>='0') && (*argument<='9')) + { + nbTests *= 10; + nbTests += *argument - '0'; + argument++; + } + break; + case 's': + argument++; + seed=0; + seedset=1; + while ((*argument>='0') && (*argument<='9')) + { + seed *= 10; + seed += *argument - '0'; + argument++; + } + break; + case 't': + argument++; + testNb=0; + while ((*argument>='0') && (*argument<='9')) + { + testNb *= 10; + testNb += *argument - '0'; + argument++; + } + break; + case 'p': /* compressibility % */ + argument++; + proba=0; + while ((*argument>='0') && (*argument<='9')) + { + proba *= 10; + proba += *argument - '0'; + argument++; + } + if (proba<0) proba=0; + if (proba>100) proba=100; + break; + case 'P': /* pause at the end */ + argument++; + pause = 1; + break; + default: + ; + return FUZ_usage(); + } + } + } + } + + // Get Seed + printf("Starting lz4frame tester (%i-bits, %s)\n", (int)(sizeof(size_t)*8), LZ4_VERSION); + + if (!seedset) seed = FUZ_GetMilliStart() % 10000; + printf("Seed = %u\n", seed); + if (proba!=FUZ_COMPRESSIBILITY_DEFAULT) printf("Compressibility : %i%%\n", proba); + + if (nbTests<=0) nbTests=1; + + //if (testNb==0) result = basicTests(seed, ((double)proba) / 100); + if (result) return 1; + return fuzzerTests(seed, nbTests, testNb, ((double)proba) / 100); +} diff --git a/programs/fullbench.c b/programs/fullbench.c index 3d39458..f34c68c 100644 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -60,10 +60,8 @@ #endif #include "lz4.h" -#define COMPRESSOR0 LZ4_compress #include "lz4hc.h" -#define COMPRESSOR1 LZ4_compressHC -#define DEFAULTCOMPRESSOR COMPRESSOR0 +#include "lz4frame.h" #include "xxhash.h" @@ -270,7 +268,7 @@ static int local_LZ4_compress_limitedOutput_withState(const char* in, char* out, return LZ4_compress_limitedOutput_withState(stateLZ4, in, out, inSize, LZ4_compressBound(inSize)); } -static void* ctx; +static LZ4_stream_t* ctx; static int local_LZ4_compress_continue(const char* in, char* out, int inSize) { return LZ4_compress_continue(ctx, in, out, inSize); @@ -323,6 +321,11 @@ static int local_LZ4_compressHC_limitedOutput_continue(const char* in, char* out return LZ4_compressHC_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize)); } +static int local_LZ4F_compressFrame(const char* in, char* out, int inSize) +{ + return (int)LZ4F_compressFrame(out, 2*inSize + 16, in, inSize, NULL); +} + static int local_LZ4_decompress_fast(const char* in, char* out, int inSize, int outSize) { (void)inSize; @@ -340,14 +343,23 @@ static int local_LZ4_decompress_fast_withPrefix64k(const char* in, char* out, in static int local_LZ4_decompress_fast_usingDict(const char* in, char* out, int inSize, int outSize) { (void)inSize; - LZ4_decompress_fast_usingDict(in, out, outSize, in - 65536, 65536); + LZ4_decompress_fast_usingDict(in, out, outSize, out - 65536, 65536); return outSize; } static int local_LZ4_decompress_safe_usingDict(const char* in, char* out, int inSize, int outSize) { (void)inSize; - LZ4_decompress_safe_usingDict(in, out, inSize, outSize, in - 65536, 65536); + LZ4_decompress_safe_usingDict(in, out, inSize, outSize, out - 65536, 65536); + return outSize; +} + +extern int LZ4_decompress_safe_forceExtDict(const char* in, char* out, int inSize, int outSize, const char* dict, int dictSize); + +static int local_LZ4_decompress_safe_forceExtDict(const char* in, char* out, int inSize, int outSize) +{ + (void)inSize; + LZ4_decompress_safe_forceExtDict(in, out, inSize, outSize, out - 65536, 65536); return outSize; } @@ -356,21 +368,37 @@ static int local_LZ4_decompress_safe_partial(const char* in, char* out, int inSi return LZ4_decompress_safe_partial(in, out, inSize, outSize - 5, outSize); } +static LZ4F_decompressionContext_t g_dCtx; + +static int local_LZ4F_decompress(const char* in, char* out, int inSize, int outSize) +{ + size_t srcSize = inSize; + size_t dstSize = outSize; + size_t result; + result = LZ4F_decompress(g_dCtx, out, &dstSize, in, &srcSize, NULL); + if (result!=0) { DISPLAY("Error decompressing frame : unfinished frame\n"); exit(8); } + if (srcSize != (size_t)inSize) { DISPLAY("Error decompressing frame : read size incorrect\n"); exit(9); } + return (int)dstSize; +} + + int fullSpeedBench(char** fileNamesTable, int nbFiles) { int fileIdx=0; char* orig_buff; -# define NB_COMPRESSION_ALGORITHMS 13 -# define MINCOMPRESSIONCHAR '0' +# define NB_COMPRESSION_ALGORITHMS 14 double totalCTime[NB_COMPRESSION_ALGORITHMS+1] = {0}; double totalCSize[NB_COMPRESSION_ALGORITHMS+1] = {0}; -# define NB_DECOMPRESSION_ALGORITHMS 7 -# define MINDECOMPRESSIONCHAR '0' -# define MAXDECOMPRESSIONCHAR (MINDECOMPRESSIONCHAR + NB_DECOMPRESSION_ALGORITHMS) - static char* decompressionNames[] = { "LZ4_decompress_fast", "LZ4_decompress_fast_withPrefix64k", "LZ4_decompress_fast_usingDict", - "LZ4_decompress_safe", "LZ4_decompress_safe_withPrefix64k", "LZ4_decompress_safe_usingDict", "LZ4_decompress_safe_partial" }; +# define NB_DECOMPRESSION_ALGORITHMS 9 double totalDTime[NB_DECOMPRESSION_ALGORITHMS+1] = {0}; + size_t errorCode; + errorCode = LZ4F_createDecompressionContext(&g_dCtx, LZ4F_VERSION); + if (LZ4F_isError(errorCode)) + { + DISPLAY("dctx allocation issue \n"); + return 10; + } // Loop for each file while (fileIdx<nbFiles) @@ -428,22 +456,6 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) return 12; } - // Init chunks data - { - int i; - size_t remaining = benchedSize; - char* in = orig_buff; - char* out = compressed_buff; - for (i=0; i<nbChunks; i++) - { - chunkP[i].id = i; - chunkP[i].origBuffer = in; in += chunkSize; - if ((int)remaining > chunkSize) { chunkP[i].origSize = chunkSize; remaining -= chunkSize; } else { chunkP[i].origSize = (int)remaining; remaining = 0; } - chunkP[i].compressedBuffer = out; out += maxCompressedChunkSize; - chunkP[i].compressedSize = 0; - } - } - // Fill input buffer DISPLAY("Loading %s... \r", inFileName); readSize = fread(orig_buff, 1, benchedSize, inFile); @@ -471,10 +483,27 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) DISPLAY("\r%79s\r", ""); DISPLAY(" %s : \n", inFileName); + // Init chunks data + { + int i; + size_t remaining = benchedSize; + char* in = orig_buff; + char* out = compressed_buff; + nbChunks = (int) ((int)benchedSize / chunkSize) + 1; + for (i=0; i<nbChunks; i++) + { + chunkP[i].id = i; + chunkP[i].origBuffer = in; in += chunkSize; + if ((int)remaining > chunkSize) { chunkP[i].origSize = chunkSize; remaining -= chunkSize; } else { chunkP[i].origSize = (int)remaining; remaining = 0; } + chunkP[i].compressedBuffer = out; out += maxCompressedChunkSize; + chunkP[i].compressedSize = 0; + } + } + // Compression Algorithms for (cAlgNb=1; (cAlgNb <= NB_COMPRESSION_ALGORITHMS) && (compressionTest); cAlgNb++) { - char* compressorName; + const char* compressorName; int (*compressionFunction)(const char*, char*, int); void* (*initFunction)(const char*) = NULL; double bestTime = 100000000.; @@ -496,6 +525,9 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) case 11: compressionFunction = local_LZ4_compressHC_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_continue"; break; case 12: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; compressorName = "LZ4_compressHC_limitedOutput_continue"; break; case 13: compressionFunction = local_LZ4_compress_forceDict; initFunction = local_LZ4_resetDictT; compressorName = "LZ4_compress_forceDict"; break; + case 14: compressionFunction = local_LZ4F_compressFrame; compressorName = "LZ4F_compressFrame"; + chunkP[0].origSize = (int)benchedSize; nbChunks=1; + break; default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; } @@ -546,29 +578,39 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) chunkP[chunkNb].compressedSize = LZ4_compress(chunkP[chunkNb].origBuffer, chunkP[chunkNb].compressedBuffer, chunkP[chunkNb].origSize); if (chunkP[chunkNb].compressedSize==0) DISPLAY("ERROR ! %s() = 0 !! \n", "LZ4_compress"), exit(1); } - { size_t i; for (i=0; i<benchedSize; i++) orig_buff[i]=0; } // zeroing source area, for CRC checking // Decompression Algorithms - for (dAlgNb=0; (dAlgNb < NB_DECOMPRESSION_ALGORITHMS) && (decompressionTest); dAlgNb++) + for (dAlgNb=1; (dAlgNb <= NB_DECOMPRESSION_ALGORITHMS) && (decompressionTest); dAlgNb++) { - char* dName = decompressionNames[dAlgNb]; + //const char* dName = decompressionNames[dAlgNb]; + const char* dName; int (*decompressionFunction)(const char*, char*, int, int); double bestTime = 100000000.; - if ((decompressionAlgo != ALL_DECOMPRESSORS) && (decompressionAlgo != dAlgNb+1)) continue; + if ((decompressionAlgo != ALL_DECOMPRESSORS) && (decompressionAlgo != dAlgNb)) continue; switch(dAlgNb) { - case 0: decompressionFunction = local_LZ4_decompress_fast; break; - case 1: decompressionFunction = local_LZ4_decompress_fast_withPrefix64k; break; - case 2: decompressionFunction = local_LZ4_decompress_fast_usingDict; break; - case 3: decompressionFunction = LZ4_decompress_safe; break; - case 4: decompressionFunction = LZ4_decompress_safe_withPrefix64k; break; - case 5: decompressionFunction = local_LZ4_decompress_safe_usingDict; break; - case 6: decompressionFunction = local_LZ4_decompress_safe_partial; break; + case 1: decompressionFunction = local_LZ4_decompress_fast; dName = "LZ4_decompress_fast"; break; + case 2: decompressionFunction = local_LZ4_decompress_fast_withPrefix64k; dName = "LZ4_decompress_fast_withPrefix64k"; break; + case 3: decompressionFunction = local_LZ4_decompress_fast_usingDict; dName = "LZ4_decompress_fast_usingDict"; break; + case 4: decompressionFunction = LZ4_decompress_safe; dName = "LZ4_decompress_safe"; break; + case 5: decompressionFunction = LZ4_decompress_safe_withPrefix64k; dName = "LZ4_decompress_safe_withPrefix64k"; break; + case 6: decompressionFunction = local_LZ4_decompress_safe_usingDict; dName = "LZ4_decompress_safe_usingDict"; break; + case 7: decompressionFunction = local_LZ4_decompress_safe_partial; dName = "LZ4_decompress_safe_partial"; break; + case 8: decompressionFunction = local_LZ4_decompress_safe_forceExtDict; dName = "LZ4_decompress_safe_forceExtDict"; break; + case 9: decompressionFunction = local_LZ4F_decompress; dName = "LZ4F_decompress"; + errorCode = LZ4F_compressFrame(compressed_buff, compressedBuffSize, orig_buff, benchedSize, NULL); + if (LZ4F_isError(errorCode)) { DISPLAY("Preparation error compressing frame\n"); return 1; } + chunkP[0].origSize = (int)benchedSize; + chunkP[0].compressedSize = (int)errorCode; + nbChunks = 1; + break; default : DISPLAY("ERROR ! Bad decompression algorithm Id !! \n"); free(chunkP); return 1; } + { size_t i; for (i=0; i<benchedSize; i++) orig_buff[i]=0; } // zeroing source area, for CRC checking + for (loopNb = 1; loopNb <= nbIterations; loopNb++) { double averageTime; diff --git a/programs/fuzzer.c b/programs/fuzzer.c index b302078..c98333d 100644 --- a/programs/fuzzer.c +++ b/programs/fuzzer.c @@ -29,6 +29,7 @@ #ifdef _MSC_VER /* Visual Studio */ # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ # pragma warning(disable : 4146) /* disable: C4146: minus unsigned expression */ +# pragma warning(disable : 4310) /* disable: C4310: constant char value > 127 */ #endif @@ -85,9 +86,9 @@ -//************************************** -// Macros -//************************************** +/***************************************** + Macros +*****************************************/ #define DISPLAY(...) fprintf(stderr, __VA_ARGS__) #define DISPLAYLEVEL(l, ...) if (displayLevel>=l) { DISPLAY(__VA_ARGS__); } @@ -135,7 +136,7 @@ unsigned int FUZ_rand(unsigned int* src) #define FUZ_RAND15BITS ((FUZ_rand(seed) >> 3) & 32767) -#define FUZ_RANDLENGTH ( ((FUZ_rand(seed) >> 7) & 3) ? (FUZ_rand(seed) % 14) : (FUZ_rand(seed) & 511) + 15) +#define FUZ_RANDLENGTH ( ((FUZ_rand(seed) >> 7) & 3) ? (FUZ_rand(seed) % 15) : (FUZ_rand(seed) % 510) + 15) void FUZ_fillCompressibleNoiseBuffer(void* buffer, int bufferSize, double proba, U32* seed) { BYTE* BBuffer = (BYTE*)buffer; @@ -173,33 +174,9 @@ void FUZ_fillCompressibleNoiseBuffer(void* buffer, int bufferSize, double proba, } -// No longer useful; included into issue 134 -int FUZ_Issue52(void) -{ - char* output; - char* input; - int i, r; - - // Overflow test, by Ludwig Strigeus - printf("Overflow test (issue 52)..."); - input = (char*) malloc (20<<20); - output = (char*) malloc (20<<20); - input[0] = 0x0F; - input[1] = 0x00; - input[2] = 0x00; - for(i = 3; i < 16840000; i++) input[i] = 0xff; - r = LZ4_decompress_safe(input, output, 20<<20, 20<<20); - - free(input); - free(output); - printf(" Passed (return = %i < 0)\n",r); - return 0; -} - - #define MAX_NB_BUFF_I134 150 #define BLOCKSIZE_I134 (32 MB) -int FUZ_Issue134(void) +int FUZ_AddressOverflow(void) { char* buffers[MAX_NB_BUFF_I134+1] = {0}; int i, nbBuff=0; @@ -243,31 +220,31 @@ int FUZ_Issue134(void) char* input = buffers[nbBuff-1]; char* output = buffers[nbBuff]; int r; - input[0] = 0xF0; // Literal length overflow - input[1] = 0xFF; - input[2] = 0xFF; - input[3] = 0xFF; - for(i = 4; i <= nbOf255+4; i++) input[i] = 0xff; + input[0] = (char)0xF0; // Literal length overflow + input[1] = (char)0xFF; + input[2] = (char)0xFF; + input[3] = (char)0xFF; + for(i = 4; i <= nbOf255+4; i++) input[i] = (char)0xff; r = LZ4_decompress_safe(input, output, nbOf255+64, BLOCKSIZE_I134); if (r>0) goto _overflowError; - input[0] = 0x1F; // Match length overflow - input[1] = 0x01; - input[2] = 0x01; - input[3] = 0x00; + input[0] = (char)0x1F; // Match length overflow + input[1] = (char)0x01; + input[2] = (char)0x01; + input[3] = (char)0x00; r = LZ4_decompress_safe(input, output, nbOf255+64, BLOCKSIZE_I134); if (r>0) goto _overflowError; output = buffers[nbBuff-2]; // Reverse in/out pointer order - input[0] = 0xF0; // Literal length overflow - input[1] = 0xFF; - input[2] = 0xFF; - input[3] = 0xFF; + input[0] = (char)0xF0; // Literal length overflow + input[1] = (char)0xFF; + input[2] = (char)0xFF; + input[3] = (char)0xFF; r = LZ4_decompress_safe(input, output, nbOf255+64, BLOCKSIZE_I134); if (r>0) goto _overflowError; - input[0] = 0x1F; // Match length overflow - input[1] = 0x01; - input[2] = 0x01; - input[3] = 0x00; + input[0] = (char)0x1F; // Match length overflow + input[1] = (char)0x01; + input[2] = (char)0x01; + input[3] = (char)0x00; r = LZ4_decompress_safe(input, output, nbOf255+64, BLOCKSIZE_I134); if (r>0) goto _overflowError; } @@ -762,8 +739,7 @@ int main(int argc, char** argv) { printf("Seed = %u\n", seed); if (proba!=FUZ_COMPRESSIBILITY_DEFAULT) printf("Compressibility : %i%%\n", proba); - //FUZ_Issue52(); - FUZ_Issue134(); + FUZ_AddressOverflow(); if (nbTests<=0) nbTests=1; diff --git a/programs/lz4cli.c b/programs/lz4cli.c index 1bbeda0..2d612e7 100644 --- a/programs/lz4cli.c +++ b/programs/lz4cli.c @@ -48,6 +48,10 @@ # pragma warning(disable : 4127) // disable: C4127: conditional expression is constant #endif +#ifdef __clang__ +# pragma clang diagnostic ignored "-Wunused-const-variable" // const variable one is really used ! +#endif + #define _FILE_OFFSET_BITS 64 // Large file support on 32-bits unix #define _POSIX_SOURCE 1 // for fileno() within <stdio.h> on unix @@ -91,7 +95,7 @@ #if defined(_MSC_VER) // Visual Studio # define swap32 _byteswap_ulong -#elif GCC_VERSION >= 403 +#elif (GCC_VERSION >= 403) || defined(__clang__) # define swap32 __builtin_bswap32 #else static inline unsigned int swap32(unsigned int x) @@ -377,7 +381,7 @@ int main(int argc, char** argv) case 'c': forceStdout=1; output_filename=stdoutmark; displayLevel=1; break; // Test - case 't': decode=1; output_filename=nulmark; break; + case 't': decode=1; LZ4IO_setOverwrite(1); output_filename=nulmark; break; // Overwrite case 'f': LZ4IO_setOverwrite(1); break; diff --git a/programs/lz4io.c b/programs/lz4io.c index 2715972..20520d6 100644 --- a/programs/lz4io.c +++ b/programs/lz4io.c @@ -233,7 +233,7 @@ int LZ4IO_setNotificationLevel(int level) /* ************************************************************************ */ -/* ********************** LZ4 File / Stream compression ******************* */ +/* ********************** LZ4 File / Pipe compression ********************* */ /* ************************************************************************ */ static int LZ4S_GetBlockSize_FromBlockId (int id) { return (1 << (8 + (2 * id))); } diff --git a/programs/xxhash.c b/programs/xxhash.c deleted file mode 100644 index be48370..0000000 --- a/programs/xxhash.c +++ /dev/null @@ -1,806 +0,0 @@ -/* -xxHash - Fast Hash algorithm -Copyright (C) 2012-2014, Yann Collet. -BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - -Redistribution and use in source and binary forms, with or without -modification, are permitted provided that the following conditions are -met: - -* Redistributions of source code must retain the above copyright -notice, this list of conditions and the following disclaimer. -* Redistributions in binary form must reproduce the above -copyright notice, this list of conditions and the following disclaimer -in the documentation and/or other materials provided with the -distribution. - -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -You can contact the author at : -- xxHash source repository : http://code.google.com/p/xxhash/ -*/ - - -//************************************** -// Tuning parameters -//************************************** -// Unaligned memory access is automatically enabled for "common" CPU, such as x86. -// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected. -// If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance. -// You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32). -#if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) -# define XXH_USE_UNALIGNED_ACCESS 1 -#endif - -// XXH_ACCEPT_NULL_INPUT_POINTER : -// If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. -// When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. -// This option has a very small performance cost (only measurable on small inputs). -// By default, this option is disabled. To enable it, uncomment below define : -// #define XXH_ACCEPT_NULL_INPUT_POINTER 1 - -// XXH_FORCE_NATIVE_FORMAT : -// By default, xxHash library provides endian-independant Hash values, based on little-endian convention. -// Results are therefore identical for little-endian and big-endian CPU. -// This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. -// Should endian-independance be of no importance for your application, you may set the #define below to 1. -// It will improve speed for Big-endian CPU. -// This option has no impact on Little_Endian CPU. -#define XXH_FORCE_NATIVE_FORMAT 0 - -//************************************** -// Compiler Specific Options -//************************************** -// Disable some Visual warning messages -#ifdef _MSC_VER // Visual Studio -# pragma warning(disable : 4127) // disable: C4127: conditional expression is constant -#endif - -#ifdef _MSC_VER // Visual Studio -# define FORCE_INLINE static __forceinline -#else -# ifdef __GNUC__ -# define FORCE_INLINE static inline __attribute__((always_inline)) -# else -# define FORCE_INLINE static inline -# endif -#endif - -//************************************** -// Includes & Memory related functions -//************************************** -#include "xxhash.h" -// Modify the local functions below should you wish to use some other memory related routines -// for malloc(), free() -#include <stdlib.h> -FORCE_INLINE void* XXH_malloc(size_t s) { return malloc(s); } -FORCE_INLINE void XXH_free (void* p) { free(p); } -// for memcpy() -#include <string.h> -FORCE_INLINE void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); } - - -//************************************** -// Basic Types -//************************************** -#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 -# include <stdint.h> - typedef uint8_t BYTE; - typedef uint16_t U16; - typedef uint32_t U32; - typedef int32_t S32; - typedef uint64_t U64; -#else - typedef unsigned char BYTE; - typedef unsigned short U16; - typedef unsigned int U32; - typedef signed int S32; - typedef unsigned long long U64; -#endif - -#if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS) -# define _PACKED __attribute__ ((packed)) -#else -# define _PACKED -#endif - -#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) -# ifdef __IBMC__ -# pragma pack(1) -# else -# pragma pack(push, 1) -# endif -#endif - -typedef struct _U32_S { U32 v; } _PACKED U32_S; -typedef struct _U64_S { U64 v; } _PACKED U64_S; - -#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) -# pragma pack(pop) -#endif - -#define A32(x) (((U32_S *)(x))->v) -#define A64(x) (((U64_S *)(x))->v) - - -//*************************************** -// Compiler-specific Functions and Macros -//*************************************** -#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) - -// Note : although _rotl exists for minGW (GCC under windows), performance seems poor -#if defined(_MSC_VER) -# define XXH_rotl32(x,r) _rotl(x,r) -# define XXH_rotl64(x,r) _rotl64(x,r) -#else -# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) -# define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r))) -#endif - -#if defined(_MSC_VER) // Visual Studio -# define XXH_swap32 _byteswap_ulong -# define XXH_swap64 _byteswap_uint64 -#elif GCC_VERSION >= 403 -# define XXH_swap32 __builtin_bswap32 -# define XXH_swap64 __builtin_bswap64 -#else -static inline U32 XXH_swap32 (U32 x) { - return ((x << 24) & 0xff000000 ) | - ((x << 8) & 0x00ff0000 ) | - ((x >> 8) & 0x0000ff00 ) | - ((x >> 24) & 0x000000ff );} -static inline U64 XXH_swap64 (U64 x) { - return ((x << 56) & 0xff00000000000000ULL) | - ((x << 40) & 0x00ff000000000000ULL) | - ((x << 24) & 0x0000ff0000000000ULL) | - ((x << 8) & 0x000000ff00000000ULL) | - ((x >> 8) & 0x00000000ff000000ULL) | - ((x >> 24) & 0x0000000000ff0000ULL) | - ((x >> 40) & 0x000000000000ff00ULL) | - ((x >> 56) & 0x00000000000000ffULL);} -#endif - - -//************************************** -// Constants -//************************************** -#define PRIME32_1 2654435761U -#define PRIME32_2 2246822519U -#define PRIME32_3 3266489917U -#define PRIME32_4 668265263U -#define PRIME32_5 374761393U - -#define PRIME64_1 11400714785074694791ULL -#define PRIME64_2 14029467366897019727ULL -#define PRIME64_3 1609587929392839161ULL -#define PRIME64_4 9650029242287828579ULL -#define PRIME64_5 2870177450012600261ULL - -//************************************** -// Architecture Macros -//************************************** -typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; -#ifndef XXH_CPU_LITTLE_ENDIAN // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch - static const int one = 1; -# define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one)) -#endif - - -//************************************** -// Macros -//************************************** -#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations - - -//**************************** -// Memory reads -//**************************** -typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; - -FORCE_INLINE U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align) -{ - if (align==XXH_unaligned) - return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr)); - else - return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr); -} - -FORCE_INLINE U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); } - -FORCE_INLINE U64 XXH_readLE64_align(const U64* ptr, XXH_endianess endian, XXH_alignment align) -{ - if (align==XXH_unaligned) - return endian==XXH_littleEndian ? A64(ptr) : XXH_swap64(A64(ptr)); - else - return endian==XXH_littleEndian ? *ptr : XXH_swap64(*ptr); -} - -FORCE_INLINE U64 XXH_readLE64(const U64* ptr, XXH_endianess endian) { return XXH_readLE64_align(ptr, endian, XXH_unaligned); } - - -//**************************** -// Simple Hash Functions -//**************************** -FORCE_INLINE U32 XXH32_endian_align(const void* input, unsigned int len, U32 seed, XXH_endianess endian, XXH_alignment align) -{ - const BYTE* p = (const BYTE*)input; - const BYTE* bEnd = p + len; - U32 h32; -#define XXH_get32bits(p) XXH_readLE32_align((const U32*)p, endian, align) - -#ifdef XXH_ACCEPT_NULL_INPUT_POINTER - if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)16; } -#endif - - if (len>=16) - { - const BYTE* const limit = bEnd - 16; - U32 v1 = seed + PRIME32_1 + PRIME32_2; - U32 v2 = seed + PRIME32_2; - U32 v3 = seed + 0; - U32 v4 = seed - PRIME32_1; - - do - { - v1 += XXH_get32bits(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; - v2 += XXH_get32bits(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; - v3 += XXH_get32bits(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; - v4 += XXH_get32bits(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; - } while (p<=limit); - - h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); - } - else - { - h32 = seed + PRIME32_5; - } - - h32 += (U32) len; - - while (p+4<=bEnd) - { - h32 += XXH_get32bits(p) * PRIME32_3; - h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; - p+=4; - } - - while (p<bEnd) - { - h32 += (*p) * PRIME32_5; - h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; - p++; - } - - h32 ^= h32 >> 15; - h32 *= PRIME32_2; - h32 ^= h32 >> 13; - h32 *= PRIME32_3; - h32 ^= h32 >> 16; - - return h32; -} - - -U32 XXH32(const void* input, unsigned int len, U32 seed) -{ -#if 0 - // Simple version, good for code maintenance, but unfortunately slow for small inputs - void* state = XXH32_init(seed); - XXH32_update(state, input, len); - return XXH32_digest(state); -#else - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - -# if !defined(XXH_USE_UNALIGNED_ACCESS) - if ((((size_t)input) & 3) == 0) // Input is aligned, let's leverage the speed advantage - { - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); - else - return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); - } -# endif - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); - else - return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); -#endif -} - -FORCE_INLINE U64 XXH64_endian_align(const void* input, unsigned int len, U64 seed, XXH_endianess endian, XXH_alignment align) -{ - const BYTE* p = (const BYTE*)input; - const BYTE* bEnd = p + len; - U64 h64; -#define XXH_get64bits(p) XXH_readLE64_align((const U64*)p, endian, align) - -#ifdef XXH_ACCEPT_NULL_INPUT_POINTER - if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)32; } -#endif - - if (len>=32) - { - const BYTE* const limit = bEnd - 32; - U64 v1 = seed + PRIME64_1 + PRIME64_2; - U64 v2 = seed + PRIME64_2; - U64 v3 = seed + 0; - U64 v4 = seed - PRIME64_1; - - do - { - v1 += XXH_get64bits(p) * PRIME64_2; p+=8; v1 = XXH_rotl64(v1, 31); v1 *= PRIME64_1; - v2 += XXH_get64bits(p) * PRIME64_2; p+=8; v2 = XXH_rotl64(v2, 31); v2 *= PRIME64_1; - v3 += XXH_get64bits(p) * PRIME64_2; p+=8; v3 = XXH_rotl64(v3, 31); v3 *= PRIME64_1; - v4 += XXH_get64bits(p) * PRIME64_2; p+=8; v4 = XXH_rotl64(v4, 31); v4 *= PRIME64_1; - } while (p<=limit); - - h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); - - v1 *= PRIME64_2; v1 = XXH_rotl64(v1, 31); v1 *= PRIME64_1; h64 ^= v1; - h64 = h64 * PRIME64_1 + PRIME64_4; - - v2 *= PRIME64_2; v2 = XXH_rotl64(v2, 31); v2 *= PRIME64_1; h64 ^= v2; - h64 = h64 * PRIME64_1 + PRIME64_4; - - v3 *= PRIME64_2; v3 = XXH_rotl64(v3, 31); v3 *= PRIME64_1; h64 ^= v3; - h64 = h64 * PRIME64_1 + PRIME64_4; - - v4 *= PRIME64_2; v4 = XXH_rotl64(v4, 31); v4 *= PRIME64_1; h64 ^= v4; - h64 = h64 * PRIME64_1 + PRIME64_4; - } - else - { - h64 = seed + PRIME64_5; - } - - h64 += (U64) len; - - while (p+8<=bEnd) - { - U64 k1 = XXH_get64bits(p); - k1 *= PRIME64_2; k1 = XXH_rotl64(k1,31); k1 *= PRIME64_1; h64 ^= k1; - h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; - p+=8; - } - - if (p+4<=bEnd) - { - h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1; - h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; - p+=4; - } - - while (p<bEnd) - { - h64 ^= (*p) * PRIME64_5; - h64 = XXH_rotl64(h64, 11) * PRIME64_1; - p++; - } - - h64 ^= h64 >> 33; - h64 *= PRIME64_2; - h64 ^= h64 >> 29; - h64 *= PRIME64_3; - h64 ^= h64 >> 32; - - return h64; -} - - -unsigned long long XXH64(const void* input, unsigned int len, unsigned long long seed) -{ - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - -# if !defined(XXH_USE_UNALIGNED_ACCESS) - if ((((size_t)input) & 7)==0) // Input is aligned, let's leverage the speed advantage - { - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); - else - return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); - } -# endif - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); - else - return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); -} - -//**************************** -// Advanced Hash Functions -//**************************** - -struct XXH_state32_t -{ - U64 total_len; - U32 seed; - U32 v1; - U32 v2; - U32 v3; - U32 v4; - int memsize; - char memory[16]; -}; - -struct XXH_state64_t -{ - U64 total_len; - U64 seed; - U64 v1; - U64 v2; - U64 v3; - U64 v4; - int memsize; - char memory[32]; -}; - - -int XXH32_sizeofState(void) -{ - XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); // A compilation error here means XXH32_SIZEOFSTATE is not large enough - return sizeof(struct XXH_state32_t); -} - -int XXH64_sizeofState(void) -{ - XXH_STATIC_ASSERT(XXH64_SIZEOFSTATE >= sizeof(struct XXH_state64_t)); // A compilation error here means XXH64_SIZEOFSTATE is not large enough - return sizeof(struct XXH_state64_t); -} - - -XXH_errorcode XXH32_resetState(void* state_in, U32 seed) -{ - struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; - state->seed = seed; - state->v1 = seed + PRIME32_1 + PRIME32_2; - state->v2 = seed + PRIME32_2; - state->v3 = seed + 0; - state->v4 = seed - PRIME32_1; - state->total_len = 0; - state->memsize = 0; - return XXH_OK; -} - -XXH_errorcode XXH64_resetState(void* state_in, unsigned long long seed) -{ - struct XXH_state64_t * state = (struct XXH_state64_t *) state_in; - state->seed = seed; - state->v1 = seed + PRIME64_1 + PRIME64_2; - state->v2 = seed + PRIME64_2; - state->v3 = seed + 0; - state->v4 = seed - PRIME64_1; - state->total_len = 0; - state->memsize = 0; - return XXH_OK; -} - - -void* XXH32_init (U32 seed) -{ - void* state = XXH_malloc (sizeof(struct XXH_state32_t)); - if (state != NULL) XXH32_resetState(state, seed); - return state; -} - -void* XXH64_init (unsigned long long seed) -{ - void* state = XXH_malloc (sizeof(struct XXH_state64_t)); - if (state != NULL) XXH64_resetState(state, seed); - return state; -} - - -FORCE_INLINE XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian) -{ - struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; - const BYTE* p = (const BYTE*)input; - const BYTE* const bEnd = p + len; - -#ifdef XXH_ACCEPT_NULL_INPUT_POINTER - if (input==NULL) return XXH_ERROR; -#endif - - state->total_len += len; - - if (state->memsize + len < 16) // fill in tmp buffer - { - XXH_memcpy(state->memory + state->memsize, input, len); - state->memsize += len; - return XXH_OK; - } - - if (state->memsize) // some data left from previous update - { - XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize); - { - const U32* p32 = (const U32*)state->memory; - state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++; - state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++; - state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++; - state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++; - } - p += 16-state->memsize; - state->memsize = 0; - } - - if (p <= bEnd-16) - { - const BYTE* const limit = bEnd - 16; - U32 v1 = state->v1; - U32 v2 = state->v2; - U32 v3 = state->v3; - U32 v4 = state->v4; - - do - { - v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; - v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; - v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; - v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; - } while (p<=limit); - - state->v1 = v1; - state->v2 = v2; - state->v3 = v3; - state->v4 = v4; - } - - if (p < bEnd) - { - XXH_memcpy(state->memory, p, bEnd-p); - state->memsize = (int)(bEnd-p); - } - - return XXH_OK; -} - -XXH_errorcode XXH32_update (void* state_in, const void* input, unsigned int len) -{ - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH32_update_endian(state_in, input, len, XXH_littleEndian); - else - return XXH32_update_endian(state_in, input, len, XXH_bigEndian); -} - - - -FORCE_INLINE U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian) -{ - struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; - const BYTE * p = (const BYTE*)state->memory; - BYTE* bEnd = (BYTE*)state->memory + state->memsize; - U32 h32; - - if (state->total_len >= 16) - { - h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); - } - else - { - h32 = state->seed + PRIME32_5; - } - - h32 += (U32) state->total_len; - - while (p+4<=bEnd) - { - h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3; - h32 = XXH_rotl32(h32, 17) * PRIME32_4; - p+=4; - } - - while (p<bEnd) - { - h32 += (*p) * PRIME32_5; - h32 = XXH_rotl32(h32, 11) * PRIME32_1; - p++; - } - - h32 ^= h32 >> 15; - h32 *= PRIME32_2; - h32 ^= h32 >> 13; - h32 *= PRIME32_3; - h32 ^= h32 >> 16; - - return h32; -} - - -U32 XXH32_intermediateDigest (void* state_in) -{ - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian); - else - return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian); -} - - -U32 XXH32_digest (void* state_in) -{ - U32 h32 = XXH32_intermediateDigest(state_in); - - XXH_free(state_in); - - return h32; -} - - -FORCE_INLINE XXH_errorcode XXH64_update_endian (void* state_in, const void* input, int len, XXH_endianess endian) -{ - struct XXH_state64_t * state = (struct XXH_state64_t *) state_in; - const BYTE* p = (const BYTE*)input; - const BYTE* const bEnd = p + len; - -#ifdef XXH_ACCEPT_NULL_INPUT_POINTER - if (input==NULL) return XXH_ERROR; -#endif - - state->total_len += len; - - if (state->memsize + len < 32) // fill in tmp buffer - { - XXH_memcpy(state->memory + state->memsize, input, len); - state->memsize += len; - return XXH_OK; - } - - if (state->memsize) // some data left from previous update - { - XXH_memcpy(state->memory + state->memsize, input, 32-state->memsize); - { - const U64* p64 = (const U64*)state->memory; - state->v1 += XXH_readLE64(p64, endian) * PRIME64_2; state->v1 = XXH_rotl64(state->v1, 31); state->v1 *= PRIME64_1; p64++; - state->v2 += XXH_readLE64(p64, endian) * PRIME64_2; state->v2 = XXH_rotl64(state->v2, 31); state->v2 *= PRIME64_1; p64++; - state->v3 += XXH_readLE64(p64, endian) * PRIME64_2; state->v3 = XXH_rotl64(state->v3, 31); state->v3 *= PRIME64_1; p64++; - state->v4 += XXH_readLE64(p64, endian) * PRIME64_2; state->v4 = XXH_rotl64(state->v4, 31); state->v4 *= PRIME64_1; p64++; - } - p += 32-state->memsize; - state->memsize = 0; - } - - if (p+32 <= bEnd) - { - const BYTE* const limit = bEnd - 32; - U64 v1 = state->v1; - U64 v2 = state->v2; - U64 v3 = state->v3; - U64 v4 = state->v4; - - do - { - v1 += XXH_readLE64((const U64*)p, endian) * PRIME64_2; v1 = XXH_rotl64(v1, 31); v1 *= PRIME64_1; p+=8; - v2 += XXH_readLE64((const U64*)p, endian) * PRIME64_2; v2 = XXH_rotl64(v2, 31); v2 *= PRIME64_1; p+=8; - v3 += XXH_readLE64((const U64*)p, endian) * PRIME64_2; v3 = XXH_rotl64(v3, 31); v3 *= PRIME64_1; p+=8; - v4 += XXH_readLE64((const U64*)p, endian) * PRIME64_2; v4 = XXH_rotl64(v4, 31); v4 *= PRIME64_1; p+=8; - } while (p<=limit); - - state->v1 = v1; - state->v2 = v2; - state->v3 = v3; - state->v4 = v4; - } - - if (p < bEnd) - { - XXH_memcpy(state->memory, p, bEnd-p); - state->memsize = (int)(bEnd-p); - } - - return XXH_OK; -} - -XXH_errorcode XXH64_update (void* state_in, const void* input, unsigned int len) -{ - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH64_update_endian(state_in, input, len, XXH_littleEndian); - else - return XXH64_update_endian(state_in, input, len, XXH_bigEndian); -} - - - -FORCE_INLINE U64 XXH64_intermediateDigest_endian (void* state_in, XXH_endianess endian) -{ - struct XXH_state64_t * state = (struct XXH_state64_t *) state_in; - const BYTE * p = (const BYTE*)state->memory; - BYTE* bEnd = (BYTE*)state->memory + state->memsize; - U64 h64; - - if (state->total_len >= 32) - { - U64 v1 = state->v1; - U64 v2 = state->v2; - U64 v3 = state->v3; - U64 v4 = state->v4; - - h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); - - v1 *= PRIME64_2; v1 = XXH_rotl64(v1, 31); v1 *= PRIME64_1; h64 ^= v1; - h64 = h64*PRIME64_1 + PRIME64_4; - - v2 *= PRIME64_2; v2 = XXH_rotl64(v2, 31); v2 *= PRIME64_1; h64 ^= v2; - h64 = h64*PRIME64_1 + PRIME64_4; - - v3 *= PRIME64_2; v3 = XXH_rotl64(v3, 31); v3 *= PRIME64_1; h64 ^= v3; - h64 = h64*PRIME64_1 + PRIME64_4; - - v4 *= PRIME64_2; v4 = XXH_rotl64(v4, 31); v4 *= PRIME64_1; h64 ^= v4; - h64 = h64*PRIME64_1 + PRIME64_4; - } - else - { - h64 = state->seed + PRIME64_5; - } - - h64 += (U64) state->total_len; - - while (p+8<=bEnd) - { - U64 k1 = XXH_readLE64((const U64*)p, endian); - k1 *= PRIME64_2; k1 = XXH_rotl64(k1,31); k1 *= PRIME64_1; h64 ^= k1; - h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; - p+=8; - } - - if (p+4<=bEnd) - { - h64 ^= (U64)(XXH_readLE32((const U32*)p, endian)) * PRIME64_1; - h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; - p+=4; - } - - while (p<bEnd) - { - h64 ^= (*p) * PRIME64_5; - h64 = XXH_rotl64(h64, 11) * PRIME64_1; - p++; - } - - h64 ^= h64 >> 33; - h64 *= PRIME64_2; - h64 ^= h64 >> 29; - h64 *= PRIME64_3; - h64 ^= h64 >> 32; - - return h64; -} - - -unsigned long long XXH64_intermediateDigest (void* state_in) -{ - XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; - - if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) - return XXH64_intermediateDigest_endian(state_in, XXH_littleEndian); - else - return XXH64_intermediateDigest_endian(state_in, XXH_bigEndian); -} - - -unsigned long long XXH64_digest (void* state_in) -{ - U64 h64 = XXH64_intermediateDigest(state_in); - - XXH_free(state_in); - - return h64; -} - diff --git a/programs/xxhash.h b/programs/xxhash.h deleted file mode 100644 index 4311485..0000000 --- a/programs/xxhash.h +++ /dev/null @@ -1,168 +0,0 @@ -/* - xxHash - Extremely Fast Hash algorithm - Header File - Copyright (C) 2012-2014, Yann Collet. - BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following disclaimer - in the documentation and/or other materials provided with the - distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - You can contact the author at : - - xxHash source repository : http://code.google.com/p/xxhash/ -*/ - -/* Notice extracted from xxHash homepage : - -xxHash is an extremely fast Hash algorithm, running at RAM speed limits. -It also successfully passes all tests from the SMHasher suite. - -Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) - -Name Speed Q.Score Author -xxHash 5.4 GB/s 10 -CrapWow 3.2 GB/s 2 Andrew -MumurHash 3a 2.7 GB/s 10 Austin Appleby -SpookyHash 2.0 GB/s 10 Bob Jenkins -SBox 1.4 GB/s 9 Bret Mulvey -Lookup3 1.2 GB/s 9 Bob Jenkins -SuperFastHash 1.2 GB/s 1 Paul Hsieh -CityHash64 1.05 GB/s 10 Pike & Alakuijala -FNV 0.55 GB/s 5 Fowler, Noll, Vo -CRC32 0.43 GB/s 9 -MD5-32 0.33 GB/s 10 Ronald L. Rivest -SHA1-32 0.28 GB/s 10 - -Q.Score is a measure of quality of the hash function. -It depends on successfully passing SMHasher test set. -10 is a perfect score. -*/ - -#pragma once - -#if defined (__cplusplus) -extern "C" { -#endif - - -/***************************** - Type -*****************************/ -typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode; - - - -/***************************** - Simple Hash Functions -*****************************/ - -unsigned int XXH32 (const void* input, unsigned int len, unsigned int seed); -unsigned long long XXH64 (const void* input, unsigned int len, unsigned long long seed); - -/* -XXH32() : - Calculate the 32-bits hash of sequence of length "len" stored at memory address "input". - The memory between input & input+len must be valid (allocated and read-accessible). - "seed" can be used to alter the result predictably. - This function successfully passes all SMHasher tests. - Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s - Note that "len" is type "int", which means it is limited to 2^31-1. - If your data is larger, use the advanced functions below. -XXH64() : - Calculate the 64-bits hash of sequence of length "len" stored at memory address "input". -*/ - - - -/***************************** - Advanced Hash Functions -*****************************/ - -void* XXH32_init (unsigned int seed); -XXH_errorcode XXH32_update (void* state, const void* input, unsigned int len); -unsigned int XXH32_digest (void* state); - -void* XXH64_init (unsigned long long seed); -XXH_errorcode XXH64_update (void* state, const void* input, unsigned int len); -unsigned long long XXH64_digest (void* state); - -/* -These functions calculate the xxhash of an input provided in several small packets, -as opposed to an input provided as a single block. - -It must be started with : -void* XXHnn_init() -The function returns a pointer which holds the state of calculation. -If the pointer is NULL, allocation has failed, so no state can be tracked. - -The state pointer must be provided as "void* state" parameter for XXHnn_update(). -XXHnn_update() can be called as many times as necessary. -The user must provide a valid (allocated) input. -The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. -Note that "len" is type "int", which means it is limited to 2^31-1. -If your data is larger, it is recommended to chunk your data into blocks -of size for example 2^30 (1GB) to avoid any "int" overflow issue. - -Finally, you can end the calculation anytime, by using XXHnn_digest(). -This function returns the final nn-bits hash. -You must provide the same "void* state" parameter created by XXHnn_init(). -Memory will be freed by XXHnn_digest(). -*/ - - -int XXH32_sizeofState(void); -XXH_errorcode XXH32_resetState(void* state, unsigned int seed); - -#define XXH32_SIZEOFSTATE 48 -typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t; - -int XXH64_sizeofState(void); -XXH_errorcode XXH64_resetState(void* state, unsigned long long seed); - -#define XXH64_SIZEOFSTATE 88 -typedef struct { long long ll[(XXH64_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH64_stateSpace_t; - -/* -These functions allow user application to make its own allocation for state. - -XXHnn_sizeofState() is used to know how much space must be allocated for the xxHash nn-bits state. -Note that the state must be aligned to access 'long long' fields. Memory must be allocated and referenced by a pointer. -This pointer must then be provided as 'state' into XXHnn_resetState(), which initializes the state. - -For static allocation purposes (such as allocation on stack, or freestanding systems without malloc()), -use the structure XXHnn_stateSpace_t, which will ensure that memory space is large enough and correctly aligned to access 'long long' fields. -*/ - - -unsigned int XXH32_intermediateDigest (void* state); -unsigned long long XXH64_intermediateDigest (void* state); -/* -These functions do the same as XXHnn_digest(), generating a nn-bit hash, -but preserve memory context. -This way, it becomes possible to generate intermediate hashes, and then continue feeding data with XXHnn_update(). -To free memory context, use XXHnn_digest(), or free(). -*/ - - -#if defined (__cplusplus) -} -#endif |