CS61c_1

RISC-V lw,sw,Decisions I,II and Lab2

Load and Store from Memory

a word is 4 bytes, and same as registers.
follow little-endian convention, that is, the least significant byte is stored at the lowest memory address.（小端序）
大端序(big-endian): the most significant byte is stored at the lowest memory address.
大多数90%的处理器采用小端序，包括x86和RISC-V。一些IBM的处理器采用大端序，比如PowerPC。美国人名字，java的包名都是大端序的。美国的日期格式是中端序？（月/日/年）

some instructions

main memory , also called DRAM(dynamic random access memory), is large but slow.
Register is 50x-500x faster than main memory.1ns vs 50-100ns.
打个比方：我们的脑子中找一个东西（大概需要1分钟），100倍就是1.5小时，相当于你开车到一个小镇拿一份文件，如果是500倍，那就是你开车去另一个城市拿文件了。由此可见从内存中load数据是多么慢的一件事。expensive!

1
2


int A[100];
g = h + A[3];

1
2


lw x10,12(x15) // load a word, from right to left
add x11,x12,x10

1
2


int A[100];
A[10] = h + A[3];

1
2
3


lw x10,12(x15)
add x10,x12,x10
sw x10,40(x15) // store a word, from left to right

x+12 and x+40 must be multiples of 4. In addition to word data transfer(lw,sw), RISC-V also has byte data transfers(lb,sb), same format as lw,sw.

注意符号扩展！
使用lb指令从内存加载一个字节到寄存器的时候，会进行符号扩展(sign extension), 会根据该字节的最高位（符号位）来决定扩展的值。如果最高位是1，表示负数，那么扩展的高位（剩余24位）会全部填充为1；如果最高位是0，表示正数，那么扩展的高位会全部填充为0。
lbu指令与lb类似，但它执行零扩展(zero extension)，无论最高位是0还是1，扩展的高位都会全部填充为0。

make decisions

beq reg1,reg2,L1 # branch if equal
if the content not equal, just continue to next instruction.
bne reg1,reg2,L1 # branch if not equal
blt,bge,bltu,bgeu # less than, greater equal, unsigned
jump 无条件跳转

1
2
3
4
5


if(i == j){
    f = g + h;
}eles{
    f = g - h;
}

1
2
3
4
5


bne x13,x14,Else
add x10,x11,x12
j Exit // don't forget to jump over the else part
Else: sub x10,x11,x12
Exit:

不需要bg和ble指令，直接交换比较的两个寄存器即可。
巧记blt：bacon，lettuce，tomato，某种sandwich的缩写😂
更复杂的例子

1
2
3
4
5


int A[20];
int sum=0;
for (int i=0;i<20;i++){
    sum += A[i];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    add x9,x8,x0 # x9 = &A[0]
    add x10, x0,x0 # sum=0
    add x11,x0,x0 # i=0
    addi x13,x0,20
Loop:
    bge x11,x13,Done
    lw x12,0(x9) # load A[i]
    add x10,x10,x12 # sum += A[i]
    addi x9,x9,4 # move to next element
    addi x11,x11,1 # i++
    j Loop
Done:

Logical Instructons

Always two variants: register-immediate and register-register.
Register: and x5, x6, x7 # x5 = x6 & x7
Immediate: andi x5, x6, 3 # x5 = x6 & 3
Used for ‘masks’
andi with 0000 00FF isolates the least significant byte.
andi with FF00 0000 isolates the most significant byte.
There is no logic NOT instruction in RISC-V, because we can use xor with 11111111 to achieve the same effect,RISC-V就是精简🐶
shift left logical(sll), immediate(slli)
slli x11,x12,2 # x11 = x12 « 2 how to multiply by 12 using shifts and adds? shift left by 2 is multiply by 4, shift left by 3 is multiply by 8, and add them up,这种方法在数字信号处理中很常见。
shift right logical(srl), immediate(srli)
shift right arithmetic(sra), immediate(srai)（扩展符号为到空出的高位）

1
2
3
4
5
6


1111 1111 1111 1111 1111 1111 1110 0111 = -25
sra by 4:
1111 1111 1111 1111 1111 1111 1111 1110 = -2
如果理解为除2的4次方，那么-25/16 = -1.5625，向下取整为-2。
但是在c中要求算术是向0取整的，所以-25/16=-1。
所以还需要一些操作～～～

Assembler to Machine Code

a.out很大，无法放到寄存器，必须放到内存中。
PC(program counter)寄存器，存放下一条要执行的指令的地址。
RISC-V指令都是32位的，每条指令的地址都是4的倍数。
PC = PC + 4 or branch/jump to new address.

Symbolic register names

a0-a7 for argument registers(x10-x17) for function calls.
zero for x0

Pseudo-instructions

mv rd, rs = addi rd,rs,0
li rd, 13 = addi rd, x0,13
nop = addi x0,x0,0
ret = jr ra
不改变代码执行逻辑，只是为了方便阅读和编写。

Function Calls

1
2
3
4
5
6
7


// the step of function call
1. 放置参数到合适的位置
2. 将控制权移交给函数
3. 获取局部空间
4. 执行函数
5. 将返回值放置到合适的位置，恢复寄存器，释放局部空间
6. 将控制权返回起点

a0-a1(x10-x11) as two return values.
ra(x1) as return address.
s0-s1(x8-x9) and s2-s11(x18-x27) as saved registers.
use jal to link and jump (保存返回地址到ra并且跳转),比如说jal ra sum
use jr to jump register(跳转到寄存器地址)，比如说jr ra返回。
jalr rd,rs,imm是jal和jr的结合体，先将PC+4保存到rd，然后跳转到rs+imm地址。这么来看的话其实j，jr都是jal的特例。 j: jal x0,label jr ra: jal x0,ra

Lab 2 – Adavanced C

Exercise 0 – makefiles

For large, complex, programs, most C programmers write what’s called a “makefile” to help with compilation. A makefile is a text file (literally labelled “Makefile”) in the code directory that contains a set of rules, each of which has commands that compile the C program for them. 金口玉言啊。

Exercise 1 – Bit operations

写完我发现csapp的lab1确实逆天。

Exercise 2 – Linear Feedback Shift Register

LFSR是一种伪随机数生成器，通过移位寄存器和反馈函数来生成伪随机序列。
反馈函数通常是一个线性函数，常见的形式是异或操作。
LFSR的状态由寄存器中的位组成，每次移位时，根据反馈函数计算出新的位，并将其插入到寄存器的最高位，同时右移其他位。
LFSR的周期取决于寄存器的长度和反馈函数的选择。

Exercise 3 – Memory Management

bad_vector_new: 使用了一个局部变量的地址作为返回值，这个局部变量在函数返回后就不再有效了，属于是一个悬空指针，有可能会导致各种奇怪的未定义行为。
also_bad_vector_new: 说实话，我感觉没什么特别大的问题，返回的时候直接返回结构体本身，虽然说结构体中包含data指针，只要后面不乱赋值造成同一块内存乱使用和乱释放，就没问题（
唯一需要注意的点就是在set超过size的值的时候需要重新malloc一个更大的data，注意要把原来的数据拷贝过去，然后注意！！！要初始化size+1到loc-1之间的值为0（不然会内存报错垃圾值），最后记得free原来的data指针。