1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "Benchmark.h"
9#include "SkCanvas.h"
10#include "SkFontHost.h"
11#include "SkPaint.h"
12#include "SkString.h"
13#include "SkTemplates.h"
14
15#include "gUniqueGlyphIDs.h"
16#define gUniqueGlyphIDs_Sentinel    0xFFFF
17
18static int count_glyphs(const uint16_t start[]) {
19    const uint16_t* curr = start;
20    while (*curr != gUniqueGlyphIDs_Sentinel) {
21        curr += 1;
22    }
23    return static_cast<int>(curr - start);
24}
25
26class FontCacheBench : public Benchmark {
27public:
28    FontCacheBench()  {}
29
30protected:
31    virtual const char* onGetName() SK_OVERRIDE {
32        return "fontcache";
33    }
34
35    virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
36        SkPaint paint;
37        this->setupPaint(&paint);
38        paint.setTextEncoding(SkPaint::kGlyphID_TextEncoding);
39
40        const uint16_t* array = gUniqueGlyphIDs;
41        while (*array != gUniqueGlyphIDs_Sentinel) {
42            int count = count_glyphs(array);
43            for (int i = 0; i < loops; ++i) {
44                paint.measureText(array, count * sizeof(uint16_t));
45            }
46            array += count + 1;    // skip the sentinel
47        }
48    }
49
50private:
51    typedef Benchmark INHERITED;
52};
53
54///////////////////////////////////////////////////////////////////////////////
55
56static uint32_t rotr(uint32_t value, unsigned bits) {
57    return (value >> bits) | (value << (32 - bits));
58}
59
60typedef uint32_t (*HasherProc)(uint32_t);
61
62static uint32_t hasher0(uint32_t value) {
63    value = value ^ (value >> 16);
64    return value ^ (value >> 8);
65}
66
67static uint32_t hasher2(uint32_t h) {
68    h ^= h >> 16;
69    h *= 0x85ebca6b;
70    h ^= h >> 13;
71    h *= 0xc2b2ae35;
72    h ^= h >> 16;
73
74    h ^= (h >> 8);
75    return h;
76}
77
78static const struct {
79    const char* fName;
80    HasherProc  fHasher;
81} gRec[] = {
82    { "hasher0",  hasher0 },
83    { "hasher2",  hasher2 },
84};
85
86#define kMaxHashBits   12
87#define kMaxHashCount  (1 << kMaxHashBits)
88
89static int count_collisions(const uint16_t array[], int count, HasherProc proc,
90                            unsigned hashMask) {
91    char table[kMaxHashCount];
92    sk_bzero(table, sizeof(table));
93
94    int collisions = 0;
95    for (int i = 0; i < count; ++i) {
96        int index = proc(array[i]) & hashMask;
97        collisions += table[index];
98        table[index] = 1;
99    }
100    return collisions;
101}
102
103static void dump_array(const uint16_t array[], int count) {
104    for (int i = 0; i < count; ++i) {
105        SkDebugf(" %d,", array[i]);
106    }
107    SkDebugf("\n");
108}
109
110class FontCacheEfficiency : public Benchmark {
111public:
112    FontCacheEfficiency()  {
113        if (false) dump_array(NULL, 0);
114        if (false) rotr(0, 0);
115    }
116
117protected:
118    virtual const char* onGetName() SK_OVERRIDE {
119        return "fontefficiency";
120    }
121
122    virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
123        static bool gDone;
124        if (gDone) {
125            return;
126        }
127        gDone = true;
128
129        for (int hashBits = 6; hashBits <= 12; hashBits += 1) {
130            int hashMask = ((1 << hashBits) - 1);
131            for (int limit = 32; limit <= 1024; limit <<= 1) {
132                for (size_t i = 0; i < SK_ARRAY_COUNT(gRec); ++i) {
133                    int collisions = 0;
134                    int glyphs = 0;
135                    const uint16_t* array = gUniqueGlyphIDs;
136                    while (*array != gUniqueGlyphIDs_Sentinel) {
137                        int count = SkMin32(count_glyphs(array), limit);
138                        collisions += count_collisions(array, count, gRec[i].fHasher, hashMask);
139                        glyphs += count;
140                        array += count + 1;    // skip the sentinel
141                    }
142                    SkDebugf("hashBits [%d] limit [%d] collisions [%d / %d = %1.2g%%] using %s\n", hashBits, limit, collisions, glyphs,
143                             collisions * 100.0 / glyphs, gRec[i].fName);
144                }
145            }
146        }
147    }
148
149private:
150    typedef Benchmark INHERITED;
151};
152
153///////////////////////////////////////////////////////////////////////////////
154
155DEF_BENCH( return new FontCacheBench(); )
156
157// undefine this to run the efficiency test
158//DEF_BENCH( return new FontCacheEfficiency(); )
159