Add error diffusion to palette based rendering. Only used for bitmap and scaled bitmap plots. Doesn't do serpentine path, since that would need changes to the common bitmap rendering code.

5 files changed, 206 insertions, 29 deletions

diff --git a/include/palette.h b/include/palette.h
index 845c1bc..f975ef2 100644
--- a/include/palette.h
+++ b/include/palette.h
@@ -27,21 +27,35 @@ struct nsfb_palette_s {
 	enum nsfb_palette_type_e type; /**< Palette type */
 	uint8_t last; /**< Last used palette index */
 	nsfb_colour_t data[256]; /**< Palette for index modes */
+
+	bool dither; /**< Whether to use error diffusion */
+	struct {
+		int width; /**< Length of error value buffer ring*/
+		int current; /**< Current pos in ring buffer*/
+		int *data; /**< Ring buffer error values */
+		int data_len; /**< Max size of ring */
+	} dither_ctx;
 };
 
+
 /** Create an empty palette object. */
-bool nsfb_palette_new(struct nsfb_palette_s **palette);
+bool nsfb_palette_new(struct nsfb_palette_s **palette, int width);
 
 /** Free a palette object. */
 void nsfb_palette_free(struct nsfb_palette_s *palette);
 
+/** Init error diffusion for a plot. */
+void nsfb_palette_dither_init(struct nsfb_palette_s *palette, int width);
+
+/** Finalise error diffusion after a plot. */
+void nsfb_palette_dither_fini(struct nsfb_palette_s *palette);
+
 /** Generate libnsfb 8bpp default palette. */
 void nsfb_palette_generate_nsfb_8bpp(struct nsfb_palette_s *palette);
 
-
-static inline uint8_t nsfb_palette_best_match(
-		const struct nsfb_palette_s *palette,
-		nsfb_colour_t c)
+/** Find best palette match for given colour. */
+static inline uint8_t nsfb_palette_best_match(struct nsfb_palette_s *palette,
+		nsfb_colour_t c, int *r_error, int *g_error, int *b_error)
 {
 	uint8_t best_col = 0;
 
@@ -68,6 +82,9 @@ static inline uint8_t nsfb_palette_best_match(
 
 		best_col = col;
 		best_distance = cur_distance;
+		*r_error = dr;
+		*g_error = dg;
+		*b_error = db;
 
 		/* Index into grayscale part */
 		col = (( c        & 0xFF) +
@@ -82,6 +99,9 @@ static inline uint8_t nsfb_palette_best_match(
 		if (cur_distance < best_distance) {
 			best_distance = cur_distance;
 			best_col = col;
+			*r_error = dr;
+			*g_error = dg;
+			*b_error = db;
 		}
 		break;
 
@@ -97,6 +117,9 @@ static inline uint8_t nsfb_palette_best_match(
 			if (cur_distance < best_distance) {
 				best_distance = cur_distance;
 				best_col = col;
+				*r_error = dr;
+				*g_error = dg;
+				*b_error = db;
 			}
 		}
 		break;
@@ -108,4 +131,101 @@ static inline uint8_t nsfb_palette_best_match(
         return best_col;
 }
 
+/** Find best palette match for given colour, with error diffusion. */
+static inline uint8_t nsfb_palette_best_match_dither(
+		struct nsfb_palette_s *palette, nsfb_colour_t c)
+{
+	int r, g, b;
+	int current;
+	int error;
+	int width = palette->dither_ctx.width;
+	uint8_t best_col_index;
+
+	if (palette == NULL)
+		return 0;
+
+	if (palette->dither == false)
+		return nsfb_palette_best_match(palette, c, &r, &g, &b);
+
+	current = palette->dither_ctx.current;
+
+	/* Get RGB components of colour, and apply error */
+	r = ( c        & 0xFF) + palette->dither_ctx.data[current    ];
+	g = ((c >>  8) & 0xFF) + palette->dither_ctx.data[current + 1];
+	b = ((c >> 16) & 0xFF) + palette->dither_ctx.data[current + 2];
+
+	/* Clamp new RGB components to range */
+	if (r <   0) r =   0;
+	if (r > 255) r = 255;
+	if (g <   0) g =   0;
+	if (g > 255) g = 255;
+	if (b <   0) b =   0;
+	if (b > 255) b = 255;
+
+	/* Reset error diffusion slots to 0 */
+	palette->dither_ctx.data[current    ] = 0;
+	palette->dither_ctx.data[current + 1] = 0;
+	palette->dither_ctx.data[current + 2] = 0;
+
+	/* Rebuild colour from modified components */
+	c = r + (g << 8) + (b << 16);
+
+	/* Get best match for pixel, and find errors for each component */
+	best_col_index = nsfb_palette_best_match(palette, c, &r, &g, &b);
+
+	/* Advance one set of error diffusion slots */
+	current += 3;
+	if (current >= width)
+		current = 0;
+	palette->dither_ctx.current = current;
+
+	/* Save errors
+	 *
+	 *       [*]-[N]
+	 *      / | \
+	 *   [l]-[m]-[r]
+	 */
+	error = current;
+
+	/* Error for [N] (next) */
+	if (error != 0) {
+		/* The pixel exists */
+		palette->dither_ctx.data[error    ] += r * 7 / 16;
+		palette->dither_ctx.data[error + 1] += g * 7 / 16;
+		palette->dither_ctx.data[error + 2] += b * 7 / 16;
+	}
+
+	error += width - 2 * 3;
+	if (error >= width)
+		error -= width;
+	/* Error for [l] (below, left) */
+	if (error >= 0 && error != 3) {
+		/* The pixel exists */
+		palette->dither_ctx.data[error    ] += r * 3 / 16;
+		palette->dither_ctx.data[error + 1] += g * 3 / 16;
+		palette->dither_ctx.data[error + 2] += b * 3 / 16;
+	}
+
+	error += 3;
+	if (error >= width)
+		error -= width;
+	/* Error for [m] (below, middle) */
+	palette->dither_ctx.data[error    ] += r * 5 / 16;
+	palette->dither_ctx.data[error + 1] += g * 5 / 16;
+	palette->dither_ctx.data[error + 2] += b * 5 / 16;
+
+	error += 3;
+	if (error >= width)
+		error -= width;
+	/* Error for [r] (below, right) */
+	if (error != 0) {
+		/* The pixel exists */
+		palette->dither_ctx.data[error    ] += r / 16;
+		palette->dither_ctx.data[error + 1] += g / 16;
+		palette->dither_ctx.data[error + 2] += b / 16;
+	}
+
+	return best_col_index;
+}
+
 #endif /* PALETTE_H */
diff --git a/src/palette.c b/src/palette.c
index eba95cd..d600001 100644
--- a/src/palette.c
+++ b/src/palette.c
@@ -13,12 +13,13 @@
 #include <assert.h>
 #include <stdbool.h>
 #include <stdlib.h>
+#include <string.h>
 
 #include "palette.h"
 
 
 /** Create an empty palette object. */
-bool nsfb_palette_new(struct nsfb_palette_s **palette)
+bool nsfb_palette_new(struct nsfb_palette_s **palette, int width)
 {
 	*palette = malloc(sizeof(struct nsfb_palette_s));
 	if (*palette == NULL) {
@@ -28,14 +29,41 @@ bool nsfb_palette_new(struct nsfb_palette_s **palette)
 	(*palette)->type = NSFB_PALETTE_EMPTY;
 	(*palette)->last = 0;
 
+	(*palette)->dither = false;
+	(*palette)->dither_ctx.data_len = width * 3;
+	(*palette)->dither_ctx.data = malloc(width * 3 * sizeof(int));
+	if ((*palette)->dither_ctx.data == NULL) {
+		nsfb_palette_free(*palette);
+		return false;
+	}
+
 	return true;
 }
 
 /** Free a palette object. */
 void nsfb_palette_free(struct nsfb_palette_s *palette)
 {
-	if (palette != NULL)
+	if (palette != NULL) {
+		if (palette->dither_ctx.data != NULL) {
+			free(palette->dither_ctx.data);
+		}
 		free(palette);
+	}
+}
+
+/** Init error diffusion for a plot. */
+void nsfb_palette_dither_init(struct nsfb_palette_s *palette, int width)
+{
+	palette->dither = true;
+	memset(palette->dither_ctx.data, 0, palette->dither_ctx.data_len);
+	palette->dither_ctx.width = width * 3;
+	palette->dither_ctx.current = 0;
+}
+
+/** Finalise error diffusion after a plot. */
+void nsfb_palette_dither_fini(struct nsfb_palette_s *palette)
+{
+	palette->dither = false;
 }
 
 /** Generate libnsfb 8bpp default palette. */
diff --git a/src/plot/8bpp.c b/src/plot/8bpp.c
index 05574d8..0245542 100644
--- a/src/plot/8bpp.c
+++ b/src/plot/8bpp.c
@@ -39,7 +39,7 @@ static uint8_t colour_to_pixel(nsfb_t *nsfb, nsfb_colour_t c)
         if (nsfb->palette == NULL)
                 return 0;
 
-        return nsfb_palette_best_match(nsfb->palette, c);
+        return nsfb_palette_best_match_dither(nsfb->palette, c);
 }
 
 #define PLOT_TYPE uint8_t
diff --git a/src/plot/common.c b/src/plot/common.c
index 185e323..c9f9dc1 100644
--- a/src/plot/common.c
+++ b/src/plot/common.c
@@ -16,6 +16,8 @@
 #error PLOT_LINELEN must be a macro to increment a line length
 #endif
 
+#include "palette.h"
+
 #define SIGN(x)  ((x<0) ?  -1  :  ((x>0) ? 1 : 0))
 
 static bool
@@ -249,8 +251,7 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 	nsfb_bbox_t clipped; /* clipped display */
 
 	/* The part of the scaled image actually displayed is cropped to the
-	 * current context.
-	 */
+	 * current context. */
 	clipped.x0 = x;
 	clipped.y0 = y;
 	clipped.x1 = x + width;
@@ -271,6 +272,10 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 	else
 		rwidth = width;
 
+	if (nsfb->palette != NULL) {
+		nsfb_palette_dither_init(nsfb->palette, rwidth);
+	}
+
 	/* get veritcal (y) and horizontal (x) scale factors; both integer
 	 * part and remainder */
 	dx = bmp_width / width;
@@ -299,7 +304,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 	pvideo = get_xy_loc(nsfb, clipped.x0, clipped.y0);
 	pvideo_limit = pvideo + PLOT_LINELEN(nsfb->linelen) * rheight;
 	if (alpha) {
-		for (; pvideo < pvideo_limit; pvideo += PLOT_LINELEN(nsfb->linelen)) {
+		for (; pvideo < pvideo_limit;
+				pvideo += PLOT_LINELEN(nsfb->linelen)) {
 			/* looping through render area vertically */
 			xoff = xoffs;
 			rx = rxs;
@@ -322,7 +328,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 								xloop)));
 					}
 					/* plot pixel */
-					*(pvideo + xloop) = colour_to_pixel(nsfb, abpixel);
+					*(pvideo + xloop) = colour_to_pixel(
+							nsfb, abpixel);
 				}
 				/* handle horizontal interpolation */
 				xoff += dx;
@@ -341,7 +348,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 			}
 		}
 	} else {
-		for (; pvideo < pvideo_limit; pvideo += PLOT_LINELEN(nsfb->linelen)) {
+		for (; pvideo < pvideo_limit;
+				pvideo += PLOT_LINELEN(nsfb->linelen)) {
 			/* looping through render area vertically */
 			xoff = xoffs;
 			rx = rxs;
@@ -350,7 +358,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 				/* get value of source pixel in question */
 				abpixel = pixel[yoff + xoff];
 				/* plot pixel */
-				*(pvideo + xloop) = colour_to_pixel(nsfb, abpixel);
+				*(pvideo + xloop) = colour_to_pixel(
+						nsfb, abpixel);
 
 				/* handle horizontal interpolation */
 				xoff += dx;
@@ -369,6 +378,11 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc,
 			}
 		}
 	}
+
+	if (nsfb->palette != NULL) {
+		nsfb_palette_dither_fini(nsfb->palette);
+	}
+
 	return true;
 }
 
@@ -391,17 +405,16 @@ bitmap(nsfb_t *nsfb,
         int height = loc->y1 - loc->y0;
         nsfb_bbox_t clipped; /* clipped display */
 
-	if (width == 0 || height == 0)
-		return true;
+        if (width == 0 || height == 0)
+                return true;
 
         /* Scaled bitmaps are handled by a separate function */
         if (width != bmp_width || height != bmp_height)
                 return bitmap_scaled(nsfb, loc, pixel, bmp_width, bmp_height,
                                 bmp_stride, alpha);
 
-        /* The part of the scaled image actually displayed is cropped to the
-         * current context.
-         */
+        /* The part of the image actually displayed is cropped to the
+         * current context. */
         clipped.x0 = x;
         clipped.y0 = y;
         clipped.x1 = x + width;
@@ -416,6 +429,10 @@ bitmap(nsfb_t *nsfb,
         if (width > (clipped.x1 - clipped.x0))
                 width = (clipped.x1 - clipped.x0);
 
+        if (nsfb->palette != NULL) {
+                nsfb_palette_dither_init(nsfb->palette, width);
+        }
+
         xoff = clipped.x0 - x;
         yoff = (clipped.y0 - y) * bmp_stride;
         height = height * bmp_stride + yoff;
@@ -428,16 +445,22 @@ bitmap(nsfb_t *nsfb,
                         for (xloop = 0; xloop < width; xloop++) {
                                 abpixel = pixel[yloop + xloop + xoff];
                                 if ((abpixel & 0xFF000000) != 0) {
-                                	/* pixel is not transparent; have to
-                                	 * plot something */
-                                        if ((abpixel & 0xFF000000) != 0xFF000000) {
-                                        	/* pixel is not opaque; need to
-                                        	 * blend */
-                                                abpixel = nsfb_plot_ablend(abpixel,
-                                                                           pixel_to_colour(nsfb, *(pvideo + xloop)));
+                                        /* pixel is not transparent; have to
+                                         * plot something */
+                                        if ((abpixel & 0xFF000000) !=
+                                                       0xFF000000) {
+                                                /* pixel is not opaque; need to
+                                                 * blend */
+                                                abpixel = nsfb_plot_ablend(
+                                                                abpixel,
+                                                                pixel_to_colour(
+                                                                nsfb,
+                                                                *(pvideo +
+                                                                xloop)));
                                         }
 
-                                        *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel);
+                                        *(pvideo + xloop) = colour_to_pixel(
+                                                        nsfb, abpixel);
                                 }
                         }
                         pvideo += PLOT_LINELEN(nsfb->linelen);
@@ -446,11 +469,17 @@ bitmap(nsfb_t *nsfb,
                 for (yloop = yoff; yloop < height; yloop += bmp_stride) {
                         for (xloop = 0; xloop < width; xloop++) {
                                 abpixel = pixel[yloop + xloop + xoff];
-                                *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel);
+                                *(pvideo + xloop) = colour_to_pixel(
+                                                nsfb, abpixel);
                         }
                         pvideo += PLOT_LINELEN(nsfb->linelen);
                 }
         }
+
+        if (nsfb->palette != NULL) {
+                nsfb_palette_dither_fini(nsfb->palette);
+        }
+
         return true;
 }
 
diff --git a/src/surface/sdl.c b/src/surface/sdl.c
index 7a86dc1..0554e26 100644
--- a/src/surface/sdl.c
+++ b/src/surface/sdl.c
@@ -458,7 +458,7 @@ static int sdl_initialise(nsfb_t *nsfb)
     nsfb->surface_priv = sdl_screen;
 
     if (nsfb->bpp == 8) {
-        nsfb_palette_new(&nsfb->palette);
+        nsfb_palette_new(&nsfb->palette, nsfb->width);
         set_palette(nsfb);
     }