From: gad@eclipse.its.rpi.edu (Garance A. Drosehn)
Subject: Re: bug/fix for sort !!!
Date: Mon, 31 Aug 1992 04:33:30 GMT

I'm basically reposting this just in case no one sees comp.sys.next these  
days (as well they should not, seeing it hasn't officially existed for a  
year or so now...  :-).

The author claims this bug is in NeXTSTEP 2.1.  Does anyone know if it's in  
NeXTSTEP 3.0?
---
Garance Alistair Drosehn     =     gad@eclipse.its.rpi.edu
ITS Systems Programmer            (handles NeXT-type mail)
Rensselaer Polytechnic Institute;           Troy NY    USA

 - - - - - - - - [start quoted article]

In article <1992Aug27.202530.28111@u.washington.edu>
    in newsgroup comp.sys.next
    corey@milton.u.washington.edu (Corey Satten) writes:
> As hard as it is to believe, after all these years of use, I found a bug
> in /usr/bin/sort when used with the -u flag.  The bug only shows up for
> relatively large inputs and causes a few of the last lines of output to
> be omitted.  Below is a script you can feed both to /bin/sh to test your
> sort and to "patch" to (hopefully - but as always, no guarantees) fix
> your sort.c.  The context diff is for BSD 4.3 sort.c, however the exact
> same code exists (at different line numbers) in Ultrix 4.1 sort.c so
> you can still apply the patch verbatim.
> 
> --------
> Corey Satten, corey@cac.washington.edu
> Networks and Distributed Computing
> University of Washington

  [patch from the article, but not quoted with the ">"s - garance]
#!/bin/sh
#
# Test for sort -u bug.  The bug causes a small number of lines to be
# omitted from the sort -u output for relatively large sort inputs.
#
# It is caused by the merge code not handling EOF properly in the  
next-to-last
# temp-file generated by sort.  In order to trigger the bug, enough input
# must be presented that sort merges a larger number of tempfiles into a
# smaller number and then merges the smaller number.  Alternatively,
# the uninitialized memory which is compared against the last value
# could accidently contain that value.
#
# This bug is known to be present in:
#	BSD 4.3 Tahoe
#	Sequent Dynix V3.1.4
#	NeXT version 2.1
#	Ultrix version 4.1, 4.2a
#	AT&T 7300/3b1 version 3.51
#
# It appears not to be present in SunOS 4.x, OSF/1 however this may only
# be because the size of the input required to trigger the bug has been
# raised (the size of the tempfiles and memory arrays has been raised).
#
# A context diff of what I hope is a fix to the 4.3BSD version is
# appended at the end of this script.  Use at your own risk.
#
# Corey Satten, corey@cac.washington.edu, July 31, 1992

TMP=/tmp/data$$
trap "rm -f $TMP.c $TMP; exit 0" 0 1 2 13 15

COUNT=${1-45}		# value supplied as $1, else default to 45

lines=`echo "$COUNT^3 * 1.015625 / 10 * 10" | bc`
echo testing sort with input of roughly $lines lines 1>&2

cat <<EOF >$TMP.c
#include <stdio.h>
#define r(x) ("qwertyuiopasdfghjklzxcvbnm"[pos(x)%26])
#define pos(x) ((x)>0?(x):5-(x))

main() {
    int lines = 0;
    int i,j,k;
    for (i=0; i<$COUNT; ++i) {
	for (j=0; j<$COUNT; ++j) {
	    for (k=0; k<$COUNT; ++k) {
		if ( (++lines & 63) == 0) printf("zzzzzzzzzzz - OK\n");
		printf("%c%c%c%c%c%c\n",
		    r(k), r(j+k), r(j-k), r(i+k), r(i-k), r(i+j+k));
		    }
		}
	    }
	}
EOF
cc $TMP.c -o $TMP || {
    rm -f $TMP.o
    echo
    echo " Sorry, your C compiler didn't compile my program." 1>&2
    exit 1
    }

if $TMP | sort -u | grep -s '^zzzzzzzzzzz' ; then
    echo
    echo " sort -u worked for this input (COUNT=$COUNT) but to be safe, you"
    echo ' might wish to try again with a larger value of COUNT.  You may'
    echo ' supply a value for COUNT as an argument to this script.'
    echo ' The number of lines is roughly COUNT to the 3rd power.'
    exit 0
else
    echo
    echo ' sort -u failed on this system.  The line beginning with  
zzzzzzzzzz'
    echo ' was omitted from the sort -u output.  You might wish to compare'
    echo ' sort -u output with output from sort|uniq to see if there are  
any'
    echo ' other differences.'
    exit 1
fi

# I believe this change applied to the 4.3BSD code fixes the problem.
# Use at your own risk.  -Corey
#
*** sort.c	Fri Jul 31 08:35:33 1992
--- new_sort.c	Fri Jul 31 14:33:20 1992
***************
*** 387,392 ****
--- 387,393 ----
  	int	j;
  	int	k, l;
  	int	muflg;
+ 	int	last_muflg;
  
  	p = (struct merg *)lspace;
  	j = 0;
***************
*** 432,438 ****
  				term();
  			}
  		}
! 		if(muflg){
  			cp = ibuf[i-1]->l;
  			dp = p->l;
  			do {
--- 433,439 ----
  				term();
  			}
  		}
! 		if(last_muflg = muflg){	/* yes assignment. Corey */
  			cp = ibuf[i-1]->l;
  			dp = p->l;
  			do {
***************
*** 452,458 ****
  				*ip = *(ip-1);
  				*(ip-1) = jp;
  			}
! 			if(!muflg)
  				break;
  			j = (*compare)(ibuf[i-1]->l,p->l);
  			if(cflg) {
--- 453,466 ----
  				*ip = *(ip-1);
  				*(ip-1) = jp;
  			}
! 		/*
! 		 * Instead of testing muflg, I introduce last_muflg
! 		 * because when i-- reaches 1 and the value of muflg
! 		 * changes, the code suddenly compares against p->l
! 		 * which hasn't had a recent value copied into it.
! 		 * Corey.
! 		 */
! 			if(!last_muflg)
  				break;
  			j = (*compare)(ibuf[i-1]->l,p->l);
  			if(cflg) {