Home | History | Annotate | Download | only in fonts 
      1 /*
      2  * Copyright (C) 2012 Apple Inc. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions
      6  * are met:
      7  * 1. Redistributions of source code must retain the above copyright
      8  *    notice, this list of conditions and the following disclaimer.
      9  * 2. Redistributions in binary form must reproduce the above copyright
     10  *    notice, this list of conditions and the following disclaimer in the
     11  *    documentation and/or other materials provided with the distribution.
     12  *
     13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
     14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
     17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
     21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     24  */
     25 
     26 #ifndef WidthCache_h
     27 #define WidthCache_h
     28 
     29 #include "platform/text/TextRun.h"
     30 #include "wtf/Forward.h"
     31 #include "wtf/HashFunctions.h"
     32 #include "wtf/HashSet.h"
     33 #include "wtf/HashTableDeletedValueType.h"
     34 #include "wtf/StringHasher.h"
     35 
     36 namespace WebCore {
     37 
     38 struct GlyphOverflow;
     39 
     40 class WidthCache {
     41 private:
     42     // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl.
     43     class SmallStringKey {
     44     public:
     45         static unsigned capacity() { return s_capacity; }
     46 
     47         SmallStringKey()
     48             : m_length(s_emptyValueLength)
     49         {
     50         }
     51 
     52         SmallStringKey(WTF::HashTableDeletedValueType)
     53             : m_length(s_deletedValueLength)
     54         {
     55         }
     56 
     57         template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length)
     58             : m_length(length)
     59         {
     60             ASSERT(length <= s_capacity);
     61 
     62             StringHasher hasher;
     63 
     64             bool remainder = length & 1;
     65             length >>= 1;
     66 
     67             unsigned i = 0;
     68             while (length--) {
     69                 m_characters[i] = characters[i];
     70                 m_characters[i + 1] = characters[i + 1];
     71                 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
     72                 i += 2;
     73             }
     74 
     75             if (remainder) {
     76                 m_characters[i] = characters[i];
     77                 hasher.addCharacter(characters[i]);
     78             }
     79 
     80             m_hash = hasher.hash();
     81         }
     82 
     83         const UChar* characters() const { return m_characters; }
     84         unsigned short length() const { return m_length; }
     85         unsigned hash() const { return m_hash; }
     86 
     87         bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; }
     88         bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; }
     89 
     90     private:
     91         static const unsigned s_capacity = 15;
     92         static const unsigned s_emptyValueLength = s_capacity + 1;
     93         static const unsigned s_deletedValueLength = s_capacity + 2;
     94 
     95         unsigned m_hash;
     96         unsigned short m_length;
     97         UChar m_characters[s_capacity];
     98     };
     99 
    100     struct SmallStringKeyHash {
    101         static unsigned hash(const SmallStringKey& key) { return key.hash(); }
    102         static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; }
    103         static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length.
    104     };
    105 
    106     struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
    107         static const bool hasIsEmptyValueFunction = true;
    108         static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); }
    109         static const bool needsDestruction = false;
    110         static const unsigned minimumTableSize = 16;
    111     };
    112 
    113     friend bool operator==(const SmallStringKey&, const SmallStringKey&);
    114 
    115 public:
    116     WidthCache()
    117         : m_interval(s_maxInterval)
    118         , m_countdown(m_interval)
    119     {
    120     }
    121 
    122     float* add(const TextRun& run, float entry, bool hasKerningOrLigatures, bool hasWordSpacingOrLetterSpacing, GlyphOverflow* glyphOverflow)
    123     {
    124         // The width cache is not really profitable unless we're doing expensive glyph transformations.
    125         if (!hasKerningOrLigatures)
    126             return 0;
    127         // Word spacing and letter spacing can change the width of a word.
    128         if (hasWordSpacingOrLetterSpacing)
    129             return 0;
    130         // Since this is just a width cache, we don't have enough information to satisfy glyph queries.
    131         if (glyphOverflow)
    132             return 0;
    133         // If we allow tabs and a tab occurs inside a word, the width of the word varies based on its position on the line.
    134         if (run.allowTabs())
    135             return 0;
    136         if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
    137             return 0;
    138 
    139         if (m_countdown > 0) {
    140             --m_countdown;
    141             return 0;
    142         }
    143 
    144         return addSlowCase(run, entry);
    145     }
    146 
    147     void clear()
    148     {
    149         m_singleCharMap.clear();
    150         m_map.clear();
    151     }
    152 
    153 private:
    154     float* addSlowCase(const TextRun& run, float entry)
    155     {
    156         int length = run.length();
    157         bool isNewEntry;
    158         float *value;
    159         if (length == 1) {
    160             SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry);
    161             isNewEntry = addResult.isNewEntry;
    162             value = &addResult.iterator->value;
    163         } else {
    164             SmallStringKey smallStringKey;
    165             if (run.is8Bit())
    166                 smallStringKey = SmallStringKey(run.characters8(), length);
    167             else
    168                 smallStringKey = SmallStringKey(run.characters16(), length);
    169 
    170             Map::AddResult addResult = m_map.add(smallStringKey, entry);
    171             isNewEntry = addResult.isNewEntry;
    172             value = &addResult.iterator->value;
    173         }
    174 
    175         // Cache hit: ramp up by sampling the next few words.
    176         if (!isNewEntry) {
    177             m_interval = s_minInterval;
    178             return value;
    179         }
    180 
    181         // Cache miss: ramp down by increasing our sampling interval.
    182         if (m_interval < s_maxInterval)
    183             ++m_interval;
    184         m_countdown = m_interval;
    185 
    186         if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
    187             return value;
    188 
    189         // No need to be fancy: we're just trying to avoid pathological growth.
    190         m_singleCharMap.clear();
    191         m_map.clear();
    192         return 0;
    193     }
    194 
    195     typedef HashMap<SmallStringKey, float, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
    196     typedef HashMap<uint32_t, float, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t> > SingleCharMap;
    197     static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
    198     static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
    199     static const unsigned s_maxSize = 500000; // Just enough to guard against pathological growth.
    200 
    201     int m_interval;
    202     int m_countdown;
    203     SingleCharMap m_singleCharMap;
    204     Map m_map;
    205 };
    206 
    207 inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
    208 {
    209     if (a.length() != b.length())
    210         return false;
    211     return WTF::equal(a.characters(), b.characters(), a.length());
    212 }
    213 
    214 } // namespace WebCore
    215 
    216 #endif // WidthCache_h
    217