/* 
 * rlesortmap.c - Sort the colormap using a n-d peano curve.
 * 
 * Author:	Spencer W. Thomas
 * 		EECS Dept.
 * 		University of Michigan
 * Date:	Fri Feb 15 1991
 * Copyright (c) 1991, University of Michigan
 */

#include <stdio.h>
#include "rle.h"
#include "rle_raw.h"

#define	map_pixel( pix, cmaplen, cmap )	((pix) > cmaplen ? (pix) : \
					 cmap[pix])

/* This is global so that the pcompar function can see it. */
static rle_map ** cmap = NULL;
static int ncolor;

/* pcompar compares two colormap entries using the Peano ordering. */
extern pcompar();

/*****************************************************************
 * TAG( main )
 * 
 * Usage:
 * 	rlesortmap [-o outfile] [infile]
 * Inputs:
 * 	infile:		Input file to have its colormap sorted.
 * 			Defaults to stdin.
 * Outputs:
 * 	outfile:	Result of sorting the colormap.
 * 			Defaults to stdout.
 * Assumptions:
 *	[None]
 * Algorithm:
 * 	Uses a Peano curve ordering to sort the elements in the input
 * 	colormap.  Keeps track of where each original element went,
 * 	and then remaps the input data accordingly.  This makes most
 * 	sense for pseudo-color input files, but the program will work
 * 	on any input file.
 */
void
main( argc, argv )
int argc;
char **argv;
{
    register int i, c, j;
    char * infname = NULL, * outfname = NULL;
    FILE *outfile = stdout;
    int oflag = 0, y, nskip, nrow;
    int	rle_cnt, rle_err;
    rle_hdr 	in_hdr, out_hdr;
    rle_op ** scan, ** outscan;
    int * nraw;
    int cmaplen;
    rle_map *mapp, **scmap;
    int *sortindex, *isort;

    in_hdr = *rle_hdr_init( NULL );
    out_hdr = *rle_hdr_init( NULL );

    if ( scanargs( argc, argv, "% o%-outfile!s infile%s",
		   &oflag, &outfname, &infname ) == 0 )
	exit( 1 );
    /* Open input file and read RLE header */
    in_hdr.rle_file = rle_open_f(cmd_name( argv ), infname, "r");
    rle_names( &in_hdr, cmd_name( argv ), infname, 0 );
    rle_names( &out_hdr, in_hdr.cmd, outfname, 0 );

    for ( rle_cnt = 0;
	  (rle_err = rle_get_setup( &in_hdr )) == RLE_SUCCESS;
	  rle_cnt++ )
    {
	/* Copy header data from the input file */
	(void)rle_hdr_cp( &in_hdr, &out_hdr );
	rle_addhist( argv, &in_hdr, &out_hdr );

	/* Open the output file */
	if ( rle_cnt == 0 )
	    outfile = rle_open_f( cmd_name( argv ), outfname, "w" );
	out_hdr.rle_file = outfile;

	nrow = in_hdr.xmax - in_hdr.xmin + 1;	/* how wide is it? */

	if ( in_hdr.ncmap > 0 )
	{
	    char *map_cmt;

	    cmaplen = 1 << in_hdr.cmaplen;	/* length of the color map */
	    /* Get pointers to the individual rows of the color map */
	    cmap = (rle_map **) malloc( in_hdr.ncmap * sizeof(rle_map *) );
	    RLE_CHECK_ALLOC( in_hdr.cmd, cmap, "color map" );
	    for ( c = 0; c < in_hdr.ncmap; c++ )
		cmap[c] = &in_hdr.cmap[c * cmaplen];

	    /* Pointers for storing sorted colormap. */
	    scmap = (rle_map **) malloc( in_hdr.ncmap * sizeof(rle_map *) );
	    mapp = (rle_map *)malloc( in_hdr.ncmap * cmaplen * sizeof(rle_map) );
	    RLE_CHECK_ALLOC( in_hdr.cmd, scmap && mapp, "color map" );
	    for ( c = 0; c < in_hdr.ncmap; c++ )
		scmap[c] = &mapp[c * cmaplen];

	    /* If usable colormap length given, use it. */
	    if ( (map_cmt = rle_getcom( "color_map_length", &in_hdr )) &&
		 atoi( map_cmt ) > 0 )
		cmaplen = atoi( map_cmt );
	}
	else
	    cmaplen = 0;

	if ( cmaplen > 0 )
	{
	    /* Allocate space for the sort indices. */
	    sortindex = (int *)malloc( sizeof(int) * cmaplen );
	    RLE_CHECK_ALLOC( in_hdr.cmd, sortindex, 0 );

	    /* And initialize them to the identity mapping. */
	    for ( i = 0; i < cmaplen; i++ )
		sortindex[i] = i;

	    ncolor = in_hdr.ncmap;
	    /* Do the sort. */
	    qsort( sortindex, cmaplen, sizeof(int), pcompar );

	    /* Compute the inverse sort map. */
	    isort = (int *)malloc( sizeof(int) * cmaplen );
	    RLE_CHECK_ALLOC( in_hdr.cmd, isort, 0 );
	    for ( i = 0; i < cmaplen; i++ )
		isort[sortindex[i]] = i;

#if 0
	    /* Collapse identical entries. */
	    for ( i = 1, j = 0; i < cmaplen; i++ )
	    {
		int xi, xi1;
		xi = sortindex[i];
		xi1 = sortindex[i-1];

		for ( c = 0; c < ncolor; c++ )
		    if ( cmap[c][xi] != cmap[c][xi1] )
			break;
		/* If loop broke, colors are different. */
		if ( c != ncolor )
		    j++;
		if ( i != j )
		    sortindex[j] = sortindex[i];
	    }
	    cmaplen = j + 1;
#endif

	    /* Rearrange the physical colormap. */
	    for ( i = 0; i < cmaplen; i++ )
	    {
		int xi = sortindex[i];

		for ( c = 0; c < ncolor; c++ )
		    scmap[c][i] = cmap[c][xi];
	    }

	    /* And put the sorted colormap into the output file. */
	    out_hdr.cmap = mapp;
	    if ( cmaplen < (1 << out_hdr.cmaplen ) )
	    {
		char buf[80];

		sprintf( buf, "color_map_length=%d", cmaplen );
		rle_putcom( buf, &out_hdr );
	    }
	}
	
	/* Allocate space for the rle opcode information */
	if ( rle_raw_alloc( &in_hdr, &scan, &nraw ) < 0 )
	    RLE_CHECK_ALLOC( in_hdr.cmd, 0, "image data" );

	if ( in_hdr.ncmap > 0 && in_hdr.background )
	    for ( i = 0; i < out_hdr.ncolors; i++ )
		in_hdr.bg_color[i] = map_pixel( in_hdr.bg_color[i],
						cmaplen, isort );

	/* Start the output file */
	rle_put_setup( &out_hdr );

	y = in_hdr.ymin - 1;
	while ( (nskip = rle_getraw( &in_hdr, scan, nraw )) != 32768 )
	{
	    nskip -= y;		/* figure out difference from previous line */
	    y += nskip;
	    if ( nskip > 1 )
		rle_skiprow( &out_hdr, nskip - 1 );
	    if ( cmaplen > 0 )
	    {
		for ( c = 0; c < in_hdr.ncolors; c++ )
		    if ( c < in_hdr.ncmap )
			for ( i = 0; i < nraw[c]; i++ )
			    switch( scan[c][i].opcode )
			    {
			    case RRunDataOp:
				scan[c][i].u.run_val =
				    map_pixel( scan[c][i].u.run_val,
					       cmaplen, isort );
				break;
			    case RByteDataOp:
				for ( j = 0; j < scan[c][i].length;
				      j++ )
				    scan[c][i].u.pixels[j] = 
					map_pixel( scan[c][i].u.pixels[j],
						   cmaplen, isort);
				break;
			    }
	    }
	    rle_putraw( scan, nraw, &out_hdr );
	    rle_freeraw( &in_hdr, scan, nraw );
	}
	rle_puteof( &out_hdr );

	if ( in_hdr.ncmap > 0 )
	{
	    free( cmap );
	    free( scmap );
	    free( mapp );
	}

	rle_raw_free( &in_hdr, scan, nraw );
    }

    /* Check for an error.  EOF or EMPTY is ok if at least one image
     * has been read.  Otherwise, print an error message.
     */
    if ( rle_cnt == 0 || (rle_err != RLE_EOF && rle_err != RLE_EMPTY) )
	rle_get_error( rle_err, cmd_name( argv ), infname );

    exit( 0 );
}

/*****************************************************************
 * TAG( pcompar )
 * 
 * Compares the indicated colormap entries using the Peano ordering.
 * Inputs:
 * 	a, b:	Indices into the sortindex array (which indexes the
 * 		colormap itself.)
 * Outputs:
 * 	Returns -1 if cmap[sortindex[a]] < cmap[sortindex[b]],
 * 		0 if they are equal, and
 * 		1 if a ">" b.
 * Assumptions:
 *	(global) ncolors <= 4.
 * Algorithm:
 *	Uses the Peano curve ordering for n=ncolors and m=8 to get a
 *	linear ordering for the n-dimensional colors.
 */
int
pcompar( ap, bp )
int *ap, *bp;
{
    int a = *ap, b = *bp;
    unsigned long int ai, bi;
    int c[4];

    switch( ncolor )
    {
    case 4:	c[3] = cmap[3][a] >> 8;
    case 3:	c[2] = cmap[2][a] >> 8;
    case 2:	c[1] = cmap[1][a] >> 8;
    case 1:	c[0] = cmap[0][a] >> 8;
    }
    hilbert_c2i( ncolor, 8, c, &ai );

    switch( ncolor )
    {
    case 4:	c[3] = cmap[3][b] >> 8;
    case 3:	c[2] = cmap[2][b] >> 8;
    case 2:	c[1] = cmap[1][b] >> 8;
    case 1:	c[0] = cmap[0][b] >> 8;
    }
    hilbert_c2i( ncolor, 8, c, &bi );

    if ( ai < bi )
	return -1;
    else if ( ai == bi )
	return 0;
    else
	return 1;
}