CSC231 Homework 8 Fall 2017

--D. Thiebaut (talk) 13:57, 27 November 2017 (EST)

---

This homework assignment is due Monday Dec. 4th, at 11:55 p.m.

Problem #1

Write an assembly program called hw8a.asm that contains several functions, but no main program. In other words, your program should not contain a "_start" label. The main program will be in a separate file that will be assembled separately, and linked to your program to create an executable file.

The functions should behave as follows:

• f1( s ). Receives the address of a string s in the stack, and converts the string to uppercase, replacing all the alphabetic characters in the string to uppercase. We assume that the string, as in C, is terminated by a '\0' char. Here is an example of how to call the function:

s1          db       "Hello world!", 0
s1Len       equ      $-s1

 ...

             mov     eax, s1
             push    eax
             call    f1

             mov    ecx, s1
             mov    edx, s1Len-1    ; figure out why the -1!
             mov    eax, 4
             mov    ebx, 1
             int    0x80

The code above will print "HELLO WORLD!"

• f2(a, b, c): f2 receives 3 integer parameters in the stack and computes 2a + 3b -c and returns this value in eax.

Here is an example of how to call the function:

a           dd       3
b           dd       5
c           dd       7

 ...
             push    dword[a]
             push    dword[b]
             push    dword[c]
             call    f2
             
; upon return from f2, eax will contain 2a + 3b - c = 2*3 + 3*5 - 7 = 14

• f3( table, n ): this function receives in the stack the address of an array of ints, and the number of ints in the array. It returns in eax the number of even ints in the array. f3 should not modify any of the other registers, besides eax, of course!

Here is an example of how to call the function f3:

array     dd       3, 5, 0, 1, 2, 10, 100, 4, 1
arrayLen  equ      ($-array)/4                      ; figure out the /4 part.


 ...
             mov     eax, array
             push    eax
             mov     eax, arrayLen
             push    eax
             call    f3
             ; upon return from f3, eax contains 5, because there are 5 even numbers in array.

Making Your Functions Known to Other Programs

Your hw8a.asm program should contain only the 3 functions described above. You may add other helper functions if it makes your programming task easier. For example, you may want to have a function that tests an integer and returns 1 or 0 depending on whether the integer is even or not. No need for a data segment or for a _Start label. However, you need to make your functions known to the main program that is in a different file, and that will be linked with your program. So you need to add these 3 lines at the top of your program:

           global f1
           global f2
           global f3

Testing Your Code

Create the following program and call it test.asm. It will be the test program for your hw8b.asm program:

;;;------------------------------------------------------------
;;; test.asm     
;;; tests the functions in hw8_2.asm by calling each one
;;; and printing its result.
;;;------------------------------------------------------------
	extern	_printString
	extern	_println
	extern 	_printDec

	extern	f1        ; f1, f2, and f3 are declared somewhere else
	extern  f2
	extern	f3

;;;------------------------------------------------------------
;;; some variables to pass to the functions
;;;------------------------------------------------------------
	 section .data
s1	 db	 "Hello there! 12345", 0
s1Len	 equ	 $-s1
Table	 dd	 1, 2, 3, 30, 100, 200
TableLen equ	 ($-Table)/4
x1	 dd	 10
x2	 dd	 20
x3	 dd	 -1

;;;------------------------------------------------------------
;;; main program
;;;------------------------------------------------------------
	 section .text
	 global	 _start
_start:
;;; test f1
	 mov	 eax, s1	; pass s1 to f1
	 push	 eax
	 call	 f1
	 mov	 ecx, s1
	 mov	 edx, s1Len
	 call	 _printString
	 call	 _println
	
;;; test f2
	 push	dword[x1]	; pass x1, x2, x3 to f2
	 push	dword[x2]
	 push	dword[x3]
	 call	f2
	 call	_printDec
	 call	_println

;;; test f3
	 mov	eax, Table	; pass Table and length to f3
	 push	eax
	 mov	eax, TableLen
	 push	eax
	 call	f3
	 call	_printDec
	 call	_println
	
;;; ; exit
	mov     ebx, 0
	mov     eax, 1
	int     0x80

• Assemble, link, and run as follows:

231b@aurora ~ nasm -f elf test.asm
231b@aurora ~ nasm -f elf hw8a.asm
231b@aurora ~ nasm -f elf 231Lib.asm
231b@aurora ~ ld -melf_i386  -o test test.o hw8a.o 231Lib.o
231b@aurora ~ ./test
HELLO THERE! 12345
81
4

Note

The test program above does not check whether f3 modifies the ebx, ecx, edx, esi, or edi registers. You can verify this yourself (maybe by printing the registers before and after the call to f3)!

Problem 2

Java Program

/*
Series.java
Homework program with a recursive function.
*/

class Series {

    /**
       sumNSquared: returns the sum 1 + 2*2 + 3*3 + 4*4 +... + n*n
       The computation is done recursively.
     */
    private static int sumNSquared( int n ) {
	
	if ( n <= 1 ) return 1;
	return n*n + sumNSquared( n-1 );
    }

    public static void main( String args[] ) {
	int n =  Integer.parseInt ( args[0] );
	System.out.print( "sumNSquared(" + n + ")=" + sumNSquared(n) +"\n\n" );
    }
}

Example

cs231a@aurora ~ $ javac Series.java 
cs231a@aurora ~ $ java Series 1
sumNSquared(1)=1

cs231a@aurora ~ $ java Series 2
sumNSquared(2)=5

cs231a@aurora ~ $ java Series 10
sumNSquared(10)=385

cs231a@aurora ~ $ java Series 100
sumNSquared(100)=338350

Questions

Please answer the following questions on Moodle:

Question 1

What is the smallest integer number provided on the command line that will generate an arithmetic overflow of the result?

Question 2

Will the Java Virtual Machine crash when an airthmetic overflow of the result occurs in the program?

Question 3

How many recursive calls will take place before a stack overflow error occurs?

Problem 3

Create an assembly program called hw8c.asm that implements the program of Problem 2, with a slight modification: your program will prompt the user for a number, and will output the series corresponding to that number.

Examples

cs231a@aurora ~ $ ./hw8c
> 5
55
cs231a@aurora ~ $ ./hw8c 
> 1
1
cs231a@aurora ~ $ ./hw8c
> 10
385

Submission

Submit your program in the Homework 8 Problem 3 section on Moodle.

Solution Program

Problem 1

;;; ------------------------------------------------------
;;; hw8_2.asm
;;; D. Thiebaut
;;; ------------------------------------------------------

	global 	f1
	global	f2
	global	f3

;;; ------------------------------------------------------
;;; f1( s ): modifies s in place and make it uppercase.
f1:	push	ebp
	mov	ebp, esp
	push	ebx
	mov	ebx, dword[ebp+8]
.for:	cmp	byte[ebx], 0
	je	.done
	cmp	byte[ebx],'a'
	jl	.endfor
	cmp	byte[ebx],'z'
	jg	.endfor
	add	byte[ebx],'A'-'a'
.endfor:
	inc	ebx
	jmp	.for
.done:
	pop	ebx
	pop	ebp
	ret	4

;;; ------------------------------------------------------
;;; f2( a, b, c )
;;; returns 2a + 3b -c in eax
;;; computes it as 2(a+b) + b - c (fewer operations)
f2:	push	ebp
	mov	ebp, esp
	mov	eax, dword[ebp+8+4+4] ; get first param
	add	eax, dword[ebp+8+4]   ; eax <- a+b
	add	eax, eax	      ; eax <- 2(a+b)
	add	eax, dword[ebp+8+4]   ; eax <- 2(a+b) + b
	sub	eax, dword[ebp+8]     ; eax <- 2a + 3b -c
	pop	ebp		      ;
	ret	4*3		      ; return and get rid of 3 ints


;;; ------------------------------------------------------
;;; f3( array, n )
;;; computes the number of even ints in array, of length n.
;;; returns this number in eax.
f3:	push	ebp
	mov	ebp, esp
	
	push	ebx
	push	ecx
	
	mov	ebx, dword[ebp+8+4] 	; ebx <- array
	mov	ecx, dword[ebp+8]	; ecx <- n
	mov	eax, 0			; number of even ints
.for:	and	dword[ebx], 1		; and array[i] with 1
	jnz	.notEven		; if result is 1, then odd number
.even:	inc	eax			; otherwise, add 1 to counter.
.notEven:
	add	ebx, 4
	loop	.for

	pop	ecx
	pop	ebx
	
	pop	ebp
	ret	2*4

Problem 2

Question 1: what value of n creates an overflow?  
Answer: 1861

1860
sumNSquared(1860)=2146682110

1861
sumNSquared(1861)=-2144821865


Question 2: The Java VM does not crash when the number provided on the command line generates an overflow

Question 3: We use bash:
 
 for i in `seq 9000 10000` ; do java Series $i ; done &> output.txt
 
The bash loop above runs the Series program for all values of i ranging in 9000 to 10000, 
and outputs both stdout and stderr to the file output.txt
 
 grep -B 5  -i stackOverflow output.txt | head -n 10

The command above looks for the lines containing "stackoverflow", and ask to see 
5 lines BEFORE the matching line (-B 5).   The "head -n 10" pipe keeps only the 
first 10 lines of the output of grep:

Here's the output of the bash command: 
 
sumNSquared(9923)=-675808722
 
sumNSquared(9924)=-577322946
 
Exception in thread "main" java.lang.StackOverflowError
--
at Series.sumNSquared(Series.java:15)
at Series.sumNSquared(Series.java:15)
at Series.sumNSquared(Series.java:15)
 
 
So the answer is that the stack overflow occurs for n = 9925.

Problem 3

;;; --------------------------------------------------
;;; hw8c.asm
;;; D. Thiebaut
;;; Uses a recursive function to compute
;;; n*n + (n-1)*(n-1) + ... + 3*3 + 2*2 + 1*1
;;; 
;;; --------------------------------------------------

	section	.data
n	dd	0
prompt	db	"> "
	
	section	.text
	global	_start
	extern	_printInt
	extern	_println
	extern  _getInput
	extern  _printString
	
;;; --------------------------------------------------
;;; def series( n ):
;;;     if n==1:
;;;         return 1
;;;     res = series( n-1 )
;;;     return n*n + res
;;; --------------------------------------------------
;;; passes n in stack, returns result in eax
series:	push	ebp
	mov	ebp, esp

	push	ebx		;save regs used by function
	push	edx
	
.if:	cmp	dword[ebp+8], 1
	jg	.recurse
	mov	eax, 1
	jmp	.endSeries

.recurse:
	mov	eax,dword[ebp+8]
	mul	dword[ebp+8]
	push	eax		;save n*n in stack, temporarily

	mov	eax,dword[ebp+8] ;eax <- n
	dec	eax		;eax <- n-1
	push	eax		;pass n-1 to fact
	call	series		;eax <- series(n-1)
	pop	ebx		;get n*n
	add	eax,ebx		;eax <- n*n + series(n-1)

.endSeries:
	pop	edx
	pop	ebx
	
	pop	ebp
	ret	4
	
;;; def main():
;;; 	n = 5
;;; 	print( series( n ) )
;;; main()
	
_start:
	;; get n from user
	mov	ecx, prompt
	mov	edx, 2
	call	_printString
	call	_getInput
	mov	dword[n], eax

	;; call series
	push	dword[n]
	call	series

	;; print result passed in eax
	call	_printInt
	call	_println

exit:
	mov	eax, 1
	mov	ebx, 0
	int 	0x80