(C) Robust code Should an unsigned int array index be tested for "< 0"
-
Suppose I have a function that takes an array pointer and an index declared as type unsigned int and the function will access the array at that index. AFAIK "Index < 0" should never evaluate to be true regardless of what the caller passed because the unsigned type will control how the bits at the address of Index are interpreted and there will be no interpretation of a bit as an indication of sign. So implicitly an unsigned int is not capable of an access violation Below / before an array's first element given the pointer arithmetic. All that being said it does not seem at all necessary to test it. There are other reasons to use the test however. #1 it may improve readability as someone who reads the code sees that a full boundary check is being done #2 it may make the code symmetric with other code that tests upper and lower boundaries of any other type of variable #3 if the function is later modified and the type is accidentally changed to int (for example the types are changed when porting to a different machine architecture) or the code is copy and pasted to a different context where Index is not unsigned, omitting the bounds check introduces the possibility of an access violation #4 I think it's possible, perhaps likely, that an intelligent compiler will optimize it out completely, even if it didn't we're not talking about a grave loss of efficiency. So although I feel stupid writing what seems to be redundant and unnecessary code and concern myself with conciseness, for a robust application it seems worthwhile.
Well, I hope this is a question by a student. It would prove that there is at least One student still studying the 'C' language in this world. It also gives me a dark impression of your teacher. (unless if you missed lessons, or was not paying attention) The situation is clearly not understood by you in terms of Bits and Bytes. Signed or Unsigned is all a matter of interpretation, and, something called 2 compliment arithmetic. One Byte of 8 bits can only have 256 possible values, 0 to 255! (Hope you know and understand that much) The question is, how do we interpret this. We can take this as an unsigned range of 0 to 255, or, as a range of -127 to + 127. In the latter case the most significant bit will represent the sign. 1 for Negative, 0 for positive. The beauty of this scheme is the Two Complement Inversion. Every Number can have it's sign changed by first inverting all bits, and then adding One. Addition and Subtraction using that scheme works correctly all the time. It is so good, the machine is not interested in whether a byte is signed or unsigned! It uses the same mechanism to do arithmetic for both! A Byte of value 0xFF will per definition always be interpreted as 255 by the compiler if it is of unsigned type. It will also always be interpreted by the compiler as -1, if it is of signed type. Actually, an Unsigned 32 bit Int initialised to -1, would have the value 4294967295, the same as an Unsigned Byte initialised to -1 would have the value of 255. The Compiler is friendly! If you initialise a signed byte with 255, it's value will be -1! There is hence absolutely no point in testing an unsigned integer for being negative! It has no capacity of being negative! A half decent compiler will probably optimise the test for this condition out! An Unsigned Integer is always, and, per definition, equal or larger than 0. I hope I managed to explain in the above as to WHY! As to your problem of access violations, After a Brief look at your code: (unsigned int32)-1 means for the compiler: 4294967295. So Your essentially loop says for(i=0; i<4294967295;i++){...} Make your iterator Signed! Tell me how you get on after that! Regards :)
Bram van Kampen
-
CPallini wrote:
I would keep it simple: an unsigned cannot be less than zero, full stop.
This simple fact seems to be no longer on the curriculum! Wrote a bit about it to the caller! I feel that an awfull lot of skills are no longer taught, the same skills I had to learn myself, e.g. How does a computer actually work! Registers,Stackpointers, The Stack and the Heap, the function of the OS, Machine Code, what does an assembler do, what does a compiler do, etc. I will encourage anyone willing to study 'C' or 'CPP'. These people on this queery seem to be basically stuck on the underlying hardware concepts. Kind Regards,
Bram van Kampen
-
Well, I hope this is a question by a student. It would prove that there is at least One student still studying the 'C' language in this world. It also gives me a dark impression of your teacher. (unless if you missed lessons, or was not paying attention) The situation is clearly not understood by you in terms of Bits and Bytes. Signed or Unsigned is all a matter of interpretation, and, something called 2 compliment arithmetic. One Byte of 8 bits can only have 256 possible values, 0 to 255! (Hope you know and understand that much) The question is, how do we interpret this. We can take this as an unsigned range of 0 to 255, or, as a range of -127 to + 127. In the latter case the most significant bit will represent the sign. 1 for Negative, 0 for positive. The beauty of this scheme is the Two Complement Inversion. Every Number can have it's sign changed by first inverting all bits, and then adding One. Addition and Subtraction using that scheme works correctly all the time. It is so good, the machine is not interested in whether a byte is signed or unsigned! It uses the same mechanism to do arithmetic for both! A Byte of value 0xFF will per definition always be interpreted as 255 by the compiler if it is of unsigned type. It will also always be interpreted by the compiler as -1, if it is of signed type. Actually, an Unsigned 32 bit Int initialised to -1, would have the value 4294967295, the same as an Unsigned Byte initialised to -1 would have the value of 255. The Compiler is friendly! If you initialise a signed byte with 255, it's value will be -1! There is hence absolutely no point in testing an unsigned integer for being negative! It has no capacity of being negative! A half decent compiler will probably optimise the test for this condition out! An Unsigned Integer is always, and, per definition, equal or larger than 0. I hope I managed to explain in the above as to WHY! As to your problem of access violations, After a Brief look at your code: (unsigned int32)-1 means for the compiler: 4294967295. So Your essentially loop says for(i=0; i<4294967295;i++){...} Make your iterator Signed! Tell me how you get on after that! Regards :)
Bram van Kampen
Before I got your reply I did a little more investigating into the issue. I was looking at the bitwise representation which I noticed is 2C as you said. I wrote this small program to test it out. Here is the output:
//Declare an int and unsigned int, initialize to -1, check bit representation:
//int int_neg_1 = -1;
11111111111111111111111111111111//unsigned int uint_neg_1 = -1;
11111111111111111111111111111111//Cast the unsigned int to int, check representation:
(int)uint_neg_1;
11111111111111111111111111111111//Compare printf as signed and unsigned int for all three:
int_neg_1 : %d: -1, %u: 4294967295
uint_neg_1: %d: -1, %u: 4294967295
(int)uint_neg_1: %d: -1, %u: 4294967295//This is the thing that caught me off guard. "uint_neg_1 < 0" does not evaluate to true.
int_neg_1 < 0: True
uint_neg_1 < 0: False//If however, I cast the unsigned int to "int" it seems to force interpretation as a signed number:
(int)uint_neg_1 < 0: TrueSo it seems that the bitwise storage and representation for signed and unsigned integers is the same. The typecast to int changed the evaluation of the expression. I'd like to see / understand the difference in the assembly instructions because I think that is probably where the paths diverge.
Quote:
There is hence absolutely no point in testing an unsigned integer for being negative! It has no capacity of being negative!
That's what I believed, but based on my experiment it's not safe to rely on the "unsigned" type as an indication of being >= 0. If someone invokes my function with "-1" and it is written without the bounds check, the result is an access violation. As a design practice my code should catch the error of the caller. I have a bad headache, I apologize if I've made mistakes. See this post for the use case of an unsigned int < 0 check: Re: (C) Robust code Should an unsigned int array index be tested for "< 0" - C / C++ / MFC Discussion Boards[^]
/* code sample for demonstration and testing purposes */
#include #define print_binary(a) \
for(j = 31; j >= 0; j--) \
printf("%c", a & (1 << j) ? '1' : '0'); \
printf("\n\n"); -
Before I got your reply I did a little more investigating into the issue. I was looking at the bitwise representation which I noticed is 2C as you said. I wrote this small program to test it out. Here is the output:
//Declare an int and unsigned int, initialize to -1, check bit representation:
//int int_neg_1 = -1;
11111111111111111111111111111111//unsigned int uint_neg_1 = -1;
11111111111111111111111111111111//Cast the unsigned int to int, check representation:
(int)uint_neg_1;
11111111111111111111111111111111//Compare printf as signed and unsigned int for all three:
int_neg_1 : %d: -1, %u: 4294967295
uint_neg_1: %d: -1, %u: 4294967295
(int)uint_neg_1: %d: -1, %u: 4294967295//This is the thing that caught me off guard. "uint_neg_1 < 0" does not evaluate to true.
int_neg_1 < 0: True
uint_neg_1 < 0: False//If however, I cast the unsigned int to "int" it seems to force interpretation as a signed number:
(int)uint_neg_1 < 0: TrueSo it seems that the bitwise storage and representation for signed and unsigned integers is the same. The typecast to int changed the evaluation of the expression. I'd like to see / understand the difference in the assembly instructions because I think that is probably where the paths diverge.
Quote:
There is hence absolutely no point in testing an unsigned integer for being negative! It has no capacity of being negative!
That's what I believed, but based on my experiment it's not safe to rely on the "unsigned" type as an indication of being >= 0. If someone invokes my function with "-1" and it is written without the bounds check, the result is an access violation. As a design practice my code should catch the error of the caller. I have a bad headache, I apologize if I've made mistakes. See this post for the use case of an unsigned int < 0 check: Re: (C) Robust code Should an unsigned int array index be tested for "< 0" - C / C++ / MFC Discussion Boards[^]
/* code sample for demonstration and testing purposes */
#include #define print_binary(a) \
for(j = 31; j >= 0; j--) \
printf("%c", a & (1 << j) ? '1' : '0'); \
printf("\n\n");Member 14088880 wrote:
//This is the thing that caught me off guard. "uint_neg_1 < 0" does not evaluate to true.
And that is correct. An unsigned number can only have positive values in the range 0 to infinity. The main point here is that you must follow the rules of mathematics and logic. If you declare a numeric variable as unsigned then that is how it will be treated, and it will never be considered to have a negative value (even if it does have the sign bit set). The compiler will add code to manipulate the value in such a way that any 'negativeness' is always ignored.
-
Suppose I have a function that takes an array pointer and an index declared as type unsigned int and the function will access the array at that index. AFAIK "Index < 0" should never evaluate to be true regardless of what the caller passed because the unsigned type will control how the bits at the address of Index are interpreted and there will be no interpretation of a bit as an indication of sign. So implicitly an unsigned int is not capable of an access violation Below / before an array's first element given the pointer arithmetic. All that being said it does not seem at all necessary to test it. There are other reasons to use the test however. #1 it may improve readability as someone who reads the code sees that a full boundary check is being done #2 it may make the code symmetric with other code that tests upper and lower boundaries of any other type of variable #3 if the function is later modified and the type is accidentally changed to int (for example the types are changed when porting to a different machine architecture) or the code is copy and pasted to a different context where Index is not unsigned, omitting the bounds check introduces the possibility of an access violation #4 I think it's possible, perhaps likely, that an intelligent compiler will optimize it out completely, even if it didn't we're not talking about a grave loss of efficiency. So although I feel stupid writing what seems to be redundant and unnecessary code and concern myself with conciseness, for a robust application it seems worthwhile.
I wrote a small demonstration of the issue. Peter and Paul are writing ticketing system software and Peter makes a mistake swapping two variables and creating a negative number which is passed as an unsigned integer to Paul. Paul makes a mistake thinking an unsigned int will not cause an out of (lower) bounds array access if it passes the test "index >= 0". Peter makes a mistake, Paul fails to catch it, the memory is potentially corrupted and undefined behavior results. That's the PRINCIPLE the code is meant to demonstrate, which is the only purpose of this code. As an alternative I put in a boundary check based on the address the index would have us access and the addresses of the first and last members of the array. I think that's a better approach. It should match the way the array is accessed exactly and it should be completely independent of variable size, type, typecasting, and bitwise representation. As an aside, VS on the maximum warning level does not warn for the ints passed to the function that was declared with unsigned ints. Also, the compiler can't foresee that a negative value will be passed to the function because the sign of that variable is determined at run time.
#include
#include
#include//Paul writes this code
int get_available_seat_count(unsigned int *seating_counts, unsigned int row_index, unsigned int num_rows, unsigned int seats_per_row)
{
if(row_index < 0)
{
printf("row_index < 0: TRUE\n");
return -1;
}
else
printf("row_index < 0: FALSE\n");//preferable method?:
if(&seating_counts[row_index] < &seating_counts[0])
printf("Array minimum boundary violation, index is %d\n", row_index);if(&seating\_counts\[row\_index\] > &seating\_counts\[num\_rows-1\]) printf("Array maximum boundary violation, index is %d\\n", row\_index); return seats\_per\_row - seating\_counts\[row\_index\];}
//Peter writes this code
void main()
{
//row 0 is the back of the theater, row[num_rows-1] is at the stage
int num_rows = 12;
int seats_per_row = 40;
int n_available_seats;
int row_index;
unsigned int seating_counts[12];
int i;//set the current state of the theater: srand((int)time(NULL)); for(i = 0; i < num\_rows; i++) seating\_counts\[i\] = (unsigned int)rand() % seats\_per\_row; printf("Customer: are there any seats available in the third row from the stage?\\n\\n"); row\_index = 3; //rows are stored in reverse order from customer request, subtract row\_index to get offset n\_available\_sea -
Member 14088880 wrote:
//This is the thing that caught me off guard. "uint_neg_1 < 0" does not evaluate to true.
And that is correct. An unsigned number can only have positive values in the range 0 to infinity. The main point here is that you must follow the rules of mathematics and logic. If you declare a numeric variable as unsigned then that is how it will be treated, and it will never be considered to have a negative value (even if it does have the sign bit set). The compiler will add code to manipulate the value in such a way that any 'negativeness' is always ignored.
It seems like in this signed/unsigned case typecasting allows you to change the way the variable is evaluated in expressions. I think that is typical of typecasting in general, it changes interpretation. On the other hand I think if you typecast to a data type with a different size it does not just affect the expression but also the raw value. Please see my newest reply to the main topic. Thanks
-
Member 14088880 wrote:
//This is the thing that caught me off guard. "uint_neg_1 < 0" does not evaluate to true.
And that is correct. An unsigned number can only have positive values in the range 0 to infinity. The main point here is that you must follow the rules of mathematics and logic. If you declare a numeric variable as unsigned then that is how it will be treated, and it will never be considered to have a negative value (even if it does have the sign bit set). The compiler will add code to manipulate the value in such a way that any 'negativeness' is always ignored.
It seems like in this signed/unsigned case typecasting allows you to change the way the variable is evaluated in expressions. I think that is typical of typecasting in general, it changes interpretation. On the other hand I think if you typecast to a data type with a different size it does not just affect the expression but also the raw value. Please see my newest reply to the main topic. Thanks
-
It seems like in this signed/unsigned case typecasting allows you to change the way the variable is evaluated in expressions. I think that is typical of typecasting in general, it changes interpretation. On the other hand I think if you typecast to a data type with a different size it does not just affect the expression but also the raw value. Please see my newest reply to the main topic. Thanks
-
I wrote a small demonstration of the issue. Peter and Paul are writing ticketing system software and Peter makes a mistake swapping two variables and creating a negative number which is passed as an unsigned integer to Paul. Paul makes a mistake thinking an unsigned int will not cause an out of (lower) bounds array access if it passes the test "index >= 0". Peter makes a mistake, Paul fails to catch it, the memory is potentially corrupted and undefined behavior results. That's the PRINCIPLE the code is meant to demonstrate, which is the only purpose of this code. As an alternative I put in a boundary check based on the address the index would have us access and the addresses of the first and last members of the array. I think that's a better approach. It should match the way the array is accessed exactly and it should be completely independent of variable size, type, typecasting, and bitwise representation. As an aside, VS on the maximum warning level does not warn for the ints passed to the function that was declared with unsigned ints. Also, the compiler can't foresee that a negative value will be passed to the function because the sign of that variable is determined at run time.
#include
#include
#include//Paul writes this code
int get_available_seat_count(unsigned int *seating_counts, unsigned int row_index, unsigned int num_rows, unsigned int seats_per_row)
{
if(row_index < 0)
{
printf("row_index < 0: TRUE\n");
return -1;
}
else
printf("row_index < 0: FALSE\n");//preferable method?:
if(&seating_counts[row_index] < &seating_counts[0])
printf("Array minimum boundary violation, index is %d\n", row_index);if(&seating\_counts\[row\_index\] > &seating\_counts\[num\_rows-1\]) printf("Array maximum boundary violation, index is %d\\n", row\_index); return seats\_per\_row - seating\_counts\[row\_index\];}
//Peter writes this code
void main()
{
//row 0 is the back of the theater, row[num_rows-1] is at the stage
int num_rows = 12;
int seats_per_row = 40;
int n_available_seats;
int row_index;
unsigned int seating_counts[12];
int i;//set the current state of the theater: srand((int)time(NULL)); for(i = 0; i < num\_rows; i++) seating\_counts\[i\] = (unsigned int)rand() % seats\_per\_row; printf("Customer: are there any seats available in the third row from the stage?\\n\\n"); row\_index = 3; //rows are stored in reverse order from customer request, subtract row\_index to get offset n\_available\_sea -
Suppose I have a function that takes an array pointer and an index declared as type unsigned int and the function will access the array at that index. AFAIK "Index < 0" should never evaluate to be true regardless of what the caller passed because the unsigned type will control how the bits at the address of Index are interpreted and there will be no interpretation of a bit as an indication of sign. So implicitly an unsigned int is not capable of an access violation Below / before an array's first element given the pointer arithmetic. All that being said it does not seem at all necessary to test it. There are other reasons to use the test however. #1 it may improve readability as someone who reads the code sees that a full boundary check is being done #2 it may make the code symmetric with other code that tests upper and lower boundaries of any other type of variable #3 if the function is later modified and the type is accidentally changed to int (for example the types are changed when porting to a different machine architecture) or the code is copy and pasted to a different context where Index is not unsigned, omitting the bounds check introduces the possibility of an access violation #4 I think it's possible, perhaps likely, that an intelligent compiler will optimize it out completely, even if it didn't we're not talking about a grave loss of efficiency. So although I feel stupid writing what seems to be redundant and unnecessary code and concern myself with conciseness, for a robust application it seems worthwhile.
I haven't read all of the responses in detail, so excuse me if some of the below has already be mentioned. 1. If the function argument is defined as unsigned, a signed int will be silently transformed into an unsigned leading to potentially inappropriate behavior from the viewpoint of the caller (already mentioned). The main issue here is the silent transformation that may at best be indicated as a warning at compile time. For that reason, it might be worth considering to change the argument type to signed. Some of the big guys in C++ programming think that the use of unsigned is often not worth the hassle and may convey a false sense of security. Point in case: if you have a variable of type array index, it's true that a negative value doesn't make sense. But defining it unsigned still doesn't make it range-safe as you still need to check the upper bound. Being unsigned safes you one check, but introduces the new problem of silent signed to unsigned conversions. In the end you gain nothing. 2. The test <0 always returns true on an unsigned variable. Therefore there is no point to make it. If you want to make a two-sided bounds check on an unsigned, checking just the upper bound actually treats both, because negative values will be converted to very large positive values! 3. regarding #3: don't worry about possible future extensions! Make your code look reasonable and meaningful from the point of view of the requirements that you have now! Chances are, that any future requirement will look different than you're anticipating. Furthermore, if anything problematic of a scope you're describing here is going to happen, a lot more than your function will be affected, and it's quite possible someone will come up with some generic workaround that can cope with this problem; however, if you make your code try to anticipate that change, the generic code may not work on it, because it doesn't look as expected! Better just design your code in the most reasonable way now! 4. You can avoid a lot of these problems if you simply use std::array
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
I haven't read all of the responses in detail, so excuse me if some of the below has already be mentioned. 1. If the function argument is defined as unsigned, a signed int will be silently transformed into an unsigned leading to potentially inappropriate behavior from the viewpoint of the caller (already mentioned). The main issue here is the silent transformation that may at best be indicated as a warning at compile time. For that reason, it might be worth considering to change the argument type to signed. Some of the big guys in C++ programming think that the use of unsigned is often not worth the hassle and may convey a false sense of security. Point in case: if you have a variable of type array index, it's true that a negative value doesn't make sense. But defining it unsigned still doesn't make it range-safe as you still need to check the upper bound. Being unsigned safes you one check, but introduces the new problem of silent signed to unsigned conversions. In the end you gain nothing. 2. The test <0 always returns true on an unsigned variable. Therefore there is no point to make it. If you want to make a two-sided bounds check on an unsigned, checking just the upper bound actually treats both, because negative values will be converted to very large positive values! 3. regarding #3: don't worry about possible future extensions! Make your code look reasonable and meaningful from the point of view of the requirements that you have now! Chances are, that any future requirement will look different than you're anticipating. Furthermore, if anything problematic of a scope you're describing here is going to happen, a lot more than your function will be affected, and it's quite possible someone will come up with some generic workaround that can cope with this problem; however, if you make your code try to anticipate that change, the generic code may not work on it, because it doesn't look as expected! Better just design your code in the most reasonable way now! 4. You can avoid a lot of these problems if you simply use std::array
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
Great response! Thanks!