bson@rice-chex.ai.mit.edu (Jan Brittenson) (10/31/90)
Here is a simple string hashing program. It takes a string as an argument; it returns in level 2 the string with its first character incremented, and in level 1 a short integer hash value. It doesn't check for an empty stack, or that the argument actually is a string. Be careful - embed it suitably. It's an additive version of the XOR (for lack of a Saturn XOR instruction) algorithm described in the June 1990 issue of CACM (Peter Pearson: _Fast Hashing Of Variable-Length Text Strings_). The incrementation of the first character aids in computing larger hash values. Load the hex data and convert it with ASC->. %%HP: T(3)A(R)F(.); "CCD2057200D6061438FB97608FCC021D88A82414BB64149808240700007CA130 D014F171A6A136134A64C213614A136CD8ADED81AF008F2D7608DA0D8101F797 49683FD91D55A52630F2659859C5564876A7DFFB3736898290FC6270E469CDE6 E70679575F735E6EFAB4AABCF5CBDA78630442B2ED15C0D4EF67DE8774D738C8 E8B0B82F8E358D40D25A524ABDF6CE7FDD7CCCBA4521B13C71E1C7ADF93D9408 5092F46124D0B79DC40D29BB519554105C6B33DC9319DBCA2EEE66A90F169B6F C2FF7A1C9AA2CF1F7EC63AB3AE1B9F6CA044C11EC9B903D69EE36460750BEAFD E0224641200C05F3A1112C1AEB72278FA4533EE228F10A8458835BF0C3D8BFD5 43E59907EC5D2A7B8C806AAB8BF86DFE9100BE394B77D32B9614E902174C0E4D A812478588134F4E238A3B818631AFD1A3AC0932252D9C7D1834B5A6B6F906" Store it in 'HASH'. A simple example: \<< "" + HASH # 60F9Bh SYSEVAL @ Drop level 2 # 18DBFh SYSEVAL @ Short to real \>> Null strings always yield 0. And, finally, the source code, ASAP style. O / \/ /\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ O \ ;;+ ;; HASH -- Hash string ;; ;; Synopsis: ;; Hash string in level 1. Return string with first character ;; incremented in level 2. Return hash value in level 1. ;; ;; bson@ai.mit.edu, Oct 31, 1990 ;; ;;- save_regs=#679b restore_regs=#67d2 strlen_a=#120cc shortpush_r0_rplret=#18d0a ; Std.preamble data.b 'H' data.b 'P' data.b 'H' data.b 'P' data.b '4' data.b '8' data.b '-' data.b 'D' data.a #2dcc begin: data.a end-begin ; Enter here hash: move.a a,c push.a c move.a @d1,a call.a save_regs call.a strlen_a move.a a,b ; B = length of string in bytes brz.a a,hash_exit move.b @d1,a ; Increment the first char inc.b a move.b a,@d1 move.p5 hash_table,a ; Set D0 to table start pop.a c add.a c,a move.a a,d0 clr.a a ; Start with 0 hash value hash_loop: move.b @d1,c ; Next char add.a 2,d1 add.b c,a ; Add to prev hash value swap.a c,d0 move.a c,d0 add.b a,a add.a a,c swap.a c,d0 ; D0 = 2*char+table move.b @d0,a ; Get new hash value from table swap.a c,d0 dec.a b ; Loop chars brnz.a b,hash_loop hash_exit: move.a a,r0 call.a restore_regs jump.a shortpush_r0_rplret ; Random permutations of 00-ff dummy: hash_table=dummy-hash data.b #10 data.b #7f data.b #79 data.b #94 data.b #86 data.b #f3 data.b #9d data.b #d1 data.b #55 data.b #5a data.b #62 data.b #3 data.b #2f data.b #56 data.b #89 data.b #95 data.b #5c data.b #65 data.b #84 data.b #67 data.b #7a data.b #fd data.b #bf data.b #73 data.b #63 data.b #98 data.b #28 data.b #9 data.b #cf data.b #26 data.b #7 data.b #4e data.b #96 data.b #dc data.b #6e data.b #7e data.b #60 data.b #97 data.b #75 data.b #f5 data.b #37 data.b #e5 data.b #e6 data.b #af data.b #4b data.b #aa data.b #cb data.b #5f data.b #bc data.b #ad data.b #87 data.b #36 data.b #40 data.b #24 data.b #2b data.b #de data.b #51 data.b #c data.b #4d data.b #fe data.b #76 data.b #ed data.b #78 data.b #47 data.b #7d data.b #83 data.b #8c data.b #8e data.b #b data.b #8b data.b #f2 data.b #e8 data.b #53 data.b #d8 data.b #4 data.b #2d data.b #a5 data.b #25 data.b #a4 data.b #db data.b #6f data.b #ec data.b #f7 data.b #dd data.b #c7 data.b #cc data.b #ab data.b #54 data.b #12 data.b #1b data.b #c3 data.b #17 data.b #1e data.b #7c data.b #da data.b #9f data.b #d3 data.b #49 data.b #80 data.b #5 data.b #29 data.b #4f data.b #16 data.b #42 data.b #d data.b #7b data.b #d9 data.b #4c data.b #d0 data.b #92 data.b #bb data.b #15 data.b #59 data.b #45 data.b #1 data.b #c5 data.b #b6 data.b #33 data.b #cd data.b #39 data.b #91 data.b #bd data.b #ac data.b #e2 data.b #ee data.b #66 data.b #9a data.b #f0 data.b #61 data.b #b9 data.b #f6 data.b #2c data.b #ff data.b #a7 data.b #c1 data.b #a9 data.b #2a data.b #fc data.b #f1 data.b #e7 data.b #6c data.b #a3 data.b #3b data.b #ea data.b #b1 data.b #f9 data.b #c6 data.b #a data.b #44 data.b #1c data.b #e1 data.b #9c data.b #9b data.b #30 data.b #6d data.b #e9 data.b #3e data.b #46 data.b #6 data.b #57 data.b #b0 data.b #ae data.b #df data.b #e data.b #22 data.b #64 data.b #14 data.b #2 data.b #c0 data.b #50 data.b #3f data.b #1a data.b #11 data.b #c2 data.b #a1 data.b #be data.b #27 data.b #72 data.b #f8 data.b #4a data.b #35 data.b #e3 data.b #2e data.b #82 data.b #1f data.b #a0 data.b #48 data.b #85 data.b #38 data.b #b5 data.b #f data.b #3c data.b #8d data.b #fb data.b #5d data.b #34 data.b #5e data.b #99 data.b #70 data.b #ce data.b #d5 data.b #a2 data.b #b7 data.b #c8 data.b #8 data.b #a6 data.b #ba data.b #b8 data.b #8f data.b #d6 data.b #ef data.b #19 data.b #0 data.b #eb data.b #93 data.b #b4 data.b #77 data.b #3d data.b #b2 data.b #69 data.b #41 data.b #9e data.b #20 data.b #71 data.b #c4 data.b #e0 data.b #d4 data.b #8a data.b #21 data.b #74 data.b #58 data.b #88 data.b #31 data.b #f4 data.b #e4 data.b #32 data.b #a8 data.b #b3 data.b #18 data.b #68 data.b #13 data.b #fa data.b #1d data.b #3a data.b #ca data.b #90 data.b #23 data.b #52 data.b #d2 data.b #c9 data.b #d7 data.b #81 data.b #43 data.b #5b data.b #6a data.b #6b end:
grue@batserver.cs.uq.oz.au (Frobozz) (11/15/90)
bson@rice-chex.ai.mit.edu (Jan Brittenson) writes: > Here is a simple string hashing program. It takes a string as an >argument; it returns in level 2 the string with its first character >incremented, and in level 1 a short integer hash value. It doesn't >check for an empty stack, or that the argument actually is a string. >Be careful - embed it suitably. It's an additive version of the XOR >(for lack of a Saturn XOR instruction) algorithm described in the June >1990 issue of CACM (Peter Pearson: _Fast Hashing Of Variable-Length >Text Strings_). What is wrong with using the built in function BYTES as a hashing function? It calculates some kind of CRC on the thing that is passed to it and it is rather fast. Pauli seeya Paul Dale | Internet/CSnet: grue@batserver.cs.uq.oz.au Dept of Computer Science| Bitnet: grue%batserver.cs.uq.oz.au@uunet.uu.net Uni of Qld | JANET: grue%batserver.cs.uq.oz.au@uk.ac.ukc Australia, 4072 | EAN: grue@batserver.cs.uq.oz | UUCP: uunet!munnari!batserver.cs.uq.oz!grue f4e6g4Qh4++ | JUNET: grue@batserver.cs.uq.oz.au --
cloos@acsu.buffalo.edu (James H. Cloos) (11/15/90)
In article <5699@uqcspe.cs.uq.oz.au> grue@batserver.cs.uq.oz.au writes: >What is wrong with using the built in function BYTES as a hashing function? >It calculates some kind of CRC on the thing that is passed to it and it >is rather fast. The algorithm BYTES uses (though no the actual code!) was posted by me a while back. The algorithm is the same one used by Kermit. See the file kcrc.48 in wuarchive.wustl.edu. It may exist other places, too. -JimC -- James H. Cloos, Jr. Phone: +1 716 673-1250 cloos@ACSU.Buffalo.EDU Snail: PersonalZipCode: 14048-0772, USA cloos@ub.UUCP Quote: <>