now I am coding a bubble sort with MASM
the goal is simpel
read numbers and store it in array and sort it.
I tried it several times but it's not working
.586
.MODEL FLAT
INCLUDE io.h ; header file for input/output
.STACK 4096
.DATA
number DWORD ?
count DWORD ?
prompt BYTE "Enter the number", 0
string BYTE 20 DUP (?)
sortLbl BYTE "The sorted array is", 0
sortAnswer BYTE 11 DUP (?), 0
nbrArray DWORD 100 DUP (?)
.CODE
_MainProc PROC
lea ebx,nbrArray ; get address of nbrArray
mov ecx,0
input prompt, string, 20
atod string
cmp eax,0
je exitGo
add [ebx],eax
add ebx,4
inc ecx
goinput: input prompt, string, 20
atod string
add [ebx],eax
add ebx,4
inc ecx
cmp eax,0
jz goNext
jmp goinput
goNext: dec ecx
call goSort
lea ebp,nbrArray ; get address of nbrArray
printArray : mov eax,[ebp]
add ebp,4
dtoa sortAnswer,eax ;convert to ASCII character
output sortLbl,sortAnswer
mov eax,[ebp]
cmp eax,0
jz exitGo
loop PrintArray
exitGo:
mov eax, 0 ; exit with return code 0
ret
_MainProc ENDP
goSort PROC NEAR32
dec ecx ; do not count last 0 input
dec ecx ; decrement outer loop counter by 1 (arraysize -1)
lp1: add edx, ecx ; save outer loop count
mov ebx, nbrArray ; point to first value
[color=Red] lp2: mov eax, [ebx] [/color]
cmp [ebx+4], eax
jge lp3
xchg eax, [ebx+4]
mov [ebx], eax
lp3: add ebx, 4 ; move both pointers forward
loop lp2 ; inner loop
dec edx ; retraeve outer loop count
loop lp1 ; else repeat outer loop
lp4: ret
goSort ENDP
END
When I run it,
Unhandled exception at 0x00411aae in windows32.exe: 0xC0000005: Access violation reading location 0x00000002.
this message occured at lp2(red color)
I needs your help. I just want to figure out it's problem of syntax or algorithm
Thank you
Added code tags
mov ebx, offset nbrArray
Quote from: Slugsnack on April 09, 2010, 06:58:34 PM
mov ebx, offset nbrArray
thank for your interest but when I changed it.
Microsoft Visual Studio C Runtime Library has detected a fatal error in windows32.exe.
Press Break to debug the program or Continue to terminate the program.
this messgae occur and dbghook.c file poped up
can you upload a compilable version of your code and i'll test it and find where the bug is. or the io.h file
You probably shouldn't be changing EBP, or at least preserving it for the function calls (before the 'output')
-r
I would like to upload the file but I don't know how to upload it :eek
this is url to download the necessary file
http://www.jblearning.com/catalog/samplefile.aspx?isbn13=9780763772239&isbn=0763772232&filename=windows32.zip&isOlder=0
I really appreciate your help
that compiles and runs fine for me. but it's not a bubble sort, just adds two numbers..
Shawn
in here, we all use the masm32 package
at the upper right corner of the forum is a link to download it
when you install it, close all programs until it is done building the libraries
your code makes no sense to us because it is written to be used with the C compiler :bg
bsort.asm(29) : error A2008: syntax error : input
bsort.asm(30) : error A2008: syntax error : atod
bsort.asm(73) : error A2008: syntax error : sortAnswer
bsort.asm(74) : error A2008: syntax error : output
bsort.asm(79) : error A2006: undefined symbol : PrintArray
i am going to have a look at the windows32.zip file....
ok - i have io.h in there, now :P
bsort.obj : error LNK2001: unresolved external symbol __getInput
bsort.obj : error LNK2001: unresolved external symbol __showOutput
bsort.obj : error LNK2001: unresolved external symbol _atodproc
bsort.obj : error LNK2001: unresolved external symbol _dtoaproc
bsort.obj : error LNK2001: unresolved external symbol _wtoaproc
bsort.obj : error LNK2001: unresolved external symbol _atowproc
i think if i change some names with "crt__" prefixes, i can make it work
QuoteI would like to upload the file but I don't know how to upload it
below the reply window is a link that says >
Additional Optionsclick on that, then attach your file
it must be a ZIP file, less than 256 Kb
ok - i have taken the io.asm file and created an obj - i chose to rename it DetmerIO.asm/DetmerIO.obj
also, i have renamed io.h to DetmerIO.inc
now my only problem :P
how do you link multiple obj files with this new-fangled linker ? - lol
in the old days, you could use LINK file1.obj+file2.obj
that doesn't seem to work
any help ?
You just enumerate them LINK moe.obj larry.obj curly.obj
-Clive
thanks Clive
i still have unresolved externals
i don't know enough about C libraries to make it work, i guess
Yeah, I got it to compile and run with VS 2010 too, like Slugsnack says it's not a bubble sort, it asks for two numbers and then adds them and displays the result.
It uses Richard Detmer's IO library from his book. They are not C libraries they are MASM format despite the .h file extensions.
i am sure i am missing something, then
if it builds for you guys, you don't need me :P
well i was not building with masm32, but vc++
Fixing the sort, there are a couple of things that could work more efficiently. The xchg is VERY expensive, and the loop could exit quicker if it determined the list was in order.
-Clive
goSort PROC NEAR32
push esi
push edi
dec ecx ; do not count last 0 input
jz lp4 ; Empty list
dec ecx ; decrement outer loop counter by 1 (arraysize -1)
jz lp4 ; List of 1 already sorted
lp1: mov edx, ecx ; save outer loop count
lea esi, nbrArray ; point to first value
lp2: mov eax, [esi]
cmp [esi+4], eax
jge lp3
xchg eax, [esi+4]
mov [esi], eax
lp3: add esi, 4 ; move both pointers forward
loop lp2 ; inner loop
mov ecx, edx ; retrieve outer loop count
loop lp1 ; else repeat outer loop
lp4: pop edi
pop esi
ret
goSort ENDP
Here with some optimization. Still a bubblesort, but easy enough to understand.
-Clive
goSort PROC NEAR32
push ebx
push esi
push edi
dec ecx ; do not count last 0 input
jz lp4 ; Empty list
dec ecx ; decrement outer loop counter by 1 (arraysize -1)
jz lp4 ; List of 1 already sorted
lp1: mov edx, ecx ; save outer loop count
lea esi, nbrArray ; point to first value
xor edi, edi ; clear exchange flag
mov eax, [esi+0] ; Hold current element in eax
lp2: mov ebx, [esi+4] ; Hold next element in ebx
cmp ebx, eax
jge lp3
xchg eax, ebx ; register to register cheap
mov [esi+0], eax ; echo change back to memory
mov [esi+4], ebx ; will use write buffers
add edi, 1 ; flag an exchange
lp3: add esi, 4 ; move both pointers forward
mov eax, ebx ; move element next element to current
sub ecx, 1
jnz lp2 ; inner loop
or edi, edi ; list sorted if no exchanges
jz lp4
mov ecx, edx ; retrieve outer loop count
sub ecx, 1
jnz lp1 ; else repeat outer loop
lp4: pop edi
pop esi
pop ebx
ret
goSort ENDP
shawn,
just take a look :wink
OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
align 16
BblSrt proc lenArea:dword, lpArea:dword
pop eax ; return addres
pop edx ; edx->lenArea in DWords
mov [esp-1*4], ebx ; saving register ebx
pop ebx ; ebx->lpArea
mov [esp-1*4], esi ; saving register esi
sub edx, 1
mov esi, esp ; saving register esp
jle lExit
jne NoExchangesArea
align 16
ExchangesArea:
pop [esp-2*4]
sub ecx, 1
mov [esp-1*4], eax
je NoExchangesArea
@@:
cmp eax, [esp]
jae ExchangesArea
sub ecx, 1
pop eax
jne @b
NoExchangesArea:
mov esp, ebx ; ebx->lpArea
mov ecx, edx ; edx->length of area /4 ->in Dwords
pop eax
@@:
cmp [esp], eax
jb ExchangesArea
sub ecx, 1
pop eax
jne @b
lExit:
mov ebx, [esi-2*4] ; restoring ebx register
mov esp, esi ; restoring esp register
mov esi, [esi-1*4] ; restoring esi register
jmp dword ptr [esp-3*4] ; jmp to return address
BblSrt endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef
Quote from: lingo
xchg eax, [esp]
This instruction will absolutely murder performance, it is locked and atomic. You can measure the RAM access speed with this construct.
-Clive
Quote from: clive on April 10, 2010, 07:17:52 PM
Quote from: lingo
xchg eax, [esp]
This instruction will absolutely murder performance, it is locked and atomic. You can measure the RAM access speed with this construct.
-Clive
Clive is right...
Intel(R) Celeron(R) M CPU 420 @ 1.60GHz (SSE3)
555 cycles for mov
2010 cycles for xchg
"This instruction will absolutely murder performance..."
Ok, corrected... :wink
That has to win a prize for the nastiest, stack unsafe code I've seen in a while. :cheekygreen:
-Clive
"..for the nastiest, stack unsafe code.."
Don't talk about things you don't understand, and don't tell God how to run the world and how to write safety code in assembly... :naughty:
Quote from: clive on April 10, 2010, 09:49:34 PM
That has to win a prize for the nastiest, stack unsafe code I've seen in a while. :cheekygreen:
-Clive
Can you explain why you consider it unsafe? The stack is your property, isn't it?
(I hate to defend lingo, I am just curious :bg)
Anything below the stack pointer is fair game for the processor to use as it pleases. The operating system, or parts thereof, might also reasonably expect the user space stack to be usable.
-Clive
Rumours (in this forum) say that was correct for old versions of Windows but nowadays the OS won't touch [esp-4] any more.
i prefer not to use area under [esp] - i think it's a matter of time before something bad happens
this is a discussion we have had a few times before, but we shouldn't confuse poor Shawn any more than he already is :bg
Quote from: dedndave on April 10, 2010, 11:19:11 PM
i prefer not to use area under [esp] - i think it's a matter of time before something bad happens
I've never problems when using this "dubious" technique . Also I don't think, that the OS (or whatever) will extract ESP from threads context to use memory below esp...
In case we get more questions about this book "Introduction to 80x86 Assembly Language and Computer Architecture" Second Edition, the libraries and source code for it are here (http://www.jblearning.com/catalog/9780763772239/) under Samples. The book is intended to be used with Visual Studio 2008 as the development environment. Also, even though the include files are .h files they are in MASM format.
i realize that i am posting 16-bit code in a 32-bit forum :bg
but, this routine is simple and seemed to work fairly well - it wouldn't take much effort to make a 32-bit routine out of it
;--------------------------------------------------------------------------------------------
BSort PROC NEAR
;
;Byte Array Bubble Sort
;
;Call With: SI = address of array
; CX = size of array in bytes
;
; Returns: the array is sorted, lower values at lower addresses
;
; all general registers are used and not saved
;
;-------------------------------------------
jcxz BSort4 ;if array size = 0, sort is done
dec cx ;count to last byte
jz BSort4 ;if array size = 1, sort is done
mov bp,1 ;bp = 1 - used to set the swap flag
xor dx,dx ;dx = 0 - initial swap flag
cmp cx,bp ;if cx = 1, there are only 2 bytes
ja BSort0 ;more than 2 - skip the adjustment
mov bp,dx ;if only 2 bytes, we want one pass, so flag = 0
BSort0: add cx,si ;cx = top address
dec si ;adjust for the skip (DI gets ADD'ed before 1st pass)
mov di,-1 ;di = 1 for up, -1 for down (gets NEG'ed before 1st pass)
mov bx,si ;bx = bottom address (gets XCHG'ed with CX before 1st pass)
dec bx ;adjust for "one less" (DI gets SUB'ed before 1st pass)
BSort1: sub bx,di ;one less next time
xchg bx,cx ;swap ends
neg di ;switch direction
add si,di ;skip one - already did that pair
add si,di ;skip another one - one less next time
BSort2: mov ax,[si] ;get 2 bytes
cmp al,ah ;do they need to be swapped ?
jbe BSort3 ;no - next address
xchg al,ah ;yes - swap them
mov dx,bp ;set the swap flag
mov [si],ax ;store the swapped byte pair
BSort3: add si,di ;step in the current direction
cmp si,bx ;are we at the end ?
jnz BSort2 ;no - next pair
dec dx ;yes - clear the sort flag if it is 1
jz BSort1 ;if the sort flag was 1 before DEC, we are not done
BSort4: ret ;exit the routine
BSort ENDP
;--------------------------------------------------------------------------------------------
Like most lessons I have learnt them all the hard way and the stack is no different. Work on the right side of the stack and you can make as much mess as you like up to the limit of stackl memory, work on the wrong side of the stack and it often jumps up and bites you. RE exchanges of data ALA sort algos there is a stat on taken or not taken exchanges that is theoretically 50/50 depending on the data and vagualy I remember that pre-loading the data was faster than testing first. XCHG is an old timer that lives in microcode and is best left there.
xchg reg,reg seems to work ok :bg
i don't use xchg reg,mem very often - and when i do, it is not a speed-critical application
i was thinking about the stack issue
if for no other reason than this, the area below [esp] should be regarded as "unsafe"
we all know about commited stack pages - and probing the stack down prior to allocating larger stack spaces
what would happen if, by chance, the location [esp-4*n] falls on a page that has not been commited, yet
well - i can guess what will happen - lol
error c0000005 will happen
i don't see anything wrong with reserving the space you want to use on the stack with SUB ESP,nnnnnnnn
a few bytes and clock cylces buys you peace of mind :bg
Dave,
There is nothing wrong with XCHG except that its really slow, it works fine just like LOOP but apart from legacy code that has not be re-written yet, it is an old instruction that is way off the pace to manually coded alternatives. x86 is RISC under the hood and have a preferred instruction set, vary from that and you get really slow code in algos that matter. There will never be a fast bubble sort unless you are sorting nearly sorted data and a double ender (cocktail shaker sort) is nearly as simple and does not suffer the same limitations but you can make a bubble sort even slower by using antique instructions.
i wonder if that applies to the special case single-byte XCHG EAX,reg form
that includes the NOP instruction (which is essentially XCHG EAX,EAX)
i use this form quite often - any time i have tried to replace it, the code seemed to get slower
"i prefer not to use area under [esp] - i think it's a matter of time before something bad happens"
"routine is simple and seemed to work fairly well"
"i don't use xchg reg,mem very often - and when i do, it is not a speed-critical application"
"i was thinking about the stack issue
if for no other reason than this, the area below [esp] should be regarded as "unsafe"
"any time i have tried to replace it, the code seemed to get slower"
"i wonder if that applies to the special case single-byte XCHG EAX,reg"
Why do you poison every thread with garbage and code like this? Who needs all that nonsense?
No offense, but don't talk about things you don't understand, just get your pills and try to control yourself... :wink
lol Lingo
you are a fairly decent coder, but you have the manners of bogdan - lol
no wonder neither of you have any friends
well - at least you can code a little
as for not understanding things - you may be right
that is why i asked the question
this is the campus and i am trying to learn from the discussion
Quote from: dedndave on April 11, 2010, 01:16:54 PM
if for no other reason than this, the area below [esp] should be regarded as "unsafe"
we all know about commited stack pages - and probing the stack down prior to allocating larger stack spaces
what would happen if, by chance, the location [esp-4*n] falls on a page that has not been commited, yet
Dave,
That problem would also apply if you previously put a
sub esp, nnn, so it should not be an argument.
I wonder if we could design a testbed...
QuoteThat problem would also apply if you previously put a sub esp, nnn, so it should not be an argument.
you got me, there, Jochen :P
designing a test bed sounds like as much fun as watching paint dry
i don't think there is any way to test for "what could happen"
i was having more fun talking about lingo's lack of personality :bg
i guess, when it comes down to it, accessing memory below [esp] is a matter of personal preference
Quote from: dedndave on April 11, 2010, 04:38:05 PM
designing a test bed sounds like as much fun as watching paint dry
Let's try:
Button1 proc
StackRange = 8000
mov ecx, StackRange-4
.Repeat
mov dword ptr [esp+ecx-StackRange], ecx
sub ecx, 4
.Until Sign?
.Repeat
mov eax, [esp-4] ; 15 seconds to switch tasks, work with MS Word, ....
sub eax, 4
mov edx, [esp-8]
.if eax!=edx
MsgBox 0, "FOUL A!!", "Hi", MB_OK
exit
.endif
dec ecx
.Until Zero?
mov ecx, StackRange-4
.Repeat
mov eax, [esp+ecx-StackRange]
.if eax!=ecx
MsgBox 0, "Foul B!!", "Hi", MB_OK
exit
.endif
sub ecx, 4
.Until Sign?
MsgBox 0, chr$("Thank you so much for pushing me!"), addr txApp, MB_OK
ret
Button1 endpEDIT: Extended the test. After the long loop, the whole StackRange is being checked for modifications. Under Windows XP SP2, there are none, but a check under Win9x might be interesting.