Bug 1132467 - Adjust qcms lut inverse binary search of non monotonic TRC. r=jrmuizel
authorBenoit Girard <b56girard@gmail.com>
Thu, 04 Jun 2015 19:30:52 -0400
changeset 275732 83d5d84f1092a1871c5aceba5a391eb413fd5f9f
parent 275681 87c493cc1166c19ea9aaf29665ffc5de15965850
child 275733 3d5f3ef8315024cb63f1874ed3ecd5182b63e989
push id3220
push userbzhao@mozilla.com
push dateMon, 06 Jul 2015 03:31:09 +0000
reviewersjrmuizel
bugs1132467
milestone42.0a1
Bug 1132467 - Adjust qcms lut inverse binary search of non monotonic TRC. r=jrmuizel
gfx/qcms/moz.build
gfx/qcms/transform_util.c
gfx/qcms/transform_util.h
gfx/tests/gtest/TestQcms.cpp
gfx/tests/gtest/moz.build
--- a/gfx/qcms/moz.build
+++ b/gfx/qcms/moz.build
@@ -12,17 +12,17 @@ EXPORTS += [
 SOURCES += [
     'chain.c',
     'iccread.c',
     'matrix.c',
     'transform.c',
     'transform_util.c',
 ]
 
-FINAL_LIBRARY = 'gkmedias'
+FINAL_LIBRARY = 'xul'
 
 if CONFIG['GNU_CC']:
     CFLAGS += ['-Wno-missing-field-initializers']
 
 use_sse1 = False
 use_sse2 = False
 use_altivec = False
 if '86' in CONFIG['OS_TEST']:
--- a/gfx/qcms/transform_util.c
+++ b/gfx/qcms/transform_util.c
@@ -258,57 +258,65 @@ uint16_fract_t lut_inverse_interp16(uint
             return 0;
 
         NumPoles = 0;
         while (LutTable[length-1- NumPoles] == 0xFFFF && NumPoles < length-1)
                         NumPoles++;
 
         // Does the curve belong to this case?
         if (NumZeroes > 1 || NumPoles > 1)
-        {               
+        {
                 int a, b;
 
-                // Identify if value fall downto 0 or FFFF zone             
+                // Identify if value fall downto 0 or FFFF zone
                 if (Value == 0) return 0;
-               // if (Value == 0xFFFF) return 0xFFFF;
+                // if (Value == 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;
+                if (NumZeroes > 1) {
+                        a = ((NumZeroes-1) * 0xFFFF) / (length-1);
+                        l = a - 1;
+                }
+                if (NumPoles > 1) {
+                        b = ((length-1 - NumPoles) * 0xFFFF) / (length-1);
+                        r = b + 1;
+                }
+        }
+
+        if (r <= l) {
+                // If this happens LutTable is not invertible
+                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. 
-                    
+                    // 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
-        
+
+        assert(x >= 1);
+
         val2 = (length-1) * ((double) (x - 1) / 65535.0);
 
         cell0 = (int) floor(val2);
         cell1 = (int) ceil(val2);
            
         if (cell0 == cell1) return (uint16_fract_t) x;
 
         y0 = LutTable[cell0] ;
--- a/gfx/qcms/transform_util.h
+++ b/gfx/qcms/transform_util.h
@@ -84,10 +84,20 @@ static inline float u8Fixed8Number_to_fl
 float *build_input_gamma_table(struct curveType *TRC);
 struct matrix build_colorant_matrix(qcms_profile *p);
 void build_output_lut(struct curveType *trc,
                       uint16_t **output_gamma_lut, size_t *output_gamma_lut_length);
 
 struct matrix matrix_invert(struct matrix mat);
 qcms_bool compute_precache(struct curveType *trc, uint8_t *output);
 
+// Tested by GTest
+#ifdef  __cplusplus
+extern "C" {
+#endif
+
+uint16_fract_t lut_inverse_interp16(uint16_t Value, uint16_t LutTable[], int length);
+
+#ifdef  __cplusplus
+}
+#endif
 
 #endif
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/TestQcms.cpp
@@ -0,0 +1,168 @@
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+#include "gtest/gtest.h"
+#include "gmock/gmock.h"
+
+#include "mozilla/ArrayUtils.h"
+#include "qcms.h"
+#include "transform_util.h"
+
+const size_t allGBSize = 1 * 256 * 256 * 4;
+static unsigned char* createAllGB() {
+  unsigned char* buff = (unsigned char*)malloc(allGBSize);
+  int pos = 0;
+  for (int r = 0; r < 1; r++) { // Skip all R values for speed
+    for (int g = 0; g < 256; g++) {
+      for (int b = 0; b < 256; b++) {
+        buff[pos * 4 + 0] = r;
+        buff[pos * 4 + 1] = g;
+        buff[pos * 4 + 2] = b;
+        buff[pos * 4 + 3] = 0x80;
+        pos++;
+      }
+    }
+  }
+
+  return buff;
+}
+
+TEST(GfxQcms, Identity) {
+  // XXX: This means that we can't have qcms v2 unit test
+  //      without changing the qcms API.
+  qcms_enable_iccv4();
+
+  qcms_profile* input_profile = qcms_profile_sRGB();
+  qcms_profile* output_profile = qcms_profile_sRGB();
+
+  EXPECT_FALSE(qcms_profile_is_bogus(input_profile));
+  EXPECT_FALSE(qcms_profile_is_bogus(output_profile));
+
+  const qcms_intent intent = QCMS_INTENT_DEFAULT;
+  qcms_data_type input_type = QCMS_DATA_RGBA_8;
+  qcms_data_type output_type = QCMS_DATA_RGBA_8;
+
+  qcms_transform* transform = qcms_transform_create(input_profile, input_type,
+                                                    output_profile, output_type,
+                                                    intent);
+
+  unsigned char *data_in = createAllGB();;
+  unsigned char *data_out = (unsigned char*)malloc(allGBSize);
+  qcms_transform_data(transform, data_in, data_out, allGBSize / 4);
+
+  qcms_profile_release(input_profile);
+  qcms_profile_release(output_profile);
+  qcms_transform_release(transform);
+
+  free(data_in);
+  free(data_out);
+}
+
+TEST(GfxQcms, LutInverseCrash) {
+  uint16_t lutTable1[] = {
+    0x0000, 0x0000, 0x0000, 0x8000, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+  };
+  uint16_t lutTable2[] = {
+    0xFFF0, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
+  };
+
+  // Crash/Assert test
+  lut_inverse_interp16((uint16_t)5, lutTable1, (int)mozilla::ArrayLength(lutTable1));
+  lut_inverse_interp16((uint16_t)5, lutTable2, (int)mozilla::ArrayLength(lutTable2));
+}
+
+TEST(GfxQcms, LutInverse) {
+  // mimic sRGB_v4_ICC mBA Output
+  //
+  //       XXXX
+  //      X
+  //     X
+  // XXXX
+  uint16_t value;
+  uint16_t lutTable[256];
+
+  for (int i = 0; i < 20; i++) {
+    lutTable[i] = 0;
+  }
+
+  for (int i = 20; i < 200; i++) {
+    lutTable[i] = (i - 20) * 0xFFFF / (200 - 20);
+  }
+
+  for (int i = 200; i < (int)mozilla::ArrayLength(lutTable); i++) {
+    lutTable[i] = 0xFFFF;
+  }
+
+  for (uint16_t i = 0; i < 65535; i++) {
+    lut_inverse_interp16(i, lutTable, (int)mozilla::ArrayLength(lutTable));
+  }
+
+  // Lookup the interesting points
+
+  value = lut_inverse_interp16(0, lutTable, (int)mozilla::ArrayLength(lutTable));
+  EXPECT_LE(value, 20 * 256);
+
+  value = lut_inverse_interp16(1, lutTable, (int)mozilla::ArrayLength(lutTable));
+  EXPECT_GT(value, 20 * 256);
+
+  value = lut_inverse_interp16(65535, lutTable, (int)mozilla::ArrayLength(lutTable));
+  EXPECT_LT(value, 201 * 256);
+}
+
+TEST(GfxQcms, LutInverseNonMonotonic) {
+  // Make sure we behave sanely for non monotic functions
+  //   X  X  X
+  //  X  X  X
+  // X  X  X
+  uint16_t lutTable[256];
+
+  for (int i = 0; i < 100; i++) {
+    lutTable[i] = (i - 0) * 0xFFFF / (100 - 0);
+  }
+
+  for (int i = 100; i < 200; i++) {
+    lutTable[i] = (i - 100) * 0xFFFF / (200 - 100);
+  }
+
+  for (int i = 200; i < 256; i++) {
+    lutTable[i] = (i - 200) * 0xFFFF / (256 - 200);
+  }
+
+  for (uint16_t i = 0; i < 65535; i++) {
+    lut_inverse_interp16(i, lutTable, (int)mozilla::ArrayLength(lutTable));
+  }
+
+  // Make sure we don't crash, hang or let sanitizers do their magic
+}
--- a/gfx/tests/gtest/moz.build
+++ b/gfx/tests/gtest/moz.build
@@ -11,16 +11,17 @@ UNIFIED_SOURCES += [
     'TestAsyncPanZoomController.cpp',
     'TestBufferRotation.cpp',
     'TestColorNames.cpp',
     'TestCompositor.cpp',
     'TestGfxPrefs.cpp',
     'TestGfxWidgets.cpp',
     'TestLayers.cpp',
     'TestMoz2D.cpp',
+    'TestQcms.cpp',
     'TestRect.cpp',
     'TestRegion.cpp',
     'TestSkipChars.cpp',
     # Hangs on linux in ApplyGdkScreenFontOptions
     #'gfxFontSelectionTest.cpp',
     'TestTextures.cpp',
     # Test works but it doesn't assert anything
     #'gfxTextRunPerfTest.cpp',
@@ -38,15 +39,16 @@ UNIFIED_SOURCES += [ '/gfx/2d/unittest/%
 ]]
 
 include('/ipc/chromium/chromium-config.mozbuild')
 
 LOCAL_INCLUDES += [
     '/gfx/2d',
     '/gfx/2d/unittest',
     '/gfx/layers',
+    '/gfx/qcms',
 ]
 
 FINAL_LIBRARY = 'xul-gtest'
 
 CXXFLAGS += CONFIG['MOZ_CAIRO_CFLAGS']
 
 FAIL_ON_WARNINGS = True