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,13 @@ +# $FreeBSD$ + +PACKAGE=lib${LIB} +LIB= cmb +SHLIB_MAJOR= 0 +INCS= cmb.h +MAN= cmb.3 + +SRCS= cmb.c + +CFLAGS+= -I${.CURDIR} + +.include Index: lib/libcmb/cmb.h =================================================================== --- /dev/null +++ lib/libcmb/cmb.h @@ -0,0 +1,98 @@ +/*- + * Copyright (c) 2002-2018 Devin Teske + * All rights reserved. + * + * 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-03-29 15:27:50 -0700 freebsdfrau $ + * $FreeBSD$ + */ + +#ifndef _CMB_H_ +#define _CMB_H_ + +#include +#include + +#include +#include + +#ifdef HAVE_CONFIG_H +#include "config.h" +#elif defined(__FreeBSD_version) +#define HAVE_OPENSSL_BN_H 1 +#endif + +#ifdef HAVE_OPENSSL_BN_H +#include +#endif + +#ifndef TRUE +#define TRUE 1 +#endif +#ifndef FALSE +#define FALSE 0 +#endif + +static uint8_t cmb_print_nul = FALSE; +static const char *cmb_print_delimiter = " "; +static const char *cmb_print_prefix = NULL; +static const char *cmb_print_suffix = NULL; + +/* + * Anatomy of config option to pass as cmb*() config argument + */ +struct cmb_config { + uint8_t nul_terminate; /* Terminate combinations with ASCII NUL */ + char *delimiter; /* Item separator (default is " ") */ + char *prefix; /* Prefix for each combination */ + char *suffix; /* Suffix for each combination */ + uint32_t range_min; /* Minimum number of elements in combination */ + uint32_t range_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)(uint32_t nitems, char *items[]); +}; + +__BEGIN_DECLS +int cmb(struct cmb_config *_config, uint32_t _nitems, char *_items[]); +int cmb_print(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,150 @@ +.\" Copyright (c) 2018 Devin Teske +.\" All rights reserved. +.\" +.\" 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-07-04 22:39:18 +0000 freebsdfrau $ +.\" +.Dd July 4, 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 "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" +#endif +.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 */ + char *delimiter; /* Item separator (default is " ") */ + char *prefix; /* Prefix for each combination */ + char *suffix; /* Suffix for each combination */ + uint32_t range_min; /* Minimum elements in combination */ + uint32_t range_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)(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 +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 range_min +and +.Ar range_max . +Only combinations containing at minimum +.Ar range_min +items and at most +.Ar range_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 12.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,696 @@ +/*- + * Copyright (c) 2002-2018 Devin Teske + * All rights reserved. + * + * 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-04-03 10:38:24 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#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) +{ + 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; + + if (nitems == 0) return (0); + + /* Process config options */ + if (config != NULL) { + if (config->range_min != 0 || config->range_max != 0) { + setinit = config->range_min; + setdone = config->range_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; + + /* If entire set is requested, return 2^N-1 */ + if ((setinit == 1 && setdone == nitems) || + (setinit == nitems && setdone == 1)) + 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 + */ + 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) + errx(EXIT_FAILURE, "Number too large!"); + if (ncombos > ULLONG_MAX - count) + errx(EXIT_FAILURE, "Number too large!"); + 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; + 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)(uint32_t nitems, char *items[]) = cmb_print; + + if (nitems == 0) return (0); + + /* Process config options */ + if (config != NULL) { + cmb_print_nul = config->nul_terminate; + if (config->action != NULL) action = config->action; + if (config->count != 0) { + docount = TRUE; + count = config->count; + } + if (config->delimiter != NULL) + cmb_print_delimiter = config->delimiter; + if (config->prefix != NULL) cmb_print_prefix = config->prefix; + if (config->range_min != 0 || config->range_max != 0) { + setinit = config->range_min; + setdone = config->range_max; + } + if (config->start > 1) { + doseek = TRUE; + seek = config->start; + } + if (config->suffix != NULL) cmb_print_suffix = config->suffix; + } + + /* 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?!"); + + /* + * 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) + errx(EXIT_FAILURE, "Number too large!"); + + /* Jump to next set if requested start is beyond this one */ + if (doseek) { + if (seek > ncombos) { + seek -= ncombos; + 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) { + if ((retval = action(curset, curitems)) != 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; + if ((retval = action(curset, curitems)) != 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 */ + +cmb_return: + free(curitems); + free(setnums); + free(setnums_backend); + + return (retval); +} + +int +cmb_print(uint32_t nitems, char *items[]) +{ + uint32_t n; + + if (cmb_print_prefix != NULL) printf("%s", cmb_print_prefix); + for (n = 0; n < nitems; n++) { + printf("%s", items[n]); + if (n < nitems - 1 && cmb_print_delimiter != NULL) + 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) +{ + 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) { + if (config->range_min != 0 || config->range_max != 0) { + setinit = config->range_min; + setdone = config->range_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 (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 (!BN_lshift(count, BN_value_one(), nitems)) + goto cmb_count_bn_return; + if (!BN_sub_word(count, 1)) goto cmb_count_bn_return; + 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; + 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)(uint32_t nitems, char *items[]) = cmb_print; + + if (nitems == 0) return (0); + + /* Process config options */ + if (config != NULL) { + cmb_print_nul = config->nul_terminate; + 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; + } + if (config->delimiter != NULL) + cmb_print_delimiter = config->delimiter; + if (config->prefix != NULL) cmb_print_prefix = config->prefix; + if (config->range_min != 0 || config->range_max != 0) { + setinit = config->range_min; + setdone = config->range_max; + } + if (config->start_bn != NULL && + !BN_is_negative(config->start_bn) && + !BN_is_zero(config->start_bn) && + !BN_is_one(config->start_bn)) + { + doseek = TRUE; + if ((seek = BN_dup(config->start_bn)) == NULL) + goto cmb_bn_return; + } + if (config->suffix != NULL) cmb_print_suffix = config->suffix; + } + + /* 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?!"); + + /* + * 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; + 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) { + if ((retval = action(curset, curitems)) != 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; + if ((retval = action(curset, curitems)) != 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 */ + +cmb_bn_return: + BN_free(combo); + BN_free(count); + BN_free(ncombos); + BN_free(seek); + + return (retval); +} +#endif /* HAVE_OPENSSL_BN_H */ 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,11 @@ +# $FreeBSD$ + +PROG= cmb + +CFLAGS+= -I${.CURDIR} + +LIBADD= -lcmb -lcrypto + +WARNS?= 6 + +.include Index: usr.bin/cmb/cmb.1 =================================================================== --- /dev/null +++ usr.bin/cmb/cmb.1 @@ -0,0 +1,104 @@ +.\" Copyright (c) 2018 Devin Teske +.\" All rights reserved. +.\" +.\" 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. +.\" +.\" $FreeBSD$ +.\" +.Dd July 4, 2018 +.Dt CMB 1 +.Os +.Sh NAME +.Nm cmb +.Nd combinatorics utility +.Sh SYNOPSIS +.Nm +.Op Fl 0t +.Op Fl c Ar # +.Op Fl d Ar str +.Op Fl i Ar # +.Op Fl k Ar range +.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 , +separated by space +.Pq default . +.Pp +Available options: +.Bl -tag -width ".Fl r Ar range" +.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. +.It Fl i Ar num +Set starting position in combination set. +Default is 1. +.It Fl k Ar range +Number or range +.Pq Qo min..max Qc or Qo min-max Qc +of how many items appear in each combination. +A value of +.Ql 0 +.Pq default +calculates all combinations. +.It Fl n Ar num +Use +.Ar num +arguments. +Default is to use all 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 HISTORY +The +.Nm +utility first appeared in +.Fx 12.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,188 @@ +/*- + * Copyright (c) 2018 Devin Teske + * All rights reserved. + * + * 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.c 2018-07-04 22:56:58 +0000 freebsdfrau $ + * $FreeBSD$ + */ + +#include +#ifdef __FBSDID +__FBSDID("$FrauBSD: pkgcenter/depend/cmb/cmb.c 2018-07-04 22:56:58 +0000 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include + +#include +#include +#define __STDC_FORMAT_MACROS +#include +#include +#include +#include +#include +#include + +#ifdef HAVE_CONFIG_H +#include "config.h" +#elif defined(__FreeBSD_version) +#define HAVE_OPENSSL_BN_H 1 +#define HAVE_OPENSSL_CRYPTO_H 1 +#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_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:i: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 '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': /* range */ + config->range_min = + strtoull(optarg, (char **)NULL, 10); + if ((cp = strstr(optarg, "..")) != NULL) { + config->range_max = + strtoull(cp + 2, (char **)NULL, 10); + } else if ((cp = strstr(optarg, "-")) != NULL) { + config->range_max = + strtoull(cp + 1, (char **)NULL, 10); + } else { + config->range_max = config->range_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) usage(); /* NOTREACHED */ + + /* + * Calculate combinations + */ + if (nitems == 0) 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 + printf("%"PRIu64"\n", cmb_count(config, nitems)); +#endif + } else { +#ifdef HAVE_OPENSSL_BN_H + retval = cmb_bn(config, nitems, argv); +#else + retval = cmb(config, nitems, argv); +#endif + } + + return (retval); +} + +/* + * Print short usage statement to stderr and exit with error status. + */ +static void +usage(void) +{ + fprintf(stderr, "usage: %s %s item1 ...\n", pgm, + "[-0t] [-c #] [-d str] [-i #] [-k range] [-p str] [-s str]"); + exit(EXIT_FAILURE); +}