题解 · Encoder · 解题

前面几篇文章已经把encoder彻底弄懂了，现在到了最后一步，编写decoder。

当时做题的时候写的代码在这里。是老老实实定义了二叉树结点、用指针实现的大学生标准写法。调试的痕迹也都还在，~~欢迎大家下载嘲笑~~~

哈夫曼编码大家肯定都学过，自己写一份也不难（确信）。现在写题解我想使用一个无需指针实现二叉树的方法:-)

构造哈夫曼树

在程序开头我们必须构造哈夫曼树，我直接贴代码

#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include "main.h"

uint8_t tree[256 * 2 - 1];
size_t left[256 * 2 - 1];
size_t right[256 * 2 - 1];

void init()
{
    int count = 0;
    for (int i = 0; i < 256; i++)
    {
        uint32_t row = ((uint32_t *)table)[i];
        uint32_t val = row & 0x00ffffff;
        uint32_t len = row >> 24;
        size_t ptr = 0;
        for (int j = 0; j < len; j++)
        {
            size_t &target = (val & (1 << j)) ? left[ptr] : right[ptr];
            if (!target)
                target = ++count;
            ptr = target;
        }
        tree[ptr] = i;
        assert(!left[ptr] && !right[ptr]);
    }
}

使用了一个断言，可以确认应该是叶子的结点没有子节点。断言未触发说明题目给的确实是一个无前缀编码。

Decode it!

int main()
{
    init();
    size_t ptr = 0;
    uint32_t v1, r12 = 8;
    while (1)
    {
        // read bit
        if (r12 == 8)
        {
            if ((v1 = getchar()) == EOF)
                return 0;
            r12 = 0;
        }
        int c = (v1 & (1 << r12++)) != 0;
        // decode
        size_t target = c ? left[ptr] : right[ptr];
        if (target)
            ptr = target;
        else
        {
            putchar(tree[ptr]);
            ptr = c ? left[0] : right[0];
        }
    }
}

这样就行了……让我们试试：

$ g++ -o decoder decoder.cpp
$ cat output.bin | ./decoder
nactf{4ss3mbly_huffm4n_c0d1ng_1s_fun_6JkDGFG3qTAYVe8h}
b$

？？？？ fun？ fun你个大头鬼？