From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with archive (Exim 4.43) id 1LWHXS-0002Gc-9O for mharc-grub-devel@gnu.org; Sun, 08 Feb 2009 16:50:06 -0500 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LWHXQ-0002FT-9G for grub-devel@gnu.org; Sun, 08 Feb 2009 16:50:04 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LWHXN-0002Df-Pq for grub-devel@gnu.org; Sun, 08 Feb 2009 16:50:02 -0500 Received: from [199.232.76.173] (port=58684 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LWHXN-0002DT-NB for grub-devel@gnu.org; Sun, 08 Feb 2009 16:50:01 -0500 Received: from gateway05.websitewelcome.com ([67.18.21.3]:49856) by monty-python.gnu.org with smtp (Exim 4.60) (envelope-from ) id 1LWHXN-0003Ry-60 for grub-devel@gnu.org; Sun, 08 Feb 2009 16:50:01 -0500 Received: (qmail 21916 invoked from network); 8 Feb 2009 22:07:28 -0000 Received: from gator297.hostgator.com (74.53.228.114) by gateway05.websitewelcome.com with SMTP; 8 Feb 2009 22:07:28 -0000 Received: from [67.185.177.95] (port=34995 helo=localhost) by gator297.hostgator.com with esmtpsa (TLSv1:AES128-SHA:128) (Exim 4.69) (envelope-from ) id 1LWHXG-000712-7t for grub-devel@gnu.org; Sun, 08 Feb 2009 15:49:54 -0600 Date: Sun, 8 Feb 2009 13:49:53 -0800 From: Colin D Bennett To: grub-devel@gnu.org Message-ID: <20090208134953.00aef328@gibibit.com> X-Mailer: Claws Mail 3.7.0 (GTK+ 2.14.7; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: multipart/signed; boundary="Sig_/dy=WhEs=QKNw4Nd5ZmVF.w9"; protocol="application/pgp-signature"; micalg=PGP-SHA1 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - gator297.hostgator.com X-AntiAbuse: Original Domain - gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - gibibit.com X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Subject: [PATCH] Faster text rendering by optimizing font glyph lookup X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: The development of GRUB 2 List-Id: The development of GRUB 2 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 08 Feb 2009 21:50:04 -0000 --Sig_/dy=WhEs=QKNw4Nd5ZmVF.w9 Content-Type: multipart/mixed; boundary="MP_/eXjLke6v7Nii=buZDR+bE00" --MP_/eXjLke6v7Nii=buZDR+bE00 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline This patch greatly=E2=80=94*tremendously*, even, if higher-numbered Unicode characters are used=E2=80=94speeds up retrieving a glyph for a particular Unicode character. This makes text rendering in general much faster. My text benchmark shows the new text rendering speed is somewhere from 2.6x to 31x of the previous speed. Basically, PFF2 font files are now required to have the character index ordered in ascending order of code point. Fonts created by 'grub-mkfont' already satisfy this requirement. Fonts created by my old Java 'fonttool' do not, and cannot be used any longer. The font loader verifies that fonts fulfill the character ordering requirement, refusing to load invalid fonts, but the primary change is in the 'find_glyph()' function, which now uses a binary search rather than a linear search to find the glyph. Regards, Colin --MP_/eXjLke6v7Nii=buZDR+bE00 Content-Type: text/x-patch Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename=font-optimization.patch =3D=3D=3D modified file 'ChangeLog' --- ChangeLog 2009-02-04 10:52:25 +0000 +++ ChangeLog 2009-02-08 21:46:42 +0000 @@ -1,3 +1,14 @@ +2009-02-08 Colin D Bennett + + Optimized font character lookup using binary search instead of linear + search. Fonts now are required to have the character index ordered by + code point. + + * font/font.c (load_font_index): Verify that fonts have ordered + character indices. + (find_glyph): Use binary search instead of linear search to find a + character in a font. + 2009-02-04 Felix Zielcke =20 util/getroot.c (grub_util_get_grub_dev): Add support for /dev/mdNpN and =3D=3D=3D modified file 'font/font.c' --- font/font.c 2009-01-19 17:09:53 +0000 +++ font/font.c 2009-02-08 19:50:58 +0000 @@ -249,6 +249,7 @@ grub_font *font) { unsigned i; + grub_uint32_t last_code; =20 #if FONT_DEBUG >=3D 2 grub_printf("load_font_index(sect_length=3D%d)\n", sect_length); @@ -277,6 +278,8 @@ grub_printf("num_chars=3D%d)\n", font->num_chars); #endif =20 + last_code =3D 0; + /* Load the character index data from the file. */ for (i =3D 0; i < font->num_chars; i++) { @@ -287,6 +290,17 @@ return 1; entry->code =3D grub_be_to_cpu32 (entry->code); =20 + /* Verify that characters are in ascending order. */ + if (i !=3D 0 && entry->code <=3D last_code) + { + grub_error (GRUB_ERR_BAD_FONT, + "Font characters not in ascending order: %u <=3D %u", + entry->code, last_code); + return 1; + } + + last_code =3D entry->code; + /* Read storage flags byte. */ if (grub_file_read (file, (char *) &entry->storage_flags, 1) !=3D 1) return 1; @@ -583,15 +597,25 @@ static struct char_index_entry * find_glyph (const grub_font_t font, grub_uint32_t code) { - grub_uint32_t i; - grub_uint32_t len =3D font->num_chars; - struct char_index_entry *table =3D font->char_index; - - /* Do a linear search. */ - for (i =3D 0; i < len; i++) + struct char_index_entry *table; + grub_size_t lo; + grub_size_t hi; + grub_size_t mid; + + /* Do a binary search in `char_index', which is ordered by code point. = */ + table =3D font->char_index; + lo =3D 0; + hi =3D font->num_chars - 1; + + while (lo <=3D hi) { - if (table[i].code =3D=3D code) - return &table[i]; + mid =3D lo + (hi - lo) / 2; + if (code < table[mid].code) + hi =3D mid - 1; + else if (code > table[mid].code) + lo =3D mid + 1; + else + return &table[mid]; } =20 return 0; --MP_/eXjLke6v7Nii=buZDR+bE00-- --Sig_/dy=WhEs=QKNw4Nd5ZmVF.w9 Content-Type: application/pgp-signature; name=signature.asc Content-Disposition: attachment; filename=signature.asc -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.9 (GNU/Linux) iEYEARECAAYFAkmPU4UACgkQokx8fzcGbYcvYQCdG6jJLYaEvAav3KCv7jw/QGJX lxsAn1Xo+KcCyCtFILhOUeTQVWViOZGU =bnUc -----END PGP SIGNATURE----- --Sig_/dy=WhEs=QKNw4Nd5ZmVF.w9--