Victor Duvanenko is an IC design engineer. He has worked on several graphics chips at Intel. Presently he is a consultant at Silicon Engineering Inc. in Santa Cruz. He can be reached at 1040 S. Winchester Blvd., #11, San Jose, CA 95128.
Image compilation is a unique method of image compression whereby an image is transformed into a graphics coprocessor instruction stream. Even a simple implementation of the image compilation technique has lead to a 2.5:1 compression ratio with a corresponding reduction in the image reconstruction time.
At present, resolutions for graphics displays vary from 320 x 200 on the very low-end to 2K x 2K on the highend, with 640 x 480 being fairly common. A 640 x 480 display consists of 307,200 pixels. If the depth is 8 bits per pixel (a byte for each dot on the screen), then it takes 307,200 bytes to define a full screen image. This is a considerable amount of data to move or manipulate interactively. Considering that resolution of raster displays is increasing every year, the job of graphic data manipulation will not get any easier.
To put into perspective what it means to manipulate large amounts of data, consider that to transmit 307,200 bytes of data would take 43 minutes over a 1200-baud modem and about five minutes over a 9600-baud modem.
At 9600 baud, you could not manipulate an image interactively. While you could manipulate text, it would be impractical to manipulate high-resolution bitmaps. With high-resolution color scanners rapidly becoming an inexpensive reality, interactive image manipulation will be a necessity.
With applications such as large graphics databases, any compression is welcome. With other applications (such as interactive graphics systems) bitmap reconstruction time is of paramount importance. Consequently, any reduction in bitmap size would directly translate into improvement of response time.
You can reduce transmission time to enable more efficient graphics data manipulation by using the following methods:
One such graphics engine is the Intel 82786, a chip that contains many graphics instructions/primitives embedded in hardware. The 82786 also provides a 40-Mbyte/second bandwidth to graphics memory (a power that will be discussed later).
The programs described in this article are designed to illustrate the specific advantages provided by a dedicated graphics coprocessor like the 82786. The image compilation code consists of two stand-alone programs one program for image compression and the other for image reconstruction.
The compression is performed entirely by the microprocessor, which converts (compiles) an image/bitmap into a series of higher-level graphics instructions. The graphics program, not the bitmap, is stored on the hard disk. To reconstruct an image, the CPU loads the graphics program into graphics memory. The graphics coprocessor then executes the code and the bitmap is perfectly restored.
Parallelism can be harvested for improved performance. The graphics program can be split into subprograms. As the CPU loads one subprogram, the graphics coprocessor can be executing another, thus reconstructing an image piece-by-piece in parallel.
If this method of data compression is so great, you might ask, why isn't it being used more widely? Several reasons can be given for this. For one thing, inexpensive dedicated graphics hardware is relatively new. People are just beginning to appreciate the power and flexibility that these machines offer. The cost of these machines may still be prohibitive for some applications. Another reason is that compression takes time--the bigger and more complex the bitmap, the longer it takes. In some cases, this outweighs the gain. Yet another reason is that it takes time, money, and programming skills to refine and solidify compression algorithms. (It took two weeks to write the software in Listing One and Listing Two.) Finally, data compression does not work in all cases. Any general-purpose compression method must make some files longer (otherwise you could continually apply the method to produce an arbitrarily small file).<fn1>
However, you could always apply the compression method, then see if the file gets smaller. If it does not get smaller, you could then stay with the original. Therefore, the resulting file is always less than or equal to, in size, to the original file.
The compression program shown in Listing One, expects an 8-bit-per-pixel 640 x 480 bitmap to reside in graphics memory (graphics memory is mapped into part of system memory space). The only necessity is graphics memory accessibility to the CPU.
The easiest (and most obvious) way to compile an image is to:
This procedure would be repeated for all possible colors (in this case 0 through 255). The bitmap will be scanned as many times as there are possible colors. This could get out of hand with 2K x 2K 32-bit-per-pixel bitmaps. Even with 8 bits per pixel, scanning a 640 x 480 bitmap 256 times takes over an hour. The obvious way is usually not the best way.
The next most obvious approach is to process only the colors that the bitmap contains. This requires an overhead of a single pass through the bitmap (one would have an array of flags that would be set, once a color was detected). This helps, but more can be done.
Because the x and y coordinates are always known during the image scan, it is easy to find the maximum and minimum x and y coordinates for each color. A smaller region could be scanned during the compilation stage. This is exactly what the find_all_colors procedure of the compression program does. It scans through the bitmap once and establishes the region of color existence. A special structure color_struct, handles this. Each element in the structure contains the maximum and minimum x and y coordinates and the number of times that the color is detected during the scan. To make life easier, a type color_t of color_struct is defined.
The next stage is to compile each of the regions of color, the extract_scan_lines procedure. Adding some initialization instructions is appropriate since you are making a graphics coprocessor instruction stream. Place a define color and a scan lines instruction (see sidebar for a discussion of the scan lines instruction) into a buffer. The array of scan lines will follow. Then proceed one scan line at a time, starting at minimum y and x coordinate for this color.
The run-length encoding is quite simple: as the desired color is found, a flag is set. If the next pixel is of the same color, the count is incremented. If it is not of the same color, the end of the run has been reached and its length is stored in the buffer. This goes on, line-by-line of an image, until maximum y and x have been reached. This procedure is repeated for each color in the image.
The graphics coprocessor instruction stream is stored in an array called buff. This array is several disk blocks in size. When it is filled, an end instruction is added and the array is written to a file on hard disk.
The loader program, found in Listing Two expects a file to be in a specific format, which "compact" conforms to. This format consists of packets of data that are preceded by a header. The header describes the address in graphics memory where the data is to be placed and how many bytes of data are to be placed.
The loader program performs some initialization tasks before loading the graphics coprocessor instructions into graphics memory. It waits for the graphics coprocessor to finish any instructions that may still be executing. It then loads the first packet of graphics instructions (scan lines) and directs the graphics coprocessor to execute them. While the graphics coprocessor is executing these instructions, the main processor gets another packet from the disk. This process continues until all packets have been loaded. The loader takes a time stamp before and after the loading process and reports the total time that it took to load and reconstruct the bitmap.
To further illustrate some of the performance advantages that a graphics coprocessor provides, Table 1, page 43, lists the test results. These tests were run on Intel's Xenix 311 system (which uses a 6-MHz 80286 microprocessor) with an 82786 add-in board (20 MHz with 1 Mbyte of graphics memory). All bitmaps were 640 x 480 at 8 bits per pixel. Bitmaps 1 - 3 are of Mandelbrot fractals. Bitmap 1, which consists of a straight uncompressed bitmap, is the control. Bitmap 4, a solid, single color bitmap, illustrates the best case.
Compression Compression Reconstruction File Compression
Method Time Time Size Ratio
Bitmap 1 none n/a 3.5 sec 307K 1:1
Bitmap 2 scan lines 612 sec. 1.3 sec. 120K 2.5:1
Bitmap 3 scan lines 613 sec. 1.3 sec. 121K 2.5:1
Bitmap 4 scan lines 11 sec. 0.02 sec. 2.9K 105:1
After reviewing the test results for bitmaps shown in Table 1, you may think that 10 minutes is an excessive price to pay for a 2 1/2 times reduction in size and reconstruction time. It is for some applications. For other applications, it allows them to place 2 1/2 times more information on the storage medium to present 2 1/2 times the amount of data to the user in a given amount of time or to retrieve images 2 1/2 times faster. This could make or break an application. Effectively, an 8-bits-per-pixel bitmap has been reduced down to about 3-bits per pixel, without losing any information.
Some of the routines developed are useful for digital image processing. For example, find_all_colors routine generates a profile of the bitmap by quoting the number of times a color appeared in the bitmap. This could be turned into the probability density quote by dividing that count by the total number of pixels in the bitmap. This could be taken one step farther. Based on the probability density quote of a color, you could decide that the color is rare in a bitmap and is not worth processing. This could reduce the compression time as well as compressing the file, at a cost of losing some information. Using this method, you could minimize the picture content that is lost.
In any case, the compaction algorithm speed could be improved (about three times by my estimates). If you used a 20-MHz 80386, the compression time would dip to less than a minute.
This image compilation technique offers infinite avenues for further exploration. This article has explored only a single instruction. Other instructions (bit_blit, for example) offer other possibilities. The graphics coprocessors that are presently available have a great variety of instructions, and this method of image compilation can lead to an adaptive image compression.
It is possible to predict whether an image can be compressed by using run-length encoding. An average length of a run can be calculated for an image. If the average run takes up more space than one scan lines array element (dx, dy, and length use 6 bytes) then run-length encoding is worthwhile. For example, at 8 bits (one byte) per pixel, the average run for an image must be greater than 6 pixels. This is the break-even point for a compression technique. The compression ratio can be improved by removing redundancy from the compressed file. This can be accomplished by encoding repetitive scan lines sequences in the 82786 macros/subroutines. This achieves a two-dimensional compression.
Another method is to reduce the number of bits used for dx, dy, and length elements in the scan lines array by scanning through the array and determining the maximum values ever used. This would require extra processing by the CPU, which would increase encoding and reconstruction time. A differential encoding technique could also be used to encode the differences between successive dx, dy, and length values.<fn2> This also requires some extra CPU processing. By using combinations of these techniques, you could increase compression ratios to above 10:1. The penalty of added CPU processing time may still outweigh the benefit of reduced I/O time caused by improved compression.
Compression techniques are still in the infancy, and many promising techniques are emerging, such as "Chaotic Compression" (see Computer Graphics World, November 1987) promises a 10,000:1 compression ratio.
2. 82786 Graphics Coprocessor User's Manual. Intel, 1987.
One of the most powerful 82786 instructions is scan lines, which is used to draw a series of horizontal lines. It is the fastest 82786 drawing instruction, executing at up to 2.5 million pixels per second, at 8 bits per pixel (faster at lower pixel depths). This instruction is generally used for area fills, and has pattern capabilities.
The scan lines instruction looks like this: 1. the instruction itself, 16 bits (0BA00H); 2. the address of the scan lines array, a 32-bit value, low word followed by the high word; and 3. the number of horizontal lines to be drawn.
The scan lines array elements have a particular format, consisting of: 1. dx, an offset from the beginning of the previous line in the x direction (16 bits, negative or positive); 2. dy, an offset from the beginning of the previous line in the y direction (16 bits, negative or positive); and 3. the length of the line (16 bits, negative or positive).
The scan lines instruction starts at the present graphics location, adds dx and dy values of the first array element to it, and draws a line of the specified length. The graphics location is left at the beginning of the line. The new graphics location is then adjusted by dx and dy values of the second array element. The second line is then drawn. This process is repeated until the specified number of lines have been drawn. You could thus draw a scan line at the bottom of the screen and then one at the top of the screen, all within the same scan lines array.
Areas of any shape can be drawn by using the scan lines instruction, and they do not have to be contiguous. You can jump to any position on the screen and continue drawing at any time, all with a single array (as long as the color and the pattern can remain constant).
You can break up an image into areas of constant color and use a single scan lines array to describe each of them (one for black, one for white, one for a shade of green, and so forth). It would take as many scan lines arrays as there are colors in an image to completely describe that image.
The scan lines instruction closely resembles run-length encoding. Run-length encoding removes redundancy from a data file by replacing data elements with the count followed by the element itself. For example, a sequence of AAAAAA can be replaced with 6A, resulting in 3:1 compression. The same technique can be applied to images. A sequence of six black pixels can be replaced by the number 60 (where 6 is the count and 0 is the color black). For an area of constant color, specifying the color along with every run is redundant. You can specify the offset from the current graphical location followed by the run-length.
This should begin to resemble the scan lines definition--dx, dy, and length. For many images, encoding areas in this fashion is an efficient way of removing redundancy, thereby compressing an image. The less space an image takes, the faster it can be transmitted or retrieved from storage.
_IMAGE COMPRESSION VIA COMPILATION_
by
Victor J. Duvanenko
[LISTING ONE]
/* Bitmap compaction program. */
/* Converts bitmaps in 82786 graphics memory to Graphics processor instruc- */
/* tions. Simulates run length encoding, causing data compression for most */
/* bitmaps. Compression of an 8 bits per pixel down to 3 bits per pixel is */
/* not uncommon. */
/* Created by Victor J. Duvanenko */
/* Usage: compact output_file_name */
/* Input: */
/* An 82786 eight bits per pixel bitmap at address of 0x10000 (this */
/* can be easily changed). The bitmap is 640 pixels wide and 480 */
/* pixels heigh (this can also be changed). This was done for the */
/* simplicity of this example. */
/* Output: */
/* Binary file in the following format. */
/* a) Header */
/* 1) type ( 0 - GP instructions, 1 - bitmap data ). */
/* 2) 32 bit address (lets the loader know where to place the */
/* data in graphics/82786 memory). If equal to 0xffffffff */
/* then the loader can place data anywhere. */
/* 3) number of bytes to load. */
/* b) Data */
/* 1) define color instruction */
/* 2) scan line instruction */
/* 3) link instruction (link around the array) */
/* 4) scan line array */
/* Caution: The loader must add a 'stop' instruction to the data */
/* (a NOP instruction with GCL bit set). See loader source */
/* code for example. */
/* */
/* This program was written for the XENIX environment, but can be easily */
/* and quickly ported to the PC. Just concentrate on the ideas and not on */
/* the implementation specifics. I'll try to point out XENIX specific sec- */
/* tions. */
#include<stdio.h>
#include<fcntl.h>
#include<sys/param.h>
#include "/usr/tls786/h/tls786.h"
#include "/usr/tls786/h/tv1786.h"
#defineMAX_NUM_COLORS 256 /* maximum number of colors */
#define GP_BUFF_SIZE 8192 /* GP instruction buffer size */
#define BITMAP_WIDTH 640
#define TRUE 1
#define FALSE 0
#define OK TRUE /* return status for procedures */
#define PMODE 0644 /* protection mode of the output file */
#define MOVSW_ON TRUE /* enable 'move strings' in XENIX driver */
#define DEBUG FALSE /* top debug level - a fun one to turn on */
#define DEBUG_1 FALSE /* next debug level deeper */
#define DEBUG_2 FALSE /* everything you'd ever care to trace */
/* Global data buffers - used by several routines */
unsigned int gp_buff[ GP_BUFF_SIZE ]; /* GP instruction buffer */
unsigned int buff[ GP_BUFF_SIZE ]; /* temporary storage buffer */
unsigned char line_buff[ BITMAP_WIDTH ]; /* line buffer */
/* line_buff should ideally be dynamically alocated to allow any */
/* bitmap width. Left as an excersize for a C hacker. */
int p6handle; /* XENIX file descriptor for the 82786 memory */
int bm_height = 480; /* bitmap height */
int bm_width = 640; /* bitmap width */
long bm_address = 0x10000L; /* bitmap address */
/* Description of each color, histogram, plus additional fields for added */
/* dramatic performance improvement (defines a window of color existance). */
/* Enable DEBUG to see time savings that result from this technique. */
struct color_struct
{
long count; /* number of times a color appears in the bitmap */
int begin_y, /* scan line where a color first appears */
end_y, /* scan line where a color last appears */
begin_x, /* x position where a color first appears */
end_x; /* x position where a color last appears */
};
typedef struct color_struct color_t;
/* Array containing color information about a bitmap under analysis */
color_t colors[ MAX_NUM_COLORS ];
/*---------------------------------------------------------------------*/
/* The body of the data compression program. */
/*---------------------------------------------------------------------*/
main(argc,argv)
int argc;
char *argv[];
{
register i, index, j, num_colors;
int n, value, x, y;
int f1, f2, /* file descriptors */
buff_overflow;
/* the following variables are for debug purposes only */
long average_begin_y, average_end_y;
long average_begin_x, average_end_x;
float percentage_y, percentage_x;
color_t *clr_p;
/* XENIX needed structures needed for movsw section of the driver */
union {
struct tv1_cntrl brddata;
byte rawdata[ sizeof( struct tv1_cntrl ) ];
struct io_data rdata;
} regdata;
/* Check the command line for proper syntax, a little */
if (argc < 2)
{
fprintf( stderr,"Usage is: %s output_file_name\n", argv[0] );
exit(1);
}
/* Open the file where compacted bitmap will be placed. If it doesn't */
/* exist create it. */
if (( f2 = open( argv[1], O_CREAT | O_WRONLY, PMODE )) == -1 )
{
fprintf( stderr, "%s: Can't create %s.\n", argv[0], argv[1] );
exit(1);
}
/* XENIX specific functions to allow one to treat 82786 graphics memory */
/* as a file - a file descriptor gets passed to every routine that talks */
/* to the 82786. This allows a very flexible multiple 82786 environment. */
p6handle = open786( MASTER_786 );
if ( p6handle == NULL ) {
fprintf( stderr, "%s: Can't access 82786.\n", argv[0] );
exit(1);
}
#if MOVSW_ON
/* XENIX specific - enable movsw in the 82786 driver */
ioctl( p6handle, TEST_SFLAG, ®data );
if ( regdata.rdata.regval == FALSE )
ioctl( p6handle, SET_SFLAG, &value );
#endif
/* Find all unique colors in the bitmap file. */
num_colors = find_all_colors( colors, bm_height );
#if DEBUG
/* histogram and performance improvement information of the color */
/* existance window technique. */
printf( "num_colors = %d\n", num_colors );
average_begin_y = average_end_y = 0L;
average_begin_x = average_end_x = 0L;
for( i = 0; i < MAX_NUM_COLORS; i++ )
{
clr_p = &colors[i]; /* for denser and cleaner notation purposes */
printf( "c %4d %7ld b_y%4d e_y%4d", i, clr_p->count, clr_p->begin_y,
clr_p->end_y );
printf( " b_x%5d e_x%5d\n", clr_p->begin_x, clr_p->end_x );
/* average only the existing colors */
if ( clr_p->count != 0 )
{
average_begin_y += (long)clr_p->begin_y;
average_end_y += (long)clr_p->end_y;
average_begin_x += (long)clr_p->begin_x;
average_end_x += (long)clr_p->end_x;
}
}
printf( "\n" );
average_begin_y /= (long)num_colors;
average_end_y /= (long)num_colors;
printf( "average Y begin = %ld\t\taverage Y end = %ld\n", average_begin_y,
average_end_y );
percentage_y = ((float)( average_begin_y ) / bm_height * 100 );
percentage_y += ((float)((long)( bm_height ) - average_end_y ) / bm_height
* 100 );
printf( "percentage Y savings = %2.2f\n", percentage_y );
average_begin_x /= (long)num_colors;
average_end_x /= (long)num_colors;
printf( "average X begin = %ld\t\taverage X end = %ld\n", average_begin_x,
average_end_x );
percentage_x = ((float)( average_begin_x ) / bm_width * 100 );
percentage_x += ((float)((long)( bm_width ) - average_end_x ) / bm_width
* 100 );
printf( "percentage X savings = %2.2f\n", percentage_x );
#endif
/* Relying on the loader to execute a def_bitmap instruction before */
/* loading the GP instruction list generated by this program. */
/* Convert each color in the bitmap into scan lines - one color at a time */
for( i = index = 0; i < MAX_NUM_COLORS; i++ )
{
if ( colors[i].count == 0L ) continue; /* skip non-existant colors */
buff_overflow = FALSE;
n = extract_scan_lines((long)(index << 1),colors, i, buff, &buff_overflow);
if ( buff_overflow )
{
fprintf( stderr, "GP instruction list overflow.\n" );
exit( 1 );
}
/* If the newly extracted scan lines array can't fit into the GP */
/* instruction buffer, store instruction built up so far, and */
/* start filling the buffer from the begining. */
if (( index + n ) > GP_BUFF_SIZE )
{
/* Flag the user if a color generates more lines than there is */
/* space in the instruction buffer. Very unlikely. */
if ( index <= 0 )
{
fprintf( stderr, "Instruction list overflow.\n" );
exit( 1 );
}
/* store GP instruction built up so far */
write_buffer_to_file( f2, gp_buff, index );
/* adjust the addresses in the GP instruction set */
/* since the GP code is not relocatable. */
index = 0;
buff[ 4 ] = (int)(( 20L ) & 0xffffL ); /* scan line array address */
buff[ 5 ] = (int)(( 20L ) >> 16 );
buff[ 8 ] = (int)(( (long)( n << 1 )) & 0xffffL ); /* link address */
buff[ 9 ] = (int)(( (long)( n << 1 )) >> 16);
}
/* copy elements from temporary buffer into instruction buffer */
for ( j = 0; j < n; )
gp_buff[ index++ ] = buff[ j++ ];
#if DEBUG
printf( "index = %d\n", index );
#endif
}
/* store whatever is left in the very last buffer */
if ( index > 0 )
write_buffer_to_file( f2, gp_buff, index );
#if MOVSW_ON
/* XENIX specific - disable movesw in the 82786 driver */
if ( regdata.rdata.regval == FALSE )
ioctl( p6handle, CLEAR_SFLAG, &value );
#endif
return( 0 ); /* DONE!!! Wasn't that simple?! */
}
/*-------------------------------------------------------------------------*/
/* Scan through the bitmap once and fill the 'colors' array with some */
/* very useful data about each color - how many times it apears in the */
/* bitmap and where in the bitmap it resides (define a window of existance */
/* for each color. Return number of colors that were found in the bitmap. */
/*-------------------------------------------------------------------------*/
find_all_colors( colors, num_lines )
color_t colors[]; /* array of colors - 256 elements */
int num_lines; /* number of lines in the bitmap */
{
register int x; /* x coordinate on a scan line */
register color_t *color_ptr; /* pointer - for speed */
register int n; /* number of bytes in a scan line */
int line, /* present scan line in the bitmap */
num_colors; /* number of colors found in the bitmap */
#if DEBUG_1
printf("Entered find_all_colors routine. num_lines = %d\n", num_lines );
#endif
/* Initialize the 'colors' array. */
for( x = 0; x < MAX_NUM_COLORS; )
{
color_ptr = &colors[x++]; /* use a pointer for speed */
color_ptr->count = 0L;
color_ptr->begin_y = color_ptr->end_y = 0;
color_ptr->begin_x = color_ptr->end_x = 0;
}
/* Scan and analyze the bitmap one line at a time. */
for ( line = 0; line < num_lines; line++ )
{
n = get_scan_line( bm_address, line_buff, line, bm_width );
for( x = 0; x < n; x++ )
{
color_ptr = &( colors[ line_buff[x] ]);
/* mark the begining scan line for this color */
if ( color_ptr->count++ == 0L )
{
color_ptr->begin_y = line;
color_ptr->begin_x = x;
}
/* adjust the ending scan line each time a color is detected */
color_ptr->end_y = line;
/* adjust x window for a color if needed */
if ( x < color_ptr->begin_x ) color_ptr->begin_x = x;
if ( x > color_ptr->end_x ) color_ptr->end_x = x;
}
}
for ( x = num_colors = 0; x < MAX_NUM_COLORS; )
if ( colors[x++].count > 0L ) num_colors++;
#if DEBUG_1
printf( "Exited find_all_colors routine.\n" );
#endif
return( num_colors );
}
/*-------------------------------------------------------------------------*/
/* The heart of compression. */
/* Procedure to extract scan lines from a bitmap file (with some help from */
/* 'colors' array). Assumes that the GP buffer is impossible to overrun */
/* (left as an exercise to correct). The best way to understand this one */
/* is to go through it with a particular bitmap in mind. */
/*-------------------------------------------------------------------------*/
extract_scan_lines( start_addr, colors, color, buff, overflow )
long start_addr; /* starting address of this GP instruction list */
color_t colors[]; /* colors description array */
int color, /* color that is being extracted */
buff[], /* gp instruction buffer */
overflow; /* overflow flag, gets set if the instruction buffer end */
/* is reached = ( num_elements - GP_BUFF_THRESHOLD ) */
{
/* Keep x and y coordinates from call to call - needed to calculate */
/* dx and dy of the next scan line array. */
static int x = 0, /* present x coordinate */
y = 0; /* present y coordinate */
register i, count, line;
int index, dy; /* gp instruction buffer index */
int n, num_lines,
num_lines_index, first_time;
int link_lower, link_upper;
BOOLEAN within_scan_line;
#if DEBUG
printf( "color = %d\n",color );
#endif
/* Start at the begining of a buffer and add the GP instructions */
/* to define color, scan lines, and link (around the array). */
/* Relies on the loader to def_bitmap, texture, and raster operation. */
index = 0;
/* def_color instruction */
buff[ index++ ] = 0x3d00;
buff[ index++ ] = (((int)color ) | (((int)color ) << 8));
buff[ index++ ] = 0;
/* scan_lines instruction */
buff[ index++ ] = 0xba00;
buff[ index++ ] = (int)(( start_addr + 20L ) & 0xffffL );
buff[ index++ ] = (int)(( start_addr + 20L ) >> 16 );
num_lines_index = index++; /* number of lines in the scan lines */
/* array is not yet known. */
/* link instruction - jump around the array */
buff[ index++ ] = 0x0200;
link_lower = index++; /* fill in when the number of elements is */
link_upper = index++; /* known. */
num_lines = 0;
first_time = TRUE;
/* start at the bottom of the window (of this color) */
/* and process one line at a time until the top of the window. */
dy = line = colors[ color ].begin_y;
for ( ; line <= colors[ color ].end_y; line++ )
{
n = get_scan_line( bm_address, line_buff, line, bm_width );
count = 0;
within_scan_line = FALSE;
/* Process the line one pixel at a time */
n = colors[ color ].end_x;
for( i = colors[ color ].begin_x; i <= n; i++ )
{
if ( line_buff[i] != color )
{
/* found a pixel that is not of desired color */
if ( within_scan_line )
{
/* reached the end of scan line of desired color */
buff[ index++ ] = --count; /* length of it */
within_scan_line = FALSE;
y += dy;
count = dy = 0;
num_lines++;
}
continue; /* to the next pixel */
}
else /* found a pixel of desired color */
{
if ( ! within_scan_line ) /* found the begining */
{
buff[ index++ ] = i - x; /* dx for scan line instruction */
x = i;
if ( first_time )
{
/* first time for this color */
#if DEBUG_2
printf( "first time, y = %d, dy = %d\n", y, dy );
#endif
buff[ index++ ] = dy - y; /* dy for scan line */
y = dy;
dy = 0; /* reset dy, now that we've moved */
first_time = FALSE;
}
else
buff[ index++ ] = dy; /* dy for scan line instr. */
within_scan_line = TRUE; /* signal the begining edge */
}
count++;
/* Take care of the last pixel == color case */
if ( i == n )
{
buff[ index++ ] = --count;
within_scan_line = FALSE;
y += dy;
count = dy = 0;
num_lines++;
}
}
}
#if DEBUG_1
printf( "x = %d,\t y = %d\n", x, y );
#endif
dy++;
}
/* Now, the number of lines of this color is known. */
/* Therefore, scan line array instruction and link address can be filled.*/
buff[ num_lines_index ] = num_lines;
buff[ link_lower ] = (int)(( start_addr + (long)( index << 1)) & 0xffffL );
buff[ link_upper ] = (int)(( start_addr + (long)( index << 1)) >> 16);
#if DEBUG_2
printf( "num_lines = %d,\tx = %d,\t y = %d\n", num_lines, x, y );
#endif
return( index );
}
/*--------------------------------------------------------------*/
/* Procedure that writes the GP instruction list to a file. */
/* An appropriate header is added before the GP list. */
/*--------------------------------------------------------------*/
write_buffer_to_file( fd, buff, num_of_elements )
int fd, /* output file descriptor */
buff[], /* pointer to the buffer */
num_of_elements; /* number of elements to be written */
/* each element is 16 bits (integer) */
{
/* Header - placed before every block (8 bytes) */
struct header
{
int type; /* 0 - GP instructions, 1 - bitmap */
long addr; /* load address, ffffffff - don't care */
int num_bytes; /* number of bytes */
};
typedef struct header header_t;
header_t hdr;
/* Write the header into the file */
hdr.type = 0;
hdr.addr = 0L; /* tell the loader to place instructions */
/* address 0 in 82786 memory. */
hdr.num_bytes = num_of_elements << 1;
/* Write the header into the output file */
if ( write( fd, &hdr, sizeof( hdr )) != sizeof( hdr ))
{
fprintf( stderr, "compact: Write error.\n" );
exit(1);
}
/* Write the GP instruction list into the output file */
if ( write( fd, buff, num_of_elements << 1 ) != ( num_of_elements << 1 ))
{
fprintf( stderr, "compact: Write error.\n" );
exit(1);
}
return( OK );
}
/*--------------------------------------------------------------------*/
/* Procedure to read any scan line from the bitmap stored in graphics */
/* memory. Swap bytes to make scanning easier. */
/*--------------------------------------------------------------------*/
get_scan_line( base_addr, buff_gsl, line, line_width )
long base_addr; /* starting address of the bitmap */
unsigned char *buff_gsl; /* scan line buffer */
int line, /* which line to read */
line_width; /* how many pixels in a line */
{
long address;
#if DEBUG_1
printf( "Entered get_scan_line routine. addr = %lx", addr );
printf( "\tline = %d\tline_width = %d\n", line, line_width );
#endif
address = base_addr + ((long)( line ) * (long)( line_width ));
getmem( p6handle, address, buff_gsl, line_width >> 1 );
swab( buff_gsl, buff_gsl, line_width );
/* be carefull with swab (note that source and destination are the same) */
/* functionality depends on implementation of the swab routine. */
#if DEBUG_1
printf("Exited get_scan_line routine.\n");
#endif
return( line_width );
}
[LISTING TWO]
/* A simple GP instruction list loader. */
/* Created by Victor J. Duvanenko */
/* */
/* Loads a GP instruction list from a file into 82786 memory and instructs */
/* the GP to execute them. If the file contains more instructions they are */
/* read in. The loader then waits for the GP to finish the previous list. */
/* Only when the GP is finished does the loader place the new list in 82786 */
/* memory. */
/* */
/* Usage: load file_name */
/* */
/* Input: Binary file of the followind format */
/* a) Header */
/* 1) type ( 0 - GP instructions, 1 - bitmap data ). */
/* 2) 32 bit address (lets the loader know where to place the */
/* data in graphics/82786 memory). If equal to 0xffffffff */
/* then the loader can place data anywhere. */
/* 3) number of bytes to load. */
/* b) Data */
/* 1) GP instruction list. */
/* */
/* Output: GP instructions are loaded into 82786 memory. */
/* */
/* The loader provides the following services (may harm some applications) */
/* 1) def_bitmap, def_texture, and raster_op instructions with certain */
/* defaults are executed before loading the GP instruction list. */
/* 2) "stop" instruction is placed at the end of every GP list - 'nop' with */
/* GCL bit set. */
/* 3) Load time quote in milliseconds. */
#include<stdio.h>
#include<fcntl.h>
#include<sys/types.h>
#include<sys/timeb.h>
#include "/usr/tls786/h/tls786.h"
#include "/usr/tls786/h/tv1786.h"
#define BUFF_SIZE 32600
#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define OK 1
#define INTERVAL 1 /* Sampling period in milliseconds */
#define WAIT 5000 /* wait period for the GP or DP to finish */
#define COMM_BUF_BOTTOM 0L
#define DEBUG FALSE
#define DEBG_1 FALSE
/* GP instruction list buffer */
unsigned char buff[ BUFF_SIZE ];
main(argc,argv)
int argc;
char *argv[];
{
register i;
int p6handle, f1, n_items, ellapsed_time, value;
struct timeb time_before, time_after;
long addr,
addr_bm; /* bitmap base address */
/* Header - placed before every block (8 bytes) */
struct header
{
int type; /* 0 - GP instructions, 1 - Bitmap */
long addr; /* load address, ffffffff - don't care */
int num_bytes; /* number of bytes */
};
typedef struct header header_t;
header_t hdr;
/* XENIX specific - turns on movsw instruction */
union
{
struct tv1_cntrl brddata;
byte rawdata[ sizeof( struct tv1_cntrl )];
struct io_data rdata;
}regdata;
/* Check command line for proper usage - just a little. */
if (argc == 1)
{
fprintf( stderr, "Usage is: %s file_name\n", argv[0] );
exit(1);
}
/* Open the input file for reading only. */
if (( f1 = open( argv[1], O_RDONLY )) == -1 )
{
fprintf( stderr, "%s: Can't open %s.\n", argv[0], argv[1] );
exit(1);
}
/* XENIX specific - enable the 82786 driver. */
p6handle = open786( MASTER_786 );
if ( p6handle == NULL ) {
fprintf( stderr, "%s: Can't access 82786.\n", argv[0] );
exit(1);
}
/* XENIX specific - enable the use of movsw instruction driver. */
value = 0;
ioctl( p6handle, TEST_SFLAG, ®data );
if ( regdata.rdata.regval == FALSE )
ioctl( p6handle, SET_SFLAG, &value );
addr = 0L;
addr_bm = 0x10000L;
ftime( &time_before ); /* Get present time stamp */
/* A bit of overhead to make sure that the bitmap and texture are defined */
/* before the GP command list is loaded. */
i = 0;
buff[ i++ ] = 0x00; /* Def_bitmap */
buff[ i++ ] = 0x1a;
buff[ i++ ] = 0x00;
buff[ i++ ] = 0x00;
buff[ i++ ] = 0x01;
buff[ i++ ] = 0x00;
buff[ i++ ] = 0x7f; /* 640 (for now) */
buff[ i++ ] = 0x02;
buff[ i++ ] = 0xdf; /* by 480 (for now) */
buff[ i++ ] = 0x01;
buff[ i++ ] = 0x08; /* 8bpp (for now) */
buff[ i++ ] = 0x00;
buff[ i++ ] = 0x00; /* Def_logical_op */
buff[ i++ ] = 0x41;
buff[ i++ ] = 0xff;
buff[ i++ ] = 0xff;
buff[ i++ ] = 0x05;
buff[ i++ ] = 0x00;
buff[ i++ ] = 0x00; /* Def_texture */
buff[ i++ ] = 0x06;
buff[ i++ ] = 0xff;
buff[ i++ ] = 0xff;
buff[ i++ ] = 0x01; /* stop */
buff[ i++ ] = 0x03;
/* Wait for a previous GP command list to finish */
if ( waitgp( p6handle, INTERVAL, WAIT ) < 0 ) {
printf("GP is hung!!!\n");
exit(1);
}
/* Place it in 786 graphics memory */
putmem( p6handle, addr, buff, i >> 1 );
/* Direct the GP to execute the command */
putreg( p6handle, GRP_GR1, (int)( addr & 0xffff ));
putreg( p6handle, GRP_GR2, (int)( addr >> 16 ));
putreg( p6handle, GRP_GR0, 0x200 );
/* Now, for the GP list from an input file. */
/* Read the header and then the data. */
while (( n_items = read( f1, &hdr, sizeof( hdr ))) > 0 )
{
i = 0;
if ( n_items != sizeof( hdr ))
{
printf( stderr, "%s: Read error.\n", argv[0] );
exit(1);
}
/* does it matter where the GP list is placed? */
if ( hdr.addr != 0xffffffffL ) addr = hdr.addr;
/* GP instruction list */
if ( hdr.type == 0 )
{
if (( n_items = read( f1, buff, hdr.num_bytes )) == hdr.num_bytes )
{
/* Add a "stop" command to the GP instruction list */
i += n_items;
buff[ i++ ] = 0x01;
buff[ i++ ] = 0x03;
/* Wait for the GP to finish any previous instruction */
if ( waitgp( p6handle, INTERVAL, WAIT ) < 0 )
{
fprintf( stderr, "GP is hung!!!\n" );
exit( 1 );
}
/* Place it in 786 graphics memory */
putmem( p6handle, addr, buff, i >> 1 );
}
else
{
printf( stderr, "%s: Read error.\n", argv[0] );
exit(1);
}
/* Direct the GP to execute the command */
putreg( p6handle, GRP_GR1, (int)( addr & 0xffff ));
putreg( p6handle, GRP_GR2, (int)( addr >> 16 ));
putreg( p6handle, GRP_GR0, 0x200 );
}
/* Is it bitmaps - then place the data at that address */
if ( hdr.type == 1 )
{
if (( n_items = read( f1, &buff[i], hdr.num_bytes )) == hdr.num_bytes )
{
/* Place it in 786 graphics memory */
putmem( p6handle, addr_bm + hdr.addr, buff, n_items >> 1 );
}
}
}
/* Get the time stamp after the loading is done. */
ftime( &time_after );
ellapsed_time = (int)( time_after.time - time_before.time ) * 1000;
ellapsed_time += ( time_after.millitm - time_before.millitm );
printf( "%dms\n", ellapsed_time );
/* XENIX specific - disable movesw in the 786 driver */
if ( regdata.rdata.regval == FALSE )
ioctl( p6handle, CLEAR_SFLAG, &value );
return(0);
}