Ca.cpp

Go to the documentation of this file.

/*
 * Copyright (C) 2009 Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
 *
 * This file is part of nucad (Non-Uniform CA Designer).
 *
 * nucad is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * nucad is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with nucad.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "config.h"
#include "Ca.h"
#include "Color.h"

#ifndef BUILDING_DOX
#   include <iostream>
#endif

#ifndef CA_CYCLIC_NEIGHBORHOOD
#   define CA_CYCLIC_NEIGHBORHOOD 0
#endif

std::ostream& operator<< (std::ostream &str, const CaState &ca) {
    for (unsigned row = 0; row < ca.size(); ++row) {
        for (unsigned col = 0; col < ca.size(); ++col)
            str << " " << ca.getCellAtPos(Pos(row,col));
        str << std::endl;
    }
    return str;
}

void writeRule(std::ostream &str, const TRule5N &rule) {
    static const unsigned CENTER = 1 << 0;
    static const unsigned TOP    = 1 << 1;
    static const unsigned RIGHT  = 1 << 2;
    static const unsigned BOTTOM = 1 << 3;
    static const unsigned LEFT   = 1 << 4;

    // top
    str << "  ";
    for (unsigned i = 0; i < RULE_WIDTH; ++i) {
        bool next = rule[i];
        if ((i & CENTER) == rule[i])
            continue;
        str << (next
                ? Color(C_LIGHT_GREEN)
                : Color(C_LIGHT_RED))
            << static_cast<bool>(i & TOP)
            << Color(C_NO_COLOR) << "      ";
    }
    str << std::endl;

    // left, self, right
    for (unsigned i = 0; i < RULE_WIDTH; ++i) {
        bool next = rule[i];
        if ((i & CENTER) == rule[i])
            continue;
        str << (next
                ? Color(C_LIGHT_GREEN)
                : Color(C_LIGHT_RED))
            << static_cast<bool>(i & LEFT) << " "
            << static_cast<bool>(i & CENTER) << " "
            << static_cast<bool>(i & RIGHT) << "  "
            << Color(C_NO_COLOR);
    }
    str << std::endl;

    // bottom
    str << "  ";
    for (unsigned i = 0; i < RULE_WIDTH; ++i) {
        bool next = rule[i];
        if ((i & CENTER) == rule[i])
            continue;
        str << (next
                ? Color(C_LIGHT_GREEN)
                : Color(C_LIGHT_RED))
            << static_cast<bool>(i & BOTTOM)
            << Color(C_NO_COLOR) << "      ";
    }
    str << std::endl;
}

bool applyRule(const CaState &ca, Pos pos, const TRule5N &rule) {
    bool state = ca.getCellAtPos(pos);

    // FIXME: performance impact
    unsigned char idx = ca.getCellAtPos(neighbor(pos, D_LEFT));
    idx <<= 1; idx |= ca.getCellAtPos(neighbor(pos, D_BOTTOM));
    idx <<= 1; idx |= ca.getCellAtPos(neighbor(pos, D_RIGHT));
    idx <<= 1; idx |= ca.getCellAtPos(neighbor(pos, D_TOP));
    idx <<= 1; idx |= state;

#if DEBUG_RULE_APPLICATION
        std::cerr << std::endl;
        std::cerr << "  "
            << static_cast<bool>(idx & (1 << 1))
            << std::endl;
        std::cerr << static_cast<bool>(idx & (1 << 4)) << " "
            << static_cast<bool>(idx & (1 << 0)) << " "
            << static_cast<bool>(idx & (1 << 2)) << std::endl;
        std::cerr << "  " << static_cast<bool>(idx & (1 << 3))
            << std::endl << "--> " << rule[idx]
            << std::endl << std::endl;
#endif // DEBUG_RULE_APPLICATION

    return rule[idx];
}

bool applyRules(CaState &ca, const ICaRules *rules) {
    // make snapshot (synchronous CA's state change)
    CaState last(ca);

    for (unsigned row = 0; row < ca.size(); ++row) {
        for (unsigned col = 0; col < ca.size(); ++col) {
            const Pos pos(row, col);
            TRule5N rule;
            rules->getRuleAtPos(pos, rule);
            const bool nextState = applyRule(last, pos, rule);
            ca.setCellAtPos(pos, nextState);
        }
    }

    return last != ca;
}

// /////////////////////////////////////////////////////////////////////////////
// CaState implementation
CaState::CaState(size_t size):
    size_(size)
{
    assert(size);
    bitset_.resize(size*size, false);
}

size_t CaState::size() const {
    return size_;
}

bool CaState::getCellAtPos(Pos pos) const {
#if CA_CYCLIC_NEIGHBORHOOD
    if (-1 == pos.row)
        pos.row += size_;
    else if (static_cast<TCoord>(size_) == pos.row)
        pos.row = 0;

    if (-1 == pos.col)
        pos.col += size_;
    else if (static_cast<TCoord>(size_) == pos.col)
        pos.col = 0;
#endif

    if (pos.row < 0 || pos.col < 0
            || size_ <= static_cast<size_t> (pos.row)
            || size_ <= static_cast<size_t> (pos.col))
        return false;
    else
        return bitset_[pos.row * size_ + pos.col];
}

void CaState::setCellAtPos(Pos pos, bool val) {
#if CA_CYCLIC_NEIGHBORHOOD
    if (-1 == pos.row)
        pos.row += size_;
    else if (static_cast<TCoord>(size_) == pos.row)
        pos.row = 0;

    if (-1 == pos.col)
        pos.col += size_;
    else if (static_cast<TCoord>(size_) == pos.col)
        pos.col = 0;
#endif

    if (pos.row < 0 || pos.col < 0
            || size_ <= static_cast<size_t> (pos.row)
            || size_ <= static_cast<size_t> (pos.col))
        return;
    bitset_[pos.row * size_ + pos.col] = val;
}

bool CaState::operator== (const CaState &other) const {
    return size_ == other.size_
        && bitset_ == other.bitset_;
}

// /////////////////////////////////////////////////////////////////////////////
// CaEvaluator implementation
#ifndef BUILDING_DOX
struct CaEvaluator::Private {
    IGate           *gate;
    IGateBinding    *binding;
    CaEvalParams    params;
};
#endif

CaEvaluator::CaEvaluator(
        const IGate &gate,
        const IGateBinding &binding,
        const CaEvalParams &params):
    d(new Private)
{
    d->gate = gate.clone();
    d->binding = binding.clone();
    d->params = params;
}

CaEvaluator::~CaEvaluator() {
    delete d->binding;
    delete d->gate;
    delete d;
}

size_t CaEvaluator::caSize() const {
    return d->params.caSize;
}

float CaEvaluator::eval(const ICaRules *ca) {
    const IGate &gate = *(d->gate);
    const IGateBinding &binding = *(d->binding);
    const TBus cnt = 1 << d->gate->nInputs();
    const unsigned nSteps = d->params.nSteps;
    unsigned score = 0;

    // for each input value
    for(TBus in = 0; in < cnt; ++in) {
        const TBus exp = gate[in];

        // initialize CA
        CaState state(d->params.caSize);
        binding.setInput(state, in);

        unsigned match = 0;
        for(unsigned step = 0; step < nSteps; ++step) {
            // synchronous rule application
            bool live = applyRules(state, ca);

            // obtain gate's output from cell matrix
            TBus out = binding.getOutput(state);
            if (out == exp) {
                ++ match;
            } else {
                // hamming distance projection
                const TBus nOut = d->gate->nOutputs();
                unsigned ham = 0;
                for (unsigned i = 0; i < nOut; ++i) {
                    TBus mask = 1 << i;
                    if (static_cast<bool>(out & mask) != static_cast<bool>(exp & mask))
                        ++ ham;
                }
                match *= nOut - ham;
                match /= nOut;
            }
            if (!live) {
                // nothing has changed in last step, we are on a good way
                if (out == exp)
                    match = nSteps << 1;
                else
                    match <<= 1;

                // nothing has changed in the last step, there is absolutely
                // no chance anything can change in the next step
                // let's stop it
                break;
            }
        }

        // include partial score (per input) to the sum
        score += match;
    }

    // normalize score to range <0, 1>
    return static_cast<float>(score)/(cnt*(nSteps << 1));
}

bool CaEvaluator::cntSteps(const ICaRules *ca, unsigned &min, unsigned &max) {
    const IGate &gate = *(d->gate);
    const IGateBinding &binding = *(d->binding);
    const TBus cnt = 1 << d->gate->nInputs();
    const unsigned maxSteps = d->params.nSteps;
    min = maxSteps;
    max = 0;

    // for each input value
    for(TBus in = 0; in < cnt; ++in) {
        unsigned step;

        // initialize CA
        CaState state(d->params.caSize);
        binding.setInput(state, in);

        // simulate and count steps
        bool live = true;
        for(step = 0; live && step < maxSteps; ++step) {
            live = applyRules(state, ca);
            TBus out = binding.getOutput(state);
            TBus exp = gate[in];
            if (!live && out != exp)
                return false;
        }

        if (live && step == maxSteps)
            // CA didn't stop in the limit defined by params.nSteps
            return false;

        // update min/max
        if (step < min)
            min = step;
        if (max < step)
            max = step;
    }

    // CA stopped in the limit for all possible inputs, it seems working
    return true;
}

namespace {
    void writeCaState(
            std::ostream &str,
            const CaState &state,                       // current state
            const CaState &inputs,                      // inputs mask
            const CaState &outputs,                     // output mask
            const CaState &desiredOutputs,              // desired output vals
            const CaState &lastState,                   // last state
            bool preferInput = false)                   // true to show inputs
    {
        const size_t size = state.size();
        assert(size == inputs.size());
        assert(size == outputs.size());
        assert(size == desiredOutputs.size());
        assert(size == lastState.size());

        for (unsigned row = 0; row < size; ++row) {
            for (unsigned col = 0; col < size; ++col) {
                Pos pos(row, col);

                // obtain values on current position
                bool val = state.getCellAtPos(pos);
                bool in = inputs.getCellAtPos(pos);
                bool out = outputs.getCellAtPos(pos);
                bool outOk = out && (val == desiredOutputs.getCellAtPos(pos));
                bool change = val ^ lastState.getCellAtPos(pos);

                str << " ";

                // select color according to priority
                if (change)
                    str << Color(C_YELLOW);
                else if (preferInput && in)
                    str << Color(C_LIGHT_BLUE);
                else if (outOk)
                    str << Color(C_LIGHT_GREEN);
                else if (out)
                    str << Color(C_LIGHT_RED);
                else if (in)
                    str << Color(C_LIGHT_GREEN);

                str << val;
                if (in || out || change)
                    str << Color(C_NO_COLOR);
            }

            // end of row
            str << std::endl;
        }
    }
}

void CaEvaluator::simulate(const ICaRules *rules, std::ostream &str, TBus in) {
    const IGate &gate = *(d->gate);
    const IGateBinding &binding = *(d->binding);
    const size_t caSize = d->params.caSize;
    const unsigned maxSteps = d->params.nSteps;

    // obtain input mask
    CaState inputs(caSize);
    binding.setInput(inputs, static_cast<TBus>(-1));

    // obtain output mask
    CaState outputs(caSize);
    binding.setOutput(outputs, static_cast<TBus>(-1));

    // we need it to highlight matched/mismatched output values
    CaState desiredOutputs(caSize);
    binding.setOutput(desiredOutputs, gate[in]);

    // initialize CA and write its initial state
    CaState state(caSize);
    binding.setInput(state, in);
    writeCaState(str, state, inputs, outputs, desiredOutputs, state, true);
    str << std::endl;

    // simulate CA and write its state after each step
    bool live = true;
    for(unsigned step = 0; live && step < maxSteps; ++step) {
        CaState last(state);
        live = applyRules(state, rules);
        str << Color(C_LIGHT_BLUE) << "--- step: " << (step + 1)
            << Color(C_NO_COLOR) << std::endl;
        writeCaState(str, state, inputs, outputs, desiredOutputs, last);
        str << std::endl;
    }
}

void CaEvaluator::simulate(const ICaRules *rules, std::ostream &str) {
    const TBus cnt = 1 << d->gate->nInputs();

    // for each input value
    for(TBus in = 0; in < cnt; ++in) {
        str << Color(C_LIGHT_GREEN) << "--- input: " << in
            << Color(C_NO_COLOR) << std::endl;
        this->simulate(rules, str, in);
    }
}

---