/*

 * Copyright (c) 2000 Matteo Frigo

 * Copyright (c) 2000 Massachusetts Institute of Technology

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

 *

 */

#include "kernel/ifftw.h"

#include <string.h>

/* GNU Coding Standards, Sec. 5.2: "Please write the comments in a GNU

   program in English, because English is the one language that nearly

   all programmers in all countries can read."

                    ingemisco tanquam reus

        culpa rubet vultus meus

        supplicanti parce [rms]

*/

#define VALIDP(solution) ((solution)->flags.hash_info & H_VALID)

#define LIVEP(solution) ((solution)->flags.hash_info & H_LIVE)

#define SLVNDX(solution) ((solution)->flags.slvndx)

#define BLISS(flags) (((flags).hash_info) & BLESSING)

#define INFEASIBLE_SLVNDX ((1U<<BITS_FOR_SLVNDX)-1)

#define MAXNAM 64  /* maximum length of registrar's name.

          Used for reading wisdom.  There is no point

          in doing this right */

#ifdef FFTW_DEBUG

static void check(hashtab *ht);

#endif

/* x <= y */

#define LEQ(x, y) (((x) & (y)) == (x))

/* A subsumes B */

static int subsumes(const flags_t *a, unsigned slvndx_a, const flags_t *b)

{

     if (slvndx_a != INFEASIBLE_SLVNDX) {

    A(a->timelimit_impatience == 0);

    return (LEQ(a->u, b->u) && LEQ(b->l, a->l));

     } else {

    return (LEQ(a->l, b->l) 

      && a->timelimit_impatience <= b->timelimit_impatience);

     }

}

static unsigned addmod(unsigned a, unsigned b, unsigned p)

{

     /* gcc-2.95/sparc produces incorrect code for the fast version below. */

#if defined(__sparc__) && defined(__GNUC__)

     /* slow version  */

     return (a + b) % p;

#else

     /* faster version */

     unsigned c = a + b;

     return c >= p ? c - p : c;

#endif

}

/*

  slvdesc management:

*/

static void sgrow(planner *ego)

{

     unsigned osiz = ego->slvdescsiz, nsiz = 1 + osiz + osiz / 4;

     slvdesc *ntab = (slvdesc *)MALLOC(nsiz * sizeof(slvdesc), SLVDESCS);

     slvdesc *otab = ego->slvdescs;

     unsigned i;

     ego->slvdescs = ntab;

     ego->slvdescsiz = nsiz;

     for (i = 0; i < osiz; ++i)

    ntab[i] = otab[i];

     X(ifree0)(otab);

}

static void register_solver(planner *ego, solver *s)

{

     slvdesc *n;

     int kind;

     if (s) { /* add s to solver list */

    X(solver_use)(s);

    A(ego->nslvdesc < INFEASIBLE_SLVNDX);

    if (ego->nslvdesc >= ego->slvdescsiz)

         sgrow(ego);

    n = ego->slvdescs + ego->nslvdesc;

    n->slv = s;

    n->reg_nam = ego->cur_reg_nam;

    n->reg_id = ego->cur_reg_id++;

    A(strlen(n->reg_nam) < MAXNAM);

    n->nam_hash = X(hash)(n->reg_nam);

    kind = s->adt->problem_kind;

    n->next_for_same_problem_kind = ego->slvdescs_for_problem_kind[kind];

    ego->slvdescs_for_problem_kind[kind] = (int)/*from unsigned*/ego->nslvdesc;

    ego->nslvdesc++;

     }

}

static unsigned slookup(planner *ego, char *nam, int id)

{

     unsigned h = X(hash)(nam); /* used to avoid strcmp in the common case */

     FORALL_SOLVERS(ego, s, sp, {

    UNUSED(s);

    if (sp->reg_id == id && sp->nam_hash == h

        && !strcmp(sp->reg_nam, nam))

         return (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);

     });

     return INFEASIBLE_SLVNDX;

}

/* Compute a MD5 hash of the configuration of the planner.

   We store it into the wisdom file to make absolutely sure that

   we are reading wisdom that is applicable */

static void signature_of_configuration(md5 *m, planner *ego)

{

     X(md5begin)(m);

     X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */

     FORALL_SOLVERS(ego, s, sp, {

    UNUSED(s);

    X(md5int)(m, sp->reg_id);

    X(md5puts)(m, sp->reg_nam);

     });

     X(md5end)(m);

}

/*

  md5-related stuff:

*/

/* first hash function */

static unsigned h1(const hashtab *ht, const md5sig s)

{

     unsigned h = s[0] % ht->hashsiz;

     A(h == (s[0] % ht->hashsiz));

     return h;

}

/* second hash function (for double hashing) */

static unsigned h2(const hashtab *ht, const md5sig s)

{

     unsigned h = 1U + s[1] % (ht->hashsiz - 1);

     A(h == (1U + s[1] % (ht->hashsiz - 1)));

     return h;

}

static void md5hash(md5 *m, const problem *p, const planner *plnr)

{

     X(md5begin)(m);

     X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */

     X(md5int)(m, plnr->nthr);

     p->adt->hash(p, m);

     X(md5end)(m);

}

static int md5eq(const md5sig a, const md5sig b)

{

     return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3];

}

static void sigcpy(const md5sig a, md5sig b)

{

     b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3];

}

/*

  memoization routines :

*/

/*

   liber scriptus proferetur

   in quo totum continetur

   unde mundus iudicetur

*/

struct solution_s {

     md5sig s;

     flags_t flags;

};

static solution *htab_lookup(hashtab *ht, const md5sig s, 

           const flags_t *flagsp)

{

     unsigned g, h = h1(ht, s), d = h2(ht, s);

     solution *best = 0;

     ++ht->lookup;

     /* search all entries that match; select the one with

  the lowest flags.u */

     /* This loop may potentially traverse the whole table, since at

  least one element is guaranteed to be !LIVEP, but all elements

  may be VALIDP.  Hence, we stop after at the first invalid

  element or after traversing the whole table. */

     g = h;

     do {

    solution *l = ht->solutions + g;

    ++ht->lookup_iter;

    if (VALIDP(l)) {

         if (LIVEP(l)

       && md5eq(s, l->s)

       && subsumes(&l->flags, SLVNDX(l), flagsp) ) { 

        if (!best || LEQ(l->flags.u, best->flags.u))

       best = l;

         }

    } else 

         break;

    g = addmod(g, d, ht->hashsiz);

     } while (g != h);

     if (best) 

    ++ht->succ_lookup;

     return best;

}

static solution *hlookup(planner *ego, const md5sig s, 

       const flags_t *flagsp)

{

     solution *sol = htab_lookup(&ego->htab_blessed, s, flagsp);

     if (!sol) sol = htab_lookup(&ego->htab_unblessed, s, flagsp);

     return sol;

}

static void fill_slot(hashtab *ht, const md5sig s, const flags_t *flagsp,

          unsigned slvndx, solution *slot)

{

     ++ht->insert;

     ++ht->nelem;

     A(!LIVEP(slot));

     slot->flags.u = flagsp->u;

     slot->flags.l = flagsp->l;

     slot->flags.timelimit_impatience = flagsp->timelimit_impatience;

     slot->flags.hash_info |= H_VALID | H_LIVE;

     SLVNDX(slot) = slvndx;

     /* keep this check enabled in case we add so many solvers

  that the bitfield overflows */

     CK(SLVNDX(slot) == slvndx);     

     sigcpy(s, slot->s);

}

static void kill_slot(hashtab *ht, solution *slot)

{

     A(LIVEP(slot)); /* ==> */ A(VALIDP(slot));

     --ht->nelem;

     slot->flags.hash_info = H_VALID;

}

static void hinsert0(hashtab *ht, const md5sig s, const flags_t *flagsp, 

         unsigned slvndx)

{

     solution *l;

     unsigned g, h = h1(ht, s), d = h2(ht, s); 

     ++ht->insert_unknown;

     /* search for nonfull slot */

     for (g = h; ; g = addmod(g, d, ht->hashsiz)) {

    ++ht->insert_iter;

    l = ht->solutions + g;

    if (!LIVEP(l)) break;

    A((g + d) % ht->hashsiz != h);

     }

     fill_slot(ht, s, flagsp, slvndx, l);

}

static void rehash(hashtab *ht, unsigned nsiz)

{

     unsigned osiz = ht->hashsiz, h;

     solution *osol = ht->solutions, *nsol;

     nsiz = (unsigned)X(next_prime)((INT)nsiz);

     nsol = (solution *)MALLOC(nsiz * sizeof(solution), HASHT);

     ++ht->nrehash;

     /* init new table */

     for (h = 0; h < nsiz; ++h) 

    nsol[h].flags.hash_info = 0;

     /* install new table */

     ht->hashsiz = nsiz;

     ht->solutions = nsol;

     ht->nelem = 0;

     /* copy table */

     for (h = 0; h < osiz; ++h) {

    solution *l = osol + h;

    if (LIVEP(l))

         hinsert0(ht, l->s, &l->flags, SLVNDX(l));

     }

     X(ifree0)(osol);

}

static unsigned minsz(unsigned nelem)

{

     return 1U + nelem + nelem / 8U;

}

static unsigned nextsz(unsigned nelem)

{

     return minsz(minsz(nelem));

}

static void hgrow(hashtab *ht)

{

     unsigned nelem = ht->nelem;

     if (minsz(nelem) >= ht->hashsiz)

    rehash(ht, nextsz(nelem));

}

#if 0

/* shrink the hash table, never used */

static void hshrink(hashtab *ht)

{

     unsigned nelem = ht->nelem;

     /* always rehash after deletions */

     rehash(ht, nextsz(nelem));

}

#endif

static void htab_insert(hashtab *ht, const md5sig s, const flags_t *flagsp,

      unsigned slvndx)

{

     unsigned g, h = h1(ht, s), d = h2(ht, s);

     solution *first = 0;

     /* Remove all entries that are subsumed by the new one.  */

     /* This loop may potentially traverse the whole table, since at

  least one element is guaranteed to be !LIVEP, but all elements

  may be VALIDP.  Hence, we stop after at the first invalid

  element or after traversing the whole table. */

     g = h;

     do {

    solution *l = ht->solutions + g;

    ++ht->insert_iter;

    if (VALIDP(l)) {

         if (LIVEP(l) && md5eq(s, l->s)) {

        if (subsumes(flagsp, slvndx, &l->flags)) {

       if (!first) first = l;

       kill_slot(ht, l);

        } else {

       /* It is an error to insert an element that

          is subsumed by an existing entry. */

       A(!subsumes(&l->flags, SLVNDX(l), flagsp));

        }

         }

    } else 

         break;

    g = addmod(g, d, ht->hashsiz);

     } while (g != h);

     if (first) {

    /* overwrite FIRST */

    fill_slot(ht, s, flagsp, slvndx, first);

     } else {

    /* create a new entry */

    hgrow(ht);

    hinsert0(ht, s, flagsp, slvndx);

     }

}

static void hinsert(planner *ego, const md5sig s, const flags_t *flagsp, 

        unsigned slvndx)

{

     htab_insert(BLISS(*flagsp) ? &ego->htab_blessed : &ego->htab_unblessed,

     s, flagsp, slvndx );

}

static void invoke_hook(planner *ego, plan *pln, const problem *p, 

      int optimalp)

{

     if (ego->hook)

    ego->hook(ego, pln, p, optimalp);

}

#ifdef FFTW_RANDOM_ESTIMATOR

/* a "random" estimate, used for debugging to generate "random"

   plans, albeit from a deterministic seed. */

unsigned X(random_estimate_seed) = 0;

static double random_estimate(const planner *ego, const plan *pln, 

            const problem *p)

{

     md5 m;

     X(md5begin)(&m);

     X(md5unsigned)(&m, X(random_estimate_seed));

     X(md5int)(&m, ego->nthr);

     p->adt->hash(p, &m);

     X(md5putb)(&m, &pln->ops, sizeof(pln->ops));

     X(md5putb)(&m, &pln->adt, sizeof(pln->adt));

     X(md5end)(&m);

     return ego->cost_hook ? ego->cost_hook(p, m.s[0], COST_MAX) : m.s[0];

}

#endif

double X(iestimate_cost)(const planner *ego, const plan *pln, const problem *p)

{

     double cost =

    + pln->ops.add

    + pln->ops.mul

#if HAVE_FMA

    + pln->ops.fma

#else

    + 2 * pln->ops.fma

#endif

    + pln->ops.other;

     if (ego->cost_hook)

    cost = ego->cost_hook(p, cost, COST_MAX);

     return cost;

}

static void evaluate_plan(planner *ego, plan *pln, const problem *p)

{

     if (ESTIMATEP(ego) || !BELIEVE_PCOSTP(ego) || pln->pcost == 0.0) {

    ego->nplan++;

    if (ESTIMATEP(ego)) {

    estimate:

         /* heuristic */

#ifdef FFTW_RANDOM_ESTIMATOR

         pln->pcost = random_estimate(ego, pln, p);

         ego->epcost += X(iestimate_cost)(ego, pln, p);

#else

         pln->pcost = X(iestimate_cost)(ego, pln, p);

         ego->epcost += pln->pcost;

#endif

    } else {

         double t = X(measure_execution_time)(ego, pln, p);

         if (t < 0) {  /* unavailable cycle counter */

        /* Real programmers can write FORTRAN in any language */

        goto estimate;

         }

         pln->pcost = t;

         ego->pcost += t;

         ego->need_timeout_check = 1;

    }

     }

     invoke_hook(ego, pln, p, 0);

}

/* maintain dynamic scoping of flags, nthr: */

static plan *invoke_solver(planner *ego, const problem *p, solver *s, 

         const flags_t *nflags)

{

     flags_t flags = ego->flags;

     int nthr = ego->nthr;

     plan *pln;

     ego->flags = *nflags;

     PLNR_TIMELIMIT_IMPATIENCE(ego) = 0;

     A(p->adt->problem_kind == s->adt->problem_kind);

     pln = s->adt->mkplan(s, p, ego);

     ego->nthr = nthr;

     ego->flags = flags;

     return pln;

}

/* maintain the invariant TIMED_OUT ==> NEED_TIMEOUT_CHECK */

static int timeout_p(planner *ego, const problem *p)

{

     /* do not timeout when estimating.  First, the estimator is the

  planner of last resort.  Second, calling X(elapsed_since)() is

  slower than estimating */

     if (!ESTIMATEP(ego)) {

    /* do not assume that X(elapsed_since)() is monotonic */

    if (ego->timed_out) {

         A(ego->need_timeout_check);

         return 1;

    }

    if (ego->timelimit >= 0 &&

        X(elapsed_since)(ego, p, ego->start_time) >= ego->timelimit) {

         ego->timed_out = 1;

         ego->need_timeout_check = 1;

         return 1;

    }

     }

     A(!ego->timed_out);

     ego->need_timeout_check = 0;

     return 0;

}

static plan *search0(planner *ego, const problem *p, unsigned *slvndx, 

         const flags_t *flagsp)

{

     plan *best = 0;

     int best_not_yet_timed = 1;

     /* Do not start a search if the planner timed out. This check is

  necessary, lest the relaxation mechanism kick in */

     if (timeout_p(ego, p))

    return 0;

     FORALL_SOLVERS_OF_KIND(p->adt->problem_kind, ego, s, sp, {

    plan *pln;

    pln = invoke_solver(ego, p, s, flagsp);

    if (ego->need_timeout_check) 

         if (timeout_p(ego, p)) {

        X(plan_destroy_internal)(pln);

        X(plan_destroy_internal)(best);

        return 0;

         }

    if (pln) {

         /* read COULD_PRUNE_NOW_P because PLN may be destroyed

      before we use COULD_PRUNE_NOW_P */

         int could_prune_now_p = pln->could_prune_now_p;

         if (best) {

        if (best_not_yet_timed) {

       evaluate_plan(ego, best, p);

       best_not_yet_timed = 0;

        }

        evaluate_plan(ego, pln, p);

        if (pln->pcost < best->pcost) {

       X(plan_destroy_internal)(best);

       best = pln;

                         *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);

        } else {

       X(plan_destroy_internal)(pln);

        }

         } else {

        best = pln;

                    *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);                    

         }

         if (ALLOW_PRUNINGP(ego) && could_prune_now_p) 

        break;

    }

     });

     return best;

}

static plan *search(planner *ego, const problem *p, unsigned *slvndx, 

        flags_t *flagsp)

{

     plan *pln = 0;

     unsigned i;

     /* relax impatience in this order: */

     static const unsigned relax_tab[] = {

    0, /* relax nothing */

    NO_VRECURSE,

    NO_FIXED_RADIX_LARGE_N,

    NO_SLOW,

    NO_UGLY

     };

     unsigned l_orig = flagsp->l;

     unsigned x = flagsp->u;

     /* guaranteed to be different from X */

     unsigned last_x = ~x; 

     for (i = 0; i < sizeof(relax_tab) / sizeof(relax_tab[0]); ++i) {

    if (LEQ(l_orig, x & ~relax_tab[i]))

         x = x & ~relax_tab[i];

    if (x != last_x) {

         last_x = x;

         flagsp->l = x;

         pln = search0(ego, p, slvndx, flagsp);

         if (pln) break;

    }

     }

     if (!pln) {

    /* search [L_ORIG, U] */

    if (l_orig != last_x) {

         last_x = l_orig;

         flagsp->l = l_orig;

         pln = search0(ego, p, slvndx, flagsp);

    }

     }

     return pln;

}

#define CHECK_FOR_BOGOSITY            \

     if ((ego->bogosity_hook ?            \

    (ego->wisdom_state = ego->bogosity_hook(ego->wisdom_state, p)) \

    : ego->wisdom_state) == WISDOM_IS_BOGUS)     \

    goto wisdom_is_bogus;

static plan *mkplan(planner *ego, const problem *p)

{

     plan *pln;

     md5 m;

     unsigned slvndx;

     flags_t flags_of_solution;

     solution *sol;

     solver *s;

     ASSERT_ALIGNED_DOUBLE;

     A(LEQ(PLNR_L(ego), PLNR_U(ego)));

     if (ESTIMATEP(ego))

    PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; /* canonical form */

#ifdef FFTW_DEBUG

     check(&ego->htab_blessed);

     check(&ego->htab_unblessed);

#endif

     pln = 0;

     CHECK_FOR_BOGOSITY;

     ego->timed_out = 0;

     ++ego->nprob;

     md5hash(&m, p, ego);

     flags_of_solution = ego->flags;

     if (ego->wisdom_state != WISDOM_IGNORE_ALL) {

    if ((sol = hlookup(ego, m.s, &flags_of_solution))) { 

         /* wisdom is acceptable */

         wisdom_state_t owisdom_state = ego->wisdom_state;

         /* this hook is mainly for MPI, to make sure that

      wisdom is in sync across all processes for MPI problems */

         if (ego->wisdom_ok_hook && !ego->wisdom_ok_hook(p, sol->flags))

        goto do_search; /* ignore not-ok wisdom */

         slvndx = SLVNDX(sol);

         if (slvndx == INFEASIBLE_SLVNDX) {

        if (ego->wisdom_state == WISDOM_IGNORE_INFEASIBLE)

       goto do_search;

        else

       return 0;   /* known to be infeasible */

         }

         flags_of_solution = sol->flags;

         /* inherit blessing either from wisdom

      or from the planner */

         flags_of_solution.hash_info |= BLISS(ego->flags);

         ego->wisdom_state = WISDOM_ONLY;

         s = ego->slvdescs[slvndx].slv;

         if (p->adt->problem_kind != s->adt->problem_kind)

        goto wisdom_is_bogus;

         pln = invoke_solver(ego, p, s, &flags_of_solution);

         CHECK_FOR_BOGOSITY;     /* catch error in child solvers */

         sol = 0; /* Paranoia: SOL may be dangling after

         invoke_solver(); make sure we don't accidentally

         reuse it. */

         if (!pln)

        goto wisdom_is_bogus;

         ego->wisdom_state = owisdom_state;

         goto skip_search;

    }

    else if (ego->nowisdom_hook) /* for MPI, make sure lack of wisdom */

         ego->nowisdom_hook(p);  /*   is in sync across all processes */

     }

 do_search:

     /* cannot search in WISDOM_ONLY mode */

     if (ego->wisdom_state == WISDOM_ONLY)

    goto wisdom_is_bogus;

     flags_of_solution = ego->flags;

     pln = search(ego, p, &slvndx, &flags_of_solution);

     CHECK_FOR_BOGOSITY;     /* catch error in child solvers */

     if (ego->timed_out) {

    A(!pln);

    if (PLNR_TIMELIMIT_IMPATIENCE(ego) != 0) {

         /* record (below) that this plan has failed because of

      timeout */

         flags_of_solution.hash_info |= BLESSING;

    } else {

         /* this is not the top-level problem or timeout is not

      active: record no wisdom. */

         return 0;

    }

     } else {

    /* canonicalize to infinite timeout */

    flags_of_solution.timelimit_impatience = 0;

     }

 skip_search:

     if (ego->wisdom_state == WISDOM_NORMAL ||

   ego->wisdom_state == WISDOM_ONLY) {

    if (pln) {

         hinsert(ego, m.s, &flags_of_solution, slvndx);

         invoke_hook(ego, pln, p, 1);

    } else {

         hinsert(ego, m.s, &flags_of_solution, INFEASIBLE_SLVNDX);

    }

     }

     return pln;

 wisdom_is_bogus:

     X(plan_destroy_internal)(pln);

     ego->wisdom_state = WISDOM_IS_BOGUS;

     return 0;

}

static void htab_destroy(hashtab *ht)

{

     X(ifree)(ht->solutions);

     ht->solutions = 0;

     ht->nelem = 0U;

}

static void mkhashtab(hashtab *ht)

{

     ht->nrehash = 0;

     ht->succ_lookup = ht->lookup = ht->lookup_iter = 0;

     ht->insert = ht->insert_iter = ht->insert_unknown = 0;

     ht->solutions = 0;

     ht->hashsiz = ht->nelem = 0U;

     hgrow(ht);     /* so that hashsiz > 0 */

}

/* destroy hash table entries.  If FORGET_EVERYTHING, destroy the whole

   table.  If FORGET_ACCURSED, then destroy entries that are not blessed. */

static void forget(planner *ego, amnesia a)

{

     switch (a) {

   case FORGET_EVERYTHING:

        htab_destroy(&ego->htab_blessed);

        mkhashtab(&ego->htab_blessed);

        /* fall through */

   case FORGET_ACCURSED:

        htab_destroy(&ego->htab_unblessed);

        mkhashtab(&ego->htab_unblessed);

        break;

   default:

        break;

     }

}

/* FIXME: what sort of version information should we write? */

#define WISDOM_PREAMBLE PACKAGE "-" VERSION " " STRINGIZE(X(wisdom))

static const char stimeout[] = "TIMEOUT";

/* tantus labor non sit cassus */

static void exprt(planner *ego, printer *p)

{

     unsigned h;

     hashtab *ht = &ego->htab_blessed;

     md5 m;

     signature_of_configuration(&m, ego);

     p->print(p, 

        "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",

        m.s[0], m.s[1], m.s[2], m.s[3]);

     for (h = 0; h < ht->hashsiz; ++h) {

    solution *l = ht->solutions + h;

    if (LIVEP(l)) {

         const char *reg_nam;

         int reg_id;

         if (SLVNDX(l) == INFEASIBLE_SLVNDX) {

        reg_nam = stimeout;

        reg_id = 0;

         } else {

        slvdesc *sp = ego->slvdescs + SLVNDX(l);

        reg_nam = sp->reg_nam;

        reg_id = sp->reg_id;

         }

         /* qui salvandos salvas gratis

      salva me fons pietatis */

         p->print(p, "  (%s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)\n",

      reg_nam, reg_id, 

      l->flags.l, l->flags.u, l->flags.timelimit_impatience, 

      l->s[0], l->s[1], l->s[2], l->s[3]);

    }

     }

     p->print(p, ")\n");

}

/* mors stupebit et natura

   cum resurget creatura */

static int imprt(planner *ego, scanner *sc)

{

     char buf[MAXNAM + 1];

     md5uint sig[4];

     unsigned l, u, timelimit_impatience;

     flags_t flags;

     int reg_id;

     unsigned slvndx;

     hashtab *ht = &ego->htab_blessed;

     hashtab old;

     md5 m;

     if (!sc->scan(sc, 

       "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",

       sig + 0, sig + 1, sig + 2, sig + 3))

    return 0; /* don't need to restore hashtable */

     signature_of_configuration(&m, ego);

     if (m.s[0] != sig[0] || m.s[1] != sig[1] ||

   m.s[2] != sig[2] || m.s[3] != sig[3]) {

    /* invalid configuration */

    return 0;

     }

     /* make a backup copy of the hash table (cache the hash) */

     {

    unsigned h, hsiz = ht->hashsiz;

    old = *ht;

    old.solutions = (solution *)MALLOC(hsiz * sizeof(solution), HASHT);

    for (h = 0; h < hsiz; ++h)

         old.solutions[h] = ht->solutions[h];

     }

     while (1) {

    if (sc->scan(sc, ")"))

         break;

    /* qua resurget ex favilla */

    if (!sc->scan(sc, "(%*s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)",

      MAXNAM, buf, &reg_id, &l, &u, &timelimit_impatience,

      sig + 0, sig + 1, sig + 2, sig + 3))

         goto bad;

    if (!strcmp(buf, stimeout) && reg_id == 0) {

         slvndx = INFEASIBLE_SLVNDX;

    } else {

         if (timelimit_impatience != 0)

        goto bad;

         slvndx = slookup(ego, buf, reg_id);

         if (slvndx == INFEASIBLE_SLVNDX)

        goto bad;

    }

    /* inter oves locum praesta */

    flags.l = l;

    flags.u = u;

    flags.timelimit_impatience = timelimit_impatience;

    flags.hash_info = BLESSING;

    CK(flags.l == l);

    CK(flags.u == u);

    CK(flags.timelimit_impatience == timelimit_impatience);

    if (!hlookup(ego, sig, &flags))

         hinsert(ego, sig, &flags, slvndx);

     }

     X(ifree0)(old.solutions);

     return 1;

 bad:

     /* ``The wisdom of FFTW must be above suspicion.'' */

     X(ifree0)(ht->solutions);

     *ht = old;

     return 0;

}

/*

 * create a planner

 */

planner *X(mkplanner)(void)

{

     int i;

     static const planner_adt padt = {

    register_solver, mkplan, forget, exprt, imprt

     };

     planner *p = (planner *) MALLOC(sizeof(planner), PLANNERS);

     p->adt = &padt;

     p->nplan = p->nprob = 0;

     p->pcost = p->epcost = 0.0;

     p->hook = 0;

     p->cost_hook = 0;

     p->wisdom_ok_hook = 0;

     p->nowisdom_hook = 0;

     p->bogosity_hook = 0;

     p->cur_reg_nam = 0;

     p->wisdom_state = WISDOM_NORMAL;

     p->slvdescs = 0;

     p->nslvdesc = p->slvdescsiz = 0;

     p->flags.l = 0;

     p->flags.u = 0;

     p->flags.timelimit_impatience = 0;

     p->flags.hash_info = 0;

     p->nthr = 1;

     p->need_timeout_check = 1;

     p->timelimit = -1;

     mkhashtab(&p->htab_blessed);

     mkhashtab(&p->htab_unblessed);

     for (i = 0; i < PROBLEM_LAST; ++i)

    p->slvdescs_for_problem_kind[i] = -1;

     return p;

}

void X(planner_destroy)(planner *ego)

{

     /* destroy hash table */

     htab_destroy(&ego->htab_blessed);

     htab_destroy(&ego->htab_unblessed);

     /* destroy solvdesc table */

     FORALL_SOLVERS(ego, s, sp, {

    UNUSED(sp);

    X(solver_destroy)(s);

     });

     X(ifree0)(ego->slvdescs);

     X(ifree)(ego); /* dona eis requiem */

}

plan *X(mkplan_d)(planner *ego, problem *p)

{

     plan *pln = ego->adt->mkplan(ego, p);

     X(problem_destroy)(p);

     return pln;

}

/* like X(mkplan_d), but sets/resets flags as well */

plan *X(mkplan_f_d)(planner *ego, problem *p, 

        unsigned l_set, unsigned u_set, unsigned u_reset)

{

     flags_t oflags = ego->flags;

     plan *pln;

     PLNR_U(ego) &= ~u_reset;

     PLNR_L(ego) &= ~u_reset;

     PLNR_L(ego) |= l_set;

     PLNR_U(ego) |= u_set | l_set;

     pln = X(mkplan_d)(ego, p);

     ego->flags = oflags;

     return pln;

}

/*

 * Debugging code:

 */

#ifdef FFTW_DEBUG

static void check(hashtab *ht)

{

     unsigned live = 0;

     unsigned i;

     A(ht->nelem < ht->hashsiz);

     for (i = 0; i < ht->hashsiz; ++i) {

    solution *l = ht->solutions + i; 

    if (LIVEP(l)) 

         ++live; 

     }

     A(ht->nelem == live);