rbj@uunet.UU.NET (Root Boy Jim) (02/09/91)
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:
print time,"\n"; &mkEven(7);
print time,"\n"; &prtEven;
print time,"\n"; exit(0);
sub mkEven # global %even (level)
{
local($_,$k) = @_;
$_ || return $even{"\0"} = "\0"; # bottom out
&mkEven(--$_); # lower half
$_ = 1 << $_; # next bit
for $k (keys %even) { # key loop
$even{pack('c',$_^ord($k))} = # new key
pack('c',128^$_^ord($even{$k})); # new value
}
}
sub prtEven
{
for (sort keys(%even)) {
printf("%x %x\n",ord($_),ord($even{$_}));
}
}
--
Root Boy Jim Cottrell <rbj@uunet.uu.net>
I got a head full of ideas
They're driving me insanelwall@jpl-devvax.JPL.NASA.GOV (Larry Wall) (02/12/91)
In article <121817@uunet.UU.NET> rbj@uunet.UU.NET (Root Boy Jim) writes: : 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. How 'bout: sub chr {sprintf("%c",$_[0]);} : Anyway, here it is: [recursive solution omitted] I'd just say: #!/usr/bin/perl for (0 .. 127) { $bits = unpack('B8',pack('C',$_)); printf "%x %x\n", $_, $_ | ((($bits =~ tr/1/1/) & 1) << 7); } or maybe for (0 .. 127) { $bits = unpack(B8,pack(C,$_)); $bits =~ s/0/1/ if $bits =~ tr/1// & 1; printf "%x %x\n", $_, unpack(C,pack(B8, $bits)); } (Requires 3.0 patchlevel 44.) Larry
rbj@uunet.UU.NET (Root Boy Jim) (02/12/91)
In article <11387@jpl-devvax.JPL.NASA.GOV> lwall@jpl-devvax.JPL.NASA.GOV (Larry Wall) writes: >In article <121817@uunet.UU.NET> rbj@uunet.UU.NET (Root Boy Jim) writes: >: I hereby request another function: chr(), the opposite of ord(). >: Either that, or get rid of ord. > >How 'bout: > > sub chr {sprintf("%c",$_[0]);} Yes, I know that it can be done that way, or I can use pack, as I did. I suppose I can use use vec. Which is most efficient? However, I would rather have one primitive to SAY WHAT I MEAN rather than having to simulate it from a subroutine call and a more general primitive. I have heard that ord preceded pack/unpack and that's why it's there. >: Anyway, here it is: >[recursive solution omitted] > >I'd just say: > >[iterative solution deleted] Well, if we want to slice bits, how about: #!/usr/bin/perl for (0 .. 127) { $x = $_; $_ ^= $_>>4; $_ ^= $_>>2; $_ ^= $_>>1; printf "%x %x\n", $x, $x ^ (($_ & 1) << 7); } -- Root Boy Jim Cottrell <rbj@uunet.uu.net> I got a head full of ideas They're driving me insane
allbery@NCoast.ORG (Brandon S. Allbery KB8JRR) (02/14/91)
As quoted from <121817@uunet.UU.NET> by rbj@uunet.UU.NET (Root Boy Jim): +--------------- | I hereby request another function: chr(), the opposite of ord(). | Either that, or get rid of ord. Anyway, here it is: +--------------- sub chr { pack('c', @_[$[]); } ++Brandon -- Me: Brandon S. Allbery VHF/UHF: KB8JRR on 220, 2m, 440 Internet: allbery@NCoast.ORG Packet: KB8JRR @ WA8BXN America OnLine: KB8JRR AMPR: KB8JRR.AmPR.ORG [44.70.4.88] uunet!usenet.ins.cwru.edu!ncoast!allbery Delphi: ALLBERY
ccplumb@rose.uwaterloo.ca (Colin Plumb) (02/14/91)
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
shaw@paralogics.UUCP (Guy Shaw) (03/12/91)
One non-recursive way to generate a parity table is to count through the
character set in (binary reflected) Gray code order. Since the successor
of any Gray code number changes only one binary digit, the parity will
flip back and forth between even and odd.
#! /usr/local/bin/perl
# For purposes of demonstration,
# print out the first 32 Gray code numbers
print "bin gray\n";
print "--- ---\n";
for $i (0..31) {
printf "%3x %3x\n", $i,$i^($i>>1);
}
print "\n";
&MakeEvenParityTable;
# Generate full 256-entry even parity table,
# but just print the first 32
for $i (0..31) {
printf "%3x %3x\n", $i,$even[$i];
}
exit 0;
sub MakeEvenParityTable {
local($bin,$gray,$parity);
$even[0] = 0;
$parity = 0;
for $bin (1..255) {
$gray = $bin ^ ($bin>>1);
$parity = $parity ^ 128;
$even[$gray] = $gray | $parity;
}
}
--
Guy Shaw
Paralogics
paralogics!shaw@uunet.uu.net or uunet!paralogics!shaw