Faster, LUT-based elementary cellular automaton

lut-automaton.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <memory.h>

uint8_t get_bits(uint8_t *in_base, size_t start_bit, size_t n_bits)
{
    size_t split = start_bit % 8;
    uint8_t *base = &in_base[start_bit/8];

    uint8_t slice;

    /* Grab up to 2 bytes */
    if(split == 0)
    {
        /* Aligns with bottom of byte */

        slice = base[0];
    }
    else
    {
        /* Split across 2 bytes */

        slice = base[0] >> split;
        slice |= base[1] << (8 - split);
    }

    slice &= (1 << n_bits) - 1;

    return slice;
}

void put_bits(uint8_t *out_base, size_t start_bit, uint8_t bits, size_t n_bits)
{
    size_t split = start_bit % 8;
    uint8_t *base = &out_base[start_bit/8];

    uint8_t mask = (1 << n_bits) - 1;

    bits &= (1 << n_bits) - 1;

    /* Write up to 2 bytes */
    if(split == 0)
    {
        /* Aligns with bottom of byte */

        uint8_t tmp = base[0];
        tmp &= ~mask;
        tmp |= bits;
        base[0] = tmp;
    }
    else
    {
        /* Split across 2 bytes */

        /* Put the lower byte back */
        base[0] &= ~(mask << split);
        base[0] |= (bits << split);

        /* Put the upper byte back */
        base[1] &= ~(mask >> (8 - split));
        base[1] |= (bits >> (8 - split));
    }
}

void step(uint8_t* lut, uint8_t* in, uint8_t* out, size_t len_bits)
{
    /* Bit position of input */
    size_t input_bit_pos = 0;

    while((input_bit_pos + 8) < len_bits)
    {
        /* Get 8 bits from the right place */
        uint8_t input_slice = get_bits(in, input_bit_pos, 8);

        uint8_t output_bits = lut[input_slice];

        size_t output_bit_pos = input_bit_pos + 1;

        /* put 6 bits in the right place */
        put_bits(out, output_bit_pos, output_bits, 6);

        input_bit_pos += 6;
    }
}

void gen_lut(uint8_t *lut, uint8_t rule)
{
    for(size_t i = 0; i < 256; i++)
    {
        uint8_t pattern = (uint8_t)i;
        uint8_t output = 0;

        for(size_t j = 0; j < 6; j++)
        {
            /* Grab 3 bits */
            uint8_t slice = pattern >> j;
            slice &= 0x7;

            uint8_t new_bit = (rule >> slice) & 0x1;

            output |= (new_bit << 6);
            output = output >> 1;
        }

        lut[i] = output;
    }
}

#define STATE_BYTES 10


void print_state(uint8_t *state, size_t len)
{
    for(size_t i = 0; i < len * 8; i++)
    {
        /* Each bit */

        size_t byte_index = i / 8;
        /* Shift state to match rule */

        size_t bit_in_byte = i % 8;

        if((state[byte_index] >> bit_in_byte) & 0x1)
        {
            printf("#");
        }
        else
        {
            printf(" ");
        }
    }

    fflush(stdout);
}


int main(int argc, char **argv)
{
    int rule = 30;
    if(argc > 1)
    {
        rule = atol(argv[1]);
    }


    /* Do a test */
    while(0)
    {
        uint8_t test[5];
        uint8_t bits = rand();
        int offset = rand() * 24 / RAND_MAX;
        int nbits = rand() * 8 / RAND_MAX;

        bits &= ((1 << nbits) - 1);

        put_bits(test, offset, bits, nbits);

        uint8_t r = get_bits(test, offset, nbits);

        assert(r == bits);
    }


    uint8_t state[STATE_BYTES];
    uint8_t state2[STATE_BYTES];
    memset(state, 0, STATE_BYTES);
    memset(state2, 0, STATE_BYTES);

    uint8_t lut[256];
    gen_lut(lut, rule);

    while(1)
    {
        state[0] = rand();
        state[STATE_BYTES-1] = rand();
        step(lut, state, state2, STATE_BYTES * 8);
        print_state(state2, STATE_BYTES);

        getchar();

        state2[0] = rand();
        state2[STATE_BYTES-1] = rand();
        step(lut, state2, state, STATE_BYTES * 8);
        print_state(state, STATE_BYTES);

        getchar();
    }
    return 0;
}