4 ms·

Rediscovering Hamming Code

52 points by juxhindb 5y ago

anonymousiam 5y ago
Re: "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.
- juxhindb 5y ago
  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.
  - saagarjha 5y ago
    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.
    - juxhindb 5y ago
      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.
      - juxhindb 5y ago
        An extension to this infact is the following - https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0e0f2134c17fd365272285/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L960 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. :-)
BugWatch 5y ago
Since it's a "digital horror", a "Hammer code" would have fit quite nicely.

52 points by juxhindb 5y ago

Re: "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.

juxhindb 5y ago
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.
- saagarjha 5y ago
  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.
  - juxhindb 5y ago
    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.
    - juxhindb 5y ago
      An extension to this infact is the following - https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0e0f2134c17fd365272285/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L960 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. :-)

BugWatch 5y ago

Since it's a "digital horror", a "Hammer code" would have fit quite nicely.