## C++ AMP Extras: Tile Size Checking at Compile Time

Thursday, December 6, 2012 – 3:31 PMMany tiled C++ AMP algorithms rely on the tile size being a an exact multiple of two, scan and reduce are both examples of this.

template <int TileSize, typename T> void InclusiveScanAmpTiled(array_view<T, 1> input, array_view<T, 1> output) { // ...

Ideally you would like to check at compile time that the **TileSize** template parameter is a power of two. You can do this with a combination of static_assert and a template meta-program (TMP).

```
static_assert(IsPowerOfTwoStatic<TileSize>::result,
"TileSize must be a power of 2.");
```

The **IsPowerOfTwoStatic** template program checks that the number only contains a single set bit and hence is a power of two.

static const unsigned int Bit08 = 0x80; static const unsigned int Bit16 = 0x8000; static const unsigned int Bit32 = 0x80000000; template<unsigned int N> struct IsPowerOfTwoStatic { enum { result = ((CountBitsStatic<N, Bit32>::result == 1) ? TRUE : FALSE) }; }; // While 1 is technically 2^0, for the purposes of calculating // tile size it isn't useful. template <> struct IsPowerOfTwoStatic<1> { enum { result = FALSE }; }; template<unsigned int N, unsigned int MaxBit> struct CountBitsStatic { enum { result = (IsBitSetStatic<N, MaxBit>::result + CountBitsStatic<N, (MaxBit >> 1)>::result) }; }; // Ensure that template program terminates. template<unsigned int N> struct CountBitsStatic<N, 0> { enum { result = FALSE }; }; template<unsigned int N, int MaxBit> struct IsBitSetStatic { enum { result = (N & MaxBit) ? 1 : 0 }; };

Essentially this recursively unfolds the **CountBitsStatic** bit counting function during compilation.

There are numerous other ways to count the number of set bits at runtime. I picked a template approach because I was on a meta-programming kick.

template <unsigned int MaxBit> unsigned int CountBits(unsigned int n) { return (n & 0x1) + CountBits<MaxBit-1>(n >> 1); } // template specialization to terminate the recursion when there's only one bit left template<> unsigned int CountBits<1>(unsigned int n) { return n & 0x1; } BOOL IsPowerOfTwo(unsigned int n) { return (CountBits<32>(n) == 1); };

Other approaches are discussed in Best algorithm to count the number of set bits in a 32-bit integer?

## 1 Trackback(s)

Sorry, comments for this entry are closed at this time.