c - 不使用 64 位数据类型的 32 位有符号整数乘法

Question

我想在不使用 64 位数据类型的情况下进行 32 位有符号整数乘法。我的输入是 Q1.31（两者）格式。

input1 = A32 (Ah Al) - higher, lower half's of A32
input2 = B32 (Bh Bl) - higher, lower half's of B32

结果应为 Q1.31 格式，保留溢出情况。

我需要 C 代码。请同时提供格式说明。

Answer 1

有符号 Q1.31 格式是一种完全分数格式，能够表示 -1 和几乎 +1 之间的操作数。比例因子为2³¹。这意味着当每个 Q1.31 操作数存储在 32 位有符号整数中时，我们可以通过计算有符号整数的全双倍宽度积来生成 Q1.31 乘积，然后将结果右移 31 位。右移是必要的，因为产品包含比例因子两次，并且偏移充当除法，用于删除比例因子的一个实例。

我们可以通过分别计算全积的上 32 位和下 32 位

来计算两个 32 位整数的双倍宽度乘积。较低的 32 位被简单地计算为两个输入的普通乘积。要计算高 32 位，我们需要编写一个函数mul32hi() 。为了避免在中间计算中使用更广泛的类型（即使用超过 32 位的类型），我们需要将原始操作数分成两半，计算它们的部分乘积，然后对这些部分乘积进行适当的求和。

请注意，各种处理器都提供实现mul32hi()功能的硬件指令。在这种情况下，人们希望使用适当的内部函数，或者如果不存在内部函数，则使用一些内联汇编代码，而不是使用此处提供的仿真代码。

它有助于首先将问题简化为相应的无符号乘法，umul32hi()，然后通过 2 的补码表示的定义（在以下 C 代码中假设）从中导出有符号结果：

#include <stdint.h>
/* compute the upper 32 bits of the product of two unsigned 32-bit integers */
uint32_t umul32hi (uint32_t a, uint32_t b)
{
    /* split operands into halves */
    uint32_t al = (uint16_t)a;
    uint32_t ah = a >> 16;
    uint32_t bl = (uint16_t)b;
    uint32_t bh = b >> 16;
    /* compute partial products */
    uint32_t p0 = al * bl;
    uint32_t p1 = al * bh;
    uint32_t p2 = ah * bl;
    uint32_t p3 = ah * bh;
    /* sum partial products */
    uint32_t cy = ((p0 >> 16) + (uint16_t)p1 + (uint16_t)p2) >> 16;
    return p3 + (p2 >> 16) + (p1 >> 16) + cy;
}
/* compute the upper 32 bits of the product of two signed 32-bit integers */
int32_t mul32hi (int32_t a, int32_t b)
{
    return umul32hi (a, b) - ((a < 0) ? b : 0) - ((b < 0) ? a : 0);
}
/* compute the full 64-bit product of two signed 32-bit integers */
void mul32wide (int32_t a, int32_t b, int32_t *rhi, int32_t *rlo)
{
    *rlo = a * b;           /* bits <31:0> of the product a * b */
    *rhi = mul32hi (a, b);  /* bits <63:32> of the product a * b */
}
/* compute the product of two signed Q1.31 fixed-point numbers */    
int32_t mul_q_1_31 (int32_t a, int32_t b)
{
    int32_t hi, lo;
    mul32wide (a, b, &hi, &lo);
    /* Q1.31 is scaled by 2**31, trim out scale factor */
    return (int32_t)(((uint32_t)hi << 1) | ((uint32_t)lo >> 31));
}

我将"离开溢出情况"的请求解释为忽略溢出。因此，将 -1 （0x80000000） 乘以 -1 （0x80000000） 与 mul_q_1_31() 将返回 -1 （0x80000000）。

Answer 2

以下站点旨在提供 ANSI-C 库的 32 位实现，用于一般使用 Q 数进行操作： http://www.ti.com/tool/sprc542

我没有尝试过这个，也不能保证它会或不会为你做什么，但是该站点上有一个链接，您可以在其中请求源代码。