qfind - a spaceship search program

For scripts to aid with computation or simulation in cellular automata.
Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

qfind - a spaceship search program

Post by Sokwe » June 19th, 2017, 8:36 am

This is a topic for the discussion of qfind, a multithreaded spaceship search program written by Matthias Merzenich (that's me).

The latest version of the program can be found here.

As an example, running qfind with the arguments

Code: Select all

-r B3/S23 -p 10 -y 1 -w 5 -s even -q 18 -t 2
will search for an orthogonal ship in B3/S23 with a period of 10, a translation of 1 cell per period, and a logical width of 5 (full width 10) using 2 threads during each deepening step and a queue size of 2^18 nodes.

Please report any bugs that you find.

This post has been edited. The original text of this post is below:

-----

For the past few weeks I have been working on a new program that is in some sense a combination of gfind and zfind. It has the same limitations as zfind: it only searches for orthogonal spaceships of search-width less than 11. The output looks similar to gfind.

The program uses OpenMP in the most naive way. The main search is breadth-first and is not parallel. After the BFS queue fills up each element in the queue is run through a depth-first search to find an extension. If an extension of the specified length is found, then the element is kept; otherwise it is discarded. The depth-first testing of elements is done in parallel with a simple omp parallel for.

This naive approach seems sub-optimal. Usually there is one element in the queue that takes much longer to check than all of the others. Eventually, this becomes the only thread still running while all of the other threads are idle. I'll have to do a number of tests to see if I can make it more efficient, but that may take a while. For now I will post what I have.

Edit: this code is old. Please use the current version, which is linked at the top of this post.

Code: Select all

/*
** By Matthias Merzenich, David Eppstein, Paul Tooke, and "zdr"
** This is a first attempt at combining gfind and zfind.
** The code is currently a mess, but I hope to improve it over time.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <omp.h>

#define BANNER "By Matthias Merzenich, 18 June 2017"
#define FILEVERSION ((unsigned long) 2017061801)  //yyyymmddnn

#define QBITS 23

#define HASHBITS 21
#define DEFAULT_DEPTHLIMIT (qBits-3)
#define SEARCHLIMIT 50

#define P_RULE 0
#define P_WIDTH 1
#define P_PERIOD 2
#define P_OFFSET 3
#define P_SYMMETRY 4
#define P_NUM_SHIPS 5
#define P_REORDER 6
#define P_CHECKPOINT 7
#define P_BASEBITS 8
#define P_QBITS 9
#define P_HASHBITS 10
#define P_DEPTHLIMIT 11
#define P_NUMTHREADS 12

#define NUM_PARAMS 13

#define SYM_ASYM 1
#define SYM_ODD 2
#define SYM_EVEN 3
#define SYM_GUTTER 4

int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};

int params[NUM_PARAMS];
int width;
int deepeningAmount;
int lastdeep;
int nRowsInState;
int phase;

int period;
#define MAXPERIOD 30

int fwdOff[MAXPERIOD], backOff[MAXPERIOD], doubleOff[MAXPERIOD], tripleOff[MAXPERIOD];

int offset;
unsigned long rule;

int aborting;
int nFound;

enum mode {
   asymmetric,          /* basic orthogonal or diagonal pattern */
   odd, even,           /* orthogonal with bilateral symmetry */
   gutter,              /* orthogonal bilateral symmetry with empty column in middle */
} mode;

/* the big data structures */
#define qBits params[P_QBITS]
#define QSIZE (1<<qBits)

#define hashBits params[P_HASHBITS]
#define HASHSIZE (1<<hashBits)
#define HASHMASK (HASHSIZE - 1)

typedef uint32_t node;
typedef uint16_t row;

row * rows;
node * base;
node * hash;

/*
** Representation of vertices.
**
** Each vertex is represented by an entry in the rows[] array.
** That entry consists of the bits of the last row of the vertex's pattern
** concatenated with a number, the "offset" of the vertex.
** The parent of vertex i is formed by adding the offset of i
** with the number in base[i/BASEFACTOR].
**
** If node i has offset -1, the entry is considered to be empty and is skipped.
** This is to deal with the case that base[i/BASEFACTOR] is already set to
** something too far away to deal with via the offset.
**
** qIsEmpty() checks the size of the queue
** enqueue(n,r) adds a new node with last row r and parent n
** dequeue() returns the index of the next unprocessed node
** pop() undoes the previous enqueue operation
** resetQ() clears the queue
**
** ROW(b) returns the last row of b
** PARENT(b) returns the index of the parent of b
*/

#define MAXWIDTH (10)

#define ROWBITS ((1<<width)-1)
#define BASEBITS (params[P_BASEBITS])
#define BASEFACTOR (1<<BASEBITS)
#define MAXOFFSET ((((row) -1) >> width) - 1)

#define ROW(i) (rows[i] & ROWBITS)
#define OFFSET(i) (rows[i] >> width)
#define EMPTY(i) (rows[i] == (row)-1)
#define MAKEEMPTY(i) rows[i] = (row)-1
#define PARENT(i) (base[(i)>>BASEBITS]+OFFSET(i))
#define FIRSTBASE(i) (((i) & ((1<<BASEBITS) - 1)) == 0)

void printRow(row theRow){
   int i;
   for(i = 0; i < width; i++) printf("%c",(theRow & 1 << i ? '*' : '.'));
   printf("\n");
}

/* =========================================== */
/*  Lookup Tables to determine successor rows  */
/* =========================================== */

uint32_t *gInd;
uint32_t *gcount;
uint16_t *gRows;

//uint32_t *pInd, *pRemain;
//uint16_t *pRows;

unsigned char *causesBirth;


int evolveBit(int row1, int row2, int row3, int bshift){
   int r;
   r = bc[(row1 >> bshift) & 7];
   r += bc[(row2 >> bshift) & 7] + 4 * ((row2 >> bshift) & 2);
   r += bc[(row3 >> bshift) & 7];
   return (rule >> r) & 1;
}

int evolveRow(int row1, int row2, int row3){
   int row4;
   int row1_s,row2_s,row3_s;
   int j,s = 0;
   if(params[P_SYMMETRY] == SYM_ODD) s = 1;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(params[P_SYMMETRY] == SYM_ASYM && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   if(params[P_SYMMETRY] == SYM_ODD || params[P_SYMMETRY] == SYM_EVEN){
      row1_s = (row1 << 1) + ((row1 >> s) & 1);
      row2_s = (row2 << 1) + ((row2 >> s) & 1);
      row3_s = (row3 << 1) + ((row3 >> s) & 1);
   }
   else{
      row1_s = (row1 << 1);
      row2_s = (row2 << 1);
      row3_s = (row3 << 1);
   }
   row4 = evolveBit(row1_s, row2_s, row3_s, 0);
   for(j = 1; j < width; j++)row4 += evolveBit(row1, row2, row3, j - 1) << j;
   return row4;
}

void sortRows(uint32_t rowSet){
   uint32_t totalRows = gInd[rowSet + 1] - gInd[rowSet];
   uint16_t *theRow = &(gRows[gInd[rowSet]]);
   uint32_t i;
   int64_t j;
   uint16_t t;
   for(i = 1; i < totalRows; ++i){
      t = theRow[i];
      j = i - 1;
      while(j >= 0 && gcount[theRow[j]] < gcount[t]){
         theRow[j+1] = theRow[j];
         --j;
      }
      theRow[j+1] = t;
   }
}

void makeTables(){
   printf("\nBuilding lookup tables... ");

   causesBirth = malloc((long long)sizeof(*causesBirth) << width);

   gInd = malloc(((long long)sizeof(*gInd) << (width * 3)) + sizeof(*gInd));
   gcount = malloc((long long)sizeof(*gcount) * (1 << width));
   uint32_t i;
   int row1,row2,row3,row4;
   long int rows123,rows124;
   uint32_t numValid = 0;

   for(row1 = 0; row1 < 1 << width; row1++) causesBirth[row1] = (evolveRow(row1,0,0) ? 1 : 0);

   for(i = 0; i < 1 << width; ++i) gcount[i] = 0;
   for(i = 0; i < ((1 << (3 * width)) + 1); i++)gInd[i] = 0;
   rows123 = -1;     //represents row1, row2, and row3 stacked vertically
   for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
      rows123++;
      row4 = evolveRow(row1,row2,row3);
      if(row4 < 0) continue;
      ++gcount[row4];
      gInd[rows123 - row3 + row4]++;
      numValid++;
   }
   gRows = malloc(2 * numValid);
   for(rows124 = 1; rows124 < 1 << (3 * width); rows124++) gInd[rows124] += gInd[rows124 - 1];
   gInd[1 << (3 * width)] = gInd[(1 << (3 * width)) - 1];  //extra needed for last set to calculate number
   rows123 = -1;
   for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
      rows123++;
      row4 = evolveRow(row1,row2,row3);
      if(row4 < 0) continue;
      rows124 = rows123 - row3 + row4;
      gInd[rows124]--;
      gRows[gInd[rows124]] = (uint16_t)row3;
   }
   printf("Lookup tables built.\n");

   gcount[0] = UINT32_MAX;
   if(params[P_REORDER]){
      printf("Sorting lookup table..... ");
      for(rows124 = 0; rows124 < 1 << (3 * width); ++rows124){
         sortRows(rows124);
      }
      printf("Lookup table sorted.\n");
   }
   free(gcount);
}

void makePhases(){
   int i;
   for (i = 0; i < period; i++) backOff[i] = -1;
   i = 0;
   for (;;) {
      int j = offset;
      while (backOff[(i+j)%period] >= 0 && j < period) j++;
      if (j == period) {
         backOff[i] = period-i;
         break;
      }
      backOff[i] = j;
      i = (i+j)%period;
   }
   for (i = 0; i < period; i++)
      fwdOff[(i+backOff[i])%period] = backOff[i];
   for (i = 0; i < period; i++) {
      int j = (i - fwdOff[i]);
      if (j < 0) j += period;
      doubleOff[i] = fwdOff[i] + fwdOff[j];
   }
   for (i = 0; i <  period; i++){
      int j = (i - fwdOff[i]);
      if (j < 0) j += period;
      tripleOff[i] = fwdOff[i] + doubleOff[j];
   }
}

/* ====================================================== */
/*  Hash table for detecting equivalent partial patterns  */
/* ====================================================== */

void resetHash() { if (hash != 0) memset(hash,0,4*HASHSIZE); }

int hashPhase = 0;

static inline long hashFunction(node b, row r) {
   long h = r;
   int i;
   for (i = 0; i < nRowsInState; i++) {
      h = (h * 269) + ROW(b);
      b = PARENT(b);
   }
   h += (h>>16)*269;
   h += (h>>8)*269;
   return h & HASHMASK;
}

/* test if q+r is same as p */
static inline int same(node p, node q, row r) {
   int i;
   for (i = 0; i < nRowsInState; i++) {
      if (p >= QSIZE || q >= QSIZE || EMPTY(p) || EMPTY(q)) return 0;   /* sanity check */
      if (ROW(p) != r) return 0;
      p = PARENT(p);
      r = ROW(q);
      q = PARENT(q);
   }
   return 1;
}

/* test if we've seen this child before */
//void success(node);
static inline int isVisited(node b, row r) {
   if (same(0,b,r)) return 1;
   if (hash != 0) {
      int hashVal = hashFunction(b,r);
      node hashNode = hash[hashVal];
      if (hashNode == 0) return 0;
      if (same(hashNode,b,r)){
         return 1;
      }
   }
   return 0;
}

/* set node (NOT child) to be visited */
static inline void setVisited(node b) {
   if (hash != 0) hash[ hashFunction(PARENT(b),ROW(b)) ] = b;
}



/* ============================================== */
/*  Output patterns found by successful searches  */
/* ============================================== */

#define MAXRLELINEWIDTH 63
int RLEcount = 0;
int RLElineWidth = 0;
char RLEchar;

void sendRLE(char c) {
  if (RLEcount > 0 && c != RLEchar) {
      if (RLElineWidth++ >= MAXRLELINEWIDTH) {
         if (RLEchar != '\n') putchar('\n');
         RLElineWidth = 0;
      }
    if (RLEcount == 1) putchar(RLEchar);
    else {
       printf("%d%c", RLEcount, RLEchar);
       RLElineWidth ++;
       if (RLEcount > 9) RLElineWidth++;
    }
    RLEcount = 0;
    if (RLEchar == '\n') RLElineWidth = 0;
  }
  if (c != '\0') {
    RLEcount++;
    RLEchar = c;
  } else RLElineWidth = 0;
}

int outputParity = 0;

void putRow(unsigned long rr, unsigned long r, int shift) {
   while (r | rr) {
      if (shift == 0)
         sendRLE(r & 1 ? 'o' : 'b');
      else shift--;
      r >>= 1;
      if (rr & 1) r |= (1<<31);
      rr >>= 1;
   }
   sendRLE('$');
}

/*void printRule() {
  int i;
  printf("B");
  for (i = 0; i < 9; i++) if (rule & (1 << (9+i))) putchar(i+'0');
  printf("/S");
  for (i = 0; i < 9; i++) if (rule & (1 << i)) putchar(i+'0');
}*/

void printRule() {
   int i;
   printf("B");
   for(i = 0; i < 9; i++) if(rule & (1 << i)) putchar(i+'0');
   printf("/S");
   for(i = 0; i < 9; i++) if(rule & (1 << (i+9))) putchar(i+'0');
}

/*void printRule() {
   int i;
   printf("B");
   for(i = 0; i < 9; i++){
      if(rule & (1 << i)) printf("%d",i);
   }
   printf("/S");
   for(i = 9; i < 18; i++){
      if(rule & (1 << i)) printf("%d",i - 9);
   }
}*/


int modeWidth() {
   switch(mode) {
      case asymmetric:
         return width;
      case odd:
         return 2*width-1;
      case even:
         return 2*width;
      case gutter:
         return 2*width+1;
   }
   return 0;
}

/* PATCH - Keep static array for output to prevent memory leak */
//int sxsAllocRows =  0;
//unsigned long *  sxsAllocData;
//unsigned long *  sxsAllocData2;

/* PATCH - Avoid Intel shift bug */
static inline unsigned long
safeShift(unsigned long r, int i)
{
    unsigned long rr = r;
    while (i>16) { rr >>= 16; i-=16;}
    return (rr>>i);
}


void success(node b, row *pRows, int nodeRow, uint32_t lastRow){
   node c;
   int nrows = 0;
   int skewAmount = 0;
   int swidth;
   int p, i, j, margin;
   //row *srows, *ssrows, *drows, *ddrows;
   unsigned long *srows, *ssrows, *drows, *ddrows;
   static unsigned long *oldsrows = 0, *oldssrows = 0;
   static unsigned long *olddrows = 0, *oldddrows = 0;
   static int oldnrows = 0;

   uint32_t currRow = lastRow;
   int nDeepRows = 0;
   int nodeDiff;

   /* check if output disabled while deepening */
   /*if (perdidor) {
      perdidor = 2;
      return;
   }*/

   if(pRows != NULL){
      while(pRows[currRow] == 0){
         if(currRow == 0){
            printf("Success called on search root!\n");
            aborting = 1;
            return;
         }
         currRow--;
      }
      nDeepRows = (currRow / period) - 1;
      nodeDiff = nodeRow - period - (currRow%period);
      nodeRow -= nodeDiff;

      for(j = 0; j < nodeDiff; j++){
         b = PARENT(b);
      }
      currRow = currRow - period + 1;
      nrows = nDeepRows;
      
   }
   else{
      /* shift until we find nonzero row.
         then shift PERIOD-1 more times to get leading edge of glider */
      while (ROW(b) == 0) {
         b = PARENT(b);
         if (b == 0) {
            printf("Success called on search root!\n");
            aborting = 1;
            return;
         }
      }
   }
   if(nrows < 0) nrows = 0;
   
   for (p = 0; p < period-1; p++) b = PARENT(b);
   if (b == 0) {
      printf("Success called on search root!\n");
      aborting = 1;
      return;
   }
   
   /* count rows */
   c = b;
   while (c != 0) {
      for (p = 0; p < period; p++)
         c = PARENT(c);
      nrows++;
   }
   
   /* build data structure of rows so we can reduce width etc */
   srows = malloc((nrows+MAXWIDTH+1) * sizeof(unsigned long));
   ssrows = malloc((nrows+MAXWIDTH+1) * sizeof(unsigned long));
   drows = srows; ddrows = ssrows; /* save orig ptr for free() */
   for (i = 0; i <= nrows+MAXWIDTH; i++) srows[i]=ssrows[i]=0;
   for (i = nrows - 1; i >= 0; i--) {
      row r;
      if(nDeepRows > 0){
         r = pRows[currRow];
         currRow -= period;
         nDeepRows--;
      }
      else{
         r = ROW(b);
         for (p = 0; p < period; p++) {
            b = PARENT(b);
         }
      }
      //row rx;
      switch(mode) {
         case asymmetric:
            srows[i] = r;
            break;

         case odd:
            srows[i] = r << (MAXWIDTH - 1);
            ssrows[i] = r >> (32 - (MAXWIDTH - 1));
            for (j = 1; j < MAXWIDTH; j++)
               if (r & (1<<j))
                  srows[i] |= 1 << (MAXWIDTH - 1 - j);
            break;

         case even:
            srows[i] = r << MAXWIDTH;
            ssrows[i] = r >> (32 - MAXWIDTH);
            for (j = 0; j < MAXWIDTH; j++)
               if (r & (1<<j))
                  srows[i] |= 1 << (MAXWIDTH - 1 - j);
            break;

         case gutter:
            srows[i] = r << MAXWIDTH + 1;
            ssrows[i] = r >> (32 - (MAXWIDTH + 1));
            for (j = 0; j < MAXWIDTH; j++)
               if (r & (1<<j))
                  srows[i+skewAmount] |= 1 << (MAXWIDTH - 1 - j);
            break;

         default:
            printf("Unexpected mode in success!\n");
            aborting = 1;
            return;
      }
   }
   
   /* normalize nrows to only include blank rows */
   nrows += MAXWIDTH;
   while (srows[nrows-1] == 0 && ssrows[nrows-1] == 0 && nrows>0) nrows--;
   while (srows[0] == 0 && ssrows[0] == 0 && nrows>0) {
      srows++;
      ssrows++;
      nrows--;
   }
   
   /* sanity check: are all rows empty? */
   int allEmpty = 1;
   for(i = 0; i < nrows; i++){
      if(srows[i]){
         allEmpty = 0;
         break;
      }
   }
   if(allEmpty) return;
   
   /* make at least one row have nonzero first bit */
   i = 0;
   while ((srows[i] & 1) == 0) {
      for (i = 0; (srows[i] & 1) == 0 && i < nrows; i++) { }
      if (i == nrows) {
         for (i = 0; i < nrows; i++) {
            srows[i] >>= 1;
            if (ssrows[i] & 1) srows[i] |= (1<<31);
            ssrows[i] >>= 1;
         }
         i = 0;
      }
   }
   
   swidth = 0;
   for (i = 0; i < nrows; i++)
      while (safeShift(ssrows[i],swidth))
         swidth++;
   if (swidth) swidth += 32;
   for (i = 0; i < nrows; i++)
      while (safeShift(srows[i],swidth))
         swidth++;
   
      
   /* compute margin on other side of width */
   margin = 0;

   /* make sure we didn't just output the exact same pattern (happens a lot for puffer) */
   if (nrows == oldnrows) {
      int different = 0;
      for (i = 0; i < nrows && !different; i++)
         different = (srows[i] != oldsrows[i] || ssrows[i] != oldssrows[i]);
      if (!different) {
         free(drows);
         free(ddrows);
         return;
      }
   }
   if (olddrows != 0) free(olddrows);
   if (oldddrows != 0) free(oldddrows);
   oldsrows = srows;
   oldssrows = ssrows;
   olddrows = drows;
   oldddrows = ddrows;
   oldnrows = nrows;

   /* output it all */
   printf("\nx = %d, y = %d, rule = ", swidth - margin, nrows);
   printRule();
   putchar('\n');

   while (nrows-- > 0) {
      if (margin > nrows) putRow(ssrows[nrows], srows[nrows], margin - nrows);
      else putRow(ssrows[nrows], srows[nrows], 0);
   }
   RLEchar = '!';
   sendRLE('\0');
   printf("\n\n");
   fflush(stdout);
   //if (++nFound >= findLimit) aborting = 1;
}


/* Is this a node at which we can stop? */
int terminal(node n){
   int p;

   for (p = 0; p < period; p++) {   /* last row in each phase must be zero */
      if (ROW(n) != 0) return 0;
      n = PARENT(n);
   }

   for (p = 0; p < period; p++) {
      if(causesBirth[ROW(n)]) return 0;
      n = PARENT(n);
   }
   return 1;
}




/* ================================================ */
/*  Queue of partial patterns still to be examined  */
/* ================================================ */

/* SU patch */
node qHead,qTail;

/* PATCH queue dimensions required during save/restore */
node qStart; /* index of first node in queue */
node qEnd;   /* index of first unused node after end of queue */

/* Maintain phase of queue nodes. After dequeue(), the global variable phase
   gives the phase of the dequeued item.  If the queue is compacted, this information
   needs to be reinitialized by a call to rephase(), after which phase will not be
   valid until the next call to dequeue().  Variable nextRephase points to the next
   node for which dequeue will need to increment the phase. Phase is not maintained
   when treating queue as a stack (using pop()) -- caller must do it in that case.
   It's ok to change phase since we maintain a separate copy in queuePhase. */

int queuePhase = 0;
node nextRephase = 0;
void rephase() {
   node x, y;
   while (qHead < qTail && EMPTY(qHead)) qHead++;   /* skip past empty queue cells */
   x = qHead;   /* find next item in queue */
   queuePhase = period - 1;
   while (x != 0) {
      x = PARENT(x);
      queuePhase++;
   }
   queuePhase %= period;

   /* now walk forward through queue finding breakpoints between each generation
      invariants: y is always the first in its generation */
   x = 0; y = 0;
   while (y <= qHead) {
      ++x;
      if (x >= qTail || !EMPTY(x) && PARENT(x) >= y) y = x;
   }
   nextRephase = y;
}

/* phase of an item on the queue */
int peekPhase(node i) {
   return (i < nextRephase? queuePhase : (queuePhase+1)%period);
}

/* Test queue status */
static inline int qIsEmpty() {
   while (qHead < qTail && EMPTY(qHead)) qHead++;
   return (qTail == qHead);
}

void qFull() {
    if (aborting != 2) {
      printf("Exceeded %d node limit, search aborted\n", QSIZE);
      fflush(stdout);
      aborting = 2;
   }
}

static inline void enqueue(node b, row r) {
   node i = qTail++;
   if (i >= QSIZE) qFull();
   else if (FIRSTBASE(i)) {
      base[i>>BASEBITS] = b;
      rows[i] = r;
   } else {
      long o = b - base[i>>BASEBITS];
      if (o < 0 || o >(long) MAXOFFSET) {   /* offset out of range */
         while (!FIRSTBASE(i)) {
            rows[i] = -1;
            i = qTail++;
            if (i >= QSIZE) qFull();
         }
         base[i>>BASEBITS] = b;
         rows[i] = r;
      } else rows[i] = (o << width) + r;
   }
}

static inline node dequeue() {
   while (qHead < qTail && EMPTY(qHead)) qHead++;
   if (qHead >= nextRephase) {
      queuePhase = (queuePhase+1)%period;
      nextRephase = qTail;
   }
   phase = queuePhase;
   return qHead++;
}

static inline void pop() {
   qTail--;
   while (qTail > qHead && EMPTY(qTail-1)) qTail--;
}

void resetQ() { qHead = qTail = 0; }

static inline int qTop() { return qTail - 1; }


/* ================================= */
/* PATCH08 - dump state              */
/* ================================= */

int dumpNum = 1;
char dumpFile[12];
#define DUMPROOT "dump"
int dumpFlag = 0; /* Dump status flags, possible values follow */
#define DUMPPENDING (1)
#define DUMPFAILURE (2)
#define DUMPSUCCESS (3)

int dumpandexit = 0;

FILE * openDumpFile()
{
    FILE * fp;

    while (dumpNum < 10000)
    {
        sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
        if (fp=fopen(dumpFile,"r"))
            fclose(fp);
        else
            return fopen(dumpFile,"w");
    }
    return (FILE *) 0;
}

void dumpState()
{
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%lu\n",FILEVERSION);
    for (i = 0; i < NUM_PARAMS; i++)
        fprintf(fp,"%d\n",params[i]);
    fprintf(fp,"%d\n",width);
    //fprintf(fp,"%d\n",widthReduction);
    fprintf(fp,"%d\n",period);
    fprintf(fp,"%d\n",offset);
    fprintf(fp,"%d\n",mode);
    //fprintf(fp,"%d\n",diagonal);
    //fprintf(fp,"%d\n",nFound);
    fprintf(fp,"%d\n",lastdeep);

    fprintf(fp,"%u\n",qHead-qStart);
    fprintf(fp,"%u\n",qEnd-qStart);
    for (i = qStart; i < qEnd; i++)
        fprintf(fp,"%u\n",rows[i]);
    fclose(fp);
    dumpFlag = DUMPSUCCESS;
}





/* ================================= */
/*  Compaction of nearly full queue  */
/* ================================= */

void putnum(long n) {
   char suffix;
   if (n >= 1000000) {
      n /= 100000;
      suffix = 'M';
   } else if (n >= 1000) {
      n /= 100;
      suffix = 'k';
   } else {
      printf("%ld", n);
      return;
   }

   if (n >= 100) printf("%ld", n/10);
   else printf("%ld.%ld", n/10, n%10);
   putchar(suffix);
}

long currentDepth() {
   long i;
   node x;
   x = qTail - 1;
   i = 1;
   while (x != 0) {
      x = PARENT(x);
      i++;
   }
   return i;
}



/*
   doCompact() now has two parts.  The first part compresses
   the queue.  The second part consists of the last loop which
   converts parent bits to back parent pointers. The search
   state may be saved in between.  The queue dimensions, which
   were previously saved in local variables are saved in globals.
*/

void doCompactPart1()
{
   node x,y;
   qEnd = qTail;
   
   /* make a pass backwards from the end finding unused nodes at or before qHead */
   x = qTail - 1;
   y = qHead - 1;
   while (y > 0) {
      /* invariants: everything after y is still active.
                     everything after x points to something after y.
                     x is nonempty and points to y or something before y.
                     so, if x doesnt point to y, y must be unused and can be removed. */
      if (!EMPTY(y)) {
         if (y > PARENT(x)) rows[y] = -1;
         else while (EMPTY(x) || PARENT(x) == y) x--;
      }
      y--;
   }
   
   /* make a pass forwards converting parent pointers to offset from prev parent ptr.
      note that after unused nodes are eliminated, all these offsets are zero or one. */
   y = 0;
   for (x = 0; x < qTail; x++) if (!EMPTY(x)) {
      if (PARENT(x) == y) rows[x] = ROW(x);
      else {
         y = PARENT(x);
         rows[x] = (1<<width) + ROW(x);
      }
   }
   
   /*
      Make a pass backwards compacting gaps.
   
      For most times we run this, it could be combined with the next phase, but
      every once in a while the process of repacking the remaining items causes them
      to use *MORE* space than they did before they were repacked (because of the need
      to leave empty space when OFFSET gets too big) and without this phase the repacked
      stuff overlaps the not-yet-repacked stuff causing major badness.
      
      For this phase, y points to the current item to be repacked, and x points
      to the next free place to pack an item.
    */
   x = y = qTail-1;
   for (;;) {
      if (qHead == y) qHead = x;
      if (!EMPTY(y)) {
         rows[x] = rows[y];
         x--;
      }
      if (y-- == 0) break;   /* circumlocution for while (y >= 0) because x is unsigned */
   }
    qStart = ++x;    /* mark start of queue */
}

void doCompactPart2()
{
    node x,y;

   /*
      Make a pass forwards converting parent bits back to parent pointers.
      
      For this phase, x points to the current item to be repacked, and y points
      to the parent of the previously repacked item.
      After the previous pass, x is initialized to first nonempty item,
      and all items after x are nonempty. 
    */
   qTail = 0; y = 0;
   resetHash();
   for (x = qStart; x < qEnd; x++) {
      if (OFFSET(x)) {   /* skip forward to next parent */
         y++;
         while (EMPTY(y)) y++;
      }
      enqueue(y,ROW(x));
      if (aborting) return;
      if (qHead == x) qHead = qTail - 1;
      setVisited(qTail - 1);
   }
   rephase();
}

void doCompact()
{
   /* make sure we still have something left in the queue */
   if (qIsEmpty()) {
      qTail = qHead = 0;   /* nothing left, make an extremely compact queue */
      return;
   }
    /* First loop of part 1 requires qTail-1 to be non-empty. Make it so */
    while(EMPTY(qTail-1))
        qTail--;

    doCompactPart1();
    if (dumpFlag == DUMPPENDING) dumpState();
    doCompactPart2();
}



/* =================================== */
/* PATCH08 - preview partial results   */
/* =================================== */

static void preview(int allPhases)
{
    node i,j,k;
    int ph;

    for (i = qHead; (i<qTail) && EMPTY(i); i++);
    for (j = qTail-1; (j>i) && EMPTY(j); j--);
    if (j<i) return;
/*
    for (ph = 0; ph < period; ph++)
    {
        i=PARENT(i);
        j=PARENT(j);
    }
*/
    while (j>=i && !aborting)
    {
        if (!EMPTY(j))
        {
            success(j, NULL, 0, 0);
            //success(j);
            if (allPhases == 0)
            {
                k=j;
                for (ph = 1; ph < period; ph++)
                {
                    k=PARENT(k);
                    success(k, NULL, 0, 0);
                    //success(k);
                }
            }
        }
        j--;
    }
}


/* ================================= */
/* PATCH08 - resume from saved state */
/* ================================= */

char * loadFile;

void loadFail()
{
    printf("Load from file %s failed\n",loadFile);
    exit(1);
}

signed int loadInt(FILE *fp)
{
    signed int v;
    if (fscanf(fp,"%d\n",&v) != 1) loadFail();
    return v;
}

unsigned int loadUInt(FILE *fp)
{
    unsigned int v;
    if (fscanf(fp,"%u\n",&v) != 1) loadFail();
    return v;
}

void loadState(char * cmd, char * file)
{
    FILE * fp;
    int i;

    loadFile = file;
    fp = fopen(loadFile, "r");
    if (!fp) loadFail();
    if (loadUInt(fp) != FILEVERSION)
    {
        printf("Incompatible file version\n");
        exit(1);
    }

    /* Load parameters and set stuff that can be derived from them */
    for (i = 0; i < NUM_PARAMS; i++)
        params[i] = loadInt(fp);
   // rule = (params[P_BIRTHS] << 9) + params[P_SURVIVES];
   rule = params[P_RULE];

    /* Load / initialise globals */
    width          = loadInt(fp);
    //widthReduction = loadInt(fp);
    period         = loadInt(fp);
    offset         = loadInt(fp);
    mode           = loadInt(fp);
    //diagonal       = loadInt(fp);
    //nFound         = loadInt(fp);
    lastdeep       = loadInt(fp);
   deepeningAmount = period; /* Currently redundant, since it's recalculated */
   //perdidor        = 0;
   aborting        = 0;
   nRowsInState = period+period;   /* how many rows needed to compute successor graph? */

    /* Allocate space for the data structures */
   base = malloc((QSIZE>>BASEBITS)*sizeof(node));
   rows = malloc(QSIZE*sizeof(row));
   if (base == 0 || rows == 0) {
      printf("Unable to allocate BFS queue!\n");
      exit(0);
   }
   
   if (hashBits == 0) hash = 0;
   else {
      hash = malloc(HASHSIZE*sizeof(node));
      if (hash == 0) printf("Unable to allocate hash table, duplicate elimination disabled\n");
   }

    /* Various bits that need doing before we load the BFS queue */
   // makeReversals();
   //makeUnterm();
   // set4x();
   
    /* Load up BFS queue and complete compaction */
    qHead  = loadUInt(fp);
    qEnd   = loadUInt(fp);
    qStart = QSIZE - qEnd;
    qEnd   = QSIZE;
    qHead += qStart;
    if (qStart > QSIZE || qStart < QSIZE/16)
    {
      printf("BFS queue is too small for saved state\n");
      exit(0);
   }
   for (i = qStart; i < qEnd; i++)
        rows[i] = (row) loadUInt(fp);
    fclose(fp);
/*
   printf("qHead:  %d qStart: %d qEnd: %d\n",qHead,qStart,qEnd);
   printf("rows[0]: %d\n",rows[qStart]);
   printf("rows[1]: %d\n",rows[qStart+1]);
   printf("rows[2]: %d\n",rows[qStart+2]);
   fflush(stdout);
   exit(0);
*/
    doCompactPart2();


    /* Let the user know that we got this far */
   printf("State successfully loaded from file %s",loadFile);
   
   if(!strcmp(cmd,"p") || !strcmp(cmd,"P")){
      preview(1);
      exit(0);
   }
   
   fflush(stdout);
   
   omp_set_num_threads(params[P_NUMTHREADS]);
}





int lookAhead(row *pRows, int a, int pPhase){
   uint32_t ri11, ri12, ri13, ri22, ri23;  //indices: first number represents vertical offset, second number represents generational offset
   uint32_t rowSet11, rowSet12, rowSet13, rowSet22, rowSet23, rowSet33;
   uint32_t riStart11, riStart12, riStart13, riStart22, riStart23;
   uint32_t numRows11, numRows12, numRows13, numRows22, numRows23;
   uint32_t row11, row12, row13, row22, row23;
   
   
   rowSet11 = (pRows[a - params[P_PERIOD] - fwdOff[pPhase]] << (2 * params[P_WIDTH]))
             +(pRows[a - fwdOff[pPhase]] << params[P_WIDTH])
             + pRows[a];
   riStart11 = gInd[rowSet11];
   numRows11 = gInd[rowSet11 + 1] - riStart11;
   
   if(!numRows11) return 0;

   rowSet12 = (pRows[a - params[P_PERIOD] - doubleOff[pPhase]] << (2 * params[P_WIDTH]))
             +(pRows[a - doubleOff[pPhase]] << params[P_WIDTH])
             + pRows[a - fwdOff[pPhase]];
   riStart12 = gInd[rowSet12];
   numRows12 = gInd[rowSet12 + 1] - riStart12;

   if(tripleOff[pPhase] >= params[P_PERIOD]){
      //riStart13 = pInd[a + params[P_PERIOD] - tripleOff[pPhase]] + pRemain[a + params[P_PERIOD] - tripleOff[pPhase]];
      numRows13 = 1;
   }
   else{
      rowSet13 = (pRows[a - params[P_PERIOD] - tripleOff[pPhase]] << (2 * params[P_WIDTH]))
                +(pRows[a - tripleOff[pPhase]] << params[P_WIDTH])
                + pRows[a - doubleOff[pPhase]];
      riStart13 = gInd[rowSet13];
      numRows13 = gInd[rowSet13 + 1] - riStart13;
   }

   for(ri11 = 0; ri11 < numRows11; ++ri11){
      row11 = gRows[ri11 + riStart11];
      for(ri12 = 0; ri12 < numRows12; ++ri12){
         row12 = gRows[ri12 + riStart12];
         rowSet22 = (pRows[a - doubleOff[pPhase]] << (2 * params[P_WIDTH]))
                   +(row12 << params[P_WIDTH])
                   + row11;
         riStart22 = gInd[rowSet22];
         numRows22 = gInd[rowSet22 + 1] - riStart22;
         if(!numRows22) continue;

         for(ri13 = 0; ri13 < numRows13; ++ri13){
            if(tripleOff[pPhase] >= params[P_PERIOD]){
               row13 = pRows[a + params[P_PERIOD] - tripleOff[pPhase]];
            }
            else{
               row13 = gRows[ri13 + riStart13];
            }
            rowSet23 = (pRows[a - tripleOff[pPhase]] << (2 * params[P_WIDTH]))
                      +(row13 << params[P_WIDTH])
                      + row12;
            riStart23 = gInd[rowSet23];
            numRows23 = gInd[rowSet23 + 1] - riStart23;
            if(!numRows23) continue;

            for(ri22 = 0; ri22 < numRows22; ++ri22){
               row22 = gRows[ri22 + riStart22];
               for(ri23 = 0; ri23 < numRows23; ++ri23){
                  row23 = gRows[ri23 + riStart23];
                  rowSet33 = (row13 << (2 * params[P_WIDTH]))
                            +(row23 << params[P_WIDTH])
                            + row22;
                  if(gInd[rowSet33] != gInd[rowSet33 + 1]) return 1;
               }
            }
         }
      }
   }
   return 0;
}



void process(node theNode)
{
   long long int i;
   int firstRow = 0;
   uint32_t numRows;
   uint32_t newRowSet;
   node x = theNode;
   int pPhase = peekPhase(x);
   row pRows[3*MAXPERIOD];
   int currRow = 2*period + pPhase + 1;
   for(i = currRow - 1; i >= 0; --i){
      pRows[i] = ROW(x);
      x = PARENT(x);
   }

   ++pPhase;
   if(pPhase == period) pPhase = 0;

   newRowSet = (pRows[currRow - 2 * period] << (2 * params[P_WIDTH]))
              +(pRows[currRow - period] << params[P_WIDTH])
              + pRows[currRow - period + backOff[pPhase]];
   numRows = gInd[newRowSet + 1] - gInd[newRowSet];


   if(theNode == 0){
      firstRow = 1;
   }

   for(i = firstRow; i < numRows; ++i){
      pRows[currRow] = gRows[gInd[newRowSet] + i];
      if (!isVisited(theNode, pRows[currRow]) && lookAhead(pRows, currRow, pPhase)){
         enqueue(theNode, pRows[currRow]);
         if (terminal(qTail-1)) success(qTail-1, NULL, 0, 0);
         setVisited(qTail - 1);
      }
   }
}

int depthFirst(node theNode, long howDeep, uint32_t *pInd, uint32_t *pRemain, row *pRows){
//   uint32_t *pInd;
//   uint32_t *pRemain;

   int pPhase;
//   row *pRows;

   uint32_t newRowSet;
   pPhase = peekPhase(theNode);




//   pInd = malloc((long long)sizeof(*pInd) * (howDeep + 3 * params[P_PERIOD]));
//   pRemain = malloc((long long)sizeof(*pRemain) * (howDeep + 3 * params[P_PERIOD]));
//   pRows = malloc((long long)sizeof(*pRows) * (howDeep + 3 * params[P_PERIOD]));

   node x = theNode;
   uint32_t startRow = 2*period + pPhase + 1;
   uint32_t currRow = startRow;
   
   int i;
   for(i = currRow - 1; i >= 0; --i){
      pRows[i] = ROW(x);
      x = PARENT(x);
   }

   ++pPhase;
   if(pPhase == period) pPhase = 0;

   newRowSet = (pRows[currRow - 2 * period] << (2 * width))
              |(pRows[currRow - period] << width)
              | pRows[currRow - period + backOff[pPhase]];

   pRemain[currRow] = gInd[newRowSet + 1] - gInd[newRowSet];
   pInd[currRow] = gInd[newRowSet + 1];

   
   for(;;){

      if(!pRemain[currRow]){
         --currRow;
         if(pPhase == 0) pPhase = period;
         --pPhase;
         if(currRow < startRow){
//            free(pInd);
//            free(pRemain);
//            free(pRows);
            return 0;
         }
         continue;
      }
      //--pRemain[currRow];

      pRows[currRow] = gRows[pInd[currRow] - pRemain[currRow]];
      --pRemain[currRow];
      if(!lookAhead(pRows, currRow, pPhase)) continue;

      ++currRow;
      ++pPhase;
      if(pPhase == period) pPhase = 0;
      if(currRow > startRow + howDeep){
//         free(pInd);
//         free(pRemain);
//         free(pRows);
         for(i = 1; i <= period; ++i){
            if(pRows[currRow - i]) return 1;
         }
         currRow -= period;
         for(i = 1; i<= period; ++i){
            if(causesBirth[pRows[currRow - i]]) return 1;
         }
         success(theNode, pRows, startRow - 1, currRow + period - 1);
         
         return 1;
         
      }

      newRowSet = (pRows[currRow - 2 * period] << (2 * params[P_WIDTH]))
                 +(pRows[currRow - period] << params[P_WIDTH])
                 + pRows[currRow - period + backOff[pPhase]];
      pRemain[currRow] = gInd[newRowSet + 1] - gInd[newRowSet];
      pInd[currRow] = gInd[newRowSet + 1];

   }
}


static void deepen(){
   node i;
   //node j;

//   if (findLimit > 1) perdidor = 1;   /* disable success if want mult pattern output */

   /* compute amount to deepen, apply reduction if too deep */
#ifdef PATCH07
   timeStamp();
#endif
   printf("Queue full");
   i = currentDepth();
   if (i >= lastdeep) deepeningAmount = period;
   else deepeningAmount = lastdeep + period - i;   /* go at least one period deeper */

   lastdeep = i + deepeningAmount;

   /* start report of what's happening */
   printf(", depth %ld, deepening %d, ", (long int) i, deepeningAmount);
   putnum(qTail - qHead);
   printf("/");
   putnum(qTail);
   fflush(stdout);


   /* go through queue, deepening each one */
   
   #pragma omp parallel
   {
   node j;
   uint32_t *pInd;
   uint32_t *pRemain;
   row *pRows;
   
   
   pInd = malloc((long long)sizeof(*pInd) * (deepeningAmount + 4 * params[P_PERIOD]));
   pRemain = malloc((long long)sizeof(*pRemain) * (deepeningAmount + 4 * params[P_PERIOD]));
   pRows = malloc((long long)sizeof(*pRows) * (deepeningAmount + 4 * params[P_PERIOD]));
   
   #pragma omp for
   for (j = qHead; j < qTail; j++) {
      if (!EMPTY(j) && !depthFirst(j, deepeningAmount, pInd, pRemain, pRows))
         MAKEEMPTY(j);
   }
   free(pInd);
   free(pRemain);
   free(pRows);
   }
   
   if (deepeningAmount > period) deepeningAmount--; /* allow for gradual depth reduction */
   
   /* before reporting new queue size, shrink tree back down */
   printf(" -> ");
   fflush(stdout);
//   hash = savedHash;
   //perdidor = 0;

   /* signal time for dump */
   if (params[P_CHECKPOINT]) dumpFlag = DUMPPENDING;

   doCompact();

   /* now finish report */
   putnum(qTail - qHead);
   printf("/");
   putnum(qTail);
   printf("\n");

   /* Report successful/unsuccessful dump */
   if (dumpFlag == DUMPSUCCESS)
   {
#ifdef PATCH07
      timeStamp();
#endif
       printf("State dumped to %s\n",dumpFile);
       /*analyse();
       if (chainWidth)
           printf("[%d/%d]\n",chainDepth,chainWidth+1);
       else
           printf("[%d/-]\n",chainDepth);*/
   }
   else if (dumpFlag == DUMPFAILURE)
   {
#ifdef PATCH07
      timeStamp();
#endif
      printf("State dump unsuccessful\n");
   }

   
   fflush(stdout);
}


static void breadthFirst()
{
   while (!aborting && !qIsEmpty()) {
      if (qTail - qHead >= (1<<params[P_DEPTHLIMIT]) || qTail >= QSIZE - QSIZE/16 ||
          qTail >= QSIZE - (deepeningAmount << 2)) deepen();
      else process(dequeue());
   }
}


int gcd(int a, int b) {
   if (a > b) return gcd(b,a);
   else if (a == 0) return b;
   else return gcd(b-a,a);
}

void echoParams(){
   printf("%s",BANNER);
   printf("\n");
   printf("Rule: ");
   printRule();
   printf("\n");
   printf("Period: %d\n",params[P_PERIOD]);
   printf("Offset: %d\n",params[P_OFFSET]);
   printf("Width:  %d\n",params[P_WIDTH]);
   if(params[P_SYMMETRY] == SYM_ASYM) printf("Symmetry: asymmetric\n");
   else if(params[P_SYMMETRY] == SYM_ODD) printf("Symmetry: odd\n");
   else if(params[P_SYMMETRY] == SYM_EVEN) printf("Symmetry: even\n");
   else if(params[P_SYMMETRY] == SYM_GUTTER) printf("Symmetry: gutter\n");
   if(params[P_CHECKPOINT]) printf("Dump state after compaction of queue\n");
   if(!params[P_REORDER]) printf("Use naive search order.\n");
   printf("Number of threads:  %d\n",params[P_NUMTHREADS]);
}


void usage(){
   printf("%s\n",BANNER);
   printf("\n");
   printf("Usage: \"program_name options\"\n");
   printf("  e.g. \"program_name B3/S23 p3 k1 w6 v\" searches Life (rule B3/S23) for\n");
   printf("  c/3 orthogonal spaceships with even bilateral symmetry and a\n");
   printf("  search width of 6 (full width 12).\n");
   printf("\n");
   printf("Available options:\n");
   printf("  bNN/sNN searches for spaceships in the specified rule (default: b3/s23)\n");
   printf("\n");
   printf("  pNN  searches for spaceships with period NN\n");
   printf("  kNN  searches for spaceships that travel NN cells every period\n");
   printf("  wNN  searches for spaceships with search width NN\n");
   printf("       (full width depends on symmetry type)\n");
   printf("\n");
   printf("  tNN  runs search using NN threads during deepening step (default: 1)\n");
   printf("  hNN  sets the hash table size to 2^NN (default %d)\n",HASHBITS);
   printf("       Use /h0 to disable duplicate elimination.\n");
   printf("  qNN  sets the BFS queue size to 2^NN (default %d)\n",QBITS);
   printf("  iNN  groups 2^NN queue entries to an index node (default 4)\n");
   printf("\n");
   //printf("  lNN  terminates the search if it reaches a depth of NN (default: %d)\n",DEFAULT_DEPTH_LIMIT);
   //printf("  mNN  disallows spaceships longer than a depth of NN\n");
   //printf("       (the spaceship length is approximately depth/period)\n");
   //printf("  fNN  disallows spaceships that do not have the full period by a depth of NN\n");
   //printf("  tNN  disallows full-period rows of width greater than NN\n");
   //printf("  sNN  terminates the search if NN spaceships are found (default: 1)\n");
   //printf("\n");
   printf("  d    dumps the search state after each queue compaction\n");
   //printf("  j    dumps the state at start of search\n");
   printf("\n");
   printf("  a    searches for asymmetric spaceships\n");
   printf("  u    searches for odd bilaterally symmetric spaceships\n");
   printf("  v    searches for even bilaterally symmetric spaceships\n");
   printf("  g    searches for symmetric spaceships with gutters (empty center column)\n");
   printf("\n");
   //printf("  o    uses naive search order (search will take longer when no ships exist)\n");
   //printf("\n");
   //printf("  e FF uses rows in the file FF as the initial rows for the search\n");
   //printf("       (use the companion Golly python script to easily generate the\n");
   //printf("       initial row file)\n");
   //printf("\n");
   printf("\"program_name command file\" reloads the state from the specified file\n");
   printf("and performs the command. Available commands: \n");
   printf("  s    resumes search from the loaded state\n");
   printf("  p    previews partial results\n");
}


int main(int argc, char *argv[]){
   params[P_RULE] = 6152;         //first 9 bits represent births; next 9 bits represent survivals
   params[P_WIDTH] = 0;
   params[P_PERIOD] = 0;
   params[P_OFFSET] = 0;
   params[P_SYMMETRY] = 0;
   //params[P_INIT_ROWS] = 0;
   //params[P_FULL_PERIOD] = 0;
   params[P_NUM_SHIPS] = 1;
   //params[P_FULL_WIDTH] = 0;
   params[P_REORDER] = 1;
   params[P_BASEBITS] = 5;
   params[P_QBITS] = QBITS;
   params[P_HASHBITS] = HASHBITS;
   params[P_NUMTHREADS] = 1;

   int loadDumpFlag = 0;


   //int dumpandexit = 0;
   int skipNext = 0;
   //int div1,div2;
   int s;
   if(argc == 2 && !strcmp(argv[1],"c")){
      usage();
      return 0;
   }
   if(argc == 3 && (!strcmp(argv[1],"s") || !strcmp(argv[1],"S") || !strcmp(argv[1],"p") || !strcmp(argv[1],"P"))) loadDumpFlag = 1;
   else{
      for(s = 1; s < argc; s++){    //read input parameters
         if(skipNext){
            skipNext = 0;
            continue;
         }
         switch(argv[s][0]){
            case 'b': case 'B':     //read rule
               params[P_RULE] = 0;
               int sshift = 0;
               int i;
               for(i = 1; i < 100; i++){
                  int rnum = argv[s][i];
                  if(!rnum)break;
                  if(rnum == 's' || rnum == 'S')sshift = 9;
                  if(rnum >= '0' && rnum <= '8')params[P_RULE] += 1 << (sshift + rnum - '0');
               }
            break;
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &params[P_WIDTH]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &params[P_PERIOD]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &params[P_OFFSET]); break;
            case 'u': case 'U': params[P_SYMMETRY] = SYM_ODD; mode = odd; break;
            case 'v': case 'V': params[P_SYMMETRY] = SYM_EVEN; mode = even; break;
            case 'a': case 'A': params[P_SYMMETRY] = SYM_ASYM; mode = asymmetric; break;
            case 'g': case 'G': params[P_SYMMETRY] = SYM_GUTTER; mode = gutter; break;
            case 'd': case 'D': params[P_CHECKPOINT] = 1; break;
            //case 'j': case 'J': dumpandexit = 1; break;
            //case 'e': case 'E': params[P_INIT_ROWS] = s + 1; skipNext = 1; break;
            //case 'f': case 'F': sscanf(&argv[s][1], "%d", &params[P_FULL_PERIOD]); break;
            case 's': case 'S': sscanf(&argv[s][1], "%d", &params[P_NUM_SHIPS]); break;
            case 't': case 'T': sscanf(&argv[s][1], "%d", &params[P_NUMTHREADS]); break;
            case 'o': case 'O': params[P_REORDER] = 0; break;
            case 'q': case 'Q': sscanf(&argv[s][1], "%d", &params[P_QBITS]); break;
            case 'h': case 'H': sscanf(&argv[s][1], "%d", &params[P_HASHBITS]); break;
            case 'i': case 'I': sscanf(&argv[s][1], "%d", &params[P_BASEBITS]); break;
         }
      }
   }

   
   
   
   if(loadDumpFlag) loadState(argv[1],argv[2]);
   else{
      
      width = params[P_WIDTH];
      period = params[P_PERIOD];
      offset = params[P_OFFSET];
      deepeningAmount = period;
      lastdeep = 0;
      hashPhase = (gcd(period,offset)>1);
   
      rule = params[P_RULE];
   
      nRowsInState = period+period;
   
      params[P_DEPTHLIMIT] = DEFAULT_DEPTHLIMIT;
   
      //if(params[P_SYMMETRY] == SYM_ASYM){
      //   mode = asymmetric;
      //}
   
      base = malloc((QSIZE>>BASEBITS)*sizeof(node));
      rows = malloc(QSIZE*sizeof(row));
      if (base == 0 || rows == 0) {
         printf("Unable to allocate BFS queue!\n");
         exit(0);
      }
   
      if (hashBits == 0) hash = 0;
      else {
         hash = malloc(HASHSIZE*sizeof(node));
         if (hash == 0) printf("Unable to allocate hash table, duplicate elimination disabled\n");
      }
      
      omp_set_num_threads(params[P_NUMTHREADS]);
      
      enqueue(0,0);
   }
   
   echoParams();
   
   makePhases();
   makeTables();

   //enqueue(0,0);
   rephase();


   /*printRule();
   printf("\nperiod: %d\n",period);
   printf("width: %d\n",width);
   printf("offset: %d\n",offset);
   printf("Symmetry: %d\n\n",params[P_SYMMETRY]);*/
   //printf("Hash bits: %d\n\n",hashBits);


   printf("Starting Search\n");
   
   breadthFirst();

   printf("Search complete.\n");

   return 0;
}
To compile with gcc, you need to use the "-fopenmp" flag. For other compilers it may be different. Run the program with "c" as the only parameter to get a list of options. When using the "t" command to set the number of threads, the number of threads should be less than or equal to the number of cores that your computer has available.
-Matthias Merzenich

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: A new spaceship search program

Post by Saka » June 19th, 2017, 8:43 am

Maybe name it:
-gertz (I dunno, gz)
-sfind (sokwe find)
-zxg (x is a common symbol used for plant crosses)
-ssf (acronym for Sokwe's Spaceship Finder)
-SoSpi (See above)
-mfind (Matthias find)
-msd (acronym for Matthias's Spaceshil Finder)
-MaSpi (See above)

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: A new spaceship search program

Post by praosylen » June 19th, 2017, 10:48 am

I like it!

It finds the copperhead after ~45 seconds on my system, compared to the reported 1 hour for gfind. That's pretty impressive, although it doesn't beat zfind itself. So, basically, a limited version of gfind that's faster, especially at high periods?

Also, are there any plans for non-totalistic support? Seeing as how both gfind and zfind can independently be modified for non-totalistic support, would this be possible?

Naming suggestions:

sss (SpaceShip Search)
qfind (quick)
tsearch/tfind (thin)

Is this search program capable of ruling out the existence of ships with a specific period and speed? Does that include period-doubling/tripling/etc. combinations?

EDIT: No results found for p10 k5 w9 v -- the search took about 5 minutes. This is quite a fast program.

EDIT 2: On every 4c/8 search I have done so far, it has skipped many results containing MWSSs and HWSSs, when the equivalent results containing LWSSs were outputted. Is this some kind of issue with repeating components of length 1, or is a more serious issue present?

EDIT 3: This is by no means important, but a trailing newline at the end of the output might be good.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 19th, 2017, 5:23 pm

A for awesome wrote:So, basically, a limited version of gfind that's faster, especially at high periods?
Yes, basically.
A for awesome wrote:Is this search program capable of ruling out the existence of ships with a specific period and speed? Does that include period-doubling/tripling/etc. combinations?
I'm not confident enough to make this claim yet. Eventually I want the answer to be yes.
A for awesome wrote:It finds the copperhead after ~45 seconds on my system, compared to the reported 1 hour for gfind. That's pretty impressive, although it doesn't beat zfind itself.
It doesn't beat zfind partly due to luck. The search order of zfind happens to find the copperhead fairly early. A better speed test would be to use a search that finds no spaceships. In such cases, it seems that the new program is slower than zfind when only using one core, but multiple cores can make it faster than zfind (at least for some searches).

For example, the c/10 odd-symmetric width-11 (w6) search is faster (at least for me) with 2 cores using the multithreaded program. On the other hand, zfind was faster than a 4-core multithreaded search for c/11 odd-symmetric width-9 (w5) ships. In general, this new program probably does better for slow, high-period ships with "large" widths.

Hopefully there's room to improve the single-threaded version of the new program.
A for awesome wrote:are there any plans for non-totalistic support?
The necessary modifications should be similar to those in ntzfind. I think the only place where the rules are used is in the function evolveBit(). The function printRule() would also need to be modified. I'll leave these modifications to someone else.
A for awesome wrote:On every 4c/8 search I have done so far, it has skipped many results containing MWSSs and HWSSs, when the equivalent results containing LWSSs were outputted. Is this some kind of issue with repeating components of length 1, or is a more serious issue present?
This is due to the duplicate row elimination. Basically, the last few rows of a MWSS or HWSS look just like the last few rows of a LWSS. Since the search has already seen the last few rows of the LWSS, it discards those rows when they show up again in the MWSS and HWSS. To see this, run "p4 k2 w6 g". You should get only LWSSs and X66. Next, run "p4 k2 w6 g h0" (the "h0" command turns off duplicate elimination). You should find MWSSs and HWSSs in the output. Note that you should kill this second search after a few seconds, since it will never stop finding ships.
A for awesome wrote:No results found for p10 k5 w9 v -- the search took about 5 minutes. This is quite a fast program.
How many cores did you use?
A for awesome wrote:a trailing newline at the end of the output might be good.
Do you mean after "Search complete."?
-Matthias Merzenich

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: A new spaceship search program

Post by praosylen » June 19th, 2017, 6:04 pm

Sokwe wrote:
A for awesome wrote:No results found for p10 k5 w9 v -- the search took about 5 minutes. This is quite a fast program.
How many cores did you use?
1.
Sokwe wrote:
A for awesome wrote:a trailing newline at the end of the output might be good.
Do you mean after "Search complete."?
Yes.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 19th, 2017, 6:18 pm

A for awesome wrote:
Sokwe wrote: How many cores did you use?
1.
I think the main advantage of this program over zfind is being multithreaded. If you have a multi-core computer, you should definitely try using the "t" command.

Another advantage over zfind is that the search is essentially breadth-first, so it finds short spaceships first. It's also good for finding multiple spaceships with which zfind always struggled (e.g., see my results here).
A for awesome wrote:a trailing newline at the end of the output might be good.
Done.
-Matthias Merzenich

User avatar
gameoflifeboy
Posts: 474
Joined: January 15th, 2015, 2:08 am

Re: A new spaceship search program

Post by gameoflifeboy » June 19th, 2017, 7:53 pm

When I compile it on Ubuntu using

Code: Select all

gcc ./sfind.c -fopenmp
I get this error:

Code: Select all

/tmp/ccxtPgUA.o: In function `success':
sfind.c:(.text+0x15b0): undefined reference to `safeShift'
sfind.c:(.text+0x15fc): undefined reference to `safeShift'
/tmp/ccxtPgUA.o: In function `doCompactPart2':
sfind.c:(.text+0x2385): undefined reference to `enqueue'
sfind.c:(.text+0x23b9): undefined reference to `setVisited'
/tmp/ccxtPgUA.o: In function `doCompact':
sfind.c:(.text+0x23e9): undefined reference to `qIsEmpty'
/tmp/ccxtPgUA.o: In function `process':
sfind.c:(.text+0x326c): undefined reference to `isVisited'
sfind.c:(.text+0x32b7): undefined reference to `enqueue'
sfind.c:(.text+0x32fa): undefined reference to `setVisited'
/tmp/ccxtPgUA.o: In function `breadthFirst':
sfind.c:(.text+0x3a6e): undefined reference to `dequeue'
sfind.c:(.text+0x3a89): undefined reference to `qIsEmpty'
/tmp/ccxtPgUA.o: In function `main':
sfind.c:(.text+0x437d): undefined reference to `enqueue'
collect2: error: ld returned 1 exit status
This is strange, because all of these functions are defined in the code and no errors were reported within any of them. Can anyone tell me what's going on here?

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: A new spaceship search program

Post by Saka » June 19th, 2017, 11:47 pm

gameoflifeboy wrote:When I compile it on Ubuntu using

Code: Select all

gcc ./sfind.c -fopenmp
I get this error:

Code: Select all

Snip
This is strange, because all of these functions are defined in the code and no errors were reported within any of them. Can anyone tell me what's going on here?
Same here

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 1:28 am

gameoflifeboy wrote:When I compile it... I get this error
This seems to be caused by the inline functions when you compile without optimizations. First, you should almost always compile with optimizations. The way to do this with gcc is to use the -O3 flag. If you compile with -O3 these errors will be gone.

Since this program is just a single c source file with standard header files, there's no cost to declaring all inline functions static, so I have edited the original code accordingly. Now it should compile without -O3, but again, you want to be compiling with -O3, so this fix shouldn't matter much.
-Matthias Merzenich

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: A new spaceship search program

Post by Saka » June 20th, 2017, 7:28 am

I tried it. Nice! How do I set the "level" (like in gfind)? Is it H?
EDIT: Found it, it's Q. What does h and i do then? I think i groups results? I don't understand those technical terms.
It's very fast, maybe name it:
qfind (Like A for Awesome)
qsearch
Quickee
F1 (This is also used for tissue cultures, but whatever)
HnS (Hide and Seek. You are seeking for the spaceships hehe)

EDIT2:
OH MY GOD p4 k1 w8 q50 u/g MAKES SO MUCH RLES
THIS SO FAST

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 2:35 pm

Saka wrote:I tried it. Nice! How do I set the "level" (like in gfind)?
EDIT: Found it, it's Q.
I'm not sure what you mean by "level". The "q" parameter sets the size of the breadth-first queue. When the queue fills up it triggers a deepening round. This works exactly the same as gfind.
Saka wrote:What does h and i do then?
The "h" parameter sets the size of the hash table used in duplicate elimination. Setting h to larger values means you can store more rows to check for duplicates. Setting "h0" means that duplicate elimination is turned off entirely. For most searches there's no reason to change the default value.

The "i" parameter is a little technical and I'm not really sure of its intended purpose. (memory saving?) Don't bother changing it.
-Matthias Merzenich

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: A new spaceship search program

Post by Scorbie » June 20th, 2017, 2:57 pm

Huh, great program you've got there!
It reports interesting partials when I do not specify any symmetry (from a/v/u) is this intended behavior?
For instance,

Code: Select all

./sfind b3s23 p5 k2 w9
outputs these:

Code: Select all

x = 29, y = 37, rule = B3/S23
21b2obobo$24bo$20bo3bo$20bo4bo$20bob5o$20bobo3bo$21bo4bo$22b4o$23b2o$
21bo$23bo$20bo3bo$21b3o$21b3o$25b2o$24b3o$24b3o2$24bo2bo$20b4o3bo$24b
3o$20b2o$24b3o$22bobo$20b2ob2o$obo20b2o$3b3o14b2obo2b2o$5b2o15b2o2bo$
3bo21b2o$3b2o17b2obob2o$4b2o16b2obob2o$2b2ob2o16bobobo$bo2bo17b2ob3o$
2ob2o18bo3bo$bobo19bobo$2bo21bo2bo$25b3o!
(While writing this post)
Ah, now I get it... this is a half-solution for the gutter symmetry!

Anyway, exciting to see another searcher out here :)

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 3:02 pm

Scorbie wrote:It reports interesting partials when I do not specify any symmetry (from a/v/u) is this intended behavior?
It's not intended. I was in a rush to release it, so I didn't add any checks for bad input.
-Matthias Merzenich

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: A new spaceship search program

Post by Scorbie » June 20th, 2017, 3:03 pm

Sokwe wrote:
Scorbie wrote:It reports interesting partials when I do not specify any symmetry (from a/v/u) is this intended behavior?
It's not intended. I was in a rush to release it, so I didn't add any checks for bad input.
Whoops! I misthought that the symmetry defaults to the gutter symmetry. (If it does you can just change the documentation...) Thanks for the prompt response:)

EDIT to Sokwe's reply (In order to reduce all this clutter I'm making)
Ah, I see. Thanks! (It's undefined behavior anyway, so no worries on your side :))
Last edited by Scorbie on June 20th, 2017, 3:47 pm, edited 1 time in total.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 3:07 pm

Scorbie wrote:I misthought that the symmetry defaults to the gutter symmetry.
When you use the actual gutter symmetry ("g" parameter) it outputs complete spaceships.
-Matthias Merzenich

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: A new spaceship search program

Post by praosylen » June 20th, 2017, 4:14 pm

Sokwe wrote:The "i" parameter is a little technical and I'm not really sure of its intended purpose. (memory saving?) Don't bother changing it.
Here's some sort of a clue: Greatly increasing the "i" parameter seems to speed up searches significantly, especially at high periods. Using "i16" almost halves the time taken to find the copperhead, and for some even-higher-period searches, the speed-up for certain i-values is by more than a factor of 10 (although the trend might reverse at extreme periods):

Code: Select all

p5 k2 w9 a
i2: 15s
i10: 14s
i12: 13s
i14: 13s
i16: 13s
i18: 13s
i20: 14s
i22: 15s
i23: "Exceeded 8388608 node limit, search aborted"


p6 k2 w7 v
i2: 14s
i10: 12s
i12: 10s
i14: 9s
i16: 8s
i17: 11s
i18: 14s
i20: 14s
i22: 15s
i23: "Exceeded 8388608 node limit, search aborted"


p10 k1 w5 v
i2: 110s
i10: 108s
i11: 100s
i12: 76s
i13: 69s
i14: 64s
i15: 65s
i16: 62s
i17: 65s
i18: 66s
i19: 74s
i20: 76s
i21: 79s
i22: 80s
i23: "Exceeded 8388608 node limit, search aborted"


p19 k1 w3 v
i2: 20s
i10: 18s
i11: 17s
i12: 17s
i13: 15s
i14: 8s
i15: 5s
i16: 4s
i17: 3s
i18: 2s
i19: 2s
i20: 2s
i21: 2s
i22: 2s
i23: "Exceeded 8388608 node limit, search aborted"


p13 k6 w6 v
i2: 16s
i10: 13s
i11: 12s
i12: 9s
i13: 5s
i14: 3s
i15: 2s
i16: 1.5s
i17: 1.5s
i18: 1.5s
i19: <1.5s
i20: <1.5s
i21: <1.5s
i22: <1.5s
i23: "Exceeded 8388608 node limit, search aborted"


p24 k9 w4 v
i2: 24s
i10: 24s
i12: 24s
i13: 23s
i14: 22s
i15: 19s
i16: 18s
i18: 18s
i20: 17s
i22: 17s
These are not the most accurate values, as I used a stopwatch to determine them, but they should be good to within a second. Do you have any idea what is going on?

EDIT: I noticed that increasing the "i" parameter also caused more and larger ships to appear on the 2c/6 searches. Are some of those duplicates that would normally be caught by the duplicate elimination?
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 4:55 pm

A for awesome wrote:Do you have any idea what is going on?
No, I don't. I guess I'll have to look into this more. I thought an i value greater than 6 didn't make sense based on the code. I guess I don't understand it as well as I thought.
-Matthias Merzenich

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: A new spaceship search program

Post by Saka » June 20th, 2017, 10:04 pm

Any way to increase the max number of nodes?

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » June 20th, 2017, 11:17 pm

Saka wrote:Any way to increase the max number of nodes?
That's what the "q" parameter does. The default value is 23, so the maximum number of nodes is 2^23=8388608.
-Matthias Merzenich

User avatar
BlinkerSpawn
Posts: 1992
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: A new spaceship search program

Post by BlinkerSpawn » June 21st, 2017, 2:10 pm

muzik wrote:Will it be able to support nontotalistic rules?
Sokwe wrote:
A for awesome wrote:are there any plans for non-totalistic support?
The necessary modifications should be similar to those in ntzfind. I think the only place where the rules are used is in the function evolveBit(). The function printRule() would also need to be modified. I'll leave these modifications to someone else.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: A new spaceship search program

Post by toroidalet » July 3rd, 2017, 12:22 am

When I try compiling it with gcc newzfind.c (that's what I called it) -o newzfind -fopenmp
I get the error where it spams the command line with treating unicode characters as whitespaces and then doesn't compile as an executable.
Also, for the name I recommend qfind (q is about halfway between z and g and looks sort of like a g in some fonts)
Any sufficiently advanced software is indistinguishable from malice.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » July 3rd, 2017, 7:23 pm

toroidalet wrote:When I try compiling it with gcc newzfind.c (that's what I called it) -o newzfind -fopenmp
I get the error where it spams the command line with treating unicode characters as whitespaces and then doesn't compile as an executable.
I'm not sure why this is happening. If you post the exact error messages here I might be able to figure something out.
toroidalet wrote:Also, for the name I recommend qfind (q is about halfway between z and g and looks sort of like a g in some fonts)
I think this is what I will probably go with. You're reasoning was actually my original plan before I realized that there isn't a letter halfway between 'g' and 'z'.
-Matthias Merzenich

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: A new spaceship search program

Post by toroidalet » July 3rd, 2017, 11:08 pm

The error message went like

Code: Select all

{abridged}
newzfind.c:1598:10: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
         if (hash == 0) printf("Unable to allocate hash table, duplicat...
      ^
newzfind.c:1598:13: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
         if (hash == 0) printf("Unable to allocate hash table, duplicat...
        ^
newzfind.c:1599:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      }
^
newzfind.c:1599:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      }
  ^
newzfind.c:1599:7: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      }
    ^
newzfind.c:1600:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
^
newzfind.c:1600:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
  ^
newzfind.c:1600:7: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
    ^
newzfind.c:1601:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      omp_set_num_threads(params[P_NUMTHREADS]);
^
newzfind.c:1601:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      omp_set_num_threads(params[P_NUMTHREADS]);
  ^
newzfind.c:1601:7: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      omp_set_num_threads(params[P_NUMTHREADS]);
    ^
newzfind.c:1602:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
^
newzfind.c:1602:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
  ^
newzfind.c:1602:7: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      
    ^
newzfind.c:1603:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      enqueue(0,0);
^
newzfind.c:1603:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      enqueue(0,0);
  ^
newzfind.c:1603:7: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
      enqueue(0,0);
    ^
newzfind.c:1604:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   }
^
newzfind.c:1604:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   }
  ^
newzfind.c:1605:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
^
newzfind.c:1605:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
  ^
newzfind.c:1606:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   echoParams();
^
newzfind.c:1606:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   echoParams();
  ^
newzfind.c:1607:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
^
newzfind.c:1607:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
  ^
newzfind.c:1608:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   makePhases();
^
newzfind.c:1608:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   makePhases();
  ^
newzfind.c:1609:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   makeTables();
^
newzfind.c:1609:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   makeTables();
  ^
newzfind.c:1611:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   //enqueue(0,0);
^
newzfind.c:1611:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   //enqueue(0,0);
  ^
newzfind.c:1612:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   rephase();
^
newzfind.c:1612:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   rephase();
  ^
newzfind.c:1615:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   /*printRule();
^
newzfind.c:1615:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   /*printRule();
  ^
newzfind.c:1620:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   //printf("Hash bits: %d\n\n",hashBits);
^
newzfind.c:1620:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   //printf("Hash bits: %d\n\n",hashBits);
  ^
newzfind.c:1623:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   printf("Starting Search\n");
^
newzfind.c:1623:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   printf("Starting Search\n");
  ^
newzfind.c:1624:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
^
newzfind.c:1624:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   
  ^
newzfind.c:1625:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   breadthFirst();
^
newzfind.c:1625:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   breadthFirst();
  ^
newzfind.c:1627:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   printf("Search complete.");
^
newzfind.c:1627:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   printf("Search complete.");
  ^
newzfind.c:1629:1: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   return 0;
^
newzfind.c:1629:4: warning: treating Unicode character as whitespace
      [-Wunicode-whitespace]
   return 0;
  ^
This happened with zfind too, but I forgot how I fixed that.
Any sufficiently advanced software is indistinguishable from malice.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search program

Post by Sokwe » July 4th, 2017, 3:02 am

toroidalet wrote:The error message went like...
It only seems to be attacking characters that are already white space, so these warnings should not be preventing compilation.

I wonder if your text editor is somehow changing the text when it is saved. Try downloading the code instead:
qfind.c
(45.86 KiB) Downloaded 472 times
If the downloaded code works, then I would guess that the problem is with your text editor. If the downloaded code has the same problems, I would guess that the problem is with the compiler.
-Matthias Merzenich

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: A new spaceship search program

Post by wildmyron » July 4th, 2017, 10:07 am

Sokwe wrote:
toroidalet wrote:The error message went like...
It only seems to be attacking characters that are already white space, so these warnings should not be preventing compilation.
Perhaps try compiling with -Wno-unicode-whitespace to suppress these warnings so that the actual error messages preventing compilation won't be lost amongst the warnings, though figuring out why the file suddenly has unicode characters littered everywhere is probably a better option.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Post Reply