tycho/species/operand_table.cpp

/* "Species" - a CoreWars evolver.  Copyright (C) 2003 'Varfar'
 *
 * This program 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 1, or (at your option) any later
 * version.
 *
 * This program 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 this program; if not, write to the Free Software Foundation, Inc.,
 * 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "operand_table.hpp"
#include "species.hpp"

#include "opcode_branch_lookup.hpp"

#include <fstream>
using namespace std;

/*************** COperandBin implementation ******************************/

COperandTable::COperandBin::COperandBin(const unsigned coresize) {
	_coresize = coresize;
	// work out how many bins
	_bins = 1;
	for(unsigned i=1; i<(_coresize/2); i <<= 1) {
		_bins++;
	}
	// and actually assign them
	_bin = new unsigned[_bins];
	for(unsigned i=0; i<_bins-1; i++) {
		_bin[i] = 1 << i;
	}
	_bin[_bins-1] = _coresize/2;
}

unsigned COperandTable::COperandBin::bin(const unsigned idx) const { // get the max of this bin
	if(safety_checks)
		if(idx < 0 || idx >= _bins)
			PANIC(MISC,"invalid bin index",NULL);
	return _bin[idx];
}

unsigned COperandTable::COperandBin::get(const unsigned operand) const { // index of bin this operand falls into
	const unsigned op = (operand < (_coresize/2)) ? operand: (_coresize - operand); // fold, discard sign
	for(unsigned i=0; i<_bins; i++) {
		if(op <= _bin[i])
			return i;
	}
	PANIC(MISC,"Bad bin for operand",NULL);
	return (_bins-1); // dumb compiler!
}

void COperandTable::COperandBin::dump(ostream &out) const {
	out << "there are " << _bins << " bins: ";
	for(unsigned i=0; i<_bins; i++) {
		out << _bin[i] << ' ';
	}
	out << endl;
}

/*************** COperandEntry implementation *****************************/

COperandTable::COperandEntry::COperandEntry(const COperandBin *bins): _bins(bins) {
	_count = 0;
	_bin = new unsigned[_bins->bins()];
	for(unsigned i=0; i<_bins->bins(); i++) {
		_bin[i] = 0;
	}
}

COperandTable::COperandEntry::COperandEntry(const COperandBin *bins,istream &in): _bins(bins) {
	_count = bread_unsigned(in);
	_bin = new unsigned[_bins->bins()];
	unsigned sum = 0;
	for(unsigned i=0; i<_bins->bins(); i++) {
		_bin[i] = bread_unsigned(in);
		sum += _bin[i];
	}
	if(sum != _count) {
		PANIC(MISC,"error reading in operand prob table",NULL);
	}
}

void COperandTable::COperandEntry::learn(const unsigned operand) {
	_bin[_bins->get(operand)]++;
	_count++;
}

void COperandTable::COperandEntry::save(ostream &out) const {
	bwrite_unsigned(out,_count);
	for(unsigned i=0; i<_bins->bins(); i++)
		bwrite_unsigned(out,_bin[i]);
}

void COperandTable::COperandEntry::dump(ostream &out) const {
	out << _count << " sampled: ";
	for(unsigned i=0; i<_bins->bins(); i++)
		out << _bin[i] << ' ';
	out << endl;
}

unsigned COperandTable::COperandEntry::suggest() const {
	const unsigned TARGET_BIN = CRand::irand(_count),
		CORESIZE = _bins->coresize();
	unsigned y = 0;
	for(unsigned i=0; i<_bins->bins(); i++) {
		y += _bin[i];
		if(y > TARGET_BIN) {
			unsigned ret;
			if(0 == i) {
				ret = CRand::irand(_bins->bin(i));
			} else {
				ret = (_bins->bin(i-1) + CRand::irand(_bins->bin(i)-_bins->bin(i-1)));
			}
			if(0 == CRand::irand(2)) // flip sign?
				ret = (CORESIZE - 1 - ret);
			return ret;
		}
	}
	PANIC(MISC,"roulette off end of COperandTable::COperandTable::suggest",NULL);
}

/*************** COperandTable implementation *****************************/

const char *COperandTable::FILE_KEY = "operands_file";

COperandTable::COperandTable(const char *lookup_filename):
	COperand(0) {
	_type = TABLE;
	load(lookup_filename,false);
}

COperandTable::COperandTable(const field_t coresize):
	COperand(coresize) {
	_type = TABLE;
	_operand_bin = new COperandBin(_coresize);
	for(unsigned i=0; i<OPCODE_LAST; i++) {
		_operand[(OPCODE)i][A] = new COperandEntry(_operand_bin);
		_operand[(OPCODE)i][B] = new COperandEntry(_operand_bin);
	}
}

// actual query point
void COperandTable::rnd(insn_t &instruction,const Field field) {
	switch(field) {
		case A:
			instruction.a = _operand[instruction.opcode()][A]->suggest();
			break;
		case B:
			instruction.b = _operand[instruction.opcode()][B]->suggest();
			break;
		default:
			PANIC(MISC,"bad field in COperandTable::rnd()",NULL);
	}
}

void COperandTable::load(const char *lookup_filename,const bool check_constraints) {
	unsigned file_version;
	_filename = lookup_filename;
	ifstream in(lookup_filename,ifstream::binary|ifstream::in);
	if(!in.good())
		PANIC(MISC,"error openning file",lookup_filename);
	file_version = bread_unsigned(in);
	if(FILE_VERSION != file_version)
		PANIC(MISC,"bad file version in lookup",lookup_filename);
	unsigned coresize = bread_unsigned(in);
	if(check_constraints)
		if(_coresize != coresize)
			PANIC(MISC,"bad coresize in ",lookup_filename);
	_coresize = coresize;
	_operand_bin = new COperandBin(_coresize);
	for(unsigned i=0; i<OPCODE_LAST; i++) {
		_operand[(OPCODE)i][A] = new COperandEntry(_operand_bin,in);
		_operand[(OPCODE)i][B] = new COperandEntry(_operand_bin,in);
	}
	if(!in.good())
		PANIC(MISC,"error reading from file",lookup_filename);
	in.close();
}

void COperandTable::learn(const char *rc_filename) {
	warrior_t warrior;
	// load it
	cout << "loading " << rc_filename << ".." << endl;
	asm_fname(rc_filename,&warrior,_coresize); // will panic fatally if can't
	// and analyse
	for(int i=0; i<warrior.len; i++) {
		_operand[warrior.code[i].opcode()][A]->learn(warrior.code[i].a);
		_operand[warrior.code[i].opcode()][B]->learn(warrior.code[i].b);
	}
}

void COperandTable::save(const char *lookup_filename) {
	ofstream out(lookup_filename,ofstream::binary|ofstream::trunc);
	bwrite_unsigned(out,FILE_VERSION);
	bwrite_unsigned(out,_coresize);
	for(unsigned i=0; i<OPCODE_LAST; i++) {
		_operand[(OPCODE)i][A]->save(out);
		_operand[(OPCODE)i][B]->save(out);
	}
	if(!out.good())
		PANIC(MISC,"error writing to ",lookup_filename);
	out.close();
}

void COperandTable::dump(ostream &out) {
	_operand_bin->dump(out);
	for(unsigned i=0; i<OPCODE_LAST; i++) {
		// A operand
		out << MNEMONIC_OPCODE((OPCODE)i) << "-A: ";
		_operand[(OPCODE)i][A]->dump(out);
		// B operand
		out << MNEMONIC_OPCODE((OPCODE)i) << "-B: ";
		_operand[(OPCODE)i][B]->dump(out);
	}
}

void COperandTable::bwrite_u16_t(std::ostream &out,const u16_t i) {
	out.write(reinterpret_cast<const char*>(&i),sizeof(i));
}

void COperandTable::bwrite_unsigned(std::ostream &out,const unsigned i) {
	out.write(reinterpret_cast<const char*>(&i),sizeof(i));
}

u16_t COperandTable::bread_u16_t(std::istream &in) {
	u16_t i;
	in.read(reinterpret_cast<char*>(&i),sizeof(i));
	return i;
}

unsigned COperandTable::bread_unsigned(std::istream &in) {
	unsigned i;
	in.read(reinterpret_cast<char*>(&i),sizeof(i));
	return i;
}

// and saving
void COperandTable::write_ini(ostream &os) {
	os << type_key() << "=" << impl_desc(type()) << endl
		<< FILE_KEY << '=' << _filename << endl;
}

void COperandTable::write_override_ini(std::ostream &os,const COperand *parent) {
	if(parent == this) // nothing to do?
		return;
	write_ini(os);
}

// from COperand
void COperandTable::read_ini_impl(INIFile &ini) {
	KeyValuePair *kvp;
	kvp = ini.get(FILE_KEY); if(0 == kvp) PANIC(MISC,FILE_KEY,"expected"); // null?!
	kvp->getValueAsString(_filename);
	load(_filename.c_str());
}

COperand *COperandTable::read_override_ini_impl(INIFile &ini) { /* loads freq values; if any freq values are
	specified, then a copy of this freq will be made; all unspecified values in the new
	class will be "inherited" from this one, and any specified values will be overriden.  If nothing
	is specified, then this will be returned */
	string filename;
	COperand *ret = this;
	KeyValuePair *kvp;
	kvp = ini.get(FILE_KEY);
	if(0 != kvp) { // specified?
		kvp->getValueAsString(filename);
		if(_filename != filename) {
			ret = COperand::read_ini(ini,_coresize);
		}
	}
	return ret;
}