Here is a quick code fragment I wrote to calculate the hamming distance between two bytes in registers AL and AH. The Hamming Distance is stored in DX. Can anybody find if I made any errors? Is the logic right in this code? Thanks.

``calculate:cmp AL, 1je cal1cal0:cmp AH, 0jne no_matchjmp matchcal1:cmp AH, 1jne no_matchjmp matchno_match:inc DXinc CXcmp CX, 8je doneshl AL, 1shl AH, 1jmp calculatematch:inc CXcmp CX, 8je doneshl AH, 1shl AL, 1jmp calculate``
Posted on 2009-10-26 19:51:24 by dre
Well, "cal1" is a lousy name for a label - looks too much like the "call" instruction. But it'll work...

As for your logic... try a test case. Imagine al=2, ah=2. My memory is fuzzy on "Hamming distance", but I think it should be zero. First compare fails, so we "fall through". Second compare fails, so we go to "no_match" and bump the counter in dx. No, your logic isn't right. :(

You might want to take a look at the "test" instruction. It'll check to see if just one bit is one or zero.

Better yet, look at the "xor" instruction. If you were to "xor al, ah", bits that were the same in each would be zero, bits that differ would be one. Now (if I remember what "Hamming distance" is) the number of set bits in al would be the Hamming distance. Couning them would be a "population count" - Google for "efficient" ways to do a "population count"... I think there's even a "popcnt" instruction on some CPUs (?).

A naive way to do it would involve the fact that a bit "shifted out" of a register ends up in the carry flag. The "adc" instruction includes the carry flag in its add. "adc dx, 0" after a shift, looped through 8 times, would count 'em for ya.

I suspect that something like that is what you're "supposed" to be doing for this. Your method could probably be made to work, too, but not with "cmp al, 1".

Best,
Frank

Posted on 2009-10-26 20:52:58 by fbkotler
Does this look any better?

``check:and AL, 1jz bit_zerojnz bit_onebit_zero:and AH, 1jz matchjnz no_matchbit_one:and AH, 1jz no_matchjnz matchno_match:inc CXinc DXcmp CX, 8je doneshl AL, 1shl AH, 1jmp checkmatch:inc CXcmp CX, 8je doneshl AL, 1shl AH, 1jmp check``
Posted on 2009-10-26 21:25:55 by dre
"and" alters the first operand. Is this what you want? Look into the difference between "and" and "test". You're on the right track.

Best,
Frank

Posted on 2009-10-27 00:28:09 by fbkotler
Isn't it simpler to calculate population (i.e. number of bits set) of al XOR ah? There are many tricks to do that (keywords: bit twiddling hacks), SSE4.2 even include opcode for that.
Posted on 2009-10-27 01:48:06 by baldr
``;;Hamming Distance AL <-> AH ;;USES/DESTROYES AL CX DX  XOR AL, AH ;;AL now has set bits for all differences with AH  MOV CX, 8 ;;set loop counter to 8  MOV DX, 0 ;;ZERO DXCountAndAccum: ;;loop label for jump  SHL AL, 1 ;;Shift AL 1 bit to the left  ADC DX, 0 ;;Add AL's shifted bit to DX  DEC CX ;;subtract 1 from CX  JNZ CountAndAccum ;;WHILE CX != 0 LOOP``

Writing in ASM doesn't given you "open season" to throw out good programming practices.
- COMMENT YOUR CODE SO IT CAN BE UNDERSTOOD
- USE MEANINGFUL LABEL NAMES
Posted on 2009-10-27 09:53:09 by r22
r22,

XOR DX, DX is Intel®'s approved method of setting DX to 0.
Obvious comments should be banned, period.
No need for loop counter (how much bits in 00h are 1? ;-).

``;;; Hamming distance;;; Expects: codes in ah and al ;;; Returns: distance in ax;;; Uses/Destroys: flags ;-)	xor	ah, al	; ah contains 1 in different bit positions	xor	al, al	; al will count themnext:	shr	ah, 1	; CF contains next bit from ah	ja	next	; if neither CF nor ZF set, shift again	jnc	done	; if CF not set then ZF set from shr => ah==0 => done	inc	al	; got 1 bit, count it	jmp	nextdone:			; ah == 0, al (and ax therefore) == Hamming distance``

It shifts ah one more time than needed, but that greatly simplifies loop exit condition.
Posted on 2009-10-27 11:15:24 by baldr
Thanks for everyone's help.
Posted on 2009-10-28 11:01:51 by dre