X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzx-decompress.c;h=d3ba46af846de85ec23f9cd35743fddfda05e2a7;hb=869ca1f4cc4654501d52f8c3e660c056904ccabf;hp=2405b9493ad9710f0476af9e2745fe8c59490b2f;hpb=883833a4b3dabec325edf1ca938000f91d587c00;p=wimlib diff --git a/src/lzx-decompress.c b/src/lzx-decompress.c index 2405b949..d3ba46af 100644 --- a/src/lzx-decompress.c +++ b/src/lzx-decompress.c @@ -7,7 +7,7 @@ */ /* - * Copyright (C) 2012, 2013 Eric Biggers + * Copyright (C) 2012, 2013, 2014 Eric Biggers * * This file is part of wimlib, a library for working with WIM files. * @@ -26,7 +26,7 @@ */ /* - * LZX is a LZ77 and Huffman-code based compression format that has many + * LZX is an LZ77 and Huffman-code based compression format that has many * similarities to the DEFLATE format used in zlib. The compression ratio is as * good or better than DEFLATE. * @@ -38,12 +38,12 @@ * last decompress to a fixed number of bytes, by default 32768. This is quite * similar to the cabinet (.cab) file format, but they are not the same. * According to the cabinet format documentation, the LZX block size is - * independent from the CFDATA blocks, and a LZX block may span several CFDATA + * independent from the CFDATA blocks, and an LZX block may span several CFDATA * blocks. However, in WIMs, LZX blocks do not appear to ever span multiple WIM * chunks. Note that this means any WIM chunk may be decompressed or compressed * independently from any other chunk, which allows random access. * - * A LZX compressed WIM chunk contains one or more LZX blocks of the aligned, + * An LZX compressed WIM chunk contains one or more LZX blocks of the aligned, * verbatim, or uncompressed block types. For aligned and verbatim blocks, the * size of the block in uncompressed bytes is specified by a bit following the 3 * bits that specify the block type, possibly followed by an additional 16 bits. @@ -115,6 +115,10 @@ #include +#ifdef __SSE2__ +# include +#endif + /* Huffman decoding tables and maps from symbols to code lengths. */ struct lzx_tables { @@ -319,7 +323,7 @@ lzx_read_code_lens(struct input_bitstream *istream, u8 lens[], * in bytes, will be returned. * @block_type_ret: A pointer to an int into which the type of the block * (LZX_BLOCKTYPE_*) will be returned. - * @tables: A pointer to a lzx_tables structure in which the + * @tables: A pointer to an lzx_tables structure in which the * main tree, the length tree, and possibly the * aligned offset tree will be constructed. * @queue: A pointer to the least-recently-used queue into which @@ -711,20 +715,19 @@ lzx_decode_match(unsigned main_element, int block_type, } static void -undo_call_insn_translation(u32 *call_insn_target, s32 input_pos, - s32 file_size) +undo_call_insn_translation(u32 *call_insn_target, s32 input_pos) { s32 abs_offset; s32 rel_offset; abs_offset = le32_to_cpu(*call_insn_target); - if (abs_offset >= -input_pos && abs_offset < file_size) { + if (abs_offset >= -input_pos && abs_offset < LZX_WIM_MAGIC_FILESIZE) { if (abs_offset >= 0) { /* "good translation" */ rel_offset = abs_offset - input_pos; } else { /* "compensating translation" */ - rel_offset = abs_offset + file_size; + rel_offset = abs_offset + LZX_WIM_MAGIC_FILESIZE; } *call_insn_target = cpu_to_le32(rel_offset); } @@ -753,20 +756,104 @@ undo_call_insn_translation(u32 *call_insn_target, s32 input_pos, * as it is used in calculating the translated jump targets. But in WIM files, * this file size is always the same (LZX_WIM_MAGIC_FILESIZE == 12000000).*/ static void -undo_call_insn_preprocessing(u8 *uncompressed_data, s32 uncompressed_size) +undo_call_insn_preprocessing(u8 *uncompressed_data, size_t uncompressed_size) { - for (s32 i = 0; i < uncompressed_size - 10; i++) { - if (uncompressed_data[i] == 0xe8) { - undo_call_insn_translation((u32*)&uncompressed_data[i + 1], - i, - LZX_WIM_MAGIC_FILESIZE); - i += 4; - } +#ifdef __SSE2__ + + /* SSE2 vectorized implementation for x86_64. This speeds up LZX + * decompression by about 5-8% overall. (Usually --- the performance + * actually regresses slightly in the degenerate case that the data + * consists entirely of 0xe8 bytes.) */ + __m128i *p128 = (__m128i *)uncompressed_data; + u32 valid_mask = 0xFFFFFFFF; + + if (uncompressed_size >= 32 && + ((uintptr_t)uncompressed_data % 16 == 0)) + { + __m128i * const end128 = p128 + uncompressed_size / 16 - 1; + + /* Create a vector of all 0xe8 bytes */ + const __m128i e8_bytes = _mm_set1_epi8(0xe8); + + /* Iterate through the 16-byte vectors in the input. */ + do { + /* Compare the current 16-byte vector with the vector of + * all 0xe8 bytes. This produces 0xff where the byte is + * 0xe8 and 0x00 where it is not. */ + __m128i cmpresult = _mm_cmpeq_epi8(*p128, e8_bytes); + + /* Map the comparison results into a single 16-bit + * number. It will contain a 1 bit when the + * corresponding byte in the current 16-byte vector is + * an e8 byte. Note: the low-order bit corresponds to + * the first (lowest address) byte. */ + u32 e8_mask = _mm_movemask_epi8(cmpresult); + + if (!e8_mask) { + /* If e8_mask is 0, then none of these 16 bytes + * have value 0xe8. No e8 translation is + * needed, and there is no restriction that + * carries over to the next 16 bytes. */ + valid_mask = 0xFFFFFFFF; + } else { + /* At least one byte has value 0xe8. + * + * The AND with valid_mask accounts for the fact + * that we can't start an e8 translation that + * overlaps the previous one. */ + while ((e8_mask &= valid_mask)) { + + /* Count the number of trailing zeroes + * in e8_mask. This will produce the + * index of the byte, within the 16, at + * which the next e8 translation should + * be done. */ + u32 bit = __builtin_ctz(e8_mask); + + /* Do the e8 translation. */ + u8 *p8 = (u8 *)p128 + bit; + undo_call_insn_translation((s32 *)(p8 + 1), + p8 - uncompressed_data); + + /* Don't start an e8 translation in the + * next 4 bytes. */ + valid_mask &= ~((u32)0x1F << bit); + } + /* Moving on to the next vector. Shift and set + * valid_mask accordingly. */ + valid_mask >>= 16; + valid_mask |= 0xFFFF0000; + } + } while (++p128 < end128); + } + + u8 *p8 = (u8 *)p128; + while (!(valid_mask & 1)) { + p8++; + valid_mask >>= 1; + } +#else /* __SSE2__ */ + u8 *p8 = uncompressed_data; +#endif /* !__SSE2__ */ + + if (uncompressed_size > 10) { + /* Finish any bytes that weren't processed by the vectorized + * implementation. */ + u8 *p8_end = uncompressed_data + uncompressed_size - 10; + do { + if (*p8 == 0xe8) { + undo_call_insn_translation((s32 *)(p8 + 1), + p8 - uncompressed_data); + p8 += 5; + } else { + p8++; + } + } while (p8 < p8_end); } } /* - * Decompresses a LZX-compressed block of data from which the header has already + * Decompresses an LZX-compressed block of data from which the header has already * been read. * * @block_type: The type of the block (LZX_BLOCKTYPE_VERBATIM or