NaN tricks in Lua

最近在读云风的《reading lua》,看到了一个浮点数 NAN trick 的应用,觉得比较有意思,结合代码和相关资料总结一下。

什么是 NaN

在浮点数中,NaN 用来表示特殊值,在一些未定义的操作中,会生成 NaN,具体的例子可以参考 wiki.

会返回 NaN 的运算有如下三种:

  • 操作数中至少有一个是 NaN 的运算

  • 未定义操作

    • 下列除法运算:0/0、∞/∞、∞/−∞、−∞/∞、−∞/−∞
    • 下列乘法运算:0 ∞、0 -∞
    • 下列加法运算:∞ + (−∞)、(−∞) + ∞
    • 下列减法运算:∞ - (−∞)、(−∞) - ∞
  • 产生复数结果的实数运算。例如:

    • 对负数进行开方运算
    • 对负数进行对数运算
    • 对比 -1 小或比 +1 大的数进行反正弦或反余弦运算

如何来表示NaN呢?

以 32 位单精度为例:指数域 = 255,尾数域非零即表示 NaN,具体可以参考wiki

这样,实际上除去指数域(8位)和符号域(1位),还有 23 位,空去 1 位标记非 0,实际上有 22 位是可以重复利用的,这就是所谓的“NaN tricks”

如果是 64 位双精度,同样可以得到 50 位的重复利用空间。

Lua 源码中的应用

在 Lua 5.1 的源码中,就利用了这个 trick,对 Lua 的数据类型进行了优化。(在32位机上,打开 LUA_NANTRICK 即可)。

假设当前环境是 32 位机器,分析一下源码(lobject.h).

先来看一下 Value 的定义:lua_CFunction 是一个函数指针,numfield 是一个宏,在没有指定 LUA_NANTRICK 的时候是一个 lua_Number,指定了 LUA_NANTRICK 时为空。

union Value {
  GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  numfield         /* numbers */
};

未开启 NAN 选项下 TValuefields 的定义:数据域,包含了一个 Value 和 type。

也就是说,在 32 位机器上,且没有开启 LUA_NANTRICK 的编译环境下,TValuefields 会占 8 + 4 = 12 个字节(Value 中的 lua_number 占 8 个字节)。

/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/
#define TValuefields    Value value_; int tt_

那么在开启了 NaN 选项下呢?

首先会将上文的 numfield 定义为空,将 lua_number 类型从 Value 联合体中去除,此时的 Value 就是 4 个字节.

再来看 TValuefields,不再是简单的 Value + type 了,而是定义了一个联合体,在 32 位机器上,这个联合体的长度就是 8 个字节。

那么,这个联合体如何来区分类型呢?这里就用到了 NaN tricks。

...

#undef numfield
#define numfield    /* no such field; numbers are the entire struct */

...

#if (LUA_IEEEENDIAN == 0)   /* { */
/* little endian */
#define TValuefields  \
    union { struct { Value v__; int tt__; } i; double d__; } u
#define NILCONSTANT {{NULL, tag2tt(LUA_TNIL)}}
/* field-access macros */
#define v_(o)       ((o)->u.i.v__)
#define d_(o)       ((o)->u.d__)
#define tt_(o)      ((o)->u.i.tt__)
#else               /* }{ */
/* big endian */
#define TValuefields  \
    union { struct { int tt__; Value v__; } i; double d__; } u
#define NILCONSTANT {{tag2tt(LUA_TNIL), {NULL}}}
/* field-access macros */
#define v_(o)       ((o)->u.i.v__)
#define d_(o)       ((o)->u.d__)
#define tt_(o)      ((o)->u.i.tt__)
#endif              /* } */
#endif          /* } */

这里是定义 TValuefields 类型的接口。

在上文我们提到,只要指数域全 1,值域非 0,即可认为是 NaN。

这里的处理是这样的:

  • 如果是 lua_number,那么必然不可能是 NaN,通过检查指数域是否全 1 就可以判断出是否为 NaN(这里用了 0x7FF7A500 这个mark),如果不为 NaN,就认为是 lua_number;
  • 如果不是 luanumber,则将 tt 的高 24 位置成 0x7FF7A5,最后 8 位表示类型;
#define NNMARK      0x7FF7A500
#define NNMASK      0x7FFFFF00
/* basic check to distinguish numbers from non-numbers */
#undef ttisnumber
#define ttisnumber(o)   ((tt_(o) & NNMASK) != NNMARK)

#define tag2tt(t)   (NNMARK | (t))

#undef rttype
#define rttype(o)   (ttisnumber(o) ? LUA_TNUMBER : tt_(o) & 0xff)