#include <stdint.h>

namespace tmp {

/* TODO: We could later enhance this to uint32_t and uint64_t */
typedef uint8_t limb_type;
typedef uint16_t double_limb_type;

struct limb_calc_base {
  static const unsigned int LIMB_BITS = sizeof(limb_type) * 8;
  static const limb_type MAX_LIMB = ~static_cast<limb_type>(0);
};

/* Limb operations */
template<limb_type a>
struct limb_literal_expr: limb_calc_base {
  static const limb_type result = a;
  static const limb_type carry = 0;
};

template<typename a, typename b>
struct limb_add_expr: limb_calc_base {
  static const double_limb_type a_result = a::result;
  static const double_limb_type b_result = b::result;

  static const limb_type result = (a_result + b_result) & MAX_LIMB;
  static const limb_type carry = a::carry + b::carry +
    ((a_result + b_result) >> LIMB_BITS);
};

template<limb_type a, limb_type b, limb_type c = 0>
struct limb_direct_add_expr:
  limb_add_expr<
    limb_literal_expr<a>,
    limb_add_expr<limb_literal_expr<b>, limb_literal_expr<c> >
  >
{};

template<limb_type a, limb_type b>
struct limb_direct_add_expr<a, b, 0>:
  limb_add_expr<limb_literal_expr<a>, limb_literal_expr<b> >
{};

/* Limb list */
struct limb_node_end {
  static const limb_type size = 0;
};

template<limb_type Value, typename Tail>
struct limb_node {
  static const limb_type value = Value;
  static const limb_type size = Tail::size + 1;
  typedef Tail tail_type;
};

/* Normalize */
/* Two limb lists are called normalized when they have the same size. This
 * normalizes two lists by adding zero limbs to the one with less size. */
template<typename A, typename B>
struct normalize;

template<typename A, typename B>
struct normalize_sizecmp {
  static const int result =
    (A::size > B::size ? 1 : (A::size < B::size ? -1 : 0));
};

template<typename A, typename B, int ABCmp>
struct normalize_impl {};

template<typename A, typename B>
struct normalize_impl<A, B, -1> {
  typedef normalize<limb_node<0, A>, B> normalize_type;
  typedef typename normalize_type::first_type first_type;
  typedef typename normalize_type::second_type second_type;
};

template<typename A, typename B>
struct normalize_impl<A, B, 1> {
  typedef normalize<A, limb_node<0, B> > normalize_type;
  typedef typename normalize_type::first_type first_type;
  typedef typename normalize_type::second_type second_type;
};

template<typename A, typename B>
struct normalize_impl<A, B, 0> {
  typedef A first_type;
  typedef B second_type;
};

template<typename A, typename B>
struct normalize: normalize_impl<A, B, normalize_sizecmp<A, B>::result> {};

/* Denormalize */
/* Removes useless zeroes at the beginning */

/* Add */
template<typename A, typename B>
struct carry_add_impl {
  typedef carry_add_impl<typename A::tail_type, typename B::tail_type>
    tail_result_type;
  typedef limb_direct_add_expr<
    A::value,
    B::value,
    tail_result_type::carry
  > add_result_type;

  typedef limb_node<
    add_result_type::result,
    typename tail_result_type::result_type
  > result_type;

  static const limb_type carry = add_result_type::carry;
};

template<>
struct carry_add_impl<limb_node_end, limb_node_end> {
  typedef limb_node_end result_type;
  static const limb_type carry = 0;
};

template<typename A, typename B>
struct carry_add:
  carry_add_impl<typename normalize<A, B>::first_type, typename normalize<A, B>::second_type>
{};

template<typename A, typename B, bool HasCarry>
struct add_impl {};

template<typename A, typename B>
struct add_impl<A, B, false> {
  typedef carry_add<A, B> carry_type;
  typedef typename carry_type::result_type result_type;
};

template<typename A, typename B>
struct add_impl<A, B, true> {
  typedef carry_add<A, B> carry_type;
  typedef limb_node<carry_type::carry, typename carry_type::result_type>
    result_type;
};

template<typename A, typename B>
struct add: add_impl<A, B, carry_add<A, B>::carry != 0> {};

} // namespace tmp

#include <iostream>

int main()
{
  using namespace tmp;
  typedef limb_node<34, limb_node_end> first;
  typedef limb_node<2, limb_node<255, limb_node_end> > second;
  typedef add<first, second> sum;
  std::cout << static_cast<unsigned int>(sum::result_type::value) << std::endl;
  std::cout << static_cast<unsigned int>(sum::result_type::tail_type::value) << std::endl;
}