PARITY.ih File Reference

Priority calculation, inline interface and implementation. More...

#include <PBI/Inline.h>
#include <PBI/Attribute.h>
#include <PARITY.h>

Defines
#define	PARITY__EXP_PROTO   INLINE_USR_EXP_PROTO
#define	PARITY__LCL_PROTO   INLINE_USR_LCL_PROTO
#define	PARITY__EXP_FNC   INLINE_USR_EXP_FNC
#define	PARITY__LCL_FNC   INLINE_USR_LCL_FNC
Functions
PARITY__EXP_PROTO int	PARITY__calc8 (unsigned char byte) ATTR_UNUSED_OK
	Calculates the parity over the 8 bits in the specified byte.
PARITY__EXP_PROTO int	PARITY__calc16 (unsigned short int hword) ATTR_UNUSED_OK
	Calculates the parity over the 16 bits in the specified half word.
PARITY__EXP_PROTO int	PARITY__calc32 (unsigned int word) ATTR_UNUSED_OK
	Calculates the parity over the 32 bits in the specified word.
PARITY__EXP_PROTO int	PARITY__calc64 (unsigned long long int ll) ATTR_UNUSED_OK
	Calculates the parity over the 64 bits in the specified long long.
PARITY__EXP_PROTO int	PARITY__calc8N (const unsigned char *bytes, int nbytes) ATTR_UNUSED_OK
	Calculates the parity over all the bits in the specified array of bytes.
PARITY__EXP_PROTO int	PARITY__calc16N (const unsigned short int *hwords, int nhwords) ATTR_UNUSED_OK
	Calculates the parity over all the bits in the specified array of half words (16-bit integers).
PARITY__EXP_PROTO int	PARITY__calc32N (const unsigned int *words, int nwords) ATTR_UNUSED_OK
	Calculates the parity over all the bits in the specified array of words (32-bit integers).
PARITY__EXP_PROTO int	PARITY__calc64N (const unsigned long long int *lls, int nlls) ATTR_UNUSED_OK
	Calculates the parity over all the bits in the specified array of long long words (64-bit integers).
PARITY__EXP_PROTO int	PARITY__calcOdd8 (unsigned char byte) ATTR_UNUSED_OK
	Calculates the odd parity over the 8 bits in the specified byte.
PARITY__EXP_PROTO int	PARITY__calcOdd16 (unsigned short int hword) ATTR_UNUSED_OK
	Calculates the odd parity over the 16 bits in the specified half word.
PARITY__EXP_PROTO int	PARITY__calcOdd32 (unsigned int word) ATTR_UNUSED_OK
	Calculates the odd parity over the 32 bits in the specified word.
PARITY__EXP_PROTO int	PARITY__calcOdd64 (unsigned long long int ll) ATTR_UNUSED_OK
	Calculates the odd parity over the 64 bits in the specified long long.
PARITY__EXP_PROTO int	PARITY__calcOdd8N (const unsigned char *bytes, int nbytes) ATTR_UNUSED_OK
	Calculates the odd parity over all the bits in the specified array of bytes.
PARITY__EXP_PROTO int	PARITY__calcOdd16N (const unsigned short int *hwords, int nhwords) ATTR_UNUSED_OK
	Calculates the odd parity over all the bits in the specified array of half words (16-bit integers).
PARITY__EXP_PROTO int	PARITY__calcOdd32N (const unsigned int *words, int nwords) ATTR_UNUSED_OK
	Calculates the odd parity over all the bits in the specified array of words (32-bit integers).
PARITY__EXP_PROTO int	PARITY__calcOdd64N (const unsigned long long int *lls, int nlls) ATTR_UNUSED_OK
	Calculates the odd parity over all the bits in the specified array of long long words (64-bit integers).

---

Detailed Description

Priority calculation, inline interface and implementation.

Author:

JJRussell - russell@slac.stanford.edu

    CVS $Id: PARITY.ih,v 1.2 2011/03/25 22:16:56 russell Exp $

SYNOPSIS

This defines the inline implementation of the parity routines. Routines are provided to calculate the parity over

1. A byte (8 bits)
2. A short (16 bits)
3. An int (32 bits)

as well as arrays of the same.

ALGORITHM

The parity is simply defined as 0 if the count of set bits is even and odd if the count of set bits is odd. One could add all the bits together, but all that is really needed is the low bit of the sum, This is simply the XOR of all the bits.

Consider the following straightforward way to XOR all the bits in a 32 bit word.

    .
    .
    parity = (word   >> 16) ^ (word);
    parity = (parity >>  8) ^ (parity);
    parity = (parity >>  4) ^ (parity);
    parity = (parity >>  2) ^ (parity);
    parity = (parity >>  1) ^ (parity);
    return  parity & 1;

This takes advantage of the fact that the XORs can be done in parallel. However, there is a small improvement that can be made on this algorithm. Consider building an array is that as big as the value of an input value and whose value at an given index is a single bit giving the parity of the value. Of course such an array for a 32-bit integer would be prohibitively large. Even if this was not true, on RISC machines, one should avoid referencing uncached memory for performance reasons.

There is an variation on this theme that does work. First, execute the above algorithm until only 4 bits remain. Now the range of these 4 bits is modest, 0-15, so one could consider an array. The array that will be indexed, however is not as a traditional memory array, but as a bit array built in a single 16-bit number. The indexing is accomplished by simply right shifting this 16-bit numer and masking off the low order bit.

    .
    .
    index  =  word;
    index ^= (index >> 16);   / * Reduce to 16 significant bits  * /
    index ^= (index >>  8);   / * Reduce to  8 significant bits  * /
    index ^= (index >>  4);   / * Reduce to  8 significant bits  * /
    index &= 0xf;             / * Pick off the lower 4 bits      * /
    return 0x6996 >> index;   / * Index the answer array         * /

Note another nice feature of this algortihm. If one desires a logical functions that returns TRUE if the parity is EVEN, or equivalently one that returns the ODD parity then one simply replaces the 0x6996 with 0x9669.

The above sequence should cost approximately 8 integer instructions on a PowerPC. Narrower widths cost less; a 16-bit value should cost about 6 instructions and a byte should cost 4 instructions.

CALLABLE VERSIONS

Callable versions of these routines are also available. The names of the callable versions are the same as these, except the double underscore is replaced with a single underscore.

Note also that the implementation of the callable versions of the array routines may or may not be the same as the inline versions. There are various techniques that can speed up the calculation on large arrays. Because of the additional logic these techniques add, it would not be appropriate to use them in the inline versions.

The best advise here is, if one is calculating the parity over arrays less than say ~10 elements, use the inline versions. If one is calculating the parity over larger arrays, use the callable versions. The overhead of the call will be compensated by speedier routines. This statement is particularly true when calculating the parity over arrays of bytes and half words (short ints).

---

Function Documentation

PARITY__EXP_FNC int PARITY__calc16

(

unsigned short int

hword

)

Calculates the parity over the 16 bits in the specified half word.

Returns:

The parity, either 0 or 1, over the 16 bits the specified half word.

Parameters:

hword

The half word (short int) to calculate the parity of.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc16N	(	const unsigned short int *	hwords,
		int	nhwords
	)

Calculates the parity over all the bits in the specified array of half words (16-bit integers).

Returns:

The parity, either 0 or 1, over all the bits in the specified array of half words (16-bit integers). If a length of 0 is specified, 0 is returned.

Parameters:

	hwords	The array of half words (16-bit integers) to calculate the parity over.
	nhwords	The number of half words (16-bit integers) in the array.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc32

(

unsigned int

word

)

Calculates the parity over the 32 bits in the specified word.

Returns:

The parity, either 0 or 1, over the 32 bits the specified word.

Parameters:

word

The word to calculate the parity over.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc32N	(	const unsigned int *	words,
		int	nwords
	)

Calculates the parity over all the bits in the specified array of words (32-bit integers).

Returns:

The parity, either 0 or 1, of the specified array of words. If a length of 0 is specified, 0 is returned.

Parameters:

	words	The array of words (ints) to calculate the parity over.
	nwords	The number of words (ints) in the array.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc64

(

unsigned long long int

ll

)

Calculates the parity over the 64 bits in the specified long long.

Returns:

The parity, either 0 or 1, over the 64 bits of the specified long long .

Parameters:

ll

The long long to calculate the parity over.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc64N	(	const unsigned long long int *	lls,
		int	nlls
	)

Calculates the parity over all the bits in the specified array of long long words (64-bit integers).

Returns:

The parity, either 0 or 1, of the specified array of long longs If a length of 0 is specified, 0 is returned.

Parameters:

	lls	The array of long longs to calculate the parity over.
	nlls	The number of long longs in the array.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc8

(

unsigned char

byte

)

Calculates the parity over the 8 bits in the specified byte.

Returns:

The parity, either 0 or 1, over the 8 bits in the specified byte.

Parameters:

byte

The byte to calculate the parity over.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calc8N	(	const unsigned char *	bytes,
		int	nbytes
	)

Calculates the parity over all the bits in the specified array of bytes.

Returns:

The parity, either 0 or 1, over the specified array of bytes. If a length of 0 is specified, 0 is returned.

Parameters:

	bytes	The array of bytes to calculate the parity over.
	nbytes	The number of bytes in array.

References PARITY_K_EVEN.

PARITY__EXP_FNC int PARITY__calcOdd16

(

unsigned short int

hword

)

Calculates the odd parity over the 16 bits in the specified half word.

Returns:

The odd parity, either 0 or 1, over the 16 bits the specified half word.

Parameters:

hword

The half word (short int) to calculate the parity of.

References PARITY_K_ODD.

Referenced by EBF_sivUpdate().

PARITY__EXP_FNC int PARITY__calcOdd16N	(	const unsigned short int *	hwords,
		int	nhwords
	)

Calculates the odd parity over all the bits in the specified array of half words (16-bit integers).

Returns:

The parity, either 0 or 1, over all the bits in the specified array of half words (16-bit integers). If a length of 0 is specified, 1 is returned.

Parameters:

	hwords	The array of half words (16-bit integers) to calculate the odd parity over.
	nhwords	The number of half words (16-bit integers) in the array.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd32

(

unsigned int

word

)

Calculates the odd parity over the 32 bits in the specified word.

Returns:

The odd parity, either 0 or 1, over the 32 bits the specified word.

Parameters:

word

The word to calculate the odd parity over.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd32N	(	const unsigned int *	words,
		int	nwords
	)

Calculates the odd parity over all the bits in the specified array of words (32-bit integers).

Returns:

The odd parity, either 0 or 1, of the specified array of words. If a length of 0 is specified, 1 is returned.

Parameters:

	words	The array of words (ints) to calculate the odd parity over.
	nwords	The number of words (ints) in the array.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd64

(

unsigned long long int

ll

)

Calculates the odd parity over the 64 bits in the specified long long.

Returns:

The odd parity, either 0 or 1, over the 64 bits of the specified long long.

Parameters:

ll

The long long to calculate the odd parity over.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd64N	(	const unsigned long long int *	lls,
		int	nlls
	)

Calculates the odd parity over all the bits in the specified array of long long words (64-bit integers).

Returns:

The odd parity, either 0 or 1, of the specified array of long log words (64-bit integers). If a length of 0 is specified, 1 is returned.

Parameters:

	lls	The array of long long's to calculate the odd parity over.
	nlls	The number of long long's in the array.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd8

(

unsigned char

byte

)

Calculates the odd parity over the 8 bits in the specified byte.

Returns:

The odd parity, either 0 or 1, over the 8 bits in the specified byte.

Parameters:

byte

The byte to calculate the odd parity over.

References PARITY_K_ODD.

PARITY__EXP_FNC int PARITY__calcOdd8N	(	const unsigned char *	bytes,
		int	nbytes
	)

Calculates the odd parity over all the bits in the specified array of bytes.

Returns:

The odd parity, either 0 or 1, over the specified array of bytes. If a length of 0 is specified, 1 is returned.

Parameters:

	bytes	The array of bytes to calculate the odd parity over.
	nbytes	The number of bytes in array.

References PARITY_K_ODD.