No algorithmic changes, just cleaning up.

Bug: v8:11515
Change-Id: Ib173713a1191d443faf2aebbcc31ff7608823436
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3151957Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76920}

The very last part skipped the max_digits check, and earlier parts
forgot to account for that in their check. The reason why the last
part originally got special treatment no longer applies, so we can
fix this bug by removing the special case, simplifying the overall
logic.

Fixed: chromium:1248972
Change-Id: I1857dd8b63c00f9bdfb9237f2ea3621ecc1339e2
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3160522
Auto-Submit: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Maya Lekova <mslekova@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76842}

No asymptotic improvements, and none are planned either.
Minor speedups (25-50%) through reduced overhead: accessing Digits
is faster than working with Handle<BigInt>, and this implementation
avoids allocating intermediate results.

Bug: v8:11515
Change-Id: I2aab2b1c5c9cbb910800161b8514c497daf2b587
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3149453Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76793}

No multiplications needed, just putting bits directly into
the right places.

Bug: v8:11515
Change-Id: I65e5658bb5ed12caec9325f414563526f8edbbf3
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3055291
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76727}

When an attempt to parse a huge string to a BigInt fails, then
including the entire string in it makes the exception's message
unwieldy, so this patch puts only the first 1000 characters of
such invalid strings into the exception message.

Bug: chromium:1245239
Change-Id: I2c62f0d34256653ba67da9666e8c5a1a4bbe0599
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3133142
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Mathias Bynens <mathias@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76619}

Combining parts in a balanced-binary-tree like order allows us to
use fast multiplication algorithms.

Bug: v8:11515
Change-Id: I6829929671770f009f10f6f3b383501fede476ab
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3049079Reviewed-by: Maya Lekova <mslekova@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/main@{#76404}

This patch significantly speeds up parsing of small BigInts. Its
primary idea is to move the loop that's iterating over the string
into the FromStringAccumulator API. That enables using function-
local variables instead of member fields.
A second optimization is to use a stack-allocated digit_t[] array
for small sizes, before falling back to a (comparatively slow)
std::vector.
As a particularly fast path, when this stack-allocated storage is
guaranteed to be enough, we can perform inlined multiply-and-add
steps directly on that data.
Finally, this patch changes the conversion of characters to their
numeric values from computations to a lookup table, which is a bit
faster for radixes <= 10 (where, in the old code, only one range
needed to be checked), and a lot faster for radixes > 10.

Bug: v8:11515
Change-Id: Ifd8ec4799ac34447ba6d4350b7788b559307784c
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3064603
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#76210}

No changes to the algorithm, approximately 4x performance
improvement thanks to reduced overhead.

Bug: v8:11515
Change-Id: Id3f6c91bd650f6ae47ac8f169dc780420091998e
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3046185
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Leszek Swirski <leszeks@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#76022}

It was previously only passed to compilation units in src/bigint/,
but inconsistencies arise when it's not passed to other compilation
units that #include src/bigint/bigint.h.

Fixed: chromium:1233397
Change-Id: Idb310d8c13bad12766699086574aa2c3869eb56c
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3056452Reviewed-by: Leszek Swirski <leszeks@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75941}

Dividing by first computing a multiplicative inverse is faster than
Burnikel-Ziegler division for very large inputs.

Bug: v8:11515
Change-Id: Ice45690c3fa4eef7102d418cdd3d82a942a076c5
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3015573
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75743}

Bug: v8:11515
Change-Id: I598e57de1c7d6219096dd2306fa206faf7247bb5
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2999869
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75526}

This just moves the existing algorithm, and translates it from
Handle<BigInt> to Digits as underlying data format.

Bug: v8:11515
Change-Id: Ieefee4e953e14f4c574aebab94d825ddb7c31f8c
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2975304
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75391}

No changes to the algorithm; minor speedup due to the move
from Handle<BigInt> to Digits.

Bug: v8:11515
Change-Id: Id85fe4f0c276d3ad826fee79205719092d0e0715
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2947412
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Maya Lekova <mslekova@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75158}

Due to the limits of ia32's calling convention, being able to
avoid construction of "Digits" objects (thanks to inlining)
helps a lot for microbenchmarks.

Fixed: chromium:1192133
Change-Id: I5676640d96a99dc6422f3946c608bcc93ef222ba
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2947410
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Thibaud Michaud <thibaudm@chromium.org>
Auto-Submit: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75028}

Also replace the schoolbook algorithm with an optimized version
that runs about twice as fast.
This also adds infrastructure to support interrupt checks from
BigInt library code.

Bug: v8:11515
Change-Id: I5f812913697384afca98937e1fb7361b4ec22d62
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773043
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Reviewed-by: Michael Achenbach <machenbach@chromium.org>
Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Cr-Commit-Position: refs/heads/master@{#74045}

memcpy might need the above header included to prevent
compilation errors on gcc.

Change-Id: Idfc901f160e051effb322d7da6ecc682b0fedb11
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2782486Reviewed-by: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Milad Fa <mfarazma@redhat.com>
Cr-Commit-Position: refs/heads/master@{#73634}

This is a reland of c4b44d5d

Original change's description:
> [bigint] Begin src/bigint refactoring
>
> This patch moves a first function, Compare, from src/objects/bigint.cc
> to src/bigint/, to blaze the trail. More to follow!
>
> Bug: v8:11515
> Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Reviewed-by: Hannes Payer <hpayer@chromium.org>
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#73511}

Bug: v8:11515
Change-Id: I50a81593a8acaa91161bb01a445bddbb8e6315c4
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773804Reviewed-by: Hannes Payer <hpayer@chromium.org>
Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#73610}

This reverts commit c4b44d5d.

Reason for revert: UBSan failures (https://ci.chromium.org/ui/p/v8/builders/ci/V8%20Linux64%20UBSan/15621/overview)

Original change's description:
> [bigint] Begin src/bigint refactoring
>
> This patch moves a first function, Compare, from src/objects/bigint.cc
> to src/bigint/, to blaze the trail. More to follow!
>
> Bug: v8:11515
> Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762
> Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295
> Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
> Reviewed-by: Hannes Payer <hpayer@chromium.org>
> Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#73511}

Bug: v8:11515
Change-Id: I98f3e385c785297b1b71de07fc4835da2bbe816c
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2773048
Auto-Submit: Leszek Swirski <leszeks@chromium.org>
Commit-Queue: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Cr-Commit-Position: refs/heads/master@{#73515}

This patch moves a first function, Compare, from src/objects/bigint.cc
to src/bigint/, to blaze the trail. More to follow!

Bug: v8:11515
Change-Id: Id7fa0b40ea852dbed1360f7ab439cb32d0c15762
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2737295Reviewed-by: Thibaud Michaud <thibaudm@chromium.org>
Reviewed-by: Hannes Payer <hpayer@chromium.org>
Commit-Queue: Jakob Kummerow <jkummerow@chromium.org>
Cr-Commit-Position: refs/heads/master@{#73511}