For case insensitive languages with ASCII alphanumeric identifiers (that begin with a letter), there are 34,658 identifiers up to three characters long, 1,247,714 up to 4 characters long, and 44,917,730 up to 5 characters long. The initial character takes 4.70 bits, and each succeeding character 5.17 bits. You can fit any one- or two-character identifier in ten bits, or any three-character one in just over 15 bits. Up to four characters fit in 21 bits, five in 26 bits, and six in under 31 bits.
If identifiers are case-sensitive, start with a letter, and contain letters, digits, underscore, and one other character (say '.'), the identifiers are basically base-64 digits (except the initial digit is limited to first 52 or 54 values, as digits cannot start an identifier). Each character then takes exactly 6 bits, so one can fit four of these in a 24-bit word, or five in a 30-bit word.
This kind of
perfect hashing is useful, because it is bijective. Instead of storing the script as text, one can tokenize it as it is read, and convert tokens back to string if a listing is desired. This is what old BASIC versions usually did, to save memory.
I personally like to use DJB2 Xor hash instead, because it is trivial, but has few collisions among ASCII alphanumeric strings. It does mean that there might be more than one string corresponding to each identifier, so I recommend against using it for cases when the user can add new identifiers (like variables).
When you have a microcontroller that reads in new values for state variables from an UART, then the UART receive interrupt can be a simple state machine, that in the state variable name phase just hashes the name; and in the assignment or lookup phase, does a binary search into a sorted array of hashes, with each hash corresponding to a type and a pointer in RAM. This naturally leads to a command mini-language where each identifier is followed by the command character (
= for assignment,
? for query), followed by optional value, followed by end of command character (usually newline). The array of hashes+types+RAM-pointers can reside in ROM/Flash, and for N entries, 3+⌈log
2N⌉ lookups are enough to locate the correct entry, if any.
With GCC and Clang, one can use the section attributes to collect such entries from each compilation unit to a single section at link time. One then does need to do a custom fixup pass, extracting the section from the target object file, sorting the entries for binary searching, and write the section back. Extraction and reinsertion is trivial with
objcopy (which is part of the development tools used with GCC or Clang), but you do need to sort the binary data (extracted into a separate file, containing only the binary data) yourself using a helper script or program. Such a fixup pass is also useful for detecting if identifier hashes collide; the sorter does not need to even know the hash algorithm used.
Home
Help
Search
Login
Register
