fs/ntfs3/lznt.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *
0004  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
0005  *
0006  */
0007
0008 #include <linux/kernel.h>
0009 #include <linux/slab.h>
0010 #include <linux/stddef.h>
0011 #include <linux/string.h>
0012 #include <linux/types.h>
0013
0014 #include "debug.h"
0015 #include "ntfs_fs.h"
0016
0017 // clang-format off
0018 /* Src buffer is zero. */
0019 #define LZNT_ERROR_ALL_ZEROS    1
0020 #define LZNT_CHUNK_SIZE     0x1000
0021 // clang-format on
0022
0023 struct lznt_hash {
0024     const u8 *p1;
0025     const u8 *p2;
0026 };
0027
0028 struct lznt {
0029     const u8 *unc;
0030     const u8 *unc_end;
0031     const u8 *best_match;
0032     size_t max_len;
0033     bool std;
0034
0035     struct lznt_hash hash[LZNT_CHUNK_SIZE];
0036 };
0037
0038 static inline size_t get_match_len(const u8 *ptr, const u8 *end, const u8 *prev,
0039                    size_t max_len)
0040 {
0041     size_t len = 0;
0042
0043     while (ptr + len < end && ptr[len] == prev[len] && ++len < max_len)
0044         ;
0045     return len;
0046 }
0047
0048 static size_t longest_match_std(const u8 *src, struct lznt *ctx)
0049 {
0050     size_t hash_index;
0051     size_t len1 = 0, len2 = 0;
0052     const u8 **hash;
0053
0054     hash_index =
0055         ((40543U * ((((src[0] << 4) ^ src[1]) << 4) ^ src[2])) >> 4) &
0056         (LZNT_CHUNK_SIZE - 1);
0057
0058     hash = &(ctx->hash[hash_index].p1);
0059
0060     if (hash[0] >= ctx->unc && hash[0] < src && hash[0][0] == src[0] &&
0061         hash[0][1] == src[1] && hash[0][2] == src[2]) {
0062         len1 = 3;
0063         if (ctx->max_len > 3)
0064             len1 += get_match_len(src + 3, ctx->unc_end,
0065                           hash[0] + 3, ctx->max_len - 3);
0066     }
0067
0068     if (hash[1] >= ctx->unc && hash[1] < src && hash[1][0] == src[0] &&
0069         hash[1][1] == src[1] && hash[1][2] == src[2]) {
0070         len2 = 3;
0071         if (ctx->max_len > 3)
0072             len2 += get_match_len(src + 3, ctx->unc_end,
0073                           hash[1] + 3, ctx->max_len - 3);
0074     }
0075
0076     /* Compare two matches and select the best one. */
0077     if (len1 < len2) {
0078         ctx->best_match = hash[1];
0079         len1 = len2;
0080     } else {
0081         ctx->best_match = hash[0];
0082     }
0083
0084     hash[1] = hash[0];
0085     hash[0] = src;
0086     return len1;
0087 }
0088
0089 static size_t longest_match_best(const u8 *src, struct lznt *ctx)
0090 {
0091     size_t max_len;
0092     const u8 *ptr;
0093
0094     if (ctx->unc >= src || !ctx->max_len)
0095         return 0;
0096
0097     max_len = 0;
0098     for (ptr = ctx->unc; ptr < src; ++ptr) {
0099         size_t len =
0100             get_match_len(src, ctx->unc_end, ptr, ctx->max_len);
0101         if (len >= max_len) {
0102             max_len = len;
0103             ctx->best_match = ptr;
0104         }
0105     }
0106
0107     return max_len >= 3 ? max_len : 0;
0108 }
0109
0110 static const size_t s_max_len[] = {
0111     0x1002, 0x802, 0x402, 0x202, 0x102, 0x82, 0x42, 0x22, 0x12,
0112 };
0113
0114 static const size_t s_max_off[] = {
0115     0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
0116 };
0117
0118 static inline u16 make_pair(size_t offset, size_t len, size_t index)
0119 {
0120     return ((offset - 1) << (12 - index)) |
0121            ((len - 3) & (((1 << (12 - index)) - 1)));
0122 }
0123
0124 static inline size_t parse_pair(u16 pair, size_t *offset, size_t index)
0125 {
0126     *offset = 1 + (pair >> (12 - index));
0127     return 3 + (pair & ((1 << (12 - index)) - 1));
0128 }
0129
0130 /*
0131  * compress_chunk
0132  *
0133  * Return:
0134  * * 0  - Ok, @cmpr contains @cmpr_chunk_size bytes of compressed data.
0135  * * 1  - Input buffer is full zero.
0136  * * -2 - The compressed buffer is too small to hold the compressed data.
0137  */
0138 static inline int compress_chunk(size_t (*match)(const u8 *, struct lznt *),
0139                  const u8 *unc, const u8 *unc_end, u8 *cmpr,
0140                  u8 *cmpr_end, size_t *cmpr_chunk_size,
0141                  struct lznt *ctx)
0142 {
0143     size_t cnt = 0;
0144     size_t idx = 0;
0145     const u8 *up = unc;
0146     u8 *cp = cmpr + 3;
0147     u8 *cp2 = cmpr + 2;
0148     u8 not_zero = 0;
0149     /* Control byte of 8-bit values: ( 0 - means byte as is, 1 - short pair ). */
0150     u8 ohdr = 0;
0151     u8 *last;
0152     u16 t16;
0153
0154     if (unc + LZNT_CHUNK_SIZE < unc_end)
0155         unc_end = unc + LZNT_CHUNK_SIZE;
0156
0157     last = min(cmpr + LZNT_CHUNK_SIZE + sizeof(short), cmpr_end);
0158
0159     ctx->unc = unc;
0160     ctx->unc_end = unc_end;
0161     ctx->max_len = s_max_len[0];
0162
0163     while (up < unc_end) {
0164         size_t max_len;
0165
0166         while (unc + s_max_off[idx] < up)
0167             ctx->max_len = s_max_len[++idx];
0168
0169         /* Find match. */
0170         max_len = up + 3 <= unc_end ? (*match)(up, ctx) : 0;
0171
0172         if (!max_len) {
0173             if (cp >= last)
0174                 goto NotCompressed;
0175             not_zero |= *cp++ = *up++;
0176         } else if (cp + 1 >= last) {
0177             goto NotCompressed;
0178         } else {
0179             t16 = make_pair(up - ctx->best_match, max_len, idx);
0180             *cp++ = t16;
0181             *cp++ = t16 >> 8;
0182
0183             ohdr |= 1 << cnt;
0184             up += max_len;
0185         }
0186
0187         cnt = (cnt + 1) & 7;
0188         if (!cnt) {
0189             *cp2 = ohdr;
0190             ohdr = 0;
0191             cp2 = cp;
0192             cp += 1;
0193         }
0194     }
0195
0196     if (cp2 < last)
0197         *cp2 = ohdr;
0198     else
0199         cp -= 1;
0200
0201     *cmpr_chunk_size = cp - cmpr;
0202
0203     t16 = (*cmpr_chunk_size - 3) | 0xB000;
0204     cmpr[0] = t16;
0205     cmpr[1] = t16 >> 8;
0206
0207     return not_zero ? 0 : LZNT_ERROR_ALL_ZEROS;
0208
0209 NotCompressed:
0210
0211     if ((cmpr + LZNT_CHUNK_SIZE + sizeof(short)) > last)
0212         return -2;
0213
0214     /*
0215      * Copy non cmpr data.
0216      * 0x3FFF == ((LZNT_CHUNK_SIZE + 2 - 3) | 0x3000)
0217      */
0218     cmpr[0] = 0xff;
0219     cmpr[1] = 0x3f;
0220
0221     memcpy(cmpr + sizeof(short), unc, LZNT_CHUNK_SIZE);
0222     *cmpr_chunk_size = LZNT_CHUNK_SIZE + sizeof(short);
0223
0224     return 0;
0225 }
0226
0227 static inline ssize_t decompress_chunk(u8 *unc, u8 *unc_end, const u8 *cmpr,
0228                        const u8 *cmpr_end)
0229 {
0230     u8 *up = unc;
0231     u8 ch = *cmpr++;
0232     size_t bit = 0;
0233     size_t index = 0;
0234     u16 pair;
0235     size_t offset, length;
0236
0237     /* Do decompression until pointers are inside range. */
0238     while (up < unc_end && cmpr < cmpr_end) {
0239         /* Correct index */
0240         while (unc + s_max_off[index] < up)
0241             index += 1;
0242
0243         /* Check the current flag for zero. */
0244         if (!(ch & (1 << bit))) {
0245             /* Just copy byte. */
0246             *up++ = *cmpr++;
0247             goto next;
0248         }
0249
0250         /* Check for boundary. */
0251         if (cmpr + 1 >= cmpr_end)
0252             return -EINVAL;
0253
0254         /* Read a short from little endian stream. */
0255         pair = cmpr[1];
0256         pair <<= 8;
0257         pair |= cmpr[0];
0258
0259         cmpr += 2;
0260
0261         /* Translate packed information into offset and length. */
0262         length = parse_pair(pair, &offset, index);
0263
0264         /* Check offset for boundary. */
0265         if (unc + offset > up)
0266             return -EINVAL;
0267
0268         /* Truncate the length if necessary. */
0269         if (up + length >= unc_end)
0270             length = unc_end - up;
0271
0272         /* Now we copy bytes. This is the heart of LZ algorithm. */
0273         for (; length > 0; length--, up++)
0274             *up = *(up - offset);
0275
0276 next:
0277         /* Advance flag bit value. */
0278         bit = (bit + 1) & 7;
0279
0280         if (!bit) {
0281             if (cmpr >= cmpr_end)
0282                 break;
0283
0284             ch = *cmpr++;
0285         }
0286     }
0287
0288     /* Return the size of uncompressed data. */
0289     return up - unc;
0290 }
0291
0292 /*
0293  * get_lznt_ctx
0294  * @level: 0 - Standard compression.
0295  *     !0 - Best compression, requires a lot of cpu.
0296  */
0297 struct lznt *get_lznt_ctx(int level)
0298 {
0299     struct lznt *r = kzalloc(level ? offsetof(struct lznt, hash)
0300                        : sizeof(struct lznt),
0301                  GFP_NOFS);
0302
0303     if (r)
0304         r->std = !level;
0305     return r;
0306 }
0307
0308 /*
0309  * compress_lznt - Compresses @unc into @cmpr
0310  *
0311  * Return:
0312  * * +x - Ok, @cmpr contains 'final_compressed_size' bytes of compressed data.
0313  * * 0 - Input buffer is full zero.
0314  */
0315 size_t compress_lznt(const void *unc, size_t unc_size, void *cmpr,
0316              size_t cmpr_size, struct lznt *ctx)
0317 {
0318     int err;
0319     size_t (*match)(const u8 *src, struct lznt *ctx);
0320     u8 *p = cmpr;
0321     u8 *end = p + cmpr_size;
0322     const u8 *unc_chunk = unc;
0323     const u8 *unc_end = unc_chunk + unc_size;
0324     bool is_zero = true;
0325
0326     if (ctx->std) {
0327         match = &longest_match_std;
0328         memset(ctx->hash, 0, sizeof(ctx->hash));
0329     } else {
0330         match = &longest_match_best;
0331     }
0332
0333     /* Compression cycle. */
0334     for (; unc_chunk < unc_end; unc_chunk += LZNT_CHUNK_SIZE) {
0335         cmpr_size = 0;
0336         err = compress_chunk(match, unc_chunk, unc_end, p, end,
0337                      &cmpr_size, ctx);
0338         if (err < 0)
0339             return unc_size;
0340
0341         if (is_zero && err != LZNT_ERROR_ALL_ZEROS)
0342             is_zero = false;
0343
0344         p += cmpr_size;
0345     }
0346
0347     if (p <= end - 2)
0348         p[0] = p[1] = 0;
0349
0350     return is_zero ? 0 : PtrOffset(cmpr, p);
0351 }
0352
0353 /*
0354  * decompress_lznt - Decompress @cmpr into @unc.
0355  */
0356 ssize_t decompress_lznt(const void *cmpr, size_t cmpr_size, void *unc,
0357             size_t unc_size)
0358 {
0359     const u8 *cmpr_chunk = cmpr;
0360     const u8 *cmpr_end = cmpr_chunk + cmpr_size;
0361     u8 *unc_chunk = unc;
0362     u8 *unc_end = unc_chunk + unc_size;
0363     u16 chunk_hdr;
0364
0365     if (cmpr_size < sizeof(short))
0366         return -EINVAL;
0367
0368     /* Read chunk header. */
0369     chunk_hdr = cmpr_chunk[1];
0370     chunk_hdr <<= 8;
0371     chunk_hdr |= cmpr_chunk[0];
0372
0373     /* Loop through decompressing chunks. */
0374     for (;;) {
0375         size_t chunk_size_saved;
0376         size_t unc_use;
0377         size_t cmpr_use = 3 + (chunk_hdr & (LZNT_CHUNK_SIZE - 1));
0378
0379         /* Check that the chunk actually fits the supplied buffer. */
0380         if (cmpr_chunk + cmpr_use > cmpr_end)
0381             return -EINVAL;
0382
0383         /* First make sure the chunk contains compressed data. */
0384         if (chunk_hdr & 0x8000) {
0385             /* Decompress a chunk and return if we get an error. */
0386             ssize_t err =
0387                 decompress_chunk(unc_chunk, unc_end,
0388                          cmpr_chunk + sizeof(chunk_hdr),
0389                          cmpr_chunk + cmpr_use);
0390             if (err < 0)
0391                 return err;
0392             unc_use = err;
0393         } else {
0394             /* This chunk does not contain compressed data. */
0395             unc_use = unc_chunk + LZNT_CHUNK_SIZE > unc_end
0396                       ? unc_end - unc_chunk
0397                       : LZNT_CHUNK_SIZE;
0398
0399             if (cmpr_chunk + sizeof(chunk_hdr) + unc_use >
0400                 cmpr_end) {
0401                 return -EINVAL;
0402             }
0403
0404             memcpy(unc_chunk, cmpr_chunk + sizeof(chunk_hdr),
0405                    unc_use);
0406         }
0407
0408         /* Advance pointers. */
0409         cmpr_chunk += cmpr_use;
0410         unc_chunk += unc_use;
0411
0412         /* Check for the end of unc buffer. */
0413         if (unc_chunk >= unc_end)
0414             break;
0415
0416         /* Proceed the next chunk. */
0417         if (cmpr_chunk > cmpr_end - 2)
0418             break;
0419
0420         chunk_size_saved = LZNT_CHUNK_SIZE;
0421
0422         /* Read chunk header. */
0423         chunk_hdr = cmpr_chunk[1];
0424         chunk_hdr <<= 8;
0425         chunk_hdr |= cmpr_chunk[0];
0426
0427         if (!chunk_hdr)
0428             break;
0429
0430         /* Check the size of unc buffer. */
0431         if (unc_use < chunk_size_saved) {
0432             size_t t1 = chunk_size_saved - unc_use;
0433             u8 *t2 = unc_chunk + t1;
0434
0435             /* 'Zero' memory. */
0436             if (t2 >= unc_end)
0437                 break;
0438
0439             memset(unc_chunk, 0, t1);
0440             unc_chunk = t2;
0441         }
0442     }
0443
0444     /* Check compression boundary. */
0445     if (cmpr_chunk > cmpr_end)
0446         return -EINVAL;
0447
0448     /*
0449      * The unc size is just a difference between current
0450      * pointer and original one.
0451      */
0452     return PtrOffset(unc, unc_chunk);
0453 }