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然后转换成数字或字母。结束后看群里大佬们的交流，发现跟大佬们差距还很大，才知道还有很多地方可以优化，大佬们请轻喷！