projects/linux·blob master · refs

247 lines · 6.7 KiB

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 <[email protected]>
36 */
37
38#include <linux/unaligned.h>
39
40#include <linux/bitops.h>
41#include <linux/string.h> /* memset, memcpy */
42#include <linux/lz4.h>
43
44#define FORCE_INLINE __always_inline
45
46/*-************************************
47 * Basic Types
48 **************************************/
49#include <linux/types.h>
50
51typedef uint8_t BYTE;
52typedef uint16_t U16;
53typedef uint32_t U32;
54typedef int32_t S32;
55typedef uint64_t U64;
56typedef uintptr_t uptrval;
57
58/*-************************************
59 * Architecture specifics
60 **************************************/
61#if defined(CONFIG_64BIT)
62#define LZ4_ARCH64 1
63#else
64#define LZ4_ARCH64 0
65#endif
66
67#if defined(__LITTLE_ENDIAN)
68#define LZ4_LITTLE_ENDIAN 1
69#else
70#define LZ4_LITTLE_ENDIAN 0
71#endif
72
73/*-************************************
74 * Constants
75 **************************************/
76#define MINMATCH 4
77
78#define WILDCOPYLENGTH 8
79#define LASTLITERALS 5
80#define MFLIMIT (WILDCOPYLENGTH + MINMATCH)
81/*
82 * ensure it's possible to write 2 x wildcopyLength
83 * without overflowing output buffer
84 */
85#define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH)
86
87/* Increase this value ==> compression run slower on incompressible data */
88#define LZ4_SKIPTRIGGER 6
89
90#define HASH_UNIT sizeof(size_t)
91
92#define KB (1 << 10)
93#define MB (1 << 20)
94#define GB (1U << 30)
95
96#define MAX_DISTANCE LZ4_DISTANCE_MAX
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 **************************************/
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 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
153static 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 */
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_ENDIAN
189 return __ffs(val) >> 3;
190#else
191 return (BITS_PER_LONG - 1 - __fls(val)) >> 3;
192#endif
193}
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_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
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#endif