I needs your help

[dedndave]

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

Code Select Expand


;--------------------------------------------------------------------------------------------

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

;--------------------------------------------------------------------------------------------

[hutch--]

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.

[dedndave]

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

[hutch--]

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.

[dedndave]

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

[lingo]

"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

[dedndave]

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

[jj2007]

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...

[dedndave]

That 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

[jj2007]

designing a test bed sounds like as much fun as watching paint dry

Let's try:

Code Select Expand

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 endp

EDIT: 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.