在不使用乘法器的情况下，以2 ^ 8为基数加速大型模块化乘法

Question

我目前正在将nacl库转换为risc-v。我已经有poly1305工作。我正在尝试使用risc-v核心指令集来执行此操作，因此我没有乘法器。Pol1305的算法正在使用ceil（m / 16）* 17 * 17 8位乘法，其中m是消息长度（以字节为单位）（两个2 ^ 130整数乘以2 ^ 8以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算法可以减少多精度运算中的8bit乘法次数。