用查找表修正近似值

# 用查找表修正一个近似值 来源：https://www.corsix.org/content/using-a-lookup-table-to-correct-an-approximation 我经常发现自己需要编写*（也就是说，用代码生成器生成）*将枚举值转换为字符串的函数。这样一个函数的朴素实现可能看起来像这样： ``` const char* dxgi_format_to_string(unsigned x) { switch (x) { case 0: return "UNKNOWN"; case 1: return "R32G32B32A32_TYPELESS"; case 2: return "R32G32B32A32_FLOAT"; case 3: return "R32G32B32A32_UINT"; case 4: return "R32G32B32A32_SINT"; case 5: return "R32G32B32_TYPELESS"; case 6: return "R32G32B32_FLOAT"; case 7: return "R32G32B32_UINT"; case 8: return "R32G32B32_SINT"; case 9: return "R16G16B16A16_TYPELESS"; case 10: return "R16G16B16A16_FLOAT"; case 11: return "R16G16B16A16_UNORM"; case 12: return "R16G16B16A16_UINT"; case 13: return "R16G16B16A16_SNORM"; case 14: return "R16G16B16A16_SINT"; case 15: return "R32G32_TYPELESS"; case 16: return "R32G32_FLOAT"; case 17: return "R32G32_UINT"; case 18: return "R32G32_SINT"; case 19: return "R32G8X24_TYPELESS"; case 20: return "D32_FLOAT_S8X24_UINT"; case 21: return "R32_FLOAT_X8X24_TYPELESS"; case 22: return "X32_TYPELESS_G8X24_UINT"; default: return NULL; } } ``` 用现代 gcc 在 `-O0` 或 `-O1` 下编译上面的代码，生成的汇编相当糟糕。所幸在 `-O2` 及以上优化级别，现代 gcc 能将其改写为更接近下面的形式： ``` const char* dxgi_format_to_string(unsigned x) { static const char* const cases[] = { "UNKNOWN", "R32G32B32A32_TYPELESS", "R32G32B32A32_FLOAT", "R32G32B32A32_UINT", "R32G32B32A32_SINT", "R32G32B32_TYPELESS", "R32G32B32_FLOAT", "R32G32B32_UINT", "R32G32B32_SINT", "R16G16B16A16_TYPELESS", "R16G16B16A16_FLOAT", "R16G16B16A16_UNORM", "R16G16B16A16_UINT", "R16G16B16A16_SNORM", "R16G16B16A16_SINT", "R32G32_TYPELESS", "R32G32_FLOAT", "R32G32_UINT", "R32G32_SINT", "R32G8X24_TYPELESS", "D32_FLOAT_S8X24_UINT", "R32_FLOAT_X8X24_TYPELESS", "X32_TYPELESS_G8X24_UINT", }; if (x > 22u) return NULL; return cases[x]; } ``` 这样生成的汇编代码好多了，虽然指针表占用的空间还是比我希望的要大（这还没算上每个表项还需要一条重定向记录……）。可以将所有字符串拼接为一段连续的内存，然后用一个指向该内存的偏移量表来进一步缩小体积——利用相对偏移量可以远小于指针这一点： ``` const char* dxgi_format_to_string(unsigned x) { const char* cases = /* 0*/ "UNKNOWN\0" /* 8*/ "R32G32B32A32_TYPELESS\0" /* 30*/ "R32G32B32A32_FLOAT\0" /* 49*/ "R32G32B32A32_UINT\0" /* 67*/ "R32G32B32A32_SINT\0" /* 85*/ "R32G32B32_TYPELESS\0" /*104*/ "R32G32B32_FLOAT\0" /*120*/ "R32G32B32_UINT\0" /*135*/ "R32G32B32_SINT\0" /*150*/ "R16G16B16A16_TYPELESS\0" /*172*/ "R16G16B16A16_FLOAT\0" /*191*/ "R16G16B16A16_UNORM\0" /*210*/ "R16G16B16A16_UINT\0" /*228*/ "R16G16B16A16_SNORM\0" /*247*/ "R16G16B16A16_SINT\0" /*265*/ "R32G32_TYPELESS\0" /*281*/ "R32G32_FLOAT\0" /*294*/ "R32G32_UINT\0" /*306*/ "R32G32_SINT\0" /*318*/ "R32G8X24_TYPELESS\0" /*336*/ "D32_FLOAT_S8X24_UINT\0" /*357*/ "R32_FLOAT_X8X24_TYPELESS\0" /*382*/ "X32_TYPELESS_G8X24_UINT"; static const uint16_t offsets[] = { 0, 8, 30, 49, 67, 85, 104, 120, 135, 150, 172, 191, 210, 228, 247, 265, 281, 294, 306, 318, 336, 357, 382, }; if (x > 22u) return NULL; return cases + offsets[x]; } ``` 这已经相当不错了，但 `offsets` 表还能进一步缩小。考虑函数 `x ↦ offsets[x]`：它将 `0` 映射到 `0`，将 `22` 映射到 `382`，所以一种可能的线性近似是 `x ↦ x * int(round(382.0 / 22.0))`，也就是 `x ↦ x * 17`。`x * 17` 很少*恰好等于* `offsets[x]`，但 `x * 17` 与 `offsets[x]` 之间的差值恰好始终落在 `[-9, +10]` 的范围内。因此，可以用 `x * 17` 加上一个修正值表来替代 `offsets` 表，而这个修正值表占用的空间比原来的偏移量表更小： ``` const char* dxgi_format_to_string(unsigned x) { const char* cases = /* 0*/ "UNKNOWN\0" /* 8*/ "R32G32B32A32_TYPELESS\0" /* 30*/ "R32G32B32A32_FLOAT\0" /* 49*/ "R32G32B32A32_UINT\0" /* 67*/ "R32G32B32A32_SINT\0" /* 85*/ "R32G32B32_TYPELESS\0" /*104*/ "R32G32B32_FLOAT\0" /*120*/ "R32G32B32_UINT\0" /*135*/ "R32G32B32_SINT\0" /*150*/ "R16G16B16A16_TYPELESS\0" /*172*/ "R16G16B16A16_FLOAT\0" /*191*/ "R16G16B16A16_UNORM\0" /*210*/ "R16G16B16A16_UINT\0" /*228*/ "R16G16B16A16_SNORM\0" /*247*/ "R16G16B16A16_SINT\0" /*265*/ "R32G32_TYPELESS\0" /*281*/ "R32G32_FLOAT\0" /*294*/ "R32G32_UINT\0" /*306*/ "R32G32_SINT\0" /*318*/ "R32G8X24_TYPELESS\0" /*336*/ "D32_FLOAT_S8X24_UINT\0" /*357*/ "R32_FLOAT_X8X24_TYPELESS\0" /*382*/ "X32_TYPELESS_G8X24_UINT"; static const int8_t corrections[] = { 0, -9, -4, -2, -1, 0, 2, 1, -1, -3, 2, 4, 6, 7, 9, 10, 9, 5, 0, -5, -4, 0, 8, }; if (x > 22u) return NULL; return cases + ((long)(x * 17u) + corrections[x]); } ``` 这里存在一种通用模式：一个精确函数可以通过一个快速但不精确的近似值加上一个修正值表来计算，如果这能让表比其他方案所需的更小，那么这样做就是值得的。这不是一个新颖的想法，但它仍然需要不时地被提起——即便只是为了提醒编译器开发者们，他们仍然有尚未实现的优化手段。