“垫底”逆袭！从一次错误中转换思路迎来破局

2021-06-16 14:18:07 浏览数 (1)

在第二期极客挑战赛的ARM64赛道中，“HOOCCOOH”同学以480字节的成绩摘得赛道冠军。值得一提的是，这位同学为了参加arm64赛道，几乎是现学现用aarch64 指令集，瞬间新技能 1

或许，极客挑战赛的乐趣之一就在于通过不断学习、不断精钻细研，满足对技术的无穷探索欲。

下面由他带来ARM64赛道的解题思路和心得分享，也欢迎小伙伴们在文末留言，分享自己的解题报告链接。（原赛题传送门：腾讯极客挑战赛丨全世界最最最小的程序，等你来battle！）

第一个错误方向

看到这个题目，立刻想到那个输出自己 MD5 的 gif ，碰撞啊！于是弄了一个碰撞器，撞出 128 对冲突数据串起来，然后把结果 128bit encode 进去让程序通过判断识别得到最终答案。由于目前个人电脑可以计算的方案需要两个 block 来做一次碰撞，通过枚举弄到 32 个前导零，程序仍需要存 (128-32)*128 byte = 12 KB 。巨大无比，当场垫底，于是立刻换思路。

老老实实算 MD5

首先按 wiki 抄一个 MD5 实现，千万不要抄比赛样例，那个把计算全部 unroll 了，体积上毫无优势。然后在基本代码上进行一些通用优化，大部分和 x86 思路差异不大，不细展开了。

  1. 手写汇编 手动构造 ELF 文件头拼接可执行文件，大家也懂
  2. ELF 头的 e_ident 末尾和 p_paddr 都可以随意塞数据，这里我塞进了一个常数 PI 。
  3. 最后一个块需要进行一些处理，可以在 ELF 头中设定页可写，然后在代码段直接写。
  4. MD5 内部状态直接预处理前 n-1 个块，塞进程序末尾；程序只需要求最后一个块即可。这里保证最后一个块不能超出 64 byte，最后控制得比较好，无需 pad 就满足了要求。
  5. MD5 计算用到一个 K[] 表，使用 sin 生成。x86(x87) 有 FSIN 指令可以直接用，但 aarch64 就没办法了，直接用个循环暴力求泰勒展开即可。我们需要 2^-32 的精度，搞不了奇技淫巧，循环次数要给够。记得之前需要把 x 缩放到 x % PI ，不然精度必挂；可使用循环减或除-取整-乘，指令数相同。
  6. 另有一个 S[] 表，发现每 16 个一组中为四个重复，可以去掉重复，然后稍微推导一下，通过 S[i >> 2 & 0b1100 | i & 0b11] 索引即可。
  7. 对于 i 的循环内的四种情况，我们不需要先比较跳转进去再跳转到结尾；因为我们都是设置 F 和 g ，于是可以：
    1. 啥都不管直接执行 case0
    2. 看看是否确实符合 case0 条件，是的话跳出
    3. 直接执行 case1 ，此时覆盖了 case0 的结果
    4. 看看是否符合 case1 条件，是的话跳出
    5. ...同理这样可以把比较 跳入 跳出变成只有比较 跳出。
  8. 由于上一条，我们可以复用不同轮中计算中间结果，比如 [0, 16) 轮的 ~B & D 和 [48, 64) 轮的 B | ~D 按位相反。反正 aarch64 寄存器多，而且可以位运算同时取反，这里可以省几条指令。

针对 Aarch64 指令集的优化

  1. 善用 orn, eon, bic ，别再额外 not 了。
  2. 访存指令 ldr/str 有同时操作两个寄存器的版本 ldp/stp，一条指令 ldp x0, x1, [x8], #16 即可读入整个 16 byte state 并且步进指针。
  3. 访存指令的自动步进非常好用，而且步进没必要是读写的大小。我们可以滥用一下来达到“访存，然后调整到我们后续需要的位置上去”的效果，避免额外的 adr。
  4. 在 2 中我们读进了两个 64bit 状态，但 MD5 计算都是 32bit 呀，怎么办？没关系，几乎所有计算指令都支持给一个操作数先移位再计算。我们寄存器值为 x0 = B << 32 | A, x1 = D << 32 | C
    • A-C, B-D 之间的运算，直接作为 64bit 运算即可，
    • 其他交错情况，可以将一个寄存器右移 32bit 再进行 64bit 运算，也只需要一条指令。
  5. 作为 4 的补充，一轮结束时轮换 ABCD 可用 extr 简化成三条指令。
  6. tbz/tbnz 可以代替几乎所有 cmp b
  7. 输出代码稍微复用了一下 4bit to ASCII 的逻辑，一个循环处理 4bit 而不是 8bit。不过赛后看了别人的思路后发现这里其实是可以通过碰撞成只有数字来减少更多代码的。
  8. 剩下还有些微优化，比如反着输出来少两次 write 传参，加法不考虑进位通过随机调整程序来撞出一个正确答案等等。

反正最后成果是 480 byte 啦，其实还有一定优化空间。

一些体会

本来咱是 x86_64 选手... 但由于前几名过猛，咱又太菜，最后止步 400 byte 就优化不动了。于是想想之前了解过一点 ARM ，就现学了 aarch64 指令集换赛道跑。不得不说其实 aarch64 定长指令大大降低了心智负担，只需要专心于优化指令数就好，不用纠结各个变长指令长度了！

说起来有点奇怪，似乎 aarch64 赛道相比另两个挺冷门的，提交次数也没那么疯狂（逃

总之非常感谢这次比赛提供的机会吧，也学到了挺多新技术和技巧，非常有趣！

腾讯极客挑战赛

0 人点赞