php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Doc Bug #66780 weird sorting behaviour due to overflow in custom comparison function
Submitted: 2014-02-26 10:34 UTC Modified: 2016-08-27 18:39 UTC
From: eric dot deruiter at amplixs dot com Assigned: cmb (profile)
Status: Closed Package: Arrays related
PHP Version: 5.5.9 OS:
Private report: No CVE-ID: None
 [2014-02-26 10:34 UTC] eric dot deruiter at amplixs dot com
Description:
------------
It seems that a user defined comparison function should return an 32 integer, if you return anything bigger / smaller this will cause weird sorting behaviour due to integer overflows.

If you write custom comparison functions it is common practise to subtract 2 numeric values to determine which one is larger. And as numeric values can be 64 bit in PHP, I would expect this to work correctly.

Test script:
---------------
$items = [1073741824,1,18014398509481984,8589934592,256,16777216,4,1024,17592186044416,32768,2199023255552,1125899906842624,34359738368,137438953472,1152921504606846976,4611686018427387904,8796093022208,140737488355328,2147483648,4398046511104,36028797018963968,9007199254740992,131072,17179869184,72057594037927936,512,68719476736,144115188075855872,288230376151711744,2048,281474976710656,9.2233720368548E+18,16,128,549755813888,536870912,8388608,70368744177664,2251799813685248,262144,4294967296,134217728,32,524288,65536,1099511627776,4503599627370496,2,2305843009213693952,35184372088832,67108864,8,33554432,2097152,562949953421312,4194304,4096,576460752303423488,274877906944,268435456,16384,8192,64,1048576];

usort($items, function($a, $b) 
  { 
    return $a - $b; 
  });

print_r($items);

usort($items, function($a, $b) 
  {
    $res = $a - $b; 
    if ($res < 0) 
      return -1; 
    else if ($res > 0) 
      return 1; 
    else 
      return 0; 
  });
  
print_r($items);

Expected result:
----------------
I would expect both comparison functions to have the exact same behaviour, resulting in a ascending sorted array.


Actual result:
--------------
The first array is not sorted as expected: the tail of the array looks like this:

    [47] => 288230376151711744
    [48] => 576460752303423488
    [49] => 1152921504606846976
    [50] => 2305843009213693952
    [51] => 4611686018427387904
    [52] => 9.2233720368548E+18
    [53] => 1
    [54] => 2
    [55] => 4
    [56] => 8
    [57] => 16
    [58] => 32
    [59] => 128
    [60] => 256
    [61] => 512
    [62] => 1024
    [63] => 2048



Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2016-08-26 18:44 UTC] cmb@php.net
-Status: Open +Status: Verified -Assigned To: +Assigned To: cmb
 [2016-08-26 18:44 UTC] cmb@php.net
This issue has been fixed as of PHP 7.0.0[1], but as it is a bug,
that should probably be backported to PHP 5.6.

[1] <https://3v4l.org/sWNi7>
 [2016-08-26 18:54 UTC] cmb@php.net
-Type: Bug +Type: Documentation Problem
 [2016-08-26 18:54 UTC] cmb@php.net
The culprit is that compare_func_t is expected to return an
int[1]. Changing this would break API compatibility, so I'm
switching to doc-bug.

[1] <https://github.com/php/php-src/blob/PHP-5.6.25/Zend/zend_hash.h#L47>
 [2016-08-27 18:39 UTC] cmb@php.net
Automatic comment from SVN on behalf of cmb
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=339940
Log: Fix #66780: weird sorting behaviour due to overflow in custom comparison function
 [2016-08-27 18:39 UTC] cmb@php.net
-Status: Verified +Status: Closed
 [2020-02-07 06:06 UTC] phpdocbot@php.net
Automatic comment on behalf of cmb
Revision: http://git.php.net/?p=doc/en.git;a=commit;h=4760df15c147fa3793e8d05fca4795ba9162839f
Log: Fix #66780: weird sorting behaviour due to overflow in custom comparison function
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Sun May 05 14:01:31 2024 UTC