2011-08-29 1 views
2

저는 허프만 디코더를 구현하려고 시도해 왔으며, 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); 
     } 
    } 
} 
+0

아마도 codereview.stackexchange.com – bdonlan

+0

에 더 적합할까요? 검토 질문으로 간주됩니까? – ronag

+0

아아, 너는 단지 일반 공연 리뷰를 요구하고 있다고 생각했다. 계속해라. – bdonlan

답변

1

먼저 모든 벡터를 피하십시오. 하나의 미리 할당 된 버퍼에 포인터를 가질 수는 있지만, vector이 작은 크기의 작은 버퍼를 메모리 전체에 할당하고 캐시 풋 프린트가 지붕을 통과하는 시나리오는 원하지 않습니다.

리프가 아닌 상태의 수는 256보다 훨씬 적을 수 있습니다. 실제로는 128보다 낮을 수 있습니다. 낮은 상태 ID를 할당하여 전체 상태 집합에 대한 테이블 항목을 생성하지 않도록 할 수 있습니다 노드 (총 511 개의 노드까지 가능). 결국, 입력을 소비 한 후에는 잎 노드로 끝나지 않을 것입니다. 우리가한다면 출력을 생성하고 루트로 되돌아갑니다.

먼저해야 할 일은 내부 노드에 해당하는 상태 (즉, 비 잎으로 포인터가있는 상태)를 낮은 상태 번호로 재 할당하는 것입니다. 또한 이것을 사용하여 상태 전이 테이블의 메모리 소비를 줄일 수 있습니다.

이 낮은 상태 번호를 할당하면 각 가능한 비 리프 상태와 가능한 각 입력 바이트 (즉, 이중 중첩 된 for 루프)를 통과 할 수 있습니다. 비트 기반 디코딩 알고리즘에서와 같이 트리를 탐색하고 출력 바이트 세트, 최종 노드 ID (리프가 아니어야 함) 및 스트림 끝 (end-of-stream) 여부를 기록하십시오 표.

+0

나는 당신이 대답 한 것으로 이해하는 것으로 나의 게시물을 업데이트했습니다. 하위 테이블을 생성하는 방법은 여전히 ​​확실하지 않습니다. – ronag

+0

@ronag, 뒤로 물러나서 꼭대기에서 내 포스트 읽기 - 내부 노드의 번호를 매기는 코드는 보이지 않습니다. 내부 노드의 번호를 다시 매길 필요가 없다면 모든 511 개의 잠재적 상태를 반복해야합니다 (루프 내에서 가능한 모든 256 바이트의 입력 바이트) – bdonlan

+0

"current-> value = tables.size(); ", 실제로 필요한 하위 테이블을 할당합니다. – ronag