Monthly Archives: May 2016

Updated Bubble Sort in x86 ASM

So, after another week of studying assembly, I went back and rewrote my bubble sort algorithm.  I’m feeling a lot better about this implementation.  I’m sure it could could be even better, but I’m pretty pleased with it this time.

Here is the code:

 

; Author J. Logiodice
; Date: 05/28/2016
; Purpose: Bubble SOrt
; This method will read in a series of TOTAL_NUMS numbers
; And bubble sort them, then print them out in sorted order to the screen
format PE console
entry start

include ‘win32a.inc’

TOTAL_NUMS = 10 ;10

section ‘.bss’ data readable writeable

array_numbers dd TOTAL_NUMS dup (?)
nMinus1Mem dd ?
boolSwapped db ?

section ‘.text’ code readable executable

start:

; Set up the loop variables
mov ecx, dword TOTAL_NUMS
mov esi, dword TOTAL_NUMS ;ecx
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Read in one number at a time, for TOTAL_NUMS numbers, store them in the bytes that
; start with array_numbers
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

loopRead:

; have to use esi because read_hex uses edi
dec esi

; read input into eax but first clear out eax
xor eax, eax
call read_hex

; move value into memory offset (reverse order)
mov dword [array_numbers + esi * 4], eax

loop loopRead

; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; loop iteratively over the array until no more swapping occurs,
; and the highest number ends up in the lowest part of the array (lowest to highest)
; start with array_numbers
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Set back up the loop variables
restartLoop:

mov ecx, dword TOTAL_NUMS – 1
; set the swapped variable to false
mov [boolSwapped], byte 0 ;dword 0

lea esi, [array_numbers]

loopSort:

; jump to the loop exit if ecx is 0
; this will occur if we are at the end of the counter, or if the
; initial array was of size 0 bytes
jecxz loopExit
; load the first number in array_numbers into eax
lodsd
; after lodsd, edi is pointing to edi – dword
; if we compare the value at edi at this point it is effectively the value below eax
; compare eax to the number below it in the array
cmp eax, [esi] ;, eax
; if [esi] > eax, then no ZF or CF set, so jump below or equal
jbe noSwap
; if here then eax is lower, swap eax and the higher number in memory
mov ebx, dword [esi]
mov [esi], dword eax
mov dword [esi-4], ebx

; if a swap occured, set boolSwapped = 1

mov [boolSwapped], 1b
noSwap:
; jump here if no swapping needs to occur, but we’re still in the loop
loop loopSort

loopExit:

; if boolSwapped isn’t false, then we’ve swapped at least one
; during the iteration, let’s go through it one more time to make sure
; that we don’t have any more to swap
cmp [boolSwapped], 1b
jae restartLoop
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Print each number back out to the screen for unmodified numbers
; we will loop from the lowest to highest part of the array – which is the largest to smallest number
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

mov ecx, TOTAL_NUMS
lea esi, [array_numbers]

loopPrint:

jecxz loopExit
lodsd
call print_eax

loop loopPrint
exit_prog:
push 0
call [ExitProcess]
include ‘training.inc’

x96 ASM bubble sort in VIM

Bubble sort in x86 ASM

[[NOTE: For a more efficient way to implement the bubble sort, see my later post]]

Why?  I have no idea.  It’s funny how many times I set off my AV scanner trying to compile and run my PE.  That brings back some great memories with the VCL.

I’m sure there are cleaner ways to do it – but right now, I’m just worried about making it work.  😉

NOTE: Written in FASM, and the training.inc can be found over at xorpd on git.

; Author J. Logiodice
; Date: 05/22/2016
; Purpose: Bubble SOrt
; This method will read in a series of TOTAL_NUMS numbers
; And bubble sort them, then print them out in sorted order to the screen
format PE console
entry start

include ‘win32a.inc’

TOTAL_NUMS = 10 ;10

section ‘.bss’ data readable writeable

array_numbers dd TOTAL_NUMS dup (?)
nMinus1Mem dd ?
boolSwapped dd ?

section ‘.text’ code readable executable

start:

; Set up the loop variables
mov ecx, TOTAL_NUMS
mov esi, ecx
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Read in one number at a time, for TOTAL_NUMS numbers, store them in the bytes that
; start with array_numbers
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
loopRead:

dec esi

; read input into eax but first clear out eax
xor eax, eax
call read_hex

; move value into memory offset (reverse order)
mov dword [array_numbers + esi * 4], eax

loop loopRead

; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; I am sure there is a more effecient way of doing this
; I will probably try and clean it up later, but for now it works.
; loop iteratively over the array until no more swapping occurs,
; and the highest number ends up in the lowest part of the array (lowest to highest)
; start with array_numbers
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Set back up the loop variables
restartLoop:

mov ecx, TOTAL_NUMS
mov esi, ecx

; set the swapped variable to false
mov [boolSwapped], dword 0

loopSort:

dec esi
mov eax, esi
sub eax,1d

test esi, esi
jbe loopExit
mov edx, dword [array_numbers + eax * 4]
cmp edx, dword [array_numbers + esi * 4]
jbe noSwap
; if we get into this section, then swapping needs to occur
; set the boolSwapped to true
mov [boolSwapped], dword 1

; need to swap the two numbers
mov [nMinus1Mem], dword edx
mov edx, dword [array_numbers + esi * 4]
mov [array_numbers + eax * 4], dword edx
mov edx, dword [nMinus1Mem]
mov [array_numbers + esi * 4], dword edx
noSwap:
; jump here if no swapping needs to occur, but we’re still in the loop
loop loopSort

loopExit:

; if boolSwapped isn’t false, then we’ve swapped at least one
; during the iteration, let’s go through it one more time to make sure
; that we don’t have any more to swap
cmp [boolSwapped], 1b
jae restartLoop
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
; Print each number back out to the screen for unmodified numbers
; we will loop from the lowest to highest part of the array – which is the largest to smallest number
; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

;mov edi, array_numbers
mov ecx, TOTAL_NUMS
mov esi, ecx

loopPrint:

dec esi
mov eax, [array_numbers + esi * 4]
call print_eax

loop loopPrint

exit_prog:
push 0
call [ExitProcess]
include ‘training.inc’

Ehrlich’s Binary Shirt

In case you are wondering:

01000010 = 42h = B (A)
01101001 = 69h = i (A)
01110100 = 74h = t (A)
01100011 = 63h = c (A)
01101111 = 6Fh = o (A)
01101001 = 69h = i (A)
01101110 = 6Eh = n (A)

You know what they say, there are only 10 types of people in the world: those who understand binary, and those who don’t.