Bit Manipulation

[Allan Bruce]

Hi there,

Would the following functions work for bit manipulation? I want to specify
a byte and the bit of the byte (from the MSB down to LSB) and either set it,
clear it or get what it is currently at.
Thanks
Allan

void BitSet(unsigned char *Byte, int Bit)
{
unsigned char Mask = 0x80; // all zeros with a 1 at the MSB

if (Bit>7 || Byte==NULL)
return;

Mask = Mask >> Bit;
*Byte = *Byte | Mask;
}

void BitClr(unsigned char *Byte, int Bit)
{
unsigned char Mask = 0x80; // all zeros with a 1 at the MSB

if (Bit>7 || Byte==NULL)
return;

Mask = ~(Mask >> Bit);
*Byte = *Byte & Mask;
}

int BitGet(unsigned char *Byte, int Bit)
{
unsigned char Mask = 0x80; // all zeros with a 1 at the MSB

if (Bit>7 || Byte==NULL)
return;

Mask = Mask >> Bit;
if ((*Byte & Mask) == Mask)
return 1;
else
return 0;
}

--
Allan Bruce
Dept. of Computing Science
University of Aberdeen
Aberdeen AB24 3UE
Scotland, UK

[Ivan Vecerina]

"Allan Bruce" <al*****@TAKEAW AYf2s.com> wrote in message
news:bm******** **@news.freedom 2surf.net...
| Would the following functions work for bit manipulation?
....
| void BitSet(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
Ok if you want to number 0 as the most significant bit,
and 7 as the least significant. This is not the usual
convention I have seen in C: people usually think
in terms of ( 1<<bitPos ).

| if (Bit>7 || Byte==NULL)
| return;
|
| Mask = Mask >> Bit;
| *Byte = *Byte | Mask;

Ok. Note that you could write:
*Byte |= Mask; // but it's a matter of taste...
| }
|
| void BitClr(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
|
| if (Bit>7 || Byte==NULL)
| return;
|
| Mask = ~(Mask >> Bit);
| *Byte = *Byte & Mask;
| }
|
| int BitGet(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
|
| if (Bit>7 || Byte==NULL)
| return;
Error: you need to specify a return value here...

| Mask = Mask >> Bit;
| if ((*Byte & Mask) == Mask)
| return 1;
| else
| return 0;
Ok. But note that the last 4 lines are equivalent to:
return ( (*Byte & Mask)==Mask );
Or:
return ( *Byte & Mask ) ? 1 : 0;
| }
But all in all, your code is mostly ok.

Regards,
Ivan
--
http://ivan.vecerina.com

[Allan Bruce]

"Ivan Vecerina" <NONE_use_form@ website_to_cont act_me> wrote in message
news:3f******** @news.swissonli ne.ch...

"Allan Bruce" <al*****@TAKEAW AYf2s.com> wrote in message
news:bm******** **@news.freedom 2surf.net...
| Would the following functions work for bit manipulation?
...
| void BitSet(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
Ok if you want to number 0 as the most significant bit,
and 7 as the least significant. This is not the usual
convention I have seen in C: people usually think
in terms of ( 1<<bitPos ).

| if (Bit>7 || Byte==NULL)
| return;
|
| Mask = Mask >> Bit;
| *Byte = *Byte | Mask;

Ok. Note that you could write:
*Byte |= Mask; // but it's a matter of taste...
| }
|
| void BitClr(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
|
| if (Bit>7 || Byte==NULL)
| return;
|
| Mask = ~(Mask >> Bit);
| *Byte = *Byte & Mask;
| }
|
| int BitGet(unsigned char *Byte, int Bit)
| {
| unsigned char Mask = 0x80; // all zeros with a 1 at the MSB
|
| if (Bit>7 || Byte==NULL)
| return;
Error: you need to specify a return value here...

| Mask = Mask >> Bit;
| if ((*Byte & Mask) == Mask)
| return 1;
| else
| return 0;
Ok. But note that the last 4 lines are equivalent to:
return ( (*Byte & Mask)==Mask );
Or:
return ( *Byte & Mask ) ? 1 : 0;
| }
But all in all, your code is mostly ok.

Regards,
Ivan

Thanks.

I am making a basic huffman coding program, which reads in all the bytes of
a file, sorts them by the frequency they appear in the file, then pairs the
lowest frequencies to produce a kind of tree.
When I pair them up, I am creating a binary code which adds a 1 at the
beginning if the node was the highest of the pair, otherwise it adds a 0 at
the beginning. It is this part that I have reversed so the code bits are
added at the end of the bit patters, but this will be reversed when
outputting to file.
Has anybody coded a basic huffman compression scheme? It would be
interesting to see how they write the info to file, since I have variable
length bit patterns (potentially 2 -> 255 bits). What I am doing is reading
each bit then adding it to the following function:

void Bytify(int xiBit) // takes bits in and once a full byte is recieved,
writes to file
{
static unsigned char lPosition = 0x80;
static unsigned char lByte = 0x0;

if (xiBit) // if the xi bit is set
lByte = lByte | lPosition; // then add it to the char

lPosition = lPosition >> 1; // next position for next time round

if (lPosition == 0x0) // if we are on the last position
{
fputc((int)lByt e, fptr); // write byte to file
lPosition = 0x80; // and reset the postion and the new byte
lByte = 0x0;
}
}
One last thing, if I have the length of the bit field, I am using this to
find out the byte containing the bit, and the bit within that byte:

lBitPosition = loop%8;
lCharPosition = (loop - lBitPosition) / 8;

Where loop is going from 0 to BitPatternLengt h-1. Is this ok? Or is there a
better way to do it?
Thanks
Allan

[pete]

Allan Bruce wrote:

Hi there,

Would the following functions work for bit manipulation?
I want to specify a byte and the bit of the byte
(from the MSB down to LSB) and either set it,
clear it or get what it is currently at. void BitSet(unsigned char *Byte, int Bit)
{
unsigned char Mask = 0x80; // all zeros with a 1 at the MSB

if (Bit>7 || Byte==NULL)
return;

Mask = Mask >> Bit;
*Byte = *Byte | Mask;
}

It's OK, except that it's eight_bit_centr ic.

#include <stdio.h>
#include <limits.h>

void BitSet(unsigned char *Byte, int Bit)
{
if (Bit > CHAR_BIT - 1 || Byte == NULL) {
return;
}
*Byte |= (((unsigned char)-1 >> 1) + 1) >> Bit;
}

--
pete

[Ivan Vecerina]

"Allan Bruce" <al*****@TAKEAW AYf2s.com> wrote in message
news:bm******** **@news.freedom 2surf.net...
| Has anybody coded a basic huffman compression scheme? It would be
| interesting to see how they write the info to file, since I have variable
| length bit patterns (potentially 2 -> 255 bits).
Well, it's been a long long time for me.
The approach I would take is more or less:

static unsigned char cur=0;
static int freeBits = 8; // # of available bits in *dst

void bitsWriter(unsi gned long newbits, int bitCount)
{
while(bitCount> 0) {
unsigned nbits = bitCount;
if( nbits>freeBits ) nbits = freeBits;
freeBits -= nbits;
bitCount -= nbits;
cur = (cur<<nbits)|(n ewbits>>bitCoun t);
if( freeBits==0 ) { // byte is complete
fputc((int)cur, fptr);
freeBits = 8;
}
}
}
//NB: a flush function needs to be added

Data bits are passed in 'newbits', first bit in MSB,
and last bit aligned on bit zero.
If a huffman code takes more than 32 bits, it will
need to be written using multiple calls.

The buffer 'cur' could be of type unsigned long (e.g. 32 bits)
if you are careful with endianess issues.

| What I am doing is reading
| each bit then adding it to the following function:
|
| void Bytify(int xiBit) // takes bits in and once a full byte is
recieved,
| writes to file
| {
| static unsigned char lPosition = 0x80;
| static unsigned char lByte = 0x0;
|
| if (xiBit) // if the xi bit is set
| lByte = lByte | lPosition; // then add it to the char
|
| lPosition = lPosition >> 1; // next position for next time round
|
| if (lPosition == 0x0) // if we are on the last position
| {
| fputc((int)lByt e, fptr); // write byte to file
| lPosition = 0x80; // and reset the postion and the new byte
| lByte = 0x0;
| }
| }
Seems correct.
Might be slower as the function is called for each bit.

| One last thing, if I have the length of the bit field, I am using this to
| find out the byte containing the bit, and the bit within that byte:
|
| lBitPosition = loop%8;
| lCharPosition = (loop - lBitPosition) / 8;
Ok if 'loop' is positive, but the ' - lBitPosition ' part is unnecessary.
In C, integer divide will automatically round down the value.
So: lCharPosition = loop/8;

| Where loop is going from 0 to BitPatternLengt h-1.
| Is this ok? Or is there a better way to do it?
I would store and transmit the Huffman code word by word,
for efficiency reasons:

void sendCode( //NB: assuming 32-bit longs
int bitLen,
unsigned long codeBuf[32]) // 8*32 = 256 bits
{
while(bitLen>32 ) {
bitsWriter( codeBuf, 32);
++codeBuf;
bitLen-=32;
}
bitsWriter( codeBuf, bitLen ); // last (incomplete) word
}

But your code was correct. It is better to first write your encoder
in a way that you can easily understand, and then to look into
performance improvements...
Regards,
Ivan
--
http://ivan.vecerina.com