1 /******************************************************************************
2 * ips4o/utils.hpp
3 *
4 * In-place Parallel Super Scalar Samplesort (IPS⁴o)
5 *
6 ******************************************************************************
7 * BSD 2-Clause License
8 *
9 * Copyright © 2017, Michael Axtmann <michael.axtmann@kit.edu>
10 * Copyright © 2017, Daniel Ferizovic <daniel.ferizovic@student.kit.edu>
11 * Copyright © 2017, Sascha Witt <sascha.witt@kit.edu>
12 * All rights reserved.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are met:
16 *
17 * * Redistributions of source code must retain the above copyright notice, this
18 * list of conditions and the following disclaimer.
19 *
20 * * Redistributions in binary form must reproduce the above copyright notice,
21 * this list of conditions and the following disclaimer in the documentation
22 * and/or other materials provided with the distribution.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *****************************************************************************/
35
36 #pragma once
37
38 #define IPS4O_ASSUME_NOT(c) if (c) __builtin_unreachable()
39
40 #include <limits>
41
42 #include "ips4o_fwd.hpp"
43
44 namespace ips4o {
45 namespace detail {
46
47 /**
48 * Compute the logarithm to base 2, rounded down.
49 */
log2(unsigned long n)50 inline constexpr unsigned long log2(unsigned long n) {
51 return (std::numeric_limits<unsigned long>::digits - 1 - __builtin_clzl(n));
52 }
53
54 } // namespace detail
55 } // namespace ips4o
56