Programming Assignment 5 - Moving Rectangles

Advanced Programming II, Spring 2003

Due Date

This assignment is due by 2:00 p.m. on Tuesday, 1 April.

See the assignment turn-in page (last modified on 21 January 2003) for instructions on turning in your assignment.

Background

Operations that move byte rectangles from one place in memory to another became important with the rise of bit-mapped displays.

A rectangle can be represented as a triple (s, h, w), where (for simplicity, assume that all units are in bytes)

s is the start of the rectangle in memory; that is, s is the memory address of the upper-left element in the rectangle.
h is the height of the rectangle; that is, h is the number of rows in the rectangle.
w is the width of the rectangle; that is, w is the number of columns in the rectangle.

s, h, and w must all be non-negative. The rectangle (s, contains hw bytes.

Storing two-dimensional rectangles in one-dimensional memory requires mapping the rectangles into memory. One common mapping is known as row-major form, which stores the rows of a rectangle successively in memory. Given a rectangle (s, h, w) with non-zero height and width, the rectangle is stored memory as

The Problem

Write a program that reads from std-in a sequence of zero or more rectangle-move instructions and writes to std-out a code sequence that implements the given rectangle-move instructions. The generated moving code should have the following properties:

It's correct; that is, the rectangle (S, H, W) appears in its entierety in the rectangle (D, H, W) after the rectangle-move instruction's been executed.
It's as fast as possible.

Input

Input consists of a sequence of zero or more rectangle-move instructions. A rectangle-move instruction has the form

rmove d s h w

and moves the rectangle (s, h, w) to the rectangle (d, h, w). The source and destination rectangles may overlap arbitrarily.

Each input line should either be blank (contain only space characters) or contain a single, complete, correct rectangle-move statement; blank input lines should be ignored. Any other input line should cause your program to write an informative error message to std-err and immediately terminate execution with no further processing.

Each rmove instruction input has no relation to any other rmove instruction input. In solving this problem, you should consider each rmove instruction in isolation.

Output

Output should be a sequence of memory-move instructions that implement the input rectangle-move instructions. Each instruction sequence should begin with the associated rectangle-move instruction, followed by the sequence of memory-move instructions that implements the rectangle-move instructions.

A memory-move instruction has the form

movei d s

where i is the number of bytes to be moved, d is the destination address to which the bytes will be moved, and s is the source address from which the bytes will be moved. The effect of the memory-move instruction movei d s is

for j = 0 to i - 1
  memory[d + j] = memory[s + j]

The number of bytes moved (that is, i) must be 8, 4, 2, or 1; both the source and destination address must be divisible by i (that is, both s % i == 0 and d % i == 0 must be true). Assume that all movei instructions take the same time to execute.

Successive instruction sequences should be separated from the next by a blank line. The instruction sequences should be output in the same order the rectangle-move instructions were input; the instruction sequence for the first rectangle-move instruction should be output first, and so on.

For example, if the input is

rmove 20 10 1 2

the output will be

rmove 20 10 1 2 
move2 20 10

The output

rmove 20 10 1 2
move1 20 10
move1 21 11

is incorrect because it takes too long. However, the correct output for input

rmove 21 11 1 2

rmove 21 11 1 2
move1 21 11
move1 22 12

The output

rmove 21 11 1 2 
move2 21 11

is incorrect because neither 21 nor 11 is evenly divisible by 2.

This page last modified on 7 March 2003.