题解 · Encoder · 算法

在前一篇文章中,已经成功地把程序的功能用C语言表示了出来。接下来为了弄清楚这段程序到底对数据做了什么,需要把自己写的C代码看懂(天哪。

在读程序的过程中,根据自己的理解,稍微调整了几条语句,比如把r12 >> 3写成r12 / 8(它们是等价的),程序本身没有改变,但是对人来说更好理解了。

#include <stdint.h>
#include <stdio.h>
#include "main.h" // unsigned char table[1040] = {.....}

int main()
{
    uint64_t v2 = 0, v1, r12 = 0;
    uint32_t *table_u32 = (uint32_t *)table;

    while ((v1 = getchar()) != EOF)
    {
        v2 |= table_u32[v1] << r12;
        r12 += table_u32[v1] >> 24;
        if (r12 >= 8)
        {
            fwrite(&v2, 1, r12 / 8, stdout);
            v2 >>= r12 / 8 * 8;
            v2 &= 0xFF;
            r12 &= 0b111L;
        }
    }
    if ((uint32_t)r12 != 0)
        fwrite(&v2, 1, 1, stdout);
}

格物致知。 ——王阳明

然后就开始格这段代码,盯着看了一会之后就看懂了(嗯)。

数据格式

要读懂程序,那首先必须弄懂的就是这长度为1024的数据的格式,要了解这一点,我们必须看懂程序是如何使用这段数据的。

unsigned char table[1040] =
{   // 很有意思的是这里有两列数全都是为0的,观察规律非常重要。
	0xca, 0x37, 0x00, 0x0e, 0x4a, 0x3f, 0x00, 0x0e, 
	0xca, 0x17, 0x00, 0x0e, 0x0a, 0x01, 0x00, 0x0d, 
	0x4a, 0x1f, 0x00, 0x0e, 0x8a, 0x05, 0x00, 0x0e, 
	0x8a, 0x24, 0x00, 0x0e, 0xca, 0x31, 0x00, 0x0e, 
	0x0a, 0x1d, 0x00, 0x0d, 0x0a, 0x09, 0x00, 0x0d, 
	0x39, 0x00, 0x00, 0x06, 0xca, 0x30, 0x00, 0x0e, 
	0x4a, 0x20, 0x00, 0x0e, 0xca, 0x0a, 0x00, 0x0e, 
	0x8a, 0x04, 0x00, 0x0e, 0x4a, 0x17, 0x00, 0x0e, 

那么我们就可以大胆地猜测table是以4个字节为一组的,而且最后一个字节肯定和前三个不!一!样!,汇编代码也印证了这一点(地址总是乘以4,而且把第四位单独取出来了嘛!)

movzbq 0x3(%rbx,%rax,4),%rdx
mov    (%rbx,%rax,4),%rax

那么1024个字节,每四个为1组,一共256组,一个字节也是刚好有256种可能。很明显就是把读入的每个字节都映射到表中每一组。差不多是这个意思:

uint32_t row = ((uint32_t*)table)[v1];
uint32_t row_1 = row & 0x00FFFFFF;
uint16_t row_2 = row >> 24;

那么这被单独拿出来的最后一个字节具体有什么含义呢?比如拿出第一组来:

0xca, 0x37, 0x00 | 0x0e
row_1 = 0b0011011111001010;
row_2 = 13;

可以发现最后这个字节表示的其实是本组数据的长度(单位为bit)!理解了这一点,整个数据段的格式就很明确了。

观察算法

进一步地思考这个算法发现,r12的值会在读入数据时被增加(r12 += row2),当它超过8时程序会进入一个if语句进行处理。结合前面row_2是长度的猜想,这段代码的意思就是“r12记录读入数据的长度,当凑够1个字节之后输出”,听起来就特别有道理对不对。

仔细想想数据的处理过程,先是读入一个字节(8bit),根据table转换为不等长的bit流,每凑够8bit再调用write输出。循环结束还有一个if,用来在输入数据结束后输出凑不齐8bit的数据。

graph TB
    ReadByte[8 bit] -- 根据table映射 --> SomeBits[<8 bit]
    SomeBits -- 凑够8bit --> EeightBits[8 bit]

然后关于不等长编码的知识开始在脑子里被唤醒——

这难道是个哈夫曼编码……

逆运算

这只能是个哈夫曼编码,就算不是哈夫曼编码,也必须是个无前缀编码,否则这不等长编码没办法解码呀~

那么编写decoder的思路也就很明确了,按照Huffman Coding的思路来就好。先根据encoder里给的数据段里的数据还原出一棵哈夫曼树,然后把output.bin用这棵树解码试试就行了。

关于解码器的代码请见下一篇文章~