CSC231 Homework 8 Solution Program 2010
--D. Thiebaut 23:35, 21 November 2010 (UTC)
;;; ; File: hw8.asm
;;; ; Author: Tiffany Q. Liu
;;; ; Acct: 231a-ac
;;; ; Date: November 17, 2010
;;; ; Desc: Programs Conway's Game of Life in one dimension. Starts with a
;;; ; generation containing 70 cells. Each cell can either be dead (0 or
;;; ; '.') or alive (1 or '@'). The next generation of cells is determined
;;; ; by a rule, which states that a cell is alive when it had one
;;; ; neighbor cell that was alive in the previous generation and a cell
;;; ; is dead when it either had two dead neighbor cells (underpopulation)
;;; ; in the previous generation or two alive neighbor cells
;;; ; (overpopulation) in the previous generation. This program prints out
;;; ; 20 generations of 70 cells, one above the next, one line at a time.
;;; ; The program utilizes the stack to pass parameters and return values
;;; ; between functions.
;;; ;
;;; ; to assemble and run:
;;; ;
;;; ; nasm -f elf -F stabs hw8.asm
;;; ; ld -melf_i386 -o hw8 hw8.o
;;; ; ./hw8
;;; ;
;;; ; Output:
;;; ; .@...@..@@@@..@@.@@@.@@....@@..@...@..@@@@..@@.@@@.@@....@@..@...@..@@
;;; ; @.@.@.@@@..@@@@@.@.@.@@@..@@@@@.@.@.@@@..@@@@@.@.@.@@@..@@@@@.@.@.@@@@
;;; ; ......@.@@@@...@.....@.@@@@...@.....@.@@@@...@.....@.@@@@...@.....@..@
;;; ; .....@..@..@@.@.@...@..@..@@.@.@...@..@..@@.@.@...@..@..@@.@.@...@.@@.
;;; ; ....@.@@.@@@@....@.@.@@.@@@@....@.@.@@.@@@@....@.@.@@.@@@@....@.@..@@@
;;; ; ...@..@@.@..@@..@....@@.@..@@..@....@@.@..@@..@....@@.@..@@..@...@@@.@
;;; ; ..@.@@@@..@@@@@@.@..@@@..@@@@@@.@..@@@..@@@@@@.@..@@@..@@@@@@.@.@@.@..
;;; ; .@..@..@@@@....@..@@@.@@@@....@..@@@.@@@@....@..@@@.@@@@....@...@@..@.
;;; ; @.@@.@@@..@@..@.@@@.@.@..@@..@.@@@.@.@..@@..@.@@@.@.@..@@..@.@.@@@@@.@
;;; ; ..@@.@.@@@@@@@..@.@....@@@@@@..@.@....@@@@@@..@.@....@@@@@@....@...@..
;;; ; .@@@...@.....@@@...@..@@....@@@...@..@@....@@@...@..@@....@@..@.@.@.@.
;;; ; @@.@@.@.@...@@.@@.@.@@@@@..@@.@@.@.@@@@@..@@.@@.@.@@@@@..@@@@@.......@
;;; ; @@.@@....@.@@@.@@...@...@@@@@.@@...@...@@@@@.@@...@...@@@@...@@.....@.
;;; ; @@.@@@..@..@.@.@@@.@.@.@@...@.@@@.@.@.@@...@.@@@.@.@.@@..@@.@@@@...@.@
;;; ; @@.@.@@@.@@....@.@.....@@@.@..@.@.....@@@.@..@.@.....@@@@@@.@..@@.@...
;;; ; @@...@.@.@@@..@...@...@@.@..@@...@...@@.@..@@...@...@@....@..@@@@..@..
;;; ; @@@.@....@.@@@.@.@.@.@@@..@@@@@.@.@.@@@..@@@@@.@.@.@@@@..@.@@@..@@@.@.
;;; ; @.@..@..@..@.@.......@.@@@@...@.....@.@@@@...@.....@..@@@..@.@@@@.@..@
;;; ; ...@@.@@.@@...@.....@..@..@@.@.@...@..@..@@.@.@...@.@@@.@@@..@..@..@@.
;;; ; ..@@@.@@.@@@.@.@...@.@@.@@@@....@.@.@@.@@@@....@.@..@.@.@.@@@.@@.@@@@@
;;; ; -------------------------------------------------------------------
EXIT equ 1
WRITE equ 4
STDOUT equ 1
;;; ------------------------------------------------------------
;;; data areas
;;; ------------------------------------------------------------
section .data
lifeCh db ' ' ; character to print for a cell
saveCnt dd 0 ; used to save counter from ecx
lf db 0x0a ; linefeed character
N dd 70 ; # of cells per generation
numGen dd 20 ; # of generations to compute & print
x dd 53 ; used for pseudo-random # generation
rule db '.', '@' ; array used to determine the character
; to print based on the value in the
; cell (0 - '.'dead, and 1 - '@' alive)
fate db 0, 1, 0 ; used to determine the fate of the cell
; based on the # of neighbors it had in
; the previous generation (0 - 0, 1 - 0,
; 0 - 0)
section .bss
life resb 70 ; array holding current generation of
; life cells
resb 1 ; pad beginning with a dead cell
oldLife resb 70 ; temp array holding previous life cells ; used to determine next generation
resb 1 ; pad end with a dead cell
;;; ------------------------------------------------------------
;;; code area
;;; ------------------------------------------------------------
section .text
global _start
;;; ---------------------------
;;; main(): Initiates definition
;;; of the first generation of
;;; cells and initiates printing
;;; and computing of 20
;;; generations.
;;; ---------------------------
_start:
push dword[N] ; defFirstGen(N, *life): call to
push life ; function that defines the
call defFirstGen ; 1st gen. of N cells in the array life
push dword[N] ; compPrintLife(N, *life, *oldLife,
push life ; numGen): call to
push oldLife ; function that computes and prints N
push dword[numGen] ; cells in array life for numGen of
call compPrintLife ; generations
;;; exit()
mov eax, EXIT
mov ebx, 0
int 0x80 ; final system call
;;; ---------------------------
;;; defFirstGen(N, *life):
;;; Initializes the cells that
;;; are to be alive for the 1st
;;; generation in life with 1.
;;; Life of a cell is determined
;;; using pseudo-randomization.
;;; ---------------------------
defFirstGen:
push ebp ; save old ebp pointer
mov ebp, esp ; initialize new ebp pointer
pushad ; push all registers
;;; Macros: number of cells and pointer to the life array
%define dfg_numCell dword[ebp + 12]
%define dfg_life dword[ebp + 8]
mov esi, dfg_life ; esi points to life array
mov ecx, dfg_numCell ; loop counter = number of cells
.for:
;;; calculate pseudo-random
;;; value x:
;;; x = (x * 17) % 31
xor edx, edx
mov eax, dword[x]
mov ebx, 17
mul ebx
mov ebx, 31
div ebx
mov dword[x], edx
;;; convert pseudo-random
;;; number x to either 0 or 1
;;; by taking the mod of 2
xor edx, edx
mov eax, dword[x]
mov ebx, 2
div ebx
mov byte[esi], dl
inc esi
loop .for
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 2*4 ; return with 2 paramemters popped from
; stack
;;; ---------------------------
;;; compPrintLife(N, *life,
;;; *oldLife,
;;; numGen):
;;; Computes and print numGen
;;; of generation with N cells
;;; per generation. The current
;;; generation to compute and
;;; print is stored in the life
;;; array and the previous
;;; generation is stored
;;; temporarily in oldLife to
;;; compute the current
;;; generation.
;;; ---------------------------
compPrintLife:
push ebp ; save old ebp pointer
mov ebp, esp ; initialize new ebp pointer
pushad ; push all registers
;;; Macros: number of cells, pointer to life array, pointer to oldLife array,
;;; and number of generations
%define cpl_numCell dword[ebp + 20]
%define cpl_life dword[ebp + 16]
%define cpl_oldLife dword[ebp + 12]
%define cpl_numGen dword[ebp + 8]
mov ecx, cpl_numGen ; loop counter = # of generations
mov esi, cpl_life ; esi points to life array
mov edi, cpl_oldLife ; edi points to oldLife array
mov eax, cpl_numCell ; eax <- number of cells
.for:
push eax ; printGen(N, *life): calls function to
push esi ; print current generation of N cells in
call printGen ; life array
push eax ; compNextGen(N, *life, *oldLife): call
push esi ; function to compute next generation of
push edi ; N cells in life array
call compNextGen
loop .for
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 4*4 ; return with 4 parameters popped from
; stack
;;; ---------------------------
;;; printGen(N, *life):
;;; Prints the current generation
;;; of N cells in the life array
;;; by converting the number in
;;; each cell with its
;;; corresponding character
;;; defined by the rule array.
;;; ---------------------------
printGen:
push ebp ; save old ebp pointer
mov ebp, esp ; intialize new ebp pointer
pushad ; push all registers
;;; Macros: number of cells and pointer to life array
%define pg_numCell dword[ebp + 12]
%define pg_life dword[ebp + 8]
mov ecx, pg_numCell ; loop counter = number of cells
mov esi, pg_life ; edi points to life array
.for:
mov dword[saveCnt], ecx ; save loop counter to saveCnt
mov eax, WRITE ; prepare to print
xor ebx, ebx ; clear out ebx
xor edx, edx ; clear out edx
mov bl, byte[esi] ; bl <- value from life array (0 or 1)
mov dl, byte[rule + ebx] ; dl <- converted character ('.' or '@')
mov byte[lifeCh], dl ; lifeCh <- character
mov ebx, STDOUT ; prepare to print
mov ecx, lifeCh ; ecx <- pointer to lifeCh
mov edx, 1 ; length of string to print = 1 char
int 0x80 ; print character
inc esi ; esi points to next item in life array
mov ecx, dword[saveCnt] ; restore loop counter to ecx
loop .for
mov eax, WRITE ; print linefeed character at the end of
mov ebx, STDOUT ; each generation of cells
mov ecx, lf
mov edx, 1
int 0x80
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 2*4 ; return with 2 parameters popped from
; stack
;;; ---------------------------
;;; compNextGen(N, *life, *oldLife):
;;; Computes the next generation
;;; of N cells. First saves the
;;; previous generation in
;;; oldLife. Then uses oldLife
;;; to compute number of live
;;; neighbor cells in previous
;;; generation. Then each cell
;;; is either going to be dead
;;; or alive in the current
;;; generation based on the
;;; number of neighbors it had
;;; in the previous generation
;;; and the fate array.
;;; ---------------------------
compNextGen:
push ebp ; save old ebp pointer
mov ebp, esp ; intialize new ebp pointer
pushad ; push registers
;;; Macros: number of cells, pointer to life array, pointer to oldLife array,
;;; number of neighbors for a current cell
%define cng_numCell dword[ebp + 16]
%define cng_life dword[ebp + 12]
%define cng_oldLife dword[ebp + 8]
%define cng_numNeigh dword[ebp - 36]
mov ecx, cng_numCell ; loop counter = number of cells
mov esi, cng_life ; esi points to life array
mov edi, cng_oldLife ; edi points to oldLife array
push ecx ; savePastLife(N, *life, *oldLife):
push esi ; calls function to save values of N
push edi ; cells in life array to oldLife array
call savePastLife
push eax ; push dummy variable to stack to store
; number of neighbors
.for:
push edi ; compNumNeighbors(*oldLife): calls
call compNumNeighbors ; function to compute number of
; neighbors the current cells had in
; previous generation
mov ebx, cng_numNeigh ; ebx <- number of neighbors
mov al, byte[fate + ebx] ; determine whether cell is dead or
mov byte[esi], al ; alive in next generation using
; numNeigh and fate array
inc esi ; esi points to next cell in life
inc edi ; edi points to next cell in oldLife
loop .for
pop eax ; pop numNeigh variable from stack
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 3*4 ; return with 3 parameters popped from
; stack
;;; ---------------------------
;;; savePastLife(N, *life, *oldLife):
;;; Saves the cells from the
;;; previous generation by
;;; copying the values in the
;;; N cells of life to the N
;;; cells of oldLife.
;;; ---------------------------
savePastLife:
push ebp ; save old ebp pointer
mov ebp, esp ; initialize new ebp pointer
pushad ; push registers
;;; Macros: number of cells, pointer to life array, pointer to oldLife array
%define spl_numCell dword[ebp + 16]
%define spl_life dword[ebp + 12]
%define spl_oldLife dword[ebp + 8]
mov ecx, spl_numCell ; loop counter = number of cells
mov esi, spl_life ; esi points to life array
mov edi, spl_oldLife ; edi points to oldLife array
;;; Copy every value in life array to oldLife array one cell at a time
.for:
mov al, byte[esi]
mov byte[edi], al
inc esi
inc edi
loop .for
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 3*4 ; return with 3 parameters popped from
; stack
;;; ---------------------------
;;; compNumNeighbors(
;;; *currCellOfOldLife):
;;; Computes the number of
;;; neighbors to the current
;;; cell of oldLife by adding
;;; the values in the cells to
;;; the left and right of the
;;; current cell. numNeigh
;;; returned from function via
;;; stack.
;;; ---------------------------
compNumNeighbors:
push ebp ; save old ebp pointer
mov ebp, esp ; initialize new ebp pointer
pushad ; push registers
;;; Macros: number of neighbors, pointer to oldLife array
%define cnn_numNeigh dword[ebp + 12]
%define cnn_oldLife dword[ebp + 8]
mov esi, cnn_oldLife ; esi points to current cell in oldLife
xor eax, eax ; clear out eax
mov al, byte[esi - 1] ; al <- value of left neighbor
add al, byte[esi + 1] ; al <- al + value of right neighbor
mov cnn_numNeigh, eax ; numNeigh <- left neigh + right neigh
popad ; restore registers
pop ebp ; restore old ebp pointer
ret 1*4 ; return with 1 parameter popped from
; stack
