Assignment 4

Assignment goals:

Understanding concepts and mechanisms in computer architecture and assembly language. Preparation for final exam in assembly language and SPlab.

Note: This assignment is to be done SOLO.

Questions:

Answer all the following questions. BRIEFLY explain all your answers.

Write a macro that receives a pointer to a null-terminated string, and generates the code that prints it out using system calls, using memory ONLY ON THE STACK. You may not use any library functions inside the macro.
Consider the following 80X86 code segment.
```
        section .data

        mov    eax, 0
     l: shl    ebx, 1
        adc    eax, 0
	add    al, 0
	jnz    l
```
We wish to write this code without using any form of LOOP, and with no conditional jumps (we can use other forms of JMP, however). Write a code segment that provides the same results for eax (but may use or destroy other registers). You may NOT "unfold" the above loop!
Write 80X86 instructions to get a value of -1 in the al register on an 80X86:
1. List 5 different ways to do this with ONE instruction, assuming that it had the value 1 originally.
2. List 2 ways to do this with 2 instructions, each different from all the instructions used in part 1.
Consider the following structure definition in C, used to represent a node in a binary tree:
```
typedef struct node {
    struct node *left, *right;
    int value;
} node;
```
Write a recursive function in 80X86 assembly language that computes and returns the sum of all the values in the leaves of the tree, that can be called from C and has the following signature:
```
int sum_leaves(node *p);
```
List the SHORTEST POSSIBLE CODE (counting number of instructions) for making x, y, and z, defined as follows, get the value -1.
```
    x:   resb 1
    z:	 resw 1
    y:   dw   0xff00
```
a) For an 80X86 machine, b) For Motorola 68000, which is a big-endian machine (assume that it has an instruction: MOVEQ.S #num, var that moves a value num to a location in memory at address var. S is the operand size, one of: B (byte), W (16 bit word), L (32 bit longword).
Consider the following 80X86 code segment. Assume that when the code is run, ECX is non-zero.
```
  L: MOV    AL, [ESI]
     XOR    [EDI], AL
     LOOP   L, ECX
```
1. What does this code do?
2. Re-write the above code segment for better runtime efficiency, under the assumption that ECX initially is divisible by 4.

Consider the following code for Motorola 68000 (comments state what each instruction does, according to the 68000 instruction manual (no, we did not teach you that machine, you should learn the relevant details on your own from the exercise). Note that the 68000 has 32-bit registers D0-D7 and A0-A7, where A7 is also the STACK POINTER.

 F: MOVE.L   D0, -(A7)     ; D0 to memory - predecrement mode
    SUBQ.L   #1, D0        ; Subtract immediate - long (32 bit) operand
    BMI      N             ; Branch (jump) if result was negative
    JSR      F             ; CALL subroutine F (push PC then jump to F)
    ADD.L   (A7)+, D2      ; Signed add memory (postincrement) 
                           ; with D2, result in D2
    RTS                    ; Return from procedure/subroutine
 N: MOVE.L   (A7)+, D0     ; Move memory to D0 - postincrement mode
    MOVEQ.L  #1, D2        ; Move immediate to D2
    RTS

What happens if we execute an instruction JSR F, with D0=0? D0=1? Other values of D0 (call that value k)?

Write instruction sequences to perform some common set operations, for 80X86.

Each set is a subset of [1..16], and is represented by corresponding bits in the register (e.g., AX=1000000000000101 represents {1,3,16}).

Use the following table. Each entry contains a single bit. The index into the table selects which bit is set (e.g., the value at index zero has bit zero set).

 
BitTbl:         dw   1, 2, 4, 8
                dw   10h, 20h, 40h, 80h
                dw   100h, 200h, 400h, 800h
                dw   1000h, 2000h, 4000h, 8000h

a. Insert - adds the specified item to the set.

   BX contains a value in the range 0..15.
   AX contains a set.

b. Member - Member clears the zero flag if BX is an element
            of the AX set, it sets the zero flag otherwise.

   BX contains a value in the range 0..15.
   AX contains a set.

c. Parity - EAX describes a set. Check whether the number of elements in the set, is
   even, and if it is turn on the parity flag, otherwise turn it off.

d. Union - computes EAX := EAX union EBX.
          

e. Set difference - find the elements in the set described in EBX but
   not in EAX. The result should be in ECX.

In the SPAKKY processor manufactured by the MOON company, multiplication takes 5 time units, and addition takes 2 time units. A certain program run uses 50% addition and 50% multiplication instructions (instruction count, not runtime). MOON's engineers want to improve the machine so that the current runtime of the program, 100 seconds, is reduced to 90 seconds, by improving the efficiency of the multiplication instruction. However, doing so will cause addition to require 3 time units. How many time units should they target for the multiplication instruction, in order to achieve the 90-second runtime goal?

Codes and Hamming distances:

 
(a) What is the distance of the following code?

    X  |   Code word
    -------------
    00 | 000000
    01 | 001111
    10 | 110010
    11 | 111101

 (b) How many errors can it detect?  
 (c) How many errors can it fix?       
 (d) How many erasures can it fix?

(SPlab part) Consider the following hexedit display of an ELF file.

00000000   7F 45 4C 46  01 01 01 00  00 00 00 00  .ELF........
0000000C   00 00 00 00  02 00 03 00  01 00 00 00  ............
00000018   30 83 04 08  34 00 00 00  50 14 00 00  0...4...P...
00000024   00 00 00 00  34 00 20 00  08 00 28 00  ....4. ...(.
00000030   24 00 21 00  06 00 00 00  34 00 00 00  $.!.....4...
0000003C   34 80 04 08  34 80 04 08  00 01 00 00  4...4.......
00000048   00 01 00 00  05 00 00 00  04 00 00 00  ............

(a) How many section headers does it have?
(b) Is it an object file or an executable file?

(SPlab part) What does the run of the following program print:

main() {
   int i = 3, pid;

   while(--i) {
     pid = fork();
     if(pid || (i&1))
       printf("boo %d!\n", i);
   }
}

Is the answer unique?

Nominal deadline: Thursday, June 16, at 12:00 noon.