· Sven Rosvall
· Mixing Strings in C++
· C++ as a Safer C
· Listing 1
· Listing 2
· Listing 3
· C++ Lookup Mysteries
· Kari Rosvall
· The Rosvalls
C++ as a Safer CBy Sven Rosvall
First published in Overload Issue 59.
There are many features in C++ that can be used to enhance quality of code written with classic C design even if no object oriented techniques are used. This article describes a technique to protect against value overflow and out-of-bounds access of arrays.
This article started with a discussion about how C projects could use features in C++ to improve the quality of the code without having to do any major redesign.
Bounded Integral TypesThe built-in integral types in C and C++ are very crude. They map directly to what can be represented in hardware as bytes and words with or without signs. There is no way to say that a number can only have values in the range 1 to 100. The best you can do is to use an unsigned char which typically has a value range from 0 to 255, but this does not provide any checking for overflow.
It is easy to create an integral type that does the range checking as Pascal and Ada do. The implementation of BoundedInt in listing 1 shows how this can be done with C++ templates. It takes three parameters. The first two specify the inclusive range of allowed values. The third parameter specifies the underlying type to be used and uses a default type given by the BoundedIntTraits class.
The BoundedIntTraits class is used to find the smallest built-in type that can hold numbers of the specified range. It uses some meta-programming to figure out which type to use. The implementation of the BoundedIntTraits class is shown in listing 2.
The checking is performed here by using the assert() macro. Note that this checking only happens in debug builds and not in the release builds to reduce the overhead for this checking. Using inlining and the assert() macro removes any overhead in optimised release builds. With a good optimiser the resulting code will be identical to when built-in types are used. Alternatives to assert() can of course be used such as throwing an exception or logging a message to a file.
The BoundedInt class is only designed to work with value ranges that fit in an int. To support wider ranges all methods that take an int as a parameter must have overloaded siblings that take a long, or even long long where supported.
The operator+=() member must check that the new value is within the valid range. It also has to check that there is no overflow during addition. The method of detecting overflow is complicated as there is no support for detecting overflow for built-in types in C and C++. The method here scales down all values to manageable sizes in order to do an overflow check. Because of the scaling down, it has to keep track of carry over data from the least significant bits to work properly in edge cases where the value range are close to the value range of the underlying type.
The binary plus operators are added with all possible variations of the parameters to make sure that the assertion of operator+=() is used properly. If these were not available, any addition would convert BoundedInt objects to built-in types and the built-in addition operator would be used and no value checking would be performed.
Other operators that BoundedInt should support are not shown here as they would take too much space. The design of these operators follows the design for the plus operator.
A default constructor is available in order to mimic the behaviour of built-in types. It does not initialise the value but maintains a flag to indicate that this object does not have a defined value. This flag is checked by member functions that access or modify the value. The m_initialised member flag is surrounded by conditional pre-processing directives to avoid overhead in release builds.
The copy constructor and copy assignment operators are not defined as the compiler generated versions are appropriate.
Below are some examples from an imaginary C project implementing a lift control with a single change to use BoundedInt:
Bounded ArraysA BoundedInt object can be used as a bounds checked index into arrays. Example:
If ix for some reason is changed to an invalid value, the BoundedInt class will warn about this.
We can take this one step further by creating a class that only allows element access using numbers within the allowed range.
Note that the member data is public to allow aggregate initialisation. See below.
Whenever an element is requested using an index of any built-in integral type, that index is converted to a BoundedInt which checks that its value is within the acceptable range.
This template takes two parameters, the type of the elements in the array and a non-type template parameter to indicate the size of the array. The simple example above will work as before with only a small change to the definition of myBeers.
This array can be initialised in the same way as a built-in array:
There is no overhead in release builds for this array class. The index operator is inlined and there is no indirect pointer access to the underlying array.
Bounded PointersIn the same way as for using checked array indices we can create a smart pointer class that makes sure that it points to an element inside the array. It will have to know the base address of the array and the size to do the checking. This information is retrieved from the array class when a pointer is created.
The starting point is an example with built-in pointers:
myBeers is an array where the last elements members are cleared as a termination condition. We replace the built-in pointer p with a smart pointer:
The loop in the example above remains unchanged.
The definition of BoundedPointer is shown in listing 3. The array base address, array size and the initialised flag are kept as members only for debug builds to perform the runtime checks. To avoid this overhead in release builds the m_base, m_size and m_initialised members are surrounded with conditional pre-processing directives.
A BoundedPointer object can be constructed from built-in arrays, pointers (assuming only one element) and from user defined array types. The constructor for user defined array types takes two parameters (base address and size) and is intended to be called from conversion operators of those array classes. This conversion operator for BoundedArray looks like this:
The BoundedPointer class supports all the operations that can be used with built-in pointers. There are checks for incrementing and decrementing the pointer so that it points outside its array. As with BoundedInt there are checks to see that the pointer is initialised when it is used.
All methods are inlined to avoid any overhead in release builds.
UsageThe classes described here are designed to do the bounds checking during unit and system testing when compiled in debug mode. It is important to run as many test cases as possible that exercise all boundary conditions.
In release builds, all you have to do is make sure that the NDEBUG macro is defined, inlining is enabled and the optimise level is as high as possible. Then your code will be as efficient as if built-in types were used.
The BoundedIntTraits in listing 2 hides the chosen underlying integral type. If the ranges change in the future, there is no need to manually change the underlying type required for the wider range.
ExtensionsThis article describes the design of a class that wrap an array and adds bounds checking functionality. There are many more possible classes that can be used in this framework for different purposes. Examples include a class that manages dynamically allocated arrays.
A possible extension to the checked pointer is to keep track of if the array still exists. If the array goes out of scope or is de-allocated the pointer shall be set to an invalid state. This is straight-forward to implement but is outside the scope of this article.
This article does not discuss checked iterators for STL containers as the article was originally intended to motivate C users to adopt C++ to improve their lives. For STL there are already implementations that check validity of the iterators.
PortabilityAlthough the code in this article has been tested with some C++ compilers there are some difficulties using some existing compilers.
If your compiler does not support partial template specialisations you cannot use the traits class BoundedIntTraits. You can avoid the BoundedIntTraits class by removing it from the template parameter list of BoundedInt and replace it with int. You will miss the feature where the underlying type of BoundedInt is automatically chosen from the specified range and it will be int if a type is not specified.
ConclusionWith the strategies shown in this article it is possible to catch various out of bounds conditions during the testing phase at no cost to the released code.
An additional benefit is that the bounds given to BoundedInt and the array types document their valid ranges well.
Related ReadingSafe and efficient data types in C++ by Nicolas Burrus.
Describes classes for compile time type safety when using different integral types. It defines safe operations for a set of integral types. The integral types used here are only bounded by the number of bits used in the internal representation. The description of operations and integral promotion is interesting and can be applied to the classes in this article.
Boost Integer Library.
Boost array class in the container library.
Bounds checking pointers for GCC.