mul64x32.rs

fn low(a: u32) -> u32 {
    a & 0xFFFF
}

fn high(a: u32) -> u32 {
    a >> 16
}

fn splice(w1: u32, w0: u32) -> u32 {
    low(w1) << 16 | low(w0)
}

fn u64_mul_u32(a_hi: u32, a_lo: u32, b: u32) -> (u32, u32, u32) {
    // Multiplies a 64-bit number by a 32-bit number and outputs a 96-bit result.
    //
    // Does not use any 64-bit operations and we don't have access to add + carry
    // operations, so we operate entirely on mul(u16, u16) -> u32.

    // This implements standard "long multiplication" algorithm using 16-bit words.
    // Each element in this diagram is a 16-bit word.
    //
    //                  a3  a2  a1  a0
    //               *          b1  b0
    //     ----------------------------
    // i0 =                    p00 p00
    // i1 =                p10 p10
    // i2 =            p20 p20
    // i3 =        p30 p30
    // i4 =                p01 p01
    // i5 =            p11 p11
    // i6 =        p21 p21
    // i7 =    p31 p31
    //     ----------------------------
    //      r6  r5  r4  r3  r2  r1  r0

    let a0 = low(a_lo);
    let a1 = high(a_lo);
    let a2 = low(a_hi);
    let a3 = high(a_hi);

    let b0 = low(b);
    let b1 = high(b);

    let i0 = a0 * b0;
    let i1 = a1 * b0;
    let i2 = a2 * b0;
    let i3 = a3 * b0;
    let i4 = a0 * b1;
    let i5 = a1 * b1;
    let i6 = a2 * b1;
    let i7 = a3 * b1;

    let r0 = low(i0);
    let r1 = high(i0) + low(i1) + low(i4) + high(r0);
    let r2 = high(i1) + low(i2) + high(i4) + low(i5) + high(r1);
    let r3 = high(i2) + low(i3) + high(i5) + low(i6) + high(r2);
    let r4 = high(i3) + high(i6) + low(i7) + high(r3);
    let r5 = high(i7) + high(r4);

    let out0 = splice(r1, r0);
    let out1 = splice(r3, r2);
    let out2 = splice(r5, r4);

    (out2, out1, out0)
}