PHP Bit shift неожиданные результаты/переполнение?

В небольшом скрипте, над которым я работаю, я использую следующие функции: 

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 );
}

Они оба определены в этом документе на страницах 5 и 10

Я применяю следующее И получаю следующие результаты: 

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

Вход совершенно нормальный, как и два последних (SIGMA0 13 и SIGMA0 22), однако сдвиг ROTR( 1779033703, 2 ), по-видимому, переполняет предел 2^31-1 со знаком int.

Значение, которое я ожидаю , является 3665983897, которое я смог получить в VB.Net с:

' 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

Я читал, что есть несколько способов обойти проблему переполнения, обрабатывая целое число как строку с помощью библиотеки gmp, но я не нашел рабочего метода.

До сих пор я пытался привести целое число в виде строки, а затем с помощью gmp_init( string ) преобразовать строку в число GMP, но библиотека, похоже, не поддерживает сдвиг битов.

PS: я использую 32-битную сборку PHP (я на Windows использую XAMPP, который не поддерживает 64bit пока)

1 3
php bit-shift

1 ответ:

Поскольку у вас 32-разрядная установка PHP, а PHP не поддерживает целые числа без знака, вам нужно будет использовать библиотеку GMP для решения вашей проблемы. К сожалению, GMP не имеет арифметических функций сдвига битов, однако их можно моделировать с помощью деления и умножения: 

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 );

Обратите внимание, что поскольку GMP является произвольной точностью, вам нужно замаскировать выход ROTR, чтобы ограничить его до 32 бит побитовым and'ing с помощью (1 << 32) - 1.

Вывод: 

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

Вот демо на 3v4l

1