Closing all of the doors (or, in our case, lockers) left open from Week 3, this week gets into the weeds of a computer’s memory, digging deeper into how data is stored within variables and arrays, like strings.
If you’ve visited my other blogs, you’ll find something askew here – because this week’s problem set is extremely long, I’ve chosen to omit it from this guide (though, I would strongly encourage you to give it a try!)
That aside, let’s review my personal notes and observations on Week 4’s lecture.
Lecture Notes
If you’ve ever tried zooming in on an image, chances are you were probably left frustrated at the result… pixels upon pixels… upon pixels.
It turns out that every digital image is just a really large, really precise map of pixels, each of which is filled with a color.
RGB is a color system that mixes different amounts of red, green, and blue light to create the colors we see on our screen.
If you’ve ever worked with Adobe Photoshop, or any type of color picker really, you’ll know that an RGB color can be represented via six values.
For instance, blue can be expressed through RGB as #0000FF, where the first two values represent red, the second two, green, and the last two, blue.
In our example, 255 (the maximum amount of blue) is represented as FF… but why?
To answer this question, let’s break down Week 4.
Number Systems: Hexadecimal
Hexadecimal, a 16-character counting system, is what we use to represent RGB colors.
The values in hexadecimal are as follows:
0 1 2 3 4 5 6 7 8 9 A B C D E F
Note that, after 9, the values switch to letters, where A represents 10, and so on, up until F (15).
Letters are used in place of numbers in order to minimize the amount of digits needed to represent a larger value.
For instance, 255, in decimal, takes up three slots or place values, while it can simply be done in hexadecimal using two: FF.
Much like how in decimal, each ‘place’ is a power of ten (12 = 2 10^0 + 1 10^1), in hexadecimal, each place value is a power of 16 (FF = 15 16^0 + 15 16^1).
Through hexadecimal, or base-16, we can represent information more concisely.
Pointers and Addresses
While we can represent more information with less place values through hexadecimal, a problem arises: how can we differentiate between numbers in hexadecimal versus decimal?
Take a look at the number 12.
This unit stores two very different values depending on the type of counting system I use.
This can become an issue in C as blocks of memory are identified each with respective addresses, which take the form of hexadecimal numbers.
But how could I, or for that matter, the computer, know whether the value 11 is referring to the location in memory in hexadecimal (the address) or the literal integer value in decimal?
As it happens, computer scientists have agreed to denote hexadecimal numbers with the prefix 0x, so as to avoid any confusion.
Let’s write a simple program that visualizes this concept.
#include <stdio.h>
int main(void)
{
int n = 50;
printf("%i\n", n);
}
Here, the variable n is stored somewhere in memory holding the value 50.
Taking a random hexadecimal value for our address – 0x123 – we can see how our variable n takes up four bytes in memory (as it’s an int), starting at 0x123.
Note that technically each byte in memory has its own address, so the first of the four bytes that n occupies lives at the address 0x123.
In C, memory can be accessed via the following operators:
& retrieves the hexadecimal address of something stored in memory
* tells the compiler to go to that location in memory
In order to access the memory location of a variable, we can apply these operators within our code!
#include <stdio.h>
int main(void)
{
int n = 50;
printf("%p\n", &n);
}
Here, we’ve accessed the address of the variable n through the syntax &n. One thing that might jump out is that unfamiliar %p – much like %i or %s we’ve seen in the past, this format specifier just acts as a placeholder for pointers.
Running this code, you will get a memory address starting with 0x.
But why do we need a new format specifier? Why can’t we just use something like %i?
Let’s take a look at a lengthier, but more explicit way to do this problem.
#include <stdio.h>
int main(void)
{
int n = 50;
int *p = &n;
printf("%p\n", p);
}
Here, instead of directly printing &n, we’ve stored it in a variable with a new data type – a pointer to an int.
This is simply because addresses (like the one stored in &n) typically require more bytes than an int can provide.
Depending on the bit-size of your operating system (whether 32-bit or 64-bit), the size of a pointer will vary. However, usually, a pointer is stored as an 8-byte value, while an int is stored as a 4-bit value.
Just remember that pointers are variables that contain the address of some value – so, in order to store memory addresses, you must use the dereference operator * before your variable!
So what if we had the memory address but wanted to access the value of the variable itself?
#include <stdio.h>
int main(void)
{
int n = 50;
int *p = &n;
printf("%i\n", *p);
}
Here, the variable pointer p stores the hexadecimal address of n, as we’d seen in the last example.
Within the print statement, instead of using just p this time, we use *p, which, remember, tells the compiler to go to that location in memory and effectively retrieve the value of n.
Unrelated to the lecture, as I was digging around the internet trying to find out more about pointers, I found that pointers themselves have addresses, which can be accessed through double pointers **.
In the code above, our pointer p stores the address of n, and our double pointer p2 stores the address of pointer p.
Note that the (void *) casting is unnecessary, but a good precaution as %p expects a pointer of type void.
We can see, visually, how p2 points to p1, which points to n.
Stringing Together the Secret of Strings
Didn’t it seem a little peculiar how whenever we’ve worked with strings in the past, we’ve also had to include cs50’s specific library?
Funnily, strings don’t exist in C.
Recall how strings are just arrays of characters. For instance, string s = “HI!”.
So when we create a string, what’s really happening in memory is that our variable s is pointing to the first letter of our string: “H”.
Note that our pointer s and our array of characters are stored in different places in memory, the first byte (storing “H”) being connected by a pointer.
Let’s test this out in the codespace if strings are, indeed, just arrays of chars.
As expected, both our pointer s and the first character in the array have the same address. Notice, too, how every character in the string is stored exactly one byte away from the other.
Knowing this, we can remove the training wheels, so to speak, and rewrite a simple string program without the aid of cs50.h…
#include <stdio.h>
int main(void)
{
char *s = "HI!";
printf("%s\n", s);
}
We can go even further, accessing and printing each element of the string using bracket notation using %c as a char format specifier.
#include <stdio.h>
int main(void)
{
char *s = "HI!";
printf("%c\n", s[0]);
printf("%c\n", s[1]);
printf("%c\n", s[2]);
}
If we wanted to do achieve this without arrays, we could also directly access the memory, telling the compiler to go into a specific memory address (via *) and adding one byte to each address.
#include <stdio.h>
int main(void)
{
char *s = "HI!";
printf("%c\n", *s);
printf("%c\n", *(s + 1));
printf("%c\n", *(s + 2));
}
But what if we were to access memory beyond our char * of length 3…?
After trying to access an absurd number of bits beyond my char array, a Segmentation Fault occurred. You can imagine how hackers might try to use this method to view sensitive information.
Comparing Strings
In last week’s lecture, we sort of glossed over the fact that strings could not be compared using the == operator, and that something like ‘strcmp()’ would be more appropriate.
Why?
Well, remember that strings are nothing more than pointers to arrays of chars and if we were to compare strings via the following method…
#include <cs50.h>
#include <stdio.h>
int main(void)
{
// Get two strings
char *s = get_string("s: ");
char *t = get_string("t: ");
// Compare strings' addresses
if (s == t)
{
printf("Same\n");
}
else
{
printf("Different\n");
}
}
… our code would not work as intended as, notice, we are comparing the pointer s, which stores the address of the first byte in the string, to pointer t.
Because our variables exist in two different locations in memory, this algorithm was always doomed to fail.
In a revised version, I’ve replicated the ‘strcmp()’ function (albeit, under another name), passing two char * values as parameters, and adding one to the index until a character from either string hits the NULL terminator.
The conditional within the loop indexes into the char array and checks if both values are different, returning 1 if so.
Once one of the strings terminates, the program returns 0 if, essentially, both strings have terminated.
If not, and the other string is longer than the terminating one, 1 is returned.
Keep in mind, pointer arithmetic is also an option here! Replace any instance str1[i] and str2[i] with the following:
*(str1 + i)
*(str2 + i)
Copying Strings and Memory Allocation
With comparing strings down, copying them should be fairly easy… right?
Your first instinct might be doing something like this (as was mine):
string s = get_string("s: ");
string t = s;
But recall that a string is nothing more than a pointer to a char… meaning that when we set s to t, all we’re doing is going to the address of the first byte in s and setting that value to t.
When we print this out, it seems that the string has been copied.
In truth, all this program has done is made t point to the same byte of memory as s:
Indeed, if we were to modify the value of the string stored in the pointers t or s and print both of them out, you will find that whatever you’ve changed in one is reflected, also, in the other.
This is simply because they are the exact same, or aliases of one another.
Creating an authentic copy of a string requires the use of ‘malloc()’, a function that allows us to allocate a certain amount of memory without actually using it just yet.
After using malloc(), we must also use the ‘free()’ statement to tell the compiler to deallocate or free up that memory when we’re done with it.
Now at the terminal window we see that when one of the strings was modified, the other did not change, signifying that this program does work as intended.
Note that we called malloc(strlen(s) + 1) as we needed to reserve enough space to store the contents of the string plus that one extra NULL terminator ‘\0’.
It’s also worth mentioning that within the for loop, instead of calling strlen(s) multiple times, we optimized efficiency by storing its value in a variable n, calling the function just once.
Luckily for us, the C language comes pre-equipped with a ‘strcpy()’ function, essentially replacing our for loop.
Finally, we can track memory leakage through Valgrind, a built-in tool, by running it on our program like so: valgrind ./copy.
Garbage Values
When using malloc(), or any other memory allocation techniques (like simply declaring an array with no values), it’s more than likely that your computer will have already used that chunk of memory before, meaning that within them will be junk or garbage values.
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int scores[1024];
for (int i = 0; i < 1024; i++)
{
printf("%i\n", scores[i]);
}
}
For instance, running this code might yield insane numbers or characters, as I didn’t take the liberty to initialize my scores array.
Scope and Swapping
If I asked you to swap two liquids, each contained in separate containers, you would likely need a third to act as a temporary storage… let’s try this in the codespace, but using a function this time.
#include <stdio.h>
void swap(int a, int b);
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, y is %i\n", x, y);
swap(x, y);
printf("x is %i, y is %i\n", x, y);
}
void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;
}
This code does, indeed, run… but it doesn’t work. Weird.
When we pass values into a function like swap(), those values are just copies, meaning the x and y passed in, and the a and b modified within the function, are not pointing to the same places in memory.
This is where the concept of scope comes into play: variables defined within the main() function can only be successfully modified there, within that scope (and the same applies for variables defined in the swap() function).
Global variables, as the name would suggest, have a scope across the whole program – though, we haven’t come across them quite yet.
#include <stdio.h>
void swap(int a, int b);
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, y is %i\n", x, y);
swap(&x, &y);
printf("x is %i, y is %i\n", x, y);
}
void swap(int a, int b)
{
int tmp = *a;
a = b;
*b = tmp;
}
In a revised version of this code, instead of passing the variables themselves, we simply pass the address of those variables.
Because the function accepts pointers as parameters, it knows exactly where in memory to modify x and y, in a way superseding scope.
In other words, the swap() function still makes “copies” of the addresses of x and y, and stores them in a and b, but since that address only exists once in memory (and x and a and y and b are pointing to the same things), we know that the correct values will, indeed, be swapped.
It’s a lot to take in, I know, but just one more thing. Take a look at the below image.
This diagram shows where each of these components live in memory. As you can probably imagine, problems can arise when heap and stack intersect and buffer overflows occur. Here are the two types:
Heap Overflow: when the heap overflows, accessing memory you’re not supposed to.
Stack Overflow (like the website): when too many functions are called, overflowing the available memory
Keep in mind that the heap and stack are just where memory is allocated.
User Input Through Scanf
While we’re still here, removing the guard rails of the cs50.h library, let’s implement the ‘get_int()’ function from scratch.
Using scanf, rather easily, we were able to recreate the function and print out the result at the end. We use the & character so that scanf() has a memory address in which to store the user input into.
Because we don’t know how many bytes will be in the string a user inputs, it would be difficult to implement a ‘get_string()’ duplicate with our current knowledge!
Final Thoughts
Hopefully this guide has given you enough pointers in the right direction and has addressed all of your concerns about memory in C!
Closing off with a word from Leonardo da Vinci, “learning is not enough; we must apply.” So if you do have the chance, make sure to give Problem Set 4 a try!
That’s all for Week 4.