<!-- Abstract: CS 211 Computer Architecture Lecture 04: Memory and Variable Size Arrays --> # CS 211 - Lecture 04 - Memory and Variable Size Arrays Bernhard Firner 2026-02-02 --- ## Review! * Pointers and Memory * 2's complement --- ## Concepts * In your computer hardware, there are no variable names * Just memory and temporary storage * So every variable name that you see is really referring to some place in memory --- ## Address Of * The & (address of) operator gets a pointer to something * A pointer is a number with a large enough range for your hardware * So 8 bytes in a 64-bit machine, 4 bytes in a 32-bit machine * We can use this to examine the actual memory of our variables --- ## Memory Inspection ```C #include <stdio.h> #include <stdlib.h> /* * This function doesn't return anything, so it returns 'void' * 'char' is the smallest unit of memory. * size_t is a special type that we use along with pointers. * It is guaranteed to have the same range as memory. */ void show_bytes(unsigned char* data, size_t len) { for (int i = 0; i < len; ++i) { printf("Byte %i is %02x\n", i, data[i]); } printf("\n"); } int main(int argc, char argv[][]) { // Verify that there are enough user arguments if (argc < 2) { printf("There aren't enough arguments.\n"); return 10; } int user_input = atoi(argv[1]); printf("Received user input %i\n", user_input); show_bytes((unsigned char*)&user_input, sizeof(int)); } ``` --- ## Memory * Notice that we can cast the pointer from any type * All memory is the same, we decide how to interpret the data present * Normally, that is automatically handled by the **type system** of our programming language * But the type system that exists in hardware is more relaxed --- ## Interpreting Integer Data * We've only looked at one type of data so far: integers * But it's an important one! * Integers can be signed or unsigned * Signed integers are represented using a system called 2's complement --- ## Integer Ranges * An integer's range depends upon its number of bytes * 1 byte: char * 2 bytes: short int * 4 bytes: int (4 bytes on most systems) * 8 bytes: long long int * Each type can be signed or unsigned --- ## Note on Names * More integer docuemention: [https://cppreference.com/w/c/language/arithmetic_types.html](https://cppreference.com/w/c/language/arithmetic_types.html) * If the vague names bother you, stdint.h defines more precise names * [https://cppreference.com/w/c/types/integer.html](https://cppreference.com/w/c/language/arithmetic_types.html) * int8_t for 8 bit int * uint_32_t for 32 bit unsigned int * etc --- ## Signed and Unsigned * The range of an unsigned int with n-bits is $0$ to $2^n - 1$ * The range of a signed int with n-bits is $-2^{n-1}$ to $2^{n-1} - 1$ * Adding 1 to the maximum value always wraps around the to minimum * And subtracting 1 from the minimum will wrap around to the maximum --- ## Interpreting Data * 0xFF (which is 1111 1111 in binary) is different as a signed or unsigned number * It is the maximum unsigned value, 255 * But it is just -1 as a signed value * Take the 2's complement to find the corresponding positive value: * negate all bits, then add 1 --- ## Hex and Binary * When we write numbers in hex and binary, the most significant digits are on the left * 1000 0000 is 127 * 1000 is 8 <table> <tr> <td><b>Binary Number</b></td> <td>1</td> <td>0</td> <td>1</td> <td>1</td> </tr> <tr> <td><b>Places</b></td> <td>$2^3$</td> <td>$2^2$</td> <td>$2^1$</td> <td>$2^0$</td> </tr> <tr> <td><b>Places</b></td> <td>8</td> <td>4</td> <td>2</td> <td>1</td> </tr> </table> --- ## Hex and Binary * When we write numbers in hex and binary, the most significant digits are on the left * 0x100 is 256 * 0x1000 is 4096 <table> <tr> <td><b>Hex Number</b></td> <td>1</td> <td>0</td> <td>8</td> <td>E</td> </tr> <tr> <td><b>Places</b></td> <td>$16^3$</td> <td>$16^2$</td> <td>$16^1$</td> <td>$16^0$</td> </tr> <tr> <td><b>Places</b></td> <td>4096</td> <td>256</td> <td>16</td> <td>1</td> </tr> </table> --- ## Memory Layout * Remember that the layout of MSB and LSB is dependent upon hardware * In little endian systems, the least significant bit (LSB) is first * "first" meaning that it appears at at lower memory address * Big endian systems are the opposite, with the most significant bit (MSB) first --- ## 2's complement * With signed values, anything with the **most significant bit** set is negative ```C #include <stdio.h> #include <stdlib.h> int main(int argc, char argv[][]) { // Verify that there are enough user arguments if (argc < 2) { printf("There aren't enough arguments.\n"); return 10; } int user_input = atoi(argv[1]); if (user_input & (1 << 31)) { printf("Number %i is negative!\n", user_input); } return 0; } ``` --- ## Types and Memory * From here, there are two related topics * Other numeric types * More information about memory * We can't do two things at once, so we'll look at memory first * Starting with allocating memory for arrays --- ## Arrays * [https://cppreference.com/w/c/language/array.html](https://cppreference.com/w/c/language/array.html) * Three types of arrays: * Known constant size * Variable length * Unknown size --- ## Known-Constant Size * Set at `compile time` * In function arguments: * `void print_array(bool array[10]) {` * In variable declaration: * `bool bool_array[10];` --- ## Constant size arrays ```C #include <stdio.h> #include <stdbool.h> void print_array(bool array[10]) { for (int i = 0; i < 10; ++i) { printf("%i: %i\n", i, array[i]); } } int main(int argc, char** argv) { { // This has a fixed size bool bool_array[10]; print_array(bool_array); } { // We could initialize with a set of values bool bool_array[] = {false, false, false, false, false, true, true, true, true, true}; print_array(bool_array); } { // Or we could just set some values bool bool_array[10] = {false, false, true}; print_array(bool_array); } return 0; } ``` -v- ## Notes on `for` * [https://cppreference.com/w/c/language/for.html](https://cppreference.com/w/c/language/for.html) * Four parts: 1. init clause 2. conditional expression 3. iteration expression 4. loop statement * The first three are inside of the parenthesis ```C for (init clause; conditional expression; iteration expression) statement ``` -v- ## More notes * Every part of the for loop has its own scope * This means we could not use it in the `getlen` function ```C // Get the length of a string int strlen(char* str) { // Empty loop statement is okay for (int index = 0; str[index] != '\0'; index += 1); // But index does not exist here, it is out of scope // So we woulve have nothing to return return index; } ``` -v- ## Even more notes * You can do weird things, like leave sections empty ```C // Get the length of a string int strlen(char* str) { int index = 0; for (; str[index] != '\0'; index += 1); return index; } ``` * Some people write infinite loops with `for` rather than `while` * `for(;;) { ... }` * `while (true) { ... }` * Focus on clarity --- ## `sizeof` * The `sizeof` operator returns the size of a variable or type * Can be used to get the number of elements of an array with known size ```C #include <stdio.h> int main(void) { // Notice that we should really initialize our array. float a[10]; // floats are 4 bytes, and there are 10 of them printf("sizeof(a) is %li\n", sizeof(a)); printf("sizeof(*a) is %li\n", sizeof(*a)); printf("There are %li elements\n", sizeof(a)/sizeof(*a)); return 0; } ``` --- ## Initialization * If we initialize any values in an array, C will initialize all of them * The default value will be 0, or some equivalent * '\0' for char, 0.0 for floats, for example * Uninitialized data gets arbitrary values ```C // The first two will be 10 and 11, the rest will be 0. int numbers[10] = {10, 11}; ``` --- ## Checkpoint * Everything making sense? * To contrast a few alternatives for making memory, we're going to do a small algorithm * You don't need to memorize this algorithm! * It is just complicated enough to motivate some learning --- ## Sieve of Eratosthenes * Finds all of the primes up to some number * Algorithm: 1. Mark all numbers from 2 to N as being possibly prime 2. Start at 2 (the first prime) 3. This number is prime; mark all of its multiples as not prime 4. Go to the next number still marked as possibly prime 5. Repeat steps 3 and 4 until reaching N --- ## Boolean Values * In new versions of C we can simply use the bool type * bool is a type that has values **true** and **false** * In slightly older versions, we need to include stdbool.h * To avoid complicating things, we'll always include stdbool.h --- ## Sieve to 100 ```C #include <stdio.h> #include <stdbool.h> int main(void) { // Find and print the primes to 100 bool not_prime[101] = {true, true}; // The other 99 values are default initialized to false // Loop over all numbers to 100 for (int i = 2; i <= 100; ++i) { // Loop over all multiples of any prime numbers if (!not_prime[i]) { // Mark all multiples as not prime for (int j = 2*i; j <= 100; j+=i) { not_prime[j] = true; } } } // Print the primes for (int i = 0; i <= 100; ++i) { if (!not_prime[i]) { printf("%i is prime.\n", i); } } return 0; } ``` --- ## Variable-Length Arrays * We can't know everything ahead of time * For example, how many primes does a user need? * Have to get the input from them, at **run time** * Means a shift in responsibilities * From the compiler to us, the programmers --- ## Variable-Length Declaration * Just put a variable with the length in the `[]` * If the desired size is in variable x: * `int a[x];` * But now we cannot initialize as before * `int a[x] = {0, 1, 2, 3};` * Why not? * Because the compiler does not know if there will be four elements. --- ## `sizeof` and Variable-Length Arrays * `sizeof` still works ```C #include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { float b[atoi(argv[1])]; // floats are 4 bytes, and there are ? of them printf("sizeof(b) is %li\n", sizeof(b)); printf("sizeof(*b) is %li\n", sizeof(*b)); printf("There are %li elements\n", sizeof(b)/sizeof(*b)); return 0; } ``` * But only if the size is known within the current scope --- ## What are They? * You probably aren't thinking about memory and assembly when you look at C * At least, you aren't thinking about those things *yet*! * Fixed-size arrays have memory magagement written at compile-time * Variable length arrays are the same, but the exact size is placed into a run time variable * More details will follow when we've learned enough! --- ## More Useful Sieve ```C #include <stdio.h> #include <stdlib.h> #include <stdbool.h> int main(int argc, char** argv) { if (argc < 2) { printf("Please provide a number!\n"); return 0; } unsigned int size = atoi(argv[1]); // Find and print the primes to 100 bool not_prime[size] = {}; not_prime[0] = true; not_prime[1] = true; // We need to initialize the rest ourselves for (int i = 2; i < size; ++i) { not_prime[i] = false; } // Loop over all numbers to 100 for (int i = 2; i < size; ++i) { // Loop over all multiples of any prime numbers if (!not_prime[i]) { // Mark all multiples as not prime for (int j = 2*i; j < size; j+=i) { not_prime[j] = true; } } } // Print the primes for (int i = 0; i < size; ++i) { if (!not_prime[i]) { printf("%i is prime.\n", i); } } return 0; } ``` --- ## Arrays as Arguments * Can we pass arrays around to different functions? * Of course! They're just pointers, and those are just numbers * But things get a bit more complicated if we want functions to accept arrays of arbitrary size * `int sum(int values[10])` could be a function that sums any array of 10 numbers * `int sum(int values[], int length)` could be a function that sums any array of arbitrarily many numbers --- ## Some Details * An additional complication: * We cannot use `sizeof` to get the size of the array * The array is passed into a function that handles arbitrary sizes * `int sum(int values[]) {` * vs * `int sum(int values[10]) {` * The array is just a pointer, it doesn't have a size * Remember `int values[]` is the same as `int* values` --- ## Summing numbers ```C #include <stdio.h> #include <stdlib.h> int sum(int values[], int length) { int total = 0; for (int i = 0; i < length; ++i) { total += values[i]; } return total; } int main(int argc, char** argv) { // Exit early if we are not given anything to do if (argc < 2) { printf("Please provide at least one number to sum.\n"); return 0; } // There are argc-1 numbers. int numbers[argc-1]; // Remember to begin at i = 1 to skip the program name. for (int i = 1; i < argc; ++i) { numbers[i-1] = atoi(argv[i]); } printf("The sum is %i\n", sum(numbers, argc-1)); return 0; } ``` --- ## Returning an Array * We haven't talked about **ownership** * Any array we've used is owned by its local scope * When a variable goes **out of scope**, the compiler **reclaims** that memory --- ## Memory Ownership * In the summation example, `main` owns `numbers` * The `sum` function can change values, but cannot delete `numbers` * The compiler **reclaims** the memory from `numbers` when it goes **out of scope** --- ## Returning Memory * But what if we want to return memory from a function? * For example, finding prime numbers is something that could go into a function * But how can we return the numbers? * When the compiler writes **compile time** memory management code, it can only write it in a local scope * Meaning that it can only guarantee it is correct within a function --- ## Dynamic Memory Allocation * As soon as memory is returned from a function, the compilier cannot manage it * Thus fixed size arrays and variable length arrays cannot be returned from a function * **Dynamically allocated memory** *can* be returned from a function * Dynamic memory is * Memory that remains outside of its original scope * The fastest way to shoot yourself in the foot --- ## Dynamic Memory Allocation * When you pass dynamic arrays * Keep track of array sizes or else * Memory corruption and segfaults * Security vulnerability * Range check all usage or else * Program crashes * Buffer overflow exploits --- ## Dynamic Memory Allocation * When cleaning up * Remember to delete them when they are no longer needed * If not? Memory leaks and system crashes * Make sure no code acts like they aren't deleted or * Memory corruption and segfaults * Security vulnerability --- ## Dynamic Memory Allocation * This is why people kept making new languages --- ## But Why Not... ```python #include <stdio.h> #include <stdlib.h> // The wrong way int* doubled(int values[], int length) { int double_values[length]; for (int i = 0; i < length; ++i) { double_values[i] = values[i]*2; } return double_values; } int main(int argc, char** argv) { // Exit early if we are not given anything to do if (argc < 2) { printf("Please provide at least one number to double.\n"); return 0; } int numbers[argc-1]; // Remember to begin at i = 1 to skip the program name. for (int i = 1; i < argc; ++i) { numbers[i-1] = atoi(argv[i]); } int* doubled_values = doubled(numbers, argc-1); for (int i = 1; i < argc; ++i) { printf("%i doubled to %i\n", numbers[i], doubled_values[i]); } return 0; } ``` --- ## ``` example17.c: In function ‘doubled’: example17.c:10:12: warning: function returns address of local variable [-Wreturn-local-addr] 10 | return double_values; ``` * Returning function-local memory will fail * In this case, the function `doubled` owns the array * The memory inside of that function is reclaimed when the function ends * This is the only way that the compiler can guarantee correctness --- ## Memory Reclamation * There are differences in memory types * When a function is called its variables are initialized * Where does the memory come from? * Usually the **stack** --- ## Stack Memory * The compiler cannot know what memory you've allocated * Needs a deterministic way to set aside memory for functions, etc * Solution: * Function memory grows from one side of the address space * The `stack` * User allocated memory grows from the other side * The `heap` --- ## Stack Vs Heap Memory <style> .container { display: flex; } .col {flex: 1;} </style> <div class="container"> <div class="col"> * Memory used inside functions is dealt with automatically * Function memory grows on the `stack` * User allocated memory grows on the `heap` * In x86 (architecture we use) * Stack decreases from the top * Heap increases from the bottom </div> <div> <table> <tr><td>Higher</td><td><b>stack</b></td></tr> <tr><td></td><td>$\big\downarrow$</td></tr> <tr><td></td><td></td></tr> <tr><td></td><td></td></tr> <tr><td></td><td></td></tr> <tr><td></td><td></td></tr> <tr><td></td><td></td></tr> <tr><td></td><td></td></tr> <tr><td></td><td>$\big\uparrow$</td></tr> <tr><td>Lower</td><td><b>heap</b></td></tr> </table> </div> </div> --- ## Example ```C /* * Stack Vs Heap example */ #include <stdio.h> #include <stdlib.h> void a() { unsigned char stack_memory[16]; unsigned char *heap_memory = calloc(16, sizeof(unsigned char)); printf("a stack memory is %p\n", stack_memory); printf("a heap memory is %p\n", heap_memory); free(heap_memory); return; } void b() { unsigned char stack_memory[16]; unsigned char *heap_memory = calloc(16, sizeof(unsigned char)); printf("b stack memory is %p\n", stack_memory); printf("b heap memory is %p\n", heap_memory); a(); free(heap_memory); return; } void c() { unsigned char stack_memory[16]; unsigned char *heap_memory = calloc(16, sizeof(unsigned char)); printf("c stack memory is %p\n", stack_memory); printf("c heap memory is %p\n", heap_memory); b(); free(heap_memory); return; } void d() { unsigned char stack_memory[16]; unsigned char *heap_memory = calloc(16, sizeof(unsigned char)); printf("d stack memory is %p\n", stack_memory); printf("d heap memory is %p\n", heap_memory); c(); free(heap_memory); return; } int main(void) { d(); return 0; } ``` --- ## Example Output * Example values not guaranteed, direction is consistent <pre> $ ./a.out d stack memory is 0x7ffc2eceb250 d heap memory is 0x55d2ddab12a0 c stack memory is 0x7ffc2eceb210 c heap memory is 0x55d2ddab16d0 b stack memory is 0x7ffc2eceb1d0 b heap memory is 0x55d2ddab16f0 a stack memory is 0x7ffc2eceb190 a heap memory is 0x55d2ddab1710 </pre> --- ## Unwinding * When a function returns, its memory is released * Called unwinding because functions call functions call functions... * Fast, efficient, and automatic * Stack memory is a **last in, first out** * Each function's memory is "on top of" the last one * We can unwind without checking anything but the current function * In our example, `a` unwinds first, then `b`, `c`, `d`, and `main` --- ## Stack Overflows * If you call enough functions, and they use enough memory, you can run out * This is called a **stack overflow** * Think of the **stack** as an array of fixed size that the compiler sets aside * Normally sufficient * Strange function calling patterns will cause problems --- ## Example ```C /* * Demonstrate a stack overflow. */ void bad() { int a[1000]; bad(); } int main(void) { bad(); return 0; } ``` --- ## Pause * Before going into Heap Memory, is everything clear? --- ## Heap Memory * When you manually allocate memory it goes onto the `heap` * Why do dynamic memory allocation? * Otherwise you can't return memory from your functions * We want our sieve function to be useful * it needs to return an array of numbers of unknown length --- ## Variable Length Arrays * Variable length arrays (VLAs) are a special case * They may either go onto the stack, or onto the heap * It depends upon their size, and is a compiler-specific decision * Always cleaned up when they go out of scope though --- ## Side Note on `VLAs` * Require special consideration * On embedded devices * or if you want precise control over memory consumption * In those cases, choose a maximum "worst case" size and make them fixed size --- ## Quick Summary * This is a good stopping point * memory is a multi-lecture topic * Next time, we'll go over dynamic memory management with **calloc** and **free**