1 #ifndef __LZ4DEFS_H__ 2 #define __LZ4DEFS_H__ 3 4 /* 5 * lz4defs.h -- common and architecture specific defines for the kernel usage 6 7 * LZ4 - Fast LZ compression algorithm 8 * 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 without 11 * modification, are permitted provided that the following conditions are 12 * met: 13 * * Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * * Redistributions in binary form must reproduce the above 16 * copyright notice, this list of conditions and the following disclaimer 17 * in the documentation and/or other materials provided with the 18 * distribution. 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * 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.org 32 * - LZ4 source repository : https://github.com/lz4/lz4 33 * 34 * Changed for kernel usage by: 35 * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> 36 */ 37 38 #include <asm/unaligned.h> 39 40 #include <linux/bitops.h> 41 #include <linux/string.h> /* memset, memcpy */ 42 43 #define FORCE_INLINE __always_inline 44 45 /*-************************************ 46 * Basic Types 47 **************************************/ 48 #include <linux/types.h> 49 50 typedef uint8_t BYTE; 51 typedef uint16_t U16; 52 typedef uint32_t U32; 53 typedef int32_t S32; 54 typedef uint64_t U64; 55 typedef uintptr_t uptrval; 56 57 /*-************************************ 58 * Architecture specifics 59 **************************************/ 60 #if defined(CONFIG_64BIT) 61 #define LZ4_ARCH64 1 62 #else 63 #define LZ4_ARCH64 0 64 #endif 65 66 #if defined(__LITTLE_ENDIAN) 67 #define LZ4_LITTLE_ENDIAN 1 68 #else 69 #define LZ4_LITTLE_ENDIAN 0 70 #endif 71 72 /*-************************************ 73 * Constants 74 **************************************/ 75 #define MINMATCH 4 76 77 #define WILDCOPYLENGTH 8 78 #define LASTLITERALS 5 79 #define MFLIMIT (WILDCOPYLENGTH + MINMATCH) 80 /* 81 * ensure it's possible to write 2 x wildcopyLength 82 * without overflowing output buffer 83 */ 84 #define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH) 85 86 /* Increase this value ==> compression run slower on incompressible data */ 87 #define LZ4_SKIPTRIGGER 6 88 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 16 96 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 97 #define STEPSIZE sizeof(size_t) 98 99 #define ML_BITS 4 100 #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 memory 106 **************************************/ 107 static FORCE_INLINE U16 LZ4_read16(const void *ptr) 108 { 109 return get_unaligned((const U16 *)ptr); 110 } 111 112 static FORCE_INLINE U32 LZ4_read32(const void *ptr) 113 { 114 return get_unaligned((const U32 *)ptr); 115 } 116 117 static FORCE_INLINE size_t LZ4_read_ARCH(const void *ptr) 118 { 119 return get_unaligned((const size_t *)ptr); 120 } 121 122 static FORCE_INLINE void LZ4_write16(void *memPtr, U16 value) 123 { 124 put_unaligned(value, (U16 *)memPtr); 125 } 126 127 static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value) 128 { 129 put_unaligned(value, (U32 *)memPtr); 130 } 131 132 static FORCE_INLINE U16 LZ4_readLE16(const void *memPtr) 133 { 134 return get_unaligned_le16(memPtr); 135 } 136 137 static 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 freestanding 144 * environments, the compiler can't assume the implementation of memcpy() is 145 * standard compliant, so apply its specialized memcpy() inlining logic. When 146 * possible, use __builtin_memcpy() to tell the compiler to analyze memcpy() 147 * as-if it were standard compliant, so it can inline it in freestanding 148 * 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 153 static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) 154 { 155 #if LZ4_ARCH64 156 U64 a = get_unaligned((const U64 *)src); 157 158 put_unaligned(a, (U64 *)dst); 159 #else 160 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 #endif 166 } 167 168 /* 169 * customized variant of memcpy, 170 * which can overwrite up to 7 bytes beyond dstEnd 171 */ 172 static 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 186 static FORCE_INLINE unsigned int LZ4_NbCommonBytes(register size_t val) 187 { 188 #if LZ4_LITTLE_ENDIAN 189 return __ffs(val) >> 3; 190 #else 191 return (BITS_PER_LONG - 1 - __fls(val)) >> 3; 192 #endif 193 } 194 195 static 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_ARCH64 217 if ((pIn < (pInLimit - 3)) 218 && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { 219 pIn += 4; 220 pMatch += 4; 221 } 222 #endif 223 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 236 typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; 237 typedef enum { byPtr, byU32, byU16 } tableType_t; 238 239 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; 240 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; 241 242 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; 243 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive; 244 245 #define LZ4_STATIC_ASSERT(c) BUILD_BUG_ON(!(c)) 246 247 #endif 248