
DIRECTORY
Ascii,
Basics,
IO,
RefText,
Rope,
BitTableLookup;

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;
IAmNotACrook: INT = 2789127;
Failed: PUBLIC ERROR[why: BitTableLookup.FailureTypes] = CODE;

Read: PUBLIC PROC [ in: STREAM ] RETURNS [ table: Table ] = TRUSTED {
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 {
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.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] = {
[] м InsertOrLookup[ table, word, FALSE ];
};


Lookup: PUBLIC PROC [table: Table, word: REF TEXT] RETURNS [member: BOOLEAN] = {
member м InsertOrLookup[ table, word, TRUE ];
};

CharTable: ARRAY [0..26) OF CARDINAL = [
0FF2DH, --[-211]--	0FEB4H, --[-332]--	449,		588,
7102,		0FCAAH, --[-854]--	0FC21H, --[-991]-- 0FBA2H,--[-1118]--
1278,		1433,
0F9E0H, --[-1568]--	0F953H, --[-1709]--	1874,		2027,
2180,		0F6DBH, --[-2341]--	0F652H, --[-2478]-- 0F591H, --[-2671]--
2798,		2963,
0F3A4H, --[-3164]--	0F308H, --[-3320]--	0F273H, --[-3469]--	3624,
3793,	3944
];


NumberHashFunctions: PUBLIC PROC [] RETURNS [numberHashFunctions: INT] = {
numberHashFunctions м 7;
};


bit16: CARD = 10000H;

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]
ELSE
c м char - 0C;
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;
};

END.

CHANGE LOG

Created by Nix on May 2, 1985 3:05:08 pm PDT
, BitTableLookupImpl, IMPORTS, EXPORTS, SHARES, =, BitToRow, Create, Write, Insert, Lookup, NumberHashFunctions, InsertOrLookup, M (local of InsertOrLookup), P (local of InsertOrLookup), R (local of InsertOrLookup), X (local of InsertOrLookup), R1 (local of InsertOrLookup), R3 (local of InsertOrLookup), R5 (local of InsertOrLookup), Word (local of InsertOrLookup), Bit (local of InsertOrLookup), END, CHANGE, Created


      
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
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.

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. 

Reads in a Table from the given stream.  One had better be there.
Writes out a Table to the given stream.
IO.UnsafePutBlock[ out, [LOOPHOLE[LONG[@validationStamp]], 0, BYTES[INT] ]];
Inserts the word into the given table.
Looks up the word in the table and returns TRUE iff it thinks that the word is in there.
a		b		c		d
e		f		g		h
i		j
k		l		m		n
o		p		q		r
s		t
u		v		w		x
y		z

 Э╩	ы  ХNewlineDelimiter
Ц(cedarcode) styleЩ codeЪЬЩKЪЬ
╧eЬ=ЩHKЪЬ!Щ!KЩ&KЩ8KЩ*KЩ"ЧKШ Ъ╧k	Ш	KЪЬШKШKЪЮЬШKЪЬШKЪЬШKЪЬШЧKШ Ъ╨lnЬЮЬЮШ!KЪЮЬЮЬШ(KЪЮЬШKЪЮ	ЬШKЪЬЮШKШ KЪЮЬЮЬЮЬШKЪЮЬЮЬЮЬЮЬШKЪЬЮЬШ#KЪЬЮЬ Ш3KЪЬЮЬШ/KЪЬЮЬШ-KШ ЪЬЮЬШKЩ▓ЧЪЬЮЬШKЪЬФЩФKЩ ЧKЪЬЮЬЮЬ%ЮЬШ?Ъ╧nЬЮЬЮЬЮЬЮЬЮЬШEKЪЬAЩAKЪЬЮЬЮЬШ&KЪЬЮЬЮЬЮЬШKЪЬ#Ш#KЪЬЮЬШKЪаЬ5ШAKШ KЪ
ЮЬЮЬЮЬЮЬ3Ю
ЬШvKЪЮЬЮЬЮЬШ=KШ KЪЬЮЬШKЪЬЮЬШKЪЬЮЬШ"ЪЮЬЮЬЮЬЮШ KЪЬЮЬШ!ЪЮЬЮЬЮЬ0ЮШVKЪЬШЧKЪЮЬШЧЪ	ЮЬЮЬЮЬЮЬ3ЮШ_KЪЮЬШЧKЪЮЬЮЬЮЬШ=KШKШ ЧЪа
ЬЮЬЮЬШJKШKШKШKШ ЧЪ
аЬЮЬЮЬЮЬЮЬШ<KЪЬ'Щ'KЪЬЮЬЮЬЮЬЮЬЮЬ╧cШ>KЪЬ	ЮЬЮЬЮЬЮЬЮЬбШBKШDKЪЬЮЬШKЪЬЮЬШ KЪ
ЮЬЮЬЮЬЮЬЮЬЩLKЪЮЬЮЬШ-KЪЮЬШKЪЮЬЮЬШ KЪЬЮЬШЪЮЬЮЬЮЬЮШ KЪЮЬЮЬШ9KЪЮЬШЧKЪЮЬЮЬШ-KЪЬШKШ ЧKШ Ъ
аЬЮЬЮЬЮЬЮЬШ6KЪЬ&Щ&KЪЬ"ЮЬШ*KШЧKШ KШ ЪаЬЮЬЮЬЮЬЮЬЮЬ
ЮЬШPKЪЬXЩXKЪЬ&ЮЬШ-KШKШ ЧЪ╨fn	╧f╨fkг	дгдгШ(KЪг
Щ
KЪг
Щ
KЪгЩKЪдг╨cf
гдЬгебегЬ
Ш0KЪгдге
гдге
гдгеШ?KЪгШKЪг
Щ
KЪг
Щ
KЪгЩKЪдгегдгегШ4KЪгдгегЮдгегЮгеШBKЪгШKЪг
Щ
KЪгЩKЪЮгегЮгегЮгегШAKЪг
Ш
KЪгШKШ KШ ЧЪ
╨bnЬЮЬЮЬЮЬЮЬШJKШKШKШ ЧKШ ЪЬЮЬ
ШKШ ЧЪаЬЮЬЮЬЮЬ
ЮЬЮЬ
ЮЬЮЬЮЬШsЪжЬЮЬЮЬЮЬЮЬЮЬШ:KЪЬЮЬШKШЧЪ╨bkЬЮЬЮЬЮЬЮЬЮЬШ:KЪЬЮЬШKШЧЪзЬЮЬЮЬЮЬЮЬЮЬШ:KЪЬЮЬШKШЧЪзЬЮЬЮЬЮЬЮЬЮЬШ:KЪЬЮЬШKШЧЪаЬЮЬЮЬЮЬЮЬЮЬШ8KЪ	ЬЮЬЮЬЮЬЮЬШ4KШЧЪаЬЮЬЮЬЮЬЮЬЮЬШ8KЪЬЮЬШKШЧЪаЬЮЬЮЬЮЬЮЬЮЬШ8KЪЬЮЬШKШЧЪаЬЮЬЮЬЮЬЮЬЮЬЮЬШIKЪЬЮЬШ!KШЧЪаЬЮЬЮЬЮЬ
ЮЬЮЬЮЬШDKЪЬЮЬШ'KШЧKЪЬЮЬШKЪЬЮЬШKЪЬ1ЮЬШ:KЪЬЮЬШ&KЪЬЮЬШKЪЬЮЬШ#KЪЬЮЬШKЪЬЮЬШ#KЪЬЮЬШKЪЬЮЬШ#KЪЬЮЬШKШЪЮЬЮЬЮЬЮШ&KШAЪЮЬЮЬ
ЮШKШЧЪЮШKШЧKШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKЪЬЮЬЮЬШKШKШKШKШKШKШKШKЪЮЬШЧЪЮЬЮЬШKЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KЪЮЬЮЬЮЬЮЬШ>KШЧЪЮЬШKЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KЪЬЮЬЮЬШ5KШЧKЪЬ	ЮЬШKШЧЧKШ KЪЮЬШKШ KЪЮЬЮШ
KШ KЪЬ-╧rВЬиЬиЬиЬиЬиЬиЬиЬиЬиШ╧KШ KЩ KШ Ч ЕЧ    Ь  %З  