Ранее я размещал этот вопрос в Stack Overflow, но мне сказали разместить его здесь, поскольку мой код уже работает, и я просто пытаюсь его оптимизировать. Предыстория: я разрабатываю эмулятор Game Boy, и, поскольку большая часть этого уже сделана, в настоящее время я пытаюсь оптимизировать все, насколько это возможно.
Вот эта операция, которую выполняет графический процессор, когда он извлекает 16-битные графические данные (которые кодируют строку из 8 цветных пикселей, 2bpp) для помещения в очередь.
Данные расположены в виде младшего и старшего байтов, при заданной позиции мы маскируем и сдвигаем соответствующий бит в младшем и старшем байтах одинаково, чтобы сформировать 2-битное число, которое представляет оттенок или цвет. (нам также нужно сдвинуть соответствующий бит старшего байта влево на 1, чтобы сделать его MSB)
Визуально операция выглядит примерно так:
Given high = 0xff, low = 0x00
Let position = 0
high, low = 0b11111111 0b00000000
^ ^
+----------+-> n = 0b10
1 0
Let position = 1
high, low = 0b11111111 0b00000000
^ ^
+----------+-> n = 0b10
1 0
...
И фактическая операция двоичного манипулирования может выглядеть примерно так
n = ((low >> (7 - position)) & 1) | (((high >> (7 - position)) & 1) << 1)
Помимо расчета (7 - position)
один раз и сохраняя его в переменной, остается не так много места для оптимизации.
Мне было интересно, есть ли какой-нибудь встроенный компилятор, который я мог бы использовать, или есть более оптимизированный способ сделать это, я не идентифицирую. Учтите, что старший и младший байты не обязательно должны быть отдельными переменными, они могут быть просто одним 16-битным целым числом, я видел аналогичные операции в сборке / встроенных функциях, таких как blend
, или упакованные целочисленные операции.
В любом случае, заранее спасибо!
1 ответ
Рискуя закрыть этот вопрос как не по теме, я считаю эту проблему интересной и рискну найти ответ.
Я считаю, что лучший ответ здесь — это просто справочная таблица. У вас есть только 16 бит входного домена, поэтому вы можете создать LUT с 2 ^ 16 записями, каждая запись дает 8 цветов на выходе. Это будет стоить вам около 64-512 КБ памяти в зависимости от того, как вы кодируете вывод. Для эмулятора это кажется доступным даже на слабых системах. Я ожидаю, что это будет как минимум в 8 раз быстрее, чем ваш код, потому что вы получаете все цвета параллельно + вы не выполняете кучу битовой арифметики, поэтому я не удивлюсь, если это будет даже быстрее, чем это. В идеале вы запекли свою активную палитру в LUT (или предварительно запекли LUT для всех палитр), чтобы LUT предоставлял прямые кортежи RGB, которые вы можете перенести на экран без дальнейшего массажа.
Если пол-мегабайта ОЗУ — это слишком много (я не знаю, на чем вы это используете), вы можете поменять полубайты так, чтобы у вас был первый байт с первыми 4 пикселями и второй байт с последними двумя пикселей (например, превратить 0xABCD в 0xAC, 0xBD). Затем вы можете использовать LUT на 256 входов с 4-мя цветами в качестве вывода и пропускать каждый сданный байт отдельно. Предположительно, этот LUT будет стоить от 256 байт до 1 КБ, в зависимости от того, как вы кодируете вывод. Даже с swizzle это должно быть быстрее, чем ваш исходный код, поскольку вы получаете все цвета параллельно.
Swizzle относительно дешев:
Given two bytes A, B
X = (A & 0xF0) | ((B & 0xF0) >> 4)
Y = ((A & 0x0F) << 4) | (B & 0x0F)
Обратите внимание, что даже если вы все еще выполняете некоторые двоичные операции, вы получаете несколько пикселей параллельно через LUT.