[Libre-soc-dev] SVP64 Vectorised add-carry => big int add

[Richard Wilbur]

> On Apr 15, 2022, at 17:45, Jacob Lifshay <programmerjake at gmail.com> wrote:
> 
>>>>> On Fri, Apr 15, 2022, 15:46 lkcl <luke.leighton at gmail.com> wrote:
>>> 
>>> looking at the algorithm
>>> https://libre-soc.org/openpower/sv/bitmanip/appendix/
>>> 
>>> i am not seeing the top 32 bit of the 64 bit mul actually being used
>>> except for overflow.
>>> 
> 
> am i right in thinking that 64 bit mul could be used with 64 bit result not
>> 128 bit?
>> 
> 
> no, you're not right...think of what happens when multiplying a big-int
> with 32-bit words:
> [0x12345678, 0x9abcdef0]
> by a single word 0x1000 (which is half of what the inner loop does, q[i] is
> the single word it multiplies by):
> 0x9abcdef0 * 0x1000 = 0x9abcdef00000

I disagree here:
0x9abcdef0 * 0x1000 = 0x9abcdef0000
Multiplying by the word 0x1000 is equivalent to left shift by 12 (not 16) bits—3 nybbles (hex digits) instead of 4.

Your result follows if the multiplicand is 0x10000 instead of 0x1000 but the larger multiplicand won’t fit in a 16-bit word.

> so it produces word 0xdef00000 with carry = 0x9abc (carry is the result of
> mul-hi)
> critically carry can't just be an overflow flag here
> next 0x12345678 * 0x1000 + 0x9abc (carry) = 0x123456789abc
> so it produces word 0x56789abc with carry = 0x1234
> finally the product is:
> [0x1234, 0x56789abc, 0xdef00000]
> 
> Jacob