Minecraft(我的世界)中文论坛

 找回密码
 注册(register)
查看: 2131|回复: 40

[命令] 【CBL|丢人素学姐, pku_zzzz】在Minecraft中计算字符串的MD5值

  [复制链接]
丢人素学姐 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1859
钻石
性别
保密
注册时间
2017-3-6
查看详细资料
发表于 2019-3-1 16:52:55 | 显示全部楼层 |阅读模式

您尚未登录,立即登录享受更好的浏览体验!

您需要 登录 才可以下载或查看,没有帐号?注册(register)

x
本帖最后由 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


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

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

  11.     //carry=c.d[c.len++]/2;
  12.     ofs_add << "scoreboard players operation stemp1 svars"
  13.                 << " = @s vars." << RES << endl;
  14.     ofs_add << "scoreboard players operation stemp1 svars"
  15.                 << " /= const2 svars" << endl;

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

  19.     ofs_add.close();

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

  22. }
复制代码
        等等!你看到了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











来自群组: Command Block Logic

评分

参与人数 14人气 +37 金粒 +252 贡献 +3 收起 理由
fayedada + 1 + 20 MCBBS有你更精彩~
CCxia + 1 MCBBS有你更精彩~
liach + 2 + 40 写这么多记分板计算很辛苦啊
+ 2 + 20 别人的世界
buhuichongfu + 2 + 10 你的世界……
langyo_v3 + 2 + 40 .
chyx + 3 MCBBS有你更精彩~
SPGoding + 4 MCBBS有你更精彩~
贰逼 + 4 + 40 + 1 精华
ItIsEnderman + 4 + 32 可海星
xmdhs + 3 可怕
玄素 + 4 + 50 + 2 MCBBS有你更精彩~
匿名的网友 + 3 MCBBS有你更精彩~
ETW_Derp + 2 可怕

查看全部评分

pku_zzzz 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1013
钻石
性别
保密
注册时间
2018-1-17
查看详细资料
发表于 2019-3-1 17:00:55 | 显示全部楼层
沙发?

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

其实感觉这样的想法还是挺容易想到的,毕竟现在的命令差不多也快发展成面向实体编程了(笑)。

评分

参与人数 2人气 +4 贡献 +2 收起 理由
SPGoding + 4 MCBBS有你更精彩~
玄素 + 2 MCBBS有你更精彩~

查看全部评分

回复

使用道具 举报

爱心大魔王 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
51700
钻石
性别
保密
注册时间
2014-6-7
查看详细资料
发表于 2019-3-1 18:15:32 | 显示全部楼层
计算MD5你们是真的恐怖,以后都不用下软件了,MC里计算就好了

评分

参与人数 2人气 +2 收起 理由
langyo + 1 ↓ 可能是的
+ 1 等等,你不会成为第一个真·屠龙者吧(卤蛋.

查看全部评分

回复

使用道具 举报

森林蝙蝠 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
6972
钻石
性别
保密
注册时间
2016-6-16
查看详细资料
发表于 2019-3-1 20:22:46 | 显示全部楼层
太牛逼了,衬托得我渺小不堪,一无是处。
回复

使用道具 举报

MCHanxi 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1595
钻石
性别
保密
注册时间
2014-7-8
查看详细资料
发表于 2019-3-1 20:29:45 | 显示全部楼层
太强了,mc迟早变成运行环境(大雾)
回复

使用道具 举报

zyjking 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
10473
钻石
性别
保密
注册时间
2016-1-27
查看详细资料
发表于 2019-3-1 21:56:27 | 显示全部楼层
在MC中计算MD5……
你们是有多闲……
回复

使用道具 举报

我是文明人 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1759
钻石
性别
保密
注册时间
2015-2-28
查看详细资料
发表于 2019-3-2 18:19:29 | 显示全部楼层
感谢楼主分享~学到了
回复

使用道具 举报

fanyanfeng 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
76
钻石
性别
保密
注册时间
2019-3-2
查看详细资料
发表于 2019-3-2 21:52:51 | 显示全部楼层
厉害,没谁了
回复

使用道具 举报

taibaiOVO 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
259
钻石
性别
保密
注册时间
2019-2-2
查看详细资料
发表于 2019-3-3 10:07:06 | 显示全部楼层
感谢楼主分享~学到了
回复

使用道具 举报

princess01 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
645
钻石
性别
保密
注册时间
2018-11-24
查看详细资料
发表于 2019-3-4 00:22:15 | 显示全部楼层
突然感到自己的渺小系列
回复

使用道具 举报

WB1436871576 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
67
钻石
性别
保密
注册时间
2019-2-12
查看详细资料
发表于 2019-3-8 11:44:04 | 显示全部楼层
牛逼到我看不懂...............................
回复

使用道具 举报

164978694 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
10
钻石
性别
保密
注册时间
2019-3-10
查看详细资料
发表于 2019-3-10 16:16:57 | 显示全部楼层
正经:
我眼睛疼

余味:
[图片]

正经:
不能一直盯着电脑

余味:
嗯嗯 那就别看了
回复

使用道具 举报

爱国假面 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
940
钻石
性别
保密
注册时间
2019-2-15
查看详细资料
发表于 2019-3-10 17:58:35 | 显示全部楼层
。。。大佬,佩服!
回复

使用道具 举报

2984035075 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
49
钻石
性别
保密
注册时间
2019-3-15
查看详细资料
发表于 2019-3-16 08:20:48 | 显示全部楼层
ooooooooooooo

评分

参与人数 1人气 -1 金粒 -10 收起 理由
玄素 -1 -10 无意义

查看全部评分

回复

使用道具 举报

...Fisherman 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
182
钻石
性别
保密
注册时间
2017-8-31
查看详细资料
发表于 2019-3-17 14:18:23 | 显示全部楼层
学到了,哈哈哈
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册(register)

本版积分规则

Archiver|小黑屋|Mcbbs.net ( 京ICP备15023768号-1 ) | 京公网安备 11010502037624号 | 手机版

GMT+8, 2019-9-22 09:27 , Processed in 0.061622 second(s), Total 27, Slave 22 queries , Gzip On, MemCached On.

"Minecraft"以及"我的世界"为Mojang Synergies AB的商标 本站与Mojang以及微软公司没有从属关系

© 2010-2019 我的世界中文论坛 版权所有 本站原创图文内容版权属于原创作者,未经许可不得转载

快速回复 返回顶部 返回列表