前言

该实验是《深入理解计算机系统》(英文缩写CSAPP)课程附带实验——Lab1:Data Lab,对应书中第二章内容(信息的表示和处理),因为是所有实验中的第一个实验,本篇文章记录了进行Lab之前的准备工作(虚拟机的安装(Vmware Workstation+Ubuntu),Lab环境配置),实验附带说明文档README、bits.c文件中的引导以及注意事项的翻译,进行编译的步骤,以及函数实现。

一.WIN10虚拟机安装

1.关于Vmware Workstation,Ubuntu和Vmware tools

  • Vmware Workstation是虚拟机载体,将你的硬件资源虚拟化,然后可以在里面模拟一台计算机。
  • Ubuntu是操作系统,是基于Linux内核的一个发行版,他要安装在虚拟机里。
  • Vmware tools是一些工具,我安装的是 VMware Workstation 16 Pro,安装时已经自带了,可能一些之前的版本需要额外操作进行配置。

2.安装步骤

具体的安装步骤我之前参考的几个博客有详细说明,安装过程没有出现问题,这一部分直接附上链接:

二.Lab环境配置(安装GCC编译套装)

搜索打开终端命令窗口(快捷键:Ctrl+Alt+T),分别输入以下三行指令,每行输入结束后回车即可

> sudo apt-get install build-essential
> sudo apt-get install gcc-multilib
> sudo apt-get install gdb

参考:【CSAPP】lab0 环境的配置

三.README及实验引导翻译

CSAPP实验网站中每个实验标题后面都有四个附件,前面的三个为给教师的说明文档和实验题目版本的说明,我们只需要下载Self-Study Handout(自学手册)并阅读其中的README(给学生的说明文档)即可

1.实验总说明

Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.
学生实现简单的逻辑、二进制补码和浮点数,但使用c的一个高度受限的子集。例如,他们可能被要求仅使用位级操作和直线代码计算一个数字的绝对值。本实验帮助学生理解C数据类型的位级表示和数据操作的位级行为。

2.README.Directions for students


The CS:APP Data Lab
Directions to Students


您的目标是修改bits.c的副本,使其通过btest中的所有测试,而不违反任何编码准则。


0. 文件:


makefile -生成btest、fshow和show
readme -此文件
bits.c -你将修改并提交的文件
bits.h -头文件
btest.c -主要的btest程序
btest.h -用于构建btest
decl.c -用于构建btest
tests.c - 用于构建btest
test-header.c - 用于构建btest
dlc* -规则检查编译器二进制(数据实验室编译器)
driver .pl* -使用btest和dlc自动升级位的驱动程序
Driverhdrs.pm -可选的“击败教授”比赛的头文件
fshow.c -用于检查浮点表示的工具
ishow.c -用于检查整数表示的实用程序


1. 修改bits.c并检查它是否符合dlc


注意:在开始之前,请仔细阅读bits.c文件中的说明。这些给出了编码规则,如果你想要获得满分,你需要遵循这些规则。

使用dlc编译器(./dlc)自动检查你的版本bits.c用于符合编码准则:

  unix> ./dlc bits.c

如果你的代码没有问题的话,dlc会静默地返回。否则,它将打印标记任何问题的消息。

使用-e开关运行dlc:

  unix> ./dlc -e bits.c 

使dlc打印每个函数使用的操作符数量的计数。(括号不算)

一旦您有了一个合法的解决方案,您可以使用./btest程序测试它的正确性。


2. 用btest测试


这个目录中的Makefile用额外的代码编译您的bits.c版本,以创建一个名为btest的程序(或测试工具)。

要编译并运行btest程序,输入:

   unix> make btest
   unix> ./btest [optional cmd line args]

每次修改bits.c程序时,都需要重新编译btest。当从一个平台转移到另一个平台时,你会想要摆脱旧版本的btest,并生成一个新版本。使用命令:

  unix> make clean
  unix> make btest

btest通过在每个函数上运行数百万个测试用例来测试代码的正确性。它广泛地测试已知的角落情况,例如整数谜题的Tmin和0,浮点数谜题的0、inf,以及非规范化和规范化数字之间的边界。当btest检测到函数中的一个错误时,它会打印出失败的测试、不正确的结果和预期的结果,然后终止对该函数的测试。

以下是btest的命令行选项:

  unix> ./btest -h

用法: ./btest [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>]
-1 <val> 指定第一个函数参数
-2 <val> 指定第二个函数参数
-3 <val> 指定第三个函数参数
-f <name> 只测试指定的函数
-g格式化自动升级输出,不输出错误信息
-h打印此消息
-r <n> 对所有的问题都给予n个统一的权重
-T <lim> 设置超时时间限制为lim

示例:
测试所有函数的正确性并输出错误信息:

  unix> ./btest

以简洁的形式测试所有函数,不发送错误消息:

  unix> ./btest -g

测试函数foo的正确性:

  unix> ./btest -f foo

用特定参数测试函数foo的正确性:

  unix> ./btest -f foo -1 27 -2 0xf 

Btest不会检查你的代码是否符合编码指南。使用dlc来做到这一点。


3.辅助程序


我们已经包括了ishow和fshow程序,以帮助您分别解读整数和浮点表示。个参数都接受一个十进制或十六进制数作为参数。要构建它们的类型:

  unix> make

示例用法:

  unix> ./ishow 0x27

Hex = 0x00000027, Signed = 39, Unsigned = 39

  unix> ./ishow 27

Hex = 0x0000001b, Signed = 27, Unsigned = 27

  unix> ./fshow 0x15213243

Floating point value(浮点值) 3.255334057e-26
Bit Representation(位表示) 0x15213243, sign(符号) = 0, exponent(指数) = 0x2a, fraction(分数) = 0x213243
Normalized. (标准化) +1.2593463659 X 2^(-85)

  unix> ./fshow 15213243

Floating point value 2.131829405e-38
Bit Representation 0x00e822bb, sign = 0, exponent = 0x01, fraction = 0x6822bb
Normalized. +1.8135598898 X 2^(-126)

3.bits.c文件中的引导以及注意事项

参考:CSAPP:DataLab实验
/*
*CS:APP数据实验室
*
*<请输入您的姓名和用户名>
*
*bits.c -源代码文件与您的解决方案到实验室。
*
*这是你要交给老师的文件。
*
*警告:不包括<stdio.h>头;它混淆了DLC编译器。您仍然可以在不包含<stdio.h>的情况下使用printf进行调试,尽管您可能会得到一个编译器警告。一般来说,忽略编译器警告并不是一种好的做法,但在本例中是可以的。
*/

/*
*学生须知:
*
第一步:仔细阅读以下说明。
*/

您将通过编辑此源文件中的函数集合向Data Lab提供您的解决方案。

整数编码规则:
用实现该函数的一行或多行C代码替换每个函数中的“return”语句。你的代码必须遵循以下风格:

  int Funct(arg1, arg2, ...) {
      /*您的实现如何工作的简要描述*/
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

每个“Expr”都是一个表达式,仅使用以下内容:
整数常量0到255(0xFF)(不能超过8位),包括0和255。不允许使用像0xffffffff这样的大常量。
函数参数和局部变量(没有全局变量)。
一元整数运算! 〜
二进制整数运算&^ | + << >>
一些问题进一步限制了允许的运算符集合。
每个“Expr”可能包含多个运算符。你不局限于每行一个操作数。

明确禁止您:
使用任何控制结构,如if,do,while,for,switch等。
定义或使用任何宏。
在此文件中定义任何其他功能。
调用任何功能。
使用任何其他操作,例如&&,||, - 或?:
使用任何形式的转换
使用除int之外的任何数据类型。这意味着你不能使用数组,结构体或者共用体。

你可以假设你的机器:
使用2进制补码,32位整数表示
算术上进行右移。 // 此处整数题目数据类型都定义为int,有符号数右移操作都为算术移位
如果偏移量小于0或大于31,则在偏移时具有不可预知的行为。

可接受的编码样式示例:

/ *
pow2plus1 - 返回2 ^ x + 1,其中0 <= x <= 31
/
 int pow2plus1(int x){
     / *利用移位能力计算2 * /的功率
     return1 << x)+ 1;
  }
/ *
pow2plus4 - 返回2 ^ x + 4,其中0 <= x <= 31
/
 int pow2plus4(int x){
     / *利用移位能力计算2 * /的功率
     int result =1 << x);
     result+ = 4;
     return result;
  }

浮点编码规则

对于需要实现浮点运算的问题,编码规则不那么严格。允许使用循环和条件控制。你可以同时使用整型和无符号。你可以使用任意整数和无符号常数。可以对整数或无符号数据使用任何算术、逻辑或比较操作。

明确禁止您:
1.定义或使用任何宏
2.在此文件中定义任何其他函数
3.调用任何函数
4.使用任何形式的转换
5.使用除int或unsigned之外的任何数据类型。这意味着你不能使用数组,结构体,共用体
6.使用任何浮点数据类型,操作或常量

注:
1.使用dlc(数据实验室检查器)编译器(在讲义中描述)来检查你的解决方案的合法性。
2.每个函数都有最大数量的运算符(!〜&^ | + << >>)您可以使用它来实现该功能;dlc检查最大操作数。请注意,’='不是计算;您可以根据需要使用尽可能多的这些而不会受到惩罚。
//每个函数都有所使用的操作符有限,“=”不算。(整数浮点数都可以用”=”)
3.使用btest测试工具检查函数的正确性。
4.使用BDD检查器正式验证函数
5.每个函数的最大操作数在每个函数的头注释中给出。如果writeup中的最大操作与此文件中的最大操作之间存在任何不一致,则将此文件视为权威源文件。

/*
*步骤2:根据编码规则修改以下功能。
*
*重要.为避免评分意外:
*1. 使用dlc编译器检查你的解决方案是否符合编码规则。
*2. 使用BDD检查器正式验证您的解决方案是否产生了正确的答案。
*/

四.编译步骤

1.准备

  • 搜索打开终端命令窗口(快捷键:Ctrl+Alt+T) 在命令终端输入pwd:查看当前路径,ls 查看当前路径下的文件

  • 解压datalab-handout.tar文件

    打开终端,分别输入pwd,ls,cd(空格)\桌面 ,回车(或者右击 datalab-handout.tar,属性,复制其路径(上级目录,下同),或者直接打开文件夹,右键在终端打开,直接跳转到该路径)
    来到压缩包路径下,输入以下命令,将压缩包解压到同名文件夹下:

    > tar -xvf datalab-handout.tar 
    

2.对函数进行编译

用命令 >cd 路径 将目录切换到dlc所在的文件下(或者直接打开文件夹,右键在终端打开,直接跳转到该路径)

  • 修改bits.c并检查它是否符合dlc

输入./dlc bits.c对bits.c文件中的函数进行编译,用于符合编码准则:

  unix> ./dlc bits.c

使用-e开关运行dlc:

  unix> ./dlc -e bits.c 

使dlc打印每个函数使用的操作符数量的计数。(括号不算)

  • 用btest测试所有函数的正确性

每次修改bits.c程序时,都需要重新编译btest。当从一个平台转移到另一个平台时,你会想要摆脱旧版本的btest,并生成一个新版本。使用命令:

  unix> make clean
  unix> make btest

测试所有函数的正确性并输出错误信息:

  unix> ./btest

以简洁的形式测试所有函数,不发送错误消息:

  unix> ./btest -g

测试函数foo的正确性:

  unix> ./btest -f foo
  • 辅助程序

ishow和fshow程序,可分别解读整数和浮点表示。每个参数都接受一个十进制或十六进制数作为参数。要构建它们的类型:

  unix> make

五.函数实现

需要注意的点:

  1. 按位右移>> :
    对有符号数都是算数右移(最高位是0补0,最高位是1补1)
    对无符号数都是逻辑右移(最高位补0)
  2. 提取符号的方法:x&1 (格式化该数,得到其符号)

1. bitXor

用~和&计算x^y

 /* bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
   return ~(~(x & ~y) & ~(~x & y));
}

思路:
等价于return (x&~y)|(y&~x); 但此处只能用~和&

2. tmin

返回最小二进制补整数

 /* tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1<<31; 
}

思路:
8位最小二进制补码为10000000,即1左移7位

3. isTmax

如果x是二进制补码的最大值,则返回1,否则返回0

 /* isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
 	int i = x+1;//Tmin,1000...
 	x=x+i;//-1,1111...
 	x=~x;//0,0000...
 	i=!i;//exclude x=0xffff...
 	x=x+i;//exclude x=0xffff...
 	return !x;
}

思路:
假设x为TMax(01111111,8位),则x+1得到TMin(10000000),再加x,取反再取非,即可返回1,而其余值返回0
但因为当x=-1时,最后返回值也为1,所以要排除这种情况

4.allOddBits

如果word中所有的奇数位为1,则返回1,否则返回0(位从0~31位)

 /* allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */

int allOddBits(int x) {
  int a_8 = 0xAA;
  int a_16 = (a_8 << 8)|(a_8);
  int a_32 = (a_16 << 16)|(a_16);
  int equal = (x & a_32) ^ a_32;  //要加 x&a_32 ,排除有偶数位是1的情况,如01010101,10101001
  return !equal;
}

思路:
说明文档规定常数不能超过8bit,所以先对0xAA扩展
逆元运算 a^a=0

5.negate

返回-x

 /* negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return (~x)+1;
}

思路:
一个数的相反数为其二进制位表示的按位取反,再+1,即-x=(~x)+1

6.isAsciiDigit

如果0x30 <= x <= 0x39,返回1,否则返回0

 /* 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 a=x+(~(0x30)+1);   //x-0x30
	int b=(~x+1)+0x39;	//0x39-x
	int c=a>>31;	//若a符号位为0,即a>0,则c为0;若a符号位为1,即a<0,则c为-1
	int d=b>>31;
	return !c&!d; //!0=1, !(-1)=0
}

思路:
要使0x30 <= x <= 0x39,则x-0x30>=0 且 0x39-x>=0
即运算结果的符号位为0,可以用移位操作(有符号数右移为算术右移)
另,减法运算可以看作x+(-x), -x=~x+1

7.conditional

用位级运算表示三目运算符 x?y:z

 /* conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
	int a=!!x;
	int condition=~a+1;
	return (condition&y)|(~condition&z);
}

思路:
用倒推的思路,返回值二选一,return结果一定是用 | 连接
而一个返回y,一个返回z,返回原值可以用补码全1(即-1)和&来实现,返回0可用0和&来实现
定义中间量condition=-1或0,condition需要与x相关联,则可以用!!x和取相反数的操作来实现
当 x!=0时,!!x=1, condition=~(!!x)+1=-1
当 x= 0时,!!x=0, condition=~(!!x)+1= 0

8.isLessOrEqual

如果x<=y,则返回1,否则返回0

 /* 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 negX=~x+1;          //-x
	int add=y+negX;	 //y-x
	int yxSign=add>>31&1;    //y-x的符号
	int xSign=x>>31&1;	  //x的符号
	int ySign=y>>31&1;	  //y的符号
	int checkSign=xSign^ySign;	//判断x,y的符号是否相同,如果相同,返回0,否则返回1
	return (!checkSign&!yxSign)|(checkSign&xSign);   //如果4~6行没有&1进行格式化,最后返回的值会是11111111(-1)或0,而不是00000001(1)或0 
							                         //(原因:(checkSign&xSign)这一部分括号内没有加!,区别isAsciiDigit(x),logicalNeg(x)和howManyBits(x),对符号位的应用)
	//返回1有两种情况:x,y符号相同标志位为0(相同)位与 y-x 的符号为0(y-x>=0)结果为1;
	//     	   符号相同标志位为1(不同)位与x的符号位为1(x<0)
}

思路:
(这里不可以只运用isAsciiDigit(x)的思路,用减法和判断符号位来实现
因为isAsciiDigit(x)中,0x30 <= x <= 0x39,相减判断不会有溢出的情况)
而此处可能出现溢出的情况:
当y<0,x>0时,可能出现 y-x>0 负溢出,而理论上用于判断y,x大小关系时应该是y-x<0,所以这种情况返回值取反
当y>0,x<0时,可能出现 y-x<0 正溢出,而理论上用于判断y,x大小关系时应该是y-x>0,所以这种情况返回值取反
即x,y符号不同正数为大,符号相同看差值符号
所以,返回1有两种情况:

  • x,y符号相同标志位为0(相同)位与 y-x 的符号为0(y-x>=0)结果为1;
  • x,y符号相同标志位为1(不同)位与x的符号位为1(x<0)

注:因为有符号数右移操作为算术右移,所以提取数的符号位要在右移之后&1,将其格式化,才能得到0或1

9.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) {
	int neg=x|((~x)+1);
	int sign=neg>>31;   //sign为0或-1
	return sign+1;    
}

思路:
运用0的性质,0的相反数还是0,按位或得到的值还是0(最高位也为0)
其他值与相反数按位或得到的最高位为1(值与相反数总有一个是负数)

10.howManyBits

使用补码时最少需要多少比特位

 /*howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {

	int b16,b8,b4,b2,b1,b0;
	int sign=x>>31;    //x的符号
	x = (sign&~x)|(~sign&x);/*如果x为正则不变,如果x为负则按位取反,因为要去掉符号位计算剩下需要几位,最后return值有+1,不影响
				   例如1111 1111 1111 1111 1111 1111 1111 1101表示-3,其按位取反得0000 0000 0000 0000 0000 0000 0000 0010
				   计算b16+b8+b4+b2+b1+b0=2,return 2+1=3,即-3最少需要3位比特位表示补码(相当101)*/

// 不断缩小范围
	b16 = !!(x>>16)<<4;//b16用于计数,检查最高十六位(32-16)是否有1,如果有,则!!(x>>16)=1, (1<<4)=0000...10000=2^4=16;如果没有,则为0
	x = x>>b16;//如果有(b16=16,至少需要16位),则将x右移16位;如果没有(b16=0),x不变
	b8 = !!(x>>8)<<3;//如果上一步移动了,则检查最高8位(32-16-8)是否有1;如果上一步没移动,则检查最高24位(32-8)是否有1
					 //如果有,b8=2^3=8;如果没有,则为0
	x = x>>b8;//如果有,x右移8位;如果没有,x不变
	b4 = !!(x>>4)<<2;
	x = x>>b4;
	b2 = !!(x>>2)<<1;
	x = x>>b2;
	b1 = !!(x>>1);
	x = x>>b1;
	b0 = x;
	return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

思路:
如表示12,只需要4+1(符号位)=5位即可
相当于将问题转化成了从最高位到最低位寻找第一个数据为1的问题,这里需要先排除负数符号位的影响
可以使用类似于二分的思想,先看高低16位(判断是否存在数据为1的比特位),再看8位,4,2,1…

ps:
(浮点数的位级计算规则暂时没学,故浮点数部分实验没做)

程序思路部分参考:

  • 终端验证:

六.小结

本实验为CSAPP书中第一章的内容,帮助我们理解C数据类型的位级表示和数据操作的位级行为,主要掌握整数的位级表示和运算,以及有符号数的一些特殊性质即可。

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐