저는 허프만 디코더를 구현하려고 시도해 왔으며, my initial attempt은 차선책으로 디코딩 알고리즘을 선택하기 때문에 성능이 떨어졌습니다.허프만 디코딩 서브 테이블
테이블 조회를 사용하여 허프만 디코딩을 구현하려고했습니다. 그러나, 나는 서브 테이블 생성에 조금 갇혀 누군가가 올바른 방향으로 나를 가리킬 수 있기를 바랬다.
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);
}
}
}
아마도 codereview.stackexchange.com – bdonlan
에 더 적합할까요? 검토 질문으로 간주됩니까? – ronag
아아, 너는 단지 일반 공연 리뷰를 요구하고 있다고 생각했다. 계속해라. – bdonlan