Page MenuHomeFreeBSD
Files F141995599

D16132.id50015.diff
No OneTemporary
Actions

D16132.id50015.diff
View Options

Index: lib/Makefile
===================================================================
--- lib/Makefile
+++ lib/Makefile
@@ -37,6 +37,7 @@
libcam \
libcapsicum \
libcasper \
+ libcmb \
libcompat \
libcrypt \
libdevctl \
Index: lib/libcmb/Makefile
===================================================================
--- /dev/null
+++ lib/libcmb/Makefile
@@ -0,0 +1,20 @@
+# $FreeBSD$
+
+.include <src.opts.mk>
+
+PACKAGE=lib${LIB}
+LIB= cmb
+SHLIB_MAJOR= 0
+INCS= cmb.h
+MAN= cmb.3
+
+SRCS= cmb.c
+
+CFLAGS+= -I${.CURDIR}
+
+.if ${MK_OPENSSL} != "no"
+CFLAGS+= -DHAVE_LIBCRYPTO
+LIBADD+= crypto
+.endif
+
+.include <bsd.lib.mk>
Index: lib/libcmb/cmb.h
===================================================================
--- /dev/null
+++ lib/libcmb/cmb.h
@@ -0,0 +1,98 @@
+/*-
+ * Copyright (c) 2002-2018 Devin Teske <dteske@FreeBSD.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FrauBSD: pkgcenter/depend/libcmb/cmb.h 2018-11-03 11:49:13 -0700 freebsdfrau $
+ * $FreeBSD$
+ */
+
+#ifndef _CMB_H_
+#define _CMB_H_
+
+#include <sys/param.h>
+#include <sys/types.h>
+
+#include <stddef.h>
+#include <stdint.h>
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#elif defined(__FreeBSD_version)
+#ifdef HAVE_LIBCRYPTO
+#define HAVE_OPENSSL_BN_H 1
+#else
+#undef HAVE_OPENSSL_BN_H
+#endif
+#endif
+
+#ifdef HAVE_OPENSSL_BN_H
+#include <openssl/bn.h>
+#endif
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+/*
+ * Anatomy of config option to pass as cmb*() config argument
+ */
+struct cmb_config {
+ uint8_t nul_terminate; /* Terminate combinations with ASCII NUL */
+ uint8_t show_empty; /* Show empty set with no items */
+ 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 */
+#ifdef HAVE_OPENSSL_BN_H
+ BIGNUM *count_bn; /* bn(3) number of combinations */
+ BIGNUM *start_bn; /* bn(3) starting combination */
+#endif
+
+ /*
+ * Function pointer; action to perform 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.
+ */
+ int (*action)(struct cmb_config *config, uint32_t nitems,
+ char *items[]);
+};
+
+__BEGIN_DECLS
+int cmb(struct cmb_config *_config, uint32_t _nitems, char *_items[]);
+int cmb_print(struct cmb_config *config, uint32_t _nitems, char *_items[]);
+uint64_t cmb_count(struct cmb_config *_config, uint32_t _nitems);
+#ifdef HAVE_OPENSSL_BN_H
+int cmb_bn(struct cmb_config *_config, uint32_t _nitems, char *_items[]);
+BIGNUM * cmb_count_bn(struct cmb_config *_config, uint32_t _nitems);
+#endif
+__END_DECLS
+
+#endif /* !_CMB_H_ */
Index: lib/libcmb/cmb.3
===================================================================
--- /dev/null
+++ lib/libcmb/cmb.3
@@ -0,0 +1,158 @@
+.\" Copyright (c) 2018 Devin Teske <dteske@FreeBSD.org>
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\" $FrauBSD: pkgcenter/depend/libcmb/cmb.3 2018-11-03 11:49:13 -0700 freebsdfrau $
+.\" $FreeBSD$
+.\"
+.Dd November 3, 2018
+.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 nitems" "char *items[]"
+.Ft int
+.Fn cmb_print "struct cmb_config *config" "uint32_t nitems" "char *items[]"
+.Ft uint64_t
+.Fn cmb_count "struct cmb_config *config" "uint32_t nitems"
+.Pp
+/* OpenSSL
+.Xr bn 3
+support */
+.Pp
+.Ft int
+.Fn cmb_bn "struct cmb_config *config" "uint32_t nitems" "char *items[]"
+.Ft "BIGNUM *"
+.Fn cmb_count_bn "struct cmb_config *config" "uint32_t nitems"
+.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 nul_terminate; /* Terminate combinations with NUL */
+ uint8_t show_empty; /* Show empty set with no items */
+ 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 */
+
+ /* OpenSSL bn(3) support */
+ BIGNUM *count_bn; /* Number of combinations */
+ BIGNUM *start_bn; /* Starting combination */
+
+ /*
+ * Function pointer; action to perform 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.
+ */
+ int (*action)(struct cmb_config *config, uint32_t nitems,
+ char *items[]);
+};
+.Ed
+.Pp
+If
+.Ar nul_terminate
+is non-zero,
+.Fn cmb_print
+will print combination items separated by ASCII NUL character
+.Pq character code 0 .
+Otherwise,
+if
+.Ar nul_terminate
+is zero
+.Pq default ,
+.Ar delimiter
+is used and if unset,
+combinations are separated by a single space.
+.Pp
+If
+.Ar show_empty
+is non-zero,
+the empty set
+.Pq consisting of a single combination with no items
+is accounted-for.
+.Pp
+For each combination,
+if
+.Ar prefix
+is non-NULL it is printed before the first item and
+if
+.Ar suffix
+is non-NULL it 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 minimum
+.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
+to a non-zero value.
+.Pp
+If
+.Ar start
+is greater than one,
+the
+.Nm
+library will seek to that number combination before starting.
+.Pp
+.Ar count_bn
+and
+.Ar start_bn
+are only available on platforms with OpenSSL
+.Xr bn 3
+and are used by
+.Fn cmb_bn
+and
+.Fn cmb_count_bn
+to overcome limitations by 64-bit integers.
+.Sh HISTORY
+The
+.Nm
+library first appeared in
+.Fx 13.0 .
+.Sh AUTHORS
+.An Devin Teske Aq Mt dteske@FreeBSD.org
Index: lib/libcmb/cmb.c
===================================================================
--- /dev/null
+++ lib/libcmb/cmb.c
@@ -0,0 +1,873 @@
+/*-
+ * Copyright (c) 2002-2018 Devin Teske <dteske@FreeBSD.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#ifdef __FBSDID
+__FBSDID("$FrauBSD: pkgcenter/depend/libcmb/cmb.c 2018-11-03 12:15:22 -0700 freebsdfrau $");
+__FBSDID("$FreeBSD$");
+#endif
+
+#include <err.h>
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "cmb.h"
+
+/*
+ * 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 nitems)
+{
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ uint32_t curset;
+ uint32_t i = nitems;
+ uint32_t k;
+ uint32_t p;
+ uint32_t setdone = nitems;
+ uint32_t setinit = 1;
+ uint64_t count = 0;
+ long double z = 1;
+ uint64_t ncombos;
+
+ errno = 0;
+ if (nitems == 0)
+ return (0);
+
+ /* Process config options */
+ if (config != NULL) {
+ show_empty = config->show_empty;
+ 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 > nitems && setdone > nitems)
+ return (0);
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > nitems)
+ setinit = nitems;
+ if (setdone > nitems)
+ setdone = nitems;
+
+ /* 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 == nitems) ||
+ (setinit == nitems && setdone == 1)) {
+ if (show_empty) {
+ if (nitems >= 64) {
+ errno = ERANGE;
+ return (0);
+ }
+ return (1 << nitems);
+ } else
+ return (ULLONG_MAX >> (64 - nitems));
+ }
+
+ /* 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 += nextset)
+ {
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0)
+ z = (z * i--) / k++;
+
+ /* Add number of combinations in this set to total */
+ if ((ncombos = 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 nitems, char *items[])
+{
+ uint8_t docount = FALSE;
+ uint8_t doseek = FALSE;
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ int retval = 0;
+ uint32_t curset;
+ uint32_t i = nitems;
+ uint32_t k;
+ uint32_t n;
+ uint32_t p;
+ uint32_t seed;
+ uint32_t setdone = nitems;
+ 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;
+ long double z = 1;
+ char **curitems;
+ uint32_t *setnums;
+ uint32_t *setnums_backend;
+ int (*action)(struct cmb_config *config, uint32_t nitems,
+ char *items[]) = cmb_print;
+
+ if (nitems == 0)
+ return (0);
+ else if (cmb_count(config, nitems) == 0)
+ return (errno);
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->action != NULL)
+ action = config->action;
+ if (config->count != 0) {
+ docount = TRUE;
+ count = config->count;
+ }
+ show_empty = config->show_empty;
+ 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;
+ }
+ }
+
+ /* 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 > nitems)
+ setinit = nitems;
+ if (setdone > nitems)
+ setdone = nitems;
+
+ /* Set the direction of flow (incrementing vs. decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* 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?!");
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset > 0 && show_empty) {
+ if (!doseek) {
+ retval = action(config, 0, NULL);
+ if (retval != 0)
+ goto cmb_return;
+ if (docount && --count == 0)
+ goto cmb_return;
+ } else {
+ seek--;
+ if (seek == 1)
+ doseek = FALSE;
+ }
+ }
+
+ /*
+ * 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 += nextset)
+ {
+ /* Calculate number of combinations (incrementing) */
+ if (nextset > 0)
+ z = (z * i--) / k++;
+
+ /* Cast number of combinations in set to integer */
+ if ((ncombos = 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 */
+ for (n = 0; n < curset; n++)
+ curitems[n] = items[n];
+
+ /* Produce results with the first set of items */
+ if (!doseek) {
+ retval = action(config, 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 nitems-N and ending at nitems (again, N is the
+ * same integer as the current set we are operating on; nitems
+ * is the total number of items). For example, if we are
+ * operating on a set-of-2, and nitems 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++] = nitems - 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;
+
+ /* 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, 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, 0, NULL);
+ }
+
+cmb_return:
+ free(curitems);
+ free(setnums);
+ free(setnums_backend);
+
+ return (retval);
+}
+
+int
+cmb_print(struct cmb_config *config, uint32_t nitems, char *items[])
+{
+ uint8_t cmb_print_nul = FALSE;
+ uint32_t n;
+ const char *cmb_print_delimiter = " ";
+ const char *cmb_print_prefix = NULL;
+ const char *cmb_print_suffix = NULL;
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->delimiter != NULL)
+ cmb_print_delimiter = config->delimiter;
+ cmb_print_nul = config->nul_terminate;
+ cmb_print_prefix = config->prefix;
+ cmb_print_suffix = config->suffix;
+ }
+
+ if (cmb_print_prefix != NULL)
+ printf("%s", cmb_print_prefix);
+ for (n = 0; n < nitems; n++) {
+ printf("%s", items[n]);
+ if (n < nitems - 1)
+ printf("%s", cmb_print_delimiter);
+ }
+ if (cmb_print_suffix != NULL)
+ printf("%s", cmb_print_suffix);
+ if (cmb_print_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 nitems)
+{
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ uint32_t curset;
+ uint32_t i = nitems;
+ uint32_t k;
+ uint32_t p;
+ uint32_t setdone = nitems;
+ uint32_t setinit = 1;
+ BIGNUM *count = NULL;
+ BIGNUM *ncombos = NULL;
+
+ if (nitems == 0)
+ return (NULL);
+
+ /* Process config options */
+ if (config != NULL) {
+ show_empty = config->show_empty;
+ 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 > nitems && setdone > nitems)
+ return (NULL);
+
+ /* Enforce limits so we don't run over bounds */
+ if (setinit > nitems)
+ setinit = nitems;
+ if (setdone > nitems)
+ setdone = nitems;
+
+ /* Set the direction of flow (incrementing vs decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* Initialize count */
+ if ((count = BN_new()) == NULL)
+ return (NULL);
+ if (!BN_zero(count))
+ goto cmb_count_bn_return;
+
+ /* If entire set is requested, return 2^N[-1] */
+ if ((setinit == 1 && setdone == nitems) ||
+ (setinit == nitems && setdone == 1)) {
+ if (show_empty) {
+ BN_lshift(count, BN_value_one(), nitems);
+ goto cmb_count_bn_return;
+ } else {
+ if (BN_lshift(count, BN_value_one(), nitems))
+ 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 += 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' 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 nitems, char *items[])
+{
+ uint8_t docount = FALSE;
+ uint8_t doseek = FALSE;
+ uint8_t show_empty = FALSE;
+ int8_t nextset = 1;
+ int retval = 0;
+ uint32_t curset;
+ uint32_t i = nitems;
+ uint32_t k;
+ uint32_t n;
+ uint32_t p;
+ uint32_t seed;
+ uint32_t setdone = nitems;
+ uint32_t setinit = 1;
+ uint32_t setmax;
+ uint32_t setnums_last;
+ uint32_t setpos;
+ uint32_t setpos_backend;
+ char **curitems;
+ uint32_t *setnums;
+ uint32_t *setnums_backend;
+ BIGNUM *combo = NULL;
+ BIGNUM *count = NULL;
+ BIGNUM *ncombos = NULL;
+ BIGNUM *seek = NULL;
+ int (*action)(struct cmb_config *config, uint32_t nitems,
+ char *items[]) = cmb_print;
+
+ if (nitems == 0)
+ return (0);
+
+ /* Process config options */
+ if (config != NULL) {
+ if (config->action != NULL)
+ action = config->action;
+ 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;
+ }
+ show_empty = config->show_empty;
+ 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;
+ }
+ }
+
+ /* 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 > nitems)
+ setinit = nitems;
+ if (setdone > nitems)
+ setdone = nitems;
+
+ /* Set the direction of flow (incrementing vs. decrementing) */
+ if (setinit > setdone)
+ nextset = -1;
+
+ /* 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?!");
+
+ /* Show the empty set consisting of a single combination of no-items */
+ if (nextset > 0 && show_empty) {
+ if (!doseek) {
+ retval = action(config, 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;
+ }
+ }
+
+ /*
+ * 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 += 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;
+ }
+
+ /* 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 */
+ for (n = 0; n < curset; n++)
+ curitems[n] = items[n];
+
+ /* Produce results with the first set of items */
+ if (!doseek) {
+ retval = action(config, 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 nitems-N and ending at nitems (again, N is the
+ * same integer as the current set we are operating on; nitems
+ * is the total number of items). For example, if we are
+ * operating on a set-of-2, and nitems 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++] = nitems - 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;
+
+ /* 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;
+ retval = action(config, 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))) {
+ retval = action(config, 0, NULL);
+ }
+ }
+
+cmb_bn_return:
+ BN_free(combo);
+ BN_free(count);
+ BN_free(ncombos);
+ BN_free(seek);
+
+ return (retval);
+}
+#endif /* HAVE_OPENSSL_BN_H */
Index: share/mk/src.libnames.mk
===================================================================
--- share/mk/src.libnames.mk
+++ share/mk/src.libnames.mk
@@ -80,6 +80,7 @@
cap_random \
cap_sysctl \
cap_syslog \
+ cmb \
com_err \
compiler_rt \
crypt \
@@ -338,6 +339,9 @@
_DP_zfs_core= nvpair
_DP_zpool= md pthread z nvpair avl umem
_DP_be= zfs nvpair
+.if ${MK_OPENSSL} != "no"
+_DP_cmb= crypto
+.endif
# OFED support
.if ${MK_OFED} != "no"
@@ -477,6 +481,8 @@
LIBBE?= ${LIBBEDIR}/libbe.a
+LIBCMB?= ${LIBCMBDIR}/libcmb.a
+
LIBPMCSTATDIR= ${OBJTOP}/lib/libpmcstat
LIBPMCSTAT?= ${LIBPMCSTATDIR}/libpmcstat.a
Index: usr.bin/Makefile
===================================================================
--- usr.bin/Makefile
+++ usr.bin/Makefile
@@ -18,6 +18,7 @@
chat \
chpass \
cksum \
+ cmb \
cmp \
col \
colldef \
Index: usr.bin/cmb/Makefile
===================================================================
--- /dev/null
+++ usr.bin/cmb/Makefile
@@ -0,0 +1,16 @@
+# $FreeBSD$
+
+.include <src.opts.mk>
+
+PROG= cmb
+
+CFLAGS+= -I${.CURDIR}
+
+LIBADD= cmb
+
+.if ${MK_OPENSSL} != "no"
+CFLAGS+= -DHAVE_LIBCRYPTO
+LIBADD+= crypto
+.endif
+
+.include <bsd.prog.mk>
Index: usr.bin/cmb/cmb.1
===================================================================
--- /dev/null
+++ usr.bin/cmb/cmb.1
@@ -0,0 +1,262 @@
+.\" Copyright (c) 2018 Devin Teske <dteske@FreeBSD.org>
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\" $FrauBSD: pkgcenter/depend/cmb/cmb.1 2018-11-04 01:38:00 -0700 freebsdfrau $
+.\" $FreeBSD$
+.\"
+.Dd November 4, 2018
+.Dt CMB 1
+.Os
+.Sh NAME
+.Nm cmb
+.Nd combinatorics utility
+.Sh SYNOPSIS
+.Nm
+.Op Fl 0et
+.Op Fl c Ar #
+.Op Fl d Ar str
+.Op Fl i Ar #
+.Op Fl k Ar size
+.Op Fl p Ar str
+.Op Fl s Ar str
+.Ar item1
+.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.
+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 ".Fl r Ar size"
+.It Fl 0
+Terminate combinations with ASCII NUL
+.Pq character code 0
+instead of newline.
+Use in conjunction with
+.Dq Li xargs -0
+for example.
+.It Fl c Ar num
+Produce
+.Ar num
+combinations.
+If
+.Ql 0
+.Pq default
+all combinations produced.
+.It Fl d Ar text
+Delimiter for separating items.
+Default is space
+.Pq Dq " " .
+.It Fl e
+Show empty set.
+A single combination containing no-items.
+.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.
+.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 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 p Ar text
+Prefix each combination with
+.Ar text .
+.It Fl s Ar text
+Suffix each combination with
+.Ar text .
+.It Fl t
+Print total number of combinations and exit.
+.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 1 2 3 4 5 6 1 2 3 4 5 6
+.Ed
+.Sh HISTORY
+The
+.Nm
+utility first appeared in
+.Fx 13.0 .
+.Sh AUTHORS
+.An Devin Teske Aq Mt dteske@FreeBSD.org
Index: usr.bin/cmb/cmb.c
===================================================================
--- /dev/null
+++ usr.bin/cmb/cmb.c
@@ -0,0 +1,302 @@
+/*-
+ * Copyright (c) 2018 Devin Teske <dteske@FreeBSD.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#ifdef __FBSDID
+__FBSDID("$FrauBSD: pkgcenter/depend/cmb/cmb.c 2018-11-04 01:09:33 -0700 freebsdfrau $");
+__FBSDID("$FreeBSD$");
+#endif
+
+#include <sys/param.h>
+
+#include <cmb.h>
+#include <err.h>
+#include <errno.h>
+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.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_BN_H
+#include <openssl/bn.h>
+#else
+#include <sys/time.h>
+#endif
+#ifdef HAVE_OPENSSL_CRYPTO_H
+#include <openssl/crypto.h>
+#endif
+
+/* Environment */
+static char *pgm; /* set to argv[0] by main() */
+
+/* Function prototypes */
+static void usage(void);
+#ifndef HAVE_OPENSSL_BN_H
+static uint64_t rand_range(uint64_t range);
+#endif
+
+/* Inline functions */
+#ifndef HAVE_OPENSSL_BN_H
+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) + lrand48());
+}
+#endif
+
+int
+main(int argc, char *argv[])
+{
+ uint8_t opt_randi = FALSE;
+ uint8_t opt_empty = FALSE;
+ uint8_t opt_total = FALSE;
+ char *cp;
+ int ch;
+ int retval = EXIT_SUCCESS;
+ uint64_t nitems = 0;
+ size_t config_size = sizeof(struct cmb_config);
+ size_t optlen;
+ struct cmb_config *config = NULL;
+#if defined(HAVE_OPENSSL_BN_H) && defined(HAVE_OPENSSL_CRYPTO_H)
+ BIGNUM *count;
+#else
+ uint64_t count;
+ uint64_t nstart = 0; /* negative start */
+ struct timeval tv;
+#endif
+
+ 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
+ */
+ while ((ch = getopt(argc, argv, "0c:d:ei:k:n:p:s:t")) != -1) {
+ switch(ch) {
+ case '0': /* NUL terminate */
+ config->nul_terminate = TRUE;
+ break;
+ case 'c': /* count */
+#ifdef HAVE_OPENSSL_BN_H
+ if (BN_dec2bn(&(config->count_bn), optarg) == 0)
+ errx(EXIT_FAILURE, "OpenSSL Error?!");
+#else
+ config->count = strtoull(optarg, (char **)NULL, 10);
+#endif
+ break;
+ case 'd': /* delimiter */
+ config->delimiter = optarg;
+ break;
+ case 'e': /* empty */
+ opt_empty = TRUE;
+ config->show_empty = opt_empty;
+ break;
+ case 'i': /* start */
+ if ((optlen = strlen(optarg)) > 0 &&
+ strncmp("random", optarg, optlen) == 0) {
+ opt_randi = TRUE;
+ }
+#ifdef HAVE_OPENSSL_BN_H
+ if (!opt_randi &&
+ BN_dec2bn(&(config->start_bn), optarg) == 0)
+ errx(EXIT_FAILURE, "OpenSSL Error?!");
+#else
+ if (!opt_randi) {
+ config->start =
+ strtoull(optarg, (char **)NULL, 10);
+ if (*optarg == '-' && config->start > 0) {
+ nstart =
+ strtoll(optarg, (char **)NULL, 10);
+ }
+ }
+#endif
+ break;
+ case 'k': /* size */
+ config->size_min = strtoull(optarg, (char **)NULL, 10);
+ if ((cp = strstr(optarg, "..")) != NULL) {
+ config->size_max =
+ strtoull(cp + 2, (char **)NULL, 10);
+ } else if ((cp = strstr(optarg, "-")) != NULL) {
+ config->size_max =
+ strtoull(cp + 1, (char **)NULL, 10);
+ } else {
+ config->size_max = config->size_min;
+ }
+ break;
+ case 'n': /* args */
+ nitems = strtoull(optarg, (char **)NULL, 10);
+ break;
+ case 'p': /* prefix */
+ config->prefix = optarg;
+ break;
+ case 's': /* suffix */
+ config->suffix = optarg;
+ break;
+ case 't': /* total */
+ opt_total = TRUE;
+ break;
+ default: /* unhandled argument (based on switch) */
+ usage();
+ /* NOTREACHED */
+ }
+ }
+ argc -= optind;
+ argv += optind;
+
+ /* At least one non-option argument is required */
+ if (argc == 0 && !opt_empty)
+ usage(); /* NOTREACHED */
+
+ /*
+ * Calculate combinations
+ */
+ if (nitems == 0 || nitems > (uint64_t)argc)
+ nitems = (uint64_t)argc;
+ if (opt_total) {
+#if defined(HAVE_OPENSSL_BN_H) && defined(HAVE_OPENSSL_CRYPTO_H)
+ char *count_str;
+
+ if ((count = cmb_count_bn(config, nitems)) != NULL) {
+ count_str = BN_bn2dec(count);
+ printf("%s\n", count_str);
+ OPENSSL_free(count_str);
+ BN_free(count);
+ } else
+ printf("0\n");
+#else
+ count = cmb_count(config, nitems);
+ if (errno)
+ err(errno, NULL);
+ printf("%"PRIu64"\n", count);
+#endif
+ } else {
+#ifdef HAVE_OPENSSL_BN_H
+ if (opt_randi) {
+ if ((count = cmb_count_bn(config, nitems)) != NULL) {
+ if (config->start_bn == NULL)
+ config->start_bn = BN_new();
+ if (BN_rand_range(config->start_bn, count))
+ BN_add_word(config->start_bn, 1);
+ }
+ } else if (config->start_bn != NULL &&
+ BN_is_negative(config->start_bn)) {
+ if ((count = cmb_count_bn(config, nitems)) != NULL) {
+ BN_add(config->start_bn,
+ count, 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);
+ }
+ }
+ retval = cmb_bn(config, nitems, argv);
+#else
+ if (opt_randi) {
+ count = cmb_count(config, nitems);
+ if (errno)
+ err(errno, NULL);
+ if (gettimeofday(&tv,NULL) == 0) {
+ srand48((long)tv.tv_usec);
+ config->start = rand_range(count) + 1;
+ }
+ } else if (nstart != 0) {
+ count = cmb_count(config, nitems);
+ if (errno)
+ err(errno, NULL);
+ if (count >= (nstart * -1))
+ config->start = count + nstart + 1;
+ else
+ config->start = 0;
+ }
+ retval = cmb(config, nitems, argv);
+ if (errno)
+ err(errno, NULL);
+#endif
+ }
+
+ return (retval);
+}
+
+/*
+ * Print short usage statement to stderr and exit with error status.
+ */
+static void
+usage(void)
+{
+ fprintf(stderr, "usage: %s [options] item1 item2 ...\n", pgm);
+#define OPTFMT "\t%-10s %s\n"
+ fprintf(stderr, "OPTIONS:\n");
+ fprintf(stderr, OPTFMT, "-0",
+ "NUL terminate combinations (use with `xargs -0').");
+ fprintf(stderr, OPTFMT, "-c num",
+ "Produce num combinations (default `0' for all).");
+ fprintf(stderr, OPTFMT, "-d str", "Item delimiter (default is ` ').");
+ fprintf(stderr, OPTFMT, "-e", "Show empty set with no items.");
+ 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 num",
+ "Limit arguments taken from the command-line.");
+ fprintf(stderr, OPTFMT, "-p str", "Prefix text for each line.");
+ fprintf(stderr, OPTFMT, "-s str", "Suffix text for each line.");
+ fprintf(stderr, OPTFMT, "-t",
+ "Print number of combinations and exit.");
+ exit(EXIT_FAILURE);
+}
+
+#ifndef HAVE_OPENSSL_BN_H
+/*
+ * Return pseudo-random 64-bit unsigned integer in range 0 <= return <= range.
+ */
+static uint64_t
+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);
+}
+#endif

File Metadata

Mime Type
text/plain
Expires
Thu, Jan 15, 4:02 PM (2 h, 53 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27652938
Default Alt Text
D16132.id50015.diff (48 KB)

Event Timeline