flat assembler
Message board for the users of flat assembler.

Index > Heap > algorithms for programmers

Author
Thread Post new topic Reply to topic
silkodyssey



Joined: 02 Oct 2003
Posts: 198
Location: St.Vincent & the Grenadines
silkodyssey
Haven't read it but from a quick glance it looks interesting.

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

_________________
silkodyssey
Post 24 Apr 2006, 18:05
View user's profile Send private message MSN Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Yeah, some time ago I started converting it to ASM Smile
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 mask_copy_bit,13,0010b,0100b ; == 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

proc mask_copy_bit a, msrc, mdst
; 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]
        add     eax,ecx
    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
        add     [a],eax
        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 Smile
Post 24 Apr 2006, 20:32
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
Average without overflow in x86 is just:
Code:
mov eax,[x]
add eax,[y]
rcr eax,1
adc eax,0 ; (optional) round up    
Post 14 Sep 2010, 06:35
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 can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.