Implementar el desplazamiento de bits de BigInt utilizando intrínsecos sobre una matriz.
Me gustaría implementar desplazamiento de bits sobre un bloque de memoria utilizando SIMD. He encontrado esta solución que sigue esencialmente estos pasos:
– Desplazamientos por bytes de shift / CHAR_BIT
utilizando memmove
si el desplazamiento es mayor que CHAR_BIT
.
– Desplazamientos de bits iterando sobre cada char
del bloque de memoria.
Esto es esencialmente un O(n). Sé que puedo simplemente iterar sobre tipos de datos más grandes que char
, sin embargo, estoy bastante seguro de que esto se puede hacer incluso más rápido utilizando intrínsecos.
void rshift(void *self, int other, size_t size) {
if (other < size * CHAR_BIT) {
unsigned char *s = self,
*pass = calloc(2, sizeof(unsigned char));
<pre><code> if (pass != NULL) {
int chars = other / CHAR_BIT,
bits = other % CHAR_BIT;
if (chars > 0) {
memmove(s + chars, s, size - chars);
memset(s, 0, chars);
}
if (bits > 0) {
for (size_t i = 0; i < size;
i++, pass[0] = pass[1] << (CHAR_BIT - bits)) {
pass[1] = s[i] & ((1 << bits) - 1);
s[i] = (s[i] >> bits) | pass[0];
}
}
free(pass);
}
} else memset(self, 0, size);
}
He intentado echar un vistazo a las diferentes operaciones intrínsecas, como _mm_srli_si128
, que sin embargo realiza desplazamientos por bytes, no desplazamientos por bits.
¿Existe alguna manera de implementar la función anterior utilizando instrucciones SIMD?
davy.ai
Sí, hay una forma de implementar la función anterior utilizando instrucciones SIMD. Una forma de hacer esto es utilizando las funciones intrínsecas de desplazamiento a derecha bitwise (
_mm_srli_epi*_
) disponibles en las Intel Intrinsics para SSE y AVX.Este enfoque implica cargar los datos en un registro SIMD (por ejemplo,
__m128i
o__m256i
) y realizar la operación de desplazamiento en ese registro. Dado que los registros tienen un tamaño mayor quechar
, podemos realizar la operación de desplazamiento en varios bytes (o incluso enteros) a la vez, lo que resulta en una implementación más rápida.Aquí tienes un ejemplo de implementación de la función
rshift
utilizando instrucciones SIMD:Esta implementación utiliza intrínsecas SSE2 para
__m128i
, pero también puedes utilizar intrínsecas AVX (__m256i
) para registros más anchos y aún mejor rendimiento. Ten en cuenta que la implementación SIMD puede no ser necesariamente más rápida que la implementación original, dependiendo del tamaño de los datos y la cantidad de desplazamiento. Siempre se recomienda realizar pruebas de rendimiento con diferentes implementaciones para encontrar la más óptima para tu caso de uso.</string.h></stdlib.h></immintrin.h>