Create Subversion repository

git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1 9d0c8265-081b-0410-96cb-a4ca84ce46f8

1 files changed, 728 insertions, 0 deletions

diff --git a/urt/rle_putrow.c b/urt/rle_putrow.c
new file mode 100644
index 00000000..230720f8
--- /dev/null
+++ b/urt/rle_putrow.c
@@ -0,0 +1,728 @@
+/*
+ * This software is copyrighted as noted below.  It may be freely copied,
+ * modified, and redistributed, provided that the copyright notice is 
+ * preserved on all copies.
+ * 
+ * There is no warranty or other guarantee of fitness for this software,
+ * it is provided solely "as is".  Bug reports or fixes may be sent
+ * to the author, who may or may not act on them as he desires.
+ *
+ * You may not include this software in a program or other software product
+ * without supplying the source, or without informing the end-user that the 
+ * source is available for no extra charge.
+ *
+ * If you modify this software, you should include a notice giving the
+ * name of the person performing the modification, the date of modification,
+ * and the reason for such modification.
+ *
+ *  Modified at BRL 16-May-88 by Mike Muuss to avoid Alliant STDC desire
+ *  to have all "void" functions so declared.
+ */
+/* 
+ * rle_putrow.c - Save a row of the fb to a file.
+ * 
+ * Author:	Spencer W. Thomas
+ * 		Computer Science Dept.
+ * 		University of Utah
+ * Date:	1 April 1981
+ * Copyright (c) 1981,1986 Spencer W. Thomas
+ *
+ * $Id: rle_putrow.c,v 3.0.1.2 1992/01/28 18:29:22 spencer Exp $
+ */
+ 
+#include <stdio.h>
+#include "rle_put.h"
+#include "rle.h"
+
+
+#define FASTRUNS		/* Faster run finding */
+#ifdef vax
+#define LOCC			/* Use vax instructions for more speed */
+#endif
+
+#define	FALSE	0
+#define	TRUE	1
+
+/* Save some typing. */
+#define PBRUN the_hdr->priv.put.brun
+
+/*****************************************************************
+ * TAG( findruns )
+ * 
+ * Find runs not a given color in the row.
+ * Inputs:
+ * 	row:		Row of pixel values
+ *	rowlen:		Number of pixels in the row.
+ *	color:		Color to compare against.
+ *	nrun:		Number of runs already found (in different colors).
+ *	brun:		Runs found in other color channels already.
+ * Outputs:
+ * 	brun:		Modified to reflect merging of runs in this color.
+ *	Returns number of runs in brun.
+ * Assumptions:
+ *
+ * Algorithm:
+ * 	Search for occurences of pixels not of the given color outside
+ *	the runs already found.  When some are found, add a new run or
+ *	extend an existing one.  Adjacent runs with fewer than two
+ *	pixels intervening are merged.
+ */
+static int
+findruns(rle_pixel * const row, 
+         int         const rowlen, 
+         int         const color, 
+         int         const nrunAlready,
+         short    (* const brun)[2]) {
+
+    int i = 0, lower, upper;
+    int s, j;
+    int nrun;
+
+#ifdef DEBUG
+    fprintf( stderr, "findruns( " );
+    for ( s = 0; s < rowlen; s++ )
+        fprintf( stderr, "%2x.%s", row[s], (s % 20 == 19) ? "\n\t" : "" );
+    if ( s % 20 != 0 )
+        fprintf( stderr, "\n\t" );
+    fprintf( stderr, "%d, %d, %d, \n\t", rowlen, color, nrun );
+    for ( j = 0; j < nrun; j++ )
+        fprintf( stderr, "(%3d,%3d) %s", brun[j][0], brun[j][1],
+                 (j % 6 == 5) ? "\n\t" : "" );
+    fprintf( stderr, ")\n" );
+#endif
+
+    nrun = nrunAlready;
+
+    while ( i <= nrun )
+    {
+        /* Assert: 0 <= i <= rowlen
+         * brun[i] is the run following the "blank" space being
+         * searched.  If i == rowlen, search after brun[i-1].
+	 */
+
+	/* get lower and upper bounds of search */
+
+        if ( i == 0 )
+            lower = 0;
+        else
+            lower = brun[i-1][1] + 1;
+
+        if ( i == nrun )
+            upper = rowlen - 1;
+        else
+            upper = brun[i][0] - 1;
+
+#ifdef DEBUG
+        fprintf( stderr, "Searching before run %d from %d to %d\n",
+                 i, lower, upper );
+#endif
+        /* Search for beginning of run != color */
+#if  defined(LOCC)&defined(vax)
+        s = upper - skpc( (char *)row + lower, upper - lower + 1, color ) + 1;
+#else
+        for ( s = lower; s <= upper; s++ )
+            if ( row[s] != color )
+                break;
+#endif
+
+        if ( s <= upper )	/* found a new run? */
+        {
+            if ( s > lower + 1 || i == 0 ) /* disjoint from preceding run? */
+            {
+#ifdef DEBUG
+                fprintf( stderr, "Found new run starting at %d\n", s );
+#endif
+                /* Shift following runs up */
+                for ( j = nrun; j > i; j-- )
+                {
+                    brun[j][0] = brun[j-1][0];
+                    brun[j][1] = brun[j-1][1];
+                }
+                brun[i][0] = s;
+                nrun++;
+            }
+            else
+            {
+                i--;		/* just add to preceding run */
+#ifdef DEBUG
+                fprintf( stderr, "Adding to previous run\n" );
+#endif
+            }
+
+#if defined(LOCC)&defined(vax)
+            s = upper - locc( (char *)row + s, upper - s + 1, color ) + 1;
+#else
+            for ( ; s <= upper; s++ )
+                if ( row[s] == color )
+                    break;
+#endif
+            brun[i][1] = s - 1;
+
+#ifdef DEBUG
+            fprintf( stderr, "Ends at %d", s - 1 );
+#endif
+            if ( s >= upper && i < nrun - 1 ) /* merge with following run */
+            {
+                brun[i][1] = brun[i+1][1];
+                /* move following runs back down */
+                for ( j = i + 2; j < nrun; j++ )
+                {
+                    brun[j-1][0] = brun[j][0];
+                    brun[j-1][1] = brun[j][1];
+                }
+                nrun--;
+#ifdef DEBUG
+                fprintf( stderr, ", add to next run" );
+#endif
+            }
+#ifdef DEBUG
+            putc( '\n', stderr );
+#endif
+        }
+	
+        /* Search in next space */
+        i++;
+    }
+
+    return nrun;
+}
+
+
+
+/*****************************************************************
+ * TAG( rle_putrow )
+ * Write a scanline to the output file.
+ * 
+ * Inputs:
+ *	rows:		Pointer to vector of pointers to
+ *			rle_pixel arrays containing the pixel information.
+ *			If NULL, rowlen scanlines are skipped.
+ *	rowlen:		The number of pixels in the scanline, or the
+ *			number of scanlines to skip (see above).
+ * Outputs:
+ * 	Run length encoded information is written to the_hdr.rle_file.
+ * Assumptions:
+ * 	I'm sure there are lots of assumptions in here.
+ * Algorithm:
+ * 	There are two parts:
+ * 		1. Find all "sufficiently long" runs of background
+ * 		   color.  These will not be saved at all.
+ * 		2. For each run of non-background, for each color
+ * 		   channel, find runs of identical pixel values
+ * 		   between "data" segments (of differing pixel
+ * 		   values).
+ * 	For part 1, "sufficiently long" is 2 pixels, if the following
+ * 	data is less than 256 pixels long, otherwise it is 4 pixels.
+ * 	This is enforced by a post-process merge.
+ *
+ * 	Part 1 can be done in two different ways, depending on whether
+ * 	FASTRUNS is defined or not.  With FASTRUNS defined, it finds
+ * 	runs of the background pixel value in each channel
+ * 	independently, and then merges the results.  With FASTRUNS not
+ * 	defined, it scans all channels in parallel.
+ *
+ * 	Part 2 uses a state machine.  For each run of non-background
+ * 	data, it searches for sufficiently long sequences of a single
+ * 	value (in each channel independently).  Sufficiently long is 4
+ * 	pixels if the following data is < 256 pixels, 6 pixels
+ * 	otherwise.  This is because the startup cost for the run is 2
+ * 	bytes, and the startup cost for a data segment is 2 bytes if
+ * 	it is < 256 pixels long, 4 bytes otherwise.  Thus a run
+ * 	shorter than 4 or 6 pixels (respectively) would actually make
+ * 	the output longer.  An additional pixel is required if the
+ * 	preceding data is an odd number of pixels long (because a
+ * 	filler byte will be output at the end of it.)
+ */
+
+void
+rle_putrow(rows, rowlen, the_hdr)
+register rle_pixel *rows[];
+int rowlen;
+register rle_hdr * the_hdr;
+{
+    register int i, j;
+    int nrun;
+    register rle_pixel *row;
+    int mask;
+    char bits[256];
+    short   state,		/* State of run-finding state machine. */
+	    dstart,		/* Starting point for current data segment. */
+    	    dend,		/* Ending point of current data segment. */
+	    rstart = 0,		/* Starting point of current run. */
+	    runval = 0;		/* Data value for current run. */
+
+    if (rows == NULL)
+    {
+	the_hdr->priv.put.nblank += rowlen;
+	return;
+    }
+    /* 
+     * If not done already, allocate space to remember runs of
+     * non-background color.  A run of bg color must be at least 2
+     * bytes long to count, so there can be at most rowlen/3 of them.
+     */
+    if ( PBRUN == NULL )
+    {
+	PBRUN = (short (*)[2])malloc(
+	    (unsigned)((rowlen/3 + 1) * 2 * sizeof(short)) );
+	if ( PBRUN == NULL )
+	{
+	    fprintf( stderr, "%s: Malloc failed in rle_putrow, writing %s\n",
+		     the_hdr->cmd, the_hdr->file_name );
+	    exit(1);
+	}
+    }
+    /* Unpack bitmask in the_hdr struct */
+    for ( i=0; i < the_hdr->ncolors; i++ )
+	bits[i] = RLE_BIT( *the_hdr, i );
+    bits[255] = RLE_BIT( *the_hdr, -1 );
+
+    /* 
+     * If saving only non-background pixels, find runs of them.  Note
+     * that the alpha channel is considered to be background iff it is
+     * zero.
+     */
+#ifdef	FASTRUNS
+    if ( the_hdr->background )
+    {
+	/* 
+	 * Find runs in each color individually, merging them as we go.
+	 */
+	nrun = 0;		/* start out with no runs */
+	/* Alpha channel first */
+	if ( the_hdr->alpha )
+	    nrun = findruns( rows[-1], rowlen, 0, nrun, PBRUN );
+	/* Now the color channels */
+	for ( i = 0; i < the_hdr->ncolors; i++ )
+	    if ( bits[i] )
+		nrun = findruns( rows[i], rowlen, the_hdr->bg_color[i],
+				 nrun, PBRUN );
+    }
+    else
+    {
+	PBRUN[0][0] = 0;
+	PBRUN[0][1] = rowlen-1;
+	nrun = 1;
+    }
+#else				/* FASTRUNS */
+    if (the_hdr->background)	/* find non-background runs */
+    {
+	j = 0;
+	for (i=0; i<rowlen; i++)
+	    if (!same_color( i, rows, the_hdr->bg_color,
+			     the_hdr->ncolors, bits ) ||
+		(the_hdr->alpha && rows[-1][i] != 0))
+	    {
+		if (j > 0 && i - PBRUN[j-1][1] <= 2)
+		    j--;
+		else
+		    PBRUN[j][0] = i; /* start of run */
+		for ( i++;
+		      i < rowlen && 
+			( !same_color( i, rows, the_hdr->bg_color,
+					 the_hdr->ncolors, bits ) ||
+			  (the_hdr->alpha && rows[-1][i] != 0) );
+		      i++)
+		    ;			/* find the end of this run */
+		PBRUN[j][1] = i-1;    /* last in run */
+		j++;
+	    }
+	nrun = j;
+    }
+    else
+    {
+	PBRUN[0][0] = 0;
+	PBRUN[0][1] = rowlen-1;
+	nrun = 1;
+    }
+#endif				/* FASTRUNS */
+    /* One final pass merges runs with fewer than 4 intervening pixels
+     * if the second run is longer than 255 pixels.  This is because
+     * the startup cost for such a run is 4 bytes.
+     */
+    if ( nrun > 1 )
+    {
+	for ( i = nrun - 1; i > 0; i-- )
+	{
+	    if ( PBRUN[i][1] - PBRUN[i][0] > 255 &&
+		 PBRUN[i-1][1] + 4 > PBRUN[i][0] )
+	    {
+		PBRUN[i-1][1] = PBRUN[i][1];
+		for ( j = i; j < nrun - 1; j++ )
+		{
+		    PBRUN[j][0] = PBRUN[j+1][0];
+		    PBRUN[j][1] = PBRUN[j+1][1];
+		}
+		nrun--;
+	    }
+	}
+    }
+
+    if (nrun > 0)
+    {
+	if (the_hdr->priv.put.nblank > 0)
+	{
+	    SkipBlankLines(the_hdr->priv.put.nblank);
+	    the_hdr->priv.put.nblank = 0;
+	}
+	for ( mask = (the_hdr->alpha ? -1 : 0);
+	      mask < the_hdr->ncolors;
+	      mask++)			/* do all colors */
+	{
+	    if ( ! bits[mask & 0xff] )
+	    {
+		continue;
+	    }
+	    row = rows[mask];
+	    SetColor(mask);
+	    if (PBRUN[0][0] > 0)
+	    {
+		SkipPixels(PBRUN[0][0], FALSE, FALSE);
+	    }
+	    for (j=0; j<nrun; j++)
+	    {
+		state = DATA;
+		dstart = PBRUN[j][0];
+		dend = PBRUN[j][1];
+		for (i=dstart; i<=dend; i++)
+		{
+		    switch(state)
+		    {
+		    case DATA:
+			if (i > dstart && runval == row[i])
+			{
+			    /* 2 in a row may be a run. */
+			    /* If odd data length, start with RUN1 */
+			    if ( ((i - dstart) % 2) == 0)
+				state = RUN1;
+			    else
+				state = RUN2;
+			}
+			else
+			{
+			    runval = row[i];	/* maybe a run starts here? */
+			    rstart = i;
+			}
+			break;
+	    
+		    case RUN4:
+			if (runval == row[i])
+			{
+			    /* If the following data might be longer
+			     * than 255 pixels then look for 8 in a
+			     * row, otherwise, 6 in a row is
+			     * sufficient.  Fake this by skipping to
+			     * state RUN5.
+			     */
+			    if ( dend - i > 255 )
+				state  = RUN5;	/* Need some more. */
+			    else
+				state = RUN7;	/* Next one makes a run. */
+			    
+			}
+			else
+			{
+			    state = DATA;	/* Nope, back to data */
+			    runval = row[i];	/* but maybe a new run here? */
+			    rstart = i;
+			}
+			break;
+
+		    case RUN1:
+		    case RUN2:
+		    case RUN3:
+		    case RUN5:
+		    case RUN6:
+			if (runval == row[i])
+			{
+			    /* Move to the next state. */
+			    state++;
+			}
+			else
+			{
+			    state = DATA;	/* Nope, back to data */
+			    runval = row[i];	/* but maybe a new run here? */
+			    rstart = i;
+			}
+			break;
+
+
+		    case RUN7:
+			if (runval == row[i])	/* enough in a row for a run */
+			{
+			    state = INRUN;
+			    putdata(row + dstart, rstart - dstart);
+#ifdef FASTRUNS
+#ifdef LOCC
+			    /* Shortcut to find end of run! */
+			    i = dend - skpc( (char *)row + i, dend + 1 - i,
+					     runval );
+#else
+			    while ( row[++i] == runval && i <= dend)
+				; /* not quite so good, but not bad */
+			    i--;
+#endif /* LOCC */
+#endif /* FASTRUNS */
+			}
+			else
+			{
+			    state = DATA;		/* not a run, */
+			    runval = row[i];	/* but may this starts one */
+			    rstart = i;
+			}
+			break;
+	    
+		    case INRUN:
+			if (runval != row[i])	/* if run out */
+			{
+			    state = DATA;
+			    putrun(runval, i - rstart, FALSE);
+			    runval = row[i];	/* who knows, might be more */
+			    rstart = i;
+			    dstart = i;	/* starting a new 'data' run */
+			}
+			break;
+		    }
+		}
+		if (state == INRUN)
+		    putrun(runval, i - rstart, TRUE);	/* last bit */
+		else
+		    putdata(row + dstart, i - dstart);
+
+		if (j < nrun-1)
+		    SkipPixels(
+			    PBRUN[j+1][0] - dend - 1,
+			    FALSE, state == INRUN);
+		else
+		{
+		    if (rowlen - dend > 0)
+			SkipPixels(
+			    rowlen - dend - 1,
+			    TRUE, state == INRUN);
+		}
+	    }
+
+	    if ( mask != the_hdr->ncolors - 1 )
+		NewScanLine(FALSE);
+	}
+    }
+
+    /* Increment to next scanline */
+    the_hdr->priv.put.nblank++;
+
+    /* flush every scanline */
+    fflush( the_hdr->rle_file );
+}
+
+
+/*****************************************************************
+ * TAG( rle_skiprow )
+ * 
+ * Skip rows in RLE file.
+ * Inputs:
+ * 	the_hdr:    	Header struct for RLE output file.
+ *  	nrow:	    	Number of rows to skip.
+ * Outputs:
+ * 	Increments the nblank field in the the_hdr struct, so that a Skiplines
+ *  	code will be output the next time rle_putrow or rle_putraw is called.
+ * Assumptions:
+ * 	Only effective when called between rle_putrow or rle_putraw calls (or
+ *  	some other routine that follows the same conventions.
+ * Algorithm:
+ *	[None]
+ */
+void
+rle_skiprow( the_hdr, nrow )
+rle_hdr *the_hdr;
+int nrow;
+{
+    the_hdr->priv.put.nblank += nrow;
+}
+
+
+/*****************************************************************
+ * TAG( rle_put_init )
+ * 
+ * Initialize the header structure for writing scanlines. 
+ * Inputs:
+ *	[None]
+ * Outputs:
+ * 	the_hdr:	Private portions initialized for output.
+ * Assumptions:
+ *	[None]
+ * Algorithm:
+ *	[None]
+ */
+void
+rle_put_init( the_hdr )
+register rle_hdr *the_hdr;
+{
+    the_hdr->dispatch = RUN_DISPATCH;
+
+    if ( the_hdr->is_init != RLE_INIT_MAGIC )
+    {
+	the_hdr->cmd = "Urt";
+	the_hdr->file_name = "some file";
+    }
+    the_hdr->priv.put.nblank = 0;	/* Reinit static vars */
+    /* Would like to be able to free previously allocated storage,
+     * but can't count on a non-NULL value being a valid pointer.
+     */
+    PBRUN = NULL;
+    the_hdr->priv.put.fileptr = 0;
+
+    /* Only save alpha if alpha AND alpha channel bit are set. */
+    if ( the_hdr->alpha )
+	the_hdr->alpha = (RLE_BIT( *the_hdr, -1 ) != 0);
+    else
+	RLE_CLR_BIT( *the_hdr, -1 );
+}
+
+/*****************************************************************
+ * TAG( rle_put_setup )
+ * 
+ * Initialize for writing RLE, and write header to output file.
+ * Inputs:
+ * 	the_hdr:	Describes output image.
+ * Outputs:
+ * 	the_hdr:	Initialized.
+ * Assumptions:
+ *	Lots of them.
+ * Algorithm:
+ *	[None]
+ */
+void
+rle_put_setup( the_hdr )
+register rle_hdr * the_hdr;
+{
+    rle_put_init( the_hdr );
+    the_hdr->img_num++;		/* Count output images. */
+    Setup();
+}
+
+void
+DefaultBlockHook(rle_hdr * the_hdr)
+{
+    					/* Do nothing */
+}
+
+/*****************************************************************
+ * TAG( rle_puteof )
+ * Write an EOF code into the output file.
+ */
+void
+rle_puteof( the_hdr )
+register rle_hdr * the_hdr;
+{
+    /* Don't puteof twice. */
+    if ( the_hdr->dispatch == NO_DISPATCH )
+	return;
+    PutEof();
+    fflush( the_hdr->rle_file );
+    /* Free storage allocated by rle_put_init. */
+    if ( PBRUN != NULL )
+    {
+	free( PBRUN );
+	PBRUN = NULL;
+    }
+    /* Signal that puteof has been called. */
+    the_hdr->dispatch = NO_DISPATCH;
+}
+
+#ifndef FASTRUNS
+/*****************************************************************
+ * TAG( same_color )
+ * 
+ * Determine if the color at the given index position in the scan rows
+ * is the same as the background color.
+ * Inputs:
+ * 	index:	    Index to the pixel position in each row.
+ *	rows:	    array of pointers to the scanlines
+ *	bg_color:   the background color
+ *	ncolors:    number of color elements/pixel
+ * Outputs:
+ * 	TRUE if the color at row[*][i] is the same as bg_color[*].
+ * Assumptions:
+ *	[None]
+ * Algorithm:
+ *	[None]
+ */
+static int
+same_color( index, rows, bg_color, ncolors, bits )
+register rle_pixel *rows[];
+register int bg_color[];
+char *bits;
+{
+    register int i;
+
+    for ( i = 0; i < ncolors; i++, bits++ )
+	if ( *bits &&
+	     rows[i][index] != bg_color[i] )
+	    return 0;
+    return 1;				/* all the same */
+}
+#endif /* !FASTRUNS */
+
+/*****************************************************************
+ * TAG( rgb_to_bw )
+ * 
+ * Perform the NTSC Y transform on RGB data to get B&W data.
+ * Inputs:
+ * 	red_row, green_row, blue_row:	Given RGB pixel data.
+ *	rowlen:	    Number of pixels in the rows.
+ * Outputs:
+ * 	bw_row:	    Output B&W data.  May coincide with one of the
+ *		    inputs.
+ * Assumptions:
+ *	[None]
+ * Algorithm:
+ * 	BW = .30*R + .59*G + .11*B
+ */
+void
+rgb_to_bw( red_row, green_row, blue_row, bw_row, rowlen )
+rle_pixel *red_row;
+rle_pixel *green_row;
+rle_pixel *blue_row;
+rle_pixel *bw_row;
+int rowlen;
+{
+    register int x, bw;
+
+    for (x=0; x<rowlen; x++)
+    {
+	/* 68000 won't store float > 127 into byte? */
+	/* HP compiler blows it */
+	bw = 0.5 + .30*red_row[x] + .59*green_row[x] + .11*blue_row[x];
+	bw_row[x] = bw;
+    }
+}
+
+#ifdef LOCC
+/*ARGSUSED*/
+locc( p, l, c )
+register char *p;
+register int l;
+register int c;
+{
+    asm( "locc	r9,r10,(r11)" );
+#ifdef lint
+    c = (int) p;		/* why doesn't ARGSUSED work? */
+    l = c;
+    return l;			/* Needs return value, at least */
+#endif
+}
+
+/*ARGSUSED*/
+skpc( p, l, c )
+register char *p;
+register int l;
+register int c;
+{
+    asm( "skpc r9,r10,(r11)" );
+#ifdef lint
+    c = (int) p;		/* why doesn't ARGSUSED work? */
+    l = c;
+    return l;			/* Needs return value, at least */
+#endif
+}
+#endif