From 45d6f29f15f1d2323bcaa2498aed23ff0c8a1567 Mon Sep 17 00:00:00 2001
From: Behdad Esfahbod <behdad@behdad.org>
Date: Sat, 30 Jul 2011 14:44:30 -0400
Subject: [PATCH] [Indic] Reorder matras

Number of failing shape-complex tests goes from 125 down to 94.

Next: Add Ra handling and it's fair to say we kinda support Indic :).
---
 src/hb-ot-shape-complex-indic.cc | 29 +++++++++++++++++++++++++++--
 src/hb-ot-shape-normalize.cc     | 26 ++++++++++----------------
 src/hb-private.hh                | 36 ++++++++++++++++++++++++++++++------
 3 files changed, 67 insertions(+), 24 deletions(-)

diff --git a/src/hb-ot-shape-complex-indic.cc b/src/hb-ot-shape-complex-indic.cc
index 0579500..95f3f1f 100644
--- a/src/hb-ot-shape-complex-indic.cc
+++ b/src/hb-ot-shape-complex-indic.cc
@@ -63,8 +63,6 @@ enum indic_position_t {
   POS_ABOVE,
   POS_BELOW,
   POS_POST,
-
-  POS_INHERIT /* For Halant, Nukta, ZWJ, ZWNJ */
 };
 
 /* Categories used in IndicSyllabicCategory.txt from UCD */
@@ -365,6 +363,14 @@ _hb_ot_shape_complex_setup_masks_indic (hb_ot_map_t *map, hb_buffer_t *buffer)
   }
 }
 
+static int
+compare_indic_order (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb)
+{
+  int a = pa->indic_position();
+  int b = pb->indic_position();
+
+  return a < b ? -1 : a == b ? 0 : +1;
+}
 
 static void
 found_consonant_syllable (const hb_ot_map_t *map, hb_buffer_t *buffer, hb_mask_t *mask_array,
@@ -454,6 +460,25 @@ found_consonant_syllable (const hb_ot_map_t *map, hb_buffer_t *buffer, hb_mask_t
    */
 
 
+  /* Reorder characters */
+
+  for (i = start; i < base; i++)
+    buffer->info[i].indic_position() = POS_PRE;
+  buffer->info[base].indic_position() = POS_BASE;
+
+  /* Attach ZWJ, ZWNJ, nukta, and halant to previous char to move with them. */
+  for (i = start + 1; i < end; i++)
+    if ((FLAG (buffer->info[i].indic_category()) &
+	 (FLAG (OT_ZWNJ) | FLAG (OT_ZWJ) | FLAG (OT_N) | FLAG (OT_H))))
+      buffer->info[i].indic_position() = buffer->info[i - 1].indic_position();
+
+  /* We do bubble-sort, skip malicious clusters attempts */
+  if (end - start > 20)
+    return;
+
+  /* Sit tight, rock 'n roll! */
+  hb_bubble_sort (buffer->info + start, end - start, compare_indic_order);
+
   /* Setup masks now */
 
   /* Pre-base */
diff --git a/src/hb-ot-shape-normalize.cc b/src/hb-ot-shape-normalize.cc
index 8ed7a67..e2fd91c 100644
--- a/src/hb-ot-shape-normalize.cc
+++ b/src/hb-ot-shape-normalize.cc
@@ -147,6 +147,15 @@ decompose_multi_char_cluster (hb_ot_shape_context_t *c,
     decompose_current_glyph (c, FALSE);
 }
 
+static int
+compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb)
+{
+  unsigned int a = pa->combining_class();
+  unsigned int b = pb->combining_class();
+
+  return a < b ? -1 : a == b ? 0 : +1;
+}
+
 void
 _hb_ot_shape_normalize (hb_ot_shape_context_t *c)
 {
@@ -216,22 +225,7 @@ _hb_ot_shape_normalize (hb_ot_shape_context_t *c)
       continue;
     }
 
-    unsigned int k = end - i - 1;
-    do {
-      hb_glyph_info_t *pinfo = buffer->info + i;
-      unsigned int new_k = 0;
-
-      for (unsigned int j = 0; j < k; j++)
-	if (pinfo[j].combining_class() > pinfo[j+1].combining_class()) {
-	  hb_glyph_info_t t;
-	  t = pinfo[j];
-	  pinfo[j] = pinfo[j + 1];
-	  pinfo[j + 1] = t;
-
-	  new_k = j;
-	}
-      k = new_k;
-    } while (k);
+    hb_bubble_sort (buffer->info + i, end - i, compare_combining_class);
 
     i = end;
   }
diff --git a/src/hb-private.hh b/src/hb-private.hh
index b5277a5..23fc0af 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -568,12 +568,9 @@ struct hb_auto_trace_t<0> {
 				   const char *message) {}
 };
 
-HB_BEGIN_DECLS
-
 
 /* Misc */
 
-HB_END_DECLS
 
 /* Pre-mature optimization:
  * Checks for lo <= u <= hi but with an optimization if lo and hi
@@ -590,13 +587,40 @@ hb_in_range (T u, T lo, T hi)
     return lo <= u && u <= hi;
 }
 
-HB_BEGIN_DECLS
-
 
-/* Useful for set-operations on small enums */
+/* Useful for set-operations on small enums.
+ * For example, for testing "x ∈ {x1, x2, x3}" use:
+ * (FLAG(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3)))
+ */
 #define FLAG(x) (1<<(x))
 
 
+template <typename T> inline void
+hb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
+{
+  if (unlikely (!len))
+    return;
+
+  unsigned int k = len - 1;
+  do {
+    unsigned int new_k = 0;
+
+    for (unsigned int j = 0; j < k; j++)
+      if (compar (&array[j], &array[j+1]) > 0) {
+        T t;
+	t = array[j];
+	array[j] = array[j + 1];
+	array[j + 1] = t;
+
+	new_k = j;
+      }
+    k = new_k;
+  } while (k);
+}
+
+
+HB_BEGIN_DECLS
+
 HB_END_DECLS
 
 #endif /* HB_PRIVATE_HH */
-- 
2.7.4