今天你要来点 puzzle 吗?
Intro
你的解法被允许包含任何可以通过编译的代码, 包括但不限于内联汇编 (不过 puzzle 设计时并不会考虑这种解法), 未指明行为或未定义行为, 但请确保自己知道自己解法的正确性从何而来. 当你的解法依赖 RSI/ABI/编译器特性时, 请以如下配置为参考 (这个配置下的编译结果应该和 NOI Linux 2 是一致的, 如果你发现不一致的情况可以告诉我 qwq):
Target: x86_64-linux-gnu
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04.2)
全文编译命令如下:
g++ puz_N.cpp ans_N.cpp -Wall -Wextra -Wshadow -Wconversion -Werror -Og -fno-inline -fno-stack-protector -D PUZZLE_ID=N -o test
其中:
-Wall -Wextra -Wshadow -Wconversion -Werror要求你在写 UB 的时候伪装一下, 不能被编译器发现 (大嘘).-Og保证你的代码几乎被逐句翻译为可读性较高的汇编指令而不引入过多优化.-fno-inline显式阻止了函数内联 (这在-Og优化级别下仍然可能发生), 以方便你更好地利用过程调用相关的 ABI 约定.-fno-stack-protector关闭了汇编指令层次的栈保护措施, 我们大概不会做这方面的 puzzle, 关掉这个单纯是为了让函数序言不那么冗长.-D PUZZLE_ID=N定义了头文件所辅助的 puzzle id. 这在一些任务中是必要的.
测试用的头文件如下 (注意它可能会不断更新, 但总是兼容旧版; 你可以在 ans_N.cpp 中直接 include 它).
#pragma once
#include <array>
#include <cmath>
#include <cstdio>
#include <random>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <type_traits>
typedef u_int8_t u8;
typedef u_int32_t u32;
typedef long double f80;
typedef u_int64_t u64;
typedef __uint128_t u128;
// #define PUZZLE_ID 1 // 你可以手动设置 PUZZLE_ID 来方便 IntelliSense 分析
#ifdef PUZZLE_ID
# if PUZZLE_ID == 1
constexpr size_t F80_SIZE = sizeof(f80);
constexpr int F80_BIAS = 16383;
constexpr size_t MESSAGE_LEN = F80_SIZE - 9;
typedef u8 message_t[MESSAGE_LEN];
# endif
#endif
#define Success() \
do { \
fprintf(stderr, "Puzzle solved.\n"); \
exit(0); \
} while (false)
#define Require(cond, msg, ...) \
do { \
if (!(cond)) { \
fprintf(stderr, "Failed: " msg "\n", ##__VA_ARGS__); \
_Exit(1); \
} \
} while (false)
#define ReqEq(type, ph, x, y) \
Require((type)(x) == (type)(y), ph " != " ph, (type)(x), (type)(y))
#define ReqEq_f80(x, y) ReqEq(f80, "%.20Lf", x, y)
#define ReqEq_u32(x, y) ReqEq(u32, "%u", x, y)
我们认为你的答案正确, 当且仅当它能通过编译并且使得 test 正常运行并最终返回 0.
为了方便你测试, 提供一个编译脚本:
#!/bin/bash
id=$1
puzzle=puz_$id.cpp
answer=ans_$id.cpp
FLAGS="-Wall -Wextra -Wshadow -Wconversion -Werror -Og -fno-inline -fno-stack-protector"
g++ $FLAGS -D PUZZLE_ID=$id $puzzle $answer -o test && ./test
你可以将 judge.h, puz_N.cpp, ans_N.cpp 和 run.sh 保存在同一目录下, 然后使用命令
linux> chmod +x run.sh
为脚本添加可执行权限, 此后就能使用
linux> ./run.sh N
来编译并运行第 \(N\) 个 puzzle 的程序.
Puzzle #0
在本 puzzle 中, 你需要猜测由 random_device 返回的随机数的结果. random_device 一般采样自依赖系统设备实现的真随机数, 你能够一次猜对吗?
- 特殊说明:
- 允许依赖汇编结果编码.
- 允许使用内联汇编.
- 允许引入未指明或未定义行为, 只要它能通过编译并且在你的设备上成功运行.
// puz_0.cpp
#include "judge.h"
u32 guess(void);
u32 sample() {
return std::random_device()();
}
int main() {
u32 x = sample();
u32 y = guess();
ReqEq_u32(x, y);
Success();
}
请在 ans_0.cpp 中实现 u32 guess(void) 函数.
- 冷知识: 在函数声明时,
u32 guess(void);和u32 guess();并不等价. 前者告诉编译器 "这是一个无参数的函数", 后者告诉编译器 "这是一个函数, 但我不知道它的参数类型".
Discussion
@zero4338 提供了一种解答 (因为 ta 提供答案时编译命令中的 -Wx 选项没有这么多, 我略修改了代码使得它可以通过编译):
#include "judge.h"
u32 guess(void) {
int z = 0xdeadbeef; // useless value to escape compiler check
int y = *((u32*)(&z) + 12);
return y;
}
然而这个解答并不正确: 除了 guess::z 因为被取地址必须分配在栈上外, 其他三个局部变量 (main::x, main::y, guess::y) 并不一定被编译器安排在栈空间上, 而更有可能被安排为寄存器变量, 这时基于栈偏移的做法就不奏效了.
不过, 我们可以弱化一下问题, 让基于栈偏移的做法有前途. 我们将所有局部变量加上 volatile 修饰:
volatile是一种类型修饰符, 告诉编译器受修饰变量可能被除当前线程以外的线程, 程序等修改. 从效果上,volatile强制编译器每次读变量时, 都从内存中读取 (因此它也必须存储在内存中), 而不把它缓存在寄存器中.- 对
volatile int x;的x++和++x从-std=c++2a(C++ 20) 起被遗弃 (deprecated, by-Wvolatile), 因为它们隐含地违背了上述原则.
- 对
// puz_0.cpp
#include "judge.h"
u32 guess(void);
u32 sample() {
return std::random_device()();
}
int main() {
volatile u32 x = sample();
volatile u32 y = guess();
ReqEq_u32(x, y);
return 0;
}
// ans_0.cpp
#include "judge.h"
u32 guess(void) {
volatile u32 z = 0xdeadbeef; // useless value to escape compiler check
volatile u32 y = *((u32*)(&z) + 12);
return y;
}
这样, 编译后使用命令
linux> objdump -d test
objdump命令用于展示目标文件 (你可以理解作由编译器生成的具有特定组织格式的一类二进制文件) 的信息.-d/--disassemble指定展示可执行节 (executable section) 的反汇编信息.
并观察 main 和 guess 的汇编:
main:
endbr64
sub $0x18,%rsp ; 将栈指针 (总是 rsp) 减去 0x18
; 相当于为当前函数分配 0x18 字节的栈帧
call 1349 ; call <sample>, 这个函数名 objdump 会帮你标注
; 汇编里的数字是 PC 相对寻址的偏移量, 不重要
mov %eax,0xc(%rsp) ; eax 是 sample() 的 32 位返回值
; 所以 main::x 在 rsp+12
call 15a7 ; call <guess>
; 此指令执行后 rsp<-rsp+8 (压入返回地址),
; 紧接着从 guess 标签的下一条指令开始执行...
mov %eax,0x8(%rsp)
mov 0xc(%rsp),%edx
mov 0x8(%rsp),%eax
cmp %eax,%edx
; ......
; ......
guess:
endbr64
movl $0xdeadbeef,-0x4(%rsp) ; guess::z 在 rsp-4
mov 0x2c(%rsp),%eax ; 求出 guess::y 的值. 我们需要调整 0x2c 这个偏移量
mov %eax,-0x8(%rsp)
mov -0x8(%rsp),%eax
ret
根据汇编, 正确的 u32 指针偏移量应该是 \((12+8+4)/4=6\), 即 y = *((u32*)(&z) + 6). 此时编译运行成功.
- (相信大家比较熟悉了.) C/C++ 中, 对指针的加减行为 由指针类型决定. 笼统地说,
type* p的p + x意味着p偏移x * sizeof(type). 特别地, 在 C++ 中, 对void*的加法是未定义行为, 并且可能无法通过编译. 但 C 的 GNU 扩展中规定void*的加法步长为 \(1\), 相当于将它视作char*来运算.
但是, 即使加上 volatile 标记, 这种解法也不尽优美: "main::x 在 %rsp+12 仍然依赖于编译器的规划." 再例如, 我们知道 x86-64 Linux 约定, 在 call 指令之前, %rsp 必须 \(16\) 字节对齐. 因此, 进入 main 函数时, $rsp % 16 == 8, main 函数内部申请了 \(4+4=8\) 字节栈空间, 所以理论上编译器可以只给 main 分配 \(8\) 字节内存 (即代码块第三行改为 sub $0x8,%rsp), 这样也满足栈对齐需求. 选择 \(24\) 字节而非 \(8\) 字节仍然依赖于编译器甚至优化选项.
@FjswYuzu 提供了一种内联汇编的解法, 他的思路与我们期待的解法完全相同:
// ans_0.cpp
__attribute__((naked))
u32 guess(void) {
__asm__("ret");
}
即使不查阅汇编代码, 我们也能够猜测 main 函数中, 两次函数调用附近的代码段形如:
main:
; ......
call <sample>
mov %eax, <x>
call <guess>
mov %eax, <y>
; ......
所以, 如果 guess 函数不修改 eax, 我们就已经大功告成了. 直接让它 ret 就是最简单的做法.
Solution
当然, 按照我们一开始的约定, 这里提供一种不使用内联汇编的解法. 它和 @FjswYuzu 的解法本质相同.
#include "judge.h"
static void foo() {} // 定义一个真的 "just ret" 的函数
u32 guess() {
return ((u32 (*)(void))foo)();
// 哄骗编译器, 让编译器认为那个空函数会返回一个值
// 无论这里编译器是否采取尾递归优化, 返回的值都一定是一开始的 eax
}
其实我们很想写成:
#include "judge.h"
static void foo() {}
auto guess = (u32 (*)(void))foo;
但显而易见地, 链接器 (linker) 并不喜欢这样的代码: 它会认为 guess 只是一个全局的指针变量 (在 .data 中), 而非全局函数名 (在 .text 中). 这份代码可以通过编译但无法链接为可执行程序 (puz_0::guess 符号无法解析). 上面这种写法需要 puz_0.cpp 中的对应声明替换为:
extern u32 (*guess)(void);
Puzzle #1
在此 puzzle 中, 你需要通过一个 \(80\) 位扩展精度浮点数传递至多 \(7\) 个字节的信息 (信息长度可能与你的设备或编译器有关), 并保证浮点数的数值误差非常小. \(80-7\times8=24\), 这怎么可能保持浮点精度呢?
- 特殊说明:
- 保证作为信使的浮点数是 非负实数 (既不是
nan也不是inf), 你可以在编解码时使用这个性质. - 注意 IEEE 754 扩展双精度标准与一般的单/双精度浮点标准存在差异, 即使你很熟悉后者, 也建议你查阅关于前者的相关资料.
- 请阅读
errorCheck部分来获知你所需要保持的精度要求. - 请阅读
judge.h的message_t相关定义来获知那你所需要传递的信息长度要求. - 请不要在编解码时通过全局/静态变量等方式偷渡信息.
- 请不要窃取任何堆栈或寄存器信息.
- 以上两条是君子协议, 代码层面并没有限制, 但请你尽量遵守 (标准解法当然是遵守的啦).
- 保证作为信使的浮点数是 非负实数 (既不是
#include "judge.h"
static std::mt19937_64 rng(std::random_device{}());
/**
* 检查 src 相对 std 的误差是否在允许范围内.
* 绝对误差不超过 2^{-BIAS-56} 或者相对误差不超过 2^{-57} 即可.
*/
static const f80 ABS_LIMIT = std::ldexp(f80(1), -F80_BIAS - 56);
static const f80 REL_LIMIT = std::ldexp(f80(1), -57);
static bool errorCheck(f80 std, f80 src) {
assert(std >= 0); // which means src is non-negative and not NaN
if (src != src) return false; // NaN check
if (std == src) return true;
f80 absErr = std - src;
if (absErr < 0) absErr = -absErr;
if (absErr <= ABS_LIMIT) return true;
f80 relErr = absErr / std;
return relErr <= REL_LIMIT;
}
/**
* 以下函数满足:
* - encode(M, X) => errorCheck(interpret(X), M)
* - encode(M, X), extract(M, Y) => Y==X
*/
/** 将 message 编码入 messenger 中 */
void encode(f80 *messenger, message_t message);
/** 从由 encode 编码过的 messenger 中解码出 message */
void extract(f80 *messenger, message_t message);
/** 从由 encode 编码过的 messenger 中还原原来的 messenger */
f80 interpret(f80 *messenger);
/**
* 以下是测试数据生成与测试运行代码, 你的解法不应该依赖它们的实现.
*/
/**
* 将一个 128 位的原始数据转换为 f80 类型, 断言此浮点数是非负实数.
*/
static f80 hex2f80(u64 exp, u64 man) {
assert(exp < 0x7fff);
assert(man < (1ull << 63));
u128 raw = u128(exp << 1 | !!exp) << 63 | man;
f80 res;
memcpy(&res, &raw, F80_SIZE);
return res;
}
/**
* 在 bit level 均匀随机地生成一个 [非负] f80 [实数] (不是 NaN 也不是 Inf).
*/
static f80 getMessenger(size_t k) {
static const u64 MAX_MAN = (1ull << 63) - 1;
static const size_t SPECIAL_COUNT = 10;
static const f80 SPECIAL[] = {
hex2f80(0x0, 0x0), // 0
hex2f80(0x1, 0x0), // 最小的规格化数
hex2f80(0x3fff, 0x0), // 1.0
hex2f80(0x7ffe, MAX_MAN), // 最大的有限数
hex2f80(0x0, MAX_MAN), // 最大的非规格化数
hex2f80(0x0, 0x1), // 最小的非规格化数
hex2f80(0x0, 0x3f), // [property hidden]
hex2f80(0x0, MAX_MAN ^ 0x3f), // [property hidden]
hex2f80(0x7ffe, 0x3f), // [property hidden]
hex2f80(0x7ffe, MAX_MAN ^ 0x3f) // [property hidden]
};
if (k < SPECIAL_COUNT) return SPECIAL[k];
std::uniform_int_distribution<u64> edist(0, 0x7ffe),
mdist(0, MAX_MAN);
u64 exp = edist(rng), man = mdist(rng);
return hex2f80(exp, man);
}
static void getMessage(message_t message) {
for (size_t i = 0; i < MESSAGE_LEN; ++i) {
message[i] = static_cast<u8>(rng() % 256);
}
}
/**
* 运行第 k 组测试数据.
* 为了方便编码和调试, 我们没有引入乱序编解码, 也没有隔离加密者和解密者的程序状态.
* 但原则上, 你的解法应该支持乱序编解码, 并且不依赖于 encode 和 extract 之间的任何内部状态.
*/
static void runTest(size_t k) {
message_t message, decoded;
getMessage(message);
f80 messenger = getMessenger(k), origin = messenger;
encode(&messenger, message);
extract(&messenger, decoded);
Require(errorCheck(origin, interpret(&messenger)),
"interpret error on test %zu", k);
for (size_t i = 0; i < MESSAGE_LEN; ++i) {
Require(decoded[i] == message[i],
"extract error at byte %zu: %u != %u on test %zu",
i, decoded[i], message[i], k);
}
}
int main() {
for (size_t i = 0; i < 10000; ++i) {
runTest(i);
}
Success();
}
浙公网安备 33010602011771号