#    C Code to convert between raster scanned rectangular images and
#    images scanned along a space-filling curve (Hilbert's variant on
#    a Peano curve, windowed to the image size).
#
# To install this software:
#  1) create a directory (e.g. with the shell command mkdir spacefill)
#  2) change to that directory (e.g. with the command cd spacefill),
#  3) direct the remainder of this mail through sh (e.g. sh < ../savedmail).
# This will cause sh to create files in the new directory; it will do nothing
# else.  Then read README in the new directory for additional instructions.
#
# Note:  The source code included here is covered by copyright.  This
# copyright extends specific permission for redistribution, modification
# and resale of this code.
# 
cat > README <<\xxxxxxxxxx
  File: README
  Author: Douglas Jones
  Date: May. 20, 1991
  Purpose: Description of the space-filling-curve software distribution.

This software distribution includes the following files:

	README     (you are reading this)
	fill.c     Code to convert from a raster-scanned image to the same
			image scanned along a space-filling curve.
	unfill.c   Code to convert from an image scanned along a space-filling
			curve to a raster-scanned image.
	filltest.c Code to test the space-filling curve algorithm (prints
                        a space filling curve on standard out).
        filler.h   The include file common to all of the above.

The fill and unfill utilities are filters, taking standard input to standard
output.  They should be portable but have only been tested under IBM's AOS
operating system on an IBM RT.

The fill, unfill and filltest utilities all take, as parameters, the width
and height of the image to be scanned.  Experiment with filltest to see how
these are interpreted.

Both routines process image files stored one pixel per byte, where the
file contains exactly <width> x <height> pixels.  All header, colormap or
other information must be removed prior to applying these filters.
xxxxxxxxxx
cat > fill.c <<\xxxxxxxxxx
/* File: fill.c
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: May. 15, 1991.
   Language: C (UNIX)
   Copyright 1991 by Douglas Jones.  The author hereby gives permission for
                     unlimited redistribution, reuse or modification of this
                     code, whether for profit or not, so long as the author
                     is credited for this work, and so long as a) whoever
                     redistributes this code extends the same permissions to
                     the ultimate recipient, or b) whoever modifies this code
                     makes this unmodified code available to the ultimate
                     recipient.
   Patent status:  The author is unaware of any patents covering the use of
                   this algorithm in any context.
   Purpose: convert an x by y raster image to a linear sequence using a
            space filling curve.
   Algorithm: Read image into array, then scan it using a space filling
              curve generator.
*/

#include<stdio.h>

char* progname;	   /* the name of this program (argv[0]) */
char* image;       /* place to store image for conversion */
int width, height; /* the image size */

/* fatal error processing */
error( msg )
char *msg; /* the error message */
{
	fprintf( stderr, "Usage: %s <width> <height> -- %s\n", progname, msg );
        exit( -1 );
}

/* setup routine */
setup()
{
	int row, column;
	int ch;

	for (row = 0; row < height; row++ ){
		for (column = 0; column < width; column++ ){
			if (((ch = getchar()) == EOF) && feof(stdin)) {
				error( "Premature EOF on standard input" );
			}
			image[row*width + column] = ch;
		}
	}

	if ((ch = getchar()) != EOF) {
		error( "too much data on standard input" );
	}
}

/* thing to do at every point */
doit( x, y )
int x, y;
{
        if ((x < width) && (y < height)) {
		putchar(image[y*width + x]);
	}
}

#include "filler.h"

/* THE MAIN PROGRAM */
main(argc, argv)
int argc;
char *argv[];
{
	int size;

        progname = argv[0];

	/* get width and height of image */
	if (argc != 3) { /* width and height not given */
		error( "Wrong number of command line arguments" );
        }
	
	if (sscanf( &argv[1][0], "%d\0", &width ) != 1) {
		error( "Width must be integer" );
	}

	if (sscanf( &argv[2][0], "%d\0", &height ) != 1) {
		error( "Height must be integer" );
	}

        if (width <= 0) {
		error( "Width must be positive" );
	}

        if (height <= 0) {
		error( "Height must be positive" );
	}

	/* allocate an array to hold the image */
	image = (char *)malloc( width*height );

	/* find size such that size >= max(width, height) */
	for (size = 1; (size < width) || (size < height); size *= 2) {}

	/* read in the image along raster lines */
	setup();

	/* spit it out along a space-filling curve */
	fill( size, 0,0, 0,1, 1,0 );

	exit(0);
}
xxxxxxxxxx
cat > unfill.c <<\xxxxxxxxxx
/* File: unfill.c
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: May. 20, 1991.
   Language: C (UNIX)
   Copyright 1991 by Douglas Jones.  The author hereby gives permission for
                     unlimited redistribution, reuse or modification of this
                     code, whether for profit or not, so long as the author
                     is credited for this work, and so long as a) whoever
                     redistributes this code extends the same permissions to
                     the ultimate recipient, or b) whoever modifies this code
                     makes this unmodified code available to the ultimate
                     recipient.
   Patent status:  The author is unaware of any patents covering the use of
                   this algorithm in any context.
   Purpose: convert a linear sequence following a space filling curve to
            an x by y raster image.
   Algorithm: Read image into array along space filling curve, then scan
              it using a simple raster.
*/

#include<stdio.h>

char* progname;	   /* the name of this program (argv[0]) */
char* image;       /* place to store image for conversion */
int width, height; /* the image size */

/* fatal error processing */
error( msg )
char *msg; /* the error message */
{
	fprintf( stderr, "Usage: %s <width> <height> -- %s\n", progname, msg );
        exit( -1 );
}

/* takedown routine */
takedown()
{
	int row, column;
	int ch;

	if ((ch = getchar()) != EOF) {
		error( "too much data on standard input" );
	}

	for (row = 0; row < height; row++ ){
		for (column = 0; column < width; column++ ){
			putchar(image[row*width + column]);
		}
	}
}

/* thing to do at every point */
doit( x, y )
int x, y;
{
	int ch;
        if ((x < width) && (y < height)) {
		if (((ch = getchar()) == EOF) && feof(stdin)) {
			error( "Premature EOF on standard input" );
		}
		image[y*width + x] = ch;
	}
}

#include "filler.h"

/* THE MAIN PROGRAM */
main(argc, argv)
int argc;
char *argv[];
{
	int size;

        progname = argv[0];

	/* get width and height of image */
	if (argc != 3) { /* width and height not given */
		error( "Wrong number of command line arguments" );
        }
	
	if (sscanf( &argv[1][0], "%d\0", &width ) != 1) {
		error( "Width must be integer" );
	}

	if (sscanf( &argv[2][0], "%d\0", &height ) != 1) {
		error( "Height must be integer" );
	}

        if (width <= 0) {
		error( "Width must be positive" );
	}

        if (height <= 0) {
		error( "Height must be positive" );
	}

	/* allocate an array to hold the image */
	image = (char *)malloc( width*height );

	/* find size such that size >= max(width, height) */
	for (size = 1; (size < width) || (size < height); size *= 2) {}

	/* read in the image along a space-filling curve */
	fill( size, 0,0, 0,1, 1,0 );

	/* spit it out along raster lines */
	takedown();

	exit(0);
}
xxxxxxxxxx
cat > filltest.c <<\xxxxxxxxxx
/* File: filltest.c
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: May. 15, 1991.
   Language: C (UNIX)
   Copyright 1991 by Douglas Jones.  The author hereby gives permission for
                     unlimited redistribution, reuse or modification of this
                     code, whether for profit or not, so long as the author
                     is credited for this work, and so long as a) whoever
                     redistributes this code extends the same permissions to
                     the ultimate recipient, or b) whoever modifies this code
                     makes this unmodified code available to the ultimate
                     recipient.
   Patent status:  The author is unaware of any patents covering the use of
                   this algorithm in any context.
   Purpose: Space filling curve generator test
   Algorithm: Make printable output from filler.h in the following form:

     .  ._.  . ._._.
        ._!  !_! ._!
             ._. !_.
             ! !_._!
*/

#include<stdio.h>

char* progname;	    /* the name of this program (argv[0]) */
char plot[127][64]; /* array to hold printable result */
int xprev, yprev;   /* previous point plotted */
int width, height;  /* the image size */

/* setup routine */
setup()
{
	int row, column;
	for (row = 0; row < height; row++ ){
		for (column = 0; column < (width*2-1); column++ ){
			plot[column][row] = ' ';
		}
	}
	xprev = -2;
	yprev = -2;
}

/* takedown routine */
takedown()
{
	int row, column;
	for (row = 0; row < height; row++ ){
		for (column = 0; column < (width*2-1); column++ ){
			putchar(plot[column][row]);
		}
		putchar('\n');
	}
}

/* thing to do at every point */
doit( x, y )
int x, y;
{
        if ((x < width) && (y < height)) {
		plot[x*2][y] = '.';
		if (x == (xprev + 1)) {
			plot[xprev*2 + 1][y] = '_';
		} else if (x == (xprev - 1)) {
			plot[x*2 + 1][y] = '_';
		} else if (y == (yprev + 1)) {
			plot[x*2][y] = '!';
		} else if (y == (yprev - 1)) {
			plot[x*2][yprev] = '!';
		}
		xprev = x;
		yprev = y;
	}
}

#include "filler.h"

/* fatal error processing */
error( msg )
char *msg; /* the error message */
{
	fprintf( stderr, "Usage: %s <width> <height> -- %s\n", progname, msg );
        exit( -1 );
}

/* THE MAIN PROGRAM */
main(argc, argv)
int argc;
char *argv[];
{

	int size;

        progname = argv[0];

	/* get width and height of image */
	if (argc != 3) { /* width and height not given */
		error( "Wrong number of command line arguments" );
        }
	
	if (sscanf( &argv[1][0], "%d\0", &width ) != 1) {
		error( "Width must be integer" );
	}

	if (sscanf( &argv[2][0], "%d\0", &height ) != 1) {
		error( "Height must be integer" );
	}

        if ((width <= 0) || (width > 40)) {
		error( "Width must be between 1 and 40" );
	}

        if ((height <= 0) || (height > 36)) {
		error( "Height must be between 1 and 36" );
	}

	/* find size such that size >= max(width, height) */
	for (size = 1; (size < width) || (size < height); size *= 2) {}

	/* prepare to generate curve */
	setup();

	/* spit it out along a space-filling curve */
	fill( size, 0,0, 0,1, 1,0 );

        /* output the generated curve */
        takedown();
	exit(0);
}
xxxxxxxxxx
cat > filler.h <<\xxxxxxxxxx
/* File: filler.h
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: May. 15, 1991.
   Language: C (UNIX)
   Copyright 1991 by Douglas Jones.  The author hereby gives permission for
                     unlimited redistribution, reuse or modification of this
                     code, whether for profit or not, so long as the author
                     is credited for this work, and so long as a) whoever
                     redistributes this code extends the same permissions to
                     the ultimate recipient, or b) whoever modifies this code
                     makes this unmodified code available to the ultimate
                     recipient.
   Patent status:  The author is unaware of any patents covering the use of
                   this algorithm in any context.
   Purpose: Space filling curve generator.
   Algorithm: Recursively fill a region with a rectilinear curve;
              at each point, call doit(x,y) with the coordinates of the point.
*/

fill( size,  xorig,yorig,  xdir,ydir,  xperp,yperp )

int size;         /* size of region - must be a power of 2 */
int xorig, yorig; /* origin of region */
int xdir, ydir;   /* unit vector from origin to ending path through region */
int xperp, yperp; /* unit vector perpendicular to (xdir,ydir) */

/* To generate:  (a,b). ._._.(a+3,b)     |      ---->
                      !_! ._!            | dir   perp
                      ._. !_.            v
                      ! !_._!
               (a,b+3)       (a+3,b+3)

   Use: fill( 4, a,b, 0,1, 1,0 )

   This will call doit(x,y) at successive values of (x,y) along the path:
   (a,b) (a,b+1) (a+1,b+1) (a+1,b) (a+2,b) (a+3,b) ... (a,b+3)
*/

{
	if (size < 2) { /* trivial case */

		doit( xorig, yorig );

	} else { /* interesting case */

		int sdiv2;  /* size of component figures */

		sdiv2 = size / 2;

		/* first quadrant */
		fill( sdiv2, xorig,yorig, xperp,yperp, xdir,ydir );

		/* second quadrant */
		fill( sdiv2, xorig + xperp*sdiv2,
			     yorig + yperp*sdiv2,
					  xdir,ydir, xperp,yperp );

		/* third quadrant */
		fill( sdiv2, xorig + xperp*sdiv2 + xdir*sdiv2,
			     yorig + yperp*sdiv2 + ydir*sdiv2,
					  xdir,ydir, xperp,yperp );

		/* fourth quadrant */
		fill( sdiv2, xorig + xperp*(sdiv2-1) + xdir*(size-1),
			     yorig + yperp*(sdiv2-1) + ydir*(size-1),
					  -xperp,-yperp, -xdir,-ydir );

	}
}
xxxxxxxxxx