霍夫曼视频解码

Question

我一直试图实现一个快速哈夫曼解码器，以便编码/解码视频。然而，我几乎无法用我的解码器解码1080 p50视频。另一方面，在ffmpeg中有很多编解码器，熵解码的速度是前者的4-8倍。

我一直试图优化和分析我的代码，但我认为我不能让它运行得更快。有人对如何优化赫夫曼解码有任何建议吗？

我的分析器说，我的应用程序在以下代码中花费了大部分时间：

current = current->children + data_reader.next_bit();                           
*ptr    = current->value;
ptr     = ptr + current->step;

以下是整个代码：

void decode_huff(void* input, uint8_t* dest)
{
    struct node
    {
        node*               children; // 0 right, 1 left
        uint8_t             value;
        bool                step;
    };

    CACHE_ALIGN node                    nodes[512] = {};
    node*                               nodes_end   = nodes+1;      

    auto data = reinterpret_cast<unsigned long*>(input); 
    size_t table_size   = *(data++); // Size is first 32 bits.
    size_t num_comp     = *(data++); // Data size is second 32 bits.

    bit_reader table_reader(data);  
    unsigned char n_bits = ((table_reader.next_bit() << 2) | (table_reader.next_bit() << 1) | (table_reader.next_bit() << 0)) & 0x7; // First 3 bits are n_bits-1.

    // Unpack huffman-tree
    std::stack<node*> stack;
    stack.push(nodes);      // "nodes" is root
    while(!stack.empty())
    {
        node* ptr = stack.top();
        stack.pop();
        if(table_reader.next_bit())
        {
            ptr->step = true;
            ptr->children = nodes->children;
            for(int n = n_bits; n >= 0; --n)
                ptr->value |= table_reader.next_bit() << n;
        }
        else
        {
            ptr->children = nodes_end++;
            nodes_end++;

            stack.push(ptr->children+0);
            stack.push(ptr->children+1);
        }
    }       

    // Decode huffman-data

    // THIS IS THE SLOW PART            

    auto huffman_data   = reinterpret_cast<long*>(input) + (table_size+32)/32; 

    size_t data_size = *(huffman_data++); // Size is first 32 bits.     

    uint8_t* ptr = dest;
    auto current = nodes;

    bit_reader data_reader(huffman_data);

    size_t end = data_size - data_size % 4;
    while(data_reader.index() < end)
    { 
        current = current->children + data_reader.next_bit();                           
        *ptr    = current->value;
        ptr     = ptr + current->step;

        current = current->children + data_reader.next_bit();                           
        *ptr    = current->value;
        ptr     = ptr + current->step;

        current = current->children + data_reader.next_bit();                           
        *ptr    = current->value;
        ptr     = ptr + current->step;

        current = current->children + data_reader.next_bit();                           
        *ptr    = current->value;
        ptr     = ptr + current->step;
    }

    while(data_reader.index() < data_size)
    { 
        current = current->children + data_reader.next_bit();                           
        *ptr    = current->value;
        ptr     = ptr + current->step;
    }

    // If dest is not filled with num_comp, duplicate the last value.
    std::fill_n(ptr, num_comp - (ptr - dest), ptr == dest ? nodes->value : *(ptr-1));   
}

class bit_reader
{
public:
    typedef long block_type;
    static const size_t bits_per_block = sizeof(block_type)*8;
    static const size_t high_bit = 1 << (bits_per_block-1);

    bit_reader(void* data) 
        : data_(reinterpret_cast<block_type*>(data))
        , index_(0){}

    long next_bit()
    {
        const size_t block_index = index_ / bits_per_block;
        const size_t bit_index = index_ % bits_per_block;

        ++index_;

        return (data_[block_index] >> bit_index) & 1;
    }

    size_t index() const {return index_;}
private:    
    size_t index_;
    block_type* data_;
};

Answer 1

你似乎是在单比特的基础上工作。这太慢了。您必须将几个位组合在一起，在表中查找适当的模式，然后在树中继续(如果必要的话)。

您可以在这里看到这个解决方案的大纲，http://www.gzip.org/algorithm.txt。当然，谷歌搜索“快速赫夫曼解码”也揭示了几篇关于这一主题的论文。阅读它们也可能是值得的。

Answer 2

在不进行分析的情况下，您的next_bit在每个调用中执行一个除法和一个模数(尽管这些操作很可能合并成一个divmod)。

我将失去这个抽象，并将主循环展开八次(而不是四次)：对输入中一个字节中的每一个单独的位进行一次。这样，您就可以完全省略除法，一次只取一个字节。

但是，正如Tobias所提议的那样，第一步当然应该是算法改进。

Answer 3

我所发现的最快的方法是简单且非常紧凑的代码，尤其是如果您能够使用规范或半规范的Huffman代码进行压缩。首先阅读关于如何使用Dan Hirschberg和Debra Lelewer的“有效解码前缀码”同时解码所有码字位的文章，1990年4月，第33卷，第4卷，449至459页。

多年来(实际上是几十年)，我在基本的“零扩展”表思想的基础上，进一步提高了速度，并在C语言中进行了许多速度优化。

此外，您还可以设置解码器来对每个表循环迭代中的两个连续码字进行解码。这在多大程度上取决于处理器缓存大小、转换旁置缓冲区、总线速度、芯片结构以及许多其他因素。