Byte parity question...

[philbo30]

I admit, I didn't spend any time researching this yet so this is the
first step...

Is there a C function available to determine byte parity or is the
usual course to just count the 1s?

 

[cr88192]

I admit, I didn't spend any time researching this yet so this is the
first step...

Is there a C function available to determine byte parity or is the
usual course to just count the 1s?

counting 1s, though possible, but is a slow option.

k=0; for(j=0; j<8; j++)if(i&(1<<j))k++;
even: !(k&1)
odd: k&1


one can use a table, or a bitmap, instead.

nibbles (Even, Odd):
0-E 1-O 2-O 3-E
4-O 5-E 6-E 7-O
8-O 9-E A-E B-O
C-E D-O E-O F-E

so, a bitmask:
static int p_even=0x9669;
static int p_odd=0x6996;

nibble 'i' is even? 'p_even&(1<<i)' or '(p_even>>i)&1'.

and for a byte:
((p_even>>(i&15))&1)==((p_even>>((i>>4)&15))&1)

or, odd:
((p_odd>>(i&15))^(p_odd>>((i>>4)&15)))&1

consequently, we can define a bitmap table, and do a byte like this:
(p_even_bm[i>>4]>>(i&15))&1
(p_odd_bm[i>>4]>>(i&15))&1


or, even faster (but taking a lot more space), is giving an individual value
for every input value:
p_even_tab
p_odd_tab

along with other possibilities...

 

[junky_fellow]

I admit, I didn't spend any time researching this yet so this is the
first step...

Is there a C function available to determine byte parity or is the
usual course to just count the 1s?

You may use XOR operation.

 

[Charlie Gordon]

You may use XOR operation.

That's an interesting alternative to a memory based lookup table.
Assuming bytes have 8 bits, this code should do:

static inline int byte_parity(unsigned char b) {
b ^= b >> 4;
b ^= b >> 2;
b ^= b >> 1;
return b & 1;
}

This method can be easily generalized to larger unsigned types.

 

[Tor Rustad]

I admit, I didn't spend any time researching this yet so this is the
first step...

Is there a C function available to determine byte parity or is the
usual course to just count the 1s?

There is no such function in the standard C library.

If CHAR_BIT is 8, you could use this table:

static unsigned char parity[] =
{
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
};

where parity[octet] gives the bit count. Yes, the above table was
generated by simply counting the 1s.

 

[Tor Rustad]

where parity[octet] gives the bit count.

ITYM:

"where parity[octet] gives the parity of the octet."

 

[Richard Tobin]

where parity[octet] gives the bit count.

[/QUOTE]

ITYM:

"where parity[octet] gives the parity of the octet."

Maybe he just forgot to say "modulo 2" at the end.

-- Richard

 

[Thad Smith]

Assuming bytes have 8 bits, this code should do:

static inline int byte_parity(unsigned char b) {
b ^= b >> 4;
b ^= b >> 2;
b ^= b >> 1;
return b & 1;
}

This method can be easily generalized to larger unsigned types.

This generalization, for a byte, should work for all sizes of bytes.
Most compilers will eliminate the while loop for 8-bit byte targets.

/* Function: parity
** Description: Return the parity of the argument.
*/
int /* parity of b: 1 if number of 1 bits is odd,
** 0 otherwise. */
parity (unsigned char b) {
while (b > 0xff) {
b = (b >> 8) ^ (b & 0xff);
}
b ^= b >> 4;
b ^= b >> 2;
return ((b >> 1) ^ b) & 1;
}

 

[Michal Nazarewicz]

This generalization, for a byte, should work for all sizes of
bytes. Most compilers will eliminate the while loop for 8-bit byte
targets.

Or one could use preprocessor directives to help compiler a bit:

/* Function: parity
** Description: Return the parity of the argument.
*/
int /* parity of b: 1 if number of 1 bits is odd,
** 0 otherwise. */
parity (unsigned char b) { #if CHAR_BIT > 16
while (b > 0xff) {
b = (b >> 8) ^ (b & 0xff);
}

#elif CHAR_BIT > 8
b ^= b >> 8;
#endif