lut_inverse_interp16: interpolate degenerate zeros in TRC curves

third_party/qcms/src/transform_util.c

 //  qcms
 //  Copyright (C) 2009 Mozilla Foundation
 //
 // Permission is hereby granted, free of charge, to any person obtaining
 // a copy of this software and associated documentation files (the "Software"),
 // to deal in the Software without restriction, including without limitation
 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
 // and/or sell copies of the Software, and to permit persons to whom the Software
 // is furnished to do so, subject to the following conditions:
 //
@@ skipping 316 matching lines @@
 
         // Does the curve belong to this case?
         if (NumZeroes > 1 || NumPoles > 1)
         {
                 int a, b, sample;
 
                 // Identify if value fall downto 0 or FFFF zone
                 if (Value == 0) return 0;
                 // if (Value == 0xFFFF) return 0xFFFF;
                 sample = (length-1) * ((double) Value * (1./65535.));
-                if (LutTable[sample] == 0)
-                    return 0;
                 if (LutTable[sample] == 0xffff)
                     return 0xffff;
 
                 // else restrict to valid zone
 
                 a = ((NumZeroes-1) * 0xFFFF) / (length-1);
                 b = ((length-1 - NumPoles) * 0xFFFF) / (length-1);
 
                 l = a - 1;
                 r = b + 1;
 
                 // Ensure a valid binary search range
 
                 if (l < 1)
                     l = 1;
                 if (r > 0x10000)
                     r = 0x10000;
+
+                // If the search range is inverted due to degeneracy,
+                // deem LutTable non-invertible in this search range.
+                // Refer to https://bugzil.la/1132467
+
+                if (r <= l)
+                    return 0;
         }
 
         // Seems not a degenerated case... apply binary search
 
         while (r > l) {
 
                 x = (l + r) / 2;
 
                 res = (int) lut_interp_linear16((uint16_fract_t) (x-1), LutTable, length);
 
                 if (res == Value) {
 
                     // Found exact match.
 
                     return (uint16_fract_t) (x - 1);
                 }
 
                 if (res > Value) r = x - 1;
                 else l = x + 1;
         }
 
         // Not found, should we interpolate?
 
+        // Get surrounding nodes
 
-        // Get surrounding nodes
+        assert(x >= 1);
 
         val2 = (length-1) * ((double) (x - 1) / 65535.0);
 
         cell0 = (int) floor(val2);
         cell1 = (int) ceil(val2);
 
+        assert(cell0 >= 0);
+        assert(cell1 >= 0);
+        assert(cell0 < length);
+        assert(cell1 < length);
+
         if (cell0 == cell1) return (uint16_fract_t) x;
 
         y0 = LutTable[cell0] ;
         x0 = (65535.0 * cell0) / (length-1); 
 
         y1 = LutTable[cell1] ;
         x1 = (65535.0 * cell1) / (length-1);
 
         a = (y1 - y0) / (x1 - x0);
         b = y0 - a * x0;
@@ skipping 251 matching lines @@
         14,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,
         13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     13,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,
         24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     24,     13
 };