invert_bits.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
#ifndef __INVERT_BITS_HH
# define __INVERT_BITS_HH

# include "bin_pow.hh"
# include "static_bin_log.hh"
# include <type_traits>

namespace fast {
  template <typename integral_type, int size, int width, integral_type pattern>
  struct repeat_pattern_recurse {
    enum: integral_type {
      value = (integral_type)repeat_pattern_recurse<integral_type,
                                                    size,
                                                    2*width,
                                                    pattern |
                                                    (pattern << width)>::value
    };
  };

  template <typename integral_type, int size, integral_type pattern>
  struct repeat_pattern_recurse<integral_type, size, size, pattern> {
    enum: integral_type { value = pattern };
  };

  template <typename integral_type, int width, integral_type pattern>
  struct repeat_pattern:
    public repeat_pattern_recurse<integral_type, sizeof(integral_type)<<3,
                                  width, pattern>
  {};

  template <typename integral_type, int N>
  struct inversion_helper {
    enum: integral_type
      { shift = 1 << (N-1),
        smallpattern = ((integral_type)bin_pow_pow<integral_type, N>::value-1)
        << shift,
        pattern = repeat_pattern<integral_type, 2*shift, smallpattern>::value
      };
    static void step(integral_type& v) {
      integral_type l = v << shift;
      v >>= shift;
      v = (l & pattern)
        | (v & (pattern >> shift));
      inversion_helper<integral_type, N-1>::step(v);
    }
  };

  template <typename integral_type>
  struct inversion_helper<integral_type, 0> {
    static void step(integral_type&) {}
  };

  template <typename integral_type>
  inline void invert_bits(integral_type& v) {
    static_assert(std::is_integral<integral_type>::value,
                  "Cannot invert bits on non integral types.");
    static_assert(sizeof(integral_type) ==
                  1<< static_bin_log<integral_type,
                                     sizeof(integral_type)>::value,
                  "Type size is not a power of two.");

    inversion_helper<integral_type,
                     static_bin_log<integral_type,
                                    sizeof(integral_type)<<3>::value>::step(v);
  }
}

#endif