Week 03 Laboratory Exercises

Objectives

  • to practice using bitwise memory
  • to practice manipulating dynamic memory
  • to explore arbitrary precision integer arithmetic

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Set up for the lab by creating a new directory called lab03 and changing to this directory.
mkdir lab03
cd lab03

There are some provided files for this lab which you can fetch with this command:

1521 fetch lab03

If you're not working at CSE, you can download the provided files as a zip file or a tar file.

Exercise — individual:
Extract The Components of a Float

Floating-point Representation

Single-precision floating-point numbers that follow the IEEE 754 standard have an internal structure that looks like this:

The value is determined as: \[ {-1}^{\text{sign}} \times \left(1 + \text{frac}\right) \times 2^{\text{exp} - 127} \] The 32 bits in each float are used as follows:

sign

is a single bit that indicates the number's sign. If set to 0, the number is positive; if set to 1, the number is negative.

exp

is an unsigned 8-bit value (giving a range of \([0\cdots255]\)) which is interpreted as a value in the range \([-127\cdots128]\) by subtracting 127 (the bias) from the stored 8-bit value. It gives a multiplier for the fraction part (i.e., \( 2^{\text{exp}-127} \)).

frac

is a value in the range \( [0\cdots1] \), determined using positional notation: \[ \frac{\text{bit}_{22}}{2^{1}} + \frac{\text{bit}_{21}}{2^{2}} + \frac{\text{bit}_{20}}{2^{3}} + \cdots + \frac{\text{bit}_{2}}{2^{21}} + \frac{\text{bit}_{1}}{2^{22}} + \frac{\text{bit}_{0}}{2^{23}} \] The overall value of the floating-point value is determined by adding 1 to the fraction: we assume that the "fraction" part is actually a value in the range \( [1\cdots2] \), but save bits by not explicitly storing the leading 1 bit.

For example:

raw 32 bits:  01000000001000000000000000000000
partitioned:  0 10000000 01000000000000000000000
sign:         0, so positive
exp:          10000000 = 128, so multiplier is 2128-127 = 21
frac:         0×2-1 + 1×2-2 + ... = 0.25, but we need to add 1

final value:  1.25 × 21 = 2.5

Exercise Description

Your task is to add code to this function in float_bits.c:

// separate out the 3 components of a float
float_components_t float_bits(uint32_t f) {
    // PUT YOUR CODE HERE
}

The function float_bits is given the bits of a float as type uint32_t. Add code so that it returns a struct float_components, containing the sign, exponent and fraction fields of the struct.

You also should add appropriate code to the functions is_nan, is_positive_infinity, is_negative_infinity, and is_zero. All four functions take a struct float_components as their argument, and return 0 or 1 depending on some property of the float it represents:

  • is_nan returns 1 iff the struct float_components corresponds to the not-a-number value, NaN, and 0 otherwise;

  • is_positive_infinity returns 1 iff the struct float_components corresponds to the positive infinity, inf, and 0 otherwise;

  • is_negative_infinity returns 1 iff the struct float_components corresponds to the negative infinity, -inf, and 0 otherwise; and

  • is_zero returns 1 iff the struct float_components corresponds to either positive or negative zero.

These function must be implemented only using bit operations and integer comparisons.

Once these functions are completed, you should get output like:

./float_bits -42
float_bits(-42) returned
sign=0x1
exponent=0x84
fraction=0x280000
is_nan returned 0
is_positive_infinity returned 0
is_negative_infinity returned 0
is_zero returned 0
./float_bits 3.14159
float_bits(3.14159012) returned
sign=0x0
exponent=0x80
fraction=0x490fd0
is_nan returned 0
is_positive_infinity returned 0
is_negative_infinity returned 0
is_zero returned 0
./float_bits -inf
float_bits(-inf) returned
sign=0x1
exponent=0xff
fraction=0x000000
is_nan returned 0
is_positive_infinity returned 0
is_negative_infinity returned 1
is_zero returned 0

Use make(1) to build your code:

make    # or 'make float_bits'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest float_bits 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab03_float_bits float_bits.c

You must run give before Monday 04 October 21:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Exercise — individual:
Multiply A Float by 2048 Using Bit Operations

Your task is to add code to this function in float_2048.c:

// float_2048 is given the bits of a float f as a uint32_t
// it uses bit operations and + to calculate f * 2048
// and returns the bits of this value as a uint32_t
//
// if the result is too large to be represented as a float +inf or -inf is returned
//
// if f is +0, -0, +inf or -inf, or Nan it is returned unchanged
//
// float_2048 assumes f is not a denormal number
//
uint32_t float_2048(uint32_t f) {
    // PUT YOUR CODE HERE

    return 42;
}

Add code to the function float_2048 so that, given a float as a uint32_t, it multiplies that value by 2048 using only bit operations and addition (+), and returns the result. If, after multiplication, the result is too large to be represented as a float, return inf if the original float was positive, and -inf if it was negative.

Once your program is working, you should see something like:

./float_2048 1
2048
./float_2048 3.14159265
6433.98193
./float_2048 -2.718281828e-20
-5.56704133e-17
./float_2048 1e38
inf
./float_2048 -1e37
-inf
./float_2048 inf
inf
./float_2048 -inf
-inf
./float_2048 nan
nan

Use make(1) to build your code:

make    # or 'make float_2048'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest float_2048 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab03_float_2048 float_2048.c

You must run give before Monday 04 October 21:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Challenge Exercise — individual:
Compare Floats Using Bit Operations

Your task is to add code to this function in float_less.c:

// float_less is given the bits of 2 floats bits1, bits2 as a uint32_t
// and returns 1 if bits1 < bits2, 0 otherwise
// 0 is return if bits1 or bits2 is Nan
// only bit operations and integer comparisons are used
uint32_t float_less(uint32_t bits1, uint32_t bits2) {
    // PUT YOUR CODE HERE

    return 42;
}

Add code to the function float_less, which takes the bits of two floats as the type uint32_t, and returns 1 if the value of the first float is less than the second, and 0 otherwise. It should do this using bit operations and integer comparisons.

For example:

./float_less 1 2
float_less(1, 2) returned 1 which is correct
float_less(2, 1) returned 0 which is correct
./float_less -3.14159265 -2.718281828e-20
float_less(-3.14159274, -2.7182819e-20) returned 1 which is correct
float_less(-2.7182819e-20, -3.14159274) returned 0 which is correct
./float_less -inf inf
float_less(-inf, inf) returned 1 which is correct
float_less(inf, -inf) returned 0 which is correct
./float_less -0 0
float_less(-0, 0) returned 0 which is correct
float_less(0, -0) returned 0 which is correct
./float_less NaN inf
float_less(nan, inf) returned 0 which is correct
float_less(inf, nan) returned 0 which is correct

Use make(1) to build your code:

make    # or 'make float_less'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest float_less 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab03_float_less float_less.c

You must run give before Monday 04 October 21:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Challenge Exercise — individual:
Print A Float Using Only putchar and puts

Your task is to add code to this function in float_print.c:

//
// float_print is given the bits of a float as a uint32_t
// it prints out the float in the same format as "%.9g\n"
// using only putchar & puts
//
void float_print(uint32_t bits) {
    // PUT YOUR CODE HERE
}

The function float_print takes a float as a uint32_t. Add code to it that prints its value as a decimal, in "%.9g" format, using only putchar(3) or puts(3). You cannot use any other functions, such as printf(3).

Once your implementation is working, you should see things like:

./float_print 1
1
./float_print 3.14159265
3.14159274
./float_print -2.718281828e-20
-2.7182819e-20
./float_print 1.7e38
1.69999998e+38
./float_print inf
inf
./float_print -inf
-inf
./float_print nan
nan

Use make(1) to build your code:

make    # or 'make float_print'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest float_print 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab03_float_print float_print.c

You must run give before Monday 04 October 21:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 4 Monday 21:00:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1521 classrun -sturec