Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 2eb77e9c947382dbf8bca4a61c0e794bb5524136
https://github.com/WebKit/WebKit/commit/2eb77e9c947382dbf8bca4a61c0e794bb5524136
Author: Yusuke Suzuki <[email protected]>
Date: 2026-07-31 (Fri, 31 Jul 2026)
Changed paths:
A JSTests/stress/bigint-fold-mod.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
M Source/JavaScriptCore/runtime/VM.h
Log Message:
-----------
[JSC] Implement Crandall reduction
https://bugs.webkit.org/show_bug.cgi?id=320763
rdar://183764395
Reviewed by Justin Michaud.
This patch implements Crandall reduction for fast modulo calculation.
When you have
R = A mod B
R ≡ A (mod B)
If B is Pseudo-Mersenne (2^k - C, where C is small), then you can
decompose A into,
R ≡ X * 2^k + Y (mod B)
R ≡ X * C + Y (mod B)
Since X * C + Y result needs to be handled in the same way again as
X * C + Y would exceeds B again, but at most 2 times is enough. Then we
can convert mod into much cheaper computation. For example, if C is one
digit, X * C becomes multiplication with one digit, so O(N) instead of
O(N^2).
Test: JSTests/stress/bigint-fold-mod.js
* JSTests/stress/bigint-fold-mod.js: Added.
(shouldBe):
(refMod):
(checkRepeated):
(checkAllDividendSizes):
(runOfOneDivisor):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::JSBigInt::cachedModFoldFactor):
(JSC::JSBigInt::cachedModFoldImpl):
(JSC::JSBigInt::cachedModFoldFixed):
(JSC::JSBigInt::cachedModFold):
(JSC::JSBigInt::cachedMod):
(JSC::JSBigInt::remainderImpl):
* Source/JavaScriptCore/runtime/JSBigInt.h:
* Source/JavaScriptCore/runtime/VM.h:
Canonical link: https://commits.webkit.org/318364@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
