- Update (16Sept2015): New blog note, similar theme: Know your timer's type
- Update (12April2012): one of the compiler vendors mentioned below has admitted to consider to make the compiler generate a #warning for the dead code examples here! So maybe it is possible to change the world, just a little?
One added to a number
Even if the value one added to any number is always greater than the number itself, this is not so when we work with finite word sizes in a program. The example code below shows some examples that should have a predefined semantics (but they don't seem to):
I would not program with an expression like on the left side! Also, I never use single letters for variables. But this is research, where this is legal for an hour.
A signed number would wrap around when "1" is added to it, from most positive 127 to most negative -128 (assuming 8 bit basic word length in these examples). An unsigned would wrap from its most positive 255 to 0. You must define the int.. and word.. types for yourself, and be sure that there is a greater value around it this would stop the loop (like my 300, which is more than 255 anyway). I do this so that I only have one complex ball in the air at a time. Research tries to divide and conquer.
Since 127 is not less than -128 (top left and right code - it's greater!) and 255 is not less than 0 (bottom left and right code - it's also greater!), my compiler should make the program hit the four breakpoints BP1-BP4 in turn. Right?
Not my compiler, optimized code or not! The program only hits BP3 and BP4! In the rightmost code, the variable "y" runs before "x" by "1", so all is fine. But in the leftmost code, the variable "x" incremented in the expression as "x+1" causes the compiler to get it wrong!
I tried to take control of the value "1" that's added by making a variable "one" with value "1" as signed or unsigned, but it did not help. I tried two variables that followed each other and "x < (y+1)", but it did not help. Finally I tried "(((x+1)-x)>0)", but still I never hit the false branches BP1-BP4!
Compilers
I compiled with the IAR compiler for an eight bit machine. We also compiled with gcc on Linux, and it's the same. I ran a test with static analysis tool QA·C from Programming Research with rather strict "personality", and it did not complain. I have not tested with PC-Lint.
The "excuse"
Of course there is an "excuse" for this in the C compiler world. How an expression is internally evaluated is not the programmer's business. He doesn't own the expression. This is so by language design.
So, if they use 16 bits to evaluate an 8 bit expression (there is nothing like an "8 bit expression", it's "their any-bit expression"), then it would not wrap around from 127 or 255, but get straight into 128 or 256. If there is width enough. But they will sooner or later get another semantics from the same syntax, as widths go from 8 to 16 to 32 to 64 - and wrap around is or is not inevitable!
(How about type casting inside the expression? In this case I could try to, but I would still have to test to know what happens - hugely unnecessary in 2012, almost 50 years after Fortran. WYSI-not-WYG! And besides, I had already used typed variables into the expression)
(This remembers me of a situation where I was going to make a single-bit mask by shifting into a word8, 16 or 32. In order to make a macro work, the one'er that I had to use was required to be typecast to a long. So the macro became #define MASK_F(c) (1L << c), observe the 'L'. The standard seems to state that it is supposed to be like this. The long typecast was required for the 32-bit mask, and did not hurt for the other masks. I wonder why this is intelligent language design)
Back to the not hitting false issue. There is a serious cognitive problem also here. Any programmer relates to word widths. They are always finite, like a ruler inside our heads, from one ear to the other.
We should hit all those breakpoints! But the state of the art is that we might probably not get there.
We would never know, a priori. But this is as precise as it gets: we'd have to think about this expression is a bubble.
(PS, if you are still with me. My starting sentence "Even if the value one added to any number is always greater than the number itself" is about as precise as I could make it..)
.
typedef signed char int8_a;
typedef unsigned char word8_a;
typedef unsigned short word16_a;
#define MAX 300
word16_a cnt;
{
// -------- signed --------
{
int8_a x = 0;
cnt = 0;
//
while (cnt < MAX)
{
if (x < (x+1))
{
cnt = cnt + 1;
}
else
{
cnt = MAX; // BP1
}
x = x + 1;
//
}
}
// -------- unsigned --------
{
word8_a x = 0;
cnt = 0;
//
while (cnt < MAX)
{
if (x < (x+1))
{
cnt = cnt + 1;
}
else
{
cnt = MAX; // BP2
}
x = x + 1;
//
}
}
}
| // Øyvind Teig
// Trondheim
// Norway
//
//
{
// -------- signed --------
{
int8_a x = 0;
int8_a y = 1;
cnt = 0;
while (cnt < MAX)
{
if (x < y)
{
cnt = cnt + 1;
}
else
{
cnt = MAX; // BP3
}
x = x + 1;
y = y + 1;
}
}
// -------- unsigned --------
{
word8_a x = 0;
word8_a y = 1;
cnt = 0;
while (cnt < MAX)
{
if (x < y)
{
cnt = cnt + 1;
}
else
{
cnt = MAX; // BP4
}
x = x + 1;
y = y + 1;
}
}
}
|
A signed number would wrap around when "1" is added to it, from most positive 127 to most negative -128 (assuming 8 bit basic word length in these examples). An unsigned would wrap from its most positive 255 to 0. You must define the int.. and word.. types for yourself, and be sure that there is a greater value around it this would stop the loop (like my 300, which is more than 255 anyway). I do this so that I only have one complex ball in the air at a time. Research tries to divide and conquer.
Since 127 is not less than -128 (top left and right code - it's greater!) and 255 is not less than 0 (bottom left and right code - it's also greater!), my compiler should make the program hit the four breakpoints BP1-BP4 in turn. Right?
Not my compiler, optimized code or not! The program only hits BP3 and BP4! In the rightmost code, the variable "y" runs before "x" by "1", so all is fine. But in the leftmost code, the variable "x" incremented in the expression as "x+1" causes the compiler to get it wrong!
I tried to take control of the value "1" that's added by making a variable "one" with value "1" as signed or unsigned, but it did not help. I tried two variables that followed each other and "x < (y+1)", but it did not help. Finally I tried "(((x+1)-x)>0)", but still I never hit the false branches BP1-BP4!
Compilers
I compiled with the IAR compiler for an eight bit machine. We also compiled with gcc on Linux, and it's the same. I ran a test with static analysis tool QA·C from Programming Research with rather strict "personality", and it did not complain. I have not tested with PC-Lint.
The "excuse"
Of course there is an "excuse" for this in the C compiler world. How an expression is internally evaluated is not the programmer's business. He doesn't own the expression. This is so by language design.
So, if they use 16 bits to evaluate an 8 bit expression (there is nothing like an "8 bit expression", it's "their any-bit expression"), then it would not wrap around from 127 or 255, but get straight into 128 or 256. If there is width enough. But they will sooner or later get another semantics from the same syntax, as widths go from 8 to 16 to 32 to 64 - and wrap around is or is not inevitable!
(How about type casting inside the expression? In this case I could try to, but I would still have to test to know what happens - hugely unnecessary in 2012, almost 50 years after Fortran. WYSI-not-WYG! And besides, I had already used typed variables into the expression)
(This remembers me of a situation where I was going to make a single-bit mask by shifting into a word8, 16 or 32. In order to make a macro work, the one'er that I had to use was required to be typecast to a long. So the macro became #define MASK_F(c) (1L << c), observe the 'L'. The standard seems to state that it is supposed to be like this. The long typecast was required for the 32-bit mask, and did not hurt for the other masks. I wonder why this is intelligent language design)
Back to the not hitting false issue. There is a serious cognitive problem also here. Any programmer relates to word widths. They are always finite, like a ruler inside our heads, from one ear to the other.
We should hit all those breakpoints! But the state of the art is that we might probably not get there.
We would never know, a priori. But this is as precise as it gets: we'd have to think about this expression is a bubble.
(PS, if you are still with me. My starting sentence "Even if the value one added to any number is always greater than the number itself" is about as precise as I could make it..)
.
