#562 Inconsistent results from qsort callback

[Yury Gribov]

Hi,

qsort callback CompareEdges may return invalid result when arguments are swapped. Such bugs may causes inconsistent order or even crashes in some qsort implementations (https://bugzilla.samba.org/show_bug.cgi?id=3959).

The issue has been detected when running standard testsuite under SortChecker:
gravity[3808]: qsort: comparison function is not symmetric (comparison function 0x49a250 (/home/yugr/build/graphicsmagick-1.3.23/Magick++/demo/gravity+0x49a250), called from 0x49b771 (/home/yugr/build/graphicsmagick-1.3.23/Magick++/demo/gravity+0x49b771), cmdline is "./gravity")

Closer examination in debugger reveals that swapping order of operands does not cause output negation as required by qsort:

(gdb) p CompareEdges(polygon_info->edges + 0, polygon_info->edges + 1)
$1 = -1
(gdb) p CompareEdges(polygon_info->edges + 1, polygon_info->edges + 0)
$2 = -1

(gdb) p polygon_info->edges[0]
$3 = {bounds = {x1 = 300, y1_magick = 100, x2 = 300, y2 = 500}, scanline = -1, points = 0x1fb4ee0, number_points = 2, direction = 1, highwater = 0, ghostline = 0}
(gdb) p polygon_info->edges[1]
$4 = {bounds = {x1 = 300, y1_magick = 100, x2 = 300, y2 = 500}, scanline = -1, points = 0x1fb4ff0, number_points = 2, direction = 0, highwater = 0, ghostline = 1}

[Bob Friesenhahn]

Sending to Gregory Wolfe since this is a render.c issue.

[Gregory J Wolfe]

I have looked at the current source code but not yet come up with a fix. The problem is that for the test case you showed above, function CompareEdges() should return 0 (i.e., identical items), but the current code always wants to return -1 or 1 (either the first item comes first, or the second item comes first). If the two items are identical (or parallel), the current code always returns -1.

Having only been working with the GM code base for a few months, I do not yet know what the side effects would be if CompareEdges() returned 0 for identical items. More study/testing is needed.

[Gregory J Wolfe]

This problem has been fixed by change set 0b84e4687682, dated 5/30/2018.

The modified code uses several additional criteria to determine the relative order of the two edges, returning 0 (edges are "equal") only if the first segments of each edge are exactly the same.

Thanks for your detailed analysis.