[Qemu-devel] [Bug 1655700] [NEW] disas/libvixl/vixl/invalset.h: possible dodgy code in binary search ?

[Qemu-devel] [Bug 1655700] [NEW] disas/libvixl/vixl/invalset.h: possible dodgy code in binary search ?

[dcb]

Public bug reported:


[qemu/disas/libvixl/vixl/invalset.h:442]: (style) Array index 'low' is used before limits check.

Source code is

    while (!IsValid(elements[low]) && (low < high)) ++low;

Also:

qemu/disas/libvixl/vixl/invalset.h:450]: (style) Array index 'middle' is
used before limits check.

The source code is

   while (!IsValid(elements[high]) && (low < high)) --high;

Mind you, these lines of code look similar but didn't get reported:

    while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
    while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;

Given that binary search is notoriously tricky to get correct and a standard C library routine
I am puzzled as to why the standard library routine didn't get used, with of course a custom
comparison function.

** Affects: qemu
     Importance: Undecided
         Status: New

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1655700

Title:
  disas/libvixl/vixl/invalset.h: possible dodgy code in binary search ?

Status in QEMU:
  New

Bug description:
  
  [qemu/disas/libvixl/vixl/invalset.h:442]: (style) Array index 'low' is used before limits check.

  Source code is

      while (!IsValid(elements[low]) && (low < high)) ++low;

  Also:

  qemu/disas/libvixl/vixl/invalset.h:450]: (style) Array index 'middle'
  is used before limits check.

  The source code is

     while (!IsValid(elements[high]) && (low < high)) --high;

  Mind you, these lines of code look similar but didn't get reported:

      while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
      while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;

  Given that binary search is notoriously tricky to get correct and a standard C library routine
  I am puzzled as to why the standard library routine didn't get used, with of course a custom
  comparison function.

To manage notifications about this bug go to:
https://bugs.launchpad.net/qemu/+bug/1655700/+subscriptions

[Qemu-devel] [Bug 1655700] Re: disas/libvixl/vixl/invalset.h: possible dodgy code in binary search ?

[Peter Maydell]

That doesn't look like a bounds check to me, so I think your checker is
producing false positives.

libvixl is third-party code in any case, so stylistic questions are
better directed to them upstream. But I think the difference between
this code and a standard binary search is (as the comment says) that it
ignores invalid elements in the array.


** Changed in: qemu
       Status: New => Invalid

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1655700

Title:
  disas/libvixl/vixl/invalset.h: possible dodgy code in binary search ?

Status in QEMU:
  Invalid

Bug description:
  
  [qemu/disas/libvixl/vixl/invalset.h:442]: (style) Array index 'low' is used before limits check.

  Source code is

      while (!IsValid(elements[low]) && (low < high)) ++low;

  Also:

  qemu/disas/libvixl/vixl/invalset.h:450]: (style) Array index 'middle'
  is used before limits check.

  The source code is

     while (!IsValid(elements[high]) && (low < high)) --high;

  Mind you, these lines of code look similar but didn't get reported:

      while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
      while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;

  Given that binary search is notoriously tricky to get correct and a standard C library routine
  I am puzzled as to why the standard library routine didn't get used, with of course a custom
  comparison function.

To manage notifications about this bug go to:
https://bugs.launchpad.net/qemu/+bug/1655700/+subscriptions