arrow/util/int_util_overflow.h

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017
0018 #pragma once
0019
0020 #include <cstdint>
0021 #include <limits>
0022 #include <type_traits>
0023
0024 #include "arrow/status.h"
0025 #include "arrow/util/macros.h"
0026 #include "arrow/util/visibility.h"
0027
0028 // "safe-math.h" includes <intsafe.h> from the Windows headers.
0029 #include "arrow/util/windows_compatibility.h"
0030 #include "arrow/vendored/portable-snippets/safe-math.h"
0031 // clang-format off (avoid include reordering)
0032 #include "arrow/util/windows_fixup.h"
0033 // clang-format on
0034
0035 namespace arrow {
0036 namespace internal {
0037
0038 // Define functions AddWithOverflow, SubtractWithOverflow, MultiplyWithOverflow
0039 // with the signature `bool(T u, T v, T* out)` where T is an integer type.
0040 // On overflow, these functions return true.  Otherwise, false is returned
0041 // and `out` is updated with the result of the operation.
0042
0043 #define OP_WITH_OVERFLOW(_func_name, _psnip_op, _type, _psnip_type)           \
0044   [[nodiscard]] static inline bool _func_name(_type u, _type v, _type* out) { \
0045     return !psnip_safe_##_psnip_type##_##_psnip_op(out, u, v);                \
0046   }
0047
0048 #define OPS_WITH_OVERFLOW(_func_name, _psnip_op)            \
0049   OP_WITH_OVERFLOW(_func_name, _psnip_op, int8_t, int8)     \
0050   OP_WITH_OVERFLOW(_func_name, _psnip_op, int16_t, int16)   \
0051   OP_WITH_OVERFLOW(_func_name, _psnip_op, int32_t, int32)   \
0052   OP_WITH_OVERFLOW(_func_name, _psnip_op, int64_t, int64)   \
0053   OP_WITH_OVERFLOW(_func_name, _psnip_op, uint8_t, uint8)   \
0054   OP_WITH_OVERFLOW(_func_name, _psnip_op, uint16_t, uint16) \
0055   OP_WITH_OVERFLOW(_func_name, _psnip_op, uint32_t, uint32) \
0056   OP_WITH_OVERFLOW(_func_name, _psnip_op, uint64_t, uint64)
0057
0058 OPS_WITH_OVERFLOW(AddWithOverflow, add)
0059 OPS_WITH_OVERFLOW(SubtractWithOverflow, sub)
0060 OPS_WITH_OVERFLOW(MultiplyWithOverflow, mul)
0061 OPS_WITH_OVERFLOW(DivideWithOverflow, div)
0062
0063 #undef OP_WITH_OVERFLOW
0064 #undef OPS_WITH_OVERFLOW
0065
0066 // Define function NegateWithOverflow with the signature `bool(T u, T* out)`
0067 // where T is a signed integer type.  On overflow, these functions return true.
0068 // Otherwise, false is returned and `out` is updated with the result of the
0069 // operation.
0070
0071 #define UNARY_OP_WITH_OVERFLOW(_func_name, _psnip_op, _type, _psnip_type) \
0072   [[nodiscard]] static inline bool _func_name(_type u, _type* out) {      \
0073     return !psnip_safe_##_psnip_type##_##_psnip_op(out, u);               \
0074   }
0075
0076 #define SIGNED_UNARY_OPS_WITH_OVERFLOW(_func_name, _psnip_op)   \
0077   UNARY_OP_WITH_OVERFLOW(_func_name, _psnip_op, int8_t, int8)   \
0078   UNARY_OP_WITH_OVERFLOW(_func_name, _psnip_op, int16_t, int16) \
0079   UNARY_OP_WITH_OVERFLOW(_func_name, _psnip_op, int32_t, int32) \
0080   UNARY_OP_WITH_OVERFLOW(_func_name, _psnip_op, int64_t, int64)
0081
0082 SIGNED_UNARY_OPS_WITH_OVERFLOW(NegateWithOverflow, neg)
0083
0084 #undef UNARY_OP_WITH_OVERFLOW
0085 #undef SIGNED_UNARY_OPS_WITH_OVERFLOW
0086
0087 /// Signed addition with well-defined behaviour on overflow (as unsigned)
0088 template <typename SignedInt>
0089 SignedInt SafeSignedAdd(SignedInt u, SignedInt v) {
0090   using UnsignedInt = typename std::make_unsigned<SignedInt>::type;
0091   return static_cast<SignedInt>(static_cast<UnsignedInt>(u) +
0092                                 static_cast<UnsignedInt>(v));
0093 }
0094
0095 /// Signed subtraction with well-defined behaviour on overflow (as unsigned)
0096 template <typename SignedInt>
0097 SignedInt SafeSignedSubtract(SignedInt u, SignedInt v) {
0098   using UnsignedInt = typename std::make_unsigned<SignedInt>::type;
0099   return static_cast<SignedInt>(static_cast<UnsignedInt>(u) -
0100                                 static_cast<UnsignedInt>(v));
0101 }
0102
0103 /// Signed negation with well-defined behaviour on overflow (as unsigned)
0104 template <typename SignedInt>
0105 SignedInt SafeSignedNegate(SignedInt u) {
0106   using UnsignedInt = typename std::make_unsigned<SignedInt>::type;
0107   return static_cast<SignedInt>(~static_cast<UnsignedInt>(u) + 1);
0108 }
0109
0110 /// Signed left shift with well-defined behaviour on negative numbers or overflow
0111 template <typename SignedInt, typename Shift>
0112 SignedInt SafeLeftShift(SignedInt u, Shift shift) {
0113   using UnsignedInt = typename std::make_unsigned<SignedInt>::type;
0114   return static_cast<SignedInt>(static_cast<UnsignedInt>(u) << shift);
0115 }
0116
0117 }  // namespace internal
0118 }  // namespace arrow