algorithm - How can I multiply two hex 128 bit numbers in assembly

Question

I have two 128 bit numbers in memory in hexadecimal, for example (little endian):

x:0x12 0x45 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
y:0x36 0xa1 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

I've to perform the unsigned multiplication between these two numbers so my new number will be:

z:0xcc 0xe3 0x7e 0x2b 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

Now, I'm aware that I can move the half x and y number into rax and rbx registers and, for example, do the mul operation, and do the same with the other half. The problem is that by doing so I lose the carry-over and I've no idea how I can avoid that. It's about 4 hours I'm facing this problem and the only solution that can I see is the conversion in binary (and <-> shl,1).

Can you give me some input about this problem?
I think the best solution is to take one byte par time.

Answer 1

Let μ = 2⁶⁴, then we can decompose your 128 bit numbers a and b into a = a₁μ + a₂ and b = b₁μ + b₂. Then we can compute c = ab with 64 · 64 → 128 bit multiplications by first computing partial products:

q₁μ + q₂ = a₂b₂
r₁μ + r₂ = a₁b₂
s₁μ + s₂ = a₂b₁
t₁μ + t₂ = a₁b₁

and then accumulating them into a 256 bit result (watch the overflow when doing the additions!):

c = t₁μ³ + (t₂ + s₁ + r₁) μ² + (s₂ + r₂ + q₁) μ + q₂