bug#41544: 26.3; Possible incorrect results from color-distance

[Mattias Engdegård]

[CC:ing Tom Tromey, who used colour-distance in css-mode]

Ah, where to begin. Clearly a distance metric ought to be symmetric; as you 
note, this is easily fixed by replacing the shift by division, which has the 
extra benefit of not relying on the implementation-defined behaviour when 
right-shifting negative values in C. The extra cost is negligible.

Looking at it a bit closer, it seems a waste to use full 16 bit colour channels 
only to shift out 8 of them before getting started. I presume this was done 
partly in order to follow the Riedersma metric more closely, and partly to stay 
within 32 bit numbers (I note that the code uses the C 'long' type, which is 
almost always a mistake). Using 64-bit arithmetic costs us next to nothing 
today, and this solves several problems.

But a darker cloud is on the horizon. Since the Emacs implementation omits the 
square root of the result, it no longer satisfies the triangle inequality, 
which is even more fundamental for distance metrics than symmetry. It is good 
enough for comparison of distances, but they can no longer be added, since it's 
not a true metric.

In fact, it seems that users of color_distance are confused as well: a comment 
says

  /* If the distance (as returned by color_distance) between two colors is
     less than this, then they are considered the same, for determining
     whether a color is supported or not.  The range of values is 0-65535.  */

  #define TTY_SAME_COLOR_THRESHOLD  10000

which is a lie, since color_distance can return values well above 65535.
Some uses are very questionable, given that it's the square of a metric:

      int delta_delta
        = (color_distance (&fg_std_color, &bg_std_color)
           - color_distance (&fg_tty_color, &bg_tty_color));
      if (delta_delta > TTY_SAME_COLOR_THRESHOLD
          || delta_delta < -TTY_SAME_COLOR_THRESHOLD)

So what to do? Best would be to do the arithmetic on the entire channel values 
and take the square root at the end; the cost is nothing to worry about on 
hardware less than 30 years old. Some constants used for comparison would need 
to be adjusted: the above-mentioned TTY_SAME_COLOR_THRESHOLD (10000), 
face-near-same-threshold (30000), and a number in css--contrasty-color 
(292485).  At least the last should probably use the luma norm originally 
proposed instead (see bug#25525); the use of colour-distance here cannot be 
right.