Changeset View
Standalone View
lib/libcmb/cmb.c
- This file was added.
Property | Old Value | New Value |
---|---|---|
svn:eol-style | null | native \ No newline at end of property |
svn:keywords | null | FreeBSD=%H \ No newline at end of property |
svn:mime-type | null | text/plain \ No newline at end of property |
/*- | |||||
* Copyright (c) 2002-2018 Devin Teske <dteske@FreeBSD.org> | |||||
* All rights reserved. | |||||
adridg: The year range looks unlikely (but possible .. it doesn't match `cmb.h` in any case) | |||||
Done Inline ActionsI am seeing that libcmb/cmb.c and libcmb/cmb.h match: From libcmb/cmb.c: * Copyright (c) 2002-2018 Devin Teske <dteske@FreeBSD.org> From libcmb/cmb.h: * Copyright (c) 2002-2018 Devin Teske <dteske@FreeBSD.org> Which is important because the first version of the code started its life as a utility for compiling all possible binary combinations of a given software, released on April 4, 2002 [1]. The reason why the copyrights in libcmb/cmb.c and libcmb/cmb.h (which read 2002-2018) differ from that of the other copyrights is because the libcmb/cmb.[ch] code is directly derived from my longterm work [2] while code with a copyright of 2018 is new code not drawn from the historical body of work. [1] http://synhxd.sourceforge.net/doc/changes.txt (Excerpt below) Version 0.2.2 April 4, 2002 =========================== - changed output of `/version' from `hxd ver...' to `shxd ver...' (since both shxd and hxd are in the 0.2.x version system now) - created a new mkbin script (read the agreement in the source of the file, or don't run it)(file is `utils/bashmkbin') [2] bashmkbin de-obfuscated, optimized, and ported to bourne shell dteske: I am seeing that `libcmb/cmb.c` and `libcmb/cmb.h` match:
From `libcmb/cmb.c`:
```
*… | |||||
* | |||||
* Redistribution and use in source and binary forms, with or without | |||||
* modification, are permitted provided that the following conditions | |||||
* are met: | |||||
* 1. Redistributions of source code must retain the above copyright | |||||
* notice, this list of conditions and the following disclaimer. | |||||
* 2. Redistributions in binary form must reproduce the above copyright | |||||
* notice, this list of conditions and the following disclaimer in the | |||||
* documentation and/or other materials provided with the distribution. | |||||
* | |||||
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |||||
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |||||
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |||||
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |||||
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |||||
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |||||
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |||||
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |||||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |||||
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |||||
* SUCH DAMAGE. | |||||
*/ | |||||
#include <sys/cdefs.h> | |||||
#ifdef __FBSDID | |||||
__FBSDID("$FrauBSD: pkgcenter/depend/libcmb/cmb.c 2018-04-03 10:38:24 -0700 freebsdfrau $"); | |||||
__FBSDID("$FreeBSD$"); | |||||
#endif | |||||
#include <err.h> | |||||
#include <limits.h> | |||||
#include <stddef.h> | |||||
#include <stdint.h> | |||||
#include <stdio.h> | |||||
#include <stdlib.h> | |||||
#include <string.h> | |||||
#include "cmb.h" | |||||
/* | |||||
* Takes pointer to `struct cmb_config' options and number of items. Returns | |||||
* total number of combinations according to config options. | |||||
*/ | |||||
uint64_t | |||||
cmb_count(struct cmb_config *config, uint32_t nitems) | |||||
{ | |||||
int8_t nextset = 1; | |||||
uint32_t curset; | |||||
uint32_t i = nitems; | |||||
uint32_t k; | |||||
uint32_t p; | |||||
uint32_t setdone = nitems; | |||||
uint32_t setinit = 1; | |||||
uint64_t count = 0; | |||||
long double z = 1; | |||||
uint64_t ncombos; | |||||
if (nitems == 0) return (0); | |||||
/* Process config options */ | |||||
if (config != NULL) { | |||||
if (config->range_min != 0 || config->range_max != 0) { | |||||
setinit = config->range_min; | |||||
setdone = config->range_max; | |||||
} | |||||
} | |||||
/* Adjust values to be non-zero (mathematical constraint) */ | |||||
if (setinit == 0) setinit = 1; | |||||
if (setdone == 0) setdone = 1; | |||||
/* Return zero if the request is out of range */ | |||||
if (setinit > nitems && setdone > nitems) return (0); | |||||
/* Enforce limits so we don't run over bounds */ | |||||
if (setinit > nitems) setinit = nitems; | |||||
if (setdone > nitems) setdone = nitems; | |||||
/* If entire set is requested, return 2^N-1 */ | |||||
if ((setinit == 1 && setdone == nitems) || | |||||
(setinit == nitems && setdone == 1)) | |||||
return (ULLONG_MAX >> (64 - nitems)); | |||||
/* Set the direction of flow (incrementing vs. decrementing) */ | |||||
if (setinit > setdone) nextset = -1; | |||||
/* | |||||
* Loop over each `set' in the configured direction until we are done | |||||
*/ | |||||
p = nextset > 0 ? setinit - 1 : setinit; | |||||
for (k = 1; k <= p; k++) z = (z * i--) / k; | |||||
for (curset = setinit; | |||||
nextset > 0 ? curset <= setdone : curset >= setdone; | |||||
curset += nextset) | |||||
{ | |||||
/* Calculate number of combinations (incrementing) */ | |||||
if (nextset > 0) z = (z * i--) / k++; | |||||
/* Add number of combinations in this set to total */ | |||||
if ((ncombos = z) == 0) | |||||
errx(EXIT_FAILURE, "Number too large!"); | |||||
if (ncombos > ULLONG_MAX - count) | |||||
errx(EXIT_FAILURE, "Number too large!"); | |||||
count += ncombos; | |||||
/* Calculate number of combinations (decrementing) */ | |||||
if (nextset < 0) z = (z * --k) / ++i; | |||||
} | |||||
return (count); | |||||
} | |||||
/* | |||||
* Takes pointer to `struct cmb_config' options, number of items, and array of | |||||
* `char *' items. Calculates combinations according to options and either | |||||
* prints combinations to stdout (default) or runs `action' if passed-in as | |||||
* function pointer member of `config' argument. | |||||
*/ | |||||
int | |||||
cmb(struct cmb_config *config, uint32_t nitems, char *items[]) | |||||
{ | |||||
uint8_t docount = FALSE; | |||||
uint8_t doseek = FALSE; | |||||
int8_t nextset = 1; | |||||
int retval = 0; | |||||
uint32_t curset; | |||||
uint32_t i = nitems; | |||||
uint32_t k; | |||||
uint32_t n; | |||||
uint32_t p; | |||||
uint32_t seed; | |||||
uint32_t setdone = nitems; | |||||
uint32_t setinit = 1; | |||||
uint32_t setmax; | |||||
uint32_t setnums_last; | |||||
uint32_t setpos; | |||||
uint32_t setpos_backend; | |||||
uint64_t combo; | |||||
uint64_t count = 0; | |||||
uint64_t ncombos; | |||||
uint64_t seek = 0; | |||||
long double z = 1; | |||||
char **curitems; | |||||
uint32_t *setnums; | |||||
uint32_t *setnums_backend; | |||||
int (*action)(uint32_t nitems, char *items[]) = cmb_print; | |||||
if (nitems == 0) return (0); | |||||
/* Process config options */ | |||||
if (config != NULL) { | |||||
cmb_print_nul = config->nul_terminate; | |||||
if (config->action != NULL) action = config->action; | |||||
if (config->count != 0) { | |||||
docount = TRUE; | |||||
count = config->count; | |||||
} | |||||
if (config->delimiter != NULL) | |||||
cmb_print_delimiter = config->delimiter; | |||||
if (config->prefix != NULL) cmb_print_prefix = config->prefix; | |||||
if (config->range_min != 0 || config->range_max != 0) { | |||||
setinit = config->range_min; | |||||
setdone = config->range_max; | |||||
} | |||||
if (config->start > 1) { | |||||
doseek = TRUE; | |||||
seek = config->start; | |||||
} | |||||
if (config->suffix != NULL) cmb_print_suffix = config->suffix; | |||||
} | |||||
/* Adjust values to be non-zero (mathematical constraint) */ | |||||
if (setinit == 0) setinit = 1; | |||||
if (setdone == 0) setdone = 1; | |||||
/* Enforce limits so we don't run over bounds */ | |||||
if (setinit > nitems) setinit = nitems; | |||||
if (setdone > nitems) setdone = nitems; | |||||
/* Set the direction of flow (incrementing vs. decrementing) */ | |||||
if (setinit > setdone) nextset = -1; | |||||
/* Allocate memory */ | |||||
setmax = setdone > setinit ? setdone : setinit; | |||||
if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
if ((setnums_backend = | |||||
(uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
/* | |||||
* Loop over each `set' in the configured direction until we are done. | |||||
* NB: Each `set' can represent a single item or multiple items. | |||||
*/ | |||||
p = nextset > 0 ? setinit - 1 : setinit; | |||||
for (k = 1; k <= p; k++) z = (z * i--) / k; | |||||
for (curset = setinit; | |||||
nextset > 0 ? curset <= setdone : curset >= setdone; | |||||
curset += nextset) | |||||
{ | |||||
/* Calculate number of combinations (incrementing) */ | |||||
if (nextset > 0) z = (z * i--) / k++; | |||||
/* Cast number of combinations in set to integer */ | |||||
if ((ncombos = z) == 0) | |||||
errx(EXIT_FAILURE, "Number too large!"); | |||||
/* Jump to next set if requested start is beyond this one */ | |||||
if (doseek) { | |||||
if (seek > ncombos) { | |||||
seek -= ncombos; | |||||
continue; | |||||
} else if (seek == 1) { | |||||
doseek = FALSE; | |||||
} | |||||
} | |||||
/* Fill array with the initial positional arguments */ | |||||
for (n = 0; n < curset; n++) curitems[n] = items[n]; | |||||
/* Produce results with the first set of items */ | |||||
if (!doseek) { | |||||
if ((retval = action(curset, curitems)) != 0) break; | |||||
if (docount && --count == 0) break; | |||||
} | |||||
/* | |||||
* Prefill two arrays used for matrix calculations. | |||||
* | |||||
* The first array (setnums) is a linear sequence starting at | |||||
* one (1) and ending at N (where N is the same integer as the | |||||
* current set we're operating on). For example, if we are | |||||
* currently on a set-of-2, setnums is 1, 2. | |||||
* | |||||
* The second array (setnums_backend) is a linear sequence | |||||
* starting at nitems-N and ending at nitems (again, N is the | |||||
* same integer as the current set we are operating on; nitems | |||||
* is the total number of items). For example, if we are | |||||
* operating on a set-of-2, and nitems is 8, setnums_backend is | |||||
* set to 7, 8. | |||||
*/ | |||||
p = 0; | |||||
for (n = 0; n < curset; n++) setnums[n] = n; | |||||
for (n = curset; n > 0; n--) setnums_backend[p++] = nitems - n; | |||||
/* | |||||
* Process remaining self-similar combinations in the set. | |||||
*/ | |||||
for (combo = 1; combo < ncombos; combo++) { | |||||
setnums_last = curset; | |||||
/* | |||||
* Using self-similarity (matrix) theorem, determine | |||||
* (by comparing the [sliding] setnums to the stored | |||||
* setnums_backend) the number of arguments that remain | |||||
* available for shifting into a new setnums value | |||||
* (for later mapping into curitems). | |||||
* | |||||
* In essence, determine when setnums has slid into | |||||
* setnums_backend in which case we can mathematically | |||||
* use the last item to find the next-new item. | |||||
*/ | |||||
for (n = curset; n > 0; n--) { | |||||
setpos = setnums[n - 1]; | |||||
setpos_backend = setnums_backend[n - 1]; | |||||
/* | |||||
* If setpos is equal to or greater than | |||||
* setpos_backend then we keep iterating over | |||||
* the current set's list of argument positions | |||||
* until otherwise; each time incrementing the | |||||
* amount of numbers we must produce from | |||||
* formulae rather than stored position. | |||||
*/ | |||||
setnums_last = n - 1; | |||||
if (setpos < setpos_backend) break; | |||||
} | |||||
/* | |||||
* The next few stanzas are dedicated to rebuilding the | |||||
* setnums array for mapping positional items | |||||
* [immediately following] into curitems. | |||||
*/ | |||||
/* | |||||
* Get the generator number used to populate unknown | |||||
* positions in the matrix (using self-similarity). | |||||
*/ | |||||
seed = setnums[setnums_last]; | |||||
/* | |||||
* Use the generator number to populate any position | |||||
* numbers that weren't carried over from previous | |||||
* combination run -- using self-similarity theorem. | |||||
*/ | |||||
for (n = setnums_last; n <= curset; n++) | |||||
setnums[n] = seed + n - setnums_last + 1; | |||||
/* Now map new setnums into values stored in items */ | |||||
for (n = 0; n < curset; n++) | |||||
curitems[n] = items[setnums[n]]; | |||||
/* Produce results with this set of items */ | |||||
if (doseek) { | |||||
seek--; | |||||
if (seek == 1) doseek = FALSE; | |||||
} | |||||
if (!doseek || seek == 1) { | |||||
doseek = FALSE; | |||||
if ((retval = action(curset, curitems)) != 0) | |||||
goto cmb_return; | |||||
if (docount && --count == 0) goto cmb_return; | |||||
} | |||||
} /* for combo */ | |||||
/* Calculate number of combinations (decrementing) */ | |||||
if (nextset < 0) z = (z * --k) / i++; | |||||
} /* for curset */ | |||||
cmb_return: | |||||
free(curitems); | |||||
free(setnums); | |||||
free(setnums_backend); | |||||
return (retval); | |||||
} | |||||
int | |||||
cmb_print(uint32_t nitems, char *items[]) | |||||
{ | |||||
uint32_t n; | |||||
if (cmb_print_prefix != NULL) printf("%s", cmb_print_prefix); | |||||
for (n = 0; n < nitems; n++) { | |||||
printf("%s", items[n]); | |||||
if (n < nitems - 1 && cmb_print_delimiter != NULL) | |||||
printf("%s", cmb_print_delimiter); | |||||
} | |||||
if (cmb_print_suffix != NULL) printf("%s", cmb_print_suffix); | |||||
if (cmb_print_nul) | |||||
printf("%c", 0); | |||||
else | |||||
printf("\n"); | |||||
return (0); | |||||
} | |||||
#ifdef HAVE_OPENSSL_BN_H | |||||
/* | |||||
* Takes pointer to `struct cmb_config' options and number of items. Returns | |||||
* total number of combinations according to config options. Numbers formatted | |||||
* as openssl bn(3) BIGNUM type. | |||||
*/ | |||||
BIGNUM * | |||||
cmb_count_bn(struct cmb_config *config, uint32_t nitems) | |||||
{ | |||||
int8_t nextset = 1; | |||||
Done Inline ActionsWhen iterating downwards, eg. using command-line options -k 3..2 this over-estimates the size remaining, so it will print garbage at the end (e.g. cmb -k 3..2 $( seq 1 4 ) prints bits of my environment and cmd -k 3..2 $( seq 1 3 ) bails out with Result too large). The symmetry with the nextset > 0 is broken which looks funny. z=(z*--k)/++i fixes the issue. adridg: When iterating **downwards**, eg. using command-line options `-k 3..2` this over-estimates the… | |||||
Done Inline ActionsGood catch! Fixed in the next update dteske: Good catch! Fixed in the next update | |||||
uint32_t curset; | |||||
uint32_t i = nitems; | |||||
uint32_t k; | |||||
uint32_t p; | |||||
uint32_t setdone = nitems; | |||||
uint32_t setinit = 1; | |||||
BIGNUM *count = NULL; | |||||
BIGNUM *ncombos = NULL; | |||||
if (nitems == 0) return (NULL); | |||||
/* Process config options */ | |||||
if (config != NULL) { | |||||
if (config->range_min != 0 || config->range_max != 0) { | |||||
setinit = config->range_min; | |||||
setdone = config->range_max; | |||||
} | |||||
} | |||||
/* Adjust values to be non-zero (mathematical constraint) */ | |||||
if (setinit == 0) setinit = 1; | |||||
if (setdone == 0) setdone = 1; | |||||
/* Return zero if the request is out of range */ | |||||
if (setinit > nitems && setdone > nitems) return (NULL); | |||||
/* Enforce limits so we don't run over bounds */ | |||||
if (setinit > nitems) setinit = nitems; | |||||
if (setdone > nitems) setdone = nitems; | |||||
/* Set the direction of flow (incrementing vs decrementing) */ | |||||
if (setinit > setdone) nextset = -1; | |||||
/* Initialize count */ | |||||
if ((count = BN_new()) == NULL) return (NULL); | |||||
if (!BN_zero(count)) goto cmb_count_bn_return; | |||||
/* If entire set is requested, return 2^N-1 */ | |||||
if ((setinit == 1 && setdone == nitems) || | |||||
(setinit == nitems && setdone == 1)) { | |||||
if (!BN_lshift(count, BN_value_one(), nitems)) | |||||
goto cmb_count_bn_return; | |||||
if (!BN_sub_word(count, 1)) goto cmb_count_bn_return; | |||||
goto cmb_count_bn_return; | |||||
} | |||||
/* Allocate memory */ | |||||
if ((ncombos = BN_new()) == NULL) goto cmb_count_bn_return; | |||||
if (!BN_one(ncombos)) goto cmb_count_bn_return; | |||||
/* | |||||
* Loop over each `set' in the configured direction until we are done | |||||
*/ | |||||
p = nextset > 0 ? setinit - 1 : setinit; | |||||
for (k = 1; k <= p; k++) { | |||||
if (!BN_mul_word(ncombos, i--)) goto cmb_count_bn_return; | |||||
if (BN_div_word(ncombos, k) == (BN_ULONG)-1) | |||||
goto cmb_count_bn_return; | |||||
} | |||||
for (curset = setinit; | |||||
nextset > 0 ? curset <= setdone : curset >= setdone; | |||||
curset += nextset) | |||||
{ | |||||
/* Calculate number of combinations (incrementing) */ | |||||
if (nextset > 0) { | |||||
if (!BN_mul_word(ncombos, i--)) break; | |||||
if (BN_div_word(ncombos, k++) == (BN_ULONG)-1) break; | |||||
} | |||||
/* Add number of combinations in this set to total */ | |||||
if (!BN_add(count, count, ncombos)) break; | |||||
/* Calculate number of combinations (decrementing) */ | |||||
if (nextset < 0) { | |||||
if (!BN_mul_word(ncombos, --k)) break; | |||||
if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1) break; | |||||
} | |||||
} | |||||
cmb_count_bn_return: | |||||
BN_free(ncombos); | |||||
return (count); | |||||
} | |||||
/* | |||||
* Takes pointer to `struct cmb_config' options, number of items, and array | |||||
* of `char *' items. Calculates combinations according to options and either | |||||
* prints combinations to stdout (default) or runs `action' if passed-in as | |||||
* function pointer member of `config' argument. Numbers formatted as openssl | |||||
* bn(3) BIGNUM type. | |||||
*/ | |||||
int | |||||
cmb_bn(struct cmb_config *config, uint32_t nitems, char *items[]) | |||||
{ | |||||
uint8_t docount = FALSE; | |||||
uint8_t doseek = FALSE; | |||||
int8_t nextset = 1; | |||||
int retval = 0; | |||||
uint32_t curset; | |||||
uint32_t i = nitems; | |||||
uint32_t k; | |||||
uint32_t n; | |||||
uint32_t p; | |||||
uint32_t seed; | |||||
uint32_t setdone = nitems; | |||||
uint32_t setinit = 1; | |||||
uint32_t setmax; | |||||
uint32_t setnums_last; | |||||
uint32_t setpos; | |||||
uint32_t setpos_backend; | |||||
char **curitems; | |||||
uint32_t *setnums; | |||||
uint32_t *setnums_backend; | |||||
BIGNUM *combo = NULL; | |||||
BIGNUM *count = NULL; | |||||
BIGNUM *ncombos = NULL; | |||||
BIGNUM *seek = NULL; | |||||
int (*action)(uint32_t nitems, char *items[]) = cmb_print; | |||||
if (nitems == 0) return (0); | |||||
/* Process config options */ | |||||
if (config != NULL) { | |||||
cmb_print_nul = config->nul_terminate; | |||||
if (config->action != NULL) action = config->action; | |||||
if (config->count_bn != NULL && | |||||
!BN_is_negative(config->count_bn) && | |||||
!BN_is_zero(config->count_bn)) | |||||
{ | |||||
docount = TRUE; | |||||
if ((count = BN_dup(config->count_bn)) == NULL) | |||||
goto cmb_bn_return; | |||||
} | |||||
if (config->delimiter != NULL) | |||||
cmb_print_delimiter = config->delimiter; | |||||
if (config->prefix != NULL) cmb_print_prefix = config->prefix; | |||||
if (config->range_min != 0 || config->range_max != 0) { | |||||
setinit = config->range_min; | |||||
setdone = config->range_max; | |||||
} | |||||
if (config->start_bn != NULL && | |||||
!BN_is_negative(config->start_bn) && | |||||
!BN_is_zero(config->start_bn) && | |||||
!BN_is_one(config->start_bn)) | |||||
{ | |||||
doseek = TRUE; | |||||
if ((seek = BN_dup(config->start_bn)) == NULL) | |||||
goto cmb_bn_return; | |||||
} | |||||
if (config->suffix != NULL) cmb_print_suffix = config->suffix; | |||||
} | |||||
/* Adjust values to be non-zero (mathematical constraint) */ | |||||
if (setinit == 0) setinit = 1; | |||||
if (setdone == 0) setdone = 1; | |||||
/* Enforce limits so we don't run over bounds */ | |||||
if (setinit > nitems) setinit = nitems; | |||||
if (setdone > nitems) setdone = nitems; | |||||
/* Set the direction of flow (incrementing vs. decrementing) */ | |||||
if (setinit > setdone) nextset = -1; | |||||
/* Allocate memory */ | |||||
if ((combo = BN_new()) == NULL) goto cmb_bn_return; | |||||
if ((ncombos = BN_new()) == NULL) goto cmb_bn_return; | |||||
if (!BN_one(ncombos)) goto cmb_bn_return; | |||||
setmax = setdone > setinit ? setdone : setinit; | |||||
if ((curitems = (char **)malloc(sizeof(char *) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
if ((setnums = (uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
if ((setnums_backend = | |||||
(uint32_t *)malloc(sizeof(uint32_t) * setmax)) == NULL) | |||||
errx(EXIT_FAILURE, "Out of memory?!"); | |||||
/* | |||||
* Loop over each `set' in the configured direction until we are done. | |||||
* NB: Each `set' can represent a single item or multiple items. | |||||
*/ | |||||
p = nextset > 0 ? setinit - 1 : setinit; | |||||
for (k = 1; k <= p; k++) { | |||||
if (!BN_mul_word(ncombos, i--)) goto cmb_bn_return; | |||||
if (BN_div_word(ncombos, k) == (BN_ULONG)-1) | |||||
goto cmb_bn_return; | |||||
} | |||||
for (curset = setinit; | |||||
nextset > 0 ? curset <= setdone : curset >= setdone; | |||||
curset += nextset) | |||||
{ | |||||
/* Calculate number of combinations (incrementing) */ | |||||
if (nextset > 0) { | |||||
if (!BN_mul_word(ncombos, i--)) break; | |||||
if (BN_div_word(ncombos, k++) == (BN_ULONG)-1) break; | |||||
} | |||||
/* Jump to next set if requested start is beyond this one */ | |||||
if (doseek) { | |||||
if (BN_ucmp(seek, ncombos) > 0) { | |||||
if (!BN_sub(seek, seek, ncombos)) break; | |||||
continue; | |||||
} else if (BN_is_one(seek)) { | |||||
doseek = FALSE; | |||||
} | |||||
} | |||||
/* Fill array with the initial positional arguments */ | |||||
for (n = 0; n < curset; n++) curitems[n] = items[n]; | |||||
/* Produce results with the first set of items */ | |||||
if (!doseek) { | |||||
if ((retval = action(curset, curitems)) != 0) break; | |||||
if (docount) { | |||||
if (!BN_sub_word(count, 1)) break; | |||||
if (BN_is_zero(count)) break; | |||||
} | |||||
} | |||||
/* | |||||
* Prefill two arrays used for matrix calculations. | |||||
* | |||||
* The first array (setnums) is a linear sequence starting at | |||||
* one (1) and ending at N (where N is the same integer as the | |||||
* current set we're operating on). For example, if we are | |||||
* currently on a set-of-2, setnums is 1, 2. | |||||
* | |||||
* The second array (setnums_backend) is a linear sequence | |||||
* starting at nitems-N and ending at nitems (again, N is the | |||||
* same integer as the current set we are operating on; nitems | |||||
* is the total number of items). For example, if we are | |||||
* operating on a set-of-2, and nitems is 8, setnums_backend is | |||||
* set to 7, 8. | |||||
*/ | |||||
p = 0; | |||||
for (n = 0; n < curset; n++) setnums[n] = n; | |||||
for (n = curset; n > 0; n--) setnums_backend[p++] = nitems - n; | |||||
/* | |||||
* Process remaining self-similar combinations in the set. | |||||
*/ | |||||
if (!BN_one(combo)) break; | |||||
for (; BN_ucmp(combo, ncombos) < 0; ) { | |||||
setnums_last = curset; | |||||
/* | |||||
* Using self-similarity (matrix) theorem, determine | |||||
* (by comparing the [sliding] setnums to the stored | |||||
* setnums_backend) the number of arguments that remain | |||||
* available for shifting into a new setnums value | |||||
* (for later mapping into curitems). | |||||
* | |||||
* In essence, determine when setnums has slid into | |||||
* setnums_backend in which case we can mathematically | |||||
* use the last item to find the next-new item. | |||||
*/ | |||||
for (n = curset; n > 0; n--) { | |||||
setpos = setnums[n - 1]; | |||||
setpos_backend = setnums_backend[n - 1]; | |||||
/* | |||||
* If setpos is equal to or greater than | |||||
* setpos_backend then we keep iterating over | |||||
* the current set's list of argument positions | |||||
* until otherwise; each time incrementing the | |||||
* amount of numbers we must produce from | |||||
* formulae rather than stored position. | |||||
*/ | |||||
setnums_last = n - 1; | |||||
if (setpos < setpos_backend) break; | |||||
} | |||||
/* | |||||
* The next few stanzas are dedicated to rebuilding the | |||||
* setnums array for mapping positional items | |||||
* [immediately following] into curitems. | |||||
*/ | |||||
/* | |||||
* Get the generator number used to populate unknown | |||||
* positions in the matrix (using self-similarity). | |||||
*/ | |||||
seed = setnums[setnums_last]; | |||||
/* | |||||
* Use the generator number to populate any position | |||||
* numbers that weren't carried over from previous | |||||
* combination run -- using self-similarity theorem. | |||||
*/ | |||||
for (n = setnums_last; n <= curset; n++) | |||||
setnums[n] = seed + n - setnums_last + 1; | |||||
/* Now map new setnums into values stored in items */ | |||||
for (n = 0; n < curset; n++) | |||||
curitems[n] = items[setnums[n]]; | |||||
/* Produce results with this set of items */ | |||||
if (doseek) { | |||||
if (!BN_sub_word(seek, 1)) goto cmb_bn_return; | |||||
if (BN_is_one(seek)) doseek = FALSE; | |||||
} | |||||
if (!doseek || BN_is_one(seek)) { | |||||
doseek = FALSE; | |||||
if ((retval = action(curset, curitems)) != 0) | |||||
goto cmb_bn_return; | |||||
if (docount) { | |||||
if (!BN_sub_word(count, 1)) | |||||
goto cmb_bn_return; | |||||
if (BN_is_zero(count)) | |||||
goto cmb_bn_return; | |||||
} | |||||
} | |||||
if (!BN_add_word(combo, 1)) goto cmb_bn_return; | |||||
} /* for combo */ | |||||
/* Calculate number of combinations (decrementing) */ | |||||
if (nextset < 0) { | |||||
if (!BN_mul_word(ncombos, --k)) break; | |||||
if (BN_div_word(ncombos, ++i) == (BN_ULONG)-1) break; | |||||
} | |||||
} /* for curset */ | |||||
cmb_bn_return: | |||||
BN_free(combo); | |||||
BN_free(count); | |||||
BN_free(ncombos); | |||||
BN_free(seek); | |||||
return (retval); | |||||
} | |||||
#endif /* HAVE_OPENSSL_BN_H */ |
The year range looks unlikely (but possible .. it doesn't match cmb.h in any case)