Cursed boost.pp math

boostpp_math.c

// SPDX-FileCopyrightText: 2020 Nicolás Alvarez <[email protected]>
//
// SPDX-License-Identifier: MIT

#include <boost/preprocessor.hpp>

// Utilities to convert from numbers (bytes) or words (highbyte,lowbyte pairs)
// into nibbles.

// a -> (a1,a0)
#define SPLIT_BYTE_NIBBLES(N) (BOOST_PP_DIV(N,16), BOOST_PP_MOD(N,16))
// (ah, al) -> (a3,a2,a1,a0)
#define SPLIT_WORD_NIBBLES(N) \
    ( \
        BOOST_PP_DIV(BOOST_PP_TUPLE_ELEM(2,0,N),16), \
        BOOST_PP_MOD(BOOST_PP_TUPLE_ELEM(2,0,N),16), \
        BOOST_PP_DIV(BOOST_PP_TUPLE_ELEM(2,1,N),16), \
        BOOST_PP_MOD(BOOST_PP_TUPLE_ELEM(2,1,N),16)  \
    )
// (a1,a0) -> a
#define NIBBLES_TO_BYTE(N) \
    BOOST_PP_ADD( \
        BOOST_PP_MUL(BOOST_PP_TUPLE_ELEM(2,0,N), 16), \
        BOOST_PP_TUPLE_ELEM(2,1,N) \
    )
// (a3,a2,a1,a0) -> (ah,al)
#define NIBBLES_TO_WORD(N) \
    ( \
        BOOST_PP_ADD( \
            BOOST_PP_MUL(BOOST_PP_TUPLE_ELEM(4,0,N), 16), \
            BOOST_PP_TUPLE_ELEM(4,1,N) \
        ), \
        BOOST_PP_ADD( \
            BOOST_PP_MUL(BOOST_PP_TUPLE_ELEM(4,2,N), 16), \
            BOOST_PP_TUPLE_ELEM(4,3,N) \
        ) \
    )


// Addition of 16-bit numbers using boost.preprocessor.

/*
 * Algorithm explained in functional notation:
 *
 * add_impl(rs,nil,nil) = rs
 * add_impl((r, rs), (a, as), (b, bs)) = add_impl((a + b + r/16, (r%16, rs), as, bs)
 * add(as, bs) = add_impl((0, nil), as, bs)
 *
 * To add 0x1234 + 0x5678, call add([1,2,3,4], [5,6,7,8])
 *
 * 
 * Alternatively (and closer to the actual implementation):
 *
 * f((a,b), r) = [(a + b + head(r)/16), head(r)%16, tail(r)]
 * add(list) = foldr(f, list)
 *
 * To add 0x1234 to 0x5678, turn it into lists of pairs of matching nibbles:
 * add([(1,5), (2,6), (3,7), (4,8)])
 */

// BIGNUM_ADD((AH, AL), (BH, BL))
// Adds two 16-bit numbers, each represented as (high,low)
// This macro just converts (AH,AL),(BH,BL) into (A3,A2,A1,A0),(B3,B2,B1,B0) and calls BIGNUM_ADD_T
#define BIGNUM_ADD(A, B) \
    NIBBLES_TO_WORD( \
        BIGNUM_ADD_T( \
            SPLIT_WORD_NIBBLES(A), \
            SPLIT_WORD_NIBBLES(B) \
        ) \
    )

// This macro just converts (A3,A2,A1,A0),(B3,B2,B1,B0) into ((A3,B3))((A2,B2))((A1,B1))((A0,B0)) and calls
// BIGNUM_ADD_SEQ. It also converts the output sequence back into a tuple.
#define BIGNUM_ADD_T(A, B) \
    BOOST_PP_SEQ_TO_TUPLE( \
        BIGNUM_ADD_SEQ( \
            ((BOOST_PP_TUPLE_ELEM(4,0,A), BOOST_PP_TUPLE_ELEM(4,0,B))) \
            ((BOOST_PP_TUPLE_ELEM(4,1,A), BOOST_PP_TUPLE_ELEM(4,1,B))) \
            ((BOOST_PP_TUPLE_ELEM(4,2,A), BOOST_PP_TUPLE_ELEM(4,2,B))) \
            ((BOOST_PP_TUPLE_ELEM(4,3,A), BOOST_PP_TUPLE_ELEM(4,3,B))) \
        ) \
    )

// Adds two sequences of nibbles, could be any size.
// The input type is a sequence of 2-tuples of matching nibbles (note the double parentheses):
// ((aN,bN))...((a2,b2))((a1,b1))((a0,b0))
#define BIGNUM_ADD_SEQ(seq) BOOST_PP_SEQ_POP_BACK(BOOST_PP_SEQ_FOLD_RIGHT(BIGNUM_ADD_OP, (0), seq))

#define BIGNUM_ADD_OP(s, state, seq) \
    ( \
        BOOST_PP_ADD( \
            BOOST_PP_ADD( \
                BOOST_PP_DIV( \
                    BOOST_PP_SEQ_HEAD(state), /* R */ \
                    16 \
                ), \
                BOOST_PP_TUPLE_ELEM(2,0,seq) /* A */ \
            ), \
            BOOST_PP_TUPLE_ELEM(2,1,seq) /* B */ \
        ) \
    )( \
        BOOST_PP_MOD(BOOST_PP_SEQ_HEAD(state), 16) \
    ) \
    BOOST_PP_SEQ_TAIL(state)



// 0x1238 = (0x12 0x38) = (18,56)
// 0x5679 = (0x56 0x79) = (86,121)
//  0x1238 + 0x5679 = 0x86b1
// 0x68b1 = (0x68 0xb1) = (104, 117)
BIGNUM_ADD((18,56), (86,121)) == (104, 117);