1// SPDX-License-Identifier: GPL-2.0
2/*
3 *
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
5 *
6 */
7
8#include <linux/kernel.h>
9#include <linux/slab.h>
10#include <linux/stddef.h>
11#include <linux/string.h>
12#include <linux/types.h>
13
14#include "debug.h"
15#include "ntfs_fs.h"
16
17// clang-format off
18/* Src buffer is zero. */
19#define LZNT_ERROR_ALL_ZEROS	1
20#define LZNT_CHUNK_SIZE		0x1000
21// clang-format on
22
23struct lznt_hash {
24	const u8 *p1;
25	const u8 *p2;
26};
27
28struct lznt {
29	const u8 *unc;
30	const u8 *unc_end;
31	const u8 *best_match;
32	size_t max_len;
33	bool std;
34
35	struct lznt_hash hash[LZNT_CHUNK_SIZE];
36};
37
38static inline size_t get_match_len(const u8 *ptr, const u8 *end, const u8 *prev,
39				   size_t max_len)
40{
41	size_t len = 0;
42
43	while (ptr + len < end && ptr[len] == prev[len] && ++len < max_len)
44		;
45	return len;
46}
47
48static size_t longest_match_std(const u8 *src, struct lznt *ctx)
49{
50	size_t hash_index;
51	size_t len1 = 0, len2 = 0;
52	const u8 **hash;
53
54	hash_index =
55		((40543U * ((((src[0] << 4) ^ src[1]) << 4) ^ src[2])) >> 4) &
56		(LZNT_CHUNK_SIZE - 1);
57
58	hash = &(ctx->hash[hash_index].p1);
59
60	if (hash[0] >= ctx->unc && hash[0] < src && hash[0][0] == src[0] &&
61	    hash[0][1] == src[1] && hash[0][2] == src[2]) {
62		len1 = 3;
63		if (ctx->max_len > 3)
64			len1 += get_match_len(src + 3, ctx->unc_end,
65					      hash[0] + 3, ctx->max_len - 3);
66	}
67
68	if (hash[1] >= ctx->unc && hash[1] < src && hash[1][0] == src[0] &&
69	    hash[1][1] == src[1] && hash[1][2] == src[2]) {
70		len2 = 3;
71		if (ctx->max_len > 3)
72			len2 += get_match_len(src + 3, ctx->unc_end,
73					      hash[1] + 3, ctx->max_len - 3);
74	}
75
76	/* Compare two matches and select the best one. */
77	if (len1 < len2) {
78		ctx->best_match = hash[1];
79		len1 = len2;
80	} else {
81		ctx->best_match = hash[0];
82	}
83
84	hash[1] = hash[0];
85	hash[0] = src;
86	return len1;
87}
88
89static size_t longest_match_best(const u8 *src, struct lznt *ctx)
90{
91	size_t max_len;
92	const u8 *ptr;
93
94	if (ctx->unc >= src || !ctx->max_len)
95		return 0;
96
97	max_len = 0;
98	for (ptr = ctx->unc; ptr < src; ++ptr) {
99		size_t len =
100			get_match_len(src, ctx->unc_end, ptr, ctx->max_len);
101		if (len >= max_len) {
102			max_len = len;
103			ctx->best_match = ptr;
104		}
105	}
106
107	return max_len >= 3 ? max_len : 0;
108}
109
110static const size_t s_max_len[] = {
111	0x1002, 0x802, 0x402, 0x202, 0x102, 0x82, 0x42, 0x22, 0x12,
112};
113
114static const size_t s_max_off[] = {
115	0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
116};
117
118static inline u16 make_pair(size_t offset, size_t len, size_t index)
119{
120	return ((offset - 1) << (12 - index)) |
121	       ((len - 3) & (((1 << (12 - index)) - 1)));
122}
123
124static inline size_t parse_pair(u16 pair, size_t *offset, size_t index)
125{
126	*offset = 1 + (pair >> (12 - index));
127	return 3 + (pair & ((1 << (12 - index)) - 1));
128}
129
130/*
131 * compress_chunk
132 *
133 * Return:
134 * * 0	- Ok, @cmpr contains @cmpr_chunk_size bytes of compressed data.
135 * * 1	- Input buffer is full zero.
136 * * -2 - The compressed buffer is too small to hold the compressed data.
137 */
138static inline int compress_chunk(size_t (*match)(const u8 *, struct lznt *),
139				 const u8 *unc, const u8 *unc_end, u8 *cmpr,
140				 u8 *cmpr_end, size_t *cmpr_chunk_size,
141				 struct lznt *ctx)
142{
143	size_t cnt = 0;
144	size_t idx = 0;
145	const u8 *up = unc;
146	u8 *cp = cmpr + 3;
147	u8 *cp2 = cmpr + 2;
148	u8 not_zero = 0;
149	/* Control byte of 8-bit values: ( 0 - means byte as is, 1 - short pair ). */
150	u8 ohdr = 0;
151	u8 *last;
152	u16 t16;
153
154	if (unc + LZNT_CHUNK_SIZE < unc_end)
155		unc_end = unc + LZNT_CHUNK_SIZE;
156
157	last = min(cmpr + LZNT_CHUNK_SIZE + sizeof(short), cmpr_end);
158
159	ctx->unc = unc;
160	ctx->unc_end = unc_end;
161	ctx->max_len = s_max_len[0];
162
163	while (up < unc_end) {
164		size_t max_len;
165
166		while (unc + s_max_off[idx] < up)
167			ctx->max_len = s_max_len[++idx];
168
169		/* Find match. */
170		max_len = up + 3 <= unc_end ? (*match)(up, ctx) : 0;
171
172		if (!max_len) {
173			if (cp >= last)
174				goto NotCompressed;
175			not_zero |= *cp++ = *up++;
176		} else if (cp + 1 >= last) {
177			goto NotCompressed;
178		} else {
179			t16 = make_pair(up - ctx->best_match, max_len, idx);
180			*cp++ = t16;
181			*cp++ = t16 >> 8;
182
183			ohdr |= 1 << cnt;
184			up += max_len;
185		}
186
187		cnt = (cnt + 1) & 7;
188		if (!cnt) {
189			*cp2 = ohdr;
190			ohdr = 0;
191			cp2 = cp;
192			cp += 1;
193		}
194	}
195
196	if (cp2 < last)
197		*cp2 = ohdr;
198	else
199		cp -= 1;
200
201	*cmpr_chunk_size = cp - cmpr;
202
203	t16 = (*cmpr_chunk_size - 3) | 0xB000;
204	cmpr[0] = t16;
205	cmpr[1] = t16 >> 8;
206
207	return not_zero ? 0 : LZNT_ERROR_ALL_ZEROS;
208
209NotCompressed:
210
211	if ((cmpr + LZNT_CHUNK_SIZE + sizeof(short)) > last)
212		return -2;
213
214	/*
215	 * Copy non cmpr data.
216	 * 0x3FFF == ((LZNT_CHUNK_SIZE + 2 - 3) | 0x3000)
217	 */
218	cmpr[0] = 0xff;
219	cmpr[1] = 0x3f;
220
221	memcpy(cmpr + sizeof(short), unc, LZNT_CHUNK_SIZE);
222	*cmpr_chunk_size = LZNT_CHUNK_SIZE + sizeof(short);
223
224	return 0;
225}
226
227static inline ssize_t decompress_chunk(u8 *unc, u8 *unc_end, const u8 *cmpr,
228				       const u8 *cmpr_end)
229{
230	u8 *up = unc;
231	u8 ch = *cmpr++;
232	size_t bit = 0;
233	size_t index = 0;
234	u16 pair;
235	size_t offset, length;
236
237	/* Do decompression until pointers are inside range. */
238	while (up < unc_end && cmpr < cmpr_end) {
239		/* Correct index */
240		while (unc + s_max_off[index] < up)
241			index += 1;
242
243		/* Check the current flag for zero. */
244		if (!(ch & (1 << bit))) {
245			/* Just copy byte. */
246			*up++ = *cmpr++;
247			goto next;
248		}
249
250		/* Check for boundary. */
251		if (cmpr + 1 >= cmpr_end)
252			return -EINVAL;
253
254		/* Read a short from little endian stream. */
255		pair = cmpr[1];
256		pair <<= 8;
257		pair |= cmpr[0];
258
259		cmpr += 2;
260
261		/* Translate packed information into offset and length. */
262		length = parse_pair(pair, &offset, index);
263
264		/* Check offset for boundary. */
265		if (unc + offset > up)
266			return -EINVAL;
267
268		/* Truncate the length if necessary. */
269		if (up + length >= unc_end)
270			length = unc_end - up;
271
272		/* Now we copy bytes. This is the heart of LZ algorithm. */
273		for (; length > 0; length--, up++)
274			*up = *(up - offset);
275
276next:
277		/* Advance flag bit value. */
278		bit = (bit + 1) & 7;
279
280		if (!bit) {
281			if (cmpr >= cmpr_end)
282				break;
283
284			ch = *cmpr++;
285		}
286	}
287
288	/* Return the size of uncompressed data. */
289	return up - unc;
290}
291
292/*
293 * get_lznt_ctx
294 * @level: 0 - Standard compression.
295 *	   !0 - Best compression, requires a lot of cpu.
296 */
297struct lznt *get_lznt_ctx(int level)
298{
299	struct lznt *r = kzalloc(level ? offsetof(struct lznt, hash) :
300					 sizeof(struct lznt),
301				 GFP_NOFS);
302
303	if (r)
304		r->std = !level;
305	return r;
306}
307
308/*
309 * compress_lznt - Compresses @unc into @cmpr
310 *
311 * Return:
312 * * +x - Ok, @cmpr contains 'final_compressed_size' bytes of compressed data.
313 * * 0 - Input buffer is full zero.
314 */
315size_t compress_lznt(const void *unc, size_t unc_size, void *cmpr,
316		     size_t cmpr_size, struct lznt *ctx)
317{
318	int err;
319	size_t (*match)(const u8 *src, struct lznt *ctx);
320	u8 *p = cmpr;
321	u8 *end = p + cmpr_size;
322	const u8 *unc_chunk = unc;
323	const u8 *unc_end = unc_chunk + unc_size;
324	bool is_zero = true;
325
326	if (ctx->std) {
327		match = &longest_match_std;
328		memset(ctx->hash, 0, sizeof(ctx->hash));
329	} else {
330		match = &longest_match_best;
331	}
332
333	/* Compression cycle. */
334	for (; unc_chunk < unc_end; unc_chunk += LZNT_CHUNK_SIZE) {
335		cmpr_size = 0;
336		err = compress_chunk(match, unc_chunk, unc_end, p, end,
337				     &cmpr_size, ctx);
338		if (err < 0)
339			return unc_size;
340
341		if (is_zero && err != LZNT_ERROR_ALL_ZEROS)
342			is_zero = false;
343
344		p += cmpr_size;
345	}
346
347	if (p <= end - 2)
348		p[0] = p[1] = 0;
349
350	return is_zero ? 0 : PtrOffset(cmpr, p);
351}
352
353/*
354 * decompress_lznt - Decompress @cmpr into @unc.
355 */
356ssize_t decompress_lznt(const void *cmpr, size_t cmpr_size, void *unc,
357			size_t unc_size)
358{
359	const u8 *cmpr_chunk = cmpr;
360	const u8 *cmpr_end = cmpr_chunk + cmpr_size;
361	u8 *unc_chunk = unc;
362	u8 *unc_end = unc_chunk + unc_size;
363	u16 chunk_hdr;
364
365	if (cmpr_size < sizeof(short))
366		return -EINVAL;
367
368	/* Read chunk header. */
369	chunk_hdr = cmpr_chunk[1];
370	chunk_hdr <<= 8;
371	chunk_hdr |= cmpr_chunk[0];
372
373	/* Loop through decompressing chunks. */
374	for (;;) {
375		size_t chunk_size_saved;
376		size_t unc_use;
377		size_t cmpr_use = 3 + (chunk_hdr & (LZNT_CHUNK_SIZE - 1));
378
379		/* Check that the chunk actually fits the supplied buffer. */
380		if (cmpr_chunk + cmpr_use > cmpr_end)
381			return -EINVAL;
382
383		/* First make sure the chunk contains compressed data. */
384		if (chunk_hdr & 0x8000) {
385			/* Decompress a chunk and return if we get an error. */
386			ssize_t err =
387				decompress_chunk(unc_chunk, unc_end,
388						 cmpr_chunk + sizeof(chunk_hdr),
389						 cmpr_chunk + cmpr_use);
390			if (err < 0)
391				return err;
392			unc_use = err;
393		} else {
394			/* This chunk does not contain compressed data. */
395			unc_use = unc_chunk + LZNT_CHUNK_SIZE > unc_end ?
396					  unc_end - unc_chunk :
397					  LZNT_CHUNK_SIZE;
398
399			if (cmpr_chunk + sizeof(chunk_hdr) + unc_use >
400			    cmpr_end) {
401				return -EINVAL;
402			}
403
404			memcpy(unc_chunk, cmpr_chunk + sizeof(chunk_hdr),
405			       unc_use);
406		}
407
408		/* Advance pointers. */
409		cmpr_chunk += cmpr_use;
410		unc_chunk += unc_use;
411
412		/* Check for the end of unc buffer. */
413		if (unc_chunk >= unc_end)
414			break;
415
416		/* Proceed the next chunk. */
417		if (cmpr_chunk > cmpr_end - 2)
418			break;
419
420		chunk_size_saved = LZNT_CHUNK_SIZE;
421
422		/* Read chunk header. */
423		chunk_hdr = cmpr_chunk[1];
424		chunk_hdr <<= 8;
425		chunk_hdr |= cmpr_chunk[0];
426
427		if (!chunk_hdr)
428			break;
429
430		/* Check the size of unc buffer. */
431		if (unc_use < chunk_size_saved) {
432			size_t t1 = chunk_size_saved - unc_use;
433			u8 *t2 = unc_chunk + t1;
434
435			/* 'Zero' memory. */
436			if (t2 >= unc_end)
437				break;
438
439			memset(unc_chunk, 0, t1);
440			unc_chunk = t2;
441		}
442	}
443
444	/* Check compression boundary. */
445	if (cmpr_chunk > cmpr_end)
446		return -EINVAL;
447
448	/*
449	 * The unc size is just a difference between current
450	 * pointer and original one.
451	 */
452	return PtrOffset(unc, unc_chunk);
453}
454