CSC231 Homework 6 Fall 2017

--D. Thiebaut (talk) 12:59, 5 November 2017 (EST)

---

This homework is due on 11/13/17 at 11:55 p.m.

Problem #1

• Assume that you have an assembly program that uses a loop to compute Fibonacci numbers.
• The Fibonacci terms get stored in an array called Fib as they are computed. The array is an array of dwords.
• In the loop, the program computes

           Fib[ i ] = Fib[ i-1 ] + Fib[ i-2 ];

• The program uses some form of addressing mode to store each Fib[i] term in the array.
• If we are not worried about possible overflow of the arithmetic, i.e. we are not worried that the computation might become invalid at some point, and if we assume that the array can be as large as we want (we have a large amount of RAM in our computer), what is a good approximation to the maximum number of Fibonacci terms an assembly program can compute in 1 second, if our computer has a 2.5 GHz Pentium processor? In other words, try to write the loop that computes the Fibonacci terms with as few instructions as possible; that will give you the maximum number of terms that can be computed per second.
• Answer the multiple-choice question on Moodle.

Note: You do not have to submit code for this section, but you should probably write the assembly code that computes the Fibonacci terms, just to see how tight you can make the loop, and find the maximum number of terms that can be computed...

Problem #2

When you were a kid, you may have exchanged secret messages with friends. An easy way to generated coded messages is to assign a different letter to each letter of the alphabet. For example:

a b c d e f g h i j k l m n o p q r s t u v w x y z
| | | | | | | | | | | | | | | | | | | | | | | | | | 
b c d a f g h e m n i j k l p o r q t s x y z u v w

If you wanted to send a secret message containing the word "hello" to a friend, you would need to encode it first. For this, you would look up each letter of the word in the first line above (normal alphabet), find the letter directly underneath (in the scrambled alphabet), and make up a new word with the letters from the second line. 'h' would become 'e', 'e' would become 'f', 'l' would become 'j', and 'o' would become 'p'. So 'hello' would be 'encoded' as 'efjjp'. Your friend then would decode 'efjjp' back into 'hello' by using a similar process, explained below.

To decode the message, your friend could use the same method you used, but with a different second scrambled alphabet:

a b c d e f g h i j k l m n o p q r s t u v w x y z
| | | | | | | | | | | | | | | | | | | | | | | | | | 
d a b c h e f g k l m n i j p o r q t s x y z u v w

To decode 'efjjp', your friend would look up 'e' in the first alphabet above, and find 'h' just below. 'h' would be the first letter of the encoded message. 'f' is above 'e', so 'e' is the second letter. 'j' is above 'l', so the next letters are 'll'. And finally 'p' is above 'o', so the final letter of the encoded message had to be 'o': "hello."

For this assignment, you are given the executable version of an encoder, which uses the process illustrated above. Your assignment is to write the decoder that will take words in lowercase and will decode them to their original version.

You can get a copy of the executable version of the encoder as follows:

getcopy hw6code

Call your program hw6decode.asm and submit it to Moodle when done.

Examples

The following examples illustrate how your program must work when working

Additional Information

Coding Hints

• To transform a character into another character, you can use a simple trick.
• First declare an array, say table, containing a scrambled version of the alphabet:

      	 0   1	 2   3	 4   5	 6   7	 8   9	10  11	12  13	14  15     25
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---...+---+
Table  | b | c | d | a | f | g | h | e | m | n | i | j | k | l | p | o ..   w |
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---...+---+

• Then when you get a character to encode, say 'h', subtract 'a' from it. This gives you the number 7.
• Then go in the array Table, at index 7, and grab the letter there: 'e'. 'e' is the encoded version of 'h'.
• By removing 'a' from the character to encode, you actually use the array Table as if its Index 0 was actually 'a', Index 1, the letter 'b', Index 2, the letter 'c', etc.

Restrictions

• The input strings your decode program will be subjected to will never be longer than 256 characters.
• The input strings your decode program will be subjected to will only contain lowercase characters.

Submission

Submit your program on Moodle in the Homework 6 Problem 2 section. Make sure you document your code well.

Problem 3

Assume that we have an application that uses signed integers of 11 bits. The integers are coded using 2's complement. The following questions should be answered on Moodle, in the Homework 6 Problem 3 section.

Question 1

What is the smallest (most negative) number that can be represented with this format? Use a decimal number when entering your answer in Moodle.

Question 2

What is the largest (most positive) number that can be represented with this format? Use a decimal number when entering your answer in Moodle.

Question 3

What is the decimal equivalent of 0x7FF in this format? Use a decimal number when entering your answer in Moodle.

Question 4

What is the decimal equivalent of 0x400 in this format? Use a decimal number when entering your answer in Moodle.

Question 5

What is the decimal equivalent of 0x3FF in this format? Use a decimal number when entering your answer in Moodle.

Question 6

Assume that we code +255 (decimal) and +256 (decimal) in this 11-bit, 2's complement integer format. Will the sum of these two numbers be stored correctly in 11 bits or will the result overflow the 11 bits?

Solution Assembly Program

Fast Fibs

;;; Solution for Homework 6 Problem 1
;;; D. Thiebaut

	section	.data
Fib	times 	100 dd	0

	section	.text
	global	_start
	extern	_printInt, _println
_start:
;;; initialize first 2 fibs
	
	mov	dword[Fib], 1	;Fib[0] <- 1
	mov	dword[Fib+4], 1	;Fib[1] <- 1

;;; setup the loop
	mov	ebx, Fib+8	;ebx points to Fib[2]
	mov	eax, 1		;eax contains Fib[1]

;;; loop away!  Once the loop goes a few times, eax
;;; will contain Fib[n-1] and ebx will point to Fib[n-2]
	mov	ecx, 10
for:	add	eax, dword[ebx-8]	;add to eax Fib[n-2]
	mov	dword[ebx], eax		;Fib[n] <- Fib[n-1]+Fib[n-2]

	call	_printInt		;if you remove these two statements
	call	_println		;you get a loop of 4 instructions!
	
	add	ebx, 4			;n <- n+1
	loop	for

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

Encode/Decode

;;;  hw6decode.asm
;;; D. Thiebaut
;;; This file decodes words (no spaces, only lowercase) that are given
;;; after the prompt.  Only one word at a time.
;;; The words have been encoded with a dictionary declared as
;;;
;;;  dict db  'asemblyfordcghijknpqtuvwxz'
;;;
;;; Example:
;;;   nasm -f elf hw6decode.asm
;;;   ld -melf_i386 -o hw6decode hw6decode.o 231Lib.o
;;;    cs231a@aurora ~/HWs/HW6/PB2 $ ./hw6code
;;; 	> hello
;;; 	fbcci
;;; 	cs231a@aurora ~/HWs/HW6/PB2 $ ./hw6decode
;;; 	> fbcci
;;; 	hello
;;; 

	section	.data
;;;              asemblyfordcghijknpqtuvwxz
;;;              abcdefghijklmnopqrstuvwxyz
dict	db	'aelkchmnopqfdristjbuvwxygz' ; the dictionary used for decoding
prompt	db	'> '
input	dd	0		;save address of string input by user
noChars dd	0		;number of chars typed by user
temp	dd	0		;to save ecx when needed (we don't now
				; push yet)
	
	section	.txt
	global	_start
	extern	_printString
	extern	_getString
	extern	_println

_start:
;;; get a string from the user.  Print
;;; prompt first, then save the address
;;; of first byte of string in input, and
;;; number of chars in input in noChars
	
	mov	ecx, prompt
	mov	edx, 2
	call	_printString
	call	_getString
	mov	dword[noChars], edx
	mov	dword[input], ecx
	
;;; get ready to loop over all the chars in string
;;; entered by user.
;;; for each char found, subtract 'a' from it
;;; and make it an index in dict.  Fetch the char
;;; at that index and print it.
	mov	ecx, dword[noChars]
	mov	ebx, dword[input]
	
for:	mov	eax, 0		; eax will be address of char in dict
	mov	al, byte[ebx]	; make eax 32-bit version of char
	sub	al, 'a'		; subtract 'a' to get index in dict
	add	eax, dict	; make eax addess of char in dict
	mov	al, byte[eax]	; get char in dict
	mov	byte[ebx],al	; replace original char
	inc	ebx
	loop 	for

;;; print the decoded string on the screen
	mov	ecx, dword[input]
	mov	edx, dword[noChars]
	call	_printString
	call	_println

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