archival/libunarchive/rangecoder.h

   1 /*
   2  * Small range coder implementation for lzma.
   3  * Copyright (C) 2006  Aurelien Jacobs <aurel@gnuage.org>
   4  *
   5  * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
   6  * Copyright (c) 1999-2005  Igor Pavlov
   7  *
   8  * This program is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21  */
  22
  23 #include <stdint.h>
  24
  25 #include "libbb.h"
  26
  27 #ifndef always_inline
  28 #  if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >0)
  29 #    define always_inline __attribute__((always_inline)) inline
  30 #  else
  31 #    define always_inline inline
  32 #  endif
  33 #endif
  34
  35 #ifdef CONFIG_FEATURE_LZMA_FAST
  36 #  define speed_inline always_inline
  37 #else
  38 #  define speed_inline
  39 #endif
  40
  41
  42 typedef struct {
  43         int fd;
  44         uint8_t *ptr;
  45         uint8_t *buffer;
  46         uint8_t *buffer_end;
  47         int buffer_size;
  48         uint32_t code;
  49         uint32_t range;
  50         uint32_t bound;
  51 } rc_t;
  52
  53
  54 #define RC_TOP_BITS 24
  55 #define RC_MOVE_BITS 5
  56 #define RC_MODEL_TOTAL_BITS 11
  57
  58
  59 static speed_inline void rc_read(rc_t * rc)
  60 {
  61         rc->buffer_size = read(rc->fd, rc->buffer, rc->buffer_size);
  62         if (rc->buffer_size <= 0)
  63                 bb_error_msg_and_die("unexpected EOF");
  64         rc->ptr = rc->buffer;
  65         rc->buffer_end = rc->buffer + rc->buffer_size;
  66 }
  67
  68 static always_inline void rc_init(rc_t * rc, int fd, int buffer_size)
  69 {
  70         int i;
  71
  72         rc->fd = fd;
  73         rc->buffer = malloc(buffer_size);
  74         rc->buffer_size = buffer_size;
  75         rc->buffer_end = rc->buffer + rc->buffer_size;
  76         rc->ptr = rc->buffer_end;
  77
  78         rc->code = 0;
  79         rc->range = 0xFFFFFFFF;
  80         for (i = 0; i < 5; i++) {
  81                 if (rc->ptr >= rc->buffer_end)
  82                         rc_read(rc);
  83                 rc->code = (rc->code << 8) | *rc->ptr++;
  84         }
  85 }
  86
  87 static always_inline void rc_free(rc_t * rc)
  88 {
  89         if (ENABLE_FEATURE_CLEAN_UP)
  90                 free(rc->buffer);
  91 }
  92
  93 static always_inline void rc_normalize(rc_t * rc)
  94 {
  95         if (rc->range < (1 << RC_TOP_BITS)) {
  96                 if (rc->ptr >= rc->buffer_end)
  97                         rc_read(rc);
  98                 rc->range <<= 8;
  99                 rc->code = (rc->code << 8) | *rc->ptr++;
 100         }
 101 }
 102
 103 static speed_inline int rc_is_bit_0(rc_t * rc, uint16_t * p)
 104 {
 105         rc_normalize(rc);
 106         rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
 107         return rc->code < rc->bound;
 108 }
 109
 110 static speed_inline void rc_update_bit_0(rc_t * rc, uint16_t * p)
 111 {
 112         rc->range = rc->bound;
 113         *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
 114 }
 115
 116 static speed_inline void rc_update_bit_1(rc_t * rc, uint16_t * p)
 117 {
 118         rc->range -= rc->bound;
 119         rc->code -= rc->bound;
 120         *p -= *p >> RC_MOVE_BITS;
 121 }
 122
 123 static speed_inline int rc_get_bit(rc_t * rc, uint16_t * p, int *symbol)
 124 {
 125         if (rc_is_bit_0(rc, p)) {
 126                 rc_update_bit_0(rc, p);
 127                 *symbol *= 2;
 128                 return 0;
 129         } else {
 130                 rc_update_bit_1(rc, p);
 131                 *symbol = *symbol * 2 + 1;
 132                 return 1;
 133         }
 134 }
 135
 136 static always_inline int rc_direct_bit(rc_t * rc)
 137 {
 138         rc_normalize(rc);
 139         rc->range >>= 1;
 140         if (rc->code >= rc->range) {
 141                 rc->code -= rc->range;
 142                 return 1;
 143         }
 144         return 0;
 145 }
 146
 147 static speed_inline void
 148 rc_bit_tree_decode(rc_t * rc, uint16_t * p, int num_levels, int *symbol)
 149 {
 150         int i = num_levels;
 151
 152         *symbol = 1;
 153         while (i--)
 154                 rc_get_bit(rc, p + *symbol, symbol);
 155         *symbol -= 1 << num_levels;
 156 }
 157
 158 /* vi:set ts=4: */