src/native_client/src/include/checked_cast.h

   1 /*
   2  * Copyright 2010 The Native Client Authors.  All rights reserved.
   3  * Use of this source code is governed by a BSD-style license that can
   4  * be found in the LICENSE file.
   5  */
   6
   7 //
   8 // checked_cast.h
   9 //
  10 // A template system, intended to be a drop-in replacement for static_cast<>,
  11 // which performs compile-time and (if necessary) runtime evaluation of
  12 // integral type casts to detect and handle arithmetic overflow errors.
  13 //
  14 #ifndef NATIVE_CLIENT_SRC_INCLUDE_CHECKED_CAST_H_
  15 #define NATIVE_CLIENT_SRC_INCLUDE_CHECKED_CAST_H_ 1
  16
  17 // Windows defines std::min and std::max in a different header
  18 // than gcc prior to Visual Studio 2013.
  19 #if NACL_WINDOWS
  20 #include <xutility>
  21 #endif
  22
  23 #include <algorithm>
  24 #include <limits>
  25
  26 // TODO(ilewis): remove reference to base as soon as we can get COMPILE_ASSERT
  27 //                from another source.
  28 #include "native_client/src/shared/platform/nacl_log.h"
  29
  30 namespace nacl {
  31
  32   //
  33   // Function to determine whether an information-preserving cast
  34   // is possible. In other words, if this function returns true, then
  35   // the input value has an exact representation in the target type.
  36   //
  37   template<typename target_t, typename source_t>
  38   bool can_cast(const source_t& input);
  39
  40   //
  41   // Function to safely cast from one type to another, with a customizable
  42   // policy determining what happens if the cast cannot complete without
  43   // losing information.
  44   //
  45   template <
  46     typename target_t,
  47     typename source_t,
  48     template<typename, typename> class trunc_policy>
  49   target_t checked_cast(const source_t& input);
  50
  51   //
  52   // Convenience wrappers for specializations of checked_cast with
  53   // different truncation policies
  54   //
  55   template<typename T, typename S>
  56   T assert_cast(const S& input);
  57
  58   template<typename T, typename S>
  59   T saturate_cast(const S& input);
  60
  61
  62   //
  63   // Helper function prototypes
  64   //
  65   //
  66   namespace CheckedCast {
  67     //
  68     // OnTruncate* functions: policy functions that define
  69     // what to do if a checked cast can't be made without
  70     // truncation that loses data.
  71     //
  72     template <typename target_t, typename source_t>
  73     struct TruncationPolicySaturate {
  74       static target_t OnTruncate(const source_t& input);
  75     };
  76
  77     template <typename target_t, typename source_t>
  78     struct TruncationPolicyAbort {
  79       static target_t OnTruncate(const source_t& input);
  80     };
  81
  82     namespace detail {
  83 //-----------------------------------------------------------------------------
  84 // RuntimeHelpers
  85 //
  86 // Ugly nested templates--necessary because GCC is ever vigilant about type
  87 // safety, and has no way to temporarily disable certain warnings
  88 //
  89 //-----------------------------------------------------------------------------
  90
  91       //
  92       // TrivialityChecker template
  93       // Makes decisions about whether a cast is trivial (does not require
  94       // the value of the input to be checked).
  95       //
  96       // The specializations are necessary to avoid running comparisons that
  97       // are either invalid or always true, since these comparisons trigger
  98       // warnings.
  99       //
 100       template<typename tlimits, typename slimits, bool IsCompileTimeTrivial>
 101       struct TrivialityChecker {
 102         static bool IsRuntimeTrivial() { return false; }
 103       };
 104
 105       template<typename tlimits, typename slimits>
 106       struct TrivialityChecker<tlimits, slimits, true> {
 107         static bool IsRuntimeTrivial() {
 108           // Split into variables to bypass const value warning
 109           bool tlimits_lequ_min_slimits = tlimits::min() <= slimits::min();
 110           bool tlimits_gequ_max_slimits = tlimits::max() >= slimits::max();
 111           bool trivial = tlimits_lequ_min_slimits && tlimits_gequ_max_slimits;
 112           return trivial;
 113         }
 114       };
 115
 116       //
 117       // Casting versions of std::min and std::max.
 118       // These should only be called from code that has checked to make
 119       // sure the cast is valid, otherwise compiler warnings will be
 120       // triggered.
 121       //
 122       template<typename A, typename B>
 123       static B cast_min(const A& a, const B& b) {
 124         return (static_cast<B>(a) < b) ? static_cast<B>(a) : b;
 125       }
 126
 127       template<typename A, typename B>
 128       static B cast_max(const A& a, const B& b) {
 129         return (static_cast<B>(a) > b) ? static_cast<B>(a) : b;
 130       }
 131
 132       //
 133       // Template specializations for determining valid ranges for
 134       // any given typecast. Specialized for different combinations
 135       // of signed/unsigned types.
 136       //
 137       template<typename target_t,
 138                typename source_t,
 139                bool SignednessDiffers,
 140                bool TargetIsSigned>
 141       struct RangeDetail {
 142         typedef std::numeric_limits<target_t> tlimits;
 143         typedef std::numeric_limits<source_t> slimits;
 144
 145         static source_t OverlapMin() {
 146           return cast_max(tlimits::min(), slimits::min());
 147         }
 148         static source_t OverlapMax() {
 149           return cast_min(tlimits::max(), slimits::max());
 150         }
 151       };
 152
 153       // signed target / unsigned source
 154       template<typename target_t, typename source_t>
 155       struct RangeDetail<target_t, source_t, true, true> {
 156         typedef std::numeric_limits<target_t> tlimits;
 157         typedef std::numeric_limits<source_t> slimits;
 158
 159         static source_t OverlapMin() {
 160           if (tlimits::min() >= 0) {
 161             return cast_max(tlimits::min(), slimits::min());
 162           } else {
 163             return slimits::min();
 164           }
 165         }
 166         static source_t OverlapMax() {
 167           if (tlimits::max() >= 0) {
 168             return cast_min(tlimits::max(), slimits::max());
 169           } else {
 170             return slimits::min();
 171           }
 172         }
 173       };
 174
 175       // unsigned target / signed source
 176       template<typename target_t, typename source_t>
 177       struct RangeDetail<target_t, source_t, true, false> {
 178         typedef std::numeric_limits<target_t> tlimits;
 179         typedef std::numeric_limits<source_t> slimits;
 180
 181         static source_t OverlapMin() {
 182           if (slimits::min() >= 0) {
 183             return cast_max(tlimits::min(), slimits::min());
 184           } else if (slimits::max() >= 0) {
 185             return cast_min(tlimits::min(), slimits::max());
 186           } else {
 187             return slimits::min();
 188           }
 189         }
 190         static source_t OverlapMax() {
 191           if (slimits::max() >= 0) {
 192             return cast_min(tlimits::max(), slimits::max());
 193           } else {
 194             return slimits::min();
 195           }
 196         }
 197       };
 198
 199       //
 200       // Wrapper for RangeDetail. Prevents RangeDetail objects
 201       // from being instantiated for unsupported types.
 202       //
 203       template<typename target_t, typename source_t, bool IsSupported>
 204       struct RangeHelper {
 205         typedef std::numeric_limits<target_t> tlimits;
 206         typedef std::numeric_limits<source_t> slimits;
 207
 208         static bool OverlapExists() { return false; }
 209
 210         // The return values from OverlapMin() and OverlapMax() are
 211         // arbitrary if OverlapExists() returns false, so we'll
 212         // just return the minimum source value for both.
 213         static source_t OverlapMin() { return slimits::min(); }
 214         static source_t OverlapMax() { return slimits::min(); }
 215       };
 216
 217       template<typename target_t, typename source_t>
 218       struct RangeHelper<target_t, source_t, true> {
 219         typedef std::numeric_limits<target_t> tlimits;
 220         typedef std::numeric_limits<source_t> slimits;
 221
 222         typedef RangeDetail<target_t,
 223           source_t,
 224           (tlimits::is_signed != slimits::is_signed),
 225           tlimits::is_signed> detail_t;
 226
 227         static bool OverlapExists() {
 228           return detail_t::OverlapMin() < detail_t::OverlapMax();
 229         }
 230         static source_t OverlapMin() { return detail_t::OverlapMin(); }
 231         static source_t OverlapMax() { return detail_t::OverlapMax(); }
 232       };
 233
 234       //
 235       // CastInfo
 236       //
 237       // Maintains information about how to cast between
 238       // two types.
 239       //
 240       template<typename target_t, typename source_t>
 241       struct CastInfo {
 242         typedef std::numeric_limits<target_t> tlimits;
 243         typedef std::numeric_limits<source_t> slimits;
 244
 245         static const bool kSupported = tlimits::is_specialized
 246           && slimits::is_specialized
 247           && tlimits::is_integer
 248           && slimits::is_integer
 249           && tlimits::is_bounded
 250           && slimits::is_bounded;
 251
 252         static const bool kIdenticalSignedness =
 253           (tlimits::is_signed == slimits::is_signed);
 254
 255         // "digits" in numeric_limits refers to binary
 256         // digits. (Decimal digits are stored in a field
 257         // called digits10.)
 258         static const bool kSufficientBits =
 259           (tlimits::digits >= slimits::digits);
 260
 261         static const bool kCompileTimeTrivial = kSupported
 262           && kIdenticalSignedness
 263           && kSufficientBits;
 264
 265         typedef TrivialityChecker<tlimits,
 266                                   slimits,
 267                                   kCompileTimeTrivial> trivial_t;
 268         typedef RangeHelper<target_t, source_t, kSupported> range_t;
 269
 270         // Can the cast be done without runtime checks--i.e. are
 271         // all possible input values also valid output values?
 272         static bool RuntimeTrivial() {
 273           return trivial_t::IsRuntimeTrivial();
 274         }
 275
 276         // Are there any valid input values for which a cast would succeed?
 277         static bool RuntimePossible() {
 278           return range_t::OverlapExists();
 279         }
 280
 281         // Is the given source value a valid target value?
 282         static bool RuntimeRangeCheck(const source_t& src) {
 283           return (range_t::OverlapExists()
 284                   && src <= range_t::OverlapMax()
 285                   && src >= range_t::OverlapMin());
 286         }
 287
 288         // Range of source values which are also valid target values.
 289         static source_t RuntimeRangeMin() { return range_t::OverlapMin(); }
 290         static source_t RuntimeRangeMax() { return range_t::OverlapMax(); }
 291       };
 292     }  // namespace detail
 293   }  // namespace CheckedCast
 294 }  // namespace nacl
 295
 296
 297 //-----------------------------------------------------------------------------
 298 //
 299 // Implementation
 300 //
 301 //-----------------------------------------------------------------------------
 302
 303 //-----------------------------------------------------------------------------
 304 // checked_cast(const source_t& input)
 305 //    An augmented replacement for static_cast. Does range checking,
 306 //    overflow validation. Includes a policy which allows the caller to
 307 //    specify what action to take if it's determined that the cast
 308 //    would lose data.
 309 //
 310 // Template parameters:
 311 //    target_t:     the type on the left hand side of the cast
 312 //    source_t:     the type on the right hand side of the cast
 313 //    trunc_policy: type of a policy object that will be called
 314 //                if the cast would result in a loss of data. The
 315 //                type must implement a method named OnTruncate which
 316 //                is compatible with the following signature:
 317 //                target_t (target_t& output, const source_t& input).
 318 //                It is the responsibility of this function to
 319 //                convert the value of 'input' and store the result
 320 //                of the conversion in out parameter 'output'. It is
 321 //                permissible for the function to abort or log warnings
 322 //                if that is the desired behavior.
 323 //
 324 // Function parameters:
 325 //    input:    the value to convert.
 326 //
 327 // usage:
 328 //    // naive truncation handler for sample purposes ONLY!!
 329 //    template <typename T, typename S>
 330 //    void naive_trunc(T& o, const S& i) {
 331 //      // this only gets called if checked_cast can't do a safe automatic
 332 //      // conversion. In real code you'd want to do something cool like
 333 //      // clamp the incoming value or abort the program. For this sample
 334 //      // we just return a c-style cast, which makes the outcome roughly
 335 //      // equivalent to static_cast<>.
 336 //      o = (T)i;
 337 //    }
 338 //
 339 //    void main() {
 340 //      uint64_t foo = 0xffff0000ffff0000;
 341 //      uint32_t bar = checked_cast<uint32_t>(foo, naive_trunc);
 342 //    }
 343 //
 344 template <
 345     typename target_t,
 346     typename source_t,
 347     template<typename, typename> class trunc_policy>
 348 target_t nacl::checked_cast(const source_t& input) {
 349   target_t output;
 350
 351   //
 352   // Runtime checks--these should compile out for all basic types
 353   //
 354   if (nacl::can_cast<target_t>(input)) {
 355     output = static_cast<target_t>(input);
 356   } else {
 357     output = trunc_policy<target_t, source_t>::OnTruncate(input);
 358   }
 359
 360   return output;
 361 }
 362
 363 //-----------------------------------------------------------------------------
 364 // can_cast(const source_t& input)
 365 //  Returns true if checked_cast will return without invoking trunc_policy.
 366 //-----------------------------------------------------------------------------
 367 template <typename target_t, typename source_t>
 368 bool nacl::can_cast(const source_t& input) {
 369   typedef CheckedCast::detail::CastInfo<target_t, source_t> info;
 370
 371   bool result;
 372
 373   //
 374   // Runtime checks--these should compile out for all basic types
 375   //
 376   result = info::RuntimeTrivial()
 377     || (info::RuntimePossible()
 378     && info::RuntimeRangeCheck(input));
 379
 380   return result;
 381 }
 382
 383
 384 //
 385 // Convenience wrappers for specializations of checked_cast
 386 //
 387
 388 //-----------------------------------------------------------------------------
 389 // checked_cast_fatal(const S& input)
 390 // Calls checked_cast; on truncation, log error and abort
 391 //-----------------------------------------------------------------------------
 392 template<typename T, typename S>
 393 T nacl::assert_cast(const S& input) {
 394   return checked_cast<T, S, CheckedCast::TruncationPolicyAbort>(input);
 395 }
 396 //-----------------------------------------------------------------------------
 397 // saturate_cast(const S& input)
 398 // Calls checked_cast; on truncation, saturates the input to the minimum
 399 // or maximum of the output.
 400 //-----------------------------------------------------------------------------
 401 template<typename T, typename S>
 402 T nacl::saturate_cast(const S& input) {
 403   return
 404     checked_cast<T, S, CheckedCast::TruncationPolicySaturate>(input);
 405 }
 406
 407 //-----------------------------------------------------------------------------
 408 // CheckedCastDetail::OnTruncationSaturate
 409 // Implements the Saturate truncation policy.
 410 //-----------------------------------------------------------------------------
 411 template <typename target_t, typename source_t>
 412 target_t nacl
 413     ::CheckedCast
 414     ::TruncationPolicySaturate<target_t, source_t>
 415     ::OnTruncate(const source_t& input) {
 416   typedef detail::CastInfo<target_t, source_t> info;
 417
 418   source_t clamped = input;
 419   bool valid = info::RuntimePossible();
 420
 421   if (!valid) {
 422     NaClLog(LOG_FATAL, "Checked cast: type ranges do not overlap");
 423   }
 424
 425   clamped = std::max(clamped, info::RuntimeRangeMin());
 426   clamped = std::min(clamped, info::RuntimeRangeMax());
 427
 428   target_t output = static_cast<target_t>(clamped);
 429
 430   return output;
 431 }
 432
 433
 434
 435 //-----------------------------------------------------------------------------
 436 // CheckedCastDetail::OnTruncationAbort
 437 // Implements the Abort truncation policy.
 438 //-----------------------------------------------------------------------------
 439 template <typename target_t, typename source_t>
 440 target_t nacl
 441     ::CheckedCast
 442     ::TruncationPolicyAbort<target_t, source_t>
 443     ::OnTruncate(const source_t&) {
 444   NaClLog(LOG_FATAL, "Arithmetic overflow");
 445
 446   // Unreachable, assuming that LOG_FATAL really is fatal
 447   return 0;
 448 }
 449
 450
 451 #endif  /* NATIVE_CLIENT_SRC_INCLUDE_CHECKED_CAST_H_ */