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

Question

Учитывая номер uint32 0x12345678 (например, значение цвета RGBW), как я могу эффективно и динамически масштабировать каждый байт в нем (учитывая коэффициент масштабирования 0 <= f <= 1 (или эквивалентный целочисленный делитель)?

Я знаю, что мог бы сделать это более длинным способом (разбить число на его компоненты, возможно, с помощью структуры и цикла для управления каждым по очереди), но есть ли способ сделать это быстрее, без зацикливания? (Сопоставление статических значений может быть другим способом, но динамический метод предпочтительнее.)

Редактировать: C ++ (идеи C тоже интересны), встраиваемые, сотни или тысячи пикселей (не миллионы). Специально масштабируемые светодиоды RGBW.

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

Снова отредактируйте: это для встроенных платформ (микроконтроллеров). Хотя я полностью отвечаю на вопросы, которые помогают более широкой аудитории, я специально спросил об этом в контексте языка (ов) и алгоритмов, а не оптимизаций для конкретных платформ и наборов инструкций, поскольку оптимизации для конкретной платформы могут отличаться, если вообще присутствуют .

Answer 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 результаты не используются:

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

Answer 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,75src_2 + src_4).Это может быть полезно, если ваша встроенная система не имеет быстрого множителя (вы можете предварительно рассчитать необходимые маски из коэффициента масштабирования один раз перед обработкой всех пикселей), или если вам действительно нужен только ограниченный набор коэффициентов масштабирования (вы можете просто жестко кодироватькомбинации степеней двух дробей, которые вам нужны, в набор специализированных функций масштабирования).

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

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

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

Answer 3

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

Я провел эксперимент на 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 для одного и того же процессора регистрируется и, таким образом, избегает копирования.

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

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"  // test high byte of scale
        "brne 0f                 \n\t"  // if non zero, we are done
        "mul %A[rgbw], %A[scale] \n\t"  // multiply LSB
        "mov %A[rgbw], r1        \n\t"  // move result into place
        "mul %B[rgbw], %A[scale] \n\t"  // same with three other bytes
        "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 в любая другая архитектура.