Учитывая 32-битное число, каков эффективный способ масштабирования каждого байта по определенному коэффициенту?

Ответ 1

Количество умножений может быть уменьшено путем более эффективного использования умножений на более "полных" битах за один раз, не тратя столько битов на пустоту. Некоторые биты заполнения все еще необходимы, чтобы гарантировать, что продукт для одного канала не повредит результат для другого канала. Используя 8-битную шкалу с фиксированной запятой, и поскольку на канал приходится 8 бит, выходной сигнал составляет 16 бит на канал, поэтому два из них помещаются в uint32_t рядом друг с другом. Это требует 8 бит отступов. Таким образом, R и B (с 8 нулями между ними) можно масштабировать с одним умножением вместе, то же самое для G и W. Результатом являются старшие 8 бит 16-битного результата на канал. Итак, как-то так (не проверено):

uint32_t RB = RGBW & 0x00FF00FF;
uint32_t GW = (RGBW >> 8) & 0x00FF00FF;
RB *= scale;
GW *= scale;
uint32_t out = ((RB >> 8) & 0x00FF00FF) | (GW & 0xFF00FF00);

scale представляет собой число от 0..256, которое интерпретируется как 0..1 с шагом 1/256. Таким образом, scale = 128 соответствует уменьшению вдвое значений канала и так далее.

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

Умножение делает это, где результаты x не используются:

Вот быстрое средство для сравнения различных методов масштабирования, от Тимо в комментариях.

Ответ 2

Вы можете напрямую рассчитать степень двойки входных значений с помощью сдвигов и масок:

unsigned long src_2 = ((src >> 1) & 0x7f7f7f7fUL) + (src & 0x01010101UL);
unsigned long src_4 = ((src >> 2) & 0x3f3f3f3fUL) + ((src >> 1) & 0x01010101UL);
unsigned long src_8 = ((src >> 3) & 0x1f1f1f1fUL) + ((src >> 2) & 0x01010101UL);
unsigned long src_16 = ((src >> 4) & 0x0f0f0f0fUL) + ((src >> 3) & 0x01010101UL);
unsigned long src_32 = ((src >> 5) & 0x07070707UL) + ((src >> 4) & 0x01010101UL);
unsigned long src_64 = ((src >> 6) & 0x03030303UL) + ((src >> 5) & 0x01010101UL);
unsigned long src_128 = ((src >> 7) & 0x01010101UL) + ((src >> 6) & 0x01010101UL);
unsigned long src_256 = ((src >> 7) & 0x01010101UL);

(Здесь src_2 - это src где каждое поле индивидуально делится на 2, src_4 - это src каждое поле индивидуально делится на 4 и т.д.).

Любые другие дроби от 0/256 до 255/256 могут быть сделаны путем необязательного добавления каждого из этих значений (например, 0,75 - это src_2 + src_4). Это может быть полезно, если ваша встроенная система не имеет быстрого множителя (вы можете предварительно рассчитать необходимые маски из коэффициента масштабирования один раз перед обработкой всех пикселей), или если вам действительно нужен только ограниченный набор коэффициентов масштабирования (вы можете просто жестко кодировать комбинации степеней двух фракций, которые вам нужны, в набор специализированных функций масштабирования).

Например, специализированная функция масштабирования на 0,75 во внутреннем цикле просто сделает:

dest = ((src >> 1) & 0x7f7f7f7fUL) + (src & 0x01010101UL) +
    ((src >> 2) & 0x3f3f3f3fUL) + ((src >> 1) & 0x01010101UL);

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

Ответ 3

Попробуй это:

uint32_t scale = (uint32_t)(f * 256.0); // assuming 0 <= f <= 1
uint64_t source = 
  ((uint64_t)(v & 0xff000000) << 24) |
  ((uint64_t)(v & 0x00ff0000) << 16) |
  ((uint64_t)(v & 0x0000ff00) <<  8) |
  ((uint64_t)(v & 0x000000ff)      );
uint64_t temp = source * scale;
uint32_t scaled = 
  ((temp >> 32) & 0xff000000) |
  ((temp >> 24) & 0x00ff0000) |
  ((temp >> 16) & 0x0000ff00) |
  ((temp >>  8) & 0x000000ff);

Это должно быть довольно близко к быстрому без использования ассемблера. Дополнительные улучшения могут быть сделаны, если вы можете упаковать шестнадцатеричные значения AABBCCDD в 00AA00BB00CC00DD и распаковать AA00BB00CC00DD00 в AABBCCDD.

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

Ответ 4

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

Я провел эксперимент на Arduino, который основан на микроконтроллере AVR. Это очень ограниченный 8-битный, Гарвардский, RISC MCU, с аппаратным умножителем 8 × 8 → 16-бит.

Вот простая реализация, использующая типизацию для умножения отдельных байтов:

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)
{
    union {
        uint32_t value;
        uint8_t bytes[4];
    } x = { .value = rgbw };
    x.bytes[0] = x.bytes[0] * scale >> 8;
    x.bytes[1] = x.bytes[1] * scale >> 8;
    x.bytes[2] = x.bytes[2] * scale >> 8;
    x.bytes[3] = x.bytes[3] * scale >> 8;
    return x.value;
}

Скомпилированный с gcc на -Os (типично для этих устройств с ограниченным объемом памяти), для его выполнения требуется 28 циклов ЦП, то есть 7 циклов на байт. Компилятор достаточно умен, чтобы выделить rgbw и x для rgbw и тех же регистров ЦП и, таким образом, избежать копирования.

Вот версия, основанная на ответе Гарольда:

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)
{
    uint32_t rb = rgbw & 0x00FF00FF;
    uint32_t gw = (rgbw >> 8) & 0x00FF00FF;
    rb *= scale;
    gw *= scale;
    uint32_t out = ((rb >> 8) & 0x00FF00FF) | (gw & 0xFF00FF00);
    return out;
}

Это очень умная оптимизация, которая может окупиться на 32-битном MCU. Однако на этом маленьком 8-битовом процессоре потребовалось 176 циклов ЦП! Сгенерированная сборка содержит два вызова библиотечной функции, которая реализует полное 32-разрядное умножение, а также множество перемещаемых и очищаемых регистров.

Наконец, вот моя встроенная версия сборки:

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)
{
    asm(
        "tst %B[scale]           \n\t"
        "brne 0f                 \n\t"
        "mul %A[rgbw], %A[scale] \n\t"
        "mov %A[rgbw], r1        \n\t"
        "mul %B[rgbw], %A[scale] \n\t"
        "mov %B[rgbw], r1        \n\t"
        "mul %C[rgbw], %A[scale] \n\t"
        "mov %C[rgbw], r1        \n\t"
        "mul %D[rgbw], %A[scale] \n\t"
        "mov %D[rgbw], r1        \n"
        "0:"
        : [rgbw] "+r" (rgbw)   // output
        : [scale] "r" (scale)  // input
        : "r0", "r1"  // clobbers
    );
    return rgbw;
}

Здесь используется тот факт, что масштабный коэффициент не может быть больше 256. Фактически любой фактор, превышающий 256, рассматривается как 256, что можно считать признаком. Выполнение занимает 14 циклов и только 3 цикла, если масштаб 256.

Резюме:

• 176 циклов для версии, оптимизированной для 32-битного ядра
• 28 циклов для наивного варианта исполнения
• 14 циклов для сборки

Мой вывод из этого эксперимента состоит в том, что вы смотрите здесь на вид микрооптимизации, где архитектура действительно имеет значение. Вы не можете серьезно пытаться оптимизировать это на уровне C без какого-либо предположения об архитектуре, на которой он будет работать. Кроме того, если для вас имеет значение коэффициент 2, стоит попробовать реализацию в сборке. Используйте условную компиляцию, чтобы включить реализацию asm в целевой архитектуре, и используйте стандартную реализацию C в любой другой архитектуре.