Using templates to enforce compile-time bounds checking

Discussion in 'C++' started by Dave Rahardja, Nov 20, 2005.

  1. I have the following program that uses an array of chars to simulate a bit
    set:

    ---------

    // An out-of-bounds exception
    class BoundsException {};

    template <int bits = 1>
    class Bitset
    {
    public:

    Bitset()
    {
    // Clear all the bits in the bit flag bytes
    for (int i = 0; i < charCount; ++i) {
    bitFlags = 0;
    }
    }

    // Sets a bit in the bitset.
    void set(int bit)
    {
    if (bit >= bits || bit < 0) {
    throw BoundsException();
    }
    int byteNum = bit / 8;
    int bitNum = bit % 8;
    bitFlags[byteNum] |= (1 << bitNum);
    }

    private:
    static const int charCount = (bits + 7) / 8;
    unsigned char bitFlags[charCount];
    };

    int main()
    {
    Bitset<9> bitset9;
    bitset9.set(0); // OK
    bitset9.set(-1); // BoundsException thrown

    bitset9.set(8); // OK
    bitset9.set(9); // BoundsException thrown

    return 0;
    }

    ---------

    As you can see, I'm using runtime checks to bounds-check the bit number each
    time set() is called.

    However, it turns out that set() will only receive compile-time constants, and
    never runtime computed values.

    Is there a way to perform _compile-time_ bounds checking for the indexes? A
    little template trickery maybe?

    -dr
     
    Dave Rahardja, Nov 20, 2005
    #1
    1. Advertising

  2. On Sun, 20 Nov 2005 21:22:46 GMT, Dave Rahardja <> wrote:

    >I have the following program that uses an array of chars to simulate a bit
    >set:
    >
    >---------
    >
    >// An out-of-bounds exception
    >class BoundsException {};
    >
    >template <int bits = 1>
    >class Bitset
    >{
    >public:
    >
    > Bitset()
    > {
    > // Clear all the bits in the bit flag bytes
    > for (int i = 0; i < charCount; ++i) {
    > bitFlags = 0;
    > }
    > }
    >
    > // Sets a bit in the bitset.
    > void set(int bit)
    > {
    > if (bit >= bits || bit < 0) {
    > throw BoundsException();
    > }
    > int byteNum = bit / 8;
    > int bitNum = bit % 8;
    > bitFlags[byteNum] |= (1 << bitNum);
    > }
    >
    >private:
    > static const int charCount = (bits + 7) / 8;
    > unsigned char bitFlags[charCount];
    >};
    >
    >int main()
    >{
    > Bitset<9> bitset9;
    > bitset9.set(0); // OK
    > bitset9.set(-1); // BoundsException thrown
    >
    > bitset9.set(8); // OK
    > bitset9.set(9); // BoundsException thrown
    >
    > return 0;
    >}
    >
    >---------
    >
    >As you can see, I'm using runtime checks to bounds-check the bit number each
    >time set() is called.
    >
    >However, it turns out that set() will only receive compile-time constants, and
    >never runtime computed values.
    >
    >Is there a way to perform _compile-time_ bounds checking for the indexes? A
    >little template trickery maybe?
    >
    >-dr


    First of all, there is std::bitset<size_t> as well as
    std::vector<bool>. No need to re-invent the wheel here.

    Not sure about your last question -- runtime and compile-time are two
    orthogonal concepts, actually they are somewhat diametrically opposed.
    It seems that you would like to have your cake and eat it, too. If you
    want to use runtime values to create a bitset, you have to allocate
    the memory dynamically. You could do this if you implement the storage
    as a vector and not as an array.

    BTW, there are standard exception classes in <stdexcept> you could use
    instead of your own BoundsException (std::eek:ut_of_range or
    std::invalid_argument come to mind). You could also inherit
    BoundsException from one of these, or from std::exception.

    --
    Bob Hairgrove
     
    Bob Hairgrove, Nov 20, 2005
    #2
    1. Advertising

  3. > However, it turns out that set() will only receive compile-time constants, and
    > never runtime computed values.
    >
    > Is there a way to perform _compile-time_ bounds checking for the indexes? A
    > little template trickery maybe?


    a simple compile time check could be performed with the following set()
    variant:

    template <int bits = 1>
    class Bitset
    {
    public:
    ...
    // Sets a bit in the bitset.
    template <int bit>
    void set()
    {
    static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];
    int byteNum = bit / 8;
    int bitNum = bit % 8;
    bitFlags[byteNum] |= (1 << bitNum);
    }
    ...
    }

    int main()
    {
    Bitset<9> bitset9;
    bitset9.set<0>(); // OK
    bitset9.set<-1>(); // compile time error

    bitset9.set<8>(); // OK
    bitset9.set<9>(); // compile time error
    return 0;

    }

    this is a template trick that relies on the compiler evaluating the
    array size expression at compile time, and complaining about an illegal
    size of 0.

    maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
    more fletched out variant of static assertion.

    see http://www.boost.org/doc/html/boost_staticassert.html

    -- peter
     
    peter steiner, Nov 20, 2005
    #3
  4. Dave Rahardja wrote:

    See the code I added.
    >
    > // An out-of-bounds exception
    > class BoundsException {};
    >
    > template <int bits = 1>
    > class Bitset
    > {
    > public:
    >
    > Bitset()
    > {
    > // Clear all the bits in the bit flag bytes
    > for (int i = 0; i < charCount; ++i) {
    > bitFlags = 0;
    > }
    > }
    >
    > // Sets a bit in the bitset.
    > void set(int bit)
    > {
    > if (bit >= bits || bit < 0) {
    > throw BoundsException();
    > }
    > int byteNum = bit / 8;
    > int bitNum = bit % 8;
    > bitFlags[byteNum] |= (1 << bitNum);
    > }


    template <int N>
    void set()
    {
    static_assert( (N<=bits) && (N>=0) );
    set( N );
    }

    >
    > private:
    > static const int charCount = (bits + 7) / 8;
    > unsigned char bitFlags[charCount];
    > };
    >
    > int main()
    > {
    > Bitset<9> bitset9;
    > bitset9.set(0); // OK

    bitset9.set<0>();

    > bitset9.set(-1); // BoundsException thrown

    bitset9.set<-1>();
    >
    > bitset9.set(8); // OK

    bitset9.set<8>();
    > bitset9.set(9); // BoundsException thrown

    bitset9.set<9>();
    >
    > return 0;
    > }
    >
    > ---------
    >
    > As you can see, I'm using runtime checks to bounds-check the bit number each
    > time set() is called.
    >
    > However, it turns out that set() will only receive compile-time constants, and
    > never runtime computed values.
    >
    > Is there a way to perform _compile-time_ bounds checking for the indexes? A
    > little template trickery maybe?


    You need to change the parameter and make it a template parameter. You
    can either do it by passing a special type or by passing a parameter
    specifically.

    Anything you can catch at compile time is better than catching at run-time.
     
    Gianni Mariani, Nov 20, 2005
    #4
  5. On 20 Nov 2005 14:12:32 -0800, "peter steiner" <> wrote:


    > static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];


    ....

    >this is a template trick that relies on the compiler evaluating the
    >array size expression at compile time, and complaining about an illegal
    >size of 0.


    Nice! This is just what I'm looking for.

    >maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
    >more fletched out variant of static assertion.


    Right.

    Thanks to all the other posters who suggested using the std::bitset and
    std::vector<bool> implementations, but I'm writing code for an embedded
    product for which the STL implementations are overkill. All the code I posted
    is virtually all that's needed.

    Besides, I'm still going to resort to a similar trick to make the std::
    containers provide me compile-time checks.

    -dr
     
    Dave Rahardja, Nov 21, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Casey Hawthorne
    Replies:
    21
    Views:
    903
    Roedy Green
    Jun 5, 2004
  2. Chris

    Array bounds checking

    Chris, Jul 5, 2005, in forum: Java
    Replies:
    5
    Views:
    833
  3. Casey Hawthorne
    Replies:
    16
    Views:
    1,231
  4. Jim Cook

    Macro argument bounds checking?

    Jim Cook, Sep 17, 2003, in forum: C Programming
    Replies:
    7
    Views:
    885
    Dave Thompson
    Sep 22, 2003
  5. Cliff  Martin
    Replies:
    1
    Views:
    3,084
    Larry Smith
    Jan 31, 2007
Loading...

Share This Page