path: root/mps/code/bt.c

/* bt.c: BIT TABLES
 *
 * $Id$
 * Copyright (c) 2001-2020 Ravenbrook Limited.  See end of file for license.
 *
 * READERSHIP
 *
 * .readership: Any MPS developer
 *
 * DESIGN
 *
 * .design: see <design/bt>
 *
 * .aver.critical: The function BTIsResRange (and anything it calls)
 * is on the critical path <design/critical-path> because it is
 * called by NailboardIsResRange, which is called for every object in
 * a nailboarded segment when the segment is scanned or reclaimed; see
 * <design/nailboard#.impl.isresrange>.
 */

#include "bt.h"
#include "config.h"
#include "check.h"
#include "mpm.h"

SRCID(bt, "$Id$");


/* BTIndexAlignUp, BTIndexAlignDown -- Align bit-table indices
 *
 * Align bit-table indices up and down to word boundaries
 */

#define BTIndexAlignUp(index) (IndexAlignUp((index), MPS_WORD_WIDTH))
#define BTIndexAlignDown(index) (IndexAlignDown((index), MPS_WORD_WIDTH))


/* BTMask -- generate sub-word masks
 *
 * Create a mask with only specified bits set
 */

/* Return a word mask of bits set only from base and above */
#define BTMaskLow(base) (~(Word)0 << (base))

/* Return a word mask of bits set only below limit */
#define BTMaskHigh(limit) (~(Word)0 >> (MPS_WORD_WIDTH - (limit)))

/* Return a word mask of bits set only in requested range */
#define BTMask(base,limit) (BTMaskHigh((limit)) & BTMaskLow((base)))


/* BTWordIndex, BTBitIndex -- Decode BT indexes
 *
 * Return word and bit indexes from index
 */

#define BTWordIndex(index) ((index) >> MPS_WORD_SHIFT)
#define BTBitIndex(index) ((index) & (MPS_WORD_WIDTH - 1))


/* BTIsSmallRange -- test range size
 *
 * Predicate to determine whether a range is sufficiently small
 * that it's not worth trying to separate words and odd bits.
 * The choice of what counts as "sufficiently small" is made
 * for efficiency reasons. Empirical evidence indicates that
 * a good choice is ranges of size 6 or less.
 */

#define BTIsSmallRange(base,limit) ((base) + 6 >= (limit))


/* ACT_ON_RANGE -- macro to act on a base-limit range
 *
 * Three actions should be provided:
 *   - single_action(btIndex) - operates on a single bit
 *   - bits_action(wordIndex, base, limit) -- operates on part-words
 *   - word_action(wordIndex) -- Operates on full words in range
 * WORD_ACTIONs should not use break or continue.
 *
 * If the range is small enough it will be processed a single
 * bit at a time. Larger ranges are processed as words where
 * possible, and part-words for boundary bits.
 */

#define ACT_ON_RANGE(base,limit,single_action, \
                     bits_action,word_action) \
  BEGIN \
    if (BTIsSmallRange((base), (limit))) { \
      /* Small ranges are processed most efficiently bit-by-bit */ \
      Index actBit; \
      for (actBit = (base); actBit < (limit); ++actBit) { \
        single_action(actBit); \
      } \
    } else { \
      Index actInnerBase = BTIndexAlignUp((base)); \
      if (actInnerBase > (limit)) { /* no inner range */ \
        /* Must have base < limit otherwise caught by small range case */ \
        /* And see .aver.critical. */ \
        AVER_CRITICAL((base) < (limit)); \
        bits_action(BTWordIndex((base)), \
                    BTBitIndex((base)), \
                    BTBitIndex((limit))); \
      } else { \
        Index actInnerLimit = BTIndexAlignDown((limit)); \
        Index actWordIndex, actWordBase, actWordLimit; \
\
        actWordBase = BTWordIndex(actInnerBase); \
        actWordLimit = BTWordIndex(actInnerLimit); \
\
        if ((base) < actInnerBase) { \
          bits_action(actWordBase-1, \
                      BTBitIndex((base)), \
                      MPS_WORD_WIDTH); \
        } \
\
        for (actWordIndex = actWordBase; actWordIndex < actWordLimit; \
            ++actWordIndex) { \
          word_action(actWordIndex); \
        } \
\
        if ((limit) > actInnerLimit) { \
          bits_action(actWordLimit, 0, BTBitIndex((limit))); \
        } \
      } \
    } \
  END


/* ACT_ON_RANGE_HIGH -- macro to act on a base-limit range
 *
 * in reverse order. Usage as for ACT_ON_RANGE
 */

#define ACT_ON_RANGE_HIGH(base,limit,single_action, \
                          bits_action,word_action) \
  BEGIN \
    if (BTIsSmallRange((base), (limit))) { \
      /* Small ranges are processed most efficiently bit-by-bit */ \
      Index actBit; \
      for (actBit = (limit); actBit > (base); --actBit) { \
        single_action(actBit - 1); \
      } \
    } else { \
      Index actInnerBase = BTIndexAlignUp((base)); \
      if (actInnerBase > (limit)) { /* no inner range */ \
        AVER((base) < (limit)); /* caught by small range case */ \
        bits_action(BTWordIndex((base)), \
                    BTBitIndex((base)), \
                    BTBitIndex((limit))); \
      } else { \
        Index actInnerLimit = BTIndexAlignDown((limit)); \
        Index actWordIndex, actWordBase, actWordLimit; \
\
        actWordBase = BTWordIndex(actInnerBase); \
        actWordLimit = BTWordIndex(actInnerLimit); \
\
        if ((limit) > actInnerLimit) { \
          bits_action(actWordLimit, 0, BTBitIndex((limit))); \
        } \
\
        for (actWordIndex = actWordLimit; actWordIndex > actWordBase; \
            --actWordIndex) { \
          word_action(actWordIndex-1); \
        } \
\
        if ((base) < actInnerBase) { \
          bits_action(actWordBase-1, \
                      BTBitIndex((base)), \
                      MPS_WORD_WIDTH); \
        } \
      } \
    } \
  END



/* BTCreate -- allocate a BT from the control pool
 *
 * <design/bt#.if.create>
 */

Res BTCreate(BT *btReturn, Arena arena, Count length)
{
  Res res;
  BT bt;
  void *p;

  AVER(btReturn != NULL);
  AVERT(Arena, arena);
  AVER(length > 0);

  res = ControlAlloc(&p, arena, BTSize(length));
  if (res != ResOK)
    return res;
  bt = (BT)p;

  *btReturn = bt;
  return ResOK;
}


/* BTDestroy -- free a BT to the control pool.
 *
 * <design/bt#.if.destroy>
 */

void BTDestroy(BT bt, Arena arena, Count length)
{
  AVER(bt != NULL);
  AVERT(Arena, arena);
  AVER(length > 0);

  ControlFree(arena, bt, BTSize(length));
}


/* BTCheck -- check the validity of a bit table
 *
 * There's not much that can be checked at present.  This is
 * discussed in review.impl.c.bt.4.
 */

Bool BTCheck(BT bt)
{
  AVER(bt != NULL);
  AVER(AddrIsAligned((Addr)bt, sizeof(Word)));
  return TRUE;
}


/* BTSize -- return the size of a BT
 *
 * <design/bt#.fun.size>
 */

Size (BTSize)(Count n)
{
  /* check that the expression used in rounding up doesn't overflow */
  AVER(n+MPS_WORD_WIDTH-1 > n);

  return BTSize(n);
}


/* BTGet -- get a bit from a BT
 *
 * <design/bt#.fun.get>
 */

Bool (BTGet)(BT t, Index i)
{
  AVERT(BT, t);
  /* Can't check i */

  /* see macro in <code/mpm.h> */
  return BTGet(t, i);
}


/* BTSet -- set a bit in a BT
 *
 * <design/bt#.fun.set>
 */

void (BTSet)(BT t, Index i)
{
  AVERT(BT, t);
  /* Can't check i */

  /* see macro in <code/mpm.h> */
  BTSet(t, i);
}


/* BTRes -- reset a bit in a BT
 *
 * <design/bt#.fun.res>
 */

void (BTRes)(BT t, Index i)
{
  AVERT(BT, t);
  /* Can't check i */

  /* see macro in <code/mpm.h> */
  BTRes(t, i);
}


/* BTSetRange -- set a range of bits in a BT
 *
 * <design/bt#.fun.set-range>
 */

void BTSetRange(BT t, Index base, Index limit)
{
  AVERT(BT, t);
  AVER(base < limit);

#define SINGLE_SET_RANGE(i) \
  BTSet(t, (i))
#define BITS_SET_RANGE(i,base,limit) \
  t[(i)] |= BTMask((base),(limit))
#define WORD_SET_RANGE(i) \
  t[(i)] = ~(Word)(0)

  ACT_ON_RANGE(base, limit, SINGLE_SET_RANGE,
               BITS_SET_RANGE, WORD_SET_RANGE);
}


/* BTIsResRange -- test whether a range of bits is all reset
 *
 * <design/bt#.fun.is-reset-range>.
 */

Bool BTIsResRange(BT bt, Index base, Index limit)
{
  AVERT_CRITICAL(BT, bt);   /* See .aver.critical */
  AVER_CRITICAL(base < limit);
  /* Can't check range of base or limit */

#define SINGLE_IS_RES_RANGE(i) \
  if (BTGet(bt, (i))) return FALSE
#define BITS_IS_RES_RANGE(i,base,limit) \
  if ((bt[(i)] & BTMask((base),(limit))) != (Word)0) return FALSE
#define WORD_IS_RES_RANGE(i) \
  if (bt[(i)] != (Word)0) return FALSE

  ACT_ON_RANGE(base, limit, SINGLE_IS_RES_RANGE,
               BITS_IS_RES_RANGE, WORD_IS_RES_RANGE);
  return TRUE;
}


/* BTIsSetRange -- test whether a range of bits is all set
 *
 * <design/bt#.fun.is-set-range>.
 */

Bool BTIsSetRange(BT bt, Index base, Index limit)
{
  AVERT(BT, bt);
  AVER(base < limit);
  /* Can't check range of base or limit */

#define SINGLE_IS_SET_RANGE(i) \
  if (!BTGet(bt, (i))) return FALSE
#define BITS_IS_SET_RANGE(i,base,limit) \
  BEGIN \
    Word bactMask = BTMask((base),(limit)); \
    if ((bt[(i)] & bactMask) != bactMask) \
      return FALSE; \
  END
#define WORD_IS_SET_RANGE(i) \
  if (bt[(i)] != ~(Word)0) return FALSE

  ACT_ON_RANGE(base, limit, SINGLE_IS_SET_RANGE,
               BITS_IS_SET_RANGE, WORD_IS_SET_RANGE);
  return TRUE;
}


/* BTResRange -- reset a range of bits in a BT
 *
 * <design/bt#.fun.res-range>
 */

void BTResRange(BT t, Index base, Index limit)
{
  AVERT(BT, t);
  AVER(base < limit);

#define SINGLE_RES_RANGE(i) \
  BTRes(t, (i))
#define BITS_RES_RANGE(i,base,limit) \
  t[(i)] &= ~(BTMask((base),(limit)))
#define WORD_RES_RANGE(i) t[(i)] = (Word)(0)

  ACT_ON_RANGE(base, limit, SINGLE_RES_RANGE,
               BITS_RES_RANGE, WORD_RES_RANGE);
}


/* BTFindSet -- find the lowest set bit in a range in a bit table.
 *
 * Sets foundReturn to false if the range is entirely reset;
 * in this case indexReturn is unset. Sets foundReturn to true
 * otherwise.
 *
 * Implemented as a macro for efficiency reasons.
 * The macro internally uses the label btFindSetLabel.
 * If the macro must be used more than once within a function
 * this label must be redefined to avoid a nameclash. E.g.
 *    #define btFindSetLabel uniqueLabel
 *    BTFindSet(...)
 *    #undef btFindSetLabel
 */

#define BTFindSet(foundReturn,indexReturn,bt,base,limit)\
  BEGIN \
    Bool *bfsFoundReturn = (foundReturn); \
    Index *bfsIndexReturn = (indexReturn); \
    BT bfsBt = (bt); \
    ACT_ON_RANGE((base), (limit), SINGLE_FIND_SET,  \
                 BITS_FIND_SET, WORD_FIND_SET); \
    *bfsFoundReturn = FALSE; \
btFindSetLabel:; \
  END

#define SINGLE_FIND_SET(i)  \
  if (BTGet(bfsBt, (i))) { \
    *bfsIndexReturn = (i); \
    *bfsFoundReturn = TRUE; \
    goto btFindSetLabel; \
  }
#define BITS_FIND_SET(wi,base,limit)  \
  BEGIN \
    Index bactWi = (wi); \
    ACTION_FIND_SET(bactWi, bfsBt[bactWi], (base), (limit)); \
  END
#define WORD_FIND_SET(wi) \
  BEGIN \
    Index wactWi = (wi); \
    ACTION_FIND_SET(wactWi, bfsBt[wactWi], 0, MPS_WORD_WIDTH); \
  END
#define ACTION_FIND_SET(wi,word,base,limit) \
  ACTION_FIND_SET_BIT((wi),(word),(base),(limit),btFindSetLabel)


/* ACTION_FIND_SET_BIT -- Find first set bit in a range
 *
 * Helper macro to find the low bit in a range of a word.
 * Works by first shifting the base of the range to the low
 * bits of the word. Then loops performing a binary chop
 * over the data looking to see if a bit is set in the lower
 * half. If not, it must be in the upper half which is then
 * shifted down. The loop completes after using a chop unit
 * of a single single bit.
 */

#define ACTION_FIND_SET_BIT(wi,word,base,limit,label) \
  BEGIN \
    /* no need to mask the low bits which are shifted */ \
    Index actionIndex = (base); \
    Word actionWord = ((word) & BTMaskHigh((limit))) >> actionIndex; \
    Count actionMaskWidth = (MPS_WORD_WIDTH >> 1); \
    Word actionMask = ~(Word)0 >> (MPS_WORD_WIDTH-actionMaskWidth); \
    if (actionWord != (Word)0) { \
      while (actionMaskWidth != (Count)0) { \
        if ((actionWord & actionMask) == (Word)0) { \
          actionIndex += actionMaskWidth; \
          actionWord >>= actionMaskWidth; \
        } \
        actionMaskWidth >>= 1; \
        actionMask >>= actionMaskWidth; \
      } \
      *bfsIndexReturn = ((wi) << MPS_WORD_SHIFT) | actionIndex; \
      *bfsFoundReturn = TRUE; \
      goto label; \
    } \
  END


/* BTFindRes -- find the lowest reset bit in a range in a bit table.
 *
 * Usage as for BTFindSet
 *
 * Internally uses the label btFindResLabel
 * which must be redefined to avoid a nameclash if the macro is
 * used twice in a function scope.
 */

#define BTFindRes(foundReturn,indexReturn,bt,base,limit)\
  BEGIN \
    Bool *bfsFoundReturn = (foundReturn); \
    Index *bfsIndexReturn = (indexReturn); \
    BT bfsBt = (bt); \
    ACT_ON_RANGE((base), (limit), SINGLE_FIND_RES,  \
                 BITS_FIND_RES, WORD_FIND_RES); \
    *bfsFoundReturn = FALSE; \
btFindResLabel:; \
  END

#define SINGLE_FIND_RES(i)  \
  if (!BTGet(bfsBt, (i))) { \
    *bfsIndexReturn = (i); \
    *bfsFoundReturn = TRUE; \
    goto btFindResLabel; \
  }
#define BITS_FIND_RES(wi,base,limit)  \
  BEGIN \
    Index bactWi = (wi); \
    ACTION_FIND_RES(bactWi,bfsBt[bactWi], (base), (limit)); \
  END
#define WORD_FIND_RES(wi) \
  BEGIN \
    Index wactWi = (wi); \
    ACTION_FIND_RES(wactWi, bfsBt[wactWi], 0, MPS_WORD_WIDTH); \
  END
#define ACTION_FIND_RES(wi,word,base,limit) \
  ACTION_FIND_SET_BIT((wi),~(word),(base),(limit),btFindResLabel)


/* BTFindSetHigh -- find the highest set bit in a range in a bit table.
 *
 * Usage as for BTFindSet
 *
 * Internally uses the label btFindSetHighLabel
 * which must be redefined to avoid a nameclash if the macro is
 * used twice in a function scope.
 */

#define BTFindSetHigh(foundReturn,indexReturn,bt,base,limit)\
  BEGIN \
    Bool *bfsFoundReturn = (foundReturn); \
    Index *bfsIndexReturn = (indexReturn); \
    BT bfsBt = (bt); \
    ACT_ON_RANGE_HIGH((base), (limit), SINGLE_FIND_SET_HIGH, \
                      BITS_FIND_SET_HIGH, WORD_FIND_SET_HIGH); \
    *bfsFoundReturn = FALSE; \
btFindSetHighLabel:; \
  END

#define SINGLE_FIND_SET_HIGH(i)  \
  if (BTGet(bfsBt, (i))) { \
    *bfsIndexReturn = (i); \
    *bfsFoundReturn = TRUE; \
    goto btFindSetHighLabel; \
  }
#define BITS_FIND_SET_HIGH(wi,base,limit) \
  BEGIN \
    Index bactWi = (wi); \
    ACTION_FIND_SET_HIGH(bactWi, bfsBt[bactWi], (base), (limit)); \
  END
#define WORD_FIND_SET_HIGH(wi) \
  BEGIN \
    Index wactWi = (wi); \
    ACTION_FIND_SET_HIGH(wactWi, (bfsBt[wactWi]), 0, MPS_WORD_WIDTH); \
  END
#define ACTION_FIND_SET_HIGH(wi,word,base,limit) \
  ACTION_FIND_SET_BIT_HIGH((wi),(word),(base),(limit),btFindSetHighLabel)


/* ACTION_FIND_SET_BIT_HIGH -- Find highest set bit in a range
 *
 * Helper macro to find the high bit in a range of a word.
 * Essentially a mirror image of ACTION_FIND_SET
 */

#define ACTION_FIND_SET_BIT_HIGH(wi,word,base,limit,label) \
  BEGIN \
    /* no need to mask the high bits which are shifted */ \
    Index actionShift = MPS_WORD_WIDTH - (limit);  \
    Index actionIndex = MPS_WORD_WIDTH - 1 - actionShift; \
    Word actionWord = ((word) & BTMaskLow((base))) << actionShift; \
    Count actionMaskWidth = (MPS_WORD_WIDTH >> 1); \
    Word actionMask = ~(Word)0 << (MPS_WORD_WIDTH-actionMaskWidth); \
    if (actionWord != (Word)0) { \
      while (actionMaskWidth != (Count)0) { \
        if ((actionWord & actionMask) == (Word)0) { \
          actionIndex -= actionMaskWidth; \
          actionWord <<= actionMaskWidth; \
        } \
        actionMaskWidth >>= 1; \
        actionMask <<= actionMaskWidth; \
      } \
      *bfsIndexReturn = ((wi) << MPS_WORD_SHIFT) | actionIndex; \
      *bfsFoundReturn = TRUE; \
      goto label; \
    } \
  END


/* BTFindResHigh -- find the highest reset bit in a range
 *
 * Usage as for BTFindSet
 *
 * Internally uses the label btFindSetHighLabel
 * which must be redefined to avoid a nameclash if the macro is
 * used twice in a function scope.
 */

#define BTFindResHigh(foundReturn,indexReturn,bt,base,limit)\
  BEGIN \
    Bool *bfsFoundReturn = (foundReturn); \
    Index *bfsIndexReturn = (indexReturn); \
    BT bfsBt = (bt); \
    ACT_ON_RANGE_HIGH((base), (limit), SINGLE_FIND_RES_HIGH, \
                      BITS_FIND_RES_HIGH, WORD_FIND_RES_HIGH); \
    *bfsFoundReturn = FALSE; \
btFindResHighLabel:; \
  END

#define SINGLE_FIND_RES_HIGH(i)  \
  if (!BTGet(bfsBt, (i))) { \
    *bfsIndexReturn = (i); \
    *bfsFoundReturn = TRUE; \
    goto btFindResHighLabel; \
  }
#define BITS_FIND_RES_HIGH(wi,base,limit) \
  BEGIN \
    Index bactWi = (wi); \
    ACTION_FIND_RES_HIGH(bactWi, bfsBt[bactWi], (base), (limit)); \
  END
#define WORD_FIND_RES_HIGH(wi) \
  BEGIN \
    Index wactWi = (wi); \
    ACTION_FIND_RES_HIGH(wactWi, (bfsBt[wactWi]), 0, MPS_WORD_WIDTH); \
  END
#define ACTION_FIND_RES_HIGH(wi,word,base,limit) \
  ACTION_FIND_SET_BIT_HIGH((wi),~(word),(base),(limit),btFindResHighLabel)


/* BTFindResRange -- find a reset range of bits in a bit table
 *
 * Starts searching at the low end of the search range.
 *
 * <design/bt#.fun.find-res-range>.
 */

static Bool BTFindResRange(Index *baseReturn, Index *limitReturn,
                           BT bt,
                           Index searchBase, Index searchLimit,
                           Count minLength, Count maxLength)
{
  Bool foundRes;         /* true if a reset bit is found */
  Index resBase;         /* base of a candidate reset range */
  Index unseenBase;      /* base of testing so far */
  Index minLimit;        /* limit of minimal acceptable range */
  Index resLimit;        /* limit of search for a candidate range */

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVERT(BT, bt);
  AVER(searchBase < searchLimit);
  AVER(minLength > 0);
  AVER(minLength <= maxLength);
  AVER(maxLength <= searchLimit - searchBase);

  foundRes = FALSE;     /* don't know first reset bit */
  minLimit = 0;         /* avoid spurious compiler warning */
  resBase = searchBase; /* haven't seen anything yet */
  unseenBase = searchBase;  /* haven't seen anything yet */
  resLimit = searchLimit - minLength + 1;

  while (resBase < resLimit) {
    Index setIndex;  /* index of last set bit found */
    Bool foundSet = FALSE; /* true if a set bit is found */

    /* Find the first reset bit if it's not already known */
    if (!foundRes) {
      BTFindRes(&foundRes, &resBase, bt, unseenBase, resLimit);
      if (!foundRes) {
        /* failure */
        return FALSE;
      }
      unseenBase = resBase + 1;
      minLimit = resBase + minLength;
    }

    /* Look to see if there is any set bit in the minimum range */
    BTFindSetHigh(&foundSet, &setIndex, bt, unseenBase, minLimit);
    if (!foundSet) {
      /* Found minimum range. Extend it. */
      Index setBase;   /* base of search for set bit */
      Index setLimit;  /* limit search for set bit */
      foundSet = FALSE;
      setBase = minLimit;
      setLimit = resBase + maxLength;
      if (setLimit > searchLimit)
        setLimit = searchLimit;
      if (setLimit > setBase)
        BTFindSet(&foundSet, &setIndex, bt, setBase, setLimit);
      if (!foundSet)
        setIndex = setLimit;

      AVER(setIndex - resBase >= minLength);
      AVER(setIndex - resBase <= maxLength);
      *baseReturn = resBase;
      *limitReturn = setIndex;
      return TRUE;

    } else {
      /* Range was too small. Try again */
      unseenBase = minLimit;
      resBase = setIndex + 1;
      if (resBase != minLimit) {
        /* Already found the start of next candidate range */
        minLimit = resBase + minLength;
        /* minLimit might just have gone out of bounds, but in that
         * case resBase >= resLimit and so the loop will exit. */
        AVER(minLimit <= searchLimit || resBase >= resLimit);
      } else {
        foundRes = FALSE;
      }
    }
  }

  /* failure */
  return FALSE;
}


/* BTFindResRangeHigh -- find a reset range of bits in a bit table
 *
 * Starts searching at the high end of the search range.
 *
 * <design/bt#.fun.find-res-range>.
 */

static Bool BTFindResRangeHigh(Index *baseReturn, Index *limitReturn,
                               BT bt,
                               Index searchBase, Index searchLimit,
                               Count minLength,
                               Count maxLength)
{
  Bool foundRes;         /* true if a reset bit is found */
  Index resLimit;        /* limit of a candidate reset range */
  Index resIndex;        /* index of highest reset bit found */
  Index unseenLimit;     /* limit of testing so far */
  Index minBase;         /* base of minimal acceptable range */
  Index resBase;         /* base of search for a candidate range */

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVERT(BT, bt);
  AVER(searchBase < searchLimit);
  AVER(minLength > 0);
  AVER(minLength <= maxLength);
  AVER(maxLength <= searchLimit - searchBase);

  foundRes = FALSE;     /* don't know first reset bit */
  minBase = 0;          /* avoid spurious compiler warning */
  resLimit = searchLimit;    /* haven't seen anything yet */
  unseenLimit = searchLimit; /* haven't seen anything yet */
  resBase = searchBase + minLength -1;

  while (resLimit > resBase) {
    Index setIndex;  /* index of first set bit found */
    Bool foundSet = FALSE; /* true if a set bit is found */

    /* Find the first reset bit if it's not already known */
    if (!foundRes) {
      /* Look for the limit of a range */
      BTFindResHigh(&foundRes, &resIndex, bt, resBase, unseenLimit);
      if (!foundRes) {
        /* failure */
        return FALSE;
      }
      resLimit = resIndex + 1;
      unseenLimit = resIndex;
      minBase = resLimit - minLength;
    }

    /* Look to see if there is any set bit in the minimum range */
    BTFindSet(&foundSet, &setIndex, bt, minBase, unseenLimit);
    if (!foundSet) {
      /* Found minimum range. Extend it. */
      Index setBase;   /* base of search for set bit */
      Index setLimit;  /* limit search for set bit */
      Index baseIndex; /* base of reset range found */
      foundSet = FALSE;
      setLimit = minBase;
      if ((searchBase + maxLength) > resLimit)
        setBase = searchBase;
      else
        setBase  = resLimit - maxLength;
      if (setLimit > setBase)
        BTFindSetHigh(&foundSet, &setIndex, bt, setBase, setLimit);
      if (foundSet)
        baseIndex = setIndex+1;
      else
        baseIndex = setBase;

      AVER(resLimit - baseIndex >= minLength);
      AVER(resLimit - baseIndex <= maxLength);
      *baseReturn = baseIndex;
      *limitReturn = resLimit;
      return TRUE;

    } else {
      /* Range was too small. Try again */
      unseenLimit = minBase;
      resLimit = setIndex;
      if (resLimit != minBase) {
        /* Already found the start of next candidate range. This wraps
         * round if minLength > resLimit (all the variables are
         * unsigned so this behaviour is defined), but that means that
         * resLimit <= resBase and so the loop will exit. */
        AVER(resLimit >= minLength || resLimit <= resBase);
        minBase = resLimit - minLength;
      } else {
        foundRes = FALSE;
      }
    }
  }

  /* failure */
  return FALSE;
}


/* BTFindLongResRange -- find long range of reset bits in a bit table
 *
 * <design/bt#.fun.find-long-res-range>.
 */

Bool BTFindLongResRange(Index *baseReturn, Index *limitReturn,
                        BT bt,
                        Index searchBase, Index searchLimit,
                        Count length)
{
  /* All parameters are checked by BTFindResRange. */
  return BTFindResRange(baseReturn, limitReturn,
                        bt,
                        searchBase, searchLimit,
                        length, searchLimit - searchBase);
}


/* BTFindLongResRangeHigh -- find long range of reset bits in a bit table
 *
 * <design/bt#.fun.find-long-res-range-high>.
 */

Bool BTFindLongResRangeHigh(Index *baseReturn, Index *limitReturn,
                            BT bt,
                            Index searchBase, Index searchLimit,
                            Count length)
{
  /* All parameters are checked by BTFindResRangeHigh. */
  return BTFindResRangeHigh(baseReturn, limitReturn,
                            bt,
                            searchBase, searchLimit,
                            length, searchLimit - searchBase);
}


/* BTFindShortResRange -- find short range of reset bits in a bit table
 *
 * <design/bt#.fun.find-short-res-range>.
 */

Bool BTFindShortResRange(Index *baseReturn, Index *limitReturn,
                         BT bt,
                         Index searchBase, Index searchLimit,
                         Count length)
{
  /* All parameters are checked by BTFindResRange. */
  return BTFindResRange(baseReturn, limitReturn,
                        bt,
                        searchBase, searchLimit,
                        length, length);
}

/* BTFindShortResRangeHigh -- find short range of reset bits in a bit table
 *
 * Starts looking from the top of the search range.
 *
 * <design/bt#.fun.find-short-res-range-high>.
 */

Bool BTFindShortResRangeHigh(Index *baseReturn, Index *limitReturn,
                             BT bt,
                             Index searchBase, Index searchLimit,
                             Count length)
{
  /* All parameters are checked by BTFindResRangeHigh. */
  return BTFindResRangeHigh(baseReturn, limitReturn,
                            bt,
                            searchBase, searchLimit,
                            length, length);
}


/* BTRangesSame -- check that a range of bits in two BTs are the same.
 *
 * <design/bt#.if.ranges-same>
 */

Bool BTRangesSame(BT comparand, BT comparator, Index base, Index limit)
{
  AVERT(BT, comparand);
  AVERT(BT, comparator);
  AVER(base < limit);

#define SINGLE_RANGES_SAME(i) \
  if (BTGet(comparand, (i)) != BTGet(comparator, (i))) \
      return FALSE
#define BITS_RANGES_SAME(i,base,limit) \
  BEGIN \
    Index bactI = (i); \
    Word bactMask = BTMask((base),(limit)); \
    if ((comparand[bactI] & (bactMask)) != \
       (comparator[bactI] & (bactMask))) \
      return FALSE; \
  END
#define WORD_RANGES_SAME(i) \
  BEGIN \
    Index wactI = (i); \
    if ((comparand[wactI]) != (comparator[wactI])) \
      return FALSE; \
  END

  ACT_ON_RANGE(base, limit, SINGLE_RANGES_SAME,
               BITS_RANGES_SAME, WORD_RANGES_SAME);
  return TRUE;
}


/* BTCopyInvertRange -- copy a range of bits from one BT to another,
 * inverting them as you go.
 *
 * <design/bt#.if.copy-invert-range>
 */

void BTCopyInvertRange(BT fromBT, BT toBT, Index base, Index limit)
{
  AVERT(BT, fromBT);
  AVERT(BT, toBT);
  AVER(fromBT != toBT);
  AVER(base < limit);

#define SINGLE_COPY_INVERT_RANGE(i) \
  if (BTGet(fromBT, (i))) \
    BTRes(toBT, (i)); \
  else \
    BTSet(toBT, (i))
#define BITS_COPY_INVERT_RANGE(i,base,limit) \
  BEGIN \
    Index bactI = (i); \
    Word bactMask = BTMask((base),(limit)); \
    toBT[bactI] = \
      (toBT[bactI] & ~bactMask) | (~fromBT[bactI] & bactMask); \
  END
#define WORD_COPY_INVERT_RANGE(i) \
  BEGIN \
    Index wactI = (i); \
    toBT[wactI] = ~fromBT[wactI]; \
  END

  ACT_ON_RANGE(base, limit, SINGLE_COPY_INVERT_RANGE,
               BITS_COPY_INVERT_RANGE, WORD_COPY_INVERT_RANGE);
}


/* BTCopyRange -- copy a range of bits from one BT to another
 *
 * <design/bt#.if.copy-range>
 */

void BTCopyRange(BT fromBT, BT toBT, Index base, Index limit)
{
  AVERT(BT, fromBT);
  AVERT(BT, toBT);
  AVER(fromBT != toBT);
  AVER(base < limit);

#define SINGLE_COPY_RANGE(i) \
  if (BTGet(fromBT, (i))) \
    BTSet(toBT, (i)); \
  else \
    BTRes(toBT, (i))
#define BITS_COPY_RANGE(i,base,limit) \
  BEGIN \
    Index bactI = (i); \
    Word bactMask = BTMask((base),(limit)); \
    toBT[bactI] = \
      (toBT[bactI] & ~bactMask) | (fromBT[bactI] & bactMask); \
  END
#define WORD_COPY_RANGE(i) \
  BEGIN \
    Index wactI = (i); \
    toBT[wactI] = fromBT[wactI]; \
  END

  ACT_ON_RANGE(base, limit, SINGLE_COPY_RANGE,
               BITS_COPY_RANGE, WORD_COPY_RANGE);
}


/* BTCopyOffsetRange -- copy a range of bits from one BT to an
 * offset range in another BT
 *
 * .slow: Can't always use ACT_ON_RANGE because word alignment
 * may differ for each range. We could try to be smart about
 * detecting similar alignment - but we don't.
 *
 * <design/bt#.if.copy-offset-range>
 */

void BTCopyOffsetRange(BT fromBT, BT toBT,
                       Index fromBase, Index fromLimit,
                       Index toBase, Index toLimit)
{
  Index fromBit, toBit;

  AVERT(BT, fromBT);
  AVERT(BT, toBT);
  AVER(fromBT != toBT);
  AVER(fromBase < fromLimit);
  AVER(toBase < toLimit);
  AVER((fromLimit - fromBase) == (toLimit - toBase));

  for (ITER_PARALLEL(fromBit = fromBase, toBit = toBase);
       fromBit < fromLimit;
       ITER_PARALLEL(++fromBit, ++toBit))
  {
    if (BTGet(fromBT, fromBit))
      BTSet(toBT, toBit);
    else
      BTRes(toBT, toBit);
  }
}


/* BTCountResRange -- count number of reset bits in a range */

Count BTCountResRange(BT bt, Index base, Index limit)
{
  Count c = 0;
  Index bit;

  AVERT(BT, bt);
  AVER(base < limit);

  for (bit = base; bit < limit; ++bit)
    if (!BTGet(bt, bit))
      ++c;
  return c;
}


/* C. COPYRIGHT AND LICENSE
 *
 * Copyright (C) 2001-2020 Ravenbrook Limited <https://www.ravenbrook.com/>.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */