Repository: hadoop Updated Branches: refs/heads/trunk 6039059c3 -> 4c061e607
http://git-wip-us.apache.org/repos/asf/hadoop/blob/4c061e60/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4.h ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4.h b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4.h index 44ada14..3e74002 100644 --- a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4.h +++ b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4.h @@ -1,7 +1,8 @@ /* LZ4 - Fast LZ compression algorithm Header File - Copyright (C) 2011-2014, Yann Collet. + Copyright (C) 2011-2015, 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 @@ -28,7 +29,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. You can contact the author at : - - LZ4 source repository : http://code.google.com/p/lz4/ + - LZ4 source repository : https://github.com/Cyan4973/lz4 - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c */ #pragma once @@ -38,22 +39,22 @@ extern "C" { #endif /* - * lz4.h provides raw compression format functions, for optimal performance and integration into programs. - * If you need to generate data using an inter-operable format (respecting the framing specification), - * please use lz4frame.h instead. + * lz4.h provides block compression functions, and gives full buffer control to programmer. + * If you need to generate inter-operable compressed data (respecting LZ4 frame specification), + * and can let the library handle its own memory, please use lz4frame.h instead. */ /************************************** - Version +* Version **************************************/ -#define LZ4_VERSION_MAJOR 1 /* for major interface/format changes */ -#define LZ4_VERSION_MINOR 3 /* for minor interface/format changes */ +#define LZ4_VERSION_MAJOR 1 /* for breaking interface changes */ +#define LZ4_VERSION_MINOR 7 /* for new (non-breaking) interface capabilities */ #define LZ4_VERSION_RELEASE 1 /* for tweaks, bug-fixes, or development */ #define LZ4_VERSION_NUMBER (LZ4_VERSION_MAJOR *100*100 + LZ4_VERSION_MINOR *100 + LZ4_VERSION_RELEASE) int LZ4_versionNumber (void); /************************************** - Tuning parameter +* Tuning parameter **************************************/ /* * LZ4_MEMORY_USAGE : @@ -66,77 +67,90 @@ int LZ4_versionNumber (void); /************************************** - Simple Functions +* Simple Functions **************************************/ -int LZ4_compress (const char* source, char* dest, int sourceSize); +int LZ4_compress_default(const char* source, char* dest, int sourceSize, int maxDestSize); int LZ4_decompress_safe (const char* source, char* dest, int compressedSize, int maxDecompressedSize); /* -LZ4_compress() : - Compresses 'sourceSize' 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() - inputSize : Max supported value is LZ4_MAX_INPUT_SIZE - return : the number of bytes written in buffer dest - or 0 if the compression fails +LZ4_compress_default() : + Compresses 'sourceSize' bytes from buffer 'source' + into already allocated 'dest' buffer of size 'maxDestSize'. + Compression is guaranteed to succeed if 'maxDestSize' >= LZ4_compressBound(sourceSize). + It also runs faster, so it's a recommended setting. + If the function cannot compress 'source' into a more limited 'dest' budget, + compression stops *immediately*, and the function result is zero. + As a consequence, 'dest' content is not valid. + This function never writes outside 'dest' buffer, nor read outside 'source' buffer. + sourceSize : Max supported value is LZ4_MAX_INPUT_VALUE + maxDestSize : full or partial size of buffer 'dest' (which must be already allocated) + return : the number of bytes written into buffer 'dest' (necessarily <= maxOutputSize) + or 0 if compression fails LZ4_decompress_safe() : - compressedSize : is obviously the source size - maxDecompressedSize : is the size of the destination buffer, which must be already allocated. - return : the number of bytes decompressed into the destination buffer (necessarily <= maxDecompressedSize) - If the destination buffer is not large enough, decoding will stop and output an error code (<0). + compressedSize : is the precise full size of the compressed block. + maxDecompressedSize : is the size of destination buffer, which must be already allocated. + return : the number of bytes decompressed into destination buffer (necessarily <= maxDecompressedSize) + If destination buffer is not large enough, decoding will stop and output an error code (<0). If the source stream is detected malformed, the function will stop decoding and return a negative result. - This function is protected against buffer overflow exploits, - and never writes outside of output buffer, nor reads outside of input buffer. - It is also protected against malicious data packets. + This function is protected against buffer overflow exploits, including malicious data packets. + It never writes outside output buffer, nor reads outside input buffer. */ /************************************** - Advanced Functions +* Advanced Functions **************************************/ #define LZ4_MAX_INPUT_SIZE 0x7E000000 /* 2 113 929 216 bytes */ -#define LZ4_COMPRESSBOUND(isize) ((unsigned int)(isize) > (unsigned int)LZ4_MAX_INPUT_SIZE ? 0 : (isize) + ((isize)/255) + 16) +#define LZ4_COMPRESSBOUND(isize) ((unsigned)(isize) > (unsigned)LZ4_MAX_INPUT_SIZE ? 0 : (isize) + ((isize)/255) + 16) /* LZ4_compressBound() : Provides the maximum size that LZ4 compression may output in a "worst case" scenario (input data not compressible) - This function is primarily useful for memory allocation purposes (output buffer size). + This function is primarily useful for memory allocation purposes (destination buffer size). Macro LZ4_COMPRESSBOUND() is also provided for compilation-time evaluation (stack memory allocation for example). - - isize : is the input size. Max supported value is LZ4_MAX_INPUT_SIZE - return : maximum output size in a "worst case" scenario - or 0, if input size is too large ( > LZ4_MAX_INPUT_SIZE) + Note that LZ4_compress_default() compress faster when dest buffer size is >= LZ4_compressBound(srcSize) + inputSize : max supported value is LZ4_MAX_INPUT_SIZE + return : maximum output size in a "worst case" scenario + or 0, if input size is too large ( > LZ4_MAX_INPUT_SIZE) */ -int LZ4_compressBound(int isize); - +int LZ4_compressBound(int inputSize); /* -LZ4_compress_limitedOutput() : - Compress 'sourceSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'. - If it cannot achieve it, compression will stop, and result of the function will be zero. - This saves time and memory on detecting non-compressible (or barely compressible) data. - This function never writes outside of provided output buffer. - - sourceSize : Max supported value is LZ4_MAX_INPUT_VALUE - maxOutputSize : is the size of the destination buffer (which must be already allocated) - return : the number of bytes written in buffer 'dest' - or 0 if compression fails +LZ4_compress_fast() : + Same as LZ4_compress_default(), but allows to select an "acceleration" factor. + The larger the acceleration value, the faster the algorithm, but also the lesser the compression. + It's a trade-off. It can be fine tuned, with each successive value providing roughly +~3% to speed. + An acceleration value of "1" is the same as regular LZ4_compress_default() + Values <= 0 will be replaced by ACCELERATION_DEFAULT (see lz4.c), which is 1. */ -int LZ4_compress_limitedOutput (const char* source, char* dest, int sourceSize, int maxOutputSize); +int LZ4_compress_fast (const char* source, char* dest, int sourceSize, int maxDestSize, int acceleration); /* -LZ4_compress_withState() : - Same compression functions, but using an externally allocated memory space to store compression state. +LZ4_compress_fast_extState() : + Same compression function, just using an externally allocated memory space to store compression state. Use LZ4_sizeofState() to know how much memory must be allocated, - and then, provide it as 'void* state' to compression functions. + and allocate it on 8-bytes boundaries (using malloc() typically). + Then, provide it as 'void* state' to compression function. */ int LZ4_sizeofState(void); -int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize); -int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compress_fast_extState (void* state, const char* source, char* dest, int inputSize, int maxDestSize, int acceleration); + + +/* +LZ4_compress_destSize() : + Reverse the logic, by compressing as much data as possible from 'source' buffer + into already allocated buffer 'dest' of size 'targetDestSize'. + This function either compresses the entire 'source' content into 'dest' if it's large enough, + or fill 'dest' buffer completely with as much data as possible from 'source'. + *sourceSizePtr : will be modified to indicate how many bytes where read from 'source' to fill 'dest'. + New value is necessarily <= old value. + return : Nb bytes written into 'dest' (necessarily <= targetDestSize) + or 0 if compression fails +*/ +int LZ4_compress_destSize (const char* source, char* dest, int* sourceSizePtr, int targetDestSize); /* @@ -152,7 +166,6 @@ LZ4_decompress_fast() : */ int LZ4_decompress_fast (const char* source, char* dest, int originalSize); - /* LZ4_decompress_safe_partial() : This function decompress a compressed block of size 'compressedSize' at position 'source' @@ -169,104 +182,108 @@ int LZ4_decompress_safe_partial (const char* source, char* dest, int compressedS /*********************************************** - Experimental Streaming Compression Functions +* Streaming Compression Functions ***********************************************/ - -#define LZ4_STREAMSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8) -#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U32 * sizeof(unsigned int)) +#define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE-3)) + 4) +#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U64 * sizeof(long long)) /* * LZ4_stream_t * information structure to track an LZ4 stream. * important : init this structure content before first use ! + * note : only allocated directly the structure if you are statically linking LZ4 + * If you are using liblz4 as a DLL, please use below construction methods instead. */ -typedef struct { unsigned int table[LZ4_STREAMSIZE_U32]; } LZ4_stream_t; +typedef struct { long long table[LZ4_STREAMSIZE_U64]; } LZ4_stream_t; /* * LZ4_resetStream * Use this function to init an allocated LZ4_stream_t structure */ -void LZ4_resetStream (LZ4_stream_t* LZ4_streamPtr); +void LZ4_resetStream (LZ4_stream_t* streamPtr); /* - * If you prefer dynamic allocation methods, * LZ4_createStream will allocate and initialize an LZ4_stream_t structure * LZ4_freeStream releases its memory. + * In the context of a DLL (liblz4), please use these methods rather than the static struct. + * They are more future proof, in case of a change of LZ4_stream_t size. */ LZ4_stream_t* LZ4_createStream(void); -int LZ4_freeStream (LZ4_stream_t* LZ4_stream); +int LZ4_freeStream (LZ4_stream_t* streamPtr); /* * LZ4_loadDict * Use this function to load a static dictionary into LZ4_stream. * Any previous data will be forgotten, only 'dictionary' will remain in memory. * Loading a size of 0 is allowed. - * Return : 1 if OK, 0 if error + * Return : dictionary size, in bytes (necessarily <= 64 KB) */ -int LZ4_loadDict (LZ4_stream_t* LZ4_stream, const char* dictionary, int dictSize); +int LZ4_loadDict (LZ4_stream_t* streamPtr, const char* dictionary, int dictSize); /* - * LZ4_compress_continue - * Compress data block 'source', using blocks compressed before as dictionary to improve compression ratio - * Previous data blocks are assumed to still be present at their previous location. + * LZ4_compress_fast_continue + * Compress buffer content 'src', using data from previously compressed blocks as dictionary to improve compression ratio. + * Important : Previous data blocks are assumed to still be present and unmodified ! + * 'dst' buffer must be already allocated. + * If maxDstSize >= LZ4_compressBound(srcSize), compression is guaranteed to succeed, and runs faster. + * If not, and if compressed data cannot fit into 'dst' buffer size, compression stops, and function returns a zero. */ -int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize); - -/* - * LZ4_compress_limitedOutput_continue - * Same as before, but also specify a maximum target compressed size (maxOutputSize) - * If objective cannot be met, compression exits, and returns a zero. - */ -int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compress_fast_continue (LZ4_stream_t* streamPtr, const char* src, char* dst, int srcSize, int maxDstSize, int acceleration); /* * LZ4_saveDict * If previously compressed data block is not guaranteed to remain available at its memory location * save it into a safer place (char* safeBuffer) * Note : you don't need to call LZ4_loadDict() afterwards, - * dictionary is immediately usable, you can therefore call again LZ4_compress_continue() - * Return : dictionary size in bytes, or 0 if error - * Note : any dictSize > 64 KB will be interpreted as 64KB. + * dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue() + * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error */ -int LZ4_saveDict (LZ4_stream_t* LZ4_stream, char* safeBuffer, int dictSize); +int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int dictSize); /************************************************ - Experimental Streaming Decompression Functions +* Streaming Decompression Functions ************************************************/ -#define LZ4_STREAMDECODESIZE_U32 4 -#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int)) +#define LZ4_STREAMDECODESIZE_U64 4 +#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U64 * sizeof(unsigned long long)) +typedef struct { unsigned long long table[LZ4_STREAMDECODESIZE_U64]; } LZ4_streamDecode_t; /* * LZ4_streamDecode_t * information structure to track an LZ4 stream. - * important : init this structure content using LZ4_setStreamDecode or memset() before first use ! + * init this structure content using LZ4_setStreamDecode or memset() before first use ! + * + * In the context of a DLL (liblz4) please prefer usage of construction methods below. + * They are more future proof, in case of a change of LZ4_streamDecode_t size in the future. + * LZ4_createStreamDecode will allocate and initialize an LZ4_streamDecode_t structure + * LZ4_freeStreamDecode releases its memory. */ -typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t; +LZ4_streamDecode_t* LZ4_createStreamDecode(void); +int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); /* * LZ4_setStreamDecode * Use this function to instruct where to find the dictionary. - * This function can be used to specify a static dictionary, - * or to instruct where to find some previously decoded data saved into a different memory space. - * Setting a size of 0 is allowed (same effect as no dictionary). + * Setting a size of 0 is allowed (same effect as reset). * Return : 1 if OK, 0 if error */ int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize); /* - * If you prefer dynamic allocation methods, - * LZ4_createStreamDecode will allocate and initialize an LZ4_streamDecode_t structure - * LZ4_freeStreamDecode releases its memory. - */ -LZ4_streamDecode_t* LZ4_createStreamDecode(void); -int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); - -/* *_continue() : These decoding functions allow decompression of multiple blocks in "streaming" mode. - Previously decoded blocks must still be available at the memory position where they were decoded. - If it's not possible, save the relevant part of decoded data into a safe buffer, - and indicate where its new address using LZ4_setStreamDecode() + Previously decoded blocks *must* remain available at the memory position where they were decoded (up to 64 KB) + In the case of a ring buffers, decoding buffer must be either : + - Exactly same size as encoding buffer, with same update rule (block boundaries at same positions) + In which case, the decoding & encoding ring buffer can have any size, including very small ones ( < 64 KB). + - Larger than encoding buffer, by a minimum of maxBlockSize more bytes. + maxBlockSize is implementation dependent. It's the maximum size you intend to compress into a single block. + In which case, encoding and decoding buffers do not need to be synchronized, + and encoding ring buffer can have any size, including small ones ( < 64 KB). + - _At least_ 64 KB + 8 bytes + maxBlockSize. + In which case, encoding and decoding buffers do not need to be synchronized, + and encoding ring buffer can have any size, including larger than decoding buffer. + Whenever these conditions are not possible, save the last 64KB of decoded data into a safe buffer, + and indicate where it is saved using LZ4_setStreamDecode() */ int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxDecompressedSize); int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize); @@ -276,8 +293,8 @@ int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const ch Advanced decoding functions : *_usingDict() : These decoding functions work the same as - a combination of LZ4_setDictDecode() followed by LZ4_decompress_x_continue() - They don't use nor update an LZ4_streamDecode_t structure. + a combination of LZ4_setStreamDecode() followed by LZ4_decompress_x_continue() + They are stand-alone. They don't need nor update an LZ4_streamDecode_t structure. */ int LZ4_decompress_safe_usingDict (const char* source, char* dest, int compressedSize, int maxDecompressedSize, const char* dictStart, int dictSize); int LZ4_decompress_fast_usingDict (const char* source, char* dest, int originalSize, const char* dictStart, int dictSize); @@ -285,37 +302,57 @@ int LZ4_decompress_fast_usingDict (const char* source, char* dest, int originalS /************************************** - Obsolete Functions +* Obsolete Functions **************************************/ -/* -Obsolete decompression functions -These function names are deprecated and should no longer be used. -They are only provided here for compatibility with older user programs. -- LZ4_uncompress is the same as LZ4_decompress_fast -- LZ4_uncompress_unknownOutputSize is the same as LZ4_decompress_safe -These function prototypes are now disabled; uncomment them if you really need them. -It is highly recommended to stop using these functions and migrated to newer ones */ +/* Deprecate Warnings */ +/* Should these warnings messages be a problem, + it is generally possible to disable them, + with -Wno-deprecated-declarations for gcc + or _CRT_SECURE_NO_WARNINGS in Visual for example. + You can also define LZ4_DEPRECATE_WARNING_DEFBLOCK. */ +#ifndef LZ4_DEPRECATE_WARNING_DEFBLOCK +# define LZ4_DEPRECATE_WARNING_DEFBLOCK +# define LZ4_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) +# if (LZ4_GCC_VERSION >= 405) || defined(__clang__) +# define LZ4_DEPRECATED(message) __attribute__((deprecated(message))) +# elif (LZ4_GCC_VERSION >= 301) +# define LZ4_DEPRECATED(message) __attribute__((deprecated)) +# elif defined(_MSC_VER) +# define LZ4_DEPRECATED(message) __declspec(deprecated(message)) +# else +# pragma message("WARNING: You need to implement LZ4_DEPRECATED for this compiler") +# define LZ4_DEPRECATED(message) +# endif +#endif /* LZ4_DEPRECATE_WARNING_DEFBLOCK */ + +/* Obsolete compression functions */ +/* These functions are planned to start generate warnings by r131 approximately */ +int LZ4_compress (const char* source, char* dest, int sourceSize); +int LZ4_compress_limitedOutput (const char* source, char* dest, int sourceSize, int maxOutputSize); +int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize); +int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compress_continue (LZ4_stream_t* LZ4_streamPtr, const char* source, char* dest, int inputSize); +int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_streamPtr, const char* source, char* dest, int inputSize, int maxOutputSize); + +/* Obsolete decompression functions */ +/* These function names are completely deprecated and must no longer be used. + They are only provided here for compatibility with older programs. + - LZ4_uncompress is the same as LZ4_decompress_fast + - LZ4_uncompress_unknownOutputSize is the same as LZ4_decompress_safe + These function prototypes are now disabled; uncomment them only if you really need them. + It is highly recommended to stop using these prototypes and migrate to maintained ones */ /* int LZ4_uncompress (const char* source, char* dest, int outputSize); */ /* int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize); */ -/* - * If you prefer dynamic allocation methods, - * LZ4_createStreamDecode() - * provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure. - * LZ4_free just frees it. - */ -/* void* LZ4_createStreamDecode(void); */ -/*int LZ4_free (void* LZ4_stream); yes, it's the same one as for compression */ - /* Obsolete streaming functions; use new streaming interface whenever possible */ -void* LZ4_create (const char* inputBuffer); -int LZ4_sizeofStreamState(void); -int LZ4_resetStreamState(void* state, const char* inputBuffer); -char* LZ4_slideInputBuffer (void* state); +LZ4_DEPRECATED("use LZ4_createStream() instead") void* LZ4_create (char* inputBuffer); +LZ4_DEPRECATED("use LZ4_createStream() instead") int LZ4_sizeofStreamState(void); +LZ4_DEPRECATED("use LZ4_resetStream() instead") int LZ4_resetStreamState(void* state, char* inputBuffer); +LZ4_DEPRECATED("use LZ4_saveDict() instead") char* LZ4_slideInputBuffer (void* state); /* Obsolete streaming decoding functions */ -int LZ4_decompress_safe_withPrefix64k (const char* source, char* dest, int compressedSize, int maxOutputSize); -int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int originalSize); +LZ4_DEPRECATED("use LZ4_decompress_safe_usingDict() instead") int LZ4_decompress_safe_withPrefix64k (const char* src, char* dst, int compressedSize, int maxDstSize); +LZ4_DEPRECATED("use LZ4_decompress_fast_usingDict() instead") int LZ4_decompress_fast_withPrefix64k (const char* src, char* dst, int originalSize); #if defined (__cplusplus) http://git-wip-us.apache.org/repos/asf/hadoop/blob/4c061e60/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.c ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.c b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.c index 34a6173..bbe7a9d 100644 --- a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.c +++ b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.c @@ -1,566 +1,279 @@ /* - LZ4 HC - High Compression Mode of LZ4 - Copyright (C) 2011-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 : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ + LZ4 HC - High Compression Mode of LZ4 + Copyright (C) 2011-2015, 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 : + - LZ4 source repository : https://github.com/Cyan4973/lz4 + - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c */ /************************************** - Tuning Parameter +* Tuning Parameter **************************************/ -#define LZ4HC_DEFAULT_COMPRESSIONLEVEL 8 +static const int LZ4HC_compressionLevel_default = 9; /************************************** - Memory routines +* Includes **************************************/ -#include <stdlib.h> /* calloc, free */ -#define ALLOCATOR(s) calloc(1,s) -#define FREEMEM free -#include <string.h> /* memset, memcpy */ -#define MEM_INIT memset - - -/************************************** - CPU Feature Detection -**************************************/ -/* 32 or 64 bits ? */ -#if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \ - || defined(__64BIT__) || defined(__mips64) \ - || defined(__powerpc64__) || defined(__powerpc64le__) \ - || defined(__ppc64__) || defined(__ppc64le__) \ - || defined(__PPC64__) || defined(__PPC64LE__) \ - || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) \ - || defined(__s390x__) ) /* Detects 64 bits mode */ -# define LZ4_ARCH64 1 -#else -# define LZ4_ARCH64 0 -#endif - -/* - * Little Endian or Big Endian ? - * Overwrite the #define below if you know your architecture endianess - */ -#include <stdlib.h> /* Apparently required to detect endianess */ -#if defined (__GLIBC__) -# include <endian.h> -# if (__BYTE_ORDER == __BIG_ENDIAN) -# define LZ4_BIG_ENDIAN 1 -# endif -#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN)) -# define LZ4_BIG_ENDIAN 1 -#elif defined(__sparc) || defined(__sparc__) \ - || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \ - || defined(__hpux) || defined(__hppa) \ - || defined(_MIPSEB) || defined(__s390__) -# define LZ4_BIG_ENDIAN 1 -#else -/* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */ -#endif - -/* - * 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 - */ -#if defined(__ARM_FEATURE_UNALIGNED) -# define LZ4_FORCE_UNALIGNED_ACCESS 1 -#endif - -/* Define this parameter if your target system or compiler does not support hardware bit count */ -#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */ -# define LZ4_FORCE_SW_BITCOUNT -#endif +#include "lz4hc.h" /************************************** - Compiler Options +* Local Compiler Options **************************************/ -#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ -/* "restrict" is a known keyword */ -#else -# define restrict /* Disable restrict */ +#if defined(__GNUC__) +# pragma GCC diagnostic ignored "-Wunused-function" #endif -#ifdef _MSC_VER /* Visual Studio */ -# define FORCE_INLINE static __forceinline -# include <intrin.h> /* For Visual 2005 */ -# if LZ4_ARCH64 /* 64-bits */ -# pragma intrinsic(_BitScanForward64) /* For Visual 2005 */ -# pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */ -# else /* 32-bits */ -# 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 FORCE_INLINE static inline __attribute__((always_inline)) -# else -# define FORCE_INLINE static inline -# endif -#endif - -#ifdef _MSC_VER /* Visual Studio */ -# define lz4_bswap16(x) _byteswap_ushort(x) -#else -# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8))) +#if defined (__clang__) +# pragma clang diagnostic ignored "-Wunused-function" #endif /************************************** - Includes +* Common LZ4 definition **************************************/ -#include "lz4hc.h" -#include "lz4.h" +#define LZ4_COMMONDEFS_ONLY +#include "lz4.c" /************************************** - Basic Types +* Local Constants **************************************/ -#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(LZ4_FORCE_UNALIGNED_ACCESS) -# define _PACKED __attribute__ ((packed)) -#else -# define _PACKED -#endif - -#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) -# ifdef __IBMC__ -# pragma pack(1) -# else -# pragma pack(push, 1) -# endif -#endif - -typedef struct _U16_S { U16 v; } _PACKED U16_S; -typedef struct _U32_S { U32 v; } _PACKED U32_S; -typedef struct _U64_S { U64 v; } _PACKED U64_S; - -#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) -# pragma pack(pop) -#endif - -#define A64(x) (((U64_S *)(x))->v) -#define A32(x) (((U32_S *)(x))->v) -#define A16(x) (((U16_S *)(x))->v) - - -/************************************** - Constants -**************************************/ -#define MINMATCH 4 - #define DICTIONARY_LOGSIZE 16 #define MAXD (1<<DICTIONARY_LOGSIZE) -#define MAXD_MASK ((U32)(MAXD - 1)) -#define MAX_DISTANCE (MAXD - 1) +#define MAXD_MASK (MAXD - 1) #define HASH_LOG (DICTIONARY_LOGSIZE-1) #define HASHTABLESIZE (1 << HASH_LOG) #define HASH_MASK (HASHTABLESIZE - 1) -#define ML_BITS 4 -#define ML_MASK (size_t)((1U<<ML_BITS)-1) -#define RUN_BITS (8-ML_BITS) -#define RUN_MASK ((1U<<RUN_BITS)-1) - -#define COPYLENGTH 8 -#define LASTLITERALS 5 -#define MFLIMIT (COPYLENGTH+MINMATCH) -#define MINLENGTH (MFLIMIT+1) #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) -#define KB *(1U<<10) -#define MB *(1U<<20) -#define GB *(1U<<30) +static const int g_maxCompressionLevel = 16; /************************************** - Architecture-specific macros -**************************************/ -#if LZ4_ARCH64 /* 64-bit */ -# define STEPSIZE 8 -# define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; -# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) -# define AARCH A64 -# define HTYPE U32 -# define INITBASE(b,s) const BYTE* const b = s -#else /* 32-bit */ -# define STEPSIZE 4 -# define LZ4_COPYSTEP(s,d) A32(d) = A32(s); d+=4; s+=4; -# define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d); -# define AARCH A32 -# define HTYPE U32 -# define INITBASE(b,s) const BYTE* const b = s -#endif - -#if defined(LZ4_BIG_ENDIAN) -# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } -# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; } -#else /* Little Endian */ -# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } -# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } -#endif - - -/************************************** - Local Types +* Local Types **************************************/ typedef struct { - const BYTE* inputBuffer; - const BYTE* base; - const BYTE* end; - HTYPE hashTable[HASHTABLESIZE]; - U16 chainTable[MAXD]; - const BYTE* nextToUpdate; + U32 hashTable[HASHTABLESIZE]; + U16 chainTable[MAXD]; + const BYTE* end; /* next block here to continue on current prefix */ + const BYTE* base; /* All index relative to this position */ + const BYTE* dictBase; /* alternate base for extDict */ + BYTE* inputBuffer; /* deprecated */ + U32 dictLimit; /* below that point, need extDict */ + U32 lowLimit; /* below that point, no more dict */ + U32 nextToUpdate; /* index from which to continue dictionary update */ + U32 compressionLevel; } LZ4HC_Data_Structure; /************************************** - Macros +* Local Macros **************************************/ -#define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e); -#define LZ4_BLINDCOPY(s,d,l) { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; } #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG)) -#define HASH_VALUE(p) HASH_FUNCTION(A32(p)) -#define HASH_POINTER(p) (HashTable[HASH_VALUE(p)] + base) -#define DELTANEXT(p) chainTable[(size_t)(p) & MAXD_MASK] -#define GETNEXT(p) ((p) - (size_t)DELTANEXT(p)) +//#define DELTANEXTU16(p) chainTable[(p) & MAXD_MASK] /* flexible, MAXD dependent */ +#define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */ +static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); } -/************************************** - Private functions -**************************************/ -#if LZ4_ARCH64 -FORCE_INLINE int LZ4_NbCommonBytes (register U64 val) -{ -#if defined(LZ4_BIG_ENDIAN) -# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanReverse64( &r, val ); - return (int)(r>>3); -# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clzll(val) >> 3); -# else - int r; - if (!(val>>32)) { r=4; } else { r=0; val>>=32; } - if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } - r += (!val); - return r; -# endif -#else -# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r = 0; - _BitScanForward64( &r, val ); - return (int)(r>>3); -# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctzll(val) >> 3); -# else - static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 }; - return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58]; -# endif -#endif -} - -#else - -FORCE_INLINE int LZ4_NbCommonBytes (register U32 val) -{ -#if defined(LZ4_BIG_ENDIAN) -# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r; - _BitScanReverse( &r, val ); - return (int)(r>>3); -# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clz(val) >> 3); -# else - int r; - if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } - r += (!val); - return r; -# endif -#else -# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) - unsigned long r; - _BitScanForward( &r, val ); - return (int)(r>>3); -# elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctz(val) >> 3); -# else - static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 }; - return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; -# endif -#endif -} -#endif - - -int LZ4_sizeofStreamStateHC() -{ - return sizeof(LZ4HC_Data_Structure); -} - -FORCE_INLINE void LZ4_initHC (LZ4HC_Data_Structure* hc4, const BYTE* base) +/************************************** +* HC Compression +**************************************/ +static void LZ4HC_init (LZ4HC_Data_Structure* hc4, const BYTE* start) { MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); - hc4->nextToUpdate = base + 1; - hc4->base = base; - hc4->inputBuffer = base; - hc4->end = base; -} - -int LZ4_resetStreamStateHC(void* state, const char* inputBuffer) -{ - if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */ - LZ4_initHC((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer); - return 0; -} - - -void* LZ4_createHC (const char* inputBuffer) -{ - void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure)); - LZ4_initHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer); - return hc4; -} - - -int LZ4_freeHC (void* LZ4HC_Data) -{ - FREEMEM(LZ4HC_Data); - return (0); + hc4->nextToUpdate = 64 KB; + hc4->base = start - 64 KB; + hc4->end = start; + hc4->dictBase = start - 64 KB; + hc4->dictLimit = 64 KB; + hc4->lowLimit = 64 KB; } /* Update chains up to ip (excluded) */ FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) { - U16* chainTable = hc4->chainTable; - HTYPE* HashTable = hc4->hashTable; - INITBASE(base,hc4->base); + U16* chainTable = hc4->chainTable; + U32* HashTable = hc4->hashTable; + const BYTE* const base = hc4->base; + const U32 target = (U32)(ip - base); + U32 idx = hc4->nextToUpdate; - while(hc4->nextToUpdate < ip) + while(idx < target) { - const BYTE* const p = hc4->nextToUpdate; - size_t delta = (p) - HASH_POINTER(p); + U32 h = LZ4HC_hashPtr(base+idx); + size_t delta = idx - HashTable[h]; if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; - DELTANEXT(p) = (U16)delta; - HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base); - hc4->nextToUpdate++; + DELTANEXTU16(idx) = (U16)delta; + HashTable[h] = idx; + idx++; } -} - - -char* LZ4_slideInputBufferHC(void* LZ4HC_Data) -{ - LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data; - size_t distance = (hc4->end - 64 KB) - hc4->inputBuffer; - - if (hc4->end <= hc4->inputBuffer + 64 KB) return (char*)(hc4->end); /* no update : less than 64KB within buffer */ - - distance = (distance >> 16) << 16; /* Must be a multiple of 64 KB */ - LZ4HC_Insert(hc4, hc4->end - MINMATCH); - memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB); - hc4->nextToUpdate -= distance; - hc4->base -= distance; - if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB) /* Avoid overflow */ - { - int i; - hc4->base += 1 GB; - for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB; - } - hc4->end -= distance; - return (char*)(hc4->end); -} - -FORCE_INLINE size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit) -{ - const BYTE* p1t = p1; - - while (p1t<matchlimit-(STEPSIZE-1)) - { - size_t diff = AARCH(p2) ^ AARCH(p1t); - if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; } - p1t += LZ4_NbCommonBytes(diff); - return (p1t - p1); - } - if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; } - if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; } - if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++; - return (p1t - p1); + hc4->nextToUpdate = target; } -FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos, const int maxNbAttempts) +FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, /* Index table will be updated */ + const BYTE* ip, const BYTE* const iLimit, + const BYTE** matchpos, + const int maxNbAttempts) { U16* const chainTable = hc4->chainTable; - HTYPE* const HashTable = hc4->hashTable; - const BYTE* ref; - INITBASE(base,hc4->base); + U32* const HashTable = hc4->hashTable; + const BYTE* const base = hc4->base; + const BYTE* const dictBase = hc4->dictBase; + const U32 dictLimit = hc4->dictLimit; + const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1); + U32 matchIndex; + const BYTE* match; int nbAttempts=maxNbAttempts; - size_t repl=0, ml=0; - U16 delta=0; /* useless assignment, to remove an uninitialization warning */ + size_t ml=0; /* HC4 match finder */ LZ4HC_Insert(hc4, ip); - ref = HASH_POINTER(ip); - -#define REPEAT_OPTIMIZATION -#ifdef REPEAT_OPTIMIZATION - /* Detect repetitive sequences of length <= 4 */ - if ((U32)(ip-ref) <= 4) /* potential repetition */ - { - if (A32(ref) == A32(ip)) /* confirmed */ - { - delta = (U16)(ip-ref); - repl = ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; - *matchpos = ref; - } - ref = GETNEXT(ref); - } -#endif + matchIndex = HashTable[LZ4HC_hashPtr(ip)]; - while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) + while ((matchIndex>=lowLimit) && (nbAttempts)) { nbAttempts--; - if (*(ref+ml) == *(ip+ml)) - if (A32(ref) == A32(ip)) + if (matchIndex >= dictLimit) { - size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; - if (mlt > ml) { ml = mlt; *matchpos = ref; } + match = base + matchIndex; + if (*(match+ml) == *(ip+ml) + && (LZ4_read32(match) == LZ4_read32(ip))) + { + size_t mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH; + if (mlt > ml) { ml = mlt; *matchpos = match; } + } } - ref = GETNEXT(ref); - } - -#ifdef REPEAT_OPTIMIZATION - /* Complete table */ - if (repl) - { - const BYTE* ptr = ip; - const BYTE* end; - - end = ip + repl - (MINMATCH-1); - while(ptr < end-delta) + else { - DELTANEXT(ptr) = delta; /* Pre-Load */ - ptr++; + match = dictBase + matchIndex; + if (LZ4_read32(match) == LZ4_read32(ip)) + { + size_t mlt; + const BYTE* vLimit = ip + (dictLimit - matchIndex); + if (vLimit > iLimit) vLimit = iLimit; + mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH; + if ((ip+mlt == vLimit) && (vLimit < iLimit)) + mlt += LZ4_count(ip+mlt, base+dictLimit, iLimit); + if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; } /* virtual matchpos */ + } } - do - { - DELTANEXT(ptr) = delta; - HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); /* Head of chain */ - ptr++; - } while(ptr < end); - hc4->nextToUpdate = end; + matchIndex -= DELTANEXTU16(matchIndex); } -#endif return (int)ml; } -FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos, const int maxNbAttempts) +FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( + LZ4HC_Data_Structure* hc4, + const BYTE* const ip, + const BYTE* const iLowLimit, + const BYTE* const iHighLimit, + int longest, + const BYTE** matchpos, + const BYTE** startpos, + const int maxNbAttempts) { - U16* const chainTable = hc4->chainTable; - HTYPE* const HashTable = hc4->hashTable; - INITBASE(base,hc4->base); - const BYTE* ref; + U16* const chainTable = hc4->chainTable; + U32* const HashTable = hc4->hashTable; + const BYTE* const base = hc4->base; + const U32 dictLimit = hc4->dictLimit; + const BYTE* const lowPrefixPtr = base + dictLimit; + const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1); + const BYTE* const dictBase = hc4->dictBase; + U32 matchIndex; int nbAttempts = maxNbAttempts; - int delta = (int)(ip-startLimit); + int delta = (int)(ip-iLowLimit); + /* First Match */ LZ4HC_Insert(hc4, ip); - ref = HASH_POINTER(ip); + matchIndex = HashTable[LZ4HC_hashPtr(ip)]; - while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) + while ((matchIndex>=lowLimit) && (nbAttempts)) { nbAttempts--; - if (*(startLimit + longest) == *(ref - delta + longest)) - if (A32(ref) == A32(ip)) + if (matchIndex >= dictLimit) { -#if 1 - const BYTE* reft = ref+MINMATCH; - const BYTE* ipt = ip+MINMATCH; - const BYTE* startt = ip; + const BYTE* matchPtr = base + matchIndex; + if (*(iLowLimit + longest) == *(matchPtr - delta + longest)) + if (LZ4_read32(matchPtr) == LZ4_read32(ip)) + { + int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit); + int back = 0; - while (ipt<matchlimit-(STEPSIZE-1)) - { - size_t diff = AARCH(reft) ^ AARCH(ipt); - if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; } - ipt += LZ4_NbCommonBytes(diff); - goto _endCount; - } - if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; } - if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; } - if ((ipt<matchlimit) && (*reft == *ipt)) ipt++; -_endCount: - reft = ref; -#else - /* Easier for code maintenance, but unfortunately slower too */ - const BYTE* startt = ip; - const BYTE* reft = ref; - const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit); -#endif + while ((ip+back>iLowLimit) + && (matchPtr+back > lowPrefixPtr) + && (ip[back-1] == matchPtr[back-1])) + back--; - while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;} + mlt -= back; - if ((ipt-startt) > longest) + if (mlt > longest) + { + longest = (int)mlt; + *matchpos = matchPtr+back; + *startpos = ip+back; + } + } + } + else + { + const BYTE* matchPtr = dictBase + matchIndex; + if (LZ4_read32(matchPtr) == LZ4_read32(ip)) { - longest = (int)(ipt-startt); - *matchpos = reft; - *startpos = startt; + size_t mlt; + int back=0; + const BYTE* vLimit = ip + (dictLimit - matchIndex); + if (vLimit > iHighLimit) vLimit = iHighLimit; + mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH; + if ((ip+mlt == vLimit) && (vLimit < iHighLimit)) + mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit); + while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchPtr[back-1])) back--; + mlt -= back; + if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; } } } - ref = GETNEXT(ref); + matchIndex -= DELTANEXTU16(matchIndex); } return longest; @@ -569,34 +282,44 @@ _endCount: typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; +#define LZ4HC_DEBUG 0 +#if LZ4HC_DEBUG +static unsigned debug = 0; +#endif + FORCE_INLINE int LZ4HC_encodeSequence ( - const BYTE** ip, - BYTE** op, - const BYTE** anchor, - int matchLength, - const BYTE* ref, - limitedOutput_directive limitedOutputBuffer, - BYTE* oend) + const BYTE** ip, + BYTE** op, + const BYTE** anchor, + int matchLength, + const BYTE* const match, + limitedOutput_directive limitedOutputBuffer, + BYTE* oend) { int length; BYTE* token; +#if LZ4HC_DEBUG + if (debug) printf("literal : %u -- match : %u -- offset : %u\n", (U32)(*ip - *anchor), (U32)matchLength, (U32)(*ip-match)); +#endif + /* Encode Literal length */ length = (int)(*ip - *anchor); token = (*op)++; - if ((limitedOutputBuffer) && ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > oend)) return 1; /* Check output limit */ + if ((limitedOutputBuffer) && ((*op + (length>>8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */ if (length>=(int)RUN_MASK) { int len; *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; } else *token = (BYTE)(length<<ML_BITS); /* Copy Literals */ - LZ4_BLINDCOPY(*anchor, *op, length); + LZ4_wildCopy(*op, *anchor, (*op) + length); + *op += length; /* Encode Offset */ - LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref)); + LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2; /* Encode MatchLength */ length = (int)(matchLength-MINMATCH); - if ((limitedOutputBuffer) && (*op + (1 + LASTLITERALS) + (length>>8) > oend)) return 1; /* Check output limit */ + if ((limitedOutputBuffer) && (*op + (length>>8) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */ if (length>=(int)ML_MASK) { *token+=ML_MASK; length-=ML_MASK; for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (length > 254) { length-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)length; } else *token += (BYTE)(length); @@ -608,16 +331,15 @@ FORCE_INLINE int LZ4HC_encodeSequence ( } -#define MAX_COMPRESSION_LEVEL 16 static int LZ4HC_compress_generic ( - void* ctxvoid, - const char* source, - char* dest, - int inputSize, - int maxOutputSize, - int compressionLevel, - limitedOutput_directive limit - ) + void* ctxvoid, + const char* source, + char* dest, + int inputSize, + int maxOutputSize, + int compressionLevel, + limitedOutput_directive limit + ) { LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid; const BYTE* ip = (const BYTE*) source; @@ -629,7 +351,7 @@ static int LZ4HC_compress_generic ( BYTE* op = (BYTE*) dest; BYTE* const oend = op + maxOutputSize; - const int maxNbAttempts = compressionLevel > MAX_COMPRESSION_LEVEL ? 1 << MAX_COMPRESSION_LEVEL : compressionLevel ? 1<<(compressionLevel-1) : 1<<LZ4HC_DEFAULT_COMPRESSIONLEVEL; + unsigned maxNbAttempts; int ml, ml2, ml3, ml0; const BYTE* ref=NULL; const BYTE* start2=NULL; @@ -640,8 +362,10 @@ static int LZ4HC_compress_generic ( const BYTE* ref0; - /* Ensure blocks follow each other */ - if (ip != ctx->end) return 0; + /* init */ + if (compressionLevel > g_maxCompressionLevel) compressionLevel = g_maxCompressionLevel; + if (compressionLevel < 1) compressionLevel = LZ4HC_compressionLevel_default; + maxNbAttempts = 1 << (compressionLevel-1); ctx->end += inputSize; ip++; @@ -689,10 +413,10 @@ _Search2: _Search3: /* - * Currently we have : - * ml2 > ml1, and - * ip1+3 <= ip2 (usually < ip1+ml1) - */ + * Currently we have : + * ml2 > ml1, and + * ip1+3 <= ip2 (usually < ip1+ml1) + */ if ((start2 - ip) < OPTIMAL_ML) { int correction; @@ -760,9 +484,9 @@ _Search3: } /* - * OK, now we have 3 ascending matches; let's write at least the first one - * ip & ref are known; Now for ml - */ + * OK, now we have 3 ascending matches; let's write at least the first one + * ip & ref are known; Now for ml + */ if (start2 < ip+ml) { if ((start2 - ip) < (int)ML_MASK) @@ -794,7 +518,6 @@ _Search3: ml2 = ml3; goto _Search3; - } /* Encode Last Literals */ @@ -812,73 +535,182 @@ _Search3: } -int LZ4_compressHC2(const char* source, char* dest, int inputSize, int compressionLevel) -{ - void* ctx = LZ4_createHC(source); - int result; - if (ctx==NULL) return 0; +int LZ4_sizeofStateHC(void) { return sizeof(LZ4HC_Data_Structure); } - result = LZ4HC_compress_generic (ctx, source, dest, inputSize, 0, compressionLevel, noLimit); +int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel) +{ + if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */ + LZ4HC_init ((LZ4HC_Data_Structure*)state, (const BYTE*)src); + if (maxDstSize < LZ4_compressBound(srcSize)) + return LZ4HC_compress_generic (state, src, dst, srcSize, maxDstSize, compressionLevel, limitedOutput); + else + return LZ4HC_compress_generic (state, src, dst, srcSize, maxDstSize, compressionLevel, noLimit); +} - LZ4_freeHC(ctx); - return result; +int LZ4_compress_HC(const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel) +{ + LZ4HC_Data_Structure state; + return LZ4_compress_HC_extStateHC(&state, src, dst, srcSize, maxDstSize, compressionLevel); } -int LZ4_compressHC(const char* source, char* dest, int inputSize) { return LZ4_compressHC2(source, dest, inputSize, 0); } -int LZ4_compressHC2_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) -{ - void* ctx = LZ4_createHC(source); - int result; - if (ctx==NULL) return 0; - result = LZ4HC_compress_generic (ctx, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); +/************************************** +* Streaming Functions +**************************************/ +/* allocation */ +LZ4_streamHC_t* LZ4_createStreamHC(void) { return (LZ4_streamHC_t*)malloc(sizeof(LZ4_streamHC_t)); } +int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr) { free(LZ4_streamHCPtr); return 0; } + - LZ4_freeHC(ctx); - return result; +/* initialization */ +void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) +{ + LZ4_STATIC_ASSERT(sizeof(LZ4HC_Data_Structure) <= sizeof(LZ4_streamHC_t)); /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */ + ((LZ4HC_Data_Structure*)LZ4_streamHCPtr)->base = NULL; + ((LZ4HC_Data_Structure*)LZ4_streamHCPtr)->compressionLevel = (unsigned)compressionLevel; } -int LZ4_compressHC_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) +int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) { - return LZ4_compressHC2_limitedOutput(source, dest, inputSize, maxOutputSize, 0); + LZ4HC_Data_Structure* ctxPtr = (LZ4HC_Data_Structure*) LZ4_streamHCPtr; + if (dictSize > 64 KB) + { + dictionary += dictSize - 64 KB; + dictSize = 64 KB; + } + LZ4HC_init (ctxPtr, (const BYTE*)dictionary); + if (dictSize >= 4) LZ4HC_Insert (ctxPtr, (const BYTE*)dictionary +(dictSize-3)); + ctxPtr->end = (const BYTE*)dictionary + dictSize; + return dictSize; } -/***************************** - Using external allocation -*****************************/ -int LZ4_sizeofStateHC() { return sizeof(LZ4HC_Data_Structure); } +/* compression */ +static void LZ4HC_setExternalDict(LZ4HC_Data_Structure* ctxPtr, const BYTE* newBlock) +{ + if (ctxPtr->end >= ctxPtr->base + 4) + LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */ + /* Only one memory segment for extDict, so any previous extDict is lost at this stage */ + ctxPtr->lowLimit = ctxPtr->dictLimit; + ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); + ctxPtr->dictBase = ctxPtr->base; + ctxPtr->base = newBlock - ctxPtr->dictLimit; + ctxPtr->end = newBlock; + ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */ +} -int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel) +static int LZ4_compressHC_continue_generic (LZ4HC_Data_Structure* ctxPtr, + const char* source, char* dest, + int inputSize, int maxOutputSize, limitedOutput_directive limit) { - if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */ - LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source); - return LZ4HC_compress_generic (state, source, dest, inputSize, 0, compressionLevel, noLimit); + /* auto-init if forgotten */ + if (ctxPtr->base == NULL) + LZ4HC_init (ctxPtr, (const BYTE*) source); + + /* Check overflow */ + if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB) + { + size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit; + if (dictSize > 64 KB) dictSize = 64 KB; + + LZ4_loadDictHC((LZ4_streamHC_t*)ctxPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize); + } + + /* Check if blocks follow each other */ + if ((const BYTE*)source != ctxPtr->end) + LZ4HC_setExternalDict(ctxPtr, (const BYTE*)source); + + /* Check overlapping input/dictionary space */ + { + const BYTE* sourceEnd = (const BYTE*) source + inputSize; + const BYTE* dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit; + const BYTE* dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit; + if ((sourceEnd > dictBegin) && ((const BYTE*)source < dictEnd)) + { + if (sourceEnd > dictEnd) sourceEnd = dictEnd; + ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase); + if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit; + } + } + + return LZ4HC_compress_generic (ctxPtr, source, dest, inputSize, maxOutputSize, ctxPtr->compressionLevel, limit); +} + +int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize) +{ + if (maxOutputSize < LZ4_compressBound(inputSize)) + return LZ4_compressHC_continue_generic ((LZ4HC_Data_Structure*)LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, limitedOutput); + else + return LZ4_compressHC_continue_generic ((LZ4HC_Data_Structure*)LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, noLimit); } -int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize) -{ return LZ4_compressHC2_withStateHC (state, source, dest, inputSize, 0); } +/* dictionary saving */ -int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) +int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize) { - if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */ - LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source); - return LZ4HC_compress_generic (state, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); + LZ4HC_Data_Structure* streamPtr = (LZ4HC_Data_Structure*)LZ4_streamHCPtr; + int prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit)); + if (dictSize > 64 KB) dictSize = 64 KB; + if (dictSize < 4) dictSize = 0; + if (dictSize > prefixSize) dictSize = prefixSize; + memmove(safeBuffer, streamPtr->end - dictSize, dictSize); + { + U32 endIndex = (U32)(streamPtr->end - streamPtr->base); + streamPtr->end = (const BYTE*)safeBuffer + dictSize; + streamPtr->base = streamPtr->end - endIndex; + streamPtr->dictLimit = endIndex - dictSize; + streamPtr->lowLimit = endIndex - dictSize; + if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit; + } + return dictSize; } -int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize) -{ return LZ4_compressHC2_limitedOutput_withStateHC (state, source, dest, inputSize, maxOutputSize, 0); } +/*********************************** +* Deprecated Functions +***********************************/ +/* Deprecated compression functions */ +/* These functions are planned to start generate warnings by r131 approximately */ +int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); } +int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); } +int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); } +int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); } +int LZ4_compressHC_withStateHC (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, LZ4_compressBound(srcSize), 0); } +int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, maxDstSize, 0); } +int LZ4_compressHC2_withStateHC (void* state, const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); } +int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, maxDstSize, cLevel); } +int LZ4_compressHC_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, LZ4_compressBound(srcSize)); } +int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, maxDstSize); } + + +/* Deprecated streaming functions */ +/* These functions currently generate deprecation warnings */ +int LZ4_sizeofStreamStateHC(void) { return LZ4_STREAMHCSIZE; } + +int LZ4_resetStreamStateHC(void* state, char* inputBuffer) +{ + if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */ + LZ4HC_init((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer); + ((LZ4HC_Data_Structure*)state)->inputBuffer = (BYTE*)inputBuffer; + return 0; +} -/**************************** - Stream functions -****************************/ +void* LZ4_createHC (char* inputBuffer) +{ + void* hc4 = ALLOCATOR(1, sizeof(LZ4HC_Data_Structure)); + if (hc4 == NULL) return NULL; /* not enough memory */ + LZ4HC_init ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer); + ((LZ4HC_Data_Structure*)hc4)->inputBuffer = (BYTE*)inputBuffer; + return hc4; +} -int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize) +int LZ4_freeHC (void* LZ4HC_Data) { - return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, 0, noLimit); + FREEMEM(LZ4HC_Data); + return (0); } int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel) @@ -886,12 +718,14 @@ int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, compressionLevel, noLimit); } -int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize) +int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) { - return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, 0, limitedOutput); + return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); } -int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) +char* LZ4_slideInputBufferHC(void* LZ4HC_Data) { - return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); + LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data; + int dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB); + return (char*)(hc4->inputBuffer + dictSize); } http://git-wip-us.apache.org/repos/asf/hadoop/blob/4c061e60/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.h ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.h b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.h index deb2394..431f7c8 100644 --- a/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.h +++ b/hadoop-common-project/hadoop-common/src/main/native/src/org/apache/hadoop/io/compress/lz4/lz4hc.h @@ -1,7 +1,7 @@ /* LZ4 HC - High Compression Mode of LZ4 Header File - Copyright (C) 2011-2014, Yann Collet. + Copyright (C) 2011-2015, 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 @@ -28,8 +28,8 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. You can contact the author at : - - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - - LZ4 source repository : http://code.google.com/p/lz4/ + - LZ4 source repository : https://github.com/Cyan4973/lz4 + - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c */ #pragma once @@ -38,136 +38,152 @@ extern "C" { #endif +/***************************** +* Includes +*****************************/ +#include <stddef.h> /* size_t */ -int LZ4_compressHC (const char* source, char* dest, int inputSize); -/* -LZ4_compressHC : - return : the number of bytes in compressed buffer dest - or 0 if compression fails. - note : destination buffer must be already allocated. - To avoid any problem, size it to handle worst cases situations (input data not compressible) - Worst case size evaluation is provided by function LZ4_compressBound() (see "lz4.h") -*/ -int LZ4_compressHC_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize); +/************************************** +* Block Compression +**************************************/ +int LZ4_compress_HC (const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel); /* -LZ4_compress_limitedOutput() : - Compress 'inputSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'. - If it cannot achieve it, compression will stop, and result of the function will be zero. - This function never writes outside of provided output buffer. - - inputSize : Max supported value is 1 GB - maxOutputSize : is maximum allowed size into the destination buffer (which must be already allocated) - return : the number of output bytes written in buffer 'dest' - or 0 if compression fails. +LZ4_compress_HC : + Destination buffer 'dst' must be already allocated. + Compression completion is guaranteed if 'dst' buffer is sized to handle worst circumstances (data not compressible) + Worst size evaluation is provided by function LZ4_compressBound() (see "lz4.h") + srcSize : Max supported value is LZ4_MAX_INPUT_SIZE (see "lz4.h") + compressionLevel : Recommended values are between 4 and 9, although any value between 0 and 16 will work. + 0 means "use default value" (see lz4hc.c). + Values >16 behave the same as 16. + return : the number of bytes written into buffer 'dst' + or 0 if compression fails. */ -int LZ4_compressHC2 (const char* source, char* dest, int inputSize, int compressionLevel); -int LZ4_compressHC2_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); -/* - Same functions as above, but with programmable 'compressionLevel'. - Recommended values are between 4 and 9, although any value between 0 and 16 will work. - 'compressionLevel'==0 means use default 'compressionLevel' value. - Values above 16 behave the same as 16. - Equivalent variants exist for all other compression functions below. -*/ - /* Note : -Decompression functions are provided within LZ4 source code (see "lz4.h") (BSD license) + Decompression functions are provided within LZ4 source code (see "lz4.h") (BSD license) */ -/************************************** - Using an external allocation -**************************************/ int LZ4_sizeofStateHC(void); -int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize); -int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize); - -int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel); -int LZ4_compressHC2_limitedOutput_withStateHC(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); - +int LZ4_compress_HC_extStateHC(void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel); /* -These functions are provided should you prefer to allocate memory for compression tables with your own allocation methods. -To know how much memory must be allocated for the compression tables, use : -int LZ4_sizeofStateHC(); +LZ4_compress_HC_extStateHC() : + Use this function if you prefer to manually allocate memory for compression tables. + To know how much memory must be allocated for the compression tables, use : + int LZ4_sizeofStateHC(); -Note that tables must be aligned for pointer (32 or 64 bits), otherwise compression will fail (return code 0). + Allocated memory must be aligned on 8-bytes boundaries (which a normal malloc() will do properly). -The allocated memory can be provided to the compressions functions using 'void* state' parameter. -LZ4_compress_withStateHC() and LZ4_compress_limitedOutput_withStateHC() are equivalent to previously described functions. -They just use the externally allocated memory area instead of allocating their own (on stack, or on heap). + The allocated memory can then be provided to the compression functions using 'void* state' parameter. + LZ4_compress_HC_extStateHC() is equivalent to previously described function. + It just uses externally allocated memory for stateHC. */ /************************************** - Streaming Functions +* Streaming Compression **************************************/ -/* Note : these streaming functions still follows the older model */ -void* LZ4_createHC (const char* inputBuffer); -int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize); -int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize); -char* LZ4_slideInputBufferHC (void* LZ4HC_Data); -int LZ4_freeHC (void* LZ4HC_Data); - -int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel); -int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); - +#define LZ4_STREAMHCSIZE 262192 +#define LZ4_STREAMHCSIZE_SIZET (LZ4_STREAMHCSIZE / sizeof(size_t)) +typedef struct { size_t table[LZ4_STREAMHCSIZE_SIZET]; } LZ4_streamHC_t; /* -These functions allow the compression of dependent blocks, where each block benefits from prior 64 KB within preceding blocks. -In order to achieve this, it is necessary to start creating the LZ4HC Data Structure, thanks to the function : - -void* LZ4_createHC (const char* inputBuffer); -The result of the function is the (void*) pointer on the LZ4HC Data Structure. -This pointer will be needed in all other functions. -If the pointer returned is NULL, then the allocation has failed, and compression must be aborted. -The only parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer. -The input buffer must be already allocated, and size at least 192KB. -'inputBuffer' will also be the 'const char* source' of the first block. - -All blocks are expected to lay next to each other within the input buffer, starting from 'inputBuffer'. -To compress each block, use either LZ4_compressHC_continue() or LZ4_compressHC_limitedOutput_continue(). -Their behavior are identical to LZ4_compressHC() or LZ4_compressHC_limitedOutput(), -but require the LZ4HC Data Structure as their first argument, and check that each block starts right after the previous one. -If next block does not begin immediately after the previous one, the compression will fail (return 0). - -When it's no longer possible to lay the next block after the previous one (not enough space left into input buffer), a call to : -char* LZ4_slideInputBufferHC(void* LZ4HC_Data); -must be performed. It will typically copy the latest 64KB of input at the beginning of input buffer. -Note that, for this function to work properly, minimum size of an input buffer must be 192KB. -==> The memory position where the next input data block must start is provided as the result of the function. - -Compression can then resume, using LZ4_compressHC_continue() or LZ4_compressHC_limitedOutput_continue(), as usual. - -When compression is completed, a call to LZ4_freeHC() will release the memory used by the LZ4HC Data Structure. + LZ4_streamHC_t + This structure allows static allocation of LZ4 HC streaming state. + State must then be initialized using LZ4_resetStreamHC() before first use. + + Static allocation should only be used in combination with static linking. + If you want to use LZ4 as a DLL, please use construction functions below, which are future-proof. */ -int LZ4_sizeofStreamStateHC(void); -int LZ4_resetStreamStateHC(void* state, const char* inputBuffer); +LZ4_streamHC_t* LZ4_createStreamHC(void); +int LZ4_freeStreamHC (LZ4_streamHC_t* streamHCPtr); /* -These functions achieve the same result as : -void* LZ4_createHC (const char* inputBuffer); + These functions create and release memory for LZ4 HC streaming state. + Newly created states are already initialized. + Existing state space can be re-used anytime using LZ4_resetStreamHC(). + If you use LZ4 as a DLL, use these functions instead of static structure allocation, + to avoid size mismatch between different versions. +*/ -They are provided here to allow the user program to allocate memory using its own routines. +void LZ4_resetStreamHC (LZ4_streamHC_t* streamHCPtr, int compressionLevel); +int LZ4_loadDictHC (LZ4_streamHC_t* streamHCPtr, const char* dictionary, int dictSize); -To know how much space must be allocated, use LZ4_sizeofStreamStateHC(); -Note also that space must be aligned for pointers (32 or 64 bits). +int LZ4_compress_HC_continue (LZ4_streamHC_t* streamHCPtr, const char* src, char* dst, int srcSize, int maxDstSize); -Once space is allocated, you must initialize it using : LZ4_resetStreamStateHC(void* state, const char* inputBuffer); -void* state is a pointer to the space allocated. -It must be aligned for pointers (32 or 64 bits), and be large enough. -The parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer. -The input buffer must be already allocated, and size at least 192KB. -'inputBuffer' will also be the 'const char* source' of the first block. +int LZ4_saveDictHC (LZ4_streamHC_t* streamHCPtr, char* safeBuffer, int maxDictSize); -The same space can be re-used multiple times, just by initializing it each time with LZ4_resetStreamState(). -return value of LZ4_resetStreamStateHC() must be 0 is OK. -Any other value means there was an error (typically, state is not aligned for pointers (32 or 64 bits)). +/* + These functions compress data in successive blocks of any size, using previous blocks as dictionary. + One key assumption is that previous blocks (up to 64 KB) remain read-accessible while compressing next blocks. + There is an exception for ring buffers, which can be smaller 64 KB. + Such case is automatically detected and correctly handled by LZ4_compress_HC_continue(). + + Before starting compression, state must be properly initialized, using LZ4_resetStreamHC(). + A first "fictional block" can then be designated as initial dictionary, using LZ4_loadDictHC() (Optional). + + Then, use LZ4_compress_HC_continue() to compress each successive block. + It works like LZ4_compress_HC(), but use previous memory blocks as dictionary to improve compression. + Previous memory blocks (including initial dictionary when present) must remain accessible and unmodified during compression. + As a reminder, size 'dst' buffer to handle worst cases, using LZ4_compressBound(), to ensure success of compression operation. + + If, for any reason, previous data blocks can't be preserved unmodified in memory during next compression block, + you must save it to a safer memory space, using LZ4_saveDictHC(). + Return value of LZ4_saveDictHC() is the size of dictionary effectively saved into 'safeBuffer'. */ + +/************************************** +* Deprecated Functions +**************************************/ +/* Deprecate Warnings */ +/* Should these warnings messages be a problem, + it is generally possible to disable them, + with -Wno-deprecated-declarations for gcc + or _CRT_SECURE_NO_WARNINGS in Visual for example. + You can also define LZ4_DEPRECATE_WARNING_DEFBLOCK. */ +#ifndef LZ4_DEPRECATE_WARNING_DEFBLOCK +# define LZ4_DEPRECATE_WARNING_DEFBLOCK +# define LZ4_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) +# if (LZ4_GCC_VERSION >= 405) || defined(__clang__) +# define LZ4_DEPRECATED(message) __attribute__((deprecated(message))) +# elif (LZ4_GCC_VERSION >= 301) +# define LZ4_DEPRECATED(message) __attribute__((deprecated)) +# elif defined(_MSC_VER) +# define LZ4_DEPRECATED(message) __declspec(deprecated(message)) +# else +# pragma message("WARNING: You need to implement LZ4_DEPRECATED for this compiler") +# define LZ4_DEPRECATED(message) +# endif +#endif // LZ4_DEPRECATE_WARNING_DEFBLOCK + +/* compression functions */ +/* these functions are planned to trigger warning messages by r131 approximately */ +int LZ4_compressHC (const char* source, char* dest, int inputSize); +int LZ4_compressHC_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compressHC2 (const char* source, char* dest, int inputSize, int compressionLevel); +int LZ4_compressHC2_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); +int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize); +int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize); +int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel); +int LZ4_compressHC2_limitedOutput_withStateHC(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); +int LZ4_compressHC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize); +int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize); + +/* Streaming functions following the older model; should no longer be used */ +LZ4_DEPRECATED("use LZ4_createStreamHC() instead") void* LZ4_createHC (char* inputBuffer); +LZ4_DEPRECATED("use LZ4_saveDictHC() instead") char* LZ4_slideInputBufferHC (void* LZ4HC_Data); +LZ4_DEPRECATED("use LZ4_freeStreamHC() instead") int LZ4_freeHC (void* LZ4HC_Data); +LZ4_DEPRECATED("use LZ4_compress_HC_continue() instead") int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel); +LZ4_DEPRECATED("use LZ4_compress_HC_continue() instead") int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel); +LZ4_DEPRECATED("use LZ4_createStreamHC() instead") int LZ4_sizeofStreamStateHC(void); +LZ4_DEPRECATED("use LZ4_resetStreamHC() instead") int LZ4_resetStreamStateHC(void* state, char* inputBuffer); + + #if defined (__cplusplus) } #endif http://git-wip-us.apache.org/repos/asf/hadoop/blob/4c061e60/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/src/codec/Lz4Codec.cc ---------------------------------------------------------------------- diff --git a/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/src/codec/Lz4Codec.cc b/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/src/codec/Lz4Codec.cc index 48c96b5..063e7e0 100644 --- a/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/src/codec/Lz4Codec.cc +++ b/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/src/codec/Lz4Codec.cc @@ -35,7 +35,7 @@ Lz4CompressStream::Lz4CompressStream(OutputStream * stream, uint32_t bufferSizeH void Lz4CompressStream::compressOneBlock(const void * buff, uint32_t length) { size_t compressedLength = _tempBufferSize - 8; - int ret = LZ4_compress((char*)buff, _tempBuffer + 8, length); + int ret = LZ4_compress_default((char*)buff, _tempBuffer + 8, length, LZ4_compressBound(length)); if (ret > 0) { compressedLength = ret; ((uint32_t*)_tempBuffer)[0] = bswap(length); http://git-wip-us.apache.org/repos/asf/hadoop/blob/4c061e60/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/test/TestCompressions.cc ---------------------------------------------------------------------- diff --git a/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/test/TestCompressions.cc b/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/test/TestCompressions.cc index c998589..fa7ae3f 100644 --- a/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/test/TestCompressions.cc +++ b/hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-nativetask/src/main/native/test/TestCompressions.cc @@ -185,7 +185,7 @@ void MeasureSingleFileLz4(const string & path, CompressResult & total, size_t bl size_t currentblocksize = std::min(data.length() - start, blockSize); uint64_t startTime = t.now(); for (int i = 0; i < times; i++) { - int osize = LZ4_compress((char*)data.data() + start, outputBuffer, currentblocksize); + int osize = LZ4_compress_default((char*)data.data() + start, outputBuffer, currentblocksize, LZ4_compressBound(currentblocksize)); result.compressedSize += osize; result.uncompressedSize += currentblocksize; }
