Line data    Source code

       1             : // Copyright (c) 2022-2023  Made to Order Software Corp.  All Rights Reserved
       2             : //
       3             : // https://snapwebsites.org/project/snapdev
       4             : // contact@m2osw.com
       5             : //
       6             : // This program is free software: you can redistribute it and/or modify
       7             : // it under the terms of the GNU General Public License as published by
       8             : // the Free Software Foundation, either version 3 of the License, or
       9             : // (at your option) any later version.
      10             : //
      11             : // This program is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : //
      16             : // You should have received a copy of the GNU General Public License
      17             : // along with this program.  If not, see <https://www.gnu.org/licenses/>.
      18             : #pragma once
      19             : 
      20             : /** \file
      21             :  * \brief Various mathematical functions.
      22             :  *
      23             :  * These functions are extensions to the math functions offered by the C
      24             :  * and the C++ libraries.
      25             :  */
      26             : 
      27             : // self
      28             : //
      29             : #include    <snapdev/int128_literal.h>
      30             : #include    <snapdev/limits_int128.h>
      31             : #include    <snapdev/not_reached.h>
      32             : 
      33             : 
      34             : // C
      35             : //
      36             : #include    <byteswap.h>
      37             : #include    <signal.h>
      38             : 
      39             : 
      40             : namespace snapdev
      41             : {
      42             : 
      43             : 
      44             : /** \brief Compute a power of an integer number.
      45             :  *
      46             :  * This function multiplies the specified \p value by itself \p power times.
      47             :  *
      48             :  * This is a function to compute an integer power so \p power must be an
      49             :  * integer and is generally expected to be positive. Since a negative power
      50             :  * is legal, we handle the case, but in most likelihood, the result will
      51             :  * be zero in this case.
      52             :  *
      53             :  * \note
      54             :  * If \p power is 0, the result is always 1.
      55             :  *
      56             :  * \note
      57             :  * If \p power is negative, the result is 0 unless \p value is 1 or -1 in
      58             :  * which case the result is 1 or -1.
      59             :  *
      60             :  * \todo
      61             :  * The function does not check for overflow.
      62             :  *
      63             :  * \todo
      64             :  * Once all versions use g++ v10 or more, we can remove the is_same_v<>
      65             :  * against __int128.
      66             :  *
      67             :  * \param[in] value  An integer.
      68             :  * \param[in] power  The number of times to multiply \p value by itself.
      69             :  *
      70             :  * \return The resulting "value ** power".
      71             :  */
      72             : #pragma GCC diagnostic push
      73             : #pragma GCC diagnostic ignored "-Wpedantic"
      74             : template<typename T>
      75             : constexpr std::enable_if_t<(std::is_integral_v<T> && std::is_signed_v<T>)
      76        1418 :               || std::is_same_v<T, __int128>, T> pow(T value, int power) noexcept
      77             : {
      78             :     using namespace snapdev::literals;
      79             : 
      80        1418 :     if(power == 0)
      81             :     {
      82          11 :         return static_cast<T>(1);
      83             :     }
      84        1407 :     if(power < 0)
      85             :     {
      86             :         // negative powers are similar to (1 / value ** power) which is
      87             :         // 1 or -1 if value is 1 or -1
      88             :         //
      89        1280 :         switch(value)
      90             :         {
      91         128 :         case -1:
      92         128 :             return static_cast<T>((power & 1) == 0 ? 1 : -1);
      93             : 
      94         128 :         case 1:
      95         128 :             return static_cast<T>(1);
      96             : 
      97        1024 :         default:
      98        1024 :             return static_cast<T>(0);
      99             : 
     100             :         }
     101             :         snapdev::NOT_REACHED();
     102             :     }
     103             : 
     104         127 :     T result(static_cast<T>(1));
     105             :     for(;;)
     106             :     {
     107         769 :         if((power & 1) != 0)
     108             :         {
     109         448 :             result *= value;
     110             :         }
     111         769 :         power /= 2;
     112         769 :         if(power == 0)
     113             :         {
     114         127 :             return result;
     115             :         }
     116         642 :         value *= value;
     117             :     }
     118             :     snapdev::NOT_REACHED();
     119             : }
     120             : #pragma GCC diagnostic pop
     121             : 
     122             : 
     123             : #pragma GCC diagnostic push
     124             : #pragma GCC diagnostic ignored "-Wpedantic"
     125             : template<typename T>
     126             : constexpr std::enable_if_t<(std::is_integral_v<T> && !std::is_signed_v<T>)
     127         778 :               || std::is_same_v<T, unsigned __int128>, T> pow(T value, int power)
     128             : {
     129             :     using namespace snapdev::literals;
     130             : 
     131         778 :     if(power == 0)
     132             :     {
     133          11 :         return static_cast<T>(1);
     134             :     }
     135         767 :     if(power < 0)
     136             :     {
     137             :         // negative powers are similar to (1 / value ** power) which is
     138             :         // 1 if value is 1
     139             :         //
     140         640 :         switch(value)
     141             :         {
     142         128 :         case 1:
     143         128 :             return static_cast<T>(1);
     144             : 
     145         512 :         default:
     146         512 :             return static_cast<T>(0);
     147             : 
     148             :         }
     149             :         snapdev::NOT_REACHED();
     150             :     }
     151             : 
     152         127 :     T result(static_cast<T>(1));
     153             :     for(;;)
     154             :     {
     155         769 :         if((power & 1) != 0)
     156             :         {
     157         448 :             result *= value;
     158             :         }
     159         769 :         power /= 2;
     160         769 :         if(power == 0)
     161             :         {
     162         127 :             return result;
     163             :         }
     164         642 :         value *= value;
     165             :     }
     166             :     snapdev::NOT_REACHED();
     167             : }
     168             : #pragma GCC diagnostic pop
     169             : 
     170             : 
     171             : /** \brief Add two signed numbers, return min or max on overflow.
     172             :  *
     173             :  * This function adds \p lhs to \p rhs and returns the total unless there
     174             :  * is an overflow in which case the minimum (if \p lhs and \p rhs are
     175             :  * negative) or the maximum (if \p lhs and \p rhs are positive) is returned.
     176             :  *
     177             :  * \note
     178             :  * This function is picked only if T is signed.
     179             :  *
     180             :  * \note
     181             :  * T can be `signed __int128`.
     182             :  *
     183             :  * \tparam T  The type of integer concerned. \p lhs and \p rhs must be of the
     184             :  * same type.
     185             :  * \param[in] lhs  The left handside number to add.
     186             :  * \param[in] rhs  The right handside number to add.
     187             :  *
     188             :  * \return Saturated lhs + rhs.
     189             :  */
     190             : #pragma GCC diagnostic push
     191             : #pragma GCC diagnostic ignored "-Wpedantic"
     192             : template<typename T>
     193             : std::enable_if_t<(std::is_integral_v<T> && std::is_signed_v<T>)
     194     1785495 :               || std::is_same_v<T, __int128>, T> saturated_add(T lhs, T rhs)
     195             : {
     196     1785495 :     T const result(lhs + rhs);
     197     1785495 :     T const sign(lhs ^ rhs);
     198     1785495 :     if(sign < 0)
     199             :     {
     200             :         // no possible overflow (lhs & rhs are opposite signs)
     201             :         //
     202      892697 :         return result;
     203             :     }
     204      892798 :     T const result_sign(result ^ lhs);
     205      892798 :     if(result_sign >= 0)
     206             :     {
     207             :         // overflow did not happen (result is still the same sign)
     208             :         //
     209      443898 :         return result;
     210             :     }
     211             :     return lhs < 0
     212      448900 :             ? std::numeric_limits<T>::min()
     213      448900 :             : std::numeric_limits<T>::max();
     214             : }
     215             : #pragma GCC diagnostic pop
     216             : 
     217             : 
     218             : /** \brief Add two unsigned numbers, return max on overflow.
     219             :  *
     220             :  * This function adds \p lhs to \p rhs and returns the total unless there
     221             :  * is an overflow in which case the maximum is returned.
     222             :  *
     223             :  * \note
     224             :  * This function is picked only if T is unsigned.
     225             :  *
     226             :  * \note
     227             :  * T can be `unsigned __int128`. This is currently checked explicitly
     228             :  * because older C++ standard libraries do not view __int128 as an integral
     229             :  * type (it is not included in the list of types checked).
     230             :  *
     231             :  * \tparam T  The type of integer concerned. \p lhs and \p rhs must be of the
     232             :  * same type.
     233             :  * \param[in] lhs  The left handside number to add.
     234             :  * \param[in] rhs  The right handside number to add.
     235             :  *
     236             :  * \return Saturated lhs + rhs.
     237             :  */
     238             : #pragma GCC diagnostic push
     239             : #pragma GCC diagnostic ignored "-Wpedantic"
     240             : template<typename T>
     241             : std::enable_if_t<(std::is_integral_v<T> && std::is_unsigned_v<T>)
     242     1836664 :                || std::is_same_v<T, unsigned __int128>, T> saturated_add(T lhs, T rhs)
     243             : {
     244     1836664 :     return lhs > std::numeric_limits<T>::max() - rhs
     245      916578 :             ? std::numeric_limits<T>::max()
     246     2753227 :             : lhs + rhs;
     247             : }
     248             : #pragma GCC diagnostic pop
     249             : 
     250             : 
     251             : /** \brief Subtract an unsigned number from another, return min on overflow.
     252             :  *
     253             :  * This function subtract \p rhs from \p lhs and returns the difference
     254             :  * unless there is an underflow in which case the minimum (0) is returned.
     255             :  *
     256             :  * \note
     257             :  * This function is picked only if T is unsigned.
     258             :  *
     259             :  * \note
     260             :  * T can be `unsigned __int128`. This is currently checked explicitly
     261             :  * because older C++ standard libraries do not view __int128 as an integral
     262             :  * type (it is not included in the list of types checked).
     263             :  *
     264             :  * \tparam T  The type of integer concerned. \p lhs and \p rhs must be of the
     265             :  * same type.
     266             :  * \param[in] lhs  The left handside number to subtract from.
     267             :  * \param[in] rhs  The right handside number to subtract.
     268             :  *
     269             :  * \return Saturated lhs - rhs.
     270             :  */
     271             : #pragma GCC diagnostic push
     272             : #pragma GCC diagnostic ignored "-Wpedantic"
     273             : template<typename T>
     274             : std::enable_if_t<(std::is_integral_v<T> && std::is_unsigned_v<T>)
     275     1800135 :                || std::is_same_v<T, unsigned __int128>, T> saturated_subtract(T lhs, T rhs)
     276             : {
     277     1800135 :     return lhs < rhs ? 0 : lhs - rhs;
     278             : }
     279             : #pragma GCC diagnostic pop
     280             : 
     281             : 
     282             : /** \brief Rotate an integer to the left.
     283             :  *
     284             :  * This function rotates the specified integer (\p x) to the left by
     285             :  * \p r bits.
     286             :  *
     287             :  * In most cases, if the processor you are using has a `rotl` instruction
     288             :  * (i.e. x86, amd64 do) then that instration will be used by your compiler.
     289             :  *
     290             :  * \note
     291             :  * If r is negative, rotate to the right.
     292             :  *
     293             :  * \param[in] x  The value to be rotated.
     294             :  * \param[in] r  The number of bits to rotate the value by toward the left.
     295             :  *
     296             :  * \return The value \p x rotated by \p r bits.
     297             :  */
     298             : #pragma GCC diagnostic push
     299             : #pragma GCC diagnostic ignored "-Wpedantic"
     300             : template<typename T>
     301             : constexpr T rotl(T x, int r)
     302             : {
     303             :     std::size_t const s(sizeof(T) * 8);
     304             :     r = r % s;
     305             :     if(r < 0)
     306             :     {
     307             :         return (x >> r) | (x << (s - r));
     308             :     }
     309             :     else
     310             :     {
     311             :         return (x << r) | (x >> (s - r));
     312             :     }
     313             : }
     314             : #pragma GCC diagnostic pop
     315             : 
     316             : 
     317             : /** \brief Swap all the bytes of a 128 bit number.
     318             :  *
     319             :  * This function swaps the bytes of a 128 bit number. This is similar to
     320             :  * flipping the bytes between big endian and little endian.
     321             :  *
     322             :  * \note
     323             :  * See also bwap_64(), bswap_32(), bswap_16().
     324             :  *
     325             :  * \param[in] n  The 128 bit number to byte swap.
     326             :  *
     327             :  * \return The swapped __int128 value.
     328             :  */
     329             : #pragma GCC diagnostic push
     330             : #pragma GCC diagnostic ignored "-Wpedantic"
     331             : inline unsigned __int128 bswap_128(unsigned __int128 n)
     332             : {
     333             :     unsigned __int128 m;
     334             :     std::uint64_t const * src(reinterpret_cast<std::uint64_t const *>(&n));
     335             :     std::uint64_t * dest(reinterpret_cast<std::uint64_t*>(&m));
     336             :     dest[1] = bswap_64(src[0]);
     337             :     dest[0] = bswap_64(src[1]);
     338             :     return m;
     339             : }
     340             : #pragma GCC diagnostic pop
     341             : 
     342             : 
     343             : 
     344             : } // namespace snapdev
     345             : // vim: ts=4 sw=4 et