ZSYJKAA@WYOCDC1.BITNET (Jim Kirkpatrick 307 766-5303) (05/18/88)
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.
Jim Kirkpatrick ZSYJKAA@WYOCDC1 (on BITNET)
"help stamp out 5-page signature files"LEICHTER@VENUS.YCC.YALE.EDU ("Jerry Leichter ", LEICHTER-JERRY@CS.YALE.EDU) (05/22/88)
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))