mORMot Open Source

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

FastFindInt64Sorted hangs on 32-bit build

Test code:

uses
  SysUtils,
  mORMot,
  SynCommons;

procedure DoTest;
var
  I, J: Integer;
  VLen: Integer;
  VArr: TIDDynArray;
begin
  VLen := 3;
  SetLength(VArr, VLen);
  for I := 0 to VLen - 1 do begin
    VArr[I] := I;
  end;
 J := FastFindInt64Sorted(PInt64Array(VArr), VLen-1, 2); // <-- hangs
end;

Previous worked version FastFindInt64Sorted:

function FastFindInt64Sorted(P: PInt64Array; R: PtrInt; const Value: Int64): PtrInt; overload;
var L: PtrInt;
    cmp: Int64;
begin
  L := 0;
  if 0<=R then
  repeat
    result := (L + R) shr 1;
    cmp := P^[result]-Value;
    if cmp=0 then
      exit;
    if cmp<0 then
      L := result + 1 else
      R := result - 1;
  until (L > R);
  result := -1
end;

Current, bugged version (infinite loop):

function FastFindInt64Sorted(P: PInt64Array; R: PtrInt; const Value: Int64): PtrInt; overload;
var L: PtrInt;
begin
  L := 0;
  if 0<=R then
  repeat
    result := (L + R) shr 1;
    {$ifdef CPUX86} // circumvent Int64 comparison slowness
    result := SortDynArrayInt64(P^[result],Value);
    if result=0 then
      exit else
    if result <0 then
    {$else}
    if P^[result]=Value then
      exit else
    if P^[result]<Value then
    {$endif}
      L := result + 1 else
      R := result - 1;
  until (L > R);
  result := -1
end;

I use Delphi 10.2 and x86 build for test.

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

Re: FastFindInt64Sorted hangs on 32-bit build

Fix:

function FastFindInt64Sorted(P: PInt64Array; R: PtrInt; const Value: Int64): PtrInt; overload;
var L: PtrInt;
    cmp: Integer;
begin
  L := 0;
  if 0<=R then
  repeat
    result := (L + R) shr 1;
    {$ifdef CPUX86} // circumvent Int64 comparison slowness
    cmp := SortDynArrayInt64(P^[result],Value);
    if cmp=0 then
      exit else
    if cmp<0 then
    {$else}
    if P^[result]=Value then
      exit else
    if P^[result]<Value then
    {$endif}
      L := result + 1 else
      R := result - 1;
  until (L > R);
  result := -1
end;

Last edited by zed (2017-11-20 16:09:36)

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,659

Website

Re: FastFindInt64Sorted hangs on 32-bit build

Nice catch!

Please check https://synopse.info/fossil/info/f9bee556f8