CODEWITHSUNDEEP
phpbit-shift
Mason Ticehurst
Mason Ticehurst

Reputation: 484

PHP Bit shift Unexpected Results/Overflow?

In a small script I'm working on I use the follow functions:

function ROTR( $x, $t ){
    return( $x >> $t ) | ( $x << ( 32 - $t ) );
}

function Σ0( $x ){
    echo("SIG INPUT: " . $x . "<br>" );

    $s0 = ROTR( $x, 2 );
    $s1 = ROTR( $x, 13 );
    $s2 = ROTR( $x, 22 );

    echo( "SIGMA0 2: " . $s0 . "<br>" );
    echo( "SIGMA0 13: " . $s1 . "<br>" );
    echo( "SIGMA0 22: " . $s2 . "<br>" );

    return ( $s0 ^ $s1 ^ $s2 );
}

These are both defined in this document on pages 5 & 10

I apply the following and get these results:

Σ0( 1779033703 )
> SIG INPUT: 1779033703
> SIGMA0 2: -628983399
> SIGMA0 13: 859525199
> SIGMA0 22: 664378792

The input is perfectly normal, as well as the last two (SIGMA0 13 and SIGMA0 22) however the ROTR( 1779033703, 2 ) shift appears to overflow the 2^31-1 signed int limit.

The value I am expecting is 3665983897, which I was able to obtain in VB.Net with:

' THIS SCRIPT HAS INTEGER OVERFLOW CHECKS DISABLED!
Function RotRight(x As UInt32, count As UInt32) As UInt32
    Dim t5 = x \ (2 ^ count)
    Dim t6 = x * (2 ^ (32 - count))

    Return (t5 Or t6)
End Function

Function EP0(x As UInt32) As UInt32
    Dim t7 = RotRight(x, 2)
    Dim t8 = RotRight(x, 13)
    Dim t9 = RotRight(x, 22)

    Return (t7 Xor t8 Xor t9)
End Function

>

SIG INPUT: 1779033703
SIGMA0 2: 3665983897
SIGMA0 13: 859525199
SIGMA0 22: 664378792

I've read that there are several ways to circumvent the overflow issue by treating the integer as a string with the gmp library, but I have not found a working method.

So far, I've tried casting the integer as a string and then using gmp_init( string ) to convert the string into a GMP number, but the library does not appear to support bit shifting.

PS: I am using a 32bit build of PHP (I'm on Windows using XAMPP which does not support 64bit yet)

Upvotes: 3

Views: 132

Answers (1)

Nick
Nick

Reputation: 147196

Because you have a 32-bit PHP installation, and PHP does not support unsigned integers, you will need to use a library like GMP to resolve your problem. Unfortunately GMP does not have bit-shifting arithmetic functions, however you can simulate them using division and multiplication:

function ROTR( $x, $t ){
    return gmp_and(gmp_or(gmp_div($x, 1 << $t), gmp_mul($x, 1 << (32 - $t))), "4294967295");
}

function Σ0( $x ){
    echo("SIG INPUT: " . $x . "\n" );

    $s0 = ROTR( $x, 2 );
    $s1 = ROTR( $x, 13 );
    $s2 = ROTR( $x, 22 );

    echo( "SIGMA0 2: " . gmp_strval($s0, 10) . "\n" );
    echo( "SIGMA0 13: " . gmp_strval($s1, 10) . "\n" );
    echo( "SIGMA0 22: " . gmp_strval($s2, 10) . "\n" );

    return ( gmp_xor($s0, gmp_xor($s1, $s2)) );
}

Σ0( 1779033703 );

Note that because GMP is arbitrary precision, you need to mask the output of ROTR to restrict it to 32 bits by bitwise and'ing it with (1 << 32) - 1.

Output:

SIG INPUT: 1779033703
SIGMA0 2: 3665983897
SIGMA0 13: 859525199
SIGMA0 22: 664378792

Here's a demo on 3v4l

Upvotes: 1

Related Questions