Arrange timed code.cpp

//// 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) //

1. 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 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 labes that /// are defined in this block. struct block { typedef map<string, int> labelmap; int

string

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 appended 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; }