src/ds/gx/software.c (view raw)
1/* Copyright (c) 2013-2017 Jeffrey Pfau
2 *
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6#include <mgba/internal/ds/gx/software.h>
7
8#include <mgba-util/memory.h>
9#include "gba/renderers/software-private.h"
10
11#define SCREEN_SIZE (DS_VIDEO_VERTICAL_PIXELS << 12)
12
13DEFINE_VECTOR(DSGXSoftwarePolygonList, struct DSGXSoftwarePolygon);
14DEFINE_VECTOR(DSGXSoftwareEdgeList, struct DSGXSoftwareEdge);
15DEFINE_VECTOR(DSGXSoftwareSpanList, struct DSGXSoftwareSpan);
16
17static void DSGXSoftwareRendererInit(struct DSGXRenderer* renderer);
18static void DSGXSoftwareRendererReset(struct DSGXRenderer* renderer);
19static void DSGXSoftwareRendererDeinit(struct DSGXRenderer* renderer);
20static void DSGXSoftwareRendererInvalidateTex(struct DSGXRenderer* renderer, int slot);
21static void DSGXSoftwareRendererSetRAM(struct DSGXRenderer* renderer, struct DSGXVertex* verts, struct DSGXPolygon* polys, unsigned polyCount);
22static void DSGXSoftwareRendererDrawScanline(struct DSGXRenderer* renderer, int y);
23static void DSGXSoftwareRendererGetScanline(struct DSGXRenderer* renderer, int y, color_t** output);
24
25static void _expandColor(uint16_t c15, uint8_t* r, uint8_t* g, uint8_t* b) {
26 *r = ((c15 << 1) & 0x3E) | 1;
27 *g = ((c15 >> 4) & 0x3E) | 1;
28 *b = ((c15 >> 9) & 0x3E) | 1;
29}
30
31static color_t _finishColor(uint8_t r, uint8_t g, uint8_t b) {
32#ifndef COLOR_16_BIT
33 color_t rgb = (r << 2) & 0xF8;
34 rgb |= (g << 10) & 0xF800;
35 rgb |= (b << 18) & 0xF80000;
36 return rgb;
37#else
38#error Unsupported color depth
39#endif
40}
41
42static color_t _lookupColor(struct DSGXSoftwareEndpoint* ep, struct DSGXSoftwarePolygon* poly) {
43 // TODO: Optimize
44 uint16_t texel;
45
46 int16_t s = ep->s >> 4;
47 int16_t t = ep->t >> 4;
48 if (!DSGXTexParamsIsSRepeat(poly->poly->texParams)) {
49 if (s < 0) {
50 s = 0;
51 } else if (s >= poly->texW) {
52 s = poly->texW - 1;
53 }
54 } else if (DSGXTexParamsIsSMirror(poly->poly->texParams)) {
55 if (s & poly->texW) {
56 s = poly->texW - s;
57 }
58 s &= poly->texW - 1;
59 } else {
60 s &= poly->texW - 1;
61 }
62 if (!DSGXTexParamsIsTRepeat(poly->poly->texParams)) {
63 if (t < 0) {
64 t = 0;
65 } else if (t >= poly->texH) {
66 t = poly->texW - 1;
67 }
68 } else if (DSGXTexParamsIsTMirror(poly->poly->texParams)) {
69 if (t & poly->texH) {
70 t = poly->texH - t;
71 }
72 t &= poly->texH - 1;
73 } else {
74 t &= poly->texH - 1;
75 }
76
77 uint16_t texelCoord = s + t * poly->texW;
78 switch (poly->texFormat) {
79 case 0:
80 default:
81 return _finishColor(ep->cr, ep->cg, ep->cb);
82 case 1:
83 return _finishColor(0, 0, 0x3F);
84 case 2:
85 texel = ((uint8_t*) poly->texBase)[texelCoord >> 2];
86 if (texelCoord & 0x3) {
87 texel >>= 2 * texel & 3;
88 }
89 texel &= 0x3;
90 break;
91 case 3:
92 texel = ((uint8_t*) poly->texBase)[texelCoord >> 1];
93 if (texelCoord & 0x1) {
94 texel >>= 4;
95 }
96 texel &= 0xF;
97 break;
98 case 4:
99 texel = ((uint8_t*) poly->texBase)[texelCoord];
100 break;
101 case 5:
102 return _finishColor(0x3F, 0, 0x3F);
103 case 6:
104 return _finishColor(0x3F, 0x3F, 0);
105 case 7:
106 return _finishColor(0x3F, 0x3F, 0x3F);
107 }
108 if (DSGXTexParamsIs0Transparent(poly->poly->texParams) && !texel) {
109 return FLAG_UNWRITTEN;
110 }
111 uint8_t r, g, b;
112 texel = poly->palBase[texel];
113 _expandColor(texel, &r, &g, &b);
114 return _finishColor(r, g, b);
115}
116
117static int _edgeSort(const void* a, const void* b) {
118 const struct DSGXSoftwareEdge* ea = a;
119 const struct DSGXSoftwareEdge* eb = b;
120
121 // Sort upside down
122 if (ea->y0 < eb->y0) {
123 return 1;
124 }
125 if (ea->y0 > eb->y0) {
126 return -1;
127 }
128 if (ea->y1 < eb->y1) {
129 return 1;
130 }
131 if (ea->y1 > eb->y1) {
132 return -1;
133 }
134 return 0;
135}
136
137static bool _edgeToSpan(struct DSGXSoftwareSpan* span, const struct DSGXSoftwareEdge* edge, int index, int32_t y) {
138 int32_t height = edge->y1 - edge->y0;
139 int64_t yw = (y << 12) - edge->y0;
140 if (!height) {
141 return false;
142 }
143 // Clamp to bounds
144 if (yw < 0) {
145 yw = 0;
146 } else if (yw > height) {
147 yw = height;
148 }
149 int64_t heightRecip = 0x100000000LL / height;
150 span->ep[index].x = ((((int64_t) (edge->x1 - edge->x0) * yw) * heightRecip) >> 32) + edge->x0;
151 if (index && span->ep[0].x > span->ep[index].x) {
152 int32_t temp = span->ep[index].x;
153 span->ep[index] = span->ep[0];
154 span->ep[0].x = temp;
155 index = 0;
156 }
157 int32_t w = ((((int64_t) (edge->w1 - edge->w0) * yw) * heightRecip) >> 32) + edge->w0;
158 int64_t wRecip = 0x1000000000000LL / w;
159 span->ep[index].w = w;
160 span->ep[index].cr = ((((((int32_t) (edge->cr1 * edge->w1 - edge->cr0 * edge->w0) * yw) * heightRecip) >> 32) + edge->cr0 * edge->w0) * wRecip) >> 48;
161 span->ep[index].cg = ((((((int32_t) (edge->cg1 * edge->w1 - edge->cg0 * edge->w0) * yw) * heightRecip) >> 32) + edge->cg0 * edge->w0) * wRecip) >> 48;
162 span->ep[index].cb = ((((((int32_t) (edge->cb1 * edge->w1 - edge->cb0 * edge->w0) * yw) * heightRecip) >> 32) + edge->cb0 * edge->w0) * wRecip) >> 48;
163 span->ep[index].s = ((((((int32_t) (edge->s1 * edge->w1 - edge->s0 * edge->w0) * yw) * heightRecip) >> 32) + edge->s0 * edge->w0) * wRecip) >> 48;
164 span->ep[index].t = ((((((int32_t) (edge->t1 * edge->w1 - edge->t0 * edge->w0) * yw) * heightRecip) >> 32) + edge->t0 * edge->w0) * wRecip) >> 48;
165
166 return true;
167}
168
169static int _spanSort(const void* a, const void* b) {
170 const struct DSGXSoftwareSpan* sa = a;
171 const struct DSGXSoftwareSpan* sb = b;
172
173 // Sort backwards
174 if (sa->ep[0].x < sb->ep[0].x) {
175 return 1;
176 }
177 if (sa->ep[0].x > sb->ep[0].x) {
178 return -1;
179 }
180 if (sa->ep[0].w < sb->ep[0].w) {
181 return 1;
182 }
183 if (sa->ep[0].w > sb->ep[0].w) {
184 return -1;
185 }
186 return 0;
187}
188
189static void _lerpEndpoint(const struct DSGXSoftwareSpan* span, struct DSGXSoftwareEndpoint* ep, unsigned x) {
190 int64_t width = span->ep[1].x - span->ep[0].x;
191 int64_t xw = ((uint64_t) x << 12) - span->ep[0].x;
192 if (!width) {
193 return; // TODO?
194 }
195 // Clamp to bounds
196 if (xw < 0) {
197 xw = 0;
198 } else if (xw > width) {
199 xw = width;
200 }
201 int32_t w0 = span->ep[0].w;
202 int32_t w1 = span->ep[1].w;
203 int64_t widthRecip = 0x100000000LL / width;
204 int32_t w = ((((int64_t) (w1 - w0) * xw) * widthRecip) >> 32) + w0;
205 ep->w = w;
206 int64_t wRecip = 0x1000000000000LL / w;
207
208 uint64_t r = ((((span->ep[1].cr * (int64_t) w1 - span->ep[0].cr * (int64_t) w0) * xw) * widthRecip) >> 32) + span->ep[0].cr * (int64_t) w0;
209 uint64_t g = ((((span->ep[1].cg * (int64_t) w1 - span->ep[0].cg * (int64_t) w0) * xw) * widthRecip) >> 32) + span->ep[0].cg * (int64_t) w0;
210 uint64_t b = ((((span->ep[1].cb * (int64_t) w1 - span->ep[0].cb * (int64_t) w0) * xw) * widthRecip) >> 32) + span->ep[0].cb * (int64_t) w0;
211 ep->cr = (r * wRecip) >> 48;
212 ep->cg = (g * wRecip) >> 48;
213 ep->cb = (b * wRecip) >> 48;
214
215 int32_t s = ((((span->ep[1].s * (int64_t) w1 - span->ep[0].s * (int64_t) w0) * xw) * widthRecip) >> 32) + span->ep[0].s * (int64_t) w0;
216 int32_t t = ((((span->ep[1].t * (int64_t) w1 - span->ep[0].t * (int64_t) w0) * xw) * widthRecip) >> 32) + span->ep[0].t * (int64_t) w0;
217 ep->s = (s * wRecip) >> 48;
218 ep->t = (t * wRecip) >> 48;
219}
220
221void DSGXSoftwareRendererCreate(struct DSGXSoftwareRenderer* renderer) {
222 renderer->d.init = DSGXSoftwareRendererInit;
223 renderer->d.reset = DSGXSoftwareRendererReset;
224 renderer->d.deinit = DSGXSoftwareRendererDeinit;
225 renderer->d.invalidateTex = DSGXSoftwareRendererInvalidateTex;
226 renderer->d.setRAM = DSGXSoftwareRendererSetRAM;
227 renderer->d.drawScanline = DSGXSoftwareRendererDrawScanline;
228 renderer->d.getScanline = DSGXSoftwareRendererGetScanline;
229}
230
231static void DSGXSoftwareRendererInit(struct DSGXRenderer* renderer) {
232 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
233 DSGXSoftwarePolygonListInit(&softwareRenderer->activePolys, DS_GX_POLYGON_BUFFER_SIZE / 4);
234 DSGXSoftwareEdgeListInit(&softwareRenderer->activeEdges, DS_GX_POLYGON_BUFFER_SIZE);
235 DSGXSoftwareSpanListInit(&softwareRenderer->activeSpans, DS_GX_POLYGON_BUFFER_SIZE / 2);
236 softwareRenderer->bucket = anonymousMemoryMap(sizeof(*softwareRenderer->bucket) * DS_GX_POLYGON_BUFFER_SIZE);
237 softwareRenderer->scanlineCache = anonymousMemoryMap(sizeof(color_t) * DS_VIDEO_VERTICAL_PIXELS * DS_VIDEO_HORIZONTAL_PIXELS);
238}
239
240static void DSGXSoftwareRendererReset(struct DSGXRenderer* renderer) {
241 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
242 softwareRenderer->flushPending = false;
243}
244
245static void DSGXSoftwareRendererDeinit(struct DSGXRenderer* renderer) {
246 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
247 DSGXSoftwarePolygonListDeinit(&softwareRenderer->activePolys);
248 DSGXSoftwareEdgeListDeinit(&softwareRenderer->activeEdges);
249 DSGXSoftwareSpanListDeinit(&softwareRenderer->activeSpans);
250 mappedMemoryFree(softwareRenderer->bucket, sizeof(*softwareRenderer->bucket) * DS_GX_POLYGON_BUFFER_SIZE);
251 mappedMemoryFree(softwareRenderer->scanlineCache, sizeof(color_t) * DS_VIDEO_VERTICAL_PIXELS * DS_VIDEO_HORIZONTAL_PIXELS);
252}
253
254static void DSGXSoftwareRendererInvalidateTex(struct DSGXRenderer* renderer, int slot) {
255 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
256 // TODO
257}
258
259static void DSGXSoftwareRendererSetRAM(struct DSGXRenderer* renderer, struct DSGXVertex* verts, struct DSGXPolygon* polys, unsigned polyCount) {
260 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
261
262 softwareRenderer->flushPending = true;
263 softwareRenderer->verts = verts;
264 DSGXSoftwarePolygonListClear(&softwareRenderer->activePolys);
265 DSGXSoftwareEdgeListClear(&softwareRenderer->activeEdges);
266 unsigned i;
267 for (i = 0; i < polyCount; ++i) {
268 struct DSGXSoftwarePolygon* poly = DSGXSoftwarePolygonListAppend(&softwareRenderer->activePolys);
269 struct DSGXSoftwareEdge* edge = DSGXSoftwareEdgeListAppend(&softwareRenderer->activeEdges);
270 poly->poly = &polys[i];
271 poly->texFormat = DSGXTexParamsGetFormat(poly->poly->texParams);
272 poly->texW = 8 << DSGXTexParamsGetSSize(poly->poly->texParams);
273 poly->texH = 8 << DSGXTexParamsGetTSize(poly->poly->texParams);
274 switch (poly->texFormat) {
275 case 0:
276 case 7:
277 poly->texBase = NULL;
278 poly->palBase = NULL;
279 break;
280 case 2:
281 poly->texBase = &renderer->tex[DSGXTexParamsGetVRAMBase(poly->poly->texParams) >> VRAM_BLOCK_OFFSET][(DSGXTexParamsGetVRAMBase(poly->poly->texParams) << 2) & 0xFFFF];
282 poly->palBase = &renderer->texPal[poly->poly->palBase >> 12][(poly->poly->palBase << 2) & 0x1FFF];
283 break;
284 default:
285 poly->texBase = &renderer->tex[DSGXTexParamsGetVRAMBase(poly->poly->texParams) >> VRAM_BLOCK_OFFSET][(DSGXTexParamsGetVRAMBase(poly->poly->texParams) << 2) & 0xFFFF];
286 poly->palBase = &renderer->texPal[poly->poly->palBase >> 11][(poly->poly->palBase << 3) & 0x1FFF];
287 break;
288 }
289 edge->polyId = i;
290
291 struct DSGXVertex* v0 = &verts[poly->poly->vertIds[0]];
292 struct DSGXVertex* v1;
293
294 int v;
295 for (v = 1; v < poly->poly->verts; ++v) {
296 v1 = &verts[poly->poly->vertIds[v]];
297 if (v0->vy >= v1->vy) {
298 edge->y0 = SCREEN_SIZE - v0->vy;
299 edge->x0 = v0->vx;
300 edge->w0 = v0->vw;
301 _expandColor(v0->color, &edge->cr0, &edge->cg0, &edge->cb0);
302 edge->s0 = v0->vs;
303 edge->t0 = v0->vt;
304
305 edge->y1 = SCREEN_SIZE - v1->vy;
306 edge->x1 = v1->vx;
307 edge->w1 = v1->vw;
308 _expandColor(v1->color, &edge->cr1, &edge->cg1, &edge->cb1);
309 edge->s1 = v1->vs;
310 edge->t1 = v1->vt;
311 } else {
312 edge->y0 = SCREEN_SIZE - v1->vy;
313 edge->x0 = v1->vx;
314 edge->w0 = v1->vw;
315 _expandColor(v1->color, &edge->cr0, &edge->cg0, &edge->cb0);
316 edge->s0 = v1->vs;
317 edge->t0 = v1->vt;
318
319 edge->y1 = SCREEN_SIZE - v0->vy;
320 edge->x1 = v0->vx;
321 edge->w1 = v0->vw;
322 _expandColor(v0->color, &edge->cr1, &edge->cg1, &edge->cb1);
323 edge->s1 = v0->vs;
324 edge->t1 = v0->vt;
325 }
326
327 edge = DSGXSoftwareEdgeListAppend(&softwareRenderer->activeEdges);
328 edge->polyId = i;
329 v0 = v1;
330 }
331
332 v1 = &verts[poly->poly->vertIds[0]];
333 if (v0->vy >= v1->vy) {
334 edge->y0 = SCREEN_SIZE - v0->vy;
335 edge->x0 = v0->vx;
336 edge->w0 = v0->vw;
337 _expandColor(v0->color, &edge->cr0, &edge->cg0, &edge->cb0);
338 edge->s0 = v0->vs;
339 edge->t0 = v0->vt;
340
341 edge->y1 = SCREEN_SIZE - v1->vy;
342 edge->x1 = v1->vx;
343 edge->w1 = v1->vw;
344 _expandColor(v1->color, &edge->cr1, &edge->cg1, &edge->cb1);
345 edge->s1 = v1->vs;
346 edge->t1 = v1->vt;
347 } else {
348 edge->y0 = SCREEN_SIZE - v1->vy;
349 edge->x0 = v1->vx;
350 edge->w0 = v1->vw;
351 _expandColor(v1->color, &edge->cr0, &edge->cg0, &edge->cb0);
352 edge->s0 = v1->vs;
353 edge->t0 = v1->vt;
354
355 edge->y1 = SCREEN_SIZE - v0->vy;
356 edge->x1 = v0->vx;
357 edge->w1 = v0->vw;
358 _expandColor(v0->color, &edge->cr1, &edge->cg1, &edge->cb1);
359 edge->s1 = v0->vs;
360 edge->t1 = v0->vt;
361 }
362 }
363 qsort(DSGXSoftwareEdgeListGetPointer(&softwareRenderer->activeEdges, 0), DSGXSoftwareEdgeListSize(&softwareRenderer->activeEdges), sizeof(struct DSGXSoftwareEdge), _edgeSort);
364}
365
366static void DSGXSoftwareRendererDrawScanline(struct DSGXRenderer* renderer, int y) {
367 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
368 if (!softwareRenderer->flushPending) {
369 return;
370 }
371 DSGXSoftwareSpanListClear(&softwareRenderer->activeSpans);
372 memset(softwareRenderer->bucket, 0, sizeof(*softwareRenderer->bucket) * DS_GX_POLYGON_BUFFER_SIZE);
373 int i;
374 for (i = DSGXSoftwareEdgeListSize(&softwareRenderer->activeEdges); i; --i) {
375 size_t idx = i - 1;
376 struct DSGXSoftwareEdge* edge = DSGXSoftwareEdgeListGetPointer(&softwareRenderer->activeEdges, idx);
377 if (edge->y1 >> 12 < y) {
378 DSGXSoftwareEdgeListShift(&softwareRenderer->activeEdges, idx, 1);
379 continue;
380 } else if (edge->y0 >> 12 > y) {
381 continue;
382 }
383
384 unsigned poly = edge->polyId;
385 struct DSGXSoftwareSpan* span = softwareRenderer->bucket[poly];
386 if (span && !span->ep[1].w) {
387 _edgeToSpan(span, edge, 1, y);
388 softwareRenderer->bucket[poly] = NULL;
389 } else if (!span) {
390 span = DSGXSoftwareSpanListAppend(&softwareRenderer->activeSpans);
391 memset(&span->ep[1], 0, sizeof(span->ep[1]));
392 span->poly = DSGXSoftwarePolygonListGetPointer(&softwareRenderer->activePolys, poly);
393 if (!_edgeToSpan(span, edge, 0, y)) {
394 // Horizontal line
395 DSGXSoftwareSpanListShift(&softwareRenderer->activeSpans, DSGXSoftwareSpanListSize(&softwareRenderer->activeSpans) - 1, 1);
396 } else {
397 softwareRenderer->bucket[poly] = span;
398 }
399 }
400 }
401 qsort(DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, 0), DSGXSoftwareSpanListSize(&softwareRenderer->activeSpans), sizeof(struct DSGXSoftwareSpan), _spanSort);
402
403 color_t* scanline = &softwareRenderer->scanlineCache[DS_VIDEO_HORIZONTAL_PIXELS * y];
404
405 int nextSpanX = DS_VIDEO_HORIZONTAL_PIXELS;
406 if (DSGXSoftwareSpanListSize(&softwareRenderer->activeSpans)) {
407 nextSpanX = DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, DSGXSoftwareSpanListSize(&softwareRenderer->activeSpans) - 1)->ep[0].x;
408 nextSpanX >>= 12;
409 }
410 for (i = 0; i < DS_VIDEO_HORIZONTAL_PIXELS; ++i) {
411 struct DSGXSoftwareSpan* span = NULL;
412 struct DSGXSoftwareEndpoint ep;
413 int32_t depth = INT32_MIN;
414 scanline[i] = FLAG_UNWRITTEN;
415 if (i >= nextSpanX) {
416 size_t nextSpanId = DSGXSoftwareSpanListSize(&softwareRenderer->activeSpans);
417 span = DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, nextSpanId - 1);
418 while (i > (span->ep[1].x >> 12) || !span->ep[1].x) {
419 DSGXSoftwareSpanListShift(&softwareRenderer->activeSpans, nextSpanId - 1, 1);
420 --nextSpanId;
421 if (!nextSpanId) {
422 nextSpanX = DS_VIDEO_HORIZONTAL_PIXELS;
423 span = NULL;
424 break;
425 }
426 span = DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, nextSpanId - 1);
427 nextSpanX = span->ep[0].x >> 12;
428 }
429 if (i < nextSpanX) {
430 span = NULL;
431 } else {
432 struct DSGXSoftwareSpan* testSpan = DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, nextSpanId - 1);
433 while (i > (testSpan->ep[0].x >> 12)) {
434 if (i <= (testSpan->ep[1].x >> 12)) {
435 _lerpEndpoint(testSpan, &ep, i);
436 color_t color = _lookupColor(&ep, testSpan->poly);
437 if (scanline[i] == FLAG_UNWRITTEN) {
438 scanline[i] = color;
439 }
440 if (ep.w >= depth) {
441 depth = ep.w;
442 span = testSpan;
443 if (color != FLAG_UNWRITTEN) {
444 scanline[i] = color;
445 }
446 }
447 }
448 --nextSpanId;
449 if (!nextSpanId) {
450 break;
451 }
452 testSpan = DSGXSoftwareSpanListGetPointer(&softwareRenderer->activeSpans, nextSpanId - 1);
453 }
454 }
455 }
456 }
457 if (y == DS_VIDEO_VERTICAL_PIXELS - 1) {
458 softwareRenderer->flushPending = false;
459 }
460}
461
462static void DSGXSoftwareRendererGetScanline(struct DSGXRenderer* renderer, int y, color_t** output) {
463 struct DSGXSoftwareRenderer* softwareRenderer = (struct DSGXSoftwareRenderer*) renderer;
464 *output = &softwareRenderer->scanlineCache[DS_VIDEO_HORIZONTAL_PIXELS * y];
465}