2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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.
27 #include <type_traits>
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
40 return (num / denom) +
41 ((num % denom) != 0 ? 1 : 0) *
42 (std::is_signed<T>::value && (num ^ denom) < 0 ? -1 : 0);
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
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
62 return (num / denom) +
63 ((num % denom) != 0 ? 1 : 0) *
64 (std::is_signed<T>::value && (num ^ denom) < 0 ? 0 : 1);
68 inline constexpr T divCeilBranchful(T num, T denom) {
69 // First case handles negative or zero rational result, where trunc and ceil
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
76 : (num + (num > 0 ? -1 : 1)) / denom + 1;
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);
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.
97 : (num + (num > 0 ? -1 : 1)) / denom +
98 (std::is_signed<T>::value && (num ^ denom) < 0 ? -1 : 1);
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;
109 #if defined(__arm__) && !FOLLY_A64
110 constexpr auto kIntegerDivisionGivesRemainder = false;
112 constexpr auto kIntegerDivisionGivesRemainder = true;
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.
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
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.
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 kIntegerDivisionGivesRemainder && std::is_signed<R>::value
136 ? detail::divFloorBranchless<R>(num, denom)
137 : detail::divFloorBranchful<R>(num, denom);
141 * Returns num/denom, rounded toward positive infinity. Put another way,
142 * returns the smallest integral value that is greater than or equal to
143 * the exact (not rounded) fraction num/denom.
145 * This function undergoes the same integer promotion rules as a
146 * built-in operator, except that we don't allow bool -> int promotion.
147 * This function is undefined if denom == 0. It is also undefined if the
148 * result type T is a signed type, num is std::numeric_limits<T>::min(),
149 * and denom is equal to -1 after conversion to the result type.
151 template <typename N, typename D>
152 inline constexpr detail::IdivResultType<N, D> divCeil(N num, D denom) {
153 using R = decltype(num / denom);
154 return kIntegerDivisionGivesRemainder && std::is_signed<R>::value
155 ? detail::divCeilBranchless<R>(num, denom)
156 : detail::divCeilBranchful<R>(num, denom);
160 * Returns num/denom, rounded toward zero. If num and denom are non-zero
161 * and have different signs (so the unrounded fraction num/denom is
162 * negative), returns divCeil, otherwise returns divFloor. If T is an
163 * unsigned type then this is always equal to divFloor.
165 * Note that this is the same as the normal integer division operator,
166 * at least since C99 (before then the rounding for negative results was
167 * implementation defined). This function is here for completeness and
168 * as a place to hang this comment.
170 * This function undergoes the same integer promotion rules as a
171 * built-in operator, except that we don't allow bool -> int promotion.
172 * This function is undefined if denom == 0. It is also undefined if the
173 * result type T is a signed type, num is std::numeric_limits<T>::min(),
174 * and denom is equal to -1 after conversion to the result type.
176 template <typename N, typename D>
177 inline constexpr detail::IdivResultType<N, D> divTrunc(N num, D denom) {
182 * Returns num/denom, rounded away from zero. If num and denom are
183 * non-zero and have different signs (so the unrounded fraction num/denom
184 * is negative), returns divFloor, otherwise returns divCeil. If T is
185 * an unsigned type then this is always equal to divCeil.
187 * This function undergoes the same integer promotion rules as a
188 * built-in operator, except that we don't allow bool -> int promotion.
189 * This function is undefined if denom == 0. It is also undefined if the
190 * result type T is a signed type, num is std::numeric_limits<T>::min(),
191 * and denom is equal to -1 after conversion to the result type.
193 template <typename N, typename D>
194 inline constexpr detail::IdivResultType<N, D> divRoundAway(N num, D denom) {
195 using R = decltype(num / denom);
196 return kIntegerDivisionGivesRemainder && std::is_signed<R>::value
197 ? detail::divRoundAwayBranchless<R>(num, denom)
198 : detail::divRoundAwayBranchful<R>(num, denom);