# Generate candidate passwords from many small subsets of characters from a
# much larger full character set.  This will test for passwords containing too
# few different characters.  As currently implemented, this code will produce
# some duplicates, although their number is relatively small when the maximum
# number of different characters (the maxdiff setting) is significantly lower
# than the maximum length (the maxlength setting).  Nevertheless, you may want
# to pass the resulting candidate passwords through "unique" if you intend to
# test them against hashes that are salted and/or of a slow to compute type.
[List.External:Subsets]
int minlength;		// Minimum password length to try
int maxlength;		// Maximum password length to try
int startdiff;		// Initial number of characters in a subset to try
int maxdiff;		// Maximum number of characters in a subset to try
int last;		// Last character position, zero-based
int lastid;		// Character index in the last position
int id[0x7f];		// Current character indices for other positions
int subset[0x100], c0;	// Current subset
int subcount;		// Number of characters in the current subset
int subid[0x100];	// Indices into charset[] of characters in subset[]
int charset[0x100];	// Full character set
int charcount;		// Number of characters in the full charset

void init()
{
	int i, c;

	minlength = 1;	// Minimum password length to try, must be at least 1
	maxlength = 8;	// Must be at least same as minlength

	startdiff = 1;	// Initial number of different characters to try
	maxdiff = 3;	// Maximum number of different characters to try

/* This defines the character set */
	i = 0;
	c = 0x20;
	while (c <= 0x7e)
		charset[i++] = c++;

	if (maxdiff > (charcount = i))
		maxdiff = i;
	if (maxdiff > maxlength)
		maxdiff = maxlength;

/*
 * Initialize the variables such that generate() gets to its "next subset"
 * code, which will initialize everything for real.
 */
	subcount = (i = startdiff) - 1;
	while (i--)
		subid[i] = charcount;
	subset[0] = c0 = 0;
	last = maxlength - 1;
	lastid = -1;
}

void generate()
{
	int i;

/* Handle the typical case specially */
	if (word[last] = subset[++lastid]) return;

	lastid = 0;
	word[i = last] = c0;
	while (i--) {			// Have a preceding position?
		if (word[i] = subset[++id[i]]) return;
		id[i] = 0;
		word[i] = c0;
	}

	if (++last < maxlength) {	// Next length?
		id[last] = lastid = 0;
		word[last] = c0;
		word[last + 1] = 0;
		return;
	}

/* Next subset */
	if (subcount) {
		int j;
		i = subcount - 1;
		j = charcount;
		while (++subid[i] >= j) {
			if (i--) {
				j--;
				continue;
			}
			subid[i = 0] = 0;
			subset[++subcount] = 0;
			break;
		}
	} else {
		subid[i = 0] = 0;
		subset[++subcount] = 0;
	}
	subset[i] = charset[subid[i]];
	while (++i < subcount)
		subset[i] = charset[subid[i] = subid[i - 1] + 1];

	if (subcount > maxdiff) {
		word = 0;		// Done
		return;
	}

/*
 * We won't be able to fully use the subset if the length is smaller than the
 * character count.  We assume that we've tried all smaller subsets before, so
 * we don't bother with such short lengths.
 */
	if (minlength < subcount)
		last = subcount - 1;
	else
		last = minlength - 1;
	c0 = subset[0];
	i = 0;
	while (i <= last) {
		id[i] = 0;
		word[i++] = c0;
	}
	lastid = 0;
	word[i] = 0;
}