diff options
| -rw-r--r-- | INSTALL | 2 | ||||
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | include/linux/lz4.h | 651 | ||||
| -rw-r--r-- | linux/lz4_compress.c | 930 | ||||
| -rw-r--r-- | linux/lz4_decompress.c | 492 | ||||
| -rw-r--r-- | linux/lz4defs.h | 228 |
6 files changed, 6 insertions, 2303 deletions
@@ -14,6 +14,6 @@ Dependencies: On debian, you can install these with apt install -y pkg-config libblkid-dev uuid-dev libscrypt-dev libsodium-dev libkeyutils-dev liburcu-dev zlib1g-dev libzstd-dev libattr1-dev - libaio-dev + libaio-dev liblz4-dev Then, just make && make install @@ -31,15 +31,11 @@ ifdef D CFLAGS+=-DCONFIG_BCACHEFS_DEBUG=y endif -PKGCONFIG_LIBS="blkid uuid liburcu libsodium zlib" -PKGCONFIG_LIBS_STATIC="libzstd" +PKGCONFIG_LIBS="blkid uuid liburcu libsodium zlib liblz4 libzstd" CFLAGS+=`pkg-config --cflags ${PKGCONFIG_LIBS}` LDLIBS+=`pkg-config --libs ${PKGCONFIG_LIBS}` -CFLAGS+=`pkg-config --static --cflags ${PKGCONFIG_LIBS_STATIC}` -LDLIBS+=`pkg-config --static --libs ${PKGCONFIG_LIBS_STATIC}` - LDLIBS+=-lm -lpthread -lrt -lscrypt -lkeyutils -laio ifeq ($(PREFIX),/usr) diff --git a/include/linux/lz4.h b/include/linux/lz4.h index 394e3d92..86e1dde3 100644 --- a/include/linux/lz4.h +++ b/include/linux/lz4.h @@ -1,648 +1,5 @@ -/* LZ4 Kernel Interface - * - * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com> - * Copyright (C) 2016, Sven Schmidt <4sschmid@informatik.uni-hamburg.de> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * - * This file is based on the original header file - * for LZ4 - Fast LZ compression algorithm. - * - * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011-2016, 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://www.lz4.org - * - LZ4 source repository : https://github.com/lz4/lz4 - */ +#include <lz4.h> -#ifndef __LZ4_H__ -#define __LZ4_H__ - -#include <linux/types.h> -#include <linux/string.h> /* memset, memcpy */ - -/*-************************************************************************ - * CONSTANTS - **************************************************************************/ -/* - * LZ4_MEMORY_USAGE : - * Memory usage formula : N->2^N Bytes - * (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) - * Increasing memory usage improves compression ratio - * Reduced memory usage can improve speed, due to cache effect - * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache - */ -#define LZ4_MEMORY_USAGE 14 - -#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_ACCELERATION_DEFAULT 1 -#define LZ4_HASHLOG (LZ4_MEMORY_USAGE-2) -#define LZ4_HASHTABLESIZE (1 << LZ4_MEMORY_USAGE) -#define LZ4_HASH_SIZE_U32 (1 << LZ4_HASHLOG) - -#define LZ4HC_MIN_CLEVEL 3 -#define LZ4HC_DEFAULT_CLEVEL 9 -#define LZ4HC_MAX_CLEVEL 16 - -#define LZ4HC_DICTIONARY_LOGSIZE 16 -#define LZ4HC_MAXD (1<<LZ4HC_DICTIONARY_LOGSIZE) -#define LZ4HC_MAXD_MASK (LZ4HC_MAXD - 1) -#define LZ4HC_HASH_LOG (LZ4HC_DICTIONARY_LOGSIZE - 1) -#define LZ4HC_HASHTABLESIZE (1 << LZ4HC_HASH_LOG) -#define LZ4HC_HASH_MASK (LZ4HC_HASHTABLESIZE - 1) - -/*-************************************************************************ - * STREAMING CONSTANTS AND STRUCTURES - **************************************************************************/ -#define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE - 3)) + 4) -#define LZ4_STREAMSIZE (LZ4_STREAMSIZE_U64 * sizeof(unsigned long long)) - -#define LZ4_STREAMHCSIZE 262192 -#define LZ4_STREAMHCSIZE_SIZET (262192 / sizeof(size_t)) - -#define LZ4_STREAMDECODESIZE_U64 4 -#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U64 * \ - sizeof(unsigned long long)) - -/* - * LZ4_stream_t - information structure to track an LZ4 stream. - */ -typedef struct { - uint32_t hashTable[LZ4_HASH_SIZE_U32]; - uint32_t currentOffset; - uint32_t initCheck; - const uint8_t *dictionary; - uint8_t *bufferStart; - uint32_t dictSize; -} LZ4_stream_t_internal; -typedef union { - unsigned long long table[LZ4_STREAMSIZE_U64]; - LZ4_stream_t_internal internal_donotuse; -} LZ4_stream_t; - -/* - * LZ4_streamHC_t - information structure to track an LZ4HC stream. - */ -typedef struct { - unsigned int hashTable[LZ4HC_HASHTABLESIZE]; - unsigned short chainTable[LZ4HC_MAXD]; - /* next block to continue on current prefix */ - const unsigned char *end; - /* All index relative to this position */ - const unsigned char *base; - /* alternate base for extDict */ - const unsigned char *dictBase; - /* below that point, need extDict */ - unsigned int dictLimit; - /* below that point, no more dict */ - unsigned int lowLimit; - /* index from which to continue dict update */ - unsigned int nextToUpdate; - unsigned int compressionLevel; -} LZ4HC_CCtx_internal; -typedef union { - size_t table[LZ4_STREAMHCSIZE_SIZET]; - LZ4HC_CCtx_internal internal_donotuse; -} LZ4_streamHC_t; - -/* - * LZ4_streamDecode_t - information structure to track an - * LZ4 stream during decompression. - * - * init this structure using LZ4_setStreamDecode (or memset()) before first use - */ -typedef struct { - const uint8_t *externalDict; - size_t extDictSize; - const uint8_t *prefixEnd; - size_t prefixSize; -} LZ4_streamDecode_t_internal; -typedef union { - unsigned long long table[LZ4_STREAMDECODESIZE_U64]; - LZ4_streamDecode_t_internal internal_donotuse; -} LZ4_streamDecode_t; - -/*-************************************************************************ - * SIZE OF STATE - **************************************************************************/ -#define LZ4_MEM_COMPRESS LZ4_STREAMSIZE -#define LZ4HC_MEM_COMPRESS LZ4_STREAMHCSIZE - -/*-************************************************************************ - * Compression Functions - **************************************************************************/ - -/** - * LZ4_compressBound() - Max. output size in worst case szenarios - * @isize: Size of the input data - * - * Return: Max. size LZ4 may output in a "worst case" szenario - * (data not compressible) - */ -static inline int LZ4_compressBound(size_t isize) -{ - return LZ4_COMPRESSBOUND(isize); -} - -/** - * LZ4_compress_default() - Compress data from source to dest - * @source: source address of the original data - * @dest: output buffer address of the compressed data - * @inputSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE - * @maxOutputSize: full or partial size of buffer 'dest' - * which must be already allocated - * @wrkmem: address of the working memory. - * This requires 'workmem' of LZ4_MEM_COMPRESS. - * - * Compresses 'sourceSize' bytes from buffer 'source' - * into already allocated 'dest' buffer of size 'maxOutputSize'. - * Compression is guaranteed to succeed if - * 'maxOutputSize' >= LZ4_compressBound(inputSize). - * 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. - * - * Return: Number of bytes written into buffer 'dest' - * (necessarily <= maxOutputSize) or 0 if compression fails - */ -int LZ4_compress_default(const char *source, char *dest, int inputSize, - int maxOutputSize, void *wrkmem); - -/** - * LZ4_compress_fast() - As LZ4_compress_default providing an acceleration param - * @source: source address of the original data - * @dest: output buffer address of the compressed data - * @inputSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE - * @maxOutputSize: full or partial size of buffer 'dest' - * which must be already allocated - * @acceleration: acceleration factor - * @wrkmem: address of the working memory. - * This requires 'workmem' of LZ4_MEM_COMPRESS. - * - * 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 LZ4_ACCELERATION_DEFAULT, which is 1. - * - * Return: Number of bytes written into buffer 'dest' - * (necessarily <= maxOutputSize) or 0 if compression fails - */ -int LZ4_compress_fast(const char *source, char *dest, int inputSize, - int maxOutputSize, int acceleration, void *wrkmem); - -/** - * LZ4_compress_destSize() - Compress as much data as possible - * from source to dest - * @source: source address of the original data - * @dest: output buffer address of the compressed data - * @sourceSizePtr: will be modified to indicate how many bytes where read - * from 'source' to fill 'dest'. New value is necessarily <= old value. - * @targetDestSize: Size of buffer 'dest' which must be already allocated - * @wrkmem: address of the working memory. - * This requires 'workmem' of LZ4_MEM_COMPRESS. - * - * 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'. - * - * Return: Number of bytes written into 'dest' (necessarily <= targetDestSize) - * or 0 if compression fails - */ -int LZ4_compress_destSize(const char *source, char *dest, int *sourceSizePtr, - int targetDestSize, void *wrkmem); - -/*-************************************************************************ - * Decompression Functions - **************************************************************************/ - -/** - * LZ4_decompress_fast() - Decompresses data from 'source' into 'dest' - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated with 'originalSize' bytes - * @originalSize: is the original and therefore uncompressed size - * - * Decompresses data from 'source' into 'dest'. - * This function fully respect memory boundaries for properly formed - * compressed data. - * It is a bit faster than LZ4_decompress_safe(). - * However, it does not provide any protection against intentionally - * modified data stream (malicious input). - * Use this function in trusted environment only - * (data to decode comes from a trusted source). - * - * Return: number of bytes read from the source buffer - * or a negative result if decompression fails. - */ -int LZ4_decompress_fast(const char *source, char *dest, int originalSize); - -/** - * LZ4_decompress_safe() - Decompression protected against buffer overflow - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated - * @compressedSize: is the precise full size of the compressed block - * @maxDecompressedSize: is the size of 'dest' buffer - * - * Decompresses data fom 'source' into 'dest'. - * 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. - * - * Return: number of bytes decompressed into destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - */ -int LZ4_decompress_safe(const char *source, char *dest, int compressedSize, - int maxDecompressedSize); - -/** - * LZ4_decompress_safe_partial() - Decompress a block of size 'compressedSize' - * at position 'source' into buffer 'dest' - * @source: source address of the compressed data - * @dest: output buffer address of the decompressed data which must be - * already allocated - * @compressedSize: is the precise full size of the compressed block. - * @targetOutputSize: the decompression operation will try - * to stop as soon as 'targetOutputSize' has been reached - * @maxDecompressedSize: is the size of destination buffer - * - * This function decompresses a compressed block of size 'compressedSize' - * at position 'source' into destination buffer 'dest' - * of size 'maxDecompressedSize'. - * The function tries to stop decompressing operation as soon as - * 'targetOutputSize' has been reached, reducing decompression time. - * This function never writes outside of output buffer, - * and never reads outside of input buffer. - * It is therefore protected against malicious data packets. - * - * Return: the number of bytes decoded in the destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - * - */ -int LZ4_decompress_safe_partial(const char *source, char *dest, - int compressedSize, int targetOutputSize, int maxDecompressedSize); - -/*-************************************************************************ - * LZ4 HC Compression - **************************************************************************/ - -/** - * LZ4_compress_HC() - Compress data from `src` into `dst`, using HC algorithm - * @src: source address of the original data - * @dst: output buffer address of the compressed data - * @srcSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE - * @dstCapacity: full or partial size of buffer 'dst', - * which must be already allocated - * @compressionLevel: Recommended values are between 4 and 9, although any - * value between 1 and LZ4HC_MAX_CLEVEL will work. - * Values >LZ4HC_MAX_CLEVEL behave the same as 16. - * @wrkmem: address of the working memory. - * This requires 'wrkmem' of size LZ4HC_MEM_COMPRESS. - * - * Compress data from 'src' into 'dst', using the more powerful - * but slower "HC" algorithm. Compression is guaranteed to succeed if - * `dstCapacity >= LZ4_compressBound(srcSize) - * - * Return : the number of bytes written into 'dst' or 0 if compression fails. - */ -int LZ4_compress_HC(const char *src, char *dst, int srcSize, int dstCapacity, - int compressionLevel, void *wrkmem); - -/** - * LZ4_resetStreamHC() - Init an allocated 'LZ4_streamHC_t' structure - * @streamHCPtr: pointer to the 'LZ4_streamHC_t' structure - * @compressionLevel: Recommended values are between 4 and 9, although any - * value between 1 and LZ4HC_MAX_CLEVEL will work. - * Values >LZ4HC_MAX_CLEVEL behave the same as 16. - * - * An LZ4_streamHC_t structure can be allocated once - * and re-used multiple times. - * Use this function to init an allocated `LZ4_streamHC_t` structure - * and start a new compression. - */ -void LZ4_resetStreamHC(LZ4_streamHC_t *streamHCPtr, int compressionLevel); - -/** - * LZ4_loadDictHC() - Load a static dictionary into LZ4_streamHC - * @streamHCPtr: pointer to the LZ4HC_stream_t - * @dictionary: dictionary to load - * @dictSize: size of dictionary - * - * Use this function to load a static dictionary into LZ4HC_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) - */ -int LZ4_loadDictHC(LZ4_streamHC_t *streamHCPtr, const char *dictionary, - int dictSize); - -/** - * LZ4_compress_HC_continue() - Compress 'src' using data from previously - * compressed blocks as a dictionary using the HC algorithm - * @streamHCPtr: Pointer to the previous 'LZ4_streamHC_t' structure - * @src: source address of the original data - * @dst: output buffer address of the compressed data, - * which must be already allocated - * @srcSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE - * @maxDstSize: full or partial size of buffer 'dest' - * which must be already allocated - * - * 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 than 64 KB. - * Ring buffers scenario is automatically detected and 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. Previous memory blocks - * (including initial dictionary when present) must remain accessible - * and unmodified during compression. - * 'dst' buffer should be sized to handle worst case scenarios, using - * LZ4_compressBound(), to ensure operation success. - * 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'. - * - * Return: Number of bytes written into buffer 'dst' or 0 if compression fails - */ -int LZ4_compress_HC_continue(LZ4_streamHC_t *streamHCPtr, const char *src, - char *dst, int srcSize, int maxDstSize); - -/** - * LZ4_saveDictHC() - Save static dictionary from LZ4HC_stream - * @streamHCPtr: pointer to the 'LZ4HC_stream_t' structure - * @safeBuffer: buffer to save dictionary to, must be already allocated - * @maxDictSize: size of 'safeBuffer' - * - * 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_loadDictHC() afterwards, - * dictionary is immediately usable, you can therefore call - * LZ4_compress_HC_continue(). - * - * Return : saved dictionary size in bytes (necessarily <= maxDictSize), - * or 0 if error. - */ -int LZ4_saveDictHC(LZ4_streamHC_t *streamHCPtr, char *safeBuffer, - int maxDictSize); - -/*-********************************************* - * Streaming Compression Functions - ***********************************************/ - -/** - * LZ4_resetStream() - Init an allocated 'LZ4_stream_t' structure - * @LZ4_stream: pointer to the 'LZ4_stream_t' structure - * - * An LZ4_stream_t structure can be allocated once - * and re-used multiple times. - * Use this function to init an allocated `LZ4_stream_t` structure - * and start a new compression. - */ -void LZ4_resetStream(LZ4_stream_t *LZ4_stream); - -/** - * LZ4_loadDict() - Load a static dictionary into LZ4_stream - * @streamPtr: pointer to the LZ4_stream_t - * @dictionary: dictionary to load - * @dictSize: size of dictionary - * - * 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) - */ -int LZ4_loadDict(LZ4_stream_t *streamPtr, const char *dictionary, - int dictSize); - -/** - * LZ4_saveDict() - Save static dictionary from LZ4_stream - * @streamPtr: pointer to the 'LZ4_stream_t' structure - * @safeBuffer: buffer to save dictionary to, must be already allocated - * @dictSize: size of 'safeBuffer' - * - * 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. - */ -int LZ4_saveDict(LZ4_stream_t *streamPtr, char *safeBuffer, int dictSize); - -/** - * LZ4_compress_fast_continue() - Compress 'src' using data from previously - * compressed blocks as a dictionary - * @streamPtr: Pointer to the previous 'LZ4_stream_t' structure - * @src: source address of the original data - * @dst: output buffer address of the compressed data, - * which must be already allocated - * @srcSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE - * @maxDstSize: full or partial size of buffer 'dest' - * which must be already allocated - * @acceleration: acceleration factor - * - * 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 ! - * If maxDstSize >= LZ4_compressBound(srcSize), - * compression is guaranteed to succeed, and runs faster. - * - * Return: Number of bytes written into buffer 'dst' or 0 if compression fails - */ -int LZ4_compress_fast_continue(LZ4_stream_t *streamPtr, const char *src, - char *dst, int srcSize, int maxDstSize, int acceleration); - -/** - * LZ4_setStreamDecode() - Instruct where to find dictionary - * @LZ4_streamDecode: the 'LZ4_streamDecode_t' structure - * @dictionary: dictionary to use - * @dictSize: size of dictionary - * - * Use this function to instruct where to find the 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); - -/** - * LZ4_decompress_fast_continue() - Decompress blocks in streaming mode - * @LZ4_streamDecode: the 'LZ4_streamDecode_t' structure - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated - * @compressedSize: is the precise full size of the compressed block - * @maxDecompressedSize: is the size of 'dest' buffer - * - * These decoding function allows 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. W - * 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() - * - * Return: number of bytes decompressed into destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - */ -int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, - const char *source, char *dest, int compressedSize, - int maxDecompressedSize); - -/** - * LZ4_decompress_fast_continue() - Decompress blocks in streaming mode - * @LZ4_streamDecode: the 'LZ4_streamDecode_t' structure - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated with 'originalSize' bytes - * @originalSize: is the original and therefore uncompressed size - * - * These decoding function allows 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. W - * 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() - * - * Return: number of bytes decompressed into destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - */ -int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, - const char *source, char *dest, int originalSize); - -/** - * LZ4_decompress_safe_usingDict() - Same as LZ4_setStreamDecode() - * followed by LZ4_decompress_safe_continue() - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated - * @compressedSize: is the precise full size of the compressed block - * @maxDecompressedSize: is the size of 'dest' buffer - * @dictStart: pointer to the start of the dictionary in memory - * @dictSize: size of dictionary - * - * These decoding function works the same as - * a combination of LZ4_setStreamDecode() followed by - * LZ4_decompress_safe_continue() - * It is stand-alone, and don'tn eed a LZ4_streamDecode_t structure. - * - * Return: number of bytes decompressed into destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - */ -int LZ4_decompress_safe_usingDict(const char *source, char *dest, - int compressedSize, int maxDecompressedSize, const char *dictStart, - int dictSize); - -/** - * LZ4_decompress_fast_usingDict() - Same as LZ4_setStreamDecode() - * followed by LZ4_decompress_fast_continue() - * @source: source address of the compressed data - * @dest: output buffer address of the uncompressed data - * which must be already allocated with 'originalSize' bytes - * @originalSize: is the original and therefore uncompressed size - * @dictStart: pointer to the start of the dictionary in memory - * @dictSize: size of dictionary - * - * These decoding function works the same as - * a combination of LZ4_setStreamDecode() followed by - * LZ4_decompress_safe_continue() - * It is stand-alone, and don'tn eed a LZ4_streamDecode_t structure. - * - * Return: number of bytes decompressed into destination buffer - * (necessarily <= maxDecompressedSize) - * or a negative result in case of error - */ -int LZ4_decompress_fast_usingDict(const char *source, char *dest, - int originalSize, const char *dictStart, int dictSize); - -#endif +#define LZ4_compress_destSize(src, dst, srclen, dstlen, workspace) \ + LZ4_compress_destSize(src, dst, srclen, dstlen) +#define LZ4_MEM_COMPRESS 0 diff --git a/linux/lz4_compress.c b/linux/lz4_compress.c deleted file mode 100644 index 091b57bb..00000000 --- a/linux/lz4_compress.c +++ /dev/null @@ -1,930 +0,0 @@ -/* - * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011 - 2016, 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://www.lz4.org - * - LZ4 source repository : https://github.com/lz4/lz4 - * - * Changed for kernel usage by: - * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> - */ - -/*-************************************ - * Dependencies - **************************************/ -#include <linux/lz4.h> -#include "lz4defs.h" -#include <linux/kernel.h> -#include <asm/unaligned.h> - -static const int LZ4_minLength = (MFLIMIT + 1); -static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1)); - -/*-****************************** - * Compression functions - ********************************/ -static FORCE_INLINE U32 LZ4_hash4( - U32 sequence, - tableType_t const tableType) -{ - if (tableType == byU16) - return ((sequence * 2654435761U) - >> ((MINMATCH * 8) - (LZ4_HASHLOG + 1))); - else - return ((sequence * 2654435761U) - >> ((MINMATCH * 8) - LZ4_HASHLOG)); -} - -static FORCE_INLINE U32 LZ4_hash5( - U64 sequence, - tableType_t const tableType) -{ - const U32 hashLog = (tableType == byU16) - ? LZ4_HASHLOG + 1 - : LZ4_HASHLOG; - -#if LZ4_LITTLE_ENDIAN - static const U64 prime5bytes = 889523592379ULL; - - return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); -#else - static const U64 prime8bytes = 11400714785074694791ULL; - - return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog)); -#endif -} - -static FORCE_INLINE U32 LZ4_hashPosition( - const void *p, - tableType_t const tableType) -{ -#if LZ4_ARCH64 - if (tableType == byU32) - return LZ4_hash5(LZ4_read_ARCH(p), tableType); -#endif - - return LZ4_hash4(LZ4_read32(p), tableType); -} - -static void LZ4_putPositionOnHash( - const BYTE *p, - U32 h, - void *tableBase, - tableType_t const tableType, - const BYTE *srcBase) -{ - switch (tableType) { - case byPtr: - { - const BYTE **hashTable = (const BYTE **)tableBase; - - hashTable[h] = p; - return; - } - case byU32: - { - U32 *hashTable = (U32 *) tableBase; - - hashTable[h] = (U32)(p - srcBase); - return; - } - case byU16: - { - U16 *hashTable = (U16 *) tableBase; - - hashTable[h] = (U16)(p - srcBase); - return; - } - } -} - -static FORCE_INLINE void LZ4_putPosition( - const BYTE *p, - void *tableBase, - tableType_t tableType, - const BYTE *srcBase) -{ - U32 const h = LZ4_hashPosition(p, tableType); - - LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); -} - -static const BYTE *LZ4_getPositionOnHash( - U32 h, - void *tableBase, - tableType_t tableType, - const BYTE *srcBase) -{ - if (tableType == byPtr) { - const BYTE **hashTable = (const BYTE **) tableBase; - - return hashTable[h]; - } - - if (tableType == byU32) { - const U32 * const hashTable = (U32 *) tableBase; - - return hashTable[h] + srcBase; - } - - { - /* default, to ensure a return */ - const U16 * const hashTable = (U16 *) tableBase; - - return hashTable[h] + srcBase; - } -} - -static FORCE_INLINE const BYTE *LZ4_getPosition( - const BYTE *p, - void *tableBase, - tableType_t tableType, - const BYTE *srcBase) -{ - U32 const h = LZ4_hashPosition(p, tableType); - - return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); -} - - -/* - * LZ4_compress_generic() : - * inlined, to ensure branches are decided at compilation time - */ -static FORCE_INLINE int LZ4_compress_generic( - LZ4_stream_t_internal * const dictPtr, - const char * const source, - char * const dest, - const int inputSize, - const int maxOutputSize, - const limitedOutput_directive outputLimited, - const tableType_t tableType, - const dict_directive dict, - const dictIssue_directive dictIssue, - const U32 acceleration) -{ - const BYTE *ip = (const BYTE *) source; - const BYTE *base; - const BYTE *lowLimit; - const BYTE * const lowRefLimit = ip - dictPtr->dictSize; - const BYTE * const dictionary = dictPtr->dictionary; - const BYTE * const dictEnd = dictionary + dictPtr->dictSize; - const size_t dictDelta = dictEnd - (const BYTE *)source; - const BYTE *anchor = (const BYTE *) source; - const BYTE * const iend = ip + inputSize; - const BYTE * const mflimit = iend - MFLIMIT; - const BYTE * const matchlimit = iend - LASTLITERALS; - - BYTE *op = (BYTE *) dest; - BYTE * const olimit = op + maxOutputSize; - - U32 forwardH; - size_t refDelta = 0; - - /* Init conditions */ - if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) { - /* Unsupported inputSize, too large (or negative) */ - return 0; - } - - switch (dict) { - case noDict: - default: - base = (const BYTE *)source; - lowLimit = (const BYTE *)source; - break; - case withPrefix64k: - base = (const BYTE *)source - dictPtr->currentOffset; - lowLimit = (const BYTE *)source - dictPtr->dictSize; - break; - case usingExtDict: - base = (const BYTE *)source - dictPtr->currentOffset; - lowLimit = (const BYTE *)source; - break; - } - - if ((tableType == byU16) - && (inputSize >= LZ4_64Klimit)) { - /* Size too large (not within 64K limit) */ - return 0; - } - - if (inputSize < LZ4_minLength) { - /* Input too small, no compression (all literals) */ - goto _last_literals; - } - - /* First Byte */ - LZ4_putPosition(ip, dictPtr->hashTable, tableType, base); - ip++; - forwardH = LZ4_hashPosition(ip, tableType); - - /* Main Loop */ - for ( ; ; ) { - const BYTE *match; - BYTE *token; - - /* Find a match */ - { - const BYTE *forwardIp = ip; - unsigned int step = 1; - unsigned int searchMatchNb = acceleration << LZ4_SKIPTRIGGER; - - do { - U32 const h = forwardH; - - ip = forwardIp; - forwardIp += step; - step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); - - if (unlikely(forwardIp > mflimit)) - goto _last_literals; - - match = LZ4_getPositionOnHash(h, - dictPtr->hashTable, - tableType, base); - - if (dict == usingExtDict) { - if (match < (const BYTE *)source) { - refDelta = dictDelta; - lowLimit = dictionary; - } else { - refDelta = 0; - lowLimit = (const BYTE *)source; - } } - - forwardH = LZ4_hashPosition(forwardIp, - tableType); - - LZ4_putPositionOnHash(ip, h, dictPtr->hashTable, - tableType, base); - } while (((dictIssue == dictSmall) - ? (match < lowRefLimit) - : 0) - || ((tableType == byU16) - ? 0 - : (match + MAX_DISTANCE < ip)) - || (LZ4_read32(match + refDelta) - != LZ4_read32(ip))); - } - - /* Catch up */ - while (((ip > anchor) & (match + refDelta > lowLimit)) - && (unlikely(ip[-1] == match[refDelta - 1]))) { - ip--; - match--; - } - - /* Encode Literals */ - { - unsigned const int litLength = (unsigned int)(ip - anchor); - - token = op++; - - if ((outputLimited) && - /* Check output buffer overflow */ - (unlikely(op + litLength + - (2 + 1 + LASTLITERALS) + - (litLength / 255) > olimit))) - return 0; - - if (litLength >= RUN_MASK) { - int len = (int)litLength - RUN_MASK; - - *token = (RUN_MASK << ML_BITS); - - for (; len >= 255; len -= 255) - *op++ = 255; - *op++ = (BYTE)len; - } else - *token = (BYTE)(litLength << ML_BITS); - - /* Copy Literals */ - LZ4_wildCopy(op, anchor, op + litLength); - op += litLength; - } - -_next_match: - /* Encode Offset */ - LZ4_writeLE16(op, (U16)(ip - match)); - op += 2; - - /* Encode MatchLength */ - { - unsigned int matchCode; - - if ((dict == usingExtDict) - && (lowLimit == dictionary)) { - const BYTE *limit; - - match += refDelta; - limit = ip + (dictEnd - match); - - if (limit > matchlimit) - limit = matchlimit; - - matchCode = LZ4_count(ip + MINMATCH, - match + MINMATCH, limit); - - ip += MINMATCH + matchCode; - - if (ip == limit) { - unsigned const int more = LZ4_count(ip, - (const BYTE *)source, - matchlimit); - - matchCode += more; - ip += more; - } - } else { - matchCode = LZ4_count(ip + MINMATCH, - match + MINMATCH, matchlimit); - ip += MINMATCH + matchCode; - } - - if (outputLimited && - /* Check output buffer overflow */ - (unlikely(op + - (1 + LASTLITERALS) + - (matchCode >> 8) > olimit))) - return 0; - - if (matchCode >= ML_MASK) { - *token += ML_MASK; - matchCode -= ML_MASK; - LZ4_write32(op, 0xFFFFFFFF); - - while (matchCode >= 4 * 255) { - op += 4; - LZ4_write32(op, 0xFFFFFFFF); - matchCode -= 4 * 255; - } - - op += matchCode / 255; - *op++ = (BYTE)(matchCode % 255); - } else - *token += (BYTE)(matchCode); - } - - anchor = ip; - - /* Test end of chunk */ - if (ip > mflimit) - break; - - /* Fill table */ - LZ4_putPosition(ip - 2, dictPtr->hashTable, tableType, base); - - /* Test next position */ - match = LZ4_getPosition(ip, dictPtr->hashTable, - tableType, base); - - if (dict == usingExtDict) { - if (match < (const BYTE *)source) { - refDelta = dictDelta; - lowLimit = dictionary; - } else { - refDelta = 0; - lowLimit = (const BYTE *)source; - } - } - - LZ4_putPosition(ip, dictPtr->hashTable, tableType, base); - - if (((dictIssue == dictSmall) ? (match >= lowRefLimit) : 1) - && (match + MAX_DISTANCE >= ip) - && (LZ4_read32(match + refDelta) == LZ4_read32(ip))) { - token = op++; - *token = 0; - goto _next_match; - } - - /* Prepare next loop */ - forwardH = LZ4_hashPosition(++ip, tableType); - } - -_last_literals: - /* Encode Last Literals */ - { - size_t const lastRun = (size_t)(iend - anchor); - - if ((outputLimited) && - /* Check output buffer overflow */ - ((op - (BYTE *)dest) + lastRun + 1 + - ((lastRun + 255 - RUN_MASK) / 255) > (U32)maxOutputSize)) - return 0; - - if (lastRun >= RUN_MASK) { - size_t accumulator = lastRun - RUN_MASK; - *op++ = RUN_MASK << ML_BITS; - for (; accumulator >= 255; accumulator -= 255) - *op++ = 255; - *op++ = (BYTE) accumulator; - } else { - *op++ = (BYTE)(lastRun << ML_BITS); - } - - memcpy(op, anchor, lastRun); - - op += lastRun; - } - - /* End */ - return (int) (((char *)op) - dest); -} - -static int LZ4_compress_fast_extState( - void *state, - const char *source, - char *dest, - int inputSize, - int maxOutputSize, - int acceleration) -{ - LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse; -#if LZ4_ARCH64 - const tableType_t tableType = byU32; -#else - const tableType_t tableType = byPtr; -#endif - - LZ4_resetStream((LZ4_stream_t *)state); - - if (acceleration < 1) - acceleration = LZ4_ACCELERATION_DEFAULT; - - if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) { - if (inputSize < LZ4_64Klimit) - return LZ4_compress_generic(ctx, source, - dest, inputSize, 0, - noLimit, byU16, noDict, - noDictIssue, acceleration); - else - return LZ4_compress_generic(ctx, source, - dest, inputSize, 0, - noLimit, tableType, noDict, - noDictIssue, acceleration); - } else { - if (inputSize < LZ4_64Klimit) - return LZ4_compress_generic(ctx, source, - dest, inputSize, - maxOutputSize, limitedOutput, byU16, noDict, - noDictIssue, acceleration); - else - return LZ4_compress_generic(ctx, source, - dest, inputSize, - maxOutputSize, limitedOutput, tableType, noDict, - noDictIssue, acceleration); - } -} - -int LZ4_compress_fast(const char *source, char *dest, int inputSize, - int maxOutputSize, int acceleration, void *wrkmem) -{ - return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize, - maxOutputSize, acceleration); -} - -int LZ4_compress_default(const char *source, char *dest, int inputSize, - int maxOutputSize, void *wrkmem) -{ - return LZ4_compress_fast(source, dest, inputSize, - maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem); -} - -/*-****************************** - * *_destSize() variant - ********************************/ -static int LZ4_compress_destSize_generic( - LZ4_stream_t_internal * const ctx, - const char * const src, - char * const dst, - int * const srcSizePtr, - const int targetDstSize, - const tableType_t tableType) -{ - const BYTE *ip = (const BYTE *) src; - const BYTE *base = (const BYTE *) src; - const BYTE *lowLimit = (const BYTE *) src; - const BYTE *anchor = ip; - const BYTE * const iend = ip + *srcSizePtr; - const BYTE * const mflimit = iend - MFLIMIT; - const BYTE * const matchlimit = iend - LASTLITERALS; - - BYTE *op = (BYTE *) dst; - BYTE * const oend = op + targetDstSize; - BYTE * const oMaxLit = op + targetDstSize - 2 /* offset */ - - 8 /* because 8 + MINMATCH == MFLIMIT */ - 1 /* token */; - BYTE * const oMaxMatch = op + targetDstSize - - (LASTLITERALS + 1 /* token */); - BYTE * const oMaxSeq = oMaxLit - 1 /* token */; - - U32 forwardH; - - /* Init conditions */ - /* Impossible to store anything */ - if (targetDstSize < 1) - return 0; - /* Unsupported input size, too large (or negative) */ - if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) - return 0; - /* Size too large (not within 64K limit) */ - if ((tableType == byU16) && (*srcSizePtr >= LZ4_64Klimit)) - return 0; - /* Input too small, no compression (all literals) */ - if (*srcSizePtr < LZ4_minLength) - goto _last_literals; - - /* First Byte */ - *srcSizePtr = 0; - LZ4_putPosition(ip, ctx->hashTable, tableType, base); - ip++; forwardH = LZ4_hashPosition(ip, tableType); - - /* Main Loop */ - for ( ; ; ) { - const BYTE *match; - BYTE *token; - - /* Find a match */ - { - const BYTE *forwardIp = ip; - unsigned int step = 1; - unsigned int searchMatchNb = 1 << LZ4_SKIPTRIGGER; - - do { - U32 h = forwardH; - - ip = forwardIp; - forwardIp += step; - step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); - - if (unlikely(forwardIp > mflimit)) - goto _last_literals; - - match = LZ4_getPositionOnHash(h, ctx->hashTable, - tableType, base); - forwardH = LZ4_hashPosition(forwardIp, - tableType); - LZ4_putPositionOnHash(ip, h, - ctx->hashTable, tableType, - base); - - } while (((tableType == byU16) - ? 0 - : (match + MAX_DISTANCE < ip)) - || (LZ4_read32(match) != LZ4_read32(ip))); - } - - /* Catch up */ - while ((ip > anchor) - && (match > lowLimit) - && (unlikely(ip[-1] == match[-1]))) { - ip--; - match--; - } - - /* Encode Literal length */ - { - unsigned int litLength = (unsigned int)(ip - anchor); - - token = op++; - if (op + ((litLength + 240) / 255) - + litLength > oMaxLit) { - /* Not enough space for a last match */ - op--; - goto _last_literals; - } - if (litLength >= RUN_MASK) { - unsigned int len = litLength - RUN_MASK; - *token = (RUN_MASK<<ML_BITS); - for (; len >= 255; len -= 255) - *op++ = 255; - *op++ = (BYTE)len; - } else - *token = (BYTE)(litLength << ML_BITS); - - /* Copy Literals */ - LZ4_wildCopy(op, anchor, op + litLength); - op += litLength; - } - -_next_match: - /* Encode Offset */ - LZ4_writeLE16(op, (U16)(ip - match)); op += 2; - - /* Encode MatchLength */ - { - size_t matchLength = LZ4_count(ip + MINMATCH, - match + MINMATCH, matchlimit); - - if (op + ((matchLength + 240)/255) > oMaxMatch) { - /* Match description too long : reduce it */ - matchLength = (15 - 1) + (oMaxMatch - op) * 255; - } - ip += MINMATCH + matchLength; - - if (matchLength >= ML_MASK) { - *token += ML_MASK; - matchLength -= ML_MASK; - while (matchLength >= 255) { - matchLength -= 255; - *op++ = 255; - } - *op++ = (BYTE)matchLength; - } else - *token += (BYTE)(matchLength); - } - - anchor = ip; - - /* Test end of block */ - if (ip > mflimit) - break; - if (op > oMaxSeq) - break; - - /* Fill table */ - LZ4_putPosition(ip - 2, ctx->hashTable, tableType, base); - - /* Test next position */ - match = LZ4_getPosition(ip, ctx->hashTable, tableType, base); - LZ4_putPosition(ip, ctx->hashTable, tableType, base); - - if ((match + MAX_DISTANCE >= ip) - && (LZ4_read32(match) == LZ4_read32(ip))) { - token = op++; *token = 0; - goto _next_match; - } - - /* Prepare next loop */ - forwardH = LZ4_hashPosition(++ip, tableType); - } - -_last_literals: - /* Encode Last Literals */ - { - size_t lastRunSize = (size_t)(iend - anchor); - - if (op + 1 /* token */ - + ((lastRunSize + 240) / 255) /* litLength */ - + lastRunSize /* literals */ > oend) { - /* adapt lastRunSize to fill 'dst' */ - lastRunSize = (oend - op) - 1; - lastRunSize -= (lastRunSize + 240) / 255; - } - ip = anchor + lastRunSize; - - if (lastRunSize >= RUN_MASK) { - size_t accumulator = lastRunSize - RUN_MASK; - - *op++ = RUN_MASK << ML_BITS; - for (; accumulator >= 255; accumulator -= 255) - *op++ = 255; - *op++ = (BYTE) accumulator; - } else { - *op++ = (BYTE)(lastRunSize<<ML_BITS); - } - memcpy(op, anchor, lastRunSize); - op += lastRunSize; - } - - /* End */ - *srcSizePtr = (int) (((const char *)ip) - src); - return (int) (((char *)op) - dst); -} - -static int LZ4_compress_destSize_extState( - LZ4_stream_t *state, - const char *src, - char *dst, - int *srcSizePtr, - int targetDstSize) -{ -#if LZ4_ARCH64 - const tableType_t tableType = byU32; -#else - const tableType_t tableType = byPtr; -#endif - - LZ4_resetStream(state); - - if (targetDstSize >= LZ4_COMPRESSBOUND(*srcSizePtr)) { - /* compression success is guaranteed */ - return LZ4_compress_fast_extState( - state, src, dst, *srcSizePtr, - targetDstSize, 1); - } else { - if (*srcSizePtr < LZ4_64Klimit) - return LZ4_compress_destSize_generic( - &state->internal_donotuse, - src, dst, srcSizePtr, - targetDstSize, byU16); - else - return LZ4_compress_destSize_generic( - &state->internal_donotuse, - src, dst, srcSizePtr, - targetDstSize, tableType); - } -} - - -int LZ4_compress_destSize( - const char *src, - char *dst, - int *srcSizePtr, - int targetDstSize, - void *wrkmem) -{ - return LZ4_compress_destSize_extState(wrkmem, src, dst, srcSizePtr, - targetDstSize); -} - -/*-****************************** - * Streaming functions - ********************************/ -void LZ4_resetStream(LZ4_stream_t *LZ4_stream) -{ - memset(LZ4_stream, 0, sizeof(LZ4_stream_t)); -} - -int LZ4_loadDict(LZ4_stream_t *LZ4_dict, - const char *dictionary, int dictSize) -{ - LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse; - const BYTE *p = (const BYTE *)dictionary; - const BYTE * const dictEnd = p + dictSize; - const BYTE *base; - - if ((dict->initCheck) - || (dict->currentOffset > 1 * GB)) { - /* Uninitialized structure, or reuse overflow */ - LZ4_resetStream(LZ4_dict); - } - - if (dictSize < (int)HASH_UNIT) { - dict->dictionary = NULL; - dict->dictSize = 0; - return 0; - } - - if ((dictEnd - p) > 64 * KB) - p = dictEnd - 64 * KB; - dict->currentOffset += 64 * KB; - base = p - dict->currentOffset; - dict->dictionary = p; - dict->dictSize = (U32)(dictEnd - p); - dict->currentOffset += dict->dictSize; - - while (p <= dictEnd - HASH_UNIT) { - LZ4_putPosition(p, dict->hashTable, byU32, base); - p += 3; - } - - return dict->dictSize; -} - -static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict, - const BYTE *src) -{ - if ((LZ4_dict->currentOffset > 0x80000000) || - ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { - /* address space overflow */ - /* rescale hash table */ - U32 const delta = LZ4_dict->currentOffset - 64 * KB; - const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; - int i; - - for (i = 0; i < LZ4_HASH_SIZE_U32; i++) { - if (LZ4_dict->hashTable[i] < delta) - LZ4_dict->hashTable[i] = 0; - else - LZ4_dict->hashTable[i] -= delta; - } - LZ4_dict->currentOffset = 64 * KB; - if (LZ4_dict->dictSize > 64 * KB) - LZ4_dict->dictSize = 64 * KB; - LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; - } -} - -int LZ4_saveDict(LZ4_stream_t *LZ4_dict, char *safeBuffer, int dictSize) -{ - LZ4_stream_t_internal * const dict = &LZ4_dict->internal_donotuse; - const BYTE * const previousDictEnd = dict->dictionary + dict->dictSize; - - if ((U32)dictSize > 64 * KB) { - /* useless to define a dictionary > 64 * KB */ - dictSize = 64 * KB; - } - if ((U32)dictSize > dict->dictSize) - dictSize = dict->dictSize; - - memmove(safeBuffer, previousDictEnd - dictSize, dictSize); - - dict->dictionary = (const BYTE *)safeBuffer; - dict->dictSize = (U32)dictSize; - - return dictSize; -} - -int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source, - char *dest, int inputSize, int maxOutputSize, int acceleration) -{ - LZ4_stream_t_internal *streamPtr = &LZ4_stream->internal_donotuse; - const BYTE * const dictEnd = streamPtr->dictionary - + streamPtr->dictSize; - - const BYTE *smallest = (const BYTE *) source; - - if (streamPtr->initCheck) { - /* Uninitialized structure detected */ - return 0; - } - - if ((streamPtr->dictSize > 0) && (smallest > dictEnd)) - smallest = dictEnd; - - LZ4_renormDictT(streamPtr, smallest); - - if (acceleration < 1) - acceleration = LZ4_ACCELERATION_DEFAULT; - - /* Check overlapping input/dictionary space */ - { - const BYTE *sourceEnd = (const BYTE *) source + inputSize; - - if ((sourceEnd > streamPtr->dictionary) - && (sourceEnd < dictEnd)) { - streamPtr->dictSize = (U32)(dictEnd - sourceEnd); - if (streamPtr->dictSize > 64 * KB) - streamPtr->dictSize = 64 * KB; - if (streamPtr->dictSize < 4) - streamPtr->dictSize = 0; - streamPtr->dictionary = dictEnd - streamPtr->dictSize; - } - } - - /* prefix mode : source data follows dictionary */ - if (dictEnd == (const BYTE *)source) { - int result; - - if ((streamPtr->dictSize < 64 * KB) && - (streamPtr->dictSize < streamPtr->currentOffset)) { - result = LZ4_compress_generic( - streamPtr, source, dest, inputSize, - maxOutputSize, limitedOutput, byU32, - withPrefix64k, dictSmall, acceleration); - } else { - result = LZ4_compress_generic( - streamPtr, source, dest, inputSize, - maxOutputSize, limitedOutput, byU32, - withPrefix64k, noDictIssue, acceleration); - } - streamPtr->dictSize += (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - return result; - } - - /* external dictionary mode */ - { - int result; - - if ((streamPtr->dictSize < 64 * KB) && - (streamPtr->dictSize < streamPtr->currentOffset)) { - result = LZ4_compress_generic( - streamPtr, source, dest, inputSize, - maxOutputSize, limitedOutput, byU32, - usingExtDict, dictSmall, acceleration); - } else { - result = LZ4_compress_generic( - streamPtr, source, dest, inputSize, - maxOutputSize, limitedOutput, byU32, - usingExtDict, noDictIssue, acceleration); - } - streamPtr->dictionary = (const BYTE *)source; - streamPtr->dictSize = (U32)inputSize; - streamPtr->currentOffset += (U32)inputSize; - return result; - } -} diff --git a/linux/lz4_decompress.c b/linux/lz4_decompress.c deleted file mode 100644 index 5cf910d7..00000000 --- a/linux/lz4_decompress.c +++ /dev/null @@ -1,492 +0,0 @@ -/* - * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011 - 2016, 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://www.lz4.org - * - LZ4 source repository : https://github.com/lz4/lz4 - * - * Changed for kernel usage by: - * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> - */ - -/*-************************************ - * Dependencies - **************************************/ -#include <linux/lz4.h> -#include "lz4defs.h" -#include <linux/kernel.h> -#include <asm/unaligned.h> - -/*-***************************** - * Decompression functions - *******************************/ -/* LZ4_decompress_generic() : - * This generic decompression function cover all use cases. - * It shall be instantiated several times, using different sets of directives - * Note that it is important this generic function is really inlined, - * in order to remove useless branches during compilation optimization. - */ -static FORCE_INLINE int LZ4_decompress_generic( - const char * const source, - char * const dest, - int inputSize, - /* - * If endOnInput == endOnInputSize, - * this value is the max size of Output Buffer. - */ - int outputSize, - /* endOnOutputSize, endOnInputSize */ - int endOnInput, - /* full, partial */ - int partialDecoding, - /* only used if partialDecoding == partial */ - int targetOutputSize, - /* noDict, withPrefix64k, usingExtDict */ - int dict, - /* == dest when no prefix */ - const BYTE * const lowPrefix, - /* only if dict == usingExtDict */ - const BYTE * const dictStart, - /* note : = 0 if noDict */ - const size_t dictSize - ) -{ - /* Local Variables */ - const BYTE *ip = (const BYTE *) source; - const BYTE * const iend = ip + inputSize; - - BYTE *op = (BYTE *) dest; - BYTE * const oend = op + outputSize; - BYTE *cpy; - BYTE *oexit = op + targetOutputSize; - const BYTE * const lowLimit = lowPrefix - dictSize; - - const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize; - const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; - const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 }; - - const int safeDecode = (endOnInput == endOnInputSize); - const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB))); - - /* Special cases */ - /* targetOutputSize too high => decode everything */ - if ((partialDecoding) && (oexit > oend - MFLIMIT)) - oexit = oend - MFLIMIT; - - /* Empty output buffer */ - if ((endOnInput) && (unlikely(outputSize == 0))) - return ((inputSize == 1) && (*ip == 0)) ? 0 : -1; - - if ((!endOnInput) && (unlikely(outputSize == 0))) - return (*ip == 0 ? 1 : -1); - - /* Main Loop : decode sequences */ - while (1) { - size_t length; - const BYTE *match; - size_t offset; - - /* get literal length */ - unsigned int const token = *ip++; - - length = token>>ML_BITS; - - if (length == RUN_MASK) { - unsigned int s; - - do { - s = *ip++; - length += s; - } while (likely(endOnInput - ? ip < iend - RUN_MASK - : 1) & (s == 255)); - - if ((safeDecode) - && unlikely( - (size_t)(op + length) < (size_t)(op))) { - /* overflow detection */ - goto _output_error; - } - if ((safeDecode) - && unlikely( - (size_t)(ip + length) < (size_t)(ip))) { - /* overflow detection */ - goto _output_error; - } - } - - /* copy literals */ - cpy = op + length; - if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT)) - || (ip + length > iend - (2 + 1 + LASTLITERALS)))) - || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { - if (partialDecoding) { - if (cpy > oend) { - /* - * Error : - * write attempt beyond end of output buffer - */ - goto _output_error; - } - if ((endOnInput) - && (ip + length > iend)) { - /* - * Error : - * read attempt beyond - * end of input buffer - */ - goto _output_error; - } - } else { - if ((!endOnInput) - && (cpy != oend)) { - /* - * Error : - * block decoding must - * stop exactly there - */ - goto _output_error; - } - if ((endOnInput) - && ((ip + length != iend) - || (cpy > oend))) { - /* - * Error : - * input must be consumed - */ - goto _output_error; - } - } - - memcpy(op, ip, length); - ip += length; - op += length; - /* Necessarily EOF, due to parsing restrictions */ - break; - } - - LZ4_wildCopy(op, ip, cpy); - ip += length; - op = cpy; - - /* get offset */ - offset = LZ4_readLE16(ip); - ip += 2; - match = op - offset; - - if ((checkOffset) && (unlikely(match < lowLimit))) { - /* Error : offset outside buffers */ - goto _output_error; - } - - /* costs ~1%; silence an msan warning when offset == 0 */ - LZ4_write32(op, (U32)offset); - - /* get matchlength */ - length = token & ML_MASK; - if (length == ML_MASK) { - unsigned int s; - - do { - s = *ip++; - - if ((endOnInput) && (ip > iend - LASTLITERALS)) - goto _output_error; - - length += s; - } while (s == 255); - - if ((safeDecode) - && unlikely( - (size_t)(op + length) < (size_t)op)) { - /* overflow detection */ - goto _output_error; - } - } - - length += MINMATCH; - - /* check external dictionary */ - if ((dict == usingExtDict) && (match < lowPrefix)) { - if (unlikely(op + length > oend - LASTLITERALS)) { - /* doesn't respect parsing restriction */ - goto _output_error; - } - - if (length <= (size_t)(lowPrefix - match)) { - /* - * match can be copied as a single segment - * from external dictionary - */ - memmove(op, dictEnd - (lowPrefix - match), - length); - op += length; - } else { - /* - * match encompass external - * dictionary and current block - */ - size_t const copySize = (size_t)(lowPrefix - match); - size_t const restSize = length - copySize; - - memcpy(op, dictEnd - copySize, copySize); - op += copySize; - - if (restSize > (size_t)(op - lowPrefix)) { - /* overlap copy */ - BYTE * const endOfMatch = op + restSize; - const BYTE *copyFrom = lowPrefix; - - while (op < endOfMatch) - *op++ = *copyFrom++; - } else { - memcpy(op, lowPrefix, restSize); - op += restSize; - } - } - - continue; - } - - /* copy match within block */ - cpy = op + length; - - if (unlikely(offset < 8)) { - const int dec64 = dec64table[offset]; - - op[0] = match[0]; - op[1] = match[1]; - op[2] = match[2]; - op[3] = match[3]; - match += dec32table[offset]; - memcpy(op + 4, match, 4); - match -= dec64; - } else { - LZ4_copy8(op, match); - match += 8; - } - - op += 8; - - if (unlikely(cpy > oend - 12)) { - BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1); - - if (cpy > oend - LASTLITERALS) { - /* - * Error : last LASTLITERALS bytes - * must be literals (uncompressed) - */ - goto _output_error; - } - - if (op < oCopyLimit) { - LZ4_wildCopy(op, match, oCopyLimit); - match += oCopyLimit - op; - op = oCopyLimit; - } - - while (op < cpy) - *op++ = *match++; - } else { - LZ4_copy8(op, match); - - if (length > 16) - LZ4_wildCopy(op + 8, match + 8, cpy); - } - - op = cpy; /* correction */ - } - - /* end of decoding */ - if (endOnInput) { - /* Nb of output bytes decoded */ - return (int) (((char *)op) - dest); - } else { - /* Nb of input bytes read */ - return (int) (((const char *)ip) - source); - } - - /* Overflow error detected */ -_output_error: - return -1; -} - -int LZ4_decompress_safe(const char *source, char *dest, - int compressedSize, int maxDecompressedSize) -{ - return LZ4_decompress_generic(source, dest, compressedSize, - maxDecompressedSize, endOnInputSize, full, 0, - noDict, (BYTE *)dest, NULL, 0); -} - -int LZ4_decompress_safe_partial(const char *source, char *dest, - int compressedSize, int targetOutputSize, int maxDecompressedSize) -{ - return LZ4_decompress_generic(source, dest, compressedSize, - maxDecompressedSize, endOnInputSize, partial, - targetOutputSize, noDict, (BYTE *)dest, NULL, 0); -} - -int LZ4_decompress_fast(const char *source, char *dest, int originalSize) -{ - return LZ4_decompress_generic(source, dest, 0, originalSize, - endOnOutputSize, full, 0, withPrefix64k, - (BYTE *)(dest - 64 * KB), NULL, 64 * KB); -} - -int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode, - const char *dictionary, int dictSize) -{ - LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode; - - lz4sd->prefixSize = (size_t) dictSize; - lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize; - lz4sd->externalDict = NULL; - lz4sd->extDictSize = 0; - return 1; -} - -/* - * *_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 it stands using LZ4_setStreamDecode() - */ -int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, - const char *source, char *dest, int compressedSize, int maxOutputSize) -{ - LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; - int result; - - if (lz4sd->prefixEnd == (BYTE *)dest) { - result = LZ4_decompress_generic(source, dest, - compressedSize, - maxOutputSize, - endOnInputSize, full, 0, - usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, - lz4sd->externalDict, - lz4sd->extDictSize); - - if (result <= 0) - return result; - - lz4sd->prefixSize += result; - lz4sd->prefixEnd += result; - } else { - lz4sd->extDictSize = lz4sd->prefixSize; - lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; - result = LZ4_decompress_generic(source, dest, - compressedSize, maxOutputSize, - endOnInputSize, full, 0, - usingExtDict, (BYTE *)dest, - lz4sd->externalDict, lz4sd->extDictSize); - if (result <= 0) - return result; - lz4sd->prefixSize = result; - lz4sd->prefixEnd = (BYTE *)dest + result; - } - - return result; -} - -int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, - const char *source, char *dest, int originalSize) -{ - LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; - int result; - - if (lz4sd->prefixEnd == (BYTE *)dest) { - result = LZ4_decompress_generic(source, dest, 0, originalSize, - endOnOutputSize, full, 0, - usingExtDict, - lz4sd->prefixEnd - lz4sd->prefixSize, - lz4sd->externalDict, lz4sd->extDictSize); - - if (result <= 0) - return result; - - lz4sd->prefixSize += originalSize; - lz4sd->prefixEnd += originalSize; - } else { - lz4sd->extDictSize = lz4sd->prefixSize; - lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; - result = LZ4_decompress_generic(source, dest, 0, originalSize, - endOnOutputSize, full, 0, - usingExtDict, (BYTE *)dest, - lz4sd->externalDict, lz4sd->extDictSize); - if (result <= 0) - return result; - lz4sd->prefixSize = originalSize; - lz4sd->prefixEnd = (BYTE *)dest + originalSize; - } - - return result; -} - -/* - * Advanced decoding functions : - * *_usingDict() : - * These decoding functions work the same as "_continue" ones, - * the dictionary must be explicitly provided within parameters - */ -static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source, - char *dest, int compressedSize, int maxOutputSize, int safe, - const char *dictStart, int dictSize) -{ - if (dictSize == 0) - return LZ4_decompress_generic(source, dest, - compressedSize, maxOutputSize, safe, full, 0, - noDict, (BYTE *)dest, NULL, 0); - if (dictStart + dictSize == dest) { - if (dictSize >= (int)(64 * KB - 1)) - return LZ4_decompress_generic(source, dest, - compressedSize, maxOutputSize, safe, full, 0, - withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0); - return LZ4_decompress_generic(source, dest, compressedSize, - maxOutputSize, safe, full, 0, noDict, - (BYTE *)dest - dictSize, NULL, 0); - } - return LZ4_decompress_generic(source, dest, compressedSize, - maxOutputSize, safe, full, 0, usingExtDict, - (BYTE *)dest, (const BYTE *)dictStart, dictSize); -} - -int LZ4_decompress_safe_usingDict(const char *source, char *dest, - int compressedSize, int maxOutputSize, - const char *dictStart, int dictSize) -{ - return LZ4_decompress_usingDict_generic(source, dest, - compressedSize, maxOutputSize, 1, dictStart, dictSize); -} - -int LZ4_decompress_fast_usingDict(const char *source, char *dest, - int originalSize, const char *dictStart, int dictSize) -{ - return LZ4_decompress_usingDict_generic(source, dest, 0, - originalSize, 0, dictStart, dictSize); -} diff --git a/linux/lz4defs.h b/linux/lz4defs.h deleted file mode 100644 index 80018ea6..00000000 --- a/linux/lz4defs.h +++ /dev/null @@ -1,228 +0,0 @@ -#ifndef __LZ4DEFS_H__ -#define __LZ4DEFS_H__ - -/* - * lz4defs.h -- common and architecture specific defines for the kernel usage - - * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011-2016, 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://www.lz4.org - * - LZ4 source repository : https://github.com/lz4/lz4 - * - * Changed for kernel usage by: - * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> - */ - -#include <asm/unaligned.h> -#include <linux/bitops.h> -#include <linux/string.h> /* memset, memcpy */ - -#define FORCE_INLINE __always_inline - -/*-************************************ - * Basic Types - **************************************/ -#include <linux/types.h> - -typedef uint8_t BYTE; -typedef uint16_t U16; -typedef uint32_t U32; -typedef int32_t S32; -typedef uint64_t U64; -typedef uintptr_t uptrval; - -/*-************************************ - * Architecture specifics - **************************************/ -#if defined(CONFIG_64BIT) -#define LZ4_ARCH64 1 -#else -#define LZ4_ARCH64 0 -#endif - -#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ -#define LZ4_LITTLE_ENDIAN 1 -#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ -#define LZ4_LITTLE_ENDIAN 0 -#endif - -/*-************************************ - * Constants - **************************************/ -#define MINMATCH 4 - -#define WILDCOPYLENGTH 8 -#define LASTLITERALS 5 -#define MFLIMIT (WILDCOPYLENGTH + MINMATCH) - -/* Increase this value ==> compression run slower on incompressible data */ -#define LZ4_SKIPTRIGGER 6 - -#define HASH_UNIT sizeof(size_t) - -#define KB (1 << 10) -#define MB (1 << 20) -#define GB (1U << 30) - -#define MAXD_LOG 16 -#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) -#define STEPSIZE sizeof(size_t) - -#define ML_BITS 4 -#define ML_MASK ((1U << ML_BITS) - 1) -#define RUN_BITS (8 - ML_BITS) -#define RUN_MASK ((1U << RUN_BITS) - 1) - -/*-************************************ - * Reading and writing into memory - **************************************/ -static FORCE_INLINE U16 LZ4_read16(const void *ptr) -{ - return get_unaligned((const U16 *)ptr); -} - -static FORCE_INLINE U32 LZ4_read32(const void *ptr) -{ - return get_unaligned((const U32 *)ptr); -} - -static FORCE_INLINE size_t LZ4_read_ARCH(const void *ptr) -{ - return get_unaligned((const size_t *)ptr); -} - -static FORCE_INLINE void LZ4_write16(void *memPtr, U16 value) -{ - put_unaligned(value, (U16 *)memPtr); -} - -static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value) -{ - put_unaligned(value, (U32 *)memPtr); -} - -static FORCE_INLINE U16 LZ4_readLE16(const void *memPtr) -{ - return get_unaligned_le16(memPtr); -} - -static FORCE_INLINE void LZ4_writeLE16(void *memPtr, U16 value) -{ - return put_unaligned_le16(value, memPtr); -} - -static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) -{ -#if LZ4_ARCH64 - U64 a = get_unaligned((const U64 *)src); - - put_unaligned(a, (U64 *)dst); -#else - U32 a = get_unaligned((const U32 *)src); - U32 b = get_unaligned((const U32 *)src + 1); - - put_unaligned(a, (U32 *)dst); - put_unaligned(b, (U32 *)dst + 1); -#endif -} - -/* - * customized variant of memcpy, - * which can overwrite up to 7 bytes beyond dstEnd - */ -static FORCE_INLINE void LZ4_wildCopy(void *dstPtr, - const void *srcPtr, void *dstEnd) -{ - BYTE *d = (BYTE *)dstPtr; - const BYTE *s = (const BYTE *)srcPtr; - BYTE *const e = (BYTE *)dstEnd; - - do { - LZ4_copy8(d, s); - d += 8; - s += 8; - } while (d < e); -} - -static FORCE_INLINE unsigned int LZ4_NbCommonBytes(register size_t val) -{ -#if LZ4_LITTLE_ENDIAN - return __ffs(val) >> 3; -#else - return (BITS_PER_LONG - 1 - __fls(val)) >> 3; -#endif -} - -static FORCE_INLINE unsigned int LZ4_count( - const BYTE *pIn, - const BYTE *pMatch, - const BYTE *pInLimit) -{ - const BYTE *const pStart = pIn; - - while (likely(pIn < pInLimit - (STEPSIZE - 1))) { - size_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); - - if (!diff) { - pIn += STEPSIZE; - pMatch += STEPSIZE; - continue; - } - - pIn += LZ4_NbCommonBytes(diff); - - return (unsigned int)(pIn - pStart); - } - -#if LZ4_ARCH64 - if ((pIn < (pInLimit - 3)) - && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { - pIn += 4; - pMatch += 4; - } -#endif - - if ((pIn < (pInLimit - 1)) - && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { - pIn += 2; - pMatch += 2; - } - - if ((pIn < pInLimit) && (*pMatch == *pIn)) - pIn++; - - return (unsigned int)(pIn - pStart); -} - -typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; -typedef enum { byPtr, byU32, byU16 } tableType_t; - -typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; -typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; - -typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; -typedef enum { full = 0, partial = 1 } earlyEnd_directive; - -#endif |