taf.fyi

間夫之爱——《哀鸿：城破十日记》

2026-04-06T00:00:00.000Z

# 前言

$\text{别把看重的东西附上无边的价值}\\ \text{也别把他人看重的东西贬得一文不值}$

前半句是一位学长的格言，我引用于此，后半句为我自己所补充。

诚然这是一个当前差评一边倒的作品，我要是说我喜欢这个作品，说我喜欢里面的角色林翩翩，大概会招来很多笑话和贬低。尽管如此，我依然觉得假以时日，这部作品自然会得到更加公正客观的评价。其前作饿殍我也是相当喜欢的，并写过一篇观后感 (含剧透)，所以在我玩完饿殍后不久得知续作哀鸿公布的消息时，便决定一定要玩一玩了。不怕笑话地说，我玩哀鸿是流过不少泪的，我觉得哀鸿比饿殍更加出彩。

本文只讲 “为什么我会喜欢《哀鸿：城破十日记》”，不讲其缺陷，其缺点早已有很多人诟病批评太多，不需要我赘述。本文的 杂谈 以后的部分含轻微剧透，若完全不想被剧透 ~~(虽然大部分人估计都被剧透过了)~~ 并且对游戏感兴趣，那么还是谨慎选择要不要读。我希望更多人能不抱着偏见亲身体验这个游戏后再给予评价，届时我想即使是不喜欢，也会多少觉得这部作品并非一无是处。

首先，我是坚持认为林翩翩是真女主的，也就是说，我认为林翩翩是这个故事的核心角色，并不认为她是一个饱含恶意的角色，也并不乐于见到人们向她倾泻恶意。

# 杂谈

从游戏本身一些非剧情设计上，我也注意到了一些可以辩解林翩翩是真女主的地方：

游戏本身的主程序 TheLamentingGeese.exe 用的 Icon 图是林翩翩
这个游戏前期一直选第一个选项是 “最正确的”，能够避免 BE 的，后期的二选一反而要尽量选第二个选项才是避免 NE 的：
- 后期若一直选第一个选项所进到的 NE，男主会幻视地看到林翩翩。其他 NE 则没有这般对两位女主的描写
- 后期若一直选第二个选项所进到的 TE，则是游戏流程相对更长一点、揭示的东西更多一点的林翩翩结局
游戏通关后，鉴赏音乐时，可以看到如下三首曲目，排在最后：
- 翩翩偏偏
- 翩翩如此
- 翩翩那年
三首实际上都是同一织体稍加变化或更换乐器，发布的游戏原声带倒是只有其中一首 “翩翩如此”。游戏过程中，我恰好也最喜欢这几首，觉得它们最为温柔

当然，我自知这些只是一些没什么说服力的小细节，但若是认可我的想法的人，也会多少像我一般猜测这些细节是嵇零有意为之。

# 香臭

在我玩这个游戏的时候，最令我印象深刻的，是忆线第十回，方知宥第一次与雁儿姐在青楼重逢，两人交流琴棋书画，结束后回家的那一晚：

	今夜能与她重逢，同她交心，听她奏乐…… 这些种种，都让我心情前所未有的好。
	甚至，我有了一种 “今夜简直是此生最好的一夜” 的感觉。
	我想将今夜反复品味，想永远都不要忘记。
	哪怕是出泠音阁后，我仍然在路上反复品味，这使我不自觉地加快脚步，身心却完全分离。
	我的心仍沉浸在雁儿姐的姿容、对话、以及琴曲之中。
	我的身却宛如失去了控制，手臂欢快地摆动着，腿脚也自己寻找着归路。
	我穿过南门，穿过青楼的街区，穿过花街……
	我时而傻笑加快脚步，时而停驻，趁人不注意时嗅一下手背上的残香，回味方才的种种
	直到 ——
林翩翩	咦？知宥？
	直到有一人唤我的名字。
方知宥	……
	我侧过眼眸，朝着声音的来处望去。
	柳巷的一处，林翩翩提一盏灯站着，映着她瘦削的身影，以及凌乱的发丝。
	她看向我，眼神中带着讶异，似乎是没想到会如此突然地与我重逢。
方知宥	这么晚还在啊……
	我有些尴尬地向她打招呼。
	大概是因为与雁儿姐久别重逢后的喜悦太过强烈，此时，我的脑袋不太清醒。
	一边向她打招呼时，我还一边向她迈出了一步。
方知宥	……
	其实，迈出脚步后，我便有点后悔了。
	若是离她近了，她便能闻见我身上的香味，知晓我去了青楼。
	不知怎的。
	我不太想让她知道我去了青楼。
林翩翩	你别…… 别走太近了！
	没等我主动因后悔而退步，林翩翩便有些慌张地后退一步，她手中提着的灯也因此晃乱了人影。
方知宥	呃，怎么了？
	虽然，我此时也不想离她太近，但我没想到她会主动提出来这一点。
林翩翩	我…… 我刚刚才接过客，那人甚是粗鲁，弄得我身上有些味道……
	她低下头，咬着唇，将手挡在胸前，有些不好意思地说道。
方知宥	……
	我微微一怔。
	原来如此。
	此刻，已是亥时了。
	林翩翩的姿色，在柳巷绝对算是出众的。
	若不像与我相遇的那个夜晚那般一直哭，
	这个时辰她必定是接过客的。
	她大概是刚接过一个客，或者是今夜曾接过数个客人…… 已在附近的酒肆屋舍中短宿过数次……
	此时，她大概是想最后再站一会儿，揽一单最后的生意…… 不料却遇见了我。
林翩翩	对了…… 知宥，有一件事我想讲给你听，是关于我的一件好事……
	正当我在思考时，她突然向我开口了。
方知宥	哦？什么好事啊？
	我正觉得尴尬，没有话题可以找，一时不知该说些什么。
	正当此时，她突然给了我转移话题的由头。
	于是，我便迫不及待地将话题接上。
林翩翩	我……
	她正要开口，却突然顿住。
林翩翩	咦？…… 总感觉你身上好香啊……
	她嗅了嗅鼻子，似乎因闻到我身上的香味而分了神。
方知宥	……
	还是败露了。
林翩翩	嘿嘿，先不提我的事，你难道刚去过青楼啦？
	她抬起眼眸，打趣般地笑着望向我。
方知宥	我……
	……

	……
林翩翩	嘿嘿，那就好，那夜从桥上看过去呀，她简直像是一位下凡的天女……
	她抿着唇赞叹道，眼里闪烁光芒，看起来也很开心。
林翩翩	知宥，你能和她再相遇是件好事…… 只是注意别花太多银子了，留些银子很重要，这样以后无论怎样都能有个后路……
	紧接着，她还不忘像是老娘一般叮嘱我存钱。
方知宥	嗯……
	我点了点头。
林翩翩	喔，时辰有些晚了，你得回家了吧…… 快些回去吧！
林翩翩	刚见过心心念念的人，我若是你啊…… 必定立刻回去睡觉！好续着念想做个好梦！
	她看了看暗下来的夜空，有些着急地对我提醒道。
方知宥	好，那你也早休息。
	我点了点头，向她叮嘱了一句后，便与她挥手告别，擦肩而过，背道而行。
方知宥	……
	走了十几步后，我将要拐过路口。
	这时，我才突然想起来，她刚才说 “有一件关于她的好事要告诉我”。
方知宥	啊，对了，你刚才……
	我回过头去，想要叫她。
方知宥	……
	然而，柳巷的尽头，早没了那盏微暗的灯，也没了她的身影。
	……

显然，这里的描写可以用一个字轻易地概括：“卑”。林翩翩身为柳巷的底层妓女是卑微的，更是自卑的，在这一处 “臭” 与 “香”，“暗” 与 “明” 的对比淋漓尽致地展现了出来：林翩翩的身上沾染着柳巷嫖客的臭，方知宥的身上浸染着青楼闺阁的香；林翩翩在夜晚和陌生粗鲁的客人做着性服务的工作，方知宥在白天和青梅竹马的头牌花魁苏怜烟乐谈琴棋书画；面对着这样的方知宥和苏怜烟，她的 “好事” 显得不值一提，她表达了自己的祝福和关心，然后便匆忙地从对方眼前消失了。

在这一处对比，我觉得我看到了整部作品的基调，并且彻底将我的注意力从表面的女主苏怜烟转移到了林翩翩身上。

# 纯洁

顺治六年，我听说那下令屠城的金翅大鹏王因感染天花而死，死前脸上长满了出血的脓包，甚是难看。
闻此死讯，我心中自是快意 —— 这杀戮无数的魔头，终究是遭了报应。
然而，在这消息传来数月后的一个晚秋，我却突然做了一个梦。
梦中，我见到了一个故人 ——
—— 林翩翩。
梦里的她，穿着那身我曾见过的苍绿色丝绸长裙，静立在一片绚烂的花海之中。
她墨发如瀑，裙袂随风轻扬，面容却有些模糊，看不真切。
我看不清她是在哭泣，还是在微笑。
只知她静静注视着我，一言不发。
奇怪 ……
此刻梦中的她，给我的感觉与以往任何时刻都不同。
她身穿华服，是那闻名一城的红倌人的模样，早已褪去了最初遇到她时的青涩怯懦。
然而，她身上却不见丝毫刻意修饰的媚态。
—— 纯洁。
不知为何，这次见到她，我脑海中竟浮现出这样一个词。
一个或许与我认知中她的最初与最终身份，全然不符的词。
……

这大概是嵇零最敢写的一段。他直接把 “纯洁” 两个字扔出来，他想说，那个卖了十几年身的林翩翩身脏心不脏。

# 間夫

$\text{人类最古老的职业是卖淫}\\ \text{正如人类最古老的情感是性欲}$

妓女的题材让我想起一部日本畅销 “非虚构作品”《东京贫困女子》，它描写了日本社会边缘的风俗小姐、AV 女演员、非法卖淫的女大学生等人物，整部作品主要来自作者中村淳彦和同事对真实人物的采访。这部作品漫画化后，我得以有机会读过，其描写自然远比哀鸿现实，其中所写妓女所面临种种困境，今时如此，古时亦然。然而，我并不因此就觉得哀鸿之中的妓女写的不好，我并不会在一个虚构作品里苛求它贴近现实，我更希望在里面能看到现实中所看不到的，值得赞颂的，或许是人类的情感，或许是人性的光辉。

好巧不巧，前一段时间我玩完 Muv-Luv，对其标题甚是感兴趣，特意考究了一下，因而得知了其中 Muv 来自日语俚语 —— 間夫。对 Muv-Luv 标题的详细解读在这篇文章的前言部分 (当然前言是没有剧透的)。

間夫，读作 mabu ，源自日本的妓院和妓女文化，它是艺妓们使用的词语，原意是指情夫，汉字写作間 (ma) 夫 (bu)，它褪去汉字仅保留读音演变为如今的日本俚语マブ (ma bu)，意思是真正的，真挚的。为什么間夫会引申出这样的含义？因为它在过去所指代的正是妓女 “真正的爱人”。

每日卖身的妓女，竟然还会有所谓的倾注了真情实感的爱人？看上去好像有些可笑，但这其实正是这些妓女生活的一种寄托。我想，读到本文的大部分人，人生都是充满希望的，所以难以想象这样的人生 —— 底层妓女的人生，绝望的，一眼望得到头的人生，这也是林翩翩这样的角色在真实世界本该有的人生。于此诞生的便是，在只有性而没有爱的人生里寻求爱的，偷偷地抱有着对方能有朝一日为自己赎身的希望的，甚至是她们苦难人生里的一点小小期盼的，“間夫”。

当时我就在想，間夫之爱的题材显然是上限极高的，但如果要我来写間夫之爱，要怎样才能写好？这只是在我脑中一闪而过的小小思考，并未仔细探讨。

现在我有眉目了：我要先写一对理想化的苦命鸳鸯，他们郎才女貌，是世俗意义的才子佳人，他们每天探讨高雅的话题与艺术。然后，我要用他们反衬这与风雅二字风马牛不相及的間夫之爱 ...... 这，就是《哀鸿：城破十日记》。

在氛围最为紧张的游戏开头，我们第一次见到林翩翩的时候，她看到被捉来的方知宥那一刻，她的手僵住了，手里的酒坛落到地上，碎了一地。在那万万不可得罪鞑兵的时候，所有角色都不得不小心翼翼保全性命的时候，她偏偏如此地不小心，打碎了手里的酒坛。她是如此担心知宥的安危，是如此地害怕他就这么死在眼前的鞑兵刀下，所以就在那么一瞬间，也只有短短的一瞬间，这份担心与害怕在胜过了她对自身死亡的恐惧。整个《哀鸿：城破十日记》就是方知宥死里逃生探求真相的故事，而在被绝望笼罩、人名如草芥的扬州城那五天，正是林翩翩拯救了方知宥，正是林翩翩帮他找出了那所谓的真相。

可这样的林翩翩偏偏生前从未真正得到方知宥的爱。明明不过百两银子便能赎身，为什么仅为见苏怜烟就花了三百两银子的方知宥，就是未曾想过替林翩翩赎身？間夫这个词，自它诞生起便从未代表过間夫对妓女的爱，它不过是妓女对間夫的掺杂着幻想的、自知不切实际的爱。林翩翩自己当然也清楚，大字不识几个的底层妓女如何配得上方知宥，如何比得上琴棋书画样样拿得出手还冰清玉洁的苏怜烟。所有的观众，也包括我，都痛恨着这愚蠢的方知宥，他只有在二十多年后才想起，才明白林翩翩的爱。这是十分日系 “侘寂” 的缺憾，但这里又没有什么日式超展开，没有什么跨越时空的超科学或奇幻的力量，只有那个不过十几铜钱的破旧香囊留了下来。无论方知宥再怎么回应，林翩翩都不可能听得到了。《哀鸿：城破十日记》并没有什么苦大仇深或者深刻的主题，它只是这么一个名为林翩翩的妓女的爱 (間夫) 的故事。

$\text{谨以此作，致那些已逝而长存的}\\ \text{爱情与信念、历史与文化}\\ \text{以及由此而生的亿万却唯一的奇迹}\\$

嵇零在 TE 谢幕中写了如上这段看起来中二无比的话。我对历史与文化没有太多敬畏，但我还是很认可，嵇零所想表达的这些 “爱情与信念”，还有 “奇迹”，这也正是我最期待在一个虚构作品中看到的。

我期待看到这間夫之爱，那被认为最不配得到爱的妓女，那终其一生也未能得到爱的回应的少女，却诠释了最为真挚的爱 —— 这便是那亿万却唯一的奇迹。

Muv-Luv

2026-02-09T00:00:00.000Z

# 前言

我花了四天时间，除了睡觉休息就都在玩这部游戏了，Extra + Unlimited 两篇总共历时 30+ Hours，Alternative 篇历时 40+ Hours。

游戏名 Muv-Luv，读音マブラヴ (ma bu ra bu)，据说是某位编剧拍脑袋随口说出的，刚好也 “朗朗上口”。其中读作ラヴ (ra bu) 的 Luv 确实是 Love 的意思，比较常见即使是非日本人也不难看出，而 Muv 的意义在于它的读音マブ (ma bu)，对于非日本人就比较难理解了。

マブ其实能够在另一个比较常见的日本俚語マブダチ (ma bu da chi) 中看到，这个俚語意思是真正的朋友、摯友。即使是土生土长的日本人也不一定考究过这里的マブ，对于比较熟悉日语的我，我对 Muv-Luv 的マブ的第一印象，就和这些非文学背景的日本人对マブダチ中的マブ的第一印象一样，以为マブ代表眩 (マブ) しい，也就是耀眼的、光彩夺目的意思。

但我了解到マブダチ这个词之后，便对其真正由来有了兴趣，查了一下，发现它的由来其实并不眩しい。マブ源自日本的妓院和妓女文化，它是艺妓们使用的词语，原意是指情夫，汉字写作間 (ma) 夫 (bu)。

妓女，被称为人类最古老的职业。她们往往在工作中被粗暴地对待，因为她们的工作仅仅是性，没有爱。她们的情人 “間夫” 是她们 “真正的丈夫”，是能够帮助她们的，至少是幻想中的，克服困难处境的真正伴侣，她们梦想着有一天能够看到契约结束，她们被 “間夫” 或者别的什么人赎身。“間夫” 是妓女们只有性而没有爱的生活里寻求爱的对象，这是她们苦难人生中为数不多的缓解压力放松的途径之一。

那么，接下来让我们再看一次这个游戏标题：間夫 (Muv)-Love(Luv)，制作组对游戏名的解释为真爱。

游戏的主要创作者，âge 社的社长吉宗钢纪曾吐露，Muv-Luv 在某种程度上是一次对 EVA 的 “复仇”。Muv-Luv 的最后一章尾声部分标题正是游戏名本身 Muv-Luv(真爱)，非常巧妙地呼应了 EVA 的最后一话标题 “真心为你”（まごころを、君に）。まごころ (ma go ko ro) 和マブラヴ (ma bu ra bu)，同样都是四个音，前者是真心，后者是真爱。但是，我在此提到 EVA 绝非为了吹嘘 Muv-Luv 有多高深。实际上，鄙人鉴赏能力有限，没能欣赏出 EVA 所想表达的核心思想，没能理解它的 “真心”。而 Muv-Luv 也绝非想表达什么高深的东西，相反，它的核心是非常简单，非常纯粹的东西。

从 Extra 到 Alternative，玩家都会在 OP 里面看到这句话，一句围绕着 “真爱” 的看起来非常中二的话：

$\text{Save in the name of true love}$

This article contains no AIGC.
本文包含剧透，强烈建议还没体验游戏或动漫的读者别往下读。非常遗憾我无法在不剧透的情况下表达我的想法。
那么，按照惯例，先骂后夸。

# 很多缺点

在系统工程的领域，有着这么一个简单的规律：任何系统越是庞大复杂，越是容易出现漏洞。现代密码学体系并非基于直观上更安全的复杂的加密算法，而是基于单一数学难题的简单算法，也是同样遵循这个简单的道理，因为算法越是复杂，攻击面反而越广。这个道理同样适用于 Galgame，当然我指的是单个故事，比如 Muv-Luv 三部曲实际上还是一个故事，但 Muv-Luv 系列其他作品就不会也不应该纳入这个故事，而是应该分别单独评价了。我也曾读过文本量极大的视觉小说，所以我深刻地理解文本量和阅读体验或者说最终故事的质量绝对不是简单的正相关的，这也就是为什么很多玩家并不喜欢业界所谓的 “分割商” 法，因为说到底 Galgame 终究是商业游戏产品，我们必须承认任何作品总有些部分写的多只是为了水游戏时长或者赚取更多稿费。而写的越多，自然容易写出各种各样的缺点。

Muv-Luv 这部作品，饱含着吉宗钢纪强烈的不惜抵押自己房子换取资金的热情，以及他自儿时以来在众多科幻、机甲动漫作品的影响下积累的特别特别多的想象，所以 Muv-Luv 被塞进去了太多科幻、军事、政治的东西，因此这样一部长篇 Galgame，不可避免的有着非常非常多的缺点，已被很多玩家所诟病过。尽管总是能看到对 Muv-Luv 例如 “立于人类两万多部 Galgame 的顶点”、“史上最强 Galgame” 这些极高的甚至是夸张的评价，但依然需要客观地正视这些缺点。

其首要的也是最大的缺点 —— 也是所有其他缺点的根源，就是它的篇幅太长。枯燥乏味、明显重复的前中期灌水日常，容易让玩家审美疲劳，劝退耐心不足和时间精力有限的玩家。
30+ 小时的日常结束后是 “右翼” 味特别大的长达 5-7 小时的政治戏桥段，对于日本观众可能甚至是加分项，但是对于非日本人绝对是难以共情的，只会感觉到是一种三观和立场的输出。极其降智莫名其妙的在君主立宪制国家谈对君主多么的忠义，反复讲那一套君主应该怎样怎样，将大和民族的领袖塑造为圣人，“民应为国鞠躬尽瘁，国应为民深仁厚泽” 特别的冠冕堂皇。表面试图刻画 “世界不是非黑即白的” 实际上依然没能跳出大和民族的立场，其实际所刻画的是高尚的日本大和民族在狡猾的美国势力阴谋中醒悟到各自的爱国情，然后把矛盾转移到美国完事了。表面上说各方其实都没有立场，都是为了日本，其实最核心的立场就是日本。当然可以理解为正式和 beta 开战前想通过一场人类内斗，流血的代价获取应该团结的反思，但这也没写出来。说实话，非要水字数的话，真的不如将笔墨花在刻画姐妹情上，作为傀儡身不由己但互相搀扶等等，但是囿于老昭和正宗太阳旗出身的吉宗钢纪的强烈爱国情，以及大萧条的时代背景，这篇政治戏在我看来成为了最大的败笔。
恶趣味情节，让部分玩家厌恶，降低这部分玩家的观感。
哪里好用哪里搬的 Beta 大军，想营造新的冲突、突如其来的危机只需要写从哪里哪里突然钻出来庞大的 Beta 大军就行了，一两次或许没问题，但是反反复复的套用，容易让观众感到缺乏新意。
主角的成长塑造 “用力过猛”，本质上其实还是反反复复出现相同套路。其实在主角最后一次回到 “主世界” 终于见到纯夏的时候，已经基本完成了角色的成长，后续的成长描写则是写得越多，反而越差，越让观众感受到相同的套路。
反复用相同的套路杀青角色。除了麻理茉和凉宫遥等少数配角之外，其余角色的战死几乎都非常 “死得其所”。尤其是最终决战亦是如此，所有角色都用生命换来了对战局危机的帮助 —— 甚至这些危机的营造千篇一律是利用 “哪里好用哪里搬的 Beta 大军” 这一套路。这些死亡缺少了一份 “无常”，容易让观众在一次又一次 “先谈心后当烈士” 的套路中产生审美疲劳，愈来愈难以调动观众情绪。
缺少经费而质量断崖式下降的决战。作为最终决战相比前面两场战斗显然质量大幅下降，主角团之外的战斗没有任何描写，主角本身对战斗的推动作用基本没写出来，全程坐在巨型机甲里沿着计划的路线用机枪炮弹打一打 Beta，而其它几位女主的战死同样透露着上一个所讲的问题。
后宫倾向的都合式结局。结局甚至使用游戏名 Muv-Luv 真爱作为最终章的标题，然而却依然回归到 Extra 搞笑风格的所有女主倒贴争夺男主的强烈后宫倾向的结局，恕我直言反而让人看不到 “真爱”。如果非要都合式结局并且不想偏袒任何女主即使是纯夏的话，还不如去掉后宫倒贴元素，将角色们之间的关系回归到友情，这样刻画的后宫风格的 “真爱” 实在是过于廉价。

# 纯粹的爱

讲了这么多尖锐的批评，都是偏向理性的观点，其实是比较累的。接下来，该讲讲稍微轻松一点的，感性的东西。

――――それは、語られなかった他なる結末。とてもちいさな、とてもおおきな、とてもたいせつな、あいとゆうきのおとぎばなし――――

在开头的 Extra 篇里，我作为印象深刻的，是纯夏和武受冥夜邀请来到豪华的大酒店的那个晚上。酒店经理非常客气地让两人点菜，纯夏拿起菜单，面对着菜单里大概从未见过的菜名，陷入了慌乱。看出了纯夏的紧张与尴尬的武，对经理提出，要两碗牛肉饭。

Alternative 篇也有这一段的回忆。武大概也有点慌乱吧，怎么可能完全不慌乱呢？

两人来到酒店外说话，“你怎么这么乱来，本来可以点高级的山珍海味呢！”，“有什么关系，这么高级的酒店的牛肉饭也一定很好吃吧！”，两个人大概这样没头没脑地聊着。我记得纯夏在最后说了一句，ありがとう / 谢谢你。

还有一段同样 Alternative 篇也出现过的，是某一个夜晚两人在窗边对话。纯夏回答自己为什么要每天给武做便当呢...... 这是在冥夜这样的天降大小姐面前，平民青梅竹马的纯夏仅能为武做到的，也是仅纯夏才能做的事情。

慢慢地，纯夏觉得自己赢不了冥夜，知道了她和小武永远在一起这件事不再是理所当然，甚至将要遥不可及。直到冥夜离开的那一天，她哭着让小武去找冥夜，一个人躲到了学校后面的那座山丘上，因为她无法面对小武。这个山丘上有太多的回忆，在 Alternative 的世界里，回忆起一切记忆恢复人格的 00 单元纯夏，同样在无法面对小武的时候，一个人来到了这个山丘上。

Extra 并非因为枯燥无聊便是完全没有必要的，我十分认可这样的 “前期搞笑后期发力” 的布局，但是 Extra 篇或许是受限于传统废萌的形式，没有做到足够搞笑，因而不够吸引人。

而当 Extra 篇结束，Unlimited 篇开始，所有熟悉的人物以不同的面貌再次出现了，但是纯夏没再出现了，取而代之的是一位名为社霞的神秘少女。这位少女就像一枚烟雾弹，完美地 “欺骗” 了武，完美地 “欺骗” 了所有的观众。我打开 Unlimited 的游戏设置，看到纯夏的立绘和语音，我以为还能见到纯夏。而眼前的霞，她实在是太像纯夏了，但是对她说出纯夏这个名字时，她却并不认识。

在漫长的又一个世界的时间线终于迎来第一个结局，我发现纯夏从始至终都没有出现过。是我打得不对吗？我有点慌，打开攻略流程图 —— 没有更多剧情了，该讲的剧情都在线性故事里讲完了。即使解锁一个又一个结局，发现所有女主这些结局不过是公式一般地套用模板，纯夏在 Unlimited 从未出现过。

武认为纯夏不存在于这个世界，玩家当然不会这么认为，但玩家的焦点都在霞身上，结果无论是武还是玩家，都没有找到纯夏。在向克拉克致敬的 “遥远地球之歌” 中， Unlimited 的故事结束了，它表面上是线性的故事，但其实在那个圣诞节后就产生了无数的分支与没有展现的死亡结局，“Unlimited” 代表着每一次死亡后重新轮回的无限。

$\text{私を見つけて}$

Alternative 篇开启，此时已是真正的轮回重来，然而，漫长的十几个小时打下来，依然没有看到纯夏。

当武逃避着这个残酷的世界回到 Extra 的世界时，把这个 Alternative 世界的因果也带了过去，只要 Alternative 世界存在同样的人作为接收体，便会让 Extra 世界认识武的人的记忆在寥寥几句对话内全部消散；只要 Alternative 世界的人遭遇生死这样重大的因果，便会将同样的因果带给 Extra 世界同样的人。在这里，玩家已经可以发现了： Extra 世界的纯夏会失去记忆，并且甚至遭遇了极其严重的事故，但却还活着。尽管游戏中的武还没有发现，但游戏外的玩家可以更加确信了，纯夏是存在于 Alternative 世界的，所以才会发生这样的因果交流。

$\text{鑑はどこがいるはずよ}$

【夕呼】「 …… 你是喜欢纯夏的对吧！？」
【武】「 …… 老师？」
【夕呼】「—— 回答我的问题！」
【武】「—— 喜、喜欢！」
【夕呼】「—— 声音太小了！你的心意就只有这点程度吗！？」
【武】「—— 我喜欢纯夏！！！」
【夕呼】「—— 再大声点！」
【武】「—— 我喜欢纯夏！！！」
【夕呼】「—— 再大声点！」
【武】「—— 我喜欢纯夏！！！」
【夕呼】「—— 还不够！！」
【武】「我 —— 爱着纯夏！！」
【夕呼】「是正子素的光！能行！」
【武】「老师 ——」
【夕呼】「—— 鉴应该是存在于某个地方的」
—— 咦？
【夕呼】「正因为那样奇迹才会发生 …… 」

$\text{だからこそ奇跡が起きた}$

终于，回到 Alternative 的世界，00 单元已经造好，我们终于见到了 “纯夏”。

也终于看清了第一个真相......

是的，就是那缸中之脑。

纯夏一直在我们眼前，Unlimited 篇开始就一直在，明明早已有过无数次暗示，这是如此的简单的真相......

OP 里缸中之脑的特殊镜头......

在那阴森空荡的实验室里的正中央如此醒目的地方唯一的发着光的......

夕呼老师此前对纯夏的事如此明显地在撒谎说不知道......

Unlimited 篇的结局霞会抱着那个容器用纯夏的口吻说着无法离开的话......

Alternative 的开头明星作战里将最后的镜头对准着 “她”......

然而正如游戏里夕呼老师所说，你早应该发现了，只是不愿意承认吧。不止是武，也包括玩家。武在潜意识里，他不希望纯夏出现在这个 Beta 存在的残酷的世界里。而在我 (玩家) 的潜意识里，我难道真的没怀疑过那个缸中之脑会是某个人么？我难道真没怀疑过某个刚好一直找不到的人，重要的人，就是这个 “房间里的大象” 么？—— 在我亲身的游戏体验中，我真的从未想过。

在 Alternative 世界麻理茉死前，我们从未真正感受过这个存在 Beta 的世界的恶意，Unlimited 篇里我们从未直接接触过 Beta 和任何身边的人的死亡。然而实际上，那份最大的恶意，一直藏在失踪的纯夏和那闭口不谈的缸中之脑里。这个欺骗所有玩家的如此简单的诡计，不仅仅是依赖霞这枚烟雾弹，更是玩家潜意识里不愿意在一个美少女游戏中作出如此残酷的，甚至有点反人类的假设......

挚爱就在眼前，但没能鼓起勇气认出来，这份遗憾与愧疚，压在所有武和所有玩家的心头。所以最后决战的时刻，武对 00 单元纯夏最后的坦白中他说，如果再轮回一次，这一次一定会第一时间来到横滨基地的地下 19 层来找你。

与这纯粹的恶意相反，在武下定决心回来之前，万念俱灰之际读到的纯夏的日记，那是游戏中所体验到的，最纯粹的爱意。那是 Extra 的世界里我们见过的，来自青梅竹马的不加掩饰的、笨拙的、纯粹的爱。

纯夏的日记里，我们可以看到小武从小就在纯夏身边，是啊，这就是所谓的青梅竹马，形影不离，互相捉弄着，也互相关心着。在很小时候某一个圣诞夜里，两人相遇了，小武把自己礼物的一部分，一个简单的小兔子玩偶，送给了没收到礼物的寂寞的纯夏。自那以来，两人就在一起了，小武一直在生日、在圣诞节、在一些值得庆祝的日子，送着乱七八糟的小礼物给纯夏。没有哪一份礼物是贵重的，但对纯夏来说，每一份礼物都是珍贵的。与对方在一起这件事，每天晚上隔着窗户就能见到彼此这件事，以后也一定会一直在一起这件事，是如此的理所当然。

我想说，爱绝对不是也从来不是单向的、不平衡的，这也是为什么 Extra 篇里我印象最为深刻的是那个酒店的夜晚。在 Beta 存在的世界里，在横滨黑暗绝望的地下巢穴里，是小武压抑着同样恐惧的自己，鼓励着纯夏，鼓起勇气从将要带走纯夏的 Beta 手里保护她，以血肉之躯向士兵级 Beta 赤手空拳地发起挑战。

这个故事确实写的有很多很多缺点，并且作为二十多年前的作品，在后来石头门、进巨等等这些青出于蓝而胜于蓝的作品面前难免相形见绌，“Save in the name of true love” 类似这样的口号也早已不再新鲜。但它核心所传达出来的那份真爱，对我而言，跨越了二十多年时代变迁里其他优秀作品闪烁的光芒，跨越了我原本特别反感的政治立场，跨越了所有的恶趣味、虚伪与缺陷。

这个故事刻画了很多很多强烈的情感，有冥夜对武的默默守望与支持，有 207 训练小队的温暖情谊，有女武神战队的前辈们以及全人类面对 Beta 时压倒了恐惧与绝望的仇恨和勇气......

但我觉得，一个故事的内核一定是它的读者多年之后淡忘之时依然印象最为深刻的东西。Muv-Luv 的故事为什么会发生，2 个世界无数条时间线为什么会发生轮回与因果交流...... 整个漫长宏大的故事是建立在一个很小的根基上的。

多年之后，我再回忆 Muv-Luv，我觉得会让我最印象深刻的绝非那些 “宏大细致的设定、酷炫的机甲作战”...... 彼时，最有可能在我脑海中依然挥之不去的，会有可能是什么呢？

在此，我引用一位网友 OuroChival 的文章以机甲为背景，套着战争外皮的，讲述爱的故事的结尾，既作为这显而易见的答案，也作为本文的结尾。

鉴纯夏和白银武被 BETA 囚禁，白银武为了保护纯夏被士兵级分尸，自从这个世界的武死掉之后，纯夏心里便只有一个念头了：

$\text{武ちゃんに会いたい}$

那份思念何其之强，以至于在 G 弹的重力场的叠加之上竟能跨越时空，让原来的白银武来到这里

$\text{武ちゃんに会いたい}$

那份思念何其之强，以至于哪怕白银武走上了 Alternative5，与别的女性结合，没有见到纯夏，便能再次返回 10 月 22 日

$\text{武ちゃんに会いたい}$

那份思念何其之强，哪怕身上的器官被一个个摘除，无意识的纯夏依然想要见到白银武。

$\text{武ちゃんに会いたい}$

至此我们再次看到那句话

那是没被说出的另类结束。非常渺小的、非常壮大的、非常重要的、爱与勇气的童话故事

诚然，我应该说，白银武的来临不是偶然，更没有什么阴谋论，

Muv-Luv 实际上只是一个，非常渺小的，微不足道的，不值一提的故事，无论表面多大的叙事，世界观，机甲作战，其内核都是这么一个渺小的故事......

—— 那是一个名为鉴纯夏的女孩的爱的故事

さくら、もゆ（樱花，萌放）通关感想

2026-01-03T00:00:00.000Z

# 前言

我在 6 天内通关了该游戏：

2025.12.28 夜晚，我终于开始玩这个游戏，一晚上算是推完了序章，也就是 OP1 之后。
2025.12.29 夜晚，继续玩完了共通线部分，直到第一个选项。~~这一天有组会~~
2025.12.30 熬夜通关了第一条姬织线。
2025.12.31 熬夜通关了第二条千和线。
2026.1.1 一整天通关了第三条小春线。然后彻夜通宵最后一条小黑线，直到凌晨 6 点半有点怕猝死先睡觉。
2026.1.2 起床后花了 2 个小时终于通关。

第一天晚上我本来想着打到 OP 看完一遍《輪廻》就睡觉，但是没想到 OP 响起的时候，竟然并不是我期待已久的《輪廻》，然后才得知《輪廻》是 OP2。这还是我玩到的第一个有 2 个 OP 的 galgame。

我先推姬织线再推千和线，因为这似乎是 OP1 里暗示的顺序。

仅代表个人感想

我对于这个作品因为雪人语受到很多人批评的同时，看到 SCA - 自 (同样以 “樱” 作为一大主题) 的樱之诗 / 刻却在批评空间和 Bangumi (截至本文撰写时) 上远超这个作品感到极其困惑....... 素晴日也比本作品评分要略高一些......SCA - 自的掉书袋信息密度过高，漆原雪人的 “雪人语” 信息密度过低，但我觉得它们有效信息其实都一样少，不过漆原雪人写的是真正触动人心的故事，没有故弄玄虚。

# 爱、勇气、孤单、寂寞

这是一个用爱与勇气对抗孤单与寂寞的故事。

我常常看到，其他人用游戏里与游戏本身同名的歌曲 —— 被称为 “爱与勇气的赞歌”—— 来形容这个故事。这个童话风格的故事里，最大的敌人，不是 “大人” 或 “夜之王”，而是孤单与寂寞，每一个角色都在对抗着它们。这大概就是作品成功的原因了，写故事的人知道，他的读者 (我)—— 会玩这个游戏的人，就是孤单寂寞的人。

$\text{兔子太寂寞的话，会死哦}$

第一次出现【寂寞】这个词，是在魔法使的家，和魔法使姐妹以及小春一起吃饭的时候：

大家一起双手合十。
复杂的事可以边吃晚饭边聊
总之就变成现在这样了，晚饭带上了小春一起吃。
…… 那孩子 (小黑)，不在。
听说她依然呆在朝日姐为她准备的二楼房间里闭门不出。
怎么叫她也没有回应。
小黑的饭稍后由我送到她房间里吧。
看来朝日姐早已想到我和小黑会住进这个家，并且都已经做好准备。
(二楼的房间，吗)
我抬头看了看天花板。
我们在这吵吵闹闹吃饭的声音那边不可能听不到吧。
她一个人，不觉得寂寞吗？

大概就是从这里开始，读者 (我) 知道了故事里第一个寂寞的人，也是最寂寞的人，就是小黑。

# 寂寞的孩子与悲伤的孩子

“寂寞的孩子” 和 “悲伤的孩子” 的故事，是第一个悲伤氛围的感人故事，也为主角和小黑的命运最早定下了基调。

“寂寞的孩子” 是一只夜之国的猫 —— 十夜，注定无法和人类做朋友，所有人类长大后都会忘记她。孤单寂寞的她，还是一直对遇到的同样孤单寂寞的人类小朋友们给予陪伴、加油打气。

她在下雨天遇到了 “悲伤的孩子”，并治愈了她。“悲伤的孩子” 慢慢不再寂寞，但她看出了 “寂寞的孩子” 的寂寞，约好了在下一个晴天一起玩。但下一个晴天，“悲伤的孩子” 长大了，再也看不到 “寂寞的孩子” 了。

但是永远长不大的猫，依然会帮助着长大成 “大妈”“大叔” 的寂寞的人们。姐姐给她的只能用唯一一次的魔法，她决定用来帮助已经看不到她的 “悲伤的孩子”。这小小的不起眼的魔法，改变了很多人的命运：“悲伤的孩子” 走出了寂寞，有了一个儿子 —— 远矢。远矢为了帮助母亲见到被遗忘的十夜，成为了千和的 “第三位” 爸爸，也因为这一特殊身份而疏远了亲生女儿 —— 小春的妈妈。这一切，都是读者 (我) 后面才慢慢知晓的。而那个下一个晴天玩的约定，在几十年后的夜之国，也终于兑现了。

十夜要去见朋友前，大雅叮嘱十夜不要跟着奇怪的大叔走：

十夜：大叔们，真可怜啊。
大雅：欸？可怜...... 为什么？
十夜：因为，因为啊，只因为他们是大叔，就会让人觉得 “那个人说不定是个怪人啊，以防万一还是不要接近为好”，对吧？
十夜：明明对小孩子或者是女性就不会这么想。
......
十夜：所以啊，大雅。
十夜：所以总有一天会变成大叔的大雅，还是从现在开始对大叔温柔一些比较好哦，聪明的妹妹我是这么想的。
......
十夜：如果看到了寂寞的大叔的话，大雅，要对他温柔哟。
大雅：喔，喔。
十夜：这样的话，当大雅成为大叔的时候，也一定会有人对你稍微温柔一点的哦。

# 世界でいちばん優しい時間

这是一个 BGM 的名字。第一次听到它，一定是在 OP1 结束后，大雅回忆起很久以前列车上的旅途：

后来发现其实 OP1 之前就出现过这个 BGM 了，但是这个场景是最令人印象深刻的。

到站了。
下一站。
车外漫天风雪。
许许多多雪的结晶从敞开着的车门飘舞而入。
几位乘客上下车后 —— 门关上了。
一直陪伴在我身旁的那孩子也下车了。
终究是，一个人。
孤身一人啊。
即便只有我一人，我也必须要完成我的计划，我的复仇 ……
虽然，我像这样擅自想象了一下。
但是那孩子依然盯着时钟。
依然，在我身边。

是拉电闸的声音。
熄灯了。
然后，一瞬间。
在那里蔓延开来的是，
大雅：「 …… 星空？」
顶棚、厢壁、床铺，甚至座位和窗户上。
满是闪耀着绿色荧光的点和线。
好像是用只有被不可见光照射才能看得见的特殊的涂料画的，黑暗中闪闪发光。
而那些连接起来的光，又像 “星座” 一样组成了各种各样的形状。
猫的脸。
某人的笑容。
飞在空中的纸飞机。
看上去很好吃的冰淇淋。
还画着那孩子最喜欢的巧克力。

小黑用荧光笔所画的笨拙的涂鸦，是对真白稚拙的模仿。但是在小小的列车车厢里，温馨无比。

小黑：「所以啊 …… 我，也会想象我的未来哦。」
小黑：「直到你能一个人入睡 …… 我都绝对绝对，不会让你孤身一的。只有想象着这样的未来 …… 我才，睡得着哦。」
你害羞地笑了。
小黑：「 …… 呐，怎么样呢。
小黑：「这样的约定，能成为你 “魔法” 的 “咒语” …… 能成为你今天的，闪亮亮 …… 吗？」
我仰望着星空。
看着那些荧光色的亮点。
然后，我也发现了一颗，找到它了。
处处为失败。
在在皆沮丧。
事事均无进展
在如此无可救药的今天结束之时，却有一颗，闪闪发光的星星。
今后你也会一直陪伴在我身边。

看着那张侧脸
真是不可思议，我似乎觉得今天也没那么糟糕了。
因为 ……
嗯，是啊。
和你一起吃掉的巧克力，真的非常好吃。

# 世界でいちばん近い距離

大雅的视角下，很容易发现，大雅总是用第二人称称呼小黑。这是一个很特别的称呼，因为这是唯一的。大雅的视角，或许直到最后的结局之前，从未承认过小黑是特别的，但却似乎总是在意着小黑，句句不提，却又好像句句不离。

大雅和小黑走进魔法使的家之前：

大雅：小黑，抓紧我，抓哪都行。
小黑：...... 我知道了。
小黑点了点头
她伸过来的手略显犹豫...... 然后紧紧地
似乎抓住了我校服的下摆。

像是前后呼应一般，走进魔法使的家里后，大雅获得 “魔法少女” 使的能力时：

我感到一阵晕眩。
头晕眼花。
正在我想要抱住无比沉重的脑袋的时候。
......
发现小黑悄悄地，握住了我的手。
什么时候......
完全没察觉到。
大雅：小黑？
小黑：......
即便叫了她的名字，她依旧用侧脸对着我，根本不看我这边......
但是，不知何时牵着的我的手，她并没有松开。
不知不觉间，我的头晕感已经消失了。
因为有你这样陪伴在我身边，我才......
......
我反握住那只小小的手。
把那些说不出的话藏在了心里。
（要是手牵着手的时候心意也可以连接就好了......）
我这么想着，心里仿佛落下了一声叹息。

与小春白头偕老的时间线，主角死后来到夜之国：

大雅什么也不回答。
只是不停地走着。
穿过宽广的车站 ……
到达人山人海的终点。
对那样的大雅搭话也总觉得可怕 ……
大雅：「......」
我啪嗒啪嗒地跟在他的背后。
载着很多人的火车飞驰而去。只剩下我们两个人，被留在了没有人的站台上。
大雅：「......」
大雅什么也没说，只是低着头站着。
我站在那样大雅的后面，三步、四步左右的地方。我们总是有这样的距离。
再往前走一步就行了。
那样的话只要伸手就能触摸到。
但我害怕拉近那个距离。有那种看不见的距离。心里也是。身体也是。

# 缄默的孩子与黑色的猫

主角和小黑，像是对 “故事里的男主角（真正的大雅）和女主角（真白）” 的拙劣模仿。在小黑线的开头，叙事上稍微欺骗了一下读者 (我)，差点让我们以为，小黑是真白的转生什么的。而正当读者 (我) 担心故事会不会又要落于大男主、大女主的俗套时，故事又出乎意料地引出了我们真正一直看到的两位小主角 —— 在孤单和寂寞中相互依偎着的不知名的缄默的孩子和黑色的猫。他们憧憬着大雅和真白，所以黑色的猫变成了白色的人类形态，缄默的孩子变成了先前我们一直看到的能言善道的 “大雅”。

黑色的猫的某次独白：

「 …… 我没有名字，所以我想给你起个名字」
抱着我，那个孩子说 —— 虽然只有我的声音很小，但是他跟我说话了。
我很高兴那个。小黑。你这样叫我。你抚摸了我很多次。分给我同样的饭菜。
仅此而已。
是的吧？
这里再也没有什么了。
没有像真白那样在人生中寻找恋爱故事的想法，也没有把这个世界和自己的想法放在天平上进行讨论的戏剧性故事。
「所以我觉得没有什么像你们这样特别的东西。但是 …… 」
在我心中，也有能够支持重要的人的 “特别的力量”。
「 …… 」
原本以为没有什么 “才能” 的我，如果有什么 “力量” 的话
「我 …… 我希望接下来的大雅所有的时间，哪怕只有一点点也好，都能保持微笑 …… 」
但是 ……
那样的 “想法” 也是，正因为是这样的 “生物” 才会有的吧。
这么一想，为什么呢。我有点悲伤。

寻找缄默的孩子的希望的，黑色的猫，找到了那个希望：

小黑：「 …… 我那时给了你 “勇气” …… “希望” 吗？」
脑海中突然浮现出那孩子的笑容，似乎回答了我的问题。
......“人的内心是由之前被抛下的言语的颜色构成的。”

$\text{ありがとう}$

$\text{きみがこの世界に生まれてきてくれて}$

$\text{本当に}$

$\text{よかった}$

Mini OceanBase 2025

2025-11-10T00:00:00.000Z

# 参赛经历

前情提要: Mini OceanBase 2024

2025 年 10 月底，我和去年的队友再次参加了第五届 OceanBase 数据库大赛。尽管可以提前开发，但是我们都比较忙直到初赛正式开始后才开工，耗费 2 个多星期时间，在 11 月 9 日晚上终于 AK 了今年初赛的全部题目。我们是第 26 名 AK 的队伍，也是广东省的第一。

这一次比赛，我修好了很多去年的 BUG，也成功挑战了更难的题目。截至我们 AK 为止，通过率最低的 2 道那难题 full-text-index (全文索引) 和 create-view (视图) 都由我负责完成。

对于这样复杂的项目实现复杂的功能，数据结构的设计是最重要的。数据结构设计的好，写起来就会得心应手，代码也更美观。这个过程是需要也值得多花时间的，在做后面几道难题时，我思考设计数据结构的时间基本占到总的开发时间的一半。尽管如此，依然会写着写着发现设计的有问题，然后又重新设计重写数据结构和接口，有的时候会哭笑不得的发现反复重写两三次最后又回到一开始的设计或者整个被另一个设计思路取代而删掉。

# 关于 Expression

今年我发现，之前数据结构的设计存在非常糟糕的问题，既出现在子查询也出现在 Order By，这个问题就是：

$Expression$

Expression 去年也是我实现的，但去年我没有意识到 Expression 的思想的重要性，毕竟当时的我没有系统学过《编译原理》。

Expression 代表的不仅仅是简单的数学计算表达式，而是一种编程语言的设计思想。在几乎所有语言设计中都一定会用它来表示全部的右值。其实相应的，也有 “左值表达式”，那就是所有可以被赋值、被定义的东西，它当然也可以是一种表达式，只是没有那么复杂所以并不总是吸引人们的注意。这里我们讨论的 Expression 主要还是 右值表达式。

所有的编译原理课程一定会讲到 Expression 的设计，讲到他如何处理运算的优先级。而在实际写一个编译器的时候，我们总是会它用来表示：所有赋值语句的右侧、所有函数调用的传参、所有返回语句的结果...... 它无处不在。

为什么使用 Expression 后一定代码更简单、顺畅、美观？原因很简单：能很自然地复用 Expression 的逻辑和代码实现。所以 Expression 的思想归根到底还是逻辑的复用，并且同时是代码逻辑和语法解析逻辑的复用。

# Order By

去年我的 Order By 有一个愚蠢的设计失误：我把 Order By Operator 放在了 Project Operator 的上面 (根节点)。这是我当时想着 Order By 需要收集所有最终结果来完成排序时所得到的一个想当然的实现。这会导致 Order By Operator 只能拿到被投影过的 tuple，比如 SELECT A FROM t ORDER BY B 的时候就会发现 Order By Operator 根本得不到排序所需要的 B 的值。

还有一个问题就是 Expression 了，我在 ORDER BY ... 后面没有用 Expression 表示排序的 key。同样也是今年需要支持 Order By 后面允许函数才发现这个问题。这一问题比较好处理，切换成 Expression 比较简单，切换后非常顺畅就实现了新的需求。

至于 big-order-by 这道题目，是队友优化完成的，他的思路看起来投机取巧，不是外排序实现的。因为排序时所有的值都是 int 类型，所以他在检测到排序数据量很大时，把所有的 Value 都转化为 int，然后对 int 类型的数据排序，最后输出前慢慢转换回去。Value 改为 int 节省了很多内存，足以通过测评。

这看起来像是邪门歪道，但在真实的业务场景，倘若真的对海量数据排序，往往全都是对 int 类型数据比较，那么额外的抽象数据结构确实带来了大量冗余无用的内存负担，将它们优化掉是完全合理有必要的。

# 子查询

我实现的子查询没有用 Expression 表示。在今年发现 UPDATE ... SET A = B 这样的语句中 B 需要支持子查询时，我才意识到这个问题。子查询最终我也没有修正回 Expression 的设计，因为已经庞大复杂的代码迁移起来比较头疼，懒得再改了，我额外处理了一遍 UPDATE 的情况。

子查询还有一个非常需要注意的地方，那就是实际上子查询并非是只执行一次就够的，它的父级查询获取得到了多少个 tuple，它就需要执行多少次。例如如下这个 SQL 语句:

SELECT * FROM t1 WHERE t1.id IN (SELECT t2.id FROM t2 WHERE t2.id <= t1.id);

这里的子查询 (SELECT t2.id FROM t2 WHERE t2.id <= t1.id) 需要针对每一个从 t1 中获取到的 tuple 执行一次，才能得到正确的结果。所以需要注意，每一次当前查询获取到一个当前 tuple，都需要 open 一次子查询树，执行一遍子查询，完成相关操作后进行 close 。

至于父级 tuple 的信息如何向下传递给子查询呢？我的实现是基于火山模型的 next 方法创建了一个特殊的 next_with_tuple 方法，根级首次查询调用这个方法的时候放入当前自己获取到的 tuple，在经过每一级子查询语句的时候，都会把传下来的这个 tuple 上附加到子查询当前获取到的 tuple 上，这样 PredicatePhysicalOperator 等算子就能看到所有父级查询 tuple 信息了。

当然这一套本质上是编译原理的作用域，更加经典的实现是给每一级查询定义一个作用域，当前作用域找不到的继续到上一级作用域找。

# alias

在 alias 的实现中也需要开始实现类似作用域的处理，因为子查询需要可以创建遮蔽父级查询的 alias。

但是在实现子查询的时候，我在语义分析阶段并没有给每一级查询创建一个 ExpressionBinder 也就是 Field 的绑定上下文 (也就是编译原理中的变量绑定上下文)，而是把父级的上下文直接传给了子查询。所以我只好修改 ExpressionBinder 内部实现，让它区分哪些 alias 和表是父级查询的、哪些又是当前查询的。

我给表和 alias 查询表分别划分了 2 个集合来进行区分，在每次准备对子查询进行语义分析处理之前，把当前查询集合里的全部放到父级查询里就行了。而在进行绑定操作的时候，优先在当前查询的集合里找，找不到再到父级查询的集合里继续找，从而实现 “变量遮蔽” 的功能。

# union

原本的投影算子 Project 只有一个子节点，可能是 OrderBy、GroupBy、Predicate。既然 union 的几个查询列一定是相同的，那么 Project 也一定是相同的。所以我把 UNION 的所有其他查询一个接一个放到这个共同的 Project 下面，让 Project 按顺序对所有子树获取 tuple 就行了。

# 视图

在着手开始视图的开发前，我阅读参考了 2024 年同样二战 AK 入围决赛的 soulter 的博客。soulter 写的非常详细，整体思路描述的非常清晰，讲到了很多坑，他们甚至开源了自己的代码。不过我并没有看他们的代码，毕竟我都好不容易自己写了这么多题目了，为什么不全部自己写下去呢？

视图的实现思路主要是把视图的定义存储下来，然后在查询时把视图展开成对应的查询语句再执行。看上去非常简单，然而真正复杂的地方在视图的更新。今年这道题目官方给视图的更新写了详细的说明，以前还是没有的，所以去年 soulter 他自己测试了 MySQL 的视图更新逻辑和规则。

MySQL 会将视图的定义存到一个名为 INFORMATION_SCHEMA 的特殊的 DB/Schema 的一个特殊的表 VIEWS 之中，同时每一个视图本身所定义的 DB/Schema 和它所实际查询的表所在的 DB/Schema 可以是不同的，也就是视图的定义包含自己所在的 DB/Schema 这一属性。在 MiniOB，始终只有一个 DB/Schema sys ，所有的表也都放在这里面。所以简单起见我直接将视图的定义存到这个 sys 里的一个特殊的表 __VIEWS__ ，并且认为所有视图都属于这个 sys 。我将我的表 __VIEWS__ 设计如下：

	/**
	@brief 存储所有视图的特殊表
	@ +------------+------------+------+
	@ \| Field \| Type \| NULL \|
	@ +------------+------------+------+
	@ \| SCHEMA \| char (64) \| NO \|
	@ \| NAME \| char (64) \| NO \|
	@ \| ATTR_NAMES \| char (255) \| YES \|
	@ \| DEFINITION \| char (255) \| NO \|
	@ \| ID \| int \| NO \|
	@ +------------+------------+------+
	*/
	const char VIEWS_TABLE_NAME[10] = "__VIEWS__";
	const int VIEWS_TABLE_FIELD_NUM = 5;
	const AttrInfoSqlNode VIEWS_TABLE_ATTRS[5] = {
	AttrInfoSqlNode{AttrType::CHARS, "SCHEMA", 64, false},
	AttrInfoSqlNode{AttrType::CHARS, "NAME", 64, false},
	AttrInfoSqlNode{AttrType::CHARS, "ATTR_NAMES", 255, true},
	AttrInfoSqlNode{AttrType::CHARS, "DEFINITION", 255, false},
	AttrInfoSqlNode{AttrType::INTS, "ID", 4, false}
	};

由于创建视图时可以 CREATE VIEW(A, B, C, ...) AS ... 的形式重新定义查询出来的列名，所以这些 A,B,C 信息也要存到 __VIEWS__ 之中，也就是上面的 ATTR_NAMES ，我存成逗号分隔的字符串。

当然 MySQL 实际上是用 text 类型存视图的定义 SQL 语句的，然而此时我的队友 Luv 负责实现 text 还没做完，我就先用 CHARS 类型了。

那么怎么查询一个视图呢？只要能将视图视为一种特殊的表，或者说抽象的表，就能支持可能对它执行的复杂查询。soulter 的实现稍微暴力，他将需要解析的视图定义、视图名字、视图 Stmt 都放在了 SQLStageEvent 中，在处理一条 SQL 语句的每一个阶段 (语法解析 -> 语义分析 -> 优化 -> 执行)，检查有没有视图，有的话就同时也处理视图 SQL 语句，在最后的执行阶段把视图的物理执行算子拼接到对应表的扫描算子下。

我觉得这样设计有点奇怪也不够优雅，首先有一个问题就是完全没有必要每次都解析一次查询语句，在初始化视图到内存的时候解析一次就够了，后面每次复用这个解析得到的物理执行算子树，这也是我的实现思路。

在数据库初始化的时候会将磁盘上表元数据读入内存名为 Table 的数据结构，MiniOB 比较暴力直接读取所有表元数据文件将全部表读入内存，由于我们不是生产级数据库暂时不考虑内存装不下所有表、视图元数据的情况。我给 Table 加了一个成员 unique_ptr<PhysicalOperator> 类型的 query_tree_ 代表视图查询的物理执行树，以及一个简单的方法 is_view() 在这个树存在 (指针非空) 的时候返回 true 。数据库初始化的时候，也读取我的 __VIEW__ 表，解析查询语句存入 query_tree_ ，创建 Table 。

事实上还有一种思路是视图应该在语义分析阶段完成，也就是 Optimizer 里完成。将视图的展开视为一种查询语句的重写 (rewrite)，而查询语句的重写本来就是优化器需要做的事情之一，通过新增一种 Rewriter 来实现。

至于上面 soulter 的那个拼接过程是怎样的呢？如下是他的博客原文:

在 TableScanPhysicalOperator 中，需要调用 Table::get_record_scanner 获得 RecordFileScanner 对象，通过 RecordFileScanner::next(Record &record) ，以扫描表内的所有记录。 RecordFileScanner 类很复杂，但需要读取表的 Page 文件。而 View 就是个虚拟表，哪来的实体文件？诶 🤓，很简单，这时候之前存的 View 中的 operator_ 就派上用场了，我创建了一个 RecordPhysicalOperatorScanner ，它的 next 方法就是去调用这个 operator_ 物理算子。

原本扫描表的物理算子有且只有两种： TableScanPhysicalOperator 和 IndexScanPhysicalOperator ，他的实现仅处理了前者的情况，但也并没有问题，因为视图无法被创建索引，永远不会扫描视图的时候使用 IndexScanPhysicalOperator 。

我决定直接为表的扫描创建一个新的算子 ViewScanPhysicalOperator ，在生成物理执行计划的时候检查表的 is_view() 来决定使用该算子。这个算子和原来的 TableScanPhysicalOperator 没有太大差别，只需要将 open 、 next 、 close 、 current_tuple 从原本调用 RecordFileScanner 改为调用视图的 query_tree_ 作为子节点。不过注意既然选择了复用 PhysicalOperator ， query_tree_ 的所有权始终是属于其所属视图 Table 的，所以新算子存这个查询子树要存成普通指针而不是物理执行树默认的独享指针。

现在来看最复杂的视图更新，但是复杂的更新规则实际上过滤下来会发现总是只允许视图同时更新一个基表，只需要更新的时候确定是哪一个基表，然后从那个基表的 TableScanPhysicalOperator 获取 RID 就行了。

soulter 的方案如下：

最后（也是没有办法的办法），我给 cell，也就是 Value 类都加上了这两个信息，也就是直接把粒度放到了最小。

他给 tuple 的每一个 cell 也就是 Value 加上了 RID rid_ 和 string table_name_ 两个成员。这非常冗余，但是他也因此得到了另一个好处：

MYSQL 不支持同时插入多表，但我这里额外实现了这个功能。很简单，在最外层循环套一个 base_tables_ 循环，然后对每个 base_table ，根据 attr_name_2_base_table_field_name 和 field_base_table_name 找到对应的字段，创建 Value List 再进行插入操作即可。似乎不是很难，但很难理解为什么 MYSQL 不支持这个功能。

诶 🤓，你猜 MySQL 为什么不支持这个功能？因为 MySQL 没有给 tuple 的每一个 cell 加上 RID 信息。

最后我的做法则是给 PhysicalOperator 增加了一个方法 view_update_rid() ，虚类上默认实现为递归调用全部子节点的方法，在 TableScanPhysicalOperator 结束递归返回所需的 RID。当然只需要一个 RID，因为正如先前所述，更新的时候永远只会更新一个基表，只需要知道那一个表的当前 tuple 的 RID 即可。

上面的处理实际上仅在 UPDATE 的时候是需要的，其他更新操作并不需要 RID 信息。而 INSERT 的时候刚加简单，只需要在语义分析阶段也就是创建 Stmt 的时候，检查 INSERT 的字段是否来自同一个基表，否则不允许插入，是的话就记录下这个基表等到执行的时候对该表插入即可。需要注意初始化一个全为 NULL 的更新需要的 Value 列表，然后按照指定的插入字段和值填充，保证其他字段默认为 NULL。对于 DELETE，完全不允许对多基表视图操作，无需考虑。

# 全文索引

全文索引 (full-text-index) 是一道今年的新题目，实现思路主要是建立倒排索引 (Inverted Index)，将每个词语映射到包含该词语的文档列表。这样，在查询时，可以快速定位包含特定词语的文档，从而提高查询效率。

全文索引需要分词器 (tokenizer)，题目指定使用 cppjieba，应该是默认分词模式因为最后也是这样过的测评。实现分词语句比较简单，只需要创建一个二元操作 Expression 表示分词操作即可，所以我创建了 TokenizeExpr 。然后还需要输出一个疑似 CHARS VECTOR 的东西，为此我创建了一个只存在于内存中的 Value 数据类型，专门显示 vector<string> 分词结果。创建全文索引的上层实现也比较简单。

测试全文索引的语句疑似只有一种，形式如下：

	SELECT id, content, MATCH(content) AGAINST('某个Query') AS score \
	FROM texts WHERE MATCH(content) AGAINST('某个Query') > 0 \
	ORDER BY MATCH(content) AGAINST('某个Query') DESC, id ASC;

首先还是需要加一个 Expression，我叫它 MatchExpr，用来识别 MATCH(content) AGAINST('某个Query') 。

一开始，我新加了一个 OrderByPushdownRewriter 在 Order By 里出现 MatchExpr 时下沉到在 IndexScanner 那里完成排序，然后发现这样有很大问题，我完全忘记了排序后面还有一个 id ASC ，而 IndexScanner 本身设计就不应该扫描表访问 Record，所以我也不能在这里获取 tuple 计算排序的其他键值。

那要不要改到 IndexTableScanPhysicalOperator 呢？这时我就发现完全没必要下沉了，B + 树索引下沉是因为完全可以去掉排序逻辑，但倒排索引只是计算 BM25 评分，还要排序的话没必要复制一份排序逻辑到底层，我只让 IndexScanner 提供 RID 以及相应的 BM25 评分即可。

那么，我要不要像先前实现视图时候一样搞一个火山模型上递归调用的方法获取 BM25 的值呢？这样写会发现还是有个麻烦，那就是所有会对 MatchExpr 取值的地方都要我去修改逻辑。这就很不好了，这个获取 BM25 评分的操作最好能被封装到 MatchExpr 类自己的方法里，也就是 get_value(const Tuple tuple, &Value value) 。那么我只能将 BM25 信息放在每一次向上传递的 tuple 里，这样 MatchExpr 执行 get_value 的时候才能得到 BM25 信息。那么我应该像 soulter 一样在 Tuple 这个类里加一个成员吗？还有一个巧妙一点的办法是在 IndexTableScanPhysicalOperator 返回 tuple 给上层的时候加那么一个 cell 表示当前这个 RID BM25 评分。而 MatchExpr 的 get_value 方法中怎么找到这个 cell 呢？可以通过 TupleCellSpec 匹配，但这道题目不考虑 Join 操作，所以只有一个表，我就简单地把这个 BM25 加到原始 tuple 的最后面，MatchExpr 的 get_value 方法也直接从这个位置取即可。

最后我把原本的 OrderByPushdownRewriter 简单修改，不再 pushdown 而只是找到 ORDER BY 后面的 MatchExpr，存到 TableGetLogicalOperator 让其在生成物理执行计划的时候选择使用倒排索引 Index。当然，这一切都建立在整条 SQL 语句出现的 MatchExpr 始终是同一个的条件下，万一出现多种 MatchExpr，他们的 Field 和 Query 不同，那么就得对所有 Expression 做一个处理，找到所有 MatchExpr 并把他们的 Field 和 Query 往下传递，并且出现多个 Field 时，已经是 Multi Index 的情况了，太复杂我就没有再考虑。

所幸，这道题确实测试语句其实没有那么复杂，一条 SQL 语句始终只有一个 MatchExpr。我还发现系统测评实际上不会重启 observer 测试持久化，因为创建全文索引的 create 代码漏了父类 Index 的初始化，而读取表元数据文件 open 的代码没有问题，我本地脚本测试经常重启 observer 所以没发现 create 的问题，反而在官方测评里出现了...... 总之，过测评甚至不需要考虑持久化倒排索引信息，“内存数据库” 都能搞定。

不过我的实现当然还是老老实实持久化了的，由于倒排索引是 token 为键、所有包含该文档的相关信息为值的键值结构，我很自然地用一个简单的 Json 文件存储。我设计的 Json 结构如下：

	{
	"total_doc_num": 114514,
	"total_doc_len": 1919180,
	"inverted_index": {
	"我是一个token": [
	[0, 0, 350, 234],
	[0, 1, 350, 234],
	[0, 2, 350, 234]
	],
	"我是另一个token": [
	[1, 0, 123, 456],
	[1, 2, 123, 456]
	],
	}
	}

除倒排索引本身之外还有 2 个整个表统计下来的数据 total_doc_num 和 total_doc_len ，在计算 BM25 的时候需要用到。倒排索引本身以 token 为键，值为一个列表，列表包含多个四元组。每一个四元组代表一个文档，内容为 [PageNum, SlotNum, TermFreq, DocLen] ，前面 2 个共同组成一个 RID，后面 2 个则同样是是计算 BM25 的时候需要用到。

# null

最后放一个赛博案底，Value 是 4 字节的，我存成 4 个 0xEE 特殊值来表示 NULL。

什么，你问我 bitmap 是啥？我不知道。

Jabberwocky——素晴らしき日々(美好的每一天)通关感想

2025-07-09T00:00:00.000Z

# Overture

$\text{この美しくない世の中で、最も美しい童話はいつも悲しい。}$

$\text{在这不美好的世上，最美好的童话总是悲伤的。}$

$\text{——《银河铁道之夜》}$

这个游戏是我 2022 年大概 10 月到 11 月的时候玩的，也是我玩通关的第一个 Galgame。为什么是这个作品呢？在选这个作品之前，我也曾过浏览论坛和其他人写的评鉴与推荐，也听说了中文 Galgame 圈里流传的所谓 “十二神魔器”、龙骑士的寒蝉与海猫等等作品。最后，选择了这一部电波系的《素晴らしき日々》作为入坑之作，要说理由的话，并非因为它的评价有多优秀，仅仅是因为它的一首曲子 ——《夜の向日葵》。这首曲子我在高中就听过了，听着那 哀而不伤 的旋律，我一直想看看它所衬托的到底是一个怎样的故事。

序章时我还一直觉得很无聊，并且第一次玩还不太能把控速度，以致于花了一个星期才慢慢结束了序章。序章结束后，故事性变强了起来，而后两三天便玩完了全部剩下章节。那几天过的很快，当全部通关后，我还沉浸在故事的余韵里整整一周难以忘怀。

我最喜欢哪一章呢，那当然还是百合线的篇章了。柔弱的文学少女和化学少女互相扶持，SCA 自先生也很喜欢 “百合”，在《樱之诗》中同样有那么一个百合线的篇章。

至于整个故事，对当时的我而言，还是比较新奇的，而对于三年后的我而言，这个故事已经没有当年的冲击力了。序章的结尾是在致敬《银河铁道之夜》，这也是我后来才知道的。不同章节采用不同的视角，最后还有 “多重人格” 解释这一切，颇有海猫的味道。

全文中大量出现的 “掉书袋”，序章一开始时我还会认真看一看，后来我也变得不耐烦了，能跳则跳地看了。说白了全都是 SCA 自故作高深的引经据典，恐怕连他自己都不知道自己在写什么东西。他引用了大量哲学的内容，我基本都看不懂，当然也有一些理工科内容的混了进来作了一些略显门外汉的解释让我看得觉得非常可笑。当然，看着这些无意义脚本的我，岂不是同样可笑？而第二章 (卓司视角) 是最为抽象的篇章，最为狂妄的篇章，把所有的合理、所有的理性踩在脚下，坠向了虚无缥缈的终之空。

《夜の向日葵》—— 这首温柔又哀伤的曲子，就是这样一部抽象、狂妄、无意义作品的序幕曲。

# Jabberwocky

# 彷徨う鳥


ボクたちはただ名ばかりでシャボン玉の様にふくらんでしまった…… そんな空想の恋人に恋いこがれている……。さぁ、君、取りたまえ。この空想を、そして本物に変えるのは君だ。ボクは恋の嘆きとか書き散らかしたけど……、彷徨う鳥の留まるのを君は見る事が出来る人なんだ。さあ、取りたまえ。実はないだけ雄弁だと…… 君にも分かる日が来るから……。さあ、取りたまえ。
我们的情人不过是随便借个名字，用幻想吹出来的肥皂泡！…… 把信拿去吧，你可以假戏真做。我本来是无病呻吟，漫无目的地吐露爱情，现在这些飘泊无定的鸟儿有地方栖息了。你可以从信里看出来 —— 拿去吧！—— 由于不是出自真心，话就说得格外动听！

ボクたちはただ名ばかりでシャボン玉の様にふくらんでしまった…… そんな空想の恋人に恋いこがれている……。さぁ、君、取りたまえ。この空想を、そして本物に変えるのは君だ。ボクは恋の嘆きとか書き散らかしたけど……、彷徨う鳥の留まるのを君は見る事が出来る人なんだ。さあ、取りたまえ。実はないだけ雄弁だと…… 君にも分かる日が来るから……。さあ、取りたまえ。

我们的情人不过是随便借个名字，用幻想吹出来的肥皂泡！…… 把信拿去吧，你可以假戏真做。我本来是无病呻吟，漫无目的地吐露爱情，现在这些飘泊无定的鸟儿有地方栖息了。你可以从信里看出来 —— 拿去吧！—— 由于不是出自真心，话就说得格外动听！

上述片段是游戏中序章高岛引用的《Cyrano de Bergerac》(西哈诺 / 大鼻子情圣) 的片段。Cyrano 多才多艺，但是相貌丑陋 —— 有着一个令自己自卑的硕大的鼻子，却爱上了漂亮的远房表妹 Roxane，出于自卑而无法吐露爱情。Roxane 却爱上了空有英俊外表的 Christian。Cyrano 不忍 Roxane 伤心，帮助 Christian 写情书、讲情话。可以说，Roxane 爱上了一个由 Christian 的皮囊和 Cyrano 灵魂组成的幻想情人。

而之所以要节选这段话出现在游戏里，大概是因为想呼应多重人格的剧情安排 —— 高岛爱上的是卓司的外表和另一个灵魂组成的幻想情人。高岛最后追寻到自己的爱情了么？显然是没有的，她只不过是爱上了一个自己的幻想。游戏中她的视角的篇章是最压抑的，并有两个结局：一个是跳楼自尽的悲惨结局，另一个则是与橘希实香携手共进的百合结局，这也是她最幸福的结局。

“用幻想吹出来的肥皂泡” 是多么虚无缥缈、多么讽刺的描述，追求幻想中的爱情的人，多多少少都像是「彷徨う鳥」寻找一个栖息之地。在这个虚无缥缈的故事中，恋爱同样也是如此虚无缥缈之物。

# The brain is wider than the sky

SCA 自先生似乎非常喜欢 Emily Dickinson 的这首诗，它多次出现在了《素晴らしき日々》、《樱之诗》、《樱之刻》中：

The brain is wider than the sky,	我们的头脑比天空更辽阔
for put them side by side,	来，将二者对比着看一看
the one the other will contain.	我们的思维可以轻易将这片广阔的天空完全容纳
with ease and you beside.	然后…… 连你也可以
The brain is deeper than the sea,	我们的头脑比海更深.
for hold them blue to blue,	来，将蓝与蓝重叠瞧一瞧
the one the other will absorb,	我们的思维可以完全吸收大海
as sponges, buckets do.	有如海绵吸收桶里的水一般
The brain is just the weight of god,	我们的头脑正好与上帝有着相同的重量
for heft them pound to pound,	来，试试准确地量一量
and they will differ if they do,	若是有所不同，那便是
as syllable from sound.	有如语言和声响的不同

# 空気力学

$\text{我是剑客，诗人，哲学家，理学家，音乐家，也是空气力学的先驱！}$

$\text{我的大脑比这片天空更辽阔！}$

SCA 自先生似乎很向往空气动力学，序章结束时，整个《素晴らしき日々》的 OP 响起，SCA 自叫它《空气力学少女与少年之诗》。他的掉书袋中不乏维特根斯坦 —— 一位原本就读空气动力学专业的哲学家。

空气动力学是什么？是理想、是对陷入疯狂的少年和陷入绝望的少女跳楼自尽的戏谑、是对广阔无垠天空和自由飞翔的向往。

飞翔，是《素晴らしき日々》的 OP 与 ED 中常出现的关键词：

私の空気力学、飛ぶんだ、ただひたすらにね。きっと届くはずさ今。	我的空气力学，飞翔吧，一个劲地向前飞翔吧。现在，一定能够到达	OP: 空気力学少女と少年の詩
輝きを失わない空，まだ果てのない大地を，飛び続けてゆくナグルファルの船，越えて行くはず。	这永不失去光辉的星空，应该也能被仍在无边无际的大地不断翱翔的纳吉尔法之船所飞越而去	ED: ナグルファルの船上にて

讽刺的是，游戏中与空气力学最接近的事情就是跳楼了。游戏中的自杀与哲学联想起来，不难让人想起加缪的话：真正的哲学问题只有一个，那就是自杀，判断人生值不值得活，等于回答哲学的根本问题。

# 向日葵

“可是啊，不是说向日葵会一直朝太阳的方向盛开吗？朝夏天的太阳公公盛开，就像光明的象征一样。”
“向日葵并没有朝太阳盛开哦。”
“哎？是这样吗？”
“向日葵追寻太阳，是在花开之前，一旦开花了，就再也不会追着太阳了。”

上述对话节选自结局 “向日葵の坂道”，是游戏中少数对向日葵这个意向的解释之一。

SCA 自先生似乎非常喜欢向日葵，从《向日葵の教会と長い夏休み》到《夜の向日葵》，以及《樱之诗》、《樱之刻》中的向日葵画作。向日葵这个意向当然并不少见，但是 SCA 自似乎一直很喜欢，或者说玩不腻。

$\text{夜晚的向日葵，存在的理由又是什么呢？}$

$\text{命中注定要朝向阳光生长，那夜晚的向日葵们，岂不是很辛苦？}$

$\text{哈哈，总能忍过去。没有太阳，有一点点星光，一点点希望，活着，就足够了吧。}$

# Finale

其实，这个作品在今天的我看来，称不上有多优秀，也可能是时间隔的久了，很多感触都已经淡化了。在批评空间和 Bangumi 上，这依然是一个好评如潮的作品。但这个作品也一直在出圈，正在成为 —— 我这么说或许有点难听 ——“时尚单品”，当然，我自己也不喜欢这样的现象。

这个世界需要思考哲学的人，但不是所有人都适合这样的角色，我也是。但我觉得每一个人偶尔也会想要，或者说需要，在忙碌的学习工作闲暇中思考属于自己的小小的哲学，所以这样的作品还是会适合很多人。因此，对于我这种原本就对哲学没什么兴趣的读者（理工科学生），这个作品虽然并不能带来多少共鸣，但是也不会让我觉得讨厌。

或许是因为 SCA - 自想表达的东西太多了 —— 他总是想表达很多很多东西，使得《素晴らしき日々》就是这样一部乱七八糟的、抽象的、狂妄的、无意义的作品。

不条理と理不尽ばかり——穢翼のEustia(脏翅膀)通关感想

2025-07-08T00:00:00.000Z

# 一些评价

所有章节中我觉得最好的是还是序章。此时的 Tia 处境可以说极其糟糕，被卖到牢狱，还发现得了羽化病，为了活下去而故意隐瞒被黑羽袭击的目击情报，而且这不过是苟且偷生之计，没准哪一天就被 Caim 扔出去然后死在不知道什么小巷子里或被羽狩抓走...... 此时的 Tia 是名副其实的 小动物。

序章里，她的内心独白尤其令人怜悯：

ティアは思う──
思えば、わたしは石ころみたいなものだ。
自分の好きには動くことができなくて、どこに置かれるかは周りの人次第。
雨の中でも火の中でも、置かれた場所でじっと耐えなくちゃいけない。
宝石みたいに光ってたら大事にしてもらえたかもしれないけど、自分はただの汚い石ころだった。
どうして、石ころに生まれてしまったんだろう。

同时，Caim 对 Tia 却从一开始就非常的温柔，不仅仅为了获取情报，或许也出于同情，或许也出于目击到 Tia 发光留下的疑惑。这时候的 Tia 和 Caim 的关系是最为微妙的。

而后面章节的 Tia 和 Caim 的关系反而变得过于简单，Tia 依赖着 Caim，同时 Caim 照顾 Tia 寻求她身上的真相，我觉得反而不如序章有意思了，Tia 的角色塑造也显得有点单薄不够丰满，毕竟通过多个章节 Caim 的角色塑造已经非常饱满了，而 Tia 身上感觉缺少了笔墨。后面的章节里两人只有简单的约会、贴贴了，两人之间缺少 “故事” 来形成羁绊，例如序章那样 “互相欺骗” 的故事。 ~~当然也可能是我久闻脏翅膀大名，对 Tia 感情线期待太高了~~

除序章之外，我最喜欢的就是第三章，原因当然是 Collett 和 Lavria 不是亲姐妹胜于亲姐妹的复杂深厚的羁绊 ~~(百合)~~ 。最后 Lavria 替代 Collett 前去赴死，临终前弹奏起熟悉的旋律，两个少女在坠落中坦白...... 或许老套，但足够精彩。

结局的伊莲娜的复仇，让我联想到了《来自深渊》（另一个我很喜欢的作品）的黄金乡篇章，支撑整座城市的伊莲娜和化为生骇村的伊露缪伊何其相像。但是土笔给伊露缪伊添加了属于她自己的救赎，那就是和布耶可的情感故事 ~~(又是百合？)~~ 。在伊露缪伊向她为了复仇所孕育的孩子 —— 法普塔传达自己的悲惨记忆时，唯独未曾将和布耶可的回忆告诉过法普塔。脏翅膀里的伊莲娜则并没有多少笔墨刻画，仅仅是传达了一份憎恨与复仇的愿望给她同样为了复仇所孕育的孩子 ——Eustia。在我看来，这里或许还有可以提升的空间，毕竟憎恨与复仇之外的故事让法普塔原谅生骇村这一行为更加合理，同样地，在伊莲娜的故事里添加憎恨与复仇之外的故事也能让 Tia 选择拯救人类的行为更加合理，故事也更加丰满也更具荒谬感。

至于后期大量的政治过家家，尤其是王女篇章...... 反正我是能跳就跳了。总的来说其实没有我想象的那么多幼稚的政治戏，所以体验还好。

最后，最终章里 Lucius 的 “大多数人的暴政” 实在是需要吐槽一下，这个看似是符合 Lucius 人设的 “理性” 的主张，但恐怕本质上这是在以牢狱比喻日本，试图影射，抑或说是灵感来自于，日本一直以来的 “卖惨点”。现实里，牢狱真的只是个被 “大多数” 所霸凌的 “少部分” 吗？ ~~当然这只是我个人看法。~~

何其巧合的是，《穢翼の Eustia》发售之际迎来了 2011 年日本的大地震 —— 和 “Grand Fall” 相似的天灾，据说受到大地震影响物流导致游戏延迟了一个月发售。当然，日本本身就是地震多发的国家。令人寻味的是《穢翼の Eustia》成为了八月社自己也再也未曾逾越的极其优秀的作品。

# 喃喃自语

以下内容比较压抑，慎读。

世界は理不尽なことに溢れてる。

人生不如意事，十常居八九。

最近突然想玩这个作品，可能也和我的心境有关。序章一进去，就看到 Caim 的如上自述，颇有感触。这如此普通的口吻描述 “不幸”，好似家常便饭。我曾经和朋友聊到过，为什么我们要玩这种游戏？原因实在是太简单太显而易见了，那就是现实遇到了挫折，来虚拟的世界寻求慰藉罢了。当一个人 “社会化” 的时候，是不需要这些东西的。

不条理な世の中だからこそ後悔のないように生きる。

正因这个世界如此荒诞，所以想要人生不留遗憾。

临近结局时所有人实际上都知道这座城市要完蛋了，于是所有人都在追求 “不留遗憾”，看到这里我突然意识到，自己来这里观赏这个故事，不过是想看更加荒诞的世界里人们遭受更加荒诞的事情，来抚慰自己所面临的荒诞的现实。正是因为我所面临的这个现实是如此的 不条理 ，是如此的 理不尽 ，我才想要这样的故事。

救ってくれるから信じるのではなく、信じることで救われるのよ。

不是因为被拯救了才相信，而是因为相信了才被拯救。

这是 Lavria 对 Collett 说过的话。在这两位圣职者眼里，自己所信仰的究竟是什么呢？是能拯救自己的神明或天使吗？倘若不是的话，那她们所表现出来的虔诚，到底是什么？

我们只不过是想要一个理由罢了，我们只不过是想给自己的遭遇找一个慰藉罢了。宗教信仰，最初或许就是这样诞生的。

在序章里 Tia 第一次和 Caim 坦白自己的梦，说自己一定是为了什么才来到这个世界上的时候，Caim 的回答就给出了这一切的答案了 ——Tia 至今为止所遭受的一切，为什么她要作为下人被人使唤，为什么她会被卖到娼馆，为什么她会得羽化病，不过是她比较倒霉罢了，没有任何理由。她所幻想的人生的意义，并不存在。

就像这里 Caim 回答 Tia 人生意义的答案一样，就像后来 Caim 回答临终的狂犬伽尔杀人如麻的人生的意义一样，就像最后 Caim 回答自己人生经历的答案一样，这一切都没有任何理由。

可是也正如当时 Tia 回答的那样：“因为如果不这么想，自己就没有继续承受下去的动力了。”

那么最后 Tia 的人生意义存在么？她的诞生，其实是 “母亲” 为了向人类复仇的产物，荒诞，荒唐，荒谬。

最后她没有完成这个她一直在梦中听到的 “母亲” 传达的 “人生的意义”，而是拯救了这个自她诞生起便不曾温柔对待过她的世界。但她没有任何一句提过想拯救人类，她只是为了拯救在她被卖到牢狱得了羽化病最倒霉最黑暗的时候，将温柔假戏真做地对待她的 Caim。

大数据平台 All in One 搭建记录

2025-05-07T00:00:00.000Z

# 架构介绍

Hostname	IP	用户
controller (跳板机)	222.200.180.102	openstack
cpf-1 (虚拟机)	10.10.3.183	ubuntu
cpf-2 (虚拟机)	10.10.1.96	ubuntu
cpf-3 (虚拟机)	10.10.3.222	ubuntu
cpf-4 (虚拟机)	10.10.0.176	ubuntu

本文在内网环境中的 4 个节点上部署一套包含 Hadoop、Spark、Tez、Flink 的环境，文中提到的跳板机和节点如上所示。

最终搭建起的架构如图所示：(忽略其中的 zipkin, promethus, grafana 本文暂不讨论)

# Hadoop

安装兼容版本的 Java，我这里使用 Ubuntu 24.02，直接使用 apt 安装 Java 8 ：

sudo apt install openjdk-8-jre

通过 which java ，查看软链接，找到 Java 的实际安装目录，在我这里为 /usr/lib/jvm/java-8-openjdk-amd64 。

下载 Hadoop，我这里选择下载 hadoop-stable 的为 hadoop-3.4.1 。直接 wget 下载然后 tar -zxvf 解压。我下载时国内网速太慢，挂了梯子下载然后 scp 分发。

在所有节点上执行如下：

	sudo tar xzf hadoop-3.4.1.tar.gz -C /opt
	sudo ln -s /opt/hadoop-3.4.1/ /opt/hadoop
	sudo chown -R ubuntu:ubuntu /opt/hadoop
	sudo chown -R ubuntu:ubuntu /opt/hadoop-3.4.1

	sudo mkdir data
	sudo mkdir /data/hadoop
	sudo chown -R ubuntu:ubuntu /data/hadoop
	mkdir /data/hadoop/data
	mkdir /data/hadoop/name
	mkdir /data/hadoop/pid
	mkdir /data/hadoop/tmp

然后，在 /opt/hadoop/etc/hadoop 目录下，编辑配置文件：

core-site.xml :

	# Add these elements:
	## Do not forget to change the tmp directory
	<property>
	<name>fs.defaultFS</name>
	<value>hdfs://{master}:9000</value>
	</property>
	<property>
	<name>hadoop.tmp.dir</name>
	<value>/data/hadoop/tmp</value>
	</property>

hadoop-env.sh :

	# Add these commands:
	## Do not forget to change the PID directory
	export JAVA_HOME=/usr/lib/jvm/java-8-openjdk-amd64
	export HADOOP_PID_DIR=/data/hadoop/pid

hdfs-site.xml :

	# Add these elements:
	## dfs.replication property specifies replication factor, you may want to change it. I prefer replication factor of two for small clusters.
	## Do not forget to change the data directory
	## Do not forget to change the name directory
	<property>
	<name>dfs.namenode.http-address</name>
	<value>{master}:9001</value>
	</property>
	<property>
	<name>dfs.namenode.secondary.http-address</name>
	<value>{master}:9002</value>
	</property>
	<property>
	<name>dfs.webhdfs.enabled</name>
	<value>true</value>
	</property>
	<property>
	<name>dfs.replication</name>
	<value>2</value>
	</property>
	<property>
	<name>dfs.data.dir</name>
	<value>/data/hadoop/data</value>
	</property>
	<property>
	<name>dfs.name.dir</name>
	<value>/data/hadoop/name</value>
	</property>
	<property>
	<name>dfs.permission</name>
	<value>false</value>
	</property>

mapred-site.xml :

	# Add these elements:
	<property>
	<name>mapreduce.framework.name</name>
	<value>yarn</value>
	</property>
	<property>
	<name>mapreduce.application.classpath</name>
	<value>$HADOOP_MAPRED_HOME/share/hadoop/mapreduce/:$HADOOP_MAPRED_HOME/share/hadoop/mapreduce/lib/</value>
	</property>
	<property>
	<name>mapred.job.tracker</name>
	<value>{master}:54311</value>
	</property>
	# The host and port that the MapReduce job tracker runs at. If "local", then jobs are run in-process as a single map and reduce task.

workers :

	# Add the names of all workers
	cpf-2
	cpf-3
	cpf-4

yarn-site.xml :

	# Add these lines
	## You may want to change the max-disk-utilization-per-disk-percentage.
	## Notice that the value of "yarn.nodemanager.hostname" property is {worker}. We leave it for now, and will change it later
	<property>
	<name>yarn.nodemanager.aux-services</name>
	<value>mapreduce_shuffle</value>
	</property>
	<property>
	<name>yarn.nodemanager.env-whitelist</name>
	<value>JAVA_HOME,HADOOP_COMMON_HOME,HADOOP_HDFS_HOME,HADOOP_CONF_DIR,CLASSPATH_PREPEND_DISTCACHE,HADOOP_YARN_HOME,HADOOP_MAPRED_HOME</value>
	</property>
	<property>
	<name>yarn.nodemanager.disk-health-checker.max-disk-utilization-per-disk-percentage</name>
	<value>95</value>
	</property>
	<property>
	<name>yarn.resourcemanager.hostname</name>
	<value>{master}</value>
	</property>
	<property>
	<name>yarn.nodemanager.hostname</name>
	<value>{worker}</value>
	</property>

通过 sudo vim /etc/profile.d/apache-01-hadoop.sh 编辑一个 Hadoop 相关环境变量的配置文件，这个文件命名是为了在后续加载 Spark、Tez 环境变量的配置文件之前完成加载，因为后者依赖于这里的一些环境变量。

	# Java
	export JAVA_HOME=/usr/lib/jvm/java-8-openjdk-amd64
	# Haddop & YARN
	export PDSH_RCMD_TYPE=ssh
	export HADOOP_HOME=/opt/hadoop
	export HADOOP_CONF_DIR=/opt/hadoop/etc/hadoop
	export HADOOP_MAPRED_HOME=/opt/hadoop
	export HADOOP_COMMON_HOME=/opt/hadoop
	export HADOOP_HDFS_HOME=/opt/hadoop
	export HADOOP_YARN_HOME=/opt/hadoop
	export PATH=$HADOOP_HOME/bin:$PATH
	export HDFS_NAMENODE_USER="ubuntu"
	export HDFS_DATANODE_USER="ubuntu"
	export HDFS_SECONDARYNAMENODE_USER="ubuntu"
	export YARN_RESOURCEMANAGER_USER="ubuntu"
	export YARN_NODEMANAGER_USER="ubuntu"
	export LD_LIBRARY_PATH=$HADOOP_HOME/lib/native

然后就可以启动 hadoop 试试看了，常用操作如下：

	# 格式化 (清除) hdfs
	hadoop namenode -format

	# 启动 hdfs 和 yarn 集群
	/opt/hadoop/sbin/start-dfs.sh
	/opt/hadoop/sbin/start-yarn.sh

	# 停止 hdfs 和 yarn 集群
	/opt/hadoop/sbin/stop-yarn.sh
	/opt/hadoop/sbin/stop-dfs.sh

万一误操作导致 hdfs 文件系统爆了，在所有节点上执行如下脚本：

	#!/bin/bash
	rm -rf /data/hadoop/data
	rm -rf /data/hadoop/name
	rm -rf /data/hadoop/pid
	rm -rf /data/hadoop/tmp
	mkdir -p /data/hadoop/data
	mkdir -p /data/hadoop/name
	mkdir -p /data/hadoop/pid
	mkdir -p /data/hadoop/tmp

# Spark

同样首先还是在所有节点上安装二进制程序到 /opt 下：

	sudo tar xzf spark-3.4.4-bin-hadoop3.tgz -C /opt
	sudo ln -s /opt/spark-3.4.4-bin-hadoop3/ /opt/spark
	sudo chown -R ubuntu:ubuntu /opt/spark
	sudo chown -R ubuntu:ubuntu /opt/spark-3.4.4-bin-hadoop3

然后将 hadoop 的相关配置文件复制到 spark 的配置目录下：

	cp /opt/hadoop/etc/hadoop/core-site.xml /opt/spark/conf/
	cp /opt/hadoop/etc/hadoop/hdfs-site.xml /opt/spark/conf/
	cp /opt/hadoop/etc/hadoop/yarn-site.xml /opt/spark/conf/

然后，在 /opt/spark/conf 目录下，编辑配置文件：

workers :

	# 写入 worker 节点 hostname (当然不一定要复制模板)
	cpf-2
	cpf-3
	cpf-4

cp spark-env.sh.template spark-env.sh 后在 spark-env.sh 增加如下内容 :

	export JAVA_HOME=/usr/lib/jvm/java-8-openjdk-amd64
	export SPARK_HOME=/opt/spark
	export SPARK_CONF_DIR=$SPARK_HOME/conf
	export HADOOP_HOME=/opt/hadoop
	export HADOOP_CONF_DIR=$HADOOP_HOME/etc/hadoop
	export YARN_CONF_DIR=$HADOOP_HOME/etc/hadoop
	export SPARK_WORKER_DIR=/tmp/spark/work

cp log4j2.properties.template log4j2.properties 使用默认配置即可。

sudo vim /etc/profile.d/apache-02-spark.sh 配置 Spark 相关环境变量：

	export SPARK_HOME=/opt/spark
	export SPARK_CONF_DIR=$SPARK_HOME/conf
	export PATH=$SPARK_HOME/bin:$PATH

最后上传 Spark 相关 jar 文件到 HDFS：

	hdfs dfs -mkdir -p /user/spark/share/lib
	hadoop fs -put /opt/spark/jars/* /user/spark/share/lib/

# Tez

	sudo tar xzf apache-tez-0.10.5-bin.tar.gz -C /opt
	sudo ln -s /opt/apache-tez-0.10.5-bin/ /opt/tez
	sudo chown -R ubuntu:ubuntu /opt/tez
	sudo chown -R ubuntu:ubuntu /opt/apache-tez-0.10.5-bin

将解压出来的 share/tez.tar.gz 上传到 hdfs 中：

	hadoop fs -mkdir -p /apps/tez
	hadoop fs -copyFromLocal /opt/tez/share/tez.tar.gz /apps/tez/

准备一个配置文件 tez-site.xml ，在 /opt/tez/conf 目录中将有自动生成的配置文件模板，所以我们的配置文件也放在这里。这里仅配置一项即可：

	<configuration>
	<property>
	<name>tez.lib.uris</name>
	<value>${fs.defaultFS}/apps/tez/tez.tar.gz</value>
	</property>
	</configuration>

sudo vim /etc/profile.d/apache-03-tez.sh 配置 Spark 相关环境变量：

	export TEZ_HOME=/opt/tez
	export TEZ_CONF_DIR=${TEZ_HOME}/conf
	export TEZ_JARS=${TEZ_HOME}
	export HADOOP_CLASSPATH=${HADOOP_CLASSPATH}:${TEZ_CONF_DIR}:${TEZ_JARS}/:${TEZ_JARS}/lib/

# Flink

Flink on YARN 支持如下几种模式：

Session 模式，先将 Flink 集群作为一个作业提交给 YARN 来启动集群，然后再提交作业，且后续提交的作业共享 Flink 集群的资源。
- Attached 模式，顾名思义前台运行；
- Dettached 模式，顾名思义后台运行；
Application 模式，直接提交作业。提交后在 YARN 上启动一个 Flink 集群，应用程序 jar 的 main() 方法将在 YARN 中的 JobManager 上执行。应用程序一完成，集群就会关闭。

接下来部署一个 Dettached Session 模式的 Flink 集群，这将同时提供一个 Web UI 供提交监控 Flink 作业。

首先还是在所有节点上安装二进制程序到 /opt 下：

	sudo tar xzf flink-2.0.0.tar.gz -C /opt
	sudo ln -s /opt/flink-2.0.0/ /opt/flink
	sudo chown -R ubuntu:ubuntu /opt/flink
	sudo chown -R ubuntu:ubuntu /opt/flink-2.0.0

然后修改配置文件 /opt/flink/conf/config.yaml ，指定 Flink 版本所兼容的 Java 版本，例如这里 Flink 2.0.0 需要 Java 17+ 版本，我将其指定为 apt 安装的 Java 17 安装路径：

	env:
	java:
	home: /usr/lib/jvm/java-17-openjdk-amd64
	#
	# ......
	#
	rest:
	port: xxxxx # 绑定 Web UI 到指定端口

上面配置修改了 rest.port 绑定 Web UI 端口，因为默认的 8081 端口已经被 Hadoop 和 YARN 占用了，避免每次启动都是随机端口。尽管如此，还是无法绑定到指定 address 上，因为提交 Flink 集群后，前端分配到哪个节点是不确定的，只能在启动后确定。

但是，我们的 Hadoop 和 YARN 依然依赖于 Java 8 所以当前环境变量 JAVA_HOME 指向的 Java 路径是 Java 8 的，并且 Flink 也依赖于这个环境变量！所以即使加了上面的配置启动集群时还是会有 Java 版本不兼容的报错。所以只好启动的时候指定一个高版本 Java 路径：

JAVA_HOME=/usr/lib/jvm/java-17-openjdk-amd64 ./bin/yarn-session.sh -d

然后会输出 Web UI 的访问方式，以及 Flink 集群的 application id 用于停止集群。当然，YARN 面板上随时可以查到这个 Flink 集群的 application id，所以并不一定需要记下它。

当然，停止集群的时候也要指定 Java 路径：

echo "stop" | JAVA_HOME=/usr/lib/jvm/java-17-openjdk-amd64 ./bin/yarn-session.sh -id <application_id>

但是接下来还有可能遇到一个问题导致提交的作业永远无法顺利执行，就是资源限制问题。和 Spark 和 Tez 不太一样，Flink 需要一个作业作为 Flink 集群，若我们使用同一个用户启动 Flink 集群，再提交其他非 Flink 作业时可能会发现作业卡住永远没有进展，是因为当前用户 AM 资源上限被 Flink 集群这个作业占完了。似乎能修改配置解决，有比较好的解决方案了后续再补上...

# 访问内网环境

在 ~/.ssh/config 中添加如下配置：

Host hadoop-tunnel
  HostName 222.200.180.102
  User openstack
  # HDFS Web UI (namenode)
  LocalForward 9870 10.10.3.183:9870
  # HDFS Web UI (secondary namenode)
  LocalForward 9868 10.10.3.183:9868
  # YARN Web UI
  LocalForward 8088 10.10.3.183:8088
  LocalForward 8042 10.10.1.96:8042
  LocalForward 8043 10.10.3.222:8042
  LocalForward 8044 10.10.0.176:8042
  # zipkin Web UI
  LocalForward 9411 10.10.3.183:9411
  # JobHistory Web UI
  LocalForward 19888 10.10.3.183:19888
  # Promethues Web UI
  LocalForward 9090 10.10.3.183:9090
  # Node_Exporter Web UI
  LocalForward 9100 10.10.3.183:9100
  LocalForward 9200 10.10.1.96:9100
  LocalForward 9300 10.10.3.222:9100
  LocalForward 9400 10.10.0.176:9100
  # Grafana Web UI 监控可视化
  LocalForward 3000 10.10.3.183:3000

Host cpf-1
  HostName 10.10.3.183
  User ubuntu
  ProxyCommand ssh -W %h:%p hadoop-tunnel

Host cpf-2
  HostName 10.10.1.96
  User ubuntu
  ProxyCommand ssh -W %h:%p hadoop-tunnel

Host cpf-3
  HostName 10.10.3.222
  User ubuntu
  ProxyCommand ssh -W %h:%p hadoop-tunnel

Host cpf-4
  HostName 10.10.0.176
  User ubuntu
  ProxyCommand ssh -W %h:%p hadoop-tunnel

基于上述配置：

	ssh -N hadoop-tunnel # 会挂着转发全部 Web 应用
	ssh hadoop-tunnel # 登录跳板机，顺便转发全部 Web 应用
	ssh cpf-1 # 登录虚拟机

# 提交任务

除了 Flink 都需要连接到虚拟机上提交。

# Spark

需要通过 spark-submit 来提交。

由于是 Spark on YARN 的部署方式，提交的任务中，SparkSession 需要增加一项配置 .config("spark.hadoop.fs.defaultFS", "hdfs://cpf-1:9000") 来指定使用 YARN 和 hadoop，并且在提交时指定 --master yarn --deploy-mode cluster 。

	spark-submit
	--master yarn \
	--deploy-mode cluster \
	xxxApp

使用 Spot 追踪，假设追踪后端为 zipkin 并且部署在 http://cpf-1:9411，需要增加：

	spark-submit
	--jars spot-complete-3.5_2.12-0.1.1.jar \
	--conf spark.extraListeners=com.xebia.data.spot.TelemetrySparkListener \
	--conf spark.otel.traces.exporter=zipkin \
	--conf spark.otel.exporter.zipkin.endpoint=http://cpf-1:9411/api/v2/spans \
	xxxApp

这里的 spot-complete-3.5_2.12-x.x.x.jar 从这个 fork 的 CI (build) 下载，因为原项目仓库依赖缺少 opentelemetry-exporter-zipkin 会导致用 zipkin 测试失败。

python 测试为例如下：

	from pyspark.sql import SparkSession

	spark = SparkSession\
	.builder\
	.config("spark.hadoop.fs.defaultFS", "hdfs://cpf-1:9000")\
	.appName("test01")\
	.getOrCreate()

	def get_python_version(_):
	import sys
	print("Python version:", sys.version)

	def get_packages(_):
	import pkg_resources
	print({pkg.key: pkg.version for pkg in pkg_resources.working_set})

	# Driver 端的 Python 版本
	get_python_version(114)

	# Executor 端的 Python 版本
	spark.sparkContext.parallelize([1], 1).map(get_python_version).collect()

	# 列出所有 Driver 端的包名
	get_packages(514)

	# 列出所有 Executor 端的包名
	spark.sparkContext.parallelize([1], 1).map(get_packages).collect()

	spark.stop()

提交测试并追踪：

	spark-submit \
	--master yarn \
	--deploy-mode cluster \
	--jars spot-complete-3.5_2.12-0.1.1.jar \
	--conf spark.extraListeners=com.xebia.data.spot.TelemetrySparkListener \
	--conf spark.otel.traces.exporter=zipkin \
	--conf spark.otel.exporter.zipkin.endpoint=http://cpf-1:9411/api/v2/spans \
	test.py

# Flink

可以直接通过 Web UI 提交，也可以登陆虚拟机通过指令提交，只是提交时必须指定 JAVA_HOME （默认的 JAVA_HOME 是给 hadoop 和 yarn 用的 java 8）：

	JAVA_HOME=/usr/lib/jvm/java-17-openjdk-amd64 \
	/opt/flink/bin/flink run \
	/opt/flink/examples/streaming/TopSpeedWindowing.jar

# Tez

虚拟机上通过指令按照普通的 MapReduce 任务提交即可，例如：

	hadoop \
	jar tez-examples-0.10.5.jar \
	orderedwordcount \
	/tmp/test/wordcount-input \
	/tmp/test/wordcount-output

Mini OceanBase 2024

2025-01-20T00:00:00.000Z

# 参赛经历

感谢 Luv 拉我过来参加这个比赛。我和他以及一位他的学弟组队参赛，我们的队伍名字叫做 神雕侠侣 (Luv 起的名，不知道是不是因为拉我来之前它们队伍只有两个人的原因)。拉我来的时候距离初赛结束还有 2 周时间，几位队友都花了不少时间，我中途掉线了 4 天去完成密码学实验的手搓大数库去了，感觉非常可惜，如果我多在线这 4 天，虽然还是进不了决赛，或许还能摸一个省奖走。

当然这个比赛为什么我们那么难进决赛，一个根本原因还是赛题都是承接往年的题，平时也可以通过 “训练营” 做题，最终进入决赛的队伍大部分都 AK 了，想必都是有以前的基础，而我们则没法在这么短时间内，又要应付课程和作业又要做出这么多题。我相信我们第二年再参赛应该能拿捏并弥补遗憾的。

有几道题我还是基本做出来的，比如 null、子查询、复杂子查询的实现，虽然 null 我的实现并不正确，但这些都还遇到了各种问题没来得及 debug 完。实际上我的排序实现也不正确，我还是用了内排序做的，在真正的大数据排序下估计是要爆内存的，我们就遇到过忘了删掉 LOG_DEBUG 提交然后爆内存。（但是测评用的数据似乎并不是特别多）

分工协作做不同题目，虽然个人完成的题目提交评测没有问题，但是 merge 之后经常遇到不兼容的问题，需要不断的排查。我印象最深的是，我实现的子查询和 Luv 实现的 update-mvcc 不兼容，折磨了好久。

尽管如此，我非常享受这一次比赛，我对数据库的实现、运行有了深刻的理解。我在专业课程上所学的《数据库系统原理》是偏理论的，而且说实话讲的并没有多好 ~~(考试和给分还一坨真的是烂中烂)~~ 。真正上手去做一个数据库，才是我眼中更加理想的学习过程。Mini Oceanbase 在这一点上非常适合学习使用，它是为数据库初学者设计的，让学习者体验从底层开始的完整实现，麻雀虽小五脏俱全，没有工业生产级别数据库那么庞大复杂以及高性能，但是有一个真实数据库完整且规范的实现。

# MiniOB 架构

MiniOB 用 C++ 实现，采用面向对象风格。下图中，左侧为不同阶段处理器对象，右侧为该阶段下所处理的结果对象。

	┌──────────────────┐ ┌──────────────────┐
	│ SQL │ ---> │ String │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Parser │ ---> │ ParsedSqlNode │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Resolver │ ---> │ Statement │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Transformer │ ---> │ LogicalOperator │
	└────────┬─────────┘ │ PhysicalOperator │
	│ │ or │
	┌────────▼─────────┐ │ CommandExecutor │
	│ Optimizer │ ---> │ │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Executor │ ---> │ SqlResult │
	└──────────────────┘ └──────────────────┘

# SQL 解析

任何输入的 SQL 语句都是一条字符串，解析的任务是将这样一条机器无法理解的字符串最终转化为机器可理解的数据结构形式的节点 ParsedNode 。解析的过程分为词法解析和语法解析：

词法解析：负责匹配不同的关键词，例如 SELECT , WHERE ...... 这样的词，以及剩余其他的字符串、数值或日期字面量。这些都被匹配为对应的 token 供语法解析使用
语法解析：有了匹配出来的各种 token，就可以定义这些 token 如何排列组合能够得到一条 SQL 语句，并构造出一个 ParsedNode 作为返回结果，这个 ParsedNode 数据结构应当包含这个查询所需的所有数据和条件

特别注意的是，语法解析涉及大量经典的递归语法，需要准确定义递归和递归边界。例如子查询、 JOIN 连接、 WHERE 后的条件等等。

# 词法分析

MiniOB 使用词法分析工具 flex

# 语法分析

MiniOB 使用语法分析工具 bison

语法解析时，会定义一些不同类型的字面量，包括数值、日期、字符串，可以说字符串以外的字面量都是正则表达式定义的特殊的字符串。

同时还有一种类型 Attribute 也就是表的属性，表的属性定义为两种：带表名的和不带表名的。

在语法解析的时候，我们还定义一种特殊的结构： Expression 或者说表达式。它就是 SELECT 后以及 WHERE 后会出现的，字面量以及 Attribute 参与的的运算表达式。

# Statement

缩写为 stmt ，接下来都这么简称它。

在得到 ParsedNode 之后，还需要进一步将其转化为 Stmt ，这个过程被称为 Resolve 阶段。通常在 Resolve 阶段会校验 SQL 语法树的合法性，比如查询的表是否存在，运算类型是否正确。

实际上， ParsedNode 已经是树的结构了，但不一定是合法的树，Resolve 阶段得到的 Stmt 则一定是合法的树结构。

同时，这一步还会进行绑定操作，从 FROM 后面得到一系列表，将每一个语句中出现的 Attribute 尝试在这些表中绑定，当然如果绑定失败，那就是查询语句不合法，包括：

FROM 后有多个表有相同名字的属性，这个名字的属性 Attribute 出现了但没有指定表名，无法确定该绑定哪一个
属性 Attribute 不在任何一个 FROM 后的表中

绑定的 Attribute 不仅出现在 SELECT 后面，还会出现在任何 Expression 中，也就是出现在任何 SELECT 后以及 WHERE 后会出现的 Expression 中。

# 执行模型

在理解 Logical Operator 和 Physical Operator 的工作过程之前，必须先了解数据库实现的经典模型：火山模型以及它的并行向量化版本。

# 火山模型

构建一颗树的结构，每一个节点被称为 Operator ，采用面向对象的设计，这些 Operator 都实现如下几个方法：

open() ，相当于初始化，只在刚开始执行一次
next() ，由上层反复调用，直到执行失败，表示不再有更多 tuple
tuple() ，每次 next() 执行成功，则也执行这个方法，将得到一个 tuple
close() ，最后结束，从上到下依次关闭，保证所有叶子结点关闭对相应数据的访问

注意这些方法都是迭代执行的，上一层调用下一层的方法，下一层将继续调用在下一层同样的方法。

这里说的当然无论是逻辑还是物理的 Operator 都是抽象类，在底下将实现不同的继承类，作为执行计划树上的不同节点。

	┌──Volcano iteration model─┐
	│ ┌───────────┐ │
	│ │ │ │
	│ │ operator1 │ │
	│ │ │ │
	│ └──┬────▲───┘ │
	│ next()│ │ │
	│ tuple()│ │ tuple │
	│ ┌──▼────┴───┐ │
	│ │ │ │
	│ │ operator2 │ │
	│ │ │ │
	│ └──┬────▲───┘ │
	│ next()│ │ │
	│ tuple()│ │ tuple │
	│ ┌──▼────┴───┐ │
	│ │ │ │
	│ │ operator3 │ │
	│ │ │ │
	│ └───────────┘ │
	└──────────────────────────┘

# 向量化执行模型

和火山模型执行过程完全一致，但是每一次是以 chunk 或者说 batch 为单位向量化执行，有点像现代处理器的向量指令，可以并行化加速。由于我在比赛中没有实现这个模型，并没有特别了解。

	┌─────── Vectorization model ──────┐
	│ ┌───────────┐ │
	│ │ │ │
	│ │ operator1 │ │
	│ │ │ │
	│ └─┬─────▲───┘ │
	│ next()│ │ │
	│next_chunk()│ │ chunk/batch │
	│ ┌─▼─────┴───┐ │
	│ │ │ │
	│ │ operator2 │ │
	│ │ │ │
	│ └─┬─────▲───┘ │
	│ next()│ │ │
	│next_chunk()│ │ chunk/batch │
	│ ┌─▼─────┴───┐ │
	│ │ │ │
	│ │ operator3 │ │
	│ │ │ │
	│ └───────────┘ │
	└──────────────────────────────────┘

# Logical Operator

这个过程也就是生成逻辑执行计划，就是将 Stmt 的树组装为 LogicalOperator 的树。在面向对象的设计中，这一步由 Logical Plan Generator 完成。

LogicalOperator 的树已经和 PhysicalOperator 在结构上基本一致了，只是它并没有真的实现 open() ， next() ， tuple() 和 close() 。

一颗 SQL 的 Operator 树具有如下通用泛化结构：

	Project/Insert/Delete/Update
	\|
	[OrderBy]
	\|
	[GroupBy]
	\|
	Predict
	\|
	Join
	/ \
	TableScan Join
	/ \
	TableScan ......

其中有一些是可选的，例如 GroupBy。另外，Join 的执行可以看出其实是迭代进行的，每一次都是两个表之间进行。而 TableScan 的实现也有向量化版本，而且这个 Operator 在逻辑计划和物理计划中名字不太一样，实际上它在逻辑计划中还可以叫做 TableGet Operator，这样的叶子节点是整个执行过程中真正从数据库的 record 获取 tuple 的地方。

在构建完这样一颗树之后，将会开始优化。分为两种优化：

先对 Expression 优化，将不依赖于 Attribute 的表达式直接计算出来
然后是 Operator 树的优化，但是 MiniOB 中并没有实现这一方面的优化，本文不再考虑。实际上这种优化就是尽可能将 Predict 拆开、放在 Join 的子孙节点，节省 Join 开销。

第一种优化也叫做 Rewrite，在面向对象的设计中由 Rewriter 完成。我们对每一种 Expression 事先定义好一些列优化规则，叫做 Simplification Rule。于是优化过程就是如下伪代码：

	auto rewrite = [] (oper, &dirty) {
	for (oper : 当前 Operator 的子节点) {
	for (expr : oper 的所有表达式) {
	if (expr 是可优化表达式) {
	for (rule : 这个表达式类型的所有 Simplification Rule) {
	尝试应用规则
	if (应用规则成功简化表达式) {
	dirty = true;
	}
	}
	}
	}
	rewrite(oper, dirty);
	}
	}

	bool dirty = false;
	do {
	rewrite(根节点, dirty);
	} while ( dirty );

# Physical Operator

最后，优化完的逻辑执行计划被转化为物理执行计划，在面向对象的设计中，这一步由 Physical Plan Generator 完成。优化完的 Logical Operator 树直接每个节点对应转化就可以。

这里着重的关注点就是不同 Operator 的 open() ， next() ， tuple() 和 close() 四个方法了，它们决定了每个 Operator 节点扮演什么角色以及如何工作。

# Predicate

起到条件判断或者说过滤作用的 Predict Operator，它的 next() 和 tuple() 就会是如下的逻辑：

	void next () {
	do {
	子节点.next();
	当前 tuple = 子节点.tuple();
	} while (当前 tuple 不满足条件);
	}

	Tuple tuple () {
	return 子节点.tuple();
	}

# Groupby

GroupBy 有两种情况的实现被划分为了物理执行计划中的两种节点：

ScalarGroupByPhysicalOperator ，聚合目标只有一个，或者说 SELECT 后面只有一个表达式。它的实现方式相对简单，逐条处理数据进行分组和聚合操作。
HashGroupByPhysicalOperator ，聚合目标有多个，或者说 SELECT 后面有多个表达式。基于哈希表来实现不同分组的聚合。

执行聚合操作就和上面 Predict Operator 的原理很像，只不过他是在 open() 的时候就迭代完了所有子孙节点的 tuple，在迭代过程不断更新每一个 group 的聚合结果 (当然对于 Scalar 只有一个 group)。在面向对象的程序实现过程，聚合的过程由这样一个类来实现：

	class Aggregator
	{
	public:
	virtual ~Aggregator() = default;

	virtual RC accumulate(const Value &value) = 0;
	virtual RC evaluate(Value &result) = 0;

	protected:
	Value value_;
	};

open() 中每次迭代都执行一次 accumulate() ，当在 next() 和 tuple() 迭代阶段则每次 next() 成功后，执行一次 evaluate 返回聚合结果。

和 Operator 一样，这里的 Aggregator 也是抽象类，依据五种聚合函数得到五种继承类：

AvgAggregator
CountAggregator
MinAggregator
MaxAggregator
SumAggregator

# Orderby

Orderby 的情况和先前两种都不一样，因为 Predicate 和 Groupby 实际上都仅需一个一个扫描 tuple，不需要一次性全读入内存。但是排序是需要考虑读多少进入内存的，也就是所谓的 外排序 的情况。

如果还是内排序那一套来实现，就和聚合类似，在 open() 阶段就完成排序即可，排序结果一个一个返回给上一层 Operator。但是正如我在本文开头讲的那样，终究是有爆内存的问题的。

那么该如何实现外排序呢？这个问题我当时没考虑到，而且当时存储模块主要由队友 Luv 负责，我也尚不清楚如何利用内存、存储实现外排序。

# 子查询

子查询的实现，需要在 语法解析 阶段就建立 ParsedNode 的迭代的树结构。然后在此后的 Stmt ， LogicalOperator ， PhysicalOperator 阶段都传递并保持这样的树结构。只有这样才能实现递归执行的效果。

这个过程还牵扯到了一些比较复杂的语法判断问题，尤其是 Attribute 的绑定，给 Resolve 阶段带来了不小的麻烦。

而在物理执行计划，和上面两种情况仍然一样，注意子查询作为 WHERE 后的一种条件判断，需要将子查询的 Operator 子树放在 Predicate 节点的子节点。在 open() 阶段完成整个子查询，上层的 Predicate 每次通过 next() 和 tuple() 拿到一个 tuple。

# Reference

Documentation of MiniOB

Pollard-Rho

2024-12-19T00:00:00.000Z

# 大数运算

大数运算实现先前的实验报告已经有过，不再赘述。

但是在 Pollard-Rho 中有大数的模 3 运算，在先前的大数库中没有实现。这里再在 Field::Int 类中增加模 3 运算的方法：

cpp

	int mod3() const {
	__uint128_t res = 0;
	for(int i = F.N - 1;i >= 0; i--){
	res = (res * (static_cast<__uint128_t>(1) << 64) + a[i]) % 3;
	}
	return static_cast<int> (res);
	}

# 大数字符串输入输出处理

本次实验不像先前的实验都是二进制输入输出，而是十进制字符串输入输出。

对于输出，由于输出的离散对数是有限域 $n$ 以内的，而 $n$ 在本次实验限定为 64 位以内，所以可以直接使用 C++ 本身自带的 64 位数输出。

对于输入，包含了大数，我在自己的大数库已经有实现，为了更高效的性能，我使用查表的方式实现。我的大数库最高支持 2048 bits 的大数，使用 uint64_t[32] 存储，对应到十进制是 618 位，所以建立的 LookUpTable 可以以 618 个十进制位、1 到 9 这 9 个十进制数作为索引，查询结果就是对应的大数的二进制表示。建表如下：

cpp

	auto gen_TABLE(){
	array<array<array<uint64_t, 32>, 9>, 617> table = {0};
	uint64_t a[32] = {0};
	uint64_t a1[32] = {0};
	a[0] = 1;
	for(int i = 0; i < 617; ++i){
	for(int j = 0; j < 32; ++j){
	a1[j] = a[j];
	}
	int t = i == 616 ? 3 : 9;
	for(int j = 0; j < t; ++j){
	uint64_t carry = 0;
	for (int k = 0; k < 32; ++k) {
	table[i][j][k] = a[k];
	uint64_t sum = a[k] + a1[k] + carry;
	if (sum < a[k] \|\| sum < a1[k]) {
	carry = 1;
	} else {
	carry = 0;
	}
	a[k] = sum;
	}
	}
	}
	return table;
	}

这里我之所以使用 array<array<array<uint64_t, 32>, 9>, 617> 存表，是因为我原本希望在编译时 constexpr 建表，提升运行效率，但是在 OJ 系统上会导致超出编译内存。

cpp

	/*
	not in constexpr, bcz adding it will exceed memory limit on OJ system.
	*/
	const auto TABLE = gen_TABLE();

输入就通过查表实现，根据输入的每一个十进制位查刚刚建立的表，查询结果加到最终结果之中：

cpp

	// return the sum of used limbs
	inline int string2limbs(const string& s, uint64_t * a){
	int l = s.length(), k = 1;
	bool flag = l > 19;
	a[0] = stoull(
	s.substr(
	flag ? l - 19 : 0,
	flag ? 19 : l
	)
	);
	for (int i = 19; i < l; ++i) {
	int j = s[l - i - 1] - '0';
	if(j == 0) continue;
	uint64_t sum, carry = 0;
	k = 0;
	j--;
	while(TABLE[i][j][k] == 0)k++;
	while(k < 32 && (TABLE[i][j][k] != 0 \|\| carry != 0)){
	sum = a[k] + TABLE[i][j][k] + carry;
	if (sum < a[k] + carry \|\| sum < TABLE[i][j][k] + carry) {
	carry = 1;
	} else {
	carry = 0;
	}
	a[k] = sum;
	k++;
	}
	}
	return k;
	}

我的大数库采用面向对象的设计，所以输入也封装到了友元 >> 之中：

cpp

	// 输入有限域（p）
	inline friend std::istream& operator>>(std::istream& is, Field& f) {
	string s;
	is >> s;
	f.N = string2limbs(s, p);
	initField(f.p, f.p_2, f.R2modp, f.g, f.N); // 有限域预计算处理
	return is;
	}

	// 输入整数
	inline friend std::istream& operator>>(std::istream& is, Int& a) {
	string s;
	is >> s;
	string2limbs(s, a.a);
	return is;
	}

# Pollard-Rho

Pollard-Rho 的算法我也采用了面向对象的设计，将一个 DLP 问题的条件作为成员变量封装在里面：

$p$ 定义在 Field f ，同时也是整个 Pollard-Rho 算法大数运算时所基于的有限域。
uint64_t n 即为 $n$ ，因为输入限制在 64 位以内，所以不必使用大数。
Int alpha = Int(f) 即为 $\alpha$ ，属于有限域 $p$ 。
Int beta = Int(f) 即为 $\beta$ ，属于有限域 $p$ 。

cpp

	class PollardRho {
	public:
	PollardRho(){};

	private:
	void func(Int const & x, __uint128_t const & a, __uint128_t const & b, Int & x_, __uint128_t & a_, __uint128_t & b_);

	void func(Int & x, __uint128_t & a, __uint128_t & b);

	__uint128_t gcd(__uint128_t a, __uint128_t b); // 返回 a,b 的 gcd

	__uint128_t mod_inverse(__uint128_t a, __uint128_t p); // 返回 a^(-1) mod p

	// 值为 1 的大数
	string _One = string("1");
	const Int One = Int(f, _One);

	public:
	Field f;
	Int alpha = Int(f);
	Int beta = Int(f);
	uint64_t n;

	uint64_t solve();
	}

具体的算法流程如下：

$\begin{aligned} &(x1,a1,b1)\gets f(1,0,0)\\ &(x2,a2,b2)\gets f(x1,a1,b1)\\ &\bold{\text{while}}\ x1\neq x2\\ &\ \ \ \ (x1,a1,b1)\gets f(x1,a1,b1)\\ &\ \ \ \ (x2,a2,b2)\gets f(x2,a2,b2)\\ &\ \ \ \ (x2,a2,b2)\gets f(x2,a2,b2)\\ &\text{解线性同余方程:}\\ &\ \ \ \ (b2-b1)x=a1-a2\ \ \ \ (\bmod n) \end{aligned}$

其中 $f$ 的计算如下：

$f(x,a,b)= \begin{cases} (\beta x ,& a,& (b+1)\bmod n &), && x\bmod3=1\\ (x^2 ,& 2a ,& 2b\bmod n &), && x\bmod3=0\\ (\alpha x ,& (a+1)\bmod n ,& b &), && x\bmod3=2 \end{cases}$

这里我对输入和输出是否为为同一变量分别作了实现避免 C++ 未定义行为（我真的怕极了，不想在遇到 undefined behavior 了）：

cpp

	void func(Int const & x, __uint128_t const & a, __uint128_t const & b, Int & x_, __uint128_t & a_, __uint128_t & b_){
	switch(x.mod3()){
	case 1: {
	x_ = beta * x;
	a_ = a;
	b_ = (b + 1) % n;
	} break;
	case 0: {
	x_ = x * x;
	a_ = (a * 2) % n;
	b_ = (b * 2) % n;
	} break;
	default: { // 2
	x_ = alpha * x;
	a_ = (a + 1) % n;
	b_ = b;
	}
	}
	}

	void func(Int & x, __uint128_t & a, __uint128_t & b){
	switch(x.mod3()){
	case 1: {
	x = beta * x;
	a = a;
	b = (b + 1) % n;
	} break;
	case 0: {
	x = x * x;
	a = (a * 2) % n;
	b = (b * 2) % n;
	} break;
	default: { // 2
	x = alpha * x;
	a = (a + 1) % n;
	b = b;
	}
	}
	}

然后求最终 $b1,b2,a1,a2$ 的过程如下：

cpp

	uint64_t solve(){
	Int x1(f), x2(f);
	__uint128_t a1, b1, a2, b2;
	func(One, 0, 0, x1, a1, b1);
	func(x1, a1, b1, x2, a2, b2);
	while(x1 != x2){
	func(x1, a1, b1);
	func(x2, a2, b2);
	func(x2, a2, b2);
	}
	// 解线性同余方程...
	}

最后就是求解线性同余方程了，主要参考 OIWiki 中用逆元求解的思路，这里我的方程如下：

$(b2-b1)x=a1-a2\ \ \ \ (\bmod n)$

当然这里我先要保证 $b2-b1$ 和 $a1-a2$ 都是模 $n$ 下的正数，上述 Pollard-Rho 得到的结果并不保证 $b2>b1$ 和 $a1>a2$ ，所以稍微处理一下：

cpp

	while(b2 < b1) b2 += static_cast<__uint128_t>(n);
	while(a1 < a2) a1 += static_cast<__uint128_t>(n);

接下来先求 $g=gcd(b1-b2,n)$ ，通过如下函数实现：

cpp

	__uint128_t gcd(__uint128_t a, __uint128_t b){
	while (b != 0) {
	__uint128_t temp = b;
	b = a % b;
	a = temp;
	}
	return a;
	}

当且仅当 $(b2-b1)\bmod g\neq0$ 时是无解的，反之则可以在 $(b2-b1)x=a1-a2$ 两侧同时除以 $g$ ，得到新方程：

$b'x'=a'\ \ \ \ (\bmod n')\ \ \ \ \begin{cases} b'=(b2-b1)\div g\\ a'=(a1-a2)\div g\\ n'=n\div g\\ \end{cases}$

就可以通过求逆得到一个基础解 $x'=a'\cdot b'^{-1}\bmod n$ 。求逆代码实现如下：

cpp

	__uint128_t mod_inverse(__uint128_t a, __uint128_t p) {
	__uint128_t u = a, v = p, x1 = 1, x2 = 0, q, r, x;
	while(u != 1){
	q = v / u;
	r = v - q * u;
	while(x2 < q * x1) x2 += p;
	x = x2 - q * x1;
	v = u;
	u = r;
	x2 = x1;
	x1 = x;
	}
	return x1 % p;
	}

但这个解不一定是 DLP 的解，因为线性同余方程有 $g=gcd(b1-b2,n)$ 个解，只有一个才是我们想要的，那就只好尝试 $g$ 次试出最终解了，这 $g$ 个解通过 $x'$ 构造如下：

$x_i=(x'+i\cdot n')\bmod n\ ,\ \ \ 0\leq i\lt g$

最终求解原方程代码如下：

cpp

	if ((b2 - b1) % g != 0){
	// 无解
	} else {
	__uint128_t n_ = n / g;
	__uint128_t a_ = (a1 - a2) / g;
	__uint128_t b_ = (b2 - b1) / g;
	__uint128_t b_inv = mod_inverse(b_, n_);
	__uint128_t x_ = (a_ * b_inv) % n_;
	Int t(f);
	for(uint64_t i = 0; i < g; ++i){
	uint64_t tmp = static_cast<uint64_t>(x_);
	t.a[0] = tmp;
	if((alpha ^ t) == beta){
	return tmp;
	}
	x_ = (x_ + n_) % n;
	}
	}
	return 0xFFFF'FFFF'FFFF'FFFF; // 无解，我返回一个特殊的数

# 我学号的 DLP

相关代码进行计时，输入输出：

cpp

	#ifndef ONLINE_JUDGE
	#include <chrono>
	#include <iomanip>
	FILE output, input;
	chrono::time_point<chrono::high_resolution_clock> start_time, end_time;
	#endif

	int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.tie(0);

	#ifndef ONLINE_JUDGE
	output = freopen("output", "w", stdout);
	input = freopen("input", "r", stdin);
	start_time = chrono::high_resolution_clock::now();
	#endif

	PollardRho solution;
	string s;
	cin >> solution.f >> solution.n >> solution.alpha >> solution.beta;
	cout << solution.solve();
	cout.flush();

	#ifndef ONLINE_JUDGE
	output = freopen("time", "w", stdout);
	end_time = chrono::high_resolution_clock::now();
	auto ns = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time);
	auto us = chrono::duration_cast<chrono::microseconds>(end_time - start_time);
	auto ms = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
	cout << ns.count() << " ns" << endl
	fclose(input);
	fclose(output);
	#endif
	}

我的学号 $22342043$ 所确定的 DLP 问题：

$\begin{aligned} p&=3768901521908407201157691198029711972876087647970824596533\\ (&p−1=2×2×23×8783×2419781956425763×192888768642311611×9993115456385501509)\\ n&=9993115456385501509\\ \alpha&=3107382411142271813235322646657672922264748410711464860476^{2×2×23×8783×2419781956425763×192888768642311611×22342043}\\ &=1672705575588793411750559287020484713881877693514202546508\\ \beta&=2120553873612439845419858696451540936395844505496867133711 \end{aligned}$

输入文件 input 内容如下：

raw

	3768901521908407201157691198029711972876087647970824596533
	9993115456385501509
	1672705575588793411750559287020484713881877693514202546508
	2120553873612439845419858696451540936395844505496867133711

我在 Linux 虚拟机环境下计算，配置：

CPU：Intel (R) Xeon (R) CPU E7-4830 v3 @ 2.10GHz 总共 8 核
内存： 16.00 GiB
OS：Ubuntu 22.04

(fish) 开始计算：

shell

nohup bash ./my_program > output.log 2>&1 & set pid $last_pid; echo $pid > pid

计算结果：

$4823944491583471581$

计算时间：

RSA

2024-12-12T00:00:00.000Z

# 大数运算

我的大数运算实现基本参考了 BearSSL 的实现思路来实现。

存储上，2048-bits 的大数存到 32 个 uint64_t 作为 limb 实现，limb 是大数库中常见的一个概念，表示我这里每一个 uint64_t 单位，它们相差 $W=2^{64}$ 大小的基。

由于一开始我实现大数库的时候，设计的可能不是特别到位，limb 的存储顺序是低位到高位放在下标从低到高，和输入的数据反过来，所以程序中相应的处理了一下。

加减法没有特殊的优化，单纯的：加法从最低位 limb 加到最高位 limb，减法从最高位 limb 减到最低位 limb。

乘法的优化是比较关键的部分，采用 Montgomery 模乘，其原理在上述 BearSSL 的文章中有详细介绍。

# 预计算

为了最大限度利用 Montgomery 模乘优化，在输入有限域的模 p 也就是 RSA 中的 n 时，就需要初始化计算好如下内容：

$p^2\bmod p\\ R^2\bmod p\\ g=p_0^{-1}\bmod W$

其中 $R=W^{N}=2^{32\cdot64}=2^{2^{11}}$ ， $N$ 来自 $p$ 存储所占用的 limb 的数量，当然不一定是 32，只是 RSA-2048 中都是 32。

$g$ 是 $p$ 的最低位一个 limb $p_0$ 模 $W=2^{64}$ 下的逆，用来加速模 $p$ 的 Montgomery 乘法。

# $R^2\bmod p$

我对 $R^2\bmod p$ 的实现如下：

cpp

	uint64_t borrow = 2, diff;
	for (int i = 0; i < 32; ++i) {
	diff = p_2[i] - borrow;
	if(p_2[i] < borrow){
	borrow = 1;
	} else {
	borrow = 0;
	}
	p_2[i] = diff;
	}
	uint64_t buffer[33] = {0};
	buffer[0] = 1;
	for(int i = 0; i < (N << 7); ++i){
	for (int j = 32; j > 0; --j) {
	fread(buffer, sizeof(uint8_t), 1, stdout);
	buffer[j] = (buffer[j] << 1) \| (buffer[j - 1] >> 63);
	}
	buffer[0] = buffer[0] << 1;
	bool flag = true;
	for (int j = 31; j >= 0; --j) {
	if(buffer[j] > p[j]) {
	break;
	} else if (buffer[j] < p[j]) {
	flag = false;
	break;
	}
	}
	if(buffer[32] != 0) {
	flag = true;
	}
	if(flag){
	uint64_t borrow = 0, diff;
	for (int j = 0; j < 32; ++j) {
	diff = buffer[j] - p[j] - borrow;
	if(buffer[j] < p[j] \|\| buffer[j] < borrow){
	borrow = 1;
	} else {
	borrow = 0;
	}
	buffer[j] = diff;
	}
	if(borrow) buffer[32] = 0;
	}
	}
	memcpy(R2modp, buffer, 256);

上述过程其实就是从 1 开始，循环执行 $N<<7=(N\cdot64)^2$ 次：

乘 2，通过左移 1 位实现
检查是否大于 $p$ ，大于则减去 $P$

这样得到最后的 $R^2\bmod p$ 结果。

# $p_0^{-1}\bmod W$

$g$ 有一个比较技巧性的计算方法如下：( $m$ 就是模 $p$ )

所以我对它的实现如下：

cpp

	g = p[0];
	for(int i = 0; i < 5; ++i){
	g = g * (2 - p[0] * g);
	}
	g = -g;
	memcpy(p_2, p, 256);

# Montgomery Multiplication

Montgomery Multiplication 是 Montgomery 变换域上的乘法，比在 $p$ 有限域上更适合计算机运算，将其记为 $\odot$ ，其效果就是：

$a\odot b=\frac{ab}{R}\bmod p$

BearSSL 给出的伪代码如下：( $m$ 就是模 $p$ )

我的实现如下：

cpp

	Int MontgomeryMultiply(const uint64_t * b) const {
	auto add2z = [](uint64_t * z, uint64_t &b, int i){
	uint64_t carry = b, sum;
	for (; i < 3; ++i) {
	sum = z[i] + carry;
	if (sum < carry \|\| sum < z[i]) {
	carry = 1;
	} else {
	carry = 0;
	}
	z[i] = sum;
	}
	};
	Int d(F);
	uint64_t d_h[2] = {0};
	for(int i = 0; i < F.N; ++i){
	uint64_t f = (d.a[0] + a[i] * b[0]) * F.g;
	uint64_t c[2] = {0};
	for(int j = 0; j < F.N; ++j){
	uint64_t z[3]= {c[0], c[1], 0};
	__uint128_t ai = static_cast<__uint128_t>(a[i]);
	__uint128_t bj = static_cast<__uint128_t>(b[j]);
	__uint128_t aibj = ai * bj;
	uint64_t aibj_l = static_cast<uint64_t>(aibj);
	uint64_t aibj_h = static_cast<uint64_t>(aibj >> 64);
	__uint128_t f_ = static_cast<__uint128_t>(f);
	__uint128_t mj = static_cast<__uint128_t>(F.p[j]);
	__uint128_t f_mj = f_ * mj;
	uint64_t f_mj_l = static_cast<uint64_t>(f_mj);
	uint64_t f_mj_h = static_cast<uint64_t>(f_mj >> 64);
	add2z(z, aibj_l, 0);
	add2z(z, aibj_h, 1);
	add2z(z, f_mj_l, 0);
	add2z(z, f_mj_h, 1);
	add2z(z, d.a[j], 0);
	if(j > 0){
	d.a[j - 1] = z[0];
	}
	c[0] = z[1];
	c[1] = z[2];
	}
	uint64_t z[3]= {d_h[0], d_h[1], 0};
	add2z(z, c[0], 0);
	add2z(z, c[1], 1);
	d.a[F.N - 1] = z[0];
	d_h[0] = z[1];
	d_h[1] = z[2];
	}
	bool flag = true;
	for (int i = 31; i >= 0; --i) {
	if (d.a[i] > F.p[i]) {
	break;
	} else if (d.a[i] < F.p[i]) {
	flag = false;
	break;
	}
	}
	if(d_h[0] != 0) flag = true;
	if(flag){
	uint64_t borrow = 0, diff;
	for (int j = 0; j < F.N; ++j) {
	diff = d.a[j] - F.p[j] - borrow;
	if(d.a[j] < F.p[j] + borrow){
	borrow = 1;
	} else {
	borrow = 0;
	}
	d.a[j] = diff;
	}
	}
	return d;
	}

# 模乘

在有了上述准备后，有限域 $p$ 上的模乘 $\otimes$ 可以通过这样实现：

$a\otimes b=ab\bmod p=\frac{abR^2}{R^2}\bmod p=(\frac{a\cdot R^2}{R}\bmod p)\cdot\frac{b}{R}\bmod p$

也就是两次 Montgomery Multiplication 运算就可以完成。第一次是对 $a$ 和 $R^2$ ，第二次是对上一个结果和 $b$ 。

我对它的实现如下：（采用了面向对象设计）

cpp

	Int operator*(const Int& other) const {
	Int aR = this->MontgomeryMultiply(F.R2modp);
	return aR.MontgomeryMultiply(other.a);
	}

# 模指数

$a^b\bmod p$ 采用从 $b$ 最高位开始，逐位对 $a$ 执行平方和乘法实现，这里我的平方复用乘法实现。我只考虑性能，没有采取抗侧信道攻击的平方乘法都执行的方式。实现如下：

cpp

	Int operator^(const Int& other) const {
	Int c(F), tmp(F, a);
	Int aR = this->MontgomeryMultiply(F.R2modp);
	if(*this == c) return c;
	c.a[0] = 1;
	bool start = false;
	for(int i = 31; i >= 0; --i){
	for(int j = 63; j >= 0; --j){
	if(start){
	c = c * c;
	}
	if(other.a[i] & (1ULL << j)){
	if(!start){
	start = true;
	c = *this;
	} else {
	c = c.MontgomeryMultiply(aR.a);
	}
	}
	}
	}
	return c;
	}

# OAEP 填充

注意到需要对 Seed 和 MaskedDB 作为输入进行 MGF 哈希，MGF 哈希还需要在输入后面填充 4 个字节的计数，所以我干脆直接将这两个变量的存储就声明多了这 4 字节填充：

cpp

	uint8_t xSeed[36]; // 32 + 4 = 36
	uint8_t xMaskedDB[227] = {0}; // 256 - 32 - 1 + 4 = 227

# MGF1

利用上一个实验完成的 SHA-256 作为哈希函数 $H$ 。

设置一个从 0 开始、用 4 字节的大端序表示的计数器 $c$ ，将输出设为空数据
不断在输出上拼接 $H(m∣∣c)$ 并增加计数（ $c\gets c+1$ ），直到输出达到指定的长度为止，然后截断多余的部分

实现如下：

cpp

	void MGF(uint8_t * xin, uint32_t ilen, uint8_t * out, uint32_t olen){
	uint32_t t = olen / 32;
	uint32_t i = 0;
	uint8_t * bytes_i = (uint8_t *)(&i);
	for(; i < t; ++i){
	for(int j = 0; j < 4; ++j){
	xin[ilen + j] = bytes_i[3 - j]; // 小端存储的计数转化为大端
	}
	sha256(out + i * 32, xin, ilen + 4);
	}
	if(olen % 32 != 0){
	uint8_t buffer[32];
	for(int j = 0; j < 4; ++j){
	xin[ilen + j] = bytes_i[3 - j]; // 小端存储的计数转化为大端
	}
	sha256(buffer, xin, ilen + 4);
	memcpy(out + i * 32, buffer, olen % 32);
	}
	}

这里我的输入 xin 都是有声明多余 4 个字节供计数填充的。

# Hash(L)

注意到实验输入 $L$ 始终为空， $H(L)$ 结果是固定的，所以干脆直接硬编码了这个结果：

cpp

	uint8_t HashedL[32] = {
	0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14,
	0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
	0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c,
	0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55
	};

# 随机种子生成

利用 x64 CPU 的 RDRAND 指令实现如下：

cpp

	uint8_t xSeed[36]; // 32 + 4 = 36
	for(int i = 0; i < 4; ++i){
	uint64_t randomValue;
	unsigned char status;
	asm volatile (
	"rdrand %0;\n"
	"setc %1"
	: "=r"(randomValue), "=r"(status)
	:
	: "cc"
	);
	memcpy(xSeed + i * 8, &randomValue, 8);
	}

RDRAND 指令一次生成 64 bits 大小的随机数，生成 4 次获得所需的 32 字节随机种子。

# 其他优化可能

上课时老师讲过利用中国剩余定理优化，主要原理是分解使得计算 2048 bits 的有限域运算变成更小的有限域运算，可以很大程度上提升性能，在大数库实现过程也看得到，随着运算规模增大，时间开销的增长并不只是线性增长的，2048 bits 的时间开销比 1024 bits 大了远不止两倍。但是输入并没有给我 $n=pq$ 的 $p$ 和 $q$ ，这个优化也没法用。

SHA-256

2024-12-05T00:00:00.000Z

# 算法流程

# 扩展对齐

给定输入都是按字节对齐的，也就是 8bits 的倍数，但不一定是 SHA-256 要求的 512bits 的倍数，需要补位或者扩展。

补位对齐的工作不是在一开始做好的，因为输入数据量可能很大，一次性将所有数据读入程序内存空间是不合适的，而 SHA-256 工作本身就是分组迭代，所以 512bits = 64B 为单位（块）读入，每次处理完 64B 再读取下一个块的数据。只有在读最后一个块的时候，需要视情况补位扩展：

最后一个块大小小于等于 56 个字节，那么最后 8 个字节填入 64bits 无符号编码的原始数据字节为单位的长度，其余字节补 0x80
否则当前块剩余字节补 0x80 （当然如果刚好最后一个块是 512bits 就不补，但后面的工作还要做），然后处理完当前块之后再补一个块，这一块最后 8 个字节填入 64bits 无符号编码的原始数据字节为单位的长度，其余字节补 0x80

综上，再考虑处理一个读入数据的时候还不知道这一块是不是最后一块，可以这样处理：不管原始数据有多长，先读取数据并处理一个块，然后判断读取数据长度，如果等于 64B，那么继续读取数据并处理一个块然后判断读取数据长度，否则按照上面的补位扩展处理。

所以我在程序实现的时候使用 do{...}while(...) 循环结构，来实现这样的逻辑：

cpp

	uint64_t bytesRead = 0, totalBytesRead = 0;
	uint8_t * bytesTotalBytesRead = (uint8_t *)(&totalBytesRead);
	uint8_t bytes[64] = {0};
	do {
	bytesRead = fread(bytes, 1, sizeof(bytes), stdin);
	if (bytesRead == 64) {
	totalBytesRead += 64;
	hashRounds(bytes);
	} else if (bytesRead <= 55) {
	totalBytesRead = (totalBytesRead + bytesRead) * 8;
	bytes[bytesRead] = 0x80;
	memset(bytes + bytesRead + 1, 0, 63 - bytesRead);
	for(int i = 0; i < 8; ++i){ /* 这个循环比较特殊 */
	bytes[i + 56] = bytesTotalBytesRead[7 - i];
	}
	hashRounds(bytes);
	} else {
	uint8_t bytes_end[64] = {0};
	totalBytesRead = (totalBytesRead + bytesRead) * 8;
	bytes[bytesRead] = 0x80;
	memset(bytes + bytesRead + 1, 0, 63 - bytesRead );
	hashRounds(bytes);
	for(int i = 0; i < 8; ++i){ /* 这个循环比较特殊 */
	bytes_end[i + 56] = bytesTotalBytesRead[7 - i];
	}
	hashRounds(bytes_end);
	}
	} while (
	bytesRead == 64
	);

上面的注释我指出了 2 个特殊的循环，在这两个循环我相当于将 bytesTotalBytesRead 的大小端模式反了过来存到 bytes 或 bytes_end ，这是有原因的，我在后面会提到。

hashRounds 就是 SHA-256 更标准的描述中的轮函数，这个函数的功能就是根据 512bits = 64B 输入更新 256bits 签名或者哈希值结果。

# 初始值与常量

算法根据每一个块对哈希值进行更新，而初始的哈希值则是一个固定的值，它来自自然数中前 8 个素数二次方根的小数部分里十进制下的前十位，定义如下：

cpp

	uint32_t H[8] = {
	0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
	};

每一轮更新都还需要一个 8 x 256bits 大小的常量 K，它来自自然数中前 64 个素数三次方根的小数部分里十进制下的前十位，定义如下：

cpp

	const uint32_t K[64] = {
	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
	0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
	0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
	0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
	0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
	0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
	0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
	};

# 轮函数

每一轮更新，初始化 8 个 word（32B） a,b,c,d,e,f,g,h 为 H[8] 的 8 个 word。然后循环迭代如下过程 64 轮：

更详细准确的计算过程如下：

64 轮需要 64 个字 w ，也就是需要一个 w[64] ，它的前 16 个字来自输入的 512bits = 16x32bits，其剩余 56

这里 >>> 表示循环右移，可以通过两次位移拼接实现，例如 n 位的 k 可以通过如下方式实现：

cpp

x >>> k = ((x >> k) | (x << (n-k))

最后经过 64 轮迭代后，再将 a,b,c,d,e,f,g,h 分别加到 H[8] 的 8 个 word，作为这一轮更新结束的签名或哈希值。

代码实现如下，输入是 64x8B = 512bits ：

cpp

	void hashRounds(uint8_t * bytes){
	uint32_t w[64];

	for(int i = 0; i < 16; ++i){ /* 这个循环比较特殊 */
	for(int j = 0; j < 4; ++j){
	memcpy((uint8_t )w + 4 i + j, bytes + 4 * i + 3 - j, 1);
	}
	}

	for(int i = 16; i < 64; ++i){
	uint32_t s0 = ((w[i - 15] >> 7) \| (w[i - 15] << 25)) ^ ((w[i - 15] >> 18) \| (w[i - 15] << 14)) ^ (w[i - 15] >> 3);
	uint32_t s1 = ((w[i - 2] >> 17) \| (w[i - 2] << 15)) ^ ((w[i - 2] >> 19) \| (w[i - 2] << 13)) ^ (w[i - 2] >> 10);
	w[i] = w[i - 16] + s0 + w[i - 7] + s1;
	}

	uint32_t a = H[0];
	uint32_t b = H[1];
	uint32_t c = H[2];
	uint32_t d = H[3];
	uint32_t e = H[4];
	uint32_t f = H[5];
	uint32_t g = H[6];
	uint32_t h = H[7];
	uint32_t s1, ch, t1, s0, maj, t2;
	for(int i = 0; i < 64; ++i){
	s1 = ((e >> 6) \| (e << 26)) ^ ((e >> 11) \| (e << 21)) ^ ((e >> 25) \| (e << 7));
	ch = (e & f) ^ ((~e) & g );
	t1 = h + s1 + ch + K[i] + w[i];
	s0 = ((a >> 2) \| (a << 30)) ^ ((a >> 13) \| (a << 19)) ^ ((a >> 22) \| (a << 10));
	maj = (a & b) ^ (a & c) ^ (b & c);
	t2 = s0 + maj;
	h = g;
	g = f;
	f = e;
	e = d + t1;
	d = c;
	c = b;
	b = a;
	a = t1 + t2;
	}
	H[0] += a;
	H[1] += b;
	H[2] += c;
	H[3] += d;
	H[4] += e;
	H[5] += f;
	H[6] += g;
	H[7] += h;
	}

上面的注释我指出了 2 个特殊的循环，在这两个循环我相当于将输入 64x8B = 512bits 为大小的块，以 1 word = 4B 为单位将大小端模式反了过来作为 w[64] 的前 16 个字。

这里和前面处理扩展补位一样，都是因为 SHA-256 算法中，进行移位、循环移位等操作都是对一个 word 操作，而我为了方便使用 uint32_t 作为一个 word 直接用 C++ 基本运算处理，现代处理器基本都是小端存储，存入 uint32_t 的时候需要保持和算法大端存储模式描述的一致，就得这样操作。

这个问题也是我 debug 了好几个小时才发现的

当然最终输出 H 的时候，也需要类似的处理将小端存储描述的结果转化为大端存储描述的结果。

# 一些可能的优化

# SIMD 优化

这里我没有实现，只是想到有这个方案，因为 Intel x86_64 提供了这样的指令集家族 SHA，可以直接硬件加速整个 SHA-256 算法。我在网上找到这样一个开源实现：

https://github.com/minio/sha256-simd

这个实现中使用汇编调用了 SHA 指令集。

# 并行优化

SHA-256 的更新过程中 64 轮迭代依赖于上一轮迭代，无法实现并行。同样的轮函数依赖于上一轮的结果，也无法实现并行。

参考：https://stackoverflow.com/questions/24088295/can-sha1-sha-256-sha-512-be-broken-up-to-run-across-multiple-cores-threads

但是对每一个块的预处理，也就是 w[64] 的生成是相互独立的，还是可以并行化的。

# 思考题

# 问题 1

SHA-1 的初始常数是很有规律的 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 ，SHA-256 的初始常数和轮常数分别来自于前几个素数的平方根 / 立方根的小数部分。为什么要这么设计？

# 回答

平方根和立方根本身具有良好的数学性质，确保生成的常数在运算中能够提供良好的混合性和扩散性。这对于哈希函数的安全性至关重要，因为它们需要确保输入的微小变化能导致输出的巨大变化。

# 问题 2

有一类 hash 算法被称为 “Non-cryptographic hash function”，例如 Java (OpenJDK) 中 hashCode 的实现是非常简单的迭代计算 h = 31 * h + x ，其他的此类算法包括 FNV、MurmurHash、xxHash 等。它们与 MD5、SHA-1、SHA-256 等 hash 算法的区别是什么？它们有哪些主要用途？为什么会比 SHA-256 等等更适合用于这些场景？

# 回答

非加密哈希函数：主要用于快速的数据散列和分布，优化性能，适用于哈希表、数据去重等场景。它们不具备防篡改或安全性的特性，具有更高的计算速度和更低的内存占用，因为它们的算法设计较为简单，优化了性能。另外非加密哈希函数在设计时并不考虑碰撞抵抗性，可能会存在多个输入映射到同一输出的现象。
加密哈希函数：旨在确保数据的完整性和安全性，具有抗碰撞性、抗篡改性等特性，适用于数字签名、密码保护等安全应用。另外还确保不同输入几乎不可能产生相同的哈希值。

# 问题 3

如果你需要设计一个用户系统，你也许知道数据库中不应该以明文存储用户的密码（遗憾的是，我国的知名计算机技术社区 CSDN 就犯过这样的错误），而应该存储密码的 hash。但是，在这种情况下直接使用 SHA-256 等等仍然是不推荐的。有哪些 hash 算法更适合用来处理密码？它们与 SHA-256 等等有什么区别？

# 回答

bcrypt：是一个基于 Blowfish 加密算法的哈希函数，它设计为慢速哈希，具有可调节的工作因子，可以随时间增加计算复杂度。通过增加计算时间来抵御暴力破解和字典攻击。
scrypt：旨在防止专用硬件（如 ASIC）进行暴力破解，使用大量内存和计算资源。由于其内存强度，scrypt 对抗并行计算攻击（如 GPU 和 ASIC）效果更好。
Argon2：具有高效的内存使用和可调节的时间复杂度。具备高度的安全性和灵活性，支持多种配置以应对不同的攻击场景。

它们与 SHA-256 的区别：SHA-256 是一种快速的哈希函数，设计目标是高效计算，但也使得暴力破解（即快速尝试大量候选密码）变得可行。而 bcrypt、scrypt 和 Argon2 则故意设计为较慢，以增加破解的难度，使得暴力破解的成本显著提高。

# 问题 4

在比特币中，有一类节点的功能是将交易数据打包成区块附加到区块链上，而我们常说的 “挖矿”，其基本原理就是不断变换区块中的 nonce 字段，使整个区块的 SHA-256（当成一个 256 bit 的大整数）小于比特币网络当前规定的难度值。glminer 是一个由 EtherDream 编写的玩具版 “挖矿” 演示：给定 12 bytes 的数据 Q，要求找到另一串 4 bytes 的数据 A，使 Q+A 的 SHA-256 以 00000000 开头。尝试用你实现的 SHA-256 或各种标准库 / 第三方库来实现这一功能，并和 glminer 比较计算 SHA-256 的性能。查看在 V2EX 上的讨论以及 glminer 的源代码，为什么会存在这样的性能差距？它是如何实现 SHA-256 计算的？

# 回答

我没有尝试编写挖矿程序，但我看了 glminer 源码，它使用了自定义着色器代码计算哈希，通过 WebGL 画图渲染触发 GPU 不断对尝试的随机数执行这个代码计算哈希值，实现挖矿的效果。

它的代码能够用 GPU 以 2048 线程并行化加速，所以效果当然是比单线程程序要好很多的。

AES-128

2024-11-21T00:00:00.000Z

# 加密模式处理

# ECB

The Electronic Codebook Mode

# CBC

The Cipher Block Chaining Mode

# CFB

The Cipher Feedback Mode

这里只需要考虑 CFB-128bit，也就是 $s=b$ ，所以上述过程可以简化为如下：

$\begin{aligned} &\text{CFB Encryption:} &&C_1=P_1\oplus CIPH_K(IV)\\ &&&C_j=P_j\oplus CIPH_K(C_{j-1}) && \text{for}\ j=2\cdots n;\\\\ &\text{CFB Decryption:} &&P_1=C_1\oplus CIPH_K(IV)\\ &&&P_j=C_j\oplus CIPH_K(C_{j-1}) && \text{for}\ j=2\cdots n; \end{aligned}$

# OFB

The Output Feedback Mode

最后一个分组 block 长度可以小于 128 bit，这里假定其长度为 $u$ 。

我消去 $I$ ，仅用 $O$ 表示密钥流的变化，更加直观：

$\begin{aligned} &\text{OFB Encryption:} &&O_1=CIPH_K(IV)\\ &&&O_j=CIPH_K(O_{j-1}) && \text{for}\ j=2\cdots n;\\ &&&C_j=P_j\oplus O_{j} && \text{for}\ j=1,2\cdots n-1;\\ &&&C_n^*=P_n^*\oplus (O_{j}>>(b-u))\\ \\ &\text{OFB Decryption:} &&O_1=CIPH_K(IV)\\ &&&O_j=CIPH_K(O_{j-1}) && \text{for}\ j=2\cdots n;\\ &&&P_j=C_j\oplus O_{j} && \text{for}\ j=1,2\cdots n-1;\\ &&&P_n^*=C_n^*\oplus (O_{j}>>(b-u))\\ \end{aligned}$

$b$ 是一个 block 分组的大小，这里就是 128 bit。

# CTR

The Counter Mode

# AES Cipher & Inverse

下图展现了实现加密和解密 AES 的过程，将每一轮每一个变换函数建立了一一对应关系。

其中除了 Add 操作之外（直接异或即可），包含主要 3 对变换和反变换。另外还需要进行 Expand Key，在 AES-128 中就是将 128 bits 输入 key 计算得到规模为 128x11 bits 的 11 个 key。

# SubBytes & Inverse

这一变换数学上的功能是对每一个字节实现如下变换：

将八位字节视为有限域 $GF(2^8)$ 上的元素，进行取逆
然后进行如下仿射变换：（ $b_i$ 表示一个字节从低位开始数的第 $i+1$ 位）

从结果上来说，上述变换过程及其反变换完全可以通过查表来完成。所以对于 SubBytes 和 InvSubBytes 变换，就是分别将每一个字节经过预先计算好的 AES S-Box 和 AES Inv-S-Box 进行查表置换。

对于一个字节，有 $2^8=256$ 种取值，所以两个 Box 的大小都是 256，内容如下：

cpp

	const uint8_t Sbox[256] = {
	0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
	0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
	0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
	0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
	0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
	0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
	0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
	0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
	0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
	0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
	0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
	0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
	0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
	0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
	0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
	0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
	};

	const uint8_t InvSbox[256] = {
	0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
	0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
	0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
	0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
	0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
	0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
	0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
	0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
	0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
	0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
	0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
	0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
	0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
	0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
	0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
	0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
	};

# ShiftRows & Inverse

这一变换比较简单，就是对表示为 4x4 矩阵的 16 字节数据，对第 $i$ 行进行 $i$ 字节轮转。（ $0\leq i\leq 3$ ）

所以显然第一行，也就是第 $0$ 行进行 $0$ 字节轮转是没有实际作用可以省略的。其过程如下图所示：

逆变换则如下所示：

cpp 使用冒泡的方式处理如下：

cpp

	// uint8_t c[16]

	inline void ShiftRows(uint8_t * c){
	swap(c[1], c[5]);
	swap(c[5], c[9]);
	swap(c[9], c[13]);
	swap(c[2], c[10]);
	swap(c[6], c[14]);
	swap(c[15], c[11]);
	swap(c[11], c[7]);
	swap(c[7], c[3]);
	}

	inline void InvShiftRows(uint8_t * c){
	swap(c[9], c[13]);
	swap(c[5], c[9]);
	swap(c[1], c[5]);
	swap(c[2], c[10]);
	swap(c[6], c[14]);
	swap(c[7], c[3]);
	swap(c[11], c[7]);
	swap(c[15], c[11]);
	}

# MixColumns & Inverse

对表示为 4x4 矩阵的 16 字节数据，每一列 4 字节向量，视为一个 $x=2^8$ 并且系数来自 $GF(2^8)$ 的多项式

$a(x)=a_3x+a_2x+a_1x+a_0\\a_i\in GF(2^8),\ \ x=2^8$

AES 使用了一对可逆的多项式，通过对这两个多项式进行模乘实现变换和逆变换：

$b(x)=\{\text{0x03}\}x^3+\{\text{0x01}\}x^2+\{\text{0x01}\}x+\{\text{0x02}\}\\ b^{-1}(x)=\{\text{0x0B}\}x^3+\{\text{0x0D}\}x^2+\{\text{0x09}\}x+\{\text{0x0E}\}$

于是 $a(x)\otimes b(x)$ 就可以表示为有限域 $GF(2^8)$ 上的向量与可逆矩阵乘法：

同理， $a(x)\otimes b^{-1}(x)$ 也表示为有限域 $GF(2^8)$ 上的向量与可逆矩阵乘法：

这里有限域 $GF(2^8)$ 上的模乘运算如果再通过查表算，就需要 $7\times256$ 大小的表，因为两个矩阵总共出现了 7 种不同的系数。在 AES 标准中没有使用查表，而是使用有限域 $GF(2^8)$ 上位运算实现的乘 2 模运算 xtime 实现。这个函数运算非常简单，cpp 实现如下：

cpp

	auto xtime = [](uint8_t x) -> uint8_t {
	return (x & 0x80) ? ((x << 1) ^ 0x1B) : (x << 1);
	};

对于一般的有限域 $GF(2^8)$ 上模乘运算 $a\otimes b$ ，就能用 xtime 表示如下：

$a\otimes b=b_7\cdot\text{xtime}^{7}(a)+b_6\cdot\text{xtime}^{6}(a)+\cdots+b_1\cdot\text{xtime}(a)+b_0\cdot a\ \ \ ,\ \ \ b_i\in\{0,1\}$

然后矩阵运算还可以技巧性的使用中间变量，避免进行重复相同的运算，cpp 实现单独对一个列变换和反变换如下：

cpp

	inline void MixColumn(uint8_t * a){
	uint8_t t, u;
	t = a[0] ^ a[1] ^ a[2] ^ a[3];
	u = a[0];
	a[0] ^= t ^ xtime(a[i] ^ a[1]);
	a[1] ^= t ^ xtime(a[1] ^ a[2]);
	a[2] ^= t ^ xtime(a[2] ^ a[3]);
	a[3] ^= t ^ xtime(a[3] ^ u);
	}

	inline void InvMixColumn(uint8_t * a){
	uint8_t u, v;
	u = xtime(xtime(c[i] ^ c[i + 2]));
	v = xtime(xtime(c[i + 1] ^ c[i + 3]));
	c[i] ^= u;
	c[i + 1] ^= v;
	c[i + 2] ^= u;
	c[i + 3] ^= v;
	MixColumn(c);
	}

# Key Expansion

过程大致如图所示：

NIST 的 AES 标准文档 FIPS 197 给出的伪代码如下：

这里关键的几个步骤在于如下 2 个函数：

SubWord ，对一个 word 的 4 个字节分别进行和 SubBytes 变换一样的操作
RotWord ，对一个 word 的 4 个字节进行和 ShiftRows 变换第二行一样的操作

还有一个数组 Rcon ，定义为：

cpp

	uint8_t Rcon[32] = {
	0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
	0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
	0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
	0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
	}

在 AES-128 中只需要用到前 11 个。

# 思考题

# 问题 1

除了课堂上介绍的五种模式以外，分组加密还有一些其他的工作模式。考虑下面的两个场景，使用什么工作模式可以满足它们的需求？这个工作模式的原理是什么？

你需要检查密文是否被篡改（不需要单独使用 Hash 函数）。
你需要加密一块磁盘。磁盘上的数据是以扇区（通常为 512 Bytes）为单位读写的，操作系统可以通过扇区号随机访问扇区。磁盘加密的密文长度必须要和明文相同，不能使用额外的空间。（有兴趣的话，可以尝试使用一下磁盘加密软件，例如开源的 VeraCrypt）

# 回答

检查密文是否被篡改，就需要认证功能，分组密码中支持认证的模式被称为 AE 模式，例如：

XCBC
ACBC
APM
OCB
EAX
CWC
CCM
GCM。

有的模式也允许为未加密的关联数据进行认证，因此被称为 AEAD（Authenticated-Encryption with Associated-Data。

对于磁盘加密，要求密文长度与明文相同且不能使用额外的空间，可以使用 ECB、CBC、CTR 、XTS（XEX Tweakable Block Cipher with ciphertext stealing）模式。根据我查阅到资料， XTS 模式是专门设计用于磁盘加密的工作模式，例如 Kingston 等厂商就会在其产品中使用。

# 问题 2

尝试在实验 3-2 中实现全部五种工作模式：ECB、CBC、CFB、OFB、CTR。

只要实现了对单个分组的加密和解密，实现其他的工作模式也是很简单的！
选做，不会对分数产生影响。

在前面有各个模式分析，当时我没时间搞这个

# 问题 3

尝试使用 x64 CPU 的 AES 指令集（AES-NI）实现 AES-256。

参考资料：x86/x64 SIMD 命令による AES 暗号処理
理解 AES-NI 的各个指令的用途。
上面的链接中有 C++ 编写的示例代码，仅供参考，不要直接提交或使用 GPT 格式化重命名后提交。
请先用自己实现的版本 AC 后再编写使用 AES-NI 的版本，并在实验报告中附上两个版本的提交 ID。
不计入思考题分数，但是可以影响性能分。

见附录

# Reference

NIST 的 AES 标准文档 FIPS 197
一个叫 crypto_commons 的 python 库中 AES 的实现
Youtube 上的一个 AES 图解系列视频
NIST 的文档 Recommendation for Block Cipher Modes of Operation

# 附录

当时忙着一个写数据库的比赛（Mini OceanBase ）没来得及弄密码学了

没来得及完全完成 x64 CPU 的 AES 指令集（AES-NI）实现 AES-256，实际上我在自己实现的时候就已开始想使用 __m128i 一步到位，然后发现这是思考题附加内容，并且使用 AES 指令是真的 “一步到位”，非常简单。所以我自己的实现只好退而求其次使用 uint32_t 和 uint8_t 来实现。

已经初步写好，但好像还是错的，没来得及 debug 了，如下：

cpp

	#include <cstdint>
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <stdint.h>
	#include <cstring>
	#include <emmintrin.h>
	#include <immintrin.h>


	// Number of columns (32-bit words) comprising the State. For this standard, Nb = 4
	#define Nb 4

	// Number of 32-bit words comprising the Cipher Key. For this standard, Nk = 4, 6, or 8
	#define Nk 4

	// Number of rounds, which is a function of Nk and Nb (which is fixed). For this standard, Nr = 10, 12, or 14
	#define Nr 10

	using namespace std;

	void ecb_en(__m128i & KEY, uint32_t & len);
	void ecb_de(__m128i & KEY, uint32_t & len);
	void cbc_en(__m128i & KEY, __m128i & IV, uint32_t & len);
	void cbc_de(__m128i & KEY, __m128i & IV, uint32_t & len);
	void cfb_en(__m128i & KEY, __m128i & IV, uint32_t & len);
	void cfb_de(__m128i & KEY, __m128i & IV, uint32_t & len);
	void ofb_en(__m128i & KEY, __m128i & IV, uint32_t & len);
	void ofb_de(__m128i & KEY, __m128i & IV, uint32_t & len);
	void ctr_en(__m128i & KEY, __m128i & IV, uint32_t & len);
	void ctr_de(__m128i & KEY, __m128i & IV, uint32_t & len);


	enum MODE : uint8_t {
	ECB_EN = 0x00,
	ECB_DE = 0x80,
	CBC_EN = 0x01,
	CBC_DE = 0x81,
	CFB_EN = 0x02,
	CFB_DE = 0x82,
	OFB_EN = 0x03,
	OFB_DE = 0x83,
	CTR_EN = 0x04,
	CTR_DE = 0x84,
	};



	#ifndef ONLINE_JUDGE
	#include <chrono>
	#include <iomanip>
	FILE output, input;
	chrono::time_point<chrono::high_resolution_clock> start_time, end_time;
	#endif


	int main(){
	#ifndef ONLINE_JUDGE
	output = freopen("output.bin", "wb", stdout);
	input = freopen("input.bin", "rb", stdin);
	start_time = chrono::high_resolution_clock::now();
	#endif

	uint8_t mode;
	__m128i KEY;
	__m128i IV;
	uint32_t len;
	fread(&mode, sizeof(mode), 1, stdin);
	fread(&KEY, sizeof(KEY), 1, stdin);
	fread(&IV, sizeof(IV), 1, stdin);
	fread(&len, sizeof(len), 1, stdin);

	switch(mode){
	// case ECB_EN:{ecb_en(KEY, len);}break;
	// case ECB_DE:{ecb_de(KEY, len);}break;
	case CBC_EN:{cbc_en(KEY, IV, len);} break;
	case CBC_DE:{cbc_de(KEY, IV, len);} break;
	// case CFB_EN:{cfb_en(KEY, IV, len);}break;
	// case CFB_DE:{cfb_de(KEY, IV, len);}break;
	// case OFB_EN:{ofb_en(KEY, IV, len);}break;
	// case OFB_DE:{ofb_de(KEY, IV, len);}break;
	// case CTR_EN:{ctr_en(KEY, IV, len);}break;
	// case CTR_DE:{ctr_de(KEY, IV, len);}break;
	}

	#ifndef ONLINE_JUDGE
	fclose(input);
	fclose(output);
	output = freopen("time", "w", stdout);
	end_time = chrono::high_resolution_clock::now();
	auto ns = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time);
	auto us = chrono::duration_cast<chrono::microseconds>(end_time - start_time);
	auto ms = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
	cout << ns.count() << " ns\n"
	<< us.count() << " us\n"
	<< ms.count() << " ms";
	fclose(output);
	#endif

	return 0;
	}


	// uint32_t key[Nk] ---expand---> __m128i w128[Nr+1]
	void KeyExpansion(__m128i & key, __m128i * w128, bool decrypting){
	w128[0] = key;
	__m128i t, t2;

	#define EXPAND(n, RCON) \
	t = _mm_slli_si128(key, 4);\
	t = _mm_xor_si128(key, t);\
	t2 = _mm_slli_si128(t, 8);\
	t = _mm_xor_si128(t, t2);\
	key = _mm_aeskeygenassist_si128(key, RCON);\
	key = _mm_shuffle_epi32(key, 0xFF);\
	key = _mm_xor_si128(t, key);\
	w128[n] = key;

	EXPAND(1, 0x01);

	// Go on...
	EXPAND(2, 0x02);
	EXPAND(3, 0x04);
	EXPAND(4, 0x08);
	EXPAND(5, 0x10);
	EXPAND(6, 0x20);
	EXPAND(7, 0x40);
	EXPAND(8, 0x80);
	EXPAND(9, 0x1b);
	EXPAND(10, 0x36);

	if (decrypting) {
	w128[0] = w128[0];
	w128[1] = _mm_aesimc_si128(w128[1]);
	w128[2] = _mm_aesimc_si128(w128[2]);
	w128[3] = _mm_aesimc_si128(w128[3]);
	w128[4] = _mm_aesimc_si128(w128[4]);
	w128[5] = _mm_aesimc_si128(w128[5]);
	w128[6] = _mm_aesimc_si128(w128[6]);
	w128[7] = _mm_aesimc_si128(w128[7]);
	w128[8] = _mm_aesimc_si128(w128[8]);
	w128[9] = _mm_aesimc_si128(w128[9]);
	w128[Nr] = w128[Nr];
	}
	}


	// Add 128-bit k to c
	inline void AddRoundKey(__m128i & c, __m128i & k){
	c = _mm_xor_si128(c, k);
	}


	// AES Cipher
	inline void Ciph(__m128i c, __m128i * w128){
	__m128i state = _mm_loadu_si128(&c);
	state = _mm_xor_si128(state, w128[0]);
	state = _mm_aesenc_si128(state, w128[1]);
	state = _mm_aesenc_si128(state, w128[2]);
	state = _mm_aesenc_si128(state, w128[3]);
	state = _mm_aesenc_si128(state, w128[4]);
	state = _mm_aesenc_si128(state, w128[5]);
	state = _mm_aesenc_si128(state, w128[6]);
	state = _mm_aesenc_si128(state, w128[7]);
	state = _mm_aesenc_si128(state, w128[8]);
	state = _mm_aesenc_si128(state, w128[9]);
	state = _mm_aesenclast_si128(state, w128[Nr]);
	_mm_storeu_si128(reinterpret_cast<__m128i *>(&c), state);
	}



	// AES Inverse Cipher
	inline void EqInvCiph(__m128i & c, __m128i * w128){
	__m128i state = _mm_loadu_si128(&c);
	state = _mm_xor_si128(state, w128[Nr]);
	state = _mm_aesdec_si128(state, w128[9]);
	state = _mm_aesdec_si128(state, w128[8]);
	state = _mm_aesdec_si128(state, w128[7]);
	state = _mm_aesdec_si128(state, w128[6]);
	state = _mm_aesdec_si128(state, w128[5]);
	state = _mm_aesdec_si128(state, w128[4]);
	state = _mm_aesdec_si128(state, w128[3]);
	state = _mm_aesdec_si128(state, w128[2]);
	state = _mm_aesdec_si128(state, w128[1]);
	state = _mm_aesdeclast_si128(state, w128[0]);
	_mm_storeu_si128(reinterpret_cast<__m128i *>(&c), state);
	}


	// CBC mode encryption
	void cbc_en(__m128i & KEY, __m128i & IV, uint32_t & len){
	__m128i p, c, w[Nr+1];
	uint8_t p_bytes[16];
	uint8_t c_bytes[16];
	c = IV;
	KeyExpansion(KEY, w, 0);
	while(len >= Nb * 4){
	len -= Nb * 4;
	fread(&p, sizeof(p), 1, stdin);
	AddRoundKey(c, p);
	Ciph(c, w);
	fwrite(&c, sizeof(c), 1, stdout);
	}
	memset(p_bytes + len, Nb * 4 - len, Nb * 4 - len);
	fread(&p, sizeof(uint8_t), len, stdin);
	AddRoundKey(c, p);
	Ciph(c, w);
	fwrite(&c, sizeof(c), 1, stdout);
	}


	// CBC mode decryption, input must be multiple of 128 bits
	void cbc_de(__m128i & KEY, __m128i & IV, uint32_t & len){
	__m128i p, c, last_c, w[Nr+1];
	uint8_t p_bytes[16];
	memcpy(&last_c, &IV, Nb * 4);
	KeyExpansion(KEY, w, 1);
	while(len > 0){
	fread(&c, sizeof(c), 1, stdin);
	p = c;
	EqInvCiph(p, w);
	AddRoundKey(p, last_c);
	last_c = c;
	if(len == Nb * 4){
	_mm_storeu_si128((__m128i*)p_bytes, p);
	int l = p_bytes[Nb * 4 - 1];
	for(int i = 1; i < l; ++i){
	if(p_bytes[Nb * 4 - 1 - i] != l) {
	l = 0;
	break;
	}
	}
	fwrite(&p, sizeof(uint8_t), Nb * 4 - l, stdout);
	} else {
	fwrite(&p, sizeof(p), 1, stdout);
	}
	len -= Nb * 4;
	}
	}

有限域运算

2024-10-23T00:00:00.000Z

# 准备工作

# 原理

在有限域 $F_{2^{131}}$ 上实现运算：

加法（等价于减法，就是异或）
取模
- 输入：由于只考虑乘法结果作为输入，乘法结果最高只会有 $x^{260}$ ，所以输入为 261 位以内的数
- 输出：131 位以内的限域 $F_{2^{131}}$ 上取模结果
乘法
平方
- 与一般的乘法运算相比较特殊，具有较大优化空间，单独实现
求逆（等价于 “除法”）
- 实现一：费马小定理
- 实现二：扩展欧几里得

# 数据存储

使用 uint64_t[3] 来表示输入、输出数据。

对于乘法运算，高位需要先保留，然后取模，所以乘法、平方、取模运算的过程中使用到 uint64_t[5] 。

对于加法运算，由于只需要异或，不需要移位，采用 __m256i 存储和运算。

# 处理输入输出

cpp

	#ifndef ONLINE_JUDGE
	#include <chrono>
	#include <iomanip>
	FILE output, input;
	chrono::time_point<chrono::high_resolution_clock> start_time, end_time;
	#endif

	int main(){
	#ifndef ONLINE_JUDGE
	output = freopen("output.bin", "w", stdout);
	input = freopen("input.bin", "r", stdin);
	start_time = chrono::high_resolution_clock::now();
	#endif

	uint32_t n;
	uint8_t op;
	uint64_t a[3], b[3];

	fread(&n, sizeof(int32_t), 1, stdin);

	while(n--){
	fread(&op, sizeof(op), 1, stdin);
	fread(&a, sizeof(a), 1, stdin);
	fread(&b, sizeof(b), 1, stdin);
	uint64_t c[4] = {0};
	switch(op){
	case 0:
	gf_add(c, a, b);
	break;
	case 1:
	gf_mul(c, a, b);
	break;
	case 2:
	gf_pow2(c, a);
	break;
	case 3:
	gf_inv(c, a);
	break;
	}
	fwrite(&c, sizeof(uint64_t), 3, stdout);
	}

	#ifndef ONLINE_JUDGE
	fclose(input);
	fclose(output);
	output = freopen("time", "w", stdout);
	end_time = chrono::high_resolution_clock::now();
	auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time);
	auto us = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
	auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
	cout << ns.count() << " ns" << endl
	<< us.count() << " us" << endl
	<< ms.count() << " ms";
	fclose(output);
	#endif

	return 0;
	}

# 输入输出可读化

为了方便 debug 和检验，编写相关测试脚本如下， test.sh ：

shell

	python3 gen-input.py ${2} ${3}
	g++ -Wall -Wextra -Ofast \
	-march=native -mtune=native \
	-std=c++20 \
	-o test solv${1}.cpp
	./test
	if ((${3} < 10)); then
	python3 bin2hex.py
	fi

主要思路为 gen-input.py 根据输入参数生成四种运算中的一种 ${1} ，测试次数为 ${2} ，生成一份二进制输入文件 input.bin 。编译代码执行时 ${1} 指定不同源文件，方便切换观察和对比不同实现的性能。最后看测试次数 ${3} 如果超过 10，一般就是大量运算测试性能，那就不必将输出转化为可视化文本了，转化耗时长、文件大而且没有意义；否则就用脚本 bin2hex.py 将程序二进制输出转化为可读文本，十六进制格式显示数字，用于检验运算正确性。

当然输出也可以用 hex editor 查看就行了

# 加法

# Trival

最简单，对每一位异或即可。

cpp

	inline void gf_add(uint64_t c[3], const uint64_t a[3], const uint64_t b[3]){
	c[0] = a_{0} ^ b_{0};
	c[1] = a_{1} ^ b_{1};
	c[2] = a_{2} ^ b_{2};
	}

# SIMD 优化

我尝试使用 SIMD 指令集优化，我发现我的电脑和在线测试平台都支持 AVX512，所以尝试用该指令集同时对 8 个 uint64 异或。我可以最多存 8 份加法的输入，但是问题就在于输出的时候，虽然实验测试用例有连续 1M 个加法，但是也有随机顺序的测试，输出的顺序还要保证和输入的顺序一致，这样还要存储大量的结果，考虑到这样会增加更多开销，就没有往这方面做下去。所以最后针对加法，不再使用 uint64_t ，直接读取到 __m256i ，运算并输出：

cpp

	fread((uint64_t *)&a_256, sizeof(uint64_t), 3, stdin);
	fread((uint64_t *)&b_256, sizeof(uint64_t), 3, stdin);
	gf_add(c_256, a_256, b_256);
	fwrite((uint64_t *)&c_256, sizeof(uint64_t), 3, stdout);

cpp

	// c = a + b
	inline void gf_add(__m256i &c_256, const __m256i &a_256, const __m256i &b_256){
	c_256 = _mm256_xor_si256(a_256, b_256);
	}

# 取模

使用模:

$f(x)=x^{131}+x^{13}+x^{2}+x+1$

# Trival

首先我尝试了 trival 的做法，那就是对于输入 $e(x)$ 高于 $x^{130}$ 的每一位，都进行暴力的除法求出其 $e(x)/f(x)$ 的余部，余部加到 $e(x)$ 中，这样就消去了这一高位。如此至多执行 $260-130=130$ 次就可以完成求摸。

显然 $x^{131}$ 到 $x^{260}$ 的每一位对 $f(x)$ 除法的余部都是固定的，那么可以提前算出这些余部，实际取模的时候就只需要查表就可以了。如下是一个打印格式为 z^132 mod f(z) = ... 的输出 $x^{131}$ 到 $x^{260}$ 的每一位对 $f(x)$ 除法的余部的程序：

cpp

	#include <iostream>
	#include <vector>
	#include <numeric>
	#include <algorithm>
	#include <stdint.h>

	using namespace std;

	FILE output, input;
	const int k = 10;
	const int highest = 260;

	int highest_degree(uint64_t a[k]){
	for(int j=k - 1; j>=0; --j){
	for(int i=63; i>=0; --i){
	if(a[j] & (1ULL << i)){
	return 64 * j + i;
	}
	}
	}
	return -1;
	}

	// x^131 + x^13 + x^2 + x + 1
	void ls_mod(uint64_t t[k], int n){
	t[(131 + n) / 64] \|= 1ULL << ((131 + n) % 64);
	t[(13 + n) / 64] \|= 1ULL << ((13 + n) % 64);
	t[(2 + n) / 64] \|= 1ULL << ((2 + n) % 64);
	t[(1 + n) / 64] \|= 1ULL << ((1 + n) % 64);
	t[n / 64] \|= 1ULL << (n % 64);
	}


	void modular_reduction(uint64_t r[k], int h){
	while(h > 130){
	uint64_t t[k] = {0};
	ls_mod(t, h - 131);
	for(int i=0; i<k; ++i){
	r[i] ^= t[i];
	}
	h = highest_degree(r);
	}
	}


	int main(){
	output = freopen("reducted", "w", stdout);
	for(int i=131; i<=highest; ++i){
	uint64_t r[k] = {0};
	r[i / 64] ^= (1ULL << (i % 64));
	modular_reduction(r, i);
	printf("z^%d mod f(z) = ", i);
	for(int j=130; j>=0; --j){
	if(r[j / 64] & (1ULL << (j % 64))){
	printf("z^%d + ", j);
	}
	}
	fseek(output, -3, SEEK_END);
	fputc(' ', output);
	printf("\n");
	}
	fclose(output);
	return 0;
	}

类似的，调整输出格式可以直接复制粘贴到源代码中组成一个固定的数组常量 modular_reduction ：

cpp

	uint64_t modular_reduction[130][3] = {
	{ 0x0000000000002007, 0x0000000000000000, 0x0000000000000000 }, // x^131
	{ 0x000000000000400E, 0x0000000000000000, 0x0000000000000000 },
	{ 0x000000000000801C, 0x0000000000000000, 0x0000000000000000 },
	{ 0x0000000000010038, 0x0000000000000000, 0x0000000000000000 },
	{ 0x0000000000020070, 0x0000000000000000, 0x0000000000000000 },
	{ 0x00000000000400E0, 0x0000000000000000, 0x0000000000000000 },
	{ 0x00000000000801C0, 0x0000000000000000, 0x0000000000000000 },
	{ 0x0000000000100380, 0x0000000000000000, 0x0000000000000000 },
	{ 0x0000000000200700, 0x0000000000000000, 0x0000000000000000 },
	// ......
	{ 0x0000000001001807, 0x0000000000000000, 0x0000000000000006 }, // x^260
	};

取模运算查表版的 trival 实现：

cpp

	// mod x^131 + x^13 + x^2 + x + 1
	void gf_mod(uint64_t b[3], uint64_t e[5]){
	b_{0} = e[0];
	b_{1} = e[1];
	b_{2} = e[2];
	for(int i=260; i>130; --i){
	if(e[i / 64] & (1ULL << (i % 64))){
	b_{0} ^= modular_reduction[i - 131][0];
	b_{1} ^= modular_reduction[i - 131][1];
	b_{2} ^= modular_reduction[i - 131][2];
	}
	}
	b_{2} &= 7ULL;
	}

这里一共需要 $130\times3=390$ 次异或运算。

# 快速取模

参考 ECC2-131 的并行 Pollard rho 算法实现分析第 57 页的快速取模原理：

参考论文中的伪代码：

论文中快速取模算法伪码中的掩码 0xFFFFFFFFFFFFFFF8 错误，应该修改为 0xFFFFFFFFFFFFFFFC ，实现如下：

cpp

	// mod x^131 + x^13 + x^2 + x + 1
	inline void gf_mod(uint64_t b[4], uint64_t e[5]){
	uint64_t t;
	for(int i=4; i>=3; --i){
	t = e[i];
	e[i - 3] ^= (t << 61) ^ (t << 62) ^ (t << 63);
	e[i - 2] ^= (t << 10) ^ (t >> 1) ^ (t >> 2) ^ (t >> 3);
	e[i - 1] ^= (t >> 54);
	}
	t = e[2] & 0xFFFFFFFFFFFFFFF8;
	b_{0} = e[0] ^ (t << 10) ^ (t >> 1) ^ (t >> 2) ^ (t >> 3);
	b_{1} = e[1] ^ (t >> 54);
	b_{2} = e[2] & 0x7;
	}

# 乘法

# Trival

最 Trival 的做法就是自己手搓一个乘法，配合前面 Trival 版的取模的话，就可以在乘法实现的过程查表消去高位来取模。

cpp

	// c = a * b
	void gf_mul(uint64_t c[3], const uint64_t a[3], const uint64_t b[3]){
	uint64_t e[5] = {0};
	for(int i=0; i<131; ++i){
	for(int j=0; j<131; ++j){
	if(
	((1ULL << (i % 64)) & a[i / 64]) &&
	((1ULL << (j % 64)) & b[j / 64])
	){
	e[(i + j) / 64] ^= (1ULL << ((i + j) % 64));
	if (i + j < 131) {
	c[(i + j) / 64] ^= (1ULL << ((i + j) % 64));
	} else {
	c[0] ^= modular_reduction[i + j - 131][0];
	c[1] ^= modular_reduction[i + j - 131][1];
	c[2] ^= modular_reduction[i + j - 131][2];
	}
	}
	}
	}
	}

这里就需要做 $131\times131$ 次判断，性能相当的差，无法 AC。

# PCLMULQDQ 优化

_mm_clmulepi64_si128 指令可以将 2 个 64 位数相乘得到一个 128 位的数，这也是 64 位机器所能做的乘法，所以将数按 64 位分为 3 部分，有：

$a=a_{2}x^{128}+a_{1}x^{64}+a_{0}\\ b=b_{2}x^{128}+b_{1}x^{64}+b_{0}$

令 $M=x^{64}$ 有：

$a=a_{2}M^{2}+a_{1}M+a_{0}\\ b=b_{2}M^{2}+b_{1}M+b_{0}$

乘法有：

$\begin{aligned} a\times b&=(a_{2}M^{2}+a_{1}M+a_{0})\times(b_{2}M^{2}+b_{1}M+b_{0})\\ &=a_2b_2M^4+(a_2b_1+a_1b_2)M^3+(a_2b_0+a_0b_2+a_1b_1)M^2+(a_1b_0+a_0b_1)M+a_0b_0 \end{aligned}$

观察到 $a_ib_jM^k$ 满足 $i+j=k$ ，所以我自己实现的不经过优化的分组乘法如下：

cpp

	// c = a * b
	inline void gf_mul(uint64_t c[3], const uint64_t a[3], const uint64_t b[3]){
	uint64_t e[6] = {0};
	__m128i a_tmp, b_tmp, tmp;
	for(int i=0; i<3; ++i){
	a_tmp = _mm_set_epi64x(0, a[i]);
	for(int j=0; j<3; ++j){
	b_tmp = _mm_set_epi64x(0, b[j]);
	tmp = _mm_clmulepi64_si128(a_tmp, b_tmp, 0x00);
	e[i + j] ^= _mm_cvtsi128_si64(tmp);
	e[i + j + 1] ^= _mm_extract_epi64(tmp, 1);
	}
	}
	gf_mod(c, e);
	}

在这里一共做了 9 次 SMI 乘法、18 次异或运算。因为两个相乘数均被分为 3 部分，乘法一共需要进行 $3\times3=9$ 次，每次乘法得到 $a_ib_j$ 包含低 64 位和高 64 位两部分结果，需要分开加到乘法结果中，所以一共需要进行 $3\times3\times2=18$ 次异或运算。

实际上其中一个异或 $e_5=(a_2\times b_2)_{\text{high 64 bits}}$ 是不需要的，因为这一部分一定是 0，但是形式上保留的话会使代码更简洁。

# Karatsuba

参考论文中的伪代码：

我接着按照论文的伪代码实现了 Toom-cook 3-way 算法，或者说 Karatsuba 算法优化后的版本。这个优化的本质实际上就是通过增加加减法运算的次数，减少乘法运算的次数。对于分为 3 组的我们的情况，就可以将 9 次乘法运算减少到 6 次乘法运算。

优化原理在于，对于分组表示的数：

$a=a_{2}M^{2}+a_{1}M+a_{0}\\ b=b_{2}M^{2}+b_{1}M+b_{0}$

乘法运算有：

$\begin{aligned} a\times b=&(a_{2}M^{2}+a_{1}M+a_{0})\times(b_{2}M^{2}+b_{1}M+b_{0})\\ =&a_2b_2M^4+(a_2b_1+a_1b_2)M^3+(a_2b_0+a_0b_2+a_1b_1)M^2+(a_1b_0+a_0b_1)M+a_0b_0\\ =&a_2b_2M^4+\\ &[(a_1+a_2)(b_1+b_2)-a_1a_1-b_2b_2]M^3+\\ &[(a_0+a_2)(b_0+b_2)+a_1a_1-b_2b_2-a_0b_0]M^2+\\ &[(a_1+a_0)(b_1+b_0)-a_1a_1-b_0b_0]M+\\ &a_0b_0\\ \end{aligned}$

可以看到只需要进行 6 次乘法：

$a_0b_0$
$a_1b_1$
$a_2b_2$
$(a_1+a_2)(b_1+b_2)$
$(a_0+a_2)(b_0+b_2)$
$(a_1+a_0)(b_1+b_0)$

这里我的变量命名 a0xb0 表示 $a_{0}\times b_{0}$ ， a0a1xb0b1 表示 $(a_{0}+a_{1})\times(b_{0}+b_{1})$ 。我的实现如下：

cpp

	// c = a * b
	void gf_mul(uint64_t c[3], const uint64_t a[3], const uint64_t b[3]){
	__m128i a0xb0 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{0}), _mm_set_epi64x(0, b_{0}), 0);
	__m128i a1xb1 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{1}), _mm_set_epi64x(0, b_{1}), 0);
	__m128i a2xb2 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{2}), _mm_set_epi64x(0, b_{2}), 0);
	__m128i a0a1xb0b1 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{0} ^ a_{1}), _mm_set_epi64x(0, b_{0} ^ b_{1}), 0);
	__m128i a0a2xb0b2 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{0} ^ a_{2}), _mm_set_epi64x(0, b_{0} ^ b_{2}), 0);
	__m128i a1a2xb1b2 = _mm_clmulepi64_si128( _mm_set_epi64x(0, a_{1} ^ a_{2}), _mm_set_epi64x(0, b_{1} ^ b_{2}), 0);
	uint64_t e[5] = {
	(uint64_t) _mm_cvtsi128_si64(a0xb0),
	(uint64_t) _mm_cvtsi128_si64(a0xb0) ^ _mm_cvtsi128_si64(a1xb1) ^ _mm_cvtsi128_si64(a0a1xb0b1),
	(uint64_t) _mm_cvtsi128_si64(a0xb0) ^ _mm_cvtsi128_si64(a1xb1) ^ _mm_cvtsi128_si64(a2xb2) ^ _mm_cvtsi128_si64(a0a2xb0b2),
	(uint64_t) _mm_cvtsi128_si64(a1xb1) ^ _mm_cvtsi128_si64(a2xb2) ^ _mm_cvtsi128_si64(a1a2xb1b2),
	(uint64_t) _mm_cvtsi128_si64(a2xb2),
	// 0
	};
	e[1] ^= (uint64_t) _mm_extract_epi64(a0xb0, 1),
	e[2] ^= (uint64_t) _mm_extract_epi64(a0xb0, 1) ^ _mm_extract_epi64(a1xb1, 1) ^ _mm_extract_epi64(a0a1xb0b1, 1),
	e[3] ^= (uint64_t) _mm_extract_epi64(a0xb0, 1) ^ _mm_extract_epi64(a1xb1, 1) ^ _mm_extract_epi64(a2xb2, 1) ^ _mm_extract_epi64(a0a2xb0b2, 1),
	e[4] ^= (uint64_t) _mm_extract_epi64(a1xb1, 1) ^ _mm_extract_epi64(a2xb2, 1) ^ _mm_extract_epi64(a1a2xb1b2, 1),
	// e[5] ^= _mm_extract_epi64(a2xb2, 1),
	gf_mod(c, e);
	}

本来分组乘法，按照我上一个实现，应该需要 $e[6]$ 即 6 个 uint64_t 存储的，但是异或 $e_5=(a_2\times b_2)_{\text{high 64 bits}}$ 是不需要的，这一部分一定是 0，在这个实现中不必再保留它，所以被定义为了 5 个 uint64_t 。上面两行注释代表了这个被省略的第 6 个 uint64_t 。

然而，这里的优化并没有使我的程序变快，甚至会变慢，因为 PCLMULQDQ 指令的乘法本身就已经足够快了，即使减少了 3 个乘法，增加的大量赋值、异或运算开销已经抵消了 3 个乘法的优化，甚至拖慢了程序。

# 平方

# Trival

Trival 的做法就是复用乘法的实现，调用乘法运算即可：

cpp

	// c = a^2
	void gf_pow2(uint64_t c[3], const uint64_t a[3]){
	gf_mul(c, a, a);
	}

# PCLMULQDQ 优化

在乘法运算 PCLMULQDQ 实现的基础上，会发现平方运算中，分组乘法有一些项是会在模 2 加法运算下被 “抵消” 的，可以干脆不算：

$\begin{aligned} a\times a=&(a_{2}M^{2}+a_{1}M+a_{0})\times(a_{2}M^{2}+a_{1}M+a_{0})\\ =&a_2a_2M^4+(a_2a_1+a_1a_2)M^3+(a_2a_0+a_0a_2+a_1a_1)M^2+(a_1a_0+a_0a_1)M+a_0a_0\\ =&a_2^2M^4+a_1^2M^2+a_0^2 \end{aligned}$

所以优化后实现如下：

cpp

	// c = a^2
	inline void gf_pow2(uint64_t c[3], const uint64_t a[3]){
	uint64_t e[6] = {0};
	__m128i a_tmp, tmp;
	for(int i=0; i<6; i+=2){
	a_tmp = _mm_set_epi64x(0, a[i >> 1]);
	tmp = _mm_clmulepi64_si128(a_tmp, a_tmp, 0x00);
	e[i] ^= _mm_cvtsi128_si64(tmp);
	e[i \| 1] ^= _mm_extract_epi64(tmp, 1);
	}
	gf_mod(c, e);
	}

# 查表

注意到上一个实现中，将数字分组为 3 组的情况下，平方运算结果恰好为 3 个部分的平方和，只是各自有不同的位置。那么如果分组更小的话，例如一个分组为 8 位大小，那么便可以构造一个 $2^8=256$ 条记录的表，一次平方运算总共需要查表以及做对应的加法（异或） $\lceil\frac{131}{8}\rceil=17$ 次。

# 求逆

# 费马小定理

提交：#886

费马小定理的推论：任意 $F_{2^{m}}$ 上的 $x$ 逆满足：

$x^{-1}=x^{2^{131}-2}$

可以通过递归计算，本质上就是和快速幂一个原理：

$\begin{aligned} x^{-1}=&x^{2^{131}-2}\\ =&x^{2^{130}+2^{129}+\cdots+2^2+2}\\ =&(x^{2^{129}+2^{128}+\cdots+2^2+2}\cdot x)^2\\ &\cdots\\ =&((\cdots((x^2\cdot x)^2\cdot x)^2\cdots\cdots)^2\cdot x)^2 \end{aligned}$

于是令：

$T(s)=(s\cdot x)^2$

就有：

$x^{-1}=T^{129}(x^2)$

当然这个递归是可以转化为循环的，所以实现如下：

cpp

	// c = a^(-1)
	inline void gf_inv(uint64_t * c, const uint64_t a[3]){
	uint64_t t1[3], t2[3];
	gf_pow2(c, a);
	for(int i=0; i<129; ++i){
	copy(c, c + 3, t2);
	gf_mul(t1, t2, a);
	gf_pow2(c, t1);
	}
	}

# 扩展欧几里得

提交：#917

参考 ECC2-131 的并行 Pollard rho 算法实现分析第 40 页的伪代码：

实现如下：

cpp

	// c = a ^ (-1)
	inline void gf_inv(uint64_t * c, const uint64_t a[3]){
	uint64_t va[3] = {0x2007, 0, 0x8};
	uint64_t ua[3] = {a[0], a[1], a[2]};
	uint64_t g2a[3] = {0};
	uint64_t g1a[3] = {1, 0, 0};
	uint64_t * v = va;
	uint64_t * u = ua;
	uint64_t * g1 = g1a;
	uint64_t * g2 = g2a;
	while((u[2] != 0) \|\| (u[1] != 0) \|\| (u[0] != 1)){
	int j = gf_degree(u) - gf_degree(v);
	if(j < 0){
	swap(u, v);
	swap(g1, g2);
	j = -j;
	}
	gf_lsk(c, v, j);
	gf_add_eq(u, c);
	gf_lsk(c, g2, j);
	gf_add_eq(g1, c);
	}
	copy(g1, g1 + 3, c);
	}

其中 gf_add_eq 实现类似 += 赋值功能：

cpp

	// a += b
	inline void gf_add_eq(uint64_t a[5], const uint64_t b[5]){
	a[0] ^= b[0];
	a[1] ^= b[1];
	a[2] ^= b[2];
	}

gf_degree 返回输入数的最高位的位置

cpp

	// highest digit, 0 <= d <= 131
	inline int gf_degree(const uint64_t a[5]){
	int d = 131;
	while( ! (a[d / 64] & (1ULL << (d % 64)))) d--;
	return d;
	}

gf_lsk 返回输入数据左移 k 位的结果，这里保证左移后的结果都是最高位不超过 $x^{131}$ 的：

cpp

	// left shif k digits, 0 <= k <= 130
	inline void gf_lsk(uint64_t c[3], const uint64_t a[3], int k){
	if(k == 0) {
	c[0] = a[0];
	c[1] = a[1];
	c[2] = a[2];
	return;
	}
	int i = k / 64;
	int j = k % 64;
	switch(i){
	case 0:
	c[0] = a[0] << j;
	c[1] = (a[0] >> (64 - j)) \| (a[1] << j);
	c[2] = (a[1] >> (64 - j)) \| (a[2] << j);
	break;
	case 1:
	c[0] = 0;
	c[1] = a[0] << j;
	c[2] = (a[0] >> (64 - j)) \| (a[1] << j);
	break;
	case 2:
	c[0] = 0;
	c[1] = 0;
	c[2] = a[0] << j;
	}
	}

仿射希尔密码

2024-10-05T00:00:00.000Z

封面是《崩坏・星穹铁道》的希儿，但我并不是崩坏玩家，只是觉得好看，原图 pid 为 109714317。

# 破解原理

以下运算均为模 26 意义下

# 转化为方程问题

仿射希尔密码中定义密钥包括一个矩阵 $L$ 和一个向量 $\vec b$ :

L=\begin{pmatrix} l_{11} & l_{12} & \cdots & l_{1m}\\ l_{21} & l_{22} & \cdots & l_{2m}\\ \vdots & \vdots & & \vdots\\ l_{m1} & l_{m2} & \cdots & l_{mm} \end{pmatrix} \ ,\ \ \vec b=\begin{pmatrix} b_{1}\\ b_{2}\\ \vdots\\ b_{m} \end{pmatrix}\\

给定的明文首先字母转化为在模 26 下的数，然后每连续 $m$ 个数分为一组，每一组数组成一个长度为 $m$ 的向量 $\vec x$ ，将其经过如下运算：

$\vec x\cdot L+\vec b=\vec y$

得到的向量 $\vec y$ 再转化为对应的字母，就是一段属于密文的分组。所有明文分组按顺序运算，得到的密文分组按同样的顺序拼接，就得到了密文。

仿射希尔密码在现代的选择明文、选择密文攻击下是不安全的，只要攻击方：

利用统计规律或其他手段得到了分组长度 $m$ ；
获取了足够多的明文密文对；

这些明文密文对实际上就能依据 $m$ 分组得到一系列形如 $\vec x\cdot L+\vec b=\vec y$ 的方程，只要方程足够多（足够好），那么就能解出其中的 $L$ 和 $\vec b$ 。

接下来的分析在如下假设的场景下进行：

已知分组长度 $m$ ；
已知明文密文对的长度 $len$ $l e n$ 满足 $len\geq 2m^2$ $l e n \geq 2 m 2$ ；
- 换句话说如上两个条件保证了给出刚好 $n=len\div m\geq2m$ 个形如 $\vec x\cdot L+\vec b=\vec y$ 的方程。
给出的明文密文对一定是有解的

于是问题转化为已知 $n$ 个方程：

$\begin{aligned} \vec x_{1}\cdot L+\vec b&=\vec y_{1}\\ \vec x_{2}\cdot L+\vec b&=\vec y_{2}\\ &\cdots\\ \vec x_{n}\cdot L+\vec b&=\vec y_{n} \end{aligned}$

求解矩阵 $L$ 和向量 $\vec b$ 。

也可以写成：

$\begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1m}\\ x_{21} & x_{22} & \cdots & x_{2m}\\ \vdots & \vdots & & \vdots\\ x_{m1} & x_{m2} & \cdots & x_{mm}\\ \vdots & \vdots & & \vdots\\ x_{(2m)1} & x_{(2m)2} & \cdots & x_{(2m)m}\\ \vdots & \vdots & & \vdots\\ x_{n1} & x_{n2} & \cdots & x_{nm} \end{pmatrix} \begin{pmatrix} l_{11} & l_{12} & \cdots & l_{1m}\\ l_{21} & l_{22} & \cdots & l_{2m}\\ \vdots & \vdots & & \vdots\\ l_{m1} & l_{m2} & \cdots & l_{mm} \end{pmatrix} + \begin{pmatrix} b_{1} & b_{2} & \cdots & b_{m}\\ b_{1} & b_{2} & \cdots & b_{m}\\ \vdots & \vdots & & \vdots\\ \vdots & \vdots & & \vdots\\ \vdots & \vdots & & \vdots\\ \vdots & \vdots & & \vdots\\ b_{1} & b_{2} & \cdots & b_{m} \end{pmatrix} = \begin{pmatrix} y_{11} & y_{12} & \cdots & y_{1m}\\ y_{21} & y_{22} & \cdots & y_{2m}\\ \vdots & \vdots & & \vdots\\ y_{m1} & y_{m2} & \cdots & y_{mm}\\ \vdots & \vdots & & \vdots\\ y_{(2m)1} & y_{(2m)2} & \cdots & y_{(2m)m}\\ \vdots & \vdots & & \vdots\\ y_{n1} & y_{n2} & \cdots & y_{nm} \end{pmatrix}$

# 思路一

这一方法基于常规的方阵矩阵方程解法，对于如下形式的矩阵方程：

$X\cdot L = Y$

最直接的解法就是对 $X$ 求逆：

$L=X^{-1}\cdot Y$

回到原来的问题，在 $n\geq 2m$ 的背景下，对 $n$ 个方程暴力枚举的抽出 $2m$ 个方程，排列组成两个 $m$ 阶方阵的方程:

$X1\cdot L+B=Y1\\ X2\cdot L+B=Y2$

做差消掉 $B$ ，得到齐次方程:

$(X1-X2)\cdot L=Y1-Y2$

然后检查些向量组成的矩阵 $(X1-X2)$ 是否可逆，若不可逆就继续枚举下一个，可逆就能算出答案:

$L=(X1-X2)^{-1}\cdot(Y1-Y2)\\$

$B = Y1-X1\cdot L$

其中 $B$ 是每一行均为 $\vec b$ 的方阵。

在这个算法的基础上，从 $n$ 个方程里面选 $2m$ 个没什么问题，就是 $C_{n}^{2m}$ ，但是这 $2m$ 个向量在 $(X1-X2)$ 中的排列分布对 $(X1-x2)$ 是否可逆是有影响的，这是经过尝试验证的。

具体步骤如下：

暴力枚举 $C_{n}^{m}$ 选， $n$ 个向量不排列组成 $X1$ 。
暴力枚举 $X_{m}^{n-m}$ 排列 $m$ 个向量组成 $X2$ 。
检查 $(X1-X2)$ 是否可逆。

这个做法不太好，比较慢，这一过程还能优化吗？

# 思路二

这一方法基于非方阵矩阵方程的最小二乘法解法，对于如下形式的矩阵方程， $X$ ， $Y$ 不再是方阵：

$X\cdot L = Y$

解形式为：

$L = (X^{T}X)^{-1}X^{T}Y$

这里要求 $(X^{T}X)$ 可逆。这就和上一个思路要求 $(X1-X2)$ 可逆很像。

在这种情况下，求解用的矩阵 $X$ 的行数不再有限制，而且当然越多越好，越能保证最终是可逆的。那么干脆就用上所有 $n$ 个方程，就让 $X$ 的行数为 $n$ 。但是还需要消去 $\vec b$ ，经过尝试发现消去 $\vec b$ 所用的方程也会影响最终 $(X^{T}X)$ 的可逆性。那么这里也需要暴力枚举各种排列组合了么？

为了比上一个思路更快，尝试在这一步随机选择消去 $\vec b$ 所用的方程，实践发现随机选取得到的 $(X^{T}X)$ 是可逆的情况是稠密的，总是能够很快求解成功。

# 思路三

只是想法，并没有实现

依然是基于非方阵矩阵方程的求解。

实际上，目前我已知的非方阵矩阵方程的求解就只有两种办法:

最小二乘法
奇异值分解 (SVD)(伪逆)

那么采取奇异值分解，或者说伪逆的办法也是可以的。

对于一个任意的矩阵 $X$ （大小为 $n \times m$ ），可以进行奇异值分解：

$X = U \Sigma V^T$

其中：

$U$ 是一个 $n \times n$ 的正交矩阵，列向量是 $XX^T$ 的特征向量
$\Sigma$ 是一个 $n \times m$ 的对角矩阵，包含 $X$ 的奇异值
$V^T$ 是一个 $m \times m$ 的正交矩阵，，列向量是 $X^TX$ 的特征向量

伪逆 $X^+$ 可以通过 SVD 得到：

$X^+ = V \Sigma^+ U^T$

其中 $\Sigma^+$ 是将 $\Sigma$ 中的非零奇异值取倒数并转置后得到的矩阵。在模 26 的意义下应当是取逆。

这里实际上有一个问题就是是否所有的奇异值都是可逆的

对于如下形式的矩阵方程， $X$ ， $Y$ 不再是方阵：

$X\cdot L = Y$

其解形式为：

$L = X^+Y$

当 $X$ 的秩 $r$ 小于 $\min(m, n)$ 时， $X^+$ 仍然是有效的，但解可能不唯一。在我们的应用中，保证有解的条件下应该是唯一的。

# 代码实现

# Common

# 矩阵运算

所有的运算均模 26 意义下，所以可以先定义：

cpp

const int MOD = 26;

为了方便和加快求逆，可以直接定义一个数组作为取逆表，使得下标作为输入就能得到结果，若结果为 0 就表示不可逆：

cpp

	const int inversetable[26] = {
	0, 1, 0, 9, 0, 21, 0, 15, 0, 3, 0, 19, 0,
	0, 0, 7, 0, 23, 0, 11, 0, 5, 0, 17, 0, 25
	};

计算行列式：

cpp

	int determinant(const vector<vector<int>>& matrix) {
	int n = matrix.size();
	if (n == 1) return matrix[0][0] % MOD;

	int det = 0;
	for (int p = 0; p < n; p++) {
	vector<vector<int>> submatrix(n - 1, vector<int>(n - 1));
	for (int i = 1; i < n; i++) {
	int sub_j = 0;
	for (int j = 0; j < n; j++) {
	if (j == p) continue;
	submatrix[i - 1][sub_j++] = matrix[i][j];
	}
	}
	det += (p % 2 == 0 ? 1 : -1) * matrix[0][p] * determinant(submatrix);
	}
	return (det % MOD + MOD) % MOD; // 确保是正数
	}

计算伴随矩阵：

cpp

	vector<vector<int>> adjugate(const vector<vector<int>>& matrix) {
	int n = matrix.size();
	vector<vector<int>> adj(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	vector<vector<int>> submatrix(n - 1, vector<int>(n - 1));
	int sub_i = 0;
	for (int row = 0; row < n; row++) {
	if (row == i) continue;
	int sub_j = 0;
	for (int col = 0; col < n; col++) {
	if (col == j) continue;
	submatrix[sub_i][sub_j++] = matrix[row][col];
	}
	sub_i++;
	}
	adj[j][i] = ((i + j) % 2 == 0 ? 1 : -1) * determinant(submatrix) % MOD;
	adj[j][i] = (adj[j][i] + MOD) % MOD; // 确保是正数
	}
	}
	return adj;
	}

以行列式的逆和原矩阵作为输入计算逆矩阵。这里将行列式的逆解耦出来是为了方便先判断方阵是否可逆，再计算逆：

cpp

	vector<vector<int>> inverse(const vector<vector<int>>& matrix, int det_inv) {
	int n = matrix.size();
	vector<vector<int>> adj = adjugate(matrix);
	vector<vector<int>> inv(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	inv[i][j] = (adj[i][j] * det_inv) % MOD;
	inv[i][j] = (inv[i][j] + MOD) % MOD;
	}
	}
	return inv;
	}

矩阵乘法：

cpp

	vector<vector<int>> multiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
	int rowsA = A.size();
	int colsA = A[0].size();
	int colsB = B[0].size();
	vector<vector<int>> C(rowsA, vector<int>(colsB, 0));
	for (int i = 0; i < rowsA; i++) {
	for (int j = 0; j < colsB; j++) {
	for (int k = 0; k < colsA; k++) {
	C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
	}
	}
	}
	return C;
	}

矩阵减法：

cpp

	vector<vector<int>> sub(const vector<vector<int>>& A, const vector<vector<int>>& B) {
	int rowsA = A.size();
	int colsB = B[0].size();
	vector<vector<int>> C(rowsA, vector<int>(colsB, 0));
	for (int i = 0; i < rowsA; i++) {
	for (int j = 0; j < colsB; j++) {
	C[i][j] = (A[i][j] - B[i][j] + MOD) % MOD;
	}
	}
	return C;
	}

# 处理输入输出

为了方便观察算法效率，在输出的时候增加输出算法运行时间。同时还希望以文件流进行输入输出方便测试和观察。

假定在线测评平台使用 -DONLINE_JUDGE 参数，可以在源代码中这样处理：

cpp

	#ifndef ONLINE_JUDGE
	#include <chrono>
	#include <iomanip>
	FILE output, input;
	chrono::time_point<std::chrono::high_resolution_clock> start_time, end_time;
	#endif

	// ......

	int main(){
	#ifndef ONLINE_JUDGE
	output = freopen("output", "w", stdout); // 重定向标准输出流
	input = freopen("input", "r", stdin); // 重定向标准输入流
	start_time = chrono::high_resolution_clock::now();
	#endif

	// 代码主体

	#ifndef ONLINE_JUDGE
	fclose(input);
	end_time = chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
	cout << endl << endl
	<< "time: "
	<< fixed << setprecision(3)
	<< duration.count() << " ms";
	fclose(output);
	#endif

	return 0;
	}

要求输入为 3 行：

第一行为数字代表 $m$
第二行为明文
第三行为密文

明文密文全部都是大写字母，长度 $len$ 相同且满足 $len\geq 2m^2$ ；

因此可以先将明文，密文分别存到字符串中，后续再依据算法处理。

cpp

	string m_s, s, c;
	getline(cin, m_s);
	getline(cin, c);
	getline(cin, s);

	int len = s.size();
	int m = stoi(m_s);

打印矩阵，从而输出密钥 $L$ ：

cpp

	void printMatrix(const vector<vector<int>>& A){
	int m = A[0].size();
	for (const auto& row : A) {
	for (int i = 0; i < m - 1; ++i) {
	cout << row[i] << " ";
	}
	cout << row[m - 1] << endl;
	}
	}

输出 $\vec b$ 需要单独输出一个向量。假定已经通过 $B = Y1-X1\cdot L$ 得到了矩阵 $B$ ：

cpp

	for (int i = 0; i < m - 1; ++i) {
	cout << B[0][i] << " ";
	}
	cout << B[0][m - 1];

# 思路一

# 存储向量和矩阵

定义全局变量：

cpp

	vector<vector<int>> x;
	vector<vector<int>> y;
	vector<vector<int>> X;
	vector<vector<int>> Y;
	vector<vector<int>> X1;
	vector<vector<int>> Y1;
	vector<vector<int>> X2;
	vector<vector<int>> Y2;
	int m = 0, n=0, det_inv = 0;

存储的形式是全局变量，这样递归的时候更方便。

这里 x 和 y 分别存储了 $n$ 个向量，每一对向量分别代表一个 $\vec x\cdot L + \vec b=\vec y$ 中的向量。这是为了排列组合的时候方便选取指定的方程。

这里 m , n , det_inv 也是全局变量，也是为了方便递归。

另外几个矩阵的关系是：

$Y=Y1-Y2\\ X=X1-X2$

通过如下方式从明文和密文中提取 $n$ 对向量：

cpp

	for(int i=0; i < len; i+=m){
	x.push_back(vector<int>());
	y.push_back(vector<int>());
	for(int j=0; j<m; ++j){
	x[i / m].push_back(c[i + j] - 'A');
	y[i / m].push_back(s[i + j] - 'A');
	}
	}
	n = x.size();

# 递归

$n$ 个里面选 $m$ 对向量组合作为 X1 和 Y1 ，定义返回值：

0 表示找到了可逆的 $(X1-X2)$ ，递归结束。
1 表示还没有找到

后面的函数返回值都是与此相同的定义。

cpp

	int combi(int n, int m, int start, vector<int>& combination) {
	if (combination.size() == (long unsigned int)m) {
	return after_combi(combination);
	}
	for (int i = start; i < n; ++i) {
	combination.push_back(i);
	if(combi(n, m, i + 1, combination) == 0)return 0;
	combination.pop_back();
	}
	return 1;
	}

对每一个组合，执行如下函数，存储 X1 和 Y1 ，并开始递归寻找剩余 $n-m$ 对向量的 $m$ 排列来组成 X2 和 Y2

cpp

	int after_combi(vector<int>& combination){
	vector<int> remain(n);
	iota(remain.begin(), remain.end(), 0);
	for(int i=0; i < m; ++i){
	X1[i] = x[combination[i]];
	Y1[i] = y[combination[i]];
	remain.erase(remove(remain.begin(), remain.end(), combination[i]), remain.end());
	}
	vector<bool> used(n, false);
	vector<int> current;
	return permu(remain, current, used, m);
	}

$n$ 个数 $k$ 排序的递归实现

cpp

	int permu(vector<int>& nums, vector<int>& current, vector<bool>& used, int k) {
	if ((int)current.size() == k) {
	return after_permu(nums);
	}
	for (size_t i = 0; i < nums.size(); ++i) {
	if (!used[i]) {
	used[i] = true;
	current.push_back(nums[i]);
	if(permu(nums, current, used, m) == 0)return 0;
	used[i] = false;
	current.pop_back();
	}
	}
	return 1;
	}

在递归的最后，存储 X2 和 Y2 ，判断 $(X1-X2)$ 是否可逆：

可逆则可以输出结果并返回 0 以中断结束递归
否则返回 0 继续递归

cpp

	int after_permu(vector<int>& permutation){
	for(int i=0; i < m; ++i){
	X2[i] = x[permutation[i]];
	Y2[i] = y[permutation[i]];
	}
	X = sub(X2, X1);
	det_inv = inversetable[determinant(X)];
	if (det_inv == 0 ) return 1;
	Y = sub(Y2, Y1);
	vector<vector<int>> L = multiply(inverse(X, det_inv), Y);
	vector<vector<int>> B = sub(Y1, multiply(X1, L));

	// 输出结果......

	return 0;
	}

在 main 函数最后调用 combi 开始递归。

# 思路二

# 存储矩阵

定义如下变量：

cpp

	vector<vector<int>> X = vector<vector<int>>(n, vector<int>(m));
	vector<vector<int>> Y = vector<vector<int>>(n, vector<int>(m));
	vector<vector<int>> X_T = vector<vector<int>>(m, vector<int>(n));
	vector<vector<int>> X1 = vector<vector<int>>(m, vector<int>(m));
	vector<vector<int>> Y1 = vector<vector<int>>(m, vector<int>(m));
	vector<vector<int>> XTX;
	int m = 0, n=0, det_inv = 0;

X 和 Y 均为 $n\times m$ 的矩阵。
X_T 是 $m\times n$ 的矩阵，代表 $X^{T}$ 。
XTX 是 $m\times m$ 的矩阵，代表 $X^{T}X$ 。
X1 和 Y1 仍然为 $m\times m$ 的矩阵，用来计算 $B$ 。

# 计算

循环反复地随机生成 X 和 Y ，直到得到的 $X^{T}X$ 可逆为止。

cpp

	// #include <random>

	random_device rd;
	mt19937 gen(rd());
	uniform_int_distribution<> dis(0, n - 1);

	while(det_inv == 0){
	for(int i = 0; i < n; ++i){
	int d = dis(gen);
	for(int j = 0; j < m; ++j){
	X[i][j] = (c[i * m + j] - c[ d * m + j ] + MOD) % MOD;
	Y[i][j] = (s[i * m + j] - s[ d * m + j ] + MOD) % MOD;
	X_T[j][i] = X[i][j];
	}
	}
	XTX = multiply(X_T, X);
	det_inv = inversetable[determinant(XTX)];
	}

	vector<vector<int>> L = multiply(multiply(inverse(XTX, det_inv), X_T), Y);
	vector<vector<int>> B = sub(Y1, multiply(X1, L));

	// 输出结果......

# 测试

# 随机生成测试数据

借用 SageMath 中的 HillCryptosystem 类可以方便地生成随机的希尔密码测试数据，但是 SageMath 不支持仿射希尔密码。

SageMath

	from sage.all import *
	import random
	import string

	m = 5 # 分组长度 m
	n = 12 # 分组数量 n
	A = AlphabeticStrings()
	H = HillCryptosystem(A, Integer(m))
	K = H.random_key()
	e = H(K)
	print(K) # 输出随机密钥矩阵

	c = A(''.join(random.choices(string.ascii_uppercase, k = m * n)))

	print(m) # 输出一行分组长度 m
	print(c) # 输出一行随机明文 c
	print(e(c)) # 输出一行对应密文 s

python 的 cryptography 库也一样，虽然支持希尔密码但是不支持仿射希尔密码。

# 评价

只考虑 $m\leq5$ 的情况，再大的情况可能耗时更长暂不考虑。

这个实验作业的输入条件如此

在 $n$ 和 $2m^2$ 的差值小于等于 $1$ 时，思路一和思路二实现的破解速度几乎没有差别。

当 $n$ 和 $2m^2$ 的差值提升时，思路一寻找组合排列的时间复杂度大幅提升，这时候思路二的代码可以比思路一快上万倍，考虑到思路一的实现是递归，实际上函数调用栈较深也会影响性能。

然而，当 $n$ 和 $2m^2$ 的差值提升时，思路一的时间复杂度大幅降低，二者就又变得一样快了，猜测是因为这种情况下更容易找到线性无关的向量对 $\vec x$ 和 $\vec y$ ，使得所需的矩阵可逆。

思路二的速度几乎不受输入的情况影响，总的来说更稳定效果更好。但是思路一输入条件特别简单的时候速度还是比思路二要好的。

维吉尼亚密码

2024-09-19T00:00:00.000Z

# 破解原理

Kasiski 测试法：
- 找到所有可能的周期 m
指数重合法：
- 在备选周期中找到最有可能的周期
- 在确定周期后用来确定密钥

# 代码实现

这只是一个作业，用来完成在线测评，在这里输入假定：

$\text{密文长度}:\text{密钥长度} > 50:1$

# 处理输入输出

传统的维吉尼亚密码都是允许大小写，并且大小写统一在 $\mathbb{z}_{26}$ 空间加密解密，其他空格、换行、标点符号均不参与加密，输出时须保留其原样。

cpp

	int main(){
	vector<char> input;
	vector<char> c;
	int input_l=0, c_l=0;
	char tmp;
	while(fread(&tmp, sizeof(char), 1, stdin)){
	input.push_back(tmp);
	if((tmp <= 'Z' && tmp >= 'A') \|\| (tmp <= 'z' && tmp >= 'a')){
	c.push_back(tmp);
	c_l += 1;
	}
	input_l += 1;
	}

	// 破解获取密钥 K

	// 解密并输出
	}

在这里使用了两个 vector<char> 存储了：

包括空格、换行、标点符号的完整原文 input
去除了空格、换行、标点符号的密文 c

# 寻找可能的周期

维吉尼亚密码的破解经验来看，在密文中长度为 3 的相同密文段的距离以及它们的所有因数都可以作为可能的周期，当然 1 除外。在实践中，这样的相同密文段往往是存在的，并且并不稀疏，而长度为 4 开始就非常稀疏难以找到了。

在这里只考虑长度为 3 的相同密文段，没有任何其他优化直接暴力枚举所有长度为 3 的密文段。为了防止重复，使用集合存储它们的距离。

cpp

	string c_s(c.begin(), c.end());
	set<int> candidates;
	for(int i=0;i<c_l-2;++i){
	string substr = c_s.substr(i, 3);
	size_t found = c_s.substr(i + 2, c_l - i).find(substr);
	if(found != string::npos){
	int tmp = abs(i-(int)found);
	candidates.insert(tmp);
	}
	}

# 确定最有可能的周期

对每一个备选周期，包括刚刚求出的一系列距离以及它们的因数，按照备选周期 candidate = m 将密文 c 在分为 candidate 段：

$\begin{aligned} y_1&=y_1y{m+1}y_{2m+1}\cdots\\ y_2&=y_2y{m+2}y_{2m+2}\cdots\\ &......\\ y_m&=y_my{2m}y_{3m}\cdots \end{aligned}$

对每一个长度为 $l_{y_i}$ 的 $y_i$ ，统计出 26 个字母各自的出现频数 $f_j$ ，计算 $M_i$ 如下：

$\frac{\sum_{j=0}^{25}f_j\cdot(f_j-1)}{l_{y_i}\cdot(l_{y_i}-1)}$

其中 $p_i$ 是统计出来的英语书面语 26 个字母的出现频率。通过常量定义如下：

cpp

	const double FREQ[26] = {
	0.082, 0.015, 0.028, 0.043,
	0.127, 0.022, 0.020, 0.061,
	0.070, 0.002, 0.008, 0.040,
	0.024, 0.067, 0.075, 0.019,
	0.001, 0.060, 0.063, 0.091,
	0.028, 0.010, 0.023, 0.001,
	0.020, 0.001
	};

计算出来的 $M_i$ 将会和实际英语书面语的重合指数比较，重合指数的计算如下，假设大量样本得到的文本长度为 $l$ ，26 个字母各自的出现为频数 $f_j$ ：

$\frac{\sum_{j=0}^{25}p_j\cdot(p_j-1)}{l\cdot(l-1)}\approx\sum_{j=0}^{25}p_j^2=0.065$

认为越接近这个数值的 $M_i$ ，那么对应的周期 m 越有可能是正确的密钥长度。

同时这里假定密文和密钥的比例不小于 $50:1$ ，所以根据密文长度可以筛选掉一些太长的备选周期，而且实际允许程序发现有一些错误的密钥长度下计算的 $M_i$ 比真正的密钥长度还接近 $0.065$ ，这一筛选可以提高破解准确率。

cpp

	int m = c_l / 50;
	double idx_avg_best_diff = 1;
	vector<string> y_vec;
	vector<vector<int> > y_freq;
	for(int candidate: candidates){
	for (int factor = 2; factor <= candidate; ++factor) {
	if (candidate % factor == 0 && factor * 50 < c_l) {
	vector<string> y_vec_tmp(factor);
	vector<vector<int> > y_freq_tmp(factor, vector<int>(26, 0));
	for(int i=0;i<c_l;++i){
	y_vec_tmp[i % factor].push_back(c[i]);
	if(c[i] - 'a' >= 0){
	y_freq_tmp[i % factor][c[i] - 'a'] += 1;
	} else {
	y_freq_tmp[i % factor][c[i] - 'A'] += 1;
	}
	}
	double M_avg = 0;
	for(int i=0;i<factor;++i){
	double M = 0;
	for(int j=0;j<26;++j){
	M += y_freq_tmp[i][j] * (y_freq_tmp[i][j] - 1);
	}
	M /= y_vec_tmp[i].length() * (y_vec_tmp[i].length() - 1);
	M_avg += M;
	}
	M_avg /= factor;
	double idx_avg_diff = abs(M_avg - 0.065);
	if(idx_avg_diff < idx_avg_best_diff){
	m = factor;
	idx_avg_best_diff = idx_avg_diff;
	y_vec = y_vec_tmp;
	y_freq = y_freq_tmp;
	}
	}
	}
	}

# 确定密钥

在确定了密钥长度 m 之后，维吉尼亚加密就被分解为了 m 个单表移位加密，所以接下来的步骤实际上就是进行 m 次单表移位破解， m 个单表加密密文就是依据周期 m 划分的密文段 $y_1,y_2,\cdots y_m$ 。

对每一个密文段 $y_i$ ，依然采用计算重合指数的方式，对所有 26 种可能的偏移都进行一次解密，对得到的明文段的重合指数最接近 $0.065$ 的就是真正的偏移，其偏移量对应的字母构成了密钥。

在这里我们不需要真的进行 26 次解密，只是对 26 种偏移后的文段计算重合指数就行：

$M_i=\sum_{j=0}^{25}\frac{p_j\cdot f_{j+i}}{l_{y_i}}$

cpp

	vector<int> K(m,0);
	for(int k=0;k<m;++k){
	double M_best_diff = 1;
	for(int i=0;i<26;++i){
	double M = 0;
	for(int j=0;j<26;++j){
	M += FREQ[j] * y_freq[k][(j + i) % 26];
	}
	M /= y_vec[k].size();
	M /= m;
	double M_diff = abs(M - 0.065);
	if(M_diff < M_best_diff){
	M_best_diff = M_diff;
	K[k] = i;
	}
	}
	}

# 解密

到此为止，就得到了密钥 K ，解密并输出的过程如下：

cpp

	for(int i=0; i<input_l; ++i){
	if((input[i] <= 'Z' &&input[i] >= 'A') \|\| (input[i] <= 'z' &&input[i] >= 'a')){
	if(c[j] - 'a' >= 0){
	tmp = 'a' + (c[j] -'a' - K[j % m] + 52) % 26;
	} else {
	tmp = 'A' + (c[j] -'A' - K[j % m] + 52) % 26;
	}
	fwrite(&tmp, sizeof(char), 1, stdout);
	j++;
	} else {
	fwrite(&input[i], sizeof(char), 1, stdout);
	}
	}

这样将保留输入的空格、换行、标点符号等得到可读的明文。

# 缺陷

这个程序在测试中对于如下输出：

input

	S lotabgy kqmasbaew qy n eizuwuggakgy kknrem lbj dkeanevfo zuw
	iagzmtgakogq wl qaoogst srkagtwa ue vwihemtgk. I bndqj qaoogst
	yvyvggmzk bf i srkagtw ooiwa g ewkocamtg uwtsalkaum zusb zuw
	ukfkimr uisr xzuz s akavmx xfwca lw zuw zkpaxorfb.

	Jvyqznd aotfizhjmy njm g flitqszj rdmsrfb us ewyg uzeclwmesxnvu
	xxblwibd aavlmy, nfl gew kuzewtyq cyrv nue kwlgoixr
	vqygjqhhlqua, xqtnfkond bxnfagplquak, kualzgpl ugasokzwvz
	fgnzjszk, nfl oa gbnrj kgfwa cuwzk vl qy vexuelitg lw jrlmig
	xwxtwze bj bgzhmxvfo.

破解得到的密钥为： SIGNSIGN 。

这当然是正确的，但是在线测评系统可不这么认为，它认为正确的密钥应该是： SIGN 。在这个程序的计算中， SIGNSIGN 划分和计算得到的重合指数比 SIGN 还要接近 $0.065$ ！

这就相当麻烦了，如果硬要过测评为目的，那么还需要判断密钥是否是周期的，需要 KMP 算法找出最小周期子串。

所幸，这次出现这个情况的测试用例是输入输出示例，所以我硬编码处理了这个情况来 AC

在 Linux 上安装 SQL Server

2024-09-09T00:00:00.000Z

本文记录了在 Ubuntu 22.04 上安装 Microsoft SQL Server (mssql-server) 2022，实践中可以用于《MySQL 数据库技术与实验指导》作为实验教材的实验课程中。

官方教程

# 安装 mssql-server

按照官方文档，在 Ubuntu 上可以使用 APT 直接安装二进制库。安装过程如下：

导入 Microsoft 的 GPG 密钥 microsoft.asc

shell

curl -fsSL https://packages.microsoft.com/keys/microsoft.asc | sudo gpg --dearmor -o /usr/share/keyrings/microsoft-prod.gpg

再次下载密钥保存到 /etc/apt/trusted.gpg.d/ 目录下，APT 用它来验证软件包的签名

shell

curl https://packages.microsoft.com/keys/microsoft.asc | sudo tee /etc/apt/trusted.gpg.d/microsoft.asc

添加 mssql-server 软件包源到 APT 软件包源列表

shell

curl -fsSL https://packages.microsoft.com/config/ubuntu/22.04/mssql-server-2022.list | sudo tee /etc/apt/sources.list.d/mssql-server-2022.list

这一步会产生如下的报错：

shell

Failed to fetch https://packages.microsoft.com/ubuntu/22.04/mssql-server-2022/dists/jammy/InRelease

反而按照 Ubuntu 20.04 的步骤，换成 add-apt-repository 就不会报错：

shell

sudo add-apt-repository "$(wget -qO- https://packages.microsoft.com/config/ubuntu/20.04/mssql-server-2022.list)"

如果还有报错，可以参考这里。

通过 APT 安装 mssql-server

shell

	sudo apt-get update
	sudo apt-get install -y mssql-server

然后，由于 Ubuntu 22.04 缺少如下 2 个二进制库，在接下来安装的过程会出现这样的报错：

shell

error while loading shared libraries: libldap-2.4.so.2: cannot open shared object file: No such file or directory.

# or

error while loading shared libraries: libssl.so.1.1: cannot open shared object file: No such file or directory.

所以需要手动安装这两个库：

shell

sudo dpkg -i $(wget -qO- http://http.us.debian.org/debian/pool/main/o/openldap/libldap-2.4-2_2.4.47+dfsg-3+deb10u7_amd64.deb)

sudo dpkg -i $(wget -qO- http://nz2.archive.ubuntu.com/ubuntu/pool/main/o/openssl/libssl1.1_1.1.1f-1ubuntu2.22_amd64.deb)

初始化 SQL Server 实例

shell

sudo /opt/mssql/bin/mssql-conf setup

启动后选择版本安装。Microsoft 提供了 3 个免费版本：

Evaluation
Developer
Express

安装过程将会为实例的初始默认账号 sa 定义密码，之后第一次须使用用户名 sa 和自定义密码才能连接实例。

# 安装本地命令行工具

接下来，要想在 Linux 上本地连接数据库实例，还需要安装官方提供的命令行工具 mssql-tools18 。如果只是远程连接那么这一步其实并不必要。

同样通过 APT 安装如下：

官方文档中导入 Microsoft 的 GPG 密钥步骤不必重复，跳过

添加软件包源到 APT 软件包源列表

shell

curl https://packages.microsoft.com/config/ubuntu/22.04/prod.list | sudo tee /etc/apt/sources.list.d/mssql-release.list

APT 安装

shell

	sudo apt-get update
	sudo apt-get install mssql-tools18 unixodbc-dev

添加环境变量

shell

	# for shell
	echo 'export PATH="$PATH:/opt/mssql-tools18/bin"' >> ~/.bash_profile
	source ~/.bash_profile

	# for interactive/non-login shell
	echo 'export PATH="$PATH:/opt/mssql-tools18/bin"' >> ~/.bashrc
	source ~/.bashrc

# 导入数据库

官方文档

由于实验课程提供的数据是 SQL Server 导出的，也只能用 Microsoft 提供的办法导入，而目前 Microsoft 只提供了 Windows 上的：

SSMS(GUI)
SSDT(CLI)
两种途径导入导出数据库，所以也只能通过 Windows 导入数据库到 Linux 上的 SQL Server。

实际上和导入 Windows 的数据库没有多大区别，唯一的注意事项是数据文件的权限。具体步骤如下：

将数据文件上传到 Linux 上，并放到专门存放数据库的路径，默认是 /var/opt/mssql/data/ 。例如我们的数据文件是：

School_Data.MDF
School_Log.LDF

然后需要修改权限：

shell

	chown mssql School_Data.MDF School_Log.LDF
	chmod +020 School_Data.MDF School_Log.LDF

然后打开 Windows 的 SSMS，连接到数据库（如何连接见下文）

鼠标右键点击 数据库 / Databases ，点击 附加 / Attach

在新弹出的窗口点击 添加 / add

在新弹出的第二个窗口点击选中要导入的数据库文件，然后点击 确认 / OK

最后点击窗口的 确认 / OK ，即可导入成功

# 连接数据库

Microsoft 提供了一些跨平台连接方案，VS Code 可以使用 SQL Server 插件，SSMS 连接时服务器类型选择 Database Engine 即可。然后服务器名称填写主机名或者 ip ，验证方式选择 SQL Server ，使用 sa 账号即可登录。

其他通用的连接工具登录方式类似，只需注意 SQL Server 的默认连接端口是 1433 。很多 DBMS 软件例如 Nacicat 在连接时都提供专门连接 SQL Server 的选项。

官方文档推荐在第一次连接登录后，创建一个新的账号并禁用 sa 账号作为最佳实践。仅用于学习暂时不必这样操作。（因为根据官方文档来看似乎比较麻烦）

PVE更改节点主机名、ip与集群同步

2024-08-14T00:00:00.000Z

# 更改主机名

更改主机名的操作和 Debian 基本一致，但是 PVE 中会产生新的问题：

配置文件需要手动迁移
如果该节点已加入了集群，集群同步会出问题：
- 集群配置文件需要手动更新
- 节点之间 ssh 通信问题
Cepth 我在这次还没有配置 Cepth，所以情况未知

和 Debian 一样的操作：

bash

	#!/bin/bash

	# 获取旧主机名字
	old_hostname=$(hostname)

	# 输入新主机名
	echo "请输入新的主机名:"
	read new_hostname

	sudo sed -i "s/$old_hostname/$new_hostname/g" /etc/hosts /etc/hostname /etc/postfix/main.cf

然后需要重启让新主机名生效。重启会可能会同时看到新节点和旧节点，新节点上看不到原来的虚拟机、容器，旧节点上看得到，因为虽然重启创建了 /etc/pve/nodes/$new_hostname/ 目录，但是旧节点的配置文件还在 /etc/pve/nodes/$old_hostname/ 中。

其中 /etc/pve/nodes/$old_hostname/qemu-server/ 比较特殊， mv 指令无法将它们直接移动，需要借助 “中转” 移动过去。

bash

	#!/bin/bash

	# 输入新主机名
	read old_hostname

	# 获取旧主机名
	new_hostname=$(hostname)

	cp -r /etc/pve/nodes/$old_hostname/* /etc/pve/nodes/$new_hostname/

	# 中转
	mkdir /root/temp

	mv /etc/pve/nodes/$old_hostname/qemu-server/* /root/temp/

	cp /root/temp/* /etc/pve/nodes/$new_hostname/qemu-server/

	rm -rf /etc/pve/nodes/$old_hostname /root/temp /root/t.sh

每一个更改主机名的节点，都要单独对其执行如上操作。

# 更改 ip

修改 /etc/issue

修改 /etc/hosts

在 PVE 面板中节点的网络（network）修改 ip ，点击应用配置（apply configuration）使其生效

或者直接修改 etc/network/interfaces ，然后重启网络 systemctl restart networking

# 集群同步

# 集群配置文件

按照官方文档，在每一个节点上编辑集群配置文件 /etc/pve/corosync.conf 和 /etc/corosync/corosync.conf （一般重启 corosync 会自动和前者同步），可以修改不同节点主机名、IP、集群 id 等：

bash

	cp /etc/pve/corosync.conf /etc/pve/corosync.conf.new

	cp /etc/pve/corosync.conf /etc/pve/corosync.conf.bak

	nano /etc/pve/corosync.conf.new

	mv /etc/pve/corosync.conf.new /etc/pve/corosync.conf

	systemctl restart corosync

如果修改节点 id，一定注意它是从 1 开始而不是 0 开始的！

这里因为权限问题不能直接编辑，而是创建新文件覆盖的方式编辑。原因如下：

shell

	root@node3:~# ls -lah /etc/pve/corosync.conf
	-rw-r----- 1 root www-data 638 Aug 13 14:36 /etc/pve/corosync.conf

还有另一种方式可以编辑这样的文件，通过切换文件系统的方式。如果上述方法操作失误或编辑出错了，可以通过如下方法挽救：

shell

	systemctl stop pve-cluster

	systemctl stop corosync

	pmxcfs -l

	# 现在可以编辑任意文件了

	nano /etc/pve/corosync.conf

	# 恢复

	killall pmxcfs

	systemctl start pve-cluster

	systemctl start corosync

此外，若修改了节点的 id，还需要在重启 corosync 前受影响节点上删除旧的 id 信息：

shell

rm -rf /var/lib/corosync/*

编辑好配置文件之后，预期将在面板的 数据中心->概要; Datacenter(Cluster)->Summary 看到预期的节点情况。

这个过程由于我参考了官方文档 “从删除集群删除节点” 的内容，我曾误删过 /etc/corosync/authkey 和，导致了 systemctl start corosync 失败，查看日志看到 no such file or directory 这样的的报错，可以从其他节点 tcp 等方式拷贝过去解决。

# ssh 通信

修改主机名、ip 后还会导致节点之间的 ssh 通信出问题，登录某一节点 ip 的面板无法访问另一个节点的信息。

修改 /etc/hosts 增加这些节点和 ip，仍没有解决。

在每一个节点上对每一个其他节点 nodeX (x.x.x.x) 执行 /usr/bin/ssh -e none -o 'HostKeyAlias=nodeX' root@x.x.x.x /bin/true ，仍没有解决。

最终解决：

在每一个节点 nodeX (x.x.x.x) 上，查看 /etc/ssh/ssh_host_rsa_key.pub 得到该节点为 PVE 使用的 rsa 公钥 (pub)xxx... ，然后每一个节点上在集群共享文件 /etc/pve/priv/known_hosts 中编辑确保有且仅有如下信息，删去旧的不正确的信息：

known_hosts

	x.x.x.x ssh-rsa (pub)xxx...
	nodeX ssh-rsa (pub)xxx...
	x.x.x.x ssh-rsa (pub)xxx...
	nodeX ssh-rsa (pub)xxx...
	......

在每一个节点上，建立软链接：

shell

ln -s /etc/pve/priv/known_hosts /etc/ssh/ssh_known_hosts

最后重启 pveproxy 服务：

shell

systemctl restart pveproxy

PVE更换系统盘时的LVM冲突问题

2024-07-11T00:00:00.000Z

自我总结：不懂 Linux 导致的，希望以后通过折腾 Arch 好好学习 Linux

考完期末考这天修了一晚上 PVE 上的虚拟机启动不了的问题。起因是更换了系统盘，将原来的机械硬盘换成了一个 SSD，重装了 PVE，发现虚拟机无法开机。这期间查询了大量论坛，尝试了各种各样的方法，最后终于以非常简单的方式解决，决定写一写记录一下，避免以后再遇到，因为这个问题单纯看 PVE 的报错竟然是完全和问题原因不沾边的！

更换系统盘前，将虚拟机 vm1 迁移到了另一个节点上，更换系统盘重装系统后，将 vm1 迁移回了这台物理机上，启动虚拟机，得到了如下报错：

shell

TASK ERROR: KVM virtualisation configured, but not available. Either disable in VM configuration or enable in BIOS.

按照报错的指引，进入 BIOS 查看了设置，设置是正确的，有启用虚拟化支持。

然后在网络上查询了大量资料、论坛讨论记录，均无法解决。这个过程尝试了包括：

apt upgrade 升级
开新虚拟机
重装系统（PVE）

在虚拟机 Option 中取消 KVM hardware Virtualization 的启用，这样就没有使用 KVM 技术，虚拟机性能是会更差的。但是启动 vm1 发现虚拟机一直重启，对新虚拟机是有如下报错：

shell

	Error: Unknown device type.
	can't create interface fwln306i0 - command '/sbin/ip link add name fwln306i0 mtu 1500 type veth peer name fwpr306p0 mtu 1500' failed: exit code 2

	kvm: -netdev type=tap,id=net0,ifname=tap306i0,script=/var/lib/qemu-server/pve-bridge,downscript=/var/lib/qemu-server/pve-bridgedown: network script /var/lib/qemu-server/pve-bridge failed with status 512
	TASK ERROR: start failed: QEMU exited with code 1

上述方法都没有解决问题。

真正发现问题原因是我在查看 BIOS 和重装系统后，发现每次开机启动 PVE 都有这样的报错：

经过询问大佬，才知道，我们更换系统盘后，由于仍想利用旧的机械硬盘，机械盘仍然插在物理机上。拔掉旧的盘之后问题就解决了。

PVE 采用 LVM，产生了逻辑卷冲突，导致了上图的报错，至于为什么会有什么关于虚拟化的报错，我们就不太清楚了，但是因为这个奇怪的报错我们浪费了两三个小时......

《饿殍：明末千里行》通关感想

2024-05-27T00:00:00.000Z

今天因为校青马班的活动又跑到南校开会、参观团一大。中涂我也不能用电脑，于是无聊之际，手机打开了一直感兴趣的《饿殍：明末千里行》的游戏录播，看了前面就上头了。于是一直到凌晨 3 点，打完了 2 个 TE ，非常有感触，于是一边听着 ED 写下本篇文章作记录。（即使第二天有早八我也不管了！）

这是我玩的第二篇国产的国产文字冒险游戏。《饿殍》难怪这么火，是有些原因的：

首先作为一个全年龄向的游戏，受众确实更加广泛
描写饥荒惨状，敢于如此露骨地描写、刻画，也是非常少见的
当然也有一些比较出圈的 “名场面”，懂得都懂了

我尤其比较喜欢的，还得是双线叙事处理穗的回忆了。穗的回忆可以说是最压抑的部分，在回忆的开头，展现了一点穗原本家庭的美好画面，但后面便开始逐渐步入绝望，令人揪心。尤其是《绝望》这一篇，最为压抑。

这部作品的描绘，很有 “中国” 的历史特色，最后也展现了 “反叛” 这样的末代王朝常见的主旋律。与日系作品相比，少了一分细腻，但却传达了与物哀一样的悲剧的美。

要说从这作品思考到了什么，倒也没有什么。对我来说，我想也是对于大部分和我一样的观众来说，这样的作品给我们的，更多的是摆脱平常朝九晚五、三点一线生活的一点调味。相比平静的青春校园主题作品，这样的乱世、在乱世中旅行、在乱世中寻仇的题材，更给人刺激感、新鲜感。

穗这个角色，塑造的相当好。她给人一种 “小大人” 的感觉，但是这些成熟、懂事、机灵等等不符合其年龄的特点，都反衬着她的艰辛遭遇，都令人心酸。在穗的回忆中，她反而是没有那么 “懂事” 的，还会因为父母煮了小猫而赌气。这样的前后对照，也是对她悲惨遭遇的深层次的刻画，饥荒的灾难不仅摧残她的身体，更塑造了她的性格，催生了她的成长。

而一路上，玩家要想达到好结局，必须要做的只有一件事：尽量在穗面前表现得善良一些，增加所谓的 “好感度”。这也是和传统的文字冒险游戏选项分支不太一样，从这里实际上也看出了游戏的一大主题：原谅。玩家的最终目标，或者说主人公良的终极目标，就是获取穗的原谅。不得不说这还是蛮反差的，因为穗的回忆中，淋漓尽致地描写了良杀害了穗爹爹后，穗家庭的更加惨不忍睹的悲剧，而玩家在见识到这一切之后，还要去替这个 “罪魁祸首” 寻求原谅。

确实，这也是很多人会排斥、难以接受的地方。把穗一家害得如此惨的弑父仇敌，凭什么要原谅？

当然，游戏制作者还是 “上价值”，提醒了玩家们，罪魁祸首不是良，不是男主，而是荒淫无道的王爷、朝廷官府，这也是为什么这个游戏这么有 “中国” 的历史特色，原来一切都是人压迫人导致的悲剧。

整个作品描绘的是一个悲剧、一幅惨状、一对命运不幸的主人公。

穗的人生，自从家里只剩她自己之后，就总是在围绕着 “为了复仇而活着” 了。

良的人生，自从父亲去世只剩他一个人之后，直到遇到穗之前，总是围绕着 “为自己而活着”。

两个角色也就是这样，有一种恰到好处的 “距离感”，看似合作伙伴，实则杀父仇人，在相互帮助、依赖的过程中，产生了一点点的、非常少的 “为对方而活着” 的感觉。而尤其是到了 TE “同生” ，“为对方而活着” 的感觉就更强烈了。

贯穿整个故事的，一直都是两人这样的 “距离感”。在 TE 之前的 3 个结局，突出表现了距离感与陌生感：

无言，穗实施了计划让良在茫然、错愕中被捕、处以极刑，可以说是最不好的结局之一
快逃，和无言的区别在于穗给了良准备的机会，给了良体面赴死的机会
不见，最让人放不下的结局
- 穗的想法来看，可以有两种解读：
  - 可以认为穗似乎原谅良了，不再杀良，宁可自己一人消失
  - 可以认为穗依然复仇了，只是她的复仇，不再是设计良被捕，而是用自己的消失、荷包的提醒，告诉良真相之后一言不发地独自消失
- 穗的去向来看，也有两种解读：
  - 很大可能，穗投湖自尽了，在失去 “复仇” 这一人生意义后，只好自杀
  - 很小的概率，穗或许伪造了投湖的迹象，依然活着，并且选择不再出现在良眼前

那张惊艳无比的烟花的 CG ，竟是良和穗的最后一面。而后，穗谎称解手，便一去不返，突然没了音讯。两人再次拉开了距离，突然一股陌生感、寂寞感向玩家袭来。

至此，穗这个角色的塑造堪称饱满，她不再是弱小无力的” 小羊 “，而是和良站在平等的位置上的，甚至站在审判良的位置上的，一个饱满的角色。并且，一直保持了一份 “距离感”，即穗与良的 “距离感”，也是玩家与 “穗” 这个角色的 “距离感”，是不再相见的 “距离感”、是弑父血仇的 “距离感”、是生与死的” 距离感 “。

直到最后的结局 “同生” 也是，一直保留了这份若即若离的距离感，两人还是以仇人相称。这份 “距离感”，比皆大欢喜、甜甜蜜蜜发糖我觉得要更好。

片段一 (同生)
良 [喂，我算了一下，如今你大概二十有三了吧。]
满穗 [嗯。]
良 [现在嫁人了没？]
满穗 [没嫁呢。]
良 [哦。]
满穗 [良呢？打仗的候娶妻了吗？]
良 [没娶，兵荒乱的，娶什么妻。]
满穗 [也是。]

片段二 (同生)
满穗 [其实，这么多年来，我跟别人提起我的名字，一直都是 “穗”。]
满穗 [唯独良爷，我说了全名，是叫满穗。]
良 [......]
良 [哦？为何只有我有这个区别？]
满穗 [呵...... 当初我就是觉得，要仇人知道我的全名，我才没有白复仇。]
满穗 [如今怎么想的，我也不知道了......]
良 [......]
满穗 [......]
良 [......]
满穗 [话说回来，良爷觉得怎么样？]
良 [什么怎么样？]
满穗 [你喜欢 “满穗”，还是 “穗”？]
良 [......]
满穗 [......]
良 [......]
良 [“满穗” 吧]
满穗 [......]
良 [我喜欢 “满穗”......]
满穗 [哦......]
良 [满穗、满穗、满穗......]
我念了一遍又一遍她的名字。
满穗 [......]
她没有说话，只是装著听不见我在念她的名字
她特不时地整笑著，不知在高兴些什么
她望著窗外，饮著茶，似乎在想著一些什么......
—— 咕
我也饮下了一杯茶，望著她所眺望的方向，嘴角不自地勾起了一丝笑意。

片段三 (共死)
满穗 [以前... 我装成哑巴... 现在... 你真成哑巴了... 真好笑...]
她轻声笑着
满穗 [良，抱紧我吧......]

PVE直通显卡

2024-05-07T00:00:00.000Z

PVE 版本：8.1.4 ，显卡：NVIDIA GTX 745

# 宿主机配置

# IOMMU

shell

nano /etc/default/grub

将 GRUB_CMDLINE_LINUX_DEFAULT="..." 中的内容修改为如下：

shell

GRUB_CMDLINE_LINUX_DEFAULT="quiet intel_iommu=on iommu=pt video=efifb:off"

准确来说是在 "..." 原来的内容后面增加这些内容，其中：

quiet 一般是原来就有的
intel_iommu=on 和 iommu=pt 是必须的
video=efifb:off 如果你是给 Windows VM 直通显卡串流玩游戏的话是需要的

然后更新配置文件：

shell

update-grub

检查 IOMMU 是否启动：

shell

dmesg | grep -e DMAR -e IOMMU

看到有 DMAR 或 IOMMU 输出就行，例如我们就只看到了 DMAR 的输出。

# 配置显卡

找到自己的显卡的相关信息：

shell

lspci -knn | grep VGA

我们需要如下内容：

shell

01:00.0 VGA compatible controller [0300]: NVIDIA Corporation GM107 [GeForce GTX 745] [10de:1382] (rev a2)

        Subsystem: NVIDIA Corporation GM107 [GeForce GTX 745] [10de:1065] # these ids

        Kernel modules: nvidiafb, nouveau # these modules

[10de:1065] 是 <vendor id>:<device id> 形式的厂商 id 和设备 id
nvidiafb 和 nouveau 是我们的显卡所使用的驱动模块

将厂商 id 和设备 id 组合添加到 vfio 配置文件中：

shell

nano /etc/modprobe.d/vfio.conf

增加如下内容：

shell

options vfio-pci ids=10de:1382 disable_vga=1

如果你有多张显卡需要直通，那么不同显卡对应的 <vendor id>:<device id> 就以逗号分隔加在 ids= 后面即可，例如：

shell

options vfio-pci ids=1145:1400,1919:1800 disable_vga=1

屏蔽显卡驱动模块：

shell

echo "blacklist <some-module>" >> /etc/modprobe.d/blacklist.conf

对每一个模块都需要加单独一行，例如我们是 nvidiafb 和 nouveau ，则需要：

shell

	echo "blacklist nvidiafb" >> /etc/modprobe.d/blacklist.conf
	echo "blacklist nouveau" >> /etc/modprobe.d/blacklist.conf

有一些教程说是修改配置文件 /etc/modprobe.d/pve-blacklist.conf ，但是官方文档（目前）说的是 /etc/modprobe.d/blacklist.conf ，两者不知道有没有区别

# vfio

shell

nano /etc/modules

增加如下几行：

shell

	vfio
	vfio_iommu_type1
	vfio_pci
	vfio_virqfd #not needed if on kernel 6.2 or newer

最后执行如下指令，并且重启：

shell

update-initramfs -u -k all

最后使用如下指令检查配置是否成功：

shell

lspci -k

预期是得到对应的显卡部分有如下输出结果：

shell

	01:00.0 VGA compatible controller: NVIDIA Corporation GP108 [GeForce GT 1030] (rev a1)
	Subsystem: Micro-Star International Co., Ltd. [MSI] GP108 [GeForce GT 1030]
	Kernel driver in use: <some-module> # 预期是 vfio
	Kernel modules: <some-module>

# 问题

执行最后一句指令时，我们却遇到了这个输出：

shell

	...
	Re-executing '/etc/kernel/postinst.d/zz-proxmox-boot' in new private mount namespace..
	No /etc/kernel/proxmox-boot-uuids found, skipping ESP sync.

然后 lspci -k 检查也没有预期的输出，虚拟机添加显卡设备后无法开机。

我尝试了官方文档中 Host Device Passthrough 部分的方法：

For both methods you need to update the initramfs again and reboot after that.

Should this not work, you might need to set a soft dependency to load the gpu modules before loading vfio-pci. This can be done with the softdep flag, see also the manpages on modprobe.d for more information.

For example, if you are using drivers named <some-module> :

shell

# echo "softdep <some-module> pre: vfio-pci" >> /etc/modprobe.d/<some-module>.conf

但仍然没有效果。

所幸，似乎有不少人也遇到了这个问题，我找到了这个帖子，似乎说是因为没有同步连接 ESP 导致的，接下来我按照里面一个解决方案走：

然后我先尝试了重新挂载 /boot/efi ，首先 lsblk -o +FSTYPE 查看 /boot/efi 挂载的磁盘分区，例如我这里是 sda2 ，然后重新挂载一下：

shell

	umount /boot/efi
	proxmox-boot-tool init /dev/sda2

然后先前类似 No /etc/kernel/proxmox-boot-uuids found, skipping ESP sync. 的输出就没有了，最后成功了。

# VM 配置

选中 VM ，在 == 硬件（Hardware）== 部分中，== 机型（Machine）== 应该（尽量）选择 q35 类型，如果不是的话可以在关机状态下修改。

然后还是在硬件（Hardware）部分，点击添加（add），选择 PCI 设备，找到自己的显卡添加设备。

或者 CLI 版本操作：

shell

	qm set VMID -hostpci0 00:02.0
	# or add these to vm config file:
	# hostpci0: 00:02.0

启动虚拟机，一切无误的话就能够正常启动，然后在虚拟机中就可以当作真实物理机插着显卡进一步安装驱动操作啦

taf.fyi

間夫之爱——《哀鸿：城破十日记》

# 前言

# 杂谈

# 香臭

# 纯洁

# 間夫

Muv-Luv

# 前言

# 很多缺点

# 纯粹的爱

さくら、もゆ（樱花，萌放）通关感想

# 前言

# 爱、勇气、孤单、寂寞

# 寂寞的孩子与悲伤的孩子

# 世界でいちばん優しい時間

# 世界でいちばん近い距離

# 缄默的孩子与黑色的猫

Mini OceanBase 2025

# 参赛经历

# 关于 Expression

# Order By

# 子查询

# alias

# union

# 视图

# 全文索引

# null

Jabberwocky——素晴らしき日々(美好的每一天)通关感想

# Overture

# Jabberwocky

# 彷徨う鳥

# The brain is wider than the sky

# 空気力学

# 向日葵

# Finale

不条理と理不尽ばかり——穢翼のEustia(脏翅膀)通关感想

# 一些评价

# 喃喃自语

大数据平台 All in One 搭建记录

# 架构介绍

# Hadoop

# Spark

# Tez

# Flink

# 访问内网环境

# 提交任务

# Spark

# Flink

# Tez

Mini OceanBase 2024

# 参赛经历

# MiniOB 架构

# SQL 解析

# 词法分析

# 语法分析

# Statement

# 执行模型

# 火山模型

# 向量化执行模型

# Logical Operator

# Physical Operator

# Predicate

# Groupby

# Orderby

# 子查询

# Reference

Pollard-Rho

# 大数运算

# 大数字符串输入输出处理

# Pollard-Rho

# 我学号的 DLP

RSA

# 大数运算

# 预计算

# R2 mod pR^2\bmod pR2modp

# p0−1 mod Wp_0^{-1}\bmod Wp0−1​modW

# Montgomery Multiplication

# 模乘

# 模指数

# $R^2\bmod p$

# $p_0^{-1}\bmod W$