此算法为hash中比较简单的线性探测法，代码优化选项OD（无）
顺便说句，这些算法实现大多会拿我在学数据结构的时候自己实现的或者书上的，所以风格编码肯定不能和百度到的那些比，权当练练手，不过物尽其用吧，也不枉费当时特意把这些代码保存下来，嘿嘿
以下为C的算法代码：
//线性探测
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAX_SIZE 13
#define b 13
char *ht[MAX_SIZE];
int stringtoint(char *key)
{
int number;
for(number=0;*key;key++)
number+=*key;
return number;
}
int f(int k)
{
return k%b;
}
char* search(char* key)
{
int current,homebucket;
homebucket=f(stringtoint(key));
for(current=homebucket;ht[current]&&strcmp(ht[current],key);)
{
current=(current+1)%b;
if(current==homebucket)
return NULL;
}
if(strcmp(ht[current],key)==0)
return ht[current];
return NULL;
}
void insert(char *key)
{
int homebucket,current;
homebucket=f(stringtoint(key));
for(current=homebucket;ht[current];)
{
current=(current+1)%b;
if(current==homebucket)
return;
}
ht[current]=(char*)malloc(sizeof(*key));
strcpy(ht[current],key);
}
int main()
{
int i;
char word[MAX_SIZE];
for(i=0;i<MAX_SIZE;i++)
{
ht[i]=NULL;
}
for(i=0;i<3;i++)
{
scanf("%s",word);
insert(word);
fflush(stdin);
}
printf("search:");
scanf("%s",word);
printf("%s\n",search(word));
for(i=0;i<MAX_SIZE;i++)
printf("%s\n",ht[i]);
system("pause");
return 0;
}
惯例，OD跟踪，往下翻，有个jmp main指令，很明显就是它啦，F7跟进去，显示如下代码
01381170 >/$ 83EC 18 sub esp, 18 ; 首先分配临时存储空间
01381173 |. A1 00303801 mov eax, dword ptr [__security_cookie]
01381178 |. 33C4 xor eax, esp
0138117A |. 894424 14 mov dword ptr [esp+14], eax
0138117E |. 33C0 xor eax, eax
01381180 |. 53 push ebx
01381181 |. 8B1D A8203801 mov ebx, dword ptr [<&MSVCR90.fflush>] ; MSVCR90.fflush
01381187 |. 55 push ebp
01381188 |. 8B2D AC203801 mov ebp, dword ptr [<&MSVCR90.__iob_func>] ; MSVCR90.__p__iob
0138118E |. 56 push esi
0138118F |. 8B35 B0203801 mov esi, dword ptr [<&MSVCR90.scanf>] ; MSVCR90.scanf
01381195 |. A3 6C333801 mov dword ptr [ht], eax ; 初始化全局变量的指针数组
.....................
......................
013811DE |. 57 push edi
013811DF |. 90 nop
013811E0 |> 8D4424 14 /lea eax, dword ptr [esp+14] ; eax指向分配存储空间中最后一个变量
013811E4 |. 50 |push eax
013811E5 |. 68 04213801 |push 01382104 ; ASCII "%s"
013811EA |. FFD6 |call esi ; scanf("%s",esp+14)
013811EC |. 8D7C24 1C |lea edi, dword ptr [esp+1C] ; 其实这个esp+1c就是上面那个esp+14,详细可以查查C的调用约定
013811F0 |. E8 FBFEFFFF |call insert ; 额。。这个我们先不管，先把主函数整体给反汇编出来
013811F5 |. FFD5 |call ebp ; fflush
013811F7 |. 50 |push eax
013811F8 |. FFD3 |call ebx
013811FA |. 83C4 0C |add esp, 0C ; 堆栈平衡跑这来了，服了
013811FD |. 836C24 10 01 |sub dword ptr [esp+10], 1 ; 其实就是上面那个mov dword ptr [esp+c],3，看到没
01381202 |.^ 75 DC \jnz short 013811E0 ; if [esp+10]==1 break;
01381204 |. 8B1D A0203801 mov ebx, dword ptr [<&MSVCR90.printf>] ; MSVCR90.printf
0138120A |. 68 08213801 push 01382108 ; /format = "search:"
0138120F |. FFD3 call ebx ; \printf
01381211 |. 8BCF mov ecx, edi
01381213 |. 51 push ecx
01381214 |. 68 04213801 push 01382104 ; ASCII "%s"
01381219 |. FFD6 call esi ; scanf调用
0138121B |. E8 E0FDFFFF call search
01381220 |. 50 push eax ; 从这里可以看出eax的返回值是个字符串指针
01381221 |. 68 10213801 push 01382110 ; ASCII "%s",LF
01381226 |. FFD3 call ebx
01381228 |. 83C4 14 add esp, 14 ; 还是平衡堆栈
0138122B |. BE 6C333801 mov esi, offset ht ; ht是个全局变量
01381230 |. 5F pop edi
01381231 |> 8B16 /mov edx, dword ptr [esi]
01381233 |. 52 |push edx
01381234 |. 68 10213801 |push 01382110 ; ASCII "%s",LF
01381239 |. FFD3 |call ebx
0138123B |. 83C6 04 |add esi, 4 ; 由此可见全局变量是每个元素4字节的数组
0138123E |. 83C4 08 |add esp, 8
01381241 |. 81FE A0333801 |cmp esi, offset _adjust_fdiv
01381247 |.^ 7C E8 \jl short 01381231
01381249 |. 68 14213801 push 01382114 ; /command = "pause"
0138124E |. FF15 A4203801 call dword ptr [<&MSVCR90.system>] ; \system
01381254 |. 8B4C24 24 mov ecx, dword ptr [esp+24]
01381258 |. 83C4 04 add esp, 4
0138125B |. 5E pop esi
0138125C |. 5D pop ebp
0138125D |. 5B pop ebx
0138125E |. 33CC xor ecx, esp
01381260 |. 33C0 xor eax, eax
01381262 |. E8 04000000 call __security_check_cookie
01381267 |. 83C4 18 add esp, 18
0138126A \. C3 retn
下面是insert函数，简单的将字符串每个字节相加，得到的数再取余数，然后看能不能插入hash表，不过有个地方代码很古怪，作用肯定是求余啦，只是。。。
012810F0 >/$ 8A07 mov al, byte ptr [edi] ; 这里edi就是指向输入的字符啦
012810F2 |. 33C9 xor ecx, ecx
012810F4 |. 8BD7 mov edx, edi ; 随时关注edi的动向哦~~~
012810F6 |. 84C0 test al, al
012810F8 |. 74 12 je short 0128110C
012810FA |. 8D9B 00000000 lea ebx, dword ptr [ebx] ; 前面用到的寄存器在这都有效。。。
01281100 |> 0FBEC0 /movsx eax, al ; movsx：此乃带符号扩展
01281103 |. 42 |inc edx
01281104 |. 03C8 |add ecx, eax
01281106 |. 8A02 |mov al, byte ptr [edx]
01281108 |. 84C0 |test al, al
0128110A |.^ 75 F4 \jnz short 01281100 ; 仔细分析这一段代码就是把每个字符的Ascii数值相加放入ecx
0128110C |> B8 4FECC44E mov eax, 4EC4EC4F ; 除法，取模运算的优化，定点表示法(即4EC4EC4F为除数的倒数小数位的1倍或2的n次方倍的16进制表示)
01281111 |. F7E9 imul ecx ;指令执行后eax为商的小数部分，edx为商的整数部分（可能是2的n次方倍）
01281113 |. C1FA 02 sar edx, 2 ; 带符号右移4位，由此可以看出商为真正的商的4倍
01281116 |. 8BC2 mov eax, edx
01281118 |. C1E8 1F shr eax, 1F ;取符号位（适应负数情况）
0128111B |. 03C2 add eax, edx ;加上符号位
0128111D |. 6BC0 0D imul eax, eax, 0D ; 三操作数乘法指令，以前还真没见过 eax=eax*0D 如是
01281120 |. 2BC8 sub ecx, eax ; 执行后ecx即为余数，(x%y=x-(x/y)*y) ，还不明白可以去看百度文库的代码逆向文章其中有除法，取模的优化详解~~
01281122 |. 833C8D 6C3328>cmp dword ptr [ecx*4+ht], 0
0128112A |. 56 push esi
0128112B |. 8BF1 mov esi, ecx
0128112D |. 74 1C je short 0128114B ; 如果为NULL
0128112F |. 90 nop
01281130 |> 8D46 01 /lea eax, dword ptr [esi+1] ; ht数组的下一个下标
01281133 |. 99 |cdq
01281134 |. BE 0D000000 |mov esi, 0D
01281139 |. F7FE |idiv esi
0128113B |. 8BF2 |mov esi, edx
0128113D |. 3BF1 |cmp esi, ecx
0128113F |. 74 2A |je short 0128116B ; 插入失败
01281141 |. 833CB5 6C3328>|cmp dword ptr [esi*4+ht], 0
01281149 |.^ 75 E5 \jnz short 01281130 ; 嗯，这里还是没有空位，继续找吧
0128114B |> 6A 01 push 1 ; /size = 1
0128114D |. FF15 B4202801 call dword ptr [<&MSVCR90.malloc>] ; \malloc
01281153 |. 83C4 04 add esp, 4
01281156 |. 8904B5 6C3328>mov dword ptr [esi*4+ht], eax
0128115D |. 8BCF mov ecx, edi
0128115F |. 8BD0 mov edx, eax
01281161 |> 8A01 /mov al, byte ptr [ecx] ; 简单地将字符拷贝到新分配的内存中
01281163 |. 8802 |mov byte ptr [edx], al
01281165 |. 41 |inc ecx
01281166 |. 42 |inc edx
01281167 |. 84C0 |test al, al
01281169 |.^ 75 F6 \jnz short 01281161
0128116B |> 5E pop esi
0128116C \. C3 retn
这是search函数
00241000 /$ 8A07 mov al, byte ptr [edi] ; 此处的edi就是那个存字符的缓冲区也是要搜索的
00241002 |. 33C9 xor ecx, ecx
00241004 |. 8BD7 mov edx, edi
00241006 |. 84C0 test al, al
00241008 |. 74 12 je short 0024101C ; 如果字符串结尾
0024100A |. 8D9B 00000000 lea ebx, dword ptr [ebx] ; 此处是printf函数地址，可以在主函数找到。。顺便感叹下这寄存器窜的
00241010 |> 0FBEC0 /movsx eax, al ; 下面这个循环稍微看下就知道是字符串数值相加啦
00241013 |. 42 |inc edx
00241014 |. 03C8 |add ecx, eax
00241016 |. 8A02 |mov al, byte ptr [edx]
00241018 |. 84C0 |test al, al
0024101A |.^ 75 F4 \jnz short 00241010
0024101C |> B8 4FECC44E mov eax, 4EC4EC4F ;依然是个取余操作，详情参考前面注释
00241021 |. F7E9 imul ecx
00241023 |. C1FA 02 sar edx, 2
00241026 |. 8BC2 mov eax, edx
00241028 |. C1E8 1F shr eax, 1F
0024102B |. 03C2 add eax, edx
0024102D |. 6BC0 0D imul eax, eax, 0D
00241030 |. 2BC8 sub ecx, eax ; 这里得到了余数
00241032 |. 53 push ebx
00241033 |. 56 push esi
00241034 |. 8BF1 mov esi, ecx
00241036 |. 8D04B5 000000>lea eax, dword ptr [esi*4]
0024103D |. 83B8 6C332400>cmp dword ptr [eax+24336C], 0 ; 看全局数组某个位置是否为空
00241044 |. 8BD6 mov edx, esi
00241046 |. 74 58 je short 002410A0 ; 下面循环貌似有点复杂，先看发现空位后的操作
00241048 |. EB 06 jmp short 00241050
0024104A | 8D9B 00000000 lea ebx, dword ptr [ebx]
00241050 |> 8B80 6C332400 /mov eax, dword ptr [eax+24336C] ; 搜索到的字符串地址
00241056 |. 8BCF |mov ecx, edi ; 字符串寄存器又换成ecx了
00241058 |> 8A18 |/mov bl, byte ptr [eax]
0024105A |. 3A19 ||cmp bl, byte ptr [ecx]
0024105C |. 75 1A ||jnz short 00241078
0024105E |. 84DB ||test bl, bl
00241060 |. 74 12 ||je short 00241074 ; 发现相等并等于0字符后跳出并检查是否为所求字符串
00241062 |. 8A58 01 ||mov bl, byte ptr [eax+1]
00241065 |. 3A59 01 ||cmp bl, byte ptr [ecx+1]
00241068 |. 75 0E ||jnz short 00241078
0024106A |. 83C0 02 ||add eax, 2
0024106D |. 83C1 02 ||add ecx, 2
00241070 |. 84DB ||test bl, bl
00241072 |.^ 75 E4 |\jnz short 00241058
00241074 |> 33C0 |xor eax, eax
00241076 |. EB 05 |jmp short 0024107D
00241078 |> 1BC0 |sbb eax, eax
0024107A |. 83D8 FF |sbb eax, -1
0024107D |> 85C0 |test eax, eax
0024107F |. 74 1F |je short 002410A0
00241081 |. 8D42 01 |lea eax, dword ptr [edx+1] ; 下标后移一个位置后取余
00241084 |. 99 |cdq
00241085 |. B9 0D000000 |mov ecx, 0D
0024108A |. F7F9 |idiv ecx
0024108C |. 3BD6 |cmp edx, esi
0024108E |. 74 49 |je short 002410D9 ; 意思就是取余后仍然等于原来那个位置，那么查找失败返回0
00241090 |. 8D0495 000000>|lea eax, dword ptr [edx*4]
00241097 |. 83B8 6C332400>|cmp dword ptr [eax+24336C], 0
0024109E |.^ 75 B0 \jnz short 00241050 ; 发现下一个非空位，继续搜索
002410A0 |> 8B3495 6C3324>mov esi, dword ptr [edx*4+24336C]
002410A7 |. 8BCF mov ecx, edi ; 之后ecx指向搜索的字符串
002410A9 |. 8BC6 mov eax, esi
002410AB |. EB 03 jmp short 002410B0 ; 跳转之后的基本都是strcmp函数的代码，看来这个库函数是汇编实现还是内联的。。效率确实没得说
002410AD | 8D49 00 lea ecx, dword ptr [ecx]
002410B0 |> 8A10 /mov dl, byte ptr [eax]
002410B2 |. 3A11 |cmp dl, byte ptr [ecx]
002410B4 |. 75 28 |jnz short 002410DE
002410B6 |. 84D2 |test dl, dl
002410B8 |. 74 12 |je short 002410CC
002410BA |. 8A50 01 |mov dl, byte ptr [eax+1]
002410BD |. 3A51 01 |cmp dl, byte ptr [ecx+1]
002410C0 |. 75 1C |jnz short 002410DE
002410C2 |. 83C0 02 |add eax, 2
002410C5 |. 83C1 02 |add ecx, 2
002410C8 |. 84D2 |test dl, dl
002410CA |.^ 75 E4 \jnz short 002410B0
002410CC |> 33C0 xor eax, eax ; 看着这么多指令，其实就是返回找到的那个元素的地址
002410CE |. F7D8 neg eax
002410D0 |. 1BC0 sbb eax, eax
002410D2 |. F7D0 not eax
002410D4 |. 23C6 and eax, esi
002410D6 |. 5E pop esi
002410D7 |. 5B pop ebx
002410D8 |. C3 retn
002410D9 |> 5E pop esi
002410DA |. 33C0 xor eax, eax
002410DC |. 5B pop ebx
002410DD |. C3 retn
002410DE |> 1BC0 sbb eax, eax ; 返回0
002410E0 |. 83D8 FF sbb eax, -1
002410E3 |. F7D8 neg eax
002410E5 |. 1BC0 sbb eax, eax ; 这里算出eax==FFFFFFFF
002410E7 |. F7D0 not eax
002410E9 |. 23C6 and eax, esi
002410EB |. 5E pop esi
002410EC |. 5B pop ebx
002410ED \. C3 retn
总结：
发现编译器还是满厉害的，2个小函数直接被优化掉放入调用函数的代码里了，这还只是无优化版本，库也估计也有很多是反汇编实现而且是内联的
有一点比较麻烦的就是C函数的调用约定导致堆栈平衡有点混乱，说不定就突然冒出个add esp,xx不明所以，还导致变量的使用由于堆栈原因比较难看，尤其是寄存器还跨函数使用。。。还得到前面找这个寄存器存的是什么数据，还好windows调用约定是函数自己平衡堆栈，规律性来说应该是要强些的
后来试了下优化选项为o2，结果发现和无优化选项的代码一模一样，表示有点失望。。
PS:学着别人自己做的逆向笔记。。。质量不怎么样，发现自己真不会写笔记，光看自己的解说就。。。不过还是都传上来好了