IIPixelImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Michael Plass, October 2, 1986 5:30:00 pm PDT
Doug Wyatt, March 6, 1986 4:09:53 pm PST
DIRECTORY
Basics USING [bitsPerWord, CARD, HighHalf, LongMult, LongNumber, RawWords],
IIPixel USING [PixelBuffer, PixelBufferRep, PixelMap, PixelMapRep, PixelProc, ResampleAction],
IISample USING [BitsPerSample, Function, Get, GetSamples, CopySamples, maxCount, NewSampleMap, NewSamples, GetBox, MultipleReleaseOfScratch, nullFunction, PutSamples, Sample, SampleBuffer, SampleBufferRep, SampleMap, zeroVec],
IITransformation USING [InverseTransform, InverseTransformVec, Transformation],
Real USING [Fix, FScale, RealException, Round],
SF USING [Box, BoxAction, BoxGenerator, SizeF, Vec];
IIPixelImpl: CEDAR MONITOR
IMPORTS Basics, IISample, IITransformation, Real, SF
EXPORTS IIPixel
SHARES IISample
bitsPerWord: NAT ~ Basics.bitsPerWord;
RawSamples: TYPE ~ Basics.RawWords;
Transformation: TYPE ~ IITransformation.Transformation;
InlinePointerToSamples: PROC [samples: IISample.SampleBuffer, start: NAT, count: NAT]
RETURNS [
LONG
POINTER
TO RawSamples] ~
TRUSTED
INLINE {
check: NAT ~ NAT[samples.maxLength-start]-count;
RETURN[LOOPHOLE[samples, LONG POINTER]+SIZE[IISample.SampleBufferRep[start]]];
};
NewPixels:
PUBLIC
PROC [samplesPerPixel:
NAT, length:
NAT, scratch: PixelBuffer ←
NIL]
RETURNS [PixelBuffer] ~ {
new: PixelBuffer ← scratch;
IF new=NIL OR new.samplesPerPixel#samplesPerPixel THEN
new ← NEW[PixelBufferRep[samplesPerPixel]];
FOR i:
NAT
IN[0..samplesPerPixel)
DO
new[i] ← IISample.NewSamples[length: length];
ENDLOOP;
new.length ← length;
RETURN[new];
};
nScratchPixelBuffers: NAT ~ 6;
scratchPixelBuffers:
ARRAY [0..nScratchPixelBuffers)
OF PixelBuffer ←
ALL[
NIL];
ObtainScratchPixels:
PUBLIC
ENTRY
PROC [samplesPerPixel:
NAT, length:
NAT]
RETURNS [PixelBuffer] ~ {
FOR i:
NAT
IN [0..nScratchPixelBuffers)
DO
buf: PixelBuffer ~ scratchPixelBuffers[i];
IF buf #
NIL
AND buf.samplesPerPixel = samplesPerPixel
AND buf.length >= length
THEN {
scratchPixelBuffers[i] ← NIL;
buf.length ← length;
FOR j:
NAT
IN [0..samplesPerPixel)
DO
buf[j].length ← length;
ENDLOOP;
RETURN [buf];
};
ENDLOOP;
RETURN[NewPixels[samplesPerPixel: samplesPerPixel, length: length]]
};
ReleaseScratchPixels:
PUBLIC
ENTRY
PROC [pixels: PixelBuffer] ~ {
slot: NAT ← 0;
IF pixels.samplesPerPixel = 0 THEN RETURN; -- Joker
FOR j:
NAT
IN [1..pixels.samplesPerPixel)
DO
IF pixels[j].maxLength # pixels[0].maxLength THEN RETURN
ENDLOOP;
FOR i:
NAT
IN [0..nScratchPixelBuffers)
DO
t: PixelBuffer ← scratchPixelBuffers[i];
IF t = NIL THEN slot ← i
ELSE IF pixels = t THEN RETURN WITH ERROR IISample.MultipleReleaseOfScratch;
ENDLOOP;
pixels.length ← pixels[0].maxLength;
scratchPixelBuffers[slot] ← pixels;
};
DoWithScratchPixels:
PUBLIC
PROC [samplesPerPixel:
NAT, length:
NAT,
action: PROC [PixelBuffer]] ~ {
scratch: PixelBuffer ~ ObtainScratchPixels[samplesPerPixel: samplesPerPixel, length: length];
action[scratch ! UNWIND => ReleaseScratchPixels[scratch]];
ReleaseScratchPixels[scratch];
};
NewPixelMap:
PUBLIC
PROC [samplesPerPixel:
NAT, box:
SF.Box, maxSample: PixelProc]
RETURNS [PixelMap] ~ {
new: PixelMap ← NEW[PixelMapRep[samplesPerPixel]];
FOR i:
NAT
IN[0..samplesPerPixel)
DO
bitsPerSample: IISample.BitsPerSample ~
SELECT maxSample[i]
FROM
<2 => 1, <4 => 2, <16 => 4, <256 => 8, ENDCASE => IISample.BitsPerSample.LAST;
new[i] ← IISample.NewSampleMap[box: box, bitsPerSample: bitsPerSample];
ENDLOOP;
new.box ← box;
RETURN[new];
};
MakePixelMap:
PUBLIC
PROC [s0, s1, s2, s3, s4: IISample.SampleMap ←
NIL]
RETURNS [PixelMap] ~ {
s: ARRAY [0..5) OF IISample.SampleMap ~ [s0, s1, s2, s3, s4];
Count:
PROC
RETURNS [i:
NAT ← 0]
~ INLINE {WHILE i < 5 AND s[i] # NIL DO i ← i + 1 ENDLOOP};
n: NAT ~ Count[];
new: PixelMap ~ NEW[PixelMapRep[n]];
new.box ← IF n = 0 THEN [IISample.zeroVec, IISample.zeroVec] ELSE IISample.GetBox[s[0]];
FOR i:
NAT
IN [0..n)
DO
assert: BOOL[TRUE..TRUE] ~ IISample.GetBox[s[i]] = new.box;
new[i] ← s[i];
ENDLOOP;
FOR i:
NAT
IN [n..5)
DO
assert: BOOL[TRUE..TRUE] ~ s[i] = NIL;
ENDLOOP;
RETURN [new]
};
GetPixels:
PUBLIC
PROC [self: PixelMap, initIndex:
SF.Vec ← IISample.zeroVec, delta:
SF.Vec ← [s: 0, f: 1],
pixels: PixelBuffer, start: NAT ← 0, count: NAT ← IISample.maxCount] ~ {
FOR i:
NAT
IN [0..self.samplesPerPixel)
DO
IISample.GetSamples[self[i], initIndex, delta, pixels[i], start, count];
ENDLOOP;
};
PutPixels:
PUBLIC
PROC [self: PixelMap, initIndex:
SF.Vec ← IISample.zeroVec, delta:
SF.Vec ← [s: 0, f: 1],
pixels: PixelBuffer, start: NAT ← 0, count: NAT ← IISample.maxCount,
function: IISample.Function ← IISample.nullFunction] ~ {
FOR i:
NAT
IN [0..self.samplesPerPixel)
DO
IISample.PutSamples[self[i], initIndex, delta, pixels[i], start, count, function];
ENDLOOP;
};
realLastInt:
REAL ←
REAL[
LAST[
INT]];
Floor:
PROC[a:
REAL]
RETURNS[c:
REAL] ~ {
IF ABS[a] >= realLastInt THEN RETURN [a];
c ← REAL[Real.Fix[a]];
IF c>a THEN RETURN[c-1] ELSE RETURN[c]
};
ScaledFromRealMod:
PROC [d:
REAL, m:
CARDINAL]
RETURNS [
INT] ~ {
s: Basics.LongNumber ← [li[0]];
IF m # 0
THEN {
modulus: REAL ~ m;
residue: REAL ← IF d IN [0..modulus) THEN d ELSE (d-modulus*Floor[d/modulus]);
s.li ← Real.Round[Real.FScale[residue, Basics.bitsPerWord]];
Now some paranoia about floating-point fuzz
IF s.li < 0 THEN {s.hi ← s.hi + m};
IF s.hi >= m THEN {s.hi ← s.hi - m};
IF s.hi >= m THEN ERROR;
};
RETURN [s.li];
};
Sample1: TYPE ~ IISample.Sample[0..1B];
Sample8: TYPE ~ IISample.Sample[0..377B];
RawSamples1: TYPE ~ RECORD [PACKED SEQUENCE COMPUTED CARDINAL OF Sample1];
RawSamples8: TYPE ~ RECORD [PACKED SEQUENCE COMPUTED CARDINAL OF Sample8];
Pointer1: TYPE ~ LONG POINTER TO RawSamples1;
Pointer8:
TYPE ~
LONG
POINTER
TO RawSamples8;
Resample1:
PROC [dest, source: PixelMap, m: Transformation, interpolate:
BOOL] ~ {
boxes: SF.BoxGenerator ~ {boxAction[dest.box]};
action: ResampleAction ~ {
FOR j:
NAT
IN [0..pixels.samplesPerPixel)
DO
IISample.PutSamples[map: dest[j], buffer: pixels[j], initIndex: min];
ENDLOOP;
};
Resample[self: source, m: m, interpolate: interpolate, boxes: boxes, bounds: dest.box, action: action];
};
Resample:
PUBLIC
PROC [self: PixelMap, m: Transformation, interpolate:
BOOL,
boxes: SF.BoxGenerator, bounds: SF.Box, action: ResampleAction] ~ {
samplesPerPixel: NAT ~ self.samplesPerPixel;
sSize: NAT ~ self.box.max.s-self.box.min.s; -- source size in slow (scan line) direction
fSize: NAT ~ self.box.max.f-self.box.min.f; -- source size in fast (pixel) direction
ssDelta: Basics.LongNumber; -- source delta s for destination s increment
fsDelta: Basics.LongNumber; -- source delta f for destination s increment
sfDelta: Basics.LongNumber; -- source delta s for destination f increment
ffDelta: Basics.LongNumber; -- source delta f for destination f increment
d0: SF.Vec ← bounds.min; -- initial destination position
s0: Basics.LongNumber; -- initial source s (corresponding to d0)
f0: Basics.LongNumber; -- initial source f (corresponding to d0)
pixels: PixelBuffer ~ ObtainScratchPixels[samplesPerPixel, SF.SizeF[bounds]];
rs, rf: REAL ← 0.0;
boxActionPointSamples:
SF.BoxAction ~ {
count: NAT ~ SF.SizeF[box];
smax: Basics.LongNumber ~ [pair[hi: sSize, lo: 0]];
fmax: Basics.LongNumber ~ [pair[hi: fSize, lo: 0]];
ssup: Basics.LongNumber ~ ssDelta;
fsup: Basics.LongNumber ~ fsDelta;
ssdn: Basics.LongNumber ~ [lc[smax.lc-ssup.lc]];
fsdn: Basics.LongNumber ~ [lc[fmax.lc-fsup.lc]];
sfup: Basics.LongNumber ~ sfDelta;
ffup: Basics.LongNumber ~ ffDelta;
sfdn: Basics.LongNumber ~ [lc[smax.lc-sfup.lc]];
ffdn: Basics.LongNumber ~ [lc[fmax.lc-ffup.lc]];
d1: SF.Vec ← d0; -- destination position at start of scan line
s1: Basics.LongNumber ← s0; -- source s corresponding to d1
f1: Basics.LongNumber ← f0; -- source f corresponding to d1
WHILE d1.s<box.min.s
DO
d1.s ← d1.s+1;
IF s1.lc<ssdn.lc THEN s1.lc ← s1.lc+ssup.lc ELSE s1.lc ← s1.lc-ssdn.lc;
IF f1.lc<fsdn.lc THEN f1.lc ← f1.lc+fsup.lc ELSE f1.lc ← f1.lc-fsdn.lc;
ENDLOOP;
IF d1.s=box.min.s THEN { d0 ← d1; s0.lc ← s1.lc; f0.lc ← f1.lc } ELSE ERROR;
WHILE d1.f<box.min.f
DO
d1.f ← d1.f+1;
IF s1.lc<sfdn.lc THEN s1.lc ← s1.lc+sfup.lc ELSE s1.lc ← s1.lc-sfdn.lc;
IF f1.lc<ffdn.lc THEN f1.lc ← f1.lc+ffup.lc ELSE f1.lc ← f1.lc-ffdn.lc;
ENDLOOP;
IF d1.f=box.min.f THEN NULL ELSE ERROR;
pixels.length ← count;
--For each scan line of box--
DO
FOR i:
NAT
IN[0..samplesPerPixel)
DO
map: IISample.SampleMap ~ self[i];
samples: IISample.SampleBuffer ~ pixels[i];
s: Basics.LongNumber ← s1;
f: Basics.LongNumber ← f1;
IF sfDelta.li = 0
AND ffDelta = [pair[hi: 1, lo: 0]]
THEN {
count1: NAT ~ MIN[count, fSize-f.hi];
count2: NAT ~ MIN[count-count1, f.hi];
count3: NAT ~ count-count1-count2;
IISample.GetSamples[map: map, initIndex: [s: s.hi+self.box.min.s, f: f.hi+self.box.min.f], buffer: samples, start: 0, count: count1];
IF count2 # 0 THEN IISample.GetSamples[map: map, initIndex: [s: s.hi+self.box.min.s, f: self.box.min.f], buffer: samples, start: count1, count: count2];
IF count3 # 0 THEN IISample.CopySamples[dst: samples, src: samples, dstStart: count1+count2, srcStart: 0, count: count3];
}
ELSE
IF map.base.bit=0
AND (map.bitsPerLine
MOD bitsPerWord)=0
AND map.bitsPerSample=8
THEN {
base: Pointer8 ~ LOOPHOLE[map.base.word];
wordsPerLine: NAT ~ map.bitsPerLine/bitsPerWord;
result: LONG POINTER TO RawSamples ~ InlinePointerToSamples[samples, 0, count];
IF sfup.lc=0
THEN {
line: Pointer8 ~ base+Basics.LongMult[s.hi, wordsPerLine];
FOR k:
NAT
IN[0..count)
DO
TRUSTED { result[k] ← line[f.hi] };
IF f.lc<ffdn.lc THEN f.lc ← f.lc+ffup.lc ELSE f.lc ← f.lc-ffdn.lc;
ENDLOOP;
}
ELSE {
FOR k:
NAT
IN[0..count)
DO
line: Pointer8 ~ base+Basics.LongMult[s.hi, wordsPerLine];
TRUSTED { result[k] ← line[f.hi] };
IF s.lc<sfdn.lc THEN s.lc ← s.lc+sfup.lc ELSE s.lc ← s.lc-sfdn.lc;
IF f.lc<ffdn.lc THEN f.lc ← f.lc+ffup.lc ELSE f.lc ← f.lc-ffdn.lc;
ENDLOOP;
};
}
ELSE {
-- the slow but general way
FOR k:
NAT
IN[0..count)
DO
samples[k] ← IISample.Get[map, [s: s.hi+self.box.min.s, f: f.hi+self.box.min.f]];
IF s.lc<sfdn.lc THEN s.lc ← s.lc+sfup.lc ELSE s.lc ← s.lc-sfdn.lc;
IF f.lc<ffdn.lc THEN f.lc ← f.lc+ffup.lc ELSE f.lc ← f.lc-ffdn.lc;
ENDLOOP;
};
ENDLOOP;
action[pixels, d1];
d1.s ← d1.s+1; IF NOT d1.s<box.max.s THEN EXIT;
IF s1.lc<ssdn.lc THEN s1.lc ← s1.lc+ssup.lc ELSE s1.lc ← s1.lc-ssdn.lc;
IF f1.lc<fsdn.lc THEN f1.lc ← f1.lc+fsup.lc ELSE f1.lc ← f1.lc-fsdn.lc;
ENDLOOP;
};
boxActionInterpolatedSamples:
SF.BoxAction ~ {
count: NAT ~ SF.SizeF[box];
smax: Basics.LongNumber ~ [pair[hi: sSize, lo: 0]];
fmax: Basics.LongNumber ~ [pair[hi: fSize, lo: 0]];
ssup: Basics.LongNumber ~ ssDelta;
fsup: Basics.LongNumber ~ fsDelta;
ssdn: Basics.LongNumber ~ [lc[smax.lc-ssup.lc]];
fsdn: Basics.LongNumber ~ [lc[fmax.lc-fsup.lc]];
sfup: Basics.LongNumber ~ sfDelta;
ffup: Basics.LongNumber ~ ffDelta;
sfdn: Basics.LongNumber ~ [lc[smax.lc-sfup.lc]];
ffdn: Basics.LongNumber ~ [lc[fmax.lc-ffup.lc]];
isup: CARDINAL ~ 1;
ifup: CARDINAL ~ 1;
isdn: CARDINAL ~ smax.hi-isup;
ifdn: CARDINAL ~ fmax.hi-ifup;
d1: SF.Vec ← d0; -- destination position at start of scan line
s1: Basics.LongNumber ← s0; -- source s corresponding to d1
f1: Basics.LongNumber ← f0; -- source f corresponding to d1
WHILE d1.s<box.min.s
DO d1.s ← d1.s+1;
IF s1.lc<ssdn.lc THEN s1.lc ← s1.lc+ssup.lc ELSE s1.lc ← s1.lc-ssdn.lc;
IF f1.lc<fsdn.lc THEN f1.lc ← f1.lc+fsup.lc ELSE f1.lc ← f1.lc-fsdn.lc;
ENDLOOP;
IF d1.s=box.min.s THEN { d0 ← d1; s0.lc ← s1.lc; f0.lc ← f1.lc } ELSE ERROR;
WHILE d1.f<box.min.f
DO d1.f ← d1.f+1;
IF s1.lc<sfdn.lc THEN s1.lc ← s1.lc+sfup.lc ELSE s1.lc ← s1.lc-sfdn.lc;
IF f1.lc<ffdn.lc THEN f1.lc ← f1.lc+ffup.lc ELSE f1.lc ← f1.lc-ffdn.lc;
ENDLOOP;
IF d1.f=box.min.f THEN NULL ELSE ERROR;
pixels.length ← count;
--For each scan line of box--
DO
FOR i:
NAT
IN[0..samplesPerPixel)
DO
map: IISample.SampleMap ~ self[i];
samples: IISample.SampleBuffer ~ pixels[i];
s: Basics.LongNumber ← s1;
f: Basics.LongNumber ← f1;
IF map.base.bit=0 AND (map.bitsPerLine MOD bitsPerWord)=0 AND
map.bitsPerSample=8
THEN {
base: Pointer8 ~ LOOPHOLE[map.base.word];
wordsPerLine: NAT ~ map.bitsPerLine/bitsPerWord;
result: LONG POINTER TO RawSamples ~ InlinePointerToSamples[samples, 0, count];
FOR k:
NAT
IN[0..count)
DO
Loop overhead (23 cycles) --
Calculate i* (34 cycles) --
is0: CARDINAL ~ s.hi;
is1: CARDINAL ~ IF is0<isdn THEN is0+isup ELSE is0-isdn;
if0: CARDINAL ~ f.hi;
if1: CARDINAL ~ IF if0<ifdn THEN if0+ifup ELSE if0-ifdn;
Calculate w* (68 cycles) --
w11: CARDINAL ~ Basics.HighHalf[Basics.LongMult[s.lo, f.lo]];
w10: CARDINAL ~ s.lo-w11;
w01: CARDINAL ~ f.lo-w11;
w00: CARDINAL ~ 0-w01-w10-w11;
v00, v01, v10, v11, value: CARDINAL;
Calculate line* (80 cycles) --
line0: Pointer8 ~ base+Basics.LongMult[is0, wordsPerLine];
line1: Pointer8 ~ base+Basics.LongMult[is1, wordsPerLine];
Fetch v* (52 cycles) --
TRUSTED { v00 ← line0[if0]; v01 ← line0[if1]; v10 ← line1[if0]; v11 ← line1[if1]; };
Calculate value (143 cycles) --
value ←
IF w00#0
THEN Basics.HighHalf[
Basics.LongMult[w00, v00] + Basics.LongMult[w01, v01] +
Basics.LongMult[w10, v10] + Basics.LongMult[w11, v11]
] ELSE v00;
Store result (14 cycles) --
TRUSTED { result[k] ← value };
Bump s and f (66 cycles) --
IF s.lc<sfdn.lc THEN s.lc ← s.lc+sfup.lc ELSE s.lc ← s.lc-sfdn.lc;
IF f.lc<ffdn.lc THEN f.lc ← f.lc+ffup.lc ELSE f.lc ← f.lc-ffdn.lc;
Total (480 cycles): 30.7 microseconds/sample; 8 seconds for 512*512 samples --
ENDLOOP;
}
ELSE {
-- the slow but general way
FOR k:
NAT
IN[0..count)
DO
is0: CARDINAL ~ s.hi;
is1: CARDINAL ~ IF is0<isdn THEN is0+isup ELSE is0-isdn;
if0: CARDINAL ~ f.hi;
if1: CARDINAL ~ IF if0<ifdn THEN if0+ifup ELSE if0-ifdn;
w11: CARDINAL ~ Basics.HighHalf[Basics.LongMult[s.lo, f.lo]];
w10: CARDINAL ~ s.lo-w11;
w01: CARDINAL ~ f.lo-w11;
w00: CARDINAL ~ 0-w01-w10-w11;
v00, v01, v10, v11, value: CARDINAL;
v00 ← IISample.Get[map, [s: is0+self.box.min.s, f: if0+self.box.min.f]];
v01 ← IISample.Get[map, [s: is0+self.box.min.s, f: if1+self.box.min.f]];
v10 ← IISample.Get[map, [s: is1+self.box.min.s, f: if0+self.box.min.f]];
v11 ← IISample.Get[map, [s: is1+self.box.min.s, f: if1+self.box.min.f]];
value ←
IF w00=0
THEN v00
ELSE Basics.HighHalf[
Basics.LongMult[w00, v00] + Basics.LongMult[w01, v01] +
Basics.LongMult[w10, v10] + Basics.LongMult[w11, v11]];
samples[k] ← value;
IF s.lc<sfdn.lc THEN s.lc ← s.lc+sfup.lc ELSE s.lc ← s.lc-sfdn.lc;
IF f.lc<ffdn.lc THEN f.lc ← f.lc+ffup.lc ELSE f.lc ← f.lc-ffdn.lc;
ENDLOOP;
};
ENDLOOP;
action[pixels, d1];
d1.s ← d1.s+1; IF NOT d1.s<box.max.s THEN EXIT;
IF s1.lc<ssdn.lc THEN s1.lc ← s1.lc+ssup.lc ELSE s1.lc ← s1.lc-ssdn.lc;
IF f1.lc<fsdn.lc THEN f1.lc ← f1.lc+fsup.lc ELSE f1.lc ← f1.lc-fsdn.lc;
ENDLOOP;
};
-- Set increments --
[[rs, rf]] ← m.InverseTransformVec[[0, 1] !
Real.RealException => { rs ← rf ← 0; CONTINUE }];
-- A singular transformation means the image can't be shown anyway.
sfDelta.li ← ScaledFromRealMod[rs, sSize];
ffDelta.li ← ScaledFromRealMod[rf, fSize];
[[rs, rf]] ← m.InverseTransformVec[[1, 0] !
Real.RealException => { rs ← rf ← 0; CONTINUE }];
ssDelta.li ← ScaledFromRealMod[rs, sSize];
fsDelta.li ← ScaledFromRealMod[rf, fSize];
-- Set initial position --
[[rs, rf]] ← m.InverseTransform[[d0.s+0.5, d0.f+0.5] !
Real.RealException => { rs ← rf ← 0; CONTINUE }];
IF interpolate
AND HalfInteger[rs]
AND HalfInteger[rf]
AND sfDelta.lo = 0
AND ffDelta.lo = 0
AND ssDelta.lo = 0
AND fsDelta.lo = 0
THEN {
-- No need to interpolate, since all sampling points fall on pixel centers anyway --
interpolate ← FALSE;
};
IF interpolate THEN { rs ← rs-0.5; rf ← rf-0.5 };
s0.li ← ScaledFromRealMod[rs-self.box.min.s, sSize];
f0.li ← ScaledFromRealMod[rf-self.box.min.f, fSize];
boxes[IF interpolate THEN boxActionInterpolatedSamples ELSE boxActionPointSamples];
ReleaseScratchPixels[pixels];
};
HalfInteger:
PROC [r:
REAL]
RETURNS [
BOOL] ~ {
fuzz: INT ~ 8;
half: INT ~ INT[LAST[CARDINAL]]/2+1;
lo: CARDINAL ~ half-fuzz;
hi: CARDINAL ~ half+fuzz;
n: Basics.LongNumber ~ [li[ScaledFromRealMod[r, 1]]];
halfInteger: BOOL ~ n.lo IN [lo..hi];
RETURN [halfInteger]
};
END.