bigint.h | Explore in Territory

// Copyright 2021 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_BIGINT_BIGINT_H_
#define V8_BIGINT_BIGINT_H_

#include <stdint.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

namespace v8 {
namespace bigint {

// To play nice with embedders' macros, we define our own DCHECK here.
// It's only used in this file, and undef'ed at the end.
#ifdef DEBUG
#define BIGINT_H_DCHECK …

extern bool kAdvancedAlgorithmsEnabledInLibrary;
#else
#define BIGINT_H_DCHECK …
#endif

// The type of a digit: a register-width unsigned integer.
digit_t;
signed_digit_t;
#if UINTPTR_MAX == 0xFFFFFFFF
// 32-bit platform.
using twodigit_t = uint64_t;
#define HAVE_TWODIGIT_T …
static constexpr int kLog2DigitBits = 5;
#elif UINTPTR_MAX == 0xFFFFFFFFFFFFFFFF
// 64-bit platform.
static constexpr int kLog2DigitBits = …;
#if defined(__SIZEOF_INT128__)
twodigit_t;
#define HAVE_TWODIGIT_T …
#endif  // defined(__SIZEOF_INT128__)
#else
#error Unsupported platform.
#endif
static constexpr int kDigitBits = …;
static_assert …;

// Describes an array of digits, also known as a BigInt. Unsigned.
// Does not own the memory it points at, and only gives read-only access to it.
// Digits are stored in little-endian order.
class Digits { … };

// Writable version of a Digits array.
// Does not own the memory it points at.
class RWDigits : public Digits { … };

class Platform { … };

// These are the operations that this library supports.
// The signatures follow the convention:
//
//   void Operation(RWDigits results, Digits inputs);
//
// You must preallocate the result; use the respective {OperationResultLength}
// function to determine its minimum required length. The actual result may
// be smaller, so you should call result.Normalize() on the result.
//
// The operations are divided into two groups: "fast" (O(n) with small
// coefficient) operations are exposed directly as free functions, "slow"
// operations are methods on a {Processor} object, which provides
// support for interrupting execution via the {Platform}'s {InterruptRequested}
// mechanism when it takes too long. These functions return a {Status} value.

// Returns r such that r < 0 if A < B; r > 0 if A > B; r == 0 if A == B.
// Defined here to be inlineable, which helps ia32 a lot (64-bit platforms
// don't care).
inline int Compare(Digits A, Digits B) { … }

// Z := X + Y
void Add(RWDigits Z, Digits X, Digits Y);
// Addition of signed integers. Returns true if the result is negative.
bool AddSigned(RWDigits Z, Digits X, bool x_negative, Digits Y,
               bool y_negative);
// Z := X + 1
void AddOne(RWDigits Z, Digits X);

// Z := X - Y. Requires X >= Y.
void Subtract(RWDigits Z, Digits X, Digits Y);
// Subtraction of signed integers. Returns true if the result is negative.
bool SubtractSigned(RWDigits Z, Digits X, bool x_negative, Digits Y,
                    bool y_negative);
// Z := X - 1
void SubtractOne(RWDigits Z, Digits X);

// The bitwise operations assume that negative BigInts are represented as
// sign+magnitude. Their behavior depends on the sign of the inputs: negative
// inputs perform an implicit conversion to two's complement representation.
// Z := X & Y
void BitwiseAnd_PosPos(RWDigits Z, Digits X, Digits Y);
// Call this for a BigInt x = (magnitude=X, negative=true).
void BitwiseAnd_NegNeg(RWDigits Z, Digits X, Digits Y);
// Positive X, negative Y. Callers must swap arguments as needed.
void BitwiseAnd_PosNeg(RWDigits Z, Digits X, Digits Y);
void BitwiseOr_PosPos(RWDigits Z, Digits X, Digits Y);
void BitwiseOr_NegNeg(RWDigits Z, Digits X, Digits Y);
void BitwiseOr_PosNeg(RWDigits Z, Digits X, Digits Y);
void BitwiseXor_PosPos(RWDigits Z, Digits X, Digits Y);
void BitwiseXor_NegNeg(RWDigits Z, Digits X, Digits Y);
void BitwiseXor_PosNeg(RWDigits Z, Digits X, Digits Y);
void LeftShift(RWDigits Z, Digits X, digit_t shift);
// RightShiftState is provided by RightShift_ResultLength and used by the actual
// RightShift to avoid some recomputation.
struct RightShiftState { … };
void RightShift(RWDigits Z, Digits X, digit_t shift,
                const RightShiftState& state);

// Z := (least significant n bits of X, interpreted as a signed n-bit integer).
// Returns true if the result is negative; Z will hold the absolute value.
bool AsIntN(RWDigits Z, Digits X, bool x_negative, int n);
// Z := (least significant n bits of X).
void AsUintN_Pos(RWDigits Z, Digits X, int n);
// Same, but X is the absolute value of a negative BigInt.
void AsUintN_Neg(RWDigits Z, Digits X, int n);

enum class Status { … };

class FromStringAccumulator;

class Processor { … };

inline int AddResultLength(int x_length, int y_length) { … }
inline int AddSignedResultLength(int x_length, int y_length, bool same_sign) { … }
inline int SubtractResultLength(int x_length, int y_length) { … }
inline int SubtractSignedResultLength(int x_length, int y_length,
                                      bool same_sign) { … }
inline int MultiplyResultLength(Digits X, Digits Y) { … }
constexpr int kBarrettThreshold = …;
inline int DivideResultLength(Digits A, Digits B) { … }
inline int ModuloResultLength(Digits B) { … }

int ToStringResultLength(Digits X, int radix, bool sign);
// In DEBUG builds, the result of {ToString} will be initialized to this value.
constexpr char kStringZapValue = …;

int RightShift_ResultLength(Digits X, bool x_sign, digit_t shift,
                            RightShiftState* state);

// Returns -1 if this "asIntN" operation would be a no-op.
int AsIntNResultLength(Digits X, bool x_negative, int n);
// Returns -1 if this "asUintN" operation would be a no-op.
int AsUintN_Pos_ResultLength(Digits X, int n);
inline int AsUintN_Neg_ResultLength(int n) { … }

// Support for parsing BigInts from Strings, using an Accumulator object
// for intermediate state.

class ProcessorImpl;

#if !defined(DEBUG) && (defined(__GNUC__) || defined(__clang__))
// Clang supports this since 3.9, GCC since 4.x.
#define ALWAYS_INLINE …
#elif !defined(DEBUG) && defined(_MSC_VER)
#define ALWAYS_INLINE …
#else
#define ALWAYS_INLINE …
#endif

static constexpr int kStackParts = …;

// A container object for all metadata required for parsing a BigInt from
// a string.
// Aggressively optimized not to waste instructions for small cases, while
// also scaling transparently to huge cases.
// Defined here in the header so that it can be inlined.
class FromStringAccumulator { … };

// The rest of this file is the inlineable implementation of
// FromStringAccumulator methods.

#if defined(__GNUC__) || defined(__clang__)
// Clang supports this since 3.9, GCC since 5.x.
#define HAVE_BUILTIN_MUL_OVERFLOW …
#else
#define HAVE_BUILTIN_MUL_OVERFLOW …
#endif

// Numerical value of the first 127 ASCII characters, using 255 as sentinel
// for "invalid".
static constexpr uint8_t kCharValue[] = …;

// A space- and time-efficient way to map {2,4,8,16,32} to {1,2,3,4,5}.
static constexpr uint8_t kCharBits[] = …;

template <class CharIt>
CharIt FromStringAccumulator::ParsePowerTwo(CharIt current, CharIt end,
                                            digit_t radix) { … }

template <class CharIt>
CharIt FromStringAccumulator::Parse(CharIt start, CharIt end, digit_t radix) { … }

bool FromStringAccumulator::AddPart(digit_t multiplier, digit_t part,
                                    bool is_last) { … }

bool FromStringAccumulator::AddPart(digit_t part) { … }

}  // namespace bigint
}  // namespace v8

#undef BIGINT_H_DCHECK
#undef ALWAYS_INLINE
#undef HAVE_BUILTIN_MUL_OVERFLOW

#endif  // V8_BIGINT_BIGINT_H_
chromium/v8/src/bigint/bigint.h
