Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!sot-ecs!sra
From: sra@ecs.soton.ac.uk (Stephen Adams)
Newsgroups: comp.lang.misc
Subject: Re: Compiler Costs
Message-ID: <SRA.90Jul17105145@alonzo.ecs.soton.ac.uk>
Date: 17 Jul 90 09:51:45 GMT
References: <1319@fs1.ee.ubc.ca> <56704@lanl.gov> <=AP4-:8@ggpc2.ferranti.com>
	<1990Jul16.163019.3933@diku.dk>
Sender: sra@ecs.soton.ac.uk
Organization: Southampton University Computer Science
Lines: 56
In-reply-to: njk@diku.dk's message of 16 Jul 90 16:30:19 GMT

In article <1990Jul16.163019.3933@diku.dk> njk@diku.dk (Niels J|rgen Kruse) writes:

 > peter@ficc.ferranti.com (Peter da Silva) writes:
 > 
 > }In article <56704@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
 > }[lookup table]
 > }> Works just fine (but still slower than the assemble - by a lot) - provided
 > }> that you are doing parity checking of something _small_, like a single
 > }> byte.  The table gets kind of large for a 32-bit integer.
 > 
 > }Luckily, parity is conserved. Thus you can use the byte lookup table 4 times
 > }over the word.
 > 
 > Better yet, xor the bytes together and then use the fine lookup table.
 > Parity is just the xor of all the bits in any old order, remember.

Indeed, you can use this property and `fold' the byte in
half using shift and xor.  Then fold the 4bit word in half
and so on until you have just one bit which is the parity.
The other bits in the word become junk but that doesnt
matter because you just ignore them.  This seems to work
quite fast in practice and doesnt require a lookup table.
On a RISC it should be about as fast as a lookup table as
all the work is done in registers.

	x = datum;
	x^=(x>>4);
	x^=(x>>2);
	x^=(x>>1);
	parity_bit = x&1;

It extends naturally to the 32bit case:

	x = datum;
	x^=(x>>16);
	x^=(x>>8);
	x^=(x>>4);
	x^=(x>>2);
	x^=(x>>1);
	parity_bit = x&1;

If you need to use the parity bit in the correct bit
position then shift the other way (bytes):

	x = datum;
	x^=(x<<4);
	x^=(x<<2);
	x^=(x<<1);
	/*parity_bit = x&0x80;*/
	x^=(x&0x80);   /* force even parity */


--
Stephen Adams                        S.Adams@uk.ac.soton.ecs (JANET)
Computer Science                     S.Adams@ecs.soton.ac.uk (Bitnet)
Southampton SO9 5NH, UK              S.Adams@sot-ecs.uucp    (uucp)