-
str2long Contest Results Part 1
[NOTE: Reading this post only makes sense if you read and cared about this previous post.] Ok, evaluating the submissions has been more work than I anticipated, and also things have gotten pretty busy at work, so I’m going to split the evaluation of the submissions into two parts. This first part will discuss objective…
-
A Quick Coding Contest: Convert String to Integer Without Overflow
UPDATE: As of Saturday March 9, the contest is closed. Results will be posted in a few days. I’ve created a Github repository containing all submissions and my test harness. Regular readers will know that I’m obsessed with integer overflows. One apparently simple piece of code that many programmers get wrong in this respect is…
-
Four Books on Debugging
It often seems like the ability to debug complex problems is not distributed very evenly among programmers. No doubt there’s some truth to this, but also people can become better over time. Although the main way to improve is through experience, it’s also useful to keep the bigger picture in mind by listening to what…
-
Around Zion National Park
Zion NP makes a great destination for a quick weekend trip in winter (and not just for people living nearby—Zion is only about a 2.5 hour drive from Las Vegas). Since the main canyon is 800 m deep, some parts of it don’t get much sun in winter. On the other hand, the east side…
-
Undefined Behavior Executed by Coq
I built a version of OCaml with some instrumentation for reporting errors in using the C language’s integers. Then I used that OCaml to build the Coq proof assistant. Here’s what happens when we start Coq: [regehr@gamow ~]$ ~/z/coq/bin/coqtop intern.c:617:10: runtime error: left shift of 255 by 56 places cannot be represented in type ‘intnat’…
-
Catching Integer Errors with Clang
Peng Li and I at Utah, along with our collaborators Will Dietz and Vikram Adve at UIUC, wrote an integer overflow checker for Clang which has found problems in most C/C++ codes that we have looked at. Do you remember how pervasive memory safety errors were before Valgrind came out? Integer overflows are that way…
-
How to Fuzz an ADT Implementation
Sometimes the standard libraries don’t meet your requirements. When this happens you might grab an open source b-tree, splay tree, Judy array, or whatever, or you might implement something yourself. This post is about the situation where you have some code for a data structure, you also have some unit tests, but even so you…
-
Simplest Program Showing the Difference Between Sequential Consistency and TSO
The effects of weak memory models on programs running on shared-memory multiprocessors can be very difficult to understand. Today I was looking for the simplest program that illustrates the difference between sequentially consistent execution and TSO (the memory model provided by x86 and x86-64). Based on an example from Section 8.2.3.4 of the big Intel…
-
Use of Goto in Systems Code
The goto wars of the 1960s and 1970s are long over, and goto is dead—except that it isn’t. It has a number of legitimate uses in well-structured code including an idiom seen in systems code where a failure partway through a sequence of stateful operations necessitates unwinding the operations that have already completed. For example:…
-
Nobody Expects the Spanish Inquisition, or INT_MIN to be Divided by -1
INT_MIN % -1 and INT_MIN / -1 in C/C++ are little gifts that keep on giving. Recently, Xi Wang has been using this construct to knock over languages implemented in C/C++. Then today Tavis Ormandy posted an excellent local DOS for a Windows 8 machine. But the fun doesn’t stop there. For one thing, as…