# Lecture 1 ## What is information? - Bits of information - 1 bit = 1 yes/no information - $n = \log_2(m)$ - $n$ = number of bits - $m$ = number of information things you can specify/represent - If you have 8 bits: can represent/specify 256 things - $2^n$ - Is a "thing" capable of specifying one of 2341 options? That thing contains $\log_2(2341)$ bits of information ## Representing information - 2 primary entities in electronics: voltage and current - Most info in modern EECS is expressed in voltage, although current plays an important role too > **Analog system:** voltage can be expressed and interpreted as many values. > **Digital system:** voltage is limited (almost always to 2 categories of values) - *Analog vs. digital:* - **Analog** - 0 vs 10V (can have *manyyyyy* encoded bits with one value) - shades of gray! - **Digital** - 0 vs. 1 bit - black and white - [I] On paper, the ideal case is evidently analog, because a voltage varying from 0 to 10V in 0.01V steps means a single reading can contain up to 1000 options or approx 9.96 bits of info - But not noise robust! Variance in 0.01V measurement will mess the whole thing up. - [*] Digital solution is robust! either has signal or 0 - Digital conveys less information in one bit, but way more robust than analog ### Digital in electronics (digital contract) - Use voltages to represent the yes/no 1/0: - High voltage: 1 - Low voltage 0: - Specifically we set up a "contract" which all parts agree to: - Above a certain amount is 1, below a certain amount is 0, in the middle between these is the forbidden zone (to prevent us from even having to worry about weird noisy flips in the middle) ### Information budget - How many bits needed to represent hour of day? - 24 options: $\text{ceil}(\log_2(24))$ = 5 bits ## Binary $$v = \sum_{i=0}^{N-1} 2^i \cdot b_i$$ - Smallest number: $0$, largest number: $2^{N} - 1$ - Binary addition, subtraction, multiplication, division are all performed as they are in base 10 - **Overflow:** if we use a fixed number of bits, addition a nnd other ops can produce results outside the range that the output can represent - **Underflow:** ^ same idea but w subtraction (negative numbers in lec 2) - [I] Limiting output to $N$ bits is the same as mod $2^N$ - overflow and underflow can be helpful ^ ! ### Decimal to binary 1. Find the largest power of 2 that will fit into the decimal number, e.g. for 21, we would have $2^4 = 16$ 2. Subtract 21 - 16 = 5 3. Check $2^3$, doesn't fit, check $2^2$, fits 4. Subtract 5 - 4 = 1 5. Check $2^1$, doesn't fit, check $2^0$, fits 6. Subtract 1 - 1 = 0 → Done! Answer: `0b10101` ## C programming language - Been around for 50 years - Very low-level compared to Python - Very unsafe language compared to Python - Original C textbook is very good, masterpiece of technical literature - Python is written in C! - Need to declare types! ### Printing - Specifying width: `printf("%3d, %6d\n", a, b)` - `a` will be given 3 columns of space, `b` will be given 6 columns - Printing floating space: `%f` - `%d`: decimal number ### Types - 3 main types: - integers: `int`, 4 bytes - characters: `char`, 1 byte - 1 byte = 8 bits → standard ASCII has only $2^7 = 128$ characters so 1 byte suffices! - floating point numbers: `float`, 4 bytes - [!] Cannot change a variable's type post creation! ### `goto` (not in Python) - C allows you to jump to labeled locations in your code using the `goto` statement - very close to how assembly works! ### Operators - Logical and bitwise! - Shift operations - Shift left by `i` is same as multiply by $2^i$ as long as don't fall off edge - think: `24` → `240` in base 10 is multiply by $10^1$ → same idea for base 2 - Shift right by `i` is same as integer divide by $2^i$ (floor) - think: `24` → `2` = `24//10` (integer divide) ### Pointer - Pointer is a data type in C that "points" to other data - It does so by storing a memory address (called a *reference*) - We can then access what it points to as needed (**dereference**) - Allows direct access and manipulation of memory (dangerous, but also freeing) ```C int x = 5; // make int called x int * ptr_to_x; // make int pointer called ptr_to_x ptr_to_x = &x; // give ptr_to_x the address of x ``` - `int * ptr_to_x;` declares that `ptr_to_x` is a pointer to an integer - [i] Pointer is itself a variable! It also lives in memory and has its own address. Except its value is the address of integer `x`'s spot in memory. - `*` is used in conjunction with type to declare a pointer - `*` is also used to **dereference** = get the value at the address the pointer points to ```C int * z; // declare int pointer named z *z = a; // set the value z points to to be int a b = *z; // set int b to be the value z points to int *z = &a; // set pointer z's value to a's address ``` - [I] As operators, `*` and `&` are opposites and can cancel out: ```C int x = 5; // create x and set to 5 x = 6; // set x to 6 *(&x) = 6; // same thing as line above ``` - `*(&x) = 6` → "the value located at the address of `x` is 6" - [*] **The purpose/utility of pointers:** 1. To point to a variable 2. To refer to memory regions that aren't associated with variables 1. MMIO - read directly from fixed spots in memory 3. To point to a group/region of data/variables 1. Large groups of data can be slow to copy around - if we can instead just hand around a pointer to the data group, can be much faster! ### Larger data types in C - Arrays ```C int a[6] = {3, 9, 6, 1, 7, 2}; ``` - [!] Need to know array length explicitly in C! Unlike python - Size must be known at init + fixed - Type of all elements of the array must be the same (can't have mix of ints and chars and floats) - Variable `a` stores the *address* to the first element in array - `*(a+3)` = 4th element of `a` (index 3) > Array is an ordered list of contents in memory - there is no attribute `len` etc. - Structs ## What is memory? - Memory is a large chunk of electrical storage - *Everything* is stored in binary - Every part of memory has an address affiliated with it - Goes from low addresses to high addresses - If you were to "look" at memory - you'd just see a massive sea of `1`'s and `0`'s going on for ages ## Hexadecimal - Base 16! ``` 0000 - 0 0001 - 1 0010 - 2 0011 - 3 0100 - 4 0101 - 5 0110 - 6 0111 - 7 1000 - 8 1001 - 9 1010 - A 1011 - B 1100 - C 1101 - D 1110 - E 1111 - F ``` - We use hex and binary interchangeably (they are the exact same thing to the computer)! Except hex is easier for us humans to read when the binary strings get long. ## Organization - bytes & words > Smallest unit accessible in memory of most modern computers is a **byte** which is 8 bits. - In 6.190, we operate in a **32 bit** system which means the memory is organized into 4-byte **words** - In memory, we have: - 4-byte words with addresses - Each word contains 32 bits of data - Addresses are also 32 bits of data # Recitation 1 - Unsigned binary operations - Addition (add digit-wise, carry over when 1+1) - Multiplication (multiply digit-wise, add partial products) - How would you get the memory address of a value stored in a variable x? `&x` - A pointer is a memory address - (Read up on what a pointer is more - is it an address? points to an address? What is it?) - If a variable `z` stores the address of the number value 10, how would you get that value 10 from `z`? `*z` - `*z` = go to address `z` and get that value - e.g: ```c int x = 10; int *z = &x ``` # Lab 1: Introduction - ESP32: Espressif ESP32-C3-DevKitM-1 - RISC-V microprocessor - PCB ## 5.2) Starter code - C header file: `6190.h` - PlatformIO project config file: `platformio.ini` ## 6) General purpose input/output (GPIO) - GPIO pins: - Before usage, must configure them by writing values to specific memory addresses (aka. *control registers*) on the ESP32 - 32-bit values ### 6.1) Bit manipulation - **3 main operations:** 1. Setting one bit in the $n$-bit value so that the bit is equal to 1 (w/o modifying any of the other bits in the value) - To set bit `x` (zero-indexing from the rightmost bit) to be 1: `val |= (1 << x);` 2. Clearing one bit in the $n$-bit value so that the bit is equal to 0 (w/o modifying any of the other bits in the value) - To clear bit `x` (zero-indexing from the rightmost bit) to be 0: `val &= ~(1 << 2);` 3. Reading one bit from the $n$-bit value (without modifying the value itself) - To read `x`th bit: `bit = (val >> x) & 1;` - [i] Rightmost "least-significant" bit is the 0th bit ### 6.2) GPIO configuration - Given a memory address, e.g. `GPIO_ENABLE_ADRR`, to access the value at this memory address: ```C int *gpio_enable_addr = (int*) GPIO_ENABLE_ADDR; // declare pointer equal to this memory address int gpio_enable_val = *gpio_enable_addr; // puts 32-bit value stored at GPIO_ENABLE_ADDR into variable gpio_enable_val *gpio_enable_addr = 500; // writes the 32-bit number 500 to memory address GPIO_ENABLE_ADDR ``` ## 7) Logical LEDs - Questions: - Why is 0 = button pressed? # Exercise 1 ## Some C Practice - `enum` = "creating a type" with a meaningful name - enums don't make your code more efficient but they make your code more readable ```C enum location {Below=-1, Within=0, Above=1}; # then a valid function that returns type location would be: location boundary_function(...) { return Within; } ``` - Review how to code binary search, e.g.: ```C long abs(long n) { if (n >= 0) { return n; } else { return -1 * n; } } long cube(int n) { return (long)n * n * n; } int cube_root(int value){ // Binary search from 1 to value if (value == 1) { return 1; } int low = 1; int high = value / 2; long best_dist_so_far = -1; int best_so_far; while (low <= high) { int mid = (low + high) / 2; long mid_cubed = cube(mid); long new_dist = abs(mid_cubed - value); if (best_dist_so_far == -1 || new_dist < best_dist_so_far) { best_dist_so_far = new_dist; best_so_far = mid; } // Binary search update if (mid_cubed < value) { low = mid + 1; } else { high = mid - 1; // Why mid - 1 and not mid? } } return best_so_far; } ``` - Review how to code a merge sort # Lecture 2 - $n$ bits - can represent $2^n$ different things - 1byte = 8bits - how many bits needed to represent $t$ possibilities? $\text{ceil}(\log_2(t))$ bits - [I] an 8-bit value represents $2^8$ unique *things* but there are many types of *things* we need to represent - not necessarily a number - 163 if unsigned int - -93 if signed integer - ... if float - ... etc! ## Lec outline - Addresses - Pointers - Arrays - Pointer arithmetic - C-strings (a little bit) - Characters - ASCII - Unicode - Numbers - Ints - Signed ints - Decimals, etc. - Booleans ## Recap: Computer organization > The smallest unit accessible in memory of most modern computers is a **byte** which is 8 bits. - Computer memory: - 4-byte words with addresses - Each word contains 32 bits of data - Consecutive words have addresses that are 4 bytes apart - this doesn't mean you can't go to address that is 1 byte apart - it just won't be the next consecutive **word** - 32-bit machine: addresses are 32 bits; 64-bit machine: addresses are 64 bits - 32-bit machine: $2^{32}$ different addresses available - each address points to 1 byte, so $2^{32}$ bytes of addressable memory - $2^{32}$ bytes = $2^{30}$ words > An address is like a **label/location** in memory. At that location, the computer can store bits. How you interpret those bits depends on your program: they could represent an `int`, a `char`, an instruction, part of an array, part of a pointer, etc. - [i] Pointers must have size (like any other variable)! To hold the address of an arbitrary spot in memory for 32-bit machines, pointer has size = 32 bits ### Size of different data types - 1 byte: `char`, `uint8_t`, `int8_t` - 2 bytes: `uint16_t`, `int16_t` - 4 bytes: `uint32_t`, `int32_t`, `float` - pointers also have type! we need to know what size of thing to pull from the address - `int *ptr_x;` = pointer `ptr_x` of type `int` - can also write `int * ptr_x`, `int* ptr_x`, but `int *ptr_x` is probably closest to the true meaning saying "`*ptr_x`" is of type integer ### Pointers will break if the types are wrong ```C char c = 'J'; char *ptr_c = &c; int *ptr_d = &c; printf("ptrc_c points to %c, ptr_d points to %d\n", *ptr_c, *ptr_d); // prints: ptr_c points to J, ptr_d points to 525944906 ``` - [!] above code will lead to interpreting the contents at `&c` as an int - a char is not an int ... their encoding and sizes are different! so decoding char as an int (what we do when we dereference `*ptr_d`) causes problems - [I] A pointer itself is a variable, which lives in memory - which means it can be pointed to as well → we call that a pointer pointer ## Arrays - Creating an array does 2 things: 1. Allocates memory for the array 2. Creates a pointer by which you access that spot in memory - [I] An array is basically a pointer + specially allocated memory! - Dereferencing with an offset is identical to indexing! `y[3] == *(y+3)` - [!] Watch your limits! Arrays exist in memory, and there are no boundary checks in C! - [!] **Slight difference between array variable and pointer:** array's pointer is the only way to access the memory that makes up the array so be careful! ```C int a = 1; int *x = &a; int y[10] = {1,2,3,4,5} // x and y are of the same type! int poitners! (sort of) y = &a; // not allowed will throw compile error ``` - ^ this protects you from losing access to your memory location! - [!] **an array cannot be reassigned!** - once an array exists, you can't reassign it! the value of an array is an address!!! ==**an array is a fixed pointer.**== - however, you can reassign the things in the array - [!] the information about how large an array is needs to get passed into functions separately - all the function sees is a pointer! > Arrays devolve to pointers inside functions. - e.g. ^ need to write: ```C void double_every_entry_better(int *ptr, int length) { for (int i = 0; i < length; i++) { *(ptr + i) = *(ptr + i) * 2; } }// length param is called *metadata* ``` ## Strings > Strings are arrays of `chars`. They have a special character `NULL` to mark the end of a string so that we don't have to repeatedly hand around second arguments with the strings saying how long it is. ## Characters > `ASCII`: Represent original computer characters using 8 bits: 256 possibilities (though only lower 128 are used)![[Screenshot 2026-05-05 at 5.01.18 PM.png]] - `0b00000000` is `NULL` - Another form of `ASCII` table (same as one above but with nicer colors):![[Screenshot 2026-05-05 at 5.02.13 PM.png]] - The char encoding is separate from the render - e.g. rendering `A` is a query to a lookup table - Other character encodings: - Unicode - more languages, symbols, etc. - 4 byte representation! - ASCII still kept at 1 byte ## Boolean - Original C doesn't really have a "bool" type - A boolean only needs 1 bit to express itself - In general an unsigned int is used s.t. 0 is `false`, and everything else is `true`. ## Numbers - **Unsigned ints** `uints`: - `uint8_t` - 1 byte - `uint16_t` - 2 bytes - `uint32_t` - 4 bytes - Inherent modularity when you use a fixed number of bits - overflow - **Signed ints** - Two's complement: use inherent modularity of fixed bit unsigned addition to encode negative numbers - The negative of a number $A$ can be expressed as $-A = 2^3 - A$ (for 3-bit numbers): generally, $$\boxed{-A = 1 + (\neg A)}$$ - Remember this!! - How many values can we encode with 3 bits now? -4 to 3 (only one 0!) → $2^3$ distinct values! - `int8_t`: 1 byte: $2^8$ values - `int16_t`: 2 bytes: $2^{16}$ values - `int32_t`: 4bytes: $2^{32}$ values ### Two's complement $$v = -2^{N-1} \cdot b_{N-1} + \sum_{i=0}^{N - 2} 2^i \cdot b_i$$ - Negative numbers have `1` in the high-order bit - Most negative number: `10...0` = $-2^{N-1}$ - Most positive number: `01...1` = $2^{N-1} - 1$ - If all bits are 1: $-1$ ### Extending digits - In unsigned int, if you want to make it take more bits, just add 0s to the front - In signed int, you need to *sign extend* ### Shift left - Add 0s to the right, drop of MSB - Always "logical" ### Shift right - Logical: Pad 0s - Arithmetic: Sign extend ## Why still have unsigned ints? - `uint8_t` and `int8_t` both represent 256 things, but: - `uint8_t`: 0 to +255 - `int8_t`: -128 to +127 - [I] If I know my loop has to iterate from 0 to 140 (or if I'm working with array indices etc.) it would be a waste to have to use 16 bits because I have to use only signed integers. `uint8_t` is a better choice for some things so we keep them around! ## Decimals - One attempt: fixed point representation - Instead, we actually use: floating point! - An exponential format - [I] Thought experiment to motivate the ideas behind floating point: - Imagine we have an (totally nonexistent lol) 8-bit type called `exp8_t` where the 8 bits represent an exponent: ![[Screenshot 2026-05-05 at 7.37.23 PM.png|500]] - ^ this would allow us to encode a massive *range* of numbers with decimal points but the precisions of the numbers would be limited (only really one number for each order of magnitude) - [*] We can increase precision by adding more bits! → **IEEE754 floating point representation** ## IEEE754 Floating point ![[Screenshot 2026-05-05 at 7.41.15 PM.png|400]] - ^ 24 bit fixed-point number (23 bits of which are specifiable) - e.g., mantissa in the image = $1 + 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + \ldots 0 = 1 + 0.25 = 1.25$ # Exercise 2 ## Two's complement - What's the smallest number of bits needed to properly represent the result of `0b0010 - 0b0100`? - `- (0b0100) = 0b1011 + 1 = 1100` - `0b0010 + 0b1100 = 0b1110 = -8+4+2 = -2 = 0b10` → 2 bits is sufficient! - **Arithmetic vs. logical right shift:** - Arithmetic: left append MSB-matching bits (0s or 1s) - Logical: left append 0 bits only ## Floating point - 32-bit floating point to decimal: - (1 sign bit) (8 bits exponent) (23 bits fraction) - Sign bit = 0: positive; sign bit = 1: negative → $2^{\text{sign bit}}$ - Exponent: $2^\text{exp-127}$ ($\text{exp} - 127$ assuming the IEEE bias is 127) - i.e., convert the 8 bits to decimal, subtract 127, then raise 2 to the power of this - Fraction (mantissa): 1.[23 bit fraction] (e.g., `01001` should be interpreted as `1.{01001}` in decimal) - The `{01001}` should be converted via: (left) `2^-1 | 2^-2 | 2^-3 | ...` (right) - i.e., $0 \times 0.5 + 1 \times 0.25 + \ldots$ - Final decimal number: `(-1)^sign * mantissa * 2^exponent` - e.g.: `0b1011_1110_1010_0000_0000_0000_0000_0000` - Sign bit: 1 - Exponent: `01111101` = 125 - 127 → $2^{-2} = 0.25$ - Fraction: `1.{01000000000000000000000}` = 1.25 - Combined: $(-1)^1 \times 0.25 \times 1.25 = -0.3125$ - Decimal to 32-bit floating point:$$\text{decimal number} \rightarrow (-1)^{\text{sign}} \times (1.\text{fraction}) \times 2^\text{exponent}$$ - e.g: -10 1. Sign bit: 1 (negative) 2. Convert 10 → binary: `1010` 3. Scientific notation in base 2: `1010 → 1.010 * 2^3` (this is essentially $(1*2^0 + 0*2^{-1} + 1*2^{-2} + 0*2^{-3}) * 2^3 = 1*2^3+0*2^2+1*2^1+0*2^0$ ) 4. Exponent: $2^3 \rightarrow 3 + 127$ 5. Drop leading 1, pad to 23 bits for mantissa: `01000000000...` - e.g: 0.875 1. Sign bit: 0 (positive) 2. Convert 0.875 → binary: fraction method of binary conversion! **Multiply by 2 repeatedly:** - 0.875 * 2 = 1.75 → `1` - 0.75 * 2 = 1.5 → `1` - 0.5 * 2 = 1 → `1` - 0 * 2 = 0 → `0` - Total: `0.1110` 3. Normalize (scientific notation): `0.1110` → `1.110 * 2^{-1}` 4. Exponent: $2^{-1} \rightarrow 127 -1 = 126$ 5. Drop leading 1, pad to 23 bits for mantissa: `1100000...` 6. Assemble: `0_01111110_1100_0000_0000_0000_0000_000` - [I] How to figure out if a decimal can be represented **exactly** in binary (IEEE 754)? > A number can be represented exactly in binary iff its reduced fraction has denominator = $2^k$, aka. only fractions whose denominator is a power of 2 will terminate in binary. - e.g: $\frac{710}{512}$ can be represented in 32-bit floating point binary - $\frac{1}{15}$ **cannot** be represented in 32-bit floating point binary, because its most reduced form (i.e. itself, 1/15) has denominator $15 \neq 2^k$. - $0.1$ **cannot** be represented in 32-bit floating point binary, because its most reduced form has denominator $10 \neq 2^k$. - [i] Floating point logical comparisons abide by normal logic (positive > negative, larger number > smaller number, etc.) ## Mixed width inputs ```C a = 0b01001; b = 0b011; unsigned result = a + b; result = 0b? 01001 00011 // extend 0s because we are doing unsigned addition ----- 01100 ``` Another example: ```C a = 0b1010; b = 0b00011; signed result = a + b; 11010 // extend most significant bit for signed operations 00011 ----- 11101 ``` And another one: ```C a = 0b11011; b = 0b1001; signed result = a - b; 11011 // extend MSB 00111 // negated 1001 + extend MSB ----- 100010 // keep 5 least significant dig - 00010 result = 0b00010 ``` And another one: ```C a = 0b01011; b = 0b0110; signed result = a + b; 01011 00110 // extend MSB ----- 10001 // overflow! redo with more padding 001011 000110 ------ 010001 // yay looks good! no more overflow result = 0b010001 ``` - [I] **Summary** of steps: (assuming that each time we encounter overflow, we pad to fix it) `a + b` 1. Match widths to $N = \max(|a|, |b|)$: - Unsigned: prepend `0`'s to the shorter operand - Signed: replicate the MSB (most significant bit) of the shorter operand 2. For subtraction, convert to addition: `a - b = a + (-b)` - `-b` = flip bits + add 1 3. Perform addition, keep $N$ rightmost bits 4. Check for overflow: - Unsigned: was there a carry out of the MSB? - Signed: did two same-sign inputs produce an opposite-sign result? - [i] Mixed sign addition (one negative, one positive) can never overflow - will always end up at a number less "extreme" (closer to 0) than `a` or `b` 5. If overflow, redo with $N+1$ bits (extend both operands by 1 bit - 0 or sign extend depending on unsigned/signed), then repeat from step 3. ## C++ operator precedence https://en.cppreference.com/w/cpp/language/operator_precedence.html - Important order to remember: 1. `a++, a--, type(a), a[]` 2. `++a, --a`, `*a, &a`, `!a, ~a, (type)a` 3. `a * b, a / b, a % b` 4. `a + b, a - b` 5. `a << b, a >> b` 6. `a < b, a <= b, a > b, a >= b` 7. `a == b, a != b` 8. `a & b` 9. `a ^ b` 10. `a | b` 11. `a && b` 12. `a || b` 13. `a = b, a ? b : c`, `a += b`, `a *= b`, ... e.g: ```cpp int b = 8 ^ 5 & 9 | 3; ``` 1. `5 & 9 = 0101 & 1001 = 0001` 2. `1000 ^ 0001 = 1001` 3. `1001 | 0011 = 1011` 4. `1011`= 11 ```cpp int c = !0 && 1 || 5 || 3 && 0; ``` 1. `!0` = 1 2. `1 && 0 = 0`, `3 && 0 = 0` 3. `0 || 5 || 0 = 1` ```cpp int d = 2 + 3 << 4 / 2 == 7 ^ 5 * 2 | 4; ``` 1. `5 * 2 = 10`, `4 / 2 = 2` 2. `2 + 3 = 5` 3. `5 << 2 = 0101 << 2 = 010100` 4. `010100 == 7` = False = 0 5. `0 ^ 10 = 0000 ^ 1010 = 1010` 6. `1010 | 0100 = 1110` = 14 ```cpp int a = 2; int b = a++ + a; printf("a = %d, b = %d\n", a, b); // prints a = 3, b = 5 int e = 6; int f = e++ - 2 + e; // what is the value of f? ``` - [I] `a++` is a **post-increment:** uses the current value of `a` first, then increments - ^ compared to `++a`, which increments first, then uses the new value. ## Pointer arithmetic > **Memory** (in this class): Consider all memory to be made up of consecutive "blocks," like an infinite array. Each block can hold 8 binary values (8 bits), or 1 *byte* of information. - For the computer to interact with this data, each block needs to have a label → this label is called an *address*, and we usually write it in hexadecimal. - These blocks are labeled sequentially, so if 0x10 is the first block, then 0x11 is the second block ... - In C, we store this address to data in a *pointer.* > *Pointers* are called pointers because they point towards data we would like to reference. ```C int number = 60004; int* number_ptr = &number; *number_ptr; // equals 60004 ``` ### Pointers to different types - We can make pointers to any type of object in C! - Different types of variables take up different amounts of memory - Integers take 4 bytes (4 blocks of data) - Chars take up to 1 byte - Floats take up 4 bytes - Doubles take up 8 bytes - Dereferencing pointers of a certain type will always return a value of that type (e.g., `*number_ptr` will always return an integer) - **Pointers to arrays:** Arrays in C are pointers to the type of element held by the array. ```C int x[3] = {1, 2, 3}; // x is a pointer to an integer: *x gives access to the first element of the array, i.e. *x = x[0], aka. x = &x[0] ``` - ^ note that the address of `x[1]` = `&x[1]` = `((int)(&x[0])) + 4`, because `x` is an array of integers and each integer takes up 4 bytes of memory - In C, we can write `&x[0] + 1` to access the address of `x[1]` because C knows `&x[0]` is `int*` and will know to move 4 bytes - We can also write `x = x + 1` to get the address of `x[1]`: if you increment `x` by 1 and then dereference `*x`, you will get the next element of the array. - Even though the address of `x[1]` is 4 bytes away, C knows that incrementing an integer pointer is equivalent to adding 4 to it. - Analogously, for `char`'s: ```C char y[5] = {'a', 'b', 'c', 'd', 'e'}; // *y = y[0] // if you increment y by 1, the resulting address will be ((int) (&y[0])) + 1 because each character only takes up one byte of memory ``` # Lecture 3: C strings & other things ## Outline 1. IEEE 754 floating point representation 1. Range vs. precision compromise 2. FP8 debate 2. Arrays in C 1. `sizeof` 3. C-string 1. `string.h` 4. structs ## IEEE 754 floating point > ^ A scientific notation approach to number representation! - `float`: - 4 bytes (32 bits): $2^{32}$ values - Expresses from approx. $[-3.4\times 10^{38}, +3.4 \times 10^{38}]$ - Also expresses small numbers down to $1.17\times 10^{-38}$ - Decimal point is "==floating==" (as opposed to fixed) - In a fixed-point system, the position of the decimal/binary point is permanently locked in place by design (e.g. 16 bits for the integer part, 16 bits for the fractional part) - In a floating points system, the decimal point is freed by using the binary equivalent of scientific notation. The exponent acts as an instruction telling the computer *where to move* the decimal point! ![[floating point.png]] $$\text{value} = (-1)^\text{sign} \cdot 2^{\text{exp} - 127} \cdot \left(1 + \sum_{i=1}^{23} b_{23 - i} \cdot 2^{-i}\right)$$ - *How do we do math with floats?* - You can't just add them like we did with integers → need more complicated algorithms and circuits (add the exponents, multiply the mantissas, ...) - **Don't worry about it in this class! Just worry about the encoding.** - [!] A 32 bit `float` does **not** let us represent more numbers than a 32 bit `int`: still can only represent $2^{32}$ unique values! - ^ but it does let us represent a far wider range of numbers compared to an integer or a fixed point number - [I] Floating point is a *compromise*: we sacrifice precision for range! - [!] Floating point can have **massive gaps**!! - The amount of "change" caused by toggling the least significant bit (lsb) of the fraction part (mantissa) is also affected by what the exponent value is, because everything gets multiplied together to form the final value. - ^ To see this in action: - Starting at $0.15625$, the "next" value expressible is: $0.156250014901$, a jump of $1.4901 \times 10^{-8}$ (not bad of a gap!) - Starting at $5.31691198314 \times 10^{37}$, the next value expressible is $5.3169124902 \times 10^{37}$, a gap of $5.0706 \times 10^{30}$!!! yikes... - [!] Floating point use is **approximation based:** - 32 bit floats represent $2^{32}$ ($4.3 \times 10^9$) values between $[-3.4\times 10^{38}, +3.4 \times 10^{38}]$ - ^ by Pigeonhole principle, there is *no way* to represent every number (or even integer) between these limits with only 32 bits ! ```C #include int main (void) { float x = 123456789; float y = 123456788; printf("the value of x is %f\n", x); printf("the value of y is %f\n", y); } // prints: "the value of x is 123456792.000000" "the value of y is 123456784.000000" ``` - [!] This **approximation based** schema can be *problematic*!! Exponential representation means that merging (+/-, etc...) two numbers of vastly different scales can result in the smaller one getting consumed by the larger one and lost. ```C int main (void) { float x = 1.35e9; float y = 23.0; float sum = x + y; float sum_wo_x = sum - x; printf("x is %f\n y is %f\n x + y is %f\n x + y - x is %f\n", x, y, sum, sum_wo_x); } // prints: x is 1350000000.000000, y is 23.000000, x + y is 1350000000.000000, x + y - x is 0.000000 ``` - Floating point has a **double 0:** two distinct binary representations for the number zero, $+0$ and $-0$ - $+0$: sign bit is `0`, exponent is all `0`'s, fraction is all `0`'s - $-0$: sign bit is `1`, exponent is all `0`'s, fraction is all `0`'s - Although they have different binary patterns, computers are explicitly programmed to treat them as numerically equal: $+0 == -0$ evaluates to true. - [I] Double 0 is a feature instead of a bug :) -- it can be helpful when doing calculus (left vs. right limits) - [i] Floating point 0 is **by definition** (as in the encoding of all 0s or sign bit 1, all 0s is *defined to be 0*) -- the normalized formula has $+1$ that makes it impossible to be 0 using the formula. ### How are floats still "relevant" to learn today? - The `fp8` debate! - [I] The last ~5 years have been a very exciting time for data representation actually, because of ML! - In the ML field, we're building massive systems with billions of weights that need to be stored and used. - The fewer bits we need to represent those weights, the more we can store. - Also the fewer bits we need, the faster we can compute. - General consensus is that a 32 bit float is overkill in a lot of applications. - [?] Do we use ints? Smaller floats? Something else? - [*] ^ so there's been a lot of research in formats! - *What is the best mini-float representation for ML?* - Various types of 8-bit floating points (FP8) have been coming out. - [I] **Different variations!** - More bits on mantissa? More on exponent? More/less overall? - NVIDIA really likes E4M3 and E5M2 formats. - Field is gradually coalescing on things: https://docs.nvidia.com/deeplearning/transformer-engine/user-guide/examples/fp8_primer.html ![[flops + floating point format.png]] > **FLOPS** = FLoating-point Operations Per Second. An "operation" is a math calculation (e.g. adding, multiplying two floating-point numbers together). - [I] FLOPS is a measurement of raw computing speed! It specifies exactly how many floating-point math problems a processor can solve in 1 single second. - T (TeraFLOPS) = trillions of operations per second - P (PetaFLOPS) = quadrillions of operations per second (1 P = 1000 T) - FP16: 16-bit floating-point numbers - FP8: 8-bit floating-point numbers - The smaller the bit-size, the less precise the number is, but the faster the computer can do the math. - We can train LLMs in FP4! ![[train LLMs in FP4.png]] ## Arrays > In C, arrays are just **continuous portions of memory** accessible via a pointer-like element. - Creating an array in C: ```C int x[] = {1, 2, 3, 4}; // make 4 long int array, call it x int y[10]; // create 10 long int array, call it y (but don't declare values) int z[5] = {1}; // create 5 long called z, 0th element is 1, rest are 0 ``` - Can do the same thing for char array, but the syntax is a bit more flexible because we also use char arrays for strings: ```C char a[10] = {'t', 'h', 'e', ' ', 'c', 'a', 't', '.'}; // 10 char array with 2 nulls char b[] = "the cat."; // 9 long array with "the cat." followed by 1 null ``` - [!] C code cares about double quotes " " (which specify strings) vs. single quotes ' ' (which specify chars)!!!!!! (Python doesn't care) ### How memory works for consecutive arrays ![[memory after code.png]] - [!] **Problem:** The computer doesn't ever "see" the whole memory - it just gets glimpses of it. If you tell the code that there's an array at `0x3fc93f10`, yay, but there's nothing in memory that tells the program how much memory is associated with that *array*: the computer only knows where it starts. - [?] *How can we tell the computer the size of an array?* - Solution 1: `sizeof` - Solution 2: Explicitly pass "size of array" variables around (this is the cleaner solution) ### In functions, arrays devolve to pointers ! - [!] In C, all function arguments are **passed by value.** - Passing an array in its entirety is expensive (in time and memory). Instead, we pass a pointer that contains the array's address (by value) and therefore implicitly provide a way to pass the array by reference. - "by value": when you pass a variable by value, the computer creates a complete, independent copy of the data and hands that copy to the function. Here, we provide the *address* by value (but not the actual array). - "by reference": when you pass by reference, you aren't giving the function a copy of the data. Instead, you give the function **direct access** to the original data in memory. Here, we provide the function a way to access the array *by reference.* - When an array is handed in as an argument to a function in C, within the scope of the function, all that can be seen is the pointer. **Not the array!!!** ### `sizeof` > `sizeof` provides the size of a data object. It can sort of help but *isn't what you think it is!!!* ```C char a[10] = {'t','h','e',' ','c','a','t','.'}; //10 char array with two nulls char b[] = "the cat"; //8 long array with "the cat" followed by null int x; char y; int z[15]; printf("%d\n",sizeof(a)); //prints 10 printf("%d\n",sizeof(b)); //prints 8 printf("%d\n",sizeof(x)); //prints 4 printf("%d\n",sizeof(y)); //prints 1 printf("%d\n",sizeof(z)); //prints 60 printf("%d\n",sizeof(z)/sizeof(int)); //prints 15 ``` - Because arrays devolve to pointers when passed around to functions in C, while `sizeof` can still be used in a function, it will not provide the size of an array pointed to by a pointer! e.g. below code will um run into issues :"( ```C int sum_array(int* ai) { int sum = 0; for (int i = 0; i < sizeof(ai); i++){ sum+= ai[i]; } return sum; } int main(void) { int aa[10] = {2,4,6,8,10,12,14,16,18,20}; int c = sum_array(aa); //value of c? } ``` - [?] Why does `sizeof` break on arrays in functions? **Because `sizeof` provides the number of bytes that *thing* is.** - On previous slide, the "thing" is a pointer inside a function that is: - only 4 bytes (on a 32-bit system) - only 8 bytes (on a 64-bit system) - [!] There is **no way** to inherently know the size of an array that is passed in as an argument in C. - You **must:** - Pass along variable informing of size of array (general solution) - Establish some sort of rule-set for the size of the object (C-strings) - [!] Scoping can also make stuff confusing with `sizeof`: `sizeof` works on things that are in scope - In original C, `sizeof` is **not a function**: it is an **operator** - This means it is interpreted at *compile time* rather than *run time* - Before the code even runs, `sizeof` evaluates all the places where it is used and is replaced with a number. - [*] ^ summary: `sizeof` only gives you the size of the thing that the compiler can see in the original declaration ```C int aa[10] = {2,4,6,8,10,12,14,16,18,20}; int sum_array(int* ai) { int sum = 0; printf("size of ai: %d\n",sizeof(ai)); // prints 4 printf("size of aa: %d\n",sizeof(aa)); // prints 40 for (int i = 0; i < sizeof(ai); i++) { // will loop i = [0, 4) sum += ai[i]; } return sum; } int main(void) { int c = sum_array(aa); printf("%d\n",c); } ``` - `sizeof` with functions: if you have a function that is supposed to process many different arrays, those arrays will be handed in via a pointer which will point to the start of those arrays when called. `sizeof` can't be called on a pointer since it isn't a run-time function. You won't know ahead of time what is going to come in! #### Conclusion - [i] Mostly don't use/rely on `sizeof` for array things in functions. - [i] There is **no way** to inherently know the size of an array that is passed in as an argument in C. - You **must**: - Pass along variable informing of size of array (general solution) - Establish some sort of rule-set for the size of the object (C-strings: the rule is to go until you see the null character `\0`) - `strlen` counts the characters until it hits the "stop" sign (the null char) - Later notes will talk more about this! - An array has **no** metadata about its size that is accessible at run-time. ### Compile vs. run time #### Compile time: "baking a cake from a recipe 🎂" > **Compile time** is the period when the compiler (like `gcc` or `clang`) is reading your source code and translating it into machine code (the binary `.exe` or `.out` file). - **When it happens:** Before the program ever starts running on your computer. - **What happens:** The compiler checks for syntax errors, makes sure your types match, and performs optimizations. - **The `sizeof` connection:** Because `sizeof` is a **compile-time operator**, the compiler doesn't wait for the program to run to figure out sizes. It looks at the data types and hard-codes the numbers directly into the binary. - _Example:_ If you write `int x = sizeof(int);`, the compiler literally replaces `sizeof(int)` with the number `4` (or `8`) in the final file. #### Run time: "eating the cake 🍰" > **Run time** is the period when your program is actually being executed by the CPU. - **When it happens:** Every time you type `./my_program` or click "Run." - **What happens:** The computer follows the instructions in the binary. It handles user input, calculates values based on what the user types, and allocates memory dynamically (like using `malloc`). - **Comparison:** While `sizeof` happens at compile time, a function like `strlen()` happens at **run time**. The computer has to actually count the characters one by one while the program is running because it doesn't know what the string will be until then. ## C-strings > A C-string is a NULL-terminated `char` array. All elements are ASCII characters! (https://en.wikipedia.org/wiki/ASCII#Printable_characters) - The C-string is from where the pointer points to → where **first NULL** occurs ```C char b[] = "the cat"; // 8 long arrach with "the cat" followed by 1 NULL ``` - This *agreement* about first-NULL allows `char` arrays to be handed around *without* a supporting length variable in some cases - [I] Central idea is that we sacrifice one value in our char encoding space to be the "STOP", similar to what we do in DNA/RNA representations with a stop codon. ### string.h > The `string.h` library is an important set of functions that allow for convenient C-string manipulation, e.g: determine attributes of strings, manipulate/modify C-strings, compare C-strings... - We'll look at a subset of the library! All functions found at: https://www.tutorialspoint.com/c_standard_library/string_h.htm --- - `strlen`: Determine length of a C-string, `int strlen(const char *str);` - **Input:** pointer to a C-string - `const char *` is a way of saying the function won't modify contents of what is pointed to - **Returns:** the length of the string - "length" is defined as the number of non-NULL characters *up until* the NULL. ```C int custom_strlen(const char *str) { char *searcher = str; while (*searcher != '\0') { searcher++; } return searcher - str; } ``` --- - `string.h` manipulation functions: `strcpy` and `strcat` - `strcpy`: copy a string, `char *strcpy(char *destination, const char *source);` - Copy to `destination` C-string the contents of C-string pointed to by `source` - Returns pointer `destination` mainly for convenience ```C char *custom_strcpy(char *destination, const char *source) { uint32_t i = 0; while (*(source + i) != NULL) { *(destination + i) = source[i]; i++; } // make sure to add back stop NULL to destination after copying contents!! destination[i] = 0; // NULL, '\0' will also work return destination; } ``` - [!] Warnings about `strcpy`: e.g., examine the below code: ```C int main(void) { char prez[] = "Sally Kornbluth"; char buffer[4]; int len = custom_strlen(prez); printf("length of string: %d\n", len); custom_strcpy(buffer, prez); printf("Original String: \"%s\"\n",prez); printf("Copied String: \"%s\"\n",buffer); } // will print: // length of string: 15 // Original String: "y Kornbluth" // Copied String: "Sally Kornbluth" ``` - ^ the problem is that `prez` lives after `buffer` in memory, so when we call `strcpy`, it copies over the memory parts that we don't overwrite! [TODO FIGURE THIS OUT LATER BRAIN NOT WORKING RN] ![[Screenshot 2026-04-19 at 5.49.22 PM.png|400]] ![[Screenshot 2026-04-19 at 5.49.51 PM.png|400]] ![[Screenshot 2026-04-19 at 5.49.59 PM.png|400]] - `strcat`: concatenate a C-string, `char *strcat(char *destination, const char *source);` - **Add** onto `destination` C-string the contents of C-string pointed to by `source` - Returns pointer to `destination` mainly for convenience. ```C int custom_strlen ( const char *str ); char *custom_strcpy ( char *destination, const char *source ); char *custom_strcat ( char *destination, const char *source ) { return custom_strcpy(destination + custom_strlen(destination), source); } ``` - `strncopy`: copy $n$ characters from a C-string - `strncat`: concatenate $n$-characters from a C-string - [!] Buffer overread/overwrite bug found in openSSL in 2014 - The bug could leak information by not respecting buffer boundaries - https://en.wikipedia.org/wiki/Heartbleed - Safer `string.h` functions: - `strlcpy`: copy $n-1$ characters from a C-string and makes sure to NULL terminate - `strlcat`: concatenate $n-1$ characters from a C-string and makes sure to NULL terminate ### string.h comparison functions - `strcmp`: `int strcmp(const char *str1, const char *str2);` - `strncmp`: `int strncmp(const char *str1, const char *str2, size_t n);` - ^ Both of these compare two C-strings: - `strncmp` compares the first $n$ characters - `strcmp` compares the entire C-string - What does "compare" mean? It returns: - `<0` if the first character that does not match has a lower value in str1 than in str2 - `0` if the contents of both strings are equal - `>0` if the first character that does not match has a greater value in str1 than in str2 ### string.h search functions - `strchr`: Find first instance of character in c-string, `char *strchr(const char *haystack, char needle);` - looks for first instance of `needle` in C-string `haystack` and returns a poitner to it - if it isn't found, it returns a NULL pointer - e.g. determine if there is an 'l' in "Sally Kornbluth" - `strrchr`: Find last instance of character in c-string - looks for last instance of `needle` in C-string `haystack` and returns a pointer to it - returns NULL if not found ```C char *custom_strchr ( const char *haystack, char needle ) { uint32_t i = 0; while (haystack[i] != NULL) { if (*(haystack+i) == needle) { return haystack + i; } i++; } return NULL; } ``` - `strstr`: Find location of sub c-string inside c-string - looks for first instance of c-string `needle` in c-string `haystack` and returns a pointer the beginning of `needle` - returns NULL if not found - `strtok`: Tokenize c-string into sub c-strings. (exercise this week!) ### `sprintf` >`sprintf` is a function included in standard C that is not part of `string.h`, but is often used to do similar tasks as `string.h` functions. - [I] Just like `printf`, but writes to char buffer rather than terminal. - `int sprintf(char *str, const char* format, ...);` - Write to `str` using regular string formatting rules like `%d`, etc... - Function returns **the number of characters written!** - [*] **Uses for sprintf:** - Used to replicate/provide slight deviations/improvements on several of the `string.h` functions - Allows the creation of formatted C-strings rather than just printing them to terminal! e.g.: I want to stringify a computationally determined number: ```C int i = some_function(19, 86); // return 2012 char temp[10]; sprintf(temp, "%d", i); // temp now holds the c-string: "2012\0" // NULL is auto-added in sprintf ``` - Example: Let's generate a C-string that has every number in it from 0 to 1000! **2 methods:** [TODO READ THIS CODE CAREFULLY LATER] 1. One function that repeatedly uses `strcat`: ```C //version one using strcat: char totes[10000000]; //big enough void build_num_string_1() { totes[0] = 0;//null first value for (int i =0; i<100000; i++){ char temp[10]; sprintf(temp,"%d ",i); strcat(totes,temp); } printf("%s\n",totes); } ``` - ^ this takes 0.56 ish seconds to run 2. One function that uses `sprintf` in conjunction with pointer arithmetic directly: ```C //version 2 using sprintf and //pointer arithmetic: char totes[10000000];//big enough void build_num_string_2(){ totes[0] = 0;//null first value int tally = 0; for (int i =0; i<100000; i++){ tally += sprintf(totes+tally,"%d ",i); } printf("%s\n",totes); } ``` - ^ this takes 0.004 ish seconds to run :0! #### Some conclusions about string stuff - `strcat` repeatedly has to scan the string from the beginning, causing longer and longer run-times for longer and longer strings! - Avoid repeatedly scanning a string if you can help it! ### The evolution of the String - In the evolution of programming languages, one of the first things tacked onto a higher level "string" data type was a piece of **meta-data** keeping track of string length - So when we `+=` a Python string, that length is already known inside the object! - [*] Python's string library is actually *many* lines of well written C! https://github.com/python/cpython/tree/main/Objects/stringlib - (CPython is the default, original, and most widely used implementation of the Python programming language! aka., OG Python is essentially a C wrapper :) ) ## Structs > **Structs** can have member variables, but do not have member methods or functions. - Access member variables with dot operator: e.g. `thing.x` to access `thing`'s `x` member - Example struct: ```C struct Subject { int dept; int units; char name[100]; int num_students; }; int main(void) { struct Subject our_course; our_course.dept = 6; our_course.units = 6; strcpy(our_course.name, "6.1903: Intro to C and Assembly"); our_course.num_students = 255; } ``` ### Structs with functions ```C void make_subject1(struct Subject s) { s.dept = 8; s.units = 12; strcpy(s.name, "8.02: Physics 2"); s.num_students = 500; } make_subject(our_course); printf("%s has %d students and is in Course %d and is %d credits.\n", our_course.name, our_course.num_students, our_course.dept, our_course.units); // What will this ^ print? ``` - [I] ^ ==Arguments are always passed by **value**!!== - So the above code will print the original values defined earlier (`"6.1903: Intro to C and Assembly has 255 students and is in Course 6 and is 6 credits."`) -- we passed in a *copy* of `our_course` instead of actual `our_course`, so in-place edits occurred on the copy of `our_course` (and therefore were not saved to the outside `our_course` we defined earlier) - So the re-assigning was futile! > **Function arguments** are ==passed by value== (arguments := things that you pass into the function when calling it). - To fix the earlier code to actually meaningfully change `our_course` outside of the function, we can do: ```C struct Subject make_subject1(struct Subject s) { s.dept = 8; s.units = 12; strcpy(s.name, "8.02: Physics 2"); s.num_students = 500; return s; } our_course = make_subject(our_course); ``` - [?] One might ask - don't we pass pointers when we pass arrays into functions? - Yes - we pass the *literal value of the address.* When you pass a pointer to a function, the computer creates a **local copy** of that pointer variable. - Then, in the function: - If you were to change the pointer itself inside the function, the original pointer in `main` wouldn't change at all, because the function only gets a *copy* of the original pointer. - BUT if you dereference the pointer, i.e. `*copy_of_address`, you go to the physical location this address points to and changes the value stored there, which changes the same thing located at that physical location that the outside pointer points to. - [!] **Is passing a struct into a function a good idea,** given that arguments are always passed by value? - To pass by value means a copy needs to be made - structs can be big, so passing a large thing by value can be: - Slow - Use limited memory to make temporary copy - use too much and you could get a stack overflow! - [i] So passing a struct by value, while allowed, is often not the best idea. - [I] Instead, pass a pointer to structs! ### Struct pointers > Just like everything else, you can have a pointer to a struct. - The pointer allows us to reference things in memory (round-about way of passing by reference) and modify it directly! ```C void make_subject3(struct Subject* s); make_subject3(&our_course); // call function on pointer to our_course ``` - [?] *How to access members of struct pointer?* - [!] `*s.units = 12;` is **not** going to work, because `*` has lower priority than `.` - Recall: ![[c order of operations.png]] `*` is higher than `.` - Instead, we can do: `(*s).units = 12;` - This isn't the slickest though ^! - [*] **Preferred method:** `s->units = 12;` where `->` hides the `*` + `.` combo (arrow is equivalent to doing `(*s).units`) - Example code with struct pointer: ```C void make_subject3(struct Subject* s) { s->dept = 8; //or (*s).dept s->units = 12; //or (*s).units strcpy((*s).name, "8.02: Physics 2"); //or s->name (*s).num_students = 500; //or s->num_students } make_subject3(&our_course); //call function on pointer to our_course printf("%s has %d students and is in Course %d and is %d credits.\n", our_course.name, our_course.num_students, our_course.dept, our_course.units); // ^ prints: 8.02: Physics 2 has 500 students and is in Course 8 and is 12 credits. ``` ### How big is a Struct? - At least as big as the sum of its component parts! - e.g. ^ sum up the bits for `Subject` on a 32-bit system: ```C struct Subject { int dept; int units; char name[100]; int num_students; }; ``` ### Couple of other `struct` things - No member functions, so no concept of public/private - Struct can have member structs, just not member of same type (`Subject` cannot have member `Subject`) - Can declare structs with starting values: https://en.wikipedia.org/wiki/Struct_(C_programming_language) - Other ways of initializing structs: ```C // declare but don't initialize struct Subject our_course; // declare and initialize struct Subject other_course = {9, 12, "9.01: Intro Brain Stuff", 100}; // declare and initialize (named fields) struct Subject other_other_course = {.dept = 1, .units = 12, .name = "1.01: Intro Prob/Inference", .num_students = 100}; ``` ## Appendix - Why is NULL ok for a return value? - NULL in C is defined as the value 0. - In general, **nothing** is going to be sitting at memory location 0. - Other languages such as Python have a whole datatype to do this - Python's `NoneType` # Exercise 3 ## String stuff - `const char **texts` is a pointer to a pointer to `char` - usually an array of strings - ^ array of **read-only strings** ```C char c = 'a'; char *s = "hello"; char *arr[] = {"hello", "world"}; // then: char **texts = arr; ``` ## Parsing and extracting ints - `*my_array` is the same thing as doing `my_array[0]` - ^ an array of **anything** in C is referred to by a **pointer** to its first element ### Parsing ```C char c = '5'; int x = (int)c; // convert c to an integer print(x); // prints out 53 ``` - ^ this prints out `53` in decimal because the value stored in memory for the char '5' is `00110101` (`53` in decimal) - ASCII for '5' is 53! - ^ to convert char to actual integer value, can use `atoi`: ```C int x = atoi("15"); printf("%d",x+1); //prints 16 x = atoi("-15"); printf("%d",x+1); //prints -14 x = atoi("+1505"); printf("%d",x+1); //prints 1506 x = atoi("abc"); printf("%d",x); //prints 0 printf("%d",x+1); //prints 1 ``` - [!] Things to beware with `atoi`: - If non-numbers are fed to it, it returns a 0 - `atoi` expects a `char` array and **not** a single `char` - [i] `strtok` splits char array at delimiter positions - e.g. split `"134&245&111333&89"` by `&` - https://cplusplus.com/reference/cstring/strtok/ - `strtok` is a **stateful function**: it is designed to be called multiple times - [!] If you try to pass a `char` rather than a `char *` as the second argument to `strtok`, will get a compilation of the form: `invalid conversion from 'char' to 'const char*' [-fpermissive]` (this will also happen if you try to use `strcat` or `strcpy` with a single `char` rather than with a pointer to a `char`) ![[strtok.svg]] ### Some `strtok` practice ```C char my_string[] = "Don't Be Suspicious. Don't Be suspicious. Don't be Suspicious. Don't be suspicious."; char* my_ptrs[10]; int my_addrs[10]; ``` You first run: ```C int ms_addr = (int)&my_string; printf("0x%x\n",ms_addr); ``` And get back: `0xf77b` You then proceed to run: ```C my_ptrs[0] = strtok(my_string,"b"); my_addrs[0] = (int)my_ptrs[0]; printf("0x%x\n",my_addrs[0]); ``` - **Q:** What gets printed? `0xf77b` - **Q:** `my_ptrs[0]` is pointing to a string. What string is it pointing to? - "Don't Be Suspicious. Don't Be suspicious. Don't " You then proceed to do the following: ```C my_ptrs[1] = strtok(NULL,"b"); my_addrs[1] = (int)my_ptrs[1]; printf("0x%x\n",my_addrs[1]); ``` - **Q:** What gets printed now? - `0xf77b` + len("Don't Be Suspicious. Don't Be suspicious. Don't ") + 1 (pointer skips the newly inserted NULL) = `0xf77b` + 48 + 1 = `0xf77b` + 49 (decimal) = `0xf7ac` - **Q:** `my_ptrs[1]` is pointing to a string. What string is it pointing to? - "e Suspicious. Don't " ```C my_ptrs[2] = strtok(NULL,"b"); my_addrs[2] = (int)my_ptrs[2]; printf("0x%x\n",my_addrs[2]); ``` - **Q:** What gets printed now? - `0xf7ac` + len("e Suspicious. Don't ") + 1 = 0xf7ac + 21 = `0xf7c1` - **Q:** `my_ptrs[2]` is pointing to a string. What string is it pointing to? - "e suspicious." We then run this line: ```C my_ptrs[3] = strtok(NULL,"b"); ``` - **Q:** What value will be stored in `my_ptrs[3]`? - NULL We then proceed to run the following: ```C my_ptrs[4] = strtok(my_string,"p."); my_addrs[4] = (int)my_ptrs[4]; printf("0x%x\n",my_addrs[4]); ``` - **Q:** What gets printed? - `0xf77b` - **Q:** `my_ptrs[4]` is pointing to a string. What string is it pointing to? - "Don't Be Sus" - [I] **Core idea of how `strtok` works:** `strtok` resets when you feed it a non-NULL first argument - ^ so when we called `my_ptrs[4] = strtok(my_string,"p.");`, the pointer was reset to the head of `my_string` (`0xf77b`) - `NULL` first argument (`strtok(NULL...)`) = continue from where you left off ### `int_extractor` implementation using `strtok` *Review this before the exam!* ```C void int_extractor(char* data_array, int* output_values, char delimiter){ int i = 0; char delim_str[2] = {delimiter, '\0'}; char *res = strtok(data_array, delim_str); while (res != 0) { output_values[i] = atoi(res); i += 1; res = strtok(NULL, delim_str); } } ``` # Lecture 4: RISC-V Assembly ## Sum an array ```C int i = 0; int arr_sum = 0; int arr_len = 10; while (i < arr_len) { int val = *(arr + i); arr_sum += val; i++; } ``` - Need to translate C/Java/Python/... (high-level languages) into a language that just uses the **general-purpose processor's** list of **instructions** that it can execute using its hardware - This language is *assembly*! - Assembly then gets translated into binary that the processor has hardware to decode → **machine code** > **Takeaway:** Assembly language tells us the exact steps that a processor carries out when running through a program. - Assembly and machine code are the same thing! Just the former is for the programmer, latter is for machine (but exists 1-1 mapping) ## What is an assembly language program? > An assembly language program is a *sequence of instructions* which ... ### Instruction set architecture (ISA) > **ISA:** The contract between software and hardware. - Functional definition of operations ... - 2 main approaches to ISAs: 1. CISC (complex instruction set computer) 2. RISC (reduced instruction set computer) - Apple: used to be CISC (x86) and now is RISC (ARM) ### CISC philosophy - Fundamental instructions are more **complex** - Larger instruction set - Programs that have fewer instructions - e.g. Intel (x86) ### RISC philosophy - Fundamental instructions are more **basic** - Faster to processor to execut - Smaller instruction set - Programs with longer instructions - e.g. ARM ### RISC-V ISA - A newer (2010), open free ISA from Berkeley - Several variants: - `I`: Base integer instructions - `M`: multiply and divide ... - etc. - We will study the `RV32I` processor, which is the base integer 32-bit variant. ## Registers vs. memory - Both store information! | **Registers** | **Memory** | | ------------------------------- | --------------------------------------- | | Expensive | Cheap | | Physically large | Very dense/small | | Quick to access | Slower to access | | Actually in the computer itself | Further away/separate from the computer | > **Conclusion for most computers** (compromise): Have a small set of registers (maybe 20 or 30) that you use as much as possible as temporary variables; use memory as rarely as possible! ## RISC-V Processor storage **Registers:** - 32 general-purpose registers `x0-x31` - Each register is 32 bits wide - `x0 = 0` always **Memory:** - Each memory location is 32 bits wide - **1 word = 32 bits = 4 bytes** - When the processor loads/stores data, usually does it in 4-byte chunks. - Each memory address refers to **1 byte** (8 bits) - "Memory is byte (8 bits) addressable" - Addresses of adjacent words are 4 apart: 1 word = 32 bits = 32/8 → 4 addresses - So memory looks like: ``` Address Data 0x00 [1 byte] 0x01 [1 byte] 0x02 [1 byte] 0x03 [1 byte] ^ collectively the addresses for 1 word ``` - Addresses are 32 bits: each address is represented using 32 bits - So the total number of unique addresses is $2^{32}$ - Can address $2^{32}$ bytes of $2^{30}$ words: - 32-bit address → $2^{32}$ unique addresses - Each address points to 1 byte → $2^{32}$ bytes = 4 GB - 1 word = 4 bytes → $\frac{2^{32} \text{ bytes}}{4} = 2^{30} \text{ words}$ ## RISC-V Instructions - **3 types of operations:** - **Computational:** Perform arithmetic and logical operations on register - **Loads and stores:** Move data between registers and main memory - **Control flow:** Change the execution order of instructions ### (1) Computational instructions - 4 main classes of operations: - Arithmetic - Comparison - Bitwise logical - Shift - 2 formats: (of instructions) - Register-register instructions - Register-immediate instructions | **Format** | Arithmetic | Comparisons | Logical | Shifts | | ------------------ | ------------ | --------------- | --------------------- | ---------------------- | | Register-register | `add`, `sub` | `slt`, `sltu` | `and`,`or`, `xor` | `sll`, `srl`, `sra` | | Register-immediate | `addi` | `slti`, `sltiu` | `andi`, `ori`, `xori` | `slli`, `srli`, `srai` | - **Register-register instructions:** - Format: `oper rd, rs1, rs2` - 2 source operand registers: `rs1`, `rs2` - 1 destination register for result: `rd` - `rd, rs1, rs2` could be the same or different! - e.g. ```nasm add x3, x1, x2 # x3 ← x1 + x2 slt x3, x1, x2 # if x1 < x2 then x3 = 1 else x3 = 0 and x3, x1, x2 # x3 ← x1 & x2 sll x3, x1, x2 # x3 ← x1 << x2 ``` - **Register-immediate instructions** - Format: `oper rd, rs1, constant` - 1 source operand comes from register: `rs1` - 1 source operand comes from constant: `constant` (12 bits, 5 for shifts) - 1 destination register: `rd` ```nasm addi x3, x1, 4 # x3 ← x1 + 4 slti x3, x1, 4 # if x1 < 4 then x3 = 1 else x3 = 0 andi x3, x1, 4 # x3 ← x1 & 4 slli x3, x1, 4 # x3 ← x1 << 4 ``` - ^ no `subi`, instead use `addi` with negative constant - `addi x3, x1, -4` = `x3 ← x1 - 4` - [I] **All values are binary!!** - Suppose `x1 = 00101; x2 = 00011` - `add x3, x1, x2` is adding in base 2! - `sll x3, x1, x2` = `00101 << x2 bits` = `01000` - note fixed width shifting! - Right shifts: logical vs. arithmetic - Suppose `x1 = 00101; x2 = 00010` - `srl x3, x1, x2` = `00001` - `sra x3, x1, x2 = 00001` - [*] Every bit you shift to the right, **you divide by 2.** - Suppose `x1 = 10101; x2 = 00010` - `srl x3, x1, x2 = 00101` - `sra x3, x1, x2 = 11101` - Arithmetic shift (1) retains the negativity of negative numbers and (2) retains the effect of **dividing by 2 for each bit you shift to the right** - [i] Logical right shift: shift in 0s; arithmetic right shift: shift in value of most significant bit. ### Putting values into registers - What if we wanted to put `0x123` into `x2`? - ^ can use `addi`! ```nasm addi x2, x0, 0x123 # x2 = 0x123 + 0 = 0x00000123 ``` - What if we wanted to put `0x12345678` into `x2`? - [!] We **can't** just do `addi x2, x0, 0x12345678`! ==The constant in register-immediate instructions is limited to 12 bits.== - [?] *Why limited bits for the constant?* **Because the full instruction itself needs to fit in 8 bits**, and specifying source/destination/operation all require bits! The number of bits left for the constant happens to be 12. - `addi` can only compile 12 bits - [I] Instead: use `lui`! #### `lui`: Load Upper Immediate - Format: `lui rd, luiConstant` - Puts **20-bit** constant value (`luiConstant`) in the upper 20 bits of a register (`rd`) - i.e. puts in most significant 20 bits of the 32 bits available! - **Appends 12 zeros to the low end of the register** - Supports putting constants that are larger than 12 bits into a register! - e.g. - What if we wanted to put `0x12345678` into `x2`? ```nasm lui x2, 0x12345 # put 0x12345 into upper 20 bits of x2: x2 = 0x12345000 addi x2, x2, 0x678 # x2 = 0x12345000 + 0x678: x2 = 0x12345678 ``` #### Compound computation Let's do `a = ((b+3) >> c) - 1` 1. Break up complex expression into **basic computations** - Our instructions can only specify two source operands and one destination operand 2. Computational instructions can **only access registers, not memory** - Assume `a`, `b`, `c` are in register `x1`, `x2`, `x3` respectively. Use `x4` for `temp0` and `x5` for `temp1` ```C temp0 = b + 3; // addi x4, x2, 3 temp1 = temp0 >> c; // sra x5, x4, x3 a = temp1 - 1; // addi x1, x5, -1 ``` - Yay {this point} concludes our computational instructions! ### (2) Loads and stores - These are the **only** operations that allow you to move data between registers and main memory! - **Accessing words in memory:** - In 6.190, all RISC-V memory accesses will involve entire 32-bit words - We will read an entire 32-bit word from memory - We will store an entire 32-bit word into memory - However, memory is *byte* (8-bit) addressable - Addresses of adjacent words are 4 apart - [!] **Memory addresses used in load and store instructions must be multiples of 4!** #### RISC-V Load Instruction - Format: `lw rd, offset(rs1)` - Read the 23-bit value stored at the memory address `rs1 + offset` - Base address `rs1` always stored in a register - Offset `offset` is a 12-bit constant - `base + offset` sum must be a multiple of 4! - Put that 32-bit value in a register `rd` - `lw x1, 0x4(x0)` = `x1 ← Mem[x0 + 0x4]` - go to address `0x4`, take contents and put in `x1` #### RISC-V Store Instruction - Take 32-bit value in register `rs2` and store it at the memory address `rs1 + offset` - Base address `rs1` always stored in a register - Offset `offset` is a **12-bit constant** - base + offset sum must be a multiple of 4! - `sw x3, 0x10(x0)` = `Mem[x0 + 0x10] ← x3` ![[load+store assembly.png|400]] #### Revisit: Let's sum an array! Assume we have an array `arr` with 10 integers starting at memory address `0x700`. ![[sum array to assembly 1.png|400]] - [!] **Yes there is a problem here!!** We're adding integers, and integers take up 4 bytes (32 bits). - The current setup adds 1 for each new array entry, but `0x700(1)` brings us to `0x701`, which is not 4 bytes away from `0x700` (so we're still in the memory for the previous array entry)! We need to get to `0x704`: so change `addi x5, x5, 1` to `addi x5, x5, 4` - ^ Accordingly, `arr_len`can't be tracked as `10` → needs to be `40` in order to cover all 10 integers! - ^ Corrected code: ![[sum array to assembly 2.png|400]] *Now let's do the while loop in assembly!* ### (3) Control flow *We detour to understand how assembly works first and then come back to this in a later section.* ## How does assembly work? ### Instructions are stored in memory - Assembly language gets translated into machine language, which is then stored in memory for the processor to read as it executes the program. - In RV32I, all instructions are **32 bits.** More on this in a bit! - e.g. ![[assembly language to instruction.png|400]] ### How does the computer know where it is in the program? - A RISC-V processor has a special register called the **program counter (pc)**. - Holds the memory address of the current instruction - Processor uses this address to fetch the instruction from memory - Then it decodes and executes it - An assembly program will always continue to the next instruction (`pc = pc + 4`) **unless otherwise told by a control flow instruction** (`pc = pc + offset`) - [i] Recall: Instructions are 32 bits (1-word), and memory is 8-bit addressable, so `pc = pc + 4` to move us the equivalent of 32 bits in memory - The `offset` is the distance between the memory address of the current instruction and the memory address of the instruction the program is jumping to - **2 main types** of control flow instructions: 1. **Conditional branch:** branch (`jump`) only if a condition is met 2. **Unconditional branch:** always `jump` > ^ Allow us to create conditional (`if/else`) statements and loops (`while/for`)! ### (3) Control flow, revisited! #### Labels - When writing assembly, you can place ==labels== to give convenient names to lines of instructions - When you need to branch or jump to another part of your code, you just use the label for that code, e.g. ```nasm some_code: addi x5, x0, 521 # refers to addi x5, x0, 521 some_other_code: # refers to the instruction immediately below it, lui x2, 0x12345 lui x2, 0x12345 addi x2, x2, 0x678 ``` - [!] **Labels are not functions at all!!!!!!!** They are simply a tag that makes it easier for the programmer to refer to an instruction (specifically refer to the address at which this instruction is stored for the computer). - This is why a label has no size - takes up no space in memory! It is just a nametag we stick on to the instruction address for ease of programming. - ![[assembly label does not live in memory.png|400]] - Labels do not generate machine code, do not occupy memory at runtime, ... - they exist only during assembly and linking! #### Conditional branch instructions - Format: `comp rs1, rs2, label` - First performs comparison to determine if branch is taken or not: `rs1 comp rs2` - If comparison returns `True`, then branch is taken (jump to `label`), else continue executing program in order. - Updates program counter (`pc`) accordingly | Instruction | beq | bne | blt | bge | bltu | bgeu | | ----------- | --- | --- | --- | --- | ---- | ---- | | `comp` | == | != | < | >= | < | <= | - e.g. `beq x1, x2, label` = `if x1 == x2, jump to label. else go to next instruction` - **Conditional branch example:** Assume `x1 = a, x2 = b, x3 = c` ```C if (a < b) { // bge x1, x2, else c = a + 1; // addi x3, x1, 1 } else { // beq x0, x0, end ← unconditional jump to end if you executed if branch! c = b + 2; // else: addi ax3, x2, 2 } // end: ``` #### Unconditional branch instructions 1. `jal`: unconditional jump and link [today we'll ignore the linking part of this instruction] - Format: `jal rd, label` - Jump to instruction following `label` - program counter (`pc`) updates to be address of that instruction - Link (next lecture): stored in register `rd` - `jal x3, somewhere` = jump to instruction indicated by label `somewhere`, store link in `x3` 2. `jalr`: unconditional jump via register and link - Format: `jalr rd, offset(rs1)` - Jump to instruction specified by `rs1 + offset` - program counter (`pc`) updates to be address of that instruction - `rs1` is a register, `offset` is a constant - Link (next lecture): stored in register `rd` - Can jump to any 32 bit address - supports long jumps that are not possible with `bne`, `blt`, etc (because size of branches are limited in terms of how much they can jump - limited to the number of bits that I have available for coding constants in my instructions) - ^ because `beq x1, x2, label` is actually `beq x1, x2, offset` to the assembler where `offset = address(label) - address(current instruction)` - And remember: the full instruction `beq x1, x2, label` must only take up 32 bits! Thus causing a jump size limit. - [I] ^ but `jalr` doesn't have this problem! - `jal` still involves a constant: `target = pc + immediate` → `immediate` must fit inside instruction, limiting - `jalr` jumps to any arbitrary address in memory: `target = register + small offset` - e.g: 1. `lui t0, upper_20_bits` : load upper part 2. `addi t0, t0, lower_12` : add lower part 3. `jalr x0, 0(t0)` : jump to full 32-bit address - [*] ^ this mechanism gives us *true arbitrary jumps!* - Instructions are all 32 bits, so `offset + rs1` address must be a multiple of 4 - e.g. `jalr x3, 4(x1)` = jump to instruction indicated by `x1 + 4`, store link in `x3` ### Revisit - let's sum an array! ![[full array sum coe.png|400]] - `bge x5, x7, end` implements exiting the loop when `i >= arr_len` - `jal x0, loop` repeats the loop ## Instruction encoding > Now let's address - *How do we actually turn these assembly instructions into binary instructions?* - **Machine language** is the *binary encoding* of assembly instructions - Binary encoding - just like integers, floats, other data types! Everything is bits - All RV32I instructions are **4 bytes** (32 bits) - [?] How do we translate between assembly and instruction encodings? **RISC-V ISA tells us exactly how!** - [i] **6 main types** of instruction encodings: ![[isa reference card.png|600]] - `opcode` = "operation code" = tells the CPU: what *kind* of instruction is this? - e.g., load (`lw`), store (`sw`), arithmetic (`add`, `sub`)... - `funct3/funct7` = specific operation within that category ^ - e.g. `add` and `sub` use the same opcode (R-style arithmetic) - how do we distinguish them? use `funct3` and `funct7`! - `funct3`: subcatgory - `funct7`: final disambiguation - R: register instructions - I: register immediate computational - B: branch - U: lui - J: jump **Full instruction set:** ![[RV32I base instruction set.png|600]] ### R-type: Register-register instruction format ![[isa decoding.png|500]] - Why do we use 5 bits for the registers? - Because we have 32 registers! → need 0-31 to specify all of them → 5 bits to specify a register ### I-type: Register-immediate instruction format ![[isa opcode decoding.png|500]] - Why do we use 12 bits for the constant? - Because we only have 12 bits left out of the 32 bits an instruction can take up - we need all the other ones for specifying registers, instruction type, etc.! ### Other types? In recitation! ## Applying all these ideas! > Suppose you're walking down the street and you come across the following blocks in memory: | Address | Data | | --------- | ------------------------------------ | | `0x10FA0` | `0b00100000100100000000001010010011` | | `0x10FA4` | `0b00001011000100000000001100010011` | | `0x10FA8` | `0b00000000010100110100001010110011` | - What does it mean ^? *Depends on how we're supposed to interpret it!* - If the value at `0x10FA0` is an ==**unsigned int**==: - ![[address eg assembly vs data.png|500]] - If the value at `0x10FA4` is four `uint8_ts` in an **==array==**: - ![[assembly vs data 2.png|500]] - If the value at `0x10FA8` is a ==**float**==: - ![[address vs data 3.png|500]] - [?] *How do we know if the value at `MEM_ADDRESS` is data or an instruction?* - [i] If the **program pointer** points to some `MEM_ADDRESS`, it is interpreted as an *instruction*! - If the value at `0x10FA0` is an ==**instruction**==: `0010011` (last 7 bits) = register immediate (from ISA sheet) - [!] **THE COLORING BARS IN THE BELOW FIGURES ARE OFF, DO NOT READ BASED ON THAT** - ![[decoding binary to instruction 1.png|500]] - **==Instruction==** at `0x10FA4`? - ![[decoding binary to instruction 2.png|500]] - `0010011` = register immediate - `00110` = 6 → `rd = x6` - ... - Instruction at `0x10FA8`? ``` 0b 0000000 00101 00110 100 00101 0110011 funct7 rs2 rs1 funct3 rd opcode ``` - opcode: `0110011` = R-type instruction! (reg-reg) according to ISA sheet - `rd = 00101 = 5` → register `x5` (save to `x5`) - `funct3 = 100`, `funct7 = 0000000` → `xor` operation according to ISA sheet! - `rs1 = 00110 = 6` → register `x6` - `rs2 = 00101 = 5` → register `x5` - [*] ^ combined: `xor x5, x6, x5` ### Data memory vs. instruction memory - Data will live in one part of the memory - Program (instructions) will live in another part of the memory. - Instruction memory is usually write-protected (don't want to change program during runtime) ### Looking into the future ;) - Pseudoinstructions: not *real*! - While writing assembly, these can save a few keystrokes or lines - makes life for the programmer easier! (concept similar to keyboard shortcut commands) - Registers and their names: - The registers all have "symbolic names" which more accurately reflect their expected usage and "conventions" we must adhere to when using them - [!] Instruction encodings (machine code) *always* use the `x`-register! - (i.e., the hardware only knows registers as numbers `x0`-`x31` -- not names like `sp`, `ra`, `t0` etc. [these latter symbolic names are for us humans, not for the machine]) - We'll cover these next week! > Next lecture: Implementing procedures in assembly. # Recitation 4 ## Translating C to Assembly Assume `a` is stored at address `0x1000`, `b` is stored at `0x1004`, `c` is stored at `0x1008`. All values are 32-bit signed integers. - How to execute `a = b + 3 * c`? ```python # 1. Load input variables into registers # THIS WILL NOT WORK: addi x5, x0, 0x1000 → intermediate cannot be more than 12 bits! # ^ use lui instead lui x5, 0x1 # auto shifts 12 bits to the left → 0x1 << 12 = 0x1000 lw x6, 4(x5) lw x7, 8(x5) # 2. Calculate a = b + 3*c slli x8, x7, 1 add x8, x8, x7 add x8, x8, x6 # 3. Store result into memory location for a sw x8, 0(x5) ``` - How to execute: `if (a > b) { c = 17; }`? ```python # 1. Load input values into registers lui a1, 0x1 lw a2, 0(a1) #a lw a3, 4(a1) #b # 2. Branch to end if a <= b (or b >= a) bge a3, a2, end # 3. Prepare result addi a4, x0, 17 sw a4, 8(a1) # c = 17 end: ``` - How to execute: ```C int sum = 0; for (int i = 0; i < 10; i++){ sum += i; } ``` ```python addi a1, zero, 0 addi a2, zero, 0 addi a3, zero, 10 loop: add a1, a1, a2 # a1 = a1 + a2 or sum = sum + i addi a2, a2, 1 # i = i+1 blt a2, a3, loop # branch to beginning of loop body ``` - Translate: ```C for (int i = 0; i < 10; i++) { c[i] = a[i] + b[i]; } ``` ```python lui a1, 0x1 addi a1, a1, 0x100 # a1 = address of a[0] lui a2, 0x2 # a2 = address of c[0] addi a3, zero, 0 # a3 = 0 (i) addi t1, zero, 10 loop: slli a4, a3, 2 # a4 = 4 * i add a5, a1, a4 # a5 = address of a[i] add a6, a2, a4 # a6 = address of c[i] lw a7, 0(a5) # a7 = a[i] lw t2, 0x100(a5) # t2 = b[i]; b is offset from a by 0x100 add a7, a7, t2 # a7 = a[i] + b[i] sw a7, 0(a6) # c[i] = a[i] + b[i] addi a3, a3, 1 # i = i + 1 blt a3, t1, loop # branch back to loop if i < 10 ``` # Lab 4: Assembly > All C functions ultimately get assembled into assembly code. On the ESP32, these instructions get compiled into **RISC-V** assembly language. ## 4.2) RISC-V Assembly & PlatformIO ### 4.2.2) Handling function arguments & return values - [i] Assembly doesn't have variable names: just **32 registers** - The same registers are always dedicated to holding function argument and return values: - Function arguments: `a0`-`a7` - Function return values: registers `a0`-`a1` - Function arguments must be placed in these specific registers *before* the function is called: - First argument goes in `a0`, second goes in `a1`, ... - Function return values must be placed in the dedicated registers before the function returns (via the `jalr x0, 0(ra)` instruction) - Most functions return only one thing, and that goes in register `a0` - If there is a second return value, that is placed in `a1` e.g. ```C int pinRead(int pin_num) { // pinRead code here return val; } ``` 1. **Before any call** to `pinRead()`, the generated assembly program would put the value `pin_num` in register `a0`. If there happened to be a 2nd argument, that would be placed in `a1`. A third argument would be placed in `a2`... and so on until `a7`. ==Order matters here==! 2. **Before returning** from `pinRead()`, the assembly program would place the return value (in this case the bit value read from the GPIO pin) in register `a0` ### 4.2.3) Assembly (.S) files **Header:** ```nasm .section .text # indicates a code segment .align 2 # specifies how data should be arranged in memory //.globl pinSetup # makes pinSetup able to be used outside of this file .globl pinWrite # makes pinWrite able to be used outside of this file .globl pinRead # makes pinRead able to be used outside of this file .globl setPixel # makes setPixel able to be used outside of this file .globl eraseBuffer # makes eraseBuffer able to be used outside of this file ``` > Assembly uses `#` for comments (C uses `//`) - Some things to know: - `jalr x0, 0(ra)` instruction is how the program will return from each procedure - this should be the *last* instruction in each procedure - if you delete it, the program will not return!! - base instruction set list: https://llp.mit.edu/6190/_static/S26B/resources/references/riscv_isa_reference.pdf - once you start using control flow instructions (e.g. branching and jumping), you'll need to add **labels** to your program. - because all of these procedures are located within the same file, you should not use the same label name twice! ## 5) GPIO in Assembly ### 5.1) Accessing memory using assembly - [!] **There are only two RISC-V assembly instructions that interact with memory:** - "load word" `lw`: reads a 32-bit value from a given memory location - "store word" `sw`: writes a 32-bit value to a given memory location ```C int *mem_address = 0x20000000 // the value of interest is stored at address 0x20000000 int value_at_mem_address = *mem_address ``` ^ in assembly, this would look like: ```python lui a3, 0x20000 #load value 0x20000000 into register a3 (a3 = 0x20000000) lw a4, 0(a3) #load 32-bit value stored at memory address 0x20000000 (a3) plus an offset of 0 into register a4 (a4 <= Mem[0x20000000]) ``` - What if we wanted to access the 32-bit value stored at memory address 0x20000004? Rather than performing another `lui` instruction, we can just use an offset in our `lw` instruction: ```python lw a5, 4(a3) # load 32-bit value stored at memory address 0x20000004 (a3) plus an offset of 4 into register a5 (a5 <= Mem[0x20000004]) ``` > ^ this offset **must** be an immediate -- even if the offset is 0! - [i] In assembly, we'll be working exclusively with **32-bit** values - So, adjacent memory locations (e.g. array) will be 4 bytes away from each other e.g. ```C int arr[3] = {0, 1, 2}; // &arr = 0x20000000 ``` - ^ `arr[0]` would be stored in memory at address 0x20000000, `arr[1]` would be at address 0x20000004, and `arr[2]` would be at address 0x20000008. - [?] **What if we wanted to modify the value stored at a given address?** - ^ in C: ```C int *mem_address = 0x20000000 // we want to write something to address 0x20000000 *mem_address = 7; // write the number 7 to memory address 0x20000000 ``` - ^ in assembly: ```python lui a3, 0x20000 #load value 0x20000000 into register a3 (a3 = 0x20000000) addi a4, x0, 7 #notice how we can also use decimal encoding? doesn't need to be hex (a4 = 7) sw a4, 0(a3) #store 32-bit value from register a4 (7) in memory address 0x20000000 (Mem[0x20000000] <= 7) ``` ```python sw a3, 0(a0) # storing what is at a3 to address a0 ``` ## 6) Updating LED display using Assembly > *Let's explore how to work with arrays using Assembly!* - Let's translate `eraseBuffer` from C to Assembly. ```C void eraseBuffer() { /* Function that clears screen buffer by setting all bits to 0. */ for (uint8_t i = 0; i < 8; i++) { screen_buffer[i] = 0; // set all 32 bits to 0 } } ``` ```python eraseBuffer: addi a1, x0, 8 # upper bound on for loop addi a2, x0, 0 # "i" in for loop looping: slli a3, a2, 2 # calculate 4*i add a4, a0, a3 # get address of array element by adding base address + 4*i sw zero, 0(a4) # write 0 to memory address addi a2, a2, 1 # increment i bne a2, a1, looping # continue looping if i < 8 jalr x0, 0(ra) # return from eraseBuffer ``` - Notes: - 32-bit architecture, so `memory_addr_of_arr_element_i = array_start_addr + 4*i` - Every array element is an `int`, which is 4 bytes. - Use `sw` instruction to *write* the value 0 to this location in memory, effectively doing `screen_buffer[i] = 0` ^ Memory looks like: ``` Address: 1000 1001 1002 1003 ... Content: [byte] [byte] [byte] [byte] ``` - We have *==byte-addressed== memory*, so addresses of adjacent words are 4 apart: 1 word = 32 bits = 32/8 → 4 addresses - [I] **Crucial idea:** Addresses themselves are just labels → the **hardware** defines that each +1 address points to the next byte (8 bits). - [!] `0x1000, 0x1001, 0x1002` are just numbers: `0x1001 = 0x1000 + 1`, etc. Nothing about "8 bits" is inherent about adding these hex numbers themselves. **The address difference is 1, but the data units they index are 1 byte = 8 bits each.** RISC-V defines that memory is byte-addressed, which is how we interpret the address labels `0x1000` to map to actual data. The hardware is built to match these schemas. - [!] **KEY INSIGHT:** `lui a7, 0xFFFFF` + `addi a7, a7, 0xFFF` **does not** give you all F's `0xFFFF_FFFF`!!!!!! Because adding is *signed* in RISC-V - Instead, to get `0xFFFF_FFFF`, this is -1 in signed binary → do `addi a7, x0, -1` # Postlab 4 ## Collatz - [!] TODO: Read into how this works more! Was super cool! ## Bubble sort ```python bubblesort: # a0: first memory address of array (DO NOT MODIFY) # a1: length of array addi a2, x0, 1 # swapped = 1 loop: beq a2, x0, end # if swapped == 0, end sort addi a2, x0, 0 # swapped = 0 addi a3, x0, 0 # i = 0 jal x0, innerloop innerloop: addi a7, a1, -1 # a7 = n - 1 bge a3, a7, end_step # if i >= n - 1 go to loop end # loop not ending yet slli a4, a3, 2 # a4 = i*4 (integers are 4 bytes) add a4, a4, a0 lw a5, 0(a4) # p[i] lw a6, 0x4(a4) # p[i + 1] addi a3, a3, 1 blt a6, a5, conditional jal x0, innerloop conditional: sw a6, 0(a4) # p[i] = p[i+1] sw a5, 0x4(a4) # p[i+1] = p[i] # LED UPDATE CODE START addi sp, sp, -36 sw a0, 0(sp) sw a1, 4(sp) sw a2, 8(sp) sw a3, 12(sp) sw a4, 16(sp) sw a5, 20(sp) sw a6, 24(sp) sw a7, 28(sp) sw ra, 32(sp) jal ra, arrayViz lw a0, 0(sp) lw a1, 4(sp) lw a2, 8(sp) lw a3, 12(sp) lw a4, 16(sp) lw a5, 20(sp) lw a6, 24(sp) lw a7, 28(sp) lw ra, 32(sp) addi sp, sp, 36 # LED UPDATE CODE END addi a2, x0, 1 # swapped = 1 jal x0, innerloop end_step: addi a1, a1, -1 # n = n-1 jal x0, loop # return to while loop end: jalr x0, 0(ra) ``` # Exercises 4 ## RISC-V Assembly ```python addi a1, a2, 9 # a1: 9 lui a2, 3 addi a3, x0, 3 sub a3, a3, a1 # 0xFFFFFFFA slt a4, a3, zero # a4: 1 sltu a5, a3, zero # a5: 0 addi a4, zero, 1 # a4 = 1 beq a5, zero, L1 # jump to L1 slli a4, a4, 2 L1: slli a4, a4, 5 # a4 << 5 = 0x1 << 5 = 0x100000 lui a0, 2 lw a1, 8(a0) addi a2, a1, 4 sw a2, 0(a0) # writes to memory location 0x00002000 unimp # special instruction that tells the processor to stop running . = 0x2000 .word 0x12345678 # resides in memory location 0x2000 .word 0xDEADBEEF # resides in memory location 0x2004 .word 0x50505050 # resides in memory location 0x2008 ``` - `.` sets the current location counter - think: "where am I writing in memory?" - tells the computer: "next thing goes at address `0x2000`" - `.word` tells the computer to store a 32-bit value (4 bytes) into memory - ^ this last chunk is essentially the same as writing the below code in C: ```C int* ptr = (int*)0x2000; // = interpret number 0x2000 as a pointer to an int ptr[0] = 0x12345678; ptr[1] = 0xDEADBEEF; ptr[2] = 0x50505050; ``` ### Part 2 ```python lui a0, 0x2 addi a7, x0, 0 lw a1, 0(a0) L1 : andi a2, a1, 1 beq a2, zero, L2 addi a7, a7, 1 L2 : srli a1, a1, 1 bne a1, x0, L1 unimp . = 0x2000 .word 0x12345678 ``` - Execution begins with the first instruction `lui a0, 0x2` which initializes register `a0` to `0x00002000`. The next instruction sets register `a7` to `0`. - What does the `lw a1, 0(a0)` instruction write into register `a1` (answer in 32-bit hexadecimal format like 0x`0CDEF1AF`)? - `0(a0)` = value stored at memory address `a0` = `0x12345678` - Now consider running the code to completion when it reaches the `unimp` instruction. - How many times will the loop in this code (the loop consists of the `andi a2, a1, 1` instruction through the `bne a1, x0, L1` instruction) be executed? (answer in positive integer format) [REDO THIS QUESTION] - What will be the value inside the register `a7` when the execution reaches the `unimp` instruction? (answer in 32-bit hexadecimal format like 0x`0CDEF1AF`) 0x [REDO THIS QUESTION] ## RISC-V Instruction encoding - [i] Not all immediate bits are encoded: missing lower bits are filled with 0s and missing upper bits are sign extended [CONFIRM WHAT THIS MEANS SOMETIME] - [I] `srai` and all the immediate shift instructions only use 5 bits (instead of the 12 available when we do regular I-type instructions such as `addi`) because you **can only shift a 32-bit by 0-31 positions**! - so you don't need 12 bits! - For `jal` and branch instructions (`beq, bne, blt, bge, bltu, bgeu`), the immediate encodes the target address as an offset from the current pc: `pc + imm = label` - e.g. What is the 32-bit binary encoding of the instruction `bge x2, x3, label` if label is 4 instructions after the current instruction (pay close attention to how the branch offset gets encoded)? 0b - `imm = 4*4 = 0100` → in 12 bits: (this side is index 12) `0000_0001_0000` (this side is index 1) - label is 4 instructions after: 4 instructions * 4 bytes / instruction = 16 bytes - we measure in units of bytes because **almost all architectures (RISC-V, x86, ARM)** are ==byte-addressed==: every byte in the RAM has its own unique address. Since the program counter is the register that points to the "current address" of the instruction being executed, that address is a byte address - since bit 0 of the offset is guaranteed to be 0 (all instructions must be at least 2-byte aligned - every possible branch target address will always be an even number, and even numbers always end in 0 in binary) → so we drop `imm[0]` from representation for maximal compression - ![[bge instruction isa.png]] - `0000000_00011_00010_101_1000_0_1100011` - What is the 32-bit binary encoding of the instruction `sw x6, 8(x2)`? 0b - ![[sw instruction isa.png]] - `imm = 8 = 0000_0000_1000` - `0000000_00110_00010_010_01000_0100011` - Consider the 32-bit binary value 0b0000000_00000_00001_110_00101_0010011. If you interpret this number as the encoding of a risc-v instruction, which instruction does this encoding translate into? - `0b0000000_00000_00001_110_00101_0010011` - `ori` - `rd = 00101 = x5` - `rs1 = 00001 = x1` - `imm[11:0]` = all 0's - putting together: `ori x3, x1, 0` ## Binary to instructions `0b0000000_01110_01101_000_01100_0110011` - `add` - `rd = x12` - `rs1 = x13` - `rs2 = x14` - put together: `add x12, x13, x14` `0b0100000_01110_01101_000_01100_0110011` - `sub` - same as above: `sub x12, x13, x14` `0b111101010111_01101_011_01100_0010011` - `sltiu` - `rd = 01100 = 12` - `rs1 = 01101 = 13` - `1111_0101_0111 = F97` `0b111101010111_01101_010_01100_0010011` - `slti` - `rd = x12` - `rs1 = x13` - `111101010111 = F97` # Lecture 5: Compiling code & implementing procedures ## Components of a RISC-V processor - **Register file:** `x0...x31` - **ALU:** arithmetic logic unit (where actual computations are done) - **Main memory:** give it address, and it fetches the corresponding data - Holds program & data > To transport data between register and main memory, we have two operations: load word `lw` (memory → register) and store word `sw` (register → memory). - [*] *Special register:* **program counter** - Program counter holds the *address* of the location and memory where we're going to find our next instruction. - ^ When you go to that location, you'll find the instructions & data - [i] **Memory holds both data and instructions.** We determine whether an address to something in memory is data or instructions by seeing whether or not the pc points to it (if pc points to it, then we interpret it as an instruction! otw as data) ## RISC-V instruction types - [*] 3 types! 1. **Computational instructions** executed by ALU - Register-register: `oper rd, rs1, rs2` - Register-immediate: `oper rd, rs1, constant` - `constant` is 12 bits! - What if the value we have in register `rs1` is more than 12 bits? How do we do operations on things of different sizes (`rs1` & `constant)? - We pad `constant` (pad in a sign-extend MSB manner: 0s if positive, 1s if negative) to 32 bits - `lui rd, luiConstant` (20-bit) - ^ This instruction takes 20-bit `luiConstant`, left-shifts it by 12 bits, and fills in the right-most 12 bits with 0s - [i] The computational instructions have a register that they *write* to! 2. **Loads & stores:** - `lw rd, offset(rs1)` - `sw rs2, offset(rs1)` - [i] Store word doesn't write to a register! - Memory address = Reg[`rs1`] + sign_extend(`offset`) 3. **Control flow instructions:** - Conditional: `comp rs1, rs2, label` - [!] ^ limited to `label` address (which is computed as an `offset` from current program counter value) being *12 bits only*! - Unconditional: `jal rd, label`and `jalr rd, offset(rs1)` - [*] `jalr` is a way we can have the conditional jump to somewhere that requires more than 12 bits to specify the address offset from pc - [i] PC register gets updated in control flow instructions! - Normally, after each instruction, `pc++` - If a control flow instruction is used, `pc = address of label` 4. **Pseudoinstructions:** - Not "real" but they make our lives easier! - They are converted into actual RISC-V instructions when being assembled into machine code. ![[isa pseudoinstructions.png]] ## Pseudoinstructions > Pseudoinstructions are *converted* to actual RISC-V instructions. | Pseudoinstruction | Equivalent assembly instruction | | ------------------- | ----------------------------------- | | `mv x2, x1` | `addi x2, x1, 0` | | `ble x1, x2, label` | `bge x2, x1, label` | | `j label` | `jal x0, label` | | `li x2, 3` | `addi x2, x0, 3` | | `li x3, 0x4321` | `lui x3, 0x4`, `addi x3, x3, 0x321` | - [i] ^ `li` pseudoinstruction translates into either one or two instructions depending on size of constant ## Data memory vs. instruction memory - Instructions & data are stored as **32-bit** binary values in memory - Data lives in one part of the memory, the program (instructions) live in another part of the memory - [*] Instruction memory is usually write-protected (to avoid changing program during run-time) - `lw` and `sw` operations access data memory only (not program memory!) ## Review: Program counter > The **program counter** (pc) register keeps track of the address of your next instruction. - *Default* (non control-flow instructions): `pc = pc + 4` - `+4` because each instruction is 32-bits = 4 bytes, and memory is byte-addressed! So move down 4 bytes in memory to get to the next instruction. - Control flow instructions might update `pc` by a different amount ```python . = 0x0 # this indicates that the immediately following instruction is at address 0x0 blt x1, x2, label addi x1, x1, 1 label: lw x3, 0x100(x0) . = 0x100 .word 0x12345678 # at address 0x100, we have this data word 0x123... ``` ![[how addresses are stored with ..png]] - [?] If we do a jump to label, what address is label representing? - `0x8` (because `pc` was initially 0 → so offset between `0x0` and `0x8` is `0x8`)! So if the condition is met, we set `pc = 0x8` for the jump - How does `lw` work? - `lw x3, 0x100(x0)` means that we load value from memory location `0x100+0 = 0x100`→ so this instruction essentially sets `x3 = 0x12345678` ## Compiling conditional statements > Compiling `if-else` statements in assembly! - C code: ```C if (expr) { if-code; } else { else-code; } ``` - Let's start with an example (part of GCD code): ```C if (x > y) { x = x - y; } else { y = y - x; } ``` - We'll use `x10` for `x` and `x11` for `y` (registers) ```python slt x12, x11, x10 # 1 if reg[x11] < reg[x10], 0 otw beq x12, x0, else # fall through to if-code sub x10, x10, x11 # x = x - y j endif # unconditional jump to the end else: # reg[x10] >= reg[x11] sub x11, x11, x10 endif: ``` - [I] *General recipe for compiling `if-else` statements in assembly:* 1. Compile `expr` into register `xN` 2. Conditional branch instruction that will jump to `else` when `expr` is 0 3. Compile `if-code` into assembly 4. Add unconditional jump past `else` branch 5. Compile `else-code` into assembly - [!] But the above recipe required storing `expr` result into some register before jumping - can we skip this step? - Can also do: ```python ble x10, x11, else sub x10, x10, x11 j endif else: sub x11, x11, x10 endif: ``` - [*] *Alternative recipe* ^: ==[this is the one you should use!== 1. Conditional branch instruction that will jump when the *opposite* of `expr` is true 2. Compile `if-code` into assembly 3. Add unconditional jump past `else` branch 4. Compile `else-code` into assembly ## Compiling loops ```C while (expr) { loop-code } ``` - [*] Recipe 1: 1. Conditional branch instruction that will jump past loop body when opposite of `expr` is true 2. Compile `loop-code` into assembly 3. Add unconditional jump to top of loop at end of `loop-code` - Example: ```C while (x != y) { if (x > y) { x = x - y; } else { y = y - x; } } ``` ```python loop: beq x10, x11, endloop # loop content ble x10, x11, else sub x10, x10, x11 j endif else: sub x11, x11, x10 endif: # unconditional jump to top of loop j loop endloop: ``` - [!] Notice that for Recipe 1 of writing while loops, we have two conditionals (branch)! Control flow instructions are actually the most expensive ones. Can we make it cheaper? - [*] (Compiling loops...another way!) Recipe 2: 1. Compile `loop-code` into assembly 2. Put a conditional branch instruction after `loop_code` that jumps to the top of loop when `expr` is true 3. Before starting loop, jump to that conditional branch instruction ```python j compare loop: ble x10, x11, else sub x10, x10, x11 j endif else: sub x11, x11, x10 endif: compare: bne x10, x11, loop ``` - [I] ^ now we only have a single control flow instruction (`ble`) repeated inside the loop! ## Procedures > *What if we wanted to write a `gcd` function that we could use throughout a program?* - [*] Encapsulate code into a procedure! ```C int gcd(int a, int b) { int x = a; int y = b; while (x != y) { if (x > y) { x = x - y; } else { y = y - x; } } return x; } ``` ### Introduction to procedures > A **procedure** (aka. function, subroutine) is a reusable code fragment that performs a specific task. It has the following key components: - Single named entry point - Zero or more formal arguments - Local storage - Returns to the caller when finished - [?] *Why use procedures?* Because they enable **abstraction** and **reuse**! - Compose large programs from collections of simple procedures - [*] **2 players: caller & callee** - When one procedure is called by another, a relationship is created between two procedures: - ==Caller==: the procedure that was called by the other procedure - ==Callee==: the procedure that was called by the caller ```C int coprimes(int a, int b) { return gcd(a, b) == 1; } void app_main() { int a = 5; int b = 10; int x = coprimes(a, b); ... } ``` - ^ `gcd(a, b)`: `coprimes` is the **caller**, `gcd` is the **callee** - `coprimes(a, b)`: `app_main` is the **caller**, `coprimes` is the **callee** > A procedure can be *both* a caller and a callee! Depends on which procedure call we're talking about. - [?] **Procedures introduce many questions:** 1. How to transfer control to callee and back to caller? 2. How to communicate arguments and return values? 3. How to let procedures use more storage than can fit in registers? 4. What if the caller and callee need to use the same register? ### How to transfer control to callee and back to caller? - Hypothesis: Callee could use an unconditional jump construction to get to the callee procedure... - [!] But the callee could be called from multiple places in a program! - [?] So how would the callee know where to return to? - [I] **Fix:** ==Return address==! > **Return address (`ra`):** Register `x1` (symbolic name `ra`) is used to hold a procedure's return address. Once finished with a procedure, the *callee* will use `ra` to jump back to the correct instruction within the *caller* procedure. - [?] *How do we use `ra` to get back to the correct spot in the caller?* **Jump and link!** #### Jump and link - `jal`: unconditional jump and link - Format: `jal rd, label` - Jump to instruction at `label` - `pc` register updates to be address of that instruction - **Link:** stored in register `rd` - The *link* is the address of the instruction after the `jal` instruction (`rd = pc + 4` prior to updating `pc`) - [*] This is how we remember where we came from! ```python jal x1, label # jump to instruction following label addi x7, x7, 1 # x1 holds address of addi instruction ``` - Example: `jal ra, sum` - When calling a procedure, we store the link in `ra` ```python proc: ... [0x100] jal ra, sum # ra = 0x104 ... [0x678] jal ra, sum # ra = 0x67C ``` - ^ Equivalent pseudoinstructions: `jal sum`, `call sum` - [I] CPU transfers "control" to callee by moving the `pc` to the address of the callee's instructions - [?] *How can the callee use `ra` to return back to the caller?* #### Jump and link register - `jalr`: unconditional jump via register and link - Format: `jalr rd, offset(rs1)` - Jump to instruction stored at address `Reg[rs1] + offset` - `pc` updates to be address of that ^ instruction - **Link:** stored in register `rd` - The *link* is the address of the instruction after the `jalr` instruction (`rd = pc + 4` prior to updating `pc`) - [*] Again, this is how we remember where we came from pre-jump! - [I] How to transfer control back to the caller? **Use `jalr x0, 0(ra)`**! - `ra` indicates where the program should return to - [!] This works as long as `sum` was *called using* `jal ra, sum` or equivalent, and `ra` *hasn't been overwritten since*!! - Store link in `x0` → effectively discards it! We have no need to remember that we came from the end of a procedure. ``` python proc: ... [0x100] jal ra, sum # ra = 0x104 ... [0x678] jal ra, sum # ra = 0x67C # ---- sum: ... jalr x0, 0(ra) ``` - Equivalent pseudoinstructions to `jalr x0, 0(ra)`: - `jr ra`, `ret` #### Summary - **To call a procedure:** `jal ra, label` - Equivalent pseudoinstructions: - `jal label` - `call label` - [!] These all assume by *default* that you're storing the link in the `ra` register - **To return from a procedure:** `jalr x0, 0(ra)` - Equivalent pseudoinstructions: - `jr ra` - `ret` - [!] Again assume by *default* that return value is stored in memory at address `ra` & that we throw out the link (i.e., set `x0` to it) because we have no need to remember the position at the end of a procedure. ### How to communicate arguments and return values? - [?] How does the callee know which register to look for a specific argument in, and how does the caller know which registers contain the return value? - **We need some rules!** > A **calling convention** specifies rules for register usage across procedures. - RISC-V calling convention gives *symbolic names* to registers `x0-x31` to denote their role. - Certain registers are specified to hold function arguments and return values | Symbolic name | Registers | Description | | ------------- | -------------- | ---------------------- | | `a0` to `a7` | `x10` to `x17` | Function arguments | | `a0` to `a1` | `x10` to `x11` | Function return values | #### RISC-V Function Arguments - [i] Registers `a0-a7` (`x10-x17`) are used as function arguments - First argument goes in `a0`, second in `a1`, ... - If a function has more than 8 arguments, the extra ones will be passed via memory - *more on this later!* - [!] The caller must put function arguments in the necessary registers **before** calling a procedure - this way the callee can find them! ```C int coprimes(int a, int b) { return gcd(a, b) == 1; } // coprimes responsible for making sure a0 = a, a1 = b *before* calling gcd int gcd(int x, int y) { ... } // so that gcd can assume a0 = x, a1 = y ``` #### RISC-V Return Values - [i] Registers `a0-a1` (`x10-x11`) are used as function return values - First return value goes in `a0`, second in `a1` - If a function **has more than ==2== return values**, the extra ones will be returned via specific slots in memory - *more on this later!* - [!] The callee is responsible for putting return values in the necessary registers before returning ```C int gcd(int x, int y) { ... } // gcd responsible for putting val in a0 before returning int coprimes(int a, int b) { return gcd(a, b) == 1; } // so coprimes can assume gcd(a,b) will be in a0, ready to use ``` > **Responsibility enables assumptions:** The callee and caller don't need to know the implementation details of each other - they can work together solely by following the *shared set of rules* defined by the **calling convention.** ### How to let procedures use more storage than can fit in registers? - Storage problems: - **Running out of registers:** There are only 32 registers, and all procedures need to be able to use the same 32 registers - need to *manage register usage across different procedures* to share them! - **Registers dedicated to certain things:** Only 8 registers dedicated to holding function arguments - what if a procedure has 9? Same for function return vals (except only 2 dedicated registers). - [b] **TL;DR solution:** Use a special section of memory! ### RISC-V Stack - Section of memory - Grows *down* from higher to lower addresses - `sp` register points to the top of the stack ![[stacks grow from high to low addr.png|200]] - [i] **2 operations:** `push` and `pop` - **Push:** put something on top of stack 1. `addi sp, sp, -4` ← allocate space for a 32-bit word 2. `sw a1, 0(sp)` ← put element on - **Pop:** take something off top of stack 1. `lw a1, 0(sp)` ← take element off 2. `addi sp, sp, 4` ← deallocate space #### Using the stack - A program must use the stack in a Last-In-First-Out (LIFO) manner - The most recent thing added to the stack will be the next thing taken off - [!] Any procedure may use the stack, but it must *leave the stack as it found it!* 1. Anything that goes on the stack must get taken off by the time the procedure returns. 2. `sp` must be reset to the value that it was at the beginning of the procedure. ![[push vs pop stack.png|400]] #### How to let a procedure use more memory than can fit in registers? > An **activation record** holds all storage needs of a procedure that do not fit in registers. The entire region of the stack that a particular procedure uses is its activation record. - A new activation record is put on the stack when a new procedure is called (the program creates a *new block of memory on the stack* for this specific function call) - That activation record is taken off the stack when that procedure returns 1. its stack frame is removed (deallocate space) 2. the stack pointer `sp` moves back 3. control returns to `main` - [b] Activation records go on the stack LIFO: the current procedure's activation record (aka. **stack frame**) is always at the top of the stack - [I] Intuition: activation record of a procedure = all the local storage a procedure needs - [i] When you're inside a procedure, the stack pointer is always pointing to your procedure's activation record! ![[LIFO stack.png|400]] ### What if the caller and the callee need to use the same register? > RISC-V calling convention **specifies rules for sharing registers** among different procedures. #### Calling convention - If a register will (potentially) be overwritten across a function call, its value must be saved on the stack - The caller procedure is responsible for saving some registers & the callee procedure is responsible for saving others. - RISC-V ISA tells us which ones are which! ![[isa calling convention.png|600]] - RISC-V calling convention gives symbolic names to registers `x0-x31` to denote their role: | Symbolic name | Registers | Description | Saver | | ------------- | ---------------- | ---------------------- | ------ | | `a0` to `a7` | `x10` to `x17` | Function arguments | Caller | | `a0` and `a1` | `x10` and `x11` | Function return values | Caller | | `ra` | `x1` | Return address | Caller | | `t0` to `t6` | `x5-7`, `x28-31` | Temporaries | Caller | | `s0` to `s11` | `x8-9`, `x18-27` | Saved registers | Callee | | `sp` | `x2` | Stack pointer | Callee | | `gp` | `x3` | Global pointer | --- | | `tp` | `x4` | Thread pointer | --- | | `zero` | `x0` | Hardwired zero | --- | ==Reasoning behind why each of these registers are the responsibility of the caller vs. callee:== - Temporaries are registers used for short-term scratch work during computation (intermediate calculations, loop counters, short-lived helper values, values that do not need to survive a function call) - These are **caller-saved** because the callee is free to overwrite them - if the caller wants to keep them across a function call (i.e., caller does `xyz` work stored in temporary registers, then calls `proc`, then still wants values from `xyz` work), the caller must save them first. - ^ vs: Saved registers are values that must survive procedure calls - if a caller stores a value in a saved register, it is expecting this value to be "long-lived" and to still be there after calling other procedures. - So these are **callee-saved**! - `gp, tp, zero` are special-purpose registers that follow fixed conventions, not normal save/restore rules - How to remember which registers are caller-saved vs. callee-saved: - Caller-saved: procedure's attitude toward these registers = "I might destroy this, save it if you care" - arguments, temporaries, return address - Callee-saved: "I promise to give this back unchanged" - saved registers, stack pointer #### Caller-saved registers (`aN`, `tN`, `ra`) - [!] These registers are **not preserved across a procedure call!** - The callee can use them freely → the caller doesn't know what registers the callee will use, so *it must assume the callee will use all registers.* - ==For a caller to use a caller-saved register:== If the caller needs a caller-saved register's value after the procedure call, it must: 1. *Before calling the procedure:* save the register's value on the stack 2. *After returning from the procedure:* restore the old value from the stack before next using the register > Any callee can use these registers **freely** because it can safely assume the caller will save any register values it will need. #### Callee-saved registers (`sN`, `sp*`) - [*] These registers are **preserved across a procedure call**! - The caller can assume that the register's will be the same *before and after* the procedure call. - ==For a callee to use a callee-saved register:== If the callee wants to use a callee-saved register, it must: 1. *Before using:* save the register's value on the stack 2. *After using:* restore the old value from the stack before returning to the caller - [b] The stack pointer `sp` doesn't go on the stack ^, just needs to be reset to its original value. > Any caller can safely assume that these register values will be *untouched* because the callee will restore them to their original state before returning. #### Summary **Caller:** - Saves any `aN`, `tN`, or `ra` registers *whose values need to be maintained past the procedure call* on the stack prior to the procedure call - Restores them *before using them again* after returning from the callee **Callee:** - Saves original values of `sN` registers on the stack *before using them* in a procedure. - Must restore `sN` registers and stack pointer when done using them, *before exiting procedure.* ### Examples - Example: Using **callee-saved** registers: - Implement `f` using `s0` and `s1` to store intermediate values: (`s0` and `s1` are saved registers that the caller expects to be long-lived!) ```C int f(int x, int y) { return (x + 3) | (y + 0x123456); } ``` - ^ Translate C to assembly: ```nasm f: addi sp, sp -8 # allocate 2 words (8 bytes) on stack sw s0, 0(sp) # save s0 sw s1, 4(sp) # save s1 addi s0, a0, 3 li s1, 0x123456 # load immediate (pseudoinstruction) add s1, a1, s1 or a0, s0, s1 lw s0, 0(sp) # restore s0 lw s1, 4(sp) # restore s1 addi sp, sp 8 # deallocate 2 words from stack (restore sp) ret # pseudoinstruction for jalr x0, 0(ra) ``` - *Core ideas ^*: - `a0` = holds the **return value** - the caller *knows* to check `a0` and `a1` for return values because of RISC-V calling convention - if more than 2 return values, we use pointers to memory! - `ra` = holds the **return address** (where to go back with the program counter) - ^ this is saved when the procedure is called (by the caller): `jal ra, label` ![[stacks before and after procedure call.png|500]] - Example: Using **caller-saved** registers ```C // caller int x = 1; int y = 2; int z = sum(x, y); int w = sum(z, y); // callee int sum(int a, int b) { return a + b; } ``` - ^ Translating C to assembly: ```python li a0, 1 li a1, 2 addi sp, sp -8 # allocate stack frame sw ra, 0(sp) # why?? sw a1, 4(sp) # save y jal ra, sum # a0 = sum(x,y) = z lw a1, 4(sp) # restore y jal ra, sum # a0 = sum(x,y) = w lw ra, 0(sp) # why?? addi sp, sp, 8 # deallocate stack ``` - [?] Some questions: - *Why did we save `a1`?* - Callee may have modified `a1` (caller doesn’t see implementation of `sum`!) - *Why didn't we save `a0`?* - We don't need the original value (`x`) after either procedure call. - *Why did we save `ra`?* - This code is probably also inside some larger procedure! So its `ra` starts out containing `where this procedure should return after it finishes`. - But then this procedure calls `sum`, which overwrites `ra` with the address that `sum` should return to in this procedure. - So we save `ra` before calling `sum` and then restore after the `sum` calls are done → this way, this procedure can later do `ret` and correctly return to *its* caller ### Nested procedures - [!] If a procedure calls another procedure, it needs to save its own return address - Remember that `ra` is **caller-saved** - Example: ```C int coprimes(int a, int b) { return gcd(a, b) == 1; } ``` - Corresponding assembly code ^: ```python coprimes: addi sp, sp, -4 sw ra, 0(sp) # save my own return address (set by code that called coprimes) call gcd # overwrites ra! pseudoinstruction = jal ra, gcd addi a0, a0, -1 # gcd result - 1 sltiu a0, a0, 1 # check unsigned less than 1 (only sets 1 if a0=0) lw ra, 0(sp) addi sp, sp, 4 ret # program will return to the ra address set by code that called coprimes ``` ### Computing with large data structures - How do we pass large data structures (e.g. array) into procedures when the data struct is too large to be stored in registers? - [I] Pass the **base address (pointer to array)** and the **size** of the array as arguments - Example: code to find the maximum element in an array with size elements ```C int main() { int ages[5] = {23, 4, 6, 81, 16}; int max = maximum(ages, 5); } ``` - ^ In assembly: ```python main: li a0, ages li a1, 5 ages: .word 0x17 # at address 0(ages), we have 32-bit word 0x17 .word 0x4 # at address 4(ages), we have 32-bit word 0x4 .word 0x6 .word 0x51 .word 0x10 ``` - C code for finding max of array: ```C int maximum(int *a, size) { int max = 0; for (int i = 0; i < size; i++) { if (a[i] > max) { max = a[i]; } } return max; } ``` - ^ Assembly translation: ```python maximum: mv t0, zero # t0: i mv t1, zero # t1: max j compare loop: slli t2, t0, 2 # t2: i*4 add t3, a0, t2 # t3: addr of a[i]=base+i*4 lw t4, 0(t3) # t4: a[i] ble t4, t1, endif mv t1, t4 # max = a[i] endif: addi t0, t0, 1 # i++ compare: blt t0, a1, loop mv a0, t1 # a0 = max (prepare to return) ret ``` > *Next lecture:* Dynamic memory allocation! # Lab 5: Game of Life - 3 rules of GOL: 1. Any live cell with 2 or 3 live neighbors survives 2. Any dead cell with 3 live neighbors becomes alive 3. All other live cells die in the next generation, and all other dead cells stay dead. - [b] Today: Write `updateBoard` in assembly! - `updateBoard` in C: ```C void updateBoard(uint32_t *current_board, uint32_t *new_board) { eraseBuffer(new_board); // clear board buffer // for each cell in the board for (int y = 0; y < 8; y++) { for (int x = 0; x < 32; x++) { // tally cell (x,y)'s # of living neighbors int neighbor_tally = checkNeighbors(current_board, x, y); // get the cell's current life state int current_cell = getPixel(current_board, x, y); // if 3 neighbors... if (neighbor_tally == 3) { // cell (x,y) is alive in next time step setPixel(new_board, x, y, 1); } // if 2 neighbors and current cell is occupied... else if (current_cell && neighbor_tally == 2) { setPixel(new_board, x, y, 1); //stay alive } // else, do nothing (since we emptied all cells using eraseBuffer call) } } } ``` - Available helpers: - `eraseBuffer`, `getPixel` ## 3.4) Registers and calling convention - `ra`: return address - `sp`: points to top of stack - `t0-t6`: these registers can be used for whatever but *may not* persist after function calls - `s0-s11`: these registers can be used for whatever but *must* persist after function calls - `a0-a1`: hold first two arguments of function call and return values (if needed) - `a2-a7`: hold other arguments for function call (if needed) ### Caller vs. callee - Responsibilities of callee: 1. make sure `sp` has the same value when exiting the procedure as when it entered the procedure 2. every single `s` register must have the same value exiting the procedure as it did when it entered the procedure - Responsibilities of the caller: - `a`, `t` may not be conserved after procedure call - caller need to save what it wants to save - `ra` needs to be saved by caller ## Key notes - Remember to deallocate stack space (restore stack pointer `sp` to original spot when procedure was called) at the end of every procedure!! # Postlab 5: Quicksort ```C int partition(int* p, int start, int end) { int x = p[end]; // select pivot int tmp, i = start - 1; for (int j = start; j < end; j++) { if (p[j] <= x) { i++; # swap tmp = p[i]; p[i] = p[j]; p[j] = tmp; } } # insert the pivot back into its spot # after above loop, i = last index at which p[i] <= p[x] # ^ so p[i+1] > p[x] tmp = p[i + 1]; p[i + 1] = p[end]; p[end] = tmp; return i + 1; } void quicksort(int* p, int start, int end) { if (start < end) { int q = partition(p, start, end); quicksort(p, start, q - 1); // quicksort before pivot quicksort(p, q + 1, end); // quicksort after pivot } } ``` # Exercise 5 ## Pseudoinstructions - Pseudoinstruction → non-pseudo: - `call function_name`→ `jal ra, function_name` - Non-pseudo → pseudo: - `sub a4, zero, a2`→ `neg a4, a2` ## Calling convention - What value is left in register `x3` after execution of this code segment? `addi x3, zero, 0xFF4` - `0xFFFFFFF4` - [i] ^ remember that assembly will sign extend!! ## Calling convention 2 ```python f: # (1) mv a2, a1 mv s0, a1 li a1, 2 # (2) call mul # (3) add a0, a0, a2 add a0, a0, s0 # (4) ret # (5) ``` - At minimum, need to store to the stack 3 things (`ra`, `x`, `y`) - Could store directly or store `s0` and displace `s0` for this procedure ## Symbolic encoding - [?] What is the 32-bit binary encoding of the instruction `jal ra, label` where label is 10 instructions after the current instruction? 0b - `1101111` - `rd` = `ra` = `x1` → `00001` - `imm[31:12]` = 10 instructions → offset of 40 bytes - 40 = `0b101000` - bit 0 is dropped because address instructions are always divisible by 2 (valid address always divisible by 4) ``` imm[20|10:1|11|19:12] in the instruction but interpreted as: imm[20|19:12|11|10:1|0] ``` ``` imm[20|10:1|11|19:12] → 20 bits total total stored 0000_0000_0000_0001_0100 | 0 (implicit 0) 21 1 0000_0010_1000_0000_0000 ``` - ^ combined: `0000_0101_0000_0000_0000_00001_1101111` --- - [?] What is the 32-bit binary encoding of the instruction `lw s1, 4(sp)`? 0b ![[is indices.png]] ![[lw isa.png]] - `0000011` - `rd` = `s1` = `x9` → `9 = 0b1001` → `01001` - `rs1` = `sp` = `x2` → `10` → `00010` - `imm` = `4` = `0000_0000_0100` - Combined: `0000_0000_0100_00010_010_01001_0000011` --- - [?] What is the 32-bit binary encoding of the instruction `beq a2, t6, label` where label is 7 instructions after the current instruction? 0b ![[Screenshot 2026-05-02 at 11.32.47 AM.png]] - `1100011` - `rs1` = `a2` = `x12` = `01100` - `rs2` = `t6` = `x31` = `11111` - `imm` = 7 instructions after = address is 7x4 bits offset: 28 = `11100` - Drops lowest 0: encode `0000_0000_1110` - Combined: `000_0000_11111_01100_000_11100_1100011` --- - [?] What is the 32-bit binary encoding of the instruction `sw t3, 8(a0)`? 0b ![[sw isa.png]] - `0100011` - `rs1` = `a0` = `x10` = `01010` - `rs2 = t3` =`x28` = `11100` - `imm` = `8` = `1000` - (can see on sheet - `sw` does not drop lowest bit (bit 0 is in the instruction binary), immediate is stored) - `0000_0000_0100` - Combined: `0000_000_11100_01010_010_01000_0100011` --- - [?] What instruction does the 32-bit binary value `0b0000000_00101_01010_101_01000_0110011` encode (using symbolic registers)?![[srl isa.png]] - `rs2 = 00101 = x5 = t0` - `rs1 = 01010 = x10 = a0` - `rd = 01000 = x8 = s0` - Combined: `srl s0, a0, t0` ## Stack Detective ```C int fn(int x) { int lowbit = x & 1; int rest = x >> 1; if (x == 0) return 0; else return ???; } // keep going until we hit a lowbit = 0 ``` ```python fn: addi sp, sp -12 sw s0, 0(sp) sw s1, 4(sp) sw ra, 8(sp) andi s0, a0, 1 # x & 1 srai s1, a0, 1 # x >> 1 yy: beqz a0, rtn # if a0 = 0, jump to rtn mv a0, s1 # a0 = x >> 1 jal ra, fn # jump and link to ra = next line, go to fn add a0, a0, s0 # a0 = fn(rest) + lowbit rtn: # restore stack lw s0, 0(sp) lw s1, 4(sp) lw ra, 8(sp) addi sp, sp, 12 jr ra ``` - `jr ra` = jump register: `pc <= reg[rs1] & ~1` - rounds address = `reg[rs1]` to an **even number** (0s out the 1s bit), and then sets `pc` to this address ![[stack detector 2.png|200]] ``` [first call] s0 = 0x3 s1 = 0x22 ra = 0xC4 s0 = 0x1 s1 = 0x23 ra = 0x4C s0 = 0x1 : lowbit s1 = 0x11 : rest ra = 0x4C s0 = 0x1 s1 = ??? ← call to this function = (0x11 & 1) >> 1 ra = 0x4C ``` - [!] WRONG WAY TO THINK ABOUT THIS (0x11 & 1) >> 1 : `00010001 & 1 = 00010001` → `00010001 >> 1 = 00001000=0x8` ![[exercise stack detector.png|500]] - What is the hex address of the instruction tagged `rtn:`? 0x4C + 4 because `jal ra, fn` stores the address of `add a0, a0, s0` to `0x4C` (`8(sp)`), and `rtn` is the next instruction after that (and instructions are stored with 4 byte offsets) - During procedure, stack pointer points at the lowest spot (bottom) of the stack for this procedure - i.e. `8(sp)` is 8 + address of `sp` register - Stack pointer marks the boundary between free / unallocated stack space and where active stack frames start: ``` lower addresses free / unallocated stack space ------------------------------- SP -> active stack frames start here active stack frames higher addresses ``` - What is the hex address of the `jal` instruction that called `fn` originally? 0x - `ra` first recorded = `0xC4` → so `jal` instruction that called `fn` must have been `0xC4 - 0x4` (instruction before the one linked) = `0xC0` - What hex value will be returned to the _original_ caller if the value of `a0` at the time of the original call was 0x47? 0x - This function is counting the number of ones - `0x47 = 01000111` = 4 --- **Exercise 2** ```C int get_remainder(int x, int y) { int difference = x - y; if (difference < 0) return x; else return get_remainder(x - y, y); } ``` ```python get_remainder: sub t0, a0, a1 # t0: x - y bltz t0, rtn # if t0 < 0, return x addi sp, sp, -4 sw ra, 0(sp) mv a0, t0 # a0 = x - y jal get_remainder # call fn on x - y lw ra, 0(sp) addi sp, sp, 4 rtn: jr ra # jump register: jr ra = jalr x0, 0(ra) ``` - The execution of the procedure call `get_remainder(0x68, 0x20)` has been suspended just as the processor is about to execute the instruction labeled `rtn:` during one of the recursive calls to `get_remainder`. A portion of the stack at the time execution was suspended is shown below: ![[exercise stack.png]] - For all of the following questions, suppose that during the initial (non-recursive) call to `get_remainder`, `sp` pointed to the memory location containing `0x10`. - [?] What is the hexadecimal value of the `???` in the stack dump that the stack pointer is pointing to? 0x - only `ra` is ever stored - so `0x10` → `0x1C`, we added `C` → next `ra`, we are adding same amount (since this is the same recursive function) → `0x1C + 0xC = 0x28` ## True Stack Detectives ```python arraySum: lw a2, 0(a0) li a3, 1 beq a1, a3, end addi sp, sp, -8 sw ra, 0(sp) sw a2, 4(sp) addi a0, a0, 4 #REPLACE <--- jal arraySum lw a2, 4(sp) add a2, a2, a0 lw ra, 0(sp) addi sp, sp, 8 end: mv a0, a2 ret ``` - `jal arraySum` will jump to label `arraySum` and write `ra = addr of next instruction` (in this case `lw a2, 4(sp)`) ## Exercises to review / general concepts to remember - True Stack Detectives - [i] In binary, bit 0 is the rightmost / least significant bit (remember this when reviewing the indices of ISA instruction → binary)![[dropping low bit branching instructions.png|500]] - [!] In a downward-growing stack, lower memory addresses are more recent/deeper calls, and higher memory addresses are older caller frames (because we subtract from `sp` each time we add new things) ``` older calls = higher addresses newer calls = lower addresses current top = current sp push/allocate = sp decreases pop/free = sp increases ``` # Lecture 6 - Memory is a large chunk of storage that stores stuff - word = 32 bits - registers: bigger (take up more real estate on cpu) than memory, but can be immediately accessed - memory might run fast or might run slower - depends where in memory you're trying to access - DRAM - crazy high densities - the individual bits in a DRAM are so tiny!!! - very small capacitance - this is so tiny that they leak from material imperfections and can't hold their binary value for more than ~100ms at room temperature - every bit of the billions stored in DRAM is periodically read and rewritten about every 64 ms on average at room temperature - a "refresh" - instructions and stack are *different regions of memory* - usually instructions have priority over data (in terms of access priority) - heap - changes at runtime - "data" (global and static variables) are separate from stack in memory space - stack grows from higher addresses to lower addresses - variable-length arrays are dangerous - risk too much stack growth - at run-time your stack goes too far you'll get a stack overflow - even worse is to have a stack overflow and not be aware of it - often place "stack canaries" - heap - variable length arrays # Pointers - Pointers themselves are variables stored in memory. They are always of size 4 bytes (32 bits) so that they can point to any memory address on a 32-bit machine. - Pointers point to the memory address of the lowest (least significant) base of a variable. e.g., if you have `uint32_t x = 80`, then a pointer to `x` `int *y = &x` would store the memory address of the least significant byte of `x` - And then the fact that this pointer is an `uint32_t` pointer will inform the compiler that starting from memory address `y`, this byte at `y` and the next 3 bytes should be collectively dereferenced. - If this pointer was declared as an `uint8_t` pointer, the compiler will only dereference the 1 byte at address `y` - [*] **For a variable, its less significant bytes are stored in lower memory addresses.** - [*] **Stack grows from higher addresses to lower addresses.**

title	tags	date	read
RL Notes		Jun 29, 2026	—
Algo Notes	technical	Jun 29, 2026	18 min
Papers		Jun 29, 2026	—
6.1210 Introduction to Algorithms	class	Jun 29, 2026	1 min
6.190 MIT Course Notes	class	Jun 29, 2026	113 min
6.191 MIT Course Notes	classtechnical	Jun 29, 2026	—