All that division and stuff in the hashing function is a bit painful on a PIC. You might try a simple hash function like: unsigned char Hash( char const *szCommand ) { unsigned char result = 0; while (*szCommand) { result = (result << 1) | (result >> 7); // rotate left one result ^= *szCommand; } } Also, your hash function does not necessarily have to look at all the characters in the command. Bob Ammerman RAm Systems ----- Original Message ----- From: "Jack Smith" To: Sent: Wednesday, August 13, 2003 9:32 AM Subject: Re: [PIC] Command string interpreter / parser > As a starting point, as per Aho, Sethi and Ullman in "Compilers Principles, > Techniques and Tools": > > (a) compute the sum of the ASCII values of the characters in the input > command string. Call this sum N. There are assumed to be M different > possible commands. > > (b) the hash value is determined by the remainder of N/M. M should be a > prime number so increase the divisor to the next highest prime number if M > is not already a prime. > > Instead of using a simple sum in step (a) consider some other function, such > as a polynomial based on the position of the characters in the input string. > > Note that this isn't guaranteed to give you a perfect hash function, so some > further error checking may be appropriate. > > > > Jack > > > > -----Original Message----- > From: pic microcontroller discussion list > [mailto:PICLIST@MITVMA.MIT.EDU]On Behalf Of Bob Ammerman > Sent: Wednesday, August 13, 2003 9:01 AM > To: PICLIST@MITVMA.MIT.EDU > Subject: Re: [PIC] Command string interpreter / parser > > > It should be possible to create a 'perfect' hash function for your commands. > This function would map every valid command into a different number in a > small range (say zero to 63). > > So here is what you would do: > > Define your command table something like this: > > char const * const cmds[64] = { > "ABC", // command that hashes to 0 > "DEF", // command that hashes to 1 > 0, // no command hashes to 2 > .... > }; > > Take your command string and hash it, giving the value H. > > Take a look at the Hth entry in the command table. > > A null entry means the command string was not valid. > > If the command string equals the table entry then you have found your > command, otherwise you have an invalid command. > > Have fun finding the perfect hash function ;-) > > Bob Ammerman > RAm Systems > > > > ----- Original Message ----- > From: "Wesley Moore" > To: > Sent: Wednesday, August 13, 2003 8:15 AM > Subject: Re: [PIC] Command string interpreter / parser > > > > What you describe in the first paragraph quoted here is almost hashing. > > Hashing involves applying a hash function that maps a string > > to a (usually) unique number. That number is then truncated in some manner > > to be the index into your hash table. In your case this would be the table > > of commands. As Wouter already mentioned you then do a char by char check > > on the hash table entry that you find (assuming one was found) to double > > check that the command is indeed a proper match. > > > > On a PC a hash table gives you very fast access to data with a trade off > > in memory. Perhaps a hash table with linear probing would work well for > > your application (Google should be able to return lots of computer science > > course notes with info on how that works). It would be a lot more work > over > > basic string comparisons though. > > > > Wesley > > > > On Wed, Aug 13, 2003 at 07:21:10AM +0100, Trevor Page wrote: > > > I know one other way could be to take the checksum of the input string > > > and compare that with checksums of the strings in ROM which is a much > > > faster process, but this would result in other randomly typed character > > > combinations potentially causing a 'match' too, unless there is a more > > > clever way of doing it. > > > > > > Or there is the hash process which I am vaguely familiar with, but I > > > don't know if this is what I need. > > > > -- > > Wesley Moore http://wmoore.freeshell.org/ > > RMIT - BEng (Comp Sys Eng)/BApp.Sc. (Comp Sci) 5th (And Final!) Year > > SDF Public Access UNIX System http://sdf.lonestar.org/ > > > > -- > > http://www.piclist.com#nomail Going offline? Don't AutoReply us! > > email listserv@mitvma.mit.edu with SET PICList DIGEST in the body > > > > -- > http://www.piclist.com#nomail Going offline? Don't AutoReply us! > email listserv@mitvma.mit.edu with SET PICList DIGEST in the body > --- > Incoming mail is certified Virus Free. > Checked by AVG anti-virus system (http://www.grisoft.com). > Version: 6.0.507 / Virus Database: 304 - Release Date: 8/4/2003 > > --- > Outgoing mail is certified Virus Free. > Checked by AVG anti-virus system (http://www.grisoft.com). > Version: 6.0.507 / Virus Database: 304 - Release Date: 8/4/2003 > > -- > http://www.piclist.com#nomail Going offline? Don't AutoReply us! > email listserv@mitvma.mit.edu with SET PICList DIGEST in the body -- http://www.piclist.com#nomail Going offline? Don't AutoReply us! email listserv@mitvma.mit.edu with SET PICList DIGEST in the body