NH4: Store game state diffs in logs and save files

Every time a command is logged, the game now performs an in-memory save,
compares it to its previous one, and stores the base 64 encoded
difference in the game log.  These diffs aren't used for anything yet.

Diffs consist of copy, edit and seek commands encoded in the top 2 bits
of a 16 bit value and using the last 14 bits to store an associated
count (signed for seeks, otherwise unsigned).  Edit commands are also
followed by that many bytes of the differing data.

To help keep diffs efficient, tags marking sections of the save are
tracked.  The current state looks up tags from the previous state and
issues seek commands if the tracking position differs from where the tag
says it should be.  The current state also creates its own tags so the
next state can use them.  Tags are NOT saved, nor are they strictly
needed for correctness, but they help to reduce redundant diff output
where the same data exists in the current and previous state but
difference tracking reads them offset from one another.

Compared to NetHack4:

 * the comments now do a better job of explaining how these diffs work

 * diff commands are now an enum instead of defines

 * the tag linked list free code in mfree() has been rewritten to be
   simpler, also preventing an initial free(NULL)

 * some fixes for diff command/count encoding issues have been
   back-ported

Store gamestate diffs in log/savefiles
Alex Smith <ais523@bham.ac.uk>
77291079817c2831e764d1bb1832fc08fdbd4ec7
NH4: Replay from diffs if the commands won't sync

Each diff that is reached in the log during a replay is used to
construct the save file as the game was played (mf).  The replay itself
makes its own in-memory save (diff_base) and compares the two.  If they
differ, the replay recovers from the game's version constructed from
diffs before continuing.

Note that this change makes rewinding turns much slower than before.  A
fix exists in NetHack4, but it hasn't been ported yet.

Compared to NetHack4, recovering from save-compared desyncs accounts for
tutorial mode, the diff command/count decoding is simplified slightly
and some extra comments have been added.

Replay from diffs, if the commands won't sync
Alex Smith <ais523@bham.ac.uk>
7990aa24b1f190f60543b3e845b2774f64187a39
NH4: Fix replays with broken command data

Also, count replays by diffs (~) instead of commands (>).

This is meant to go with commit cd1d97bb6f (NH4: replay from diffs if
the commands won't sync).

Make log replay count by ~ not >, fix replay of logs with broken command
data
Alex Smith <ais523@bham.ac.uk>
7d748339f938cc3e814da31a1b2b5ea3468c8cee
NH4: Display prompt selections in message history

Responses to menus, questions and prompts are now recorded in the
message log, and shown in message window if they wouldn't block other
messages with --More--.

Display menu/question/prompt selections in message history
Alex Smith <ais523@bham.ac.uk>
58295ae9c592d37b87928a24c0fa7c002a9f2b46

NetHack4 bugfix: id is not always the same as accel in object menus
Alex Smith <ais523@bham.ac.uk>
9874b0dfe6a3f91a0f87caea7d2a8e4ef4ba5f1e
NH4: Initialize diff logging correctly

This is meant to go with commit 86bb075297 (NH4: store game state diffs
in logs and save files).

This was extracted from the following NetHack4 commit:

Add messages to log, show them when replaying from diffs
Alex Smith <ais523@bham.ac.uk>
5c1eaef25838605ce3340ce3f760087074b4f3a4
NH4: Log messages, show when replaying from diffs

There's a fair amount of code in the NetHack4 version of this commit
that actually belong with other, previous commits.  This version only
contains what's needed for this feature to work.  Since messages aren't
logged during multi-turn actions or occupations, messages beyond the
last 30 may be left out, which is a minor problem.

Add messages to log, show them when replaying from diffs
Alex Smith <ais523@bham.ac.uk>
5c1eaef25838605ce3340ce3f760087074b4f3a4
NH4: Don't reverse trap chain order upon restore

This causes the replay code to spuriously report a desync when
rewinding if a level has at least two traps on it.

Don't reverse order of trap chain upon save and restore
Alex Smith <ais523@bham.ac.uk>
0fc1051e98ce2315e27baa09f199b3d39fbbda30
Fix replay desync warning due to timer_id

The ID for timers is assigned from an incrementing static int which
wasn't reset, saved or restored with games, causing the command-driven
replays to use different IDs from the ones in the logged save diffs, in
turn causing a desync warning to be displayed.

This bug also exists in NetHack4.

Closes #77 on GitHub.
NH4: Save null shopkeeper bills explicitly

Without this, shopkeepers with null bill pointers could be saved with a
pointer-based value, at least in theory.  In practice, shopkeeper bill
pointers are only set to null when they're dead and about to be purged.
In any case, this helps prevent bogus replay desync warnings with the
new diff-logged replay system.

Compared to NetHack4, this omits the byte-numbering in the monster
restoring code.

Save empty shopkeeper bills correctly
Alex Smith <ais523@bham.ac.uk>
24c8844e9e1506d83253d532ad3a8b80882d47dc
NH4: Don't call check_special_room on game restore

From NetHack4:

"As far as I can tell, it's a no-op; there isn't a matching call in
vanilla, and all it does is set urooms0 to urooms.  urooms0 is ignored
everywhere except inside check_special_room anyway; and saving and
restoring shouldn't cause you to leave or enter a room, so nothing
should happen.  The change to urooms0 confuses the desync detector, so
it's better to remove this call than leave it in."

Don't call check_special_room on game restore
Alex Smith <ais523@bham.ac.uk>
60454da37c4eccb920ee4a241474e31febace68b
Save and restore u.ubirthday to fix replays

Without this, restoring a game or rewinding in a replay would cause
u.ubirthday to be set to 0 instead of time the character was created.
This affects:

 * which bones file is chosen to be saved or loaded in the current
   level's bones pool
 * which ant type occupies any given anthole
 * the randomized creator deity name
 * the erosion applied to T-shirt labels when reading them
 * the cost of gems in a shop
 * which name is randomly chosen for shopkeepers

The last one was triggering a diff log replay desync warning when
rewinding a replay and advancing to a level a shopkeeper was created on,
since the name chosen by the replay was different from the one in the
logged diff.  The anthole population and gem costs would almost
certainly cause game-affecting desyncs as well.

This fix assumes 64 bits is enough to store time_t, since the C99
standard (ISO/IEC 9899/1999, n1256.pdf) states "the range and precision
of times representable in clock_t and time_t are implementation-
defined."  (It's 4 bytes large on my 32-bit Linux system.)  NitroHack
already assumes this via storing the result of time(NULL) in the
unsigned long long turntime variable.

The character's birthday is already stored in the log header, but due to
the heavily-stateful nature of log reading and the mid-log recovery of
the new logged diff replay system, it is easier and more reliable to
save and restore it with the rest of struct you.

NetHack4 partially addresses this in the following commits (code not
used here):

 * bed7cae11304dd0d5c2679c9f2bc5461cc3fb877
 * f893eb81fb405bcbe8ae623729351245f06cfd77

However, they only fix this for manually-loaded games, not for rewinding
in replays, so this bug also exists in NetHack4.
Prevent lock-up when pruning message history

nh_view_replay_step() may issue print_message(moves, "") with moves == 0
if the new logged diff replay system fails while restoring a game,
leading to an infinite loop in prune_messages() in the interface.

This bug also exists in NetHack4.