Page MenuHomeFreeBSD
Files F166690747

D16132.id183333.diff
No OneTemporary
Actions

D16132.id183333.diff
View Options

diff --git a/lib/Makefile b/lib/Makefile
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -44,6 +44,7 @@
libcam \
libcapsicum \
libcasper \
+ libcmb \
libcompat \
libcrypt \
libdevctl \
diff --git a/lib/libcmb/Makefile b/lib/libcmb/Makefile
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/Makefile
@@ -0,0 +1,21 @@
+.include <src.opts.mk>
+
+LIB= cmb
+SHLIB_MAJOR= 0
+INCS= cmb.h
+MAN= cmb.3
+SRCS= cmb.c
+
+CFLAGS+= -I${.CURDIR}
+
+LIBADD+= m
+
+.if ${MK_OPENSSL} != "no"
+CFLAGS+= -DHAVE_LIBCRYPTO
+LIBADD+= crypto
+.endif
+
+HAS_TESTS=
+SUBDIR.${MK_TESTS}+= tests
+
+.include <bsd.lib.mk>
diff --git a/lib/libcmb/cmb.h b/lib/libcmb/cmb.h
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/cmb.h
@@ -0,0 +1,373 @@
+/*-
+ * Copyright (c) 2002-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#ifndef _CMB_H_
+#define _CMB_H_
+
+#include <sys/param.h>
+#include <sys/types.h>
+
+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+#include <math.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#elif defined(__FreeBSD_version)
+#ifdef HAVE_LIBCRYPTO
+#define HAVE_OPENSSL_BN_H 1
+#define HAVE_OPENSSL_CRYPTO_H 1
+#else
+#undef HAVE_OPENSSL_BN_H
+#undef HAVE_OPENSSL_CRYPTO_H
+#endif
+#endif
+
+#ifdef HAVE_OPENSSL_CRYPTO_H
+#include <openssl/crypto.h>
+#endif
+#ifdef HAVE_OPENSSL_BN_H
+#include <openssl/bn.h>
+#ifndef OPENSSL_free
+#define OPENSSL_free(x) (void)(x)
+#endif
+#endif
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+#ifndef CMB_DEBUG
+#define CMB_DEBUG FALSE
+#endif
+
+/*
+ * Version constants for cmb_version(3)
+ */
+#define CMB_VERSION 0
+#define CMB_VERSION_LONG 1
+
+/*
+ * Header version info
+ */
+#define CMB_H_VERSION_MAJOR 3
+#define CMB_H_VERSION_MINOR 10
+#define CMB_H_VERSION_PATCH 0
+
+/*
+ * Macros for cmb_config options bitmask
+ */
+#define CMB_OPT_DEBUG 0x01 /* Enable debugging */
+#define CMB_OPT_NULPARSE 0x02 /* NUL delimit cmb_parse*() */
+#define CMB_OPT_NULPRINT 0x04 /* NUL delimit cmb_print*() */
+#define CMB_OPT_EMPTY 0x08 /* Show empty set with no items */
+#define CMB_OPT_NUMBERS 0x10 /* Show combination sequence numbers */
+#define CMB_OPT_RESERVED 0x20 /* Reserved for future use by cmb(3) */
+#define CMB_OPT_OPTION1 0x40 /* Available (unused by cmb(3)) */
+#define CMB_OPT_OPTION2 0x80 /* Available (unused by cmb(3)) */
+
+/*
+ * Macros for defining call-back functions/pointers
+ */
+#define CMB_ACTION(x) \
+ int x(struct cmb_config *config, uint64_t seq, uint32_t n_items, \
+ char *items[])
+#ifdef HAVE_OPENSSL_BN_H
+#define CMB_ACTION_BN(x) \
+ int x(struct cmb_config *config, BIGNUM *seq, uint32_t n_items, \
+ char *items[])
+#endif
+
+/*
+ * Build info
+ */
+struct cmb_build_info {
+ uint8_t debug; /* CMB_DEBUG */
+};
+extern struct cmb_build_info cmb_build_info;
+
+/*
+ * Anatomy of config option to pass as cmb*() config argument
+ */
+struct cmb_config {
+ uint8_t options; /* CMB_OPT_* bitmask. Default 0 */
+ char *delimiter; /* Item separator (default is " ") */
+ char *prefix; /* Prefix for each combination */
+ char *suffix; /* Suffix for each combination */
+ uint32_t size_min; /* Minimum number of elements in combination */
+ uint32_t size_max; /* Maximum number of elements in combination */
+
+ uint64_t count; /* Number of combinations */
+ uint64_t start; /* Starting combination */
+
+ void *data; /* Reserved for action callback */
+
+ /*
+ * cmb(3) function callback; called for each combination (default is
+ * cmb_print()). If the return from action() is non-zero, cmb() will
+ * stop calculation. The cmb() return value is the first non-zero
+ * result from action(), zero otherwise.
+ */
+ CMB_ACTION((*action));
+
+#ifdef HAVE_OPENSSL_BN_H
+ BIGNUM *count_bn; /* bn(3) number of combinations */
+ BIGNUM *start_bn; /* bn(3) starting combination */
+
+ /*
+ * cmb_bn(3) function callback; called for each combination (default is
+ * cmb_print_bn()). If the return from action_bn() is non-zero,
+ * cmb_bn() will stop calculation. The cmb_bn() return value is the
+ * first non-zero result from action_bn(), zero otherwise.
+ */
+ CMB_ACTION_BN((*action_bn));
+#endif
+};
+
+__BEGIN_DECLS
+int cmb(struct cmb_config *_config, uint32_t _n_items,
+ char *_items[]);
+uint64_t cmb_count(struct cmb_config *_config, uint32_t _n_items);
+char ** cmb_parse(struct cmb_config *_config, int _fd,
+ uint32_t *_n_items, uint32_t _max);
+char ** cmb_parse_file(struct cmb_config *_config, char *_path,
+ uint32_t *_n_items, uint32_t _max);
+int cmb_print(struct cmb_config *_config, uint64_t _seq,
+ uint32_t _n_items, char *_items[]);
+const char * cmb_version(int _type);
+#ifdef HAVE_OPENSSL_BN_H
+int cmb_bn(struct cmb_config *_config, uint32_t _n_items,
+ char *_items[]);
+BIGNUM * cmb_count_bn(struct cmb_config *_config, uint32_t _n_items);
+int cmb_print_bn(struct cmb_config *_config, BIGNUM *_seq,
+ uint32_t _n_items, char *_items[]);
+#endif
+
+/* Inline functions */
+static inline void cmb_print_seq(uint64_t seq) { printf("%"PRIu64" ", seq); }
+#ifdef HAVE_OPENSSL_BN_H
+static inline void cmb_print_seq_bn(BIGNUM *seq) { char *seq_str;
+ printf("%s ", seq_str = BN_bn2dec(seq));
+ OPENSSL_free(seq_str);
+}
+#endif /* HAVE_OPENSSL_BN_H */
+__END_DECLS
+
+/*
+ * Transformations
+ */
+
+extern int cmb_transform_precision;
+struct cmb_xitem {
+ char *cp; /* original item */
+ union cmb_xitem_type {
+ long double ld; /* item as long double */
+ } as;
+};
+
+#define CMB_TRANSFORM_EQ(eq, op, x, seqt, seqp) \
+ int \
+ x(struct cmb_config *config, seqt seq, uint32_t n_items, char *items[]) \
+ { \
+ uint8_t show_numbers = FALSE; \
+ uint32_t n; \
+ long double ld; \
+ long double total = 0; \
+ const char *delimiter = " "; \
+ const char *prefix = NULL; \
+ const char *suffix = NULL; \
+ struct cmb_xitem *xitem = NULL; \
+ \
+ if (config != NULL) { \
+ if (config->delimiter != NULL) \
+ delimiter = config->delimiter; \
+ if ((config->options & CMB_OPT_NUMBERS) != 0) \
+ show_numbers = TRUE; \
+ prefix = config->prefix; \
+ suffix = config->suffix; \
+ } \
+ if (!opt_silent) { \
+ if (show_numbers) \
+ seqp(seq); \
+ if (prefix != NULL && !opt_quiet) \
+ printf("%s", prefix); \
+ } \
+ if (n_items > 0) { \
+ memcpy(&xitem, &items[0], sizeof(struct cmb_xitem *)); \
+ total = xitem->as.ld; \
+ if (!opt_silent && !opt_quiet) { \
+ printf("%s", xitem->cp); \
+ if (n_items > 1) \
+ printf("%s" #op "%s", delimiter, delimiter); \
+ } \
+ } \
+ for (n = 1; n < n_items; n++) { \
+ memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \
+ ld = xitem->as.ld; \
+ total = eq; \
+ if (!opt_silent && !opt_quiet) { \
+ printf("%s", xitem->cp); \
+ if (n < n_items - 1) \
+ printf("%s" #op "%s", delimiter, delimiter); \
+ } \
+ } \
+ if (!opt_silent) { \
+ if (suffix != NULL && !opt_quiet) \
+ printf("%s", suffix); \
+ printf("%s%.*Lf\n", opt_quiet ? "" : " = ", \
+ cmb_transform_precision, total); \
+ } \
+ return (0); \
+ }
+
+#define CMB_TRANSFORM_OP(op, x) \
+ CMB_TRANSFORM_EQ(total op ld, op, x, uint64_t, cmb_print_seq)
+#define CMB_TRANSFORM_FN(op, fn, x) \
+ CMB_TRANSFORM_EQ(fn(total, ld), op, x, uint64_t, cmb_print_seq)
+
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+#define CMB_TRANSFORM_OP_BN(op, x) \
+ CMB_TRANSFORM_EQ(total op ld, op, x, BIGNUM *, cmb_print_seq_bn)
+#define CMB_TRANSFORM_FN_BN(op, fn, x) \
+ CMB_TRANSFORM_EQ(fn(total, ld), op, x, BIGNUM *, cmb_print_seq_bn)
+#endif
+
+/*
+ * Example transformations
+ */
+
+#if 0
+CMB_TRANSFORM_OP(+, cmb_add); /* creates cmb_add() */
+CMB_TRANSFORM_FN(/, div, cmb_div); /* creates cmb_div() */
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+CMB_TRANSFORM_OP_BN(+, cmb_add_bn); /* creates cmb_add_bn() */
+CMB_TRANSFORM_FN_BN(/, div, cmb_div_bn); /* creates cmb_div_bn() */
+#endif
+#endif
+
+/*
+ * Find transformations
+ */
+
+extern char *cmb_transform_find_buf;
+extern int cmb_transform_find_buf_size;
+extern struct cmb_xitem *cmb_transform_find;
+
+#define CMB_TRANSFORM_EQ_FIND(eq, op, x, seqt, seqp) \
+ int \
+ x(struct cmb_config *config, seqt seq, uint32_t n_items, char *items[]) \
+ { \
+ uint8_t show_numbers = FALSE; \
+ uint32_t n; \
+ int len; \
+ long double ld; \
+ long double total = 0; \
+ const char *delimiter = " "; \
+ const char *prefix = NULL; \
+ const char *suffix = NULL; \
+ struct cmb_xitem *xitem = NULL; \
+ \
+ for (n = 0; n < n_items; n++) { \
+ memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \
+ ld = xitem->as.ld; \
+ total = eq; \
+ } \
+ if (cmb_transform_precision == 0) { \
+ if (total != cmb_transform_find->as.ld) { \
+ return (0); \
+ } \
+ } else { \
+ len = snprintf(NULL, 0, "%.*Lf", \
+ cmb_transform_precision, total) + 1; \
+ if (len > cmb_transform_find_buf_size) { \
+ cmb_transform_find_buf = \
+ reallocf(cmb_transform_find_buf, \
+ (unsigned long)len); \
+ if (cmb_transform_find_buf == NULL) { \
+ errx(EXIT_FAILURE, "Out of memory?!"); \
+ /* NOTREACHED */ \
+ } \
+ cmb_transform_find_buf_size = len; \
+ } \
+ (void)snprintf(cmb_transform_find_buf, (size_t)len, \
+ "%.*Lf", cmb_transform_precision, total); \
+ if (strncmp(cmb_transform_find_buf, \
+ cmb_transform_find->cp, (size_t)len) != 0) \
+ return (0); \
+ } \
+ if (config != NULL) { \
+ if (config->delimiter != NULL) \
+ delimiter = config->delimiter; \
+ if ((config->options & CMB_OPT_NUMBERS) != 0) \
+ show_numbers = TRUE; \
+ prefix = config->prefix; \
+ suffix = config->suffix; \
+ } \
+ if (!opt_silent) { \
+ if (show_numbers) \
+ seqp(seq); \
+ if (prefix != NULL && !opt_quiet) \
+ printf("%s", prefix); \
+ } \
+ if (n_items > 0) { \
+ memcpy(&xitem, &items[0], sizeof(struct cmb_xitem *)); \
+ if (!opt_silent && !opt_quiet) { \
+ printf("%s", xitem->cp); \
+ if (n_items > 1) \
+ printf("%s" #op "%s", delimiter, delimiter); \
+ } \
+ } \
+ for (n = 1; n < n_items; n++) { \
+ memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \
+ if (!opt_silent && !opt_quiet) { \
+ printf("%s", xitem->cp); \
+ if (n < n_items - 1) \
+ printf("%s" #op "%s", delimiter, delimiter); \
+ } \
+ } \
+ if (!opt_silent) { \
+ if (suffix != NULL && !opt_quiet) \
+ printf("%s", suffix); \
+ printf("%s%.*Lf\n", opt_quiet ? "" : " = ", \
+ cmb_transform_precision, total); \
+ } \
+ return (0); \
+ }
+
+#define CMB_TRANSFORM_OP_FIND(op, x) \
+ CMB_TRANSFORM_EQ_FIND(total op ld, op, x, uint64_t, cmb_print_seq)
+#define CMB_TRANSFORM_FN_FIND(op, fn, x) \
+ CMB_TRANSFORM_EQ_FIND(fn(total, ld), op, x, uint64_t, cmb_print_seq)
+
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+#define CMB_TRANSFORM_OP_FIND_BN(op, x) \
+ CMB_TRANSFORM_EQ_FIND(total op ld, op, x, BIGNUM *, cmb_print_seq_bn)
+#define CMB_TRANSFORM_FN_FIND_BN(op, fn, x) \
+ CMB_TRANSFORM_EQ_FIND(fn(total, ld), op, x, BIGNUM *, cmb_print_seq_bn)
+#endif
+
+/*
+ * Example find transformations
+ */
+
+#if 0
+CMB_TRANSFORM_OP_FIND(+, cmb_add_find); /* creates cmb_add_find() */
+CMB_TRANSFORM_FN_FIND(/, div, cmb_div_find); /* creates cmb_div_find() */
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+CMB_TRANSFORM_OP_FIND_BN(+, cmb_add_bn); /* creates cmb_add_bn() */
+CMB_TRANSFORM_FN_FIND_BN(/, div, cmb_div_bn); /* creates cmb_div_bn() */
+#endif
+#endif
+
+#endif /* !_CMB_H_ */
diff --git a/lib/libcmb/cmb.3 b/lib/libcmb/cmb.3
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/cmb.3
@@ -0,0 +1,435 @@
+.\" Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+.\"
+.\" SPDX-License-Identifier: BSD-2-Clause
+.\"
+.Dd August 3, 2026
+.Dt CMB 3
+.Os
+.Sh NAME
+.Nm cmb
+.Nd combinatorics library
+.Sh LIBRARY
+.Lb libcmb
+.Sh SYNOPSIS
+.In cmb.h
+.Ft int
+.Fn cmb "struct cmb_config *config" "uint32_t n_items" "char *items[]"
+.Ft uint64_t
+.Fn cmb_count "struct cmb_config *config" "uint32_t n_items"
+.Ft char **
+.Fn cmb_parse "struct cmb_config *config" "int fd" "uint32_t *n_items" "uint32_t max"
+.Ft char **
+.Fn cmb_parse_file "struct cmb_config *config" "char *path" "uint32_t *n_items" "uint32_t max"
+.Ft int
+.Fn cmb_print "struct cmb_config *config" "uint64_t seq" "uint32_t n_items" "char *items[]"
+.Ft const char *
+.Fn cmb_version "int type"
+.Pp
+/* OpenSSL
+.Xr bn 3
+support */
+.Pp
+.Ft int
+.Fn cmb_bn "struct cmb_config *config" "uint32_t n_items" "char *items[]"
+.Ft "BIGNUM *"
+.Fn cmb_count_bn "struct cmb_config *config" "uint32_t n_items"
+.Ft int
+.Fn cmb_print_bn "struct cmb_config *config" "BIGNUM *seq" "uint32_t n_items" "char *items[]"
+.Sh DESCRIPTION
+The
+.Nm
+library provides a light-weight,
+portable,
+and fast interface for enumerating combinations.
+.Pp
+Anatomy of config argument to
+.Fn cmb* :
+.Bd -literal -offset indent
+struct cmb_config {
+ uint8_t options; /* CMB_OPT_* bitmask. Default 0 */
+ char *delimiter; /* Item separator (default is " ") */
+ char *prefix; /* Prefix for each combination */
+ char *suffix; /* Suffix for each combination */
+ uint32_t size_min; /* Minimum elements in combination */
+ uint32_t size_max; /* Maximum elements in combination */
+
+ uint64_t count; /* Number of combinations */
+ uint64_t start; /* Starting combination */
+
+ void *data; /* Reserved for action callback */
+
+ /*
+ * cmb(3) function callback; called for each combination
+ * (default is cmb_print()). If the return from action() is non-
+ * zero, cmb() will stop calculation. The cmb() return value is
+ * the first non-zero result from action(), zero otherwise.
+ */
+ CMB_ACTION((*action));
+
+ /* OpenSSL bn(3) support */
+
+ BIGNUM *count_bn; /* Number of combinations */
+ BIGNUM *start_bn; /* Starting combination */
+
+ /*
+ * cmb_bn(3) function callback; called for each combination
+ * (default is cmb_print_bn()). If the return from action_bn()
+ * is non-zero, cmb_bn() will stop calculation. The cmb_bn()
+ * return value is the first non-zero result from action_bn(),
+ * zero otherwise.
+ */
+ CMB_ACTION_BN((*action_bn));
+};
+.Ed
+.Pp
+The macro
+.Fn CMB_ACTION x
+is defined as:
+.Bd -literal -offset indent
+int x(struct cmb_config *config, uint64_t seq, uint32_t n_items,
+ char *items[]);
+.Ed
+.Pp
+When compiled with OpenSSL/LibreSSL support
+.Pq default ,
+the macro
+.Fn CMB_ACTION_BN x
+is defined as:
+.Bd -literal -offset indent
+int x(struct cmb_config *config, BIGNUM *seq, uint32_t n_items,
+ char *items[]);
+.Ed
+.Pp
+Macros for cmb_config options bitmask:
+.Bd -literal -offset indent
+CMB_OPT_DEBUG /* Enable debugging */
+CMB_OPT_NULPARSE /* NUL delimit cmb_parse*() */
+CMB_OPT_NULPRINT /* NUL delimit cmb_print*() */
+CMB_OPT_EMPTY /* Show empty set with no items */
+CMB_OPT_NUMBERS /* Show combination sequence numbers */
+CMB_OPT_RESERVED /* Reserved for future use by cmb(3) */
+CMB_OPT_OPTION1 /* Available (unused by cmb(3)) */
+CMB_OPT_OPTION2 /* Available (unused by cmb(3)) */
+.Ed
+.Pp
+If
+.Ar CMB_OPT_DEBUG
+is set and
+.Xr cmb 3
+was compiled with
+.Ql CMB_DEBUG ,
+enable debugging information on stderr.
+.Pp
+If
+.Ar CMB_OPT_NULPARSE
+is set,
+.Fn cmb_parse
+and
+.Fn cmb_parse_file
+will read items separated by an ASCII NUL character
+.Pq character code 0 .
+Otherwise,
+newline
+.Pq character code 10
+is used.
+.Pp
+If
+.Ar CMB_OPT_NULPRINT
+is set,
+.Fn cmb_print
+and
+.Fn cmb_print_bn
+will print combination items separated by an ASCII NUL character
+.Pq character code 0 .
+Otherwise,
+.Ar delimiter
+is used and if unset,
+combinations are separated by a single space.
+.Pp
+If
+.Ar CMB_OPT_EMPTY
+is set,
+the empty set
+.Pq consisting of a single combination with no items
+is enumerated by
+.Fn cmb
+/
+.Fn cmb_bn
+and counted by
+.Fn cmb_count
+/
+.Fn cmb_count_bn .
+.Pp
+If
+.Ar CMB_OPT_NUMBERS
+is set,
+print combination sequence number before calling
+.Fn action .
+Combinations are calculated in arithmetic progression,
+providing predictable order.
+The sequence number can be used as
+.Ar start
+or
+.Ar start_bn
+to begin at that combination.
+The sequence number precedes the prefix and is followed by a single space,
+regardless of
+.Ar delimiter .
+.Pp
+For each combination,
+if
+.Ar prefix
+is non-NULL it is printed before the first item in each combination and
+.Ar suffix ,
+if non-NULL,
+is printed after the last item.
+.Pp
+To operate on only a subset or range of subsets,
+use
+.Ar size_min
+and
+.Ar size_max .
+Only combinations containing at least
+.Ar size_min
+items and at most
+.Ar size_max
+items will be calculated.
+.Pp
+To limit the number of combinations that are calculated,
+set
+.Ar count
+or
+.Ar count_bn
+to a non-zero value.
+.Pp
+If
+.Ar start
+or
+.Ar start_bn
+is greater than one,
+the
+.Nm
+library will seek to that number combination before starting.
+.Pp
+.Ar action_bn ,
+.Ar count_bn ,
+and
+.Ar start_bn
+are only available on platforms with OpenSSL/LibreSSL
+.Xr bn 3
+and are used by
+.Fn cmb_bn
+and
+.Fn cmb_count_bn
+to overcome limits of 64-bit integers.
+.Pp
+.Fn cmb_version
+takes
+.Li CMB_VERSION
+or
+.Li CMB_VERSION_LONG
+as
+.Ar type
+and returns string version.
+For unknown
+.Ar type ,
+the text
+.Dq not available
+is returned.
+.Pp
+.Fn cmb
+enumerates combinations of
+.Fa n_items
+elements from
+.Fa items
+according to
+.Fa config ,
+calling
+.Fa action
+for each combination.
+.Pp
+.Fn cmb_count
+returns the total number of combinations that
+.Fn cmb
+would enumerate for the same
+.Fa config
+and
+.Fa n_items
+without invoking
+.Fa action .
+.Pp
+.Fn cmb_bn
+and
+.Fn cmb_count_bn
+are the
+.Xr bn 3
+counterparts of
+.Fn cmb
+and
+.Fn cmb_count ,
+used when combination counts or sequence numbers exceed 64-bit limits.
+.Ss Transformations
+The
+.Nm
+header also provides macros that mint
+.Ar action
+and
+.Ar action_bn
+callbacks which reduce each combination of numeric items with an operator or
+function and print the expression and total.
+.Xr cmb 1
+uses these for
+.Fl X
+and
+.Fl F .
+The macros expand to full function definitions,
+so each desired transform must be instantiated in exactly one translation unit
+.Pq e.g., with static linkage ;
+they must not be left uncommented in a header included by multiple files.
+.Pp
+Numeric items are passed as pointers to
+.Vt struct cmb_xitem
+cast through
+.Vt "char *"
+in the
+.Fa items
+array:
+.Bd -literal -offset indent
+struct cmb_xitem {
+ char *cp; /* printable item text */
+ union {
+ long double ld; /* numeric value */
+ } as;
+};
+.Ed
+.Pp
+.Va cmb_transform_precision
+controls how many digits after the decimal point are used when printing totals
+.Pq and when comparing totals for find transforms .
+A precision of
+.Li 0
+compares
+.Vt long double
+values directly for find transforms.
+.Pp
+For find transforms,
+set
+.Va cmb_transform_find
+to the target
+.Vt struct cmb_xitem
+before calling
+.Fn cmb
+or
+.Fn cmb_bn .
+.Va cmb_transform_find_buf
+and
+.Va cmb_transform_find_buf_size
+are maintained by the find macros when precision is non-zero
+.Pq string compare of formatted totals
+and need not be set by the caller.
+.Pp
+Convenience macros that produce a
+.Fn CMB_ACTION
+compatible function
+.Fa x .
+The
+.Fa op
+argument is stringified into the printed expression between items
+.Pq for example
+.Ql +
+in
+.Ql "1 + 3 = 4" .
+For
+.Ql OP
+macros,
+.Fa op
+is also the C operator applied to the running total;
+for
+.Ql FN
+macros the total is updated with
+.Fa fn
+and
+.Fa op
+is display-only:
+.Bd -literal -offset indent
+CMB_TRANSFORM_OP(op, x) /* total = total op ld */
+CMB_TRANSFORM_FN(op, fn, x) /* total = fn(total, ld) */
+.Ed
+.Pp
+When built with OpenSSL/LibreSSL
+.Xr bn 3 ,
+.Fn CMB_TRANSFORM_OP_BN
+and
+.Fn CMB_TRANSFORM_FN_BN
+produce
+.Fn CMB_ACTION_BN
+compatible functions for use as
+.Ar action_bn .
+.Pp
+Find variants only print when the running total matches
+.Va cmb_transform_find :
+.Bd -literal -offset indent
+CMB_TRANSFORM_OP_FIND(op, x)
+CMB_TRANSFORM_FN_FIND(op, fn, x)
+.Ed
+.Pp
+.Fn CMB_TRANSFORM_OP_FIND_BN
+and
+.Fn CMB_TRANSFORM_FN_FIND_BN
+are the corresponding
+.Xr bn 3
+forms.
+.Pp
+.Fn CMB_TRANSFORM_EQ
+and
+.Fn CMB_TRANSFORM_EQ_FIND
+are the underlying macros;
+the
+.Ql OP
+and
+.Ql FN
+forms wrap them for binary operators and two-argument functions.
+.Pp
+Transforms expect
+.Va opt_silent
+and
+.Va opt_quiet
+to exist in the same translation unit;
+truthy values suppress printing,
+matching the globals used by
+.Xr cmb 1 .
+Find transforms may call
+.Xr errx 3
+if growing
+.Va cmb_transform_find_buf
+fails.
+.Pp
+Example
+.Pq find combinations of 1, 2, and 3 that sum to 4 :
+.Bd -literal -offset indent
+static uint8_t opt_quiet = FALSE;
+static uint8_t opt_silent = FALSE;
+static CMB_TRANSFORM_OP_FIND(+, cmb_add_find);
+
+struct cmb_xitem x1 = { .cp = "1", .as.ld = 1 };
+struct cmb_xitem x2 = { .cp = "2", .as.ld = 2 };
+struct cmb_xitem x3 = { .cp = "3", .as.ld = 3 };
+char *items[] = { (char *)&x1, (char *)&x2, (char *)&x3 };
+struct cmb_xitem find = { .cp = "4", .as.ld = 4 };
+struct cmb_config config = { .action = cmb_add_find };
+
+cmb_transform_find = &find;
+cmb_transform_precision = 0;
+cmb(&config, 3, items); /* prints: 1 + 3 = 4 */
+.Ed
+.Sh SEE ALSO
+.Xr cmb 1 ,
+.Xr bn 3 ,
+.Xr errx 3
+.Sh HISTORY
+The
+.Nm
+library first appeared in
+.Fx 16.0 .
+.Sh AUTHORS
+.An Devin Teske Aq Mt dteske@FreeBSD.org
diff --git a/lib/libcmb/cmb.c b/lib/libcmb/cmb.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/cmb.c
@@ -0,0 +1,1362 @@
+/*-
+ * Copyright (c) 2002-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <sys/stat.h>
+
+#include <err.h>
+#include <errno.h>
+#include <fcntl.h>
+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "cmb.h"
+#include "cmb_private.h"
+
+#ifdef HAVE_OPENSSL_CRYPTO_H
+#include <openssl/crypto.h>
+#endif
+
+#if CMB_DEBUG
+#include <stdarg.h>
+#include <unistd.h>
+#define CMB_DEBUG_PREFIX "DEBUG: "
+#define CMB_DEBUG_PREFIX_LEN 7
+#ifndef CMB_DEBUG_BUFSIZE
+#define CMB_DEBUG_BUFSIZE 2048
+#endif
+#endif
+
+#ifndef PATH_MAX
+#define PATH_MAX 1024
+#endif
+
+#ifndef CMB_PARSE_FRAGSIZE
+#define CMB_PARSE_FRAGSIZE 512
+#endif
+
+static const char version[] = "libcmb 3.10.0";
+static const char version_long[] = "$Version: libcmb 3.10.0 $";
+
+/*
+ * Build info
+ */
+struct cmb_build_info cmb_build_info = {
+ .debug = CMB_DEBUG,
+};
+
+/*
+ * Globals
+ */
+int cmb_transform_find_buf_size = 0;
+int cmb_transform_precision = 0;
+char *cmb_transform_find_buf = NULL;
+struct cmb_xitem *cmb_transform_find = NULL;
+
+#if CMB_DEBUG
+__attribute__((__format__ (__printf__, 1, 0)))
+static void
+cmb_debug(const char *fmt, ...)
+{
+ int len;
+ va_list ap;
+ char buf[CMB_DEBUG_BUFSIZE];
+
+ sprintf(buf, CMB_DEBUG_PREFIX);
+ va_start(ap, fmt);
+ len = vsnprintf(&buf[CMB_DEBUG_PREFIX_LEN],
+ sizeof(buf) - CMB_DEBUG_PREFIX_LEN - 1, fmt, ap);
+ va_end(ap);
+ if (len == -1)
+ len = sizeof(buf) - CMB_DEBUG_PREFIX_LEN - 1;
+ len += CMB_DEBUG_PREFIX_LEN;
+ buf[len++] = '\n';
+ write(2, buf, (size_t)len);
+}
+#endif
+
+/*
+ * Takes one of below described type constants. Returns string version.
+ *
+ * TYPE DESCRIPTION
+ * CMB_VERSION Short version text. For example, "x.y".
+ * CMB_VERSION_LONG RCS style ($Version$).
+ *
+ * For unknown type, the text "not available" is returned.
+ */
+const char *
+cmb_version(int type)
+{
+ switch(type) {
+ case CMB_VERSION:
+ return (version);
+ case CMB_VERSION_LONG:
+ return (version_long);
+ default:
+ return ("not available");
+ }
+}
+
+/*
+ * Takes pointer to `struct cmb_config' options, file path to read items from,
+ * pointer to uint32_t (written-to, containing number of items read), and
+ * uint32_t to optionally maximum number of items read from file. Returns
+ * allocated array of char * items read from file.
+ */
+char **
+cmb_parse_file(struct cmb_config *config, char *path, uint32_t *n_items,
+ uint32_t max)
+{
+#if CMB_DEBUG
+ uint8_t debug = FALSE;
+#endif
+ int fd;
+ char rpath[PATH_MAX];
+
+#if CMB_DEBUG
+ if (config != NULL && (config->options & CMB_OPT_DEBUG) != 0)
+ debug = TRUE;
+#endif
+
+ /* Resolve the file path */
+ if (path == NULL || (path[0] == '-' && path[1] == '\0')) {
+ strcpy(rpath, "/dev/stdin");
+ } else if (realpath(path, rpath) == 0)
+ return (NULL);
+
+ /* Open the file */
+ if ((fd = open(rpath, O_RDONLY)) < 0)
+ return (NULL);
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug("%s: opened `%s' fd=%u", __func__, rpath, fd);
+#endif
+
+ return (cmb_parse(config, fd, n_items, max));
+}
+
+/*
+ * Takes pointer to `struct cmb_config' options, file descriptor to read items
+ * from, pointer to uint32_t (written-to, containing number of items read), and
+ * uint32_t to optionally maximum number of items read from file. Returns
+ * allocated array of char * items read from file.
+ */
+char **
+cmb_parse(struct cmb_config *config, int fd, uint32_t *n_items, uint32_t max)
+{
+ char d = '\n';
+#if CMB_DEBUG
+ uint8_t debug = FALSE;
+#endif
+ uint32_t _n_items;
+ char **items = NULL;
+ char *b, *buf;
+ char *p;
+ uint64_t n;
+ size_t bufsize, buflen;
+ size_t datasize = 0;
+ size_t fragsize = sizeof(char *) * CMB_PARSE_FRAGSIZE;
+ size_t itemsize = fragsize;
+ ssize_t r = 1;
+ struct stat sb;
+
+ errno = 0;
+
+ /* Process config options */
+ if (config != NULL) {
+ if ((config->options & CMB_OPT_NULPARSE) != 0)
+ d = '\0';
+ else if (config->delimiter != NULL)
+ if (*(config->delimiter) != '\0')
+ d = *(config->delimiter);
+#if CMB_DEBUG
+ if ((config->options & CMB_OPT_DEBUG) != 0)
+ debug = TRUE;
+#endif
+ }
+
+ /* Use output block size as buffer size if available */
+ if (fstat(fd, &sb) == 0) {
+ if (S_ISREG(sb.st_mode)) {
+ if (sysconf(_SC_PHYS_PAGES) >
+ PHYSPAGES_THRESHOLD)
+ bufsize = MIN(BUFSIZE_MAX, MAXPHYS * 8);
+ else
+ bufsize = BUFSIZE_SMALL;
+ } else
+ bufsize = (size_t)MAX(sb.st_blksize,
+ (blksize_t)sysconf(_SC_PAGESIZE));
+ } else
+ bufsize = MIN(BUFSIZE_MAX, MAXPHYS * 8);
+
+ /* Initialize buffer/pointers */
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug("%s: reading fd=%u bufsize=%lu",
+ __func__, fd, bufsize);
+#endif
+ if ((buf = malloc(bufsize)) == NULL) {
+ close(fd);
+ return (NULL);
+ }
+ buflen = bufsize;
+ if ((items = malloc(itemsize)) == NULL) {
+ free(buf);
+ close(fd);
+ return (NULL);
+ }
+
+ /* Read the file until EOF */
+ b = buf;
+ *n_items = _n_items = 0;
+ while (r != 0) {
+ r = read(fd, b, bufsize);
+
+ /* Test for Error/EOF */
+ if (r <= 0)
+ break;
+
+ /* Resize the buffer if necessary */
+ datasize += (size_t)r;
+ if (buflen - datasize < bufsize) {
+ buflen += bufsize;
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug("%s: increasing buffer to %lu bytes",
+ __func__, buflen);
+#endif
+ {
+ char *tmp;
+
+ if ((tmp = reallocf(buf, buflen)) == NULL) {
+ free(items);
+ items = NULL;
+ goto cmb_parse_return;
+ }
+ buf = tmp;
+ }
+ }
+ b = &buf[datasize];
+ }
+
+ if (datasize == 0) {
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug("%s: n_items=%u datasize=%lu",
+ __func__, *n_items, datasize);
+#endif
+ free(buf);
+ free(items);
+ close(fd);
+ return (NULL);
+ }
+
+ /* chomp trailing newline */
+ if (buf[datasize-1] == '\n')
+ buf[datasize-1] = '\0';
+
+ /* Look for delimiter */
+ p = buf;
+ for (n = 0; n < datasize; n++) {
+ if (buf[n] != d)
+ continue;
+ items[_n_items++] = p;
+ buf[n] = '\0';
+ p = buf + n + 1;
+ if (max > 0 && _n_items >= max)
+ goto cmb_parse_return;
+ if (_n_items >= 0xffffffff) {
+ free(buf);
+ free(items);
+ items = NULL;
+ errno = EFBIG;
+ goto cmb_parse_return;
+ } else if (_n_items % CMB_PARSE_FRAGSIZE == 0) {
+ void *tmp;
+
+ itemsize += fragsize;
+ if ((tmp = reallocf(items, itemsize)) == NULL) {
+ free(buf);
+ items = NULL;
+ goto cmb_parse_return;
+ }
+ items = tmp;
+ }
+ }
+ if (p < buf + datasize)
+ items[_n_items++] = p;
+
+cmb_parse_return:
+ *n_items = _n_items;
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug("%s: n_items=%u datasize=%lu",
+ __func__, *n_items, datasize);
+#endif
+ close(fd);
+ return (items);
+}
+
+/*
+ * Takes pointer to `struct cmb_config' options and number of items. Returns
+ * total number of combinations according to config options.
+ */
+uint64_t
+cmb_count(struct cmb_config *config, uint32_t n_items)
+{
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ uint32_t curset;
+ uint32_t i = n_items;
+ uint32_t k;
+ uint32_t p;
+ uint32_t setdone = n_items;
+ uint32_t setinit = 1;
+ uint64_t count = 0;
+ long double z = 1;
+ uint64_t ncombos;
+
+ errno = 0;
+ if (n_items == 0)
+ return (0);
+
+ /* Process config options */
+ if (config != NULL) {
+ if ((config->options & CMB_OPT_EMPTY) != 0)
+ show_empty = TRUE;
+ if (config->size_min != 0 || config->size_max != 0) {
+ setinit = config->size_min;
+ setdone = config->size_max;
+ }
+ }
+
+ /* Adjust values to be non-zero (mathematical constraint) */
+ if (setinit == 0)
+ setinit = 1;
+ if (setdone == 0)
+ setdone = 1;
+
+ /* Return zero if the request is out of range */
+ if (setinit > n_items && setdone > n_items)
+ return (0);
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > n_items)
+ setinit = n_items;
+ if (setdone > n_items)
+ setdone = n_items;
+
+ /* Check for integer overflow */
+ if ((setinit > setdone && setinit - setdone >= 64) ||
+ (setinit < setdone && setdone - setinit >= 64)) {
+ errno = ERANGE;
+ return (0);
+ }
+
+ /* If entire set is requested, return 2^N[-1] */
+ if ((setinit == 1 && setdone == n_items) ||
+ (setinit == n_items && setdone == 1)) {
+ if (show_empty) {
+ if (n_items >= 64) {
+ errno = ERANGE;
+ return (0);
+ }
+ return (1 << n_items);
+ } else
+ return (ULLONG_MAX >> (64 - n_items));
+ }
+
+ /* Set the direction of flow (incrementing vs. decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /*
+ * Loop over each `set' in the configured direction until we are done
+ */
+ if (show_empty)
+ count++;
+ p = nextset > 0 ? setinit - 1 : setinit;
+ for (k = 1; k <= p; k++)
+ z = (z * i--) / k;
+ for (curset = setinit;
+ nextset > 0 ? curset <= setdone : curset >= setdone;
+ curset += (uint32_t)nextset)
+ {
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0)
+ z = (z * i--) / k++;
+
+ /* Add number of combinations in this set to total */
+ if ((ncombos = (uint64_t)z) == 0) {
+ errno = ERANGE;
+ return (0);
+ }
+ if (ncombos > ULLONG_MAX - count) {
+ errno = ERANGE;
+ return (0);
+ }
+ count += ncombos;
+
+ /* Calculate number of combinations (decrementing) */
+ if (nextset < 0)
+ z = (z * --k) / ++i;
+ }
+
+ return (count);
+}
+
+/*
+ * Takes pointer to `struct cmb_config' options, number of items, and array of
+ * `char *' items. Calculates combinations according to options and either
+ * prints combinations to stdout (default) or runs `action' if passed-in as
+ * function pointer member of `config' argument.
+ */
+int
+cmb(struct cmb_config *config, uint32_t n_items, char *items[])
+{
+#if CMB_DEBUG
+ uint8_t debug = FALSE;
+#endif
+ uint8_t docount = FALSE;
+ uint8_t doseek = FALSE;
+ uint8_t show_empty = FALSE;
+ uint8_t show_numbers = FALSE;
+ int8_t nextset = 1;
+ int retval = 0;
+ uint32_t curset;
+ uint32_t i = n_items;
+ uint32_t k;
+ uint32_t n;
+ uint32_t p;
+ uint32_t seed;
+ uint32_t setdone = n_items;
+ uint32_t setinit = 1;
+ uint32_t setmax;
+ uint32_t setnums_last;
+ uint32_t setpos;
+ uint32_t setpos_backend;
+ uint64_t combo;
+ uint64_t count = 0;
+ uint64_t ncombos;
+ uint64_t seek = 0;
+ uint64_t seq = 1;
+ long double z = 1;
+ char **curitems;
+ uint32_t *setnums;
+ uint32_t *setnums_backend;
+ CMB_ACTION((*action)) = cmb_print;
+
+ errno = 0;
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->action != NULL)
+ action = config->action;
+ if (config->count != 0) {
+ docount = TRUE;
+ count = config->count;
+ }
+ if ((config->options & CMB_OPT_DEBUG) != 0) {
+#if CMB_DEBUG
+ debug = TRUE;
+#else
+ warnx("libcmb not compiled with debug support!");
+#endif
+ }
+ if ((config->options & CMB_OPT_EMPTY) != 0)
+ show_empty = TRUE;
+ if ((config->options & CMB_OPT_NUMBERS) != 0)
+ show_numbers = TRUE;
+ if (config->size_min != 0 || config->size_max != 0) {
+ setinit = config->size_min;
+ setdone = config->size_max;
+ }
+ if (config->start > 1) {
+ doseek = TRUE;
+ seek = config->start;
+#if CMB_DEBUG
+ if (show_numbers || debug)
+#else
+ if (show_numbers)
+#endif
+ seq = seek;
+ }
+ }
+
+ if (!show_empty) {
+ if (n_items == 0)
+ return (0);
+ else if (cmb_count(config, n_items) == 0)
+ return (errno);
+ }
+
+ /* Adjust values to be non-zero (mathematical constraint) */
+ if (setinit == 0)
+ setinit = 1;
+ if (setdone == 0)
+ setdone = 1;
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > n_items)
+ setinit = n_items;
+ if (setdone > n_items)
+ setdone = n_items;
+
+ /* Set the direction of flow (incrementing vs. decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset > 0 && show_empty) {
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug(">>> 0-item combinations <<<");
+#endif
+ if (!doseek) {
+ retval = action(config, seq++, 0, NULL);
+ if (retval != 0)
+ return (retval);
+ if (docount && --count == 0)
+ return (retval);
+ } else {
+ seek--;
+ if (seek == 1)
+ doseek = FALSE;
+ }
+ }
+
+ if (n_items == 0)
+ return (0);
+
+ /* Allocate memory */
+ setmax = setdone > setinit ? setdone : setinit;
+ if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ if ((setnums_backend =
+ (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+
+ /*
+ * Loop over each `set' in the configured direction until we are done.
+ * NB: Each `set' can represent a single item or multiple items.
+ */
+ p = nextset > 0 ? setinit - 1 : setinit;
+ for (k = 1; k <= p; k++)
+ z = (z * i--) / k;
+ for (curset = setinit;
+ nextset > 0 ? curset <= setdone : curset >= setdone;
+ curset += (uint32_t)nextset)
+ {
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug(">>> %u-item combinations <<<", curset);
+#endif
+
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0)
+ z = (z * i--) / k++;
+
+ /* Cast number of combinations in set to integer */
+ if ((ncombos = (uint64_t)z) == 0)
+ return (errno = ERANGE);
+
+ /* Jump to next set if requested start is beyond this one */
+ if (doseek) {
+ if (seek > ncombos) {
+ seek -= ncombos;
+ if (nextset < 0)
+ z = (z * --k) / ++i;
+ continue;
+ } else if (seek == 1) {
+ doseek = FALSE;
+ }
+ }
+
+ /* Fill array with the initial positional arguments */
+#if CMB_DEBUG
+ if (debug)
+ fprintf(stderr, CMB_DEBUG_PREFIX "setnums=[");
+#endif
+ for (n = 0; n < curset; n++) {
+#if CMB_DEBUG
+ if (debug) {
+ if (n == curset - 1)
+ fprintf(stderr, "\033[31m%u\033[m", n);
+ else
+ fprintf(stderr, "%u", n);
+ if (n + 1 < curset)
+ fprintf(stderr, ",");
+ }
+#endif
+ curitems[n] = items[n];
+ }
+#if CMB_DEBUG
+ if (debug)
+ fprintf(stderr, "] seq=%"PRIu64"\n", seq);
+#endif
+
+ /* Produce results with the first set of items */
+ if (!doseek) {
+ retval = action(config, seq++, curset, curitems);
+ if (retval != 0)
+ break;
+ if (docount && --count == 0)
+ break;
+ }
+
+ /*
+ * Prefill two arrays used for matrix calculations.
+ *
+ * The first array (setnums) is a linear sequence starting at
+ * one (1) and ending at N (where N is the same integer as the
+ * current set we're operating on). For example, if we are
+ * currently on a set-of-2, setnums is 1, 2.
+ *
+ * The second array (setnums_backend) is a linear sequence
+ * starting at n_items-N and ending at n_items (again, N is the
+ * same integer as the current set we are operating on; n_items
+ * is the total number of items). For example, if we are
+ * operating on a set-of-2, and n_items is 8, setnums_backend is
+ * set to 7, 8.
+ */
+ for (n = 0; n < curset; n++)
+ setnums[n] = n;
+ p = 0;
+ for (n = curset; n > 0; n--)
+ setnums_backend[p++] = n_items - n;
+
+ /*
+ * Process remaining self-similar combinations in the set.
+ */
+ for (combo = 1; combo < ncombos; combo++) {
+ setnums_last = curset;
+
+ /*
+ * Using self-similarity (matrix) theorem, determine
+ * (by comparing the [sliding] setnums to the stored
+ * setnums_backend) the number of arguments that remain
+ * available for shifting into a new setnums value
+ * (for later mapping into curitems).
+ *
+ * In essence, determine when setnums has slid into
+ * setnums_backend in which case we can mathematically
+ * use the last item to find the next-new item.
+ */
+ for (n = curset; n > 0; n--) {
+ setpos = setnums[n - 1];
+ setpos_backend = setnums_backend[n - 1];
+ /*
+ * If setpos is equal to or greater than
+ * setpos_backend then we keep iterating over
+ * the current set's list of argument positions
+ * until otherwise; each time incrementing the
+ * amount of numbers we must produce from
+ * formulae rather than stored position.
+ */
+ setnums_last = n - 1;
+ if (setpos < setpos_backend)
+ break;
+ }
+
+ /*
+ * The next few stanzas are dedicated to rebuilding the
+ * setnums array for mapping positional items
+ * [immediately following] into curitems.
+ */
+
+ /*
+ * Get the generator number used to populate unknown
+ * positions in the matrix (using self-similarity).
+ */
+ seed = setnums[setnums_last];
+
+ /*
+ * Use the generator number to populate any position
+ * numbers that weren't carried over from previous
+ * combination run -- using self-similarity theorem.
+ */
+ for (n = setnums_last; n <= curset; n++)
+ setnums[n] = seed + n - setnums_last + 1;
+#if CMB_DEBUG
+ if (debug) {
+ fprintf(stderr, CMB_DEBUG_PREFIX "setnums=[");
+ for (n = 0; n < curset; n++) {
+ if (n == setnums_last) {
+ fprintf(stderr,
+ "\033[31m%u\033[m",
+ setnums[n]);
+ } else {
+ fprintf(stderr, "%u",
+ setnums[n]);
+ }
+ if (n + 1 < curset)
+ fprintf(stderr, ",");
+ }
+ fprintf(stderr, "] seq=%"PRIu64"\n", seq);
+ }
+#endif
+
+ /* Now map new setnums into values stored in items */
+ for (n = 0; n < curset; n++)
+ curitems[n] = items[setnums[n]];
+
+ /* Produce results with this set of items */
+ if (doseek) {
+ seek--;
+ if (seek == 1)
+ doseek = FALSE;
+ }
+ if (!doseek || seek == 1) {
+ doseek = FALSE;
+ retval = action(config, seq++, curset,
+ curitems);
+ if (retval != 0)
+ goto cmb_return;
+ if (docount && --count == 0)
+ goto cmb_return;
+ }
+
+ } /* for combo */
+
+ /* Calculate number of combinations (decrementing) */
+ if (nextset < 0)
+ z = (z * --k) / ++i;
+
+ } /* for curset */
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset < 0 && show_empty) {
+ if ((!doseek || seek == 1) && (!docount || count > 0)) {
+ retval = action(config, seq++, 0, NULL);
+ }
+ }
+
+cmb_return:
+ free(curitems);
+ free(setnums);
+ free(setnums_backend);
+
+ return (retval);
+}
+
+CMB_ACTION(cmb_print)
+{
+ uint8_t nul = FALSE;
+ uint8_t show_numbers = FALSE;
+ uint32_t n;
+ const char *delimiter = " ";
+ const char *prefix = NULL;
+ const char *suffix = NULL;
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->delimiter != NULL)
+ delimiter = config->delimiter;
+ if ((config->options & CMB_OPT_NULPRINT) != 0)
+ nul = TRUE;
+ if ((config->options & CMB_OPT_NUMBERS) != 0)
+ show_numbers = TRUE;
+ prefix = config->prefix;
+ suffix = config->suffix;
+ }
+
+ if (show_numbers)
+ printf("%"PRIu64" ", seq);
+ if (prefix != NULL)
+ printf("%s", prefix);
+ for (n = 0; n < n_items; n++) {
+ printf("%s", items[n]);
+ if (n < n_items - 1)
+ printf("%s", delimiter);
+ }
+ if (suffix != NULL)
+ printf("%s", suffix);
+ if (nul)
+ printf("%c", 0);
+ else
+ printf("\n");
+
+ return (0);
+}
+
+#ifdef HAVE_OPENSSL_BN_H
+/*
+ * Takes pointer to `struct cmb_config' options and number of items. Returns
+ * total number of combinations according to config options. Numbers formatted
+ * as openssl bn(3) BIGNUM type.
+ */
+BIGNUM *
+cmb_count_bn(struct cmb_config *config, uint32_t n_items)
+{
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ uint32_t curset;
+ uint32_t i = n_items;
+ uint32_t k;
+ uint32_t p;
+ uint32_t setdone = n_items;
+ uint32_t setinit = 1;
+ BIGNUM *count = NULL;
+ BIGNUM *ncombos = NULL;
+
+ if (n_items == 0)
+ return (NULL);
+
+ /* Process config options */
+ if (config != NULL) {
+ if ((config->options & CMB_OPT_EMPTY) != 0)
+ show_empty = TRUE;
+ if (config->size_min != 0 || config->size_max != 0) {
+ setinit = config->size_min;
+ setdone = config->size_max;
+ }
+ }
+
+ /* Adjust values to be non-zero (mathematical constraint) */
+ if (setinit == 0)
+ setinit = 1;
+ if (setdone == 0)
+ setdone = 1;
+
+ /* Return NULL if the request is out of range */
+ if (setinit > n_items && setdone > n_items)
+ return (NULL);
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > n_items)
+ setinit = n_items;
+ if (setdone > n_items)
+ setdone = n_items;
+
+ /* Set the direction of flow (incrementing vs decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* Initialize count */
+ if ((count = BN_new()) == NULL)
+ return (NULL);
+ BN_zero(count);
+
+ /* If entire set is requested, return 2^N[-1] */
+ if ((setinit == 1 && setdone == n_items) ||
+ (setinit == n_items && setdone == 1)) {
+ if (show_empty) {
+ BN_lshift(count, BN_value_one(), (int)n_items);
+ goto cmb_count_bn_return;
+ } else {
+ if (BN_lshift(count, BN_value_one(), (int)n_items))
+ BN_sub_word(count, 1);
+ goto cmb_count_bn_return;
+ }
+ }
+
+ /* Allocate memory */
+ if ((ncombos = BN_new()) == NULL)
+ goto cmb_count_bn_return;
+ if (!BN_one(ncombos))
+ goto cmb_count_bn_return;
+
+ /*
+ * Loop over each `set' in the configured direction until we are done
+ */
+ p = nextset > 0 ? setinit - 1 : setinit;
+ for (k = 1; k <= p; k++) {
+ if (!BN_mul_word(ncombos, i--))
+ goto cmb_count_bn_return;
+ if (BN_div_word(ncombos, k) == (BN_ULONG)-1)
+ goto cmb_count_bn_return;
+ }
+ for (curset = setinit;
+ nextset > 0 ? curset <= setdone : curset >= setdone;
+ curset += (uint32_t)nextset)
+ {
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0) {
+ if (!BN_mul_word(ncombos, i--))
+ break;
+ if (BN_div_word(ncombos, k++) == (BN_ULONG)-1)
+ break;
+ }
+
+ /* Add number of combinations in this set to total */
+ if (!BN_add(count, count, ncombos))
+ break;
+
+ /* Calculate number of combinations (decrementing) */
+ if (nextset < 0) {
+ if (!BN_mul_word(ncombos, --k))
+ break;
+ if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1)
+ break;
+ }
+ }
+
+cmb_count_bn_return:
+ BN_free(ncombos);
+
+ return (count);
+}
+
+/*
+ * Takes pointer to `struct cmb_config' options, number of items, and array
+ * of `char *' items. Calculates combinations according to options and either
+ * prints combinations to stdout (default) or runs `action_bn' if passed-in as
+ * function pointer member of `config' argument. Numbers formatted as openssl
+ * bn(3) BIGNUM type.
+ */
+int
+cmb_bn(struct cmb_config *config, uint32_t n_items, char *items[])
+{
+#if CMB_DEBUG
+ uint8_t debug = FALSE;
+#endif
+ uint8_t docount = FALSE;
+ uint8_t doseek = FALSE;
+ uint8_t show_empty = FALSE;
+ uint8_t show_numbers = FALSE;
+ int8_t nextset = 1;
+ int retval = 0;
+ uint32_t curset;
+ uint32_t i = n_items;
+ uint32_t k;
+ uint32_t n;
+ uint32_t p;
+ uint32_t seed;
+ uint32_t setdone = n_items;
+ uint32_t setinit = 1;
+ uint32_t setmax;
+ uint32_t setnums_last;
+ uint32_t setpos;
+ uint32_t setpos_backend;
+ char **curitems;
+#if CMB_DEBUG
+ char *seq_str;
+#endif
+ uint32_t *setnums;
+ uint32_t *setnums_backend;
+ BIGNUM *combo = NULL;
+ BIGNUM *count = NULL;
+ BIGNUM *ncombos = NULL;
+ BIGNUM *seek = NULL;
+ BIGNUM *seq = NULL;
+ CMB_ACTION_BN((*action_bn)) = cmb_print_bn;
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->action_bn != NULL)
+ action_bn = config->action_bn;
+ if (config->count_bn != NULL &&
+ !BN_is_negative(config->count_bn) &&
+ !BN_is_zero(config->count_bn))
+ {
+ docount = TRUE;
+ if ((count = BN_dup(config->count_bn)) == NULL)
+ goto cmb_bn_return;
+ }
+ if ((config->options & CMB_OPT_DEBUG) != 0) {
+#if CMB_DEBUG
+ debug = TRUE;
+#else
+ warnx("libcmb not compiled with debug support!");
+#endif
+ }
+ if ((config->options & CMB_OPT_EMPTY) != 0)
+ show_empty = TRUE;
+ if ((config->options & CMB_OPT_NUMBERS) != 0)
+ show_numbers = TRUE;
+ if (config->size_min != 0 || config->size_max != 0) {
+ setinit = config->size_min;
+ setdone = config->size_max;
+ }
+ if (config->start_bn != NULL &&
+ !BN_is_negative(config->start_bn) &&
+ !BN_is_zero(config->start_bn) &&
+ !BN_is_one(config->start_bn))
+ {
+ doseek = TRUE;
+ if ((seek = BN_dup(config->start_bn)) == NULL)
+ goto cmb_bn_return;
+#if CMB_DEBUG
+ if (show_numbers || debug) {
+#else
+ if (show_numbers) {
+#endif
+ if ((seq = BN_dup(seek)) == NULL)
+ goto cmb_bn_return;
+ if (!BN_sub_word(seq, 1))
+ goto cmb_bn_return;
+ }
+ }
+ }
+
+ if (n_items == 0 && !show_empty)
+ goto cmb_bn_return;
+
+ /* Adjust values to be non-zero (mathematical constraint) */
+ if (setinit == 0)
+ setinit = 1;
+ if (setdone == 0)
+ setdone = 1;
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > n_items)
+ setinit = n_items;
+ if (setdone > n_items)
+ setdone = n_items;
+
+ /* Set the direction of flow (incrementing vs. decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* Initialize sequence number */
+ if (seq == NULL) {
+ if ((seq = BN_new()) == NULL)
+ goto cmb_bn_return;
+ BN_zero(seq);
+ }
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset > 0 && show_empty) {
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug(">>> 0-item combinations <<<");
+#endif
+ if (!doseek) {
+ if (!BN_add_word(seq, 1))
+ goto cmb_bn_return;
+ retval = action_bn(config, seq, 0, NULL);
+ if (retval != 0)
+ goto cmb_bn_return;
+ if (docount) {
+ if (!BN_sub_word(count, 1))
+ goto cmb_bn_return;
+ if (BN_is_zero(count))
+ goto cmb_bn_return;
+ }
+ } else {
+ if (!BN_sub_word(seek, 1))
+ goto cmb_bn_return;
+ if (BN_is_one(seek))
+ doseek = FALSE;
+ }
+ }
+
+ if (n_items == 0)
+ goto cmb_bn_return;
+
+ /* Allocate memory */
+ if ((combo = BN_new()) == NULL)
+ goto cmb_bn_return;
+ if ((ncombos = BN_new()) == NULL)
+ goto cmb_bn_return;
+ if (!BN_one(ncombos))
+ goto cmb_bn_return;
+ setmax = setdone > setinit ? setdone : setinit;
+ if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ if ((setnums_backend =
+ (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+
+ /*
+ * Loop over each `set' in the configured direction until we are done.
+ * NB: Each `set' can represent a single item or multiple items.
+ */
+ p = nextset > 0 ? setinit - 1 : setinit;
+ for (k = 1; k <= p; k++) {
+ if (!BN_mul_word(ncombos, i--))
+ goto cmb_bn_return;
+ if (BN_div_word(ncombos, k) == (BN_ULONG)-1)
+ goto cmb_bn_return;
+ }
+ for (curset = setinit;
+ nextset > 0 ? curset <= setdone : curset >= setdone;
+ curset += (uint32_t)nextset)
+ {
+#if CMB_DEBUG
+ if (debug)
+ cmb_debug(">>> %u-item combinations <<<", curset);
+#endif
+
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0) {
+ if (!BN_mul_word(ncombos, i--))
+ break;
+ if (BN_div_word(ncombos, k++) == (BN_ULONG)-1)
+ break;
+ }
+
+ /* Jump to next set if requested start is beyond this one */
+ if (doseek) {
+ if (BN_ucmp(seek, ncombos) > 0) {
+ if (!BN_sub(seek, seek, ncombos))
+ break;
+ if (nextset < 0) {
+ if (!BN_mul_word(ncombos, --k))
+ break;
+ if (BN_div_word(ncombos, ++i) ==
+ (BN_ULONG)-1)
+ break;
+ }
+ continue;
+ } else if (BN_is_one(seek)) {
+ doseek = FALSE;
+ }
+ }
+
+ /* Fill array with the initial positional arguments */
+#if CMB_DEBUG
+ if (debug)
+ fprintf(stderr, CMB_DEBUG_PREFIX "setnums=[");
+#endif
+ for (n = 0; n < curset; n++) {
+#if CMB_DEBUG
+ if (debug) {
+ if (n == curset - 1)
+ fprintf(stderr, "\033[31m%u\033[m", n);
+ else
+ fprintf(stderr, "%u", n);
+ if (n + 1 < curset)
+ fprintf(stderr, ",");
+ }
+#endif
+ curitems[n] = items[n];
+ }
+#if CMB_DEBUG
+ if (debug) {
+ seq_str = BN_bn2dec(seq);
+ fprintf(stderr, "] seq=%s\n", seq_str);
+ OPENSSL_free(seq_str);
+ }
+#endif
+
+ /* Produce results with the first set of items */
+ if (!doseek) {
+ if (!BN_add_word(seq, 1))
+ goto cmb_bn_return;
+ retval = action_bn(config, seq, curset, curitems);
+ if (retval != 0)
+ break;
+ if (docount) {
+ if (!BN_sub_word(count, 1))
+ break;
+ if (BN_is_zero(count))
+ break;
+ }
+ }
+
+ /*
+ * Prefill two arrays used for matrix calculations.
+ *
+ * The first array (setnums) is a linear sequence starting at
+ * one (1) and ending at N (where N is the same integer as the
+ * current set we're operating on). For example, if we are
+ * currently on a set-of-2, setnums is 1, 2.
+ *
+ * The second array (setnums_backend) is a linear sequence
+ * starting at n_items-N and ending at n_items (again, N is the
+ * same integer as the current set we are operating on; n_items
+ * is the total number of items). For example, if we are
+ * operating on a set-of-2, and n_items is 8, setnums_backend is
+ * set to 7, 8.
+ */
+ p = 0;
+ for (n = 0; n < curset; n++)
+ setnums[n] = n;
+ for (n = curset; n > 0; n--)
+ setnums_backend[p++] = n_items - n;
+
+ /*
+ * Process remaining self-similar combinations in the set.
+ */
+ if (!BN_one(combo))
+ break;
+ for (; BN_ucmp(combo, ncombos) < 0; ) {
+ setnums_last = curset;
+
+ /*
+ * Using self-similarity (matrix) theorem, determine
+ * (by comparing the [sliding] setnums to the stored
+ * setnums_backend) the number of arguments that remain
+ * available for shifting into a new setnums value
+ * (for later mapping into curitems).
+ *
+ * In essence, determine when setnums has slid into
+ * setnums_backend in which case we can mathematically
+ * use the last item to find the next-new item.
+ */
+ for (n = curset; n > 0; n--) {
+ setpos = setnums[n - 1];
+ setpos_backend = setnums_backend[n - 1];
+ /*
+ * If setpos is equal to or greater than
+ * setpos_backend then we keep iterating over
+ * the current set's list of argument positions
+ * until otherwise; each time incrementing the
+ * amount of numbers we must produce from
+ * formulae rather than stored position.
+ */
+ setnums_last = n - 1;
+ if (setpos < setpos_backend)
+ break;
+ }
+
+ /*
+ * The next few stanzas are dedicated to rebuilding the
+ * setnums array for mapping positional items
+ * [immediately following] into curitems.
+ */
+
+ /*
+ * Get the generator number used to populate unknown
+ * positions in the matrix (using self-similarity).
+ */
+ seed = setnums[setnums_last];
+
+ /*
+ * Use the generator number to populate any position
+ * numbers that weren't carried over from previous
+ * combination run -- using self-similarity theorem.
+ */
+ for (n = setnums_last; n <= curset; n++)
+ setnums[n] = seed + n - setnums_last + 1;
+#if CMB_DEBUG
+ if (debug) {
+ fprintf(stderr, CMB_DEBUG_PREFIX "setnums=[");
+ for (n = 0; n < curset; n++) {
+ if (n == setnums_last) {
+ fprintf(stderr,
+ "\033[31m%u\033[m",
+ setnums[n]);
+ } else {
+ fprintf(stderr, "%u",
+ setnums[n]);
+ }
+ if (n + 1 < curset)
+ fprintf(stderr, ",");
+ }
+ seq_str = BN_bn2dec(seq);
+ fprintf(stderr, "] seq=%s\n", seq_str);
+ OPENSSL_free(seq_str);
+ }
+#endif
+
+ /* Now map new setnums into values stored in items */
+ for (n = 0; n < curset; n++)
+ curitems[n] = items[setnums[n]];
+
+ /* Produce results with this set of items */
+ if (doseek) {
+ if (!BN_sub_word(seek, 1))
+ goto cmb_bn_return;
+ if (BN_is_one(seek))
+ doseek = FALSE;
+ }
+ if (!doseek || BN_is_one(seek)) {
+ doseek = FALSE;
+ if (!BN_add_word(seq, 1))
+ goto cmb_bn_return;
+ retval = action_bn(config, seq, curset,
+ curitems);
+ if (retval != 0)
+ goto cmb_bn_return;
+ if (docount) {
+ if (!BN_sub_word(count, 1))
+ goto cmb_bn_return;
+ if (BN_is_zero(count))
+ goto cmb_bn_return;
+ }
+ }
+
+ if (!BN_add_word(combo, 1))
+ goto cmb_bn_return;
+
+ } /* for combo */
+
+ /* Calculate number of combinations (decrementing) */
+ if (nextset < 0) {
+ if (!BN_mul_word(ncombos, --k))
+ break;
+ if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1)
+ break;
+ }
+
+ } /* for curset */
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset < 0 && show_empty) {
+ if ((!doseek || BN_is_one(seek)) &&
+ (!docount || !BN_is_zero(count))) {
+ if (!BN_add_word(seq, 1))
+ goto cmb_bn_return;
+ retval = action_bn(config, seq, 0, NULL);
+ }
+ }
+
+cmb_bn_return:
+ BN_free(combo);
+ BN_free(count);
+ BN_free(ncombos);
+ BN_free(seek);
+ BN_free(seq);
+
+ return (retval);
+}
+
+CMB_ACTION_BN(cmb_print_bn)
+{
+ uint8_t nul = FALSE;
+ uint8_t show_numbers = FALSE;
+ uint32_t n;
+ char *seq_str;
+ const char *delimiter = " ";
+ const char *prefix = NULL;
+ const char *suffix = NULL;
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->delimiter != NULL)
+ delimiter = config->delimiter;
+ if ((config->options & CMB_OPT_NULPRINT) != 0)
+ nul = TRUE;
+ if ((config->options & CMB_OPT_NUMBERS) != 0)
+ show_numbers = TRUE;
+ prefix = config->prefix;
+ suffix = config->suffix;
+ }
+
+ if (show_numbers) {
+ seq_str = BN_bn2dec(seq);
+ printf("%s ", seq_str);
+ OPENSSL_free(seq_str);
+ }
+ if (prefix != NULL)
+ printf("%s", prefix);
+ for (n = 0; n < n_items; n++) {
+ printf("%s", items[n]);
+ if (n < n_items - 1)
+ printf("%s", delimiter);
+ }
+ if (suffix != NULL)
+ printf("%s", suffix);
+ if (nul)
+ printf("%c", 0);
+ else
+ printf("\n");
+
+ return (0);
+}
+#endif /* HAVE_OPENSSL_BN_H */
diff --git a/lib/libcmb/cmb_private.h b/lib/libcmb/cmb_private.h
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/cmb_private.h
@@ -0,0 +1,38 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#ifndef _CMB_PRIVATE_H_
+#define _CMB_PRIVATE_H_
+
+/* Limits */
+#define BUFSIZE_MAX (2 * 1024 * 1024)
+ /* Buffer size for read(2) input */
+#ifndef MAXPHYS
+#define MAXPHYS (128 * 1024)
+ /* max raw I/O transfer size */
+#endif
+
+/*
+ * Memory strategy threshold, in pages: if physmem is larger than this,
+ * use a large buffer.
+ */
+#define PHYSPAGES_THRESHOLD (32 * 1024)
+
+/*
+ * Small (default) buffer size in bytes. It's inefficient for this to be
+ * smaller than MAXPHYS.
+ */
+#define BUFSIZE_SMALL (MAXPHYS)
+
+/*
+ * Math macros
+ */
+#undef MIN
+#define MIN(x,y) ((x) < (y) ? (x) : (y))
+#undef MAX
+#define MAX(x,y) ((x) > (y) ? (x) : (y))
+
+#endif /* !_CMB_PRIVATE_H_ */
diff --git a/lib/libcmb/tests/Makefile b/lib/libcmb/tests/Makefile
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/Makefile
@@ -0,0 +1,17 @@
+.include <src.opts.mk>
+
+PACKAGE= tests
+
+TESTSDIR= ${TESTSBASE}/lib/libcmb
+
+PLAIN_TESTS_C= test1 test2 test3 test4 test5 test6
+WARNS?= 2
+
+CFLAGS+= -I${.CURDIR:H}
+LIBADD+= cmb m
+
+.if ${MK_OPENSSL} != "no"
+LIBADD+= crypto
+.endif
+
+.include <bsd.test.mk>
diff --git a/lib/libcmb/tests/test1.c b/lib/libcmb/tests/test1.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test1.c
@@ -0,0 +1,83 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <cmb.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static int num_calls = 0;
+static int
+afunc(struct cmb_config *config __unused, uint64_t seq __unused,
+ uint32_t n_items __unused, char *items[] __unused)
+{
+ num_calls++;
+ return (0);
+}
+
+int
+main(void)
+{
+ uint32_t n_items = 4;
+ int retval;
+ uint64_t seq = 1;
+ char *items[] = {
+ __DECONST(char *, "a"),
+ __DECONST(char *, "b"),
+ __DECONST(char *, "c"),
+ __DECONST(char *, "d"),
+ };
+ char itemstr[] = "a, b, c, d";
+ static struct cmb_config config = {
+ .options = CMB_OPT_NUMBERS,
+ .delimiter = __DECONST(char *, ","),
+ .prefix = __DECONST(char *, "\t["),
+ .suffix = __DECONST(char *, "]"),
+ .size_min = 2,
+ .size_max = 3,
+ .count = 6,
+ .start = 4,
+ };
+
+ printf("config = {\n");
+ printf("\t.options = 0x%08x,\n", config.options);
+ printf("\t.delimiter = \"%s\",\n", config.delimiter);
+ printf("\t.prefix = \"%s\",\n", config.prefix);
+ printf("\t.suffix = \"%s\",\n", config.suffix);
+ printf("\t.size_min = %u,\n", config.size_min);
+ printf("\t.size_max = %u,\n", config.size_max);
+ printf("\t.count = %"PRIu64",\n", config.count);
+ printf("\t.start = %"PRIu64",\n", config.start);
+ printf("}\n");
+
+ printf("cmb_version(%u): %s\n", CMB_VERSION, cmb_version(CMB_VERSION));
+ printf("cmb_version(%u): %s\n", CMB_VERSION_LONG,
+ cmb_version(CMB_VERSION_LONG));
+ printf("size_min=%u size_max=%u\n", config.size_min, config.size_max);
+ printf("cmb_count(config, %u) = %"PRIu64"\n", n_items,
+ cmb_count(&config, n_items));
+ printf("cmb_print(config, %"PRIu64", %u, [%s]):\n", seq, n_items,
+ itemstr);
+ retval = cmb_print(&config, seq, n_items, items);
+ printf("\tRESULT: %i\n", retval);
+ printf("cmb(config, %u, [%s]):\n", n_items, itemstr);
+ printf("NOTE: { .start = %"PRIu64", .count = %"PRIu64" }\n",
+ config.start, config.count);
+ retval = cmb(&config, n_items, items);
+ printf("\tRESULT: %i\n", retval);
+
+ /*
+ * Callbacks
+ */
+ config.options = 0;
+ config.action = afunc;
+ printf("cmb_callback(config, %u, [%s], afunc):\n", n_items, itemstr);
+ retval = cmb(&config, n_items, items);
+ printf("\tnum_calls: %i\n", num_calls);
+ printf("\tRESULT: %i\n", retval);
+
+ return (EXIT_SUCCESS);
+}
diff --git a/lib/libcmb/tests/test2.c b/lib/libcmb/tests/test2.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test2.c
@@ -0,0 +1,53 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <cmb.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define CHOICE 2
+#define NITEMS 10000
+
+static int total = 0;
+
+static int
+afunc(struct cmb_config *config __unused, uint64_t seq __unused,
+ uint32_t n_items __unused, char *items[] __unused)
+{
+ total++;
+ return (0);
+}
+
+int
+main(void)
+{
+ static struct cmb_config config = {
+ .size_min = CHOICE,
+ .size_max = CHOICE,
+ .action = afunc,
+ };
+ char *items[NITEMS];
+ int retval;
+ uint64_t expected;
+
+ expected = cmb_count(&config, NITEMS);
+ printf("Silently enumerating choose-%u from %u items:\n", CHOICE,
+ NITEMS);
+ retval = cmb(&config, NITEMS, items);
+ printf("\t%"PRIu64" combinations enumerated\n", (uint64_t)total);
+ if (retval != 0 || (uint64_t)total != expected) {
+ printf("\tEXPECTED: %"PRIu64" combinations, cmb returned 0\n",
+ expected);
+ printf("\tGOT: %"PRIu64" combinations, cmb returned %i\n",
+ (uint64_t)total, retval);
+ printf("\tRESULT: 1\n");
+ return (EXIT_FAILURE);
+ }
+ printf("\tRESULT: 0\n");
+
+ return (EXIT_SUCCESS);
+}
diff --git a/lib/libcmb/tests/test3.c b/lib/libcmb/tests/test3.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test3.c
@@ -0,0 +1,45 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <cmb.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static int
+afunc(struct cmb_config *config __unused, uint64_t seq __unused,
+ uint32_t n_items, char *items[])
+{
+ int i;
+
+ printf("\t");
+ for (i = 0; i < (int)n_items; i++)
+ printf("%s%s", items[i], i < (int)(n_items - 1) ? " " : "");
+ printf("\n");
+
+ return (0);
+}
+
+int
+main(void)
+{
+ int n_items = 4;
+ char *items[] = {
+ __DECONST(char *, "a"),
+ __DECONST(char *, "b"),
+ __DECONST(char *, "c"),
+ __DECONST(char *, "d"),
+ };
+ static struct cmb_config config = {
+ .size_min = 2,
+ .size_max = 2,
+ .action = afunc,
+ };
+
+ printf("Enumerating choose-2 from [a, b, c, d] (%u) items:\n", n_items);
+ (void)cmb(&config, n_items, items);
+
+ return (EXIT_SUCCESS);
+}
diff --git a/lib/libcmb/tests/test4.c b/lib/libcmb/tests/test4.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test4.c
@@ -0,0 +1,91 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <sys/types.h>
+#include <sys/wait.h>
+
+#include <cmb.h>
+#include <err.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#define CHOICE 2
+#define NITEMS 10000
+
+static int pfd[2] = { 0, 0 };
+
+static int
+afunc(struct cmb_config *config __unused, uint64_t seq __unused,
+ uint32_t n_items, char *items[])
+{
+ uint32_t i;
+
+ for (i = 0; i < n_items; i++)
+ printf("%s%s", items[i], i < (n_items - 1) ? " " : "");
+ printf("\n");
+
+ return (0);
+}
+
+int
+main(void)
+{
+ uint32_t i;
+ pid_t pid;
+ int status;
+ static struct cmb_config config = {
+ .size_min = CHOICE,
+ .size_max = CHOICE,
+ .action = afunc,
+ };
+ char *items[NITEMS];
+ char count_arg[23];
+
+ printf("Enumerating choose-%u from %u via bsdpv(1) line mode:\n",
+ CHOICE, NITEMS);
+
+ if (pipe(pfd) != 0)
+ err(EXIT_FAILURE, "pipe");
+
+ if ((pid = fork()) == 0) { /* child */
+ dup2(pfd[0], STDIN_FILENO);
+ close(pfd[0]);
+ close(pfd[1]);
+ (void)snprintf(count_arg, sizeof(count_arg), "%"PRIu64":c",
+ cmb_count(&config, NITEMS));
+ execlp("bsdpv", "bsdpv", "-l", count_arg, NULL);
+ err(EXIT_FAILURE, "bsdpv");
+ /* NOTREACHED */
+ }
+ /* parent */
+
+ dup2(pfd[1], STDOUT_FILENO);
+ close(pfd[0]);
+ close(pfd[1]);
+
+ for (i = 0; i < NITEMS; i++) {
+ items[i] = (char *)calloc(1, 11);
+ if (items[i] == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ (void)snprintf(items[i], 11, "%u", i);
+ }
+ (void)cmb(&config, NITEMS, items);
+
+ fflush(stdout);
+ close(STDOUT_FILENO);
+ if (waitpid(pid, &status, 0) < 0)
+ err(EXIT_FAILURE, "waitpid");
+ if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
+ fprintf(stderr, "\tRESULT: FAIL (bsdpv status %d)\n", status);
+ return (EXIT_FAILURE);
+ }
+
+ fprintf(stderr, "\tRESULT: 0\n");
+ return (EXIT_SUCCESS);
+}
diff --git a/lib/libcmb/tests/test5.c b/lib/libcmb/tests/test5.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test5.c
@@ -0,0 +1,50 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <cmb.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static int total = 0;
+
+static int
+afunc(struct cmb_config *config __unused, uint64_t seq __unused,
+ uint32_t n_items __unused, char *items[] __unused)
+{
+ return (total++);
+}
+
+int
+main(void)
+{
+ static struct cmb_config config = {
+ .action = afunc,
+ };
+ int n_items = 3;
+ int retval;
+ uint64_t expected;
+ char *items[] = {
+ __DECONST(char *, "a"),
+ __DECONST(char *, "b"),
+ __DECONST(char *, "c"),
+ };
+
+ expected = cmb_count(&config, n_items);
+ printf("Testing non-zero callback return:\n");
+ printf("NOTE: callback returns 0 first call, then non-zero to stop\n");
+ retval = cmb(&config, n_items, items);
+ printf("\t%u of %"PRIu64" callbacks executed\n", total, expected);
+ printf("\tcmb returned %i (expected early stop)\n", retval);
+ if (total != 2 || retval != 1) {
+ printf("\tEXPECTED: 2 callbacks, cmb returned 1\n");
+ printf("\tRESULT: 1\n");
+ return (EXIT_FAILURE);
+ }
+ printf("\tRESULT: 0\n");
+
+ return (EXIT_SUCCESS);
+}
diff --git a/lib/libcmb/tests/test6.c b/lib/libcmb/tests/test6.c
new file mode 100644
--- /dev/null
+++ b/lib/libcmb/tests/test6.c
@@ -0,0 +1,58 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+/*
+ * Combinatorial sum-to-target via libcmb(3) transform-find macros.
+ * Equivalent to: cmb -X add -F 4 -r 3
+ */
+
+#include <cmb.h>
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* Required by CMB_TRANSFORM_* macros (same role as in cmb(1)). */
+static uint8_t opt_quiet = FALSE;
+static uint8_t opt_silent = FALSE;
+
+static CMB_TRANSFORM_OP_FIND(+, cmb_add_find);
+
+int
+main(void)
+{
+ uint32_t n_items = 3;
+ int retval;
+ struct cmb_xitem x1 = { .cp = __DECONST(char *, "1"), .as.ld = 1 };
+ struct cmb_xitem x2 = { .cp = __DECONST(char *, "2"), .as.ld = 2 };
+ struct cmb_xitem x3 = { .cp = __DECONST(char *, "3"), .as.ld = 3 };
+ char *items[] = {
+ (char *)&x1,
+ (char *)&x2,
+ (char *)&x3,
+ };
+ struct cmb_xitem find = { .cp = __DECONST(char *, "4"), .as.ld = 4 };
+ struct cmb_config config = {
+ .action = cmb_add_find,
+ };
+
+ cmb_transform_find = &find;
+ cmb_transform_precision = 0;
+
+ printf("Finding combinations of [1, 2, 3] (%u) items that sum to 4:\n",
+ n_items);
+ printf("NOTE: equivalent to `cmb -X add -F 4 -r 3'\n");
+ printf("EXPECTED: 1 + 3 = 4\n");
+ retval = cmb(&config, n_items, items);
+ if (retval != 0) {
+ printf("\tcmb returned %i\n", retval);
+ printf("\tRESULT: 1\n");
+ return (EXIT_FAILURE);
+ }
+ printf("\tRESULT: 0\n");
+
+ return (EXIT_SUCCESS);
+}
diff --git a/share/mk/bsd.libnames.mk b/share/mk/bsd.libnames.mk
--- a/share/mk/bsd.libnames.mk
+++ b/share/mk/bsd.libnames.mk
@@ -37,6 +37,7 @@
LIBC?= ${LIBDESTDIR}${LIBDIR_BASE}/libc.a
LIBCALENDAR?= ${LIBDESTDIR}${LIBDIR_BASE}/libcalendar.a
LIBCAM?= ${LIBDESTDIR}${LIBDIR_BASE}/libcam.a
+LIBCMB?= ${LIBDESTDIR}${LIBDIR_BASE}/libcmb.a
LIBCOMPAT?= ${LIBDESTDIR}${LIBDIR_BASE}/libcompat.a
LIBCOMPILER_RT?=${LIBDESTDIR}${LIBDIR_BASE}/libcompiler_rt.a
LIBCOM_ERR?= ${LIBDESTDIR}${LIBDIR_BASE}/libcom_err.a
diff --git a/share/mk/src.libnames.mk b/share/mk/src.libnames.mk
--- a/share/mk/src.libnames.mk
+++ b/share/mk/src.libnames.mk
@@ -135,6 +135,7 @@
cap_pwd \
cap_sysctl \
cap_syslog \
+ cmb \
com_err \
compiler_rt \
crypt \
@@ -392,6 +393,10 @@
_DP_magic= z
_DP_memstat= kvm
_DP_mp= crypto
+_DP_cmb= m
+.if ${MK_OPENSSL} != "no"
+_DP_cmb+= crypto
+.endif
_DP_mt= sbuf bsdxml
_DP_ncursesw= tinfow
_DP_netmap=
@@ -719,6 +724,7 @@
LIBPKGECCDIR= ${_LIB_OBJTOP}/secure/lib/libpkgecc
LIBPKGECC?= ${LIBPKGECCDIR}/libpkgecc${PIE_SUFFIX}.a
+
LIBPMCSTATDIR= ${_LIB_OBJTOP}/lib/libpmcstat
LIBPMCSTAT?= ${LIBPMCSTATDIR}/libpmcstat${PIE_SUFFIX}.a
diff --git a/usr.bin/Makefile b/usr.bin/Makefile
--- a/usr.bin/Makefile
+++ b/usr.bin/Makefile
@@ -17,6 +17,7 @@
chat \
chpass \
cksum \
+ cmb \
cmp \
col \
colrm \
diff --git a/usr.bin/cmb/Makefile b/usr.bin/cmb/Makefile
new file mode 100644
--- /dev/null
+++ b/usr.bin/cmb/Makefile
@@ -0,0 +1,15 @@
+.include <src.opts.mk>
+
+PROG= cmb
+MAN= cmb.1
+
+CFLAGS+= -I${SRCTOP}/lib/libcmb
+
+LIBADD+= cmb m
+
+.if ${MK_OPENSSL} != "no"
+CFLAGS+= -DHAVE_LIBCRYPTO
+LIBADD+= crypto
+.endif
+
+.include <bsd.prog.mk>
diff --git a/usr.bin/cmb/cmb.1 b/usr.bin/cmb/cmb.1
new file mode 100644
--- /dev/null
+++ b/usr.bin/cmb/cmb.1
@@ -0,0 +1,375 @@
+.\" Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+.\"
+.\" SPDX-License-Identifier: BSD-2-Clause
+.\"
+.Dd July 28, 2026
+.Dt CMB 1
+.Os
+.Sh NAME
+.Nm cmb
+.Nd combinatorics utility
+.Sh SYNOPSIS
+.Nm
+.Op Fl 0DefNorStvz
+.Op Fl c Ar num
+.Op Fl d Ar str
+.Op Fl F Ar num
+.Op Fl i Ar num
+.Op Fl k Ar size
+.Op Fl n Ar num
+.Op Fl P Ar num
+.Op Fl p Ar str
+.Op Fl s Ar str
+.Op Fl X Ar op
+.Op Ar item Ar ...
+.Sh DESCRIPTION
+The
+.Nm
+utility prints combinations,
+one per line
+.Pq default ,
+with items in each combination separated by space
+.Pq default .
+Given N items on the command line,
+there are N sets where each set consists of an increasing number of items
+.Pq default .
+By default,
+all sets are produced
+.Pq Ql Li -k 0 .
+Combination order within a set of N items is always consistent and repeatable
+given the order of items on the command line.
+The order of combinations within a single set of N items
+.Pq where every combination in the set has the same number of items
+is dependent upon the order of items on the command line.
+.Pp
+Available options:
+.Bl -tag -width "-r range"
+.It Fl 0
+Change the behavior of
+.Ql Fl f
+to read items separated by a NUL character
+.Pq character code 0
+instead of newline.
+.It Fl c Ar num
+Produce at most
+.Ar num
+combinations.
+If
+.Ql 0
+.Pq default
+all combinations produced.
+Ignored when given
+.Ql Fl t .
+.It Fl D
+Enable debugging information on stderr.
+See
+.Xr cmb 3 .
+.It Fl d Ar text
+Delimiter for separating items.
+Default is space
+.Pq Dq " " .
+Ignored when given
+.Ql Fl t .
+.It Fl e
+Show empty set.
+A single combination containing no items.
+.It Fl F Ar num
+Find
+.Sq Fl X Ar op
+values that equal
+.Ar num .
+Requires
+.Sq Fl X Ar op .
+.It Fl f
+Treat each command line argument as a file containing items,
+one item per line
+.Pq default .
+With
+.Ql Fl 0 ,
+read items separated by a NUL character.
+If an argument is
+.Ql Li - ,
+read from stdin.
+The sum of items read from all files cannot exceed 4294967295
+.Pq 2^32-1 .
+.It Fl i Ar num
+Skip the first
+.Va num-1
+combinations.
+If
+.Va num
+is negative,
+skip to
+.Va |num|
+combinations before the end.
+If
+.Va num
+matches
+.Ql Li random
+.Pq case-sensitive
+a random number between 1 and the total number of combinations is chosen.
+Ignored when given
+.Ql Fl t .
+.It Fl k Ar size
+Number or range
+.Pq Qo min..max Qc or Qo min-max Qc
+of how many items must appear in each combination.
+A value of
+.Ql 0
+.Pq default
+calculates all sets starting with 1-item combinations.
+If
+.Va size
+is negative one
+.Pq Li -1 ,
+calculate sets in descending order,
+starting with the maximum number of items.
+A range of
+.Ql Li -1..N
+will do the same but stop at N-item combinations.
+A range of
+.Ql Li N..-1
+will start with N-item combinations and end with the maximum number of items.
+The order of combinations in each set is unaffected by negative
+.Va size
+values.
+A range of
+.Ql Li -1..-1
+calculates the ending set consisting of only the maximum number of items.
+.It Fl N
+Show combination sequence numbers.
+Combinations are calculated in arithmetic progression,
+providing predictable order.
+The sequence number can be used as a value to
+.Ql Fl i Ar num
+to start at that combination.
+Ignored when given
+.Ql Fl t .
+.It Fl n Ar num
+Limit the number of arguments taken from the command line.
+No effect if
+.Va num
+is greater than the number of arguments.
+.It Fl o
+Disable OpenSSL
+.Xr bn 3
+support
+.Pq limits calculations to 64-bits .
+No effect if unsupported.
+Use
+.Ql Fl v
+to check OpenSSL support.
+The default is to use OpenSSL when supported.
+Must appear before
+.Ql Fl c Ar num
+and
+.Ql Fl i Ar num
+options.
+.It Fl P Ar num
+Change the behavior of
+.Ql Fl X Ar op
+to use
+.Ar num
+units of precision when printing floating point results.
+Default behavior of
+.Ql Fl X Ar op
+is to use the highest precision of provided arguments.
+Ignored when given
+.Ql Fl t .
+.It Fl p Ar text
+Prefix each combination with
+.Ar text .
+Ignored when given
+.Ql Fl t .
+.It Fl q
+Quiet.
+Do not print items from set when given
+.Ql Fl X Ar op .
+.It Fl r
+Treat each command line argument as a number or range to be expanded.
+If a single number,
+expand to numbers 1 to num.
+If a range
+.Pq Qo min..max Qc or Qo min-max Qc ,
+expand to numbers min to max.
+Numbers must be integers between 0 and 4294967295
+.Pq 2^32-1 .
+.It Fl S
+Silent.
+Do not print combinations to stdout.
+Used with
+.Xr time 1
+to determine
+.Xr stdio 3
+overhead.
+With
+.Ql Fl t ,
+do not print result.
+.It Fl s Ar text
+Suffix each combination with
+.Ar text .
+Ignored when given
+.Ql Fl t .
+.It Fl t
+Print total number of combinations and exit.
+.It Fl v
+Print version information to stdout and exit.
+Includes
+.Xr cmb 3
+library version and
+.Pq if enabled
+.Xr SSL 3
+library version.
+.It Fl X Ar op
+Perform math on items where
+.Ar op
+is
+.Ql Li add ,
+.Ql Li subtract ,
+.Ql Li divide ,
+or
+.Ql Li multiply
+.Pq case-sensitive .
+Argument
+.Ar op
+can be shortened to its minimally distinct representation;
+such as
+.Ql Li a
+for
+.Ql Li add .
+Ignored when given
+.Ql Fl t .
+.It Fl z
+Print combinations followed by an ASCII NUL character
+.Pq character code 0
+instead of newline
+.Pq character code 10 .
+With
+.Ql Fl t ,
+do not print a trailing character after the result.
+.El
+.Sh EXAMPLES
+Print all two-word combinations
+.Pq Qo bird dog Qc , Qo bird house Qc , and Qo dog house Qc
+given
+.Qq bird ,
+.Qq dog ,
+and
+.Qq house :
+.Bd -literal -offset indent
+cmb -k 2 bird dog house
+.Ed
+.Pp
+Print number of combinations
+.Pq 7
+given
+.Qq a ,
+.Qq b ,
+and
+.Qq c :
+.Bd -literal -offset indent
+cmb -t a b c
+.Ed
+.Pp
+Print first 5 combinations
+.Pq Qo x Qc , Qo y Qc , Qo z Qc , Qo x y Qc , and Qo x z Qc
+given
+.Qq x ,
+.Qq y ,
+and
+.Qq z :
+.Bd -literal -offset indent
+cmb -c 5 x y z
+.Ed
+.Pp
+Skip first 3 combinations
+.Pq Qo x Qc , Qo y Qc , and Qo z Qc
+given
+.Qq x ,
+.Qq y ,
+and
+.Qq z :
+.Bd -literal -offset indent
+cmb -i 4 x y z
+.Ed
+.Pp
+Print last 5 combinations
+.Pq Qo z Qc , Qo x y Qc , Qo x z Qc , Qo y z Qc , and Qo x y z Qc
+given
+.Qq x ,
+.Qq y ,
+and
+.Qq z :
+.Bd -literal -offset indent
+cmb -i -5 x y z
+.Ed
+.Pp
+Print items separated by comma instead of space:
+.Bd -literal -offset indent
+cmb -d , a b c
+.Ed
+.Pp
+Print numbers as JSON:
+.Bd -literal -offset indent
+cmb -p '{"values":[' -s ']}' -d , 1 2 3
+.Ed
+.Pp
+Print strings as JSON:
+.Bd -literal -offset indent
+cmb -p '{"values":[' -s ']}' -d , '"a"' '"b"' '"c"'
+.Ed
+.Pp
+Print all 2- and 3-word combinations
+.Po
+.Qq big blue ,
+.Qq big red ,
+.Qq big couch ,
+.Qq blue red ,
+.Qq blue couch ,
+.Qq red couch ,
+.Qq big blue red ,
+.Qq big blue couch ,
+.Qq big red couch ,
+and
+.Qq blue red couch
+.Pc
+given
+.Qq big ,
+.Qq blue ,
+.Qq red ,
+and
+.Qq couch :
+.Bd -literal -offset indent
+cmb -k 2..3 big blue red couch
+.Ed
+.Pp
+Print combinations starting with the maximum number of items
+.Pq 3 ,
+ending with 2-item combinations:
+.Bd -literal -offset indent
+cmb -k -1..2 1 2 3
+.Ed
+.Pp
+Print combinations starting with 2 items ending with maximum items
+.Pq 3 :
+.Bd -literal -offset indent
+cmb -k 2..-1 x y z
+.Ed
+.Pp
+Roll a set of 2 six-sided dice,
+producing a single random combination of two numbers:
+.Bd -literal -offset indent
+cmb -c 1 -k 2 -i rand -r 6 6
+.Ed
+.Pp
+Find all combinations of numbers 1, 2, and 3 that produce the sum of 4:
+.Bd -literal -offset indent
+cmb -X add -F 4 -r 3
+.Ed
+.Sh HISTORY
+The
+.Nm
+utility first appeared in
+.Fx 16.0 .
+.Sh AUTHORS
+.An Devin Teske Aq Mt dteske@FreeBSD.org
diff --git a/usr.bin/cmb/cmb.c b/usr.bin/cmb/cmb.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/cmb/cmb.c
@@ -0,0 +1,1191 @@
+/*-
+ * Copyright (c) 2018-2026 Devin Teske <dteske@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <sys/param.h>
+#include <sys/time.h>
+
+#include <cmb.h>
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+#include <openssl/err.h>
+#endif
+#include <err.h>
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#ifndef UINT_MAX
+#define UINT_MAX 0xFFFFFFFF
+#endif
+
+static char version[] = "$Version: 3.10.0 $";
+
+/* Environment */
+static char *pgm; /* set to argv[0] by main() */
+
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static void
+openssl_err(const char *label)
+{
+ unsigned long e;
+ char errbuf[256];
+
+ e = ERR_get_error();
+ if (e == 0)
+ errx(EXIT_FAILURE, "%s", label);
+ ERR_error_string_n(e, errbuf, sizeof(errbuf));
+ errx(EXIT_FAILURE, "%s: %s", label, errbuf);
+}
+#endif
+
+/* Globals */
+static uint8_t opt_quiet = FALSE;
+static uint8_t opt_silent = FALSE;
+static const char digit[11] = "0123456789";
+
+#ifndef _Noreturn
+#define _Noreturn __attribute__((noreturn))
+#endif
+
+/* Function prototypes */
+static void _Noreturn cmb_usage(void);
+static uint64_t cmb_rand_range(uint64_t range);
+static CMB_ACTION(cmb_add);
+static CMB_ACTION(cmb_div);
+static CMB_ACTION(cmb_mul);
+static CMB_ACTION(cmb_nop);
+static CMB_ACTION(cmb_sub);
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static CMB_ACTION_BN(cmb_add_bn);
+static CMB_ACTION_BN(cmb_div_bn);
+static CMB_ACTION_BN(cmb_mul_bn);
+static CMB_ACTION_BN(cmb_nop_bn);
+static CMB_ACTION_BN(cmb_sub_bn);
+#endif
+static CMB_ACTION(cmb_add_find);
+static CMB_ACTION(cmb_div_find);
+static CMB_ACTION(cmb_mul_find);
+static CMB_ACTION(cmb_sub_find);
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static CMB_ACTION_BN(cmb_add_find_bn);
+static CMB_ACTION_BN(cmb_div_find_bn);
+static CMB_ACTION_BN(cmb_mul_find_bn);
+static CMB_ACTION_BN(cmb_sub_find_bn);
+#endif
+static size_t numlen(const char *s);
+static size_t rangelen(const char *s, size_t nlen, size_t slen);
+static size_t unumlen(const char *s);
+static size_t urangelen(const char *s, size_t nlen, size_t slen);
+static uint8_t parse_range(const char *s, uint32_t *min, uint32_t *max);
+static uint8_t parse_unum(const char *s, uint32_t *n);
+static uint8_t parse_urange(const char *s, uint32_t *min, uint32_t *max);
+static uint32_t range_char(uint32_t start, uint32_t stop, uint32_t idx,
+ char *dst[]);
+static uint32_t range_float(uint32_t start, uint32_t stop, uint32_t idx,
+ char *dst[]);
+
+/* Inline functions */
+static inline uint8_t p2(uint64_t x) { return (x == (x & -x)); }
+static inline uint64_t urand64(void) { return (((uint64_t)lrand48() << 42)
+ + ((uint64_t)lrand48() << 21) + (uint64_t)lrand48());
+}
+
+/*
+ * Transformations (-X op)
+ */
+struct cmb_xfdef
+{
+ const char *opname;
+ CMB_ACTION((*action));
+ CMB_ACTION((*action_find));
+};
+static struct cmb_xfdef cmb_xforms[] = {
+ /* opname action */
+ {"multiply", cmb_mul, cmb_mul_find},
+ {"divide", cmb_div, cmb_div_find},
+ {"add", cmb_add, cmb_add_find},
+ {"subtract", cmb_sub, cmb_sub_find},
+ {NULL, NULL, NULL},
+};
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+struct cmb_xfdef_bn
+{
+ const char *opname;
+ CMB_ACTION_BN((*action_bn));
+ CMB_ACTION_BN((*action_find_bn));
+};
+static struct cmb_xfdef_bn cmb_xforms_bn[] = {
+ /* opname action_bn */
+ {"multiply", cmb_mul_bn, cmb_mul_find_bn},
+ {"divide", cmb_div_bn, cmb_div_find_bn},
+ {"add", cmb_add_bn, cmb_add_find_bn},
+ {"subtract", cmb_sub_bn, cmb_sub_find_bn},
+ {NULL, NULL, NULL},
+};
+#endif
+
+int
+main(int argc, char *argv[])
+{
+ uint8_t free_find = FALSE;
+ uint8_t opt_empty = FALSE;
+ uint8_t opt_file = FALSE;
+ uint8_t opt_find = FALSE;
+#ifdef HAVE_LIBCRYPTO
+ uint8_t opt_nossl = FALSE;
+#endif
+ uint8_t opt_nulparse = FALSE;
+ uint8_t opt_nulprint = FALSE;
+ uint8_t opt_precision = FALSE;
+ uint8_t opt_randi = FALSE;
+ uint8_t opt_range = FALSE;
+ uint8_t opt_total = FALSE;
+ uint8_t opt_version = FALSE;
+ const char *cp;
+ char *cmdver = version;
+ char *endptr = NULL;
+ char **items = NULL;
+ char **items_tmp = NULL;
+ const char *libver = cmb_version(CMB_VERSION);
+ char *opt_transform = NULL;
+ int ch;
+ int len;
+ int retval = EXIT_SUCCESS;
+ uint32_t i;
+ uint32_t n;
+ uint32_t n_items = 0;
+ uint32_t rstart = 0;
+ uint32_t rstop = 0;
+ size_t config_size = sizeof(struct cmb_config);
+ size_t cp_size = sizeof(char *);
+ size_t optlen;
+ struct cmb_config *config = NULL;
+ struct cmb_xitem *xitem = NULL;
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ BIGNUM *count_bn;
+#endif
+ uint64_t count;
+ uint64_t fitems = 0;
+ uint64_t nstart = 0; /* negative start */
+ uint64_t ritems = 0;
+ uint64_t ull;
+ unsigned long ul;
+ struct timeval tv;
+
+ pgm = argv[0]; /* store a copy of invocation name */
+
+ /* Allocate config structure */
+ if ((config = malloc(config_size)) == NULL)
+ errx(EXIT_FAILURE, "Out of memory?!");
+ bzero(config, sizeof(struct cmb_config));
+
+ /*
+ * Process command-line options
+ */
+#define OPTSTRING "0c:Dd:eF:fi:k:Nn:oP:p:qrSs:tvX:z"
+ while ((ch = getopt(argc, argv, OPTSTRING)) != -1) {
+ switch(ch) {
+ case '0': /* NUL terminate */
+ config->options ^= CMB_OPT_NULPARSE;
+ opt_nulparse = TRUE;
+ break;
+ case 'c': /* count */
+ if ((optlen = strlen(optarg)) == 0 ||
+ unumlen(optarg) != optlen) {
+ errx(EXIT_FAILURE, "-c: invalid count `%s'",
+ optarg);
+ /* NOTREACHED */
+ }
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (!opt_nossl &&
+ BN_dec2bn(&(config->count_bn), optarg) == 0)
+ openssl_err("OpenSSL error");
+ if (opt_nossl) {
+#endif
+ errno = 0;
+ config->count = strtoull(optarg,
+ (char **)NULL, 10);
+ if (errno != 0)
+ err(EXIT_FAILURE, "-c: invalid count `%s'",
+ optarg);
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ }
+#endif
+ break;
+ case 'D': /* debug */
+ config->options ^= CMB_OPT_DEBUG;
+ break;
+ case 'd': /* delimiter */
+ config->delimiter = optarg;
+ break;
+ case 'e': /* empty */
+ opt_empty = TRUE;
+ config->options ^= CMB_OPT_EMPTY;
+ break;
+ case 'F': /* find */
+ opt_find = TRUE;
+ if (cmb_transform_find != NULL)
+ free(cmb_transform_find);
+ if ((cmb_transform_find =
+ malloc(sizeof(struct cmb_xitem))) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ cmb_transform_find->cp = optarg;
+ endptr = NULL;
+ errno = 0;
+ cmb_transform_find->as.ld = strtold(optarg, &endptr);
+ if (endptr == NULL || *endptr != '\0') {
+ if (errno == 0)
+ errno = EINVAL;
+ errx(EXIT_FAILURE, "-F: %s `%s'",
+ strerror(errno), optarg);
+ /* NOTREACHED */
+ }
+ break;
+ case 'f': /* file */
+ opt_file = TRUE;
+ opt_range = FALSE;
+ break;
+ case 'i': /* start */
+ if ((optlen = strlen(optarg)) > 0 &&
+ strncmp("random", optarg, optlen) == 0) {
+ opt_randi = TRUE;
+ } else if (optlen == 0 || numlen(optarg) != optlen) {
+ errx(EXIT_FAILURE, "-i: invalid number `%s'",
+ optarg);
+ /* NOTREACHED */
+ }
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (!opt_randi && !opt_nossl &&
+ BN_dec2bn(&(config->start_bn), optarg) == 0)
+ openssl_err("OpenSSL error");
+ if (!opt_randi && opt_nossl) {
+#else
+ if (!opt_randi) {
+#endif
+ errno = 0;
+ if (*optarg == '-') {
+ nstart = strtoull(&optarg[1],
+ (char **)NULL, 10);
+ } else {
+ config->start = strtoull(optarg,
+ (char **)NULL, 10);
+ }
+ if (errno != 0)
+ err(EXIT_FAILURE,
+ "-i: invalid start `%s'", optarg);
+ /* NOTREACHED */
+ }
+ break;
+ case 'k': /* size */
+ if (!parse_range(optarg, &(config->size_min),
+ &(config->size_max))) {
+ err(EXIT_FAILURE, "-k: invalid range `%s'",
+ optarg);
+ /* NOTREACHED */
+ }
+ break;
+ case 'N': /* numbers */
+ config->options ^= CMB_OPT_NUMBERS;
+ break;
+ case 'n': /* n-args */
+ if (!parse_unum(optarg, &n_items)) {
+ errx(EXIT_FAILURE, "-n: %s `%s'",
+ strerror(errno), optarg);
+ /* NOTREACHED */
+ }
+ break;
+ case 'o': /* disable openssl */
+#ifdef HAVE_LIBCRYPTO
+ opt_nossl = TRUE;
+#endif
+ break;
+ case 'P': /* precision */
+ if (!parse_unum(optarg,
+ (uint32_t *)&cmb_transform_precision)) {
+ errx(EXIT_FAILURE, "-P: %s `%s'",
+ strerror(errno), optarg);
+ /* NOTREACHED */
+ }
+ opt_precision = TRUE;
+ break;
+ case 'p': /* prefix */
+ config->prefix = optarg;
+ break;
+ case 'q': /* quiet */
+ opt_quiet = 1;
+ break;
+ case 'r': /* range */
+ opt_range = TRUE;
+ opt_file = FALSE;
+ break;
+ case 'S': /* silent */
+ opt_silent = TRUE;
+ break;
+ case 's': /* suffix */
+ config->suffix = optarg;
+ break;
+ case 't': /* total */
+ opt_total = TRUE;
+ break;
+ case 'v': /* version */
+ opt_version = TRUE;
+ break;
+ case 'X': /* transform */
+ opt_transform = optarg;
+ break;
+ case 'z': /* zero */
+ opt_nulprint = TRUE;
+ config->options ^= CMB_OPT_NULPRINT;
+ break;
+ default: /* unhandled argument (based on switch) */
+ cmb_usage();
+ /* NOTREACHED */
+ }
+ }
+ argc -= optind;
+ argv += optind;
+
+ /*
+ * Process `-v' command-line option
+ */
+ if (opt_version) {
+ cmdver += 10; /* Seek past "$Version: " */
+ cmdver[strlen(cmdver)-2] = '\0'; /* Place NUL before "$" */
+#ifdef HAVE_OPENSSL_CRYPTO_H
+ printf("%s: %s (%s; %s)", pgm, cmdver, libver,
+ SSLeay_version(SSLEAY_VERSION));
+#else
+ printf("%s: %s (%s)", pgm, cmdver, libver);
+#endif
+ if (cmb_build_info.debug)
+ printf(" [debug]");
+ printf("\n");
+ exit(EXIT_SUCCESS);
+ }
+
+ /*
+ * At least one non-option argument is required unless `-e' is given
+ */
+ if (argc == 0 && !opt_empty) {
+ warnx("argument required unless `-e'");
+ cmb_usage();
+ /* NOTREACHED */
+ }
+
+ /*
+ * `-X op' required if given `-F num'
+ */
+ if (opt_find && opt_transform == NULL) {
+ errx(EXIT_FAILURE, "`-X op' required when using `-F num'");
+ /* NOTREACHED */
+ }
+
+ /*
+ * `-X op' required if given `-P num'
+ */
+ if (opt_precision && opt_transform == NULL) {
+ errx(EXIT_FAILURE, "`-X op' required when using `-P num'");
+ /* NOTREACHED */
+ }
+
+ /*
+ * `-f' required if given `-0'
+ */
+ if (opt_nulparse && !opt_file) {
+ errx(EXIT_FAILURE, "`-f' required when using `-0'");
+ /* NOTREACHED */
+ }
+
+ /*
+ * Calculate number of items
+ */
+ if (n_items == 0 || n_items > (uint32_t)argc)
+ n_items = (uint32_t)argc;
+ if (opt_range) {
+ for (n = 0; n < n_items; n++) {
+ if (!parse_urange(argv[n], &rstart, &rstop)) {
+ errx(EXIT_FAILURE, "-r: %s `%s'",
+ strerror(errno), argv[n]);
+ /* NOTREACHED */
+ }
+ if (unumlen(argv[n]) == strlen(argv[n])) {
+ rstop = rstart;
+ rstart = 1;
+ }
+ if (rstart < rstop)
+ ull = rstop - rstart + 1;
+ else
+ ull = rstart - rstop + 1;
+ if (ritems + ull > UINT_MAX) {
+ errx(EXIT_FAILURE, "-r: Too many items");
+ /* NOTREACHED */
+ }
+ ritems += ull;
+ }
+ }
+
+ /*
+ * Print total for num items and exit if given `-t -r'
+ */
+ if (opt_total && opt_range) {
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (!opt_nossl) {
+ char *count_str;
+
+ count_bn = cmb_count_bn(config, (uint32_t)ritems);
+ if (opt_silent)
+ exit(EXIT_SUCCESS);
+ if (count_bn != NULL) {
+ count_str = BN_bn2dec(count_bn);
+ printf("%s%s", count_str,
+ opt_nulprint ? "" : "\n");
+ OPENSSL_free(count_str);
+ BN_free(count_bn);
+ } else
+ printf("0%s", opt_nulprint ? "" : "\n");
+ } else {
+#endif
+ count = cmb_count(config, (uint32_t)ritems);
+ if (opt_silent)
+ exit(EXIT_SUCCESS);
+ if (errno) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ printf("%"PRIu64"%s", count, opt_nulprint ? "" : "\n");
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ }
+#endif
+ exit(EXIT_SUCCESS);
+ }
+
+ /*
+ * Read arguments ...
+ */
+ if (opt_file) {
+ /* ... as a series of files if given `-f' */
+ for (n = 0; n < n_items; n++) {
+ items_tmp = cmb_parse_file(config, argv[n], &i, 0);
+ if (items_tmp == NULL && errno != 0) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ if (fitems + i > UINT_MAX) {
+ errx(EXIT_FAILURE, "-f: Too many items");
+ /* NOTREACHED */
+ }
+ fitems += (uint64_t)i;
+ items = reallocf(items, (size_t)(fitems * cp_size));
+ if (items == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ (void)memcpy(&items[fitems-i], items_tmp, i * cp_size);
+ }
+ n_items = (uint32_t)fitems;
+ } else if (opt_range) {
+ /* ... as a series of ranges if given `-r' */
+ if ((items = calloc(ritems, sizeof(char *))) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ i = 0;
+ for (n = 0; n < n_items; n++) {
+ parse_urange(argv[n], &rstart, &rstop);
+ if (unumlen(argv[n]) == strlen(argv[n])) {
+ rstop = rstart;
+ rstart = 1;
+ }
+ if (opt_transform != NULL)
+ i = range_float(rstart, rstop, i, items);
+ else
+ i = range_char(rstart, rstop, i, items);
+ }
+ n_items = (uint32_t)ritems;
+ } else {
+ /* ... as a series of strings or numbers if given `-X op' */
+ items = argv;
+ }
+
+ /*
+ * Time-based benchmarking (-S for silent) and transforms (-X op).
+ *
+ * NB: For benchmarking, the call-stack is still incremented into the
+ * action, while using a nop function allows us to benchmark
+ * various action overhead.
+ */
+ if (opt_silent && opt_transform == NULL) {
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (opt_nossl)
+ config->action = cmb_nop;
+ else
+ config->action_bn = cmb_nop_bn;
+#else
+ config->action = cmb_nop;
+#endif
+ config->options &= ~CMB_OPT_NUMBERS;
+ } else if (opt_transform != NULL) {
+ if ((optlen = strlen(opt_transform)) == 0) {
+ errx(EXIT_FAILURE, "-X: %s `'", strerror(EINVAL));
+ /* NOTREACHED */
+ }
+ ch = -1;
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (opt_nossl) {
+ while ((cp = cmb_xforms[++ch].opname) != NULL) {
+ if (strncmp(cp, opt_transform, optlen) != 0)
+ continue;
+ if (opt_find)
+ config->action =
+ cmb_xforms[ch].action_find;
+ else
+ config->action = cmb_xforms[ch].action;
+ break;
+ }
+ } else {
+ while ((cp = cmb_xforms_bn[++ch].opname) != NULL) {
+ if (strncmp(cp, opt_transform, optlen) != 0)
+ continue;
+ if (opt_find)
+ config->action_bn =
+ cmb_xforms_bn[ch].action_find_bn;
+ else
+ config->action_bn =
+ cmb_xforms_bn[ch].action_bn;
+ break;
+ }
+ }
+ if (config->action == NULL && config->action_bn == NULL) {
+ errx(EXIT_FAILURE, "-X: %s `%s'", strerror(EINVAL),
+ opt_transform);
+ /* NOTREACHED */
+ }
+#else
+ while ((cp = cmb_xforms[++ch].opname) != NULL) {
+ if (strncmp(cp, opt_transform, optlen) != 0)
+ continue;
+ if (opt_find)
+ config->action = cmb_xforms[ch].action_find;
+ else
+ config->action = cmb_xforms[ch].action;
+ break;
+ }
+ if (config->action == NULL) {
+ errx(EXIT_FAILURE, "-X: %s `%s'", strerror(EINVAL),
+ opt_transform);
+ /* NOTREACHED */
+ }
+#endif
+
+ /*
+ * Convert items into array of struct pointers
+ * NB: Transformation function does not perform conversions
+ */
+ if (!opt_range) {
+ ul = sizeof(struct cmb_xitem *);
+ if ((items_tmp = calloc(n_items, ul)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ for (n = 0; n < n_items; n++) {
+ if ((xitem = malloc(sizeof(struct cmb_xitem)))
+ == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ xitem->cp = items[n];
+ endptr = NULL;
+ errno = 0;
+ xitem->as.ld = strtold(items[n], &endptr);
+ if (endptr == NULL || *endptr != '\0') {
+ if (errno == 0)
+ errno = EINVAL;
+ errx(EXIT_FAILURE, "-X: %s `%s'",
+ strerror(errno), items[n]);
+ /* NOTREACHED */
+ }
+ items_tmp[n] = (char *)xitem;
+ if (opt_precision)
+ continue;
+ if ((cp = strchr(items[n], '.')) != NULL) {
+ len = (int)strlen(items[n]);
+ len -= cp - items[n] + 1;
+ if (len > cmb_transform_precision)
+ cmb_transform_precision = len;
+ }
+ }
+ items = items_tmp;
+ }
+ }
+
+ /*
+ * Adjust precision based on `-F num'
+ */
+ if (opt_find) {
+ if ((cp = strchr(cmb_transform_find->cp, '.')) != NULL) {
+ len = (int)strlen(cmb_transform_find->cp);
+ len -= cp - cmb_transform_find->cp + 1;
+ if (len > cmb_transform_precision) {
+ cmb_transform_precision = len;
+ } else {
+ len = snprintf(NULL, 0, "%.*Lf",
+ cmb_transform_precision,
+ cmb_transform_find->as.ld) + 1;
+ cmb_transform_find->cp =
+ malloc((unsigned long)len);
+ if (cmb_transform_find->cp == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ free_find = TRUE;
+ (void)snprintf(cmb_transform_find->cp,
+ (size_t)len, "%.*Lf",
+ cmb_transform_precision,
+ cmb_transform_find->as.ld);
+ }
+ } else if (cmb_transform_precision > 0) {
+ len = snprintf(NULL, 0, "%.*Lf",
+ cmb_transform_precision,
+ cmb_transform_find->as.ld) + 1;
+ cmb_transform_find->cp = malloc((unsigned long)len);
+ if (cmb_transform_find->cp == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ free_find = TRUE;
+ (void)snprintf(cmb_transform_find->cp, (size_t)len,
+ "%.*Lf", cmb_transform_precision,
+ cmb_transform_find->as.ld);
+ }
+ }
+
+ /*
+ * Calculate combinations
+ */
+ if (opt_total) {
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ if (!opt_nossl) {
+ char *count_str;
+
+ count_bn = cmb_count_bn(config, n_items);
+ if (opt_silent)
+ exit(EXIT_SUCCESS);
+ if (count_bn != NULL) {
+ count_str = BN_bn2dec(count_bn);
+ printf("%s%s", count_str,
+ opt_nulprint ? "" : "\n");
+ OPENSSL_free(count_str);
+ BN_free(count_bn);
+ } else
+ printf("0%s", opt_nulprint ? "" : "\n");
+ } else {
+#endif
+ count = cmb_count(config, n_items);
+ if (opt_silent)
+ exit(EXIT_SUCCESS);
+ if (errno) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ printf("%"PRIu64"%s", count, opt_nulprint ? "" : "\n");
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+ }
+ } else if (!opt_nossl) {
+ if (opt_randi) {
+ if ((count_bn =
+ cmb_count_bn(config, n_items)) != NULL) {
+ if (config->start_bn == NULL)
+ config->start_bn = BN_new();
+ if (BN_rand_range(config->start_bn, count_bn))
+ BN_add_word(config->start_bn, 1);
+ }
+ } else if (config->start_bn != NULL &&
+ BN_is_negative(config->start_bn)) {
+ if ((count_bn =
+ cmb_count_bn(config, n_items)) != NULL) {
+ BN_add(config->start_bn,
+ count_bn, config->start_bn);
+ BN_add_word(config->start_bn, 1);
+ if (BN_is_negative(config->start_bn))
+ BN_zero(config->start_bn);
+ BN_free(count_bn);
+ }
+ }
+ retval = cmb_bn(config, n_items, items);
+#endif
+ } else {
+ if (opt_randi) {
+ count = cmb_count(config, n_items);
+ if (errno) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ if (gettimeofday(&tv,NULL) == 0) {
+ srand48((long)tv.tv_usec);
+ config->start = cmb_rand_range(count) + 1;
+ }
+ } else if (nstart != 0) {
+ count = cmb_count(config, n_items);
+ if (errno) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ if (count > nstart)
+ config->start = count - nstart + 1;
+ else
+ config->start = 0;
+ }
+ retval = cmb(config, n_items, items);
+ if (errno) {
+ err(EXIT_FAILURE, NULL);
+ /* NOTREACHED */
+ }
+ }
+
+ /*
+ * Clean up
+ */
+ if (opt_file || opt_range) {
+ for (n = 0; n < n_items; n++)
+ free(items[n]);
+ free(items);
+ } else if (opt_transform) {
+ for (n = 0; n < n_items; n++) {
+ memcpy(&xitem, &items[n], sizeof(char *));
+ if (opt_range)
+ free(xitem->cp);
+ free(xitem);
+ }
+ free(items);
+ }
+ if (opt_find) {
+ if (free_find)
+ free(cmb_transform_find->cp);
+ free(cmb_transform_find);
+ if (cmb_transform_find_buf != NULL)
+ free(cmb_transform_find_buf);
+ }
+ free(config);
+
+ return (retval);
+}
+
+/*
+ * Print short usage statement to stderr and exit with error status.
+ */
+static void
+cmb_usage(void)
+{
+ fprintf(stderr, "usage: %s [options] [item ...]\n", pgm);
+#define OPTFMT "\t%-10s %s\n"
+#define OPTFMT_1U "\t%-10s %s%u%s\n"
+ fprintf(stderr, "OPTIONS:\n");
+ fprintf(stderr, OPTFMT, "-0",
+ "Read items terminated by NUL when given `-f'.");
+ fprintf(stderr, OPTFMT, "-c num",
+ "Produce num combinations (default `0' for all).");
+ fprintf(stderr, OPTFMT, "-D",
+ "Enable debugging information on stderr."
+ );
+ fprintf(stderr, OPTFMT, "-d text", "Item delimiter (default is ` ').");
+ fprintf(stderr, OPTFMT, "-e", "Show empty set with no items.");
+ fprintf(stderr, OPTFMT, "-F num",
+ "Find `-X op' results matching num.");
+ fprintf(stderr, OPTFMT, "-f",
+ "Treat arguments as files to read items from; `-' for stdin.");
+ fprintf(stderr, OPTFMT, "-i num",
+ "Skip the first num-1 combinations.");
+ fprintf(stderr, OPTFMT, "-k size",
+ "Number or range (`min..max' or `min-max') of items.");
+ fprintf(stderr, OPTFMT, "-N", "Show combination sequence numbers.");
+ fprintf(stderr, OPTFMT, "-n num",
+ "Limit arguments taken from the command-line.");
+ fprintf(stderr, OPTFMT, "-o",
+ "Disable OpenSSL (limits calculations to 64-bits).");
+ fprintf(stderr, OPTFMT, "-P num",
+ "Set floating point precision when given `-X op'.");
+ fprintf(stderr, OPTFMT, "-p text", "Prefix text for each line.");
+ fprintf(stderr, OPTFMT, "-q",
+ "Quiet. Do not print items from set when given `-X op'.");
+ fprintf(stderr, OPTFMT_1U, "-r",
+ "Treat arguments as ranges of up-to ", UINT_MAX, " items.");
+ fprintf(stderr, OPTFMT, "-S", "Silent (for performance benchmarks).");
+ fprintf(stderr, OPTFMT, "-s text", "Suffix text for each line.");
+ fprintf(stderr, OPTFMT, "-t",
+ "Print number of combinations and exit.");
+ fprintf(stderr, OPTFMT, "-v",
+ "Print version info to stdout and exit.");
+ fprintf(stderr, OPTFMT, "-X op",
+ "Perform math on items where `op' is add, sub, div, or mul.");
+ fprintf(stderr, OPTFMT, "-z",
+ "Print combinations NUL terminated (use with `xargs -0').");
+ exit(EXIT_FAILURE);
+}
+
+/*
+ * Return pseudo-random 64-bit unsigned integer in range 0 <= return <= range.
+ */
+static uint64_t
+cmb_rand_range(uint64_t range)
+{
+ static const uint64_t M = (uint64_t)~0;
+ uint64_t exclusion = p2(range) ? 0 : M % range + 1;
+ uint64_t res = 0;
+
+ while ((res = urand64()) < exclusion) {}
+ return (res % range);
+}
+
+static size_t
+numlen(const char *s)
+{
+ if (s == NULL || *s == '\0')
+ return (0);
+ else if (*s == '-')
+ return (strspn(&s[1], digit) + 1);
+ else
+ return (strspn(s, digit));
+}
+
+static size_t
+rangelen(const char *s, size_t nlen, size_t slen)
+{
+ size_t rlen;
+ const char *cp = s;
+
+ if (nlen == 0)
+ return (0);
+ else if (nlen == slen)
+ return (nlen);
+
+ cp += nlen;
+ if (*cp == '-') {
+ cp += 1;
+ if (*cp == '\0')
+ return (0);
+ return (nlen + strspn(cp, digit) + 1);
+ } else if (strncmp(cp, "..", 2) == 0) {
+ cp += 2;
+ if ((rlen = numlen(cp)) == 0)
+ return (0);
+ return (nlen + rlen + 2);
+ } else
+ return (0);
+}
+
+static uint8_t
+parse_range(const char *s, uint32_t *min, uint32_t *max)
+{
+ const char *cp;
+ size_t nlen;
+ size_t optlen;
+ uint64_t ull;
+
+ errno = 0;
+
+ if (s == NULL || ((nlen = numlen(s)) != (optlen = strlen(s)) &&
+ rangelen(s, nlen, optlen) != optlen)) {
+ errno = EINVAL;
+ return (FALSE);
+ }
+
+ if (*s == '-') {
+ ull = strtoull(&s[1], (char **)NULL, 10);
+ *min = UINT_MAX - (uint32_t)ull;
+ } else {
+ ull = strtoull(s, (char **)NULL, 10);
+ *min = (uint32_t)ull;
+ }
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+
+ cp = &s[nlen];
+ if (*cp == '\0')
+ *max = *s == '-' ? (uint32_t)ull : *min;
+ else if ((strncmp(cp, "..", 2)) == 0) {
+ cp += 2;
+ if (*cp == '-') {
+ ull = strtoull(&cp[1], (char **)NULL, 10);
+ *max = UINT_MAX - (uint32_t)ull;
+ } else {
+ ull = strtoull(cp, (char **)NULL, 10);
+ *max = (uint32_t)ull;
+ }
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+ } else if (*cp == '-') {
+ ull = strtoull(&cp[1], (char **)NULL, 10);
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+ *max = (uint32_t)ull;
+ } else {
+ errno = EINVAL;
+ return (FALSE);
+ }
+
+ return (TRUE);
+}
+
+static size_t
+unumlen(const char *s)
+{
+ if (s == NULL || *s == '\0')
+ return (0);
+ else
+ return (strspn(s, digit));
+}
+
+static size_t
+urangelen(const char *s, size_t nlen, size_t slen)
+{
+ size_t rlen;
+ const char *cp = s;
+
+ if (nlen == 0)
+ return (0);
+ else if (nlen == slen)
+ return (nlen);
+
+ cp += nlen;
+ if (*cp == '-') {
+ cp += 1;
+ if (*cp == '\0')
+ return (0);
+ return (nlen + strspn(cp, digit) + 1);
+ } else if (strncmp(cp, "..", 2) == 0) {
+ cp += 2;
+ if ((rlen = unumlen(cp)) == 0)
+ return (0);
+ return (nlen + rlen + 2);
+ } else
+ return (0);
+}
+
+static uint8_t
+parse_unum(const char *s, uint32_t *n)
+{
+ uint64_t ull;
+
+ errno = 0;
+
+ if (s == NULL || unumlen(s) != strlen(s)) {
+ errno = EINVAL;
+ return (FALSE);
+ }
+
+ ull = strtoull(optarg, (char **)NULL, 10);
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+
+ *n = (uint32_t)ull;
+
+ return (TRUE);
+}
+
+static uint8_t
+parse_urange(const char *s, uint32_t *min, uint32_t *max)
+{
+ const char *cp;
+ size_t nlen;
+ size_t optlen;
+ uint64_t ull;
+
+ errno = 0;
+
+ if (s == NULL || ((nlen = unumlen(s)) != (optlen = strlen(s)) &&
+ urangelen(s, nlen, optlen) != optlen) || *s == '-') {
+ errno = EINVAL;
+ return (FALSE);
+ }
+
+ ull = strtoull(s, (char **)NULL, 10);
+ *min = *max = (uint32_t)ull;
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+
+ cp = &s[nlen];
+ if (*cp == '\0')
+ *max = *min;
+ else if ((strncmp(cp, "..", 2)) == 0) {
+ cp += 2;
+ ull = strtoull(cp, (char **)NULL, 10);
+ *max = (uint32_t)ull;
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+ } else if (*cp == '-') {
+ ull = strtoull(&cp[1], (char **)NULL, 10);
+ if (errno != 0)
+ return (FALSE);
+ else if (ull > UINT_MAX) {
+ errno = ERANGE;
+ return (FALSE);
+ }
+ *max = (uint32_t)ull;
+ } else {
+ errno = EINVAL;
+ return (FALSE);
+ }
+
+ return (TRUE);
+}
+
+static uint32_t
+range_char(uint32_t start, uint32_t stop, uint32_t idx, char *dst[])
+{
+ int len;
+ uint32_t num;
+
+ if (start <= stop) {
+ for (num = start; num <= stop; num++) {
+ len = snprintf(NULL, 0, "%u", num) + 1;
+ if ((dst[idx] = malloc((unsigned long)len)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ (void)snprintf(dst[idx], (size_t)len, "%u", num);
+ idx++;
+ }
+ } else {
+ for (num = start; num >= stop; num--) {
+ len = snprintf(NULL, 0, "%u", num) + 1;
+ if ((dst[idx] = (char *)malloc((unsigned long)len)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ (void)snprintf(dst[idx], (size_t)len, "%u", num);
+ idx++;
+ }
+ }
+
+ return (idx);
+}
+
+static uint32_t
+range_float(uint32_t start, uint32_t stop, uint32_t idx, char *dst[])
+{
+ int len;
+ uint32_t num;
+ size_t size;
+ struct cmb_xitem *xitem;
+
+ size = sizeof(struct cmb_xitem);
+ if (start <= stop) {
+ for (num = start; num <= stop; num++) {
+ if ((xitem = malloc(size)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ len = snprintf(NULL, 0, "%u", num) + 1;
+ if ((xitem->cp = malloc((unsigned long)len)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ (void)snprintf(xitem->cp, (size_t)len, "%u", num);
+ xitem->as.ld = (long double)num;
+ dst[idx] = (char *)xitem;
+ idx++;
+ }
+ } else {
+ for (num = start; num >= stop; num--) {
+ if ((xitem = malloc(size)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ len = snprintf(NULL, 0, "%u", num) + 1;
+ if ((xitem->cp = malloc((unsigned long)len)) == NULL) {
+ errx(EXIT_FAILURE, "Out of memory?!");
+ /* NOTREACHED */
+ }
+ (void)snprintf(xitem->cp, (size_t)len, "%u", num);
+ xitem->as.ld = (long double)num;
+ dst[idx] = (char *)xitem;
+ idx++;
+ }
+ }
+
+ return (idx);
+}
+
+/*
+ * For performance benchmarking
+ */
+static
+CMB_ACTION(cmb_nop)
+{
+ (void)config;
+ (void)seq;
+ (void)n_items;
+ (void)items;
+ return (0);
+}
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static
+CMB_ACTION_BN(cmb_nop_bn)
+{
+ (void)config;
+ (void)seq;
+ (void)n_items;
+ (void)items;
+ return (0);
+}
+#endif
+
+/*
+ * Transformation functions
+ */
+static CMB_TRANSFORM_OP(*, cmb_mul);
+static CMB_TRANSFORM_OP(/, cmb_div);
+static CMB_TRANSFORM_OP(+, cmb_add);
+static CMB_TRANSFORM_OP(-, cmb_sub);
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static CMB_TRANSFORM_OP_BN(*, cmb_mul_bn);
+static CMB_TRANSFORM_OP_BN(/, cmb_div_bn);
+static CMB_TRANSFORM_OP_BN(+, cmb_add_bn);
+static CMB_TRANSFORM_OP_BN(-, cmb_sub_bn);
+#endif
+
+/*
+ * Find transformation functions
+ */
+static CMB_TRANSFORM_OP_FIND(*, cmb_mul_find);
+static CMB_TRANSFORM_OP_FIND(/, cmb_div_find);
+static CMB_TRANSFORM_OP_FIND(+, cmb_add_find);
+static CMB_TRANSFORM_OP_FIND(-, cmb_sub_find);
+#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H)
+static CMB_TRANSFORM_OP_FIND_BN(*, cmb_mul_find_bn);
+static CMB_TRANSFORM_OP_FIND_BN(/, cmb_div_find_bn);
+static CMB_TRANSFORM_OP_FIND_BN(+, cmb_add_find_bn);
+static CMB_TRANSFORM_OP_FIND_BN(-, cmb_sub_find_bn);
+#endif

File Metadata

Mime Type
text/plain
Expires
Sun, Aug 16, 3:04 PM (1 h, 30 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
36826742
Default Alt Text
D16132.id183333.diff (109 KB)

Event Timeline