首页
论坛
课程
招聘
hash
雪    币: 227
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
14
回帖
46
粉丝
0

[原创]对api 名字 hash的一点理解

2008-12-24 11:26 8384

[原创]对api 名字 hash的一点理解

2008-12-24 11:26
8384
Hash windows api method
为了控制shellcode 大小,总将api的名字用一个算法求得对应的一个Dword数(32位)
2的 32次方 可以表达4 294 967 296种可能。
网络常用的一个hash算法的c语言实现如下
#include <windows.h>
#include <stdio.h>
DWORD GetHash(char *fun_name)
{
DWORD digest=0;
while(*fun_name)
{
   digest=((digest<<25)|(digest>>7));
   digest+=*fun_name;
   fun_name++;
}
return digest;
}
void main()
{
DWORD hash;
hash=GetHash("MessageBoxA");
printf("result of hash is %.8x\n",hash);
}
基本算法就是 h=h<<25 | h>>7 +*fun_name

用汇编语言实现                                                       
xor edx,edx                                ;ebx equals zero
mov esi,offset funcname                        ;get the start of api name string
1oop:
Movsz eax,byte prt[esi]                        ;get one byte from name string to eax
cmp al,ah                                               ;if we get zero then Exit
jz Exit
ror   edx ,07h                                ;this statement equals digest=((digest<<25)|(digest>>7));
add edx,eax                                ; this statement equals digest+=*fun_name;
add esi,1                                ; ask esi to point to the next byte
jmp 1oop
Exit:

一时间没有想明白ror   edx ,07h 为什么等于digest=((digest<<25)|(digest>>7))
好笨,昨天画了画明白了~
假如有这样一来一个32位二进制数
执行完digest<<25后把右边的7位移动到左边,然后右边七位补25个0
执行完digest>>7后把左边25位移动到右边,然后左边7位补0
把两个数或运算后 正好跟循环右移7位是相等的.

[看雪官方培训]《安卓高级研修班(网课)》9月班开始招生!挑战极限、工资翻倍!

最新回复 (20)
vxasm
雪    币: 2014
活跃值: 活跃值 (10)
能力值: ( LV13,RANK:250 )
在线值:
发帖
22
回帖
310
粉丝
0
vxasm 活跃值 6 2008-12-24 12:07
2
0
把这个数重新异或后 正好跟循环右移7位是相等的.

应该是

digest<<25:把最低7位变成高位。
digest>>7:右移7位是为了保留原来的最高7位。
hash
雪    币: 227
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
14
回帖
46
粉丝
0
hash 活跃值 2008-12-24 14:31
3
0
改过来了~  谢谢大牛~
cjia
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
4
回帖
9
粉丝
0
cjia 活跃值 2009-4-14 20:08
4
0
谢谢,我也在这儿有点儿困惑!
cntrump
雪    币: 1675
活跃值: 活跃值 (10)
能力值: ( LV12,RANK:670 )
在线值:
发帖
204
回帖
2065
粉丝
0
cntrump 活跃值 13 2009-4-14 20:13
5
0
tag : api hash
BlueT
雪    币: 517
活跃值: 活跃值 (11)
能力值: ( LV6,RANK:90 )
在线值:
发帖
8
回帖
883
粉丝
0
BlueT 活跃值 2 2009-4-14 20:56
6
0
如果真用汇编,何必要这么做?
xfish
雪    币: 266
活跃值: 活跃值 (11)
能力值: ( LV9,RANK:220 )
在线值:
发帖
16
回帖
115
粉丝
0
xfish 活跃值 5 2009-4-14 21:51
7
0
to 楼上:
因为高级语言没有提供rol ror这样的循环移位操作符。

所以如需
rol dest, n , 需[shl dest, n] or [shr dest, 32 - n]
海风月影
雪    币: 750
能力值: (RANK:700 )
在线值:
发帖
86
回帖
2289
粉丝
8
海风月影 活跃值 17 2009-4-15 00:23
8
0
LS怎么总是这么执着高级语言不行??
我觉得应该是你对c语言不够了解吧

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

ULONG GetHash(char *fun_name)
{
	ULONG digest = 0;
	while (*fun_name)
	{
	   digest = _lrotl (digest, 7);
	   digest += *fun_name;
	   fun_name ++;
	}
	return digest;
}

void main()
{
	ULONG hash;
	hash = GetHash("MessageBoxA");
	printf ("result of hash is %.8x\n", hash);
	getchar ();
	return ;
}


上面代码在VC6里面release /MT编译后的结果:

00401000   /$  8B5424 04           mov     edx, dword ptr [esp+4]
00401004   |.  33C0                xor     eax, eax
00401006   |.  8A0A                mov     cl, byte ptr [edx]
00401008   |.  84C9                test    cl, cl
0040100A   |.  74 10               je      short TestRol.0040101C
0040100C   |>  0FBEC9              /movsx   ecx, cl
0040100F   |.  C1C0 07             |rol     eax, 7                         ;  注意这行是编译出来的,不是内联汇编
00401012   |.  03C1                |add     eax, ecx
00401014   |.  8A4A 01             |mov     cl, byte ptr [edx+1]
00401017   |.  42                  |inc     edx
00401018   |.  84C9                |test    cl, cl
0040101A   |.^ 75 F0               \jnz     short TestRol.0040100C
0040101C   \>  C3                  retn
0040101D       90                  nop
0040101E       90                  nop
0040101F       90                  nop
00401020   /$  68 48704000         push    TestRol.00407048                ;  ASCII "MessageBoxA"
00401025   |.  E8 D6FFFFFF         call    TestRol.00401000
0040102A   |.  50                  push    eax
0040102B   |.  68 30704000         push    TestRol.00407030                ;  ASCII "result of hash is %.8x",LF
00401030   |.  E8 BD010000         call    TestRol.004011F2
00401035   |.  A1 5C704000         mov     eax, dword ptr [40705C]
0040103A   |.  83C4 0C             add     esp, 0C
0040103D   |.  48                  dec     eax
0040103E   |.  A3 5C704000         mov     dword ptr [40705C], eax
00401043   |.  78 07               js      short TestRol.0040104C
00401045   |.  FF05 58704000       inc     dword ptr [407058]              ;  
0040104B   |.  C3                  retn
0040104C   |>  68 58704000         push    TestRol.00407058
00401051   |.  E8 0A000000         call    TestRol.00401060
00401056   |.  59                  pop     ecx
00401057   \.  C3                  retn
Mxixihaha
雪    币: 309
活跃值: 活跃值 (28)
能力值: ( LV2,RANK:10 )
在线值:
发帖
64
回帖
385
粉丝
0
Mxixihaha 活跃值 2009-4-15 00:55
9
0
膜拜风月
foxabu
雪    币: 217
活跃值: 活跃值 (11)
能力值: ( LV13,RANK:530 )
在线值:
发帖
55
回帖
1239
粉丝
0
foxabu 活跃值 13 2009-4-15 02:03
10
0
我只是进来膜拜名字的。
wdsm
雪    币: 203
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
6
回帖
63
粉丝
0
wdsm 活跃值 2009-4-15 10:58
11
0
我认为海风那个代码的优化是VC6做了手脚的,当判断出是调用那个函数的时候,直接用汇编指令代替。原因有三个,如下:

1.看编译器安装目录中库文件代码中的rotl.c,我同样用VC6试验了,同样的函数无论如何优化总是不能只得到一条汇编指令。
/***
*unsigned _rotl(val, shift) - int rotate left
*
*Purpose:
*       Performs a rotate left on an unsigned integer.
*
*       [Note:  The _lrotl entry is based on the assumption
*       that sizeof(int) == sizeof(long).]
*Entry:
*       unsigned val:   value to rotate
*       int    shift:   number of bits to shift by
*
*Exit:
*       returns rotated value
*
*Exceptions:
*       None.
*
*******************************************************************************/

unsigned long __cdecl _lrotl (
        unsigned long val,
        int shift
        )
{
        return( (unsigned long) _rotl((unsigned) val, shift) );
}

unsigned __cdecl _rotl (
        unsigned val,
        int shift
        )
{
        register unsigned hibit;        /* non-zero means hi bit set */
        register unsigned num = val;    /* number to rotate */

        shift &= 0x1f;                  /* modulo 32 -- this will also make
                                           negative shifts work */

        while (shift--) {
                hibit = num & 0x80000000;  /* get high bit */
                num <<= 1;              /* shift left one bit */
                if (hibit)
                        num |= 1;       /* set lo bit if hi bit was set */
        }

        return num;
}

2.海风的代码在编译之后,查看obj文件的时候代码里面就出现了那条汇编指令。针对一般的库函数没有这种搞法的,都是需要再连接一下。

3.这个更有意思,就算在c文件中只想声明一个名叫_rotl的函数都不行,编译的时候提示
error C2169: '_rotl' : intrinsic function, cannot be defined

这里可以看出那是VC优化手段中的一种。
我凑凑热闹,不好意思,跑题了。。。
海风月影
雪    币: 750
能力值: (RANK:700 )
在线值:
发帖
86
回帖
2289
粉丝
8
海风月影 活跃值 17 2009-4-15 11:50
12
0
楼上说得太玄乎了

把我上面的代码copy到rol.c里面,然后拖进VC6,直接编译,选release,生成一下,代码就会出现rol eax,7

至于你说的rotl.c,我在VC6里面没找到这个源码,VS2005里面才有,但是VS2005也可以编译出这个指令

用VS2005编译上面那个rol.c,命令行

cl rol.c /O2

然后看代码,你会发现同样也有rol eax,7

=====================华丽的分割线=====================================

我贴出来,只是想说VC可以编译成这个样子,这个指令并不是汇编独有的
wdsm
雪    币: 203
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
6
回帖
63
粉丝
0
wdsm 活跃值 2009-4-15 11:57
13
0
我完全没有否认你的意思,我用VC6编译了你的代码,结果和你的一样,会出现那条指令的!我只是由此说明了一下这是VC的一种优化手段。呵呵,至于那个文件嘛,VC6在安装时默认是不会安装那些文件的,便于调试,我将那些文件从安装包里面拷贝进去了。安装包里面VC98\CRT下面就是的。

我贴出来是想说,VC6之所以编译成这个样子,是由于那个函数完全可以用一条汇编编译器指令指令来实现,结果编译的时候检查_lrotl()函数是否是被调用了,如果是被调用了,编译器会破例把这个函数直接用一条汇编指令实现之。
海风月影
雪    币: 750
能力值: (RANK:700 )
在线值:
发帖
86
回帖
2289
粉丝
8
海风月影 活跃值 17 2009-4-15 12:27
14
0
学         习
boywhp
雪    币: 1034
活跃值: 活跃值 (10)
能力值: ( LV12,RANK:750 )
在线值:
发帖
98
回帖
593
粉丝
1
boywhp 活跃值 12 2009-4-15 12:40
15
0
google 杂凑函数 linux字符串hash算法
将一个大集合通过杂凑函数的索引到一个ID范围,不知道理解可对
dge
雪    币: 558
活跃值: 活跃值 (10)
能力值: ( LV13,RANK:290 )
在线值:
发帖
11
回帖
251
粉丝
0
dge 活跃值 6 2009-4-15 12:41
16
0
来膜拜海风的
vire
雪    币: 101
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
0
回帖
12
粉丝
0
vire 活跃值 2009-4-15 12:42
17
0
用楼猪的代码 digest=((digest<<25)|(digest>>7));在GCC下直接就rol了。
如果C语言(编译器)这点事情都干不了的话,那嵌入式那帮哥们还怎么混。。。。。岂不是效率低下至死。。。。
是吧。
wdsm
雪    币: 203
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
6
回帖
63
粉丝
0
wdsm 活跃值 2009-4-15 12:55
18
0
海风太谦虚了!仅从C上讲,你就比我高出近一个数量级了。
书呆彭
雪    币: 2058
能力值: (RANK:250 )
在线值:
发帖
30
回帖
1861
粉丝
1
书呆彭 活跃值 6 2009-4-15 15:03
19
0
有一种函数,叫intrisics function,它是编译器(compiler)提供的,而不是库(library)提供的。

比如此例中的_rotl,再比如memcpy。比如这里有一篇文章,对memcpy进行了分析:

http://blog.codingnow.com/2005/10/vc_memcpy.html

虽然PC平台的编译器,这种函数不常见,但也是存在的,只是不同的编译器实现方式不同。

在嵌入式编译器中,intrinsics function是相当常见的。打开iar embbedded workbench的头文件,随处可见intrisics修饰的函数,最典型的就是__disable_interrupt()。
dge
雪    币: 558
活跃值: 活跃值 (10)
能力值: ( LV13,RANK:290 )
在线值:
发帖
11
回帖
251
粉丝
0
dge 活跃值 6 2009-4-16 22:59
20
0
msvcrt.dll导出了memcpy,_rotl。
书呆彭
雪    币: 2058
能力值: (RANK:250 )
在线值:
发帖
30
回帖
1861
粉丝
1
书呆彭 活跃值 6 2009-4-19 00:53
21
0
它当然导出了。

intrisic fuction由编译器决定如何生成代码,如果能够优化,它就会用经过优化的代码来实现,如果编译器无法决定是否能够进行优化,它就会生成一条对库函数的CALL指令的。
游客
登录 | 注册 方可回帖
返回