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,22 @@ +# $FreeBSD$ + +.include + +PACKAGE=lib${LIB} +LIB= cmb +SHLIB_MAJOR= 0 +INCS= cmb.h +MAN= cmb.3 + +SRCS= cmb.c + +CFLAGS+= -I${.CURDIR} + +LIBADD+= m + +.if ${MK_OPENSSL} != "no" +CFLAGS+= -DHAVE_LIBCRYPTO +LIBADD+= crypto +.endif + +.include Index: lib/libcmb/cmb.h =================================================================== --- /dev/null +++ lib/libcmb/cmb.h @@ -0,0 +1,394 @@ +/*- + * Copyright (c) 2002-2019 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 2019-08-23 18:07:49 -0700 freebsdfrau $ + * $FreeBSD$ + */ + +#ifndef _CMB_H_ +#define _CMB_H_ + +#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_CRYPTO_H +#include +#endif +#ifdef HAVE_OPENSSL_BN_H +#include +#ifndef OPENSSL_free +#define OPENSSL_free(x) (void)(x) +#endif +#endif + +#ifndef TRUE +#define TRUE 1 +#endif +#ifndef FALSE +#define FALSE 0 +#endif + +#ifndef CMB_DEBUG +#define CMB_DEBUG FALSE +#endif + +/* + * Version constants for cmb_version(3) + */ +#define CMB_VERSION 0 +#define CMB_VERSION_LONG 1 + +/* + * Header version info + */ +#define CMB_H_VERSION_MAJOR 3 +#define CMB_H_VERSION_MINOR 5 +#define CMB_H_VERSION_PATCH 6 + +/* + * Macros for cmb_config options bitmask + */ +#define CMB_OPT_DEBUG 0x01 /* Enable debugging */ +#define CMB_OPT_NULPARSE 0x02 /* NUL delimit cmb_parse*() */ +#define CMB_OPT_NULPRINT 0x04 /* NUL delimit cmb_print*() */ +#define CMB_OPT_EMPTY 0x08 /* Show empty set with no items */ +#define CMB_OPT_NUMBERS 0x10 /* Show combination sequence numbers */ +#define CMB_OPT_RESERVED 0x20 /* Reserved for future use by cmb(3) */ +#define CMB_OPT_OPTION1 0x40 /* Available (unused by cmb(3)) */ +#define CMB_OPT_OPTION2 0x80 /* Available (unused by cmb(3)) */ + +/* + * Macros for defining call-back functions/pointers + */ +#define CMB_ACTION(x) \ + int x(struct cmb_config *config, uint64_t seq, uint32_t nitems, \ + char *items[]) +#ifdef HAVE_OPENSSL_BN_H +#define CMB_ACTION_BN(x) \ + int x(struct cmb_config *config, BIGNUM *seq, uint32_t nitems, \ + char *items[]) +#endif + +/* + * Build info + */ +struct cmb_build_info { + uint8_t debug; /* CMB_DEBUG */ +}; +extern struct cmb_build_info cmb_build_info; + +/* + * Anatomy of config option to pass as cmb*() config argument + */ +struct cmb_config { + uint8_t options; /* CMB_OPT_* bitmask. Default 0 */ + char *delimiter; /* Item separator (default is " ") */ + char *prefix; /* Prefix for each combination */ + char *suffix; /* Suffix for each combination */ + uint32_t size_min; /* Minimum number of elements in combination */ + uint32_t size_max; /* Maximum number of elements in combination */ + + uint64_t count; /* Number of combinations */ + uint64_t start; /* Starting combination */ + + void *data; /* Reserved for action callback */ + + /* + * cmb(3) function callback; called for each combination (default is + * cmb_print()). If the return from action() is non-zero, cmb() will + * stop calculation. The cmb() return value is the first non-zero + * result from action(), zero otherwise. + */ + CMB_ACTION((*action)); + +#ifdef HAVE_OPENSSL_BN_H + BIGNUM *count_bn; /* bn(3) number of combinations */ + BIGNUM *start_bn; /* bn(3) starting combination */ + + /* + * cmb_bn(3) function callback; called for each combination (default is + * cmb_print_bn()). If the return from action_bn() is non-zero, + * cmb_bn() will stop calculation. The cmb_bn() return value is the + * first non-zero result from action_bn(), zero otherwise. + */ + CMB_ACTION_BN((*action_bn)); +#endif +}; + +__BEGIN_DECLS +int cmb(struct cmb_config *_config, uint32_t _nitems, + char *_items[]); +uint64_t cmb_count(struct cmb_config *_config, uint32_t _nitems); +char ** cmb_parse(struct cmb_config *_config, int _fd, + uint32_t *_nitems, uint32_t _max); +char ** cmb_parse_file(struct cmb_config *_config, char *_path, + uint32_t *_nitems, uint32_t _max); +int cmb_print(struct cmb_config *_config, uint64_t _seq, + uint32_t _nitems, char *_items[]); +const char * cmb_version(int _type); +#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); +int cmb_print_bn(struct cmb_config *_config, BIGNUM *_seq, + uint32_t _nitems, char *_items[]); +#endif + +/* Inline functions */ +static inline void cmb_print_seq(uint64_t seq) { printf("%"PRIu64" ", seq); } +#ifdef HAVE_OPENSSL_BN_H +static inline void cmb_print_seq_bn(BIGNUM *seq) { char *seq_str; + printf("%s ", seq_str = BN_bn2dec(seq)); + OPENSSL_free(seq_str); +} +#endif /* HAVE_OPENSSL_BN_H */ +__END_DECLS + +/* + * Transformations + */ + +extern int cmb_transform_precision; +struct cmb_xitem { + char *cp; /* original item */ + union cmb_xitem_type { + long double ld; /* item as long double */ + } as; +}; + +#define CMB_TRANSFORM_EQ(eq, op, x, seqt, seqp) \ + int \ + x(struct cmb_config *config, seqt seq, uint32_t nitems, char *items[]) \ + { \ + uint8_t show_numbers = FALSE; \ + uint32_t n; \ + long double ld; \ + long double total = 0; \ + const char *delimiter = " "; \ + const char *prefix = NULL; \ + const char *suffix = NULL; \ + struct cmb_xitem *xitem = NULL; \ + \ + if (config != NULL) { \ + if (config->delimiter != NULL) \ + delimiter = config->delimiter; \ + if ((config->options & CMB_OPT_NUMBERS) != 0) \ + show_numbers = TRUE; \ + prefix = config->prefix; \ + suffix = config->suffix; \ + } \ + if (!opt_silent) { \ + if (show_numbers) \ + seqp(seq); \ + if (prefix != NULL && !opt_quiet) \ + printf("%s", prefix); \ + } \ + if (nitems > 0) { \ + memcpy(&xitem, &items[0], sizeof(struct cmb_xitem *)); \ + total = xitem->as.ld; \ + if (!opt_silent && !opt_quiet) { \ + printf("%s", xitem->cp); \ + if (nitems > 1) \ + printf("%s" #op "%s", delimiter, delimiter); \ + } \ + } \ + for (n = 1; n < nitems; n++) { \ + memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \ + ld = xitem->as.ld; \ + total = eq; \ + if (!opt_silent && !opt_quiet) { \ + printf("%s", xitem->cp); \ + if (n < nitems - 1) \ + printf("%s" #op "%s", delimiter, delimiter); \ + } \ + } \ + if (!opt_silent) { \ + if (suffix != NULL && !opt_quiet) \ + printf("%s", suffix); \ + printf("%s%.*Lf\n", opt_quiet ? "" : " = ", \ + cmb_transform_precision, total); \ + } \ + return (0); \ + } + +#define CMB_TRANSFORM_OP(op, x) \ + CMB_TRANSFORM_EQ(total op ld, op, x, uint64_t, cmb_print_seq) +#define CMB_TRANSFORM_FN(op, fn, x) \ + CMB_TRANSFORM_EQ(fn(total, ld), op, x, uint64_t, cmb_print_seq) + +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +#define CMB_TRANSFORM_OP_BN(op, x) \ + CMB_TRANSFORM_EQ(total op ld, op, x, BIGNUM *, cmb_print_seq_bn) +#define CMB_TRANSFORM_FN_BN(op, fn, x) \ + CMB_TRANSFORM_EQ(fn(total, ld), op, x, BIGNUM *, cmb_print_seq_bn) +#endif + +/* + * Example transformations + */ + +#if 0 +CMB_TRANSFORM_OP(+, cmb_add); /* creates cmb_add() */ +CMB_TRANSFORM_FN(/, div, cmb_div); /* creates cmb_div() */ +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +CMB_TRANSFORM_OP_BN(+, cmb_add_bn); /* creates cmb_add_bn() */ +CMB_TRANSFORM_FN_BN(/, div, cmb_div_bn); /* creates cmb_div_bn() */ +#endif +#endif + +/* + * Find transformations + */ + +extern char *cmb_transform_find_buf; +extern int cmb_transform_find_buf_size; +extern struct cmb_xitem *cmb_transform_find; + +#define CMB_TRANSFORM_EQ_FIND(eq, op, x, seqt, seqp) \ + int \ + x(struct cmb_config *config, seqt seq, uint32_t nitems, char *items[]) \ + { \ + uint8_t show_numbers = FALSE; \ + uint32_t n; \ + int len; \ + long double ld; \ + long double total = 0; \ + const char *delimiter = " "; \ + const char *prefix = NULL; \ + const char *suffix = NULL; \ + struct cmb_xitem *xitem = NULL; \ + \ + for (n = 0; n < nitems; n++) { \ + memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \ + ld = xitem->as.ld; \ + total = eq; \ + } \ + if (cmb_transform_precision == 0) { \ + if (total != cmb_transform_find->as.ld) { \ + return (0); \ + } \ + } else { \ + len = snprintf(NULL, 0, "%.*Lf", \ + cmb_transform_precision, total) + 1; \ + if (len > cmb_transform_find_buf_size) { \ + cmb_transform_find_buf = \ + realloc(cmb_transform_find_buf, \ + (unsigned long)len); \ + if (cmb_transform_find_buf == NULL) { \ + errx(EXIT_FAILURE, "Out of memory?!"); \ + /* NOTREACHED */ \ + } \ + cmb_transform_find_buf_size = len; \ + } \ + (void)sprintf(cmb_transform_find_buf, "%.*Lf", \ + cmb_transform_precision, total); \ + if (strcmp(cmb_transform_find_buf, \ + cmb_transform_find->cp) != 0) \ + return (0); \ + } \ + if (config != NULL) { \ + if (config->delimiter != NULL) \ + delimiter = config->delimiter; \ + if ((config->options & CMB_OPT_NUMBERS) != 0) \ + show_numbers = TRUE; \ + prefix = config->prefix; \ + suffix = config->suffix; \ + } \ + if (!opt_silent) { \ + if (show_numbers) \ + seqp(seq); \ + if (prefix != NULL && !opt_quiet) \ + printf("%s", prefix); \ + } \ + if (nitems > 0) { \ + memcpy(&xitem, &items[0], sizeof(struct cmb_xitem *)); \ + if (!opt_silent && !opt_quiet) { \ + printf("%s", xitem->cp); \ + if (nitems > 1) \ + printf("%s" #op "%s", delimiter, delimiter); \ + } \ + } \ + for (n = 1; n < nitems; n++) { \ + memcpy(&xitem, &items[n], sizeof(struct cmb_xitem *)); \ + if (!opt_silent && !opt_quiet) { \ + printf("%s", xitem->cp); \ + if (n < nitems - 1) \ + printf("%s" #op "%s", delimiter, delimiter); \ + } \ + } \ + if (!opt_silent) { \ + if (suffix != NULL && !opt_quiet) \ + printf("%s", suffix); \ + printf("%s%.*Lf\n", opt_quiet ? "" : " = ", \ + cmb_transform_precision, total); \ + } \ + return (0); \ + } + +#define CMB_TRANSFORM_OP_FIND(op, x) \ + CMB_TRANSFORM_EQ_FIND(total op ld, op, x, uint64_t, cmb_print_seq) +#define CMB_TRANSFORM_FN_FIND(op, fn, x) \ + CMB_TRANSFORM_EQ_FIND(fn(total, ld), op, x, uint64_t, cmb_print_seq) + +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +#define CMB_TRANSFORM_OP_FIND_BN(op, x) \ + CMB_TRANSFORM_EQ_FIND(total op ld, op, x, BIGNUM *, cmb_print_seq_bn) +#define CMB_TRANSFORM_FN_FIND_BN(op, fn, x) \ + CMB_TRANSFORM_EQ_FIND(fn(total, ld), op, x, BIGNUM *, cmb_print_seq_bn) +#endif + +/* + * Example find transformations + */ + +#if 0 +CMB_TRANSFORM_OP_FIND(+, cmb_add_find); /* creates cmb_add_find() */ +CMB_TRANSFORM_FN_FIND(/, div, cmb_div_find); /* creates cmb_div_find() */ +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +CMB_TRANSFORM_OP_FIND_BN(+, cmb_add_bn); /* creates cmb_add_bn() */ +CMB_TRANSFORM_FN_FIND_BN(/, div, cmb_div_bn); /* creates cmb_div_bn() */ +#endif +#endif + +#endif /* !_CMB_H_ */ Index: lib/libcmb/cmb.3 =================================================================== --- /dev/null +++ lib/libcmb/cmb.3 @@ -0,0 +1,267 @@ +.\" Copyright (c) 2018-2019 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 2019-03-29 22:01:11 -0700 freebsdfrau $ +.\" $FreeBSD$ +.\" +.Dd March 29, 2019 +.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 uint64_t +.Fn cmb_count "struct cmb_config *config" "uint32_t nitems" +.Ft char ** +.Fn cmb_parse "struct cmb_config *config" "int fd" "uint32_t *nitems" "uint32_t max" +.Ft char ** +.Fn cmb_parse_file "struct cmb_config *config" "char *path" "uint32_t *nitems" "uint32_t max" +.Ft int +.Fn cmb_print "struct cmb_config *config" "uint64_t seq" "uint32_t nitems" "char *items[]" +.Ft const char * +.Fn cmb_version "int type" +.Pp +/* OpenSSL +.Xr bn 3 +support */ +.Pp +.Ft int +.Fn cmb_bn "struct cmb_config *config" "uint32_t nitems" "char *items[]" +.Ft "BIGNUM *" +.Fn cmb_count_bn "struct cmb_config *config" "uint32_t nitems" +.Ft int +.Fn cmb_print_bn "struct cmb_config *config" "BIGNUM *seq" "uint32_t nitems" "char *items[]" +.Sh DESCRIPTION +The +.Nm +library provides a light-weight, +portable, +and fast interface for enumerating combinations. +.Pp +Anatomy of config argument to +.Fn cmb* : +.Bd -literal -offset indent +struct cmb_config { + uint8_t options; /* CMB_OPT_* bitmask. Default 0 */ + char *delimiter; /* Item separator (default is " ") */ + char *prefix; /* Prefix for each combination */ + char *suffix; /* Suffix for each combination */ + uint32_t size_min; /* Minimum elements in combination */ + uint32_t size_max; /* Maximum elements in combination */ + + uint64_t count; /* Number of combinations */ + uint64_t start; /* Starting combination */ + + void *data; /* Reserved for action callback */ + + /* + * cmb(3) function callback; called for each combination + * (default is cmb_print()). If the return from action() is non- + * zero, cmb() will stop calculation. The cmb() return value is + * the first non-zero result from action(), zero otherwise. + */ + CMB_ACTION((*action)); + + /* OpenSSL bn(3) support */ + + BIGNUM *count_bn; /* Number of combinations */ + BIGNUM *start_bn; /* Starting combination */ + + /* + * cmb_bn(3) function callback; called for each combination + * (default is cmb_print_bn()). If the return from action_bn() + * is non-zero, cmb_bn() will stop calculation. The cmb_bn() + * return value is the first non-zero result from action_bn(), + * zero otherwise. + */ + CMB_ACTION_BN((*action_bn)); +}; +.Ed +.Pp +The macro +.Fn CMB_ACTION x +is defined as: +.Bd -literal -offset indent +int x(struct cmb_config *config, uint64_t seq, uint32_t nitems, + char *items[]); +.Ed +.Pp +When compiled with OpenSSL/LibreSSL support +.Pq default , +the macro +.Fn CMB_ACTION_BN x +is defined as: +.Bd -literal -offset indent +int x(struct cmb_config *config, BIGNUM *seq, uint32_t nitems, + char *items[]); +.Ed +.Pp +Macros for cmb_config options bitmask: +.Bd -literal -offset indent +CMB_OPT_DEBUG /* Enable debugging */ +CMB_OPT_NULPARSE /* NUL delimit cmb_parse*() */ +CMB_OPT_NULPRINT /* NUL delimit cmb_print*() */ +CMB_OPT_EMPTY /* Show empty set with no items */ +CMB_OPT_NUMBERS /* Show combination sequence numbers */ +CMB_OPT_RESERVED /* Reserved for future use by cmb(3) */ +CMB_OPT_OPTION1 /* Available (unused by cmb(3)) */ +CMB_OPT_OPTION2 /* Available (unused by cmb(3)) */ +.Ed +.Pp +If +.Ar CMB_OPT_DEBUG +is set and +.Xr cmb 3 +was compiled with +.Ql CMB_DEBUG , +enable debugging information on stderr. +.Pp +If +.Ar CMB_OPT_NULPARSE +is set, +.Fn cmb_parse +and +.Fn cmb_parse_file +will read items separated by ASCII NUL character +.Pq character code 0 . +Otherwise, +newline +.Pq character code 10 +is used. +.Pp +If +.Ar CMB_OPT_NULPRINT +is set, +.Fn cmb_print +and +.Fn cmb_print_bn +will print combination items separated by ASCII NUL character +.Pq character code 0 . +Otherwise, +.Ar delimiter +is used and if unset, +combinations are separated by a single space. +.Pp +If +.Ar CMB_OPT_EMPTY +is set, +the empty set +.Pq consisting of a single combination with no items +is enumerated by +.Fn cmb +/ +.Fn cmb_bn +and counted by +.Fn cmb_count +/ +.Fn cmb_count_bn . +.Pp +If +.Ar CMB_OPT_NUMBERS +is set, +print combination sequence number before calling +.Fn action . +Combinations are calculated in arithmetic progression, +providing predictable order. +The sequence number can be used as +.Ar start +or +.Ar start_bn +value to begin at that combination. +The sequence number precedes the prefix and is followed by a single space, +regardless of +.Ar delimiter . +.Pp +For each combination, +if +.Ar prefix +is non-NULL it is printed before the first item in each combination and +.Ar suffix , +if non-NULL, +is printed after the last item. +.Pp +To operate on only a subset or range of subsets, +use +.Ar size_min +and +.Ar size_max . +Only combinations containing at 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 +or +.Ar count_bn +to a non-zero value. +.Pp +If +.Ar start +or +.Ar start_bn +is greater than one, +the +.Nm +library will seek to that number combination before starting. +.Pp +.Ar action_bn , +.Ar count_bn , +and +.Ar start_bn +are only available on platforms with OpenSSL/LibreSSL +.Xr bn 3 +and are used by +.Fn cmb_bn +and +.Fn cmb_count_bn +to overcome limitations by 64-bit integers. +.Pp +.Fn cmb_version +takes +.Li CMB_VERSION +or +.Li CMB_VERSION_LONG +as +.Ar type +and returns string version. +For unknown +.Ar type , +the text +.Dq not available +is returned. +.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,1369 @@ +/*- + * Copyright (c) 2002-2019 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 2019-08-23 18:07:49 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include + +#include +#include +#include +#define __STDC_FORMAT_MACROS +#include +#include +#include +#include +#include +#include +#include +#include + +#include "cmb.h" +#include "cmb_private.h" + +#ifdef HAVE_OPENSSL_CRYPTO_H +#include +#endif + +#if CMB_DEBUG +#include +#include +#define CMB_DEBUG_PREFIX "DEBUG: " +#define CMB_DEBUG_PREFIX_LEN 7 +#ifndef CMB_DEBUG_BUFSIZE +#define CMB_DEBUG_BUFSIZE 2048 +#endif +#endif + +#ifndef PATH_MAX +#define PATH_MAX 1024 +#endif + +#ifndef CMB_PARSE_FRAGSIZE +#define CMB_PARSE_FRAGSIZE 512 +#endif + +static const char version[] = "libcmb 3.5.6"; +static const char version_long[] = "$Version: libcmb 3.5.6 $"; + +/* + * Build info + */ +struct cmb_build_info cmb_build_info = { + .debug = CMB_DEBUG, +}; + +/* + * Globals + */ +int cmb_transform_find_buf_size = 0; +int cmb_transform_precision = 0; +char *cmb_transform_find_buf = NULL; +struct cmb_xitem *cmb_transform_find = NULL; + +#if CMB_DEBUG +__attribute__((__format__ (__printf__, 1, 0))) +static void +cmb_debug(const char *fmt, ...) +{ + int len; + va_list ap; + char buf[CMB_DEBUG_BUFSIZE]; + + sprintf(buf, CMB_DEBUG_PREFIX); + va_start(ap, fmt); + len = vsnprintf(&buf[CMB_DEBUG_PREFIX_LEN], + sizeof(buf) - CMB_DEBUG_PREFIX_LEN - 1, fmt, ap); + va_end(ap); + if (len == -1) + len = sizeof(buf) - CMB_DEBUG_PREFIX_LEN - 1; + len += CMB_DEBUG_PREFIX_LEN; + buf[len++] = '\n'; + write(2, buf, (size_t)len); +} +#endif + +/* + * Takes one of below described type constants. Returns string version. + * + * TYPE DESCRIPTION + * CMB_VERSION Short version text. For example, "x.y". + * CMB_VERSION_LONG RCS style ($Version$). + * + * For unknown type, the text "not available" is returned. + */ +const char * +cmb_version(int type) +{ + switch(type) { + case CMB_VERSION: return (version); + case CMB_VERSION_LONG: return (version_long); + default: return ("not available"); + } +} + +/* + * Takes pointer to `struct cmb_config' options, file path to read items from, + * pointer to uint32_t (written-to, containing number of items read), and + * uint32_t to optionally maximum number of items read from file. Returns + * allocated array of char * items read from file. + */ +char ** +cmb_parse_file(struct cmb_config *config, char *path, uint32_t *nitems, + uint32_t max) +{ +#if CMB_DEBUG + uint8_t debug = FALSE; +#endif + int fd; + char rpath[PATH_MAX]; + +#if CMB_DEBUG + if (config != NULL) { + if ((config->options & CMB_OPT_DEBUG) != 0) + debug = TRUE; + } +#endif + + /* Resolve the file path */ + if (path == NULL || (path[0] == '-' && path[1] == '\0')) { + strcpy(rpath, "/dev/stdin"); + } else if (realpath(path, rpath) == 0) + return (NULL); + + /* Open the file */ + if ((fd = open(rpath, O_RDONLY)) < 0) + return (NULL); +#if CMB_DEBUG + if (debug) + cmb_debug("%s: opened `%s' fd=%u", __func__, rpath, fd); +#endif + + return (cmb_parse(config, fd, nitems, max)); +} + +/* + * Takes pointer to `struct cmb_config' options, file descriptor to read items + * from, pointer to uint32_t (written-to, containing number of items read), and + * uint32_t to optionally maximum number of items read from file. Returns + * allocated array of char * items read from file. + */ +char ** +cmb_parse(struct cmb_config *config, int fd, uint32_t *nitems, uint32_t max) +{ + char d = '\n'; +#if CMB_DEBUG + uint8_t debug = FALSE; +#endif + uint32_t _nitems; + char **items = NULL; + char *b, *buf; + char *p; + uint64_t n; + size_t bufsize, buflen; + size_t datasize = 0; + size_t fragsize = sizeof(char *) * CMB_PARSE_FRAGSIZE; + size_t itemsize = fragsize; + ssize_t r = 1; + struct stat sb; + + errno = 0; + + /* Process config options */ + if (config != NULL) { + if ((config->options & CMB_OPT_NULPARSE) != 0) + d = '\0'; + else if (config->delimiter != NULL) + if (*(config->delimiter) != '\0') + d = *(config->delimiter); +#if CMB_DEBUG + if ((config->options & CMB_OPT_DEBUG) != 0) + debug = TRUE; +#endif + } + + /* Use output block size as buffer size if available */ + if (fstat(fd, &sb) != 0) { + if (S_ISREG(sb.st_mode)) { + if (sysconf(_SC_PHYS_PAGES) > + PHYSPAGES_THRESHOLD) + bufsize = MIN(BUFSIZE_MAX, MAXPHYS * 8); + else + bufsize = BUFSIZE_SMALL; + } else + bufsize = (size_t)MAX(sb.st_blksize, + (blksize_t)sysconf(_SC_PAGESIZE)); + } else + bufsize = MIN(BUFSIZE_MAX, MAXPHYS * 8); + + /* Initialize buffer/pointers */ +#if CMB_DEBUG + if (debug) + cmb_debug("%s: reading fd=%u bufsize=%lu", + __func__, fd, bufsize); +#endif + if ((buf = malloc(bufsize)) == NULL) + return (NULL); + buflen = bufsize; + if ((items = malloc(itemsize)) == NULL) + return (NULL); + + /* Read the file until EOF */ + b = buf; + *nitems = _nitems = 0; + while (r != 0) { + r = read(fd, b, bufsize); + + /* Test for Error/EOF */ + if (r <= 0) + break; + + /* Resize the buffer if necessary */ + datasize += (size_t)r; + if (buflen - datasize < bufsize) { + buflen += bufsize; +#if CMB_DEBUG + if (debug) + cmb_debug("%s: increasing buffer to %lu bytes", + __func__, buflen); +#endif + if ((buf = realloc(buf, buflen)) == NULL) { + free(buf); + free(items); + return (NULL); + } + } + b = &buf[datasize]; + } + + if (datasize == 0) { +#if CMB_DEBUG + if (debug) + cmb_debug("%s: nitems=%u datasize=%lu", + __func__, *nitems, datasize); +#endif + free(buf); + free(items); + return (NULL); + } + + /* chomp trailing newline */ + if (buf[datasize-1] == '\n') + buf[datasize-1] = '\0'; + + /* Look for delimiter */ + p = buf; + for (n = 0; n < datasize; n++) { + if (buf[n] != d) + continue; + items[_nitems++] = p; + buf[n] = '\0'; + p = buf + n + 1; + if (max > 0 && _nitems >= max) + goto cmb_parse_return; + if (_nitems >= 0xffffffff) { + items = NULL; + errno = EFBIG; + goto cmb_parse_return; + } else if (_nitems % CMB_PARSE_FRAGSIZE == 0) { + itemsize += fragsize; + if ((items = realloc(items, itemsize)) == NULL) + goto cmb_parse_return; + } + } + if (p < buf + datasize) + items[_nitems++] = p; + +cmb_parse_return: + *nitems = _nitems; +#if CMB_DEBUG + if (debug) + cmb_debug("%s: nitems=%u datasize=%lu", + __func__, *nitems, datasize); +#endif + close(fd); + return (items); +} + +/* + * Takes pointer to `struct cmb_config' options and number of items. Returns + * total number of combinations according to config options. + */ +uint64_t +cmb_count(struct cmb_config *config, uint32_t 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) { + if ((config->options & CMB_OPT_EMPTY) != 0) + show_empty = TRUE; + if (config->size_min != 0 || config->size_max != 0) { + setinit = config->size_min; + setdone = config->size_max; + } + } + + /* Adjust values to be non-zero (mathematical constraint) */ + if (setinit == 0) + setinit = 1; + if (setdone == 0) + setdone = 1; + + /* Return zero if the request is out of range */ + if (setinit > 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 += (uint32_t)nextset) + { + /* Calculate number of combinations (incrementing) */ + if (nextset > 0) + z = (z * i--) / k++; + + /* Add number of combinations in this set to total */ + if ((ncombos = (uint64_t)z) == 0) { + errno = ERANGE; + return (0); + } + if (ncombos > ULLONG_MAX - count) { + errno = ERANGE; + return (0); + } + count += ncombos; + + /* Calculate number of combinations (decrementing) */ + if (nextset < 0) + z = (z * --k) / ++i; + } + + return (count); +} + +/* + * Takes pointer to `struct cmb_config' options, number of items, and array of + * `char *' items. Calculates combinations according to options and either + * prints combinations to stdout (default) or runs `action' if passed-in as + * function pointer member of `config' argument. + */ +int +cmb(struct cmb_config *config, uint32_t nitems, char *items[]) +{ +#if CMB_DEBUG + uint8_t debug = FALSE; +#endif + uint8_t docount = FALSE; + uint8_t doseek = FALSE; + uint8_t show_empty = FALSE; + uint8_t show_numbers = FALSE; + int8_t nextset = 1; + int retval = 0; + uint32_t curset; + uint32_t i = 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; + uint64_t seq = 1; + long double z = 1; + char **curitems; + uint32_t *setnums; + uint32_t *setnums_backend; + CMB_ACTION((*action)) = cmb_print; + + errno = 0; + + /* Process config options */ + if (config != NULL) { + if (config->action != NULL) + action = config->action; + if (config->count != 0) { + docount = TRUE; + count = config->count; + } + if ((config->options & CMB_OPT_DEBUG) != 0) { +#if CMB_DEBUG + debug = TRUE; +#else + warnx("libcmb not compiled with debug support!"); +#endif + } + if ((config->options & CMB_OPT_EMPTY) != 0) + show_empty = TRUE; + if ((config->options & CMB_OPT_NUMBERS) != 0) + show_numbers = TRUE; + if (config->size_min != 0 || config->size_max != 0) { + setinit = config->size_min; + setdone = config->size_max; + } + if (config->start > 1) { + doseek = TRUE; + seek = config->start; +#if CMB_DEBUG + if (show_numbers || debug) +#else + if (show_numbers) +#endif + seq = seek; + } + } + + if (!show_empty) { + if (nitems == 0) + return (0); + else if (cmb_count(config, nitems) == 0) + return (errno); + } + + /* Adjust values to be non-zero (mathematical constraint) */ + if (setinit == 0) + setinit = 1; + if (setdone == 0) + setdone = 1; + + /* Enforce limits so we don't run over bounds */ + if (setinit > nitems) + setinit = nitems; + if (setdone > nitems) + setdone = nitems; + + /* Set the direction of flow (incrementing vs. decrementing) */ + if (setinit > setdone) + nextset = -1; + + /* Show the empty set consisting of a single combination of no-items */ + if (nextset > 0 && show_empty) { +#if CMB_DEBUG + if (debug) + cmb_debug(">>> 0-item combinations <<<"); +#endif + if (!doseek) { + retval = action(config, seq++, 0, NULL); + if (retval != 0) + return (retval); + if (docount && --count == 0) + return (retval); + } else { + seek--; + if (seek == 1) + doseek = FALSE; + } + } + + if (nitems == 0) + return (0); + + /* Allocate memory */ + setmax = setdone > setinit ? setdone : setinit; + if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + if ((setnums_backend = + (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + + /* + * Loop over each `set' in the configured direction until we are done. + * NB: Each `set' can represent a single item or multiple items. + */ + p = nextset > 0 ? setinit - 1 : setinit; + for (k = 1; k <= p; k++) + z = (z * i--) / k; + for (curset = setinit; + nextset > 0 ? curset <= setdone : curset >= setdone; + curset += (uint32_t)nextset) + { +#if CMB_DEBUG + if (debug) + cmb_debug(">>> %u-item combinations <<<", curset); +#endif + + /* Calculate number of combinations (incrementing) */ + if (nextset > 0) + z = (z * i--) / k++; + + /* Cast number of combinations in set to integer */ + if ((ncombos = (uint64_t)z) == 0) + return (errno = ERANGE); + + /* Jump to next set if requested start is beyond this one */ + if (doseek) { + if (seek > ncombos) { + seek -= ncombos; + if (nextset < 0) + z = (z * --k) / ++i; + continue; + } else if (seek == 1) { + doseek = FALSE; + } + } + + /* Fill array with the initial positional arguments */ +#if CMB_DEBUG + if (debug) + fprintf(stderr, CMB_DEBUG_PREFIX "setnums=["); +#endif + for (n = 0; n < curset; n++) { +#if CMB_DEBUG + if (debug) { + if (n == curset - 1) + fprintf(stderr, "\033[31m%u\033[m", n); + else + fprintf(stderr, "%u", n); + if (n + 1 < curset) + fprintf(stderr, ","); + } +#endif + curitems[n] = items[n]; + } +#if CMB_DEBUG + if (debug) + fprintf(stderr, "] seq=%"PRIu64"\n", seq); +#endif + + /* Produce results with the first set of items */ + if (!doseek) { + retval = action(config, seq++, curset, curitems); + if (retval != 0) + break; + if (docount && --count == 0) + break; + } + + /* + * Prefill two arrays used for matrix calculations. + * + * The first array (setnums) is a linear sequence starting at + * one (1) and ending at N (where N is the same integer as the + * current set we're operating on). For example, if we are + * currently on a set-of-2, setnums is 1, 2. + * + * The second array (setnums_backend) is a linear sequence + * starting at 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. + */ + for (n = 0; n < curset; n++) + setnums[n] = n; + p = 0; + 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; +#if CMB_DEBUG + if (debug) { + fprintf(stderr, CMB_DEBUG_PREFIX "setnums=["); + for (n = 0; n < curset; n++) { + if (n == setnums_last) { + fprintf(stderr, + "\033[31m%u\033[m", + setnums[n]); + } else { + fprintf(stderr, "%u", + setnums[n]); + } + if (n + 1 < curset) + fprintf(stderr, ","); + } + fprintf(stderr, "] seq=%"PRIu64"\n", seq); + } +#endif + + /* Now map new setnums into values stored in items */ + for (n = 0; n < curset; n++) + curitems[n] = items[setnums[n]]; + + /* Produce results with this set of items */ + if (doseek) { + seek--; + if (seek == 1) + doseek = FALSE; + } + if (!doseek || seek == 1) { + doseek = FALSE; + retval = action(config, seq++, curset, + curitems); + if (retval != 0) + goto cmb_return; + if (docount && --count == 0) + goto cmb_return; + } + + } /* for combo */ + + /* Calculate number of combinations (decrementing) */ + if (nextset < 0) + z = (z * --k) / ++i; + + } /* for curset */ + + /* Show the empty set consisting of a single combination of no-items */ + if (nextset < 0 && show_empty) { + if ((!doseek || seek == 1) && (!docount || count > 0)) { + retval = action(config, seq++, 0, NULL); + } + } + +cmb_return: + free(curitems); + free(setnums); + free(setnums_backend); + + return (retval); +} + +CMB_ACTION(cmb_print) +{ + uint8_t nul = FALSE; + uint8_t show_numbers = FALSE; + uint32_t n; + const char *delimiter = " "; + const char *prefix = NULL; + const char *suffix = NULL; + + /* Process config options */ + if (config != NULL) { + if (config->delimiter != NULL) + delimiter = config->delimiter; + if ((config->options & CMB_OPT_NULPRINT) != 0) + nul = TRUE; + if ((config->options & CMB_OPT_NUMBERS) != 0) + show_numbers = TRUE; + prefix = config->prefix; + suffix = config->suffix; + } + + if (show_numbers) + printf("%"PRIu64" ", seq); + if (prefix != NULL) + printf("%s", prefix); + for (n = 0; n < nitems; n++) { + printf("%s", items[n]); + if (n < nitems - 1) + printf("%s", delimiter); + } + if (suffix != NULL) + printf("%s", suffix); + if (nul) + printf("%c", 0); + else + printf("\n"); + + return (0); +} + +#ifdef HAVE_OPENSSL_BN_H +/* + * Takes pointer to `struct cmb_config' options and number of items. Returns + * total number of combinations according to config options. Numbers formatted + * as openssl bn(3) BIGNUM type. + */ +BIGNUM * +cmb_count_bn(struct cmb_config *config, uint32_t 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) { + if ((config->options & CMB_OPT_EMPTY) != 0) + show_empty = TRUE; + if (config->size_min != 0 || config->size_max != 0) { + setinit = config->size_min; + setdone = config->size_max; + } + } + + /* Adjust values to be non-zero (mathematical constraint) */ + if (setinit == 0) + setinit = 1; + if (setdone == 0) + setdone = 1; + + /* Return NULL if the request is out of range */ + if (setinit > 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(), (int)nitems); + goto cmb_count_bn_return; + } else { + if (BN_lshift(count, BN_value_one(), (int)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 += (uint32_t)nextset) + { + /* Calculate number of combinations (incrementing) */ + if (nextset > 0) { + if (!BN_mul_word(ncombos, i--)) + break; + if (BN_div_word(ncombos, k++) == (BN_ULONG)-1) + break; + } + + /* Add number of combinations in this set to total */ + if (!BN_add(count, count, ncombos)) + break; + + /* Calculate number of combinations (decrementing) */ + if (nextset < 0) { + if (!BN_mul_word(ncombos, --k)) + break; + if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1) + break; + } + } + +cmb_count_bn_return: + BN_free(ncombos); + + return (count); +} + +/* + * Takes pointer to `struct cmb_config' options, number of items, and array + * of `char *' items. Calculates combinations according to options and either + * prints combinations to stdout (default) or runs `action_bn' if passed-in as + * function pointer member of `config' argument. Numbers formatted as openssl + * bn(3) BIGNUM type. + */ +int +cmb_bn(struct cmb_config *config, uint32_t nitems, char *items[]) +{ +#if CMB_DEBUG + uint8_t debug = FALSE; +#endif + uint8_t docount = FALSE; + uint8_t doseek = FALSE; + uint8_t show_empty = FALSE; + uint8_t show_numbers = FALSE; + int8_t nextset = 1; + int retval = 0; + uint32_t curset; + uint32_t i = 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; +#if CMB_DEBUG + char *seq_str; +#endif + uint32_t *setnums; + uint32_t *setnums_backend; + BIGNUM *combo = NULL; + BIGNUM *count = NULL; + BIGNUM *ncombos = NULL; + BIGNUM *seek = NULL; + BIGNUM *seq = NULL; + CMB_ACTION_BN((*action_bn)) = cmb_print_bn; + + /* Process config options */ + if (config != NULL) { + if (config->action_bn != NULL) + action_bn = config->action_bn; + if (config->count_bn != NULL && + !BN_is_negative(config->count_bn) && + !BN_is_zero(config->count_bn)) + { + docount = TRUE; + if ((count = BN_dup(config->count_bn)) == NULL) + goto cmb_bn_return; + } + if ((config->options & CMB_OPT_DEBUG) != 0) { +#if CMB_DEBUG + debug = TRUE; +#else + warnx("libcmb not compiled with debug support!"); +#endif + } + if ((config->options & CMB_OPT_EMPTY) != 0) + show_empty = TRUE; + if ((config->options & CMB_OPT_NUMBERS) != 0) + show_numbers = TRUE; + if (config->size_min != 0 || config->size_max != 0) { + setinit = config->size_min; + setdone = config->size_max; + } + if (config->start_bn != NULL && + !BN_is_negative(config->start_bn) && + !BN_is_zero(config->start_bn) && + !BN_is_one(config->start_bn)) + { + doseek = TRUE; + if ((seek = BN_dup(config->start_bn)) == NULL) + goto cmb_bn_return; +#if CMB_DEBUG + if (show_numbers || debug) { +#else + if (show_numbers) { +#endif + if ((seq = BN_dup(seek)) == NULL) + goto cmb_bn_return; + if (!BN_sub_word(seq, 1)) + goto cmb_bn_return; + } + } + } + + if (nitems == 0 && !show_empty) + goto cmb_bn_return; + + /* Adjust values to be non-zero (mathematical constraint) */ + if (setinit == 0) + setinit = 1; + if (setdone == 0) + setdone = 1; + + /* Enforce limits so we don't run over bounds */ + if (setinit > nitems) + setinit = nitems; + if (setdone > nitems) + setdone = nitems; + + /* Set the direction of flow (incrementing vs. decrementing) */ + if (setinit > setdone) + nextset = -1; + + /* Initialize sequence number */ + if (seq == NULL) { + if ((seq = BN_new()) == NULL) + goto cmb_bn_return; + if (!BN_zero(seq)) + goto cmb_bn_return; + } + + /* Show the empty set consisting of a single combination of no-items */ + if (nextset > 0 && show_empty) { +#if CMB_DEBUG + if (debug) + cmb_debug(">>> 0-item combinations <<<"); +#endif + if (!doseek) { + if (!BN_add_word(seq, 1)) + goto cmb_bn_return; + retval = action_bn(config, seq, 0, NULL); + if (retval != 0) + goto cmb_bn_return; + if (docount) { + if (!BN_sub_word(count, 1)) + goto cmb_bn_return; + if (BN_is_zero(count)) + goto cmb_bn_return; + } + } else { + if (!BN_sub_word(seek, 1)) + goto cmb_bn_return; + if (BN_is_one(seek)) + doseek = FALSE; + } + } + + if (nitems == 0) + goto cmb_bn_return; + + /* Allocate memory */ + if ((combo = BN_new()) == NULL) + goto cmb_bn_return; + if ((ncombos = BN_new()) == NULL) + goto cmb_bn_return; + if (!BN_one(ncombos)) + goto cmb_bn_return; + setmax = setdone > setinit ? setdone : setinit; + if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + if ((setnums_backend = + (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + + /* + * Loop over each `set' in the configured direction until we are done. + * NB: Each `set' can represent a single item or multiple items. + */ + p = nextset > 0 ? setinit - 1 : setinit; + for (k = 1; k <= p; k++) { + if (!BN_mul_word(ncombos, i--)) + goto cmb_bn_return; + if (BN_div_word(ncombos, k) == (BN_ULONG)-1) + goto cmb_bn_return; + } + for (curset = setinit; + nextset > 0 ? curset <= setdone : curset >= setdone; + curset += (uint32_t)nextset) + { +#if CMB_DEBUG + if (debug) + cmb_debug(">>> %u-item combinations <<<", curset); +#endif + + /* Calculate number of combinations (incrementing) */ + if (nextset > 0) { + if (!BN_mul_word(ncombos, i--)) + break; + if (BN_div_word(ncombos, k++) == (BN_ULONG)-1) + break; + } + + /* Jump to next set if requested start is beyond this one */ + if (doseek) { + if (BN_ucmp(seek, ncombos) > 0) { + if (!BN_sub(seek, seek, ncombos)) + break; + if (nextset < 0) { + if (!BN_mul_word(ncombos, --k)) + break; + if (BN_div_word(ncombos, ++i) == + (BN_ULONG)-1) + break; + } + continue; + } else if (BN_is_one(seek)) { + doseek = FALSE; + } + } + + /* Fill array with the initial positional arguments */ +#if CMB_DEBUG + if (debug) + fprintf(stderr, CMB_DEBUG_PREFIX "setnums=["); +#endif + for (n = 0; n < curset; n++) { +#if CMB_DEBUG + if (debug) { + if (n == curset - 1) + fprintf(stderr, "\033[31m%u\033[m", n); + else + fprintf(stderr, "%u", n); + if (n + 1 < curset) + fprintf(stderr, ","); + } +#endif + curitems[n] = items[n]; + } +#if CMB_DEBUG + if (debug) { + seq_str = BN_bn2dec(seq); + fprintf(stderr, "] seq=%s\n", seq_str); + OPENSSL_free(seq_str); + } +#endif + + /* Produce results with the first set of items */ + if (!doseek) { + if (!BN_add_word(seq, 1)) + goto cmb_bn_return; + retval = action_bn(config, seq, curset, curitems); + if (retval != 0) + break; + if (docount) { + if (!BN_sub_word(count, 1)) + break; + if (BN_is_zero(count)) + break; + } + } + + /* + * Prefill two arrays used for matrix calculations. + * + * The first array (setnums) is a linear sequence starting at + * one (1) and ending at N (where N is the same integer as the + * current set we're operating on). For example, if we are + * currently on a set-of-2, setnums is 1, 2. + * + * The second array (setnums_backend) is a linear sequence + * starting at 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; +#if CMB_DEBUG + if (debug) { + fprintf(stderr, CMB_DEBUG_PREFIX "setnums=["); + for (n = 0; n < curset; n++) { + if (n == setnums_last) { + fprintf(stderr, + "\033[31m%u\033[m", + setnums[n]); + } else { + fprintf(stderr, "%u", + setnums[n]); + } + if (n + 1 < curset) + fprintf(stderr, ","); + } + seq_str = BN_bn2dec(seq); + fprintf(stderr, "] seq=%s\n", seq_str); + OPENSSL_free(seq_str); + } +#endif + + /* Now map new setnums into values stored in items */ + for (n = 0; n < curset; n++) + curitems[n] = items[setnums[n]]; + + /* Produce results with this set of items */ + if (doseek) { + if (!BN_sub_word(seek, 1)) + goto cmb_bn_return; + if (BN_is_one(seek)) + doseek = FALSE; + } + if (!doseek || BN_is_one(seek)) { + doseek = FALSE; + if (!BN_add_word(seq, 1)) + goto cmb_bn_return; + retval = action_bn(config, seq, curset, + curitems); + if (retval != 0) + goto cmb_bn_return; + if (docount) { + if (!BN_sub_word(count, 1)) + goto cmb_bn_return; + if (BN_is_zero(count)) + goto cmb_bn_return; + } + } + + if (!BN_add_word(combo, 1)) + goto cmb_bn_return; + + } /* for combo */ + + /* Calculate number of combinations (decrementing) */ + if (nextset < 0) { + if (!BN_mul_word(ncombos, --k)) + break; + if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1) + break; + } + + } /* for curset */ + + /* Show the empty set consisting of a single combination of no-items */ + if (nextset < 0 && show_empty) { + if ((!doseek || BN_is_one(seek)) && + (!docount || !BN_is_zero(count))) { + if (!BN_add_word(seq, 1)) + goto cmb_bn_return; + retval = action_bn(config, seq, 0, NULL); + } + } + +cmb_bn_return: + BN_free(combo); + BN_free(count); + BN_free(ncombos); + BN_free(seek); + BN_free(seq); + + return (retval); +} + +CMB_ACTION_BN(cmb_print_bn) +{ + uint8_t nul = FALSE; + uint8_t show_numbers = FALSE; + uint32_t n; + char *seq_str; + const char *delimiter = " "; + const char *prefix = NULL; + const char *suffix = NULL; + + /* Process config options */ + if (config != NULL) { + if (config->delimiter != NULL) + delimiter = config->delimiter; + if ((config->options & CMB_OPT_NULPRINT) != 0) + nul = TRUE; + if ((config->options & CMB_OPT_NUMBERS) != 0) + show_numbers = TRUE; + prefix = config->prefix; + suffix = config->suffix; + } + + if (show_numbers) { + seq_str = BN_bn2dec(seq); + printf("%s ", seq_str); + OPENSSL_free(seq_str); + } + if (prefix != NULL) + printf("%s", prefix); + for (n = 0; n < nitems; n++) { + printf("%s", items[n]); + if (n < nitems - 1) + printf("%s", delimiter); + } + if (suffix != NULL) + printf("%s", suffix); + if (nul) + printf("%c", 0); + else + printf("\n"); + + return (0); +} +#endif /* HAVE_OPENSSL_BN_H */ Index: lib/libcmb/cmb_private.h =================================================================== --- /dev/null +++ lib/libcmb/cmb_private.h @@ -0,0 +1,60 @@ +/*- + * 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$ + */ + +#ifndef _CMB_PRIVTE_H_ +#define _CMB_PRIVTE_H_ + +/* Limits */ +#define BUFSIZE_MAX (2 * 1024 * 1024) + /* Buffer size for read(2) input */ +#ifndef MAXPHYS +#define MAXPHYS (128 * 1024) + /* max raw I/O transfer size */ +#endif + +/* + * Memory strategy threshold, in pages: if physmem is larger than this, + * use a large buffer. + */ +#define PHYSPAGES_THRESHOLD (32 * 1024) + +/* + * Small (default) buffer size in bytes. It's inefficient for this to be + * smaller than MAXPHYS. + */ +#define BUFSIZE_SMALL (MAXPHYS) + +/* + * Math macros + */ +#undef MIN +#define MIN(x,y) ((x) < (y) ? (x) : (y)) +#undef MAX +#define MAX(x,y) ((x) > (y) ? (x) : (y)) + +#endif /* !_CMB_PRIVTE_H_ */ Index: lib/libcmb/tests/Makefile =================================================================== --- /dev/null +++ lib/libcmb/tests/Makefile @@ -0,0 +1,11 @@ +# $FreeBSD$ + +.include + +PROGS= test1 test2 test3 test4 test5 + +MAN= + +LIBADD= cmb + +.include Index: lib/libcmb/tests/test1.c =================================================================== --- /dev/null +++ lib/libcmb/tests/test1.c @@ -0,0 +1,102 @@ +/*- + * Copyright (c) 2018-2019 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/tests/test1.c 2019-04-10 15:27:36 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include +#include +#include + +static int num_calls = 0; +static int +afunc(struct cmb_config *config, uint64_t seq, uint32_t nitems, char *items[]) +{ + num_calls++; + return (0); +} + +int +main(void) +{ + uint32_t nitems = 4; + int retval; + uint64_t seq = 1; + char *items[] = {"a", "b", "c", "d"}; + char itemstr[] = "a, b, c, d"; + static struct cmb_config config = { + .options = CMB_OPT_NUMBERS, + .delimiter = ",", + .prefix = "\t[", + .suffix = "]", + .size_min = 2, + .size_max = 3, + .count = 6, + .start = 4, + }; + + printf("config = {\n"); + printf("\t.options = 0x%08x,\n", config.options); + printf("\t.delimiter = \"%s\",\n", config.delimiter); + printf("\t.prefix = \"%s\",\n", config.prefix); + printf("\t.suffix = \"%s\",\n", config.suffix); + printf("\t.size_min = %u,\n", config.size_min); + printf("\t.size_max = %u,\n", config.size_max); + printf("\t.count = %"PRIu64",\n", config.count); + printf("\t.start = %"PRIu64",\n", config.start); + printf("}\n"); + + printf("cmb_version(%u): %s\n", CMB_VERSION, cmb_version(CMB_VERSION)); + printf("cmb_version(%u): %s\n", CMB_VERSION_LONG, + cmb_version(CMB_VERSION_LONG)); + printf("size_min=%u size_max=%u\n", config.size_min, config.size_max); + printf("cmb_count(config, %u) = %"PRIu64"\n", nitems, + cmb_count(&config, nitems)); + printf("cmb_print(config, %"PRIu64", %u, [%s]):\n", seq, nitems, + itemstr); + retval = cmb_print(&config, seq, nitems, items); + printf("\tRESULT: %i\n", retval); + printf("cmb(config, %u, [%s]):\n", nitems, itemstr); + printf("NOTE: { .start = %"PRIu64", .count = %"PRIu64" }\n", + config.start, config.count); + retval = cmb(&config, nitems, items); + printf("\tRESULT: %i\n", retval); + + /* + * Callbacks + */ + config.options = 0; + config.action = afunc; + printf("cmb_callback(config, %u, [%s], afunc):\n", nitems, itemstr); + retval = cmb(&config, nitems, items); + printf("\tnum_calls: %i\n", num_calls); + printf("\tRESULT: %i\n", retval); + + return (EXIT_SUCCESS); +} Index: lib/libcmb/tests/test2.c =================================================================== --- /dev/null +++ lib/libcmb/tests/test2.c @@ -0,0 +1,62 @@ +/*- + * Copyright (c) 2018-2019 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/tests/test2.c 2019-01-05 21:22:28 -0800 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include +#include + +#define CHOICE 2 +#define NITEMS 10000 + +static int total = 0; + +static int +afunc(struct cmb_config *config, uint64_t seq, uint32_t nitems, char *items[]) +{ + total++; + return (0); +} + +int +main(void) +{ + static struct cmb_config config = { + .size_min = CHOICE, + .size_max = CHOICE, + .action = afunc, + }; + char *items[NITEMS]; + + printf("Silently enumerating choose-%u from %u:\n", CHOICE, NITEMS); + (void)cmb(&config, NITEMS, items); + + return (EXIT_SUCCESS); +} Index: lib/libcmb/tests/test3.c =================================================================== --- /dev/null +++ lib/libcmb/tests/test3.c @@ -0,0 +1,64 @@ +/*- + * Copyright (c) 2018-2019 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/tests/test3.c 2019-01-05 21:35:36 -0800 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include +#include + +static int +afunc(struct cmb_config *config, uint64_t seq, uint32_t nitems, char *items[]) +{ + int i; + + printf("\t"); + for (i = 0; i < nitems; i++) + printf("%s%s", items[i], i < (nitems - 1) ? " " : ""); + printf("\n"); + + return (0); +} + +int +main(void) +{ + int nitems = 4; + char *items[] = {"a", "b", "c", "d"}; + static struct cmb_config config = { + .size_min = 2, + .size_max = 2, + .action = afunc, + }; + + printf("Enumerating choose-2 from %u:\n", nitems); + (void)cmb(&config, nitems, items); + + return (EXIT_SUCCESS); +} Index: lib/libcmb/tests/test4.c =================================================================== --- /dev/null +++ lib/libcmb/tests/test4.c @@ -0,0 +1,102 @@ +/*- + * Copyright (c) 2018-2019 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/tests/test4.c 2019-01-19 17:52:40 -0800 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#define CHOICE 2 +#define NITEMS 10000 + +static int dpv[2] = { 0, 0 }; + +static int +afunc(struct cmb_config *config, uint64_t seq, uint32_t nitems, char *items[]) +{ + uint32_t i; + + for (i = 0; i < nitems; i++) + printf("%s%s", items[i], i < (nitems - 1) ? " " : ""); + printf("\n"); + + return (0); +} + +int +main(void) +{ + uint32_t i; + pid_t pid; + int status; + static struct cmb_config config = { + .size_min = CHOICE, + .size_max = CHOICE, + .action = afunc, + }; + char *items[NITEMS]; + char count_arg[23]; + + pipe(dpv); + + if ((pid = fork()) == 0) { /* child */ + dup2(dpv[0], STDIN_FILENO); + close(dpv[0]); + close(dpv[1]); + sprintf(count_arg, "%"PRIu64":c", cmb_count(&config, NITEMS)); + execlp("dpv", "dpv", "-l", count_arg, NULL); + err(EXIT_FAILURE, "dpv"); + /* NOTREACHED */ + } + /* parent */ + + dup2(dpv[1], STDOUT_FILENO); + close(dpv[0]); + close(dpv[1]); + + for (i = 0; i < NITEMS; i++) { + items[i] = (char *)calloc(1, 11); + sprintf(items[i], "%u", i); + } + (void)cmb(&config, NITEMS, items); + + fflush(stdout); + close(STDOUT_FILENO); + waitpid(pid, &status, 0); + + return (EXIT_SUCCESS); +} Index: lib/libcmb/tests/test5.c =================================================================== --- /dev/null +++ lib/libcmb/tests/test5.c @@ -0,0 +1,60 @@ +/*- + * Copyright (c) 2018-2019 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/tests/test5.c 2019-01-19 16:48:37 -0800 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include +#include +#include + +static int total = 0; + +static int +afunc(struct cmb_config *config, uint64_t seq, uint32_t nitems, char *items[]) +{ + return (total++); +} + +int +main(void) +{ + static struct cmb_config config = { + .action = afunc, + }; + int nitems = 3; + char *items[] = {"a", "b", "c"}; + + printf("Testing non-zero callback return:\n"); + (void)cmb(&config, nitems, items); + printf("%u of %"PRIu64" callbacks executed\n", + total, cmb_count(&config, nitems)); + + return (EXIT_SUCCESS); +} Index: share/mk/src.libnames.mk =================================================================== --- share/mk/src.libnames.mk +++ share/mk/src.libnames.mk @@ -84,6 +84,7 @@ cap_pwd \ cap_sysctl \ cap_syslog \ + cmb \ com_err \ compiler_rt \ crypt \ @@ -362,6 +363,9 @@ _DP_zfs_core= nvpair _DP_zpool= md pthread z nvpair avl umem _DP_be= zfs nvpair +.if ${MK_OPENSSL} != "no" +_DP_cmb= m crypto +.endif # OFED support .if ${MK_OFED} != "no" @@ -529,6 +533,9 @@ LIBBE?= ${LIBBEDIR}/libbe${PIE_SUFFIX}.a +LIBCMBDIR= ${_LIB_OBJTOP}/lib/libcmb +LIBCMB?= ${LIBCMBDIR}/libcmb.a + LIBPMCSTATDIR= ${_LIB_OBJTOP}/lib/libpmcstat LIBPMCSTAT?= ${LIBPMCSTATDIR}/libpmcstat${PIE_SUFFIX}.a Index: usr.bin/Makefile =================================================================== --- usr.bin/Makefile +++ usr.bin/Makefile @@ -18,6 +18,7 @@ chat \ chpass \ cksum \ + cmb \ cmp \ col \ colrm \ 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,395 @@ +.\" Copyright (c) 2018-2019 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 2019-08-23 20:37:14 -0700 freebsdfrau $ +.\" $FreeBSD$ +.\" +.Dd August 23, 2019 +.Dt CMB 1 +.Os +.Sh NAME +.Nm cmb +.Nd combinatorics utility +.Sh SYNOPSIS +.Nm +.Op Fl 0DefNorStvz +.Op Fl c Ar num +.Op Fl d Ar str +.Op Fl F Ar num +.Op Fl i Ar num +.Op Fl k Ar size +.Op Fl n Ar num +.Op Fl P Ar num +.Op Fl p Ar str +.Op Fl s Ar str +.Op Fl X Ar op +.Op Ar item Ar ... +.Sh DESCRIPTION +The +.Nm +utility prints combinations, +one per line +.Pq default , +with items in each combination separated by space +.Pq default . +Given N items on the command-line, +there are N sets where each set consists of an increasing number of items +.Pq default . +By default, +all sets are produced +.Pq Ql Li -k 0 . +Combination order within a set of N-items is always consistent and repeatable +given the order of items on the command-line. +The order of combinations within a single set of N-items +.Pq where every combination in the set has the same number of items +is dependent upon the order of items on the command-line. +.Pp +Available options: +.Bl -tag -width ".Fl r Ar range" +.It Fl 0 +Change the behavior of +.Ql Fl f +to read items separated by NUL character +.Pq character code 0 +instead of newline. +.It Fl c Ar num +Produce at-most +.Ar num +combinations. +If +.Ql 0 +.Pq default +all combinations produced. +Ignored when given +.Ql Fl t . +.It Fl D +Enable debugging information on stderr. +See +.Xr cmb 3 . +.It Fl d Ar text +Delimiter for separating items. +Default is space +.Pq Dq " " . +Ignored when given +.Ql Fl t . +.It Fl e +Show empty set. +A single combination containing no-items. +.It Fl F Ar num +Find +.Sq Fl X Ar op +values that equal +.Ar num . +Requires +.Sq Fl X Ar op . +.It Fl f +Treat each command-line argument as a file containing items, +one item per line +.Pq default . +With +.Ql Fl 0 , +read items separated by NUL character. +If an argument is +.Ql Li - , +read from stdin. +The sum of items read from all files cannot exceed 4294967295. +.It Fl i Ar num +Skip the first +.Va num-1 +combinations. +If +.Va num +is negative, +skip to +.Va |num| +combinations before the end. +If +.Va num +matches +.Ql Li random +.Pq case-sensitive +a random number between 1 and the total number of combinations is chosen. +Ignored when given +.Ql Fl t . +.It Fl k Ar size +Number or range +.Pq Qo min..max Qc or Qo min-max Qc +of how many items must appear in each combination. +A value of +.Ql 0 +.Pq default +calculates all sets starting with 1-item combinations. +If +.Va size +is negative one +.Pq Li -1 , +calculate sets in descending order, +starting with the maximum number of items. +A range of +.Ql Li -1..N +will do the same but stop at N-item combinations. +A range of +.Ql Li N..-1 +will start with N-item combinations and end with the maximum number of items. +The order of combinations in each set is unaffected by negative +.Va size +values. +A range of +.Ql Li -1..-1 +calculates the ending set consisting of only the maximum number of items. +.It Fl N +Show combination sequence numbers. +Combinations are calculated in arithmetic progression, +providing predictable order. +The sequence number can be used as a value to +.Ql Fl i Ar num +to start at that combination. +Ignored when given +.Ql Fl t . +.It Fl n Ar num +Limit the number of arguments taken from the command-line. +No effect if +.Va num +is greater than the number of arguments. +.It Fl o +Disable OpenSSL +.Xr bn 3 +support +.Pq limits calculations to 64-bits . +No effect if unsupported. +Use +.Ql Fl v +to check OpenSSL support. +The default is to use OpenSSL when supported. +Must appear before +.Ql Fl c Ar num +and +.Ql Fl i Ar num +options. +.It Fl P Ar num +Change the behavior of +.Ql Fl X Ar op +to use +.Ar num +units of precision when printing floating point results. +Default behavior of +.Ql Fl X Ar op +is to use the highest precision of provided arguments. +Ignored when given +.Ql Fl t . +.It Fl p Ar text +Prefix each combination with +.Ar text . +Ignored when given +.Ql Fl t . +.It Fl q +Quiet. +Do not print items from set when given +.Ql Fl X Ar op . +.It Fl r +Treat each command-line argument as a number or range to be expanded. +If a single number, +expand to numbers 1 to num. +If a range +.Pq Qo min..max Qc or Qo min-max Qc , +expand to numbers min to max. +Numbers must be whole positive integers between 0 and 4294967295. +.It Fl S +Silent. +Do not print combinations to stdout. +Used with +.Xr time 1 +to determine +.Xr stdio 3 +overhead. +With +.Ql Fl t , +do not print result. +.It Fl s Ar text +Suffix each combination with +.Ar text . +Ignored when given +.Ql Fl t . +.It Fl t +Print total number of combinations and exit. +.It Fl v +Print version information to stdout and exit. +Includes +.Xr cmb 3 +library version and +.Pq if-enabled +.Xr SSL 3 +library version. +.It Fl X Ar op +Perform math on items where +.Ar op +is +.Ql Li add , +.Ql Li subtract , +.Ql Li divide , +or +.Ql Li multiply +.Pq case-sensitive . +Argument +.Ar op +can be shortened to its minimally distinct representation; +such as +.Ql Li a +for +.Ql Li add . +Ignored when given +.Ql Fl t . +.It Fl z +Print combinations followed by ASCII NUL character +.Pq character code 0 +instead of newline +.Pq character code 10 . +With +.Ql Fl t , +do not print a trailing character after the result. +.El +.Sh EXAMPLES +Print all two-word combinations +.Pq Qo bird dog Qc , Qo bird house Qc , and Qo dog house Qc +given +.Qq bird , +.Qq dog , +and +.Qq house : +.Bd -literal -offset indent +cmb -k 2 bird dog house +.Ed +.Pp +Print number of combinations +.Pq 7 +given +.Qq a , +.Qq b , +and +.Qq c : +.Bd -literal -offset indent +cmb -t a b c +.Ed +.Pp +Print first 5 combinations +.Pq Qo x Qc , Qo y Qc , Qo z Qc , Qo x y Qc , and Qo x z Qc +given +.Qq x , +.Qq y , +and +.Qq z : +.Bd -literal -offset indent +cmb -c 5 x y z +.Ed +.Pp +Skip first 3 combinations +.Pq Qo x Qc , Qo y Qc , and Qo z Qc +given +.Qq x , +.Qq y , +and +.Qq z : +.Bd -literal -offset indent +cmb -i 4 x y z +.Ed +.Pp +Print last 5 combinations +.Pq Qo z Qc , Qo x y Qc , Qo x z Qc , Qo y z Qc , and Qo x y z Qc +given +.Qq x , +.Qq y , +and +.Qq z : +.Bd -literal -offset indent +cmb -i -5 x y z +.Ed +.Pp +Print items separated by comma instead of space: +.Bd -literal -offset indent +cmb -d , a b c +.Ed +.Pp +Print numbers as JSON: +.Bd -literal -offset indent +cmb -p '{"values":[' -s ']}' -d , 1 2 3 +.Ed +.Pp +Print strings as JSON: +.Bd -literal -offset indent +cmb -p '{"values":[' -s ']}' -d , '"a"' '"b"' '"c"' +.Ed +.Pp +Print all 2- and 3-word combinations +.Po +.Qq big blue , +.Qq big red , +.Qq big couch , +.Qq blue red , +.Qq blue couch , +.Qq red couch , +.Qq big blue red , +.Qq big blue couch , +.Qq big red couch , +and +.Qq blue red couch +.Pc +given +.Qq big , +.Qq blue , +.Qq red , +and +.Qq couch : +.Bd -literal -offset indent +cmb -k 2..3 big blue red couch +.Ed +.Pp +Print combinations starting with the maximum number of items +.Pq 3 , +ending with 2-item combinations: +.Bd -literal -offset indent +cmb -k -1..2 1 2 3 +.Ed +.Pp +Print combinations starting with 2-items ending with maximum items +.Pq 3 : +.Bd -literal -offset indent +cmb -k 2..-1 x y z +.Ed +.Pp +Roll a set of 2 six-sided dice, +producing a single random combination of two numbers: +.Bd -literal -offset indent +cmb -c 1 -k 2 -i rand -r 6 6 +.Ed +.Pp +Find all combinations of numbers 1, 2, and 3 that produce the sum of 4: +.Bd -literal -offset indent +cmb -X add -F 4 -r 3 +.Ed +.Sh HISTORY +The +.Nm +utility first appeared in +.Fx 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,1200 @@ +/*- + * Copyright (c) 2018-2019 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 2019-08-23 20:37:14 -0700 freebsdfrau $"); +__FBSDID("$FreeBSD$"); +#endif + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#ifndef UINT_MAX +#define UINT_MAX 0xFFFFFFFF +#endif + +static char version[] = "$Version: 3.9.5 $"; + +/* Environment */ +static char *pgm; /* set to argv[0] by main() */ + +/* Globals */ +static uint8_t opt_quiet = FALSE; +static uint8_t opt_silent = FALSE; +static const char digit[11] = "0123456789"; + +#ifndef _Noreturn +#define _Noreturn __attribute__((noreturn)) +#endif + +/* Function prototypes */ +static void _Noreturn cmb_usage(void); +static uint64_t cmb_rand_range(uint64_t range); +static CMB_ACTION(cmb_add); +static CMB_ACTION(cmb_div); +static CMB_ACTION(cmb_mul); +static CMB_ACTION(cmb_nop); +static CMB_ACTION(cmb_sub); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +static CMB_ACTION_BN(cmb_add_bn); +static CMB_ACTION_BN(cmb_div_bn); +static CMB_ACTION_BN(cmb_mul_bn); +static CMB_ACTION_BN(cmb_nop_bn); +static CMB_ACTION_BN(cmb_sub_bn); +#endif +static CMB_ACTION(cmb_add_find); +static CMB_ACTION(cmb_div_find); +static CMB_ACTION(cmb_mul_find); +static CMB_ACTION(cmb_sub_find); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +static CMB_ACTION_BN(cmb_add_find_bn); +static CMB_ACTION_BN(cmb_div_find_bn); +static CMB_ACTION_BN(cmb_mul_find_bn); +static CMB_ACTION_BN(cmb_sub_find_bn); +#endif +static size_t numlen(const char *s); +static size_t rangelen(const char *s, size_t nlen, size_t slen); +static size_t unumlen(const char *s); +static size_t urangelen(const char *s, size_t nlen, size_t slen); +static uint8_t parse_range(const char *s, uint32_t *min, uint32_t *max); +static uint8_t parse_unum(const char *s, uint32_t *n); +static uint8_t parse_urange(const char *s, uint32_t *min, uint32_t *max); +static uint32_t range_char(uint32_t start, uint32_t stop, uint32_t idx, + char *dst[]); +static uint32_t range_float(uint32_t start, uint32_t stop, uint32_t idx, + char *dst[]); + +/* Inline functions */ +static inline uint8_t p2(uint64_t x) { return (x == (x & -x)); } +static inline uint64_t urand64(void) { return (((uint64_t)lrand48() << 42) + + ((uint64_t)lrand48() << 21) + (uint64_t)lrand48()); +} + +/* + * Transformations (-X op) + */ +struct cmb_xfdef +{ + const char *opname; + CMB_ACTION((*action)); + CMB_ACTION((*action_find)); +}; +static struct cmb_xfdef cmb_xforms[] = { + /* opname action */ + {"multiply", cmb_mul, cmb_mul_find}, + {"divide", cmb_div, cmb_div_find}, + {"add", cmb_add, cmb_add_find}, + {"subtract", cmb_sub, cmb_sub_find}, + {NULL, NULL, NULL}, +}; +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +struct cmb_xfdef_bn +{ + const char *opname; + CMB_ACTION_BN((*action_bn)); + CMB_ACTION_BN((*action_find_bn)); +}; +static struct cmb_xfdef_bn cmb_xforms_bn[] = { + /* opname action_bn */ + {"multiply", cmb_mul_bn, cmb_mul_find_bn}, + {"divide", cmb_div_bn, cmb_div_find_bn}, + {"add", cmb_add_bn, cmb_add_find_bn}, + {"subtract", cmb_sub_bn, cmb_sub_find_bn}, + {NULL, NULL, NULL}, +}; +#endif + +int +main(int argc, char *argv[]) +{ + uint8_t free_find = FALSE; + uint8_t opt_empty = FALSE; + uint8_t opt_file = FALSE; + uint8_t opt_find = FALSE; +#ifdef HAVE_LIBCRYPTO + uint8_t opt_nossl = FALSE; +#endif + uint8_t opt_nulparse = FALSE; + uint8_t opt_nulprint = FALSE; + uint8_t opt_precision = FALSE; + uint8_t opt_randi = FALSE; + uint8_t opt_range = FALSE; + uint8_t opt_total = FALSE; + uint8_t opt_version = FALSE; + const char *cp; + char *cmdver = version; + char *endptr = NULL; + char **items = NULL; + char **items_tmp = NULL; + const char *libver = cmb_version(CMB_VERSION); + char *opt_transform = NULL; + int ch; + int len; + int retval = EXIT_SUCCESS; + uint32_t i; + uint32_t n; + uint32_t nitems = 0; + uint32_t rstart = 0; + uint32_t rstop = 0; + size_t config_size = sizeof(struct cmb_config); + size_t cp_size = sizeof(char *); + size_t optlen; + struct cmb_config *config = NULL; + struct cmb_xitem *xitem = NULL; +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + BIGNUM *count_bn; +#endif + uint64_t count; + uint64_t fitems = 0; + uint64_t nstart = 0; /* negative start */ + uint64_t ritems = 0; + uint64_t ull; + unsigned long ul; + struct timeval tv; + + pgm = argv[0]; /* store a copy of invocation name */ + + /* Allocate config structure */ + if ((config = malloc(config_size)) == NULL) + errx(EXIT_FAILURE, "Out of memory?!"); + bzero(config, sizeof(struct cmb_config)); + + /* + * Process command-line options + */ +#define OPTSTRING "0c:Dd:eF:fi:k:Nn:oP:p:qrSs:tvX:z" + while ((ch = getopt(argc, argv, OPTSTRING)) != -1) { + switch(ch) { + case '0': /* NUL terminate */ + config->options ^= CMB_OPT_NULPARSE; + opt_nulparse = TRUE; + break; + case 'c': /* count */ + if ((optlen = strlen(optarg)) == 0 || + unumlen(optarg) != optlen) { + errx(EXIT_FAILURE, "-c: %s `%s'", + strerror(EINVAL), optarg); + /* NOTREACHED */ + } +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (!opt_nossl && + BN_dec2bn(&(config->count_bn), optarg) == 0) + errx(EXIT_FAILURE, "OpenSSL Error?!"); + if (opt_nossl) { +#endif + errno = 0; + config->count = strtoull(optarg, + (char **)NULL, 10); + if (errno != 0) { + errx(EXIT_FAILURE, "-c: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + } +#endif + break; + case 'D': /* debug */ + config->options ^= CMB_OPT_DEBUG; + break; + case 'd': /* delimiter */ + config->delimiter = optarg; + break; + case 'e': /* empty */ + opt_empty = TRUE; + config->options ^= CMB_OPT_EMPTY; + break; + case 'F': /* find */ + opt_find = TRUE; + if (cmb_transform_find != NULL) + free(cmb_transform_find); + if ((cmb_transform_find = + malloc(sizeof(struct cmb_xitem))) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + cmb_transform_find->cp = optarg; + endptr = NULL; + errno = 0; + cmb_transform_find->as.ld = strtold(optarg, &endptr); + if (endptr == NULL || *endptr != '\0') { + if (errno == 0) + errno = EINVAL; + errx(EXIT_FAILURE, "-F: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } + break; + case 'f': /* file */ + opt_file = TRUE; + opt_range = FALSE; + break; + case 'i': /* start */ + if ((optlen = strlen(optarg)) > 0 && + strncmp("random", optarg, optlen) == 0) { + opt_randi = TRUE; + } else if (optlen == 0 || numlen(optarg) != optlen) { + errx(EXIT_FAILURE, "-i: %s `%s'", + strerror(EINVAL), optarg); + /* NOTREACHED */ + } +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (!opt_randi && !opt_nossl && + BN_dec2bn(&(config->start_bn), optarg) == 0) + errx(EXIT_FAILURE, "OpenSSL Error?!"); + if (!opt_randi && opt_nossl) { +#else + if (!opt_randi) { +#endif + errno = 0; + if (*optarg == '-') { + nstart = strtoull(&optarg[1], + (char **)NULL, 10); + } else { + config->start = strtoull(optarg, + (char **)NULL, 10); + } + if (errno != 0) { + errx(EXIT_FAILURE, "-i: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } + } + break; + case 'k': /* size */ + if (!parse_range(optarg, &(config->size_min), + &(config->size_max))) { + errx(EXIT_FAILURE, "-k: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } + break; + case 'N': /* numbers */ + config->options ^= CMB_OPT_NUMBERS; + break; + case 'n': /* n-args */ + if (!parse_unum(optarg, &nitems)) { + errx(EXIT_FAILURE, "-n: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } + break; + case 'o': /* disable openssl */ +#ifdef HAVE_LIBCRYPTO + opt_nossl = TRUE; +#endif + break; + case 'P': /* precision */ + if (!parse_unum(optarg, + (uint32_t *)&cmb_transform_precision)) { + errx(EXIT_FAILURE, "-n: %s `%s'", + strerror(errno), optarg); + /* NOTREACHED */ + } + opt_precision = TRUE; + break; + case 'p': /* prefix */ + config->prefix = optarg; + break; + case 'q': /* quiet */ + opt_quiet = 1; + break; + case 'r': /* range */ + opt_range = TRUE; + opt_file = FALSE; + break; + case 'S': /* silent */ + opt_silent = TRUE; + break; + case 's': /* suffix */ + config->suffix = optarg; + break; + case 't': /* total */ + opt_total = TRUE; + break; + case 'v': /* version */ + opt_version = TRUE; + break; + case 'X': /* transform */ + opt_transform = optarg; + break; + case 'z': /* zero */ + opt_nulprint = TRUE; + config->options ^= CMB_OPT_NULPRINT; + break; + default: /* unhandled argument (based on switch) */ + cmb_usage(); + /* NOTREACHED */ + } + } + argc -= optind; + argv += optind; + + /* + * Process `-v' command-line option + */ + if (opt_version) { + cmdver += 10; /* Seek past "$Version: " */ + cmdver[strlen(cmdver)-2] = '\0'; /* Place NUL before "$" */ +#ifdef HAVE_OPENSSL_CRYPTO_H + printf("%s: %s (%s; %s)", pgm, cmdver, libver, + SSLeay_version(SSLEAY_VERSION)); +#else + printf("%s: %s (%s)", pgm, cmdver, libver); +#endif + if (cmb_build_info.debug) + printf(" [debug]"); + printf("\n"); + exit(EXIT_SUCCESS); + } + + /* + * At least one non-option argument is required unless `-e' is given + */ + if (argc == 0 && !opt_empty) { + warnx("argument required unless `-e'"); + cmb_usage(); + /* NOTREACHED */ + } + + /* + * `-X op' required if given `-F num' + */ + if (opt_find && opt_transform == NULL) { + errx(EXIT_FAILURE, "`-X op' required when using `-F num'"); + /* NOTREACHED */ + } + + /* + * `-X op' required if given `-P num' + */ + if (opt_precision && opt_transform == NULL) { + errx(EXIT_FAILURE, "`-X op' required when using `-P num'"); + /* NOTREACHED */ + } + + /* + * `-f' required if given `-0' + */ + if (opt_nulparse && !opt_file) { + errx(EXIT_FAILURE, "`-f' required when using `-0'"); + /* NOTREACHED */ + } + + /* + * Calculate number of items + */ + if (nitems == 0 || nitems > (uint32_t)argc) + nitems = (uint32_t)argc; + if (opt_range) { + for (n = 0; n < nitems; n++) { + if (!parse_urange(argv[n], &rstart, &rstop)) { + errx(EXIT_FAILURE, "-r: %s `%s'", + strerror(errno), argv[n]); + /* NOTREACHED */ + } + if (unumlen(argv[n]) == strlen(argv[n])) { + rstop = rstart; + rstart = 1; + } + if (rstart < rstop) + ull = rstop - rstart + 1; + else + ull = rstart - rstop + 1; + if (ritems + ull > UINT_MAX) { + errx(EXIT_FAILURE, "-r: Too many items"); + /* NOTREACHED */ + } + ritems += ull; + } + } + + /* + * Print total for num items and exit if given `-t -r' + */ + if (opt_total && opt_range) { +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (!opt_nossl) { + char *count_str; + + count_bn = cmb_count_bn(config, (uint32_t)ritems); + if (opt_silent) + exit(EXIT_SUCCESS); + if (count_bn != NULL) { + count_str = BN_bn2dec(count_bn); + printf("%s%s", count_str, + opt_nulprint ? "" : "\n"); + OPENSSL_free(count_str); + BN_free(count_bn); + } else + printf("0%s", opt_nulprint ? "" : "\n"); + } else { +#endif + count = cmb_count(config, (uint32_t)ritems); + if (opt_silent) + exit(EXIT_SUCCESS); + if (errno) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + printf("%"PRIu64"%s", count, opt_nulprint ? "" : "\n"); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + } +#endif + exit(EXIT_SUCCESS); + } + + /* + * Read arguments ... + */ + if (opt_file) { + /* ... as a series of files if given `-f' */ + for (n = 0; n < nitems; n++) { + items_tmp = cmb_parse_file(config, argv[n], &i, 0); + if (items_tmp == NULL && errno != 0) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + if (fitems + i > UINT_MAX) { + errx(EXIT_FAILURE, "-f: Too many items"); + /* NOTREACHED */ + } + fitems += (uint64_t)i; + items = realloc(items, (size_t)(fitems * cp_size)); + if (items == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + (void)memcpy(&items[fitems-i], items_tmp, i * cp_size); + } + nitems = (uint32_t)fitems; + } else if (opt_range) { + /* ... as a series of ranges if given `-r' */ + if ((items = calloc(ritems, sizeof(char *))) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + i = 0; + for (n = 0; n < nitems; n++) { + parse_urange(argv[n], &rstart, &rstop); + if (unumlen(argv[n]) == strlen(argv[n])) { + rstop = rstart; + rstart = 1; + } + if (opt_transform != NULL) + i = range_float(rstart, rstop, i, items); + else + i = range_char(rstart, rstop, i, items); + } + nitems = (uint32_t)ritems; + } else { + /* ... as a series of strings or numbers if given `-X op' */ + items = argv; + } + + /* + * Time-based benchmarking (-S for silent) and transforms (-X op). + * + * NB: For benchmarking, the call-stack is still incremented into the + * action, while using a nop function allows us to benchmark + * various action overhead. + */ + if (opt_silent && opt_transform == NULL) { +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (opt_nossl) + config->action = cmb_nop; + else + config->action_bn = cmb_nop_bn; +#else + config->action = cmb_nop; +#endif + config->options &= ~CMB_OPT_NUMBERS; + } else if (opt_transform != NULL) { + if ((optlen = strlen(opt_transform)) == 0) { + errx(EXIT_FAILURE, "-X: %s `'", strerror(EINVAL)); + /* NOTREACHED */ + } + ch = -1; +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (opt_nossl) { + while ((cp = cmb_xforms[++ch].opname) != NULL) { + if (strncmp(cp, opt_transform, optlen) != 0) + continue; + if (opt_find) + config->action = + cmb_xforms[ch].action_find; + else + config->action = cmb_xforms[ch].action; + break; + } + } else { + while ((cp = cmb_xforms_bn[++ch].opname) != NULL) { + if (strncmp(cp, opt_transform, optlen) != 0) + continue; + if (opt_find) + config->action_bn = + cmb_xforms_bn[ch].action_find_bn; + else + config->action_bn = + cmb_xforms_bn[ch].action_bn; + break; + } + } + if (config->action == NULL && config->action_bn == NULL) { + errx(EXIT_FAILURE, "-X: %s `%s'", strerror(EINVAL), + opt_transform); + /* NOTREACHED */ + } +#else + while ((cp = cmb_xforms[++ch].opname) != NULL) { + if (strncmp(cp, opt_transform, optlen) != 0) + continue; + if (opt_find) + config->action = cmb_xforms[ch].action_find; + else + config->action = cmb_xforms[ch].action; + break; + } + if (config->action == NULL) { + errx(EXIT_FAILURE, "-X: %s `%s'", strerror(EINVAL), + opt_transform); + /* NOTREACHED */ + } +#endif + + /* + * Convert items into array of struct pointers + * NB: Transformation function does not perform conversions + */ + if (!opt_range) { + ul = sizeof(struct cmb_xitem *); + if ((items_tmp = calloc(nitems, ul)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + for (n = 0; n < nitems; n++) { + if ((xitem = malloc(sizeof(struct cmb_xitem))) + == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + xitem->cp = items[n]; + endptr = NULL; + errno = 0; + xitem->as.ld = strtold(items[n], &endptr); + if (endptr == NULL || *endptr != '\0') { + if (errno == 0) + errno = EINVAL; + errx(EXIT_FAILURE, "-X: %s `%s'", + strerror(errno), items[n]); + /* NOTREACHED */ + } + items_tmp[n] = (char *)xitem; + if (opt_precision) + continue; + if ((cp = strchr(items[n], '.')) != NULL) { + len = (int)strlen(items[n]); + len -= cp - items[n] + 1; + if (len > cmb_transform_precision) + cmb_transform_precision = len; + } + } + items = items_tmp; + } + } + + /* + * Adjust precision based on `-F num' + */ + if (opt_find) { + if ((cp = strchr(cmb_transform_find->cp, '.')) != NULL) { + len = (int)strlen(cmb_transform_find->cp); + len -= cp - cmb_transform_find->cp + 1; + if (len > cmb_transform_precision) { + cmb_transform_precision = len; + } else { + len = snprintf(NULL, 0, "%.*Lf", + cmb_transform_precision, + cmb_transform_find->as.ld) + 1; + cmb_transform_find->cp = + malloc((unsigned long)len); + if (cmb_transform_find->cp == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + free_find = TRUE; + (void)sprintf(cmb_transform_find->cp, "%.*Lf", + cmb_transform_precision, + cmb_transform_find->as.ld); + } + } else if (cmb_transform_precision > 0) { + len = snprintf(NULL, 0, "%.*Lf", + cmb_transform_precision, + cmb_transform_find->as.ld); + cmb_transform_find->cp = malloc((unsigned long)len); + if (cmb_transform_find->cp == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + free_find = TRUE; + (void)sprintf(cmb_transform_find->cp, + "%.*Lf", cmb_transform_precision, + cmb_transform_find->as.ld); + } + } + + /* + * Calculate combinations + */ + if (opt_total) { +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + if (!opt_nossl) { + char *count_str; + + count_bn = cmb_count_bn(config, nitems); + if (opt_silent) + exit(EXIT_SUCCESS); + if (count_bn != NULL) { + count_str = BN_bn2dec(count_bn); + printf("%s%s", count_str, + opt_nulprint ? "" : "\n"); + OPENSSL_free(count_str); + BN_free(count_bn); + } else + printf("0%s", opt_nulprint ? "" : "\n"); + } else { +#endif + count = cmb_count(config, nitems); + if (opt_silent) + exit(EXIT_SUCCESS); + if (errno) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + printf("%"PRIu64"%s", count, opt_nulprint ? "" : "\n"); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) + } + } else if (!opt_nossl) { + if (opt_randi) { + if ((count_bn = + cmb_count_bn(config, nitems)) != NULL) { + if (config->start_bn == NULL) + config->start_bn = BN_new(); + if (BN_rand_range(config->start_bn, count_bn)) + BN_add_word(config->start_bn, 1); + } + } else if (config->start_bn != NULL && + BN_is_negative(config->start_bn)) { + if ((count_bn = + cmb_count_bn(config, nitems)) != NULL) { + BN_add(config->start_bn, + count_bn, config->start_bn); + BN_add_word(config->start_bn, 1); + if (BN_is_negative(config->start_bn)) + BN_zero(config->start_bn); + BN_free(count_bn); + } + } + retval = cmb_bn(config, nitems, items); +#endif + } else { + if (opt_randi) { + count = cmb_count(config, nitems); + if (errno) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + if (gettimeofday(&tv,NULL) == 0) { + srand48((long)tv.tv_usec); + config->start = cmb_rand_range(count) + 1; + } + } else if (nstart != 0) { + count = cmb_count(config, nitems); + if (errno) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + if (count > nstart) + config->start = count - nstart + 1; + else + config->start = 0; + } + retval = cmb(config, nitems, items); + if (errno) { + err(EXIT_FAILURE, NULL); + /* NOTREACHED */ + } + } + + /* + * Clean up + */ + if (opt_file || opt_range) { + for (n = 0; n < nitems; n++) + free(items[n]); + free(items); + } else if (opt_transform) { + for (n = 0; n < nitems; n++) { + memcpy(&xitem, &items[n], sizeof(char *)); + if (opt_range) + free(xitem->cp); + free(xitem); + } + free(items); + } + if (opt_find) { + if (free_find) + free(cmb_transform_find->cp); + free(cmb_transform_find); + if (cmb_transform_find_buf != NULL) + free(cmb_transform_find_buf); + } + free(config); + + return (retval); +} + +/* + * Print short usage statement to stderr and exit with error status. + */ +static void +cmb_usage(void) +{ + fprintf(stderr, "usage: %s [options] [item ...]\n", pgm); +#define OPTFMT "\t%-10s %s\n" +#define OPTFMT_1U "\t%-10s %s%u%s\n" + fprintf(stderr, "OPTIONS:\n"); + fprintf(stderr, OPTFMT, "-0", + "Read items terminated by NUL when given `-f'."); + fprintf(stderr, OPTFMT, "-c num", + "Produce num combinations (default `0' for all)."); + fprintf(stderr, OPTFMT, "-D", + "Enable debugging information on stderr." + ); + fprintf(stderr, OPTFMT, "-d text", "Item delimiter (default is ` ')."); + fprintf(stderr, OPTFMT, "-e", "Show empty set with no items."); + fprintf(stderr, OPTFMT, "-F num", + "Find `-X op' results matching num."); + fprintf(stderr, OPTFMT, "-f", + "Treat arguments as files to read items from; `-' for stdin."); + fprintf(stderr, OPTFMT, "-i num", + "Skip the first num-1 combinations."); + fprintf(stderr, OPTFMT, "-k size", + "Number or range (`min..max' or `min-max') of items."); + fprintf(stderr, OPTFMT, "-N", "Show combination sequence numbers."); + fprintf(stderr, OPTFMT, "-n num", + "Limit arguments taken from the command-line."); + fprintf(stderr, OPTFMT, "-o", + "Disable OpenSSL (limits calculations to 64-bits)."); + fprintf(stderr, OPTFMT, "-P num", + "Set floating point precision when given `-X op'."); + fprintf(stderr, OPTFMT, "-p text", "Prefix text for each line."); + fprintf(stderr, OPTFMT, "-q", + "Quiet. Do not print items from set when given `-X op'."); + fprintf(stderr, OPTFMT_1U, "-r", + "Treat arguments as ranges of up-to ", UINT_MAX, " items."); + fprintf(stderr, OPTFMT, "-S", "Silent (for performance benchmarks)."); + fprintf(stderr, OPTFMT, "-s text", "Suffix text for each line."); + fprintf(stderr, OPTFMT, "-t", + "Print number of combinations and exit."); + fprintf(stderr, OPTFMT, "-v", + "Print version info to stdout and exit."); + fprintf(stderr, OPTFMT, "-X op", + "Perform math on items where `op' is add, sub, div, or mul."); + fprintf(stderr, OPTFMT, "-z", + "Print combinations NUL terminated (use with `xargs -0')."); + exit(EXIT_FAILURE); +} + +/* + * Return pseudo-random 64-bit unsigned integer in range 0 <= return <= range. + */ +static uint64_t +cmb_rand_range(uint64_t range) +{ + static const uint64_t M = (uint64_t)~0; + uint64_t exclusion = p2(range) ? 0 : M % range + 1; + uint64_t res = 0; + + while ((res = urand64()) < exclusion) {} + return (res % range); +} + +static size_t +numlen(const char *s) +{ + if (s == NULL || *s == '\0') + return (0); + else if (*s == '-') + return (strspn(&s[1], digit) + 1); + else + return (strspn(s, digit)); +} + +static size_t +rangelen(const char *s, size_t nlen, size_t slen) +{ + size_t rlen; + const char *cp = s; + + if (nlen == 0) + return (0); + else if (nlen == slen) + return (nlen); + + cp += nlen; + if (*cp == '-') { + cp += 1; + if (*cp == '\0') + return (0); + return (nlen + strspn(cp, digit) + 1); + } else if (strncmp(cp, "..", 2) == 0) { + cp += 2; + if ((rlen = numlen(cp)) == 0) + return (0); + return (nlen + rlen + 2); + } else + return (0); +} + +static uint8_t +parse_range(const char *s, uint32_t *min, uint32_t *max) +{ + const char *cp; + size_t nlen; + size_t optlen; + uint64_t ull; + + errno = 0; + + if (s == NULL || ((nlen = numlen(s)) != (optlen = strlen(s)) && + rangelen(s, nlen, optlen) != optlen)) { + errno = EINVAL; + return (FALSE); + } + + if (*s == '-') { + ull = strtoull(&s[1], (char **)NULL, 10); + *min = UINT_MAX - (uint32_t)ull; + } else { + ull = strtoull(s, (char **)NULL, 10); + *min = (uint32_t)ull; + } + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + + cp = &s[nlen]; + if (*cp == '\0') + *max = *s == '-' ? (uint32_t)ull : *min; + else if ((strncmp(cp, "..", 2)) == 0) { + cp += 2; + if (*cp == '-') { + ull = strtoull(&cp[1], (char **)NULL, 10); + *max = UINT_MAX - (uint32_t)ull; + } else { + ull = strtoull(cp, (char **)NULL, 10); + *max = (uint32_t)ull; + } + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + } else if (*cp == '-') { + ull = strtoull(&cp[1], (char **)NULL, 10); + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + *max = (uint32_t)ull; + } else { + errno = EINVAL; + return (FALSE); + } + + return (TRUE); +} + +static size_t +unumlen(const char *s) +{ + if (s == NULL || *s == '\0') + return (0); + else + return (strspn(s, digit)); +} + +static size_t +urangelen(const char *s, size_t nlen, size_t slen) +{ + size_t rlen; + const char *cp = s; + + if (nlen == 0) + return (0); + else if (nlen == slen) + return (nlen); + + cp += nlen; + if (*cp == '-') { + cp += 1; + if (*cp == '\0') + return (0); + return (nlen + strspn(cp, digit) + 1); + } else if (strncmp(cp, "..", 2) == 0) { + cp += 2; + if ((rlen = unumlen(cp)) == 0) + return (0); + return (nlen + rlen + 2); + } else + return (0); +} + +static uint8_t +parse_unum(const char *s, uint32_t *n) +{ + uint64_t ull; + + errno = 0; + + if (s == NULL || unumlen(s) != strlen(s)) { + errno = EINVAL; + return (FALSE); + } + + ull = strtoull(optarg, (char **)NULL, 10); + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + + *n = (uint32_t)ull; + + return (TRUE); +} + +static uint8_t +parse_urange(const char *s, uint32_t *min, uint32_t *max) +{ + const char *cp; + size_t nlen; + size_t optlen; + uint64_t ull; + + errno = 0; + + if (s == NULL || ((nlen = unumlen(s)) != (optlen = strlen(s)) && + urangelen(s, nlen, optlen) != optlen) || *s == '-') { + errno = EINVAL; + return (FALSE); + } + + ull = strtoull(s, (char **)NULL, 10); + *min = *max = (uint32_t)ull; + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + + cp = &s[nlen]; + if (*cp == '\0') + *max = *min; + else if ((strncmp(cp, "..", 2)) == 0) { + cp += 2; + ull = strtoull(cp, (char **)NULL, 10); + *max = (uint32_t)ull; + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + } else if (*cp == '-') { + ull = strtoull(&cp[1], (char **)NULL, 10); + if (errno != 0) + return (FALSE); + else if (ull > UINT_MAX) { + errno = ERANGE; + return (FALSE); + } + *max = (uint32_t)ull; + } else { + errno = EINVAL; + return (FALSE); + } + + return (TRUE); +} + +static uint32_t +range_char(uint32_t start, uint32_t stop, uint32_t idx, char *dst[]) +{ + int len; + uint32_t num; + + if (start <= stop) { + for (num = start; num <= stop; num++) { + len = snprintf(NULL, 0, "%u", num) + 1; + if ((dst[idx] = malloc((unsigned long)len)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + (void)sprintf(dst[idx], "%u", num); + idx++; + } + } else { + for (num = start; num >= stop; num--) { + len = snprintf(NULL, 0, "%u", num) + 1; + if ((dst[idx] = (char *)malloc((unsigned long)len)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + (void)sprintf(dst[idx], "%u", num); + idx++; + } + } + + return (idx); +} + +static uint32_t +range_float(uint32_t start, uint32_t stop, uint32_t idx, char *dst[]) +{ + int len; + uint32_t num; + size_t size; + struct cmb_xitem *xitem; + + size = sizeof(struct cmb_xitem); + if (start <= stop) { + for (num = start; num <= stop; num++) { + if ((xitem = malloc(size)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + len = snprintf(NULL, 0, "%u", num) + 1; + if ((xitem->cp = malloc((unsigned long)len)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + (void)sprintf(xitem->cp, "%u", num); + xitem->as.ld = (long double)num; + dst[idx] = (char *)xitem; + idx++; + } + } else { + for (num = start; num >= stop; num--) { + if ((xitem = malloc(size)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + len = snprintf(NULL, 0, "%u", num) + 1; + if ((xitem->cp = malloc((unsigned long)len)) == NULL) { + errx(EXIT_FAILURE, "Out of memory?!"); + /* NOTREACHED */ + } + (void)sprintf(xitem->cp, "%u", num); + xitem->as.ld = (long double)num; + dst[idx] = (char *)xitem; + idx++; + } + } + + return (idx); +} + +/* + * For performance benchmarking + */ +static +CMB_ACTION(cmb_nop) +{ + (void)config; + (void)seq; + (void)nitems; + (void)items; + return (0); +} +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +static +CMB_ACTION_BN(cmb_nop_bn) +{ + (void)config; + (void)seq; + (void)nitems; + (void)items; + return (0); +} +#endif + +/* + * Transformation functions + */ +static CMB_TRANSFORM_OP(*, cmb_mul); +static CMB_TRANSFORM_OP(/, cmb_div); +static CMB_TRANSFORM_OP(+, cmb_add); +static CMB_TRANSFORM_OP(-, cmb_sub); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +static CMB_TRANSFORM_OP_BN(*, cmb_mul_bn); +static CMB_TRANSFORM_OP_BN(/, cmb_div_bn); +static CMB_TRANSFORM_OP_BN(+, cmb_add_bn); +static CMB_TRANSFORM_OP_BN(-, cmb_sub_bn); +#endif + +/* + * Find transformation functions + */ +static CMB_TRANSFORM_OP_FIND(*, cmb_mul_find); +static CMB_TRANSFORM_OP_FIND(/, cmb_div_find); +static CMB_TRANSFORM_OP_FIND(+, cmb_add_find); +static CMB_TRANSFORM_OP_FIND(-, cmb_sub_find); +#if defined(HAVE_LIBCRYPTO) && defined(HAVE_OPENSSL_BN_H) +static CMB_TRANSFORM_OP_FIND_BN(*, cmb_mul_find_bn); +static CMB_TRANSFORM_OP_FIND_BN(/, cmb_div_find_bn); +static CMB_TRANSFORM_OP_FIND_BN(+, cmb_add_find_bn); +static CMB_TRANSFORM_OP_FIND_BN(-, cmb_sub_find_bn); +#endif