[Git][freetype/freetype][hdmx-advances] [truetype] Binary search through `hdmx` records.

[Alexei Podtelezhnikov (@apodtele)]

Alexei Podtelezhnikov pushed to branch hdmx-advances at FreeType / FreeType

Commits:

• de70a401
  by Alexei Podtelezhnikov at 2021-12-01T10:28:35-05:00

  [truetype] Binary search through `hdmx` records.
  
  The `hdmx` table is supposed to be sorted by ppem size, which
  enables binary search.  We also drop the check for the sufficient
  length of the record because it is now enforced when the table
  is loaded.
  
  * src/truetype/ttpload.c (tt_face_load_hdmx): Prudently sort records.
  (tt_face_get_device_metrics): Implement binary search to retrieve
  advances.
  

1 changed file:

• src/truetype/ttpload.c

Changes:

src/truetype/ttpload.c

---

...	...	@@ -498,6 +498,14 @@
498	498	}
499	499
500	500
	501	+ FT_COMPARE_DEF( int )
	502	+ compare_ppem( const void* a,
	503	+ const void* b )
	504	+ {
	505	+ return *(FT_Byte*)a - *(FT_Byte*)b;
	506	+ }
	507	+
	508	+
501	509	/**************************************************************************
502	510	*
503	511	* @Function:
...	...	@@ -577,8 +585,10 @@
577	585	if ( FT_QNEW_ARRAY( face->hdmx_record_sizes, num_records ) )
578	586	goto Fail;
579	587
580		- /* XXX: We do not check if the records are sorted by ppem */
581		- /* and cannot use binary search later. */
	588	+ /* The records must be already sorted by ppem but it does not */
	589	+ /* hurt to make sure so that the binary search works later. */
	590	+ ft_qsort( p, num_records, record_size, compare_ppem );
	591	+
582	592	for ( nn = 0; nn < num_records; nn++ )
583	593	{
584	594	if ( p + record_size > limit )
...	...	@@ -619,27 +629,36 @@
619	629	/**************************************************************************
620	630	*
621	631	* Return the advance width table for a given pixel size if it is found
622		- * in the font's `hdmx' table (if any).
	632	+ * in the font's `hdmx' table (if any). The records must be sorted for
	633	+ * the binary search to work properly.
623	634	*/
624	635	FT_LOCAL_DEF( FT_Byte* )
625	636	tt_face_get_device_metrics( TT_Face face,
626	637	FT_UInt ppem,
627	638	FT_UInt gindex )
628	639	{
629		- FT_UInt nn;
	640	+ FT_UInt min = 0;
	641	+ FT_UInt max = face->hdmx_record_count;
	642	+ FT_UInt mid;
630	643	FT_Byte* result = NULL;
631	644	FT_ULong record_size = face->hdmx_record_size;
632	645	FT_Byte* record = FT_OFFSET( face->hdmx_table, 8 );
633	646
634	647
635		- for ( nn = 0; nn < face->hdmx_record_count; nn++ )
636		- if ( face->hdmx_record_sizes[nn] == ppem )
	648	+ while ( min < max )
	649	+ {
	650	+ mid = ( min + max ) >> 1;
	651	+
	652	+ if ( face->hdmx_record_sizes[mid] > ppem )
	653	+ max = mid;
	654	+ else if ( face->hdmx_record_sizes[mid] < ppem )
	655	+ min = mid + 1;
	656	+ else
637	657	{
638		- gindex += 2;
639		- if ( gindex < record_size )
640		- result = record + nn * record_size + gindex;
	658	+ result = record + mid * record_size + gindex + 2;
641	659	break;
642	660	}
	661	+ }
643	662
644	663	return result;
645	664	}

—
View it on GitLab.
You're receiving this email because of your account on gitlab.freedesktop.org. If you'd like to receive fewer emails, you can adjust your notification settings.