1 /* $NetBSD: wsdisplay_glyphcache.c,v 1.7 2015/08/24 22:50:33 pooka Exp $ */
2
3 /*
4 * Copyright (c) 2012 Michael Lorenz
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 /*
29 * a simple glyph cache in offscreen memory
30 * For now it only caches glyphs with the default attribute ( assuming they're
31 * the most commonly used glyphs ) but the API should at least not prevent
32 * more sophisticated caching algorithms
33 */
34
35 #ifdef _KERNEL_OPT
36 #include "opt_glyphcache.h"
37 #endif
38
39 #include <sys/systm.h>
40 #include <sys/atomic.h>
41 #include <sys/errno.h>
42 #include <sys/kmem.h>
43 #include <dev/wscons/wsdisplay_glyphcachevar.h>
44
45 #ifdef GLYPHCACHE_DEBUG
46 #define DPRINTF aprint_normal
47 #else
48 #define DPRINTF while (0) printf
49 #endif
50
51 static inline int
attr2idx(long attr)52 attr2idx(long attr)
53 {
54 if ((attr & 0xf0f0fff8) != 0)
55 return -1;
56
57 return (((attr >> 16) & 0x0f) | ((attr >> 20) & 0xf0));
58 }
59
60 /* first line, lines, width, attr */
61 int
glyphcache_init(glyphcache * gc,int first,int lines,int width,int cellwidth,int cellheight,long attr)62 glyphcache_init(glyphcache *gc, int first, int lines, int width,
63 int cellwidth, int cellheight, long attr)
64 {
65 int cache_lines, buckets, i, usedcells = 0, idx;
66 gc_bucket *b;
67
68 /* first the geometry stuff */
69 gc->gc_cellwidth = cellwidth;
70 gc->gc_cellheight = cellheight;
71 gc->gc_firstline = first;
72 gc->gc_cellsperline = width / cellwidth;
73 gc->gc_buckets = NULL;
74 gc->gc_numbuckets = 0;
75 if (lines < 0) lines = 0;
76 cache_lines = lines / cellheight;
77 gc->gc_numcells = cache_lines * gc->gc_cellsperline;
78
79 /* now allocate buckets */
80 buckets = (gc->gc_numcells / 223);
81 if ((buckets * 223) < gc->gc_numcells)
82 buckets++;
83
84 /*
85 * if we don't have enough video memory to cache at least a few glyphs
86 * we stop right here
87 */
88 if (buckets < 1)
89 return ENOMEM;
90
91 gc->gc_buckets = kmem_alloc(sizeof(gc_bucket) * buckets, KM_SLEEP);
92 if (gc->gc_buckets == NULL) {
93 aprint_error("%s: can't allocate memory\n", __func__);
94 return ENOMEM;
95 }
96 gc->gc_numbuckets = buckets;
97
98 DPRINTF("%s: using %d buckets\n", __func__, buckets);
99 for (i = 0; i < buckets; i++) {
100 b = &gc->gc_buckets[i];
101 b->gb_firstcell = usedcells;
102 b->gb_numcells = min(223, gc->gc_numcells - usedcells);
103 usedcells += 223;
104 b->gb_usedcells = 0;
105 b->gb_index = -1;
106 }
107
108 /* initialize the attribute map... */
109 for (i = 0; i < 256; i++) {
110 gc->gc_attrmap[i] = -1;
111 }
112
113 /* first bucket goes to default attr */
114 idx = attr2idx(attr);
115 if (idx >= 0) {
116 gc->gc_attrmap[idx] = 0;
117 gc->gc_buckets[0].gb_index = idx;
118 }
119
120 glyphcache_wipe(gc);
121 DPRINTF("%s: using %d cells total, from %d width %d\n", __func__,
122 gc->gc_numcells, gc->gc_firstline, gc->gc_cellsperline);
123 return 0;
124 }
125
126 void
glyphcache_wipe(glyphcache * gc)127 glyphcache_wipe(glyphcache *gc)
128 {
129 gc_bucket *b;
130 int i, j, idx;
131
132 if ((gc->gc_buckets == NULL) || (gc->gc_numbuckets < 1))
133 return;
134
135 idx = gc->gc_buckets[0].gb_index;
136
137 /* empty all the buckets */
138 for (i = 0; i < gc->gc_numbuckets; i++) {
139 b = &gc->gc_buckets[i];
140 b->gb_usedcells = 0;
141 b->gb_index = -1;
142 for (j = 0; j < b->gb_numcells; j++)
143 b->gb_map[j] = -1;
144 }
145
146 for (i = 0; i < 256; i++) {
147 gc->gc_attrmap[i] = -1;
148 }
149
150 /* now put the first bucket back where it was */
151 gc->gc_attrmap[idx] = 0;
152 gc->gc_buckets[0].gb_index = idx;
153 }
154
155 /*
156 * add a glyph drawn at (x,y) to the cache as (c)
157 * call this only if glyphcache_try() returned GC_ADD
158 * caller or gc_bitblt must make sure the glyph is actually completely drawn
159 */
160 int
glyphcache_add(glyphcache * gc,int c,int x,int y)161 glyphcache_add(glyphcache *gc, int c, int x, int y)
162 {
163 gc_bucket *b = gc->gc_next;
164 int cell;
165 int cx, cy;
166
167 if (b->gb_usedcells >= b->gb_numcells)
168 return ENOMEM;
169 cell = atomic_add_int_nv(&b->gb_usedcells, 1) - 1;
170 cell += b->gb_firstcell;
171 cy = gc->gc_firstline +
172 (cell / gc->gc_cellsperline) * gc->gc_cellheight;
173 cx = (cell % gc->gc_cellsperline) * gc->gc_cellwidth;
174 b->gb_map[c - 33] = (cx << 16) | cy;
175 gc->gc_bitblt(gc->gc_blitcookie, x, y, cx, cy,
176 gc->gc_cellwidth, gc->gc_cellheight, gc->gc_rop);
177 if (gc->gc_underline & 1) {
178 glyphcache_underline(gc, x, y, gc->gc_underline);
179 }
180 return 0;
181 }
182
183 void
glyphcache_underline(glyphcache * gc,int x,int y,long attr)184 glyphcache_underline(glyphcache *gc, int x, int y, long attr)
185 {
186 if (gc->gc_rectfill == NULL)
187 return;
188
189 gc->gc_rectfill(gc->gc_blitcookie, x, y + gc->gc_cellheight - 2,
190 gc->gc_cellwidth, 1, attr);
191 }
192 /*
193 * check if (c) is in the cache, if so draw it at (x,y)
194 * return:
195 * - GC_OK when the glyph was found
196 * - GC_ADD when the glyph wasn't found but can be added
197 * - GC_NOPE when the glyph can't be cached
198 */
199 int
glyphcache_try(glyphcache * gc,int c,int x,int y,long attr)200 glyphcache_try(glyphcache *gc, int c, int x, int y, long attr)
201 {
202 int cell, cx, cy, idx, bi;
203 gc_bucket *b;
204
205 idx = attr2idx(attr);
206 /* see if we're in range */
207 if ((c < 33) || (c > 255) || (idx < 0))
208 return GC_NOPE;
209 /* see if there's already a bucket for this attribute */
210 bi = gc->gc_attrmap[idx];
211 if (bi == -1) {
212 /* nope, see if there's an empty one left */
213 bi = 1;
214 while ((bi < gc->gc_numbuckets) &&
215 (gc->gc_buckets[bi].gb_index != -1)) {
216 bi++;
217 }
218 if (bi < gc->gc_numbuckets) {
219 /* found one -> grab it */
220 gc->gc_attrmap[idx] = bi;
221 b = &gc->gc_buckets[bi];
222 b->gb_index = idx;
223 b->gb_usedcells = 0;
224 /* make sure this doesn't get evicted right away */
225 b->gb_lastread = time_uptime;
226 } else {
227 /*
228 * still nothing
229 * steal the least recently read bucket
230 */
231 time_t moo = time_uptime;
232 int i, oldest = 1;
233
234 for (i = 1; i < gc->gc_numbuckets; i++) {
235 if (gc->gc_buckets[i].gb_lastread < moo) {
236 oldest = i;
237 moo = gc->gc_buckets[i].gb_lastread;
238 }
239 }
240
241 /* if we end up here all buckets must be in use */
242 b = &gc->gc_buckets[oldest];
243 gc->gc_attrmap[b->gb_index] = -1;
244 b->gb_index = idx;
245 b->gb_usedcells = 0;
246 gc->gc_attrmap[idx] = oldest;
247 /* now scrub it */
248 for (i = 0; i < b->gb_numcells; i++)
249 b->gb_map[i] = -1;
250 /* and set the time stamp */
251 b->gb_lastread = time_uptime;
252 }
253 } else {
254 /* found one */
255 b = &gc->gc_buckets[bi];
256 }
257
258 /* see if there's room in the bucket */
259 if (b->gb_usedcells >= b->gb_numcells)
260 return GC_NOPE;
261
262 cell = b->gb_map[c - 33];
263 if (cell == -1) {
264 gc->gc_next = b;
265 gc->gc_underline = attr;
266 return GC_ADD;
267 }
268
269 /* it's in the cache - draw it */
270 cy = cell & 0xffff;
271 cx = (cell >> 16) & 0xffff;
272 gc->gc_bitblt(gc->gc_blitcookie, cx, cy, x, y,
273 gc->gc_cellwidth, gc->gc_cellheight, gc->gc_rop);
274 /* and underline it if needed */
275 if (attr & 1)
276 glyphcache_underline(gc, x, y, attr);
277 /* update bucket's time stamp */
278 b->gb_lastread = time_uptime;
279 return GC_OK;
280 }
281