Changes to speed up FindGap.

[KeepingRealBusy]

Jeroen and all others,

I have modified FindGap for 3.36 as follows, where the changes are identified by
C++ comments (//). I have not implemented the skip logic for MftExcludes yet,
nor tested the implemented changes yet (compiles correctly). This should speed
up this piece of logic. I guess a good test would be to name it FindGapNew, then
call both findGap and FindGapNew 1000 times for timing (one time test, then
report the times), then do a defrag calling both functions and comparing the
returns to insure that the returns are the same (probably need to do this on an
idle HD with no other I/O going on or the results could vary (by design)).

Anyone care to review the code changes for me before I try it and have to
restore my HD because of a stupid error? (Yes, I have DiskImage backups of all
my HDs).

Dave.

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGap(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[65536];               /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
//
//  Added:
  ULONG64 NewLcn;
//  EndAdd
//
  ULONG64 ClusterStart;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  int Index;
//
//  Added:
  int NewIndex;
//  EndAdd
//
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  do {
    /* Fetch a block of cluster data. If error then return NO. */
    BitmapParam.StartingLcn.QuadPart = Lcn;
//
//  Shouldn't this really be a calculated value based on the zone desired
//  ((MaximumLcn - MinimumLcn) / 8), adjusted for start, instead of
//  sizeof(BitmapData) to avoid moving 64KB each call for the small zone 0?
//
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,sizeof(BitmapData),&w,NULL);
    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }
    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    if (Lcn >= BitmapData.StartingLcn + BitmapData.BitmapSize) return(NO);
    if (MaximumLcn == 0) MaximumLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;
//
//  Replace:
//  IndexMax = sizeof(BitmapData.Buffer);
//  With:
    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)w;
//  End of replace.
//
    if (BitmapData.BitmapSize / 8 < IndexMax) IndexMax = (int)(BitmapData.BitmapSize / 8);
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);
//
//      Replace:
//      if (((Lcn >= Data->MftExcludes[0].Start) && (Lcn < Data->MftExcludes[0].End)) ||
//          ((Lcn >= Data->MftExcludes[1].Start) && (Lcn < Data->MftExcludes[1].End)) ||
//          ((Lcn >= Data->MftExcludes[2].Start) && (Lcn < Data->MftExcludes[2].End))) {
//         if (IgnoreMftExcludes == FALSE) InUse = 1;
//        }
//      With:
        /* If we are not even going to force the InUse bit,
           then don't even make the following 6 compares. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= Data->MftExcludes[0].Start) && (Lcn < Data->MftExcludes[0].End)) ||
              ((Lcn >= Data->MftExcludes[1].Start) && (Lcn < Data->MftExcludes[1].End)) ||
              ((Lcn >= Data->MftExcludes[2].Start) && (Lcn < Data->MftExcludes[2].End))) {
             InUse = 1;
            }
          }
        /* I would like to step around big open space with this code but there
           is a problem: as I step to a new BYTE, I may enter a new MftExcludes
           area with (IgnoreMftExcludes == FALSE) and need to set InUse to a 1.

           What would cure that problem and also speed up the algorithm is to do
           a one time setup (if (IgnoreMftExcludes == FALSE)) of setting all
           bits in the bit map that corresponded to ANY MftExcludes area (as if
           all of the clusters in the MftExcludes areas were all in use).

           Without doing that (setting the bits), what could be done is to set
           (NewLcn = Lcn) and (NewIndex = Index), detect the entry to EACH
           MftExcludes area and skip to the last BYTE of THAT MftExcludes area,
           setting (NewIndex += BYTES_skipped), setting (NewLcn = ((Lcn & -8) +
           (BYTES_skipped * 8)), then below, where Mask is shifted, detect that
           (Lcn <> NewLcn) and force (Lcn = NewLcn), (Mask = 1), and (Index =
           NewIndex) for searching the last Byte of the MftExcludes area.

           By skipping the MftExcludes area in one chunk rather than BYTE by
           BYTE, this solution would be even faster than the first solution AND
           you do net need to force the bits in the bit map which is time
           consuming when checking for filling the first and last BYTE of the
           MftExcludes areas and then filling all BYTES between those limits
           with 255 (especially if the code is never executed because you find a
           gap before running into the MftExcludes areas).

        if ((BitmapData.Buffer[Index] == 0) && (InUse == 0)){
           Mask = 1;
           Index++;
           Lcn += 8;
           continue;
           } */
//      End of replace.
//
        if ((PrevInUse == 0) && (InUse != 0)) {
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) &&
              (Lcn - ClusterStart >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) ||
              (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            }
          }
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;
///
//        New code:
          /* Step around large allocations. */
          while (((BitmapData.Buffer[Index-1] & Mask) == Mask) &&
                 (Index < IndexMax) &&
                 (BitmapData.Buffer[Index] == 255)) {
                Index++;
                Lcn += 8;
                }
//        End of new code
//
        } else {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) &&
             (Lcn < BitmapData.StartingLcn + BitmapData.BitmapSize) &&
             (Lcn < MaximumLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[jeroen]

Thank you very much for sharing your code, I appreciate it. I have looked at it and I like your idea of skipping whole bytes, instead of bit by bit. I've made a note and will implement something like that sometime in the future in MyDefrag. I will also look at using a larger buffer, although I'm not sure about that. The most frequent use of the subroutine is to find the first gap, so making the buffer bigger will potentially load more unused data.

[KeepingRealBusy]

Jeroen,

Here is my final version of FindGap with the implementation of all the things I was contemplating, sans the CPP comments.

Feel free to critically review the code. After 40 years in the trenches, I have been reviewed by experts - with sharp knives - and attitudes. I survived. If I am doing something wrong (misreading your code or the MS documentation) then please tell me. I am sort of looking at local optimization one routine at a time, trying to understand it and see where C optimization can be done. Then I go back and re-write in MASM for the ultimate optimization (C and C++ optimization is really, really, really quite bad).

Dave.

Code:

* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGap(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[65536];               /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[0].End;
  ULONG64 ClusterStart;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  do {
    /* Fetch a block of cluster data. If error then return NO. */
    BitmapParam.StartingLcn.QuadPart = Lcn;
    /* Don't read more than necessary. */
    if (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize = (sizeof(BitmapData) - 65536 + min(65536, BitmapDataSize));
         }
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);
    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }
    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    if (Lcn >= BitmapData.StartingLcn + BitmapData.BitmapSize) return(NO);
    if (MaximumLcn == 0) MaximumLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;
    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);
        NewLcn = Lcn;
        NewIndex = Index;
        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd & -8);
             NewIndex += (int)((NewLcn - (Lcn & -8)) >> 3);
            }
          }
        if ((PrevInUse == 0) && (InUse != 0)) {
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) &&
              (Lcn - ClusterStart >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) ||
              (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            }
          }
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }
      /* If Lcn not equal NewLcn, then skipping past MftExcludes */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = 1;
          continue; 
        }

      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;
          /* Step through large allocated areas. */
          if (BitmapData.Buffer[Index-1] & Mask) == 1)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas. */
          else
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) &&
             (Lcn < BitmapData.StartingLcn + BitmapData.BitmapSize) &&
             (Lcn < MaximumLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

RE C Optimization:

I found out (by creating the .cod file) that VS2008 calculates min(x,y) as follows:

Code:

var1 = min(exp2,exp3);
TempVar2 = Exp2;
TempVar3 = Exp3;
if (TempVar2 < TempVar3)
   Var1 = Exp2;
else
   Var1 = Exp3

It evaluates the complex expressions and saves their values in temporary variables, then compares the variables, then re-evaluates the expression with the lowest value again instead of using the value it saved in the temporary variable!

Stupid! Stupid! Stupid!

Multiple ret's are also a problem. It implements the ret multiple times, including the epilog code, and this is with full optimization. Even if you convert the code to set a RetVal to a return value and break out of the loop, then at exit return RetVal, depending on the code, it sometimes still creates two ret's with epilog code.

The only salvation is MASM! Code in C, then convert the C code to MASM constructs.

Dave

[KeepingRealBusy]

Jeroen,

Here is my latest version of FindGap. In line with your thinking about changing
the size of the buffer, I did a "#define BITMAP_BUFFER_SIZE 65536" in
JkDefragLib.h. and replaced the 65536 where ever found in JkDefragLib.cpp (only
found for the actual buffer size definition or limits in the code).

Note there are two places where BitmapData is defined in JkDefragLib.cpp with a
size of 65536 - be sure to change both and update JkDefragLib.h.

I created new variables for gap sizes and replaced many multiple identical
calculations to optimize the code.

I amplified the commentary.

I have examined this code critically, and even if a Buffer Block splits an
MftExcludes area, I think it should work and skip to the end of the MftExcludes
area when the next Buffer Block is obtained.

Dave.

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGap(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 LastBitmapLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[0].End;
  ULONG64 ClusterStart;
  ULONG64 GapSize;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 HighestSize;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  ULONG64 LargestSize;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  GapSize = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  HighestSize = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  LargestSize = 0;

  do {
    BitmapParam.StartingLcn.QuadPart = Lcn;

    /* Don't read more than necessary. */
    if  (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
         }

    /* Fetch a block of cluster data. If error then return NO. */
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);

    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }

    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);

    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);

    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);
        NewLcn = Lcn;
        NewIndex = Index;

        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd & -8);
             NewIndex += (int)((NewLcn - (Lcn & -8)) >> 3);
            }
          }

        if ((PrevInUse == 0) && (InUse != 0)) {
          GapSize = Lcn - ClusterStart;
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            HighestSize = GapSize;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            LargestSize = GapSize;
            }
          }

        /* Save the start of a gap. */
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }

      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. Note
         that NewLcn is set to the first Bit of the Byte that includes the end
         of the MftExcludes area so Mask is set to 1. */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = 1;
          continue; 
        }

      /* Step through the current indexed Byte, bit by bit. */
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;

          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & Mask) == 1)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & Mask) == 0) */
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else /* if (Mask < 128) */ {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < LastBitmapLcn) && (Lcn < MaximumLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

Here is a diff of the prior (almost) final version and the (new) final version
to show what I changed.

Dave.

Code:

------------------------------------------------------------------ 34
    BYTE Buffer[65536];               /* Most efficient if binary multiple. */
-------------------------------------------------------------- 34
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
------------------------------------------------------------------ 39
-------------------------------------------------------------- 39
  ULONG64 LastBitmapLcn;
------------------------------------------------------------------ 47
-------------------------------------------------------------- 48
  ULONG64 GapSize;
------------------------------------------------------------------ 49
-------------------------------------------------------------- 51
  ULONG64 HighestSize;
------------------------------------------------------------------ 51
-------------------------------------------------------------- 54
  ULONG64 LargestSize;
------------------------------------------------------------------ 67
-------------------------------------------------------------- 71
  GapSize = 0;
------------------------------------------------------------------ 70
-------------------------------------------------------------- 75
  HighestSize = 0;
------------------------------------------------------------------ 72
-------------------------------------------------------------- 78
  LargestSize = 0;
 
------------------------------------------------------------------ 73
    /* Fetch a block of cluster data. If error then return NO. */
-------------------------------------------------------------- 81
------------------------------------------------------------------ 75
-------------------------------------------------------------- 82
 
------------------------------------------------------------------ 76
    if (MaximumLcn == 0)
-------------------------------------------------------------- 84
    if  (MaximumLcn == 0)
------------------------------------------------------------------ 80
         BitmapDataSize = (sizeof(BitmapData) - 65536 + min(65536, BitmapDataSize));
-------------------------------------------------------------- 88
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
------------------------------------------------------------------ 82
-------------------------------------------------------------- 91
 
    /* Fetch a block of cluster data. If error then return NO. */
------------------------------------------------------------------ 84
-------------------------------------------------------------- 95
 
------------------------------------------------------------------ 89
-------------------------------------------------------------- 101
 
------------------------------------------------------------------ 97
    if (Lcn >= BitmapData.StartingLcn + BitmapData.BitmapSize) return(NO);
    if (MaximumLcn == 0) MaximumLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
-------------------------------------------------------------- 110
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);
 
    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;
------------------------------------------------------------------ 106
-------------------------------------------------------------- 121
 
------------------------------------------------------------------ 108
-------------------------------------------------------------- 124
 
    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
------------------------------------------------------------------ 109
-------------------------------------------------------------- 129
 
      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
------------------------------------------------------------------ 113
-------------------------------------------------------------- 136
 
------------------------------------------------------------------ 124
-------------------------------------------------------------- 148
 
------------------------------------------------------------------ 125
-------------------------------------------------------------- 150
          GapSize = Lcn - ClusterStart;
------------------------------------------------------------------ 126
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);
-------------------------------------------------------------- 152
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);
------------------------------------------------------------------ 130
          if ((ClusterStart >= MinimumLcn) &&
              (Lcn - ClusterStart >= MinimumSize)) {
-------------------------------------------------------------- 156
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
------------------------------------------------------------------ 139
-------------------------------------------------------------- 164
            HighestSize = GapSize;
------------------------------------------------------------------ 142
          if ((LargestBeginLcn == 0) ||
              (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
-------------------------------------------------------------- 168
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
------------------------------------------------------------------ 146
-------------------------------------------------------------- 171
            LargestSize = GapSize;
------------------------------------------------------------------ 148
-------------------------------------------------------------- 174
 
        /* Save the start of a gap. */
------------------------------------------------------------------ 151
      /* If Lcn not equal NewLcn, then skipping past MftExcludes */
-------------------------------------------------------------- 179
 
      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. Note
         that NewLcn is set to the first Bit of the Byte that includes the end
         of the MftExcludes area so Mask is set to 1. */
------------------------------------------------------------------ 159
-------------------------------------------------------------- 190
      /* Step through the current indexed Byte, bit by bit. */
------------------------------------------------------------------ 162
          /* Step through large allocated areas. */
          if (BitmapData.Buffer[Index-1] & Mask) == 1)
-------------------------------------------------------------- 194
 
          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & Mask) == 1)
------------------------------------------------------------------ 169
          /* Step through large un-allocated areas. */
          else
-------------------------------------------------------------- 203
          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & Mask) == 0) */
------------------------------------------------------------------ 176
        } else {
-------------------------------------------------------------- 211
        } else /* if (Mask < 128) */ {
------------------------------------------------------------------ 182
    } while ((ErrorCode == ERROR_MORE_DATA) &&
             (Lcn < BitmapData.StartingLcn + BitmapData.BitmapSize) &&
             (Lcn < MaximumLcn));
-------------------------------------------------------------- 217
    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < LastBitmapLcn) && (Lcn < MaximumLcn));

[KeepingRealBusy]

Jeroen,

Found some more changes in the end game (after "do...While" fails).

Dave

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGap(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 LastBitmapLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[0].End;
  ULONG64 ClusterStart;
  ULONG64 GapSize;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 HighestSize;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  ULONG64 LargestSize;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  GapSize = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  HighestSize = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  LargestSize = 0;

  do {
    BitmapParam.StartingLcn.QuadPart = Lcn;

    /* Don't read more than necessary. */
    if  (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
         }

    /* Fetch a block of cluster data. If error then return NO. */
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);

    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }

    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);

    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);

    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);
        NewLcn = Lcn;
        NewIndex = Index;

        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd & -8);
             NewIndex += (int)((NewLcn - (Lcn & -8)) >> 3);
            }
          }

        if ((PrevInUse == 0) && (InUse != 0)) {
          GapSize = Lcn - ClusterStart;
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            HighestSize = GapSize;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            LargestSize = GapSize;
            }
          }

        /* Save the start of a gap. */
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }

      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. Note
         that NewLcn is set to the first Bit of the Byte that includes the end
         of the MftExcludes area so Mask is set to 1. */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = 1;
          continue; 
        }

      /* Step through the current indexed Byte, bit by bit. */
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;

          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & Mask) == 1)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & Mask) == 0) */
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else /* if (Mask < 128) */ {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < MaximumLcn) && (Lcn < LastBitmapLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    GapSize = Lcn - ClusterStart;
    if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

Here is the diff of these last changes.

Dave.

Code:

------------------------------------------------------------------ 217
    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < LastBitmapLcn) && (Lcn < MaximumLcn));
-------------------------------------------------------------- 217
    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < MaximumLcn) && (Lcn < LastBitmapLcn));
------------------------------------------------------------------ 224
    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
-------------------------------------------------------------- 224
    GapSize = Lcn - ClusterStart;
    if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
------------------------------------------------------------------ 236
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
-------------------------------------------------------------- 236
    if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {

[jeroen]

Thanks again for sharing your code, I appreciate it. See http://www.mydefrag.com/ for the succesor to JkDefrag, called MyDefrag. It's still in beta but nearing the first release now.

[KeepingRealBusy]

Jeroen,

I tested this by naming the function FindGapNew and kept the original FindGap.

In the function Fixup I called FindGapNew just before calling FindGap, but saved
the gap values in new variables NewBegin and NewEnd, then called FindGap
normally. After calling FindGap, I compared the returned gap values and aborted
if they did not match (debugged in Visual Studio Release).

I was testing a drive that was not busy so both of the calls should have got the
same bitmaps and returned the same results. They didn't!

I found the error (the initializarion of NewLcn and NewIndex) and had to move
the initializations in front of "if (Lcn >= MinimumLcn) {" instead of following
"InUse = (BitmapData.Buffer[Index] & Mask);".

With that fix, the defrag of the drive completed correctly and the dual calls
always matched their returned values.

I will try to do 1000 calls to each of the FindGap functions for each file (in
Fixup) and accumulate the times for an entire defrag and see what kind of speed
improvement it makes, however, since the drive is already defragged, there may
not be much to move around. This may take a while.

The following is the corrected, tested FindGap.

Dave.

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGap(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 LastBitmapLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[0].End;
  ULONG64 ClusterStart;
  ULONG64 GapSize;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 HighestSize;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  ULONG64 LargestSize;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  GapSize = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  HighestSize = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  LargestSize = 0;

  do {
    BitmapParam.StartingLcn.QuadPart = Lcn;

    /* Don't read more than necessary. */
    if  (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
         }

    /* Fetch a block of cluster data. If error then return NO. */
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);

    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }

    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);

    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);

    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
      NewLcn = Lcn;
      NewIndex = Index;
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);

        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd & -8);
             NewIndex += (int)((NewLcn - (Lcn & -8)) >> 3);
            }
          }

        if ((PrevInUse == 0) && (InUse != 0)) {
          GapSize = Lcn - ClusterStart;
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            HighestSize = GapSize;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            LargestSize = GapSize;
            }
          }

        /* Save the start of a gap. */
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }

      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. Note
         that NewLcn is set to the first Bit of the Byte that includes the end
         of the MftExcludes area so Mask is set to 1. */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = 1;
          continue; 
        }

      /* Step through the current indexed Byte, bit by bit. */
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;

          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & Mask) == 1)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & Mask) == 0) */
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else /* if (Mask < 128) */ {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < LastBitmapLcn) && (Lcn < MaximumLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

I found another bug by inspection. The bitmap is a little-endian bit array where
the the MostSignificantBit in a byte is continued to the LeastSignificantBit in
the next byte in memory, thus to check for a continuation of an allocated area
you need to mask the prior byte with 128 and check for a 128 to detect a
continuation with a following byte of 255. Likewise, mask the previous byte with
128 and check for 0 to detect a continuation with a following byte of 0.

Here is the corrected version.

Dave.

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGapNew(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 LastBitmapLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[0].End;
  ULONG64 ClusterStart;
  ULONG64 GapSize;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 HighestSize;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  ULONG64 LargestSize;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  GapSize = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  HighestSize = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  LargestSize = 0;

  do {
    BitmapParam.StartingLcn.QuadPart = Lcn;

    /* Don't read more than necessary. */
    if  (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
         }

    /* Fetch a block of cluster data. If error then return NO. */
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);

    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }

    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);

    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

    /* Don't search bits in the buffer which are not set by DeviceIoControl. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);

    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
      NewLcn = Lcn;
      NewIndex = Index;
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);

        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd & -8);
             NewIndex += (int)((NewLcn - (Lcn & -8)) >> 3);
            }
          }

        if ((PrevInUse == 0) && (InUse != 0)) {
          GapSize = Lcn - ClusterStart;
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            HighestSize = GapSize;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            LargestSize = GapSize;
            }
          }

        /* Save the start of a gap. */
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
        PrevInUse = InUse;
        }

      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. Note
         that NewLcn is set to the first Bit of the Byte that includes the end
         of the MftExcludes area so Mask is set to 1. */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = 1;
          continue; 
        }

      /* Step through the current indexed Byte, bit by bit. */
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;

          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & 128) == 128)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & 128) == 0) */
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else /* if (Mask < 128) */ {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < MaximumLcn) && (Lcn < LastBitmapLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    GapSize = Lcn - ClusterStart;
    if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

I think the timing results speak for themselves. Use the code if you find it
useful.

Dave.

Code:

//  I made the following debug changes to FixUp:

//
//  New Debug variables.
//
ULONG64 NewBegin;
ULONG64 NewEnd;
ULONG64 SaveBegin;
ULONG64 SaveEnd;
DWORD NewCount = 0;
DWORD StartTime;
DWORD EndTime;
DWORD LoopCount;
DWORD NewTime = 0;
DWORD OldTime = 0;
//
//  End of variables.
//
.
.
.
//
//  New code to call FindGapNew and time 100 loops.
//
NewCount++;
StartTime = GetTickCount();
for(LoopCount = 0; LoopCount < 100; LoopCount++)
   FindGapNew(Data,Data->Zones[FileZone],0,Item->Clusters,YES,NO,&NewBegin,&NewEnd,FALSE);
EndTime = GetTickCount();
NewTime += (EndTime - StartTime);
//
//  New code to time 100 loops of FindGap as well.
//
StartTime = GetTickCount();
for(LoopCount = 0; LoopCount < 100; LoopCount++)
//
//  This is the normal call to FindGap
//
      Result = FindGap(Data,Data->Zones[FileZone],0,Item->Clusters,YES,NO,&GapBegin[FileZone],
        &GapEnd[FileZone],FALSE);
//
//  End of normal call.
//
EndTime = GetTickCount();
OldTime += (EndTime - StartTime);
//
//  Normal code.
//
      if (Result == NO) {
        /* Show debug message: "Cannot move item away because no gap is big enough: %I64d[%lu]" */
        Data->ShowDebug(2,Item,Data->DebugMsg[25],GetItemLcn(Item),Item->Clusters);
        GapEnd[FileZone] = GapBegin[FileZone];         /* Force re-scan of gap. */
        Data->PhaseDone = Data->PhaseDone + Item->Clusters;
        continue;
        }
//
//  End of normal code, now check matching gaps.
//
if ((NewBegin != GapBegin[FileZone]) && (NewEnd != GapEnd[FileZone])){
  SaveBegin = GapBegin[FileZone];
  SaveEnd = GapEnd[FileZone];
  __asm
  {
  mov eax,NewCount
  xor ebx,ebx
  mov ebx,[ebx]
  }
//
//  End of checking code.
//
.
.
.
//
//  At the end of FixUp
//
  __asm
  {
  mov eax,NewCount
  mov ebx,NewTime
  mov ecx,OldTime
  xor edx,edx
  mov edx,[edx]
  }

//
//  The registers at the exception at the end.
//
//        NewCount        NewTime        OldTime
//  EAX = 00000006 EBX = 0000006E ECX = 00018567
//  all passes   6            110          99687   Msec for 100 loops
//  all passes   6           1100         996870   Msec for 1000 loops
//  Each pass    1            183         166145   Msec for 1 loop 
//                                        165962   excess Msec each pass with old (1000 loops).
//                                       165.962   excess Msec each pass with old (1 loop).
//

[jeroen]

Thanks again for your contribution, I appreciate it. Your code is 1000 times faster? That is very impressive and I will definitely implement your idea in the future, as I said before. The code that I am using in MyDefrag is different from JkDefrag, for example I am not using a Mask anymore, so it's not as easy as just copying your changes. It's a complex little subroutine, as you have seen, and it will take me some work.

[KeepingRealBusy]

Jeroen,

The 1000 times as fast finding was a bit premature. It resulted from the fact
that the HD was almost empty and had been defragged once already so it was
mainly a huge gap.

I was not satisfied with the test. Not enough executions because the drive was
relative empty and unused and already defragged. I copied a huge directory into
it, renamed FindGap to FindGapOld, created a FindGap that called, timed (10
iterations), and checked the returns for both FindGapNew and then FindGapOld.
This forced all calls to FindGap to be counted and timed and not just the calls
in Fixup. I removed the __asm trap from Fixup and added a debug output to the
log with both of the times and count of executions. I left the __asm trap in the
new FindGap to catch any mismatch, but all seems clean now.

Turns out that there was several errors. The bitmap size returned is not just
for the partial buffer returned, but to the end of the selection. I added a
restriction to limit IndexMax to BITMAP_BUFFER_SIZE. The MftExcludes overlaped
causing a problem. I corrected this by forcing the end of the first to the end
of the second, then overlayed the second with the third, then set the start of
the third to the end of the bitmap. I also checked for an overlap between the
second and third. Another error was forcing the Lcn after such a skip to the
first bit in the byte containing the end of the area, expecting to walk through
the possible remaining bits one by one. Would you believe a huge loop because
the first bit in the last byte was inside the excludes area (wasn't a mod 8 end
point) so I forced it again, and again, and again... everytime through the While
loop. Fixed this by setting the NewLcn to the end of the MftExcludes area and
calculated the Mask for that bit.

It all seems to work now with 1029 FindGap calls. The following is the log from
the execution along with some calculations for single execution times.

I will also post the latest tested versions of FindGapNew, FindGapOld,
FindGap, and Fixup (my ShowDebug statements have been C++ commented out
- had to see what was happening to fix the above errors). I tried to include it
here but it exceeded the 20000 character count limit.

Dave.

Code:

17:28:40 JkDefrag v3.36
17:28:40 Date: 2009/06/25
17:28:40 Windows version: v5.1 build 2600 Service Pack 2
17:28:40 Commandline argument '-l' accepted, logfile = JkDefrag.log
17:28:40 Commandline argument '-d' accepted, debug = 1
17:28:40 NtfsDisableLastAccessUpdate is inactive, using LastAccessTime for SpaceHogs.
17:28:40 Processing 'e:'
17:28:40 Opening volume '\\?\Volume{dfea1be2-00ea-11dc-8e55-806d6172696f}' at mountpoint 'e:'
17:28:40 Input mask: E:\*
17:28:45 Phase 1: Analyze
17:28:45 This is an NTFS disk.
17:28:51 Phase 2: Defragment
17:29:05 Phase 3: Fixup
17:30:05 NewCount, NewTime, and OldTime 76,    421,  22097 Msec for 10 iterations for 76 executions
                                         1,   5.54, 290.75 Msec for 10 iterations for 1 execution
                                         1,   .554, 29.075 Msec for 1 iterations for 1 execution
17:30:08 Zone 1: Fast Optimize
17:30:18 Zone 2: Fast Optimize
17:31:32 Zone 3: Fast Optimize
17:32:40 Phase 3: Fixup
         The following times and counts are an accumulation with the Defragment times and counts.
17:32:40 NewCount, NewTime, and OldTime 1029,  1093,   41176 Msec for 10 iterations for 1029 executions
                                           1, 1.062, 40.0156 Msec for 10 iterations for 1 execution
                                           1, .1062, 4.00156 Msec for 1 iterations for 1 execution
                          (1029 * (4.00156 - .1062))    4008 Msec excess for old vs new
                                                           4 Seconds excess - no big deal, but 40 times as fast.
17:32:43 Finished.
17:32:43 - Total disk space: 250089603072 bytes (232.9141 gigabytes), 61057032 clusters
17:32:43 - Bytes per cluster: 4096 bytes
17:32:43 - Number of files: 18519
17:32:43 - Number of directories: 1493
17:32:43 - Total size of analyzed items: 4266160128 bytes (3.9732 gigabytes), 1041543 clusters
17:32:43 - Number of fragmented items: 0 (0.0000% of all items)
17:32:43 - Total size of fragmented items: 0 bytes, 0 clusters, 0.0000% of all items, 0.0000% of disk
17:32:43 - Free disk space: 214569754624 bytes, 52385194 clusters, 85.7972% of disk
17:32:43 - Number of gaps: 121
17:32:43 - Number of small gaps: 112 (92.5620% of all gaps)
17:32:43 - Size of small gaps: 663552 bytes, 162 clusters, 0.0003% of free disk space
17:32:43 - Number of big gaps: 9 (7.4380% of all gaps)
17:32:43 - Size of big gaps: 214569091072 bytes, 52385032 clusters, 99.9997% of free disk space
17:32:43 - Average gap size: 432935.4876 clusters
17:32:43 - Biggest gap: 125024288768 bytes, 30523508 clusters, 58.2674% of free disk space
17:32:43 - Average end-begin distance: 2693400 clusters, 4.4113% of volume size
17:32:43 These items could not be moved:
17:32:43   Fragments       Bytes  Clusters Name
17:32:43           1    67108864     16384 e:\$LogFile
17:32:43           1        2504         1 e:\$MFT::$BITMAP
17:32:43           1    20512768      5008 e:\$MFT
17:32:43           1        4096         1 e:\$MFTMirr
17:32:43           1        4172         2 e:\.::$SECURITY_DESCRIPTOR
17:32:43           1     7632136      1864 e:\$Bitmap
17:32:43   --------- ----------- --------- -----
17:32:43           6    95264540     23260 Total
17:32:43 The 25 largest items on disk:
17:32:43   Fragments       Bytes  Clusters Name
17:32:43           1   536870969    131073 e:\DAVE06DATA\Strtest.sav\unused\gtbtg\random1.dat.sav
17:32:43           1   227278848     55488 e:\masm32\tools\ollydbg\S0000000.dat
17:32:43           1   175169466     42766 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1in1.txt
17:32:43           1   175169466     42766 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1ot1.txt
17:32:43           1    85177060     20796 e:\DAVE06DATA\Strtest.sav\qsortid\qsortidcom.lst
17:32:43           1    79269772     19353 e:\DAVE06DATA\Strtest.sav\qsort\qsortcom.lst
17:32:43           1    67108864     16384 e:\$LogFile
17:32:43           1    62341384     15221 e:\DAVE06DATA\Strtest.sav\qsortid\qsortidtrc.lst
17:32:43           1    57238224     13975 e:\DAVE06DATA\Strtest.sav\qsort\qsorttrc.lst
17:32:43           1    39737970      9702 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1in2.txt
17:32:43           1    39737970      9702 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1in3.txt
17:32:43           1    39737970      9702 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1ot2.txt
17:32:43           1    39737970      9702 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1ot3.txt
17:32:43           1    28509250      6961 e:\DAVE06DATA\Strtest.sav\qsortid\qsortidtst.lst
17:32:43           1    27786402      6784 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1in4.txt
17:32:43           1    27786402      6784 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1in5.txt
17:32:43           1    27786402      6784 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1ot4.txt
17:32:43           1    27786402      6784 e:\DAVE06DATA\Strtest.sav\Skiphuge\file\bin\Sort1ot5.txt
17:32:43           1    26226482      6403 e:\DAVE06DATA\Strtest.sav\qsort\qsorttst.lst
17:32:43           1    24102349      5885 e:\DAVE06DATA\Tex\SAV-9-01-1000-MITRE.exe
17:32:43           1    24102349      5885 e:\System Volume Information\_restore{106CF321-99A3-4E3A-9103-1BD027606A99}\RP282\A0084141.exe
17:32:43           1    20512768      5008 e:\$MFT
17:32:43           1    20322482      4962 e:\DAVE06DATA\Msvc152\HELP\VCBKS15.HLP
17:32:43           1    20322482      4962 e:\System Volume Information\_restore{106CF321-99A3-4E3A-9103-1BD027606A99}\RP282\A0085480.HLP
17:32:43           1    16847734      4114 e:\DAVE06DATA\Strtest.sav\pfd\fullsave.txt

[KeepingRealBusy]

Jeroen,

Here is the latest code for the FindGapNew.

Dave.

Code:

DWORD NewCount = 0;
DWORD NewTime = 0;
DWORD OldTime = 0;

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGapNew(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[BITMAP_BUFFER_SIZE];        /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  int     BitmapDataSize;
  ULONG64 NewLcn;
  ULONG64 LastBitmapLcn;
  ULONG64 ExcStart0 = Data->MftExcludes[0].Start;
  ULONG64 ExcStart1 = Data->MftExcludes[1].Start;
  ULONG64 ExcStart2 = Data->MftExcludes[2].Start;
  ULONG64 ExcEnd;
  ULONG64 ExcEnd0 = Data->MftExcludes[0].End;
  ULONG64 ExcEnd1 = Data->MftExcludes[1].End;
  ULONG64 ExcEnd2 = Data->MftExcludes[2].End;
  ULONG64 ClusterStart;
  ULONG64 GapSize;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 HighestSize;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  ULONG64 LargestSize;
  int Index;
  int NewIndex;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;

  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  GapSize = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  HighestSize = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;
  LargestSize = 0;

//  /* "Looking for gap from %I64d, to %I64d for size %I64d" */
//  Data->ShowDebug(1,NULL,L"Looking for gap from %I64d, to %I64d for size %I64d",MinimumLcn,MaximumLcn,MinimumSize);

//  /* "Exclude 0 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 0 from %I64d, to %I64d",ExcStart0,ExcEnd0);

//  /* "Exclude 1 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 1 from %I64d, to %I64d",ExcStart1,ExcEnd1);

//  /* "Exclude 2 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 2 from %I64d, to %I64d",ExcStart2,ExcEnd2);

  do {
    BitmapParam.StartingLcn.QuadPart = Lcn;

    /* Don't read more than necessary. */
    if  (MaximumLcn == 0)
         BitmapDataSize = sizeof(BitmapData);
    else {
         BitmapDataSize = ((((MaximumLcn + 7) & -8) - (MinimumLcn & -8)) >> 3);
         BitmapDataSize =
           (sizeof(BitmapData) - BITMAP_BUFFER_SIZE + min(BITMAP_BUFFER_SIZE, BitmapDataSize));
         }

    /* Fetch a block of cluster data. If error then return NO. */
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,BitmapDataSize,&w,NULL);

    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }

    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    LastBitmapLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;
    if (Lcn >= LastBitmapLcn) return(NO);

    if (MaximumLcn == 0) MaximumLcn = LastBitmapLcn;

    /* Don't tell anybody, but the MftExcludes areas can overlap. If ExcEnd0
       overlaps ExcStart1, then use ExcEnd1 instead of ExcEnd0 and replace
       ExcStart1 and ExcEnd1 with ExcStart2 and ExcEnd2, and set  ExcStart2 to
       LastBitmapLcn. Do the same for  ExcEnd1 and ExcStart3*/
    if (ExcEnd0 >= ExcStart1) {
      ExcEnd0 = ExcEnd1;
      ExcStart1 = ExcStart2;
      ExcEnd1 = ExcEnd2;
      ExcStart2 = LastBitmapLcn;
      }
    else if (ExcEnd1 >= ExcStart2) {
      ExcEnd1 = ExcEnd2;
      ExcStart2 = LastBitmapLcn;
      }

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

//    /* "Bitmap from %I64d, to %I64d" */
//    Data->ShowDebug(1,NULL,L"Bitmap from %I64d, to %I64d",Lcn,LastBitmapLcn);

    /* Don't search bits in the buffer which are not set by DeviceIoControl,
       but do not exceed BITMAP_BUFFER_SIZE. */
    IndexMax = (int)(BitmapData.BitmapSize >> 3);
    IndexMax = (int)min(IndexMax, BITMAP_BUFFER_SIZE);

    /* PrevInUse starts as 1. Search for the first unused cluster, this is the
       start of a gap. Then Search for the first used cluster, this is the end
       of the gap. This search may span blocks of buffered data. */
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

      /* DeviceIoControl can round down the requested StartingLcn so an early
         gap may be found, ignore it. */
      NewLcn = Lcn;
      NewIndex = Index;
//      /* "Lcn and NewLcn %I64d, %I64d" */
//      Data->ShowDebug(1,NULL,L"Lcn and NewLcn %I64d, %I64d",Lcn,NewLcn);
      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);

        /* If we are not going to force the InUse bit,
           then don't even make the 6 compares that follow. */
        if (IgnoreMftExcludes == FALSE) {
          if (((Lcn >= ExcStart0) && (Lcn < (ExcEnd = ExcEnd0))) ||
              ((Lcn >= ExcStart1) && (Lcn < (ExcEnd = ExcEnd1))) ||
              ((Lcn >= ExcStart2) && (Lcn < (ExcEnd = ExcEnd2)))) {
             InUse = 1;
             NewLcn = (ExcEnd);
             NewIndex = (int)((NewLcn - BitmapData.StartingLcn) >> 3);
//             /* "Lcn and NewLcn %I64d, to %I64d" */
//             Data->ShowDebug(1,NULL,L"Lcn and NewLcn %I64d, %I64d",Lcn,NewLcn);
            }
          }


        if ((PrevInUse == 0) && (InUse != 0)) {
          GapSize = Lcn - ClusterStart;
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,GapSize);
//          Data->ShowDebug(1,NULL,Data->DebugMsg[13],ClusterStart,GapSize);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            HighestSize = GapSize;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            LargestSize = GapSize;
            }
          }

        /* Save the start of a gap. */
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
//        if ((PrevInUse != 0) && (InUse == 0)) {
//           ClusterStart = Lcn;
//          /* Show debug message: "ClusterStart = %I64d" */
//          Data->ShowDebug(1,NULL,L"ClusterStart = %I64d",Lcn);
//          }
        PrevInUse = InUse;
        }

      /* If Lcn not equal NewLcn, then we are skipping past MftExcludes. */
      if (Lcn != NewLcn) {
          Lcn = NewLcn;
          Index = NewIndex;
          Mask = (1 << (NewLcn & 7));
          continue; 
        }

      /* Step through the current indexed Byte, bit by bit. */
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;

          /* Step through large allocated areas, Byte by Byte. Note: Lcn points
             to the last Bit of a Byte - incremented below. */
          if ((BitmapData.Buffer[Index-1] & 128) == 128)
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 255)) {
                   Index++;
                   Lcn += 8;
              }

          /* Step through large un-allocated areas, Byte by Byte. Note: Lcn
             points to the last Bit of a Byte - incremented below. */
          else /* if (BitmapData.Buffer[Index-1] & 128) == 0) */
            while ((Index < IndexMax) && (BitmapData.Buffer[Index] == 0)) {
                   Index++;
                   Lcn += 8;
              }

        } else /* if (Mask < 128) */ {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

//    /* "Index and IndexMax %I64d, %I64d" */
//    Data->ShowDebug(1,NULL,L"Index and IndexMax %d, %d",Index,IndexMax);
//    /* "Lcn and MaximumLcn %I64d, %I64d" */
//    Data->ShowDebug(1,NULL,L"Lcn and MaximumLcn %I64d, %I64d",Lcn,LastBitmapLcn);

    } while ((ErrorCode == ERROR_MORE_DATA) && (Lcn < MaximumLcn) && (Lcn < LastBitmapLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);
//    Data->ShowDebug(1,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    GapSize = Lcn - ClusterStart;
    if ((ClusterStart >= MinimumLcn) && (GapSize >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) || (LargestSize < GapSize)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }