> 1. Explicitly set the C standard to C17 or older, so the code is built using the custom boolean type.
> Option 1) seemed like the easiest one, but it also felt a bit like kicking the can down the road – plus, it introduced the question of which standard to use.
Arguably, that's the sanest one: you can't expect the old C code to follow the rules of the new versions of the language. In a better world, each source file would start with something like
#pragma lang_ver stdc89
and it would automatically kick off the compatibility mode in the newer compilers, but oh well. Even modern languages such as Go miss this obvious solution.
On the topic of the article, yeah, sticking anything other than 0 or 1 into C99 bool type is UB. Use ints.
Yeah, it’s only kicking the can down the road if you’re the actual maintainer of the software.
If you’re just a packager, it’s your job to get the package to build and work correctly; for your own sanity, you should be making minimal changes to the underlying code to facilitate that. Get it building with the old language version and file a bug report.
With C you put that information as a build option in your Makefile or similar. That’s a consequence of C only standardizing the actual language (and a runtime library), not the build environment.
I know this is likely to be an unpopular take but: I wish it was normal to ship your compiler in your source repo.
Modern compilers are bloated as hell huge things which makes it a bit impractical, but if it was a normal thing to do then we'd probably have optimized the binary sizes somewhat.
I just really like the idea of including _everything_ you need for the project. Also ensures that weird problems like this dont happen. As an extra benefit, if you included the compiler source and a bootstrapping path instead of just the latest binary, then you could easily include project specific compiler / language extensions with no extra effort.
> you can't expect the old C code to follow the rules of the new versions of the language
Well, to be pedantic, the entire point of the C standard, and the standard body, is that you should expect it to work, as long as you're working within the standard!
Not really, no. Newer versions of standard can (and do, although rarely, I have give it to C standard committee) introduce incompatibilities with earlier versions of standard. E.g. at one point the standard explicitly allowed to #undef "bool", "true", and "false" (and to redefine them later) but IIRC this has been deprecated and removed.
In any case: blindly switching what is essentially a typedef-ed int into _Bool has no business working as expected, since _Bool is a rather quirky type.
If I were the author, I would skip the part about using the compiler explorer and reading the assembly. When I write C code, I need to satisfy the rules of the C language. Unless I’m debugging the compiler or dealing with performance issues, my experience is that reading the generated assembler and understanding it is usually a slow way of debugging. The author eventually did compile with -fsanitize=undefined but I would honestly do that first. It prints a nice error message about the exact issue as the author has shown.
I have to disagree. If you merely want to fix the problem, you can stop as soon as you find something that's awry and whose alteration removes the problem. But don't you want to understand the problem? Don't you want to see how the compiler can reasonably generate code that says a bool variable is true and false at the same time?
It’s about abstraction layers. Most of the time, understanding the generated assembler code isn’t useful when it comes to understanding the problem. It satisfies my curiosity sure, but the problem is at the C level, an undefined behavior.
Understanding what the C compiler generates is interesting, but without a corresponding intuition about the optimizer passes, such understanding is shallow and unlikely to be generalized to other problems in the future. You probably won’t even remember this the next time you debug another undefined behavior. On the other hand, if you were to know the optimizer passes employed by the compiler and could deduce this code from that, then it is a useful exercise to enhance your intuition about them.
I think it depends on your experience. I have a lot of experience from the Old Days™ and from developing for microcontrollers, so I find reading assembly very natural and straightforward. When coding for the really small MCUs I've often had the disassembly generated and shown on another window every time I incrementally build, and can check and make sure it's what I was expecting to see.
I do agree that knowledge of compiler optimizations is really important to working this way, though you'll eventually pick them up anyway. I don't see much value in looking at -O0 or -Og disassembly. You want the strongest stuff the compiler can generate if you're going to do this, which is usually either -O3 or -Oz (both of which are strong in their own ways). -O0 disassembly is... just so much pain for so little gain. Besides, -O3 breaks more stuff anyway!
For someone without this level of experience (and who isn't interested in learning)... yeah, I can see why you'd want to do this another way. But if you've got the experience already, it's plenty fast enough.
I think that's the kind of intuitive decision that comes from years of troubleshooting experience. It's not obvious that would be the place to start. It's impressive to me at least he got there.
The author knew there was a problem, knew where the problem was, and knew what the problem was, but even with that and an extensive perusal of the standard he still only thinks he knows what part of the standard was violated, presumably because nothing else fit ("didn't explicitly say anything about invalid _Bool values. After some more searching, I believe I've found my answer"). There's no way anyone without omniscience could have predicted this obscure issue being present somewhere in Doom's 60,000 lines of code.
Presumably also the author has now learned this, after discovering at the end that compiling with the sanitizer enabled immediately showed which is the bug, which would have saved a lot of time if he had always used it.
I've never felt the need to use a separate boolean type in C; zero and nonzero are enough and very natural to use.
Seeing "== false" and variations thereof always triggers the suspicion that its author doesn't fully understand boolean expressions. I have once seen the even worse "(x == false) == true".
Yeah, but it's a shame that almost every language gets it wrong (and even traditional presentation of mathematical logic) and uses zero as representation of FALSE. It should represent TRUE!
Pedantic: the axioms of Boolean algebra don’t assign any natural numbers to the elements “top” and “bottom” of the set it operates on. The notation is usually “1” and “0” but it doesn’t have to be. It’s a convenience that many computer languages have named those elements “true” and “false”, and yes, it’s totally valid that in some representations, top = 0 = true and bottom = 1 = false.
Technically true, in practice using 0 for the bottom element and 1 for the top is a pretty strong convention; justified, for example, by the connection to probability measures and isomorphism with the Boolean ring ℤ/2ℤ.
That is right, and you could map the Boolean values to other numbers, e.g. mapping them to +1 and -1 corresponds better to many of the hardware implementation techniques for logic circuits.
However when the use of Boolean algebra is embedded in some bigger theories, there are cases when the mapping to 0 and 1 becomes mandatory, e.g. in relationship with the theory of probabilities or with the theory of binary polynomials, where the logical operations can be mapped to arithmetic or algebraic operations.
The mapping to 0 and 1 is fully exploited in APL and its derivatives, where it enables the concise writing of many kinds of conditional expressions (in a similar manner to how mask registers are used in GPUs and in AVX-512).
> Pedantic: the axioms of Boolean algebra don’t assign any natural numbers to the elements “top” and “bottom” of the set it operates on.
Yes? That's precisely what I meant when I said that the traditional presentation of mathematical logic get it wrong: it assigns 0 to FALSE and 1 to TRUE, but it can be done other way around.
Yikes. I think this article undersells the point somewhat. This line of code undermines the type system by spraying -1's into an array of structs, so the only surprise to me is that it took this long to break.
typedef struct
{
// If false use 0 for any position.
// Note: as eight entries are available,
// we might as well insert the same name eight times.
boolean rotate;
// Lump to use for view angles 0-7.
short lump[8];
// Flip bit (1 = flip) to use for view angles 0-7.
byte flip[8];
} spriteframe_t;
which is okay to splat with all-ones as long as `boolean` is either a typedef for a fundamental type(*) or an enum – because C enums are just ints in a trenchcoat and have no forbidden bit patterns! The C99 `bool`/`_Bool` is, AFAICS, the first type in C that has fewer values than possible bit patterns.
So yeah, on C99 and C++ this always had UB and could've broken at any time – though I presume compiler devs were not particularly eager to make it ill-behaved just because. But in pre-C99 it's entirely fine, and `rotate == true || rotate == false` could easily be false without UB.
---
(*) other than `char` for which setting the MSB is… not UB but also not the best idea in general.
And, indeed, if you look at the author's writeup, you see exactly that the generated code satisifes `(rotate == true || rotate == false) == false`, since rotate is checked explicitly against 0 and 1. The essence of the difference is:
> When boolean is an enum, the compiler does exactly what I expected – the == false condition checks if the value is equal to 0, and the == true condition checks if the value is equal to 1.
> However, when boolean is actually _Bool, the == false check is transformed into != 1, and the == true check is transformed into != 0 – which makes perfect sense in the realm of boolean logic. But it also means that for a value of 255, hilarity ensures: since 255 is neither 0 nor 1, both conditions pass!
So a value of 255 also makes both checks fail for the enum, but because of the ordering of the code, it was expected to evaluate as != false.
Had the check:
```
if (sprtemp[frame].rotate == false)
```
been written as:
```
if (sprtemp[frame].rotate != true)
```
then it would work for the `bool` type, but not the `enum` type, at least in C23 mode. Assumedly the C++ mode (effectively) treated the boolean as an enum, or possibly as `false == 0`, `true != 0`.
C has no particularly strong type system, and it works on typical platforms with all types up to the introduction of _Bool. And maybe float/double, but I think it gives a NaN.
> Ah-ha! The generated instructions were ever so slightly different. This would be great news, if it wasn't for me forgetting about one little detail: I have zero knowledge of x86 assembly.
Lol'd at this. I've been there: "ah hah! I found you. hrm, now what does this mean..."
TFA makes me thankful my work doesn't involve C / C++. Learning it earlier in life was enough.
This brings memories - back when I was a student programming in Turbo Pascal 6, I got the same invalid bool (due to array range overflow) which was both true and false at the same time.
As someone who has always despised the usage of "foo == true" and "foo == false" in predicates instead of just "foo" or "not foo" (or "!foo"), this pleases me.
That practice misses the point of what it means for a value to be a boolean. (Even in C, if it's actually an int.)
There's another way to explain the UB: IIRC, any value when stored to a _Bool is supposed to be converted to 0 or 1. The memset() bypasses this rule, boom.
That is a fucking travesty. If there’s one thing we should be able to rely on C for it’s that it works with assembly, and it’s always been the case that 0 is false and any other value is true. That’s a compiler bug as far as I’m concerned. I don’t use C++ because it’s gone in a ludicrous unhelpful direction since 2000 or so, but it’s sad to learn that C of all languages decided to favor pedantry over working code.
Note that this is explicitly comparing two values, which is very different from checking whether a single value is true. Surely you wouldn't expect -1 == 0 to evaluate to true.
> Surely you wouldn't expect -1 == 0 to evaluate to true.
I wouldn't, no - but that's exactly what's happening in the test case.
Likewise, I wouldn't expect -1 == 1 to evaluate to true, but here we are.
The strict semantics of the new bool type may very well be "correct", and the reversed-test logic used by the compiler is certainly understandable and defensible - but given the long-established practice with integer types - i.e "if(some_var) {...}" and "if(!some_var) {...}" - that non-zero is "true" and zero is "false", it's a shame that the new type is inconsistent with that.
The (minor, but still) optimization that is enabled by assuming _Bool can contain only 1 or 0 is that negating a boolean value can be with x^1, without requiring a conditional.
That being said, for just testing the value, using the zero/nonzero test that every (?) cpu has is enough; I'm not sure what is achieved here with this more complex test.
I still remember one of my first teachers of programming softly shaming me for writing a condition like
if (something == true)
I haven't done so ever since (1997), and thus I avoid the contrary (with == false) as well, using ! instead. But I would be a lot less ashamed if I knew that there are such conditions in production software.
I would also never guess that the problem described in the article may occur...
Buy your teacher a drink! I went into university with the baggage of ten years of programming experience, mentored by my industry-experienced father. One of our profs had the exact reverse point of view (i.e. "foo == true" was according to him "good practice"), and I wisely chose to disregard his opinions on coding practices from that point on.
> 1. Explicitly set the C standard to C17 or older, so the code is built using the custom boolean type.
> Option 1) seemed like the easiest one, but it also felt a bit like kicking the can down the road – plus, it introduced the question of which standard to use.
Arguably, that's the sanest one: you can't expect the old C code to follow the rules of the new versions of the language. In a better world, each source file would start with something like
and it would automatically kick off the compatibility mode in the newer compilers, but oh well. Even modern languages such as Go miss this obvious solution.On the topic of the article, yeah, sticking anything other than 0 or 1 into C99 bool type is UB. Use ints.
Yeah, it’s only kicking the can down the road if you’re the actual maintainer of the software.
If you’re just a packager, it’s your job to get the package to build and work correctly; for your own sanity, you should be making minimal changes to the underlying code to facilitate that. Get it building with the old language version and file a bug report.
Rust does the right thing, with the per-crate
statement.With C you put that information as a build option in your Makefile or similar. That’s a consequence of C only standardizing the actual language (and a runtime library), not the build environment.
I know this is likely to be an unpopular take but: I wish it was normal to ship your compiler in your source repo.
Modern compilers are bloated as hell huge things which makes it a bit impractical, but if it was a normal thing to do then we'd probably have optimized the binary sizes somewhat.
I just really like the idea of including _everything_ you need for the project. Also ensures that weird problems like this dont happen. As an extra benefit, if you included the compiler source and a bootstrapping path instead of just the latest binary, then you could easily include project specific compiler / language extensions with no extra effort.
That's pretty close to the underlying concept behind Guix and Nix. Give them a glance, if you can!
Since you mention Go, it does offer precisely the feature you describe in the form of build constraints. A file starting with
tells the toolchain to use Go 1.18. A slightly different syntax was used prior to Go 1.17 but the feature itself has existed since Go 1.0.> you can't expect the old C code to follow the rules of the new versions of the language
Well, to be pedantic, the entire point of the C standard, and the standard body, is that you should expect it to work, as long as you're working within the standard!
Not really, no. Newer versions of standard can (and do, although rarely, I have give it to C standard committee) introduce incompatibilities with earlier versions of standard. E.g. at one point the standard explicitly allowed to #undef "bool", "true", and "false" (and to redefine them later) but IIRC this has been deprecated and removed.
In any case: blindly switching what is essentially a typedef-ed int into _Bool has no business working as expected, since _Bool is a rather quirky type.
I'm using the dictionary definition of expect here, which is compatible with what you're saying.
Excellent debugging journey.
If I were the author, I would skip the part about using the compiler explorer and reading the assembly. When I write C code, I need to satisfy the rules of the C language. Unless I’m debugging the compiler or dealing with performance issues, my experience is that reading the generated assembler and understanding it is usually a slow way of debugging. The author eventually did compile with -fsanitize=undefined but I would honestly do that first. It prints a nice error message about the exact issue as the author has shown.
I have to disagree. If you merely want to fix the problem, you can stop as soon as you find something that's awry and whose alteration removes the problem. But don't you want to understand the problem? Don't you want to see how the compiler can reasonably generate code that says a bool variable is true and false at the same time?
It’s about abstraction layers. Most of the time, understanding the generated assembler code isn’t useful when it comes to understanding the problem. It satisfies my curiosity sure, but the problem is at the C level, an undefined behavior.
Understanding what the C compiler generates is interesting, but without a corresponding intuition about the optimizer passes, such understanding is shallow and unlikely to be generalized to other problems in the future. You probably won’t even remember this the next time you debug another undefined behavior. On the other hand, if you were to know the optimizer passes employed by the compiler and could deduce this code from that, then it is a useful exercise to enhance your intuition about them.
I think it depends on your experience. I have a lot of experience from the Old Days™ and from developing for microcontrollers, so I find reading assembly very natural and straightforward. When coding for the really small MCUs I've often had the disassembly generated and shown on another window every time I incrementally build, and can check and make sure it's what I was expecting to see.
I do agree that knowledge of compiler optimizations is really important to working this way, though you'll eventually pick them up anyway. I don't see much value in looking at -O0 or -Og disassembly. You want the strongest stuff the compiler can generate if you're going to do this, which is usually either -O3 or -Oz (both of which are strong in their own ways). -O0 disassembly is... just so much pain for so little gain. Besides, -O3 breaks more stuff anyway!
For someone without this level of experience (and who isn't interested in learning)... yeah, I can see why you'd want to do this another way. But if you've got the experience already, it's plenty fast enough.
I think that's the kind of intuitive decision that comes from years of troubleshooting experience. It's not obvious that would be the place to start. It's impressive to me at least he got there.
The author knew there was a problem, knew where the problem was, and knew what the problem was, but even with that and an extensive perusal of the standard he still only thinks he knows what part of the standard was violated, presumably because nothing else fit ("didn't explicitly say anything about invalid _Bool values. After some more searching, I believe I've found my answer"). There's no way anyone without omniscience could have predicted this obscure issue being present somewhere in Doom's 60,000 lines of code.
With the behavior specified UB sanitizer would have been my first tool to try.
Presumably also the author has now learned this, after discovering at the end that compiling with the sanitizer enabled immediately showed which is the bug, which would have saved a lot of time if he had always used it.
I've never felt the need to use a separate boolean type in C; zero and nonzero are enough and very natural to use.
Seeing "== false" and variations thereof always triggers the suspicion that its author doesn't fully understand boolean expressions. I have once seen the even worse "(x == false) == true".
Yeah, but it's a shame that almost every language gets it wrong (and even traditional presentation of mathematical logic) and uses zero as representation of FALSE. It should represent TRUE!
Zero as the absence of something definitely makes more sense as false than true. It is the case for these common C idioms:
Pedantic: the axioms of Boolean algebra don’t assign any natural numbers to the elements “top” and “bottom” of the set it operates on. The notation is usually “1” and “0” but it doesn’t have to be. It’s a convenience that many computer languages have named those elements “true” and “false”, and yes, it’s totally valid that in some representations, top = 0 = true and bottom = 1 = false.
Technically true, in practice using 0 for the bottom element and 1 for the top is a pretty strong convention; justified, for example, by the connection to probability measures and isomorphism with the Boolean ring ℤ/2ℤ.
That is right, and you could map the Boolean values to other numbers, e.g. mapping them to +1 and -1 corresponds better to many of the hardware implementation techniques for logic circuits.
However when the use of Boolean algebra is embedded in some bigger theories, there are cases when the mapping to 0 and 1 becomes mandatory, e.g. in relationship with the theory of probabilities or with the theory of binary polynomials, where the logical operations can be mapped to arithmetic or algebraic operations.
The mapping to 0 and 1 is fully exploited in APL and its derivatives, where it enables the concise writing of many kinds of conditional expressions (in a similar manner to how mask registers are used in GPUs and in AVX-512).
> Pedantic: the axioms of Boolean algebra don’t assign any natural numbers to the elements “top” and “bottom” of the set it operates on.
Yes? That's precisely what I meant when I said that the traditional presentation of mathematical logic get it wrong: it assigns 0 to FALSE and 1 to TRUE, but it can be done other way around.
Including the words "top" and "bottom". In my language, if(x) is the same as if(x==bottom), and 1<2 resolves to bottom. Take that.
> memset (sprtemp,-1, sizeof(sprtemp));
Yikes. I think this article undersells the point somewhat. This line of code undermines the type system by spraying -1's into an array of structs, so the only surprise to me is that it took this long to break.
`spriteframe_t` is defined as
which is okay to splat with all-ones as long as `boolean` is either a typedef for a fundamental type(*) or an enum – because C enums are just ints in a trenchcoat and have no forbidden bit patterns! The C99 `bool`/`_Bool` is, AFAICS, the first type in C that has fewer values than possible bit patterns.So yeah, on C99 and C++ this always had UB and could've broken at any time – though I presume compiler devs were not particularly eager to make it ill-behaved just because. But in pre-C99 it's entirely fine, and `rotate == true || rotate == false` could easily be false without UB.
---
(*) other than `char` for which setting the MSB is… not UB but also not the best idea in general.
And, indeed, if you look at the author's writeup, you see exactly that the generated code satisifes `(rotate == true || rotate == false) == false`, since rotate is checked explicitly against 0 and 1. The essence of the difference is:
> When boolean is an enum, the compiler does exactly what I expected – the == false condition checks if the value is equal to 0, and the == true condition checks if the value is equal to 1.
> However, when boolean is actually _Bool, the == false check is transformed into != 1, and the == true check is transformed into != 0 – which makes perfect sense in the realm of boolean logic. But it also means that for a value of 255, hilarity ensures: since 255 is neither 0 nor 1, both conditions pass!
So a value of 255 also makes both checks fail for the enum, but because of the ordering of the code, it was expected to evaluate as != false.
Had the check: ``` if (sprtemp[frame].rotate == false) ```
been written as: ``` if (sprtemp[frame].rotate != true) ```
then it would work for the `bool` type, but not the `enum` type, at least in C23 mode. Assumedly the C++ mode (effectively) treated the boolean as an enum, or possibly as `false == 0`, `true != 0`.
Maybe changing the type of the variable to int was the better solution?
C99 does not use bool unless you explicitly include stdbool.h, which won't be in any pre-C99 code. By default, you just get _Bool.
C has no particularly strong type system, and it works on typical platforms with all types up to the introduction of _Bool. And maybe float/double, but I think it gives a NaN.
> For this, I used the Godbolt compiler explorer.
> Ah-ha! The generated instructions were ever so slightly different. This would be great news, if it wasn't for me forgetting about one little detail: I have zero knowledge of x86 assembly.
Lol'd at this. I've been there: "ah hah! I found you. hrm, now what does this mean..."
TFA makes me thankful my work doesn't involve C / C++. Learning it earlier in life was enough.
Small errror: the demo program says
however, seeing the output, what was actually run must have beenThis brings memories - back when I was a student programming in Turbo Pascal 6, I got the same invalid bool (due to array range overflow) which was both true and false at the same time.
As someone who has always despised the usage of "foo == true" and "foo == false" in predicates instead of just "foo" or "not foo" (or "!foo"), this pleases me.
That practice misses the point of what it means for a value to be a boolean. (Even in C, if it's actually an int.)
What is this guy doing... you just build it against the standard it was written for. Yeesh. What a mess.
There's another way to explain the UB: IIRC, any value when stored to a _Bool is supposed to be converted to 0 or 1. The memset() bypasses this rule, boom.
> After consulting some sources, I started translating the assembly instructions into plain Polish
Ah yes, obfuscation
[dead]
That is a fucking travesty. If there’s one thing we should be able to rely on C for it’s that it works with assembly, and it’s always been the case that 0 is false and any other value is true. That’s a compiler bug as far as I’m concerned. I don’t use C++ because it’s gone in a ludicrous unhelpful direction since 2000 or so, but it’s sad to learn that C of all languages decided to favor pedantry over working code.
The code in question is:
Note that this is explicitly comparing two values, which is very different from checking whether a single value is true. Surely you wouldn't expect -1 == 0 to evaluate to true.> Surely you wouldn't expect -1 == 0 to evaluate to true.
I wouldn't, no - but that's exactly what's happening in the test case.
Likewise, I wouldn't expect -1 == 1 to evaluate to true, but here we are.
The strict semantics of the new bool type may very well be "correct", and the reversed-test logic used by the compiler is certainly understandable and defensible - but given the long-established practice with integer types - i.e "if(some_var) {...}" and "if(!some_var) {...}" - that non-zero is "true" and zero is "false", it's a shame that the new type is inconsistent with that.
You're not wrong. The processor has a perfectly good zero/notzero check. There was absolutely no reason for the compiler to check if x^1==0.
The (minor, but still) optimization that is enabled by assuming _Bool can contain only 1 or 0 is that negating a boolean value can be with x^1, without requiring a conditional.
That being said, for just testing the value, using the zero/nonzero test that every (?) cpu has is enough; I'm not sure what is achieved here with this more complex test.
I still remember one of my first teachers of programming softly shaming me for writing a condition like
if (something == true)
I haven't done so ever since (1997), and thus I avoid the contrary (with == false) as well, using ! instead. But I would be a lot less ashamed if I knew that there are such conditions in production software.
I would also never guess that the problem described in the article may occur...
Buy your teacher a drink! I went into university with the baggage of ten years of programming experience, mentored by my industry-experienced father. One of our profs had the exact reverse point of view (i.e. "foo == true" was according to him "good practice"), and I wisely chose to disregard his opinions on coding practices from that point on.