source: src/linux/universal/linux-3.5/lib/xz/xz_dec_bcj.c @ 31672

Last change on this file since 31672 was 31672, checked in by brainslayer, 5 months ago

fix fs detection

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