2

I want to compare sequence numbers (given to this code from elsewhere) that may wrap around. Simply comparing two such values will not handle the case like 0x00000002 being greater than 0xfffffffd, but I can assume that the numbers being compared are close together, not nearly 4 billion apart.

I get the desired result efficently if, rather than comparing, I subtract, allowing two's complement wrap-around, and then interpreting the difference as signed. In fact, I would hope that the final test (for branching) against 0 will be no extra cost as the subtraction already set the flags.

My question concerns the presence of undefined behavior in C++11 and later. How do I write this so it does what I said, rather than the optimizer possibly trashing the code, perhaps assuming that the result is never negative.

The straightforward code would be:

bool seq_ordered (uint32_t a, uint32_t b)
{
auto delta = int32_t (b-a);
return delta > 0;
}

Would it be better to do the initial subtraction while interpreting the arguments as signed or unsigned? Is there a modern idiom to provide for wrapping arithmetic?

  • It's often important to be careful with the types of numeric literals (e.g. use 0u rather than 0, or use UINT32_C etc), but your 0 above is OK. – Steve314 May 30 '16 at 3:20
2

(Disclaimer: I am not an expert in undefined behavior. But I believe I know just enough to give an answer to this question.)
(Disclaimer: Length of answer is not an indication of correctness.)
(More disclaimer: It appears that Daniel Jour's answer handles a condition that I didn't (nor does OP's version): when (b-a) == 0x80000000. The significance is that neither OP's or my version of code can be used safely as a sorting predicate, which requires tie-breaking. Sorting modular numbers is a topic in itself and the existence of an answer is data-dependent.)

// OP's original code
bool seq_ordered (uint32_t a, uint32_t b)
{
    auto delta = int32_t (b-a);
    return delta > 0;
}

I think your code is fine as-is. It makes two assumptions, but both assumptions should be fine.

  • The source values a and b are correctly encoded in binary scaling, which is compatible with two's complement.
  • The C++ target platform uses two's complement.

You should be careful regarding the first point (the source values), especially if they are generated by hardware (such as rotary encoder). Although it is practical to assume that most C++ targets use two's complement, analog-to-digital devices are not part of your "computer environment". Check the documentation of the electronic component.

Guarding against the second point is simple: use a static_assert so that the code will not compile on targets that do not use two's complement.

static_assert((uint32_t)(-1) == (uint32_t)0xFFFFFFFFuL, "Invalid arithmetic unless target uses two's complement");

Explanation: (according to my understanding)

  • Subtraction between two uint32_t obeys modulo 232
  • Conversion from uint32_t into int32_t is implementation-defined. It is specifically not undefined. Typically this means it is dependent on whether the target uses two's complement or not.
    My opinion is that it is practical to assume it and then guard against using static_assert.
  • If the two preceding steps were correct, the comparison is performed in int32_t and should yield the mathematically correct result.

If you do not like the conversion into int32_t at all, but are comfortable with the practical assumption of two's complement, then you can avoid the conversion as follows:

// I think it should give mathematically identical result, no?
bool seq_ordered(uint32_t a, uint32_t b)
{
    uint32_t diff = (b - a);
    return (diff > 0uL) && (diff < 0x80000000uL);
}

(Disclaimer: based on my testing with a few online C++ compilers, the x86-64 disassembly generated from my version is different from OP's version. Specifically, my version results in two comparisons, whereas OP's version results in one comparison.)

The following links are provided for reference. As I said I'm not expert in this, so I cannot guarantee the correctness of my own answer.

  • Thanks in particular for the links. Your explaination details what I need to know, and it's good to see where that is in the spec rather than just having it repeated. But, you cite the C rules for overflow. Is C++11 different? Does it depend on the type (C likes to do + and - after promotions, while c++ defines them for each integral type). – JDługosz May 30 '16 at 0:46
  • OP's code is not fine. "Conversion from uint32_t into int32_t is implementation-defined [..]" if the result is in the range of representable value of int32_t. Otherwise it's an integer overflow and thus undefined behaviour. Why use a "magic value" 0x80000000 instead of calculating it as "half of the range" ((UINT32_MAX + 1) / 2, note: not the real calculation)? – Daniel Jour May 30 '16 at 10:10
  • Sorry, my first remark was wrong. You're right, it's in fact implementation defined. But why the magic value? – Daniel Jour May 30 '16 at 10:17
  • @DanielJour I actually intended to give you the credit which you deserved, but I am not confident enough to analyze your code (since it is a bit long) to say that it is correct for all situations for which it will compile. (In fact I'm surprised that someone had downvoted yours.) I am intentional in limiting my answer to one type (uint32_t) and to constant values (i.e. I am refraining from generalizations) as I try to analyze the situation (according to the rules). Expert practitioners can certainly make bigger leaps than I do. (Edited: to counteract the undeserved -1, I have now +1 yours.) – rwong May 30 '16 at 10:51
  • @rwong I think that's a good choice. I generalized it because I'm confident of the underlying mathematical "operations", but that's of course not needed if only uint32_t is of interest. You could add a sentence about why it's the value 0x80000000 though (otherwise it's a bit hard to understand). – Daniel Jour May 30 '16 at 10:57
0

You're working on the wrong level here. You should simply return b > a. Writing a function that's correct in all cases is going to be exceptionally difficult and nearly everybody gets it wrong and has a bunch of subtle UB in their codebase. And that's before trying to get it as fast as the compiler.

Or in simple terms, the answer to your question is "You don't".

The only way this can work is to use a builtin compiler feature, like a builtin function or a compiler flag like -fwrapv. These do not exist for all compilers.

  • 1
    I disagree. "You don't" is the best choice when there's an already working implementation, for example provided by the compiler. But somebody had to write this, too. Which is going to be you if the environment you're targeting doesn't provide such functionality. It's really difficult, true. One can easily miss cases of undefined behaviour, true (if you find one in my answer, please let me know). Moreover, there's also the possibility to write the required code in the assembly language of the target. – Daniel Jour May 29 '16 at 10:31
  • They didn't have to write that, because they were under different constraints- they can make assumptions that you never can. Also, writing the function in the assembly language of the target is basically admitting defeat, since the question is in C++, – DeadMG May 30 '16 at 11:47
  • I think the intention was to define a non-transitive wrapping relation so that 0xAAAAAAAA would compare greater than 0x55555555, and 0x00000000 would compare greater than 0xAAAAAAAA, but 0x55555555 would compare greater than 0x00000000. – supercat Jul 6 '16 at 21:29
0

TL;DR version:

Since there's no such thing as overflow / underflow with unsigned data types in C++ you can safely calculate a difference between your two values. The size of this difference in relation to the range of possible values indicates which value is less than the other:

template<bool Strict = true, typename T>
bool ordered(T assumed_smaller, T assumed_larger) {
  static_assert(std::is_unsigned<T>::value, "Need unsigned");
  // Calculate the half of the range of the type, by using it's bit width.
  constexpr T const half_range = 1u << ((sizeof(T) * CHAR_BIT) - 1);
  // Calculate difference, possibly with wrap around.
  T const difference = assumed_larger - assumed_smaller;
  bool const not_equal = difference != 0;
  if (Strict) {
    // Strict mode, disallow ordered(a,b) and ordered(b,a) to be both true
    return not_equal
           && ((difference < half_range)
               || ((difference == half_range)
                   && (assumed_smaller < assumed_larger)));
  } else {
    // Non-strict, both ordered(a,b) and ordered(b,a) are true
    // if they're half_range apart.
    return not_equal && (difference <= half_range);
  }
}

A bit more detail:

Assuming 2 bit unsigned integers (thus 0 to 3 as possible values), one has the following cases:

0 0 | false
0 1 | true
0 2 | true
0 3 | false

1 0 | false
1 1 | false
1 2 | true
1 3 | true

2 0 | false (0 2 is already true)
2 1 | false
2 2 | false
2 3 | true

3 0 | true
3 1 | false (1 3 is already true)
3 2 | false
3 3 | false

true means the first value on the line is to be considered "coming before" the second value. One can better imagine this when viewing the possible values arranged in a kind of a circle (since we want to allow wrapping):

  0
3   1
  2

Two values are in the correct order if we can get from the assumed smaller one to the other one - going clockwise - in no more than 2 steps. Thus 3 0 are in the correct order, but 3 2 are not.

To accomplish this, one just needs to check whether assumed_larger - assumed_smaller <= 2 (where 2 is half of max_value + 1, or 2^(bits-1)). This difference is the number of steps in clockwise direction if assumed_larger >= assumed_smaller and in counter-clockwise direction otherwise (thanks to modulo, example: 0 - 3 = -3 = -3 + 4 = 1 (mod 4)).

This leaves the following issue: 0 2 and 2 0 (as well as 1 3 and 3 1) both require 2 steps, thus with the above test both would be in the correct order, which is a violation of the expectation that "if a != b, then either a before b or b before a.

Since the question states that the values won't be "far apart", this wouldn't be an issue, but to correct it one needs to handle the case assumed_larger - assumed_smaller == 2 specially by actually comparing both values.

bool seq_ordered(uint32_t assumed_smaller, uint32_t assumed_larger) {
  constexpr uint32_t const half_range = 1 << ((sizeof(uint32_t) * CHAR_BIT) / 2);
  uint32_t difference = assumed_larger - assumed_smaller;
  return (difference != 0)
         && ((difference < half_range)
             || ((difference == half_range)
                 && (assumed_smaller < assumed_larger)));
  • Thanks. Why not just use strick < rather than <= and avoid the separate test for equality? – JDługosz May 29 '16 at 7:26
  • @JDługosz Because with < you'll get incorrect result for assumed_smaller == 0. – Daniel Jour May 29 '16 at 7:37
  • @JDługosz Wait a second ... assuming 2 bit unsigned integers (0 - 3), what should seq_ordered(0, 3) return? – Daniel Jour May 29 '16 at 7:38
  • The Q states that the delta will be small compared to the range of the type. So this should be false, since -1 has a smaller absolute value than +3. Using the original code posted, with 2 bit types, produces this result. With your code, 3 <= 3 requires 3!=3 to veto it, but writing 3 < 3 would also work to produce false. – JDługosz May 29 '16 at 7:52
  • 1
    This isn't correct - you've performed the subtraction then checked for over/underflow, which is illegal. – DeadMG May 29 '16 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.