1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Stephen Cleary 2000.
4 // (C) Copyright Ion Gaztanaga 2007-2012.
5 //
6 // Distributed under the Boost Software License, Version 1.0.
7 //    (See accompanying file LICENSE_1_0.txt or copy at
8 //    http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // See http://www.boost.org/libs/interprocess for documentation.
11 //
12 // This file is a slightly modified file from Boost.Pool
13 //
14 //////////////////////////////////////////////////////////////////////////////
15 
16 #ifndef BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
17 #define BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
18 
19 #ifndef BOOST_CONFIG_HPP
20 #  include <boost/config.hpp>
21 #endif
22 #
23 #if defined(BOOST_HAS_PRAGMA_ONCE)
24 #  pragma once
25 #endif
26 
27 #include <climits>
28 #include <boost/static_assert.hpp>
29 
30 namespace boost {
31 namespace interprocess {
32 namespace ipcdetail {
33 
34 // Greatest common divisor and least common multiple
35 
36 //
37 // gcd is an algorithm that calculates the greatest common divisor of two
38 //  integers, using Euclid's algorithm.
39 //
40 // Pre: A > 0 && B > 0
41 // Recommended: A > B
42 template <typename Integer>
gcd(Integer A,Integer B)43 inline Integer gcd(Integer A, Integer B)
44 {
45    do
46    {
47       const Integer tmp(B);
48       B = A % B;
49       A = tmp;
50    } while (B != 0);
51 
52    return A;
53 }
54 
55 //
56 // lcm is an algorithm that calculates the least common multiple of two
57 //  integers.
58 //
59 // Pre: A > 0 && B > 0
60 // Recommended: A > B
61 template <typename Integer>
lcm(const Integer & A,const Integer & B)62 inline Integer lcm(const Integer & A, const Integer & B)
63 {
64    Integer ret = A;
65    ret /= gcd(A, B);
66    ret *= B;
67    return ret;
68 }
69 
70 template <typename Integer>
log2_ceil(const Integer & A)71 inline Integer log2_ceil(const Integer & A)
72 {
73    Integer i = 0;
74    Integer power_of_2 = 1;
75 
76    while(power_of_2 < A){
77       power_of_2 <<= 1;
78       ++i;
79    }
80    return i;
81 }
82 
83 template <typename Integer>
upper_power_of_2(const Integer & A)84 inline Integer upper_power_of_2(const Integer & A)
85 {
86    Integer power_of_2 = 1;
87 
88    while(power_of_2 < A){
89       power_of_2 <<= 1;
90    }
91    return power_of_2;
92 }
93 
94 //This function uses binary search to discover the
95 //highest set bit of the integer
floor_log2(std::size_t x)96 inline std::size_t floor_log2 (std::size_t x)
97 {
98    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
99    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
100    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
101 
102    std::size_t n = x;
103    std::size_t log2 = 0;
104 
105    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
106       std::size_t tmp = n >> shift;
107       if (tmp)
108          log2 += shift, n = tmp;
109    }
110 
111    return log2;
112 }
113 
114 } // namespace ipcdetail
115 } // namespace interprocess
116 } // namespace boost
117 
118 #endif
119