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 #include <linux/string.h> /* memset, memcpy */ 40 41 #define FORCE_INLINE __always_inline 42 43 /*-************************************ 44 * Basic Types 45 **************************************/ 46 #include <linux/types.h> 47 48 typedef uint8_t BYTE; 49 typedef uint16_t U16; 50 typedef uint32_t U32; 51 typedef int32_t S32; 52 typedef uint64_t U64; 53 typedef uintptr_t uptrval; 54 55 /*-************************************ 56 * Architecture specifics 57 **************************************/ 58 #if defined(CONFIG_64BIT) 59 #define LZ4_ARCH64 1 60 #else 61 #define LZ4_ARCH64 0 62 #endif 63 64 #if defined(__LITTLE_ENDIAN) 65 #define LZ4_LITTLE_ENDIAN 1 66 #else 67 #define LZ4_LITTLE_ENDIAN 0 68 #endif 69 70 /*-************************************ 71 * Constants 72 **************************************/ 73 #define MINMATCH 4 74 75 #define WILDCOPYLENGTH 8 76 #define LASTLITERALS 5 77 #define MFLIMIT (WILDCOPYLENGTH + MINMATCH) 78 /* 79 * ensure it's possible to write 2 x wildcopyLength 80 * without overflowing output buffer 81 */ 82 #define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH) 83 84 /* Increase this value ==> compression run slower on incompressible data */ 85 #define LZ4_SKIPTRIGGER 6 86 87 #define HASH_UNIT sizeof(size_t) 88 89 #define KB (1 << 10) 90 #define MB (1 << 20) 91 #define GB (1U << 30) 92 93 #define MAXD_LOG 16 94 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) 95 #define STEPSIZE sizeof(size_t) 96 97 #define ML_BITS 4 98 #define ML_MASK ((1U << ML_BITS) - 1) 99 #define RUN_BITS (8 - ML_BITS) 100 #define RUN_MASK ((1U << RUN_BITS) - 1) 101 102 /*-************************************ 103 * Reading and writing into memory 104 **************************************/ 105 static FORCE_INLINE U16 LZ4_read16(const void *ptr) 106 { 107 return get_unaligned((const U16 *)ptr); 108 } 109 110 static FORCE_INLINE U32 LZ4_read32(const void *ptr) 111 { 112 return get_unaligned((const U32 *)ptr); 113 } 114 115 static FORCE_INLINE size_t LZ4_read_ARCH(const void *ptr) 116 { 117 return get_unaligned((const size_t *)ptr); 118 } 119 120 static FORCE_INLINE void LZ4_write16(void *memPtr, U16 value) 121 { 122 put_unaligned(value, (U16 *)memPtr); 123 } 124 125 static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value) 126 { 127 put_unaligned(value, (U32 *)memPtr); 128 } 129 130 static FORCE_INLINE U16 LZ4_readLE16(const void *memPtr) 131 { 132 return get_unaligned_le16(memPtr); 133 } 134 135 static FORCE_INLINE void LZ4_writeLE16(void *memPtr, U16 value) 136 { 137 return put_unaligned_le16(value, memPtr); 138 } 139 140 /* 141 * LZ4 relies on memcpy with a constant size being inlined. In freestanding 142 * environments, the compiler can't assume the implementation of memcpy() is 143 * standard compliant, so apply its specialized memcpy() inlining logic. When 144 * possible, use __builtin_memcpy() to tell the compiler to analyze memcpy() 145 * as-if it were standard compliant, so it can inline it in freestanding 146 * environments. This is needed when decompressing the Linux Kernel, for example. 147 */ 148 #define LZ4_memcpy(dst, src, size) __builtin_memcpy(dst, src, size) 149 #define LZ4_memmove(dst, src, size) __builtin_memmove(dst, src, size) 150 151 static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) 152 { 153 #if LZ4_ARCH64 154 U64 a = get_unaligned((const U64 *)src); 155 156 put_unaligned(a, (U64 *)dst); 157 #else 158 U32 a = get_unaligned((const U32 *)src); 159 U32 b = get_unaligned((const U32 *)src + 1); 160 161 put_unaligned(a, (U32 *)dst); 162 put_unaligned(b, (U32 *)dst + 1); 163 #endif 164 } 165 166 /* 167 * customized variant of memcpy, 168 * which can overwrite up to 7 bytes beyond dstEnd 169 */ 170 static FORCE_INLINE void LZ4_wildCopy(void *dstPtr, 171 const void *srcPtr, void *dstEnd) 172 { 173 BYTE *d = (BYTE *)dstPtr; 174 const BYTE *s = (const BYTE *)srcPtr; 175 BYTE *const e = (BYTE *)dstEnd; 176 177 do { 178 LZ4_copy8(d, s); 179 d += 8; 180 s += 8; 181 } while (d < e); 182 } 183 184 static FORCE_INLINE unsigned int LZ4_NbCommonBytes(register size_t val) 185 { 186 #if LZ4_LITTLE_ENDIAN 187 return __ffs(val) >> 3; 188 #else 189 return (BITS_PER_LONG - 1 - __fls(val)) >> 3; 190 #endif 191 } 192 193 static FORCE_INLINE unsigned int LZ4_count( 194 const BYTE *pIn, 195 const BYTE *pMatch, 196 const BYTE *pInLimit) 197 { 198 const BYTE *const pStart = pIn; 199 200 while (likely(pIn < pInLimit - (STEPSIZE - 1))) { 201 size_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); 202 203 if (!diff) { 204 pIn += STEPSIZE; 205 pMatch += STEPSIZE; 206 continue; 207 } 208 209 pIn += LZ4_NbCommonBytes(diff); 210 211 return (unsigned int)(pIn - pStart); 212 } 213 214 #if LZ4_ARCH64 215 if ((pIn < (pInLimit - 3)) 216 && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { 217 pIn += 4; 218 pMatch += 4; 219 } 220 #endif 221 222 if ((pIn < (pInLimit - 1)) 223 && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { 224 pIn += 2; 225 pMatch += 2; 226 } 227 228 if ((pIn < pInLimit) && (*pMatch == *pIn)) 229 pIn++; 230 231 return (unsigned int)(pIn - pStart); 232 } 233 234 typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; 235 typedef enum { byPtr, byU32, byU16 } tableType_t; 236 237 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; 238 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; 239 240 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; 241 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive; 242 243 #define LZ4_STATIC_ASSERT(c) BUILD_BUG_ON(!(c)) 244 245 #endif 246