.so mod.ms
.ce 1
.ls 2
\fBOverview of the IRIS bitblt Primitive\fP
.sp 2.5
By Daniel Stone, Brown University/IRIS
.sp 1
.NH 1
Introduction
.sp
.PP
The IRIS bitblt primitive (here after referred to as "bitblt") was derived
after researching the following papers and books, \fBBitmap Graphics
Siggraph'84 Course Notes\fP, \fBSmalltalk-80 The Language and Its
Implementation\fP "The Graphics Kernel" and \fBInside Macintosh\fP "QuickDraw".
If one has any questions or does not know what a bitblt is, one should
look over these resources.  People who know what a bitblt primitive does
may want to skip to the "Introduction Summary" or the "Bitblt Interface"
section of this paper.  Below I will describe, in general terms where the
bitblt program came from and how it works.
.PP
"bitblt" comes from BIT-boundary BLock Transfer.  It is called
a "RasterOp" by Newman and Sproull.
It originated from the \fIFrame Buffer\fP model or \fIRaster Graphics\fP.
The typical raster graphics screen has an array of memory (called a frame
buffer) and hardware that scans through that memory
and maps it onto the tube to create an image.
A raster tube is made up of a two dimensional array of tiny dots of light 
called picture elements.
Pixel (or pel) is short for picture elements.
Different tubes have different amounts of memory
associated with each "pixel" on the screen. 
Color and gray scale screens may have frame buffers
where 8 bits represent a pixel on the screen.
Black and white (monochrome) screens have frame
buffers where each bit represents a pixel on
the screen.  Because of this attribute, these screens are sometimes
referred to as \fIbitmap\fP displays.
Bitblt was designed to work on bitmap displays.
Because one pixel is represented by one bit, pixel
and bit are used interchangeably in this paper.
The bitmap (or frame buffer memory) may be
addressable on bit, byte or WORD (16 bits or
SHORT) boundaries depending on the screen hardware.
Most displays (all that I've worked with) allow access
on byte or short boundaries.
On each screen, the line of pixels (or bits) across the screen (or
across the frame buffer or bitmap) is called a
\fIscanline\fP.
A screen that is 768 bits high by 1024 bits wide has 768 scanlines each
of which is 1024 bits (or 64 shorts) wide.
.PP
Bitblt arose from the need to move an image on the
screen from one spot to another.
Some screens allow the user to address individual bits or address
bytes or shorts in the frame buffer.   Others allow byte or short
access only. The bitblt primative receives arguments
as if the screen has bit addressing
and deals with the screen in what ever addressing
mode it has.
So bitblt works on frame buffer memory that is byte or short addressable.
This has the effect of hiding the screen hardware from the user.
Bitblt is the "output primitive", it is the only function needed to
deal with the screen.  It can be used to draw lines, characters, images,
shapes, and anything else.
.PP
If bitblt works on frame buffer memory that is byte or short addressable
then it should (and does) work on ANY memory that is byte or short
addressable.
So bitblt can act on bitmaps in main memory as well as on the frame buffer.
But why would one want to use bitblt on "off-screen" memory?
There are many reasons and here are a few common ones.
An application may want to store fonts off screen and then "blt" them to
the screen as needed.  An application may want to store menus, icons,
windows, and any other window manager items that would have to be re-created
\fIevery time\fP they were used.
An application may wish to show animation by  storing all sequences then
using bitblt to put them on and off the screen quickly.
Basicly bitmaps are a general representation of an image, and
bitblt is a general primitive for manipulating them.
.PP
Bitblt not only copies the source to the destination but a user can also
specify different bit combination rules like and, or, xor etc..
Bitblt takes the source, combines it with the destination according to the
combination rule and puts it back in the destination.
.PP
Another bitmap operation needed is the ability to replicate a specified source
all over a bit specified area in the destination. (By "bit specified area"
I mean there is a rectangular set of bits in the destination which are to
be changed.  There may also be a set of bits surrounding this area and it
is not to be changed.) This would allow a user to
easily set or blank part or all of a bitmap.
The source could be all white
or all black or some pattern and it would be "tiled" in a bit specified area
of the destination.
("Tiled", as in taking these little squares of tile all with the same pattern
on them and lining them up on your bathroom floor or wall.)
A tile in the bitblt program is a specified size of 16 x 16 bits which is
16 unsigned shorts.  The user specifies a tile combination rule (like
TileCopy or TileOr, etc.) and a tile and (after specifying other parameters)
calls the bitblt function.  Bitblt uses the tile as the source and replicates
it all over the specified area in the destination.  How it replicates the
tile on the destination is very important.  Think of the destination as being
totally covered by the tile so that the first bit in the tile is sitting ON
the first bit in the destination. So you've rolled the tile dough onto the
destination and now you cookie cut this dough with the bit specified area
in the destination and peel away everything on the outside of the cookie
cutter.  This leaves the tile where you want it. In other words the
tile is lined up with the origin of the destination.
.PP
The last necessary bitmap operation is being able to copy a source or tile
to the destination through a bitmap.  For example, say you want the letter
"A" stenciled onto your new lawn mower.
You take a can of black spray paint, the letter "A" in a stencil,
place it on your lawn mower and spray.  The lawn mower now has a
black letter "A" on it.  In this case, the spray paint is a black tile,
the letter
"A" stencil is the masking bitmap and the lawn mower is the destination bitmap.
.sp 1
.NH 2
Introduction Summary
.sp
.IP 1.
Bitblt is designed to work on monochrome
"bitmapped" displays which are byte or short
addressable.
.sp .5
.IP 2.
Bitblt allows the user to specify in BIT addressable
form what bits in a source bitmap are to be copied
to a bit specified area in a destination bitmap.
The user sees a two dimensional array of bits, not
an array of bytes or shorts.
.sp .5
.IP 3.
A bitmap is a general term for an allocated area
of memory that is acted on by bitblt. The bitmap
may be in main memory or it may be the frame buffer.
.sp .5
.IP 4.
A scanline is a line of pixels (or bits) across a bitmap.
.IP 5.
Bitblt is the lowest level graphics primitive on
which all graphics output is based.
.IP 6.
Bitblt works on ALL memory that is byte or short addressable.
.sp
.LP
Advantages of bitblt:
.IP 1.
One general bitmap interface to deal with.
.IP 2.
Doing all raster manipulations in one primitive,
only one set of code to change when improvements are thought of.
.IP 3.
All applications benefit from any improvements.
.IP 4.
Portable.
.sp
.LP
Disadvantages of bitblt:
.IP 1.
For absolute speed, certain functions, like fonts,
may have to be special cased.
.sp 2
.NH 1
Bitblt Interface
.sp 1
.LP
To copy a set of bits from source to destination the bitblt function
needs to have certain information.
.sp .5
.IP 1.
It needs the address of the source bitmap (if the combination rule is a
"source" rule).
.IP 2.
It needs the address of the destination bitmap.
.IP 3.
It needs to know the location of the bits within the source
bitmap which are to be copied.
.IP 4.
It needs to know the location of bits within the destination
bitmap which are to receive the source.
.IP 5.
It needs to know how to combine the source with the
destination.  Ex. COPY, OR, XOR, AND, etc. the
source to the destination,
.sp .5
.LP
Other useful things the bitblt function does:
.sp .5
.IP 6.
Replicate a special type of source all over the
destination - (Tiles or Textures or Patterns.)
.IP 7.
Clip down the source and destination to a clipping area.
.IP 8.
Copy the source to the destination through a mask.  (Like a stencil.)
.LP
The geometry and structures involved must be discussed first before the
actual interface structure is given in detail.
.NH 2
Geometry and Structures
.ls 2
.PP
The bitblt function uses the "infinitely thin" coordinate system.  In this
system there are infinitely thin lines running \fIbetween\fP each pixel
on a bitmap. (See Siggraph'84 course notes or Inside Macintosh as
referenced above.)  The pixels or bits are between the
points on the grid.  A rectangle that is H points wide and
V points tall encloses H x V bits.
Other coordinate systems (like X) say that 
the points on the grid \fIare\fP the pixels.
This is important when discussing rectangles.  For example, say we
have a rectangle whose origin is 1,2 and whose width is 2 \fIpixels\fP wide
and its height is 3 \fIpixels\fP high.
Using the infinitely thin coordinate system the bottom right
corner of this rectangle would be 1+2,2+3 = \fI3,5\fP and would encompass
2 x 3 = 6 bits.
Note that because of the coordinate system there are bits either on the outside
or on the inside of the rectangle.  Using the other coordinate system,
the bottom right corner of the this rectangle would be 1+2-1,2+3-1 = \fI2,4\fP.
Why? Because this coordinate system is \fIinclusive\fP, so 1 through \fIand
including\fP 2 is 2 bits and 2 through \fIand including\fP 4 is 3 bits.
I chose the infinitely thin coordinate system because I thought it was less
confusing but different people like different things.
.PP
Three structures were used to define the basic graphic entities:
rectangles, bitmaps, and tiles, that bitblt must deal with.
The Siggraph'84 Course Notes describe four structures that they used
to implement their slow bitblt function.  One of them, the Point structure,
I found useless.  The others I used but modified a bit.
A rectangle I defined as 4 shorts:
.DS
typedef struct Blt_Rectangle {
	short origin_y;
	short origin_x;
	short corner_y;
	short corner_x;
}
.DE
.LP
Because a rectangle uses shorts, each coordinate has a range of
-32768,-32768 to 32767,32767.
.PP
A bitmap is defined as an unsigned short pointer which points to
the actual data (usually an array of unsigned shorts which \fImust
be short aligned\fP), a rectangle which
is the bounding rectangle for that data, and a short integer
which is the number of shorts wide the bitmap is. (Very similar to Inside
Macintosh structure.)
.DS
typedef struct Blt_Bitmap {
	unsigned short *base;
	Blt_Rectangle rect;
	short nshorts;
} Blt_Bitmap;
.DE
.LP
Base points to an array of unsigned shorts which
is the data that makes up the bitmap.  However nshorts is what
gives "base", the array of unsigned shorts, a sort of 2 dimensional quality
because this arbitrary array is now broken up into x number of segments each
of which has "nshorts" number of shorts in it.
Each of these segments is called a scanline.
Previously I referred to a scanline as a line of pixels across the screen.
(See Introduction.)  Now I would like to generalize and call a scanline
a line of pixels (or bits) across an arbitrary bitmap.
For example, lets say "base" points to an array of 24 unsigned shorts.
If "nshorts" was 3 then there would be 8 scanlines, 3 shorts each.
If "nshorts" was 4 then there would be 6 scanlines, 4 shorts each.
"rect" could be anything as long as (rect.corner_x - rect.origin_x (the width))
<= (nshorts * 16) and (rect.corner_y - rect.origin_y (the height)) <=
(the size of the array(24) / nshorts)
.PP
The third structure is the tile structure also called the 
Texture structure in the Siggraph course notes and referred to as
a Pattern structure in Inside Macintosh.  It is an array of
16 unsigned shorts so it forms a 16 by 16 bit tile.  Note
a Pattern in Inside Macintosh is only 8 by 8 bits but its the
same idea.
.DS
typedef struct Blt_Tile {
	unsigned short tile[TILE_SIZE];
} Blt_Tile;
.DE   
.LP
When a tile is put on a bitmap it is aligned to the bitmap's
origin (top left) corner.  This is done so that the same tile drawn in
different places on the same bitmap will line up.
.NH 2
The Interface Structure
.PP
The bitblt function returns -1 if a bad pointer was found or
something was wrong, 0 if the width or height of the bitblt
turned out to be less than zero and 1 if everything went ok.
It also has a global Blt_Rectangle called change_rect which
contains the final area changed by the bitblt function.  At first this
was only used for debugging purposes but now it is used for the
ACIS Experimental Display (Viking).
Because bit block transfer programs must be fast, many internal routines
have been converted to macros.
.LP
The bitblt routine receives a pointer to a Blt_userdata (BLT in X) structure.
This structure looks like this:
.sp .5
.QP
\fBBlt_Bitmap src_bitmap\fP - Bitmap to be copied from.
.sp .5
.QP
\fBBlt_Rectangle src_rect\fP - Specifies the area in the
src_bitmap to be used, its coordinates are in the
source bitmap's coordinate system.
.sp .5
.QP
\fBBlt_Bitmap dst_bitmap\fP - Bitmap to be changed.
.sp .5
.QP
\fBBlt_Rectangle dst_rect\fP - Specifies the area in the
dst_bitmap to be changed.  Its coordinates are in
the destination bitmap's coordinate system.
.sp .5
.QP
\fBBlt_Rectangle clp_rect\fP - Another rectangle to clip
against if the BLT_CLIPON bit in blt_flags is a 1.
If the BLT_CLIPON bit is 0 then clp_rect is never
accessed. (In other words it does not have to be set to
anything.) Its coordinates are also in the destination
bitmap's coordinate system.
.sp .5
.QP
\fBBlt_Tile *tile_ptr\fP - The tile (or pattern or
texture... this is a 16x16 bit area) to be used if the
combination rule uses a tile.
.sp .5
.QP
\fBBlt_Bitmap msk_bitmap\fP - Masking bitmap, which is
like regions in the Macintosh world.  This is hard to
explain.  A masking bitmap is kind of like a
stencil, for every 1 or on bit in the mask bitmap the bit
operation is allowed.  Where there are 0 or off bits in the
mask bitmap the destination will remain the same.
To use this feature, the BLT_MASKON bit in blt_flags
must be 1.  The setup for this structure requires
some explanation.
.QP
- "base" points to the actual data used for the mask.
.QP
- "nshorts" is the number of shorts wide the bitmap is.
(These two are just like normal bitmaps.)
.QP
- "rect" is NOT just any bounding rectangle, its
coordinates have to be in the destination bitmap's
coordinate system.  Furthermore, this bitmap
is expected to line up with the dst_rect or
clp_rect depending on what you want.  Typically
this is set equal to either dst_rect or clp_rect.
An example of this in use is:
You have a tiny bitmap that contains the image of
the character "A".  It is 1 short wide (16 bits) by
12 scan lines high.  It is in the Blt_Bitmap struct
char_A.
We set comb_rule equal to a tile rule (like
TileCopy), set the dst_bitmap equal to
bitblt_screen (see Examples at end of paper), turn off/on
clipping, set blt_flags or/equal (|=) to BLT_MASKON,
set up the dst_rect with say 10,10,22,22, set the
tile_ptr equal to a tile that is all black and now
we set up msk_bitmap.  msk_bitmap.base = char_A.base,
msk_bitmap.nshorts = char_A.nshorts, and
msk_bitmap.rect = dst_rect or clip_rect depending
on whether or not clipping was on and what you wanted.
Now the character "A" is "stenciled" onto the destination at 10,10,22,22.
(Note the normal thing to do would be to
copy this "A" to the screen every time "SHIFT a"
is hit (using char_A as the source and bitblt_screen
as the destination), but in this example we were
different to make a point.)
.sp .5
.QP
\fBshort comb_rule\fP - Combination rule to be used. If
this rule is a SOURCE combination rule then tile_ptr
is never accessed. (Again, In other words it does not
have to be set to anything.)  If this rule is a
tile rule then src_bitmap and src_rect are never
accessed.
.sp .5
.QP
\fBshort blt_flags\fP - A bit on means do a certain extra
operation.  For example if the first bit is on (the
BLT_CLIPON bit) then do clipping.  If the BLT_MASKON
bit is on then the masking bitmap is used.  Both
of these can be set at the same time. (of course.)
(BLT_MASKON | BLT_CLIPON)
.sp
.LP
The actual C structure looks like this:
.DS
typedef struct {
	Blt_Bitmap      src_bitmap;
	Blt_Rectangle   src_rect;
	Blt_Bitmap      dst_bitmap;
	Blt_Rectangle   dst_rect;
	Blt_Rectangle   clp_rect;
	Blt_Tile        *tile_ptr;
	Blt_Bitmap      msk_bitmap;
	short           comb_rule;
	short           blt_flags;
} Blt_userdata;
typedef Blt_userdata BLT;
.DE
.LP
Flags blt_flags could be:
.DS
 #define BLT_CLIPON      0x1
 #define BLT_MASKON      0x2
.DE
.NH
Examples
.sp
.LP
Here is an example of setting up a Blt_Bitmap structure where the hardware
screen address is 0xF4D80000 and the visible screen is 1024 bits wide and
768 bits high:
.sp .5
.DS
bitblt_screen.base = (unsigned short *)0xF4D80000;
bitblt_screen.rect.origin_x = 0;
bitblt_screen.rect.origin_y = 0;
bitblt_screen.rect.corner_x = 1024;
bitblt_screen.rect.corner_y = 768;
bitblt_screen.nshorts = (1024 + 15)/16;
.DE
.LP
Note the + 15 is not needed in this case, but the width may not always be
on a short boundary and + 15 rounds it up.
Also the rectangle could have a different origin and does not have to take
up the whole screen (although that would be silly) It may be like this:
.DS
bitblt_screen.rect.origin_x = 300;
bitblt_screen.rect.origin_y = 300;
bitblt_screen.rect.corner_x = 1324;
bitblt_screen.rect.corner_y = 1068;
.DE
.LP
or use 1/4 of the screen:
.DS
bitblt_screen.rect.origin_x = 0;
bitblt_screen.rect.origin_y = 0;
bitblt_screen.rect.corner_x = 256;
bitblt_screen.rect.corner_y = 192;
.DE
.LP
Note bitblt_screen.nshorts \fImust\fP still be (1024 + 15)/16 even though the
rectangle is smaller.
