| /* | |
| * Branch/Call/Jump (BCJ) filter decoders | |
| * | |
| * Authors: Lasse Collin <[email protected]> | |
| * Igor Pavlov <http://7-zip.org/> | |
| * | |
| * This file has been put into the public domain. | |
| * You can do whatever you want with this file. | |
| */ | |
| #include "xz_private.h" | |
| /* | |
| * The rest of the file is inside this ifdef. It makes things a little more | |
| * convenient when building without support for any BCJ filters. | |
| */ | |
| #ifdef XZ_DEC_BCJ | |
| struct xz_dec_bcj { | |
| /* Type of the BCJ filter being used */ | |
| enum { | |
| BCJ_X86 = 4, /* x86 or x86-64 */ | |
| BCJ_POWERPC = 5, /* Big endian only */ | |
| BCJ_IA64 = 6, /* Big or little endian */ | |
| BCJ_ARM = 7, /* Little endian only */ | |
| BCJ_ARMTHUMB = 8, /* Little endian only */ | |
| BCJ_SPARC = 9 /* Big or little endian */ | |
| } type; | |
| /* | |
| * Return value of the next filter in the chain. We need to preserve | |
| * this information across calls, because we must not call the next | |
| * filter anymore once it has returned XZ_STREAM_END. | |
| */ | |
| enum xz_ret ret; | |
| /* True if we are operating in single-call mode. */ | |
| bool single_call; | |
| /* | |
| * Absolute position relative to the beginning of the uncompressed | |
| * data (in a single .xz Block). We care only about the lowest 32 | |
| * bits so this doesn't need to be uint64_t even with big files. | |
| */ | |
| uint32_t pos; | |
| /* x86 filter state */ | |
| uint32_t x86_prev_mask; | |
| /* Temporary space to hold the variables from struct xz_buf */ | |
| uint8_t *out; | |
| size_t out_pos; | |
| size_t out_size; | |
| struct { | |
| /* Amount of already filtered data in the beginning of buf */ | |
| size_t filtered; | |
| /* Total amount of data currently stored in buf */ | |
| size_t size; | |
| /* | |
| * Buffer to hold a mix of filtered and unfiltered data. This | |
| * needs to be big enough to hold Alignment + 2 * Look-ahead: | |
| * | |
| * Type Alignment Look-ahead | |
| * x86 1 4 | |
| * PowerPC 4 0 | |
| * IA-64 16 0 | |
| * ARM 4 0 | |
| * ARM-Thumb 2 2 | |
| * SPARC 4 0 | |
| */ | |
| uint8_t buf[16]; | |
| } temp; | |
| }; | |
| #ifdef XZ_DEC_X86 | |
| /* | |
| * This is used to test the most significant byte of a memory address | |
| * in an x86 instruction. | |
| */ | |
| static inline int bcj_x86_test_msbyte(uint8_t b) | |
| { | |
| return b == 0x00 || b == 0xFF; | |
| } | |
| static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| static const bool mask_to_allowed_status[8] | |
| = { true, true, true, false, true, false, false, false }; | |
| static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 }; | |
| size_t i; | |
| size_t prev_pos = (size_t)-1; | |
| uint32_t prev_mask = s->x86_prev_mask; | |
| uint32_t src; | |
| uint32_t dest; | |
| uint32_t j; | |
| uint8_t b; | |
| if (size <= 4) | |
| return 0; | |
| size -= 4; | |
| for (i = 0; i < size; ++i) { | |
| if ((buf[i] & 0xFE) != 0xE8) | |
| continue; | |
| prev_pos = i - prev_pos; | |
| if (prev_pos > 3) { | |
| prev_mask = 0; | |
| } else { | |
| prev_mask = (prev_mask << (prev_pos - 1)) & 7; | |
| if (prev_mask != 0) { | |
| b = buf[i + 4 - mask_to_bit_num[prev_mask]]; | |
| if (!mask_to_allowed_status[prev_mask] | |
| || bcj_x86_test_msbyte(b)) { | |
| prev_pos = i; | |
| prev_mask = (prev_mask << 1) | 1; | |
| continue; | |
| } | |
| } | |
| } | |
| prev_pos = i; | |
| if (bcj_x86_test_msbyte(buf[i + 4])) { | |
| src = get_unaligned_le32(buf + i + 1); | |
| while (true) { | |
| dest = src - (s->pos + (uint32_t)i + 5); | |
| if (prev_mask == 0) | |
| break; | |
| j = mask_to_bit_num[prev_mask] * 8; | |
| b = (uint8_t)(dest >> (24 - j)); | |
| if (!bcj_x86_test_msbyte(b)) | |
| break; | |
| src = dest ^ (((uint32_t)1 << (32 - j)) - 1); | |
| } | |
| dest &= 0x01FFFFFF; | |
| dest |= (uint32_t)0 - (dest & 0x01000000); | |
| put_unaligned_le32(dest, buf + i + 1); | |
| i += 4; | |
| } else { | |
| prev_mask = (prev_mask << 1) | 1; | |
| } | |
| } | |
| prev_pos = i - prev_pos; | |
| s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1); | |
| return i; | |
| } | |
| #endif | |
| #ifdef XZ_DEC_POWERPC | |
| static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| size_t i; | |
| uint32_t instr; | |
| for (i = 0; i + 4 <= size; i += 4) { | |
| instr = get_unaligned_be32(buf + i); | |
| if ((instr & 0xFC000003) == 0x48000001) { | |
| instr &= 0x03FFFFFC; | |
| instr -= s->pos + (uint32_t)i; | |
| instr &= 0x03FFFFFC; | |
| instr |= 0x48000001; | |
| put_unaligned_be32(instr, buf + i); | |
| } | |
| } | |
| return i; | |
| } | |
| #endif | |
| #ifdef XZ_DEC_IA64 | |
| static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| static const uint8_t branch_table[32] = { | |
| 0, 0, 0, 0, 0, 0, 0, 0, | |
| 0, 0, 0, 0, 0, 0, 0, 0, | |
| 4, 4, 6, 6, 0, 0, 7, 7, | |
| 4, 4, 0, 0, 4, 4, 0, 0 | |
| }; | |
| /* | |
| * The local variables take a little bit stack space, but it's less | |
| * than what LZMA2 decoder takes, so it doesn't make sense to reduce | |
| * stack usage here without doing that for the LZMA2 decoder too. | |
| */ | |
| /* Loop counters */ | |
| size_t i; | |
| size_t j; | |
| /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */ | |
| uint32_t slot; | |
| /* Bitwise offset of the instruction indicated by slot */ | |
| uint32_t bit_pos; | |
| /* bit_pos split into byte and bit parts */ | |
| uint32_t byte_pos; | |
| uint32_t bit_res; | |
| /* Address part of an instruction */ | |
| uint32_t addr; | |
| /* Mask used to detect which instructions to convert */ | |
| uint32_t mask; | |
| /* 41-bit instruction stored somewhere in the lowest 48 bits */ | |
| uint64_t instr; | |
| /* Instruction normalized with bit_res for easier manipulation */ | |
| uint64_t norm; | |
| for (i = 0; i + 16 <= size; i += 16) { | |
| mask = branch_table[buf[i] & 0x1F]; | |
| for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) { | |
| if (((mask >> slot) & 1) == 0) | |
| continue; | |
| byte_pos = bit_pos >> 3; | |
| bit_res = bit_pos & 7; | |
| instr = 0; | |
| for (j = 0; j < 6; ++j) | |
| instr |= (uint64_t)(buf[i + j + byte_pos]) | |
| << (8 * j); | |
| norm = instr >> bit_res; | |
| if (((norm >> 37) & 0x0F) == 0x05 | |
| && ((norm >> 9) & 0x07) == 0) { | |
| addr = (norm >> 13) & 0x0FFFFF; | |
| addr |= ((uint32_t)(norm >> 36) & 1) << 20; | |
| addr <<= 4; | |
| addr -= s->pos + (uint32_t)i; | |
| addr >>= 4; | |
| norm &= ~((uint64_t)0x8FFFFF << 13); | |
| norm |= (uint64_t)(addr & 0x0FFFFF) << 13; | |
| norm |= (uint64_t)(addr & 0x100000) | |
| << (36 - 20); | |
| instr &= (1 << bit_res) - 1; | |
| instr |= norm << bit_res; | |
| for (j = 0; j < 6; j++) | |
| buf[i + j + byte_pos] | |
| = (uint8_t)(instr >> (8 * j)); | |
| } | |
| } | |
| } | |
| return i; | |
| } | |
| #endif | |
| #ifdef XZ_DEC_ARM | |
| static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| size_t i; | |
| uint32_t addr; | |
| for (i = 0; i + 4 <= size; i += 4) { | |
| if (buf[i + 3] == 0xEB) { | |
| addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8) | |
| | ((uint32_t)buf[i + 2] << 16); | |
| addr <<= 2; | |
| addr -= s->pos + (uint32_t)i + 8; | |
| addr >>= 2; | |
| buf[i] = (uint8_t)addr; | |
| buf[i + 1] = (uint8_t)(addr >> 8); | |
| buf[i + 2] = (uint8_t)(addr >> 16); | |
| } | |
| } | |
| return i; | |
| } | |
| #endif | |
| #ifdef XZ_DEC_ARMTHUMB | |
| static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| size_t i; | |
| uint32_t addr; | |
| for (i = 0; i + 4 <= size; i += 2) { | |
| if ((buf[i + 1] & 0xF8) == 0xF0 | |
| && (buf[i + 3] & 0xF8) == 0xF8) { | |
| addr = (((uint32_t)buf[i + 1] & 0x07) << 19) | |
| | ((uint32_t)buf[i] << 11) | |
| | (((uint32_t)buf[i + 3] & 0x07) << 8) | |
| | (uint32_t)buf[i + 2]; | |
| addr <<= 1; | |
| addr -= s->pos + (uint32_t)i + 4; | |
| addr >>= 1; | |
| buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07)); | |
| buf[i] = (uint8_t)(addr >> 11); | |
| buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07)); | |
| buf[i + 2] = (uint8_t)addr; | |
| i += 2; | |
| } | |
| } | |
| return i; | |
| } | |
| #endif | |
| #ifdef XZ_DEC_SPARC | |
| static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size) | |
| { | |
| size_t i; | |
| uint32_t instr; | |
| for (i = 0; i + 4 <= size; i += 4) { | |
| instr = get_unaligned_be32(buf + i); | |
| if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) { | |
| instr <<= 2; | |
| instr -= s->pos + (uint32_t)i; | |
| instr >>= 2; | |
| instr = ((uint32_t)0x40000000 - (instr & 0x400000)) | |
| | 0x40000000 | (instr & 0x3FFFFF); | |
| put_unaligned_be32(instr, buf + i); | |
| } | |
| } | |
| return i; | |
| } | |
| #endif | |
| /* | |
| * Apply the selected BCJ filter. Update *pos and s->pos to match the amount | |
| * of data that got filtered. | |
| * | |
| * NOTE: This is implemented as a switch statement to avoid using function | |
| * pointers, which could be problematic in the kernel boot code, which must | |
| * avoid pointers to static data (at least on x86). | |
| */ | |
| static void bcj_apply(struct xz_dec_bcj *s, | |
| uint8_t *buf, size_t *pos, size_t size) | |
| { | |
| size_t filtered; | |
| buf += *pos; | |
| size -= *pos; | |
| switch (s->type) { | |
| #ifdef XZ_DEC_X86 | |
| case BCJ_X86: | |
| filtered = bcj_x86(s, buf, size); | |
| break; | |
| #endif | |
| #ifdef XZ_DEC_POWERPC | |
| case BCJ_POWERPC: | |
| filtered = bcj_powerpc(s, buf, size); | |
| break; | |
| #endif | |
| #ifdef XZ_DEC_IA64 | |
| case BCJ_IA64: | |
| filtered = bcj_ia64(s, buf, size); | |
| break; | |
| #endif | |
| #ifdef XZ_DEC_ARM | |
| case BCJ_ARM: | |
| filtered = bcj_arm(s, buf, size); | |
| break; | |
| #endif | |
| #ifdef XZ_DEC_ARMTHUMB | |
| case BCJ_ARMTHUMB: | |
| filtered = bcj_armthumb(s, buf, size); | |
| break; | |
| #endif | |
| #ifdef XZ_DEC_SPARC | |
| case BCJ_SPARC: | |
| filtered = bcj_sparc(s, buf, size); | |
| break; | |
| #endif | |
| default: | |
| /* Never reached but silence compiler warnings. */ | |
| filtered = 0; | |
| break; | |
| } | |
| *pos += filtered; | |
| s->pos += filtered; | |
| } | |
| /* | |
| * Flush pending filtered data from temp to the output buffer. | |
| * Move the remaining mixture of possibly filtered and unfiltered | |
| * data to the beginning of temp. | |
| */ | |
| static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b) | |
| { | |
| size_t copy_size; | |
| copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos); | |
| memcpy(b->out + b->out_pos, s->temp.buf, copy_size); | |
| b->out_pos += copy_size; | |
| s->temp.filtered -= copy_size; | |
| s->temp.size -= copy_size; | |
| memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size); | |
| } | |
| /* | |
| * The BCJ filter functions are primitive in sense that they process the | |
| * data in chunks of 1-16 bytes. To hide this issue, this function does | |
| * some buffering. | |
| */ | |
| XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s, | |
| struct xz_dec_lzma2 *lzma2, | |
| struct xz_buf *b) | |
| { | |
| size_t out_start; | |
| /* | |
| * Flush pending already filtered data to the output buffer. Return | |
| * immediatelly if we couldn't flush everything, or if the next | |
| * filter in the chain had already returned XZ_STREAM_END. | |
| */ | |
| if (s->temp.filtered > 0) { | |
| bcj_flush(s, b); | |
| if (s->temp.filtered > 0) | |
| return XZ_OK; | |
| if (s->ret == XZ_STREAM_END) | |
| return XZ_STREAM_END; | |
| } | |
| /* | |
| * If we have more output space than what is currently pending in | |
| * temp, copy the unfiltered data from temp to the output buffer | |
| * and try to fill the output buffer by decoding more data from the | |
| * next filter in the chain. Apply the BCJ filter on the new data | |
| * in the output buffer. If everything cannot be filtered, copy it | |
| * to temp and rewind the output buffer position accordingly. | |
| * | |
| * This needs to be always run when temp.size == 0 to handle a special | |
| * case where the output buffer is full and the next filter has no | |
| * more output coming but hasn't returned XZ_STREAM_END yet. | |
| */ | |
| if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) { | |
| out_start = b->out_pos; | |
| memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size); | |
| b->out_pos += s->temp.size; | |
| s->ret = xz_dec_lzma2_run(lzma2, b); | |
| if (s->ret != XZ_STREAM_END | |
| && (s->ret != XZ_OK || s->single_call)) | |
| return s->ret; | |
| bcj_apply(s, b->out, &out_start, b->out_pos); | |
| /* | |
| * As an exception, if the next filter returned XZ_STREAM_END, | |
| * we can do that too, since the last few bytes that remain | |
| * unfiltered are meant to remain unfiltered. | |
| */ | |
| if (s->ret == XZ_STREAM_END) | |
| return XZ_STREAM_END; | |
| s->temp.size = b->out_pos - out_start; | |
| b->out_pos -= s->temp.size; | |
| memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size); | |
| /* | |
| * If there wasn't enough input to the next filter to fill | |
| * the output buffer with unfiltered data, there's no point | |
| * to try decoding more data to temp. | |
| */ | |
| if (b->out_pos + s->temp.size < b->out_size) | |
| return XZ_OK; | |
| } | |
| /* | |
| * We have unfiltered data in temp. If the output buffer isn't full | |
| * yet, try to fill the temp buffer by decoding more data from the | |
| * next filter. Apply the BCJ filter on temp. Then we hopefully can | |
| * fill the actual output buffer by copying filtered data from temp. | |
| * A mix of filtered and unfiltered data may be left in temp; it will | |
| * be taken care on the next call to this function. | |
| */ | |
| if (b->out_pos < b->out_size) { | |
| /* Make b->out{,_pos,_size} temporarily point to s->temp. */ | |
| s->out = b->out; | |
| s->out_pos = b->out_pos; | |
| s->out_size = b->out_size; | |
| b->out = s->temp.buf; | |
| b->out_pos = s->temp.size; | |
| b->out_size = sizeof(s->temp.buf); | |
| s->ret = xz_dec_lzma2_run(lzma2, b); | |
| s->temp.size = b->out_pos; | |
| b->out = s->out; | |
| b->out_pos = s->out_pos; | |
| b->out_size = s->out_size; | |
| if (s->ret != XZ_OK && s->ret != XZ_STREAM_END) | |
| return s->ret; | |
| bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size); | |
| /* | |
| * If the next filter returned XZ_STREAM_END, we mark that | |
| * everything is filtered, since the last unfiltered bytes | |
| * of the stream are meant to be left as is. | |
| */ | |
| if (s->ret == XZ_STREAM_END) | |
| s->temp.filtered = s->temp.size; | |
| bcj_flush(s, b); | |
| if (s->temp.filtered > 0) | |
| return XZ_OK; | |
| } | |
| return s->ret; | |
| } | |
| XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call) | |
| { | |
| struct xz_dec_bcj *s = kmalloc(sizeof(*s), GFP_KERNEL); | |
| if (s != NULL) | |
| s->single_call = single_call; | |
| return s; | |
| } | |
| XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id) | |
| { | |
| switch (id) { | |
| #ifdef XZ_DEC_X86 | |
| case BCJ_X86: | |
| #endif | |
| #ifdef XZ_DEC_POWERPC | |
| case BCJ_POWERPC: | |
| #endif | |
| #ifdef XZ_DEC_IA64 | |
| case BCJ_IA64: | |
| #endif | |
| #ifdef XZ_DEC_ARM | |
| case BCJ_ARM: | |
| #endif | |
| #ifdef XZ_DEC_ARMTHUMB | |
| case BCJ_ARMTHUMB: | |
| #endif | |
| #ifdef XZ_DEC_SPARC | |
| case BCJ_SPARC: | |
| #endif | |
| break; | |
| default: | |
| /* Unsupported Filter ID */ | |
| return XZ_OPTIONS_ERROR; | |
| } | |
| s->type = id; | |
| s->ret = XZ_OK; | |
| s->pos = 0; | |
| s->x86_prev_mask = 0; | |
| s->temp.filtered = 0; | |
| s->temp.size = 0; | |
| return XZ_OK; | |
| } | |
| #endif |