学习
实践
活动
工具
TVP
写文章
专栏首页极客挑战赛Hard模式赛道如何破关?这种“朴素”方法也管用
原创

Hard模式赛道如何破关?这种“朴素”方法也管用

在第二期极客挑战赛的MIPS64赛道中,“我就看看不参加”同学以581字节的成绩最终获得赛道冠军。除了是赛道第一名,他还是所有赛道中累计提交次数最多的同学(共85次)。一次次的提交,一次次的改进优化,一个个字节的减少,是锲而不舍、不断打磨的精神体现,也是追求技术极致的乐趣所在。

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


ELF file header 中间有一些空,可以插入一些常数和代码,后面的8字节可以直接去掉。去掉后末尾的phentsize为1,刚好Program segment header的p_type也为1,所以可以共用2字节。

Program segment header后的align可以直接去掉,中间的空以及p_filesz,p_memsz的低位,可以插入一些常数和代码。

具体处理如下:

.include "const.asm"

elfHead:
.long   0x464c457f    
.long   0x00010102    
md5Magic:
.long   0x67452301
.long   0xefcdab89

.short   2 # e_type
.short   8 # e_machine,
.long   1 # e_version 

.quad   ENTRY_ADDR # e_entry, 
.quad   0x38 #e_phoff

li   $28,LOAD_ADDR
.setnoreorder
.setnomacro
bmain
lw$11,8($28)
.setmacro
.setreorder

.short   64 #e_ehsize
.short   56 #e_phentsiz

progHead:
.long   1 #p_type
.long   7 #p_flags,
.quad   P_OFFSET # p_offset
.quad   ENTRY_ADDR # p_vaddr,
sin1:       #cos1 直接根据sin1算出
.long2399735053
.long1072360788

.long1106247680 
double4294967296: 
.long 0
.long1106247680
.long 0

...

由于MIPS指令都是定长的4字节,加之水平有限,所以中间还是有很多空间没有利用。

然后就是计算MD5,然后转换,都是很常规的做法,尽量重复利用指令。

sinx的计算

MIPS64貌似没有直接计算sin的指令,这里可以采用泰勒展开式:

迭代到17就可满足精度,但是我用泰勒公式写出来的指令较多

因为不需要计算任意角,只需要计算1-64的整数,所以最后采用了两角和公式:

sin1、cos1作为常数,循环依次加到64即可

...

ldc1$f2,DATA_BASE($28)   #sin1
lwc1$f1,DATA_BASE-24($28) #cos(x-1)   因为文件头中数值为1的很多,随便读一个即可
cvt.d.w$f1,$f1             #cos(x-1)   因为文件头中数值为1的很多,随便读一个即可
dmtc1$0,$f0               #sin(x-1) 貌似线上mips赛道即使为0,寄存器也要初始化
nmsub.d $f3,$f1,$f2,$f2     #计算cos1
sqrt.d $f3,$f3             #计算cos1

...


mul.d$f7,$f0,$f3     #sin(x-1)*cos1
mul.d$f0,$f0,$f2     #sin(x-1)*sin1
madd.d$f7,$f7,$f1,$f2   #sinx = cos(x-1)*sin1 + sin(x-1)*cos1 
msub.d$f1,$f0,$f1,$f3   #conx = cos(x-1)*cos1 - sin(x-1)*sin1

...

这里因为不用考虑性能,可以不用预先计算,在需要时计算,省略循环和读写的指令

#MIPS跟另两个平台的一些区别

  • 线上MIPS环境貌似寄存器即使为0,也需要初始化
  • MIPS架构中,为了充分利用CPU流水线,所有转移指令后都紧跟一条延迟槽指令。非Likely转移指令延迟槽中指令总会得到执行。所以这里需要特别注意,为了防止编译器自动用nop填充延迟槽,可以用.setnoreorder.set  nomacro,然后自己写延迟槽指令。
  • MIPS和ARM貌似没有循环左移指令(大概是因为循环左移跟循环右移可以转换),所以需要把循环左移的常数换成循环右移的常数,避免在运行时转换

一些优化点

  • 最后的syscall指令中,最后3字节可以去掉,syscall指令为0x0000000c,高位的3个字节都是0可以去掉,填充后变成了0x0000080c, 但是syscall指令第6-26bit貌似可以随意更改(syscall 0 - 0xfffff),所以两个syscall指令第6-26bit其实也可以利用

总体方法很朴素,计算md5也没做特殊处理,就是老老实实的算md5然后转换成数字或字母。结束后看群里大佬们的交流,发现跟大佬们差距还很大,才知道还有很多地方可以优化,大佬们请轻喷!

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

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

登录 后参与评论
0 条评论

相关文章

  • 【Scikit-Learn 中文文档】概率校准 - 监督学习 - 用户指南 | ApacheCN

    1.16. 概率校准 执行分类时, 您经常希望不仅可以预测类标签, 还要获得相应标签的概率. 这个概率给你一些预测的信心. 一些模型可以给你贫乏的概率估计,...

    片刻
  • 【Scikit-Learn 中文文档】神经网络模块(监督的)- 监督学习 - 用户指南 | ApacheCN

    中文文档: http://sklearn.apachecn.org/cn/0.19.0/modules/calibration.html 英文文档: htt...

    片刻
  • git撤销修改各种情况

    如何在Git里撤销(几乎)任何操作 一、撤销一个已经公开的改变 场景:已经执行了gitpush,将修改发送到了github,需要撤销某一个commit。 方法:...

    fanfan
  • LeetCode 32,并不Hard的难题,解法超级经典,带你领略动态规划的精彩

    今天给大家分享的是LeetCode当中的32题,这是一道Hard难度的题。也是一道经典的字符串处理问题,在接下来的文章当中,我们会详细地解读有关它的三个解法。

    TechFlow-承志
  • 数据结构 | 每日一练(107)

    ——老子

    小林C语言
  • 每周学点大数据 | No.33最大独立集

    No.33期 最大独立集 Mr. 王:好,现在我们来谈谈最大独立集的问题。首先求解最大独立集是一个NP-hard问题,接下来要介绍的这个求解方法是一个近...

    灯塔大数据
  • 有关SaaS趋势的四个核心问题

    来源:ToBeSaaS  作者 :戴珂  ---- 有媒体请我写一篇文章,预测一下中国SaaS的未来。 坦率讲,这跟预测大盘一样的不靠谱,无论预测成什么,...

    腾讯SaaS加速器
  • 用API优先和API模拟打破软件交付关键路径上的依赖

    开发团队正在使用 API 模拟来打破关键路径依赖关系,并将串行流程为并行的。本文探讨了应该在哪些地方使用 API 模拟才能产生最大的影响,并提供了一个模型来估算...

    深度学习与Python
  • 算法常见问题

    逻辑回归要点:逻辑回归是通过sigmoid函数使损失函数达到最小或者是似然函数达到最大通过相应的优化算法求出其中的参数值实现分类。(什么优化算法:了解过梯度下降...

    步履不停凡
  • 长城汽车转型:不靠挖高管,不靠买业务

    雷刚 发自 副驾寺 量子位 | 公众号 QbitAI 汽车工业大变革中,谁是转型变革最富成效的玩家? 长城汽车——至少从今年、从现在开始,可以列入年度候选项了。...

    量子位
  • 一篇文章洞悉ToB SaaS的增长规律

    来源:ToBeSaaS 作者:戴珂 ---- ToB SaaS的本质就是增长,增长是ToB创业者始终追逐的目标。看懂SaaS增长模型和洞悉其增长规律,让增长在你...

    腾讯SaaS加速器
  • 重学数据结构和算法(三)之递归、二分、字符串匹配

    周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?别忘了你是程序员,这个可难不倒你,递归就开始排...

    六月的雨
  • 从春招到秋招,算法工程师养成记(阿里+腾讯+其他)

    自我介绍 大家好,我是老班长,一名老牛油(至于多老呢?我基本是第一批关注牛客网的同学,我加牛客网qq1群的时候,群里只有400多人(现在估计10多个群了吧),那...

    牛客网
  • LeetCode 23 Hard,K个链表归并

    https://leetcode.com/problems/merge-k-sorted-lists/

    TechFlow-承志
  • MCU HardFault问题查找和破解方法

    在嵌入式开发中,偶尔会遇到Hard Fault死机的异常,常见产生Hard Fault的原因大致有以下几类:

    用户2366192
  • 传统电商“漏斗模型”VS抖音兴趣电商“雪球增长模型”

    抖音电商在今年4月初提出“兴趣电商”之后,业内外都表现出极大的兴趣,特别是商家们,都希望借助抖音电商的创新得到发展机会,从而在红利期占尽先机。

    庄帅
  • Linux内核实战(三)- 学学基本命令

    Linux操作系统有很多功能,其中最简单和直接的方式就是命令行(Command Line)。

    JavaEdge
  • 这不是你以为的汽车金融行业

    汽车金融市场的格局将以一个比我们任何人的预料都快的速度变化起来。一切过去的从业者,一切准备进入的新玩家,都必须快速提高认知能力而决定是否被时代弃取。

    用户1310347
  • 别滥用隐式反馈了,模型学偏了!

    现在大家都习惯用隐式反馈来学习推荐模型,并作用于线上推荐系统(十方也不例外)。大量的隐式反馈数据确实缓解了数据稀疏的问题,但是这些数据很多并没有反馈用户真正的需...

    炼丹笔记

扫码关注腾讯云开发者

领取腾讯云代金券