Advanced Programming II, Spring 2003

Programming Assignment 5 - An Example Solution

Table of Contents

Introduction

This note presents an example solution to the fifth programming assignment.

Design

Before getting to the design, it's a good idea to clear away some of this problem's underbrush. All that stuff about matrices is just eye-wash; as the Background Section explained, the matrices are represented as continguous sequences of memory bytes.

The problem requires two things: that the source sequence be moved to the destination without corruption, and that the move be accomplished with as few instructions as possible.

Ignoring possible hardware failures, the only way data can become corrupted during a move is if the source and destination sequences overlap, and the source data clobbers data at the destination before the destination data are moved. In turn, this happens when the source sequence appears before (has lower addresses than) the destination sequence and the source data are moved in order of increasing address.

The solution to this problem is simple: move the data in order of decreasing addresses. Unfortunately, this solution is not universal, because it can clobber data when the destination sequence appears before and overlaps the source sequence.

The solution to the second problem - minimual instruction count - requires a bit more work. Greed is one possible solution: at any point during the move use the instruction that can legally move the largest amount of data. This is simple, but does greed result in an optimal (that is, minimal) solution?

A little thought shows that it does. Suppose that greed moves four bytes at address i (that is, four is the largest power of two that evenly divides i) and assume that an address j, i < j < i + 4 is evenly divisible by eight (it should be clear to you that j = i + 2).

In such a circumstance, greed has failed because the sequence of instructions 

move2 d   i
move8 d+2 i+2

moves ten bytes while the greedy sequence of instructions 

move4 d   i
move4 d+4 i+4

can move at most eight bytes (if j = i + 2 is divisible by eight, then i + 4 = j + 2 cannot be).

However, can such a circumstance exist? If i is divisible by four, then i + 2 cannot be divisible by eight and the initial circumstance cannot exist. Generalizing this argument shows that greed is optimal for this problem.

The rmove Instruction

The class representing an rmove instruction is straightforward. The class fields are constant, which requires an explicit assignment operator that can assign to the fields by casting away the const-ness. The assignment operator doesn't check for self-assignment because nothing bad happens with unchecked self-assignment, except for a little wasted time (but don't forget to balance out that wasted time with the time wasted checking for self-assignment when it doesn't occur).

Making class fields directly accessible is considered bad programming practice because it leaks information (how fields are implemented) to the outside world. That the fields are constant doesn't mitigate anything, because the const-ness is easily (although obviously) circumvented, as shown by the assignment operator.

Just to make things interesting, this assignment throws exceptions if anything goes wrong. 

<rmove-exception.h>=

#ifndef _rmove_exception_h_defined_
#define _rmove_exception_h_defined_

#include <stdexcept>

struct rmove_exception : public std::invalid_argument { 

  rmove_exception(const std::string & emsg) 
    : invalid_argument(emsg) { }

  };

#endif
Defines rmove_exception, rmove-exception.h (links are to index).

This code is written to a file (or else not used).

Although the code could throw a string or character array, it's good programming practice to define an explicit exception to make it clear not so much what's being thrown as what's being caught.

In the absence of special requirements, the easiest way do define a new exception is to create it as a child of an existing exception. In this case the standard invalid-argument exception was close in nature to the kind of exception this code should throw, and it accepts a string argument which can be used to carray an eror message. See main() for an example of the how these exceptions are caught. 

<rmove-inst.h>=

#ifndef _rmove_inst_h_defined_
#define _rmove_inst_h_defined_

#include "read.h"

struct rmove_inst {

  const unsigned dst, src, ht, wd;

  rmove_inst()
    : dst(0), src(0), ht(0), wd(0) { }

  rmove_inst(std::istream & iss)
    : dst(read<unsigned>(iss, "destination address")),
      src(read<unsigned>(iss, "source address")),
      ht(read<unsigned>(iss, "rectangle height")),
      wd(read<unsigned>(iss, "rectangle width")) { }

  rmove_inst(unsigned d, unsigned s, unsigned h, unsigned w)
    : dst(d), src(s), ht(h), wd(w) { }

  rmove_inst & operator = (const rmove_inst & rhs) { 
    const_cast<unsigned &>(dst) = rhs.dst;
    const_cast<unsigned &>(src) = rhs.src;
    const_cast<unsigned &>(ht) = rhs.ht;
    const_cast<unsigned &>(wd) = rhs.wd;
    return *this;
    }
  };

#endif
Defines rmove_inst, rmove-inst.h (links are to index).

This code is written to a file (or else not used).

Main

Once you get past the exception handling, main() has nothing surprising. Notice that using exceptions don't releive you of the need to program defensively, in this case against unexpected exceptions being thrown. 
<main.cc>=

#include <iostream>
#include <cstdlib>
#include "read-rmi.h"
#include "write-rmi.h"
#include "rmove-exception.h"


int main() {
  try {
    std::string sep;
    rmove_inst rmi;

    while (read_rmi(std::cin, rmi)) {
      std::cout << sep;
      sep = "\n";
      write_rmi(std::cout, rmi);
      }
    }
  catch (rmove_exception rme) {
    std::cerr << rme.what() << ".\n";
    exit(EXIT_FAILURE);
    }
  catch (...) {
    std::cerr << "Unexpected exception caught.\n";
    exit(EXIT_FAILURE);
    }
  }
Defines main, main.cc (links are to index).

This code is written to a file (or else not used).

Reading rmove Instructions

Reading a rmove instruction from an input stream is straightforward. 
<read-rmi.h>=

#ifndef _read_rmi_h_defined_
#define _read_rmi_h_defined_

#include <istream>
#include "rmove-inst.h"

// Read an rmove instruction from the given input stream; return true iff an
// instruction was read.

   extern bool read_rmi(std::istream &, rmove_inst &);

#endif
Defines read-rmi.h (links are to index).

This code is written to a file (or else not used).

 
<read-rmi.cc>=

#include <sstream>
#include <iostream>
#include "read-rmi.h"
#include "str-utils.h"
#include "read.h"


static void
make_rmi(const std::string & str, rmove_inst & rmi) {

  // Read and store an rmove instruction from the given string, which should 
  // contain exactly one rmove instruction. Throw an rmove-exception if it 
  // doesn't.

  std::istringstream iss(str);

  if (read<std::string>(iss, "\"rmove\" identifier") != "rmove")
    throw rmove_exception("Rmove instruction doesn't begin with \"rmove\"");

  rmi = rmove_inst(iss);

  char c;
  iss >> c;
  if (!iss.eof())
    throw rmove_exception("Junk following rmove instruction");
  }


bool
read_rmi(std::istream & is, rmove_inst & rmi) {
  
  std::string str;

  if (!str_utils::read_next_nonblank_line(is, str))
    return false;

  make_rmi(str, rmi);

  return true;
  }
Defines read_rmi, read-rmi.cc (links are to index).

This code is written to a file (or else not used).

Writing rmove Instructions

If you understood the discussion given in the Design Section, then the following code to write an rmove instruction and its associated move instructions should not present any difficulties.

It is possible to put up a good argument that this code is poorly designed because it mixes what should be two separate functions: computing the optimal block moves and writing the results. In this code's defense, I'll point out that, while the functions are mixed, the subroutines implementing each functions are fully separate, and that anybody offended by mixture will have an easy time pulling out the functions into separate files. I didn't think it was worth the bother to do so. 

<write-rmi.h>=

#ifndef _write_rmi_h_defined_
#define _write_rmi_h_defined_

#include <ostream>
#include "rmove-inst.h"

// Write the given rmove instruction to the given output stream.

   extern void write_rmi(std::ostream &, const rmove_inst &);

#endif
Defines write-rmi.h (links are to index).

This code is written to a file (or else not used).

 
<write-rmi.cc>=

#include <sstream>
#include <iterator>
#include "write-rmi.h"
#include "str-utils.h"

// Deja vu c++ style.

   static unsigned size(unsigned, unsigned, unsigned);


static str_utils::str_vec
move_data(unsigned dst, unsigned src, unsigned bytes) {

  // Return a vector containing the minimum number of move instructions to 
  // move the given number of bytes from the given source address to the given 
  // destination address.

  str_utils::str_vec strs;

  while (bytes > 0) {
    const unsigned s = size(dst, src, bytes);
    std::ostringstream oss;

    oss << "move" << s << " " << dst << " " << src << "\n";
    strs.push_back(oss.str());

    dst += s;
    src += s;
    bytes -= s;
    }

  return strs;
  }


static unsigned
size(unsigned d, unsigned s, unsigned b) {

  // Return the largest power of two no more than the smaller of 8 and b that 
  // divides both d and s evenly.

  unsigned i = 1;

  while ((i*2 <= b) and (i < 8))
    i *= 2;

  while (i > 1)
    if ((d % i == 0) and (s % i == 0))
      return i;
    else
      i /= 2;

  return 1;
  }


void
write_rmi(std::ostream & os, const rmove_inst & rmi) {

  os << "rmove " 
     << rmi.dst << " " << rmi.src << " "
     << rmi.ht << " " << rmi.wd << "\n";

  const unsigned bytes = rmi.ht*rmi.wd;
  const str_utils::str_vec moves = move_data(rmi.dst, rmi.src, bytes);

  if ((rmi.dst + bytes <= rmi.src) or 
      (rmi.src + bytes <= rmi.dst) or
      (rmi.dst < rmi.src))
    std::copy(moves.begin(), moves.end(),
              std::ostream_iterator<std::string>(os));
  else if (rmi.src < rmi.dst)
    std::copy(moves.rbegin(), moves.rend(),
              std::ostream_iterator<std::string>(os));
  }
Defines write-rmi.cc (links are to index).

This code is written to a file (or else not used).

 The only thing left is the generic read() function that throws rmove exceptions. 

<read.h>=

#ifndef _read_h_defined_
#define _read_h_defined_

#include "rmove-exception.h"

template < typename T >
T
read(std::istream & is, const char * const what) {

  // Read and return a value of the given type; throw an rmove-exception 
  // if anything goes wrong.

  T t;
  
  if (!(is >> t))
    throw rmove_exception(std::string("Input error during ") + what + 
                          std::string(" read"));

  return t;
  }

#endif
Defines read, read.h (links are to index).

This code is written to a file (or else not used).

Index

This page last modified on 13 May 2003.