Instructions
Requirements and Specifications
Source Code
; Program Header Here
; Write Macros Here
; Determines the number of characters (including null) of the provided string
; Argument 1: Address of string
; Returns length in rdx
%macro findLength 1
push rcx
mov rdx, 1
%%countLettersLoop:
mov cl, byte[%1 + rdx - 1]
cmp cl, NULL
je %%countLettersDone
inc rdx
loop %%countLettersLoop
%%countLettersDone:
pop rcx
%endmacro
; Prints a string to standard output
; Argument 1: Address of string location
%macro printString 1
push rbx
lea rbx, [%1]
%%printLoop:
cmp byte[rbx], NULL
je %%readLengthDone
mov rax, SYSTEM_WRITE
mov rdi, STANDARD_OUT
mov rsi, rbx
mov rdx, 1
syscall
inc rbx
jmp %%printLoop
%%readLengthDone:
pop rbx
%endmacro
; Outputs error message and stops program execution
; Argument 1: Address of error message
%macro endOnError 1
printString %1
mov rax, SYSTEM_EXIT
mov rdi, FAILURE
syscall
%endMacro
%macro clearInputBuffer 0
%%clearBufferLoop:
mov rax, SYSTEM_READ
mov rdi, STANDARD_IN
mov rsi, inputString
mov rdx, 1
syscall
cmp byte[inputString], LINEFEED
jne %%clearBufferLoop
%endmacro
; Reads a string in from standard in
; Argument 1: Address of location to place string
; Argument 2: Integer max length of string
%macro readString 2
mov rbx, 0
%%readLengthLoop:
mov rax, SYSTEM_READ
mov rdi, STANDARD_IN
lea rsi, [%1 + rbx]
mov rdx, 1
syscall
inc rbx
cmp byte[%1 + rbx - 1], LINEFEED
je %%readLengthDone
cmp rbx, %2 + 1
jb %%readLengthLoop
clearInputBuffer
endOnError errorStringTooLong
%%readLengthDone:
mov byte[%1 + rbx - 1], NULL
%endmacro
section .data
; System Service Call Constants
SYSTEM_EXIT equ 60
SUCCESS equ 0
FAILURE equ 1
SYSTEM_WRITE equ 1
SYSTEM_READ equ 0
STANDARD_OUT equ 1
STANDARD_IN equ 0
; ASCII Values
NULL equ 0
LINEFEED equ 10
; Program Constraints
MINIMUM_ARRAY_SIZE equ 2
MAXIMUM_ARRAY_SIZE equ 10000
MINIMUM_MAX_VALUE equ 1
MAXIMUM_MAX_VALUE equ 100000
INPUT_LENGTH equ 20
OUTPUT_LENGTH equ 11
VALUES_PER_LINE equ 5
; Labels / Useful Strings
labelHeader db "Sorted Random Number Generator", LINEFEED, LINEFEED, NULL
labelSorted db "Sorted Random Numbers", LINEFEED, LINEFEED, NULL
endOfLine db LINEFEED, NULL
space db " "
; Prompts
promptCount db "Number of values to generate (2-10,000): ", NULL
promptMaxVal db "Maximum Value (1-100,000): ", NULL
; Error Messages
; Array Length
errorArrayMinimum db LINEFEED, "Error - Program can only generate at least 1 value.", LINEFEED, LINEFEED, NULL
errorArrayMaximum db LINEFEED, "Error - Program can only generate at most 10,000 values.", LINEFEED, LINEFEED, NULL
; Max value
errorMaxValMinimum db LINEFEED, "Error - Maximum value must be at least 1.", LINEFEED, LINEFEED, NULL
errorMaxValMaximum db LINEFEED, "Error - Maximum value must be at most 100,000.", LINEFEED, LINEFEED, NULL
; Decimal String Conversion
errorStringUnexpected db LINEFEED,"Error - Unexpected character found in input." , LINEFEED, LINEFEED, NULL
errorStringNoDigits db LINEFEED,"Error - Value must contain at least one numeric digit." , LINEFEED, LINEFEED, NULL
; Input Length
errorStringTooLong db LINEFEED, "Error - Input can be at most 20 characters long." , LINEFEED, LINEFEED, NULL
; Other
arrayLength dd 0
maxValue dd 0
; current lcg value, start in 1
lcg dd 1
; globals for lcg
lcgA dd 48271
lcgM dd 2147483647
section .bss
; Array of integer values, not all will necessarily be used
array resd 10000
inputString resb 21
outputString resb 11
section .text
global _start
_start:
; Output Header
printString labelHeader
; Output Array Length Prompt
printString promptCount
; Read in Array Length - one character at a time
readString inputString, INPUT_LENGTH
; Convert Array Length
mov rdi, inputString
mov rsi, arrayLength
call convertDecimalToInteger
; Check that Array Length is Valid - output error message and end program if not
cmp dword[arrayLength], MINIMUM_ARRAY_SIZE
jl arrayLengthErrorMinimum
cmp dword[arrayLength], MAXIMUM_ARRAY_SIZE
jg arrayLengthErrorMaximum
jmp arrayLengthVerified
arrayLengthErrorMinimum:
endOnError errorArrayMinimum
arrayLengthErrorMaximum:
endOnError errorArrayMaximum
arrayLengthVerified:
; Output Max value Prompt
printString promptMaxVal
; Read in Max value - one character at a time
readString inputString, INPUT_LENGTH
; Convert Max value
mov rdi, inputString
mov rsi, maxValue
call convertDecimalToInteger
; Check that Max value is Valid - output error message and end program if not
cmp dword[maxValue], MINIMUM_MAX_VALUE
jl maxValErrorMinimum
cmp dword[maxValue], MAXIMUM_MAX_VALUE
jg maxValErrorMaximum
jmp maxValueVerified
maxValErrorMinimum:
endOnError errorMaxValMinimum
maxValErrorMaximum:
endOnError errorMaxValMaximum
maxValueVerified:
; Generate Array Length Values randomly
mov ecx, dword[arrayLength]
mov r11, array
randLoop:
mov rdi, lcg
mov esi, dword[maxValue]
call lcgGenerator ; generate random number
mov [r11], eax ; save random number
add r11, 4 ; advance to next position in array
loop randLoop
mov rdi, array
mov esi, dword[arrayLength]
call combSort ; sort using comb sort
; Output Array Values in Hex - (5 Per Line)
; Print Header
printString labelSorted
; Print Values - 5 Per Line
mov ecx, dword[arrayLength]
mov r8, VALUES_PER_LINE
mov r9, array
outputLoop:
push rcx
push r9
push r8
mov rdi, r9
mov rsi, outputString
call convertIntegerToHexadecimal
pop r8
mov rax, SYSTEM_WRITE
mov rdi, STANDARD_OUT
mov rsi, outputString
mov rdx, OUTPUT_LENGTH
syscall
cmp r8, 1
je printNewLine
mov rsi, space
dec r8
jmp printDelimiter
printNewLine:
mov rsi, endOfLine
mov r8, VALUES_PER_LINE
printDelimiter:
mov rax, SYSTEM_WRITE
mov rdi, STANDARD_OUT
mov rdx, 1
syscall
pop r9
add r9, 4
pop rcx
dec rcx
cmp rcx, 0
jne outputLoop
cmp r8, VALUES_PER_LINE
je endProgram
mov rax, SYSTEM_WRITE
mov rdi, STANDARD_OUT
mov rsi, endOfLine
mov rdx, 1
syscall
endProgram:
mov rax, SYSTEM_EXIT
mov rdi, SUCCESS
syscall
; Convert decimal string to dword integer
; Argument 1: null terminated string (byte array)
; Argument 2: dword integer variable
convertDecimalToInteger:
mov eax, 0
mov rbx, rdi
mov r9d, 1 ; sign
mov r8d, 10 ; base
mov r10, 0 ; digits processed
checkForSpaces1:
mov cl, byte[rbx]
cmp cl, " "
jne nextCheck1
inc rbx
jmp checkForSpaces1
nextCheck1:
cmp cl, "+"
je checkForSpaces2Adjust
cmp cl, "-"
jne checkNumerals
mov r9d, -1
checkForSpaces2Adjust:
inc rbx
checkForSpaces2:
mov cl, byte[rbx]
cmp cl, " "
jne nextCheck2
inc rbx
jmp checkForSpaces2
nextCheck2:
checkNumerals:
movzx ecx, byte[rbx]
cmp cl, NULL
je finishConversion
cmp cl, " "
je checkForSpaces3
cmp cl, "0"
jb errorUnexpectedCharacter
cmp cl, "9"
jbe convertCharacter
errorUnexpectedCharacter:
endOnError errorStringUnexpected
convertCharacter:
sub cl, "0"
mul r8d
add eax, ecx
inc r10
inc rbx
jmp checkNumerals
checkForSpaces3:
mov cl, byte[rbx]
cmp cl, " "
jne checkNull
inc rbx
jmp checkForSpaces3
checkNull:
cmp cl, NULL
je finishConversion
endOnError errorStringUnexpected
finishConversion:
cmp r10, 0
jne applySign
endOnError errorStringNoDigits
applySign:
mul r9d
mov dword[rsi], eax
ret
; Convert integer to hexadecimal string
; Argument 1: dword integer variable
; Argument 2: string (11 byte array)
convertIntegerToHexadecimal:
mov byte[rsi], "0"
mov byte[rsi+1], "x"
mov byte[rsi+10], NULL
mov rbx, rsi
add rbx, 9
mov r8d, 16 ;base
mov rcx, 8
mov eax, dword[rdi]
convertHexLoop:
mov edx, 0
div r8d
cmp dl, 10
jae addA
add dl, "0" ; Convert 0-9 to "0"-"9"
jmp nextDigit
addA:
add dl, 55 ; 65 - 10 = 55 to convert 10 to "A"
nextDigit:
mov byte[rbx], dl
dec rbx
dec rcx
cmp eax, 0
jne convertHexLoop
addZeroes:
cmp rcx, 0
je endConversion
mov byte[rbx], "0"
dec rbx
dec rcx
jmp addZeroes
endConversion:
ret
; LCG generator, generate a random number using a linear congruential generator
; Argument 1: reference to lcg variable
; Argument 2: range
; Returns eax = random number
lcgGenerator:
mov eax, [rdi] ; load lcg_n-1
mul dword[lcgA] ; lcg_n-1 * a
div dword[lcgM] ; divide lcg_n-1 * a over m
mov [rdi], edx ; use (lcg_n-1 * a) mod m as next lcg
mov eax, [rdi] ; returning new lcg
inc esi ; load range + 1
mov edx, 0 ; extend zero in edx for division
div esi ; divide lcg / range + 1
mov eax, edx ; return lcg mod (range + 1)
ret
; Comb sort function, sorts the input array using comb sort
; Argument 1: address of the dword array to be sorted
; Argument 2: length of array
combSort:
mov r8d, esi ; gapsize = n
combLoop:
mov eax, 10
mul r8d ; gapsize * 10
mov ecx, 13
mov edx, 0
div ecx ; gapsize*10 / 13
mov r8d, eax ; gapsize = gapsize*10 / 13
cmp r8d, 0 ; if gapsize == 0
jne combNext ; else, skip
mov r8d, 1 ; gapsize = 1
combNext:
mov r9d, 0 ; swapsdone = 0
mov ecx, 0 ; i = 0
mov edx, esi ; load n
sub edx, r8d ; n - gapsize
mov r10, rdi ; point to start of array
mov r11, 0
mov r11d, r8d ; load gapsize
shl r11, 2 ; multiply by 4
add r11, rdi ; point to array[gapsize]
combForLoop:
cmp ecx, edx ; compare i with n-gapsize
jge combEndLoop
mov eax, [r10] ; load array[i]
mov ebx, [r11] ; load array[i+gapsize]
cmp eax, ebx ; compare array[i] with array[i+gapsize]
jle combSkip ; if array[i] <= array[i+gapsize], skip
mov [r10], ebx ; array[i] = array[i+gapsize]
mov [r11], eax ; array[i+gapsize] = temp
inc r9d ; swapsdone ++
combSkip:
add r10, 4 ; advance to array[i+1]
add r11, 4 ; advance to array[i+gapsize+1]
inc ecx ; i++
jmp combForLoop
combEndLoop:
cmp r8d, 1 ; see if gapsize == 1
jne combLoop ; if not, continue
cmp r9d, 0 ; see if swapsdone == 0
jne combLoop ; if not, continue
ret