ImagerMaskCacheImpl.mesa
Copyright (C) 1984, 1985 by Xerox Corporation. All rights reserved.
Michael Plass, August 17, 1984 3:57:12 pm PDT
Doug Wyatt, January 26, 1985 5:42:55 pm PST
DIRECTORY
Ascii,
Basics,
BasicTime,
CountedVM,
FS,
ImagerFrameBuffer,
ImagerMaskCache,
ImagerMask,
ImagerPixelMap,
ImagerTransformation,
IO,
Process,
Rope,
SafeStorage,
Scaled,
VM,
ImagerMaskCacheImpl: CEDAR MONITOR
IMPORTS VM, BasicTime, CountedVM, IO, Ascii, FS, ImagerTransformation, Rope, Process, SafeStorage, ImagerMask, ImagerPixelMap, Basics, ImagerFrameBuffer
EXPORTS ImagerMaskCache
~ BEGIN OPEN ImagerMaskCache;
WordsForPages: PROC [pages: INT] RETURNS [INT] ~ {RETURN [VM.WordsForPages[pages]]};
PagesForWords: PROC [words: INT] RETURNS [INT] ~ {RETURN [VM.PagesForWords[words]]};
currentStatus: Status ← disabled;
statusChange: CONDITION;
lockCount: NAT ← 0;
lockOwner: UNSAFE PROCESS ← NIL;
lockFree: CONDITION;
GetHeader: PUBLIC PROC RETURNS [header: Header] ~ {
Locked: PROC ~ TRUSTED {
status: Status ← GetStatus[waitDuringTransition: TRUE];
IF status = disabled THEN header ← [0, 0, 0, 0]
ELSE {
hdr: LONG POINTER TO Header ← residentPointer;
header ← hdr^
};
};
DoUnderLock[Locked];
};
Lock: ENTRY PROC ~ {
me: UNSAFE PROCESS ~ Process.GetCurrent[];
IF lockOwner # me THEN {
WHILE lockCount # 0 DO WAIT lockFree ENDLOOP;
lockOwner ← me;
};
lockCount ← lockCount + 1;
};
UnLock: ENTRY PROC ~ {
IF lockOwner # Process.GetCurrent[] THEN ERROR;
lockCount ← lockCount - 1;
IF lockCount = 0 THEN {lockOwner ← NIL; NOTIFY lockFree};
};
GetStatus: PUBLIC ENTRY PROC [waitDuringTransition: BOOLEAN] RETURNS [Status] ~ {
WHILE waitDuringTransition AND currentStatus = transition DO
WAIT statusChange;
ENDLOOP;
RETURN [currentStatus]
};
SetStatus: PUBLIC ENTRY PROC [status: Status] ~ {
currentStatus ← status;
BROADCAST statusChange;
};
DoUnderLock: PUBLIC PROC [action: PROC] ~ {
Lock[];
action[ ! UNWIND => UnLock[]];
UnLock[];
};
DoEnabled: PUBLIC PROC [action: PROC] ~ {
Lock[];
BEGIN ENABLE UNWIND => UnLock[];
IF currentStatus = extendable THEN NULL
ELSE Enable[];
action[];
END;
UnLock[];
};
DoReadOnlyOrEnabled: PUBLIC PROC [action: PROC] ~ {
Lock[];
BEGIN ENABLE UNWIND => UnLock[];
IF currentStatus = readOnly OR currentStatus = extendable THEN NULL
ELSE Enable[];
action[];
END;
UnLock[];
};
Disable: PUBLIC PROC ~ {
Lock[];
BEGIN ENABLE UNWIND => UnLock[];
status: Status ← GetStatus[waitDuringTransition: TRUE];
currentStatus ← transition;
IF status = extendable THEN {
IF WriteCacheToDisk[].couldNotExtend THEN NULL;
FS.Close[file];
file ← [NIL];
residentPointer ← NIL;
resident ← NIL;
SafeStorage.ReclaimCollectibleObjects[];
status ← disabled;
};
IF status = readOnly THEN {
FS.Close[file];
file ← [NIL];
residentPointer ← NIL;
resident ← NIL;
SafeStorage.ReclaimCollectibleObjects[];
ResetTables[];
status ← disabled;
};
SetStatus[status];
END;
UnLock[];
};
MakeReadOnly: PUBLIC PROC ~ {
Lock[];
BEGIN ENABLE UNWIND => UnLock[];
status: Status ← GetStatus[waitDuringTransition: TRUE];
currentStatus ← transition;
IF status = extendable THEN {
date: BasicTime.GMT;
IF WriteCacheToDisk[].couldNotExtend THEN {
FS.Close[file];
file ← [NIL];
residentPointer ← NIL;
resident ← NIL;
SafeStorage.ReclaimCollectibleObjects[];
status ← disabled;
}
ELSE {
date ← FS.GetInfo[file].created;
FS.Close[file];
file ← FS.Open[fontCacheName, $read, date];
status ← readOnly;
};
};
IF status = disabled THEN {
OpenFileAndBuildTables[];
status ← readOnly;
};
SetStatus[status];
END;
UnLock[];
};
Enable: PUBLIC PROC ~ {
Lock[];
BEGIN ENABLE UNWIND => UnLock[];
status: Status ← GetStatus[waitDuringTransition: TRUE];
currentStatus ← transition;
IF status = disabled THEN {
OpenFileAndBuildTables[];
status ← extendable;
};
IF status = readOnly THEN {
date: BasicTime.GMT ← FS.GetInfo[file].created;
FS.Close[file];
file ← FS.Open[fontCacheName, $write, date];
status ← extendable;
};
SetStatus[status];
END;
UnLock[];
};
transTable: TransTable ← NEW[TransTableRep[20]];
TransTable: TYPE ~ REF TransTableRep;
TransTableRep: TYPE ~ RECORD [
length: NAT ← 0,
highWaterMark: NAT ← 0,
seq: SEQUENCE maxLength: NAT OF REF TransformationCodeEntry
];
CheckTransTable: PROC ~ {
-- This is to document the invariants on the transformation table, and is not normally executed.
FOR i: NAT IN [0..transTable.maxLength) DO
ti: REF TransformationCodeEntry ← transTable[i];
ok: BOOL ←
SELECT i FROM
IN [0..transTable.length) =>
ti.codeValue = i,
-- These have code values associated with them
IN [transTable.length..transTable.highWaterMark) =>
ti.codeValue = CARDINAL.LAST,
-- These currently have no code values, but have been handed out to clients and so must be kept around.
IN [transTable.highWaterMark..transTable.maxLength) =>
ti = NIL,
-- Free slots in the sequence.
ENDCASE => ERROR;
IF NOT ok THEN ERROR;
ENDLOOP;
};
TransformationFromTransID: PUBLIC PROC[transID: TransID] RETURNS[Transformation] ~ {
t: Coefficients ← transID.coefficients;
RETURN [ImagerTransformation.Create[t.a, t.b, t.c, t.d, t.e, t.f]];
};
TransIDFromTransformation: PUBLIC PROC [transformation: Transformation, scanConversionType: ScanConversionType, hint: TransID] RETURNS [transID: TransID] ~ {
t: Transformation ~ transformation;
c: Coefficients ← [t.a, t.b, t.c, t.d, t.e, t.f];
IF hint # NIL AND hint.coefficients = c AND hint.scanConversionType = scanConversionType THEN RETURN [hint];
RETURN [InsertTransformation[c, scanConversionType]];
};
InsertTransformation: PROC [c: Coefficients, scanConversionType: ScanConversionType] RETURNS [transID: TransID] ~ {
Locked: PROC ~ {
FOR i: NAT IN [0..transTable.highWaterMark) DO
ti: TransID ← transTable[i];
IF ti.coefficients = c AND ti.scanConversionType = scanConversionType THEN {transID ← ti; RETURN};
ENDLOOP;
IF transTable.highWaterMark >= transTable.maxLength THEN {
new: TransTable ← NEW[TransTableRep[transTable.maxLength + 20]];
FOR i: NAT IN [0..transTable.highWaterMark) DO
new[i] ← transTable[i];
transTable[i] ← NIL;
ENDLOOP;
new.length ← transTable.length;
new.highWaterMark ← transTable.highWaterMark;
transTable ← new;
};
transID ← transTable[transTable.highWaterMark]
← NEW [TransformationCodeEntry ← [CARDINAL.LAST, c, scanConversionType]];
transTable.highWaterMark ← transTable.highWaterMark + 1;
};
DoUnderLock[Locked];
};
SetTransIDCode: PROC [transID: TransID] ~ {
Assigns next available code to transID.
IF transID.codeValue = CARDINAL.LAST THEN {
FOR i: NAT IN [transTable.length..transTable.highWaterMark) DO
IF transTable[i] = transID THEN {
s: REF TransformationCodeEntry ← transTable[transTable.length];
transTable[transTable.length] ← transID;
transTable[i] ← s;
transID.codeValue ← transTable.length;
transTable.length ← transTable.length + 1;
RETURN;
};
ENDLOOP;
ERROR FontCacheInconsistency[$BadTransID, 0];
};
};
GetTransCode: PROC [transID: TransID] RETURNS [transIDCode: CARDINAL] ~ {
IF transID.codeValue = CARDINAL.LAST THEN TRUSTED {
SetTransIDCode[transID];
[] ← AppendEntry[transformationCode, SIZE[TransformationCodeEntry], LOOPHOLE[transID]];
};
transIDCode ← transID.codeValue;
};
fontIDTableOldLength: NAT ← 0;
fontIDTable: FontIDTable ← NEW[FontIDTableRep[20]];
FontIDTable: TYPE ~ REF FontIDTableRep;
FontIDTableRep: TYPE ~ RECORD [
length: NAT ← 0,
highWaterMark: NAT ← 0,
seq: SEQUENCE maxLength: NAT OF REF FontIDCodeEntry
];
CheckFontIDTable: PROC ~ {
-- This is to document the invariants on the fontID table, and is not normally executed.
FOR i: NAT IN [0..fontIDTable.maxLength) DO
fi: REF FontIDCodeEntry ← fontIDTable[i];
ok: BOOL ←
SELECT i FROM
IN [0..fontIDTable.length) =>
fi.codeValue = i,
-- These have code values associated with them
IN [fontIDTable.length..fontIDTable.highWaterMark) =>
fi.codeValue = CARDINAL.LAST,
-- These currently have no code values, but have been handed out to clients and so must be kept around.
IN [fontIDTable.highWaterMark..fontIDTable.maxLength) =>
fi = NIL,
-- Free slots in the sequence.
ENDCASE => ERROR;
IF NOT ok THEN ERROR;
ENDLOOP;
};
RopeFromFontID: PUBLIC PROC [fontID: FontID] RETURNS [name: ROPE] ~ {
i: NAT ← 0;
append: PROC RETURNS [CHAR] ~ {RETURN [fontID[(i←i+1)-1]]};
name ← Rope.FromProc[fontID.chars, append];
};
GMTFromFontID: PUBLIC PROC [fontID: FontID] RETURNS [createdTime: BasicTime.GMT] ~ {
createdTime ← fontID.createdTime;
};
CreateFontID: PROC [chars: NAT, charProc: PROC [NAT] RETURNS [CHAR], createdTime: BasicTime.GMT] RETURNS [fontID: FontID] ~ {
Match: PROC [fid: REF FontIDCodeEntry] RETURNS [BOOLEAN] ~ {
IF fid.createdTime # createdTime THEN RETURN [FALSE];
IF fid.chars # chars THEN RETURN [FALSE];
FOR i: NAT IN [0..chars) DO
IF fid[i] # charProc[i] THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
};
Lookup: PROC ~ {
FOR i: NAT IN [0..fontIDTable.highWaterMark) DO
fi: FontID ← fontIDTable[i];
IF Match[fi] THEN {fontID ← fi; RETURN};
ENDLOOP;
fontID ← NEW[FontIDCodeEntry[chars]];
fontID.codeValue ← CARDINAL.LAST;
fontID.createdTime ← createdTime;
FOR i: NAT IN [0..chars) DO
fontID[i] ← charProc[i];
ENDLOOP;
IF fontIDTable.highWaterMark >= fontIDTable.maxLength THEN {
new: FontIDTable ← NEW[FontIDTableRep[fontIDTable.highWaterMark + 20]];
FOR i: NAT IN [0..fontIDTable.highWaterMark) DO
new[i] ← fontIDTable[i];
ENDLOOP;
new.length ← fontIDTable.length;
new.highWaterMark ← fontIDTable.highWaterMark;
fontIDTable ← new;
};
fontIDTable[fontIDTable.highWaterMark] ← fontID;
fontIDTable.highWaterMark ← fontIDTable.highWaterMark + 1;
};
DoUnderLock[Lookup];
};
FontIDFromRopeAndGMT: PUBLIC PROC [name: ROPE, createdTime: BasicTime.GMT] RETURNS [fontID: FontID] ~ {
charProc: PROC [i: NAT] RETURNS [CHAR] ~ {RETURN [Ascii.Lower[name.Fetch[i]]]};
fontID ← CreateFontID[name.Length, charProc, createdTime];
};
FontIDFromFontIDCodeEntry: PROC [f: LONG POINTER TO FontIDCodeEntry] RETURNS [fontID: FontID] ~ TRUSTED {
charProc: SAFE PROC [i: NAT] RETURNS [CHAR] ~ TRUSTED {RETURN [f[i]]};
fontID ← CreateFontID[f.chars, charProc, f.createdTime];
};
SetFontIDCode: PROC [fontID: FontID] ~ {
Assigns next available code to transID.
IF fontID.codeValue = CARDINAL.LAST THEN {
FOR i: NAT IN [fontIDTable.length..fontIDTable.highWaterMark) DO
IF fontIDTable[i] = fontID THEN {
s: REF FontIDCodeEntry ← fontIDTable[fontIDTable.length];
fontIDTable[fontIDTable.length] ← fontID;
fontIDTable[i] ← s;
fontID.codeValue ← fontIDTable.length;
fontIDTable.length ← fontIDTable.length + 1;
RETURN;
};
ENDLOOP;
ERROR FontCacheInconsistency[$BadFontID, 0];
};
};
GetFontCode: PROC [fontID: FontID] RETURNS [fontIDCode: CARDINAL] ~ {
IF fontID.codeValue = CARDINAL.LAST THEN TRUSTED {
SetFontIDCode[fontID];
[] ← AppendEntry[fontIDCode, SIZE[FontIDCodeEntry[fontID.chars]], LOOPHOLE[fontID]];
};
fontIDCode ← fontID.codeValue;
};
fontCacheName: ROPE ← "[]<>FontCache.DontDeleteMe";
file: FS.OpenFile;
resident: CountedVM.Handle ← NIL;
residentPointer: LONG POINTER ← NIL;
CreateNewFile: PROC ~ TRUSTED {
header: Header ← [
password: passwordValue,
numberOfEntries: 0,
numberOfWords: SIZE[Header] + SIZE[CARDINAL],
totalUsage: 0
];
pointer: LONG POINTER ← @header;
stream: IO.STREAM ← FS.StreamOpen[fontCacheName, $create];
stream.UnsafePutBlock[[base: pointer, startIndex: 0, count: SIZE[Header]*Basics.bytesPerWord]];
stream.PutChar['\000];
stream.PutChar['\000];
stream.Close;
};
CantAppend: ERROR ~ CODE;
AppendEntry: PROC [entryType: EntryType, entryLengthInWords: CARDINAL, dataPtr: LONG POINTER] RETURNS [offset: INT] ~ {
nwords: CARDINAL ~ entryLengthInWords + SIZE[EntryPrefix];
TryAppend: PROC RETURNS [failed: BOOLEAN] ~ TRUSTED {
hdr: LONG POINTER TO Header ← residentPointer;
destOffset: LONG CARDINAL ← hdr.numberOfWords - SIZE[CARDINAL];
newSize: INT ← hdr.numberOfWords + nwords;
IF newSize < 0 THEN ERROR;
IF newSize > resident.Words THEN failed ← TRUE
ELSE {
ep: LONG POINTER TO EntryPrefix ← residentPointer+destOffset;
ep^ ← [entryType, entryLengthInWords];
PrincOpsUtils.LongCopy[from: dataPtr, nwords: entryLengthInWords, to: residentPointer+destOffset+SIZE[EntryPrefix]];
LOOPHOLE[residentPointer+destOffset+nwords, LONG POINTER TO CARDINAL]^ ← 0;
hdr.numberOfWords ← newSize;
hdr.numberOfEntries ← hdr.numberOfEntries + 1;
offset ← destOffset + SIZE[EntryPrefix];
failed ← FALSE
};
};
IF currentStatus # extendable THEN ERROR CantAppend;
IF TryAppend[].failed THEN {
WriteOutAndReadIn[];
IF TryAppend[].failed THEN ERROR CantAppend;
};
};
WriteCacheToDisk: PROC RETURNS [couldNotExtend: BOOLEAN ← FALSE] ~ TRUSTED {
hdr: LONG POINTER TO Header ← residentPointer;
pages: INT ← PagesForWords[hdr.numberOfWords];
FS.SetPageCount[file, pages
! FS.Error => IF error.group = environment THEN {couldNotExtend ← TRUE; CONTINUE}
];
IF couldNotExtend THEN RETURN;
FS.Write[file: file, to: 0, nPages: pages, from: residentPointer];
FS.SetByteCountAndCreatedTime[file, hdr.numberOfWords*Basics.bytesPerWord, BasicTime.Now[]];
};
WriteOutAndReadIn: PROC ~ TRUSTED {
Writes out the resident version, reallocates resident vm, and reads the resident version back in. The data structures do not need to change for this operation.
If it could not extend the file, it returns without doing anything.
hdr: LONG POINTER TO Header ← residentPointer;
pages: INT ← PagesForWords[hdr.numberOfWords];
couldNotExtend: BOOLEAN ← TRUE;
IF WriteCacheToDisk[].couldNotExtend THEN RETURN;
residentPointer ← hdr ← NIL;
resident ← NIL;
SafeStorage.ReclaimCollectibleObjects[];
Process.Pause[Process.MsecToTicks[1000]];
The pause is in the hope that finalization will free up the old vm before reallocation.
AllocateResidentCacheSpace[minPages: pages];
FS.Read[file: file, from: 0, nPages: pages, to: residentPointer];
};
FontCacheInconsistency: PUBLIC ERROR [reason: ATOM, wordOffset: INT] ~ CODE;
hashEntries: INT ← 0;
maxProbes: NAT ← 100;
hashTableSize: NAT ~ 32749; -- a prime
hashTable: REF ARRAY [0..hashTableSize) OF INT ← NEW[ARRAY [0..hashTableSize) OF INT];
stats: RECORD [sLookups, sProbes, uLookups, uProbes, fLookups: LONG CARDINAL ← 0];
HashTableLookup: PROC [fontIDCode, transformationCode: CARDINAL, charCode: INT]
RETURNS [hashIndex: CARDINAL] ~ TRUSTED {
The first probe is intentionally biased to hit the first part of the table; for the simple (common) case of no more than 8 font names, 8 transformations, and char codes in the normal range, most of the hash table need not be swapped in. Successive probes are generated by a multiplicative-congruence random number generator.
OPEN stats;
rand: CARDINAL ← Basics.LowHalf[LOOPHOLE[charCode]] + Basics.HighHalf[LOOPHOLE[charCode]]*1024 + fontIDCode + fontIDCode*32 + transformationCode * 2048 - transformationCode;
h0: CARDINAL ← fontIDCode MOD 8 + transformationCode MOD 8 * 8 + (Basics.LowHalf[LOOPHOLE[charCode]] MOD 128 - 32)* 64;
WHILE h0 >= hashTableSize DO h0 ← h0 - hashTableSize ENDLOOP;
hashIndex ← h0;
FOR i: CARDINAL IN [0..hashTableSize) DO
t: INT ← hashTable[hashIndex];
IF t = 0 THEN {uProbes ← uProbes + (i + 1); uLookups ← uLookups + 1; RETURN}
ELSE {
te: LONG POINTER TO MaskEntry ← residentPointer + t;
IF te.fontIDCode = fontIDCode
AND te.transformationCode = transformationCode
AND te.charCode = charCode
THEN {sProbes ← sProbes + (i + 1); sLookups ← sLookups + 1; RETURN};
};
rand ← Basics.LongDivMod[Basics.LongMult[3141, rand] + 271, hashTableSize].remainder;
IF (hashIndex ← h0 + rand) >= hashTableSize THEN hashIndex ← hashIndex - hashTableSize;
ENDLOOP;
hashIndex ← CARDINAL.LAST;
fLookups ← fLookups + 1;
};
runGroupOverhead: INT ← 3600;
Used only in deciding which representation to use; a big number weights the choice in favor of rasters.
maskBitsLimit: INT ← 60000;
Used in deciding whether to cache the mask or not
InsertMask: PUBLIC PROC [fontID: FontID, transID: TransID, charCode: INT, sWidth, fWidth: Scaled.Value, mask: Mask, amplified, correctSpace, correctMask: BOOLEAN] RETURNS [ok: BOOLEAN ← FALSE] ~ {
bb: ImagerPixelMap.DeviceRectangle ← ImagerMask.BoundingBox[mask];
runCount: INT ← ImagerMask.CountRuns[mask];
rasterBits: INT ← Basics.LongMult[bb.fSize, bb.sSize];
runGroupBits: INT ← SIZE[Run]*16*runCount + runGroupOverhead;
maskEntryRef: REF MaskEntry ← NIL;
nwords: CARDINAL;
IF MIN[runGroupBits, rasterBits] > maskBitsLimit THEN RETURN [FALSE];
maskEntryRef ← IF runGroupBits < rasterBits THEN GetRuns[mask, bb, runCount] ELSE GetRaster[mask, bb];
WITH maskEntryRef SELECT FROM
ra: REF MaskEntry.raster => nwords ← SIZE[MaskEntry.raster[ra.sSizeBB*((ra.fSizeBB+Basics.bitsPerWord-1)/Basics.bitsPerWord)]];
ru: REF MaskEntry.runs => nwords ← SIZE[MaskEntry.runs[ru.nRuns]];
ENDCASE => ERROR;
maskEntryRef.charCode ← charCode;
maskEntryRef.usage ← 0;
maskEntryRef.sWidth ← sWidth;
maskEntryRef.fWidth ← fWidth;
maskEntryRef.amplified ← amplified;
maskEntryRef.correctSpace ← correctSpace;
maskEntryRef.correctMask ← correctMask;
BEGIN
Insert: PROC ~ TRUSTED {
offset: INT;
hashIndex: CARDINAL;
maskEntryRef.fontIDCode ← GetFontCode[fontID];
maskEntryRef.transformationCode ← GetTransCode[transID];
hashIndex ← HashTableLookup[maskEntryRef.fontIDCode, maskEntryRef.transformationCode, maskEntryRef.charCode];
IF hashIndex = CARDINAL.LAST THEN ok ← FALSE
ELSE IF hashTable[hashIndex] = 0 THEN {
offset ← AppendEntry[mask, nwords, LOOPHOLE[maskEntryRef]];
hashTable[hashIndex] ← offset;
ok ← TRUE;
};
};
DoReadOnlyOrEnabled[Insert ! CantAppend => CONTINUE];
IF NOT ok THEN {
header: Header ← GetHeader[];
TrimCache[maxNumberOfMasks: INT[hashTableSize]*8/10, maxNumberOfWords: header.numberOfWords*8/10];
DoReadOnlyOrEnabled[Insert ! CantAppend => CONTINUE];
};
END;
};
GetRuns: PROC [mask: Mask, bb: ImagerPixelMap.DeviceRectangle, runCount: INT] RETURNS [REF MaskEntry] ~ {
maxRuns: NAT ← runCount+bb.sSize;
maskEntryRef: REF MaskEntry.runs ← NEW[MaskEntry.runs[maxRuns]];
i: NAT ← 0;
s: INTEGER ← bb.sMin;
AppendRun: PROC [sMin, fMin: INTEGER, fSize: NAT] ~ {
WHILE s # sMin DO
IF s > sMin THEN ERROR;
IF i = 0 THEN {s ← bb.sMin ← bb.sMin + 1; bb.sSize ← bb.sSize - 1}
ELSE IF NOT maskEntryRef[i-1].lastRun THEN {
maskEntryRef[i-1].lastRun ← TRUE;
s ← s + 1;
}
ELSE {
IF i >= maxRuns THEN ERROR;
maskEntryRef[i] ← [fMin: 0, lastRun: TRUE, fSize: 0];
s ← s + 1;
i ← i + 1;
};
ENDLOOP;
IF i >= maxRuns THEN ERROR;
maskEntryRef[i] ← [fMin: fMin-bb.fMin, lastRun: FALSE, fSize: fSize];
i ← i + 1;
};
ImagerMask.GenerateRuns[mask, mask, AppendRun, 0, 0];
IF i > 0 THEN {maskEntryRef[i-1].lastRun ← TRUE; s ← s + 1};
maskEntryRef.nRuns ← i;
maskEntryRef.sMinBB ← bb.sMin;
maskEntryRef.fMinBB ← bb.fMin;
maskEntryRef.sSizeBB ← s - bb.sMin;
maskEntryRef.fSizeBB ← bb.fSize;
RETURN [maskEntryRef]
};
GetRaster: PROC [mask: Mask, bb: ImagerPixelMap.DeviceRectangle] RETURNS [REF MaskEntry] ~ TRUSTED {
rast: CARDINAL ← (bb.fSize+Basics.bitsPerWord-1)/Basics.bitsPerWord;
words: CARDINAL ← bb.sSize*rast;
maskEntryRef: REF MaskEntry.raster ← NEW[MaskEntry.raster[words]];
pixelMap: ImagerPixelMap.PixelMap ← [sOrigin: bb.sMin, fOrigin: bb.fMin, sMin: 0, fMin: 0, sSize: bb.sSize, fSize: bb.fSize, refRep: NEW[ImagerPixelMap.PixelMapRep ← [ref: resident, pointer: @maskEntryRef[0], words: words, lines: bb.sSize, lgBitsPerPixel: 0, rast: rast]]];
pixelMap.Clear;
ImagerMask.ApplyConstant[mask, mask, pixelMap, 1];
maskEntryRef.sMinBB ← bb.sMin;
maskEntryRef.fMinBB ← bb.fMin;
maskEntryRef.sSizeBB ← bb.sSize;
maskEntryRef.fSizeBB ← bb.fSize;
RETURN [maskEntryRef]
};
AgeUseCounts: PROC ~ TRUSTED {
Assume resident cache is present and locked
pointer: LONG POINTER ← residentPointer;
offset: INT ← SIZE[Header];
hdr: LONG POINTER TO Header ← residentPointer;
words: INT ← hdr.numberOfWords;
entries: INT ← hdr.numberOfEntries;
newTotal: LONG CARDINAL ← 0;
WHILE offset < words DO
prefix: LONG POINTER TO EntryPrefix ← pointer+offset;
offset ← offset + SIZE[EntryPrefix];
SELECT prefix.entryType FROM
trailer => EXIT;
mask => {
entry: LONG POINTER TO MaskEntry ← pointer + offset;
entry.usage ← entry.usage/2 + entry.usage MOD 2;
newTotal ← newTotal + entry.usage;
};
ENDCASE => NULL;
offset ← offset + prefix.entryLengthInWords;
entries ← entries - 1;
ENDLOOP;
IF offset # words THEN ERROR FontCacheInconsistency[$UnexpectedEndMarker, offset];
IF entries # 0 THEN ERROR FontCacheInconsistency[$WrongNumberOfEntries, offset];
hdr.totalUsage ← newTotal;
};
GetMask: PUBLIC UNSAFE PROC [fontID: FontID, transID: TransID, charCode: INT] RETURNS [maskDesc: MaskDesc ← [NIL, NIL]] ~ UNCHECKED {
Get: PROC ~ TRUSTED {
hashIndex: CARDINAL ← HashTableLookup[fontID.codeValue, transID.codeValue, charCode];
offset: INT;
IF hashIndex # CARDINAL.LAST AND (offset ← hashTable[hashIndex]) # 0 THEN {
me: LONG POINTER TO MaskEntry ← residentPointer + offset;
hdr: LONG POINTER TO Header ← residentPointer;
hdr.totalUsage ← hdr.totalUsage + 1;
IF (me.usage ← me.usage + 1) = CARDINAL.LAST THEN AgeUseCounts[];
maskDesc ← [resident, me];
};
};
DoReadOnlyOrEnabled[Get];
};
GetStringBodyMasks: PUBLIC PROC [
fontID: FontID,
transID: TransID,
stringBodyDesc: StringBodyDesc,
maskProc: UNSAFE PROC [MaskDesc]
] RETURNS [StringBodyDesc] ~ TRUSTED {
Could do this much faster . .
WHILE stringBodyDesc.length # 0 DO
charCode: CARDINAL ← Current[stringBodyDesc];
maskDesc: MaskDesc ← GetMask[fontID, transID, charCode];
IF maskDesc.maskEntryPtr = NIL THEN EXIT;
maskProc[maskDesc];
stringBodyDesc ← Advance[stringBodyDesc];
ENDLOOP;
RETURN [stringBodyDesc]
};
cacheVersion: CARDINAL ← 0;
ResetTables: PROC ~ TRUSTED {
cacheVersion ← cacheVersion + 1;
PrincOpsUtils.LongZero[where: LOOPHOLE[hashTable], nwords: SIZE[ARRAY [0..hashTableSize) OF INT]];
WHILE fontIDTable.length > 0 DO
fontIDTable[fontIDTable.length ← fontIDTable.length - 1].codeValue ← CARDINAL.LAST;
ENDLOOP;
WHILE transTable.length > 0 DO
transTable[transTable.length ← transTable.length - 1].codeValue ← CARDINAL.LAST;
ENDLOOP;
};
BuildTables: PROC ~ TRUSTED {
pointer: LONG POINTER ← residentPointer;
offset: INT ← SIZE[Header];
hdr: LONG POINTER TO Header ← residentPointer;
words: INT ← hdr.numberOfWords;
entries: INT ← hdr.numberOfEntries;
totalUsage: INT ← hdr.totalUsage;
IF hdr.password # passwordValue THEN
ERROR FontCacheInconsistency[$NotAFontCache, 0];
IF Basics.bytesPerWord*words # FS.GetInfo[file].bytes THEN
ERROR FontCacheInconsistency[$InconsistentLengths, 0];
ResetTables[];
WHILE offset < words DO
prefix: LONG POINTER TO EntryPrefix ← pointer+offset;
offset ← offset + SIZE[EntryPrefix];
SELECT prefix.entryType FROM
trailer => EXIT;
fontIDCode => {
ffidce: LONG POINTER TO FontIDCodeEntry ← pointer+offset;
fontID: FontID ← FontIDFromFontIDCodeEntry[ffidce];
SetFontIDCode[fontID];
IF fontID.codeValue # ffidce.codeValue THEN ERROR FontCacheInconsistency[$FontIDCodesOutOfSequence, offset];
};
transformationCode => {
tce: LONG POINTER TO TransformationCodeEntry ← pointer+offset;
transID: TransID ← InsertTransformation[tce.coefficients, tce.scanConversionType];
SetTransIDCode[transID];
IF transID.codeValue # tce.codeValue THEN ERROR FontCacheInconsistency[$TransformationCodesOutOfSequence, offset];
};
mask => {
maskEntry: LONG POINTER TO MaskEntry ← pointer+offset;
hashIndex: CARDINAL ← HashTableLookup[maskEntry.fontIDCode, maskEntry.transformationCode, maskEntry.charCode];
IF maskEntry.fontIDCode >= fontIDTable.length
OR maskEntry.transformationCode >= transTable.length
THEN FontCacheInconsistency[$MaskWithUndefinedFontOrTransformation, offset];
IF hashIndex # CARDINAL.LAST THEN {
IF hashTable[hashIndex] # 0 THEN
FontCacheInconsistency[$MultiplyDefinedMask, offset];
hashTable[hashIndex] ← offset;
totalUsage ← totalUsage - maskEntry.usage;
};
};
ENDCASE => ERROR FontCacheInconsistency[$BadEntryType, offset];
offset ← offset + prefix.entryLengthInWords;
entries ← entries - 1;
ENDLOOP;
IF offset # words THEN ERROR FontCacheInconsistency[$UnexpectedEndMarker, offset];
IF entries # 0 THEN ERROR FontCacheInconsistency[$WrongNumberOfEntries, offset];
IF totalUsage # 0 THEN ERROR FontCacheInconsistency[$WrongTotalUsage, offset];
};
CVMAllocate: PROC [words: INT] RETURNS [CountedVM.Handle]
~ {RETURN [CountedVM.Allocate[words]]};
AllocateResidentCacheSpace: PROC [minPages: INT] ~ TRUSTED {
This attempts to allocate resident vm to be 26% bigger than minPages.
If it fails to allocate this amount, it decreases its expectations and tries again.
newpages: INT ← MAX[20, (minPages*126+50)/100];
residentPointer ← NIL;
resident ← NIL;
resident ← CVMAllocate[WordsForPages[newpages] ! VM.CantAllocate => {newpages ← MAX[minPages, bestInterval.count]; CONTINUE}];
IF resident = NIL THEN {
SafeStorage.ReclaimCollectibleObjects[];
Process.Pause[Process.MsecToTicks[2000]];
resident ← CVMAllocate[WordsForPages[newpages]];
Let the error through if we still can't get VM.
};
residentPointer ← resident.Pointer;
};
OpenFileAndBuildTables: PROC ~ TRUSTED {
openOK: BOOLEAN ← TRUE;
pages: INT ← 0;
bytes: INT ← 0;
residentPages: INT ← 0;
file ← FS.Open[fontCacheName, $write ! FS.Error => {openOK ← FALSE; CONTINUE}];
IF NOT openOK THEN {
openOK ← TRUE;
CreateNewFile[];
file ← FS.Open[fontCacheName, $write];
};
[pages: pages, bytes: bytes] ← FS.GetInfo[file];
AllocateResidentCacheSpace[pages];
FS.Read[file: file, from: 0, nPages: pages, to: residentPointer];
BuildTables[];
};
Current: PUBLIC PROC [stringBodyDesc: StringBodyDesc] RETURNS [charCode: INT] ~ {
Fet: PROC [i: INT] RETURNS [CARDINAL] ~ {
char: CHAR;
IF i >= stringBodyDesc.start+stringBodyDesc.length THEN RETURN [0];
WITH stringBodyDesc.stringBody SELECT FROM
r: Rope.ROPE => char ← r.Fetch[i];
t: REF TEXT => char ← t[i];
ENDCASE => ERROR;
RETURN [ORD[char]]
};
charCode ← Fet[stringBodyDesc.start];
IF charCode = 255 THEN {
charCode ← Fet[stringBodyDesc.start+1]*256+Fet[stringBodyDesc.start+2];
}
ELSE charCode ← stringBodyDesc.fontSet*256+charCode;
};
Advance: PUBLIC PROC [stringBodyDesc: StringBodyDesc] RETURNS [StringBodyDesc] ~ {
Fet: PROC [i: INT] RETURNS [CARDINAL] ~ {
char: CHAR;
IF i >= stringBodyDesc.start+stringBodyDesc.length THEN RETURN [0];
WITH stringBodyDesc.stringBody SELECT FROM
r: Rope.ROPE => char ← r.Fetch[i];
t: REF TEXT => char ← t[i];
ENDCASE => ERROR;
RETURN [ORD[char]]
};
code: CARDINAL ← Fet[stringBodyDesc.start];
WHILE code = 225 DO
stringBodyDesc.fontSet ← Fet[stringBodyDesc.start+1];
stringBodyDesc.start ← stringBodyDesc.start+2;
stringBodyDesc.length ← stringBodyDesc.length-2;
ENDLOOP;
stringBodyDesc.start ← stringBodyDesc.start+1;
stringBodyDesc.length ← stringBodyDesc.length-1;
RETURN [stringBodyDesc]
};
TrimCache: PUBLIC PROC [maxNumberOfMasks: INT, maxNumberOfWords: INT] ~ {
enabled: PROC ~ TRUSTED {
hdr: LONG POINTER TO Header ← residentPointer;
maxMasks: CARDINAL ← MIN[hdr.numberOfEntries, hashTableSize];
index: CardSeq ← NEW[CardSeqRep[maxMasks]];
GetMaskIndices[index];
SortByUsage[index];
DiscardExcessEntries[index, maxNumberOfMasks, maxNumberOfWords];
DiscardUnusedCodes[index];
WriteNewFile[index];
Disable[];
};
DoEnabled[enabled];
};
CardSeq: TYPE ~ REF CardSeqRep;
CardSeqRep: TYPE ~ RECORD [length: NAT← 0, c: SEQUENCE maxLength: NAT OF LONG CARDINAL];
GetMaskIndices: PROC [index: CardSeq] ~ TRUSTED {
hdr: LONG POINTER TO Header ← residentPointer;
words: INT ← hdr.numberOfWords;
entries: INT ← hdr.numberOfEntries;
offset: INT ← SIZE[Header];
WHILE offset < words DO
prefix: LONG POINTER TO EntryPrefix ← residentPointer+offset;
offset ← offset + SIZE[EntryPrefix];
SELECT prefix.entryType FROM
trailer => EXIT;
mask => {
IF index.length < index.maxLength THEN {
index[index.length] ← offset;
index.length ← index.length + 1;
};
};
ENDCASE => NULL;
offset ← offset + prefix.entryLengthInWords;
entries ← entries - 1;
ENDLOOP;
IF offset # words THEN ERROR FontCacheInconsistency[$UnexpectedEndMarker, offset];
IF entries # 0 THEN ERROR FontCacheInconsistency[$WrongNumberOfEntries, offset];
};
shellD: ARRAY [1..11] OF CARDINAL = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535];
SortByUsage: PROC [index: CardSeq] ~ {
Shell sort
Key: PROC [i: NAT] RETURNS [CARDINAL] ~ TRUSTED {
entry: LONG POINTER TO MaskEntry ← residentPointer+index[i];
RETURN [entry.usage]
};
length: NAT ← index.length;
passes: NAT ← 1;
UNTIL shellD[passes+2] >= index.length DO passes ← passes+1 ENDLOOP;
FOR pass: NAT DECREASING IN [1..passes] DO
h: NAT ← shellD[pass];
FOR i: NAT IN [0..length) DO
key: CARDINAL ← Key[i];
data: LONG CARDINAL ← index[i];
j: NAT ← i;
WHILE j>=h AND key < Key[j-h] DO
index[j] ← index[j-h];
j ← j-h;
ENDLOOP;
index[j] ← data;
ENDLOOP;
ENDLOOP;
};
DiscardExcessEntries: PROC [index: CardSeq, maxNumberOfMasks: INT, maxNumberOfWords: INT] ~ TRUSTED {
n: INT ← 0;
words: INT ← 0;
maxNumberOfMasks ← MIN[maxNumberOfMasks, index.length];
WHILE n < maxNumberOfMasks DO
prefix: LONG POINTER TO EntryPrefix ← residentPointer + index[n] - SIZE[EntryPrefix];
words ← words + SIZE[EntryPrefix] + prefix.entryLengthInWords;
IF words > maxNumberOfWords THEN EXIT;
n ← n + 1;
ENDLOOP;
index.length ← n;
};
DiscardUnusedCodes: PROC [index: CardSeq] ~ TRUSTED {
Abuses the data structures, but only within this proc.
used: CARDINAL ~ 0;
unused: CARDINAL ~ CARDINAL.LAST;
fn, tn: NAT ← 0;
First mark everything as unused.
FOR i: NAT IN [0..fontIDTable.length) DO
fontIDTable[i].codeValue ← unused;
ENDLOOP;
FOR i: NAT IN [0..transTable.length) DO
transTable[i].codeValue ← unused;
ENDLOOP;
Find those that are used.
FOR i: NAT IN [0..index.length) DO
maskEntry: LONG POINTER TO MaskEntry ← residentPointer+index[i];
fontIDTable[maskEntry.fontIDCode].codeValue ← used;
transTable[maskEntry.transformationCode].codeValue ← used;
ENDLOOP;
Give the used ones their new codes.
FOR i: NAT IN [0..fontIDTable.length) DO
IF fontIDTable[i].codeValue = used THEN {fontIDTable[i].codeValue ← fn; fn ← fn+1};
ENDLOOP;
tn ← 0;
FOR i: NAT IN [0..transTable.length) DO
IF transTable[i].codeValue = used THEN {transTable[i].codeValue ← tn; tn ← tn + 1};
ENDLOOP;
Put the new codes in the mask entries.
FOR i: NAT IN [0..index.length) DO
maskEntry: LONG POINTER TO MaskEntry ← residentPointer+index[i];
maskEntry.fontIDCode ← fontIDTable[maskEntry.fontIDCode].codeValue;
maskEntry.transformationCode ← transTable[maskEntry.transformationCode].codeValue;
ENDLOOP;
Shuffle the entries into their rightful places in the table.
FOR i: NAT IN [0..fontIDTable.length) DO
dest: CARDINAL ← fontIDTable[i].codeValue;
IF dest # unused THEN {
s: REF FontIDCodeEntry ← fontIDTable[i];
fontIDTable[i] ← fontIDTable[dest];
fontIDTable[dest] ← s;
};
ENDLOOP;
FOR i: NAT IN [0..transTable.length) DO
dest: CARDINAL ← transTable[i].codeValue;
IF dest # unused THEN {
s: REF TransformationCodeEntry ← transTable[i];
transTable[i] ← transTable[dest];
transTable[dest] ← s;
};
ENDLOOP;
Finally, fix up the lengths.
fontIDTable.length ← fn;
transTable.length ← tn;
};
WriteNewFile: PROC [index: CardSeq] ~ TRUSTED {
header: Header ← [
password: passwordValue,
numberOfEntries: 0,
numberOfWords: SIZE[Header],
totalUsage: 0
];
pointer: LONG POINTER ← @header;
stream: IO.STREAM ← FS.StreamOpen[fontCacheName, $create];
stream.UnsafePutBlock[[base: pointer, startIndex: 0, count: SIZE[Header]*Basics.bytesPerWord]];
header ← PutNamesAndTransformations[stream, header];
header ← CopySelectedMasks[stream, index, header];
stream.PutChar['\000];
stream.PutChar['\000];
header.numberOfWords ← header.numberOfWords + SIZE[CARDINAL];
stream.SetIndex[0];
stream.UnsafePutBlock[[base: pointer, startIndex: 0, count: SIZE[Header]*Basics.bytesPerWord]];
stream.Close;
};
PutNamesAndTransformations: PROC [stream: IO.STREAM, header: Header] RETURNS [Header] ~ TRUSTED {
FOR i: NAT IN [0..fontIDTable.length) DO
f: REF FontIDCodeEntry ← fontIDTable[i];
words: CARDINAL ← SIZE[FontIDCodeEntry[f.chars]];
prefix: EntryPrefix ← [fontIDCode, words];
prefixPtr: LONG POINTER ← @prefix;
stream.UnsafePutBlock[[base: prefixPtr, startIndex: 0, count: SIZE[EntryPrefix]*Basics.bytesPerWord]];
stream.UnsafePutBlock[[base: LOOPHOLE[f], startIndex: 0, count: words*Basics.bytesPerWord]];
header.numberOfEntries ← header.numberOfEntries + 1;
header.numberOfWords ← header.numberOfWords + SIZE[EntryPrefix] + words;
ENDLOOP;
FOR i: NAT IN [0..transTable.length) DO
t: REF TransformationCodeEntry ← transTable[i];
words: CARDINAL ~ SIZE[TransformationCodeEntry];
prefix: EntryPrefix ← [transformationCode, words];
prefixPtr: LONG POINTER ← @prefix;
stream.UnsafePutBlock[[base: prefixPtr, startIndex: 0, count: SIZE[EntryPrefix]*Basics.bytesPerWord]];
stream.UnsafePutBlock[[base: LOOPHOLE[t], startIndex: 0, count: words*Basics.bytesPerWord]];
header.numberOfEntries ← header.numberOfEntries + 1;
header.numberOfWords ← header.numberOfWords + SIZE[EntryPrefix] + words;
ENDLOOP;
RETURN [header]
};
CopySelectedMasks: PROC [stream: IO.STREAM, index: CardSeq, header: Header] RETURNS [Header] ~ TRUSTED {
FOR i: NAT IN [0..index.length) DO
offset: LONG CARDINAL ← index[i];
prefix: LONG POINTER TO EntryPrefix ← residentPointer+offset-SIZE[EntryPrefix];
maskEntry: LONG POINTER TO MaskEntry ← residentPointer+offset;
stream.UnsafePutBlock[[base: LOOPHOLE[prefix], startIndex: 0, count: (SIZE[EntryPrefix] + prefix.entryLengthInWords)*Basics.bytesPerWord]];
header.numberOfEntries ← header.numberOfEntries + 1;
header.numberOfWords ← header.numberOfWords + SIZE[EntryPrefix] + prefix.entryLengthInWords;
header.totalUsage ← header.totalUsage + maskEntry.usage;
ENDLOOP;
RETURN [header]
};
GetListOfContents: PUBLIC PROC RETURNS [list: LIST OF MaskDescriptor ← NIL] ~ {
SeqOfRope: TYPE ~ RECORD[SEQUENCE length: NAT OF ROPE];
n: REF SeqOfRope ← NEW[SeqOfRope[fontIDTable.length]];
cons: PROC [fontID: FontID, transID: TransID, maskDesc: MaskDesc] RETURNS [BOOL ← TRUE] ~ TRUSTED {
entry: LONG POINTER TO MaskEntry ← maskDesc.maskEntryPtr;
IF n[entry.fontIDCode] = NIL THEN n[entry.fontIDCode] ← RopeFromFontID[fontIDTable[entry.fontIDCode]];
list ← CONS[[
name: NARROW[n[entry.fontIDCode]],
transID: transID,
usage: entry.usage,
set: entry.charCode/256,
c: VAL[Basics.LowHalf[entry.charCode] MOD 256]
], list];
};
Enumerate[cons];
};
Enumerate: PUBLIC PROC [action: PROC [FontID, TransID, MaskDesc] RETURNS [continue: BOOL]] ~ {
Enumerate: PROC ~ TRUSTED {
hdr: LONG POINTER TO Header ← residentPointer;
words: INT ← hdr.numberOfWords;
entries: INT ← hdr.numberOfEntries;
offset: INT ← SIZE[Header];
running: BOOLEAN ← TRUE;
WHILE running AND offset < words DO
prefix: LONG POINTER TO EntryPrefix ← residentPointer+offset;
offset ← offset + SIZE[EntryPrefix];
SELECT prefix.entryType FROM
trailer => EXIT;
mask => {
entry: LONG POINTER TO MaskEntry ← residentPointer+offset;
running ← action[fontIDTable[entry.fontIDCode], transTable[entry.transformationCode], [resident, entry]];
};
ENDCASE => NULL;
offset ← offset + prefix.entryLengthInWords;
entries ← entries - 1;
ENDLOOP;
};
DoReadOnlyOrEnabled[Enumerate];
};
SetMaskUsage: PUBLIC PROC [fontID: FontID, transID: TransID, charCode: INT, usage: CARDINAL] ~ {
Proc: PROC ~ TRUSTED {
maskDesc: MaskDesc ← GetMask[fontID, transID, charCode];
IF maskDesc.maskEntryPtr # NIL THEN {
hdr: LONG POINTER TO Header ← residentPointer;
hdr.totalUsage ← hdr.totalUsage - maskDesc.maskEntryPtr.usage + usage;
maskDesc.maskEntryPtr.usage ← usage;
IF usage = CARDINAL.LAST THEN AgeUseCounts[];
};
};
DoReadOnlyOrEnabled[Proc];
};
showHash: BOOLEAN ← FALSE;
ShowHash: PROC ~ TRUSTED {
showHash ← TRUE;
Process.Detach[FORK ShowHashProcess[]];
};
ShowHashProcess: PROC ~ TRUSTED {
pm: ImagerPixelMap.PixelMap ← ImagerPixelMap.Create[0, [808-64, 256, 64, 512]];
display: ImagerPixelMap.PixelMap ← ImagerFrameBuffer.LFDisplay[];
b: LONG POINTER TO PACKED ARRAY [0..32767] OF [0..1] ← pm.refRep.pointer;
WHILE showHash DO
Process.Pause[Process.MsecToTicks[500]];
pm.Clear;
FOR i: NAT IN [0..hashTableSize) DO
IF hashTable[i] > 0 THEN b[i] ← 1;
ENDLOOP;
display.Transfer[pm];
ENDLOOP;
};
END.