include/linux/lz4.h

   1 /* LZ4 Kernel Interface
   2  *
   3  * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
   4  * Copyright (C) 2016, Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 as
   8  * published by the Free Software Foundation.
   9  *
  10  * This file is based on the original header file
  11  * for LZ4 - Fast LZ compression algorithm.
  12  *
  13  * LZ4 - Fast LZ compression algorithm
  14  * Copyright (C) 2011-2016, Yann Collet.
  15  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions are
  18  * met:
  19  *      * Redistributions of source code must retain the above copyright
  20  *        notice, this list of conditions and the following disclaimer.
  21  *      * Redistributions in binary form must reproduce the above
  22  * copyright notice, this list of conditions and the following disclaimer
  23  * in the documentation and/or other materials provided with the
  24  * distribution.
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  * You can contact the author at :
  37  *      - LZ4 homepage : http://www.lz4.org
  38  *      - LZ4 source repository : https://github.com/lz4/lz4
  39  */
  40
  41 #ifndef __LZ4_H__
  42 #define __LZ4_H__
  43
  44 #include <linux/types.h>
  45 #include <linux/string.h>        /* memset, memcpy */
  46
  47 /*-************************************************************************
  48  *      CONSTANTS
  49  **************************************************************************/
  50 /*
  51  * LZ4_MEMORY_USAGE :
  52  * Memory usage formula : N->2^N Bytes
  53  * (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
  54  * Increasing memory usage improves compression ratio
  55  * Reduced memory usage can improve speed, due to cache effect
  56  * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache
  57  */
  58 #define LZ4_MEMORY_USAGE 14
  59
  60 #define LZ4_MAX_INPUT_SIZE      0x7E000000 /* 2 113 929 216 bytes */
  61 #define LZ4_COMPRESSBOUND(isize)        (\
  62         (unsigned int)(isize) > (unsigned int)LZ4_MAX_INPUT_SIZE \
  63         ? 0 \
  64         : (isize) + ((isize)/255) + 16)
  65
  66 #define LZ4_ACCELERATION_DEFAULT 1
  67 #define LZ4_HASHLOG      (LZ4_MEMORY_USAGE-2)
  68 #define LZ4_HASHTABLESIZE (1 << LZ4_MEMORY_USAGE)
  69 #define LZ4_HASH_SIZE_U32 (1 << LZ4_HASHLOG)
  70
  71 #define LZ4HC_MIN_CLEVEL                        3
  72 #define LZ4HC_DEFAULT_CLEVEL                    9
  73 #define LZ4HC_MAX_CLEVEL                        16
  74
  75 #define LZ4HC_DICTIONARY_LOGSIZE 16
  76 #define LZ4HC_MAXD (1<<LZ4HC_DICTIONARY_LOGSIZE)
  77 #define LZ4HC_MAXD_MASK (LZ4HC_MAXD - 1)
  78 #define LZ4HC_HASH_LOG (LZ4HC_DICTIONARY_LOGSIZE - 1)
  79 #define LZ4HC_HASHTABLESIZE (1 << LZ4HC_HASH_LOG)
  80 #define LZ4HC_HASH_MASK (LZ4HC_HASHTABLESIZE - 1)
  81
  82 /*-************************************************************************
  83  *      STREAMING CONSTANTS AND STRUCTURES
  84  **************************************************************************/
  85 #define LZ4_STREAMSIZE_U64 ((1 << (LZ4_MEMORY_USAGE - 3)) + 4)
  86 #define LZ4_STREAMSIZE  (LZ4_STREAMSIZE_U64 * sizeof(unsigned long long))
  87
  88 #define LZ4_STREAMHCSIZE        262192
  89 #define LZ4_STREAMHCSIZE_SIZET (262192 / sizeof(size_t))
  90
  91 #define LZ4_STREAMDECODESIZE_U64        4
  92 #define LZ4_STREAMDECODESIZE             (LZ4_STREAMDECODESIZE_U64 * \
  93         sizeof(unsigned long long))
  94
  95 /*
  96  * LZ4_stream_t - information structure to track an LZ4 stream.
  97  */
  98 typedef struct {
  99         uint32_t hashTable[LZ4_HASH_SIZE_U32];
 100         uint32_t currentOffset;
 101         uint32_t initCheck;
 102         const uint8_t *dictionary;
 103         uint8_t *bufferStart;
 104         uint32_t dictSize;
 105 } LZ4_stream_t_internal;
 106 typedef union {
 107         unsigned long long table[LZ4_STREAMSIZE_U64];
 108         LZ4_stream_t_internal internal_donotuse;
 109 } LZ4_stream_t;
 110
 111 /*
 112  * LZ4_streamHC_t - information structure to track an LZ4HC stream.
 113  */
 114 typedef struct {
 115         unsigned int     hashTable[LZ4HC_HASHTABLESIZE];
 116         unsigned short   chainTable[LZ4HC_MAXD];
 117         /* next block to continue on current prefix */
 118         const unsigned char *end;
 119         /* All index relative to this position */
 120         const unsigned char *base;
 121         /* alternate base for extDict */
 122         const unsigned char *dictBase;
 123         /* below that point, need extDict */
 124         unsigned int     dictLimit;
 125         /* below that point, no more dict */
 126         unsigned int     lowLimit;
 127         /* index from which to continue dict update */
 128         unsigned int     nextToUpdate;
 129         unsigned int     compressionLevel;
 130 } LZ4HC_CCtx_internal;
 131 typedef union {
 132         size_t table[LZ4_STREAMHCSIZE_SIZET];
 133         LZ4HC_CCtx_internal internal_donotuse;
 134 } LZ4_streamHC_t;
 135
 136 /*-************************************************************************
 137  *      SIZE OF STATE
 138  **************************************************************************/
 139 #define LZ4_MEM_COMPRESS        LZ4_STREAMSIZE
 140 #define LZ4HC_MEM_COMPRESS      LZ4_STREAMHCSIZE
 141
 142 /*-************************************************************************
 143  *      Compression Functions
 144  **************************************************************************/
 145
 146 /**
 147  * LZ4_compressBound() - Max. output size in worst case szenarios
 148  * @isize: Size of the input data
 149  *
 150  * Return: Max. size LZ4 may output in a "worst case" szenario
 151  * (data not compressible)
 152  */
 153 static inline int LZ4_compressBound(size_t isize)
 154 {
 155         return LZ4_COMPRESSBOUND(isize);
 156 }
 157
 158 /**
 159  * LZ4_compress_default() - Compress data from source to dest
 160  * @source: source address of the original data
 161  * @dest: output buffer address of the compressed data
 162  * @inputSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE
 163  * @maxOutputSize: full or partial size of buffer 'dest'
 164  *      which must be already allocated
 165  * @wrkmem: address of the working memory.
 166  *      This requires 'workmem' of LZ4_MEM_COMPRESS.
 167  *
 168  * Compresses 'sourceSize' bytes from buffer 'source'
 169  * into already allocated 'dest' buffer of size 'maxOutputSize'.
 170  * Compression is guaranteed to succeed if
 171  * 'maxOutputSize' >= LZ4_compressBound(inputSize).
 172  * It also runs faster, so it's a recommended setting.
 173  * If the function cannot compress 'source' into a more limited 'dest' budget,
 174  * compression stops *immediately*, and the function result is zero.
 175  * As a consequence, 'dest' content is not valid.
 176  *
 177  * Return: Number of bytes written into buffer 'dest'
 178  *      (necessarily <= maxOutputSize) or 0 if compression fails
 179  */
 180 int LZ4_compress_default(const char *source, char *dest, int inputSize,
 181         int maxOutputSize, void *wrkmem);
 182
 183 /*-************************************************************************
 184  *      Decompression Functions
 185  **************************************************************************/
 186
 187 /**
 188  * LZ4_decompress_fast() - Decompresses data from 'source' into 'dest'
 189  * @source: source address of the compressed data
 190  * @dest: output buffer address of the uncompressed data
 191  *      which must be already allocated with 'originalSize' bytes
 192  * @originalSize: is the original and therefore uncompressed size
 193  *
 194  * Decompresses data from 'source' into 'dest'.
 195  * This function fully respect memory boundaries for properly formed
 196  * compressed data.
 197  * It is a bit faster than LZ4_decompress_safe().
 198  * However, it does not provide any protection against intentionally
 199  * modified data stream (malicious input).
 200  * Use this function in trusted environment only
 201  * (data to decode comes from a trusted source).
 202  *
 203  * Return: number of bytes read from the source buffer
 204  *      or a negative result if decompression fails.
 205  */
 206 int LZ4_decompress_fast(const char *source, char *dest, int originalSize);
 207
 208 /**
 209  * LZ4_decompress_safe() - Decompression protected against buffer overflow
 210  * @source: source address of the compressed data
 211  * @dest: output buffer address of the uncompressed data
 212  *      which must be already allocated
 213  * @compressedSize: is the precise full size of the compressed block
 214  * @maxDecompressedSize: is the size of 'dest' buffer
 215  *
 216  * Decompresses data from 'source' into 'dest'.
 217  * If the source stream is detected malformed, the function will
 218  * stop decoding and return a negative result.
 219  * This function is protected against buffer overflow exploits,
 220  * including malicious data packets. It never writes outside output buffer,
 221  * nor reads outside input buffer.
 222  *
 223  * Return: number of bytes decompressed into destination buffer
 224  *      (necessarily <= maxDecompressedSize)
 225  *      or a negative result in case of error
 226  */
 227 int LZ4_decompress_safe(const char *source, char *dest, int compressedSize,
 228         int maxDecompressedSize);
 229
 230 /*-************************************************************************
 231  *      LZ4 HC Compression
 232  **************************************************************************/
 233
 234 /**
 235  * LZ4_compress_HC() - Compress data from `src` into `dst`, using HC algorithm
 236  * @src: source address of the original data
 237  * @dst: output buffer address of the compressed data
 238  * @srcSize: size of the input data. Max supported value is LZ4_MAX_INPUT_SIZE
 239  * @dstCapacity: full or partial size of buffer 'dst',
 240  *      which must be already allocated
 241  * @compressionLevel: Recommended values are between 4 and 9, although any
 242  *      value between 1 and LZ4HC_MAX_CLEVEL will work.
 243  *      Values >LZ4HC_MAX_CLEVEL behave the same as 16.
 244  * @wrkmem: address of the working memory.
 245  *      This requires 'wrkmem' of size LZ4HC_MEM_COMPRESS.
 246  *
 247  * Compress data from 'src' into 'dst', using the more powerful
 248  * but slower "HC" algorithm. Compression is guaranteed to succeed if
 249  * `dstCapacity >= LZ4_compressBound(srcSize)
 250  *
 251  * Return : the number of bytes written into 'dst' or 0 if compression fails.
 252  */
 253 int LZ4_compress_HC(const char *src, char *dst, int srcSize, int dstCapacity,
 254         int compressionLevel, void *wrkmem);
 255
 256 #endif