flat assembler
Message board for the users of flat assembler.

Index > Main > [solved] add trick 2

Author
Thread Post new topic Reply to topic
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Hi team,

I want to add 2 signed integers, reverse sign if result > MAX or result < MIN and continue addition.

Example with MAX = 99 adding 20 to 90 outputs -88 [ 91,92...99, (reverse) -98,-97...-88 ]

Code:
; examples:
; MAX=99, MIN=-MAX

; _add(90, 20)   =  -88
; _add(90, -20)  =  70
; _add(-90, 20)  =  -70
; _add(-90, -20) =  88
    


Any small asm algo appreciated.


Last edited by Picnic on 23 Jul 2011, 14:29; edited 1 time in total
Post 22 Jul 2011, 15:13
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
Code:
;eax = X ; 70
;ebx = Y ; 20
;ecx = MIN ; -99
;edx = MAX ; 99

ADD eax, ebx ; x = x + y ; 120
MOV ebx, 0 ; y = 0
CMP eax, edx ; x > MAX ; 120 > 99
CMOVG ebx, edx ; ? y = MAX ; 99
CMP eax, ecx ; x < MIN ; 120 < -99
CMOVL ebx, ecx ; ? y = MIN ;
SUB eax, ebx ; x = x - y ; 120 - 99 = 11
SUB eax, ebx ; x = x - y ; 11 - 99 = -88
    


Looks like it could work ...
Post 22 Jul 2011, 16:17
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Picnic wrote:
Hi team,

I want to add 2 signed integers, reverse sign if result > MAX or result < MIN and continue addition.

Example with MAX = 99 adding 20 to 90 outputs -88 [ 91,92...99, (reverse) -98,-97...-88 ]
Picnic, I'm not sure if I understood the conditions of your programming competition.

Here some questions arise:
  • can the MAX and MIN be arbitrarily chosen, or, oppositely, always is MIN = -MAX?

  • are you sure that "reversion" of the sign will make -98 from 100 (shouldn't be here -99)?
I assume that we can describe it as follows: for any numbers MIN ≤ a, b ≤ MAX we have defined operation of the modified addition (let's denote this operator as Θ), so sum a Θ b is in fact a+b modulo (MAX - MIN) translated by some vector:

a Θ b = (a+b - MIN) mod (MAX - MIN) + MIN

Smile
Post 22 Jul 2011, 18:18
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
Code:
add_n_neg:
.min = -99
.max = -.min
add eax,ebx
cmp eax,.min
jl .neg
cmp  eax,.max
jg .neg
ret
.neg:
neg eax
ret
    

and then, you just have to preload ebx with the new value to add, call add_n_neg to iterate.

but it would be preferable to do some ping pong action, because if not, a very far to bound addition will lead to an always outside bound result.

if you do some ping pong action, using max or min as a symetry axis, you will always decrease the difference between the value and the bounds, but substracting the bound from the value, in order to reflect the position inside.

the same thing is true if for example, the number to add to X is 45, X is originally 20, and max is 21.
what happens if min = -20? the result of the addition will be 65, greater than 21.
then, negation, and as a result, we have -65, that is lower than -20 (min), and then, another negation is made, and so on.
in the case of the algo of the topic, the value will constantlly oscillate between a value bigger than max, and a value loer than min.

if you do the ping pong algo, instead of negate, you sub min or max.
and if value is greater than max, in our case, it will become 65-21 = 44.
44 is between min and max, then, no more iteration required, the value will be stable.


Last edited by edfed on 22 Jul 2011, 18:42; edited 1 time in total
Post 22 Jul 2011, 18:25
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
MHajduk wrote:
I assume that we can describe it as follows: for any numbers MIN ≤ a, b < MAX we have defined operation of the modified addition (let's denote this operator as Θ), so sum a Θ b is in fact a+b modulo (MAX - MIN) translated by some vector:

a Θ b = (a+b - MIN) mod (MAX - MIN) + MIN
If this is exactly what we want to do then we have a such code:
Code:
; Input:
;       eax := a
;       ebx := b
;
; Output:
; edx := (a+b - MIN) mod (MAX - MIN) + MIN
;
xor        edx, edx
add eax, ebx
sub eax, MIN
mov ecx, (MAX - MIN)
idiv        ecx
add      edx, MIN    
Post 22 Jul 2011, 18:37
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
This is just a remake of r22's code:
Code:
; Input: EAX = [-MAX..MAX]; EDX = [-MAX..MAX]; Output: EAX
        add   eax, edx

        lea   ecx, [eax - 2*MAX]
        cmp   eax, MAX

        cmovg eax, ecx

        lea   ecx, [eax + 2*MAX]
        cmp   eax, -MAX

        cmovl eax, ecx    
Worked with Picnic's examples, but haven't checked any further. Not sure if this could be adapted to be as flexible as MHajduk's code, I'm more dumb than usual today Confused

[edit]This version although it has one more instruction it may be faster due to the removal of some dependencies:
Code:
; Input: EAX = [-MAX..MAX]; EDX = [-MAX..MAX]; Output: EAX
        add   eax, edx

        lea   ecx, [eax - 2*MAX]
        mov   edx, eax
        cmp   eax, MAX

        cmovg eax, ecx
        lea   ecx, [edx + 2*MAX]
        cmp   edx, -MAX

        cmovl eax, ecx    


Last edited by LocoDelAssembly on 22 Jul 2011, 20:03; edited 1 time in total
Post 22 Jul 2011, 19:42
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Picnic wrote:
Code:
; examples:
; MAX=99, MIN=-MAX

; _add(90, 20)   =  -88
; _add(90, -20)  =  70
; _add(-90, 20)  =  -70
; _add(-90, -20) =  88
    
Let's check my formula

a Θ b = (a + b - MIN) mod (MAX - MIN) + MIN

arithmetically:

_add(90, 20) = 90 Θ 20 =
= (90 + 20 - MIN) mod (MAX - MIN) + MIN =
= (90 + 20 - (-99)) mod (99 - (-99)) + (-99) =
= (110 + 99) mod (99 + 99) - 99 =
= 209 mod 198 - 99 =
= 11 - 99 = -88

Analogously we have:

_add(90, -20) = 90 Θ - 20 =
= (90 - 20 + 99) mod 198 - 99 =
= (70 + 99) mod 198 - 99 =
169 mod 198 - 99 =
169 - 99 = 70

_add(-90, 20) = -90 Θ 20 =
= (-90 + 20 + 99) mod 198 - 99 =
= (-70 + 99) mod 198 - 99 =
= 29 mod 198 - 99 =
= 29 - 99 = -70

_add(-90, -20) = -90 Θ - 20 =
= (-90 + (-20) + 99) mod 198 - 99 =
= (-110 + 99) mod 198 - 99 =
= (-11) mod 198 - 99 =
= 187 - 99 = 88

So, the main conditions of the exercise are met. Smile
Post 22 Jul 2011, 19:55
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
edfed, MIN = -MAX always, and the number to add is always < MAX and > MIN -sorry i did not mention that- but since result can exceed limits therefore this adjust, yes a ping pong like adjust.

MHajduk, i get 92 not 88 using your code snippet with _add(-90, -20)
I still have to test the formula.

LocoDelAssembly, i think your code gives me the results i need!
Post 22 Jul 2011, 20:10
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Picnic wrote:
MHajduk, i get 92 not 88 using your code snippet with _add(-90, -20)
I still have to test the formula.
Because 'idiv' is shitty and gives us also negative rests.
Post 22 Jul 2011, 20:51
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Some workaround here, but I don't like it:
Code:
; Input: 
;       eax := a 
;       ebx := b 
; 
; Output: 
;       edx := (a+b - MIN) mod (MAX - MIN) + MIN  
;
add     eax, ebx  
sub     eax, MIN  
mov     ecx, (MAX - MIN) 
cdq  
idiv    ecx
test       edx, edx
jns .x
add       edx, (MAX - MIN)

.x:
     add     edx, MIN    
Post 22 Jul 2011, 21:17
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
I see another possibility. We can adjust the sum before 'div' to get always non-negative values. I assume that MAX ≥ 0 and MAX > MIN.

For all integer k we have

(y + k*x) mod x = y mod x

so, we can add a multiply of (MAX - MIN) before division, and for small MIN and MAX this code should work properly:
Code:
; Input: 
;       eax := a 
;       ebx := b 
; 
; Output: 
;       edx := (a+b - MIN) mod (MAX - MIN) + MIN  
; 
xor     edx, edx  
add     eax, ebx
add    eax, (MAX - MIN) - MIN 
mov     ecx, (MAX - MIN)
div      ecx
add     edx, MIN    


Sorry if I f****d something up - I'm so tired now. Wink
Post 22 Jul 2011, 22:21
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
xor edx,edx
mov ecx,max-min
lea eax,[eax+ebx+(max-min)-min]
div ecx
lea eax,[edx+min]
Post 22 Jul 2011, 23:09
View user's profile Send private message Visit poster's website Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Thanks all for the time and effort, quite enlightening posts.
edfed it loops between min & max sweet!
Post 23 Jul 2011, 14:29
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Picnic, I'm glad because of your comment. Your excitation makes me sure that my method with "shifted" modulo slightly modified by edfed (really smart use of the 'lea' instruction) is correct. So, my yesterday's doubts were completely needless, cool. Razz


Just for the sake of completness, if anybody cares about it, I would like to add some considerations on the theme of adjustment before division.

Some theory

We want to adjust our sum a + b - MIN before division in a such "transparent" way that always dividend will be positive. We assume that MAX > MIN (it's quite natural assumption). Let's consider two complementary cases:

  1. MIN >= 0

    In this case expression

    a + b - MIN

    will be always greater or equal to 0, because "in the worst case" for a = MIN and b = MIN we will have

    a + b - MIN = MIN + MIN - MIN = MIN >= 0

  2. MIN < 0

    Now expression

    a + b - MIN

    can be (for some values of a and b) negative. We know that operation modulo is "transparent" (or, in other words, "insensitive") for the addition of the integer multiply of divisor to the argument:

    (y + k*x) mod x = y mod x

    Hence we get that

    (a + b + k*(MAX - MIN) - MIN) mod (MAX - MIN) = (a + b - MIN) mod (MAX - MIN)

    For every given pair of values MIN and MAX we want to find corresponding value of k that

    a + b + k*(MAX - MIN) - MIN >= 0

    Let's consider "the worst case", i.e. when a = b = MIN:

    MIN + MIN + k*(MAX - MIN) - MIN >= 0

    we have

    MIN + k*(MAX - MIN) >= 0

    and

    k*(MAX - MIN) >= -MIN

    finally

    k >= -MIN / (MAX - MIN)

    Note, that here everything is correct because always (MAX - MIN) > 0 from assumption.

    We want k to be integer. It is enough to take

    k = [-MIN / (MAX - MIN)] + 1

    Where [x] means the "floor" function (called also "entier").


Code snippets modification

Let's come back to the code snippets. Lines
Code:
add     eax, (MAX - MIN) - MIN ; mine

lea eax,[eax+ebx+(max-min)-min] ; edfed's    
should look like that:
Code:
add     eax, k*(MAX - MIN) - MIN       ; mine

lea eax,[eax+ebx+k*(max-min)-min] ; edfed's    
where
  • k = [-MIN / (MAX - MIN)] + 1 for MIN < 0

  • k = 0 for MIN >= 0

The change isn't big yet crucial when we would be talking about arbitrary MIN and MAX. Of course, in our special case when MAX = -MIN we have

k = [-MIN / (MAX - MIN)] + 1 = [-MIN / (-MIN - MIN)] + 1 = [-MIN / (-2MIN)] + 1 = [1/2] + 1 = 0 + 1 = 1

so, in this special case, both lines of code snippets will be the same as original ones. Smile
Post 23 Jul 2011, 18:20
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.