TinTin++ Mud Client The TinTin++ message board

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 
TinTin++ Mud Client

Hashing function in tintin

 
Post new topic   Reply to topic    The TinTin++ message board Forum Index -> Script Help
View previous topic :: View next topic  
Author Message
perlsaiyan



Joined: 21 Sep 2014
Posts: 26

PostPosted: Sun Jan 04, 2015 11:34 am    Post subject: Hashing function in tintin Reply with quote

Has anyone worked out a fast/cheap (CPU-wise) hashing function for arbitrary strings, and feel like sharing some code? I'd like it to be pure tin script (does this language have a name?) and as fast as possible Smile

I'd like to end up with a string suitable for using as a key in a data structure, preferably a hash of both room name and description (which I capture and could concatenate together.
Back to top
View user's profile Send private message
Slysven



Joined: 10 Apr 2011
Posts: 369
Location: As "Jomin al'Bara" in WoTMUD or Wiltshire, UK

PostPosted: Sun Jan 04, 2015 12:35 pm    Post subject: Reply with quote

Well I did something similar before I produced a patch to hash non-empty room descriptions for a MUD which does (did, WoTMUD - it has been off-line since early 2014 though it says it is coming back) not divulge information such as room vnumb to mortal players. I hashed the description into 2^16 (64K) bins so that I could search quickly for a combination of room name and description. It uses the apparently not currently documented %A argument to #FORMAT to return the ASCII character value of the first character in the string and multiplied that by the character position in the string before adding it to a running total moduli-ed to the given range.

Note that I choose 2^16 as a hash range because I thought that would be a reasonable size for MUDs that had tens of thousands of rooms with mostly different descriptions, and at the end I process the value into a 4 hex digit string which I intended to pass with the room name to other players on the MUD who did not necessarily have the same Map (so no common vnumbs) or even the same Client. Though calculation of the hash was not too intensive I needed to provide an indexing system within the TinTin++ code base to provide the lookup so it was easier in practice to also provide the hashing calculation in C code as well. One gotcha to be wary of is how end-of-line characters are stored in a room description variable, are they '\n' i.e. ASCII character 13 or "\n" the backslash character followed by lower case 'n', the answer to that can vary and will alter the results here...!

Code:
#ALIAS        {mkhash %1}
{
   #nop description_hashing;
   #if {"%1"==""}
   {
      #echo {Usage: mkhash {full multi-line room description} - result is stored in \$result};
      return ""
   };
   #variable mkhash_result 0;
   #variable mkhash_index 0;
   #parse {%1} {mkhash_char}
   {
      #math {mkhash_index} ${mkhash_index}+1;
      #format {mkhash_code} {%A} {$mkhash_char};
      #math {mkhash_result} (${mkhash_result}+(${mkhash_code}*${mkhash_index}))%%65536
   };
   #math mkhash_return[0] ${mkhash_result}%%16;
   #math {mkhash_result} (${mkhash_result}-${mkhash_return[0]})/16;
   #math mkhash_return[1] ${mkhash_result}%%16;
   #math {mkhash_result} (${mkhash_result}-${mkhash_return[1]})/16;
   #math mkhash_return[2] ${mkhash_result}%%16;
   #math {mkhash_result} (${mkhash_result}-${mkhash_return[2]})/16;
   #math mkhash_return[3] ${mkhash_result}%%16;
   #loop {0} {3} {mkhash_nibble}
   {
      #switch {$mkhash_return[$mkhash_nibble]}
      {
         #case {10}
         {
            #variable mkhash_return[$mkhash_nibble] a
         };
         #case {11}
         {
            #variable mkhash_return[$mkhash_nibble] b
         };
         #case {12}
         {
            #variable mkhash_return[$mkhash_nibble] c
         };
         #case {13}
         {
            #variable mkhash_return[$mkhash_nibble] d
         };
         #case {14}
         {
            #variable mkhash_return[$mkhash_nibble] e
         };
         #case {15}
         {
            #variable mkhash_return[$mkhash_nibble] f
         }
      }
   };
   #variable result ${mkhash_return[3]}${mkhash_return[2]}${mkhash_return[1]}${mkhash_return[0]};
   #unvariable mkhash_%*;
   #return ${result}
}
{5}


For the patch you will find it here but it was against 2.00.9 so may need tweaking to apply against the current TinTin++ codebase. It is released under the same terms as TinTin++ which was GPL versiopn 2 or (at your option) any later version.
Back to top
View user's profile Send private message
perlsaiyan



Joined: 21 Sep 2014
Posts: 26

PostPosted: Mon Jan 12, 2015 10:29 pm    Post subject: Reply with quote

What is the %% operator? I'm going to move this to 2^24, due to room count on the MUD I'm playing, and discovery of hash collisions Smile
Back to top
View user's profile Send private message
Slysven



Joined: 10 Apr 2011
Posts: 369
Location: As "Jomin al'Bara" in WoTMUD or Wiltshire, UK

PostPosted: Thu Jan 15, 2015 3:09 pm    Post subject: Reply with quote

'%' is modulus but needs to be doubled to escape it in that position otherwise it would be mistaken for an argument supplied to the parent #ALIAS.
Back to top
View user's profile Send private message
perlsaiyan



Joined: 21 Sep 2014
Posts: 26

PostPosted: Thu Jan 15, 2015 6:31 pm    Post subject: Reply with quote

Thanks, I figured out what it was doing from teh codez but couldn't replicate it in the client. Now I understand why.

I ended up using 2^24 keyspace, but adding the title to the key I was using after doing some math on collision rates at the room counts I'm dealing with.
Back to top
View user's profile Send private message
Scandum
Site Admin


Joined: 03 Dec 2004
Posts: 3818

PostPosted: Mon Jan 01, 2018 6:12 pm    Post subject: Reply with quote

Slysven wrote:
'%' is modulus but needs to be doubled to escape it in that position otherwise it would be mistaken for an argument supplied to the parent #ALIAS.


The double %% can be avoided by adding spaces:

Code:

#math mkhash_return[0] ${mkhash_result}%%16;


Is identical to:

Code:

#math mkhash_return[0] ${mkhash_result} % 16;


In the 2.01.4 release * has become a special symbol, but hopefully that won't break too many scripts. Adding spaces is good practice though for a scripting language like tintin.
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    The TinTin++ message board Forum Index -> Script Help All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Get TinTin++ Mud Client at SourceForge.net. Fast, secure and Free Open Source software downloads Get TinTin++ Mud Client at SourceForge.net. Fast, secure and Free Open Source software downloads
TinTin++ Homepage

Powered by phpBB © 2001, 2002 phpBB Group