/*
  Bitmapped domains.
*/

#ifndef COMPACT_DOMAINS
#  error "COMPACT_DOMAINS undefined: shouldn't be reading this file"
#endif

#ifndef ffs
#  if UNIT_BITS == (__SIZEOF_INT__ << 3)
/* #define ffs ffs */
#  elif UNIT_BITS == (__SIZEOF_LONG__ << 3)
#    define ffs ffsl
#  elif UNIT_BITS == (__SIZEOF_LONG_LONG__ << 3)
#    define ffs ffsll
#  else
#    error "what ffs shall I use?"
#  endif
#endif

#define WORDS	DOMAIN_MAP_WORDS

#define LSBIT ((_fd_bitmap) 1)
#define MSBIT ((_fd_bitmap) 1 << UNIT_BITS - 1)
#define ALL_ONES ((_fd_bitmap) -1)


/* Count the ones in a bitmap. */
static int ones(_fd_bitmap m)
{
  // from http://aggregate.org/MAGIC/

#if UNIT_BITS == 32
  m -= (m >> 1) & 0x55555555;
  m = (m >> 2 & 0x33333333) + (m & 0x33333333);
  m = ((m >> 4) + m) & 0x0f0f0f0f;
  m += m >> 8;
  m += m >> 16;

  return m & 0x0000003f;
#elif UNIT_BITS == 64
  m -= (m >> 1) & 0x5555555555555555LL;
  m = (m >> 2 & 0x3333333333333333LL) + (m & 0x3333333333333333LL);
  m = ((m >> 4) + m) & 0x0f0f0f0f0f0f0f0fLL;
  m += m >> 8;
  m += m >> 16;
  m += m >> 32;

  return m & 0x000000000000007fLL;
#endif /* UNIT_BITS == 32 || UNIT_BITS == 64 */
}


#ifndef DOMAIN_BOUNDS

fd_value fd_new_value(int min, int max)
{
  fd_value v;

  if (min < MIN_VALUE)
    _fd_fatal("value less than MIN_VALUE");

  if (max > MAX_VALUE)
    _fd_fatal("value greater than MAX_VALUE");

#ifdef INLINE_DOMAINS
  return (ALL_ONES >> min) & (ALL_ONES << DOMAIN_BITS - max - 1);
#elif WORDS == 1
  if (v = malloc(sizeof(*v)))
    (*v)[0] = (ALL_ONES >> min) & (ALL_ONES << DOMAIN_BITS - max - 1);
#else /* INLINE_DOMAINS || WORDS == 1 */
  if (v = malloc(sizeof(*v)))
    {
      int f = min / UNIT_BITS, l = max / UNIT_BITS;

      if (f == l)
	(*v)[f] = (ALL_ONES >> min % UNIT_BITS) &
		  (ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1);
      else
	{
	  (*v)[f] = ALL_ONES >> min % UNIT_BITS;
	  while (++f < l)
	    (*v)[f] = ALL_ONES;
	  (*v)[l] = ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1;
	}
    }
#endif /* INLINE_DOMAINS || WORDS == 1 */

  return v;
}

#if defined(USE_STORE) && !defined(INLINE_DOMAINS)

/* create a new domain at the address given */
void _fd_init_domain(DOMAIN_REF_T(domain), int min, int max)
{
  if (min < MIN_VALUE)
    _fd_fatal("value less than MIN_VALUE");

  if (max > MAX_VALUE)
    _fd_fatal("value greater than MAX_VALUE");

#if WORDS == 1
  (*domain)[0] = (ALL_ONES >> min) & (ALL_ONES << DOMAIN_BITS - max - 1);
#else /* WORDS == 1 */
  {
    int f = min / UNIT_BITS, l = max / UNIT_BITS;

    memset(domain, 0, DOMAIN_BITS / 8);

    if (f == l)
      (*domain)[f] = (ALL_ONES >> min % UNIT_BITS) &
		     (ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1);
    else
      {
	(*domain)[f] = ALL_ONES >> min % UNIT_BITS;
	while (++f < l)
	  (*domain)[f] = ALL_ONES;
	(*domain)[l] = ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1;
      }
  }
#endif /* WORDS == 1 */
}

#endif /* USE_STORE && !INLINE_DOMAINS */

bool _fd_val_empty(fd_value domain)
{
#ifdef INLINE_DOMAINS
  return domain == 0;
#elif WORDS == 1
  return **domain == 0;
#else /* INLINE_DOMAINS || WORDS == 1 */
  int i;

  for (i = 0; i < WORDS; ++i)
    if ((*domain)[i])
      return false;

  return true;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

int _fd_val_single(fd_value domain, int *value)
{
#ifdef INLINE_DOMAINS
  if (domain != (domain & -domain))
    return 0;

  if (value != NULL)
    *value = DOMAIN_BITS - ffs(domain);

  return 1;
#elif WORDS == 1
#if 01
  _fd_bitmap d;

  d = (*domain)[0];

  if (d != (d & -d))
    return 0;

  if (value != NULL)
    *value = DOMAIN_BITS - ffs(d);

  return 1;
#elif 0
  int b;

  b = ffs(**domain);

  if (**domain != LSBIT << b - 1)
    return 0;

  if (value != NULL)
    *value = DOMAIN_BITS - b;

  return 1;
#elif 0
  _fd_bitmap d;
  int b;

  for (b = 0, d = **domain; d != 0 && (d & MSBIT) == 0; ++b, d <<= 1)
    ;

  if (d != MSBIT)
    return 0;

  if (value != NULL)
    *value = b;

  return 1;
#elif 0
  _fd_bitmap d = **domain;
  _fd_bitmap bit;
  int v;

  for (v = MAX_VALUE, bit = 0x1; v >= MIN_VALUE; --v, bit <<= 1)
    if (d == bit)
      {
	if (value != NULL)
	  *value = v;

	return 1;
      }

  return 0;
#elif 0
  _fd_bitmap d = **domain;
  int v;
  _fd_bitmap bit;

  for (v = MIN_VALUE, bit = MSBIT; v <= MAX_VALUE; ++v, bit >>= 1)
    if (d & bit)
      {
	if (d == bit)
	  {
	    if (value != NULL)
	      *value = v;

	    return 1;
	  }

	return 0;
      }

  return 0;
#elif 0
  _fd_bitmap d = **domain;
  int bot = MIN_VALUE, top = MAX_VALUE;
  _fd_bitmap bits, mask;

  bits = DOMAIN_BITS / 2;
  mask = ALL_ONES << bits;

  while (bot < top)
    if ((d & mask) == 0)
      {
	bot += bits;
	bits /= 2;
	mask >>= bits;
      }
    else if ((d & mask) == d)
      {
	top -= bits;
	bits /= 2;
	mask <<= bits;
      }
    else
      return 0;

  if (d == 0)
    return 0;

  if (value != NULL)
    *value = bot;

  return 1;
#elif 0
  _fd_bitmap d = **domain;
  int bits, bit31;
  _fd_bitmap mask;

  bits = DOMAIN_BITS / 2;
  mask = (_fd_bitmap) -1 >> bits;
  bit31 = MAX_VALUE;

  while (bits)
    {
      if ((d & mask) == 0)
	{
	  d >>= bits;
	  bit31 -= bits;
	}
      else if ((d & ~mask) != 0)
	return 0;

      bits >>= 1;
      mask >>= bits;
    }

  if (d == 0)
    return 0;

  if (value != NULL)
    *value = bit31;

  return 1;
#elif 0
#if UNIT_BITS != 32
#  error "only works for 32 bits/unit"
#endif
  int v;

  switch (**domain)
    {
      case 0x80000000: v = 0; break;
      case 0x40000000: v = 1; break;
      case 0x20000000: v = 2; break;
      case 0x10000000: v = 3; break;
      case 0x08000000: v = 4; break;
      case 0x04000000: v = 5; break;
      case 0x02000000: v = 6; break;
      case 0x01000000: v = 7; break;
      case 0x00800000: v = 8; break;
      case 0x00400000: v = 9; break;
      case 0x00200000: v = 10; break;
      case 0x00100000: v = 11; break;
      case 0x00080000: v = 12; break;
      case 0x00040000: v = 13; break;
      case 0x00020000: v = 14; break;
      case 0x00010000: v = 15; break;
      case 0x00008000: v = 16; break;
      case 0x00004000: v = 17; break;
      case 0x00002000: v = 18; break;
      case 0x00001000: v = 19; break;
      case 0x00000800: v = 20; break;
      case 0x00000400: v = 21; break;
      case 0x00000200: v = 22; break;
      case 0x00000100: v = 23; break;
      case 0x00000080: v = 24; break;
      case 0x00000040: v = 25; break;
      case 0x00000020: v = 26; break;
      case 0x00000010: v = 27; break;
      case 0x00000008: v = 28; break;
      case 0x00000004: v = 29; break;
      case 0x00000002: v = 30; break;
      case 0x00000001: v = 31; break;
      default:
	return 0;
    }

  if (value != NULL)
    *value = v;

  return 1;
#endif
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap *p, *q;
  int i, n;

  for (n = 0, q = *domain; n < WORDS && *q == 0; ++n, ++q)
    ;

  assert(n < WORDS);	// empty domains are detected elsewhere

  for (i = n + 1, p = q + 1; i < WORDS && *p == 0; ++i, ++p)
    ;

  if (i < WORDS)
    return 0;

  if (*q != (*q & -*q))
    return 0;

  if (value != NULL)
    *value = UNIT_BITS * (n + 1) - ffs(*q);

  return 1;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

#if 0
static _empty, _times, _success;

int _fd_val_single(fd_value domain, int *value)
{
  int result;

  _times++;

  result = _fd_val_single_(domain, value);

  _success += result;
  if (*domain == 0)
    _empty++;

  return result;
}
#endif


void _fd_free_value(fd_value value)
{
#ifndef INLINE_DOMAINS
  free(value);
#endif
}


/* return maximum value from DOMAIN */
int _fd_val_max(fd_value domain)
{
#ifdef INLINE_DOMAINS
  assert(domain != 0);

  return DOMAIN_BITS - ffs(domain) + MIN_VALUE;
#elif WORDS == 1
  assert(**domain != 0);

  return DOMAIN_BITS - ffs(**domain) + MIN_VALUE;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap *p, *q;
  int bit, base;

  q = *domain;

  base = MAX_VALUE + 1;
  for (p = q + WORDS - 1; p >= q && *p == 0; --p)
    base -= UNIT_BITS;

  assert(p >= *domain);	// the domain mustn't be empty

  bit = ffs(*p);

  return base - bit;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* return minimum value from DOMAIN */
int _fd_val_min(fd_value domain)
{
  _fd_bitmap d;
  long v = MIN_VALUE;

#ifdef INLINE_DOMAINS
  assert(domain != 0);

  d = domain;
#else /* INLINE_DOMAINS */
#if WORDS == 1
  assert(**domain != 0);

  d = (*domain)[0];
#else /* WORDS == 1 */
  _fd_bitmap *p;
  int i;

  for (i = 0, p = *domain; i < WORDS && *p == 0; ++i, ++p)
    v += UNIT_BITS;

  assert(i < WORDS);	// the domain mustn't be empty

  d = *p;
#endif /* WORDS == 1 */
#endif /* INLINE_DOMAINS */

#if __i386__ || __x86_64__
  long b;

#if __i386__ && UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#endif

  // the Intel manual says that bsr's second operand is the source and
  // that the result will be stored in the first, but the default AT&T
  // syntax GCC produces puts them in reverse
  asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

  v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
  // seen in the GNU-Prolog sources

#if UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
  if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x8000000000000000LL) == 0) { v += 1; }
#elif UNIT_BITS == 32
  if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x80000000) == 0) { v += 1; }
#else
#  error "don't know how to work with UNIT_BITS bits/unit"
#endif
#endif /* __i386__ || __x86_64__ */

  return v;
}

/* return and remove minimum value from DOMAIN */
int _fd_val_del_min(DOMAIN_REF_T(domain))
{
#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;
  long v = 0;

  p = (_fd_bitmap *) domain;

  assert(*p != 0);

  d = *p;

#if __i386__ || __x86_64__
  long b;

#if __i386__ && UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#endif

  asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

  v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
  // seen in the GNU-Prolog sources

#if DOMAIN_BITS == 64
  if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
  if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x8000000000000000LL) == 0) { v += 1;  d <<= 1; }
#elif DOMAIN_BITS == 32
  if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x80000000) == 0) { v += 1;  d <<= 1; }
#else
#  error "don't know how to work with DOMAIN_BITS bits"
#endif
#endif /* __i386__ || __x86_64__ */

  *p ^= MSBIT >> v;

  return v + MIN_VALUE;
#else /* INLINE_DOMAINS || WORDS == 1 */
#warning "_fd_val_del_min is _fd_val_min + _fd_val_del_val"
  int v = _fd_val_min(domain);

  _fd_val_del_val(v, domain);

  return v;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* return and remove maximum value from DOMAIN */
int _fd_val_del_max(DOMAIN_REF_T(domain))
{
#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap *p;
  int b;

  p = (_fd_bitmap *) domain;

  assert(*p != 0);

  b = ffs(*p);

  *p ^= LSBIT << (b - 1);

  return DOMAIN_BITS - b + MIN_VALUE;;
#else /* INLINE_DOMAINS || WORDS == 1 */
#warning "_fd_val_del_max is _fd_val_max + _fd_val_del_val"
  int v = _fd_val_max(domain);

  _fd_val_del_val(v, domain);

  return v;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

int _fd_val_contains_val(fd_value domain, int value)
{
  if (value < MIN_VALUE || value > MAX_VALUE)
    return 0;

#ifdef INLINE_DOMAINS
  return (domain & MSBIT >> value) != 0;
#elif WORDS == 1
  return ((*domain)[0] & MSBIT >> value) != 0;
#else /* INLINE_DOMAINS || WORDS == 1 */
  return ((*domain)[value / UNIT_BITS] & MSBIT >> value % UNIT_BITS) != 0;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

// XXX: a variable can only be set to values in its domain
void _fd_val_set_value(DOMAIN_REF_T(domain), int value)
{
  assert(MIN_VALUE <= value && value <= MAX_VALUE);

#if defined(INLINE_DOMAINS) || WORDS == 1
  * (_fd_bitmap *) domain = MSBIT >> value;
#else /* INLINE_DOMAINS || WORDS == 1 */
  memset(domain, 0, sizeof(*domain));

  (*domain)[value / UNIT_BITS] = MSBIT >> value % UNIT_BITS;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove all values greater than or equal to VALUE from DOMAIN */
int _fd_val_del_ge(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

  if (value > MAX_VALUE)
    return 0;

  p = (_fd_bitmap *) domain;

  if (value <= MIN_VALUE)
    d = 0;
  else
    d = *p & (ALL_ONES << DOMAIN_BITS - value);

  if (*p == d)
    return 0;

  *p = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap *p, w;
  int changed = 0;
  int i;

  if (value > MAX_VALUE)
    return 0;

  if (value <= MIN_VALUE)
    {
      // domain becomes empty
      memset(domain, 0, sizeof(*domain));

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = WORDS - 1, p = *domain + i; i > value / UNIT_BITS && *p == 0; --i, --p)
    ;

  if (i > value / UNIT_BITS)
    {
      memset(*domain + value / UNIT_BITS + 1, 0,
	     (i - value / UNIT_BITS) * sizeof(**domain));

      changed = 1;
    }

  w = (*domain)[value / UNIT_BITS] &
        ((ALL_ONES << UNIT_BITS - value % UNIT_BITS - 1) << 1);
        // XXX: convoluted because of when value % UNIT_BITS == 0

  if (!changed && w == (*domain)[value / UNIT_BITS])
    return 0;

  (*domain)[value / UNIT_BITS] = w;

  return 1;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove all values greater than VALUE from DOMAIN */
int _fd_val_del_gt(int value, DOMAIN_REF_T(domain))
{
#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value + 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (value >= MAX_VALUE)
    return 0;

  p = (_fd_bitmap *) domain;

  if (value < MIN_VALUE)
    d = 0;
  else
    d = *p & -(MSBIT >> value);

  if (*p == d)
    return 0;

  *p = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
#warning "_fd_val_del_gt is _fd_val_del_ge(+1)"
  return _fd_val_del_ge(value + 1, domain);
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove all values less than or equal to VALUE from DOMAIN */
int _fd_val_del_le(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

  if (value < MIN_VALUE)
    return 0;

  p = (_fd_bitmap *) domain;

  if (value >= MAX_VALUE)
    d = 0;
  else
    d = *p & (ALL_ONES >> value + 1);

  if (*p == d)
    return 0;

  *p = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap *p, w;
  int changed = 0;
  int i;

  if (value < MIN_VALUE)
    return 0;

  if (value >= MAX_VALUE)
    {
      // domain becomes empty
      memset(domain, 0, sizeof(*domain));

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = 0, p = *domain; i < value / UNIT_BITS && *p == 0; ++i, ++p)
    ;

  if (i < value / UNIT_BITS)
    {
      memset(*domain + i, 0, (value / UNIT_BITS - i) * sizeof(**domain));

      changed = 1;
    }

  w = (*domain)[value / UNIT_BITS] & (ALL_ONES >> value % UNIT_BITS >> 1);

  if (!changed && w == (*domain)[value / UNIT_BITS])
    return 0;

  (*domain)[value / UNIT_BITS] = w;

  return 1;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove all values less than VALUE from DOMAIN */
int _fd_val_del_lt(int value, DOMAIN_REF_T(domain))
{
#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value - 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (value <= MIN_VALUE)
    return 0;

  p = (_fd_bitmap *) domain;

  if (value > MAX_VALUE)
    d = 0;
  else
    d = *p & (ALL_ONES >> value);

  if (*p == d)
    return 0;

  *p = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
#warning "_fd_val_del_lt is _fd_val_del_le(-1)"
  return _fd_val_del_le(value - 1, domain);
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove VALUE from DOMAIN */
int _fd_val_del_val(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

  if (value > MAX_VALUE || value < MIN_VALUE)
    return 0;

  p = (_fd_bitmap *) domain;

  d = *p & ~ (MSBIT >> value);

  if (*p == d)
    return 0;

  *p = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap w;

  if (value > MAX_VALUE || value < MIN_VALUE)
    return 0;

  w = (*domain)[value / UNIT_BITS] & ~ (MSBIT >> value % UNIT_BITS);

  if ((*domain)[value / UNIT_BITS] == w)
    return 0;

  (*domain)[value / UNIT_BITS] = w;

  return 1;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove every value other than VALUE from DOMAIN */
int _fd_val_del_other(DOMAIN_REF_T(domain), int value)
{
#ifdef DEBUG_VALUE
  printf("remove all but {%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if defined(INLINE_DOMAINS) || WORDS == 1
  _fd_bitmap d, *p;

  if (value < MIN_VALUE || value > MAX_VALUE)
    d = 0;
  else
    d = MSBIT >> value;

  p = (_fd_bitmap *) domain;

  if (*p == d)
    return 0;

  *p &= d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap w;
  int other_values = 0;
  int i;

  if (value < MIN_VALUE || value > MAX_VALUE)
    {
      // domain becomes empty
      memset(domain, 0, sizeof(*domain));

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = 0; !other_values && i < value / UNIT_BITS; ++i)
    other_values = (*domain)[i] != 0;

  for (i = WORDS - 1; !other_values && i > value / UNIT_BITS; --i)
    other_values = (*domain)[i] != 0;

  w = (*domain)[value / UNIT_BITS] & (MSBIT >> value % UNIT_BITS);

  other_values = other_values || (*domain)[value / UNIT_BITS] != w;

  if (other_values)
    memset(domain, 0, sizeof(*domain));

  (*domain)[value / UNIT_BITS] = w;

  return other_values;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* remove from DOMAIN1 all values not in DOMAIN2 */
int _fd_val_intersect(DOMAIN_REF_T(domain1), fd_value domain2)
{
#ifdef INLINE_DOMAINS
  _fd_bitmap d = *domain1 & domain2;

  if (*domain1 == d)
    return 0;

  *domain1 = d;

  return 1;
#elif WORDS == 1
  _fd_bitmap d = (*domain1)[0] & (*domain2)[0];

  if ((*domain1)[0] == d)
    return 0;

  (*domain1)[0] = d;

  return 1;
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap w;
  int changed = 0;
  int i;

  for (i = 0; i < WORDS; ++i)
    {
      w = (*domain1)[i] & (*domain2)[i];

      if (w != (*domain1)[i])
	{
	  (*domain1)[i] = w;
	  changed = 1;
	}
    }

  return changed;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* create a clone of VALUE */
fd_value _fd_val_clone(fd_value value)
{
#ifdef INLINE_DOMAINS
  return value;
#elif WORDS == 1
  fd_value new = malloc(sizeof(*new));

  (*new)[0] = (*value)[0];

  return new;
#else /* INLINE_DOMAINS || WORDS == 1 */
  fd_value new = malloc(sizeof(*new));

  memcpy(new, value, sizeof(*new));

  return new;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

#ifndef INLINE_DOMAINS
/* copy FROM's value to TO */
void _fd_val_copy(DOMAIN_REF_T(to), fd_value from)
{
#ifdef INLINE_DOMAINS
  *to = from;
#elif WORDS == 1
  (*to)[0] = (*from)[0];
#else /* INLINE_DOMAINS || WORDS == 1 */
  memcpy(to, from, sizeof(*from));
#endif /* INLINE_DOMAINS || WORDS == 1 */
}
#endif /* !INLINE_DOMAINS */

int _fd_val_size(fd_value domain)
{
#ifdef INLINE_DOMAINS
#if 01
  return ones(domain);
#else
  _fd_bitmap d;
  int s;

  for (d = domain, s = 0; d != 0; d <<= 1)
    s += (d & MSBIT) != 0;

  return s;
#endif
#elif WORDS == 1
#if 01
  return ones((*domain)[0]);
#else
  _fd_bitmap d;
  int s;

  for (d = **domain, s = 0; d != 0; d <<= 1)
    s += (d & MSBIT) != 0;

  return s;
#endif
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap w, *p;
  int i, s;

  p = *domain;

  s = 0;
  for (i = 0, w = *p; i < WORDS; ++i, w = *++p)
#if 01
    s += ones(w);
#else
    for (; w != 0; w <<= 1)
      s += (w & MSBIT) != 0;
#endif

  return s;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

void _fd_val_print(fd_value value)
{
#ifdef INLINE_DOMAINS
  _fd_bitmap d = value;
  int v;

  putchar('{');

  v = 0;
  while (d)
    {
      for (; d && (d & MSBIT) == 0; ++v, d <<= 1)
	;

      printf("%d", v);

      d <<= 1;
      v++;

      if (d & MSBIT)
	{
	  for (++v, d <<= 1; (d & MSBIT) != 0; ++v, d <<= 1)
	    ;

	  printf("..%d", v - 1);
	}

      if (d)
	printf(",");
    }

  putchar('}');
#elif WORDS == 1
  _fd_bitmap d = (*value)[0];
  int v;

  putchar('{');

  v = 0;
  while (d)
    {
      for (; d && (d & MSBIT) == 0; ++v, d <<= 1)
	;

      printf("%d", v);

      d <<= 1;
      v++;

      if (d & MSBIT)
	{
	  for (++v, d <<= 1; (d & MSBIT) != 0; ++v, d <<= 1)
	    ;

	  printf("..%d", v - 1);
	}

      if (d)
	printf(",");
    }

  putchar('}');
#else /* INLINE_DOMAINS || WORDS == 1 */
  _fd_bitmap w, *p;
  int v, i;

  p = *value;

  putchar('{');

  for (i = 0, w = *p; i < WORDS && w == 0; ++i, w = *++p)
    ;

  v = MIN_VALUE + i * UNIT_BITS;

  while (i < WORDS)
    {
      for (; w && (w & MSBIT) == 0; ++v, w <<= 1)
	;

      printf("%d", v);

      if (++v % UNIT_BITS == 0)
	if (++i < WORDS)
	  w = *++p;
	else
	  break;
      else
	w <<= 1;

      if (w & MSBIT)
	{
	  do
	    {
	      for (++v, w <<= 1; (w & MSBIT) != 0; ++v, w <<= 1)
		;
	    }
	  while (v % UNIT_BITS == 0 && ++i < WORDS && (w = *++p));

	  printf("..%d", v - 1);
	}

      while (!w && ++i < WORDS)
	{
	  w = *++p;
	  v = MIN_VALUE + i * UNIT_BITS;
	}

      if (w)
	printf(",");
    }

  putchar('}');
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

/* Iterate over a domain. */

fd_iterator _fd_val_iterator(fd_value domain)
{
#ifdef INLINE_DOMAINS
  fd_iterator i = malloc(sizeof(*i)); // XXX: NULL

  *i = _fd_val_clone(domain);

  return i;
#else /* INLINE_DOMAINS */
  return _fd_val_clone(domain);
#endif /* INLINE_DOMAINS */
}

// XXX: this is just !_fd_val_empty()
int _fd_val_has_next(fd_iterator domain)
{
#ifdef INLINE_DOMAINS
  return *domain != 0;
#elif WORDS == 1
  return **domain != 0;
#else /* INLINE_DOMAINS || WORDS == 1 */
  int i;

  for (i = 0; i < WORDS; ++i)
    if ((*domain)[i])
      return 1;

  return 0;
#endif /* INLINE_DOMAINS || WORDS == 1 */
}

int _fd_val_next_element(fd_iterator domain)
{
  _fd_bitmap d, *p;
  long v = 0;

  // find the minimum value in the domain
#ifdef INLINE_DOMAINS
  p = domain;
#elif WORDS == 1
  p = *domain;
#else
  for (p = *domain; *p == 0; ++p)
    v += UNIT_BITS;
#endif /* INLINE_DOMAINS || WORDS == 1 */

  d = *p;

#if __i386__ || __x86_64__
  long b;

#  if __i386__ && UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#  endif

  asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

  v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
  // seen in the GNU-Prolog sources

#  if UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
  if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x8000000000000000LL) == 0) { v += 1; }
#  elif UNIT_BITS == 32
  if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x80000000) == 0) { v += 1; }
#  else
#    error "don't know how to work with UNIT_BITS bits/unit"
#  endif
#endif /* __i386__ || __x86_64__ */

  // delete the value found from the domain
#if defined(INLINE_DOMAINS) || WORDS == 1
  *p ^= MSBIT >> v;
#else
  *p ^= MSBIT >> v % UNIT_BITS;
#endif

  return v + MIN_VALUE;
}

void _fd_val_iterator_dispose(fd_iterator domain)
{
#ifdef INLINE_DOMAINS
  free(domain);
#else
  _fd_free_value(domain);
#endif
}

// SPLIT&GO

void _fd_val_split(DOMAIN_REF_T(src), DOMAIN_REF_T(remaining))
{
#ifdef INLINE_DOMAINS
  int value = _fd_val_select(*src);

  *remaining = *src ^ (MSBIT >> value);
  *src = MSBIT >> value;
#elif WORDS == 1
  int value = _fd_val_select(src);

  (*remaining)[0] = (*src)[0] ^ (MSBIT >> value);
  (*src)[0] = MSBIT >> value;
#else /* INLINE_DOMAINS || WORDS == 1 */
  int value = _fd_val_select(src);

  // XXX: done in _fd_start_saving_store()
  //memcpy(remaining, src, sizeof(*src));
  memset(src, 0, sizeof(*src));

  (*src)[value / UNIT_BITS] = MSBIT >> value % UNIT_BITS;
  (*remaining)[value / UNIT_BITS] ^= MSBIT >> value % UNIT_BITS;
#endif /* INLINE_DOMAINS */
}

#else /* DOMAIN_BOUNDS */

/*
  Bitmapped domains with minimum and maximum.
*/

// The following should hold:
//   sizeof(_fd_value_core) = DOMAIN_WORDS * sizeof(_fd_bitmap)

// Invariants:
//   domain->min & ~INVALID_BOUNDARY <= min(domain)
//   domain->max & ~INVALID_BOUNDARY >= max(domain)

#define INVALID_BOUNDARY ((_fd_boundary) (1 << (sizeof(_fd_boundary) << 3) - 1))

fd_value fd_new_value(int min, int max)
{
  fd_value v;

  if (min < MIN_VALUE)
    _fd_fatal("value less than MIN_VALUE");

  if (max > MAX_VALUE)
    _fd_fatal("value greater than MAX_VALUE");

#if WORDS == 1
  if (v = malloc(sizeof(*v)))
      *v->map = (ALL_ONES >> min) & (ALL_ONES << DOMAIN_BITS - max - 1);
#else /* WORDS == 1 */
  if (v = malloc(sizeof(*v)))
    {
      _fd_bitmap *d = v->map;
      int f = min / UNIT_BITS, l = max / UNIT_BITS;

      if (f == l)
	d[f] = (ALL_ONES >> min % UNIT_BITS) &
	       (ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1);
      else
	{
	  d[f] = ALL_ONES >> min % UNIT_BITS;
	  while (++f < l)
	    d[f] = ALL_ONES;
	  d[l] = ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1;
	}
    }
#endif /* WORDS == 1 */

  if (v)
    {
      v->min = min;
      v->max = max;
    }

  return v;
}

#ifdef USE_STORE

/* create a new domain at the address given */
void _fd_init_domain(DOMAIN_REF_T(domain), int min, int max)
{
  if (min < MIN_VALUE)
    _fd_fatal("value less than MIN_VALUE");

  if (max > MAX_VALUE)
    _fd_fatal("value greater than MAX_VALUE");

#if WORDS == 1
  *domain->map = (ALL_ONES >> min) & (ALL_ONES << DOMAIN_BITS - max - 1);
#else /* WORDS == 1 */
  {
    _fd_bitmap *d = domain->map;
    int f = min / UNIT_BITS, l = max / UNIT_BITS;

    memset(d, 0, DOMAIN_BITS / 8);

    if (f == l)
      d[f] = (ALL_ONES >> min % UNIT_BITS) &
	     (ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1);
    else
      {
	d[f] = ALL_ONES >> min % UNIT_BITS;
	while (++f < l)
	  d[f] = ALL_ONES;
	d[l] = ALL_ONES << UNIT_BITS - max % UNIT_BITS - 1;
      }
  }
#endif /* WORDS == 1 */

  domain->min = min;
  domain->max = max;
}

#endif /* USE_STORE */

bool _fd_val_empty(fd_value domain)
{
#if WORDS == 1
  return *domain->map == 0;
#else /* WORDS == 1 */
  int i;

  for (i = 0; i < WORDS; ++i)
    if (domain->map[i])
      return false;

  return true;
#endif /* WORDS == 1 */
}

int _fd_val_single(fd_value domain, int *value)
{
#if WORDS == 1
  _fd_bitmap d;

  d = *domain->map;

  if (d != (d & -d))
    return 0;

  if (value != NULL)
    *value = DOMAIN_BITS - ffs(d);

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap *p, *d;
  int i, n;

  if (!(domain->max & INVALID_BOUNDARY) && !(domain->min & INVALID_BOUNDARY))
    {
      if (domain->min == domain->max)
	{
	  if (value != NULL)
	    *value = domain->min;

	  return 1;
	}

      return 0;
    }

  for (n = 0, d = domain->map; n < WORDS && *d == 0; ++n, ++d)
    ;

  assert(n < WORDS);	// empty domains are detected elsewhere

  for (i = n + 1, p = d + 1; i < WORDS && *p == 0; ++i, ++p)
    ;

  if (i < WORDS)
    return 0;

  if (*d != (*d & -*d))
    return 0;

  if (value != NULL)
    *value = domain->min = domain->max = UNIT_BITS * (n + 1) - ffs(*d);    

  return 1;
#endif /* WORDS == 1 */
}


void _fd_free_value(fd_value value)
{
  free(value);
}


/* return maximum value from DOMAIN */
int _fd_val_max(fd_value domain)
{
  if (domain->max & INVALID_BOUNDARY)
    {
#if WORDS == 1
      assert(*domain->map != 0);

      domain->max = DOMAIN_BITS - ffs(*domain->map) + MIN_VALUE;
#else /* WORDS == 1 */
      _fd_bitmap *p, w;
      int bit, base;

      base = MAX_VALUE + 1;
      for (p = domain->map + WORDS - 1; *p == 0; --p)
	base -= UNIT_BITS;

      assert(p >= domain->map);		// the domain shan't be empty

      bit = ffs(*p);

      assert(base - bit <= (domain->max & ~INVALID_BOUNDARY));

      domain->max = base - bit;
#endif /* WORDS == 1 */
    }

  return domain->max;
}

/* return minimum value from DOMAIN */
int _fd_val_min(fd_value domain)
{
  if (domain->min & INVALID_BOUNDARY)
    {
      _fd_bitmap d;
      long v = MIN_VALUE;

#if WORDS == 1
      assert(*domain->map != 0);

      d = *domain->map;
#else /* WORDS == 1 */
      _fd_bitmap *p;

      for (p = domain->map; *p == 0; ++p)
	v += UNIT_BITS;

      assert((p - domain->map) < WORDS);	// the domain shan't be empty

      d = *p;
#endif /* WORDS == 1 */

#if __i386__ || __x86_64__
      long b;

#if __i386__ && UNIT_BITS == 64
      if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#endif

      // the Intel manual says that bsr's second operand is the source and
      // that the result will be stored in the first, but the default AT&T
      // syntax GCC produces puts them in reverse
      asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

      v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
      // seen in the GNU-Prolog sources

#if UNIT_BITS == 64
      if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
      if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
      if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
      if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
      if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
      if ((d & 0x8000000000000000LL) == 0) { v += 1; }
#elif UNIT_BITS == 32
      if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
      if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
      if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
      if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
      if ((d & 0x80000000) == 0) { v += 1; }
#else
#  error "don't know how to work with UNIT_BITS bits/unit"
#endif
#endif /* __i386__ || __x86_64__ */

      assert((domain->min & ~INVALID_BOUNDARY) <= v);

      domain->min = v;
    }

  return domain->min;
}

/* return and remove minimum value from DOMAIN */
int _fd_val_del_min(DOMAIN_REF_T(domain))
{
#if WORDS == 1
  long v = 0;

  assert(*domain->map != 0);

  if (domain->min & INVALID_BOUNDARY)
    {
      _fd_bitmap d;

      d = *domain->map;

#if __i386__ || __x86_64__
      long b;

#if __i386__ && UNIT_BITS == 64
      if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#endif

      asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

      v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
      // from GNU-Prolog

#if DOMAIN_BITS == 64
      if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
      if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
      if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
      if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
      if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
      if ((d & 0x8000000000000000LL) == 0) { v += 1;  d <<= 1; }
#elif DOMAIN_BITS == 32
      if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
      if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
      if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
      if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
      if ((d & 0x80000000) == 0) { v += 1;  d <<= 1; }
#else
#  error "don't know how to work with DOMAIN_BITS bits"
#endif
#endif /* __i386__ || __x86_64__ */

      *domain->map ^= MSBIT >> v;

      v += MIN_VALUE;
    }
  else
    {
      v = domain->min;

      *domain->map ^= MSBIT >> v - MIN_VALUE;
    }

  domain->min |= INVALID_BOUNDARY;
  if (domain->max == v)
    domain->max |= INVALID_BOUNDARY;

  return v;
#else /* WORDS == 1 */
#warning "_fd_val_del_min is _fd_val_min + _fd_val_del_val"
  int v = _fd_val_min(domain);

  _fd_val_del_val(v, domain);

  return v;
#endif /* WORDS == 1 */
}

/* return and remove maximum value from DOMAIN */
int _fd_val_del_max(DOMAIN_REF_T(domain))
{
#if WORDS == 1
  int v;

  assert(*domain->map != 0);

  if (domain->max & INVALID_BOUNDARY)
    {
      int b;

      b = ffs(*domain->map);

      *domain->map ^= LSBIT << (b - 1);

      v = DOMAIN_BITS - b + MIN_VALUE;;
    }
  else
    {
      v = domain->min;

      *domain->map ^= MSBIT >> v - MIN_VALUE;
    }

  domain->max |= INVALID_BOUNDARY;
  if (domain->min == v)
    domain->min |= INVALID_BOUNDARY;

  return v;
#else /* || WORDS == 1 */
#warning "_fd_val_del_max is _fd_val_max + _fd_val_del_val"
  int v = _fd_val_max(domain);

  _fd_val_del_val(v, domain);

  return v;
#endif /* WORDS == 1 */
}

int _fd_val_contains_val(fd_value domain, int value)
{
  if (value < (int) (domain->min & ~INVALID_BOUNDARY) ||
      value > (int) (domain->max & ~INVALID_BOUNDARY))
    return 0;

#if WORDS == 1
  return (*domain->map & MSBIT >> value) != 0;
#else /* WORDS == 1 */
  return (domain->map[value / UNIT_BITS] & MSBIT >> value % UNIT_BITS) != 0;
#endif /* WORDS == 1 */
}

// XXX: a variable can only be set to values in its domain
void _fd_val_set_value(DOMAIN_REF_T(domain), int value)
{
  assert(MIN_VALUE <= value && value <= MAX_VALUE);

#if WORDS == 1
  *domain->map = MSBIT >> value;
#else /* WORDS == 1 */
  memset(domain->map, 0, WORDS * sizeof(*domain->map));

  domain->map[value / UNIT_BITS] = MSBIT >> value % UNIT_BITS;
#endif /* WORDS == 1 */

  domain->min = domain->max = value;
}

/* remove all values greater than or equal to VALUE from DOMAIN */
int _fd_val_del_ge(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if WORDS == 1
  _fd_bitmap d;

  if (value > (int) (domain->max & ~INVALID_BOUNDARY))
    return 0;

  if (value <= (int) (domain->min & ~INVALID_BOUNDARY))
    {
      d = 0;
      domain->min |= INVALID_BOUNDARY;
    }
  else
    d = *domain->map & (ALL_ONES << DOMAIN_BITS - value);

  if (*domain->map == d)
    return 0;

  *domain->map = d;
  domain->max |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap *p, w;
  int changed = 0;
  int i;

  if (value > (int) (domain->max & ~INVALID_BOUNDARY))
    return 0;

  if (value <= (int) (domain->min & ~INVALID_BOUNDARY))
    {
      // domain becomes empty
      memset(domain->map, 0, WORDS * sizeof(*domain->map));
      domain->min |= INVALID_BOUNDARY;
      domain->max |= INVALID_BOUNDARY;

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = WORDS - 1, p = domain->map + i; i > value / UNIT_BITS && *p == 0; --i, --p)
    ;

  if (i > value / UNIT_BITS)
    {
      memset(domain->map + value / UNIT_BITS + 1, 0,
	     (i - value / UNIT_BITS) *sizeof(*domain->map));

      changed = 1;
    }

  w = domain->map[value / UNIT_BITS] &
        ((ALL_ONES << UNIT_BITS - value % UNIT_BITS - 1) << 1);
        // XXX: convoluted because of when value % UNIT_BITS == 0

  if (!changed && w == domain->map[value / UNIT_BITS])
    return 0;

  domain->map[value / UNIT_BITS] = w;
  domain->max |= INVALID_BOUNDARY;

  return 1;
#endif /* WORDS == 1 */
}

/* remove all values greater than VALUE from DOMAIN */
int _fd_val_del_gt(int value, DOMAIN_REF_T(domain))
{
#if WORDS == 1
  _fd_bitmap d;

#ifdef DEBUG_VALUE
  printf("remove {%d..} from ", value + 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (value >= (int) (domain->max & ~INVALID_BOUNDARY))
    return 0;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY))
    {
      d = 0;
      domain->min |= INVALID_BOUNDARY;
    }
  else
    d = *domain->map & -(MSBIT >> value);

  if (*domain->map == d)
    return 0;

  *domain->map = d;
  domain->max |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
#warning "_fd_val_del_gt is _fd_val_del_ge(+1)"
  return _fd_val_del_ge(value + 1, domain);
#endif /* WORDS == 1 */
}

/* remove all values less than or equal to VALUE from DOMAIN */
int _fd_val_del_le(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if WORDS == 1
  _fd_bitmap d;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY))
    return 0;

  if (value >= (int) (domain->max & ~INVALID_BOUNDARY))
    {
      d = 0;
      domain->max |= INVALID_BOUNDARY;
    }
  else
    d = *domain->map & (ALL_ONES >> value + 1);

  if (*domain->map == d)
    return 0;

  *domain->map = d;
  domain->min |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap *p, w;
  int changed = 0;
  int i;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY))
    return 0;

  if (value >= (int) (domain->max & ~INVALID_BOUNDARY))
    {
      // domain becomes empty
      memset(domain->map, 0, WORDS * sizeof(*domain->map));
      domain->min |= INVALID_BOUNDARY;
      domain->max |= INVALID_BOUNDARY;

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = 0, p = domain->map; i < value / UNIT_BITS && *p == 0; ++i, ++p)
    ;

  if (i < value / UNIT_BITS)
    {
      memset(domain->map + i, 0, (value / UNIT_BITS - i) *sizeof(*domain->map));

      changed = 1;
    }

  w = domain->map[value / UNIT_BITS] & (ALL_ONES >> value % UNIT_BITS >> 1);

  if (!changed && w == domain->map[value / UNIT_BITS])
    return 0;

  domain->map[value / UNIT_BITS] = w;
  domain->min |= INVALID_BOUNDARY;

  return 1;
#endif /* WORDS == 1 */
}

/* remove all values less than VALUE from DOMAIN */
int _fd_val_del_lt(int value, DOMAIN_REF_T(domain))
{
#if WORDS == 1
  _fd_bitmap d;

#ifdef DEBUG_VALUE
  printf("remove {..%d} from ", value - 1);
  _fd_val_print(domain);
  putchar('\n');
#endif

  if (value <= (int) (domain->min & ~INVALID_BOUNDARY))
    return 0;

  if (value > (int) (domain->max & ~INVALID_BOUNDARY))
    {
      d = 0;
      domain->max |= INVALID_BOUNDARY;
    }
  else
    d = *domain->map & (ALL_ONES >> value);

  if (*domain->map == d)
    return 0;

  *domain->map = d;
  domain->min |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
#warning "_fd_val_del_lt is _fd_val_del_le(-1)"
  return _fd_val_del_le(value - 1, domain);
#endif /* WORDS == 1 */
}

/* remove VALUE from DOMAIN */
int _fd_val_del_val(int value, DOMAIN_REF_T(domain))
{
#ifdef DEBUG_VALUE
  printf("remove {%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if WORDS == 1
  _fd_bitmap d;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY) ||
      value > (int) (domain->max & ~INVALID_BOUNDARY))
    return 0;

  d = *domain->map & ~ (MSBIT >> value);

  if (*domain->map == d)
    return 0;

  *domain->map = d;
  if (domain->min == value)
    domain->min |= INVALID_BOUNDARY;
  if (domain->max == value)
    domain->max |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap w;

  if (value > (int) (domain->max & ~INVALID_BOUNDARY) ||
      value < (int) (domain->min & ~INVALID_BOUNDARY))
    return 0;

  w = domain->map[value / UNIT_BITS] & ~ (MSBIT >> value % UNIT_BITS);

  if (domain->map[value / UNIT_BITS] == w)
    return 0;

  domain->map[value / UNIT_BITS] = w;
  if (domain->min == value)
    domain->min |= INVALID_BOUNDARY;
  if (domain->max == value)
    domain->max |= INVALID_BOUNDARY;

  return 1;
#endif /* WORDS == 1 */
}

/* remove every value other than VALUE from DOMAIN */
int _fd_val_del_other(DOMAIN_REF_T(domain), int value)
{
#ifdef DEBUG_VALUE
  printf("remove all but {%d} from ", value);
  _fd_val_print(domain);
  putchar('\n');
#endif

#if WORDS == 1
  _fd_bitmap d;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY) ||
      value > (int) (domain->max & ~INVALID_BOUNDARY))
    d = 0;
  else
    d = MSBIT >> value;

  if (*domain->map == d)
    return 0;

  *domain->map &= d;

  if (*domain->map)
    domain->min = domain->max = value;
  else
    {
      domain->min |= INVALID_BOUNDARY;
      domain->max |= INVALID_BOUNDARY;
    }

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap w;
  int other_values = 0;
  int i;

  if (value < (int) (domain->min & ~INVALID_BOUNDARY) ||
      value > (int) (domain->max & ~INVALID_BOUNDARY))
    {
      // domain becomes empty
      memset(domain->map, 0, WORDS * sizeof(*domain->map));
      domain->min |= INVALID_BOUNDARY;
      domain->max |= INVALID_BOUNDARY;

      // XXX: assume it wasn't already empty
      return 1;
    }

  for (i = 0; !other_values && i < value / UNIT_BITS; ++i)
    other_values = domain->map[i] != 0;

  for (i = i + 1; !other_values && i < WORDS; ++i)
    other_values = domain->map[i] != 0;

  w = domain->map[value / UNIT_BITS] & (MSBIT >> value % UNIT_BITS);

  other_values = other_values || domain->map[value / UNIT_BITS] != w;

  if (!other_values)
    return 0;

  memset(domain->map, 0, WORDS * sizeof(*domain->map));

  if (w)
    {
      domain->map[value / UNIT_BITS] = w;
      domain->min = domain->max = value;
    }
  else
    {
      domain->min |= INVALID_BOUNDARY;
      domain->max |= INVALID_BOUNDARY;
    }

  return 1;
#endif /* WORDS == 1 */
}

/* remove from DOMAIN1 all values not in DOMAIN2 */
int _fd_val_intersect(DOMAIN_REF_T(domain1), fd_value domain2)
{
#if WORDS == 1
  _fd_bitmap d = *domain1->map & *domain2->map;

  if (*domain1->map == d)
    return 0;

  *domain1->map = d;
  if (domain1->min != domain2->min)
    domain1->min |= INVALID_BOUNDARY;
  if (domain1->max != domain2->max)
    domain1->max |= INVALID_BOUNDARY;

  return 1;
#else /* WORDS == 1 */
  _fd_bitmap w;
  int changed = 0;
  int i;

  for (i = 0; i < WORDS; ++i)
    {
      w = domain1->map[i] & domain2->map[i];

      if (w != domain1->map[i])
	{
	  domain1->map[i] = w;
	  changed = 1;
	}
    }

  if (changed)
    {
      if (domain1->min != domain2->min)
	domain1->min |= INVALID_BOUNDARY;
      if (domain1->max != domain2->max)
	domain1->max |= INVALID_BOUNDARY;
    }

  return changed;
#endif /* WORDS == 1 */
}

/* create a clone of VALUE */
fd_value _fd_val_clone(fd_value value)
{
  fd_value new = malloc(sizeof(*new)); // XXX: NULL

  memcpy(new, value, sizeof(*new));

  return new;
}

/* copy FROM's value to TO */
void _fd_val_copy(DOMAIN_REF_T(to), fd_value from)
{
  memcpy(to, from, sizeof(*from));
}

int _fd_val_size(fd_value domain)
{
#if WORDS == 1
  return ones(*domain->map);
#else /* WORDS == 1 */
  _fd_bitmap w;
  int i, s;

  s = 0;
  for (i = 0; i < WORDS; ++i)
    s += ones(domain->map[i]);

  return s;
#endif /* WORDS == 1 */
}

void _fd_val_print(fd_value value)
{
#if WORDS == 1
  _fd_bitmap d = *value->map;
  int v;

  putchar('{');

  v = 0;
  while (d)
    {
      for (; d && (d & MSBIT) == 0; ++v, d <<= 1)
	;

      printf("%d", v);

      d <<= 1;
      v++;

      if (d & MSBIT)
	{
	  for (++v, d <<= 1; (d & MSBIT) != 0; ++v, d <<= 1)
	    ;

	  printf("..%d", v - 1);
	}

      if (d)
	printf(",");
    }

  putchar('}');
#else /* WORDS == 1 */
  _fd_bitmap w;
  int v, i;

  putchar('{');

  for (i = 0, w = value->map[i]; i < WORDS && w == 0; ++i, w = value->map[i])
    ;

  v = MIN_VALUE + i * UNIT_BITS;

  while (i < WORDS)
    {
      for (; w && (w & MSBIT) == 0; ++v, w <<= 1)
	;

      printf("%d", v);

      if (++v % UNIT_BITS == 0)
	if (++i < WORDS)
	  w = value->map[i];
	else
	  break;
      else
	w <<= 1;

      if (w & MSBIT)
	{
	  do
	    {
	      for (++v, w <<= 1; (w & MSBIT) != 0; ++v, w <<= 1)
		;
	    }
	  while (v % UNIT_BITS == 0 && ++i < WORDS && (w = value->map[i]));

	  printf("..%d", v - 1);
	}

      while (!w && ++i < WORDS)
	{
	  w = value->map[i];
	  v = MIN_VALUE + i * UNIT_BITS;
	}

      if (w)
	printf(",");
    }

  putchar('}');
#endif /* WORDS == 1 */
}

/* Iterate over a domain. */

fd_iterator _fd_val_iterator(fd_value domain)
{
  return _fd_val_clone(domain);
}

// XXX: this is just !_fd_val_empty()
int _fd_val_has_next(fd_iterator domain)
{
#if WORDS == 1
  return *domain->map != 0;
#else /* WORDS == 1 */
  int i;

  for (i = 0; i < WORDS; ++i)
    if (domain->map[i])
      return 1;

  return 0;
#endif /* WORDS == 1 */
}

int _fd_val_next_element(fd_iterator domain)
{
  _fd_bitmap d;
  long v = 0;

  // find the minimum value in the domain
#if WORDS == 1
  d = *domain->map;
#else
  _fd_bitmap *p;

  for (p = domain->map; *p == 0; ++p)
    v += UNIT_BITS;

  d = *p;
#endif /* WORDS == 1 */

#if __i386__ || __x86_64__
  long b;

#  if __i386__ && UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) != 0) { v -= 32; d >>= 32; }
#  endif

  asm("bsr %[map], %[bit]" : [bit] "=r" (b) : [map] "r" ((unsigned long) d));

  v += UNIT_BITS - b - 1;
#else /* __i386__ || __x86_64__ */
  // seen in the GNU-Prolog sources

#  if UNIT_BITS == 64
  if ((d & 0xffffffff00000000LL) == 0) { v += 32; d <<= 32; }
  if ((d & 0xffff000000000000LL) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff00000000000000LL) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf000000000000000LL) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc000000000000000LL) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x8000000000000000LL) == 0) { v += 1; }
#  elif UNIT_BITS == 32
  if ((d & 0xffff0000) == 0) { v += 16; d <<= 16; }
  if ((d & 0xff000000) == 0) { v += 8;  d <<= 8; }
  if ((d & 0xf0000000) == 0) { v += 4;  d <<= 4; }
  if ((d & 0xc0000000) == 0) { v += 2;  d <<= 2; }
  if ((d & 0x80000000) == 0) { v += 1; }
#  else
#    error "don't know how to work with UNIT_BITS bits/unit"
#  endif
#endif /* __i386__ || __x86_64__ */

  // delete the value found from the domain
#if WORDS == 1
  *domain->map ^= MSBIT >> v;
#else
  *p ^= MSBIT >> v % UNIT_BITS;
#endif

  return v + MIN_VALUE;
}

void _fd_val_iterator_dispose(fd_iterator domain)
{
  _fd_free_value(domain);
}

// SPLIT&GO

void _fd_val_split(DOMAIN_REF_T(src), DOMAIN_REF_T(remaining))
{
  int value = _fd_val_select(src);

  // XXX: done in _fd_start_saving_store()
  //memcpy(remaining, src, sizeof(*src));
  memset(src->map, 0, WORDS * sizeof(*src->map));

  src->map[value / UNIT_BITS] = MSBIT >> value % UNIT_BITS;
  remaining->map[value / UNIT_BITS] ^= MSBIT >> value % UNIT_BITS;

  if (value == src->min)
    remaining->min |= INVALID_BOUNDARY;

  if (value == src->max)
    remaining->max |= INVALID_BOUNDARY;

  src->min = src->max = value;
}

#endif /* DOMAIN_BOUNDS */