c++ - Dado un número de 32 bits, ¿cuál es una forma eficiente de escalar cada byte en un determinado factor?

bit-manipulation

Question

Dado un número uint32 0x12345678 (por ejemplo, un valor de color RGBW), ¿cómo podría escalar cada byte en forma eficiente y dinámica (dado un factor de escala 0 <= f <= 1 (o un divisor entero equivalente)?

Sé que podría hacerlo de una manera más larga (dividir el número en sus componentes, tal vez a través de una estructura, y hacer un bucle para manipular cada uno a su vez), pero ¿hay alguna manera de hacerlo más rápido, sin hacer un bucle? (La asignación de valores estáticos sería otra forma, pero es preferible un método dinámico).

Edición: C ++ (las ideas en C también son interesantes), incrustadas, cientos o miles de píxeles (no millones). Especificamente escalado de leds RGBW.

Otra cosa que surgió: esto es con gcc, por lo que se permite el uso de código (ya lo uso para cosas similares; solo quería ver si hay una forma mejor que esa).

Editar de nuevo: Esto es para plataformas integradas (microcontroladores). Si bien estoy a favor de respuestas que ayuden a una audiencia más amplia, pregunté a propósito sobre esto en el contexto de los lenguajes y algoritmos, en lugar de optimizaciones para plataformas y conjuntos de instrucciones específicos, ya que las optimizaciones específicas de la plataforma pueden variar si están presentes. .

Answer 1

El número de multiplicaciones se puede reducir utilizando las multiplicaciones de manera más efectiva, en más bits "completos" a la vez, sin perder tantos bits en el vacío. Todavía se necesitan algunos bits de relleno para garantizar que el producto para un canal no dañe el resultado para otro canal. Usando una escala de punto fijo de 8 bits, y dado que hay 8 bits por canal, la salida es de 16 bits por canal, por lo que dos de ellos encajan en el uint32_t lado a lado. Eso necesita 8 bits de relleno. Por lo tanto, R y B (con 8 ceros entre ellos) se pueden escalar con una multiplicación juntos, lo mismo para G y W. El resultado es los 8 bits más altos del resultado de 16 bits por canal. Así que algo como esto (no probado):

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

La scale es un número de 0..256 que se interpreta como 0..1, en pasos de 1/256. Entonces, la scale = 128 corresponde a la mitad de los valores del canal y así sucesivamente.

Es posible agregar un paso de redondeo, simplemente agregando un sesgo adecuado después de multiplicar.

La multiplicación hace esto, donde no se usan los resultados de x :

Aquí hay una base quickbench para comparar varios métodos de escalado, de Timo en los comentarios.

Answer 2

Puede calcular directamente la potencia de dos fracciones de los valores de entrada con desplazamientos y máscaras:

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);

(Aquí src_2 es src con cada campo dividido individualmente por 2, src_4 es src con cada campo dividido individualmente por 4 y así sucesivamente).

Cualquiera de las otras fracciones desde 0/256 hasta 255/256 se puede hacer agregando opcionalmente cada uno de estos valores (por ejemplo, 0.75 es src_2 + src_4 ). Esto podría ser útil si su sistema incorporado no tiene un multiplicador rápido (puede precalcular las máscaras necesarias del factor de escala una vez antes de procesar todos los píxeles), o si solo necesita un conjunto limitado de factores de escala (puede simplemente codificar el código). combinaciones de poder de dos fracciones que necesita en un conjunto de funciones de escala especializadas.

Por ejemplo, una función especializada de escala por 0,75 en su bucle interno simplemente haría:

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

Aunque no es aplicable a su caso de uso, este método también se puede usar para precalcular máscaras que aplican diferentes factores de escala a cada componente del vector.

Answer 3

Se ha mencionado en la discusión que la solución óptima puede ser específica de la arquitectura. Alguien también sugirió codificarlo en ensamblador. El ensamblaje tiene un costo en términos de portabilidad, pero también plantea la cuestión de si (y en qué medida) puede vencer al optimizador del compilador.

Hice un experimento en un Arduino, que se basa en un microcontrolador AVR. Este es un MCU RISC de Harvard de 8 bits muy limitado, con un multiplicador de hardware de 8 × 8 → 16 bits.

Aquí está la implementación sencilla, utilizando el punteo de tipos para multiplicar los bytes individuales:

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;
}

Compilado con gcc en -Os (típico en estos dispositivos con limitaciones de memoria), esto requiere 28 ciclos de CPU para ejecutar, es decir, 7 ciclos por byte. El compilador es lo suficientemente inteligente como para asignar rgbw y x a los mismos registros de la CPU y así evitar una copia.

Aquí está la versión basada en la respuesta de Harold:

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;
}

Esta es una optimización muy inteligente que probablemente resulte rentable en una MCU de 32 bits. Sin embargo, en este pequeño 8-amargo, ¡tomó 176 ciclos de CPU para ejecutarse! El ensamblaje generado incluye dos llamadas a una función de biblioteca que implementa una multiplicación completa de 32 bits, junto con muchos registros de movimiento y borrado.

Por último, aquí está mi versión de montaje en línea:

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;
}

Éste utiliza el hecho de que el factor de escala no puede ser mayor que 256. De hecho, cualquier factor mayor que 256 se trata como 256, lo que podría considerarse una característica. La ejecución toma 14 ciclos, y solo 3 ciclos si la escala es 256.

Resumen:

• 176 ciclos para la versión optimizada para un núcleo de 32 bits.
• 28 ciclos para la versión ingenua del punning tipográfico.
• 14 ciclos para la versión de montaje.

Mi conclusión de este experimento es que están observando aquí el tipo de microoptimización donde la arquitectura realmente importa. No puedes intentar seriamente optimizar esto en el nivel C sin ninguna suposición sobre la arquitectura en la que se ejecutará. Además, si un factor 2 en la velocidad es importante para usted, vale la pena intentar una implementación en ensamblaje. Utilice la compilación condicional para habilitar la implementación de asm en la arquitectura de destino y recurra a una implementación de C genérica en cualquier otra arquitectura.