← Back to branch summary

~ubuntu-branches/ubuntu/maverick/blender/maverick

« back to all changes in this revision

Viewing changes to extern/fftw/kernel/planner.c

  • Committer: Bazaar Package Importer
  • Author(s): Khashayar Naderehvandi, Khashayar Naderehvandi, Alessio Treglia
  • Date: 2009-01-22 16:53:59 UTC
  • mfrom: (14.1.1 experimental)
  • Revision ID: james.westby@ubuntu.com-20090122165359-v0996tn7fbit64ni
Tags: 2.48a+dfsg-1ubuntu1
https://launchpad.net/bugs/320045
[ Khashayar Naderehvandi ]
* Merge from debian experimental (LP: #320045), Ubuntu remaining changes:
  - Add patch correcting header file locations.
  - Add libvorbis-dev and libgsm1-dev to Build-Depends.
  - Use avcodec_decode_audio2() in source/blender/src/hddaudio.c

[ Alessio Treglia ]
* Add missing previous changelog entries.

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/fftw/kernel/planner.c
 
1
/*
 
2
 * Copyright (c) 2000 Matteo Frigo
 
3
 * Copyright (c) 2000 Massachusetts Institute of Technology
 
4
 *
 
5
 * This program is free software; you can redistribute it and/or modify
 
6
 * it under the terms of the GNU General Public License as published by
 
7
 * the Free Software Foundation; either version 2 of the License, or
 
8
 * (at your option) any later version.
 
9
 *
 
10
 * This program is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program; if not, write to the Free Software
 
17
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
 *
 
19
 */
 
20
 
 
21
/* $Id: planner.c,v 1.189 2006-01-17 05:17:27 athena Exp $ */
 
22
#include "ifftw.h"
 
23
#include <string.h>
 
24
 
 
25
/* GNU Coding Standards, Sec. 5.2: "Please write the comments in a GNU
 
26
   program in English, because English is the one language that nearly
 
27
   all programmers in all countries can read."
 
28
 
 
29
                    ingemisco tanquam reus
 
30
                    culpa rubet vultus meus
 
31
                    supplicanti parce [rms]
 
32
*/
 
33
 
 
34
#define VALIDP(solution) ((solution)->flags.hash_info & H_VALID)
 
35
#define LIVEP(solution) ((solution)->flags.hash_info & H_LIVE)
 
36
#define SLVNDX(solution) ((solution)->flags.slvndx)
 
37
#define BLISS(flags) (((flags).hash_info) & BLESSING)
 
38
#define INFEASIBLE_SLVNDX ((1U<<BITS_FOR_SLVNDX)-1)
 
39
 
 
40
 
 
41
#define MAXNAM 64  /* maximum length of registrar's name.
 
42
                      Used for reading wisdom.  There is no point
 
43
                      in doing this right */
 
44
 
 
45
 
 
46
#ifdef FFTW_DEBUG
 
47
static void check(hashtab *ht);
 
48
#endif
 
49
 
 
50
/* x <= y */
 
51
#define LEQ(x, y) (((x) & (y)) == (x))
 
52
 
 
53
/* A subsumes B */
 
54
static int subsumes(const flags_t *a, unsigned slvndx_a, const flags_t *b)
 
55
{
 
56
     if (slvndx_a != INFEASIBLE_SLVNDX) {
 
57
          A(a->timelimit_impatience == 0);
 
58
          return (LEQ(a->u, b->u) && LEQ(b->l, a->l));
 
59
     } else {
 
60
          return (LEQ(a->l, b->l) 
 
61
                  && a->timelimit_impatience <= b->timelimit_impatience);
 
62
     }
 
63
}
 
64
 
 
65
static unsigned addmod(unsigned a, unsigned b, unsigned p)
 
66
{
 
67
     /* gcc-2.95/sparc produces incorrect code for the fast version below. */
 
68
#if defined(__sparc__) && defined(__GNUC__)
 
69
     /* slow version  */
 
70
     return (a + b) % p;
 
71
#else
 
72
     /* faster version */
 
73
     unsigned c = a + b;
 
74
     return c >= p ? c - p : c;
 
75
#endif
 
76
}
 
77
 
 
78
/*
 
79
  slvdesc management:
 
80
*/
 
81
static void sgrow(planner *ego)
 
82
{
 
83
     unsigned osiz = ego->slvdescsiz, nsiz = 1 + osiz + osiz / 4;
 
84
     slvdesc *ntab = (slvdesc *)MALLOC(nsiz * sizeof(slvdesc), SLVDESCS);
 
85
     slvdesc *otab = ego->slvdescs;
 
86
     unsigned i;
 
87
 
 
88
     ego->slvdescs = ntab;
 
89
     ego->slvdescsiz = nsiz;
 
90
     for (i = 0; i < osiz; ++i)
 
91
          ntab[i] = otab[i];
 
92
     X(ifree0)(otab);
 
93
}
 
94
 
 
95
static void register_solver(planner *ego, solver *s)
 
96
{
 
97
     slvdesc *n;
 
98
     int kind;
 
99
 
 
100
     if (s) { /* add s to solver list */
 
101
          X(solver_use)(s);
 
102
 
 
103
          A(ego->nslvdesc < INFEASIBLE_SLVNDX);
 
104
          if (ego->nslvdesc >= ego->slvdescsiz)
 
105
               sgrow(ego);
 
106
 
 
107
          n = ego->slvdescs + ego->nslvdesc;
 
108
 
 
109
          n->slv = s;
 
110
          n->reg_nam = ego->cur_reg_nam;
 
111
          n->reg_id = ego->cur_reg_id++;
 
112
          
 
113
          A(strlen(n->reg_nam) < MAXNAM);
 
114
          n->nam_hash = X(hash)(n->reg_nam);
 
115
 
 
116
          kind = s->adt->problem_kind;
 
117
          n->next_for_same_problem_kind = ego->slvdescs_for_problem_kind[kind];
 
118
          ego->slvdescs_for_problem_kind[kind] = ego->nslvdesc;
 
119
 
 
120
          ego->nslvdesc++;
 
121
     }
 
122
}
 
123
 
 
124
static unsigned slookup(planner *ego, char *nam, int id)
 
125
{
 
126
     unsigned h = X(hash)(nam); /* used to avoid strcmp in the common case */
 
127
     FORALL_SOLVERS(ego, s, sp, {
 
128
          UNUSED(s);
 
129
          if (sp->reg_id == id && sp->nam_hash == h
 
130
              && !strcmp(sp->reg_nam, nam))
 
131
               return sp - ego->slvdescs;
 
132
     });
 
133
     return INFEASIBLE_SLVNDX;
 
134
}
 
135
 
 
136
/*
 
137
  md5-related stuff:
 
138
*/
 
139
 
 
140
/* first hash function */
 
141
static unsigned h1(const hashtab *ht, const md5sig s)
 
142
{
 
143
     unsigned h = s[0] % ht->hashsiz;
 
144
     A(h == (s[0] % ht->hashsiz));
 
145
     return h;
 
146
}
 
147
 
 
148
/* second hash function (for double hashing) */
 
149
static unsigned h2(const hashtab *ht, const md5sig s)
 
150
{
 
151
     unsigned h = 1U + s[1] % (ht->hashsiz - 1);
 
152
     A(h == (1U + s[1] % (ht->hashsiz - 1)));
 
153
     return h;
 
154
}
 
155
 
 
156
static void md5hash(md5 *m, const problem *p, const planner *plnr)
 
157
{
 
158
     X(md5begin)(m);
 
159
     X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */
 
160
     X(md5int)(m, plnr->nthr);
 
161
     p->adt->hash(p, m);
 
162
     X(md5end)(m);
 
163
}
 
164
 
 
165
static int md5eq(const md5sig a, const md5sig b)
 
166
{
 
167
     return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3];
 
168
}
 
169
 
 
170
static void sigcpy(const md5sig a, md5sig b)
 
171
{
 
172
     b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3];
 
173
}
 
174
 
 
175
/*
 
176
  memoization routines :
 
177
*/
 
178
 
 
179
/*
 
180
   liber scriptus proferetur
 
181
   in quo totum continetur
 
182
   unde mundus iudicetur
 
183
*/
 
184
struct solution_s {
 
185
     md5sig s;
 
186
     flags_t flags;
 
187
};
 
188
 
 
189
static solution *htab_lookup(hashtab *ht, const md5sig s, 
 
190
                             const flags_t *flagsp)
 
191
{
 
192
     unsigned g, h = h1(ht, s), d = h2(ht, s);
 
193
     solution *best = 0;
 
194
 
 
195
     ++ht->lookup;
 
196
 
 
197
     /* search all entries that match; select the one with
 
198
        the lowest flags.u */
 
199
     /* This loop may potentially traverse the whole table, since at
 
200
        least one element is guaranteed to be !LIVEP, but all elements
 
201
        may be VALIDP.  Hence, we stop after at the first invalid
 
202
        element or after traversing the whole table. */
 
203
     g = h;
 
204
     do {
 
205
          solution *l = ht->solutions + g;
 
206
          ++ht->lookup_iter;
 
207
          if (VALIDP(l)) {
 
208
               if (LIVEP(l)
 
209
                   && md5eq(s, l->s)
 
210
                   && subsumes(&l->flags, SLVNDX(l), flagsp) ) { 
 
211
                    if (!best || LEQ(l->flags.u, best->flags.u))
 
212
                         best = l;
 
213
               }
 
214
          } else 
 
215
               break;
 
216
 
 
217
          g = addmod(g, d, ht->hashsiz);
 
218
     } while (g != h);
 
219
 
 
220
     if (best) 
 
221
          ++ht->succ_lookup;
 
222
     return best;
 
223
}
 
224
 
 
225
static solution *hlookup(planner *ego, const md5sig s, 
 
226
                         const flags_t *flagsp)
 
227
{
 
228
     solution *sol = htab_lookup(&ego->htab_blessed, s, flagsp);
 
229
     if (!sol) sol = htab_lookup(&ego->htab_unblessed, s, flagsp);
 
230
     return sol;
 
231
}
 
232
 
 
233
static void fill_slot(hashtab *ht, const md5sig s, const flags_t *flagsp,
 
234
                      unsigned slvndx, solution *slot)
 
235
{
 
236
     ++ht->insert;
 
237
     ++ht->nelem;
 
238
     A(!LIVEP(slot));
 
239
     slot->flags.u = flagsp->u;
 
240
     slot->flags.l = flagsp->l;
 
241
     slot->flags.timelimit_impatience = flagsp->timelimit_impatience;
 
242
     slot->flags.hash_info |= H_VALID | H_LIVE;
 
243
     SLVNDX(slot) = slvndx;
 
244
 
 
245
     /* keep this check enabled in case we add so many solvers
 
246
        that the bitfield overflows */
 
247
     CK(SLVNDX(slot) == slvndx);     
 
248
     sigcpy(s, slot->s);
 
249
}
 
250
 
 
251
static void kill_slot(hashtab *ht, solution *slot)
 
252
{
 
253
     A(LIVEP(slot)); /* ==> */ A(VALIDP(slot));
 
254
 
 
255
     --ht->nelem;
 
256
     slot->flags.hash_info = H_VALID;
 
257
}
 
258
 
 
259
static void hinsert0(hashtab *ht, const md5sig s, const flags_t *flagsp, 
 
260
                     unsigned slvndx)
 
261
{
 
262
     solution *l;
 
263
     unsigned g, h = h1(ht, s), d = h2(ht, s); 
 
264
 
 
265
     ++ht->insert_unknown;
 
266
 
 
267
     /* search for nonfull slot */
 
268
     for (g = h; ; g = addmod(g, d, ht->hashsiz)) {
 
269
          ++ht->insert_iter;
 
270
          l = ht->solutions + g;
 
271
          if (!LIVEP(l)) break;
 
272
          A((g + d) % ht->hashsiz != h);
 
273
     }
 
274
 
 
275
     fill_slot(ht, s, flagsp, slvndx, l);
 
276
}
 
277
 
 
278
static void rehash(hashtab *ht, unsigned nsiz)
 
279
{
 
280
     unsigned osiz = ht->hashsiz, h;
 
281
     solution *osol = ht->solutions, *nsol;
 
282
 
 
283
     nsiz = (unsigned)X(next_prime)((INT)nsiz);
 
284
     nsol = (solution *)MALLOC(nsiz * sizeof(solution), HASHT);
 
285
     ++ht->nrehash;
 
286
 
 
287
     /* init new table */
 
288
     for (h = 0; h < nsiz; ++h) 
 
289
          nsol[h].flags.hash_info = 0;
 
290
 
 
291
     /* install new table */
 
292
     ht->hashsiz = nsiz;
 
293
     ht->solutions = nsol;
 
294
     ht->nelem = 0;
 
295
 
 
296
     /* copy table */
 
297
     for (h = 0; h < osiz; ++h) {
 
298
          solution *l = osol + h;
 
299
          if (LIVEP(l))
 
300
               hinsert0(ht, l->s, &l->flags, SLVNDX(l));
 
301
     }
 
302
 
 
303
     X(ifree0)(osol);
 
304
}
 
305
 
 
306
static unsigned minsz(unsigned nelem)
 
307
{
 
308
     return 1U + nelem + nelem / 8U;
 
309
}
 
310
 
 
311
static unsigned nextsz(unsigned nelem)
 
312
{
 
313
     return minsz(minsz(nelem));
 
314
}
 
315
 
 
316
static void hgrow(hashtab *ht)
 
317
{
 
318
     unsigned nelem = ht->nelem;
 
319
     if (minsz(nelem) >= ht->hashsiz)
 
320
          rehash(ht, nextsz(nelem));
 
321
}
 
322
 
 
323
#if 0
 
324
/* shrink the hash table, never used */
 
325
static void hshrink(hashtab *ht)
 
326
{
 
327
     unsigned nelem = ht->nelem;
 
328
     /* always rehash after deletions */
 
329
     rehash(ht, nextsz(nelem));
 
330
}
 
331
#endif
 
332
 
 
333
static void htab_insert(hashtab *ht, const md5sig s, const flags_t *flagsp,
 
334
                        unsigned slvndx)
 
335
{
 
336
     unsigned g, h = h1(ht, s), d = h2(ht, s);
 
337
     solution *first = 0;
 
338
 
 
339
     /* Remove all entries that are subsumed by the new one.  */
 
340
     /* This loop may potentially traverse the whole table, since at
 
341
        least one element is guaranteed to be !LIVEP, but all elements
 
342
        may be VALIDP.  Hence, we stop after at the first invalid
 
343
        element or after traversing the whole table. */
 
344
     g = h;
 
345
     do {
 
346
          solution *l = ht->solutions + g;
 
347
          ++ht->insert_iter;
 
348
          if (VALIDP(l)) {
 
349
               if (LIVEP(l) && md5eq(s, l->s)) {
 
350
                    if (subsumes(flagsp, slvndx, &l->flags)) {
 
351
                         if (!first) first = l;
 
352
                         kill_slot(ht, l);
 
353
                    } else {
 
354
                         /* It is an error to insert an element that
 
355
                            is subsumed by an existing entry. */
 
356
                         A(!subsumes(&l->flags, SLVNDX(l), flagsp));
 
357
                    }
 
358
               }
 
359
          } else 
 
360
               break;
 
361
 
 
362
          g = addmod(g, d, ht->hashsiz);
 
363
     } while (g != h);
 
364
 
 
365
     if (first) {
 
366
          /* overwrite FIRST */
 
367
          fill_slot(ht, s, flagsp, slvndx, first);
 
368
     } else {
 
369
          /* create a new entry */
 
370
          hgrow(ht);
 
371
          hinsert0(ht, s, flagsp, slvndx);
 
372
     }
 
373
}
 
374
 
 
375
static void hinsert(planner *ego, const md5sig s, const flags_t *flagsp, 
 
376
                    unsigned slvndx)
 
377
{
 
378
     htab_insert(BLISS(*flagsp) ? &ego->htab_blessed : &ego->htab_unblessed,
 
379
                 s, flagsp, slvndx );
 
380
}
 
381
 
 
382
 
 
383
static void invoke_hook(planner *ego, plan *pln, const problem *p, 
 
384
                        int optimalp)
 
385
{
 
386
     if (ego->hook)
 
387
          ego->hook(ego, pln, p, optimalp);
 
388
}
 
389
 
 
390
double X(iestimate_cost)(const plan *pln)
 
391
{
 
392
     return 0.0
 
393
          + pln->ops.add
 
394
          + pln->ops.mul
 
395
 
 
396
#if HAVE_FMA
 
397
          + pln->ops.fma
 
398
#else
 
399
          + 2 * pln->ops.fma
 
400
#endif
 
401
 
 
402
          + pln->ops.other;
 
403
}
 
404
 
 
405
static void evaluate_plan(planner *ego, plan *pln, const problem *p)
 
406
{
 
407
     if (ESTIMATEP(ego) || !BELIEVE_PCOSTP(ego) || pln->pcost == 0.0) {
 
408
          ego->nplan++;
 
409
 
 
410
          if (ESTIMATEP(ego)) {
 
411
          estimate:
 
412
               /* heuristic */
 
413
               pln->pcost = X(iestimate_cost)(pln);
 
414
               ego->epcost += pln->pcost;
 
415
          } else {
 
416
               double t = X(measure_execution_time)(pln, p);
 
417
 
 
418
               if (t < 0) {  /* unavailable cycle counter */
 
419
                    /* Real programmers can write FORTRAN in any language */
 
420
                    goto estimate;
 
421
               }
 
422
 
 
423
               pln->pcost = t;
 
424
               ego->pcost += t;
 
425
               ego->need_timeout_check = 1;
 
426
          }
 
427
     }
 
428
     
 
429
     invoke_hook(ego, pln, p, 0);
 
430
}
 
431
 
 
432
/* maintain dynamic scoping of flags, nthr: */
 
433
static plan *invoke_solver(planner *ego, problem *p, solver *s, 
 
434
                           const flags_t *nflags)
 
435
{
 
436
     flags_t flags = ego->flags;
 
437
     int nthr = ego->nthr;
 
438
     plan *pln;
 
439
     ego->flags = *nflags;
 
440
     PLNR_TIMELIMIT_IMPATIENCE(ego) = 0;
 
441
     A(p->adt->problem_kind == s->adt->problem_kind);
 
442
     pln = s->adt->mkplan(s, p, ego);
 
443
     ego->nthr = nthr;
 
444
     ego->flags = flags;
 
445
     return pln;
 
446
}
 
447
 
 
448
/* maintain the invariant TIMED_OUT ==> NEED_TIMEOUT_CHECK */
 
449
static int timeout_p(planner *ego)
 
450
{
 
451
     /* do not timeout when estimating.  First, the estimator is the
 
452
        planner of last resort.  Second, calling X(elapsed_since)() is
 
453
        slower than estimating */
 
454
     if (!ESTIMATEP(ego)) {
 
455
          /* do not assume that X(elapsed_since)() is monotonic */
 
456
          if (ego->timed_out) {
 
457
               A(ego->need_timeout_check);
 
458
               return 1;
 
459
          }
 
460
 
 
461
          if (ego->timelimit >= 0 &&
 
462
              X(elapsed_since)(ego->start_time) >= ego->timelimit) {
 
463
               ego->timed_out = 1;
 
464
               ego->need_timeout_check = 1;
 
465
               return 1;
 
466
          }
 
467
     }
 
468
 
 
469
     A(!ego->timed_out);
 
470
     ego->need_timeout_check = 0;
 
471
     return 0;
 
472
}
 
473
 
 
474
static plan *search0(planner *ego, problem *p, unsigned *slvndx, 
 
475
                     const flags_t *flagsp)
 
476
{
 
477
     plan *best = 0;
 
478
     int best_not_yet_timed = 1;
 
479
 
 
480
     /* Do not start a search if the planner timed out. This check is
 
481
        necessary, lest the relaxation mechanism kick in */
 
482
     if (timeout_p(ego))
 
483
          return 0;
 
484
 
 
485
     FORALL_SOLVERS_OF_KIND(p->adt->problem_kind, ego, s, sp, {
 
486
          plan *pln;
 
487
 
 
488
          pln = invoke_solver(ego, p, s, flagsp);
 
489
 
 
490
          if (ego->need_timeout_check) 
 
491
               if (timeout_p(ego)) {
 
492
                    X(plan_destroy_internal)(pln);
 
493
                    X(plan_destroy_internal)(best);
 
494
                    return 0;
 
495
               }
 
496
 
 
497
          if (pln) {
 
498
               /* read COULD_PRUNE_NOW_P because PLN may be destroyed
 
499
                  before we use COULD_PRUNE_NOW_P */
 
500
               int could_prune_now_p = pln->could_prune_now_p;
 
501
 
 
502
               if (best) {
 
503
                    if (best_not_yet_timed) {
 
504
                         evaluate_plan(ego, best, p);
 
505
                         best_not_yet_timed = 0;
 
506
                    }
 
507
                    evaluate_plan(ego, pln, p);
 
508
                    if (pln->pcost < best->pcost) {
 
509
                         X(plan_destroy_internal)(best);
 
510
                         best = pln;
 
511
                         *slvndx = sp - ego->slvdescs;
 
512
                    } else {
 
513
                         X(plan_destroy_internal)(pln);
 
514
                    }
 
515
               } else {
 
516
                    best = pln;
 
517
                    *slvndx = sp - ego->slvdescs;
 
518
               }
 
519
 
 
520
               if (ALLOW_PRUNINGP(ego) && could_prune_now_p) 
 
521
                    break;
 
522
          }
 
523
     });
 
524
 
 
525
     return best;
 
526
}
 
527
 
 
528
static plan *search(planner *ego, problem *p, unsigned *slvndx, 
 
529
                    flags_t *flagsp)
 
530
{
 
531
     plan *pln = 0;
 
532
     unsigned i;
 
533
 
 
534
     /* relax impatience in this order: */
 
535
     static const unsigned relax_tab[] = {
 
536
          0, /* relax nothing */
 
537
          NO_VRECURSE,
 
538
          NO_FIXED_RADIX_LARGE_N,
 
539
          NO_SLOW,
 
540
          NO_UGLY
 
541
     };
 
542
 
 
543
     unsigned l_orig = flagsp->l;
 
544
     unsigned x = flagsp->u;
 
545
 
 
546
     /* guaranteed to be different from X */
 
547
     unsigned last_x = ~x; 
 
548
 
 
549
     for (i = 0; i < sizeof(relax_tab) / sizeof(relax_tab[0]); ++i) {
 
550
          if (LEQ(l_orig, x & ~relax_tab[i]))
 
551
               x = x & ~relax_tab[i];
 
552
 
 
553
          if (x != last_x) {
 
554
               last_x = x;
 
555
               flagsp->l = x;
 
556
               pln = search0(ego, p, slvndx, flagsp);
 
557
               if (pln) break;
 
558
          }
 
559
     }
 
560
 
 
561
     if (!pln) {
 
562
          /* search [L_ORIG, U] */
 
563
          if (l_orig != last_x) {
 
564
               last_x = l_orig;
 
565
               flagsp->l = l_orig;
 
566
               pln = search0(ego, p, slvndx, flagsp);
 
567
          }
 
568
     }
 
569
 
 
570
     return pln;
 
571
}
 
572
 
 
573
#define CHECK_FOR_BOGOSITY                      \
 
574
     if (ego->wisdom_state == WISDOM_IS_BOGUS)  \
 
575
          goto wisdom_is_bogus
 
576
 
 
577
static plan *mkplan(planner *ego, problem *p)
 
578
{
 
579
     plan *pln;
 
580
     md5 m;
 
581
     unsigned slvndx;
 
582
     flags_t flags_of_solution;
 
583
     solution *sol;
 
584
     solver *s;
 
585
 
 
586
     ASSERT_ALIGNED_DOUBLE;
 
587
     A(LEQ(PLNR_L(ego), PLNR_U(ego)));
 
588
 
 
589
     if (ESTIMATEP(ego))
 
590
          PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; /* canonical form */
 
591
 
 
592
 
 
593
#ifdef FFTW_DEBUG
 
594
     check(&ego->htab_blessed);
 
595
     check(&ego->htab_unblessed);
 
596
#endif
 
597
 
 
598
     pln = 0;
 
599
 
 
600
     CHECK_FOR_BOGOSITY;
 
601
 
 
602
     ego->timed_out = 0;
 
603
 
 
604
     ++ego->nprob;
 
605
     md5hash(&m, p, ego);
 
606
 
 
607
     flags_of_solution = ego->flags;
 
608
 
 
609
     if ((ego->wisdom_state != WISDOM_IGNORE_ALL) &&
 
610
         (sol = hlookup(ego, m.s, &flags_of_solution))) { 
 
611
          /* wisdom is acceptable */
 
612
          wisdom_state_t owisdom_state = ego->wisdom_state;
 
613
          slvndx = SLVNDX(sol);
 
614
 
 
615
          if (slvndx == INFEASIBLE_SLVNDX) {
 
616
               if (ego->wisdom_state == WISDOM_IGNORE_INFEASIBLE)
 
617
                    goto do_search;
 
618
               else
 
619
                    return 0;   /* known to be infeasible */
 
620
          }
 
621
 
 
622
          flags_of_solution = sol->flags;
 
623
 
 
624
          /* inherit blessing either from wisdom
 
625
             or from the planner */
 
626
          flags_of_solution.hash_info |= BLISS(ego->flags);
 
627
 
 
628
          ego->wisdom_state = WISDOM_ONLY;
 
629
 
 
630
          s = ego->slvdescs[slvndx].slv;
 
631
          if (p->adt->problem_kind != s->adt->problem_kind)
 
632
               goto wisdom_is_bogus;
 
633
          
 
634
          pln = invoke_solver(ego, p, s, &flags_of_solution);
 
635
 
 
636
          CHECK_FOR_BOGOSITY;     /* catch error in child solvers */
 
637
 
 
638
          sol = 0; /* Paranoia: SOL may be dangling after
 
639
                      invoke_solver(); make sure we don't accidentally
 
640
                      reuse it. */
 
641
 
 
642
          if (!pln)
 
643
               goto wisdom_is_bogus;
 
644
 
 
645
          ego->wisdom_state = owisdom_state;
 
646
 
 
647
          goto skip_search;
 
648
     }
 
649
 
 
650
 do_search:
 
651
     /* cannot search in WISDOM_ONLY mode */
 
652
     if (ego->wisdom_state == WISDOM_ONLY)
 
653
          goto wisdom_is_bogus;
 
654
 
 
655
     flags_of_solution = ego->flags;
 
656
     pln = search(ego, p, &slvndx, &flags_of_solution);
 
657
     CHECK_FOR_BOGOSITY;          /* catch error in child solvers */
 
658
 
 
659
     if (ego->timed_out) {
 
660
          A(!pln);
 
661
          if (PLNR_TIMELIMIT_IMPATIENCE(ego) != 0) {
 
662
               /* record (below) that this plan has failed because of
 
663
                  timeout */
 
664
               flags_of_solution.hash_info |= BLESSING;
 
665
          } else {
 
666
               /* this is not the top-level problem or timeout is not
 
667
                  active: record no wisdom. */
 
668
               return 0;
 
669
          }
 
670
     } else {
 
671
          /* canonicalize to infinite timeout */
 
672
          flags_of_solution.timelimit_impatience = 0;
 
673
     }
 
674
 
 
675
 skip_search:
 
676
     if (ego->wisdom_state == WISDOM_NORMAL ||
 
677
         ego->wisdom_state == WISDOM_ONLY) {
 
678
          if (pln) {
 
679
               hinsert(ego, m.s, &flags_of_solution, slvndx);
 
680
               invoke_hook(ego, pln, p, 1);
 
681
          } else {
 
682
               hinsert(ego, m.s, &flags_of_solution, INFEASIBLE_SLVNDX);
 
683
          }
 
684
     }
 
685
 
 
686
     return pln;
 
687
 
 
688
 wisdom_is_bogus:
 
689
     X(plan_destroy_internal)(pln);
 
690
     ego->wisdom_state = WISDOM_IS_BOGUS;
 
691
     return 0;
 
692
}
 
693
 
 
694
static void htab_destroy(hashtab *ht)
 
695
{
 
696
     X(ifree)(ht->solutions);
 
697
     ht->solutions = 0;
 
698
     ht->nelem = 0U;
 
699
}
 
700
 
 
701
static void mkhashtab(hashtab *ht)
 
702
{
 
703
     ht->nrehash = 0;
 
704
     ht->succ_lookup = ht->lookup = ht->lookup_iter = 0;
 
705
     ht->insert = ht->insert_iter = ht->insert_unknown = 0;
 
706
 
 
707
     ht->solutions = 0;
 
708
     ht->hashsiz = ht->nelem = 0U;
 
709
     hgrow(ht);                 /* so that hashsiz > 0 */
 
710
}
 
711
 
 
712
/* destroy hash table entries.  If FORGET_EVERYTHING, destroy the whole
 
713
   table.  If FORGET_ACCURSED, then destroy entries that are not blessed. */
 
714
static void forget(planner *ego, amnesia a)
 
715
{
 
716
     switch (a) {
 
717
         case FORGET_EVERYTHING:
 
718
              htab_destroy(&ego->htab_blessed);
 
719
              mkhashtab(&ego->htab_blessed);
 
720
              /* fall through */
 
721
         case FORGET_ACCURSED:
 
722
              htab_destroy(&ego->htab_unblessed);
 
723
              mkhashtab(&ego->htab_unblessed);
 
724
              break;
 
725
         default:
 
726
              break;
 
727
     }
 
728
}
 
729
 
 
730
/* FIXME: what sort of version information should we write? */
 
731
#define WISDOM_PREAMBLE PACKAGE "-" VERSION " " STRINGIZE(X(wisdom))
 
732
static const char stimeout[] = "TIMEOUT";
 
733
 
 
734
/* tantus labor non sit cassus */
 
735
static void exprt(planner *ego, printer *p)
 
736
{
 
737
     unsigned h;
 
738
     hashtab *ht = &ego->htab_blessed;
 
739
 
 
740
     p->print(p, "(" WISDOM_PREAMBLE "\n");
 
741
     for (h = 0; h < ht->hashsiz; ++h) {
 
742
          solution *l = ht->solutions + h;
 
743
          if (LIVEP(l)) {
 
744
               const char *reg_nam;
 
745
               int reg_id;
 
746
 
 
747
               if (SLVNDX(l) == INFEASIBLE_SLVNDX) {
 
748
                    reg_nam = stimeout;
 
749
                    reg_id = 0;
 
750
               } else {
 
751
                    slvdesc *sp = ego->slvdescs + SLVNDX(l);
 
752
                    reg_nam = sp->reg_nam;
 
753
                    reg_id = sp->reg_id;
 
754
               }
 
755
 
 
756
               /* qui salvandos salvas gratis
 
757
                  salva me fons pietatis */
 
758
               p->print(p, "  (%s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)\n",
 
759
                        reg_nam, reg_id, 
 
760
                        l->flags.l, l->flags.u, l->flags.timelimit_impatience, 
 
761
                        l->s[0], l->s[1], l->s[2], l->s[3]);
 
762
          }
 
763
     }
 
764
     p->print(p, ")\n");
 
765
}
 
766
 
 
767
/* mors stupebit et natura
 
768
   cum resurget creatura */
 
769
static int imprt(planner *ego, scanner *sc)
 
770
{
 
771
     char buf[MAXNAM + 1];
 
772
     md5uint sig[4];
 
773
     unsigned l, u, timelimit_impatience;
 
774
     flags_t flags;
 
775
     int reg_id;
 
776
     unsigned slvndx;
 
777
     hashtab *ht = &ego->htab_blessed;
 
778
     hashtab old;
 
779
 
 
780
     if (!sc->scan(sc, "(" WISDOM_PREAMBLE))
 
781
          return 0; /* don't need to restore hashtable */
 
782
 
 
783
     /* make a backup copy of the hash table (cache the hash) */
 
784
     {
 
785
          unsigned h, hsiz = ht->hashsiz;
 
786
          old = *ht;
 
787
          old.solutions = (solution *)MALLOC(hsiz * sizeof(solution), HASHT);
 
788
          for (h = 0; h < hsiz; ++h)
 
789
               old.solutions[h] = ht->solutions[h];
 
790
     }
 
791
 
 
792
     while (1) {
 
793
          if (sc->scan(sc, ")"))
 
794
               break;
 
795
 
 
796
          /* qua resurget ex favilla */
 
797
          if (!sc->scan(sc, "(%*s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)",
 
798
                        MAXNAM, buf, &reg_id, &l, &u, &timelimit_impatience,
 
799
                        sig + 0, sig + 1, sig + 2, sig + 3))
 
800
               goto bad;
 
801
 
 
802
          if (!strcmp(buf, stimeout) && reg_id == 0) {
 
803
               slvndx = INFEASIBLE_SLVNDX;
 
804
          } else {
 
805
               if (timelimit_impatience != 0)
 
806
                    goto bad;
 
807
 
 
808
               slvndx = slookup(ego, buf, reg_id);
 
809
               if (slvndx == INFEASIBLE_SLVNDX)
 
810
                    goto bad;
 
811
          }
 
812
 
 
813
          /* inter oves locum praesta */
 
814
          flags.l = l;
 
815
          flags.u = u;
 
816
          flags.timelimit_impatience = timelimit_impatience;
 
817
          flags.hash_info = BLESSING;
 
818
 
 
819
          CK(flags.l == l);
 
820
          CK(flags.u == u);
 
821
          CK(flags.timelimit_impatience == timelimit_impatience);
 
822
 
 
823
          hinsert(ego, sig, &flags, slvndx);
 
824
     }
 
825
 
 
826
     X(ifree0)(old.solutions);
 
827
     return 1;
 
828
 
 
829
 bad:
 
830
     /* ``The wisdom of FFTW must be above suspicion.'' */
 
831
     X(ifree0)(ht->solutions);
 
832
     *ht = old;
 
833
     return 0;
 
834
}
 
835
 
 
836
/*
 
837
 * create a planner
 
838
 */
 
839
planner *X(mkplanner)(void)
 
840
{
 
841
     int i;
 
842
 
 
843
     static const planner_adt padt = {
 
844
          register_solver, mkplan, forget, exprt, imprt
 
845
     };
 
846
 
 
847
     planner *p = (planner *) MALLOC(sizeof(planner), PLANNERS);
 
848
 
 
849
     p->adt = &padt;
 
850
     p->nplan = p->nprob = 0;
 
851
     p->pcost = p->epcost = 0.0;
 
852
     p->hook = 0;
 
853
     p->cur_reg_nam = 0;
 
854
     p->wisdom_state = WISDOM_NORMAL;
 
855
 
 
856
     p->slvdescs = 0;
 
857
     p->nslvdesc = p->slvdescsiz = 0;
 
858
 
 
859
     p->flags.l = 0;
 
860
     p->flags.u = 0;
 
861
     p->flags.timelimit_impatience = 0;
 
862
     p->flags.hash_info = 0;
 
863
     p->nthr = 1;
 
864
     p->need_timeout_check = 1;
 
865
     p->timelimit = -1;
 
866
 
 
867
     mkhashtab(&p->htab_blessed);
 
868
     mkhashtab(&p->htab_unblessed);
 
869
 
 
870
     for (i = 0; i < PROBLEM_LAST; ++i)
 
871
          p->slvdescs_for_problem_kind[i] = -1;
 
872
 
 
873
     return p;
 
874
}
 
875
 
 
876
void X(planner_destroy)(planner *ego)
 
877
{
 
878
     /* destroy hash table */
 
879
     htab_destroy(&ego->htab_blessed);
 
880
     htab_destroy(&ego->htab_unblessed);
 
881
 
 
882
     /* destroy solvdesc table */
 
883
     FORALL_SOLVERS(ego, s, sp, {
 
884
          UNUSED(sp);
 
885
          X(solver_destroy)(s);
 
886
     });
 
887
 
 
888
     X(ifree0)(ego->slvdescs);
 
889
     X(ifree)(ego); /* dona eis requiem */
 
890
}
 
891
 
 
892
plan *X(mkplan_d)(planner *ego, problem *p)
 
893
{
 
894
     plan *pln = ego->adt->mkplan(ego, p);
 
895
     X(problem_destroy)(p);
 
896
     return pln;
 
897
}
 
898
 
 
899
/* like X(mkplan_d), but sets/resets flags as well */
 
900
plan *X(mkplan_f_d)(planner *ego, problem *p, 
 
901
                    unsigned l_set, unsigned u_set, unsigned u_reset)
 
902
{
 
903
     flags_t oflags = ego->flags;
 
904
     plan *pln;
 
905
 
 
906
     PLNR_U(ego) &= ~u_reset;
 
907
     PLNR_L(ego) &= ~u_reset;
 
908
     PLNR_L(ego) |= l_set;
 
909
     PLNR_U(ego) |= u_set | l_set;
 
910
     pln = X(mkplan_d)(ego, p);
 
911
     ego->flags = oflags;
 
912
     return pln;
 
913
}
 
914
 
 
915
/*
 
916
 * Debugging code:
 
917
 */
 
918
#ifdef FFTW_DEBUG
 
919
static void check(hashtab *ht)
 
920
{
 
921
     unsigned live = 0;
 
922
     unsigned i;
 
923
 
 
924
     A(ht->nelem < ht->hashsiz);
 
925
 
 
926
     for (i = 0; i < ht->hashsiz; ++i) {
 
927
          solution *l = ht->solutions + i; 
 
928
          if (LIVEP(l)) 
 
929
               ++live; 
 
930
     }
 
931
 
 
932
     A(ht->nelem == live);
 
933
 
 
934
     for (i = 0; i < ht->hashsiz; ++i) {
 
935
          solution *l1 = ht->solutions + i; 
 
936
          int foundit = 0;
 
937
          if (LIVEP(l1)) {
 
938
               unsigned g, h = h1(ht, l1->s), d = h2(ht, l1->s);
 
939
 
 
940
               g = h;
 
941
               do {
 
942
                    solution *l = ht->solutions + g;
 
943
                    if (VALIDP(l)) {
 
944
                         if (l1 == l)
 
945
                              foundit = 1;
 
946
                         else if (LIVEP(l) && md5eq(l1->s, l->s)) {
 
947
                              A(!subsumes(&l->flags, SLVNDX(l), &l1->flags));
 
948
                              A(!subsumes(&l1->flags, SLVNDX(l1), &l->flags));
 
949
                         }
 
950
                    } else 
 
951
                         break;
 
952
                    g = addmod(g, d, ht->hashsiz);
 
953
               } while (g != h);
 
954
 
 
955
               A(foundit);
 
956
          }
 
957
     }
 
958
}
 
959
#endif