Solución:
El número de multiplicaciones se puede reducir usando las multiplicaciones de manera más efectiva, en más bits “completos” a la vez, sin desperdiciar tantos bits en vacío. Todavía se necesitan algunos bits de relleno para garantizar que el producto de un canal no corrompa el resultado de 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. Entonces, R y B (con 8 ceros entre ellos) se pueden escalar con una multiplicación conjunta, lo mismo para G y W. El resultado son los 8 bits más altos del resultado de 16 bits por canal. Entonces 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);
los scale es un número de 0..256 que se interpreta como 0..1, en pasos de 1/256. Entonces scale = 128 corresponde a dividir a la mitad 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 el x los resultados no se utilizan:
Aquí hay un banco rápido para comparar varios métodos de escalado, de Timo en los comentarios.
Puede calcular directamente la potencia de dos fracciones de los valores de entrada con cambios 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 de 0/256 a 255/256 se puede hacer agregando opcionalmente cada uno de estos valores (por ejemplo, 0,75 es src_2 + src_4). Esto puede resultar útil si su sistema integrado no tiene un multiplicador rápido (puede precalcular las máscaras necesarias a partir 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 las combinaciones de potencias 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 utilizar para calcular previamente máscaras que aplican diferentes factores de escala a cada componente del vector.
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 pregunta 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. Esta es una MCU RISC de Harvard de 8 bits muy limitada, con un multiplicador de hardware de 8 × 8 → 16 bits.
Aquí está la implementación sencilla, usando juegos de palabras 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 restricción de memoria), esto requiere 28 ciclos de CPU para ejecutarse, 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 dará sus frutos en una MCU de 32 bits. Sin embargo, en este pequeño 8-bitter, ¡se necesitaron 176 ciclos de CPU para ejecutarse! El ensamblado generado presenta dos llamadas a una función de biblioteca que implementa una multiplicación completa de 32 bits, junto con muchos registros en movimiento y borrado.
Por último, aquí está mi versión de ensamblaje en línea:
static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)
{
asm(
"tst %B[scale] nt" // test high byte of scale
"brne 0f nt" // if non zero, we are done
"mul %A[rgbw], %A[scale] nt" // multiply LSB
"mov %A[rgbw], r1 nt" // move result into place
"mul %B[rgbw], %A[scale] nt" // same with three other bytes
"mov %B[rgbw], r1 nt" // ...
"mul %C[rgbw], %A[scale] nt"
"mov %C[rgbw], r1 nt"
"mul %D[rgbw], %A[scale] nt"
"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 de juegos de palabras
- 14 ciclos para la versión de montaje
Mi conclusión de este experimento es que estás viendo el tipo de microoptimización donde la arquitectura realmente importa. No se puede intentar optimizar esto en el nivel C sin ninguna suposición sobre la arquitectura en la que se ejecutará. Además, si le importa un factor 2 en la velocidad, vale la pena probar una implementación en ensamblador. 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.