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

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