fs/ntfs3/lznt.c

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