tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Int96.h (4546B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #ifndef builtin_temporal_Int96_h
      8 #define builtin_temporal_Int96_h
      9 
     10 #include "mozilla/Assertions.h"
     11 #include "mozilla/MathAlgorithms.h"
     12 #include "mozilla/Maybe.h"
     13 
     14 #include <array>
     15 #include <climits>
     16 #include <stddef.h>
     17 #include <stdint.h>
     18 #include <utility>
     19 
     20 namespace js::temporal {
     21 
     22 /**
     23 * 96-bit integer with explicit sign. Supports integers in the range
     24 * [-(2**96 - 1), 2**96 - 1].
     25 */
     26 class Int96 final {
     27 public:
     28  using Digit = uint32_t;
     29  using TwoDigit = uint64_t;
     30 
     31  // The 96-bit integer is stored as three separate 32-bit integers.
     32  using Digits = std::array<Digit, 3>;
     33 
     34 private:
     35  // Unsigned number in the range [0, 0xffff'ffff'ffff'ffff'ffff'ffff].
     36  //
     37  // The least significant digit is stored at index 0. The most significant
     38  // digit is stored at index 2.
     39  Digits digits = {};
     40 
     41  // Explicit negative sign.
     42  bool negative = false;
     43 
     44 public:
     45  // Default constructor initializes to zero.
     46  constexpr Int96() = default;
     47 
     48  // Create from an 64-bit integer.
     49  constexpr explicit Int96(int64_t value) : negative(value < 0) {
     50    // NB: Not std::abs, because std::abs(INT64_MIN) is undefined behavior.
     51    uint64_t abs = mozilla::Abs(value);
     52    digits[1] = uint32_t(abs >> 32);
     53    digits[0] = uint32_t(abs);
     54  }
     55 
     56  constexpr Int96(Digits digits, bool negative)
     57      : digits(digits), negative(negative) {
     58    // Assert zero is non-negative.
     59    MOZ_ASSERT_IF((digits[0] | digits[1] | digits[2]) == 0, !negative);
     60  }
     61 
     62  constexpr bool operator==(const Int96& other) const {
     63    return digits[0] == other.digits[0] && digits[1] == other.digits[1] &&
     64           digits[2] == other.digits[2] && negative == other.negative;
     65  }
     66 
     67  constexpr bool operator<(const Int96& other) const {
     68    if (negative != other.negative) {
     69      return negative;
     70    }
     71    for (size_t i = digits.size(); i != 0; --i) {
     72      Digit x = digits[i - 1];
     73      Digit y = other.digits[i - 1];
     74      if (x != y) {
     75        return negative ? x > y : x < y;
     76      }
     77    }
     78    return false;
     79  }
     80 
     81  // Other operators are implemented in terms of operator== and operator<.
     82  constexpr bool operator!=(const Int96& other) const {
     83    return !(*this == other);
     84  }
     85  constexpr bool operator>(const Int96& other) const { return other < *this; }
     86  constexpr bool operator<=(const Int96& other) const {
     87    return !(other < *this);
     88  }
     89  constexpr bool operator>=(const Int96& other) const {
     90    return !(*this < other);
     91  }
     92 
     93  /**
     94   * Multiply this integer with an multiplier. Overflow is not supported.
     95   */
     96  constexpr Int96& operator*=(Digit multiplier) {
     97    Digit carry = 0;
     98    for (auto& digit : digits) {
     99      TwoDigit d = digit;
    100      d *= multiplier;
    101      d += carry;
    102 
    103      digit = Digit(d);
    104      carry = Digit(d >> 32);
    105    }
    106    MOZ_ASSERT(carry == 0, "unsupported overflow");
    107 
    108    return *this;
    109  }
    110 
    111  /**
    112   * Multiply this integer with an multiplier. Overflow is not supported.
    113   */
    114  constexpr Int96 operator*(Digit multiplier) const {
    115    auto result = *this;
    116    result *= multiplier;
    117    return result;
    118  }
    119 
    120  /**
    121   * Divide this integer by the divisor using Euclidean division. The divisor
    122   * must be smaller than the most significant digit of the integer. Returns the
    123   * quotient and the remainder.
    124   */
    125  constexpr std::pair<int64_t, int32_t> operator/(Digit divisor) const {
    126    MOZ_ASSERT(digits[2] < divisor, "unsupported divisor");
    127 
    128    Digit quotient[2] = {};
    129    Digit remainder = digits[2];
    130    for (int32_t i = 1; i >= 0; i--) {
    131      TwoDigit n = (TwoDigit(remainder) << 32) | digits[i];
    132      quotient[i] = n / divisor;
    133      remainder = n % divisor;
    134    }
    135 
    136    int64_t result = int64_t((TwoDigit(quotient[1]) << 32) | quotient[0]);
    137    if (negative) {
    138      result *= -1;
    139      if (remainder != 0) {
    140        result -= 1;
    141        remainder = divisor - remainder;
    142      }
    143    }
    144    return {result, int32_t(remainder)};
    145  }
    146 
    147  /**
    148   * Return the absolute value of this integer.
    149   */
    150  constexpr Int96 abs() const { return {digits, false}; }
    151 
    152  /**
    153   * Return Some(Int96) if the integer value fits into a 96-bit integer.
    154   * Otherwise returns Nothing().
    155   */
    156  static mozilla::Maybe<Int96> fromInteger(double value);
    157 };
    158 
    159 } /* namespace js::temporal */
    160 
    161 #endif /* builtin_temporal_Int96_h */