5 * lz4defs.h -- common and architecture specific defines for the kernel usage
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
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
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
34 * Changed for kernel usage by:
35 * Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
38 #include <linux/unaligned.h>
40 #include <linux/bitops.h>
41 #include <linux/string.h> /* memset, memcpy */
43 #define FORCE_INLINE __always_inline
45 /*-************************************
47 **************************************/
48 #include <linux/types.h>
55 typedef uintptr_t uptrval
;
57 /*-************************************
58 * Architecture specifics
59 **************************************/
60 #if defined(CONFIG_64BIT)
66 #if defined(__LITTLE_ENDIAN)
67 #define LZ4_LITTLE_ENDIAN 1
69 #define LZ4_LITTLE_ENDIAN 0
72 /*-************************************
74 **************************************/
77 #define WILDCOPYLENGTH 8
78 #define LASTLITERALS 5
79 #define MFLIMIT (WILDCOPYLENGTH + MINMATCH)
81 * ensure it's possible to write 2 x wildcopyLength
82 * without overflowing output buffer
84 #define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH)
86 /* Increase this value ==> compression run slower on incompressible data */
87 #define LZ4_SKIPTRIGGER 6
89 #define HASH_UNIT sizeof(size_t)
96 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
97 #define STEPSIZE sizeof(size_t)
100 #define ML_MASK ((1U << ML_BITS) - 1)
101 #define RUN_BITS (8 - ML_BITS)
102 #define RUN_MASK ((1U << RUN_BITS) - 1)
104 /*-************************************
105 * Reading and writing into memory
106 **************************************/
107 static FORCE_INLINE U16
LZ4_read16(const void *ptr
)
109 return get_unaligned((const U16
*)ptr
);
112 static FORCE_INLINE U32
LZ4_read32(const void *ptr
)
114 return get_unaligned((const U32
*)ptr
);
117 static FORCE_INLINE
size_t LZ4_read_ARCH(const void *ptr
)
119 return get_unaligned((const size_t *)ptr
);
122 static FORCE_INLINE
void LZ4_write16(void *memPtr
, U16 value
)
124 put_unaligned(value
, (U16
*)memPtr
);
127 static FORCE_INLINE
void LZ4_write32(void *memPtr
, U32 value
)
129 put_unaligned(value
, (U32
*)memPtr
);
132 static FORCE_INLINE U16
LZ4_readLE16(const void *memPtr
)
134 return get_unaligned_le16(memPtr
);
137 static FORCE_INLINE
void LZ4_writeLE16(void *memPtr
, U16 value
)
139 return put_unaligned_le16(value
, memPtr
);
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.
150 #define LZ4_memcpy(dst, src, size) __builtin_memcpy(dst, src, size)
151 #define LZ4_memmove(dst, src, size) __builtin_memmove(dst, src, size)
153 static FORCE_INLINE
void LZ4_copy8(void *dst
, const void *src
)
156 U64 a
= get_unaligned((const U64
*)src
);
158 put_unaligned(a
, (U64
*)dst
);
160 U32 a
= get_unaligned((const U32
*)src
);
161 U32 b
= get_unaligned((const U32
*)src
+ 1);
163 put_unaligned(a
, (U32
*)dst
);
164 put_unaligned(b
, (U32
*)dst
+ 1);
169 * customized variant of memcpy,
170 * which can overwrite up to 7 bytes beyond dstEnd
172 static FORCE_INLINE
void LZ4_wildCopy(void *dstPtr
,
173 const void *srcPtr
, void *dstEnd
)
175 BYTE
*d
= (BYTE
*)dstPtr
;
176 const BYTE
*s
= (const BYTE
*)srcPtr
;
177 BYTE
*const e
= (BYTE
*)dstEnd
;
186 static FORCE_INLINE
unsigned int LZ4_NbCommonBytes(register size_t val
)
188 #if LZ4_LITTLE_ENDIAN
189 return __ffs(val
) >> 3;
191 return (BITS_PER_LONG
- 1 - __fls(val
)) >> 3;
195 static FORCE_INLINE
unsigned int LZ4_count(
198 const BYTE
*pInLimit
)
200 const BYTE
*const pStart
= pIn
;
202 while (likely(pIn
< pInLimit
- (STEPSIZE
- 1))) {
203 size_t const diff
= LZ4_read_ARCH(pMatch
) ^ LZ4_read_ARCH(pIn
);
211 pIn
+= LZ4_NbCommonBytes(diff
);
213 return (unsigned int)(pIn
- pStart
);
217 if ((pIn
< (pInLimit
- 3))
218 && (LZ4_read32(pMatch
) == LZ4_read32(pIn
))) {
224 if ((pIn
< (pInLimit
- 1))
225 && (LZ4_read16(pMatch
) == LZ4_read16(pIn
))) {
230 if ((pIn
< pInLimit
) && (*pMatch
== *pIn
))
233 return (unsigned int)(pIn
- pStart
);
236 typedef enum { noLimit
= 0, limitedOutput
= 1 } limitedOutput_directive
;
237 typedef enum { byPtr
, byU32
, byU16
} tableType_t
;
239 typedef enum { noDict
= 0, withPrefix64k
, usingExtDict
} dict_directive
;
240 typedef enum { noDictIssue
= 0, dictSmall
} dictIssue_directive
;
242 typedef enum { endOnOutputSize
= 0, endOnInputSize
= 1 } endCondition_directive
;
243 typedef enum { decode_full_block
= 0, partial_decode
= 1 } earlyEnd_directive
;
245 #define LZ4_STATIC_ASSERT(c) BUILD_BUG_ON(!(c))