From 16f792a7ff8f42595624e34be132355515c0ee46 Mon Sep 17 00:00:00 2001 From: Ryan Harrison Date: Wed, 31 Jan 2018 20:48:34 +0000 Subject: Remove handrolled bsearch from FGAS_GetUnicodeBitField BUG=pdfium:798 Change-Id: I054db94b53fbfabdf5dd860e951bef9c53177ad1 Reviewed-on: https://pdfium-review.googlesource.com/24830 Reviewed-by: dsinclair Commit-Queue: Ryan Harrison --- xfa/fgas/font/fgas_fontutils.cpp | 33 +++++++++++++++++---------------- 1 file changed, 17 insertions(+), 16 deletions(-) diff --git a/xfa/fgas/font/fgas_fontutils.cpp b/xfa/fgas/font/fgas_fontutils.cpp index 2cf56ce7ca..b4adaa85bd 100644 --- a/xfa/fgas/font/fgas_fontutils.cpp +++ b/xfa/fgas/font/fgas_fontutils.cpp @@ -1868,22 +1868,23 @@ const FGAS_FontInfo g_XFAFontsMap[] = { } // namespace -const FGAS_FONTUSB* FGAS_GetUnicodeBitField(wchar_t wUnicode) { - int32_t iEnd = sizeof(g_FXGdiFontUSBTable) / sizeof(FGAS_FONTUSB) - 1; - ASSERT(iEnd >= 0); - - int32_t iStart = 0; - int32_t iMid; - do { - iMid = (iStart + iEnd) / 2; - const FGAS_FONTUSB& usb = g_FXGdiFontUSBTable[iMid]; - if (wUnicode < usb.wStartUnicode) - iEnd = iMid - 1; - else if (wUnicode > usb.wEndUnicode) - iStart = iMid + 1; - else - return &usb; - } while (iStart <= iEnd); +const FGAS_FONTUSB* FGAS_GetUnicodeBitField(wchar_t unicode) { + // This search is trying to find the entry where the unicode character falls + // bewtween start and end. std::upper_bound needs to be used here instead of + // lower_bound, because they return the first value that meets the + // requirement, as though they are linearly searching. For lower_bound this + // means the first element less then the value, and for upper_bound this means + // the first element greater then the value. Since the entries are sorted in + // ascending order, the correct entry is the first one with an end greater, + // aka after, the value. + auto* result = std::upper_bound( + std::begin(g_FXGdiFontUSBTable), std::end(g_FXGdiFontUSBTable), unicode, + [](const wchar_t unicode, const FGAS_FONTUSB& iter) { + return iter.wEndUnicode > unicode; + }); + if (result != std::end(g_FXGdiFontUSBTable) && + result->wStartUnicode <= unicode && result->wEndUnicode >= unicode) + return result; return nullptr; } -- cgit v1.2.3