ReZero's Utopia.

# CSAPP

Word count: 5.4kReading time: 25 min
2020/10/01 Share

## Not be the real thing

1. digit might be overfolw

2. float will not be overflow, but could lost precision

## Memory

1. RAM: Random am

## Bit

Exclusive-Or(XOR) A ^ B

Union | //并

Complement ~ //补

Intersection & //交

Symmetric difference ^ //差

## Integer

Unsigned：

$$B2U(X)=\sum_{i=0}^{w-1}x_i*2^i$$

Signed：

$$B2T(X)=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$$

### Type Conversion

If not set keyword(unsigned) in C, then must use U follow number to change the default value(signed) such as 15213U

### Conversion mutual

• Byte will not changed, but change the interpreted way.

• Both all will be convert into unsigned if include one unsigned.

### Type extension & Intercept

• Extend: from short to int

• unsigned: plus 0
• signed: plus sign
• Intercept: from unsigned int to unsigned short

• unsigned: mod operation
• signed: almost mod operation

### Calculate & Overflow

Both w bit unsigned number mutual plus, and get a result w+1 bit. Then it will lose the highest bit, just like mod operation:

$$s=UAdd_w(u,v)=u+v ; mod ; 2^w$$

So as signed number, but change the sign symbol.

## Float

$$\sum_{k=-j}^ib_k\times 2^k$$

### IEEE standard

$$(-1)^s ; M ; 2^E$$

s is sign symbol, M always be [1.0, 2.0) decimal, and E is power.

Exp related E(not equal must, as the limit of bit count), frac related M(So as E)

#### Normalized Values

$$v=(-1)^s ; M ; 2^E$$

• E = Exp - Bias
• Exp: exp encode area unsigned digit
• Bias: as k is exp encode count, which means

$$2^{k-1} - 1$$

- single precision: 127 (Exp:1...254,E:-126...127)
- double precision: 1023 (Exp:1...2046, E:-1022...1023)

Note: Exp encode only need unsigned digit to operate.

For M, it must begin with 1: M = 1.xxx…x2, and xxx means frac(frac = 000.00 corresponding minium M = 1.0), when frac=111…1, M will be infinite close to 2.0

For Example: Float F = 15213.0

$$15213_{10}=11101101101101_2=1.1101101101101_2 \times 2^{13}$$

So the frac part is the point behind, and Exp = E + Bias = 12 + 127 = 140 = 10001100(b)

#### Denormalized Values

E = 1 - Bias And M = 0.xxx...x2 But others not changed.

exp = 000…0 & frac = 000…0 : 0
exp = 000…0 & frac != 000…0 : infinite to 0
exp = 111…1 & frac = 000..0 infinite
exp = 111…1 & frac != 000…0 NaN

#### Real sample

Note:

• exp = 0000(Denormalize) 1/8 is the distance

## Data in Memory

Internet: Big Endian

x86 OR ARM: Little Endian

%p: point, %x: Hex, Execute as:

## Basic

### C2M

.c (gcc -0g 0S) -> .s
.s (gcc OR as) -> .o
.o (with lib.a operated by gcc OR ld) execute.

appropriate code:

Processor:

• Storage: Memory & Register
• Calc: Memory & Register
• Transfer: condition call OR condition branch

### Assembly

General purpose register

• %rax(%eax) 用于做累加
• %rcx(%ecx) 用于计数
• %rdx(%edx) 用于保存数据
• %rbx(%ebx) 用于做内存查找的基础地址
• %rsi(%esi) 用于保存源索引值
• %rdi(%edi) 用于保存目标索引值

%rsp(%esp) 和 %rbp(%ebp) 则是作为栈指针和基指针来使用的

movq Sour:[Imm|Reg|Mem], Dest[Reg|Mem] (But No Mem Mem)

D(Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]+D]

• D - 常数偏移量

• Rb - 基寄存器

• Ri - 索引寄存器，不能是 %rsp

• S - 系数

• (Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]]

• D(Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]+D]

• (Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]]

More orders:

• addq Src, Dest -> Dest = Dest + Src

• subq Src, Dest -> Dest = Dest - Src

• imulq Src, Dest -> Dest = Dest * Src

• salq Src, Dest -> Dest = Dest << Src

• sarq Src, Dest -> Dest = Dest >> Src

• shrq Src, Dest -> Dest = Dest >> Src

• xorq Src, Dest -> Dest = Dest ^ Src

• andq Src, Dest -> Dest = Dest & Src

• orq Src, Dest -> Dest = Dest | Src

• incq Dest -> Dest = Dest + 1

• decq Dest -> Dest = Dest - 1

• negq Dest -> Dest = -Dest

• notq Dest -> Dest = ~Dest

## Flow Control

• 临时数据存放在 (%rax, …)
• 运行时栈的地址存储在 (%rsp) 中
• 目前的代码控制点存储在 (%rip, …) 中
• 目前测试的状态放在 CF, ZF, SF, OF 中

### Condition & Jump

• CF: Carry Flag (针对无符号数)
• ZF: Zero Flag
• SF: Sign Flag (针对有符号数)
• OF: Overflow Flag (针对有符号数)

%rdi save x，%rsi save y， %rax save return.

ntest = !Test;
if (ntest) goto Else;
value = Then_Expr;
goto Done;

Else:
val = Else_Expr;
Done:

result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if (nt) result = eval;
return result;

absdiff:
movq %rdi, %rax # x
subq %rsi, %rax # result = x-y
movq %rsi, %rdx
subq %rdi, %rdx # eval = y-x
cmpq %rsi, %rdi # x:y
cmovle %rdx, %rax # if <=, result = eval
ret

// Do While 的 C 语言代码
long pcount_do(unsigned long x)
{
long result = 0;
do {
result += x & 0x1;
x >>= 1;
} while (x);
return result;
}
// Goto 版本
long pcount_goto(unsigned long x)
{
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if (x) goto loop;
return result;
}

movl    $0, %eax # result = 0 .L2: # loop: movq %rdi, %rdx andl$1, %edx # t = x & 0x1
addq %rdx, %rax # result += t
shrq %rdi # x >>= 1
jne .L2 # if (x) goto loop
rep; ret

// C Code
do
Body
while (Test);
// Goto Version
loop:
Body
if (Test)
goto loop

// C While version
while (Test)
Body
// Goto Version
goto test;
loop:
Body
test:
if (Test)
goto loop;
done:

// For
for (Init; Test; Update)
Body

// While Version
Init;
while (Test) {
Body
Update;
}

long switch_eg (long x, long y, long z){
long w = 1;
switch (x) {
case 1:
w = y*z;
break;
case 2:
w = y/z;
// fall through
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2;
}
return w;
}

switch_eg:
movq %rdx, %rcx
cmpq 6, %rdi # x:6 ja .L8 jmp *.L4(, %rdi, 8) ## Jump table as .section .rodata .align 8 .L4: .quad .L8 # x = 0 .quad .L3 # x = 1 .quad .L5 # x = 2 .quad .L9 # x = 3 .quad .L8 # x = 4 .quad .L7 # x = 5 .quad .L7 # x = 6 // multstore 函数 void multstore (long x, long, y, long *dest) { long t = mult2(x, y); *dest = t; } // mult2 函数 long mult2(long a, long b) { long s = a * b; return s; } // Assembly 0000000000400540 : # x 在 %rdi 中，y 在 %rsi 中，dest 在 %rdx 中 400540: push %rbx # 通过压栈保存 %rbx 400541: mov %rdx, %rbx # 保存 dest 400544: callq 400550 # 调用 mult2(x, y) # t 在 %rax 中 400549: mov %rax, (%rbx) # 结果保存到 dest 中 40054c: pop %rbx # 通过出栈恢复原来的 %rbx 40054d: retq # 返回 0000000000400550 : # a 在 %rdi 中，b 在 %rsi 中 400550: mov %rdi, %rax # 得到 a 的值 400553: imul %rsi, %rax # a * b # s 在 %rax 中 400557: retq # 返回 long pcount_r(unsigned long x) { if (x == 0) return 0; else return (x & 1) + pcount_r(x >> 1); } pcount_r: mov0, %eax
testq %rdi, %rdi
je .L6
push %rbx
movq %rdi, %rbx
andl $1, %ebx shrq %rdi call pcount_r addq %rbx, %rax popq %rbx .L6: rep; ret struct rec { int a[4]; size_t i; struct rect *next; }; struct S1 { char c; int i[2]; double v; } *p; void echo() { char buf[4]; // 太小 gets(buf); puts(buf); } void call_echo() { echo(); } 00000000004006cf : 4006cf: 48 83 ec 18 sub$0x18, %rsp
4006d3: 48 89 e7 mov %rsp, %rdi
4006d6: e8 a5 ff ff ff callq 400680
4006db: 48 89 e7 mov %rsp, %rdi
4006de: e8 3d fe ff ff callq 400520 <puts@plt>
4006e3: 48 83 c4 18 add $0x18, %rsp 4006e7: c3 retq # call_echo 部分 4006e8: 48 83 ec 08 sub$0x8, %rsp
4006ec: b8 00 00 00 00      mov   $0x0, %eax 4006f1: e8 d9 ff ff ff callq 4006cf <echo> 4006f6: 48 83 c4 08 add$0x8, %rsp
4006fa: c3                  retq

// 把 nxn 的矩阵 a 的每一行加起来，存到向量 b 中
void sum_rows1(double a, double *b, long n)
{
long i, j;
for (i = 0; i < n; i++)
{
b[i] = 0;
for (j = 0; j < n; j++)
b[i] += a[i
n + j];
}
}

// 把 nxn 的矩阵 a 的每一行加起来，存到向量 b 中
void sum_rows2(double a, double *b, long n)
{
long i, j;
for (i = 0; i < n; i++)
{
double val = 0;
for (j = 0; j < n; j++)
val += a[i
n + j];
b[i] = val;
}
}

// 把 nxn 的矩阵 a 的每一行加起来，存到向量 b 中
void sum_rows2(double a, double *b, long n)
{
long i, j;
for (i = 0; i < n; i++)
{
double val = 0;
for (j = 0; j < n; j++)
val += a[i
n + j];
b[i] = val;
}
}

# sum_rows2 内循环

.L10:
addsd (%rdi), %xmm0 # 浮点数载入 + 加法
cmpq %rax, %rdi
jne .L10

// 文件 main.c
int sum(int *a, int n);
int array[2] = {1, 2}; // 变量 array 在此定义
int main() // 定义了一个全局函数
{
int val = sum(array, 2);
// val 是局部变量，链接器并不知道
// sum 函数是一个全局引用
// array 变量是一个全局引用
return val;
}
// —————————————–
// 文件 sum.c
int sum(int *a, int n) // 定义了一个全局函数
{
int i, s = 0;
// i 和 s 是局部变量，链接器并不知道
for (i = 0; i < n; i++)
s += a[i];

return s;

}



- 局部非静态变量会保存在栈中
- 局部静态变量会保存在 .bss 或 .data 中



Author：ReZero