CSC231 Homework 11 Solutions 2012
--D. Thiebaut 09:55, 12 December 2012 (EST)
Problem 1
;;; Julia Edwards
;;; 231a-aa
;;; December 1, 2012
;;; dumpRegs.inc
;;;
;;; Uses functions to print out the contents of the registers:
;;; eax, ebx, ecx, edx, edi, esi
;;; in hexadecimal, as an unsigned int, and as a signed int.
;;; The signed and unsigned ints are separated with commas,
;;; as is appropriate. They are printed out through calls
;;; to a recursive function, printDecimal.
;;; E.g.:
;;;
;;; ---------------------------------------------
;;; eax = 0x00000004 4 4
;;; ebx = 0x00000001 1 1
;;; ecx = 0xFFFFFFFF 4,294,967,295 -1
;;; edx = 0x000012FC 4,860 4,860
;;; edi = 0xFFFFFFFE 4,294,967,294 -2
;;; esi = 0x12235557 304,305,495 304,305,495
;;; ---------------------------------------------
;;;
;;; LIMITATIONS:
;;; **Because the (register's) counter is a word variable, this puts
;;; a limitation on the number of registers that could be printed.
;;; Luckily, we have far less than 1024 registers, but that is the
;;; max number of registers which can hypothetically be printed.
;;;
;;; **Because registers can only hold up to 4 bytes (one dword), the
;;; max number that will be printed is 0xFFFFFFFF = 4,294,967,295 or -1.
;;;
;;;
;;; MAX STACK SPACED USED:
;;;
;;; The maximum stack space that is used depends on the size of the
;;; largest number stored in the registers (e.g. if eax contains
;;; 0xFFFFFFFF, it has the largest number stored in any of the registers
;;; by default). It also depends on whether there is a large negative
;;; number in any of the registers. The maximum stack space possibly used
;;; is used by a 10-digit long negative number, as we'll see.
;;;
;;; The maximum stack space used by the program occurs when printing a
;;; 10-digit long, negative number. Therefore, there are two maximum-stack-
;;; space-used possibilities: one for the cases when at least one register contains
;;; a number between -1,000,000,000 (0xC4653600) and -2,147,483,648 (0x80000000),
;;; and the other for the cases when no registers hold numbers between these two
;;; values.
;;;
;;; The most stack space is used when printing a decimal number. This function takes
;;; 1 word and 1 dword as parameters (passed through the stack) as well as 1 dword for
;;; the return address, and pushes ebp, eax, ebx, ecx, and edx immediately. Altogether,
;;; this is 1 * 2 bytes + (2 + 5) * 4 bytes = 30 bytes used, just upon entrance into the
;;; function. Later in the function, the stack space grows once again by a word (2 bytes)
;;; when dx is pushed to save the quotient for printing purposes. This means that 32 bytes
;;; are pushed to the stack every time a recursive call is made (and in the final, non-
;;; recursive call, only 30 bytes are pushed to the stack because dx isn't pushed in this
;;; case).
;;;
;;; When printing a negative number, another 20 bytes is pushed (only once) to the
;;; stack, because printNegative takes one dword as a parameter, a dword for a return
;;; address, and pushes ebp, eax, and ebx (5 * 4 bytes = 20). This is why the most stack
;;; spaced is used when printing a 10-digit-long negative number (as 10-digits is the
;;; maximum possible number of digits).
;;;
;;; In general, the maximum number of stack space used (in bytes) as a function of N
;;; (where N = the number of digits of the maximum number) is:
;;;
;;; (32 * N) + 20 - 2 for the case when a register contains a
;;; 10-digit negative number (-2 because dx
;;; is not pushed in the final call)
;;; and
;;;
;;; (32 * N) - 2 when none of the registers contain a 10-digit
;;; negative number
;;;
;;; E.g.:
;;;
;;; FFFFFFFF (with no registers containing large negative numbers:
;;; FFFFFFFF = 10 digits (unsigned), so N = 10
;;;
;;; (32 * 10) - 2 = 318 bytes used (at the maximum)
;;;
;;;
;;; To include this file in a .asm file:
;;;
;;; %include "dumpRegs.inc"
;;;
section .data
;;; holds the names of the registers we will print (pre-formatted)
regNames db "eax = 0x", "ebx = 0x",
db "ecx = 0x", "edx = 0x",
db "edi = 0x", "esi = 0x"
;;; holds the line for the top and bottom of the box
line db "---------------------------------------------", 10
lineLen equ $-line
;;; holds a space
space db " "
spaceLen equ $-space
;;; holds a new line
newLine db 10
newLineLen equ $-newLine
;;; a string of all the hex digits
hexChars db "0123456789ABCDEF"
;;; holds the value of the current register we're printing
currentReg dd 0x00000000
;;; used to print the appropriate label
counter dw 0
char db 'x'
negSign db '-'
comma db ','
section .text
;;; dumpRegs()
;;; no parameters
;;; prints the contents of the following registers:
;;; eax, ebx, ecx, edx, esi, edi
;;; inside of a nicely formatted box.
;;; modifies:
;;; currentReg
;;; counter
;;; returns nothing
dumpRegs: mov word[counter], 0
call printLine ;prints the top of the box
mov dword[currentReg], eax ;print eax's formatted line
call printReg
add word[counter], 8 ;increment the counter for
;label by 8, because each
;label is 8 bytes long
mov dword[currentReg], ebx ;print ebx's formatted line
call printReg
add word[counter], 8
mov dword[currentReg], ecx ;print ecx's formatted line
call printReg
add word[counter], 8
mov dword[currentReg], edx ;print edx's formatted line
call printReg
add word[counter], 8
mov dword[currentReg], edi ;print edi's formatted line
call printReg
add word[counter], 8
mov dword[currentReg], esi ;print esi's formatted line
call printReg
call printLine ;print the bottom of the box
;exit dumpRegs()
ret
;;; printLine():
;;; no parameters
;;; no modifications
;;; prints a long, dashed on the screen and
;;; returns to a new line. Uses int 0x80 to print.
;;;e.g.:
;;; ----------------------------------------------
;;; returns nothing
printLine:
push ecx ;store registers
push edx
mov ecx, line ;the line to print
mov edx, lineLen ;the length of that line
call printString
;;; restore the values of eax, ebx, ecx, and edx
pop edx
pop ecx
;;; exit printLine()
ret
;;; printString(String string, int lengthOfString):
;;; parameters:
;;; ecx = string to print
;;; edx = length of the string to print
;;; modifies: ecx, edx
;;; prints the string passed in through ecx
;;; using int 0x80.
;;;
printString:
push eax ;save eax
push ebx ;save ebx
mov eax, 4 ;write
mov ebx, 1 ;stdout
int 0x80 ;print the string
pop ebx ;restore original contents of ebx
pop eax ;restore original contents of eax
;;; exit printString()
ret
;;; printSpace():
;;; no parameters
;;; no modifications
;;; prints a space by calling printString().
;;;
printSpace: push edx ;save edx
push ecx ;save ecx
mov ecx, space ;move a space
;into ecx (parameter
;for printString())
mov edx, spaceLen ;move the length
;of that space
;into edx (parameter
;for printString())
call printString
pop ecx ;restore original
;value of ecx
pop edx ;restore original
; value of edx
;exit printSpace()
ret
;;; printNewLine():
;;; no parameters
;;; no modifications
;;; prints a new line by calling printString().
;;;
printNewLine: push edx ;save edx
push ecx ;save ecx
mov ecx, newLine ;move a new line
;into ecx (parameter
;for printString())
mov edx, newLineLen ;move the length
;of that new line
;into edx (parameter
;for printString())
call printString
pop ecx ;restore original
;value of ecx
pop edx ;restore original
; value of edx
;;;exit printNewLine
ret
;;; printNegSign:
;;; no parameters
;;; no modifications
;;; prints a '-' by calling printString().
;;;
printNegSign: push edx ;save edx
push ecx ;save ecx
mov ecx, negSign
mov edx, 1
call printString
pop ecx ;restore original
;value of ecx
pop edx ;restore original
;value of edx
;;;exit printNegSign
ret
;;; printLabel():
;;; no parameters
;;; no modifications
;;; prints the first part of each line
;;; by calling printString().
;;;
;;; i.e.:
;;; | eax =
;;;
printLabel: push ecx ;save ecx
push edx ;save edx
mov ecx, regNames ;the list of register names
;(parameter for printString())
add cx, word[counter] ;the index of the name of
;the register we're on
mov edx, 8 ;the length of each label
;(parameter for printString())
call printString
pop edx ;restore original edx
pop ecx ;restore original ecx
;exit printLabel()
ret
;;; printReg(int currentReg)
;;; parameters: currentReg (contains the contents of the current
;;; register that we're printing)
;;; no modifications
;;;
;;; calls printLabel, printHexWord, printSpace, printHexByte, and
;;; printEndBar to print out the contents of the given register
;;; in blocks like:
;;;
;;; | eax = 0000 00 00 |
;;;
printReg: call printLabel ;print the register label
call printHexDWord
call printSpace
call printSpace
push word 0x00
push dword[currentReg]
call printDecimal
call printSpace
cmp dword[currentReg], 0x80000000
jae printNeg
push word 0x00
push dword[currentReg]
call printDecimal
jmp end
printNeg: push dword[currentReg]
call printNegative
end: call printNewLine
; exit printReg()
ret
;;; printHexDigit(int currentReg)
;;; parameters: currentReg (holds the value of the current
;;; register that we're printing)
;;; no modifications
;;; prints a hexdigit (=4 bits) using the int 0x80 method
;;;
printHexDigit:
;save each register, as all would be altered by the int 0x80 call
push edx
push ecx
push ebx
push eax
;move the contents of the register we're printing (stored in currentReg)
;into eax
mov eax, dword[currentReg]
rol eax, 4 ;move the next digit to
;print into al (digits
;are 4 bits long)
mov dword[currentReg], eax ;save the changes made
and eax, 0x0F ;isolate al
; move hexChars into ecx and use al as an index so that we can
; print the letter/number corresponding to the current digit
mov ecx, hexChars
add cx, ax
mov eax, 4 ;write
mov ebx, 1 ;stdout
mov edx, 1 ;print 1 character
;that is 1 byte long
int 0x80 ;print the character
;restore the registers to their original values
pop eax
pop ebx
pop ecx
pop edx
;exit printHexDigit()
ret
;;; printHexByte():
;;; parameters: currentReg (holds the value of the current
;;; register that we're printing)
;;; no modifications
;;; calls printHexDigit() twice to print out
;;; the hex value of a byte.
;;;
printHexByte: call printHexDigit
call printHexDigit
;;; exit printHexByte()
ret
;;; printHexWord():
;;; parameters: currentReg (holds the value of the current
;;; register that we're printing)
;;; no modifications
;;; calls printHexByte() twice to print out
;;; the hex value of a word (2 bytes long)
printHexWord: call printHexByte
call printHexByte
;;; exit printHexWord()
ret
;;; printHexDWord():
;;; parameters: currentReg (holds the value of the current
;;; register that we're printing)
;;; no modifications
;;; calls printHexWord() twice to print out
;;; the hex value of a dword (2 words long)
printHexDWord:
call printHexWord
call printHexWord
;;; exit printHexDWord()
ret
;;;printDecimal:
;;;parameters:
;;; dword number - the number to print out
;;; word comma counter - keeps track of when a comma
;;; needs to be printed out (after
;;; every 3 digits)
;;;
;;;no modifications
;;;no returns
;;;
;;;Prints out an integer passed through the stack as its unsigned, decimal version.
;;; e.g. "-1" will be printed out as 4294967295
printDecimal:
;;save registers
push ebp
mov ebp, esp
push eax
push ebx
push ecx
push edx
;;;figure out if there is only one digit left in our number...
mov eax, [ebp+8] ;eax <-- the quotient of the last divide,
; or the original number (if just
; entering the function)
mov edx, 0 ;will divide edx:eax by 10. edx gets 0
mov ebx, 10 ;divisor is 10
div ebx ;edx <-- remainder, eax <-- quotient
cmp eax, 0 ;is there something left?
je printOut ;if no, print out the digit
;;;figure out if comma counter needs to be reset (if we're recursing)
mov cx, word[ebp+12]
cmp cx, 3 ;compare to 3, and not 0, so that
;a comma is not printed after the
;least significant digit
je reset ;if 3, reset comma counter
inc cx ;else, comma counter+=1
jmp recurse
reset: mov cx, 1 ;comma counter <--1, because there
;are 3 digits bewteen 1 and 3 (inclusive)
;and we want to print a comma after every
;3 digits
recurse: push dx ;save the remainder (for when we exit the recursion)
push cx ;pass in comma counter
push eax ;pass in the quotient
call printDecimal
;;; ; done finding digits. ecx has the number
;;; ; of digits, and the stack has the numbers
pop dx ;dx <-- the remainder of the last call
printOut:
mov ax, dx ;ax <-- dx, so that the most sig. digit prints
;out properly
add al, '0' ;transform into Ascii
mov byte[char], al ;put it in string and print string
mov eax, 4
mov ebx, 1
mov edx, 1
mov ecx, char
int 0x80
mov cx, word[ebp+12] ;cx <--comma counter
cmp cx, 3 ;if cx==3...
je Comma ;print a comma
jmp finish ;else, return
;print a comma if cx == 3
Comma: mov eax, 4
mov ebx, 1
mov ecx, comma
mov edx, 1
int 0x80
;restore registers
finish: pop edx
pop ecx
pop ebx
pop eax
pop ebp
;1 dword * 4 bytes + 1 word * 2 bytes
ret 6
;;;printNegative:
;;;parameters:
;;; dword contents - the contents of the register
;;;no modifications
;;;returns nothing
;;;Converts a negative number from its 2's complement value to
;;;decimal value, and prints out a negative sign before
;;;calling printDecimal to print out the decimal value.
printNegative:
;save registers
push ebp
mov ebp, esp
push eax
push ebx
mov eax, dword[ebp+8] ;eax <--register contents
sub eax, 1 ;2's complement flips all bits and adds 1,
;so to convert back, subtract 1 first then...
mov ebx, 0xFFFFFFFF
xor eax, ebx ;...flip all bits by xor-ing with 0xFFFFFFFF...
call printNegSign ;print the '-'
push word 0x00 ;pass in comma counter = 0
push eax ;pass unsigned value...
call printDecimal ;print it
;restore regs
pop ebx
pop eax
pop ebp
;1 dword * 4 bytes = 4
ret 4
Problem 2
The trick here was to see that the program's recursion pattern is a tree, but the stack grows as deep as the longest path from the root of the tree to a leaf node. If we are computing fib( N ) where N is larger than 2, then the recursion will stop when we reach 2. So the longest path will be N-1. The stack with grow proportionally to O(N), or kxN, where k is a constant. Depending on how you wrote your program, k will be some multiple of words.
The major error, which everybody avoided (congrats!) would have been to say that because the tree size is O(N2), then the size of the stack is the same. Glad nobody fell for that!
