PHP Bit shift Unexpected Results/Overflow?

Question

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)

could you attach the output for each of this from your vb.net code t7 = RotRight(x, 2) t8 = RotRight(x, 13) t9 = RotRight(x, 22) — Rinsad Ahmed
– Rinsad Ahmed, Commented Sep 28, 2018 at 0:25
@RinsadAhmed Sorry, I forgot to include that. I've edited the question with those details. Thanks :) — Mason Ticehurst
– Mason Ticehurst, Commented Sep 28, 2018 at 0:41
@RinsadAhmed "Divides one operand by another and returns an integer result" tutorialspoint.com/vb.net/vb.net_operators.htm — Mason Ticehurst
– Mason Ticehurst, Commented Sep 28, 2018 at 0:42
"but the library does not appear to support bit shifting" well then you're going to need to either multiply or divide by powers of two. — Sammitch
– Sammitch, Commented Sep 28, 2018 at 1:06

Nick · Accepted Answer · 2018-09-28 02:21:04Z

1

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

edited Sep 28, 2018 at 2:21

answered Sep 28, 2018 at 1:32

Nick

147k23 gold badges67 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Mason Ticehurst Over a year ago

Perhaps I am still doing something wrong here :( I can confirm that $x is passed as an integer. Both $g and $x are the same number value when Σ0 is ran (the gmp_init returns an object, but the whole number portion is the same). This time around (I've copied the exact same functions for both) I get SIG INPUT: 1779033703 SIGMA0 2: 1910222893661452697

Nick Over a year ago

1910222893661452697 is the value you get when you use 64-bit arithmetic. The masking in ROTR (the outer gmp_and with (1 << 32) - 1 should make that impossible. Note that the assignment to $g was unnecessary and I have edited it out.

Nick Over a year ago

I've added a demo link on 34vl.org

Mason Ticehurst Over a year ago

I am now fairy confident it is something wrong with my PHP installation or perhaps being x86 is altering my results. Practically every online IDE I found that supports GMP (including the example you have provided) works. However, on my local x86 PHP server, I get a result as if the number has not been masked. Very strange indeed. Regardless, I very much appreciate the help!

Nick Over a year ago

Sorry, I'm an idiot. Because your system is 32 bits it can't represent (1<<32). I've edited the code with a string value of (1<<32)-1 i.e. 4294967295, that should work for you. I've updated the demo link as well.

Collectives™ on Stack Overflow

PHP Bit shift Unexpected Results/Overflow?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related