1

What is unsigned underflow and what's the relationship of subtraction produced a borrow? This is an excerpt from ARM Architecture Reference Manual.

For a subtraction, including the comparison instruction CMP, C is set to 0 if the subtraction produced a borrow (that is, an unsigned underflow), and to 1 otherwise.

From https://cwe.mitre.org/data/definitions/191.html, integer underflow means subtracting a value from a negative signed value to get positive value (for example with 2 bit system, b10[-2] - b01 [1] = b10 + b10 + 1 = b01 = +1). I used the fact that in 2's complement system, subtraction is addition with bit reversals + 1.

Unsigned undeflow should be different from the integer underflow because the same operation results in the correct one (for example b10[2] - b01[1] = b10 + b10 + 1 = b01 = +1). But I'm not sure what makes the unsigned underflow condition. I also can't see how this has something to do with the condition when subtraction produced a borrow.

Added

I kinda understand that unsigned underflow occurs when b00 [0] - b01[1] = b00 + b10 + 1 = b11 = 3. But it's confusing to understand because it's unsigned underflow but doesn't seem to produce a borrow (no carry generated) -- From John Bollinger's answer A "borrow" is the subtraction analogue of a "carry". Then, borrow is an opposite of a carry?

prosseek
  • 182,215
  • 215
  • 566
  • 871
  • 1
    Subtract 2 from 1 with unsigned numbers, get 255 (byte) or 65535 (word), etc.? – Dave S May 30 '17 at 03:15
  • The only plausible meaning for the term is the result of subtracting a greater unsigned integer value from a lesser one. The mathematical result of such an operation would be a negative number, but the computed result is (interpreted as) a positive one. A "borrow" is the subtraction analogue of a "carry". – John Bollinger May 30 '17 at 03:19
  • Possible duplicate of [Question about C behaviour for unsigned integer underflow](https://stackoverflow.com/questions/2760502/question-about-c-behaviour-for-unsigned-integer-underflow) – Vishwajeet Vishu May 30 '17 at 03:58
  • @Vishwajeet Vishu: I think it's a very different question, as your reference is about unsigned value representation as a signed one in C, and mine is about ARM's carry bit generation. – prosseek May 30 '17 at 04:11
  • @prosseek my apologies then. There also interger underflow was explained. Thats why – Vishwajeet Vishu May 30 '17 at 04:24

2 Answers2

3

binary subtraction is done with addition, it is the beauty of twos complement. from grade school we know that a - b = a + (-b) and twos complement tells us that -b = ~b + 1 (invert and add one). so a - b = a + (~b) + 1, which you can do by inverting b and setting the carry in bit rather than clearing it. (invert b and invert the carry in).

so 5 - 4

 1111
  101
+ 011
=====
  001

had this been done with grade school math there wouldnt have been a borrow.

and 4 - 5

 0001
  100
+ 010
=====
  111

and you can repeat this for other bit patterns, you will see that a borrow results in no carry out and no borrow results in a carry out.

We know that when it is addition the carry out bit is an unsigned overflow, some processors invert the carry out on a subtraction (just like inverting the carry in and second operand), some dont, would have to look at arms details on this, but the bit ends up in the carry flag in general (if the processor even have flags). so based on the documentation or sometimes you have to hack your way through this (do experiments) but without the carry out inversion yes a borrow and a carry are opposite.

I assume the unsigned underflow is the same as a borrow, 4 - 5 means you underflowed. Unsiged 4 - 5 = 7 as we saw above. but signed 4 - 5 = -1, for addition/subtraction the processor doesnt know signed from unsigned those are concepts that are relevant to the programmer and/or higher level language. again the beauty of twos complement.

squ1dd13
  • 84
  • 2
  • 9
old_timer
  • 69,149
  • 8
  • 89
  • 168
1

In elementary arithmetic, a carry is a digit that is transferred from one column of digits to another column of more significant digits. It is part of the standard algorithm to add numbers together by starting with the rightmost digits and working to the left. For example, when 6 and 7 are added to make 13, the "3" is written to the same column and the "1" is carried to the left. When used in subtraction the operation is called a borrow.
Wikipedia

It is not fundamentally different for unsigned integer subtraction.

The term underflow comes from floating point arithmetic, and is defined in LIA-1:

b) underflow: the absolute value of the unrounded result is less than the smallest normal value, and the rounded result may have lost accuracy due to the denormalisation (more than lost by ordinary rounding if the exponent range was unbounded).
IEC 10967 §4.1.3

The term integer underflow is actually a misappropriation of the term underflow. What is actually meant is that the result of the subtraction cannot be represented by the fixed width integer type.

jxh
  • 69,070
  • 8
  • 110
  • 193
  • Good reference, but I still don't see the relationship between unsigned underflow and producing a borrow (carry). – prosseek May 30 '17 at 04:59
  • Because machine subtraction is really an addition against a complement. – jxh May 30 '17 at 06:40
  • @prosseek I agree. The definition of overflow given in this answer is for floating-point arithmetic, not signed integer arithmetic. – Ellen Spertus Jun 27 '18 at 17:59
  • 1
    @EllenSpertus: I see your point. I think integer underflow is actually a misappropriation of the floating point term against integer overflow with negative values. – jxh Jun 27 '18 at 19:25