This is a follow-up to #1000:
_(u)mulh code path (on non-ARM64 MSVC).254+# define SECP256K1_WIDEMUL_INT128 1
255+# define SECP256K1_INT128_STRUCT 1
256+#elif UINTPTR_MAX > 0xffffffff
257+/* Systems with 64-bit pointers (and thus registers) very likely benefit from
258+ * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
259+ * multiplication logic. */
0/* Systems with 64-bit pointers (and thus registers) very likely benefit from
1 * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
2 * multiplication logic). */
243 # define SECP256K1_INT128_NATIVE 1
244 #elif defined(USE_FORCE_WIDEMUL_INT64)
245+/* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */
246 # define SECP256K1_WIDEMUL_INT64 1
247 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
248+/* If __int128 exists, use int128. */
0/* If native 128-bit types exist, use int128. */
(because our logic will also happily use int128_t, not only __int128.)
40@@ -37,6 +41,10 @@ static SECP256K1_INLINE int secp256k1_u128_check_bits(const secp256k1_uint128 *r
41 return (*r >> n == 0);
42 }
43
44+static SECP256K1_INLINE void secp256k1_i128_load(secp256k1_int128 *r, int64_t hi, uint64_t lo) {
45+ *r = (((uint128_t)(uint64_t)hi) << 64) + lo;
((int128_t)hi << 64) + lo?
((int128_t)hi << 64) + lo is UB if hi is negative (left-shift of negative value is undefined).
((uint128_t)hi << 64) + lo would work, but involves sign-extending hi, and then throwing those extension bits away.
((uint128_t)(uint64_t)hi << 64) + lo is equivalent, but avoids the sign-extension, which I thought would be more obviously correct.
251+#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
252+/* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct
253+ * (which has special logic to implement using intrinsics on those systems). */
254+# define SECP256K1_WIDEMUL_INT128 1
255+# define SECP256K1_INT128_STRUCT 1
256+#elif UINTPTR_MAX > 0xffffffff
0#elif SIZE_MAX > 0xffffffff
maybe this is a better heuristic because uintptr_t is an optional type. Though even if it’s not defined, your code at least won’t error because then UINTPTR_MAX will be treated as 0 in the preprocessor`. I don’t know.
Also add a corresponding CI job
1977+ { /* secp256k1_u128_accum_mul */
1978+ secp256k1_uint128 res;
1979+
1980+ /* Check secp256k1_u128_accum_mul overflow */
1981+ secp256k1_u128_from_u64(&res, 0);
1982+ secp256k1_u128_accum_mul(&res, UINT64_MAX, UINT64_MAX);
secp256k1_u128_mul(&res, UINT64_MAX, UINT64_MAX); without the secp256k1_u128_from_u64?
And similarly below.
secp256k1_u128_accum_mul to secp256k1_u128_mul instead. Maybe that’s better addressed in a separate PR to improve the tests?
I believe what I’m proposing is a small change. I’m proposing changing the logic from
res = 0
res += UINT64_MAX*UINT64_MAX
res += UINT64_MAX*UINT64_MAX
to
res = UINT64_MAX*UINT64_MAX
res += UINT64_MAX*UINT64_MAX
It still tests accumulating multiplication overflow.
But maybe it isn’t worth changing.
1896+ load256i128(rswz, &swz);
1897+ CHECK(secp256k1_memcmp_var(rswr, rswz, 16) == 0);
1898+ /* test secp256k1_i128_accum_mul */
1899+ mulmod256(rswr, rsb, rsc, NULL);
1900+ add256(rswr, rswr, rswa);
1901+ if (int256is127(rswr)) {
int256is127() succeeds with probability ~15/16 (93.75%).
256+#elif SIZE_MAX > 0xffffffff
257+/* Systems with 64-bit pointers (and thus registers) very likely benefit from
258+ * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
259+ * multiplication logic). */
260+# define SECP256K1_WIDEMUL_INT128 1
261+# define SECP256K1_INT128_STRUCT 1
on 64 bit aarch64, int64 is faster than int128_struct.
Yes, but my benchmark also showed int64 is faster than int128, as this was on a system supporting __int128. So if there are systems where we want to prefer widemul=int64 over widemul=int128, that’s a discussion independent from the int128_struct decision logic.
To find an example where this branch here (use int128_struct over int64, because int128 isn’t available) matters, we’ll need to go outside of gcc/clang/icc/MSVC, because on those we all have access to true 64x64->128 hardware multiplication if it exists. I don’t know if there are any vaguely popular C compilers for 64-bit platforms out there… does Borland still exist?
EDIT: GCC 4.5 and below, or clang 3.0 and below, for x86_64, would be relevant platforms…
utACK 99bd3355994a436e25d148c68e097cca11f3c63e
EDIT: Maybe #1158 (comment) should be merged first?
ACK 99bd3355994a436e25d148c68e097cca11f3c63e tested this also on MSVC locally with the override, including all the benchmark binaries
EDIT: Maybe #1158 (comment) should be merged first?
I think we should be greedy and merge it now that it has enough ACKs. The other one will be rather easy to rebase.