paeth-reference.c

/*-
 * Reference implementation and judging program for the Paeth challenge.
 * Published under CC-BY by Robert Clausecker (FUZxxl).
 */

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static void	 fail(char*, ...);
static int	*generate(int*, int*);
static int	*input(int*, int*);
static void	 display(int, int, const int*);
static void	 paeth(int, int, int*);
static int	 predict(int, int, int);
extern int	 main(int, char*[]);

extern int
main(argc, argv)
	char *argv[];
{
	int x1, y1, *buf1, x2, y2, *buf2;

	srand(time(NULL));

	if (argc != 2 || strlen(argv[1]) != 1)
		goto usage;

	switch (*argv[1]) {
	case 'g':
		buf1 = generate(&x1, &y1);
		display(x1, y1, buf1);

		return EXIT_SUCCESS;

	case 's':
		buf1 = input(&x1, &y1);
		paeth(x1, y1, buf1);
		display(x1, y1, buf1);

		return EXIT_SUCCESS;

	case 'v':
		buf1 = input(&x1, &y1);
		buf2 = input(&x2, &y2);
		if (x1 != x2 || y1 != y2)
			goto invalid;

		paeth(x1, y1, buf1);
		if (memcmp(buf1, buf2, x1 * y1))
			goto invalid;

		fprintf(stderr, "VALID\n");
		return EXIT_SUCCESS;

	default:
		goto usage;
	}

usage:
	fail("usage: %s [gsv]\n", argv[0]);

invalid:
	fail("INVALID\n");
}

static void
fail(msg)
	char *msg;
{
	va_list args;

	va_start(args, msg);
	vfprintf(stderr, msg, args);
	va_end(args);

	exit(EXIT_FAILURE);
}

static int*
generate(x, y)
	int *x, *y;
{
	int i, *buf;

	*x = rand() % 1022 + 2;
	*y = rand() % 1022 + 2;

	buf = malloc(*x * *y * sizeof *buf);
	if (buf == NULL)
		fail("out of memory\n");

	for (i = 0; i < *x * *y; i++)
		buf[i] = rand() % 256;

	return buf;
}

static void
display(x, y, buf)
	const int *buf;
{
	int i;

	printf("%d %d", x, y);

	for (i = 0; i < x * y; i++)
		printf(" %d", buf[i]);

	printf("\n");
}

static int*
input(x, y)
	int *x, *y;
{
	int i, *buf;

	if (scanf("%d %d ", x, y) != 2 || *x < 2 || *y < 2)
		goto invalid;

	buf = malloc(*x * *y * sizeof *buf);
	if (buf == NULL)
		fail("out of memory\n");

	for (i = 0; i < *x * *y; i++)
		if (scanf("%d ", buf + i) != 1 || buf[i] < 0 || buf[i] > 255)
			goto invalid;

	return buf;

invalid:
	fail("INVALID\n");
}

static void
paeth(x, y, ibuf)
	int *ibuf;
{
	int i, j, *pbuf;

	pbuf = malloc(x * y * sizeof *pbuf);
	if (pbuf == NULL)
		fail("out of memory\n");

	pbuf[0] = ibuf[0] - predict(0, 0, 0);

	for (i = 1; i < x; i++)
		pbuf[i] = ibuf[i] - predict(ibuf[i - 1], 0, 0);

	for (j = 1; j < y; j++) {
		pbuf[j * x] = ibuf[j * x] - predict(0, ibuf[j * x - x], 0);

		for (i = 1; i < x; i++)
			pbuf[j * x + i] = ibuf[j * x + i] -
			    predict(ibuf[j * x + i - 1], ibuf[j * x + i - x],
			    ibuf[j * x + i - x - 1]);
	}

	for (i = 0; i < x * y; i++)
		ibuf[i] = pbuf[i] & 255;

	free(pbuf);
}

static int
predict(a, b, c)
{
	int p, pa, pb, pc;

	p = a + b - c;
	pa = abs(p - a);
	pb = abs(p - b);
	pc = abs(p - c);

	if (pa <= pb && pa <= pc)
		return a;
	else if (pb <= pc)
		return b;
	else
		return c;
}