generator.h

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <sstream>
#include <string>
#include <list>
#include <utility>

using std::string;

#define ASSERT assert

typedef uint64_t Val;

enum Op {
	DUMMY_OP, // 0
	FIRST_OP,
	IF0 = FIRST_OP, // 1
	FOLD,     // 2
	NOT,
	SHL1,     // 4
	SHR1,
	SHR4,     // 6
	SHR16,
	AND,      // 8
	OR,
	XOR,      // 10
	PLUS,
	C0,       // 12
	C1,       // 13
	VAR,      // 14
	TFOLD,
	MAX_OP
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class OpSet
{
public:
	OpSet() : set_(0) {}

	void add(Op op) { set_ |= 1 << op; }
	bool has(Op op) { return set_ & (1 << op); }
	void del(Op op) { set_ &= ~(1 << op); }

	int set_;
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Context
{
public:
	Context(): count(0) {}

	void push(Val val) { values[count++] = val; }
	void pop() { ASSERT(count); --count; }

	Val get(int id) { return values[id]; }

    int count;
    Val values[1000];
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Expr
{
public:
    Expr();
	Expr(Op op, Expr* e1 = NULL, Expr* e2 = NULL, Expr* e3 = NULL);
	Expr(Op op, int var_id);
    ~Expr();

    Val run(Val input);
	Val eval(Context* ctx);

    string program();

private:
	friend class Generator;

	string code();
    Val do_fold(Context* ctx);

    Op    op;
    int   id; // for VAR
	int   count;
	Expr* opnd[3];
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Callback
{
public:
	virtual ~Callback() {}
	virtual bool action(Expr* e) = 0;
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Generator
{
public:
    void generate(int size, Callback* callback = NULL);
    void add_allowed_op(Op op) { allowed_ops_.add(op); }
    void allow_all();

private:
	void gen();
    void emit(Expr e, int opnds);
	void built();

    Expr* program;

    bool scoped[50];
	Expr arena[50];
	Expr* parents[50];
	int ptr;
	int next_opnd;
	int left;

	int count;
	bool done;
	bool allow_fold;

	OpSet allowed_ops_;
	int used_ops_[MAX_OP];

	Callback* callback_;
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Verifier: public Callback
{
public:
	Verifier() : count(0) {}
	void add(Val input, Val output);

	virtual bool action(Expr* program);

protected:
	typedef std::list< std::pair<Val, Val> > Pairs;

	Pairs pairs;
	int count;
};

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

class Printer: public Callback
{
public:
	Printer() : count(0) {}
    virtual bool action(Expr* e);

private:
	int count;
};