Amylaars driver.
*/
INLINE int
whashstr P2(char *, s, int, maxn)
{
register unsigned char oh, h;
register unsigned char *p;
register int i;
if(!s)return 0;
if (!*s)
return 0;
p = (unsigned char *) s;
oh = T[*p];
h = (*(p++) + 1) & 0xff;
for (i = maxn - 1; *p && --i >= 0; ) {
oh = T[oh ^ *p];
h = T[h ^ *(p++)];
}
return (oh << 8) + h;
}
注释中说明这两个函数基于Pearson发表的一篇 文章,这篇文章发表于Communications of the ACM archive Volume 33, Issue 6 (June 1990),文章题目是: Fast hashing of variable-length text strings。whashstr函数取自于Amylaars driver——另一个mud driver? 这个函数比第一个函数hashstr速度要快一点,因此在MudOS中 全部采用whashstr函数来实现散列表。
我并没有找到Pearson的那篇文章,对于数组T[]的产生也就无从得知,在查找资料(参 考资料3)时找到另一个产生的T的算法和一个散列函数:
-- use an array of 256 1-byte values
ub1 x[0..255];
-- fill it with the values 0 to 255 in some pseudorandom order
-- (this is derived from the alleged RC4)
{ for i in 0..255 do
{ x[i] := i;
}
}
k=7;
{ for j in 0..3 do
{ for i in 0..255 do
{ s = x[i];
k = (k + s) mod 256;
x[i] = x[k];
x[k] = s;
}
}
}
-- use the length of the message to initialize the hash
-- XXX can be 0, or some constant, or some argument
hash := (XXX+len) mod 256;
-- hash the characters in the message one byte at a time
{for i in 0..len-1 do
{hash := (hash + message[i]) mod 256; hash := x[hash];}}
将生成T的算法写成c函数:
void gen_T(int* vec)
{
int i, j, s, k = 7;
for (i = 0; i < 256; ++i)
{
vec[i] = i;
}
for (j = 0; j < 4; ++j)
{
for (i = 0; i < 256; ++i)
{
s = vec[i];
k = (k + s) % 256;
vec[i] = vec[k];
vec[k] = s;
}
}
}
于是,我们有 了另一个散列函数:
static int simulate_T[] =
{
49,118,63,252,13,155,114,130,137,40,210,62,219,246,136,221,
174,106,37,227,166,25,139,19,204,212,64,176,70,11,170,58,
146,24,123,77,184,248,108,251,43,171,12,141,126,41,95,142,
167,46,178,235,30,75,45,208,110,230,226,50,32,112,156,180,
205,68,202,203,82,7,247,217,223,71,116,76,6,31,194,183,
15,102,97,215,234,240,53,119,52,47,179,99,199,8,101,35,
65,132,154,239,148,51,216,74,93,192,42,86,165,113,89,48,
100,195,29,211,169,38,57,214,127,117,59,39,209,88,1,134,
92,163,0,66,237,22,164,200,85,9,190,129,111,172,231,14,
181,206,128,23,187,73,149,193,241,236,197,159,55,125,196,60,
161,238,245,94,87,157,122,158,115,207,17,20,145,232,107,16,
21,185,33,225,175,253,81,182,67,243,69,220,153,5,143,3,
26,213,147,222,105,188,229,191,72,177,250,135,152,121,218,44,
下一页 上一页
返回列表
返回首页
©2024 MUD游戏网_文字mud 电脑版
Powered by iwms