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