Add some functions needed fore encoding LSS16 files

Signed-off-by: Mattias Andrée <m@maandree.se>

9 files changed, 494 insertions, 22 deletions

diff --git a/Makefile b/Makefile
index 4aa5329..048aeee 100644
--- a/Makefile
+++ b/Makefile
@@ -22,7 +22,11 @@ BIN =\
 OBJ_LIB =\
 	liblss16_decoder_init.o\
 	liblss16_decode_to_colour_index.o\
-	liblss16_decode_strerror.o
+	liblss16_decode_strerror.o\
+	liblss16_encoder_init.o\
+	liblss16_encode_from_colour_index.o\
+	liblss16_encode_strerror.o\
+	liblss16_optimise.o
 
 OBJ =\
 	$(OBJ_LIB)\
diff --git a/TODO b/TODO
index df2a093..e059718 100644
--- a/TODO
+++ b/TODO
@@ -1,3 +1,3 @@
-Write encoder
+Write ppmtolss16
 Write man pages
 Write README
diff --git a/liblss16.h b/liblss16.h
index cf51ec0..12d7e7a 100644
--- a/liblss16.h
+++ b/liblss16.h
@@ -104,6 +104,51 @@ enum liblss16_decode_error {
 
 
 /**
+ * Image encoding state
+ */
+enum liblss16_encode_state {
+	/**
+	 * Still encoding
+	 */
+	LIBLSS16_ENCODE_RUNNING,
+
+	/**
+	 * Encodig done
+	 */
+	LIBLSS16_ENCODE_DONE,
+
+	/**
+	 * Error occured while encoding
+	 */
+	LIBLSS16_ENCODE_ERROR
+};
+
+
+/**
+ * Error values for image encoding
+ */
+enum liblss16_encode_error {
+	/**
+	 * The image has zero width, zero height,
+	 * or the height exceeds 32767
+	 */
+	LIBLSS16_ENCODE_BAD_IMAGE_SIZE,
+
+	/**
+	 * User specified that colour were encoded in
+	 * 6 bits, however at least one colour value
+	 * had at least one of it it high bits set
+	 */
+	LIBLSS16_ENCODE_BAD_COLOUR,
+
+	/**
+	 * Colour index above 15 specified for a pixel
+	 */
+	LIBLSS16_ENCODE_BAD_COLOUR_INDEX
+};
+
+
+/**
  * sRGB colour values, with transfer function applied,
  * encoded in values in [0, 255]
  */
@@ -126,9 +171,9 @@ struct liblss16_colour {
 
 
 /**
- * Decode state
+ * Image header
  */
-struct liblss16_decoder {
+struct liblss16_header {
 	/**
 	 * The width of the raster
 	 */
@@ -143,7 +188,17 @@ struct liblss16_decoder {
 	 * Image colour map
 	 */
 	struct liblss16_colour colour_map[16];
+};
+
 
+/**
+ * Decode state
+ */
+struct liblss16_decoder {
+	/**
+	 * Image header
+	 */
+	struct liblss16_header image;
 
 	/**
 	 * For internal use
@@ -161,6 +216,23 @@ struct liblss16_decoder {
 
 
 /**
+ * Encode state
+ *
+ * Should be considered opaque
+ */
+struct liblss16_encoder {
+	struct liblss16_header header;
+	uint16_t x_rem;
+	uint16_t y_rem;
+	uint16_t repetition;
+	uint8_t header_position;
+	uint8_t previous;
+	uint8_t nbuffered;
+	uint8_t buffered[6];
+};
+
+
+/**
  * Initialise a decoder
  * 
  * @param  decoder  The decoder
@@ -169,6 +241,8 @@ void liblss16_decoder_init(struct liblss16_decoder *decoder);
 
 
 /**
+ * Decode an LSS16 file
+ * 
  * @param   decoder       Decoder state, must have been initialised with
  *                        `liblss16_decoder_init` before the first call
  * @param   data          Data to decode image from (may be partial)
@@ -179,7 +253,8 @@ void liblss16_decoder_init(struct liblss16_decoder *decoder);
  *                        for the pixels in the image. They are returned
  *                        primarily from to the top down and secondarily
  *                        from left to right.
- * @param   pixels_size   The number of elements that may be stored in `pixels`
+ * @param   pixels_size   The number of elements that may be stored in `pixels`,
+ *                        must be at least 1
  * @param   npixels_out   Output parameter for the number of elements stored
  *                        in `pixels`. Always set.
  * @param   error_out     Output parameter for the error; only set if
@@ -213,4 +288,73 @@ __attribute__((__const__))
 const char *liblss16_decode_strerror(enum liblss16_decode_error error);
 
 
+/**
+ * Initialise an encoder
+ *
+ * @param   encoder    The encoder
+ * @param   header     Image information
+ * @param   rgb6       If non-zero, colour values in `header->colour_map` are
+ *                     encoded in 6 bits (the limitation of the LSS16 format)
+ *                     rather than 8 bits
+ * @param   error_out  Output parameter for the error; only set when -1 is
+ *                     returned; may be `NULL`
+ * @return             0 on success, -1 on failure
+ */
+int liblss16_encoder_init(struct liblss16_encoder *encoder, const struct liblss16_header *header,
+                          int rgb6, enum liblss16_encode_error *error_out);
+
+
+/**
+ * Encode an LSS16 file
+ * 
+ * @param   encoder        Encoder state, must have been initialised with
+ *                         `liblss16_encoder_init` before the first call
+ * @param   buffer         Output buffer for the image data
+ * @param   size           Size of `buffer`
+ * @param   written_out    The number of bytes written to `size`, must be at least 1
+ * @param   pixels         Buffer with pixels to encode; the pixels are to preencoded
+ *                         (before the function is called) with the colour index of
+ *                         each pixel. Pixels are input primarily from to the top
+ *                         down and secondarily from left to right.
+ * @param   npixels        The number of provided pixels
+ * @param   nconsumed_out  Output parameter for the number of pixels consumed into
+ *                         to state of the encoder
+ * @param   error_out      Output parameter for the error; only set if
+ *                         `LIBLSS16_ENCODE_ERROR` is returned; may be `NULL`
+ * @return                 The processing state: normally `LIBLSS16_ENCODE_RUNNING`,
+ *                         but `LIBLSS16_ENCODE_DONE` when the image has been
+ *                         fully encoded, and `LIBLSS16_ENCODE_ERROR` on error
+ */
+enum liblss16_encode_state liblss16_encode_from_colour_index(
+	struct liblss16_encoder *encoder, void *buffer, size_t size,
+	size_t *written_out, const uint8_t *pixels, size_t npixels,
+	size_t *nconsumed_out, enum liblss16_encode_error *error_out);
+
+
+/**
+ * Get error description for an error code
+ * 
+ * @param   error  The error code
+ * @return         The error description
+ */
+#if defined(__GNUC__)
+__attribute__((__const__))
+#endif
+const char *liblss16_encode_strerror(enum liblss16_encode_error error);
+
+
+/**
+ * Optimise and image
+ * 
+ * @param  header  The image metadata
+ * @param  pixel   Buffer with pixels; the pixels are to encoded with the
+ *                 colour index of each pixel. Pixels are encoded primarily
+ *                 from to the top down and secondarily from left to right.
+ * 
+ * Both `pixels` and `header->colour_map` may be rewritten
+ * (to an equivalent image with at least as good compression with LSS16)
+ */
+void liblss16_optimise(struct liblss16_header *header, uint8_t *pixels);
+
+
 #endif
diff --git a/liblss16_decode_to_colour_index.c b/liblss16_decode_to_colour_index.c
index 3d184c2..a552289 100644
--- a/liblss16_decode_to_colour_index.c
+++ b/liblss16_decode_to_colour_index.c
@@ -85,7 +85,7 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 		/* fall through */
 
 	case 4:
-		decoder->width = (uint16_t)*data++;
+		decoder->image.width = (uint16_t)*data++;
 		++*consumed_out;
 		++decoder->internal.init_state;
 		if (!--length)
@@ -93,7 +93,7 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 		/* fall through */
 
 	case 5:
-		decoder->width |= (uint16_t)((uint16_t)*data++ << 8);
+		decoder->image.width |= (uint16_t)((uint16_t)*data++ << 8);
 		++*consumed_out;
 		++decoder->internal.init_state;
 		if (!--length)
@@ -101,7 +101,7 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 		/* fall through */
 
 	case 6:
-		decoder->height = (uint16_t)*data++;
+		decoder->image.height = (uint16_t)*data++;
 		++*consumed_out;
 		++decoder->internal.init_state;
 		if (!--length)
@@ -109,13 +109,13 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 		/* fall through */
 
 	case 7:
-		decoder->height |= (uint16_t)((uint16_t)*data++ << 8);
+		decoder->image.height |= (uint16_t)((uint16_t)*data++ << 8);
 		++*consumed_out;
 		++decoder->internal.init_state;
 
-		decoder->internal.x_rem = decoder->width;
-		decoder->internal.y_rem = decoder->height;
-		if (!decoder->width || !decoder->height || decoder->height >> 15) {
+		decoder->internal.x_rem = decoder->image.width;
+		decoder->internal.y_rem = decoder->image.height;
+		if (!decoder->image.width || !decoder->image.height || decoder->image.height >> 15) {
 			if (error_out)
 				*error_out = LIBLSS16_DECODE_BAD_IMAGE_SIZE;
 			return LIBLSS16_DECODE_ERROR;
@@ -131,13 +131,13 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 			uint8_t value = *data++;
 			++*consumed_out;
 			if (value & 0xC0) {
-				((uint8_t *)decoder->colour_map)[i] = value;
+				((uint8_t *)decoder->image.colour_map)[i] = value;
 				if (error_out)
 					*error_out = LIBLSS16_DECODE_BAD_COLOUR;
 				return LIBLSS16_DECODE_ERROR;
 			} else {
 				value = (uint8_t)(((unsigned)value * 255U + 31U) / 63U);
-				((uint8_t *)decoder->colour_map)[i] = value;
+				((uint8_t *)decoder->image.colour_map)[i] = value;
 			}
 
 			if (!--length)
@@ -184,7 +184,7 @@ liblss16_decode_to_colour_index(struct liblss16_decoder *decoder,
 					}
 					decoder->internal.x_rem -= m;
 					if (!decoder->internal.x_rem) {
-						decoder->internal.x_rem = decoder->width;
+						decoder->internal.x_rem = decoder->image.width;
 						decoder->internal.y_rem--;
 						if (decoder->internal.saved > 1U) {
 							if (error_out)
diff --git a/liblss16_encode_from_colour_index.c b/liblss16_encode_from_colour_index.c
new file mode 100644
index 0000000..1efff36
--- /dev/null
+++ b/liblss16_encode_from_colour_index.c
@@ -0,0 +1,177 @@
+/* See LICENSE file for copyright and license details. */
+#include "liblss16.h"
+#include <string.h>
+#include <stdlib.h>
+
+
+static size_t
+flush_buffer(struct liblss16_encoder *encoder, uint8_t *buffer, size_t size)
+{
+	size_t i;
+	for (i = 0; size && encoder->nbuffered - i > 1U; i += 2U, size--)
+		buffer[i] = (uint8_t)(encoder->buffered[i + 0] | (encoder->buffered[i + 1] << 4));
+	memmove(&encoder->buffered[0], &encoder->buffered[i], encoder->nbuffered - i);
+	return i;
+}
+
+
+enum liblss16_encode_state
+liblss16_encode_from_colour_index(struct liblss16_encoder *encoder, void *buffer_, size_t size,
+                                  size_t *written_out, const uint8_t *pixels, size_t npixels,
+                                  size_t *nconsumed_out, enum liblss16_encode_error *error_out)
+{
+	uint8_t *buffer = buffer_;
+	size_t n;
+
+	*written_out = 0;
+	*nconsumed_out = 0;
+
+	switch (encoder->header_position) {
+	case 0:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)0x3DU;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 1:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)0xF3U;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 2:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)0x13U;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 3:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)0x14U;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 4:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)encoder->header.width;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 5:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)(encoder->header.width >> 8);
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 6:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)encoder->header.height;
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	case 7:
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = (uint8_t)(encoder->header.height >> 8);
+		++*nconsumed_out;
+		encoder->header_position++;
+		/* fall through */
+
+	default:
+		break;
+	}
+
+	while (encoder->header_position < 8U + 16U * 3U) {
+		if (!size--)
+			return LIBLSS16_ENCODE_RUNNING;
+		*buffer++ = ((const uint8_t *)encoder->header.colour_map)[encoder->header_position++];
+		++*nconsumed_out;
+		encoder->header_position++;
+	}
+
+	if (encoder->nbuffered > 1U) {
+		n = flush_buffer(encoder, buffer, size);
+		buffer = &buffer[n];
+		size -= n;
+		*written_out += n;
+		if (encoder->nbuffered > 1U)
+			return LIBLSS16_ENCODE_RUNNING;
+		if (!encoder->y_rem) {
+			if (encoder->nbuffered)
+				abort();
+			return LIBLSS16_ENCODE_DONE;
+		}
+	}
+
+	while (npixels--) {
+		if (*pixels == encoder->previous) {
+			encoder->repetition++;
+		} else if (*pixels > 15U) {
+			if (error_out)
+				*error_out = LIBLSS16_ENCODE_BAD_COLOUR_INDEX;
+			return LIBLSS16_ENCODE_ERROR;
+		} else {
+			if (!encoder->repetition) {
+				/* do nothing */
+			} else if (encoder->repetition < 16U) {
+				encoder->buffered[encoder->nbuffered++] = encoder->previous;
+				encoder->buffered[encoder->nbuffered++] = (uint8_t)encoder->repetition;
+			} else {
+				unsigned value = encoder->repetition - 16U;
+				encoder->buffered[encoder->nbuffered++] = encoder->previous;
+				encoder->buffered[encoder->nbuffered++] = 0;
+				encoder->buffered[encoder->nbuffered++] = (uint8_t)(value & 15U);
+				encoder->buffered[encoder->nbuffered++] = (uint8_t)(value >> 4);
+			}
+			encoder->buffered[encoder->nbuffered++] = *pixels;
+			encoder->previous = *pixels;
+			encoder->repetition = 0;
+
+			n = flush_buffer(encoder, buffer, size);
+			buffer = &buffer[n];
+			size -= n;
+			*written_out += n;
+			if (encoder->nbuffered > 1U)
+				return LIBLSS16_ENCODE_RUNNING;
+		}
+		++pixels;
+		++*nconsumed_out;
+
+		if (!--encoder->x_rem) {
+			encoder->previous = 0;
+			encoder->repetition = 0;
+			encoder->x_rem = encoder->header.width;
+			encoder->y_rem--;
+			if (encoder->nbuffered & 1)
+				encoder->buffered[encoder->nbuffered++] = 0;
+
+			n = flush_buffer(encoder, buffer, size);
+			buffer = &buffer[n];
+			size -= n;
+			*written_out += n;
+			if (encoder->nbuffered > 1U)
+				return LIBLSS16_ENCODE_RUNNING;
+			else if (encoder->nbuffered)
+				abort();
+
+			if (!encoder->y_rem)
+				return LIBLSS16_ENCODE_DONE;
+		}
+	}
+
+	return LIBLSS16_ENCODE_RUNNING;
+}
diff --git a/liblss16_encode_strerror.c b/liblss16_encode_strerror.c
new file mode 100644
index 0000000..a5fcd49
--- /dev/null
+++ b/liblss16_encode_strerror.c
@@ -0,0 +1,21 @@
+/* See LICENSE file for copyright and license details. */
+#include "liblss16.h"
+
+
+const char *
+liblss16_encode_strerror(enum liblss16_encode_error error)
+{
+	switch (error) {
+	case LIBLSS16_ENCODE_BAD_IMAGE_SIZE:
+		return "Unencodable image: unsupported image size";
+
+	case LIBLSS16_ENCODE_BAD_COLOUR:
+		return "Invalid colour map: 6-bit colours encoded with additional bits";
+
+	case LIBLSS16_ENCODE_BAD_COLOUR_INDEX:
+		return "Invalid image: colour index out of range";
+
+	default:
+		return "Unrecognised error";
+	}
+}
diff --git a/liblss16_encoder_init.c b/liblss16_encoder_init.c
new file mode 100644
index 0000000..037cd8e
--- /dev/null
+++ b/liblss16_encoder_init.c
@@ -0,0 +1,46 @@
+/* See LICENSE file for copyright and license details. */
+#include "liblss16.h"
+#include <string.h>
+
+
+int
+liblss16_encoder_init(struct liblss16_encoder *encoder, const struct liblss16_header *header,
+		      int rgb6, enum liblss16_encode_error *error_out)
+{
+	int i;
+
+	memset(encoder, 0, sizeof(*encoder));
+	memcpy(&encoder->header, header, sizeof(*header));
+
+	if (!encoder->header.width || !encoder->header.height || encoder->header.height >> 15) {
+		if (error_out)
+			*error_out = LIBLSS16_ENCODE_BAD_IMAGE_SIZE;
+		return -1;
+	}
+
+	if (rgb6) {
+		uint8_t or = 0;
+		for (i = 0; i < 16; i++) {
+			or |= encoder->header.colour_map[i].r;
+			or |= encoder->header.colour_map[i].g;
+			or |= encoder->header.colour_map[i].b;
+		}
+		if (or & 0xC0) {
+			if (error_out)
+				*error_out = LIBLSS16_ENCODE_BAD_COLOUR;
+			return -1;
+		}
+	} else {
+		struct liblss16_colour *map = encoder->header.colour_map;
+		for (i = 0; i < 16; i++) {
+			map[i].r = (uint8_t)(((unsigned)map[i].r * 63U + 127U) / 255U);
+			map[i].g = (uint8_t)(((unsigned)map[i].g * 63U + 127U) / 255U);
+			map[i].b = (uint8_t)(((unsigned)map[i].b * 63U + 127U) / 255U);
+		}
+	}
+
+	encoder->x_rem = encoder->header.width;
+	encoder->y_rem = encoder->header.height;
+
+	return 0;
+}
diff --git a/liblss16_optimise.c b/liblss16_optimise.c
new file mode 100644
index 0000000..911fcd2
--- /dev/null
+++ b/liblss16_optimise.c
@@ -0,0 +1,80 @@
+/* See LICENSE file for copyright and license details. */
+#include "liblss16.h"
+#include <string.h>
+
+
+void
+liblss16_optimise(struct liblss16_header *header, uint8_t *pixels)
+{
+	uint8_t remap[16], unmap[16], ncolours, colour, preferred;
+	unsigned x, y, count, width;
+	size_t p, n;
+	int32_t zero[16], nonzero[16];
+	int32_t zero_penalty, least;
+
+	for (x = 0; x < 16U; x++) {
+		remap[x] = (uint8_t)x;
+		unmap[x] = 0;
+	}
+
+	memset(zero, 0, sizeof(zero));
+	memset(nonzero, 0, sizeof(nonzero));
+
+	for (x = 0; x < 15U; x++) {
+		if (unmap[x])
+			continue;
+		header->colour_map[ncolours++] = header->colour_map[x];
+		for (y = x + 1U; y < 16U; y++) {
+			if (header->colour_map[y].r != header->colour_map[x].r ||
+			    header->colour_map[y].g != header->colour_map[x].g ||
+			    header->colour_map[y].b != header->colour_map[x].b)
+				continue;
+			unmap[y] = 1;
+			remap[y] = ncolours;
+		}
+	}
+
+	width = (unsigned)header->width;
+	width = width < 17U ? width : 17U;
+	for (y = 0, p = 0; y < (unsigned)header->height; y++) {
+		colour = remap[pixels[p]];
+		count = 1U;
+		for (x = 1U; x < width; x++, p++) {
+			if (remap[pixels[p]] != colour)
+				break;
+			count += 1U;
+		}
+		p += (size_t)header->width - (size_t)x;
+		zero[colour] += count < 16U ? 2 : 3;
+		nonzero[colour] += count == 1 ? 1 : count < 17 ? 3 : 4;
+	}
+
+	least = zero[0] - nonzero[0];
+	preferred = 0U;
+	for (x = 1U; x < (unsigned)ncolours; x++) {
+		zero_penalty = zero[x] - nonzero[x];
+		if (zero_penalty < least) {
+			least = zero_penalty;
+			preferred = (uint8_t)x;
+		}
+	}
+
+	if (preferred) {
+		struct liblss16_colour tc;
+		uint8_t t8;
+		tc = header->colour_map[preferred];
+		header->colour_map[preferred] = header->colour_map[0];
+		header->colour_map[0] = tc;
+		t8 = remap[preferred];
+		remap[preferred] = remap[0];
+		remap[0] = t8;
+	}
+
+	n = p;
+	for (n = p, p = 0; p < n; p++)
+		pixels[p] = remap[pixels[p]];
+
+	memset(&header->colour_map[ncolours],
+	       header->colour_map[ncolours - 1U].b,
+	       (16U - ncolours) * sizeof(*header->colour_map));
+}
diff --git a/lss16toppm.c b/lss16toppm.c
index db4d448..6dcff62 100644
--- a/lss16toppm.c
+++ b/lss16toppm.c
@@ -92,14 +92,14 @@ main(int argc, char *argv[])
 
 			if (!head_printed) {
 				head_printed = 1;
-				len = sprintf(wbuf, "P6\n%u %u\n255\n", decoder.width, decoder.height);
+				len = sprintf(wbuf, "P6\n%u %u\n255\n", decoder.image.width, decoder.image.height);
 				if (len < 0 || (size_t)len >= sizeof(wbuf))
 					abort();
 				pending = (size_t)len;
 				if (print_colour_map) {
-					for (i = 0; i < sizeof(decoder.colour_map) / sizeof(*decoder.colour_map); i++) {
-						fprintf(stderr, "#%02x%02x%02x=%zu\n", decoder.colour_map[i].r,
-						        decoder.colour_map[i].g, decoder.colour_map[i].b, i);
+					for (i = 0; i < sizeof(decoder.image.colour_map) / sizeof(*decoder.image.colour_map); i++) {
+						fprintf(stderr, "#%02x%02x%02x=%zu\n", decoder.image.colour_map[i].r,
+						        decoder.image.colour_map[i].g, decoder.image.colour_map[i].b, i);
 					}
 				}
 			}
@@ -108,9 +108,9 @@ main(int argc, char *argv[])
 					writeall(wbuf, pending);
 					pending = 0;
 				}
-				wbuf[pending++] = (char)decoder.colour_map[pixels[i]].r;
-				wbuf[pending++] = (char)decoder.colour_map[pixels[i]].g;
-				wbuf[pending++] = (char)decoder.colour_map[pixels[i]].b;
+				wbuf[pending++] = (char)decoder.image.colour_map[pixels[i]].r;
+				wbuf[pending++] = (char)decoder.image.colour_map[pixels[i]].g;
+				wbuf[pending++] = (char)decoder.image.colour_map[pixels[i]].b;
 			}
 		}
 	}