CSC231 Homework 8 Solution 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

• 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

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

• • 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

--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.