本帖最后由 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值？
没为什么。就是让大家知道我（们）可以做到。


限制：
  • 此数据包只支持计算ASCII字符串
  • 需满足 1<=字符串长度<567

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


使用方法：
  • 加载本数据包
  • 仔细阅读使用方法（也就是你现在在阅读的东西）。
  • 运行命令
    1. /function md5:reset
    复制代码
    （注意，每次计算前都必须运行该指令以重置系统。）
  • 输入字符串。本数据包目前支持两种输入方式。一、使用我之前制作的数据包'keyboard'。你可以在->此处<-找到它的使用方法。输入完毕后，执行
    1. /function md5:import_string
    复制代码
    以导入数据。由于这个键盘的使用十分不方便，只建议用来输入很短的字符串。二、使用项目中的test_string函数。具体地说，调用测试函数，使用方法为
    1. test_string("Put the string you want to test here!");
    复制代码
    然后编译运行后将生成的文件放入
    1. .minecraft/<Your World Name>/datapacks/md5/data/md5/functions/
    复制代码
    并运行
    1. /function md5:test_string
    复制代码
    导入字符串。
  • 运行
    1. /function md5:core_wrapper
    复制代码
    进行运算。注意：运行这个函数会造成明显卡顿。
  • 运行
    1. /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为例，摘抄自素学姐的代码）：
  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]