Optimizing a Conditional (asm)

[utz]

Hi,

Been twisting my head over this little assembly problem for quite some time without much progress. I have a nested conditional that I want to calculate as fast as possible and in constant time.

Assuming three 8-bit integers a, b, and d, I want to calculate the following:

Code: Select all

if (abs(a - b) > d) {
  if (a > b) return a + d;
  else return a - d;
} else return b;

Thought about various ways of transforming the darned thing. Eg. the following should be equivalent (unless I messed things up):

Code: Select all

if (b > a) {
  if (b - a > d) return a + d;
  else return b;
} else {
  if (a - b > d) return a - d;
  else return b;
}

A couple of ideas that led to nowhere so far:
1. In the second version, (b - a > d) could be replaced by (a + d <= b) or probably (a + d < b), so the return value for the true branch would already be calculated in the condition.
2. This looks kind of interesting:

Code: Select all

; b is in reg A, a is in reg B, d is in reg D
sub b
sbc a,a
xor d
; if (b > a) return d else return -d - 1

So, any ideas? I'd preferably want to do it with just 3 registers, though I would sacrifice a fourth for a significant speed boost. The inputs can be trashed. On entry the HL register will point to d, but (hl) should not be trashed.

[Ast A. Moore]

Okay, not by way of helping (I’m pretty bad at this sort of math), but by way of making sure I understand your logic correctly, does this at least get the principle right?

Code: Select all

	 ld a,20
	 ld b,30
	 ld hl,integer_D

	 sub b
	 or a
	 jp p,1$
	 neg
1$	 cp (hl)
	 jr nc,2$
	 xor b
	 cp b
	 jr nc,3$
	 sub (hl)
	 ret
3$	 add a,(hl)
	 ret
2$	 ld a,b
	 ret

integer_D
	defb 40

(I’ll get my coat.)

[djnzx48]

Perhaps you could calculate a - b and return a value depending on what range the result falls in, but this is assuming the difference between a and b is not greater than 128. For example:

Code: Select all

0       <= a - b < d       : result is b
d       <= a - b < 128     : result is a + d
128     <= a - b < 256 - d : result is a - d
256 - d <= a - b < 256     : result is b

Then the routine could go something like this (obviously not constant time). The logic can be simplified if the value of d is allowed to remain constant.

Code: Select all

    sub b
    cp d
    jr c, exit_b
    cp 127
    jr c, exit_add
    cp 256-d
    jr c, exit_sub
    
exit_b:
    ld a, b
    ret
    
exit_add:
    add a, b
    add a, d
    ret
    
exit_sub:
    add a, b
    sub d
    ret

[djnzx48]

How about this? Constant time, 47 T-states.

Code: Select all

    cp b
    jp nc, subtract
    add a, (hl)
    cp b
    jr c, exit
    ld a, b
    ret nc
    
subtract:
    sub (hl)
    cp b
    jr nc, exit
    ld a, b
    ret c

exit:
    ret

Edit: after examining the specifications more closely, I think your two examples have different behaviour. If so, this routine should correspond to the second example.

[utz]

Ast A. Moore: Some nice voodoo with parity there But looks like it doesn't produce the desired output, unfortunately.

djnzx48: Hmm, maybe I should've just posted a naïve asm implementation instead of being clever in the middle of the night. In any case, your second snippet does the right thing. So thanks a lot.

Regarding your first post, unfortunately I can guarantee neither abs(a-b) <= 128 nor a constant d. However, I realized I don't actually care about the lower nibble of the result, and I can guarantee that (d & 0xf) = 0. Maybe that helps in some way?