2

私はハフマンデコーダーを実装しようとしてきましたが、最初の試みでは、デコードアルゴリズムの選択が最適ではなかったため、パフォーマンスが低下していました。

テーブルルックアップを使用してハフマンデコードを実装しようと思った。しかし、私はサブテーブルの生成に少しこだわっており、誰かが私を正しい方向に向けてくれることを望んでいました。

struct node
{
    node*               children; // 0 right, 1 left
    uint8_t             value;
    uint8_t             is_leaf;
};

struct entry
{
    uint8_t              next_table_index;
    std::vector<uint8_t> values;

    entry() : next_table_index(0){}
};

void build_tables(node* nodes, std::vector<std::array<entry, 256>>& tables, int table_index);
void unpack_tree(void* data, node* nodes);

std::vector<uint8_t, tbb::cache_aligned_allocator<uint8_t>> decode_huff(void* input)
{
    // Initial setup
    CACHE_ALIGN node                    nodes[512] = {};

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

    unpack_tree(data, nodes);

    auto huffman_data = reinterpret_cast<long*>(input) + (table_size+32)/32; 
    size_t data_size = *(huffman_data++); // Size is first 32 bits.     
    auto huffman_data2  = reinterpret_cast<char*>(huffman_data);

    // Build tables

    std::vector<std::array<entry, 256>> tables(1);
    build_tables(nodes, tables, 0);

    // Decode

    uint8_t current_table_index = 0;

    std::vector<uint8_t, tbb::cache_aligned_allocator<uint8_t>> result; 
    while(result.size() < result_size)
    {
        auto& table  = tables[current_table_index];

        uint8_t key = *(huffman_data2++);
        auto& values = table[key].values;
        result.insert(result.end(), values.begin(), values.end());

        current_table_index = table[key].next_table_index;
    }

    result.resize(result_size);

    return result;
}

void build_tables(node* nodes, std::vector<std::array<entry, 256>>& tables, int table_index)
{
    for(int n = 0; n < 256; ++n)
    {
        auto current = nodes;

        for(int i = 0; i < 8; ++i)
        {
            current = current->children + ((n >> i) & 1);       
            if(current->is_leaf)
                tables[table_index][n].values.push_back(current->value);
        }

        if(!current->is_leaf)
        {
            if(current->value == 0)
            {
                current->value = tables.size();
                tables.push_back(std::array<entry, 256>());
                build_tables(current, tables, current->value);
            }

            tables[table_index][n].next_table_index = current->value;
        }
    }   
}

void unpack_tree(void* data, node* nodes)
{   
    node* nodes_end = nodes+1;      
    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[0]);      // "nodes" is root
    while(!stack.empty())
    {
        node* ptr = stack.top();
        stack.pop();
        if(table_reader.next_bit())
        {
            ptr->is_leaf = 1;
            ptr->children = nodes[0].children;
            for(int n = n_bits; n >= 0; --n)
                ptr->value |= table_reader.next_bit() << n;
        }
        else
        {
            ptr->children = nodes_end;
            nodes_end += 2;

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

1 に答える 1

1

まず、これらすべてのベクトルを避けます。vector事前に割り当てられた単一のバッファーへのポインターを持つことができますが、これらの小さな小さなバッファーをメモリー全体に割り当て、キャッシュのフットプリントが屋根を通過するシナリオは望ましくありません。

非リーフ状態の数は256よりはるかに少ない可能性があることにも注意してください。実際、128まで低くなる可能性があります。それらに低い状態IDを割り当てることにより、状態ノードのセット全体のテーブルエントリの生成を回避できます（合計で511ノードまでの高さ）。結局のところ、入力を消費した後は、リーフノードにたどり着くことはありません。その場合、出力を生成してから、ルートに戻ります。

次に、最初に行う必要があるのは、内部ノードに対応する状態（つまり、非リーフへのポインターを持つ状態）を低い状態番号に再割り当てすることです。これを使用して、状態遷移表のメモリ消費を削減することもできます。

これらの低い状態番号を割り当てたら、可能性のある各非リーフ状態、および可能性のある各入力バイト（つまり、二重にネストされたforループ）を通過できます。ビットベースのデコードアルゴリズムの場合と同じようにツリーをトラバースし、出力バイトのセット、最終的なノードID（リーフであってはなりません！）、およびストリームの終わりに到達したかどうかを記録します。マーク。

于 2011-08-29T19:24:30.733 に答える