定点乘法

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，因为所有的项都是0，除了hihi，只有hihi的最低4位用于最后的总和。

我通常的溢出检测魔术在这里不起作用：结果为零，所以结果的符号是没有意义的（例如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大概可以最容易地检测到。没有准备好一段好的代码。