xref: /linux/fs/smb/client/compress/lz77.h (revision d14bbfff259cadb5af84413658699159556da156) 
1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /*
3  * Copyright (C) 2024, SUSE LLC
4  *
5  * Authors: Enzo Matsumiya <ematsumiya@suse.de>
6  *
7  * Definitions and optmized helpers for LZ77 compression.
8  */
9 #ifndef _SMB_COMPRESS_LZ77_H
10 #define _SMB_COMPRESS_LZ77_H
11 
12 #include <linux/uaccess.h>
13 #ifdef CONFIG_CIFS_COMPRESSION
14 #include <asm/ptrace.h>
15 #include <linux/kernel.h>
16 #include <linux/string.h>
17 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
18 #include <asm-generic/unaligned.h>
19 #endif
20 
21 #define LZ77_HASH_LOG		13
22 #define LZ77_HASH_SIZE		(1 << LZ77_HASH_LOG)
23 #define LZ77_HASH_MASK		lz77_hash_mask(LZ77_HASH_LOG)
24 
25 /* We can increase this for better compression (but worse performance). */
26 #define LZ77_MATCH_MIN_LEN	3
27 /* From MS-XCA, but it's arbitrarily chosen. */
28 #define LZ77_MATCH_MAX_LEN	S32_MAX
29 /*
30  * Check this to ensure we don't match the current position, which would
31  * end up doing a verbatim copy of the input, and actually overflowing
32  * the output buffer because of the encoded metadata.
33  */
34 #define LZ77_MATCH_MIN_DIST	1
35 /* How far back in the buffer can we try to find a match (i.e. window size) */
36 #define LZ77_MATCH_MAX_DIST	8192
37 
38 #define LZ77_STEPSIZE_16	sizeof(u16)
39 #define LZ77_STEPSIZE_32	sizeof(u32)
40 #define LZ77_STEPSIZE_64	sizeof(u64)
41 
42 struct lz77_flags {
43 	u8 *pos;
44 	size_t count;
45 	long val;
46 };
47 
48 static __always_inline u32 lz77_hash_mask(const unsigned int log2)
49 {
50 	return ((1 << log2) - 1);
51 }
52 
53 static __always_inline u32 lz77_hash64(const u64 v, const unsigned int log2)
54 {
55 	const u64 prime5bytes = 889523592379ULL;
56 
57 	return (u32)(((v << 24) * prime5bytes) >> (64 - log2));
58 }
59 
60 static __always_inline u32 lz77_hash32(const u32 v, const unsigned int log2)
61 {
62 	return ((v * 2654435769LL) >> (32 - log2)) & lz77_hash_mask(log2);
63 }
64 
65 static __always_inline u32 lz77_log2(unsigned int x)
66 {
67 	return x ? ((u32)(31 - __builtin_clz(x))) : 0;
68 }
69 
70 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
71 static __always_inline u8 lz77_read8(const void *ptr)
72 {
73 	return *(u8 *)ptr;
74 }
75 
76 static __always_inline u16 lz77_read16(const void *ptr)
77 {
78 	return *(u16 *)ptr;
79 }
80 
81 static __always_inline u32 lz77_read32(const void *ptr)
82 {
83 	return *(u32 *)ptr;
84 }
85 
86 static __always_inline u64 lz77_read64(const void *ptr)
87 {
88 	return *(u64 *)ptr;
89 }
90 
91 static __always_inline void lz77_write8(void *ptr, const u8 v)
92 {
93 	*(u8 *)ptr = v;
94 }
95 
96 static __always_inline void lz77_write16(void *ptr, const u16 v)
97 {
98 	*(u16 *)ptr = v;
99 }
100 
101 static __always_inline void lz77_write32(void *ptr, const u32 v)
102 {
103 	*(u32 *)ptr = v;
104 }
105 
106 static __always_inline void lz77_write64(void *ptr, const u64 v)
107 {
108 	*(u64 *)ptr = v;
109 }
110 
111 static __always_inline void lz77_write_ptr16(void *ptr, const void *vp)
112 {
113 	*(u16 *)ptr = *(const u16 *)vp;
114 }
115 
116 static __always_inline void lz77_write_ptr32(void *ptr, const void *vp)
117 {
118 	*(u32 *)ptr = *(const u32 *)vp;
119 }
120 
121 static __always_inline void lz77_write_ptr64(void *ptr, const void *vp)
122 {
123 	*(u64 *)ptr = *(const u64 *)vp;
124 }
125 
126 static __always_inline long lz77_copy(u8 *dst, const u8 *src, size_t count)
127 {
128 	return copy_from_kernel_nofault(dst, src, count);
129 }
130 #else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
131 static __always_inline u8 lz77_read8(const void *ptr)
132 {
133 	return get_unaligned((u8 *)ptr);
134 }
135 
136 static __always_inline u16 lz77_read16(const void *ptr)
137 {
138 	return lz77_read8(ptr) | (lz77_read8(ptr + 1) << 8);
139 }
140 
141 static __always_inline u32 lz77_read32(const void *ptr)
142 {
143 	return lz77_read16(ptr) | (lz77_read16(ptr + 2) << 16);
144 }
145 
146 static __always_inline u64 lz77_read64(const void *ptr)
147 {
148 	return lz77_read32(ptr) | ((u64)lz77_read32(ptr + 4) << 32);
149 }
150 
151 static __always_inline void lz77_write8(void *ptr, const u8 v)
152 {
153 	put_unaligned(v, (u8 *)ptr);
154 }
155 
156 static __always_inline void lz77_write16(void *ptr, const u16 v)
157 {
158 	lz77_write8(ptr, v & 0xff);
159 	lz77_write8(ptr + 1, (v >> 8) & 0xff);
160 }
161 
162 static __always_inline void lz77_write32(void *ptr, const u32 v)
163 {
164 	lz77_write16(ptr, v & 0xffff);
165 	lz77_write16(ptr + 2, (v >> 16) & 0xffff);
166 }
167 
168 static __always_inline void lz77_write64(void *ptr, const u64 v)
169 {
170 	lz77_write32(ptr, v & 0xffffffff);
171 	lz77_write32(ptr + 4, (v >> 32) & 0xffffffff);
172 }
173 
174 static __always_inline void lz77_write_ptr16(void *ptr, const void *vp)
175 {
176 	const u16 v = lz77_read16(vp);
177 
178 	lz77_write16(ptr, v);
179 }
180 
181 static __always_inline void lz77_write_ptr32(void *ptr, const void *vp)
182 {
183 	const u32 v = lz77_read32(vp);
184 
185 	lz77_write32(ptr, v);
186 }
187 
188 static __always_inline void lz77_write_ptr64(void *ptr, const void *vp)
189 {
190 	const u64 v = lz77_read64(vp);
191 
192 	lz77_write64(ptr, v);
193 }
194 static __always_inline long lz77_copy(u8 *dst, const u8 *src, size_t count)
195 {
196 	memcpy(dst, src, count);
197 	return 0;
198 }
199 #endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
200 
201 static __always_inline unsigned int __count_common_bytes(const unsigned long diff)
202 {
203 #ifdef __has_builtin
204 #  if __has_builtin(__builtin_ctzll)
205 	return (unsigned int)__builtin_ctzll(diff) >> 3;
206 #  endif
207 #else
208 	/* count trailing zeroes */
209 	unsigned long bits = 0, i, z = 0;
210 
211 	bits |= diff;
212 	for (i = 0; i < 64; i++) {
213 		if (bits[i])
214 			break;
215 		z++;
216 	}
217 
218 	return (unsigned int)z >> 3;
219 #endif
220 }
221 
222 static __always_inline size_t lz77_match(const u8 *match, const u8 *cur, const u8 *end)
223 {
224 	const u8 *start = cur;
225 
226 	if (cur == match)
227 		return 0;
228 
229 	if (likely(cur < end - (LZ77_STEPSIZE_64 - 1))) {
230 		u64 const diff = lz77_read64(cur) ^ lz77_read64(match);
231 
232 		if (!diff) {
233 			cur += LZ77_STEPSIZE_64;
234 			match += LZ77_STEPSIZE_64;
235 		} else {
236 			return __count_common_bytes(diff);
237 		}
238 	}
239 
240 	while (likely(cur < end - (LZ77_STEPSIZE_64 - 1))) {
241 		u64 const diff = lz77_read64(cur) ^ lz77_read64(match);
242 
243 		if (!diff) {
244 			cur += LZ77_STEPSIZE_64;
245 			match += LZ77_STEPSIZE_64;
246 			continue;
247 		}
248 
249 		cur += __count_common_bytes(diff);
250 		return (size_t)(cur - start);
251 	}
252 
253 	if (cur < end - 3 && !(lz77_read32(cur) ^ lz77_read32(match))) {
254 		cur += LZ77_STEPSIZE_32;
255 		match += LZ77_STEPSIZE_32;
256 	}
257 
258 	if (cur < end - 1 && lz77_read16(cur) == lz77_read16(match)) {
259 		cur += LZ77_STEPSIZE_16;
260 		match += LZ77_STEPSIZE_16;
261 	}
262 
263 	if (cur < end && *cur == *match)
264 		cur++;
265 
266 	return (size_t)(cur - start);
267 }
268 
269 static __always_inline unsigned long lz77_max(unsigned long a, unsigned long b)
270 {
271 	int m = (a < b) - 1;
272 
273 	return (a & m) | (b & ~m);
274 }
275 
276 static __always_inline unsigned long lz77_min(unsigned long a, unsigned long b)
277 {
278 	int m = (a > b) - 1;
279 
280 	return (a & m) | (b & ~m);
281 }
282 
283 int lz77_compress(const u8 *src, size_t src_len, u8 *dst, size_t *dst_len);
284 /* when CONFIG_CIFS_COMPRESSION not set lz77_compress() is not called */
285 #endif /* !CONFIG_CIFS_COMPRESSION */
286 #endif /* _SMB_COMPRESS_LZ77_H */
287