248 lines · c
1#ifndef __LZ4DEFS_H__2#define __LZ4DEFS_H__3 4/*5 * lz4defs.h -- common and architecture specific defines for the kernel usage6 7 * LZ4 - Fast LZ compression algorithm8 * Copyright (C) 2011-2016, Yann Collet.9 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)10 * Redistribution and use in source and binary forms, with or without11 * modification, are permitted provided that the following conditions are12 * met:13 * * Redistributions of source code must retain the above copyright14 * notice, this list of conditions and the following disclaimer.15 * * Redistributions in binary form must reproduce the above16 * copyright notice, this list of conditions and the following disclaimer17 * in the documentation and/or other materials provided with the18 * distribution.19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.30 * You can contact the author at :31 * - LZ4 homepage : http://www.lz4.org32 * - LZ4 source repository : https://github.com/lz4/lz433 *34 * Changed for kernel usage by:35 * Sven Schmidt <4sschmid@informatik.uni-hamburg.de>36 */37 38#include <linux/unaligned.h>39 40#include <linux/bitops.h>41#include <linux/string.h> /* memset, memcpy */42 43#define FORCE_INLINE __always_inline44 45/*-************************************46 * Basic Types47 **************************************/48#include <linux/types.h>49 50typedef uint8_t BYTE;51typedef uint16_t U16;52typedef uint32_t U32;53typedef int32_t S32;54typedef uint64_t U64;55typedef uintptr_t uptrval;56 57/*-************************************58 * Architecture specifics59 **************************************/60#if defined(CONFIG_64BIT)61#define LZ4_ARCH64 162#else63#define LZ4_ARCH64 064#endif65 66#if defined(__LITTLE_ENDIAN)67#define LZ4_LITTLE_ENDIAN 168#else69#define LZ4_LITTLE_ENDIAN 070#endif71 72/*-************************************73 * Constants74 **************************************/75#define MINMATCH 476 77#define WILDCOPYLENGTH 878#define LASTLITERALS 579#define MFLIMIT (WILDCOPYLENGTH + MINMATCH)80/*81 * ensure it's possible to write 2 x wildcopyLength82 * without overflowing output buffer83 */84#define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH)85 86/* Increase this value ==> compression run slower on incompressible data */87#define LZ4_SKIPTRIGGER 688 89#define HASH_UNIT sizeof(size_t)90 91#define KB (1 << 10)92#define MB (1 << 20)93#define GB (1U << 30)94 95#define MAXD_LOG 1696#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)97#define STEPSIZE sizeof(size_t)98 99#define ML_BITS 4100#define ML_MASK ((1U << ML_BITS) - 1)101#define RUN_BITS (8 - ML_BITS)102#define RUN_MASK ((1U << RUN_BITS) - 1)103 104/*-************************************105 * Reading and writing into memory106 **************************************/107static FORCE_INLINE U16 LZ4_read16(const void *ptr)108{109 return get_unaligned((const U16 *)ptr);110}111 112static FORCE_INLINE U32 LZ4_read32(const void *ptr)113{114 return get_unaligned((const U32 *)ptr);115}116 117static FORCE_INLINE size_t LZ4_read_ARCH(const void *ptr)118{119 return get_unaligned((const size_t *)ptr);120}121 122static FORCE_INLINE void LZ4_write16(void *memPtr, U16 value)123{124 put_unaligned(value, (U16 *)memPtr);125}126 127static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value)128{129 put_unaligned(value, (U32 *)memPtr);130}131 132static FORCE_INLINE U16 LZ4_readLE16(const void *memPtr)133{134 return get_unaligned_le16(memPtr);135}136 137static FORCE_INLINE void LZ4_writeLE16(void *memPtr, U16 value)138{139 return put_unaligned_le16(value, memPtr);140}141 142/*143 * LZ4 relies on memcpy with a constant size being inlined. In freestanding144 * environments, the compiler can't assume the implementation of memcpy() is145 * standard compliant, so apply its specialized memcpy() inlining logic. When146 * possible, use __builtin_memcpy() to tell the compiler to analyze memcpy()147 * as-if it were standard compliant, so it can inline it in freestanding148 * environments. This is needed when decompressing the Linux Kernel, for example.149 */150#define LZ4_memcpy(dst, src, size) __builtin_memcpy(dst, src, size)151#define LZ4_memmove(dst, src, size) __builtin_memmove(dst, src, size)152 153static FORCE_INLINE void LZ4_copy8(void *dst, const void *src)154{155#if LZ4_ARCH64156 U64 a = get_unaligned((const U64 *)src);157 158 put_unaligned(a, (U64 *)dst);159#else160 U32 a = get_unaligned((const U32 *)src);161 U32 b = get_unaligned((const U32 *)src + 1);162 163 put_unaligned(a, (U32 *)dst);164 put_unaligned(b, (U32 *)dst + 1);165#endif166}167 168/*169 * customized variant of memcpy,170 * which can overwrite up to 7 bytes beyond dstEnd171 */172static FORCE_INLINE void LZ4_wildCopy(void *dstPtr,173 const void *srcPtr, void *dstEnd)174{175 BYTE *d = (BYTE *)dstPtr;176 const BYTE *s = (const BYTE *)srcPtr;177 BYTE *const e = (BYTE *)dstEnd;178 179 do {180 LZ4_copy8(d, s);181 d += 8;182 s += 8;183 } while (d < e);184}185 186static FORCE_INLINE unsigned int LZ4_NbCommonBytes(register size_t val)187{188#if LZ4_LITTLE_ENDIAN189 return __ffs(val) >> 3;190#else191 return (BITS_PER_LONG - 1 - __fls(val)) >> 3;192#endif193}194 195static FORCE_INLINE unsigned int LZ4_count(196 const BYTE *pIn,197 const BYTE *pMatch,198 const BYTE *pInLimit)199{200 const BYTE *const pStart = pIn;201 202 while (likely(pIn < pInLimit - (STEPSIZE - 1))) {203 size_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);204 205 if (!diff) {206 pIn += STEPSIZE;207 pMatch += STEPSIZE;208 continue;209 }210 211 pIn += LZ4_NbCommonBytes(diff);212 213 return (unsigned int)(pIn - pStart);214 }215 216#if LZ4_ARCH64217 if ((pIn < (pInLimit - 3))218 && (LZ4_read32(pMatch) == LZ4_read32(pIn))) {219 pIn += 4;220 pMatch += 4;221 }222#endif223 224 if ((pIn < (pInLimit - 1))225 && (LZ4_read16(pMatch) == LZ4_read16(pIn))) {226 pIn += 2;227 pMatch += 2;228 }229 230 if ((pIn < pInLimit) && (*pMatch == *pIn))231 pIn++;232 233 return (unsigned int)(pIn - pStart);234}235 236typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive;237typedef enum { byPtr, byU32, byU16 } tableType_t;238 239typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;240typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;241 242typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;243typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive;244 245#define LZ4_STATIC_ASSERT(c) BUILD_BUG_ON(!(c))246 247#endif248