/*****************************************************************************\
 *  bitstring.c - bitmap manipulation functions
 *****************************************************************************
 *  See comments about origin, limitations, and internal structure in
 *  bitstring.h.
 *
 *  Copyright (C) 2002 The Regents of the University of California.
 *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
 *  Written by Jim Garlick <garlick@llnl.gov>, Morris Jette <jette1@llnl.gov>
 *  CODE-OCEC-09-009. All rights reserved.
 *
 *  This file is part of Slurm, a resource management program.
 *  For details, see <https://slurm.schedmd.com/>.
 *  Please also read the included file: DISCLAIMER.
 *
 *  Slurm is free software; you can redistribute it and/or modify it under
 *  the terms of the GNU General Public License as published by the Free
 *  Software Foundation; either version 2 of the License, or (at your option)
 *  any later version.
 *
 *  In addition, as a special exception, the copyright holders give permission
 *  to link the code of portions of this program with the OpenSSL library under
 *  certain conditions as described in each individual source file, and
 *  distribute linked combinations including the two. You must obey the GNU
 *  General Public License in all respects for all of the code used other than
 *  OpenSSL. If you modify file(s) with this exception, you may extend this
 *  exception to your version of the file(s), but you are not obligated to do
 *  so. If you do not wish to do so, delete this exception statement from your
 *  version.  If you delete this exception statement from all source files in
 *  the program, then also delete it here.
 *
 *  Slurm is distributed in the hope that it will be useful, but WITHOUT ANY
 *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 *  FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
 *  details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with Slurm; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA.
\*****************************************************************************/

#include "config.h"

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "src/common/bitstring.h"
#include "src/common/log.h"
#include "src/common/macros.h"
#include "src/common/xassert.h"
#include "src/common/xmalloc.h"
#include "src/common/xstring.h"

#define BITSTR_MAGIC 		0x42434445
#define BITSTR_MAXPOS		(BITSTR_WORD_SIZE - 1)
#define BITSTR_OVERHEAD 	2
#define BITSTR_SHIFT 		6
#define BITSTR_SHIFT_WORD8	3
#define BITSTR_SHIFT_WORD64	6
#define BITSTR_MAXVAL		0xffffffffffffffff
#define BITSTR_WORD_SIZE	(sizeof(bitstr_t) * 8)

/* word of the bitstring bit is in */
#define	_bit_word(bit) 		(((bit) >> BITSTR_SHIFT) + BITSTR_OVERHEAD)

/* address of the byte containing bit */
#define _bit_byteaddr(name, bit) \
	((char *)((name) + BITSTR_OVERHEAD) + ((bit) >> BITSTR_SHIFT_WORD8))

/* mask for the bit within its word */
#ifdef SLURM_BIGENDIAN
#define	_bit_mask(bit) ((bitstr_t)1 << (BITSTR_MAXPOS - ((bit)&BITSTR_MAXPOS)))
#else
#define	_bit_mask(bit) ((bitstr_t)1 << ((bit)&BITSTR_MAXPOS))
#endif

/* mask for less significant bits within their word*/
#ifdef SLURM_BIGENDIAN
#define _bit_nmask(n) \
	((~((bitstr_t) 0)) << ((BITSTR_MAXPOS + 1) - ((n) & BITSTR_MAXPOS)))
#else
#define _bit_nmask(n) \
	(((bitstr_t) 1 << ((n) & BITSTR_MAXPOS)) - 1)
#endif

/* number of bits actually allocated to a bitstr */
#define _bitstr_bits(name) 	((name)[1])

/* magic cookie stored here */
#define _bitstr_magic(name) 	((name)[0])

/* words in a bitstring of nbits bits */
#define	_bitstr_words(nbits)	\
	((((nbits) + BITSTR_MAXPOS) >> BITSTR_SHIFT) + BITSTR_OVERHEAD)

#undef bit_test
#define bit_test(name, bit) \
	((((name)[_bit_word(bit)]) & _bit_mask(bit)) ? 1 : 0)

/* check signature */
#define _assert_bitstr_valid(name) do { \
	xassert((name) != NULL); \
	xassert(_bitstr_magic(name) == BITSTR_MAGIC); \
} while (0)

/* check bit position */
#define _assert_bit_valid(name,bit) do { \
	xassert((bit) >= 0); \
	xassert((bit) < _bitstr_bits(name)); 	\
} while (0)


/* Ensure valid bitmap size, prevent overflow in buffer size calculation */
#define _assert_valid_size(bit) do {	\
	xassert((bit) > 0);		\
	xassert((bit) <= 0x40000000); 	\
} while (0)

/*
 * Define slurm-specific aliases for use by plugins, see slurm_xlator.h
 * for details.
 */
strong_alias(bit_alloc,		slurm_bit_alloc);
strong_alias(bit_set,		slurm_bit_set);
strong_alias(bit_clear,		slurm_bit_clear);
strong_alias(bit_nclear,	slurm_bit_nclear);
strong_alias(bit_nset,		slurm_bit_nset);
strong_alias(bit_set_all,	slurm_bit_set_all);
strong_alias(bit_clear_all,	slurm_bit_clear_all);
strong_alias(bit_ffc,		slurm_bit_ffc);
strong_alias(bit_ffs,		slurm_bit_ffs);
strong_alias(bit_size,		slurm_bit_size);
strong_alias(bit_and,		slurm_bit_and);
strong_alias(bit_not,		slurm_bit_not);
strong_alias(bit_or,		slurm_bit_or);
strong_alias(bit_set_count,	slurm_bit_set_count);
strong_alias(bit_set_count_range, slurm_bit_set_count_range);
strong_alias(bit_clear_count,	slurm_bit_clear_count);
strong_alias(bit_nset_max_count,slurm_bit_nset_max_count);
strong_alias(bit_rotate_copy,	slurm_bit_rotate_copy);
strong_alias(bit_rotate,	slurm_bit_rotate);
strong_alias(bit_fmt,		slurm_bit_fmt);
strong_alias(bit_fmt_full,	slurm_bit_fmt_full);
strong_alias(bit_unfmt,		slurm_bit_unfmt);
strong_alias(bitfmt2int,	slurm_bitfmt2int);
strong_alias(bit_fmt_hexmask,	slurm_bit_fmt_hexmask);
strong_alias(bit_fmt_hexmask_trim, slurm_bit_fmt_hexmask_trim);
strong_alias(bit_unfmt_hexmask,	slurm_bit_unfmt_hexmask);
strong_alias(bit_fls,		slurm_bit_fls);
strong_alias(bit_fls_from_bit,	slurm_bit_fls_from_bit);
strong_alias(bit_fill_gaps,	slurm_bit_fill_gaps);
strong_alias(bit_super_set,	slurm_bit_super_set);
strong_alias(bit_overlap,	slurm_bit_overlap);
strong_alias(bit_overlap_any,	slurm_bit_overlap_any);
strong_alias(bit_equal,		slurm_bit_equal);
strong_alias(bit_copy,		slurm_bit_copy);
strong_alias(bit_pick_cnt,	slurm_bit_pick_cnt);
strong_alias(bit_nffc,		slurm_bit_nffc);
strong_alias(bit_noc,		slurm_bit_noc);
strong_alias(bit_nffs,		slurm_bit_nffs);
strong_alias(bit_copybits,	slurm_bit_copybits);
strong_alias(bit_get_bit_num,	slurm_bit_get_bit_num);

#ifdef SLURM_BIGENDIAN
static const char* hexmask_lookup[256] = {
	"00",	"80",	"40",	"C0",	"20",	"A0",	"60",	"E0",
	"10",	"90",	"50",	"D0",	"30",	"B0",	"70",	"F0",
	"08",	"88",	"48",	"C8",	"28",	"A8",	"68",	"E8",
	"18",	"98",	"58",	"D8",	"38",	"B8",	"78",	"F8",
	"04",	"84",	"44",	"C4",	"24",	"A4",	"64",	"E4",
	"14",	"94",	"54",	"D4",	"34",	"B4",	"74",	"F4",
	"0C",	"8C",	"4C",	"CC",	"2C",	"AC",	"6C",	"EC",
	"1C",	"9C",	"5C",	"DC",	"3C",	"BC",	"7C",	"FC",
	"02",	"82",	"42",	"C2",	"22",	"A2",	"62",	"E2",
	"12",	"92",	"52",	"D2",	"32",	"B2",	"72",	"F2",
	"0A",	"8A",	"4A",	"CA",	"2A",	"AA",	"6A",	"EA",
	"1A",	"9A",	"5A",	"DA",	"3A",	"BA",	"7A",	"FA",
	"06",	"86",	"46",	"C6",	"26",	"A6",	"66",	"E6",
	"16",	"96",	"56",	"D6",	"36",	"B6",	"76",	"F6",
	"0E",	"8E",	"4E",	"CE",	"2E",	"AE",	"6E",	"EE",
	"1E",	"9E",	"5E",	"DE",	"3E",	"BE",	"7E",	"FE",
	"01",	"81",	"41",	"C1",	"21",	"A1",	"61",	"E1",
	"11",	"91",	"51",	"D1",	"31",	"B1",	"71",	"F1",
	"09",	"89",	"49",	"C9",	"29",	"A9",	"69",	"E9",
	"19",	"99",	"59",	"D9",	"39",	"B9",	"79",	"F9",
	"05",	"85",	"45",	"C5",	"25",	"A5",	"65",	"E5",
	"15",	"95",	"55",	"D5",	"35",	"B5",	"75",	"F5",
	"0D",	"8D",	"4D",	"CD",	"2D",	"AD",	"6D",	"ED",
	"1D",	"9D",	"5D",	"DD",	"3D",	"BD",	"7D",	"FD",
	"03",	"83",	"43",	"C3",	"23",	"A3",	"63",	"E3",
	"13",	"93",	"53",	"D3",	"33",	"B3",	"73",	"F3",
	"0B",	"8B",	"4B",	"CB",	"2B",	"AB",	"6B",	"EB",
	"1B",	"9B",	"5B",	"DB",	"3B",	"BB",	"7B",	"FB",
	"07",	"87",	"47",	"C7",	"27",	"A7",	"67",	"E7",
	"17",	"97",	"57",	"D7",	"37",	"B7",	"77",	"F7",
	"0F",	"8F",	"4F",	"CF",	"2F",	"AF",	"6F",	"EF",
	"1F",	"9F",	"5F",	"DF",	"3F",	"BF",	"7F",	"FF",
};
#else
static const char* hexmask_lookup[256] = {
	"00",	"01",	"02",	"03",	"04",	"05",	"06",	"07",
	"08",	"09",	"0A",	"0B",	"0C",	"0D",	"0E",	"0F",
	"10",	"11",	"12",	"13",	"14",	"15",	"16",	"17",
	"18",	"19",	"1A",	"1B",	"1C",	"1D",	"1E",	"1F",
	"20",	"21",	"22",	"23",	"24",	"25",	"26",	"27",
	"28",	"29",	"2A",	"2B",	"2C",	"2D",	"2E",	"2F",
	"30",	"31",	"32",	"33",	"34",	"35",	"36",	"37",
	"38",	"39",	"3A",	"3B",	"3C",	"3D",	"3E",	"3F",
	"40",	"41",	"42",	"43",	"44",	"45",	"46",	"47",
	"48",	"49",	"4A",	"4B",	"4C",	"4D",	"4E",	"4F",
	"50",	"51",	"52",	"53",	"54",	"55",	"56",	"57",
	"58",	"59",	"5A",	"5B",	"5C",	"5D",	"5E",	"5F",
	"60",	"61",	"62",	"63",	"64",	"65",	"66",	"67",
	"68",	"69",	"6A",	"6B",	"6C",	"6D",	"6E",	"6F",
	"70",	"71",	"72",	"73",	"74",	"75",	"76",	"77",
	"78",	"79",	"7A",	"7B",	"7C",	"7D",	"7E",	"7F",
	"80",	"81",	"82",	"83",	"84",	"85",	"86",	"87",
	"88",	"89",	"8A",	"8B",	"8C",	"8D",	"8E",	"8F",
	"90",	"91",	"92",	"93",	"94",	"95",	"96",	"97",
	"98",	"99",	"9A",	"9B",	"9C",	"9D",	"9E",	"9F",
	"A0",	"A1",	"A2",	"A3",	"A4",	"A5",	"A6",	"A7",
	"A8",	"A9",	"AA",	"AB",	"AC",	"AD",	"AE",	"AF",
	"B0",	"B1",	"B2",	"B3",	"B4",	"B5",	"B6",	"B7",
	"B8",	"B9",	"BA",	"BB",	"BC",	"BD",	"BE",	"BF",
	"C0",	"C1",	"C2",	"C3",	"C4",	"C5",	"C6",	"C7",
	"C8",	"C9",	"CA",	"CB",	"CC",	"CD",	"CE",	"CF",
	"D0",	"D1",	"D2",	"D3",	"D4",	"D5",	"D6",	"D7",
	"D8",	"D9",	"DA",	"DB",	"DC",	"DD",	"DE",	"DF",
	"E0",	"E1",	"E2",	"E3",	"E4",	"E5",	"E6",	"E7",
	"E8",	"E9",	"EA",	"EB",	"EC",	"ED",	"EE",	"EF",
	"F0",	"F1",	"F2",	"F3",	"F4",	"F5",	"F6",	"F7",
	"F8",	"F9",	"FA",	"FB",	"FC",	"FD",	"FE",	"FF",
};
#endif

/*
 * Implement a simple cache for a specific size of bitstring rather
 * than churning through xfree() + xmalloc() constantly.
 * This is intended for use with node_record_count in slurmctld, which
 * is constantly cycling through bitstrings of that size in the scheduler.
 */
static pthread_mutex_t cache_mutex = PTHREAD_MUTEX_INITIALIZER;
static void *cached_bitstr = NULL;
static bitoff_t cached_bitstr_len = 0;

static void *_cache_pop(void)
{
	void *b = NULL;

	slurm_mutex_lock(&cache_mutex);
	if (cached_bitstr) {
		b = cached_bitstr;
		cached_bitstr = *(void **) b;
	}
	slurm_mutex_unlock(&cache_mutex);

	return b;
}

static void _cache_push(void *b)
{
	slurm_mutex_lock(&cache_mutex);
	*(void **) b = cached_bitstr;
	cached_bitstr = b;
	slurm_mutex_unlock(&cache_mutex);
}

extern void bit_cache_init(bitoff_t nbits)
{
/*
 * Disable cache in MEMORY_LEAK_DEBUG as otherwise valgrind may attribute
 * any bitstring leaks that cycled through the cache to the original
 * allocation location, which is potentially completely unrelated to where
 * the leak is. The only downside is that a leak of the cache itself will
 * not be caught.
 */
#ifndef MEMORY_LEAK_DEBUG
	slurm_mutex_lock(&cache_mutex);
	if (cached_bitstr_len && (cached_bitstr_len != nbits))
		fatal_abort("%s: cannot change size once set", __func__);
	cached_bitstr_len = nbits;
	slurm_mutex_unlock(&cache_mutex);
#endif
}

extern void bit_cache_fini(void)
{
	void *b = NULL;
	while ((b = _cache_pop()))
		xfree(b);
}

/*
 * Allocate a bitstring.
 *   nbits (IN)		valid bits in new bitstring, initialized to all clear
 *   RETURN		new bitstring
 */
bitstr_t *bit_alloc(bitoff_t nbits)
{
	bitstr_t *new = NULL;

	_assert_valid_size(nbits);

	if (nbits == cached_bitstr_len)
		new = _cache_pop();

	if (new)
		memset(new, 0, _bitstr_words(nbits) * sizeof(bitstr_t));
	else
		new = xcalloc(_bitstr_words(nbits), sizeof(bitstr_t));

	_bitstr_magic(new) = BITSTR_MAGIC;
	_bitstr_bits(new) = nbits;

	return new;
}

static bitstr_t *bit_alloc_nz(bitoff_t nbits)
{
	bitstr_t *new = NULL;

	_assert_valid_size(nbits);

	if (nbits == cached_bitstr_len)
		new = _cache_pop();

	if (!new)
		new = xcalloc_nz(_bitstr_words(nbits), sizeof(bitstr_t));

	_bitstr_magic(new) = BITSTR_MAGIC;
	_bitstr_bits(new) = nbits;

	return new;
}

/*
 * Reallocate a bitstring (expand or contract size).
 *   b (IN)		pointer to old bitstring
 *   nbits (IN)		valid bits in new bitstr
 *   RETURN		new bitstring
 */
bitstr_t *slurm_bit_realloc(bitstr_t **b, bitoff_t nbits)
{
	_assert_bitstr_valid(*b);
	_assert_valid_size(nbits);

	xrecalloc(*b, _bitstr_words(nbits), sizeof(bitstr_t));

	_assert_bitstr_valid(*b);
	_bitstr_bits(*b) = nbits;

	return *b;
}

/*
 * Free a bitstr.
 *   b (IN/OUT)	bitstr to be freed
 */
void slurm_bit_free(bitstr_t **b)
{
	xassert(*b);
	xassert(_bitstr_magic(*b) == BITSTR_MAGIC);

	_bitstr_magic(*b) = 0;

	if (_bitstr_bits(*b) == cached_bitstr_len) {
		_cache_push(*b);
		*b = NULL;
	} else
		xfree(*b);
}

/*
 * Return the number of possible bits in a bitstring.
 *   b (IN)		bitstring to check
 *   RETURN		number of bits allocated
 */
bitoff_t
bit_size(bitstr_t *b)
{
	_assert_bitstr_valid(b);
	return _bitstr_bits(b);
}

/*
 * Is bit N of bitstring b set?
 *   b (IN)		bitstring to test
 *   bit (IN)		bit position to test
 *   RETURN		1 if bit set, 0 if clear
 */
int
slurm_bit_test(bitstr_t *b, bitoff_t bit)
{
	_assert_bitstr_valid(b);
	_assert_bit_valid(b, bit);
	return bit_test(b, bit);
}

/*
 * Set bit N of bitstring.
 *   b (IN)		target bitstring
 *   bit (IN)		bit position to set
 */
void
bit_set(bitstr_t *b, bitoff_t bit)
{
	_assert_bitstr_valid(b);
	_assert_bit_valid(b, bit);
	b[_bit_word(bit)] |= _bit_mask(bit);
}

/*
 * Clear bit N of bitstring
 *   b (IN)		target bitstring
 *   bit (IN)		bit position to clear
 */
void
bit_clear(bitstr_t *b, bitoff_t bit)
{
	_assert_bitstr_valid(b);
	_assert_bit_valid(b, bit);
	b[_bit_word(bit)] &= ~_bit_mask(bit);
}

/*
 * Set bits start ... stop in bitstring
 *   b (IN)		target bitstring
 *   start (IN)		starting (low numbered) bit position
 *   stop (IN)		ending (higher numbered) bit position
 */
void
bit_nset(bitstr_t *b, bitoff_t start, bitoff_t stop)
{
	_assert_bitstr_valid(b);
	_assert_bit_valid(b, start);
	_assert_bit_valid(b, stop);

	while (start <= stop && start % 8 > 0) 	     /* partial first byte? */
		bit_set(b, start++);
	while (stop >= start && (stop+1) % 8 > 0)    /* partial last byte? */
		bit_set(b, stop--);
	if (stop > start) {                          /* now do whole bytes */
		xassert((stop-start+1) % 8 == 0);
		memset(_bit_byteaddr(b, start), 0xff, (stop-start+1) / 8);
	}
}

/*
 * Clear bits start ... stop in bitstring
 *   b (IN)		target bitstring
 *   start (IN)		starting (low numbered) bit position
 *   stop (IN)		ending (higher numbered) bit position
 */
void
bit_nclear(bitstr_t *b, bitoff_t start, bitoff_t stop)
{
	_assert_bitstr_valid(b);
	_assert_bit_valid(b, start);
	_assert_bit_valid(b, stop);

	while (start <= stop && start % 8 > 0) 	/* partial first byte? */
		bit_clear(b, start++);
	while (stop >= start && (stop+1) % 8 > 0)/* partial last byte? */
		bit_clear(b, stop--);
	if (stop > start) {			/* now do whole bytes */
		xassert((stop-start+1) % 8 == 0);
		memset(_bit_byteaddr(b, start), 0, (stop-start+1) / 8);
	}
}

/*
 * Set all bits in bitstring
 *   b (IN)		target bitstring
 */
void
bit_set_all(bitstr_t *b)
{
	bit_nset(b, 0, bit_size(b)-1);
}

/*
 * Clear all bits in bitstring
 *   b (IN)		target bitstring
 */
void
bit_clear_all(bitstr_t *b)
{
	bit_nclear(b, 0, bit_size(b)-1);
}

/*
 * Find first bit clear in bitstring.
 *   b (IN)		bitstring to search
 *   nbits (IN)		number of bits to search
 *   RETURN      	resulting bit position (-1 if none found)
 */
bitoff_t
bit_ffc(bitstr_t *b)
{
	bitoff_t bit = 0, value = -1;

	_assert_bitstr_valid(b);

	while (bit < _bitstr_bits(b) && value == -1) {
		int32_t word = _bit_word(bit);

		if (b[word] == BITSTR_MAXVAL) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}
		while (bit < _bitstr_bits(b) && _bit_word(bit) == word) {
			if (!bit_test(b, bit)) {
				value = bit;
				break;
			}
			bit++;
		}
	}
	return value;
}

/* Find the first n contiguous bits clear in b.
 *   b (IN)             bitstring to search
 *   n (IN)             number of bits needed
 *   RETURN             position of first bit in range (-1 if none found)
 */
bitoff_t
bit_nffc(bitstr_t *b, int32_t n)
{
	bitoff_t value = -1;
	bitoff_t bit;
	int32_t cnt = 0;

	_assert_bitstr_valid(b);
	xassert(n > 0 && n < _bitstr_bits(b));

	for (bit = 0; bit < _bitstr_bits(b); bit++) {
		if (bit_test(b, bit)) {		/* fail */
			cnt = 0;
		} else {
			cnt++;
			if (cnt >= n) {
				value = bit - (cnt - 1);
				break;
			}
		}
	}

	return value;
}

/* Find n contiguous bits clear in b starting at some offset.
 *   b (IN)             bitstring to search
 *   n (IN)             number of bits needed
 *   seed (IN)          position at which to begin search
 *   RETURN             position of first bit in range (-1 if none found)
 */
bitoff_t
bit_noc(bitstr_t *b, int32_t n, int32_t seed)
{
	bitoff_t value = -1;
	bitoff_t bit;
	int32_t cnt = 0;

	_assert_bitstr_valid(b);
	xassert(n > 0 && n <= _bitstr_bits(b));

	if ((seed + n) >= _bitstr_bits(b))
		seed = _bitstr_bits(b);	/* skip offset test, too small */

	for (bit = seed; bit < _bitstr_bits(b); bit++) {	/* start at offset */
		if (bit_test(b, bit)) {		/* fail */
			cnt = 0;
		} else {
			cnt++;
			if (cnt >= n) {
				value = bit - (cnt - 1);
				return value;
			}
		}
	}

	cnt = 0;	/* start at beginning */
	for (bit = 0; bit < _bitstr_bits(b); bit++) {
		if (bit_test(b, bit)) {		/* fail */
			if (bit >= seed)
				break;
			cnt = 0;
		} else {
			cnt++;
			if (cnt >= n) {
				value = bit - (cnt - 1);
				return value;
			}
		}
	}

	return -1;
}

/* Find the first n contiguous bits set in b.
 *   b (IN)             bitstring to search
 *   n (IN)             number of bits needed
 *   RETURN             position of first bit in range (-1 if none found)
 */
bitoff_t
bit_nffs(bitstr_t *b, int32_t n)
{
	bitoff_t value = -1;
	bitoff_t bit;
	int32_t cnt = 0;

	_assert_bitstr_valid(b);
	xassert(n > 0 && n <= _bitstr_bits(b));

	for (bit = 0; bit <= _bitstr_bits(b) - n; bit++) {
		if (!bit_test(b, bit)) {	/* fail */
			cnt = 0;
		} else {
			cnt++;
			if (cnt >= n) {
				value = bit - (cnt - 1);
				break;
			}
		}
	}

	return value;
}

/*
 * Find first bit set in b from an offset.
 *   b (IN)		bitstring to search
 *   bit (IN)		bit to start the search at
 *   RETURN		resulting bit position (-1 if none found)
 */
bitoff_t bit_ffs_from_bit(bitstr_t *b, bitoff_t bit)
{
	bitoff_t value = -1;
	int32_t word;
#if (HAVE___BUILTIN_CLZLL && (defined SLURM_BIGENDIAN)) || \
    (HAVE___BUILTIN_CTZLL && (!defined SLURM_BIGENDIAN))
	bitstr_t bitstr_word;

	_assert_bitstr_valid(b);
	if ((bit % BITSTR_WORD_SIZE) && (bit < _bitstr_bits(b))) {
		bitstr_t mask = ~_bit_nmask(bit);
		bit -= (bit % BITSTR_WORD_SIZE);
		word = _bit_word(bit);
		bitstr_word = b[word] & mask;
		goto test_word;
	}

	while ((bit < _bitstr_bits(b)) && (value == -1)) {

		word = _bit_word(bit);
		bitstr_word = b[word];
test_word:
		if (bitstr_word == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}
#if HAVE___BUILTIN_CLZLL && (defined SLURM_BIGENDIAN)
		value = bit + __builtin_clzll(bitstr_word);
#elif HAVE___BUILTIN_CTZLL && (!defined SLURM_BIGENDIAN)
		value = bit + __builtin_ctzll(bitstr_word);
#endif
	}

	if (value < _bitstr_bits(b))
		return value;
	else
		return -1;
#else
	_assert_bitstr_valid(b);
	if ((bit % BITSTR_WORD_SIZE) && (bit < _bitstr_bits(b)) &&
	    (b[_bit_word(bit)] == 0)) {
		bit += BITSTR_WORD_SIZE;
		bit -= (bit % BITSTR_WORD_SIZE);
	}
	while ((bit < _bitstr_bits(b)) && (value == -1)) {
		word = _bit_word(bit);
		if (b[word] == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}
		while (bit < _bitstr_bits(b) && _bit_word(bit) == word) {
			if (bit_test(b, bit)) {
				value = bit;
				break;
			}
			bit++;
		}
	}
	return value;
#endif
}

/*
 * Find first bit set in b.
 *   b (IN)		bitstring to search
 *   RETURN 		resulting bit position (-1 if none found)
 */
bitoff_t bit_ffs(bitstr_t *b)
{
	return bit_ffs_from_bit(b, 0);
}

/*
 * Find last bit set in b.
 *   b (IN)		bitstring to search
 *   RETURN 		resulting bit position (-1 if none found)
 */
bitoff_t bit_fls(bitstr_t *b)
{
	/* zero origin */
	bitoff_t bit = _bitstr_bits(b) - 1;

	return bit_fls_from_bit(b, bit);
}

/*
 * Find last bit set in b from an offset.
 *   b (IN)		bitstring to search
 *   bit (IN)		bit to start the search at
 *   RETURN		resulting bit position (-1 if none found)
 */
bitoff_t bit_fls_from_bit(bitstr_t *b, bitoff_t bit)
{
	bitoff_t value = -1;
	int32_t word;

	_assert_bitstr_valid(b);
	_assert_bit_valid(b, bit);

	if (_bitstr_bits(b) == 0)	/* empty bitstring */
		return -1;

	while (bit >= 0 && 		/* test partial words */
		(_bit_word(bit) == _bit_word(bit + 1))) {
		if (bit_test(b, bit)) {
			value = bit;
			break;
		}
		bit--;
	}
	while (bit >= 0 && value == -1) {	/* test whole words */
		word = _bit_word(bit);
		if (b[word] == 0) {
			bit -= BITSTR_WORD_SIZE;
			continue;
		}
#if HAVE___BUILTIN_CTZLL && (defined SLURM_BIGENDIAN)
		value = bit - __builtin_ctzll(b[word]);
#elif HAVE___BUILTIN_CLZLL && (!defined SLURM_BIGENDIAN)
		value = bit - __builtin_clzll(b[word]);
#else
		while (bit >= 0) {
			if (bit_test(b, bit)) {
				value = bit;
				break;
			}
			bit--;
		}
#endif
	}
	return value;
}

/*
 * set all bits between the first and last bits set (i.e. fill in the gaps
 *	to make set bits contiguous)
 */
void
bit_fill_gaps(bitstr_t *b)
{
	bitoff_t first, last;

	_assert_bitstr_valid(b);

	first = bit_ffs(b);
	if (first == -1)
		return;

	last = bit_fls(b);
	bit_nset(b, first, last);

	return;
}

/*
 * return 1 if all bits set in b1 are also set in b2, 0 otherwise
 */
int
bit_super_set(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);
	xassert(_bitstr_bits(b1) == _bitstr_bits(b2));

	for (bit = 0; bit < _bitstr_bits(b1); bit += BITSTR_WORD_SIZE) {
		if (b1[_bit_word(bit)] != (b1[_bit_word(bit)] &
		                           b2[_bit_word(bit)])) {
			bitstr_t mask;
			if ((bit + BITSTR_WORD_SIZE) <= _bitstr_bits(b1))
				return 0;
			mask = _bit_nmask(_bitstr_bits(b1));
			if ((b1[_bit_word(bit)] & mask) != (b1[_bit_word(bit)] &
							    b2[_bit_word(bit)] &
							    mask))
				return 0;
		}

	}

	return 1;
}

/*
 * return 1 if b1 and b2 are identical, 0 otherwise
 */
extern int
bit_equal(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);

	if (_bitstr_bits(b1) != _bitstr_bits(b2))
		return 0;

	bit_cnt = _bitstr_bits(b1);

	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE) {
		if (b1[_bit_word(bit)] != b2[_bit_word(bit)])
			return 0;
	}
	if (bit < bit_cnt) {
		uint64_t mask = _bit_nmask(bit_cnt);
		if ((b1[_bit_word(bit)] ^ b2[_bit_word(bit)]) & mask)
			return 0;
	}

	return 1;
}


/*
 * b1 &= b2 as many bits as both bitstr_t have
 *   b1 (IN/OUT)	first string
 *   b2 (IN)		second bitstring
 */
void
bit_and(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);

	bit_cnt = MIN(_bitstr_bits(b1), _bitstr_bits(b2));
	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE)
		b1[_bit_word(bit)] &= b2[_bit_word(bit)];

	if (bit < bit_cnt) {
		uint64_t mask = ~(_bit_nmask(bit_cnt));
		b1[_bit_word(bit)] &= (b2[_bit_word(bit)] | mask);
	}
}

/*
 * b1 &= ~b2 as many bits as both bitstr_t have
 * b1 (IN/OUT)
 * b2 (IN)
 */
void bit_and_not(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);

	bit_cnt = MIN(_bitstr_bits(b1), _bitstr_bits(b2));
	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE)
		b1[_bit_word(bit)] &= ~b2[_bit_word(bit)];

	if (bit < bit_cnt) {
		uint64_t mask = _bit_nmask(bit_cnt);
		b1[_bit_word(bit)] &= ~(b2[_bit_word(bit)] & mask);
	}
}

/*
 * b1 = ~b1		one's complement
 *   b1 (IN/OUT)	first bitmap
 */
void
bit_not(bitstr_t *b)
{
	bitoff_t bit;

	_assert_bitstr_valid(b);

	for (bit = 0; bit < _bitstr_bits(b); bit += BITSTR_WORD_SIZE)
		b[_bit_word(bit)] = ~b[_bit_word(bit)];
}

/*
 * b1 |= b2 as many bits as both bitstr_t have
 *   b1 (IN/OUT)	first bitmap
 *   b2 (IN)		second bitmap
 */
void
bit_or(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);

	bit_cnt = MIN(_bitstr_bits(b1), _bitstr_bits(b2));
	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE)
		b1[_bit_word(bit)] |= b2[_bit_word(bit)];

	if (bit < bit_cnt) {
		uint64_t mask = _bit_nmask(bit_cnt);
		b1[_bit_word(bit)] |= (b2[_bit_word(bit)] & mask);
	}
}

/*
 * b1 |= ~b2 as many bits as both bitstr_t have
 * b1 (IN/OUT)
 * b2 (IN)
 */
void bit_or_not(bitstr_t *b1, bitstr_t *b2)
{
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);

	bit_cnt = MIN(_bitstr_bits(b1), _bitstr_bits(b2));
	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE)
		b1[_bit_word(bit)] |= ~b2[_bit_word(bit)];

	if (bit < bit_cnt) {
		uint64_t mask = ~(_bit_nmask(bit_cnt));
		b1[_bit_word(bit)] |= ~(b2[_bit_word(bit)] | mask);
	}
}

/*
 * return a copy of the supplied bitmap
 */
bitstr_t *
bit_copy(bitstr_t *b)
{
	bitstr_t *new;
	int32_t newsize_bits;
	size_t len = 0;  /* Number of bytes to memcpy() */

	_assert_bitstr_valid(b);

	newsize_bits  = bit_size(b);
	len = (_bitstr_words(newsize_bits) - BITSTR_OVERHEAD)*sizeof(bitstr_t);
	new = bit_alloc_nz(newsize_bits);
	memcpy(&new[BITSTR_OVERHEAD], &b[BITSTR_OVERHEAD], len);

	return new;
}

void
bit_copybits(bitstr_t *dest, bitstr_t *src)
{
	int32_t len;

	_assert_bitstr_valid(dest);
	_assert_bitstr_valid(src);
	xassert(bit_size(src) == bit_size(dest));

	len = (_bitstr_words(bit_size(src)) - BITSTR_OVERHEAD)*sizeof(bitstr_t);
	memcpy(&dest[BITSTR_OVERHEAD], &src[BITSTR_OVERHEAD], len);
}

#ifdef HAVE___BUILTIN_POPCOUNTLL
#define hweight __builtin_popcountll
#else
/*
 * Returns the hamming weight (i.e. the number of bits set) in a word.
 * NOTE: This routine borrowed from Linux 4.9 <tools/lib/hweight.c>.
 */
static uint64_t
hweight(uint64_t w)
{
        w -= (w >> 1) & 0x5555555555555555ul;
        w =  (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
        w =  (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
        return (w * 0x0101010101010101ul) >> 56;
}
#endif

/*
 * Count the number of bits set in bitstring.
 *   b (IN)		bitstring to check
 *   RETURN		count of set bits
 */
int32_t
bit_set_count(bitstr_t *b)
{
	int32_t count = 0;
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b);

	bit_cnt = _bitstr_bits(b);
	for (bit = 0; (bit + BITSTR_WORD_SIZE) <= bit_cnt;
	     bit += BITSTR_WORD_SIZE) {
		count += hweight(b[_bit_word(bit)]);
	}
	if (bit < bit_cnt) {
		uint64_t mask = _bit_nmask(bit_cnt);
		count += hweight(b[_bit_word(bit)] & mask);
	}
	return count;
}

/*
 * Count the number of bits set in a range of bitstring.
 *   b (IN)		bitstring to check
 *   start (IN) first bit to check
 *   end (IN)	last bit to check+1
 *   RETURN		count of set bits
 */
int32_t
bit_set_count_range(bitstr_t *b, int32_t start, int32_t end)
{
	int32_t count = 0, eow;
	bitoff_t bit;

	_assert_bitstr_valid(b);
	_assert_bit_valid(b,start);

	end = MIN(end, _bitstr_bits(b));
	/* end of word */
	eow = (((start + BITSTR_MAXPOS) >> BITSTR_SHIFT) << BITSTR_SHIFT);

	bit = start;
	if ((start < eow) && (eow <= end)) {
		uint64_t mask = ~_bit_nmask(start);
		count += hweight(b[_bit_word(bit)] & mask);
		bit = eow;
	} else if (eow > start) {
		uint64_t mask = ~_bit_nmask(start);
		mask &= _bit_nmask(end);
		count += hweight(b[_bit_word(bit)] & mask);
		bit = eow;
	}
	for (; (bit + BITSTR_WORD_SIZE) <= end ; bit += BITSTR_WORD_SIZE) {
		count += hweight(b[_bit_word(bit)]);
	}
	if (bit < end) {
		uint64_t mask = _bit_nmask(end);
		count += hweight(b[_bit_word(bit)] & mask);
	}

	return count;
}

static int32_t _bit_overlap_internal(bitstr_t *b1, bitstr_t *b2, bool count_it)
{
	int32_t count = 0;
	int64_t anded;
	bitoff_t bit, bit_cnt;

	_assert_bitstr_valid(b1);
	_assert_bitstr_valid(b2);
	xassert(_bitstr_bits(b1) == _bitstr_bits(b2));

	bit_cnt = _bitstr_bits(b1);
	for (bit = 0; bit < bit_cnt; bit += BITSTR_WORD_SIZE) {
		if ((bit + BITSTR_WORD_SIZE - 1) >= bit_cnt)
			break;
		anded = b1[_bit_word(bit)] & b2[_bit_word(bit)];
		if (count_it)
			count += hweight(anded);
		else if (anded)
			return 1;
	}

	if (bit < bit_cnt) {
		uint64_t mask = _bit_nmask(bit_cnt);
		anded = b1[_bit_word(bit)] & b2[_bit_word(bit)] & mask;
		if (count_it)
			count += hweight(anded);
		else if (anded)
			return 1;
	}

	return count;
}

/*
 * return number of bits set in b1 that are also set in b2, 0 if no overlap
 */
extern int32_t bit_overlap(bitstr_t *b1, bitstr_t *b2)
{
	return _bit_overlap_internal(b1, b2, 1);
}

/*
 * return 1 if there is at least one bit set in b1 that is also set in b2, 0 if
 * no overlap
 */
extern int32_t bit_overlap_any(bitstr_t *b1, bitstr_t *b2)
{
	return _bit_overlap_internal(b1, b2, 0);
}

/*
 * Count the number of bits clear in bitstring.
 *   b (IN)		bitstring to check
 *   RETURN		count of clear bits
 */
int32_t
bit_clear_count(bitstr_t *b)
{
	_assert_bitstr_valid(b);
	return (_bitstr_bits(b) - bit_set_count(b));
}

/* Return the count of the largest number of contiguous bits set in b.
 *   b (IN)             bitstring to search
 *   RETURN             the largest number of contiguous bits set in b
 */
int32_t
bit_nset_max_count(bitstr_t *b)
{
	bitoff_t bit;
	int32_t  cnt = 0;
	int32_t  maxcnt = 0;
	uint32_t bitsize;

	_assert_bitstr_valid(b);
	bitsize = _bitstr_bits(b);

	for (bit = 0; bit < bitsize; bit++) {
		if (!bit_test(b, bit)) {	/* no longer continuous */
			cnt = 0;
		} else {
			cnt++;
			if (cnt > maxcnt) {
				maxcnt = cnt;
			}
		}
		if (cnt == 0 && ((bitsize - bit) < maxcnt)) {
		    	break;			/* already found max */
		}
	}

	return maxcnt;
}

/*
 * rotate b1 by n bits returning a rotated copy
 *   b1 (IN)		bitmap to rotate
 *   n  (IN)		rotation distance (+ = rotate left, - = rotate right)
 *   nbits (IN)		size of the new copy (in which the rotation occurs)
 *				note: nbits must be >= bit_size(b1)
 *   RETURN		new rotated bitmap
 */
bitstr_t *
bit_rotate_copy(bitstr_t *b1, int32_t n, bitoff_t nbits)
{
	bitoff_t bit, dst;
	bitstr_t *new;
	bitoff_t bitsize;
	bitoff_t deltasize, wrapbits;

	_assert_bitstr_valid(b1);
	bitsize = bit_size(b1);
	xassert(nbits >= bitsize);
	deltasize = nbits - bitsize;

	/* normalize n to a single positive rotation */
	n = n % nbits;
	if (n < 0) {
		n += nbits;
	}

	wrapbits = 0;	/* number of bits that will wrap around */
	if (n > deltasize) {
		wrapbits = n - deltasize;
	}

	new = bit_alloc(nbits);

	/* bits shifting up */
	for (bit = 0; bit < (bitsize-wrapbits); bit++) {
		if (bit_test(b1, bit))
			bit_set(new, bit+n);
	}
	/* continue bit into wrap-around bits, if any */
	for (dst = 0; bit < bitsize; bit++, dst++) {
		if (bit_test(b1, bit))
			bit_set(new, dst);
	}
	return(new);
}

/*
 * rotate b1 by n bits
 *   b1 (IN/OUT)	bitmap to rotate
 *   n  (IN)		rotation distance (+ = rotate left, - = rotate right)
 */
void
bit_rotate(bitstr_t *b1, int32_t n)
{
	uint32_t bitsize;
	bitstr_t *new;

	if (n == 0)
		return;

	_assert_bitstr_valid(b1);
	bitsize = bit_size(b1);

	new = bit_rotate_copy(b1, n, bitsize);
	bit_copybits(b1, new);
	FREE_NULL_BITMAP(new);
}

/*
 * find first set n
 * return position of nth set bit in bitstr word
 * minimal validity checking: if n > set_count, return 63
 * if n == 0, return 0
 */
static bitoff_t _ffsn(bitstr_t b, bitoff_t n)
{
	uint64_t mask = 0xFFFFFFFFu;
	uint32_t size = 32u;
	bitstr_t base = 0u;

	while (size > 0) {
		if (n > hweight(b & mask)) {
			base += size;
			size >>= 1;
			mask |= mask << size;
		} else {
			size >>= 1;
			mask >>= size;
		}
	}
	return base;
}

/*
 * return the bit position of the nth set bit
 * if n > bit_set_count(b), return the position of the last set bit
 * return -1 if b is empty or n == 0
 */
bitoff_t bit_nth_set(bitstr_t *b, bitoff_t n)
{
	bitoff_t bit, bit_cnt, last_bit;
	bitstr_t mask = -1;
	bitstr_t last_mask = -1;
	uint32_t count, last_count, last_word;

	_assert_bitstr_valid(b);
	if (n <= 0)
		return -1;
	bit_cnt = _bitstr_bits(b);
	last_word = _bit_word(bit_cnt);

	last_bit = -1;
	for (bit = 0; bit < bit_cnt; bit += BITSTR_WORD_SIZE){
		if (_bit_word(bit) == last_word)
			mask = _bit_nmask(bit_cnt);
		count = hweight(b[_bit_word(bit)] & mask);
		if (count > 0){
			last_bit = bit;
			last_count = count;
		}
		if (n <= count)
			break;
		n -= count;
	}

	/* b has no set bits */
	if (last_bit < 0)
		return -1;
	if (_bit_word(last_bit) == last_word)
		last_mask = _bit_nmask(bit_cnt);

	/*
	 * if last_bit != bit, n > set_count.
	 * find position of last bit in last non-empty word
	 */
	return last_bit + _ffsn(b[_bit_word(last_bit)] & last_mask,
	                        (last_bit == bit) ? n : last_count);
}

/*
 * Clear all bits after the first n set bits
 */
void bit_pick_firstn(bitstr_t *b, bitoff_t n)
{
	_assert_bitstr_valid(b);
	bitoff_t nth_bit = bit_nth_set(b, n);
	/*
	 * b is empty or nth bit is at the last position.
	 * Nothing to do in either case
	 */
	if (((nth_bit + 1) == _bitstr_bits(b)) || (nth_bit < 0))
		return;
	bit_nclear(b, nth_bit + 1, _bitstr_bits(b) - 1);
}

/*
 * build a bitmap containing the first nbits of b which are set
 */
bitstr_t *
bit_pick_cnt(bitstr_t *b, bitoff_t nbits)
{
	bitoff_t bit = 0, new_bits, count = 0;
	bitstr_t *new;

	_assert_bitstr_valid(b);

	if (_bitstr_bits(b) < nbits)
		return NULL;

	new = bit_alloc(bit_size(b));

	while ((bit < _bitstr_bits(b)) && (count < nbits)) {
		int32_t word = _bit_word(bit);

		if (b[word] == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}

		new_bits = hweight(b[word]);
		if (((count + new_bits) <= nbits) &&
		    ((bit + BITSTR_WORD_SIZE - 1) < _bitstr_bits(b))) {
			new[word] = b[word];
			count += new_bits;
			bit += BITSTR_WORD_SIZE;
			continue;
		}
		while ((bit < _bitstr_bits(b)) && (count < nbits)) {
			if (bit_test(b, bit)) {
				bit_set(new, bit);
				count++;
			}
			bit++;
		}
	}
	if (count < nbits) {
		FREE_NULL_BITMAP(new);
	}

	return new;
}

/*
 * Convert to range string format, e.g. 0-5,42
 */
char *bit_fmt(char *str, int32_t len, bitstr_t *b)
{
	int32_t word;
	char *comma = "";
	bitoff_t bit;

	_assert_bitstr_valid(b);
	xassert(len > 0);
	*str = '\0';
	for (bit = 0; bit < _bitstr_bits(b); ) {
		word = _bit_word(bit);
		if (b[word] == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}

		if (bit_test(b, bit)) {
			int32_t ret, size;
			bitoff_t start = bit;

			while (bit+1 < _bitstr_bits(b) && bit_test(b, bit+1)) {
				bit++;
			}
			size = strlen(str);
			if (bit == start) {	/* add single bit position */
				ret = snprintf(str + size, len - size,
				               "%s%"BITSTR_FMT"", comma, start);
			} else { 		/* add bit position range */
				ret = snprintf(str + size, len - size,
				               "%s%"BITSTR_FMT"-%"BITSTR_FMT"",
					       comma, start, bit);
			}
			comma = ",";

			xassert(ret != -1);
			if (ret == -1)
				error("failed to write to string -- this should never happen");
		}
		bit++;
	}
	return str;
}

/*
 * Convert to range string format, e.g. 0-5,42 with no length restriction
 * Call xfree() on return value to avoid memory leak
 */
char *bit_fmt_full(bitstr_t *b)
{
	int32_t word;
	bitoff_t start, bit;
	char *str = NULL, *pos = NULL, *comma = "";
	_assert_bitstr_valid(b);

	for (bit = 0; bit < _bitstr_bits(b); ) {
		word = _bit_word(bit);
		if (b[word] == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}

		if (bit_test(b, bit)) {
			start = bit;
			while (bit+1 < _bitstr_bits(b) && bit_test(b, bit+1)) {
				bit++;
			}
			if (bit == start)	/* add single bit position */
				xstrfmtcatat(str, &pos, "%s%"BITSTR_FMT"",
					     comma, start);
			else 			/* add bit position range */
				xstrfmtcatat(str, &pos,
					     "%s%"BITSTR_FMT"-%"BITSTR_FMT,
					     comma, start, bit);
			comma = ",";
		}
		bit++;
	}

	return str;
}

/*
 * Convert to range string format, e.g. 0-5,42 with no length restriction
 * offset IN - location of bit zero
 * len IN - number of bits to test
 * Call xfree() on return value to avoid memory leak
 */
char *bit_fmt_range(bitstr_t *b, int offset, int len)
{
	int32_t word;
	bitoff_t start, fini_bit, bit;
	char *str = NULL, *pos = NULL, *comma = "";
	_assert_bitstr_valid(b);

	fini_bit = MIN(_bitstr_bits(b), offset + len);
	for (bit = offset; bit < fini_bit; ) {
		word = _bit_word(bit);
		if (b[word] == 0) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}

		if (bit_test(b, bit)) {
			start = bit;
			while ((bit + 1 < fini_bit) && bit_test(b, bit + 1)) {
				bit++;
			}
			if (bit == start) {	/* add single bit position */
				xstrfmtcatat(str, &pos, "%s%"BITSTR_FMT"",
					     comma, (start - offset));
			} else {		/* add bit position range */
				xstrfmtcatat(str, &pos,
					     "%s%"BITSTR_FMT"-%"BITSTR_FMT,
					     comma, (start - offset),
					     (bit - offset));
			}
			comma = ",";
		}
		bit++;
	}

	return str;
}

/*
 * Convert range string format, e.g. "0-5,42" to bitmap
 * Ret 0 on success, -1 on error
 */
extern int bit_unfmt(bitstr_t *b, const char *str)
{
	int32_t *intvec;
	int rc = 0;

	_assert_bitstr_valid(b);
	if (!str || str[0] == '\0')	/* no bits set */
		return rc;
	intvec = bitfmt2int(str);
	if (intvec == NULL)
		return -1;
	rc = inx2bitstr(b, intvec);
	xfree(intvec);
	return rc;
}

/*
 * bitfmt2int - convert a string describing bitmap (output from bit_fmt,
 *	e.g. "0-30,45,50-60") into an array of integer (start/end) pairs
 *	terminated by -1 (e.g. "0, 30, 45, 45, 50, 60, -1")
 *	Also supports the "1-17:4" step format ("1, 5, 9, 13, 17, -1").
 * input: bitmap string as produced by bitstring.c : bitfmt
 * output: an array of integers
 * NOTE: the caller must xfree the returned memory
 */
extern int32_t *bitfmt2int(const char *bit_str_ptr)
{
	int32_t *bit_int_ptr, i, bit_inx, size, sum, start_val;
	char *tmp = NULL;
	int32_t start_task_id = -1;
	int32_t end_task_id = -1;
	int32_t step = -1;

	if (bit_str_ptr == NULL)
		return NULL;
	if (!(xstrchr(bit_str_ptr, ':'))) {
		size = strlen(bit_str_ptr) + 1;
		/* more than enough space */
		bit_int_ptr = xmalloc(sizeof(int32_t) * (size * 2 + 1));
		bit_inx = sum = 0;
		start_val = -1;
		for (i = 0; i < size; i++) {
			if (bit_str_ptr[i] >= '0' &&
			    bit_str_ptr[i] <= '9') {
				sum = (sum * 10) + (bit_str_ptr[i] - '0');
			} else if (bit_str_ptr[i] == '-') {
				start_val = sum;
				sum = 0;
			} else if (bit_str_ptr[i] == ',' ||
				   bit_str_ptr[i] == '\0') {
				if (i == 0)
					break;
				if (start_val == -1)
					start_val = sum;
				bit_int_ptr[bit_inx++] = start_val;
				bit_int_ptr[bit_inx++] = sum;
				start_val = -1;
				sum = 0;
			}
		}
		xassert(bit_inx < (size * 2 + 1));
	} else {	/* handle step format */
		start_task_id = strtol(bit_str_ptr, &tmp, 10);
		if (*tmp != '-')
			return NULL;
		end_task_id = strtol(tmp + 1, &tmp, 10);
		if (*tmp != ':')
			return NULL;
		step = strtol(tmp + 1, &tmp, 10);
		if (*tmp != '\0')
			return NULL;
		if (end_task_id < start_task_id || step <= 0)
			return NULL;

		size = ((end_task_id - start_task_id) / step) + 1;
		bit_int_ptr = xmalloc(sizeof(int32_t) * (size * 2 + 1));
		bit_inx = 0;
		for(i = start_task_id; i < end_task_id; i += step) {
			bit_int_ptr[bit_inx++] = i;     /* start of pair */
			bit_int_ptr[bit_inx++] = i;     /* end of pair */
		}
	}
	bit_int_ptr[bit_inx] = -1;
	return bit_int_ptr;
}

int inx2bitstr(bitstr_t *b, int32_t *inx)
{
	int32_t *p, bit_cnt;
	int rc = 0;

	xassert(b);
	xassert(inx);

	bit_cnt = _bitstr_bits(b);
	if (bit_cnt > 0)
		bit_nclear(b, 0, bit_cnt - 1);
	for (p = inx; *p != -1; p += 2) {
		if ((*p < 0) || (*p >= bit_cnt) ||
		    (*(p + 1) < 0) || (*(p + 1) >= bit_cnt)) {
			rc = -1;
			break;
		}
		bit_nset(b, *p, *(p + 1));
	}
	return rc;
}

/*
 * convert a bitstring to inx format
 * returns an xmalloc()'d array of int32_t that must be xfree()'d
 */
int32_t *bitstr2inx(bitstr_t *b)
{
	bitoff_t start, bit, pos = 0;
	int32_t *bit_inx;

	if (!b) {
		bit_inx = xmalloc(sizeof(int32_t));
		bit_inx[0] = -1;
		return bit_inx;
	}

	/* worst case: every other bit set, resulting in an array of length
	 * bitstr_bits(b) + 1 (if an odd number of elements)
	 * + 1 (for trailing -1) */
	bit_inx = xmalloc_nz(sizeof(int32_t) * (_bitstr_bits(b) + 2));

	for (bit = 0; bit < _bitstr_bits(b); ) {
		/* skip past empty words */
		if (!b[_bit_word(bit)]) {
			bit += BITSTR_WORD_SIZE;
			continue;
		}

		if (bit_test(b, bit)) {
			start = bit;
			while (bit + 1 < _bitstr_bits(b)
			       && bit_test(b, bit + 1))
				bit++;
			bit_inx[pos++] = start;
			bit_inx[pos++] = bit;
		}
		bit++;
	}
	/* terminate array with -1 */
	bit_inx[pos] = -1;

	return bit_inx;
}

/* If trim_output is true, strip off leading zeros from result. */
static char *_bit_fmt_hexmask(bitstr_t *bitmap, bool trim_output)
{
	char *retstr, *ptr;
	char current;
	bitoff_t i, j, word;
	bitoff_t bitsize;

	if (trim_output)
		bitsize = bit_fls(bitmap) + 1;
	else
		bitsize = bit_size(bitmap);

	if (!bitsize)
		return xstrdup("0x0");

	/* 4 bits per ASCII '0'-'F' */
	bitoff_t charsize = (bitsize + 3) / 4;

	retstr = xmalloc(charsize + 3);

	retstr[0] = '0';
	retstr[1] = 'x';
	retstr[charsize + 2] = '\0';
	ptr = &retstr[charsize + 1];

	for (i = 0; i < bitsize;) {
		if (i + BITSTR_WORD_SIZE <= bitsize) {
			word = _bit_word(i);
			for (j = 0; j < sizeof(bitstr_t); j++) {
				uint8_t idx = ((uint8_t *)(&(bitmap[word])))[j];
				*ptr = hexmask_lookup[idx][1];
				ptr--;
				*ptr = hexmask_lookup[idx][0];
				ptr--;
			}
			i += BITSTR_WORD_SIZE;
		} else {
			current = 0;
			if (bit_test(bitmap, i))
				current |= 0x1;
			i++;
			if ((i < bitsize) && bit_test(bitmap, i))
				current |= 0x2;
			i++;
			if ((i < bitsize) && bit_test(bitmap, i))
				current |= 0x4;
			i++;
			if ((i < bitsize) && bit_test(bitmap, i))
				current |= 0x8;
			i++;

			if (current <= 9) {
				current += '0';
			} else {
				current += 'A' - 10;
			}
			*ptr-- = current;
		}
	}

	return retstr;
}

/* bit_fmt_hexmask
 *
 * Given a bitstr_t, allocate and return a string in the form of:
 *                         "0x0123ABC\0"
 *                            ^     ^
 *                            |     |
 *                           MSB   LSB
 *   bitmap (IN)  bitmap to format
 *   RETURN       formatted string
 */
char *bit_fmt_hexmask(bitstr_t *bitmap)
{
	return _bit_fmt_hexmask(bitmap, false);
}

/* bit_fmt_hexmask_trim
 *
 * Same as bit_fmt_hexmask() except leading zeros are stripped from the output.
 */
char *bit_fmt_hexmask_trim(bitstr_t *bitmap)
{
	return _bit_fmt_hexmask(bitmap, true);
}

/* bit_unfmt_hexmask
 *
 * Given a hex mask string "0x0123ABC\0", convert to a bitstr_t *
 *                            ^     ^
 *                            |     |
 *                           MSB   LSB
 *   bitmap (OUT)  bitmap to update
 *   str (IN)      hex mask string to unformat
 *   RET: 0 on success, -1 on error
 */
int bit_unfmt_hexmask(bitstr_t * bitmap, const char* str)
{
	int32_t bit_index = 0, len;
	int rc = 0;
	const char *curpos;
	bitstr_t current;
	bitoff_t bitsize;

	if (!bitmap || !str)
		return -1;

	len = strlen(str);
	bitsize = bit_size(bitmap);
	curpos = str + len - 1;

	bit_nclear(bitmap, 0, bitsize - 1);
	if (xstrncmp(str, "0x", 2) == 0) {	/* Bypass 0x */
		str += 2;
	}

	while (curpos >= str) {
		current = (bitoff_t) *curpos;
		if (isxdigit(current)) {	/* valid hex digit */
			if (isdigit(current)) {
				current -= '0';
			} else {
				current = toupper(current);
				current -= 'A' - 10;
			}
		} else {			/* not a valid hex digit */
		    	current = 0;
			rc = -1;
			break;
		}

		if (bit_index + 3 < bitsize && !(bit_index % 4)) {
#ifdef SLURM_BIGENDIAN
			current = (((current & 1) << 3) |
				   ((current & 2) << 1) |
				   ((current & 4) >> 1) |
				   ((current & 8) >> 3));
			current = (current << ((BITSTR_MAXPOS -
					        (bit_index & BITSTR_MAXPOS)) -
					       3));
			bitmap[_bit_word(bit_index)] |= current;
#else
			bitmap[_bit_word(bit_index)] |=
				(current & 0xf) << (bit_index & BITSTR_MAXPOS);
#endif
			curpos--;
			bit_index += 4;
			continue;
		}
		if (current & 1) {
			if (bit_index < bitsize)
				bit_set(bitmap, bit_index);
			else {
				rc = -1;
				break;
			}
		}
		if (current & 2) {
			if ((bit_index + 1) < bitsize)
				bit_set(bitmap, bit_index + 1);
			else {
				rc = -1;
				break;
			}
		}
		if (current & 4) {
			if ((bit_index + 2) < bitsize)
				bit_set(bitmap, bit_index + 2);
			else {
				rc = -1;
				break;
			}
		}
		if (current & 8) {
			if ((bit_index + 3) < bitsize)
				bit_set(bitmap, bit_index + 3);
			else {
				rc = -1;
				break;
			}
		}
		curpos--;
		bit_index += 4;
	}
	return rc;
}

/* Find the bit set at pos (0 - bitstr_bits) in bitstr b.
 *   b (IN)             bitstring to search
 *   pos (IN)           bit to search for
 *   RETURN             number bit is set in bitstring (-1 on error)
 */

bitoff_t
bit_get_bit_num(bitstr_t *b, int32_t pos)
{
	bitoff_t bit;
	int32_t cnt = 0;
	bitoff_t bit_cnt;

	_assert_bitstr_valid(b);
	bit_cnt = _bitstr_bits(b);
	xassert(pos <= bit_cnt);

	for (bit = 0; bit < bit_cnt; bit++) {
		if (bit_test(b, bit)) {	/* we got one */
			if (cnt == pos)
				break;
			cnt++;
		}
	}

	if (bit >= bit_cnt)
		bit = -1;

	return bit;
}

void bit_consolidate(bitstr_t *b)
{
	int set_count = bit_set_count(b);

	if (set_count && (set_count < bit_size(b))) {
		bit_nclear(b, set_count, bit_size(b) - 1);
		bit_nset(b, 0, set_count - 1);
	}
}