🚀 go-pugleaf

In article <2675@crdos1.crd.ge.COM> davidsen@crdos1.crd.ge.com (bill davidsen) writes:
+
+  I have discovered what appears to be a serious bug in the sort
+routine used in several SysV variants including Stellar. Since it
+causes silent loss of data I am cross posting a bit more than I usually
+do.
+
+  The problem occurs when the options -n (numeric) and -u (discard
+duplicates) are used together sorting data which has a fixed width
+numeric as the first key field. The results is output of only one line,
+regardless of the input data. I found this by losing 15 months of data
+(yes it was backed up). Since sort is often in shell scripts run from
+cron to do system things, this problem might not be instantly noticed.


     Interesting. Right now I'm running on a Solbourne, which is a Sun
clone, and it has the dual BSD/SYSV environment.

     The bug shows up using the SYSV sort, but not the BSD sort.....

  Several people have told me to use the -b option on the sort. That
doesn't work. I thought I posted the test script with this option set,
but I didn't. Adding -b to the two sort commands does not change the
behavior on any machines to which I have access.

  Sure saves on disk space, though ;-)

-- 
	- bill davidsen (davidsen@crdgw1.crd.ge.com)
	GE Corp. R&D Center; Box 8, KW-C206; Schenectady NY 12345

In article <2675@crdos1.crd.ge.COM>, davidsen@crdos1.crd.ge.COM (Wm E Davidsen Jr) writes:
> 
>   I have discovered what appears to be a serious bug in the sort
> routine used in several SysV variants including Stellar. Since it
> causes silent loss of data I am cross posting a bit more than I usually
> do.
> 
[deleted some details to save space, followed by test script...]
> 
> sort -nu <<XX >x$$.tmp
>   1: a
>   3: b
>   2: c
>   1: a
>  10: x
> XX
> 
>   Of course someone may tell me it's supposed to work that way, and that
> the BSD version is broken.

I suspect this may be the case.  The system V manual page says this about
the -u option:

     -u	  Unique: suppress all but one in each set of lines hav-
	  ing equal keys.

This doesn't agree with the code, though.  The real behavior matches what
I find in the BSD manual page:

     u	  Suppress all but  one	 in  each  set	of  equal  lines.
	  Ignored bytes	and bytes outside keys do not participate
	  in this comparison.

The next clue is from the System V manual page again:

     -n	  An initial numeric string, consisting	of optional
	  blanks, optional minus sign, and zero	or more	digits
	  with optional	decimal	point, is sorted by arithmetic
	  value.  The -n option	implies	the -b option (see
	  below).  Note	that the -b option is only effective when
	  restricted sort key specifications are in effect.

The tricky point is that a numeric comparison stops as soon as it finds
a non-numeric character.  Since your test file has leading blanks, and
you didn't specify a sort key, the numeric comparison stops when it
sees the leading blank in each record; the test file appears to
contain five empty records as seen by the numeric comparison code.
Furthermore, the -u option suppresses the following escape clause in
the manual page:

     When there	are multiple sort keys,	later keys  are	 compared
     only  after all earlier keys compare equal.  Lines	that oth-
     erwise compare equal are ordered with all bytes significant.

Translation: if a numeric comparison, or a set of keyed comparisons,
shows that two records match, `sort' then compares both records as
simple text to determine whether the records are really identical.  
This `tie breaking' test is suppressed if the -u option is enabled.

Since all five of your test lines appear to be identical, the -u
option deletes all but one of them.  I think the command you want
to use is

	sort -nu +0

This forces a trip through the key finder, which activates the code
that strips leading blanks.

> -- 
> bill davidsen	(davidsen@crdos1.crd.GE.COM -or- uunet!crdgw1!crdos1!davidsen)
>     VMS is a text-only adventure game. If you win you can use unix.

Flames, counter arguments, cheerfully accepted.  I didn't write the
rules, I just work here.
-- 
Griff Smith	AT&T (Bell Laboratories), Murray Hill
Phone:		1-201-582-7736
UUCP:		{most AT&T sites}!ulysses!ggs
Internet:	ggs@ulysses.att.com

>The next clue is from the System V manual page again:
>
>     -n	  An initial numeric string, consisting	of optional
>	  blanks, optional minus sign, and zero	or more	digits
>	  with optional	decimal	point, is sorted by arithmetic
>	  value.  The -n option	implies	the -b option (see
>	  below).  Note	that the -b option is only effective when
>	  restricted sort key specifications are in effect.

And a further clue comes from the SunOS 4.0.3 manual page:

  SYSTEM V DESCRIPTION
       When no fields are specified in the command line, the System
       V version of sort treats leading blanks as significant, even
       with the -n (numeric collating sequence) option; the lines:
            123
              23

       are collated as:
              23
            123

I.e., this is one of the places where the SunOS "/usr/bin/sort" and
"/usr/5bin/sort" differ in their behavior.

(They're both built from the same source code, BTW, which is basically
the S5R2 "sort", that being significantly faster than the V7-vintage
sort that comes with 4.3BSD; see J. P. Linderman's paper in the
October 1984 AT&T Bell Laboratories Technical Journal, October 1984,
Vol. 63 No. 8 Part 2 - the second special UNIX issue - which discusses
work on sorting that, I think, got into the S5 sort in S5R2.  There's an
"#ifdef S5EMUL" that governs which of the behaviors is selected.)

In article <2675@crdos1.crd.ge.COM> davidsen@crdos1.crd.ge.com (bill davidsen) writes:
|
|  I have discovered what appears to be a serious bug in the sort
|routine used in several SysV variants including Stellar. Since it
|causes silent loss of data I am cross posting a bit more than I usually
|do.
|
|  The problem occurs when the options -n (numeric) and -u (discard
|duplicates) are used together sorting data which has a fixed width
|numeric as the first key field. The results is output of only one line,
|regardless of the input data. I found this by losing 15 months of data
|(yes it was backed up). Since sort is often in shell scripts run from
|cron to do system things, this problem might not be instantly noticed.
|
|  I have generated the following shell script to test for the problem.
| [...]

	This isn't a problem on the AT&T 3B1, although
	Convergent may have used the BSD version...

-- 
  ,u,	 Bruce Becker	Toronto, Ontario
a /i/	 Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu
 `\o\-e	 UUCP: ...!uunet!mnetor!becker!bdb
 _< /_	 "I still have my phil-os-o-phy" - Meredith Monk

In article <2675@crdos1.crd.ge.COM> davidsen@crdos1.crd.ge.com (bill davidsen) writes:
>
>  I have discovered what appears to be a serious bug in the sort
>routine used in several SysV variants including Stellar. Since it
>causes silent loss of data I am cross posting a bit more than I usually
>do.
>
>  The problem occurs when the options -n (numeric) and -u (discard
>duplicates) are used together sorting data which has a fixed width
>numeric as the first key field. The results is output of only one line,
>regardless of the input data. I found this by losing 15 months of data
>(yes it was backed up). Since sort is often in shell scripts run from
>cron to do system things, this problem might not be instantly noticed.
>
>  I have generated the following shell script to test for the problem.


I have & send my version of sort under SCO XENIX: this test run correctly!

-----------------------------------------------------------------------
Start test of sort error

Starting check
Output appears okay unless diff reported below:
Test ends


=== CUT HERE =============================================================
/*
 * It is version of SORT, maybe old, but BUG FREE!
 */
#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define lcmp(a,b) ((a&0377)-(b&0377))   /* My RUSSIAN version of lcmp was here */

#define	L	512
#define	C	20
#define N       15  /* Max. files number for merge */
#define MEM     (((unsigned)56)*1024) /* 56K max */
#define NF      10 /* Max. fields number */

FILE *is, *os;
char isbuf[BUFSIZ], osbuf[BUFSIZ];

char   *dirtry[] = {
    "/usr/tmp", "/tmp", NULL
};
char  **dirs;
char    file1[30];
char   *file = file1;
char   *filep;
int     nfiles;
unsigned    nlines;
unsigned    ntext;
int    *lspace;
char   *tspace;
int     cmp (), cmpa ();
int     (*compare) () = cmpa;
char   *eol ();
int     term ();
int     mflg;
int     cflg;
int     uflg;
char   *outfil;
int     unsafeout;		/* kludge to assure -m -o works
				   */
char    tabchar;
int     eargc;
char  **eargv;
char   *progname;

char    zero[256];      /* All arrays extended to 256 for my RUSSIAN version */
			/* You may reduce it to 128 */

char    fold[256] = {
    0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
    0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
    0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
    0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
    0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
    0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
    0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
    0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
    0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
    0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
    0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
    0370, 0371, 0372, 0373, 0374, 0375, 0376, 0337,
    0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
    0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
    0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
    0370, 0371, 0372, 0373, 0374, 0375, 0376, 0337,
    0000, 0001, 0002, 0003, 0004, 0005, 0006, 0007,
    0010, 0011, 0012, 0013, 0014, 0015, 0016, 0017,
    0020, 0021, 0022, 0023, 0024, 0025, 0026, 0027,
    0030, 0031, 0032, 0033, 0034, 0035, 0036, 0037,
    0040, 0041, 0042, 0043, 0044, 0045, 0046, 0047,
    0050, 0051, 0052, 0053, 0054, 0055, 0056, 0057,
    0060, 0061, 0062, 0063, 0064, 0065, 0066, 0067,
    0070, 0071, 0072, 0073, 0074, 0075, 0076, 0077,
    0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
    0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
    0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
    0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177
};
char    nofold[256] = {
    0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
    0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
    0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
    0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
    0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
    0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
    0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
    0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
    0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307,
    0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317,
    0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327,
    0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337,
    0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
    0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
    0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
    0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377,
    0000, 0001, 0002, 0003, 0004, 0005, 0006, 0007,
    0010, 0011, 0012, 0013, 0014, 0015, 0016, 0017,
    0020, 0021, 0022, 0023, 0024, 0025, 0026, 0027,
    0030, 0031, 0032, 0033, 0034, 0035, 0036, 0037,
    0040, 0041, 0042, 0043, 0044, 0045, 0046, 0047,
    0050, 0051, 0052, 0053, 0054, 0055, 0056, 0057,
    0060, 0061, 0062, 0063, 0064, 0065, 0066, 0067,
    0070, 0071, 0072, 0073, 0074, 0075, 0076, 0077,
    0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
    0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
    0140, 0141, 0142, 0143, 0144, 0145, 0146, 0147,
    0150, 0151, 0152, 0153, 0154, 0155, 0156, 0157,
    0160, 0161, 0162, 0163, 0164, 0165, 0166, 0167,
    0170, 0171, 0172, 0173, 0174, 0175, 0176, 0177
};

char    nonprint[256] = {
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
};

char    dict[256] = {
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1
};

struct field {
    char   *code;
    char   *ignore;
    char    nflg;
    char    rflg;
    char    zflg;
    char    bflg[2];
    int     m[2];
    int     n[2];
}               fields[NF];

struct field    proto = {
    nofold + 128,
    zero + 128,
    0,
    1,
    0,
    {0, 0},
    {0, -1},
    {0, 0}
};
int     nfields;
int     error = 1;
char   *setfil ();

main (argc, argv)
char  **argv;
{
    register    a;
    unsigned ep, curr, fp, maxmem;
    char   *arg;
    register struct field   *p,
			    *q;
    int     i;

    for (arg = progname = argv[0]; *arg; arg++)
	if (*arg == '/')
	    progname = arg + 1;
    copyproto ();
    eargv = argv;
    while (--argc > 0) {
	if (**++argv == '-')
	    for (arg = *argv;;) {
		switch (*++arg) {
		    case '\0':
			if (arg[-1] == '-')
			    eargv[eargc++] = "-";
			break;

		    case 'o':
			if (--argc > 0)
			    outfil = *++argv;
			continue;

		    case 'T':
			if (--argc > 0)
			    dirtry[0] = *++argv;
			continue;

		    default:
			field (++*argv, nfields > 0);
			break;
		}
		break;
	    }
	else
	    if (**argv == '+') {
		if (++nfields >= NF) {
		    diag ("too many fields", "");
		    exit (1);
		}
		copyproto ();
		field (++*argv, 0);
	    }
	    else
		eargv[eargc++] = *argv;
    }
    q = &fields[0];
    for (a = 1; a <= nfields; a++) {
	p = &fields[a];
	if (p -> code != proto.code)
	    continue;
	if (p -> ignore != proto.ignore)
	    continue;
	if (p -> nflg != proto.nflg)
	    continue;
	if (p -> rflg != proto.rflg)
	    continue;
	if (p -> zflg != proto.zflg)
	    continue;
	if (p -> bflg[0] != proto.bflg[0])
	    continue;
	if (p -> bflg[1] != proto.bflg[1])
	    continue;
	p -> code = q -> code;
	p -> ignore = q -> ignore;
	p -> nflg = q -> nflg;
	p -> rflg = q -> rflg;
	p -> zflg = q -> zflg;
	p -> bflg[0] = p -> bflg[1] = q -> bflg[0];
    }
    if (eargc == 0)
	eargv[eargc++] = "-";
    if (cflg && eargc > 1) {
	diag ("can check only 1 file", "");
	exit (1);
    }
    safeoutfil ();

    fp = sbrk (0);
    lspace = (int *) fp;
    ep = min (MEM, ((unsigned) ~0) - 512 - fp) &~ 0777;
    maxmem = fp + ep;
    for (curr = fp; ep >= 512 && curr < maxmem; ep /= 2) {
	while ((long) curr + ep < (unsigned) ~0 - 512 && sbrk (ep) != -1) {
	    if ((curr += ep) >= maxmem)
		goto Out;
	}
    }
Out:
    ep = ((unsigned) sbrk (0)) - fp;
    nlines = ep - L;
    nlines /= (5 * (sizeof (char *) / sizeof (char)));
    ntext = nlines * 8;
    tspace = (char *) (lspace + nlines);
    a = -1;
    for (dirs = dirtry; *dirs; dirs++) {
	sprintf (filep = file1, "%s/stm%05uaa", *dirs, getpid ());
	while (*filep)
	    filep++;
	filep -= 2;
	if ((a = creat (file, 0600)) >= 0)
	    break;
    }
    if (a < 0) {
	diag ("can't locate temp: ", file);
	exit (1);
    }
    close (a);
    signal (SIGHUP, term);
    if (signal (SIGINT, SIG_IGN) != SIG_IGN)
	signal (SIGINT, term);
    if (signal (SIGQUIT, SIG_IGN) != SIG_IGN)
	signal (SIGQUIT, term);
    signal (SIGPIPE, term);
    signal (SIGTERM, term);
    nfiles = eargc;
    if (!mflg && !cflg) {
	sort ();
	fclose (stdin);
    }
    for (a = mflg | cflg ? 0 : eargc;
	    a + N < nfiles
	    || unsafeout
	    && a < eargc;
	    a = i) {
	i = a + N;
	if (i >= nfiles)
	    i = nfiles;
	newfile ();
	merge (a, i);
    }
    if (a != nfiles) {
	oldfile ();
	merge (a, nfiles);
    }
    error = 0;
    term ();
}

sort () {
    register char  *cp;
    register char **lp;
    register    c;
    int     done;
    int     i;
    char   *f;

    done = 0;
    i = 0;
    c = EOF;
    do {
	cp = tspace;
	lp = (char **) lspace;
	while (lp < (char **) lspace + nlines
		&& cp < tspace + ntext) {
	    *lp++ = cp;
	    while (c != '\n') {
		if (c != EOF) {
		    *cp++ = c;
		    c = getc (is);
		    continue;
		}
		else
		    if (is)
			fclose (is);
		if (i < eargc) {
		    if ((f = setfil (i++)) == 0)
			is = stdin;
		    else {
			if ((is = fopen (f, "r")) == NULL)
			    cant (f);
			setbuf (is, isbuf);
		    }
		    c = getc (is);
		}
		else
		    break;
	    }
	    *cp++ = '\n';
	    if (c == EOF) {
		done++;
		lp--;
		break;
	    }
	    c = getc (is);
	}
	qsort ((char **) lspace, lp);
	if (done == 0 || nfiles != eargc)
	    newfile ();
	else
	    oldfile ();
	while (lp > (char **) lspace) {
	    cp = *--lp;
	    if (*cp)
		do
		    putc (*cp, os);
		while (*cp++ != '\n');
	}
	fclose (os);
    } while (done == 0);
}

struct merg {
    char    l[L];
            FILE * b;
}          *ibuf[256];

merge (a, b) {
    static char merbufs[N][BUFSIZ];
    struct merg *p;
    register char  *cp,
                   *dp;
    register    i;
    struct merg **ip,
               *jp;
    char   *f;
    int     j;
    int     k,
            l;
    int     muflg;

    p = (struct merg   *) lspace;
    j = 0;
    for (i = a; i < b; i++) {
	f = setfil (i);
	if (f == 0)
	    p -> b = stdin;
	else {
	    if ((p -> b = fopen (f, "r")) == NULL)
		cant (f);
	    setbuf (p -> b, merbufs[i - a]);
	}
	ibuf[j] = p;
	if (!rline (p))
	    j++;
	p++;
    }

    do {
	i = j;
	qsort ((char **) ibuf, (char **) (ibuf + i));
	l = 0;
	while (i--) {
	    cp = ibuf[i] -> l;
	    if (*cp == '\0') {
		l = 1;
		if (rline (ibuf[i])) {
		    k = i;
		    while (++k < j)
			ibuf[k - 1] = ibuf[k];
		    j--;
		}
	    }
	}
    } while (l);

    muflg = mflg & uflg | cflg;
    i = j;
    while (i > 0) {
	cp = ibuf[i - 1] -> l;
	if (!cflg && (uflg == 0 || muflg ||
		    (*compare) (ibuf[i - 1] -> l, ibuf[i - 2] -> l)))
	    do
		putc (*cp, os);
	    while (*cp++ != '\n');
	if (muflg) {
	    cp = ibuf[i - 1] -> l;
	    dp = p -> l;
	    do {
	    } while ((*dp++ = *cp++) != '\n');
	}
	for (;;) {
	    if (rline (ibuf[i - 1])) {
		i--;
		if (i == 0)
		    break;
		if (i == 1)
		    muflg = uflg;
	    }
	    ip = &ibuf[i];
	    while (--ip > ibuf
		    && (*compare) (ip[0] -> l, ip[-1] -> l) < 0) {
		jp = *ip;
		*ip = *(ip - 1);
		*(ip - 1) = jp;
	    }
	    if (!muflg)
		break;
	    j = (*compare) (ibuf[i - 1] -> l, p -> l);
	    if (cflg) {
		if (j > 0)
		    disorder ("disorder: ", ibuf[i - 1] -> l);
		else
		    if (uflg && j == 0)
			disorder ("nonunique: ", ibuf[i - 1] -> l);
	    }
	    else
		if (j == 0)
		    continue;
	    break;
	}
    }
    p = (struct merg   *) lspace;
    for (i = a; i < b; i++) {
	fclose (p -> b);
	p++;
	if (i >= eargc)
	    unlink (setfil (i));
    }
    fclose (os);
}

rline (mp)
struct merg *mp;
{
    register char  *cp;
    register char  *ce;
    FILE * bp;
    register    c;

    bp = mp -> b;
    cp = mp -> l;
    ce = cp + L;
    do {
	c = getc (bp);
	if (c == EOF)
	    return (1);
	if (cp >= ce)
	    cp--;
	*cp++ = c;
    } while (c != '\n');
    return (0);
}

disorder (s, t)
char   *s,
       *t;
{
    register char  *u;
    for (u = t; *u != '\n'; u++);
    *u = 0;
    diag (s, t);
    term ();
}

newfile () {
    register char  *f;

    f = setfil (nfiles);
    if ((os = fopen (f, "w")) == NULL) {
	diag ("can't create ", f);
	term ();
    }
    setbuf (os, osbuf);
    nfiles++;
}

char   *
        setfil (i) {

    if      (i < eargc)
	if      (eargv[i][0] == '-' && eargv[i][1] == '\0')
	            return (0);
	else
	    return (eargv[i]);
    i -= eargc;
    filep[0] = i / 26 + 'a';
    filep[1] = i % 26 + 'a';
    return (file);
}

oldfile () {

    if (outfil) {
	if ((os = fopen (outfil, "w")) == NULL) {
	    diag ("can't create ", outfil);
	    term ();
	}
	setbuf (os, osbuf);
    }
    else
	os = stdout;
}

safeoutfil () {
    register int    i;
    struct stat obuf,
                ibuf;

    if (!mflg || outfil == 0)
	return;
    if (stat (outfil, &obuf) == -1)
	return;
    for (i = eargc - N; i < eargc; i++) {
    /*-N is suff., not nec.*/
	if (stat (eargv[i], &ibuf) == -1)
	    continue;
	if (obuf.st_dev == ibuf.st_dev &&
		obuf.st_ino == ibuf.st_ino)
	    unsafeout++;
    }
}

cant (f)
char   *f;
{

    diag ("can't open ", f);
    term ();
}

diag (s, t)
char   *s,
       *t;
{
    fputs (progname, stderr);
    fputs (": ", stderr);
    fputs (s, stderr);
    fputs (t, stderr);
    putc ('\n', stderr);
}

term () {
    register    i;

    signal (SIGQUIT, SIG_IGN);
    signal (SIGINT, SIG_IGN);
    signal (SIGHUP, SIG_IGN);
    signal (SIGTERM, SIG_IGN);
    if (nfiles == eargc)
	nfiles++;
    for (i = eargc; i <= nfiles; i++) {
    /* <= in case of interrupt */
	unlink (setfil (i));	/* with nfiles not updated */
    }
    exit (error);
}

cmp (i, j)
char   *i,
       *j;
{
    register char  *pa,
                   *pb;
    char   *skip ();
    char   *code,
           *ignore;
    int     a,
            b;
    int     k;
    char   *la,
           *lb;
    register int    sa;
    int     sb;
    char   *ipa,
	   *ipb,
           *jpa,
           *jpb;
    struct field   *fp;

    for (k = nfields > 0; k <= nfields; k++) {
	fp = &fields[k];
	pa = i;
	pb = j;
	if (k) {
	    la = skip (pa, fp, 1);
	    pa = skip (pa, fp, 0);
	    lb = skip (pb, fp, 1);
	    pb = skip (pb, fp, 0);
	}
	else {
	    la = eol (pa);
	    lb = eol (pb);
	}
	if (fp -> nflg || k == 0 && fp -> bflg[0]) {
	    while (blank (*pa))
		pa++;
	    while (blank (*pb))
		pb++;
	}
	if (fp -> nflg) {
	    sa = sb = fp -> rflg;
	    if (*pa == '-') {
		pa++;
		sa = -sa;
	    }
	    if (*pb == '-') {
		pb++;
		sb = -sb;
	    }
	    for (ipa = pa; ipa < la && isdigit (*ipa); ipa++);
	    for (ipb = pb; ipb < lb && isdigit (*ipb); ipb++);
	    jpa = ipa;
	    jpb = ipb;
	    a = 0;
	    if (sa == sb)
		while (ipa > pa && ipb > pb)
		    if (b = *--ipb - *--ipa)
			a = b;
	    while (ipa > pa)
		if (*--ipa != '0')
		    return (-sa);
	    while (ipb > pb)
		if (*--ipb != '0')
		    return (sb);
	    if (a)
		return (a * sa);
	    if (*(pa = jpa) == '.')
		pa++;
	    if (*(pb = jpb) == '.')
		pb++;
	    if (sa == sb)
		while (pa < la && isdigit (*pa)
			&& pb < lb && isdigit (*pb))
		    if (a = *pb++ - *pa++)
			return (a * sa);
	    while (pa < la && isdigit (*pa))
		if (*pa++ != '0')
		    return (-sa);
	    while (pb < lb && isdigit (*pb))
		if (*pb++ != '0')
		    return (sb);
	    continue;
	}
	code = fp -> code;
	ignore = fp -> ignore;
loop:
	while (ignore[*pa])
	    pa++;
	while (ignore[*pb])
	    pb++;
	if (pa >= la || *pa == '\n')
	    if (pb < lb && *pb != '\n')
		return (fp -> rflg);
	    else
		continue;
	if (pb >= lb || *pb == '\n')
	    return (-fp -> rflg);
	/* STUPID Ritchie compiler can't swallow whole expression */
	{ register c1 = code[*pb++], c2 = code[*pa++];
	sa = fp -> zflg ? (c1&0377) - (c2&0377) : lcmp (c1, c2);
	}
	if (sa == 0)
		goto loop;
	return (sa * fp -> rflg);
    }
    if (uflg)
	return (0);
    return (cmpa (i, j));
}

cmpa (pa, pb)
register char  *pa,
               *pb;
{
    while (*pa == *pb) {
	if (*pa++ == '\n')
	    return (0);
	pb++;
    }

    if (*pa == '\n' ) return fields[0].rflg;
    else if (*pb == '\n') return  -fields[0].rflg;
    else if (fields[0].zflg && (*pb&0377) > (*pa&0377)) return fields[0].rflg;
    else if (!fields[0].zflg && lcmp (*pb, *pa) > 0) return fields[0].rflg;
    else return -fields[0].rflg;
}

char   *
        skip (pp, fp, j)
struct field   *fp;
char   *pp;
{
    register    i;
    register char  *p;

    p = pp;
    if ((i = fp -> m[j]) < 0)
	return (eol (p));
    while (i-- > 0) {
	if (tabchar != 0) {
	    while (*p != tabchar)
		if (*p != '\n')
		    p++;
		else
		    goto ret;
	    p++;
	}
	else {
	    while (blank (*p))
		p++;
	    while (!blank (*p))
		if (*p != '\n')
		    p++;
		else
		    goto ret;
	}
    }
    if (fp -> bflg[j])
	while (blank (*p))
	    p++;
    i = fp -> n[j];
    while (i-- > 0) {
	if (*p != '\n')
	    p++;
	else
	    goto ret;
    }
ret:
    return (p);
}

char   *
        eol (p)
register char  *p;
{
    while (*p != '\n')
	p++;
    return (p);
}

copyproto () {
    register    i;
    register int   *p,
                   *q;

    p = (int *) & proto;
    q = (int *) & fields[nfields];
    for (i = 0; i < sizeof (proto) / sizeof (*p); i++)
	*q++ = *p++;
}

field (s, k)
char   *s;
{
    register struct field  *p;
    register    d;
    p = &fields[nfields];
    d = 0;
    for (; *s != 0; s++) {
	switch (*s) {
	    case '\0':
		return;

	    case 'b':
		p -> bflg[k]++;
		break;

	    case 'd':
		p -> ignore = dict + 128;
		break;

	    case 'f':
		p -> code = fold + 128;
		break;

	    case 'i':
		p -> ignore = nonprint + 128;
		break;

	    case 'c':
		cflg = 1;
		continue;

	    case 'm':
		mflg = 1;
		continue;

	    case 'n':
		p -> nflg++;
		break;

	    case 't':
		tabchar = *++s;
		if (tabchar == 0)
		    s--;
		continue;

	    case 'r':
		p -> rflg = -1;
		continue;

	    case 'u':
		uflg = 1;
		break;

	    case 'z':
		p -> zflg++;
		break;

	    case '.':
		if (p -> m[k] == -1)/* -m.n with m missing */
		    p -> m[k] = 0;
		d = &fields[0].n[0] - &fields[0].m[0];
		s++;

	    default:
		if (!isdigit (*s)) {
		    diag (
"usage: [-mucbdfinrz] [-tc] [+p1 [-p2]]... [-o file] [-T dir] [file]...",
"");
		    exit (1);
		}
		p -> m[k + d] = number (&s);
	}
	compare = cmp;
    }
}

number (ppa)
char  **ppa;
{
    int     n;
    register char  *pa;
    pa = *ppa;
    n = 0;
    while (isdigit (*pa)) {
	n = n * 10 + *pa - '0';
	*ppa = pa++;
    }
    return (n);
}

blank (c) {
    if (c == ' ' || c == '\t')
	return (1);
    return (0);
}

#define qsexc(p,q) t= *p;*p= *q;*q=t
#define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t

qsort (a, l)
char  **a,
      **l;
{
    register char **i,
                  **j;
    char  **k;
    char  **lp,
          **hp;
    int     c;
    char   *t;
    unsigned    n;



start:
    if ((n = l - a) <= 1)
	return;


    n /= 2;
    hp = lp = a + n;
    i = a;
    j = l - 1;


    for (;;) {
	if (i < lp) {
	    if ((c = (*compare) (*i, *lp)) == 0) {
		--lp;
		qsexc (i, lp);
		continue;
	    }
	    if (c < 0) {
		++i;
		continue;
	    }
	}

loop:
	if (j > hp) {
	    if ((c = (*compare) (*hp, *j)) == 0) {
		++hp;
		qsexc (hp, j);
		goto loop;
	    }
	    if (c > 0) {
		if (i == lp) {
		    ++hp;
		    qstexc (i, hp, j);
		    i = ++lp;
		    goto loop;
		}
		qsexc (i, j);
		--j;
		++i;
		continue;
	    }
	    --j;
	    goto loop;
	}


	if (i == lp) {
	    if (uflg)
		for (k = lp + 1; k <= hp;)
		    **k++ = '\0';
	    if (lp - a >= l - hp) {
		qsort (hp + 1, l);
		l = lp;
	    }
	    else {
		qsort (a, lp);
		a = hp + 1;
	    }
	    goto start;
	}


	--lp;
	qstexc (j, lp, i);
	j = --hp;
    }
}
=== CUT HERE =============================================================
__________________________________________________________________________
In-Real-Life: Andrew A. Chernov   |  Domain: ache@hq.demos.su,
Zodiac-Sign:  Virgo               |          ache%hq.demos.su@relay.eu.net
Organization: DEMOS Cooperative,  |  Phone:  +7 095 2312129
	      Moscow, USSR        |  Fax:    +7 095 2335016

--
__________________________________________________________________________
In-Real-Life: Andrew A. Chernov   |  Domain: ache@hq.demos.su,
Zodiac-Sign:  Virgo               |          ache%hq.demos.su@relay.eu.net
Organization: DEMOS Cooperative,  |  Phone:  +7 095 2312129