Byte parity question...

Discussion in 'C Programming' started by philbo30, Sep 10, 2007.

  1. philbo30

    philbo30 Guest

    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?
     
    philbo30, Sep 10, 2007
    #1
    1. Advertising

  2. philbo30

    cr88192 Guest

    "philbo30" <> wrote in message
    news:...
    >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...
     
    cr88192, Sep 10, 2007
    #2
    1. Advertising

  3. philbo30

    Guest

    On Sep 10, 4:13 am, 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?


    You may use XOR operation.
     
    , Sep 10, 2007
    #3
  4. <> a écrit dans le message de news:
    ...
    > On Sep 10, 4:13 am, 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?

    >
    > 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
     
    Charlie Gordon, Sep 10, 2007
    #4
  5. philbo30

    Tor Rustad Guest

    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>
     
    Tor Rustad, Sep 10, 2007
    #5
  6. philbo30

    Tor Rustad Guest

    Tor Rustad wrote:

    > where parity[octet] gives the bit count.


    ITYM:

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


    --
    Tor <torust [at] online [dot] no>
     
    Tor Rustad, Sep 10, 2007
    #6
  7. In article <>,
    Tor Rustad <> wrote:

    >> 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.
     
    Richard Tobin, Sep 10, 2007
    #7
  8. philbo30

    Thad Smith Guest

    Charlie Gordon wrote:
    > <> a écrit dans le message de news:
    > ...
    >> On Sep 10, 4:13 am, philbo30 <> 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 >> 8) ^ (b & 0xff);
    }
    b ^= b >> 4;
    b ^= b >> 2;
    return ((b >> 1) ^ b) & 1;
    }



    --
    Thad
     
    Thad Smith, Sep 11, 2007
    #8
  9. >> On Sep 10, 4:13 am, philbo30 <> 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.


    Thad Smith <> writes:
    > 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
    > 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--
     
    Michal Nazarewicz, Sep 11, 2007
    #9
    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. Ed

    Parity Check

    Ed, Sep 30, 2004, in forum: VHDL
    Replies:
    18
    Views:
    10,973
    yassen
    Oct 6, 2009
  2. snacktime

    Set parity of a string

    snacktime, Jan 23, 2005, in forum: Python
    Replies:
    8
    Views:
    405
    Peter Hansen
    Jan 26, 2005
  3. Petr Jakes
    Replies:
    2
    Views:
    5,263
    Petr Jakes
    Nov 12, 2005
  4. shakeelsultan

    odd parity checker FSM

    shakeelsultan, Oct 27, 2006, in forum: VHDL
    Replies:
    0
    Views:
    836
    shakeelsultan
    Oct 27, 2006
  5. Herbert Haas

    Parity check of a word

    Herbert Haas, Aug 28, 2005, in forum: C Programming
    Replies:
    15
    Views:
    713
    Krishanu Debnath
    Sep 1, 2005
Loading...

Share This Page