From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with archive (Exim 4.43) id 1NEkmO-0003JY-RT for mharc-grub-devel@gnu.org; Sun, 29 Nov 2009 09:29:36 -0500 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NEkmN-0003IC-K5 for grub-devel@gnu.org; Sun, 29 Nov 2009 09:29:35 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NEkmM-0003H4-Vl for grub-devel@gnu.org; Sun, 29 Nov 2009 09:29:35 -0500 Received: from [199.232.76.173] (port=47756 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NEkmM-0003H1-Pl for grub-devel@gnu.org; Sun, 29 Nov 2009 09:29:34 -0500 Received: from fg-out-1718.google.com ([72.14.220.153]:48886) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NEkmM-0004XG-2X for grub-devel@gnu.org; Sun, 29 Nov 2009 09:29:34 -0500 Received: by fg-out-1718.google.com with SMTP id l26so877798fgb.12 for ; Sun, 29 Nov 2009 06:29:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from :user-agent:mime-version:to:subject:x-enigmail-version:content-type; bh=1dR20FL9xfE0jgwyNnlyYpDhi9W9FWym4pcQn5yMdHY=; b=WvFLsxBaWf4nQxpLzV8EvGdHyv3//RQqyLNUEShurRszefh3K3xBVhvqsgqDPhNUr5 Tlu3Y/svYq1DUSB5rNcKkw1soM2oJeAmZlkDsnIbE17WyNoch4KZgjwEpwWKPTDGuxwZ R4R/PBgAS3ZS/P+/MmhUpbrqKQjTXSAyO0Tnw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:subject :x-enigmail-version:content-type; b=GQNyJa+xNeCJsEYGkoBTshSGpsLOaLaCkzxAhXwKMTX5K8KsXfrwCG3HiaEGWUkyfm sxhIuMh1cR/5Wzws1tPgCAkLGEVpX1Gw1sNH7HhfoljhGP4IYnGJundRvfjZdvb79WkC K3czG/lRlIc3Ep6FugWVZipWT0l7gtkc7JLlM= Received: by 10.87.73.28 with SMTP id a28mr3055095fgl.78.1259504972975; Sun, 29 Nov 2009 06:29:32 -0800 (PST) Received: from debian.bg45.phnet (130-55.76-83.cust.bluewin.ch [83.76.55.130]) by mx.google.com with ESMTPS id l19sm7739596fgb.3.2009.11.29.06.29.31 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sun, 29 Nov 2009 06:29:32 -0800 (PST) Message-ID: <4B12853E.70001@gmail.com> Date: Sun, 29 Nov 2009 15:29:18 +0100 From: =?UTF-8?B?VmxhZGltaXIgJ8+GLWNvZGVyL3BoY29kZXInIFNlcmJpbmVua28=?= User-Agent: Mozilla-Thunderbird 2.0.0.22 (X11/20091109) MIME-Version: 1.0 To: The development of GRUB 2 X-Enigmail-Version: 0.95.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="------------enigF46D3A8A5FD31B7580CCB318" X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 2) Subject: [PATCH] Faster glyph lookup by BMP index X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: The development of GNU GRUB List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 29 Nov 2009 14:29:35 -0000 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigF46D3A8A5FD31B7580CCB318 Content-Type: multipart/mixed; boundary="------------020404000404030605040302" This is a multi-part message in MIME format. --------------020404000404030605040302 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hello. Basic Multilingual Plane is range of Unicode characters in 0-65535 and it contains most of the characters needed by most of the languages of the world. By keeping an array with pointers to such characters at the cost of 128KiB per font we can almost instantenously lookup characters which are likely to be used in grub. Available in experimental --=20 Regards Vladimir '=CF=86-coder/phcoder' Serbinenko --------------020404000404030605040302 Content-Type: text/x-diff; name="bmpidx.diff" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="bmpidx.diff" =3D=3D=3D added file 'ChangeLog.bmpidx' --- ChangeLog.bmpidx 1970-01-01 00:00:00 +0000 +++ ChangeLog.bmpidx 2009-11-29 14:17:03 +0000 @@ -0,0 +1,9 @@ +2009-11-29 Vladimir Serbinenko + + Optimise glyph lookup by Basic Multilingual Plane lookup array. + + * font/font.c (struct grub_font): New member 'bmp_idx'. + (font_init): Initialise 'bmp_idx'. + (load_font_index): Fill 'bmp_idx'. + (find_glyph): Make inline. Use bmp_idx for BMP characters. + =3D=3D=3D modified file 'font/font.c' --- font/font.c 2009-07-20 17:37:37 +0000 +++ font/font.c 2009-11-29 13:24:58 +0000 @@ -58,6 +58,7 @@ struct grub_font short leading; grub_uint32_t num_chars; struct char_index_entry *char_index; + grub_uint16_t *bmp_idx; }; =20 /* Definition of font registry. */ @@ -180,6 +181,7 @@ font_init (grub_font_t font) font->descent =3D 0; font->num_chars =3D 0; font->char_index =3D 0; + font->bmp_idx =3D 0; } =20 /* Open the next section in the file. @@ -273,6 +275,14 @@ load_font_index (grub_file_t file, grub_ * sizeof (struct char_index_entry)); if (! font->char_index) return 1; + font->bmp_idx =3D grub_malloc (0x10000 * sizeof (grub_uint16_t)); + if (! font->bmp_idx) + { + grub_free (font->char_index); + return 1; + } + grub_memset (font->bmp_idx, 0xff, 0x10000 * sizeof (grub_uint16_t)); + =20 #if FONT_DEBUG >=3D 2 grub_printf("num_chars=3D%d)\n", font->num_chars); @@ -299,6 +309,9 @@ load_font_index (grub_file_t file, grub_ return 1; } =20 + if (entry->code < 0x10000) + font->bmp_idx[entry->code] =3D i; + last_code =3D entry->code; =20 /* Read storage flags byte. */ @@ -594,7 +607,7 @@ read_be_int16 (grub_file_t file, grub_in =20 /* Return a pointer to the character index entry for the glyph correspon= ding to the codepoint CODE in the font FONT. If not found, return zero. */ -static struct char_index_entry * +static inline struct char_index_entry * find_glyph (const grub_font_t font, grub_uint32_t code) { struct char_index_entry *table; @@ -602,8 +615,17 @@ find_glyph (const grub_font_t font, grub grub_size_t hi; grub_size_t mid; =20 - /* Do a binary search in `char_index', which is ordered by code point.= */ table =3D font->char_index; + + /* Use BMP index if possible. */ + if (code < 0x10000) + { + if (font->bmp_idx[code] =3D=3D 0xffff) + return 0; + return &table[font->bmp_idx[code]]; + } + + /* Do a binary search in `char_index', which is ordered by code point.= */ lo =3D 0; hi =3D font->num_chars - 1; =20 --------------020404000404030605040302-- --------------enigF46D3A8A5FD31B7580CCB318 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iF4EAREKAAYFAksShUUACgkQNak7dOguQgni9AD/WMjxUqpGWe4olcvGXs7neWca wrrXe4GJ5onniUVCD84A/2GWTIOdTlVxsXDQVw1xVX/3/mrHhAnTgIrfFWc6wsN6 =7b9D -----END PGP SIGNATURE----- --------------enigF46D3A8A5FD31B7580CCB318--