ClickHouse

1
#include <Functions/FunctionFactory.h>
2
#include <Functions/FunctionBinaryArithmetic.h>
3

4
#include <libdivide-config.h>
5
#include <libdivide.h>
6

7

8
namespace DB
9
{
10
namespace ErrorCodes
11
{
12
    extern const int ILLEGAL_DIVISION;
13
}
14

15
namespace
16
{
17

18
/// Optimizations for integer modulo by a constant.
19

20
template <typename A, typename B>
21
struct ModuloByConstantImpl
22
    : BinaryOperation<A, B, ModuloImpl<A, B>>
23
{
24
    using Op = ModuloImpl<A, B>;
25
    using ResultType = typename Op::ResultType;
26
    static const constexpr bool allow_fixed_string = false;
27
    static const constexpr bool allow_string_integer = false;
28

29
    template <OpCase op_case>
30
    static void NO_INLINE process(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t size, const NullMap * right_nullmap)
31
    {
32
        if constexpr (op_case == OpCase::RightConstant)
33
        {
34
            if (right_nullmap && (*right_nullmap)[0])
35
                return;
36
            vectorConstant(a, *b, c, size);
37
        }
38
        else
39
        {
40
            if (right_nullmap)
41
            {
42
                for (size_t i = 0; i < size; ++i)
43
                    if ((*right_nullmap)[i])
44
                        c[i] = ResultType();
45
                    else
46
                        apply<op_case>(a, b, c, i);
47
            }
48
            else
49
                for (size_t i = 0; i < size; ++i)
50
                    apply<op_case>(a, b, c, i);
51
        }
52
    }
53

54
    static ResultType process(A a, B b) { return Op::template apply<ResultType>(a, b); }
55

56
    static void NO_INLINE NO_SANITIZE_UNDEFINED vectorConstant(const A * __restrict src, B b, ResultType * __restrict dst, size_t size)
57
    {
58
        /// Modulo with too small divisor.
59
        if (unlikely((std::is_signed_v<B> && b == -1) || b == 1))
60
        {
61
            for (size_t i = 0; i < size; ++i)
62
                dst[i] = 0;
63
            return;
64
        }
65

66
        /// Modulo with too large divisor.
67
        if (unlikely(b > std::numeric_limits<A>::max()
68
            || (std::is_signed_v<A> && std::is_signed_v<B> && b < std::numeric_limits<A>::lowest())))
69
        {
70
            for (size_t i = 0; i < size; ++i)
71
                dst[i] = static_cast<ResultType>(src[i]);
72
            return;
73
        }
74

75
        if (unlikely(static_cast<A>(b) == 0))
76
            throw Exception(ErrorCodes::ILLEGAL_DIVISION, "Division by zero");
77

78
        /// Division by min negative value.
79
        if (std::is_signed_v<B> && b == std::numeric_limits<B>::lowest())
80
            throw Exception(ErrorCodes::ILLEGAL_DIVISION, "Division by the most negative number");
81

82
        /// Modulo of division by negative number is the same as the positive number.
83
        if (b < 0)
84
            b = -b;
85

86
        /// Here we failed to make the SSE variant from libdivide give an advantage.
87

88
        if (b & (b - 1))
89
        {
90
            libdivide::divider<A> divider(static_cast<A>(b));
91
            for (size_t i = 0; i < size; ++i)
92
            {
93
                /// NOTE: perhaps, the division semantics with the remainder of negative numbers is not preserved.
94
                dst[i] = static_cast<ResultType>(src[i] - (src[i] / divider) * b);
95
            }
96
        }
97
        else
98
        {
99
            // gcc libdivide doesn't work well for pow2 division
100
            auto mask = b - 1;
101
            for (size_t i = 0; i < size; ++i)
102
                dst[i] = static_cast<ResultType>(src[i] & mask);
103
        }
104
    }
105

106
private:
107
    template <OpCase op_case>
108
    static inline void apply(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t i)
109
    {
110
        if constexpr (op_case == OpCase::Vector)
111
            c[i] = Op::template apply<ResultType>(a[i], b[i]);
112
        else
113
            c[i] = Op::template apply<ResultType>(*a, b[i]);
114
    }
115
};
116

117
template <typename A, typename B>
118
struct ModuloLegacyByConstantImpl : ModuloByConstantImpl<A, B>
119
{
120
    using Op = ModuloLegacyImpl<A, B>;
121
};
122

123
}
124

125
/** Specializations are specified for dividing numbers of the type UInt64 and UInt32 by the numbers of the same sign.
126
  * Can be expanded to all possible combinations, but more code is needed.
127
  */
128

129
namespace impl_
130
{
131
template <> struct BinaryOperationImpl<UInt64, UInt8, ModuloImpl<UInt64, UInt8>> : ModuloByConstantImpl<UInt64, UInt8> {};
132
template <> struct BinaryOperationImpl<UInt64, UInt16, ModuloImpl<UInt64, UInt16>> : ModuloByConstantImpl<UInt64, UInt16> {};
133
template <> struct BinaryOperationImpl<UInt64, UInt32, ModuloImpl<UInt64, UInt32>> : ModuloByConstantImpl<UInt64, UInt32> {};
134
template <> struct BinaryOperationImpl<UInt64, UInt64, ModuloImpl<UInt64, UInt64>> : ModuloByConstantImpl<UInt64, UInt64> {};
135

136
template <> struct BinaryOperationImpl<UInt32, UInt8, ModuloImpl<UInt32, UInt8>> : ModuloByConstantImpl<UInt32, UInt8> {};
137
template <> struct BinaryOperationImpl<UInt32, UInt16, ModuloImpl<UInt32, UInt16>> : ModuloByConstantImpl<UInt32, UInt16> {};
138
template <> struct BinaryOperationImpl<UInt32, UInt32, ModuloImpl<UInt32, UInt32>> : ModuloByConstantImpl<UInt32, UInt32> {};
139
template <> struct BinaryOperationImpl<UInt32, UInt64, ModuloImpl<UInt32, UInt64>> : ModuloByConstantImpl<UInt32, UInt64> {};
140

141
template <> struct BinaryOperationImpl<Int64, Int8, ModuloImpl<Int64, Int8>> : ModuloByConstantImpl<Int64, Int8> {};
142
template <> struct BinaryOperationImpl<Int64, Int16, ModuloImpl<Int64, Int16>> : ModuloByConstantImpl<Int64, Int16> {};
143
template <> struct BinaryOperationImpl<Int64, Int32, ModuloImpl<Int64, Int32>> : ModuloByConstantImpl<Int64, Int32> {};
144
template <> struct BinaryOperationImpl<Int64, Int64, ModuloImpl<Int64, Int64>> : ModuloByConstantImpl<Int64, Int64> {};
145

146
template <> struct BinaryOperationImpl<Int32, Int8, ModuloImpl<Int32, Int8>> : ModuloByConstantImpl<Int32, Int8> {};
147
template <> struct BinaryOperationImpl<Int32, Int16, ModuloImpl<Int32, Int16>> : ModuloByConstantImpl<Int32, Int16> {};
148
template <> struct BinaryOperationImpl<Int32, Int32, ModuloImpl<Int32, Int32>> : ModuloByConstantImpl<Int32, Int32> {};
149
template <> struct BinaryOperationImpl<Int32, Int64, ModuloImpl<Int32, Int64>> : ModuloByConstantImpl<Int32, Int64> {};
150
}
151

152
struct NameModulo { static constexpr auto name = "modulo"; };
153
using FunctionModulo = BinaryArithmeticOverloadResolver<ModuloImpl, NameModulo, false>;
154

155
REGISTER_FUNCTION(Modulo)
156
{
157
    factory.registerFunction<FunctionModulo>();
158
    factory.registerAlias("mod", "modulo", FunctionFactory::CaseInsensitive);
159
}
160

161
struct NameModuloLegacy { static constexpr auto name = "moduloLegacy"; };
162
using FunctionModuloLegacy = BinaryArithmeticOverloadResolver<ModuloLegacyImpl, NameModuloLegacy, false>;
163

164
REGISTER_FUNCTION(ModuloLegacy)
165
{
166
    factory.registerFunction<FunctionModuloLegacy>();
167
}
168

169
struct NamePositiveModulo
170
{
171
    static constexpr auto name = "positiveModulo";
172
};
173
using FunctionPositiveModulo = BinaryArithmeticOverloadResolver<PositiveModuloImpl, NamePositiveModulo, false>;
174

175
REGISTER_FUNCTION(PositiveModulo)
176
{
177
    factory.registerFunction<FunctionPositiveModulo>(FunctionDocumentation
178
        {
179
            .description = R"(
180
Calculates the remainder when dividing `a` by `b`. Similar to function `modulo` except that `positiveModulo` always return non-negative number.
181
Returns the difference between `a` and the nearest integer not greater than `a` divisible by `b`.
182
In other words, the function returning the modulus (modulo) in the terms of Modular Arithmetic.
183
        )",
184
            .examples{{"positiveModulo", "SELECT positiveModulo(-1, 10);", ""}},
185
            .categories{"Arithmetic"}},
186
        FunctionFactory::CaseInsensitive);
187

188
    factory.registerAlias("positive_modulo", "positiveModulo", FunctionFactory::CaseInsensitive);
189
    /// Compatibility with Spark:
190
    factory.registerAlias("pmod", "positiveModulo", FunctionFactory::CaseInsensitive);
191
}
192

193
}
194