Rediscovering Hamming Code
blog.digital-horror.comRe: "fast" parity code in article. I always preferred the parity example from the (pre-ansi) K&R C Programming Language book:
#include <stdio.h>
main( argc, argv ) int argc; char *argv[];
{
unsigned source;
int parity;
if ( argc > 1 )
{
if ( sscanf( argv[1], "%d", &source ) == 1 )
{
printf( "%d = ", source );
for ( parity = 0; source; parity++ )
source &= ( source - 1 );
printf( "%d\n", parity & 1 );
}
}The function in the article is faster for > 8-bit values when there are more than eight ones in the value being checked. Also, I suppose theirs is better than K&R because it always executes in the same number of cycles.
Thanks for sharing that, love the simplicity behind it which is more intuitive than the example I had gone with.
I think the reason why I chose that particular one was to show how thinking about a problem from an entirely different angle can yield great (and rewarding) results.
Ideally, you'd want your compiler to use the hardware population count instructions though. So this might be one of the places where a simpler algorithm might win out because the compiler can recognize it.
In fact that is one of the follow-ups I want to have out of this. Have architecture-specific optimisations (popcnt on x86) either manually through something like the `asm` crate, or by having a simpler algorithm that the compiler can optimise away.
An extension to this infact is the following - https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0...
So the original user's comment might infact get detected by this and get optimised down to using popcnt. Will need to try it out. :-)
Since it's a "digital horror", a "Hammer code" would have fit quite nicely.