CSAPP_Lab0_环境配置

Docker 让你省去配置环境的烦恼

搜索 CSAPP:什么：环境配置竟然这么简单

WSL2

也很方便，省去了找Docker镜像，Vscode配置到本地端口等麻烦

前置知识

逻辑移动 Logic Shift

如图，一个字节的数据向右移动一位，空出来的位用0填充

Logic shift 11001111逻辑右移一位，最低位进入进位标识位

LSR

算术移动 arithmetic shift

4-1Z509144R4336.gif 11001111，符号位为1，算术右移一位后得到11100111：

​ 4-1Z509144T2534.gif

SHL

SHL（左移）指令使目的操作数逻辑左移一位，最低位用 0 填充。最高位移入进位标志位，而进位标志位中原来的数值被丢弃：

4-1Z509150K0946.gif 若将 1100 1111 左移 1 位，该数就变为 1001 1110：

4-1Z509150PXa.gif

SHL 的第一个操作数是目的操作数，第二个操作数是移位次数：

SHL destination,count

该指令可用的操作数类型如下所示：

SHL reg, imm8 SHL mem, imm8 SHL reg, CL SHL mem, CL

x86 处理器允许 imm8 为 0〜255 中的任何整数。另外，CL 寄存器包含的是移位计数。上述格式同样适用于 SHR、SAL、SAR、ROR、ROL、RCR 和 RCL 指令。

[示例]下列指令中，BL 左移一位。最高位复制到进位标志位，最低位填充 0：

mov b1, 8Fh ; BL = 10001111b shl bl, 1 ; CF = 1, BL = 00011110b

当一个数多次进行左移时，进位标志位保存的是最后移岀最高有效位（MSB）的数值。下例中，位 7 没有留在进位标志位中，因为，它被位 6（0）替换了：

mov al, 10000000b shl al, 2 ; CF = 0, AL = 00000000b

同样，当一个数多次进行右移时，进位标志位保存的是最后移出最低有效位（LSB）的数值。

位元乘法

数值进行左移（向 MSB 移动）即执行了位元乘法（Bitwise Multiplication）。例如，SHL 可以通过 2 的幕进行乘法运算。任何操作数左移 n 位，即将该数乘以 2n。现将整数 5 左移一位则得到 5 x 2¹ = 10：

mov dl, 5 ; 移动前：00000101 = 5 shl dl, 1 ; 移动后：00001010 = 10

若二进制数 0000 1010（十进制数 10）左移两位，其结果与 10 乘以 2² 相同：

mov dl, 10 ;移动前：00001010 shl dl, 2 ;移动后：00101000

SHR

SHR（右移）指令使目的操作数逻辑右移一位，最高位用 0 填充。最低位复制到进位标志位，而进位标志位中原来的数值被丢弃：

4-1Z509154113459.gif

SHR 与《SHL指令 》一节中介绍的 SHL 的指令格式相同。在下面的例子中，AL 中的最低位 0 被复制到进位标志位，而 AL 中的最高位用 0 填充：

mov al, 0D0h ; AL = 11010000b shr al, 1 ; AL = 01101000b, CF = 0

在多位移操作中，最后一个移出位 0（LSB）的数值进入进位标志位：

mov al, 00000010b shr al, 2 ; AL = 00000000b, CF = 1

位元除法

数值进行右移（向 LSB 移动）即执行了位元除法（Bitwise Division）。将一个无符号数右移 n 位，即将该数除以 2n。下述语句将 32 除以 2¹，结果为 16：

mov dl, 32 ;移动前：00100000 = 32 shr dl, 1 ;移动后：00010000 = 16

下例实现的是 64 除以 2³：

mov al, 01000000b ;AL = 64 shr al, 3 ;除以 8, AL = 00001000b

用移位的方法实现有符号数除法可以使用 SAR 指令，因为该指令会保留操作数的符号位。

函数实现

int isAsciiDigit(int x)1

该函数判断一个数是不是在[0x30,0x39],

 //3
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 
 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  int mask=(0x1<<31);
  int lessthan=x+~0x30+1;
  int morethan=0x39+~x+1;
  int less=lessthan&mask;
  int more=morethan&mask;

  return !(less|more) ;
}

isLessOrEqual()2

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  int mask =0x1<<31;

  return (!!((x+~y+1)&mask))|!(x+~y+1);   //this is wrong!😫 
}

正确的3

int isLessOrEqual(int x, int y) {
  int temp=x+~y+1;
  int flag=temp>>31;
  int flag_x=x>>31;
  int flag_y=y>>31;

  return !!( (flag&(flag_x|!flag_y))|(!flag&(!(temp^0x0)|(flag_x&(!flag_y)))));
}
//😫 gross,我自己都不愿再去看自己写的这个return,AB+AC,本以为能优化，可惜优不得，也懒得去看别人的，摆烂

logicalNeg

/*

- logicalNeg - implement the ! operator, using all of
- `the legal operators except !`
- Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
- Legal ops: ~ & ^ | + << >>
- Max ops: 12
- Rating: 4
*/
int logicalNeg(int x) {
    return ~(x|(~x+1))>>31&1;
}
//😚😚,然然我真的好喜欢你啊，我要写csapp lab!反转了写不出来，你带我走吧

突然反应过来有些本来就是0x00000001的不需要再!!()来强制转换成1了。。。。。

还想了一小会儿，非0数的正负肯定会导致符号位不一样啊。但是直接哟x|~x+1,要明白不光有一正一负，

负数 即 0|0→0

这种0|1→1，也有Tmin，-Tmin仍然是Tmin啊！不过很巧很巧，1|1→1,当且仅当x为0时才会让x和-x都为负数

第一次实验结束捏

结束了,data lab

参考

  1. 虽然x-0x30,0x39-x,其实都有可能溢出，但是不影响结果，因为蒂娜我不能吃辣辣的东西一个很小的负数加上-0x30，溢出成正数，但要让 ↩︎

  2. 粗暴的直接x-y，会导致溢出，所以在判断x-y的符号位0/1时还应该考虑，正负溢出的情况，规避掉就行了。 ↩︎

  3. 有时候会用到数电中的逻辑公式，虽然每次看都看会了能证明，可惜闪存后又忘了，用的时候不确定又得看 ↩︎