Attachment #397252 for bug #210869

View Details Raw Unified Return to Bug 210869

| Differences between



2020-04-22  Saam Barati  <sbarati@apple.com>

        BigInt32 parsing should be precise
        https://bugs.webkit.org/show_bug.cgi?id=210869

        Reviewed by Robin Morisset.

        * stress/big-int-32-parsing-should-be-precise.js: Added.

2020-04-22  Yusuke Suzuki  <ysuzuki@apple.com>

        [JSC] JSBigInt inc operation does not produce right HeapBigInt zero



function assert(b) {
    if (!b)
        throw new Error;
}

function assertIsBigInt32(arg) {
    if (useBigInt32())
        assert(isBigInt32(arg));
    else
        assert(isHeapBigInt(arg));
}

assertIsBigInt32(2147483647n);
assertIsBigInt32(2147483646n);
assertIsBigInt32(2127483646n);
assertIsBigInt32(1127483646n);
assertIsBigInt32(-2147483648n);
assertIsBigInt32(-2147483647n);
assertIsBigInt32(-1147483647n);
assertIsBigInt32(0n);
assertIsBigInt32(1n);
assertIsBigInt32(-1n);
assertIsBigInt32(42n);

assert(isHeapBigInt(2147483648n));
assert(isHeapBigInt(-2147483649n));
assert(isHeapBigInt(3147483648n));
assert(isHeapBigInt(9147483648n));
assert(isHeapBigInt(-9147483649n));
assert(isHeapBigInt(-2147583649n));



2020-04-22  Saam Barati  <sbarati@apple.com>

        BigInt32 parsing should be precise
        https://bugs.webkit.org/show_bug.cgi?id=210869

        Reviewed by Robin Morisset.

        Our algorithm before was conservative, and might produce a heap big int even
        if the value could be an int32. This patch makes the algorithm precise on
        64-bit, always producing a bigint32 if the number is indeed an int32.

        * jsc.cpp:
        (functionUseBigInt32):
        (functionIsBigInt32):
        (functionIsHeapBigInt):
        * runtime/JSBigInt.cpp:
        (JSC::JSBigInt::parseInt):

2020-04-22  Yusuke Suzuki  <ysuzuki@apple.com>

        [JSC] JSBigInt inc operation does not produce right HeapBigInt zero

Lines 275-280 static EncodedJSValue JSC_HOST_CALL func Source/JavaScriptCore/jsc.cpp_sec1
- Source/JavaScriptCore/jsc.cpp +30 lines
275	#if USE(BIGINT32)	275	#if USE(BIGINT32)
276	static EncodedJSValue JSC_HOST_CALL functionCreateBigInt32(JSGlobalObject, CallFrame);	276	static EncodedJSValue JSC_HOST_CALL functionCreateBigInt32(JSGlobalObject, CallFrame);
277	#endif	277	#endif
		278	static EncodedJSValue JSC_HOST_CALL functionUseBigInt32(JSGlobalObject, CallFrame);
		279	static EncodedJSValue JSC_HOST_CALL functionIsBigInt32(JSGlobalObject, CallFrame);
		280	static EncodedJSValue JSC_HOST_CALL functionIsHeapBigInt(JSGlobalObject, CallFrame);
278		281
279	static EncodedJSValue JSC_HOST_CALL functionPrintStdOut(JSGlobalObject, CallFrame);	282	static EncodedJSValue JSC_HOST_CALL functionPrintStdOut(JSGlobalObject, CallFrame);
280	static EncodedJSValue JSC_HOST_CALL functionPrintStdErr(JSGlobalObject, CallFrame);	283	static EncodedJSValue JSC_HOST_CALL functionPrintStdErr(JSGlobalObject, CallFrame);
Lines 550-555 private: Source/JavaScriptCore/jsc.cpp_sec2
550	#if USE(BIGINT32)	553	#if USE(BIGINT32)
551	addFunction(vm, "createBigInt32", functionCreateBigInt32, 1);	554	addFunction(vm, "createBigInt32", functionCreateBigInt32, 1);
552	#endif	555	#endif
		556	addFunction(vm, "useBigInt32", functionUseBigInt32, 0);
		557	addFunction(vm, "isBigInt32", functionIsBigInt32, 1);
		558	addFunction(vm, "isHeapBigInt", functionIsHeapBigInt, 1);
553		559
554	addFunction(vm, "dumpTypesForAllVariables", functionDumpTypesForAllVariables , 0);	560	addFunction(vm, "dumpTypesForAllVariables", functionDumpTypesForAllVariables , 0);
555		561
Lines 2300-2305 EncodedJSValue JSC_HOST_CALL functionCre Source/JavaScriptCore/jsc.cpp_sec3
2300	}	2306	}
2301	#endif	2307	#endif
2302		2308
		2309	EncodedJSValue JSC_HOST_CALL functionUseBigInt32(JSGlobalObject, CallFrame)
		2310	{
		2311	#if USE(BIGINT32)
		2312	return JSValue::encode(jsBoolean(true));
		2313	#else
		2314	return JSValue::encode(jsBoolean(false));
		2315	#endif
		2316	}
		2317
		2318	EncodedJSValue JSC_HOST_CALL functionIsBigInt32(JSGlobalObject, CallFrame callFrame)
		2319	{
		2320	#if USE(BIGINT32)
		2321	return JSValue::encode(jsBoolean(callFrame->argument(0).isBigInt32()));
		2322	#else
		2323	UNUSED_PARAM(callFrame);
		2324	return JSValue::encode(jsBoolean(false));
		2325	#endif
		2326	}
		2327
		2328	EncodedJSValue JSC_HOST_CALL functionIsHeapBigInt(JSGlobalObject, CallFrame callFrame)
		2329	{
		2330	return JSValue::encode(jsBoolean(callFrame->argument(0).isHeapBigInt()));
		2331	}
		2332
2303	EncodedJSValue JSC_HOST_CALL functionCheckModuleSyntax(JSGlobalObject* globalObject, CallFrame* callFrame)	2333	EncodedJSValue JSC_HOST_CALL functionCheckModuleSyntax(JSGlobalObject* globalObject, CallFrame* callFrame)
2304	{	2334	{
2305	VM& vm = globalObject->vm();	2335	VM& vm = globalObject->vm();



#endif
    }

    // The idea is to pick the largest number such that radix ** lengthLimitForBigInt32 <= INT32_MAX
    unsigned lengthLimitForBigInt32;
#if USE(BIGINT32)
    static_assert(sizeof(Digit) >= sizeof(uint64_t));
    // The idea is to pick the limit such that:
    // radix ** lengthLimitForBigInt32 >= INT32_MAX
    // radix ** (lengthLimitForBigInt32 - 1) <= INT32_MAX
#if ASSERT_ENABLED
    auto limitWorks = [&] {
        double lengthLimit = lengthLimitForBigInt32;
        double lowerLimit = pow(static_cast<double>(radix), lengthLimit - 1);
        double upperLimit = pow(static_cast<double>(radix), lengthLimit);
        double target = std::numeric_limits<int32_t>::max();
        return lowerLimit <= target && target <= upperLimit && upperLimit <= std::numeric_limits<int64_t>::max();
    };
#endif
    switch (radix) {
    case 2:
        lengthLimitForBigInt32 = 31;
        ASSERT(limitWorks());
        break;
    case 8:
        lengthLimitForBigInt32 = 11;
        ASSERT(limitWorks());
        break;
    case 10:
        lengthLimitForBigInt32 = 10;
        ASSERT(limitWorks());
        break;
    case 16:
        lengthLimitForBigInt32 = 8;
        ASSERT(limitWorks());
        break;
    default:
        lengthLimitForBigInt32 = 1;
        break;
    }
#else
    // The idea is to pick the largest limit such that:
    // radix ** lengthLimitForBigInt32 <= INT32_MAX
#if ASSERT_ENABLED
    auto limitWorks = [&] {
        double lengthLimit = lengthLimitForBigInt32;
        double valueLimit = pow(static_cast<double>(radix), lengthLimit);
        double overValueLimit = pow(static_cast<double>(radix), lengthLimit + 1);
        double target = std::numeric_limits<int32_t>::max();
        return valueLimit <= target && target < overValueLimit;
    };
#endif
    switch (radix) {
    case 2:
        lengthLimitForBigInt32 = 30;
        ASSERT(limitWorks());
        break;
    case 8:
        lengthLimitForBigInt32 = 10;
        ASSERT(limitWorks());
        break;
    case 10:
        lengthLimitForBigInt32 = 9;
        ASSERT(limitWorks());
        break;
    case 16:
        lengthLimitForBigInt32 = 7;
        ASSERT(limitWorks());
        break;
    default:
        lengthLimitForBigInt32 = 1;
        break;
    }
#endif // USE(BIGINT32)

    JSBigInt* heapResult = nullptr;


    unsigned limitA = 'A' + (static_cast<int32_t>(radix) - 10);
    unsigned initialLength = length - p;
    while (p < length) {
        Checked<uint64_t, CrashOnOverflow> digit = 0;
        Checked<uint64_t, CrashOnOverflow> multiplier = 1;
        for (unsigned i = 0; i < lengthLimitForBigInt32 && p < length; ++i, ++p) {
            digit *= radix;
            multiplier *= radix;
            if (data[p] >= '0' && data[p] < limit0)
                digit += static_cast<uint64_t>(data[p] - '0');
            else if (data[p] >= 'a' && data[p] < limita)
                digit += static_cast<uint64_t>(data[p] - 'a' + 10);
            else if (data[p] >= 'A' && data[p] < limitA)
                digit += static_cast<uint64_t>(data[p] - 'A' + 10);
            else {
                if (errorParseMode == ErrorParseMode::ThrowExceptions) {
                    ASSERT(globalObject);

                return JSValue();
            }
        }
        ASSERT(digit < multiplier.unsafeGet());

        if (!heapResult) {
            if (p == length) {
                ASSERT(digit.unsafeGet() <= std::numeric_limits<int64_t>::max());
                int64_t maybeResult = digit.unsafeGet();
                ASSERT(maybeResult >= 0);
                if (sign == ParseIntSign::Signed)
                    maybeResult *= -1;

                if (static_cast<int64_t>(static_cast<int32_t>(maybeResult)) == maybeResult) {
#if USE(BIGINT32)
                    return JSValue(JSValue::JSBigInt32, static_cast<int32_t>(maybeResult));
#else
                    return JSBigInt::createFrom(vm, static_cast<int32_t>(maybeResult));
#endif
                }
            }
            heapResult = allocateFor(globalObject, vm, radix, initialLength);
            RETURN_IF_EXCEPTION(scope, JSValue());

                return JSValue();
            heapResult->initialize(InitializationType::WithZero);
        }

        ASSERT(static_cast<uint64_t>(static_cast<Digit>(multiplier.unsafeGet())) == multiplier.unsafeGet());
        ASSERT(static_cast<uint64_t>(static_cast<Digit>(digit.unsafeGet())) == digit.unsafeGet());
        heapResult->inplaceMultiplyAdd(static_cast<Digit>(multiplier.unsafeGet()), static_cast<Digit>(digit.unsafeGet()));
    }

    heapResult->setSign(sign == ParseIntSign::Signed);

Return to Bug 210869

Lines 1866-1890 JSValue JSBigInt::parseInt(JSGlobalObjec Source/JavaScriptCore/runtime/JSBigInt.cpp_sec1
- Source/JavaScriptCore/runtime/JSBigInt.cpp -12 / +71 lines
1866	#endif	1866	#endif
1867	}	1867	}
1868		1868
1869	// The idea is to pick the largest number such that radix ** lengthLimitForBigInt32 <= INT32_MAX
1870	unsigned lengthLimitForBigInt32;	1869	unsigned lengthLimitForBigInt32;
		1870	#if USE(BIGINT32)
		1871	static_assert(sizeof(Digit) >= sizeof(uint64_t));
		1872	// The idea is to pick the limit such that:
		1873	// radix ** lengthLimitForBigInt32 >= INT32_MAX
		1874	// radix ** (lengthLimitForBigInt32 - 1) <= INT32_MAX
		1875	#if ASSERT_ENABLED
		1876	auto limitWorks = [&] {
		1877	double lengthLimit = lengthLimitForBigInt32;
		1878	double lowerLimit = pow(static_cast<double>(radix), lengthLimit - 1);
		1879	double upperLimit = pow(static_cast<double>(radix), lengthLimit);
		1880	double target = std::numeric_limits<int32_t>::max();
		1881	return lowerLimit <= target && target <= upperLimit && upperLimit <= std::numeric_limits<int64_t>::max();
		1882	};
		1883	#endif
		1884	switch (radix) {
		1885	case 2:
		1886	lengthLimitForBigInt32 = 31;
		1887	ASSERT(limitWorks());
		1888	break;
		1889	case 8:
		1890	lengthLimitForBigInt32 = 11;
		1891	ASSERT(limitWorks());
		1892	break;
		1893	case 10:
		1894	lengthLimitForBigInt32 = 10;
		1895	ASSERT(limitWorks());
		1896	break;
		1897	case 16:
		1898	lengthLimitForBigInt32 = 8;
		1899	ASSERT(limitWorks());
		1900	break;
		1901	default:
		1902	lengthLimitForBigInt32 = 1;
		1903	break;
		1904	}
		1905	#else
		1906	// The idea is to pick the largest limit such that:
		1907	// radix ** lengthLimitForBigInt32 <= INT32_MAX
		1908	#if ASSERT_ENABLED
		1909	auto limitWorks = [&] {
		1910	double lengthLimit = lengthLimitForBigInt32;
		1911	double valueLimit = pow(static_cast<double>(radix), lengthLimit);
		1912	double overValueLimit = pow(static_cast<double>(radix), lengthLimit + 1);
		1913	double target = std::numeric_limits<int32_t>::max();
		1914	return valueLimit <= target && target < overValueLimit;
		1915	};
		1916	#endif
1871	switch (radix) {	1917	switch (radix) {
1872	case 2:	1918	case 2:
1873	lengthLimitForBigInt32 = 30;	1919	lengthLimitForBigInt32 = 30;
		1920	ASSERT(limitWorks());
1874	break;	1921	break;
1875	case 8:	1922	case 8:
1876	lengthLimitForBigInt32 = 10;	1923	lengthLimitForBigInt32 = 10;
		1924	ASSERT(limitWorks());
1877	break;	1925	break;
1878	case 10:	1926	case 10:
1879	lengthLimitForBigInt32 = 9;	1927	lengthLimitForBigInt32 = 9;
		1928	ASSERT(limitWorks());
1880	break;	1929	break;
1881	case 16:	1930	case 16:
1882	lengthLimitForBigInt32 = 7;	1931	lengthLimitForBigInt32 = 7;
		1932	ASSERT(limitWorks());
1883	break;	1933	break;
1884	default:	1934	default:
1885	lengthLimitForBigInt32 = 1;	1935	lengthLimitForBigInt32 = 1;
1886	break;	1936	break;
1887	}	1937	}
		1938	#endif // USE(BIGINT32)
1888		1939
1889	JSBigInt* heapResult = nullptr;	1940	JSBigInt* heapResult = nullptr;
1890		1941
Lines 1893-1909 JSValue JSBigInt::parseInt(JSGlobalObjec Source/JavaScriptCore/runtime/JSBigInt.cpp_sec2
1893	unsigned limitA = 'A' + (static_cast<int32_t>(radix) - 10);	1944	unsigned limitA = 'A' + (static_cast<int32_t>(radix) - 10);
1894	unsigned initialLength = length - p;	1945	unsigned initialLength = length - p;
1895	while (p < length) {	1946	while (p < length) {
1896	int32_t digit = 0;	1947	Checked<uint64_t, CrashOnOverflow> digit = 0;
1897	Checked<int32_t, CrashOnOverflow> multiplier = 1;	1948	Checked<uint64_t, CrashOnOverflow> multiplier = 1;
1898	for (unsigned i = 0; i < lengthLimitForBigInt32 && p < length ; ++i, ++p) {	1949	for (unsigned i = 0; i < lengthLimitForBigInt32 && p < length; ++i, ++p) {
1899	digit *= radix;	1950	digit *= radix;
1900	multiplier *= radix;	1951	multiplier *= radix;
1901	if (data[p] >= '0' && data[p] < limit0)	1952	if (data[p] >= '0' && data[p] < limit0)
1902	digit += data[p] - '0';	1953	digit += static_cast<uint64_t>(data[p] - '0');
1903	else if (data[p] >= 'a' && data[p] < limita)	1954	else if (data[p] >= 'a' && data[p] < limita)
1904	digit += data[p] - 'a' + 10;	1955	digit += static_cast<uint64_t>(data[p] - 'a' + 10);
1905	else if (data[p] >= 'A' && data[p] < limitA)	1956	else if (data[p] >= 'A' && data[p] < limitA)
1906	digit += data[p] - 'A' + 10;	1957	digit += static_cast<uint64_t>(data[p] - 'A' + 10);
1907	else {	1958	else {
1908	if (errorParseMode == ErrorParseMode::ThrowExceptions) {	1959	if (errorParseMode == ErrorParseMode::ThrowExceptions) {
1909	ASSERT(globalObject);	1960	ASSERT(globalObject);
Lines 1912-1928 JSValue JSBigInt::parseInt(JSGlobalObjec Source/JavaScriptCore/runtime/JSBigInt.cpp_sec3
1912	return JSValue();	1963	return JSValue();
1913	}	1964	}
1914	}	1965	}
1915	ASSERT(digit < multiplier.unsafeGet());
1916		1966
1917	if (!heapResult) {	1967	if (!heapResult) {
1918	if (p == length) {	1968	if (p == length) {
		1969	ASSERT(digit.unsafeGet() <= std::numeric_limits<int64_t>::max());
		1970	int64_t maybeResult = digit.unsafeGet();
		1971	ASSERT(maybeResult >= 0);
1919	if (sign == ParseIntSign::Signed)	1972	if (sign == ParseIntSign::Signed)
1920	digit *= -1;	1973	maybeResult *= -1;
		1974
		1975	if (static_cast<int64_t>(static_cast<int32_t>(maybeResult)) == maybeResult) {
1921	#if USE(BIGINT32)	1976	#if USE(BIGINT32)
1922	return JSValue(JSValue::JSBigInt32, digit);	1977	return JSValue(JSValue::JSBigInt32, static_cast<int32_t>(maybeResult));
1923	#else	1978	#else
1924	return createFrom(vm, static_cast<int64_t>(digit));	1979	return JSBigInt::createFrom(vm, static_cast<int32_t>(maybeResult));
1925	#endif	1980	#endif
		1981	}
1926	}	1982	}
1927	heapResult = allocateFor(globalObject, vm, radix, initialLength);	1983	heapResult = allocateFor(globalObject, vm, radix, initialLength);
1928	RETURN_IF_EXCEPTION(scope, JSValue());	1984	RETURN_IF_EXCEPTION(scope, JSValue());
Lines 1931-1937 JSValue JSBigInt::parseInt(JSGlobalObjec Source/JavaScriptCore/runtime/JSBigInt.cpp_sec4
1931	return JSValue();	1987	return JSValue();
1932	heapResult->initialize(InitializationType::WithZero);	1988	heapResult->initialize(InitializationType::WithZero);
1933	}	1989	}
1934	heapResult->inplaceMultiplyAdd(static_cast<Digit>(multiplier.unsafeGet()), static_cast<Digit>(digit));	1990
		1991	ASSERT(static_cast<uint64_t>(static_cast<Digit>(multiplier.unsafeGet())) == multiplier.unsafeGet());
		1992	ASSERT(static_cast<uint64_t>(static_cast<Digit>(digit.unsafeGet())) == digit.unsafeGet());
		1993	heapResult->inplaceMultiplyAdd(static_cast<Digit>(multiplier.unsafeGet()), static_cast<Digit>(digit.unsafeGet()));
1935	}	1994	}
1936		1995
1937	heapResult->setSign(sign == ParseIntSign::Signed);	1996	heapResult->setSign(sign == ParseIntSign::Signed);

Lines 1-3 JSTests/ChangeLog_sec1
- JSTests/ChangeLog +9 lines
		1	2020-04-22 Saam Barati <sbarati@apple.com>
		2
		3	BigInt32 parsing should be precise
		4	https://bugs.webkit.org/show_bug.cgi?id=210869
		5
		6	Reviewed by Robin Morisset.
		7
		8	* stress/big-int-32-parsing-should-be-precise.js: Added.
		9
1	2020-04-22 Yusuke Suzuki <ysuzuki@apple.com>	10	2020-04-22 Yusuke Suzuki <ysuzuki@apple.com>
2		11
3	[JSC] JSBigInt inc operation does not produce right HeapBigInt zero	12	[JSC] JSBigInt inc operation does not produce right HeapBigInt zero

Line 0 JSTests/stress/big-int-32-parsing-should-be-precise.js_sec1
- JSTests/stress/big-int-32-parsing-should-be-precise.js +30 lines
	1	function assert(b) {
	2	if (!b)
	3	throw new Error;
	4	}
	5
	6	function assertIsBigInt32(arg) {
	7	if (useBigInt32())
	8	assert(isBigInt32(arg));
	9	else
	10	assert(isHeapBigInt(arg));
	11	}
	12
	13	assertIsBigInt32(2147483647n);
	14	assertIsBigInt32(2147483646n);
	15	assertIsBigInt32(2127483646n);
	16	assertIsBigInt32(1127483646n);
	17	assertIsBigInt32(-2147483648n);
	18	assertIsBigInt32(-2147483647n);
	19	assertIsBigInt32(-1147483647n);
	20	assertIsBigInt32(0n);
	21	assertIsBigInt32(1n);
	22	assertIsBigInt32(-1n);
	23	assertIsBigInt32(42n);
	24
	25	assert(isHeapBigInt(2147483648n));
	26	assert(isHeapBigInt(-2147483649n));
	27	assert(isHeapBigInt(3147483648n));
	28	assert(isHeapBigInt(9147483648n));
	29	assert(isHeapBigInt(-9147483649n));
	30	assert(isHeapBigInt(-2147583649n));

Lines 1-3 Source/JavaScriptCore/ChangeLog_sec1
- Source/JavaScriptCore/ChangeLog +18 lines
		1	2020-04-22 Saam Barati <sbarati@apple.com>
		2
		3	BigInt32 parsing should be precise
		4	https://bugs.webkit.org/show_bug.cgi?id=210869
		5
		6	Reviewed by Robin Morisset.
		7
		8	Our algorithm before was conservative, and might produce a heap big int even
		9	if the value could be an int32. This patch makes the algorithm precise on
		10	64-bit, always producing a bigint32 if the number is indeed an int32.
		11
		12	* jsc.cpp:
		13	(functionUseBigInt32):
		14	(functionIsBigInt32):
		15	(functionIsHeapBigInt):
		16	* runtime/JSBigInt.cpp:
		17	(JSC::JSBigInt::parseInt):
		18
1	2020-04-22 Yusuke Suzuki <ysuzuki@apple.com>	19	2020-04-22 Yusuke Suzuki <ysuzuki@apple.com>
2		20
3	[JSC] JSBigInt inc operation does not produce right HeapBigInt zero	21	[JSC] JSBigInt inc operation does not produce right HeapBigInt zero