c language

CAS CS 210 - Computer Systems Fall 2014

PROBLEM SET 2 (PS2) (ASSEMBLY LANGUAGE AND PROGRAM REPRESENTATIONS) OUT: SEPTEMBER 25

DUE: OCTOBER 16, 1:30 PM

NO LATE SUBMISSIONS WILL BE ACCEPTED

Page 1 of 13

Problem 1: 6 Points

Match each of the assembler routines on the left with the equivalent C function on the right. foo1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax shrl $31, %eax popl %ebp ret

foo2: pushl %ebp movl %esp, %ebp movl $0, %eax popl %ebp ret

foo3: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax addl %eax, %eax leal 0(,%eax,8), %edx movl %edx, %ecx subl %eax, %ecx movl %ecx, %eax popl %ebp ret

foo4: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax addl $13, %eax leal 3(%eax), %edx testl %eax, %eax cmovs %edx, %eax sarl $2, %eax popl %ebp ret

foo5: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax leal 15(%eax), %edx testl %eax, %eax cmovs %edx, %eax sarl $4, %eax popl %ebp ret

foo6: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax sarl $31, %eax popl %ebp ret

int choice1(int x) // foo5 {

return x / 16; }

int choice2(int x) // foo3 {

return 14 * x; }

int choice3(int x) // foo2 {

return (x << 31) & 1; }

int choice4(int x) // foo1 {

return (x < 0); }

int choice5(int x) // foo4 { return (x + 13) /4;

}

int choice6(int x) // foo6 {

return (x >> 31); }

Fill in your answers here: foo1 corresponds to choice . foo2 corresponds to choice . foo3 corresponds to choice . foo4 corresponds to choice . foo5 corresponds to choice . foo6 corresponds to choice .

Page 2 of 13

Problem 2: 9 Points

A: 3 Points

Consider the following C functions and assembly code:

int fun3(int a) {

return a * 128; }

int fun12(int a) {

return a * 33; }

int fun5(int a) {

return a * 65; }

pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl %edx, %eax sall $6, %eax addl %edx, %eax popl %ebp ret

Page 3 of 13

B: 3 Points

Consider the following C functions and assembly code:

int fun3(int a, int b) {

if (a & b) return a;

else return b;

}

int fun4(int a, int b) {

if (a & b) return b;

else return a;

}

int fun5(int a, int b) {

if (a < b) return b;

else return a;

}

pushl %ebp movl %esp, %ebp movl 12(%ebp), %eax movl 8(%ebp), %edx andl %edx, %eax testl %eax, %eax je .L2 movl 12(%ebp), %eax jmp .L3

.L2: movl 8(%ebp), %eax

.L3: popl %ebp ret

Which of the functions compiled into the assembly code shown?

Page 4 of 13

C: Points 3

Consider the following C functions and assembly code:

int funA(int *a, int idx, int *b) {

if (a[idx] > *b)

*b = a[idx]; else

*b = 2 * *b; return *b;

}

int funB(int *a, int idx, int *b) {

if (b[idx] > *a)

*a = b[idx]; else

*a = 2 * *a; return *a;

}

int funC(int *a, int idx, int *b) {

if (a[idx] > b) b = a[idx];

else b = 2 * b;

return b; }

pushl %ebp movl %esp, %ebp movl 16(%ebp), %eax movl 12(%ebp), %ecx movl 8(%ebp), %edx movl (%edx,%ecx,4), %ecx movl (%eax), %edx cmpl %edx, %ecx jle .L2 movl %ecx, (%eax) jmp .L3

.L2: addl %edx, %edx movl %edx, (%eax)

.L3: movl (%eax), %eax popl %ebp ret

Which of the functions compiled into the assembly code shown?

Page 5 of 13

Problem 3: 10 Points

Consider the following assembly representation of a function foo containing a for loop:

1 b a r : 2 p u s h l %ebp 3 movl %e s p , %ebp 4 s u b l $16 , %e s p 5 movl 8(% ebp ) , %e a x 6 a d d l %eax , %e a x 7 movl %eax , −4(%ebp ) 8 movl $0 , −8(%ebp ) 9 jmp . L 2

10 . L 3 : 11 movl −8(%ebp ) , %e a x 12 a d d l $7 , %e a x 13 a d d l %eax , −4(%ebp ) 14 movl −8(%ebp ) , %e a x 15 l e a l 5(% e a x ) , %edx 16 movl −4(%ebp ) , %e a x 17 i m u l l %edx , %e a x 18 movl %eax , −4(%ebp ) 19 a d d l $1 , −8(%ebp ) 20 . L 2 : 21 movl −8(%ebp ) , %e a x 22 c m p l 8(% ebp ) , %e a x 23 j l . L 3 24 movl −4(%ebp ) , %e a x 25 l e a v e 26 r e t

Fill in the blanks to provide the functionality of the loop:

int bar(int x) {

int i; int val = _____________;

for( ________; ________; i++ ) {

__________________;

__________________;

} return val;

}

Page 6 of 13

Problem 4: Points 12

#include <stdio.h> #include <stdlib.h>

typedef long long Unum; #define NAMELEN 80

struct Emp { Unum id; char name[NAMELEN]; int salary; struct Emp *next;

};

struct Emp *Emp_list = 0;

Unum Emp_get_id(struct Emp *emp) { return emp->id; }

void Emp_set_id(struct Emp *emp, Unum id) { emp->id = id; }

void Emp_get_name(struct Emp *emp, char *name) { int i; for (i=0;i<NAMELEN; i++) name[i] = emp->name[i];

}

void Emp_set_name(struct Emp *emp, char *name) { int i; for (i=0;i<NAMELEN; i++) emp->name[i] = name[i];

}

int Emp_get_salary(struct Emp *emp) { return emp->salary; }

void Emp_set_salary(struct Emp *emp, int salary) { emp->salary = salary; }

struct Emp * Emp_get_next(struct Emp *emp) { return emp->next; }

void Emp_set_next(struct Emp *emp, struct Emp *next) { emp->next = next; }

void Emp_Emp(struct Emp *emp, Unum id, char *name, int salary) { Emp_set_id(emp, id); Emp_set_name(emp, name); Emp_set_salary(emp, salary); Emp_set_next(emp, 0);

}

struct Emp *Emp_new() { return malloc(sizeof(struct Emp)); }

void Emp_add(Unum id, char *name, int salary) { struct Emp *emp = Emp_new(); Emp_Emp(emp, id, name, salary); Emp_set_next(emp, Emp_list); Emp_list = emp;

}

Page 7 of 13

Given the above code and the following disassembly

08048510 <mystery>: 8048510: 8b 15 ac 98 04 08 mov 0x80498ac,%edx 8048516: 31 c0 xor %eax,%eax 8048518: 55 push %ebp 8048519: 89 e5 mov %esp,%ebp 804851b: 85 d2 test %edx,%edx 804851d: 74 0b je 804852a <mystery+0x1a> 804851f: 90 nop 8048520: 03 42 58 add 0x58(%edx),%eax 8048523: 8b 52 5c mov 0x5c(%edx),%edx 8048526: 85 d2 test %edx,%edx 8048528: 75 f6 jne 8048520 <mystery+0x10> 804852a: 5d pop %ebp 804852b: c3 ret

Assuming &Emp list is 0x80498ac fill in the following table. Your explanations should not just be a restatement of the assembly code. Rather the explanation sould be interms of the what the assembly is doing in context of the above ’C’ code. Here are two examples of the kind of explanations we are looking for: 1) “save old frame pointer” and 2) “test if the list is empty”.

Address Explanation 8048510 initialize edx to emp list

8048516

8048518

8048519

804851b

804851d

804851f NOP 8048520

8048523

8048526

8048528

804852a restore old frame pointer 804852b return

What purpose does the mystery function server eg. what is it doing?

Page 8 of 13

Problem 5: 14 Points

Consider the following C code

1 # i n c l u d e < s t d i o . h> 2 3 v o i d b a r ( c h a r ∗b u f , c h a r ∗ s r c ) 4 { 5 w h i l e (∗ s r c ) { 6 ∗b u f = ∗ s r c ; 7 b u f + + ; s r c + + ; 8 } 9 r e t u r n ;

10 } 11 12 v o i d f o o ( v o i d ) 13 { 14 i n t i = 0 ; 15 c h a r b u f [ 4 ] ; 16 17 b a r ( b u f , ” H e l l o World ! ” ) ; 18 p r i n t f ( ” 0 x%x 0 x%x\n ” , &i , i ) ; 19 20 r e t u r n ; 21 } 22 23 i n t m a i n ( i n t a r g c , c h a r ∗∗ a r g v ) 24 { 25 f o o ( ) ; 26 r e t u r n 1 ; 27 }

Page 9 of 13

and the following dissasembly:

1 Dump o f a s s e m b l e r c o d e f o r f u n c t i o n f o o : 2 0 x 0 8 0 4 8 3 e c <+0>: p u s h %e b p 3 0 x 0 8 0 4 8 3 e d <+1>: mov %e s p ,% e b p 4 0 x 0 8 0 4 8 3 e f <+3>: s u b $0x28 ,% e s p 5 0 x 0 8 0 4 8 3 f 2 <+6>: movl $0x0 ,−0 x c (% e b p ) 6 0 x 0 8 0 4 8 3 f 9 <+13>: movl $ 0 x 8 0 4 8 5 0 4 , 0 x4 (% e s p ) 7 0 x 0 8 0 4 8 4 0 1 <+21>: l e a −0x10 (% e b p ) , % e a x 8 0 x 0 8 0 4 8 4 0 4 <+24>: mov %e a x , ( % e s p ) 9 0 x 0 8 0 4 8 4 0 7 <+27>: c a l l 0 x 8 0 4 8 3 c 4 <b a r >

10 0 x 0 8 0 4 8 4 0 c <+32>: mov −0x c (% e b p ) , % e a x 11 0 x 0 8 0 4 8 4 0 f <+35>: mov %e a x , 0 x8 (% e s p ) 12 0 x 0 8 0 4 8 4 1 3 <+39>: l e a −0x c (% e b p ) , % e a x 13 0 x 0 8 0 4 8 4 1 6 <+42>: mov %e a x , 0 x4 (% e s p ) 14 0 x 0 8 0 4 8 4 1 a <+46>: movl $ 0 x 8 0 4 8 5 1 1 , ( % e s p ) 15 0 x 0 8 0 4 8 4 2 1 <+53>: c a l l 0 x 8 0 4 8 2 f 4 <p r i n t f @ p l t > 16 0 x 0 8 0 4 8 4 2 6 <+58>: l e a v e 17 0 x 0 8 0 4 8 4 2 7 <+59>: r e t

Use the following table to translate the ASCII characters to their hexadecimal values.

00 nul 01 soh 02 stx 03 etx 04 eot 05 enq 06 ack 07 bel 08 bs 09 ht 0a nl 0b vt 0c np 0d cr 0e so 0f si 10 dle 11 dc1 12 dc2 13 dc3 14 dc4 15 nak 16 syn 17 etb 18 can 19 em 1a sub 1b esc 1c fs 1d gs 1e rs 1f us 20 space 21 ! 22 " 23 # 24 $ 25 % 26 & 27 ’ 28 ( 29 ) 2a * 2b + 2c , 2d - 2e . 2f / 30 0 31 1 32 2 33 3 34 4 35 5 36 6 37 7 38 8 39 9 3a : 3b ; 3c < 3d = 3e > 3f ? 40 @ 41 A 42 B 43 C 44 D 45 E 46 F 47 G 48 H 49 I 4a J 4b K 4c L 4d M 4e N 4f O 50 P 51 Q 52 R 53 S 54 T 55 U 56 V 57 W 58 X 59 Y 5a Z 5b [ 5c \ 5d ] 5e ˆ 5f _ 60 ‘ 61 a 62 b 63 c 64 d 65 e 66 f 67 g 68 h 69 i 6a j 6b k 6c l 6d m 6e n 6f o 70 p 71 q 72 r 73 s 74 t 75 u 76 v 77 w 78 x 79 y 7a z 7b { 7c | 7d } 7e ˜ 7f del

Page 10 of 13

Part A

Given the code, the ascii chart on the previous page, and the following starting values, fill in the following memory diagram with execution proceeding up to 0x0804840c.

pc = 0x080483ed esp = 0xffffd368

Memory values not updated may be left blank. Remember that an int value is 4 bytes located with the least significant byte at the address and the remaining 3 bytes in the successive byte addresses. Eg. If we know that six bytes starting at 0xbfffec10 is 0x01, 0x02, 0x03, 0x04, 0x05, 0x06 then we would have to write down :

0xbfffec10: 04030201 0xbfffec14: ????0605

Individual bytes of an int that whose value are unknown should be specifed as ??.

Address int hex value Description 0xffffd36c 0x08048433 return address for call to foo 0xffffd368 0xffffd378 old frame pointer 0xffffd364

0xffffd360

0xffffd35c

0xffffd358

0xffffd354

0xffffd350

0xffffd34c

0xffffd348

0xffffd344

0xffffd340

0xffffd33c

Page 11 of 13

In the descriptions be sure to indicate if an address corresponds to a specific variable or argument and its value or if an address is a return address and its value.

Part B

Provide the output from the printf in the foo function:

Page 12 of 13

Problem 6: 10 Points

Consider the following incomplete definition of a C struct along with the incomplete code for a function func given below.

typedef struct node {

_______________ x;

_______________ y;

struct node *next;

struct node *prev;

} node_t;

node_t n;

void func() {

node_t *m;

m = ______________________;

m->y /= 16;

return; }

When this C code was compiled on an IA-32 machine running Linux, the following assembly code was generated for function func.

func: pushl %ebp movl n+12,%eax movl 16(%eax),%eax movl %esp,%ebp movl %ebp,%esp shrw $4,8(%eax) popl %ebp ret

Given these code fragments, fill in the blanks in the C code given above. Note that there is a unique answer.

The types must be chosen from the following table, assuming the sizes and alignment given.

Type Size (bytes) Alignment (bytes) char 1 1 short 2 2

unsigned short 2 2 int 4 4

unsigned int 4 4 double 8 4

Page 13 of 13