Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!uw-beaver!zephyr.ens.tek.com!tektronix!percy!m2xenix!quagga!undeed!barrett
From: barrett@Daisy.EE.UND.AC.ZA (Alan P. Barrett)
Newsgroups: comp.mail.uucp
Subject: Re: Smail2.5 binary search bug
Message-ID: <1991Mar19.100209.24021@Daisy.EE.UND.AC.ZA>
Date: 19 Mar 91 10:02:09 GMT
References: <135800005@cdp> <1991Mar13.211418.20877@eci386.uucp>
Organization: Univ. Natal, Durban, S. Africa
Lines: 33

In article <1991Mar13.211418.20877@eci386.uucp>,
woods@eci386.UUCP (Greg A. Woods) writes:
> In article <135800005@cdp> brian@cdp.UUCP writes:
> > i have just discoverd that the binary search routine in
> > smail 2.5 is faulty. it seems it can miss (at least) the
> > last line in the paths file. the version i have is:

There are (at least) two binary search routines in smail2.5.  One deals
with the paths file and one deals with the fullnames file.  Both had
bugs.  Both are fixed in the apbmje900117 patches to smail2.5, which I
posted to alt.sources earlier this year.  (However, I have a nasty
suspicion that my posting did not propagate very well -- I don't think
it made it onto the list in alt.sources.index.  Should I post again?)

> I think this bug has been previously discovered, and perhaps there is
> a patch for it.  I know I ran into it at one time.
> 
> However, if I remember correctly, the bug is only triggered on very
> small files, and only on files such as yours where your smart-host
> entry is the last thing in the file.

I am not sure, but I seem to remember that the bug could bite at just
about any time, although small files are indeed more likely to trigger
it.  It had to do with the relationship between the length of a line in
the file being searched, and the distance between the start and end
pointers used during the binary search.  I am sure that smart-host was
not the only string that missed being found, although of course you are
more likely to notice if it misses the smart-host than if it misses some
other entry.

--apb
Alan Barrett, Dept. of Electronic Eng., Univ. of Natal, Durban, South Africa
Internet: barrett@ee.und.ac.za           UUCP: m2xenix!quagga!undeed!barrett