学习
实践
活动
工具
TVP
写文章
专栏首页极客挑战赛“垫底”逆袭!从一次错误中转换思路迎来破局
原创

“垫底”逆袭!从一次错误中转换思路迎来破局

在第二期极客挑战赛的ARM64赛道中,“HOOCCOOH”同学以480字节的成绩摘得赛道冠军。值得一提的是,这位同学为了参加arm64赛道,几乎是现学现用aarch64 指令集,瞬间新技能+1

或许,极客挑战赛的乐趣之一就在于通过不断学习、不断精钻细研,满足对技术的无穷探索欲。

下面由他带来ARM64赛道的解题思路和心得分享,也欢迎小伙伴们在文末留言,分享自己的解题报告链接。(原赛题传送门:腾讯极客挑战赛丨全世界最最最小的程序,等你来battle!


第一个错误方向

看到这个题目,立刻想到那个输出自己 MD5 的 gif ,碰撞啊!于是弄了一个碰撞器,撞出 128 对冲突数据串起来,然后把结果 128bit encode 进去让程序通过判断识别得到最终答案。由于目前个人电脑可以计算的方案需要两个 block 来做一次碰撞,通过枚举弄到 32 个前导零,程序仍需要存 (128-32)*128 byte = 12 KB 。巨大无比,当场垫底,于是立刻换思路。

老老实实算 MD5

首先按 wiki 抄一个 MD5 实现,千万不要抄比赛样例,那个把计算全部 unroll 了,体积上毫无优势。然后在基本代码上进行一些通用优化,大部分和 x86 思路差异不大,不细展开了。

  1. 手写汇编 + 手动构造 ELF 文件头拼接可执行文件,大家也懂
  2. ELF 头的 e_ident 末尾和 p_paddr 都可以随意塞数据,这里我塞进了一个常数 PI 。
  3. 最后一个块需要进行一些处理,可以在 ELF 头中设定页可写,然后在代码段直接写。
  4. MD5 内部状态直接预处理前 n-1 个块,塞进程序末尾;程序只需要求最后一个块即可。这里保证最后一个块不能超出 64 byte,最后控制得比较好,无需 pad 就满足了要求。
  5. MD5 计算用到一个 K[] 表,使用 sin 生成。x86(x87) 有 FSIN 指令可以直接用,但 aarch64 就没办法了,直接用个循环暴力求泰勒展开即可。我们需要 2^-32 的精度,搞不了奇技淫巧,循环次数要给够。记得之前需要把 x 缩放到 x % PI ,不然精度必挂;可使用循环减或除-取整-乘,指令数相同。
  6. 另有一个 S[] 表,发现每 16 个一组中为四个重复,可以去掉重复,然后稍微推导一下,通过 S[i >> 2 & 0b1100 | i & 0b11] 索引即可。
  7. 对于 i 的循环内的四种情况,我们不需要先比较跳转进去再跳转到结尾;因为我们都是设置 Fg ,于是可以:
    1. 啥都不管直接执行 case0
    2. 看看是否确实符合 case0 条件,是的话跳出
    3. 直接执行 case1 ,此时覆盖了 case0 的结果
    4. 看看是否符合 case1 条件,是的话跳出
    5. ...同理这样可以把比较+跳入+跳出变成只有比较+跳出。
  8. 由于上一条,我们可以复用不同轮中计算中间结果,比如 [0, 16) 轮的 ~B & D[48, 64) 轮的 B | ~D 按位相反。反正 aarch64 寄存器多,而且可以位运算同时取反,这里可以省几条指令。

针对 Aarch64 指令集的优化

  1. 善用 orn, eon, bic ,别再额外 not 了。
  2. 访存指令 ldr/str 有同时操作两个寄存器的版本 ldp/stp,一条指令 ldp x0, x1, [x8], #16 即可读入整个 16 byte state 并且步进指针。
  3. 访存指令的自动步进非常好用,而且步进没必要是读写的大小。我们可以滥用一下来达到“访存,然后调整到我们后续需要的位置上去”的效果,避免额外的 adr
  4. 在 2 中我们读进了两个 64bit 状态,但 MD5 计算都是 32bit 呀,怎么办?没关系,几乎所有计算指令都支持给一个操作数先移位再计算。我们寄存器值为 x0 = B << 32 | A, x1 = D << 32 | C
    • A-C, B-D 之间的运算,直接作为 64bit 运算即可,
    • 其他交错情况,可以将一个寄存器右移 32bit 再进行 64bit 运算,也只需要一条指令。
  5. 作为 4 的补充,一轮结束时轮换 ABCD 可用 extr 简化成三条指令。
  6. tbz/tbnz 可以代替几乎所有 cmp + b
  7. 输出代码稍微复用了一下 4bit to ASCII 的逻辑,一个循环处理 4bit 而不是 8bit。不过赛后看了别人的思路后发现这里其实是可以通过碰撞成只有数字来减少更多代码的。
  8. 剩下还有些微优化,比如反着输出来少两次 write 传参,加法不考虑进位通过随机调整程序来撞出一个正确答案等等。

反正最后成果是 480 byte 啦,其实还有一定优化空间。

一些体会

本来咱是 x86_64 选手... 但由于前几名过猛,咱又太菜,最后止步 400 byte 就优化不动了。于是想想之前了解过一点 ARM ,就现学了 aarch64 指令集换赛道跑。不得不说其实 aarch64 定长指令大大降低了心智负担,只需要专心于优化指令数就好,不用纠结各个变长指令长度了!

说起来有点奇怪,似乎 aarch64 赛道相比另两个挺冷门的,提交次数也没那么疯狂(逃

总之非常感谢这次比赛提供的机会吧,也学到了挺多新技术和技巧,非常有趣!

原创声明,本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

登录 后参与评论
0 条评论

相关文章

  • 新电商的逆袭

    互联网巨头的躬身入局、资本巨鳄的百般垂爱、创业者们的热情追捧让新零售当仁不让地成为后移动互联网时代的新风口。一时间,电商成为一个人人喊打,避之不及的存在。

    孟永辉
  • 「蔚小理」告别春天

    新能源汽车江湖正走向大乱斗。 作者 | 来自镁客星球的王饱饱 2022的3月份已经走到了尽头,意味着今年的春天也逐渐进入了尾声。 在这个多灾多难的第一季度,作为...

    镁客网
  • 后疫情时代,区块链发展将会出现哪些新风向?

    北京通证思维科技有限公司创始合伙人孟岩老师先声夺人,在本场区块链闭门会上提出了对行业的深刻看法与认识。他首先带大家回顾了区块链、数字货币等技术项目从被资本追捧,...

    TVP官方团队
  • 宁德时代迎阵痛期

    补贴退坡、原材料(钴、锂)涨价、外企入场......多方面因素的影响下,国内动力电池企业的日子并不好过。

    刘旷
  • 一个“退学生”到CTO的逆袭之路

    我曾是一个游戏网瘾少年,很严重的那种。6岁就开始玩街机,之后开始玩小霸王游戏机,初中三年长期混迹于街机房,高中三年开始进出网吧。

    田维常
  • 响铃:定义了好IP 阿里文学要怎么打造网文的增量市场

    和门户一样古老的互联网品种网络文学,虽然从来不曾没落过,但也谈不上有什么瞩目的成就,在互联网创新创业大潮下,码字这种最传统的形式起初显得有些不上不下的落寞,随着...

    曾响铃
  • AI写作最新突破可真假难辨,美国启动国家级AI计划 | 一周十大AI要闻

    OpenAI发布最新语言AI,编故事以假乱真,问答翻译写摘要都行,横扫各大语言建模任务

    量子位
  • AI写作最新突破可真假难辨,美国启动国家级AI计划 | 一周十大AI要闻

    OpenAI发布最新语言AI,编故事以假乱真,问答翻译写摘要都行,横扫各大语言建模任务

    量子位
  • 互联网医疗下半场,圆心科技三战IPO

    10月21日,北京圆心科技集团股份有限公司(下称“圆心科技”)向港交所第三次递表,闯关港股IPO。

    不二研究
  • 微博的短视频保卫战

    记得2014年前后,微信如日中天时,很多人都曾唱衰微博,今天说微博要被微信干掉、明天说微博活跃度下滑,当时的微博给人感觉就像今天的人人网一样,走下坡路仿佛已不可...

    罗超频道
  • 零伽壹链改案例:区块链赋能供应链应用 新电商逆袭成长

    近十年来,全球电子商务迎来了历史性的迅猛增长,无数人共同参与及见证了这场史无前例的“大跃进”,并且势头仍在持续。利用网络实现商务交易等业务,跨境电商、境内电商、...

    用户7573724
  • SaaS颠覆传统软件到底是不是个伪命题?

    编者按:本文作者王戴明是具有12年信息化咨询与管理经验的行业老兵,他通过对行业的观察以及与曾经客户的交流发现,即便近几年SaaS的概念炒得火热,但客户本身和客户...

    人称T客
  • 盘点2014:10个词让你看懂今年的移动互联网

      2014年就要过去了,这一年,微商、众筹、O2O、自媒体、境外电商、互联网金融、P2P租车、大数据、移动支付、社会化营销等成为最大的移动互联网风口。   时...

    小莹莹
  • O2O虚火太重需要降温了

    首发百度百家。 “全国人民用筷子用得好好的,突然跳出一大款说改用刀叉吧用一次我给点儿钱……”,拉卡拉总裁孙陶然对巨头O2O大战如此点评,“所谓O2O,传统...

    罗超频道
  • 独家《九次方·金融大数据白皮书》全文下载

    大数据文摘

扫码关注腾讯云开发者

领取腾讯云代金券