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
23 struct lznt_hash {
24 const u8 *p1;
25 const u8 *p2;
26 };
27
28 struct 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
get_match_len(const u8 * ptr,const u8 * end,const u8 * prev,size_t max_len)38 static 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
longest_match_std(const u8 * src,struct lznt * ctx)48 static 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
longest_match_best(const u8 * src,struct lznt * ctx)89 static 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
110 static const size_t s_max_len[] = {
111 0x1002, 0x802, 0x402, 0x202, 0x102, 0x82, 0x42, 0x22, 0x12,
112 };
113
114 static const size_t s_max_off[] = {
115 0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
116 };
117
make_pair(size_t offset,size_t len,size_t index)118 static 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
parse_pair(u16 pair,size_t * offset,size_t index)124 static 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 */
compress_chunk(size_t (* match)(const u8 *,struct lznt *),const u8 * unc,const u8 * unc_end,u8 * cmpr,u8 * cmpr_end,size_t * cmpr_chunk_size,struct lznt * ctx)138 static 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
209 NotCompressed:
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
decompress_chunk(u8 * unc,u8 * unc_end,const u8 * cmpr,const u8 * cmpr_end)227 static 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 // return err if more than LZNT_CHUNK_SIZE bytes are written
240 if (up - unc > LZNT_CHUNK_SIZE)
241 return -EINVAL;
242 /* Correct index */
243 while (index < ARRAY_SIZE(s_max_off) - 1 &&
244 unc + s_max_off[index] < up) {
245 index += 1;
246 }
247
248 /* Check the current flag for zero. */
249 if (!(ch & (1 << bit))) {
250 /* Just copy byte. */
251 *up++ = *cmpr++;
252 goto next;
253 }
254
255 /* Check for boundary. */
256 if (cmpr + 1 >= cmpr_end)
257 return -EINVAL;
258
259 /* Read a short from little endian stream. */
260 pair = cmpr[1];
261 pair <<= 8;
262 pair |= cmpr[0];
263
264 cmpr += 2;
265
266 /* Translate packed information into offset and length. */
267 length = parse_pair(pair, &offset, index);
268
269 /* Check offset for boundary. */
270 if (unc + offset > up)
271 return -EINVAL;
272
273 /* Truncate the length if necessary. */
274 if (up + length >= unc_end)
275 length = unc_end - up;
276
277 /* Now we copy bytes. This is the heart of LZ algorithm. */
278 for (; length > 0; length--, up++)
279 *up = *(up - offset);
280
281 next:
282 /* Advance flag bit value. */
283 bit = (bit + 1) & 7;
284
285 if (!bit) {
286 if (cmpr >= cmpr_end)
287 break;
288
289 ch = *cmpr++;
290 }
291 }
292
293 /* Return the size of uncompressed data. */
294 return up - unc;
295 }
296
297 /*
298 * get_lznt_ctx
299 * @level: 0 - Standard compression.
300 * !0 - Best compression, requires a lot of cpu.
301 */
get_lznt_ctx(int level)302 struct lznt *get_lznt_ctx(int level)
303 {
304 struct lznt *r = kzalloc(level ? offsetof(struct lznt, hash) :
305 sizeof(struct lznt),
306 GFP_NOFS);
307
308 if (r)
309 r->std = !level;
310 return r;
311 }
312
313 /*
314 * compress_lznt - Compresses @unc into @cmpr
315 *
316 * Return:
317 * * +x - Ok, @cmpr contains 'final_compressed_size' bytes of compressed data.
318 * * 0 - Input buffer is full zero.
319 */
compress_lznt(const void * unc,size_t unc_size,void * cmpr,size_t cmpr_size,struct lznt * ctx)320 size_t compress_lznt(const void *unc, size_t unc_size, void *cmpr,
321 size_t cmpr_size, struct lznt *ctx)
322 {
323 int err;
324 size_t (*match)(const u8 *src, struct lznt *ctx);
325 u8 *p = cmpr;
326 u8 *end = p + cmpr_size;
327 const u8 *unc_chunk = unc;
328 const u8 *unc_end = unc_chunk + unc_size;
329 bool is_zero = true;
330
331 if (ctx->std) {
332 match = &longest_match_std;
333 memset(ctx->hash, 0, sizeof(ctx->hash));
334 } else {
335 match = &longest_match_best;
336 }
337
338 /* Compression cycle. */
339 for (; unc_chunk < unc_end; unc_chunk += LZNT_CHUNK_SIZE) {
340 cmpr_size = 0;
341 err = compress_chunk(match, unc_chunk, unc_end, p, end,
342 &cmpr_size, ctx);
343 if (err < 0)
344 return unc_size;
345
346 if (is_zero && err != LZNT_ERROR_ALL_ZEROS)
347 is_zero = false;
348
349 p += cmpr_size;
350 }
351
352 if (p <= end - 2)
353 p[0] = p[1] = 0;
354
355 return is_zero ? 0 : PtrOffset(cmpr, p);
356 }
357
358 /*
359 * decompress_lznt - Decompress @cmpr into @unc.
360 */
decompress_lznt(const void * cmpr,size_t cmpr_size,void * unc,size_t unc_size)361 ssize_t decompress_lznt(const void *cmpr, size_t cmpr_size, void *unc,
362 size_t unc_size)
363 {
364 const u8 *cmpr_chunk = cmpr;
365 const u8 *cmpr_end = cmpr_chunk + cmpr_size;
366 u8 *unc_chunk = unc;
367 u8 *unc_end = unc_chunk + unc_size;
368 u16 chunk_hdr;
369
370 if (cmpr_size < sizeof(short))
371 return -EINVAL;
372
373 /* Read chunk header. */
374 chunk_hdr = cmpr_chunk[1];
375 chunk_hdr <<= 8;
376 chunk_hdr |= cmpr_chunk[0];
377
378 /* Loop through decompressing chunks. */
379 for (;;) {
380 size_t chunk_size_saved;
381 size_t unc_use;
382 size_t cmpr_use = 3 + (chunk_hdr & (LZNT_CHUNK_SIZE - 1));
383
384 /* Check that the chunk actually fits the supplied buffer. */
385 if (cmpr_chunk + cmpr_use > cmpr_end)
386 return -EINVAL;
387
388 /* First make sure the chunk contains compressed data. */
389 if (chunk_hdr & 0x8000) {
390 /* Decompress a chunk and return if we get an error. */
391 ssize_t err =
392 decompress_chunk(unc_chunk, unc_end,
393 cmpr_chunk + sizeof(chunk_hdr),
394 cmpr_chunk + cmpr_use);
395 if (err < 0)
396 return err;
397 unc_use = err;
398 } else {
399 /* This chunk does not contain compressed data. */
400 unc_use = unc_chunk + LZNT_CHUNK_SIZE > unc_end ?
401 unc_end - unc_chunk :
402 LZNT_CHUNK_SIZE;
403
404 if (cmpr_chunk + sizeof(chunk_hdr) + unc_use >
405 cmpr_end) {
406 return -EINVAL;
407 }
408
409 memcpy(unc_chunk, cmpr_chunk + sizeof(chunk_hdr),
410 unc_use);
411 }
412
413 /* Advance pointers. */
414 cmpr_chunk += cmpr_use;
415 unc_chunk += unc_use;
416
417 /* Check for the end of unc buffer. */
418 if (unc_chunk >= unc_end)
419 break;
420
421 /* Proceed the next chunk. */
422 if (cmpr_chunk > cmpr_end - 2)
423 break;
424
425 chunk_size_saved = LZNT_CHUNK_SIZE;
426
427 /* Read chunk header. */
428 chunk_hdr = cmpr_chunk[1];
429 chunk_hdr <<= 8;
430 chunk_hdr |= cmpr_chunk[0];
431
432 if (!chunk_hdr)
433 break;
434
435 /* Check the size of unc buffer. */
436 if (unc_use < chunk_size_saved) {
437 size_t t1 = chunk_size_saved - unc_use;
438 u8 *t2 = unc_chunk + t1;
439
440 /* 'Zero' memory. */
441 if (t2 >= unc_end)
442 break;
443
444 memset(unc_chunk, 0, t1);
445 unc_chunk = t2;
446 }
447 }
448
449 /* Check compression boundary. */
450 if (cmpr_chunk > cmpr_end)
451 return -EINVAL;
452
453 /*
454 * The unc size is just a difference between current
455 * pointer and original one.
456 */
457 return PtrOffset(unc, unc_chunk);
458 }
459