Channels ▼
RSS

Database

Image Compression Via Compilation

Source Code Accompanies This Article. Download It Now.


NOV88: IMAGE COMPRESSION VIA COMPILATION

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:

    1. Use a faster link (Ethernet perhaps) to the graphics terminal. At 1 Mbyte per second, it would take about 300 milliseconds to transmit a bitmap. Since Ethernet boards cost anywhere from $300 to $1,000, this is an expensive alternative.

    2. Use a graphics workstation with a local hard disk. Consider that it takes 3.5 seconds to load a 640 x 480 bitmap from a hard disk. (This was timed on a 6 MHz Xenix 311, using low-level I/O read function of C, the 80286 used a movsw instruction, disk I/O being the limiting factor.)

    3. Use a RAM disk or a graphics memory for local bitmap storage instead of hard disk. This would enable you to fit about three full bitmaps per megabyte of storage. (Keep in mind that to store two minutes of footage takes about 960 Mbytes.)

    4. Make your graphics terminal smarter so that a higher-level picture description is transmitted or stored on the hard disk, laser disk, or in graphics memory. This requires a dedicated high-performance graphics engine to reside locally to interpret the high-level commands and to reconstruct an image quickly. Today's microprocessors are much too slow for such tasks and do not have instruction sets that are well-suited for graphics.

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

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:

    1. Start with pixel 0 in scan line 0 of the bitmap

    2. Look for color 0

    3. Encode color 0 runs as the bitmap is scanned line by line.

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

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.

Benchmark Results

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.

Table 1: Test results of image compilation routines

          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.

Conclusion

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.

References

    1. Sedgewick, Robert. Algorithms. (Menlo Park: Addison-Wesley, 1983), pp 283-294.

2. 82786 Graphics Coprocessor User's Manual. Intel, 1987.

    3. Gonzalez, Rafael C. and Wintz, Paul. Digital Image Processing. (Menlo Park: Addison-Wesley, 1987).

The Scan Lines Instruction and Run-Length Encoding

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]

<a name="01f9_000c">


/*               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, &regdata );
  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 );
}



<a name="01f9_000d"><a name="01f9_000d">
<a name="01f9_000e">
[LISTING TWO]
<a name="01f9_000e">


/*            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, &regdata );
  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);
}






<pre>


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video