
Date: Sat, 26 Mar 2011 05:21:34 +0300 From: Solar Designer <solar@...nwall.com> To: johndev@...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 "makecharset=..." option, which is not performance critical, as long as it completes in a few seconds. I intend to rework the incremental mode, at which point I might as well either upgrade the 64bit integer math stuff to 128bit (since 64bit became insufficient for some uses lately) or move to floatingpoint (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 32bit overflow on "x*=x;" So we'd need to upgrade "x" to 64bit 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 32bit 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