1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
#include <Functions/FunctionFactory.h>
#include <Functions/FunctionBinaryArithmetic.h>
#include <libdivide-config.h>
#include <libdivide.h>
namespace DB
{
namespace ErrorCodes
{
extern const int ILLEGAL_DIVISION;
}
namespace
{
/// Optimizations for integer modulo by a constant.
template <typename A, typename B>
struct ModuloByConstantImpl
: BinaryOperation<A, B, ModuloImpl<A, B>>
{
using Op = ModuloImpl<A, B>;
using ResultType = typename Op::ResultType;
static const constexpr bool allow_fixed_string = false;
static const constexpr bool allow_string_integer = false;
template <OpCase op_case>
static void NO_INLINE process(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t size, const NullMap * right_nullmap)
{
if constexpr (op_case == OpCase::RightConstant)
{
if (right_nullmap && (*right_nullmap)[0])
return;
vectorConstant(a, *b, c, size);
}
else
{
if (right_nullmap)
{
for (size_t i = 0; i < size; ++i)
if ((*right_nullmap)[i])
c[i] = ResultType();
else
apply<op_case>(a, b, c, i);
}
else
for (size_t i = 0; i < size; ++i)
apply<op_case>(a, b, c, i);
}
}
static ResultType process(A a, B b) { return Op::template apply<ResultType>(a, b); }
static void NO_INLINE NO_SANITIZE_UNDEFINED vectorConstant(const A * __restrict src, B b, ResultType * __restrict dst, size_t size)
{
/// Modulo with too small divisor.
if (unlikely((std::is_signed_v<B> && b == -1) || b == 1))
{
for (size_t i = 0; i < size; ++i)
dst[i] = 0;
return;
}
/// Modulo with too large divisor.
if (unlikely(b > std::numeric_limits<A>::max()
|| (std::is_signed_v<A> && std::is_signed_v<B> && b < std::numeric_limits<A>::lowest())))
{
for (size_t i = 0; i < size; ++i)
dst[i] = static_cast<ResultType>(src[i]);
return;
}
if (unlikely(static_cast<A>(b) == 0))
throw Exception(ErrorCodes::ILLEGAL_DIVISION, "Division by zero");
/// Division by min negative value.
if (std::is_signed_v<B> && b == std::numeric_limits<B>::lowest())
throw Exception(ErrorCodes::ILLEGAL_DIVISION, "Division by the most negative number");
/// Modulo of division by negative number is the same as the positive number.
if (b < 0)
b = -b;
/// Here we failed to make the SSE variant from libdivide give an advantage.
if (b & (b - 1))
{
libdivide::divider<A> divider(static_cast<A>(b));
for (size_t i = 0; i < size; ++i)
{
/// NOTE: perhaps, the division semantics with the remainder of negative numbers is not preserved.
dst[i] = static_cast<ResultType>(src[i] - (src[i] / divider) * b);
}
}
else
{
// gcc libdivide doesn't work well for pow2 division
auto mask = b - 1;
for (size_t i = 0; i < size; ++i)
dst[i] = static_cast<ResultType>(src[i] & mask);
}
}
private:
template <OpCase op_case>
static inline void apply(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t i)
{
if constexpr (op_case == OpCase::Vector)
c[i] = Op::template apply<ResultType>(a[i], b[i]);
else
c[i] = Op::template apply<ResultType>(*a, b[i]);
}
};
template <typename A, typename B>
struct ModuloLegacyByConstantImpl : ModuloByConstantImpl<A, B>
{
using Op = ModuloLegacyImpl<A, B>;
};
}
/** Specializations are specified for dividing numbers of the type UInt64 and UInt32 by the numbers of the same sign.
* Can be expanded to all possible combinations, but more code is needed.
*/
namespace impl_
{
template <> struct BinaryOperationImpl<UInt64, UInt8, ModuloImpl<UInt64, UInt8>> : ModuloByConstantImpl<UInt64, UInt8> {};
template <> struct BinaryOperationImpl<UInt64, UInt16, ModuloImpl<UInt64, UInt16>> : ModuloByConstantImpl<UInt64, UInt16> {};
template <> struct BinaryOperationImpl<UInt64, UInt32, ModuloImpl<UInt64, UInt32>> : ModuloByConstantImpl<UInt64, UInt32> {};
template <> struct BinaryOperationImpl<UInt64, UInt64, ModuloImpl<UInt64, UInt64>> : ModuloByConstantImpl<UInt64, UInt64> {};
template <> struct BinaryOperationImpl<UInt32, UInt8, ModuloImpl<UInt32, UInt8>> : ModuloByConstantImpl<UInt32, UInt8> {};
template <> struct BinaryOperationImpl<UInt32, UInt16, ModuloImpl<UInt32, UInt16>> : ModuloByConstantImpl<UInt32, UInt16> {};
template <> struct BinaryOperationImpl<UInt32, UInt32, ModuloImpl<UInt32, UInt32>> : ModuloByConstantImpl<UInt32, UInt32> {};
template <> struct BinaryOperationImpl<UInt32, UInt64, ModuloImpl<UInt32, UInt64>> : ModuloByConstantImpl<UInt32, UInt64> {};
template <> struct BinaryOperationImpl<Int64, Int8, ModuloImpl<Int64, Int8>> : ModuloByConstantImpl<Int64, Int8> {};
template <> struct BinaryOperationImpl<Int64, Int16, ModuloImpl<Int64, Int16>> : ModuloByConstantImpl<Int64, Int16> {};
template <> struct BinaryOperationImpl<Int64, Int32, ModuloImpl<Int64, Int32>> : ModuloByConstantImpl<Int64, Int32> {};
template <> struct BinaryOperationImpl<Int64, Int64, ModuloImpl<Int64, Int64>> : ModuloByConstantImpl<Int64, Int64> {};
template <> struct BinaryOperationImpl<Int32, Int8, ModuloImpl<Int32, Int8>> : ModuloByConstantImpl<Int32, Int8> {};
template <> struct BinaryOperationImpl<Int32, Int16, ModuloImpl<Int32, Int16>> : ModuloByConstantImpl<Int32, Int16> {};
template <> struct BinaryOperationImpl<Int32, Int32, ModuloImpl<Int32, Int32>> : ModuloByConstantImpl<Int32, Int32> {};
template <> struct BinaryOperationImpl<Int32, Int64, ModuloImpl<Int32, Int64>> : ModuloByConstantImpl<Int32, Int64> {};
}
struct NameModulo { static constexpr auto name = "modulo"; };
using FunctionModulo = BinaryArithmeticOverloadResolver<ModuloImpl, NameModulo, false>;
REGISTER_FUNCTION(Modulo)
{
factory.registerFunction<FunctionModulo>();
factory.registerAlias("mod", "modulo", FunctionFactory::CaseInsensitive);
}
struct NameModuloLegacy { static constexpr auto name = "moduloLegacy"; };
using FunctionModuloLegacy = BinaryArithmeticOverloadResolver<ModuloLegacyImpl, NameModuloLegacy, false>;
REGISTER_FUNCTION(ModuloLegacy)
{
factory.registerFunction<FunctionModuloLegacy>();
}
struct NamePositiveModulo
{
static constexpr auto name = "positiveModulo";
};
using FunctionPositiveModulo = BinaryArithmeticOverloadResolver<PositiveModuloImpl, NamePositiveModulo, false>;
REGISTER_FUNCTION(PositiveModulo)
{
factory.registerFunction<FunctionPositiveModulo>(FunctionDocumentation
{
.description=R"(
Calculates the remainder when dividing `a` by `b`. Similar to function `modulo` except that `positiveModulo` always return non-negative number.
Returns the difference between `a` and the nearest integer not greater than `a` divisible by `b`.
In other words, the function returning the modulus (modulo) in the terms of Modular Arithmetic.
)",
.examples{{"positiveModulo", "SELECT positiveModulo(-1, 10);", ""}},
.categories{"Arithmetic"}},
FunctionFactory::CaseInsensitive);
factory.registerAlias("positive_modulo", "positiveModulo", FunctionFactory::CaseInsensitive);
/// Compatibility with Spark:
factory.registerAlias("pmod", "positiveModulo", FunctionFactory::CaseInsensitive);
}
}
|
