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

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
Picnic wrote: Hi team, Here some questions arise:
a Θ b = (a+b  MIN) mod (MAX  MIN) + MIN 

22 Jul 2011, 18:18 

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 6521 = 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
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: 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
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 [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 

22 Jul 2011, 19:42 

MHajduk
Picnic wrote:
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
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
Picnic wrote: MHajduk, i get 92 not 88 using your code snippet with _add(90, 20) 

22 Jul 2011, 20:51 

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
I see another possibility. We can adjust the sum before 'div' to get always nonnegative 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
xor edx,edx
mov ecx,maxmin lea eax,[eax+ebx+(maxmin)min] div ecx lea eax,[edx+min] 

22 Jul 2011, 23:09 

Picnic
Thanks all for the time and effort, quite enlightening posts.
edfed it loops between min & max sweet! 

23 Jul 2011, 14:29 

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:
Code snippets modification Let's come back to the code snippets. Lines Code: add eax, (MAX  MIN)  MIN ; mine lea eax,[eax+ebx+(maxmin)min] ; edfed's Code: add eax, k*(MAX  MIN)  MIN ; mine lea eax,[eax+ebx+k*(maxmin)min] ; edfed's
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 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.