chromium/v8/src/bigint/div-burnikel.cc

// 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.

// Burnikel-Ziegler division.
// Reference: "Fast Recursive Division" by Christoph Burnikel and Joachim
// Ziegler, found at http://cr.yp.to/bib/1998/burnikel.ps

#include <string.h>

#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 {

namespace {

// Compares [a_high, A] with B.
// Returns:
// - a value < 0 if [a_high, A] < B
// - 0           if [a_high, A] == B
// - a value > 0 if [a_high, A] > B.
int SpecialCompare(digit_t a_high, Digits A, Digits B) { … }

void SetOnes(RWDigits X) { … }

// Since the Burnikel-Ziegler method is inherently recursive, we put
// non-changing data into a container object.
class BZ { … };

void BZ::DivideBasecase(RWDigits Q, RWDigits R, Digits A, Digits B) { … }

// Algorithm 2 from the paper. Variable names same as there.
// Returns Q(uotient) and R(emainder) for A/B, with B having two thirds
// the size of A = [A1, A2, A3].
void BZ::D3n2n(RWDigits Q, RWDigits R, Digits A1A2, Digits A3, Digits B) { … }

// Algorithm 1 from the paper. Variable names same as there.
// Returns Q(uotient) and (R)emainder for A/B, with A twice the size of B.
void BZ::D2n1n(RWDigits Q, RWDigits R, Digits A, Digits B) { … }

}  // namespace

// Algorithm 3 from the paper. Variables names same as there.
// Returns Q(uotient) and R(emainder) for A/B (no size restrictions).
// R is optional, Q is not.
void ProcessorImpl::DivideBurnikelZiegler(RWDigits Q, RWDigits R, Digits A,
                                          Digits B) { … }

}  // namespace bigint
}  // namespace v8