diff options
author | yann.collet.73@gmail.com <yann.collet.73@gmail.com@650e7d94-2a16-8b24-b05c-7c0b3f6821cd> | 2013-04-13 09:31:22 (GMT) |
---|---|---|
committer | yann.collet.73@gmail.com <yann.collet.73@gmail.com@650e7d94-2a16-8b24-b05c-7c0b3f6821cd> | 2013-04-13 09:31:22 (GMT) |
commit | cbfd031d301222123d185320a55a923f9363f781 (patch) | |
tree | 4d1b6bee26974c0bb98ec3c2989e8e1d81da3046 | |
parent | 647baabcef0effcfcb3cc0dadb2970db681c9d52 (diff) | |
download | lz4-cbfd031d301222123d185320a55a923f9363f781.zip lz4-cbfd031d301222123d185320a55a923f9363f781.tar.gz lz4-cbfd031d301222123d185320a55a923f9363f781.tar.bz2 |
Added : LZ4 Streaming Format specification (v1.3)
Added : LZ4c command-line utility, supporting the new streaming format
Added : xxhash library
Removed : lz4demo is now replaced by lz4.c
Removed : a few level 4 warnings (issue 64)
Updated : makefiles
git-svn-id: https://lz4.googlecode.com/svn/trunk@92 650e7d94-2a16-8b24-b05c-7c0b3f6821cd
-rw-r--r-- | LZ4 Streaming Format.odt | bin | 0 -> 80344 bytes | |||
-rw-r--r-- | Makefile | 10 | ||||
-rw-r--r-- | bench.c | 6 | ||||
-rw-r--r-- | bench.h | 2 | ||||
-rw-r--r-- | cmake/CMakeLists.txt | 22 | ||||
-rw-r--r-- | cmake/pack/CMakeLists.txt | 16 | ||||
-rw-r--r-- | fuzzer.c | 4 | ||||
-rw-r--r-- | lz4.c | 44 | ||||
-rw-r--r-- | lz4.h | 23 | ||||
-rw-r--r-- | lz4_format_description.txt | 17 | ||||
-rw-r--r-- | lz4c.c | 799 | ||||
-rw-r--r-- | lz4demo.c | 482 | ||||
-rw-r--r-- | lz4hc.c | 14 | ||||
-rw-r--r-- | lz4hc.h | 2 | ||||
-rw-r--r-- | xxhash.c | 344 | ||||
-rw-r--r-- | xxhash.h | 147 |
16 files changed, 1371 insertions, 561 deletions
diff --git a/LZ4 Streaming Format.odt b/LZ4 Streaming Format.odt Binary files differnew file mode 100644 index 0000000..62aeecb --- /dev/null +++ b/LZ4 Streaming Format.odt @@ -8,18 +8,18 @@ else EXT =.exe endif -default: lz4demo +default: lz4c -all: lz4demo lz4demo32 fuzzer +all: lz4c lz4c32 fuzzer -lz4demo: lz4.c lz4hc.c bench.c lz4demo.c +lz4c: lz4.c lz4hc.c bench.c xxhash.c lz4c.c $(CC) -O3 $(CFLAGS) $^ -o $@$(EXT) -lz4demo32: lz4.c lz4hc.c bench.c lz4demo.c +lz4c32: lz4.c lz4hc.c bench.c xxhash.c lz4c.c $(CC) -m32 -Os -march=native $(CFLAGS) $^ -o $@$(EXT) fuzzer : lz4.c fuzzer.c $(CC) -O3 $(CFLAGS) $^ -o $@$(EXT) clean: - rm -f core *.o lz4demo$(EXT) lz4demo32$(EXT) fuzzer$(EXT) + rm -f core *.o lz4c$(EXT) lz4c32$(EXT) fuzzer$(EXT) @@ -1,6 +1,6 @@ /*
bench.c - Demo program to benchmark open-source compression algorithm
- Copyright (C) Yann Collet 2012
+ Copyright (C) Yann Collet 2012-2013
GPL v2 License
This program is free software; you can redistribute it and/or modify
@@ -138,13 +138,13 @@ static int BMK_pause = 0; void BMK_SetBlocksize(int bsize)
{
chunkSize = bsize;
- DISPLAY("-Using Block Size of %i KB-", chunkSize>>10);
+ DISPLAY("-Using Block Size of %i KB-\n", chunkSize>>10);
}
void BMK_SetNbIterations(int nbLoops)
{
nbIterations = nbLoops;
- DISPLAY("- %i iterations-", nbIterations);
+ DISPLAY("- %i iterations-\n", nbIterations);
}
void BMK_SetPause()
@@ -1,6 +1,6 @@ /*
bench.h - Demo program to benchmark open-source compression algorithm
- Copyright (C) Yann Collet 2012
+ Copyright (C) Yann Collet 2012-2013
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
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt index 3d3e558..1afe650 100644 --- a/cmake/CMakeLists.txt +++ b/cmake/CMakeLists.txt @@ -2,7 +2,7 @@ PROJECT(LZ4) set(CPACK_PACKAGE_DESCRIPTION_SUMMARY "ASN.1 Compiler")
set(CPACK_PACKAGE_VERSION_MAJOR 0)
set(CPACK_PACKAGE_VERSION_MINOR 0)
-set(CPACK_PACKAGE_VERSION_PATCH r51)
+set(CPACK_PACKAGE_VERSION_PATCH r52)
#set(CPACK_RESOURCE_FILE_LICENSE ${CMAKE_CURRENT_BINARY_DIR}/COPYING_LGPL)
set(VERSION_STRING " \"${CPACK_PACKAGE_VERSION_MAJOR}.${CPACK_PACKAGE_VERSION_MINOR}.${CPACK_PACKAGE_VERSION_PATCH}\" ")
include(CPack)
@@ -32,7 +32,7 @@ endif() set(SRC_DIR ../)
set(LZ4_SRCS_LIB ${SRC_DIR}lz4.c ${SRC_DIR}lz4hc.c ${SRC_DIR}lz4.h )
-set(LZ4_SRCS ${SRC_DIR}bench.c ${SRC_DIR}lz4demo.c)
+set(LZ4_SRCS ${SRC_DIR}xxhash.c ${SRC_DIR}bench.c ${SRC_DIR}lz4c.c)
if(NOT BUILD_SHARED_LIBS)
set(LZ4_SRCS ${LZ4_SRCS} ${LZ4_SRCS_LIB})
@@ -40,28 +40,28 @@ endif() if (CMAKE_SYSTEM_PROCESSOR STREQUAL "64bit")
message(STATUS "Build 64bit executable binary")
- add_executable(lz4demo64 ${LZ4_SRCS})
- install(TARGETS lz4demo64 RUNTIME DESTINATION "./")
+ add_executable(lz4c64 ${LZ4_SRCS})
+ install(TARGETS lz4c64 RUNTIME DESTINATION "./")
if(NOT BUILD_SHARED_LIBS)
message(STATUS "Build 32bit executable binary")
- add_executable(lz4demo32 ${LZ4_SRCS})
- install(TARGETS lz4demo32 RUNTIME DESTINATION "./")
+ add_executable(lz4c32 ${LZ4_SRCS})
+ install(TARGETS lz4c32 RUNTIME DESTINATION "./")
- SET_TARGET_PROPERTIES(lz4demo32 PROPERTIES
+ SET_TARGET_PROPERTIES(lz4c32 PROPERTIES
COMPILE_FLAGS PROPERTIES COMPILE_FLAGS "-m32" LINK_FLAGS "-m32")
endif()
else()
message(STATUS "Build 32bit executable binary")
- add_executable(lz4demo32 ${LZ4_SRCS})
- install(TARGETS lz4demo32 RUNTIME DESTINATION "./")
+ add_executable(lz4c32 ${LZ4_SRCS})
+ install(TARGETS lz4c32 RUNTIME DESTINATION "./")
endif()
if(BUILD_SHARED_LIBS)
set(LZ4_SOVERSION "${CPACK_PACKAGE_VERSION_MAJOR}.${CPACK_PACKAGE_VERSION_MINOR}")
if (CMAKE_SYSTEM_PROCESSOR STREQUAL "64bit")
- target_link_libraries(lz4demo64 liblz4)
+ target_link_libraries(lz4c64 liblz4)
else()
- target_link_libraries(lz4demo32 liblz4)
+ target_link_libraries(lz4c32 liblz4)
endif()
# for static library
diff --git a/cmake/pack/CMakeLists.txt b/cmake/pack/CMakeLists.txt index 6d23235..8e59824 100644 --- a/cmake/pack/CMakeLists.txt +++ b/cmake/pack/CMakeLists.txt @@ -42,21 +42,21 @@ INCLUDE_DIRECTORIES (${SRC_DIR}) set(LZ4_SRCS_LIB ${SRC_DIR}lz4.c ${SRC_DIR}lz4hc.c ${SRC_DIR}lz4.h ${SRC_DIR}lz4_format_description.txt)
-set(LZ4_SRCS ${LZ4_SRCS_LIB} ${SRC_DIR}bench.c ${SRC_DIR}lz4demo.c )
-set(FIZZER_SRCS ${SRC_DIR}lz4.c ${SRC_DIR}lz4hc.c ${SRC_DIR}lz4.h ${SRC_DIR}fuzzer.c)
+set(LZ4_SRCS ${LZ4_SRCS_LIB} ${SRC_DIR}xxhash.c ${SRC_DIR}bench.c ${SRC_DIR}lz4c.c )
+set(FUZZER_SRCS ${SRC_DIR}lz4.c ${SRC_DIR}lz4hc.c ${SRC_DIR}lz4.h ${SRC_DIR}fuzzer.c)
# EXECUTABLES FOR 32 Bit and 64 versions
if(CMAKE_SYSTEM_PROCESSOR STREQUAL "64bit")
- add_executable(lz4demo32 ${LZ4_SRCS})
- install(TARGETS lz4demo32 RUNTIME DESTINATION "./")
-SET_TARGET_PROPERTIES(lz4demo32 PROPERTIES
+ add_executable(lz4c32 ${LZ4_SRCS})
+ install(TARGETS lz4c32 RUNTIME DESTINATION "./")
+SET_TARGET_PROPERTIES(lz4c32 PROPERTIES
COMPILE_FLAGS PROPERTIES COMPILE_FLAGS "-m32 -Os" LINK_FLAGS "-m32")
endif()
-add_executable(lz4demo ${LZ4_SRCS})
-install(TARGETS lz4demo RUNTIME DESTINATION "./")
+add_executable(lz4c ${LZ4_SRCS})
+install(TARGETS lz4c RUNTIME DESTINATION "./")
-add_executable(fuzzer ${FIZZER_SRCS})
+add_executable(fuzzer ${FUZZER_SRCS})
install(TARGETS fuzzer RUNTIME DESTINATION "./")
#target_link_libraries(lz4 ${LZ4_SRCS_LIB})
@@ -1,6 +1,6 @@ /*
fuzzer.c - Fuzzer test tool for LZ4
- Copyright (C) Andrew Mahone - Yann Collet 2012
+ Copyright (C) Andrew Mahone - Yann Collet 2012-2013
Original code by Andrew Mahone / Modified by Yann Collet
GPL v2 License
@@ -99,7 +99,7 @@ int FUZ_SecurityTest() char* input;
int i, r;
- printf("Starting security tests...");
+ printf("Starting security tests (issue 52)...");
input = (char*) malloc (20<<20);
output = (char*) malloc (20<<20);
input[0] = 0x0F;
@@ -1,6 +1,6 @@ /*
LZ4 - Fast LZ compression algorithm
- Copyright (C) 2011-2012, Yann Collet.
+ Copyright (C) 2011-2013, 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
@@ -110,6 +110,7 @@ # pragma intrinsic(_BitScanForward) // For Visual 2005
# pragma intrinsic(_BitScanReverse) // For Visual 2005
# endif
+# pragma warning(disable : 4127) // disable: C4127: conditional expression is constant
#endif
#ifdef _MSC_VER
@@ -141,17 +142,17 @@ //**************************************
#if defined(_MSC_VER) // Visual Studio does not support 'stdint' natively
# define BYTE unsigned __int8
-# define U16 unsigned __int16
-# define U32 unsigned __int32
-# define S32 __int32
-# define U64 unsigned __int64
+# define U16 unsigned __int16
+# define U32 unsigned __int32
+# define S32 __int32
+# define U64 unsigned __int64
#else
# include <stdint.h>
# define BYTE uint8_t
-# define U16 uint16_t
-# define U32 uint32_t
-# define S32 int32_t
-# define U64 uint64_t
+# define U16 uint16_t
+# define U32 uint32_t
+# define S32 int32_t
+# define U64 uint64_t
#endif
#ifndef LZ4_FORCE_UNALIGNED_ACCESS
@@ -378,7 +379,7 @@ static inline int LZ4_compressCtx(void** ctx, // First Byte
- HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
+ HashTable[LZ4_HASH_VALUE(ip)] = (HTYPE)(ip - base);
ip++; forwardH = LZ4_HASH_VALUE(ip);
// Main Loop
@@ -400,7 +401,7 @@ static inline int LZ4_compressCtx(void** ctx, forwardH = LZ4_HASH_VALUE(forwardIp);
ref = base + HashTable[h];
- HashTable[h] = ip - base;
+ HashTable[h] = (HTYPE)(ip - base);
} while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
@@ -427,7 +428,7 @@ static inline int LZ4_compressCtx(void** ctx, else
*op++ = (BYTE)len;
}
- else *token = (length<<ML_BITS);
+ else *token = (BYTE)(length<<ML_BITS);
#else
if (length>=(int)RUN_MASK)
{
@@ -473,17 +474,17 @@ _endCount: if (length > 254) { length-=255; *op++ = 255; }
*op++ = (BYTE)length;
}
- else *token += length;
+ else *token += (BYTE)length;
// Test end of chunk
if (ip > mflimit) { anchor = ip; break; }
// Fill table
- HashTable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;
+ HashTable[LZ4_HASH_VALUE(ip-2)] = (HTYPE)(ip - 2 - base);
// Test next position
ref = base + HashTable[LZ4_HASH_VALUE(ip)];
- HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
+ HashTable[LZ4_HASH_VALUE(ip)] = (HTYPE)(ip - base);
if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }
// Prepare next loop
@@ -497,7 +498,7 @@ _last_literals: int lastRun = (int)(iend - anchor);
if (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) return 0;
if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
- else *op++ = (lastRun<<ML_BITS);
+ else *op++ = (BYTE)(lastRun<<ML_BITS);
memcpy(op, anchor, iend - anchor);
op += iend-anchor;
}
@@ -606,7 +607,7 @@ static inline int LZ4_compress64kCtx(void** ctx, else
*op++ = (BYTE)len;
}
- else *token = (length<<ML_BITS);
+ else *token = (BYTE)(length<<ML_BITS);
#else
if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }
else *token = (length<<ML_BITS);
@@ -638,7 +639,7 @@ _endCount: len = (int)(ip - anchor);
if unlikely(op + (1 + LASTLITERALS) + (len>>8) > oend) return 0; // Check output limit
if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }
- else *token += len;
+ else *token += (BYTE)len;
// Test end of chunk
if (ip > mflimit) { anchor = ip; break; }
@@ -662,7 +663,7 @@ _last_literals: int lastRun = (int)(iend - anchor);
if (op + lastRun + 1 + (lastRun-RUN_MASK+255)/255 > oend) return 0;
if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
- else *op++ = (lastRun<<ML_BITS);
+ else *op++ = (BYTE)(lastRun<<ML_BITS);
memcpy(op, anchor, iend - anchor);
op += iend-anchor;
}
@@ -680,6 +681,7 @@ int LZ4_compress_limitedOutput(const char* source, #if HEAPMODE
void* ctx = malloc(sizeof(struct refTables));
int result;
+ if (ctx == NULL) return 0; // Failed allocation => compression not done
if (isize < LZ4_64KLIMIT)
result = LZ4_compress64kCtx(&ctx, source, dest, isize, maxOutputSize);
else result = LZ4_compressCtx(&ctx, source, dest, isize, maxOutputSize);
@@ -729,7 +731,7 @@ int LZ4_uncompress(const char* source, size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
#if LZ4_ARCH64
- size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
+ size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
#endif
@@ -817,7 +819,7 @@ int LZ4_uncompress_unknownOutputSize( size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
#if LZ4_ARCH64
- size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
+ size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
#endif
@@ -1,7 +1,7 @@ /*
LZ4 - Fast LZ compression algorithm
Header File
- Copyright (C) 2011-2012, Yann Collet.
+ Copyright (C) 2011-2013, 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
@@ -50,27 +50,26 @@ extern "C" { // Simple Functions
//****************************
-int LZ4_compress (const char* source, char* dest, int isize);
-int LZ4_uncompress (const char* source, char* dest, int osize);
+int LZ4_compress (const char* source, char* dest, int input_size);
+int LZ4_uncompress (const char* source, char* dest, int output_size);
/*
LZ4_compress() :
- Compresses 'isize' bytes from 'source' into 'dest'.
+ Compresses 'input_size' bytes from 'source' into 'dest'.
Destination buffer must be already allocated,
and must be sized to handle worst cases situations (input data not compressible)
Worst case size evaluation is provided by function LZ4_compressBound()
-
- isize : is the input size. Max supported value is ~1.9GB
+ input_size : Max supported value is ~1.9GB
return : the number of bytes written in buffer dest
-
+ or 0 if the compression fails
LZ4_uncompress() :
- osize : is the output size, therefore the original size
+ output_size : is the original (uncompressed) size
return : the number of bytes read in the source buffer (in other words, the compressed size)
- If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction
- This function never writes outside of provided buffers, and never modifies input buffer.
- note : destination buffer must be already allocated.
- its size must be a minimum of 'osize' bytes.
+ If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction.
+ note : This function never writes outside of provided buffers, and never modifies input buffer.
+ Destination buffer must be already allocated.
+ Its size must be a minimum of 'output_size' bytes.
*/
diff --git a/lz4_format_description.txt b/lz4_format_description.txt index a170dde..888c57b 100644 --- a/lz4_format_description.txt +++ b/lz4_format_description.txt @@ -5,7 +5,7 @@ Author : Y. Collet This small specification intents to provide enough information
-to anyone willing to produce LZ4-compatible compressed streams
+to anyone willing to produce LZ4-compatible compressed data blocks
using any programming language.
LZ4 is an LZ77-type compressor with a fixed, byte-oriented encoding.
@@ -22,9 +22,9 @@ on implementation details of the compressor, and vice versa. --- Compressed stream format --
+-- Compressed block format --
-An LZ4 compressed stream is composed of sequences.
+An LZ4 compressed block is composed of sequences.
Schematically, a sequence is a suite of literals, followed by a match copy.
Each sequence starts with a token.
@@ -41,7 +41,7 @@ Each additionnal byte then represent a value from 0 to 255, which is added to the previous value to produce a total length.
When the byte value is 255, another byte is output.
There can be any number of bytes following the token. There is no "size limit".
-(Sidenote this is why a not-compressible input stream is expanded by 0.4%).
+(Sidenote this is why a not-compressible input block is expanded by 0.4%).
Example 1 : A length of 48 will be represented as :
- 15 : value for the 4-bits High field
@@ -64,8 +64,7 @@ It's possible that there are zero literal. Following the literals is the match copy operation.
It starts by the offset.
-This is a 2 bytes value, in little endian format :
-the lower byte is the first one in the stream.
+This is a 2 bytes value, in little endian format.
The offset represents the position of the match to be copied from.
1 means "current position - 1 byte".
@@ -96,8 +95,8 @@ and therefore start another one. There are specific parsing rules to respect in order to remain compatible
with assumptions made by the decoder :
1) The last 5 bytes are always literals
-2) The last match must start at least 12 bytes before end of stream
-Consequently, a file with less than 13 bytes cannot be compressed.
+2) The last match must start at least 12 bytes before end of block
+Consequently, a block with less than 13 bytes cannot be compressed.
These rules are in place to ensure that the decoder
will never read beyond the input buffer, nor write beyond the output buffer.
@@ -108,7 +107,7 @@ and stops right after literals. -- Additional notes --
There is no assumption nor limits to the way the compressor
-searches and selects matches within the source stream.
+searches and selects matches within the source data block.
It could be a fast scan, a multi-probe, a full search using BST,
standard hash chains or MMC, well whatever.
@@ -0,0 +1,799 @@ +/*
+ LZ4c - LZ4 Compression CLI program
+ Copyright (C) Yann Collet 2011-2013
+ 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 homepage : http://fastcompression.blogspot.com/p/lz4.html
+ - LZ4 source repository : http://code.google.com/p/lz4/
+*/
+/*
+ Note : this is stand-alone program.
+ It is not part of LZ4 compression library, it is a user program of LZ4 library.
+ The license of LZ4 is BSD.
+ The license of xxHash is BSD.
+ The license of the compression program is GPLv2.
+*/
+
+//**************************************
+// Compiler Options
+//**************************************
+// Disable some Visual warning messages
+#ifdef _MSC_VER // Visual Studio
+# define _CRT_SECURE_NO_WARNINGS
+# define _CRT_SECURE_NO_DEPRECATE // VS2005
+# pragma warning(disable : 4127) // disable: C4127: conditional expression is constant
+#endif
+
+
+//****************************
+// Includes
+//****************************
+#include <stdio.h> // fprintf, fopen, fread, _fileno(?)
+#include <stdlib.h> // malloc
+#include <string.h> // strcmp
+#include <time.h> // clock
+#ifdef _WIN32
+#include <io.h> // _setmode
+#include <fcntl.h> // _O_BINARY
+#endif
+#include "lz4.h"
+#include "lz4hc.h"
+#include "bench.h"
+#include "xxhash.h"
+
+
+//**************************************
+// Compiler-specific functions
+//**************************************
+#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
+
+#if defined(_MSC_VER) // Visual Studio
+# define swap32 _byteswap_ulong
+#elif GCC_VERSION >= 403
+# define swap32 __builtin_bswap32
+#else
+ static inline unsigned int swap32(unsigned int x) {
+ return ((x << 24) & 0xff000000 ) |
+ ((x << 8) & 0x00ff0000 ) |
+ ((x >> 8) & 0x0000ff00 ) |
+ ((x >> 24) & 0x000000ff );
+ }
+#endif
+
+
+//****************************
+// Constants
+//****************************
+#define COMPRESSOR_NAME "LZ4 Compression CLI"
+#define COMPRESSOR_VERSION ""
+#define COMPILED __DATE__
+#define AUTHOR "Yann Collet"
+#define EXTENSION ".lz4"
+#define WELCOME_MESSAGE "*** %s %s, by %s (%s) ***\n", COMPRESSOR_NAME, COMPRESSOR_VERSION, AUTHOR, COMPILED
+
+#define CACHELINE 64
+#define MAGICNUMBER_SIZE 4
+#define LZ4S_MAGICNUMBER 0x184D2204
+#define LZ4S_BLOCKSIZEID_DEFAULT 7
+#define LZ4S_CHECKSUM_SEED 0
+
+#define LEGACY_MAGICNUMBER 0x184C2102
+#define LEGACY_BLOCKSIZE (8<<20) // 8 MB
+
+#define _1BIT 1
+#define _2BITS 0x03
+#define _3BITS 0x07
+#define _4BITS 0x0F
+#define _8BITS 0xFF
+
+//**************************************
+// Architecture Macros
+//**************************************
+static const int one = 1;
+#define CPU_LITTLE_ENDIAN (*(char*)(&one))
+#define CPU_BIG_ENDIAN (!CPU_LITTLE_ENDIAN)
+#define LITTLE_ENDIAN_32(i) (CPU_LITTLE_ENDIAN?(i):swap32(i))
+
+
+//**************************************
+// Macros
+//**************************************
+#define DISPLAY(...) fprintf(stderr, __VA_ARGS__)
+
+
+//**************************************
+// Special input/output
+//**************************************
+#define NULL_INPUT "null"
+char stdinmark[] = "stdin";
+char stdoutmark[] = "stdout";
+#ifdef _WIN32
+char nulmark[] = "nul";
+#else
+char nulmark[] = "/dev/null";
+#endif
+
+
+//**************************************
+// Local Parameters
+//**************************************
+static int overwrite = 0;
+static int blockSizeId = LZ4S_BLOCKSIZEID_DEFAULT;
+static int blockChecksum = 1;
+
+
+//**************************************
+// Exceptions
+//**************************************
+#define DEBUG 0
+#define DEBUGOUTPUT(...) if (DEBUG) DISPLAY(__VA_ARGS__);
+#define EXM_THROW(error, ...) \
+{ \
+ DEBUGOUTPUT("Error defined at %s, line %i : \n", __FILE__, __LINE__); \
+ DISPLAY("Error %i : ", error); \
+ DISPLAY(__VA_ARGS__); \
+ DISPLAY("\n"); \
+ exit(error); \
+}
+
+
+
+//****************************
+// Functions
+//****************************
+int usage(char* exename)
+{
+ DISPLAY( "Usage :\n");
+ DISPLAY( " %s [arg] input output\n", exename);
+ DISPLAY( "Arguments :\n");
+ DISPLAY( " -c0/-c : Fast compression (default) \n");
+ DISPLAY( " -c1/-hc: High compression \n");
+ DISPLAY( " -B# : Block size [4-7](default:7)\n");
+ DISPLAY( " -x : disable checksum\n");
+ DISPLAY( " -y : overwrite without prompting \n");
+ DISPLAY( " -d : decompression \n");
+ DISPLAY( " -t : check compressed file \n");
+ DISPLAY( " -b# : benchmark files, using # [0-1] compression level\n");
+ DISPLAY( " -i# : nb of loops [1-9](default : 3), benchmark mode only\n");
+ DISPLAY( " -H : Help (this text)\n");
+ DISPLAY( "input : can be 'stdin' (pipe) or a filename\n");
+ DISPLAY( "output : can be 'stdout'(pipe) or a filename or 'null'\n");
+ return 0;
+}
+
+
+int badusage(char* exename)
+{
+ DISPLAY("Wrong parameters\n");
+ usage(exename);
+ return 0;
+}
+
+
+static int LZ4S_GetBlocksize_FromBlockId (int id) { return (1 << (8 + (2 * id))); }
+static unsigned int LZ4S_GetCheckBits_FromXXH (unsigned int xxh) { return (xxh >> 8) & _8BITS; }
+
+
+int get_fileHandle(char* input_filename, char* output_filename, FILE** pfinput, FILE** pfoutput)
+{
+
+ if (!strcmp (input_filename, stdinmark))
+ {
+ DISPLAY( "Using stdin for input\n");
+ *pfinput = stdin;
+#ifdef _WIN32 // Need to set stdin/stdout to binary mode specifically for windows
+ _setmode( _fileno( stdin ), _O_BINARY );
+#endif
+ }
+ else
+ {
+ *pfinput = fopen(input_filename, "rb");
+ }
+
+ if (!strcmp (output_filename, stdoutmark))
+ {
+ DISPLAY( "Using stdout for output\n");
+ *pfoutput = stdout;
+#ifdef _WIN32 // Need to set stdin/stdout to binary mode specifically for windows
+ _setmode( _fileno( stdout ), _O_BINARY );
+#endif
+ }
+ else
+ {
+ // Check if destination file already exists
+ *pfoutput=0;
+ if (output_filename != nulmark) *pfoutput = fopen( output_filename, "rb" );
+ if (*pfoutput!=0)
+ {
+ char ch;
+ fclose(*pfoutput);
+ DISPLAY( "Warning : %s already exists\n", output_filename);
+ if (!overwrite)
+ {
+ DISPLAY( "Overwrite ? (Y/N) : ");
+ ch = (char)getchar();
+ if (ch!='Y') EXM_THROW(11, "Operation aborted : %s already exists", output_filename);
+ }
+ }
+ *pfoutput = fopen( output_filename, "wb" );
+ }
+
+ if ( *pfinput==0 ) EXM_THROW(12, "Pb opening %s", input_filename);
+ if ( *pfoutput==0) EXM_THROW(13, "Pb opening %s", output_filename);
+
+ return 0;
+}
+
+
+
+int legacy_compress_file(char* input_filename, char* output_filename, int compressionlevel)
+{
+ int (*compressionFunction)(const char*, char*, int);
+ unsigned long long filesize = 0;
+ unsigned long long compressedfilesize = MAGICNUMBER_SIZE;
+ char* in_buff;
+ char* out_buff;
+ FILE* finput;
+ FILE* foutput;
+ int displayLevel = (compressionlevel>0);
+ clock_t start, end;
+ size_t sizeCheck;
+
+
+ // Init
+ switch (compressionlevel)
+ {
+ case 0 : compressionFunction = LZ4_compress; break;
+ case 1 : compressionFunction = LZ4_compressHC; break;
+ default : compressionFunction = LZ4_compress;
+ }
+ start = clock();
+ get_fileHandle(input_filename, output_filename, &finput, &foutput);
+
+ // Allocate Memory
+ in_buff = (char*)malloc(LEGACY_BLOCKSIZE);
+ out_buff = (char*)malloc(LZ4_compressBound(LEGACY_BLOCKSIZE));
+ if (!in_buff || !out_buff) EXM_THROW(21, "Allocation error : not enough memory");
+
+ // Write Archive Header
+ *(unsigned int*)out_buff = LITTLE_ENDIAN_32(LEGACY_MAGICNUMBER);
+ sizeCheck = fwrite(out_buff, 1, MAGICNUMBER_SIZE, foutput);
+ if (sizeCheck!=MAGICNUMBER_SIZE) EXM_THROW(22, "Write error : cannot write header");
+
+ // Main Loop
+ while (1)
+ {
+ unsigned int outSize;
+ // Read Block
+ int inSize = (int) fread(in_buff, (size_t)1, (size_t)LEGACY_BLOCKSIZE, finput);
+ if( inSize<=0 ) break;
+ filesize += inSize;
+ if (displayLevel) DISPLAY("Read : %i MB \r", (int)(filesize>>20));
+
+ // Compress Block
+ outSize = compressionFunction(in_buff, out_buff+4, inSize);
+ compressedfilesize += outSize+4;
+ if (displayLevel) DISPLAY("Read : %i MB ==> %.2f%%\r", (int)(filesize>>20), (double)compressedfilesize/filesize*100);
+
+ // Write Block
+ * (unsigned int*) out_buff = LITTLE_ENDIAN_32(outSize);
+ sizeCheck = fwrite(out_buff, 1, outSize+4, foutput);
+ if (sizeCheck!=(size_t)(outSize+4)) EXM_THROW(23, "Write error : cannot write compressed block");
+ }
+
+ // Status
+ end = clock();
+ DISPLAY( "Compressed %llu bytes into %llu bytes ==> %.2f%%\n",
+ (unsigned long long) filesize, (unsigned long long) compressedfilesize, (double)compressedfilesize/filesize*100);
+ {
+ double seconds = (double)(end - start)/CLOCKS_PER_SEC;
+ DISPLAY( "Done in %.2f s ==> %.2f MB/s\n", seconds, (double)filesize / seconds / 1024 / 1024);
+ }
+
+ // Close & Free
+ free(in_buff);
+ free(out_buff);
+ fclose(finput);
+ fclose(foutput);
+
+ return 0;
+}
+
+
+int compress_file(char* input_filename, char* output_filename, int compressionlevel)
+{
+ int (*compressionFunction)(const char*, char*, int);
+ unsigned long long filesize = 0;
+ unsigned long long compressedfilesize = 0;
+ unsigned int checkbits;
+ char* in_buff;
+ char* out_buff;
+ FILE* finput;
+ FILE* foutput;
+ int errorcode;
+ int displayLevel = (compressionlevel>0);
+ clock_t start, end;
+ int blockSize;
+ size_t sizeCheck, header_size;
+
+
+ // Init
+ start = clock();
+ switch (compressionlevel)
+ {
+ case 0 : compressionFunction = LZ4_compress; break;
+ case 1 : compressionFunction = LZ4_compressHC; break;
+ default : compressionFunction = LZ4_compress;
+ }
+ errorcode = get_fileHandle(input_filename, output_filename, &finput, &foutput);
+ if (errorcode) return errorcode;
+ blockSize = LZ4S_GetBlocksize_FromBlockId (blockSizeId);
+
+ // Allocate Memory
+ in_buff = (char*)malloc(blockSize);
+ out_buff = (char*)malloc(LZ4_compressBound(blockSize));
+ if (!in_buff || !out_buff) EXM_THROW(31, "Allocation error : not enough memory");
+
+ // Write Archive Header
+ *(unsigned int*)out_buff = LITTLE_ENDIAN_32(LZ4S_MAGICNUMBER); // Magic Number, in Little Endian convention
+ *(out_buff+4) = 0x60; // Version("01"), Block independence
+ *(out_buff+4) |= blockChecksum << 4;
+ *(out_buff+5) = (char)(blockSizeId<<4); // Block Size
+ checkbits = XXH32((out_buff+4), 2, LZ4S_CHECKSUM_SEED);
+ checkbits = LZ4S_GetCheckBits_FromXXH(checkbits);
+ *(out_buff+6) = (unsigned char) checkbits;
+ header_size = 7;
+ sizeCheck = fwrite(out_buff, 1, header_size, foutput);
+ if (sizeCheck!=header_size) EXM_THROW(32, "Write error : cannot write header");
+ compressedfilesize += header_size;
+
+ // Main Loop
+ while (1)
+ {
+ unsigned int outSize;
+ // Read Block
+ unsigned int inSize = (unsigned int) fread(in_buff, (size_t)1, (size_t)blockSize, finput);
+ if( inSize<=0 ) break;
+ filesize += inSize;
+ if (displayLevel) DISPLAY("Read : %i MB \r", (int)(filesize>>20));
+
+ // Compress Block
+ outSize = compressionFunction(in_buff, out_buff+4, inSize);
+ if (outSize < inSize) compressedfilesize += outSize+4; else compressedfilesize += inSize+4;
+ if (blockChecksum) compressedfilesize+=4;
+ if (displayLevel) DISPLAY("Read : %i MB ==> %.2f%%\r", (int)(filesize>>20), (double)compressedfilesize/filesize*100);
+
+ // Write Block
+ if (outSize < inSize)
+ {
+ unsigned int checksum;
+ int sizeToWrite;
+ * (unsigned int*) out_buff = LITTLE_ENDIAN_32(outSize);
+ if (blockChecksum)
+ {
+ checksum = XXH32(out_buff+4, outSize, LZ4S_CHECKSUM_SEED);
+ * (unsigned int*) (out_buff+4+outSize) = LITTLE_ENDIAN_32(checksum);
+ }
+ sizeToWrite = 4 + outSize + (4*blockChecksum);
+ sizeCheck = fwrite(out_buff, 1, sizeToWrite, foutput);
+ if (sizeCheck!=(size_t)(sizeToWrite)) EXM_THROW(33, "Write error : cannot write compressed block");
+
+ }
+ else // Copy Original
+ {
+ unsigned int checksum;
+ * (unsigned int*) out_buff = LITTLE_ENDIAN_32(inSize|0x80000000); // Add Uncompressed flag
+ sizeCheck = fwrite(out_buff, 1, 4, foutput);
+ if (sizeCheck!=(size_t)(4)) EXM_THROW(34, "Write error : cannot write block header");
+ sizeCheck = fwrite(in_buff, 1, inSize, foutput);
+ if (sizeCheck!=(size_t)(inSize)) EXM_THROW(35, "Write error : cannot write block");
+ if (blockChecksum)
+ {
+ checksum = XXH32(in_buff, inSize, LZ4S_CHECKSUM_SEED);
+ * (unsigned int*) out_buff = LITTLE_ENDIAN_32(checksum);
+ sizeCheck = fwrite(out_buff, 1, 4, foutput);
+ if (sizeCheck!=(size_t)(4)) EXM_THROW(36, "Write error : cannot write block checksum");
+ }
+ }
+ }
+
+ // End of Stream mark
+ * (unsigned int*) out_buff = 0;
+ sizeCheck = fwrite(out_buff, 1, 4, foutput);
+ if (sizeCheck!=(size_t)(4)) EXM_THROW(37, "Write error : cannot write end of stream");
+ compressedfilesize += 4;
+
+ // Status
+ end = clock();
+ DISPLAY( "Compressed %llu bytes into %llu bytes ==> %.2f%%\n",
+ (unsigned long long) filesize, (unsigned long long) compressedfilesize, (double)compressedfilesize/filesize*100);
+ {
+ double seconds = (double)(end - start)/CLOCKS_PER_SEC;
+ DISPLAY( "Done in %.2f s ==> %.2f MB/s\n", seconds, (double)filesize / seconds / 1024 / 1024);
+ }
+
+ // Close & Free
+ free(in_buff);
+ free(out_buff);
+ fclose(finput);
+ fclose(foutput);
+
+ return 0;
+}
+
+
+unsigned long long decodeLegacyStream(FILE* finput, FILE* foutput)
+{
+ unsigned long long filesize = 0;
+ char* in_buff;
+ char* out_buff;
+ size_t uselessRet;
+ int sinkint;
+ unsigned int blockSize;
+ size_t sizeCheck;
+
+
+ // Allocate Memory
+ in_buff = (char*)malloc(LZ4_compressBound(LEGACY_BLOCKSIZE));
+ out_buff = (char*)malloc(LEGACY_BLOCKSIZE);
+ if (!in_buff || !out_buff) EXM_THROW(51, "Allocation error : not enough memory");
+
+ // Main Loop
+ while (1)
+ {
+ // Block Size
+ uselessRet = fread(&blockSize, 1, 4, finput);
+ if( uselessRet==0 ) break; // Nothing to read : file read is completed
+ blockSize = LITTLE_ENDIAN_32(blockSize); // Convert to Little Endian
+ if (blockSize > LZ4_COMPRESSBOUND(LEGACY_BLOCKSIZE))
+ { // Cannot read next block : maybe new stream ?
+ fseek(finput, -4, SEEK_CUR);
+ break;
+ }
+
+ // Read Block
+ uselessRet = fread(in_buff, 1, blockSize, finput);
+
+ // Decode Block
+ sinkint = LZ4_uncompress_unknownOutputSize(in_buff, out_buff, blockSize, LEGACY_BLOCKSIZE);
+ if (sinkint < 0) EXM_THROW(52, "Decoding Failed ! Corrupted input detected !");
+ filesize += sinkint;
+
+ // Write Block
+ sizeCheck = fwrite(out_buff, 1, sinkint, foutput);
+ if (sizeCheck != (size_t)sinkint) EXM_THROW(53, "Write error : cannot write decoded block\n");
+ }
+
+ // Free
+ free(in_buff);
+ free(out_buff);
+
+ return filesize;
+}
+
+
+unsigned long long decodeLZ4S(FILE* finput, FILE* foutput)
+{
+ unsigned long long filesize = 0;
+ char* in_buff;
+ char* out_buff;
+ unsigned char descriptor[3];
+ size_t nbReadBytes;
+ int decodedBytes;
+ unsigned int maxBlockSize;
+ size_t sizeCheck;
+ int blockChecksumFlag;
+
+ // Decode stream descriptor
+ nbReadBytes = fread(descriptor, 1, 3, finput);
+ if (nbReadBytes != 3) EXM_THROW(61, "Unreadable header");
+ {
+ int version = (descriptor[0] >> 6) & _2BITS;
+ int independance = (descriptor[0] >> 5) & _1BIT;
+ int streamSize = (descriptor[0] >> 3) & _1BIT;
+ int reserved1 = (descriptor[0] >> 1) & _2BITS;
+ int dictionary = (descriptor[0] >> 0) & _1BIT;
+
+ int reserved2 = (descriptor[1] >> 7) & _1BIT;
+ int blockSizeId = (descriptor[1] >> 4) & _3BITS;
+ int reserved3 = (descriptor[1] >> 0) & _4BITS;
+ int checkBits = (descriptor[2] >> 0) & _8BITS;
+ int checkBits_xxh32;
+
+ blockChecksumFlag = (descriptor[0] >> 4) & _1BIT;
+
+ if (version != 1) EXM_THROW(62, "Wrong version number");
+ if (independance != 1) EXM_THROW(63, "Does not support block inter-dependence");
+ if (streamSize == 1) EXM_THROW(64, "Does not support stream size");
+ if (reserved1 != 0) EXM_THROW(65, "Wrong value for reserved bits");
+ if (dictionary == 1) EXM_THROW(66, "Does not support dictionary");
+ if (reserved2 != 0) EXM_THROW(67, "Wrong value for reserved bits");
+ if (blockSizeId < 4) EXM_THROW(68, "Unsupported block size");
+ if (reserved3 != 0) EXM_THROW(67, "Wrong value for reserved bits");
+ maxBlockSize = LZ4S_GetBlocksize_FromBlockId(blockSizeId);
+ // Checkbits verification
+ descriptor[1] &= 0xF0;
+ checkBits_xxh32 = XXH32(descriptor, 2, LZ4S_CHECKSUM_SEED);
+ checkBits_xxh32 = LZ4S_GetCheckBits_FromXXH(checkBits_xxh32);
+ if (checkBits != checkBits_xxh32) EXM_THROW(69, "Stream descriptor error detected");
+ }
+
+ // Allocate Memory
+ in_buff = (char*)malloc(maxBlockSize);
+ out_buff = (char*)malloc(maxBlockSize);
+ if (!in_buff || !out_buff) EXM_THROW(70, "Allocation error : not enough memory");
+
+ // Main Loop
+ while (1)
+ {
+ unsigned int blockSize, uncompressedFlag;
+
+ // Block Size
+ nbReadBytes = fread(&blockSize, 1, 4, finput);
+ if( nbReadBytes != 4 ) EXM_THROW(71, "Read error : cannot read next block size");
+ if (blockSize == 0) break; // End of Stream Mark : stream is completed
+ blockSize = LITTLE_ENDIAN_32(blockSize); // Convert to little endian
+ uncompressedFlag = blockSize >> 31;
+ blockSize &= 0x7FFFFFFF;
+ if (blockSize > maxBlockSize) EXM_THROW(72, "Error : invalid block size");
+
+ // Read Block
+ nbReadBytes = fread(in_buff, 1, blockSize, finput);
+ if( nbReadBytes != blockSize ) EXM_THROW(73, "Read error : cannot read data block" );
+
+ // Check Block
+ if (blockChecksumFlag)
+ {
+ unsigned int checksum = XXH32(in_buff, blockSize, LZ4S_CHECKSUM_SEED);
+ unsigned int readChecksum;
+ nbReadBytes = fread(&readChecksum, 1, 4, finput);
+ if( nbReadBytes != 4 ) EXM_THROW(74, "Read error : cannot read next block size");
+ readChecksum = LITTLE_ENDIAN_32(readChecksum); // Convert to little endian
+ if (checksum != readChecksum) EXM_THROW(75, "Error : invalid checksum detected");
+ }
+
+ if (uncompressedFlag)
+ {
+ // Write uncompressed Block
+ sizeCheck = fwrite(in_buff, 1, blockSize, foutput);
+ if (sizeCheck != (size_t)blockSize) EXM_THROW(76, "Write error : cannot write data block");
+ filesize += blockSize;
+ }
+ else
+ {
+ // Decode Block
+ decodedBytes = LZ4_uncompress_unknownOutputSize(in_buff, out_buff, blockSize, maxBlockSize);
+ if (decodedBytes < 0) EXM_THROW(77, "Decoding Failed ! Corrupted input detected !");
+ filesize += decodedBytes;
+
+ // Write Block
+ sizeCheck = fwrite(out_buff, 1, decodedBytes, foutput);
+ if (sizeCheck != (size_t)decodedBytes) EXM_THROW(78, "Write error : cannot write decoded block\n");
+ }
+ }
+
+ // Free
+ free(in_buff);
+ free(out_buff);
+
+ return filesize;
+}
+
+
+unsigned long long selectDecoder( FILE* finput, FILE* foutput)
+{
+ unsigned int magicNumber;
+ size_t nbReadBytes;
+
+ // Check Archive Header
+ nbReadBytes = fread(&magicNumber, 1, MAGICNUMBER_SIZE, finput);
+ if (nbReadBytes==0) return 0; // EOF
+ if (nbReadBytes != MAGICNUMBER_SIZE) EXM_THROW(41, "Unrecognized header : Magic Number unreadable");
+ magicNumber = LITTLE_ENDIAN_32(magicNumber); // Convert to Little Endian format
+ switch(magicNumber)
+ {
+ case LZ4S_MAGICNUMBER:
+ return decodeLZ4S(finput, foutput);
+ case LEGACY_MAGICNUMBER:
+ DISPLAY("Detected : Legacy format \n");
+ return decodeLegacyStream(finput, foutput);
+ default:
+ if (ftell(finput) == MAGICNUMBER_SIZE) EXM_THROW(42,"Unrecognized header : file cannot be decoded");
+ DISPLAY("Stream followed by unrecognized data\n");
+ return 0;
+ }
+}
+
+
+int decodeFile(char* input_filename, char* output_filename)
+{
+ unsigned long long filesize = 0, decodedSize=0;
+ FILE* finput;
+ FILE* foutput;
+ clock_t start, end;
+
+
+ // Init
+ start = clock();
+ get_fileHandle(input_filename, output_filename, &finput, &foutput);
+
+ // Loop over multiple streams
+ do
+ {
+ decodedSize = selectDecoder(finput, foutput);
+ filesize += decodedSize;
+ } while (decodedSize);
+
+ // Final Status
+ end = clock();
+ DISPLAY( "Successfully decoded %llu bytes \n", filesize);
+ {
+ double seconds = (double)(end - start)/CLOCKS_PER_SEC;
+ DISPLAY( "Done in %.2f s ==> %.2f MB/s\n", seconds, (double)filesize / seconds / 1024 / 1024);
+ }
+
+ // Close
+ fclose(finput);
+ fclose(foutput);
+
+ // Error status = OK
+ return 0;
+}
+
+
+int main(int argc, char** argv)
+{
+ int i,
+ cLevel=0,
+ decode=0,
+ bench=0,
+ filenamesStart=2,
+ legacy_format=0;
+ char* exename=argv[0];
+ char* input_filename=0;
+ char* output_filename=0;
+ char nullinput[] = NULL_INPUT;
+ char extension[] = EXTENSION;
+
+ // Welcome message
+ DISPLAY( WELCOME_MESSAGE);
+
+ if (argc<2) { badusage(exename); return 1; }
+
+ for(i=1; i<argc; i++)
+ {
+ char* argument = argv[i];
+
+ if(!argument) continue; // Protection if argument empty
+
+ // Decode command (note : aggregated commands are allowed)
+ if (argument[0]=='-')
+ {
+ while (argument[1]!=0)
+ {
+ argument ++;
+
+ switch(argument[0])
+ {
+ // Display help on usage
+ case 'H': usage(exename); return 0;
+
+ // Compression (default)
+ case 'c': if ((argument[1] >='0') && (argument[1] <='1')) { cLevel=argument[1] - '0'; argument++; } break;
+ case 'h': if (argument[1]=='c') { cLevel=1; argument++; } break;
+
+ // disable checksum
+ case 'x': blockChecksum=0; break;
+
+ // Use Legacy format (hidden option)
+ case 'l': legacy_format=1; break;
+
+ // Decoding
+ case 'd': decode=1; break;
+
+ // Bench
+ case 'b': bench=1;
+ if ((argument[1] >='0') && (argument[1] <='1')) { cLevel=argument[1] - '0'; argument++; }
+ break;
+
+ // Modify Block Size
+ case 'B':
+ if ((argument[1] >='4') && (argument[1] <='7'))
+ {
+ int B = argument[1] - '0';
+ int S = 1 << (8 + 2*B);
+ BMK_SetBlocksize(S);
+ blockSizeId = B;
+ argument++;
+ }
+ break;
+
+ // Modify Nb Iterations (benchmark only)
+ case 'i':
+ if ((argument[1] >='1') && (argument[1] <='9'))
+ {
+ int iters = argument[1] - '0';
+ BMK_SetNbIterations(iters);
+ argument++;
+ }
+ break;
+
+ // Pause at the end (benchmark only) (hidden option)
+ case 'p': BMK_SetPause(); break;
+
+ // Test
+ case 't': decode=1; output_filename=nulmark; break;
+
+ // Overwrite
+ case 'y': overwrite=1; break;
+
+ // Unrecognised command
+ default : badusage(exename); return 1;
+ }
+ }
+ continue;
+ }
+
+ // first provided filename is input
+ if (!input_filename) { input_filename=argument; filenamesStart=i; continue; }
+
+ // second provided filename is output
+ if (!output_filename)
+ {
+ output_filename=argument;
+ if (!strcmp (output_filename, nullinput)) output_filename = nulmark;
+ continue;
+ }
+ }
+
+ // No input filename ==> Error
+ if(!input_filename) { badusage(exename); return 1; }
+
+ if (bench) return BMK_benchFile(argv+filenamesStart, argc-filenamesStart, cLevel);
+
+ // No output filename ==> build one automatically (for compression only)
+ if (!output_filename)
+ {
+ if (!decode)
+ {
+ int i=0, l=0;
+ while (input_filename[l]!=0) l++;
+ output_filename = (char*)calloc(1,l+5);
+ for (i=0;i<l;i++) output_filename[i] = input_filename[i];
+ for (i=l;i<l+4;i++) output_filename[i] = extension[i-l];
+ }
+ else
+ {
+ badusage(exename);
+ return 1;
+ }
+ }
+
+ if (decode) return decodeFile(input_filename, output_filename);
+
+ // compression is default action
+ if (legacy_format)
+ {
+ DISPLAY("! Generating compressed LZ4 using Legacy format (deprecated !) ! \n");
+ return legacy_compress_file(input_filename, output_filename, cLevel);
+ }
+ else
+ {
+ return compress_file(input_filename, output_filename, cLevel);
+ }
+}
diff --git a/lz4demo.c b/lz4demo.c deleted file mode 100644 index 9103c8b..0000000 --- a/lz4demo.c +++ /dev/null @@ -1,482 +0,0 @@ -/*
- LZ4Demo - Demo CLI program using LZ4 compression
- Copyright (C) Yann Collet 2011-2012
- 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 homepage : http://fastcompression.blogspot.com/p/lz4.html
- - LZ4 source repository : http://code.google.com/p/lz4/
-*/
-/*
- Note : this is *only* a demo program, an example to show how LZ4 can be used.
- It is not considered part of LZ4 compression library.
- The license of LZ4 is BSD.
- The license of the demo program is GPL.
-*/
-
-//**************************************
-// Compiler Options
-//**************************************
-// Disable some Visual warning messages
-#define _CRT_SECURE_NO_WARNINGS
-#define _CRT_SECURE_NO_DEPRECATE // VS2005
-
-
-//****************************
-// Includes
-//****************************
-#include <stdio.h> // fprintf, fopen, fread, _fileno(?)
-#include <stdlib.h> // malloc
-#include <string.h> // strcmp
-#include <time.h> // clock
-#ifdef _WIN32
-#include <io.h> // _setmode
-#include <fcntl.h> // _O_BINARY
-#endif
-#include "lz4.h"
-#include "lz4hc.h"
-#include "bench.h"
-
-
-//**************************************
-// Compiler-specific functions
-//**************************************
-#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
-
-#if defined(_MSC_VER) // Visual Studio
-#define swap32 _byteswap_ulong
-#elif GCC_VERSION >= 403
-#define swap32 __builtin_bswap32
-#else
-static inline unsigned int swap32(unsigned int x) {
- return ((x << 24) & 0xff000000 ) |
- ((x << 8) & 0x00ff0000 ) |
- ((x >> 8) & 0x0000ff00 ) |
- ((x >> 24) & 0x000000ff );
-}
-#endif
-
-
-//****************************
-// Constants
-//****************************
-#define COMPRESSOR_NAME "Compression CLI using LZ4 algorithm"
-#define COMPRESSOR_VERSION ""
-#define COMPILED __DATE__
-#define AUTHOR "Yann Collet"
-#define EXTENSION ".lz4"
-#define WELCOME_MESSAGE "*** %s %s, by %s (%s) ***\n", COMPRESSOR_NAME, COMPRESSOR_VERSION, AUTHOR, COMPILED
-
-#define CHUNKSIZE (8<<20) // 8 MB
-#define CACHELINE 64
-#define ARCHIVE_MAGICNUMBER 0x184C2102
-#define ARCHIVE_MAGICNUMBER_SIZE 4
-
-
-//**************************************
-// Architecture Macros
-//**************************************
-static const int one = 1;
-#define CPU_LITTLE_ENDIAN (*(char*)(&one))
-#define CPU_BIG_ENDIAN (!CPU_LITTLE_ENDIAN)
-#define LITTLE_ENDIAN32(i) if (CPU_BIG_ENDIAN) { i = swap32(i); }
-
-
-//**************************************
-// Macros
-//**************************************
-#define DISPLAY(...) fprintf(stderr, __VA_ARGS__)
-
-
-//**************************************
-// Special input/output
-//**************************************
-#define NULL_INPUT "null"
-char stdinmark[] = "stdin";
-char stdoutmark[] = "stdout";
-#ifdef _WIN32
-char nulmark[] = "nul";
-#else
-char nulmark[] = "/dev/null";
-#endif
-
-
-//**************************************
-// I/O Parameters
-//**************************************
-static int overwrite = 0;
-
-
-
-//****************************
-// Functions
-//****************************
-int usage(char* exename)
-{
- DISPLAY( "Usage :\n");
- DISPLAY( " %s [arg] input output\n", exename);
- DISPLAY( "Arguments :\n");
- DISPLAY( " -c0/-c : Fast compression (default) \n");
- DISPLAY( " -c1/-hc: High compression \n");
- DISPLAY( " -d : decompression \n");
- DISPLAY( " -y : overwrite output \n");
- DISPLAY( " -t : check compressed file \n");
- DISPLAY( " -b# : Benchmark files, using # compression level\n");
- DISPLAY( " -H : help (this text)\n");
- DISPLAY( "input : can be 'stdin' (pipe) or a filename\n");
- DISPLAY( "output : can be 'stdout'(pipe) or a filename or 'null'\n");
- return 0;
-}
-
-
-int badusage(char* exename)
-{
- DISPLAY("Wrong parameters\n");
- usage(exename);
- return 0;
-}
-
-
-int get_fileHandle(char* input_filename, char* output_filename, FILE** pfinput, FILE** pfoutput)
-{
-
- if (!strcmp (input_filename, stdinmark))
- {
- DISPLAY( "Using stdin for input\n");
- *pfinput = stdin;
-#ifdef _WIN32 // Need to set stdin/stdout to binary mode specifically for windows
- _setmode( _fileno( stdin ), _O_BINARY );
-#endif
- }
- else
- {
- *pfinput = fopen(input_filename, "rb");
- }
-
- if (!strcmp (output_filename, stdoutmark))
- {
- DISPLAY( "Using stdout for output\n");
- *pfoutput = stdout;
-#ifdef _WIN32 // Need to set stdin/stdout to binary mode specifically for windows
- _setmode( _fileno( stdout ), _O_BINARY );
-#endif
- }
- else
- {
- // Check if destination file already exists
- *pfoutput=0;
- if (output_filename != nulmark) *pfoutput = fopen( output_filename, "rb" );
- if (*pfoutput!=0)
- {
- char ch;
- fclose(*pfoutput);
- DISPLAY( "Warning : %s already exists\n", output_filename);
- if (!overwrite)
- {
- DISPLAY( "Overwrite ? (Y/N) : ");
- ch = getchar();
- if (ch!='Y') { DISPLAY( "Operation aborted : %s already exists\n", output_filename); return 12; }
- }
- }
- *pfoutput = fopen( output_filename, "wb" );
- }
-
- if ( *pfinput==0 ) { DISPLAY( "Pb opening %s\n", input_filename); return 13; }
- if ( *pfoutput==0) { DISPLAY( "Pb opening %s\n", output_filename); return 14; }
-
- return 0;
-}
-
-
-
-int compress_file(char* input_filename, char* output_filename, int compressionlevel)
-{
- int (*compressionFunction)(const char*, char*, int);
- unsigned long long filesize = 0;
- unsigned long long compressedfilesize = ARCHIVE_MAGICNUMBER_SIZE;
- unsigned int u32var;
- char* in_buff;
- char* out_buff;
- FILE* finput;
- FILE* foutput;
- int r;
- int displayLevel = (compressionlevel>0);
- clock_t start, end;
- size_t sizeCheck;
-
-
- // Init
- switch (compressionlevel)
- {
- case 0 : compressionFunction = LZ4_compress; break;
- case 1 : compressionFunction = LZ4_compressHC; break;
- default : compressionFunction = LZ4_compress;
- }
- start = clock();
- r = get_fileHandle(input_filename, output_filename, &finput, &foutput);
- if (r) return r;
-
- // Allocate Memory
- in_buff = (char*)malloc(CHUNKSIZE);
- out_buff = (char*)malloc(LZ4_compressBound(CHUNKSIZE));
- if (!in_buff || !out_buff) { DISPLAY("Allocation error : not enough memory\n"); return 21; }
-
- // Write Archive Header
- u32var = ARCHIVE_MAGICNUMBER;
- LITTLE_ENDIAN32(u32var);
- *(unsigned int*)out_buff = u32var;
- sizeCheck = fwrite(out_buff, 1, ARCHIVE_MAGICNUMBER_SIZE, foutput);
- if (sizeCheck!=ARCHIVE_MAGICNUMBER_SIZE) { DISPLAY("write error\n"); return 22; }
-
- // Main Loop
- while (1)
- {
- int outSize;
- // Read Block
- int inSize = (int) fread(in_buff, (size_t)1, (size_t)CHUNKSIZE, finput);
- if( inSize<=0 ) break;
- filesize += inSize;
- if (displayLevel) DISPLAY("Read : %i MB \r", (int)(filesize>>20));
-
- // Compress Block
- outSize = compressionFunction(in_buff, out_buff+4, inSize);
- compressedfilesize += outSize+4;
- if (displayLevel) DISPLAY("Read : %i MB ==> %.2f%%\r", (int)(filesize>>20), (double)compressedfilesize/filesize*100);
-
- // Write Block
- LITTLE_ENDIAN32(outSize);
- * (unsigned int*) out_buff = outSize;
- LITTLE_ENDIAN32(outSize);
- sizeCheck = fwrite(out_buff, 1, outSize+4, foutput);
- if (sizeCheck!=(size_t)(outSize+4)) { DISPLAY("write error\n"); return 11; }
- }
-
- // Status
- end = clock();
- DISPLAY( "Compressed %llu bytes into %llu bytes ==> %.2f%%\n",
- (unsigned long long) filesize, (unsigned long long) compressedfilesize, (double)compressedfilesize/filesize*100);
- {
- double seconds = (double)(end - start)/CLOCKS_PER_SEC;
- DISPLAY( "Done in %.2f s ==> %.2f MB/s\n", seconds, (double)filesize / seconds / 1024 / 1024);
- }
-
- // Close & Free
- free(in_buff);
- free(out_buff);
- fclose(finput);
- fclose(foutput);
-
- return 0;
-}
-
-
-int decode_file(char* input_filename, char* output_filename)
-{
- unsigned long long filesize = 0;
- char* in_buff;
- char* out_buff;
- size_t uselessRet;
- int sinkint;
- unsigned int chunkSize;
- FILE* finput;
- FILE* foutput;
- clock_t start, end;
- int r;
- size_t sizeCheck;
-
-
- // Init
- start = clock();
- r = get_fileHandle(input_filename, output_filename, &finput, &foutput);
- if (r) return r;
-
- // Allocate Memory
- in_buff = (char*)malloc(LZ4_compressBound(CHUNKSIZE));
- out_buff = (char*)malloc(CHUNKSIZE);
- if (!in_buff || !out_buff) { DISPLAY("Allocation error : not enough memory\n"); return 31; }
-
- // Check Archive Header
- chunkSize = 0;
- uselessRet = fread(&chunkSize, 1, ARCHIVE_MAGICNUMBER_SIZE, finput);
- LITTLE_ENDIAN32(chunkSize);
- if (chunkSize != ARCHIVE_MAGICNUMBER) { DISPLAY("Unrecognized header : file cannot be decoded\n"); return 32; }
-
- // Main Loop
- while (1)
- {
- // Block Size
- uselessRet = fread(&chunkSize, 1, 4, finput);
- if( uselessRet==0 ) break; // Nothing to read : file read is completed
- LITTLE_ENDIAN32(chunkSize);
- if (chunkSize == ARCHIVE_MAGICNUMBER)
- continue; // appended compressed stream
-
- // Read Block
- uselessRet = fread(in_buff, 1, chunkSize, finput);
-
- // Decode Block
- sinkint = LZ4_uncompress_unknownOutputSize(in_buff, out_buff, chunkSize, CHUNKSIZE);
- if (sinkint < 0) { DISPLAY("Decoding Failed ! Corrupted input !\n"); return 33; }
- filesize += sinkint;
-
- // Write Block
- sizeCheck = fwrite(out_buff, 1, sinkint, foutput);
- if (sizeCheck != (size_t)sinkint) { DISPLAY("write error\n"); return 34; }
- }
-
- // Status
- end = clock();
- DISPLAY( "Successfully decoded %llu bytes \n", (unsigned long long)filesize);
- {
- double seconds = (double)(end - start)/CLOCKS_PER_SEC;
- DISPLAY( "Done in %.2f s ==> %.2f MB/s\n", seconds, (double)filesize / seconds / 1024 / 1024);
- }
-
- // Close & Free
- free(in_buff);
- free(out_buff);
- fclose(finput);
- fclose(foutput);
-
- return 0;
-}
-
-
-int main(int argc, char** argv)
-{
- int i,
- cLevel=0,
- decode=0,
- bench=0,
- filenamesStart=2;
- char* exename=argv[0];
- char* input_filename=0;
- char* output_filename=0;
- char nullinput[] = NULL_INPUT;
- char extension[] = EXTENSION;
-
- // Welcome message
- DISPLAY( WELCOME_MESSAGE);
-
- if (argc<2) { badusage(exename); return 1; }
-
- for(i=1; i<argc; i++)
- {
- char* argument = argv[i];
-
- if(!argument) continue; // Protection if argument empty
-
- // Decode command (note : aggregated commands are allowed)
- if (argument[0]=='-')
- {
- while (argument[1]!=0)
- {
- argument ++;
-
- switch(argument[0])
- {
- // Display help on usage
- case 'H': usage(exename); return 0;
-
- // Compression (default)
- case 'c': if ((argument[1] >='0') && (argument[1] <='1')) { cLevel=argument[1] - '0'; argument++; } break;
- case 'h': if (argument[1]=='c') { cLevel=1; argument++; } break;
-
- // Decoding
- case 'd': decode=1; break;
-
- // Bench
- case 'b': bench=1;
- if ((argument[1] >='0') && (argument[1] <='1')) { cLevel=argument[1] - '0'; argument++; }
- break;
-
- // Modify Block Size (benchmark only)
- case 'B':
- if ((argument[1] >='0') && (argument[1] <='9'))
- {
- int B = argument[1] - '0';
- int S = 1 << (10 + 2*B); BMK_SetBlocksize(S);
- argument++;
- }
- break;
-
- // Modify Nb Iterations (benchmark only)
- case 'i':
- if ((argument[1] >= '0') && (argument[1] <= '9'))
- {
- int iters = argument[1] - '0';
- BMK_SetNbIterations(iters);
- argument++;
- }
- break;
-
- // Pause at the end (benchmark only)
- case 'p': BMK_SetPause(); break;
-
- // Test
- case 't': decode=1; output_filename=nulmark; break;
-
- // Overwrite
- case 'y': overwrite=1; break;
-
- // Unrecognised command
- default : badusage(exename); return 1;
- }
- }
- continue;
- }
-
- // first provided filename is input
- if (!input_filename) { input_filename=argument; filenamesStart=i; continue; }
-
- // second provided filename is output
- if (!output_filename)
- {
- output_filename=argument;
- if (!strcmp (output_filename, nullinput)) output_filename = nulmark;
- continue;
- }
- }
-
- // No input filename ==> Error
- if(!input_filename) { badusage(exename); return 1; }
-
- if (bench) return BMK_benchFile(argv+filenamesStart, argc-filenamesStart, cLevel);
-
- // No output filename ==> build one automatically (for compression only)
- if (!output_filename)
- {
- if (!decode)
- {
- int i=0, l=0;
- while (input_filename[l]!=0) l++;
- output_filename = (char*)calloc(1,l+5);
- for (i=0;i<l;i++) output_filename[i] = input_filename[i];
- for (i=l;i<l+4;i++) output_filename[i] = extension[i-l];
- }
- else
- {
- badusage(exename);
- return 1;
- }
- }
-
- if (decode) return decode_file(input_filename, output_filename);
-
- return compress_file(input_filename, output_filename, cLevel); // Compression is 'default' action
-
-}
@@ -1,6 +1,6 @@ /*
LZ4 HC - High Compression Mode of LZ4
- Copyright (C) 2011-2012, Yann Collet.
+ Copyright (C) 2011-2013, 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
@@ -93,6 +93,8 @@ # pragma intrinsic(_BitScanForward) // For Visual 2005
# pragma intrinsic(_BitScanReverse) // For Visual 2005
# endif
+# pragma warning(disable : 4127) // disable: C4127: conditional expression is constant
+# pragma warning(disable : 4701) // disable: C4701: potentially uninitialized local variable used
#else
# ifdef __GNUC__
# define forceinline inline __attribute__((always_inline))
@@ -346,7 +348,7 @@ forceinline static void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) size_t delta = (p) - HASH_POINTER(p);
if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
DELTANEXT(p) = (U16)delta;
- HashTable[HASH_VALUE(p)] = (p) - base;
+ HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base);
hc4->nextToUpdate++;
}
}
@@ -427,7 +429,7 @@ forceinline static int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, do
{
DELTANEXT(ptr) = delta;
- HashTable[HASH_VALUE(ptr)] = (ptr) - base; // Head of chain
+ HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); // Head of chain
ptr++;
} while(ptr < end);
hc4->nextToUpdate = end;
@@ -506,7 +508,7 @@ forceinline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE length = (int)(*ip - *anchor);
token = (*op)++;
if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; }
- else *token = (length<<ML_BITS);
+ else *token = (BYTE)(length<<ML_BITS);
// Copy Literals
LZ4_BLINDCOPY(*anchor, *op, length);
@@ -517,7 +519,7 @@ forceinline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE // Encode MatchLength
len = (int)(ml-MINMATCH);
if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (len > 254) { len-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)len; }
- else *token += len;
+ else *token += (BYTE)len;
// Prepare next loop
*ip += ml;
@@ -706,7 +708,7 @@ _Search3: {
int lastRun = (int)(iend - anchor);
if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
- else *op++ = (lastRun<<ML_BITS);
+ else *op++ = (BYTE)(lastRun<<ML_BITS);
memcpy(op, anchor, iend - anchor);
op += iend-anchor;
}
@@ -1,7 +1,7 @@ /*
LZ4 HC - High Compression Mode of LZ4
Header File
- Copyright (C) 2011-2012, Yann Collet.
+ Copyright (C) 2011-2013, 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
diff --git a/xxhash.c b/xxhash.c new file mode 100644 index 0000000..95a7955 --- /dev/null +++ b/xxhash.c @@ -0,0 +1,344 @@ +/*
+ xxHash - Fast Hash algorithm
+ Copyright (C) 2012, 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
+//**************************************
+// FORCE_NATIVE_FORMAT :
+// By default, xxHash library provides endian-independant Hash values.
+// Results are therefore identical for big-endian and little-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 to your application, you may uncomment the #define below
+// It will improve speed for Big-endian CPU.
+// This option has no impact on Little_Endian CPU.
+//#define FORCE_NATIVE_FORMAT 1
+
+
+
+//**************************************
+// Includes
+//**************************************
+#include <stdlib.h> // for malloc(), free()
+#include <string.h> // for memcpy()
+#include "xxhash.h"
+
+
+
+//**************************************
+// CPU Feature Detection
+//**************************************
+// Little Endian or Big Endian ?
+// You can overwrite the #define below if you know your architecture endianess
+#if defined(FORCE_NATIVE_FORMAT) && (FORCE_NATIVE_FORMAT==1)
+// Force native format. The result will be endian dependant.
+# define XXH_BIG_ENDIAN 0
+#elif defined (__GLIBC__)
+# include <endian.h>
+# if (__BYTE_ORDER == __BIG_ENDIAN)
+# define XXH_BIG_ENDIAN 1
+# endif
+#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
+# define XXH_BIG_ENDIAN 1
+#elif defined(__sparc) || defined(__sparc__) \
+ || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \
+ || defined(__hpux) || defined(__hppa) \
+ || defined(_MIPSEB) || defined(__s390__)
+# define XXH_BIG_ENDIAN 1
+#endif
+
+#if !defined(XXH_BIG_ENDIAN)
+// Little Endian assumed. PDP Endian and other very rare endian format are unsupported.
+# define XXH_BIG_ENDIAN 0
+#endif
+
+
+
+//**************************************
+// Compiler-specific Options & Functions
+//**************************************
+#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
+
+// Note : under GCC, it may sometimes be faster to enable the (2nd) macro definition, instead of using win32 intrinsic
+#if defined(_WIN32)
+# define XXH_rotl32(x,r) _rotl(x,r)
+#else
+# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
+#endif
+
+#if defined(_MSC_VER) // Visual Studio
+# define XXH_swap32 _byteswap_ulong
+#elif GCC_VERSION >= 403
+# define XXH_swap32 __builtin_bswap32
+#else
+static inline unsigned int XXH_swap32 (unsigned int x) {
+ return ((x << 24) & 0xff000000 ) |
+ ((x << 8) & 0x00ff0000 ) |
+ ((x >> 8) & 0x0000ff00 ) |
+ ((x >> 24) & 0x000000ff );
+ }
+#endif
+
+
+
+//**************************************
+// Constants
+//**************************************
+#define PRIME32_1 2654435761U
+#define PRIME32_2 2246822519U
+#define PRIME32_3 3266489917U
+#define PRIME32_4 668265263U
+#define PRIME32_5 374761393U
+
+
+
+//**************************************
+// Macros
+//**************************************
+#define XXH_LE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(*(unsigned int*)(p)) : *(unsigned int*)(p))
+
+
+
+//****************************
+// Simple Hash Functions
+//****************************
+
+unsigned int XXH32(const void* input, int len, unsigned int seed)
+{
+#if 1
+ // 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
+
+ const unsigned char* p = (const unsigned char*)input;
+ const unsigned char* const bEnd = p + len;
+ unsigned int h32;
+
+ if (len>=16)
+ {
+ const unsigned char* const limit = bEnd - 16;
+ unsigned int v1 = seed + PRIME32_1 + PRIME32_2;
+ unsigned int v2 = seed + PRIME32_2;
+ unsigned int v3 = seed + 0;
+ unsigned int v4 = seed - PRIME32_1;
+
+ do
+ {
+ v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
+ v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
+ v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
+ v4 += XXH_LE32(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 += (unsigned int) len;
+
+ while (p<=bEnd-4)
+ {
+ h32 += XXH_LE32(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;
+
+#endif
+}
+
+
+//****************************
+// Advanced Hash Functions
+//****************************
+
+struct XXH_state32_t
+{
+ unsigned int seed;
+ unsigned int v1;
+ unsigned int v2;
+ unsigned int v3;
+ unsigned int v4;
+ unsigned long long total_len;
+ char memory[16];
+ int memsize;
+};
+
+
+void* XXH32_init (unsigned int seed)
+{
+ struct XXH_state32_t * state = (struct XXH_state32_t *) malloc ( sizeof(struct XXH_state32_t));
+ 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 (void*)state;
+}
+
+
+XXH_errorcode XXH32_update (void* state_in, const void* input, int len)
+{
+ struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
+ const unsigned char* p = (const unsigned char*)input;
+ const unsigned char* const bEnd = p + len;
+
+ if (input==NULL) return XXH_ERROR;
+
+ state->total_len += len;
+
+ if (state->memsize + len < 16) // fill in tmp buffer
+ {
+ memcpy(state->memory + state->memsize, input, len);
+ state->memsize += len;
+ return OK;
+ }
+
+ if (state->memsize) // some data left from previous update
+ {
+ memcpy(state->memory + state->memsize, input, 16-state->memsize);
+ {
+ const unsigned int* p32 = (const unsigned int*)state->memory;
+ state->v1 += XXH_LE32(p32) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
+ state->v2 += XXH_LE32(p32) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
+ state->v3 += XXH_LE32(p32) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
+ state->v4 += XXH_LE32(p32) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
+ }
+ p += 16-state->memsize;
+ state->memsize = 0;
+ }
+
+ {
+ const unsigned char* const limit = bEnd - 16;
+ unsigned int v1 = state->v1;
+ unsigned int v2 = state->v2;
+ unsigned int v3 = state->v3;
+ unsigned int v4 = state->v4;
+
+ while (p<=limit)
+ {
+ v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
+ v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
+ v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
+ v4 += XXH_LE32(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
+ }
+
+ state->v1 = v1;
+ state->v2 = v2;
+ state->v3 = v3;
+ state->v4 = v4;
+ }
+
+ if (p < bEnd)
+ {
+ memcpy(state->memory, p, bEnd-p);
+ state->memsize = (int)(bEnd-p);
+ }
+
+ return OK;
+}
+
+
+unsigned int XXH32_intermediateDigest (void* state_in)
+{
+ struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
+ unsigned char * p = (unsigned char*)state->memory;
+ unsigned char* bEnd = (unsigned char*)state->memory + state->memsize;
+ unsigned int 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 += (unsigned int) state->total_len;
+
+ while (p<=bEnd-4)
+ {
+ h32 += XXH_LE32(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;
+}
+
+
+unsigned int XXH32_digest (void* state_in)
+{
+ unsigned int h32 = XXH32_intermediateDigest(state_in);
+
+ free(state_in);
+
+ return h32;
+}
diff --git a/xxhash.h b/xxhash.h new file mode 100644 index 0000000..a1d9dee --- /dev/null +++ b/xxhash.h @@ -0,0 +1,147 @@ +/*
+ xxHash - Fast Hash algorithm
+ Header File
+ Copyright (C) 2012, 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 { OK=0, XXH_ERROR } XXH_errorcode;
+
+
+
+//****************************
+// Simple Hash Functions
+//****************************
+
+unsigned int XXH32 (const void* input, int len, unsigned int 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.
+*/
+
+
+
+//****************************
+// Advanced Hash Functions
+//****************************
+
+void* XXH32_init (unsigned int seed);
+XXH_errorcode XXH32_update (void* state, const void* input, int len);
+unsigned int XXH32_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* XXH32_init()
+The function returns a pointer which holds the state of calculation.
+
+This pointer must be provided as "void* state" parameter for XXH32_update().
+XXH32_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 XXH32_digest().
+This function returns the final 32-bits hash.
+You must provide the same "void* state" parameter created by XXH32_init().
+Memory will be freed by XXH32_digest().
+*/
+
+
+unsigned int XXH32_intermediateDigest (void* state);
+/*
+This function does the same as XXH32_digest(), generating a 32-bit hash,
+but preserve memory context.
+This way, it becomes possible to generate intermediate hashes, and then continue feeding data with XXH32_update().
+To free memory context, use XXH32_digest().
+*/
+
+
+
+//****************************
+// Deprecated function names
+//****************************
+// The following translations are provided to ease code transition
+// You are encouraged to no longer this function names
+#define XXH32_feed XXH32_update
+#define XXH32_result XXH32_digest
+#define XXH32_getIntermediateResult XXH32_intermediateDigest
+
+
+
+#if defined (__cplusplus)
+}
+#endif
|