Velocity Reviews > Byte parity question...

# Byte parity question...

philbo30
Guest
Posts: n/a

 09-09-2007
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
Guest
Posts: n/a

 09-09-2007

"philbo30" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
>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

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[i]
p_odd_tab[i]

along with other possibilities...

junky_fellow@yahoo.co.in
Guest
Posts: n/a

 09-10-2007
On Sep 10, 4:13 am, philbo30 <(E-Mail Removed)> wrote:
> 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
Guest
Posts: n/a

 09-10-2007
<(E-Mail Removed)> a écrit dans le message de news:
(E-Mail Removed) m...
> On Sep 10, 4:13 am, philbo30 <(E-Mail Removed)> wrote:
>> 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.

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.

--
Chqrlie

Guest
Posts: n/a

 09-10-2007
philbo30 wrote:
> 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 <torust [at] online [dot] no>

Guest
Posts: n/a

 09-10-2007

> where parity[octet] gives the bit count.

ITYM:

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

--
Tor <torust [at] online [dot] no>

Richard Tobin
Guest
Posts: n/a

 09-10-2007
In article <(E-Mail Removed)>,

>> where parity[octet] gives the bit count.

>ITYM:
>
>"where parity[octet] gives the parity of the octet."

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

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Guest
Posts: n/a

 09-11-2007
Charlie Gordon wrote:
> <(E-Mail Removed)> a écrit dans le message de news:
> (E-Mail Removed) m...
>> On Sep 10, 4:13 am, philbo30 <(E-Mail Removed)> wrote:

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

>
> 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 >> ^ (b & 0xff);
}
b ^= b >> 4;
b ^= b >> 2;
return ((b >> 1) ^ b) & 1;
}

--

Michal Nazarewicz
Guest
Posts: n/a

 09-11-2007
>> On Sep 10, 4:13 am, philbo30 <(E-Mail Removed)> wrote:
>>> Is there a C function available to determine byte parity or is the
>>> usual course to just count the 1s?

> Charlie Gordon wrote:
>> 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.

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 >> ^ (b & 0xff);
> }

#elif CHAR_BIT > 8
b ^= b >> 8;
#endif
> b ^= b >> 4;
> b ^= b >> 2;
> return ((b >> 1) ^ b) & 1;
> }

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--