Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: // (C) Copyright Stephen Cleary 2000.
Chris@16: // (C) Copyright Ion Gaztanaga 2007-2012.
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //    http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/interprocess for documentation.
Chris@16: //
Chris@16: // This file is a slightly modified file from Boost.Pool
Chris@16: //
Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
Chris@16: #define BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
Chris@16: 
Chris@101: #ifndef BOOST_CONFIG_HPP
Chris@101: #  include <boost/config.hpp>
Chris@101: #endif
Chris@101: #
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #  pragma once
Chris@101: #endif
Chris@101: 
Chris@16: #include <climits>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace interprocess {
Chris@16: namespace ipcdetail {
Chris@16: 
Chris@16: // Greatest common divisor and least common multiple
Chris@16: 
Chris@16: //
Chris@16: // gcd is an algorithm that calculates the greatest common divisor of two
Chris@16: //  integers, using Euclid's algorithm.
Chris@16: //
Chris@16: // Pre: A > 0 && B > 0
Chris@16: // Recommended: A > B
Chris@16: template <typename Integer>
Chris@16: inline Integer gcd(Integer A, Integer B)
Chris@16: {
Chris@16:    do
Chris@16:    {
Chris@16:       const Integer tmp(B);
Chris@16:       B = A % B;
Chris@16:       A = tmp;
Chris@16:    } while (B != 0);
Chris@16: 
Chris@16:    return A;
Chris@16: }
Chris@16: 
Chris@16: //
Chris@16: // lcm is an algorithm that calculates the least common multiple of two
Chris@16: //  integers.
Chris@16: //
Chris@16: // Pre: A > 0 && B > 0
Chris@16: // Recommended: A > B
Chris@16: template <typename Integer>
Chris@16: inline Integer lcm(const Integer & A, const Integer & B)
Chris@16: {
Chris@16:    Integer ret = A;
Chris@16:    ret /= gcd(A, B);
Chris@16:    ret *= B;
Chris@16:    return ret;
Chris@16: }
Chris@16: 
Chris@16: template <typename Integer>
Chris@16: inline Integer log2_ceil(const Integer & A)
Chris@16: {
Chris@16:    Integer i = 0;
Chris@16:    Integer power_of_2 = 1;
Chris@16: 
Chris@16:    while(power_of_2 < A){
Chris@16:       power_of_2 <<= 1;
Chris@16:       ++i;
Chris@16:    }
Chris@16:    return i;
Chris@16: }
Chris@16: 
Chris@16: template <typename Integer>
Chris@16: inline Integer upper_power_of_2(const Integer & A)
Chris@16: {
Chris@16:    Integer power_of_2 = 1;
Chris@16: 
Chris@16:    while(power_of_2 < A){
Chris@16:       power_of_2 <<= 1;
Chris@16:    }
Chris@16:    return power_of_2;
Chris@16: }
Chris@16: 
Chris@16: //This function uses binary search to discover the
Chris@16: //highest set bit of the integer
Chris@16: inline std::size_t floor_log2 (std::size_t x)
Chris@16: {
Chris@16:    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
Chris@16:    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
Chris@16:    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
Chris@16: 
Chris@16:    std::size_t n = x;
Chris@16:    std::size_t log2 = 0;
Chris@16: 
Chris@16:    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
Chris@16:       std::size_t tmp = n >> shift;
Chris@16:       if (tmp)
Chris@16:          log2 += shift, n = tmp;
Chris@16:    }
Chris@16: 
Chris@16:    return log2;
Chris@16: }
Chris@16: 
Chris@16: } // namespace ipcdetail
Chris@16: } // namespace interprocess
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif