Re: Woz range check code explanation?

From: Michael Beck (spamtrap_at_crayne.org)
Date: 11/11/04 

Date: Thu, 11 Nov 2004 18:23:33 +0000 (UTC)

Jim Leonard wrote:

Ok, for those who care here the complete explanation of the code:
>
> This checks if a value is within one of two subranges N1...N2 or
> N3...N4.
>
> ; Test range N1 through N2
> eor #N1 ; Make low range start at 0
> cmp #(N2-N1)+1 ; Test low range valid
> bcc valid ; Valid low range
>
> ; Test range N3 through N4
> adc #$FE - ( N4 eor N1 ) ; Make high range end at $FF
> cmp #$FF - ( N4 - N3 ) ; Test high range validity
> bcc error ; Invalid high range
> and #$0F ; Restore true hex value
> valid:
>
> Note that the #$FE is actually #$FF since CF is set.
>
> To use this to check for valid ASCII hex digits and convert them to
> binary hex:
>
> N1 = $30, N2 = $39, N3 = $41, N4 = $46
>
> eor #$30
> cmp #$0A
> bcc valid
> adc #$88 ; ( = $89 - clc )
> cmp #$FA
> bcc error
> and #$0F
> valid:
>
> (I still rate this as one of the neatest asm hacks I've ever seen).

This code uses the following "Trick" to do a range change with ONE compare:

if N1 <= N2

N1 <= a <= N2 <==> a - N1 <u= N2-N1 <==> a - N1 <u N2-N1+1

Note that the second <= must be an unsigned compare (using the CARRY flag on
6502). It works even if a underflow occurs. A proof can be found in teh
excelent book "Hacker's Delight" by Henry S. Warren.

The 6502 did not have a SUB instructions, just a SBB (sub with borrow) which
would requiere an SEC (set CARRY) if the state of the carry flag is not
known to be set.

To save this instruction, Steve used an EOR which works because N1 is 0x30,
so:

a ^ 0x30 == a - 0x30 for the lowest 4 bit.

because N2 is 0x39, the difference is 9 which fits into the "right" 4 bit.

The second test uses a similiar trick:

if N3 <= N4

N3 <u= a <u= N4 <==>
N3 + (MAX-N4) <u= a + (MAX-N4) <u= N4 + (MAX-N4) <==>
N3 + (MAX-N4) <u= a + (MAX-N4) <u= MAX <==>
N3 + (MAX-N4) <u= a + (MAX-N4)

MAX is the highest unsigned value, so the test a + (MAX-N4) <u= MAX
is always true and can be omitted. For 8 bit values, MAX is 0xFF.

Before we use that we must correct the effect of the EOR.
To do this, the "right" range is now N3 ^ N1 ... N4 ^ N1, in our case
0x11 .. 0x16. Again, this works only, because the difference between N3 and
N4 is less than 4 bit, so the EOR transform the interval uniformly.
(Or more precisely, N3 AND N1 == N4 AND N1, so the EOR changes the same
bits).

Now we add #$FF - ( N4 eor N1 ) which is #$E9, so the code must be

adc #$E8

this transforms the range into 0xFA .. 0xFF. Using the wrap around
we know that it is sufficient to test the lower border.

So, this 2 range checks works only if:

N1 is of the form xxx0..0
N2 - N1 < 10..0 (same number of zeros as above)
N4 AND N1 == N3 AND N1

And all this to save just the SEC :-) Ah, the old times ...

Returning to x86:

The following works for any range N1..N2, N3..N4:

for one range check the following code is the best

sub al, N1
cmp al, (N2-N1)+1

for more range checks do

add al, N1-N3
cmp al (N4-N3)+1

but a xlat may be faster for 2 or more range checks, because you can check
all ranges with one cmp instruction ...

best regards, 

-- 
Michael Beck            beck@ipd.info.uni-karlsruhe.de

Relevant Pages

  • Re: IA-32 Overflow Query
    ... There is neither a signed nor unsigned add or sub (=cmp) instruction. ... numbers and OVERFLOW signals an overflow for signed numbers), ...
    (alt.lang.asm)
  • Re: IA-32 Overflow Query
    ... > There is neither a signed nor unsigned add or sub instruction. ... > only one add and sub (cmp) instruction. ... > numbers and OVERFLOW signals an overflow for signed numbers), ...
    (alt.lang.asm)
  • Re: Fastest way to highlight printable ASCII?
    ... cmp al,33 ... or ah,00001000b {highlight foreground by setting intensity bit} ... loop @writeloopfast ... sub al,33 ...
    (comp.lang.asm.x86)
  • Re: All is right !
    ... call convert;modify AL set carry/NC on error/GOOD ... mov dx, ... cmp al,3ah ... sub al,07h ...
    (alt.lang.asm)
  • Re: Pick the odd one out.
    ... We have a compare instruction with two ... But to express that we want to compare bytes we have add a "BYTE" somewhere ... (the best place would be the cmp -> cmp.b), ... cmp BYTE PTR, 0 ...
    (alt.lang.asm)