xref: /openbmc/linux/lib/xz/xz_dec_bcj.c (revision dbf563ee)
1 /*
2  * Branch/Call/Jump (BCJ) filter decoders
3  *
4  * Authors: Lasse Collin <lasse.collin@tukaani.org>
5  *          Igor Pavlov <https://7-zip.org/>
6  *
7  * This file has been put into the public domain.
8  * You can do whatever you want with this file.
9  */
10 
11 #include "xz_private.h"
12 
13 /*
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.
16  */
17 #ifdef XZ_DEC_BCJ
18 
19 struct xz_dec_bcj {
20 	/* Type of the BCJ filter being used */
21 	enum {
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 */
28 	} type;
29 
30 	/*
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.
34 	 */
35 	enum xz_ret ret;
36 
37 	/* True if we are operating in single-call mode. */
38 	bool single_call;
39 
40 	/*
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.
44 	 */
45 	uint32_t pos;
46 
47 	/* x86 filter state */
48 	uint32_t x86_prev_mask;
49 
50 	/* Temporary space to hold the variables from struct xz_buf */
51 	uint8_t *out;
52 	size_t out_pos;
53 	size_t out_size;
54 
55 	struct {
56 		/* Amount of already filtered data in the beginning of buf */
57 		size_t filtered;
58 
59 		/* Total amount of data currently stored in buf  */
60 		size_t size;
61 
62 		/*
63 		 * Buffer to hold a mix of filtered and unfiltered data. This
64 		 * needs to be big enough to hold Alignment + 2 * Look-ahead:
65 		 *
66 		 * Type         Alignment   Look-ahead
67 		 * x86              1           4
68 		 * PowerPC          4           0
69 		 * IA-64           16           0
70 		 * ARM              4           0
71 		 * ARM-Thumb        2           2
72 		 * SPARC            4           0
73 		 */
74 		uint8_t buf[16];
75 	} temp;
76 };
77 
78 #ifdef XZ_DEC_X86
79 /*
80  * This is used to test the most significant byte of a memory address
81  * in an x86 instruction.
82  */
83 static inline int bcj_x86_test_msbyte(uint8_t b)
84 {
85 	return b == 0x00 || b == 0xFF;
86 }
87 
88 static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
89 {
90 	static const bool mask_to_allowed_status[8]
91 		= { true, true, true, false, true, false, false, false };
92 
93 	static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 };
94 
95 	size_t i;
96 	size_t prev_pos = (size_t)-1;
97 	uint32_t prev_mask = s->x86_prev_mask;
98 	uint32_t src;
99 	uint32_t dest;
100 	uint32_t j;
101 	uint8_t b;
102 
103 	if (size <= 4)
104 		return 0;
105 
106 	size -= 4;
107 	for (i = 0; i < size; ++i) {
108 		if ((buf[i] & 0xFE) != 0xE8)
109 			continue;
110 
111 		prev_pos = i - prev_pos;
112 		if (prev_pos > 3) {
113 			prev_mask = 0;
114 		} else {
115 			prev_mask = (prev_mask << (prev_pos - 1)) & 7;
116 			if (prev_mask != 0) {
117 				b = buf[i + 4 - mask_to_bit_num[prev_mask]];
118 				if (!mask_to_allowed_status[prev_mask]
119 						|| bcj_x86_test_msbyte(b)) {
120 					prev_pos = i;
121 					prev_mask = (prev_mask << 1) | 1;
122 					continue;
123 				}
124 			}
125 		}
126 
127 		prev_pos = i;
128 
129 		if (bcj_x86_test_msbyte(buf[i + 4])) {
130 			src = get_unaligned_le32(buf + i + 1);
131 			while (true) {
132 				dest = src - (s->pos + (uint32_t)i + 5);
133 				if (prev_mask == 0)
134 					break;
135 
136 				j = mask_to_bit_num[prev_mask] * 8;
137 				b = (uint8_t)(dest >> (24 - j));
138 				if (!bcj_x86_test_msbyte(b))
139 					break;
140 
141 				src = dest ^ (((uint32_t)1 << (32 - j)) - 1);
142 			}
143 
144 			dest &= 0x01FFFFFF;
145 			dest |= (uint32_t)0 - (dest & 0x01000000);
146 			put_unaligned_le32(dest, buf + i + 1);
147 			i += 4;
148 		} else {
149 			prev_mask = (prev_mask << 1) | 1;
150 		}
151 	}
152 
153 	prev_pos = i - prev_pos;
154 	s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1);
155 	return i;
156 }
157 #endif
158 
159 #ifdef XZ_DEC_POWERPC
160 static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
161 {
162 	size_t i;
163 	uint32_t instr;
164 
165 	for (i = 0; i + 4 <= size; i += 4) {
166 		instr = get_unaligned_be32(buf + i);
167 		if ((instr & 0xFC000003) == 0x48000001) {
168 			instr &= 0x03FFFFFC;
169 			instr -= s->pos + (uint32_t)i;
170 			instr &= 0x03FFFFFC;
171 			instr |= 0x48000001;
172 			put_unaligned_be32(instr, buf + i);
173 		}
174 	}
175 
176 	return i;
177 }
178 #endif
179 
180 #ifdef XZ_DEC_IA64
181 static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
182 {
183 	static const uint8_t branch_table[32] = {
184 		0, 0, 0, 0, 0, 0, 0, 0,
185 		0, 0, 0, 0, 0, 0, 0, 0,
186 		4, 4, 6, 6, 0, 0, 7, 7,
187 		4, 4, 0, 0, 4, 4, 0, 0
188 	};
189 
190 	/*
191 	 * The local variables take a little bit stack space, but it's less
192 	 * than what LZMA2 decoder takes, so it doesn't make sense to reduce
193 	 * stack usage here without doing that for the LZMA2 decoder too.
194 	 */
195 
196 	/* Loop counters */
197 	size_t i;
198 	size_t j;
199 
200 	/* Instruction slot (0, 1, or 2) in the 128-bit instruction word */
201 	uint32_t slot;
202 
203 	/* Bitwise offset of the instruction indicated by slot */
204 	uint32_t bit_pos;
205 
206 	/* bit_pos split into byte and bit parts */
207 	uint32_t byte_pos;
208 	uint32_t bit_res;
209 
210 	/* Address part of an instruction */
211 	uint32_t addr;
212 
213 	/* Mask used to detect which instructions to convert */
214 	uint32_t mask;
215 
216 	/* 41-bit instruction stored somewhere in the lowest 48 bits */
217 	uint64_t instr;
218 
219 	/* Instruction normalized with bit_res for easier manipulation */
220 	uint64_t norm;
221 
222 	for (i = 0; i + 16 <= size; i += 16) {
223 		mask = branch_table[buf[i] & 0x1F];
224 		for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) {
225 			if (((mask >> slot) & 1) == 0)
226 				continue;
227 
228 			byte_pos = bit_pos >> 3;
229 			bit_res = bit_pos & 7;
230 			instr = 0;
231 			for (j = 0; j < 6; ++j)
232 				instr |= (uint64_t)(buf[i + j + byte_pos])
233 						<< (8 * j);
234 
235 			norm = instr >> bit_res;
236 
237 			if (((norm >> 37) & 0x0F) == 0x05
238 					&& ((norm >> 9) & 0x07) == 0) {
239 				addr = (norm >> 13) & 0x0FFFFF;
240 				addr |= ((uint32_t)(norm >> 36) & 1) << 20;
241 				addr <<= 4;
242 				addr -= s->pos + (uint32_t)i;
243 				addr >>= 4;
244 
245 				norm &= ~((uint64_t)0x8FFFFF << 13);
246 				norm |= (uint64_t)(addr & 0x0FFFFF) << 13;
247 				norm |= (uint64_t)(addr & 0x100000)
248 						<< (36 - 20);
249 
250 				instr &= (1 << bit_res) - 1;
251 				instr |= norm << bit_res;
252 
253 				for (j = 0; j < 6; j++)
254 					buf[i + j + byte_pos]
255 						= (uint8_t)(instr >> (8 * j));
256 			}
257 		}
258 	}
259 
260 	return i;
261 }
262 #endif
263 
264 #ifdef XZ_DEC_ARM
265 static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
266 {
267 	size_t i;
268 	uint32_t addr;
269 
270 	for (i = 0; i + 4 <= size; i += 4) {
271 		if (buf[i + 3] == 0xEB) {
272 			addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8)
273 					| ((uint32_t)buf[i + 2] << 16);
274 			addr <<= 2;
275 			addr -= s->pos + (uint32_t)i + 8;
276 			addr >>= 2;
277 			buf[i] = (uint8_t)addr;
278 			buf[i + 1] = (uint8_t)(addr >> 8);
279 			buf[i + 2] = (uint8_t)(addr >> 16);
280 		}
281 	}
282 
283 	return i;
284 }
285 #endif
286 
287 #ifdef XZ_DEC_ARMTHUMB
288 static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
289 {
290 	size_t i;
291 	uint32_t addr;
292 
293 	for (i = 0; i + 4 <= size; i += 2) {
294 		if ((buf[i + 1] & 0xF8) == 0xF0
295 				&& (buf[i + 3] & 0xF8) == 0xF8) {
296 			addr = (((uint32_t)buf[i + 1] & 0x07) << 19)
297 					| ((uint32_t)buf[i] << 11)
298 					| (((uint32_t)buf[i + 3] & 0x07) << 8)
299 					| (uint32_t)buf[i + 2];
300 			addr <<= 1;
301 			addr -= s->pos + (uint32_t)i + 4;
302 			addr >>= 1;
303 			buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07));
304 			buf[i] = (uint8_t)(addr >> 11);
305 			buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07));
306 			buf[i + 2] = (uint8_t)addr;
307 			i += 2;
308 		}
309 	}
310 
311 	return i;
312 }
313 #endif
314 
315 #ifdef XZ_DEC_SPARC
316 static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
317 {
318 	size_t i;
319 	uint32_t instr;
320 
321 	for (i = 0; i + 4 <= size; i += 4) {
322 		instr = get_unaligned_be32(buf + i);
323 		if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) {
324 			instr <<= 2;
325 			instr -= s->pos + (uint32_t)i;
326 			instr >>= 2;
327 			instr = ((uint32_t)0x40000000 - (instr & 0x400000))
328 					| 0x40000000 | (instr & 0x3FFFFF);
329 			put_unaligned_be32(instr, buf + i);
330 		}
331 	}
332 
333 	return i;
334 }
335 #endif
336 
337 /*
338  * Apply the selected BCJ filter. Update *pos and s->pos to match the amount
339  * of data that got filtered.
340  *
341  * NOTE: This is implemented as a switch statement to avoid using function
342  * pointers, which could be problematic in the kernel boot code, which must
343  * avoid pointers to static data (at least on x86).
344  */
345 static void bcj_apply(struct xz_dec_bcj *s,
346 		      uint8_t *buf, size_t *pos, size_t size)
347 {
348 	size_t filtered;
349 
350 	buf += *pos;
351 	size -= *pos;
352 
353 	switch (s->type) {
354 #ifdef XZ_DEC_X86
355 	case BCJ_X86:
356 		filtered = bcj_x86(s, buf, size);
357 		break;
358 #endif
359 #ifdef XZ_DEC_POWERPC
360 	case BCJ_POWERPC:
361 		filtered = bcj_powerpc(s, buf, size);
362 		break;
363 #endif
364 #ifdef XZ_DEC_IA64
365 	case BCJ_IA64:
366 		filtered = bcj_ia64(s, buf, size);
367 		break;
368 #endif
369 #ifdef XZ_DEC_ARM
370 	case BCJ_ARM:
371 		filtered = bcj_arm(s, buf, size);
372 		break;
373 #endif
374 #ifdef XZ_DEC_ARMTHUMB
375 	case BCJ_ARMTHUMB:
376 		filtered = bcj_armthumb(s, buf, size);
377 		break;
378 #endif
379 #ifdef XZ_DEC_SPARC
380 	case BCJ_SPARC:
381 		filtered = bcj_sparc(s, buf, size);
382 		break;
383 #endif
384 	default:
385 		/* Never reached but silence compiler warnings. */
386 		filtered = 0;
387 		break;
388 	}
389 
390 	*pos += filtered;
391 	s->pos += filtered;
392 }
393 
394 /*
395  * Flush pending filtered data from temp to the output buffer.
396  * Move the remaining mixture of possibly filtered and unfiltered
397  * data to the beginning of temp.
398  */
399 static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b)
400 {
401 	size_t copy_size;
402 
403 	copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos);
404 	memcpy(b->out + b->out_pos, s->temp.buf, copy_size);
405 	b->out_pos += copy_size;
406 
407 	s->temp.filtered -= copy_size;
408 	s->temp.size -= copy_size;
409 	memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size);
410 }
411 
412 /*
413  * The BCJ filter functions are primitive in sense that they process the
414  * data in chunks of 1-16 bytes. To hide this issue, this function does
415  * some buffering.
416  */
417 XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
418 				     struct xz_dec_lzma2 *lzma2,
419 				     struct xz_buf *b)
420 {
421 	size_t out_start;
422 
423 	/*
424 	 * Flush pending already filtered data to the output buffer. Return
425 	 * immediatelly if we couldn't flush everything, or if the next
426 	 * filter in the chain had already returned XZ_STREAM_END.
427 	 */
428 	if (s->temp.filtered > 0) {
429 		bcj_flush(s, b);
430 		if (s->temp.filtered > 0)
431 			return XZ_OK;
432 
433 		if (s->ret == XZ_STREAM_END)
434 			return XZ_STREAM_END;
435 	}
436 
437 	/*
438 	 * If we have more output space than what is currently pending in
439 	 * temp, copy the unfiltered data from temp to the output buffer
440 	 * and try to fill the output buffer by decoding more data from the
441 	 * next filter in the chain. Apply the BCJ filter on the new data
442 	 * in the output buffer. If everything cannot be filtered, copy it
443 	 * to temp and rewind the output buffer position accordingly.
444 	 *
445 	 * This needs to be always run when temp.size == 0 to handle a special
446 	 * case where the output buffer is full and the next filter has no
447 	 * more output coming but hasn't returned XZ_STREAM_END yet.
448 	 */
449 	if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) {
450 		out_start = b->out_pos;
451 		memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
452 		b->out_pos += s->temp.size;
453 
454 		s->ret = xz_dec_lzma2_run(lzma2, b);
455 		if (s->ret != XZ_STREAM_END
456 				&& (s->ret != XZ_OK || s->single_call))
457 			return s->ret;
458 
459 		bcj_apply(s, b->out, &out_start, b->out_pos);
460 
461 		/*
462 		 * As an exception, if the next filter returned XZ_STREAM_END,
463 		 * we can do that too, since the last few bytes that remain
464 		 * unfiltered are meant to remain unfiltered.
465 		 */
466 		if (s->ret == XZ_STREAM_END)
467 			return XZ_STREAM_END;
468 
469 		s->temp.size = b->out_pos - out_start;
470 		b->out_pos -= s->temp.size;
471 		memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
472 
473 		/*
474 		 * If there wasn't enough input to the next filter to fill
475 		 * the output buffer with unfiltered data, there's no point
476 		 * to try decoding more data to temp.
477 		 */
478 		if (b->out_pos + s->temp.size < b->out_size)
479 			return XZ_OK;
480 	}
481 
482 	/*
483 	 * We have unfiltered data in temp. If the output buffer isn't full
484 	 * yet, try to fill the temp buffer by decoding more data from the
485 	 * next filter. Apply the BCJ filter on temp. Then we hopefully can
486 	 * fill the actual output buffer by copying filtered data from temp.
487 	 * A mix of filtered and unfiltered data may be left in temp; it will
488 	 * be taken care on the next call to this function.
489 	 */
490 	if (b->out_pos < b->out_size) {
491 		/* Make b->out{,_pos,_size} temporarily point to s->temp. */
492 		s->out = b->out;
493 		s->out_pos = b->out_pos;
494 		s->out_size = b->out_size;
495 		b->out = s->temp.buf;
496 		b->out_pos = s->temp.size;
497 		b->out_size = sizeof(s->temp.buf);
498 
499 		s->ret = xz_dec_lzma2_run(lzma2, b);
500 
501 		s->temp.size = b->out_pos;
502 		b->out = s->out;
503 		b->out_pos = s->out_pos;
504 		b->out_size = s->out_size;
505 
506 		if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
507 			return s->ret;
508 
509 		bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
510 
511 		/*
512 		 * If the next filter returned XZ_STREAM_END, we mark that
513 		 * everything is filtered, since the last unfiltered bytes
514 		 * of the stream are meant to be left as is.
515 		 */
516 		if (s->ret == XZ_STREAM_END)
517 			s->temp.filtered = s->temp.size;
518 
519 		bcj_flush(s, b);
520 		if (s->temp.filtered > 0)
521 			return XZ_OK;
522 	}
523 
524 	return s->ret;
525 }
526 
527 XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call)
528 {
529 	struct xz_dec_bcj *s = kmalloc(sizeof(*s), GFP_KERNEL);
530 	if (s != NULL)
531 		s->single_call = single_call;
532 
533 	return s;
534 }
535 
536 XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
537 {
538 	switch (id) {
539 #ifdef XZ_DEC_X86
540 	case BCJ_X86:
541 #endif
542 #ifdef XZ_DEC_POWERPC
543 	case BCJ_POWERPC:
544 #endif
545 #ifdef XZ_DEC_IA64
546 	case BCJ_IA64:
547 #endif
548 #ifdef XZ_DEC_ARM
549 	case BCJ_ARM:
550 #endif
551 #ifdef XZ_DEC_ARMTHUMB
552 	case BCJ_ARMTHUMB:
553 #endif
554 #ifdef XZ_DEC_SPARC
555 	case BCJ_SPARC:
556 #endif
557 		break;
558 
559 	default:
560 		/* Unsupported Filter ID */
561 		return XZ_OPTIONS_ERROR;
562 	}
563 
564 	s->type = id;
565 	s->ret = XZ_OK;
566 	s->pos = 0;
567 	s->x86_prev_mask = 0;
568 	s->temp.filtered = 0;
569 	s->temp.size = 0;
570 
571 	return XZ_OK;
572 }
573 
574 #endif
575