4 ms·

This article makes little mention of the fact that shifting a positive, signed integer can result in undefined behaviour if said shift "would" cause the "sign-

• pmjordan 14y ago
  C and its descendants have some really, really scary integer overflow/underflow and type promotion behaviour. As a lot of my code lately runs in the kernel, I'm now extremely paranoid about overflow/underflow bugs, and it's amazing how much innocuous-looking code can be a security issue. I'm amazed that even the newer languages like Go don't really tackle this problem. Signed integer overflow is at least not left undefined, but wrap-around semantics are just as good at hiding bugs. I don't know what exactly the best solution is, but I'd probably default to arbitrary-precision integers which have a highly efficient implementation for native word-sized values and a safe, non-overflowing fallback that can still be made to be pretty fast. Repeated growth checks could be eliminated in many places by some basic static analysis. If you find your code would be faster without the safety, you can always selectively switch to unsafe semantics. Basically, I think the current situation of overflow-by-default is a premature optimisation that's causing far too many bugs.
  • Jabbles 14y ago
    I don't have any data on the performance costs of using arbitrary precision integers in all code, but I'd like to see that if you know of any studies. I would have thought the overhead could be quite significant as you would have to keep a length variable for every single integer and check it every function call... The use of 64 bit integers may significantly reduce the possible places for wrap-around to occur, but I think we (C,C++,Go etc. developers) have to develop a sense of code smell for overflow situations, so that "innocuous-looking code" stands out. That or static analysis.
    • pmjordan 14y ago
      64-bit integers don't really solve the bugs, they just make them slightly less probable. They basically don't help against malicious input in the general case. The most famous example for this kind of bug is probably the binary search implementation in Java: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-... The interesting thing about this bug and many like it, is that you don't need real arbitrary-precision arithmetic to avoid it. The result of the expression (a + b) / 2 can be proven to safely fit into 32 bits if a and b are known to fit into 32 bits as well - the compiler just needs to make the result of the intermediate expression (a + b) be stored 33 bits, or to transform the it into a mathematically equivalent expression that has the same properties as the original expression with a 33-bit intermediate. Of course, this only can be applied to a subset of algorithms - I suspect this quickly devolves into the halting problem in general. But maybe new languages could specify that such halting problem cases need to be manually determined (explicitly choose between arbitrary precision arithmetic and truncation). The simpler cases can be deduced automatically. I guess that means in addition to uint32_t and uint64_t we'll probably need more specific types, such as "positive (nonzero) integer in the range 1 to 1 << 32". Which would be tedious if you had to specify it explicitly all the time, so you'd need good inference and solid support for generic functions.
• Dylan16807 14y ago
  While people like to talk about the 'sign bit' I think it's easier to remember as part of the generic "don't overflow integers" rule. Which is how the part of the standard quoted in the article words it, in terms of what shifted numbers are representable.