[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20110326022134.GC15508@openwall.com>
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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
