【分享帖】使用查表优化指令解析
用查表法优化并解耦解析程序
Tips: 阅读前请自动 #include <stdint.h>
Tips2: 本文写自某老灯，希望能为 RM 的发展做出一点微薄的贡献，让大家不要再为一些底层的琐事困扰。
Tips3: 本人水平有限，能力不强，仅作为抛砖引玉，提出一种可能的方案，大佬轻喷。
一、背景
查表在很多场景中都能遇到。例如上位机控制下位机时，下位机可能需要根据不同的指令码解析信息；又或者是通讯过程中根据信息的地址做出不同的判断。此时我们肯定需要查表。这里的查表可以是遍历某个命令列表，找出对应的做法；也可以是通过各种 if else 或 switch 组合成一种“广义的表”。然而这些做法有个问题：效率不高、且代码耦合严重。
何谓效率不高？无论是遍历列表，或是条件判断，本质上都是：带着我的某个特征值，从已有列表中从头走到尾，一个个比对是否有契合值。那么最坏的情况就是：我要带着我的值一直找到队尾，才能够找到对应值，也就是时间复杂度为列表长度，即常说的 O(n)。
何为代码耦合严重？遍历列表还算好，可以建立一个数组，其中存储的是待比较值+函数指针，查到某个对应值立刻跳转到解析函数里；if else switch 就麻烦了，每次新增一些比较值都要重新修改原来判断逻辑中的代码，不可谓不麻烦。
二、提出
如何查表才能加快速度？我们很容易就能想到“哈哈表”。例如我现在需要响应指令码“0x0B”，怎么才能够快呢？我们可以考虑创建一个如下格式的数组：
// 指定 LUT 长度
#define APP_LUT_MAXIMUM_LENGTH 114514
// 新建函数指针，用于放到结构体里
typedef int8_t (*AppLut_pRespondMethod_t)(uint8_t* pData, uint16_t size)
// 创建 LUT 元素（LUT，Look-Up-Table，即查找表）
typedef struct
{ uint8_t cmdId; AppLut_pRespondMethod_t pRespondMethod;
} AppLut_lutElement_t;
// 创建某个 LUT
AppLut_lutElement_t blablaLut[APP_LUT_MAXIMUM_LENGTH];
这样，当我们每解析到某个指令码时，我们就可以像下面这样使用
// 假设这是串口数据解包结果的结构体，用来提取指令码、数据等
typedef struct
{
uint8_t cmdIdField;
uint8_t* pDataField;
uint16_t dataFieldSize;
} depacked;
// 下面是示例通讯的 weak 中断函数，以串口为例吧
void HAL_UARTEx_RxEventCallback(UART_HandleTypeDef *huart, uint16_t Size)
{
// 假设这里可以通过某种解析函数，从原有的接收缓存中取出对应指令码和数据的区段
depacked = ExampleDepack(huart, Size);
// 查表解析
blablaLut[depacked.cmdIdField].pRespondMethod(depacked.pDataField, depacked.dataFieldSize);
return; // 退出
}
```
可以看到，我们的解析直接根据解包后的指令码，立刻调用了对应的函数。时间复杂度？直接查出来了还谈什么复杂度（好吧认真点，其实是 O(1)）。结果非常的 Amazing 啊，我们通过一个数组列表，直接让解析速度起飞了！当我们需要匹配的指令码越复杂，这个表能够为我们节省的时间就越可观！
三、改进与优化
很显然，为了维护这么一个“哈哈表”，我们需要占用一片内存空间（也就是开了一个数组），从而换取时间上的速度，也就是常说的“空间换时间”。你或许已经蠢蠢欲动了，那么代价呢？
最大的问题就是：如果我需要解析的指令码是 uint16_t 格式，而我的指令码好巧不巧，正好有个 0x1233，那我这个表不得大到离谱啊？而且如果我这个表又偏偏只需要处理 0x0000 和 0x1233 这俩指令，这不是搞笑吗？
没错，这种表的问题就是占用空间过于离谱，因而就要想办法进行改进和优化。因而引入“哈希表”
哈希表的总体思想和上面是类似的，但查表和制表的方法改进了。
以我们刚刚举的例子为例，某个表只需要处理 0x0000 和 0x1233 这俩指令，这个表理论上最小可以有多小呢？当然就是只包含这两个指令对应的元素啦！那如果是只有两个元素的表，数组应该只有`Lut[0]` 和`Lut[1]` 两个元素，我们要怎么处理呢？
显然，如果我们能够设计某种函数，让 0x0000 输入以后，变成 0；让 0x1233 输入以后变成 1。我们假设这个函数叫 “hash”，那么这个表就可以这样用了：`Lut[hash(0x0000)]` 或`Lut[hash(0x1233)]` 。通过这么一个简单的映射函数，我们就实现了整个表的简化。例如用一个除2取余函数就可以实现了。
通过这么一个映射加查表，我们就基本实现了哈希表的功能。当然实际使用中，我们还会遇到大量的问题。例如：上面这个映射函数怎么设计？怎么确定我的哈希表能不能压缩到理论上的最小数值？如果不能怎么办？强烈建议各位搜索相关知识自行学习。本文只作为引子，不做过多原理的介绍。
为了实践，这里只需要知道
- 哈希表不可能开得很大（例如有几个指令码就开几个元素），因为内存会受不了。这时候我们会允许元素重叠，并适当降低一些时间复杂度以平衡内存的耗用。
四、实践
我们使用的哈希表基于如下开源：
https://github.com/tidwall/hashmap.c
此开源使用非常简单（可见其readme）；同时使用 MIT 许可证，非常宽松，可以放心使用。使用此开源，最主要的是需要你完成：1. 哈希表多大？
首先要确保表的大小是一个素数。当除以一个素数时，会产生最分散的余数。这能保证我们放进去的元素尽可能分散。此外开源中定义了
“#define GROW_AT 0.60 /* 60% */”，
建议据此设计合适的大小。不过开源的哈希表也可以自己扩充，所以或许无所谓？2. 哈希表制表与元素
我们放进表中的是一个元素（大概率是结构体），比如结构体如下：
typedef struct{
uint16_t cmdId;
cmdIdParsedCb_t cmdIdCb;
} AppUpParser_cmdIdLutElement_t;
需要告诉哈希表，我们用 cmdId 来确定新元素放置的位置。也就是上面提到的用映射函数放到数组（内存）中某个位置的操作。因此我们根据元素实际内容编写代码，让哈希表能够读取制表标志、比较元素是否相等等（阅读开源的实例即可，非常清晰）。例如如下代码
uint64_t GetHash(const void *pElement, uint64_t seed0, uint64_t seed1){
void* pItem = lut->pGetIndexItemAddFunc(pElement);
size_t size = lut->pGetIndexItemSizeFunc(pElement);
return hashmap_sip(pItem, size, seed0, seed1);
}
seed0 seed1 可以为空，但推荐用随机数生成，这样可以在调用 GetHash 时通过 hashmap 的 seed 来判断是哪个表触发的 gethash 函数，从而方便调用不同的获取 Index 函数
3.一个奇怪的bug
在完成了基于哈希表的lut后，我们就可以把代码解耦了，例如我自己写的解析函数parser可以实现注册解析回调：
// 初始化 parser
upParser = AppUpParser_HandleRegister(&upParserCfg);
// 注册函数 0x0001
AppUpParser_cmdIdLutElement_t parsedElement;
parsedElement.cmdId = 0x0001;
parsedElement.cmdIdCb = cmdId_0001_cb;
AppUpParser_ParsedCbRegister(upParser, &parsedElement);
// 下略
这样再配合宏定义CONCA甚至还能实现批量注册。更多玩法可以发挥想象力。
Tips: 阅读前请自动 #include <stdint.h>
Tips2: 本文写自某老灯，希望能为 RM 的发展做出一点微薄的贡献，让大家不要再为一些底层的琐事困扰。
Tips3: 本人水平有限，能力不强，仅作为抛砖引玉，提出一种可能的方案，大佬轻喷。
一、背景
查表在很多场景中都能遇到。例如上位机控制下位机时，下位机可能需要根据不同的指令码解析信息；又或者是通讯过程中根据信息的地址做出不同的判断。此时我们肯定需要查表。这里的查表可以是遍历某个命令列表，找出对应的做法；也可以是通过各种 if else 或 switch 组合成一种“广义的表”。然而这些做法有个问题：效率不高、且代码耦合严重。
何谓效率不高？无论是遍历列表，或是条件判断，本质上都是：带着我的某个特征值，从已有列表中从头走到尾，一个个比对是否有契合值。那么最坏的情况就是：我要带着我的值一直找到队尾，才能够找到对应值，也就是时间复杂度为列表长度，即常说的 O(n)。
何为代码耦合严重？遍历列表还算好，可以建立一个数组，其中存储的是待比较值+函数指针，查到某个对应值立刻跳转到解析函数里；if else switch 就麻烦了，每次新增一些比较值都要重新修改原来判断逻辑中的代码，不可谓不麻烦。
二、提出
如何查表才能加快速度？我们很容易就能想到“哈哈表”。例如我现在需要响应指令码“0x0B”，怎么才能够快呢？我们可以考虑创建一个如下格式的数组：
// 指定 LUT 长度
#define APP_LUT_MAXIMUM_LENGTH 114514
// 新建函数指针，用于放到结构体里
typedef int8_t (*AppLut_pRespondMethod_t)(uint8_t* pData, uint16_t size)
// 创建 LUT 元素（LUT，Look-Up-Table，即查找表）
typedef struct
{ uint8_t cmdId; AppLut_pRespondMethod_t pRespondMethod;
} AppLut_lutElement_t;
// 创建某个 LUT
AppLut_lutElement_t blablaLut[APP_LUT_MAXIMUM_LENGTH];
这样，当我们每解析到某个指令码时，我们就可以像下面这样使用
// 假设这是串口数据解包结果的结构体，用来提取指令码、数据等
typedef struct
{
uint8_t cmdIdField;
uint8_t* pDataField;
uint16_t dataFieldSize;
} depacked;
// 下面是示例通讯的 weak 中断函数，以串口为例吧
void HAL_UARTEx_RxEventCallback(UART_HandleTypeDef *huart, uint16_t Size)
{
// 假设这里可以通过某种解析函数，从原有的接收缓存中取出对应指令码和数据的区段
depacked = ExampleDepack(huart, Size);
// 查表解析
blablaLut[depacked.cmdIdField].pRespondMethod(depacked.pDataField, depacked.dataFieldSize);
return; // 退出
}
```
可以看到，我们的解析直接根据解包后的指令码，立刻调用了对应的函数。时间复杂度？直接查出来了还谈什么复杂度（好吧认真点，其实是 O(1)）。结果非常的 Amazing 啊，我们通过一个数组列表，直接让解析速度起飞了！当我们需要匹配的指令码越复杂，这个表能够为我们节省的时间就越可观！
三、改进与优化
很显然，为了维护这么一个“哈哈表”，我们需要占用一片内存空间（也就是开了一个数组），从而换取时间上的速度，也就是常说的“空间换时间”。你或许已经蠢蠢欲动了，那么代价呢？
最大的问题就是：如果我需要解析的指令码是 uint16_t 格式，而我的指令码好巧不巧，正好有个 0x1233，那我这个表不得大到离谱啊？而且如果我这个表又偏偏只需要处理 0x0000 和 0x1233 这俩指令，这不是搞笑吗？
没错，这种表的问题就是占用空间过于离谱，因而就要想办法进行改进和优化。因而引入“哈希表”
哈希表的总体思想和上面是类似的，但查表和制表的方法改进了。
以我们刚刚举的例子为例，某个表只需要处理 0x0000 和 0x1233 这俩指令，这个表理论上最小可以有多小呢？当然就是只包含这两个指令对应的元素啦！那如果是只有两个元素的表，数组应该只有`Lut[0]` 和`Lut[1]` 两个元素，我们要怎么处理呢？
显然，如果我们能够设计某种函数，让 0x0000 输入以后，变成 0；让 0x1233 输入以后变成 1。我们假设这个函数叫 “hash”，那么这个表就可以这样用了：`Lut[hash(0x0000)]` 或`Lut[hash(0x1233)]` 。通过这么一个简单的映射函数，我们就实现了整个表的简化。例如用一个除2取余函数就可以实现了。
通过这么一个映射加查表，我们就基本实现了哈希表的功能。当然实际使用中，我们还会遇到大量的问题。例如：上面这个映射函数怎么设计？怎么确定我的哈希表能不能压缩到理论上的最小数值？如果不能怎么办？强烈建议各位搜索相关知识自行学习。本文只作为引子，不做过多原理的介绍。
为了实践，这里只需要知道
- 哈希表不可能开得很大（例如有几个指令码就开几个元素），因为内存会受不了。这时候我们会允许元素重叠，并适当降低一些时间复杂度以平衡内存的耗用。
四、实践
我们使用的哈希表基于如下开源：
https://github.com/tidwall/hashmap.c
此开源使用非常简单（可见其readme）；同时使用 MIT 许可证，非常宽松，可以放心使用。使用此开源，最主要的是需要你完成：1. 哈希表多大？
首先要确保表的大小是一个素数。当除以一个素数时，会产生最分散的余数。这能保证我们放进去的元素尽可能分散。此外开源中定义了
“#define GROW_AT 0.60 /* 60% */”，
建议据此设计合适的大小。不过开源的哈希表也可以自己扩充，所以或许无所谓？2. 哈希表制表与元素
我们放进表中的是一个元素（大概率是结构体），比如结构体如下：
typedef struct{
uint16_t cmdId;
cmdIdParsedCb_t cmdIdCb;
} AppUpParser_cmdIdLutElement_t;
需要告诉哈希表，我们用 cmdId 来确定新元素放置的位置。也就是上面提到的用映射函数放到数组（内存）中某个位置的操作。因此我们根据元素实际内容编写代码，让哈希表能够读取制表标志、比较元素是否相等等（阅读开源的实例即可，非常清晰）。例如如下代码
uint64_t GetHash(const void *pElement, uint64_t seed0, uint64_t seed1){
void* pItem = lut->pGetIndexItemAddFunc(pElement);
size_t size = lut->pGetIndexItemSizeFunc(pElement);
return hashmap_sip(pItem, size, seed0, seed1);
}
seed0 seed1 可以为空，但推荐用随机数生成，这样可以在调用 GetHash 时通过 hashmap 的 seed 来判断是哪个表触发的 gethash 函数，从而方便调用不同的获取 Index 函数
3.一个奇怪的bug
此哈希表允许用户使用自己的malloc fre等内存管理函数。我在使用时不知道为啥<stdlb.h>里没有free，只有cfree替换，虽然不影响使用，但要是有大佬知道原因烦请不吝赐
4. 解析解耦在完成了基于哈希表的lut后，我们就可以把代码解耦了，例如我自己写的解析函数parser可以实现注册解析回调：
// 初始化 parser
upParser = AppUpParser_HandleRegister(&upParserCfg);
// 注册函数 0x0001
AppUpParser_cmdIdLutElement_t parsedElement;
parsedElement.cmdId = 0x0001;
parsedElement.cmdIdCb = cmdId_0001_cb;
AppUpParser_ParsedCbRegister(upParser, &parsedElement);
// 下略
这样再配合宏定义CONCA甚至还能实现批量注册。更多玩法可以发挥想象力。
请问这篇文章对你有用吗？
【分享帖】使用查表优化指令解析
