flat assembler
Message board for the users of flat assembler. Index > Main > [solved] add trick 2
Author
 Thread  Picnic

Joined: 05 May 2007
Posts: 1288
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

```

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 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: 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  22 Jul 2011, 18:18
 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 22 Jul 2011, 18:25
 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 ``` 22 Jul 2011, 18:37
LocoDelAssembly

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

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

Joined: 05 May 2007
Posts: 1288
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! 22 Jul 2011, 20:10  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. 22 Jul 2011, 20:51
 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 ``` 22 Jul 2011, 21:17
 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.  22 Jul 2011, 22:21
 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] 22 Jul 2011, 23:09
Picnic

Joined: 05 May 2007
Posts: 1288
Picnic
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: 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. 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: 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 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