1/*
2 * Copyright 2016-present 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
29namespace folly {
30
31namespace detail {
32
33template <typename T>
34inline 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
45template <typename T>
46inline 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
56template <typename T>
57inline 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
67template <typename T>
68inline 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
79template <typename T>
80inline 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
90template <typename T>
91inline 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
101template <typename N, typename D>
102using IdivResultType = typename std::enable_if<
103 std::is_integral<N>::value && std::is_integral<D>::value &&
104 !std::is_same<N, bool>::value && !std::is_same<D, bool>::value,
105 decltype(N{1} / D{1})>::type;
106} // namespace detail
107
108#if defined(__arm__) && !FOLLY_AARCH64
109constexpr auto kIntegerDivisionGivesRemainder = false;
110#else
111constexpr auto kIntegerDivisionGivesRemainder = true;
112#endif
113
114/**
115 * Returns num/denom, rounded toward negative infinity. Put another way,
116 * returns the largest integral value that is less than or equal to the
117 * exact (not rounded) fraction num/denom.
118 *
119 * The matching remainder (num - divFloor(num, denom) * denom) can be
120 * negative only if denom is negative, unlike in truncating division.
121 * Note that for unsigned types this is the same as the normal integer
122 * division operator. divFloor is equivalent to python's integral division
123 * operator //.
124 *
125 * This function undergoes the same integer promotion rules as a
126 * built-in operator, except that we don't allow bool -> int promotion.
127 * This function is undefined if denom == 0. It is also undefined if the
128 * result type T is a signed type, num is std::numeric_limits<T>::min(),
129 * and denom is equal to -1 after conversion to the result type.
130 */
131template <typename N, typename D>
132inline constexpr detail::IdivResultType<N, D> divFloor(N num, D denom) {
133 using R = decltype(num / denom);
134 return detail::IdivResultType<N, D>(
135 kIntegerDivisionGivesRemainder && std::is_signed<R>::value
136 ? detail::divFloorBranchless<R>(num, denom)
137 : detail::divFloorBranchful<R>(num, denom));
138}
139
140/**
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.
144 *
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.
150 */
151template <typename N, typename D>
152inline constexpr detail::IdivResultType<N, D> divCeil(N num, D denom) {
153 using R = decltype(num / denom);
154 return detail::IdivResultType<N, D>(
155 kIntegerDivisionGivesRemainder && std::is_signed<R>::value
156 ? detail::divCeilBranchless<R>(num, denom)
157 : detail::divCeilBranchful<R>(num, denom));
158}
159
160/**
161 * Returns num/denom, rounded toward zero. If num and denom are non-zero
162 * and have different signs (so the unrounded fraction num/denom is
163 * negative), returns divCeil, otherwise returns divFloor. If T is an
164 * unsigned type then this is always equal to divFloor.
165 *
166 * Note that this is the same as the normal integer division operator,
167 * at least since C99 (before then the rounding for negative results was
168 * implementation defined). This function is here for completeness and
169 * as a place to hang this comment.
170 *
171 * This function undergoes the same integer promotion rules as a
172 * built-in operator, except that we don't allow bool -> int promotion.
173 * This function is undefined if denom == 0. It is also undefined if the
174 * result type T is a signed type, num is std::numeric_limits<T>::min(),
175 * and denom is equal to -1 after conversion to the result type.
176 */
177template <typename N, typename D>
178inline constexpr detail::IdivResultType<N, D> divTrunc(N num, D denom) {
179 return detail::IdivResultType<N, D>(num / denom);
180}
181
182/**
183 * Returns num/denom, rounded away from zero. If num and denom are
184 * non-zero and have different signs (so the unrounded fraction num/denom
185 * is negative), returns divFloor, otherwise returns divCeil. If T is
186 * an unsigned type then this is always equal to divCeil.
187 *
188 * This function undergoes the same integer promotion rules as a
189 * built-in operator, except that we don't allow bool -> int promotion.
190 * This function is undefined if denom == 0. It is also undefined if the
191 * result type T is a signed type, num is std::numeric_limits<T>::min(),
192 * and denom is equal to -1 after conversion to the result type.
193 */
194template <typename N, typename D>
195inline constexpr detail::IdivResultType<N, D> divRoundAway(N num, D denom) {
196 using R = decltype(num / denom);
197 return detail::IdivResultType<N, D>(
198 kIntegerDivisionGivesRemainder && std::is_signed<R>::value
199 ? detail::divRoundAwayBranchless<R>(num, denom)
200 : detail::divRoundAwayBranchful<R>(num, denom));
201}
202
203} // namespace folly
204