Volume Number: 18 (2002)
Issue Number: 07
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

One Time Pad

A one-time pad, used properly, provides a simple and unbreakable method of encryption. The “pad” is a random block of data equal in length to the message to be encoded. Two copies of the pad are needed, one for the message sender and one for the message receiver. The message to be encrypted is combined with the data in the pad by, for example, an exclusive OR; transmitted to the recipient, and decoded by the inverse operation. To be unbreakable, the pad must consist of truly random data, and it must be used only once.

Of course, you still need to securely exchange a one-time pad for each message to be encrypted. Let’s imagine that this is too much trouble, so what we are going to do instead is to use some common text as the basis for our one-time pad. We’ll select the “random” block as an offset from the first character in that text. And we’ll reuse our “one time” over and over again for different messages, with different offsets. Since the text isn’t random, and the one-time pad is used multiple times, we may have compromised security somewhat. This is a Good Thing, because your Challenge is to crack a sequence of messages encrypted with this scheme.

The prototype for the code you should write is:

void InitOneTimePad(
   const char *oneTimePad,
   /* NULL terminated text to be used for the one-time pad */
   /* You should ignore (skip) any characters not in the range 0x20-0x7E, inclusive */
   const char *dictionary[],
   /* list of NULL-terminated words in the vocabulary, sorted in ASCII order */
   long numDictionaryWords
);

char *DecryptMessage(
   /* return decrypted message */
   const char *encryptedMessage,
   /* NULL terminated text to decode */
   /* Guaranteed to contain only characters in the range 0x20-0x7E, inclusive */
   long *offset
   /* offset into the oneTimePad that you determine to be the basis for encryption */
);

void TermOneTimePad(void);

Your InitOneTimePad routine will be called each time our Intelligence Service captures a new one-time pad being used by our adversary. You will also be given a sorted dictionary of words in the vocabulary of our adversary. You can allocate memory and do whatever analysis might be appropriate.

For each intercepted message, your DecryptMessage routine will be called with the encrypted text. Fortunately, we know that our encrypting adversary uses the oneTimePad in a consistent manner. S/he uses a section of the pad starting at an offset known to the sender and receiver, but unknown to us. The section of the pad used is as long as the encrypted message, ignoring any characters in the pad (beyond the offset) outside the range of printable ASCII characters (0x20-0x7E). The nth character x of the clear text is encrypted as x+y-0x20, modulo the legal range of the character set, where y is the nth legal character of the oneTimePad beyond the offset value. So, if the oneTimePad [offset] starts with “When in the Course of human events”, and your clear text is “The British are coming.”, the encrypted text would be “,QKnB\Xt^\N%b[rWUmYUgv”, where denotes a nonprintable (and ignored) carriage return and denotes a space character that you might not otherwise notice. Note that nonprintable characters are counted in determining the starting position (offset) within the pad.

You should determine the section of the one-time pad that was used for encryption, decrypt the message, store the oneTimePad offset used for this message, and return a NULL-terminated string containing the clear text.

Your TermOneTimePad routine should return any dynamically allocated memory.

The winner of this Challenge will be the entry that correctly solves all test cases while incuring the lowest cost. Solutions will incur a cost of 10 points per millisecond of execution time, including the time incurred for initialization, decryption, and termination. You can earn a bonus of up to 25% reduction of incurred cost based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Winner of the February, 2002 Challenge

In February, we asked contestants to defragment a simulated disk drive. Scoring was based on making the fewest number of block moves, regardless of block size. We also awarded a bonus of 25% for incorporating optional features, like an untimed display of defragmentation progress, and another 25% bonus based on elegance of the solution. Congratulations to Jonny Taylor for taking first place in the Disk Defragmentation Challenge.

Six people entered solutions for this Challenge and five of those solved the problem correctly. (The sixth violated the constraint against overlapping the source and destination blocks.) The best scoring solution, by Jan Schotsman, was submitted after the deadline and was therefore not eligible to win. Three entries, including both Jonny’s and the second-place entry from Ernst Munter, provided options to display the evolving solution or to replay the solution. Jonny also provided menu options to control the speed of the display. Jonny’s entry required approximately 25% fewer moves to defragment the disks, although it required nearly three times as much computation time to do so.

Several of the entries chose to defragment the simulated files in ways that also consolidated all free space into one block. This behavior was not required, and Jonny chose not to do that. Instead, he chose to leave large fragments in place where possible, reasoning that these are less likely to be relocated on densely occupied disks without being split up into multiple pieces. Jonny first employs an “intelligent move” algorithm, described in the ConsiderMovingFragment routine, that selects and moves file fragments which, when moved, would allow other fragments to be moved to their final destination. For fragments that remain after applying the intelligent algorithm, the GuaranteedMoveFragment routine moves all remaining file fragments to their final destination.

I evaluated solutions using five test cases, one small and relatively simple, and the others simulating densely populated disks with varying levels of fragmentation. The subjective evaluation of features was based on whether a display option was present, and on other menu options provided to control the solution and the display. The “elegance” criterion was based on code commentary, coding style, cleverness of the algorithm, and on the conciseness of the code. Johnny’s winning entry was downrated a little because of the complexity of the code, but earned points for being well commented. As it turns out, entries were ranked in the same order both with and without considering the subjective criteria.

The table below lists, for each of the solutions submitted, the total number of disk block moves used to defragment the desks, the total execution time in microseconds, the raw score based on moves and execution time, the subjective bonuses based on elegance and features, and the total score after taking the bonuses into consideration. It also lists the programming language used for each entry and the operating system used for the entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Top Contestants . . .

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

. . .and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

Here is Jonny’s winning Disk Defragmentation solution:

PROGRAMMER’s Defrag.cp
Copyright © 2002
Jonny Taylor

// #include files omitted because of length; see online archive

/*   The algorithm works as follows:
Load the information from the input file about where on the disk the fragments
            of each file are to begin with
      2.   Choose where on disk we want each file to end up
      3.   “Intelligent” algorithm: where possible, move fragments to their final positions
            with minimal unnecessary moves
      4.   “Guaranteed” algorithm: move any remaining fragments to their final positions 
            whatever additional moves this takes
   
   Three data structures are used by these algorithms.
      FreeRange represents a single contiguous range of disk blocks that are not
      currently occupied by any file fragment. Every FreeRange is as large as possible          
      –  i.e. it is not possible to have
         one FreeRange for blocks 4-9 and another for 10-14 in existance at the same 
         time
      Fragment represents a single contiguous range of disk blocks belonging to the 
         same file
      FileLayout represents a single file, and has a linked list of all the fragments that 
         make it up
   
   In addition, there are four search trees that are maintained. These allow Fragments 
   to be searched by current position and by the final position that they will end up in, 
   and allow  FreeRanges to be searched by position and by length. The tree code is 
   explained and implemented in Trees.cp, but all that really matters is that insertion, 
   deletion and searching can be done in log(N) time.
   
   There are quite a few nasty cases to the algorithms I have used, which need special 
   treatment. This is particularly true for the “guaranteed” algorithm because it must be 
   able to handle anything at all.
   However for the most part the special cases are handled within a single function. 
   Functions that perform tasks such as “move a block out of the way” will do what 
   they are defined to do (though they may be allowed to fail), and will handle any 
   special cases themselves.
   
   The solution is fairly quick on reasonably complex test cases (such as test case 2 in 
   the sample code). It slows down roughly linearly as the number of files and 
   fragments on the disk increases. This results in unacceptably long running times for 
   very nasty test cases with big disks full of tiny files. However I suspect that any 
   solution would do the same.
*/
   
struct FileLayout;
struct Fragment;
struct FreeRange;

typedef struct FreeRange
{
   long   firstBlock;
   long   lastBlock;
   Node   *positionTreeNode;
   Node   *lengthTreeNode;
// method declarations omitted, see online archive
} FreeRange;

typedef struct FileLayout
{
   Fragment   *firstFragment;
   Boolean      placed;
   long      fileLength;
// method declarations omitted, see online archive
} FileLayout;

typedef struct Fragment
{
   long      startBlock;
   long      finalStartBlock;
   long      numBlocks;
   FileLayout   *owningFile;
   Boolean      inFinalPosition;
   Node      *currentStartTreeNode;
   Node      *finalStartTreeNode;
   long      firstFileBlock;
   
   Boolean      blockedBySelf;
   long      fragmentsBlockingThis;
   
   long      processedInThisLoop;
   long      score;
   Fragment   *next;
   Fragment   *nextInMoveList, *prevInMoveList;
   Fragment   *nextInFinalStartList, *prevInFinalStartList;
// method declarations omitted, see online archive
} Fragment;

#define kNotProcessed         -1
#define kMaxArraySize         32768
#define ABS(VAL)            ( (VAL) < 0 ? -(VAL) : (VAL) )
#define MIN(A, B)            ( (A) < (B) ? (A) : (B) )

FileLayout   **theFiles, **unplacedFilesSortedByLength;
Fragment   **sortedFragmentList;   
   /* Sorted array of fragment pointers. 
      Sort key varies depending on which bit of code we are in   */
Fragment   *firstFinalStart;      
   /* Linked list of fragments, ordered by final start   */
Fragment   *prevInList;
   /* Only used when setting up firstFinalStart   */

extern DisplayType      displayProgress;
extern AnimationType   animationType;

/*   Roots for the search trees   */
Node   *fragmentCurrentStartRoot,*fragmentFinalStartRoot;
Node   *freeRangeLengthRoot,*freeRangePositionRoot;
/*   General global variables   */
long      totalFragments, totalBlocks, totalFiles, 
      fragmentsPositioned;
long      uniqueSearchIndex, firstFreeBlock;
/*   Heads of linked lists of fragments that are free to move to their final positions   */
Fragment   *firstFragmentToMove, *firstOverlappingFragmentToMove;

// function prototypes omitted, see online archive

Main Defragmentation Code
// DoTests deleted for length, see online archive

void Defragment(void)
{
// test case loop omitted for length, see online archive
      
      totalFragments = 0;
      totalBlocks = 0;
      totalFiles = 0;
      fragmentsPositioned = 0;
      fragmentCurrentStartRoot = NULL_NODE;
      fragmentFinalStartRoot = NULL_NODE;
      freeRangeLengthRoot = NULL_NODE;
      freeRangePositionRoot = NULL_NODE;

// input logic omitted for length, see online archive

      ChooseFilePositions();

      /*   Rebuild the free range list to represent the current file positions
         (instead of their final positions)   */
      firstFreeBlock = 0;
      InorderTreeWalk(fragmentCurrentStartRoot, BuildFreeRangeTree);

      if (totalBlocks - 1 >= firstFreeBlock)
         new FreeRange(firstFreeBlock, totalBlocks - 1);

      /*   Move the fragments to their final positions      */
      RearrangeFragments();

      /* Release memory   */
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
         delete theFiles[fileNum];
      KillAllFreeRanges(freeRangeLengthRoot);
// test case completion logic omitted for length, see online archive
}

void RearrangeFragments(void)
{   
   Fragment   *fragPtr;

   SetDescriptionString(“Moving fragments (intelligent algorithm)”);

   for (fragPtr = firstFinalStart; fragPtr != NULL; 
            fragPtr = fragPtr->nextInFinalStartList)
   {
      if (!fragPtr->inFinalPosition)
      {
         /*   Check which fragments’ FINAL POSITION is blocked solely by the
            CURRENT position of this one      */
         fragPtr->ForEveryFragmentBlockedByThisOne(
               MarkFragmentAsBlockedBy);
      }
   }
   
   firstFragmentToMove = NULL;
   firstOverlappingFragmentToMove = NULL;
   
   /* First do a check for fragments that can move immediately to their destination 
      square */
   for (fragPtr = firstFinalStart; fragPtr != NULL; fragPtr = 
            fragPtr->nextInFinalStartList)
   {
      if ((!fragPtr->inFinalPosition) &&
         (fragPtr->fragmentsBlockingThis == 0))
      {
         fragPtr->FreeToMoveToFinalPosition();
      }
   }
   MoveFragmentsToDestinationSquares();
   
   uniqueSearchIndex = 0;
   for (fragPtr = firstFinalStart; fragPtr != NULL; 
         fragPtr = fragPtr->nextInFinalStartList)
      ConsiderMovingFragment(fragPtr);
   
   /*   There will probably be fragments left to rearrange (at least if the disk is densely 
      populated). Switch to a simple, but failsafe, algorithm to place these remaining 
      fragments      */
   SetDescriptionString(
         “Moving fragments (guaranteed algorithm)”);
   GuaranteedRearrange();
}

void BuildFreeRangeTree(void *keyPtr)
void KillAllFreeRanges(Node *x)
// these routines omitted for length, see online archive

Choosing File Positions
/*   Before I actually move any fragments, I decide what final position I want each file 
   to end up in. We could just aim to position the first file at the start of the disk, the 
   next one immediately after that, and so on. However in this problem this is not a 
   requirement. Instead we can choose to place the files anywhere we want, as long as 
   each individual file is contiguous. It is advantageous to choose a final position for 
   as many files as possible, such that one of its fragments is already in its final 
   position, and doesn’t have to be moved at all.
   
   I can’t see an easy way of determining the optimum file layout. Instead I employ a 
   greedy algorithm, picking the fragment that looks best as the first “anchor” 
   fragment, and so on. I experimented with several methods of scoring each fragment 
   as a potential anchor, taking into account factors such as:
      - Whether any fragments of the file overlap their final destination (a bad thing as 
         they then can’t be moved in a single step)
      - Whether any other fragments from the same file are also in their final positions 
         (a good thing)
      - Some attempt to determine how much selecting this file would prevent us from 
         selecting several other files
   In the end, I didn’t bother with this. Densely-populated disks are the ones that take 
   longest to solve, and the most moves to rearrange. In those cases the limiting factor 
   is the size of the fragments; a large fragment is likely to be impossible to move 
   around intact, and will have to be split up to move it. I therefore decided to 
   prioritise large fragments when selecting anchors.
   
   Incidentally, a final factor, that I have not tried to take into account at all, is the size 
   of the free spaces that are left in the final layout. I suspect it would be better to 
   select a final layout with fewer, larger spaces since this makes it easier to rearrang 
   the disk.
   
   Once I have selected as many anchor fragments as I can, there will probably be files 
   left unplaced. I don’t try and do anything clever with these. I just put them at the 
   start of the largest empty space that is available. Unfortunately, there is a problem. 
   Choosing the anchor fragments means the remaining free space may be split into a 
   number of ranges. It may be impossible to fit the remaining files into the spaces 
   (remembering the files must be contiguous). Even if it is possible, it may not be 
   possible to quickly find a valid layout. There is no obvious way of seeing when we 
   have chosen too many anchor fragments. Instead, I use a binary search method. I try 
   placing as many anchor fragments as I can, and see if I can position the remaining 
   files. If I can’t, I try with half as many anchor fragments, and continue refining the 
   value until I have a reasonable one.   */

void ChooseFilePositions(void)
{
   long      fileNum;
   Fragment   *theFragment;
   
   SetDescriptionString(“Choosing file positions”);

   /*   Sort the fragments by their length   */
   qsort(sortedFragmentList, totalFragments, sizeof(Fragment*), 
            Fragment::QSCompareByLength);

   /*   Try .........*/
   if (ArrangeFilesWithAnchorLimit(totalFiles) == false)
   {
      long   minimumAnchorCount = 0, maximumAnchorCount = 
         totalFiles + 1;
      long   middle;

      UnplaceAll();
      for (long iter = 0; iter < 5; iter++)
      {
         middle = (minimumAnchorCount + maximumAnchorCount) / 2;
         
         if (ArrangeFilesWithAnchorLimit(middle) == true)
            minimumAnchorCount = middle;
         else
            maximumAnchorCount = middle;
         
         if (maximumAnchorCount - minimumAnchorCount == 1)
            break;
         
         UnplaceAll();
      }
      if (middle != minimumAnchorCount)
      {
         UnplaceAll();
         ArrangeFilesWithAnchorLimit(minimumAnchorCount);
      }
   }   
   
   /*   Now we have settled on an arrangement, build the final start tree and linked list.
      Because this tree remains static, we don’t actually need to do all the red-black 
      insertions. We could just determine the sort order and then build a balanced 
      binary search tree by hand. However, doing RBInsert for every fragment is faster 
      than a quicksort of every fragment. However all we really need to do is a 
      quicksort of every file. If the number of files is less than half the number of 
      fragments, it turns out it is worth building the tree by hand. This will also lead to 
      a slightly better-balanced tree, which will speed up tree searches a little.
      
      We also take the opportunity to see which fragments are already in their final 
      position. If they are we mark them as such; if they aren’t then we add them to the 
      list of fragments (sortedFragmentList), which is ordered by final start. This linked 
      list will remain static until we come to the “guaranteed algorithm”, at which point 
      it may grow as fragments are split   */

   firstFinalStart = NULL;
   prevInList = NULL;
   if (totalFragments / totalFiles >= 2)
   {
      /*   Sort the files by final position and thereby sort the fragments   */
      qsort(theFiles, totalFiles, sizeof(FileLayout*), 
            FileLayout::QSCompareByFinalStart);
      long fragNum = 0;
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
      {
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
         {
            sortedFragmentList[fragNum++] = theFragment;

            theFragment->CheckIfInFinalPosition();
         }
      }
      
      /*   Build the tree, given the sorted fragment list   */
      fragmentFinalStartRoot = BuildBalancedTree(sortedFragmentList,
             0, totalFragments - 1, NULL_NODE);
   }
   else
   {
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
      {
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
         {
            ASSERT(theFragment->finalStartTreeNode == NULL);

            theFragment->CheckIfInFinalPosition();

            theFragment->finalStartTreeNode = new Node;
            theFragment->finalStartTreeNode->data = theFragment;
            theFragment->finalStartTreeNode->keyLong = 
               theFragment->finalStartBlock;
            theFragment->finalStartTreeNode->keysNodePtr = 
               &theFragment->finalStartTreeNode;
            RBInsert(&fragmentFinalStartRoot, 
               theFragment->finalStartTreeNode);
         }
      }
   }
}

Node *BuildBalancedTree(Fragment ** fragList, long first, 
            long last, Node *parent)
// this routine omitted for length, see online archive

Boolean ArrangeFilesWithAnchorLimit(long maxAnchors)
{
   long   fileNum, frag;
   long   numUnplacedFiles = 0;
   /*   Attempt to come up with a file arrangement that uses up to maxAnchors anchor 
      fragments   */

   /*   We start with no file positions chosen, and the whole disk available   */
   new FreeRange(0, totalBlocks - 1);
   
   /*   We should be able to leave some fragments where they are, and build up around 
      them the file that they are part of. I choose the largest fragments as a priority, 
      since they will be hardest to move around when we are rearranging the disk.
      This is not always ideal. For example, picking the largest fragment might prevent 
      us from picking a large number of slightly smaller ones. However it is the only 
      quick and simple way that I could find   */
   long numPlaced = 0;
   for (frag = totalFragments - 1; 
      (frag >= 0) && (numPlaced < maxAnchors); frag—)
   {
      Fragment   *fragPtr = sortedFragmentList[frag];
                        /* sortedFragmentList is currently sorted by length   */
      FileLayout   *owningFile = fragPtr->owningFile;
               
      if (!owningFile->placed)
      {
         /* This file has not been assigned a position yet Check if any other files we 
            have already positioned are blocking this position   */
         FreeRange *rangeAtStart = 
            (FreeRange*)DATA(TreeSearch(freeRangePositionRoot, 
                  &fragPtr->firstFileBlock,
                  FreeRange::FindRangeContainingBlock));
         if (rangeAtStart->lastBlock >= 
            fragPtr->firstFileBlock + owningFile->fileLength - 1)
         {
            /*   There is no file blocking this position   */
            owningFile->placed = true;
            owningFile->SetFinalPosition(rangeAtStart, 
                  fragPtr->firstFileBlock);
            numPlaced++;
         }
      }
   }
   
   /*   We now probably have some files left over, to try and fit into the gaps that are 
      left. My heuristic here is to start with the largest file, and place it in the largest 
      gap available. This is far from ideal, but I suspect that finding the optimum 
      solution is an NP-complete problem (similar to sack-filling problems), so I’m not 
      too bothered!   */

   /*   Sort the unplaced files in order of total length   */
   for (fileNum = 0; fileNum < totalFiles; fileNum++)
   {
      if (!theFiles[fileNum]->placed)
      {
         unplacedFilesSortedByLength[numUnplacedFiles] = 
            theFiles[fileNum];
         numUnplacedFiles++;
      }
   }
   qsort(unplacedFilesSortedByLength, numUnplacedFiles, 
         sizeof(FileLayout*), FileLayout::QSCompareByLength);
   
   for (fileNum = numUnplacedFiles - 1; fileNum >= 0; fileNum—)
   {
      FreeRange *chosenPosition = 
         (FreeRange*)DATA(TreeMaximum(freeRangeLengthRoot));
      if (chosenPosition->lastBlock - chosenPosition->firstBlock + 1 
                  < unplacedFilesSortedByLength[fileNum]->fileLength)
         chosenPosition = NULL;
      
      if (chosenPosition != NULL)
      {
         /*   Position the file at the start of the free range we have selected   */
         unplacedFilesSortedByLength[
               fileNum]->SetFinalPosition(chosenPosition, 
               chosenPosition->firstBlock);
      }
      else
      {
         /*   Failed to position the file. Break out immediately   */
         break;
      }
   }

   /*   Delete all the free ranges and their search trees. Either we are going to restart the 
      algorithm, or we are going to move on to the next phase, for which we need the 
      INITIAL free ranges, rather than the FINAL ones   */
   KillAllFreeRanges(freeRangeLengthRoot);
   freeRangeLengthRoot = NULL_NODE;
   freeRangePositionRoot = NULL_NODE;      

   if (fileNum >= 0)
   {
      /*   We didn’t manage to position all the files   */
      return(false);
   }
   return(true);
}

void FileLayout::SetFinalPosition(FreeRange *rangeToPlaceIn, 
            long finalStartBlock)
{
   for (Fragment *theFragment = firstFragment;
       theFragment != NULL;
       theFragment = theFragment->next)
   {
      theFragment->finalStartBlock = finalStartBlock;
      finalStartBlock += theFragment->numBlocks;
   }

   rangeToPlaceIn->RangeNotFree(firstFragment->finalStartBlock,
          fileLength);
}

void Fragment::CheckIfInFinalPosition(void)
void UnplaceAll(void)
// these routines omitted for length, see online archive

“Guaranteed” Algorithm
/*   We work through the fragments that have not yet been moved to their final 
   positions. For each one,clear any blocking fragments out of the way and move it to 
   where they were.
   This algorithm must be able to cope with all situations. This means that special 
   handling is necessary when temporary storage elsewhere on the disk is limited, and 
   when the fragment partially overlaps its final position   */

// this section deleted for length, see online archive

“Intelligent” Algorithm
/*   The idea is to identify fragments that, if moved, allow another fragment to be 
   moved to its destination.Hopefully, moving that fragment to its destination frees up 
   the space that another fragment needs to move into, and so on. For a disk with a 
   reasonable amount of free space (around half), this will move nearly all of the 
   fragments. For a disk with a very small amount of free space, it will not generally 
   work very well.

   Each fragment keeps track of how many other fragments are blocking it from being 
   moved to its final position
   
   1.   Find a fragment that is blocked by only one other fragment
   2.   See if it is possible to move that blocking fragment somewhere else
   3.   If THAT fragment could be moved to its destination were it not for one single 
      fragment blocking it, then repeat as many times as possible until we end up with a 
      blocking fragment we can’t move to its final destination
   4.   Move that fragment somewhere out of the way
   5.   Update the blockage information as a result of the move
   6.   While there are unblocked fragments, move them to their destinations, updating 
      the blockage information again
   
   There are two problems with this strategy. We might end up covering the same 
   ground several times. If we consider a long chain of dependencies before giving up, 
   we might follow that chain each time we encountered one of its members. Also, it is 
   possible to have a circular dependency chain where every fragment is waiting for 
   the next one in the loop. Under those circumstances we might end up following the 
   chain round and round for ever. To avoid both these cases I fill in the ‘unique search 
   index’ when I first process a fragment. If I come across a search index smaller than 
   the current one, I abort the search. This is not very elegant, but it works!*/

void ConsiderMovingFragment(Fragment *fragPtr)
{
   if ((!fragPtr->inFinalPosition) &&
      (fragPtr->fragmentsBlockingThis <= 1) &&
      (fragPtr->processedInThisLoop == kNotProcessed))
   {
      /*   This fragment is one that we want to be able to move   */
      Fragment   *fragToMove = fragPtr;
      FreeRange   *longestRangePtr = (FreeRange*)(TreeMaximum(
         freeRangeLengthRoot)->data);
      long      longestFreeRange = longestRangePtr->lastBlock – 
         longestRangePtr->firstBlock + 1;
      
      /*   Given the fragment that we want to move, find the one that is blocking it. 
         Check if that fragment can be moved   ...... continue description......*/
      uniqueSearchIndex++;
      fragPtr->processedInThisLoop = uniqueSearchIndex;
      do
      {
         /*   Find the fragment blocking this one   */
         Fragment *result = (Fragment*)DATA(TreeSearch(
            fragmentCurrentStartRoot, fragToMove,
            Fragment::FindOneBlockingTheKeyFragment));
         ASSERT(result != NULL);

         /*   If there isn’t anywhere we can move that fragment to, stop now   */
         if (result->numBlocks > longestFreeRange)
            break;
         
         /*   Processed in a previous loop, or already in this loop (in which case we have 
            found a ring where every fragment is preventing the next one from being 
            moved - moving any of these will allow all to be moved one after the other). 
            Stop the search   */
         if ((result->processedInThisLoop <= uniqueSearchIndex) &&
            (result->processedInThisLoop != kNotProcessed))
         {
            break;
         }
         
         /*   If we move ‘result’ we will be able to move ‘fragToMove’ into the space it has 
            left   */
         fragToMove = result;
         fragToMove->processedInThisLoop = uniqueSearchIndex;
         
         /*   If we get to a fragment that is blocked by more than one, we have reached 
            the end of the chain. Stop the loop.   */
      } while (fragToMove->fragmentsBlockingThis == 1);

      if ((fragToMove == fragPtr) &&
         (fragToMove->fragmentsBlockingThis != 0))
         return;         /*   Failed to find a place to move the one blocking it   */

      if ((fragToMove->processedInThisLoop < uniqueSearchIndex) &&
         (fragToMove->processedInThisLoop != kNotProcessed))
      {
         return;         /*   Already processed earlier   */
      }
         
      /*   Now we have decided on a fragment to move, make the move. We should have 
         checked earlier on that there a suitable space to move the fragment into. If we 
         are very unlucky, though,the new space we select will still be blocking the 
         range we are trying to free, so the call isn’t 100% guaranteed to allow any other 
         fragments to move.   */
      fragToMove->MoveOutOfTheWay();
      MoveFragmentsToDestinationSquares();
   }
}

void MarkFragmentAsBlockedBy(Fragment *theBlockedFragment, 
      Fragment *theBlocker)
// this routine omitted for length, see online archive

void MoveFragmentsToDestinationSquares(void)
{
   /*   While there are fragments queued as ready to move, move them to their final 
      destinations. Moving one fragment may add extra fragments to the lists. Moving 
      it may occasionally block one of the other fragments that are queued. In that case, 
      the fragment is removed from the queue automatically   */
   Fragment *fragToMove;
   do
   {
      while (firstOverlappingFragmentToMove != NULL)
      {
         fragToMove = firstOverlappingFragmentToMove;
         fragToMove->RemoveFromLists();
         fragToMove->MoveToFinalOverlappingPosition(true);
      }
      
      while (firstFragmentToMove != NULL)
      {
         fragToMove = firstFragmentToMove;
         fragToMove->RemoveFromLists();
         fragToMove->MoveToFinalPosition(true);
      }
   } while (firstOverlappingFragmentToMove != NULL);
}

void Fragment::ForEveryFragmentBlockedByThisOne(
      void (*theCallback)(Fragment *theBlockedFragment, 
      Fragment *theBlocker))
void Fragment::FragmentAboutToUnblock(
      Fragment *theBlockedFragment, Fragment *theBlocker)
void Fragment::FragmentAboutToBlock(Fragment *theBlockedFragment, 
         Fragment *theBlocker)
// these routines omitted for length, see online archive

void Fragment::FreeToMoveToFinalPosition(void)
{
   /*   This function is called when there is nothing preventing the fragment from 
      moving to its final position. We do not immediately move the fragment, though – 
      we just add it to the relevant queue so it will be moved in the next call to 
      MoveFragmentsToDestinationSquares. This function was probably called 
      because another fragment is about to move, unblocking this fragment’s final 
      position. That fragment might move to a new position that is STILL blocking this 
      fragment, though, so we will
      have to wait before we actually move this fragment   */
   ASSERT(nextInMoveList == NULL);
   ASSERT(prevInMoveList == NULL);
   if (blockedBySelf)
   {
      /*   Fragment is only blocked by itself. Add it to the list of ones to move.
         There is a separate list for these as we might want to wait for a bigger gap to be
         available as temporary storage   */
      nextInMoveList = firstOverlappingFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstOverlappingFragmentToMove = this;
   }
   else
   {
      /* Can be moved directly to final position   */
      nextInMoveList = firstFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstFragmentToMove = this;
   }
}

void Fragment::RemoveFromLists(void)
// this routine omitted for length, see online archive

Moving Fragments
void Fragment::MoveToPosition(long destBlock, Boolean 
         maintainBlockageCount)
{
   /*   Move the fragment as instructed, and inform any interested parties   */
   /*   We may want to keep track of which fragments are being blocked at the moment. 
      If so,maintainBlockageCount is ‘true’   */
   if (maintainBlockageCount)
   {
      /*   Inform other fragments that this fragment’s current position is about to become 
         free   */
      ForEveryFragmentBlockedByThisOne(FragmentAboutToUnblock);
   }
   
   /*   Mark the place it was as free   */
   FreeRange::FragmentRangeIsFree(this);
   
   OutputMoveInstruction(startBlock, destBlock, numBlocks, 
         inFinalPosition);
   startBlock = destBlock;
   
   /*   We might have moved it to its final destination by chance   */
   if (startBlock == finalStartBlock)
      inFinalPosition = true;

   /*   Do the standard processing for when a fragment has moved   */
   FragmentHasMoved(maintainBlockageCount);
}

void Fragment::MoveToPositionNoOutput(long destBlock)
// this routine omitted for length, see online archive

void Fragment::MoveOutOfTheWay(void)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalPosition(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalOverlappingPosition(Boolean maintainBlockageCount)
{
   /*   We want to find the most efficient way of making the move. Because the source 
      and destination ranges are not allowed to overlap for a move instruction, it cannot 
      be done with a single instruction. We could either move it somewhere completely 
      different and then back to its destination, or we could move it in several chunks, 
      but without using any extra temporary storage. This is treated as a special case 
      because there are several ways of doing it, and a number of nasty catches we need 
      to check for      */
   ASSERT(fragmentsBlockingThis == 0);
   ASSERT(blockedBySelf);
   
   long   movement = ABS(startBlock - finalStartBlock);
   long   blocksAvailable, firstBlockAvailable;

   /*   Start by working out how many steps it would take to move the fragment without 
      using any extra temporary storage.Calculate numBlocks/movement, rounded UP 
      */
   FreeRange   *bestRange = NULL;
   long      bestSteps = (numBlocks + movement - 1) / movement;
   long      blocksAvailableInBestRange, 
            firstBlockAvailableInBestRange;
   long      steps;
   
   if (bestSteps > 2)
   {
      /*   We would take at least two steps to move the fragment via any extra space we 
         might choose, so only consider other options if we can’t do it in two moves */

      /*   Find the biggest space available, and see how many steps it would take to move 
         the fragment via it. Note that this largest range may be the one that includes the 
         destination area, in which case not all
         of it is available as temporary storage   */
      FreeRange   *largestFreeRange = 
      (FreeRange*)DATA(TreeMaximum(freeRangeLengthRoot));
      
      if ((startBlock > finalStartBlock) &&
         (largestFreeRange->lastBlock == startBlock - 1))
      {
         /*   Overlap between source and dest fragment positions is at the end of the 
            destination,and overlap with this free range is at the start of the destination */
         blocksAvailable = finalStartBlock – 
               largestFreeRange->firstBlock;
         firstBlockAvailable = largestFreeRange->firstBlock;
      }
      else if ((startBlock < finalStartBlock) &&
             (largestFreeRange->firstBlock == startBlock + numBlocks))
      {
         /*   Overlap with existing fragment position is at the start of the destination, and 
            overlap with the free range is at the end of the destination */
         blocksAvailable = largestFreeRange->lastBlock – 
               (finalStartBlock + numBlocks) + 1;
         firstBlockAvailable = finalStartBlock + numBlocks;
      }
      else
      {
         /*   The free range we have found is somewhere completely different (the ideal 
            case!)   */
         blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
         firstBlockAvailable = largestFreeRange->firstBlock;
      }

      if (blocksAvailable > 0)
      {
         /*   Work out how many steps it would take to transfer the whole fragment.
            Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
         steps = 2 * ((numBlocks + blocksAvailable - 1) / 
            blocksAvailable);

         if (steps < bestSteps)
         {
            /*   This is the best option so far   */
            bestSteps = steps;
            bestRange = largestFreeRange;
            blocksAvailableInBestRange = blocksAvailable;
            firstBlockAvailableInBestRange = firstBlockAvailable;
         }
         
         if (blocksAvailable != largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1)
         {
            /*   The range we just looked at is the one that includes the destination 
               position. This has been taken into account in the calculations we just made 
               to rate it. However, this means that the second-largest free range may 
               actually be a better choice. Note that since the last range we considered 
               overlapped the destination, we know this
               one doesn’t      */
            largestFreeRange = (FreeRange*) DATA(TreePredecessor(
               largestFreeRange->lengthTreeNode));
            blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
            
            /* Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
            steps = (2 * ((numBlocks + blocksAvailable - 1) / 
               blocksAvailable));

            if (steps < bestSteps)
            {
               /*   This is the best option so far   */
               bestSteps = steps;
               bestRange = largestFreeRange;
               blocksAvailableInBestRange = blocksAvailable;
               firstBlockAvailableInBestRange = 
                  largestFreeRange->firstBlock;
            }
         }
      }
   }
   
   long   offset, blocksToMoveThisTime,
         blocksAlreadyMoved = 0,
         blocksLeftToMove = numBlocks;

   if (bestRange == NULL)
   {
      /*   The best way of moving it doesn’t use any additional storage. We move as 
         much as we can in one go, and this frees up another section that can be moved, 
         until the whole fragment has been moved   */

      /*   Starting from the end of the fragment, move it in chunks of size “movement”
         to its final position   */
      while (blocksLeftToMove > 0)
      {
         blocksToMoveThisTime = MIN(movement, blocksLeftToMove);
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
               blocksToMoveThisTime;
         else
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset,
               finalStartBlock + offset, blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
      }
   }
   else
   {
      /*   The best way of moving it is to move as much as possible into bestRange, and 
         from there to its final position, repeating until the whole fragment has been 
         moved   */

      /*   Starting from the end of the fragment, move it in chunks of size 
         “blocksAvailableInBestRange” to its final position via 
         firstBlockAvailableInBestRange   */
      while (blocksLeftToMove > 0)
      {
         blocksToMoveThisTime = MIN(blocksAvailableInBestRange, 
            blocksLeftToMove);
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
               blocksToMoveThisTime;
         else
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset, 
               firstBlockAvailableInBestRange,
                           blocksToMoveThisTime, false);
         OutputMoveInstruction(firstBlockAvailableInBestRange, 
               finalStartBlock + offset,
                           blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
      }
   }   
   
   /*   Update the internal information to take account of this move (it doesn’t matter 
      exactly how we achieved the move). Also notify any other fragments affected by 
      the move, so they can update
      their blockage counts   */
   inFinalPosition = true;
   if (maintainBlockageCount)
      ForEveryFragmentBlockedByThisOne(FragmentAboutToUnblock);
   FreeRange::FragmentRangeIsFree(this);

   startBlock = finalStartBlock;
   if (maintainBlockageCount)
      blockedBySelf = false;
   fragmentsPositioned++;
   if ((displayProgress == kDisplayBlocks) &&
      (animationType != kFastestAnimation))
   {
UpdateProgress(((float)(testCase - 1) + 
   ((float)fragmentsPositioned / (float)totalFragments)) / 
         (float)numTestCases, testCase);
   }

   /*   No need to resort the current-position tree as the fragment order hasn’t changed. 
      We do need to update its sort key, though   */
   currentStartTreeNode->keyLong = startBlock;

   if (maintainBlockageCount)
      ForEveryFragmentBlockedByThisOne(FragmentAboutToBlock);

   FreeRange::FragmentRangeNotFree(this);
}

void Fragment::FragmentHasMoved(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

Fragment *Fragment::SplitToFitLength(long lengthOfFirstPart)
// this routine omitted for length, see online archive

void OutputMoveInstruction(long from, long to, long blocksToMove, Boolean finalPosition)
{
   if (displayProgress == kDisplayBlocks)
      ClearDisplayedBlockRange(from, from + blocksToMove - 1);
   fprintf(outputFile, “%ld,%ld,%ld\n”, from, to, blocksToMove);
   if (displayProgress == kDisplayBlocks)
      SetDisplayedBlockRange(to, to + blocksToMove - 1, true, finalPosition);
}

// Search function section omitted for length, see online archive

// Main.cp, ReadExisting.cp, Trees.cp, Trees.h, Windows.cp omitted because of 
//  length; see online archive