Newsgroups: comp.lang.perl
Path: utzoo!utgpu!watserv1!watdragon!rose!ccplumb
From: ccplumb@rose.uwaterloo.ca (Colin Plumb)
Subject: Re: Even Parity Table Generation
Message-ID: <1991Feb13.205348.2779@watdragon.waterloo.edu>
Sender: daemon@watdragon.waterloo.edu (Owner of Many System Processes)
Organization: University of Waterloo
References: <121817@uunet.UU.NET>
Date: Wed, 13 Feb 1991 20:53:48 GMT
Lines: 51

rbj@uunet.UU.NET (Root Boy Jim) wrote:
>I needed an even parity table, so I decided to generate it recursively.
>I thought people might be interested in my solution, and or
>commenting on how it might be done better. And while I'm at it,
>I hereby request another function: chr(), the opposite of ord().
>Either that, or get rid of ord. Anyway, here it is:

Yes, I'd like chr() (or whatever someone wants to call it), too.

Anyway, there's a simple iterative way to generate bit-couting tables,
parity tables, etc.

bits[0] = 0;
for (i = 1; i < 256; i++)
	bits[i] = bits[i>>1] + (i&1);

For your parity application, it's just:

even[0] = 0;
for (i = 1; i < 128; i++)
	even[i] = i + ((even[i>>1]&128) ^ (i & 1 ? 128 : 0));

There are various tricky ways of rewriting that last line.  I think
	even[i] = i + (128 & (-(i & 1) ^ even[i>>1]));
is rather fun on a non-sign-magnitude machine.

In (untested) perl, that becomes:

sub mkEven # global %even
{
	local($i);
	$even{"\0"} = "\0";
	for $i (1..127) {
		$even{pack('c',$i)} = pack('c',$i +
		  (($i & 1) ? 128 : 0) ^ (128 & $even{pack('c',$i>>1)}));
	}
}

Well, okay, it's hideous...  Using a temporary array,
sub mkEven # global %even
{
	local($i,@even);
	$even[0] = 0;
	$even{"\0"} = "\0";
	for $i (1..127) {
		$even[$i] = ((i & 1) << 7) ^ $even[$i >> 1];
		$even{pack('c',$i)} = pack('c', $i + $even[$i]);
	}
}
-- 
	-Colin