Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: A binary search algorithm that searches for an element similar to the key
22 views
Skip to first unread message
io_x
Dec 23, 2011, 1:45:45 PM12/23/11
to
NGs comp.lang.c,alt.lang.asm
"88888 Dihedral" <dihedr...@googlemail.com> ha scritto nel messaggio
news:16923526.318.1324470963080.JavaMail.geo-discussion-forums@prez15...
>I wrote a binary search in assembly in 386 20 years ago.
>
> This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
> 32 bit general registers and a stack that can be pushed and popped.
>
> I suggest you store the array starting address in ESI and use EDI as a
> general
> pointer in the heap.
>
> A program in C code within 20 lines should be coded in assembly easily for
> professionals in any 32 bit cpu easily.
>
> I'll warn any programmer that dare to use any lousy name of any variable
> to be a pointer witout ptr* or p* in the name under my supervision.
>
>
> Then I'll ask the programmer to convert the program into a specified assembly
> to prove the programmer is not stealing codes form others and faking to be
> his own works.
this is the implemention to the one in k&r2 so it is not my work 100%
i had one try on that in .asm. I use RosAsm with one my home
made asm macro language; i don't know if it is right...
i like all that, these simple little instruction that goes togheter...
fuck all hlls languages
; return -10 error, 0 not find, address of the found element in array
; would be like the C library one, with the only difference return -10 for error
; and use type without UB, and not admit index with (i32) indx<0
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
push ebx
push esi
push edi
push ebp
push ebp
;int3
cmp dword[esp+ 24], 0
je .e
cmp dword[esp+ 28], 0
je .e
cmp dword[esp+ 36], 0
jle .e
cmp dword[esp+ 40], 0
je .e
cmp dword[esp+ 32], 0
je .nf
jl .e
jmp short .1
.nf: mov eax, 0
clc
jmp short .z
.e: mov eax, -10
stc
jmp short .z
.1: mov esi, 0
mov edi, dword[esp+ 32]
dec edi
mov ebx, dword[esp+ 40]
.2: cmp esi, edi
ja .nf
mov ebp, esi
add ebp, edi
jc .e
shr ebp, 1 ; k=(i+j)/2
mov eax, dword[esp+ 36]
mul ebp
cmp edx, 0
jne .e
mov edx, dword[esp+ 24]
add eax, dword[esp+ 28]
mov dword[esp+ 0], eax
push edx
push eax
call ebx
add esp, 8
cmp eax, 0
jge .3
mov edi, ebp
sub edi, 1
jmp short .2
.3: cmp eax, 0
jle .4
mov esi, ebp
add esi, 1
jmp short .2
.4: mov eax, dword[esp+ 0]
clc
.z:
pop ebp
pop ebp
pop edi
pop esi
pop ebx
ret 20
this is the C program to experiment the above
#include <stdio.h>
#include <stdlib.h>
#define u32 unsigned
#define i32 int
#define u8 unsigned char
#define R return
#define P printf
u8* __stdcall
binSearchR(u8* InOutPKey, u8* InBase,
u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
i32 cmpu32(u8* elm1, u8* elm2)
{ if(*elm1>*elm2) R -1;
else if(*elm1<*elm2) R 1;
else R 0;
}
int main(void)
{u32 v[]={0, 2, 5, 7, 8, 8, 9, 13, 20}, val=13;
u8 *r;
r=binSearchR((u8*)&val, (u8*) v, 9, sizeof(u32), cmpu32);
if(r!=0) P("r=%p find=%u\n", (void*)r, *r);
R 0;
}
this is the origin like RosAsm .dll
----------------------------
PREPARSE MACRO2D
section DATA
hInstance dd 0
; 9
arrayInt dd 0,2,4,5,8,8,9,10, 11
export binSearchR
section TEXT
; return -10 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -10 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
<b,i,j,k,k
;int3
^24==0#.e|^28==0#.e |^36<=0?#.e
^40==0#.e|^32==0#.nf|<?#.e|#.1
.nf: a=0 |clc|#.z
.e: a=-10|stc|#.z
.1: i=0 |j=^32|--j|b=^40
.2: i>j#.nf
k=i |k+=j |jc .e |k>>=1 ; k=(i+j)/2
a=^36|mul k|r!=0#.e|r=^24|a+=^28|^0=a
b<(a,r)|a<0!?#.3|j=k|j-=1|#.2
.3: a>0!?#.4|i=k|i+=1|#.2
.4: a=^0|clc
.z:
>b,i,j,k,k
ret 20
Main:
mov eax D$esp+8
mov D$hInstance eax
mov eax 1
ret 12
"88888 Dihedral" <dihedr...@googlemail.com> ha scritto nel messaggio
news:16923526.318.1324470963080.JavaMail.geo-discussion-forums@prez15...
>I wrote a binary search in assembly in 386 20 years ago.
>
> This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
> 32 bit general registers and a stack that can be pushed and popped.
>
> I suggest you store the array starting address in ESI and use EDI as a
> general
> pointer in the heap.
>
> A program in C code within 20 lines should be coded in assembly easily for
> professionals in any 32 bit cpu easily.
>
> I'll warn any programmer that dare to use any lousy name of any variable
> to be a pointer witout ptr* or p* in the name under my supervision.
>
>
> Then I'll ask the programmer to convert the program into a specified assembly
> to prove the programmer is not stealing codes form others and faking to be
> his own works.
this is the implemention to the one in k&r2 so it is not my work 100%
i had one try on that in .asm. I use RosAsm with one my home
made asm macro language; i don't know if it is right...
i like all that, these simple little instruction that goes togheter...
fuck all hlls languages
; return -10 error, 0 not find, address of the found element in array
; would be like the C library one, with the only difference return -10 for error
; and use type without UB, and not admit index with (i32) indx<0
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
push ebx
push esi
push edi
push ebp
push ebp
;int3
cmp dword[esp+ 24], 0
je .e
cmp dword[esp+ 28], 0
je .e
cmp dword[esp+ 36], 0
jle .e
cmp dword[esp+ 40], 0
je .e
cmp dword[esp+ 32], 0
je .nf
jl .e
jmp short .1
.nf: mov eax, 0
clc
jmp short .z
.e: mov eax, -10
stc
jmp short .z
.1: mov esi, 0
mov edi, dword[esp+ 32]
dec edi
mov ebx, dword[esp+ 40]
.2: cmp esi, edi
ja .nf
mov ebp, esi
add ebp, edi
jc .e
shr ebp, 1 ; k=(i+j)/2
mov eax, dword[esp+ 36]
mul ebp
cmp edx, 0
jne .e
mov edx, dword[esp+ 24]
add eax, dword[esp+ 28]
mov dword[esp+ 0], eax
push edx
push eax
call ebx
add esp, 8
cmp eax, 0
jge .3
mov edi, ebp
sub edi, 1
jmp short .2
.3: cmp eax, 0
jle .4
mov esi, ebp
add esi, 1
jmp short .2
.4: mov eax, dword[esp+ 0]
clc
.z:
pop ebp
pop ebp
pop edi
pop esi
pop ebx
ret 20
this is the C program to experiment the above
#include <stdio.h>
#include <stdlib.h>
#define u32 unsigned
#define i32 int
#define u8 unsigned char
#define R return
#define P printf
u8* __stdcall
binSearchR(u8* InOutPKey, u8* InBase,
u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
i32 cmpu32(u8* elm1, u8* elm2)
{ if(*elm1>*elm2) R -1;
else if(*elm1<*elm2) R 1;
else R 0;
}
int main(void)
{u32 v[]={0, 2, 5, 7, 8, 8, 9, 13, 20}, val=13;
u8 *r;
r=binSearchR((u8*)&val, (u8*) v, 9, sizeof(u32), cmpu32);
if(r!=0) P("r=%p find=%u\n", (void*)r, *r);
R 0;
}
this is the origin like RosAsm .dll
----------------------------
PREPARSE MACRO2D
section DATA
hInstance dd 0
; 9
arrayInt dd 0,2,4,5,8,8,9,10, 11
export binSearchR
section TEXT
; return -10 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -10 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
<b,i,j,k,k
;int3
^24==0#.e|^28==0#.e |^36<=0?#.e
^40==0#.e|^32==0#.nf|<?#.e|#.1
.nf: a=0 |clc|#.z
.e: a=-10|stc|#.z
.1: i=0 |j=^32|--j|b=^40
.2: i>j#.nf
k=i |k+=j |jc .e |k>>=1 ; k=(i+j)/2
a=^36|mul k|r!=0#.e|r=^24|a+=^28|^0=a
b<(a,r)|a<0!?#.3|j=k|j-=1|#.2
.3: a>0!?#.4|i=k|i+=1|#.2
.4: a=^0|clc
.z:
>b,i,j,k,k
ret 20
Main:
mov eax D$esp+8
mov D$hInstance eax
mov eax 1
ret 12
io_x
Dec 24, 2011, 12:45:34 AM12/24/11
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
news:4ef4cb7b$0$1387$4faf...@reader2.news.tin.it...
i rewrote it
in
; return -10 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -10 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
; would be like the C one, with the only difference return -10 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
mov ebp, esi
add ebp, edi
jc .e
shr ebp, 1 ; k=(i+j)/2
mov eax, dword[esp+ 36]
mul ebp
cmp edx, 0
jne .e
mov edx, dword[esp+ 24]
add eax, dword[esp+ 28]
jc .e
add ebp, edi
jc .e
shr ebp, 1 ; k=(i+j)/2
mov eax, dword[esp+ 36]
mul ebp
cmp edx, 0
jne .e
mov edx, dword[esp+ 24]
add eax, dword[esp+ 28]
mov dword[esp+ 0], eax
push edx
push eax
call ebx
add esp, 8
cmp eax, 0
jle .3
push edx
push eax
call ebx
add esp, 8
cmp eax, 0
mov edi, ebp
sub edi, 1
jmp short .2
.3: jz .4
sub edi, 1
jmp short .2
io_x
Dec 24, 2011, 3:52:39 AM12/24/11
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
this seems a little more slow than C library bsearch() function one
; return -1 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -1 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
push ebx
push esi
push edi
push ebp
push ebp
;int3
cmp dword[esp+ 24], 0
je .e
cmp dword[esp+ 28], 0
je .e
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
push ebx
push esi
push edi
push ebp
push ebp
;int3
cmp dword[esp+ 24], 0
je .e
cmp dword[esp+ 28], 0
je .e
mov edi, dword[esp+ 32]
mov ebx, dword[esp+ 40]
cmp dword[esp+ 36], 0
jle .e
cmp edi, 0
jle .e
je .nf
mov esi, 0
jl .e
cmp ebx, 0
je .e
dec edi
jmp short .2
.nf: xor eax, eax
clc
jmp short .z
.e: xor eax, eax
dec eax
stc
jmp short .z
.2: cmp esi, edi
jg .nf
mov ebp, esi
jg .nf
mov ebp, esi
mov eax, dword[esp+ 36]
add ebp, edi
shr ebp, 1 ; k=(i+j)/2
mul ebp
cmp edx, 0
jne .e
cmp edx, 0
jne .e
add eax, dword[esp+ 28]
mov ecx, dword[esp+ 24]
mov dword[esp+ 0], eax
jc .e
push ecx
push eax
call ebx
add esp, 8
cmp eax, 0
jle .3
dec ebp
call ebx
add esp, 8
cmp eax, 0
jle .3
mov edi, ebp
jmp short .2
.3: jz .4
inc ebp
.3: jz .4
mov esi, ebp
jmp short .2
.4: mov eax, dword[esp+ 0]
clc
.z:
pop ebp
pop ebp
pop edi
pop esi
pop ebx
ret 20
-------------------
.4: mov eax, dword[esp+ 0]
clc
.z:
pop ebp
pop ebp
pop edi
pop esi
pop ebx
ret 20
; return -1 error, 0 not find, address of the found element in array
; would be like the C one, with the only difference return -1 for error
;u8* __stdcall
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
<b,i,j,k,k
;binSearchR(u8* InOutPKey, u8* InBase,
; u32 nElmBase, u32 SizeElmBase, i32 cmp(u8* elm1, u8* elm2) );
; 0k, 4k, 8j, 12i, 16b, 20ra, 24InOutKey, 28InBase, 32P_nElmBase,
36P_SizeElmBase, 40P_cmp
binSearchR:
;int3
^24==0#.e|^28==0#.e|j=^32 | b=^40 |^36<=0?#.e
j==0#.nf |i=0|<?#.e|b==0#.e|--j|#.2
.nf: a^=a |clc|#.z
.e: a^=a|--a|stc|#.z
.2: i>j?#.nf|k=i|a=^36|k+=j |k>>=1 ; k=(i+j)/2
mul k|r#.e|a+=^28 |c=^24|^0=a|jc .e
b<(a,c) |a>0!?#.3|--k|j=k|#.2
.3: =#.4|++k|i=k|#.2
.4: a=^0|clc
.z:
>b,i,j,k,k
ret 20
------------------------
.z:
>b,i,j,k,k
ret 20
C:>ba 100
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=0.000000
sum=460116
bsearch=0.000000
sum=460116
C:>ba 1000
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=2.000000
sum=650808558
bsearch=2.000000
sum=650808558
C:>ba 1500
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=5.000000
sum=-1984601096
bsearch=5.000000
sum=-1984601096
C:>ba 2000
r=0012FF3C find=13
r=0012FF3C find=13
r=00000000
myBsearch=10.000000
sum=1373176982
bsearch=9.000000
sum=1373176982
io_x
Dec 24, 2011, 10:37:27 AM12/24/11
to
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
Buon Natale e
Felice 2012
hopcode
Dec 24, 2011, 1:11:09 PM12/24/11
to
glückliches neues 2012
Cheers,
--
.:mrk[hopcode]
.:x64lab:.
group http://groups.google.com/group/x64lab
site http://sites.google.com/site/x64lab
Nathan
Dec 24, 2011, 3:20:12 PM12/24/11
to
On Dec 24, 1:11 pm, hopcode <hopc...@nulnulul.de> wrote:
> Il 24.12.2011 16:37, io_x ha scritto:
>
> > "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> >news:4ef5661d$0$1375$4faf...@reader2.news.tin.it...
>
> > Buon Natale e
> > Felice 2012
>
> Frohe Weihnachten und
> glückliches neues 2012
>
Wishing a very Merry Christmas to all and have a Happy New Year!
> Il 24.12.2011 16:37, io_x ha scritto:
>
> > "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> >news:4ef5661d$0$1375$4faf...@reader2.news.tin.it...
>
> > Buon Natale e
> > Felice 2012
>
> Frohe Weihnachten und
> glückliches neues 2012
>
Nathan.
0 new messages