build comma-delimited text file that has an entry for every file
on the drive, with the full path to the file, and includes size,
starting cluster, and type (dir vs. file; D or F)

(this could also be fixed-size binary with MAX_PATH=260 pathname
allocated, but would be easier to debug, etc. if it's text. just
a bit slower...but there are far fewer files than there are
clusters)

  type,size,cluster,path

  [Directory Entry Sort File]
  F,59641,139,\avadash.xbe
  D,5813,918,\Media

sort the list by path name, or type and path

this tells us every file we need to move around, and where it starts

next, build a list of where each entry needs to start, by simply
iterating over the sorted file in order.  each entry starts after
the end of the previous one, so everything is packed in the sort
order.  the output from this step can be an array of clusters, each
entry's index matching the line number in the sorted file
(binary results, not text)

  [New Starting Clusters File]
  00000001
  00000005
  00000018
  0000002A
  ...

then create a file that indicates which clusters need to move where
to make the [New Starting Clusters File] list happen.  this is simply
a matter of walking each entry in the sort file, walking the FAT
entries starting from its first cluster, and mapping that cluster
number to the associated [New Starting Clusters File], offset by
the relative cluster number for the file.

so for entry #1, assume the file is 59641 bytes (4 clusters) long and
has a starting cluster of 0289A8B6 and is split into 2 fragments.
we start to walk the FAT at cluster 0289A8B6, so 0289A8B6 goes to our
new starting cluster of 1  (from our [New Starting Clusters File]
mapping), 0289A8B7 goes to the starting cluster +1, so it maps to 2,
and so on.

repeat for every entry in the sort file, in order
 
  [Cluster Mapping File]
  0289A8B6 00000001
  0289A8B7 00000002
  0013F251 00000003
  0013F252 00000004
  ...

we also need to update the starting cluster number within each directory,
going through all directories' "file" data and changing all of the non-
deleted entries, and probably eliminating the deleted ones (essentially
rewrite and pack the directory "file" data).  changing the starting
clusters in the directories should be done immediately after a file is
actually moved. this allows the user to abort, and is the safest way to
do it in case the defrag fails to complete.

==

needs work:

how to shuffle files (such as on a very full hard drive)
how to find the parent directory of any entry so we can update starting cluster after we've moved it



helpful links:

Differences between FATX and MS-DOS FAT
  http://xbox-linux.sourceforge.net/articles.php?aid=2002173055527

Xbox Partitioning and Filesystem Details
  http://xbox-linux.sourceforge.net/articles.php?aid=2002173055657