diff options
author | Fred Bauer <fred.w.bauer@gmail.com> | 2011-10-16 20:17:44 +0000 |
---|---|---|
committer | Fred Bauer <fred.w.bauer@gmail.com> | 2011-10-16 20:17:44 +0000 |
commit | cd0102ba1440c023be29662a40f40201af9a065d (patch) | |
tree | 7182b9bedc90d6a3960199189f10fba18e56017d | |
parent | 4f3e1d6b487c5a197caf2351e4ed607a056811fd (diff) | |
download | rockbox-cd0102ba1440c023be29662a40f40201af9a065d.tar.gz rockbox-cd0102ba1440c023be29662a40f40201af9a065d.zip |
font_cache.c: Optimize and simplify cache search. ~25% font rendering boost
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@30763 a1c6a512-1295-4272-9138-f99709370657
-rw-r--r-- | firmware/font_cache.c | 122 | ||||
-rw-r--r-- | firmware/include/font_cache.h | 2 |
2 files changed, 49 insertions, 75 deletions
diff --git a/firmware/font_cache.c b/firmware/font_cache.c index 843c1520c1..72a96bfb23 100644 --- a/firmware/font_cache.c +++ b/firmware/font_cache.c | |||
@@ -68,92 +68,55 @@ void font_cache_create( | |||
68 | fcache->_index[i] = i; /* small cheat here */ | 68 | fcache->_index[i] = i; /* small cheat here */ |
69 | } | 69 | } |
70 | 70 | ||
71 | /******************************************************************************* | 71 | /************************************************************************* |
72 | * font_cache_index_of | 72 | * Binary search that attempts a primary lucky guess that succeeds |
73 | ******************************************************************************/ | 73 | * when there are consecutive codes in the cache between previous |
74 | static int font_cache_index_of( | 74 | * search and new search. Returns a negative of insertion point if |
75 | struct font_cache* fcache, | 75 | * not found. |
76 | unsigned short char_code) | 76 | ************************************************************************/ |
77 | int search( struct font_cache* fcache, | ||
78 | unsigned short char_code, | ||
79 | int *p_insertion_point ) | ||
77 | { | 80 | { |
78 | struct font_cache_entry* p; | 81 | struct font_cache_entry *p; |
79 | int left, right, mid, c; | 82 | int left, right, mid=-1, c; |
80 | left = 0; | 83 | left = 0; |
81 | right = fcache->_size - 1; | 84 | right = fcache->_size - 1; |
82 | 85 | ||
86 | /* go for a lucky guess */ | ||
87 | if ( fcache->_prev_char_code != -1 ) | ||
88 | mid = char_code + | ||
89 | fcache->_prev_result - fcache->_prev_char_code; | ||
90 | |||
91 | /* check bounds or unset */ | ||
92 | if ( mid < 0 || mid > right ) | ||
93 | mid = ( left + right ) / 2; | ||
94 | |||
83 | do | 95 | do |
84 | { | 96 | { |
85 | mid = (left + right) / 2; | ||
86 | |||
87 | p = lru_data(&fcache->_lru, fcache->_index[mid]); | 97 | p = lru_data(&fcache->_lru, fcache->_index[mid]); |
88 | c = p->_char_code - char_code; | 98 | c = p->_char_code - char_code; |
89 | 99 | ||
90 | if (c == 0) | 100 | if (c == 0) |
91 | return mid; | 101 | { |
92 | 102 | fcache->_prev_result = mid; | |
103 | fcache->_prev_char_code = char_code; | ||
104 | *p_insertion_point = mid; | ||
105 | return 1; | ||
106 | } | ||
93 | if (c < 0) | 107 | if (c < 0) |
94 | left = mid + 1; | 108 | left = mid + 1; |
95 | else | 109 | else |
96 | right = mid - 1; | 110 | right = mid - 1; |
97 | } | ||
98 | while (left <= right); | ||
99 | |||
100 | return -1; | ||
101 | } | ||
102 | |||
103 | /******************************************************************************* | ||
104 | * font_cache_insertion_point | ||
105 | ******************************************************************************/ | ||
106 | static int font_cache_insertion_point( | ||
107 | struct font_cache* fcache, | ||
108 | unsigned short char_code) | ||
109 | { | ||
110 | struct font_cache_entry* p; | ||
111 | short *index = fcache->_index; | ||
112 | |||
113 | p = lru_data(&fcache->_lru, index[0]); | ||
114 | if (char_code < p->_char_code) | ||
115 | return -1; | ||
116 | |||
117 | p = lru_data(&fcache->_lru, index[fcache->_capacity - 1]); | ||
118 | if (char_code > p->_char_code) | ||
119 | return fcache->_capacity - 1; | ||
120 | |||
121 | int left, right, mid, c; | ||
122 | |||
123 | left = 0; | ||
124 | right = fcache->_capacity - 1; | ||
125 | 111 | ||
126 | do | ||
127 | { | ||
128 | mid = (left + right) / 2; | 112 | mid = (left + right) / 2; |
129 | |||
130 | p = lru_data(&fcache->_lru, index[mid]); | ||
131 | c = char_code - p->_char_code; | ||
132 | |||
133 | if (c >= 0) | ||
134 | { | ||
135 | p = lru_data(&fcache->_lru, index[mid+1]); | ||
136 | int z = char_code - p->_char_code; | ||
137 | |||
138 | if (z < 0) | ||
139 | return mid; | ||
140 | |||
141 | if (z == 0) | ||
142 | return mid + 1; | ||
143 | } | ||
144 | |||
145 | |||
146 | if (c > 0) | ||
147 | left = mid + 1; | ||
148 | else | ||
149 | right = mid - 1; | ||
150 | } | 113 | } |
151 | while (left <= right); | 114 | while (left <= right); |
152 | 115 | ||
153 | /* not found */ | 116 | /* not found */ |
154 | return -2; | 117 | *p_insertion_point = mid; |
118 | return 0; | ||
155 | } | 119 | } |
156 | |||
157 | /******************************************************************************* | 120 | /******************************************************************************* |
158 | * font_cache_get | 121 | * font_cache_get |
159 | ******************************************************************************/ | 122 | ******************************************************************************/ |
@@ -163,24 +126,33 @@ struct font_cache_entry* font_cache_get( | |||
163 | void (*callback) (struct font_cache_entry* p, void *callback_data), | 126 | void (*callback) (struct font_cache_entry* p, void *callback_data), |
164 | void *callback_data) | 127 | void *callback_data) |
165 | { | 128 | { |
166 | int insertion_point = font_cache_insertion_point(fcache, char_code); | 129 | struct font_cache_entry* p; |
167 | if (insertion_point >= 0) | 130 | int insertion_point; |
131 | int index_to_replace; | ||
132 | |||
133 | if( search(fcache, char_code, &insertion_point)) | ||
168 | { | 134 | { |
169 | short lru_handle = fcache->_index[insertion_point]; | 135 | short lru_handle = fcache->_index[insertion_point]; |
170 | struct font_cache_entry* p = lru_data(&fcache->_lru, lru_handle); | 136 | p = lru_data(&fcache->_lru, lru_handle); |
171 | if (p->_char_code == char_code) | 137 | if (p->_char_code == char_code) |
172 | { | 138 | { |
173 | lru_touch(&fcache->_lru, lru_handle); | 139 | lru_touch(&fcache->_lru, lru_handle); |
174 | return lru_data(&fcache->_lru, lru_handle); | 140 | return lru_data(&fcache->_lru, lru_handle); |
175 | } | 141 | } |
176 | } | 142 | } |
143 | else /* not found */ | ||
144 | { | ||
145 | p = lru_data(&fcache->_lru, | ||
146 | fcache->_index[insertion_point+1]); | ||
147 | if ( char_code > p->_char_code ) | ||
148 | insertion_point++; | ||
149 | } | ||
177 | 150 | ||
178 | /* not found */ | 151 | /* find index to replace */ |
179 | short lru_handle_to_replace = fcache->_lru._head; | 152 | short lru_handle_to_replace = fcache->_lru._head; |
180 | struct font_cache_entry* p = | 153 | p = lru_data(&fcache->_lru, lru_handle_to_replace); |
181 | lru_data(&fcache->_lru, lru_handle_to_replace); | 154 | search(fcache, p->_char_code, &index_to_replace); |
182 | int index_to_replace = font_cache_index_of(fcache, p->_char_code); | 155 | |
183 | |||
184 | if (insertion_point < index_to_replace) | 156 | if (insertion_point < index_to_replace) |
185 | { | 157 | { |
186 | /* shift memory up */ | 158 | /* shift memory up */ |
@@ -209,7 +181,7 @@ struct font_cache_entry* font_cache_get( | |||
209 | fcache->_size++; | 181 | fcache->_size++; |
210 | 182 | ||
211 | p->_char_code = char_code; | 183 | p->_char_code = char_code; |
184 | /* fill bitmap */ | ||
212 | callback(p, callback_data); | 185 | callback(p, callback_data); |
213 | |||
214 | return p; | 186 | return p; |
215 | } | 187 | } |
diff --git a/firmware/include/font_cache.h b/firmware/include/font_cache.h index e625abb79e..a4c959e336 100644 --- a/firmware/include/font_cache.h +++ b/firmware/include/font_cache.h | |||
@@ -29,6 +29,8 @@ struct font_cache | |||
29 | struct lru _lru; | 29 | struct lru _lru; |
30 | int _size; | 30 | int _size; |
31 | int _capacity; | 31 | int _capacity; |
32 | int _prev_char_code; | ||
33 | int _prev_result; | ||
32 | short *_index; /* index of lru handles in char_code order */ | 34 | short *_index; /* index of lru handles in char_code order */ |
33 | }; | 35 | }; |
34 | 36 | ||