http://git-wip-us.apache.org/repos/asf/hadoop/blob/4bff073b/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 3e74002..44ada14 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,8 +1,7 @@ /* LZ4 - Fast LZ compression algorithm Header File - Copyright (C) 2011-2015, Yann Collet. - + 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 @@ -29,7 +28,7 @@ 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 source repository : http://code.google.com/p/lz4/ - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c */ #pragma once @@ -39,22 +38,22 @@ extern "C" { #endif /* - * 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. + * 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. */ /************************************** -* Version + Version **************************************/ -#define LZ4_VERSION_MAJOR 1 /* for breaking interface changes */ -#define LZ4_VERSION_MINOR 7 /* for new (non-breaking) interface capabilities */ +#define LZ4_VERSION_MAJOR 1 /* for major interface/format changes */ +#define LZ4_VERSION_MINOR 3 /* for minor interface/format changes */ #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 : @@ -67,90 +66,77 @@ int LZ4_versionNumber (void); /************************************** -* Simple Functions + Simple Functions **************************************/ -int LZ4_compress_default(const char* source, char* dest, int sourceSize, int maxDestSize); +int LZ4_compress (const char* source, char* dest, int sourceSize); int LZ4_decompress_safe (const char* source, char* dest, int compressedSize, int maxDecompressedSize); /* -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_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_decompress_safe() : - 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). + 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). 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, including malicious data packets. - It never writes outside output buffer, nor reads outside input buffer. + 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. */ /************************************** -* Advanced Functions + Advanced Functions **************************************/ #define LZ4_MAX_INPUT_SIZE 0x7E000000 /* 2 113 929 216 bytes */ -#define LZ4_COMPRESSBOUND(isize) ((unsigned)(isize) > (unsigned)LZ4_MAX_INPUT_SIZE ? 0 : (isize) + ((isize)/255) + 16) +#define LZ4_COMPRESSBOUND(isize) ((unsigned int)(isize) > (unsigned int)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 (destination buffer size). + This function is primarily useful for memory allocation purposes (output buffer size). Macro LZ4_COMPRESSBOUND() is also provided for compilation-time evaluation (stack memory allocation for example). - 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 inputSize); -/* -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. + 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) */ -int LZ4_compress_fast (const char* source, char* dest, int sourceSize, int maxDestSize, int acceleration); +int LZ4_compressBound(int isize); /* -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 allocate it on 8-bytes boundaries (using malloc() typically). - Then, provide it as 'void* state' to compression function. +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 */ -int LZ4_sizeofState(void); -int LZ4_compress_fast_extState (void* state, const char* source, char* dest, int inputSize, int maxDestSize, int acceleration); +int LZ4_compress_limitedOutput (const char* source, char* dest, int sourceSize, int maxOutputSize); /* -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 +LZ4_compress_withState() : + Same compression functions, but 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. */ -int LZ4_compress_destSize (const char* source, char* dest, int* sourceSizePtr, int targetDestSize); +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); /* @@ -166,6 +152,7 @@ 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' @@ -182,108 +169,104 @@ int LZ4_decompress_safe_partial (const char* source, char* dest, int compressedS /*********************************************** -* Streaming Compression Functions + Experimental Streaming Compression Functions ***********************************************/ -#define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE-3)) + 4) -#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U64 * sizeof(long long)) + +#define LZ4_STREAMSIZE_U32 ((1 << (LZ4_MEMORY_USAGE-2)) + 8) +#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U32 * sizeof(unsigned int)) /* * 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 { long long table[LZ4_STREAMSIZE_U64]; } LZ4_stream_t; +typedef struct { unsigned int table[LZ4_STREAMSIZE_U32]; } LZ4_stream_t; /* * LZ4_resetStream * Use this function to init an allocated LZ4_stream_t structure */ -void LZ4_resetStream (LZ4_stream_t* streamPtr); +void LZ4_resetStream (LZ4_stream_t* LZ4_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* streamPtr); +int LZ4_freeStream (LZ4_stream_t* LZ4_stream); /* * 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 : dictionary size, in bytes (necessarily <= 64 KB) + * Return : 1 if OK, 0 if error */ -int LZ4_loadDict (LZ4_stream_t* streamPtr, const char* dictionary, int dictSize); +int LZ4_loadDict (LZ4_stream_t* LZ4_stream, const char* dictionary, int dictSize); /* - * 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. + * 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. */ -int LZ4_compress_fast_continue (LZ4_stream_t* streamPtr, const char* src, char* dst, int srcSize, int maxDstSize, int acceleration); +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); /* * 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 LZ4_compress_fast_continue() - * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error + * 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. */ -int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int dictSize); +int LZ4_saveDict (LZ4_stream_t* LZ4_stream, char* safeBuffer, int dictSize); /************************************************ -* Streaming Decompression Functions + Experimental Streaming Decompression Functions ************************************************/ -#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; +#define LZ4_STREAMDECODESIZE_U32 4 +#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int)) /* * LZ4_streamDecode_t * information structure to track an LZ4 stream. - * 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. + * important : init this structure content using LZ4_setStreamDecode or memset() before first use ! */ -LZ4_streamDecode_t* LZ4_createStreamDecode(void); -int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); +typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t; /* * LZ4_setStreamDecode * Use this function to instruct where to find the dictionary. - * Setting a size of 0 is allowed (same effect as reset). + * 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). * 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* 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() + 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() */ 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); @@ -293,8 +276,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_setStreamDecode() followed by LZ4_decompress_x_continue() - They are stand-alone. They don't need nor update an LZ4_streamDecode_t structure. + a combination of LZ4_setDictDecode() followed by LZ4_decompress_x_continue() + They don't use 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); @@ -302,57 +285,37 @@ int LZ4_decompress_fast_usingDict (const char* source, char* dest, int originalS /************************************** -* Obsolete Functions + Obsolete 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 */ - -/* 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 */ +/* +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 */ /* 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 */ -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); +void* LZ4_create (const char* inputBuffer); +int LZ4_sizeofStreamState(void); +int LZ4_resetStreamState(void* state, const char* inputBuffer); +char* LZ4_slideInputBuffer (void* state); /* Obsolete streaming decoding functions */ -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); +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); #if defined (__cplusplus)
http://git-wip-us.apache.org/repos/asf/hadoop/blob/4bff073b/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 bbe7a9d..34a6173 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,279 +1,566 @@ /* - 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 + 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/ */ /************************************** -* Tuning Parameter + Tuning Parameter **************************************/ -static const int LZ4HC_compressionLevel_default = 9; +#define LZ4HC_DEFAULT_COMPRESSIONLEVEL 8 /************************************** -* Includes + Memory routines **************************************/ -#include "lz4hc.h" +#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 /************************************** -* Local Compiler Options + Compiler Options **************************************/ -#if defined(__GNUC__) -# pragma GCC diagnostic ignored "-Wunused-function" +#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ +/* "restrict" is a known keyword */ +#else +# define restrict /* Disable restrict */ #endif -#if defined (__clang__) -# pragma clang diagnostic ignored "-Wunused-function" +#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))) #endif /************************************** -* Common LZ4 definition + Includes **************************************/ -#define LZ4_COMMONDEFS_ONLY -#include "lz4.c" +#include "lz4hc.h" +#include "lz4.h" /************************************** -* Local Constants + Basic Types **************************************/ +#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ +# include <stdint.h> + typedef uint8_t BYTE; + typedef uint16_t U16; + typedef uint32_t U32; + typedef int32_t S32; + typedef uint64_t U64; +#else + typedef unsigned char BYTE; + typedef unsigned short U16; + typedef unsigned int U32; + typedef signed int S32; + typedef unsigned long long U64; +#endif + +#if defined(__GNUC__) && !defined(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 (MAXD - 1) +#define MAXD_MASK ((U32)(MAXD - 1)) +#define MAX_DISTANCE (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) -static const int g_maxCompressionLevel = 16; +#define KB *(1U<<10) +#define MB *(1U<<20) +#define GB *(1U<<30) /************************************** -* Local Types + 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 **************************************/ typedef struct { - 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; + const BYTE* inputBuffer; + const BYTE* base; + const BYTE* end; + HTYPE hashTable[HASHTABLESIZE]; + U16 chainTable[MAXD]; + const BYTE* nextToUpdate; } LZ4HC_Data_Structure; /************************************** -* Local Macros + 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 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)); } - +#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)) /************************************** -* HC Compression + Private functions **************************************/ -static void LZ4HC_init (LZ4HC_Data_Structure* hc4, const BYTE* start) +#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) { MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); - 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; + 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); } /* Update chains up to ip (excluded) */ FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip) { - U16* chainTable = hc4->chainTable; - U32* HashTable = hc4->hashTable; - const BYTE* const base = hc4->base; - const U32 target = (U32)(ip - base); - U32 idx = hc4->nextToUpdate; + U16* chainTable = hc4->chainTable; + HTYPE* HashTable = hc4->hashTable; + INITBASE(base,hc4->base); - while(idx < target) + while(hc4->nextToUpdate < ip) { - U32 h = LZ4HC_hashPtr(base+idx); - size_t delta = idx - HashTable[h]; + const BYTE* const p = hc4->nextToUpdate; + size_t delta = (p) - HASH_POINTER(p); if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; - DELTANEXTU16(idx) = (U16)delta; - HashTable[h] = idx; - idx++; + DELTANEXT(p) = (U16)delta; + HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base); + hc4->nextToUpdate++; } +} + + +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); +} - hc4->nextToUpdate = target; + +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); } -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) +FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos, const int maxNbAttempts) { U16* const chainTable = hc4->chainTable; - 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; + HTYPE* const HashTable = hc4->hashTable; + const BYTE* ref; + INITBASE(base,hc4->base); int nbAttempts=maxNbAttempts; - size_t ml=0; + size_t repl=0, ml=0; + U16 delta=0; /* useless assignment, to remove an uninitialization warning */ /* HC4 match finder */ LZ4HC_Insert(hc4, ip); - matchIndex = HashTable[LZ4HC_hashPtr(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 - while ((matchIndex>=lowLimit) && (nbAttempts)) + while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) { nbAttempts--; - if (matchIndex >= dictLimit) + if (*(ref+ml) == *(ip+ml)) + if (A32(ref) == A32(ip)) { - 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; } - } + size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH; + if (mlt > ml) { ml = mlt; *matchpos = ref; } } - else + 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) { - 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 */ - } + DELTANEXT(ptr) = delta; /* Pre-Load */ + ptr++; } - matchIndex -= DELTANEXTU16(matchIndex); + do + { + DELTANEXT(ptr) = delta; + HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); /* Head of chain */ + ptr++; + } while(ptr < end); + hc4->nextToUpdate = end; } +#endif return (int)ml; } -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) +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) { - 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; + U16* const chainTable = hc4->chainTable; + HTYPE* const HashTable = hc4->hashTable; + INITBASE(base,hc4->base); + const BYTE* ref; int nbAttempts = maxNbAttempts; - int delta = (int)(ip-iLowLimit); - + int delta = (int)(ip-startLimit); /* First Match */ LZ4HC_Insert(hc4, ip); - matchIndex = HashTable[LZ4HC_hashPtr(ip)]; + ref = HASH_POINTER(ip); - while ((matchIndex>=lowLimit) && (nbAttempts)) + while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts)) { nbAttempts--; - if (matchIndex >= dictLimit) + if (*(startLimit + longest) == *(ref - delta + longest)) + if (A32(ref) == A32(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; +#if 1 + const BYTE* reft = ref+MINMATCH; + const BYTE* ipt = ip+MINMATCH; + const BYTE* startt = ip; - while ((ip+back>iLowLimit) - && (matchPtr+back > lowPrefixPtr) - && (ip[back-1] == matchPtr[back-1])) - back--; + 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 - mlt -= back; + while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;} - 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)) + if ((ipt-startt) > longest) { - 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; } + longest = (int)(ipt-startt); + *matchpos = reft; + *startpos = startt; } } - matchIndex -= DELTANEXTU16(matchIndex); + ref = GETNEXT(ref); } return longest; @@ -282,44 +569,34 @@ FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( 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* const match, - limitedOutput_directive limitedOutputBuffer, - BYTE* oend) + const BYTE** ip, + BYTE** op, + const BYTE** anchor, + int matchLength, + const BYTE* ref, + 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>>8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */ + if ((limitedOutputBuffer) && ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > 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_wildCopy(*op, *anchor, (*op) + length); - *op += length; + LZ4_BLINDCOPY(*anchor, *op, length); /* Encode Offset */ - LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2; + LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref)); /* Encode MatchLength */ length = (int)(matchLength-MINMATCH); - if ((limitedOutputBuffer) && (*op + (length>>8) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */ + if ((limitedOutputBuffer) && (*op + (1 + LASTLITERALS) + (length>>8) > 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); @@ -331,15 +608,16 @@ 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; @@ -351,7 +629,7 @@ static int LZ4HC_compress_generic ( BYTE* op = (BYTE*) dest; BYTE* const oend = op + maxOutputSize; - unsigned maxNbAttempts; + const int maxNbAttempts = compressionLevel > MAX_COMPRESSION_LEVEL ? 1 << MAX_COMPRESSION_LEVEL : compressionLevel ? 1<<(compressionLevel-1) : 1<<LZ4HC_DEFAULT_COMPRESSIONLEVEL; int ml, ml2, ml3, ml0; const BYTE* ref=NULL; const BYTE* start2=NULL; @@ -362,10 +640,8 @@ static int LZ4HC_compress_generic ( const BYTE* ref0; - /* init */ - if (compressionLevel > g_maxCompressionLevel) compressionLevel = g_maxCompressionLevel; - if (compressionLevel < 1) compressionLevel = LZ4HC_compressionLevel_default; - maxNbAttempts = 1 << (compressionLevel-1); + /* Ensure blocks follow each other */ + if (ip != ctx->end) return 0; ctx->end += inputSize; ip++; @@ -413,10 +689,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; @@ -484,9 +760,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) @@ -518,6 +794,7 @@ _Search3: ml2 = ml3; goto _Search3; + } /* Encode Last Literals */ @@ -535,182 +812,73 @@ _Search3: } -int LZ4_sizeofStateHC(void) { return sizeof(LZ4HC_Data_Structure); } - -int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel) +int LZ4_compressHC2(const char* source, char* dest, int inputSize, 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); -} - -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); -} + void* ctx = LZ4_createHC(source); + int result; + if (ctx==NULL) return 0; + result = LZ4HC_compress_generic (ctx, source, dest, inputSize, 0, compressionLevel, noLimit); - -/************************************** -* 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; } - - -/* 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; + LZ4_freeHC(ctx); + return result; } -int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) -{ - 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; -} +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; -/* compression */ + result = LZ4HC_compress_generic (ctx, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); -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 */ + LZ4_freeHC(ctx); + return result; } -static int LZ4_compressHC_continue_generic (LZ4HC_Data_Structure* ctxPtr, - const char* source, char* dest, - int inputSize, int maxOutputSize, limitedOutput_directive limit) +int LZ4_compressHC_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { - /* 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); - } + return LZ4_compressHC2_limitedOutput(source, dest, inputSize, maxOutputSize, 0); +} - /* 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; - } - } +/***************************** + Using external allocation +*****************************/ +int LZ4_sizeofStateHC() { return sizeof(LZ4HC_Data_Structure); } - 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) +int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel) { - 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); + 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); } +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_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize) +int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) { - 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; + 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); } +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; -} -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; -} +/**************************** + Stream functions +****************************/ -int LZ4_freeHC (void* LZ4HC_Data) +int LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize) { - FREEMEM(LZ4HC_Data); - return (0); + return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, 0, noLimit); } int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel) @@ -718,14 +886,12 @@ 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_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) +int LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize) { - return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); + return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, 0, limitedOutput); } -char* LZ4_slideInputBufferHC(void* LZ4HC_Data) +int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel) { - 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); + return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput); } http://git-wip-us.apache.org/repos/asf/hadoop/blob/4bff073b/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 431f7c8..deb2394 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-2015, Yann Collet. + 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 @@ -28,8 +28,8 @@ 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 + - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html + - LZ4 source repository : http://code.google.com/p/lz4/ */ #pragma once @@ -38,150 +38,134 @@ 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") +*/ -/************************************** -* Block Compression -**************************************/ -int LZ4_compress_HC (const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel); +int LZ4_compressHC_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize); /* -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. +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. */ +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_compress_HC_extStateHC(void* state, const char* src, char* dst, int srcSize, int maxDstSize, 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); + /* -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(); +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(); - Allocated memory must be aligned on 8-bytes boundaries (which a normal malloc() will do properly). +Note that tables must be aligned for pointer (32 or 64 bits), otherwise compression will fail (return code 0). - 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. +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). */ /************************************** -* Streaming Compression + Streaming Functions **************************************/ -#define LZ4_STREAMHCSIZE 262192 -#define LZ4_STREAMHCSIZE_SIZET (LZ4_STREAMHCSIZE / sizeof(size_t)) -typedef struct { size_t table[LZ4_STREAMHCSIZE_SIZET]; } LZ4_streamHC_t; -/* - 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. -*/ +/* 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); -LZ4_streamHC_t* LZ4_createStreamHC(void); -int LZ4_freeStreamHC (LZ4_streamHC_t* streamHCPtr); /* - 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. +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. */ -void LZ4_resetStreamHC (LZ4_streamHC_t* streamHCPtr, int compressionLevel); -int LZ4_loadDictHC (LZ4_streamHC_t* streamHCPtr, const char* dictionary, int dictSize); - -int LZ4_compress_HC_continue (LZ4_streamHC_t* streamHCPtr, const char* src, char* dst, int srcSize, int maxDstSize); - -int LZ4_saveDictHC (LZ4_streamHC_t* streamHCPtr, char* safeBuffer, int maxDictSize); +int LZ4_sizeofStreamStateHC(void); +int LZ4_resetStreamStateHC(void* state, const char* inputBuffer); /* - 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'. -*/ +These functions achieve the same result as : +void* LZ4_createHC (const char* inputBuffer); +They are provided here to allow the user program to allocate memory using its own routines. +To know how much space must be allocated, use LZ4_sizeofStreamStateHC(); +Note also that space must be aligned for pointers (32 or 64 bits). -/************************************** -* 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); +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. + +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)). +*/ #if defined (__cplusplus) http://git-wip-us.apache.org/repos/asf/hadoop/blob/4bff073b/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 063e7e0..48c96b5 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_default((char*)buff, _tempBuffer + 8, length, LZ4_compressBound(length)); + int ret = LZ4_compress((char*)buff, _tempBuffer + 8, length); if (ret > 0) { compressedLength = ret; ((uint32_t*)_tempBuffer)[0] = bswap(length); http://git-wip-us.apache.org/repos/asf/hadoop/blob/4bff073b/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 fa7ae3f..c998589 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_default((char*)data.data() + start, outputBuffer, currentblocksize, LZ4_compressBound(currentblocksize)); + int osize = LZ4_compress((char*)data.data() + start, outputBuffer, currentblocksize); result.compressedSize += osize; result.uncompressedSize += currentblocksize; }
