From 1d2015598cc7a9fca4b39186273e3519a88e80c7 Mon Sep 17 00:00:00 2001

From: Zhang Boyang <zhangboyang.id@gmail.com>

Date: Sun, 14 Aug 2022 18:09:38 +0800

Subject: [PATCH 06/12] font: Fix integer underflow in binary search of char

 index

If search target is less than all entries in font->index then "hi"

variable is set to -1, which translates to SIZE_MAX and leads to errors.

This patch fixes the problem by replacing the entire binary search code

with the libstdc++'s std::lower_bound() implementation.

Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com>

Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>

---

 grub-core/font/font.c | 40 ++++++++++++++++++++++------------------

 1 file changed, 22 insertions(+), 18 deletions(-)

diff --git a/grub-core/font/font.c b/grub-core/font/font.c

index e4cb0d867..abd412a5e 100644

--- a/grub-core/font/font.c

+++ b/grub-core/font/font.c

@@ -688,12 +688,12 @@ read_be_int16 (grub_file_t file, grub_int16_t * value)

 static inline struct char_index_entry *

 find_glyph (const grub_font_t font, grub_uint32_t code)

 {

-  struct char_index_entry *table;

-  grub_size_t lo;

-  grub_size_t hi;

-  grub_size_t mid;

+  struct char_index_entry *table, *first, *end;

+  grub_size_t len;

   table = font->char_index;

+  if (table == NULL)

+    return NULL;

   /* Use BMP index if possible.  */

   if (code < 0x10000 && font->bmp_idx)

@@ -706,25 +706,29 @@ find_glyph (const grub_font_t font, grub_uint32_t code)

        */

     }

-  /* Do a binary search in `char_index', which is ordered by code point.  */

-  lo = 0;

-  hi = font->num_chars - 1;

-

-  if (!table)

-    return 0;

+  /*

+   * Do a binary search in char_index which is ordered by code point.

+   * The code below is the same as libstdc++'s std::lower_bound().

+   */

+  first = table;

+  len = font->num_chars;

+  end = first + len;

-  while (lo <= hi)

+  while (len > 0)

     {

-      mid = lo + (hi - lo) / 2;

-      if (code < table[mid].code)

-	hi = mid - 1;

-      else if (code > table[mid].code)

-	lo = mid + 1;

+      grub_size_t half = len >> 1;

+      struct char_index_entry *middle = first + half;

+

+      if (middle->code < code)

+	{

+	  first = middle + 1;

+	  len = len - half - 1;

+	}

       else

-	return &table[mid];

+	len = half;

     }

-  return 0;

+  return (first < end && first->code == code) ? first : NULL;

 }

 /* Get a glyph for the Unicode character CODE in FONT.  The glyph is loaded

-- 

2.33.5