Эффективное осуществление декодирования Райс

Question

Я сделал наивную реализацию Rice декодера (и кодер):

void rice_decode(int k) { 
    int i = 0 
    int j = 0; 
    int x = 0; 
    while(i < size-k) { 
     int q = 0; 
     while(get(i) == 0) { 
      q++; 
      i++; 
     } 
     x = q<<k; 
     i++; 
     for(j=0; j<k; j++) { 
      x += get(i+j)<<j; 
     } 
     i += k; 
     printf("%i\n", x); 
     x = 0; 
    } 
} 

с size размером входного битового множества, get(i) примитивный возвращая i -й бит BitSet, и k параметр Rice. Поскольку я занимаюсь выступлениями, я также сделал более сложную реализацию с предварительной оценкой, которая выполняется быстрее. Однако, когда я включаю флаг -O3 в gcc, наивная реализация фактически превосходит последнюю.

Мой вопрос: знаю любую существующую эффективную реализацию Rice кодера/декодера (я больше озабочен с декодированием), что тарифы лучше, чем это (те, которые я смог найти либо медленнее или сравнимы)? В качестве альтернативы, есть ли у вас какая-нибудь умная идея, которая могла бы ускорить декодирование, отличную от предвычисления?

Answer 1

Кодирование риса можно рассматривать как вариант variable-length codes. Следовательно, в прошлом я использовал методы, основанные на таблицах, для создания автоматов/состояний машин, которые быстро расшифровывали фиксированные коды хаффмана и рисовые коды. Быстрый поиск по сети для fast variable-length codes или fast huffman дает множество применимых результатов, некоторые из них основаны на таблицах.

Answer 2

Здесь есть несколько биток для учебников.

while (get(i) == 0) { q++; i++;} находит наименее значащий бит, установленный в потоке.

Это может быть заменено на -data & data, которое возвращает один бит. Это может быть преобразован в индекс «Q» с некоторой хэш + LUT (например, один модуль с участием 37. - или с помощью инструкций SSE4 с crc32, я бы поставил один можно просто сделать LUT[crc32(-data&data) & 63];

Следующая петля for(j=0; j<k; j++) x += get(i+j)<<j; Ото следует заменить x+= data & ((1<<k)-1);, как один просто получает биты от K потока и обрабатывает их как целое число без знака.

Наконец один сдвигает data>>=(q+k); и читает в достаточном количестве байтов из входного потока.