summaryrefslogtreecommitdiff
path: root/firmware/font_cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/font_cache.c')
-rw-r--r--firmware/font_cache.c122
1 files changed, 47 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
74static 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 ************************************************************************/
77int 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 ******************************************************************************/
106static 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}