// Karatsuba multiplication example

#include <stdlib.h>
#include <iostream>

using namespace std;

// Determine Little-Endian or Big-Endian

#define CURRENT_BYTE_ORDER       (*(int *)"\x01\x02\x03\x04")
#define LITTLE_ENDIAN_BYTE_ORDER 0x04030201
#define BIG_ENDIAN_BYTE_ORDER    0x01020304
#define PDP_ENDIAN_BYTE_ORDER    0x02010403

#define IS_LITTLE_ENDIAN (CURRENT_BYTE_ORDER == LITTLE_ENDIAN_BYTE_ORDER)
#define IS_BIG_ENDIAN    (CURRENT_BYTE_ORDER == BIG_ENDIAN_BYTE_ORDER)
#define IS_PDP_ENDIAN    (CURRENT_BYTE_ORDER == PDP_ENDIAN_BYTE_ORDER)

//
// Karatsuba multiplication algorithm
//
//            +------+------+
//            |  x1  |  x0  |
//            +------+------+
//                   *
//            +------+------+
//            |  y1  |  y0  |
//            +------+------+
//                   =
//     +-------------+-------------+
//  +  |    x1*y1    |    x0*y0    |
//     +----+-+------+------+------+
//          . .             .
//          . .             .
//          +-+------+------+
//       +  | x0*y1 + x1*y0 |
//          +-+------+------+
//

//
// Params:
//     T  - is type of x0, x1, y0 and y1 halves
//     T2 - is type of x, y and half of res
//
template<typename T, typename T2>
inline void Karatsuba_multiply(const T * x, const T * y, T2 * res)
{
    if (IS_LITTLE_ENDIAN)
        return Karatsuba_multiply_little_endian(x,y,res);
    if (IS_BIG_ENDIAN)
        return Karatsuba_multiply_big_endian(x,y,res);
}

template<typename T, typename T2>
inline void Karatsuba_multiply_little_endian(const T * x, const T * y, T2 * res)
{
    // Define vars (differs from byte order)

    #define ptrRes ((T*)res)
    T2 &  lowWord = (T2&)(ptrRes[0]);
    T2 &  midWord = (T2&)(ptrRes[1]);
    T2 & highWord = (T2&)(ptrRes[2]);
    T  & highByte = (T &)(ptrRes[3]);

    const T & x0 = x[0];
    const T & x1 = x[1];
    const T & y0 = y[0];
    const T & y1 = y[1];

    // Multiply action

    lowWord  = x0 * y0;
    highWord = x1 * y1;

    T2 m1 = x0 * y1;
    T2 m2 = x1 * y0;

    midWord += m1;
    if (midWord < m1) highByte++;
    midWord += m2;
    if (midWord < m2) highByte++;
}

template<typename T, typename T2>
inline void Karatsuba_multiply_big_endian(const T * x, const T * y, T2 * res)
{
    // Define vars (differs from byte order)

    #define ptrRes ((T*)res)
    T2 & highWord = *(T2*)(ptrRes+0);
    T2 &  midWord = *(T2*)(ptrRes+1);
    T2 &  lowWord = *(T2*)(ptrRes+2);
    T  & highByte = *(T *)(ptrRes+0);

    const T & x0 = x[1];
    const T & x1 = x[0];
    const T & y0 = y[1];
    const T & y1 = y[0];

    // Multiply action

    lowWord  = x0 * y0;
    highWord = x1 * y1;

    T m1 = x0 * y1;
    T m2 = x1 * y0;

    midWord += m1;
    if (midWord < m1) highByte++;
    midWord += m2;
    if (midWord < m2) highByte++;
}

int main()
{
    typedef unsigned char   u8;
    typedef unsigned short u16;
    typedef unsigned int   u32;

    u16 a = 1000;
    u16 b = 2000;
    u32 r = 0;

    u8  * a_ptr = (u8*)&a;
    u8  * b_ptr = (u8*)&b;
    u16 * r_ptr = (u16*)(void*)&r;

    Karatsuba_multiply(a_ptr, b_ptr, r_ptr);

    cout << r;
}

2000000