Декодирование Хаффмана для видео


Я пытаюсь реализовать быстрый декодер Хаффмана для кодирования/декодирования видео. Однако, я едва способен декодировать видео 1080p50, используя дешифратор. С другой стороны, есть много кодеков в 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_;
};


2904
12
задан 29 августа 2011 в 11:08 Источник Поделиться
Комментарии
3 ответа

Ты, кажется, работаешь на один бит основа. Это очень медленно. Вы должны объединить несколько битов вместе, найдите соответствующий образец в таблице, а дальше посмотрим (если необходимо) в дереве.

Можно увидеть очертания этого решения, представленные здесь http://www.gzip.org/algorithm.txt. Конечно, погуглить на "быстрое декодирование Хаффмана" раскрывает несколько статей на эту тему, а также. Значение их может быть достойным, а также.

13
ответ дан 29 августа 2011 в 12:08 Источник Поделиться

Без профилирования, ваш next_bit выполняет деление и модуль при каждом вызове (хотя операции, скорее всего, будет объединен в один divmod).

Я бы избавилась от этой абстракции и раскатать основной цикл восемь раз (вместо четырех): один раз для каждого отдельного бита в байте на входе. Таким образом, можно полностью пропустить деление и просто взять один байт за один раз.

Но первый шаг, безусловно, должно стать улучшение алгоритмов, как предложил Тобиас.

7
ответ дан 29 августа 2011 в 12:08 Источник Поделиться

Самый быстрый способ я нашел-это простой и очень компактный код-мудрый, особенно если вы сможете сжать, используя канонические или полу-канонических кодов Хаффмана. Начните с чтения о том, как расшифровать все биты кодового слова одновременно, используя дан Хиршберг и Дебра Lelewer по "эффективного декодирования префиксных кодов" в связи АСМ, апрель 1990, том 33, номер 4 стр. 449-459.

На протяжении многих лет (десятилетий, на самом деле) я разработал дальнейшее повышение скорости основано на том, что основная 'ноль-расширение идеи стола, и я сделал много оптимизации скорости С.

Кроме того, вы сможете настроить декодер для декодирования двух последовательных кодовых слов в таблице итерации цикла. Насколько это помогает зависит от размера кэша процессора, буфера ассоциативной трансляции, скорость шины, архитектуре чипа, и многое другое.

5
ответ дан 28 декабря 2013 в 11:12 Источник Поделиться