Like Tree6Likes
  • 1 Post By Salem
  • 1 Post By Nominal Animal
  • 1 Post By iMalc
  • 1 Post By Nominal Animal
  • 1 Post By Nominal Animal
  • 1 Post By Nominal Animal

Help with Bitwise fragmentation in a structure??

This is a discussion on Help with Bitwise fragmentation in a structure?? within the C Programming forums, part of the General Programming Boards category; Hello Folks, I have this structure Code: typedef struct { char transLen; unsigned short transType; // 8bit unsigned short Pparity; ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    35

    Help with Bitwise fragmentation in a structure??

    Hello Folks,

    I have this structure
    Code:
    typedef struct {
       char transLen;
       unsigned short transType; // 8bit
        unsigned short Pparity;
    } Buf;
    Need your advices .. I need the variable transType to be accessed BITWISE manner in an efficient way. I need all the bits in transType as an individual variables as i will be accessing them very often n later set the PARITY (even or odd) in the Pparity variable for the transType as a whole(parity for the 8 bits). I would also set the parity for the tranLen too in Pparity.

    Here are my approaches



    Approach 1 :

    including the structure like below into Buf instead of transTyp n access indivdual bits
    Code:
    struct portie {
    
        unsigned int autfd   : 1;
    
        unsigned int bldfc   : 1;
    
        unsigned int undln   : 1;
    
        unsigned int itals   : 1;
       
        unsigned int cal: 1;
    
        unsigned int jal   : 1;
    
        unsigned int mal   : 1;
    
        unsigned int pal   : 1;
    
    } ;
    Approach 2:

    Using bitwise operators change the bits of transType without assigning identifiers for the each BIT.

    Appraoch 3: Your advices ...

    PS : Any approach would have been fine if there isnt any parity calculation

    Thank you
    Max

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    > Using bitwise operators change the bits of transType without assigning identifiers for the each BIT.
    Well you could do
    Code:
    enum {
        autfd,
        bldfc
        // and so on
    };
    
    #define GET_BIT(value,bitpos) ((value>>bitpos)&1)
    #define SET_BIT(value,bitpos) (value != (1<<bitpos))
    Despite appearances, most modern processors can extract single bits in just one or two instructions. It certainly isn't going to be horrendously expensive to how bitfields would be implemented internally.

    Where you can use in the code
    GET_BIT(value,autfd)

    The problem with the bit-fields is that you have NO control over whether unsigned int autfd : 1; maps to the LSB or the MSB of a byte.
    You can't even assume that struct portie would necessarily map to a single byte.
    Almost everything about bit-fields is implementation defined.
    seemaxie likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Left
    Join Date
    Oct 2011
    Posts
    822
    Parity calculation for eight bits is trivial; either via lookup,
    Code:
    const unsigned char odd_parity[256] = {
        0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,
        1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,
        1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,
        0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,
        1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,
        0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,
        0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,
        1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
    };
    or calculation:
    Code:
    static inline unsigned char odd_parity(unsigned char c)
    {
        c ^= c >> 4U;
        c ^= c >> 2U;
        c ^= c >> 1U;
        return c & 1U;
    }
    The former is often faster if you computes the parity bit for a lot of eight-bit units at a time (since then the parity table will be cache-hot), but the latter is just seven binary operations on a single variable, and is usually the best choice. Especially if you compute the parity bit for a single eight-bit unit, preceded and followed by other computations, the function is usually the best choice, because it will not have any cache side effects.

    If you have larger than 8-bit messages, then the parity function is preferred, because it has a logarithmic complexity wrt. number of bits. For example, the parity of a 64-bit message:
    Code:
    static inline unsigned char odd_parity(uint64_t u)
    {
        uint_fast32_t  t = (u >> 32U) ^ u;
        t ^= t >> 16U;
        t ^= t >> 8U;
        t ^= t >> 4U;
        t ^= t >> 2U;
        t ^= t >> 1U;
        return t & 1;
    }
    Technically, calculating the (odd) parity based on single bits, bit0 ^ bit1 ^ bit2 ^ ... ^ bitN, compiles to pretty lousy machine code, but only relatively: even with the "inefficient" approach it will only take a dozen or two clock cycles per eight-bit quantity, on any CPU architecture, so it is not going to be your bottleneck in any real world case.

    Therefore, the parity calculation should not really be a concern here.

    There are, however, two points that your choice does have an impact on:

    First, if you wish to use atomic built-ins provided by GCC, Intel CC, and other compilers, you need a single variable, and perhaps name the bits via constants. It is irrelevant for most single-threaded code, but may be important if multiple threads are used, or if signal handlers must modify bits.

    Second, if you often flip multiple bits at once, using a single variable and proper binary AND, OR, and NOT operations, lets you do all those at once. (You can only flip, clear, or set bits in one operation, but you can do it to more than one bit at a time.)

    In short, if you have a single variable, and just name the bits as constants, you tend to have more compact code. I also find it more readable, especially with comments that say why specific bits have to be set/cleared.

    My own code tends to the following style:
    Code:
    #define  BIT_FOO  (1U << 0)   /* Bit 0: Foo */
    #define  BIT_BAR  (1U << 1)   /* Bit 1: Bar */
    #define  BIT_BAZ  (1U << 2)   /* Bit 2: Baz */
    #define  BIT_UGH  (1U << 7)  /* Bit 7: Ugh */
    
    unsigned int u;
    
    /* Clear bits BAR and BAZ of u */
    u &= ~(BIT_BAR | BIT_BAZ);
    
    /* Set bit UGH of u */
    u |=BIT_UGH;
    
    /* Flip bits FOO and BAR of u */
    u ^= (BIT_FOO | BIT_BAR);
    Added after I saw Salem's post:

    Agreed (although the ! should be | in the example code): If you need a specific machine representation, say you intend to send the byte over a serial connection, or write to a file, or to some other device, you should not use bitfields, but variables (of the appropriate size), and use binary operators to manipulate the bits in each unit (be it unsigned char or uint8_t or whatever is most appropriate).
    Last edited by Nominal Animal; 10-23-2012 at 12:01 PM.
    seemaxie likes this.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    The fastest way of calculating parity without going into assembly is listed here:
    Bit Twiddling Hacks
    seemaxie likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Left
    Join Date
    Oct 2011
    Posts
    822
    Quote Originally Posted by iMalc View Post
    The fastest way of calculating parity without going into assembly is listed here:
    Bit Twiddling Hacks
    Yup, and it contains lots of other useful bits and pieces, too. The code there basically uses a 16-entry lookup table packed into a 16-bit integer (0110100110010110 = 0x6996 = 27030) for the final four bits:
    Code:
    static inline unsigned char odd_parity(uint64_t u)
    {
        uint_fast32_t  t = (u >> 32U) ^ u;
        t ^= t >> 16U;
        t ^= t >> 8U;
        t ^= t >> 4U;
        return ((uint_fast32_t)27030U >> (t & 15U)) & 1U;
    }
    seemaxie likes this.

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    35
    Thanks a ton Guys... n Spl thanks to Nominal for such a clean explanation. Your inputs were really helpful ...

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    35
    Can someone help me to optimize this code.. With the above inputs i have come up with this... I am setting a partiy for every 8 bits in P_parity but for 16 bits variables i have broken them twice n set the parity accordingly. In the below i broke C_Word variable twice to set the parity . And to set the parity i had kept the IF condition. It works but it would be great if someone help me out to optimize it .
    Code:
    /* To set or clear BITS in P_Parity variable */
    #define  PRTY_ID           (1U << 0)   
    #define  PRTY_CWORD1  (1U << 1)  
    #define  PRTY_CWORD2  (1U << 2)   
    #define  PRTY_DATA1   (1U << 3)   
    #define  PRTY_DATA2   (1U << 4)   
    
    #define  LED_GRN            (1U << 0)  
    #define  LED_RED            (1U << 1)   
    #define  STRTSTOP_PIN    (1U << 2)  
    #define  PID_ACTIVE       (1U << 3) 
    
    
    typedef struct {
       unsigned char   I_Id;              // 8 BITS
       unsigned short  C_Word;            // 16 BITS    
       unsigned short  D_Data;            // 16 BITS
       unsigned char P_Parity;         // 8 BITS
    } SpiBuf;
    
    
    int main(void)
    {
         int i,j;
          SpiReady.C_Word = 0xBF;
          i = odd_parity(SpiReady.C_Word);
          j = odd_parity(SpiReady.C_Word >> 8);
    
          if(!i)
          SpiReady.P_Parity &= ~(PRTY_CWORD1) ; // clear
          else
          SpiReady.P_Parity |= PRTY_CWORD1 ;  // set
    
          if(!j)
          SpiReady.P_Parity &= ~(PRTY_CWORD2) ; // clear
          else
          SpiReady.P_Parity |= PRTY_CWORD2 ;  // set
    
          printf("%d \n %d \n", i ,  j);
    
          printf("%d \n ",SpiReady.P_Parity );
    
        return 0;
    }
    
    
    
    /*Function definitions*/
    static inline unsigned char odd_parity(unsigned char c)
    {
        c ^= c >> 4U;
        c ^= c >> 2U;
        c ^= c >> 1U;
        return c & 1U;
    }
    EDIT: If once optimized i would apply the similar logic on other variables too.. I am using those printf functions just for reference .
    Last edited by seemaxie; 10-25-2012 at 09:33 AM.

  8. #8
    Left
    Join Date
    Oct 2011
    Posts
    822
    Let's see. Since you need to calculate the parity for each 8 bit unit, and pack it in one, I'd save the bit shift counts, too:
    Code:
    #define  PARITY_ID_SHIFT      0
    #define  PARITY_CWORD1_SHIFT  1
    #define  PARITY_CWORD2_SHIFT  2
    #define  PARITY_DATA1_SHIFT   3
    #define  PARITY_DATA2_SHIFT   4
    
    #define  PARITY_ID      (1U << PARITY_ID_SHIFT)
    #define  PARITY_CWORD1  (1U << PARITY_CWORD1_SHIFT)
    #define  PARITY_CWORD2  (1U << PARITY_CWORD2_SHIFT)
    #define  PARITY_DATA1   (1U << PARITY_DATA1_SHIFT)
    #define  PARITY_DATA2   (1U << PARITY_DATA2_SHIFT)
    Second, for the odd parity of the lowest eight bits you can use the optimized version,
    Code:
    static inline unsigned char odd_parity(unsigned char c)
    {
        return ((unsigned int)27030U >> (((c >> 4U) ^ c) & 15U)) & 1U;
    }
    Third, even and odd parity are opposites. So, if you initialize a mask to 0 (for odd parity) or ~0 (for even parity), XORing with the mask will give you the desired parity. For five bits, I'd use
    Code:
    #define ODD_PARITY  (0U)
    #define EVEN_PARITY (31U)
    Next, you need to check whether CWORD1 and DATA1 refer to the low byte (bits 0..7) or high byte (bits 8..15); your code indicates the low byte, so that's what I'll use below. (It makes sense only if your SPI wire functions send the low byte first.)

    As an inline function:
    Code:
    static inline void compute_parity(SpiBuf *const s, const unsigned char mask)
    {
        s->P_Parity = mask
                    ^ (odd_parity(s->I_Id)         << PARITY_ID_SHIFT)
                    ^ (odd_parity(s->C_Word)       << PARITY_CWORD1_SHIFT)
                    ^ (odd_parity(s->C_Word >> 8U) << PARITY_CWORD2_SHIFT)
                    ^ (odd_parity(s->D_Data)       << PARITY_DATA1_SHIFT)
                    ^ (odd_parity(s->D_Data >> 8U) << PARITY_DATA2_SHIFT);
    }
    The above works, because odd_parity() always returns 0 (even parity) or 1 (odd parity). Shifting the value up places it in the correct bit. Using XOR (^) means we can start with the even/odd mask; we then only flip the bits when the parity was odd.

    Now you can do for example just
    Code:
        compute_parity(&SpiReady, ODD_PARITY);
    to set all the parity bits in the SpiReady variable correctly, for odd parity.

    Note that the compiler will inline static inline functions just as if they were macros, so the above will not use stack et cetera; it is as efficient as a macro.

    I'd also put it just after the structure declaration, so that if anything changes, you only need to change it in one place.

    Questions?
    Last edited by Nominal Animal; 10-25-2012 at 11:41 AM.
    seemaxie likes this.

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    35
    Thank you for your time .. It seems to be optimized to the core .. Great touch..
    q1) The below is not needed anymore..??
    Code:
    #define  PARITY_ID      (1U << PARITY_ID_SHIFT)
    #define  PARITY_CWORD1  (1U << PARITY_CWORD1_SHIFT)
    
    #define  PARITY_CWORD2  (1U << PARITY_CWORD2_SHIFT)
    #define  PARITY_DATA1   (1U << PARITY_DATA1_SHIFT)
    #define  PARITY_DATA2   (1U << PARITY_DATA2_SHIFT)
    q2) It looks like a mistype from you.. It should be 1U right????
    Code:
    #define EVEN_PARITY (31U)
    q3) My brain could not decode how this parity calculation is happening. I would be glad if you reveal it too.
    Code:
    static inline unsigned char odd_parity(unsigned char c)
    {
        return ((unsigned int)27030U >> (((c >> 4U) ^ c) & 15U)) & 1U;
    }
    Thanks again Nominal ..

  10. #10
    Left
    Join Date
    Oct 2011
    Posts
    822
    Quote Originally Posted by seemaxie View Post
    q1) The below is not needed anymore..??
    Code:
    #define  PARITY_ID      (1U << PARITY_ID_SHIFT)
    #define  PARITY_CWORD1  (1U << PARITY_CWORD1_SHIFT)
    
    #define  PARITY_CWORD2  (1U << PARITY_CWORD2_SHIFT)
    #define  PARITY_DATA1   (1U << PARITY_DATA1_SHIFT)
    #define  PARITY_DATA2   (1U << PARITY_DATA2_SHIFT)
    I don't know, do you? They are not necessary for the parity calculations. I just kept them in case you have a use for them elsewhere in your code.

    Quote Originally Posted by seemaxie View Post
    q2) It looks like a mistype from you.. It should be 1U right????
    Code:
    #define EVEN_PARITY (31U)
    Nope. Even parity mask is all bits set. You have just five bits, 11111b = 31. I prefer to keep unused bits always zero, to avoid any problems if I find I need to use one later on.

    You could also use (~0U), but then the unused bits in the parity word will be zero if using odd parity, one if even parity.

    Quote Originally Posted by seemaxie View Post
    q3) My brain could not decode how this parity calculation is happening. I would be glad if you reveal it too.
    Let's decode what is done first. I'll explain why afterwards.
    Code:
    ((unsigned int)27030U >> ((((c >> 4U) ^ c) & 15U)) & 1U
    The red part is evaluated first. If you want, you could write the same as
    Code:
    static inline unsigned char odd_parity(unsigned char c)
    {
        c = (c >> 4U) ^ c;
        c = c & 15U;
        return ((unsigned int)27030U >> c) & 1U;
    }
    In other words, we do an exclusive XOR between the four low bits and the four high bits, storing the result in the four low bits, and clearing the four high bits. That gives us 0000b = 0 <= c <= 15 = 1111b. Then, we take 27030 = 0110100110010110b, shift the c'th bit to the rightmost/least significant position, and keep only that bit (by ANDing with 1). That is the (odd) parity bit for the 8-bit input.

    Now, why does that work?

    First, remember that (odd) parity bit is 1 if the value has an odd number of bits set. It does not matter if there are 1, 3, 5, 7, 9, .. or however many bits set, only whether there is an odd number of them or not. Also, their positions do not matter, only the count.

    If you take any bit string, fold it in half, and XOR the halves together, the result has the same parity as the original string. This is because XOR retains parity: 0^0=0, 0^1=1, 1^0=1, 1^1=0. Thus, we can compute the parity of any value (that has an even number of bits) by folding it in two and XORing the halves together, until we have just one bit left.

    We also know the (odd) parity of the first sixteen nonnegative integers:
    Code:
    0 = 0000b ➞ 0       8 = 1000b ➞ 1
    1 = 0001b ➞ 1       9 = 1001b ➞ 0
    2 = 0010b ➞ 1      10 = 1010b ➞ 0
    3 = 0011b ➞ 0      11 = 1011b ➞ 1
    4 = 0100b ➞ 1      12 = 1100b ➞ 0
    5 = 0101b ➞ 0      13 = 1101b ➞ 1
    6 = 0110b ➞ 0      14 = 1110b ➞ 1
    7 = 0111b ➞ 1      15 = 1111b ➞ 0
    Instead of doing two more folds (four to two, then two to one bit), we construct a lookup table of those sixteen values, 0110100110010110 = 27030. Note it happens to be symmetric, so you don't even need to care which end you read it from. We can now get the (odd) parity for a number 0 <= c <= 15 simply by (27030U >> c) & 1.

    Put it all together in reverse, and you end up with ((unsigned int)27030U >> (((c >> 4U) ^ c) & 15U)) & 1U yielding the (odd) parity for an eight-bit input c.
    seemaxie likes this.

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    35
    I m really happy to come out of ignorance.. Glad to meet you n thanks again for such a wonderful explanation . I will mark this thread for my future reference too . I do not know whether i can find such a clear explanation in books too but i would be glad if you suggest some books as you can see my logical thinking has to be improved .. Thanks a ton Nominal ...


    EDIT : Q1) Nope i am not using them anymore so will avoid them. Q2) Roger that .. my mistake ..
    Last edited by seemaxie; 10-25-2012 at 04:48 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. IP fragmentation
    By codewriter in forum Tech Board
    Replies: 3
    Last Post: 05-12-2012, 08:40 AM
  2. Replies: 4
    Last Post: 04-25-2010, 10:57 AM
  3. Memory Fragmentation with Dynamic FIFO Queue
    By fguy817817 in forum Linux Programming
    Replies: 17
    Last Post: 10-31-2009, 04:17 AM
  4. multi-thread socket program with packet fragmentation
    By thinkerchjf in forum Networking/Device Communication
    Replies: 2
    Last Post: 06-25-2009, 10:46 AM
  5. Allocation Granularity and fragmentation
    By ZeroMemory in forum Windows Programming
    Replies: 4
    Last Post: 01-10-2008, 07:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21