CSC231 Homework 9 2012
--D. Thiebaut 14:38, 7 November 2012 (EST)
Contents
Problem 1: Running out of stack...
Given the assembly language program shown below:
;;; hw9.asm
;;; D. Thiebaut
;;; displays a simple hello msg on the screen using int 0x80,
;; in a loop that goes around "many" times!
;;; To assemble, link and run:
;;;
;;; nasmld hw9
;;;
EXIT equ 1
READ equ 3
WRITE equ 4
STDOUT equ 1
;; -------------------------------------
;; data segment
;; -------------------------------------
section .data
msg db "hello world!",0x0a
MSGLEN equ $-msg
;; -------------------------------------
;; code segment
;; -------------------------------------
section .text
global _start
_start: mov ecx, 0 ; get ready to loop
for: mov eax,WRITE ; print message
mov ebx,STDOUT ; to screen
push ecx
mov ecx,msg ; address of msg
mov edx,MSGLEN ; # chars to print
int 0x80 ; ask os to pring msg
pop ecx
push ecx
loop for
;; exit
mov eax,EXIT ; return to OS
mov ebx,0
int 0x80
You will notice that the loop uses ecx as a counter, and int 0x80 uses ecx as well to hold the address of the string to print. The programmer decided to use the stack to push and pop the contents of ecx representing the loop counter. Unfortunately, this programmer uses one too many push instructions. The instruction in red is a bug. The ecx register is pushed twiced in the loop, but popped only once. As a result the stack will grow by one double-word every time the loop goes through one round.
Assume that when the executable version of the hw9 program is loaded into memory, the code is stored first, then the data, then the space for the stack is reserved on top of the data.
| | high memory addresses
+--------------+
| |<--- ESP
| stack |
| |
| |
| |
+--------------+
| data |
| |
+--------------+
| |
| code |
| |
+--------------+
| |
| |
| | low memory addresses
Before letting the processor start to execute the first instruction of the program, the operating system will set the ESP register to point to the top of the stack.
- Question 1
- How many lines "hello world" would the program print if it didn't have a bug in it?
- Question 2
- Assume that Linux gives every program a stack of a 1000 bytes when it is loaded into memory. What will happen to this buggy program when it is loaded and executed? Will it run to completion? Will it stop before completing? How will it stop? How many lines "hello world" will it print?
- Question 3
- Imagine that the output of the program is captured to paper. Hence we have a huge collection of "hello world" strings printed on paper. How will we notice the effect of the bug on paper? In other words, what will be printed that will show the effect of the bug?
- Question 4
- How many lines of "hello world" will the buggy program print? Although you may not get the exact number, try to be precise in evaluating this number of lines.
Submission
Save your answers in a file called hw9.txt and submit it as follows:
submit hw9 hw9.txt
Make sure to include your name and account number at the top of the file.
Problem #2: Game of Life in 1D
- Assignment 1
Watch Conway talk about the Game of Life on YouTube (Parts 1 and 2).
- Assignment 2
Read the page on Conway's Game of Life on Wikipedia. Great introduction.
- Assignment 3
Your assignment is simple, and you have to write a program that you may have already written in one or two different languages before: [Conway's Game of Life]. The challenge this time, is that it must be done in assembly, using functions where parameters are passed through the stack and not via registers, and you have to write it without the compare instruction that would normally be used for this purpose (I'll show you a way around it).
Details
- Your program should be called hw9.asm
- It should maintain the cells in a 1-dimensional array of size (at least) 70
- Each cell can be either dead or alive. Dead cells are printed as spaces (or dots), life cells with a character of your choice.
- You are free to choose the initial population in the array
- The rules are simple:
- If a cell has 2 live neighbors in a generation, it dies in the next (overpopulation).
- If a cell has no live neighbors in a generation, it dies in the next (underpopulation).
- If a cell has only one live neighbor in a generation, it either remains alive in the next, or is born in the next.
- Your program will print each generation one above the next, one line at a time.
- Your program should print at least 20 generations, but no more than 60, so as to limit the size of the printout I'll hand back to you.
- Below is an example generated by the applet on Garret Wilson's page, where the initial population was of size 6, distributed as follows: ..XXX.XXX....... where dots are dead, and Xs are alive.
Requirements
- Top-Down design
- Use functions for everything. At least one for computing the new generation, one for printing it.
- Functions cannot pass information through registers. Only via the stack!
Tricks
- At some point you will have to compute the number of neighbors for each cell. A simple way to do this is to maintain your array of cells as a collection of integers that are either 0 or 1, 0 for dead, one for alive. Then when you want to compute the number of neighbors of cell Cell[i], you add together Cell[i-1] to Cell[i+1]. You will get 0, 1, or 2. You can create another array containing the rules of the game, so that you know how what the fate of the cell is by looking it up in the array.
fate db 0, 1, 0
- if the number of neighbors is stored in ebx, for example, then mov al,[fate+ebx] will put the fate of the cell in al. This is the type of trick you can use when you can't compare ebx to 0, 1 or 2.
Submission
submit hw9 hw9.asm
