最近过得颇为矛盾：一面毕业就业双倍焦虑；另一面无所事事，除了刷点整体来看不怎么难的lc题之外也不知道干什么好。总之就是在这样双倍的烦躁叠加起来的梦魇一般的日子里……总得自己找点乐子吧。

先放一下成果，就是下图这个二维码：至少在我平时使用的扫码软件里，它指向的是某个搜索网站；而它的镜像指向的则是某个视频网站。

写完之后我试着做了一个小的在线demo，想玩的话也可以试一试。虽然想不到能做什么……比如说把蓝绿两种收款码融在一起做一个透明的牌子之类的？（不是，谁会干这种事啊）

嘛嘛嘛，不过比较长的链接还是建议用native的版本，毕竟wasm可能稍微慢一点点…

大概是去年在湖里面划水时，我检索到了这样一篇文章：https://medium.com/altsoph/double-sided-qr-code-c946468f05d4

作者给出了一个level-1的二维码作为PoC，证明了这个问题是可解的，并提供了求解的方法——实际上就是我们这次实现的解法。

嘛，原作者似乎是因为版权之类的原因无法提供求解的代码，而自己实现的过程中又难免会迎头撞上二维码标准之类的一团破事，所以当时暂时把它搁置在了一边。

前几个月疫情期间简略读了一下相关内容，试着绕过原作者给出的麻烦解法偷，搞出来个巨大的二维码——当时想着做一做优化，结果得到了一个很糟心的结果。

大概的思路是说：二维码是分多个“校验组”的，每个校验组里面有若干个数据块和校验块。

只要我们取一个足够大的二维码，就能够使得我们要塞进去的数据都在第一组里面，并且它们在交织之后冲突的位置不是特别多。而那些没有数据的地方，只要都填满0——然后最后套一下masking，就成功了。

当然，这个做法还是有不少的问题的：一方面是，要冲突尽可能少，那么能填入的数据块数量实在少的可怜：我们往往会需要一个接近极限的巨大的二维码，实际上填进去的却得是尽可能压缩过的短的可怜的链接；而即使这样，其中的冲突也是不可控的，大多数时候要么有大到会被拒绝的错误量，要么会根据二维码解码器的实现（甚至摄像头角度）不同产生非常不稳定的识别结果…

嘛，唯一的好处就是程序真的很好写：用现成的工具指定各种参数生成一堆二维码，然后按照分组的方式组合一下，如果不行就把其中冲突的地方重新roll一下选谁……

总之，最近一周多因为暂时没有什么读文献的心情，所以好好读了读二维码相关的规范…四舍五入把其中的几个比较有趣的部分自己做了一遍实现。然后突然发现之前觉得原文里难以实现的部分反而好实现了。

总之可以看原文最下面的参考文献里面的qr_standard。

首先的话当然要生成的就是定位块，也就是我们在二维码上看到的一个个或大或小的“回”字形。当然，这也是最没有自由度的一处：我们只要根据二维码的大小在对应位置画上对应图案就好了——而且它确实天然地是关于主对角线对称的。

然后我们再看看所谓的“版本信息”(Version Information)——实际上它只是表明二维码的“版本”，也就是大小。将版本号用六位整数表示，通过BCH编码加入12位校验位，然后把这18位整数分别放在两块预留的位置里。非常令人庆幸的是：这两块位置以及填充的顺序是天然对称的，因此我们也可以不用考虑这里怎么构造对称了。

此外，二维码里还包含两块“格式信息”(Format Information)，它们指出了二维码的纠错等级和使用的masking，把这些信息编码到5比特再加入10比特的校验，跟给定序列做异或，然后再放置到对应的位置上：一块围绕着左上角的定位块，另外两块分别挨着左下和右上的定位块。

嘛，这里面的比特位在镜像之后，要么对应到格式信息中的其它比特，要么对应到固定是1的比特上——所以我们考虑这段信息的错误是否超过BCH编码的纠错上限时，可以不用考虑其它信息。

理论上来说，10比特的校验可以纠正四比特错误——而且我们可以试图把这些错误分散到正反两侧，所以相对还是有一些余裕的。因此，我们不妨更“偷懒”一点，只选取对称的masking当中使得这里错误最少的那个。这样一来，负载信息的计算过程可以完全不考虑masking的影响，只需要在最后应用选取的masking即可。

而因为对于给定的level也只有八种掩码可以用（如果只要对称的就是五种），BCH本身也没多难计算：尝试的代价是如此的小，以至于我都懒得把它存成一个4x8矩阵待查了，就算每次现算都不会怎么影响运行速度。

我们首先把我们要写入二维码的消息编码成对应的二进制流。

啊，当然，二维码本身是一个复杂的多功能的格式——我们可以用ECI指定字符集、可以用混合的编码方式——不过既然主体是要试着编码链接，我们可以忽略掉那些复杂的格式，只考虑8-bit和alphanumeric两种格式。（当然，如果需要改代码支持其它类型输入的话，我的建议是直接用nayuki-qr-code-generator或者类似的东西来编码）

然后的话，如果手动编码url链接，实际有一种或许可以偷的方式…比如说https://b23.tv/av170001——前面协议部分和域名部分都可以写成大写，但是路径部分改成大写之后没办法访问——那么我们或许可以试着把其中的小写字符做一下urlencode，从而使得url里不包含小写字母，从而用alphanumeric进行编码。如果是这种小写字母很少（毕竟只有两个）的链接的话，也许可以得到比8bit更短的结果。

嘛嘛嘛，不过编码又不是重点，就姑且假设假定假装我们做完了数据部分的编码，并把该做的padding都做好了：四比特0的终结符，再填充0到字节边界（虽然我为了保险多加了一字节，但是理论上是用不到的）。剩下的数据原则上是00010001和11101100两种东西填满，但是实际上（至少在我见到的实现里）是无所谓的。

然后，我们再考虑校验位部分，正常来说的话是通过Reed-Solomon码计算出来的。然后的话——虽然说是有一个相对麻烦的多项式模——但是说到底也不过是一个可以直接当成各分量独立施加影响的东西。

如果准备写着玩的话，嘛，提示是最好每一步都对着文档里的例子比较一下输入输出结果，别最后发现字节序反了之类的，改起来再重新测试超~麻烦的。

如果准备直接偷的话——实际上可以直接用现成的Reed-Solomon库计算数据向量只有第i个分量为1时的校验向量——然后得到一张（数据长度 x 校验位长度）的二进制表格。表格乘上数据向量（当然是模2乘），实际上就是校验向量。

总而言之，我们到这里得到了原文中的提到的那些等式——正着的反着的放到一起，把已经填好的比特去掉——剩下的就是单纯的线性方程组求解了。

嘛，理论上来说这玩意也没那么好解：如果方程组不能成立，那么我们最好是适当地挑选让哪些方程成立——毕竟要让正反都不超过纠错能力嘛…

但是我不会写（自豪脸）！

或者说这个问题或许能解决——但是看起来就麻烦的要死，更不用说好像也不太能编出来什么复杂的测试样例来检查了——所以就不管了！

直接硬消元法求解方程组，然后就可以得到一个二维码——最后我们做一次RS解码（RS纠错解码是麻烦的，所以直接第三方库了。自己写的话或许可以看看Berlekamp–Welch之类的算法？），看看是不是每个校验组里面错误的码数量都不超过纠错能力。很奇妙的是当接近纠错极限时，有的扫码设备会错误工作（其实我怀疑是被现实世界的误差顶到达到了极限，这一侧二维码被拒绝了之后自动就用了另一侧的），所以在条件允许的情况下我们可以加一个“保护间隔”来避免出现类似的情况。

嘛，不过稍微进行一个脑袋的拍：同侧（指“正向”的或者“镜像”的）的方程之间甚至没有同样的变量；不同侧的方程看起来也挺互相无关的。自变量个数（没有填写的比特数）是两边都没有被已知的数据位占据的比特数，而方程数等于校验位数量乘2…当校验位相对于数据容量比较少的时候，自变量个数可以远多于方程数，那么我们一般可以得到一个几乎不用丢掉几个方程的解答。甚至需要给不少自变量赋随机值（）

所以在常见的应用场景下，我们即使到处都在大手大脚地做奇怪的“不妨约束”，也还暂时犯不上得到一个之前那样的巨大二维码（

在正规的二维码生成过程中，实际上我们要到最后才能知道使用哪一组掩码——在计算好负载之后去评估哪一种掩码使得二维码的效果尽可能好。

但是不幸的是，我们在3.2中确定了要使用的masking——所以我们实际上没什么剩下的自由度，只要应用选定的掩码，把负载中的某些位置反转就可以了。

实际上最开始写的时候根本没考虑到过弄一个在线demo出来——但是摸鱼时发现了自己磁盘里还有很久很久之前下载的emsdk，突然觉得：啊，这个好玩，想玩！

然而我一开始写代码的时候，重点突出一个随心所欲，哪怕看现在的代码也能看出些线索：最早时草草地写了个imshow，然后为了方便拷出去当一个函数，然后又顺手改成了硬编码路径的imwrite，最后把硬编码的路径定义成了常量装出一副好改的样子；此外还有调试时塞进去的一大堆有用或者没用的cout……然后包管理器告诉我：啊，wasm的opencv装不上。

嘛，手动编译我也不知道能不能成，但是肯定很麻烦。所以不如直接丢出去一个完全没优化的巨大svg——反正又不走网络请求。然后实现下载功能时又火速从SO上找了一段代码，用来把svg渲染到canvas再导出到png…至于输出进度，总之在网页端的话就随便塞两个进度条呗——然后就是这个样子了…

哦对了值得一提的是——如果不想把顺序执行的程序改成循环驱动的程序，同时还希望在程序运行过程中能更新页面（比如进度条），那么——编译时启用-sASYNCIFY参数，运行时调用emscripten_sleep这个函数可以让页面本身去处理一下事件…虽说好像说会有不太多的性能损失？（比如说SDL好像就不需要把程序改成基于main_loop的）

该说是惊喜嘛，跑的比想象中的还是要快不少的。

不过这玩意环境真是太难配了（大雾）