X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms-decompress.c;h=00e97d27e5c86de942c838c4a802bf72de61c3f0;hb=6c7b1783191ffe324953aad63735843feda9f901;hp=40d35bf6e2610e945a1034f19dc303e40ffa7d2b;hpb=883833a4b3dabec325edf1ca938000f91d587c00;p=wimlib diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 40d35bf6..00e97d27 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -1,7 +1,5 @@ /* * lzms-decompress.c - * - * A decompressor for the LZMS compression format. */ /* @@ -201,7 +199,6 @@ #include "wimlib/util.h" #include -#include #define LZMS_DECODE_TABLE_BITS 10 @@ -248,22 +245,6 @@ struct lzms_input_bitstream { size_t num_le16_remaining; }; -/* Probability entry for use by the range decoder when in a specific state. */ -struct lzms_probability_entry { - - /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that - * have been decoded using this probability entry. This is a cached - * value because it can be computed as LZMS_PROBABILITY_MAX minus the - * Hamming weight of the low-order LZMS_PROBABILITY_MAX bits of - * @recent_bits. */ - u32 num_recent_zero_bits; - - /* The most recent LZMS_PROBABILITY_MAX bits that have been decoded - * using this probability entry. The size of this variable, in bits, - * must be at least LZMS_PROBABILITY_MAX. */ - u64 recent_bits; -}; - /* Structure used for range decoding. This wraps around `struct * lzms_range_decoder_raw' to use and maintain probability entries. */ struct lzms_range_decoder { @@ -383,97 +364,10 @@ struct lzms_decompressor { u32 upcoming_delta_power; u32 upcoming_delta_offset; - /* Used for postprocessing */ + /* Used for postprocessing. */ s32 last_target_usages[65536]; }; -/* A table that maps position slots to their base values. These are constants - * computed at runtime by lzms_compute_slot_bases(). */ -static u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1]; - -/* A table that maps length slots to their base values. These are constants - * computed at runtime by lzms_compute_slot_bases(). */ -static u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1]; - -static void -lzms_decode_delta_rle_slot_bases(u32 slot_bases[], - const u8 delta_run_lens[], size_t num_run_lens) -{ - u32 delta = 1; - u32 base = 0; - size_t slot = 0; - for (size_t i = 0; i < num_run_lens; i++) { - u8 run_len = delta_run_lens[i]; - while (run_len--) { - base += delta; - slot_bases[slot++] = base; - } - delta <<= 1; - } -} - -/* Initialize the global position and length slot tables. */ -static void -lzms_compute_slot_bases(void) -{ - /* If an explicit formula that maps LZMS position and length slots to - * slot bases exists, then it could be used here. But until one is - * found, the following code fills in the slots using the observation - * that the increase from one slot base to the next is an increasing - * power of 2. Therefore, run-length encoding of the delta of adjacent - * entries can be used. */ - static const u8 position_slot_delta_run_lens[] = { - 9, 0, 9, 7, 10, 15, 15, 20, - 20, 30, 33, 40, 42, 45, 60, 73, - 80, 85, 95, 105, 6, - }; - - static const u8 length_slot_delta_run_lens[] = { - 27, 4, 6, 4, 5, 2, 1, 1, - 1, 1, 1, 0, 0, 0, 0, 0, - 1, - }; - - lzms_decode_delta_rle_slot_bases(lzms_position_slot_base, - position_slot_delta_run_lens, - ARRAY_LEN(position_slot_delta_run_lens)); - - lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS] = 0x7fffffff; - - lzms_decode_delta_rle_slot_bases(lzms_length_slot_base, - length_slot_delta_run_lens, - ARRAY_LEN(length_slot_delta_run_lens)); - - lzms_length_slot_base[LZMS_NUM_LEN_SYMS] = 0x400108ab; -} - -/* Initialize the global position length slot tables if not done so already. */ -static void -lzms_init_slot_bases(void) -{ - static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; - static bool already_computed = false; - - if (unlikely(!already_computed)) { - pthread_mutex_lock(&mutex); - if (!already_computed) { - lzms_compute_slot_bases(); - already_computed = true; - } - pthread_mutex_unlock(&mutex); - } -} - -/* Return the position slot for the specified offset. */ -static u32 -lzms_get_position_slot_raw(u32 offset) -{ - u32 position_slot = 0; - while (lzms_position_slot_base[position_slot + 1] <= offset) - position_slot++; - return position_slot; -} - /* Initialize the input bitstream @is to read forwards from the specified * compressed data buffer @in that is @in_limit 16-bit integers long. */ static void @@ -684,7 +578,7 @@ lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec) /* Decode and return the next Huffman-encoded symbol from the LZMS-compressed * block using the specified Huffman decoder. */ static u32 -lzms_decode_huffman_symbol(struct lzms_huffman_decoder *dec) +lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec) { const u8 *lens = dec->lens; const u16 *decode_table = dec->decode_table; @@ -749,7 +643,7 @@ lzms_decode_value(struct lzms_huffman_decoder *dec) /* Read the slot (position slot, length slot, etc.), which is encoded as * a Huffman symbol. */ - slot = lzms_decode_huffman_symbol(dec); + slot = lzms_huffman_decode_symbol(dec); LZMS_ASSERT(dec->slot_base_tab != NULL); @@ -884,7 +778,7 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx) bit = lzms_range_decode_bit(&ctx->delta_match_range_decoder); if (bit == 0) { - power = lzms_decode_huffman_symbol(&ctx->delta_power_decoder); + power = lzms_huffman_decode_symbol(&ctx->delta_power_decoder); raw_offset = lzms_decode_value(&ctx->delta_offset_decoder); } else { int i; @@ -927,7 +821,7 @@ lzms_decode_match(struct lzms_decompressor *ctx) static int lzms_decode_literal(struct lzms_decompressor *ctx) { - u8 literal = lzms_decode_huffman_symbol(&ctx->literal_decoder); + u8 literal = lzms_huffman_decode_symbol(&ctx->literal_decoder); LZMS_DEBUG("Decoded literal: 0x%02x", literal); return lzms_copy_literal(ctx, literal); } @@ -1027,7 +921,7 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, /* Calculate the number of position slots needed for this compressed * block. */ - num_position_slots = lzms_get_position_slot_raw(ulen - 1) + 1; + num_position_slots = lzms_get_position_slot(ulen - 1) + 1; LZMS_DEBUG("Using %u position slots", num_position_slots); @@ -1112,132 +1006,6 @@ lzms_decode_items(const u8 *cdata, size_t clen, u8 *ubuf, size_t ulen, return 0; } -static s32 -lzms_try_x86_translation(u8 *ubuf, s32 i, s32 num_op_bytes, - s32 *closest_target_usage_p, s32 last_target_usages[], - s32 max_trans_offset) -{ - u16 pos; - - if (i - *closest_target_usage_p <= max_trans_offset) { - LZMS_DEBUG("Performed x86 translation at position %d " - "(opcode 0x%02x)", i, ubuf[i]); - le32 *p32 = (le32*)&ubuf[i + num_op_bytes]; - u32 n = le32_to_cpu(*p32); - *p32 = cpu_to_le32(n - i); - } - - pos = i + le16_to_cpu(*(const le16*)&ubuf[i + num_op_bytes]); - - i += num_op_bytes + sizeof(le32) - 1; - - if (i - last_target_usages[pos] <= LZMS_X86_MAX_GOOD_TARGET_OFFSET) - *closest_target_usage_p = i; - - last_target_usages[pos] = i; - - return i + 1; -} - -static s32 -lzms_process_x86_translation(u8 *ubuf, s32 i, s32 *closest_target_usage_p, - s32 last_target_usages[]) -{ - /* Switch on first byte of the opcode, assuming it is really an x86 - * instruction. */ - switch (ubuf[i]) { - case 0x48: - if (ubuf[i + 1] == 0x8b) { - if (ubuf[i + 2] == 0x5 || ubuf[i + 2] == 0xd) { - /* Load relative (x86_64) */ - return lzms_try_x86_translation(ubuf, i, 3, - closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET); - } - } else if (ubuf[i + 1] == 0x8d) { - if ((ubuf[i + 2] & 0x7) == 0x5) { - /* Load effective address relative (x86_64) */ - return lzms_try_x86_translation(ubuf, i, 3, - closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET); - } - } - break; - - case 0x4c: - if (ubuf[i + 1] == 0x8d) { - if ((ubuf[i + 2] & 0x7) == 0x5) { - /* Load effective address relative (x86_64) */ - return lzms_try_x86_translation(ubuf, i, 3, - closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET); - } - } - break; - - case 0xe8: - /* Call relative */ - return lzms_try_x86_translation(ubuf, i, 1, closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET / 2); - - case 0xe9: - /* Jump relative */ - return i + 5; - - case 0xf0: - if (ubuf[i + 1] == 0x83 && ubuf[i + 2] == 0x05) { - /* Lock add relative */ - return lzms_try_x86_translation(ubuf, i, 3, - closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET); - } - break; - - case 0xff: - if (ubuf[i + 1] == 0x15) { - /* Call indirect */ - return lzms_try_x86_translation(ubuf, i, 2, - closest_target_usage_p, - last_target_usages, - LZMS_X86_MAX_TRANSLATION_OFFSET); - } - break; - } - return i + 1; -} - -/* Postprocess the uncompressed data by undoing the translation of relative - * addresses embedded in x86 instructions into absolute addresses. - * - * There does not appear to be any way to check to see if this postprocessing - * actually needs to be done (or to plug in alternate filters, like in LZMA), - * and the corresponding preprocessing seems to be done unconditionally. */ -static void -lzms_postprocess_data(u8 *ubuf, s32 ulen, s32 *last_target_usages) -{ - /* Offset (from beginning of buffer) of the most recent reference to a - * seemingly valid target address. */ - s32 closest_target_usage = -LZMS_X86_MAX_TRANSLATION_OFFSET - 1; - - /* Initialize the last_target_usages array. Each entry will contain the - * offset (from beginning of buffer) of the most recently used target - * address beginning with two bytes equal to the array index. */ - for (s32 i = 0; i < 65536; i++) - last_target_usages[i] = -LZMS_X86_MAX_GOOD_TARGET_OFFSET - 1; - - /* Check each byte in the buffer for an x86 opcode for which a - * translation may be possible. No translations are done on any - * instructions starting in the last 11 bytes of the buffer. */ - for (s32 i = 0; i < ulen - 11; ) - i = lzms_process_x86_translation(ubuf, i, &closest_target_usage, - last_target_usages); -} - static int lzms_decompress(const void *compressed_data, size_t compressed_size, void *uncompressed_data, size_t uncompressed_size, void *_ctx) @@ -1271,7 +1039,8 @@ lzms_decompress(const void *compressed_data, size_t compressed_size, * searched for a position of INT32_MAX or greater. */ if (uncompressed_size >= INT32_MAX) { LZMS_DEBUG("Uncompressed length too large " - "(got %u, expected < INT32_MAX)", ulen); + "(got %zu, expected < INT32_MAX)", + uncompressed_size); return -1; } @@ -1281,8 +1050,8 @@ lzms_decompress(const void *compressed_data, size_t compressed_size, return -1; /* Postprocess the data. */ - lzms_postprocess_data(uncompressed_data, uncompressed_size, - ctx->last_target_usages); + lzms_x86_filter(uncompressed_data, uncompressed_size, + ctx->last_target_usages, true); LZMS_DEBUG("Decompression successful."); return 0;