6 ms·

WTF? The article states: x = 1987654321 and y = -1987654321? Then the difference between them is -319658654 (negative) which proves that x is less than y. Th

WTF? The article states: x = 1987654321 and y = -1987654321? Then the difference between them is -319658654 (negative) which proves that x is less than y. That’s less than correct. Which is completely 100% wrong. Surely the difference would be x - y i.e (1987654321 - (-1987654321)) = (1987654321 + 1987654321) = 3975308642. Which is perfectly ok, because that's positive and so proves x is greater than y. So this comparison works just fine for negative integers...

Scaevolus 12y ago
(int32_t)3975308642 == -319658654 Overflow makes intuitive arithmetic do unusual things. Similarly, using a+b/2 for binary search midpoints is wrong. http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
imron 12y ago
The writer assumes that the reader understands and knows about how integer overflows work in C.
- bluedino 12y ago
  Exactly, don't use subtraction for comparison in C. The previous commenter may have entered that into say, a Python console where it wouldn't exhibit that behavior.
  - seivadmas 12y ago
    Ah I see the problem. Actually I used a Ruby console. So what then is the CORRECT way of doing this comparison in C, avoiding potential overflow pitfalls?
    - cygx 12y ago
      return (x > y) - (x < y);
      - vardump 12y ago
        That can be very expensive operation. Potentially two branches, not counting return from subroutine.
        cremno 12y ago
        If performance really is of concern, qsort() or similar functions probably shouldn't be used. Instead a dedicated function, which allows to choose a specific algorithm (qsort() doesn't have to use quicksort) and also doesn't involve calling a comparison function pointed to by a function pointer, can be used.
        bluecalm 12y ago
        One interesting thing I have learned recently is that GCC can do inlining through function pointers. That doesn't make your point about dedicated function being better idea for performance but it's one thing "std::sort is faster by design" people often miss. From GCC documentation: >>-findirect-inlining Inline also indirect calls that are discovered to be known at compile time thanks to previous inlining. This option has any effect only when inlining itself is turned on by the -finline-functions or -finline-small-functions options. Enabled at level -O2.
        cremno 12y ago
        But GCC likely isn't able to do that for libc functions like qsort(). Maybe if LTO is enabled and libc is linked statically, it might.
        bluecalm 12y ago
        I have no idea when it can and when it can't do that to be honest. I tested qsort vs std::sort on my machine on my data and performance was the same (Windows, MinGW, GCC 4.8, -flto enabled) but other people reported different results.
        azakai 12y ago
    - Too 12y ago
      The correct way to do a comparison is to use a comparison operator...... If x< y etc...
  - CamperBob2 12y ago
    Exactly, don't use subtraction for comparison in C.... when the difference might exceed 2^31. For many data types, like time, that will normally never happen, making subtraction the safest no-brainpower-needed approach. If in doubt, use the next larger integer type.
    - tptacek 12y ago
      If you ever want to make a vulnerability researcher drool visibly, have a C programmer say, "that will normally never happen, making ${XXX} the safest no-brainpower-needed approach".
      - CamperBob2 12y ago
        You know what causes bugs in C (besides memory leaks)? Complex or clever expressions that don't reveal their semantics at first glance. As an example from elsewhere in the thread: return (x > y) - (x < y); Quick. What's that do? What will the next person who looks at the code think it does?
        marvy 12y ago
        If it's in a function called "cmp", I think they will guess.
        CamperBob2 12y ago
        "I think they will guess." I think tptacek must be ready to have his bib changed, with all the drooling he must be doing.
        nitrogen 12y ago
        A C programmer should know that comparisons evaluate to 1 for true and 0 for false.
        pbsd 12y ago
        C programmers should also be familiar with carry propagation; I see no reason they shouldn't be expected to work out the correctness of int cmp(int x, int y) { const unsigned a = x; const unsigned b = y; const unsigned s = sizeof x * 8 - 1; return ((b^((b^(b-a))&(a^(b-a))))>>s)&~-((a^((a^(a-b))&(b^(a-b))))>>s)^-((a^((a^(a-b))&(b^(a-b))))>>s)&~-((b^((b^(b-a))&(a^(b-a))))>>s); }
  - kragen 12y ago
    Don't use subtraction for comparison in any language that uses floating-point (like Lua or JS) or silent overflow (like, typically, C, C++, Java, and C#). There are a few languages, like Python, where integer subtractions that overflow will transparently produce bignums, but they are kind of the exception.
_almosnow 12y ago
Yeah but that's what happens when people become so adapted to their tools that they forget how real math/world works... and they even have the nerve to stand up for their flawed tools. I actually like and use C everyday, but it would be aberrant for me to say essentially what the article implies: "A math algorithm is wrong because it doesn't work in C"

Scaevolus 12y ago

(int32_t)3975308642 == -319658654 Overflow makes intuitive arithmetic do unusual things. Similarly, using a+b/2 for binary search midpoints is wrong. http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

imron 12y ago

The writer assumes that the reader understands and knows about how integer overflows work in C.

bluedino 12y ago
Exactly, don't use subtraction for comparison in C. The previous commenter may have entered that into say, a Python console where it wouldn't exhibit that behavior.
- seivadmas 12y ago
  Ah I see the problem. Actually I used a Ruby console. So what then is the CORRECT way of doing this comparison in C, avoiding potential overflow pitfalls?
  - cygx 12y ago
    return (x > y) - (x < y);
    - vardump 12y ago
      That can be very expensive operation. Potentially two branches, not counting return from subroutine.
      - cremno 12y ago
        If performance really is of concern, qsort() or similar functions probably shouldn't be used. Instead a dedicated function, which allows to choose a specific algorithm (qsort() doesn't have to use quicksort) and also doesn't involve calling a comparison function pointed to by a function pointer, can be used.
        bluecalm 12y ago
        One interesting thing I have learned recently is that GCC can do inlining through function pointers. That doesn't make your point about dedicated function being better idea for performance but it's one thing "std::sort is faster by design" people often miss. From GCC documentation: >>-findirect-inlining Inline also indirect calls that are discovered to be known at compile time thanks to previous inlining. This option has any effect only when inlining itself is turned on by the -finline-functions or -finline-small-functions options. Enabled at level -O2.
        cremno 12y ago
        But GCC likely isn't able to do that for libc functions like qsort(). Maybe if LTO is enabled and libc is linked statically, it might.
        bluecalm 12y ago
        I have no idea when it can and when it can't do that to be honest. I tested qsort vs std::sort on my machine on my data and performance was the same (Windows, MinGW, GCC 4.8, -flto enabled) but other people reported different results.
      - azakai 12y ago
  - Too 12y ago
    The correct way to do a comparison is to use a comparison operator...... If x< y etc...
- CamperBob2 12y ago
  Exactly, don't use subtraction for comparison in C.... when the difference might exceed 2^31. For many data types, like time, that will normally never happen, making subtraction the safest no-brainpower-needed approach. If in doubt, use the next larger integer type.
  - tptacek 12y ago
    If you ever want to make a vulnerability researcher drool visibly, have a C programmer say, "that will normally never happen, making ${XXX} the safest no-brainpower-needed approach".
    - CamperBob2 12y ago
      You know what causes bugs in C (besides memory leaks)? Complex or clever expressions that don't reveal their semantics at first glance. As an example from elsewhere in the thread: return (x > y) - (x < y); Quick. What's that do? What will the next person who looks at the code think it does?
      - marvy 12y ago
        If it's in a function called "cmp", I think they will guess.
        CamperBob2 12y ago
        "I think they will guess." I think tptacek must be ready to have his bib changed, with all the drooling he must be doing.
      - nitrogen 12y ago
        A C programmer should know that comparisons evaluate to 1 for true and 0 for false.
        pbsd 12y ago
        C programmers should also be familiar with carry propagation; I see no reason they shouldn't be expected to work out the correctness of int cmp(int x, int y) { const unsigned a = x; const unsigned b = y; const unsigned s = sizeof x * 8 - 1; return ((b^((b^(b-a))&(a^(b-a))))>>s)&~-((a^((a^(a-b))&(b^(a-b))))>>s)^-((a^((a^(a-b))&(b^(a-b))))>>s)&~-((b^((b^(b-a))&(a^(b-a))))>>s); }
- kragen 12y ago
  Don't use subtraction for comparison in any language that uses floating-point (like Lua or JS) or silent overflow (like, typically, C, C++, Java, and C#). There are a few languages, like Python, where integer subtractions that overflow will transparently produce bignums, but they are kind of the exception.

_almosnow 12y ago

Yeah but that's what happens when people become so adapted to their tools that they forget how real math/world works... and they even have the nerve to stand up for their flawed tools. I actually like and use C everyday, but it would be aberrant for me to say essentially what the article implies: "A math algorithm is wrong because it doesn't work in C"