2 * This file is part of the GROMACS molecular simulation package.
4 * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
5 * Copyright (c) 2001-2004, The GROMACS development team.
6 * Copyright (c) 2013,2014,2015,2016, by the GROMACS development team, led by
7 * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
8 * and including many others, as listed in the AUTHORS file in the
9 * top-level source directory and at http://www.gromacs.org.
11 * GROMACS is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public License
13 * as published by the Free Software Foundation; either version 2.1
14 * of the License, or (at your option) any later version.
16 * GROMACS is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Lesser General Public License for more details.
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with GROMACS; if not, see
23 * http://www.gnu.org/licenses, or write to the Free Software Foundation,
24 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
26 * If you want to redistribute modifications to GROMACS, please
27 * consider that scientific software is very special. Version
28 * control is crucial - bugs must be traceable. We will be happy to
29 * consider code for inclusion in the official distribution, but
30 * derived work must not be called official GROMACS. Details are found
31 * in the README & COPYING files - if they are missing, get the
32 * official version at http://www.gromacs.org.
34 * To help us fund GROMACS development, we humbly ask that you cite
35 * the research papers on the package. Check out http://www.gromacs.org.
39 * Implements simple math functions
41 * \author Erik Lindahl <erik.lindahl@gmail.com>
42 * \ingroup module_math
47 #include "functions.h"
55 #if GMX_NATIVE_WINDOWS
56 # include <intrin.h> // _BitScanReverse, _BitScanReverse64
59 #include "gromacs/utility/gmxassert.h"
65 log2I(std::uint32_t n
)
67 GMX_ASSERT(n
> 0, "The behavior of log(0) is undefined");
69 // gcc, clang. xor with sign bit should be optimized out
70 return __builtin_clz(n
) ^ 31U;
71 #elif HAVE_BITSCANREVERSE
75 _BitScanReverse(&res
, static_cast<unsigned long>(n
));
76 return static_cast<unsigned int>(res
);
79 return 31 - __cntlz4(n
);
81 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
83 static const std::array
<char, 256>
86 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
87 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
88 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
89 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
90 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
91 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
92 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
93 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
94 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
95 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
96 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
97 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
98 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
99 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
100 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
101 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
105 unsigned int tmp1
, tmp2
;
107 if ((tmp1
= n
>> 16) != 0)
109 result
= ((tmp2
= tmp1
>> 8) != 0) ? 24 + log2TableByte
[tmp2
] : 16 + log2TableByte
[tmp1
];
113 result
= ((tmp2
= n
>> 8) != 0) ? 8 + log2TableByte
[tmp2
] : log2TableByte
[n
];
121 log2I(std::uint64_t n
)
123 GMX_ASSERT(n
> 0, "The behavior of log(0) is undefined");
124 #if HAVE_BUILTIN_CLZLL
125 // gcc, icc, clang. xor with sign bit should be optimized out
126 return __builtin_clzll(n
) ^ 63U;
127 #elif HAVE_BITSCANREVERSE64
129 _BitScanReverse64(&res
, static_cast<unsigned __int64
>(n
));
130 return static_cast<unsigned int>(res
);
132 return 63 - __cntlz8(n
);
135 // No 64-bit log2 instrinsic available. Solve it by calling our internal
136 // 32-bit version (which in turn might defer to a software solution)
138 std::uint32_t high32Bits
= static_cast<std::uint32_t>(n
>>32);
139 std::uint32_t result
;
143 result
= log2I(high32Bits
) + 32;
147 result
= log2I(static_cast<std::uint32_t>(n
));
155 log2I(std::int32_t n
)
157 GMX_ASSERT(n
> 0, "The behavior of log(n) for n<=0 is undefined");
158 return log2I(static_cast<std::uint32_t>(n
));
162 log2I(std::int64_t n
)
164 GMX_ASSERT(n
> 0, "The behavior of log(n) for n<=0 is undefined");
165 return log2I(static_cast<std::uint64_t>(n
));
169 greatestCommonDivisor(std::int64_t p
,
174 std::int64_t tmp
= q
;