Difference between revisions of "CSC231 Homework Solutions 2017"
(7 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 17:57, 22 April 2017 (EDT) | --[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 17:57, 22 April 2017 (EDT) | ||
---- | ---- | ||
+ | <onlydft> | ||
=Problem 1= | =Problem 1= | ||
::<source lang="asm"> | ::<source lang="asm"> | ||
Line 851: | Line 852: | ||
</source> | </source> | ||
<!-- ========================================================= --> | <!-- ========================================================= --> | ||
− | < | + | <br /> |
=hw8_1.c= | =hw8_1.c= | ||
<br /> | <br /> | ||
Line 906: | Line 907: | ||
</source> | </source> | ||
+ | =hw8_2.asm= | ||
+ | <br /> | ||
+ | ::<source lang="asm"> | ||
+ | ; hw8_2.asm | ||
+ | ; D. Thiebaut | ||
+ | |||
+ | global f1 | ||
+ | global f2 | ||
+ | global f3 | ||
+ | |||
+ | ;;; ------------------------------------------------------ | ||
+ | ;;; f1( s ): modifies s in place and make it uppercase. | ||
+ | f1: push ebp | ||
+ | mov ebp, esp | ||
+ | push ebx | ||
+ | mov ebx, dword[ebp+8] | ||
+ | .for: cmp byte[ebx], 0 | ||
+ | je .done | ||
+ | cmp byte[ebx],'a' | ||
+ | jl .endfor | ||
+ | cmp byte[ebx],'z' | ||
+ | jg .endfor | ||
+ | add byte[ebx],'A'-'a' | ||
+ | .endfor: | ||
+ | inc ebx | ||
+ | jmp .for | ||
+ | .done: | ||
+ | pop ebx | ||
+ | pop ebp | ||
+ | ret 4 | ||
+ | |||
+ | ;;; ------------------------------------------------------ | ||
+ | ;;; f2( a, b, c ) | ||
+ | ;;; returns 2a + 3b -c in eax | ||
+ | ;;; computes it as 2(a+b) + b - c (fewer operations) | ||
+ | f2: push ebp | ||
+ | mov ebp, esp | ||
+ | mov eax, dword[ebp+8+4+4] ; get first param | ||
+ | add eax, dword[ebp+8+4] ; eax <- a+b | ||
+ | add eax, eax ; eax <- 2(a+b) | ||
+ | add eax, dword[ebp+8+4] ; eax <- 2(a+b) + b | ||
+ | sub eax, dword[ebp+8] ; eax <- 2a + 3b -c | ||
+ | pop ebp ; | ||
+ | ret 4*3 ; return and get rid of 3 ints | ||
+ | |||
+ | |||
+ | ;;; ------------------------------------------------------ | ||
+ | ;;; f3( array, n ) | ||
+ | ;;; computes the number of even ints in array, of length n. | ||
+ | ;;; returns this number in eax. | ||
+ | f3: push ebp | ||
+ | mov ebp, esp | ||
+ | |||
+ | ;;; push ebx | ||
+ | push ecx | ||
+ | |||
+ | mov ebx, dword[ebp+8+4] ; ebx <- array | ||
+ | mov ecx, dword[ebp+8] ; ecx <- n | ||
+ | mov eax, 0 ; number of even ints | ||
+ | .for: and dword[ebx], 1 ; and array[i] with 1 | ||
+ | jnz .notEven ; if result is 1, then odd number | ||
+ | .even: inc eax ; otherwise, add 1 to counter. | ||
+ | .notEven: | ||
+ | add ebx, 4 | ||
+ | loop .for | ||
+ | |||
+ | ;;; pop ecx | ||
+ | pop ebx | ||
+ | |||
+ | pop ebp | ||
+ | ret 2*4 | ||
+ | |||
+ | |||
+ | </source> | ||
+ | <!-- ================================================================= --> | ||
+ | |||
+ | =Homework 9: funcs.c= | ||
+ | <br /> | ||
+ | ::<source lang="c"> | ||
+ | #include <stdio.h> | ||
+ | #include <stdlib.h> | ||
+ | #include <string.h> | ||
+ | |||
+ | // getMax: returns the largest of 3 integers passed | ||
+ | // by value | ||
+ | int getMin( int a, int b, int c ) { | ||
+ | if ( a <= b && a <= c ) | ||
+ | return a; | ||
+ | if ( b <= a && b <= c ) | ||
+ | return b; | ||
+ | return c; | ||
+ | } | ||
+ | |||
+ | // zap: given a string haystack, and a string needle, | ||
+ | // looks for the firlst location of needle in the haystack, and | ||
+ | // when it finds it, replaces it with dashes. Example | ||
+ | // char s1[] = "Mississippi"; | ||
+ | // char s2[] = "ss"; | ||
+ | // char *p = s1, *q = s2; | ||
+ | // zap( s1, s2 ) will replace s1 with "Mi--issippi". | ||
+ | // zap( s1, "mm" ) will leave s1 unchanged. | ||
+ | // Returns 0 if zap couldn't fine the needle in | ||
+ | // the haystack. Returns 1 if some character replacement | ||
+ | // took place. | ||
+ | int zap( char *haystack, char *needle ) { | ||
+ | char *p = strstr( haystack, needle ); | ||
+ | char *q; | ||
+ | if ( p==NULL ) | ||
+ | return 0; | ||
+ | for ( q=p; q != p+strlen( needle ); q++ ) | ||
+ | *q = '-'; | ||
+ | return 1; | ||
+ | } | ||
+ | |||
+ | // merge(): takes two sorted arrays of ints of length 5 | ||
+ | // and merges them into an array of length 10, so that | ||
+ | // the third array is sorted, in increasing order. | ||
+ | void merge( int A[], int B[], int C[] ) { | ||
+ | int i = 0; | ||
+ | int j = 0; | ||
+ | int k = 0; | ||
+ | while ( 1 ) { | ||
+ | if ( A[i] < B[j] ) { | ||
+ | C[k++] = A[i++]; | ||
+ | //printf( "A[%d] (%d) < B[%d] (%d) ==> C[%d] (%d)\n", i-1, A[i-1], j, B[j], k-1, C[k-1] ); | ||
+ | } | ||
+ | else { | ||
+ | C[k++] = B[j++]; | ||
+ | //printf( "A[%d] (%d) > B[%d] (%d) ==> C[%d] (%d)\n", i, A[i], j-1, B[j-1], k-1, C[k-1] ); | ||
+ | } | ||
+ | if ( i>=5 || j>=5 ) | ||
+ | break; | ||
+ | } | ||
+ | while ( i<5 && k <10 ) { | ||
+ | C[k++] = A[i++]; | ||
+ | //printf( "C[%d] (%d) <-- A[%d] (%d)\n", k-1, C[k-1], i-1, A[i-1] ); | ||
+ | } | ||
+ | while ( j<5 && k <10 ) { | ||
+ | C[k++] = B[j++]; | ||
+ | //printf( "C[%d] (%d) <-- B[%d] (%d)\n", k-1, C[k-1], j-1, B[j-1] ); | ||
+ | |||
+ | } | ||
+ | } | ||
+ | </source> | ||
+ | =Homework 9: hanoi.asm= | ||
+ | <br /> | ||
+ | ::<source lang="asm"> | ||
+ | ;;; hanoi.asm | ||
+ | ;;; D. Thiebaut | ||
+ | ;;; | ||
+ | ;;; This program solves the "Towers of Hanoi" program | ||
+ | ;;; in assembly. It prompts the user for an integer | ||
+ | ;;; number of disks (must be larger than 0) and displays | ||
+ | ;;; the name of the peg from which to move a disk, and | ||
+ | ;;; the name of the peg to move it to. The pegs are | ||
+ | ;;; labeled 'A', 'B', and 'C', and the disks are always | ||
+ | ;;; assumed to moved originally from 'A' to 'B'. | ||
+ | ;;; To assemble, link, and run: | ||
+ | ;;; nasm -f elf 231Lib.o | ||
+ | ;;; nasm -f elf hanoi.asm | ||
+ | ;;; ld -melf_i386 -o hanoi hanoi.o 231Lib.o | ||
+ | ;;; ./hanoi 3 | ||
+ | ;;; | ||
+ | |||
+ | section .data | ||
+ | N dd 5 | ||
+ | |||
+ | section .text | ||
+ | extern _getInput | ||
+ | extern _println | ||
+ | extern _printString | ||
+ | extern _atoi | ||
+ | global _start | ||
+ | _start: | ||
+ | |||
+ | ;;; get N from command line | ||
+ | ;;; When any assembly language program starts, the operating system | ||
+ | ;;; passes it argc and argv through the statck. The esp register | ||
+ | ;;; points to argc. at esp+4, is a pointer to the beginning of argv[0], | ||
+ | ;;; as a string. At esp+8 is a pointer to the beginning of argv[1], | ||
+ | ;;; as a string. | ||
+ | |||
+ | mov ebp, esp | ||
+ | mov eax, dword[ebp] ; put argc into eax | ||
+ | ;;; call _printDec ; print it | ||
+ | ;;; call _println | ||
+ | |||
+ | mov eax, dword[ebp+4+4] ; make eax points to arv[1] | ||
+ | call _atoi ; convert ascii string to int | ||
+ | mov dword[N], eax ; save N | ||
+ | |||
+ | |||
+ | ;;; define the 3 pegs and pass them in bl, cl, and dl. | ||
+ | |||
+ | mov bl, 'A' | ||
+ | mov cl, 'B' | ||
+ | mov dl, 'C' | ||
+ | |||
+ | ;;; moveDisks( N, 'A', 'B', 'C' ) ; eax <- N | ||
+ | call moveDisks ; bl <- 'A' | ||
+ | ; cl <- 'B' | ||
+ | ; dl <- 'C' | ||
+ | |||
+ | |||
+ | ;;; exit | ||
+ | mov ebx, 0 | ||
+ | mov eax, 1 | ||
+ | int 0x80 | ||
+ | |||
+ | |||
+ | ;;; ------------------------------------------------------------------ | ||
+ | ;;; moveDisks( n, source, dest, extra ) | ||
+ | ;;; eax bl cl dl | ||
+ | ;;; Moves the n disks from source to dest using extra if necessary. | ||
+ | ;;; Uses recursion to move the N-1 disks above the last one. | ||
+ | ;;; Does not modify any of the registers | ||
+ | ;;; ------------------------------------------------------------------ | ||
+ | moveDisks: pushad | ||
+ | |||
+ | ;;; if n==1: | ||
+ | ;;; print( source, dest ) | ||
+ | cmp eax, 1 | ||
+ | jg recurse | ||
+ | mov al, bl ; print source | ||
+ | call printChar | ||
+ | mov al, ' ' ; print space | ||
+ | call printChar | ||
+ | mov al, cl ; print dest | ||
+ | call printChar | ||
+ | call _println ; print \n | ||
+ | |||
+ | popad ; done! return | ||
+ | ret | ||
+ | |||
+ | recurse: | ||
+ | ;;; moveDisks( n-1, source, temp, dest ) | ||
+ | dec eax ; eax <- n-1 | ||
+ | xchg cl, dl ; swap cl & dl | ||
+ | call moveDisks ; move n-1 | ||
+ | xchg cl, dl ; swap them back | ||
+ | |||
+ | |||
+ | ;;; print( source, dest ) | ||
+ | mov al, bl ; print source | ||
+ | call printChar | ||
+ | mov al, ' ' ; print space | ||
+ | call printChar | ||
+ | mov al, cl ; print dest | ||
+ | call printChar | ||
+ | call _println ; print \n | ||
+ | |||
+ | ;;; moveDisks( n-1, temp, dest, source ) | ||
+ | popad ; get all the original parameters back | ||
+ | pushad ; and push them back in the stack | ||
+ | xchg bl, dl ; exchange source and temp | ||
+ | dec eax ; eax <-- n-1 | ||
+ | call moveDisks ; recurse | ||
+ | |||
+ | popad ; pop all registers back | ||
+ | ret | ||
+ | |||
+ | ;;; ------------------------------------------------------------------ | ||
+ | ;;; printChar: prints the character in al | ||
+ | ;;; does not modify any other register | ||
+ | ;;; ------------------------------------------------------------------ | ||
+ | section .data | ||
+ | char db 'A' | ||
+ | section .text | ||
+ | printChar: pushad | ||
+ | mov byte[char],al | ||
+ | mov ecx, char | ||
+ | mov edx, 1 | ||
+ | call _printString | ||
+ | popad | ||
+ | ret | ||
+ | |||
+ | |||
+ | |||
+ | </source> | ||
</onlydft> | </onlydft> | ||
<br /> | <br /> |