RopeHashImpl.mesa
Copyright (C) 1984, 1985 Xerox Corporation. All rights reserved.
Michael Plass, January 18, 1985 12:48:44 pm PST
Russ Atkinson (RRA) May 15, 1985 2:38:58 pm PDT
DIRECTORY
Basics USING [bytesPerWord],
Checksum USING [ComputeChecksum],
Rope,
RopePrivate,
RopeHash USING [PureText],
RefText USING [ObtainScratch, ReleaseScratch];
RopeHashImpl:
CEDAR PROGRAM
IMPORTS Checksum, Rope, RopePrivate, RefText
EXPORTS RopeHash
SHARES Rope
ROPE: TYPE = Rope.ROPE;
Text: TYPE = Rope.Text;
defaultSeed: CARDINAL = 31415;
bytesPerWord: NAT = Basics.bytesPerWord;
bufSize: NAT = 128*bytesPerWord;
TextSize: NAT = SIZE[TEXT[0]];
WordAsChars:
TYPE =
PACKED
ARRAY [0..bytesPerWord)
OF
CHAR;
FromRefText:
PUBLIC
PROC [text: PureText, seed:
CARDINAL]
RETURNS [hash:
CARDINAL] =
TRUSTED {
len: NAT ← text.length;
nLeft: NAT = len MOD bytesPerWord;
nWhole: NAT = len - nLeft;
p: LONG POINTER = LOOPHOLE[text, LONG POINTER] + TextSize;
hash ← seed;
IF nWhole >= bytesPerWord
THEN {
hash ← Checksum.ComputeChecksum[hash, nWhole/bytesPerWord, p];
};
IF nLeft # 0
THEN
TRUSTED {
leftovers: WordAsChars ← ALL[0C];
FOR j:
NAT
IN [0..nLeft)
DO
leftovers[j] ← Rope.QFetch[LOOPHOLE[text], nWhole+j];
ENDLOOP;
hash ← Checksum.ComputeChecksum[hash, SIZE[WordAsChars], @leftovers];
};
};
FromRope:
PUBLIC
PROC [rope:
ROPE, case:
BOOL, start:
INT, len:
INT, seed:
CARDINAL]
RETURNS [hash:
CARDINAL] =
TRUSTED {
rem: INT ← RopePrivate.NonNeg[Rope.InlineLength[rope] - RopePrivate.NonNeg[start]];
IF rem < len
THEN len ← rem;
Limit len to be at worst the remainder of the string
IF case
AND start = 0
AND rem = len
THEN
WITH rope
SELECT
FROM
text: Text =>
If case does not matter, and we have a flat rope, and the whole rope is to be hashed, then we have the fast case.
RETURN[FromRefText[LOOPHOLE[text], seed]];
ENDCASE;
{
In the hard case we have to move the bytes from the rope into a buffer, adjust the buffer for lower case, then perform the checksum on the buffer. We keep doing this until there are no more chars to be moved.
buf: REF TEXT ← RefText.ObtainScratch[bufSize];
p: LONG POINTER = LOOPHOLE[buf, LONG POINTER] + SIZE[TEXT[0]];
bytes: NAT ← 0;
hash ← seed;
WHILE rem > 0
DO
buf.length ← 0;
bytes ← Rope.AppendChars[buf, rope, start, rem];
IF
NOT case
THEN
Make the buffer lower case. We avoid bounds checking to speed things up.
FOR i:
NAT
IN [0..bytes)
DO
c: CHAR = Rope.QFetch[LOOPHOLE[buf], i];
IF c <= 'Z AND c >= 'A THEN RopePrivate.QStore[c + ('a-'A), LOOPHOLE[buf], i];
ENDLOOP;
hash ← FromRefText[buf, hash];
start ← start + bytes;
rem ← rem - bytes;
ENDLOOP;
RefText.ReleaseScratch[buf];
RETURN [hash];
};
};
END.