在没有乘法器的情况下，以2^8为基数加速大型模乘

Question

我目前正在将nacl库转换为risc-v。我已经有poly1305在工作了。我正试图使用risc-v核心指令集来实现这一点，所以我没有乘法器。Pol1305的算法目前使用ceil(m/16(*17*17个8位乘法，其中m是以字节为单位的消息长度(以2^8为基数的两个2^130整数乘以2^130-5的模(。所以我想用一个快速乘法算法来保持它的速度。

目前，我有一个移位和加法算法来进行乘法运算。然而，对于8位值，这需要63个周期，因为我需要避免分支(定时侧信道(，因此需要一些掩蔽，这需要更多的周期。

andi  t2, t0, 1     //t0 is the multiplier
sub   t2, zero, t2  //creating a mask
and   t3, t1, t2    //applying the mask to the multiplicand
add   a0, a0, t3    //doing the add
srli  t0, t0, 1     //shifting the multiplier
slli  t1, t1, 1     //shifting the multiplicand

这给了我每次乘法63个循环的有效结果。问题是，对于131字节的消息，程序的总执行时间为175219个周期。在这个时间中，9*17*17*63=163863个循环用于乘法。我想改进一下。

Answer 1

这里有一个经过改进的代码。这是基于Patterson和Hennessy教科书中显示的算法。

// initialization
add   a0, zero, t0  //copy multiplier to the product
slli  t1, t1, 8     //shift the multiplicand to the left half of a 16bit register
// repeat 8 times from here
andi  t2, a0, 1     //the right half of a0 is the multiplier
sub   t2, zero, t2  //creating a mask
and   t3, t1, t2    //applying the mask to the multiplicand
add   a0, a0, t3    //doing the add to the left half of the product
srli  a0, a0, 1     //shifting the product
// to here

此外，您可以通过重复上面的代码8次来应用循环展开方法，而不是通过分支/跳跃进行循环。

在算法层面上，Karatsuba算法可以减少多精度运算中的8位乘法运算次数。