flat assembler
Message board for the users of flat assembler.

 Index > Heap > algorithms for programmers
Author
silkodyssey

Joined: 02 Oct 2003
Posts: 198
silkodyssey
Haven't read it but from a quick glance it looks interesting.

http://www.jjj.de/fxt/fxtbook.pdf

_________________
silkodyssey
24 Apr 2006, 18:05

Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Yeah, some time ago I started converting it to ASM
Code:
```; From the book of Algorithms for programmers
;                     ideas and source code
; by Jörg Arndt arndt@jjj.de
; These are translations of some (hopefully most)
; algorithms presented there, in C, to ASM
include 'win32ax.inc'
.code

start:
int3
stdcall copy_bit,13,1,2 ; == 9
stdcall bit_swap,13,1,2 ; == 11
stdcall bit_swap_01,13,1,2 ; == 11
stdcall max0,11 ; == 11
stdcall min0,-11 ; == -11
stdcall average,14,10 ; == 11
;invoke  MessageBox,HWND_DESKTOP,"Hi! I'm the example program!","Win32 Assembly",MB_OK
invoke  ExitProcess,0

.end start

BITS_PER_LONG = 32 ;64 if in long mode

;# Bit wizardry

;# 1.2 Copying and swapping bits

proc copy_bit a, src, dst
; Copy bit at [src] to position [dst]
mov     eax,[a]
mov     ecx,[src]
mov     edx,eax
shr     eax,cl
mov     ecx,[dst]
shr     edx,cl
xor     eax,edx
mov     edx,[a]
and     eax,1
shl     eax,cl
xor     eax,edx ;return in eax
ret
endp

; Copy bit according at src-mask (msrc)
; to the bit according to the dest-mask (mdst).
; Both msrc and mdst must have exactly one bit set.
mov     eax,[a]
mov     ecx,[msrc]
xor     edx,edx
and     ecx,eax
cmovz   edx,[mdst]
xor     edx,[mdst]
mov     ecx,[mdst]
not     ecx
and     eax,ecx
or      eax,edx
ret
endp

proc bit_swap a, k1, k2
; Return a with bits at positions [k1] and [k2] swapped.
; k1==k2 is allowed (a is unchanged then)
mov     eax,[a]
mov     edx,eax
mov     ecx,[k1]
shr     edx,cl
mov     ecx,[k2]
shr     eax,cl
xor     edx,eax
and     edx,1
mov     eax,edx
shl     edx,cl
mov     ecx,[k1]
shl     eax,cl
xor     edx,[a]
xor     eax,edx
ret
endp

proc bit_swap_01 a, k1, k2
; Return a with bits at positions [k1] and [k2] swapped.
; Bits must have different values (!)
; (i.e. one is zero, the other one)
; k1==k2 is allowed (a is unchanged then)
mov     eax,1
mov     edx,eax
mov     ecx,[k1]
shl     eax,cl
mov     ecx,[k2]
shl     edx,cl
xor     eax,edx
xor     eax,[a]
ret
endp

;# 1.3 Avoiding branches

proc max0 x
; Return max(0, x), i.e. return zero for negative input
mov     eax,[x]
mov     edx,eax
sar     edx,BITS_PER_LONG-1
not     edx
and     eax,edx
ret
endp

proc min0 x
; Return min(0, x), i.e. return zero for positive input
mov     eax,[x]
mov     edx,eax
sar     edx,BITS_PER_LONG-1
and     eax,edx
ret
endp

proc average x, y
; Use the fact that x+y == ((x&y)<<1) + (x^y)
; that is: sum == carries + sum_without_carries
mov     eax,[x]
mov     ecx,eax
xor     eax,[y]
shr     eax,1
and     ecx,[y]
ret
endp

proc upos_abs_diff a, b
; Branchless computation of the absolute difference |(| a-b)
; Both a and b must not have the most significant bit set
mov     eax,[b]
sub     eax,[a]
mov     ecx,eax
mov     edx,eax
shr     ecx,BITS_PER_LONG-1
and     edx,ecx
shl     edx,1
sub     eax,edx
ret
endp

proc upos_sort2 a, b
; Set {a, b} := {minimum(a, b), maximum(a,b)}
; Both a and b must not have the most significant bit set
mov     eax,[b]
sub     eax,[a]
mov     edx,eax
shr     edx,BITS_PER_LONG-1
and     eax,edx
sub     [b],eax
;long d = b - a;
;d &= (d>>(BITS_PER_LONG-1));
;a += d;
;b -= d;
ret
endp
```

I've held the reference "under my pillow" for a while already
24 Apr 2006, 20:32
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
Average without overflow in x86 is just:
Code:
```mov eax,[x]
rcr eax,1
adc eax,0 ; (optional) round up    ```
14 Sep 2010, 06:35
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials 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 can attach files in this forumYou can download files in this forum