flat assembler
Message board for the users of flat assembler.

 Index > Main > [solved] add trick 2
Author
Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 22 Jul 2011, 15:13
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

```

Any small asm algo appreciated.

Last edited by Picnic on 23 Jul 2011, 14:29; edited 1 time in total
22 Jul 2011, 15:13
r22

Joined: 27 Dec 2004
Posts: 805
r22 22 Jul 2011, 16:17
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 ...
22 Jul 2011, 16:17
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 22 Jul 2011, 18:18
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

22 Jul 2011, 18:18
edfed

Joined: 20 Feb 2006
Posts: 4330
Location: Now
edfed 22 Jul 2011, 18:25
Code:
```add_n_neg:
.min = -99
.max = -.min
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
22 Jul 2011, 18:25
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 22 Jul 2011, 18:37
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
sub eax, MIN
mov ecx, (MAX - MIN)
idiv        ecx
22 Jul 2011, 18:37
LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 22 Jul 2011, 19:42
This is just a remake of r22's code:
Code:
```; Input: EAX = [-MAX..MAX]; EDX = [-MAX..MAX]; Output: EAX

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

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

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
22 Jul 2011, 19:42
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 22 Jul 2011, 19:55
Picnic wrote:
Code:
```; examples:
; MAX=99, MIN=-MAX

```
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.
22 Jul 2011, 19:55
Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 22 Jul 2011, 20:10
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!
22 Jul 2011, 20:10
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 22 Jul 2011, 20:51
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.
22 Jul 2011, 20:51
MHajduk

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

.x:
22 Jul 2011, 21:17
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 22 Jul 2011, 22:21
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, (MAX - MIN) - MIN
mov     ecx, (MAX - MIN)
div      ecx

Sorry if I f****d something up - I'm so tired now.
22 Jul 2011, 22:21
edfed

Joined: 20 Feb 2006
Posts: 4330
Location: Now
edfed 22 Jul 2011, 23:09
xor edx,edx
mov ecx,max-min
lea eax,[eax+ebx+(max-min)-min]
div ecx
lea eax,[edx+min]
22 Jul 2011, 23:09
Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece
Picnic 23 Jul 2011, 14:29
Thanks all for the time and effort, quite enlightening posts.
edfed it loops between min & max sweet!
23 Jul 2011, 14:29
MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 23 Jul 2011, 18:20
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.

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.
23 Jul 2011, 18:20
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum