Assignment 4: solutions

Assignment goals:

The assignment helps understanding concepts and mechanisms in computer architecture and assembly language. The assignment is a preparation for final exam in assembly language and SPlab. Note: This assignment is to be done SOLO.

1. Three numbers are stored in memory locations 70h, 71h, and 72h, which should be given the names X, Y and Z. Write an assembly language program that finds the smallest number and stores it in 73h.

Answer: (assuming unsigned arithmetic, result 0XFF if none is even)
    X EQU 0x70
    Y EQU 0x71
    Z EQU 0x72

          mov  bl, 0xFF    ; current smallest
          test byte [X], 1
          jz   DoneX
          mov  bl, [X]
DoneX:    test byte [Y], 1
          jz   DoneY
          cmp  bl, [Y]
          jc   DoneY
          mov  bl, [Y]
DoneY:    test byte [Z], 1
          jz   DoneZ
          cmp  bl, [Z]
          jc   DoneZ
          mov  bl, [Z]
DoneZ:    mov  [0x73], bl     
  ; Note that this program will crash due to segmentation fault in 32 bit LINUX as 
  ; written because a process in user mode is not allowed access to virtual memory addresses 0x70 through 0x73.

2. Consider the following 80X86 code segment. Assume that when the code is run, CX is non-zero.
L: ADD AX, AX
ADC DX, 0
LOOP L

1. What is the result of running the code?
2. Re-write the above code segment for better efficiency.

ANSWER: The value in AX is added to itself CX (or ECX, depending on default) times, and the result each time is added
with carry to DX. At some point (at most 16 loops) AX becomes 0, so any additional loops do nothing.
An immediate improvement then is then to preface the code with:

    CMP   ECX, 16
    JNC   L
    MOV   ECX, 16

There may be additional tricks.

3. What is the output of the following code.

mov bh, 0
push 0x000a2164
push 0x6f6f6720
push 0x79726556
push esp
call printf
add esp, 16


ANSWER: The format string printed is on the stack, starting with the last pushed (lowest address).
Convert to ASCII, noting the little endian, so:
  0x56, 0x65, 0x72,   ...  0x64, 0x21, 0x0a, 0 (null termination), so we get the "string":

     "Very good!" (without the quotes, and with a line-feed at the end)

4. List 5 different ways to add 1 to the EAX register on an 80X86 with exactly 2 80X86 instructions, where both instructions should be meaningful for a solution (i.e. if delete one instruction of the two, a solution would not work). Assume the following initial state.

eax = 3
ebx = 3

ANSWERS:
   a:   SUB     EAX, 1
        ADD     EAX, 2

(For the rest, we mean different MNEMONICS as otherwise we can get many answers by
taking the above answer and adding any value x to both immediate constants.)

   b:  DEC     EAX
       ADD     EAX, 2

   c:  STC           ; set carry
       ADC     EAX, 0

   d:  CLC          ; clear carry
       ADC     EAX, 1

Now, assuming the initial state  eax=ebx=3 we can also do:
   e:  INC     EBX
       XCHG    EAX, EBX

5. List the shortest possible code for adding 5 to y, subtracting 2 from x, and adding 1 to z, which are defined as follows (consecutive locations):

x: resb 1
z: resw 1
y: resb 1
If we know that subtracting 2 from x and adding 1 to z cause no overflow, is there a shorter way to do that? How?

ANSWER: If we know nothing about the values, then we need to do one instruction each, so:
      ADD  BYTE [y], 5
      SUB  BYTE [x], 2
      INC  WORD [z]

But if we are sure there is no overflow in the operations on x, z we can do it with one ADD instruction:
      ADD DWORD [x], 0x050001FE
because this adds 0xFE (i.e. -2) to the lowest byte, which is x, adds 0x0001 to z, and adds 0x05 to
the most significant byte, which is where y resides. This can also be done with subtraction, with a
different constant (minus the above in 2's complement). An overflow spoils this as then the addition
to x overflows onto the z variable, etc.

6. On Intel 80X86, suppose that AX = 0000000011010111, BX = 0000000001110010, CX = 0000000010111001, and Carry Flag = 1. What is the result of the following operations (also describe the state of the carry and overflow flags after execution of each)

a. ADD CL, AL
b. ADC AL, 0xF9
c. ADD AX, 0x003A
d. SUB BL, 0x73
e. RCR CX, 3

ANSWERS:
a:   CL = 10010000,  CF = 1, OF = 0

b:   AL = 11010001,  CF = 1, OF = 0

c:   AX = 0000000100010001, CF=1, OF = 0

d:   BL = 11111111, CF=1, OF = 0

e:   CX = 0110000000010111, CF = 0, OF = undefined

7. Write instruction sequences to perform some common set operations, for 80X86.
Each set is a subset of [1..16] 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. Delete - deletes the specified item from the set.

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

b. Odd - sets the zero flag if AX contains a set of numbers that are all odd.

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

d. UnionSets - Union computes AX := AX union BX.

AX and BX contain the sets.

e. Intersection - Intersection computes AX := AX intersect BX.

AX and BX contain the sets.

f. Complement - Complement computes AX := - AX, that is, all elements in the set are removed, and all elements not in the set are added.

ANSWERS:

We read the value in BX to mean BX=0 is "delete item 1" etc.
a:    MOV    BX, [BitTbl +2*BX]
      NOT    BX
      AND    AX, BX

    (the above works even if the "deleted" element is not in the set originally)

b:    TEST   AX, 0xAAAA  ; and with all EVEN items. If zero means no even elements, i.e. all odd

c:    TEST   AX, [BitTbl +2*BX]

d:    OR     AX, BX

e:    AND    AX, BX

f:    NOT    AX

8. Codes and Hamming distances:

Given the following two 5-bit code words, we would like to extend this code to 4 code words of the same length (without changing the two given code words).

    | Code word
-------------
 00 | 00000
 11 | 11111

   (a) What is the maximum hamming distance that we can get for the resulting code?
   (b) How many errors can it detect?
   (c) How many errors can it fix?
   (d) How many erasures can it fix?
   (e) Is it possible to change only a single bit in one of the two given code words above in order to extend it to 4 code words with better hamming distance? If yes, what is the needed change?

ANSWER:
We need to add 2 code words. Condsider any code word, it must have x 0's, and 5-x 1's.
So this code word must have minimum distance min(x, 5-x) from one of the current code
words, and the maximum we can get for this expression is 2. Say we pick the code words:
00011 and 11000. Each of them has distance of 2 or 3 from any other code word, so (a) the distance
of the code is 2.

So this code can: (b) detect 1 error, (c) fix no errors, (d) fix one erasure.

Finally (e) changing ANY bit, say making the 2nd code-word 11110, now we can add 2 code words:
11001, 00111. A quick check shows that these 2 word have distance 3 from 00000 and from
11110, and distance 4 from each other. So the distance of this new code is 3.

9. The following macros definitions are given

  %define ctrl 0x1F &
  %define param(a, b) ((a)+(a)*(b))
  %xdefine c1 ctrl
  %xdefine ctrl 2

Which result code line would be generated by assembler for the following source code line?

Mov byte [param(ctrl, ebx)], c1 'D'

ANSWER:  
Mov byte [((2)+(2)*ebx)], 0x1F & 'D'

10. The following PIC is given

  to_printf: dd printf
  get_my_loc:
        call next_i
  next_i: pop edx
        ret

  call get_my_loc
  push edx
  add edx, (to-print - next_i)

Which of the answers below are right?

  1. a position of to_printf cannot be calculated since this code is PIC
  2. this code is not PIC since it uses printf
  3. after this code execution EDX contains an offset of printf in the section that contains printf definition
  4. after this code execution EDX contains a difference of addresses of to_printf and next_i
  5. after this code execution EDX contains an absolute address of printf
  6. after this code execution EDX contains an absolute address of to_printf

ANSWER: 6

11. Given the following C code

  z = foo(&x, &y);

Given the following assembly code that implements foo using the C calling convention:

  foo:
  push ebp
  mov ebp, esp
  push ebx
  mov ebx, [ebp+12]
  mov eax, [ebp+8]
  mov eax, [eax]
  sub eax, ebx
  pop ebx
  ret

What is a return value of foo (using x and y to state the answer)?


ANSWER: x- &y

12. 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)
    SUB.L   (A7)+, D2      ; Signed subtract 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)?

ANSWER: with D0=0 we go to N immediately, and return with D2=-1 and D0-0.
        (there is also a push and pop of D0 which does nothing).

with D0=1 we push 1, and recursive call to F with D0=0, (which returns with D0=0 and
D2=-1), and then subtract 1-(-1) to get D2=2.

In general F computes in D2:
 F(k) = k - F(-1)    ; if k>0
 F(k) = -1           ; if k=0

For k=2 we have F(k) = 2-2 = 0
For k=3 we have F(k) = 3-0 = 3
For k=4 we have F(k) = 4-3 = 1
etc.

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

00000000   7F 45 4C 46  01 01 01 00  00 00 00 00  00 00 00 00  .ELF............
00000010   02 00 03 00  01 00 00 00  62 80 04 08  34 00 00 00  ........b...4...
00000020   D0 00 00 00  00 00 00 00  34 00 20 00  01 00 28 00  ........4. ...(.
00000030   07 00 04 00  01 00 00 00  00 00 00 00  00 80 04 08  ................
00000040   00 80 04 08  9E 00 00 00  9E 00 00 00  05 00 00 00  ................
00000050   00 10 00 00  00 00 00 00  00 00 00 00  00 00 00 00  ................
00000060   90 90 B8 04  00 00 00 BB  01 00 00 00  8B 0D 9A 80  ................
00000070   04 08 BA 08  00 00 00 CD  80 E8 01 00  00 00 90 B8  ................
00000080   01 00 00 00  BB 00 00 00  00 CD 80 00  FF FF FF FF  ................
00000090   41 68 6D 65  64 69 21 0A  00 00 90 80  04 08 00 2E  Ahmedi!.........
000000A0   73 79 6D 74  61 62 00 2E  73 74 72 74  61 62 00 2E  symtab..strtab..
000000B0   73 68 73 74  72 74 61 62  00 2E 74 65  78 74 00 2E  shstrtab..text..
000000C0   72 6F 64 61  74 61 00 53  79 72 69 61  00 00 00 00  rodata.Syria....
000000D0   00 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00  ................
000000E0   00 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00  ................
000000F0   00 00 00 00  00 00 00 00  1B 00 00 00  01 00 00 00  ................
00000100   06 00 00 00  60 80 04 08  60 00 00 00  2B 00 00 00  ....`...`...+...
00000110   00 00 00 00  00 00 00 00  10 00 00 00  00 00 00 00  ................
00000120   21 00 00 00  01 00 00 00  02 00 00 00  8C 80 04 08  !...............
00000130   8C 00 00 00  0D 00 00 00  00 00 00 00  00 00 00 00  ................
00000140   04 00 00 00  00 00 00 00  29 00 00 00  01 00 00 00  ........).......
00000150   02 00 00 00  99 80 04 08  99 00 00 00  05 00 00 00  ................
00000160   00 00 00 00  00 00 00 00  01 00 00 00  00 00 00 00  ................
00000170   11 00 00 00  03 00 00 00  00 00 00 00  00 00 00 00  ................
00000180   9E 00 00 00  2F 00 00 00  00 00 00 00  00 00 00 00  ..../...........
00000190   01 00 00 00  00 00 00 00  01 00 00 00  02 00 00 00  ................
000001A0   00 00 00 00  00 00 00 00  E8 01 00 00  E0 00 00 00  ................
000001B0   06 00 00 00  0A 00 00 00  04 00 00 00  10 00 00 00  ................
000001C0   09 00 00 00  03 00 00 00  00 00 00 00  00 00 00 00  ................
000001D0   C8 02 00 00  44 00 00 00  00 00 00 00  00 00 00 00  ....D...........
000001E0   01 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00  ................
000001F0   00 00 00 00  00 00 00 00  00 00 00 00  60 80 04 08  ............`...
00000200   00 00 00 00  03 00 01 00  00 00 00 00  8C 80 04 08  ................
00000210   00 00 00 00  03 00 02 00  00 00 00 00  99 80 04 08  ................
00000220   00 00 00 00  03 00 03 00  01 00 00 00  00 00 00 00  ................
00000230   00 00 00 00  04 00 F1 FF  06 00 00 00  8C 80 04 08  ................
00000240   00 00 00 00  00 00 02 00  0D 00 00 00  90 80 04 08  ................
00000250   00 00 00 00  00 00 02 00  15 00 00 00  7F 80 04 08  ................
00000260   00 00 00 00  00 00 01 00  1A 00 00 00  99 80 04 08  ................
00000270   00 00 00 00  00 00 03 00  20 00 00 00  9A 80 04 08  ........ .......
00000280   00 00 00 00  00 00 03 00  25 00 00 00  62 80 04 08  ........%...b...
00000290   00 00 00 00  10 00 01 00  2C 00 00 00  9E 90 04 08  ........,.......
000002A0   00 00 00 00  10 00 F1 FF  38 00 00 00  9E 90 04 08  ........8.......
000002B0   00 00 00 00  10 00 F1 FF  3F 00 00 00  A0 90 04 08  ........?.......
000002C0   00 00 00 00  10 00 F1 FF  00 65 32 2E  73 00 54 75  .........e2.s.Tu
000002D0   72 6B 65 79  00 4C 65 62  61 6E 6F 6E  00 65 78 69  rkey.Lebanon.exi
000002E0   74 00 41 73  73 61 64 00  48 6F 6D 73  00 5F 73 74  t.Assad.Homs._st
000002F0   61 72 74 00  5F 5F 62 73  73 5F 73 74  61 72 74 00  art.__bss_start.
00000300   5F 65 64 61  74 61 00 5F  65 6E 64 00               _edata._end.

(a) How many section headers does it have?
(b) Is it an object file or an executable file?
(c) How many program headers does it have?
(d) If there are any program headers, what does the first program header do?
(e) If there are any section headers, at what offset is the section header table?
(f) What are the names of all the sections in this file, if any?

ANSWER METHOD: (a) (b) (c) are retrieved from the ELF header, using
the ELF32 header struct, fields: shnum=7, type=executable, and phnum=1, respectively.

To answer (d), if phnum>0 find the program header table by using phoff in the
ELF header, and parse the first program header: find its type, vaddr, offset, mem (and file) size.
(Causes a LOAD from offset 0 in the file, to memory virtual address 0x08048000, size of 0x009E bytes.
    Protection flages are R (read), E (execute), and alignment is 0x1000  (i.e. 4K bytes)
    But actually 1 full 4K bytes are mapped, due to the 4K page size.)

To answer (e), find shoff in the ELF header ( 0xD0, or 208 (decimal)).

To answer (f), find the section header table, use shstrndx in the ELF header to
find the .shstrtab index, find its offset, and this is where all the section names
appear. A quicker way that is less sure is to look for an .shstrtab string, it has to be
a section name so things around it should also be section names, so you also get:
.symtab, .strtab, .text, .rodata, Syria

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

main() {
   int i = 4, pid;

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

Is the answer unique?

ANSWER:
NUKE 3!
NUKE 3!
NUKE 2!
NUKE 2!
NUKE 1!
NUKE 1!
NUKE 1!
NUKE 1!
NUKE 1!
NUKE 1!
NUKE 1!
NUKE 1!

This is not unique, it is possible for some of the NUKE 3! and NUKE 2! to come before some of the
NUKE 1!, depending on the system's process scheduler timing.