OSCL-LXR linux-6.0.1/​lib/​xz/​xz_dec_bcj.c	Source navigation Diff markup Identifier search General search
	Version: linux-6.0.1 spark-3.0.0 hadoop-3.2.0-src hadoop-3.3.0-src spark-2.4.7 linux-4.15.13 hadoop-2.7.4-src Revert   Change

 /*
  * Branch/Call/Jump (BCJ) filter decoders
  *
  * Authors: Lasse Collin <lasse.collin@tukaani.org>
  *          Igor Pavlov <https://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
      * immediately 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

This page was automatically generated by the 2.1.0 LXR engine. The LXR team