81–86 of 86 posts
Earlier quoted context omitted.
Evenly distributing the number of bits per word lets you chain more additions/subtractions before having to normalize.
Sure, but the point is that for the most significant limb, there is no point in having redundant bits because whatever you put in them will be discarded after normalization.
Earlier quoted context omitted.
That is paralelizable. Each of the 5 registers has no depence on the value of the others.
But when you split from 4 registers to 5, the bits for a given destination register may come from two different source registers.
[1] a left shift, a right shift, and an OR. Or just one 2->1 funnel shift instruction if your ISA has that e.g. arm64. And then ANDing with a 51 bit mask.
and out0, in0, 0x7FFFFFFFFFFFF
extr out1, in1, in0, #51
extr out2, in2, in1, #38
extr out3, in3, in2, #25
lsr out4, in3, #12
and out1, out1, 0x7FFFFFFFFFFFF
and out2, out2, 0x7FFFFFFFFFFFF
and out3, out3, 0x7FFFFFFFFFFFFEarlier quoted context omitted.
Also, there is another way to do this while keeping 64 bit limbs. All variables uint64_t. s0 += a0; s1 += a1; s2 += a2; s3 += a3; c0 = s0 The key insight here is that unless the sum at a particular limb position is all 1s the carry out from that position DOES NOT DEPEND on the carry in to that limb position, but only on whether the original add in that position produces a carry. If the sum is all 1s the the carry out…
Neat, but if you're using this in cryptographic code (one of the main consumers of bignums), keep in mind that secret data reaching branches is usually a side-channel risk. Sure, it's only 1 time in 2^64 on random data, but if you're depending on that, then you have to consider whether an attacker can choose data that will make it happen more often. If you can substitute a cmov without control flow then it's probably…
A `cmov` will have the same serialisation problem as `adc` but on machines without carry it might still leave you better off than the obvious `add s,a,b; sltu co,s,a; add s,s,ci; sltu t,s,ci; or co,co,t`.
Earlier quoted context omitted.
The C++ standard doesn't forbid introducing side channels, so the answer to the question is yes.
With all the UB, I wonder how did we manage to write any secure or safety-critical code at all.
even the one you cult over
Earlier quoted context omitted.
C does, however, now have _BitInt
Ugh, what a terrible thing to add to C.
If you ask your compiler for 1-megabyte integers, that's on you.
Earlier quoted context omitted.
Nope. Just 2n: each chunk pair is added once without carry, and once won't carry=1. For as long as radix=2, you either have a carry or you don't.
For a single addition, the radix is irrelevant, the carry is always zero or one: (r-1) + (r-1) = 2r - 2 < 2r.