mirror of
https://github.com/storytold/harfbuzz.git
synced 2026-11-19 05:51:05 +01:00
* [cache] Reject out-of-range keys on reads An empty entry can match an out-of-range key when the packed cache entry leaves storage bits unused. In the 256-entry binary coverage cache this reports glyph IDs 32512-32767 as NOT_COVERED, skipping Context/ChainContext format 2 substitutions and positioning. Apply the same key range check in get() as set(). Add regression coverage for spare-bit and full-width entries across all three storage sizes, with and without atomics. The new cache test fails before the fix and passes afterward, also with HB_TINY. All 28 GSUB/GPOS Context/ChainContext boundary cases pass. meson test -C build: 272 passed, 1 skipped, 0 failed. Fixes: https://github.com/harfbuzz/harfbuzz/issues/6418 Assisted-by: OpenAI Codex * [cache] Combine cache miss checks into one branch Fold the key range check into the existing miss condition using bitwise operations. XOR the stored and queried tags so their mismatch can be combined directly with key overflow and the empty entry check. Use a scalar empty-entry constant rather than casting through item_t, which creates temporary atomic objects in GCC builds. The binary, mapping, and cmap lookup probes now each have one conditional branch with GCC 15 and Clang 21 at -O2 on x86-64, compared with two or three in the initial fix. Testing: meson test -C build: 272 passed, 1 skipped, 0 failed. All 28 GSUB/GPOS Context/ChainContext boundary cases pass. The cache regression also passes with Clang and with HB_TINY. Assisted-by: OpenAI Codex
123 lines
4.1 KiB
C++
123 lines
4.1 KiB
C++
/*
|
|
* Copyright © 2012 Google, Inc.
|
|
*
|
|
* This is part of HarfBuzz, a text shaping library.
|
|
*
|
|
* Permission is hereby granted, without written agreement and without
|
|
* license or royalty fees, to use, copy, modify, and distribute this
|
|
* software and its documentation for any purpose, provided that the
|
|
* above copyright notice and the following two paragraphs appear in
|
|
* all copies of this software.
|
|
*
|
|
* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
|
|
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
|
|
* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
|
|
* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
|
|
* DAMAGE.
|
|
*
|
|
* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
|
|
* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
|
|
* FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
|
|
* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
|
|
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
|
|
*
|
|
* Google Author(s): Behdad Esfahbod
|
|
*/
|
|
|
|
#ifndef HB_CACHE_HH
|
|
#define HB_CACHE_HH
|
|
|
|
#include "hb.hh"
|
|
|
|
|
|
/* Implements a lockfree and thread-safe cache for int->int functions,
|
|
* using (optionally) _relaxed_ atomic integer operations.
|
|
*
|
|
* The cache is a fixed-size array of 16-bit or 32-bit integers,
|
|
* typically 256 elements.
|
|
*
|
|
* The key is split into two parts: the cache index (high bits)
|
|
* and the rest (low bits).
|
|
*
|
|
* The cache index is used to index into the array. The array
|
|
* member is a 16-bit or 32-bit integer that is used *both*
|
|
* to store the low bits of the key, and the value.
|
|
*
|
|
* The value is stored in the least significant bits of the integer.
|
|
* The low bits of the key are stored in the most significant bits
|
|
* of the integer.
|
|
*
|
|
* A cache hit is detected by comparing the low bits of the key
|
|
* with the high bits of the integer at the array position indexed
|
|
* by the high bits of the key. If they match, the value is extracted
|
|
* from the least significant bits of the integer and returned.
|
|
* Otherwise, a cache miss is reported.
|
|
*
|
|
* Cache operations (storage and retrieval) involve just a few
|
|
* arithmetic operations and a single memory access.
|
|
*/
|
|
|
|
template <unsigned int key_bits=16,
|
|
unsigned int value_bits=8 + 32 - key_bits,
|
|
unsigned int cache_bits=8,
|
|
bool thread_safe=true>
|
|
struct hb_cache_t
|
|
{
|
|
using item_t = typename std::conditional<thread_safe,
|
|
typename std::conditional<key_bits + value_bits - cache_bits <= 8,
|
|
hb_atomic_t<unsigned char>,
|
|
typename std::conditional<key_bits + value_bits - cache_bits <= 16,
|
|
hb_atomic_t<unsigned short>,
|
|
hb_atomic_t<unsigned int>>::type>::type,
|
|
typename std::conditional<key_bits + value_bits - cache_bits <= 8,
|
|
unsigned char,
|
|
typename std::conditional<key_bits + value_bits - cache_bits <= 16,
|
|
unsigned short,
|
|
unsigned int>::type>::type
|
|
>::type;
|
|
|
|
static_assert ((key_bits >= cache_bits), "");
|
|
static_assert ((key_bits + value_bits <= cache_bits + 8 * sizeof (item_t)), "");
|
|
|
|
static constexpr unsigned MAX_VALUE = (1u << value_bits) - 1;
|
|
|
|
hb_cache_t () { clear (); }
|
|
|
|
void clear ()
|
|
{
|
|
for (auto &v : values)
|
|
v = -1;
|
|
}
|
|
|
|
HB_HOT
|
|
bool get (unsigned int key, unsigned int *value) const
|
|
{
|
|
unsigned int k = key & ((1u<<cache_bits)-1);
|
|
unsigned int v = values[k];
|
|
constexpr unsigned int empty = (1ULL << (8 * sizeof (item_t))) - 1;
|
|
/* Combine overflow, tag mismatch, and empty checks into one branch. */
|
|
if ((key >> key_bits) |
|
|
((v >> value_bits) ^ (key >> cache_bits)) |
|
|
((key_bits + value_bits - cache_bits == 8 * sizeof (item_t)) && (v == empty)))
|
|
return false;
|
|
*value = v & ((1u<<value_bits)-1);
|
|
return true;
|
|
}
|
|
|
|
HB_HOT
|
|
void set (unsigned int key, unsigned int value)
|
|
{
|
|
if (unlikely ((key >> key_bits) || (value >> value_bits)))
|
|
return; /* Overflows */
|
|
unsigned int k = key & ((1u<<cache_bits)-1);
|
|
unsigned int v = ((key>>cache_bits)<<value_bits) | value;
|
|
values[k] = v;
|
|
}
|
|
|
|
private:
|
|
item_t values[1u<<cache_bits];
|
|
};
|
|
|
|
|
|
#endif /* HB_CACHE_HH */
|