program CountingBits;
#include( "stdlib.hhf" );

	// bitCount-
	//
	//	Counts the number of "1" bits in a dword value.
	//	This function expects the dword value in EAX.
	
	procedure bitCount; 
		returns( "eax" ); 
		noframe; 
		nodisplay;
		
	const
		EveryOtherBit		:= $5555_5555;
		EveryAlternatePair	:= $3333_3333;
		EvenNibbles			:= $0f0f_0f0f;
		
	begin bitCount;
	
		push( edx );
		mov( eax, edx );
		
		// Compute sum of each pair of bits
		// in EAX.  The algorithm treats 
		// each pair of bits in EAX as a two
		// bit number and calculates the
		// number of bits as follows (description
		// is for bits zero and one, it generalizes
		// to each pair):
		//
		//	EDX = 	BIT1  BIT0
		//  EAX =      0  BIT1
		//
		//  EDX-EAX =	00 if both bits were zero.
		//				01 if Bit0=1 and Bit1=0.
		//				01 if Bit0=0 and Bit1=1.
		//				10 if Bit0=1 and Bit1=1.
		//
		// Note that the result is left in EDX.
		
		shr( 1, eax );
		and( EveryOtherBit, eax );
		sub( eax, edx );
		
		// Now sum up the groups of two bits to
		// produces sums of four bits.  This works
		// as follows:
		//
		//	EDX = bits 2,3, 6,7, 10,11, 14,15, ..., 30,31
		//		  in bit positions 0,1, 4,5, ..., 28,29 with
		//		  zeros in the other positions.
		//
		//	EAX = bits 0,1, 4,5, 8,9, ... 28,29 with zeros
		//		  in the other positions.
		//
		//	EDX+EAX produces the sums of these pairs of bits.
		//	The sums consume bits 0,1,2, 4,5,6, 8,9,10, ... 28,29,30
		//  in EAX with the remaining bits all containing zero.
		
		mov( edx, eax );
		shr( 2, edx );
		and( EveryAlternatePair, eax );
		and( EveryAlternatePair, edx );
		add( edx, eax );
		
		// Now compute the sums of the even and odd nibbles in the
		// number.  Since bits 3, 7, 11, etc. in EAX all contain
		// zero from the above calcuation, we don't need to AND
		// anything first, just shift and add the two values.
		// This computes the sum of the bits in the four bytes
		// as four separate value in EAX (AL contains number of
		// bits in original AL, AH contains number of bits in
		// original AH, etc.)
		
		mov( eax, edx );
		shr( 4, eax );
		add( edx, eax );
		and( EvenNibbles, eax );
		
		// Now for the tricky part.
		// We want to compute the sum of the four bytes
		// and return the result in EAX.  The following
		// multiplication achieves this.  It works
		// as follows:
		//	(1) the $01 component leaves bits 24..31
		//		in bits 24..31.
		//
		//	(2) the $100 component adds bits 17..23
		//		into bits 24..31.
		//
		//	(3) the $1_0000 component adds bits 8..15
		//		into bits 24..31.
		//
		//	(4)	the $1000_0000 component adds bits 0..7
		//		into bits 24..31.
		//
		//	Bits 0..23 are filled with garbage, but bits
		//	24..31 contain the actual sum of the bits
		//	in EAX's original value.  The SHR instruction
		//	moves this value into bits 0..7 and zeroes
		//	out the H.O. bits of EAX.
		 
		intmul( $0101_0101, eax );
		shr( 24, eax );
		
		pop( edx );
		ret();
		
	end bitCount;
		
	
	
begin CountingBits;

	mov( 32, ecx );
	mov( 0, ebx );
	repeat
	
		mov( ebx, eax );
		bitCount();
		stdout.put
		( 
			"# of bits in $", 
			ebx, 
			" is ", 
			(type uns32 eax), 
			nl 
		);
		stc();
		rcl( 1, ebx );
		dec( ecx );
		
	until( @z );
	
end CountingBits;