Matt Kowalczyk said:
Hello,
I am working on a compression project and I want to write ASCII characters
using
the minimum amount of bits. Since I will be writing ASCII characters from
0-127
I only need 7 bits to represent a character. Therefore, if I write each
character at a time, I will end up writing 8 bits.
One method would be to somehow concatinate all the 7 bit words I am trying
to write and just pad the last byte.
e.g. Read the first 7-bit word, concatinate a bit from the next word and
write
the byte. Concat two bits from the next word and write the byte, e.g.
until I'm finished.
A few years ago, a guy on sci.crypt defended his use of gcc extensions on
the grounds that his desire to use 19-bit integers could not be met in ISO
C. Naturally enough, then, I spent a few minutes cutting some ISO C code
that would let him do just that. (It's a bit of a hack, as you'll see in a
moment, but it should work fine on a C8S16IL32 system, which is almost
certainly what you're using.)
It occurs to me that you could easily adapt it to your purposes. Set up a
buffer - an array of unsigned char - that is at least (N + 6) / 7 bytes in
size where N is the number of ASCII characters you want to crunch down, and
write to it using Put_nBit_Int. Once you've finished, the array of unsigned
char holds your "packed" data (and possibly some spare space, so you should
beware of that - maybe retain (binary) 0000000 as a terminator). You can
store or send that. At the receiving end, use Get_nBit_Int to retrieve the
crunched bytes.
The main() function at the bottom should give you a rough idea of how to use
the nbit functions.
You are welcome to use what follows, without payment, provided you credit me
in the source code.
#include <stdio.h>
#include <limits.h>
#define SET_BIT(a, n) (a)[(n) / CHAR_BIT] |= \
(unsigned char)(1U << ((n) % CHAR_BIT))
#define CLEAR_BIT(a, n) (a)[(n) / CHAR_BIT] &= \
(unsigned char)(~(1U << ((n) % CHAR_BIT)))
#define TEST_BIT(a, n) (((a)[(n) / CHAR_BIT] & \
(unsigned char)(1U << ((n) % CHAR_BIT))) ? 1 : 0)
/* Debugging function, used for printing len * CHAR_BIT
* bits from s.
*/
int print_bits(unsigned char *s, int len)
{
int i, j;
for(i = 0; i < len; i++)
{
for(j = 0; j < CHAR_BIT; j++)
{
printf("%d", TEST_BIT(s, i * CHAR_BIT + j) ? 1 : 0);
}
printf(" ");
}
printf("\n");
return 0;
}
unsigned int BitsInUnsignedInt(void)
{
static unsigned int answer = 0;
unsigned int testval = UINT_MAX;
if(answer == 0)
{
while(testval > 0)
{
++answer;
testval >>= 1;
}
}
return answer;
}
/* This function gets the Indexth n-bit unsigned int field from the bit
* array. To do this, it builds the unsigned int value bit by bit.
*
* Example call:
*
* unsigned int val;
* val = Get_nBit_Int(MyBitArray, this is the base address
* 19, get a 19-bit number
* 13, get the 14th number (0 to max - 1)
* 7); skip 7 leading bits at the start of
the array
*
*/
unsigned int Get_nBit_Int(unsigned char *BitArray,
unsigned int n,
unsigned int Index,
unsigned int BaseBit)
{
unsigned int Value = 0;
unsigned int j;
unsigned int i = Index * n;
if(n <= BitsInUnsignedInt())
{
i += BaseBit;
BitArray += i / CHAR_BIT;
i %= CHAR_BIT;
for(j = 0; j < n; j++)
{
/* Move the populated bits out of the way.
* Yes, this means that the first iteration
* of the loop does a useless shift. I think
* I can live with that.
*/
Value <<= 1;
/* Populate the low bit */
Value |= TEST_BIT(BitArray, i + j);
}
}
return Value;
}
void Put_nBit_Int(unsigned char *BitArray,
unsigned int n,
unsigned int Index,
unsigned int BaseBit,
unsigned int Value)
{
unsigned int j;
unsigned int i = Index * n;
if(n <= 32)
{
i += BaseBit;
BitArray += i / CHAR_BIT;
i %= CHAR_BIT;
j = n;
while(j--)
{
/* Use the rightmost bit */
if(Value & 1)
{
SET_BIT(BitArray, i + j);
}
else
{
CLEAR_BIT(BitArray, i + j);
}
/* Throw the rightmost bit away, moving the next bit into
* position. On the last iteration of the loop, this
* instruction is pointless. <shrug>
*/
Value >>= 1;
}
}
}
int main(void)
{
unsigned char test_array[9] = {0};
print_bits(test_array, 9);
printf("Storing the 19-bit value 0x7FFFF starting at bit 3.\n");
Put_nBit_Int(test_array, 19, 0, 3, 0x7FFFF);
print_bits(test_array, 9);
printf("Retrieving the 19-bit value starting at bit 3: %X\n",
Get_nBit_Int(test_array, 19, 0, 3));
printf("Storing the 19-bit value 0x7EDCB starting at bit 3 + (2 *
19).\n");
Put_nBit_Int(test_array, 19, 2, 3, 0x7EDCB);
print_bits(test_array, 9);
printf("Retrieving the 19-bit value starting at bit 3 + (2 * 19): %X\n",
Get_nBit_Int(test_array, 19, 2, 3));
return 0;
}
