#include <stdio.h>

#define IDX signed long
#define byte unsigned char

char *inname = NULL, *outname = NULL;
FILE *in, *out;

IDX fields = 0;
int fieldlen = 0;
byte *(*readptr)(IDX);
void (*interchange)(IDX, IDX);

byte *buf; /* for in-memory sorting */

byte *bufa, *bufb;



/* Error routines */

void error(char *msg) {
  fputs(msg, stderr);
  fputs("\n", stderr);
  exit(1);
}

void fileerr(char *fname) {
  perror(fname);
  exit(1);
}

void readerr() {
  if (ferror(in)) fileerr(inname);
  fputs("Error reading from ", stderr);
  fputs(inname, stderr);
  fputs("\n", stderr);
  exit(1);
}

void writeerr() {
  if (ferror(out)) fileerr(outname);
  fputs("Error writing to ", stderr);
  fputs(outname, stderr);
  fputs("\n", stderr);
  exit(1);
}

void usage() {
  error("Usage: sort fieldlength input-file [output-file] [options]\n"
	"where 'options' are:\n"
        "        -f        sort in file\n"
	"        -i        ignore excess bytes\n"
        "        -m        sort in memory [default]\n"
	"        -r        replace input file\n"
	);
}


/* Converts a field index to a pointer into the buffer. */
byte *memptr(IDX i) {
  return buf + (fieldlen * i);
}

byte *currentbuf = NULL;
/* Reads a field from disk into a buffer.  Alternates between two
   static buffers, so you can deal with two fields at once. */
byte *fileptr(IDX i) {
  if (currentbuf == bufa) currentbuf = bufb;
  else currentbuf = bufa;
  if (fseek(in, fieldlen*i, SEEK_SET)) fileerr(inname);
  if (!fread(currentbuf, fieldlen, 1, in)) readerr();
  return currentbuf;
}

/* Swaps fields a and b in the buffer. */
void mem_interchange(IDX a, IDX b) {
  register byte *ap = memptr(a);
  register byte *bp = memptr(b);
  register byte temp;
  register int c;
  for (c=0; c<fieldlen; c++) {
    temp = *ap;
    *ap = *bp;
    *bp = temp;
    ap++;
    bp++;
  }
}

void file_interchange(IDX a, IDX b) {
  byte *ap = fileptr(a);
  byte *bp = fileptr(b);
  if (fseek(in, fieldlen*b, SEEK_SET)) fileerr(inname);
  if (!fwrite(ap, fieldlen, 1, in)) writeerr();
  if (fseek(in, fieldlen*a, SEEK_SET)) fileerr(inname);
  if (!fwrite(bp, fieldlen, 1, in)) writeerr();
}

/* Returns 1 if (field a >= field b), 0 otherwise */
 int compare(IDX a, IDX b) {
  if (a >= fields) return 1;
  else if (b >= fields) return 0;
  else {
    register byte *ap = (*readptr)(a);
    register byte *bp = (*readptr)(b);
    register int c;
    for (c=0; c<fieldlen; c++) {
      if (*ap < *bp) return 0;
      else if (*ap > *bp) return 1;
      ap++;
      bp++;
    }
  }
  return 1;
}

int partition(IDX m, IDX p) {
  IDX i = m;
  while (1) {
    do i++; while (!compare(i, m));
    do p--; while (!compare(m, p));
    if (i < p) (*interchange)(i, p);
    else break;
  }
  (*interchange)(m, p);
  return p;
}

void quicksort(IDX p, IDX q) {
  if (p < q) {
    IDX j = q+1;
    j = partition(p, j);
    quicksort(p, j-1);
    quicksort(j+1, q);
  }
}

#define INPLACE 1
#define IGNORE  2
#define REPLACE 4

void main(int argc, char **argv) {
  int i;
  char *p;
  int flags = 0;
  long flen, done;

  /* read the command-line arguments */
  for (i=1; i<argc; i++) {
    if (argv[i][0] == '-')
      for (p=argv[i]+1; *p != 0; p++) {
	switch (*p) {
	case 'f': case 'F': flags |= INPLACE; break;
	case 'i': case 'I': flags |= IGNORE; break;
	case 'm': case 'M': flags &= ~INPLACE; break;
	case 'r': case 'R': flags |= REPLACE; break;
	default: usage();
	}
      } else {
      if (fieldlen == 0) {
	fieldlen = atol(argv[i]);
	if (fieldlen < 1) usage();
      } else if (inname == NULL) inname = argv[i];
      else if (outname == NULL) outname = argv[i];
      else usage();
    }
  }

  if (inname == NULL) usage();

  if (flags & REPLACE) {
    if (outname == NULL) outname = inname;
    else error("Error: Cannot specify a output file with the -r option");
  }

  /* find the number of fields to sort */
  in = fopen(inname, "rb");
  if (in == NULL) fileerr(inname);
  if (fseek(in, 0, SEEK_END)) fileerr(inname);
  flen = ftell(in);
  if (flen == -1L) fileerr(inname);
  fields = flen / fieldlen;
  if (flags & IGNORE) flen = fieldlen * fields;
  else if (flen % fieldlen != 0) {
    error("Error: File length is not divisible by field length");
  }


  if (flags & INPLACE) {
    fclose(in);
    if (outname != NULL) 
      error("Error: Cannot specify an output file with the -f option");
    outname = inname;
    readptr = &fileptr;
    interchange = &file_interchange;
    bufa = (byte *)malloc(fieldlen);
    bufb = (byte *)malloc(fieldlen);
    if (bufa == NULL || bufb == NULL)
      error("Error: Cannot allocate memory");
    in = fopen(inname, "r+b");
    if (in == NULL) fileerr(inname);
    out = in;

    quicksort(0, fields-1);
  }

  else {
    readptr = &memptr;
    interchange = &mem_interchange;

    buf = (byte *)malloc(flen);
    if (buf == NULL)
      error("Error: Cannot allocate memory");
    if (fseek(in, 0, SEEK_SET)) fileerr(inname);
    done = fread(buf, fieldlen, fields, in);
    if (done < fields) readerr();

    quicksort(0, fields-1);
    fclose(in);

    if (outname == NULL) {
      out = stdout;
      outname = "stdout";
    } else {
      out = fopen(outname, "wb");
      if (out == NULL) fileerr(outname);
    }
    done = fwrite(buf, fieldlen, fields, out);
    if (done < fields) writeerr();
  }

}