Some_Dude
Reputation: 307
Prime finding - some array values getting overwritten?
I have written a sieve of Eratosthenes algorithm, but i have a strange bug that I cant figure out. (Editor's note: this is not a sieve; it uses trial division to test each number for being prime.)
This program asks a user to input a number, then the program will output that number of primes to the screen. The program prints all primes correctly except after 11, where it will print 3 garbage numbers and skip the number 13, and then it will proceed with the correct number of primes from 17 onwards. Below is a sample output for 20 primes.
> Enter number of primes:
20....
prime number: 1
prime number: 2
prime number: 3
prime number: 5
prime number: 7
prime number: 11
prime number: 538976288
prime number: 909588792
prime number: 3291447
prime number: 17
prime number: 19
prime number: 23
prime number: 29
prime number: 31
prime number: 37
prime number: 41
prime number: 43
prime number: 47
prime number: 53
prime number: 59
These numbers are stored in an array, and in sieve.asm i have put a label called "PrintLoop2" which i used to look at every value in the array and i can see 13 listed there and no garbage with it, so i am not sure why this is happening.
Sieve.asm is the main program, genprimes.asm creates the prime numbers and puts them on the stack, and the other files are for I/O.
sieve.asm:
.586
.MODEL FLAT
INCLUDE io.h
EXTERN GenPrimes2:PROC
PUBLIC genPrimes
.STACK 4096 ; reserve 4096-byte stack
.DATA ; reserve storage for data
count DWORD ?
sieve BYTE 10000 DUP(1)
string BYTE 40 DUP (?)
prompt1 BYTE "Enter number of primes: ", 0
prompt2 BYTE "prime number: ", 0
prompt3 BYTE ", ", 0
primenum DWORD 11 DUP (?), 0
prime BYTE 11 DUP (?), 0
.CODE
genPrimes PROC
; push ebp ; save base pointer
; mov ebp, esp ; establish stack frame
; push ebx
; CODE
call GenPrimes2 ;call function in genprimes.asm to push primes to stack
sub esp, 4 ;move esp down
sub esp, 4 ;esp points to first value
mov ebx, 4 ; counter
mov ecx, 0 ; index register to hold value of esp that will be put into primenum array
loopArray: ;this loop fills primenum with all primes put on the stack in genprimes.asm
mov ecx, [esp]
sub esp, 4
mov primenum[ebx], ecx
add ebx, 4
cmp ebx, 2200
jb loopArray
mov ebx, 4
mov eax, 0
;This loop is for debug purposes only, i want to see if the array primenum has the value 13, which is does
;because i can see it get copied into ecx. However, i get garbage in my output where 13 should be.
PrintLoop2:
mov ecx, primenum[ebx] ; Prime numbers are the non-zeros in this Array
add ebx, 4
cmp ebx, 400
jb PrintLoop2
mov ebx, 4
mov eax, 0
add esp,2204 ;move esp back to return address
ret ;exit genPrimes
genPrimes ENDP
_sieve PROC ; start of sieve program code
input prompt1, string, 40 ; read ASCII characters
call genPrimes
atod string ; convert to integer the number of primes the user entered
mov edx, 0
;this loop will print all the non-zero values stored in the array primenum, i have set all non-primes to 0's so that only
;they will be printed
PrintLoop:
mov ecx, primenum[ebx] ; Prime numbers are the non-zeros in this Array
cmp primenum[ebx], 0
jne printPrime
add ebx, 4
jmp PrintLoop
printPrime:
dtoa prime, ecx ;convert the prime number to a string for printing
output prompt2, prime ; output label and sum
add ebx, 4
inc edx
cmp edx, eax
jb PrintLoop
mov eax, 0 ; exit with return code 0
ret
_sieve ENDP
END
genprimes.asm:
.586
.MODEL FLAT
.STACK 4096
n=550
.data
prime DWORD n DUP(?)
.code
GenPrimes2 PROC
mov ebx, 4
mov ecx, 0
loopArray:
inc ecx
mov prime[ebx], ecx
add ebx, 4
cmp ecx, n
jb loopArray
mov eax, 3
mov ebx, 2
mov edx, 0
mov ecx,3
sieve_loop:
cmp eax,ebx
je skip
mov edx, 0 ;zero out remainder
div ebx
cmp edx,0 ; if remainder 0, not a prime
je NotPrime ;Jump if is a factor, since it cant be prime
; compare eax with n, if equal increment ebx
cmp ecx,n
jge incrementEbx
; compare ebx with n, if equal end sieve
cmp ebx, n
je sieve_end
inc ecx
mov eax, ecx
jmp sieve_loop
skip:
inc eax
jmp sieve_loop
NotPrime:
mov eax, ecx ; store count in eax
imul ecx, 4
mov prime[ecx],0
mov ecx, eax
inc ecx ; increment ecx count
inc eax ; increment eax divisor
jmp sieve_loop
incrementEbx:
inc ebx
mov eax, 3 ; dividend
mov ecx, 3 ; counter
jmp sieve_loop
sieve_end:
mov ebx, 4
mov eax, 0
; ************* Add break point on print loop, ecx will be loading with primes and 0's ********************
; ************* All non-prime numbers have been changed to a 0 ********************
PrintLoop:
mov ecx, prime[ebx] ; Prime numbers are the non-zeros in this Array
push ecx
add ebx, 4
cmp ebx, 2200
jb PrintLoop
add esp,2196
mov eax, 0 ; exit with return code 0
ret
GenPrimes2 ENDP
END
io.asm:
.586
.MODEL FLAT
PUBLIC wtoaproc, atowproc, dtoaproc, atodproc
.CODE
; wtoaproc(source, dest)
; convert integer (source) to string of 6 characters at given destination address
; source integer passed as a doubleword, but only low-order word is processed
wtoaproc PROC
push ebp ; save base pointer
mov ebp, esp ; establish stack frame
push eax ; Save registers
push ebx
push ecx
push edx
push edi
pushfd ; save flags
mov eax, [ebp+8] ; first parameter (source integer)
and eax, 0ffffh ; mask high-order word
mov edi, [ebp+12] ; second parameter (dest offset)
ifSpecW: cmp ax,8000h ; special case -32,768?
jne EndIfSpecW ; if not, then normal case
mov BYTE PTR [edi],'-' ; manually put in ASCII codes
mov BYTE PTR [edi+1],'3' ; for -32,768
mov BYTE PTR [edi+2],'2'
mov BYTE PTR [edi+3],'7'
mov BYTE PTR [edi+4],'6'
mov BYTE PTR [edi+5],'8'
jmp ExitIToA ; done with special case
EndIfSpecW:
push eax ; save source number
mov al,' ' ; put blanks in
mov ecx,5 ; first five
cld ; bytes of
rep stosb ; destination field
pop eax ; restore source number
mov cl,' ' ; default sign (blank for +)
IfNegW: cmp ax,0 ; check sign of number
jge EndIfNegW ; skip if not negative
mov cl,'-' ; sign for negative number
neg ax ; number in AX now >= 0
EndIfNegW:
mov bx,10 ; divisor
WhileMoreW: mov dx,0 ; extend number to doubleword
div bx ; divide by 10
add dl,'0' ; convert remainder to character
mov [edi],dl ; put character in string
dec edi ; move forward to next position
cmp ax,0 ; check quotient
jnz WhileMoreW ; continue if quotient not zero
mov [edi],cl ; insert blank or "-" for sign
ExitIToA: popfd ; restore flags and registers
pop edi
pop edx
pop ecx
pop ebx
pop eax
pop ebp
ret ;exit
wtoaproc ENDP
; dtoaproc(source, dest)
; convert double (source) to string of 11 characters at given destination address
dtoaproc PROC NEAR32
push ebp ; save base pointer
mov ebp, esp ; establish stack frame
push eax ; Save registers
push ebx ; used by
push ecx ; procedure
push edx
push edi
pushfd ; save flags
mov eax, [ebp+8] ; first parameter (source double)
mov edi, [ebp+12] ; second parameter (dest addr)
ifSpecialD: cmp eax,80000000h ; special case -2,147,483,648?
jne EndIfSpecialD ; if not, then normal case
mov BYTE PTR [edi],'-' ; manually put in ASCII codes
mov BYTE PTR [edi+1],'2' ; for -2,147,483,648
mov BYTE PTR [edi+2],'1'
mov BYTE PTR [edi+3],'4'
mov BYTE PTR [edi+4],'7'
mov BYTE PTR [edi+5],'4'
mov BYTE PTR [edi+6],'8'
mov BYTE PTR [edi+7],'3'
mov BYTE PTR [edi+8],'6'
mov BYTE PTR [edi+9],'4'
mov BYTE PTR [edi+10],'8'
jmp ExitDToA ; done with special case
EndIfSpecialD:
push eax ; save source number
mov al,' ' ; put blanks in
mov ecx,10 ; first ten
cld ; bytes of
rep stosb ; destination field
pop eax ; copy source number
mov cl,' ' ; default sign (blank for +)
IfNegD: cmp eax,0 ; check sign of number
jge EndIfNegD ; skip if not negative
mov cl,'-' ; sign for negative number
neg eax ; number in EAX now >= 0
EndIfNegD:
mov ebx,10 ; divisor
WhileMoreD: mov edx,0 ; extend number to doubleword
div ebx ; divide by 10
add dl,30h ; convert remainder to character
mov [edi],dl ; put character in string
dec edi ; move forward to next position
cmp eax,0 ; check quotient
jnz WhileMoreD ; continue if quotient not zero
mov [edi],cl ; insert blank or "-" for sign
ExitDToA: popfd ; restore flags and registers
pop edi
pop edx
pop ecx
pop ebx
pop eax
pop ebp
ret ;exit
dtoaproc ENDP
; atowproc(source)
; Procedure to scan data segment starting at source address, interpreting
; ASCII characters as an word-size integer value which is returned in AX.
; Leading blanks are skipped. A leading - or + sign is acceptable.
; Digit(s) must immediately follow the sign (if any).
; Memory scan is terminated by any non-digit.
; No error checking is done. If the number is outside the range for a
; signed word, then the return value is undefined.
atowproc PROC
push ebp ; save base pointer
mov ebp, esp ; establish stack frame
sub esp, 2 ; local space for sign
push ebx ; Save registers
push edx
push esi
pushfd ; save flags
mov esi,[ebp+8] ; get parameter (source addr)
WhileBlankW:cmp BYTE PTR [esi],' ' ; space?
jne EndWhileBlankW ; exit if not
inc esi ; increment character pointer
jmp WhileBlankW ; and try again
EndWhileBlankW:
mov ax,1 ; default sign multiplier
IfPlusW: cmp BYTE PTR [esi],'+' ; leading + ?
je SkipSignW ; if so, skip over
IfMinusW: cmp BYTE PTR [esi],'-' ; leading - ?
jne EndIfSignW ; if not, save default +
mov ax,-1 ; -1 for minus sign
SkipSignW: inc esi ; move past sign
EndIfSignW:
mov [ebp-2],ax ; save sign multiplier
mov ax,0 ; number being accumulated
WhileDigitW:cmp BYTE PTR [esi],'0' ; next character >= '0'
jnge EndWhileDigitW ; exit if not
cmp BYTE PTR [esi],'9' ; next character <= '9'
jnle EndWhileDigitW ; not a digit if bigger than '9'
imul ax,10 ; multiply old number by 10
mov bl,[esi] ; ASCII character to BL
and bx,000Fh ; convert to single-digit integer
add ax,bx ; add to sum
inc esi ; increment character pointer
jmp WhileDigitW ; go try next character
EndWhileDigitW:
; if value is < 8000h, multiply by sign
cmp ax,8000h ; 8000h?
jnb endIfMaxW ; skip if not
imul WORD PTR [ebp-2] ; make signed number
endIfMaxW:
popfd ; restore flags
pop esi ; restore registers
pop edx
pop ebx
mov esp, ebp ; delete local variable space
pop ebp
ret ; exit
atowproc ENDP
; atodproc(source)
; Procedure to scan data segment starting at source address, interpreting
; ASCII characters as an doubleword-size integer value which is returned in EAX.
; Leading blanks are skipped. A leading - or + sign is acceptable.
; Digit(s) must immediately follow the sign (if any).
; Memory scan is terminated by any non-digit.
; No error checking is done. If the number is outside the range for a
; signed word, then the return value is undefined.
atodproc PROC
push ebp ; save base pointer
mov ebp, esp ; establish stack frame
sub esp, 4 ; local space for sign
push ebx ; Save registers
push edx
push esi
pushfd ; save flags
mov esi,[ebp+8] ; get parameter (source addr)
WhileBlankD:cmp BYTE PTR [esi],' ' ; space?
jne EndWhileBlankD ; exit if not
inc esi ; increment character pointer
jmp WhileBlankD ; and try again
EndWhileBlankD:
mov eax,1 ; default sign multiplier
IfPlusD: cmp BYTE PTR [esi],'+' ; leading + ?
je SkipSignD ; if so, skip over
IfMinusD: cmp BYTE PTR [esi],'-' ; leading - ?
jne EndIfSignD ; if not, save default +
mov eax,-1 ; -1 for minus sign
SkipSignD: inc esi ; move past sign
EndIfSignD:
mov [ebp-4],eax ; save sign multiplier
mov eax,0 ; number being accumulated
WhileDigitD:cmp BYTE PTR [esi],'0' ; compare next character to '0'
jl EndWhileDigitD ; not a digit if smaller than '0'
cmp BYTE PTR [esi],'9' ; compare to '9'
jg EndWhileDigitD ; not a digit if bigger than '9'
imul eax,10 ; multiply old number by 10
mov bl,[esi] ; ASCII character to BL
and ebx,0000000Fh ; convert to single-digit integer
add eax,ebx ; add to sum
inc esi ; increment character pointer
jmp WhileDigitD ; go try next character
EndWhileDigitD:
; if value is < 80000000h, multiply by sign
cmp eax,80000000h ; 80000000h?
jnb endIfMaxD ; skip if not
imul DWORD PTR [ebp-4] ; make signed number
endIfMaxD:
popfd ; restore flags
pop esi ; restore registers
pop edx
pop ebx
mov esp, ebp ; delete local variable space
pop ebp
ret ; exit
atodproc ENDP
END
framework.c
#include <windows.h>
#include <stdio.h>
static char buf[255];
static char inputLabel[255];
// disables warning for strcpy use
#pragma warning(disable : 4996)
void getInput(char* inputPrompt, char* result, int maxChars)
{
puts(inputPrompt);
gets(buf);
buf[maxChars - 1] = '\0';
strcpy(result,buf);
return;
}
void showOutput(char* outputLabel, char* outputString)
{
printf("%s %s\n",outputLabel,outputString);
}
int sieve(void);
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
LPSTR lpCmdLine, int nCmdShow)
{
AllocConsole();
freopen("CONIN$" , "rb", stdin);
freopen("CONOUT$", "wb", stdout);
return sieve();
}
Upvotes: 3
Views: 940
Answers (1)
Sep Roland
Reputation: 39306
Several buffer overflows.
primenum DWORD 11 DUP (?), 0
Although primenum has only 12 dwords available, your program writes 549 dwords in this array!
prime DWORD n DUP(?)
The loop that initializes this array writes 1 dword beyond it! Verify it.
Returning values on the stack.
mov ebx, 4 PrintLoop: mov ecx, prime[ebx] ; Prime numbers are the non-zeros in this Array push ecx add ebx, 4 cmp ebx, 2200 jb PrintLoop add esp,2196 mov eax, 0 ; exit with return code 0 ret
First you push 549 dwords on the stack and then by executing add esp, 2196 you effectively say that you don't care about them anymore.
Values that are to be returned via the stack must stay above the stackpointer.
You can simply temporarily remove the return address and then, before ret, put it back.
pop eax ; Temporarily remove return address
mov ebx, 4
PrintLoop:
mov ecx, prime[ebx] ; Prime numbers are the non-zeros in this Array
push ecx
add ebx, 4
cmp ebx, 2200
jb PrintLoop
push eax ; Put back return address
xor eax, eax ; exit with return code 0
ret
Of course this effects how the caller needs to process these values.
call GenPrimes2 ;call function in genprimes.asm to push primes to stack
lea ebp, [esp + 2196] ; EBP points beyond first value
xor ebx, ebx
loopArray: ; fills primenum with all primes pushed in genprimes.asm
add ebx, 4
sub ebp, 4
mov ecx, [ebp]
mov primenum[ebx], ecx
cmp ebp, esp
ja loopArray
mov ebx, 4
mov eax, 0
add esp, 2196 ; Permanently remove results from stack
ret
; compare eax with n, if equal increment ebx cmp ecx,n jge incrementEbx
Please notice that the comment doesn't match the code (eax vs ecx).
mov ecx, primenum[ebx] ; Prime numbers are the non-zeros in this Array cmp primenum[ebx], 0 jne printPrime
Here's an obvious optimization. Since you just loaded the number in ECX, it would be better to perform the test on the register.
mov ecx, primenum[ebx] ; Prime numbers are the non-zeros in this Array
test ecx, ecx
jnz printPrime
Upvotes: 3
Related Questions
- Why is my array not changing in x86 Assembly MASM
- Assembly: Issues with Indexing
- Trying to write a program that prints prime numbers in MIPS Assembly language
- Printing Prime Numbers in Assembly
- Prime numbers program error (MASM)
- strange behavior with array
- Finding prime number in nasm
- MIPS assembly, Multiplication error for finding primes above 2^16
- Trouble with prime number program in Assembly
- Logical error in prime numbers