定点乘法中的溢出检测

Question

简而言之:如果不是有符号类型，我如何使用here描述的定点乘法来检测溢出？

长版本：

我的Q31.32 fixed point type仍然有一些溢出问题。为了更容易在纸上做例子，我用同样的算法做了一个小得多的类型，一个基于sbyte的Q3.4。我认为，如果我可以解决Q3.4类型的所有问题，同样的逻辑也应该适用于Q31.32类型。

请注意，我可以通过对16位整数执行Q3.4乘法来很容易地实现它，但我这样做就好像它不存在一样，因为对于Q31.32，我需要一个不存在的128位整数(而且BigInteger太慢了)。

我希望我的乘法通过饱和度来处理溢出，即当溢出发生时，结果是可以根据操作数的符号表示的最高或最小值。

这基本上就是该类型的表示方式：

struct Fix8 {
    sbyte m_rawValue;
    public static readonly Fix8 One = new Fix8(1 << 4);
    public static readonly Fix8 MinValue = new Fix8(sbyte.MinValue);
    public static readonly Fix8 MaxValue = new Fix8(sbyte.MaxValue);

    Fix8(sbyte value) {
        m_rawValue = value;
    }

    public static explicit operator decimal(Fix8 value) {
        return (decimal)value.m_rawValue / One.m_rawValue;
    }

    public static explicit operator Fix8(decimal value) {
        var nearestExact = Math.Round(value * 16m) * 0.0625m;
        return new Fix8((sbyte)(nearestExact * One.m_rawValue));
    }
}

这就是我目前处理乘法的方法：

    public static Fix8 operator *(Fix8 x, Fix8 y) {
        sbyte xl = x.m_rawValue;
        sbyte yl = y.m_rawValue;

        // split x and y into their highest and lowest 4 bits
        byte xlo = (byte)(xl & 0x0F);
        sbyte xhi = (sbyte)(xl >> 4);
        byte ylo = (byte)(yl & 0x0F);
        sbyte yhi = (sbyte)(yl >> 4);

        // perform cross-multiplications
        byte lolo = (byte)(xlo * ylo);
        sbyte lohi = (sbyte)((sbyte)xlo * yhi);
        sbyte hilo = (sbyte)(xhi * (sbyte)ylo);
        sbyte hihi = (sbyte)(xhi * yhi);

        // shift results as appropriate
        byte loResult = (byte)(lolo >> 4);
        sbyte midResult1 = lohi;
        sbyte midResult2 = hilo;
        sbyte hiResult = (sbyte)(hihi << 4);

        // add everything
        sbyte sum = (sbyte)((sbyte)loResult + midResult1 + midResult2 + hiResult);

        // if the top 4 bits of hihi (unused in the result) are neither all 0s or 1s,
        // then this means the result overflowed.
        sbyte topCarry = (sbyte)(hihi >> 4);
        bool opSignsEqual = ((xl ^ yl) & sbyte.MinValue) == 0;
        if (topCarry != 0 && topCarry != -1) {
            return opSignsEqual ? MaxValue : MinValue;
        }

        // if signs of operands are equal and sign of result is negative,
        // then multiplication overflowed upwards
        // the reverse is also true
        if (opSignsEqual) {
            if (sum < 0) {
                return MaxValue;
            }
        }
        else {
            if (sum > 0) {
                return MinValue;
            }
        }

        return new Fix8(sum);
    }

这样可以在类型的精度范围内提供准确的结果，并处理大多数溢出情况。但是，它不能处理这些问题，例如：

Failed -8 * 2 : expected -8 but got 0
Failed 3.5 * 5 : expected 7,9375 but got 1,5

让我们计算一下第一个函数的乘法是如何发生的。

-8 and 2 are represented as x = 0x80 and y = 0x20.
xlo = 0x80 & 0x0F = 0x00
xhi = 0x80 >> 4 = 0xf8
ylo = 0x20 & 0x0F = 0x00
yhi = 0x20 >> 4 = 0x02

lolo = xlo * ylo = 0x00
lohi = xlo * yhi = 0x00
hilo = xhi * ylo = 0x00
hihi = xhi * yhi = 0xf0

总和显然是0，因为除了hihi之外，所有项都是0，但在最终和中只使用hihi的最低4位。

我通常的溢出检测魔术在这里不起作用:结果是0，所以结果的符号是没有意义的(例如，0.0625 * -0.0625 == 0(通过向下舍入)，0是正的，但操作数的符号不同)；此外，hihi的高位是1111，即使没有溢出也经常发生。

基本上，我不知道如何检测这里发生的溢出。有没有更通用的方法？

Answer 1

这花了我很长时间，但我最终弄明白了一切。这段代码经过测试，可以在sbyte允许的范围内对x和y的每种可能的组合工作。下面是注释过的代码：

    static sbyte AddOverflowHelper(sbyte x, sbyte y, ref bool overflow) {
        var sum = (sbyte)(x + y);
        // x + y overflows if sign(x) ^ sign(y) != sign(sum)
        overflow |= ((x ^ y ^ sum) & sbyte.MinValue) != 0;
        return sum;
    }

    /// <summary>
    /// Multiplies two Fix8 numbers.
    /// Deals with overflow by saturation.
    /// </summary>
    public static Fix8 operator *(Fix8 x, Fix8 y) {
        // Using the cross-multiplication algorithm, for learning purposes.
        // It would be both trivial and much faster to use an Int16, but this technique
        // won't work for a Fix64, since there's no Int128 or equivalent (and BigInteger is too slow).

        sbyte xl = x.m_rawValue;
        sbyte yl = y.m_rawValue;

        byte xlo = (byte)(xl & 0x0F);
        sbyte xhi = (sbyte)(xl >> 4);
        byte ylo = (byte)(yl & 0x0F);
        sbyte yhi = (sbyte)(yl >> 4);

        byte lolo = (byte)(xlo * ylo);
        sbyte lohi = (sbyte)((sbyte)xlo * yhi);
        sbyte hilo = (sbyte)(xhi * (sbyte)ylo);
        sbyte hihi = (sbyte)(xhi * yhi);

        byte loResult = (byte)(lolo >> 4);
        sbyte midResult1 = lohi;
        sbyte midResult2 = hilo;
        sbyte hiResult = (sbyte)(hihi << 4);

        bool overflow = false;
        // Check for overflow at each step of the sum, if it happens overflow will be true
        sbyte sum = AddOverflowHelper((sbyte)loResult, midResult1, ref overflow);
        sum = AddOverflowHelper(sum, midResult2, ref overflow);
        sum = AddOverflowHelper(sum, hiResult, ref overflow);

        bool opSignsEqual = ((xl ^ yl) & sbyte.MinValue) == 0;

        // if signs of operands are equal and sign of result is negative,
        // then multiplication overflowed positively
        // the reverse is also true
        if (opSignsEqual) {
            if (sum < 0 || (overflow && xl > 0)) {
                return MaxValue;
            }
        }
        else {
            if (sum > 0) {
                return MinValue;
            }
            // If signs differ, both operands' magnitudes are greater than 1,
            // and the result is greater than the negative operand, then there was negative overflow.
            sbyte posOp, negOp;
            if (xl > yl) {
                posOp = xl;
                negOp = yl;
            }
            else {
                posOp = yl;
                negOp = xl;
            }
            if (sum > negOp && negOp < -(1 << 4) && posOp > (1 << 4)) {
                return MinValue;
            }
        }

        // if the top 4 bits of hihi (unused in the result) are neither all 0s nor 1s,
        // then this means the result overflowed.
        sbyte topCarry = (sbyte)(hihi >> 4);
        // -17 (-1.0625) is a problematic value which never causes overflow but messes up the carry bits
        if (topCarry != 0 && topCarry != -1 && xl != -17 && yl != -17) {
            return opSignsEqual ? MaxValue : MinValue;
        }

        // Round up if necessary, but don't overflow
        var lowCarry = (byte)(lolo << 4);
        if (lowCarry >= 0x80 && sum < sbyte.MaxValue) {
            ++sum;
        }

        return new Fix8(sum);
    }

我将所有这些放到一个经过适当单元测试的.NET定点数学库中，这个库可以在这里找到：https://github.com/asik/FixedMath.Net

Answer 2

您应该检查hihi，以查看它是否包含任何超出结果范围的相关位。您还可以将结果的最高位与hihi中的相应位进行比较，以查看进位是否传播了那么远，如果是，是否指示溢出(即，位在错误方向上更改)。如果您使用补码表示法，并且单独处理符号位，那么所有这些都可能更容易表达。但在这种情况下，您的−8示例将毫无意义。

看看你的例子，你就有了hihi = 0xf0。

hihi   11110000
result     ±###.####

因此，在这种情况下，如果仅在hihi中没有溢出，那么前5位都是相同的，并且结果的符号将与hihi的符号匹配。这不是这里的情况。您可以使用以下命令进行检查

if ((hihi & 0x08) * 0x1f != (hihi & 0xf8))
  handle_overflow();

通过每次添加一个被加数并在每一步之后执行常见的溢出检测，可能最容易检测到进入hihi的进位。还没有准备好一段很好的代码。