Skip to content

pack: fix 0-case in implementation of Brensenham’s algorithm

Graphics Gems I §II.8 gives the definition of the sgn function as:

function sgn (x: int) : int;
begin return if x > 0 then 1 else –1; endfunc;

Its reference code appears to have incorrectly implemented this as:

  /* take binary sign of a, either -1, or 1 if >= 0 */
  #define SGN(a)      (((a)<0) ? -1 : 0)

The errata following the first edition notes a bug with this:

Serious errors (ones your compiler cannot or may not catch):

p. 630: …
Change SGN macro to (i.e. change positive condition result to "1"):
#define SGN(a) (((a)<0) ? -1 : 1)

This corrected version seems to have been copied into Graphviz. However neither Graphviz developers nor the Graphics Gems editors seemed to notice that the corrected macro still does not correctly implement the pseudocode it corresponds to. In the x == 0 case, the pseudocode returns -1 while the macro was returning 1.

A comment in lib/dotgen/compound.c suggests that developers may have been seeing symptoms of this but did not identify the root cause:

  /* The following functions are derived from pp. 411-415 (pp. 791-795)
   * of Graphics Gems. In the code there, they use a SGN function to
   * count crossings. This doesn't seem to handle certain special cases,
   * as when the last point is on the line. It certainly didn't work
   * for us when we used int values; see bug 145. We needed to use CMP instead.

Merge request reports