1 /* SPDX-License-Identifier: MIT */ 2 /* 3 * decompress_common.h - Code shared by the XPRESS and LZX decompressors 4 * 5 * This is a port of the upstream wimlib "decompress_common.h" which uses a 6 * subtable-based Huffman decode table format, as opposed to the older 7 * binary-tree-based format previously used in this library. 8 * 9 * Copyright (C) 2022 Eric Biggers 10 */ 11 12 #ifndef _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H 13 #define _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H 14 15 #include <linux/compiler.h> 16 #include <linux/string.h> 17 #include <linux/types.h> 18 #include <linux/slab.h> 19 #include <linux/unaligned.h> 20 21 /* "Force inline" macro (not required, but helpful for performance). */ 22 #define forceinline __always_inline 23 24 /* Size of a machine word. */ 25 #define WORDBYTES sizeof(size_t) 26 #define WORDBITS (8 * WORDBYTES) 27 28 /* UNALIGNED_ACCESS_IS_FAST should be 1 if unaligned memory accesses can be 29 * performed efficiently on the target platform. 30 */ 31 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS 32 # define UNALIGNED_ACCESS_IS_FAST 1 33 #else 34 # define UNALIGNED_ACCESS_IS_FAST 0 35 #endif 36 37 /* Deprecated name kept for compatibility with the upstream source. */ 38 #define FAST_UNALIGNED_ACCESS UNALIGNED_ACCESS_IS_FAST 39 40 /* likely()/unlikely() are provided by <linux/compiler.h>. */ 41 42 /* STATIC_ASSERT() - verify the truth of an expression at compile time. */ 43 #define STATIC_ASSERT(expr) ((void)sizeof(char[1 - 2 * !(expr)])) 44 45 /* STATIC_ASSERT_ZERO() - like STATIC_ASSERT() but evaluates to 0 so it can be 46 * used in constant expressions. 47 */ 48 #define STATIC_ASSERT_ZERO(expr) ((int)sizeof(char[-!(expr)])) 49 50 /* Unaligned word load/store helpers. */ 51 static forceinline size_t load_word_unaligned(const void *p) 52 { 53 size_t v; 54 55 memcpy(&v, p, sizeof(v)); 56 return v; 57 } 58 59 static forceinline void store_word_unaligned(size_t v, void *p) 60 { 61 memcpy(p, &v, sizeof(v)); 62 } 63 64 static forceinline void copy_word_unaligned(const void *src, void *dst) 65 { 66 store_word_unaligned(load_word_unaligned(src), dst); 67 } 68 69 static forceinline size_t repeat_u16(u16 b) 70 { 71 size_t v = b; 72 73 STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64); 74 v |= v << 16; 75 v |= v << ((WORDBITS == 64) ? 32 : 0); 76 return v; 77 } 78 79 static forceinline size_t repeat_byte(u8 b) 80 { 81 return repeat_u16(((u16)b << 8) | b); 82 } 83 84 /******************************************************************************/ 85 /* Input bitstream for XPRESS and LZX */ 86 /*----------------------------------------------------------------------------*/ 87 88 /* Structure that encapsulates a block of in-memory data being interpreted as a 89 * stream of bits, optionally with interwoven literal bytes. Bits are assumed 90 * to be stored in little endian 16-bit coding units, with the bits ordered high 91 * to low. 92 */ 93 struct input_bitstream { 94 /* Bits that have been read from the input buffer. The bits are 95 * left-justified; the next bit is always bit 31. 96 */ 97 u32 bitbuf; 98 99 /* Number of bits currently held in @bitbuf. */ 100 u32 bitsleft; 101 102 /* Pointer to the next byte to be retrieved from the input buffer. */ 103 const u8 *next; 104 105 /* Pointer past the end of the input buffer. */ 106 const u8 *end; 107 }; 108 109 /* Initialize a bitstream to read from the specified input buffer. */ 110 static forceinline void init_input_bitstream(struct input_bitstream *is, 111 const void *buffer, u32 size) 112 { 113 is->bitbuf = 0; 114 is->bitsleft = 0; 115 is->next = buffer; 116 is->end = is->next + size; 117 } 118 119 /* Note: for performance reasons, the following methods don't return error 120 * codes to the caller if the input buffer is overrun. Instead, they just 121 * assume that all overrun data is zeroes. 122 */ 123 124 /* Ensure the bit buffer variable for the bitstream contains at least @num_bits 125 * bits. Following this, bitstream_peek_bits() and/or bitstream_remove_bits() 126 * may be called on the bitstream to peek or remove up to @num_bits bits. This 127 * works for at most 16 bits, which is sufficient for LZX (max codeword length 128 * 16) and XPRESS (max codeword length 15). 129 */ 130 static forceinline void bitstream_ensure_bits(struct input_bitstream *is, 131 unsigned int num_bits) 132 { 133 if (is->bitsleft >= num_bits) 134 return; 135 136 if (unlikely(is->end - is->next < 2)) 137 goto overflow; 138 139 is->bitbuf |= (u32)get_unaligned_le16(is->next) << (16 - is->bitsleft); 140 is->next += 2; 141 is->bitsleft += 16; 142 return; 143 144 overflow: 145 is->bitsleft = 32; 146 } 147 148 /* Return the next @num_bits bits from the bitstream, without removing them. 149 * There must be at least @num_bits remaining in the buffer variable. 150 */ 151 static forceinline u32 bitstream_peek_bits(const struct input_bitstream *is, 152 unsigned int num_bits) 153 { 154 return (is->bitbuf >> 1) >> (sizeof(is->bitbuf) * 8 - num_bits - 1); 155 } 156 157 /* Remove @num_bits from the bitstream. */ 158 static forceinline void bitstream_remove_bits(struct input_bitstream *is, 159 unsigned int num_bits) 160 { 161 is->bitbuf <<= num_bits; 162 is->bitsleft -= num_bits; 163 } 164 165 /* Remove and return @num_bits bits from the bitstream. */ 166 static forceinline u32 bitstream_pop_bits(struct input_bitstream *is, 167 unsigned int num_bits) 168 { 169 u32 bits = bitstream_peek_bits(is, num_bits); 170 171 bitstream_remove_bits(is, num_bits); 172 return bits; 173 } 174 175 /* Read and return the next @num_bits bits from the bitstream. */ 176 static forceinline u32 bitstream_read_bits(struct input_bitstream *is, 177 unsigned int num_bits) 178 { 179 bitstream_ensure_bits(is, num_bits); 180 return bitstream_pop_bits(is, num_bits); 181 } 182 183 /* Read and return the next literal byte embedded in the bitstream. */ 184 static forceinline u8 bitstream_read_byte(struct input_bitstream *is) 185 { 186 if (unlikely(is->end == is->next)) 187 return 0; 188 return *is->next++; 189 } 190 191 /* Read and return the next 16-bit integer embedded in the bitstream. */ 192 static forceinline u16 bitstream_read_u16(struct input_bitstream *is) 193 { 194 u16 v; 195 196 if (unlikely(is->end - is->next < 2)) 197 return 0; 198 v = get_unaligned_le16(is->next); 199 is->next += 2; 200 return v; 201 } 202 203 /* Read and return the next 32-bit integer embedded in the bitstream. */ 204 static forceinline u32 bitstream_read_u32(struct input_bitstream *is) 205 { 206 u32 v; 207 208 if (unlikely(is->end - is->next < 4)) 209 return 0; 210 v = get_unaligned_le32(is->next); 211 is->next += 4; 212 return v; 213 } 214 215 /* Read into @dst_buffer an array of literal bytes embedded in the bitstream. 216 * Return 0 if there were enough bytes remaining in the input, otherwise -1. 217 */ 218 static forceinline int bitstream_read_bytes(struct input_bitstream *is, 219 void *dst_buffer, size_t count) 220 { 221 if (unlikely((size_t)(is->end - is->next) < count)) 222 return -1; 223 memcpy(dst_buffer, is->next, count); 224 is->next += count; 225 return 0; 226 } 227 228 /* Align the input bitstream on a coding-unit boundary. */ 229 static forceinline void bitstream_align(struct input_bitstream *is) 230 { 231 is->bitsleft = 0; 232 is->bitbuf = 0; 233 } 234 235 /******************************************************************************/ 236 /* Huffman decoding */ 237 /*----------------------------------------------------------------------------*/ 238 239 /* 240 * Required alignment for the Huffman decode tables. We require this alignment 241 * so that we can fill the entries with word instructions without having to deal 242 * with misaligned buffers. 243 */ 244 #define DECODE_TABLE_ALIGNMENT 16 245 246 /* 247 * Each decode table entry is 16 bits divided into two fields: 'symbol' (high 12 248 * bits) and 'length' (low 4 bits). See the comments in decompress_common.c for 249 * the precise meaning of these fields depending on the entry type. 250 */ 251 #define DECODE_TABLE_SYMBOL_SHIFT 4 252 #define DECODE_TABLE_MAX_SYMBOL ((1 << (16 - DECODE_TABLE_SYMBOL_SHIFT)) - 1) 253 #define DECODE_TABLE_MAX_LENGTH ((1 << DECODE_TABLE_SYMBOL_SHIFT) - 1) 254 #define DECODE_TABLE_LENGTH_MASK DECODE_TABLE_MAX_LENGTH 255 #define MAKE_DECODE_TABLE_ENTRY(symbol, length) \ 256 (((symbol) << DECODE_TABLE_SYMBOL_SHIFT) | (length)) 257 258 /* 259 * Read and return the next Huffman-encoded symbol from the given bitstream 260 * using the given decode table. If the input data is exhausted, then the 261 * Huffman symbol will be decoded as if the missing bits were all zeroes. 262 */ 263 static forceinline unsigned int read_huffsym(struct input_bitstream *is, 264 const u16 decode_table[], 265 unsigned int table_bits, 266 unsigned int max_codeword_len) 267 { 268 unsigned int entry; 269 unsigned int symbol; 270 unsigned int length; 271 272 /* Preload the bitbuffer with 'max_codeword_len' bits. */ 273 bitstream_ensure_bits(is, max_codeword_len); 274 275 /* Index the root table by the next 'table_bits' bits of input. */ 276 entry = decode_table[bitstream_peek_bits(is, table_bits)]; 277 278 /* Extract the "symbol" and "length" from the entry. */ 279 symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT; 280 length = entry & DECODE_TABLE_LENGTH_MASK; 281 282 /* If the codeword is longer than 'table_bits', the root entry is a 283 * subtable pointer. Discard the bits used to index the root table and 284 * index the subtable by the next 'length' bits. 285 */ 286 if (max_codeword_len > table_bits && 287 entry >= (1U << (table_bits + DECODE_TABLE_SYMBOL_SHIFT))) { 288 bitstream_remove_bits(is, table_bits); 289 entry = decode_table[symbol + bitstream_peek_bits(is, length)]; 290 symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT; 291 length = entry & DECODE_TABLE_LENGTH_MASK; 292 } 293 294 /* Discard the (remaining) bits of the codeword. */ 295 bitstream_remove_bits(is, length); 296 297 return symbol; 298 } 299 300 /* 301 * DECODE_TABLE_ENOUGH() evaluates to the maximum number of decode table 302 * entries, including all subtable entries, that may be required for decoding a 303 * given Huffman code. It is a compile-time mapping computed by the zlib 304 * 'enough' utility. An unknown combination produces a build error. 305 */ 306 #define DECODE_TABLE_ENOUGH(num_syms, table_bits, max_codeword_len) ( \ 307 ((num_syms) == 8 && (table_bits) == 5 && (max_codeword_len) == 7) ? 36 : \ 308 ((num_syms) == 8 && (table_bits) == 6 && (max_codeword_len) == 7) ? 66 : \ 309 ((num_syms) == 8 && (table_bits) == 7 && (max_codeword_len) == 7) ? 128 : \ 310 ((num_syms) == 20 && (table_bits) == 5 && (max_codeword_len) == 15) ? 1062 : \ 311 ((num_syms) == 20 && (table_bits) == 6 && (max_codeword_len) == 15) ? 582 : \ 312 ((num_syms) == 20 && (table_bits) == 7 && (max_codeword_len) == 15) ? 390 : \ 313 ((num_syms) == 54 && (table_bits) == 9 && (max_codeword_len) == 15) ? 618 : \ 314 ((num_syms) == 54 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1098 : \ 315 ((num_syms) == 249 && (table_bits) == 9 && (max_codeword_len) == 16) ? 878 : \ 316 ((num_syms) == 249 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1326 : \ 317 ((num_syms) == 249 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2318 : \ 318 ((num_syms) == 496 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2566 : \ 319 ((num_syms) == 256 && (table_bits) == 9 && (max_codeword_len) == 15) ? 822 : \ 320 ((num_syms) == 256 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1302 : \ 321 ((num_syms) == 256 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2310 : \ 322 ((num_syms) == 512 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1558 : \ 323 ((num_syms) == 512 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2566 : \ 324 ((num_syms) == 512 && (table_bits) == 12 && (max_codeword_len) == 15) ? 4606 : \ 325 ((num_syms) == 656 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1734 : \ 326 ((num_syms) == 656 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2726 : \ 327 ((num_syms) == 656 && (table_bits) == 12 && (max_codeword_len) == 16) ? 4758 : \ 328 ((num_syms) == 799 && (table_bits) == 9 && (max_codeword_len) == 15) ? 1366 : \ 329 ((num_syms) == 799 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1846 : \ 330 ((num_syms) == 799 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2854 : \ 331 -1) 332 333 /* Wrapper around DECODE_TABLE_ENOUGH() that does additional compile-time 334 * validation. 335 */ 336 #define DECODE_TABLE_SIZE(num_syms, table_bits, max_codeword_len) ( \ 337 STATIC_ASSERT_ZERO((num_syms) > 0) + \ 338 STATIC_ASSERT_ZERO((table_bits) > 0) + \ 339 STATIC_ASSERT_ZERO((max_codeword_len) > 0) + \ 340 STATIC_ASSERT_ZERO((num_syms) <= 1U << (max_codeword_len)) + \ 341 STATIC_ASSERT_ZERO((table_bits) <= (max_codeword_len)) + \ 342 STATIC_ASSERT_ZERO((num_syms) - 1 <= DECODE_TABLE_MAX_SYMBOL) + \ 343 STATIC_ASSERT_ZERO((table_bits) <= DECODE_TABLE_MAX_LENGTH) + \ 344 STATIC_ASSERT_ZERO((max_codeword_len) - (table_bits) <= \ 345 DECODE_TABLE_MAX_LENGTH) + \ 346 STATIC_ASSERT_ZERO((1U << table_bits) > (num_syms) - 1) + \ 347 STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH( \ 348 (num_syms), (table_bits), \ 349 (max_codeword_len)) > 0) + \ 350 STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH( \ 351 (num_syms), (table_bits), \ 352 (max_codeword_len)) - 1 <= \ 353 DECODE_TABLE_MAX_SYMBOL) + \ 354 DECODE_TABLE_ENOUGH((num_syms), (table_bits), \ 355 (max_codeword_len)) \ 356 ) 357 358 /* Declare the decode table for a Huffman code. */ 359 #define DECODE_TABLE(name, num_syms, table_bits, max_codeword_len) \ 360 u16 name[DECODE_TABLE_SIZE((num_syms), (table_bits), \ 361 (max_codeword_len))] \ 362 __aligned(DECODE_TABLE_ALIGNMENT) 363 364 /* Declare the temporary "working_space" array needed for building the decode 365 * table for a Huffman code. 366 */ 367 #define DECODE_TABLE_WORKING_SPACE(name, num_syms, max_codeword_len) \ 368 u16 name[2 * ((max_codeword_len) + 1) + (num_syms)] 369 370 int make_huffman_decode_table(u16 decode_table[], u32 num_syms, 371 u32 table_bits, const u8 lens[], 372 u32 max_codeword_len, u16 working_space[], 373 u32 decode_table_size); 374 375 /******************************************************************************/ 376 /* LZ match copying */ 377 /*----------------------------------------------------------------------------*/ 378 379 /* 380 * Copy an LZ77 match of 'length' bytes from the match source at 'out_next - 381 * offset' to the match destination at 'out_next'. The source and destination 382 * may overlap. This handles validating the length and offset; it returns 0 if 383 * the match was valid (and was copied), otherwise -1. 384 */ 385 static forceinline int lz_copy(u32 length, u32 offset, u8 *out_begin, 386 u8 *out_next, u8 *out_end, u32 min_length) 387 { 388 const u8 *src; 389 u8 *end; 390 391 /* Validate the offset. */ 392 if (unlikely(offset > (u32)(out_next - out_begin))) 393 return -1; 394 395 src = out_next - offset; 396 397 /* Fast path: copy a short, non-overlapping match whose end is not too 398 * close to the end of the buffer. 399 */ 400 if (UNALIGNED_ACCESS_IS_FAST && length <= 3 * WORDBYTES && 401 offset >= WORDBYTES && out_end - out_next >= 3 * WORDBYTES) { 402 copy_word_unaligned(src + WORDBYTES * 0, out_next + WORDBYTES * 0); 403 copy_word_unaligned(src + WORDBYTES * 1, out_next + WORDBYTES * 1); 404 copy_word_unaligned(src + WORDBYTES * 2, out_next + WORDBYTES * 2); 405 return 0; 406 } 407 408 /* Validate the length. */ 409 if (unlikely(length > (u32)(out_end - out_next))) 410 return -1; 411 end = out_next + length; 412 413 if (UNALIGNED_ACCESS_IS_FAST && likely(out_end - end >= WORDBYTES - 1)) { 414 if (offset >= WORDBYTES) { 415 do { 416 copy_word_unaligned(src, out_next); 417 src += WORDBYTES; 418 out_next += WORDBYTES; 419 } while (out_next < end); 420 return 0; 421 } else if (offset == 1) { 422 size_t v = repeat_byte(*(out_next - 1)); 423 424 do { 425 store_word_unaligned(v, out_next); 426 src += WORDBYTES; 427 out_next += WORDBYTES; 428 } while (out_next < end); 429 return 0; 430 } 431 } 432 433 /* Fall back to a bytewise copy. */ 434 if (min_length >= 2) 435 *out_next++ = *src++; 436 if (min_length >= 3) 437 *out_next++ = *src++; 438 do { 439 *out_next++ = *src++; 440 } while (out_next != end); 441 return 0; 442 } 443 444 #endif /* _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H */ 445