[lua source code] luaS_hash

2019-01-09 本文已影响26人 ffl

上一节对global_State做了子模块划分，回顾一下global_State整理后的代码：

typedef struct global_State {
  // Version
  const lua_Number *version;      /* pointer to version number */

  // Hash
  unsigned int seed;              /* randomized seed for hashes */

  // Global Registry
  TValue l_registry;

  // Global String table
  stringtable strt;               /* hash table for strings */
  Mbuffer buff;                   /* temporary buffer for string concatenation */

  // Global Meta table
  TString *tmname[TM_N];          /* array with tag-method names */
  struct Table *mt[LUA_NUMTAGS];  /* metatables for basic types */

  // Global Thread list
  struct lua_State *mainthread;
  struct lua_State *twups;        /* list of threads with open upvalues */
  
  // Memory Allocator
  lua_Alloc frealloc;             /* function to reallocate memory */
  void *ud;                       /* auxiliary data to 'frealloc' */

  // GC Info
  GCInfo *gcinfo;

  // Error Recover
  lua_CFunction panic;            /* to be called in unprotected errors */
}

加深一下印象，也就是说global_State内部包含了下面这些重要部分：

Version：pointer to version number
Hash：randomized seed for hashes
Global Registry
Global String table
Global Meta table
Global Thread list
Memory Allocator
GC Info
Error Recover

其中，Version指向了版本指针，通常我们发布程序版本号都是外置的，Lua把版本号内置在全局状态里，使得可以在运行时动态判断自己的版本号。

而，Hash部分的seed则是用在散列表里面计算哈希时的种子，在Lua的代码里可以找到这段代码：

//lstring.c
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
  unsigned int h = seed ^ cast_uint(l);
  size_t step = (l >> LUAI_HASHLIMIT) + 1;
  for (; l >= step; l -= step)
    h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  return h;
}

第1眼看上去luaS_hash的代码没什么道理可言，其实一步步展开还是能理解的。首先，哈希函数有两类：

加密用的哈希函数，例如SHA-256, SHA-512, MD5, RIPEMD-160等
非加密用的哈希函数

luaS_hash即属于非加密用的哈希函数，在散列表里的主要作用是：

把输入字符串随机映射到散列表的索引范围[0, len-1]内
哈希应该在[0,len-1]内尽量符合均匀分布(Unifrom)，也就是合法的输入被映射到[0,len-1]中任何一个地址的概率是相等的，这就使得输入经过哈希后可以得到一个“随机的地址”，以减少碰撞。

可见，它本质上是一种伪随机数生成器，而我们知道伪随机数生成器最古典的就是线性同余方法(wiki:Linear congruential generator(LCG))，它的算法如下：

$N_{j+1}===(A*N_j+B)(mod M)$

LCG算出来的伪随机数序列在模M之后就是一个周期整数序列，周期的大小决定了碰撞的概率。LCG的周期最大是M，但大部分情况都会少于M，如果要让LCG达到最大周期，应该要符合以下Hull–Dobell Theorem条件：

B，M互质
M的所有质因子都能整除A-1
若M是4的倍数，A-1也是。
A，B， $N_0$ 都比M小
A，B都是正整数

LCG本身只是伪随机数生成器，需要满足均匀分布以减少碰撞才能在散列表里面使用。因此一个非密码学使用的哈希函数是否足够好（good hash function)，就要看它是否足够均匀分布。

先看一个常见的Hash函数的实现，叫做DJBX33A (Daniel J. Bernstein, Times 33 with Addition)：

unsigned int DJBHash(char* str, unsigned int len){
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {   
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}

在for循环里做的hash = ((hash << 5) + hash) + (*str);实际上就是hash = hash*33+str[i]，就是LCG递归算法的一个中间步骤。对比一下公式，可以看到：

$N_{j+1}$ =左边的hash
$N_j$ =右边的hash
A=33
B=str[i]，str是ASCII字符串，str[i]是8 bits，从而B是[0,256)范围内的整数。
M= $2^{32}$ （或者 $2^{64}$ ，取决于int的位数）

可以看到A，B，M满足如下的几个性质：

如果B是奇数，B和M互质，至少一半的概率
M的所有质因子是2，它可以整除A-1=32
M( $2^{32}$ 或者 $2^{64}$ )是4的倍数，A-1=32也是4的倍数
A，B， $N_0$ 都比M小
A，B是正整数（除0外）。

因此DJBX33A这个哈希函数具有很好的最大周期性，从而尽可能减少碰撞。但这只解释了一半原因，另一半原因是：

A选择33这个接近 $2^n$ 的数字，可以充分利用计算机里面用shift-and-add的方式计算乘法，即：h^33 = h^32+h = (h<<5)+h
假设h是32位，则二进制表达式为A1A2...A32，其中Ai取0或者1，那么h<<5的二进制表达式是A6A7...A3200000，那么(h<<5)+h实际上把h的bit做了一次位移后再逐位和h自己相加，得到的h^33的每一个bit就尽可能均匀地混合了原来h的每一个bit信息。
从这个角度来说，如果h<<n里面的n太大，则会每次只混合了比较少的h原来bit的信息；如果n太小，则h<<n的每个bit离h的每个bit很近，这会需要更多的迭代才能让h的32个bit混合均匀。而5和32互质，也有利于多次迭代中让h的每个bit有更大概率与输出h的每个bit都有机会做混合。
考虑B=str[i]，str是ASCII字符串，str[i]是8 bits。ASCII的前4个bit都含有0x3。则：
- 迭代一次：h1=h0<<n+h0+str[i]
- 迭代二次：h2=h1<<n+h1+str[i+1] = h1'+str[i+1]
- 可以看到如果n是8，h1'的低8位就是str[i]，那么h1'和str[i+1]的[4,8]位之间就会有相同的值做混合，不利于增加信息。n取4和2也是一样的问题。而n取5则可以让str[i]的低4位有更多机会和str[i+1]的高4位做混合。

上面这段解释来自参考资料[2]的评论，而参考资料[3]的评论下则有一段对DJB里的这几个魔数的来源做了另一番解释：直接暴力计算对比，you can you up！

/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <rse@engelschall.com>
*/

除了DJBX33A哈希函数外，下面两个著名的哈希函数也是类似的做法：

wiki:Bob Jenkin's hash function
wiki:Fowler–Noll–Vo hash function
参考资料[4]上列出了一共16种不同的非加密用的哈希函数

回到luaS_hash，与DJBX33A哈希函数是类似的，其中：

通过随机种子unsigned int h = seed ^ cast_uint(l);来防御哈希碰撞攻击
通过LUAI_HASHLIMIT控制step，通过控制step可以控制哈希计算的速度
(h<<5)与 (h>>2) 做混合

可以看到seed正是使用global_State里的seed，下面的代码验证了这点：

static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  TString *ts;
  global_State *g = G(L);
  stringtable *tb = &g->strt;
  unsigned int h = luaS_hash(str, l, g->seed);
  TString **list = &tb->hash[lmod(h, tb->size)];
  ...
}

而global_State->seed的初始化如下：

LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  ...
  g->seed = luai_makeseed(L);
  ...
}

进一步，我们看下luai_makeseed(L);的代码：

static unsigned int luai_makeseed (lua_State *L) {
  char buff[3 * sizeof(size_t)];
  unsigned int h = cast_uint(time(NULL));
  int p = 0;
  addbuff(buff, p, L);  /* heap variable */
  addbuff(buff, p, &h);  /* local variable */
  addbuff(buff, p, &lua_newstate);  /* public function */
  lua_assert(p == sizeof(buff));
  return luaS_hash(buff, p, h);
}

这就是随机种子初始化的地方，可以看到最后一句调用了luaS_hash来递归的生成种子本身，而buff,p,h就是初始值，其中h就是“生成随机种子的种子”，分拆下：

字符串buff包含了heap variable,local variable,address of lua_newstate三种信息
p就是buff的长度
而种子h使用时间函数time来初始化，实际上用户可以在 luaconf.h 中配置 luai_makeseed 定义自己的随机方法。

待续

至此，我们分解清楚了global_State->seed的作用，以及luaS_hash函数背后的原理。下一次，我们会继续探索global_State-> l_registry。对技术背后原理的好奇，是前进的最大动力。

[1] https://en.wikipedia.org/wiki/Linear_congruential_generator
[2] https://stackoverflow.com/questions/1579721/why-are-5381-and-33-so-important-in-the-djb2-algorithm
[3] https://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function/13809282#13809282
[4] https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions

[lua source code] luaS_hash

待续

猜你喜欢

热点阅读