大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说LSD基数排序_mll基因重排,希望能够帮助大家进步!!!
版本:Release
优化选项:O2
调试工具:OD
源码:
//LSD基数排序(桶排序,模拟队列实现)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 11 //PS:set nodes number
void listsort(int a[],int link[],int n,int first);
int digit(int a,int i,int r)
{
int n=2-i;
while(n>0&&(a/=r))
n--;
a%=10;
return a;
}
int radixsort(int a[],int link[],int d,int r,int n)
{
int i,last,first=1,bin,current;
int front[10],rear[10];//10个桶
for(i=1;i<n;i++)
link[i]=i+1;
link[n]=0;
for(i=d-1;i>=0;i--)//对相应位排序入桶
{
for(bin=0;bin<r;bin++)
{
front[bin]=0;
rear[bin]=0;
}
for(current=first;current;current=link[current])
{
bin=digit(a[current],i,r);//取相应位的数字
if(front[bin]==0)
front[bin]=current;
else
link[rear[bin]]=current;
rear[bin]=current;
}
for(bin=0;!front[bin];bin++)
;
first=front[bin];
last=rear[bin];
for(bin++;bin<r;bin++)//将各桶连接
if(front[bin])
{
link[last]=front[bin];
last=rear[bin];
}
link[last]=0;
}
return first;
}
int main()
{
int i,first,current;
int a[MAX_SIZE];
int link[MAX_SIZE];
srand((unsigned)time(0));
for(i=1;i<MAX_SIZE;i++)
a[i]=rand()%1000;
for(i=1;i<MAX_SIZE;i++)
printf("%4d",a[i]);
putchar('\n');
first=radixsort(a,link,3,10,10);
for(current=first;current;current=link[current])
printf("%4d",a[current]);
/*
listsort(a,link,MAX_SIZE,first);
for(i=1;i<MAX_SIZE;i++)
printf("%4d",a[i]);
链表记录重放*/
system("pause");
return 0;
}
/*
void listsort(int a[],int link[],int n,int first)//链表记录重放
{
int q,i,temp;
for(i=1;i<n;i++)
{
while(first<i) first=link[first];
q=link[first];
if(first!=n)
{
SWAP(a[i],a[first],temp);
link[first]=link[i];
link[i]=first;
}
first=q;
}
}
*/
主函数就不贴了,很简单
这里贴上主要的排序函数,在下面的代码中假设不知道源码的情况下,我假设了4个int [10]大小的数组,其中2个是参数a[10],b[10],2个是函数内的局部变量c[10],d[10]
01231000 >/$ 83EC 50 sub esp, 50 ; 此时eax中存放着待排序数组a[10],ebx存放另一个数组b[10]
01231003 |. 55 push ebp
01231004 |. 56 push esi
01231005 |. 33ED xor ebp, ebp
01231007 |. C743 04 02000>mov dword ptr [ebx+4], 2 ; 初始化第二个数组
0123100E |. C743 08 03000>mov dword ptr [ebx+8], 3
01231015 |. C743 0C 04000>mov dword ptr [ebx+C], 4
0123101C |. C743 10 05000>mov dword ptr [ebx+10], 5
01231023 |. C743 14 06000>mov dword ptr [ebx+14], 6
0123102A |. C743 18 07000>mov dword ptr [ebx+18], 7
01231031 |. C743 1C 08000>mov dword ptr [ebx+1C], 8
01231038 |. C743 20 09000>mov dword ptr [ebx+20], 9
0123103F |. C743 24 0A000>mov dword ptr [ebx+24], 0A
01231046 |. 57 push edi
01231047 |. B8 01000000 mov eax, 1
0123104C |. 896B 28 mov dword ptr [ebx+28], ebp
0123104F |. 90 nop
01231050 |> 33C9 /xor ecx, ecx ; 这可是个大循环啊~~~先初始化所有的临时变量b[10],c[10]
01231052 |. 894C24 34 |mov dword ptr [esp+34], ecx
01231056 |. 894C24 38 |mov dword ptr [esp+38], ecx
0123105A |. 894C24 3C |mov dword ptr [esp+3C], ecx
0123105E |. 894C24 40 |mov dword ptr [esp+40], ecx
01231062 |. 894C24 44 |mov dword ptr [esp+44], ecx
01231066 |. 894C24 48 |mov dword ptr [esp+48], ecx
0123106A |. 894C24 4C |mov dword ptr [esp+4C], ecx
0123106E |. 894C24 50 |mov dword ptr [esp+50], ecx
01231072 |. 894C24 54 |mov dword ptr [esp+54], ecx
01231076 |. 894C24 58 |mov dword ptr [esp+58], ecx
0123107A |. 894C24 0C |mov dword ptr [esp+C], ecx
0123107E |. 894C24 10 |mov dword ptr [esp+10], ecx
01231082 |. 894C24 14 |mov dword ptr [esp+14], ecx
01231086 |. 894C24 18 |mov dword ptr [esp+18], ecx
0123108A |. 894C24 1C |mov dword ptr [esp+1C], ecx
0123108E |. 894C24 20 |mov dword ptr [esp+20], ecx
01231092 |. 894C24 24 |mov dword ptr [esp+24], ecx
01231096 |. 894C24 28 |mov dword ptr [esp+28], ecx
0123109A |. 894C24 2C |mov dword ptr [esp+2C], ecx
0123109E |. 894C24 30 |mov dword ptr [esp+30], ecx
012310A2 |. 8BF0 |mov esi, eax
012310A4 |. 85C0 |test eax, eax
012310A6 |. 74 67 |je short 0123110F ;在下面这个循环凡是用到ebx的取内存数据都是类似b[ecx],凡是用到esp的都是取临时数组c[ecx] d[ecx]此类
012310A8 |. EB 06 |jmp short 012310B0
012310AA | 8D9B 00000000 |lea ebx, dword ptr [ebx]
012310B0 |> 8B4424 60 |/mov eax, dword ptr [esp+60] ; 传进来的参数,存的是待排序数组地址
012310B4 |. 8B0CB0 ||mov ecx, dword ptr [eax+esi*4]
012310B7 |. 8BFD ||mov edi, ebp
012310B9 |. 85ED ||test ebp, ebp
012310BB |. 7E 1B ||jle short 012310D8
012310BD |. 8D49 00 ||lea ecx, dword ptr [ecx]
012310C0 |> B8 67666666 ||/mov eax, 66666667 ;下面几个是除法优化后的指令(ecx/10),如果不明白可以参考第一篇hash逆向,里面有更详细的解释
012310C5 |. F7E9 |||imul ecx
012310C7 |. C1FA 02 |||sar edx, 2
012310CA |. 8BCA |||mov ecx, edx
012310CC |. C1E9 1F |||shr ecx, 1F
012310CF |. 03CA |||add ecx, edx ;截至到这里就取得了除法的商
012310D1 |. 74 05 |||je short 012310D8
012310D3 |. 4F |||dec edi
012310D4 |. 85FF |||test edi, edi
012310D6 |.^ 7F E8 ||\jg short 012310C0
012310D8 |> B8 67666666 ||mov eax, 66666667 ;依然是除法优化,ecx/10
012310DD |. F7E9 ||imul ecx
012310DF |. C1FA 02 ||sar edx, 2
012310E2 |. 8BC2 ||mov eax, edx
012310E4 |. C1E8 1F ||shr eax, 1F
012310E7 |. 03C2 ||add eax, edx
012310E9 |. 8D1480 ||lea edx, dword ptr [eax+eax*4]
012310EC |. 03D2 ||add edx, edx
012310EE |. 2BCA ||sub ecx, edx ; 这里应该是得到指定位数字的结果吧,前面先不管了看不懂这种优化。。
012310F0 |. 837C8C 0C 00 ||cmp dword ptr [esp+ecx*4+C], 0 ; 下面几句大体上是这样if(c[ecx]==0) c[ecx]=esi; else b[d[ecx]]=esi;
012310F5 |. 75 06 ||jnz short 012310FD
012310F7 |. 89748C 0C ||mov dword ptr [esp+ecx*4+C], esi
012310FB |. EB 07 ||jmp short 01231104
012310FD |> 8B448C 34 ||mov eax, dword ptr [esp+ecx*4+34]
01231101 |. 893483 ||mov dword ptr [ebx+eax*4], esi
01231104 |> 89748C 34 ||mov dword ptr [esp+ecx*4+34], esi
01231108 |. 8B34B3 ||mov esi, dword ptr [ebx+esi*4]
0123110B |. 85F6 ||test esi, esi ; 这个比较大的循环里整体浏览下也可以发现esi是循环判断条件,但esi又牵扯到前面几个指令,其中又有我们暂时不知道干嘛的寄存器,于是可以先把架子写出来加上注释,等弄懂内部循环后再来修改也行
0123110D |.^ 75 A1 |\jnz short 012310B0
0123110F |> 33C9 |xor ecx, ecx
01231111 |. 394C24 0C |cmp dword ptr [esp+C], ecx
01231115 |. 75 08 |jnz short 0123111F
01231117 |> 41 |/inc ecx
01231118 |. 837C8C 0C 00 ||cmp dword ptr [esp+ecx*4+C], 0
0123111D |.^ 74 F8 |\je short 01231117
0123111F |> 8B448C 0C |mov eax, dword ptr [esp+ecx*4+C]
01231123 |. 8B548C 34 |mov edx, dword ptr [esp+ecx*4+34]
01231127 |. 41 |inc ecx
01231128 |. 83F9 0A |cmp ecx, 0A
0123112B |. 7D 1B |jge short 01231148
0123112D |. 03C9 |add ecx, ecx
0123112F |. 03C9 |add ecx, ecx
01231131 |> 8B7C0C 0C |/mov edi, dword ptr [esp+ecx+C]
01231135 |. 85FF ||test edi, edi
01231137 |. 74 07 ||je short 01231140
01231139 |. 893C93 ||mov dword ptr [ebx+edx*4], edi
0123113C |. 8B540C 34 ||mov edx, dword ptr [esp+ecx+34]
01231140 |> 83C1 04 ||add ecx, 4
01231143 |. 83F9 28 ||cmp ecx, 28
01231146 |.^ 7C E9 |\jl short 01231131
01231148 |> 45 |inc ebp
01231149 |. 83FD 02 |cmp ebp, 2 ; 这里ebp为判断条件并且可以发现没有地方改变ebp的值,于是整个for框架可以直接写出来了
0123114C |. C70493 000000>|mov dword ptr [ebx+edx*4], 0
01231153 |.^ 0F8E F7FEFFFF \jle 01231050
01231159 |. 5F pop edi
0123115A |. 5E pop esi
0123115B |. 5D pop ebp
0123115C |. 83C4 50 add esp, 50
0123115F \. C3 retn
注释不多,不过我想说说逆向这个函数的时候的我的方法
首先浏览下所有的跳转,清楚哪些跳转跳向哪里,然后观察一些条件判断用到的寄存器,回溯看看有没有在其他地方用到他而不用管他到底做了什么,如果只在判断处用到了的话最好了那么直接用个变量代替寄存器就能写出这个循环的整体架子,然后逐步深入,诸如if else类的跳转也可以先写出来而不用管其内部指令干了什么,就像造房子的时候先把它的架子给搞出来,之后内部再慢慢添砖加瓦,我们可以先对函数有个模糊的架子印象然后再去纠结这个函数到底做了什么
我以前也干过像把寄存器记在纸上逐条翻译指令最后再整理出结果这样纯粹蛮力的逆向一个函数,至于怎样做更效率更准确我也不好说,只能说我个人觉得有技巧性的逆向更好,学到的也更多
下面我再把边逆向边还原出的代码贴上来,应该也能看出点门道吧嗯~
此代码由Java架构师必看网-架构君整理
int eax=1;int c[10] d[10]
for (int i=0;i<=2;i++,b[edx]=0)
{
esi=eax;
for(esi=eax;esi;esi=b[esi])
{
ecx=a[esi];
取得特定位于ecx
if(c[ecx]==0)
{
c[ecx]=esi;
}
else
{
b[ d[ecx] ]=esi;
}
d[ecx]=esi;
}
for(x=c[ecx=0];!x;ecx++)
;
eax=c[ecx];edx=d[ecx];
ecx++;
for(;ecx<10;ecx++)
{
if(c[ecx])
{
b[edx]=c[ecx];
edx=d[ecx];
}
}
}