karatmult8.cpp

#include "bit.hpp"
#include "stdlib.h"
#include "mult.hpp"

void karatmult8(bit* r, const bit* f, const bit* g) {
    const int n = 8, k = n/2;
    // step 1
    // Load lower part
    // noop in C, of course
    // step 2
    bit l[n];
    dmult4(l, f, g);

    // step 3: store
    for (int i = 0; i < k; i++)
        r[i] = l[i];
    
    // step 5
    bit absa[k];
    bit absb[k];
    
    // abs doesn't exist in binary polynomials, right?
    for (int i = 0; i < k; i++)
        absa[i] = f[i] + f[i+k];
    for (int i = 0; i < k; i++)
        absb[i] = g[i] + g[i+k];

    // step 6
    bit hbar[7];
    dmult4(hbar, f+k, g+k);
    for (int i = 0; i <k; i++) 
        hbar[i] += l[k+i];

    // step 7
    bit m[n];
    dmult4(m, absa, absb);

    // step 8
    bit u[n];
    // U_0 .. U_{k-1} = l_0, ..., l_{k-1}
    for (int i = 0; i < k; i++)
        u[i] = l[i];
    // U_k .. U_{n-1} = (h_k, ..., h_{n-1})
    for (int i = k; i < n; i++)
        u[i] = hbar[i]; 
    // U += Hbar
    for (int i = 0; i < n; i++)
        u[i] += hbar[i];

    // step 9
    for (int i = 0; i < n; i++)
        u[i] += m[i];

    // step 10
    for (int i = 0; i < n; i++)
        r[k+i] = u[i];

    // step 11: no carry

    // step 12
    for (int i = k; i < n; i++)
        r[n+k+i] = hbar[i];
    
}