IMAGE MATHEMATICS
Image enhancement by numbers
Victor Duvanenko
Victor is a graduate student in electrical and computer eng., with a minor in computer graphics at North Carolina State University. At the time of this writing he was a consultant at Silicon Engineering, in Santa Cruz, Calif. Before that be worked as an IC designer at Intel. He can be reached at 1001 Japonica Ct., Knightdale, NC 27545.
Computer scientists and users have been jealous of photographers, movie makers, and television producers for some years because computer monochrome images, or even ones with 256 colors, just didn't compare with photographic-quality (true color) images. Consequently, computer users have been forced to use cartoon-like animation and imaging. This may have been sufficient for adventure games, spreadsheets, and low-end word-processing programs, but it just wasn't good enough for image processing and photography. In short, without true color capabilities, the dream of advanced applications, such as on-line encyclopedias that provide images and movie clips, will never materialize.
In this article I'll discuss some basic functions of image processing and demonstrate one possible implementation of arithmetic functions through logical operations. Then I will use these arithmetic functions to combine and enhance images.
Imaging and Photography
When we use a camera to take a picture, the light reflected from an object passes through a reducing lens and exposes the film. We take this film to a photo lab which, using a series of chemical processing steps, develops the film. Next, photographic paper is exposed by shining light through the developed film and an enlarging lens. Chemical processing is then used again to develop the photograph.
In the electronic version of photography, we can use an electronic "camera" connected to image-capture (frame grabber) hardware to take a picture, and we can use a color printer to get a paper copy of the picture. In this process, the electronic camera serves as a reducing lens and organizes the light intensity and color information, reflected from an object, into a serial stream. The image capture hardware converts this stream into numbers, which are then stored in the computer's memory. A monitor or a printer serves as an enlarging lens, and some form of magnetic memory medium, such as disk or tape, is used to store the captured image for later recall.
But a computer is much more than a mere storage medium. It can also be used as a processing lab because, once an image has been captured and stored as numbers, that image can be enhanced or changed using mathematical manipulations to achieve some of the same tricks of the trade photographers have used for years. These techniques include the use of filters to get rid of glare, create special effects, or enrich certain colors. Other techniques include the use of black and white to create a mood, the use of zoom lenses to capture only the interesting sections of images, and the use of double exposure to superimpose several images. What's significant is that each of these techniques can be accomplished mathematically, rather than chemically.
Logical Operations
Graphics and image manipulations have traditionally been limited to logical (Boolean) operations -- XOR, NOT, OR, AND, and so on -- mostly because of inexperience, simplicity, and the dominance of monochrome hardware. Because our goal is to modify an image or combine two images, we must understand fully how picture elements (pixels) can be manipulated or combined. The simplest case is monochrome graphics, 1 bit per pixel, where 1 bit in memory corresponds to 1 dot on the screen.
A single memory bit can hold only two possible values -- 0 or 1. These two values constitute a binary (Boolean) set. Two bits can be combined in only 4 possible ways to produce a single bit (see Table 1). The process of combining 2 bits to generate a single bit is called a logical operation. There are 16 possible logical operations (see Table 2). Logical operations always produce a result that is of the same length as the original elements. In other words, if two 1-bit elements are combined, the result is always 1 bit long.
Table 1: Four possible combinations of two bits
X Y Output ------------------ 0 0 output [0] 0 1 output [1] 1 0 output [2] 1 1 output [3]
Table 2: 16 possible logical operations
--------------------------------------------------------
|X Y | 0 1 2 3 4 5 6 7 8 9 A B C D E F |
|------------------------------------------------------|
| | |
|0 0 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 |
|0 1 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 |
|1 0 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 |
|1 1 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 |
-------------------------------------------------------
G N N N X N A X (Y) (X) O P
R O O O O A N N R O
O R T T R N D O W
U (X) (Y) D R E
N R
D
Many graphics software packages allow programmers to set a "logical operation attribute" and then draw in that mode. This means that in XOR mode, as a white line is drawn over an image, all the bits along the path of that line are reversed. This is a useful technique for cursors and is used in many CAD packages.
In the monochrome world, we can emulate arithmetic operations with logic operations. If you look at the AND operation you can quickly recognize a multiply, and the OR is an add with saturate (explained later). At 1 bit per pixel, logical operations do the job perfectly. For larger pixel depths (multiple bits per pixel), however, logical operations can no longer serve as substitutes for actual arithmetic operations.
Arithmetic Operations and Saturation
Arithmetic operations on two operands have a nasty habit of producing a result of length unequal to the length of either operand. Maybe that is the reason why we make a distinction between logical and arithmetic operations. In the case of addition, if the first operand is N bits long and the second is M bits long, the result can be up to (max(N, M) + 1) bits. For example, when we add the binary numbers 1 and 1 the result is 10. In other words, for addition we may require one more bit than the longest of the two operands to store the result. Some textbooks call the generation of this extra bit a "carryout" or an overflow condition. Multiplication is even worse -- we require up to (N + M) bits to store the result. For example, multiplying binary 11 (decimal 3) by 11 (3) results in 1001 (9), which requires 4 bits of storage.
By this time you are probably wondering why we are going through this nonsense. Well, the reason is, if we add two pixels that are each 8 bits long and get a 9-bit result, how do we display this result? If we have only 8-bit numbers, how do we represent a 9-bit number?
The fact that the result uses more bits than either of the operands is irritating even in microprocessors. It is not pleasant to get a 33-bit result when adding two 32-bit numbers. How do you put the result back into a 32-bit register? Most microprocessors don't have a "crowbar" instruction. And how do you deal with the result of multiplication?
The microprocessor world has come up with a simple solution -- let the software deal with it! So most microprocessors just inform the software that an overflow condition has occurred by raising a flag. The software must then look at the flag and do something about the overflow. In the case of multiplication, the microprocessor simply stores the result in two registers and, once again, leaves it to the software to figure out how to fit the result, which now occupies twice as many bits, into a single register.
Most programmers don't concern themselves with overflow conditions. If they have even a small inkling that a data type might encounter an overflow condition, they simply go to the next larger data type. For example, if there was a possibility that an array would grow beyond 64K elements, a long (32-bit) data type would simply be used for the array index. The only reasonable aid that most high-level-language compilers give us is that if two operands of different size are being combined, the result is of the larger size. (I hope this is sufficient warning to computer scientists to make sure that results don't overflow.)
But what are graphics programmers to do when they've got only a single data type that we'll call pixel. They have no other data types to fall back on. The result must fit into the pixel data type, and the resulting display must make sense (the greens are not allowed to spill over into the reds and so on).
The solution is actually quite simple. We represent all pixels that take more bits to represent than the pixel data type can hold by the largest number that a pixel data type will hold. For example, suppose we have a 24-bit-per-pixel system in which three primary colors (red, green, and blue) are used to make up each pixel, and we use 8 bits for red, 8 bits for green, and 8 bits for blue. Any intensities of blue that take more than 8 bits to represent are represented by the largest value that does fit into 8 bits (255 decimal). In other words, when adding two pixels, if the blues are added together and the result is greater than 255, then the result is forced to be equal to 255. Some books call this technique saturation. The key point is that the resultant color is always brighter (or of equal brightness) than either of the operand pixels. If saturation isn't used, it is possible for the resultant pixel to be dimmer than either of the operand pixels -- and this makes no visual sense.
For subtraction, the result is never allowed to go negative. If subtraction of two pixels results in a negative number, the resultant pixel is forced equal to zero. This is called starvation. Thus, the resultant color for subtraction is always dimmer (or of equal brightness) than the brightest operand pixel. Multiplication is handled in the same way as addition, and division doesn't cause problems (except for generating a non-integer result).
The code for this technique is simple and is shown in Listing One. Note that 8-bit color values are first promoted to the 16-bit integer data type and then added together to ensure no overflow. The resultant pixel value is then saturated, as discussed earlier.
A more mathematically philosophical explanation might be that unsigned integer arithmetic must be used and the following rules obeyed:
- 1. When adding two numbers, the result must always be greater than or equal to either operand, but less than or equal to the maximum possible value.
- 2. When subtracting two numbers, the result must always be less than or equal to the first operand, but greater than or equal to zero.
- 3. When multiplying by other than zero, the result must always be greater than or equal to either operand, but less than or equal to the maximum possible value.
Bit Block Transfer
A Bit Block Transfer, referred to as Bit_blt, is probably the most useful graphical operation. It is used to move a rectangular block of pixels from one position within an image to another position but is really nothing more than a fancy DMA (direct memory access). Bit_blt is a bit trickier than a DMA on two counts, however:
- 1. DMA treats memory as linear, one-dimensional space and moves contiguous memory regions. Bit_blt treats memory as a two-dimensional array and moves an arbitrary-size rectangle from one spot to another.
- 2. DMA always treats memory as a linear array of bytes, words, or other byte-divisible elements. Bit_blt treats memory as a two-dimensional array of pixels, usually of 1, 2, 4, 8, 16, 24, 32, or even 48 bits in size. This implies that Bit_blt handles boundary conditions very carefully, as it may need to modify a part of a byte or a word because several pixels may fit into a byte or a word.
Bit_blt is used extensively for scrolling and windowing because it is efficient at handling rectangular regions of pixels.
After a while, merely moving pixels from one place in the image to another becomes dreadfully boring. So, graphics programmers decided to make Bit_blt perform logical operations as it moves pixels of a rectangular area. For example, an XOR Bit_blt would move a rectangular region of pixels from one location, called the source, to another, called the destination. As it moves each pixel, Bit_blt would read both the source and the destination pixel and combine every bit of the two pixels using an XOR logical operation. The result would be placed in the destination pixel. This would be done on all pixels of the source and destination rectangle. Obviously, the source and the destination have to be of the same size for this to work properly. In any case, with an XOR logical operation, the result is more exhilarating than a mere movement of a rectangular region.
Because a Bit_blt operation is a popular way of manipulating bit-map graphics, many graphics processors and coprocessors handle it with great efficiency, moving pixels at rates of millions per second. But, because most graphics programmers are satisfied with logical operations, most devices limit their repertoire to logical operations only.
Being able to manipulate images with only logical operations is fine for windowing and scrolling but is not enough for image processing and photography. Somehow, we must get from logical operations to arithmetic operations.
From Logic to Arithmetic
The techniques for combining logic operations to make other useful functions are well-established in the field of logic design. It is, for instance, possible to combine logic operations/gates to make arithmetic functions. A typical adder logic circuit is shown in Figure 1. This circuit, called a full adder, adds two bits and a carryout from the addition of the lower bits. Several single-bit adders can be configured together to make a multiple-bit adder; Figure 2 shows an 8-bit adder configuration. Other useful circuits, such as a full subtracter and a half adder, are shown in Figures 3 and Figure 4. Several full subtracters can be cascaded together to form an 8-, 16-, or even 32-bit subtracter circuit.
A modified version of the full adder logic circuit is shown in Figure 5. Note the subtle difference of using the sum to generate the carryout. The advantage of this algorithm/circuit is that it is tuned toward serial implementation, which means that it can be implemented in software more readily. The algorithm uses fewer intermediate results (in fact, it uses only one), as this is very costly in graphics. For example, a single 640 x 480 image, at 24 bits/pixel occupies approximately 1 Mbyte of memory. Every intermediate result of an operation also takes 1 Mbyte of memory, so it is costly to have intermediate results. And, if your hardware has only 3 Mbytes total, you are limited to one temporary variable when combining two 640 x 480 images. You could break the image up into smaller pieces, thereby reducing the amount of needed temporary storage, but this complicates things and makes them less efficient.
In any case, the main message is that it is possible to combine logic operations in some fashion to come up with arithmetic functions. It is not necessary to use standard algorithms. You can modify these algorithms to tune them for a specific application, to squeeze more performance out of them.
Putting the Functions to Work
Now that we have these functions, how can we use them to perform simple image-processing and photography tasks? Simple! By adding two images together, with saturation, a double exposure effect is created. Another technique might be to make color adjustments by setting the second image to a constant color and then adding or subtracting it to/from the first image. You can create the effect of underexposure by subtracting some constant value from all reds, greens, and blues, which will make an image appear darker or underexposed. For overexposure, just add a constant value.
Subtraction of two images can be useful for data compression. For example, when compressing a movie, frame-to-frame differences are quite small most of the time. Thus, if you compress only the differences between the frames, you will avoid compressing the data that has not changed. Of course, you can do just about anything by directly manipulating the image in the graphics memory (bit map).
Benchmarks
By now you are probably wondering why we are going through so much pain. The reason is performance! Because Bit_blt with logical operations is available, why not use it? All we have to do is combine several Bit_blts with different logic operations to give us an arithmetic function. Of course, we could also write our own Bit_blt routine that would perform arithmetic. But, you shall see that this is not as efficient, even when using a 20-MHz 80386.
I used a 20-MHz 80386 IDR PC AT for software development and benchmarking. I also used Digihurst image-capture and display-board, along with a Sony Multiscan monitor. The Digihurst board is a true color (24 bits/pixel) graphics board capable of image capture from an NTSC source (TV). You can hook it up to a VCR, watch a movie on the monitor, and capture any frame. This board uses three Intel 82786 graphics coprocessors, one for each primary color. The board also has 3 Mbytes of graphics memory -- 1 Mbyte for each color -- and is capable of storing three full images. After the images have been captured, they can be stored on disk.
The implementation of the modified ADDer algorithm is shown in Listing Two. As you can see, it is nothing more than a series of logical Bit_blts (cmd_copy_image procedure calls), in the order specified in Figure 5. The cmd_copy_image and cmd_wm_copy_image procedures are actually direct Intel 82786 Bit_blt commands (given to all three 82786s simultaneously).
Performance benchmarks were done on two preloaded 640 x 480 true color (24 bits/pixel) images using the code shown in Listing One. The results are shown in Table 3. The 80386 program was written in C (see Listing One) and used pointers and registers wherever possible. The Digihurst board ran the 82786s at 12.5MHz, which is below the 20-MHz top-speed specification. Running the 82786s at 2OMHz will double the performance, which will result in close to a 5:1 performance ratio.
Table 3: Performance results
80386 82786 Ratio
------------------------------------------------
Addition 10.7 sec. 4.4 sec. 2.4:1
Subtraction 10.7 sec. 4.4 sec. 2.4:1
Addition 12.7 sec. 5.5 sec. 2.3:1
(with saturation)
Subtraction 12.7 sec. 5.5 sec. 2.3:1
(with starvation)
Conclusions
The benchmarks, as usual, don't tell the whole story. The 80386 performed poorly mainly because of graphics memory bandwidth limitations. In a PC AT, the graphics board connects to the 80386 through the PC AT bus, which runs at 1OMHz at best and is only 16 bits wide. Thus, the PC AT bus presents a bottleneck to a 20-MHz 80386. The 82786 accesses graphics memory directly, without bottlenecks, plus DRAM tricks such as "page mode" accesses are used to improve graphics memory bandwidth even further. The 82786 graphics memory bandwidth peaks at 40 Mbytes/sec.
Using a graphics coprocessor can have many other benefits. Because the graphics coprocessor possesses smarts, it can share the processing load. The key here is parallelism. While the graphics coprocessor is performing a task, the CPU can be doing something else in parallel. This is not possible with pure display devices such as VGA, EGA, CGA, and so on, where the CPU must do all the work. This leads me to the conclusion that even if the algorithm runs slower on the coprocessor, it may still be advantageous to use the coprocessor for that task because of parallelism.
In any case, the algorithm discussed here used logical operations to perform simple arithmetic functions that can be used to add and subtract images with and without saturation. The performance of these functions executed by graphics coprocessors was dramatically superior to that of the CPU.
Availability
All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063; or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).
Bibliography
Intel Corp., Intel 82786 Graphics Coprocessor User's Manual. 1987.
Kohavi, Zvi. Switching and Finite Automata Theory. New York: McGraw-Hill, 1978: 138 - 144.
McCluskey, Edward J. Logic Design Principles. Englewood Cliffs, N.J.: Prentice-Hall, 1986.
How Things Work, Volume I. New York: Simon & Schuster: 202 - 203.
_IMAGE MATHEMATICS_ by Victor Duvanenko
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal<a name="0148_0012">
/* Created by Victor J. Duvanenko 10-17-88
Image addition using the CPU/80386. The program reads a buffer full of
pixels from two images, adds their pixels together and stores the result
back into the second image.
*/
#include "cmdtypes.h"
#include <stdio.h>
#include <setjmp.h>
#include "const.h"
#include <fcntl.h>
#define DEBUG 0
#define ADD 1
#define DRAW 0
extern int _fmode; /* file mode */
/* CMD configuration parameters: */
unsigned memseg=0xD000; /* memory segment */
int pbase=0x208; /* port base */
/* entire bitmap expressed as a RECT: */
RECT screen={0,0,XRES-1,YRES-1};
POINT vertices[3];
extern jmp_buf errjmp;
int frame_grab=0; /* frame/field grab */
int hiquality=0; /* use high quality image reduction routines? */
/* current video parameters */
int hue=101;
int sat=111;
int con=123;
int bri=40;
/* Red, green and blue buffers */
unsigned char red_1[ 640 * 13 ],
red_2[ 640 * 13 ],
green_1[ 640 * 13 ],
green_2[ 640 * 13 ],
blue_1[ 640 * 13 ],
blue_2[ 640 * 13 ];
/*-------------------------------------------------------------------
Invocation: add_blt
---------------------------------------------------------------------*/
main(argc,argv)
int argc;
char *argv[];
{
register i, tmp, line;
RECT image1;
int saturate;
unsigned char *r1_p, *r2_p, *g1_p, *g2_p, *b1_p, *b2_p;
cmd_init( 0xD000, 0x208 );
cmd_display( 2 );
#if DRAW
cmd_clear( 1 );
cmd_clear( 2 );
cmd_clear( 3 );
cmd_text_fgcolor( 127, 127, 127 );
cmd_text_bgcolor( 0, 0, 0 );
cmd_line_attrib( 0, 0xffff, 127, 127, 127 );
cmd_write_string( 1, 10, 1, "First bitmap." );
cmd_line( 1, 639,0, 0,479 );
cmd_line( 1, 0,0, 639,479 );
cmd_write_string( 2, 20, 1, "Second bitmap." );
cmd_line( 2, 639,0, 0,479 );
cmd_line( 2, 0,0, 639,479 );
#endif
saturate = TRUE;
for( line = 0; line < 480; line += 13 )
{
#if ADD
r1_p = red_1;
r2_p = red_2;
g1_p = green_1;
g2_p = green_2;
b1_p = blue_1;
b2_p = blue_2;
#endif
/* Perform the same operation using the CPU - 80386 in our case. */
image1.llx = 0;
image1.lly = line;
image1.urx = 639;
image1.ury = line + 12;
cmd_read_area( 1, &image1, red_1, green_1, blue_1 );
cmd_read_area( 2, &image1, red_2, green_2, blue_2 );
#if ADD
/* Add all of the pixels together - use pointers for speed. */
if ( !saturate )
for( i = 0; i < 640 * 13; i++ )
{
*r2_p++ += *r1_p++;
*g2_p++ += *g1_p++;
*b2_p++ += *b1_p++;
}
else
for( i = 0; i < 640 * 13; i++, r1_p++, g1_p++, b1_p++ )
{
tmp = (int)( *r2_p ) + (int)( *r1_p );
if ( tmp > 255 ) tmp = 255;
*r2_p++ = (unsigned char)( tmp );
tmp = (int)( *g2_p ) + (int)( *g1_p );
if ( tmp > 255 ) tmp = 255;
*g2_p++ = (unsigned char)( tmp );
tmp = (int)( *b2_p ) + (int)( *b1_p );
if ( tmp > 255 ) tmp = 255;
*b2_p++ = (unsigned char)( tmp );
}
#endif
/* Place them back into bitmap 2 */
cmd_write_area( 2, &image1, red_2, green_2, blue_2, 0 );
}
return( 0 );
} /* end main */
<a name="0148_0013"><a name="0148_0013">
<a name="0148_0014">[LISTING TWO]<a name="0148_0014">
/*-------------------------------------------------------------------
Procedure that is an extension to 'cmd_copy_image'. It performs
the image copy with an ADD operation.
This procedure figures out which of the 3 bitmaps is not being used
for the operation and uses it for scratch space. The effected area
is at the same location as the destination. The user has to be aware
of this.
---------------------------------------------------------------------*/
static void add_blt( from_bm, image, to_bm, to_x, to_y, saturate )
int from_bm;
RECT *image;
int to_bm,
to_x,
to_y,
saturate; /* 1 - saturate, 0 - don't saturate */
{
register i;
int scratch_bm, one_used, two_used, three_used;
unsigned int mask;
RECT to_image,
to_image1; /* 1 bpp coordinates */
/* Figure out which bitmap is not used in the operation and use it */
/* for scratch space. */
one_used = two_used = three_used = 0;
if ( from_bm == 1 || to_bm == 1 )
one_used = 1;
if ( from_bm == 2 || to_bm == 2 )
two_used = 1;
if ( from_bm == 3 || to_bm == 3 )
three_used = 1;
if ( !one_used )
scratch_bm = 1;
else if ( !two_used )
scratch_bm = 2;
else
scratch_bm = 3;
to_image.llx = to_x;
to_image.lly = to_y;
to_image.urx = to_x + ( image->urx - image->llx );
to_image.ury = to_y + ( image->ury - image->lly );
/* Adjust X only for 8 bpp to 1 bpp conversion */
to_image1.llx = to_x << 3;
to_image1.lly = to_y;
to_image1.urx = (( to_image.urx + 1 ) << 3 ) - 1;
to_image1.ury = to_image.ury;
/* Place a copy of the destination image in scratch space */
cmd_copy_image( to_bm, &to_image, scratch_bm, to_x, to_y, 0 );
/* Form the XOR/SUM result, in the destination bitmap */
cmd_copy_image( from_bm, image, to_bm, to_x, to_y, 1 );
/* Form the AND/CARRY result, in the scratch bitmap */
cmd_copy_image( from_bm, image, scratch_bm, to_x, to_y, 2 );
/* Now bit 0 of all pixels is done */
/* The sum 0 is already in destination bitmap and carry 0 is in AND */
/* We now need to form the sum 1, which is the XOR of bit 1 and carry 0 */
/* This requires bit 1 of destination bitmap to be XOR'ed with bit 0 of */
/* the AND/CARRY bitmap. The result is placed in the destination. */
/* This can not be accomplished at 8 bpp, as all operations happen on */
/* pixel boundaries - 8 bits. Therefore, from this point forward we */
/* must treat our bitmap as 1 bpp, since this allows single bit */
/* manipulation. */
for( i = 1, mask = 0x0202; i < 8; i++, mask <<= 1 )
{
/* Form the sum of bit i. */;
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx - 1, to_image1.lly, 1, mask, 1 );
if (( mask == 0x8080 ) && ( !saturate ))
break; /* don't form the cary - done! */
/* Form the carry bit i by first using the carry in and AND'ing */
/* it with !SUM */
cmd_wm_copy_image( to_bm, &to_image1, scratch_bm, to_image1.llx + 1, to_image1.lly, 6, mask >> 1, 1 );
/* Form the OR part of the carry bit i. */
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx - 1, to_image1.lly, 3, mask, 1 );
}
#if 0
/* the old method - took 8 blits */
/* Saturate the color based on the carry(7). */
if ( saturate )
for ( i = 7, mask = 0x0101; i >= 0; i--, mask <<= 1 )
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx + i, to_image1.lly, 3, mask, 1 );
#endif
/* new and faster algorithm - takes only 4 blits */
if ( saturate )
{
/* replicate carry[7] throughout the whole pixel of scratch space */
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 1, to_image1.lly, 0, 0x4040, 1 );
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 2, to_image1.lly, 0, 0x3030, 1 );
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 4, to_image1.lly, 0, 0x0f0f, 1 );
/* saturate the image all bits at once */
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx, to_image1.lly, 3, 0xffff, 1 );
}
/* Restore modified bitmaps to 8 bpp */
set_gpbitmap_bpp( to_bm, 8 );
set_gpbitmap_bpp( scratch_bm, 8 );
}
/*-------------------------------------------------------------------
Procedure that is an extension to 'cmd_copy_image'. It performs
the image copy with an ADD operation.
This procedure figures out which of the 3 bitmaps is not being used
for the operation and uses it for scratch space. The effected area
is at the same location as the destination. The user has to be aware
of this.
---------------------------------------------------------------------*/
static void sub_blt( from_bm, image, to_bm, to_x, to_y, saturate )
int from_bm;
RECT *image;
int to_bm,
to_x,
to_y,
saturate; /* 1 - saturate, 0 - don't saturate */
{
register i;
int scratch_bm, one_used, two_used, three_used;
unsigned int mask;
RECT to_image,
to_image1; /* 1 bpp coordinates */
/* Figure out which bitmap is not used in the operation and use it */
/* for scratch space. */
one_used = two_used = three_used = 0;
if ( from_bm == 1 || to_bm == 1 )
one_used = 1;
if ( from_bm == 2 || to_bm == 2 )
two_used = 1;
if ( from_bm == 3 || to_bm == 3 )
three_used = 1;
if ( !one_used )
scratch_bm = 1;
else if ( !two_used )
scratch_bm = 2;
else
scratch_bm = 3;
to_image.llx = to_x;
to_image.lly = to_y;
to_image.urx = to_x + ( image->urx - image->llx );
to_image.ury = to_y + ( image->ury - image->lly );
/* Adjust X only for 8 bpp to 1 bpp conversion */
to_image1.llx = to_x << 3;
to_image1.lly = to_y;
to_image1.urx = (( to_image.urx + 1 ) << 3 ) - 1;
to_image1.ury = to_image.ury;
/* Place a copy of the destination image in scratch space */
cmd_copy_image( to_bm, &to_image, scratch_bm, to_x, to_y, 0 );
/* Form the XOR/SUM result, in the destination bitmap */
cmd_copy_image( from_bm, image, to_bm, to_x, to_y, 1 );
/* Form the AND/CARRY result, in the scratch bitmap */
cmd_copy_image( from_bm, image, scratch_bm, to_x, to_y, 6 );
/* Now bit 0 of all pixels is done */
/* The sum 0 is already in destination bitmap and carry 0 is in AND */
/* We now need to form the sum 1, which is the XOR of bit 1 and carry 0 */
/* This requires bit 1 of destination bitmap to be XOR'ed with bit 0 of */
/* the AND/CARRY bitmap. The result is placed in the destination. */
/* This can not be accomplished at 8 bpp, as all operations happen on */
/* pixel boundaries - 8 bits. Therefore, from this point forward we */
/* must treat our bitmap as 1 bpp, since this allows single bit */
/* manipulation. */
for( i = 1, mask = 0x0202; i < 8; i++, mask <<= 1 )
{
/* Form the sum of bit i. */;
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx - 1, to_image1.lly, 1, mask, 1 );
if (( mask == 0x8080 ) && ( !saturate ))
break; /* don't form the cary - done! */
/* Form the carry bit i by first using the carry in and AND'ing */
/* it with !SUM */
cmd_wm_copy_image( to_bm, &to_image1, scratch_bm, to_image1.llx + 1, to_image1.lly, 2, mask >> 1, 1 );
/* Form the OR part of the carry bit i. */
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx - 1, to_image1.lly, 3, mask, 1 );
}
#if 0
/* Saturate the color based on the borrow(7). */
if ( saturate )
for ( i = 7, mask = 0x0101; i >= 0; i--, mask <<= 1 )
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx + i, to_image1.lly, 6, mask, 1 );
#endif
/* new and faster algorithm - takes only 4 blits */
if ( saturate )
{
/* replicate carry[7] throughout the whole pixel of scratch space */
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 1, to_image1.lly, 0, 0x4040, 1 );
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 2, to_image1.lly, 0, 0x3030, 1 );
cmd_wm_copy_image( scratch_bm, &to_image1, scratch_bm, to_image1.llx + 4, to_image1.lly, 0, 0x0f0f, 1 );
/* saturate the image all bits at once */
cmd_wm_copy_image( scratch_bm, &to_image1, to_bm, to_image1.llx, to_image1.lly, 6, 0xffff, 1 );
}
/* Restore modified bitmaps to 8 bpp */
set_gpbitmap_bpp( to_bm, 8 );
set_gpbitmap_bpp( scratch_bm, 8 );
}
