http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/6da3961b/ext/kenlm/util/double-conversion/fast-dtoa.cc ---------------------------------------------------------------------- diff --git a/ext/kenlm b/ext/kenlm new file mode 160000 index 0000000..56fdb5c --- /dev/null +++ b/ext/kenlm @@ -0,0 +1 @@ +Subproject commit 56fdb5c44fca34d5a2e07d96139c28fb163983c5 diff --git a/ext/kenlm/util/double-conversion/fast-dtoa.cc b/ext/kenlm/util/double-conversion/fast-dtoa.cc deleted file mode 100644 index 1a0f823..0000000 --- a/ext/kenlm/util/double-conversion/fast-dtoa.cc +++ /dev/null @@ -1,664 +0,0 @@ -// Copyright 2012 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#include "fast-dtoa.h" - -#include "cached-powers.h" -#include "diy-fp.h" -#include "ieee.h" - -namespace double_conversion { - -// The minimal and maximal target exponent define the range of w's binary -// exponent, where 'w' is the result of multiplying the input by a cached power -// of ten. -// -// A different range might be chosen on a different platform, to optimize digit -// generation, but a smaller range requires more powers of ten to be cached. -static const int kMinimalTargetExponent = -60; -static const int kMaximalTargetExponent = -32; - - -// Adjusts the last digit of the generated number, and screens out generated -// solutions that may be inaccurate. A solution may be inaccurate if it is -// outside the safe interval, or if we cannot prove that it is closer to the -// input than a neighboring representation of the same length. -// -// Input: * buffer containing the digits of too_high / 10^kappa -// * the buffer's length -// * distance_too_high_w == (too_high - w).f() * unit -// * unsafe_interval == (too_high - too_low).f() * unit -// * rest = (too_high - buffer * 10^kappa).f() * unit -// * ten_kappa = 10^kappa * unit -// * unit = the common multiplier -// Output: returns true if the buffer is guaranteed to contain the closest -// representable number to the input. -// Modifies the generated digits in the buffer to approach (round towards) w. -static bool RoundWeed(Vector<char> buffer, - int length, - uint64_t distance_too_high_w, - uint64_t unsafe_interval, - uint64_t rest, - uint64_t ten_kappa, - uint64_t unit) { - uint64_t small_distance = distance_too_high_w - unit; - uint64_t big_distance = distance_too_high_w + unit; - // Let w_low = too_high - big_distance, and - // w_high = too_high - small_distance. - // Note: w_low < w < w_high - // - // The real w (* unit) must lie somewhere inside the interval - // ]w_low; w_high[ (often written as "(w_low; w_high)") - - // Basically the buffer currently contains a number in the unsafe interval - // ]too_low; too_high[ with too_low < w < too_high - // - // too_high - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // ^v 1 unit ^ ^ ^ ^ - // boundary_high --------------------- . . . . - // ^v 1 unit . . . . - // - - - - - - - - - - - - - - - - - - - + - - + - - - - - - . . - // . . ^ . . - // . big_distance . . . - // . . . . rest - // small_distance . . . . - // v . . . . - // w_high - - - - - - - - - - - - - - - - - - . . . . - // ^v 1 unit . . . . - // w ---------------------------------------- . . . . - // ^v 1 unit v . . . - // w_low - - - - - - - - - - - - - - - - - - - - - . . . - // . . v - // buffer --------------------------------------------------+-------+-------- - // . . - // safe_interval . - // v . - // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - . - // ^v 1 unit . - // boundary_low ------------------------- unsafe_interval - // ^v 1 unit v - // too_low - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // - // - // Note that the value of buffer could lie anywhere inside the range too_low - // to too_high. - // - // boundary_low, boundary_high and w are approximations of the real boundaries - // and v (the input number). They are guaranteed to be precise up to one unit. - // In fact the error is guaranteed to be strictly less than one unit. - // - // Anything that lies outside the unsafe interval is guaranteed not to round - // to v when read again. - // Anything that lies inside the safe interval is guaranteed to round to v - // when read again. - // If the number inside the buffer lies inside the unsafe interval but not - // inside the safe interval then we simply do not know and bail out (returning - // false). - // - // Similarly we have to take into account the imprecision of 'w' when finding - // the closest representation of 'w'. If we have two potential - // representations, and one is closer to both w_low and w_high, then we know - // it is closer to the actual value v. - // - // By generating the digits of too_high we got the largest (closest to - // too_high) buffer that is still in the unsafe interval. In the case where - // w_high < buffer < too_high we try to decrement the buffer. - // This way the buffer approaches (rounds towards) w. - // There are 3 conditions that stop the decrementation process: - // 1) the buffer is already below w_high - // 2) decrementing the buffer would make it leave the unsafe interval - // 3) decrementing the buffer would yield a number below w_high and farther - // away than the current number. In other words: - // (buffer{-1} < w_high) && w_high - buffer{-1} > buffer - w_high - // Instead of using the buffer directly we use its distance to too_high. - // Conceptually rest ~= too_high - buffer - // We need to do the following tests in this order to avoid over- and - // underflows. - ASSERT(rest <= unsafe_interval); - while (rest < small_distance && // Negated condition 1 - unsafe_interval - rest >= ten_kappa && // Negated condition 2 - (rest + ten_kappa < small_distance || // buffer{-1} > w_high - small_distance - rest >= rest + ten_kappa - small_distance)) { - buffer[length - 1]--; - rest += ten_kappa; - } - - // We have approached w+ as much as possible. We now test if approaching w- - // would require changing the buffer. If yes, then we have two possible - // representations close to w, but we cannot decide which one is closer. - if (rest < big_distance && - unsafe_interval - rest >= ten_kappa && - (rest + ten_kappa < big_distance || - big_distance - rest > rest + ten_kappa - big_distance)) { - return false; - } - - // Weeding test. - // The safe interval is [too_low + 2 ulp; too_high - 2 ulp] - // Since too_low = too_high - unsafe_interval this is equivalent to - // [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp] - // Conceptually we have: rest ~= too_high - buffer - return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit); -} - - -// Rounds the buffer upwards if the result is closer to v by possibly adding -// 1 to the buffer. If the precision of the calculation is not sufficient to -// round correctly, return false. -// The rounding might shift the whole buffer in which case the kappa is -// adjusted. For example "99", kappa = 3 might become "10", kappa = 4. -// -// If 2*rest > ten_kappa then the buffer needs to be round up. -// rest can have an error of +/- 1 unit. This function accounts for the -// imprecision and returns false, if the rounding direction cannot be -// unambiguously determined. -// -// Precondition: rest < ten_kappa. -static bool RoundWeedCounted(Vector<char> buffer, - int length, - uint64_t rest, - uint64_t ten_kappa, - uint64_t unit, - int* kappa) { - ASSERT(rest < ten_kappa); - // The following tests are done in a specific order to avoid overflows. They - // will work correctly with any uint64 values of rest < ten_kappa and unit. - // - // If the unit is too big, then we don't know which way to round. For example - // a unit of 50 means that the real number lies within rest +/- 50. If - // 10^kappa == 40 then there is no way to tell which way to round. - if (unit >= ten_kappa) return false; - // Even if unit is just half the size of 10^kappa we are already completely - // lost. (And after the previous test we know that the expression will not - // over/underflow.) - if (ten_kappa - unit <= unit) return false; - // If 2 * (rest + unit) <= 10^kappa we can safely round down. - if ((ten_kappa - rest > rest) && (ten_kappa - 2 * rest >= 2 * unit)) { - return true; - } - // If 2 * (rest - unit) >= 10^kappa, then we can safely round up. - if ((rest > unit) && (ten_kappa - (rest - unit) <= (rest - unit))) { - // Increment the last digit recursively until we find a non '9' digit. - buffer[length - 1]++; - for (int i = length - 1; i > 0; --i) { - if (buffer[i] != '0' + 10) break; - buffer[i] = '0'; - buffer[i - 1]++; - } - // If the first digit is now '0'+ 10 we had a buffer with all '9's. With the - // exception of the first digit all digits are now '0'. Simply switch the - // first digit to '1' and adjust the kappa. Example: "99" becomes "10" and - // the power (the kappa) is increased. - if (buffer[0] == '0' + 10) { - buffer[0] = '1'; - (*kappa) += 1; - } - return true; - } - return false; -} - -// Returns the biggest power of ten that is less than or equal to the given -// number. We furthermore receive the maximum number of bits 'number' has. -// -// Returns power == 10^(exponent_plus_one-1) such that -// power <= number < power * 10. -// If number_bits == 0 then 0^(0-1) is returned. -// The number of bits must be <= 32. -// Precondition: number < (1 << (number_bits + 1)). - -// Inspired by the method for finding an integer log base 10 from here: -// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10 -static unsigned int const kSmallPowersOfTen[] = - {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, - 1000000000}; - -static void BiggestPowerTen(uint32_t number, - int number_bits, - uint32_t* power, - int* exponent_plus_one) { - ASSERT(number < (1u << (number_bits + 1))); - // 1233/4096 is approximately 1/lg(10). - int exponent_plus_one_guess = ((number_bits + 1) * 1233 >> 12); - // We increment to skip over the first entry in the kPowersOf10 table. - // Note: kPowersOf10[i] == 10^(i-1). - exponent_plus_one_guess++; - // We don't have any guarantees that 2^number_bits <= number. - // TODO(floitsch): can we change the 'while' into an 'if'? We definitely see - // number < (2^number_bits - 1), but I haven't encountered - // number < (2^number_bits - 2) yet. - while (number < kSmallPowersOfTen[exponent_plus_one_guess]) { - exponent_plus_one_guess--; - } - *power = kSmallPowersOfTen[exponent_plus_one_guess]; - *exponent_plus_one = exponent_plus_one_guess; -} - -// Generates the digits of input number w. -// w is a floating-point number (DiyFp), consisting of a significand and an -// exponent. Its exponent is bounded by kMinimalTargetExponent and -// kMaximalTargetExponent. -// Hence -60 <= w.e() <= -32. -// -// Returns false if it fails, in which case the generated digits in the buffer -// should not be used. -// Preconditions: -// * low, w and high are correct up to 1 ulp (unit in the last place). That -// is, their error must be less than a unit of their last digits. -// * low.e() == w.e() == high.e() -// * low < w < high, and taking into account their error: low~ <= high~ -// * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent -// Postconditions: returns false if procedure fails. -// otherwise: -// * buffer is not null-terminated, but len contains the number of digits. -// * buffer contains the shortest possible decimal digit-sequence -// such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the -// correct values of low and high (without their error). -// * if more than one decimal representation gives the minimal number of -// decimal digits then the one closest to W (where W is the correct value -// of w) is chosen. -// Remark: this procedure takes into account the imprecision of its input -// numbers. If the precision is not enough to guarantee all the postconditions -// then false is returned. This usually happens rarely (~0.5%). -// -// Say, for the sake of example, that -// w.e() == -48, and w.f() == 0x1234567890abcdef -// w's value can be computed by w.f() * 2^w.e() -// We can obtain w's integral digits by simply shifting w.f() by -w.e(). -// -> w's integral part is 0x1234 -// w's fractional part is therefore 0x567890abcdef. -// Printing w's integral part is easy (simply print 0x1234 in decimal). -// In order to print its fraction we repeatedly multiply the fraction by 10 and -// get each digit. Example the first digit after the point would be computed by -// (0x567890abcdef * 10) >> 48. -> 3 -// The whole thing becomes slightly more complicated because we want to stop -// once we have enough digits. That is, once the digits inside the buffer -// represent 'w' we can stop. Everything inside the interval low - high -// represents w. However we have to pay attention to low, high and w's -// imprecision. -static bool DigitGen(DiyFp low, - DiyFp w, - DiyFp high, - Vector<char> buffer, - int* length, - int* kappa) { - ASSERT(low.e() == w.e() && w.e() == high.e()); - ASSERT(low.f() + 1 <= high.f() - 1); - ASSERT(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent); - // low, w and high are imprecise, but by less than one ulp (unit in the last - // place). - // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that - // the new numbers are outside of the interval we want the final - // representation to lie in. - // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield - // numbers that are certain to lie in the interval. We will use this fact - // later on. - // We will now start by generating the digits within the uncertain - // interval. Later we will weed out representations that lie outside the safe - // interval and thus _might_ lie outside the correct interval. - uint64_t unit = 1; - DiyFp too_low = DiyFp(low.f() - unit, low.e()); - DiyFp too_high = DiyFp(high.f() + unit, high.e()); - // too_low and too_high are guaranteed to lie outside the interval we want the - // generated number in. - DiyFp unsafe_interval = DiyFp::Minus(too_high, too_low); - // We now cut the input number into two parts: the integral digits and the - // fractionals. We will not write any decimal separator though, but adapt - // kappa instead. - // Reminder: we are currently computing the digits (stored inside the buffer) - // such that: too_low < buffer * 10^kappa < too_high - // We use too_high for the digit_generation and stop as soon as possible. - // If we stop early we effectively round down. - DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e()); - // Division by one is a shift. - uint32_t integrals = static_cast<uint32_t>(too_high.f() >> -one.e()); - // Modulo by one is an and. - uint64_t fractionals = too_high.f() & (one.f() - 1); - uint32_t divisor; - int divisor_exponent_plus_one; - BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()), - &divisor, &divisor_exponent_plus_one); - *kappa = divisor_exponent_plus_one; - *length = 0; - // Loop invariant: buffer = too_high / 10^kappa (integer division) - // The invariant holds for the first iteration: kappa has been initialized - // with the divisor exponent + 1. And the divisor is the biggest power of ten - // that is smaller than integrals. - while (*kappa > 0) { - int digit = integrals / divisor; - buffer[*length] = '0' + digit; - (*length)++; - integrals %= divisor; - (*kappa)--; - // Note that kappa now equals the exponent of the divisor and that the - // invariant thus holds again. - uint64_t rest = - (static_cast<uint64_t>(integrals) << -one.e()) + fractionals; - // Invariant: too_high = buffer * 10^kappa + DiyFp(rest, one.e()) - // Reminder: unsafe_interval.e() == one.e() - if (rest < unsafe_interval.f()) { - // Rounding down (by not emitting the remaining digits) yields a number - // that lies within the unsafe interval. - return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f(), - unsafe_interval.f(), rest, - static_cast<uint64_t>(divisor) << -one.e(), unit); - } - divisor /= 10; - } - - // The integrals have been generated. We are at the point of the decimal - // separator. In the following loop we simply multiply the remaining digits by - // 10 and divide by one. We just need to pay attention to multiply associated - // data (like the interval or 'unit'), too. - // Note that the multiplication by 10 does not overflow, because w.e >= -60 - // and thus one.e >= -60. - ASSERT(one.e() >= -60); - ASSERT(fractionals < one.f()); - ASSERT(UINT64_2PART_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f()); - while (true) { - fractionals *= 10; - unit *= 10; - unsafe_interval.set_f(unsafe_interval.f() * 10); - // Integer division by one. - int digit = static_cast<int>(fractionals >> -one.e()); - buffer[*length] = '0' + digit; - (*length)++; - fractionals &= one.f() - 1; // Modulo by one. - (*kappa)--; - if (fractionals < unsafe_interval.f()) { - return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit, - unsafe_interval.f(), fractionals, one.f(), unit); - } - } -} - - - -// Generates (at most) requested_digits digits of input number w. -// w is a floating-point number (DiyFp), consisting of a significand and an -// exponent. Its exponent is bounded by kMinimalTargetExponent and -// kMaximalTargetExponent. -// Hence -60 <= w.e() <= -32. -// -// Returns false if it fails, in which case the generated digits in the buffer -// should not be used. -// Preconditions: -// * w is correct up to 1 ulp (unit in the last place). That -// is, its error must be strictly less than a unit of its last digit. -// * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent -// -// Postconditions: returns false if procedure fails. -// otherwise: -// * buffer is not null-terminated, but length contains the number of -// digits. -// * the representation in buffer is the most precise representation of -// requested_digits digits. -// * buffer contains at most requested_digits digits of w. If there are less -// than requested_digits digits then some trailing '0's have been removed. -// * kappa is such that -// w = buffer * 10^kappa + eps with |eps| < 10^kappa / 2. -// -// Remark: This procedure takes into account the imprecision of its input -// numbers. If the precision is not enough to guarantee all the postconditions -// then false is returned. This usually happens rarely, but the failure-rate -// increases with higher requested_digits. -static bool DigitGenCounted(DiyFp w, - int requested_digits, - Vector<char> buffer, - int* length, - int* kappa) { - ASSERT(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent); - ASSERT(kMinimalTargetExponent >= -60); - ASSERT(kMaximalTargetExponent <= -32); - // w is assumed to have an error less than 1 unit. Whenever w is scaled we - // also scale its error. - uint64_t w_error = 1; - // We cut the input number into two parts: the integral digits and the - // fractional digits. We don't emit any decimal separator, but adapt kappa - // instead. Example: instead of writing "1.2" we put "12" into the buffer and - // increase kappa by 1. - DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e()); - // Division by one is a shift. - uint32_t integrals = static_cast<uint32_t>(w.f() >> -one.e()); - // Modulo by one is an and. - uint64_t fractionals = w.f() & (one.f() - 1); - uint32_t divisor; - int divisor_exponent_plus_one; - BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()), - &divisor, &divisor_exponent_plus_one); - *kappa = divisor_exponent_plus_one; - *length = 0; - - // Loop invariant: buffer = w / 10^kappa (integer division) - // The invariant holds for the first iteration: kappa has been initialized - // with the divisor exponent + 1. And the divisor is the biggest power of ten - // that is smaller than 'integrals'. - while (*kappa > 0) { - int digit = integrals / divisor; - buffer[*length] = '0' + digit; - (*length)++; - requested_digits--; - integrals %= divisor; - (*kappa)--; - // Note that kappa now equals the exponent of the divisor and that the - // invariant thus holds again. - if (requested_digits == 0) break; - divisor /= 10; - } - - if (requested_digits == 0) { - uint64_t rest = - (static_cast<uint64_t>(integrals) << -one.e()) + fractionals; - return RoundWeedCounted(buffer, *length, rest, - static_cast<uint64_t>(divisor) << -one.e(), w_error, - kappa); - } - - // The integrals have been generated. We are at the point of the decimal - // separator. In the following loop we simply multiply the remaining digits by - // 10 and divide by one. We just need to pay attention to multiply associated - // data (the 'unit'), too. - // Note that the multiplication by 10 does not overflow, because w.e >= -60 - // and thus one.e >= -60. - ASSERT(one.e() >= -60); - ASSERT(fractionals < one.f()); - ASSERT(UINT64_2PART_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f()); - while (requested_digits > 0 && fractionals > w_error) { - fractionals *= 10; - w_error *= 10; - // Integer division by one. - int digit = static_cast<int>(fractionals >> -one.e()); - buffer[*length] = '0' + digit; - (*length)++; - requested_digits--; - fractionals &= one.f() - 1; // Modulo by one. - (*kappa)--; - } - if (requested_digits != 0) return false; - return RoundWeedCounted(buffer, *length, fractionals, one.f(), w_error, - kappa); -} - - -// Provides a decimal representation of v. -// Returns true if it succeeds, otherwise the result cannot be trusted. -// There will be *length digits inside the buffer (not null-terminated). -// If the function returns true then -// v == (double) (buffer * 10^decimal_exponent). -// The digits in the buffer are the shortest representation possible: no -// 0.09999999999999999 instead of 0.1. The shorter representation will even be -// chosen even if the longer one would be closer to v. -// The last digit will be closest to the actual v. That is, even if several -// digits might correctly yield 'v' when read again, the closest will be -// computed. -static bool Grisu3(double v, - FastDtoaMode mode, - Vector<char> buffer, - int* length, - int* decimal_exponent) { - DiyFp w = Double(v).AsNormalizedDiyFp(); - // boundary_minus and boundary_plus are the boundaries between v and its - // closest floating-point neighbors. Any number strictly between - // boundary_minus and boundary_plus will round to v when convert to a double. - // Grisu3 will never output representations that lie exactly on a boundary. - DiyFp boundary_minus, boundary_plus; - if (mode == FAST_DTOA_SHORTEST) { - Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); - } else { - ASSERT(mode == FAST_DTOA_SHORTEST_SINGLE); - float single_v = static_cast<float>(v); - Single(single_v).NormalizedBoundaries(&boundary_minus, &boundary_plus); - } - ASSERT(boundary_plus.e() == w.e()); - DiyFp ten_mk; // Cached power of ten: 10^-k - int mk; // -k - int ten_mk_minimal_binary_exponent = - kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize); - int ten_mk_maximal_binary_exponent = - kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize); - PowersOfTenCache::GetCachedPowerForBinaryExponentRange( - ten_mk_minimal_binary_exponent, - ten_mk_maximal_binary_exponent, - &ten_mk, &mk); - ASSERT((kMinimalTargetExponent <= w.e() + ten_mk.e() + - DiyFp::kSignificandSize) && - (kMaximalTargetExponent >= w.e() + ten_mk.e() + - DiyFp::kSignificandSize)); - // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a - // 64 bit significand and ten_mk is thus only precise up to 64 bits. - - // The DiyFp::Times procedure rounds its result, and ten_mk is approximated - // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now - // off by a small amount. - // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. - // In other words: let f = scaled_w.f() and e = scaled_w.e(), then - // (f-1) * 2^e < w*10^k < (f+1) * 2^e - DiyFp scaled_w = DiyFp::Times(w, ten_mk); - ASSERT(scaled_w.e() == - boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize); - // In theory it would be possible to avoid some recomputations by computing - // the difference between w and boundary_minus/plus (a power of 2) and to - // compute scaled_boundary_minus/plus by subtracting/adding from - // scaled_w. However the code becomes much less readable and the speed - // enhancements are not terriffic. - DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk); - DiyFp scaled_boundary_plus = DiyFp::Times(boundary_plus, ten_mk); - - // DigitGen will generate the digits of scaled_w. Therefore we have - // v == (double) (scaled_w * 10^-mk). - // Set decimal_exponent == -mk and pass it to DigitGen. If scaled_w is not an - // integer than it will be updated. For instance if scaled_w == 1.23 then - // the buffer will be filled with "123" und the decimal_exponent will be - // decreased by 2. - int kappa; - bool result = DigitGen(scaled_boundary_minus, scaled_w, scaled_boundary_plus, - buffer, length, &kappa); - *decimal_exponent = -mk + kappa; - return result; -} - - -// The "counted" version of grisu3 (see above) only generates requested_digits -// number of digits. This version does not generate the shortest representation, -// and with enough requested digits 0.1 will at some point print as 0.9999999... -// Grisu3 is too imprecise for real halfway cases (1.5 will not work) and -// therefore the rounding strategy for halfway cases is irrelevant. -static bool Grisu3Counted(double v, - int requested_digits, - Vector<char> buffer, - int* length, - int* decimal_exponent) { - DiyFp w = Double(v).AsNormalizedDiyFp(); - DiyFp ten_mk; // Cached power of ten: 10^-k - int mk; // -k - int ten_mk_minimal_binary_exponent = - kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize); - int ten_mk_maximal_binary_exponent = - kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize); - PowersOfTenCache::GetCachedPowerForBinaryExponentRange( - ten_mk_minimal_binary_exponent, - ten_mk_maximal_binary_exponent, - &ten_mk, &mk); - ASSERT((kMinimalTargetExponent <= w.e() + ten_mk.e() + - DiyFp::kSignificandSize) && - (kMaximalTargetExponent >= w.e() + ten_mk.e() + - DiyFp::kSignificandSize)); - // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a - // 64 bit significand and ten_mk is thus only precise up to 64 bits. - - // The DiyFp::Times procedure rounds its result, and ten_mk is approximated - // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now - // off by a small amount. - // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. - // In other words: let f = scaled_w.f() and e = scaled_w.e(), then - // (f-1) * 2^e < w*10^k < (f+1) * 2^e - DiyFp scaled_w = DiyFp::Times(w, ten_mk); - - // We now have (double) (scaled_w * 10^-mk). - // DigitGen will generate the first requested_digits digits of scaled_w and - // return together with a kappa such that scaled_w ~= buffer * 10^kappa. (It - // will not always be exactly the same since DigitGenCounted only produces a - // limited number of digits.) - int kappa; - bool result = DigitGenCounted(scaled_w, requested_digits, - buffer, length, &kappa); - *decimal_exponent = -mk + kappa; - return result; -} - - -bool FastDtoa(double v, - FastDtoaMode mode, - int requested_digits, - Vector<char> buffer, - int* length, - int* decimal_point) { - ASSERT(v > 0); - ASSERT(!Double(v).IsSpecial()); - - bool result = false; - int decimal_exponent = 0; - switch (mode) { - case FAST_DTOA_SHORTEST: - case FAST_DTOA_SHORTEST_SINGLE: - result = Grisu3(v, mode, buffer, length, &decimal_exponent); - break; - case FAST_DTOA_PRECISION: - result = Grisu3Counted(v, requested_digits, - buffer, length, &decimal_exponent); - break; - default: - UNREACHABLE(); - } - if (result) { - *decimal_point = *length + decimal_exponent; - buffer[*length] = '\0'; - } - return result; -} - -} // namespace double_conversion
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/6da3961b/ext/kenlm/util/double-conversion/fast-dtoa.h ---------------------------------------------------------------------- diff --git a/ext/kenlm b/ext/kenlm new file mode 160000 index 0000000..56fdb5c --- /dev/null +++ b/ext/kenlm @@ -0,0 +1 @@ +Subproject commit 56fdb5c44fca34d5a2e07d96139c28fb163983c5 diff --git a/ext/kenlm/util/double-conversion/fast-dtoa.h b/ext/kenlm/util/double-conversion/fast-dtoa.h deleted file mode 100644 index 5f1e8ee..0000000 --- a/ext/kenlm/util/double-conversion/fast-dtoa.h +++ /dev/null @@ -1,88 +0,0 @@ -// Copyright 2010 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#ifndef DOUBLE_CONVERSION_FAST_DTOA_H_ -#define DOUBLE_CONVERSION_FAST_DTOA_H_ - -#include "utils.h" - -namespace double_conversion { - -enum FastDtoaMode { - // Computes the shortest representation of the given input. The returned - // result will be the most accurate number of this length. Longer - // representations might be more accurate. - FAST_DTOA_SHORTEST, - // Same as FAST_DTOA_SHORTEST but for single-precision floats. - FAST_DTOA_SHORTEST_SINGLE, - // Computes a representation where the precision (number of digits) is - // given as input. The precision is independent of the decimal point. - FAST_DTOA_PRECISION -}; - -// FastDtoa will produce at most kFastDtoaMaximalLength digits. This does not -// include the terminating '\0' character. -static const int kFastDtoaMaximalLength = 17; -// Same for single-precision numbers. -static const int kFastDtoaMaximalSingleLength = 9; - -// Provides a decimal representation of v. -// The result should be interpreted as buffer * 10^(point - length). -// -// Precondition: -// * v must be a strictly positive finite double. -// -// Returns true if it succeeds, otherwise the result can not be trusted. -// There will be *length digits inside the buffer followed by a null terminator. -// If the function returns true and mode equals -// - FAST_DTOA_SHORTEST, then -// the parameter requested_digits is ignored. -// The result satisfies -// v == (double) (buffer * 10^(point - length)). -// The digits in the buffer are the shortest representation possible. E.g. -// if 0.099999999999 and 0.1 represent the same double then "1" is returned -// with point = 0. -// The last digit will be closest to the actual v. That is, even if several -// digits might correctly yield 'v' when read again, the buffer will contain -// the one closest to v. -// - FAST_DTOA_PRECISION, then -// the buffer contains requested_digits digits. -// the difference v - (buffer * 10^(point-length)) is closest to zero for -// all possible representations of requested_digits digits. -// If there are two values that are equally close, then FastDtoa returns -// false. -// For both modes the buffer must be large enough to hold the result. -bool FastDtoa(double d, - FastDtoaMode mode, - int requested_digits, - Vector<char> buffer, - int* length, - int* decimal_point); - -} // namespace double_conversion - -#endif // DOUBLE_CONVERSION_FAST_DTOA_H_ http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/6da3961b/ext/kenlm/util/double-conversion/fixed-dtoa.cc ---------------------------------------------------------------------- diff --git a/ext/kenlm b/ext/kenlm new file mode 160000 index 0000000..56fdb5c --- /dev/null +++ b/ext/kenlm @@ -0,0 +1 @@ +Subproject commit 56fdb5c44fca34d5a2e07d96139c28fb163983c5 diff --git a/ext/kenlm/util/double-conversion/fixed-dtoa.cc b/ext/kenlm/util/double-conversion/fixed-dtoa.cc deleted file mode 100644 index 7c1a952..0000000 --- a/ext/kenlm/util/double-conversion/fixed-dtoa.cc +++ /dev/null @@ -1,402 +0,0 @@ -// Copyright 2010 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#include <cmath> - -#include "fixed-dtoa.h" -#include "ieee.h" - -namespace double_conversion { - -// Represents a 128bit type. This class should be replaced by a native type on -// platforms that support 128bit integers. -class UInt128 { - public: - UInt128() : high_bits_(0), low_bits_(0) { } - UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { } - - void Multiply(uint32_t multiplicand) { - uint64_t accumulator; - - accumulator = (low_bits_ & kMask32) * multiplicand; - uint32_t part = static_cast<uint32_t>(accumulator & kMask32); - accumulator >>= 32; - accumulator = accumulator + (low_bits_ >> 32) * multiplicand; - low_bits_ = (accumulator << 32) + part; - accumulator >>= 32; - accumulator = accumulator + (high_bits_ & kMask32) * multiplicand; - part = static_cast<uint32_t>(accumulator & kMask32); - accumulator >>= 32; - accumulator = accumulator + (high_bits_ >> 32) * multiplicand; - high_bits_ = (accumulator << 32) + part; - ASSERT((accumulator >> 32) == 0); - } - - void Shift(int shift_amount) { - ASSERT(-64 <= shift_amount && shift_amount <= 64); - if (shift_amount == 0) { - return; - } else if (shift_amount == -64) { - high_bits_ = low_bits_; - low_bits_ = 0; - } else if (shift_amount == 64) { - low_bits_ = high_bits_; - high_bits_ = 0; - } else if (shift_amount <= 0) { - high_bits_ <<= -shift_amount; - high_bits_ += low_bits_ >> (64 + shift_amount); - low_bits_ <<= -shift_amount; - } else { - low_bits_ >>= shift_amount; - low_bits_ += high_bits_ << (64 - shift_amount); - high_bits_ >>= shift_amount; - } - } - - // Modifies *this to *this MOD (2^power). - // Returns *this DIV (2^power). - int DivModPowerOf2(int power) { - if (power >= 64) { - int result = static_cast<int>(high_bits_ >> (power - 64)); - high_bits_ -= static_cast<uint64_t>(result) << (power - 64); - return result; - } else { - uint64_t part_low = low_bits_ >> power; - uint64_t part_high = high_bits_ << (64 - power); - int result = static_cast<int>(part_low + part_high); - high_bits_ = 0; - low_bits_ -= part_low << power; - return result; - } - } - - bool IsZero() const { - return high_bits_ == 0 && low_bits_ == 0; - } - - int BitAt(int position) { - if (position >= 64) { - return static_cast<int>(high_bits_ >> (position - 64)) & 1; - } else { - return static_cast<int>(low_bits_ >> position) & 1; - } - } - - private: - static const uint64_t kMask32 = 0xFFFFFFFF; - // Value == (high_bits_ << 64) + low_bits_ - uint64_t high_bits_; - uint64_t low_bits_; -}; - - -static const int kDoubleSignificandSize = 53; // Includes the hidden bit. - - -static void FillDigits32FixedLength(uint32_t number, int requested_length, - Vector<char> buffer, int* length) { - for (int i = requested_length - 1; i >= 0; --i) { - buffer[(*length) + i] = '0' + number % 10; - number /= 10; - } - *length += requested_length; -} - - -static void FillDigits32(uint32_t number, Vector<char> buffer, int* length) { - int number_length = 0; - // We fill the digits in reverse order and exchange them afterwards. - while (number != 0) { - int digit = number % 10; - number /= 10; - buffer[(*length) + number_length] = '0' + digit; - number_length++; - } - // Exchange the digits. - int i = *length; - int j = *length + number_length - 1; - while (i < j) { - char tmp = buffer[i]; - buffer[i] = buffer[j]; - buffer[j] = tmp; - i++; - j--; - } - *length += number_length; -} - - -static void FillDigits64FixedLength(uint64_t number, int requested_length, - Vector<char> buffer, int* length) { - const uint32_t kTen7 = 10000000; - // For efficiency cut the number into 3 uint32_t parts, and print those. - uint32_t part2 = static_cast<uint32_t>(number % kTen7); - number /= kTen7; - uint32_t part1 = static_cast<uint32_t>(number % kTen7); - uint32_t part0 = static_cast<uint32_t>(number / kTen7); - - FillDigits32FixedLength(part0, 3, buffer, length); - FillDigits32FixedLength(part1, 7, buffer, length); - FillDigits32FixedLength(part2, 7, buffer, length); -} - - -static void FillDigits64(uint64_t number, Vector<char> buffer, int* length) { - const uint32_t kTen7 = 10000000; - // For efficiency cut the number into 3 uint32_t parts, and print those. - uint32_t part2 = static_cast<uint32_t>(number % kTen7); - number /= kTen7; - uint32_t part1 = static_cast<uint32_t>(number % kTen7); - uint32_t part0 = static_cast<uint32_t>(number / kTen7); - - if (part0 != 0) { - FillDigits32(part0, buffer, length); - FillDigits32FixedLength(part1, 7, buffer, length); - FillDigits32FixedLength(part2, 7, buffer, length); - } else if (part1 != 0) { - FillDigits32(part1, buffer, length); - FillDigits32FixedLength(part2, 7, buffer, length); - } else { - FillDigits32(part2, buffer, length); - } -} - - -static void RoundUp(Vector<char> buffer, int* length, int* decimal_point) { - // An empty buffer represents 0. - if (*length == 0) { - buffer[0] = '1'; - *decimal_point = 1; - *length = 1; - return; - } - // Round the last digit until we either have a digit that was not '9' or until - // we reached the first digit. - buffer[(*length) - 1]++; - for (int i = (*length) - 1; i > 0; --i) { - if (buffer[i] != '0' + 10) { - return; - } - buffer[i] = '0'; - buffer[i - 1]++; - } - // If the first digit is now '0' + 10, we would need to set it to '0' and add - // a '1' in front. However we reach the first digit only if all following - // digits had been '9' before rounding up. Now all trailing digits are '0' and - // we simply switch the first digit to '1' and update the decimal-point - // (indicating that the point is now one digit to the right). - if (buffer[0] == '0' + 10) { - buffer[0] = '1'; - (*decimal_point)++; - } -} - - -// The given fractionals number represents a fixed-point number with binary -// point at bit (-exponent). -// Preconditions: -// -128 <= exponent <= 0. -// 0 <= fractionals * 2^exponent < 1 -// The buffer holds the result. -// The function will round its result. During the rounding-process digits not -// generated by this function might be updated, and the decimal-point variable -// might be updated. If this function generates the digits 99 and the buffer -// already contained "199" (thus yielding a buffer of "19999") then a -// rounding-up will change the contents of the buffer to "20000". -static void FillFractionals(uint64_t fractionals, int exponent, - int fractional_count, Vector<char> buffer, - int* length, int* decimal_point) { - ASSERT(-128 <= exponent && exponent <= 0); - // 'fractionals' is a fixed-point number, with binary point at bit - // (-exponent). Inside the function the non-converted remainder of fractionals - // is a fixed-point number, with binary point at bit 'point'. - if (-exponent <= 64) { - // One 64 bit number is sufficient. - ASSERT(fractionals >> 56 == 0); - int point = -exponent; - for (int i = 0; i < fractional_count; ++i) { - if (fractionals == 0) break; - // Instead of multiplying by 10 we multiply by 5 and adjust the point - // location. This way the fractionals variable will not overflow. - // Invariant at the beginning of the loop: fractionals < 2^point. - // Initially we have: point <= 64 and fractionals < 2^56 - // After each iteration the point is decremented by one. - // Note that 5^3 = 125 < 128 = 2^7. - // Therefore three iterations of this loop will not overflow fractionals - // (even without the subtraction at the end of the loop body). At this - // time point will satisfy point <= 61 and therefore fractionals < 2^point - // and any further multiplication of fractionals by 5 will not overflow. - fractionals *= 5; - point--; - int digit = static_cast<int>(fractionals >> point); - buffer[*length] = '0' + digit; - (*length)++; - fractionals -= static_cast<uint64_t>(digit) << point; - } - // If the first bit after the point is set we have to round up. - if (((fractionals >> (point - 1)) & 1) == 1) { - RoundUp(buffer, length, decimal_point); - } - } else { // We need 128 bits. - ASSERT(64 < -exponent && -exponent <= 128); - UInt128 fractionals128 = UInt128(fractionals, 0); - fractionals128.Shift(-exponent - 64); - int point = 128; - for (int i = 0; i < fractional_count; ++i) { - if (fractionals128.IsZero()) break; - // As before: instead of multiplying by 10 we multiply by 5 and adjust the - // point location. - // This multiplication will not overflow for the same reasons as before. - fractionals128.Multiply(5); - point--; - int digit = fractionals128.DivModPowerOf2(point); - buffer[*length] = '0' + digit; - (*length)++; - } - if (fractionals128.BitAt(point - 1) == 1) { - RoundUp(buffer, length, decimal_point); - } - } -} - - -// Removes leading and trailing zeros. -// If leading zeros are removed then the decimal point position is adjusted. -static void TrimZeros(Vector<char> buffer, int* length, int* decimal_point) { - while (*length > 0 && buffer[(*length) - 1] == '0') { - (*length)--; - } - int first_non_zero = 0; - while (first_non_zero < *length && buffer[first_non_zero] == '0') { - first_non_zero++; - } - if (first_non_zero != 0) { - for (int i = first_non_zero; i < *length; ++i) { - buffer[i - first_non_zero] = buffer[i]; - } - *length -= first_non_zero; - *decimal_point -= first_non_zero; - } -} - - -bool FastFixedDtoa(double v, - int fractional_count, - Vector<char> buffer, - int* length, - int* decimal_point) { - const uint32_t kMaxUInt32 = 0xFFFFFFFF; - uint64_t significand = Double(v).Significand(); - int exponent = Double(v).Exponent(); - // v = significand * 2^exponent (with significand a 53bit integer). - // If the exponent is larger than 20 (i.e. we may have a 73bit number) then we - // don't know how to compute the representation. 2^73 ~= 9.5*10^21. - // If necessary this limit could probably be increased, but we don't need - // more. - if (exponent > 20) return false; - if (fractional_count > 20) return false; - *length = 0; - // At most kDoubleSignificandSize bits of the significand are non-zero. - // Given a 64 bit integer we have 11 0s followed by 53 potentially non-zero - // bits: 0..11*..0xxx..53*..xx - if (exponent + kDoubleSignificandSize > 64) { - // The exponent must be > 11. - // - // We know that v = significand * 2^exponent. - // And the exponent > 11. - // We simplify the task by dividing v by 10^17. - // The quotient delivers the first digits, and the remainder fits into a 64 - // bit number. - // Dividing by 10^17 is equivalent to dividing by 5^17*2^17. - const uint64_t kFive17 = UINT64_2PART_C(0xB1, A2BC2EC5); // 5^17 - uint64_t divisor = kFive17; - int divisor_power = 17; - uint64_t dividend = significand; - uint32_t quotient; - uint64_t remainder; - // Let v = f * 2^e with f == significand and e == exponent. - // Then need q (quotient) and r (remainder) as follows: - // v = q * 10^17 + r - // f * 2^e = q * 10^17 + r - // f * 2^e = q * 5^17 * 2^17 + r - // If e > 17 then - // f * 2^(e-17) = q * 5^17 + r/2^17 - // else - // f = q * 5^17 * 2^(17-e) + r/2^e - if (exponent > divisor_power) { - // We only allow exponents of up to 20 and therefore (17 - e) <= 3 - dividend <<= exponent - divisor_power; - quotient = static_cast<uint32_t>(dividend / divisor); - remainder = (dividend % divisor) << divisor_power; - } else { - divisor <<= divisor_power - exponent; - quotient = static_cast<uint32_t>(dividend / divisor); - remainder = (dividend % divisor) << exponent; - } - FillDigits32(quotient, buffer, length); - FillDigits64FixedLength(remainder, divisor_power, buffer, length); - *decimal_point = *length; - } else if (exponent >= 0) { - // 0 <= exponent <= 11 - significand <<= exponent; - FillDigits64(significand, buffer, length); - *decimal_point = *length; - } else if (exponent > -kDoubleSignificandSize) { - // We have to cut the number. - uint64_t integrals = significand >> -exponent; - uint64_t fractionals = significand - (integrals << -exponent); - if (integrals > kMaxUInt32) { - FillDigits64(integrals, buffer, length); - } else { - FillDigits32(static_cast<uint32_t>(integrals), buffer, length); - } - *decimal_point = *length; - FillFractionals(fractionals, exponent, fractional_count, - buffer, length, decimal_point); - } else if (exponent < -128) { - // This configuration (with at most 20 digits) means that all digits must be - // 0. - ASSERT(fractional_count <= 20); - buffer[0] = '\0'; - *length = 0; - *decimal_point = -fractional_count; - } else { - *decimal_point = 0; - FillFractionals(significand, exponent, fractional_count, - buffer, length, decimal_point); - } - TrimZeros(buffer, length, decimal_point); - buffer[*length] = '\0'; - if ((*length) == 0) { - // The string is empty and the decimal_point thus has no importance. Mimick - // Gay's dtoa and and set it to -fractional_count. - *decimal_point = -fractional_count; - } - return true; -} - -} // namespace double_conversion http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/6da3961b/ext/kenlm/util/double-conversion/fixed-dtoa.h ---------------------------------------------------------------------- diff --git a/ext/kenlm b/ext/kenlm new file mode 160000 index 0000000..56fdb5c --- /dev/null +++ b/ext/kenlm @@ -0,0 +1 @@ +Subproject commit 56fdb5c44fca34d5a2e07d96139c28fb163983c5 diff --git a/ext/kenlm/util/double-conversion/fixed-dtoa.h b/ext/kenlm/util/double-conversion/fixed-dtoa.h deleted file mode 100644 index 3bdd08e..0000000 --- a/ext/kenlm/util/double-conversion/fixed-dtoa.h +++ /dev/null @@ -1,56 +0,0 @@ -// Copyright 2010 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#ifndef DOUBLE_CONVERSION_FIXED_DTOA_H_ -#define DOUBLE_CONVERSION_FIXED_DTOA_H_ - -#include "utils.h" - -namespace double_conversion { - -// Produces digits necessary to print a given number with -// 'fractional_count' digits after the decimal point. -// The buffer must be big enough to hold the result plus one terminating null -// character. -// -// The produced digits might be too short in which case the caller has to fill -// the gaps with '0's. -// Example: FastFixedDtoa(0.001, 5, ...) is allowed to return buffer = "1", and -// decimal_point = -2. -// Halfway cases are rounded towards +/-Infinity (away from 0). The call -// FastFixedDtoa(0.15, 2, ...) thus returns buffer = "2", decimal_point = 0. -// The returned buffer may contain digits that would be truncated from the -// shortest representation of the input. -// -// This method only works for some parameters. If it can't handle the input it -// returns false. The output is null-terminated when the function succeeds. -bool FastFixedDtoa(double v, int fractional_count, - Vector<char> buffer, int* length, int* decimal_point); - -} // namespace double_conversion - -#endif // DOUBLE_CONVERSION_FIXED_DTOA_H_ http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/6da3961b/ext/kenlm/util/double-conversion/ieee.h ---------------------------------------------------------------------- diff --git a/ext/kenlm b/ext/kenlm new file mode 160000 index 0000000..56fdb5c --- /dev/null +++ b/ext/kenlm @@ -0,0 +1 @@ +Subproject commit 56fdb5c44fca34d5a2e07d96139c28fb163983c5 diff --git a/ext/kenlm/util/double-conversion/ieee.h b/ext/kenlm/util/double-conversion/ieee.h deleted file mode 100644 index 839dc47..0000000 --- a/ext/kenlm/util/double-conversion/ieee.h +++ /dev/null @@ -1,398 +0,0 @@ -// Copyright 2012 the V8 project authors. All rights reserved. -// Redistribution and use in source and binary forms, with or without -// modification, are permitted provided that the following conditions are -// met: -// -// * Redistributions of source code must retain the above copyright -// notice, this list of conditions and the following disclaimer. -// * Redistributions in binary form must reproduce the above -// copyright notice, this list of conditions and the following -// disclaimer in the documentation and/or other materials provided -// with the distribution. -// * Neither the name of Google Inc. nor the names of its -// contributors may be used to endorse or promote products derived -// from this software without specific prior written permission. -// -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -#ifndef DOUBLE_CONVERSION_DOUBLE_H_ -#define DOUBLE_CONVERSION_DOUBLE_H_ - -#include "diy-fp.h" - -namespace double_conversion { - -// We assume that doubles and uint64_t have the same endianness. -static uint64_t double_to_uint64(double d) { return BitCast<uint64_t>(d); } -static double uint64_to_double(uint64_t d64) { return BitCast<double>(d64); } -static uint32_t float_to_uint32(float f) { return BitCast<uint32_t>(f); } -static float uint32_to_float(uint32_t d32) { return BitCast<float>(d32); } - -// Helper functions for doubles. -class Double { - public: - static const uint64_t kSignMask = UINT64_2PART_C(0x80000000, 00000000); - static const uint64_t kExponentMask = UINT64_2PART_C(0x7FF00000, 00000000); - static const uint64_t kSignificandMask = UINT64_2PART_C(0x000FFFFF, FFFFFFFF); - static const uint64_t kHiddenBit = UINT64_2PART_C(0x00100000, 00000000); - static const int kPhysicalSignificandSize = 52; // Excludes the hidden bit. - static const int kSignificandSize = 53; - - Double() : d64_(0) {} - explicit Double(double d) : d64_(double_to_uint64(d)) {} - explicit Double(uint64_t d64) : d64_(d64) {} - explicit Double(DiyFp diy_fp) - : d64_(DiyFpToUint64(diy_fp)) {} - - // The value encoded by this Double must be greater or equal to +0.0. - // It must not be special (infinity, or NaN). - DiyFp AsDiyFp() const { - ASSERT(Sign() > 0); - ASSERT(!IsSpecial()); - return DiyFp(Significand(), Exponent()); - } - - // The value encoded by this Double must be strictly greater than 0. - DiyFp AsNormalizedDiyFp() const { - ASSERT(value() > 0.0); - uint64_t f = Significand(); - int e = Exponent(); - - // The current double could be a denormal. - while ((f & kHiddenBit) == 0) { - f <<= 1; - e--; - } - // Do the final shifts in one go. - f <<= DiyFp::kSignificandSize - kSignificandSize; - e -= DiyFp::kSignificandSize - kSignificandSize; - return DiyFp(f, e); - } - - // Returns the double's bit as uint64. - uint64_t AsUint64() const { - return d64_; - } - - // Returns the next greater double. Returns +infinity on input +infinity. - double NextDouble() const { - if (d64_ == kInfinity) return Double(kInfinity).value(); - if (Sign() < 0 && Significand() == 0) { - // -0.0 - return 0.0; - } - if (Sign() < 0) { - return Double(d64_ - 1).value(); - } else { - return Double(d64_ + 1).value(); - } - } - - double PreviousDouble() const { - if (d64_ == (kInfinity | kSignMask)) return -Double::Infinity(); - if (Sign() < 0) { - return Double(d64_ + 1).value(); - } else { - if (Significand() == 0) return -0.0; - return Double(d64_ - 1).value(); - } - } - - int Exponent() const { - if (IsDenormal()) return kDenormalExponent; - - uint64_t d64 = AsUint64(); - int biased_e = - static_cast<int>((d64 & kExponentMask) >> kPhysicalSignificandSize); - return biased_e - kExponentBias; - } - - uint64_t Significand() const { - uint64_t d64 = AsUint64(); - uint64_t significand = d64 & kSignificandMask; - if (!IsDenormal()) { - return significand + kHiddenBit; - } else { - return significand; - } - } - - // Returns true if the double is a denormal. - bool IsDenormal() const { - uint64_t d64 = AsUint64(); - return (d64 & kExponentMask) == 0; - } - - // We consider denormals not to be special. - // Hence only Infinity and NaN are special. - bool IsSpecial() const { - uint64_t d64 = AsUint64(); - return (d64 & kExponentMask) == kExponentMask; - } - - bool IsNan() const { - uint64_t d64 = AsUint64(); - return ((d64 & kExponentMask) == kExponentMask) && - ((d64 & kSignificandMask) != 0); - } - - bool IsInfinite() const { - uint64_t d64 = AsUint64(); - return ((d64 & kExponentMask) == kExponentMask) && - ((d64 & kSignificandMask) == 0); - } - - int Sign() const { - uint64_t d64 = AsUint64(); - return (d64 & kSignMask) == 0? 1: -1; - } - - // Precondition: the value encoded by this Double must be greater or equal - // than +0.0. - DiyFp UpperBoundary() const { - ASSERT(Sign() > 0); - return DiyFp(Significand() * 2 + 1, Exponent() - 1); - } - - // Computes the two boundaries of this. - // The bigger boundary (m_plus) is normalized. The lower boundary has the same - // exponent as m_plus. - // Precondition: the value encoded by this Double must be greater than 0. - void NormalizedBoundaries(DiyFp* out_m_minus, DiyFp* out_m_plus) const { - ASSERT(value() > 0.0); - DiyFp v = this->AsDiyFp(); - DiyFp m_plus = DiyFp::Normalize(DiyFp((v.f() << 1) + 1, v.e() - 1)); - DiyFp m_minus; - if (LowerBoundaryIsCloser()) { - m_minus = DiyFp((v.f() << 2) - 1, v.e() - 2); - } else { - m_minus = DiyFp((v.f() << 1) - 1, v.e() - 1); - } - m_minus.set_f(m_minus.f() << (m_minus.e() - m_plus.e())); - m_minus.set_e(m_plus.e()); - *out_m_plus = m_plus; - *out_m_minus = m_minus; - } - - bool LowerBoundaryIsCloser() const { - // The boundary is closer if the significand is of the form f == 2^p-1 then - // the lower boundary is closer. - // Think of v = 1000e10 and v- = 9999e9. - // Then the boundary (== (v - v-)/2) is not just at a distance of 1e9 but - // at a distance of 1e8. - // The only exception is for the smallest normal: the largest denormal is - // at the same distance as its successor. - // Note: denormals have the same exponent as the smallest normals. - bool physical_significand_is_zero = ((AsUint64() & kSignificandMask) == 0); - return physical_significand_is_zero && (Exponent() != kDenormalExponent); - } - - double value() const { return uint64_to_double(d64_); } - - // Returns the significand size for a given order of magnitude. - // If v = f*2^e with 2^p-1 <= f <= 2^p then p+e is v's order of magnitude. - // This function returns the number of significant binary digits v will have - // once it's encoded into a double. In almost all cases this is equal to - // kSignificandSize. The only exceptions are denormals. They start with - // leading zeroes and their effective significand-size is hence smaller. - static int SignificandSizeForOrderOfMagnitude(int order) { - if (order >= (kDenormalExponent + kSignificandSize)) { - return kSignificandSize; - } - if (order <= kDenormalExponent) return 0; - return order - kDenormalExponent; - } - - static double Infinity() { - return Double(kInfinity).value(); - } - - static double NaN() { - return Double(kNaN).value(); - } - - private: - static const int kExponentBias = 0x3FF + kPhysicalSignificandSize; - static const int kDenormalExponent = -kExponentBias + 1; - static const int kMaxExponent = 0x7FF - kExponentBias; - static const uint64_t kInfinity = UINT64_2PART_C(0x7FF00000, 00000000); - static const uint64_t kNaN = UINT64_2PART_C(0x7FF80000, 00000000); - - const uint64_t d64_; - - static uint64_t DiyFpToUint64(DiyFp diy_fp) { - uint64_t significand = diy_fp.f(); - int exponent = diy_fp.e(); - while (significand > kHiddenBit + kSignificandMask) { - significand >>= 1; - exponent++; - } - if (exponent >= kMaxExponent) { - return kInfinity; - } - if (exponent < kDenormalExponent) { - return 0; - } - while (exponent > kDenormalExponent && (significand & kHiddenBit) == 0) { - significand <<= 1; - exponent--; - } - uint64_t biased_exponent; - if (exponent == kDenormalExponent && (significand & kHiddenBit) == 0) { - biased_exponent = 0; - } else { - biased_exponent = static_cast<uint64_t>(exponent + kExponentBias); - } - return (significand & kSignificandMask) | - (biased_exponent << kPhysicalSignificandSize); - } -}; - -class Single { - public: - static const uint32_t kSignMask = 0x80000000; - static const uint32_t kExponentMask = 0x7F800000; - static const uint32_t kSignificandMask = 0x007FFFFF; - static const uint32_t kHiddenBit = 0x00800000; - static const int kPhysicalSignificandSize = 23; // Excludes the hidden bit. - static const int kSignificandSize = 24; - - Single() : d32_(0) {} - explicit Single(float f) : d32_(float_to_uint32(f)) {} - explicit Single(uint32_t d32) : d32_(d32) {} - - // The value encoded by this Single must be greater or equal to +0.0. - // It must not be special (infinity, or NaN). - DiyFp AsDiyFp() const { - ASSERT(Sign() > 0); - ASSERT(!IsSpecial()); - return DiyFp(Significand(), Exponent()); - } - - // Returns the single's bit as uint64. - uint32_t AsUint32() const { - return d32_; - } - - int Exponent() const { - if (IsDenormal()) return kDenormalExponent; - - uint32_t d32 = AsUint32(); - int biased_e = - static_cast<int>((d32 & kExponentMask) >> kPhysicalSignificandSize); - return biased_e - kExponentBias; - } - - uint32_t Significand() const { - uint32_t d32 = AsUint32(); - uint32_t significand = d32 & kSignificandMask; - if (!IsDenormal()) { - return significand + kHiddenBit; - } else { - return significand; - } - } - - // Returns true if the single is a denormal. - bool IsDenormal() const { - uint32_t d32 = AsUint32(); - return (d32 & kExponentMask) == 0; - } - - // We consider denormals not to be special. - // Hence only Infinity and NaN are special. - bool IsSpecial() const { - uint32_t d32 = AsUint32(); - return (d32 & kExponentMask) == kExponentMask; - } - - bool IsNan() const { - uint32_t d32 = AsUint32(); - return ((d32 & kExponentMask) == kExponentMask) && - ((d32 & kSignificandMask) != 0); - } - - bool IsInfinite() const { - uint32_t d32 = AsUint32(); - return ((d32 & kExponentMask) == kExponentMask) && - ((d32 & kSignificandMask) == 0); - } - - int Sign() const { - uint32_t d32 = AsUint32(); - return (d32 & kSignMask) == 0? 1: -1; - } - - // Computes the two boundaries of this. - // The bigger boundary (m_plus) is normalized. The lower boundary has the same - // exponent as m_plus. - // Precondition: the value encoded by this Single must be greater than 0. - void NormalizedBoundaries(DiyFp* out_m_minus, DiyFp* out_m_plus) const { - ASSERT(value() > 0.0); - DiyFp v = this->AsDiyFp(); - DiyFp m_plus = DiyFp::Normalize(DiyFp((v.f() << 1) + 1, v.e() - 1)); - DiyFp m_minus; - if (LowerBoundaryIsCloser()) { - m_minus = DiyFp((v.f() << 2) - 1, v.e() - 2); - } else { - m_minus = DiyFp((v.f() << 1) - 1, v.e() - 1); - } - m_minus.set_f(m_minus.f() << (m_minus.e() - m_plus.e())); - m_minus.set_e(m_plus.e()); - *out_m_plus = m_plus; - *out_m_minus = m_minus; - } - - // Precondition: the value encoded by this Single must be greater or equal - // than +0.0. - DiyFp UpperBoundary() const { - ASSERT(Sign() > 0); - return DiyFp(Significand() * 2 + 1, Exponent() - 1); - } - - bool LowerBoundaryIsCloser() const { - // The boundary is closer if the significand is of the form f == 2^p-1 then - // the lower boundary is closer. - // Think of v = 1000e10 and v- = 9999e9. - // Then the boundary (== (v - v-)/2) is not just at a distance of 1e9 but - // at a distance of 1e8. - // The only exception is for the smallest normal: the largest denormal is - // at the same distance as its successor. - // Note: denormals have the same exponent as the smallest normals. - bool physical_significand_is_zero = ((AsUint32() & kSignificandMask) == 0); - return physical_significand_is_zero && (Exponent() != kDenormalExponent); - } - - float value() const { return uint32_to_float(d32_); } - - static float Infinity() { - return Single(kInfinity).value(); - } - - static float NaN() { - return Single(kNaN).value(); - } - - private: - static const int kExponentBias = 0x7F + kPhysicalSignificandSize; - static const int kDenormalExponent = -kExponentBias + 1; - static const int kMaxExponent = 0xFF - kExponentBias; - static const uint32_t kInfinity = 0x7F800000; - static const uint32_t kNaN = 0x7FC00000; - - const uint32_t d32_; -}; - -} // namespace double_conversion - -#endif // DOUBLE_CONVERSION_DOUBLE_H_
