1// Copyright 2021 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_BIGINT_DIV_HELPERS_H_
6#define V8_BIGINT_DIV_HELPERS_H_
7
8#include <memory>
9
10#include "src/bigint/bigint.h"
11#include "src/bigint/util.h"
12
13namespace v8 {
14namespace bigint {
15
16void LeftShift(RWDigits Z, Digits X, int shift);
17void RightShift(RWDigits Z, Digits X, int shift);
18
19inline void PutAt(RWDigits Z, Digits A, int count) {
20  int len = std::min(A.len(), count);
21  int i = 0;
22  for (; i < len; i++) Z[i] = A[i];
23  for (; i < count; i++) Z[i] = 0;
24}
25
26// Division algorithms typically need to left-shift their inputs into
27// "bit-normalized" form (i.e. top bit is set). The inputs are considered
28// read-only, and V8 relies on that by allowing concurrent reads from them,
29// so by default, {ShiftedDigits} allocate temporary storage for their
30// contents. In-place modification is opt-in for cases where callers can
31// guarantee that it is safe.
32// When callers allow in-place shifting and wish to undo it, they have to do
33// so manually using {Reset()}.
34// If {shift} is not given, it is auto-detected from {original}'s
35// leading zeros.
36class ShiftedDigits : public Digits {
37 public:
38  explicit ShiftedDigits(Digits& original, int shift = -1,
39                         bool allow_inplace = false)
40      : Digits(original.digits_, original.len_) {
41    int leading_zeros = CountLeadingZeros(original.msd());
42    if (shift < 0) {
43      shift = leading_zeros;
44    } else if (shift > leading_zeros) {
45      allow_inplace = false;
46      len_++;
47    }
48    shift_ = shift;
49    if (shift == 0) {
50      inplace_ = true;
51      return;
52    }
53    inplace_ = allow_inplace;
54    if (!inplace_) {
55      digit_t* digits = new digit_t[len_];
56      storage_.reset(digits);
57      digits_ = digits;
58    }
59    RWDigits rw_view(digits_, len_);
60    LeftShift(rw_view, original, shift_);
61  }
62  ~ShiftedDigits() = default;
63
64  void Reset() {
65    if (inplace_) {
66      RWDigits rw_view(digits_, len_);
67      RightShift(rw_view, rw_view, shift_);
68    }
69  }
70
71  int shift() { return shift_; }
72
73 private:
74  int shift_;
75  bool inplace_;
76  std::unique_ptr<digit_t[]> storage_;
77};
78
79}  // namespace bigint
80}  // namespace v8
81
82#endif  // V8_BIGINT_DIV_HELPERS_H_
83