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(p: memPtr); |
135 | } |
136 | |
137 | static FORCE_INLINE void LZ4_writeLE16(void *memPtr, U16 value) |
138 | { |
139 | return put_unaligned_le16(val: value, p: 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(dst: d, src: 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(ptr: pMatch) ^ LZ4_read_ARCH(ptr: pIn); |
204 | |
205 | if (!diff) { |
206 | pIn += STEPSIZE; |
207 | pMatch += STEPSIZE; |
208 | continue; |
209 | } |
210 | |
211 | pIn += LZ4_NbCommonBytes(val: diff); |
212 | |
213 | return (unsigned int)(pIn - pStart); |
214 | } |
215 | |
216 | #if LZ4_ARCH64 |
217 | if ((pIn < (pInLimit - 3)) |
218 | && (LZ4_read32(ptr: pMatch) == LZ4_read32(ptr: pIn))) { |
219 | pIn += 4; |
220 | pMatch += 4; |
221 | } |
222 | #endif |
223 | |
224 | if ((pIn < (pInLimit - 1)) |
225 | && (LZ4_read16(ptr: pMatch) == LZ4_read16(ptr: 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 | |