src/bigint/div-helpers.h

// 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_DIV_HELPERS_H_
#define V8_BIGINT_DIV_HELPERS_H_

#include <memory>

#include "src/bigint/bigint.h"
#include "src/bigint/util.h"

namespace v8 {
namespace bigint {

void LeftShift(RWDigits Z, Digits X, int shift);
void RightShift(RWDigits Z, Digits X, int shift);

inline void PutAt(RWDigits Z, Digits A, int count) {
  int len = std::min(A.len(), count);
  int i = 0;
  for (; i < len; i++) Z[i] = A[i];
  for (; i < count; i++) Z[i] = 0;
}

// Division algorithms typically need to left-shift their inputs into
// "bit-normalized" form (i.e. top bit is set). The inputs are considered
// read-only, and V8 relies on that by allowing concurrent reads from them,
// so by default, {ShiftedDigits} allocate temporary storage for their
// contents. In-place modification is opt-in for cases where callers can
// guarantee that it is safe.
// When callers allow in-place shifting and wish to undo it, they have to do
// so manually using {Reset()}.
// If {shift} is not given, it is auto-detected from {original}'s
// leading zeros.
class ShiftedDigits : public Digits {
 public:
  explicit ShiftedDigits(Digits& original, int shift = -1,
                         bool allow_inplace = false)
      : Digits(original.digits_, original.len_) {
    int leading_zeros = CountLeadingZeros(original.msd());
    if (shift < 0) {
      shift = leading_zeros;
    } else if (shift > leading_zeros) {
      allow_inplace = false;
      len_++;
    }
    shift_ = shift;
    if (shift == 0) {
      inplace_ = true;
      return;
    }
    inplace_ = allow_inplace;
    if (!inplace_) {
      digit_t* digits = new digit_t[len_];
      storage_.reset(digits);
      digits_ = digits;
    }
    RWDigits rw_view(digits_, len_);
    LeftShift(rw_view, original, shift_);
  }
  ~ShiftedDigits() = default;

  void Reset() {
    if (inplace_) {
      RWDigits rw_view(digits_, len_);
      RightShift(rw_view, rw_view, shift_);
    }
  }

  int shift() { return shift_; }

 private:
  int shift_;
  bool inplace_;
  std::unique_ptr<digit_t[]> storage_;
};

}  // namespace bigint
}  // namespace v8

#endif  // V8_BIGINT_DIV_HELPERS_H_