Minecraft(我的世界)中文论坛

标题: 【CBL|丢人素学姐, pku_zzzz】在Minecraft中计算字符串的MD5值
作者: 丢人素学姐    时间: 2019-3-1 16:52
标题: 【CBL|丢人素学姐, pku_zzzz】在Minecraft中计算字符串的MD5值
本帖最后由 Vinogradov 于 2019-3-16 19:21 编辑

在Minecraft中计算字符串的MD5值

主要制作者：丢人素学姐
压缩方案提出者：pku_zzzz

项目地址：https://github.com/YijunYuan/Minecraft_MD5
下载地址：https://github.com/YijunYuan/Minecraft_MD5/releases

什么是MD5？
MD5消息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，于1992年公开，用以取代MD4算法。这套算法的程序在 RFC 1321 中被加以规范。--Wiki


为什么要在Minecraft中计算字符串的MD5值？
没为什么。就是让大家知道我（们）可以做到。


限制：
注意：如果你无视了以上所述的限制或以下的使用方法，那么本数据包将会在没有任何警告的情况下给出错误结果，即使往里面加入警告很容易。


使用方法：


原理讲解：
        关于MD5算法本身这里不再赘述，有兴趣的朋友可以去看Wiki上的伪代码，写得非常清楚。我们这里主要谈一谈在Minecraft中的实现方法。
        纵观整个MD5算法，出现了两种数据类型：无符号8位整数，无符号32位整数；以及若干种运算：（可能带位移的）复制，加法，位运算（OR，AND，XOR，NOT，LEFT_ROTATION）。
        那么从中可以知道，使用记分板原生的运算来直接实现是不合适的，因为位运算会变得非常麻烦（而在MD5计算中位运算非常多），且在溢出等问题的控制上也比较不方便。我们需要一种能方便地进行位运算的整数系统。
        最直接的想法是，把每个整数的每个bit都分开存，这样每次位运算时，只要分别对每个bit进行处理即可，省去了把每一位取出来运算完再放回去的麻烦（这时加法 会稍微麻烦一些，但搞过OI的人肯定知道怎么实现高精度加法，这里是同样的原理）。
        基于这样的想法，素学姐的第一版实现如下：
        将一个记分板看作一个整数，将一串假名：bit0，bit1，...，bit31在此记分板中的值依次看作这个整数的第0位，第1位，...，第31位。（8bit类似）。
那么位运算的实现就可以这么写（以XOR为例，摘抄自素学姐的代码）：
  1. void inline XOR_32(ostream& STREAM, const string& IP1, const string& IP2, const string& RES) {
  2.     for (int i = 0; i < 32; i++) {
  3.         STREAM << "execute if score bit" << i << " vars." << IP1 << " = bit" << i << " vars." << IP2 << " "
  4.                     << "run scoreboard players set bit" << i << " vars." << RES << " 0" << endl;
  5.         STREAM << "execute unless score bit" << i << " vars." << IP1 << " = bit" << i << " vars." << IP2 << " "
  6.                     << "run scoreboard players set bit" << i << " vars." << RES << " 1" << endl;
  7.     }
复制代码
比较简单。类似地，其他位运算及加法大都可以写成
  1. void inline something(ostream& STREAM, const string& IP1, const string& IP2, const string& RES) {
  2.     for (int i = 0; i < 32; i++) {
  3.         xxxx
  4.     }
  5. }
复制代码
的形式。生成mcfunction后，我们发现这个写法下命令的数量超过了我们的想象，整个数据包有超过一百万条命令，数据包大小接近200MB，载入时会造成**的卡顿（虽然确实可以运算而且结果是对的）。原因就在于，对于每一次数学上的原子运算，生成命令后都数量都会变为32倍以上（因为要对每bit经行分别操作），完成两个32bit整数的加法甚至需要100多条命令，数量十分吓人。
        虽然这个数据包并不会有什么实际的用途，但我们还是想问：能不能做得更好？

        这时，pku_zzzz向素学姐提出了他的一个想法，大致如下：
既然位运算、拷贝和加法对每bit进行的操作都是完全一样的；而且两个不同的bit之间，除了加法外的运算都是互相完全独立的，那么是否可以让这32bit“并行”地运行呢？

        pku_zzzz所说的“并行”并不是真正意义上多线程的并行，而是指使用选择器将这32个bit一次性选中，然后使用execute as xxx run xxx，内层使用@s进行指代，这样只用一条指令就能完成位运算和拷贝运算，而加法运算只需在execute时指定执行顺序即可（下面会说到加法的特殊性）。
        而在第一版中，素学姐使用了并不存在的实体的假名，是无法被选择器选中的。因此，现在我们将假名改为32个盔甲架，依次加上bit0，bit1，...，bit31的tag，并让bit0，...，bitk加上tag Lk（这里k应该看作一个变量，1<=k<=32）。然后实现运算时就会变得非常简单：
        我们还是以XOR为例，
  1. void inline XOR_32(ostream& ofs, const string& IP1, const string& IP2, const string& RES) {
  2.     ofs << "execute as @e[tag=L32] if score @s vars." << IP1 << " = @s vars." << IP2 << " "
  3.          << "run scoreboard players set @s vars." << RES << " 0" << endl;
  4.     ofs << "execute as @e[tag=L32] unless score @s vars." << IP1 << " = @s vars." << IP2 << " "
  5.          << "run scoreboard players set @s vars." << RES << " 1" << endl;
  6. }
复制代码
        这样完成一次XOR运算就只需要两条命令，十分方便！
        加法的话，由于对顺序的强烈依赖性，所以需要将每bit的运算放到另一个function里，然后使用execute+选择器按顺序调用。
而如何指定调用顺序呢？
        我们想到选择器中有sort的选项，可以以某一点为基点，让选中的实体由近及远地依次执行。于是我们将前文中所述的盔甲架依次排成一列，并选最低位bit0位基点，实现加法如下：
  1. void inline ADD_32(ostream& ofs, const string& IP1, const string& IP2, const string& RES) {
  2.     MAKE_SVAR(ofs, "stemp1", 0); //carry=0


  5.     ofstream ofs_add("./output/add_impl/add_" + IP1 + "_" + IP2 + ".mcfunction");

  7.     //c.d[c.len++]=a.d[i] + b.d[i] + carry;
  8.     ofs_add << "scoreboard players operation @s vars."
  9.                 << RES << " = @s vars." << IP1 << endl;
  10.     ofs_add << "scoreboard players operation @s vars."
  11.                 << RES << " += @s vars." << IP2 << endl;
  12.     ofs_add << "scoreboard players operation @s vars."
  13.                 << RES << " += stemp1 svars" << endl;

  15.     //carry=c.d[c.len++]/2;
  16.     ofs_add << "scoreboard players operation stemp1 svars"
  17.                 << " = @s vars." << RES << endl;
  18.     ofs_add << "scoreboard players operation stemp1 svars"
  19.                 << " /= const2 svars" << endl;

  21.     //c.d[c.len++]%=2;
  22.     ofs_add << "scoreboard players operation @s vars."
  23.                 << RES << " %= const2 svars" << endl;

  25.     ofs_add.close();

  27.     ofs << "execute at @e[tag=md5.bit0] as @e[tag=L32,sort=furthest] "
  28.          << "run function md5:add_impl/add_" + IP1 + "_" + IP2 << endl;

  30. }
复制代码
        等等！你看到了furthest而不是nearest，这是为什么？加法难道不是从低位加到高位吗（反映到命令上，就是以bit0为基点，由近到远）？
        素学姐一开始写的确实是nearest，但在测试时惊奇地发现加法竟然是从高位开始加的！在确认自己写法无误后，他将问题转给了pku_zzzz，于是就有了帖子[命令] Minecraft 1.13.x 中 Function 嵌套执行的顺序问题。简而言之，MC-126946 造成了顺序颠倒。于是无奈之中我们只能将nearest改为furthest，使得行为上正常了。但这是非常肮脏的hack，很可能在未来的某个版本被修复，倒是这个地方还需要改回来。
        另外，带位移的拷贝也需要使用sort，不过不受以上所述的BUG的影响：
  1. void inline COPY(ostream& ofs, const string& TO, const string& FROM, size_t length, size_t offset) {
  2.     ofs << "execute as @e[tag=L" << length << "] at @s positioned ~" << offset <<
  3.                " ~ ~ run scoreboard players operation @e[tag=md5.bit,sort=nearest,limit=1] vars." << TO << " = @s vars."
  4.          << FROM << endl;
  5. }
复制代码
        其他运算也类似，在此不再赘述。
        在此改动后，数据包的大小已不到8MB，可见pku_zzzz的想法是极其有效且重要的！
        其他地方就没有什么特别的了，有兴趣的朋友可去GitHub中查看生成器的代码。


其他：        使用完全一样的技术，我们可以实现SHA-256等hash算法。


感谢：
@玄素@SPGoding











[groupid=546]Command Block Logic[/groupid]
作者: pku_zzzz    时间: 2019-3-1 17:00
沙发？

当时我也想到过类似的坑的，不过由于素学姐在我之前已经着手去做了，所以我就把这个点子放弃了。不过，之后具体构思的细节我也和素学姐说了，和素学姐当时的实现也有一定程度的差异，没想到素学姐直接把我挂在了第二作者的位置，我也是感到有些荣幸吧。

其实感觉这样的想法还是挺容易想到的，毕竟现在的命令差不多也快发展成面向实体编程了（笑）。
作者: 爱心魔王FHC    时间: 2019-3-1 18:15
计算MD5你们是真的恐怖，以后都不用下软件了，MC里计算就好了
作者: 森林蝙蝠    时间: 2019-3-1 20:22
太牛逼了，衬托得我渺小不堪，一无是处。
作者: 寒兮!    时间: 2019-3-1 20:29
太强了,mc迟早变成运行环境(大雾)
作者: zyjking    时间: 2019-3-1 21:56
在MC中计算MD5……
你们是有多闲……
作者: 寒江独钓    时间: 2019-3-2 18:19
感谢楼主分享~学到了
作者: fanyanfeng    时间: 2019-3-2 21:52
厉害，没谁了
作者: taibaiOVO    时间: 2019-3-3 10:07
感谢楼主分享~学到了
作者: princess01    时间: 2019-3-4 00:22
突然感到自己的渺小系列
作者: WB1436871576    时间: 2019-3-8 11:44
牛逼到我看不懂...............................
作者: 164978694    时间: 2019-3-10 16:16
正经:
我眼睛疼

余味:
[图片]

正经:
不能一直盯着电脑

余味:
嗯嗯 那就别看了
作者: 猿汐    时间: 2019-3-10 17:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: 2984035075    时间: 2019-3-16 08:20
ooooooooooooo
作者: ...Fisherman    时间: 2019-3-17 14:18
学到了，哈哈哈
作者: Trthgfghg    时间: 2019-3-17 15:59
万利达独爱i多家
作者: kether离    时间: 2019-3-22 19:53
进来逛逛然后喝茶ing最后疯狂膜拜ing
作者: asdqwe159654852    时间: 2019-3-29 16:43
444444444444444444444
作者: asdqwe159654852    时间: 2019-3-29 16:44
44444444444444444444
作者: 斩玄地青月    时间: 2019-3-29 22:50
。。。。。。
作者: 无法大神    时间: 2019-3-31 17:19
啦啦啦啦啦啦啦啦啦啦啦啦啦啦
作者: a15398390095    时间: 2019-4-1 17:54
感谢分享  感谢
作者: lovethx    时间: 2019-4-4 19:11
......................................
作者: 忘·羡    时间: 2019-4-4 20:12
讲的真好
作者: wingzi060123    时间: 2019-4-5 00:26
数学不好的人表示看不懂
作者: niyuan    时间: 2019-4-7 13:54
新人做任务
作者: 鼆畻    时间: 2019-4-7 16:44
emmmmmmmmmmmmmmmmmmmmmmmmmmmmm
作者: niyuan    时间: 2019-4-7 17:12
电脑崩了？该换了
作者: 大恐龙啊    时间: 2019-4-10 12:23
adwasawdssawdsa
作者: Nissyara    时间: 2019-4-15 20:32
做一个c编译器吧，把c代码编译成mc命令
作者: 丢人素学姐    时间: 2019-4-16 17:25
Nissyara 发表于 2019-4-15 20:32
做一个c编译器吧，把c代码编译成mc命令

你怎么知道我没在做呢
作者: lop121    时间: 2019-4-17 21:03
大佬666666
作者: 旎小殇    时间: 2019-4-18 11:22
本帖最后由 旎小殇 于 2019-5-12 23:02 编辑

感谢支持楼主继续加油，期待更新
作者: 旎小殇    时间: 2019-4-18 11:23
本帖最后由 旎小殇 于 2019-5-12 23:02 编辑

感谢支持楼主继续加油
作者: 旎小殇    时间: 2019-4-18 11:29
本帖最后由 旎小殇 于 2019-5-12 22:57 编辑

继续努力加油，很有用
作者: HUI极度灰    时间: 2019-4-20 18:08
嗯嗯嗯，好厉害！（不明觉厉）
作者: CCxia    时间: 2019-5-1 23:08
看了下确实学到了很多，之前在1.12.2里也自己写了个32位的架构来实现高精度的代数型三角函数运算，但当时自己命名不规范，没有利用假名的优势，甚至常量的命令我用@p ten这种来表示10，简直了。也准备在1.14里把之前写的不完善的地方优化一下。
作者: 1677343686    时间: 2019-5-5 13:50
大佬牛逼啊
作者: ActiveDesktop    时间: 2019-5-5 22:17
大佬。。或许以后想要做个什么东西开个mc模拟下环境就能搞出来了？= =
作者: 旎小殇    时间: 2019-5-12 22:58
旎小殇 发表于 2019-4-18 11:22
6666666666

加油加油，很有用很棒棒
作者: cf6513272991    时间: 2019-5-25 13:10

感谢楼主分享~学到了
作者: REgouzi    时间: 2020-7-11 18:32
看不懂啊看不懂，我怕是玩了个假MC
作者: 669775992    时间: 2020-7-12 00:26
......我是真没看懂，不过你在MC里用命令算MD5是个神魔操作啊？！