zigzag算法

一个非常巧妙的数字压缩算法。
下面根据我在sylar中的实践来分析这个算法

1️⃣ 场景

在我们实践当中，需要使用32位或者64位的数字类型来保存数字，但实际使用的位数却非常少，比如班级同学数量，往往只有两位数，换算成二进制也就6、7位，剩下的全是0，其实都是无效的，我们就可以用一个很巧妙的算法实现压缩。
sylar中实战需求：在序列化数字时，压缩位数。

2️⃣ 算法

这个算法要解决的有如下问题：

1. 符号位。负数有一个最高位的1，这就限制了压缩。

解决方法：将符号位移到末尾。比如10011-> 00111就能实现压缩了。

2. 补码。负数的补码形式，比较常用的较小数字反而有很多很多1。

解决方法：对正负数区分处理，负数除了符号位之外进行取反操作。
比如11111111111001(问题1处理后)-> 00000000000111就有了很大的压缩空间。

3. 分段处理。压缩之后，在考虑到保持原子性的前提，会8位为一个单位进行发送，全部是0的单位就可以抛弃，但需要解决识别长度的问题，即每个单位之间如何组合的问题。

解决方法：比较容易考虑的方案是，提供一个前缀来标记长度，从而组合。更优的方案是在单位内前缀识别的方案。即前缀(1代表还有数据0代码无数据) + 7位有效数据来组合一个单位。

3️⃣ 代码

下面是我在sylar中的相关代码
首先是zigzag算法，完成原数字与加密数字的转换，非常精妙，这里也没有刻意压行，代码就已经非常短了。

static uint32_t EncodeZigzag32(const int32_t &v)
{
	if (v < 0)
	{
		// 对于负数：左移一位，取反，把符号位移到末尾
		// 一个样例来解释
		// -1 -> 11111111-11111111-11111111-11111111
		// -(-1) -> 00000000-00000000-00000000-0000001
		// -(-1)*2 - 1 -> 00000000-00000000-0000000-00000001
		// 符号位移到末尾，其他取反。
		return ((uint32_t)(-v)) * 2 - 1;
	}
	else
	{
		// 整数：左移一位，符号位末尾(0)
		return v * 2;
	}
}

static uint64_t EncodeZigzag64(const int64_t &v)
{
	if (v < 0)
	{
		return ((uint64_t)(-v)) * 2 - 1;
	}
	else
	{
		return v * 2;
	}
}

static int32_t DecodeZigzag32(const uint32_t &v)
{
	// 和上面相反的操作：右移归位，最高位加上符号位。
	// 上面那个函数也可以用类似的巧妙写法压缩成一行，这里是按照源码列出的。
	return (v >> 1) ^ -(v & 1);
}

static int64_t DecodeZigzag64(const uint64_t &v)
{
	return (v >> 1) ^ -(v & 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

然后是传输过程，分段传输，分段接收，然后拼接。

void ByteArray::writeUint32(uint32_t value)
    {
        uint8_t tmp[5];
        uint8_t i = 0;
		// 判断value是否仍超过七位
        while (value >= 0x80)
        {
			// 取7位有效数字和一个符号位。
            tmp[i++] = (value & 0x7F) | 0x80;
            value >>= 7;
        }
        tmp[i++] = value;
        write(tmp, i);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

uint32_t ByteArray::readUint32()
    {
        uint32_t result = 0;
        for (int i = 0; i < 32; i += 7)
        {
            uint8_t b = readFuint8();
			// 看符号位：是否是最后7位
            if (b < 0x80)
            {
				// 读7位：拼接。
                result |= ((uint32_t)b) << i;
                break;
            }
            else
            {
				// 读最后7位
                result |= (((uint32_t)(b & 0x7f)) << i);
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21