<> <> <> 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] ~ { < 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; <> 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.