今天（2020年10月20日）是我的第二篇洛谷日报刊登的日子。不得不说这个等待队列是真的长，我五月初写的东西，都退役整整两个月了才排到我。上次我的那篇valarray一共只展示了一天，希望这次可以长一点。
下面进入正题。众所周知，九月末洛谷禁止了强制优化开启，让人不爽。并且作为一个相当卡常的OJ，就算开了O2也跑得很慢：我到现在还对曾经那些无论如何都卡不过去，只好交别人程序的题记忆犹新。并且我对于那些开了O2就一点用都没有的卡常技巧深恶痛绝，认为这应该是编译器的责任而非我们应该浪费精力的事。于是我打算创造一个工具，让我可以使用任何自己想要的编译选项来交题，从而轻松卡常。
为了达到这个目的，有两个办法：一个是在评测机上自己调用g++，想怎么编译怎么编译。但是洛谷是不允许你创建文件的；使用一系列管道以及memfd完成无需文件的编译操作虽然可行，但是非常繁琐。更重要的是，这样做的话编译时间也会被算进运行时间，与我们优化运行时间的目的相矛盾。另一个方法就是，把可执行文件直接写进代码里，省去编译的过程。这么做的话性能绝对可以和直接执行可执行文件相同了，但是如何在本机上创建一个能够在评测机上跑起来的可执行文件呢？相信各位曾经尝试过在不同版本的Linux之间传递二进制可执行文件的人都对此深有感触，兼容性可能不是很好。更何况洛谷的评测机和我的本机的差异，比之前尝试过传递二进制可执行文件的Linux系统之间的差异要大得多：之前我只尝试过各种Ubuntu，还没有多少成功的；然而洛谷用的是Debian buster（可以使用lsb_release -c | cut -f2验证这一点），虽然是Ubuntu的近亲，但我对Debian相当陌生。
这么做的可行性还有一个原因：Linux上C/C++的可执行文件是相当小的，一般都只有十几到二十几KB，远小于一般OJ的代码长度上限。但凡换成任何一个别的操作系统或者任何一个别的语言，哪怕是Rust，都因为需要“自带干粮”而非动态链接导致可执行文件大小过大，没有操作可行性。
所以我原计划使用Docker运行一个debian镜像，来完成本地创造兼容的可执行文件的操作，毕竟这么做比虚拟机轻量、快捷得多。结果到最后我发现在Ubuntu 20.04上编译的ELF居然可以直接在洛谷上跑起来？！！于是就省去了这个麻烦。但是我严重怀疑别的Linux版本是否也可以无缝兼容，也怀疑这个兼容性是否会随时间推移而改变。
另一个重要的问题是可执行文件如何编码在程序里。直接包在个字符串里肯定是不行的，就算使用C++11的Raw string literal也没法避免各种奇怪的问题；另一方面，我也希望输出的结果程序可以只使用古董版本的g++、最最朴素的C++98、不开任何编译选项来编译，来达到最佳的兼容效果（这很类似于JavaScript的Babel.js）。于是，我使用Base64把二进制文件编码为可见字符组成的字符串，可以直接使用在程序中。但是C++不自带Base64编解码的功能，我只好自己手动实现。讽刺性的是，这实际上是整个项目中最困难的一部分。
最后，最最关键的问题是，通过解码获得存有ELF文件的buffer之后，如何执行这个buffer呢？我也不知道为什么Linux允许看上去如此危险的功能，但事实就是这样。我们有memfd_create函数，可以在内存中创建一个文件，从而逃脱文件系统对于写入的限制！具体细节参考我搜到的这篇博客。总而言之，从内存中加载一段代码并执行是件很容易的事。
现在所有的技术障碍都被化解了，只剩下代码实现了。结果发现在舒适的现代C++世界里待惯了的我，完全就不知道C语言的指针该怎么用。我忘了一个char*在malloc之前不能使用，也忘了malloc的内存是必须要free的，更别说我从来就没知道过argv的最后是必须加上一个NULL指针的。结果导致我发现自己生成的代码仍然必须O2才能正常运行，让我以为是不是有什么超自然的阻碍横亘于O2和不开O2之间，以为一个开了O2的程序无论如何都不可能在没开O2的环境下运行，差点就放弃了。
终于调对了这些Bug，我兴高采烈地打算交个紫荆花之恋报仇雪恨。结果发现代码大小还是过大了，非常沮丧。幸亏我知道Linux下有一个实用程序可以大幅减小可执行文件的大小：strip！果然，strip执行完之后再转换，代码大小就刚刚好卡在50KB之内了。于是我就在本地使用clang++，开-Ofast -march=native编译，通过了这道之前我无论如何卡常，甚至加上火车头都没法通过的题目，并且用时只有时限的$\dfrac{2}{3}$。提交记录。
当然，这么做的潜力远不止于开点小小的优化开关。你可以选择g++或者clang++中较快的一个在本地编译，不管OJ上编译器的版本；可以自由使用C++20等新版本语法，不管OJ上的编译选项；可以使用被禁止的内联汇编；你甚至可以绕过链接限制，在代码中动态链接任何库，比如通过链接pthread线程库来开多线程；如果你得到了AC程序的二进制，也可以转成C++直接过题。
2021年2月8日 更新：使用RLE编码
base64输出的结果还是太长了，导致一个代码很短的紫荆花之恋，生成的cpp文件也有45KB之大，几乎达到了洛谷的代码大小上限。但是，可想而知，ELF文件中有很长的重复段，严重浪费了空间。所以我使用RLE（游程编码）将重复出现多于一次的字符用“重复的字符+重复次数”表示，就可以把生成的代码大小缩减$50\%$左右，普通大小的C++程序的输出代码长度只有5到6个KB。
说起来简单，实现中还是有一些细节的。这个“重复次数”该如何编码为字符串呢？肯定不能直接编码，因为base64已经使用了0-9的所有数字。所以我使用从37到46的ASCII字符来替换0-9，这些字符均为可打印且无需转义的字符，可直接写在字符串字面量里。但是这样会引入一个新的问题：base64中需要用到的+字符也在37到46这个区间之内，还是会引起歧义。所以我把base64中的+替换为了不在此区间内的>，这样就完美了。
新的提交记录，可见代码长度缩减了一半，而用时显然不会有明显的变化。
