summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authormayx <mayx@outlook.com>2026-09-30 16:01:13 +0000
committermayx <mayx@outlook.com>2026-09-30 16:01:13 +0000
commit303f5df01c48b27bb54b78054fb2739fbc18b6b0 (patch)
tree05fd3909b72838c6127135250601b848dec07181
parent932e310f9d003b2f8bf9c7efd39d112c9dc50d0e (diff)
Update 5 files
- /_data/other_repo_list.csv - /_data/links.csv - /_posts/2026-10-01-quine.md - /_tools/blogquine.py - /assets/js/pjax.js
Diffstat
-rw-r--r--_data/links.csv1
-rw-r--r--_data/other_repo_list.csv39
-rw-r--r--_posts/2026-10-01-quine.md1352
-rw-r--r--_tools/blogquine.py53
-rw-r--r--assets/js/pjax.js2
5 files changed, 1372 insertions, 75 deletions
diff --git a/_data/links.csv b/_data/links.csv
index d75e9e4..915cf59 100644
--- a/_data/links.csv
+++ b/_data/links.csv
@@ -26,3 +26,4 @@ RavelloH's Blog,https://ravelloh.com,https://ravelloh.com/feed.xml,Beginning of
EXYONE@BLOG:~$,https://exyon.ee,https://exyon.ee/feed.xml,一隅藏天地，流水遇知音。
小景,https://jingyuan-zheng.github.io/zh/,https://jingyuan-zheng.github.io/zh/index.xml,随心分享有趣的技术、开源项目与生活记录。
热汤茶馆,https://blog.hotsouprealm.top/,https://blog.hotsouprealm.top/atom.xml,茶凉了可以续，话断了可以接，这里是hahahotsoup的茶馆。
+FGHRSH 日记簿,https://www.fghrsh.net/,https://www.fghrsh.net/feed.php,把喜欢的东西都记下来···
diff --git a/_data/other_repo_list.csv b/_data/other_repo_list.csv
index 9c1b097..505db57 100644
--- a/_data/other_repo_list.csv
+++ b/_data/other_repo_list.csv
@@ -4,6 +4,7 @@ http://git.dkforestseeaaq2dqz2uflmlsybvnq2irzn4ygyvu53oazyorednviid.onion/mayx/b
http://giteabolfdejtdzblkooalqei6jr67imiugmhtsh6ocw4hlj5a4q.b32.i2p/mayx/blog
https://gitlab.lain.la/mayx/mayx.pages.lain.la
https://gitplac.si/mayx/mayx.gitpage.si
+https://git.32bit.cafe/mayx/blog
https://gitnet.fr/mayx/blog
https://opencommit.eu/mayx/blog
https://forge.fedoraproject.org/mabbs/blog
@@ -31,16 +32,13 @@ http://116.236.50.103:8789/mayx/blog
https://repo.gusdya.net/mayx/blog
https://gitea.synapsetec.cn/mayx/blog
http://gitea.yunshanghub.com:8081/mayx/blog
-http://113.177.27.200:2033/mayx/blog
http://152.69.204.151:3000/mayx/blog
http://187.216.152.151:9999/mayx/blog
http://116.63.173.179:8001/mayx/blog
https://git.furcom.org/mayx/blog
https://git.karma-riuk.com/mayx/blog
-https://git.7o9o.net/mayx/blog
https://git.gupaoedu.cn/mayx/blog
https://git.7milch.com/mayx/blog
-https://gitea.sciotech.cn/mayx/blog
https://gitea.micro-stack.org/mayx/blog
http://106.54.211.95:3000/mayx/blog
http://172.172.102.93:3000/mayx/blog
@@ -64,11 +62,9 @@ http://8.130.135.159:3000/mayx/blog
https://git.dshkabatur.ru/mayx/blog
http://47.103.78.70:3000/mayx/blog
http://194.5.152.156:3000/mayx/blog
-http://58.65.162.118:3000/mayx/blog
https://git.arkon.solutions/mayx/blog
https://gitea.yimoyuyan.cn/mayx/blog
http://221.203.14.217:3000/mayx/blog
-https://dev.kiramtech.com/mayx/blog
https://git.f4e.lol/mayx/blog
http://72.61.229.93:4000/mayx/blog
http://39.101.74.135:5000/mayx/blog_cn
@@ -80,20 +76,16 @@ http://45.55.138.82:3000/mayx/blog_cn
http://118.24.129.148:3000/mayx/blog_cn
http://120.48.141.82:3000/mayx/blog_cn
http://175.27.229.211:3000/mayx/blog_cn
-https://git.yidaimingjvn.xyz/mayx/blog_cn
http://39.105.67.143:3000/mayx/blog_cn
http://82.156.89.21:3000/mayx/blog_cn
http://xujiesoft.vicp.net:3000/mayx/blog_cn
-https://git.mingliqiye.com/mayx/blog_cn
http://58.213.60.6:19000/mayx/blog_cn
http://47.92.113.131:3000/mayx/blog
http://gyc.myds.me:4000/mayx/blog
https://git.graveyard.sh/mayx/blog
https://gitea.jnyuxia.com/mayx/blog
-https://gitea.mynas-lechner.de/mayx/blog
https://gitlab.iplusus.com/mayx/blog
https://git.miasma-os.com/mayx/blog
-https://git.zakum.cn/mayx/blog
http://47.109.103.110:9000/mayx/blog_cn
http://47.104.241.192:19999/mayx/blog_cn
http://47.98.148.146:1026/mayx/blog_cn
@@ -106,12 +98,9 @@ http://47.106.222.181:20511/mayx/blog_cn
http://118.24.161.24:3000/mayx/blog_cn
http://36.138.125.206:3000/mayx/blog_cn
https://git.crystalyx.net/mayx/blog
-https://gitea.grxe.io/mayx/blog
-https://gitea.accept.dev.dbf.nl/mayx/blog
https://barhoum-lab.fr/mayx/blog
http://gitea.snailtrack.cn/mayx/blog_cn
https://code.draussenfunker.de/mayx/blog_cn
-https://git.dinsor.co.th/mayx/blog
http://www.bkandssp.cn:30/mayx/blog
http://gitea.ydxtool.com/mayx/blog
https://gitea.malxte.de/mayx/blog
@@ -129,7 +118,6 @@ https://git.libregaming.org/mayx/blog
https://git.kaki87.net/mayx/blog
https://forgejo.vanten-s.com/mayx/blog
http://124.71.169.183:3000/mayx/blog
-https://git.msoucy.me/mayx/blog
http://140.120.108.238:49308/mayx/blog
http://git.chilidoginteractive.com:3000/mayx/blog_cn
https://git.panda-number.one/mayx/blog
@@ -138,7 +126,6 @@ https://gitea.keymantek.com:777/mayx/blog
https://git.tirtapakuan.co.id/mayx/blog
http://tian-you.top:7020/mayx/blog
http://34.17.182.140/mayx-gogs/blog
-http://gitea.mikarsoft.com/mayx/blog
https://mcgit.place/mayx/blog
https://forgejo.rekallservices.com/mayx/blog
http://git.instal.org.cn/mayx/blog
@@ -149,7 +136,6 @@ https://git.netzbyte.com/mayx/blog
https://ataymakhzan.com/mayx/blog
https://repo.qruize.com/mayx/blog
https://git.xneon.org/mayx/blog
-https://git.lamby.gay/mayx/blog
https://lab.dutt.ch/mayx/blog
https://gitea.dabit.synology.me/mayx/blog
https://git.joinplu.me/mayx/blog
@@ -170,12 +156,10 @@ https://devcraft-dot.tech/mayx/blog
https://a-t-g.ru/mayx/blog
http://wangbeibei.xyz:6002/mayx/blog
http://8.141.82.163:20000/mayx/blog_cn
-http://81.70.30.91:3000/mayx/blog_cn
http://yidaima.cn:6008/mayx/blog_cn
http://8.148.31.14:3000/mayx/blog_cn
http://58.17.14.95:8001/mayx/blog_cn
http://39.99.175.172:8000/mayx/blog_cn
-https://gitea.detr.top/mayx/blog_cn
http://175.178.193.35:3000/mayx/blog_cn
http://gitea.jb1000.com:88/mayx/blog_cn
http://www.22ai.vip/mayx/blog_cn
@@ -185,19 +169,12 @@ http://62.234.20.54:3000/mayx/blog_cn
https://gitea.4gunn.cn:52443/mayx/blog_cn
http://jdunlap.com/mayx/blog
https://git.silica.codes/mayx/blog
-https://www.vitelgrid.app/mayx/blog
https://gitruhub.ru/mayx/blog
-https://git.techworkshop42.ru/mayx/blog
-http://speedyfox.app/mayx/blog
https://mjjtop.com/mayx/blog
https://forgejo.wanderingmonster.dev/mayx/blog
-https://git.edavmig.ru/mayx/blog
https://gitea.ns5001k.sigma2.no/mayx/blog
https://git.hemangvyas.com/mayx/blog
https://gitav.ru/mayx/blog
-https://git.sakuzyo.net/mayx/blog
-http://www.365rise.top/mayx/blog
-https://git.ifuntanhub.dev/mayx/blog
https://git.aptcloud.ru/mayx/blog
https://gitlab.dev.genai-team.ru/mayx/blog
https://git.umervtilte.lol/mayx/blog
@@ -212,17 +189,23 @@ http://81.69.57.215:3000/mayx/blog_cn
https://git.dglyoo.com/mayx/blog_cn
http://c8202.top:3000/mayx/blog_cn
http://nojava.fun/mayx/blog_cn
-https://gitimn.com/mayx/blog
-https://git.resacachile.cl/mayx/blog
https://git.vycsucre.gob.ve/mayx/blog
https://newtrafficworksgit.online/mayx/blog
https://git.uj-s.com/mayx/blog
https://git.albiobola.nl/mayx/blog
-http://gitea.amm.ar/mayx/blog
https://git.83channel.net/mayx/blog
-https://git.zeppone.com/mayx/blog
https://repo.paperless.rs/mayx/blog
https://urbal.dev/mayx/blog
https://git.pwarde.nl/mayx/blog
https://bolha.dev/mayx/blog
https://git.checkerwars.com/mayx/blog
+https://git.broderlands.com/mayx/blog
+https://gitea.schwegmann.tech/mayx/blog
+https://veretium.com/mayx/blog
+https://gitea.kcm-nixi.cn:32443/mayx/blog
+https://git.riskreduction.net/mayx/blog
+https://git.twitchmagic.pro/mayx/blog
+https://gitea.ctmp.ir/mayx/blog
+https://gitea.marcin00.pl/mayx/blog
+https://git.imagitech.mx/mayx/blog
+https://git.hidosi.ru/mayx/blog
diff --git a/_posts/2026-10-01-quine.md b/_posts/2026-10-01-quine.md
new file mode 100644
index 0000000..237eed8
--- /dev/null
+++ b/_posts/2026-10-01-quine.md
@@ -0,0 +1,1352 @@
+---
+layout: post
+title: 如何制作一个“完整”的博客压缩包？
+tags: [压缩包, Quine, LZMA2, 7-Zip]
+---
+
+ 让AI做出真正的“完整”将不再是难事……<!--more-->
+
+# 起因
+ 在上次[用AI制作了各种东西](/2026/09/01/vibe-coding2.html)之后，我已经完全理解了AI确实是无所不能的。既然如此，那就让它帮我解决曾经未能解决的事情吧？
+ 去年，我为了让下载全站压缩包的按钮不断链，让这个压缩包也包含它本身而研究了[ZIP Quine](/2025/09/01/quine.html)，但限于DEFLATE的回溯窗口大小没能做到……但那是人做的东西，人还是太弱小了，现在换AI来试试，也许一切将变得不一样？
+
+# 制作基于LZMA2的博客压缩包
+ 首先，我把[Ruben Van Mello](https://github.com/ruvmello)写的那篇论文《[A Generator for Recursive Zip Files](https://www.mdpi.com/2076-3417/14/21/9797)》以及生成器[zip-quine-generator](https://github.com/ruvmello/zip-quine-generator)发给了AI，问它这个限制是不是真的，是不是真的无法创造出超过32KiB的ZIP Quine？没过多久它分析完了，告诉我确实存在这样的问题，但并不是无法解决的，最简单的办法就是换个回溯窗口更大的压缩算法。我看了一下它给我列出的几个算法，看起来LZMA2和zstd比较符合要求。不过zstd感觉不是很知名，一般的解压软件应该处理不了，所以我就选择让它基于LZMA2来制作了。
+ 不过LZMA2只是算法，还得选个容器，考虑到7z算是最出名，而且LZMA2本来就是7-Zip的作者开发的，所以就直接让它做7z版本的了。另外因为[Nate Choe](https://github.com/NateChoe1)做了通过扩展欧几里得求逆元来计算CRC32的[PR](https://github.com/ruvmello/zip-quine-generator/pull/3)，所以我也告诉它要用这种方法在多项式时间内解出CRC32的值，而不是爆破。就这样AI花了两个小时左右成功把代码写出来了，效果非常完美，另外它还偷懒地将计算CRC32的算法改成了高斯消元法😆，因为7z格式有3个相互影响的CRC32值，用扩展欧几里得会更复杂一点，不过对7z来说不写入文件的CRC32也不影响，只是会不校验罢了，至少它还是按我要求做了……但其实这个问题也并不是完全不能用扩展欧几里得算法，后来我又强烈要求了一下，AI还是给我写出来了。以下是代码片段，有兴趣的人可以参考一下（不过这个看起来写的就是很复杂，所以我自己只用了高斯消元法）：
+```python
+RU_POLY = 0x104C11DB7 # x^32+x^26+x^23+...+1（含 x^32 首项）
+
+
+def _find_probe(p):
+ ret = 0
+ for i in range(64):
+ if (1 << i) & p:
+ ret = i
+ return ret
+
+
+def _mul_raw(p1, p2):
+ """多项式乘法（无模）。"""
+ ret = 0
+ probe = _find_probe(p1)
+ for i in range(64):
+ if p2 & (1 << i):
+ assert probe + i < 64, "多项式乘法溢出"
+ ret ^= p1 << i
+ return ret
+
+
+def _poly_divmod(dividend, divisor):
+ """多项式长除法，返回 (商, 余)。"""
+ probe = _find_probe(divisor)
+ probe_bit = 1 << probe
+ quot = 0
+ rem = dividend
+ for i in range(63 - probe, -1, -1):
+ if rem & (probe_bit << i):
+ quot |= 1 << i
+ rem ^= divisor << i
+ return quot, rem
+
+
+def _mul(p1, p2, mod):
+ """p1*p2 % mod。"""
+ return _poly_divmod(_mul_raw(p1, p2), mod)[1]
+
+
+def _xgcd(p1, p2):
+ """扩展欧几里得：返回 (k1,k2,gcd)，满足 p1*k1+p2*k2=gcd。"""
+ if _find_probe(p1) < _find_probe(p2):
+ k1, k2, g = _xgcd(p2, p1)
+ return k2, k1, g
+ if p2 == 0:
+ return p1, 0, p1
+ q, r = _poly_divmod(p1, p2)
+ c1, c2, g = _xgcd(p2, r)
+ return c2, c1 ^ _mul_raw(c2, q), g
+
+
+def _minv(p, mod):
+ """p 在环上的乘法逆元；不存在时返回 0。"""
+ k1, _, g = _xgcd(p, mod)
+ if g != 1:
+ return 0
+ return _poly_divmod(k1, mod)[1]
+
+
+def _bitrev32(x):
+ """32 位比特反转。CRC 的输出循环冗余（binascii 反射）↔ 本环（非反射）互为 bit-reverse。"""
+ return int(format(x & 0xFFFFFFFF, "032b")[::-1], 2)
+
+
+def _ring_pow_x(k):
+ """环内 x^k mod P（P=RU_POLY），二进制幂 O(log k)。变量列就是单个环幂。"""
+ res, base, mod, e = 1, 2, RU_POLY, k
+ while e:
+ if e & 1:
+ res = _mul(res, base, mod)
+ base = _mul(base, base, mod)
+ e >>= 1
+ return res
+
+
+def solve_crc_system(files):
+ """解析解 CRC 定点系统
+
+ - 常数列 ：对“变量清零”的数据做一次 binascii.crc32，再 bit-reverse 32 位
+ （binascii 反射 CRC 与本环非反射 CRC 互为 bit-reverse，见 _bitrev32）。
+ - 变量列 ：单个环幂 x^(32 + 8*(len-pos-4))，二进制幂 O(log N) 一步算出；
+ 同一变量出现在多处时按位异或累加。
+ 各自 O(#rows) 次 CRC + 少量环幂即可建出整矩阵，Gauss 消元不变。
+ """
+ n = len(files)
+ mod = RU_POLY
+ matrix = [[0] * (n + 1) for _ in range(n)]
+
+ for file in range(n):
+ data = files[file][0]
+ offsets = files[file][1]
+ N = len(data)
+ zero = bytearray(data)
+ for pos in offsets: # 未知量占 4 字节，清零后求常数项
+ zero[pos:pos + 4] = b"\x00\x00\x00\x00"
+ matrix[file][n] = _bitrev32(crc32(bytes(zero)))
+ for pos, vid in offsets.items():
+ rest = N - pos - 4 # 变量被 4 字节（x^32）+ 其后字节（x^8/个）推到底
+ matrix[file][vid] ^= _ring_pow_x(32 + 8 * rest)
+ matrix[file][file] ^= 1
+
+ for sr in range(n):
+ ex = sr
+ while ex < n and matrix[ex][sr] == 0:
+ ex += 1
+ if ex == n:
+ raise RuntimeError("CRC 多项式系统奇异 @row%d" % sr)
+ if ex != sr:
+ matrix[sr], matrix[ex] = matrix[ex], matrix[sr]
+ inv = _minv(matrix[sr][sr], mod)
+ for er in range(sr + 1, n):
+ mult = _mul(inv, matrix[er][sr], mod)
+ for ec in range(n + 1):
+ matrix[er][ec] ^= _mul(mult, matrix[sr][ec], mod)
+
+ res = [0] * n
+ for row in range(n - 1, -1, -1):
+ v = matrix[row][n]
+ for col in range(row + 1, n):
+ v ^= _mul(res[col], matrix[row][col], mod)
+ res[row] = _mul(v, _minv(matrix[row][row], mod), mod)
+
+ return [_impl_val(res[i]) for i in range(n)]
+
+def _impl_val(math_val):
+ imp = 0
+ for bit in range(32):
+ if math_val & (1 << bit):
+ imp |= 1 << (31 - bit)
+ return imp
+
+class BlogQuine:
+ def solve_crc(self, F, lay, seed):
+ T, h, d = lay["T"], lay["h"], lay["d"]
+ k, n_sub, crc_base = lay["k"], lay["n_sub"], lay["crc_base"]
+ hoff = lay["total"] - h
+ vout_f = lay["total"] - 2 * T
+ hcopy = vout_f + (T - h)
+ # 已知 CRC：seed + 各文件（quine 的是未知量 D）
+ known = [crc32(seed)] + [crc32(data) for _, data in self.files]
+ assert len(known) == n_sub - 1
+ for i, e in enumerate(known):
+ struct.pack_into("<I", F, hoff + crc_base + 4 * i, e)
+ struct.pack_into("<I", F, hcopy + crc_base + 4 * i, e)
+ # 未知量 D N S：D=整个文件、N=头部 F[hoff:hoff+h]、S=签名 F[12:32]
+ dpos = crc_base + 4 * (n_sub - 1)
+ ncopy = 32 + 3 * k + d # C1k 载荷里 F[0:35) 副本起点
+ groups = [[hoff + dpos, hcopy + dpos], # D 出现两处
+ [28, ncopy + 28], # N
+ [8, ncopy + 8]] # S
+
+ # 构造 3 个“文件”喂给解析解系统：
+ # 文件0 = 整个 F，三个未知量各自出现在 groups 两处
+ # 文件1 = 头部块，只有 D 出现在相对 dpos（另一处 hcopy+dpos 在头外）
+ # 文件2 = 签名块，只有 N 出现在相对 16（28-12）
+ whole = bytes(F)
+ hdr = bytes(F[hoff:hoff + h])
+ sig = bytes(F[12:32])
+ f0_off = {hoff + dpos: 0, hcopy + dpos: 0,
+ 28: 1, ncopy + 28: 1,
+ 8: 2, ncopy + 8: 2}
+ f1_off = {dpos: 0}
+ f2_off = {28 - 12: 1}
+ vals = solve_crc_system([(whole, f0_off), (hdr, f1_off), (sig, f2_off)])
+
+ for g in range(3):
+ for p in groups[g]:
+ F[p:p + 4] = struct.pack("<I", vals[g])
+ real = (crc32(F), crc32(F[hoff:hoff + h]), crc32(F[12:32]))
+ assert real == tuple(vals), "CRC 定点失败: %s != %s" % (real, vals)
+ return vals
+```
+
+ 于是我第一时间就把原来的TGZ压缩命令换掉，换成了AI给我写的[blogquine.py](https://github.com/Mabbs/mabbs.github.io/blob/master/_tools/blogquine.py)，现在就可以通过[这里](https://mayx.eu.org/MayxBlog.7z)下载到“完整”包含我博客所有内容的压缩包了。
+ 不过唯一的问题就是这样做出来的压缩包并没有压缩😂，相当于给做成了普通的归档了。当然我的博客本身倒是不大，没压缩也多不了多少空间，但相比于能做出“完整”的效果来说，这点浪费的空间也是小问题了。
+## 对TXZ格式的尝试
+ 在做完7z格式的压缩包之后，我发现了一个问题，虽然7z确实很流行，但是在Linux下解压起来有点麻烦，7-Zip历史上主要面向Windows，Linux上长期以来更多依赖p7zip等第三方移植，因此生态集成度不如tar.xz，想要解压7z文件还得额外安装。
+ 不过Linux下也有个支持LZMA2算法的压缩软件，那就是前些年出过[后门](https://tukaani.org/xz-backdoor/)的XZ Utils，配合tar就可以做出TXZ（tar.xz）文件，甚至用我[博客终端](https://mabbs.github.io/linux/)中的BusyBox也能解压。我想了一下反正有AI，干脆一句话让AI帮我把blogquine.py改成tar.xz格式的好了，结果倒也没费多少功夫，AI就这样写出来了：
+
+<details markdown="1">
+<summary markdown="span">
+Show Code
+</summary>
+
+```python
+#!/usr/bin/env python3
+# -*- coding: utf-8 -*-
+
+import argparse
+import binascii
+import io
+import lzma
+import os
+import struct
+import sys
+import tarfile
+import time
+import ctypes
+import ctypes.util
+
+# ============================================================
+# Part 1: 最小 LZMA1 range coder（只做编码）
+# ============================================================
+
+kNumBitModelTotalBits = 11
+kBitModelTotal = 1 << kNumBitModelTotalBits # 2048
+kNumMoveBits = 5
+kTopValue = 1 << 24 # 0x1000000
+
+kNumStates = 12
+kNumLitStates = 7
+kNumPosBitsMax = 4
+kNumLenToPosStates = 4
+kNumAlignBits = 4
+kEndPosModelIndex = 14
+kNumFullDistances = 1 << (kEndPosModelIndex >> 1) # 128
+kMatchMinLen = 2
+kNumLowLenBits = 3
+kNumMidLenBits = 3
+kNumHighLenBits = 8
+kNumLowLenSymbols = 1 << kNumLowLenBits # 8
+kNumMidLenSymbols = 1 << kNumMidLenBits # 8
+kNumPosSlotBits = 6
+
+PROB_INIT = kBitModelTotal >> 1 # 1024
+
+
+class RangeEncoder:
+ """LZMA 的区间编码器。low 是 64 位（要容纳进位），range 是 32 位。"""
+
+ def __init__(self):
+ self.low = 0
+ self.range = 0xFFFFFFFF
+ self.cache = 0
+ self.cache_size = 1 # 初值 1 -> 第一个输出字节恒为 0x00
+ self.buf = bytearray()
+
+ def _shift_low(self):
+ if (self.low & 0xFFFFFFFF) < 0xFF000000 or (self.low >> 32) != 0:
+ temp = self.cache
+ while True:
+ self.buf.append((temp + (self.low >> 32)) & 0xFF)
+ temp = 0xFF
+ self.cache_size -= 1
+ if self.cache_size == 0:
+ break
+ self.cache = (self.low >> 24) & 0xFF
+ self.cache_size += 1
+ self.low = ((self.low & 0xFFFFFFFF) << 8) & 0xFFFFFFFF
+
+ def encode_bit(self, probs, idx, bit):
+ p = probs[idx]
+ bound = (self.range >> kNumBitModelTotalBits) * p
+ if bit == 0:
+ self.range = bound
+ probs[idx] = p + ((kBitModelTotal - p) >> kNumMoveBits)
+ else:
+ self.low += bound
+ self.range -= bound
+ probs[idx] = p - (p >> kNumMoveBits)
+ while self.range < kTopValue:
+ self.range = (self.range << 8) & 0xFFFFFFFF
+ self._shift_low()
+
+ def encode_direct_bits(self, value, num_bits):
+ for i in range(num_bits - 1, -1, -1):
+ self.range >>= 1
+ if (value >> i) & 1:
+ self.low += self.range
+ while self.range < kTopValue:
+ self.range = (self.range << 8) & 0xFFFFFFFF
+ self._shift_low()
+
+ def bittree_encode(self, probs, off, num_bits, symbol):
+ m = 1
+ for i in range(num_bits - 1, -1, -1):
+ bit = (symbol >> i) & 1
+ self.encode_bit(probs, off + m, bit)
+ m = (m << 1) | bit
+
+ def bittree_reverse_encode(self, probs, off, num_bits, symbol):
+ m = 1
+ for i in range(num_bits):
+ bit = symbol & 1
+ symbol >>= 1
+ self.encode_bit(probs, off + m, bit)
+ m = (m << 1) | bit
+
+ def finish(self):
+ for _ in range(5):
+ self._shift_low()
+ return bytes(self.buf)
+
+
+def _pos_slot_and_bits(d):
+ if d < 4:
+ return d, 0, 0
+ for slot in range(4, 64):
+ n = (slot >> 1) - 1
+ base = (2 | (slot & 1)) << n
+ if d < base + (1 << n):
+ return slot, n, d - base
+ raise ValueError("distance too large: %d" % d)
+
+
+# pb 必须与写进每个 LZMA2 chunk 头的 PROPS_BYTE(0x5D) 一致。
+# lc/lp 只影响 literal 编码的概率表索引，而本编码器不实现 literal 路径，故无需常量。
+PB = 2
+
+
+class LzmaEncoder:
+ """只实现 quine 用到的两条路径：match 与 rep0-match。
+
+ literal / rep-g1 / rep-g2 三条分支从未被构造，因此它们对应的概率表
+ （p_lit、p_is_rep_g1、p_is_rep_g2）以及 prev_byte 都不必存在。
+ reps 同理：编码器从不回读（rep0 的距离由解码器自行维护），故不保存。
+ """
+
+ def __init__(self):
+ self.pos_mask = (1 << PB) - 1
+ self.rc = RangeEncoder()
+ self.pos = 0
+ self.state = 0
+ n = PROB_INIT
+ self.p_is_match = [n] * (kNumStates << kNumPosBitsMax)
+ self.p_is_rep = [n] * kNumStates
+ self.p_is_rep_g0 = [n] * kNumStates
+ self.p_rep0_long = [n] * (kNumStates << kNumPosBitsMax)
+ self.p_pos_slot = [n] * (kNumLenToPosStates << kNumPosSlotBits)
+ self.p_spec_pos = [n] * (kNumFullDistances - kEndPosModelIndex)
+ self.p_align = [n] * (1 << kNumAlignBits)
+ self.p_len_choice = [n] * 2
+ self.p_len_low = [n] * (16 * kNumLowLenSymbols)
+ self.p_len_mid = [n] * (16 * kNumMidLenSymbols)
+ self.p_len_high = [n] * (1 << kNumHighLenBits)
+ self.p_rep_len_choice = [n] * 2
+ self.p_rep_len_low = [n] * (16 * kNumLowLenSymbols)
+ self.p_rep_len_mid = [n] * (16 * kNumMidLenSymbols)
+ self.p_rep_len_high = [n] * (1 << kNumHighLenBits)
+
+ @property
+ def pos_state(self):
+ return self.pos & self.pos_mask
+
+ def _encode_len(self, choice, low, mid, high, length):
+ ps = self.pos_state
+ l = length - kMatchMinLen
+ if l < kNumLowLenSymbols:
+ self.rc.encode_bit(choice, 0, 0)
+ self.rc.bittree_encode(low, ps << kNumLowLenBits, kNumLowLenBits, l)
+ else:
+ self.rc.encode_bit(choice, 0, 1)
+ l -= kNumLowLenSymbols
+ if l < kNumMidLenSymbols:
+ self.rc.encode_bit(choice, 1, 0)
+ self.rc.bittree_encode(mid, ps << kNumMidLenBits, kNumMidLenBits, l)
+ else:
+ self.rc.encode_bit(choice, 1, 1)
+ self.rc.bittree_encode(high, 0, kNumHighLenBits, l - kNumMidLenSymbols)
+
+ def _write_dist(self, dist, lts):
+ d = dist - 1
+ slot, n, low_bits = _pos_slot_and_bits(d)
+ self.rc.bittree_encode(self.p_pos_slot, lts << kNumPosSlotBits,
+ kNumPosSlotBits, slot)
+ if slot >= 4:
+ if slot < kEndPosModelIndex:
+ base = (2 | (slot & 1)) << n
+ off = base - slot - 1
+ self.rc.bittree_reverse_encode(self.p_spec_pos, off, n, low_bits)
+ else:
+ self.rc.encode_direct_bits(low_bits >> kNumAlignBits, n - kNumAlignBits)
+ self.rc.bittree_reverse_encode(self.p_align, 0, kNumAlignBits,
+ low_bits & ((1 << kNumAlignBits) - 1))
+
+ def match(self, dist, length):
+ assert kMatchMinLen <= length <= 273, length
+ ps = self.pos_state
+ self.rc.encode_bit(self.p_is_match, (self.state << kNumPosBitsMax) + ps, 1)
+ self.rc.encode_bit(self.p_is_rep, self.state, 0)
+ lts = min(length - kMatchMinLen, kNumLenToPosStates - 1)
+ self._encode_len(self.p_len_choice,
+ self.p_len_low, self.p_len_mid, self.p_len_high, length)
+ self._write_dist(dist, lts)
+ self.state = 7 if self.state < kNumLitStates else 10
+ self.pos += length
+
+ def rep_match(self, length):
+ assert kMatchMinLen <= length <= 273, length
+ ps = self.pos_state
+ self.rc.encode_bit(self.p_is_match, (self.state << kNumPosBitsMax) + ps, 1)
+ self.rc.encode_bit(self.p_is_rep, self.state, 1)
+ self.rc.encode_bit(self.p_is_rep_g0, self.state, 0)
+ self.rc.encode_bit(self.p_rep0_long, (self.state << kNumPosBitsMax) + ps, 1)
+ self._encode_len(self.p_rep_len_choice,
+ self.p_rep_len_low, self.p_rep_len_mid, self.p_rep_len_high, length)
+ self.state = 8 if self.state < kNumLitStates else 11
+ self.pos += length
+
+ def finish(self):
+ return self.rc.finish()
+
+
+# ============================================================
+# Part 2: tar + xz 格式原语
+# ============================================================
+
+MAX_MATCH = 273 # LZMA1 单个 match 长度上限
+CHUNK = 65536 # LZMA2 单 chunk 解压上限
+PROPS_BYTE = 0x5D # lc=3, lp=0, pb=2
+SEED_NOTE = ("\nMayx's Blog!").encode("utf-8")
+
+# xz 格式常量
+XZ_MAGIC = b"\xFD7zXZ\x00"
+XZ_FOOTER_MAGIC = b"YZ"
+XZ_CHECK_CRC64 = 0x04
+LZMA2_FILTER_ID = 0x21
+CHECK_SIZE = 8 # CRC64 占 8 字节
+_XZ_FLAGS = bytes([0x00, XZ_CHECK_CRC64]) # Stream Flags: reserved + check_type
+
+# tar 格式常量
+TAR_BLOCK = 512
+
+
+def round_up_512(n):
+ """长度按 tar 块 512 字节向上取整。"""
+ return (n + TAR_BLOCK - 1) // TAR_BLOCK * TAR_BLOCK
+
+
+def crc32(b):
+ return binascii.crc32(b) & 0xFFFFFFFF
+
+
+# ---------- CRC64 (ECMA-182, reflected) ----------
+
+_CRC64_POLY = 0xC96C5795D7870F42 # reflected ECMA-182
+_CRC64_INIT = 0xFFFFFFFFFFFFFFFF
+_CRC64_XOROUT = 0xFFFFFFFFFFFFFFFF
+_CRC64_NON_REFLECTED = 0x142F0E1EBA9EA3693 # 非反射多项式 (65 bit)
+_CRC64_MOD_BIT = 1 << 64 # x^64 对应的 bit
+
+
+_liblzma = None
+try:
+ _lzma_name = ctypes.util.find_library('lzma')
+ if _lzma_name:
+ _liblzma = ctypes.CDLL(_lzma_name)
+ _liblzma.lzma_crc64.argtypes = [ctypes.c_char_p, ctypes.c_size_t, ctypes.c_uint64]
+ _liblzma.lzma_crc64.restype = ctypes.c_uint64
+ # 验证：CRC64("123456789") 应为 0x995dc9bbdf1939fa
+ if _liblzma.lzma_crc64(b'123456789', 9, 0) != 0x995dc9bbdf1939fa:
+ _liblzma = None
+except (OSError, AttributeError):
+ _liblzma = None
+
+
+def _make_crc64_table():
+ table = []
+ for i in range(256):
+ crc = i
+ for _ in range(8):
+ crc = (crc >> 1) ^ _CRC64_POLY if (crc & 1) else crc >> 1
+ table.append(crc)
+ return table
+
+
+_CRC64_TABLE = _make_crc64_table()
+
+
+def _crc64_pure(data):
+ """纯 Python CRC64（ECMA-182 反射，init/xorout = 0xFFFF...FFFF）。"""
+ crc = _CRC64_INIT
+ for byte in data:
+ crc = (crc >> 8) ^ _CRC64_TABLE[(crc ^ byte) & 0xFF]
+ return crc ^ _CRC64_XOROUT
+
+
+def _crc64_lib(data):
+ """liblzma CRC64（init=0，内部处理 init/xorout）。"""
+ return _liblzma.lzma_crc64(data, len(data), 0)
+
+
+crc64 = _crc64_lib if _liblzma else _crc64_pure
+
+
+# ---------- GF(2^64) 多项式运算 ----------
+# 用于 CRC64 自引用求解。CRC64 的线性贡献可表示为
+# bit_reverse(contribution(D)) = D_poly * P (mod G_non)
+# 其中 D_poly = bit_reverse(D)，P 是位置决定的多项式。
+# 方程 D_poly * (1 ^ P1 ^ P2) = bit_reverse(CRC64(W)) 通过多项式逆元求解。
+
+def _bit_reverse64(v):
+ r = 0
+ for _ in range(64):
+ r = (r << 1) | (v & 1)
+ v >>= 1
+ return r
+
+
+def _poly_mul_mod(a, b):
+ """GF(2) 多项式乘法 mod G（非反射）。"""
+ result = 0
+ while b:
+ if b & 1:
+ result ^= a
+ b >>= 1
+ a <<= 1
+ if a & _CRC64_MOD_BIT:
+ a ^= _CRC64_NON_REFLECTED
+ return result
+
+
+def _poly_pow(base, exp):
+ """多项式幂：base^exp mod G。"""
+ result = 1
+ while exp:
+ if exp & 1:
+ result = _poly_mul_mod(result, base)
+ base = _poly_mul_mod(base, base)
+ exp >>= 1
+ return result
+
+
+def _poly_minv(p):
+ """多项式逆元 p^(-1) mod G，用扩展欧几里得算法。"""
+ if p == 0:
+ return 0
+ old_r, r = p, _CRC64_NON_REFLECTED
+ old_s, s = 1, 0
+ while r:
+ # poly divmod(old_r, r) -> (q, rem)
+ probe_r = r.bit_length() - 1
+ rem = old_r
+ q = 0
+ while rem.bit_length() - 1 >= probe_r and rem:
+ shift = rem.bit_length() - 1 - probe_r
+ q |= 1 << shift
+ rem ^= r << shift
+ old_r, r = r, rem
+ # s = old_s ^ q*s (raw 多项式乘法)
+ prod = 0
+ a, b = q, s
+ while b:
+ if b & 1:
+ prod ^= a
+ b >>= 1
+ a <<= 1
+ old_s, s = s, old_s ^ prod
+ if old_r != 1:
+ return 0
+ # old_s mod G
+ probe_m = _CRC64_NON_REFLECTED.bit_length() - 1
+ rem = old_s
+ while rem.bit_length() - 1 >= probe_m and rem:
+ shift = rem.bit_length() - 1 - probe_m
+ rem ^= _CRC64_NON_REFLECTED << shift
+ return rem
+
+
+def store_hdr(payload_len, first=False):
+ """LZMA2 uncompressed chunk 头（3 字节，大端 size-1）。"""
+ assert 1 <= payload_len <= 65536
+ return bytes([0x01 if first else 0x02]) + (payload_len - 1).to_bytes(2, "big")
+
+
+def matches_for(dist, total):
+ """dist 固定、总长 total 的 token 序列：首个 match + 后续 rep0。"""
+ assert total >= 2
+ toks = []
+ first = min(MAX_MATCH, total)
+ if total - first == 1:
+ first -= 1
+ toks.append(("m", dist, first))
+ total -= first
+ while total > 0:
+ l = min(MAX_MATCH, total)
+ if total - l == 1:
+ l -= 1
+ toks.append(("r0", l))
+ total -= l
+ return toks
+
+
+def _add_gear(chunks, o, f, q):
+ """追加一组标准 gear：store 载荷 x = slip+3，紧跟一个 lzma 把那 x 字节复制一遍。
+
+ lzma chunk 解压出的字节数正好等于 x，所以齿轮转完之后 slip (f - (o-q)) 精确
+ 归约为 len(cb)（很小的正数，x 被 CHUNK 截断时则按 CHUNK 缩减）。
+ _layout_iterate 反复套用把 slip 压到 <= 16，_trim_layouts 用它做相位微调。
+ 返回追加后的 (o, f)。
+ """
+ x = min(f - (o - q) + 3, CHUNK)
+ chunks.append({"kind": "store", "foff": f, "size": 3 + x,
+ "ooff": o, "olen": x})
+ o += x
+ f += 3 + x
+ cb, cu = lzma_chunk(matches_for(x, x), o)
+ chunks.append({"kind": "lzma", "foff": f, "size": len(cb),
+ "ooff": o, "olen": cu, "bytes": cb})
+ return o + cu, f + len(cb)
+
+
+def _forward_vac(F, vac, q):
+ """vac_store：把紧随其后的等长字节块前移覆盖自身。"""
+ fo = vac["ooff"] - q
+ olen = vac["olen"]
+ F[fo:fo + olen] = F[fo + olen:fo + 2 * olen]
+
+
+def dict_prop_for(maxdist):
+ """选最小的 LZMA2 dict prop 使字典 >= maxdist。"""
+ for p in range(41):
+ if (2 | (p & 1)) << (p // 2 + 11) >= maxdist:
+ return p, (2 | (p & 1)) << (p // 2 + 11)
+ raise ValueError("distance too large")
+
+
+def lzma_chunk(tokens, out_pos):
+ """编一个 LZMA chunk（0xC0: state+props reset，无 dict reset，无 end marker）。"""
+ enc = LzmaEncoder()
+ enc.pos = out_pos
+ total = 0
+ for t in tokens:
+ if t[0] == "m":
+ enc.match(t[1], t[2])
+ total += t[2]
+ else:
+ enc.rep_match(t[1])
+ total += t[1]
+ data = enc.finish()
+ assert total - 1 < 65536 and len(data) - 1 < 65536
+ hdr = bytes([0xC0]) + (total - 1).to_bytes(2, "big") + \
+ (len(data) - 1).to_bytes(2, "big") + bytes([PROPS_BYTE])
+ return hdr + data, total
+
+
+# ---------- tar 原语 ----------
+
+def tar_header(name, size, mtime, mode=0o644, typeflag=b'0', uid=0, gid=0):
+ """构建 512 字节 POSIX ustar tar header。
+ 注意：tar 数值字段包含 null 终止符，slice 范围必须精确匹配字段宽度。
+ mode/uid/gid 各 8 字节（7 octal + NUL），size/mtime 各 12 字节（11 octal + NUL）。
+ """
+ h = bytearray(512)
+ name_bytes = name.encode('utf-8')[:100]
+ h[0:len(name_bytes)] = name_bytes
+ h[100:108] = b'%07o\x00' % mode # 8 bytes (field 100-107)
+ h[108:116] = b'%07o\x00' % uid # 8 bytes (field 108-115)
+ h[116:124] = b'%07o\x00' % gid # 8 bytes (field 116-123)
+ h[124:136] = b'%011o\x00' % size # 12 bytes (field 124-135)
+ h[136:148] = b'%011o\x00' % mtime # 12 bytes (field 136-147)
+ h[148:156] = b' ' # checksum placeholder (8 spaces)
+ h[156:157] = typeflag
+ h[257:263] = b'ustar\x00'
+ h[263:265] = b'00'
+ assert len(h) == 512, "header length %d != 512" % len(h)
+ # 计算校验和：所有字节之和，checksum 字段视为空格
+ chksum = sum(h) & 0o7777777
+ h[148:156] = b'%06o\x00 ' % chksum # 6 octal + NUL + space = 8 bytes
+ assert len(h) == 512, "header length %d != 512 after checksum" % len(h)
+ return bytes(h)
+
+
+# ---------- xz 原语 ----------
+
+def xz_varint(v):
+ """xz 变长整数编码：每字节 7 位数据（LSB first），MSB 为续位。"""
+ b = []
+ while v >= 0x80:
+ b.append((v & 0x7F) | 0x80)
+ v >>= 7
+ b.append(v & 0x7F)
+ return bytes(b)
+
+
+def xz_stream_header():
+ """12 字节 xz stream header (CHECK_CRC64)。
+ Stream Flags = [reserved(0x00), check_type(CRC64=0x04)]。
+ """
+ flags = _XZ_FLAGS
+ crc = crc32(flags)
+ return XZ_MAGIC + flags + struct.pack('<I', crc)
+
+
+def xz_block_header(dict_size):
+ """xz block header（单 LZMA2 filter）。
+ 返回 (header_bytes, 实际字典大小)；header 长度即 block header 总长度。
+ """
+ prop, real_dict = dict_prop_for(dict_size)
+ # filter flags: filter_id(1) + props_size(1) + props(1=prop byte)
+ filter_flags = bytes([LZMA2_FILTER_ID, 1, prop])
+ # block header content: flags(1, 0x00=1 filter) + filter_flags
+ content = bytes([0x00]) + filter_flags
+ # 填充到 (1 + len(content) + 4) 是 4 的倍数
+ total = 1 + len(content) + 4
+ pad = (4 - total % 4) % 4
+ content += b'\x00' * pad
+ bh = 1 + len(content) + 4
+ assert bh % 4 == 0, "bh not 4-aligned: %d" % bh
+ crc = crc32(bytes([bh // 4 - 1]) + content)
+ header = bytes([bh // 4 - 1]) + content + struct.pack('<I', crc)
+ assert len(header) == bh
+ return header, real_dict
+
+
+def xz_index(records):
+ """xz index。records = [(unpadded_size, uncompressed_size), ...]。"""
+ data = bytes([0x00]) # index indicator
+ data += xz_varint(len(records))
+ for unpadded, uncompressed in records:
+ data += xz_varint(unpadded)
+ data += xz_varint(uncompressed)
+ # 填充到 (len(data) + 4) 是 4 的倍数
+ pad = (4 - (len(data) + 4) % 4) % 4
+ data += b'\x00' * pad
+ return data + struct.pack('<I', crc32(data))
+
+
+def xz_stream_footer(backward_size):
+ """12 字节 xz stream footer (CHECK_CRC64)。
+ backward_size = (index_size / 4) - 1。
+ Stream Flags = [reserved(0x00), check_type(CRC64=0x04)]。
+ CRC32 覆盖 Backward Size + Stream Flags（6 字节，不含 CRC32 和 Footer Magic）。
+ """
+ flags = _XZ_FLAGS
+ crc_data = struct.pack('<I', backward_size) + flags # 6 bytes, no magic
+ crc = crc32(crc_data)
+ return struct.pack('<I', crc) + crc_data + XZ_FOOTER_MAGIC
+
+
+# ============================================================
+# Part 3: 多文件 tar.xz quine 构造器
+# ============================================================
+
+class TarXzQuine:
+ def __init__(self, root, quine_name="quine.ta