Arm NEON and poly8_t and poly16_t

Question

我最近一直在研究用内部函数来优化neon技术，期间我遇到了poly8_t和poly16_t数据类型，但我不知道它们是什么。虽然我已经在网上搜索过，但至今未找到任何解释。

请问有人能够为我解释一下吗？

编辑: 谢谢大家的回答，但为什么这种方法只是一种不同的乘法等算法，它却要使用完全不同的数据类型呢？

- Goz

---

我认为这是用于多项式乘法的。搜索“polynomial multiplication neon”。 - Austin Phillips

从 https://chromium.googlesource.com/chromiumos/third_party/clang/+/release_29/test/Sema/neon-vector-types.c 的代码行中：typedef short poly16_t; - this

@self：这并没有说明它们是什么... - Goz

我会查看http://gcc.gnu.org/onlinedocs/gcc/ARM-NEON-Intrinsics.html并了解它们的实际使用方式 - 它们如何转换为汇编指令。 - auselen

另请参阅 Gouvêa 和 López 的 在 ARMv8 上实现 GCM。 - jww

Answer 1

左边 = 普通乘法，右边 = 无进位乘法

        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

对角线下降矩阵中的每个1或0表示向量“1101”和另一个向量“1001”的一个源位的部分积。

右侧应用于CRC，(ECC)错误校正码计算（Reed Solomon、BCH）和密码学（椭圆曲线、AES内部）。

说明与多项式乘法的联系，上述操作可以总结为：

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

常规的多项式乘法为：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"

在GF(2)中，每个系数都被模2简单地计算，从而得出1100101b。

GF中的数据类型看起来就像uint8_t、uint16_t或者128_t，在GF(2^8)中，数据类型包含256种独特的位模式。然而例如位模式'00010001'并没有传统的解释。（它不是十进制17，但可能是unity的123次幂，除以另一个多项式的余数。）将这个数字乘以相同的"unity"模生成多项式g(x)，导致124次幂等等。然后有限域的性质（恒等式）就有有趣的应用——例如可以（远程）轻松计算要附加到文件的32位数字以使其32位CRC匹配；或者可以使用这些属性对crc计算进行并行化，或者在有限域中实现类傅里叶变换的大数乘法（数论变换）。

- Aki Suihkonen

---

谢谢，我觉得那很有道理 :D - Goz

poly8x16_t vmulq_p8 (poly8x16_t, poly8x16_t) 给出了期望指令的形式：vmul.p8 q0, q0, q0。如果是 vmul.p8，那么它是否意味着 GF(2^8)，但您的解释是 GF(2)？也就是说，在第八位没有进位，但在中间有进位。GF(2) 乘法是 XOR/EOR。 - artless noise

GF(2)乘法是AND操作；在GF(2)及其扩展GF(2^n)中的加法是XOR。当常规二进制乘法使用ADD时，多项式乘法使用XOR来总结行（在ADD中，所有位之间存在潜在的进位）。我还没有检查文档，但我相信vmul.p8只会取无进位积的8个最低有效位；而vmull.p8将从p8*p8->p16产生完整的积。 - Aki Suihkonen

是的，我在考虑使用vmull和**GF(256)而不是GF(2^8)**。 - artless noise

Answer 2

这些类型用于无进位乘法。它对于密码算法和CRC哈希校验和非常有用。以下是一些关于应用程序的白皮书（它们探讨了x86 PCLMULQDQ指令，但相同的思想适用于ARM处理器上的无进位乘法）：

• Intel无进位乘法指令及其在计算GCM模式中的使用
• 使用PCLMULQDQ指令快速计算通用多项式的CRC校验
• Intel多项式乘法指令及其在椭圆曲线加密中的使用

- Marat Dukhan

---

ARM上的无进位乘法指令是哪个？ - auselen

在这个上下文中，ARM 必须指 Cortex A7 或 A8 处理器，其中包括 NEON 扩展。我认为它是 VMUL.P8。 - Aki Suihkonen

在ARMv7中，该指令称为“VMULL.P8”（“8位x 8位-> 16位”）。在ARMv8中，该指令称为“PMUL” / “PMULL” / “PMULL2”。具有加密扩展的ARMv8支持“64位x 64位-> 128位”无进位乘法，除了ARMv7变体。 - Marat Dukhan

Answer 3

您没有描述PMUL与PMULL之间的区别。

据我所知（可能不正确），每个单元的PMUL作用于两个8位源元素，并生成一个8位结果元素。

每个单元的PMUL生成8个部分积，每个部分积在异或之前都会移位。因此从第一个PP的LSB到最后一个PP的MSB，似乎有15位结果。但是，PMUL只能存储8位结果。

这15位结果中的最高有效7位是否被丢弃了？

- Richard

Answer 4

作为参考，这段来自Cortex-A Series Programmer’s Guide (v4)的第七章第二节：

在实现某些密码学或数据完整性算法时，多项式算术非常有用。

在{0,1}上添加两个多项式等同于按位异或。多项式加法的结果与传统加法不同。

在{0,1}上乘以两个多项式首先需要确定部分积，就像传统乘法一样，然后将部分积进行异或操作而不是传统加法。多项式乘法的结果与传统乘法不同，因为它需要对部分积进行多项式加法。

- auselen