bitwise_add.c

/*
 * @author Lohann Paterno Coutinho Ferreira <[email protected]>
 *
 * Example on how to add numbers using only bitwise operators:
 * - xor: ^ 
 * - and: &
 * - not: ~
 * - or:  |
 *
 * # Motivation
 * Implemented this to teach myself on how to build the CPU basic operations
 * using the least numbers of gates (or bitwise operations) possible.
 * - Inverter / NOT gate requires 2 transistors.
 * - NAND and NOR gates requires 4 transistors.
 * - AND and OR gates requires 6 transistors.
 * - XOR and XNOR requires 10 transistors.
 * Ref: https://youtu.be/_Pqfjer8-O4?si=AhXJCYheg9axddbT&t=543
 *
 * Converting algebraic operations into first order logic also helps on converting
 * an program into a boolean predicate, which is useful for Formal Verification.
 */
#include <stdio.h>
#include <inttypes.h>
#include <stdbool.h>

// Define a function that adds two numbers
// encoded as an boolean bitfield.
typedef void (fn_add) (bool *a, bool *b, bool *r);

/// Compute `r = a + b` using only bitwise operators.
uint8_t add_bitwise_8bit(uint8_t a, uint8_t b)
{
    uint8_t carry, xor, and;
    // bit 0
    xor = a ^ b;
    and = a & b;
    // bit 1
    carry = and << 1;
    // bit 2
    carry = (and | (carry & xor)) << 1;
    // bit 3
    carry = (and | (carry & xor)) << 1;
    // bit 4
    carry = (and | (carry & xor)) << 1;
    // bit 5
    carry = (and | (carry & xor)) << 1;
    // bit 6
    carry = (and | (carry & xor)) << 1;
    // bit 7
    carry = (and | (carry & xor)) << 1;
    return carry ^ xor;
}

/// Compute `r = a + b` using only two bitwise operators:
/// - xor (^)
/// - and (&)
/// Assumes a, b and r have at least 8 elements.
void add_xor_8bit(bool *a, bool *b, bool *r)
{
    bool aux, carry;

    // Compute BIT 0
    r[0] = a[0] ^ b[0];
    carry = a[0] & b[0];

    // Compute BIT 1
    aux = a[1] ^ b[1];
    r[1] = aux ^ carry;
    carry = a[1] ^ (aux & (a[1] ^ carry));

    // Compute BIT 2
    aux = a[2] ^ b[2];
    r[2] = aux ^ carry;
    carry = a[2] ^ (aux & (a[2] ^ carry));

    // Compute BIT 3
    aux = a[3] ^ b[3];
    r[3] = aux ^ carry;
    carry = a[3] ^ (aux & (a[3] ^ carry));

    // Compute BIT 4
    aux = a[4] ^ b[4];
    r[4] = aux ^ carry;
    carry = a[4] ^ (aux & (a[4] ^ carry));

    // Compute BIT 5
    aux = a[5] ^ b[5];
    r[5] = aux ^ carry;
    carry = a[5] ^ (aux & (a[5] ^ carry));

    // Compute BIT 6
    aux = a[6] ^ b[6];
    r[6] = aux ^ carry;
    carry = a[6] ^ (aux & (a[6] ^ carry));

    // Compute BIT 7
    aux = a[7] ^ b[7];
    r[7] = aux ^ carry;
    // carry = a[7] ^ (aux & (a[7] ^ carry));
}

/// Compute `r = a + b` using first order logic operators:
/// - not (~)
/// - and (&)
/// - or (|)
/// Assumes a, b and r have at least 8 elements.
void add_first_order_8bit(bool *a, bool *b, bool *r)
{
    bool aux1, aux2, aux3, carry;

    // Compute BIT 0
    carry = a[0] & b[0];
    r[0] = (a[0] | b[0]) & ~(carry);

    // Compute BIT 1
    aux1 = a[1] & b[1];
    aux2 = a[1] | b[1];
    aux3 = carry | aux1;
    r[1] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 2
    aux1 = a[2] & b[2];
    aux2 = a[2] | b[2];
    aux3 = carry | aux1;
    r[2] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 3
    aux1 = a[3] & b[3];
    aux2 = a[3] | b[3];
    aux3 = carry | aux1;
    r[3] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 4
    aux1 = a[4] & b[4];
    aux2 = a[4] | b[4];
    aux3 = carry | aux1;
    r[4] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 5
    aux1 = a[5] & b[5];
    aux2 = a[5] | b[5];
    aux3 = carry | aux1;
    r[5] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 6
    aux1 = a[6] & b[6];
    aux2 = a[6] | b[6];
    aux3 = carry | aux1;
    r[6] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    carry = aux2 & aux3;

    // Compute BIT 7
    aux1 = a[7] & b[7];
    aux2 = a[7] | b[7];
    aux3 = carry | aux1;
    r[7] = (aux2 & ~aux3) | (carry & (aux1 | ~aux2));
    // carry = aux2 & aux3;
}

// Encodes uint8_t `n` as an boolean array `dest`
void uint8_to_bool(uint8_t n, bool *dest)
{
    dest[0] = (n & (1 << 0)) > 0;
    dest[1] = (n & (1 << 1)) > 0;
    dest[2] = (n & (1 << 2)) > 0;
    dest[3] = (n & (1 << 3)) > 0;
    dest[4] = (n & (1 << 4)) > 0;
    dest[5] = (n & (1 << 5)) > 0;
    dest[6] = (n & (1 << 6)) > 0;
    dest[7] = (n & (1 << 7)) > 0;
}

// Decode an boolean array as `uint8_t`
uint8_t bool_to_uint8(bool *src)
{
    uint8_t n = 0;
    n |= (src[0] & 1) << 0;
    n |= (src[1] & 1) << 1;
    n |= (src[2] & 1) << 2;
    n |= (src[3] & 1) << 3;
    n |= (src[4] & 1) << 4;
    n |= (src[5] & 1) << 5;
    n |= (src[6] & 1) << 6;
    n |= (src[7] & 1) << 7;
    return n;
}

// Convert `lhs` and `rhs` into boolean array, then call `add`.
uint8_t add_with_fn(uint8_t lhs, uint8_t rhs, fn_add add)
{
    bool a[8];
    bool b[8];
    bool result[8];

    // Convert values to boolean array
    uint8_to_bool(lhs, a);
    uint8_to_bool(rhs, b);
    uint8_to_bool(0, result);

    // Compute `result = a + b` using the rovided function.
    (add) (a, b, result);

    // Convert result back to uint8_t
    return bool_to_uint8(result);
}

int main(void)
{
    unsigned int i;
    uint8_t a, b, actual, expected;
    const char *error_msg;

    error_msg = NULL;
    for (i = 0; i < 256 * 256; i++) {
        // Split `i` into two 8bit numbers.
        a = (uint8_t) (i >> 8);
        b = (uint8_t) (i >> 0);

        // Compute the expected result of `a + b`
        expected = a + b;

        // Compute `a + b` using `add_first_order_8bit`
        actual = add_with_fn(a, b, add_first_order_8bit);
        if (actual != expected) {
            error_msg = "add_first_order_8bit failed\n";
            goto error;
        }

        // Compute `a + b` using `add_xor_8bit`
        actual = add_with_fn(a, b, add_xor_8bit);
        if (actual != expected) {
            error_msg = "add_xor_8bit failed\n";
            goto error;
        }

        // Compute `a + b` using `add_bitwise_8bit`
        actual = add_bitwise_8bit(a, b);
        if (actual != expected) {
            error_msg = "add_bitwise_8bit failed\n";
            goto error;
        }

        // Print result
        printf("result: %" PRIu8 " + %" PRIu8 " = %" PRIu8 "\n", a, b,
               actual);
    }

    return 0;
error:
    fprintf(stderr, "\n------ ERROR ---------\n%s", error_msg);
    printf("result: %" PRIu8 " + %" PRIu8 " = %" PRIu8 "\n", a, b, actual);
    return 1;
}