Tutorial: Moodle VPL -- Testing with Time-Out
--D. Thiebaut (talk) 11:33, 19 May 2017 (EDT)
This VPL activity tests an assembly program that implements a recursive function (binSearch), and stops its execution if it spends too long in the recursion. Note: the solution program is not required for testing the binSearch function. Instead the bash scripts create a list of correct expected returned values for various calls to the function, and compare the expected values to the actually returned values.
vpl_run.sh
#! /bin/bash cat > vpl_execution << 'EOF' #! /bin/bash nasm -f elf main0.asm nasm -f elf 231Lib.asm nasm -f elf binSearch.asm ld -melf_i386 -o main0 main0.o 231Lib.o binSearch.o echo "" echo "Your output:" ./main0 echo "" echo "Your output should be: " echo "28" echo "-1" echo "2" echo "-1" EOF chmod +x vpl_execution
vpl_evaluate.sh
#! /bin/bash cat > vpl_execution << 'EOF' #! /bin/bash nasm -f elf main.asm nasm -f elf 231Lib.asm nasm -f elf binSearch.asm ld -melf_i386 -o main main.o 231Lib.o binSearch.o cat > solution.txt << 'EEOOFF' 31 -1 0 -1 EEOOFF timeout 2 ./main > user.txt exit_status=$? if [[ $exit_status -eq 124 ]]; then echo "Your program took more than 2 seconds to execute." echo "There is a major problem with the way you manage recursion." echo "Grade :==>> C" exit fi ./main > user.txt n=`diff --ignore-all-space -U 0 user.txt solution.txt | grep -v ++ | grep ^+ | wc -l` #echo "n = $n" if [ "$n" -eq "0" ]; then echo "Perfect match: your grade = A" echo "Grade :=>> 100" fi if [ "$n" -eq "1" ]; then echo "1 register is incorrect: your grade = B+" echo "Grade :=>> 89" fi if [ "$n" -eq "2" ]; then echo "2 registers are incorrect: your grade = B-" echo "Grade :=>> 82" fi if [ "$n" -eq "3" ]; then echo "3 registers are incorrect: your grade = C" echo "Grade :=>> 79" fi if [ "$n" -eq "4" ]; then echo "All 4 registers are incorrect: your grade = D" echo "Grade :=>> 66" fi EOF chmod +x vpl_execution
main0.asm
;;; test program for binSearch() ;;; D. Thiebaut section .data table1 dd 1,3,5,10,11,20,21,22,23,34 dd 40,41,42,43,45,48,50,51,100 dd 102,103,200,255,256,1000,1001 dd 1020,2000,3000,4000,4001,5000 TABLE1LEN equ ($-table1)/4 table2 dd 10,20,30,40,41,50,60,80,90,100 TABLE2LEN equ ($-table2)/4 section .text extern _printInt extern _println extern binSearch ;;; ------------------------------------------------------------- ;;; MAIN PROGRAM ;;; calls binSearch on two different arrays, each time for 2 ;;; different keys. The values printed should be: ;;; ;;; 28 ;;; -1 ;;; 2 ;;; -1 ;;; ;;; ------------------------------------------------------------- global _start _start: ;; binSearch( table1, 5000, 0, TABLELEN1-1 ) ;; returned value should be -8 mov eax, table1 push eax mov eax, 3000 ; search for 3000 in table1 push eax mov eax, 0 push eax mov eax, TABLE1LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table1, 2, 0, TABLELEN1-1 ) ;; returned value should be -1 mov eax, table1 push eax mov eax, 2 ; search for 2 in table1. push eax ; mov eax, 0 push eax mov eax, TABLE1LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table2, 10, 0, TABLELEN2-1 ) ;; returned value should be 2 mov eax, table2 push eax mov eax, 30 ; search for 10 in table2 push eax mov eax, 0 push eax mov eax, TABLE2LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table2, 2, 0, TABLELEN2-1 ) ;; returned value should be 2 mov eax, table2 push eax mov eax, 2 ; search for 2 in table2 push eax mov eax, 0 push eax mov eax, TABLE2LEN-1 push eax call binSearch call _printInt call _println ;;; exit mov ebx, 0 mov eax, 1 int 0x80
main.asm
;;; test program for binSearch() ;;; D. Thiebaut section .data table1 dd 1,3,5,10,11,20,21,22,23,34 dd 40,41,42,43,45,48,50,51,100 dd 102,103,200,255,256,1000,1001 dd 1020,2000,3000,4000,4001,5000 TABLE1LEN equ ($-table1)/4 table2 dd 10,20,30,40,41,50,60,80,90,100 TABLE2LEN equ ($-table2)/4 section .text extern _printInt extern _println extern binSearch ;;; ------------------------------------------------------------- ;;; MAIN PROGRAM ;;; calls binSearch on two different arrays, each time for 2 ;;; different keys. The values printed should be: ;;; ;;; 28 ;;; -1 ;;; 2 ;;; -1 ;;; ;;; ------------------------------------------------------------- global _start _start: ;; binSearch( table1, 5000, 0, TABLELEN1-1 ) ;; returned value should be -8 mov eax, table1 push eax mov eax, 5000 ; search for 3000 in table1 push eax mov eax, 0 push eax mov eax, TABLE1LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table1, 2, 0, TABLELEN1-1 ) ;; returned value should be -1 mov eax, table1 push eax mov eax, 2 ; search for 2 in table1. push eax ; mov eax, 0 push eax mov eax, TABLE1LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table2, 10, 0, TABLELEN2-1 ) ;; returned value should be 2 mov eax, table2 push eax mov eax, 10 ; search for 10 in table2 push eax mov eax, 0 push eax mov eax, TABLE2LEN-1 push eax call binSearch call _printInt call _println ;; binSearch( table2, 2, 0, TABLELEN2-1 ) ;; returned value should be 2 mov eax, table2 push eax mov eax, 2 ; search for 2 in table2 push eax mov eax, 0 push eax mov eax, TABLE2LEN-1 push eax call binSearch call _printInt call _println ;;; exit mov ebx, 0 mov eax, 1 int 0x80
231Lib.asm
;;; 231Lib.asm ;;; A simple I/O library for CSC231. ;;; will be expanded as needed. ;;; ;;; D. Thiebaut ;;; Adapted from Swarnali Ahmed's 2002 program: mytools.inc ;;; http://cs.smith.edu/dftwiki ;;; ;;; Contains several functions for performing simple I/O of ;;; data. ;;; _printDec: function that prints an integer on the screen ;;; _printString: function that prints a string on the screen ;;; _println: moves the cursor to the next line on the screen ;;; _getInput: gets a possibly signed integer from the keyboard ;;; ;;; Version 2. Sept 22, 2014. ;;; - updated _getInput to get only 1 char at at time. ;;; - now works with pipes ;;; Version 1. Sept 21, 2014. ;;; %assign SYS_EXIT 1 %assign SYS_WRITE 4 %assign STDOUT 1 global _atoi global _printDec global _printInt global _printString global _printCString global _println global _getInput global _printRegs global _printHex section .text ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ ;;; ; _atoi: gets a numerical input in a 0-terminated string ;;; ; pointed to by eax. ;;; ; returns the resulting number in eax (32 bits). ;;; ; recognizes - as the first character of ;;; ; negative numbers. Does not skip whitespace ;;; ; at the beginning. Stops on first not decimal ;;; ; character encountered. ;;; ; ;;; ; NO REGISTERS MODIFIED, except eax ;;; ; ;;; ; Example of call: ;;; ; ;;; ; call getInput ;;; ; mov dword[x], eax ; put integer in x ;;; ; ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ _atoi: section .bss intg2 resd 1 isneg2 resb 1 section .text pushad ; save all registers mov esi, eax ; eci --> buffer mov ecx, 0 ; edi = counter of chars .count: cmp byte[esi], 0 ; '\0'? je .parse inc esi inc ecx jmp .count .parse: mov esi, eax ; esi --> buffer mov ecx, edi ; loop for all chars received mov dword[intg2], 0 mov byte[isneg2], 0 .negativ: cmp byte[esi], '-' jne .loop inc byte[isneg2] .loop: mov ebx, 0 mov bl, byte[esi] ;; stop on line feed cmp bl, 0 ; '\0'? je .done ;; stop on non-digit characters cmp bl, '0' jb .done cmp bl, '9' ja .done ;; bl is a digit... multiply .int by 10 first mov edx, 10 mov eax, dword[intg2] mul edx ; edx:eax <-- 10 * .int ;; add int version of char sub bl, '0' add eax, ebx mov dword[intg2], eax inc esi loop .loop .done: ;; if negative, make eax neg cmp byte[isneg2], 0 je .return neg eax mov dword [intg2], eax ;; restore registers and return result in eax .return: popad mov eax, [intg2] ret ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ ;;; ; getInput: gets a numerical input from the keyboard. ;;; ; returns the resulting number in eax (32 bits). ;;; ; recognizes - as the first character of ;;; ; negative numbers. Does not skip whitespace ;;; ; at the beginning. Stops on first not decimal ;;; ; character encountered. ;;; ; ;;; ; NO REGISTERS MODIFIED, except eax ;;; ; ;;; ; Example of call: ;;; ; ;;; ; call getInput ;;; ; mov dword[x], eax ; put integer in x ;;; ; ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ _getInput: section .bss buffer resb 120 intg resd 1 isneg resb 1 section .text pushad ; save all registers mov esi, buffer ; eci --> buffer mov edi, 0 ; edi = counter of chars .loop1: mov eax, 03 ; input mov ebx, 0 ; stdin mov ecx, esi ; where to put the next char mov edx, 1 ; one char at a time int 0x80 ; get the input into buffer cmp byte[esi], 0 ; EOF? je .parse cmp byte[esi], 10 ; line feed? je .parse inc esi ; point to next cell inc edi ; increment char counter jmp .loop1 .parse: mov esi, buffer ; esi --> buffer mov ecx, edi ; loop for all chars received mov dword[intg], 0 mov byte[isneg], 0 .negativ: cmp byte[esi], '-' jne .loop inc byte[isneg] .loop: mov ebx, 0 mov bl, byte[esi] ;; stop on line feed cmp bl, 10 ; line feed? je .done ;; stop on non-digit characters cmp bl, '0' jb .done cmp bl, '9' ja .done ;; bl is a digit... multiply .int by 10 first mov edx, 10 mov eax, dword[intg] mul edx ; edx:eax <-- 10 * .int ;; add int version of char sub bl, '0' add eax, ebx mov dword[intg], eax inc esi loop .loop .done: ;; if negative, make eax neg cmp byte[isneg], 0 je .return neg eax mov dword [intg], eax ;; restore registers and return result in eax .return: popad mov eax, [intg] ret ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ ;;; ; _printDec: takes the double word in eax and prints it ;;; ; to STDOUT in decimal. ;;; ; ;;; ; Examples: ;;; ; print a byte variable ;;; ; mov eax, 0 ;;; ; mov al, byte[someVar] ;;; ; call _printDec ;;; ; ;;; ; print a word variable ;;; ; mov eax ;;; ; mov ax, word[otherVar] ;;; ; call _printDec ;;; ; ;;; ; print a double-word variable ;;; ; mov eax, dword[thirdVar] ;;; ; call _printDec ;;; ; ;;; ; print register edx in decimal ;;; ; ;;; ; mov eax, edx ;;; ; call _printDec ;;; ; ;;; ;REGISTERS MODIFIED: NONE ;;; ;------------------------------------------------------ ;;; ;------------------------------------------------------ _printDec: ;;; saves all the registers so that they are not changed by the function section .bss .decstr resb 10 .ct1 resd 1 ; to keep track of the size of the string section .text pushad ; save all registers mov dword[.ct1],0 ; assume initially 0 mov edi,.decstr ; edi points to decstring add edi,9 ; moved to the last element of string xor edx,edx ; clear edx for 64-bit division .whileNotZero: mov ebx,10 ; get ready to divide by 10 div ebx ; divide by 10 add edx,'0' ; converts to ascii char mov byte[edi],dl ; put it in sring dec edi ; mov to next char in string inc dword[.ct1] ; increment char counter xor edx,edx ; clear edx cmp eax,0 ; is remainder of division 0? jne .whileNotZero ; no, keep on looping inc edi ; conversion, finish, bring edi mov ecx, edi ; back to beg of string. make ecx mov edx, [.ct1] ; point to it, and edx gets # chars mov eax, SYS_WRITE ; and print! mov ebx, STDOUT int 0x80 popad ; restore all registers ret ;;; ; ------------------------------------------------------------ ;;; ; _printString: prints a string whose address is in ;;; ; ecx, and whose total number of chars ;;; ; is in edx. ;;; ; Examples: ;;; ; Assume a string labeled msg, containing "Hello World!", ;;; ; and a constant MSGLEN equal to 12. To print this string: ;;; ; ;;; ; mov ecx, msg ;;; ; mov edx, MSGLEN ;;; ; call _printSTring ;;; ; ;;; ; REGISTERS MODIFIED: NONE ;;; ; ------------------------------------------------------------ ;;; ;save eax and ebx so that it is not modified by the function _printString: push eax push ebx mov eax,SYS_WRITE mov ebx,STDOUT int 0x80 pop ebx pop eax ret ;;; ; ------------------------------------------------------------ ;;; ; _printCString: prints a string whose address is in ;;; ; ecx, and which is 0-terminated, like ;;; ; C strings. ;;; ; Examples: ;;; ; Assume a string labeled msg, containing "Hello World!", ;;; ; and a constant MSGLEN equal to 12. To print this string: ;;; ; ;;; ; mov ecx, msg ;there's a \0 somewher in msg ;;; ; call _printCString ;;; ; ;;; ; REGISTERS MODIFIED: NONE ;;; ; ------------------------------------------------------------ ;;; ;save eax and ebx so that it is not modified by the function _printCString: push ebx push edx ; save regs mov ebx, ecx ; make ebx point to string mov edx, 0 ; count in edx .for: cmp byte[ebx], 0 ; '\0' found yet? je .done inc ebx ; no, point to next char inc edx ; add 1 to counter jmp .for .done: call _printString pop edx pop ebx ret ;;; ; ------------------------------------------------------------ ;;; ; _println put the cursor on the next line. ;;; ; ;;; ; Example: ;;; ; call _println ;;; ; ;;; ; REGISTERS MODIFIED: NONE ;;; ; ------------------------------------------------------------ _println: section .data .nl db 10 section .text push ecx push edx mov ecx, .nl mov edx, 1 call _printString pop edx pop ecx ret ;;; ; ------------------------------------------------------------ ;;; ; _printHex: prints contents of eax in hexadecimal, uppercase. ;;; ; using 8 chars. ;;; ; ------------------------------------------------------------ section .data table db "0123456789ABCDEF" hexString db "xxxxxxxx" tempEax dd 0 section .text _printHex: pushad ; save all registers mov [tempEax], eax ; save eax, as we are going to need it ; several times, for all its digits mov ecx, 8 ; get ready to loop 8 times ;; get char equivalent to lower nybble of eax for: and eax, 0xF ; isolate lower nybble of eax add eax, table ; and translate it into ascii hex char mov bl, byte[eax] ; bl <- ascii ;; make eax point to place where to put this digit in hexString mov eax, hexString ; beginning of table add eax, ecx ; add ecx to it, since ecx counts dec eax ; but eax 1 too big, decrement it mov byte[eax], bl ; store ascii char at right index in hexString ;; shift eax down by 4 bits by dividing it by 16 mov ebx, 16 ; ready to shift down by 4 bits mov eax, [tempEax] ; get eax back div ebx ; shift down by 4 mov [tempEax], eax ; save again loop for ; and repeat, 8 times! ;; print the pattern in hexString, which contains 8 chars mov ecx, hexString ; mov edx, 8 call _printString popad ret ;;; ; ------------------------------------------------------------ ;;; ; _printInt: prints the contents of eax as a 2's complement ;;; ; number. ;;; ; ------------------------------------------------------------ _printInt: push eax ; save the regs we are using push ecx push edx ;; check if msb is set test eax, 0x80000000 jz positive neg eax push eax ;; the number is negative. Print a minus sign and ;; the positive equivalent of the number mov ecx, minus mov edx, 1 call _printString pop eax ;; the number is positive, just print it. positive: call _printDec pop edx pop ecx pop eax ret ;;; ; ------------------------------------------------------------ ;;; ; printMinus, _printSpace: print a minus sign, and a plus sign. ;;; ; ------------------------------------------------------------ _printMinus: push ecx push edx mov ecx, minus mov edx, 1 call _printString pop edx pop ecx ret _printSpace: push ecx push edx mov ecx, space mov edx, 1 call _printString pop edx pop ecx ret ;;; ; ------------------------------------------------------------ ;;; ; _printRegs: prints all the registers. ;;; ; ------------------------------------------------------------ section .data minus db '-' space db ' ' eaxStr db 'eax ' ebxStr db 'ebx ' ecxStr db 'ecx ' edxStr db 'edx ' esiStr db 'esi ' ediStr db 'edi ' eaxTemp dd 0 ebxTemp dd 0 ecxTemp dd 0 edxTemp dd 0 esiTemp dd 0 ediTemp dd 0 section .text _printRegs: mov [eaxTemp], eax mov [ebxTemp], ebx mov [ecxTemp], ecx mov [edxTemp], edx mov [ediTemp], edi mov [esiTemp], esi pushad ;; print eax mov ecx, eaxStr mov edx, 4 call _printString call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println ;; print ebx mov ecx, ebxStr mov edx, 4 call _printString mov eax, [ebxTemp] call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println ;; print ecx mov ecx, ecxStr mov edx, 4 call _printString mov eax, [ecxTemp] call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println ;; print edx mov ecx, edxStr mov edx, 4 call _printString mov eax, [edxTemp] call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println ;; print edi mov ecx, ediStr mov edx, 4 call _printString mov eax, [ediTemp] call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println ;; print esi mov ecx, esiStr mov edx, 4 call _printString mov eax, [esiTemp] call _printHex call _printSpace call _printDec call _printSpace call _printInt call _println popad ret