Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sat, 26 Mar 2011 05:21:34 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: pow64of32

Lukas,

On Thu, Mar 24, 2011 at 06:01:59PM +0100, ?ukasz Odzioba wrote:
> i was looking into the JtR sources

Great!

> and found that powering function
> implementation is not optimal. It is O(n), but we can do that in
> logarithmic time.

Yes, and the code in charset.c uses a slow sorting algorithm.  None of
this matters much.  These only affect the "--make-charset=..." option,
which is not performance critical, as long as it completes in a few
seconds.

I intend to re-work the incremental mode, at which point I might as well
either upgrade the 64-bit integer math stuff to 128-bit (since 64-bit
became insufficient for some uses lately) or move to floating-point
(except for the add32to64() call from status.c, which will need to stay
integer for precision).

> It's not a big deal but mayby code listed below, would be better (for
> the peace of mind).
> 
> void pow64of32(int64 *dst,unsigned int x,int n)
> {//O(logn)
>   int64 tmp={0,1};
>   while(n--){
>     if(n%2)
>       mul64by32(&tmp,x);
>     x*=x;
>     n/=2;
>   }
> }

Unfortunately, it's not that simple.  Even with three trivial bugs in
the code above fixed (see below), there's the issue with 32-bit overflow
on "x*=x;"  So we'd need to upgrade "x" to 64-bit as well, and then we
need a mul64by64(), which is not implemented currently.  Overall, I
think this peace of mind is not worth the added complexity.  We may
instead add a comment that these functions are not performance critical
and thus are simple rather than fast.

Test program, showing errors starting with "16 8" (the 32-bit overflow):

---
#include "math.h"

#include <string.h>
#include <stdio.h>

static void l_pow64of32(int64 *dst,unsigned int x,int n)
{//O(logn)
  int64 tmp={1,0};
  while(n){
    if(n%2)
      mul64by32(&tmp,x);
    x*=x;
    n/=2;
  }
  *dst = tmp;
}

int main(void)
{
	int64 y1, y2;
	unsigned int x, n;

	for (n = 0; n < 100; n++) {
		printf("n=%u\n", n);
		for (x = 0; x < 100; x++) {
			pow64of32(&y1, x, n);
			l_pow64of32(&y2, x, n);
			if (memcmp(&y1, &y2, sizeof(y1)))
				printf("%u %u\n", x, n);
		}
	}

	return 0;
}
---

That said, I appreciate you looking into the code and your proposal.

Thank you!

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ