Having trouble finding the invalid memory access in my random number array sorting program

Question

I am coding this for an assignment, where I am required to make an array in MASM and assign it random numbers given a number input. I am past the selection sort part of my assignment, and I am having trouble finding out where I am not accessing the write memory. The error code that I get is:

Exception thrown at 0x00000064 in Project.exe: 0xC0000005: Access violation executing location 0x00000064.

And here is the rest of my code:

INCLUDE Irvine32.inc

.data
    instructions BYTE "This program generates random numbers in the range [100 .. 999], displays the original list, sorts the list, and calculates the median value. Finally, it displays the list sorted in descending order.",0
    unsorted    BYTE "The unsorted random numbers:",0
    median      BYTE "The median is ",0
    sorted      BYTE "The sorted list:",0
    prompt      BYTE "How many numbers should be generated? [10 .. 200]: ",0
    invalid     BYTE "Invalid input",0
    newline     BYTE 0DH, 0AH, 0
    spaceBar    BYTE " ", 0
    array       DWORD 200 DUP(?)
    request     DWORD ?
    medianValue DWORD ?

.code
    main PROC
          call introduction
          call getData
          call generateRandomNumbers
          call displayList
          call calculateMedian
          call displayMedian
          call sortList
          call displayListDescending

          exit
     main ENDP

     introduction PROC
          mov edx, OFFSET instructions
          call WriteString
          call Crlf
          ret
     introduction ENDP

     getData PROC
          mov edx, OFFSET prompt
          call WriteString
          call ReadInt
          cmp eax, 10
          jl invalidInput
          cmp eax, 200
          jg invalidInput
          mov [request], eax
          ret

          invalidInput:
          mov edx, OFFSET invalid
          call WriteString
          call Crlf
          jmp getData
     getData ENDP

     generateRandomNumbers PROC
          mov ecx, [request]
          mov esi, OFFSET array
          generateLoop:
               call RandomRange ; Generates random number in the range [0, 899]
               add eax, 100 ; Adjust the range to [100, 999]
               mov [esi], eax
               add esi, 4
               loop generateLoop
          ret
     generateRandomNumbers ENDP

     displayList PROC
          mov edx, OFFSET unsorted
          call WriteString
          call Crlf
          mov edx, OFFSET newline
          call WriteString
          mov ecx, [request]
          mov esi, OFFSET array
          displayLoop:
          mov eax, [esi]
          call WriteInt
          mov edx, OFFSET spaceBar
          call WriteString
          add esi, 4
          loop displayLoop
          call Crlf
          ret
     displayList ENDP

     calculateMedian PROC
          mov ecx, [request]
          shr ecx, 1
          mov esi, OFFSET array
          mov eax, [esi+ecx*4]
          mov [medianValue], eax
          ret
     calculateMedian ENDP

     displayMedian PROC
          mov edx, OFFSET median
          call WriteString
          call Crlf
          mov edx, OFFSET newline
          call WriteString
          mov edx, [medianValue]
          call WriteInt
          call Crlf
          ret
     displayMedian ENDP
     
    sortList PROC
          mov ecx, [request]
          mov esi, OFFSET array
          mov ebx, OFFSET array
          mov edi, ecx

          sortLoop:
               xor edx, edx
               mov eax, [esi]
               innerLoop:
                    add ebx, 4
                    cmp ebx, edi
                    jge skipExchange
                    mov edx, [ebx]
                    cmp edx, 100
                    jge skipExchange
                    mov eax, edx
                    mov edi, ebx
               skipExchange:
                    loop innerLoop

               cmp esi, edi
               je skipSwap

               push eax
               push [esi]
               call exchangeElements
               skipSwap:
                    add esi, 4
                    cmp edx, 0
                    jne sortLoop
               
               ret

   sortList ENDP

   displayListDescending PROC
          mov edx, OFFSET newline
          call WriteString
          mov ecx, [request]
          mov esi, OFFSET array

          mov eax, ecx           ; Store the value of ecx in eax
          dec eax                ; Decrement eax to get (ecx-1)
          mov ebx, 4
          mul ebx
          shl eax, 2             ; Multiply by 4 (shift left by 2)
          add esi, eax           ; Add the offset to the base address of the array

          displayLoop:
               mov eax, [esi]
               call WriteInt
               mov edx, OFFSET spaceBar
               call WriteString
               sub esi, 4
               loop displayLoop

          call Crlf
          ret
    displayListDescending ENDP



    exchangeElements PROC
          push edx
          mov edx, [esp+12]
          mov ecx, [esp+8]
          mov [esp+12], ecx
          mov [esp+8], edx
          pop edx
          ret
     exchangeElements ENDP

END main

My best guess where the exception is being thrown is in the displayListDescending procedure. I have tried to simplify the registers and have even tried to keep track of what ESI is even tracking.
I'd appreciate any help I possibly can get.

score 1 · Answer 1 · answered Jun 25 '23 at 18:09

The exception

My best guess where the exception is being thrown is in the displayListDescending procedure.

Indeed, that is where your program reads from memory outside of the array! The calculation of the offset to the last element in the array is erroneously multiplying the index by 4 doing it twice.

mov  ecx, [request]
mov  esi, OFFSET array
mov  eax, ecx
dec  eax
mov  ebx, 4             <<<< 1st x 4
mul  ebx
shl  eax, 2             <<<< 2nd x 4
add  esi, eax

One way to solve it is to write:

mov  ecx, [request]
lea  esi, [array + ecx * 4 - 4]

Random numbers

generateRandomNumbers PROC
   mov  ecx, [request]
   mov  esi, OFFSET array
 generateLoop:
   call RandomRange ; Generates random number in the range [0, 899]
   add  eax, 100    ; Adjust the range to [100, 999]
   mov  [esi], eax
   add  esi, 4
   loop generateLoop
   ret
generateRandomNumbers ENDP

You are not generating a random number in the range [0,899]. For that to happen you need to set ECX=900 before call RandomRange. But since that would clash with the current loop counter, you need to use another register to control the loop:

generateRandomNumbers PROC
   mov  edi, [request]
   mov  esi, OFFSET array
  generateLoop:
   mov  ecx, 900
   call RandomRange ; Generates random number in the range [0, 899]
   add  eax, 100    ; Adjust the range to [100, 999]
   mov  [esi], eax
   add  esi, 4
   dec  edi
   jnz  generateLoop
  ret
generateRandomNumbers ENDP

The median

mov edx, [medianValue]
call WriteInt

The input to WriteInt goes in EAX.

The selection sort

The sortList and its accompanying exchangeElements procedures are not salvageable. They contain a lot of inexplicable operations that also make it hard to even find out if it is an actual selection sort and not some other sorting method.
I wrote this selection sort algorithm with a visual run-through so you can understand how it works. Although it uses 16-bit registers, porting it to 32-bit should not be difficult.

score 0 · Answer 2 · answered Jun 04 '23 at 07:21

0

exchangeElements probably needs a "ret 8" since you push two dwords before calling it.

answered Jun 04 '23 at 07:21

sinsi

45
5

Having trouble finding the invalid memory access in my random number array sorting program

2 Answers2

The exception

Random numbers

The median

The selection sort