+1 (315) 557-6473 

Create Random Numbers in Assembly Language and Then Sort Them Using Comb Sort in X86-64 Assembly Assignment Solution.


Write a program to create random numbers in assembly language and then sort them using comb sort in x86-64 assembly.

Requirements and Specifications

Comb Sort. The comb sort is a variation of a bubble sort where the comparisons are done over a gap rather than comparing neighbouring elements. This allows the smallest and largest values to transition nearer to their correct positions using less swaps. For an array of n items, start with a gapsize of n. Before each pass through the array, multiply the gapsize by 10 then divide by 13 (round down). The multiplication must be done before the division to avoid a loss of precision. Once the gapsize is 1, the algorithm begins to check if a swap is done on a given iteration of the array. If no swaps were performed, the list is sorted and the algorithm ends.
Screenshots of output
Implement operations for 16x16 byte arrays using row major order Assembly languageCreate random numbers in assembly language and then sort them using comb sort in Assembly language

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


  mov cl, byte[%1 + rdx - 1]

  cmp cl, NULL

  je %%countLettersDone

  inc rdx

 loop %%countLettersLoop


 pop rcx


; Prints a string to standard output

; Argument 1: Address of string location

%macro printString 1

 push rbx

 lea rbx, [%1]


  cmp byte[rbx], NULL

  je %%readLengthDone

  mov rax, SYSTEM_WRITE

  mov rdi, STANDARD_OUT

  mov rsi, rbx

  mov rdx, 1


  inc rbx

 jmp %%printLoop


 pop rbx


; 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



%macro clearInputBuffer 0


  mov rax, SYSTEM_READ

  mov rdi, STANDARD_IN

  mov rsi, inputString

  mov rdx, 1


 cmp byte[inputString], LINEFEED

 jne %%clearBufferLoop


; 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


  mov rax, SYSTEM_READ

  mov rdi, STANDARD_IN

  lea rsi, [%1 + rbx]

  mov rdx, 1


  inc rbx

  cmp byte[%1 + rbx - 1], LINEFEED

  je %%readLengthDone

 cmp rbx, %2 + 1

 jb %%readLengthLoop


  endOnError errorStringTooLong


 mov byte[%1 + rbx - 1], NULL


section .data

 ; System Service Call Constants


 SUCCESS equ 0

 FAILURE equ 1





 ; ASCII Values

 NULL equ 0

 LINEFEED equ 10

 ; Program Constraints








 ; 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


 ; 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


  endOnError errorArrayMinimum


  endOnError errorArrayMaximum


 ; 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


  endOnError errorMaxValMinimum


  endOnError errorMaxValMaximum


 ; Generate Array Length Values randomly

 mov ecx, dword[arrayLength]

 mov r11, array


  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 r9, array


  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


  cmp r8, 1

  je printNewLine

   mov rsi, space

   dec r8

   jmp printDelimiter


   mov rsi, endOfLine

   mov r8, VALUES_PER_LINE


  mov rax, SYSTEM_WRITE

  mov rdi, STANDARD_OUT

  mov rdx, 1


  pop r9

  add r9, 4

  pop rcx

  dec rcx

 cmp rcx, 0

 jne outputLoop


 je endProgram

 mov rax, SYSTEM_WRITE

 mov rdi, STANDARD_OUT

 mov rsi, endOfLine

 mov rdx, 1



 mov rax, SYSTEM_EXIT

 mov rdi, SUCCESS


; Convert decimal string to dword integer

; Argument 1: null terminated string (byte array)

; Argument 2: dword integer variable


 mov eax, 0

 mov rbx, rdi

 mov r9d, 1 ; sign

 mov r8d, 10 ; base

 mov r10, 0 ; digits processed


  mov cl, byte[rbx]

  cmp cl, " "

  jne nextCheck1

  inc rbx

 jmp checkForSpaces1


 cmp cl, "+"

 je checkForSpaces2Adjust

 cmp cl, "-"

 jne checkNumerals

 mov r9d, -1


  inc rbx


  mov cl, byte[rbx]

  cmp cl, " "

  jne nextCheck2

  inc rbx

 jmp checkForSpaces2



  movzx ecx, byte[rbx]

  cmp cl, NULL

  je finishConversion

  cmp cl, " "

  je checkForSpaces3

  cmp cl, "0"

  jb errorUnexpectedCharacter

  cmp cl, "9"

  jbe convertCharacter


   endOnError errorStringUnexpected


  sub cl, "0"

  mul r8d

  add eax, ecx

  inc r10

  inc rbx

 jmp checkNumerals


  mov cl, byte[rbx]

  cmp cl, " "

  jne checkNull

  inc rbx

 jmp checkForSpaces3


  cmp cl, NULL

  je finishConversion

   endOnError errorStringUnexpected


  cmp r10, 0

  jne applySign

   endOnError errorStringNoDigits


  mul r9d

  mov dword[rsi], eax


; Convert integer to hexadecimal string

; Argument 1: dword integer variable

; Argument 2: string (11 byte array)


 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]


  mov edx, 0

  div r8d

  cmp dl, 10

  jae addA

   add dl, "0" ; Convert 0-9 to "0"-"9"

  jmp nextDigit


   add dl, 55 ; 65 - 10 = 55 to convert 10 to "A"


   mov byte[rbx], dl

   dec rbx

   dec rcx

 cmp eax, 0

 jne convertHexLoop


  cmp rcx, 0

  je endConversion

  mov byte[rbx], "0"

  dec rbx

  dec rcx

 jmp addZeroes



; LCG generator, generate a random number using a linear congruential generator

; Argument 1: reference to lcg variable

; Argument 2: range

; Returns eax = random number


 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)


; 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


 mov r8d, esi ; gapsize = n


 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


 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]


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


 add r10, 4 ; advance to array[i+1]

 add r11, 4 ; advance to array[i+gapsize+1]

 inc ecx ; i++

 jmp combForLoop


 cmp r8d, 1 ; see if gapsize == 1

 jne combLoop ; if not, continue

 cmp r9d, 0 ; see if swapsdone == 0

 jne combLoop ; if not, continue