Обнаружение переполнения при умножении с фиксированной точкой

Вы должны проверить hihi, чтобы увидеть, содержит ли он какие-либо релевантные биты за пределами диапазона результата. Вы также можете сравнить старший бит результата с соответствующим битом в hihi, чтобы увидеть, распространился ли перенос так далеко, и если да (т. е. бит изменился), указывает ли это на переполнение (т. е. бит изменился в неправильном направлении). ). Все это, вероятно, было бы легче сформулировать, если бы вы использовали нотацию дополнения и обрабатывали знаковые биты отдельно. Но в таком случае ваш пример с −8 будет бессмысленным.

Глядя на ваш пример, у вас есть hihi = 0xf0.

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

Таким образом, в этом случае, если бы не было переполнения только в hihi, то все первые 5 битов были бы одинаковыми, а знак результата соответствовал бы знаку hihi. Это не тот случай здесь. Вы можете проверить это, используя

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

Перенос в hihi, вероятно, можно легко обнаружить, добавляя результат по одному слагаемому за раз и выполняя обычное обнаружение переполнения после каждого шага. У меня нет хорошего куска кода для этого.

Это заняло у меня много времени, но в конце концов я все понял. Этот код протестирован для работы для всех возможных комбинаций x и y в диапазоне, разрешенном sbyte. Вот закомментированный код:

    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