base/numerics/safe_conversions_impl.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
   6 #define BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
   7
   8 #include <limits>
   9
  10 #include "base/template_util.h"
  11
  12 namespace base {
  13 namespace internal {
  14
  15 // The std library doesn't provide a binary max_exponent for integers, however
  16 // we can compute one by adding one to the number of non-sign bits. This allows
  17 // for accurate range comparisons between floating point and integer types.
  18 template <typename NumericType>
  19 struct MaxExponent {
  20   static const int value = std::numeric_limits<NumericType>::is_iec559
  21                                ? std::numeric_limits<NumericType>::max_exponent
  22                                : (sizeof(NumericType) * 8 + 1 -
  23                                   std::numeric_limits<NumericType>::is_signed);
  24 };
  25
  26 enum IntegerRepresentation {
  27   INTEGER_REPRESENTATION_UNSIGNED,
  28   INTEGER_REPRESENTATION_SIGNED
  29 };
  30
  31 // A range for a given nunmeric Src type is contained for a given numeric Dst
  32 // type if both numeric_limits<Src>::max() <= numeric_limits<Dst>::max() and
  33 // numeric_limits<Src>::min() >= numeric_limits<Dst>::min() are true.
  34 // We implement this as template specializations rather than simple static
  35 // comparisons to ensure type correctness in our comparisons.
  36 enum NumericRangeRepresentation {
  37   NUMERIC_RANGE_NOT_CONTAINED,
  38   NUMERIC_RANGE_CONTAINED
  39 };
  40
  41 // Helper templates to statically determine if our destination type can contain
  42 // maximum and minimum values represented by the source type.
  43
  44 template <
  45     typename Dst,
  46     typename Src,
  47     IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed
  48                                             ? INTEGER_REPRESENTATION_SIGNED
  49                                             : INTEGER_REPRESENTATION_UNSIGNED,
  50     IntegerRepresentation SrcSign =
  51         std::numeric_limits<Src>::is_signed
  52             ? INTEGER_REPRESENTATION_SIGNED
  53             : INTEGER_REPRESENTATION_UNSIGNED >
  54 struct StaticDstRangeRelationToSrcRange;
  55
  56 // Same sign: Dst is guaranteed to contain Src only if its range is equal or
  57 // larger.
  58 template <typename Dst, typename Src, IntegerRepresentation Sign>
  59 struct StaticDstRangeRelationToSrcRange<Dst, Src, Sign, Sign> {
  60   static const NumericRangeRepresentation value =
  61       MaxExponent<Dst>::value >= MaxExponent<Src>::value
  62           ? NUMERIC_RANGE_CONTAINED
  63           : NUMERIC_RANGE_NOT_CONTAINED;
  64 };
  65
  66 // Unsigned to signed: Dst is guaranteed to contain source only if its range is
  67 // larger.
  68 template <typename Dst, typename Src>
  69 struct StaticDstRangeRelationToSrcRange<Dst,
  70                                         Src,
  71                                         INTEGER_REPRESENTATION_SIGNED,
  72                                         INTEGER_REPRESENTATION_UNSIGNED> {
  73   static const NumericRangeRepresentation value =
  74       MaxExponent<Dst>::value > MaxExponent<Src>::value
  75           ? NUMERIC_RANGE_CONTAINED
  76           : NUMERIC_RANGE_NOT_CONTAINED;
  77 };
  78
  79 // Signed to unsigned: Dst cannot be statically determined to contain Src.
  80 template <typename Dst, typename Src>
  81 struct StaticDstRangeRelationToSrcRange<Dst,
  82                                         Src,
  83                                         INTEGER_REPRESENTATION_UNSIGNED,
  84                                         INTEGER_REPRESENTATION_SIGNED> {
  85   static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED;
  86 };
  87
  88 enum RangeConstraint {
  89   RANGE_VALID = 0x0,  // Value can be represented by the destination type.
  90   RANGE_UNDERFLOW = 0x1,  // Value would overflow.
  91   RANGE_OVERFLOW = 0x2,  // Value would underflow.
  92   RANGE_INVALID = RANGE_UNDERFLOW | RANGE_OVERFLOW  // Invalid (i.e. NaN).
  93 };
  94
  95 // Helper function for coercing an int back to a RangeContraint.
  96 inline RangeConstraint GetRangeConstraint(int integer_range_constraint) {
  97   DCHECK(integer_range_constraint >= RANGE_VALID &&
  98          integer_range_constraint <= RANGE_INVALID);
  99   return static_cast<RangeConstraint>(integer_range_constraint);
 100 }
 101
 102 // This function creates a RangeConstraint from an upper and lower bound
 103 // check by taking advantage of the fact that only NaN can be out of range in
 104 // both directions at once.
 105 inline RangeConstraint GetRangeConstraint(bool is_in_upper_bound,
 106                                    bool is_in_lower_bound) {
 107   return GetRangeConstraint((is_in_upper_bound ? 0 : RANGE_OVERFLOW) |
 108                             (is_in_lower_bound ? 0 : RANGE_UNDERFLOW));
 109 }
 110
 111 // The following helper template addresses a corner case in range checks for
 112 // conversion from a floating-point type to an integral type of smaller range
 113 // but larger precision (e.g. float -> unsigned). The problem is as follows:
 114 //   1. Integral maximum is always one less than a power of two, so it must be
 115 //      truncated to fit the mantissa of the floating point. The direction of
 116 //      rounding is implementation defined, but by default it's always IEEE
 117 //      floats, which round to nearest and thus result in a value of larger
 118 //      magnitude than the integral value.
 119 //      Example: float f = UINT_MAX; // f is 4294967296f but UINT_MAX
 120 //                                   // is 4294967295u.
 121 //   2. If the floating point value is equal to the promoted integral maximum
 122 //      value, a range check will erroneously pass.
 123 //      Example: (4294967296f <= 4294967295u) // This is true due to a precision
 124 //                                            // loss in rounding up to float.
 125 //   3. When the floating point value is then converted to an integral, the
 126 //      resulting value is out of range for the target integral type and
 127 //      thus is implementation defined.
 128 //      Example: unsigned u = (float)INT_MAX; // u will typically overflow to 0.
 129 // To fix this bug we manually truncate the maximum value when the destination
 130 // type is an integral of larger precision than the source floating-point type,
 131 // such that the resulting maximum is represented exactly as a floating point.
 132 template <typename Dst, typename Src>
 133 struct NarrowingRange {
 134   typedef typename std::numeric_limits<Src> SrcLimits;
 135   typedef typename std::numeric_limits<Dst> DstLimits;
 136
 137   static Dst max() {
 138     // The following logic avoids warnings where the max function is
 139     // instantiated with invalid values for a bit shift (even though
 140     // such a function can never be called).
 141     static const int shift =
 142         (MaxExponent<Src>::value > MaxExponent<Dst>::value &&
 143          SrcLimits::digits < DstLimits::digits && SrcLimits::is_iec559 &&
 144          DstLimits::is_integer)
 145             ? (DstLimits::digits - SrcLimits::digits)
 146             : 0;
 147
 148     // We use UINTMAX_C below to avoid compiler warnings about shifting floating
 149     // points. Since it's a compile time calculation, it shouldn't have any
 150     // performance impact.
 151     return DstLimits::max() - static_cast<Dst>((UINTMAX_C(1) << shift) - 1);
 152   }
 153
 154   static Dst min() {
 155     return std::numeric_limits<Dst>::is_iec559 ? -DstLimits::max()
 156                                                : DstLimits::min();
 157   }
 158 };
 159
 160 template <
 161     typename Dst,
 162     typename Src,
 163     IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed
 164                                             ? INTEGER_REPRESENTATION_SIGNED
 165                                             : INTEGER_REPRESENTATION_UNSIGNED,
 166     IntegerRepresentation SrcSign = std::numeric_limits<Src>::is_signed
 167                                             ? INTEGER_REPRESENTATION_SIGNED
 168                                             : INTEGER_REPRESENTATION_UNSIGNED,
 169     NumericRangeRepresentation DstRange =
 170         StaticDstRangeRelationToSrcRange<Dst, Src>::value >
 171 struct DstRangeRelationToSrcRangeImpl;
 172
 173 // The following templates are for ranges that must be verified at runtime. We
 174 // split it into checks based on signedness to avoid confusing casts and
 175 // compiler warnings on signed an unsigned comparisons.
 176
 177 // Dst range is statically determined to contain Src: Nothing to check.
 178 template <typename Dst,
 179           typename Src,
 180           IntegerRepresentation DstSign,
 181           IntegerRepresentation SrcSign>
 182 struct DstRangeRelationToSrcRangeImpl<Dst,
 183                                       Src,
 184                                       DstSign,
 185                                       SrcSign,
 186                                       NUMERIC_RANGE_CONTAINED> {
 187   static RangeConstraint Check(Src value) { return RANGE_VALID; }
 188 };
 189
 190 // Signed to signed narrowing: Both the upper and lower boundaries may be
 191 // exceeded.
 192 template <typename Dst, typename Src>
 193 struct DstRangeRelationToSrcRangeImpl<Dst,
 194                                       Src,
 195                                       INTEGER_REPRESENTATION_SIGNED,
 196                                       INTEGER_REPRESENTATION_SIGNED,
 197                                       NUMERIC_RANGE_NOT_CONTAINED> {
 198   static RangeConstraint Check(Src value) {
 199     return GetRangeConstraint((value <= NarrowingRange<Dst, Src>::max()),
 200                               (value >= NarrowingRange<Dst, Src>::min()));
 201   }
 202 };
 203
 204 // Unsigned to unsigned narrowing: Only the upper boundary can be exceeded.
 205 template <typename Dst, typename Src>
 206 struct DstRangeRelationToSrcRangeImpl<Dst,
 207                                       Src,
 208                                       INTEGER_REPRESENTATION_UNSIGNED,
 209                                       INTEGER_REPRESENTATION_UNSIGNED,
 210                                       NUMERIC_RANGE_NOT_CONTAINED> {
 211   static RangeConstraint Check(Src value) {
 212     return GetRangeConstraint(value <= NarrowingRange<Dst, Src>::max(), true);
 213   }
 214 };
 215
 216 // Unsigned to signed: The upper boundary may be exceeded.
 217 template <typename Dst, typename Src>
 218 struct DstRangeRelationToSrcRangeImpl<Dst,
 219                                       Src,
 220                                       INTEGER_REPRESENTATION_SIGNED,
 221                                       INTEGER_REPRESENTATION_UNSIGNED,
 222                                       NUMERIC_RANGE_NOT_CONTAINED> {
 223   static RangeConstraint Check(Src value) {
 224     return sizeof(Dst) > sizeof(Src)
 225                ? RANGE_VALID
 226                : GetRangeConstraint(
 227                      value <= static_cast<Src>(NarrowingRange<Dst, Src>::max()),
 228                      true);
 229   }
 230 };
 231
 232 // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst,
 233 // and any negative value exceeds the lower boundary.
 234 template <typename Dst, typename Src>
 235 struct DstRangeRelationToSrcRangeImpl<Dst,
 236                                       Src,
 237                                       INTEGER_REPRESENTATION_UNSIGNED,
 238                                       INTEGER_REPRESENTATION_SIGNED,
 239                                       NUMERIC_RANGE_NOT_CONTAINED> {
 240   static RangeConstraint Check(Src value) {
 241     return (MaxExponent<Dst>::value >= MaxExponent<Src>::value)
 242                ? GetRangeConstraint(true, value >= static_cast<Src>(0))
 243                : GetRangeConstraint(
 244                      value <= static_cast<Src>(NarrowingRange<Dst, Src>::max()),
 245                      value >= static_cast<Src>(0));
 246   }
 247 };
 248
 249 template <typename Dst, typename Src>
 250 inline RangeConstraint DstRangeRelationToSrcRange(Src value) {
 251   static_assert(std::numeric_limits<Src>::is_specialized,
 252                 "Argument must be numeric.");
 253   static_assert(std::numeric_limits<Dst>::is_specialized,
 254                 "Result must be numeric.");
 255   return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value);
 256 }
 257
 258 }  // namespace internal
 259 }  // namespace base
 260
 261 #endif  // BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_