How can I multiply a pair of uint64 values safely in order to get the result as a pair of LSB and MSB of the same type?
typedef struct uint128 {
uint64 lsb;
uint64 msb;
};
uint128 mul(uint64 x, uint64 y)
{
uint128 z = {0, 0};
z.lsb = x * y;
if (z.lsb / x != y)
{
z.msb = ?
}
return z;
}
As said in the comments, the best solution would probably using a library which does that for you. But i will explain how you can do it without a library, because i think you asked to learn something. It is probably not a very efficient way but it works.
When we where in school and we had to multiply 2 numbers without a calculator, we multiplied 2 digits, had a result with 1-2 digits, and wrote them down and in the end we added them all up. We spited the multiplication up so we only had to calculate a single digit multiplication at once. A similar thing is possible with higher numbers on a CPU. But there we do not use decimal digits, we use half of the register size as digit. With that, we can multiply 2 digits and become 2 digits, in one register. In decimal 13*42 can be calculated as:
3* 2 = 0 6
10* 2 = 2 0
3*40 = 1 2 0
10*40 = 0 4 0 0
--------
0 5 4 6
A similar thing can be done with integers. To make it simple, i multiply 2 8 bit numbers to a 16 bit number on a 8 bit CPU, for that i only multiple 4 bit with 4 bit at a time. Lets multiply 0x73 with 0x4F.
0x03*0x0F = 0x002D
0x70*0x0F = 0x0690
0x03*0x40 = 0x00C0
0x70*0x40 = 0x1C00
-------
0x22BD
You basically create an array with 4 elements, in your case each element has the type uint32_t, store or add the result of a single multiplication in the right element(s) of the array, if the result of a single multiplication is too large for a single element, store the higher bits in the higher element. If an addition overflows carry 1 to the next element. In the end you can combine 2 elements of the array, in your case to two uint64_t.