]>
git.proxmox.com Git - mirror_ubuntu-kernels.git/blob - fs/ntfs3/lznt.c
1 // SPDX-License-Identifier: GPL-2.0
4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
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>
18 /* Src buffer is zero. */
19 #define LZNT_ERROR_ALL_ZEROS 1
20 #define LZNT_CHUNK_SIZE 0x1000
35 struct lznt_hash hash
[LZNT_CHUNK_SIZE
];
38 static inline size_t get_match_len(const u8
*ptr
, const u8
*end
, const u8
*prev
,
43 while (ptr
+ len
< end
&& ptr
[len
] == prev
[len
] && ++len
< max_len
)
48 static size_t longest_match_std(const u8
*src
, struct lznt
*ctx
)
51 size_t len1
= 0, len2
= 0;
55 ((40543U * ((((src
[0] << 4) ^ src
[1]) << 4) ^ src
[2])) >> 4) &
56 (LZNT_CHUNK_SIZE
- 1);
58 hash
= &(ctx
->hash
[hash_index
].p1
);
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]) {
64 len1
+= get_match_len(src
+ 3, ctx
->unc_end
,
65 hash
[0] + 3, ctx
->max_len
- 3);
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]) {
72 len2
+= get_match_len(src
+ 3, ctx
->unc_end
,
73 hash
[1] + 3, ctx
->max_len
- 3);
76 /* Compare two matches and select the best one. */
78 ctx
->best_match
= hash
[1];
81 ctx
->best_match
= hash
[0];
89 static size_t longest_match_best(const u8
*src
, struct lznt
*ctx
)
94 if (ctx
->unc
>= src
|| !ctx
->max_len
)
98 for (ptr
= ctx
->unc
; ptr
< src
; ++ptr
) {
100 get_match_len(src
, ctx
->unc_end
, ptr
, ctx
->max_len
);
101 if (len
>= max_len
) {
103 ctx
->best_match
= ptr
;
107 return max_len
>= 3 ? max_len
: 0;
110 static const size_t s_max_len
[] = {
111 0x1002, 0x802, 0x402, 0x202, 0x102, 0x82, 0x42, 0x22, 0x12,
114 static const size_t s_max_off
[] = {
115 0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
118 static inline u16
make_pair(size_t offset
, size_t len
, size_t index
)
120 return ((offset
- 1) << (12 - index
)) |
121 ((len
- 3) & (((1 << (12 - index
)) - 1)));
124 static inline size_t parse_pair(u16 pair
, size_t *offset
, size_t index
)
126 *offset
= 1 + (pair
>> (12 - index
));
127 return 3 + (pair
& ((1 << (12 - index
)) - 1));
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.
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
,
149 /* Control byte of 8-bit values: ( 0 - means byte as is, 1 - short pair ). */
154 if (unc
+ LZNT_CHUNK_SIZE
< unc_end
)
155 unc_end
= unc
+ LZNT_CHUNK_SIZE
;
157 last
= min(cmpr
+ LZNT_CHUNK_SIZE
+ sizeof(short), cmpr_end
);
160 ctx
->unc_end
= unc_end
;
161 ctx
->max_len
= s_max_len
[0];
163 while (up
< unc_end
) {
166 while (unc
+ s_max_off
[idx
] < up
)
167 ctx
->max_len
= s_max_len
[++idx
];
170 max_len
= up
+ 3 <= unc_end
? (*match
)(up
, ctx
) : 0;
175 not_zero
|= *cp
++ = *up
++;
176 } else if (cp
+ 1 >= last
) {
179 t16
= make_pair(up
- ctx
->best_match
, max_len
, idx
);
201 *cmpr_chunk_size
= cp
- cmpr
;
203 t16
= (*cmpr_chunk_size
- 3) | 0xB000;
207 return not_zero
? 0 : LZNT_ERROR_ALL_ZEROS
;
211 if ((cmpr
+ LZNT_CHUNK_SIZE
+ sizeof(short)) > last
)
215 * Copy non cmpr data.
216 * 0x3FFF == ((LZNT_CHUNK_SIZE + 2 - 3) | 0x3000)
221 memcpy(cmpr
+ sizeof(short), unc
, LZNT_CHUNK_SIZE
);
222 *cmpr_chunk_size
= LZNT_CHUNK_SIZE
+ sizeof(short);
227 static inline ssize_t
decompress_chunk(u8
*unc
, u8
*unc_end
, const u8
*cmpr
,
235 size_t offset
, length
;
237 /* Do decompression until pointers are inside range. */
238 while (up
< unc_end
&& cmpr
< cmpr_end
) {
240 while (unc
+ s_max_off
[index
] < up
)
243 /* Check the current flag for zero. */
244 if (!(ch
& (1 << bit
))) {
245 /* Just copy byte. */
250 /* Check for boundary. */
251 if (cmpr
+ 1 >= cmpr_end
)
254 /* Read a short from little endian stream. */
261 /* Translate packed information into offset and length. */
262 length
= parse_pair(pair
, &offset
, index
);
264 /* Check offset for boundary. */
265 if (unc
+ offset
> up
)
268 /* Truncate the length if necessary. */
269 if (up
+ length
>= unc_end
)
270 length
= unc_end
- up
;
272 /* Now we copy bytes. This is the heart of LZ algorithm. */
273 for (; length
> 0; length
--, up
++)
274 *up
= *(up
- offset
);
277 /* Advance flag bit value. */
281 if (cmpr
>= cmpr_end
)
288 /* Return the size of uncompressed data. */
294 * @level: 0 - Standard compression.
295 * !0 - Best compression, requires a lot of cpu.
297 struct lznt
*get_lznt_ctx(int level
)
299 struct lznt
*r
= kzalloc(level
? offsetof(struct lznt
, hash
)
300 : sizeof(struct lznt
),
309 * compress_lznt - Compresses @unc into @cmpr
312 * * +x - Ok, @cmpr contains 'final_compressed_size' bytes of compressed data.
313 * * 0 - Input buffer is full zero.
315 size_t compress_lznt(const void *unc
, size_t unc_size
, void *cmpr
,
316 size_t cmpr_size
, struct lznt
*ctx
)
319 size_t (*match
)(const u8
*src
, struct lznt
*ctx
);
321 u8
*end
= p
+ cmpr_size
;
322 const u8
*unc_chunk
= unc
;
323 const u8
*unc_end
= unc_chunk
+ unc_size
;
327 match
= &longest_match_std
;
328 memset(ctx
->hash
, 0, sizeof(ctx
->hash
));
330 match
= &longest_match_best
;
333 /* Compression cycle. */
334 for (; unc_chunk
< unc_end
; unc_chunk
+= LZNT_CHUNK_SIZE
) {
336 err
= compress_chunk(match
, unc_chunk
, unc_end
, p
, end
,
341 if (is_zero
&& err
!= LZNT_ERROR_ALL_ZEROS
)
350 return is_zero
? 0 : PtrOffset(cmpr
, p
);
354 * decompress_lznt - Decompress @cmpr into @unc.
356 ssize_t
decompress_lznt(const void *cmpr
, size_t cmpr_size
, void *unc
,
359 const u8
*cmpr_chunk
= cmpr
;
360 const u8
*cmpr_end
= cmpr_chunk
+ cmpr_size
;
362 u8
*unc_end
= unc_chunk
+ unc_size
;
365 if (cmpr_size
< sizeof(short))
368 /* Read chunk header. */
369 chunk_hdr
= cmpr_chunk
[1];
371 chunk_hdr
|= cmpr_chunk
[0];
373 /* Loop through decompressing chunks. */
375 size_t chunk_size_saved
;
377 size_t cmpr_use
= 3 + (chunk_hdr
& (LZNT_CHUNK_SIZE
- 1));
379 /* Check that the chunk actually fits the supplied buffer. */
380 if (cmpr_chunk
+ cmpr_use
> cmpr_end
)
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. */
387 decompress_chunk(unc_chunk
, unc_end
,
388 cmpr_chunk
+ sizeof(chunk_hdr
),
389 cmpr_chunk
+ cmpr_use
);
394 /* This chunk does not contain compressed data. */
395 unc_use
= unc_chunk
+ LZNT_CHUNK_SIZE
> unc_end
396 ? unc_end
- unc_chunk
399 if (cmpr_chunk
+ sizeof(chunk_hdr
) + unc_use
>
404 memcpy(unc_chunk
, cmpr_chunk
+ sizeof(chunk_hdr
),
408 /* Advance pointers. */
409 cmpr_chunk
+= cmpr_use
;
410 unc_chunk
+= unc_use
;
412 /* Check for the end of unc buffer. */
413 if (unc_chunk
>= unc_end
)
416 /* Proceed the next chunk. */
417 if (cmpr_chunk
> cmpr_end
- 2)
420 chunk_size_saved
= LZNT_CHUNK_SIZE
;
422 /* Read chunk header. */
423 chunk_hdr
= cmpr_chunk
[1];
425 chunk_hdr
|= cmpr_chunk
[0];
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
;
439 memset(unc_chunk
, 0, t1
);
444 /* Check compression boundary. */
445 if (cmpr_chunk
> cmpr_end
)
449 * The unc size is just a difference between current
450 * pointer and original one.
452 return PtrOffset(unc
, unc_chunk
);