Re: Fwd: how this C code works?

["Rajesh Kankaria" <rk@xxxxxxxxxxxxxx>]

Diwakar, I have fwd. your C Code this to a frnd of mine and he replied me
back with this..he also sent another C program.

Tapan wrote: >>

Hi Rajesh,

Many C programmers are poets too. The guy who wrote this knows the language
of binary maths so well that it is difficult not to be very impressed.

Briefly, this is how it works:

The macro function BX_(x) takes a 32-bit word x and analyses it
nibble-by-nibble. It returns a 32-bit binary word that contains the
nibble-wise bit count in the respective nibble. For example if x is 0010
0111 0101 1111, BX_ returns 0x01121122. You will see that the each nibble in
the result contains the count of bits in the respective nibble in x.

The macro function BITCOUNT uses BX_ to, first consolidate the bitcounts in
nibbles to bitcounts in bytes. This is done in the code section:
    ((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F)
Here, the result of BX_ is added to itself shifted right by 4 bits, thus
giving even numbered nibbles the correct bit count of the corresponding
byte. The "filter" of 0x0F0F0F0F is applied to the result to remove odd
numbered nibble values which are no longer needed. This, using the previous
example, BX_ of 0x01121122 results in 0x01030204.
Having accomplished this, BITCOUNT makes a very clever use of modulo
arithmetic to consoludate the four bytes into one. So, the prevous result is
applied to modulo 255 and this results in 10, which is the total number of
bits in x!

Thanks a ton, Rajesh. This was a very satisfying way of spending an hour in
a holiday morning. And, my complements to the creator of the code.

Best Regards,
Tapan

----------
Dear Rajesh,
Further to the "weird" C code you had sent me, here is a C program to
generate permutation or combinations of character arrays. It can be extended
to permute objects of any kind. Should be useful for various applications.
See if you can understand how it works.

Regards,
Tapan

-----------------------------
/*
PERMUTE.C - Recursive Permutation Generator
by Tapan A. Desai, 1992
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *out_str;


void permute(char *h,char *s)
{ 
static int count=0; 
char *d; 
int k,n; 

d=(char *)malloc(strlen(s)+1); 
for(k=0;*h=s[k];k++) { 
// This 'if' block filters out repetitions 
if(k>0) { 
for(n=k-1;n>=0 && *h!=s[n];n--); 
if(n>=0) continue; 
} 
strcpy(d,s); 
d[k]=*s; 
permute(h+1,d+1); 
if(!s[1]) printf("%-4d : %s\n",++count,out_str); 
} 

free(d); 
} 


void main(int argc,char *argv[]) 
{ 
out_str=(char *)malloc(strlen(argv[1])+1); 
out_str[strlen(argv[1])] = 0; 
permute(out_str,argv[1]); 
free(out_str); 
} 

------------
> >this came from a friend of mine. can somebody crack this? - Diwakar
> >
> >This came as the Unix fortune - can someone decipher? Thanks, Alan -
> >
> >#define BITCOUNT(x)     (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
> >#define  BX_(x)         ((x) - (((x)>>1)&0x77777777)                    \
> >                             - (((x)>>2)&0x33333333)                    \
> >                             - (((x)>>3)&0x11111111))
> >
> >
> >-- really weird C code to count the number of bits in a word