CSAPP-notes

发表于 更新于

CSAPP notes

Lecture 2

  • Argument X X = 10100010
    << 3 X = 00010000
    logical >> 2 X = 00101000
    Arithmetic >> 2 X = 11101000

    Logical right shift would fill the high digit with zero.

    Arithmetic right shift would fill the high digit with the sign digit.

  • In real world practice, when you do X << Y in the machine, most machine would actually do X << (Y mod 8) (However, when I test it locally, this mod operation didn't apply)

  • The difference between && and &：

    • && would only return 0 or 1, while & can return all kinds of integers
    • && would consider any non-zero integer as 1, and consider 0 as 0. & certainly don't have this trait
    • When the outcome of an expression is known, && would not calculate the rest of the expression. For example, if int x = 0, and we calculate expression a&&(5/a), it would not raise an DIVIDEZERO error as the second part would not be calculated. Similarly, if p is a null pointer, then p&&*p++ would not access a null pointer as the second part would be omitted.

  • If you shift left by a negative number, the outcome might not be a right shift. For example, 1 << (-2) might not be 1 >> 2

  • A different way to understand two's complement

    For example, the two's complement of a number is 10110001, then the value of this number should be: \[ 1\times (-2^7) + 0 \times 2^6 + 1 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \]

    In other word, when it comes to two's complement, we consider the weight of the highest digit to be negative. More accurately, the weight of the highest digit should be the opposite number of its original weight.

  • If a comparison operation involves two signed numbers, then it would do it signed ways. If a comparison operation involves two unsigned umbers, then it would do it unsigned ways.

    However, if a comparison operation involves a signed number and an unsigned number, then it would first transform the signed number into unsigned form then compare these two unsigned numbers.

    For example, if int x = -1; unsigned int y = 0, then x would be greater than y. In other word, x > y would be true.

    This rule applies to other operations, including add, minus, etc.

  • Define int x = -2147483648 might make the compiler confused for obscure reason. You can do the same thing by int x = -2147483647 - 1

  • An example:

    1
    2
    3
    int i;
    for (i = 10; i - sizeof(char) >= 0; i--)
        printf("%d\",i);

    For this program, what you will get is just an endless loop. Why？because sizeof(char) is an unsigned number, making the whole bunch of i - sizeof(char) to be considered unsigned. Thus, i - sizeof(char)>=0 always holds, making the loop endless.

  • How to promote a smaller type of integer to a larger type of integer?

\(\hspace{1cm}\) For example, if we have a variable x of type int, how do we cast it to type long long?

\(\hspace{1cm}\) Simply by repeatedly copying the sign digit and insert it to the left until the number of digit reach the word size of long long.

\(\hspace{1cm}\) This is both true when it is a two's complement number and when it is an unsigned number.

Lecture 3

  • Addition for unsigned number (A.K.A. UAdd) :

    Computer will just add the two numbers up and abandon the higher digit if it exceeds the word size.

    For unsigned number u and v，perform addition between them would lead to the result of \((u + v) \% 2^w\) , with w representing the word size.

  • Addition for two's complement number (A.K.A TAdd):

    Computer will do the same thing in UAdd: Add the two numbers up and abandon the higher digit if it exceeds the word size.

    For example, if we have a 4-digit two's complement number u = 1101 and v = 0101. So u is actually -3 and v is actually 5. Thus, u + v should be 2 arithmetically. When we add the 1101 and 0101, we got 10010, and we abandon the most significant digit and we got 0010, which is 2 and it matches the arithmetic result.

    Another example: u = 1101, v = 1010, so u is actually -3 and v is actually -6, so u + v should be -9 arithmetically. If we add 1101 and 1010, we got 10111. Abandon the highest digit we got 0111, which is 7.

  • UAdd and TAdd have identical Bit-level behavior

  • Multiplication for unsigned number:

    Similar to addition, computer would first calculate the product, then abandon the higher digit exceeding the word size. Simply put, \(u \times v\) would be \((u \times v) \% (2^w)\), with \(w\) representing the word size

  • Multiplication for two's complement number:

    Computer would first calculate the product, then abandon the higher digit exceeding the word size.

    For example, if u=0101 and v = 0101, then \(u \times v = 11001\). Abandon the highest digit we got 1001 , that would be -7.

  • A property for two's complement

    Assume a number x can be represented \((\overline{a_1 a_2 a_3 ... a_n})_2\) in two's complement. Let's denote \((\overline{a_1 a_2 a_3 ... a_n})_2\) as \([a_1,a_2,...,a_n]\). And we could assert that: if \(x = [a_1,a_2,...,a_n]\), then: \[ -x = [1 - a_1,1 - a_2, ... , 1 - a_n] +1 \] Notice: the last "+" operation will be done in computer ways, which means if it overflows, then the highest digit would be omitted.

    For example, 0 = [0,0,0,0], so -0 = [1,1,1,1] +1 = [1,0,0,0,0], then we omit the highest number, then we could get [0,0,0,0], and the result is correct.

  • It appears that in my computer, when you do a ">>" operation then it would actually perform arithmetic >>

  • In a 64-bit word size machine, the address of the memory would be 8-bytes (which is also 64 bits). Thus, if we do printf("%d\n",sizeof(int*)), then it would probably get "8".

  • Terminology time:

    Word means a range of memory unit storing a specific type of data. For example, an int word is comprised of 2 bytes, an long long word is comprised of 4 bytes.

  • So, how are the bytes within a multi-byte word ordered in memory?

    Two ways: Big Endian; Little Endian;

​ Little Endian is the major way today.

​ The internet still use Big Endian.

  • The way to store strings:

    Computer would just store the string from head to tail char-wise. There's no big-endian or little-endian here.

​ (Notes: IA32 is a little-endian machine, and Sun is a big-endian machine)

Lecture 4

  • An example 

    1
    printf("%d\n",(2/3)==(2/3.0));

    In fact, this program would output 0. Because (2/3) is an integer while (2 / 3.0) is a double number. Thus, the equation can not hold.

  • Implicit Conversion

    In the C language, when an operation involves multiple types of variables, type conversions occurs to make sure that the type of different variables match. In operations, implicit conversions take place. Type conversions can also be called as cast.

    • All integer type smaller than int (like short, char) will be promoted to int
    • Low precision type will be cast to high precision type.(int would be cast to float, float would be cast to double)

  • Immediate Value

    In the C language, immediate value refers to a constant value that is directly specified in code.

    The immediate value is also known as a literal.

    In the C language, the immediate value 3.14 are treated as type duoble by default.

  • IEEE floating point representation

    The IEEE float point representation represents a number in the form \(V = (-1)^s \times M \times 2^E\)

    The sign s determine whether this number is positive or negative

    The exponent E weights the value by a (possibly negative) power of 2.

    Floating-point number are represented in three fields above.

    • The single sign bit in the front directly encode sign s

    • The \(k-bit\) exponent field \(exp = e_{k-1}e_{k - 2}...e_0\) encodes the exponent \(E\)

    • The \(n - bit\) fraction field \(frac = f_{n - 1}f_{n - 2}...f_0\) encodes the significand \(M\)

    • Normalized Case

      When exp is not all 0 and exp is not all 1，it is the normalized case

      In this case, \(E = e - bias\)，where \(bias = 2^{k - 1} - 1\) and \(e\) is the unsigned number having the bit representation of \(e_{k - 1}e_{k- 2}...e_0\).

      In this case, \(M = (1.f_{n - 1}f_{n - 2}...f_0)_2\)

    • Denormalized Case

      When exp is all 0, it is the denormalized case, used to represent floating-point number that is close to zero.

      In this case, \(E = 1 - bias\), where \(bias = 2^{k - 1} - 1\).

      In this case, \(M = (0.f_{n - 1}f_{n - 2}...f_0)_2\)

    • Special Case A

      When exp is all 1, and frac is all 0, this number means infinity. By assigning s to 1 or 0, we could get positive infinity and negative infinity.

    • Special Case B

      When exp is all 1, and frac is not all 0, this number means NaN (Not a number). Such values are returned as the result of an operation where the result can not be given as a real number or as infinity, as when computing \(\sqrt{-1}\) or \(\infty - \infty\) .

  • Why do we have to define denormalized case?

    In normalized case, we can not represent 0.

    In denormalized case, we can represent 0 as well as some numbers really close to 0.

  • Floating-point Operation

    The IEEE standard specifies a simple of way of floating-point operation. Viewing the two number as real numbers and just do the operation in mathematical ways, then round the mathematical result to yield the final result.

    If one of the value is special (such as NaN, infinity,0), the IEEE standard specify a convention that attempt to be reasonable. To be specific, 1/-0 is defined to yield \(-\infty\), \(\infty - \infty\) is defined to yield NaN.

  • The floating-point addition is commutative but not associative. For example, a float x = 3.14 + 1e20 - 1e20 would yield 0, while a float x = 3.14 + (1e20 - 1e20) would yield 3.14

  • The floating-point multiplication is commutative but not associative. For example, 1e20 * 1e20 * 1e-20 would yield \(+\infty\), while 1e20 * (1e20 * 1e-20) would yield 1e20

    The floating-point multiplication does not distribute over addition.

  • Conversion between int, float and double:

    • int -> float: The number will not overflow, but it may be rounded.
    • int or float -> double: The number will not overflow and it will not be rounded. Because it has both greater range and greater precision.
    • double -> float: The number might overflow(leading to \(+\infty\) or \(-\infty\)) or be rounded.
    • float or double -> int: The number would be rounded toward \(0\).

  • Infinity can be compared. It is compared in mathematical ways.

  • For floating-point number \(a\),\(b\),\(c\)

    • if $ a> b$, then \(a + c > b + c\)
    • If \(a > b\), then \(-a < -b\)
    • For every floating-point number \(x\), we have \(x \times x \ge 0\)

Data lab

Lecture 5

  • how to assemble a file 

    1
    gcc -S test.c

    Can assemble test.c into assemble code test.s

  • how to disassemble an object code file 

    1
    objdump -d test > test.d

    Can disassemble the object code file test into assemble code file test.d

  • Use gdb to disassemble a function:

    Suppose we have a program code test.c and we want to disassemble the function build which is in this program.

    First we have to compile test.c:

    1
    gcc -Og -o test test.c

    Then we type

    1
    gdb test

    Then we would get into the gdb interface.

    After it, we type

    1
    disassemble build

    and we could get the disassemble code

  • The concept of instruction set:

    There are two kinds of prevalent instruction set, intel x86-64 and ARM. Most intel chip use x86-64 while mobile phone chip and apple chip use ARM. The course is about x86-64

  • The assembly code usually implement data manipulation in memory and register. There are 16 register, and there names are as follow:

    %rax %r8
    %rbx %r9
    %rcx %r10
    %rdx %r11
    %rsi %r12
    %rdi %r13
    %rsp %r14
    %rbp %r15

  • the syntax %rax refers to the register %rax, and the syntax (%rax) refers to the value in register %rax

  • A general way to designate address: \[ D(R_b, R_i, S) \] \(D\) is a constant, \(R_b\) and \(R_i\) are the name of two general-purpose register, and the \(S\) is the scaling factor restricted to be 1, 2, 4, or 8. This expression specifies an address, which would be: \[ D + ([numbers \ \ in \ \ R_b] + S \times [numbers \ \ in \ \ R_i]) \] For example, provided that the number stored in \(R_b\) is 0x100, the number stored in \(R_i\) is 0x200, \(D = 2\), \(S = 4\)， then \(D(R_b,R_i,S)\) would designate the address 2 + 0x100 + 0x200 * 4, which is 0x902.

    (Denote: D is short for displacement, and S is short for scaling)

  • The MOV grammar:

    • Move an immediate value to the register:

      mov $0x4, %rax

      This would move the immediate value 0x4 into the register %rax

      ​

    • Move an immediate value to the memory:

      mov $-147, (%rax)

      In this case, there is an address stored in the register %rax and it would move the immediate value -147 to that address in the memory

    • Move a value from a register to register

      mov %rad, %rdx

      It would copy the value stored in register %rad to register %rdx

    • Move a value from a register to memory

      mov %rax, (%rdx)

      It would copy the value stored in register %rax to the address (%rdx) in the memory

    • Move a value from memory to register

      mov (%rax), %rdx

      vice versa

    Note: you can't move a value from memory directly to memory

    Observation:

    ​ This operation simply move something into a register or the memory. If it is a register, the second argument should be the name of the register. If it is the memory, then the second argument should be the address, usually designated by (the name of a register) or D(Rb,Ri,S).

    ​ The first argument specifies the number we want to move. The first argument could be an immediate number, the name of a register or an address. If it is an immediate value, then it means it would move this literal. If it is the name of a register, then it means it would move the number stored in the register. If it is an address, it means it would move the number stored in this address.

  • The LEA grammar

    The general form:LEA first_argument, second_argument

    The first argument is an address, the second argument must be the name of a register.

    This operation will move the address (the first argument) itself to the second argument (a register or an address).

    • The difference between LEA and MOV: LEA would simply move the address itself while MOV would dereference the address and move the value stored in that address

​ In practice, the first argument can be literal or the name of a register. This might violate the rule, but compiler still use this, especially in some arithmetic operation.

​

Can't understand MOV and LEA? Watch this video: 4 MOV vs LEA (youtube.com)

  • In a function, the first parameter passed to the function will be stored in register %rdi, the second parameter would be stored in %rsi. The return value of a function would be stored in register %rax

  • movl instruction：

    This instruction could move a 32-bit value from one place to another.

    • From register to register:

      movl %eax, %ebx

      This would move the value in %eax to %ebx

      (Note: %eax is the lower 32 bits of %rax, so does %ebx)

    • From memory to register

      movl 0x100(%rbp), %eax

      This would move the 32-bit value from memory location at 0x100(%rbp) to register %eax. This would load 4 memory units and would load it upside down (because we are talking about little-endian machine)

      For example, here are the number stored in memory:

      Memory Location Value
      0x100 0x17
      0x101 0x25
      0x102 0x33
      0x103 0x64
      0x104 0x89
      0x105 0x26
      0x106 0x71

      If %rbp = 0, then after this operation, 0x64332517 would be stored in register %eax.

    • From register to memory

      Similar, so omit it.

    • Move a literal to memory & Move a literal to register

      Similar, so omit it.

    Note: After the movl operation, the upper-32 bits of the destination(could be register or memory location) would be set to 0

  • A general property for instructions copying and generating 1-, 2-, 4-, 8- byte values: When the destination is a register, those that generates 1-,2- byte values leaves the remaining upper bytes unchanged, while those that generate 4- byte values will set the upper 4 byte to 0.

  • The program counter(commonly called %rip) indicates the address in memory of the next instruction to be executed.

  • The regular movq operation can only have immediate source operand that can be represented in 32-bit two's complement (Simply put, the immediate source operand must be in the range of \([-2147483648, 2147483647])\). Then the compiler would do sign extension to the 32-bit two's complement to make it 64-bit, then carry out the move.

    What is sign extension?

    ​ Given a number represented in short-word-length two's complement, we want to represent this number in a long-word-length two's complement without changing its arithmetic value. This transformation is called sign extension.

    ​ We can finish this task by replicating the sign digit. Whether the number is positive or not, you will find by doing the replication the value remain unchanged.

    ​ For example, 0x0011 after sign extension becomes 0x000011, the value remains unchanged. (before: 3; after: 3)

    ​ Another example: 0x1100 after sign extension becomes 0x111100， and the value remains unchanged (before: -4; after: -32+16+8+4 = -4;)

  • As mentioned above, the regular movq instruction has limitation on literal, that's why the instructionmovabsq comes into life. It can move arbitrary 64-bit two's complement literal, and the destination must be a register.

  • When copying from a smaller source to a larger destination (for example, from a 32-bit to 64-bit), the x86-64 ISA provides two instructions: movz and movs.

    movz would set the remaining higher bits to 0, while movs would fill the remaining higher bits by replicating the most significant bits of the source operand.

    Here are some example:

​ The operation cltq has the same effect of the operation movslq, but it has more compact encoding.

cltq is short for convert l(double word) to q(quad word)

  • The unary operation:

    It has a single operand serving as both resource and destination. For example, we could have:

1
2
incq(%rax) # to increment register %rax by 1
decq(%rax) # to decrement register %rax by
  • The arithmetic binary operation:
1
2
3
4
addq %rcx, %rax   # to increment register %rax by the value stored in %rcx
subq %rcx, %rax   # to decrement register %rax by the value stored in %rax
mulq %rcx, %rax   # rax <---- (rax * rcx)   (value stored in rax and rcx are considered to be unsigned)
imulq $16, (%rax,%rdx,8) # to multiply the address %rax + 8 * %rdx by a factor of 16 (value involved are considered to be two's complement)

For these binary operations, there are two observations:

  • The source would be the first argument, and the destination would be the second argument.
  • The first operand could be an immediate number, a register or a memory location. The second operand could be an register or a memory location. However, the first operand and the second operand could not both be memory location.

  • Shift operation:

    The operation involves two operand, the first operand specifies the shift amount, and the second value designates the value we want to shift. Shift amount usually is a immediate number, but it can also be the value stored in single-byte register %cl.

    A shift operation on the data type that are w bits long would use the lower m bits of the register %cl, where \(2^m = w\). For example, if the register %cl stores the hexadecimal value of $0XFF, then SALB would shift by 7 digits, SALW would shift by 15 digits, SALL would shift by 31 digits, and SALQ would shift by 63 digits.

    • Left shift:

      Comprises two instructions: SAL and SHL. These instructions have same effect

    • Right shift:

      Comprises two instructions: SAR and SHR. The former is the arithmetic right shift, and the latter is the logical right shift.

  • Single Operand Multiplication:

    ​ This types comprise two operations: imulq S and mulq S. The former one is for two's complement, and the latter one is for unsigned. Apart from this difference, the rest are the same, so we would only talk about imulq S.

    ​ The operation imulq S would calculate the value \(S \times M[\%rax]\) keep the all 128-bit without truncate. Then it would store the higher 64 bits to register %rdx and store the lower 64 bits to register %rax.

    ​

  • cqto operation:

    This would convert a 64-bit value to 128-bit value. Specifically, it would sign extend %rax to make it to be a 128-bit value, and then store the upper 64 bit in %rdx and store the lower-64 bit in %rax

  • divide operation:

    There are divide operation: idivq and divq. Similarly, former one is for two's complement, and the latter one is for unsigned. Let's just talk about idivq since divq is the same case.

    Syntax for idivq: idivq S

    • case 1: If the bits of $rdx are all set to the sign bit of $rax (for operation divq S, we should look at whether the bits of $rdx are all set to zero), then we would consider that the dividend is a 64-bit value stored in $rax.
    • case 2: If the bits of $rdx are not all set to the sign bit of $rax (for operation divq S, we should look at whether the bits of $rdx are all set to zero), then we would consider that the dividend is a 128-bit value, with higher 64 bits stored in $rdx and lower 64 bits stored in $rax

    Anyway, after specifying the dividend, then the machine would do the division, and yield a quotient and a remainder.

    The quotient would be stored in $rax and the remainder would be stored in $rdx.