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 + +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 Index: lib/libcmb/cmb.h =================================================================== --- /dev/null +++ lib/libcmb/cmb.h @@ -0,0 +1,98 @@ +/*- + * Copyright (c) 2002-2018 Devin Teske + * + * 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 +#include + +#include +#include + +#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 +#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 +.\" +.\" 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 + * + * 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 +#ifdef __FBSDID +__FBSDID("$FrauBSD: pkgcenter/depend/libcmb/cmb.c 2018-11-03 12:15:22 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include +#include +#include +#include +#include +#include +#include + +#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 + +PROG= cmb + +CFLAGS+= -I${.CURDIR} + +LIBADD= cmb + +.if ${MK_OPENSSL} != "no" +CFLAGS+= -DHAVE_LIBCRYPTO +LIBADD+= crypto +.endif + +.include Index: usr.bin/cmb/cmb.1 =================================================================== --- /dev/null +++ usr.bin/cmb/cmb.1 @@ -0,0 +1,219 @@ +.\" Copyright (c) 2018 Devin Teske +.\" +.\" 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-03 11:49:59 -0700 freebsdfrau $ +.\" $FreeBSD$ +.\" +.Dd November 3, 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. +.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. +The order of combinations in each set is unaffected by negative +.Va size +values. +.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 the first 3 combinations given +.Qq 1 , +.Qq 2 , +and +.Qq 3 , +.Bd -literal -offset indent +cmb -i 4 1 2 3 +.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 two- and three-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 +.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,220 @@ +/*- + * Copyright (c) 2018 Devin Teske + * + * 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 +#ifdef __FBSDID +__FBSDID("$FrauBSD: pkgcenter/depend/cmb/cmb.c 2018-11-03 11:49:59 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include + +#include +#include +#include +#define __STDC_FORMAT_MACROS +#include +#include +#include +#include +#include +#include + +#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 +#endif +#ifdef HAVE_OPENSSL_CRYPTO_H +#include +#endif + +/* Environment */ +static char *pgm; /* set to argv[0] by main() */ + +/* Function prototypes */ +static void usage(void); + +int +main(int argc, char *argv[]) +{ + 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); + struct cmb_config *config = NULL; + + 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 */ +#ifdef HAVE_OPENSSL_BN_H + if (BN_dec2bn(&(config->start_bn), optarg) == 0) + errx(EXIT_FAILURE, "OpenSSL Error?!"); +#else + config->start = strtoull(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) + BIGNUM *count; + 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 + uint64_t count; + + count = cmb_count(config, nitems); + if (errno) + err(errno, NULL); + printf("%"PRIu64"\n", count); +#endif + } else { +#ifdef HAVE_OPENSSL_BN_H + retval = cmb_bn(config, nitems, argv); +#else + 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); +}