🚀 go-pugleaf

Thanks to all who have responded to my request for help with "unsit".
Please *don't* respond any more to that request as the problem has
been found and fixed.  (But the fix itself baffles me, so if you want
to think about a *new* puzzle, read on...)

* So far everyone who has responded has told me to get the version of
  "unsit" that's part of "Opener".  Actually, the version in "Opener"
  is almost identical to the version that's all over the net (according
  to archie) under the name "unsit-15.shar".  The only change is that
  the Opener version doesn't try to dialog with the user before
  over-writing a file.  This has absolutely no effect on the problem
  I've been having.  In fact, I pulled out the unsit executable from
  the Opener distribution and verified that, when asked to un-Stuff
  the particular archive I've been working with, it dies in exactly
  the same way as the version I compiled myself.

* The problem has been absolutely, unmistakably traced to a pointer
  running off the end of an array.  At one point in "unsit.c" an
  array is dimensioned with a size of 512, with the comment that
  "/* 512 should be big enough */".  At another place, a pointer
  is initialized to the head of the array and repeatedly incremented
  (via ++) to loop through the array.  It's supposed to stop when
  it sees a sentinel value, but there is *NO* provision in the code
  to keep it from running off the end of the array if the sentinel
  isn't among the first 512 elements.  By sheer cosmic coincidence,
  the very first StuffIt archive I tried to un-stuff after re-compiling
  unsit under 2.1 contained a member whose Huffman tree had more than
  512 elements.  BLAM!  Tracing confirms that the bad output begins
  as soon as the (nonexistent) 513th element is assigned (because a
  crucial variable that immediately follows the array in memory
  is clobbered).

* I have "fixed" the problem by inserting an explicit test, and
  arranging for the program to die informatively when the overrun
  occurs.  I have "verified" the fix by first exercising my trap,
  then re-compiling with a larger array size; the problem goes away
  and and the archive extracts just fine once the array is made
  big enough to hold the decoding tree.  (A *real* fix would involve
  redesigning the Huffman decoder to allocate memory dynamically;
  I do *not* plan to do this, since the static version has apparently
  worked nearly 100% of the time for nearly 100% of the users for
  three years now.)

* As soon as I've had a chance to write up a little blurb about
  this, I plan to package up an archive containing the old and new
  code, and I'll submit it to wherever is appropriate.  (But I want
  to try to contact the original author first -- I'm awaiting an
  answer to my email.)

Now for the $64,000 question--

* What still puzzles me is... *WHY* did the old binary that I compiled
  under NS 1.0 *not* die in the same way on the same input?  It merrily
  chugs along and successfully un-stuffs the entire archive.  I can
  only conclude that its variables are laid out in memory in a different
  way, so that the array overrun clobbers space that would otherwise
  have been unused, instead of clobbering other variables.

I would be MOST grateful for an explanation of this phenomenon.
But more pointers to other versions of unsit (or to Opener) are not needed.

My sincere thanks, though, to all who took the time to try to help.
It is really much appreciated.

--Cameron Smith
  cameron@symcom.math.uiuc.edu