Week 4 (Memory)

Topics

  • Pointers
  • Hexadecimal
  • malloc and free
  • File I/O

Programming Exercises

Below are a few example programming exercises that engage students in hands-on practice on the week’s topics. Keep in mind that class might not be long enough to include all exercises, so be sure to pick just a few! For this week, in particular, you might choose one exercise from each of these topics.

  • Practice with malloc
    • Give students practice with malloc and free, allocating memory dynamically, storing data in that memory, and then freeing memory when done with it.
  • Concatenate
    • Write a function concatenate that takes two strings and returns a concatenated version of the two strings.
    • Topics
      • Strings
      • Pointers
      • Memory management
    • Sample Solution 
      char *concatenate(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char *s3 = malloc(len1 + len2 + 1);
    for (int i = 0; i < len1; i++)
    {
        s3[i] = s1[i];
    }
    for (int i = 0; i < len2; i++)
    {
        s3[len1 + i] = s2[i];
    }
    s3[len1 + len2] = '\0';
    return s3;
}
      • You can test the solution using a program like: 
        int main(void) 
{
    char *s1 = get_string("s1: ");
    char *s2 = get_string("s2: ");

    char *s3 = concatenate(s1, s2);
    printf("%s\n", s3);
    free(s3);
}
  • Copy
    • In copy.c, write a program that copies a text file. Users should be able to run ./copy file1 file2 to copy the contents of text file file1 into file file2.
    • This is a good exercise to do together, as students likely won’t be familiar enough with File I/O to know how to do this on their own yet. 
      #include <stdbool.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    if (argc != 3)
    {
        printf("Usage: ./copy infile outfile\n");
        return 1;
    }
    FILE *infile = fopen(argv[1], "r");
    FILE *outfile = fopen(argv[2], "w");
    while (true)
    {
        char c = fgetc(infile);
        if (c == EOF)
        {
            break;
        }
        fputc(c, outfile);
    }
    fclose(infile);
    fclose(outfile);
}
  • Copy (Extensions)
    • If you’ve already done copy.c, these exercises are good extensions. Students could be expected to attempt these on their own, since they involves only a small amount of additional functionality:
      • In uppercase.c, write a program that takes a file, and generates a new file that converts all of the letters in the original file to uppercase.
      • In caesar.c, write a program that takes a file, and generates a new file that shifts all of the letters in the original file by 1.
  • GIF Detection
    • Write a program gif.c that checks if a file (likely) a GIF (specifically, a GIF 89a file, the latest version of the GIF file format). Note that the first six characters of a GIF 89a file are the characters G, I, F, 8, 9, a.
    • Topics
      • File signatures
      • File I/O
    • Sample Solution 
      // Detect if a file is a GIF

#include <stdbool.h>
#include <stdio.h>

const char signature[6] = {'G', 'I', 'F', '8', '9', 'a'};

bool is_gif(FILE *f);

int main(int argc, char *argv[])
{
    // Check usage
    if (argc != 2)
    {
        printf("Usage: ./gif0 filename\n");
        return 1;
    }

    // Open file
    FILE *f = fopen(argv[1], "r");
    if (!f)
    {
        printf("Could not read file.\n");
        return 1;
    }

    // Check for GIF signature
    if (is_gif(f))
    {
        printf("GIF\n");
    }
    else
    {
        printf("NOT GIF\n");
    }

    // Close file
    fclose(f);
}

bool is_gif(FILE *f)
{
    // Read bytes in to buffer
    unsigned char buffer[6];
    int bytes = fread(buffer, 1, 6, f);

    // Check number of bytes read
    if (bytes != 6)
    {
        return false;
    }

    // Check each byte
    for (int i = 0; i < 6; i++)
    {
        if (buffer[i] != signature[i])
        {
            return false;
        }
    }

    return true;
}
  • PDF Detection
    • Create a program, pdf.c, that checks whether a file, passed in as a command-line argument, is a PDF. All PDFs will be assumed to begin with a four byte sequence: 0x25 0x50 0x44 0x46.
    • Topics
      • File signatures
      • File I/O
    • Resources
    • Example Usage 
      $ ./pdf test.pdf
Likely a PDF!

      $ ./pdf test.jpg
Hm, not a PDF.
    • Sample Solution 
      #include <cs50.h>
#include <stdint.h>
#include <stdio.h>
    
int main(int argc, string argv[])
{
    // Check for usage
    if (argc != 2)
    {
        printf("Improper usage.\n");
        return 1;
    }
    
    // Open file
    FILE *pdf = fopen(argv[1], "r");
    
    // Create buffer for file
    uint8_t buffer[4];
    
    // Create array of signature bytes
    uint8_t signature[] = {0x25, 0x50, 0x44, 0x46};
    
    // Read first 4 bytes from file, then close.
    fread(buffer, 1, 4, pdf);
    fclose(pdf);
    
    // Check buffer against signature
    for (int i = 0; i < 4; i++)
    {
        if (signature[i] != buffer[i])
        {
            printf("Hm, not a PDF.\n");
            return 0;
        }
    }
    printf("Likely a PDF!\n");
    return 0;
}

Conceptual Exercises

These exercises involve thinking and problem-solving, though writing a program is less of the focus here. They still engage students in practice that helps them better understand the week’s concepts!

  • Pointer Prediction
    • Have students mentally walk through the code on the left-hand side of this diagram. Ask: How do the values of the variables and pointers evolve? What will the final values for each variable or pointer be?
    • Afterwards, students should download, compile, and run the same code, in pointers.c to test their predictions against how the code actually runs.
    • pointers.c 
      #include <cs50.h>
#include <stdio.h>

int main(void)
{
    int a = 28;
    int b = 50;
    int *c = &a;

    *c = 14;
    c = &b;
    *c = 25;
    
    // Print results
    printf("a has the value %i, located at %p\n", a, &a);
    printf("b has the value %i, located at %p\n", b, &b);
    printf("c has the value %p, located at %p\n", c, &c);
}
  • Debugging Memory Leaks
    • Debug a program, create.c, that creates a file given as input at the command-line. For example, ./create test.c will create a file test.c. But the code has three memory errors! Can you find and fix them! Try running valgrind ./create test.c to check.
    • Topics
      • Valgrind
      • Memory leaks
      • Common memory errors
      • Debugging
    • create.c 
      #include <stdio.h>
#include <stdlib.h>
#include <string.h>
    
int main(int argc, char *argv[])
{
    // Check for improper usage, otherwise, get filename length
    if (argc != 2)
    {
        printf("Wrong usage: Try ./create [filename]\n");
        return 1;
    }
    int filename_length = strlen(argv[1]);
    
    // Create a new block of memory to store filename
    char *filename = malloc(sizeof(char) * filename_length);
    
    // Copy argv[1] into block of memory for filename
    sprintf(filename, "%s", argv[1]);
    
    // Open new file under the name stored at filename
    FILE *new_file = fopen(filename, "w");
}
    • Three Errors to Identify
      • malloc one additional character, to leave space for NUL terminating character.
      • free filename
      • Close the opened file
    • Sample Solution (Code) 
      #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{

    // Check for improper usage, otherwise, get filename length
    if (argc != 2)
    {
        printf("Wrong usage: Try ./create [filename]\n");
        return 1;
    }
    int filename_length = strlen(argv[1]);

    // Create a new block of memory to store filename. Add one additional character for NUL character.
    char *filename = malloc(sizeof(char) * (filename_length + 1));

    // Copy argv[1] into block of memory for filename
    sprintf(filename, "%s", argv[1]);

    // Free filename
    free(filename);

    // Open new file under the name stored at filename
    FILE *new_file = fopen(filename, "w");

    if (new_file == NULL)
    {
        printf("Could not create file.");
        return 1;
    }

    // Close new file
    fclose(new_file);
}

Discussion Questions

One technique to promote participation in section is a quick, 2–3 minute discussion question. Letting students posit their own reasoning, even if they’re not entirely sure of an answer, can help reinforce material from lecture. One model for introducing these questions is the “Think, Pair, Share” approach, in which students take 30 seconds to think of their own answer and 60 seconds to share their answer with a partner. Afterwards, you can call on random pairs to share their thinking with the larger group. It’s also best to follow up with your own answer, too!

  • Why might each file type need to have a specific set of header bytes? If a file has the header bytes associated with .jpg, why does this not conclusively indicate the file is a .jpg?
  • In Binky Pointer Fun, we saw that Binky attempted to dereference a pointer that hadn’t yet been assigned a “pointee”. Why might this cause an error?

Annotated Sample Slides

Here you’ll find sample slides to adopt or adapt when teaching Section 4.

Some slides contain speaker notes to illustrate why the sample section takes a certain approach to illustrating a concept or leading an exercise. You’re welcome to modify these slides as you see fit, though do try to keep some of the same elements of active learning that have been included in these samples.

Past versions of sample slides are also available under the “Additional Slide Resources” dropdown.