bin_log.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 __BIN_LOG_HH
# define __BIN_LOG_HH

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

namespace fast {

  template <typename integral_type, int N>
  struct bin_log_helper {
    enum: integral_type {
      shift = 1 << (N-1),
      pattern = ((integral_type)bin_pow_pow<integral_type, N>::value-1)
      << shift
    };
    static void step(integral_type& v, integral_type& r) {
      if (v & pattern) {
        v >>= shift;
        r |= shift;
      }
      bin_log_helper<integral_type, N-1>::step(v, r);
    }
  };

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

  template <typename integral_type>
  integral_type bin_log(integral_type v) {
    static_assert(std::is_integral<integral_type>::value,
                  "Cannot use 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.");

    integral_type r = 0;
    bin_log_helper<integral_type,
                   static_bin_log<integral_type,
                   sizeof(integral_type)<<3>::value>::step(v, r);
    return r;
  }

}

#endif