本帖最后由 Vinogradov 于 2019-3-16 19:21 编辑
主要制作者：丢人素学姐
压缩方案提出者：pku_zzzz
项目地址：https://github.com/YijunYuan/Minecraft_MD5
下载地址：https://github.com/YijunYuan/Minecraft_MD5/releases
什么是MD5？
为什么要在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为例，摘抄自素学姐的代码）：复制代码比较简单。类似地，其他位运算及加法大都可以写成复制代码的形式。生成mcfunction后，我们发现这个写法下命令的数量超过了我们的想象，整个数据包有超过一百万条命令，数据包大小接近200MB，载入时会造成**的卡顿（虽然确实可以运算而且结果是对的）。原因就在于，对于每一次数学上的原子运算，生成命令后都数量都会变为32倍以上（因为要对每bit经行分别操作），完成两个32bit整数的加法甚至需要100多条命令，数量十分吓人。
虽然这个数据包并不会有什么实际的用途，但我们还是想问：能不能做得更好？
这时，pku_zzzz向素学姐提出了他的一个想法，大致如下：
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为例，
复制代码 这样完成一次XOR运算就只需要两条命令，十分方便！
加法的话，由于对顺序的强烈依赖性，所以需要将每bit的运算放到另一个function里，然后使用execute+选择器按顺序调用。
而如何指定调用顺序呢？
我们想到选择器中有sort的选项，可以以某一点为基点，让选中的实体由近及远地依次执行。于是我们将前文中所述的盔甲架依次排成一列，并选最低位bit0位基点，实现加法如下：
复制代码 等等！你看到了furthest而不是nearest，这是为什么？加法难道不是从低位加到高位吗（反映到命令上，就是以bit0为基点，由近到远）？
素学姐一开始写的确实是nearest，但在测试时惊奇地发现加法竟然是从高位开始加的！在确认自己写法无误后，他将问题转给了pku_zzzz，于是就有了帖子[命令] Minecraft 1.13.x 中 Function 嵌套执行的顺序问题。简而言之，MC-126946 造成了顺序颠倒。于是无奈之中我们只能将nearest改为furthest，使得行为上正常了。但这是非常肮脏的hack，很可能在未来的某个版本被修复，倒是这个地方还需要改回来。
另外，带位移的拷贝也需要使用sort，不过不受以上所述的BUG的影响：
复制代码 其他运算也类似，在此不再赘述。
在此改动后，数据包的大小已不到8MB，可见pku_zzzz的想法是极其有效且重要的！
其他地方就没有什么特别的了，有兴趣的朋友可去GitHub中查看生成器的代码。
其他： 使用完全一样的技术，我们可以实现SHA-256等hash算法。
感谢：
@玄素@SPGoding
来自群组: Command Block Logic
在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值？
没为什么。就是让大家知道我（们）可以做到。
限制：
- 此数据包只支持计算ASCII字符串
- 需满足 1<=字符串长度<567
使用方法：
- 加载本数据包
- 仔细阅读使用方法（也就是你现在在阅读的东西）。
- 运行命令（注意，每次计算前都必须运行该指令以重置系统。）复制代码
- /function md5:reset
- 输入字符串。本数据包目前支持两种输入方式。一、使用我之前制作的数据包'keyboard'。你可以在->此处<-找到它的使用方法。输入完毕后，执行以导入数据。由于这个键盘的使用十分不方便，只建议用来输入很短的字符串。二、使用项目中的test_string函数。具体地说，调用测试函数，使用方法为复制代码
- /function md5:import_string
然后编译运行后将生成的文件放入复制代码- test_string("Put the string you want to test here!");
并运行复制代码- .minecraft/<Your World Name>/datapacks/md5/data/md5/functions/
导入字符串。复制代码- /function md5:test_string
- 运行进行运算。注意：运行这个函数会造成明显卡顿。复制代码
- /function md5:core_wrapper
- 运行以显示结果。复制代码
- /function md5:display_result
原理讲解：
关于MD5算法本身这里不再赘述，有兴趣的朋友可以去看Wiki上的伪代码，写得非常清楚。我们这里主要谈一谈在Minecraft中的实现方法。
纵观整个MD5算法，出现了两种数据类型：无符号8位整数，无符号32位整数；以及若干种运算：（可能带位移的）复制，加法，位运算（OR，AND，XOR，NOT，LEFT_ROTATION）。
那么从中可以知道，使用记分板原生的运算来直接实现是不合适的，因为位运算会变得非常麻烦（而在MD5计算中位运算非常多），且在溢出等问题的控制上也比较不方便。我们需要一种能方便地进行位运算的整数系统。
最直接的想法是，把每个整数的每个bit都分开存，这样每次位运算时，只要分别对每个bit进行处理即可，省去了把每一位取出来运算完再放回去的麻烦（这时加法 会稍微麻烦一些，但搞过OI的人肯定知道怎么实现高精度加法，这里是同样的原理）。
基于这样的想法，素学姐的第一版实现如下：
将一个记分板看作一个整数，将一串假名：bit0，bit1，...，bit31在此记分板中的值依次看作这个整数的第0位，第1位，...，第31位。（8bit类似）。
那么位运算的实现就可以这么写（以XOR为例，摘抄自素学姐的代码）：
- void inline XOR_32(ostream& STREAM, const string& IP1, const string& IP2, const string& RES) {
- for (int i = 0; i < 32; i++) {
- STREAM << "execute if score bit" << i << " vars." << IP1 << " = bit" << i << " vars." << IP2 << " "
- << "run scoreboard players set bit" << i << " vars." << RES << " 0" << endl;
- STREAM << "execute unless score bit" << i << " vars." << IP1 << " = bit" << i << " vars." << IP2 << " "
- << "run scoreboard players set bit" << i << " vars." << RES << " 1" << endl;
- }
- void inline something(ostream& STREAM, const string& IP1, const string& IP2, const string& RES) {
- for (int i = 0; i < 32; i++) {
- xxxx
- }
- }
虽然这个数据包并不会有什么实际的用途，但我们还是想问：能不能做得更好？
这时，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为例，
- void inline XOR_32(ostream& ofs, const string& IP1, const string& IP2, const string& RES) {
- ofs << "execute as @e[tag=L32] if score @s vars." << IP1 << " = @s vars." << IP2 << " "
- << "run scoreboard players set @s vars." << RES << " 0" << endl;
- ofs << "execute as @e[tag=L32] unless score @s vars." << IP1 << " = @s vars." << IP2 << " "
- << "run scoreboard players set @s vars." << RES << " 1" << endl;
- }
加法的话，由于对顺序的强烈依赖性，所以需要将每bit的运算放到另一个function里，然后使用execute+选择器按顺序调用。
而如何指定调用顺序呢？
我们想到选择器中有sort的选项，可以以某一点为基点，让选中的实体由近及远地依次执行。于是我们将前文中所述的盔甲架依次排成一列，并选最低位bit0位基点，实现加法如下：
- void inline ADD_32(ostream& ofs, const string& IP1, const string& IP2, const string& RES) {
- MAKE_SVAR(ofs, "stemp1", 0); //carry=0
- ofstream ofs_add("./output/add_impl/add_" + IP1 + "_" + IP2 + ".mcfunction");
- //c.d[c.len++]=a.d[i] + b.d[i] + carry;
- ofs_add << "scoreboard players operation @s vars."
- << RES << " = @s vars." << IP1 << endl;
- ofs_add << "scoreboard players operation @s vars."
- << RES << " += @s vars." << IP2 << endl;
- ofs_add << "scoreboard players operation @s vars."
- << RES << " += stemp1 svars" << endl;
- //carry=c.d[c.len++]/2;
- ofs_add << "scoreboard players operation stemp1 svars"
- << " = @s vars." << RES << endl;
- ofs_add << "scoreboard players operation stemp1 svars"
- << " /= const2 svars" << endl;
- //c.d[c.len++]%=2;
- ofs_add << "scoreboard players operation @s vars."
- << RES << " %= const2 svars" << endl;
- ofs_add.close();
- ofs << "execute at @e[tag=md5.bit0] as @e[tag=L32,sort=furthest] "
- << "run function md5:add_impl/add_" + IP1 + "_" + IP2 << endl;
- }
素学姐一开始写的确实是nearest，但在测试时惊奇地发现加法竟然是从高位开始加的！在确认自己写法无误后，他将问题转给了pku_zzzz，于是就有了帖子[命令] Minecraft 1.13.x 中 Function 嵌套执行的顺序问题。简而言之，MC-126946 造成了顺序颠倒。于是无奈之中我们只能将nearest改为furthest，使得行为上正常了。但这是非常肮脏的hack，很可能在未来的某个版本被修复，倒是这个地方还需要改回来。
另外，带位移的拷贝也需要使用sort，不过不受以上所述的BUG的影响：
- void inline COPY(ostream& ofs, const string& TO, const string& FROM, size_t length, size_t offset) {
- ofs << "execute as @e[tag=L" << length << "] at @s positioned ~" << offset <<
- " ~ ~ run scoreboard players operation @e[tag=md5.bit,sort=nearest,limit=1] vars." << TO << " = @s vars."
- << FROM << endl;
- }
在此改动后，数据包的大小已不到8MB，可见pku_zzzz的想法是极其有效且重要的！
其他地方就没有什么特别的了，有兴趣的朋友可去GitHub中查看生成器的代码。
其他： 使用完全一样的技术，我们可以实现SHA-256等hash算法。
感谢：
@玄素@SPGoding
来自群组: Command Block Logic
沙发？
当时我也想到过类似的坑的，不过由于素学姐在我之前已经着手去做了，所以我就把这个点子放弃了。不过，之后具体构思的细节我也和素学姐说了，和素学姐当时的实现也有一定程度的差异，没想到素学姐直接把我挂在了第二作者的位置，我也是感到有些荣幸吧。
其实感觉这样的想法还是挺容易想到的，毕竟现在的命令差不多也快发展成面向实体编程了（笑）。
当时我也想到过类似的坑的，不过由于素学姐在我之前已经着手去做了，所以我就把这个点子放弃了。不过，之后具体构思的细节我也和素学姐说了，和素学姐当时的实现也有一定程度的差异，没想到素学姐直接把我挂在了第二作者的位置，我也是感到有些荣幸吧。
其实感觉这样的想法还是挺容易想到的，毕竟现在的命令差不多也快发展成面向实体编程了（笑）。
计算MD5你们是真的恐怖，以后都不用下软件了，MC里计算就好了
太牛逼了，衬托得我渺小不堪，一无是处。
太强了,mc迟早变成运行环境(大雾)
在MC中计算MD5……
你们是有多闲……
你们是有多闲……
感谢楼主分享~学到了
厉害，没谁了
感谢楼主分享~学到了
突然感到自己的渺小系列
牛逼到我看不懂...............................
正经:
我眼睛疼
余味:
[图片]
正经:
不能一直盯着电脑
余味:
嗯嗯 那就别看了
我眼睛疼
余味:
[图片]
正经:
不能一直盯着电脑
余味:
嗯嗯 那就别看了
。。。大佬，佩服！
ooooooooooooo
学到了，哈哈哈
万利达独爱i多家
进来逛逛然后喝茶ing最后疯狂膜拜ing
444444444444444444444
44444444444444444444
。。。。。。
啦啦啦啦啦啦啦啦啦啦啦啦啦啦
感谢分享 感谢
......................................
讲的真好
数学不好的人表示看不懂
新人做任务
emmmmmmmmmmmmmmmmmmmmmmmmmmmmm
电脑崩了？该换了
adwasawdssawdsa
做一个c编译器吧，把c代码编译成mc命令
大佬666666
本帖最后由 旎小殇 于 2019-5-12 23:02 编辑
感谢支持楼主继续加油，期待更新
感谢支持楼主继续加油，期待更新
本帖最后由 旎小殇 于 2019-5-12 23:02 编辑
感谢支持楼主继续加油
感谢支持楼主继续加油
本帖最后由 旎小殇 于 2019-5-12 22:57 编辑
继续努力加油，很有用
继续努力加油，很有用
嗯嗯嗯，好厉害！（不明觉厉）
看了下确实学到了很多，之前在1.12.2里也自己写了个32位的架构来实现高精度的代数型三角函数运算，但当时自己命名不规范，没有利用假名的优势，甚至常量的命令我用@p ten这种来表示10，简直了。也准备在1.14里把之前写的不完善的地方优化一下。
大佬牛逼啊
大佬。。或许以后想要做个什么东西开个mc模拟下环境就能搞出来了？= =
旎小殇 发表于 2019-4-18 11:22
6666666666
加油加油，很有用很棒棒
感谢楼主分享~学到了
看不懂啊看不懂，我怕是玩了个假MC
......我是真没看懂，不过你在MC里用命令算MD5是个神魔操作啊？！