linux/lib/xz/xz_dec_bcj.c
<<
>>
Prefs
   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_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 */
  83static inline int bcj_x86_test_msbyte(uint8_t b)
  84{
  85        return b == 0x00 || b == 0xFF;
  86}
  87
  88static 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
 160static 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
 181static 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
 265static 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
 288static 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
 316static 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 */
 345static 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 */
 399static 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 */
 417XZ_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
 527XZ_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
 536XZ_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