c++ - Arm NEON y poly8_t y poly16_t

intrinsics

Question

Recientemente he estado investigando la optimización de neón con intrínsecos y me he encontrado con los tipos de datos poly8_t y poly16_t. Entonces me pregunto qué diablos son.

He buscado en toda la red pero hasta ahora no he podido encontrar CUALQUIER explicación de lo que son.

¿Alguien puede explicarme?

Editar : Gracias por esas respuestas, pero ¿por qué, si se trata de una forma diferente de multiplicar, etc., tiene un tipo de datos totalmente diferente?

Answer 1

Como referencia, esto es de Cortex-A Series Programmer''s Guide (v4) capítulo 7.2.2:

La aritmética polinomial es útil cuando se implementan ciertos algoritmos de criptografía o integridad de datos.

Agregar dos polinomios sobre {0,1} es lo mismo que un O exclusivo en modo bit. Resultados polinomiales adicionales en diferentes valores a una adición convencional.

Multiplicar dos polinomios sobre {0,1} implica primero determinar los productos parciales como se hace en multiplicación convencional, luego los productos parciales son ORed exclusivos en lugar de agregarse convencionalmente. La multiplicación polinómica produce diferentes valores a la multiplicación convencional porque requiere la adición polinómica de los productos parciales.

Answer 2

Estos tipos se usan para la multiplicación sin carga. Es útil para algoritmos criptográficos y sumas de hash CRC. Aquí hay algunos libros blancos sobre aplicaciones (exploran la instrucción x86 PCLMULQDQ, pero las mismas ideas se aplican a la multiplicación sin carga en procesadores ARM):

• Instrucción de multiplicación sin uso de Intel y su uso para computar el modo GCM
• Cálculo rápido de CRC para polinomios genéricos utilizando la instrucción PCLMULQDQ
• Instrucción de multiplicación polinomial de Intel y su uso para la criptografía de curva elíptica

Answer 3

Izquierda = multiplicación regular, derecha = multiplicación sin porte

        1 1 0 1                              1 1 0 1
     *  1 0 0 1                              1 0 0 1
   ------------        -->              --------------
     (1)1 1 0 1  <-- (1) is carry            1 1 0 1
      0 0 0 0                              0 0 0 0 
    0 0 0 0                              0 0 0 0
  1 1 0 1        +                     1 1 0 1         + GF(2) or XOR
  -------------                        ---------------
  1 1 1 0 1 0 1                        1 1 0 0 1 0 1

Cada 1 o 0 en la matriz diagonalmente descendente representa el producto parcial de un bit fuente del vector ''1101'' y un bit fuente del otro vector ''1001''.

Las aplicaciones de la correcta están en CRC, cálculos de Código de corrección de errores (ECC) (Reed Solomon, BCH) y criptografía (curvas elípticas, interiores de AES).

Al ilustrar la conexión a la multiplicación polinómica , la operación anterior puede resumirse como

 1101 == x^3 + x^2 + 0 + 1;
 1001 == x^3 + 0   + 0 + 1;

La multiplicación polinomial regular es: p (x) * (x ^ 3 + 1) == p (x) * x ^ 3 + p (x) ==

 (x^3 + x^2 + 1)(x^3 + 1) == x^6+x^5+x^3 + x^3+x^2+1 
                          == 1x^6 + 1x^5 + 0x^4 + 2x^3 + 1^x2 + 0x + 1
                          == "1102101"

En GF (2), cada coeficiente se calcula simplemente en módulo 2, lo que hace 1100101b .

El tipo de datos en GF se ve igual que uint8_t, uint16_t o quizás hasta 128_t con respecto a que el tipo de datos para GF (2 ^ 8) contiene 256 patrones de bit únicos. Sin embargo, por ejemplo, el patrón de bit ''00010001'' no tiene una interpretación tradicional. (No es 17 decimal, sino quizás 123.ª potencia del módulo "unidad" algún otro polinomio). Multiplicando este número por el mismo módulo de "unidad", el polinomio generador g (x) lleva a la 124ª potencia y así sucesivamente. Entonces las propiedades (identidades) de los campos finitos solo tienen aplicaciones interesantes, de modo que uno puede (remotamente) calcular fácilmente qué número de 32 bits anexar a un archivo para hacer coincidir su CRC de 32 bits; o uno puede usar las propiedades para paralelizar el cálculo de crc, o para implementar la multiplicación de bignum con transformada tipo Fourier en campos finitos (Transformación teórica numérica).

Answer 4

No describiste PMUL vs PMULL.

Según tengo entendido (probablemente incorrectamente) cada elemento PMUL funciona en dos elementos fuente de 8 bits y genera un elemento de resultado de 8 bits.

Cada elemento PMUL genera 8 productos parciales y cada PP se desplaza respectivamente antes de XORed. Entonces desde el lsb del primer PP hasta el msb del último PP. Parece que hay 15 bits de resultado. PMUL solo puede almacenar un resultado de 8 bits.

¿Se descartan los 7 bits más importantes del resultado de 15 bits?