PDInterpBitmapImpl.mesa
Copyright (C) 1984, Xerox Corporation. All rights reserved.
Michael Plass, November 2, 1984 9:13:09 am PST
DIRECTORY BitBlt, Environment, Inline, PDInterpBitmap;
PDInterpBitmapImpl:
PROGRAM
IMPORTS BitBlt, Inline
EXPORTS PDInterpBitmap
= BEGIN
BitmapDesc: TYPE = PDInterpBitmap.BitmapDesc;
Tile: TYPE = PDInterpBitmap.Tile;
Rectangle: TYPE = PDInterpBitmap.Rectangle;
Function: TYPE = PDInterpBitmap.Function;
bitsPerWord: NAT = Environment.bitsPerWord;
lgBitsPerWord: NAT = Environment.logBitsPerWord;
wordsPerPage: NAT = Environment.wordsPerPage;
lgBitsPerPixel: NAT = 0;
pixelsPerWord: NAT = bitsPerWord;
Some inlines for basic bit-hacking operations.
BITAND:
PROC [a, b:
CARDINAL]
RETURNS[
CARDINAL]
= INLINE {RETURN[Inline.BITAND[a, b]]};
Shift:
PROC [a:
CARDINAL, b:
INTEGER]
RETURNS [
CARDINAL]
= INLINE {RETURN[Inline.BITSHIFT[a, b]]};
BITBLT:
PROC [ptr: BitBlt.BBptr] = {
In a separate procedure so the spy can figure out how much time goes here.
Could make this an inline for production.
BitBlt.BITBLT[ptr];
};
Intersect:
PUBLIC
PROC [a, b: Rectangle]
RETURNS [Rectangle] = {
sMin: INTEGER ← MAX[a.sMin, b.sMin];
fMin: INTEGER ← MAX[a.fMin, b.fMin];
sMax: INTEGER ← MIN[INT[a.sMin]+a.sSize, INT[b.sMin]+b.sSize];
fMax: INTEGER ← MIN[INT[a.fMin]+a.fSize, INT[b.fMin]+b.fSize];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [[0, 0, 0, 0]]
ELSE RETURN [[sMin, fMin, sMax-sMin, fMax-fMin]]
};
LongZero:
PROC [address:
LONG
POINTER
TO
CARDINAL, count:
CARDINAL] = {
IF count > 0
THEN {
address^ ← 0;
Inline.LongCOPY[from: address, nwords: count-1, to: address+1];
};
};
Clear:
PUBLIC
PROC [bitmapDesc: BitmapDesc] = {
pointer: LONG POINTER ← bitmapDesc.pointer;
words: LONG CARDINAL ← Inline.LongMult[bitmapDesc.rast, bitmapDesc.lines];
WHILE words > 32768
DO
LongZero[pointer, 32768];
pointer ← pointer + 32768;
words ← words - 32768;
ENDLOOP;
LongZero[pointer, words];
};
InsufficientSpace: PUBLIC ERROR = CODE;
Reshape:
PUBLIC
PROC [pointer:
LONG
POINTER, words:
INT, bounds: Rectangle]
RETURNS [bitmapDesc: BitmapDesc] = {
bitsPerPixel: CARDINAL = Shift[1, lgBitsPerPixel];
bitsPerLine:
NAT = Inline.LongMult[bounds.fSize, bitsPerPixel];
Will raise a bounds fault if too many bits per line.
wordsPerLine: CARDINAL = (bitsPerLine+(bitsPerWord-1)) / bitsPerWord;
wordsNeeded: INT = Inline.LongMult[wordsPerLine, bounds.sSize];
IF wordsNeeded > words THEN ERROR InsufficientSpace;
RETURN [[bounds.sMin, bounds.fMin, 0, 0, bounds.sSize, bounds.fSize, pointer, wordsPerLine, bounds.sSize]];
};
ShiftMap:
PUBLIC
PROC [p: BitmapDesc, s, f:
INTEGER]
RETURNS [BitmapDesc] = {
p.sOrigin ← p.sOrigin + s;
p.fOrigin ← p.fOrigin + f;
RETURN [p]
};
ShiftWindow:
PUBLIC
PROC [p: BitmapDesc, s, f:
INTEGER]
RETURNS [BitmapDesc] = {
p.sMin ← p.sMin + s;
p.fMin ← p.fMin + f;
RETURN [p]
};
Clip:
PUBLIC
PROC [p: BitmapDesc, bounds: Rectangle]
RETURNS [BitmapDesc] = {
bounds ← Intersect[Window[p], bounds];
p.sMin ← bounds.sMin-p.sOrigin;
p.fMin ← bounds.fMin-p.fOrigin;
p.sSize ← bounds.sSize;
p.fSize ← bounds.fSize;
RETURN [p]
};
SetWindow:
PUBLIC
PROC [p: BitmapDesc, bounds: Rectangle]
RETURNS [BitmapDesc] = {
RETURN [p]
};
Window:
PUBLIC
PROC [p: BitmapDesc]
RETURNS [Rectangle] = {
RETURN [[p.sOrigin + p.sMin, p.fOrigin + p.fMin, p.sSize, p.fSize]]
};
BufferBounds:
PUBLIC
PROC [p: BitmapDesc]
RETURNS [Rectangle] = {
RETURN [[p.sOrigin, p.fOrigin, p.lines, Shift[p.rast, lgBitsPerWord-lgBitsPerPixel]]]
};
BoundedWindow:
PUBLIC
PROC [p: BitmapDesc]
RETURNS [Rectangle] = {
sMin: INTEGER ← MAX[p.sOrigin + p.sMin, p.sOrigin];
fMin: INTEGER ← MAX[p.fOrigin + p.fMin, p.fOrigin];
sMax: INTEGER ← MIN[p.sOrigin + p.sMin + p.sSize, p.sOrigin + p.lines];
fMax: INTEGER ← MIN[p.fOrigin + p.fMin + p.fSize, p.fOrigin + Shift[p.rast, lgBitsPerWord-lgBitsPerPixel]];
RETURN [[sMin, fMin, MAX[sMax-sMin, 0], MAX[fMax-fMin, 0]]]
};
replicator: ARRAY [0..4] OF CARDINAL = [0FFFFH, 05555H, 01111H, 00101H, 00001H];
Fill:
PUBLIC
PROC [dest: BitmapDesc, area: Rectangle, value:
CARDINAL, function: Function] = {
lgPixelsPerWord: INTEGER = lgBitsPerWord-lgBitsPerPixel;
The following bounding box is calculated in terms of the destination buffer.
sMin: INTEGER = MAX[dest.sMin, 0, area.sMin-dest.sOrigin];
sMax: INTEGER = MIN[dest.sMin+dest.sSize, dest.lines, area.sMin+area.sSize-dest.sOrigin];
fMin: INTEGER = MAX[dest.fMin, 0, area.fMin-dest.fOrigin];
fMax: INTEGER = MIN[dest.fMin+dest.fSize, Shift[dest.rast, lgBitsPerWord-lgBitsPerPixel], area.fMin+area.fSize-dest.fOrigin];
replicatedPixel: CARDINAL ← Inline.BITAND[value, Shift[1, Shift[1, lgBitsPerPixel]]-1] * replicator[lgBitsPerPixel];
bbTableSpace: BitBlt.BBTableSpace;
bb: BitBlt.BBptr ← BitBlt.AlignedBBTable[@bbTableSpace];
IF sMin<sMax
AND fMin<fMax
THEN {
bb^ ← [
dst: [word: dest.pointer + Inline.LongMult[sMin, dest.rast] + Shift[fMin, -lgPixelsPerWord], bit: Inline.BITAND[fMin, Shift[1, lgPixelsPerWord]-1]],
dstBpl: dest.rast*bitsPerWord,
src: [word: @replicatedPixel, bit: 0],
srcDesc: [gray[[yOffset: 0, widthMinusOne: 0, heightMinusOne: 0]]],
height: sMax-sMin,
width: Shift[fMax-fMin, lgBitsPerPixel],
flags: [direction: forward, disjoint: TRUE, disjointItems: TRUE, gray: TRUE, srcFunc: function.srcFunc, dstFunc: function.dstFunc]
];
BITBLT[bb];
};
};
Transfer:
PUBLIC
PROC [dest, source: BitmapDesc, function: Function] = {
lgPixelsPerWord: INTEGER = lgBitsPerWord-lgBitsPerPixel;
sMin: INTEGER = MAX[dest.sOrigin+MAX[dest.sMin, 0], source.sOrigin+MAX[source.sMin, 0]];
sMax: INTEGER = MIN[dest.sOrigin+MIN[dest.sMin+dest.sSize, dest.lines], source.sOrigin+MIN[source.sMin+source.sSize, source.lines]];
fMin: INTEGER = MAX[dest.fOrigin+MAX[dest.fMin, 0], source.fOrigin+MAX[source.fMin, 0]];
fMax: INTEGER = MIN[dest.fOrigin+MIN[dest.fMin+dest.fSize, Shift[dest.rast, lgBitsPerWord-lgBitsPerPixel]], source.fOrigin+MIN[source.fMin+source.fSize, Shift[source.rast, lgBitsPerWord-lgBitsPerPixel]]];
bbTableSpace: BitBlt.BBTableSpace;
bb: BitBlt.BBptr = BitBlt.AlignedBBTable[@bbTableSpace];
fMinDest: NAT = fMin - dest.fOrigin;
fMinSource: NAT = fMin - source.fOrigin;
sStartDest: NAT ← sMin-dest.sOrigin;
sStartSource: NAT ← sMin-source.sOrigin;
IF sMin<sMax
AND fMin<fMax
THEN {
bb^ ← [
dstBpl: dest.rast*bitsPerWord,
srcDesc: [srcBpl[source.rast*bitsPerWord]],
height: sMax-sMin,
width: Shift[fMax-fMin, lgBitsPerPixel],
flags: [direction: forward, disjoint: TRUE, disjointItems: TRUE, gray: FALSE, srcFunc: function.srcFunc, dstFunc: function.dstFunc]
];
IF source.pointer = dest.pointer
THEN {
sSize: NAT = sMax-sMin;
fSize: NAT = fMax-fMin;
IF (fMinSource+fSize)>fMinDest
AND (fMinDest+fSize)>fMinSource
AND (sStartSource+sSize)>sStartDest
AND (sStartDest+sSize)>sStartSource
THEN {
bb.flags.disjoint ← FALSE; -- the rectangles overlap
IF sStartDest=sStartSource THEN bb.flags.disjointItems ← FALSE; -- so do the items
IF sStartDest>sStartSource
OR (sStartDest=sStartSource
AND fMinDest>fMinSource)
THEN {
-- reverse direction
bb.flags.direction ← backward; bb.srcDesc.srcBpl ← bb.dstBpl ← -bb.dstBpl;
sStartSource ← sStartSource + (sSize-1); sStartDest ← sStartDest + (sSize-1);
};
};
};
bb.dst ← [word: dest.pointer + Inline.LongMult[sStartDest, dest.rast] + Shift[fMinDest, -lgPixelsPerWord], bit: Inline.BITAND[fMinDest, Shift[1, lgPixelsPerWord]-1]];
bb.src ← [word: source.pointer + Inline.LongMult[sStartSource, source.rast] + Shift[fMinSource, -lgPixelsPerWord], bit: Inline.BITAND[fMinSource, Shift[1, lgPixelsPerWord]-1]];
BITBLT[bb];
};
};
IsPowerOfTwo:
PROC [c:
CARDINAL]
RETURNS [
BOOLEAN] =
INLINE {
RETURN [BITAND[c, c-1] = 0]
};
largeBitSize: INT ← 5000;
fSizeHint: NAT ← 100;
CreateTile:
PUBLIC
PROC [rectangle: Rectangle, phase:
INTEGER ← 0, rasterPointer:
LONG
POINTER, scratchPointer:
LONG
POINTER ←
NIL, scratchWords:
INT ← 0]
RETURNS [tile: Tile] = {
ENABLE InsufficientSpace => GO TO InsufficientScratch;
bitWidth: CARDINAL = Shift[rectangle.fSize, lgBitsPerPixel];
bitmapDesc: BitmapDesc = [rectangle.sMin, rectangle.fMin, 0, 0, rectangle.sSize, rectangle.fSize, rasterPointer, (rectangle.fSize+(pixelsPerWord-1))/pixelsPerWord, rectangle.sSize];
IF bitWidth <= 16
AND IsPowerOfTwo[bitWidth]
AND bitmapDesc.sSize < 16
AND phase = 0
THEN {
small: BitmapDesc ← Reshape[scratchPointer, scratchWords, [rectangle.sMin, rectangle.fMin, rectangle.sSize, Shift[16, -lgBitsPerPixel]]];
FOR fShift:
NAT ← 0, fShift+bitmapDesc.fSize
UNTIL fShift>=small.fSize
DO
Transfer[small, ShiftMap[bitmapDesc, 0, fShift], [null, null]];
ENDLOOP;
tile ← [small.sOrigin, small.fOrigin, small.sSize, small.fSize, 0, small.pointer, small.rast, small.lines];
}
ELSE {
fSize: NAT ← (fSizeHint+bitmapDesc.fSize-1)/bitmapDesc.fSize*bitmapDesc.fSize;
bitsPerLine: NAT ← Shift[fSize, lgBitsPerPixel];
sSize: NAT ← MAX[(((largeBitSize+bitsPerLine-1)/bitsPerLine)/bitmapDesc.sSize)*bitmapDesc.sSize, bitmapDesc.sSize];
large: BitmapDesc ← Reshape[scratchPointer, scratchWords, [bitmapDesc.sOrigin+bitmapDesc.sMin, bitmapDesc.fOrigin+bitmapDesc.fMin, sSize, fSize]];
finalPhase: CARDINAL;
WHILE phase<0 DO phase ← phase + bitmapDesc.fSize ENDLOOP;
phase ← phase MOD bitmapDesc.fSize;
finalPhase ← (phase * (sSize/bitmapDesc.sSize)) MOD bitmapDesc.fSize;
large.sSize ← bitmapDesc.sSize;
large.fSize ← bitmapDesc.fSize;
Transfer[large, bitmapDesc, [null, null]];
WHILE large.fSize<fSize
DO
fSizePrev: NAT = large.fSize;
large.fSize ← MIN[fSize, 2*fSizePrev];
Transfer[large, ShiftMap[large, 0, fSizePrev], [null, null]];
ENDLOOP;
WHILE large.sSize<sSize
DO
sSizePrev: NAT = large.sSize;
large.sSize ← MIN[sSize, 2*sSizePrev];
Transfer[large, ShiftMap[large, sSizePrev, phase], [null, null]];
{firstPart: BitmapDesc ← ShiftMap[large, sSizePrev, phase-bitmapDesc.fSize];
firstPart.fSize ← bitmapDesc.fSize;
Transfer[large, firstPart, [null, null]];
};
phase ← 2*phase;
WHILE phase > bitmapDesc.fSize DO phase ← phase - bitmapDesc.fSize ENDLOOP;
ENDLOOP;
tile ← [large.sOrigin, large.fOrigin, sSize, fSize, finalPhase, large.pointer, large.rast, large.lines];
};
EXITS InsufficientScratch => {
tile ← [rectangle.sMin, rectangle.fMin, rectangle.sSize, rectangle.fSize, phase, rasterPointer, (rectangle.fSize+(pixelsPerWord-1))/pixelsPerWord, rectangle.sSize];
};
};
TransferTile:
PUBLIC
PROC [dest: BitmapDesc, tile: Tile, function: Function ← [null, null]] = {
bitWidth: CARDINAL = Shift[tile.fSize, lgBitsPerPixel];
IF bitWidth = bitsPerWord
AND tile.rast = 1
AND tile.sSize <= 16
AND tile.phase = 0
THEN {
startLine: NAT ← MAX[dest.sMin, 0];
endLine: INTEGER ← MIN[dest.sMin+dest.sSize, dest.lines];
startPixel: NAT ← MAX[dest.fMin, 0];
endPixel: INTEGER ← MIN[dest.fMin+dest.fSize, Shift[dest.rast, lgBitsPerWord-lgBitsPerPixel]];
IF endLine>startLine
AND endPixel>startPixel
THEN {
startBit: NAT ← Shift[startPixel, lgBitsPerPixel];
bbTableSpace: BitBlt.BBTableSpace;
bb: BitBlt.BBptr = BitBlt.AlignedBBTable[@bbTableSpace];
sOffset: INTEGER ← (dest.sOrigin+dest.sMin-tile.sOrigin) MOD tile.sSize;
fOffset: INTEGER ← (dest.fOrigin+dest.fMin-tile.fOrigin) MOD tile.fSize;
WHILE sOffset < 0 DO sOffset ← sOffset + tile.sSize ENDLOOP;
WHILE fOffset < 0 DO fOffset ← fOffset + tile.fSize ENDLOOP;
bb^ ← [
dst: [word: dest.pointer + Inline.LongMult[startLine, dest.rast] + startBit/bitsPerWord, bit: startBit MOD bitsPerWord],
dstBpl: dest.rast*bitsPerWord,
src: [word: tile.pointer+sOffset, bit: Shift[fOffset, lgBitsPerPixel]],
srcDesc: [gray[[yOffset: sOffset, widthMinusOne: 0, heightMinusOne: tile.sSize-1]]],
height: endLine-startLine,
width: Shift[endPixel-startPixel, lgBitsPerPixel],
flags: [direction: forward, disjoint: TRUE, disjointItems: TRUE, gray: TRUE, srcFunc: function.srcFunc, dstFunc: function.dstFunc]
];
BITBLT[bb];
};
}
ELSE {
sMin: INT ← dest.sOrigin+dest.sMin;
fMin: INT ← dest.fOrigin+dest.fMin;
source: BitmapDesc;
sOrigin: INT ← tile.sOrigin;
fOrigin: INT ← tile.fOrigin;
WHILE sOrigin < sMin
DO
sOrigin ← sOrigin + tile.sSize;
fOrigin ← fOrigin + tile.phase;
ENDLOOP;
WHILE sOrigin > sMin
DO
sOrigin ← sOrigin - tile.sSize;
fOrigin ← fOrigin - tile.phase;
ENDLOOP;
WHILE fOrigin < fMin DO fOrigin ← fOrigin + tile.fSize ENDLOOP;
WHILE fOrigin > fMin DO fOrigin ← fOrigin - tile.fSize ENDLOOP;
source ← [sOrigin, fOrigin, 0, 0, tile.sSize, tile.fSize, tile.pointer, tile.rast, tile.lines];
WHILE source.sOrigin < sMin+dest.sSize
DO
source.fOrigin ← fOrigin;
WHILE source.fOrigin < fMin+dest.fSize
DO
Transfer[dest, source, function];
source.fOrigin ← source.fOrigin + source.fSize;
ENDLOOP;
source.sOrigin ← source.sOrigin + source.sSize;
fOrigin ← fOrigin + tile.phase;
WHILE fOrigin > fMin DO fOrigin ← fOrigin - source.fSize ENDLOOP;
ENDLOOP;
};
};
END.