180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2012 Google Inc. 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkFloatUtils_DEFINED 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkFloatUtils_DEFINED 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include <limits.h> 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include <float.h> 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <size_t size> 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkTypeWithSize { 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Prevents using SkTypeWithSize<N> with non-specialized N. 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru typedef void UInt; 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <> 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkTypeWithSize<32> { 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru typedef uint32_t UInt; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <> 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkTypeWithSize<64> { 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru typedef uint64_t UInt; 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <typename RawType> 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct SkNumericLimits { 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const int digits = 0; 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <> 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct SkNumericLimits<double> { 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const int digits = DBL_MANT_DIG; 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <> 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct SkNumericLimits<float> { 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const int digits = FLT_MANT_DIG; 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//See 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//http://stackoverflow.com/questions/17333/most-effective-way-for-float-and-double-comparison/3423299#3423299 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//http://code.google.com/p/googletest/source/browse/trunk/include/gtest/internal/gtest-internal.h 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <typename RawType, unsigned int ULPs> 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkFloatingPoint { 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Bits is a unsigned integer the same size as the floating point number. */ 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru typedef typename SkTypeWithSize<sizeof(RawType) * CHAR_BIT>::UInt Bits; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** # of bits in a number. */ 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const size_t kBitCount = CHAR_BIT * sizeof(RawType); 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** # of fraction bits in a number. */ 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const size_t kFractionBitCount = SkNumericLimits<RawType>::digits - 1; 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** # of exponent bits in a number. */ 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount; 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The mask for the sign bit. */ 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1); 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The mask for the fraction bits. */ 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const Bits kFractionBitMask = 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~static_cast<Bits>(0) >> (kExponentBitCount + 1); 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The mask for the exponent bits. */ 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask); 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** How many ULP's (Units in the Last Place) to tolerate when comparing. */ 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const size_t kMaxUlps = ULPs; 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Constructs a FloatingPoint from a raw floating-point number. 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * On an Intel CPU, passing a non-normalized NAN (Not a Number) 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * around may change its bits, although the new value is guaranteed 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * to be also a NAN. Therefore, don't expect this constructor to 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * preserve the bits in x when x is a NAN. 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru explicit SkFloatingPoint(const RawType& x) { fU.value = x; } 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Returns the exponent bits of this number. */ 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Bits exponent_bits() const { return kExponentBitMask & fU.bits; } 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Returns the fraction bits of this number. */ 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Bits fraction_bits() const { return kFractionBitMask & fU.bits; } 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Returns true iff this is NAN (not a number). */ 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool is_nan() const { 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // It's a NAN if both of the folloowing are true: 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // * the exponent bits are all ones 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // * the fraction bits are not all zero. 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0); 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Returns true iff this number is at most kMaxUlps ULP's away from ths. 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * In particular, this function: 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * - returns false if either number is (or both are) NAN. 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * - treats really large numbers as almost equal to infinity. 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * - thinks +0.0 and -0.0 are 0 DLP's apart. 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool AlmostEquals(const SkFloatingPoint& rhs) const { 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Any comparison operation involving a NAN must return false. 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_nan() || rhs.is_nan()) return false; 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Bits dist = DistanceBetweenSignAndMagnitudeNumbers(fU.bits, 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru rhs.fU.bits); 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru //SkDEBUGF(("(%f, %f, %d) ", u_.value_, rhs.u_.value_, dist)); 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return dist <= kMaxUlps; 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The data type used to store the actual floating-point number. */ 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru union FloatingPointUnion { 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The raw floating-point number. */ 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru RawType value; 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** The bits that represent the number. */ 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Bits bits; 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Converts an integer from the sign-and-magnitude representation to 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * the biased representation. More precisely, let N be 2 to the 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * power of (kBitCount - 1), an integer x is represented by the 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * unsigned number x + N. 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * For instance, 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * -N + 1 (the most negative number representable using 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * sign-and-magnitude) is represented by 1; 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 0 is represented by N; and 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * N - 1 (the biggest number representable using 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * sign-and-magnitude) is represented by 2N - 1. 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Read http://en.wikipedia.org/wiki/Signed_number_representations 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * for more details on signed number representations. 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static Bits SignAndMagnitudeToBiased(const Bits &sam) { 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (kSignBitMask & sam) { 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // sam represents a negative number. 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ~sam + 1; 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // sam represents a positive number. 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return kSignBitMask | sam; 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Given two numbers in the sign-and-magnitude representation, 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * returns the distance between them as an unsigned number. 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1, 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Bits &sam2) { 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Bits biased1 = SignAndMagnitudeToBiased(sam1); 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Bits biased2 = SignAndMagnitudeToBiased(sam2); 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1); 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru FloatingPointUnion fU; 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 174