SweepArithImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, March 28, 1986 4:30:47 pm PST
DIRECTORY
Basics USING [CompareINT, CompareCard, HighHalf, LowHalf, LongDiv, LongDivMod, LongMult, BITOR, BITSHIFT, LongNumber],
Sweep;
SweepArithImpl: CEDAR PROGRAM IMPORTS Basics EXPORTS Sweep =
BEGIN OPEN Sweep;
limit: INT = 32767;
InputOutOfRange: PUBLIC ERROR = CODE;
BoundsCheck:
PUBLIC
PROC [p: Point] ~ {
IF (p.x < 0) OR (p.x > limit) OR (p.y < 0) OR (p.y > limit) THEN ERROR InputOutOfRange;
};
CompareSlopes:
PUBLIC
PROC [l1, l2: Line]
RETURNS [Relation] ~ {
xDelta1: INT ← l1.below.x - l1.above.x;
xDelta2: INT ← l2.below.x - l2.above.x;
yDelta1: INT ← l1.above.y - l1.below.y;
yDelta2: INT ← l2.above.y - l2.below.y;
cross1, cross2: INT;
IF yDelta1 < 0 THEN {yDelta1 ← -yDelta1; xDelta1 ← - xDelta1};
IF yDelta2 < 0 THEN {yDelta2 ← -yDelta2; xDelta2 ← - xDelta2};
cross1 ← xDelta1 * yDelta2;
cross2 ← xDelta2 * yDelta1;
RETURN[Basics.CompareINT[cross1, cross2]];
};
ComparePoints:
PUBLIC
PROC [p1, p2: Point]
RETURNS [r: Relation] ~ {
r ← Basics.CompareINT[p1.y, p2.y];
IF r = equal THEN r ← Basics.CompareINT[p1.x, p2.x];
};
ComparePointLine:
PUBLIC
PROC [p: Point, l: Line]
RETURNS [Relation] ~ {
yDelta, cross, Numerator: INT;
IF (p.x < l.above.x) AND (p.x < l.below.x) THEN RETURN[less]; --Most likely
yDelta ← l.above.y - l.below.y;
Numerator ← l.above.x*(p.y - l.below.y) + l.below.x*(l.above.y - p.y);
IF yDelta < 0 THEN {yDelta ← - yDelta; Numerator ← - Numerator};
IF yDelta > 0
THEN {
cross ← yDelta * p.x;
RETURN[Basics.CompareINT[cross, Numerator]]
};
IF Numerator = 0
THEN
{IF p.x > l.above.x THEN RETURN[greater];
IF p.x < l.below.x THEN RETURN[less];
RETURN[equal]
};
ERROR;
};
CompareLinesAtY:
PUBLIC
PROC [l1, l2: Line, p: Point]
RETURNS [r: Relation] ~ {
y: INT ← p.y;
y1Delta, y2Delta, Numerator1, Numerator2: INT;
switch: BOOLEAN ← FALSE;
c1Minor, c1Major, c2Minor, c2Major: LONG CARDINAL;
IF MAX[l1.above.x, l1.below.x] < MIN[l2.above.x, l2.below.x] THEN RETURN[less]; --Most likely
y1Delta ← l1.above.y - l1.below.y;
y2Delta ← l2.above.y - l2.below.y;
Numerator1 ← l1.above.x*(y - l1.below.y) + l1.below.x*(l1.above.y - y);
Numerator2 ← l2.above.x*(y - l2.below.y) + l2.below.x*(l2.above.y - y);
IF y1Delta < 0 THEN {y1Delta ← - y1Delta; Numerator1 ← - Numerator1};
IF y2Delta < 0 THEN {y2Delta ← - y2Delta; Numerator2 ← - Numerator2};
IF (y1Delta > 0)
AND (y2Delta > 0)
THEN {
IF Numerator1 < 0
THEN {
IF Numerator2 > 0 THEN RETURN[less];
Numerator1 ← - Numerator1; Numerator2 ← - Numerator2;
switch ← TRUE
}
ELSE IF Numerator2 < 0 THEN RETURN[greater];
c1Minor ← Basics.LongMult[Basics.LowHalf[y2Delta], Basics.LowHalf[Numerator1]];
c1Major ← Basics.LongMult[Basics.LowHalf[y2Delta], Basics.HighHalf[Numerator1]] + Basics.HighHalf[c1Minor];
c2Minor ← Basics.LongMult[Basics.LowHalf[y1Delta], Basics.LowHalf[Numerator2]];
c2Major ← Basics.LongMult[Basics.LowHalf[y1Delta], Basics.HighHalf[Numerator2]] + Basics.HighHalf[c2Minor];
r ← Basics.CompareCard[c1Major, c2Major];
IF r = equal THEN r ← Basics.CompareCard[Basics.LowHalf[c1Minor], Basics.LowHalf[c2Minor] ];
IF r # equal
THEN {
IF switch THEN r ← IF r = less THEN greater ELSE less;
RETURN[r];
};
IF p.x * y1Delta > Numerator1 THEN RETURN[CompareSlopes[l2, l1]]
ELSE RETURN[CompareSlopes[l1, l2]]};
IF (y1Delta = 0)
AND l1.above.y = y
THEN
{IF ComparePointLine[l1.below, l2] # less THEN RETURN[greater];
IF ComparePointLine[l1.above, l2] # greater THEN RETURN[less];
RETURN[equal]};
IF (y2Delta = 0)
AND l2.above.y = y
THEN
{IF ComparePointLine[l2.below, l1] # less THEN RETURN[less];
IF ComparePointLine[l2.above, l1] # greater THEN RETURN[greater];
RETURN[equal]};
ERROR;
};
PairIntersection:
PUBLIC
PROC [l1: Line, l2: Line]
RETURNS [p: Point←
NIL, s: LineRelation, s1, s2: EndPointRelation ← exterior] ~ {
r1, r2: Relation;
denom, numer1, numer2: INT;
IF MAX[l1.above.x, l1.below.x] < MIN[l2.above.x, l2.below.x] THEN RETURN[s: other]; --Most likely
denom ← (l1.above.x - l1.below.x)*(l2.below.y - l2.above.y) - (l2.below.x - l2.above.x)*(l1.above.y - l1.below.y);
numer1 ← (l2.below.x - l1.below.x)*(l2.below.y - l2.above.y) - (l2.below.x - l2.above.x)*(l2.below.y - l1.below.y);
numer2 ← (l1.above.x - l1.below.x)*(l2.below.y - l1.below.y) - (l2.below.x - l1.below.x)*(l1.above.y - l1.below.y);
IF denom = 0
THEN
IF numer1 = 0
THEN {
r1 ← ComparePoints[l1.above, l2.below];
IF r1 = equal THEN RETURN[l2.below, intersect, above, below];
r2 ← ComparePoints[l1.below, l2.above];
IF r2 = equal THEN RETURN[l2.above, intersect, below, above];
IF r1 = less OR r2 = greater THEN RETURN[s: parallel] ELSE RETURN[s: colinear];
}
ELSE RETURN[s: parallel]
ELSE
{IF denom < 0 THEN {denom ← - denom; numer1 ← - numer1; numer2 ← - numer2};
SELECT numer1
FROM
< 0, > denom => {s1 ← exterior; s ← other; RETURN};
= 0 => s1 ← below;
= denom => s1 ← above;
ENDCASE => s1 ← interior;
SELECT numer2
FROM
< 0, > denom => {s2 ← exterior; s ← other; RETURN};
= 0 => {s2 ← below; s ← intersect; p ← l2.below; RETURN};
= denom => {s2 ← above; s ← intersect; p ← l2.above; RETURN};
ENDCASE => s2 ← interior;
s ← intersect;
SELECT s1
FROM
below => {p ← l1.below; RETURN};
above => {p ← l1.above; RETURN};
interior => {
p ← NEW[PointRec];
IF l1.below.x < l1.above.x
THEN
p.x ← l1.below.x + Special[l1.above.x - l1.below.x, numer1, denom]
ELSE
p.x ← l1.above.x + Special[l1.below.x - l1.above.x, denom - numer1, denom];
p.y ← l1.below.y + Special[l1.above.y - l1.below.y, numer1, denom];
};
ENDCASE;
};
};
Special:
PROC [a, b, c:
INT]
RETURNS [result:
INT] ~ {
Computes a * b / c, assuming a, b, c > 0, and a and result are INTEGER [0..32K)
OPEN Basics;
s, t: LONG CARDINAL;
p1, p2, p3, p4, c1, c2, c3: CARDINAL;
rem: CARDINAL;
IF HighHalf[c] = 0 THEN result ← LongDiv[a*b, LowHalf[c]]
ELSE {
t ← LongMult[LowHalf[a], LowHalf[b]];
s ← LongMult[LowHalf[a], HighHalf[b]] + HighHalf[t];
p4 ← 0;
p3 ← LowHalf[t];
p2 ← LowHalf[s];
p1 ← HighHalf[s];
c1 ← HighHalf[c];
c2 ← LowHalf[c];
c3 ← 0;
WHILE c1 # 0
DO
c3 ← BITOR[BITSHIFT[c3, -1], BITSHIFT[c2, 15]];
c2 ← BITOR[BITSHIFT[c2, -1], BITSHIFT[c1, 15]];
c1 ← BITSHIFT[c1, -1];
p4 ← BITOR[BITSHIFT[p4, -1], BITSHIFT[p3, 15]];
p3 ← BITOR[BITSHIFT[p3, -1], BITSHIFT[p2, 15]];
p2 ← BITOR[BITSHIFT[p2, -1], BITSHIFT[p1, 15]];
p1 ← BITSHIFT[p1, -1];
ENDLOOP;
Now c1 and p1 are zero
LOOPHOLE[s, LongNumber].highbits ← p2; LOOPHOLE[s, LongNumber].lowbits ← p3;
[result, rem] ← LongDivMod[s, c2];
LOOPHOLE[s, LongNumber].highbits ← rem; LOOPHOLE[s, LongNumber].lowbits ← p4;
t ← LongMult[result, c3];
IF t > s THEN result ← result - 1; --Never off by more than one
};
};
END.