From:	CSBVAX::MRGATE!LEICHTER@Venus.YCC.Yale.Edu@SMTP 24-MAY-1988 04:44
To:	ARISIA::EVERHART
Subj:	re: COMPUTING PARITY


Received: from Venus.YCC.Yale.Edu by KL.SRI.COM with TCP; Sat 21 May 88 18:14:48-PDT
Date: Sat, 21 May 88 21:17 EST
From: "Jerry Leichter (LEICHTER-JERRY@CS.YALE.EDU)"
 <LEICHTER@Venus.YCC.Yale.Edu>
Subject: re: COMPUTING PARITY
To: ZSYJKAA@WYOCDC1.BITNET, INFO-VAX@KL.SRI.COM
X-VMS-To: IN%"ZSYJKAA@WYOCDC1.BITNET",INFOVAX

	Is there any quick method in VMS fortran to compute the parity of a
	32-bit word?  Either a function that does exactly that, or one that
	returns the number of "1" bits in the word?

	By analogy, if you're familiar with Control Data Cybers, there's the
	POP instruction (POPulation count) which returns the number of "1"
	bits; checking the low bit of the count tells you if the word has even
	or odd parity.  CDC Fortran has a corresponding intrinsic function.
	The best I can think of in VMS is to loop 32 times and use ISHFT and
	IAND.

I don't think there's any built-in function to do this, though perhaps someone
who's a heavy FORTRAN user will prove me wrong.  However, it's not hard to
trade a little space to speed up an implementation by quite a bit:  Rather
than counting individual bits, make a table of the parity values of each
8-bit byte - depending on how you do this, it could be a 256-byte table,
or a 256-bit table, then loop through the bytes and add up the values.  Or,
slightly better, view the 32-bit word as two 16-bit values, XOR; view the
resulting 16 bits as two 8-bit fields; XOR; look up result.

There are many variations; which is best really depends on exactly how
important the ultimate in speed is and what you are writing in.  (Accessing
a table of bits is one MACRO instruction (BBx), easy to generate in a couple
of languages (BLISS, PL/I), a pain or impossible in others.  (For the absolute
maximum in speed, in MACRO, you can do it in two instructions:  One XOR,
one BBS from a 65536-bit (8192-byte) table.)

BTW, analogous techniques apply if you really want a population count, rather
than just parity - though of course now you need bigger fields in your table.
However, there is another, much more obscure technique for counting 1-bits
in a word, originally written up for the PDP-10 in HAKMEM some time back.
The following is a translation into C macros:

/*
 * Macros to compute a bit value from a bit number, bit number from bit value,
 * and the bit count (number of bits on) for 32-bit quantities.  The results
 * are compile-time constants if the arguments are.
 *
 * The definition of BITCOUNT is based on an algorithm condensed from one
 * extracted from a graph coloring register allocator which manipulates
 * bitvectors.  It was inspired by an analogous algorithm for counting bits in
 * 36 bit words in MIT's HAKMEM, designed by Chris Smith, and written by Jane
 * Hoffman.  The original conversion to a form suitable for C on a VAX was by
 * Brad Merrill; that code was fixed and re-written by Jerry Leichter.  It
 * assumes a 32-bit word.  Note that the argument is evaluated multiple times,
 * so should not have side-effects.  A full explanation of the algorithm is
 * too long to include here; in summary, BX_(x) replaces each 4-bit sequence
 * in x by the number of bits in that sequence (which will, of course, fit in
 * 4 bits).  BITCOUNT folds the 4-bit sequences into 8-bit sequences.  The
 * 8-bit sequences are then added up by recognizing that they can be viewed as
 * a base 256 number, and the sum of the digits of a base b number is the same
 * mod b-1 as the number mod b-1.
 *
 * The original implementation produce results in groups of 3, then 6 bits.
 * While natural on a PDP-10's 36-bit word, this requires special case
 * handling of the sign bit on a VAX, since the top 3-bit sequence is really
 * only 2 bits long. 
 */
#define BITVAL(n)	(1 << (n))
#define BITNUM(b)	BITCOUNT((b)-1)
#define BITCOUNT(x)	(((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define  BX_(x)		((x) - (((x)>>1)&0x77777777)			\
			     - (((x)>>2)&0x33333333)			\
			     - (((x)>>3)&0x11111111))
