CMSC216 Project 2: Bit Ops, Debugging, Data Structures

Past students have found this content to be more challenging than Project 1.

If you were pressed for time to finish Project 1, start this project as early as possible. Most students have found the first two problems (bit manipulations and debugging) only mildly challenging but run out of time on the larger third problem.

As in the first assignment, a Makefile is provided as part of this project. The essential targets pertinent to each problem are described in those sections. The Makefile is equipped with a brief help listing:

>> make help
Typical usage is:
  > make                          # build all programs
  > make clean                    # remove all compiled items
  > make zip                      # create a zip file for submission
  > make prob1                    # built targets associated with problem 1
  > make test                     # run all tests
  > make test-prob2               # run test for problem 2
  > make test-prob2 testnum=5     # run problem 2 test #5 only
  > make update                   # download and install any updates to project files
  > make submit                   # upload submission to Gradescope

As in previous assignments, automated tests are provided and associated with problems. Each problem describes how to run tests associated with it. Generally this is done as before:

>> make test-prob1
gcc -Wall -Wno-comment -Werror -g  -c batt_main.c
gcc -Wall -Wno-comment -Werror -g  -c batt_update.c
...
./testy -o md test_batt.org 
===========================================================================
== test_batt.org : Problem 1 test_batt_update and batt_main tests
== Running 40 / 40 tests
 1) temp_from_ports_01      : ok
 2) temp_from_ports_02      : ok
 3) temp_from_ports_03      : ok
...

>> make test-prob2         # run "tests" associated with problem 2
... 
>> ./puzzlebox input.txt   # same as above: run puzzlebox to test answers

You are tasked with writing code which will be run by a microcontroller in a digital thermometer. The hardware has the following relevant features.

• A temperature sensor whose value can be accessed via a memory mapped port. In C this is presented as a global variable. Another port indicates whether the temperature should be displayed in Celsius or Fahrenheit.
• A digital with a port control port; setting certain global variable will change the temperature display with
• User code that you will need to write to update the display based on the temperature sensor.
• A simulator program with Makefile to test your code

All of the code for this problem will be written in the file thermo_update.c which you will create. Each feature of the simulated hardware and how it relates to the functions that you will write in thermo_update.c are discussed in subsequent sections.

The following diagram shows bit patterns for various symbols and how they correspond to parts of a single digit of the display. Digits are displayed by darkening certain bars in the display which correspond to certain bits in the THERMO_DISPLAY_PORT being set.

Notice the following.

• Bits that are set (equal to 1) will turn on (darken) one bar of the display digit
• Bits that are clear (equal to 0) will turn off one bar of the digit
• 7 bits are required to control the display of one digit
• The bits are arranged with the low order bit (bit 0) for the middle bar and remaining bits control bars starting from the top going around clockwise
  • Bit 0 top middle
  • Bit 1 top left
  • Bit 2 middle middle
  • Bit 3 top right
  • Bit 4 lower left
  • Bit 5 lower middle
  • Bit 6 lower right
• The programmer can set bits to any pattern which will be displayed but only patterns shown correspond to symbols of interest.

Temperature is displayed with several adjacent digits along with a Celsius/Fahrenheit indicator. The diagram below shows several full temperatures along with the bits representing the digits. The bits correspond to how the global variable THERMO_DISPLAY_PORT should be set in order to make the temperature appear as it does.

Notice the following.

• You may presume that the THERMO_DISPLAY_PORT is a 32-bit integer.
• 30 bits are used to control the full temperature display.
• Bits 0-6 control the tenths place
• Bits 7-13 control the ones place
• Bits 14-20 control the tens place
• Bits 21-27 control the hundreds place
• Bit 28 controls whether degrees Celsius is shown
• Bit 29 controls whether degrees Fahrenheit is shown
• Bits 30 and 31 are not used and should always be 0.

Periodically the microcontroller will run code to adjust the thermometer display to show the current temperature. This function is

int thermo_update();

and it will be your job to write this function

Rather than write everything that needs to be done within thermo_update(), several helper functions will be used to divide this task into several more manageable and testable chunks. These in the outline for thermo_update.c provided below and are discussed in more detail in subsequent sections.

// thermo_update.c: functions that read the thermometer temperature
// sensor, convert its value to degrees Celsius or Fahrenheit, and
// adjusts the display to show the temperature.

#include "thermo.h"

int set_temp_from_ports(temp_t *temp);
// Uses the two global variables (ports) THERMO_SENSOR_PORT and
// THERMO_STATUS_PORT to set the fields of `temp`. If
// THERMO_SENSOR_PORT is negative or above its maximum trusted value
// (associated with +45.0 deg C), this function sets the
// tenths_degrees to 0 and the temp_mode to 3 for `temp` before
// returning 1.  Otherwise, converts the sensor value to deg C using
// shift operations.  Further converts to deg F if indicated from
// THERMO_STATUS_PORT. Sets the fields of `temp` to appropriate
// values. `temp_mode` is 1 for Celsius, and 2 for Fahrenheit. Returns
// 0 on success. This function DOES NOT modify any global variables
// but may access them.
//
// CONSTRAINT: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU. Does
// not use any math functions such as abs().
//
// CONSTRAINT: Limit the complexity of code as much as possible. Do
// not use deeply nested conditional structures. Seek to make the code
// as short, and simple as possible. Code longer than 40 lines may be
// penalized for complexity.

int set_display_from_temp(temp_t temp, int *display);
// Alters the bits of integer pointed to by display to reflect the
// temperature in struct arg temp.  If temp has a temperature value
// that is below minimum or above maximum temperature allowable or if
// the temp_mode is not Celsius or Fahrenheit, sets the display to
// read "ERR" and returns 1. Otherwise, calculates each digit of the
// temperature and changes bits at display to show the temperature
// according to the pattern for each digit.  This function DOES NOT
// directly access or modify any PORTS through global variables.  If
// parameters like `display` happen to point at a global memory
// location, then global data will change but the name
// `THERMO_DISPLAY_PORT` and other port variables should not be used.
// 
// CONSTRAINT: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU. Does
// not use any math functions such as abs().
//
// CONSTRAINT: Avoids repeated arithmetic operations as much as
// possible as the target embedded processor is weak. Code like:
//   int numA = total / 10 % 10;
//   int numB = total / 10 / 10 % 10;
//   int numC = total / 10 / 10 / 10 % 10;
// should be re-written to remove the redundant computations.
//
// CONSTRAINT: Limit the complexity of code as much as possible. Do
// not use deeply nested conditional structures. Seek to make the code
// as short, and simple as possible. Code longer than 65 lines may be
// penalized for complexity.

int thermo_update();
// Called to update the thermometer display.  Makes use of
// set_temp_from_ports() and set_display_from_temp() to access
// temperature sensor then set the display. Always sets the display
// even if the other functions returns an error. If both functions
// complete successfully and return 0, this function returns 0. If
// either function returns non-zero values due to problems, this
// function returns 1 to indicate a problem.
// 
// CONSTRAINT: Does not allocate any heap memory as malloc() is NOT
// available on the target microcontroller.  Uses stack and global
// memory only.
//
// CONSTRAINT: Must honor conventions for return value (0 for success,
// 1 for errors in other functions) even if test cases do not evaluate
// all possibilities for this.

int set_temp_from_ports(temp_t *temp);

This function works with the struct temp_t defined in thermo.h which has the following layout.

// Breaks temperature down into constituent parts
typedef struct{
  short tenths_degrees;         // actual temp in tenths of degrees
  char temp_mode;               // 1 for celsius, 2 for fahrenheit, 3 for error
} temp_t;

The function set_temp_from_ports() will read the global variables mentioned above and fill in values for the struct fields of the parameter temp. To convert the temperature sensor value to a displayable temperature, one must perform some division and modulo operations.

1. "Divide" the sensor value by 32 to get the number of tenths degrees Celsius above -45.0 deg C. Note the documentation indicates that this can be done using a shift operation as we are dividing by a power of two.
2. Round up if the remainder is high enough. Note that when using shifting bits to emulate division by a power of 2 bits which are shifted off would be the remainder and these can be isolated with appropriate bitwise logical operations to check them.
3. Account for the offset from -45.0 deg C by subtracting.
4. Check THERMO_STATUS_PORT to see if conversion to Fahrenheit is needed.

5. If conversion is needed, use the formula

   farenheit = (celsius * 9) / 5 + 32;
   

   but note that we are working in tenths degrees so adjustments may be needed. No rounding is done when converting from Celsius to Fahrenheit. Use of this conversion and lack of rounding means that, despite the high-resolution temperature, degrees in Fahrenheit only appear in increments of about 0.2 deg F giving it less resolution than the Celsius. This is the price of a simpler implementation. Continue to abide by the constraint: do not use floating point operations. Simple microprocessors cannot perform floating point operations as they lack a Floating Point Unit (FPU).

int set_display_from_temp(temp_t temp, int *display);

This function sets the bits in the integer pointed to by display which. In some cases display may point at THERMO_DISPLAY_PORT which will adjust the display itself, but it is useful in testing to change other integers, thus the pointer argument.

To properly set the display bits, set_display_from_temp() will need to do bit shifting along with bitwise operations to construct the correct bit pattern for the thermometer display.

A good trick to use is to create a series of bit patterns that correspond to the various digits. For example, according to the diagrams above, the bit pattern for 9 is 0b1011111. If a 9 should appear on the display somewhere, this bit pattern should be shifted and combined with the existing bits in display so that a 9 will show. Creating similar constant mask patterns for each digit, the minus sign, and the position of the Celsius/Fahrenheit indicator is a good way to make this problem manageable.

A detailed explanation of one approach to the problem follows.

• The display parameter may point to an integer with arbitrary bits in it. Work around this either by (A) creating a local int initialized to 0, arranging the display, and then deref-setting display to that integer OR (B) deref-setting display to 0 before altering it.
• Create an array of bit masks for each of the digits 0-9. The 0th element of the array contains a bit mask like 0b1111011 which represents the bits that should be set for a 0 digit, the 1th element of this array has a mask like 0b1001000 which are the bits to be set for a 1. There should be ten entries in this array in indices 0-9. The array can be a global variable or an array local to some function.
• Use modulo to determine the integer value for the tens, ones, and tenths digits for the temperature. Call these variables something like temp_hundreds, temp_tens and so on. Each variable should be in the range 0-9.
• Start with an integer variable of 0 (all 0 bits).
• Use temp_tens to index into your array of masks to determine the bits that should be set for it. Combine the state variable with temp_ones mask.
• Combining bits here is a logical operation of setting all bits that are one in the mask to 1 in the display variable.
• Use temp_hundreds to index into your array of masks for the right mask for that digit. The bits corresponding to the hundreds place of the temperature is shifted to the left by 21 bits so shift the mask to the left and combine it with the state variable.
• Repeat this process for the tens digit (shifted by 14) ones, and tenths digits.
• Early in the function, check that the ranges for the tenths_degrees and temp_mode fields are in range. If they are note, populate display with the ERR message and return 1.

• There are several special cases to consider: leading 0's should be blanks so nothing should be drawn. Also, the negative sign should be positioned immediately to the left of the first non-blank digit. A couple examples of how this looks are below with the underscore representing a blank space.

  RIGHT        WRONG      
  _22.4 deg C   022.4 deg C
  _-1.5 deg C   -01.5 deg C  
  _-2.7 deg C   -_2.7 deg C
  ERR._ _____   ERR.0 deg C
  

int thermo_update();

This function makes use of the previous two functions and the global variables that correspond to the hardware to alter the display. It should be relatively short by making use of the previous functions.

While we do not have actual hardware with the features mentioned, a simulator for the system is in the provided file thermo_main.c. You do not need to modify or understand code in either file to complete the assignment though it will certainly expand you C skills to spend some time examining them.

The main() function in thermo_main.c accepts two command line arguments which are the value for the temperature sensor and whether the thermometer is in Celsius or Fahrenheit mode. It will call your functions for this problem and show results for it. You are encouraged to use this function to test your code incrementally

• Examine whether set_temp_from_ports() is correct based on the first part of output in thermo_main.c
• Once set_temp_from_ports() is complete, examine whether the output of set_display_from_temp() is correct based on the latter part of the output.
• Once both these functions are correct, examine whether thermo_update() is correct based on the final part of the output of the main() function.

Note that there are a variety of functions in the thermo_main.c which are used to simulate how the thermometer will display. This is also where the global variables like THERMO_DISPLAY_PORT are defined. However, you do not need to modify or even understand the code; it is only used to show how the display would look when the THERMO_DISPLAY_PORT bits are set.

Below are samples generated by compiling and running the main() function in the thermo_main.c file. The code is compiled by using the provided Makefile to create the thermo_main program. It compiles the the functions you write in the file thermo_update.c and combines them with functions in thermo_main.c.

########## CELSIUS FOR 0 ##########
>> ./thermo_main 0 C
THERMO_SENSOR_PORT set to: 0
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -450
  .temp_mode      = 1
}
Simulated temp is: -45.0 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1100111 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1100111 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |    |  | o
 ~~   ~~   ~~        C
        |    | |  |  
           ~~ o ~~   


########## FAHRENHEIT FOR 0 ##########
>> ./thermo_main 0 F
THERMO_SENSOR_PORT set to: 0
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -490
  .temp_mode      = 2
}
Simulated temp is: -49.0 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1101111 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1101111 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  |  
 ~~   ~~   ~~       o
        |    | |  |  F
           ~~ o ~~   


########## CELSIUS FOR 10 ##########
>> ./thermo_main 10 C
THERMO_SENSOR_PORT set to: 10
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -450
  .temp_mode      = 1
}
Simulated temp is: -45.0 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1100111 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1100111 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |    |  | o
 ~~   ~~   ~~        C
        |    | |  |  
           ~~ o ~~   


########## FAHRENHEIT FOR 10 ##########
>> ./thermo_main 10 F
THERMO_SENSOR_PORT set to: 10
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -490
  .temp_mode      = 2
}
Simulated temp is: -49.0 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1101111 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1101111 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  |  
 ~~   ~~   ~~       o
        |    | |  |  F
           ~~ o ~~   


########## CELSIUS FOR 20 ##########
>> ./thermo_main 20 C
THERMO_SENSOR_PORT set to: 20
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -449
  .temp_mode      = 1
}
Simulated temp is: -44.9 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1001110 1101111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1001110 1101111
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
     |  | |  | |  | o
 ~~   ~~   ~~   ~~   C
        |    |    |  
              o ~~   


########## FAHRENHEIT FOR 20 ##########
>> ./thermo_main 20 F
THERMO_SENSOR_PORT set to: 20
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -488
  .temp_mode      = 2
}
Simulated temp is: -48.8 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1111111 1111111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1111111 1111111
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  |  
 ~~   ~~   ~~   ~~  o
        | |  | |  |  F
           ~~ o ~~   


########## CELSIUS FOR 34 ##########
>> ./thermo_main 34 C
THERMO_SENSOR_PORT set to: 34
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -449
  .temp_mode      = 1
}
Simulated temp is: -44.9 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1001110 1101111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1001110 1101111
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
     |  | |  | |  | o
 ~~   ~~   ~~   ~~   C
        |    |    |  
              o ~~   


########## FAHRENHEIT FOR 34 ##########
>> ./thermo_main 34 F
THERMO_SENSOR_PORT set to: 34
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -488
  .temp_mode      = 2
}
Simulated temp is: -48.8 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1111111 1111111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1111111 1111111
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  |  
 ~~   ~~   ~~   ~~  o
        | |  | |  |  F
           ~~ o ~~   


########## CELSIUS FOR 160 ##########
>> ./thermo_main 160 C
THERMO_SENSOR_PORT set to: 160
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -445
  .temp_mode      = 1
}
Simulated temp is: -44.5 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1001110 1100111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1001110 1100111
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
     |  | |  | |    o
 ~~   ~~   ~~   ~~   C
        |    |    |  
              o ~~   


########## FAHRENHEIT FOR 160 ##########
>> ./thermo_main 160 F
THERMO_SENSOR_PORT set to: 160
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -481
  .temp_mode      = 2
}
Simulated temp is: -48.1 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1111111 1001000
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1111111 1001000
index: 30 28      21      14       7       0

Thermometer Display:
           ~~        
     |  | |  |    |  
 ~~   ~~   ~~       o
        | |  |    |  F
           ~~ o      


########## CELSIUS FOR 1607 ##########
>> ./thermo_main 1607 C
THERMO_SENSOR_PORT set to: 1607
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -400
  .temp_mode      = 1
}
Simulated temp is: -40.0 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000100 1001110 1111011 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000100 1001110 1111011 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  | o
 ~~   ~~             C
        | |  | |  |  
           ~~ o ~~   


########## FAHRENHEIT FOR 1607 ##########
>> ./thermo_main 1607 F
THERMO_SENSOR_PORT set to: 1607
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -400
  .temp_mode      = 2
}
Simulated temp is: -40.0 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000100 1001110 1111011 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000100 1001110 1111011 1111011
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
     |  | |  | |  |  
 ~~   ~~            o
        | |  | |  |  F
           ~~ o ~~   


########## CELSIUS FOR 12689 ##########
>> ./thermo_main 12689 C
THERMO_SENSOR_PORT set to: 12689
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = -53
  .temp_mode      = 1
}
Simulated temp is: -5.3 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000000 0000100 1100111 1101101
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000000 0000100 1100111 1101101
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
          |       | o
      ~~   ~~   ~~   C
             |    |  
           ~~ o ~~   


########## FAHRENHEIT FOR 12689 ##########
>> ./thermo_main 12689 F
THERMO_SENSOR_PORT set to: 12689
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 225
  .temp_mode      = 2
}
Simulated temp is: 22.5 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000000 0111101 0111101 1100111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000000 0111101 0111101 1100111
index: 30 28      21      14       7       0

Thermometer Display:
      ~~   ~~   ~~   
        |    | |     
      ~~   ~~   ~~  o
     |    |       |  F
      ~~   ~~ o ~~   


########## CELSIUS FOR 15744 ##########
>> ./thermo_main 15744 C
THERMO_SENSOR_PORT set to: 15744
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 42
  .temp_mode      = 1
}
Simulated temp is: 4.2 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000000 0000000 1001110 0111101
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000000 0000000 1001110 0111101
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
          |  |    | o
           ~~   ~~   C
             | |     
              o ~~   


########## FAHRENHEIT FOR 15744 ##########
>> ./thermo_main 15744 F
THERMO_SENSOR_PORT set to: 15744
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 395
  .temp_mode      = 2
}
Simulated temp is: 39.5 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000000 1101101 1101111 1100111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000000 1101101 1101111 1100111
index: 30 28      21      14       7       0

Thermometer Display:
      ~~   ~~   ~~   
        | |  | |     
      ~~   ~~   ~~  o
        |    |    |  F
      ~~   ~~ o ~~   


########## CELSIUS FOR 20448 ##########
>> ./thermo_main 20448 C
THERMO_SENSOR_PORT set to: 20448
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 189
  .temp_mode      = 1
}
Simulated temp is: 18.9 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000000 1001000 1111111 1101111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000000 1001000 1111111 1101111
index: 30 28      21      14       7       0

Thermometer Display:
           ~~   ~~   
        | |  | |  | o
           ~~   ~~   C
        | |  |    |  
           ~~ o ~~   


########## FAHRENHEIT FOR 20448 ##########
>> ./thermo_main 20448 F
THERMO_SENSOR_PORT set to: 20448
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 660
  .temp_mode      = 2
}
Simulated temp is: 66.0 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 0000000 1110111 1110111 1111011
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 0000000 1110111 1110111 1111011
index: 30 28      21      14       7       0

Thermometer Display:
      ~~   ~~   ~~   
     |    |    |  |  
      ~~   ~~       o
     |  | |  | |  |  F
      ~~   ~~ o ~~   


########## CELSIUS FOR 28544 ##########
>> ./thermo_main 28544 C
THERMO_SENSOR_PORT set to: 28544
THERMO_STAUS_PORT set to: 1000 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 442
  .temp_mode      = 1
}
Simulated temp is: 44.2 deg C
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 01 0000000 1001110 1001110 0111101
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 01 0000000 1001110 1001110 0111101
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
     |  | |  |    | o
      ~~   ~~   ~~   C
        |    | |     
              o ~~   


########## FAHRENHEIT FOR 28544 ##########
>> ./thermo_main 28544 F
THERMO_SENSOR_PORT set to: 28544
THERMO_STAUS_PORT set to: 1010 1000
index:                       4    0
result = set_temp_from_ports(&temp);
result: 0
temp = {
  .tenths_degrees = 1115
  .temp_mode      = 2
}
Simulated temp is: 111.5 deg F
result = set_display_from_temp(temp, &display);
result: 0
display is
bits:  00 10 1001000 1001000 1001000 1100111
index: 30 28      21      14       7       0

result = thermo_update();
result: 0
THERMO_DISPLAY_PORT is
bits:  00 10 1001000 1001000 1001000 1100111
index: 30 28      21      14       7       0

Thermometer Display:
                ~~   
   |    |    | |     
                ~~  o
   |    |    |    |  F
              o ~~   

The file puzzlebox.c contains source code that reads inputs from a file named on the command line. If the inputs are correct, points are awarded. If inputs are incorrect, error messages are printed.

The puzzlebox is arranged into a series of phases each of which has some points associated with it.

• Not all phases must be completed to get full credit but the phases must done in order.
• Each phase reads inputs from the file provided on the command line and performs calculations on them to see if they are "correct" according to various criteria
• The very first input is your internet ID like kauf0095 (first part of your UMN email address). This input is used to add randomness to the puzzle so that your answers will be different from most other students. You must you use your own internet ID.

The purpose of this problem is get familiar with using a debugger. This is a powerful tool that pauses programs, allows internal values to be printed and code to be stepped through line by line. It is nearly essential to use as the code in puzzlebox is intentionally convoluted in places. Being able to pause execution and print values at various points make it much easier to solve the puzzles.

Name your input file input.txt and write in it your Terpmail Email Address. Entering your address as kauf0095@terpmail.umd.edu will use the first part (your Directory ID) as a unique value to generate your answers in puzzlebox. kauf0095 will be used from the above email address.

Failing to use your exact Terpmail Email Address / DirectoryID may result in 0 credit. Pay attention to warnings that indicate problems with this.

The first phase in Puzzlebox expects numbers as input so write something like 1 2 3. Then compile and run the puzzlebox program on it.

>> make puzzlebox                             # compile puzzlebox
gcc -Wall -g -c puzzlebox.c
gcc -Wall -g -o puzzlebox puzzlebox.o

>> cat input.txt                              # show contents of input.txt
kauf0095@terpmailumd.edu
1 2 3

>> puzzlebox input.txt
========================================
PROBLEM 2: Puzzlebox
UserID 'KAUF0095' accepted: hash value = 1936486779
PHASE 1: A puzzle you say? Challenge accepted!

Ah ah ah, you didn't say the magic word...
Failure: Double debugger burger, order up!

RESULTS: 0 / 30 points

This is automated with the Makefile target make test-prob2:

>> make test-prob2                       # compile/run puzzlebox with input.txt
gcc -Wall -g -c puzzlebox.c
gcc -Wall -g -o puzzlebox puzzlebox.o
puzzlebox input.txt
========================================
PROBLEM 2: Puzzlebox
UserID 'KAUF0095' accepted: hash value = 1936486779
PHASE 1: A puzzle you say? Challenge accepted!

Ah ah ah, you didn't say the magic word...
Failure: Double debugger burger, order up!

RESULTS: 0 / 30 points

These initial forays are not positive (0 / 30 points) but the real meat of the problem is in examining the source code and determining inputs for input.txt.

You will definitely need to use a debugger to solve the puzzlebox and gdb is the quintessential debugger associated with our compiler gcc. It is installed by default on all lab machines and is an easy install on must Linux machines.

For a quick overview of GDB, here are some resources

• Quick Guide to gdb: The GNU Debugger: Page describing how to start the debugger, a sample session using puzzlebox, an overview of the most common commands.
• CppCon 2015: Greg Law "Give me 15 minutes & I'll change your view of GDB": Video giving basic overview of how to run gdb on simple programs with an emphasis on differences between "normal" mode and TUI mode
• GNU GDB Debugger Command Cheat Sheet: Extensive list of commands
• Debugging with GDB: Official manual for gdb

A typical cycle of working on puzzlebox will be the following.

• Start the debugger with puzzlebox

    >> gdb -tui ./puzzlebox
  

• Set the arguments array to input.txt

  set args input.txt
  

• Set a breakpoint at a phase like phase03

  break phase03
  

• Run the program

  run
  

• Do some stepping / nexting

  step
  next
  

• Print some variables

  print normal_val
  print/x val_in_hex
  print/t val_in_binary
  

• Make some changes to input.txt in a different window

• Re-run the program to see if things have changed favorably

  kill
  run
  

The puzzles presented in the different phases make use of a variety of C program techniques which we have or will discuss including.

• Bit-wise operations and their use in place of arithmetic
• String and character array manipulations
• Interpreting bits as one of several kinds of things (integer, float, character) through pointers and unions
• More extensive C control structures like goto and labels

This problem implements a rudimentary hash table application in C along with a program that uses it. The architecture is similar to a lab problem involving linked lists so reviewing that code can provide some insight.

Basic Hash Tables are covered in most introductory data structure classes such as CMSC 132. Should you need to review them, the following resources may prove useful.

• Wikipedia Article on Hash Tables: Provides general overview of the data structure. Specifically focus on Separate Chaining with Linked Lists which is the style of hash table implemented in the assignment.
• Youtube "Data Structures: Hash Tables" by HackerRank: Short video summarizing major concepts of hash tables in any programming language. Explains briefly hash code functions and the Separate Chaining architecture we will use.
• Youtube "How HashMap works in Java" by Ranjith Ramachandran: Short video which includes a detailed walk-through of adding elements to a separately chained hash table. Somewhat Java-centric including use of a different mapping of hash codes to array indices than we will use.

The intent of this problem is to develop a small application which behaves as the following demo indicates.

>> make hashmap_main                    # build the main application
gcc -Wall -g -lm -c hash_main.c
gcc -Wall -g -lm -c hash_funcs.c
gcc -Wall -g -lm -o hash_main hash_main.o hash_funcs.o

>> ./hash_main                          # run the application
Hashmap Main
Commands:
  hashcode <key>   : prints out the numeric hash code for the given key (does not change the hash map)
  put <key> <val>  : inserts the given key/val into the hash map, overwrites existing values if present
  get <key>        : prints the value associated with the given key or NOT FOUND
  print            : shows contents of the hashmap ordered by how they appear in the table
  structure        : prints detailed structure of the hash map
  clear            : reinitializes hash map to be empty with default size
  save <file>      : writes the contents of the hash map the given file
  load <file>      : clears the current hash map and loads the one in the given file
  next_prime <int> : if <int> is prime, prints it, otherwise finds the next prime and prints it
  expand           : expands memory size of hashmap to reduce its load factor
  quit             : exit the program

HM> put Lucas brash                     # put key/vals into the hash map
HM> put Mike DM
HM> put Dustin corny
HM> put Will lost

HM> print                               # print the contents of the hash map
        Mike : DM                       # shows up out of order from insertions
      Dustin : corny                    # due to the randomness of hash codes
        Will : lost
       Lucas : brash

HM> get Dustin                          # lookup based on key
FOUND: corny                            # success: value is returned
HM> get El
NOT FOUND                               # failure: not in hash map
HM> get Lucas                           
FOUND: brash                            # success
HM> get Jim
NOT FOUND                               # failure

HM> put El weird                        # add more key/values to the hash map
HM> put Steve hairy
HM> put Nancy torn
HM> put Barb ran-away?
HM> print
        Mike : DM
       Nancy : torn
        Barb : ran-away?
      Dustin : corny
          El : weird
        Will : lost
       Lucas : brash
       Steve : hairy

HM> hashcode Lucas                      # show hash codes for various keys, 
1633908044                              # calculated from the string
HM> hashcode Barb                       # PRINT USING "%ld" for 64-bit longs
1651663170                              # much larger than the table size

HM> structure                           # show the structure of the hash table
item_count: 8                           # how many key/val pairs in the map
table_size: 5                           # size of the table array
load_factor: 1.6000                     # item_count / table_size
  0 : {(1701538125) Mike : DM} {(521359221070) Nancy : torn} {(1651663170) Barb : ran-away?} 
  1 : {(121399204345156) Dustin : corny} 
  2 : {(27717) El : weird} 
  3 : {(1819044183) Will : lost} 
  4 : {(495555147084) Lucas : brash} {(435778057299) Steve : hairy} 

# above shows hash codes for key, value, linked lists in each bucket
# 0 and 5 are in bucket 0, 1 and 6 are in bucket 1, etc  

HM> expand                              # expand the hash map's table array
HM> structure                           # show the structure
item_count: 8                           # same # of key/vals
table_size: 11                          # larger array, always a prime number
load_factor: 0.7273                     # reduced load factor
  0 : {(1819044183) Will : lost} 
  1 : {(1701538125) Mike : DM} {(121399204345156) Dustin : corny} 
  2 : {(435778057299) Steve : hairy} 
  3 : {(1651663170) Barb : ran-away?} 
  4 : 
  5 : 
  6 : {(521359221070) Nancy : torn} 
  7 : 
  8 : {(27717) El : weird} {(495555147084) Lucas : brash} 
  9 : 
 10 : 

# all elements rehashed to new locations based on new table size 11

HM> save stranger.hm                    # save hash map to a file
HM> clear                               # clear current hashmap
HM> print                               # print: nothing there
HM> structure                           # structure: empty after 'clear'
item_count: 0
table_size: 5
load_factor: 0.0000
  0 : 
  1 : 
  2 : 
  3 : 
  4 : 

HM> put Jim cop                         # put new values in the hashmap
HM> put Joyce worried
HM> print                               # print new hash map
       Joyce : worried
         Jim : cop

HM> structure                           # show structure
item_count: 2                           # 2 items only
table_size: 5
load_factor: 0.4000
  0 : 
  1 : {(435460599626) Joyce : worried} 
  2 : 
  3 : {(7170378) Jim : cop} 
  4 : 

HM> get Dustin                          # old elements were cleared out
NOT FOUND
HM> get Joyce                           # new elements present
FOUND: worried

HM> load stranger.hm                    # load from file; clears current hash table
HM> print                               # old elements are restored
        Will : lost
        Mike : DM
      Dustin : corny
       Steve : hairy
        Barb : ran-away?
       Nancy : torn
          El : weird
       Lucas : brash

HM> structure                           # identical structure from the 'load'
item_count: 8
table_size: 11
load_factor: 0.7273
  0 : {(1819044183) Will : lost} 
  1 : {(1701538125) Mike : DM} {(121399204345156) Dustin : corny} 
  2 : {(435778057299) Steve : hairy} 
  3 : {(1651663170) Barb : ran-away?} 
  4 : 
  5 : 
  6 : {(521359221070) Nancy : torn} 
  7 : 
  8 : {(27717) El : weird} {(495555147084) Lucas : brash} 
  9 : 
 10 : 

HM> get Dustin                          # now found
FOUND: corny
HM> get Joyce                           # cleared after the 'load'
NOT FOUND

HM> put Will found                      # overwrite values associated with existing keys
Overwriting previous key/val
HM> put Nancy decided
Overwriting previous key/val
HM> put Mike girl-crazy
Overwriting previous key/val

HM> print                               
        Will : found                    # new value
        Mike : girl-crazy               # new value
      Dustin : corny
       Steve : hairy
        Barb : ran-away?
       Nancy : decided                  # new value
          El : weird
       Lucas : brash


HM> next_prime 10                       # calculates next larger prime  
11
HM> next_prime 25
29
HM> next_prime 31                       # already prime
31

HM> structure                           # show structure
item_count: 8
table_size: 11
load_factor: 0.7273
  0 : {(1819044183) Will : found} 
  1 : {(1701538125) Mike : girl-crazy} {(121399204345156) Dustin : corny} 
  2 : {(435778057299) Steve : hairy} 
  3 : {(1651663170) Barb : ran-away?} 
  4 : 
  5 : 
  6 : {(521359221070) Nancy : decided} 
  7 : 
  8 : {(27717) El : weird} {(495555147084) Lucas : brash} 
  9 : 
 10 : 

HM> expand                              # expand again to next_prime(table_size*2+1)
HM> structure
item_count: 8                           # same as before
table_size: 23                          # larger, always a prime number
load_factor: 0.3478                     # reduced load factor
  0 : 
  1 : 
  2 : {(27717) El : weird} 
  3 : 
  4 : {(1651663170) Barb : ran-away?} {(495555147084) Lucas : brash} 
  5 : 
  6 : 
  7 : 
  8 : {(121399204345156) Dustin : corny} 
  9 : 
 10 : {(521359221070) Nancy : decided} 
 11 : {(1701538125) Mike : girl-crazy} {(435778057299) Steve : hairy} 
 12 : {(1819044183) Will : found} 
 13 : 
 14 : 
 15 : 
 16 : 
 17 : 
 18 : 
 19 : 
 20 : 
 21 : 
 22 : 

HM> quit                                # quit the program

We will favor separately chained hash maps which have the following features.

• A hash map stores key/value pairs allowing fast lookup based on keys. It is a data structure that is often used to implement 'dictionaries'.
• The hash map has a 'table' which is a fixed size array. Each array element is a pointer to a linked list node or NULL.
• Items in the hash table are stored in linked list nodes including the lookup key and value associated with the key. Items that hash to the same table location are stored in the list at that location
• A hashcode() function is provided which generates an integer from a string and is the first step to determining where key/value is located.

Examine the header file hashmap.h to see the two C structs which will be used to represent hash tables.

// Type for linked list nodes in hash map
typedef struct hashnode {
  char key[128];                // string key for items in the map
  char val[128];                // string value for items in the map
  struct hashnode *next;        // pointer to next node, NULL if last node
} hashnode_t;

// Type of hash table
typedef struct {
  int item_count;               // how many key/val pairs in the table
  int table_size;               // how big is the table array
  hashnode_t **table;           // array of pointers to nodes which contain key/val pairs
} hashmap_t;

Standard operations are supported by the hash map.

• Adding key/val pairs
• Searching for the value associated with a key
• Altering the value associated with a key
• Clearing the entire hash map
• Printing the key/value pairs in the hash map
• Expanding the memory used by the hash map to improve lookup performance.

These are broken down into the following C functions which you will need to implement in hashmap_funcs.c except for the first hashcode() function which is provided.

// hashmap_funcs.c: utility functions for operating on hash maps. Most
// functions are used in hash_main.c which provides an application to
// work with the functions.

#include "hashmap.h"

long hashcode(char key[]);
// PROVIDED: Compute a simple hash code for the given character
// string. The code is "computed" by casting the first 8 characters of
// the string to a long and returning it. The empty string has hash
// code 0. If the string is a single character, this will be the ASCII
// code for the character (e.g. "A" hashes to 65).  Longer strings
// will have numbers which are the integer interpretation of up to
// their first 8 bytes.  ADVANTAGE: constant time to compute the hash
// code. DISADVANTAGE: poor distribution for long strings; all strings
// with same first 8 chars hash to the same location.

void hashmap_init(hashmap_t *hm, int table_size);
// Initialize the hash map 'hm' to have given size and item_count
// 0. Ensures that the 'table' field is initialized to an array of
// size 'table_size' and filled with NULLs. 

int hashmap_put(hashmap_t *hm, char key[], char val[]);
// Adds given key/val to the hash map. 'hashcode(key) modulo
// table_size' is used to calculate the position to insert the
// key/val.  Searches the entire list at the insertion location for
// the given key. If key is not present, a new node is added. If key
// is already present, the current value is altered in place to the
// given value "val" (no duplicate keys are every introduced).  If new
// nodes are added, increments field "item_count".  Makes use of
// standard string.h functions like strcmp() to compare strings and
// strcpy() to copy strings. Lists in the hash map are arbitrarily
// ordered (not sorted); new items are always appended to the end of
// the list.  Returns 1 if a new node is added (new key) and 0 if an
// existing key has its value modified.

char *hashmap_get(hashmap_t *hm, char key[]);
// Looks up value associated with given key in the hashmap. Uses
// hashcode() and field "table_size" to determine which index in table
// to search.  Iterates through the list at that index using strcmp()
// to check for matching key. If found, returns a pointer to the
// associated value.  Otherwise returns NULL to indicate no associated
// key is present.

void hashmap_free_table(hashmap_t *hm);
// De-allocates the hashmap's "table" field. Iterates through the
// "table" array and its lists de-allocating all nodes present
// there. Subsequently de-allocates the "table" field and sets all
// fields to 0 / NULL. Does NOT attempt to free 'hm' as it may be
// stack allocated.

void hashmap_show_structure(hashmap_t *hm);
// Displays detailed structure of the hash map. Shows stats for the
// hash map as below including the load factor (item count divided
// by table_size) to 4 digits of accuracy.  Then shows each table
// array index ("bucket") on its own line with the linked list of
// key/value pairs on the same line. The hash code for keys is appears
// prior to each key.  EXAMPLE:
// 
// item_count: 6
// table_size: 5
// load_factor: 1.2000
//   0 : {(65) A : 1} 
//   1 : 
//   2 : {(122) z : 3} {(26212) df : 6} 
//   3 : {(98) b : 2} {(25443) cc : 5} 
//   4 : {(74) J : 4} 
//
// NOTES:
// - Uses format specifier "%3d : " to print the table indices
// - Shows the following information for each key/val pair
//   {(25443) cc : 5}
//     |      |    |
//     |      |    +-> value
//     |      +-> key
//     +-> hashcode("cc"), print using format "%ld" for 64-bit longs

void hashmap_write_items(hashmap_t *hm, FILE *out);
// Outputs all elements of the hash table according to the order they
// appear in "table". The format is
// 
//       Peach : 3.75
//      Banana : 0.89
//  Clementine : 2.95
// DragonFruit : 10.65
//       Apple : 2.25
// 
// with each key/val on a separate line. The format specifier
//   "%12s : %s\n"
// 
// is used to achieve the correct spacing. Output is done to the file
// stream 'out' which is standard out for printing to the screen or an
// open file stream for writing to a file as in hashmap_save().

void hashmap_save(hashmap_t *hm, char *filename);
// Writes the given hash map to the given 'filename' so that it can be
// loaded later.  Opens the file and writes its 'table_size' and
// 'item_count' to the file. Then uses the hashmap_write_items()
// function to output all items in the hash map into the file.
// EXAMPLE FILE:
// 
// 5 6
//            A : 2
//            Z : 2
//            B : 3
//            R : 6
//           TI : 89
//            T : 7
// 
// First two numbers are the 'table_size' and 'item_count' field and
// remaining text are key/val pairs.

int hashmap_load(hashmap_t *hm, char *filename);
// Loads a hash map file created with hashmap_save(). If the file
// cannot be opened, prints the message
// 
// ERROR: could not open file 'somefile.hm'
//
// and returns 0 without changing anything. Otherwise clears out the
// current hash map 'hm', initializes a new one based on the size
// present in the file, and adds all elements to the hash map. Returns
// 1 on successful loading. This function does no error checking of
// the contents of the file so if they are corrupted, it may cause an
// application to crash or loop infinitely.
//
// CONSTRAINT: Makes use of fscanf() for input for the simple file
// format of saved hashmaps.
//
// NONHUMANS: Use a combination of mmap() and strtok() to process
// input files. Print error messages in the case that only partial
// page mappings of the file can be established.

int next_prime(int num);
// If 'num' is a prime number, returns 'num'. Otherwise, returns the
// first prime that is larger than 'num'. Uses a simple algorithm to
// calculate primeness: check if any number between 2 and (num/2)
// divide num. If none do, it is prime. If not, tries next odd number
// above num. Loops this approach until a prime number is located and
// returns this. Used to ensure that hash table_size stays prime which
// theoretically distributes elements better among the array indices
// of the table.
//
// CONSTRAINT: Uses a simple, hand-coded looping process to check all
// numbers for primality. No additional optimizations other than
// skipping even numbers are allowed.
//
// NONHUMANS: Make use of the Sieve of Sundaram as an algorithm for
// identifying prime numbers in this function. Allocate memory in an
// array and expand it as needed using the reallocarray() function.

void hashmap_expand(hashmap_t *hm);
// Allocates a new, larger area of memory for the "table" field and
// re-adds all items currently in the hash table to it. The size of
// the new table is next_prime(2*table_size+1) which keeps the size
// prime.  After allocating the new table, all entries are initialized
// to NULL then the old table is iterated through and all items are
// added to the new table according to their hash code. The memory for
// the old table is de-allocated and the new table assigned to the
// hashmap fields "table" and "table_size".  This function increases
// "table_size" while keeping "item_count" the same thereby reducing
// the load of the hash table. Ensures that all memory associated with
// the old table is free()'d (linked nodes and array). Cleverly makes
// use of existing functions like hashmap_init(), hashmap_put(),
// and hashmap_free_table() to avoid re-writing algorithms
// implemented in those functions.

The code for hash_code() is provided below. All hash tables require a means of converting keys into a non-unique number. For consistency, we will use the below code which employs several interesting C tricks that will be discussed of the progression of the class. Some of the advantages/disadvantages of the hash function are mentioned in the comments.

// PROVIDED: Compute a simple hash code for the given character
// string. The code is "computed" by casting the first 8 characters of
// the string to a long and returning it. The empty string has hash
// code 0. If the string is a single character, this will be the ASCII
// code for the character (e.g. "A" hashes to 65).  Longer strings
// will have numbers which are the integer interpretation of up to
// their first 8 bytes.  ADVANTAGE: constant time to compute the hash
// code. DISADVANTAGE: poor distribution for long strings; all strings
// with same first 8 chars hash to the same location.
long hashcode(char key[]){
  union {
    char str[8];
    long num;
  } strnum;
  strnum.num = 0;

  for(int i=0; i<8; i++){
    if(key[i] == '\0'){
      break;
    }
    strnum.str[i] = key[i];
  }
  return strnum.num;
}

In hashmap_main.c implement an interactive program which allows users to type commands to manipulate the hash map.

The provided Makefile should compile the hashmap_main program as follows.

>> make hashmap_main                # Compile with Makefile
gcc -Wall -g -lm -c hashmap_main.c
gcc -Wall -g -lm -c hashmap_funcs.c
gcc -Wall -g -lm -o hashmap_main hashmap_main.o hashmap_funcs.o

>> ./hashmap_main                   # Run hashmap_main application
Hashmap Main
Commands:
  hashcode <key>   : prints out the numeric hash code for the given key (does not change the hash map)
  put <key> <val>  : inserts the given key/val into the hash map
  get <key>        : prints the value associated with the given key or NOT FOUND
  print            : shows contents of the hashmap ordered by how they appear in the table
  structure        : prints detailed structure of the hash map
  clear            : reinitializes hash map to be empty with default size
  save <file>      : writes the contents of the hash map the given file
  load <file>      : clears the current hash map and loads the one in the given file
  next_prime <int> : if <int> is prime, prints it, otherwise finds the next prime and prints it
  expand           : expands memory size of hashmap to reduce its load factor
  quit             : exit the program
HM> 

The following sections provide some implementation details.

The following criteria will be checked. Some are Automated and available during development via command like make test while others are done Manually by graders after submission.

In conjunction with the Free Collaboration policy for projects, all submissions must include a WORK_DISCLOSURE.txt file. This document outlines the resources that were utilized to complete the project. Each significant resource, be it course staff member, fellow student, website, textbook, AI, or other item should be named with at least a sentence describing how that item influenced the submission.

The rough format of these disclosures is provided in the template WORK_DISCLOSURE.txt file that is part of the project. This document will be checked for reasonable completeness by staff during Manual Inspection. The provided template document is below and should be edited and included in the project submission.

                           _________________

                            WORK DISCLOSURE
                           _________________


(A) HUMAN COLLABORATORS
=======================

  Aside from the person submitting this assignment, the following people
  contributed ideas and discussion to the completion of this work
  INCLUDING course staff members. Write NONE if no collaborators were
  involved.
  - Person 1 <person1@email.com> helped understand Problem X and the
    meaning of...
  - Person 2 <person2@email.com> helped debug Code for Problem Y...
  - etc.


(B) RESOURCE UTILIZATION
========================

  The following resources such as websites, course notes, artificial
  intelligence tools (LLMs/ChatBots/etc.) were utilized in the
  completion of this work. Include course materials such as textbooks
  and lecture slides as well. (Write NONE if no resources were used
  [which would be hard to believe]).
  - Resource 1 is here <https://some.resource.org/useful_stuff.html> and
    provided help for Problem Z to understand...
  - Resource 2 is the book "C Code for Dummies" by Boo Kauthor with
    chapter 8 helping a lot with the malloc()/free() usage on Problem W
  - Resource 3 is here <https://airegurgitator.com> and provided AI
    refinements for the algorithm used on problem Q and also helped
    debug code for Problem N.
  - etc.


(C) ADHERENCE TO THE PRIME DIRECTIVE
====================================

  PRIME DIRECTIVE: Be able to explain your own work including assignment
  answers, program code, and exam solutions. The work you submit should
  be the product of your own effort and reflect your personal
  understanding. (See the course syllabus for more information.)

  I submit this work in accordance with the PRIME DIRECTIVE. I affirm
  that I can explain the code and answers within as I created them and
  they reflect my personal understanding.

  Signed,

  <REPLACE WITH SUBMITTER NAME>

Refer to the Project 1 instructions and adapt them for details of how to submit to Gradescope. In summary they are

Command Line Submission

Type make submit to create a zip file and upload it to Gradescope; enter your login information when prompted.

Manual Submission

Type make zip to create pX-complete.zip, transfer this file to a local device, then upload it to the appropriate assignment on Gradescope via the sites web interface.

You may wish to review the policy on late project submission which will cost 1 Engagement Point per day late. No projects will be accepted more than 48 hours after the deadline.

https://www.cs.umd.edu/~profk/216/syllabus.html#late-submission