• CS220@JHU
• Syllabus
• Staff
• CA Office Hours
• Course Material
• Schedule
• Resources

Exercise 15

Part 1

Pull the starter code for this exercise from the public repo by taking the following steps:

1. Log into an ugraduated cluster computer. Update your copy of the course public repo with a git pull command.

2. Confirm that you can see the template files for today’s exercise by typing ls exercises/ex15 — you should see the files endian.c, interp.c and random.c.

3. Navigate to your personal repo for the course and make a directory for today’s exercise. Copy all of the C source files (*.c) from the public class repository (in the /exercises/ex15/ directory) to your personal repo’s directory for this exercise.

Part 2

Compile and run the endian.c program using the following commands:

gcc -g -o endian -Wall -Wextra -pedantic -std=c99 endian.c
./endian

In its initial form, this program will print the size in bytes of several integer data types. You can interpret the size of each data type as being the number of bytes required to store one value belonging to the data type. For example, if sizeof(int) is 4, that means that 4 bytes are needed to store one instance of the int data type. This makes a lot of sense if one byte stores 8 bits, and int is a 32-bit type.

Now that we know that instances of the various integer data types require multiple bytes of memory to represent, an important question to ask is: “how are the bytes of an integer value stored in memory”? Two typical approaches are called little endian and big endian. On a big endian computer, the most significant byte of a multi-byte data value is stored in memory before the less-significant bytes. In contrast, on a little endian computer, the least significant byte of a multi-byte data value is stored in memory before the more-significant bytes.

Uncomment the code labeled as “uncomment this part”. The variable called val contains the value 950238851, which in hexadecimal is 38A37E83. That means that the bytes making up this value, from most significant to least signnificant, are

38 A3 7E 83 

Recompile the program, then run it in gdb using the command

gdb endian

Set a breakpoint at the beginning of the main function using the command break main. Run the program in gdb using the run command. Use the next command until gdb is at the final printf command of the program. The pointer p points to the memory location which stores the value of the val variable. Run the following commands in gdb:

print/x ((unsigned char *)p)[0]
print/x ((unsigned char *)p)[1]
print/x ((unsigned char *)p)[2]
print/x ((unsigned char *)p)[3]

These gdb commands will do the following:

• type cast the pointer to p to the type “pointer to unsigned char”
• access the 4 byte values in memory starting at the address that p points to
• prints each byte value in hexadecimal (“print/x” means “print in hexadecimal”)

These gdb commands are a good illustration of how gdb can inspect arbitrary memory locations as your program runs, and let you know exactly what is stored at those locations. gdb is extremely cool!

Based on your investigation, is the computer you are running the endian program on big endian or little endian?

Part 3

In the source file interp.c, implement the int_magnitude function. It receives an unsigned int value as an argument, which it should interpret as being a 32-bit two’s complement signed integer value. It should return an unsigned int value representing the magnitude of the argument value. In other words, it returns the absolute value of the integer if it were signed. A trivial implementation of the magnitude function would look like this:

unsigned int magnitude(unsigned int val) {
  int signed_val = (int) val;
  if (signed_val < 0) {
    val = -signed_val;
  }
  return val;
}

Using your knowledge of two’s complement representation and bitwise operators, implement the magnitude function without using any signed values. In other words, don’t use any values belonging to the int data type, or any other signed data type.

Here is a suggested approach using bit operations:

• If the highest bit of val is not set to 1, then just return the value as-is
• If the highest bit of val is set to 1, then its magnitude can be found by subtracting the value of the bits other than the highest bit from the unsigned int value numerically equal to INT_MAX plus 1
• Hexadecimal value 0x80000000u represents an unsigned integer with only the left-most (highest) bit set to one, so 0x7FFFFFFFu represents an unsigned integer with all except the left-most bit set to one.

Compile the program using the command

gcc -g -o interp -Wall -Wextra -pedantic -std=c99 interp.c

Run the program using the command ./interp. You will know if your implementation is correct if you can run the program, and all of the assert statements in the main function succeed.

Part 4

1. Random numbers are only as good as the seed that is used to initialize the pseudo-random generator. In the source file random.c, add a statement to call the set_seed function at TODO (1) so that the seed value input by the user is used for the initialization. Also, implement the set_seed function (TODO (2)) so that it calls srand with the seed value as the argument.

2. One important property of the rand function is that it generates a uniform distribution of pseudo-random integer values.

In the source file random.c, add a definition for the gen_uniform function as indicated by the TODO (3) comment. The gen_uniform function should return a pseudo-random integer in the range 0 to max_num-1, inclusive, uniformly distributed.

Next, as indicated by the TODO (4) comment in the main function, add code to generate 500 uniformly-generated pseudo-random integers and increment the elements of the hist array accordingly. (Each generated pseudo-random integer should be used to increment the hist array element with the same index as the generated pseudo-random integer.)

Compile the program:

gcc -g -o random -Wall -Wextra -pedantic -std=c99 random.c

Run the program using the command ./random with input values 10, 30. The output should look something like the following:

Uniform distribution:
 0: ****************
 1: ****************
 2: ******************
 3: *****************
 4: ************
 5: ***************
 6: *****************
 7: ************
 8: ***********************
 9: **********************
10: ****************
11: *************
12: ******************
13: *******************
14: *****************************
15: *************
16: ********************
17: *****************
18: ********************
19: **************
20: *******************
21: **************
22: ***************
23: ***********
24: ***********
25: **************
26: *****************
27: ***************
28: ***********
29: **************************

The output of print_hist should show that each element of the hist array values that are similar to each other. This is what we expect from a normal distribution.

3. A normal distribution of pseudo-random integers can be generated by summing multiple uniformly-distributed pseudo-random integer values.

In random.c add a definition for the normal_rand function, as indicated by the TODO (5) comment. This function should generate values according to a normal distribution (refer to the comment for details). The normal_rand function should return a pseudo-random integer in the range 0 to max_num-1, inclusive, normally distributed.

Then, as indicated by the TODO (5) comment in the main function, add code to generate 500 normally-generated pseudo-random integers and increment the elements of the hist array accordingly. (Each generated pseudo-random integer should be used to increment the hist array element with the same index as the generated pseudo-random integer.)

Compile and run the program. The output should look something like the following:

Normal distribution:
 0: 
 1: *
 2: 
 3: *
 4: *
 5: 
 6: *
 7: *********
 8: ********************
 9: **********************
10: ********************
11: ********************************
12: *************************************
13: *********************************
14: *********************************************
15: ***********************************************
16: ***********************************************
17: ************************************************
18: ****************************************
19: ******************************
20: ***************
21: ****************
22: *************
23: ***********
24: *****
25: *
26: ***
27: **
28: 
29: 

Your program’s output doesn’t need to look exactly like the output shown above, but it should show a “bell curve” centered at approximately the middle of the array of counts.

You may need to experiment a bit to find a good way to generate a more-or-less normal distribution.