From 87f0114dd8d2cf355c4e631ab089ddd75abdcc0c Mon Sep 17 00:00:00 2001 From: Richard Qin Date: Wed, 24 Sep 2025 13:50:55 +0800 Subject: Initial commit: Add starter code for Datalab --- .clang-format | 5 + .devcontainer/devcontainer.json | 25 + .github/workflows/classroom.yml | 36 + .gitignore | 10 + Dockerfile | 20 + Makefile | 21 + README.md | 228 +++ bits.c | 177 ++ bits.h | 24 + btest.c | 636 +++++++ btest.h | 20 + decl.c | 25 + fshow.c | 140 ++ ishow.c | 69 + pycparser/__init__.py | 93 ++ pycparser/_ast_gen.py | 336 ++++ pycparser/_build_tables.py | 40 + pycparser/_c_ast.cfg | 195 +++ pycparser/ast_transforms.py | 164 ++ pycparser/c_ast.py | 1125 +++++++++++++ pycparser/c_generator.py | 502 ++++++ pycparser/c_lexer.py | 555 +++++++ pycparser/c_parser.py | 1964 ++++++++++++++++++++++ pycparser/ply/LICENSE | 34 + pycparser/ply/__init__.py | 5 + pycparser/ply/cpp.py | 905 ++++++++++ pycparser/ply/ctokens.py | 133 ++ pycparser/ply/lex.py | 1099 ++++++++++++ pycparser/ply/yacc.py | 3494 +++++++++++++++++++++++++++++++++++++++ pycparser/ply/ygen.py | 74 + pycparser/plyparser.py | 133 ++ report/Markdown.png | Bin 0 -> 78056 bytes report/README.md | 45 + report/report.md | 48 + report/report.pdf | Bin 0 -> 259789 bytes test.py | 395 +++++ tests.c | 184 +++ 37 files changed, 12959 insertions(+) create mode 100644 .clang-format create mode 100644 .devcontainer/devcontainer.json create mode 100644 .github/workflows/classroom.yml create mode 100644 .gitignore create mode 100644 Dockerfile create mode 100644 Makefile create mode 100644 README.md create mode 100644 bits.c create mode 100644 bits.h create mode 100644 btest.c create mode 100644 btest.h create mode 100644 decl.c create mode 100644 fshow.c create mode 100644 ishow.c create mode 100644 pycparser/__init__.py create mode 100644 pycparser/_ast_gen.py create mode 100644 pycparser/_build_tables.py create mode 100644 pycparser/_c_ast.cfg create mode 100644 pycparser/ast_transforms.py create mode 100644 pycparser/c_ast.py create mode 100644 pycparser/c_generator.py create mode 100644 pycparser/c_lexer.py create mode 100644 pycparser/c_parser.py create mode 100644 pycparser/ply/LICENSE create mode 100644 pycparser/ply/__init__.py create mode 100644 pycparser/ply/cpp.py create mode 100644 pycparser/ply/ctokens.py create mode 100644 pycparser/ply/lex.py create mode 100644 pycparser/ply/yacc.py create mode 100644 pycparser/ply/ygen.py create mode 100644 pycparser/plyparser.py create mode 100644 report/Markdown.png create mode 100644 report/README.md create mode 100644 report/report.md create mode 100644 report/report.pdf create mode 100644 test.py create mode 100644 tests.c diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..a634304 --- /dev/null +++ b/.clang-format @@ -0,0 +1,5 @@ +BasedOnStyle: Chromium +IndentWidth: 4 +UseTab: Never +ColumnLimit: 0 +SortIncludes: false \ No newline at end of file diff --git a/.devcontainer/devcontainer.json b/.devcontainer/devcontainer.json new file mode 100644 index 0000000..7509595 --- /dev/null +++ b/.devcontainer/devcontainer.json @@ -0,0 +1,25 @@ +{ + "name": "DataLab", + "build": { + "dockerfile": "../Dockerfile", + "context": ".." + }, + "customizations": { + "vscode": { + "settings": { + "editor.formatOnSave": false, + "[c]": { + "editor.defaultFormatter": "xaver.clang-format" + }, + "[cpp]": { + "editor.defaultFormatter": "xaver.clang-format" + }, + "C_Cpp.default.cStandard": "gnu99" + }, + "extensions": [ + "ms-vscode.cpptools", + "xaver.clang-format" + ] + } + } +} \ No newline at end of file diff --git a/.github/workflows/classroom.yml b/.github/workflows/classroom.yml new file mode 100644 index 0000000..0777a9f --- /dev/null +++ b/.github/workflows/classroom.yml @@ -0,0 +1,36 @@ +name: Autograding Tests +'on': +- push +- repository_dispatch +permissions: + checks: write + actions: read + contents: read +jobs: + run-autograding-tests: + runs-on: ubuntu-22.04 + if: github.actor != 'github-classroom[bot]' + steps: + - name: Checkout code + uses: actions/checkout@v4 + - name: Setup + run: | + sudo apt-get update + sudo apt-get install -y build-essential \ + gcc-multilib + sudo apt-get install -y python3 + - name: datalab test + id: datalab-test + uses: panjd123/autograding-command-grader@v1 + with: + test-name: datalab test + setup-command: + command: python3 test.py + timeout: 10 + max-score: 37 + - name: Autograding Reporter + uses: panjd123/autograding-grading-reporter@v1 + env: + DATALAB-TEST_RESULTS: "${{steps.datalab-test.outputs.result}}" + with: + runners: datalab-test \ No newline at end of file diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..35d84c5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,10 @@ +.vscode +ishow +fshow +btest +venv/ +.autograder_result +result.txt +__pycache__ +yacctab.py +lextab.py \ No newline at end of file diff --git a/Dockerfile b/Dockerfile new file mode 100644 index 0000000..d65fdc4 --- /dev/null +++ b/Dockerfile @@ -0,0 +1,20 @@ +FROM ubuntu:20.04 + +RUN sed -i 's/archive.ubuntu.com/mirrors.tuna.tsinghua.edu.cn/g' /etc/apt/sources.list && \ + sed -i 's/security.ubuntu.com/mirrors.tuna.tsinghua.edu.cn/g' /etc/apt/sources.list && \ + sed -i 's/archive.canonical.com/mirrors.tuna.tsinghua.edu.cn/g' /etc/apt/sources.list + +RUN apt-get update && apt-get install -y \ + gcc \ + gcc-multilib \ + g++ \ + make \ + clang-format \ + git \ + python3 + +COPY . /app + +WORKDIR /app + +CMD ["/bin/bash"] \ No newline at end of file diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..744cd71 --- /dev/null +++ b/Makefile @@ -0,0 +1,21 @@ +CC = gcc +CFLAGS = -O0 -Wall -std=gnu99 +LIBS = -lm + +all: btest fshow ishow + +btest: btest.c bits.c decl.c tests.c btest.h bits.h + $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c + +fshow: fshow.c + $(CC) $(CFLAGS) -o fshow fshow.c + +ishow: ishow.c + $(CC) $(CFLAGS) -o ishow ishow.c + +# Forces a recompile. Used by the driver program. +btestexplicit: + $(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c + +clean: + rm -f *.o btest fshow ishow *~ yacctab.py lextab.py result.txt .autograder_result \ No newline at end of file diff --git a/README.md b/README.md new file mode 100644 index 0000000..6f46b28 --- /dev/null +++ b/README.md @@ -0,0 +1,228 @@ +# DataLab + +``` + ________ ________ _________ ________ ___ ________ ________ +|\ ___ \|\ __ \|\___ ___\\ __ \|\ \ |\ __ \|\ __ \ +\ \ \_|\ \ \ \|\ \|___ \ \_\ \ \|\ \ \ \ \ \ \|\ \ \ \|\ /_ + \ \ \ \\ \ \ __ \ \ \ \ \ \ __ \ \ \ \ \ __ \ \ __ \ + \ \ \_\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \____\ \ \ \ \ \ \|\ \ + \ \_______\ \__\ \__\ \ \__\ \ \__\ \__\ \_______\ \__\ \__\ \_______\ + \|_______|\|__|\|__| \|__| \|__|\|__|\|_______|\|__|\|__|\|_______| +``` + +模板仓库：[RUC DataLab](https://github.com/RUCICS/Datalab-2025Fall) + +## 项目编译与环境指南 + +C 语言编译环境 + +```bash +sudo apt-get update +sudo apt-get install build-essential +sudo apt-get install gcc-multilib +``` + +如果有 C 语言环境问题，你可以选择删除 `gcc` 和 `g++` 然后重新执行上述指令。 + +```bash +sudo apt-get remove gcc g++ +``` + +如果仍有问题，可以联系李甘助教获取服务器登陆信息，在服务器上完成本实验。 + +-------- + +Python 编译环境已弃用，现在你不需要执行任何指令来配置，如果你第一次读到这个文档，请忽略这一部分。对于服务器用户，你不需要执行任何配置。 + +> Python 编译环境，我们演示 Virtualenv 下的配置方法，如果你使用 Conda 可以自行配置类似的环境出来 +> +> ```bash +> sudo apt-get update +> sudo apt-get install python3 python3-pip python3-venv +> python3 -m venv venv # 如果你在我们提供的服务器上进行本实验，这一步请从这里开始 +> . venv/bin/activate +> pip install pycparser -i https://mirrors.aliyun.com/pypi/simple/ +> ``` + +-------- + +如果你想获得 VSCode 的最佳代码提示体验，请指定 `cStandard` 为 `gnu99`: + +```json +{ + "C_Cpp.default.cStandard": "gnu99" +} +``` + +> 面向高级用户，我们还提供了 devcontainer 的支持。有需要的同学可以自行使用。 + +### 如何编译 + +```bash +make +``` + +> 如果你不懂什么是 `make`，请询问 AI 生成工具 “什么是 make，我应该在什么时候执行 make，make 的原理是什么” + +### Quick Start + +```bash +# 在我们的服务器上，不需要执行这一行 +sudo apt-get update && sudo apt-get install build-essential gcc-multilib + +# 其中 annaFJM 改成你的用户名 +git clone git@github.com:RUCICS/datalab2025fall-annaFJM.git + +cd datalab2025fall-annaFJM + +make +python3 test.py +# 然后你应该看到最后一行输出 Total Points:0 的字样 +``` + +## 实验简述 + +本实验考察对数的二进制表示和位运算的认识。具体来说，本实验会给出多个函数要求实现，比如求两个数的异或，但你只能用限制范围内的位运算操作符（有时候允许更多）。 + +我们的题目和你们要完成的函数都在 [`bits.c`](./bits.c) 文件中。 + +### 一个例子 + +```c +/* + * bitAnd - x & y using only ~ and | + * Example: bitXor(4, 5) = 1 + * Legal ops: ~ | + * Max ops: 7 + * Difficulty: 1 + */ +int bitAnd(int x, int y) { + return ~(~x | ~y); +} +``` + +如在 `bitAnd` 题目中，你需要修改代码，使得： + +1. 保证函数的返回值符合要求 +2. 保证只使用了 `Legal ops` 中给出的符号 +3. 符号数的总数不能超过 `Max ops` + +### 具体要求 + +你被允许： + +- 对于整型题目，即 `float_i2f` 之前的题目，你被允许定义 `int` 变量，即不能定义 `unsigned`，除非题目允许 +- 对于浮点数题目，即 `float_i2f` 及之后的题目，你被允许定义 `int` 和 `unsigned` 的变量 + +你被禁止： + +- 禁止使用控制流语句，比如 `if`, `else`, `for`, `while`，除非题目允许 +- 禁止使用非位运算符号，比如 `&&`, `||`, `-`, `?:`,`!`, `>`, `==` 除非题目允许 +- 禁止使用其他不在 `Legal ops` 中的操作符 +- 特别说明，例如 `<<=`, `++` 这类 `x = x ? 1` 的 `?=` 符号，我们视作 `?` 符号，换句话说，只要 `?` 在 `Legal ops` 里，则 `?=` 也在。 +- 禁止超过 `Max ops` 个符号数 +- 禁止使用函数，或调用任何函数 +- 禁止使用宏 +- 禁止定义其他类型的变量，比如 `float`，`char`，结构体，数组，联合体等 +- 禁止使用类型转换： + - 我们绝对禁止显式类型转换，如 `(float)x` 和 `(int)(1.0f)` + - 对于隐式类型转换，如果你感觉你的解法利用了隐式类型转换，那你应该尽量避免；如果你的解法不依赖于该隐式类型转换，则无所谓。如有符号数和无符号数计算时，有符号数会被隐式类型转换为无符号数 +- 禁止使用任何浮点常量，比如 `1.0f`，当然你可以使用它的二进制形式代表的整数，注意不要违反上一条规则 +- 禁止使用 Undefined Behavior，比如对一个 32 位数逻辑右移超过 31 位，你应该假设我们的机器会在这时候返回不确定的结果，不得利用 Undefined Behavior，以免我们跨平台编译的时候结果不一致 +- 我们要求你的编译不能有任何警告，在迫不得已的情况下，请尽量用一些代码内编译器指令来消除警告，比如 `__attribute__((unused))` +- 禁止修改除了 `bits.c` 以外的文件 +- 禁止给 `bits.c` 文件添加任何头文件，这会导致测试错误。这不影响你使用 `printf` 函数， +但使用 `printf` 函数会与 `test.py` 脚本冲突，你可以使用下文的 `btest` 脚本来调试正确性， +正确性通过后再删除 `printf` 使用 `test.py` 脚本来测试合规性 + +其他事项： + +- 符号数计数不包括赋值等号 `=` 和控制流语句如 `if`, `for` 这种关键字，但例如条件表达式内的符号还是会被计算 + +### 如何评测 + +```bash +python3 test.py +python3 test.py -V # 显示更多信息 +``` + +我们提供了一个 `test.py` 脚本，它完成以下判断： + +- 尝试编译你的代码 +- 测试正确性，即是否能返回函数正确的结果 +- 测试合规性，即是否满足题目对符号数等的要求 + +该脚本要求你的代码不能包含输出到 stdout 的调试输出，如果你需要调试，请用下文的 `btest` 脚本。 +通常情况下，你可以只用 `btest` 测试，直到所有函数都能返回正确结果，再回到 `test.py` 测试。 + +输出示例： + +```bash +bitAnd 1/1: PASS detail: Pass using 4 operations including {'|', '~'} and {'int'}. +bitXor 0/1: FAIL error1: Test bitXor(-2147483648[0x80000000],-2147483648[0x80000000]) failed. Gives 2[0x2]. Should be 0[0x0] +... +Total points: 1/37 +``` + +> 该输出展示了一份正确第一个函数的作业。 + +> `-V` 参数会显示通过的函数所用操作符数量，但可能导致你的报错不明显，默认我们只显示 FAIL 的信息。 + +### 如何使用我们提供的工具 + +#### btest + +`btest` 是正确性检验工具，是 `test.py` 脚本的一部分，你可以根据需要单独使用它以方便调试。 + +执行正确性测试 + +```bash +make +./btest +``` + +以指定参数调用某个函数测试： + +```bash +make +./btest -1 1 -2 2 -f bitXor # bitXor(1, 2) +./btest -h # 查看 btest 的其他功能 +``` + +#### ishow + +```bash +./ishow 0x27 +Hex = 0x00000027, Signed = 39, Unsigned = 39 +``` + +#### fshow + +```bash +./fshow 0x15213243 +Floating point value 3.255334057e-26 +Bit Representation 0x15213243, sign = 0, exponent = 0x2a, fraction = 0x213243 +Normalized. +1.2593463659 X 2^(-85) +``` + +### 最终得分 + +DataLab 本次设置为通过性实验，即测试点通过则为满分。 + +### 实验报告 + +作为本学期的第一个实验，我们在此说明我们每个实验的报告提交要求。 + +首先，所有实验都遵循相同的通用要求，具体见 [`report/README.md`](report/README.md)。 + +每个实验又会提供专用的实验模板，其中包含了具体助教想要你们填写的内容，具体见 [`report/DataLab.md`](report/report.md)。 + +### 提交 + +将仓库 push 到上游 Github 仓库里即可完成提交。 + +## 注意事项 + +1. 不允许抄袭，助教会将每个人代码同网上代码和其他同学代码进行查重 +2. 报告需要写清楚做题思路，否则会酌情扣分 +3. 慎用代码格式化工具，如果一定要使用，请用 [`.clang-format`](./.clang-format) 文件，如果因格式化工具导致 `bits.c` 外的文件被修改，可能会被视为作弊 diff --git a/bits.c b/bits.c new file mode 100644 index 0000000..09baed2 --- /dev/null +++ b/bits.c @@ -0,0 +1,177 @@ +/* WARNING: Do not include any other libraries here, + * otherwise you will get an error while running test.py + * You can still use printf for debugging without including + * , 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. + * + * Using printf will interfere with our script capturing the execution results. + * At this point, you can only test correctness with ./btest. + * After confirming everything is correct in ./btest, remove the printf + * and run the complete tests with test.py. + */ + + /* + * bitAnd - x & y using only ~ and | + * Example: bitAnd(4, 5) = 4 + * Legal ops: ~ | + * Max ops: 7 + * Difficulty: 1 + */ +int bitAnd(int x, int y) { + return 2; +} + +/* + * bitXor - x ^ y using only ~ and & + * Example: bitXor(4, 5) = 1 + * Legal ops: ~ & + * Max ops: 7 + * Difficulty: 1 + */ +int bitXor(int x, int y) { + return 2; +} + +/* + * samesign - Determines if two integers have the same sign. + * 0 is not positive, nor negative + * Example: samesign(0, 1) = 0, samesign(0, 0) = 1 + * samesign(-4, -5) = 1, samesign(-4, 5) = 0 + * Legal ops: >> << ! ^ && if else & + * Max ops: 12 + * Difficulty: 2 + * + * Parameters: + * x - The first integer. + * y - The second integer. + * + * Returns: + * 1 if x and y have the same sign , 0 otherwise. + */ +int samesign(int x, int y) { + return 2; +} + +/* + * logtwo - Calculate the base-2 logarithm of a positive integer using bit + * shifting. (Think about bitCount) + * Note: You may assume that v > 0 + * Example: logtwo(32) = 5 + * Legal ops: > < >> << | + * Max ops: 25 + * Difficulty: 4 + */ +int logtwo(int v) { + return 2; +} + +/* + * byteSwap - swaps the nth byte and the mth byte + * Examples: byteSwap(0x12345678, 1, 3) = 0x56341278 + * byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD + * Note: You may assume that 0 <= n <= 3, 0 <= m <= 3 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 17 + * Difficulty: 2 + */ +int byteSwap(int x, int n, int m) { + return 2; +} + +/* + * reverse - Reverse the bit order of a 32-bit unsigned integer. + * Example: reverse(0xFFFF0000) = 0x0000FFFF reverse(0x80000000)=0x1 reverse(0xA0000000)=0x5 + * Note: You may assume that an unsigned integer is 32 bits long. + * Legal ops: << | & - + >> for while ! ~ (You can define unsigned in this function) + * Max ops: 30 + * Difficulty: 3 + */ +unsigned reverse(unsigned v) { + return 2; +} + +/* + * logicalShift - shift x to the right by n, using a logical shift + * Examples: logicalShift(0x87654321,4) = 0x08765432 + * Note: You can assume that 0 <= n <= 31 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 20 + * Difficulty: 3 + */ +int logicalShift(int x, int n) { + return 2; +} + +/* + * leftBitCount - returns count of number of consective 1's in left-hand (most) end of word. + * Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12, + * leftBitCount(0xFE00FF0F) = 7 + * Legal ops: ! ~ & ^ | + << >> + * Max ops: 50 + * Difficulty: 4 + */ +int leftBitCount(int x) { + return 2; +} + +/* + * float_i2f - Return bit-level equivalent of expression (float) x + * Result is returned as unsigned int, but it is to be interpreted as + * the bit-level representation of a single-precision floating point values. + * Legal ops: if else while for & | ~ + - >> << < > ! == + * Max ops: 30 + * Difficulty: 4 + */ +unsigned float_i2f(int x) { + return 2; +} + +/* + * floatScale2 - Return bit-level equivalent of expression 2*f for + * floating point argument f. + * Both the argument and result are passed as unsigned int's, but + * they are to be interpreted as the bit-level representation of + * single-precision floating point values. + * When argument is NaN, return argument + * Legal ops: & >> << | if > < >= <= ! ~ else + == + * Max ops: 30 + * Difficulty: 4 + */ +unsigned floatScale2(unsigned uf) { + return 2; +} + +/* + * float64_f2i - Convert a 64-bit IEEE 754 floating-point number to a 32-bit signed integer. + * The conversion rounds towards zero. + * Note: Assumes IEEE 754 representation and standard two's complement integer format. + * Parameters: + * uf1 - The lower 32 bits of the 64-bit floating-point number. + * uf2 - The higher 32 bits of the 64-bit floating-point number. + * Returns: + * The converted integer value, or 0x80000000 on overflow, or 0 on underflow. + * Legal ops: >> << | & ~ ! + - > < >= <= if else + * Max ops: 60 + * Difficulty: 3 + */ +int float64_f2i(unsigned uf1, unsigned uf2) { + return 2; +} + +/* + * floatPower2 - Return bit-level equivalent of the expression 2.0^x + * (2.0 raised to the power x) for any 32-bit integer x. + * + * The unsigned value that is returned should have the identical bit + * representation as the single-precision floating-point number 2.0^x. + * If the result is too small to be represented as a denorm, return + * 0. If too large, return +INF. + * + * Legal ops: < > <= >= << >> + - & | ~ ! if else && + * Max ops: 30 + * Difficulty: 4 + */ +unsigned floatPower2(int x) { + return 2; +} diff --git a/bits.h b/bits.h new file mode 100644 index 0000000..187e482 --- /dev/null +++ b/bits.h @@ -0,0 +1,24 @@ +int bitAnd(int, int); +int test_bitAnd(int, int); +int bitXor(int, int); // 保留 +int test_bitXor(int, int); // 保留 +int logtwo(int); // 保留 +int test_logtwo(int); // 保留 +int samesign(int, int); +int test_samesign(int, int); +int byteSwap(int, int, int); // 保留 +int test_byteSwap(int, int, int); // 保留 +int logicalShift(int, int); // 保留 +int test_logicalShift(int, int); // 保留 +unsigned float_i2f(int); // 保留 +unsigned test_float_i2f(int); // 保留 +int leftBitCount(int); // 保留 +int test_leftBitCount(int); // 保留 +int float64_f2i(unsigned, unsigned); +int test_float64_f2i(unsigned, unsigned); +unsigned reverse(unsigned); +unsigned test_reverse(unsigned); +unsigned floatScale2(unsigned); +unsigned test_floatScale2(unsigned); +unsigned floatPower2(int); +unsigned test_floatPower2(int); diff --git a/btest.c b/btest.c new file mode 100644 index 0000000..fe8130e --- /dev/null +++ b/btest.c @@ -0,0 +1,636 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include "btest.h" + +/* Not declared in some stdlib.h files, so define here */ +float strtof(const char* nptr, char** endptr); + +/************************* + * Configuration Constants + *************************/ + +/* Handle infinite loops by setting upper limit on execution time, in + seconds */ +#define TIMEOUT_LIMIT 10 + +/* For functions with a single argument, generate TEST_RANGE values + above and below the min and max test values, and above and below + zero. Functions with two or three args will use square and cube + roots of this value, respectively, to avoid combinatorial + explosion */ +#define TEST_RANGE 500000 + +/* This defines the maximum size of any test value array. The + gen_vals() routine creates k test values for each value of + TEST_RANGE, thus MAX_TEST_VALS must be at least k*TEST_RANGE */ +#define MAX_TEST_VALS 13 * TEST_RANGE + +/********************************** + * Globals defined in other modules + **********************************/ +/* This characterizes the set of puzzles to test. + Defined in decl.c and generated from templates in ./puzzles dir */ +extern test_rec test_set[]; + +/************************************************ + * Write-once globals defined by command line args + ************************************************/ + +/* Emit results in a format for autograding, without showing + and counter-examples */ +static int grade = 0; + +/* Time out after this number of seconds */ +static int timeout_limit = TIMEOUT_LIMIT; /* -T */ + +/* If non-NULL, test only one function (-f) */ +static char* test_fname = NULL; + +/* Special case when only use fixed argument(s) (-1, -2, or -3) */ +static int has_arg[3] = {0, 0, 0}; +static unsigned argval[3] = {0, 0, 0}; + +/* Use fixed weight for rating, and if so, what should it be? (-r) */ +static int global_rating = 0; + +/****************** + * Helper functions + ******************/ + +/* + * Signal - installs a signal handler + */ +typedef void handler_t(int); + +handler_t* Signal(int signum, handler_t* handler) { + struct sigaction action, old_action; + + action.sa_handler = handler; + sigemptyset(&action.sa_mask); /* block sigs of type being handled */ + action.sa_flags = SA_RESTART; /* restart syscalls if possible */ + + if (sigaction(signum, &action, &old_action) < 0) + perror("Signal error"); + return (old_action.sa_handler); +} + +/* + * timeout_handler - SIGALARM hander + */ +sigjmp_buf envbuf; +void timeout_handler(int sig) { + siglongjmp(envbuf, 1); +} + +/* + * random_val - Return random integer value between min and max + */ +static int random_val(int min, int max) { + double weight = rand() / (double)RAND_MAX; + int result = min * (1 - weight) + max * weight; + return result; +} + +void pack_store(int test_vals_low[], int test_vals_high[], int* test_count, int64_t value) { + test_vals_low[*test_count] = value & 0xFFFFFFFF; + test_vals_high[*test_count] = (value >> 32) & 0xFFFFFFFF; + (*test_count)++; +} + +/* + * gen_float64_vals - 生成 64 位 float 的测试数据，分别填充到 test_vals_low 和 test_vals_high 中 + */ +static int gen_float64_vals(int test_vals_low[], int test_vals_high[], int test_range, int arg_low, int arg_high) { + int64_t i; + int test_count = 0; + if (has_arg[arg_low] && has_arg[arg_high]) { + test_vals_low[0] = argval[arg_low]; + test_vals_high[0] = argval[arg_high]; + return 1; + } else if (has_arg[arg_low] || has_arg[arg_high]) { + printf("Configuration error: You can't set only one of the two float arguments, as they are a pair.\n"); + exit(1); + } + + int64_t smallest_norm = 0x0010000000000000; + int64_t one = 0x3ff0000000000000; + int64_t largest_norm = 0x7fefffffffffffff; + + int64_t inf = 0x7ff0000000000000; + int64_t nan = 0x7ff8000000000000; + int64_t sign = 0x8000000000000000; + + for (i = 0; i < test_range; i++) { + /* Denorms around zero */ + pack_store(test_vals_low, test_vals_high, &test_count, i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | i); + + /* Region around norm to denorm transition */ + pack_store(test_vals_low, test_vals_high, &test_count, smallest_norm + i); + pack_store(test_vals_low, test_vals_high, &test_count, smallest_norm - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (smallest_norm + i)); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (smallest_norm - i)); + + /* Region around one */ + pack_store(test_vals_low, test_vals_high, &test_count, one + i); + pack_store(test_vals_low, test_vals_high, &test_count, one - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (one + i)); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (one - i)); + + /* Region below largest norm */ + pack_store(test_vals_low, test_vals_high, &test_count, largest_norm - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (largest_norm - i)); + } + + /* special vals */ + pack_store(test_vals_low, test_vals_high, &test_count, inf); /* inf */ + pack_store(test_vals_low, test_vals_high, &test_count, sign | inf); /* -inf */ + pack_store(test_vals_low, test_vals_high, &test_count, nan); /* nan */ + pack_store(test_vals_low, test_vals_high, &test_count, sign | nan); /* -nan */ + return test_count; +} + +/* + * gen_vals - Generate the integer values we'll use to test a function + */ +static int gen_vals(int test_vals[], int min, int max, int test_range, int arg) { + int i; + int test_count = 0; + + /* Special case: If the user has specified a specific function + argument using the -1, -2, or -3 flags, then simply use this + argument and return */ + if (has_arg[arg]) { + test_vals[0] = argval[arg]; + return 1; + } + + /* + * Special case: Generate test vals for floating point functions + * where the input argument is an unsigned bit-level + * representation of a float. For this case we want to test the + * regions around zero, the smallest normalized and largest + * denormalized numbers, one, and the largest normalized number, + * as well as inf and nan. + */ + if ((min == 1 && max == 1)) { + unsigned smallest_norm = 0x00800000; + unsigned one = 0x3f800000; + unsigned largest_norm = 0x7f000000; + + unsigned inf = 0x7f800000; + unsigned nan = 0x7fc00000; + unsigned sign = 0x80000000; + + /* Test range should be at most 1/2 the range of one exponent + value */ + if (test_range > (1 << 23)) { + test_range = 1 << 23; + } + + /* Functions where the input argument is an unsigned bit-level + representation of a float. The number of tests generated + inside this loop body is the value k referenced in the + comment for the global variable MAX_TEST_VALS. */ + + for (i = 0; i < test_range; i++) { + /* Denorms around zero */ + test_vals[test_count++] = i; + test_vals[test_count++] = sign | i; + + /* Region around norm to denorm transition */ + test_vals[test_count++] = smallest_norm + i; + test_vals[test_count++] = smallest_norm - i; + test_vals[test_count++] = sign | (smallest_norm + i); + test_vals[test_count++] = sign | (smallest_norm - i); + + /* Region around one */ + test_vals[test_count++] = one + i; + test_vals[test_count++] = one - i; + test_vals[test_count++] = sign | (one + i); + test_vals[test_count++] = sign | (one - i); + + /* Region below largest norm */ + test_vals[test_count++] = largest_norm - i; + test_vals[test_count++] = sign | (largest_norm - i); + } + + /* special vals */ + test_vals[test_count++] = inf; /* inf */ + test_vals[test_count++] = sign | inf; /* -inf */ + test_vals[test_count++] = nan; /* nan */ + test_vals[test_count++] = sign | nan; /* -nan */ + + return test_count; + } + + /* + * Normal case: Generate test vals for integer functions + */ + + /* If the range is small enough, then do exhaustively */ + if (max - MAX_TEST_VALS <= min) { + for (i = min; i <= max; i++) + test_vals[test_count++] = i; + return test_count; + } + + /* Otherwise, need to sample. Do so near the boundaries, around + zero, and for some random cases. */ + for (i = 0; i < test_range; i++) { + /* Test around the boundaries */ + test_vals[test_count++] = min + i; + test_vals[test_count++] = max - i; + + /* If zero falls between min and max, then also test around zero */ + if (i >= min && i <= max) + test_vals[test_count++] = i; + if (-i >= min && -i <= max) + test_vals[test_count++] = -i; + + /* Random case between min and max */ + test_vals[test_count++] = random_val(min, max); + } + return test_count; +} + +/* + * test_0_arg - Test a function with zero arguments + */ +static int test_0_arg(funct_t f, funct_t ft, char* name) { + int r = f(); + int rt = ft(); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s() failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, r, r, rt, rt); + + return error; +} + +/* + * test_1_arg - Test a function with one argument + */ +static int test_1_arg(funct_t f, funct_t ft, int arg1, char* name) { + funct1_t f1 = (funct1_t)f; + funct1_t f1t = (funct1_t)ft; + int r, rt, error; + + r = f1(arg1); + rt = f1t(arg1); + error = (r != rt); + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, r, r, rt, rt); + + return error; +} + +/* + * test_2_arg - Test a function with two arguments + */ +static int test_2_arg(funct_t f, funct_t ft, int arg1, int arg2, char* name) { + funct2_t f2 = (funct2_t)f; + funct2_t f2t = (funct2_t)ft; + int r = f2(arg1, arg2); + int rt = f2t(arg1, arg2); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, r, r, rt, rt); + + return error; +} + +/* + * test_3_arg - Test a function with three arguments + */ +static int test_3_arg(funct_t f, funct_t ft, int arg1, int arg2, int arg3, char* name) { + funct3_t f3 = (funct3_t)f; + funct3_t f3t = (funct3_t)ft; + int r = f3(arg1, arg2, arg3); + int rt = f3t(arg1, arg2, arg3); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, arg3, arg3, r, r, rt, rt); + + return error; +} + +/* + * test_function - Test a function. Return number of errors + */ +static int test_function(test_ptr t, int arg_low, int arg_high) { + int test_counts[3]; /* number of test values for each arg */ + int args = t->args; /* number of function arguments */ + int arg_test_range[3] = {0}; /* test range for each argument */ + int i, a1, a2, a3; + int errors __attribute__((unused)) = 0; + + /* These are the test values for each arg. Declared with the + static attribute so that the array will be allocated in bss + rather than the stack */ + static int arg_test_vals[3][MAX_TEST_VALS]; + + /* Sanity check on the number of args */ + if (args < 0 || args > 3) { + printf("Configuration error: invalid number of args (%d) for function %s\n", args, t->name); + exit(1); + } + + /* Assign range of argument test vals so as to conserve the total + number of tests, independent of the number of arguments */ + if (args == 1) { + arg_test_range[0] = TEST_RANGE; + } else if (args == 2) { + arg_test_range[0] = pow((double)TEST_RANGE, 0.5); /* sqrt */ + arg_test_range[1] = arg_test_range[0]; + } else { + arg_test_range[0] = pow((double)TEST_RANGE, 0.333); /* cbrt */ + arg_test_range[1] = arg_test_range[0]; + arg_test_range[2] = arg_test_range[0]; + } + + /* Sanity check on the ranges */ + if (arg_test_range[0] < 1) + arg_test_range[0] = 1; + if (arg_test_range[1] < 1) + arg_test_range[1] = 1; + if (arg_test_range[2] < 1) + arg_test_range[2] = 1; + + /* Create a test set for each argument */ + for (i = 0; i < args; i++) { + if (i == arg_low || i == arg_high) + continue; + test_counts[i] = gen_vals(arg_test_vals[i], + t->arg_ranges[i][0], /* min */ + t->arg_ranges[i][1], /* max */ + arg_test_range[i], + i); + } + + if (arg_low != -1 && arg_high != -1) { + if (args != 2) { + printf("Configuration error: invalid number of args (%d) for function %s. Support only two arguments for now.\n", args, t->name); + exit(1); + } + int test_count = gen_float64_vals(arg_test_vals[arg_low], arg_test_vals[arg_high], TEST_RANGE, arg_low, arg_high); + test_counts[arg_low] = test_count; + test_counts[arg_high] = test_count; + } + + /* Handle timeouts in the test code */ + if (timeout_limit > 0) { + int rc; + rc = sigsetjmp(envbuf, 1); + if (rc) { + /* control will reach here if there is a timeout */ + errors = 1; + printf("ERROR: Test %s failed.\n Timed out after %d secs (probably infinite loop)\n", t->name, timeout_limit); + return errors; + } + alarm(timeout_limit); + } + + /* Test function has no arguments */ + if (args == 0) { + errors += test_0_arg(t->solution_funct, t->test_funct, t->name); + return errors; + } + + /* + * Test function has at least one argument + */ + + /* Iterate over the values for first argument */ + + if (arg_low != -1 && arg_high != -1) { + for (a1 = 0; a1 < test_counts[0]; a1++) { + errors += test_2_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a1], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } + return errors; + } + + for (a1 = 0; a1 < test_counts[0]; a1++) { + if (args == 1) { + errors += test_1_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } else { + /* if necessary, iterate over values for second argument */ + for (a2 = 0; a2 < test_counts[1]; a2++) { + if (args == 2) { + errors += test_2_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } else { + /* if necessary, iterate over vals for third arg */ + for (a3 = 0; a3 < test_counts[2]; a3++) { + errors += test_3_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + arg_test_vals[2][a3], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } /* a3 */ + } + } /* a2 */ + } + } /* a1 */ + + return errors; +} + +/* + * run_tests - Run series of tests. Return number of errors + */ +static int run_tests() { + int i; + int errors = 0; + double points = 0.0; + double max_points = 0.0; + + // printf("Score\tRating\tErrors\tFunction\n"); + + for (i = 0; test_set[i].solution_funct; i++) { + int terrors; + double tscore; + double tpoints; + if (!test_fname || strcmp(test_set[i].name, test_fname) == 0) { + int rating = global_rating ? global_rating : test_set[i].rating; + if (strcmp(test_set[i].name, "float64_f2i") == 0) { // special case for float64_f2i + terrors = test_function(&test_set[i], 0, 1); + } else { + terrors = test_function(&test_set[i], -1, -1); + } + errors += terrors; + tscore = terrors == 0 ? 1.0 : 0.0; + tpoints = rating * tscore; + points += tpoints; + max_points += rating; + + if (grade || terrors < 1) + printf(" %.0f\t%d\t%d\t%s\n", + tpoints, rating, terrors, test_set[i].name); + } + } + + // printf("Total points: %.0f/%.0f\n", points, max_points); + return errors; +} + +/* + * get_num_val - Extract hex/decimal/or float value from string + */ +static int get_num_val(char* sval, unsigned* valp) { + char* endp; + + /* See if it's an integer or floating point */ + int ishex = 0; + int isfloat = 0; + int i; + for (i = 0; sval[i]; i++) { + switch (sval[i]) { + case 'x': + case 'X': + ishex = 1; + break; + case 'e': + case 'E': + if (!ishex) + isfloat = 1; + break; + case '.': + isfloat = 1; + break; + default: + break; + } + } + if (isfloat) { + float fval = strtof(sval, &endp); + if (!*endp) { + *valp = *(unsigned*)&fval; + return 1; + } + return 0; + } else { + long long int llval = strtoll(sval, &endp, 0); + long long int upperbits = llval >> 31; + /* will give -1 for negative, 0 or 1 for positive */ + if (!*valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) { + *valp = (unsigned)llval; + return 1; + } + return 0; + } +} + +/* + * usage - Display usage info + */ +static void usage(char* cmd) { + printf("Usage: %s [-hg] [-r ] [-f [-1|-2|-3 ]*] [-T