1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2024-2026, SUSE LLC 4 * Copyright (C) 2026 Namjae Jeon <linkinjeon@kernel.org> 5 * 6 * Authors: Enzo Matsumiya <ematsumiya@suse.de> 7 * Namjae Jeon <linkinjeon@kernel.org> 8 * 9 * Implementation of the LZ77 "plain" compression algorithm, as per MS-XCA spec. 10 */ 11 #include <linux/slab.h> 12 #include <linux/sizes.h> 13 #include <linux/count_zeros.h> 14 #include <linux/unaligned.h> 15 #include <linux/module.h> 16 #include <linux/overflow.h> 17 18 #include "lz77.h" 19 20 /* 21 * Compression parameters. 22 * 23 * LZ77_MATCH_MAX_DIST: Farthest back a match can be from current position (can be 1 - 8K). 24 * LZ77_HASH_LOG: 25 * LZ77_HASH_SIZE: ilog2 hash size (recommended to be 13 - 18, default 15 (hash size 26 * 32k)). 27 * LZ77_RSTEP_SIZE: Number of bytes to read from input buffer for hashing and initial 28 * match check (default 4 bytes, this effectivelly makes this the min 29 * match len). 30 * LZ77_MSTEP_SIZE: Number of bytes to extend-compare a found match (default 8 bytes). 31 * LZ77_SKIP_TRIGGER: ilog2 value for adaptive skipping, i.e. to progressively skip input 32 * bytes when we can't find matches. Default is 4. 33 * Higher values (>0) will decrease compression time, but will result 34 * in worse compression ratio. Lower values will give better 35 * compression ratio (more matches found), but will increase time. 36 */ 37 #define LZ77_MATCH_MAX_DIST SZ_8K 38 #define LZ77_HASH_LOG 15 39 #define LZ77_HASH_SIZE BIT(LZ77_HASH_LOG) 40 #define LZ77_RSTEP_SIZE sizeof(u32) 41 #define LZ77_MSTEP_SIZE sizeof(u64) 42 #define LZ77_SKIP_TRIGGER 4 43 44 #define LZ77_PREFETCH(ptr) __builtin_prefetch((ptr), 0, 3) 45 #define LZ77_FLAG_MAX 32 46 47 static __always_inline u8 lz77_read8(const u8 *ptr) 48 { 49 return get_unaligned(ptr); 50 } 51 52 static __always_inline u32 lz77_read32(const u32 *ptr) 53 { 54 return get_unaligned(ptr); 55 } 56 57 static __always_inline u64 lz77_read64(const u64 *ptr) 58 { 59 return get_unaligned(ptr); 60 } 61 62 static __always_inline void lz77_write8(u8 *ptr, u8 v) 63 { 64 put_unaligned(v, ptr); 65 } 66 67 static __always_inline void lz77_write16(u16 *ptr, u16 v) 68 { 69 put_unaligned_le16(v, ptr); 70 } 71 72 static __always_inline void lz77_write32(u32 *ptr, u32 v) 73 { 74 put_unaligned_le32(v, ptr); 75 } 76 77 static __always_inline u32 lz77_match_len(const void *match, const void *cur, const void *end) 78 { 79 const void *start = cur; 80 81 /* Safe for a do/while because otherwise we wouldn't reach here from the main loop. */ 82 do { 83 const u64 diff = lz77_read64(cur) ^ lz77_read64(match); 84 85 if (!diff) { 86 cur += LZ77_MSTEP_SIZE; 87 match += LZ77_MSTEP_SIZE; 88 89 continue; 90 } 91 92 /* This computes the number of common bytes in @diff. */ 93 cur += count_trailing_zeros(diff) >> 3; 94 95 return (cur - start); 96 } while (likely(cur + LZ77_MSTEP_SIZE <= end)); 97 98 /* Fallback to byte-by-byte comparison for last <8 bytes. */ 99 while (cur < end && lz77_read8(cur) == lz77_read8(match)) { 100 cur++; 101 match++; 102 } 103 104 return (cur - start); 105 } 106 107 /** 108 * lz77_encode_match() - Match encoding. 109 * @dst: compressed buffer 110 * @nib: pointer to an address in @dst 111 * @dist: match distance 112 * @len: match length 113 * 114 * Assumes all args were previously checked. 115 * 116 * Return: @dst advanced to new position 117 * 118 * Ref: MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing" 119 */ 120 static __always_inline void *lz77_encode_match(void *dst, void **nib, u16 dist, u32 len) 121 { 122 len -= 3; 123 dist--; 124 dist <<= 3; 125 126 if (len < 7) { 127 lz77_write16(dst, dist + len); 128 129 return dst + sizeof(u16); 130 } 131 132 dist |= 7; 133 lz77_write16(dst, dist); 134 dst += sizeof(u16); 135 len -= 7; 136 137 if (!*nib) { 138 lz77_write8(dst, umin(len, 15)); 139 *nib = dst; 140 dst++; 141 } else { 142 u8 *b = *nib; 143 144 lz77_write8(b, *b | umin(len, 15) << 4); 145 *nib = NULL; 146 } 147 148 if (len < 15) 149 return dst; 150 151 len -= 15; 152 if (len < 255) { 153 lz77_write8(dst, len); 154 155 return dst + 1; 156 } 157 158 lz77_write8(dst, 0xff); 159 dst++; 160 len += 7 + 15; 161 if (len <= 0xffff) { 162 lz77_write16(dst, len); 163 164 return dst + sizeof(u16); 165 } 166 167 lz77_write16(dst, 0); 168 dst += sizeof(u16); 169 lz77_write32(dst, len); 170 171 return dst + sizeof(u32); 172 } 173 174 /** 175 * lz77_encode_literals() - Literals encoding. 176 * @start: where to start copying literals (uncompressed buffer) 177 * @end: when to stop copying (uncompressed buffer) 178 * @dst: compressed buffer 179 * @f: pointer to current flag value 180 * @fc: pointer to current flag count 181 * @fp: pointer to current flag address 182 * 183 * Batch copy literals from @start to @dst, updating flag values accordingly. 184 * Assumes all args were previously checked. 185 * 186 * Return: @dst advanced to new position 187 * 188 * MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing" 189 */ 190 static __always_inline void *lz77_encode_literals(const void *start, const void *end, void *dst, 191 long *f, u32 *fc, void **fp) 192 { 193 if (start >= end) 194 return dst; 195 196 do { 197 const u32 len = umin(end - start, LZ77_FLAG_MAX - *fc); 198 199 memcpy(dst, start, len); 200 201 dst += len; 202 start += len; 203 204 *f <<= len; 205 *fc += len; 206 if (*fc == LZ77_FLAG_MAX) { 207 lz77_write32(*fp, *f); 208 *fc = 0; 209 *fp = dst; 210 dst += sizeof(u32); 211 } 212 } while (start < end); 213 214 return dst; 215 } 216 217 static __always_inline u32 lz77_hash(const u32 v) 218 { 219 return ((v ^ 0x9E3779B9) * 0x85EBCA6B) >> (32 - LZ77_HASH_LOG); 220 } 221 222 noinline int smb_lz77_compress(const void *src, const u32 slen, 223 void *dst, u32 *dlen) 224 { 225 const void *srcp, *rlim, *end, *anchor; 226 u32 *htable, hash, flag_count = 0; 227 void *dstp, *nib, *flag_pos; 228 long flag = 0; 229 230 /* This is probably a bug, so throw a warning. */ 231 if (WARN_ON_ONCE(*dlen < smb_lz77_compressed_alloc_size(slen))) 232 return -EINVAL; 233 234 srcp = src; 235 anchor = src; 236 end = srcp + slen; /* absolute end */ 237 rlim = end - LZ77_MSTEP_SIZE; /* read limit (for lz77_match_len()) */ 238 dstp = dst; 239 flag_pos = dstp; 240 dstp += sizeof(u32); 241 nib = NULL; 242 243 htable = kvcalloc(LZ77_HASH_SIZE, sizeof(*htable), GFP_KERNEL); 244 if (!htable) 245 return -ENOMEM; 246 247 LZ77_PREFETCH(srcp + LZ77_RSTEP_SIZE); 248 249 /* 250 * Adjust @srcp so we don't get a false positive match on first iteration. 251 * Then prepare hash for first loop iteration (don't advance @srcp again). 252 */ 253 hash = lz77_hash(lz77_read32(srcp++)); 254 htable[hash] = 0; 255 hash = lz77_hash(lz77_read32(srcp)); 256 257 /* 258 * Main loop. 259 * 260 * @dlen is >= smb_lz77_compressed_alloc_size(), so run without 261 * bound-checking @dstp. 262 * 263 * This code was crafted in a way to best utilise fetch-decode-execute CPU flow. 264 * Any attempt to optimize it, or even organize it, can lead to huge performance loss. 265 */ 266 do { 267 const void *match, *next = srcp; 268 u32 len, step = 1, skip = 1U << LZ77_SKIP_TRIGGER; 269 270 /* Match finding (hot path -- don't change the read/check/write order). */ 271 do { 272 const u32 cur_hash = hash; 273 274 srcp = next; 275 next += step; 276 277 /* 278 * Adaptive skipping. 279 * 280 * Increment @step every (1 << LZ77_SKIP_TRIGGER, 16 in our case) bytes 281 * without a match. 282 * Reset to 1 when a match is found. 283 */ 284 step = (skip++ >> LZ77_SKIP_TRIGGER); 285 if (unlikely(next > rlim)) 286 goto out; 287 288 hash = lz77_hash(lz77_read32(next)); 289 match = src + htable[cur_hash]; 290 htable[cur_hash] = srcp - src; 291 } while (likely(match + LZ77_MATCH_MAX_DIST < srcp) || 292 lz77_read32(match) != lz77_read32(srcp)); 293 294 /* 295 * Match found. Warm/cold path; begin parsing @srcp and writing to @dstp: 296 * - flush literals 297 * - compute match length (*) 298 * - encode match 299 * 300 * (*) Current minimum match length is defined by the memory read size above, so 301 * here we already know that we have 4 matching bytes, but it's just faster to 302 * redundantly compute it again in lz77_match_len() than to adjust pointers/len. 303 */ 304 dstp = lz77_encode_literals(anchor, srcp, dstp, &flag, &flag_count, &flag_pos); 305 len = lz77_match_len(match, srcp, end); 306 dstp = lz77_encode_match(dstp, &nib, srcp - match, len); 307 srcp += len; 308 anchor = srcp; 309 310 LZ77_PREFETCH(srcp); 311 312 flag = (flag << 1) | 1; 313 flag_count++; 314 if (flag_count == LZ77_FLAG_MAX) { 315 lz77_write32(flag_pos, flag); 316 flag_count = 0; 317 flag_pos = dstp; 318 dstp += sizeof(u32); 319 } 320 321 if (unlikely(srcp > rlim)) 322 break; 323 324 /* Prepare for next loop. */ 325 hash = lz77_hash(lz77_read32(srcp)); 326 } while (srcp < end); 327 out: 328 dstp = lz77_encode_literals(anchor, end, dstp, &flag, &flag_count, &flag_pos); 329 330 flag_count = LZ77_FLAG_MAX - flag_count; 331 flag <<= flag_count; 332 flag |= (1UL << flag_count) - 1; 333 lz77_write32(flag_pos, flag); 334 335 *dlen = dstp - dst; 336 kvfree(htable); 337 338 if (*dlen < slen) 339 return 0; 340 341 return -EMSGSIZE; 342 } 343 EXPORT_SYMBOL_GPL(smb_lz77_compress); 344 345 static int lz77_decode_match_len(const u8 **src, const u8 *end, u16 token, 346 u8 *nibble, bool *have_nibble, u32 *len) 347 { 348 u8 extra; 349 350 *len = (token & 0x7) + 3; 351 if ((token & 0x7) != 0x7) 352 return 0; 353 354 if (!*have_nibble) { 355 if (*src >= end) 356 return -EINVAL; 357 *nibble = *(*src)++; 358 extra = *nibble & 0xf; 359 *have_nibble = true; 360 } else { 361 extra = *nibble >> 4; 362 *have_nibble = false; 363 } 364 365 *len += extra; 366 if (extra == 0xf) { 367 u8 b; 368 369 if (*src >= end) 370 return -EINVAL; 371 b = *(*src)++; 372 if (b != 0xff) { 373 *len += b; 374 } else { 375 u16 w; 376 377 if (end - *src < 2) 378 return -EINVAL; 379 w = get_unaligned_le16(*src); 380 *src += 2; 381 if (w) { 382 *len = w + 3; 383 } else { 384 u32 long_len; 385 386 if (end - *src < 4) 387 return -EINVAL; 388 long_len = get_unaligned_le32(*src); 389 *src += 4; 390 if (check_add_overflow(long_len, 3, len)) 391 return -EINVAL; 392 } 393 } 394 } 395 396 return 0; 397 } 398 399 int smb_lz77_decompress(const void *src, const u32 slen, void *dst, 400 const u32 dlen) 401 { 402 const u8 *sp = src, *send = sp + slen; 403 u8 *dp = dst, *dend = dp + dlen; 404 u32 flags = 0; 405 int flag_count = 0; 406 u8 nibble = 0; 407 bool have_nibble = false; 408 409 while (dp < dend) { 410 u32 len, dist; 411 u16 token; 412 413 if (!flag_count) { 414 if (send - sp < 4) 415 return -EINVAL; 416 flags = get_unaligned_le32(sp); 417 sp += 4; 418 flag_count = 32; 419 } 420 421 if (!(flags & 0x80000000)) { 422 if (sp >= send) 423 return -EINVAL; 424 *dp++ = *sp++; 425 flags <<= 1; 426 flag_count--; 427 continue; 428 } 429 430 flags <<= 1; 431 flag_count--; 432 433 if (send - sp < 2) 434 return -EINVAL; 435 436 token = get_unaligned_le16(sp); 437 sp += 2; 438 439 dist = (token >> 3) + 1; 440 if (dist > dp - (u8 *)dst) 441 return -EINVAL; 442 443 if (lz77_decode_match_len(&sp, send, token, &nibble, 444 &have_nibble, &len)) 445 return -EINVAL; 446 447 if (len > dend - dp) 448 return -EINVAL; 449 450 while (len--) { 451 *dp = *(dp - dist); 452 dp++; 453 } 454 } 455 456 return 0; 457 } 458 EXPORT_SYMBOL_GPL(smb_lz77_decompress); 459 460 MODULE_LICENSE("GPL"); 461 MODULE_DESCRIPTION("SMB plain LZ77 compression"); 462