¶ XJTU-ICS lab 1: Data Lab 数据实验
¶ 实验简介
相信大家在前几节课中学习中已经学到了不少东西，这个小实验的目的是让大家更加熟悉计算机中信息表示的常见模式和整数的位级表示。你将通过解决一系列编程“谜题”来做到这一点。其中许多谜题可能看起来构造的非常刻意（human-made），但你会发现自己在处理它们的过程中更多地考虑了计算机中比特的表示法。
这些题目并不简单，但是相信在尝试求解它们的过程中你能感受到一些乐趣，并提升一些动手与编程能力。
Enjoy and Have fun! 😉
¶ 注意事项
- 这是一个“个人”作业，请不要抄袭或者尝试几个人一起完成.
- 这些问题并不是一些完全全新的问题，我们鼓励“Google”学习解决一些代码之外的问题（环境问题/工具使用问题），但是频繁的查询代码谜题相关的解将使得这个实验与课程失去意义.
¶ 开发环境
推荐使用 ICSServer + Visual Studio Code + Remote-SSH插件 进行开发。
使用教程：
也可以自己搭建开发环境，环境要求为：
- Linux 或 WSL (推荐 Ubuntu 22.04)
- gcc-11
- GNU Make
¶ 实验准备
如果你已经顺利的在本地安装或者申请到了一个稳定的Linux环境，那么就可以顺利的开始你的实验~
¶ 资源下载与解压
- 下载文件 datalab-handout.tar
- 通过VSCode/
scp等方式将文件压缩文件上传到 ICSServer 或对应的 Linux 目录下 - 通过如下命令解压文件
tar xvf datalab-handout.tar
¶ 打开编辑器或终端并连接远端服务器
¶ 实验环境测试流程
一个比较推荐的实验环境测试流程如下：
¶ 检查文件完整性
解压完成后你将获得如下的一个完整目录，请检查你下载并解压的文件中是否包含如下目录：
linux$ ls
bits.c bits.h btest.c btest.h decl.c dlc Driverlib.pm driver.pl fshow.c ishow.c Makefile README tests.c
如出现文件完整性问题请及时询问同学或者找助教解决相关问题。
¶ 尝试make
Makefile 文件描述了 Linux 系统下 C/C++ 工程的编译规则，它用来自动化编译 C/C++ 项目。分发下去的实验包内已经有编写好的Makefile ，我们只需要在本机中尝试make，就可以获得一些 Linux 下的可执行文件。
（想要仔细了解Makefile相关信息：
What is a Makefile and how does it work?
Tutorial on writing makefiles)
make方法：在对应路径下在命令行输入make，回车.
linux$ make
如果make成功，一个典型的输出结果如下所示：
linux$ make
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
gcc -O -Wall -m32 -o fshow fshow.c
gcc -O -Wall -m32 -o ishow ishow.c
¶ 出错处理
一些可能出现的典型环境问题和解决方法将在附录中做简要解释，一个比较推荐的通用的问题解决方法的路径是：
- 查看报错，根据报错分析产生原因
- 直接咨询搜索引擎或者ChatGPT
- 若无法成功解决则咨询助教或登录相关软件官方社区询问。
¶ 尝试运行
如果成功make此时你的实验目录将会变成如下：
linux$ ls
bits.c bits.h btest btest.c btest.h decl.c dlc Driverhdrs.pm Driverlib.pm driver.pl fshow fshow.c ishow ishow.c Makefile README tests.c xxxxxx-handin.zip
简单验证可用性，我们简单运行一下make之后获得可执行文件btest
运行方法：命令行输入
linux$ ./btest
此时若运行成功，则会出现：
linux$ ./btest
Score Rating Errors Function
ERROR: Test bitAnd(-2147483648[0x80000000],-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test tmax() failed...
...Gives 2[0x2]. Should be 2147483647[0x7fffffff]
ERROR: Test negate(-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test copyLSB(-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be 0[0x0]
ERROR: Test getByte(-2147483648[0x80000000],0[0x0]) failed...
...Gives 2[0x2]. Should be 0[0x0]
ERROR: Test conditional(-2147483648[0x80000000],-2147483648[0x80000000],-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test isPositive(-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be 0[0x0]
ERROR: Test logicalShift(-2147483648[0x80000000],0[0x0]) failed...
...Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test replaceByte(-2147483648[0x80000000],0[0x0],0[0x0]) failed...
...Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test multFiveEighths(-268435457[0xefffffff]) failed...
...Gives 2[0x2]. Should be -167772160[0xf6000000]
ERROR: Test bang(-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be 0[0x0]
Total points: 0/100
出现如上或类似如上的输出结果，恭喜你！这证明您的本地环境已经准备好了，之后就可以快乐的开始Coding。
¶ 实验任务
实验准备中，我们在实验路径看到非常多的文件，你是否感到了一丝慌张？别慌！大多数的东西都是来帮助你更好的完成你的实验，你本地中唯一需要更改与提交的代码文件就是bits.c(This is all you need.)。找到这个文件，采用你心仪的编辑器，开始这个实验吧！
事实上，在bits.c中已经详细说明了实验的步骤，以及各种代码的规则，请大家仔细阅读bits.c的顶部注释部分：
/*
* CS:APP Data Lab
*
* <Please put your name and userid here>
*
* bits.c - Source file with your solutions to the Lab.
* This is the file you will hand in to your instructor.
*
* WARNING: Do not include the <stdio.h> header; it confuses the dlc
* compiler. You can still use printf for debugging without including
* <stdio.h>, although you might get a compiler warning. In general,
* it's not good practice to ignore compiler warnings, but in this
* case it's OK.
*/
#if 0
/*
* Instructions to Students:
*
* STEP 1: Read the following instructions carefully.
*/
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
INTEGER CODING RULES:
....
....
....
#endif
#if 0与#endif中的注释部分已经把这个实验要做什么以及怎么做写的很清楚了，这里只做一下总结。
¶ 第一步：仔细阅读以下实验要求以及代码规则
你的任务是通过修改bits.c文件中的函数，来提交你的实验结果。
¶ 代码规则：
bits.c文件包含了针对11个编程谜题的基本框架。在这个实验中你的任务就是在一个严格的Coding Rules（代码编写规则）之下完成每个函数编写（一个函数就代表一个小谜题），即用一行或多行C代码替换每个函数中的“return”语句，以实现该函数，这个严格的代码代码编写规则如下：
假设你写的函数格式如下：
int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
...
int varM = ExprM;
varJ = ExprJ;
...
varN = ExprN;
return ExprR;
}
每个"expr"只能包含以下这些：
- 整数常量
0到255（0xFF），不允许使用大的常量如0xffffffff。 - 函数参数和局部变量（不允许使用全局变量）。
- 一元整数操作符
! ~ - 二元整数操作符
& ^ | + << >>
同时一些编程谜题（函数）进一步限制了运算符的个数，详细的规则在
bits.c中每个函数上方的注释中有明确的说明，注意，如果不按照运算符个数实现代码是要扣分的哦(关于评分细则在后面评分中有明确说明)。
明确禁止使用的操作包括：
- 控制结构如
if, do, while, for, switch等。 - 使用宏定义。例如
#define AND(a, b) ((a) & (b))是不允许的。 - 在此文件中定义任何额外的函数。
- 调用任何函数。（我们在
bits.c中包含了printf以供大家debug使用，其余只允许使用C语言基础的运算符进行求解，最终提交的代码请不要包含printf） - 使用其他操作符，如
&&, ||, -, ?, :，每个谜题的上方注释处都有明确的合法操作符种类（Legal Ops）。 - 使用任何形式的类型转换。
- 使用除
int之外的任何数据类型，同时你不能使用数组、struct或union。 - 不允许使用
include添加新的库。
¶ 可以确定的假设：
在编写代码的时候，你可以建立如下假设：
- 数据类型
int的值为32位。 - 带符号数据的右移以算术右移方式执行。
- 对于
int数据类型，如果移位量小于0或大于31时，行为不可预测，也就是说当移位运算时，移动量应该在0和31之间。
¶ 注意事项：
-
可以使用
dlc（datalab checker）编译器来检查你的答案是否符合代码规则。如果不符合代码规则，即使可以实现对应的功能，也不会得分。 -
每个函数都有最大操作符数量(
Max Ops)，由dlc检查，如果超过使用的最大操作符数量，是可以允许的，但是要扣除一部分分数（具体在得分中说明）。 -
使用
btest测试工具来检查你写的函数的正确性。 -
使用
driver.pl正式验证你的函数。
¶ 第二步：根据代码规则修改bits.c中的函数
重要提示：为避免评分时出现意外，请确保使用dlc编译器检查你的解决方案是否遵循编码规则，并使用driver.pl正式验证你的解决方案是否正确。
¶ 一个例子：
看完了以上的一些冗长的限制之后，你可能感受到了疑惑。没事，接下来我们将从一个小例子出发，来解释这个实验到底需要做些什么。
bits.c中的每个小的谜题都会有谜题本身的限制，限制的具体内容写在了谜题函数上面的注释格式中。一个典型的谜题例子如下：
/*
* minusOne - return a value of -1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 2
* Rating: 1
*/
int minusOne(void) {
return 1;
}
如上题
- 题名：
minusOne - 题目要求：
return a value of -1，返回一个-1 - 合法的操作符：
! ~ & ^ | + << >> - 最多使用的操作符数量：2个
- 分值：1分
因此我们编写如下的程序代码：
int minusOne(void) {
return ~0;
}
如果在代码中使用了非法的操作符-，例如：
int minusOne(void) {
return -1;
}
尽管结果正确（使用btest测试没问题），这个谜题仍是不得分的。同样，如果在函数中使用了if for或0xffffffff，以及有任何规则禁止的操作，都是不得分的。
¶ 谜题
这个小节简要地介绍了你将要面临的小谜题~
¶ 评分
¶ 标准评分标准
你的分数会按照如下标准计算出来（满分为100分）
提供给你的11个小谜题，前9题的Rating（分值）是8分，最后2题的分值为3分，它们的Rating加起来一共78分，如果你可以通过btest所有检查，并且代码符合上文提到的代码规则（即可以通过dlc的检查），您将得到基本分78分。
同时谜题的最大操作符数量也是有限制的，如果你可以实现在最大操作符数量之内完成函数，每个函数得2分，如果你可以保持正确性并且操作符数量在最大操作符数量之内，你将获得剩余的“性能分”22分。
¶ 迟交
在超过原定的截止时间后，我们仍然接受同学的提交。此时，在lab中能获得的最高分数将随着迟交天数的增加而减少，具体服从以下给分策略：
超时7天（含7天）以内时，每天扣除3%的分数
超时7~14天（含14天）时，每天扣除4%的分数
超时14天以上时，每天扣除7%的分数，直至扣完
以上策略中超时不足一天的，均按一天计，自ddl时间开始计算。届时在线学习平台将开放迟交通道。
评分样例：如某同学小H在lab中取得95分，但晚交3天，那么他的最终分数就为95*(1-3*3%)=86.45分。同样的分数在晚交8天时，最终分数则为95*(1-7*3%-1*4%)=71.25分。
¶ 本地自动测试你的工作
上一节中，我们简要地谈到了你的实验成绩的组成，你可能感到了慌张。我该怎么保证我本地的程序是bugfree的呢？难不成要我自己手动人肉测试吗！？这显然是一种苛求，事实上，我们将完整的测试程序在实验分发包中给了你。
-
你可以自行使用测试程序
btest去测试你的程序的正确性。 -
与此同时，为了测试代码是否符合代码规则，我们给出了
dlc文件，dlc文件可以测试你的答案中是否符合代码规则，是否超出了最大操作符数量。 -
最后可以使用
driver.pl来测试程序的最终得分，driver.pl的测试这我们最终测试你提交上来文件的方法一致，换句话说，你如果在本地使用driver.pl测试得到了满分，那么你在最终的考核中也会得到一致的分数。 -
当然实验中还有两个程序可以帮助你完成这个实验，就是
ishow和fshow。
¶ 代码功能正确性 -> btest
如果你的bits.c的程序编写满足C语言要求并可以通过编译，在本地根目录下make之后你将会获得：
linux$ make
如下的目录：
linux$ ls
bits.c bits.h btest btest.c btest.h decl.c dlc Driverlib.pm driver.pl fshow fshow.c ishow ishow.c Makefile README tests.c
其中btest程序通过多次调用它们来检查bits.c中函数的正确性不同的参数值。要构建和使用它，请键入以下两个命令：
linux$ make
linux$ ./btest
需要注意的第一点是，你每次修改你的bits.c文件之后，你需要通过make重新build之后再进行测试：
即如果你新完成了一个谜题，你想要重新测试，则需要完成如下的流程：
linux$ make
linux$ ./btest
通常来说你会获得如下类型的运行结果：
linux$ ./btest
Score Rating Errors Function
8 8 0 bitAnd
8 8 0 tmax
8 8 0 negate
ERROR: Test copyLSB(-2147483648[0x80000000]) failed...
...Gives 2[0x2]. Should be 0[0x0]
8 8 0 getByte
8 8 0 conditional
8 8 0 isPositive
8 8 0 logicalShift
8 8 0 replaceByte
3 3 0 multFiveEighths
3 3 0 bang
Total points: 70/78
如上输出中告诉你每一题的得分，如果你的程序出错，则会输出对应的出错的题目与出错时候的输入和输出。
如上中，btest告诉我们：
Test copyLSB测试用例出差错
出错的输入是：-2147483648[0x80000000]
你的输出是：2[0x2]
正确的解应该是0[0x0]
根据输出的结果我们返回去继续修改我们的代码。
¶ 代码规则检测工具 -> dlc
btest并不会告诉我们写的代码是不是符合代码规则，这时候就需要使用dlc了。dlc的使用方法非常简单，如下：
linux$ ./dlc bits.c
如果你的代码都符合代码规则，那不会输出任何结果。
如果你的代码中有不符合代码规则的地方，一个典型的输出结果如下所示：
linux$ ./dlc bits.c
dlc:bits.c:202:copyLSB: Illegal if
dlc:bits.c:230:conditional: Illegal constant (0xffffffff) (only 0x0 - 0xff allowed)
dlc:bits.c:245:isPositive: Warning: 10 operators exceeds max of 8
如上，dlc告诉我们:
在202行，copyLSB函数中，使用了非法的if。
在230行，conditional函数中，使用了非法的常量0xffffffff。
在245行，isPositive函数中，使用了10个操作符，超过了Maxops=8个。
根据输出的结果我们返回去继续修改我们的代码。
dlc同时还有很多功能，例如./dlc -e bits.c等，你可以通过./dlc -h输出的帮助信息去自行了解。
¶ 实验最终得分工具 -> driver.pl
为了计算出自己的最终分数，我们提供了driver.pl来计算。
driver.pl的使用方法如下：
linux$ ./driver.pl
一个典型的结果如下：
linux$ ./driver.pl
1. Running './dlc -z' to identify coding rules violations.
dlc:bits.c:202:copyLSB: Illegal if
dlc:bits.c:204:copyLSB: Zapping function body!
dlc:bits.c:244:isPositive: Warning: 10 operators exceeds max of 8
2. Compiling and running './btest -g' to determine correctness score.
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
3. Running './dlc -Z' to identify operator count violations.
dlc:save-bits.c:202:copyLSB: Illegal if
dlc:save-bits.c:204:copyLSB: Zapping function body!
dlc:save-bits.c:244:isPositive: Warning: 10 operators exceeds max of 8
dlc:save-bits.c:244:isPositive: Zapping function body!
4. Compiling and running './btest -g -r 2' to determine performance score.
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
5. Running './dlc -e' to get operator count of each function.
Correctness Results Perf Results
Points Rating Errors Points Ops Puzzle
8 8 0 2 4 bitAnd
8 8 0 2 2 tmax
8 8 0 2 2 negate
0 8 1 0 0 copyLSB
8 8 0 2 3 getByte
8 8 0 2 7 conditional
0 8 1 0 10 isPositive
8 8 0 2 14 logicalShift
8 8 0 2 7 replaceByte
3 3 0 2 17 multFiveEighths
3 3 0 2 10 bang
Score = 80/100 [62/78 Corr + 18/22 Perf] (76 total operators)
可以看到，最终得了80分，其中copyLSB和isPositive函数由于不符合代码规则，不得分。
¶ 进制转换工具
在题目编写过程中，您可能需要一些工具的帮助来确定一些10进制数的16进制格式。
我们为您提供了相应的便捷工具ishow、fshow，您可以使用提供的程序 ishow 查看整数的十进制和十六进制表示形式。首先编译代码如下：
linux$ make
然后使用它来检查在命令行中键入的十六进制和十进制值：
linux$ ./ishow 0x80000000
Hex = 0x80000000, Signed = -2147483648, Unsigned = 2147483648
linux$ ./ishow -1
Hex = 0xffffffff, Signed = -1, Unsigned = 4294967295
它会帮助你完成进制的转换。
同理我们还提供了fshow工具，这是一个浮点数的转换器，但是这次的实验没有涉及，所以不做要求，大家有兴趣可以自行尝试，使用方法与ishow类似。
¶ 代码提交
在datalab-hanout 目录下执行make handin
linux$ make handin
目录下都会生成一个名为 <userid>-handin.zip 的 tarball 文件（其中 <userid> 为Linux系统中你的用户名）。（每次修改代码后，记着要重新运行make handin）
在在线学习平台上的作业模块中，将该文件作为附件提交即可。
¶ 一些小的建议
- Start Early
- 谜题可能比较复杂，可能一时间不可以直接想出优秀的满足要求的解法，但是不要气馁，没有人可以马上给出最优的解法。一个比较好的解题尝试路径是：
- 先尝试在纸上写出一般的解法
- 从一般解中找出更一般性的规律，这些规律可能通常需要你的灵光一现，但是对相信聪明的你来说这不是问题。
- 如果您是采用自己本地的环境，那么总会出现一些依赖缺失，软件未安装等等之类的错误。请大家不要慌张，一个好的程序员需要更好的了解自己手里的工具，而自己搭建环境往往就是其中很重要的一部分，请大家自行查询相关环境问题，自己动手解决问题（折腾（笑））的能力在计算机专业的学习中是非常重要的。
- 找到适合自己的好工具的能力：请大家在不断地动手中学习并找到适合自己的工具，以提高自己的效率。
最后祝大家玩的愉快。
¶ 附录
¶ 附录1 典型报错和解决方法
¶ Operation not Permitted
make成功后，您将获得一些可执行文件，例如我们在这个实验中我们将会获得如下文件
btest dlc driver.pl fshow ishow
这些二进制文件可以在我们的Linux环境中被加载运行，所有我们尝试执行程序都会在对应目录下以如下的形式执行：
linux$ ./filename
可能在运行各种可执行文件的时候经常会遇到一个报错：Operation not permitted，这其实是你并没有赋予可执行文件在你的系统中执行的权利。
典型报错场景：
linux$ make
CLANG_FORMAT=clang-format ./check-format bits.c
/bin/sh: 1: ./check-format: Permission denied
make: *** [helper.mk:126: .format-checked] Error 126
一个比较直接的解决方法就是：
linux$ chmod +x filename
（filename是您需要添加执行权限的文件）
文件权限相关学习文档：Linux File Permissions and Ownership Explained with Examples