Implement saturating arithmetic on FixedWidthInteger

[stephentyrone]

This PR adds the following methods on FixedWidthInteger:

• addingWithSaturation(_:)
• subtractingWithSaturation(_:)
• negatedWithSaturation(_:)
• multipliedWithSaturation(by:)
• shiftedWithSaturation(leftBy:rounding:)

These implement saturating arithmetic. These are an alternative to the usual +, -, and * operators, which trap if the result cannot be represented in the argument type, and &+, &-, and &* which wrap out-of-range results modulo 2ⁿ for some n. Instead these methods clamp the result to the representable range of the type:

let x: Int8 = 84
let y: Int8 = 100
let a = x + y                     // traps due to overflow
let b = x &+ y                    // wraps to -72
let c = x.addingWithSaturation(y) // saturates to 127

shiftedWithSaturation performs a bitwise shift with rounding (if count is negative) and saturation (if count is positive).

All have generic implementations using only the requirements of FixedWidthInteger, but produce optimal or nearly-optimal code when used with concrete standard library types. Further optimization is possible for bigger-than-Int64 types, but this can happen as follow-up work.

This is another piece of https://github.com/apple/swift-numerics/issues/10

[stephentyrone]

N.B. I'm not totally set on spelling, but reasonably happy with this. These are pretty niche, so it's ok for them to be wordy. I also experimented with Saturating.add, etc, but I didn't totally love that.

[stephentyrone]

@swift-ci test

[stephentyrone]

@swift-ci test

[stephentyrone]

@swift-ci test

[xwu]

Just throwing out another suggestion:

saturatedAdding(_:)
saturatedSubtracting(_:)
saturatedNegation
saturatedMultiplication(by:)

[stephentyrone]

I think if I went that direction, I would probably do:

Saturated.sum(_:_:)
Saturated.product(_:_:)
Saturated.negation(_:)

This is more in-line with other "modified" ops we've been looking at. I'm not sure what to do with subtraction though; I don't much like Saturated.difference(_:_:), for instance.

[stephentyrone]

@swift-ci test

[markuswntr]

Saturation is the term of art here, but if you are unfamiliar with the concept, saturation does not immediately indicate a range enforcement (IMO) – and so I was wondering if it would be better to use a different term. BinaryInteger, for example, uses clamping to convey a similar restriction for its init<T>(clamping source: T) where T : BinaryInteger initializer which, I believe, belongs to the same category of saturated arithmetic. I think addingWithClamping et al. conveys the range enforcement quite nicely.

[stephentyrone]

Saturation is the term of art here, but if you are unfamiliar with the concept, saturation does not immediately indicate a range enforcement (IMO) – and so I was wondering if it would be better to use a different term.

I've been pondering this off and on the last few months, and I've settled on sticking with "saturating". It's true that the existing stdlib initializers use (clamping:), but:

1. I expect most people who are looking for this functionality to be familiar with the term-of-art "saturating" and to search for that name first. Beyond being the term-of-art, it's much, much more precedented than anything else:

   • Wikipedia: https://en.wikipedia.org/wiki/Saturation_arithmetic
   • ARM: SQADD.8h ("signed saturating addition of eight half-word integers")
   • x86: VPADDUSB ("vector packed addition with unsigned saturation of bytes")
   • clang generic vectors: "__builtin_elementwise_add_sat"
   • rust: "saturating_add"
   • C++ P0543 proposes "add_sat"
   • ...

2. The larger group of people who are not already familiar with this style of arithmetic don't know to search for it under any name, but we can document it clearly so that they understand it when they find it, and we teach them the "correct" term that will allow them to find the bindings in other domains in the future.

3. We can reference the (clamping: Other) inits in the documentation to help experienced users find those.

[stephentyrone]

@swift-ci test

[xwu]

"Clamping" is great for labeling the argument of an initializer ("saturating" wouldn't be nearly as good as we're saturating the range of the result type, not the argument), but I would definitely agree "clamping addition" is just...not the way.

[stephentyrone]

@swift-ci test