Убийца предсказателей переходов

lexa - 16/Дек/2010 18:54
      if (cr2_slice[0]) {
        jidx = jrow*jwide + jcol;
        i = jidx / (cr2_slice[1]*jh.high);
        if ((j = i >= cr2_slice[0]))
                 i  = cr2_slice[0];
        jidx -= i * (cr2_slice[1]*jh.high);
        row = jidx / cr2_slice[1+j];
        col = jidx % cr2_slice[1+j] + i*cr2_slice[1];
      }
Для понимания контекста:
  • Этот кусок зовется на каждый пиксел и рассчитывает, куда именно поместить распакованный из CR2 пиксель (там не так просто все).
  • jidx - номер пикселя в потоке, плавно возрастает.
  • Изображение поделено на cr2_slice[0] полос шириной cr2_slice[1] и одну полосу шириной cr2_slice[2].
  • cr2_slice[0] - небольшое число, 1-3-5
  • j - соответственно - 0 или 1.

На 15 мегапикселях - 330 миллисекунд. Разворот if правильный (чтобы было не 1+j, а честно 1 или 2) - минус 70 миллисекунд. Замена на таблицу с заранее насчитанными оффсетами - минус 200 миллисекунд. Но все равно много, перемудрили в кэноне. Главное, их "слайсы" вполне можно было бы распаковывать впараллель (как они жмутся параллельными Digic-ами), если бы в RAW были бы смещения начал. Ан нет.

Comments

pavel_burov (not verified) - 16/Дек/2010 20:57

А строчки 3 и 4 ещё оптимизировать не получится? Я так понял, что jidx делится нацело на cr2_slice[1]*jh.high и получается ноль или 1. В таком разе можно в стр. 3 попробовать i = ( jidx > cr2_slice[1]*jh.high ).

lexa - 16/Дек/2010 21:43

Нет, не нацело. Там как устроено в CR2: K слайсов шириной L и один шириной M. Высота у всех H.
Вот картинка: http://lclevy.free.fr/cr2/#lossless

Если мы номер пикселя делим на H*L, то мы получаем номер слайса. Он может быть ошибочным (если M много меньше L) и его надо округлить до K+1.

Уф.

Но все это почти неважно т.к. можно прекалькулировать оффсеты (по числу строк т.е таблица получается размером (K+1)*H (10-20 тыс). А внутри одной строчки слайса - просто декрементировать и все.
Мда. Кодом проще написать. Следите за апдейтами LibRaw.

pavel_burov (not verified) - 16/Дек/2010 22:55

А, понял. Хитро, однако.

Спасибо, полезная ссылка.

lexa - 16/Дек/2010 23:33

Ссылка полезная, а сама схема - идиотская. Лучше бы сделали тайлами с известными началами-концами бинарных данных, как в DNG.

pavel_burov (not verified) - 16/Дек/2010 23:34

Это да.

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

lexa - 17/Дек/2010 09:40

Нет, считывание идет по столбцам. А кодирование дальше - по строкам.

Т.е. выливают в какой-то буфер(ы) и их кодируют. В промежуточные буфера, которые потом склеивают.
В-принципе, если хранить дальше в нескольких буферах, а не в одном, то тоже удобно. Гы :)

Вообще же jpeg-овское кодирование, которое потоком, хоть и с маркерами рестарта, но все одно - переменной битности, это зло ужасное в век многоядерности.

_slw (not verified) - 17/Дек/2010 14:11

щито?
оно независимыми блоками 8x8 идет.
сколько у тебя картинка, 4000x5000? можешь на 300000 ядер паралелить.
ну ладно, столько перебор, но на десяток -- можно.

lexa - 17/Дек/2010 14:22

Але,

это dct можно параллелить. Который lossy jpeg.

А хаффман - который под ним лежит - нормально нельзя. И у меня - этот самый lossless jpeg, выше никаких блоков 8x8 и прочей хрени - нету.

Точнее, если там есть рестарты, то можно их искать и от них распаковывать, надеясь потом распихать по нужным местам.

_slw (not verified) - 17/Дек/2010 14:30

это dct можно параллелить.
ну. тебе мало?

А хаффман - который под ним лежит - нормально нельзя.
и? чтение с диска тоже не паралелится.
и при этом регулярно раздаются крики "сжатие данных повышает трансфер с диска". так что одно ядро на хафмане накормит стояптьсот dct.

И у меня - этот самый lossless jpeg, выше никаких блоков 8x8 и прочей хрени - нету.

а? что?
еще раз. jpeg это:
переходим в другое цветовое пространство
разбиваем картинку 8x8
dct каждого блока 8x8
отбрасываем хвосты (ну если у тебя lossless -- не отбрасываем)
кодируемся по хафману.

при декодировании все тоже самое в обратном порядке. ну только хвосты пришивать не надо.

lexa - 17/Дек/2010 14:44

Параллелить DCT мне мало, потому что в моих данных нету DCT. Нечего параллелить.

Я же говорю, SOF3. Еще бывает SOF7, SOF11 и SOF15, тоже без DCT.

Lev Serebryakov (not verified) - 21/Дек/2010 22:14

Закон парных случаев -- у меня вот на руках файл с расширением JPG и JIFI но SOF 0xc3 -- какой-то loseless. И его даже djpeg из libjpeg не берёт. Чем бы расшифровать? Википедия как-то молчит, и гугл скорее тоже.

lexa - 21/Дек/2010 22:24

c3 - это и есть SOF3, в чистом виде lossless с хаффманом.

Можно основу выдрать из RawSpeed. Собственно, у меня есть тестовый декодер, но он может ниасилить сложную структуру заголовка. Хотя с чистыми CR2-данными, выдранными из кэноновского файла - вроде справляется.

Черкни на мыло - пришлю.

and_lv (not verified) - 22/Дек/2010 01:14

Я может щас всем известное напишу или глупость какую.
К jpeg 6b существовал патч, гуглится по "pvrg jpeg ijg". Кусок из его реадме "This software implements JPEG baseline, extended-sequential, progressive
! and lossless compression processes.". Может поможет?
Плюс есть libjpeg-turbo на основе jpeg 6b c simd инструкциями, порченная и под 64 бита тоже. В свое время много юзал его японского прародителя. Давал существенный прирост в скорости против оригинального libjpeg, просто заменой shared библиотек. Но вот хаффмана там по моему не трогали.

lexa - 17/Дек/2010 14:24

Вспомнил петушиное слово: SOF3

Ivan Uskov (not verified) - 17/Дек/2010 14:20

А нельзя ли несколько видоизменить задачу? Т.е. вместо вычислений координат назначения по индексу источника вычислять индекс перебирая координаты.
Т.е. нечто вроде (псевдокод):
int col;
int row;
int iLastSliceX0 = width - cr2_slice[2];
for(row=0;row

Ivan Uskov (not verified) - 17/Дек/2010 14:21

А нельзя ли несколько видоизменить задачу? Т.е. вместо вычислений координат назначения по индексу источника вычислять индекс перебирая координаты.
Т.е. нечто вроде (псевдокод):

int col;
int row;
int iLastSliceX0 = width - cr2_slice[2];
for(row=0;row

Такая штука должа параллелится как из пушки.

Ivan Uskov (not verified) - 17/Дек/2010 14:22

Там ошибочки у меня, похоже, при расчете offset но суть думаю понятна.

Ivan Uskov - 17/Дек/2010 14:31

A.. так там хаффман. Сорри, был не прав. Вспылил. :-)

lexa - 17/Дек/2010 14:47

Хаффман там ниже.

Обсуждаемый код - это распихивание строки, уже раскодированной из Хаффмана.

Скажем, в DNG, где внизу тот же хаффман может быть, выше сделано по уму - или сплошным куском все или Tiles с известными координатами (и известными длинами, каждый тайл можно отдельно распаковывать).

А в CR2 - вот такой вот ужаснах.

Ivan Uskov - 17/Дек/2010 14:53

Т.е теоретически все-таки можно раскидать слайсы в destination order? Тогда можно и порасходовать дополнительно память в обмен на скорость (если эта скорость будет, конечно)

lexa - 17/Дек/2010 15:05

В смысле "можно"?

У CR2 - нельзя, как я понимаю. Там просто поток данных переменной битности, а индексов для хождения "в середину" (в начало слайса 3) - нету.

У DNG - при том же способе компрессии, другая организация данных.

lexa - 17/Дек/2010 15:09

Пожалуй, чуть поподробнее напишу.

Вот допустим у меня картинка 4000x3000. Слайсы, к примеру, шириной 1600,1600,800 и высотой 3000. И 4 компонента, т.е. раскодируя одну "строку" слайса я на самом деле раскодирую их 4.

Вот когда я раскодировал строку номер 752 - это я на самом деле раскодировал строки "слайсов" номер 3008-3011. В destination это прямоугольник 1600-7-3199-15 (считая с нуля).

lexa - 17/Дек/2010 14:38

Тут проблема в том, что порядок поступления пикселов - он по слайсам (слева направа, внутри слайса - сверху вниз), причем желания делать отдельный битмэп на всю картинку (Src в вашей нотации) - никакого нет, это еще мегабайт 40 (для 20Mpix), хочется ограничиться буфером на строку (а в дальнейшем - прямо in-place раскодировать, все-таки копирование жрет прилично).

А ваш код - предполагает обход в порядке пикселов destination.

Решение, которое я спер в RawSpeed заключается в том, что для каждой строки слайса мы рассчитываем смещение в destination, а дальше просто линейно идем.
Тоже не бог весть что, так как если компонентов в JPEG больше одного, то буфере будет несколько строк слайса, но достаточно эффективно, чтобы на время забыть: из 330мс стало 80. А, скажем, чтение по-байтам с пропуском маркеров - 250мс и теперь надо оптимизировать его.

Kickerua (not verified) - 19/Дек/2010 22:47

Добрый вечер.
Вопрос не по теме. :)

Насколько я себе представляю, сенсор камеры выдает одни и те же(условно) данные при одинаковых снимках, но на разном ISO. А само усиление сигнала делает АЦП, так вот вопрос, почему нельзя делать копии сигнала с усилением и без сразу же? Или повысить битность(?) АЦП, что бы он записывал с большей точностью данные, что бы потом можно было усиление делать на компьютере.

Где я не прав? :)

lexa - 19/Дек/2010 23:00

Не факт, что усилитель и АЦП - это одна микросхема.

Более разрядный АЦП - это больше данных, сам АЦП дороже и все такое. При том, что реальный диапазон используемых значений меньше, чем разрядность АЦП, в D3 вот даже есть два режима, 12 бит и 14.