I've been trying to implement a fast huffman decoder in order to encode/decode video.

  However, I'm barely able to decode a 1080p50 video using me decoder. On the other hand there are lots of codecs in ffmpeg that entropy decode 4-8 times faster.

I have been trying to optimize and profile my code, but I don't think I can get it to run much faster.

Does anyone have any suggestion as to how one can optimize huffman decoding?

My profiler says my application is spending most time in the following code:

I've been trying to implement a fast Huffman decoder in order to encode/decode video. However, I'm barely able to decode a 1080p50 video using my decoder. On the other hand, there are lots of codecs in ffmpeg that entropy decode 4-8 times faster.

I have been trying to optimize and profile my code, but I don't think I can get it to run much faster. Does anyone have any suggestion as to how one can optimize Huffman decoding?

My profiler says my application is spending most of the time in the following code:

void decode_huff(void* input, uint8_t* dest)
{
    struct node
    {
        node*               children; // 0 right, 1 left
        uint8_t             value;
        uint8_t             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[0]);      // "nodes" is root
    while(!stack.empty())
    {
        node* ptr = stack.top();
        stack.pop();
        if(table_reader.next_bit())
        {
            ptr->step = 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]);
        }
    }       
                
    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;
        
    auto huffman_data2  = reinterpret_cast<char*>(huffman_data);
    
     for(size_t n = 0; n < data_size/8; ++n)
    { 
         current = current->children + ((*huffman_data2 >> 0) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 1) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 2) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 3) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 4) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 5) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
        current = current->children + ((*huffman_data2 >> 6) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;
        
         current = current->children + ((*huffman_data2 >> 7) & 1);                      
        *ptr    = current->value;
        ptr     = ptr + current->step;

        ++huffman_data2;
    }

    for(size_t n = 0; n < data_size % 8; ++n)
    { 
        current = current->children + ((*huffman_data2 >> n) & 1);                      
         *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));   
}

EDIT: Updated after Konrads' suggestion. Better but still slow.

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_;
};