Difference between revisions of "CSC231 Homework 8 Solution 2012"

From dftwiki3
Jump to: navigation, search
(→‎Library)
(→‎Problem 3: Optional and Extra Credit)
 
(18 intermediate revisions by the same user not shown)
Line 449: Line 449:
 
<br />
 
<br />
 
<source lang="asm">
 
<source lang="asm">
−
;;; File: hw8b.asm
+
;;; ; hw8b.asm
−
;;; Name: Emma Gould (edited by D. Thiebaut)
+
;;; ; Gavi Levy Haskell
−
;;; Account: 231a-ap
+
;;; ; 231a-ae
−
;;; Due: 11/7/12
+
;;; ;
−
;;; Description: This program computes and displays the first 10 rows of Pascal's triangle.
+
;;; ; Uses functions to print the first ten
−
;;; 01 00 00 00 00 00 00 00 00 00  
+
;;; ; lines of the Pascal Triangle in hex
−
;;; 01 01 00 00 00 00 00 00 00 00  
+
;;; ;
−
;;; 01 02 01 00 00 00 00 00 00 00  
+
;;; ; prints:
−
;;; 01 03 03 01 00 00 00 00 00 00  
+
;;; ;
−
;;; 01 04 06 04 01 00 00 00 00 00  
+
;;; ;  01 00 00 00 00 00 00 00 00 00
−
;;; 01 05 0A 0A 05 01 00 00 00 00  
+
;;; ; 01 01 00 00 00 00 00 00 00 00
−
;;; 01 06 0F 14 0F 06 01 00 00 00  
+
;;; ; 01 02 01 00 00 00 00 00 00 00
−
;;; 01 07 15 23 23 15 07 01 00 00  
+
;;; ; 01 03 03 01 00 00 00 00 00 00
−
;;; 01 08 1C 38 46 38 1C 08 01 00  
+
;;; ; 01 04 06 04 01 00 00 00 00 00
−
;;; 01 09 24 54 7E 7E 54 24 09 01  
+
;;; ; 01 05 0A 0A 05 01 00 00 00 00
−
;;;
+
;;; ; 01 06 0F 14 0F 06 01 00 00 00
−
;;; To assemble, link, and run: nasm -f elf -F stabs hw8b.asm ; ld -melf_i386 -o hw8b hw8b.o ; ./hw8b
+
;;; ; 01 07 15 23 23 15 07 01 00 00
 +
;;; ; 01 08 1C 38 46 38 1C 08 01 00
 +
;;; ; 01 09 24 54 7E 7E 54 24 09 01
 +
;;; ;
 +
;;; ;
 +
;;; ;    nasm -f elf -F stabs hw8b.asm
 +
;;; ;     ld -melf_i386 -o hw8b hw8b.o
 +
;;; ;    ./hw8b
 +
 +
;; -----------------
 +
;; DATA SECTION
 +
;; -----------------
 +
section .data
 +
Pascal times 10 db 0
 +
hexChr db "0123456789ABCDEF"
 +
return db 10
 +
space db " "
 +
 +
;; -----------------
 +
;; CODE SECTION
 +
;; -----------------
 +
section .text
 +
global _start
 +
_start:
 +
mov ebx, Pascal ; pass address of array in ebx
 +
call init ; store 0 in Pascal array and 1
 +
; in first cell
 +
mov ecx, 10
 +
for: mov ebx, Pascal ; pass address of array
 +
call printArray ; print Pascal array
 +
 
 +
mov ebx, Pascal
 +
call nextLine ; compute next line of triangle
 +
 
 +
loop for
 +
 
 +
;;; exit
 +
mov eax, 1
 +
mov ebx, 0
 +
int 0x80
  
 +
;;; init
 +
;;; recieves address of Pascal in ebx
 +
;;; modifies no registers
 +
init:
 +
mov dword[ebx], 0 ; change first 4 terms to zero
 +
mov dword[ebx + 4], 0 ; change next 4 terms to 0
 +
mov word[ebx + 8], 0  ; change last 2 terms to 0
 +
mov byte[ebx], 1 ; change first term of array to 1
 +
ret
  
−
;; -------------------------------
+
;;; printArray
−
;; Data Section
+
;;; recieves address of Pascal in ebx
−
;; -------------------------------
+
;;; modifies eax, ebx, edx
−
section .data
+
printArray:
−
Pascal db 0,0,0,0,0,0,0,0,0,0 ; Pascal array of 10 bytes
+
push ecx ; save outer loop position
 +
mov ecx, 10
 +
.for:
 +
push ecx ; save loop position
 +
push ebx ; save address
  
−
hexChars db "0123456789ABCDEF" ; list of hex characters
+
mov cl, byte[ebx] ; first digit
−
hexCharLen equ 1 ; length of a single character
+
ror ecx, 4       ; get correct digit
 +
and ecx, 0x0F ; keep only this digit
 +
add ecx, hexChr ; add address of hexChr
 +
mov eax, 4
 +
mov ebx, 1
 +
mov edx, 1
 +
int 0x80 ; print first digit
  
−
notation db "0x" ; hex character notation
+
pop ebx
−
notationLen equ $-notation ; length of hex character notation
+
push ebx
 +
mov cl, byte[ebx] ; second digit
 +
and ecx, 0x0F ; keep only this digit
 +
add ecx, hexChr ; add address of hexChr
 +
mov eax, 4
 +
mov ebx, 1
 +
mov edx, 1
 +
int 0x80 ; print second digit
  
−
space db "  " ; to space the characters of the array
+
mov eax, 4
−
spaceLen equ $-space ; length of space
+
mov ebx, 1
 +
mov ecx, space
 +
mov edx, 1
 +
int 0x80 ; print space
 +
 +
pop ebx
 +
pop ecx ; retrieve loop position
 +
add ebx, 1
 +
 +
loop .for ; retrieve outer loop position
  
−
newLine db 10 ; hex characters for new line
+
mov eax, 4
−
newLineLen equ $-newLine ; length of newLine
+
mov ebx, 1
 +
mov ecx, return ; return
 +
mov edx, 1
 +
int 0x80 ; next line
 +
 +
pop ecx
 +
ret
  
−
;; -------------------------------
+
;;; nextLine
−
;; Code Section
+
;;; recieves address of Pascal in ebx
−
;; -------------------------------
+
;;; modifies eax, ebx
−
section .text
+
nextLine:
−
global _start
+
push ecx ; save outer loop position
  
−
;; -------------------------------
+
mov ecx, 9
−
;; main program
+
add ebx, 9
−
;; -------------------------------
+
.for:
−
_start:
+
push ecx ; save loop position
−
mov ebx, Pascal ; pass address of array in ebx
+
mov al, byte[ebx - 1] ; n = row[x - 1]
−
call init ; store 0 in Pascal array
+
add byte[ebx], al ; row[x] += n
−
; and 1 in first cell
+
dec ebx ; x -= 1
 +
pop ecx ; retrieve loop position
 +
loop .for
 +
 
 +
pop ecx ; retrieve loop position
 +
ret
 +
</source>
 +
<br /><br />
 +
=Problem 3: Optional and Extra Credit=
 +
 
 +
==Option 1 ==
 +
* First option: write a program that constantly pushes stuff in the stack until it seg-faults.  Make it print the size of the stack as it do so.
 +
<br />
 +
<source lang="asm">
 +
;;; hwtest.asm
 +
;;; a simple demo program to test I/O with
 +
;;; a C "wrapper" program
 +
 
 +
%include "asm_io.inc"
 +
 
 +
            ;; -------------------------
 +
            ;; data segment
 +
            ;; -------------------------
 +
            section .data
 +
msg    db      "Hello! Please enter an integer number: ",0x00
 +
msg2    db      "You have entered ",0x00
 +
x      dd      0
  
−
mov ecx, 10
+
            ;; -------------------------
−
for: mov ebx, Pascal ; pass address of array in ebx
+
            ;; code area
−
call printArray ; print Pascal array
+
            ;; -------------------------
 +
            section .text
 +
            global  asm_main
 +
asm_main:     
  
−
mov ebx, Pascal ; pass address of array
+
mov ebx, esp
−
call nextLine ; compute next line of triangle
+
for: mov eax, esp
 +
sub eax, ebx
 +
neg eax
 +
call print_int
 +
call print_nl
 +
 +
sub esp, 100000 ;equivalent to pushing 100,000 bytes
 +
 +
jmp for
  
−
loop for
 
  
−
;;; exit
+
        ret
−
mov eax, 1
 
−
mov ebx, 0
 
−
int 0x80
 
  
−
;; -------------------------------
+
</source>
−
;; function init takes the address
 
−
;; in ebx and puts one in the first byte
 
−
;; at that address and zero in the other nine
 
−
;; bytes that follow
 
−
;; -------------------------------
 
−
init:
 
−
mov    byte[ebx], 1 ; move 1 into the first cell
 
−
mov edi, 1 ; edi <- index = 1
 
−
mov ecx, 9 ; ecx <- n = 9
 
−
for1: mov byte[ebx+edi], 0 ; Fib[n] <- 0
 
−
inc edi ; index <- index + 1
 
−
loop for1 ; n <- n - 1
 
−
ret
 
  
−
;; -------------------------------
+
<br />
−
;; function printArray takes the address
+
* The output of the program is:
−
;; in ebx and prints it a byte at a time
 
−
;; in hexadecimal (by passing it to printByte)
 
−
;; between the string "0x" and three spaces
 
−
;; with a new line at the very beginning and end
 
−
;; -------------------------------
 
−
printArray:
 
−
push ecx ; save ecx from main program
 
−
call printNewLine
 
  
−
mov ecx, 10 ; n = 10
+
<code><pre>
−
for3:
+
0
−
push ecx ; save n
+
100000
−
push ebx ; save address of Pascal array
+
200000
 +
300000
 +
400000
 +
500000
 +
600000
 +
...
 +
12000000
 +
12100000
 +
12200000
 +
12300000
 +
12400000
 +
12500000
 +
Segmentation fault
 +
</pre></code>
 +
* So our program could grow its stack to about 12.5 MBytes before it crashed.  At least that's the number that was printed when the segmentation fault message appeared, but we cannot be sure that the stack was not actually larger.  It is possible that there were many more messages from our program "queued" to come inside the Operating System buffer and ready to be printed when the privileged "Seg Fault" message appeared.
  
−
mov ecx, notation ; ecx <- address of "0x"
+
==Option 2==
−
mov edx, notationLen ; edx <- length of "0x"
+
* write an infinite loop program, or program that runs for a long time without using the stack necessarily, and lookup its Process Id.  Then look in the /proc directory maintained by Linux how much space is allocated to that process's stack.
−
mov eax, 4 ; print "0x"
 
−
mov ebx, 1
 
−
int 0x80
 
  
−
pop ebx ; ebx <- address of Pascal array (from stack)
+
Here's our infinite-loop program:
−
pop ecx ; ecx <- n (from stack)
+
<br />
−
mov edi, 10 ; edi <- 10
+
<br />
−
sub edi, ecx ; edi <- 10 - n
+
<source lang="asm">
−
mov    eax, 0 ; eax <- 0 (initialize)
+
; howMuchStack.asm
−
mov al, byte[ebx+edi] ; al <- Pascal[10 - n]
+
; D. Thiebaut
−
push ecx ; save n
+
; Infinite loop
−
push ebx ; save address of Pascal array
+
;
−
call printByte ; print the byte in al in hexadecimal
+
            section .text
 +
            global  _start
 +
_start:
 +
    jmp    _start
  
−
mov ecx, space ; ecx <- address of tab
 
−
mov edx, spaceLen ; edx <- length of tab
 
−
mov eax, 4 ; print " "
 
−
mov ebx, 1
 
−
int 0x80
 
  
−
pop ebx ; ebx <- return address of Pascal array (from stack)
+
</source>
−
pop ecx ; ecx <- n (returned from stack)
+
<br />
−
loop for3 ; n <- n - 1
+
<br />
 +
* Assemble, link, and then run the program
 +
* Figure out what PID the process has.  The command for that is '''ps''' typed at the prompt:
  
−
call printNewLine
+
  '''ps'''
 +
  PID TTY          TIME CMD
 +
  20543 pts/7    00:00:00 tcsh
 +
  20641 pts/7    00:00:00 nasmld
 +
  20645 pts/7    00:00:03 howMuchStack
 +
  20646 pts/7    00:00:00 ps
  
−
pop ecx ; ecx <- restore value from main program
+
* Our process Id is shown to be '''20645'''
 +
* Ask Linux what information it has about this process, using the command '''cat /proc/20645/maps''':
 +
 +
'''cat /proc/20645/maps'''
 +
08048000-08049000 r-xp 00000000 00:13 9935063                            /Users/classes/231a/handout/howMuchStack
 +
f7707000-f7708000 r-xp 00000000 00:00 0                                  [vdso]
 +
fff73000-fff94000 rwxp 00000000 00:00 0                                  [stack]
  
−
ret
+
* subtracting fff73000 from fff94000 we get  0x21000, or 135,168, or 135 KB.  That's much smaller than the 12.5 MB we found earlier, but it is possible that our program was currently using less stack space but it could have been "grown" larger by the program and more memory would have been allocated to it.
−
;; -------------------------------
 
−
;; function printNewLine takes no
 
−
;; parameters and simply prints a new line
 
−
;; -------------------------------
 
−
printNewLine:
 
−
push ebx
 
−
push ecx
 
−
mov eax, 4
 
−
mov ebx, 1
 
−
mov ecx, newLine
 
−
mov edx, newLineLen
 
−
int 0x80
 
−
pop ecx
 
−
pop ebx
 
−
ret
 
  
−
;; -------------------------------
+
* This is also the information we get by using the command '''cat /proc/20645/status''', whose output is shown below:
−
;; function printByte takes the value
 
−
;; stored in eax and print the two nybbles
 
−
;; (most significant first) in al
 
−
;; -------------------------------
 
−
printByte:
 
−
rol al, 4 ; move most significant nybble to least
 
−
push eax ; save eax in stack
 
−
and eax, 0x0000000F ; get rid of upper nybble
 
  
−
mov ecx, hexChars ; ecx <- address of hexChars
 
−
add ecx, eax ; ecx <- address of hexChars + value of nybble
 
−
mov edx, hexCharLen ; edx <- length of a single character
 
  
−
mov eax, 4 ; print the character
+
'''cat /proc/20645/status '''
−
mov ebx, 1
+
Name: howMuchStack
−
int 0x80
+
State: R (running)
 +
Tgid: 20119
 +
Pid: 20119
 +
PPid: 20060
 +
TracerPid: 0
 +
Uid: 17700 17700 17700 17700
 +
Gid: 17700 17700 17700 17700
 +
FDSize: 64
 +
Groups: 17700 17710
 +
VmPeak:     144 kB
 +
VmSize:     144 kB
 +
VmLck:       0 kB
 +
VmPin:       0 kB
 +
VmHWM:       4 kB
 +
VmRSS:       4 kB
 +
VmData:       4 kB
 +
'''VmStk:     136 kB'''  ''<---- Stack space''
 +
VmExe:       4 kB
 +
VmLib:       0 kB
 +
VmPTE:       8 kB
 +
VmSwap:       0 kB
 +
Threads: 1
 +
SigQ: 0/63717
 +
SigPnd: 0000000000000000
 +
ShdPnd: 0000000000000000
 +
SigBlk: 0000000000000000
 +
SigIgn: 0000000000000000
 +
SigCgt: 0000000000000000
 +
CapInh: 0000000000000000
 +
CapPrm: 0000000000000000
 +
CapEff: 0000000000000000
 +
CapBnd: ffffffffffffffff
 +
Cpus_allowed: f
 +
Cpus_allowed_list: 0-3
 +
Mems_allowed: 00000000,00000000,00000000,00000000,00000000,... 00000000,00000001
 +
Mems_allowed_list: 0
 +
voluntary_ctxt_switches: 3
 +
nonvoluntary_ctxt_switches: 3470
 +
 +
VmStk is the information for our stack: 136 KB.
  
−
pop eax ; eax <- full hex value (from stack)
+
==Option 3==
−
rol al, 4 ; move lower nybble back to least significant
+
* Ask the ''man'' pages.  On beowulf or grendel, type
−
and eax, 0x0000000F ; get rid of upper nybble
 
  
−
mov ecx, hexChars ; ecx <- address of hexChars
+
    man ld
−
add ecx, eax ; ecx <- address of hexChars + value of nybble
 
−
mov edx, hexCharLen ; edx <- length of a single character
 
  
−
mov eax, 4 ; print the character
+
:to get the manual page for the linker. 
−
mov ebx, 1
+
* Type
−
int 0x80
+
    /stack
  
−
ret
+
:to search for the word stack in the man page.  You are taken automatically to the first "stack" word found.  Press ''n'' (for "next") to go to an occurrence that will shed some light on what you are after:
  
−
;; -------------------------------
+
      --'''stack''' reserve
−
;; function nextLine uses the address stored in ebx
+
      --'''stack''' reserve,commit
−
;; to compute the next row of pascal's triangle
+
          Specify the number of bytes of memory to reserve (and optionally commit) to be used as '''stack''' for
−
;; and stores it in the Pascal array
+
          this program.  The default is 2Mb reserved, 4K committed.  [This option is specific to the i386 PE
−
;; -------------------------------
+
          targeted port of the linker]
−
nextLine: push ecx
 
−
mov ecx, 9 ; ecx <- m = 9 (length of array - 1)
 
−
mov edi, 9 ; edi <- n = 9 (length of array - 1)
 
  
−
for4: mov al, byte[ebx+edi] ; al <- Pascal[n] (starting at the rightmost
+
So, here we are.  About 2Mb reserved and a minimum of 4Kb.  The good news is that if you want more stack space for your program, you can reserve some more at link time.  Important if you are doing a Depth-First search on some huge graph with millions of nodes, and you want to be sure your recursive function can go deep in the traversal...
−
; number and working left)
 
−
add al, byte[ebx+edi-1] ; al <- Pascal[n-1]
 
−
mov byte[ebx+edi], al ; Fib[n] <- al
 
−
dec edi ; n = n - 1
 
−
loop for4 ; m = m - 1
 
  
−
pop ecx
+
==Option 4==
−
ret
+
* Google!
 +
* Here some of the information I was able to find about stack size:
 +
** http://stackoverflow.com/questions/1825964/c-c-maximum-stack-size-of-program
 +
<blockquote>
 +
''stacks for threads are often smaller. You can change the default at link time, or change at run time also. For reference some defaults are:''<br />
 +
o glibc i386, x86_64 7.4 MB<br />
 +
o Tru64 5.1 5.2 MB<br />
 +
o Cygwin 1.8 MB<br />
 +
o Solaris 7..10 1 MB<br />
 +
o MacOS X 10.5 460 KB<br />
 +
o AIX 5 98 KB<br />
 +
o OpenBSD 4.0 64 KB<br />
 +
o HP-UX 11 16 KB<br />
 +
</blockquote>
 +
** and from http://stackoverflow.com/questions/682444/how-can-you-find-out-the-maximum-size-of-the-memory-stack-for-a-c-program-on-l
 +
<blockquote>
 +
--Who controls the default maximum stack size; OS or compiler?
 +
<br />
 +
--The compiler typically. The OS/hardware does limit it to a certain extent. Default is 8MB on linux IIRC. Think of ulimit -s on Linux (to change stack sizes).
 +
<br />
 +
--Is the default maximum scaled according to total memory? (ie a machine with 2gb memory would have larger default size than a machine with only 512mb) For this example both machines are same os/compiler setup, just different amounts of system RAM.
 +
<br />
 +
--No. Until and unless you do it yiurself.You can alter stack sizes via compiler switches.
 +
<br />
 +
<code><pre> ld --stack=<STACK_SIZE></pre></code>
 +
<br />
 +
or
 +
<br />
 +
<code><pre> gcc -Wl,--stack=<STACK_SIZE></pre></code>
 +
<br />
 +
The C++ Standard's take on the issue of stacks and heaps:
 +
<br />
 +
The standard is based on an abstract machine and does not really concern itself with hardware or stacks or heaps. It does talk about an allocated store and a free store. The free store is where you'd be if you are calling new (mostly). FWIW, an implementation can have only one memory area masquerading as both stack and heap when it comes to object allocation.
 +
<br />
 +
Your question, therefore, boils down to be an implementation specific issue rather than a language issue.
 +
<br />
  
 +
</blockquote>
  
−
</source>
+
<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />
−
<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />
 
 
<br /><br /><br /><br /><br /><br />
 
<br /><br /><br /><br /><br /><br />
 
[[Category:CSC231]][[Category:Homework]]
 
[[Category:CSC231]][[Category:Homework]]

Latest revision as of 10:15, 14 November 2012

--D. Thiebaut 12:15, 13 November 2012 (EST)

Problem #1, Version 1

This version contains the complete code. Version 2 below separates the dumpRegs functions and main program into two files. 

;;; ---------------------------------------------------------
;;; hw8aSol.asm
;;; D. Thiebaut
;;; 11/13/12
;;; This program supports several functions that allow the user
;;; to dump the contents of the main 6 registers (eax, ebx, ecx,
;;; edx, esi and edi) to the screen.  Great for debugging without
;;; a debugger.
;;;
;;; Typical output:
;;; 	+-----------------+
;;; 	| eax = 1234 5678 |
;;; 	| ebx = 55FF 55FF |
;;; 	| ecx = FEDC BA98 |
;;; 	| edx = 0000 0000 |
;;; 	| esi = 1111 2222 |
;;; 	| edi = 2222 3333 |
;;; 	+-----------------+
;;; 	+-----------------+
;;; 	| eax = 1234 5678 |
;;; 	| ebx = 55FF 55FF |
;;; 	| ecx = FEDC BA98 |
;;; 	| edx = 0000 0000 |
;;; 	| esi = 1111 2222 |
;;; 	| edi = 2222 3333 |
;;; 	+-----------------+
;;;
;;; To assemble, link and run:
;;;   nasm -f elf hw8aSol.asm
;;;   ld -melf_i386 hw8aSol.o -o hw8aSol
;;;   ./hw8aSol
;;; ---------------------------------------------------------

		section	.data
hex		db	"0123456789ABCDEF"
regs		db	"axbxcxdxsidi"
line		db	"+-----------------+", 10
string		db	"| exx = .... .... |", 10
lineLen 	equ	$-string
reg		equ	string+3
word1		equ	string+8

		section	.text
		global	_start

_start:

;;; Initialize the registers
		mov	eax, 0x12345678
		mov	ebx, 0x55FF55FF
		mov	ecx, 0xFEDCBA98
		mov	edx, 0x00000000
		mov	esi, 0x11112222
		mov	edi, 0x22223333

;;; dump them twice to verify that no registers gets modified...
	        call    dumpRegs
		call	dumpRegs


;;; exit back to OS
		mov	ebx, 0
		mov	eax, 1
		int	0x80

;;; ---------------------------------------------------------
;;; dumpRegs: dumps the contents of the 6 main registers (eax
;;; ebx, ecx, edx, esi and edi) in a box on the screen.
;;; the screen.  Does not modify any register
;;; ---------------------------------------------------------
dumpRegs:	pushad

;;; put all the registers to print in the stack.  The loop
;;; will pop each one, one at a time, once per loop.
	
		push	edi
		push	esi
		push	edx
		push	ecx
		push	ebx
		push	eax

;;; print top bar
		call	printBar
	
;;; prepare to loop 6 times (6 registers )
		mov	ecx, 6
		mov	esi, 0

.for		pop	ebx			;get value of register to convert from stack
		push	ecx			;save loop counter
		lea	eax, [regs + esi*2]	;get address of string representing register
	
		mov	ax, word [eax] 		;ax gets "ax" or "bx" or "cx" or ... "di"
		mov	word[reg], ax		;modify string with name of register
	
		mov	edx, word1 		;edx points to buffer where to store hex digits
						;ebx contains register to convert
		call 	storeDWord		;store hex equivalent of ebx in string
	
		mov	ecx, string 		;print the whole string
		mov	edx, lineLen
		call	printInt80
		inc	esi			;index into register names incremented
		pop	ecx			;get loop counter back
		loop	.for

;;; print bottom bar
		call 	printBar
	
		popad
		ret

;;; ---------------------------------------------------------
;;; storeDWord: gets
;;; 	ebx: register to convert
;;; 	edx: address where to put information
;;; ---------------------------------------------------------
		
storeDWord:	rol	ebx, 16			;bring most sig word in least sig word
		call	storeWord
	
		inc	edx			;make edx skip space in string
	
		rol	ebx, 16			;get lower byte back in least sig pos
		call	storeWord
		
		ret

;;; ---------------------------------------------------------
;;; storeWord: gets
;;;     bx: word to convert
;;; 	edx: address where to put information. edx incremented by 4
;;; ---------------------------------------------------------
storeWord:	rol	bx, 8			;put most sig byte of bx in lower position
		call	storeByte		;and convert it.  Store it in where edx 
						;points to. 
		rol	bx, 8			;same with lower nybble
		call	storeByte
		ret
	
;;; ---------------------------------------------------------
;;; storeByte: gets
;;;     bl: byte to convert
;;; 	edx: address where to store information.  edx incremented by 2 automatically
;;; ---------------------------------------------------------
storeByte:	push	ebx
		push	eax
	
		rol	bl, 4			;get upper nybble in lower position (LSB)
		mov	al, bl			;play with al now
		and	eax, 0x0000000F		;clear all but the least significant nybble
		add	eax, hex		;get ascii in hex array equivalentn to nybble
		mov	al, [eax] 		;hex digit now in bl
		mov	byte [edx], al		;store ascii in string
		inc	edx

		rol	bl, 4			;get lower nybble back
		mov	al, bl			;play with al
		and	eax, 0x0000000F
		add	eax, hex
		mov	al, [eax]
		mov	byte [edx], al
		inc	edx
	
		pop	eax
		pop	ebx
		ret
		
;;; ---------------------------------------------------------
;;; printInt80: prints on the screen the string whose address
;;; is in ecx and length in edx.
;;; does not modify registers
;;; ---------------------------------------------------------
printInt80:	push	eax
		push	ebx
	
		mov	eax, 4
		mov	ebx, 1
		int	0x80
	
		pop	ebx
		pop	eax
		ret
	
;;; ---------------------------------------------------------
;;; printBar: prints the horizontal bar
;;; does not modify registers
;;; ---------------------------------------------------------
printBar:	push	ecx
		push	edx
	
		mov	ecx, line
		mov	edx, lineLen
		call	printInt80
	
		pop	edx
		pop	ecx
		ret


Problem #1, Version 2

Main Program


;;; ---------------------------------------------------------
;;; hw8aSol2.asm
;;; D. Thiebaut
;;; 11/13/12
;;; This program uses the library dumpRegs.asm to dump 
;;; the contents of the main 6 registers (eax, ebx, ecx,
;;; edx, esi and edi) to the screen.  Great for debugging without
;;; a debugger.
;;;
;;; Typical output:
;;; 	+-----------------+
;;; 	| eax = 1234 5678 |
;;; 	| ebx = 55FF 55FF |
;;; 	| ecx = FEDC BA98 |
;;; 	| edx = 0000 0000 |
;;; 	| esi = 1111 2222 |
;;; 	| edi = 2222 3333 |
;;; 	+-----------------+
;;; 	+-----------------+
;;; 	| eax = 1234 5678 |
;;; 	| ebx = 55FF 55FF |
;;; 	| ecx = FEDC BA98 |
;;; 	| edx = 0000 0000 |
;;; 	| esi = 1111 2222 |
;;; 	| edi = 2222 3333 |
;;; 	+-----------------+
;;;
;;; To assemble, link and run:
;;;   nasm -f elf hw8aSol.asm
;;;   ld -melf_i386 hw8aSol.o -o hw8aSol
;;;   ./hw8aSol
;;; ---------------------------------------------------------

%include "dumpRegs.asm"
	
		section	.text
		global	_start

_start:

;;; Initialize the registers
		mov	eax, 0x12345678
		mov	ebx, 0x55FF55FF
		mov	ecx, 0xFEDCBA98
		mov	edx, 0x00000000
		mov	esi, 0x11112222
		mov	edi, 0x22223333

;;; dump them twice to verify that no registers gets modified...
	        call    dumpRegs
		call	dumpRegs


;;; exit back to OS
		mov	ebx, 0
		mov	eax, 1
		int	0x80


Library


;;; ---------------------------------------------------------
;;; dumpRegs.asm
;;; D. Thiebaut
;;; 11/13/12
;;; This libary supports several functions that allow the user
;;; to dump the contents of the main 6 registers (eax, ebx, ecx,
;;; edx, esi and edi) to the screen.  Great for debugging without
;;; a debugger.
;;;
;;; Typical output:
;;; 	+-----------------+
;;; 	| eax = 1234 5678 |
;;; 	| ebx = 55FF 55FF |
;;; 	| ecx = FEDC BA98 |
;;; 	| edx = 0000 0000 |
;;; 	| esi = 1111 2222 |
;;; 	| edi = 2222 3333 |
;;; 	+-----------------+
;;; Include in program as follows:
;;; 
;;; 
;;; %include "dumpRegs.asm"
;;; ---------------------------------------------------------

		section	.data
hex		db	"0123456789ABCDEF"
regs		db	"axbxcxdxsidi"
line		db	"+-----------------+", 10
string		db	"| exx = .... .... |", 10
lineLen 	equ	$-string
reg		equ	string+3
word1		equ	string+8

		section	.text

;;; ---------------------------------------------------------
;;; dumpRegs: dumps the contents of the 6 main registers (eax
;;; ebx, ecx, edx, esi and edi) in a box on the screen.
;;; the screen.  Does not modify any register
;;; ---------------------------------------------------------
dumpRegs:	pushad

;;; put all the registers to print in the stack.  The loop
;;; will pop each one, one at a time, once per loop.
	
		push	edi
		push	esi
		push	edx
		push	ecx
		push	ebx
		push	eax

;;; print top bar
		call	printBar
	
;;; prepare to loop 6 times (6 registers )
		mov	ecx, 6
		mov	esi, 0

.for		pop	ebx			;get value of register to convert from stack
		push	ecx			;save loop counter
		lea	eax, [regs + esi*2]	;get address of string representing register
	
		mov	ax, word [eax] 		;ax gets "ax" or "bx" or "cx" or ... "di"
		mov	word[reg], ax		;modify string with name of register
	
		mov	edx, word1 		;edx points to buffer where to store hex digits
						;ebx contains register to convert
		call 	storeDWord		;store hex equivalent of ebx in string
	
		mov	ecx, string 		;print the whole string
		mov	edx, lineLen
		call	printInt80
		inc	esi			;index into register names incremented
		pop	ecx			;get loop counter back
		loop	.for

;;; print bottom bar
		call 	printBar
	
		popad
		ret

;;; ---------------------------------------------------------
;;; storeDWord: gets
;;; 	ebx: register to convert
;;; 	edx: address where to put information
;;; ---------------------------------------------------------
		
storeDWord:	rol	ebx, 16			;bring most sig word in least sig word
		call	storeWord
	
		inc	edx			;make edx skip space in string
	
		rol	ebx, 16			;get lower byte back in least sig pos
		call	storeWord
		
		ret

;;; ---------------------------------------------------------
;;; storeWord: gets
;;;     bx: word to convert
;;; 	edx: address where to put information. edx incremented by 4
;;; ---------------------------------------------------------
storeWord:	rol	bx, 8			;put most sig byte of bx in lower position
		call	storeByte		;and convert it.  Store it in where edx 
						;points to. 
		rol	bx, 8			;same with lower nybble
		call	storeByte
		ret
	
;;; ---------------------------------------------------------
;;; storeByte: gets
;;;     bl: byte to convert
;;; 	edx: address where to store information.  edx incremented by 2 automatically
;;; ---------------------------------------------------------
storeByte:	push	ebx
		push	eax
	
		rol	bl, 4			;get upper nybble in lower position (LSB)
		mov	al, bl			;play with al now
		and	eax, 0x0000000F		;clear all but the least significant nybble
		add	eax, hex		;get ascii in hex array equivalentn to nybble
		mov	al, [eax] 		;hex digit now in bl
		mov	byte [edx], al		;store ascii in string
		inc	edx

		rol	bl, 4			;get lower nybble back
		mov	al, bl			;play with al
		and	eax, 0x0000000F
		add	eax, hex
		mov	al, [eax]
		mov	byte [edx], al
		inc	edx
	
		pop	eax
		pop	ebx
		ret
		
;;; ---------------------------------------------------------
;;; printInt80: prints on the screen the string whose address
;;; is in ecx and length in edx.
;;; does not modify registers
;;; ---------------------------------------------------------
printInt80:	push	eax
		push	ebx
	
		mov	eax, 4
		mov	ebx, 1
		int	0x80
	
		pop	ebx
		pop	eax
		ret
	
;;; ---------------------------------------------------------
;;; printBar: prints the horizontal bar
;;; does not modify registers
;;; ---------------------------------------------------------
printBar:	push	ecx
		push	edx
	
		mov	ecx, line
		mov	edx, lineLen
		call	printInt80
	
		pop	edx
		pop	ecx
		ret


Problem #2


;;; ; hw8b.asm
;;; ; Gavi Levy Haskell
;;; ; 231a-ae
;;; ;
;;; ; Uses functions to print the first ten
;;; ; lines of the Pascal Triangle in hex
;;; ;
;;; ; prints:
;;; ;
;;; ;   01 00 00 00 00 00 00 00 00 00
;;; ;	01 01 00 00 00 00 00 00 00 00
;;; ;	01 02 01 00 00 00 00 00 00 00
;;; ;	01 03 03 01 00 00 00 00 00 00
;;; ;	01 04 06 04 01 00 00 00 00 00
;;; ;	01 05 0A 0A 05 01 00 00 00 00
;;; ;	01 06 0F 14 0F 06 01 00 00 00
;;; ;	01 07 15 23 23 15 07 01 00 00
;;; ;	01 08 1C 38 46 38 1C 08 01 00
;;; ;	01 09 24 54 7E 7E 54 24 09 01	
;;; ;
;;; ;
;;; ;     nasm -f elf -F stabs hw8b.asm
;;; ;     ld -melf_i386 -o hw8b hw8b.o
;;; ;     ./hw8b
	
	;; -----------------
	;; DATA SECTION
	;; -----------------
	section	.data
Pascal	times 10 db 0
hexChr	db	"0123456789ABCDEF"
return	db	10
space	db	" "
	
	;; -----------------
	;; CODE SECTION
	;; -----------------
	section	.text
	global	_start
_start:
	mov	ebx, Pascal	; pass address of array in ebx
	call	init		; store 0 in Pascal array and 1
				; in first cell
	mov	ecx, 10		
for:	mov	ebx, Pascal	; pass address of array
	call	printArray	; print Pascal array

	mov	ebx, Pascal
	call 	nextLine	; compute next line of triangle

 	loop	for

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

;;; init
;;; recieves address of Pascal in ebx
;;; modifies no registers
init:
	mov	dword[ebx], 0	; change first 4 terms to zero
	mov	dword[ebx + 4], 0 ; change next 4 terms to 0
	mov	word[ebx + 8], 0  ; change last 2 terms to 0
	mov	byte[ebx], 1	; change first term of array to 1
	ret

;;; printArray
;;; recieves address of Pascal in ebx
;;; modifies eax, ebx, edx
printArray:
	push	ecx		; save outer loop position
	mov	ecx, 10
.for:
	push	ecx		; save loop position
	push	ebx		; save address

 	mov	cl, byte[ebx] 	; first digit
	ror	ecx, 4	      	; get correct digit
 	and	ecx, 0x0F	; keep only this digit
 	add	ecx, hexChr	; add address of hexChr
 	mov	eax, 4
 	mov	ebx, 1
 	mov	edx, 1
 	int	0x80		; print first digit

	pop	ebx
	push	ebx
 	mov	cl, byte[ebx] 	; second digit
 	and	ecx, 0x0F	; keep only this digit
 	add	ecx, hexChr	; add address of hexChr
 	mov	eax, 4
 	mov	ebx, 1
 	mov	edx, 1
 	int	0x80		; print second digit

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, space
	mov	edx, 1
	int	0x80		; print space
	
	pop	ebx
	pop	ecx		; retrieve loop position
	add	ebx, 1
	
	loop	.for		; retrieve outer loop position

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, return	; return
	mov	edx, 1
	int	0x80		; next line
	
	pop	ecx
	ret

;;; nextLine
;;; recieves address of Pascal in ebx
;;; modifies eax, ebx
nextLine:
	push	ecx		; save outer loop position

	mov	ecx, 9
	add	ebx, 9
.for:
	push	ecx		; save loop position
	mov	al, byte[ebx - 1] ; n = row[x - 1]
	add	byte[ebx], al	; row[x] += n
	dec	ebx		; x -= 1
	pop	ecx		; retrieve loop position
	loop	.for

	pop	ecx		; retrieve loop position
	ret



Problem 3: Optional and Extra Credit

Option 1

  • First option: write a program that constantly pushes stuff in the stack until it seg-faults. Make it print the size of the stack as it do so.


;;; hwtest.asm
;;; a simple demo program to test I/O with
;;; a C "wrapper" program

%include "asm_io.inc"

             ;; -------------------------
             ;; data segment
             ;; -------------------------
             section .data
msg     db      "Hello! Please enter an integer number: ",0x00
msg2    db      "You have entered ",0x00
x       dd      0

             ;; -------------------------
             ;; code area
             ;; -------------------------
             section .text
             global  asm_main
asm_main:       

	mov	ebx, esp
for:	mov	eax, esp
	sub	eax, ebx
	neg	eax
	call	print_int
	call	print_nl
	
	sub	esp, 100000	;equivalent to pushing 100,000 bytes
	
	jmp	for


        ret


  • The output of the program is:
0
100000
200000
300000
400000
500000
600000
...
12000000
12100000
12200000
12300000
12400000
12500000
Segmentation fault
  • So our program could grow its stack to about 12.5 MBytes before it crashed. At least that's the number that was printed when the segmentation fault message appeared, but we cannot be sure that the stack was not actually larger. It is possible that there were many more messages from our program "queued" to come inside the Operating System buffer and ready to be printed when the privileged "Seg Fault" message appeared.

Option 2

  • write an infinite loop program, or program that runs for a long time without using the stack necessarily, and lookup its Process Id. Then look in the /proc directory maintained by Linux how much space is allocated to that process's stack.

Here's our infinite-loop program: 

; howMuchStack.asm
; D. Thiebaut
; Infinite loop
;
             section .text
             global  _start
_start:	
	     jmp     _start



  • Assemble, link, and then run the program
  • Figure out what PID the process has. The command for that is ps typed at the prompt:
 ps 
 PID TTY          TIME CMD
 20543 pts/7    00:00:00 tcsh
 20641 pts/7    00:00:00 nasmld
 20645 pts/7    00:00:03 howMuchStack
 20646 pts/7    00:00:00 ps
  • Our process Id is shown to be 20645
  • Ask Linux what information it has about this process, using the command cat /proc/20645/maps:
cat /proc/20645/maps
08048000-08049000 r-xp 00000000 00:13 9935063                            /Users/classes/231a/handout/howMuchStack
f7707000-f7708000 r-xp 00000000 00:00 0                                  [vdso]
fff73000-fff94000 rwxp 00000000 00:00 0                                  [stack]
  • subtracting fff73000 from fff94000 we get 0x21000, or 135,168, or 135 KB. That's much smaller than the 12.5 MB we found earlier, but it is possible that our program was currently using less stack space but it could have been "grown" larger by the program and more memory would have been allocated to it.
  • This is also the information we get by using the command cat /proc/20645/status, whose output is shown below:


cat /proc/20645/status 
Name:	howMuchStack
State:	R (running)
Tgid:	20119
Pid:	20119
PPid:	20060
TracerPid:	0
Uid:	17700	17700	17700	17700
Gid:	17700	17700	17700	17700
FDSize:	64
Groups:	17700 17710 
VmPeak:	     144 kB
VmSize:	     144 kB
VmLck:	       0 kB
VmPin:	       0 kB
VmHWM:	       4 kB
VmRSS:	       4 kB
VmData:	       4 kB
VmStk:	     136 kB   <---- Stack space
VmExe:	       4 kB
VmLib:	       0 kB
VmPTE:	       8 kB
VmSwap:	       0 kB
Threads:	1
SigQ:	0/63717
SigPnd:	0000000000000000
ShdPnd:	0000000000000000
SigBlk:	0000000000000000
SigIgn:	0000000000000000
SigCgt:	0000000000000000
CapInh:	0000000000000000
CapPrm:	0000000000000000
CapEff:	0000000000000000
CapBnd:	ffffffffffffffff
Cpus_allowed:	f
Cpus_allowed_list:	0-3
Mems_allowed:	00000000,00000000,00000000,00000000,00000000,... 00000000,00000001
Mems_allowed_list:	0
voluntary_ctxt_switches:	3
nonvoluntary_ctxt_switches:	3470

VmStk is the information for our stack: 136 KB.

Option 3

  • Ask the man pages. On beowulf or grendel, type
   man ld
to get the manual page for the linker.
  • Type 
    /stack
to search for the word stack in the man page. You are taken automatically to the first "stack" word found. Press n (for "next") to go to an occurrence that will shed some light on what you are after:
      --stack reserve
      --stack reserve,commit
          Specify the number of bytes of memory to reserve (and optionally commit) to be used as stack for
          this program.  The default is 2Mb reserved, 4K committed.  [This option is specific to the i386 PE
          targeted port of the linker]

So, here we are. About 2Mb reserved and a minimum of 4Kb. The good news is that if you want more stack space for your program, you can reserve some more at link time. Important if you are doing a Depth-First search on some huge graph with millions of nodes, and you want to be sure your recursive function can go deep in the traversal...

Option 4

stacks for threads are often smaller. You can change the default at link time, or change at run time also. For reference some defaults are:
o glibc i386, x86_64 7.4 MB
o Tru64 5.1 5.2 MB
o Cygwin 1.8 MB
o Solaris 7..10 1 MB
o MacOS X 10.5 460 KB
o AIX 5 98 KB
o OpenBSD 4.0 64 KB
o HP-UX 11 16 KB

--Who controls the default maximum stack size; OS or compiler?
--The compiler typically. The OS/hardware does limit it to a certain extent. Default is 8MB on linux IIRC. Think of ulimit -s on Linux (to change stack sizes).
--Is the default maximum scaled according to total memory? (ie a machine with 2gb memory would have larger default size than a machine with only 512mb) For this example both machines are same os/compiler setup, just different amounts of system RAM.
--No. Until and unless you do it yiurself.You can alter stack sizes via compiler switches. 

 ld --stack=<STACK_SIZE>


or 

 gcc -Wl,--stack=<STACK_SIZE>


The C++ Standard's take on the issue of stacks and heaps:
The standard is based on an abstract machine and does not really concern itself with hardware or stacks or heaps. It does talk about an allocated store and a free store. The free store is where you'd be if you are calling new (mostly). FWIW, an implementation can have only one memory area masquerading as both stack and heap when it comes to object allocation.
Your question, therefore, boils down to be an implementation specific issue rather than a language issue.



















Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC231_Homework_8_Solution_2012&oldid=15853"