Generate all 67108864 De Bruijn sequences B(2, 6)

debruijn26.c

#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define force_inline __attribute__((always_inline)) inline

#define SUB_LEN 6U
#define SEQ_LEN (1U << SUB_LEN)
#define SUB_MASK (SEQ_LEN - 1U)

/** @brief Test a single bit in a bitmap, set it to 1 if it's currently unset,
 *         and finally return its previous value.
 *
 * @note No input validation.
 *
 * @param map Bitmap to check and possibly modify.
 * @param pos Bit position to test. Must be less than 64.
 * @return    The original state of the specified bit.
 *
 * @retval false The bit at @a pos was unset on function entry and is now set.
 * @retval true  The bit at @a pos was set on function entry and is unchanged.
 */
static force_inline bool
seen (uint64_t *map,
      uint64_t  pos)
{
	uint64_t bit = UINT64_C(1) << pos;
	if (*map & bit)
		return true;
	*map |= bit;
	return false;
}

/** @brief Right-rotate a 64-bit sequence.
 *
 * @note No input validation.
 *
 * @param seq Sequence to rotate.
 * @param off Amount of rotation. Must not be negative or larger than 64.
 * @return    Rotated sequence.
 */
__attribute__((const))
static force_inline uint64_t
ror_64 (uint64_t seq,
        int      off)
{
	return seq >> off | seq << ((int)SEQ_LEN - off);
}

static force_inline char *
pr_hex (uint64_t  seq,
        char     *buf,
        size_t    size)
{
	ptrdiff_t i = snprintf(buf, size, "0x%016" PRIx64, seq);
	if (i >= 0 && (size_t)i < size)
		buf += i;
	return buf;
}

static force_inline void
pr_seq (uint64_t seq)
{
	char buf[24];
	*pr_hex(seq, buf, sizeof buf) = '\0';
	puts(buf);
}

static inline uint64_t
scan60 (uint64_t seq,
        uint64_t map,
        int      pre,
        int      off)
{
	uint64_t k = ++pre ? 1u : 4u;

	for (uint64_t i = 0U; i < SEQ_LEN; i += k) {
		uint64_t map_ = map;
		if (seen(&map_, i))
			continue;

		uint64_t seq_ = seq | (i << off);
		int off_ = pre;

		for (uint64_t s = seq_ >> off_;; s >>= 1u) {
			if (seen(&map_, s & SUB_MASK))
				break;

			if (++off_ == off)
				goto not_seen;
		}

		/* collision */
		continue;

	not_seen:
		if (off < (int)(SEQ_LEN - SUB_LEN)) {
			scan60(seq_, map_, off, off + (int)SUB_LEN);
			continue;
		}

		off_ = off + 1;

		for (uint64_t s = ror_64(seq_, off_);; s >>= 1u) {
			if (seen(&map_, s & SUB_MASK))
				break;

			if (++off_ == (int)SEQ_LEN)
				goto all_good;
		}

		/* collision */
		continue;

	all_good:
		pr_seq(seq_ >> SUB_LEN);
	}

	return 0;
}

int
main (void)
{
	scan60(0u, 0u, -1, 4);
}