Кодирование длин серий — SIMD

Я предполагаю, что ваша проблема связана с RLE в кодировании блочных коэффициентов переменного тока в JPEG.

Вариант RLE, используемый в JPEG, весьма специфичен. Каждый блок 8x8 пикселей преобразуется с помощью DCT и квантуется. Затем выход DCT (64 коэффициента) разделяется на первый коэффициент постоянного тока и 63 коэффициента переменного тока. Блок 8x8 коэффициентов переменного тока преобразуется в линейный массив с использованием шаблона Zig-Zag, а затем кодируется RLE.

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

ПРЕДУПРЕЖДЕНИЕ! RLE в JPEG используется только для нулевых элементов! См. F.1.2.2.1, F.1.2.2.3 и Рисунок F.2 стандарта ISO/IEC 10918-1 : 1993.

Некоторые реализации:

Существует libjpeg-tubro (домашняя страница libjpeg-turbo.org), а его ответвлением было оптимизировано компанией Linaro для ARM в 2010-2011 гг.

В этом форке есть список оптимизаций:

• 10 - Оптимизация ARM NEON для кода квантования в 'forward_DCT' (целочисленные деления заменены умножениями с плавающей запятой. ... Эта оптимизированная функция теперь почти в 3 раза быстрее, чем исходный вариант C - jcdctmgr.c - Сергей Семашко 2010-11-10
• 9 - Оптимизация сборки ARM для encode_one_block (Оптимизация сборки ARM для encode_one_block. Почти в 2 раза быстрее, чем исходный вариант C.) - jchuff.c - Сергей Семашка 2010-11-10
• 8 - Оптимизированная для ARM NEON версия 'rgb_ycc_convert' - Сергей Семашко 2010-11-10
• 7 - Оптимизированная для ARM NEON версия ycc_rgb_convert - Сергей Семашко 2010-11-10
• 6 - Небольшая оптимизация ARM NEON для convsamp - Сергей Семашко 2010-11-10
• 5 - Оптимизированная для ARM NEON версия jpeg_fdct_ifast - Сергей Семашко 2010-11-10
• 4 - Оптимизированная для ARM NEON версия jpeg_idct_ifast - Сергей Семашко 2010-11-10
• 3 - Оптимизированная для ARM NEON версия jpeg_idct_4x4 - Сергей Семашко 2010-11-10

Редакция 9 была ARM-оптимизация файла jchuff.c для функции encode_one_block, которая кодирует AC- и DC-компоненты блока; но это делается без использования NEON

/* Encode a single block's worth of coefficients */
LOCAL(boolean)   encode_one_block 

Фактически RLE не был оптимизирован; но обнаружение ZigZag и последнего нулевого коэффициента было реализовано в сборке ARM во вспомогательной функции find_last_nonzero_index. (Он был сгенерирован с помощью рубинового генератора.) или в linaro git. Это было запланировано для двойного выпуска Cortex-A8:

* Find last nonzero coefficient and produce output in natural order,
* instructions are scheduled to make use of ARM Cortex-A8 dual-issue
* capability

Это соответствующий код функции C:

LOCAL(int)
find_last_nonzero_index (JCOEFPTR block, JCOEFPTR out)
{
  int tmp, i, n = 0;
  for (i = 1; i < DCTSIZE2; i++) {
    if ((tmp = block[jpeg_natural_order[i]]) != 0)
      n = i;
    out[i] = tmp;
}
return n;

Здесь есть оптимизации ARM или NEON для самого RLE, но я думаю, что этот ассемблерный код помогает RLE, преобразуя его в версию с линейным доступом к памяти (encode_one_block, под ifdef __arm__):

  for (k = 2; k <= last_nonzero_index; k += 2) {
      innerloop(k);
  }

r, используемый в макросе innerloop, является счетчиком RLE.

Этот линейный RLE с ручным кодированием ZigZag (для Cortex-A8) должен быть быстрее, чем исходная версия C, даже для Cortex-A9. Спасибо Сергею Семашко!

PS: Текущая версия libjpeg-turbo не имеет оптимизации рук в этом RLE: encode_one_block, строка 454 jchuff.c, rev929 - внутренний цикл был немного переписан как kloop, но RLE по-прежнему выполняется нелинейно; зигзаг не отделяется от него.

Некоторые мысли о NEON

NEON имеет набор из 32 регистров, каждый шириной 64 бита (D0..D31; согласно Anderson @ ELC 2011, стр. 5) и теоретически может использоваться для хранения 64 16-битных коэффициентов и реализации ZigZag+RLE. Все еще ищу реализации...

В стандартах MPEG есть аналогичный зигзаг + RLE, и есть некоторые попытки его реализации SIMD для x86 и arm. Существует сообщение в блоге x264dev; Зигзаг 8 x 8 rel="nofollow noreferrer">x264_zigzag_scan_8x8_frame был реализован для x86 с SSSE3. Но для ARM есть только 4x4 НЕОНОВЫЙ зигзаг в формате x264.

PS: Только для меня и всех, кто не знает внутренностей Jpeg. Краткое и понятное введение в кодирование JPEG содержится в Cardiff CM0340. слайды лекции.

PPS (обновлено 18 февраля 2013 г., 13:30): Для оптимизации RLE-кодирования мы можем выполнить предварительный поиск нулей в середине коэффициентов AC, а затем работать с этими предварительно рассчитанными данными. Мы даже можем сохранить его как полубайты или как биты в некоторых регистрах NEON.

ОБНОВЛЕНИЕ от 18 февраля: автор исправления говорит, что комментарий к коммиту 9 неточен. Было двукратное улучшение, когда этот код сравнивался с jpeg6b, а не с libjpeg-turbo. Он говорит, что unroll by 63 (как в libjpeg-tubro) имеет почти такую ​​же скорость, как и это asm-решение (на некоторых тестах чуть лучше, на других нет).