Hexadecimal (Base 16)

- 0 ~ 9 + A ~ F as equivalent to 10 ~ 15

- e.x. 1A = 1*16^1 + 10*16^0 = 26

- The maximum value with two digits in the hexadecimal system (15*16^1 + 15*16^0 = 255) is equivalent to the max value with 8 bits in binary. Each digit in the hexadecimal system with 16 values maps to 4 bits in binary, which makes it more convenient to store the address of memory.

- Prefix: "0x", for example: 0x00FFFF. It means nothing but to notify when start parsing.

- Application in the RGB color system:

? ? ? ? - conventionally use hexadecimal to describe the amount of color

Address

- &: get the address of variable x

- *: go to the address of variable x

printf( "%p\n", &x );? ? ? ? ? ? ? ? // print out the address

printf( "%i\n", *&x );? ? ? ? ? ? ? ? // look inside a particular memory address and print out the value there

Pointer (8 bytes)

- A type of variable which stores an address of other values

- A value that points to a location in memory, like an arrow

- Pointers allow us to actually pass the variable itself, not the copy.

- If we create a pointer but not set the value immediately, the value of this pointer should always be set to NULL. If we try to dereference a pointer with the NULL value, we may encounter a segfault as it points to nothing.

- In C, pointers refer to specific types of values

int n = 50;

int *p = &n;

printf( "%p\n", p);? ? ? ? ? ? ? ? // print out the address of variable n

int *px, *py, *pz;? ? ? ? ? ? ? ? // create multiple pointers in the same line

- There can be a pointer to character / boolean / integer ......

- Modern computer system has 64 bits to address the memory.

Strings

- In C, string, as a data type, actually does not exist.

- Recall string used to be considered as a contiguous array of characters, it is indeed defined as pointers in <cs50.h>, as an address to some characters in memory.

- Example:

? ? ? ? string s = "HI!";? ? ? ? ? ? ? ? //s[0] = 'H'; s[1] = 'I'; s[2] = '!'; s[3] = '\0';

? ? ? ? Let s be the pointer with the address of the first character s[0] based on their contiguous address. So this variable s stores the address of the first character of the string (0x123), and the rest of the characters are in an array back-to-back.

? ? ? ? The working principle of defining string is to start at the address in s (s[0]), reaching 1 character (1 byte) at a time from the memory, and ending when hit the null character.

char *s = "HI!";? ? ? ? ? ? ? ? // store the address of the first character and point to its location in memory

Pointer Arithmetic

char *s = "HI!";

printf( "%c\n", s[0]);? ? ? ? ? ? ? ? // || printf( "%c\n", *s);

printf( "%c\n", s[1]);? ? ? ? ? ? ? ? // ||? printf( "%c\n", *(s+1) );

printf( "%c\n", s[2]);? ? ? ? ? ? ? ? // ||? printf( "%c\n", *(s+2) );

- char *: store the address of "H" and name the variable s

- *s: go to the address stored in the variable s and print out the value there

- *(s+1): go to the location in memory with the address one byte higher (the next character), which is a syntactic sugar for s[1], equivalent in function but less readable.

Segmentation Fault (Segfault)

- Try to read or write the illegal memory location ( e.x. *(s+1000000) ), which will cause programs to crash.

Malloc

- Allocate some number of bytes in memory (blank memory, like garbage values) and pass in the numbers of memory marked for use (see COPY STRING for more details).

- This function will return NULL when the computer runs out of memory, and a NULL pointer is indeed a bogus address, or there is no address to point to. So always check whether malloc returns a null pointer in case of segfaults.?

Free

- Free the allocated memory before the main function returns

- The free function marks those allocated memories as usable again, values stored there remain as garbage values.

Garbage Value

- Unknown random values at some address in the memory from the previous running program. It doesn't make sense, as it is not given by any logic.

- When we call the free function, values stored at those used memories won't be erased or set back to zero. Instead, these remnants will be left alone for later reuse.

int main(void)

{

? ? ? ? int *x;

? ? ? ? int *y;

? ? ? ? x = malloc( sizeof( int ) );

? ? ? ? *x = 19;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // go to the address x points to and set that location in memory to the value 19

? ? ? ? *y = 84;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // garbage value

? ? ? ? // through we trying to put the value 84 at the address y points to, we never assign y a value

? ? ? ? // y looks like an address but indeed not a valid address

? ? ? ? // we may go to some unknown address when try to go to the garbage value in y as an address, which is likely to cause a segmentation fault (segfault)

}

- To see garbage values:

int main(void)

{

? ? ? ? int score[3];? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // int *score, allocate 3 bytes without putting values there

? ? ? ? for (int i = 0; i < 3; i++)

? ? ? ? {

? ? ? ? ? ? ? ? printf("%i\n", score[i]);? ? ? ? // see previous uninitialized values in the reused memory

? ? ? ? }

}

- Exception: global variables

? ? ? ? Global variables are constants outside the context of main and all other functions, and will conventionally initialize to zero or null.

Memory Layout

- Different types of data are stored and organized into different sections.

- Machine code（代碼）: compiled binary codes, loaded into the top of memory

- Globals（靜態(tài) / 全局變量）: global variables (see the exceptions above)

The following is a shared pool of memory.?

- Heap（堆）:

? ? ? ? The empty area from where the malloc function can get free memory for programs to use. Once we call the malloc function, it starts to allocate memory from the top down (↓).

? ? ? ? - A pool where dynamically allocated memory comes from, with the access of pointers

All files live on the disk drive

(hard disk drive HDD or solid-state drive SSD), a permanent location that couldn't be modified in such storage space. Manipulation and use of data can only take place in the random access memory RAM, a much smaller place where all of the volatile data exists. Data in RAM will be destroyed when the computer battery died.

? ? ? ? Volatile data is any data that is stored in memory or exists in transit, that will be lost when the computer loses power or is turned off. Volatile data resides in registries, cache, and random access memory (RAM).

Memory is essentially a huge array of 8-bit wide bytes (such as 512MB, 1GB, 2GB, 4GB)

- Stack（棧）:

? ? ? ? Stack is a sort of dynamic place that memory gets used and reused. It grows upwards (↑).?

? ? ? ? When we call a new function, a new frame is pushed onto the top of the stack and becomes the active frame. (swap then main at the bottom) There is always only one active frame. The new frame popped off of the stack when this function is completed, and the lower one turned to be the new active function on the top of the stack instead.?

? ? ? ? Used by local variables and functions in our programs as we are called, which will be auto-discarded（執(zhí)行完自動銷毀）. Those functions don't physically disappear but become garbage values after execution, and the memory they were using is freed for the next function call. ( For dynamically-allocated memory, they won't automatically return to the system for later use, and such failure to return memory back to the system when we are finished with it could result in a memory leak. )

? ? ? ? Example (see Swap):

? ? ? ? ? ? ? ? ? ? ? ? ? ? Swap Function (on top of main with local variables a, b, temp)

? ? ? ? ? ? ? ? ? ? ? ? ? ? Main Function (at the very bottom of the stack with variables x, y)

- Typically there will be enough memory the heap and stack won't collide.

- heap overflow: call the malloc function for too much memory and pass the heap

- stack overflow: call too many functions without returning from them (like set height as 999,999,999 in the programs below). We will meet the segfault (segmentation fault) when running out of memory on the stack.

? ? ? ? Example: Recursion

? ? ? ? void draw(int h);

? ? ? ? int main(void)

? ? ? ? {

? ? ? ? ? ? ? ? int height = get_int( "Height: " );

? ? ? ? ? ? ? ? draw( height );

? ? ? ? }

? ? ? ? void draw(int h)

? ? ? ? {

? ? ? ? ? ? ? ? if (h == 0)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // base case

? ? ? ? ? ? ? ? ? ? ? ? return;

? ? ? ? ? ? ? ? for ( int i = 0; i < h; i++)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? ? ? printf( "#" );

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? printf( "\n" );

? ? ? ? ? ? ? ? draw(h-1);

? ? ? ? }

// Output:

? ? ? ? ###

? ? ? ? ##

? ? ? ? #

- buffer overflow:

? ? ? ? buffer: a chunk of memory used to fit / retrieved by malloc

? ? ? ? ? ? ? ? Example: preloaded video clip before offline

? ? ? ? buffer overflow: go past of the end of the allocated chunk of memory when using the malloc function