src/gromacs/math/functions.cpp

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   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.
  10  *
  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.
  15  *
  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.
  20  *
  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.
  25  *
  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.
  33  *
  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.
  36  */
  37 /*! \internal \file
  38  * \brief
  39  * Implements simple math functions
  40  *
  41  * \author Erik Lindahl <erik.lindahl@gmail.com>
  42  * \ingroup module_math
  43  */
  44
  45 #include "gmxpre.h"
  46
  47 #include "functions.h"
  48
  49 #include "config.h"
  50
  51 #include <cstdint>
  52
  53 #include <array>
  54
  55 #if GMX_NATIVE_WINDOWS
  56 #    include <intrin.h> // _BitScanReverse, _BitScanReverse64
  57 #endif
  58
  59 #include "gromacs/utility/gmxassert.h"
  60
  61 namespace gmx
  62 {
  63
  64 unsigned int
  65 log2I(std::uint32_t n)
  66 {
  67     GMX_ASSERT(n > 0, "The behavior of log(0) is undefined");
  68 #if HAVE_BUILTIN_CLZ
  69     // gcc, clang. xor with sign bit should be optimized out
  70     return __builtin_clz(n) ^ 31U;
  71 #elif HAVE_BITSCANREVERSE
  72     // icc, MSVC
  73     {
  74         unsigned long res;
  75         _BitScanReverse(&res, static_cast<unsigned long>(n));
  76         return static_cast<unsigned int>(res);
  77     }
  78 #elif HAVE_CNTLZ4
  79     return 31 - __cntlz4(n);
  80 #else
  81     // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
  82
  83     static const std::array<char, 256>
  84     log2TableByte =
  85     {{
  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
 102      }};
 103
 104     unsigned int result;
 105     unsigned int tmp1, tmp2;
 106
 107     if ((tmp1 = n >> 16) != 0)
 108     {
 109         result = ((tmp2 = tmp1 >> 8) != 0) ? 24 + log2TableByte[tmp2] : 16 + log2TableByte[tmp1];
 110     }
 111     else
 112     {
 113         result = ((tmp2 = n >> 8) != 0) ? 8 + log2TableByte[tmp2] : log2TableByte[n];
 114     }
 115     return result;
 116 #endif
 117 }
 118
 119
 120 unsigned int
 121 log2I(std::uint64_t n)
 122 {
 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
 128     unsigned long res;
 129     _BitScanReverse64(&res, static_cast<unsigned __int64>(n));
 130     return static_cast<unsigned int>(res);
 131 #elif HAVE_CNTLZ8
 132     return 63 - __cntlz8(n);
 133 #else
 134
 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)
 137
 138     std::uint32_t high32Bits = static_cast<std::uint32_t>(n>>32);
 139     std::uint32_t result;
 140
 141     if (high32Bits)
 142     {
 143         result = log2I(high32Bits) + 32;
 144     }
 145     else
 146     {
 147         result = log2I(static_cast<std::uint32_t>(n));
 148     }
 149
 150     return result;
 151 #endif
 152 }
 153
 154 unsigned int
 155 log2I(std::int32_t n)
 156 {
 157     GMX_ASSERT(n > 0, "The behavior of log(n) for n<=0 is undefined");
 158     return log2I(static_cast<std::uint32_t>(n));
 159 }
 160
 161 unsigned int
 162 log2I(std::int64_t n)
 163 {
 164     GMX_ASSERT(n > 0, "The behavior of log(n) for n<=0 is undefined");
 165     return log2I(static_cast<std::uint64_t>(n));
 166 }
 167
 168 std::int64_t
 169 greatestCommonDivisor(std::int64_t   p,
 170                       std::int64_t   q)
 171 {
 172     while (q != 0)
 173     {
 174         std::int64_t tmp = q;
 175         q                = p % q;
 176         p                = tmp;
 177     }
 178     return p;
 179 }
 180
 181 } // namespace gmx