/*- BSP.C -------------------------------------------------------------------*

 Node builder for DOOM levels (c) 1998 Colin Reed, version 3.0 (dos extended)

 Performance increased 200% over 1.2x

 Many thanks to Mark Harrison for finding a bug in 1.1 which caused some
 texture align problems when a flipped SEG was split.

 Credit to:-

 Raphael Quinet (A very small amount of code has been borrowed from DEU).

 Matt Fell for the doom specs.

 Lee Killough for performance tuning, support for multilevel wads, special
 effects, and wads with lumps besides levels.

 Also, the original idea for some of the techniques where also taken from the
 comment at the bottom of OBJECTS.C in DEU, and the doc by Matt Fell about
 the nodes.

 Use this code for your own editors, but please credit me.

*---------------------------------------------------------------------------*/
/*
 * Modified 2010/08/04 by Christopher Bazley
 */

#include "structs.h"
#include "bsp.h"

#ifdef HAVE_UNISTD_H
# include <unistd.h>
#endif

#include <errno.h>

#ifdef RISCOS
#include "kernel.h"
#define FILE_EXT ""
#else /* RISCOS */
#define FILE_EXT ".wad"
#endif /* RISCOS */

#define DEFAULT_NAME "tmp" FILE_EXT

enum
{
  BUF_SIZE        = 1024,
  WAD_FILE_TYPE   = 0x16c, /* RISC OS Doom WAD file type */
  OSFILE_SET_TYPE = 18     /* _kernel_osfile reason code */
};

/*- Global Vars ------------------------------------------------------------*/

static FILE *outfile;
static char *testwad;
static const char *outwad;
const char* unlinkwad;

struct Seg *(*PickNode)(struct Seg *, const bbox_t bbox)=PickNode_traditional;
static int visplane;
int noreject = 0;

static unsigned char pcnt;

static struct lumplist *current_level;

static struct wad_header wad;

/*- Prototypes -------------------------------------------------------------*/

static FILE *infile;

/* fcopy - function to completely copy one stream to another */

static void fcopy(FILE* in, FILE* out)
{
	char buf[BUF_SIZE];
	int rb;
	while ((rb = fread(buf, 1, sizeof buf, in)) > 0) {
		fwrite(buf, 1, rb, out);
	}
}

/*--------------------------------------------------------------------------*/

void progress(void)
{
	if((verbosity > 1) && !((++pcnt)&31))
	{
#ifdef NO_BACKSPACE
		Verbose(".");
#else /* NO_BACKSPACE */
		Verbose("%c\b","/-\\|"[((pcnt)>>5)&3]);
#endif /* NO_BACKSPACE */
	}
}

/*- copy a lump from the input file to the output file ---*/
static void copy_lump(struct lumplist *lump)
{
 char buf[BUF_SIZE];
 size_t nread, rem;

 /* Find the start of the lump in the input WAD file */
 seek_lump(lump);

 /* Copy successive chunks of the lump until no bytes left to copy */
 for (rem = lump->dir.length; rem > 0; rem -= nread)
  {
   /* Read as much of the remaining data as will fit into the buffer */
   size_t n = rem > sizeof(buf) ? sizeof(buf) : rem;
   nread = read_chars(buf, n);
   if (nread != n)
     read_error(lump);

   /* Write all the data that was read into the buffer */
   if (write_chars(buf, nread) != nread)
     write_error(lump);
  }
}

/*- lump name comparison function for binary search ------------------------*/
int bs_compare(const void *key, const void *elem)
{
  return strncmp(key, elem, sizeof(((struct directory *)0)->name));
}

/*- get the directory from a wad file --------------------------------------*/
/* rewritten by Lee Killough to support multiple levels and extra lumps */

static struct lumplist *OpenWadFile(const char *filename)
{
 unsigned long i;
 struct lumplist *lumplist = NULL;
 struct lumplist **levelp = NULL, **topp = &lumplist;

 infile = fopen(filename,"rb");
 if (!infile)
   ProgError("Error: Cannot open WAD file %s", filename);

#if defined(HAVE_TMPFILE) && defined(ESPIPE)
 if (fseek(infile,0,SEEK_SET) == -1) {
   FILE* intmp;
   if (errno != ESPIPE) {
     perror("fseek"); exit(errno);
   }
   if (!(intmp = tmpfile())) {
     perror("tmpfile");
     ProgError("Input was not seekable and failed to create temp file");
   }
   Verbose("Copying piped input to temporary file\n");
   fcopy(infile,intmp);
   fclose(infile);
   rewind(infile = intmp);
 }
#endif /* defined(HAVE_TMPFILE) && defined(ESPIPE) */
 if (read_chars(wad.type, sizeof(wad.type)) != sizeof(wad.type) ||
     read_uint32(&wad.num_entries) || read_uint32(&wad.dir_start))
   ProgError("Failed to read header of file %s", filename);

 if ((wad.type[0]!='I' && wad.type[0]!='P') || wad.type[1]!='W' ||
      wad.type[2]!='A' || wad.type[3]!='D')
   ProgError("%s does not appear to be a WAD file -- bad magic", filename);

 Verbose("Opened %cWAD file: %s. %" PRIu32 " dir entries at 0x%08" PRIx32 ".\n",
         wad.type[0],filename,wad.num_entries,wad.dir_start);

 if (fseek(infile, wad.dir_start, SEEK_SET))
   ProgError("Failed to seek dir entries in file %s", filename);

 current_level = NULL;
 for (i = 0; i < wad.num_entries; i++)
  {
   register struct lumplist *l=GetMemory(sizeof(*l));
   register int islevel = 0;
   struct directory *dir = &l->dir;

   /* Read directory entry from file */
   if (read_uint32(&dir->start) ||
       read_uint32(&dir->length) ||
       read_chars(dir->name, sizeof(dir->name)) != sizeof(dir->name))
     ProgError("Failed to read dir entry %lu from file %s", i, filename);

   l->data=NULL;
   l->write_data = copy_lump; /* default is to copy lump from input file */
   l->next=NULL;
   l->level=NULL;

   /* Is this lump the start of a new level? */
   if ((dir->name[0]=='E' && dir->name[2]=='M' &&
        isdigit((unsigned char)dir->name[1]) &&
        isdigit((unsigned char)dir->name[3]) &&
        (dir->name[4] == '\0' || (isdigit((unsigned char)dir->name[4]) &&
                                  dir->name[5] == '\0')  )) || (
        dir->name[0]=='M' && dir->name[1]=='A' &&
        dir->name[2]=='P' && !dir->name[5] &&
        isdigit((unsigned char)dir->name[3]) &&
        isdigit((unsigned char)dir->name[4])))
    {
     /* Begin new level */
     islevel=1;
     current_level = NULL;
    }
   else if (current_level != NULL)
    {
     static const char lump_names[][9] =
     {
       "BEHAVIOR", /* Not in the unofficial Doom specs */
       "BLOCKMAP",
       "LINEDEFS",
       "NODES",
       "REJECT",
       "SCRIPTS", /* Not in the unofficial Doom specs */
       "SECTORS",
       "SEGS",
       "SIDEDEFS",
       "SSECTORS",
       "THINGS",
       "VERTEXES"
     };
     const char *match;

     if (FindDir(dir->name))
      {
       Verbose("Warning: Duplicate entry \"%-.8s\" ignored in \"%-.8s\"\n",
         dir->name, current_level->dir.name);
       free(l);
       continue;
      }

     /* The previous lump was part of a level, is this one? */
     match = bsearch(dir->name, lump_names, NELEMS(lump_names),
                     sizeof(lump_names[0]), bs_compare);
     if (match != NULL)
      {                       /* Store in current level */
       *levelp = l; /* fix up forward link */
       levelp = &l->next;
      }
     else
      {
       /* Otherwise, it's the end of the level. */
       current_level = NULL;
      }
    }

   Verbose("Read dir entry \"%-.8s\" in \"%-.8s\" "
           "(start: 0x%08" PRIx32 " length: 0x%08" PRIx32 ")\n",
           dir->name,
           current_level == NULL ? "[root]" : current_level->dir.name,
           dir->start, dir->length);

   if (current_level == NULL)
    {
     /* Add this lump or completed level to the lump list */
     *topp = l; /* fix up forward link */
     topp = &l->next;
    }

   /* Is this lump the start of a new level? */
   if (islevel)
    {
     current_level = l;
     levelp = &l->level;
    }
  }

  return lumplist;
}

/*- find the pointer to a resource -----------------------*/

struct lumplist *FindDir(const char *name)
{
 struct lumplist *l = current_level->level;
 while (l && strncmp(l->dir.name, name, sizeof(l->dir.name)))
   l=l->next;
 return l;
}

/*- report an error reading a lump from the input file ---*/

void read_error(const struct lumplist *lump)
{
 ProgError("Unable to read wad directory entry \"%-.8s\" in \"%-.8s\"\n",
           lump->dir.name, current_level == NULL ? "[root]" : current_level->dir.name);
}

/*- seek the start of a lump in the input file -----------*/

void seek_lump(const struct lumplist *lump)
{
 if (fseek(infile, lump->dir.start, SEEK_SET))
   read_error(lump);
}

/*- read a signed 16 bit integer from the input file -----*/

int read_int16(int16_t *s)
{
 return read_uint16((uint16_t *)s);
}

/*- read an unsigned 16 bit integer from the input file --*/

int read_uint16(uint16_t *s)
{
 uint8_t buffer[sizeof(*s)];

 if (fread(buffer, sizeof(*s), 1, infile) != 1)
   return 1; /* non-zero means error */

 *s = buffer[0] | buffer[1] << 8;
 return 0; /* zero means success */
}

/*- read an unsigned 32 bit integer from the input file --*/

int read_uint32(uint32_t *s)
{
 uint8_t buffer[sizeof(*s)];

 if (fread(buffer, sizeof(*s), 1, infile) != 1)
   return 1; /* non-zero means error */

 *s = buffer[0] | buffer[1] << 8 |
      buffer[2] << 16 | buffer[3] << 24;
 return 0; /* zero means success */
}

/*- read characters from the input file ------------------*/

size_t read_chars(char s[], size_t n)
{
 return fread(s, sizeof(*s), n, infile);
}

/*- report an error writing a lump to the output file ----*/

void write_error(const struct lumplist *lump)
{
 ProgError("Failure writing wad directory entry \"%-.8s\" in \"%-.8s\"\n",
           lump->dir.name, current_level == NULL ? "[root]" : current_level->dir.name);
}

/*- write a signed 16 bit integer to the output file -----*/

int write_int16(const int16_t *s)
{
 return write_uint16((const uint16_t *)s);
}

/*- write an unsigned 16 bit integer to the output file --*/

int write_uint16(const uint16_t *s)
{
 uint8_t buffer[sizeof(*s)];
 uint16_t out = *s;

 buffer[0] = out;
 buffer[1] = out >> 8;

 /* non-zero means error */
 return fwrite(buffer, sizeof(*s), 1, outfile) != 1;
}

/*- write an unsigned 32 bit integer to the output file --*/

int write_uint32(const uint32_t *s)
{
 uint8_t buffer[sizeof(*s)];
 uint32_t out = *s;

 buffer[0] = out;
 buffer[1] = out >> 8;
 buffer[2] = out >> 16;
 buffer[3] = out >> 24;

 /* non-zero means error */
 return fwrite(buffer, sizeof(s), 1, outfile) != 1;
}

/*- write bytes to the output file -----------------------*/

size_t write_chars(const char s[], size_t n)
{
 return fwrite(s, sizeof(*s), n, outfile);
}

/* Add a lump to current level
   by Lee Killough */

void add_lump(const char *name, data_callback *write_data, void *data)
{
 struct lumplist *l;
 for (l = current_level->level; l != NULL; l = l->next)
   if (!strncmp(name, l->dir.name, sizeof(l->dir.name)))
     break;
 if (!l)
  {
   l=current_level->level;
   while (l->next)
     l=l->next;
   l->next = GetMemory(sizeof(*l));
   l = l->next;
   l->next=NULL;
   strncpy(l->dir.name, name, sizeof(l->dir.name));
  }
 l->level=NULL;
 l->write_data = write_data;
 l->data=data;
}

static void sortlump(struct lumplist **link)
{
 static const char *const lumps[10]={"THINGS", "LINEDEFS", "SIDEDEFS",
  "VERTEXES", "SEGS", "SSECTORS", "NODES", "SECTORS", "REJECT", "BLOCKMAP"};
 int i=sizeof(lumps)/sizeof(*lumps)-1;
 struct lumplist **l;
 do
   for (l=link;*l;l=&(*l)->next)
     if (!strncmp(lumps[i],(*l)->dir.name,sizeof((*l)->dir.name)))
      {
       struct lumplist *t=(*l)->next;
       (*l)->next=*link;
       *link=*l;
       *l=t;
       break;
      }
 while (--i>=0);
}

/*- write lumps to output WAD file by walking a tree -----*/

static void write_lump(struct lumplist *lump)
{
 long pos;

 Fortify_CheckAllMemory();

 /* Get output wad file pointer before writing lump */
 pos = ftell(outfile);
 if (pos == -1)
   write_error(lump);

 /* Do not overwrite lump->dir.start yet in case it is used
    to read from the input file */

 if (lump->level == NULL)
  {
   if (lump->write_data != NULL)
    {
     lump->write_data(lump);
    }

   /* Get output wad file pointer after writing lump */
   lump->dir.start = (uint32_t)pos;
   pos = ftell(outfile);
   if (pos == -1)
     write_error(lump);

   lump->dir.length = (uint32_t)(pos - lump->dir.start);
  }
 else
  {
   struct lumplist *l, *previous_level;

   previous_level = current_level;
   current_level = lump;

   Verbose("\nBuilding nodes on %-.8s\n\n", lump->dir.name);
   DoLevel();

   /* Sort recognised lumps within this level */
   sortlump(&lump->level);

   /* Write all lumps within this level */
   for (l = lump->level; l != NULL; l = l->next)
    {
     write_lump(l);
    }
   LevelFinished();
   current_level = previous_level;

   lump->dir.start = (uint32_t)pos;
   lump->dir.length = 0;
  }

  Verbose("Wrote lump \"%-.8s\" in \"%-.8s\" "
          "(start: 0x%08" PRIx32 " length: 0x%08" PRIx32 ")\n",
          lump->dir.name, current_level == NULL ? "[root]" : current_level->dir.name,
          lump->dir.start, lump->dir.length);
}

/*- write catalog to output WAD file and free lump tree --*/

static void write_catalog(struct lumplist *lump)
{
 /* Keep track of the number of catalog entries */
 wad.num_entries ++;

 /* Write catalogue entry */
 if (write_uint32(&lump->dir.start) ||
     write_uint32(&lump->dir.length) ||
     write_chars(lump->dir.name, sizeof(lump->dir.name)) != sizeof(lump->dir.name))
   ProgError("Failed writing wad catalog entry %u", wad.num_entries);

 if (lump->level != NULL)
  {
   /* Write all catalog entries within this level,
      freeing the memory as we do so. */
   struct lumplist *l, *next;
   for (l = lump->level; l != NULL; l = next)
   {
     next = l->next;
     write_catalog(l);
   }
  }

  /* Free lump descriptor */
  free(lump);
}

void usage(void) __attribute__((noreturn));

void usage(void)
{
 printf("\nBSP v" VERSION "\n"
        "\nSee the file AUTHORS for a complete list of credits and contributors\n"
        "\nUsage: bsp [options] input" FILE_EXT " [[-o] <output" FILE_EXT ">]\n"
        "       (If no output" FILE_EXT " is specified, " DEFAULT_NAME " is written)\n\n"
        "Options:\n\n"
        "  -factor <nnn>  Changes the cost assigned to SEG splits\n"
        "  -picknode {traditional|visplane}\n"
	"                 Selects either the traditional nodeline choosing algorithm\n"
	"                 (balance the tree and minimise splits) or Lee's algorithm\n"
	"                 to minimise visplanes (try to balance distinct sector refs)\n"
        "  -blockmap {old|comp}\n"
        "                 Selects either the old straightforward blockmap\n"
        "                 generation, or the new compressed blockmap code\n"
        "  -noreject      Does not clobber reject map\n"
	"  -q             Quiet mode (only errors are printed)\n"
       );
 exit(EXIT_FAILURE);
}

static int quiet;

struct multi_option {
	const char *tag;
	const char *text;
	void       *value;
};

const struct multi_option picknode_options[] = {
{"traditional", "Optimising for SEG splits and balance",(void *)PickNode_traditional},
{"visplane", "Optimising for fewest visplanes", (void *)PickNode_visplane},
{NULL,NULL,NULL},
};

data_callback *CreateBlockmap = CreateBlockmap_old;
const struct multi_option blockmap_options[] = {
{"old", "BSP v3.0 blockmap algorithm",(void *)CreateBlockmap_old},
{"comp", "Compressed blockmap", (void *)CreateBlockmap_compressed},
{NULL,NULL,NULL},
};

static void parse_options(int argc, char *argv[])
{
 static char *fnames[2];
 static const struct {
   const char *option;
   void *var;
   enum {NONE, STRING, INT, MULTI} arg;
   const struct multi_option* opts;
 } tab[]= { {"-picknode", &PickNode, MULTI, picknode_options},
            {"-blockmap", &CreateBlockmap, MULTI, blockmap_options},
            {"-noreject", &noreject, NONE, NULL},
            {"-q", &quiet, NONE, NULL},
            {"-factor", &factor, INT, NULL},
            {"-o", fnames+1, STRING, NULL},
          };
 int nf=0;

 while (--argc)
   if (**++argv=='-')
    {
     int i=NELEMS(tab);
     for (;;)
       if (!strcmp(*argv,tab[--i].option))
        {
         if (tab[i].arg != NONE && !--argc) usage();
         switch (tab[i].arg) {
	 case MULTI:
	   {
		const struct multi_option* p = tab[i].opts;
		const char* opt = *++argv;

		while (p->tag) {
			if (!strcmp(p->tag,opt)) {
				*(void**)(tab[i].var) = p->value;
				Verbose("%s: %s\n",tab[i].option, p->text);
				break;
			}
			p++;
		}
	   }
	   break;
         case INT:
            {
             char *end;
             *(int *) tab[i].var=strtol(*++argv,&end,0);
             if (*end || factor<0)
               usage();
            }
           break;
         case STRING:
	   *(char **) tab[i].var = *++argv;
           break;
	 case NONE:
	     ++*(int *) tab[i].var; break;
         }
         break;
        }
       else
         if (!i)
          {
           usage();
           break;
          }
    }
   else
     if (nf<2)
       fnames[nf++]=*argv;
     else
       usage();

 testwad = fnames[0];                          /* Get input name*/

 if (!testwad || factor<0)
   usage();

 outwad = fnames[1] ? fnames[1] : DEFAULT_NAME;   /* Get output name*/
}

#ifdef FORTIFY
static void fortify_show_leaks(void)
{
 Fortify_LeaveScope();
}
#endif /* FORTIFY */

/*- Main Program -----------------------------------------------------------*/

int main(int argc,char *argv[])
{
 int using_temporary_output = 0;
 long pos;
 struct lumplist *wad_catalog, *lump, *next;

#ifdef FORTIFY
 Fortify_EnterScope();
 atexit(fortify_show_leaks);
#endif /* FORTIFY */

 parse_options(argc,argv);

 verbosity = quiet ? 0 :
#ifdef HAVE_ISATTY
	isatty(STDOUT_FILENO) ? 2 : 1
#else
	2
#endif
	;

 /* Don't buffer output to stdout, people want to see the progress
  * as it happens */
#ifdef HAVE_ISATTY
 if (isatty(STDOUT_FILENO))
#endif
   setbuf(stdout,NULL);

 if (verbosity)
  Verbose("* Doom BSP node builder ver " VERSION "\n"
	"Copyright (c)	1998 Colin Reed, Lee Killough\n"
	"		2001 Simon Howard\n"
	"		2000,2001,2002,2006 Colin Phipps <cph@moria.org.uk>\n"
	"		2010 Christopher Bazley <cs99cjb@gmail.com>\n\n");

 wad_catalog = OpenWadFile(testwad);	/* Opens and reads directory*/

 Verbose("Creating nodes using tunable factor of %d\n",factor);

 if (visplane)
  {
   Verbose("\nTaking special measures to reduce the chances of visplane overflow");
   PickNode=PickNode_visplane;
  }

 outfile = fopen(outwad, "wb");
 if (!outfile) {
#ifdef HAVE_TMPFILE
   outfile = tmpfile();
   using_temporary_output = 1;
#endif
 } else {
   unlinkwad = outwad;
 }
 if (!outfile) {
   perror(outwad);
   ProgError("Could not open output PWAD file");
 }

 if (fwrite("xxxxxxxxxxxx",sizeof wad,1,outfile) != 1)
   ProgError("Failure writing to wad file");

 /* Write every lump in the wad file catalog
    and update directory entries */
 current_level = NULL;
 for (lump = wad_catalog; lump != NULL; lump = lump->next)
   write_lump(lump);

 pos = ftell(outfile);
 if (pos == -1)
    ProgError("Failure locating end of lump data");

 wad.dir_start = (uint32_t)pos;
 wad.num_entries = 0;

 /* Write WAD file catalog and destroy lump tree*/
 for (lump = wad_catalog; lump != NULL; lump = next)
 {
   next = lump->next;
   write_catalog(lump);
 }

 /* Write WAD file header */
 if (fseek(outfile, 0, SEEK_SET) ||
     write_chars(wad.type, sizeof(wad.type)) != sizeof(wad.type) ||
     write_uint32(&wad.num_entries) ||
     write_uint32(&wad.dir_start))
    ProgError("Failure writing wad header");

 if (using_temporary_output) {
   FILE* realout = fopen(outwad,"wb");
   if (!realout) {
     perror(outwad);
     ProgError("Could not open output PWAD file");
   }
   unlinkwad = outwad;
   rewind(outfile);
   fcopy(outfile,realout);
   fclose(realout);
 }
 fclose(outfile);

 Verbose("\nSaved WAD as %s\n",outwad);

#ifdef RISCOS
 { /* Set output file type */
   _kernel_osfile_block parameters;
   parameters.load = WAD_FILE_TYPE;
   _kernel_osfile(OSFILE_SET_TYPE, outwad, &parameters);
 }
#endif /* RISCOS */

 return 0;
}

/*- end of file ------------------------------------------------------------*/
