There are several places where the rotation yields garbage according to ANSI
C definition when called with 0 bit position argument.
diff -Pur linux_reference/drivers/char/random.c linux/drivers/char/random.c
--- linux_reference/drivers/char/random.c Wed Jul 19 00:58:13 2000
+++ linux/drivers/char/random.c Sun Dec 17 22:42:59 2000
@@ -411,7 +411,7 @@
#if (!defined (__i386__))
extern inline __u32 rotate_left(int i, __u32 word)
{
- return (word << i) | (word >> (32 - i));
+ return (word << i) | (word >> ((-i)&31));
}
#else
@@ -857,7 +857,7 @@
#define K3 0x8F1BBCDCL /* Rounds 40-59: sqrt(5) * 2^30 */
#define K4 0xCA62C1D6L /* Rounds 60-79: sqrt(10) * 2^30 */
-#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
+#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( (- n)&31 ) ) )
#define subRound(a, b, c, d, e, f, k, data) \
( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
@@ -1087,7 +1087,7 @@
/* This is the central step in the MD5 algorithm. */
#define MD5STEP(f, w, x, y, z, data, s) \
- ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x )
+ ( w += f(x, y, z) + data, w = w<<s | w>>((-s)&31), w += x )
/*
* The core of the MD5 algorithm, this alters an existing MD5 hash to
@@ -1883,7 +1883,7 @@
* Rotation is separate from addition to prevent recomputation
*/
#define ROUND(f, a, b, c, d, x, s) \
- (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s)))
+ (a += f(b, c, d) + x, a = (a << s) | (a >> ((-s)&31)))
#define K1 0
#define K2 013240474631UL
#define K3 015666365641UL
Clock
Karel Kulhavy wrote:
>
> There are several places where the rotation yields garbage according to ANSI
> C definition when called with 0 bit position argument.
>
> diff -Pur linux_reference/drivers/char/random.c linux/drivers/char/random.c
> --- linux_reference/drivers/char/random.c Wed Jul 19 00:58:13 2000
> +++ linux/drivers/char/random.c Sun Dec 17 22:42:59 2000
> @@ -411,7 +411,7 @@
> #if (!defined (__i386__))
> extern inline __u32 rotate_left(int i, __u32 word)
> {
> - return (word << i) | (word >> (32 - i));
> + return (word << i) | (word >> ((-i)&31));
>
If the calling code guarantees 0 < i < 32, then the patch is unnecessary.
In the kernel I have to hand (2.2.6), grepping gives:
r->input_rotate = j & 31 ;
and then both calls to the function use r->input_rotate as the first argument,
so the guarantee from higher level code seems to be 0 <= i < 32, in which case
your patch seems needed.
On the other hand, why not put the &= inside the function with something
like:
extern inline __u32 rotate_left(int i, __u32 word)
{
switch( i &= 31 ) { /* cheap version of i %= 32 */
case 0 :
return word ;
default :
return (word << i) | (word >> (32 - i)) ;
}
or some faster alternative along the lines of:
{
i &= 31 ;
return( i ? ((word << i) | (word >> (32 - i))) : word ) ;
This works right for any i. Yours fails for i >= 32 unless you make it:
return (word << (i&31)) | (word >> ((-i)&31));
Whichever way is fastest is fine, but I'd advocate doing the range
manipulation inside the function in any case. Why trust the caller?
If the code is maintained or modified, you're almost guaranteed to
be called with bad argumantes in some version.