Bit Manipulation

Discussion in 'C Programming' started by Allan Bruce, Oct 10, 2003.

  1. Allan Bruce

    Allan Bruce Guest

    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
    Allan Bruce, Oct 10, 2003
    #1
    1. Advertising

  2. "Allan Bruce" <> wrote in message
    news:bm5vh0$93v$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
    Ivan Vecerina, Oct 10, 2003
    #2
    1. Advertising

  3. Allan Bruce

    Allan Bruce Guest

    "Ivan Vecerina" <NONE_use_form@website_to_contact_me> wrote in message
    news:3f868cca$...
    > "Allan Bruce" <> wrote in message
    > news:bm5vh0$93v$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)lByte, 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 BitPatternLength-1. Is this ok? Or is there a
    better way to do it?
    Thanks
    Allan
    Allan Bruce, Oct 10, 2003
    #3
  4. Allan Bruce

    pete Guest

    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_centric.

    #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
    pete, Oct 10, 2003
    #4
  5. "Allan Bruce" <> wrote in message
    news:bm63cb$aqf$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(unsigned long newbits, int bitCount)
    {
    while(bitCount>0) {
    unsigned nbits = bitCount;
    if( nbits>freeBits ) nbits = freeBits;
    freeBits -= nbits;
    bitCount -= nbits;
    cur = (cur<<nbits)|(newbits>>bitCount);
    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)lByte, 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 BitPatternLength-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
    Ivan Vecerina, Oct 10, 2003
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    8
    Views:
    34,262
    Luc The Perverse
    Nov 26, 2005
  2. Chris \( Val \)

    Re: Bit manipulation

    Chris \( Val \), Jun 26, 2003, in forum: C++
    Replies:
    0
    Views:
    812
    Chris \( Val \)
    Jun 26, 2003
  3. Replies:
    3
    Views:
    1,720
    Timothy Bendfelt
    Jan 19, 2007
  4. Replies:
    9
    Views:
    941
    Juha Nieminen
    Aug 22, 2007
  5. Jeff.M
    Replies:
    6
    Views:
    163
    Lasse Reichstein Nielsen
    May 4, 2009
Loading...

Share This Page