bigint-internal.cc 3.77 KB
Newer Older
1 2 3 4 5 6 7 8 9
// 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.

#include "src/bigint/bigint-internal.h"

namespace v8 {
namespace bigint {

10 11 12 13 14 15 16 17 18
// Used for checking consistency between library and public header.
#if DEBUG
#if V8_ADVANCED_BIGINT_ALGORITHMS
bool kAdvancedAlgorithmsEnabledInLibrary = true;
#else
bool kAdvancedAlgorithmsEnabledInLibrary = false;
#endif  // V8_ADVANCED_BIGINT_ALGORITHMS
#endif  // DEBUG

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
ProcessorImpl::ProcessorImpl(Platform* platform) : platform_(platform) {}

ProcessorImpl::~ProcessorImpl() { delete platform_; }

Status ProcessorImpl::get_and_clear_status() {
  Status result = status_;
  status_ = Status::kOk;
  return result;
}

Processor* Processor::New(Platform* platform) {
  ProcessorImpl* impl = new ProcessorImpl(platform);
  return static_cast<Processor*>(impl);
}

void Processor::Destroy() { delete static_cast<ProcessorImpl*>(this); }

void ProcessorImpl::Multiply(RWDigits Z, Digits X, Digits Y) {
  X.Normalize();
  Y.Normalize();
  if (X.len() == 0 || Y.len() == 0) return Z.Clear();
  if (X.len() < Y.len()) std::swap(X, Y);
  if (Y.len() == 1) return MultiplySingle(Z, X, Y[0]);
42
  if (Y.len() < kKaratsubaThreshold) return MultiplySchoolbook(Z, X, Y);
43
#if !V8_ADVANCED_BIGINT_ALGORITHMS
44
  return MultiplyKaratsuba(Z, X, Y);
45 46
#else
  if (Y.len() < kToomThreshold) return MultiplyKaratsuba(Z, X, Y);
47 48
  if (Y.len() < kFftThreshold) return MultiplyToomCook(Z, X, Y);
  return MultiplyFFT(Z, X, Y);
49
#endif
50 51
}

52 53 54
void ProcessorImpl::Divide(RWDigits Q, Digits A, Digits B) {
  A.Normalize();
  B.Normalize();
55
  DCHECK(B.len() > 0);
56 57 58 59 60 61 62 63 64 65 66
  int cmp = Compare(A, B);
  if (cmp < 0) return Q.Clear();
  if (cmp == 0) {
    Q[0] = 1;
    for (int i = 1; i < Q.len(); i++) Q[i] = 0;
    return;
  }
  if (B.len() == 1) {
    digit_t remainder;
    return DivideSingle(Q, &remainder, A, B[0]);
  }
67 68 69
  if (B.len() < kBurnikelThreshold) {
    return DivideSchoolbook(Q, RWDigits(nullptr, 0), A, B);
  }
70
#if !V8_ADVANCED_BIGINT_ALGORITHMS
71
  return DivideBurnikelZiegler(Q, RWDigits(nullptr, 0), A, B);
72 73 74 75 76 77 78 79
#else
  if (B.len() < kBarrettThreshold || A.len() == B.len()) {
    DivideBurnikelZiegler(Q, RWDigits(nullptr, 0), A, B);
  } else {
    ScratchDigits R(B.len());
    DivideBarrett(Q, R, A, B);
  }
#endif
80 81 82 83 84
}

void ProcessorImpl::Modulo(RWDigits R, Digits A, Digits B) {
  A.Normalize();
  B.Normalize();
85
  DCHECK(B.len() > 0);
86 87 88 89 90 91 92 93 94 95 96 97 98 99
  int cmp = Compare(A, B);
  if (cmp < 0) {
    for (int i = 0; i < B.len(); i++) R[i] = B[i];
    for (int i = B.len(); i < R.len(); i++) R[i] = 0;
    return;
  }
  if (cmp == 0) return R.Clear();
  if (B.len() == 1) {
    digit_t remainder;
    DivideSingle(RWDigits(nullptr, 0), &remainder, A, B[0]);
    R[0] = remainder;
    for (int i = 1; i < R.len(); i++) R[i] = 0;
    return;
  }
100 101 102 103 104
  if (B.len() < kBurnikelThreshold) {
    return DivideSchoolbook(RWDigits(nullptr, 0), R, A, B);
  }
  int q_len = DivideResultLength(A, B);
  ScratchDigits Q(q_len);
105
#if !V8_ADVANCED_BIGINT_ALGORITHMS
106
  return DivideBurnikelZiegler(Q, R, A, B);
107 108 109 110 111 112 113
#else
  if (B.len() < kBarrettThreshold || A.len() == B.len()) {
    DivideBurnikelZiegler(Q, R, A, B);
  } else {
    DivideBarrett(Q, R, A, B);
  }
#endif
114 115
}

116 117 118 119 120 121
Status Processor::Multiply(RWDigits Z, Digits X, Digits Y) {
  ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
  impl->Multiply(Z, X, Y);
  return impl->get_and_clear_status();
}

122 123 124 125 126 127 128 129 130 131 132 133
Status Processor::Divide(RWDigits Q, Digits A, Digits B) {
  ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
  impl->Divide(Q, A, B);
  return impl->get_and_clear_status();
}

Status Processor::Modulo(RWDigits R, Digits A, Digits B) {
  ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
  impl->Modulo(R, A, B);
  return impl->get_and_clear_status();
}

134 135
}  // namespace bigint
}  // namespace v8