folly/Math.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * Some arithmetic functions that seem to pop up or get hand-rolled a lot.
  19  * So far they are all focused on integer division.
  20  */
  21
  22 #pragma once
  23
  24 #include <stdint.h>
  25
  26 #include <limits>
  27 #include <type_traits>
  28
  29 namespace folly {
  30
  31 namespace detail {
  32
  33 template <typename T>
  34 inline constexpr T divFloorBranchless(T num, T denom) {
  35   // floor != trunc when the answer isn't exact and truncation went the
  36   // wrong way (truncation went toward positive infinity).  That happens
  37   // when the true answer is negative, which happens when num and denom
  38   // have different signs.  The following code compiles branch-free on
  39   // many platforms.
  40   return (num / denom) +
  41       ((num % denom) != 0 ? 1 : 0) *
  42       (std::is_signed<T>::value && (num ^ denom) < 0 ? -1 : 0);
  43 }
  44
  45 template <typename T>
  46 inline constexpr T divFloorBranchful(T num, T denom) {
  47   // First case handles negative result by preconditioning numerator.
  48   // Preconditioning decreases the magnitude of the numerator, which is
  49   // itself sign-dependent.  Second case handles zero or positive rational
  50   // result, where trunc and floor are the same.
  51   return std::is_signed<T>::value && (num ^ denom) < 0 && num != 0
  52       ? (num + (num > 0 ? -1 : 1)) / denom - 1
  53       : num / denom;
  54 }
  55
  56 template <typename T>
  57 inline constexpr T divCeilBranchless(T num, T denom) {
  58   // ceil != trunc when the answer isn't exact (truncation occurred)
  59   // and truncation went away from positive infinity.  That happens when
  60   // the true answer is positive, which happens when num and denom have
  61   // the same sign.
  62   return (num / denom) +
  63       ((num % denom) != 0 ? 1 : 0) *
  64       (std::is_signed<T>::value && (num ^ denom) < 0 ? 0 : 1);
  65 }
  66
  67 template <typename T>
  68 inline constexpr T divCeilBranchful(T num, T denom) {
  69   // First case handles negative or zero rational result, where trunc and ceil
  70   // are the same.
  71   // Second case handles positive result by preconditioning numerator.
  72   // Preconditioning decreases the magnitude of the numerator, which is
  73   // itself sign-dependent.
  74   return (std::is_signed<T>::value && (num ^ denom) < 0) || num == 0
  75       ? num / denom
  76       : (num + (num > 0 ? -1 : 1)) / denom + 1;
  77 }
  78
  79 template <typename T>
  80 inline constexpr T divRoundAwayBranchless(T num, T denom) {
  81   // away != trunc whenever truncation actually occurred, which is when
  82   // there is a non-zero remainder.  If the unrounded result is negative
  83   // then fixup moves it toward negative infinity.  If the unrounded
  84   // result is positive then adjustment makes it larger.
  85   return (num / denom) +
  86       ((num % denom) != 0 ? 1 : 0) *
  87       (std::is_signed<T>::value && (num ^ denom) < 0 ? -1 : 1);
  88 }
  89
  90 template <typename T>
  91 inline constexpr T divRoundAwayBranchful(T num, T denom) {
  92   // First case of second ternary operator handles negative rational
  93   // result, which is the same as divFloor.  Second case of second ternary
  94   // operator handles positive result, which is the same as divCeil.
  95   // Zero case is separated for simplicity.
  96   return num == 0 ? 0
  97                   : (num + (num > 0 ? -1 : 1)) / denom +
  98           (std::is_signed<T>::value && (num ^ denom) < 0 ? -1 : 1);
  99 }
 100
 101 template <typename N, typename D>
 102 using IdivResultType = typename std::enable_if<
 103     std::is_integral<N>::value && std::is_integral<D>::value &&
 104         !std::is_same<N, bool>::value &&
 105         !std::is_same<D, bool>::value,
 106     decltype(N{1} / D{1})>::type;
 107 } // namespace detail
 108
 109 #if defined(__arm__) && !FOLLY_AARCH64
 110 constexpr auto kIntegerDivisionGivesRemainder = false;
 111 #else
 112 constexpr auto kIntegerDivisionGivesRemainder = true;
 113 #endif
 114
 115 /**
 116  * Returns num/denom, rounded toward negative infinity.  Put another way,
 117  * returns the largest integral value that is less than or equal to the
 118  * exact (not rounded) fraction num/denom.
 119  *
 120  * The matching remainder (num - divFloor(num, denom) * denom) can be
 121  * negative only if denom is negative, unlike in truncating division.
 122  * Note that for unsigned types this is the same as the normal integer
 123  * division operator.  divFloor is equivalent to python's integral division
 124  * operator //.
 125  *
 126  * This function undergoes the same integer promotion rules as a
 127  * built-in operator, except that we don't allow bool -> int promotion.
 128  * This function is undefined if denom == 0.  It is also undefined if the
 129  * result type T is a signed type, num is std::numeric_limits<T>::min(),
 130  * and denom is equal to -1 after conversion to the result type.
 131  */
 132 template <typename N, typename D>
 133 inline constexpr detail::IdivResultType<N, D> divFloor(N num, D denom) {
 134   using R = decltype(num / denom);
 135   return detail::IdivResultType<N, D>(
 136       kIntegerDivisionGivesRemainder && std::is_signed<R>::value
 137           ? detail::divFloorBranchless<R>(num, denom)
 138           : detail::divFloorBranchful<R>(num, denom));
 139 }
 140
 141 /**
 142  * Returns num/denom, rounded toward positive infinity.  Put another way,
 143  * returns the smallest integral value that is greater than or equal to
 144  * the exact (not rounded) fraction num/denom.
 145  *
 146  * This function undergoes the same integer promotion rules as a
 147  * built-in operator, except that we don't allow bool -> int promotion.
 148  * This function is undefined if denom == 0.  It is also undefined if the
 149  * result type T is a signed type, num is std::numeric_limits<T>::min(),
 150  * and denom is equal to -1 after conversion to the result type.
 151  */
 152 template <typename N, typename D>
 153 inline constexpr detail::IdivResultType<N, D> divCeil(N num, D denom) {
 154   using R = decltype(num / denom);
 155   return detail::IdivResultType<N, D>(
 156       kIntegerDivisionGivesRemainder && std::is_signed<R>::value
 157           ? detail::divCeilBranchless<R>(num, denom)
 158           : detail::divCeilBranchful<R>(num, denom));
 159 }
 160
 161 /**
 162  * Returns num/denom, rounded toward zero.  If num and denom are non-zero
 163  * and have different signs (so the unrounded fraction num/denom is
 164  * negative), returns divCeil, otherwise returns divFloor.  If T is an
 165  * unsigned type then this is always equal to divFloor.
 166  *
 167  * Note that this is the same as the normal integer division operator,
 168  * at least since C99 (before then the rounding for negative results was
 169  * implementation defined).  This function is here for completeness and
 170  * as a place to hang this comment.
 171  *
 172  * This function undergoes the same integer promotion rules as a
 173  * built-in operator, except that we don't allow bool -> int promotion.
 174  * This function is undefined if denom == 0.  It is also undefined if the
 175  * result type T is a signed type, num is std::numeric_limits<T>::min(),
 176  * and denom is equal to -1 after conversion to the result type.
 177  */
 178 template <typename N, typename D>
 179 inline constexpr detail::IdivResultType<N, D> divTrunc(N num, D denom) {
 180   return detail::IdivResultType<N, D>(num / denom);
 181 }
 182
 183 /**
 184  * Returns num/denom, rounded away from zero.  If num and denom are
 185  * non-zero and have different signs (so the unrounded fraction num/denom
 186  * is negative), returns divFloor, otherwise returns divCeil.  If T is
 187  * an unsigned type then this is always equal to divCeil.
 188  *
 189  * This function undergoes the same integer promotion rules as a
 190  * built-in operator, except that we don't allow bool -> int promotion.
 191  * This function is undefined if denom == 0.  It is also undefined if the
 192  * result type T is a signed type, num is std::numeric_limits<T>::min(),
 193  * and denom is equal to -1 after conversion to the result type.
 194  */
 195 template <typename N, typename D>
 196 inline constexpr detail::IdivResultType<N, D> divRoundAway(N num, D denom) {
 197   using R = decltype(num / denom);
 198   return detail::IdivResultType<N, D>(
 199       kIntegerDivisionGivesRemainder && std::is_signed<R>::value
 200           ? detail::divRoundAwayBranchless<R>(num, denom)
 201           : detail::divRoundAwayBranchful<R>(num, denom));
 202 }
 203
 204 } // namespace folly