| 1 |
/* This file is part of libmspack. |
| 2 |
* (C) 2003-2010 Stuart Caie. |
| 3 |
* |
| 4 |
* libmspack is free software; you can redistribute it and/or modify it under |
| 5 |
* the terms of the GNU Lesser General Public License (LGPL) version 2.1 |
| 6 |
* |
| 7 |
* For further details, see the file COPYING.LIB distributed with libmspack |
| 8 |
*/ |
| 9 |
|
| 10 |
#ifndef READBITS_H |
| 11 |
#define READBITS_H 1 |
| 12 |
|
| 13 |
/* this header defines macros that read data streams by |
| 14 |
* the individual bits |
| 15 |
* |
| 16 |
* INIT_BITS initialises bitstream state in state structure |
| 17 |
* STORE_BITS stores bitstream state in state structure |
| 18 |
* RESTORE_BITS restores bitstream state from state structure |
| 19 |
* ENSURE_BITS(n) ensure there are at least N bits in the bit buffer |
| 20 |
* READ_BITS(var,n) takes N bits from the buffer and puts them in var |
| 21 |
* PEEK_BITS(n) extracts without removing N bits from the bit buffer |
| 22 |
* REMOVE_BITS(n) removes N bits from the bit buffer |
| 23 |
* |
| 24 |
* READ_BITS simply calls ENSURE_BITS, PEEK_BITS and REMOVE_BITS, |
| 25 |
* which means it's limited to reading the number of bits you can |
| 26 |
* ensure at any one time. It also fails if asked to read zero bits. |
| 27 |
* If you need to read zero bits, or more bits than can be ensured in |
| 28 |
* one go, use READ_MANY_BITS instead. |
| 29 |
* |
| 30 |
* These macros have variable names baked into them, so to use them |
| 31 |
* you have to define some macros: |
| 32 |
* - BITS_TYPE: the type name of your state structure |
| 33 |
* - BITS_VAR: the variable that points to your state structure |
| 34 |
* - define BITS_ORDER_MSB if bits are read from the MSB, or |
| 35 |
* define BITS_ORDER_LSB if bits are read from the LSB |
| 36 |
* - READ_BYTES: some code that reads more data into the bit buffer, |
| 37 |
* it should use READ_IF_NEEDED (calls read_input if the byte buffer |
| 38 |
* is empty), then INJECT_BITS(data,n) to put data from the byte |
| 39 |
* buffer into the bit buffer. |
| 40 |
* |
| 41 |
* You also need to define some variables and structure members: |
| 42 |
* - unsigned char *i_ptr; // current position in the byte buffer |
| 43 |
* - unsigned char *i_end; // end of the byte buffer |
| 44 |
* - unsigned int bit_buffer; // the bit buffer itself |
| 45 |
* - unsigned int bits_left; // number of bits remaining |
| 46 |
* |
| 47 |
* If you use read_input() and READ_IF_NEEDED, they also expect these |
| 48 |
* structure members: |
| 49 |
* - unsigned int error; // to record/return read errors |
| 50 |
* - unsigned char input_end; // to mark reaching the EOF |
| 51 |
* - unsigned char *inbuf; // the input byte buffer |
| 52 |
* - unsigned int inbuf_size; // the size of the input byte buffer |
| 53 |
* |
| 54 |
* Your READ_BYTES implementation should read data from *i_ptr and |
| 55 |
* put them in the bit buffer. READ_IF_NEEDED will call read_input() |
| 56 |
* if i_ptr reaches i_end, and will fill up inbuf and set i_ptr to |
| 57 |
* the start of inbuf and i_end to the end of inbuf. |
| 58 |
* |
| 59 |
* If you're reading in MSB order, the routines work by using the area |
| 60 |
* beyond the MSB and the LSB of the bit buffer as a free source of |
| 61 |
* zeroes when shifting. This avoids having to mask any bits. So we |
| 62 |
* have to know the bit width of the bit buffer variable. We use |
| 63 |
* <limits.h> and CHAR_BIT to find the size of the bit buffer in bits. |
| 64 |
* |
| 65 |
* If you are reading in LSB order, bits need to be masked. Normally |
| 66 |
* this is done by computing the mask: N bits are masked by the value |
| 67 |
* (1<<N)-1). However, you can define BITS_LSB_TABLE to use a lookup |
| 68 |
* table instead of computing this. This adds two new macros, |
| 69 |
* PEEK_BITS_T and READ_BITS_T which work the same way as PEEK_BITS |
| 70 |
* and READ_BITS, except they use this lookup table. This is useful if |
| 71 |
* you need to look up a number of bits that are only known at |
| 72 |
* runtime, so the bit mask can't be turned into a constant by the |
| 73 |
* compiler. |
| 74 |
|
| 75 |
* The bit buffer datatype should be at least 32 bits wide: it must be |
| 76 |
* possible to ENSURE_BITS(17), so it must be possible to add 16 new bits |
| 77 |
* to the bit buffer when the bit buffer already has 1 to 15 bits left. |
| 78 |
*/ |
| 79 |
|
| 80 |
#ifndef BITS_VAR |
| 81 |
# error "define BITS_VAR as the state structure poiner variable name" |
| 82 |
#endif |
| 83 |
#ifndef BITS_TYPE |
| 84 |
# error "define BITS_TYPE as the state structure type" |
| 85 |
#endif |
| 86 |
#if defined(BITS_ORDER_MSB) && defined(BITS_ORDER_LSB) |
| 87 |
# error "you must define either BITS_ORDER_MSB or BITS_ORDER_LSB" |
| 88 |
#else |
| 89 |
# if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB)) |
| 90 |
# error "you must define BITS_ORDER_MSB or BITS_ORDER_LSB" |
| 91 |
# endif |
| 92 |
#endif |
| 93 |
|
| 94 |
# include <limits.h> |
| 95 |
|
| 96 |
#define BITBUF_WIDTH (sizeof(bit_buffer) * CHAR_BIT) |
| 97 |
|
| 98 |
#define INIT_BITS do { \ |
| 99 |
BITS_VAR->i_ptr = &BITS_VAR->inbuf[0]; \ |
| 100 |
BITS_VAR->i_end = &BITS_VAR->inbuf[0]; \ |
| 101 |
BITS_VAR->bit_buffer = 0; \ |
| 102 |
BITS_VAR->bits_left = 0; \ |
| 103 |
BITS_VAR->input_end = 0; \ |
| 104 |
} while (0) |
| 105 |
|
| 106 |
#define STORE_BITS do { \ |
| 107 |
BITS_VAR->i_ptr = i_ptr; \ |
| 108 |
BITS_VAR->i_end = i_end; \ |
| 109 |
BITS_VAR->bit_buffer = bit_buffer; \ |
| 110 |
BITS_VAR->bits_left = bits_left; \ |
| 111 |
} while (0) |
| 112 |
|
| 113 |
#define RESTORE_BITS do { \ |
| 114 |
i_ptr = BITS_VAR->i_ptr; \ |
| 115 |
i_end = BITS_VAR->i_end; \ |
| 116 |
bit_buffer = BITS_VAR->bit_buffer; \ |
| 117 |
bits_left = BITS_VAR->bits_left; \ |
| 118 |
} while (0) |
| 119 |
|
| 120 |
#define ENSURE_BITS(nbits) do { \ |
| 121 |
while (bits_left < (nbits)) READ_BYTES; \ |
| 122 |
} while (0) |
| 123 |
|
| 124 |
#define READ_BITS(val, nbits) do { \ |
| 125 |
ENSURE_BITS(nbits); \ |
| 126 |
(val) = PEEK_BITS(nbits); \ |
| 127 |
REMOVE_BITS(nbits); \ |
| 128 |
} while (0) |
| 129 |
|
| 130 |
#define READ_MANY_BITS(val, bits) do { \ |
| 131 |
unsigned char needed = (bits), bitrun; \ |
| 132 |
(val) = 0; \ |
| 133 |
while (needed > 0) { \ |
| 134 |
if (bits_left <= (BITBUF_WIDTH - 16)) READ_BYTES; \ |
| 135 |
bitrun = (bits_left < needed) ? bits_left : needed; \ |
| 136 |
(val) = ((val) << bitrun) | PEEK_BITS(bitrun); \ |
| 137 |
REMOVE_BITS(bitrun); \ |
| 138 |
needed -= bitrun; \ |
| 139 |
} \ |
| 140 |
} while (0) |
| 141 |
|
| 142 |
#ifdef BITS_ORDER_MSB |
| 143 |
# define PEEK_BITS(nbits) (bit_buffer >> (BITBUF_WIDTH - (nbits))) |
| 144 |
# define REMOVE_BITS(nbits) ((bit_buffer <<= (nbits)), (bits_left -= (nbits))) |
| 145 |
# define INJECT_BITS(bitdata,nbits) ((bit_buffer |= \ |
| 146 |
(bitdata) << (BITBUF_WIDTH - (nbits) - bits_left)), (bits_left += (nbits))) |
| 147 |
#else /* BITS_ORDER_LSB */ |
| 148 |
# define PEEK_BITS(nbits) (bit_buffer & ((1 << (nbits))-1)) |
| 149 |
# define REMOVE_BITS(nbits) ((bit_buffer >>= (nbits)), (bits_left -= (nbits))) |
| 150 |
# define INJECT_BITS(bitdata,nbits) ((bit_buffer |= \ |
| 151 |
(bitdata) << bits_left), (bits_left += (nbits))) |
| 152 |
#endif |
| 153 |
|
| 154 |
#ifdef BITS_LSB_TABLE |
| 155 |
/* lsb_bit_mask[n] = (1 << n) - 1 */ |
| 156 |
static const unsigned short lsb_bit_mask[17] = { |
| 157 |
0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, |
| 158 |
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff |
| 159 |
}; |
| 160 |
# define PEEK_BITS_T(nbits) (bit_buffer & lsb_bit_mask[(nbits)]) |
| 161 |
# define READ_BITS_T(val, nbits) do { \ |
| 162 |
ENSURE_BITS(nbits); \ |
| 163 |
(val) = PEEK_BITS_T(nbits); \ |
| 164 |
REMOVE_BITS(nbits); \ |
| 165 |
} while (0) |
| 166 |
#endif |
| 167 |
|
| 168 |
#ifndef BITS_NO_READ_INPUT |
| 169 |
# define READ_IF_NEEDED do { \ |
| 170 |
if (i_ptr >= i_end) { \ |
| 171 |
if (read_input(BITS_VAR)) \ |
| 172 |
return BITS_VAR->error; \ |
| 173 |
i_ptr = BITS_VAR->i_ptr; \ |
| 174 |
i_end = BITS_VAR->i_end; \ |
| 175 |
} \ |
| 176 |
} while (0) |
| 177 |
|
| 178 |
static int read_input(BITS_TYPE *p) { |
| 179 |
int read = fread(p->inbuf, 1, (int)p->inbuf_size, p->input); |
| 180 |
if (read < 0) return p->error = LZX_ERR_READ; |
| 181 |
|
| 182 |
/* we might overrun the input stream by asking for bits we don't use, |
| 183 |
* so fake 2 more bytes at the end of input */ |
| 184 |
if (read == 0) { |
| 185 |
if (p->input_end) { |
| 186 |
D(("out of input bytes")) |
| 187 |
return p->error = LZX_ERR_READ; |
| 188 |
} |
| 189 |
else { |
| 190 |
read = 2; |
| 191 |
p->inbuf[0] = p->inbuf[1] = 0; |
| 192 |
p->input_end = 1; |
| 193 |
} |
| 194 |
} |
| 195 |
|
| 196 |
/* update i_ptr and i_end */ |
| 197 |
p->i_ptr = &p->inbuf[0]; |
| 198 |
p->i_end = &p->inbuf[read]; |
| 199 |
return LZX_ERR_OK; |
| 200 |
} |
| 201 |
#endif |
| 202 |
#endif |