From 1fd361a1ea06e44286c213ca1f814f49306fdc43 Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sat, 19 Aug 2006 03:12:28 +0000 Subject: Create Subversion repository git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- urt/rle_putrow.c | 728 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 728 insertions(+) create mode 100644 urt/rle_putrow.c (limited to 'urt/rle_putrow.c') 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 +#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; ibg_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 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 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 -- cgit 1.4.1