Re: [FWP] crypt() fun

[Bennett Todd <bet@rahul.net>]

2000-06-13-21:04:11 Yitzchak Scott-Thoennes:
> Ok, I give up trying to understand what this is supposed to
> accomplish.  Can you annotate it?

Sorry. Sure. What's more, I'll simplify it a lot; the $last was a
leftover from the first version, that wasn't trying to do lag/2 loop
detection, and it becomes unnecessary in this version.

	my $cur = random_string_gen();
	my @lag = ($cur);

Set up an initial state. The current string we're gonna test is a
random starting point; an external helper random_string_gen() will
do something like draw bytes from /dev/random and pick elements of a
string based on them.

	while (1) {

An infinite loop, which we'll only exit via last().

		$cur = crypt($cur, $cur);
		last if $lag[-1] eq $cur;

If the previous value of cur equals the result after we've fed it
through crypt(), then we're done.

		$cur = random_string_gen() and @lag=($cur) if $lag[0] eq $cur;

If the lag value, which advances along the sequence half the speed
of cur, should equal cur, then we've fallen into a loop; bail out,
reset the lag array, and start from a new random starting point.

		push @lag, $cur;

Otherwise remember this value; push it onto the lag queue, we'll be
getting to it by and by.

		$cur = crypt($cur, $cur);
		last if $lag[-1] eq $cur;
		$cur = random_string_gen() and @lag=($cur) if shift(@lag) eq $cur;

This is the same code we used to open the loop.

		if ($#lag > 10000) {
			$cur = random_string_gen();
			@lag = ($cur);
		} else {
			push @lag, $cur;
		}

And this differs from the mid-loop only in that we also check, and
if we've accumulated a lag queue of more than some large number (I
picked 10,000 out of the air) we toss the lag queue and restart our
search from a new randomly-chosen point. This is an attempt to keep
the lag queue from growing indefinitely out of control, if no fixed
point should be found.

-Bennett

PGP signature