Reduce memory allocation during itemization

Use the stack for more temporary allocations.

7 files changed, 105 insertions, 57 deletions

diff --git a/pango/break.c b/pango/break.c
index 58e039e5..ddef75f6 100644
--- a/pango/break.c
+++ b/pango/break.c
@@ -1862,6 +1862,9 @@ pango_get_log_attrs (const char    *text,
   g_return_if_fail (length == 0 || text != NULL);
   g_return_if_fail (log_attrs != NULL);
 
+  if (length < 0)
+    length = strlen (text);
+
   analysis.level = level;
 
   pango_default_break (text, length, &analysis, log_attrs, attrs_len);
diff --git a/pango/pango-bidi-type.c b/pango/pango-bidi-type.c
index a5a13a9a..8d4fb852 100644
--- a/pango/pango-bidi-type.c
+++ b/pango/pango-bidi-type.c
@@ -29,6 +29,7 @@
 
 #include "pango-bidi-type.h"
 #include "pango-utils.h"
+#include "pango-utils-private.h"
 
 #if FRIBIDI_MAJOR_VERSION >= 1
 #define USE_FRIBIDI_EX_API
@@ -117,8 +118,29 @@ pango_log2vis_get_embedding_levels (const gchar    *text,
 				    int             length,
 				    PangoDirection *pbase_dir)
 {
-  glong n_chars, i;
-  guint8 *embedding_levels_list;
+  int n_chars;
+  guint8 *embedding_levels;
+
+  if (length < 0)
+    length = strlen (text);
+
+  n_chars = (int)g_utf8_strlen (text, length);
+
+  embedding_levels = g_new (guint8, n_chars);
+
+  log2vis_get_embedding_levels (text, length, n_chars, pbase_dir, embedding_levels);
+
+  return embedding_levels;
+}
+
+void
+log2vis_get_embedding_levels (const gchar    *text,
+                              int             length,
+                              int             n_chars,
+                              PangoDirection *pbase_dir,
+                              guint8         *embedding_levels)
+{
+  glong i;
   const gchar *p;
   FriBidiParType fribidi_base_dir;
   FriBidiCharType *bidi_types;
@@ -152,18 +174,15 @@ pango_log2vis_get_embedding_levels (const gchar    *text,
       break;
     }
 
-  if (length < 0)
-    length = strlen (text);
-
-  n_chars = g_utf8_strlen (text, length);
+  g_assert (length >= 0);
+  g_assert (n_chars >= 0);
 
-  bidi_types = g_new (FriBidiCharType, n_chars);
+  bidi_types = g_alloca (sizeof (FriBidiCharType) * n_chars);
 #ifdef USE_FRIBIDI_EX_API
-  bracket_types = g_new (FriBidiBracketType, n_chars);
+  bracket_types = g_alloca (sizeof (FriBidiBracketType) * n_chars);
 #endif
-  embedding_levels_list = g_new (guint8, n_chars);
 
-  for (i = 0, p = text; p < text + length; p = g_utf8_next_char(p), i++)
+  for (i = 0, p = text; p < text + length; p = g_utf8_next_char (p), i++)
     {
       gunichar ch = g_utf8_get_char (p);
       FriBidiCharType char_type = fribidi_get_bidi_type (ch);
@@ -210,7 +229,7 @@ pango_log2vis_get_embedding_levels (const gchar    *text,
       {
         /* all LTR */
 	fribidi_base_dir = FRIBIDI_PAR_LTR;
-	memset (embedding_levels_list, 0, n_chars);
+	memset (embedding_levels, 0, n_chars);
 	goto resolved;
       }
     /* The case that all resolved levels will be RTL is much more complex.
@@ -230,7 +249,7 @@ pango_log2vis_get_embedding_levels (const gchar    *text,
       {
         /* all RTL */
 	fribidi_base_dir = FRIBIDI_PAR_RTL;
-	memset (embedding_levels_list, 1, n_chars);
+	memset (embedding_levels, 1, n_chars);
 	goto resolved;
       }
 
@@ -238,29 +257,22 @@ pango_log2vis_get_embedding_levels (const gchar    *text,
 #ifdef USE_FRIBIDI_EX_API
   max_level = fribidi_get_par_embedding_levels_ex (bidi_types, bracket_types, n_chars,
 						   &fribidi_base_dir,
-						   (FriBidiLevel*)embedding_levels_list);
+						   (FriBidiLevel*)embedding_levels);
 #else
   max_level = fribidi_get_par_embedding_levels (bidi_types, n_chars,
 						&fribidi_base_dir,
-						(FriBidiLevel*)embedding_levels_list);
+						(FriBidiLevel*)embedding_levels);
 #endif
 
   if (G_UNLIKELY(max_level == 0))
     {
       /* fribidi_get_par_embedding_levels() failed. */
-      memset (embedding_levels_list, 0, length);
+      memset (embedding_levels, 0, length);
     }
 
 resolved:
-  g_free (bidi_types);
-
-#ifdef USE_FRIBIDI_EX_API
-  g_free (bracket_types);
-#endif
 
   *pbase_dir = (fribidi_base_dir == FRIBIDI_PAR_LTR) ?  PANGO_DIRECTION_LTR : PANGO_DIRECTION_RTL;
-
-  return embedding_levels_list;
 }
 
 /**
diff --git a/pango/pango-context.c b/pango/pango-context.c
index ac59f3d8..fad11be0 100644
--- a/pango/pango-context.c
+++ b/pango/pango-context.c
@@ -31,6 +31,7 @@
 #include "pango-fontmap-private.h"
 #include "pango-script-private.h"
 #include "pango-emoji-private.h"
+#include "pango-utils-private.h"
 
 /**
  * PangoContext:
@@ -749,6 +750,7 @@ struct _ItemizeState
   PangoItem *item;
 
   guint8 *embedding_levels;
+  guint8 embedding_levels_[256];
   int embedding_end_offset;
   const char *embedding_end;
   guint8 embedding;
@@ -879,7 +881,7 @@ update_end (ItemizeState *state)
 }
 
 static gboolean
-width_iter_is_upright (gunichar ch)
+width_iter_is_upright_bsearch (gunichar ch)
 {
   /* https://www.unicode.org/Public/11.0.0/ucd/VerticalOrientation.txt
    * VO=U or Tu table generated by tools/gen-vertical-orientation-U-table.py.
@@ -913,28 +915,34 @@ width_iter_is_upright (gunichar ch)
     {0x1F000, 0x1F7FF}, {0x1F900, 0x1FA6F}, {0x20000, 0x2FFFD}, {0x30000, 0x3FFFD},
     {0xF0000, 0xFFFFD}, {0x100000, 0x10FFFD}
   };
-  static const int max = sizeof(upright) / sizeof(upright[0]);
-  int st = 0;
-  int ed = max;
 
-  if (ch < upright[0][0])
-    return FALSE;
+  int lower = 0;
+  int upper = G_N_ELEMENTS (upright);
 
-  while (st <= ed)
+  do
     {
-      int mid = (st + ed) / 2;
-      if (upright[mid][0] <= ch && ch <= upright[mid][1])
-        return TRUE;
+      int mid = (lower + upper) / 2;
+      if (ch < upright[mid][0])
+        upper = mid - 1;
+      else if (ch > upright[mid][1])
+        lower = mid + 1;
       else
-        if (upright[mid][0] <= ch)
-          st = mid + 1;
-        else
-          ed = mid - 1;
+        return TRUE;
     }
+  while (lower <= upper);
 
   return FALSE;
 }
 
+static inline gboolean
+width_iter_is_upright (gunichar ch)
+{
+  if (ch < 0x00A7)
+    return FALSE;
+
+  return width_iter_is_upright_bsearch (ch);
+}
+
 static void
 width_iter_next (PangoWidthIter *iter)
 {
@@ -952,7 +960,7 @@ width_iter_next (PangoWidthIter *iter)
       gunichar ch = g_utf8_get_char (iter->end);
 
       /* for zero width joiner */
-      if (ch == 0x200D)
+      if (G_UNLIKELY (ch == 0x200D))
         {
           iter->end = g_utf8_next_char (iter->end);
           met_joiner = TRUE;
@@ -960,7 +968,7 @@ width_iter_next (PangoWidthIter *iter)
         }
 
       /* ignore the upright check if met joiner */
-      if (met_joiner)
+      if (G_UNLIKELY (met_joiner))
         {
           iter->end = g_utf8_next_char (iter->end);
           met_joiner = FALSE;
@@ -1011,6 +1019,10 @@ itemize_state_init (ItemizeState               *state,
                     PangoAttrIterator          *cached_iter,
                     const PangoFontDescription *desc)
 {
+  int n_chars;
+
+  n_chars = (int) g_utf8_strlen (text + start_index, length);
+
   state->context = context;
   state->text = text;
   state->end = text + start_index + length;
@@ -1025,7 +1037,11 @@ itemize_state_init (ItemizeState               *state,
   /* First, apply the bidirectional algorithm to break
    * the text into directional runs.
    */
-  state->embedding_levels = pango_log2vis_get_embedding_levels (text + start_index, length, &base_dir);
+  if (n_chars < 256)
+    state->embedding_levels = state->embedding_levels_;
+  else
+    state->embedding_levels = g_new (guint8, n_chars);
+  log2vis_get_embedding_levels (text + start_index, length, n_chars, &base_dir, state->embedding_levels);
 
   state->embedding_end_offset = 0;
   state->embedding_end = text + start_index;
@@ -1076,7 +1092,7 @@ itemize_state_init (ItemizeState               *state,
                                &state->script_end, &state->script);
 
   width_iter_init (&state->width_iter, text + start_index, length);
-  _pango_emoji_iter_init (&state->emoji_iter, text + start_index, length);
+  _pango_emoji_iter_init (&state->emoji_iter, text + start_index, length, n_chars);
 
   if (state->emoji_iter.is_emoji)
     state->width_iter.end = MAX (state->width_iter.end, state->emoji_iter.end);
@@ -1128,6 +1144,7 @@ itemize_state_next (ItemizeState *state)
                                    &state->script_end, &state->script);
       state->changed |= SCRIPT_CHANGED;
     }
+
   if (state->run_end == state->emoji_iter.end)
     {
       _pango_emoji_iter_next (&state->emoji_iter);
@@ -1136,6 +1153,7 @@ itemize_state_next (ItemizeState *state)
       if (state->emoji_iter.is_emoji)
         state->width_iter.end = MAX (state->width_iter.end, state->emoji_iter.end);
     }
+
   if (state->run_end == state->width_iter.end)
     {
       width_iter_next (&state->width_iter);
@@ -1580,7 +1598,8 @@ itemize_state_process_run (ItemizeState *state)
 static void
 itemize_state_finish (ItemizeState *state)
 {
-  g_free (state->embedding_levels);
+  if (state->embedding_levels != state->embedding_levels_)
+    g_free (state->embedding_levels);
   if (state->free_attr_iter)
     pango_attr_iterator_destroy (state->attr_iter);
   _pango_script_iter_fini (&state->script_iter);
diff --git a/pango/pango-emoji-private.h b/pango/pango-emoji-private.h
index d5cbccf4..be7d8058 100644
--- a/pango/pango-emoji-private.h
+++ b/pango/pango-emoji-private.h
@@ -10,7 +10,7 @@
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library General Public
@@ -41,14 +41,16 @@ struct _PangoEmojiIter
   gboolean is_emoji;
 
   unsigned char *types;
+  unsigned  char types_[256];
   unsigned int n_chars;
   unsigned int cursor;
 };
 
 PangoEmojiIter *
 _pango_emoji_iter_init (PangoEmojiIter *iter,
-			const char     *text,
-			int             length);
+                        const char     *text,
+                        int             length,
+                        int             n_chars);
 
 gboolean
 _pango_emoji_iter_next (PangoEmojiIter *iter);
diff --git a/pango/pango-emoji.c b/pango/pango-emoji.c
index 334970d6..51acb626 100644
--- a/pango/pango-emoji.c
+++ b/pango/pango-emoji.c
@@ -210,14 +210,21 @@ typedef unsigned char *emoji_text_iter_t;
 
 PangoEmojiIter *
 _pango_emoji_iter_init (PangoEmojiIter *iter,
-			const char     *text,
-			int             length)
+                        const char     *text,
+                        int             length,
+                        int             n_chars)
 {
-  unsigned int n_chars = g_utf8_strlen (text, length);
-  unsigned char *types = g_malloc (n_chars);
+  unsigned char *types;
   unsigned int i;
   const char *p;
 
+  g_assert (length >= 0);
+
+  if (n_chars < 256)
+    types = iter->types_;
+  else
+    types = g_malloc (n_chars);
+
   p = text;
   for (i = 0; i < n_chars; i++)
   {
@@ -226,10 +233,7 @@ _pango_emoji_iter_init (PangoEmojiIter *iter,
   }
 
   iter->text_start = iter->start = iter->end = text;
-  if (length >= 0)
-    iter->text_end = text + length;
-  else
-    iter->text_end = text + strlen (text);
+  iter->text_end = text + length;
   iter->is_emoji = FALSE;
 
   iter->types = types;
@@ -244,7 +248,8 @@ _pango_emoji_iter_init (PangoEmojiIter *iter,
 void
 _pango_emoji_iter_fini (PangoEmojiIter *iter)
 {
-  g_free (iter->types);
+  if (iter->types != iter->types_)
+    g_free (iter->types);
 }
 
 gboolean
diff --git a/pango/pango-script.c b/pango/pango-script.c
index fc7c6332..e787a8de 100644
--- a/pango/pango-script.c
+++ b/pango/pango-script.c
@@ -100,11 +100,10 @@ _pango_script_iter_init (PangoScriptIter *iter,
 	                 const char      *text,
 			 int              length)
 {
+  g_assert (length >= 0);
+
   iter->text_start = text;
-  if (length >= 0)
-    iter->text_end = text + length;
-  else
-    iter->text_end = text + strlen (text);
+  iter->text_end = text + length;
 
   iter->script_start = text;
   iter->script_end = text;
@@ -140,6 +139,8 @@ PangoScriptIter *
 pango_script_iter_new (const char *text,
 		       int         length)
 {
+  if (length < 0)
+    length = strlen (text);
   return _pango_script_iter_init (g_slice_new (PangoScriptIter), text, length);
 }
 
diff --git a/pango/pango-utils-private.h b/pango/pango-utils-private.h
index 4087dc14..e8117411 100644
--- a/pango/pango-utils-private.h
+++ b/pango/pango-utils-private.h
@@ -54,6 +54,12 @@ const char *   pango_get_sysconf_subdirectory (void) G_GNUC_PURE;
 PANGO_DEPRECATED
 const char *   pango_get_lib_subdirectory (void) G_GNUC_PURE;
 
+void log2vis_get_embedding_levels (const gchar    *text,
+                                   int             length,
+                                   int             n_chars,
+                                   PangoDirection *pbase_dir,
+                                   guint8         *embedding_levels);
+
 G_END_DECLS
 
 #endif /* __PANGO_UTILS_PRIATE_H__ */