3

I've seen multiple questions on the site addressing unsigned integer overflow/underflow. Most of the questions about underflow ask about assigning a negative number to an unsigned integer; what's unclear to me is what happens when an unsigned int is subtracted from another unsigned int e.g. a - b where the result is negative. The relevant part of the standard is:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

In this context how do you interpret "reduced"? Does it mean that UINT_MAX+1 is added to the negative result until it is >= 0?

I see that the main point is addressed by this question (which basically says that the standard chooses to talk about overflow but the main point about modulo holds for underflow too) but it's still unclear to me:

Say the result of a-b is -1; According to the standard, the operation -1%(UINT_MAX+1) will return -1 (as is explained here); so we're back to where we started.

This may be overly pedantic, but does this modulo mean a mathematical modulo as opposed to C's computational modulo?

Reinstate Monica
  • 588
  • 7
  • 21
  • Nothing is added or subtracted, and no modulol operation is performed: the result is truncated to the number of bits of the destination operand. If the `unsigned` type is 32 bits, more bits do not even exist. However the result of a 32-bit multiplication could be 64 bits in the processor, in which case the upper 32-bits are ignored. – Weather Vane Jun 17 '18 at 21:27
  • 2
    Conceptually, the calculations are done using 'infinite precision', and the result is reduced to a value in the range `0..UINT_MAX`. – Jonathan Leffler Jun 17 '18 at 21:32
  • The modulo operations shown in examples are used to explain what happens in terms of decimal numbers. The processor does not use decimal numbers, but binary, which when expressed in the convenient hexadecimal notation are easier to understand. In this format, the truncation, or limitation, is easier to see. – Weather Vane Jun 17 '18 at 21:37
  • The part of the standard you posted talks about overflow, not underflow. It just tells that whenever an operation envolving unsigned operands surpasses the upper limit, it will get back to the limits by performing modulo the largest number that can be represented. For example, if the result would be UINT_MAX+3 not considering limits, then it will be 2 (modulo UINT_MAX+1). – Enzo Nakamura Jun 17 '18 at 21:40
  • 1
    @EnzoNakamura I think that is misleading. The code doesn't do any modulo operations. The result is either truncated, or if there are no more significant bits, allowed to wrap. Integer sizes suit the natural szie of the processor registers, allowing this to happen without any post-processing. – Weather Vane Jun 17 '18 at 21:44
  • @WeatherVane Indeed. No modulo operations may be performed by the computer. What I was trying to say is that if there were to be more significant bits, one can consider the result as a modulo (on the sense that it gets back counting from zero). In reality, the computer may just ignore the more-significant bits. Reading again, I agree it sounded misleading on this point. – Enzo Nakamura Jun 17 '18 at 21:54
  • 1
    @WeatherVane As like as "no modulo operation is performed: the result is truncated to the number of bits" is, that is an _implementation detail_ not specified. Consider a 36-bit CPU that does not have unsigned multiply/divide. Such a platform may use a mask (in effect modulo a result) to 35-bits - and with 1 padding bit and `LONG_MAX == ULONG_MAX`. Such machines employing `xxx_MAX == Uxxx_MAX` rarely exist these days, yet "resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type" is the spec. – chux - Reinstate Monica Jun 17 '18 at 23:04
  • How it works in hardware, https://en.wikipedia.org/wiki/Subtractor. Therefore, mathematical modulo is C's modulo. – Neil Jun 18 '18 at 02:06
  • 1
    @NeilEdelman. I'm not sure what you mean. Mathematical modulo is usually Euclidean modulo, where as C's modulo (%) is truncated, see https://en.wikipedia.org/wiki/Modulo_operation – Reinstate Monica Jun 18 '18 at 11:23
  • @afuna you are right; good link. The `%` operator separates into equivalence classes mod the denominator (!=0) only on `unsigned`-types. (I think that's right?) – Neil Jun 18 '18 at 18:04
  • @Jasen: are you just clarifying the terminology of the standard (that calls it remainder) or pointing out some actual difference (AFAIK a modulo operation is the name of that operation that returns the remainder - see the wiki article liked above). – Reinstate Monica Dec 06 '19 at 05:44
  • you make a good point, – Jasen Dec 07 '19 at 11:31

3 Answers3

5

Firstly, a result that is below the minimum value of the given integer type is not called "underflow" in C. The term "underflow" is reserved for floating-point types and means something completely different. Going out of range of an integer type is always overflow, regardless of which end of the range you cross. So the fact that you don't see the language specification talking about "underflow" doers not really mean anything in this case.

Secondly, you are absolutely right about the meaning of the word "reduced". The final value is defined by adding (or subtracting) UINT_MAX+1 from the "mathematical" result until it returns into the range of unsigned int. This is also the same thing as Euclidean "modulo" operation.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
1

The part of the standard you posted talks about overflow, not underflow.

"Does it mean that UINT_MAX+1 is added to the negative result until it is >= 0?"

You can think that's what happens. Abstractly the result will be the same. A similar question has already been asked about it. Check this link: Question about C behaviour for unsigned integer underflow for more details.

Another way to think is that, for example, -1 is in principle from type int (that is 4 bytes, in which all bits are 1). Then, when you tell the program to interpret all these bits 1 as unsigned int, its value will be interpreted as UINT_MAX.

Enzo Nakamura
  • 127
  • 1
  • 9
  • The processor does not do that. It is a way to explain on paper what happens. There is no post-processing which keeps adding until the number is in range. It is simply truncated. – Weather Vane Jun 17 '18 at 21:47
0

Under the hood, addition, or subtraction is bit wise and sign independent. The code generated could use the same instructions independent of whether it is signed or not. It is other operators that interpret the result, for example a > 0. Do the bit wise add or sub and this tells you the answer. b0 - b1 = b111111111 the answer is the same independent of the sign. It is only other operators that see the answer as -1 for signed types and 0xFF for unsigned types. The standard describes this behaviour, but I always find it easiest to remember how it works and deduce the consequences to the code I am writing.

signed int adds(signed int a, signed int b)
{
    return a + b;
}

unsigned int addu(unsigned a, unsigned b)
{
    return a + b;
}


int main() {
    return 0;
}

-> 

adds(int, int):
  lea eax, [rdi+rsi]
  ret
addu(unsigned int, unsigned int):
  lea eax, [rdi+rsi]
  ret
main:
  xor eax, eax
  ret
William J Bagshaw
  • 558
  • 3
  • 15
  • 1
    The authors of the Standard expected that non-arcane implementations would process many kinds of integer math (the published Rationale document identifies which ones) in sign-agnostic fashion, but they did not mandate such treatment. In gcc, something like `uint32_t mul_mod_65536(uint16_t x, uint16_t y) { return (x*y) & 0xFFFF;}` will in some contexts yield code that behaves oddly for some combinations of `x` and `y` as a result of the promotion of `x` and `y` to signed 32-bit values. – supercat Jun 26 '18 at 21:00