div-schoolbook.cc | 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.

// "Schoolbook" division. This is loosely based on Go's implementation
// found at https://golang.org/src/math/big/nat.go, licensed as follows:
//
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file [1].
//
// [1] https://golang.org/LICENSE

#include <limits>

#include "src/bigint/bigint-internal.h"
#include "src/bigint/digit-arithmetic.h"
#include "src/bigint/div-helpers.h"
#include "src/bigint/util.h"
#include "src/bigint/vector-arithmetic.h"

namespace v8 {
namespace bigint {

// Computes Q(uotient) and remainder for A/b, such that
// Q = (A - remainder) / b, with 0 <= remainder < b.
// If Q.len == 0, only the remainder will be returned.
// Q may be the same as A for an in-place division.
void ProcessorImpl::DivideSingle(RWDigits Q, digit_t* remainder, Digits A,
                                 digit_t b) { … }

// Z += X. Returns the "carry" (0 or 1) after adding all of X's digits.
inline digit_t InplaceAdd(RWDigits Z, Digits X) { … }

// Z -= X. Returns the "borrow" (0 or 1) after subtracting all of X's digits.
inline digit_t InplaceSub(RWDigits Z, Digits X) { … }

// Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
                        digit_t low) { … }

#if DEBUG
bool QLengthOK(Digits Q, Digits A, Digits B) { … }
#endif

// Computes Q(uotient) and R(emainder) for A/B, such that
// Q = (A - R) / B, with 0 <= R < B.
// Both Q and R are optional: callers that are only interested in one of them
// can pass the other with len == 0.
// If Q is present, its length must be at least A.len - B.len + 1.
// If R is present, its length must be at least B.len.
// See Knuth, Volume 2, section 4.3.1, Algorithm D.
void ProcessorImpl::DivideSchoolbook(RWDigits Q, RWDigits R, Digits A,
                                     Digits B) { … }

}  // namespace bigint
}  // namespace v8
chromium/v8/src/bigint/div-schoolbook.cc
