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

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

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

The fastest way of calculating parity without going into assembly is listed here:
Bit Twiddling Hacks

Quote:

---

Originally Posted by iMalc

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;
}

---

Thanks a ton Guys... n Spl thanks to Nominal for such a clean explanation. :)Your inputs were really helpful ... :)

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 . :)

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?

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 ..:) :) :) :) :)

Quote:

---

Originally Posted by seemaxie

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

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, 11111_b = 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

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 0000_b = 0 <= c <= 15 = 1111_b. Then, we take 27030 = 0110100110010110_b, 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.

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 ..:)