2 * Branch/Call/Jump (BCJ) filter decoders
4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
11 #include "xz_private.h"
14 * The rest of the file is inside this ifdef. It makes things a little more
15 * convenient when building without support for any BCJ filters.
20 /* Type of the BCJ filter being used */
22 BCJ_X86
= 4, /* x86 or x86-64 */
23 BCJ_POWERPC
= 5, /* Big endian only */
24 BCJ_IA64
= 6, /* Big or little endian */
25 BCJ_ARM
= 7, /* Little endian only */
26 BCJ_ARMTHUMB
= 8, /* Little endian only */
27 BCJ_SPARC
= 9 /* Big or little endian */
31 * Return value of the next filter in the chain. We need to preserve
32 * this information across calls, because we must not call the next
33 * filter anymore once it has returned XZ_STREAM_END.
37 /* True if we are operating in single-call mode. */
41 * Absolute position relative to the beginning of the uncompressed
42 * data (in a single .xz Block). We care only about the lowest 32
43 * bits so this doesn't need to be uint64_t even with big files.
47 /* x86 filter state */
48 uint32_t x86_prev_mask
;
50 /* Temporary space to hold the variables from struct xz_buf */
56 /* Amount of already filtered data in the beginning of buf */
59 /* Total amount of data currently stored in buf */
63 * Buffer to hold a mix of filtered and unfiltered data. This
64 * needs to be big enough to hold Alignment + 2 * Look-ahead:
66 * Type Alignment Look-ahead
80 * This is used to test the most significant byte of a memory address
81 * in an x86 instruction.
83 static inline int bcj_x86_test_msbyte(uint8_t b
)
85 return b
== 0x00 || b
== 0xFF;
88 static noinline_for_stack
size_t XZ_FUNC
bcj_x86(
89 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
91 static const bool mask_to_allowed_status
[8]
92 = { true, true, true, false, true, false, false, false };
94 static const uint8_t mask_to_bit_num
[8] = { 0, 1, 2, 2, 3, 3, 3, 3 };
97 size_t prev_pos
= (size_t)-1;
98 uint32_t prev_mask
= s
->x86_prev_mask
;
108 for (i
= 0; i
< size
; ++i
) {
109 if ((buf
[i
] & 0xFE) != 0xE8)
112 prev_pos
= i
- prev_pos
;
116 prev_mask
= (prev_mask
<< (prev_pos
- 1)) & 7;
117 if (prev_mask
!= 0) {
118 b
= buf
[i
+ 4 - mask_to_bit_num
[prev_mask
]];
119 if (!mask_to_allowed_status
[prev_mask
]
120 || bcj_x86_test_msbyte(b
)) {
122 prev_mask
= (prev_mask
<< 1) | 1;
130 if (bcj_x86_test_msbyte(buf
[i
+ 4])) {
131 src
= get_unaligned_le32(buf
+ i
+ 1);
133 dest
= src
- (s
->pos
+ (uint32_t)i
+ 5);
137 j
= mask_to_bit_num
[prev_mask
] * 8;
138 b
= (uint8_t)(dest
>> (24 - j
));
139 if (!bcj_x86_test_msbyte(b
))
142 src
= dest
^ (((uint32_t)1 << (32 - j
)) - 1);
146 dest
|= (uint32_t)0 - (dest
& 0x01000000);
147 put_unaligned_le32(dest
, buf
+ i
+ 1);
150 prev_mask
= (prev_mask
<< 1) | 1;
154 prev_pos
= i
- prev_pos
;
155 s
->x86_prev_mask
= prev_pos
> 3 ? 0 : prev_mask
<< (prev_pos
- 1);
160 #ifdef XZ_DEC_POWERPC
161 static noinline_for_stack
size_t XZ_FUNC
bcj_powerpc(
162 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
167 for (i
= 0; i
+ 4 <= size
; i
+= 4) {
168 instr
= get_unaligned_be32(buf
+ i
);
169 if ((instr
& 0xFC000003) == 0x48000001) {
171 instr
-= s
->pos
+ (uint32_t)i
;
174 put_unaligned_be32(instr
, buf
+ i
);
183 static noinline_for_stack
size_t XZ_FUNC
bcj_ia64(
184 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
186 static const uint8_t branch_table
[32] = {
187 0, 0, 0, 0, 0, 0, 0, 0,
188 0, 0, 0, 0, 0, 0, 0, 0,
189 4, 4, 6, 6, 0, 0, 7, 7,
190 4, 4, 0, 0, 4, 4, 0, 0
194 * The local variables take a little bit stack space, but it's less
195 * than what LZMA2 decoder takes, so it doesn't make sense to reduce
196 * stack usage here without doing that for the LZMA2 decoder too.
203 /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */
206 /* Bitwise offset of the instruction indicated by slot */
209 /* bit_pos split into byte and bit parts */
213 /* Address part of an instruction */
216 /* Mask used to detect which instructions to convert */
219 /* 41-bit instruction stored somewhere in the lowest 48 bits */
222 /* Instruction normalized with bit_res for easier manipulation */
225 for (i
= 0; i
+ 16 <= size
; i
+= 16) {
226 mask
= branch_table
[buf
[i
] & 0x1F];
227 for (slot
= 0, bit_pos
= 5; slot
< 3; ++slot
, bit_pos
+= 41) {
228 if (((mask
>> slot
) & 1) == 0)
231 byte_pos
= bit_pos
>> 3;
232 bit_res
= bit_pos
& 7;
234 for (j
= 0; j
< 6; ++j
)
235 instr
|= (uint64_t)(buf
[i
+ j
+ byte_pos
])
238 norm
= instr
>> bit_res
;
240 if (((norm
>> 37) & 0x0F) == 0x05
241 && ((norm
>> 9) & 0x07) == 0) {
242 addr
= (norm
>> 13) & 0x0FFFFF;
243 addr
|= ((uint32_t)(norm
>> 36) & 1) << 20;
245 addr
-= s
->pos
+ (uint32_t)i
;
248 norm
&= ~((uint64_t)0x8FFFFF << 13);
249 norm
|= (uint64_t)(addr
& 0x0FFFFF) << 13;
250 norm
|= (uint64_t)(addr
& 0x100000)
253 instr
&= (1 << bit_res
) - 1;
254 instr
|= norm
<< bit_res
;
256 for (j
= 0; j
< 6; j
++)
257 buf
[i
+ j
+ byte_pos
]
258 = (uint8_t)(instr
>> (8 * j
));
268 static noinline_for_stack
size_t XZ_FUNC
bcj_arm(
269 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
274 for (i
= 0; i
+ 4 <= size
; i
+= 4) {
275 if (buf
[i
+ 3] == 0xEB) {
276 addr
= (uint32_t)buf
[i
] | ((uint32_t)buf
[i
+ 1] << 8)
277 | ((uint32_t)buf
[i
+ 2] << 16);
279 addr
-= s
->pos
+ (uint32_t)i
+ 8;
281 buf
[i
] = (uint8_t)addr
;
282 buf
[i
+ 1] = (uint8_t)(addr
>> 8);
283 buf
[i
+ 2] = (uint8_t)(addr
>> 16);
291 #ifdef XZ_DEC_ARMTHUMB
292 static noinline_for_stack
size_t XZ_FUNC
bcj_armthumb(
293 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
298 for (i
= 0; i
+ 4 <= size
; i
+= 2) {
299 if ((buf
[i
+ 1] & 0xF8) == 0xF0
300 && (buf
[i
+ 3] & 0xF8) == 0xF8) {
301 addr
= (((uint32_t)buf
[i
+ 1] & 0x07) << 19)
302 | ((uint32_t)buf
[i
] << 11)
303 | (((uint32_t)buf
[i
+ 3] & 0x07) << 8)
304 | (uint32_t)buf
[i
+ 2];
306 addr
-= s
->pos
+ (uint32_t)i
+ 4;
308 buf
[i
+ 1] = (uint8_t)(0xF0 | ((addr
>> 19) & 0x07));
309 buf
[i
] = (uint8_t)(addr
>> 11);
310 buf
[i
+ 3] = (uint8_t)(0xF8 | ((addr
>> 8) & 0x07));
311 buf
[i
+ 2] = (uint8_t)addr
;
321 static noinline_for_stack
size_t XZ_FUNC
bcj_sparc(
322 struct xz_dec_bcj
*s
, uint8_t *buf
, size_t size
)
327 for (i
= 0; i
+ 4 <= size
; i
+= 4) {
328 instr
= get_unaligned_be32(buf
+ i
);
329 if ((instr
>> 22) == 0x100 || (instr
>> 22) == 0x1FF) {
331 instr
-= s
->pos
+ (uint32_t)i
;
333 instr
= ((uint32_t)0x40000000 - (instr
& 0x400000))
334 | 0x40000000 | (instr
& 0x3FFFFF);
335 put_unaligned_be32(instr
, buf
+ i
);
344 * Apply the selected BCJ filter. Update *pos and s->pos to match the amount
345 * of data that got filtered.
347 * NOTE: This is implemented as a switch statement to avoid using function
348 * pointers, which could be problematic in the kernel boot code, which must
349 * avoid pointers to static data (at least on x86).
351 static void XZ_FUNC
bcj_apply(struct xz_dec_bcj
*s
,
352 uint8_t *buf
, size_t *pos
, size_t size
)
362 filtered
= bcj_x86(s
, buf
, size
);
365 #ifdef XZ_DEC_POWERPC
367 filtered
= bcj_powerpc(s
, buf
, size
);
372 filtered
= bcj_ia64(s
, buf
, size
);
377 filtered
= bcj_arm(s
, buf
, size
);
380 #ifdef XZ_DEC_ARMTHUMB
382 filtered
= bcj_armthumb(s
, buf
, size
);
387 filtered
= bcj_sparc(s
, buf
, size
);
391 /* Never reached but silence compiler warnings. */
401 * Flush pending filtered data from temp to the output buffer.
402 * Move the remaining mixture of possibly filtered and unfiltered
403 * data to the beginning of temp.
405 static void XZ_FUNC
bcj_flush(struct xz_dec_bcj
*s
, struct xz_buf
*b
)
409 copy_size
= min_t(size_t, s
->temp
.filtered
, b
->out_size
- b
->out_pos
);
410 memcpy(b
->out
+ b
->out_pos
, s
->temp
.buf
, copy_size
);
411 b
->out_pos
+= copy_size
;
413 s
->temp
.filtered
-= copy_size
;
414 s
->temp
.size
-= copy_size
;
415 memmove(s
->temp
.buf
, s
->temp
.buf
+ copy_size
, s
->temp
.size
);
419 * The BCJ filter functions are primitive in sense that they process the
420 * data in chunks of 1-16 bytes. To hide this issue, this function does
423 XZ_EXTERN
enum xz_ret XZ_FUNC
xz_dec_bcj_run(struct xz_dec_bcj
*s
,
424 struct xz_dec_lzma2
*lzma2
, struct xz_buf
*b
)
429 * Flush pending already filtered data to the output buffer. Return
430 * immediatelly if we couldn't flush everything, or if the next
431 * filter in the chain had already returned XZ_STREAM_END.
433 if (s
->temp
.filtered
> 0) {
435 if (s
->temp
.filtered
> 0)
438 if (s
->ret
== XZ_STREAM_END
)
439 return XZ_STREAM_END
;
443 * If we have more output space than what is currently pending in
444 * temp, copy the unfiltered data from temp to the output buffer
445 * and try to fill the output buffer by decoding more data from the
446 * next filter in the chain. Apply the BCJ filter on the new data
447 * in the output buffer. If everything cannot be filtered, copy it
448 * to temp and rewind the output buffer position accordingly.
450 * This needs to be always run when temp.size == 0 to handle a special
451 * case where the output buffer is full and the next filter has no
452 * more output coming but hasn't returned XZ_STREAM_END yet.
454 if (s
->temp
.size
< b
->out_size
- b
->out_pos
|| s
->temp
.size
== 0) {
455 out_start
= b
->out_pos
;
456 memcpy(b
->out
+ b
->out_pos
, s
->temp
.buf
, s
->temp
.size
);
457 b
->out_pos
+= s
->temp
.size
;
459 s
->ret
= xz_dec_lzma2_run(lzma2
, b
);
460 if (s
->ret
!= XZ_STREAM_END
461 && (s
->ret
!= XZ_OK
|| s
->single_call
))
464 bcj_apply(s
, b
->out
, &out_start
, b
->out_pos
);
467 * As an exception, if the next filter returned XZ_STREAM_END,
468 * we can do that too, since the last few bytes that remain
469 * unfiltered are meant to remain unfiltered.
471 if (s
->ret
== XZ_STREAM_END
)
472 return XZ_STREAM_END
;
474 s
->temp
.size
= b
->out_pos
- out_start
;
475 b
->out_pos
-= s
->temp
.size
;
476 memcpy(s
->temp
.buf
, b
->out
+ b
->out_pos
, s
->temp
.size
);
479 * If there wasn't enough input to the next filter to fill
480 * the output buffer with unfiltered data, there's no point
481 * to try decoding more data to temp.
483 if (b
->out_pos
+ s
->temp
.size
< b
->out_size
)
488 * We have unfiltered data in temp. If the output buffer isn't full
489 * yet, try to fill the temp buffer by decoding more data from the
490 * next filter. Apply the BCJ filter on temp. Then we hopefully can
491 * fill the actual output buffer by copying filtered data from temp.
492 * A mix of filtered and unfiltered data may be left in temp; it will
493 * be taken care on the next call to this function.
495 if (b
->out_pos
< b
->out_size
) {
496 /* Make b->out{,_pos,_size} temporarily point to s->temp. */
498 s
->out_pos
= b
->out_pos
;
499 s
->out_size
= b
->out_size
;
500 b
->out
= s
->temp
.buf
;
501 b
->out_pos
= s
->temp
.size
;
502 b
->out_size
= sizeof(s
->temp
.buf
);
504 s
->ret
= xz_dec_lzma2_run(lzma2
, b
);
506 s
->temp
.size
= b
->out_pos
;
508 b
->out_pos
= s
->out_pos
;
509 b
->out_size
= s
->out_size
;
511 if (s
->ret
!= XZ_OK
&& s
->ret
!= XZ_STREAM_END
)
514 bcj_apply(s
, s
->temp
.buf
, &s
->temp
.filtered
, s
->temp
.size
);
517 * If the next filter returned XZ_STREAM_END, we mark that
518 * everything is filtered, since the last unfiltered bytes
519 * of the stream are meant to be left as is.
521 if (s
->ret
== XZ_STREAM_END
)
522 s
->temp
.filtered
= s
->temp
.size
;
525 if (s
->temp
.filtered
> 0)
532 XZ_EXTERN
struct xz_dec_bcj
* XZ_FUNC
xz_dec_bcj_create(bool single_call
)
534 struct xz_dec_bcj
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
536 s
->single_call
= single_call
;
541 XZ_EXTERN
enum xz_ret XZ_FUNC
xz_dec_bcj_reset(
542 struct xz_dec_bcj
*s
, uint8_t id
)
548 #ifdef XZ_DEC_POWERPC
557 #ifdef XZ_DEC_ARMTHUMB
566 /* Unsupported Filter ID */
567 return XZ_OPTIONS_ERROR
;
573 s
->x86_prev_mask
= 0;
574 s
->temp
.filtered
= 0;