Multiplying two 128-bit ints

Question

I'm trying to multiply two 128-bit integers in C.

Here is my algorithm:

Split the two 128-bit sequences into S1 and S2.

Then split S1 into S11 (front/higher half) and S12 (back/lower half) and split S2 into S21 (front/higher half) and S22 (back/lower half).

Multiply S12 by S22... = S1222.

Multiply S11 by S21... = S1121 and then bit shift it by multiplying it by 2^128

Combine S1222 and S1121 to be the front and back halves of a new array. Let's call it "Array1". The new array's length is twice as long as S1.

Then we have to multiply S12 by S21 and S11 by S22. I have multiplied these two to get S1221 and S1122, respectively (and bit-shifted them accordingly). Now I have to add them to Array1. This is the part where I'm asking for help. I'm not sure how to add these, one by one, to Array1. Keep in mind there may be a carry of 1 as you go bit by bit from 3/4 of Array1 to 1/4 of Array1, as this is the span where S1221 and S1122 need to be added.

My question is: How do I add dstM1 and dstM2 to the array d, which is already filled?

Answer 1

If you're on gcc or clang you can use __int128 and unsigned __int128 directly.

Answer 2

You are stuck in an infinite loop because i += 1/32 is the same as i += 0.

Also: note:memcpy(&d[3l/2-i], dstM1, 1/8); is memcpy(&d[1-i], dstM1, 0);