Virgin import (trimmed) of GNU Sort, textutils 2.0.21

3 files changed, 3353 insertions, 0 deletions

diff --git a/contrib/gnu-sort/src/sort.c b/contrib/gnu-sort/src/sort.c
new file mode 100644
index 0000000..a2b0ef16
--- /dev/null
+++ b/contrib/gnu-sort/src/sort.c
@@ -0,0 +1,2502 @@
+/* sort - sort lines of text (with all kinds of options).
+   Copyright (C) 88, 1991-2002 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+   Written December 1988 by Mike Haertel.
+   The author may be reached (Email) at the address mike@gnu.ai.mit.edu,
+   or (US mail) as Mike Haertel c/o Free Software Foundation.
+
+   Ørn E. Hansen added NLS support in 1997.  */
+
+#include <config.h>
+
+#include <getopt.h>
+#include <sys/types.h>
+#include <signal.h>
+#include <stdio.h>
+#include <assert.h>
+#include "system.h"
+#include "long-options.h"
+#include "error.h"
+#include "hard-locale.h"
+#include "human.h"
+#include "physmem.h"
+#include "posixver.h"
+#include "stdio-safer.h"
+#include "xmemcoll.h"
+#include "xstrtol.h"
+
+#if HAVE_SYS_RESOURCE_H
+# include <sys/resource.h>
+#endif
+#ifndef RLIMIT_DATA
+struct rlimit { size_t rlim_cur; };
+# define getrlimit(Resource, Rlp) (-1)
+#endif
+
+/* The official name of this program (e.g., no `g' prefix).  */
+#define PROGRAM_NAME "sort"
+
+#define AUTHORS N_ ("Mike Haertel and Paul Eggert")
+
+#if defined ENABLE_NLS && HAVE_LANGINFO_H
+# include <langinfo.h>
+#endif
+
+#ifndef SA_NOCLDSTOP
+# define sigprocmask(How, Set, Oset) /* empty */
+# define sigset_t int
+#endif
+
+#ifndef STDC_HEADERS
+double strtod ();
+#endif
+
+/* Undefine, to avoid warning about redefinition on some systems.  */
+/* FIXME: Remove these: use MIN/MAX from sys2.h.  */
+#undef min
+#define min(a, b) ((a) < (b) ? (a) : (b))
+#undef max
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+#define UCHAR_LIM (UCHAR_MAX + 1)
+#define UCHAR(c) ((unsigned char) (c))
+
+#ifndef DEFAULT_TMPDIR
+# define DEFAULT_TMPDIR "/tmp"
+#endif
+
+/* Use this as exit status in case of error, not EXIT_FAILURE.  This
+   is necessary because EXIT_FAILURE is usually 1 and POSIX requires
+   that sort exit with status 1 IFF invoked with -c and the input is
+   not properly sorted.  Any other irregular exit must exit with a
+   status code greater than 1.  */
+#define SORT_FAILURE 2
+#define SORT_OUT_OF_ORDER 1
+
+#define C_DECIMAL_POINT '.'
+#define NEGATION_SIGN   '-'
+#define NUMERIC_ZERO    '0'
+
+#ifdef ENABLE_NLS
+
+static char decimal_point;
+static int th_sep; /* if CHAR_MAX + 1, then there is no thousands separator */
+
+/* Nonzero if the corresponding locales are hard.  */
+static int hard_LC_COLLATE;
+# if HAVE_NL_LANGINFO
+static int hard_LC_TIME;
+# endif
+
+# define IS_THOUSANDS_SEP(x) ((x) == th_sep)
+
+#else
+
+# define decimal_point C_DECIMAL_POINT
+# define IS_THOUSANDS_SEP(x) 0
+
+#endif
+
+#define NONZERO(x) (x != 0)
+
+/* The kind of blanks for '-b' to skip in various options. */
+enum blanktype { bl_start, bl_end, bl_both };
+
+/* The character marking end of line. Default to \n. */
+static int eolchar = '\n';
+
+/* Lines are held in core as counted strings. */
+struct line
+{
+  char *text;			/* Text of the line. */
+  size_t length;		/* Length including final newline. */
+  char *keybeg;			/* Start of first key. */
+  char *keylim;			/* Limit of first key. */
+};
+
+/* Input buffers. */
+struct buffer
+{
+  char *buf;			/* Dynamically allocated buffer,
+				   partitioned into 3 regions:
+				   - input data;
+				   - unused area;
+				   - an array of lines, in reverse order.  */
+  size_t used;			/* Number of bytes used for input data.  */
+  size_t nlines;		/* Number of lines in the line array.  */
+  size_t alloc;			/* Number of bytes allocated. */
+  size_t left;			/* Number of bytes left from previous reads. */
+  size_t line_bytes;		/* Number of bytes to reserve for each line. */
+  int eof;			/* An EOF has been read.  */
+};
+
+struct keyfield
+{
+  size_t sword;			/* Zero-origin 'word' to start at. */
+  size_t schar;			/* Additional characters to skip. */
+  int skipsblanks;		/* Skip leading white space at start. */
+  size_t eword;			/* Zero-origin first word after field. */
+  size_t echar;			/* Additional characters in field. */
+  int skipeblanks;		/* Skip trailing white space at finish. */
+  int *ignore;			/* Boolean array of characters to ignore. */
+  char *translate;		/* Translation applied to characters. */
+  int numeric;			/* Flag for numeric comparison.  Handle
+				   strings of digits with optional decimal
+				   point, but no exponential notation. */
+  int general_numeric;		/* Flag for general, numeric comparison.
+				   Handle numbers in exponential notation. */
+  int month;			/* Flag for comparison by month name. */
+  int reverse;			/* Reverse the sense of comparison. */
+  struct keyfield *next;	/* Next keyfield to try. */
+};
+
+struct month
+{
+  char *name;
+  int val;
+};
+
+/* The name this program was run with. */
+char *program_name;
+
+/* FIXME: None of these tables work with multibyte character sets.
+   Also, there are many other bugs when handling multibyte characters,
+   or even unibyte encodings where line boundaries are not in the
+   initial shift state.  One way to fix this is to rewrite `sort' to
+   use wide characters internally, but doing this with good
+   performance is a bit tricky.  */
+
+/* Table of white space. */
+static int blanks[UCHAR_LIM];
+
+/* Table of non-printing characters. */
+static int nonprinting[UCHAR_LIM];
+
+/* Table of non-dictionary characters (not letters, digits, or blanks). */
+static int nondictionary[UCHAR_LIM];
+
+/* Translation table folding lower case to upper.  */
+static char fold_toupper[UCHAR_LIM];
+
+#define MONTHS_PER_YEAR 12
+
+#if defined ENABLE_NLS && HAVE_NL_LANGINFO
+# define MONTHTAB_CONST /* empty */
+#else
+# define MONTHTAB_CONST const
+#endif
+
+/* Table mapping month names to integers.
+   Alphabetic order allows binary search. */
+static MONTHTAB_CONST struct month monthtab[] =
+{
+  {"APR", 4},
+  {"AUG", 8},
+  {"DEC", 12},
+  {"FEB", 2},
+  {"JAN", 1},
+  {"JUL", 7},
+  {"JUN", 6},
+  {"MAR", 3},
+  {"MAY", 5},
+  {"NOV", 11},
+  {"OCT", 10},
+  {"SEP", 9}
+};
+
+/* During the merge phase, the number of files to merge at once. */
+#define NMERGE 16
+
+/* Minimum size for a merge or check buffer.  */
+#define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
+
+/* Minimum sort size; the code might not work with smaller sizes.  */
+#define MIN_SORT_SIZE (NMERGE * MIN_MERGE_BUFFER_SIZE)
+
+/* The number of bytes needed for a merge or check buffer, which can
+   function relatively efficiently even if it holds only one line.  If
+   a longer line is seen, this value is increased.  */
+static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
+
+/* The approximate maximum number of bytes of main memory to use, as
+   specified by the user.  Zero if the user has not specified a size.  */
+static size_t sort_size;
+
+/* The guessed size for non-regular files.  */
+#define INPUT_FILE_SIZE_GUESS (1024 * 1024)
+
+/* Array of directory names in which any temporary files are to be created. */
+static char const **temp_dirs;
+
+/* Number of temporary directory names used.  */
+static size_t temp_dir_count;
+
+/* Number of allocated slots in temp_dirs.  */
+static size_t temp_dir_alloc;
+
+/* Our process ID.  */
+static pid_t process_id;
+
+/* Flag to reverse the order of all comparisons. */
+static int reverse;
+
+/* Flag for stable sort.  This turns off the last ditch bytewise
+   comparison of lines, and instead leaves lines in the same order
+   they were read if all keys compare equal.  */
+static int stable;
+
+/* Tab character separating fields.  If NUL, then fields are separated
+   by the empty string between a non-whitespace character and a whitespace
+   character. */
+static char tab;
+
+/* Flag to remove consecutive duplicate lines from the output.
+   Only the last of a sequence of equal lines will be output. */
+static int unique;
+
+/* Nonzero if any of the input files are the standard input. */
+static int have_read_stdin;
+
+/* List of key field comparisons to be tried.  */
+static struct keyfield *keylist;
+
+void
+usage (int status)
+{
+  if (status != 0)
+    fprintf (stderr, _("Try `%s --help' for more information.\n"),
+	     program_name);
+  else
+    {
+      printf (_("\
+Usage: %s [OPTION]... [FILE]...\n\
+"),
+	      program_name);
+      fputs (_("\
+Write sorted concatenation of all FILE(s) to standard output.\n\
+\n\
+Ordering options:\n\
+\n\
+"), stdout);
+      fputs (_("\
+Mandatory arguments to long options are mandatory for short options too.\n\
+"), stdout);
+      fputs (_("\
+  -b, --ignore-leading-blanks ignore leading blanks\n\
+  -d, --dictionary-order      consider only blanks and alphanumeric characters\n\
+  -f, --ignore-case           fold lower case to upper case characters\n\
+"), stdout);
+      fputs (_("\
+  -g, --general-numeric-sort  compare according to general numerical value\n\
+  -i, --ignore-nonprinting    consider only printable characters\n\
+  -M, --month-sort            compare (unknown) < `JAN' < ... < `DEC'\n\
+  -n, --numeric-sort          compare according to string numerical value\n\
+  -r, --reverse               reverse the result of comparisons\n\
+\n\
+"), stdout);
+      fputs (_("\
+Other options:\n\
+\n\
+  -c, --check               check whether input is sorted; do not sort\n\
+  -k, --key=POS1[,POS2]     start a key at POS1, end it at POS 2 (origin 1)\n\
+  -m, --merge               merge already sorted files; do not sort\n\
+  -o, --output=FILE         write result to FILE instead of standard output\n\
+  -s, --stable              stabilize sort by disabling last-resort comparison\n\
+  -S, --buffer-size=SIZE    use SIZE for main memory buffer\n\
+"), stdout);
+      printf (_("\
+  -t, --field-separator=SEP use SEP instead of non- to whitespace transition\n\
+  -T, --temporary-directory=DIR  use DIR for temporaries, not $TMPDIR or %s\n\
+                              multiple options specify multiple directories\n\
+  -u, --unique              with -c: check for strict ordering\n\
+                              otherwise: output only the first of an equal run\n\
+"), DEFAULT_TMPDIR);
+      fputs (_("\
+  -z, --zero-terminated     end lines with 0 byte, not newline\n\
+"), stdout);
+      fputs (HELP_OPTION_DESCRIPTION, stdout);
+      fputs (VERSION_OPTION_DESCRIPTION, stdout);
+      fputs (_("\
+\n\
+POS is F[.C][OPTS], where F is the field number and C the character position\n\
+in the field.  OPTS is one or more single-letter ordering options, which\n\
+override global ordering options for that key.  If no key is given, use the\n\
+entire line as the key.\n\
+\n\
+SIZE may be followed by the following multiplicative suffixes:\n\
+"), stdout);
+      fputs (_("\
+% 1% of memory, b 1, K 1024 (default), and so on for M, G, T, P, E, Z, Y.\n\
+\n\
+With no FILE, or when FILE is -, read standard input.\n\
+\n\
+*** WARNING ***\n\
+The locale specified by the environment affects sort order.\n\
+Set LC_ALL=C to get the traditional sort order that uses\n\
+native byte values.\n\
+"), stdout );
+      puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
+    }
+  /* Don't use EXIT_FAILURE here in case it is defined to be 1.
+     POSIX requires that sort return 1 IFF invoked with -c and
+     the input is not properly sorted.  */
+  assert (status == 0 || status == SORT_FAILURE);
+  exit (status);
+}
+
+#define COMMON_SHORT_OPTIONS "-bcdfgik:mMno:rsS:t:T:uz"
+
+static struct option const long_options[] =
+{
+  {"ignore-leading-blanks", no_argument, NULL, 'b'},
+  {"check", no_argument, NULL, 'c'},
+  {"dictionary-order", no_argument, NULL, 'd'},
+  {"ignore-case", no_argument, NULL, 'f'},
+  {"general-numeric-sort", no_argument, NULL, 'g'},
+  {"ignore-nonprinting", no_argument, NULL, 'i'},
+  {"key", required_argument, NULL, 'k'},
+  {"merge", no_argument, NULL, 'm'},
+  {"month-sort", no_argument, NULL, 'M'},
+  {"numeric-sort", no_argument, NULL, 'n'},
+  {"output", required_argument, NULL, 'o'},
+  {"reverse", no_argument, NULL, 'r'},
+  {"stable", no_argument, NULL, 's'},
+  {"buffer-size", required_argument, NULL, 'S'},
+  {"field-separator", required_argument, NULL, 't'},
+  {"temporary-directory", required_argument, NULL, 'T'},
+  {"unique", no_argument, NULL, 'u'},
+  {"zero-terminated", no_argument, NULL, 'z'},
+  {GETOPT_HELP_OPTION_DECL},
+  {GETOPT_VERSION_OPTION_DECL},
+  {0, 0, 0, 0},
+};
+
+/* The set of signals that are caught.  */
+static sigset_t caught_signals;
+
+/* The list of temporary files. */
+struct tempnode
+{
+  struct tempnode *volatile next;
+  char name[1];  /* Actual size is 1 + file name length.  */
+};
+static struct tempnode *volatile temphead;
+
+/* Clean up any remaining temporary files. */
+
+static void
+cleanup (void)
+{
+  struct tempnode *node;
+
+  for (node = temphead; node; node = node->next)
+    unlink (node->name);
+}
+
+/* Report MESSAGE for FILE, then clean up and exit.  */
+
+static void die PARAMS ((char const *, char const *)) ATTRIBUTE_NORETURN;
+static void
+die (char const *message, char const *file)
+{
+  error (0, errno, "%s: %s", message, file);
+  exit (SORT_FAILURE);
+}
+
+/* Create a new temporary file, returning its newly allocated name.
+   Store into *PFP a stream open for writing.  */
+
+static char *
+create_temp_file (FILE **pfp)
+{
+  static char const slashbase[] = "/sortXXXXXX";
+  static size_t temp_dir_index;
+  sigset_t oldset;
+  int fd;
+  int saved_errno;
+  char const *temp_dir = temp_dirs[temp_dir_index];
+  size_t len = strlen (temp_dir);
+  struct tempnode *node =
+    (struct tempnode *) xmalloc (sizeof node->next + len + sizeof slashbase);
+  char *file = node->name;
+
+  memcpy (file, temp_dir, len);
+  memcpy (file + len, slashbase, sizeof slashbase);
+  node->next = temphead;
+  if (++temp_dir_index == temp_dir_count)
+    temp_dir_index = 0;
+
+  /* Create the temporary file in a critical section, to avoid races.  */
+  sigprocmask (SIG_BLOCK, &caught_signals, &oldset);
+  fd = mkstemp (file);
+  if (0 <= fd)
+    temphead = node;
+  saved_errno = errno;
+  sigprocmask (SIG_SETMASK, &oldset, NULL);
+  errno = saved_errno;
+
+  if (fd < 0 || (*pfp = fdopen (fd, "w")) == NULL)
+    die (_("cannot create temporary file"), file);
+
+  return file;
+}
+
+static FILE *
+xfopen (const char *file, const char *how)
+{
+  FILE *fp;
+
+  if (STREQ (file, "-"))
+    {
+      if (*how == 'r')
+	{
+	  have_read_stdin = 1;
+	  fp = stdin;
+	}
+      else
+	fp = stdout;
+    }
+  else
+    {
+      if ((fp = fopen_safer (file, how)) == NULL)
+	die (_("open failed"), file);
+    }
+
+  return fp;
+}
+
+/* Close FP, whose name is FILE, and report any errors.  */
+
+static void
+xfclose (FILE *fp, char const *file)
+{
+  if (fp == stdin)
+    {
+      /* Allow reading stdin from tty more than once. */
+      if (feof (fp))
+	clearerr (fp);
+    }
+  else
+    {
+      if (fclose (fp) != 0)
+	die (_("close failed"), file);
+    }
+}
+
+static void
+write_bytes (const char *buf, size_t n_bytes, FILE *fp, const char *output_file)
+{
+  if (fwrite (buf, 1, n_bytes, fp) != n_bytes)
+    die (_("write failed"), output_file);
+}
+
+/* Append DIR to the array of temporary directory names.  */
+static void
+add_temp_dir (char const *dir)
+{
+  if (temp_dir_count == temp_dir_alloc)
+    {
+      temp_dir_alloc = temp_dir_alloc ? temp_dir_alloc * 2 : 16;
+      temp_dirs = xrealloc (temp_dirs, sizeof (temp_dirs) * temp_dir_alloc);
+    }
+
+  temp_dirs[temp_dir_count++] = dir;
+}
+
+/* Search through the list of temporary files for NAME;
+   remove it if it is found on the list. */
+
+static void
+zaptemp (const char *name)
+{
+  struct tempnode *volatile *pnode;
+  struct tempnode *node;
+
+  for (pnode = &temphead; (node = *pnode); pnode = &node->next)
+    if (node->name == name)
+      {
+	unlink (name);
+	*pnode = node->next;
+	free ((char *) node);
+	break;
+      }
+}
+
+#if defined ENABLE_NLS && HAVE_NL_LANGINFO
+
+static int
+struct_month_cmp (const void *m1, const void *m2)
+{
+  return strcmp (((const struct month *) m1)->name,
+		 ((const struct month *) m2)->name);
+}
+
+#endif
+
+/* Initialize the character class tables. */
+
+static void
+inittables (void)
+{
+  int i;
+
+  for (i = 0; i < UCHAR_LIM; ++i)
+    {
+      if (ISBLANK (i))
+	blanks[i] = 1;
+      if (!ISPRINT (i))
+	nonprinting[i] = 1;
+      if (!ISALNUM (i) && !ISBLANK (i))
+	nondictionary[i] = 1;
+      if (ISLOWER (i))
+	fold_toupper[i] = toupper (i);
+      else
+	fold_toupper[i] = i;
+    }
+
+#if defined ENABLE_NLS && HAVE_NL_LANGINFO
+  /* If we're not in the "C" locale, read different names for months.  */
+  if (hard_LC_TIME)
+    {
+      for (i = 0; i < MONTHS_PER_YEAR; i++)
+	{
+	  char *s;
+	  size_t s_len;
+	  size_t j;
+	  char *name;
+
+	  s = (char *) nl_langinfo (ABMON_1 + i);
+	  s_len = strlen (s);
+	  monthtab[i].name = name = (char *) xmalloc (s_len + 1);
+	  monthtab[i].val = i + 1;
+
+	  for (j = 0; j < s_len; j++)
+	    name[j] = fold_toupper[UCHAR (s[j])];
+	  name[j] = '\0';
+	}
+      qsort ((void *) monthtab, MONTHS_PER_YEAR,
+	     sizeof (struct month), struct_month_cmp);
+    }
+#endif /* NLS */
+}
+
+/* Specify the amount of main memory to use when sorting.  */
+static void
+specify_sort_size (char const *s)
+{
+  uintmax_t n;
+  char *suffix;
+  enum strtol_error e = xstrtoumax (s, &suffix, 10, &n, "EgGkKmMPtTYZ");
+
+  /* The default unit is KiB.  */
+  if (e == LONGINT_OK && ISDIGIT (suffix[-1]))
+    {
+      if (n <= UINTMAX_MAX / 1024)
+	n *= 1024;
+      else
+	e = LONGINT_OVERFLOW;
+    }
+
+  /* A 'b' suffix means bytes; a '%' suffix means percent of memory.  */
+  if (e == LONGINT_INVALID_SUFFIX_CHAR && ISDIGIT (suffix[-1]) && ! suffix[1])
+    switch (suffix[0])
+      {
+      case 'b':
+	e = LONGINT_OK;
+	break;
+
+      case '%':
+	{
+	  double mem = physmem_total () * n / 100;
+
+	  /* Use "<", not "<=", to avoid problems with rounding.  */
+	  if (mem < UINTMAX_MAX)
+	    {
+	      n = mem;
+	      e = LONGINT_OK;
+	    }
+	  else
+	    e = LONGINT_OVERFLOW;
+	}
+	break;
+      }
+
+  if (e == LONGINT_OK)
+    {
+      sort_size = n;
+      if (sort_size == n)
+	{
+	  sort_size = MAX (sort_size, MIN_SORT_SIZE);
+	  return;
+	}
+
+      e = LONGINT_OVERFLOW;
+    }
+
+  STRTOL_FATAL_ERROR (s, _("sort size"), e);
+}
+
+/* Return the default sort size.  */
+static size_t
+default_sort_size (void)
+{
+  /* Let MEM be available memory or 1/8 of total memory, whichever
+     is greater.  */
+  double avail = physmem_available ();
+  double total = physmem_total ();
+  double mem = MAX (avail, total / 8);
+  struct rlimit rlimit;
+
+  /* Let SIZE be MEM, but no more than the maximum object size or
+     system resource limits.  Avoid the MIN macro here, as it is not
+     quite right when only one argument is floating point.  Don't
+     bother to check for values like RLIM_INFINITY since in practice
+     they are not much less than SIZE_MAX.  */
+  size_t size = SIZE_MAX;
+  if (mem < size)
+    size = mem;
+  if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
+    size = rlimit.rlim_cur;
+#ifdef RLIMIT_AS
+  if (getrlimit (RLIMIT_AS, &rlimit) == 0 && rlimit.rlim_cur < size)
+    size = rlimit.rlim_cur;
+#endif
+
+  /* Leave a large safety margin for the above limits, as failure can
+     occur when they are exceeded.  */
+  size /= 2;
+
+#ifdef RLIMIT_RSS
+  /* Leave a 1/16 margin for RSS to leave room for code, stack, etc.
+     Exceeding RSS is not fatal, but can be quite slow.  */
+  if (getrlimit (RLIMIT_RSS, &rlimit) == 0 && rlimit.rlim_cur / 16 * 15 < size)
+    size = rlimit.rlim_cur / 16 * 15;
+#endif
+
+  /* Use no less than the minimum.  */
+  return MAX (size, MIN_SORT_SIZE);
+}
+
+/* Return the sort buffer size to use with the input files identified
+   by FPS and FILES, which are alternate paths to the same files.
+   NFILES gives the number of input files; NFPS may be less.  Assume
+   that each input line requires LINE_BYTES extra bytes' worth of line
+   information.  Return at most SIZE_BOUND.  */
+
+static size_t
+sort_buffer_size (FILE *const *fps, int nfps,
+		  char *const *files, int nfiles,
+		  size_t line_bytes, size_t size_bound)
+{
+  /* In the worst case, each input byte is a newline.  */
+  size_t worst_case_per_input_byte = line_bytes + 1;
+
+  /* Keep enough room for one extra input line and an extra byte.
+     This extra room might be needed when preparing to read EOF.  */
+  size_t size = worst_case_per_input_byte + 1;
+
+  int i;
+
+  for (i = 0; i < nfiles; i++)
+    {
+      struct stat st;
+      off_t file_size;
+      size_t worst_case;
+
+      if ((i < nfps ? fstat (fileno (fps[i]), &st)
+	   : strcmp (files[i], "-") == 0 ? fstat (STDIN_FILENO, &st)
+	   : stat (files[i], &st))
+	  != 0)
+	die (_("stat failed"), files[i]);
+
+      file_size = S_ISREG (st.st_mode) ? st.st_size : INPUT_FILE_SIZE_GUESS;
+
+      /* Add the amount of memory needed to represent the worst case
+	 where the input consists entirely of newlines followed by a
+	 single non-newline.  Check for overflow.  */
+      worst_case = file_size * worst_case_per_input_byte + 1;
+      if (file_size != worst_case / worst_case_per_input_byte
+	  || size_bound - size <= worst_case)
+	return size_bound;
+      size += worst_case;
+    }
+
+  return size;
+}
+
+/* Initialize BUF.  Reserve LINE_BYTES bytes for each line; LINE_BYTES
+   must be at least sizeof (struct line).  Allocate ALLOC bytes
+   initially.  */
+
+static void
+initbuf (struct buffer *buf, size_t line_bytes, size_t alloc)
+{
+  /* Ensure that the line array is properly aligned.  If the desired
+     size cannot be allocated, repeatedly halve it until allocation
+     succeeds.  The smaller allocation may hurt overall performance,
+     but that's better than failing.  */
+  for (;;)
+    {
+      alloc += sizeof (struct line) - alloc % sizeof (struct line);
+      buf->buf = malloc (alloc);
+      if (buf->buf)
+	break;
+      alloc /= 2;
+      if (alloc <= line_bytes + 1)
+	xalloc_die ();
+    }
+
+  buf->line_bytes = line_bytes;
+  buf->alloc = alloc;
+  buf->used = buf->left = buf->nlines = 0;
+  buf->eof = 0;
+}
+
+/* Return one past the limit of the line array.  */
+
+static inline struct line *
+buffer_linelim (struct buffer const *buf)
+{
+  return (struct line *) (buf->buf + buf->alloc);
+}
+
+/* Return a pointer to the first character of the field specified
+   by KEY in LINE. */
+
+static char *
+begfield (const struct line *line, const struct keyfield *key)
+{
+  register char *ptr = line->text, *lim = ptr + line->length - 1;
+  register size_t sword = key->sword;
+  register size_t schar = key->schar;
+
+  if (tab)
+    while (ptr < lim && sword--)
+      {
+	while (ptr < lim && *ptr != tab)
+	  ++ptr;
+	if (ptr < lim)
+	  ++ptr;
+      }
+  else
+    while (ptr < lim && sword--)
+      {
+	while (ptr < lim && blanks[UCHAR (*ptr)])
+	  ++ptr;
+	while (ptr < lim && !blanks[UCHAR (*ptr)])
+	  ++ptr;
+      }
+
+  if (key->skipsblanks)
+    while (ptr < lim && blanks[UCHAR (*ptr)])
+      ++ptr;
+
+  if (schar < lim - ptr)
+    ptr += schar;
+  else
+    ptr = lim;
+
+  return ptr;
+}
+
+/* Return the limit of (a pointer to the first character after) the field
+   in LINE specified by KEY. */
+
+static char *
+limfield (const struct line *line, const struct keyfield *key)
+{
+  register char *ptr = line->text, *lim = ptr + line->length - 1;
+  register size_t eword = key->eword, echar = key->echar;
+
+  /* Note: from the POSIX spec:
+     The leading field separator itself is included in
+     a field when -t is not used.  FIXME: move this comment up... */
+
+  /* Move PTR past EWORD fields or to one past the last byte on LINE,
+     whichever comes first.  If there are more than EWORD fields, leave
+     PTR pointing at the beginning of the field having zero-based index,
+     EWORD.  If a delimiter character was specified (via -t), then that
+     `beginning' is the first character following the delimiting TAB.
+     Otherwise, leave PTR pointing at the first `blank' character after
+     the preceding field.  */
+  if (tab)
+    while (ptr < lim && eword--)
+      {
+	while (ptr < lim && *ptr != tab)
+	  ++ptr;
+	if (ptr < lim && (eword | echar))
+	  ++ptr;
+      }
+  else
+    while (ptr < lim && eword--)
+      {
+	while (ptr < lim && blanks[UCHAR (*ptr)])
+	  ++ptr;
+	while (ptr < lim && !blanks[UCHAR (*ptr)])
+	  ++ptr;
+      }
+
+#ifdef POSIX_UNSPECIFIED
+  /* The following block of code makes GNU sort incompatible with
+     standard Unix sort, so it's ifdef'd out for now.
+     The POSIX spec isn't clear on how to interpret this.
+     FIXME: request clarification.
+
+     From: kwzh@gnu.ai.mit.edu (Karl Heuer)
+     Date: Thu, 30 May 96 12:20:41 -0400
+
+     [...]I believe I've found another bug in `sort'.
+
+     $ cat /tmp/sort.in
+     a b c 2 d
+     pq rs 1 t
+     $ textutils-1.15/src/sort +0.6 -0.7 </tmp/sort.in
+     a b c 2 d
+     pq rs 1 t
+     $ /bin/sort +0.6 -0.7 </tmp/sort.in
+     pq rs 1 t
+     a b c 2 d
+
+     Unix sort produced the answer I expected: sort on the single character
+     in column 6.  GNU sort produced different results, because it disagrees
+     on the interpretation of the key-end spec "-M.N".  Unix sort reads this
+     as "skip M fields, then N characters"; but GNU sort wants it to mean
+     "skip M fields, then either N characters or the rest of the current
+     field, whichever comes first".  This extra clause applies only to
+     key-ends, not key-starts.
+     */
+
+  /* Make LIM point to the end of (one byte past) the current field.  */
+  if (tab)
+    {
+      char *newlim;
+      newlim = memchr (ptr, tab, lim - ptr);
+      if (newlim)
+	lim = newlim;
+    }
+  else
+    {
+      char *newlim;
+      newlim = ptr;
+      while (newlim < lim && blanks[UCHAR (*newlim)])
+	++newlim;
+      while (newlim < lim && !blanks[UCHAR (*newlim)])
+	++newlim;
+      lim = newlim;
+    }
+#endif
+
+  /* If we're skipping leading blanks, don't start counting characters
+     until after skipping past any leading blanks.  */
+  if (key->skipsblanks)
+    while (ptr < lim && blanks[UCHAR (*ptr)])
+      ++ptr;
+
+  /* Advance PTR by ECHAR (if possible), but no further than LIM.  */
+  if (echar < lim - ptr)
+    ptr += echar;
+  else
+    ptr = lim;
+
+  return ptr;
+}
+
+/* FIXME */
+
+static void
+trim_trailing_blanks (const char *a_start, char **a_end)
+{
+  while (*a_end > a_start && blanks[UCHAR (*(*a_end - 1))])
+    --(*a_end);
+}
+
+/* Fill BUF reading from FP, moving buf->left bytes from the end
+   of buf->buf to the beginning first.  If EOF is reached and the
+   file wasn't terminated by a newline, supply one.  Set up BUF's line
+   table too.  FILE is the name of the file corresponding to FP.
+   Return nonzero if some input was read.  */
+
+static int
+fillbuf (struct buffer *buf, register FILE *fp, char const *file)
+{
+  struct keyfield const *key = keylist;
+  char eol = eolchar;
+  size_t line_bytes = buf->line_bytes;
+  size_t mergesize = merge_buffer_size - MIN_MERGE_BUFFER_SIZE;
+
+  if (buf->eof)
+    return 0;
+
+  if (buf->used != buf->left)
+    {
+      memmove (buf->buf, buf->buf + buf->used - buf->left, buf->left);
+      buf->used = buf->left;
+      buf->nlines = 0;
+    }
+
+  for (;;)
+    {
+      char *ptr = buf->buf + buf->used;
+      struct line *linelim = buffer_linelim (buf);
+      struct line *line = linelim - buf->nlines;
+      size_t avail = (char *) linelim - buf->nlines * line_bytes - ptr;
+      char *line_start = buf->nlines ? line->text + line->length : buf->buf;
+
+      while (line_bytes + 1 < avail)
+	{
+	  /* Read as many bytes as possible, but do not read so many
+	     bytes that there might not be enough room for the
+	     corresponding line array.  The worst case is when the
+	     rest of the input file consists entirely of newlines,
+	     except that the last byte is not a newline.  */
+	  size_t readsize = (avail - 1) / (line_bytes + 1);
+	  size_t bytes_read = fread (ptr, 1, readsize, fp);
+	  char *ptrlim = ptr + bytes_read;
+	  char *p;
+	  avail -= bytes_read;
+
+	  if (bytes_read != readsize)
+	    {
+	      if (ferror (fp))
+		die (_("read failed"), file);
+	      if (feof (fp))
+		{
+		  buf->eof = 1;
+		  if (buf->buf == ptrlim)
+		    return 0;
+		  if (ptrlim[-1] != eol)
+		    *ptrlim++ = eol;
+		}
+	    }
+
+	  /* Find and record each line in the just-read input.  */
+	  while ((p = memchr (ptr, eol, ptrlim - ptr)))
+	    {
+	      ptr = p + 1;
+	      line--;
+	      line->text = line_start;
+	      line->length = ptr - line_start;
+	      mergesize = MAX (mergesize, line->length);
+	      avail -= line_bytes;
+
+	      if (key)
+		{
+		  /* Precompute the position of the first key for
+                     efficiency. */
+		  line->keylim = key->eword == -1 ? p : limfield (line, key);
+
+		  if (key->sword != -1)
+		    line->keybeg = begfield (line, key);
+		  else
+		    {
+		      if (key->skipsblanks)
+			while (blanks[UCHAR (*line_start)])
+			  line_start++;
+		      line->keybeg = line_start;
+		    }
+		  if (key->skipeblanks)
+		    trim_trailing_blanks (line->keybeg, &line->keylim);
+		}
+
+	      line_start = ptr;
+	    }
+
+	  ptr = ptrlim;
+	  if (buf->eof)
+	    break;
+	}
+
+      buf->used = ptr - buf->buf;
+      buf->nlines = buffer_linelim (buf) - line;
+      if (buf->nlines != 0)
+	{
+	  buf->left = ptr - line_start;
+	  merge_buffer_size = mergesize + MIN_MERGE_BUFFER_SIZE;
+	  return 1;
+	}
+
+      /* The current input line is too long to fit in the buffer.
+	 Double the buffer size and try again.  */
+      if (2 * buf->alloc < buf->alloc)
+	xalloc_die ();
+      buf->alloc *= 2;
+      buf->buf = xrealloc (buf->buf, buf->alloc);
+    }
+}
+
+/* Compare strings A and B containing decimal fractions < 1.  Each string
+   should begin with a decimal point followed immediately by the digits
+   of the fraction.  Strings not of this form are considered to be zero. */
+
+/* The goal here, is to take two numbers a and b... compare these
+   in parallel.  Instead of converting each, and then comparing the
+   outcome.  Most likely stopping the comparison before the conversion
+   is complete.  The algorithm used, in the old sort:
+
+   Algorithm: fraccompare
+   Action   : compare two decimal fractions
+   accepts  : char *a, char *b
+   returns  : -1 if a<b, 0 if a=b, 1 if a>b.
+   implement:
+
+   if *a == decimal_point AND *b == decimal_point
+     find first character different in a and b.
+     if both are digits, return the difference *a - *b.
+     if *a is a digit
+       skip past zeros
+       if digit return 1, else 0
+     if *b is a digit
+       skip past zeros
+       if digit return -1, else 0
+   if *a is a decimal_point
+     skip past decimal_point and zeros
+     if digit return 1, else 0
+   if *b is a decimal_point
+     skip past decimal_point and zeros
+     if digit return -1, else 0
+   return 0 */
+
+static int
+fraccompare (register const char *a, register const char *b)
+{
+  if (*a == decimal_point && *b == decimal_point)
+    {
+      while (*++a == *++b)
+	if (! ISDIGIT (*a))
+	  return 0;
+      if (ISDIGIT (*a) && ISDIGIT (*b))
+	return *a - *b;
+      if (ISDIGIT (*a))
+	goto a_trailing_nonzero;
+      if (ISDIGIT (*b))
+	goto b_trailing_nonzero;
+      return 0;
+    }
+  else if (*a++ == decimal_point)
+    {
+    a_trailing_nonzero:
+      while (*a == NUMERIC_ZERO)
+	a++;
+      return ISDIGIT (*a);
+    }
+  else if (*b++ == decimal_point)
+    {
+    b_trailing_nonzero:
+      while (*b == NUMERIC_ZERO)
+	b++;
+      return - ISDIGIT (*b);
+    }
+  return 0;
+}
+
+/* Compare strings A and B as numbers without explicitly converting them to
+   machine numbers.  Comparatively slow for short strings, but asymptotically
+   hideously fast. */
+
+static int
+numcompare (register const char *a, register const char *b)
+{
+  register int tmpa, tmpb, tmp;
+  register size_t loga, logb;
+
+  tmpa = *a;
+  tmpb = *b;
+
+  while (blanks[UCHAR (tmpa)])
+    tmpa = *++a;
+  while (blanks[UCHAR (tmpb)])
+    tmpb = *++b;
+
+  if (tmpa == NEGATION_SIGN)
+    {
+      do
+	tmpa = *++a;
+      while (tmpa == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpa));
+      if (tmpb != NEGATION_SIGN)
+	{
+	  if (tmpa == decimal_point)
+	    do
+	      tmpa = *++a;
+	    while (tmpa == NUMERIC_ZERO);
+	  if (ISDIGIT (tmpa))
+	    return -1;
+	  while (tmpb == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpb))
+	    tmpb = *++b;
+	  if (tmpb == decimal_point)
+	    do
+	      tmpb = *++b;
+	    while (tmpb == NUMERIC_ZERO);
+	  if (ISDIGIT (tmpb))
+	    return -1;
+	  return 0;
+	}
+      do
+	tmpb = *++b;
+      while (tmpb == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpb));
+
+      while (tmpa == tmpb && ISDIGIT (tmpa))
+	{
+	  do
+	    tmpa = *++a;
+	  while (IS_THOUSANDS_SEP (tmpa));
+	  do
+	    tmpb = *++b;
+	  while (IS_THOUSANDS_SEP (tmpb));
+	}
+
+      if ((tmpa == decimal_point && !ISDIGIT (tmpb))
+	  || (tmpb == decimal_point && !ISDIGIT (tmpa)))
+	return -fraccompare (a, b);
+
+      tmp = tmpb - tmpa;
+
+      for (loga = 0; ISDIGIT (tmpa); ++loga)
+	do
+	  tmpa = *++a;
+	while (IS_THOUSANDS_SEP (tmpa));
+
+      for (logb = 0; ISDIGIT (tmpb); ++logb)
+	do
+	  tmpb = *++b;
+	while (IS_THOUSANDS_SEP (tmpb));
+
+      if (loga != logb)
+	return loga < logb ? 1 : -1;
+
+      if (!loga)
+	return 0;
+
+      return tmp;
+    }
+  else if (tmpb == NEGATION_SIGN)
+    {
+      do
+	tmpb = *++b;
+      while (tmpb == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpb));
+      if (tmpb == decimal_point)
+	do
+	  tmpb = *++b;
+	while (tmpb == NUMERIC_ZERO);
+      if (ISDIGIT (tmpb))
+	return 1;
+      while (tmpa == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpa))
+	tmpa = *++a;
+      if (tmpa == decimal_point)
+	do
+	  tmpa = *++a;
+	while (tmpa == NUMERIC_ZERO);
+      if (ISDIGIT (tmpa))
+	return 1;
+      return 0;
+    }
+  else
+    {
+      while (tmpa == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpa))
+	tmpa = *++a;
+      while (tmpb == NUMERIC_ZERO || IS_THOUSANDS_SEP (tmpb))
+	tmpb = *++b;
+
+      while (tmpa == tmpb && ISDIGIT (tmpa))
+	{
+	  do
+	    tmpa = *++a;
+	  while (IS_THOUSANDS_SEP (tmpa));
+	  do
+	    tmpb = *++b;
+	  while (IS_THOUSANDS_SEP (tmpb));
+	}
+
+      if ((tmpa == decimal_point && !ISDIGIT (tmpb))
+	  || (tmpb == decimal_point && !ISDIGIT (tmpa)))
+	return fraccompare (a, b);
+
+      tmp = tmpa - tmpb;
+
+      for (loga = 0; ISDIGIT (tmpa); ++loga)
+	do
+	  tmpa = *++a;
+	while (IS_THOUSANDS_SEP (tmpa));
+
+      for (logb = 0; ISDIGIT (tmpb); ++logb)
+	do
+	  tmpb = *++b;
+	while (IS_THOUSANDS_SEP (tmpb));
+
+      if (loga != logb)
+	return loga < logb ? -1 : 1;
+
+      if (!loga)
+	return 0;
+
+      return tmp;
+    }
+}
+
+static int
+general_numcompare (const char *sa, const char *sb)
+{
+  /* FIXME: add option to warn about failed conversions.  */
+  /* FIXME: maybe add option to try expensive FP conversion
+     only if A and B can't be compared more cheaply/accurately.  */
+
+  char *ea;
+  char *eb;
+  double a = strtod (sa, &ea);
+  double b = strtod (sb, &eb);
+
+  /* Put conversion errors at the start of the collating sequence.  */
+  if (sa == ea)
+    return sb == eb ? 0 : -1;
+  if (sb == eb)
+    return 1;
+
+  /* Sort numbers in the usual way, where -0 == +0.  Put NaNs after
+     conversion errors but before numbers; sort them by internal
+     bit-pattern, for lack of a more portable alternative.  */
+  return (a < b ? -1
+	  : a > b ? 1
+	  : a == b ? 0
+	  : b == b ? -1
+	  : a == a ? 1
+	  : memcmp ((char *) &a, (char *) &b, sizeof a));
+}
+
+/* Return an integer in 1..12 of the month name S with length LEN.
+   Return 0 if the name in S is not recognized.  */
+
+static int
+getmonth (const char *s, size_t len)
+{
+  char *month;
+  register size_t i;
+  register int lo = 0, hi = MONTHS_PER_YEAR, result;
+
+  while (len > 0 && blanks[UCHAR (*s)])
+    {
+      ++s;
+      --len;
+    }
+
+  if (len == 0)
+    return 0;
+
+  month = (char *) alloca (len + 1);
+  for (i = 0; i < len; ++i)
+    month[i] = fold_toupper[UCHAR (s[i])];
+  while (blanks[UCHAR (month[i - 1])])
+    --i;
+  month[i] = '\0';
+
+  do
+    {
+      int ix = (lo + hi) / 2;
+
+      if (strncmp (month, monthtab[ix].name, strlen (monthtab[ix].name)) < 0)
+	hi = ix;
+      else
+	lo = ix;
+    }
+  while (hi - lo > 1);
+
+  result = (!strncmp (month, monthtab[lo].name, strlen (monthtab[lo].name))
+	    ? monthtab[lo].val : 0);
+
+  return result;
+}
+
+/* Compare two lines A and B trying every key in sequence until there
+   are no more keys or a difference is found. */
+
+static int
+keycompare (const struct line *a, const struct line *b)
+{
+  struct keyfield *key = keylist;
+
+  /* For the first iteration only, the key positions have been
+     precomputed for us. */
+  register char *texta = a->keybeg;
+  register char *textb = b->keybeg;
+  register char *lima = a->keylim;
+  register char *limb = b->keylim;
+
+  int diff;
+
+  for (;;)
+    {
+      register unsigned char *translate = (unsigned char *) key->translate;
+      register int *ignore = key->ignore;
+
+      /* Find the lengths. */
+      size_t lena = lima <= texta ? 0 : lima - texta;
+      size_t lenb = limb <= textb ? 0 : limb - textb;
+
+      if (key->skipeblanks)
+	{
+	  char *a_end = texta + lena;
+	  char *b_end = textb + lenb;
+	  trim_trailing_blanks (texta, &a_end);
+	  trim_trailing_blanks (textb, &b_end);
+	  lena = a_end - texta;
+	  lenb = b_end - textb;
+	}
+
+      /* Actually compare the fields. */
+      if (key->numeric | key->general_numeric)
+	{
+	  char savea = *lima, saveb = *limb;
+
+	  *lima = *limb = '\0';
+	  diff = ((key->numeric ? numcompare : general_numcompare)
+		  (texta, textb));
+	  *lima = savea, *limb = saveb;
+	}
+      else if (key->month)
+	diff = getmonth (texta, lena) - getmonth (textb, lenb);
+#ifdef ENABLE_NLS
+      /* Sorting like this may become slow, so in a simple locale the user
+         can select a faster sort that is similar to ascii sort  */
+      else if (hard_LC_COLLATE)
+	{
+	  if (ignore || translate)
+	    {
+	      char *copy_a = (char *) alloca (lena + 1 + lenb + 1);
+	      char *copy_b = copy_a + lena + 1;
+	      size_t new_len_a, new_len_b, i;
+
+	      /* Ignore and/or translate chars before comparing.  */
+	      for (new_len_a = new_len_b = i = 0; i < max (lena, lenb); i++)
+		{
+		  if (i < lena)
+		    {
+		      copy_a[new_len_a] = (translate
+					   ? translate[UCHAR (texta[i])]
+					   : texta[i]);
+		      if (!ignore || !ignore[UCHAR (texta[i])])
+			++new_len_a;
+		    }
+		  if (i < lenb)
+		    {
+		      copy_b[new_len_b] = (translate
+					   ? translate[UCHAR (textb[i])]
+					   : textb [i]);
+		      if (!ignore || !ignore[UCHAR (textb[i])])
+			++new_len_b;
+		    }
+		}
+
+	      diff = xmemcoll (copy_a, new_len_a, copy_b, new_len_b);
+	    }
+	  else if (lena == 0)
+	    diff = - NONZERO (lenb);
+	  else if (lenb == 0)
+	    goto greater;
+	  else
+	    diff = xmemcoll (texta, lena, textb, lenb);
+	}
+#endif
+      else if (ignore)
+	{
+#define CMP_WITH_IGNORE(A, B)						\
+  do									\
+    {									\
+	  for (;;)							\
+	    {								\
+	      while (texta < lima && ignore[UCHAR (*texta)])		\
+		++texta;						\
+	      while (textb < limb && ignore[UCHAR (*textb)])		\
+		++textb;						\
+	      if (! (texta < lima && textb < limb))			\
+		break;							\
+	      diff = UCHAR (A) - UCHAR (B);				\
+	      if (diff)							\
+		goto not_equal;						\
+	      ++texta;							\
+	      ++textb;							\
+	    }								\
+									\
+	  diff = (texta < lima) - (textb < limb);			\
+    }									\
+  while (0)
+
+	  if (translate)
+	    CMP_WITH_IGNORE (translate[UCHAR (*texta)],
+			     translate[UCHAR (*textb)]);
+	  else
+	    CMP_WITH_IGNORE (UCHAR (*texta), UCHAR (*textb));
+	}
+      else if (lena == 0)
+	diff = - NONZERO (lenb);
+      else if (lenb == 0)
+	goto greater;
+      else
+	{
+	  if (translate)
+	    {
+	      while (texta < lima && textb < limb)
+		{
+		  diff = (UCHAR (translate[UCHAR (*texta++)])
+			  - UCHAR (translate[UCHAR (*textb++)]));
+		  if (diff)
+		    goto not_equal;
+		}
+	    }
+	  else
+	    {
+	      diff = memcmp (texta, textb, min (lena, lenb));
+	      if (diff)
+		goto not_equal;
+	    }
+	  diff = lena < lenb ? -1 : lena != lenb;
+	}
+
+      if (diff)
+	goto not_equal;
+
+      key = key->next;
+      if (! key)
+	break;
+
+      /* Find the beginning and limit of the next field.  */
+      if (key->eword != -1)
+	lima = limfield (a, key), limb = limfield (b, key);
+      else
+	lima = a->text + a->length - 1, limb = b->text + b->length - 1;
+
+      if (key->sword != -1)
+	texta = begfield (a, key), textb = begfield (b, key);
+      else
+	{
+	  texta = a->text, textb = b->text;
+	  if (key->skipsblanks)
+	    {
+	      while (texta < lima && blanks[UCHAR (*texta)])
+		++texta;
+	      while (textb < limb && blanks[UCHAR (*textb)])
+		++textb;
+	    }
+	}
+    }
+
+  return 0;
+
+ greater:
+  diff = 1;
+ not_equal:
+  return key->reverse ? -diff : diff;
+}
+
+/* Compare two lines A and B, returning negative, zero, or positive
+   depending on whether A compares less than, equal to, or greater than B. */
+
+static int
+compare (register const struct line *a, register const struct line *b)
+{
+  int diff;
+  size_t alen, blen;
+
+  /* First try to compare on the specified keys (if any).
+     The only two cases with no key at all are unadorned sort,
+     and unadorned sort -r. */
+  if (keylist)
+    {
+      diff = keycompare (a, b);
+      alloca (0);
+      if (diff != 0 || unique || stable)
+	return diff;
+    }
+
+  /* If the keys all compare equal (or no keys were specified)
+     fall through to the default comparison.  */
+  alen = a->length - 1, blen = b->length - 1;
+
+  if (alen == 0)
+    diff = - NONZERO (blen);
+  else if (blen == 0)
+    diff = NONZERO (alen);
+#ifdef ENABLE_NLS
+  else if (hard_LC_COLLATE)
+    diff = xmemcoll (a->text, alen, b->text, blen);
+#endif
+  else if (! (diff = memcmp (a->text, b->text, min (alen, blen))))
+    diff = alen < blen ? -1 : alen != blen;
+
+  return reverse ? -diff : diff;
+}
+
+/* Check that the lines read from the given FP come in order.  Print a
+   diagnostic (FILE_NAME, line number, contents of line) to stderr and return
+   one if they are not in order.  Otherwise, print no diagnostic
+   and return zero.  */
+
+static int
+checkfp (FILE *fp, char *file_name)
+{
+  struct buffer buf;		/* Input buffer. */
+  struct line temp;		/* Copy of previous line. */
+  size_t alloc = 0;
+  uintmax_t line_number = 0;
+  struct keyfield *key = keylist;
+  int nonunique = 1 - unique;
+  int disordered = 0;
+
+  initbuf (&buf, sizeof (struct line),
+	   MAX (merge_buffer_size, sort_size));
+  temp.text = NULL;
+
+  while (fillbuf (&buf, fp, file_name))
+    {
+      struct line const *line = buffer_linelim (&buf);
+      struct line const *linebase = line - buf.nlines;
+
+      /* Make sure the line saved from the old buffer contents is
+	 less than or equal to the first line of the new buffer. */
+      if (alloc && nonunique <= compare (&temp, line - 1))
+	{
+	found_disorder:
+	  {
+	    char hr_buf[LONGEST_HUMAN_READABLE + 1];
+	    struct line const *disorder_line = line - 1;
+	    uintmax_t disorder_line_number =
+	      buffer_linelim (&buf) - disorder_line + line_number;
+	    fprintf (stderr, _("%s: %s:%s: disorder: "),
+		     program_name, file_name,
+		     human_readable (disorder_line_number, hr_buf, 1, 1));
+	    write_bytes (disorder_line->text, disorder_line->length, stderr,
+			 _("standard error"));
+	    disordered = 1;
+	    break;
+	  }
+	}
+
+      /* Compare each line in the buffer with its successor.  */
+      while (linebase < --line)
+	if (nonunique <= compare (line, line - 1))
+	  goto found_disorder;
+
+      line_number += buf.nlines;
+
+      /* Save the last line of the buffer.  */
+      if (alloc < line->length)
+	{
+	  do
+	    {
+	      alloc *= 2;
+	      if (! alloc)
+		{
+		  alloc = line->length;
+		  break;
+		}
+	    }
+	  while (alloc < line->length);
+
+	  temp.text = xrealloc (temp.text, alloc);
+	}
+      memcpy (temp.text, line->text, line->length);
+      temp.length = line->length;
+      if (key)
+	{
+	  temp.keybeg = temp.text + (line->keybeg - line->text);
+	  temp.keylim = temp.text + (line->keylim - line->text);
+	}
+    }
+
+  xfclose (fp, file_name);
+  free (buf.buf);
+  if (temp.text)
+    free (temp.text);
+  return disordered;
+}
+
+/* Merge lines from FILES onto OFP.  NFILES cannot be greater than
+   NMERGE.  Close input and output files before returning.
+   OUTPUT_FILE gives the name of the output file; if OFP is NULL, the
+   output file has not been opened yet.  */
+
+static void
+mergefps (char **files, register int nfiles,
+	  FILE *ofp, const char *output_file)
+{
+  FILE *fps[NMERGE];		/* Input streams for each file.  */
+  struct buffer buffer[NMERGE];	/* Input buffers for each file. */
+  struct line saved;		/* Saved line storage for unique check. */
+  struct line const *savedline = NULL;
+				/* &saved if there is a saved line. */
+  size_t savealloc = 0;		/* Size allocated for the saved line. */
+  struct line const *cur[NMERGE]; /* Current line in each line table. */
+  struct line const *base[NMERGE]; /* Base of each line table.  */
+  int ord[NMERGE];		/* Table representing a permutation of fps,
+				   such that cur[ord[0]] is the smallest line
+				   and will be next output. */
+  register int i, j, t;
+  struct keyfield *key = keylist;
+  saved.text = NULL;
+
+  /* Read initial lines from each input file. */
+  for (i = 0; i < nfiles; )
+    {
+      fps[i] = xfopen (files[i], "r");
+      initbuf (&buffer[i], sizeof (struct line),
+	       MAX (merge_buffer_size, sort_size / nfiles));
+      if (fillbuf (&buffer[i], fps[i], files[i]))
+	{
+	  struct line const *linelim = buffer_linelim (&buffer[i]);
+	  cur[i] = linelim - 1;
+	  base[i] = linelim - buffer[i].nlines;
+	  i++;
+	}
+      else
+	{
+	  /* fps[i] is empty; eliminate it from future consideration.  */
+	  xfclose (fps[i], files[i]);
+	  zaptemp (files[i]);
+	  free (buffer[i].buf);
+	  --nfiles;
+	  for (j = i; j < nfiles; ++j)
+	    files[j] = files[j + 1];
+	}
+    }
+
+  if (! ofp)
+    ofp = xfopen (output_file, "w");
+
+  /* Set up the ord table according to comparisons among input lines.
+     Since this only reorders two items if one is strictly greater than
+     the other, it is stable. */
+  for (i = 0; i < nfiles; ++i)
+    ord[i] = i;
+  for (i = 1; i < nfiles; ++i)
+    if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))
+      t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
+
+  /* Repeatedly output the smallest line until no input remains. */
+  while (nfiles)
+    {
+      struct line const *smallest = cur[ord[0]];
+
+      /* If uniquified output is turned on, output only the first of
+	 an identical series of lines. */
+      if (unique)
+	{
+	  if (savedline && compare (savedline, smallest))
+	    {
+	      savedline = 0;
+	      write_bytes (saved.text, saved.length, ofp, output_file);
+	    }
+	  if (!savedline)
+	    {
+	      savedline = &saved;
+	      if (savealloc < smallest->length)
+		{
+		  do
+		    if (! savealloc)
+		      {
+			savealloc = smallest->length;
+			break;
+		      }
+		  while ((savealloc *= 2) < smallest->length);
+
+		  saved.text = xrealloc (saved.text, savealloc);
+		}
+	      saved.length = smallest->length;
+	      memcpy (saved.text, smallest->text, saved.length);
+	      if (key)
+		{
+		  saved.keybeg =
+		    saved.text + (smallest->keybeg - smallest->text);
+		  saved.keylim =
+		    saved.text + (smallest->keylim - smallest->text);
+		}
+	    }
+	}
+      else
+	write_bytes (smallest->text, smallest->length, ofp, output_file);
+
+      /* Check if we need to read more lines into core. */
+      if (base[ord[0]] < smallest)
+	cur[ord[0]] = smallest - 1;
+      else
+	{
+	  if (fillbuf (&buffer[ord[0]], fps[ord[0]], files[ord[0]]))
+	    {
+	      struct line const *linelim = buffer_linelim (&buffer[ord[0]]);
+	      cur[ord[0]] = linelim - 1;
+	      base[ord[0]] = linelim - buffer[ord[0]].nlines;
+	    }
+	  else
+	    {
+	      /* We reached EOF on fps[ord[0]]. */
+	      for (i = 1; i < nfiles; ++i)
+		if (ord[i] > ord[0])
+		  --ord[i];
+	      --nfiles;
+	      xfclose (fps[ord[0]], files[ord[0]]);
+	      zaptemp (files[ord[0]]);
+	      free (buffer[ord[0]].buf);
+	      for (i = ord[0]; i < nfiles; ++i)
+		{
+		  fps[i] = fps[i + 1];
+		  files[i] = files[i + 1];
+		  buffer[i] = buffer[i + 1];
+		  cur[i] = cur[i + 1];
+		  base[i] = base[i + 1];
+		}
+	      for (i = 0; i < nfiles; ++i)
+		ord[i] = ord[i + 1];
+	      continue;
+	    }
+	}
+
+      /* The new line just read in may be larger than other lines
+	 already in core; push it back in the queue until we encounter
+	 a line larger than it. */
+      for (i = 1; i < nfiles; ++i)
+	{
+	  t = compare (cur[ord[0]], cur[ord[i]]);
+	  if (!t)
+	    t = ord[0] - ord[i];
+	  if (t < 0)
+	    break;
+	}
+      t = ord[0];
+      for (j = 1; j < i; ++j)
+	ord[j - 1] = ord[j];
+      ord[i - 1] = t;
+    }
+
+  if (unique && savedline)
+    {
+      write_bytes (saved.text, saved.length, ofp, output_file);
+      free (saved.text);
+    }
+
+  xfclose (ofp, output_file);
+}
+
+/* Sort the array LINES with NLINES members, using TEMP for temporary space.
+   The input and output arrays are in reverse order, and LINES and
+   TEMP point just past the end of their respective arrays.  */
+
+static void
+sortlines (struct line *lines, size_t nlines, struct line *temp)
+{
+  register struct line *lo, *hi, *t;
+  register size_t nlo, nhi;
+
+  if (nlines == 2)
+    {
+      if (0 < compare (&lines[-1], &lines[-2]))
+	{
+	  struct line tmp = lines[-1];
+	  lines[-1] = lines[-2];
+	  lines[-2] = tmp;
+	}
+      return;
+    }
+
+  nlo = nlines / 2;
+  lo = lines;
+  nhi = nlines - nlo;
+  hi = lines - nlo;
+
+  if (nlo > 1)
+    sortlines (lo, nlo, temp);
+
+  if (nhi > 1)
+    sortlines (hi, nhi, temp);
+
+  t = temp;
+
+  while (nlo && nhi)
+    if (compare (lo - 1, hi - 1) <= 0)
+      *--t = *--lo, --nlo;
+    else
+      *--t = *--hi, --nhi;
+  while (nlo--)
+    *--t = *--lo;
+
+  for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)
+    *--lo = *--t;
+}
+
+/* Return the index of the first of NFILES FILES that is the same file
+   as OUTFILE.  If none can be the same, return NFILES.  Consider an
+   input pipe to be the same as OUTFILE, since the pipe might be the
+   output of a command like "cat OUTFILE".  */
+
+static int
+first_same_file (char **files, int nfiles, char const *outfile)
+{
+  int i;
+  int got_outstat = 0;
+  struct stat instat, outstat;
+
+  for (i = 0; i < nfiles; i++)
+    {
+      int standard_input = STREQ (files[i], "-");
+
+      if (STREQ (outfile, files[i]) && ! standard_input)
+	return i;
+
+      if (! got_outstat)
+	{
+	  got_outstat = 1;
+	  if ((STREQ (outfile, "-")
+	       ? fstat (STDOUT_FILENO, &outstat)
+	       : stat (outfile, &outstat))
+	      != 0)
+	    return nfiles;
+	}
+
+      if (((standard_input
+	    ? fstat (STDIN_FILENO, &instat)
+	    : stat (files[i], &instat))
+	   == 0)
+	  && (S_ISFIFO (instat.st_mode) || SAME_INODE (instat, outstat)))
+	return i;
+    }
+
+  return nfiles;
+}
+
+/* Check that each of the NFILES FILES is ordered.
+   Return a count of disordered files. */
+
+static int
+check (char **files, int nfiles)
+{
+  int i, disorders = 0;
+  FILE *fp;
+
+  for (i = 0; i < nfiles; ++i)
+    {
+      fp = xfopen (files[i], "r");
+      disorders += checkfp (fp, files[i]);
+    }
+  return disorders;
+}
+
+/* Merge NFILES FILES onto OUTPUT_FILE.  However, merge at most
+   MAX_MERGE input files directly onto OUTPUT_FILE.  MAX_MERGE cannot
+   exceed NMERGE.  */
+
+static void
+merge (char **files, int nfiles, int max_merge, char const *output_file)
+{
+  while (max_merge < nfiles)
+    {
+      FILE *tfp;
+      int i, t = 0;
+      char *temp;
+      for (i = 0; i < nfiles / NMERGE; ++i)
+	{
+	  temp = create_temp_file (&tfp);
+	  mergefps (&files[i * NMERGE], NMERGE, tfp, temp);
+	  files[t++] = temp;
+	}
+      temp = create_temp_file (&tfp);
+      mergefps (&files[i * NMERGE], nfiles % NMERGE, tfp, temp);
+      files[t++] = temp;
+      nfiles = t;
+      if (nfiles == 1)
+	break;
+    }
+
+  mergefps (files, nfiles, NULL, output_file);
+}
+
+/* Sort NFILES FILES onto OUTPUT_FILE. */
+
+static void
+sort (char **files, int nfiles, char const *output_file)
+{
+  struct buffer buf;
+  int n_temp_files = 0;
+  int output_file_created = 0;
+
+  static size_t size;
+  if (! size && ! (size = sort_size))
+    size = default_sort_size ();
+
+  buf.alloc = 0;
+
+  while (nfiles)
+    {
+      char const *temp_output;
+      char const *file = *files;
+      FILE *fp = xfopen (file, "r");
+      FILE *tfp;
+
+      if (! buf.alloc)
+	initbuf (&buf, 2 * sizeof (struct line),
+		 sort_buffer_size (&fp, 1, files, nfiles,
+				   2 * sizeof (struct line), size));
+      buf.eof = 0;
+      files++;
+      nfiles--;
+
+      while (fillbuf (&buf, fp, file))
+	{
+	  struct line *line;
+	  struct line *linebase;
+
+	  if (buf.eof && nfiles
+	      && (2 * sizeof (struct line) + 1
+		  < (buf.alloc - buf.used
+		     - 2 * sizeof (struct line) * buf.nlines)))
+	    {
+	      /* End of file, but there is more input and buffer room.
+		 Concatenate the next input file; this is faster in
+		 the usual case.  */
+	      buf.left = buf.used;
+	      break;
+	    }
+
+	  line = buffer_linelim (&buf);
+	  linebase = line - buf.nlines;
+	  sortlines (line, buf.nlines, linebase);
+	  if (buf.eof && !nfiles && !n_temp_files && !buf.left)
+	    {
+	      xfclose (fp, file);
+	      tfp = xfopen (output_file, "w");
+	      temp_output = output_file;
+	      output_file_created = 1;
+	    }
+	  else
+	    {
+	      ++n_temp_files;
+	      temp_output = create_temp_file (&tfp);
+	    }
+
+	  do
+	    {
+	      line--;
+	      write_bytes (line->text, line->length, tfp, temp_output);
+	      if (unique)
+		while (linebase < line && compare (line, line - 1) == 0)
+		  line--;
+	    }
+	  while (linebase < line);
+
+	  xfclose (tfp, temp_output);
+
+	  if (output_file_created)
+	    goto finish;
+	}
+      xfclose (fp, file);
+    }
+
+ finish:
+  free (buf.buf);
+
+  if (! output_file_created)
+    {
+      int i = n_temp_files;
+      struct tempnode *node;
+      char **tempfiles = (char **) xmalloc (n_temp_files * sizeof (char *));
+      for (node = temphead; i > 0; node = node->next)
+	tempfiles[--i] = node->name;
+      merge (tempfiles, n_temp_files, NMERGE, output_file);
+      free ((char *) tempfiles);
+    }
+}
+
+/* Insert key KEY at the end of the key list.  */
+
+static void
+insertkey (struct keyfield *key)
+{
+  struct keyfield **p;
+
+  for (p = &keylist; *p; p = &(*p)->next)
+    continue;
+  *p = key;
+  key->next = NULL;
+}
+
+/* Report a bad field specification SPEC, with extra info MSGID.  */
+
+static void badfieldspec PARAMS ((char const *, char const *))
+     ATTRIBUTE_NORETURN;
+static void
+badfieldspec (char const *spec, char const *msgid)
+{
+  error (SORT_FAILURE, 0, _("%s: invalid field specification `%s'"),
+	 _(msgid), spec);
+  abort ();
+}
+
+/* Parse the leading integer in STRING and store the resulting value
+   (which must fit into size_t) into *VAL.  Return the address of the
+   suffix after the integer.  If MSGID is NULL, return NULL after
+   failure; otherwise, report MSGID and exit on failure.  */
+
+static char const *
+parse_field_count (char const *string, size_t *val, char const *msgid)
+{
+  char *suffix;
+  uintmax_t n;
+
+  switch (xstrtoumax (string, &suffix, 10, &n, ""))
+    {
+    case LONGINT_OK:
+    case LONGINT_INVALID_SUFFIX_CHAR:
+      *val = n;
+      if (*val == n)
+	break;
+      /* Fall through.  */
+    case LONGINT_OVERFLOW:
+      if (msgid)
+	error (SORT_FAILURE, 0, _("%s: count `%.*s' too large"),
+	       _(msgid), (int) (suffix - string), string);
+      return NULL;
+
+    case LONGINT_INVALID:
+      if (msgid)
+	error (SORT_FAILURE, 0, _("%s: invalid count at start of `%s'"),
+	       _(msgid), string);
+      return NULL;
+    }
+
+  return suffix;
+}
+
+/* Handle interrupts and hangups. */
+
+static void
+sighandler (int sig)
+{
+#ifndef SA_NOCLDSTOP
+  signal (sig, SIG_IGN);
+#endif
+
+  cleanup ();
+
+#ifdef SA_NOCLDSTOP
+  {
+    struct sigaction sigact;
+
+    sigact.sa_handler = SIG_DFL;
+    sigemptyset (&sigact.sa_mask);
+    sigact.sa_flags = 0;
+    sigaction (sig, &sigact, NULL);
+  }
+#else
+  signal (sig, SIG_DFL);
+#endif
+
+  kill (process_id, sig);
+}
+
+/* Set the ordering options for KEY specified in S.
+   Return the address of the first character in S that
+   is not a valid ordering option.
+   BLANKTYPE is the kind of blanks that 'b' should skip. */
+
+static char *
+set_ordering (register const char *s, struct keyfield *key,
+	      enum blanktype blanktype)
+{
+  while (*s)
+    {
+      switch (*s)
+	{
+	case 'b':
+	  if (blanktype == bl_start || blanktype == bl_both)
+	    key->skipsblanks = 1;
+	  if (blanktype == bl_end || blanktype == bl_both)
+	    key->skipeblanks = 1;
+	  break;
+	case 'd':
+	  key->ignore = nondictionary;
+	  break;
+	case 'f':
+	  key->translate = fold_toupper;
+	  break;
+	case 'g':
+	  key->general_numeric = 1;
+	  break;
+	case 'i':
+	  key->ignore = nonprinting;
+	  break;
+	case 'M':
+	  key->month = 1;
+	  break;
+	case 'n':
+	  key->numeric = 1;
+	  break;
+	case 'r':
+	  key->reverse = 1;
+	  break;
+	default:
+	  return (char *) s;
+	}
+      ++s;
+    }
+  return (char *) s;
+}
+
+static struct keyfield *
+new_key (void)
+{
+  struct keyfield *key = (struct keyfield *) xcalloc (1, sizeof *key);
+  key->eword = -1;
+  return key;
+}
+
+int
+main (int argc, char **argv)
+{
+  struct keyfield *key;
+  struct keyfield gkey;
+  char const *s;
+  int i;
+  int c = 0;
+  int checkonly = 0, mergeonly = 0, nfiles = 0;
+  int posix_pedantic = (getenv ("POSIXLY_CORRECT") != NULL);
+  bool obsolete_usage = (posix2_version () < 200112);
+  char const *short_options = (obsolete_usage
+			       ? COMMON_SHORT_OPTIONS "y::"
+			       : COMMON_SHORT_OPTIONS "y:");
+  char *minus = "-", **files;
+  char const *outfile = minus;
+  static int const sigs[] = { SIGHUP, SIGINT, SIGPIPE, SIGTERM };
+  int nsigs = sizeof sigs / sizeof *sigs;
+#ifdef SA_NOCLDSTOP
+  struct sigaction oldact, newact;
+#endif
+
+  program_name = argv[0];
+  process_id = getpid ();
+  setlocale (LC_ALL, "");
+  bindtextdomain (PACKAGE, LOCALEDIR);
+  textdomain (PACKAGE);
+
+  atexit (cleanup);
+
+#ifdef ENABLE_NLS
+
+  hard_LC_COLLATE = hard_locale (LC_COLLATE);
+# if HAVE_NL_LANGINFO
+  hard_LC_TIME = hard_locale (LC_TIME);
+# endif
+
+  /* Let's get locale's representation of the decimal point */
+  {
+    struct lconv *lconvp = localeconv ();
+
+    /* If the locale doesn't define a decimal point, or if the decimal
+       point is multibyte, use the C decimal point.  We don't support
+       multibyte decimal points yet.  */
+    decimal_point = *lconvp->decimal_point;
+    if (! decimal_point || lconvp->decimal_point[1])
+      decimal_point = C_DECIMAL_POINT;
+
+    /* We don't support multibyte thousands separators yet.  */
+    th_sep = *lconvp->thousands_sep;
+    if (! th_sep || lconvp->thousands_sep[1])
+      th_sep = CHAR_MAX + 1;
+  }
+
+#endif /* NLS */
+
+  have_read_stdin = 0;
+  inittables ();
+
+  /* Change the way library functions fail.  */
+  xalloc_exit_failure = SORT_FAILURE;
+  xmemcoll_exit_failure = SORT_FAILURE;
+
+#ifdef SA_NOCLDSTOP
+  sigemptyset (&caught_signals);
+  for (i = 0; i < nsigs; i++)
+    sigaddset (&caught_signals, sigs[i]);
+  newact.sa_handler = sighandler;
+  newact.sa_mask = caught_signals;
+  newact.sa_flags = 0;
+#endif
+
+  for (i = 0; i < nsigs; i++)
+    {
+      int sig = sigs[i];
+#ifdef SA_NOCLDSTOP
+      sigaction (sig, NULL, &oldact);
+      if (oldact.sa_handler != SIG_IGN)
+	sigaction (sig, &newact, NULL);
+#else
+      if (signal (sig, SIG_IGN) != SIG_IGN)
+	signal (sig, sighandler);
+#endif
+    }
+
+  gkey.sword = gkey.eword = -1;
+  gkey.ignore = NULL;
+  gkey.translate = NULL;
+  gkey.numeric = gkey.general_numeric = gkey.month = gkey.reverse = 0;
+  gkey.skipsblanks = gkey.skipeblanks = 0;
+
+  files = (char **) xmalloc (sizeof (char *) * argc);
+
+  for (;;)
+    {
+      /* Parse an operand as a file after "--" was seen; or if
+         pedantic and a file was seen, unless the POSIX version
+         predates 1003.1-2001 and -c was not seen and the operand is
+         "-o FILE" or "-oFILE".  */
+
+      if (c == -1
+	  || (posix_pedantic && nfiles != 0
+	      && ! (obsolete_usage
+		    && ! checkonly
+		    && optind != argc
+		    && argv[optind][0] == '-' && argv[optind][1] == 'o'
+		    && (argv[optind][2] || optind + 1 != argc)))
+	  || ((c = getopt_long (argc, argv, short_options,
+				long_options, NULL))
+	      == -1))
+	{
+	  if (optind == argc)
+	    break;
+	  files[nfiles++] = argv[optind++];
+	}
+      else switch (c)
+	{
+	case 1:
+	  key = NULL;
+	  if (obsolete_usage && optarg[0] == '+')
+	    {
+	      /* Treat +POS1 [-POS2] as a key if possible; but silently
+		 treat an operand as a file if it is not a valid +POS1.  */
+	      key = new_key ();
+	      s = parse_field_count (optarg + 1, &key->sword, NULL);
+	      if (s && *s == '.')
+		s = parse_field_count (s + 1, &key->schar, NULL);
+	      if (! (key->sword | key->schar))
+		key->sword = -1;
+	      if (! s || *set_ordering (s, key, bl_start))
+		{
+		  free (key);
+		  key = NULL;
+		}
+	      else
+		{
+		  if (optind != argc && argv[optind][0] == '-'
+		      && ISDIGIT (argv[optind][1]))
+		    {
+		      char const *optarg1 = argv[optind++];
+		      s = parse_field_count (optarg1 + 1, &key->eword,
+					     N_("invalid number after `-'"));
+		      if (*s == '.')
+			s = parse_field_count (s + 1, &key->echar,
+					       N_("invalid number after `.'"));
+		      if (*set_ordering (s, key, bl_end))
+			badfieldspec (optarg1,
+				      N_("stray character in field spec"));
+		    }
+		  insertkey (key);
+		}
+	    }
+	  if (! key)
+	    files[nfiles++] = optarg;
+	  break;
+
+	case 'b':
+	case 'd':
+	case 'f':
+	case 'g':
+	case 'i':
+	case 'M':
+	case 'n':
+	case 'r':
+	  {
+	    char str[2];
+	    str[0] = c;
+	    str[1] = '\0';
+	    set_ordering (str, &gkey, bl_both);
+	  }
+	  break;
+
+	case 'c':
+	  checkonly = 1;
+	  break;
+
+	case 'k':
+	  key = new_key ();
+
+	  /* Get POS1. */
+	  s = parse_field_count (optarg, &key->sword,
+				 N_("invalid number at field start"));
+	  if (! key->sword--)
+	    {
+	      /* Provoke with `sort -k0' */
+	      badfieldspec (optarg, N_("field number is zero"));
+	    }
+	  if (*s == '.')
+	    {
+	      s = parse_field_count (s + 1, &key->schar,
+				     N_("invalid number after `.'"));
+	      if (! key->schar--)
+		{
+		  /* Provoke with `sort -k1.0' */
+		  badfieldspec (optarg, N_("character offset is zero"));
+		}
+	    }
+	  if (! (key->sword | key->schar))
+	    key->sword = -1;
+	  s = set_ordering (s, key, bl_start);
+	  if (*s != ',')
+	    {
+	      key->eword = -1;
+	      key->echar = 0;
+	    }
+	  else
+	    {
+	      /* Get POS2. */
+	      s = parse_field_count (s + 1, &key->eword,
+				     N_("invalid number after `,'"));
+	      if (! key->eword--)
+		{
+		  /* Provoke with `sort -k1,0' */
+		  badfieldspec (optarg, N_("field number is zero"));
+		}
+	      if (*s == '.')
+		s = parse_field_count (s + 1, &key->echar,
+				       N_("invalid number after `.'"));
+	      else
+		{
+		  /* `-k 2,3' is equivalent to `+1 -3'.  */
+		  key->eword++;
+		}
+	      s = set_ordering (s, key, bl_end);
+	    }
+	  if (*s)
+	    badfieldspec (optarg, N_("stray character in field spec"));
+	  insertkey (key);
+	  break;
+
+	case 'm':
+	  mergeonly = 1;
+	  break;
+
+	case 'o':
+	  outfile = optarg;
+	  break;
+
+	case 's':
+	  stable = 1;
+	  break;
+
+	case 'S':
+	  specify_sort_size (optarg);
+	  break;
+
+	case 't':
+	  tab = optarg[0];
+	  if (tab && optarg[1])
+	    {
+	      /* Provoke with `sort -txx'.  Complain about
+		 "multi-character tab" instead of "multibyte tab", so
+		 that the diagnostic's wording does not need to be
+		 changed once multibyte characters are supported.  */
+	      error (SORT_FAILURE, 0, _("multi-character tab `%s'"), optarg);
+	    }
+	  break;
+
+	case 'T':
+	  add_temp_dir (optarg);
+	  break;
+
+	case 'u':
+	  unique = 1;
+	  break;
+
+	case 'y':
+	  /* Accept and ignore e.g. -y0 for compatibility with Solaris
+	     2.x through Solaris 7.  -y is marked as obsolete starting
+	     with Solaris 8.  */
+	  break;
+
+	case 'z':
+	  eolchar = 0;
+	  break;
+
+	case_GETOPT_HELP_CHAR;
+
+	case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
+
+	default:
+	  usage (SORT_FAILURE);
+	}
+    }
+
+  /* Inheritance of global options to individual keys. */
+  for (key = keylist; key; key = key->next)
+    if (!key->ignore && !key->translate && !key->skipsblanks && !key->reverse
+	&& !key->skipeblanks && !key->month && !key->numeric
+	&& !key->general_numeric)
+      {
+	key->ignore = gkey.ignore;
+	key->translate = gkey.translate;
+	key->skipsblanks = gkey.skipsblanks;
+	key->skipeblanks = gkey.skipeblanks;
+	key->month = gkey.month;
+	key->numeric = gkey.numeric;
+	key->general_numeric = gkey.general_numeric;
+	key->reverse = gkey.reverse;
+      }
+
+  if (!keylist && (gkey.ignore || gkey.translate || gkey.skipsblanks
+		   || gkey.skipeblanks || gkey.month || gkey.numeric
+		   || gkey.general_numeric))
+    insertkey (&gkey);
+  reverse = gkey.reverse;
+
+  if (temp_dir_count == 0)
+    {
+      char const *tmp_dir = getenv ("TMPDIR");
+      add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
+    }
+
+  if (nfiles == 0)
+    {
+      nfiles = 1;
+      files = &minus;
+    }
+
+  if (checkonly)
+    {
+      if (nfiles > 1)
+	error (SORT_FAILURE, 0, _("extra operand `%s' not allowed with -c"),
+	       files[1]);
+
+      /* POSIX requires that sort return 1 IFF invoked with -c and the
+	 input is not properly sorted.  */
+      exit (check (files, nfiles) == 0 ? EXIT_SUCCESS : SORT_OUT_OF_ORDER);
+    }
+
+  if (mergeonly)
+    {
+      int max_merge = first_same_file (files, MIN (nfiles, NMERGE), outfile);
+      merge (files, nfiles, max_merge, outfile);
+    }
+  else
+    sort (files, nfiles, outfile);
+
+  if (have_read_stdin && fclose (stdin) == EOF)
+    die (_("close failed"), "-");
+
+  exit (EXIT_SUCCESS);
+}
diff --git a/contrib/gnu-sort/src/sys2.h b/contrib/gnu-sort/src/sys2.h
new file mode 100644
index 0000000..610c1fd
--- /dev/null
+++ b/contrib/gnu-sort/src/sys2.h
@@ -0,0 +1,565 @@
+/* WARNING -- this file is temporary.  It is shared between the
+   sh-utils, fileutils, and textutils packages.  Once I find a little
+   more time, I'll merge the remaining things in system.h and everything
+   in this file will go back there. */
+
+#if STAT_MACROS_BROKEN
+# undef S_ISBLK
+# undef S_ISCHR
+# undef S_ISDIR
+# undef S_ISDOOR
+# undef S_ISFIFO
+# undef S_ISLNK
+# undef S_ISMPB
+# undef S_ISMPC
+# undef S_ISNWK
+# undef S_ISREG
+# undef S_ISSOCK
+#endif /* STAT_MACROS_BROKEN.  */
+
+#ifndef S_IFMT
+# define S_IFMT 0170000
+#endif
+#if !defined(S_ISBLK) && defined(S_IFBLK)
+# define S_ISBLK(m) (((m) & S_IFMT) == S_IFBLK)
+#endif
+#if !defined(S_ISCHR) && defined(S_IFCHR)
+# define S_ISCHR(m) (((m) & S_IFMT) == S_IFCHR)
+#endif
+#if !defined(S_ISDIR) && defined(S_IFDIR)
+# define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR)
+#endif
+#if !defined(S_ISREG) && defined(S_IFREG)
+# define S_ISREG(m) (((m) & S_IFMT) == S_IFREG)
+#endif
+#if !defined(S_ISFIFO) && defined(S_IFIFO)
+# define S_ISFIFO(m) (((m) & S_IFMT) == S_IFIFO)
+#endif
+#if !defined(S_ISLNK) && defined(S_IFLNK)
+# define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
+#endif
+#if !defined(S_ISSOCK) && defined(S_IFSOCK)
+# define S_ISSOCK(m) (((m) & S_IFMT) == S_IFSOCK)
+#endif
+#if !defined(S_ISMPB) && defined(S_IFMPB) /* V7 */
+# define S_ISMPB(m) (((m) & S_IFMT) == S_IFMPB)
+# define S_ISMPC(m) (((m) & S_IFMT) == S_IFMPC)
+#endif
+#if !defined(S_ISNWK) && defined(S_IFNWK) /* HP/UX */
+# define S_ISNWK(m) (((m) & S_IFMT) == S_IFNWK)
+#endif
+#if !defined(S_ISDOOR) && defined(S_IFDOOR) /* Solaris 2.5 and up */
+# define S_ISDOOR(m) (((m) & S_IFMT) == S_IFDOOR)
+#endif
+
+#if !S_ISUID
+# define S_ISUID 04000
+#endif
+#if !S_ISGID
+# define S_ISGID 02000
+#endif
+
+/* S_ISVTX is a common extension to POSIX.  */
+#ifndef S_ISVTX
+# define S_ISVTX 01000
+#endif
+
+#if !S_IRUSR && S_IREAD
+# define S_IRUSR S_IREAD
+#endif
+#if !S_IRUSR
+# define S_IRUSR 00400
+#endif
+#if !S_IRGRP
+# define S_IRGRP (S_IRUSR >> 3)
+#endif
+#if !S_IROTH
+# define S_IROTH (S_IRUSR >> 6)
+#endif
+
+#if !S_IWUSR && S_IWRITE
+# define S_IWUSR S_IWRITE
+#endif
+#if !S_IWUSR
+# define S_IWUSR 00200
+#endif
+#if !S_IWGRP
+# define S_IWGRP (S_IWUSR >> 3)
+#endif
+#if !S_IWOTH
+# define S_IWOTH (S_IWUSR >> 6)
+#endif
+
+#if !S_IXUSR && S_IEXEC
+# define S_IXUSR S_IEXEC
+#endif
+#if !S_IXUSR
+# define S_IXUSR 00100
+#endif
+#if !S_IXGRP
+# define S_IXGRP (S_IXUSR >> 3)
+#endif
+#if !S_IXOTH
+# define S_IXOTH (S_IXUSR >> 6)
+#endif
+
+#if !S_IRWXU
+# define S_IRWXU (S_IRUSR | S_IWUSR | S_IXUSR)
+#endif
+#if !S_IRWXG
+# define S_IRWXG (S_IRGRP | S_IWGRP | S_IXGRP)
+#endif
+#if !S_IRWXO
+# define S_IRWXO (S_IROTH | S_IWOTH | S_IXOTH)
+#endif
+
+/* S_IXUGO is a common extension to POSIX.  */
+#if !S_IXUGO
+# define S_IXUGO (S_IXUSR | S_IXGRP | S_IXOTH)
+#endif
+
+#ifndef S_IRWXUGO
+# define S_IRWXUGO (S_IRWXU | S_IRWXG | S_IRWXO)
+#endif
+
+/* All the mode bits that can be affected by chmod.  */
+#define CHMOD_MODE_BITS \
+  (S_ISUID | S_ISGID | S_ISVTX | S_IRWXU | S_IRWXG | S_IRWXO)
+
+#ifdef ST_MTIM_NSEC
+# define ST_TIME_CMP_NS(a, b, ns) ((a).ns < (b).ns ? -1 : (a).ns > (b).ns)
+#else
+# define ST_TIME_CMP_NS(a, b, ns) 0
+#endif
+#define ST_TIME_CMP(a, b, s, ns) \
+  ((a).s < (b).s ? -1 : (a).s > (b).s ? 1 : ST_TIME_CMP_NS(a, b, ns))
+#define ATIME_CMP(a, b) ST_TIME_CMP (a, b, st_atime, st_atim.ST_MTIM_NSEC)
+#define CTIME_CMP(a, b) ST_TIME_CMP (a, b, st_ctime, st_ctim.ST_MTIM_NSEC)
+#define MTIME_CMP(a, b) ST_TIME_CMP (a, b, st_mtime, st_mtim.ST_MTIM_NSEC)
+
+#ifndef RETSIGTYPE
+# define RETSIGTYPE void
+#endif
+
+#if __GNUC__
+# ifndef alloca
+#  define alloca __builtin_alloca
+# endif
+#else
+# if HAVE_ALLOCA_H
+#  include <alloca.h>
+# else
+#  ifdef _AIX
+ #  pragma alloca
+#  else
+#   ifdef _WIN32
+#    include <malloc.h>
+#    include <io.h>
+#   else
+#    ifndef alloca
+char *alloca ();
+#    endif
+#   endif
+#  endif
+# endif
+#endif
+
+#ifdef __DJGPP__
+  /* We need the declaration of setmode.  */
+# include <io.h>
+  /* We need the declaration of __djgpp_set_ctrl_c.  */
+# include <sys/exceptn.h>
+#endif
+
+#if HAVE_STDINT_H
+# include <stdint.h>
+#endif
+
+#if HAVE_INTTYPES_H
+# include <inttypes.h> /* for the definition of UINTMAX_MAX */
+#endif
+
+#include <ctype.h>
+
+/* Jim Meyering writes:
+
+   "... Some ctype macros are valid only for character codes that
+   isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
+   using /bin/cc or gcc but without giving an ansi option).  So, all
+   ctype uses should be through macros like ISPRINT...  If
+   STDC_HEADERS is defined, then autoconf has verified that the ctype
+   macros don't need to be guarded with references to isascii. ...
+   Defining isascii to 1 should let any compiler worth its salt
+   eliminate the && through constant folding."
+
+   Bruno Haible adds:
+
+   "... Furthermore, isupper(c) etc. have an undefined result if c is
+   outside the range -1 <= c <= 255. One is tempted to write isupper(c)
+   with c being of type `char', but this is wrong if c is an 8-bit
+   character >= 128 which gets sign-extended to a negative value.
+   The macro ISUPPER protects against this as well."  */
+
+#if STDC_HEADERS || (!defined (isascii) && !HAVE_ISASCII)
+# define IN_CTYPE_DOMAIN(c) 1
+#else
+# define IN_CTYPE_DOMAIN(c) isascii(c)
+#endif
+
+#ifdef isblank
+# define ISBLANK(c) (IN_CTYPE_DOMAIN (c) && isblank (c))
+#else
+# define ISBLANK(c) ((c) == ' ' || (c) == '\t')
+#endif
+#ifdef isgraph
+# define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isgraph (c))
+#else
+# define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isprint (c) && !isspace (c))
+#endif
+
+/* This is defined in <sys/euc.h> on at least Solaris2.6 systems.  */
+#undef ISPRINT
+
+#define ISPRINT(c) (IN_CTYPE_DOMAIN (c) && isprint (c))
+#define ISALNUM(c) (IN_CTYPE_DOMAIN (c) && isalnum (c))
+#define ISALPHA(c) (IN_CTYPE_DOMAIN (c) && isalpha (c))
+#define ISCNTRL(c) (IN_CTYPE_DOMAIN (c) && iscntrl (c))
+#define ISLOWER(c) (IN_CTYPE_DOMAIN (c) && islower (c))
+#define ISPUNCT(c) (IN_CTYPE_DOMAIN (c) && ispunct (c))
+#define ISSPACE(c) (IN_CTYPE_DOMAIN (c) && isspace (c))
+#define ISUPPER(c) (IN_CTYPE_DOMAIN (c) && isupper (c))
+#define ISXDIGIT(c) (IN_CTYPE_DOMAIN (c) && isxdigit (c))
+#define ISDIGIT_LOCALE(c) (IN_CTYPE_DOMAIN (c) && isdigit (c))
+
+#if STDC_HEADERS
+# define TOLOWER(Ch) tolower (Ch)
+# define TOUPPER(Ch) toupper (Ch)
+#else
+# define TOLOWER(Ch) (ISUPPER (Ch) ? tolower (Ch) : (Ch))
+# define TOUPPER(Ch) (ISLOWER (Ch) ? toupper (Ch) : (Ch))
+#endif
+
+/* ISDIGIT differs from ISDIGIT_LOCALE, as follows:
+   - Its arg may be any int or unsigned int; it need not be an unsigned char.
+   - It's guaranteed to evaluate its argument exactly once.
+   - It's typically faster.
+   POSIX says that only '0' through '9' are digits.  Prefer ISDIGIT to
+   ISDIGIT_LOCALE unless it's important to use the locale's definition
+   of `digit' even when the host does not conform to POSIX.  */
+#define ISDIGIT(c) ((unsigned) (c) - '0' <= 9)
+
+#ifndef PARAMS
+# if PROTOTYPES
+#  define PARAMS(Args) Args
+# else
+#  define PARAMS(Args) ()
+# endif
+#endif
+
+/* Take care of NLS matters.  */
+
+#if HAVE_LOCALE_H
+# include <locale.h>
+#endif
+#if !HAVE_SETLOCALE
+# define setlocale(Category, Locale) /* empty */
+#endif
+
+#if ENABLE_NLS
+# include <libintl.h>
+# if HAVE_GETTEXT && !HAVE_DCGETTEXT && !defined dcgettext
+#  define dcgettext(Domain, Text, Category) Text
+# endif
+# define _(Text) gettext (Text)
+#else
+# undef bindtextdomain
+# define bindtextdomain(Domain, Directory) /* empty */
+# undef textdomain
+# define textdomain(Domain) /* empty */
+# undef dcgettext
+# define dcgettext(Domainname, Text, Category) Text
+# define _(Text) Text
+#endif
+#define N_(Text) Text
+
+#define STREQ(a, b) (strcmp ((a), (b)) == 0)
+
+#if !HAVE_DECL_FREE
+void free ();
+#endif
+
+#if !HAVE_DECL_MALLOC
+char *malloc ();
+#endif
+
+#if !HAVE_DECL_MEMCHR
+char *memchr ();
+#endif
+
+#if !HAVE_DECL_REALLOC
+char *realloc ();
+#endif
+
+#if !HAVE_DECL_STPCPY
+# ifndef stpcpy
+char *stpcpy ();
+# endif
+#endif
+
+#if !HAVE_DECL_STRNDUP
+char *strndup ();
+#endif
+
+#if !HAVE_DECL_STRSTR
+char *strstr ();
+#endif
+
+#if !HAVE_DECL_GETENV
+char *getenv ();
+#endif
+
+#if !HAVE_DECL_LSEEK
+off_t lseek ();
+#endif
+
+/* This is needed on some AIX systems.  */
+#if !HAVE_DECL_STRTOUL
+unsigned long strtoul ();
+#endif
+
+/* This is needed on some AIX systems.  */
+#if !HAVE_DECL_STRTOULL && HAVE_UNSIGNED_LONG_LONG
+unsigned long long strtoull ();
+#endif
+
+#if !HAVE_DECL_GETLOGIN
+char *getlogin ();
+#endif
+
+#if !HAVE_DECL_TTYNAME
+char *ttyname ();
+#endif
+
+#if !HAVE_DECL_GETEUID
+uid_t geteuid ();
+#endif
+
+#if !HAVE_DECL_GETPWUID
+struct passwd *getpwuid ();
+#endif
+
+#if !HAVE_DECL_GETGRGID
+struct group *getgrgid ();
+#endif
+
+#if !HAVE_DECL_GETUID
+uid_t getuid ();
+#endif
+
+#include "xalloc.h"
+
+#if ! defined HAVE_MEMPCPY && ! defined mempcpy
+/* Be CAREFUL that there are no side effects in N.  */
+# define mempcpy(D, S, N) ((void *) ((char *) memcpy (D, S, N) + (N)))
+#endif
+
+/* Include automatically-generated macros for unlocked I/O.  */
+#include "unlocked-io.h"
+
+#define SAME_INODE(Stat_buf_1, Stat_buf_2) \
+  ((Stat_buf_1).st_ino == (Stat_buf_2).st_ino \
+   && (Stat_buf_1).st_dev == (Stat_buf_2).st_dev)
+
+#define DOT_OR_DOTDOT(Basename) \
+  (Basename[0] == '.' && (Basename[1] == '\0' \
+			  || (Basename[1] == '.' && Basename[2] == '\0')))
+
+#if SETVBUF_REVERSED
+# define SETVBUF(Stream, Buffer, Type, Size) \
+    setvbuf (Stream, Type, Buffer, Size)
+#else
+# define SETVBUF(Stream, Buffer, Type, Size) \
+    setvbuf (Stream, Buffer, Type, Size)
+#endif
+
+/* Factor out some of the common --help and --version processing code.  */
+
+/* These enum values cannot possibly conflict with the option values
+   ordinarily used by commands, including CHAR_MAX + 1, etc.  Avoid
+   CHAR_MIN - 1, as it may equal -1, the getopt end-of-options value.  */
+enum
+{
+  GETOPT_HELP_CHAR = (CHAR_MIN - 2),
+  GETOPT_VERSION_CHAR = (CHAR_MIN - 3)
+};
+
+#define GETOPT_HELP_OPTION_DECL \
+  "help", no_argument, 0, GETOPT_HELP_CHAR
+#define GETOPT_VERSION_OPTION_DECL \
+  "version", no_argument, 0, GETOPT_VERSION_CHAR
+
+#define case_GETOPT_HELP_CHAR			\
+  case GETOPT_HELP_CHAR:			\
+    usage (EXIT_SUCCESS);			\
+    break;
+
+#define HELP_OPTION_DESCRIPTION \
+  _("      --help     display this help and exit\n")
+#define VERSION_OPTION_DESCRIPTION \
+  _("      --version  output version information and exit\n")
+
+#include "closeout.h"
+#include "version-etc.h"
+
+#define case_GETOPT_VERSION_CHAR(Program_name, Authors)			\
+  case GETOPT_VERSION_CHAR:						\
+    version_etc (stdout, Program_name, PACKAGE, VERSION, Authors);	\
+    exit (EXIT_SUCCESS);						\
+    break;
+
+#ifndef MAX
+# define MAX(a, b) ((a) > (b) ? (a) : (b))
+#endif
+
+#ifndef MIN
+# define MIN(a,b) (((a) < (b)) ? (a) : (b))
+#endif
+
+#ifndef CHAR_BIT
+# define CHAR_BIT 8
+#endif
+
+/* The extra casts work around common compiler bugs.  */
+#define TYPE_SIGNED(t) (! ((t) 0 < (t) -1))
+/* The outer cast is needed to work around a bug in Cray C 5.0.3.0.
+   It is necessary at least when t == time_t.  */
+#define TYPE_MINIMUM(t) ((t) (TYPE_SIGNED (t) \
+			      ? ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1) : (t) 0))
+#define TYPE_MAXIMUM(t) ((t) (~ (t) 0 - TYPE_MINIMUM (t)))
+
+/* Upper bound on the string length of an integer converted to string.
+   302 / 1000 is ceil (log10 (2.0)).  Subtract 1 for the sign bit;
+   add 1 for integer division truncation; add 1 more for a minus sign.  */
+#define INT_STRLEN_BOUND(t) ((sizeof (t) * CHAR_BIT - 1) * 302 / 1000 + 2)
+
+#ifndef CHAR_MIN
+# define CHAR_MIN TYPE_MINIMUM (char)
+#endif
+
+#ifndef CHAR_MAX
+# define CHAR_MAX TYPE_MAXIMUM (char)
+#endif
+
+#ifndef SCHAR_MIN
+# define SCHAR_MIN (-1 - SCHAR_MAX)
+#endif
+
+#ifndef SCHAR_MAX
+# define SCHAR_MAX (CHAR_MAX == UCHAR_MAX ? CHAR_MAX / 2 : CHAR_MAX)
+#endif
+
+#ifndef UCHAR_MAX
+# define UCHAR_MAX TYPE_MAXIMUM (unsigned char)
+#endif
+
+#ifndef SHRT_MIN
+# define SHRT_MIN TYPE_MINIMUM (short int)
+#endif
+
+#ifndef SHRT_MAX
+# define SHRT_MAX TYPE_MAXIMUM (short int)
+#endif
+
+#ifndef INT_MAX
+# define INT_MAX TYPE_MAXIMUM (int)
+#endif
+
+#ifndef UINT_MAX
+# define UINT_MAX TYPE_MAXIMUM (unsigned int)
+#endif
+
+#ifndef LONG_MAX
+# define LONG_MAX TYPE_MAXIMUM (long)
+#endif
+
+#ifndef ULONG_MAX
+# define ULONG_MAX TYPE_MAXIMUM (unsigned long)
+#endif
+
+#ifndef SIZE_MAX
+# define SIZE_MAX TYPE_MAXIMUM (size_t)
+#endif
+
+#ifndef UINTMAX_MAX
+# define UINTMAX_MAX TYPE_MAXIMUM (uintmax_t)
+#endif
+
+#ifndef OFF_T_MIN
+# define OFF_T_MIN TYPE_MINIMUM (off_t)
+#endif
+
+#ifndef OFF_T_MAX
+# define OFF_T_MAX TYPE_MAXIMUM (off_t)
+#endif
+
+#ifndef UID_T_MAX
+# define UID_T_MAX TYPE_MAXIMUM (uid_t)
+#endif
+
+#ifndef GID_T_MAX
+# define GID_T_MAX TYPE_MAXIMUM (gid_t)
+#endif
+
+#ifndef PID_T_MAX
+# define PID_T_MAX TYPE_MAXIMUM (pid_t)
+#endif
+
+#ifndef CHAR_BIT
+# define CHAR_BIT 8
+#endif
+
+/* Use this to suppress gcc's `...may be used before initialized' warnings. */
+#ifdef lint
+# define IF_LINT(Code) Code
+#else
+# define IF_LINT(Code) /* empty */
+#endif
+
+#ifndef __attribute__
+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+#  define __attribute__(x)
+# endif
+#endif
+
+#ifndef ATTRIBUTE_NORETURN
+# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
+#endif
+
+#ifndef ATTRIBUTE_UNUSED
+# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+#endif
+
+#if defined strdupa
+# define ASSIGN_STRDUPA(DEST, S)		\
+  do { DEST = strdupa(S); } while (0)
+#else
+# define ASSIGN_STRDUPA(DEST, S)		\
+  do						\
+    {						\
+      const char *s_ = (S);			\
+      size_t len_ = strlen (s_) + 1;		\
+      char *tmp_dest_ = (char *) alloca (len_);	\
+      DEST = memcpy (tmp_dest_, (s_), len_);	\
+    }						\
+  while (0)
+#endif
+
+#ifndef EOVERFLOW
+# define EOVERFLOW EINVAL
+#endif
+
+#if ! HAVE_FSEEKO && ! defined fseeko
+# define fseeko(s, o, w) ((o) == (long) (o)		\
+			  ? fseek (s, o, w)		\
+			  : (errno = EOVERFLOW, -1))
+#endif
diff --git a/contrib/gnu-sort/src/system.h b/contrib/gnu-sort/src/system.h
new file mode 100644
index 0000000..6e11e44
--- /dev/null
+++ b/contrib/gnu-sort/src/system.h
@@ -0,0 +1,286 @@
+/* system-dependent definitions for fileutils, textutils, and sh-utils packages.
+   Copyright (C) 1989, 1991-2001 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Include sys/types.h before this file.  */
+
+#include <sys/stat.h>
+
+#if !defined(HAVE_MKFIFO)
+# define mkfifo(path, mode) (mknod ((path), (mode) | S_IFIFO, 0))
+#endif
+
+#if HAVE_SYS_PARAM_H
+# include <sys/param.h>
+#endif
+
+/* <unistd.h> should be included before any preprocessor test
+   of _POSIX_VERSION.  */
+#if HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+
+#ifndef STDIN_FILENO
+# define STDIN_FILENO 0
+#endif
+
+#ifndef STDOUT_FILENO
+# define STDOUT_FILENO 1
+#endif
+
+#ifndef STDERR_FILENO
+# define STDERR_FILENO 2
+#endif
+
+
+#if HAVE_LIMITS_H
+/* limits.h must come before pathmax.h because limits.h on some systems
+   undefs PATH_MAX, whereas pathmax.h sets PATH_MAX.  */
+# include <limits.h>
+#endif
+
+#include "pathmax.h"
+
+#if TIME_WITH_SYS_TIME
+# include <sys/time.h>
+# include <time.h>
+#else
+# if HAVE_SYS_TIME_H
+#  include <sys/time.h>
+# else
+#  include <time.h>
+# endif
+#endif
+
+/* Since major is a function on SVR4, we can't use `ifndef major'.  */
+#if MAJOR_IN_MKDEV
+# include <sys/mkdev.h>
+# define HAVE_MAJOR
+#endif
+#if MAJOR_IN_SYSMACROS
+# include <sys/sysmacros.h>
+# define HAVE_MAJOR
+#endif
+#ifdef major			/* Might be defined in sys/types.h.  */
+# define HAVE_MAJOR
+#endif
+
+#ifndef HAVE_MAJOR
+# define major(dev)  (((dev) >> 8) & 0xff)
+# define minor(dev)  ((dev) & 0xff)
+# define makedev(maj, min)  (((maj) << 8) | (min))
+#endif
+#undef HAVE_MAJOR
+
+#if HAVE_UTIME_H
+# include <utime.h>
+#endif
+
+/* Some systems (even some that do have <utime.h>) don't declare this
+   structure anywhere.  */
+#ifndef HAVE_STRUCT_UTIMBUF
+struct utimbuf
+{
+  long actime;
+  long modtime;
+};
+#endif
+
+/* Don't use bcopy!  Use memmove if source and destination may overlap,
+   memcpy otherwise.  */
+
+#if HAVE_STRING_H
+# if !STDC_HEADERS && HAVE_MEMORY_H
+#  include <memory.h>
+# endif
+# include <string.h>
+#else
+# include <strings.h>
+#endif
+
+#include <errno.h>
+#ifndef errno
+extern int errno;
+#endif
+
+#if HAVE_STDBOOL_H
+# include <stdbool.h>
+#else
+typedef enum {false = 0, true = 1} bool;
+#endif
+
+#if HAVE_STDLIB_H
+# define getopt system_getopt
+# include <stdlib.h>
+# undef getopt
+#endif
+
+/* The following test is to work around the gross typo in
+   systems like Sony NEWS-OS Release 4.0C, whereby EXIT_FAILURE
+   is defined to 0, not 1.  */
+#if !EXIT_FAILURE
+# undef EXIT_FAILURE
+# define EXIT_FAILURE 1
+#endif
+
+#ifndef EXIT_SUCCESS
+# define EXIT_SUCCESS 0
+#endif
+
+#if HAVE_FCNTL_H
+# include <fcntl.h>
+#else
+# include <sys/file.h>
+#endif
+
+#if !defined (SEEK_SET)
+# define SEEK_SET 0
+# define SEEK_CUR 1
+# define SEEK_END 2
+#endif
+#ifndef F_OK
+# define F_OK 0
+# define X_OK 1
+# define W_OK 2
+# define R_OK 4
+#endif
+
+/* For systems that distinguish between text and binary I/O.
+   O_BINARY is usually declared in fcntl.h  */
+#if !defined O_BINARY && defined _O_BINARY
+  /* For MSC-compatible compilers.  */
+# define O_BINARY _O_BINARY
+# define O_TEXT _O_TEXT
+#endif
+
+#ifdef __BEOS__
+  /* BeOS 5 has O_BINARY and O_TEXT, but they have no effect.  */
+# undef O_BINARY
+# undef O_TEXT
+#endif
+
+#if O_BINARY
+# ifndef __DJGPP__
+#  define setmode _setmode
+#  define fileno(_fp) _fileno (_fp)
+# endif /* not DJGPP */
+# define SET_MODE(_f, _m) setmode (_f, _m)
+# define SET_BINARY(_f) do {if (!isatty(_f)) setmode (_f, O_BINARY);} while (0)
+# define SET_BINARY2(_f1, _f2)		\
+  do {					\
+    if (!isatty (_f1))			\
+      {					\
+        setmode (_f1, O_BINARY);	\
+	if (!isatty (_f2))		\
+	  setmode (_f2, O_BINARY);	\
+      }					\
+  } while(0)
+#else
+# define SET_MODE(_f, _m) (void)0
+# define SET_BINARY(f) (void)0
+# define SET_BINARY2(f1,f2) (void)0
+# define O_BINARY 0
+# define O_TEXT 0
+#endif /* O_BINARY */
+
+#if HAVE_DIRENT_H
+# include <dirent.h>
+# define NLENGTH(direct) (strlen((direct)->d_name))
+#else /* not HAVE_DIRENT_H */
+# define dirent direct
+# define NLENGTH(direct) ((direct)->d_namlen)
+# if HAVE_SYS_NDIR_H
+#  include <sys/ndir.h>
+# endif /* HAVE_SYS_NDIR_H */
+# if HAVE_SYS_DIR_H
+#  include <sys/dir.h>
+# endif /* HAVE_SYS_DIR_H */
+# if HAVE_NDIR_H
+#  include <ndir.h>
+# endif /* HAVE_NDIR_H */
+#endif /* HAVE_DIRENT_H */
+
+#if CLOSEDIR_VOID
+/* Fake a return value. */
+# define CLOSEDIR(d) (closedir (d), 0)
+#else
+# define CLOSEDIR(d) closedir (d)
+#endif
+
+/* Get or fake the disk device blocksize.
+   Usually defined by sys/param.h (if at all).  */
+#if !defined DEV_BSIZE && defined BSIZE
+# define DEV_BSIZE BSIZE
+#endif
+#if !defined DEV_BSIZE && defined BBSIZE /* SGI */
+# define DEV_BSIZE BBSIZE
+#endif
+#ifndef DEV_BSIZE
+# define DEV_BSIZE 4096
+#endif
+
+/* Extract or fake data from a `struct stat'.
+   ST_BLKSIZE: Preferred I/O blocksize for the file, in bytes.
+   ST_NBLOCKS: Number of blocks in the file, including indirect blocks.
+   ST_NBLOCKSIZE: Size of blocks used when calculating ST_NBLOCKS.  */
+#ifndef HAVE_STRUCT_STAT_ST_BLOCKS
+# define ST_BLKSIZE(statbuf) DEV_BSIZE
+# if defined(_POSIX_SOURCE) || !defined(BSIZE) /* fileblocks.c uses BSIZE.  */
+#  define ST_NBLOCKS(statbuf) \
+  (S_ISREG ((statbuf).st_mode) \
+   || S_ISDIR ((statbuf).st_mode) \
+   ? (statbuf).st_size / ST_NBLOCKSIZE + ((statbuf).st_size % ST_NBLOCKSIZE != 0) : 0)
+# else /* !_POSIX_SOURCE && BSIZE */
+#  define ST_NBLOCKS(statbuf) \
+  (S_ISREG ((statbuf).st_mode) \
+   || S_ISDIR ((statbuf).st_mode) \
+   ? st_blocks ((statbuf).st_size) : 0)
+# endif /* !_POSIX_SOURCE && BSIZE */
+#else /* HAVE_STRUCT_STAT_ST_BLOCKS */
+/* Some systems, like Sequents, return st_blksize of 0 on pipes. */
+# define ST_BLKSIZE(statbuf) ((statbuf).st_blksize > 0 \
+			       ? (statbuf).st_blksize : DEV_BSIZE)
+# if defined(hpux) || defined(__hpux__) || defined(__hpux)
+/* HP-UX counts st_blocks in 1024-byte units.
+   This loses when mixing HP-UX and BSD filesystems with NFS.  */
+#  define ST_NBLOCKSIZE 1024
+# else /* !hpux */
+#  if defined(_AIX) && defined(_I386)
+/* AIX PS/2 counts st_blocks in 4K units.  */
+#   define ST_NBLOCKSIZE (4 * 1024)
+#  else /* not AIX PS/2 */
+#   if defined(_CRAY)
+#    define ST_NBLOCKS(statbuf) \
+  (S_ISREG ((statbuf).st_mode) \
+   || S_ISDIR ((statbuf).st_mode) \
+   ? (statbuf).st_blocks * ST_BLKSIZE(statbuf)/ST_NBLOCKSIZE : 0)
+#   endif /* _CRAY */
+#  endif /* not AIX PS/2 */
+# endif /* !hpux */
+#endif /* HAVE_STRUCT_STAT_ST_BLOCKS */
+
+#ifndef ST_NBLOCKS
+# define ST_NBLOCKS(statbuf) \
+  (S_ISREG ((statbuf).st_mode) \
+   || S_ISDIR ((statbuf).st_mode) \
+   ? (statbuf).st_blocks : 0)
+#endif
+
+#ifndef ST_NBLOCKSIZE
+# define ST_NBLOCKSIZE 512
+#endif
+
+#include "sys2.h"