PHP бит сдвиг Неожиданные результаты / переполнение?

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

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 limit.

Значение я ожидаю является 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, который еще не поддерживает 64-битную версию)

3

Решение

Поскольку у вас установлена ​​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

Другие решения

Других решений пока нет …