//
// Copyright (c) 2013 Danny Havenith
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <limits>
#include <boost/foreach.hpp>
using namespace std;
/// Simple struct that can be used as an input to describe blocks of assembly instructions with jumps and labels
/// one instance of this struct is created for every instruction word in the assembly code. The member "label" refers to the
/// label at that location, if one is defined and the member "jumpto" has the name of the label to which this instruction jumps, if it is
/// a branch or jump instruction.
struct labelinfo {
string label;
string jumpto;
};
/// a contiguous block of assembly instructions.
/// This structure holds information about the size of the block,
/// all relative jumps that emanate from this block and all labels that
/// are defined in this block.
struct block
{
// a map from label strings to relative positions
// for labels this is the relative position of the label
// for jumps this is the position of the jump instruction that jumps to that label.
typedef map<string, int> labelmap;
int size;
string name;
labelmap labels;
labelmap jumps;
bool operator<( const block &other) const
{
return name < other.name;
}
};
/// Parse labelinfo structs and create disjunct blocks.
/// This function will traverse the range of labelinfos and create blocks on-the-go.
/// The last statement of a block is recognized by the label "END". Whenever this label is encountered all
/// statements so far will be combined in one block and this block will be added to the result.
vector<block> parse_blocks( labelinfo *begin, labelinfo *end)
{
vector<block> result;
int current_line = 0;
block current_block;
while (begin != end)
{
if (begin->label == "END")
{
current_block.size = current_line + 1;
result.push_back( current_block);
current_line = 0;
current_block = block();
}
else
{
if (!begin->label.empty())
{
if (current_line == 0) current_block.name = begin->label;
current_block.labels[begin->label] = current_line;
}
if (!begin->jumpto.empty())
{
current_block.jumps[begin->jumpto] = current_line;
}
++current_line;
}
++begin;
}
return result;
}
/// Given a sequence of blocks, determine the absolute addresses of the labels that
/// appear in each block.
block::labelmap map_labels( const vector<block>& blocks)
{
block::labelmap label_addresses;
// determine absolute labels
int current_block_startaddress = 0;
BOOST_FOREACH( const block &b, blocks)
{
BOOST_FOREACH( const block::labelmap::value_type &label, b.labels)
{
label_addresses[label.first] = label.second
+ current_block_startaddress;
}
current_block_startaddress += b.size;
}
return label_addresses;
}
/// Determine whether a sequence of blocks matches the criterium of valid jumps.
/// This criterium is matched if all jumps are close enough to their destination labels.
/// Close enough, in this case, means that the offset between jump and destination must fall within [-63,64]
/// This function is faster than the calculate_fit() function because it can terminate immediately if it finds a jump
/// that does not qualify.
bool is_fit( const vector<block> &blocks)
{
block::labelmap label_addresses = map_labels(blocks);
// see if all jumps are in range.
int current_block_startaddress = 0;
BOOST_FOREACH( const block &b, blocks)
{
BOOST_FOREACH( const block::labelmap::value_type &jump, b.jumps)
{
int offset = label_addresses[jump.first] - (jump.second + current_block_startaddress);
if (offset > 64 || offset < -63) return false;
}
current_block_startaddress += b.size;
}
return true;
}
/// This is largely a copy of the is_fit() function with some changes. Instead of returning a fit/not-fit boolean,
/// this function returns a score that is calculated as the maximum (absolute) jump distance.
/// This function is slightly less efficient than that is_fit() function, because it needss to complete the
/// calculation, even if the score is higher than the fitness criterium.
int calculate_fit( const vector<block> &blocks)
{
block::labelmap label_addresses = map_labels( blocks);
// calculate the maximum jump offset in this sequence of blocks.
int max_offset = 0;
int current_block_startaddress = 0;
BOOST_FOREACH( const block &b, blocks)
{
BOOST_FOREACH( const block::labelmap::value_type &jump, b.jumps)
{
int offset = label_addresses[jump.first] - (jump.second + current_block_startaddress);
if (offset > max_offset) max_offset = offset;
if (-offset > max_offset) max_offset = -offset;
}
current_block_startaddress += b.size;
}
return max_offset;
}
/// Description of the code blocks. This was created with some spreadsheet magic from the original code spreadsheet
/// because I was too lazy to implement input text parsing.
labelinfo labels[] = {
{ "M2", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "H1"},
{ "", ""},
{ "", "L16"},
{ "", ""},
{ "L9", ""},
{ "", ""},
{ "L5", ""},
{ "", ""},
{ "", "L1"},
{ "", ""},
{ "", "M1"},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "L4"},
{ "", ""},
{ "L12", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
{ "L1", ""},
{ "", "M2"},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "L8"},
{ "", ""},
{ "L15", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
{ "L10", ""},
{ "", "M3"},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "L12"},
{ "", ""},
{ "L4", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
{ "M4", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "H1"},
{ "", ""},
{ "", "L9"},
{ "", ""},
{ "L16", ""},
{ "", ""},
{ "L13", ""},
{ "", ""},
{ "", ""},
{ "", "L10"},
{ "", ""},
{ "", "M4"},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "L15"},
{ "", ""},
{ "L8", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
{ "M1", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "H2"},
{ "", ""},
{ "", "L9"},
{ "", ""},
{ "END", ""},
{ "M3", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", "H2"},
{ "", ""},
{ "", "L16"},
{ "", ""},
{ "END", ""},
{ "H1", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
{ "H2", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "", ""},
{ "END", ""},
};
/// Print out the optimum sequence of code blocks (=with minimum max jump distance).
/// This function will simply iterate over all 40K permutations of 8 blocks and calculate the score for each
/// permutation.
int main()
{
vector<block> blocks = parse_blocks( labels, labels + sizeof labels/sizeof labels[0] );
sort( blocks.begin(), blocks.end());
BOOST_FOREACH( const block &b, blocks)
{
cout << b.name << "\n";
}
vector<block> best_blocks;
int min_offset = numeric_limits<int>::max();
do
{
int new_offset = calculate_fit( blocks);
if (new_offset < min_offset)
{
best_blocks = blocks;
min_offset = new_offset;
cout << min_offset << ", ";
}
} while (next_permutation( blocks.begin(), blocks.end()));
if (is_fit(best_blocks))
{
cout << "\nSuccess:\n";
}
else
{
cout << "\nNothing\n";
}
BOOST_FOREACH( const block &b, best_blocks)
{
cout << b.name << "\n";
}
return 0;
}