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

From: Mattias Engdegård <[email-masked]>
Date: Thu, 28 May 2020 19:31:51 +0200

[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.