mirror of
https://github.com/Mabbs/mabbs.github.io
synced 2025-09-05 22:26:03 +08:00
3dd82ed54c
- /_data/links.csv - /_data/proxylist.yml - /_tools/envs_post-receive - /_tools/serv00_post-receive - /_tools/ai-summary.js - /_posts/2025-09-01-quine.md
95 lines
18 KiB
Markdown
95 lines
18 KiB
Markdown
---
|
||
layout: post
|
||
title: 关于ZIP Quine与自产生程序的探索
|
||
tags: [压缩包, Quine, 自产生程序, Quine Relay]
|
||
---
|
||
|
||
描述自己的代码……是一种什么样的感觉？<!--more-->
|
||
|
||
# 起因
|
||
前段时间我在折腾[博客部署](/2025/08/10/tilde.html#%E4%BD%BF%E7%94%A8git-hooks%E8%87%AA%E5%8A%A8%E9%83%A8%E7%BD%B2%E5%8D%9A%E5%AE%A2)的时候，回顾起了好久以前写的[部署脚本](/deploy.sh)。对于全站打包的这个步骤，本来我打算利用这个压缩包结合[Service Worker做离线浏览](/2025/08/01/sw-proxy.html)，但因为没有合适的方案所以放弃了。而现在对于这个压缩包，我又有了一个特别的想法。事实上在这个下载全站的压缩包中，里面的内容和实际的网站并不完全相同，因为在这个压缩包里缺少了压缩包本身。所以把这个压缩包解压之后直接当作网站打开，会发现下载压缩包的链接是无效的，除非在解压之后把压缩包移动到网站里才行……
|
||
于是我就在想有没有一种可能可以让压缩包解压之后里面又包含了这个压缩包本身？似乎是个不太可能的事情，但我以前听过类似的东西，也许并非不可能？所以这次就来探索一下吧。
|
||
|
||
# 自包含压缩包的探索
|
||
在很久之前，我见到过一个很知名的自包含压缩包（又称为ZIP Quine），叫做[droste.zip](https://alf.nu/s/droste.zip)，是由Erling Ellingsen[在2005年制作](https://web.archive.org/web/20090106171423/http://tykje.com/code/useless/zip-file-quine)出来的。当时我只知道它很神奇，原理什么的并不清楚，另外在网上也基本上找不到类似的压缩包。现在再回看时发现[介绍](https://alf.nu/ZipQuine)里包含了一些相关的链接，甚至还有一篇能自己制作类似压缩包的论文，所以接下来就可以看一下这些链接来理解这种压缩包是如何制作的了。
|
||
关于原理方面，先看[Will Greenberg](https://github.com/wgreenberg)制作的一个[示例](https://wgreenberg.github.io/quine.zip/)，在这里面有一个谜题，使用“print M”（原样输出接下来的M行输入内容）和“repeat M N”（从倒数第N行的输出内容开始，重复M行）这两个指令让最终执行的结果和输入的指令完全相同。这正是对DEFLATE压缩算法所使用的LZ77编码的一种简化模拟，也就是说只要解决了这个问题，就可以让压缩包在解压时原样输出自己了。
|
||
这个问题看起来还挺复杂，不过在仓库的[Issues](https://github.com/wgreenberg/quine.zip/issues/1)就有人给出了几种解法（当然，这个题目解法不唯一），所以在理论上应该是可行的，那么接下来就需要研究压缩文件的格式来实现它了。
|
||
## 实现ZIP Quine的探索
|
||
在[Russ Cox](https://swtch.com/~rsc/)写的[Zip Files All The Way Down](https://research.swtch.com/zip)文章中，同样说明了这个原理，而且给出了一个方案，让上述这两个命令除了能够对命令本身的重复以外，还可以添加一些额外数据，这样才能做到构建一个压缩包文件。按照文章的描述，如果用之前谜题的规则来说，我们设头和尾的内容都是“print 0”，那么Cox给出的方案如下：
|
||
```
|
||
print 0
|
||
print 2
|
||
print 0
|
||
print 2
|
||
repeat 2 2
|
||
print 1
|
||
repeat 2 2
|
||
print 1
|
||
print 1
|
||
print 4
|
||
repeat 2 2
|
||
print 1
|
||
print 1
|
||
print 4
|
||
repeat 4 4
|
||
print 4
|
||
repeat 4 4
|
||
print 4
|
||
repeat 4 4
|
||
print 4
|
||
repeat 4 4
|
||
print 4
|
||
repeat 4 4
|
||
print 0
|
||
print 0
|
||
print 2
|
||
repeat 4 4
|
||
print 0
|
||
print 0
|
||
print 2
|
||
repeat 2 2
|
||
print 0
|
||
repeat 2 2
|
||
print 0
|
||
```
|
||
我们把这些指令粘贴到[quine.zip](https://wgreenberg.github.io/quine.zip/)这个谜题中，就会发现输出和输入完全相同，以此就能验证Cox方案的正确性。除此之外作者还给出了生成的源代码：[rgzip.go](http://swtch.com/rgzip.go)，只是代码里面到处都是用来构建压缩包的十六进制数字，完全看不懂😂。
|
||
另外这个方案是针对使用基于LZ77与哈夫曼编码的DEFLATE压缩算法，所以格式不重要。因此无论是ZIP，还是GZIP，以及TGZ（GZIP压缩后的TAR），其实都是一样的，因为他们都使用的是DEFLATE压缩算法。顺便一提，[Matthew Barber](https://github.com/honno)写了一篇很棒的[文章](https://github.com/honno/gzip-quine)，通过动画演示并详细讲解了如何实现一个简单的GZIP版ZIP Quine，很值得一看。
|
||
还有一点，普通的TAR文件能否实现类似功能呢？从原理来说估计不行，因为TAR文件本身并没有压缩，也不包含指令，就单纯是一堆文件和元数据的拼接，所以就做不到自包含了。
|
||
这么来看既然TGZ可以，那是不是在我博客网站的压缩包里放一份和自己一模一样的压缩包是可行的？很遗憾按照这个方法来看是做不到的，由于压缩格式和编码的限制，这个方案在实际实现时发现操作码需要是5个字节，最后发现最多只有类似`repeat 64 64`这样的指令能够满足要求，因此头尾区最多只能放64-5=59个字节的数据，也就刚刚好能容纳压缩格式需要的内容，几乎没法塞更多东西进去……显然，这些限制导致这种方式对我来说意义就不大了，何况作者的代码我也看不懂……而且还要考虑压缩包还存在校验用的CRC32，需要找满足整个压缩包的CRC32正好在压缩包中的“不动点”。虽然从CRC32的原理来说应该有办法做到通过数学方式解决，但这篇文章的作者因为解决了自包含的问题之后累了，因此放弃继续研究，选择直接暴力破解，毕竟CRC32只有32位，估计思考的时间都要比爆破的时间长吧😂。但如果是这样，即使有方案能存下我博客的数据，也不能在每次网站构建的时候都制作一次了……
|
||
虽然Russ Cox写的文章看起来做不到包含更多内容了，但Erling Ellingsen制作的droste.zip却包含了一张图片，说明并不是没办法加入更多数据，只是没有找到正确的方法。在2024年[Ruben Van Mello](https://github.com/ruvmello)写了一篇论文[A Generator for Recursive Zip Files](https://www.mdpi.com/2076-3417/14/21/9797)，在这篇论文里他不仅解决了包含的额外数据过少的问题，还编写了一个通用工具，能让普通人也能生成这样的压缩包，而且他还创新性的做了一种像衔尾蛇一样的双层嵌套循环压缩包，非常的有意思，所以接下来我打算试试他的方案。
|
||
在这篇论文中，里面简述了之前Russ Cox写的内容，也提到了59字节的限制，于是作者对原有的结构进行了一些改动，让操作码可以超出5字节的限制，具体可以看论文的表6，从而解决了只能包含59字节额外数据的限制。但由于DEFLATE压缩格式本身的约束（16位存储块长度以及32KiB回溯窗口），即使能够添加文件，最多也只能额外容纳32763字节的数据（其中包括压缩包所需的文件头）……显然这点空间完全存不下我的博客😭，看来我只能打消这个想法了。但既然都研究了半天，也不一定要存我的博客嘛，可以看看还有没有别的东西可以存？在这之前先继续阅读论文，看完再说吧。
|
||
## 制作一个嵌套循环的ZIP Quine
|
||
在实现了常规的ZIP Quine之后，接下来就是作者的创新点了（如果光是解决存储限制这点创新点估计还不够发论文吧😂）。作者在接下来制作了一种循环压缩文件，在压缩包内包含文件A和压缩包A，而压缩包A中则包含文件B和最初的压缩包，从而形成一个循环递归的结构。看论文的描述所说如果把外层的压缩包和内层的压缩包的开头和结尾按照一定的规则交替混合，就可以看作是一个整体，然后按照之前做ZIP Quine那样处理就可以……具体实现的细节得看论文的表10。只不过既然是把两个压缩包看作一个整体的话，按照上面的限制，自然每个压缩包能容纳的数据量就更小了，每个最多只能容纳16376字节的数据……
|
||
另外既然这里面有两个压缩包，那么每个压缩包还有自己的CRC32校验和，理论上如果要爆破的话计算难度得是原来的平方，这样难度就太大了。不过作者发现如果把数据的CRC32值取反（即与“0xFFFFFFFF”取异或）然后和原始数据拼到一起，整个数据的CRC32校验和就会被重置为一个固定的值“0xFFFFFFFF”，看起来挺有意思，正常的哈希算法可没有这种特性。因此原本计算难度很大的爆破计算现在就可以和之前一样了……话说为什么不让两层的CRC32都这样计算（包括之前单层的ZIP Quine）？这样就不需要爆破了……貌似是因为在普通的ZIP Quine中满足条件的CRC32需要出现两次，所以不能用这个方案吧？
|
||
现在所有的理论都足够了，我需要挑一个文件来做这样嵌套循环的ZIP Quine，既然博客的大小不可以……要不然我就用我写过的第一个大项目——[Mabbs](https://github.com/Mabbs/Mabbs.Project)吧，这个项目的主程序是22KiB，看起来似乎超出了嵌套循环ZIP Quine的限制？其实没有，它的限制指的是压缩后的大小，我这个程序压缩之后是8KiB左右，所以完全没问题。
|
||
接下来就该使用论文中提到的生成工具：[zip-quine-generator](https://github.com/ruvmello/zip-quine-generator)，这是一个Kotlin编写的程序，从发布中可以下载预构建的程序，接下来只要按照README中的描述使用“`--loop`”参数就可以用这个程序创建嵌套循环的ZIP Quine了。不过它原本的代码不能修改里面生成的压缩包的名字，另外[压缩后的文件属性是隐藏文件](https://github.com/ruvmello/zip-quine-generator/blob/3b8cf977e7a93bb956ad966d5e3b4d503f410529/src/main/kotlin/zip/ZIPArchiver.kt#L845)，还有[生成的压缩包中文件的创建时间总是当前时间](https://github.com/ruvmello/zip-quine-generator/blob/3b8cf977e7a93bb956ad966d5e3b4d503f410529/src/main/kotlin/zip/ZIPArchiver.kt#L29)，以及[给文件内填充额外数据的代码里面填的是作者的声明](https://github.com/ruvmello/zip-quine-generator/blob/3b8cf977e7a93bb956ad966d5e3b4d503f410529/src/main/kotlin/zip/ZIPArchiver.kt#L30)，表示文件是由他论文的所写的生成器生成的……这些情况让我感觉有点不爽，还是希望这些部分能自定义一下，所以我就小改了一下他的代码。顺便一说，Kotlin编译起来还挺简单，直接一句`kotlinc src/main/kotlin -include-runtime -d output.jar`就可以了，也不需要折腾Maven之类乱七八糟的东西。最终我修改并编译完程序之后就把文件丢到服务器上开始给我爆破CRC32了，花了10个小时就算出来了，倒是比想象中快😂。
|
||
最终我给我的[Mabbs](https://github.com/Mabbs/Mabbs.Project)项目创建了[Infinite Mabbs](https://github.com/Mabbs/Mabbs.Project/releases/tag/Final-version)这个发布，生成的文件也可以在[这里](/assets/Mabbs.zip)下载，这也算是不枉我研究半天这个论文了😆。
|
||
|
||
# 自产生程序的探索
|
||
说起来自包含压缩包为什么叫做ZIP Quine？其中的Quine是什么意思呢？其实这是一位美国哲学家的名字，他提出了“自指”的理论概念，所以为了纪念他，有类似概念的东西就被称作Quine，具体为什么也可以去看[维基百科](https://en.wikipedia.org/wiki/Quine_(computing)#Name)的说明。现在提到Quine一般代表的就是自产生程序，而自包含压缩包因为实现的原理和自产生程序的原理差不多，所以叫做ZIP Quine。因此接下来我打算探索一下自产生程序，更深入地了解Quine。
|
||
## 实现Quine的探索
|
||
那么什么是自产生程序？简单来说就是程序的源代码和程序的输出完全相同的程序，而且通常来说不允许通过读取/输入源代码的方式实现。按照一般的想法，让程序输出自身就需要输出中有全部代码，整个代码就会变长，而更长的代码就要输出更多，然后代码就会越来越长……所以这么想来似乎成了个死胡同。但其实这种程序实现起来并不复杂，想想ZIP Quine的实现，关键在于指令还需要以数据的形式表现，并且能被引用，这样输出的时候就会连着指令一起输出了。比如用Python的Quine举例：
|
||
```python
|
||
c = 'c = %r; print(c %% c)'; print(c % c)
|
||
```
|
||
这里的变量中就以数据的形式存储了程序的代码，而在输出的时候除了变量内的代码，又通过引用的方式又把变量的内容放回到赋值的地方，所以它的输出就和原本的代码一样了。
|
||
其实Quine的实现思路都差不多是这样，可以在[Rosetta Code](https://rosettacode.org/)中找到[各种语言实现的Quine](https://rosettacode.org/wiki/Quine)，在这其中能够发现大多数高级语言的写法都是类似的，除了一些低级语言以及esolang……这些我也看不懂😂，主要是有些语言没有变量的概念，不知道是怎么区分代码和数据……除了那个网站，在[这里](https://esolangs.org/wiki/List_of_quines)还能找到更多由esolang编写的Quine，可以看出来基本上很难看懂，其中最令人望而生畏的还得是[用Malbolge写的Quine](https://lutter.cc/malbolge/quine.html)，这个代码看起来不仅很长，而且像乱码一样。至于什么是Malbolge？这就是Malbolge程序：
|
||
```
|
||
D'<;_98=6Z43Wxx/.R?Pa
|
||
```
|
||
代码就像加了密似的，顺便一说这个执行结果是“Mayx”，关于Malbolge的具体细节可以看它的[规范](http://www.lscheffer.com/malbolge_spec.html)，另外虽然这个语言写起来很复杂，但还是有人能用它编出程序的，甚至还有人用[Malbolge Unshackled](https://esolangs.org/wiki/Malbolge_Unshackled)（Malbolge不限内存的变种）写过[Lisp解释器](https://github.com/iczelia/malbolge-lisp)，实在是恐怖如斯😨。
|
||
## 只能Quine的语言
|
||
其实想要做出Quine，还有一种更加无聊的方案，那就是设计一种只能Quine的语言🤣。根据Quine的定义，代码输出的结果就是它本身……所以我们可以把任何内容都看作代码，然后这种语言的行为就是输出所有代码……听起来是不是有点无聊？但是想想看如果把Linux中的cat命令当作解释器，就可以实现这种语言了，比如：
|
||
```
|
||
#!/bin/cat
|
||
Hello, world!
|
||
```
|
||
作为脚本执行的结果就是原样输出这段内容，不过把内容当作代码算不算作弊呢……如果看作是cat的输入显然是作弊，但如果是当作源代码的话应该就不算了吧😋……但这就不是能写出逻辑的语言了。所以说Quine的趣味并不在“能不能实现”，而在于如何在限制条件下实现。正是因为大多数语言不会直接“自我输出”，才会觉得那些精巧的Quine程序如此有意思。
|
||
## Quine Relay的探索
|
||
还有一个更加复杂的Quine变种是“Quine接力”（Quine Relay），即一个程序输出另一个程序的源代码，另一个程序又输出下一个程序的源代码，最后回到原始程序，就和之前所说的的嵌套循环ZIP Quine有点类似。最著名的例子是[Yusuke Endoh](https://github.com/mame)（这位还是[IOCCC](https://www.ioccc.org/)的冠军之一）创建的[quine-relay](https://github.com/mame/quine-relay)项目，它包含了128种编程语言的循环。
|
||
这种程序写起来会更复杂一些，不过原理都差不多，通常除了当前运行的部分是可执行代码外，其他的代码都需要以额外包含的数据形式（如字符串）存储在变量中。如果想自己做个类似简单的Quine Relay，除了去看[维基百科](https://en.wikipedia.org/wiki/Quine_(computing)#Ouroboros_programs)之外，前段时间我还看到过一个不错的[文章](https://blog.mistivia.com/posts/2024-09-21-quine/)，里面就讲了如何用“笨办法”编写Quine和Quine Relay，通过把变量中的内容编码为16进制来避免不同语言可能存在的特殊字符转译问题，思路不错，对于理解如何编写这类程序的问题很有帮助。当然这只是个**简单**的方案，仅适用于一些常规的编程语言，像上面那个[quine-relay](https://github.com/mame/quine-relay)项目中甚至还包含Brainfuck之类的esolang，这种估计得要想办法让相对高级一些的语言通过“生成”的方式得到输出下一种代码的代码，而不是简单的赋值了，所以只靠这点知识想去完全理解大佬的作品还是想多了😆。
|
||
|
||
# 感想
|
||
虽然这次探索最终没能完成让包含博客所有内容的压缩包自包含，但是在探索的过程中我还是收获了不少，尤其是Ruben Van Mello制作的ZIP Quine生成工具，实在是太棒了。很久以前我见到droste.zip这个压缩包的时候，就想整一个属于自己的ZIP Quine，现在我不仅用那个生成工具做了一个，还是对我来说很有意义的第一个项目——Mabbs，而且更关键的还是生成的是比普通的ZIP Quine更高级的嵌套循环ZIP Quine，也算是圆了小时候的心愿了。
|
||
另外在探索自产生程序的时候，也发现了一些很有意思的网站，比如[Rosetta Code](https://rosettacode.org/)以及[Esolang wiki](https://esolangs.org/) ~~（虽然这个网站里被好多小学生写了一堆无聊的东西😂）~~ ，里面有不少有趣的东西，也算是让我大开眼界了。
|
||
所以有的时候探索不一定要完成目标，在这个过程中也会收获到很多不错的东西吧😊。 |