BitTableLookupImpl.mesa
Copyright Ó 1985, 1990, 1992 by Xerox Corporation. All rights reserved.
Bob Nix, October 27, 1983 1:23 pm
Rick Beach, May 2, 1985 3:05:07 pm PDT
Last Edited by: Gasbarro October 11, 1985 5:10:13 pm PDT
Kenneth A. Pier, March 9, 1990 4:54 pm PST
Willie-s, May 22, 1992 2:36 pm PDT
BitTableLookupImpl:
CEDAR
PROGRAM
IMPORTS Ascii, Basics, IO, Rope, RefText
EXPORTS BitTableLookup
-- SHARES Rope
= BEGIN
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
Table: TYPE = BitTableLookup.Table;
TableContents: TYPE = BitTableLookup.TableContents;
RowContents: TYPE = BitTableLookup.RowContents;
RowPointer: TYPE = BitTableLookup.RowPointer;
maxTableSize:
INT ¬ 268238848;
Current implementation restrictions impose this bound on the maximum size of a bit table. The given size should suffice for tables representing a set of about 14,000,000 words.
IAmNotACrook:
INT = 2789127;
This magic number is written at the beginning and end of every bit table written to a stream, and its presence is checked whenever a table is read.
Failed: PUBLIC ERROR[why: BitTableLookup.FailureTypes] = CODE;
Read:
PUBLIC
PROC [ in:
STREAM ]
RETURNS [ table: Table ] =
TRUSTED {
Reads in a Table from the given stream. One had better be there.
bytesPerRow: INT ~ BYTES[RowContents];
bytesPerINT: INT ~ BYTES[INT];
doWeBelieveHim: Basics.LongNumber;
nRows: CARDINAL ¬ 0;
ACrookIAmNot: Basics.LongNumber ¬ SwapHalves[[li[IAmNotACrook]]];
IF IO.UnsafeGetBlock[in, [LOOPHOLE[LONG[@doWeBelieveHim]], 0, bytesPerINT]] # bytesPerINT THEN ERROR Failed[BadTable];
IF doWeBelieveHim # ACrookIAmNot THEN ERROR Failed[BadTable];
nRows ¬ 256*IO.GetByte[in];
nRows ¬ nRows + IO.GetByte[in];
table ¬ NEW[TableContents[nRows]];
FOR i:
CARDINAL
IN [0..nRows)
DO
table.bits[i] ¬ NEW[RowContents];
IF
IO.UnsafeGetBlock[in, [
LOOPHOLE[table.bits[i]], 0, bytesPerRow]] # bytesPerRow
THEN
Failed[BadTable];
ENDLOOP;
IF
IO.UnsafeGetBlock[ in, [
LOOPHOLE[
LONG[@doWeBelieveHim]], 0, bytesPerINT]] # bytesPerINT
THEN
ERROR Failed[BadTable];
IF doWeBelieveHim # ACrookIAmNot THEN ERROR Failed[BadTable];
};
SwapHalves:
PROC[ln: Basics.LongNumber]
RETURNS[nl: Basics.LongNumber] ~ {
nl.lo ¬ ln.hi;
nl.hi ¬ ln.lo;
};
Write:
PUBLIC
PROC [ table: Table, out:
STREAM ] =
TRUSTED {
Writes out a Table to the given stream.
sanity: BOOL[TRUE..TRUE] ~ BYTES[INT]=4; -- compile-time check
sanityC: BOOL[TRUE..TRUE] ~ BYTES[CARD16]=2; -- compile-time check
validationStamp: Basics.LongNumber ¬ SwapHalves[[li[IAmNotACrook]]];
s: INT;
nRows: CARDINAL ¬ table.rowSize;
IO.UnsafePutBlock[ out, [LOOPHOLE[LONG[@validationStamp]], 0, BYTES[INT] ]];
IO.PutFWord[out, LOOPHOLE[validationStamp] ];
IO.PutByte[ out, nRows / 256];
IO.PutByte[ out, nRows MOD 256];
s ¬ BYTES[RowContents];
FOR i:
CARDINAL
IN [0..nRows)
DO
IO.UnsafePutBlock[out, [LOOPHOLE[table.bits[i]], 0, s]];
ENDLOOP;
IO.PutFWord[out, LOOPHOLE[validationStamp] ];
};
Insert:
PUBLIC
PROC [table: Table, word:
REF
TEXT] = {
Inserts the word into the given table.
[] ¬ InsertOrLookup[ table, word, FALSE ];
};
Lookup:
PUBLIC
PROC [table: Table, word:
REF
TEXT]
RETURNS [member:
BOOLEAN] = {
Looks up the word in the table and returns TRUE iff it thinks that the word is in there.
member ¬ InsertOrLookup[ table, word, TRUE ];
};
CharTable:
ARRAY [0..26)
OF
CARDINAL = [
a b c d
e f g h
i j
0FF2DH, --[-211]-- 0FEB4H, --[-332]-- 449, 588,
7102, 0FCAAH, --[-854]-- 0FC21H, --[-991]-- 0FBA2H,--[-1118]--
1278, 1433,
k l m n
o p q r
s t
0F9E0H, --[-1568]-- 0F953H, --[-1709]-- 1874, 2027,
2180, 0F6DBH, --[-2341]-- 0F652H, --[-2478]-- 0F591H, --[-2671]--
2798, 2963,
u v w x
y z
0F3A4H, --[-3164]-- 0F308H, --[-3320]-- 0F273H, --[-3469]-- 3624,
3793, 3944
];
NumberHashFunctions:
PUBLIC
PROC []
RETURNS [numberHashFunctions:
INT] = {
numberHashFunctions ¬ 7;
};
InsertOrLookup:
PROC [table: Table, word:
REF
TEXT, lookup:
BOOLEAN ]
RETURNS [member:
BOOLEAN ¬
FALSE] =
TRUSTED {
M:
PROC[n, m:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (n - m) MOD bit16;
};
P:
PROC[n, m:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (n - m) MOD bit16;
};
R:
PROC[n, m:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (m - n) MOD bit16;
};
X:
PROC[n, m:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ Basics.BITXOR[n,m];
};
R1:
PROC[n:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (IF n >= 100000B THEN n*2+1 ELSE n*2) MOD bit16;
};
R3:
PROC[n:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (n*8+n/20000B) MOD bit16;
};
R5:
PROC[n:
CARDINAL]
RETURNS [r:
CARDINAL] =
TRUSTED {
r ¬ (n*32+n/4000B) MOD bit16;
};
Word:
PROC[n:
CARDINAL]
RETURNS [wordOffset:
CARDINAL] =
TRUSTED
INLINE {
wordOffset ¬ n MOD table.rowSize;
};
Bit:
PROC[n:
CARDINAL]
RETURNS [bitNum:
CARDINAL] =
TRUSTED
INLINE {
bitNum ¬ n MOD BitTableLookup.RowPrime;
};
char: CHAR;
c, p: CARDINAL;
hash1, hash2, hash3, hash4, hash5, hash6, hash7: CARDINAL;
x1, x2, x3, x4, x5, x6, x7: CARDINAL;
hash1 ¬ LOOPHOLE[953];
hash2 ¬ LOOPHOLE[0F97DH]; -- -1667
hash3 ¬ LOOPHOLE[2441];
hash4 ¬ LOOPHOLE[0F339H]; -- -3271
hash5 ¬ LOOPHOLE[4079];
hash6 ¬ LOOPHOLE[0ECA9H]; -- -4951
hash7 ¬ LOOPHOLE[5807];
p ¬ 359;
FOR j:
CARDINAL
IN [0..word.length)
DO
char ¬ Ascii.Lower[Rope.Fetch[RefText.TrustTextAsRope[word], j]];
IF char
IN ['a..'z]
THEN
c ¬ CharTable[char - 'a]
p ¬ p + 1009;
x1 ¬ M[ X[ R5[hash2], c], p];
x2 ¬ R[ M[ R3[hash3], c], p];
x3 ¬ X[ P[ R5[hash4], c], p];
x4 ¬ P[ R[ R3[hash5], c], p];
x5 ¬ P[ X[ R5[hash6], c], p];
x6 ¬ M[ M[ R3[hash7], c], p];
x7 ¬ R[ P[ R5[hash1], c], p];
hash1 ¬ x1;
hash2 ¬ x2;
hash3 ¬ x3;
hash4 ¬ x4;
hash5 ¬ x5;
hash6 ¬ x6;
hash7 ¬ x7;
ENDLOOP;
IF lookup
THEN {
IF ~table.bits[LOOPHOLE[Word[hash1]]][Bit[hash7]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash2]]][Bit[hash6]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash3]]][Bit[hash5]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash4]]][Bit[hash4]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash5]]][Bit[hash3]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash6]]][Bit[hash2]] THEN RETURN;
IF ~table.bits[LOOPHOLE[Word[hash7]]][Bit[hash1]] THEN RETURN;
}
ELSE {
table.bits[LOOPHOLE[Word[hash1]]][Bit[hash7]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash2]]][Bit[hash6]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash3]]][Bit[hash5]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash4]]][Bit[hash4]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash5]]][Bit[hash3]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash6]]][Bit[hash2]] ¬ TRUE;
table.bits[LOOPHOLE[Word[hash7]]][Bit[hash1]] ¬ TRUE;
};
member ¬ TRUE;
};