# 简介
GNU inetutils 软件包包含了一些常见的实用网络工具，例如 ping ，本文的目的是介绍和讲解 inetutils-2.5 源码包中实现的 bitmap.
bitmap 是一种数据结构，它至少应当支持以下三个操作：
- `bitmap.is_set(bit_index): bool`: 判断序号为 `bit_index` 的比特是否已经 set;
- `bitmap.set(bit_index): void`: set 序号为 `bit_index` 的比特;
- `bitmap.clear(bit_index): void`: unset 序号为 `bit_index` 的比特；
以及初始化、销毁等操作（不在本文范围内）。对于具体的实现，方法（或者函数）的名称可能不一样，但行为基本是如上所述的。
inetutils-ping 在一次连续发送 ICMP ECHOREQUEST 封包以及接收 ICMP ECHOREPLY 封包的过程中，它用一个 bitmap 实例记录并判断 ICMP ECHOREPLY 封包的序号，并通过调用这个 bitmap 的方法来判断是否收到了重复的 ICMP ECHOREPLY 封包并且记录已经收到过的 ICMP ECHOREPLY 封包的序号。
inetutils-ping 的 bitmap 实现大量应用了宏和位运算，读起来第一印象或许是比较晦涩难懂，我们接下来将提供源码展示，以及浅显的讲解。
# 源码
位于 `ping/ping_common.h` L132
```c
#define _C_BIT(p,bit) (p)->ping_cktab[(bit)>>3] /* byte in ck array */
#define _C_MASK(bit) (1 << ((bit) & 0x07))
#define _C_IND(p,bit) ((bit) % (8 * (p)->ping_cktab_size))
#define _PING_SET(p,bit) \
do \
{ \
int n = _C_IND (p,bit); \
_C_BIT (p,n) |= _C_MASK (n); \
} \
while (0)
#define _PING_CLR(p,bit) \
do \
{ \
int n = _C_IND (p,bit); \
_C_BIT (p,n) &= ~_C_MASK (n); \
} \
while (0)
#define _PING_TST(p,bit) \
(_C_BIT (p, _C_IND (p,bit)) & _C_MASK (_C_IND (p,bit)))
```
其中，`_PING_CLR` 相当于 bitmap 的 `unset`, `_PING_TST` 相当于 bitmap 的 `test`（或者 `is_set`），`_PINT_SET` 顾名思义。
进一步阅读其它源码我们可以发现，bitmap 的存储空间（一段连续的内存）应该是位于以 `(p)->ping_cktab` 为起始地址的一块连续的内存，它是一个 `char*`，这块区域的大小是 N = `(p)->ping_cktab_size` (bytes).
一个 char 变量可以存储 8 个 bit 的信息，那么，这整个 bitmap 实际上就可以存储 M = N * 8 = `(p)->ping_cktab_size` * 8 这么多个 bits 的信息，于是，`_C_IND` 所做的实际上就是把它的“输入”映射到 0 到 M-1 的这个范围。它通过取模运算（ `%` 是取余数运算符）来做到这一点。
然后你再把 bitmap 的整个存储区域看作是一个 `char[N]` 对象，每个 `char` 有 8 个 bits, 那么，`_C_BIT` 相当于对输入除以 8 ，然后根据得到的商来选择用 `char[N]` 中的哪个 `char`，相当于在一个大的 bitmap 中选出一个“子 bitmap“，也可以理解为是把输入的除去了最右边 3 个 LSB (least significant bits) 之后剩下的信息映射到用来访问 `char[N]` 的 index.
例如，假设，`_C_BIT` 的输入是 0b11010011 ，那么，它去除了 3 个 LSB （也就是 011 ）后就剩下了 11010 ，`_C_BIT` 选择 `(p)->cktab[0b11010]` 这个子 bitmap 用来进行接下来的进一步判断和操作（无论这个操作是 set 还是 test ）。
现在，我们已经知道了 `_C_BIT` 把输入的除去了 3 个 LSB 之后剩下的 bits 用来映射为子 bitmap 选择子，那么，`_C_MASK` 利用的正是 `_C_BIT` 不要的那 3 个 LSB ，并且把这 3 个 LSB 映射到一个 char 内的 bit index 。因为，0x07 的二进制表示就是 0b111 ，让 `_C_MASK` 的输入对 0b111 进行按位 AND 操作就相当于取它的 3 个 LSB ，显然这个按位 AND 运算结果的范围是 0 到 7 ，也就是说 `_C_MASK` 相当于根据输入的 3 个 LSB 来决定用在一个 char 内的 mask 是多少。
以 0b11010011 这个输入为例，它的 3 个 LSB 是 011 ，`1 << 0b11` 就是 0b1000 ，相当于一个 char 内的第 4 个 LSB 的 mask 。
# 总结
现在我们可以总结如下，对于一个大小为 M = 2^p = N * 8 (bits) 的 bitmap ，输入的 bit 2, bit 1, bit 0 被映射为单个 char 内的 mask ，bit p-1, bit p-2, ..., bit 3 组成的二进制数被映射为 char[N] 的选择子，用来从 char[N] 中选出一个 char 。
理解了 `_C_BIT`, `_C_IND` 和 `_C_MASK` 之后，`_PING_SET`，`_PING_CLR` 和 `_PING_TST` 都变得相对容易理解了。 |
|
