text: #include "finders.h"
  
  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #include <math.h>
  #include <limits.h>
  
  #include <sys/types.h>
  #include <sys/stat.h>
  
  #if defined(_WIN32)
  #include <direct.h>
  #define IS_DIR_SEP(C) ((C) == '/' || (C) == '\\')
  #define stat _stat
  #define mkdir(P,X) _mkdir(P)
  #define S_IFDIR _S_IFDIR
  #else
  #define IS_DIR_SEP(C) ((C) == '/')
  #endif
  
  
  
  //==============================================================================
  // Saving & Loading Seeds
  //==============================================================================
  
  
  uint64_t *loadSavedSeeds(const char *fnam, uint64_t *scnt)
  {
      FILE *fp = fopen(fnam, "r");
  
      uint64_t seed, i;
      uint64_t *baseSeeds;
  
      if (fp == NULL)
          return NULL;
  
      *scnt = 0;
  
      while (!feof(fp))
      {
          if (fscanf(fp, "%" PRId64, (int64_t*)&seed) == 1) (*scnt)++;
          else while (!feof(fp) && fgetc(fp) != '\n');
      }
  
      if (*scnt == 0)
          return NULL;
  
      baseSeeds = (uint64_t*) calloc(*scnt, sizeof(*baseSeeds));
  
      rewind(fp);
  
      for (i = 0; i < *scnt && !feof(fp);)
      {
          if (fscanf(fp, "%" PRId64, (int64_t*)&baseSeeds[i]) == 1) i++;
          else while (!feof(fp) && fgetc(fp) != '\n');
      }
  
      fclose(fp);
  
      return baseSeeds;
  }
  
  
  
  //==============================================================================
  // Finding Structure Positions
  //==============================================================================
  
  
  void setAttemptSeed(uint64_t *s, int cx, int cz)
  {
      *s ^= (uint64_t)(cx >> 4) ^ ( (uint64_t)(cz >> 4) << 4 );
      setSeed(s, *s);
      next(s, 31);
  }
  
  uint64_t getPopulationSeed(int mc, uint64_t ws, int x, int z)
  {
      uint64_t s;
      uint64_t a, b;
  
      setSeed(&s, ws);
      a = nextLong(&s);
      b = nextLong(&s);
      if (mc >= MC_1_13)
      {
          a |= 1; b |= 1;
      }
      else
      {
          a = (int64_t)a / 2 * 2 + 1;
          b = (int64_t)b / 2 * 2 + 1;
      }
      return (x * a + z * b) ^ ws;
  }
  
  
  int getStructureConfig(int structureType, int mc, StructureConfig *sconf)
  {
      switch (structureType)
      {
      case Feature:
          *sconf = FEATURE_CONFIG;
          return mc <= MC_1_12;
      case Desert_Pyramid:
          *sconf = mc <= MC_1_12 ? DESERT_PYRAMID_CONFIG_112 : DESERT_PYRAMID_CONFIG;
          return mc >= MC_1_3;
      case Jungle_Pyramid:
          *sconf = mc <= MC_1_12 ? JUNGLE_PYRAMID_CONFIG_112 : JUNGLE_PYRAMID_CONFIG;
          return mc >= MC_1_3;
      case Swamp_Hut:
          *sconf = mc <= MC_1_12 ? SWAMP_HUT_CONFIG_112 : SWAMP_HUT_CONFIG;
          return mc >= MC_1_4;
      case Igloo:
          *sconf = mc <= MC_1_12 ? IGLOO_CONFIG_112 : IGLOO_CONFIG;
          return mc >= MC_1_9;
      case Village:
          *sconf = VILLAGE_CONFIG;
          return 1;
      case Ocean_Ruin:
          *sconf = mc <= MC_1_15 ? OCEAN_RUIN_CONFIG_115 : OCEAN_RUIN_CONFIG;
          return mc >= MC_1_13;
      case Shipwreck:
          *sconf = mc <= MC_1_15 ? SHIPWRECK_CONFIG_115 : SHIPWRECK_CONFIG;
          return mc >= MC_1_13;
      case Ruined_Portal:
          *sconf = RUINED_PORTAL_CONFIG;
          return mc >= MC_1_16;
      case Ruined_Portal_N:
          *sconf = RUINED_PORTAL_N_CONFIG;
          return mc >= MC_1_16;
      case Monument:
          *sconf = MONUMENT_CONFIG;
          return mc >= MC_1_8;
      case End_City:
          *sconf = END_CITY_CONFIG;
          return mc >= MC_1_9;
      case Mansion:
          *sconf = MANSION_CONFIG;
          return mc >= MC_1_11;
      case Outpost:
          *sconf = OUTPOST_CONFIG;
          return mc >= MC_1_14;
      case Treasure:
          *sconf = TREASURE_CONFIG;
          return mc >= MC_1_13;
      case Mineshaft:
          *sconf = MINESHAFT_CONFIG;
          return 1;
      case Fortress:
          *sconf = mc <= MC_1_15 ? FORTRESS_CONFIG_115 : FORTRESS_CONFIG;
          return 1;
      case Bastion:
          *sconf = BASTION_CONFIG;
          return mc >= MC_1_16;
      case End_Gateway:
          *sconf = END_GATEWAY_CONFIG;
          return mc >= MC_1_13;
      default:
          memset(sconf, 0, sizeof(StructureConfig));
          return 0;
      }
  }
  
  
  // like getFeaturePos(), but modifies the rng seed
  static inline
  void getRegPos(Pos *p, uint64_t *s, int rx, int rz, StructureConfig sc)
  {
      setSeed(s, rx*341873128712ULL + rz*132897987541ULL + *s + sc.salt);
      p->x = (int)(((uint64_t)rx * sc.regionSize + nextInt(s, sc.chunkRange)) << 4);
      p->z = (int)(((uint64_t)rz * sc.regionSize + nextInt(s, sc.chunkRange)) << 4);
  }
  
  int getStructurePos(int structureType, int mc, uint64_t seed, int regX, int regZ, Pos *pos)
  {
      StructureConfig sconf;
  #if STRUCT_CONFIG_OVERRIDE
      if (!getStructureConfig_override(structureType, mc, &sconf))
  #else
      if (!getStructureConfig(structureType, mc, &sconf))
  #endif
      {
          return 0;
      }
  
      switch (structureType)
      {
      case Feature:
      case Desert_Pyramid:
      case Jungle_Pyramid:
      case Swamp_Hut:
      case Igloo:
      case Village:
      case Ocean_Ruin:
      case Shipwreck:
      case Ruined_Portal:
      case Ruined_Portal_N:
          *pos = getFeaturePos(sconf, seed, regX, regZ);
          return 1;
  
      case Monument:
      case Mansion:
          *pos = getLargeStructurePos(sconf, seed, regX, regZ);
          return 1;
  
      case End_City:
          *pos = getLargeStructurePos(sconf, seed, regX, regZ);
          return (pos->x*(int64_t)pos->x + pos->z*(int64_t)pos->z) >= 1008*1008LL;
  
      case Outpost:
          *pos = getFeaturePos(sconf, seed, regX, regZ);
          setAttemptSeed(&seed, (pos->x) >> 4, (pos->z) >> 4);
          return nextInt(&seed, 5) == 0;
  
      case Treasure:
          pos->x = (int)( ((uint32_t)regX << 4) + 9 );
          pos->z = (int)( ((uint32_t)regZ << 4) + 9 );
          seed = regX*341873128712ULL + regZ*132897987541ULL + seed + sconf.salt;
          setSeed(&seed, seed);
          return nextFloat(&seed) < 0.01;
  
      case Mineshaft:
          return getMineshafts(mc, seed, regX, regZ, regX, regZ, pos, 1);
  
      case Fortress:
          if (mc < MC_1_16) {
              setAttemptSeed(&seed, regX << 4, regZ << 4);
              int valid = nextInt(&seed, 3) == 0;
              pos->x = (int)((((uint64_t)regX << 4) + nextInt(&seed,8) + 4) << 4);
              pos->z = (int)((((uint64_t)regZ << 4) + nextInt(&seed,8) + 4) << 4);
              return valid;
          } else {
              getRegPos(pos, &seed, regX, regZ, sconf);
              return nextInt(&seed, 5) < 2;
          }
  
      case Bastion:
          getRegPos(pos, &seed, regX, regZ, sconf);
          return nextInt(&seed, 5) >= 2;
  
      case End_Gateway:
          pos->x = (int)( ((uint32_t)regX << 4) );
          pos->z = (int)( ((uint32_t)regZ << 4) );
          setSeed(&seed, getPopulationSeed(mc, seed, pos->x, pos->z) + sconf.salt);
          if (mc <= MC_1_16) {
              if (nextInt(&seed, 700) != 0)
                  return 0;
          } else {
              if (nextFloat(&seed) >= 1.0/700)
                  return 0;
          }
          pos->x += nextInt(&seed, 16);
          pos->z += nextInt(&seed, 16);
          return 1;
  
      default:
          fprintf(stderr,
                  "ERR getStructurePos: unsupported structure type %d\n", structureType);
          exit(-1);
      }
      return 0;
  }
  
  
  int getMineshafts(int mc, uint64_t seed, int cx0, int cz0, int cx1, int cz1,
          Pos *out, int nout)
  {
      uint64_t s;
      setSeed(&s, seed);
      uint64_t a = nextLong(&s);
      uint64_t b = nextLong(&s);
      int i, j;
      int n = 0;
  
      for (i = cx0; i <= cx1; i++)
      {
          uint64_t aix = i * a ^ seed;
  
          for (j = cz0; j <= cz1; j++)
          {
              setSeed(&s, aix ^ j * b);
  
              if (mc >= MC_1_13)
              {
                  if U(nextDouble(&s) < 0.004)
                  {
                      if (out && n < nout)
                      {
                          out[n].x = (int)((uint32_t)i << 4);
                          out[n].z = (int)((uint32_t)j << 4);
                      }
                      n++;
                  }
              }
              else
              {
                  skipNextN(&s, 1);
                  if U(nextDouble(&s) < 0.004)
                  {
                      int d = i;
                      if (-i > d) d = -i;
                      if (+j > d) d = +j;
                      if (-j > d) d = -j;
                      if (d >= 80 || nextInt(&s, 80) < d)
                      {
                          if (out && n < nout)
                          {
                              out[n].x = (int)((uint32_t)i << 4);
                              out[n].z = (int)((uint32_t)j << 4);
                          }
                          n++;
                      }
                  }
              }
          }
      }
  
      return n;
  }
  
  
  
  //==============================================================================
  // Multi-Structure Checks
  //==============================================================================
  
  // TODO: accurate seed testers for two or three structures in range
  
  
  
  static int blocksInRange(Pos *p, int n, int x, int z, int ax, int az, double rsq)
  {
      int i, cnt;
  
      cnt = 0;
      for (i = 0; i < n; i++)
      {
          double dx = p[i].x - x;
          double dz = p[i].z - z;
          int px, pz;
  
          for (px = 0; px < ax; px++)
          {
              for (pz = 0; pz < az; pz++)
              {
                  double ddx = px + dx;
                  double ddz = pz + dz;
                  cnt += (ddx*ddx + ddz*ddz <= rsq);
              }
          }
      }
      return cnt;
  }
  
  STRUCT(afk_meta_t)
  {
      Pos *p;
      int n;
      int *buf;
      int x0, z0, w, h, ax, az;
      double rsq;
      int best;
      int sumn;
      int64_t sumx, sumz;
  };
  
  static void checkAfkDist(afk_meta_t *d, int x, int z)
  {
      if (x < 0 || z < 0 || x >= d->w || z >= d->h)
          return;
      if (d->buf[z*d->w+x])
          return;
  
      int q = blocksInRange(d->p, d->n, x+d->x0, z+d->z0, d->ax, d->az, d->rsq);
      d->buf[z*d->w+x] = q;
      if (q >= d->best)
      {
          if (q > d->best)
          {
              d->best = q;
              d->sumn = 1;
              d->sumx = d->x0+x;
              d->sumz = d->z0+z;
          }
          else
          {
              d->sumn += 1;
              d->sumx += d->x0+x;
              d->sumz += d->z0+z;
          }
          checkAfkDist(d, x, z-1);
          checkAfkDist(d, x, z+1);
          checkAfkDist(d, x-1, z);
          checkAfkDist(d, x+1, z);
          checkAfkDist(d, x-1, z-1);
          checkAfkDist(d, x-1, z+1);
          checkAfkDist(d, x+1, z-1);
          checkAfkDist(d, x+1, z+1);
      }
  }
  
  
  Pos getOptimalAfk(Pos p[4], int ax, int ay, int az, int *spcnt)
  {
      int64_t minX = INT_MAX, minZ = INT_MAX, maxX = INT_MIN, maxZ = INT_MIN;
      int64_t w, h, i;
  
      for (i = 0; i < 4; i++)
      {
          if (p[i].x < minX) minX = p[i].x;
          if (p[i].z < minZ) minZ = p[i].z;
          if (p[i].x > maxX) maxX = p[i].x;
          if (p[i].z > maxZ) maxZ = p[i].z;
      }
  
      minX += ax/2;
      minZ += az/2;
      maxX += ax/2;
      maxZ += az/2;
  
      double rsq = 128.0*128.0 - ay*ay/4.0;
  
      w = maxX - minX;
      h = maxZ - minZ;
      Pos afk = {p[0].x + ax / 2, p[0].z + az / 2};
      int cnt = ax*az;
  
      afk_meta_t d;
      d.p = p;
      d.n = 4;
      d.buf = (int*) calloc(w*h, sizeof(int));
      d.x0 = minX;
      d.z0 = minZ;
      d.w = w;
      d.h = h;
      d.ax = ax;
      d.az = az;
      d.rsq = rsq;
  
      int v[6];
      Pos dsp[6] = {
          {(p[0].x + p[2].x) / 2, (p[0].z + p[2].z) / 2},
          {(p[1].x + p[3].x) / 2, (p[1].z + p[3].z) / 2},
          {(p[0].x + p[1].x) / 2, (p[0].z + p[1].z) / 2},
          {(p[2].x + p[3].x) / 2, (p[2].z + p[3].z) / 2},
          {(p[0].x + p[3].x) / 2, (p[0].z + p[3].z) / 2},
          {(p[1].x + p[2].x) / 2, (p[1].z + p[2].z) / 2},
      };
      for (i = 0; i < 6; i++)
          v[i] = blocksInRange(p, 4, dsp[i].x, dsp[i].z, ax, az, rsq);
  
      for (i = 0; i < 6; i++)
      {
          // pick out the highest
          int j, jmax = 0, vmax = 0;
          for (j = 0; j < 6; j++)
          {
              if (v[j] > vmax)
              {
                  jmax = j;
                  vmax = v[j];
              }
          }
          if (vmax <= ax*az)  // highest is less or equal to a single structure
              break;
  
          d.best = vmax;
          d.sumn = 0;
          d.sumx = 0;
          d.sumz = 0;
          checkAfkDist(&d, dsp[jmax].x - d.x0, dsp[jmax].z - d.z0);
          if (d.best > cnt)
          {
              cnt = d.best;
              afk.x = (int) round(d.sumx / (double)d.sumn);
              afk.z = (int) round(d.sumz / (double)d.sumn);
              if (cnt >= 3*ax*az)
                  break;
          }
          v[jmax] = 0;
      }
  
      if (spcnt)
          *spcnt = cnt;
  
      free(d.buf);
  
      return afk;
  }
  
  
  #define MAX_PATHLEN 4096
  
  STRUCT(linked_seeds_t)
  {
      uint64_t seeds[100];
      size_t len;
      linked_seeds_t *next;
  };
  
  STRUCT(threadinfo_t)
  {
      // seed range
      uint64_t start, end;
      const uint64_t *lowBits;
      int lowBitCnt;
      int lowBitN;
  
      // testing function
      int (*check)(uint64_t, void*);
      void *data;
  
      // output
      char path[MAX_PATHLEN];
      FILE *fp;
      linked_seeds_t ls;
  };
  
  
  static int mkdirp(char *path)
  {
      int err = 0, len = strlen(path);
      char *p = path;
  
  #if defined(_WIN32)
      if (p[1] == ':') p += 2;
  #endif
      while (IS_DIR_SEP(*p)) p++;
  
      while (!err && p < path+len)
      {
          char *q = p;
          while (*q && !IS_DIR_SEP(*q))
              q++;
  
          if (p != path) p[-1] = '/';
          *q = 0;
  
          struct stat st;
          if (stat(path, &st) == -1)
              err = mkdir(path, 0773);
          else if (!S_ISDIR(st.st_mode))
              err = 1;
  
          p = q+1;
      }
  
      return err;
  }
  
  
  #ifdef USE_PTHREAD
  static void *searchAll48Thread(void *data)
  #else
  static DWORD WINAPI searchAll48Thread(LPVOID data)
  #endif
  {
  // TODO TEST:
  // lower bits with various ranges
  
      threadinfo_t *info = (threadinfo_t*)data;
  
      uint64_t seed = info->start;
      uint64_t end = info->end;
      linked_seeds_t *lp = &info->ls;
      lp->len = 0;
      lp->next = NULL;
  
      if (info->lowBits)
      {
          uint64_t hstep = 1ULL << info->lowBitN;
          uint64_t hmask = ~(hstep - 1);
          uint64_t mid;
          int idx;
  
          mid = info->start & hmask;
          for (idx = 0; (seed = mid | info->lowBits[idx]) < info->start; idx++);
  
          while (seed <= end)
          {
              if U(info->check(seed, info->data))
              {
                  if (info->fp)
                  {
                      fprintf(info->fp, "%" PRId64"\n", (int64_t)seed);
                      fflush(info->fp);
                  }
                  else
                  {
                      lp->seeds[lp->len] = seed;
                      lp->len++;
                      if (lp->len >= sizeof(lp->seeds)/sizeof(uint64_t))
                      {
                          linked_seeds_t *n =
                              (linked_seeds_t*) malloc(sizeof(linked_seeds_t));
                          if (n == NULL)
                              exit(1);
                          lp->next = n;
                          lp = n;
                          lp->len = 0;
                          lp->next = NULL;
                      }
                  }
              }
  
              idx++;
              if (idx >= info->lowBitCnt)
              {
                  idx = 0;
                  mid += hstep;
              }
  
              seed = mid | info->lowBits[idx];
          }
      }
      else
      {
          while (seed <= end)
          {
              if U(info->check(seed, info->data))
              {
                  if (info->fp)
                  {
                      fprintf(info->fp, "%" PRId64"\n", (int64_t)seed);
                      fflush(info->fp);
                  }
                  else
                  {
                      lp->seeds[lp->len] = seed;
                      lp->len++;
                      if (lp->len >= sizeof(lp->seeds)/sizeof(uint64_t))
                      {
                          linked_seeds_t *n =
                              (linked_seeds_t*) malloc(sizeof(linked_seeds_t));
                          if (n == NULL)
                              exit(1);
                          lp->next = n;
                          lp = n;
                          lp->len = 0;
                          lp->next = NULL;
                      }
                  }
              }
              seed++;
          }
      }
  
  #ifdef USE_PTHREAD
      pthread_exit(NULL);
  #endif
      return 0;
  }
  
  
  int searchAll48(
          uint64_t **         seedbuf,
          uint64_t *          buflen,
          const char *        path,
          int                 threads,
          const uint64_t *    lowBits,
          int                 lowBitCnt,
          int                 lowBitN,
          int (*check)(uint64_t s48, void *data),
          void *              data
          )
  {
      threadinfo_t *info = (threadinfo_t*) malloc(threads* sizeof(*info));
      thread_id_t *tids = (thread_id_t*) malloc(threads* sizeof(*tids));
      int i, t;
      int err = 0;
  
      if (path)
      {
          size_t pathlen = strlen(path);
          char dpath[MAX_PATHLEN];
  
          // split path into directory and file and create missing directories
          if (pathlen + 8 >= sizeof(dpath))
              goto L_err;
          strcpy(dpath, path);
  
          for (i = pathlen-1; i >= 0; i--)
          {
              if (IS_DIR_SEP(dpath[i]))
              {
                  dpath[i] = 0;
                  if (mkdirp(dpath))
                      goto L_err;
                  break;
              }
          }
      }
      else if (seedbuf == NULL || buflen == NULL)
      {
          // no file and no buffer return: no output possible
          goto L_err;
      }
  
      // prepare the thread info and load progress if present
      for (t = 0; t < threads; t++)
      {
          info[t].start = (t * (MASK48+1) / threads);
          info[t].end = ((t+1) * (MASK48+1) / threads - 1);
          info[t].lowBits = lowBits;
          info[t].lowBitCnt = lowBitCnt;
          info[t].lowBitN = lowBitN;
          info[t].check = check;
          info[t].data = data;
  
          if (path)
          {
              // progress file of this thread
              snprintf(info[t].path, sizeof(info[t].path), "%s.part%d", path, t);
              FILE *fp = fopen(info[t].path, "a+");
              if (fp == NULL)
                  goto L_err;
  
              int c, nnl = 0;
              char buf[32];
  
              // find the last newline
              for (i = 1; i < 32; i++)
              {
                  if (fseek(fp, -i, SEEK_END)) break;
                  c = fgetc(fp);
                  if (c <= 0 || (nnl && c == '\n')) break;
                  nnl |= (c != '\n');
              }
  
              if (i < 32 && !fseek(fp, 1-i, SEEK_END) && fread(buf, i-1, 1, fp) > 0)
              {
                  // read the last entry, and replace the start seed accordingly
                  int64_t lentry;
                  if (sscanf(buf, "%" PRId64, &lentry) == 1)
                  {
                      info[t].start = lentry;
                      printf("Continuing thread %d at seed %" PRId64 "\n",
                          t, lentry);
                  }
              }
  
              fseek(fp, 0, SEEK_END);
              info[t].fp = fp;
          }
          else
          {
              info[t].path[0] = 0;
              info[t].fp = NULL;
          }
      }
  
  
      // run the threads
  #ifdef USE_PTHREAD
  
      for (t = 0; t < threads; t++)
      {
          pthread_create(&tids[t], NULL, searchAll48Thread, (void*)&info[t]);
      }
  
      for (t = 0; t < threads; t++)
      {
          pthread_join(tids[t], NULL);
      }
  
  #else
  
      for (t = 0; t < threads; t++)
      {
          tids[t] = CreateThread(NULL, 0, searchAll48Thread,
              (LPVOID)&info[t], 0, NULL);
      }
  
      WaitForMultipleObjects(threads, tids, TRUE, INFINITE);
  
  #endif
  
      if (path)
      {
          // merge partial files
          FILE *fp = fopen(path, "w");
          if (fp == NULL)
              goto L_err;
  
          for (t = 0; t < threads; t++)
          {
              rewind(info[t].fp);
  
              char buffer[4097];
              size_t n;
              while ((n = fread(buffer, sizeof(char), 4096, info[t].fp)))
              {
                  if (!fwrite(buffer, sizeof(char), n, fp))
                  {
                      fclose(fp);
                      goto L_err;
                  }
              }
  
              fclose(info[t].fp);
              remove(info[t].path);
          }
  
          fclose(fp);
  
          if (seedbuf && buflen)
          {
              *seedbuf = loadSavedSeeds(path, buflen);
          }
      }
      else
      {
          // merge linked seed buffers
          *buflen = 0;
  
          for (t = 0; t < threads; t++)
          {
              linked_seeds_t *lp = &info[t].ls;
              do
              {
                  *buflen += lp->len;
                  lp = lp->next;
              }
              while (lp);
          }
  
          *seedbuf = (uint64_t*) malloc((*buflen) * sizeof(uint64_t));
          if (*seedbuf == NULL)
              exit(1);
  
          i = 0;
          for (t = 0; t < threads; t++)
          {
              linked_seeds_t *lp = &info[t].ls;
              do
              {
                  memcpy(*seedbuf + i, lp->seeds, lp->len * sizeof(uint64_t));
                  i += lp->len;
                  linked_seeds_t *tmp = lp;
                  lp = lp->next;
                  if (tmp != &info[t].ls)
                      free(tmp);
              }
              while (lp);
          }
      }
  
      if (0)
  L_err:
          err = 1;
  
      free(tids);
      free(info);
  
      return err;
  }
  
  static inline
  int scanForQuadBits(const StructureConfig sconf, int radius, uint64_t s48,
          uint64_t lbit, int lbitn, uint64_t invB, int64_t x, int64_t z,
          int64_t w, int64_t h, Pos *qplist, int n)
  {
      const uint64_t m = (1ULL << lbitn);
      const uint64_t A = 341873128712ULL;
      // for lbitn=20: invB = 132477LL;
  
      if (n < 1)
          return 0;
      lbit &= m-1;
  
      int64_t i, j;
      int cnt = 0;
      for (i = x; i <= x+w; i++)
      {
          uint64_t sx = s48 + A * i;
          j = (z & ~(m-1)) | ((lbit - sx) * invB & (m-1));
          if (j < z)
              j += m;
          for (; j <= z+h; j += m)
          {
              uint64_t sp = moveStructure(s48, -i, -j);
              if ((sp & (m-1)) != lbit)
                  continue;
  
              if (isQuadBase(sconf, sp, radius))
              {
                  qplist[cnt].x = i;
                  qplist[cnt].z = j;
                  cnt++;
                  if (cnt >= n)
                      return cnt;
              }
          }
      }
  
      return cnt;
  }
  
  int scanForQuads(
          const StructureConfig sconf, int radius, uint64_t s48,
          const uint64_t *lowBits, int lowBitCnt, int lowBitN, uint64_t salt,
          int x, int z, int w, int h, Pos *qplist, int n)
  {
      int i, cnt = 0;
      uint64_t invB;
      if (lowBitN == 20)
          invB = 132477ULL;
      else if (lowBitN == 48)
          invB = 211541297333629ULL;
      else
          invB = mulInv(132897987541ULL, (1ULL << lowBitN));
  
      for (i = 0; i < lowBitCnt; i++)
      {
          cnt += scanForQuadBits(sconf, radius, s48, lowBits[i]-salt, lowBitN, invB,
                  x, z, w, h, qplist+cnt, n-cnt);
          if (cnt >= n)
              break;
      }
  
      return cnt;
  }
  
  
  
  //==============================================================================
  // Checking Biomes & Biome Helper Functions
  //==============================================================================
  
  
  int getBiomeAtPos(const LayerStack *g, const Pos pos)
  {
      int *ids = allocCache(g->entry_1, 1, 1);
      genArea(g->entry_1, ids, pos.x, pos.z, 1, 1);
      int biomeID = ids[0];
      free(ids);
      return biomeID;
  }
  
  Pos findBiomePosition(
          const int mcversion,
          const Layer *l,
          int *cache,
          const int centerX,
          const int centerZ,
          const int range,
          const char *isValid,
          uint64_t *seed,
          int *passes
          )
  {
      int x1 = (centerX-range) >> 2;
      int z1 = (centerZ-range) >> 2;
      int x2 = (centerX+range) >> 2;
      int z2 = (centerZ+range) >> 2;
      int width  = x2 - x1 + 1;
      int height = z2 - z1 + 1;
      int *ids;
      int i, j, found;
  
      Pos out;
  
      if (l->scale != 4)
      {
          printf("WARN findBiomePosition: require scale = 4, but have %d.\n",
                  l->scale);
      }
  
      ids = cache ? cache : allocCache(l, width, height);
  
      genArea(l, ids, x1, z1, width, height);
  
      out.x = centerX;
      out.z = centerZ;
      found = 0;
  
      if (mcversion >= MC_1_13)
      {
          for (i = 0, j = 2; i < width*height; i++)
          {
              if (!isValid[ids[i]]) continue;
              if ((found == 0 || nextInt(seed, j++) == 0))
              {
                  out.x = (x1 + i%width) << 2;
                  out.z = (z1 + i/width) << 2;
                  found = 1;
              }
          }
          found = j - 2;
      }
      else
      {
          for (i = 0; i < width*height; i++)
          {
              if (isValid[ids[i]] && (found == 0 || nextInt(seed, found + 1) == 0))
              {
                  out.x = (x1 + i%width) << 2;
                  out.z = (z1 + i/width) << 2;
                  ++found;
              }
          }
      }
  
  
      if (cache == NULL)
      {
          free(ids);
      }
  
      if (passes != NULL)
      {
          *passes = found;
      }
  
      return out;
  }
  
  
  int areBiomesViable(
          const Layer *       l,
          int *               cache,
          const int           posX,
          const int           posZ,
          const int           radius,
          const char *        isValid
          )
  {
      int x1 = (posX - radius) >> 2;
      int z1 = (posZ - radius) >> 2;
      int x2 = (posX + radius) >> 2;
      int z2 = (posZ + radius) >> 2;
      int width = x2 - x1 + 1;
      int height = z2 - z1 + 1;
      int i;
      int *ids;
      int viable;
  
      if (l->scale != 4)
      {
          printf("WARN areBiomesViable: require scale = 4, but have %d.\n",
                  l->scale);
      }
  
      ids = cache ? cache : allocCache(l, width, height);
      viable = !genArea(l, ids, x1, z1, width, height);
  
      if (viable)
      {
          for (i = 0; i < width*height; i++)
          {
              if (!isValid[ ids[i] ])
              {
                  viable = 0;
                  break;
              }
          }
      }
  
      if (cache == NULL)
          free(ids);
      return viable;
  }
  
  
  //==============================================================================
  // Finding Strongholds and Spawn
  //==============================================================================
  
  
  const char* getValidStrongholdBiomes(int mc)
  {
      static const int strongholdBiomes[] = {
          plains, desert, mountains, forest, taiga, snowy_tundra, snowy_mountains,
          mushroom_fields, mushroom_field_shore, desert_hills, wooded_hills,
          taiga_hills, mountain_edge, jungle,jungle_hills, jungle_edge,
          stone_shore, birch_forest, birch_forest_hills, dark_forest, snowy_taiga,
          snowy_taiga_hills, giant_tree_taiga, giant_tree_taiga_hills,
          wooded_mountains, savanna, savanna_plateau, badlands,
          wooded_badlands_plateau, badlands_plateau, sunflower_plains,
          desert_lakes, gravelly_mountains, flower_forest, taiga_mountains,
          ice_spikes, modified_jungle, modified_jungle_edge, tall_birch_forest,
          tall_birch_hills, dark_forest_hills, snowy_taiga_mountains,
          giant_spruce_taiga, giant_spruce_taiga_hills,
          modified_gravelly_mountains, shattered_savanna,
          shattered_savanna_plateau, eroded_badlands,
          modified_wooded_badlands_plateau, modified_badlands_plateau,
          bamboo_jungle, bamboo_jungle_hills,
      };
  
      static char isValid115[256], isValid[256];
      unsigned int i;
  
      if (mc <= MC_1_15)
      {
          if (!isValid115[strongholdBiomes[0]])
              for (i = 0; i < sizeof(strongholdBiomes) / sizeof(int); i++)
                  isValid115[ strongholdBiomes[i] ] = 1;
          return isValid115;
      }
      else
      {   // simulate MC-199298
          if (!isValid[strongholdBiomes[0]])
              for (i = 0; i < sizeof(strongholdBiomes) / sizeof(int); i++)
                  isValid[ strongholdBiomes[i] ] = 1;
          isValid[bamboo_jungle] = 0;
          isValid[bamboo_jungle_hills] = 0;
          return isValid;
      }
  }
  
  Pos initFirstStronghold(StrongholdIter *sh, int mc, uint64_t s48)
  {
      double dist, angle;
      uint64_t rnds;
      Pos p;
  
      setSeed(&rnds, s48);
  
      angle = 2.0 * PI * nextDouble(&rnds);
      if (mc >= MC_1_9)
          dist = (4.0 * 32.0) + (nextDouble(&rnds) - 0.5) * 32 * 2.5;
      else
          dist = (1.25 + nextDouble(&rnds)) * 32.0;
  
      p.x = ((int)round(cos(angle) * dist) << 4) + 8;
      p.z = ((int)round(sin(angle) * dist) << 4) + 8;
  
      if (sh)
      {
          sh->pos.x = sh->pos.z = 0;
          sh->nextapprox = p;
          sh->index = 0;
          sh->ringnum = 0;
          sh->ringmax = 3;
          sh->ringidx = 0;
          sh->angle = angle;
          sh->dist = dist;
          sh->rnds = rnds;
          sh->mc = mc;
      }
  
      return p;
  }
  
  int nextStronghold(StrongholdIter *sh, const LayerStack *g, int *cache)
  {
      sh->pos = findBiomePosition(sh->mc, &g->layers[L_RIVER_MIX_4], cache,
          sh->nextapprox.x, sh->nextapprox.z, 112,
          getValidStrongholdBiomes(sh->mc), &sh->rnds, NULL);
  
      sh->ringidx++;
      sh->angle += 2 * PI / sh->ringmax;
  
      if (sh->ringidx == sh->ringmax)
      {
          sh->ringnum++;
          sh->ringidx = 0;
          sh->ringmax = sh->ringmax + 2*sh->ringmax / (sh->ringnum+1);
          if (sh->ringmax > 128-sh->index)
              sh->ringmax = 128-sh->index;
          sh->angle += nextDouble(&sh->rnds) * PI * 2.0;
      }
  
      if (sh->mc >= MC_1_9)
      {
          sh->dist = (4.0 * 32.0) + (6.0 * sh->ringnum * 32.0) +
              (nextDouble(&sh->rnds) - 0.5) * 32 * 2.5;
      }
      else
      {
          sh->dist = (1.25 + nextDouble(&sh->rnds)) * 32.0;
      }
  
      sh->nextapprox.x = ((int)round(cos(sh->angle) * sh->dist) << 4) + 8;
      sh->nextapprox.z = ((int)round(sin(sh->angle) * sh->dist) << 4) + 8;
      sh->index++;
  
      return (sh->mc >= MC_1_9 ? 128 : 3) - (sh->index-1);
  }
  
  int findStrongholds(const int mc, const LayerStack *g, int *cache,
          Pos *locations, uint64_t worldSeed, int maxSH, int maxRing)
  {
      const char *validStrongholdBiomes = getValidStrongholdBiomes(mc);
      int i, x, z;
      double distance;
  
      int currentRing = 0;
      int currentCount = 0;
      int perRing = 3;
      uint64_t rnd;
  
      setSeed(&rnd, worldSeed);
      double angle = nextDouble(&rnd) * PI * 2.0;
  
      const Layer *l = &g->layers[L_RIVER_MIX_4];
  
      if (mc >= MC_1_9)
      {
          if (maxSH <= 0) maxSH = 128;
  
          for (i = 0; i < maxSH; i++)
          {
              distance = (4.0 * 32.0) + (6.0 * currentRing * 32.0) +
                  (nextDouble(&rnd) - 0.5) * 32 * 2.5;
  
              x = (int)round(cos(angle) * distance);
              z = (int)round(sin(angle) * distance);
  
              locations[i] = findBiomePosition(mc, l, cache,
                      (x << 4) + 8, (z << 4) + 8, 112, validStrongholdBiomes,
                      &rnd, NULL);
  
              angle += 2 * PI / perRing;
  
              currentCount++;
              if (currentCount == perRing)
              {
                  // Current ring is complete, move to next ring.
                  currentRing++;
                  if (currentRing == maxRing)
                  {
                      i++;
                      break;
                  }
  
                  currentCount = 0;
                  perRing = perRing + 2*perRing/(currentRing+1);
                  if (perRing > 128-i)
                      perRing = 128-i;
                  angle = angle + nextDouble(&rnd) * PI * 2.0;
              }
          }
      }
      else
      {
          if (maxSH <= 0) maxSH = 3;
  
          for (i = 0; i < maxSH; i++)
          {
              distance = (1.25 + nextDouble(&rnd)) * 32.0;
  
              x = (int)round(cos(angle) * distance);
              z = (int)round(sin(angle) * distance);
  
              locations[i] = findBiomePosition(mc, l, cache,
                      (x << 4) + 8, (z << 4) + 8, 112, validStrongholdBiomes,
                      &rnd, NULL);
  
              angle += 2 * PI / 3.0;
          }
      }
  
      return i;
  }
  
  
  static double getGrassProbability(uint64_t seed, int biome, int x, int z)
  {
      (void) seed, (void) biome, (void) x, (void) z;
      // TODO: Use ChunkGeneratorOverworld.generateHeightmap for better estimate.
      // TODO: Try to determine the actual probabilities and build a statistic.
      switch (biome)
      {
      case plains:                        return 1.0;
      case mountains:                     return 0.8; // height dependent
      case forest:                        return 1.0;
      case taiga:                         return 1.0;
      case swamp:                         return 0.3; // height dependent
      case river:                         return 0.15;
      case beach:                         return 0.0;
      case snowy_tundra:                  return 0.02;
      case snowy_mountains:               return 0.02;
      case wooded_hills:                  return 1.0;
      case taiga_hills:                   return 1.0;
      case mountain_edge:                 return 1.0; // height dependent
      case jungle:                        return 1.0;
      case jungle_hills:                  return 1.0;
      case jungle_edge:                   return 1.0;
      case birch_forest:                  return 1.0;
      case birch_forest_hills:            return 1.0;
      case dark_forest:                   return 0.9;
      case snowy_taiga:                   return 0.1; // below trees
      case snowy_taiga_hills:             return 0.1; // below trees
      case giant_tree_taiga:              return 0.6;
      case giant_tree_taiga_hills:        return 0.6;
      case wooded_mountains:              return 0.2; // height dependent
      case savanna:                       return 1.0;
      case savanna_plateau:               return 0.9;
      case wooded_badlands_plateau:       return 0.0; // height dependent
      case badlands_plateau:              return 0.0; // height dependent
  
      case sunflower_plains:              return 1.0;
      case gravelly_mountains:            return 0.2;
      case flower_forest:                 return 1.0;
      case taiga_mountains:               return 1.0;
      case swamp_hills:                   return 0.9;
      case modified_jungle:               return 1.0;
      case modified_jungle_edge:          return 1.0;
      case tall_birch_forest:             return 1.0;
      case tall_birch_hills:              return 1.0;
      case dark_forest_hills:             return 0.9;
      case snowy_taiga_mountains:         return 0.1;
      case giant_spruce_taiga:            return 0.6;
      case giant_spruce_taiga_hills:      return 0.6;
      case modified_gravelly_mountains:   return 0.2;
      case shattered_savanna:             return 1.0;
      case shattered_savanna_plateau:     return 1.0;
      case bamboo_jungle:                 return 0.4;
      case bamboo_jungle_hills:           return 0.4;
      // NOTE: in rare circumstances you can get also get grassy islands that are
      // completely in ocean variants...
      default: return 0;
      }
  }
  
  
  static const char* getValidSpawnBiomes()
  {
      static const int biomesToSpawnIn[] = {forest, plains, taiga, taiga_hills, wooded_hills, jungle, jungle_hills};
      static char isValid[256];
      unsigned int i;
  
      if (!isValid[biomesToSpawnIn[0]])
          for (i = 0; i < sizeof(biomesToSpawnIn) / sizeof(int); i++)
              isValid[ biomesToSpawnIn[i] ] = 1;
  
      return isValid;
  }
  
  
  Pos getSpawn(const int mcversion, const LayerStack *g, int *cache, uint64_t worldSeed)
  {
      const char *isSpawnBiome = getValidSpawnBiomes();
      Pos spawn;
      int found;
      int i;
  
      const Layer *l = &g->layers[L_RIVER_MIX_4];
      uint64_t rnd;
  
      setSeed(&rnd, worldSeed);
      spawn = findBiomePosition(mcversion, l, cache, 0, 0, 256, isSpawnBiome,
              &rnd, &found);
  
      if (!found)
      {
          //printf("Unable to find spawn biome.\n");
          spawn.x = spawn.z = 8;
      }
  
      double accum = 1;
      double bx = 0;
      double bz = 0;
      double bn = 0;
  
      if (mcversion >= MC_1_13)
      {
          int *area = allocCache(g->entry_1, 16, 16);
          int n2 = 0;
          int n3 = 0;
          int n4 = 0;
          int n5 = -1;
  
          for (i = 0; i < 1024; i++)
          {
              if (n2 > -16 && n2 <= 16 && n3 > -16 && n3 <= 16)
              {
                  int cx = ((spawn.x >> 4) + n2) << 4;
                  int cz = ((spawn.z >> 4) + n3) << 4;
                  int x, z;
  
                  genArea(g->entry_1, area, cx, cz, 16, 16);
  
                  for (x = 0; x < 16; x++)
                  {
                      for (z = 0; z < 16; z++)
                      {
                          Pos pos = {cx+x, cz+z};
                          int biome = area[z*16 + x];
                          double gp = getGrassProbability(worldSeed, biome,
                              pos.x, pos.z);
                          if (gp == 0)
                              continue;
  
                          bx += accum * gp * pos.x;
                          bz += accum * gp * pos.z;
                          bn += accum * gp;
  
                          accum *= 1 - gp;
                          if (accum < 0.001)
                          {
                              free(area);
                              spawn.x = (int) round(bx / bn);
                              spawn.z = (int) round(bz / bn);
                              return spawn;
                          }
                      }
                  }
              }
  
              if (n2 == n3 || (n2 < 0 && n2 == - n3) || (n2 > 0 && n2 == 1 - n3))
              {
                  int n7 = n4;
                  n4 = -n5;
                  n5 = n7;
              }
              n2 += n4;
              n3 += n5;
          }
  
          free(area);
      }
      else
      {
          for (i = 0; i < 1000; i++)
          {
              int biome = getBiomeAtPos(g, spawn);
              double gp = getGrassProbability(worldSeed, biome, spawn.x, spawn.z);
  
              bx += accum * gp * spawn.x;
              bz += accum * gp * spawn.z;
              bn += accum * gp;
  
              accum *= 1 - gp;
              if (accum < 0.001)
              {
                  spawn.x = (int) round(bx / bn);
                  spawn.z = (int) round(bz / bn);
                  break;
              }
  
              spawn.x += nextInt(&rnd, 64) - nextInt(&rnd, 64);
              spawn.z += nextInt(&rnd, 64) - nextInt(&rnd, 64);
          }
      }
  
      return spawn;
  }
  
  
  Pos estimateSpawn(const int mcversion, const LayerStack *g, int *cache, uint64_t worldSeed)
  {
      const char *isSpawnBiome = getValidSpawnBiomes();
      Pos spawn;
      int found;
  
      const Layer *l = &g->layers[L_RIVER_MIX_4];
      uint64_t rnd;
      setSeed(&rnd, worldSeed);
      spawn = findBiomePosition(mcversion, l, cache, 0, 0, 256, isSpawnBiome,
              &rnd, &found);
  
      if (!found)
      {
          spawn.x = spawn.z = 8;
      }
  
      if (mcversion >= MC_1_13)
      {
          spawn.x &= ~0xf;
          spawn.z &= ~0xf;
      }
  
      return spawn;
  }
  
  
  
  //==============================================================================
  // Validating Structure Positions
  //==============================================================================
  
  
  int isViableFeatureBiome(int mc, int structureType, int biomeID)
  {
      switch (structureType)
      {
      case Desert_Pyramid:
          return biomeID == desert || biomeID == desert_hills;
  
      case Jungle_Pyramid:
          return (biomeID == jungle || biomeID == jungle_hills ||
                  biomeID == bamboo_jungle || biomeID == bamboo_jungle_hills);
  
      case Swamp_Hut:
          return biomeID == swamp;
  
      case Igloo:
          if (mc < MC_1_9) return 0;
          return biomeID == snowy_tundra || biomeID == snowy_taiga;
  
      case Ocean_Ruin:
          if (mc < MC_1_13) return 0;
          return isOceanic(biomeID);
  
      case Shipwreck:
          if (mc < MC_1_13) return 0;
          return isOceanic(biomeID) || biomeID == beach || biomeID == snowy_beach;
  
      case Ruined_Portal:
      case Ruined_Portal_N:
          return mc >= MC_1_16;
  
      case Treasure:
          if (mc < MC_1_13) return 0;
          return biomeID == beach || biomeID == snowy_beach;
  
      case Mineshaft:
          return isOverworld(mc, biomeID);
  
      case Monument:
          if (mc < MC_1_8) return 0;
          return isDeepOcean(biomeID);
  
      case Outpost:
          if (mc < MC_1_14) return 0;
          // fall through
      case Village:
          if (biomeID == plains || biomeID == desert || biomeID == savanna)
              return 1;
          if (mc >= MC_1_10 && biomeID == taiga)
              return 1;
          if (mc >= MC_1_14 && biomeID == snowy_tundra)
              return 1;
          return 0;
  
      case Mansion:
          if (mc < MC_1_11) return 0;
          return biomeID == dark_forest || biomeID == dark_forest_hills;
  
      case Fortress:
          return (biomeID == nether_wastes || biomeID == soul_sand_valley ||
                  biomeID == warped_forest || biomeID == crimson_forest ||
                  biomeID == basalt_deltas);
  
      case Bastion:
          if (mc < MC_1_16) return 0;
          return (biomeID == nether_wastes || biomeID == soul_sand_valley ||
                  biomeID == warped_forest || biomeID == crimson_forest);
  
      case End_City:
          if (mc < MC_1_9) return 0;
          return biomeID == end_midlands || biomeID == end_highlands;
  
      case End_Gateway:
          if (mc < MC_1_13) return 0;
          return biomeID == end_highlands;
  
      default:
          fprintf(stderr,
                  "isViableFeatureBiome: not implemented for structure type %d.\n",
                  structureType);
          exit(1);
      }
      return 0;
  }
  
  static const char *getValidMonumentBiomes1()
  {
      static const int oceanMonumentBiomeList1[] =
      {
              ocean, deep_ocean, river, frozen_river,
              frozen_ocean, deep_frozen_ocean, cold_ocean, deep_cold_ocean,
              lukewarm_ocean, deep_lukewarm_ocean, warm_ocean, deep_warm_ocean
      };
      static char isValid[256];
      unsigned int i;
  
      if (!isValid[oceanMonumentBiomeList1[0]])
          for (i = 0; i < sizeof(oceanMonumentBiomeList1) / sizeof(int); i++)
              isValid[ oceanMonumentBiomeList1[i] ] = 1;
  
      return isValid;
  }
  
  static const char *getValidMonumentBiomes2()
  {
      static const int oceanMonumentBiomeList2[] =
      {
              deep_frozen_ocean, deep_cold_ocean, deep_ocean,
              deep_lukewarm_ocean, deep_warm_ocean
      };
      static char isValid[256];
      unsigned int i;
  
      if (!isValid[oceanMonumentBiomeList2[0]])
          for (i = 0; i < sizeof(oceanMonumentBiomeList2) / sizeof(int); i++)
              isValid[ oceanMonumentBiomeList2[i] ] = 1;
  
      return isValid;
  }
  
  static const char *getValidMansionBiomes()
  {
      static const int mansionBiomeList[] = {dark_forest, dark_forest+128};
      static char isValid[256];
      unsigned int i;
  
      if (!isValid[mansionBiomeList[0]])
          for (i = 0; i < sizeof(mansionBiomeList) / sizeof(int); i++)
              isValid[ mansionBiomeList[i] ] = 1;
  
      return isValid;
  }
  
  
  static int mapViableBiome(const Layer * l, int * out, int x, int z, int w, int h)
  {
      int err = mapBiome(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      int styp = ((const int*) l->data)[0];
      int i, j;
  
      for (j = 0; j < h; j++)
      {
          for (i = 0; i < w; i++)
          {
              int biomeID = out[i + w*j];
              switch (styp)
              {
              case Desert_Pyramid:
                  if (biomeID == desert || isMesa(biomeID))
                      return 0;
                  break;
              case Jungle_Pyramid:
                  if (biomeID == jungle)
                      return 0;
                  break;
              case Swamp_Hut:
                  if (biomeID == swamp)
                      return 0;
                  break;
              case Igloo:
                  if (biomeID == snowy_tundra || biomeID == snowy_taiga)
                      return 0;
                  break;
              case Treasure:
                  if (isOceanic(biomeID))
                      return 0;
                  break;
              case Ocean_Ruin:
              case Shipwreck:
              case Monument:
                  if (isOceanic(biomeID))
                      return 0;
                  break;
              case Mansion:
                  if (biomeID == dark_forest)
                      return 0;
                  break;
              default:
                  return 0;
              }
          }
      }
  
      return 1; // required biomes not found: set err status to stop generator
  }
  
  static int mapViableShore(const Layer * l, int * out, int x, int z, int w, int h)
  {
      int err = mapShore(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      int styp = ((const int*) l->data)[0];
      int mc   = ((const int*) l->data)[1];
      int i, j;
  
      for (j = 0; j < h; j++)
      {
          for (i = 0; i < w; i++)
          {
              int biomeID = out[i + w*j];
              switch (styp)
              {
              case Desert_Pyramid:
              case Jungle_Pyramid:
              case Swamp_Hut:
              case Igloo:
              case Ocean_Ruin:
              case Shipwreck:
              case Village:
              case Monument:
              case Mansion:
              case Treasure:
                  if (isViableFeatureBiome(mc, styp, biomeID))
                      return 0;
                  break;
  
              default:
                  return 0;
              }
          }
      }
  
      return 1;
  }
  
  
  int isViableStructurePos(int structureType, int mc, LayerStack *g,
          uint64_t seed, int blockX, int blockZ)
  {
      int *ids = NULL;
      Layer *l;
      int viable = 0;
  
      int64_t chunkX = blockX >> 4;
      int64_t chunkZ = blockZ >> 4;
  
      // Structures are positioned at the chunk origin, but the biome check is
      // performed near the middle of the chunk [(9,9) in 1.13, TODO: check 1.7]
      // In 1.16 the biome check is always performed at (2,2) with layer scale=4.
      int biomeX, biomeZ;
  
      Layer lbiome = g->layers[L_BIOME_256];
      Layer lshore = g->layers[L_SHORE_16];
  
      int data[2] = { structureType, mc };
  
      g->layers[L_BIOME_256].data = (void*) data;
      g->layers[L_BIOME_256].getMap = mapViableBiome;
      g->layers[L_SHORE_16].data = (void*) data;
      g->layers[L_SHORE_16].getMap = mapViableShore;
  
      switch (structureType)
      {
      case Ocean_Ruin:
      case Shipwreck:
      case Treasure:
          if (mc < MC_1_13) goto L_not_viable;
          goto L_feature;
      case Igloo:
          if (mc < MC_1_9) goto L_not_viable;
          goto L_feature;
      case Desert_Pyramid:
      case Jungle_Pyramid:
      case Swamp_Hut:
  L_feature:
          if (mc < MC_1_16)
          {
              l = &g->layers[L_VORONOI_ZOOM_1];
              biomeX = (chunkX << 4) + 9;
              biomeZ = (chunkZ << 4) + 9;
          }
          else
          {   // NOTE: L_RIVER_MIX_4 skips the ocean types, should be fine for
              // ocean ruins and ship wrecks.
              l = &g->layers[L_RIVER_MIX_4];
              biomeX = (chunkX << 2) + 2;
              biomeZ = (chunkZ << 2) + 2;
          }
          setLayerSeed(l, seed);
          ids = allocCache(l, 1, 1);
          if (genArea(l, ids, biomeX, biomeZ, 1, 1))
              goto L_not_viable;
          if (!isViableFeatureBiome(mc, structureType, ids[0]))
              goto L_not_viable;
          goto L_viable;
  
      case Village:
          l = &g->layers[L_RIVER_MIX_4];
          biomeX = (chunkX << 2) + 2;
          biomeZ = (chunkZ << 2) + 2;
          setLayerSeed(l, seed);
          ids = allocCache(l, 1, 1);
          if (genArea(l, ids, biomeX, biomeZ, 1, 1))
              goto L_not_viable;
          if (!isViableFeatureBiome(mc, structureType, ids[0]))
              goto L_not_viable;
          viable = ids[0]; // biome for viablility value as it may be useful for further analysis
          goto L_viable;
  
      case Outpost:
      {
          if (mc < MC_1_14)
              goto L_not_viable;
          uint64_t rnd = seed;
          setAttemptSeed(&rnd, chunkX, chunkZ);
          if (nextInt(&rnd, 5) != 0)
              goto L_not_viable;
          if (mc < MC_1_16)
          {
              l = &g->layers[L_VORONOI_ZOOM_1];
              biomeX = (chunkX << 4) + 9;
              biomeZ = (chunkZ << 4) + 9;
          }
          else
          {   // NOTE: this skips the ocean type check
              l = &g->layers[L_RIVER_MIX_4];
              biomeX = (chunkX << 2) + 2;
              biomeZ = (chunkZ << 2) + 2;
          }
          setLayerSeed(l, seed);
          ids = allocCache(l, 1, 1);
          if (genArea(l, ids, biomeX, biomeZ, 1, 1))
              goto L_not_viable;
          if (!isViableFeatureBiome(mc, structureType, ids[0]))
              goto L_not_viable;
          // look for villages within 10 chunks
          int cx0 = (chunkX-10), cx1 = (chunkX+10);
          int cz0 = (chunkZ-10), cz1 = (chunkZ+10);
          int rx, rz;
          StructureConfig vilconf;
          if (!getStructureConfig(Village, mc, &vilconf))
              goto L_not_viable;
          for (rz = cz0 >> 5; rz <= cz1 >> 5; rz++)
          {
              for (rx = cx0 >> 5; rx <= cx1 >> 5; rx++)
              {
                  Pos p = getFeaturePos(vilconf, seed, rx, rz);
                  int cx = p.x >> 4, cz = p.z >> 4;
                  if (cx >= cx0 && cx <= cx1 && cz >= cz0 && cz <= cz1)
                  {
                      if (mc >= MC_1_16)
                          goto L_not_viable;
                      if (isViableStructurePos(Village, mc, g, seed, p.x, p.z))
                          goto L_not_viable;
                      goto L_viable;
                  }
              }
          }
          goto L_viable;
      }
  
      case Monument:
          if (mc < MC_1_8)
              goto L_not_viable;
          else if (mc == MC_1_8)
          {   // In 1.8 monuments require only a single deep ocean block.
              l = g->entry_1;
              setLayerSeed(l, seed);
              ids = allocCache(l, 1, 1);
              if (genArea(l, ids, (chunkX << 4) + 8, (chunkZ << 4) + 8, 1, 1))
                  goto L_not_viable;
          }
          else
          {   // Monuments require two viability checks with the ocean layer
              // branch => worth checking for potential deep ocean beforehand.
              l = &g->layers[L_SHORE_16];
              setLayerSeed(l, seed);
              ids = allocCache(l, 1, 1);
              if (genArea(l, ids, chunkX, chunkZ, 1, 1))
                  goto L_not_viable;
          }
          if (!isDeepOcean(ids[0]))
              goto L_not_viable;
          if (mc >= MC_1_13)
              l = &g->layers[L13_OCEAN_MIX_4];
          else
              l = &g->layers[L_RIVER_MIX_4];
          biomeX = (chunkX << 4) + 8; // areBiomesViable expects block positions
          biomeZ = (chunkZ << 4) + 8;
          setLayerSeed(l, seed);
          if (mc < MC_1_9 || areBiomesViable(l, NULL, biomeX, biomeZ, 16, getValidMonumentBiomes2()))
              if (areBiomesViable(l, NULL, biomeX, biomeZ, 29, getValidMonumentBiomes1()))
                  goto L_viable;
          goto L_not_viable;
  
      case Mansion:
          if (mc < MC_1_11)
              goto L_not_viable;
          l = &g->layers[L_RIVER_MIX_4];
          biomeX = (chunkX << 4) + 8;
          biomeZ = (chunkZ << 4) + 8;
          setLayerSeed(l, seed);
          if (areBiomesViable(l, NULL, biomeX, biomeZ, 32, getValidMansionBiomes()))
              goto L_viable;
          goto L_not_viable;
  
      case Ruined_Portal:
      case Ruined_Portal_N:
          if (mc >= MC_1_16)
              goto L_viable;
          goto L_not_viable;
  
      case Mineshaft:
          goto L_viable;
  
      default:
          fprintf(stderr,
                  "isViableStructurePos: validation for structure type %d not implemented\n",
                  structureType);
          goto L_not_viable;
      }
  
  L_viable:
      if (!viable)
          viable = 1;
  L_not_viable:
  
      g->layers[L_BIOME_256] = lbiome;
      g->layers[L_SHORE_16] = lshore;
      if (ids)
          free(ids);
  
      return viable;
  }
  
  int isViableNetherStructurePos(int structureType, int mc, NetherNoise *nn,
          uint64_t seed, int blockX, int blockZ)
  {
      if (structureType == Fortress)
          return 1; // fortresses generate in all nether biomes and mc versions
      if (mc < MC_1_16)
          return 0;
      if (structureType == Ruined_Portal_N)
          return 1;
  
      blockX = ((blockX >> 4) << 2) + 2;
      blockZ = ((blockZ >> 4) << 2) + 2;
      setNetherSeed(nn, seed);
      int biomeID = getNetherBiome(nn, blockX, 0, blockZ, NULL);
      return isViableFeatureBiome(mc, structureType, biomeID);
  }
  
  int isViableEndStructurePos(int structureType, int mc, EndNoise *en,
          uint64_t seed, int blockX, int blockZ)
  {
      switch (structureType)
      {
      case End_City:
          if (mc < MC_1_9) return 0;
          break;
      case End_Gateway:
          if (mc < MC_1_13) return 0;
          break;
      default:
          return 0;
      }
  
      setEndSeed(en, seed);
  
      // end biomes vary only on a per-chunk scale (1:16)
      // voronoi pre-1.15 shouldn't matter for End Cities as the check will be
      // near the chunk center
      int id;
      int chunkX = blockX >> 4;
      int chunkZ = blockZ >> 4;
      mapEndBiome(en, &id, chunkX, chunkZ, 1, 1);
      return isViableFeatureBiome(mc, structureType, id) ? id : 0;
  }
  
  /* Given bordering noise columns and a fractional position between those,
   * determine the surface block height (i.e. where the interpolated noise > 0).
   * Note that the noise columns should be of size: ncolxz[ colheight+1 ]
   */
  int getSurfaceHeight(
          const double ncol00[], const double ncol01[],
          const double ncol10[], const double ncol11[],
          int colymin, int colymax, int blockspercell, double dx, double dz);
  
  void sampleNoiseColumnEnd(double column[], const SurfaceNoise *sn,
          const EndNoise *en, int x, int z, int colymin, int colymax);
  
  int isViableEndCityTerrain(const EndNoise *en, const SurfaceNoise *sn,
          int blockX, int blockZ)
  {
      int chunkX = blockX >> 4;
      int chunkZ = blockZ >> 4;
      blockX = (chunkX << 4) + 7;
      blockZ = (chunkZ << 4) + 7;
      int cellx = (blockX >> 3);
      int cellz = (blockZ >> 3);
      // TODO: make sure upper bound is ok
      const int y0 = 15, y1 = 18; // only check range that could yield h >= 60
      double ncol[3][3][y1-y0+1];
  
      sampleNoiseColumnEnd(ncol[0][0], sn, en, cellx, cellz, y0, y1);
      sampleNoiseColumnEnd(ncol[0][1], sn, en, cellx, cellz+1, y0, y1);
      sampleNoiseColumnEnd(ncol[1][0], sn, en, cellx+1, cellz, y0, y1);
      sampleNoiseColumnEnd(ncol[1][1], sn, en, cellx+1, cellz+1, y0, y1);
  
      int h00, h01, h10, h11;
      h00 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
              y0, y1, 4, (blockX & 7) / 8.0, (blockZ & 7) / 8.0);
  
      uint64_t cs;
      setSeed(&cs, chunkX + chunkZ * 10387313ULL);
      switch (nextInt(&cs, 4))
      {
      case 0: // (++) 0
          sampleNoiseColumnEnd(ncol[0][2], sn, en, cellx+0, cellz+2, y0, y1);
          sampleNoiseColumnEnd(ncol[1][2], sn, en, cellx+1, cellz+2, y0, y1);
          sampleNoiseColumnEnd(ncol[2][0], sn, en, cellx+2, cellz+0, y0, y1);
          sampleNoiseColumnEnd(ncol[2][1], sn, en, cellx+2, cellz+1, y0, y1);
          sampleNoiseColumnEnd(ncol[2][2], sn, en, cellx+2, cellz+2, y0, y1);
          h01 = getSurfaceHeight(ncol[0][1], ncol[0][2], ncol[1][1], ncol[1][2],
                  y0, y1, 4, ((blockX    ) & 7) / 8.0, ((blockZ + 5) & 7) / 8.0);
          h10 = getSurfaceHeight(ncol[1][0], ncol[1][1], ncol[2][0], ncol[2][1],
                  y0, y1, 4, ((blockX + 5) & 7) / 8.0, ((blockZ    ) & 7) / 8.0);
          h11 = getSurfaceHeight(ncol[1][1], ncol[1][2], ncol[2][1], ncol[2][2],
                  y0, y1, 4, ((blockX + 5) & 7) / 8.0, ((blockZ + 5) & 7) / 8.0);
          break;
  
      case 1: // (-+) 90
          sampleNoiseColumnEnd(ncol[0][2], sn, en, cellx+0, cellz+2, y0, y1);
          sampleNoiseColumnEnd(ncol[1][2], sn, en, cellx+1, cellz+2, y0, y1);
          h01 = getSurfaceHeight(ncol[0][1], ncol[0][2], ncol[1][1], ncol[1][2],
                  y0, y1, 4, ((blockX    ) & 7) / 8.0, ((blockZ + 5) & 7) / 8.0);
          h10 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
                  y0, y1, 4, ((blockX - 5) & 7) / 8.0, ((blockZ    ) & 7) / 8.0);
          h11 = getSurfaceHeight(ncol[0][1], ncol[0][2], ncol[1][1], ncol[1][2],
                  y0, y1, 4, ((blockX - 5) & 7) / 8.0, ((blockZ + 5) & 7) / 8.0);
          break;
  
      case 2: // (--) 180
          h01 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
                  y0, y1, 4, ((blockX    ) & 7) / 8.0, ((blockZ - 5) & 7) / 8.0);
          h10 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
                  y0, y1, 4, ((blockX - 5) & 7) / 8.0, ((blockZ    ) & 7) / 8.0);
          h11 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
                  y0, y1, 4, ((blockX - 5) & 7) / 8.0, ((blockZ - 5) & 7) / 8.0);
          break;
  
      case 3: // (+-) 270
          sampleNoiseColumnEnd(ncol[2][0], sn, en, cellx+2, cellz+0, y0, y1);
          sampleNoiseColumnEnd(ncol[2][1], sn, en, cellx+2, cellz+1, y0, y1);
          h01 = getSurfaceHeight(ncol[0][0], ncol[0][1], ncol[1][0], ncol[1][1],
                  y0, y1, 4, ((blockX    ) & 7) / 8.0, ((blockZ - 5) & 7) / 8.0);
          h10 = getSurfaceHeight(ncol[1][0], ncol[1][1], ncol[2][0], ncol[2][1],
                  y0, y1, 4, ((blockX + 5) & 7) / 8.0, ((blockZ    ) & 7) / 8.0);
          h11 = getSurfaceHeight(ncol[1][0], ncol[1][1], ncol[2][0], ncol[2][1],
                  y0, y1, 4, ((blockX + 5) & 7) / 8.0, ((blockZ - 5) & 7) / 8.0);
          break;
  
      default:
          return 0; // error
      }
      //printf("%d %d %d %d\n", h00, h01, h10, h11);
      if (h01 < h00) h00 = h01;
      if (h10 < h00) h00 = h10;
      if (h11 < h00) h00 = h11;
      return h00 >= 60;
  }
  
  
  //==============================================================================
  // Finding Properties of Structures
  //==============================================================================
  
  
  VillageType getVillageType(int mc, uint64_t seed, int blockX, int blockZ, int biomeID)
  {
      VillageType r = { 0, 0, 0 };
      if (!isViableFeatureBiome(mc, Village, biomeID))
          return r;
  
      uint64_t rnd = chunkGenerateRnd(seed, blockX >> 4, blockZ >> 4);
  
      r.biome = biomeID;
  
      if (mc >= MC_1_14)
      {
          skipNextN(&rnd, 1);
          int t;
          switch (biomeID)
          {
          case plains:
              t = nextInt(&rnd, 204);
              if      (t <  50) { r.variant = 0; } // plains_fountain_01
              else if (t < 100) { r.variant = 1; } // plains_meeting_point_1
              else if (t < 150) { r.variant = 2; } // plains_meeting_point_2
              else if (t < 200) { r.variant = 3; } // plains_meeting_point_3
              else if (t < 201) { r.variant = 0; r.abandoned = 1; }
              else if (t < 202) { r.variant = 1; r.abandoned = 1; }
              else if (t < 203) { r.variant = 2; r.abandoned = 1; }
              else if (t < 204) { r.variant = 3; r.abandoned = 1; }
              break;
          case desert:
              t = nextInt(&rnd, 250);
              if      (t <  98) { r.variant = 1; } // desert_meeting_point_1
              else if (t < 196) { r.variant = 2; } // desert_meeting_point_2
              else if (t < 245) { r.variant = 3; } // desert_meeting_point_3
              else if (t < 247) { r.variant = 1; r.abandoned = 1; }
              else if (t < 249) { r.variant = 2; r.abandoned = 1; }
              else if (t < 250) { r.variant = 3; r.abandoned = 1; }
              break;
          case savanna:
              t = nextInt(&rnd, 459);
              if      (t < 100) { r.variant = 1; } // savanna_meeting_point_1
              else if (t < 150) { r.variant = 2; } // savanna_meeting_point_2
              else if (t < 300) { r.variant = 3; } // savanna_meeting_point_3
              else if (t < 450) { r.variant = 4; } // savanna_meeting_point_4
              else if (t < 452) { r.variant = 1; r.abandoned = 1; }
              else if (t < 453) { r.variant = 2; r.abandoned = 1; }
              else if (t < 456) { r.variant = 3; r.abandoned = 1; }
              else if (t < 459) { r.variant = 4; r.abandoned = 1; }
              break;
          case taiga:
              t = nextInt(&rnd, 100);
              if      (t <  49) { r.variant = 1; } // taiga_meeting_point_1
              else if (t <  98) { r.variant = 2; } // taiga_meeting_point_2
              else if (t <  99) { r.variant = 1; r.abandoned = 1; }
              else if (t < 100) { r.variant = 2; r.abandoned = 1; }
              break;
          case snowy_tundra:
              t = nextInt(&rnd, 306);
              if      (t < 100) { r.variant = 1; } // snowy_meeting_point_1
              else if (t < 150) { r.variant = 2; } // snowy_meeting_point_2
              else if (t < 300) { r.variant = 3; } // snowy_meeting_point_3
              else if (t < 302) { r.variant = 1; r.abandoned = 1; }
              else if (t < 303) { r.variant = 2; r.abandoned = 1; }
              else if (t < 306) { r.variant = 3; r.abandoned = 1; }
              break;
          default:
              break;
          }
      }
      else if (mc >= MC_1_10)
      {
          skipNextN(&rnd, mc == MC_1_13 ? 10 : 11);
          r.abandoned = nextInt(&rnd, 50) == 0;
      }
  
      return r;
  }
  
  
  uint64_t getHouseList(uint64_t worldSeed, int chunkX, int chunkZ,
          int *out)
  {
      uint64_t rnd = chunkGenerateRnd(worldSeed, chunkX, chunkZ);
      skipNextN(&rnd, 1);
  
      out[HouseSmall] = nextInt(&rnd, 4 - 2 + 1) + 2;
      out[Church]     = nextInt(&rnd, 1 - 0 + 1) + 0;
      out[Library]    = nextInt(&rnd, 2 - 0 + 1) + 0;
      out[WoodHut]    = nextInt(&rnd, 5 - 2 + 1) + 2;
      out[Butcher]    = nextInt(&rnd, 2 - 0 + 1) + 0;
      out[FarmLarge]  = nextInt(&rnd, 4 - 1 + 1) + 1;
      out[FarmSmall]  = nextInt(&rnd, 4 - 2 + 1) + 2;
      out[Blacksmith] = nextInt(&rnd, 1 - 0 + 1) + 0;
      out[HouseLarge] = nextInt(&rnd, 3 - 0 + 1) + 0;
  
      return rnd;
  }
  
  //==============================================================================
  // Seed Filters
  //==============================================================================
  
  
  BiomeFilter setupBiomeFilter(const int *biomeList, int listLen)
  {
      BiomeFilter bf;
      int i, id;
  
      memset(&bf, 0, sizeof(bf));
  
      for (i = 0; i < listLen; i++)
      {
          id = biomeList[i];
          if (id & ~0xbf) // i.e. not in ranges [0,64),[128,192)
          {
              fprintf(stderr, "setupBiomeFilter: biomeID=%d not supported.\n", id);
              exit(-1);
          }
  
          switch (id)
          {
          case mushroom_fields:
              // mushroom shores can generate with hills and at rivers
              bf.raresToFind |= (1ULL << mushroom_fields);
              // fall through
          case mushroom_field_shore:
              bf.tempsToFind |= (1ULL << Oceanic);
              bf.majorToFind |= (1ULL << mushroom_fields);
              bf.riverToFind |= (1ULL << id);
              break;
  
          case badlands_plateau:
          case wooded_badlands_plateau:
          case badlands:
          case eroded_badlands:
          case modified_badlands_plateau:
          case modified_wooded_badlands_plateau:
              bf.tempsToFind |= (1ULL << (Warm+Special));
              if (id == badlands_plateau || id == modified_badlands_plateau)
                  bf.majorToFind |= (1ULL << badlands_plateau);
              if (id == wooded_badlands_plateau || id == modified_wooded_badlands_plateau)
                  bf.majorToFind |= (1ULL << wooded_badlands_plateau);
              if (id < 128) {
                  bf.raresToFind |= (1ULL << id);
                  bf.riverToFind |= (1ULL << id);
              } else {
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
  
          case jungle:
          case jungle_edge:
          case jungle_hills:
          case modified_jungle:
          case modified_jungle_edge:
          case bamboo_jungle:
          case bamboo_jungle_hills:
              bf.tempsToFind |= (1ULL << (Lush+Special));
              bf.majorToFind |= (1ULL << jungle);
              if (id == bamboo_jungle || id == bamboo_jungle_hills) {
                  // bamboo%64 are End biomes, so we can reuse the edgesToFind
                  bf.edgesToFind |= (1ULL << (bamboo_jungle & 0x3f));
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              } else if (id == jungle_edge) {
                  // un-modified jungle_edge can be created at shore layer
                  bf.riverToFind |= (1ULL << jungle_edge);
              } else {
                  if (id == modified_jungle_edge)
                      bf.edgesToFind |= (1ULL << jungle_edge);
                  else
                      bf.edgesToFind |= (1ULL << jungle);
                  if (id < 128) {
                      bf.raresToFind |= (1ULL << id);
                      bf.riverToFind |= (1ULL << id);
                  } else {
                      bf.raresToFindM |= (1ULL << (id-128));
                      bf.riverToFindM |= (1ULL << (id-128));
                  }
              }
              break;
  
          case giant_tree_taiga:
          case giant_tree_taiga_hills:
          case giant_spruce_taiga:
          case giant_spruce_taiga_hills:
              bf.tempsToFind |= (1ULL << (Cold+Special));
              bf.majorToFind |= (1ULL << giant_tree_taiga);
              bf.edgesToFind |= (1ULL << giant_tree_taiga);
              if (id < 128) {
                  bf.raresToFind |= (1ULL << id);
                  bf.riverToFind |= (1ULL << id);
              } else {
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
  
          case savanna:
          case savanna_plateau:
          case shattered_savanna:
          case shattered_savanna_plateau:
          case desert_hills:
          case desert_lakes:
              bf.tempsToFind |= (1ULL << Warm);
              if (id == desert_hills || id == desert_lakes) {
                  bf.majorToFind |= (1ULL << desert);
                  bf.edgesToFind |= (1ULL << desert);
              } else {
                  bf.majorToFind |= (1ULL << savanna);
                  bf.edgesToFind |= (1ULL << savanna);
              }
              if (id < 128) {
                  bf.raresToFind |= (1ULL << id);
                  bf.riverToFind |= (1ULL << id);
              } else {
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
  
          case dark_forest:
          case dark_forest_hills:
          case birch_forest:
          case birch_forest_hills:
          case tall_birch_forest:
          case tall_birch_hills:
          case swamp:
          case swamp_hills:
              bf.tempsToFind |= (1ULL << Lush);
              if (id == dark_forest || id == dark_forest_hills) {
                  bf.majorToFind |= (1ULL << dark_forest);
                  bf.edgesToFind |= (1ULL << dark_forest);
              }
              else if (id == birch_forest || id == birch_forest_hills ||
                       id == tall_birch_forest || id == tall_birch_hills) {
                  bf.majorToFind |= (1ULL << birch_forest);
                  bf.edgesToFind |= (1ULL << birch_forest);
              }
              else if (id == swamp || id == swamp_hills) {
                  bf.majorToFind |= (1ULL << swamp);
                  bf.edgesToFind |= (1ULL << swamp);
              }
              if (id < 128) {
                  bf.raresToFind |= (1ULL << id);
                  bf.riverToFind |= (1ULL << id);
              } else {
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
  
          case snowy_taiga:
          case snowy_taiga_hills:
          case snowy_taiga_mountains:
          case snowy_tundra:
          case snowy_mountains:
          case ice_spikes:
          case frozen_river:
              bf.tempsToFind |= (1ULL << Freezing);
              if (id == snowy_taiga || id == snowy_taiga_hills ||
                  id == snowy_taiga_mountains)
                  bf.edgesToFind |= (1ULL << snowy_taiga);
              else
                  bf.edgesToFind |= (1ULL << snowy_tundra);
              if (id == frozen_river) {
                  bf.raresToFind |= (1ULL << snowy_tundra);
                  bf.riverToFind |= (1ULL << id);
              } else if (id < 128) {
                  bf.raresToFind |= (1ULL << id);
                  bf.riverToFind |= (1ULL << id);
              } else {
                  bf.raresToFindM |= (1ULL << (id-128));
                  bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
  
          case sunflower_plains:
              bf.raresToFindM |= (1ULL << (id-128));
              bf.riverToFindM |= (1ULL << (id-128));
              break;
  
          case snowy_beach:
              bf.tempsToFind |= (1ULL << Freezing);
              // fall through
          case beach:
          case stone_shore:
              bf.riverToFind |= (1ULL << id);
              break;
  
          case mountains:
              bf.majorToFind |= (1ULL << mountains);
              // fall through
          case wooded_mountains:
              bf.raresToFind |= (1ULL << id);
              bf.riverToFind |= (1ULL << id);
              break;
          case gravelly_mountains:
              bf.majorToFind |= (1ULL << mountains);
              // fall through
          case modified_gravelly_mountains:
              bf.raresToFindM |= (1ULL << (id-128));
              bf.riverToFindM |= (1ULL << (id-128));
              break;
  
          case taiga:
          case taiga_hills:
              bf.edgesToFind |= (1ULL << taiga);
              bf.raresToFind |= (1ULL << id);
              bf.riverToFind |= (1ULL << id);
              break;
          case taiga_mountains:
              bf.edgesToFind |= (1ULL << taiga);
              bf.raresToFindM |= (1ULL << (id-128));
              bf.riverToFindM |= (1ULL << (id-128));
              break;
  
          case plains:
          case forest:
          case wooded_hills:
              bf.raresToFind |= (1ULL << id);
              bf.riverToFind |= (1ULL << id);
              break;
          case flower_forest:
              bf.raresToFindM |= (1ULL << (id-128));
              bf.riverToFindM |= (1ULL << (id-128));
              break;
  
          case desert: // can generate at shore layer
              bf.riverToFind |= (1ULL << id);
              break;
  
          default:
              if (isOceanic(id)) {
                  bf.tempsToFind |= (1ULL << Oceanic);
                  bf.oceanToFind |= (1ULL << id);
                  if (isShallowOcean(id)) {
                      if (id != lukewarm_ocean && id != cold_ocean)
                          bf.otempToFind |= (1ULL << id);
                  } else {
                      bf.raresToFind |= (1ULL << deep_ocean);
                      bf.riverToFind |= (1ULL << deep_ocean);
                      if (id == deep_warm_ocean)
                          bf.otempToFind |= (1ULL << warm_ocean);
                      else if (id == deep_ocean)
                          bf.otempToFind |= (1ULL << ocean);
                      else if (id == deep_frozen_ocean)
                          bf.otempToFind |= (1ULL << frozen_ocean);
                  }
              } else {
                  if (id < 64)
                      bf.riverToFind |= (1ULL << id);
                  else
                      bf.riverToFindM |= (1ULL << (id-128));
              }
              break;
          }
      }
  
      bf.shoreToFind = bf.riverToFind;
      bf.shoreToFind &= ~((1ULL << river) | (1ULL << frozen_river));
      bf.shoreToFindM = bf.riverToFindM;
  
      bf.specialCnt = 0;
      bf.specialCnt += !!(bf.tempsToFind & (1ULL << (Warm+Special)));
      bf.specialCnt += !!(bf.tempsToFind & (1ULL << (Lush+Special)));
      bf.specialCnt += !!(bf.tempsToFind & (1ULL << (Cold+Special)));
  
      return bf;
  }
  
  
  STRUCT(filter_data_t)
  {
      const BiomeFilter *bf;
      int (*map)(const Layer *, int *, int, int, int, int);
  };
  
  static int mapFilterSpecial(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      int i, j;
      uint64_t temps;
  
      /// pre-gen checks
      int specialcnt = f->bf->specialCnt;
      if (specialcnt > 0)
      {
          uint64_t ss = l->startSeed;
          uint64_t cs;
  
          for (j = 0; j < h; j++)
          {
              for (i = 0; i < w; i++)
              {
                  cs = getChunkSeed(ss, x+i, z+j);
                  if (mcFirstIsZero(cs, 13))
                      specialcnt--;
              }
          }
          if (specialcnt > 0)
              return 1;
      }
  
      int err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      temps = 0;
  
      for (j = 0; j < h; j++)
      {
          for (i = 0; i < w; i++)
          {
              int id = out[i + w*j];
              int isspecial = id & 0xf00;
              id &= ~0xf00;
              if (isspecial && id != Freezing)
                 temps |= (1ULL << (id+Special));
              else
                 temps |= (1ULL << id);
          }
      }
  
      if ((temps & f->bf->tempsToFind) ^ f->bf->tempsToFind)
          return 1;
      return 0;
  }
  
  static int mapFilterMushroom(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      int i, j;
      int err;
  
      if (w*h < 100 && (f->bf->majorToFind & (1ULL << mushroom_fields)))
      {
          uint64_t ss = l->startSeed;
          uint64_t cs;
  
          for (j = 0; j < h; j++)
          {
              for (i = 0; i < w; i++)
              {
                  cs = getChunkSeed(ss, i+x, j+z);
                  if (mcFirstIsZero(cs, 100))
                      goto L_GENERATE;
              }
          }
          return 1;
      }
  
  L_GENERATE:
      err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      if (f->bf->majorToFind & (1ULL << mushroom_fields))
      {
          for (i = 0; i < w*h; i++)
              if (out[i] == mushroom_fields)
                  return 0;
          return 1;
      }
      return 0;
  }
  
  static int mapFilterBiome(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      int i, j;
      uint64_t b;
  
      int err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0;
      for (j = 0; j < h; j++)
      {
          for (i = 0; i < w; i++)
          {
              int id = out[i + w*j];
              b |= (1ULL << id);
          }
      }
  
      if ((b & f->bf->majorToFind) ^ f->bf->majorToFind)
          return 1;
      return 0;
  }
  
  static int mapFilterOceanTemp(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      int i, j;
      uint64_t b;
  
      int err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0;
      for (j = 0; j < h; j++)
      {
          for (i = 0; i < w; i++)
          {
              int id = out[i + w*j];
              b |= (1ULL << id);
          }
      }
  
      if ((b & f->bf->otempToFind) ^ f->bf->otempToFind)
          return 1;
      return 0;
  }
  
  static int mapFilterBiomeEdge(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      uint64_t b;
      int i;
      int err;
  
      err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0;
      for (i = 0; i < w*h; i++)
          b |= (1ULL << (out[i] & 0x3f));
  
      if ((b & f->bf->edgesToFind) ^ f->bf->edgesToFind)
          return 1;
      return 0;
  }
  
  static int mapFilterRareBiome(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      uint64_t b, bm;
      int i;
      int err;
  
      err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0; bm = 0;
      for (i = 0; i < w*h; i++)
      {
          int id = out[i];
          if (id < 128) b |= (1ULL << id);
          else bm |= (1ULL << (id-128));
      }
  
      if ((b & f->bf->raresToFind) ^ f->bf->raresToFind)
          return 1;
      if ((bm & f->bf->raresToFindM) ^ f->bf->raresToFindM)
          return 1;
      return 0;
  }
  
  static int mapFilterShore(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      uint64_t b, bm;
      int i;
  
      int err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0; bm = 0;
      for (i = 0; i < w*h; i++)
      {
          int id = out[i];
          if (id < 128) b |= (1ULL << id);
          else bm |= (1ULL << (id-128));
      }
  
      if ((b & f->bf->shoreToFind) ^ f->bf->shoreToFind)
          return 1;
      if ((bm & f->bf->shoreToFindM) ^ f->bf->shoreToFindM)
          return 1;
      return 0;
  }
  
  static int mapFilterRiverMix(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      uint64_t b, bm;
      int i;
  
      int err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0; bm = 0;
      for (i = 0; i < w*h; i++)
      {
          int id = out[i];
          if (id < 128) b |= (1ULL << id);
          else bm |= (1ULL << (id-128));
      }
  
      if ((b & f->bf->riverToFind) ^ f->bf->riverToFind)
          return 1;
      if ((bm & f->bf->riverToFindM) ^ f->bf->riverToFindM)
          return 1;
      return 0;
  }
  
  static int mapFilterOceanMix(const Layer * l, int * out, int x, int z, int w, int h)
  {
      const filter_data_t *f = (const filter_data_t*) l->data;
      uint64_t b;
      int i;
      int err;
  
      if (f->bf->riverToFind)
      {
          err = l->p->getMap(l->p, out, x, z, w, h); // RiverMix
          if (err)
              return err;
      }
  
      err = f->map(l, out, x, z, w, h);
      if U(err != 0)
          return err;
  
      b = 0;
      for (i = 0; i < w*h; i++)
      {
          int id = out[i];
          if (id < 128) b |= (1ULL << id);
      }
  
      if ((b & f->bf->oceanToFind) ^ f->bf->oceanToFind)
          return 1;
      return 0;
  }
  
  void swapMap(filter_data_t *fd, BiomeFilter *bf, Layer *l,
          int (*map)(const Layer *, int *, int, int, int, int))
  {
      fd->bf = bf;
      fd->map = l->getMap;
      l->data = (void*) fd;
      l->getMap = map;
  }
  
  void restoreMap(filter_data_t *fd, Layer *l)
  {
      l->getMap = fd->map;
      l->data = NULL;
  }
  
  
  int checkForBiomes(
          LayerStack *    g,
          int             layerID,
          int *           cache,
          uint64_t        seed,
          int             x,
          int             z,
          unsigned int    w,
          unsigned int    h,
          BiomeFilter     filter,
          int             protoCheck
          )
  {
      Layer *l;
  
      if (protoCheck) // TODO: protoCheck for 1.6-
      {
          l = &g->layers[layerID];
  
          int i, j;
          int bx = x * l->scale;
          int bz = z * l->scale;
          int bw = w * l->scale;
          int bh = h * l->scale;
          int x0, z0, x1, z1;
          uint64_t ss, cs;
          uint64_t potential, required;
  
          int specialcnt = filter.specialCnt;
          if (specialcnt > 0)
          {
              l = &g->layers[L_SPECIAL_1024];
              x0 = (bx) / l->scale; if (x < 0) x0--;
              z0 = (bz) / l->scale; if (z < 0) z0--;
              x1 = (bx + bw) / l->scale; if (x+(int)w >= 0) x1++;
              z1 = (bz + bh) / l->scale; if (z+(int)h >= 0) z1++;
              ss = getStartSeed(seed, l->layerSalt);
  
              for (j = z0; j <= z1; j++)
              {
                  for (i = x0; i <= x1; i++)
                  {
                      cs = getChunkSeed(ss, i, j);
                      if (mcFirstIsZero(cs, 13))
                          specialcnt--;
                  }
              }
              if (specialcnt > 0)
                  return 0;
          }
  
          l = &g->layers[L_BIOME_256];
          x0 = bx / l->scale; if (x < 0) x0--;
          z0 = bz / l->scale; if (z < 0) z0--;
          x1 = (bx + bw) / l->scale; if (x+(int)w >= 0) x1++;
          z1 = (bz + bh) / l->scale; if (z+(int)h >= 0) z1++;
  
          if (filter.majorToFind & (1ULL << mushroom_fields))
          {
              ss = getStartSeed(seed, g->layers[L_MUSHROOM_256].layerSalt);
  
              for (j = z0; j <= z1; j++)
              {
                  for (i = x0; i <= x1; i++)
                  {
                      cs = getChunkSeed(ss, i, j);
                      if (mcFirstIsZero(cs, 100))
                          goto L_HAS_PROTO_MUSHROOM;
                  }
              }
              return 0;
          }
  L_HAS_PROTO_MUSHROOM:
  
          potential = 0;
          required = filter.majorToFind & (
                  (1ULL << badlands_plateau) | (1ULL << wooded_badlands_plateau) |
                  (1ULL << desert) | (1ULL << savanna) | (1ULL << plains) |
                  (1ULL << forest) | (1ULL << dark_forest) | (1ULL << mountains) |
                  (1ULL << birch_forest) | (1ULL << swamp));
  
          ss = getStartSeed(seed, l->layerSalt);
  
          for (j = z0; j <= z1; j++)
          {
              for (i = x0; i <= x1; i++)
              {
                  cs = getChunkSeed(ss, i, j);
                  int cs6 = mcFirstInt(cs, 6);
                  int cs3 = mcFirstInt(cs, 3);
                  int cs4 = mcFirstInt(cs, 4);
  
                  if (cs3) potential |= (1ULL << badlands_plateau);
                  else potential |= (1ULL << wooded_badlands_plateau);
  
                  switch (cs6)
                  {
                  case 0: potential |= (1ULL << desert) | (1ULL << forest); break;
                  case 1: potential |= (1ULL << desert) | (1ULL << dark_forest); break;
                  case 2: potential |= (1ULL << desert) | (1ULL << mountains); break;
                  case 3: potential |= (1ULL << savanna) | (1ULL << plains); break;
                  case 4: potential |= (1ULL << savanna) | (1ULL << birch_forest); break;
                  case 5: potential |= (1ULL << plains) | (1ULL << swamp); break;
                  }
  
                  if (cs4 == 3) potential |= (1ULL << snowy_taiga);
                  else potential |= (1ULL << snowy_tundra);
              }
          }
  
          if ((potential & required) ^ required)
              return 0;
      }
  
      l = g->layers;
      int *ids = cache ? cache : allocCache(&l[layerID], w, h);
  
      filter_data_t fd[9];
      swapMap(fd+0, &filter, l+L_OCEAN_MIX_4,     mapFilterOceanMix);
      swapMap(fd+1, &filter, l+L_RIVER_MIX_4,     mapFilterRiverMix);
      swapMap(fd+2, &filter, l+L_SHORE_16,        mapFilterShore);
      swapMap(fd+3, &filter, l+L_SUNFLOWER_64,    mapFilterRareBiome);
      swapMap(fd+4, &filter, l+L_BIOME_EDGE_64,   mapFilterBiomeEdge);
      swapMap(fd+5, &filter, l+L_OCEAN_TEMP_256,  mapFilterOceanTemp);
      swapMap(fd+6, &filter, l+L_BIOME_256,       mapFilterBiome);
      swapMap(fd+7, &filter, l+L_MUSHROOM_256,    mapFilterMushroom);
      swapMap(fd+8, &filter, l+L_SPECIAL_1024,    mapFilterSpecial);
  
      setLayerSeed(&l[layerID], seed);
      int ret = !l[layerID].getMap(&l[layerID], ids, x, z, w, h);
      if (ret)
      {
          uint64_t required, b = 0, bm = 0;
          unsigned int i;
          for (i = 0; i < w*h; i++)
          {
              int id = ids[i];
              if (id < 128) b |= (1ULL << id);
              else bm |= (1ULL << (id-128));
          }
          required = filter.riverToFind;
          required &= ~((1ULL << ocean) | (1ULL << deep_ocean));
          required |= filter.oceanToFind;
          if ((b & required) ^ required)
              ret = -1;
          required = filter.riverToFindM;
          if ((bm & required) ^ required)
              ret = -1;
      }
  
      restoreMap(fd+8, l+L_SPECIAL_1024);
      restoreMap(fd+7, l+L_MUSHROOM_256);
      restoreMap(fd+6, l+L_BIOME_256);
      restoreMap(fd+5, l+L_OCEAN_TEMP_256);
      restoreMap(fd+4, l+L_BIOME_EDGE_64);
      restoreMap(fd+3, l+L_SUNFLOWER_64);
      restoreMap(fd+2, l+L_SHORE_16);
      restoreMap(fd+1, l+L_RIVER_MIX_4);
      restoreMap(fd+0, l+L_OCEAN_MIX_4);
  
      if (cache == NULL)
          free(ids);
  
      return ret;
  }
  
  
  int checkForTemps(LayerStack *g, uint64_t seed, int x, int z, int w, int h, const int tc[9])
  {
      uint64_t ls = getLayerSalt(3); // L_SPECIAL_1024 layer seed
      uint64_t ss = getStartSeed(seed, ls);
  
      int i, j;
      int scnt = 0;
  
      if (tc[Special+Warm] > 0) scnt += tc[Special+Warm];
      if (tc[Special+Lush] > 0) scnt += tc[Special+Lush];
      if (tc[Special+Cold] > 0) scnt += tc[Special+Cold];
  
      if (scnt > 0)
      {
          for (j = 0; j < h; j++)
          {
              for (i = 0; i < w; i++)
              {
                  if (mcFirstIsZero(getChunkSeed(ss, x+i, z+j), 13))
                      scnt--;
              }
          }
          if (scnt > 0)
              return 0;
      }
  
      Layer *l = &g->layers[L_SPECIAL_1024];
      int ccnt[9] = {0};
      int *area = allocCache(l, w, h);
      int ret = 1;
  
      setLayerSeed(l, seed);
      genArea(l, area, x, z, w, h);
  
      for (i = 0; i < w*h; i++)
      {
          int id = area[i];
          int t = id & 0xff;
          if (id != t && t != Freezing)
              t += Special;
          ccnt[t]++;
      }
      for (i = 0; i < 9; i++)
      {
          if (ccnt[i] < tc[i] || (ccnt[i] && tc[i] < 0))
          {
              ret = 0;
              break;
          }
      }
  
      free(area);
      return ret;
  }
  
  
  int canBiomeGenerate(int layerId, int mc, int id)
  {
      int dofilter = 0;
  
      if (dofilter || layerId == L_BIOME_256)
      {
          dofilter = 1;
          if (id >= 64)
              return 0;
      }
      if (dofilter || (layerId == L_BAMBOO_256 && mc >= MC_1_14))
      {
          dofilter = 1;
          switch (id)
          {
          case jungle_edge:
          case wooded_mountains:
          case badlands:
              return 0;
          }
      }
      if (dofilter || (layerId == L_BIOME_EDGE_64 && mc >= MC_1_7))
      {
          dofilter = 1;
          if (id >= 64 && id != bamboo_jungle)
              return 0;
          switch (id)
          {
          case snowy_mountains:
          case desert_hills:
          case wooded_hills:
          case taiga_hills:
          case jungle_hills:
          case birch_forest_hills:
          case snowy_taiga_hills:
          case giant_tree_taiga_hills:
          case savanna_plateau:
              return 0;
          }
      }
      if (dofilter || layerId == L_HILLS_64)
      {
          dofilter = 1;
          // sunflower_plains actually generate at Hills layer as well
      }
      if (dofilter || (layerId == L_SUNFLOWER_64 && mc >= MC_1_7))
      {
          dofilter = 1;
          switch (id)
          {
          case frozen_ocean:
          case mushroom_field_shore:
          case beach:
          case stone_shore:
          case snowy_beach:
              return 0;
          }
      }
      if (dofilter || layerId == L_SHORE_16)
      {
          dofilter = 1;
          if (id == river || id == frozen_river)
              return 0;
      }
      if (dofilter || layerId == L_RIVER_MIX_4)
      {
          dofilter = 1;
          if (id == frozen_ocean && mc >= MC_1_7)
              return 0;
          if (isDeepOcean(id) && id != deep_ocean)
              return 0;
      }
      if (dofilter || (layerId == L_OCEAN_MIX_4 && mc >= MC_1_13))
      {
          dofilter = 1;
      }
  
      if (!dofilter && layerId != L_VORONOI_1)
      {
          printf("canBiomeGenerate(): unsupported layer (%d) or version (%d)\n",
              layerId, mc);
          return 0;
      }
      return isOverworld(mc, id);
  }
  
  
  // TODO: This function requires testing across versions
  void genPotential(uint64_t *mL, uint64_t *mM, int layer, int mc, int id)
  {
      // filter out bad biomes
      if (layer >= L_BIOME_256 && !canBiomeGenerate(layer, mc, id))
          return;
  
      switch (layer)
      {
      case L_SPECIAL_1024: // biomes added in (L_SPECIAL_1024, L_MUSHROOM_256]
          if (mc <= MC_1_6) goto L_bad_layer;
          if (id == Oceanic)
              genPotential(mL, mM, L_MUSHROOM_256, mc, mushroom_fields);
          if ((id & ~0xf00) >= Oceanic && (id & ~0xf00) <= Freezing)
              genPotential(mL, mM, L_MUSHROOM_256, mc, id);
          break;
  
      case L_MUSHROOM_256: // biomes added in (L_MUSHROOM_256, L_DEEP_OCEAN_256]
          if (mc >= MC_1_7) {
              if (id == Oceanic)
                  genPotential(mL, mM, L_DEEP_OCEAN_256, mc, deep_ocean);
              if ((id & ~0xf00) >= Oceanic && (id & ~0xf00) <= Freezing)
                  genPotential(mL, mM, L_DEEP_OCEAN_256, mc, id);
          } else { // (L_MUSHROOM_256, L_BIOME_256] for 1.6
              if (id == ocean || id == mushroom_fields) {
                  genPotential(mL, mM, L_BIOME_256, mc, id);
              } else {
                  genPotential(mL, mM, L_BIOME_256, mc, desert);
                  genPotential(mL, mM, L_BIOME_256, mc, forest);
                  genPotential(mL, mM, L_BIOME_256, mc, mountains);
                  genPotential(mL, mM, L_BIOME_256, mc, swamp);
                  genPotential(mL, mM, L_BIOME_256, mc, plains);
                  genPotential(mL, mM, L_BIOME_256, mc, taiga);
                  if (mc >= MC_1_2)
                      genPotential(mL, mM, L_BIOME_256, mc, jungle);
                  if (id != plains)
                      genPotential(mL, mM, L_BIOME_256, mc, snowy_tundra);
              }
          }
          break;
  
      case L_DEEP_OCEAN_256: // biomes added in (L_DEEP_OCEAN_256, L_BIOME_256]
          if (mc <= MC_1_6) goto L_bad_layer;
          switch (id & ~0xf00)
          {
          case Warm:
              if (id & 0xf00) {
                  genPotential(mL, mM, L_BIOME_256, mc, badlands_plateau);
                  genPotential(mL, mM, L_BIOME_256, mc, wooded_badlands_plateau);
              } else {
                  genPotential(mL, mM, L_BIOME_256, mc, desert);
                  genPotential(mL, mM, L_BIOME_256, mc, savanna);
                  genPotential(mL, mM, L_BIOME_256, mc, plains);
              }
              break;
          case Lush:
              if (id & 0xf00) {
                  genPotential(mL, mM, L_BIOME_256, mc, jungle);
              } else {
                  genPotential(mL, mM, L_BIOME_256, mc, forest);
                  genPotential(mL, mM, L_BIOME_256, mc, dark_forest);
                  genPotential(mL, mM, L_BIOME_256, mc, mountains);
                  genPotential(mL, mM, L_BIOME_256, mc, plains);
                  genPotential(mL, mM, L_BIOME_256, mc, birch_forest);
                  genPotential(mL, mM, L_BIOME_256, mc, swamp);
              }
              break;
          case Cold:
              if (id & 0xf00) {
                  genPotential(mL, mM, L_BIOME_256, mc, giant_tree_taiga);
              } else {
                  genPotential(mL, mM, L_BIOME_256, mc, forest);
                  genPotential(mL, mM, L_BIOME_256, mc, mountains);
                  genPotential(mL, mM, L_BIOME_256, mc, taiga);
                  genPotential(mL, mM, L_BIOME_256, mc, plains);
              }
              break;
          case Freezing:
              genPotential(mL, mM, L_BIOME_256, mc, snowy_tundra);
              genPotential(mL, mM, L_BIOME_256, mc, snowy_taiga);
              break;
          default:
              id &= ~0xf00;
              genPotential(mL, mM, L_BIOME_256, mc, id);
          }
          break;
  
      case L_BIOME_256: // biomes added in (L_BIOME_256, L_BIOME_EDGE_64]
          if (mc >= MC_1_7) {
              if (mc >= MC_1_14 && id == jungle)
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, bamboo_jungle);
              if (id == wooded_badlands_plateau || id == badlands_plateau)
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, badlands);
              else if(id == giant_tree_taiga)
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, taiga);
              else if (id == desert)
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, wooded_mountains);
              else if (id == swamp) {
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, jungle_edge);
                  genPotential(mL, mM, L_BIOME_EDGE_64, mc, plains);
              }
              genPotential(mL, mM, L_BIOME_EDGE_64, mc, id);
              break;
          }
          // (L_BIOME_256, L_HILLS_64] for 1.6
          // fallthrough
  
      case L_BIOME_EDGE_64: // biomes added in (L_BIOME_EDGE_64, L_HILLS_64]
          if (mc <= MC_1_6 && layer == L_BIOME_EDGE_64) goto L_bad_layer;
          if (!isShallowOcean(id) && getMutated(mc, id) > 0)
               genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, id));
          switch (id)
          {
          case desert:
              genPotential(mL, mM, L_HILLS_64, mc, desert_hills);
              break;
          case forest:
              genPotential(mL, mM, L_HILLS_64, mc, wooded_hills);
              break;
          case birch_forest:
              genPotential(mL, mM, L_HILLS_64, mc, birch_forest_hills);
              genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, birch_forest_hills));
              break;
          case dark_forest:
              genPotential(mL, mM, L_HILLS_64, mc, plains);
              genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, plains));
              break;
          case taiga:
              genPotential(mL, mM, L_HILLS_64, mc, taiga_hills);
              break;
          case giant_tree_taiga:
              genPotential(mL, mM, L_HILLS_64, mc, giant_tree_taiga_hills);
              genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, giant_tree_taiga_hills));
              break;
          case plains:
              if (mc >= MC_1_7)
                  genPotential(mL, mM, L_HILLS_64, mc, wooded_hills);
              genPotential(mL, mM, L_HILLS_64, mc, forest);
              genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, forest));
              break;
          case snowy_tundra:
              genPotential(mL, mM, L_HILLS_64, mc, snowy_mountains);
              break;
          case bamboo_jungle:
              genPotential(mL, mM, L_HILLS_64, mc, bamboo_jungle_hills);
              break;
          case ocean:
              if (mc >= MC_1_7)
                  genPotential(mL, mM, L_HILLS_64, mc, deep_ocean);
              break;
          case mountains:
              if (mc >= MC_1_7) {
                  genPotential(mL, mM, L_HILLS_64, mc, wooded_mountains);
                  genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, wooded_mountains));
              }
              break;
          case savanna:
              genPotential(mL, mM, L_HILLS_64, mc, savanna_plateau);
              genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, savanna_plateau));
              break;
          default:
              if (areSimilar(mc, id, wooded_badlands_plateau))
              {
                  genPotential(mL, mM, L_HILLS_64, mc, badlands);
                  genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, badlands));
              }
              else if (isDeepOcean(id))
              {
                  genPotential(mL, mM, L_HILLS_64, mc, plains);
                  genPotential(mL, mM, L_HILLS_64, mc, forest);
                  genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, plains));
                  genPotential(mL, mM, L_HILLS_64, mc, getMutated(mc, forest));
              }
          }
          genPotential(mL, mM, L_HILLS_64, mc, id);
          break;
  
      case L_HILLS_64: // biomes added in (L_HILLS_64, L_RARE_BIOME_64]
          if (mc <= MC_1_6) { // (L_HILLS_64, L_SHORE_16] for 1.6
              if (id == mushroom_fields)
                  genPotential(mL, mM, L_SHORE_16, mc, mushroom_field_shore);
              else if (id == mountains)
                  genPotential(mL, mM, L_SHORE_16, mc, mountain_edge);
              else if (id != ocean && id != river && id != swamp)
                  genPotential(mL, mM, L_SHORE_16, mc, beach);
              genPotential(mL, mM, L_SHORE_16, mc, id);
          } else {
              if (id == plains)
                  genPotential(mL, mM, L_SUNFLOWER_64, mc, sunflower_plains);
              genPotential(mL, mM, L_SUNFLOWER_64, mc, id);
          }
          break;
  
      case L_SUNFLOWER_64: // biomes added in (L_SUNFLOWER_64, L_SHORE_16] 1.7+
          if (mc <= MC_1_6) goto L_bad_layer;
          if (id == mushroom_fields)
              genPotential(mL, mM, L_SHORE_16, mc, mushroom_field_shore);
          else if (getCategory(mc, id) == jungle) {
              genPotential(mL, mM, L_SHORE_16, mc, beach);
              genPotential(mL, mM, L_SHORE_16, mc, jungle_edge);
          }
          else if (id == mountains || id == wooded_mountains || id == mountain_edge)
              genPotential(mL, mM, L_SHORE_16, mc, stone_shore);
          else if (isSnowy(id))
              genPotential(mL, mM, L_SHORE_16, mc, snowy_beach);
          else if (id == badlands || id == wooded_badlands_plateau)
              genPotential(mL, mM, L_SHORE_16, mc, desert);
          else if (id != ocean && id != deep_ocean && id != river && id != swamp)
              genPotential(mL, mM, L_SHORE_16, mc, beach);
          genPotential(mL, mM, L_SHORE_16, mc, id);
          break;
  
      case L_SHORE_16: // biomes added in (L_SHORE_16, L_RIVER_MIX_4]
          if (id == snowy_tundra)
              genPotential(mL, mM, L_RIVER_MIX_4, mc, frozen_river);
          else if (id == mushroom_fields || id == mushroom_field_shore)
              genPotential(mL, mM, L_RIVER_MIX_4, mc, mushroom_field_shore);
          else if (id != ocean && (mc < MC_1_7 || !isOceanic(id)))
              genPotential(mL, mM, L_RIVER_MIX_4, mc, river);
          genPotential(mL, mM, L_RIVER_MIX_4, mc, id);
          break;
  
      case L_RIVER_MIX_4: // biomes added in (L_RIVER_MIX_4, L_VORONOI_1]
          if (mc >= MC_1_13 && isOceanic(id)) {
              if (id == ocean) {
                  genPotential(mL, mM, L_VORONOI_1, mc, ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, warm_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, lukewarm_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, cold_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, frozen_ocean);
              } else if (id == deep_ocean) {
                  genPotential(mL, mM, L_VORONOI_1, mc, deep_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, deep_lukewarm_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, deep_cold_ocean);
                  genPotential(mL, mM, L_VORONOI_1, mc, deep_frozen_ocean);
              }
              else break;
          }
          genPotential(mL, mM, L_VORONOI_1, mc, id);
          break;
  
      case L_VORONOI_1:
          if (id < 128)   *mL |= 1ULL << id;
          else            *mM |= 1ULL << (id-128);
          break;
  
      default:
          printf("genPotential() not implemented for layer %d\n", layer);
      }
      if (0)
      {
      L_bad_layer:
          printf("genPotential() bad layer %d for version\n", layer);
      }
  }
  
  
  
  
  
  
  