/* * CHEST, chess analyst. For Copyright notice read file "COPYRIGHT". * * $Source: /home/heiner/ca/chest/RCS/acm.c,v $ * $Id: acm.c,v 3.25 1999/12/04 23:07:17 heiner Exp $ * * Adaptive chess memory */ #include "bsd.h" #include "types.h" #include "board.h" #include "move.h" #include "stats.h" #include #include "acm.h" #if ! PROD_LEV # define ACM_STATS 1 /* switch on statistics */ # define ACM_DBG 1 /* switch on local debugging */ #else # define ACM_STATS 0 /* switch off statistics */ # define ACM_DBG 0 /* switch off local debugging */ #endif #undef THIS_STATS #define THIS_STATS ACM_STATS #include "statsupp.h" #if ACM_DBG static int acm_dbg = 0; /* local debug level */ # define IFDBG(n,x) if( acm_dbg > (n) ) { x } #else /* ! ACM_DBG */ # define IFDBG(n,x) /* empty */ #endif /* ! ACM_DBG */ Eximpl int f_pppsol = 0; /* "print" positive partial sols */ static unsigned ppp_info = ACM_INFO(2, TRUE); /* min needed */ static int ppp_icnt = 0; /* already printed */ /* FFS: am start einer aufgabe zuruecksetzen */ /* * We know too different ways to allocate our cache memory: * * - static allocation: (ACM_DYN==0) * This is more efficient, and does not need any malloc(). * The authors prefer this mode. * The size of the cache is decided at compile time, * by importing either of: ACM_SLOTS or ACM_MEGS. * The compile time conversion ACM_MEGS --> ACM_SLOTS is done in "acmsize.h". * * - dynamic allocation: (ACM_DYN==1) * No statically allocated memory. * During run time, if using this module at all (i.e. acm_start() is called), * we try to allocate memory via malloc(). The amount (in MB) is specified * in "f_megs_want". * The manifests ACM_SLOTS and ACM_MEGS now are just the defaults. * This mode is useful for distributing a binary: another machine may * have another amount of available physical memory. * * The effective number of slots is used as modulus for the hash code, * and should be a prime (NOT a power of 2). * FFS: if using ZHASH we may like powers of 2. * * When dynamically allocating memory, we must assure that all "mn_hash" * are cleared (set to zero), to indicate free slots. * Therefore, we use "calloc" instead of "malloc", hoping, that the * implementation will not really need to explicitly clearing the memory, * but rather get an already cleared memory from the kernel. * Otherwise, ACM_CALLOC=0 may be defined from outside, and we use * plain "malloc" and clear the "mn_hash" ourselves. * * Each entry is considered to occupy 40 bytes, i.e. 25000 nodes per Mbyte. */ #include "acmsize.h" /* defines ACM_SLOTS */ typedef unsigned long AcmInx; /* slot index */ #define ACM_MIN_SLOTS 1000 /* CF: minimum meaningful */ #define ACM_XTEST 5 /* CF: #(additional slot searches) */ #define ACM_2PRIM 33889 /* secondary prime */ #if ACM_DYN # include /* malloc/calloc */ Eximpl long f_megs_want = -1L; /* -1 == default */ static AcmNode *acm__ptr = 0; static AcmInx acm__slots = 0; /* so many allocated */ # define allslots acm__ptr # define ACM_EFF_SLOTS acm__slots # ifndef ACM_CALLOC # define ACM_CALLOC 1 /* CF: calloc instead of malloc */ # endif #else /* ! ACM_DYN */ I0static AcmNode acm__allslots[ACM_SLOTS]; # define allslots acm__allslots # define ACM_EFF_SLOTS ACM_SLOTS #endif /* ! ACM_DYN */ #define acm_slotnum(h) (((unsigned long)(h)) % ACM_EFF_SLOTS) #define acm_slotoff(h) (((unsigned long)(h)) / ACM_EFF_SLOTS) /* * We collect aproximate cost notifications via acm_note() per info, * and use the average value to calculate an overall saving. */ static AnaCost sum_icost[256] = {0}; /* [info] cost sum */ static Counter cnt_icost[256]; /* [info] so many summands */ static AnaCost apx_saved = 0; /* apx. costs saved by "acm" */ #if ACM_STATS static Counter sc_entered; /* into acm cache */ static Counter sc_unlink; /* deleted (overwritten) */ static Counter sc_search[2]; /* [search/snoop] */ static Counter sc_found[2]; /* [search/snoop] */ static Counter sc_cmp; /* compared contents */ static Counter sc_imade[256]; /* by info: created */ static Counter sc_iused[256]; /* by info: recalled */ static Counter sc_iupgr[256]; /* by info: upgraded */ static Counter sc_iforg[256]; /* by info: forgotten */ #endif /* ! ACM_STATS */ /* * For conditional clearing we have to track the active type of job and * color to move, since they are not (always) represented in every node. */ static int g_acm_tomove = -1; /* not yet restricted */ static int g_acm_jobtype = -1; /* not yet restricted */ Eximpl double acm_speed(void) { /* Speed computation is a bit funny. What we want is "would have done" / * "really done" Note that "apx_ovhd" is contained in "apx_cost". */ #define OVHD_WEIGHT 0.4 /* (pi * thumb) */ if (apx_cost) { double would; would = (double) apx_cost; would += (double) apx_saved; would -= (double) apx_ovhd *OVHD_WEIGHT; return would / (double) apx_cost; } return 1.0; /* FFS */ } #if ! PROD_LEV Eximpl Counter acm_cnt_in(void) { return sc_entered; } Eximpl Counter acm_cnt_out(void) { return sc_unlink; } #endif /* ! PROD_LEV */ /* * acm_stats() * Print the collected acm statistics. */ Eximpl void /* ARGSUSED */ acm_stats(TimeSecs secs) { /* total (user) time */ #if ACM_STATS register int i; register int n; register Counter searched; Counter alive; Counter nfree; if (f_stats <= 0) { return; } printf("acm statistics:\n"); alive = sc_entered - sc_unlink; nfree = (Counter) ACM_EFF_SLOTS - alive; searched = sc_search[0] + sc_search[1]; if (searched) { show_scs(0, 8, sc_search[0], "/"); show_scs(0, 8, sc_search[1], " searched\n"); show_scs(0, 8, sc_found[0], "/"); show_scs(0, 8, sc_found[1], " found"); printf(" (%4.1f/%4.1f), ", percent(sc_found[0], sc_search[0]), percent(sc_found[1], sc_search[1]) ); show_scs(1, 7, sc_cmp, " compared"); if (sc_found[0] || sc_found[1]) { printf(" [%5.3f/found]", (double) sc_cmp / ((double) sc_found[0] + (double) sc_found[1])); } printf("\n"); } show_scs(0, 8, sc_entered, "/"); show_scs(0, 8, sc_unlink, " in/out "); show_scs(1, 7, alive, " alive,"); show_scs(1, 7, nfree, " free"); printf("\n"); if (apx_cost) { printf("apx costs: done %.0f", (double) apx_cost); printf(", saved %.0f (%5.3f)", (double) apx_saved, (double) apx_saved / (double) apx_cost); printf(", ovhd %.0f", (double) apx_ovhd); printf(", speed %.2f", acm_speed()); printf("\n"); if (secs) { printf("cost done per sec =%9.1f\n", ((double) apx_cost) / secs); } } if (searched) { static Counter *arrs[4] = {sc_imade, sc_iused, sc_iupgr, sc_iforg}; static char *nams[4] = {"made", "used", "upgr", "forg"}; #define minL 5 /* minimum print length of a single counter */ #define maxC 99999 /* (10 ** minL) - 1 */ int lens[8]; Flag noupgr1; register int itop; itop = ACM_IDEP(256); for (i = itop; --i >= 0;) { register int i0, i1; i0 = ACM_INFO(i, 0); i1 = ACM_INFO(i, 1); if (sc_imade[i0] || sc_iused[i0] || sc_iupgr[i0] || sc_iforg[i0] || sc_imade[i1] || sc_iused[i1] || sc_iupgr[i1] || sc_iforg[i1]) { break; } itop = i; } noupgr1 = TRUE; for (i = 0; i < itop; ++i) { if (sc_iupgr[ACM_INFO(i, 1)]) { noupgr1 = FALSE; break; } } for (n = 0; n < 8; ++n) { lens[n] = minL; } for (i = 0; i < itop; ++i) { register int i0, i1; register int len; i0 = ACM_INFO(i, 0); i1 = ACM_INFO(i, 1); for (n = 0; n < 4; ++n) { if (arrs[n][i0] > maxC) { len = dec_length(arrs[n][i0]); if (len > lens[n]) lens[n] = len; } if (arrs[n][i1] > maxC) { len = dec_length(arrs[n][i1]); if (len > lens[n + 4]) lens[n + 4] = len; } } } printf("info "); for (n = 0; n < 4; ++n) { printf("%*s-", lens[n + 0], nams[n]); } printf(" "); for (n = 0; n < 4; ++n) { if (noupgr1 && (arrs[n] == sc_iupgr)) { continue; } printf("%*s+", lens[n + 4], nams[n]); } printf("\n"); for (i = 0; i < itop; ++i) { register int i0, i1; i0 = ACM_INFO(i, 0); i1 = ACM_INFO(i, 1); if (sc_imade[i0] || sc_iused[i0] || sc_iupgr[i0] || sc_iforg[i0] || sc_imade[i1] || sc_iused[i1] || sc_iupgr[i1] || sc_iforg[i1] ) { printf("%4d ", i); for (n = 0; n < 4; ++n) { show_sc(1, lens[n + 0], arrs[n][i0]); } printf(" "); for (n = 0; n < 4; ++n) { if (noupgr1 && (arrs[n] == sc_iupgr)) { continue; } show_sc(1, lens[n + 4], arrs[n][i1]); } printf("\n"); } } #undef minL #undef maxC } #if 1 if (searched) { register int itop; printf("%4s %10s %11s %12s %10s %11s %12s\n", "info", "cnt-", "cost-", "avg-", "cnt+", "cost+", "avg+"); itop = ACM_IDEP(256); for (i = 0; i < itop; ++i) { register int i0, i1; i0 = ACM_INFO(i, 0); i1 = ACM_INFO(i, 1); if (cnt_icost[i0] || cnt_icost[i1]) { printf("%4d", i); show_sc(1, 10, cnt_icost[i0]); printf(" %11.0f", (double) sum_icost[i0]); printf(" %12.1f", cnt_icost[i0] ? (double) sum_icost[i0] / (double) cnt_icost[i0] : 0.0); show_sc(1, 10, cnt_icost[i1]); printf(" %11.0f", (double) sum_icost[i1]); printf(" %12.1f", cnt_icost[i1] ? (double) sum_icost[i1] / (double) cnt_icost[i1] : 0.0); printf("\n"); } } } #endif if ((f_stats > 3) && ACM_EFF_SLOTS) { register int u = 0; register int c = 0; register int sum = 0; register AcmInx slot; printf("acm slot usage:\n"); for (n = 0, slot = 0; slot < ACM_EFF_SLOTS; ++slot) { u = (allslots[slot].mn_hash != 0); c <<= 1; c += u; sum += u; if ((slot & 3) == 3) { if (n == 0) printf("%6d\t", (int) (slot & ~3)); printf("%x", c); c = 0; if (++n >= 60) { printf(" %2d\n", sum); n = 0; sum = 0; } } } if (n) printf("\n"); } printf("end of acm statistics.\n"); #endif /* ACM_STATS */ } static void acm_fatal(void) { panic("Fatal ACM error"); } static void acm_1_line(uint32 uv, const char *spc) { union { uint8 byts[4]; uint32 line; } buf; register int i; register unsigned v; buf.line = uv; for (i = 0; i < 8; ++i) { v = USHR(buf.byts[i >> 1], (4 & -(i & 01))); #define MYFIGLIST "-?BbSsLlTtDdKk??" printf("%c%s", MYFIGLIST[v & 0x0f], spc); } } /* * acm_1show() * Dump the specified node in a low level fashion. * acm_1show_bas() * Do the basic part of it. */ static void acm_1show_bas(char pref, const uint32 pkarr[8], unsigned xb) { register int i; printf("%c %04x", (pref ? pref : 'B'), xb); #if ACM_DBG if (acm_dbg > 2) { for (i = 8; --i >= 0;) { printf("\t"); acm_1_line(pkarr[i], " "); printf("\n"); } } else #endif { for (i = 0; i < 8; ++i) { printf(","); acm_1_line(pkarr[i], ""); } printf("\n"); } } Eximpl void acm_1show(const AcmNode * np, Bool all) { acm_1show_bas(0, np->mn_board, np->mn_xboard); if (all) { printf("h=%8lx/%6lu", (long) np->mn_hash, (long) acm_slotnum(np->mn_hash)); printf(", i=%2x", np->mn_info); printf(", r=%2x", np->mn_refcnt); printf("\n"); } } #if ACM_DBG static void acm_coll_tell( /* tell about a collision */ const char *who, uint32 h, const uint32 ip[8], unsigned xb, const AcmNode * np) { printf("%s COLL: h=%8lx cmp=%lu\n", who, (long) h, (long) sc_cmp); acm_1show_bas('?', ip, xb); acm_1show(np, 1); } #define ACM_COLL_TELL(who, h, ip, xb, np) \ if( ((h) == (np)->mn_hash) && ((xb) == (np)->mn_xboard) ) { \ acm_coll_tell(who, h, ip, xb, np); \ } #endif /* ACM_DBG */ /* * FFS: implicitly we assume: * (white ^ black) & 01 * all figure codes - no_figure are unique in their low 3 bits * (castle00 | castle000) == 0x03 */ #if 0 /* if without packed board in Board (or not * using it) */ register Board *bp; register uint32 v; register AcmHash h; register AcmHash h2; h = 0; h2 = 0; { register Field *p; register int i; /* Scan linewise, collect one uint32 for each: */ for (i = 0; i < 8; ++i) { v = 0; p = &(bp->b_f[MK_POS(7, i)]); /* Fast scan for first non-empty, to reduce shifting: */ while (p->f_c == empty) { --p; } if (p->f_c != border) { do { v <<= 3; v += (p->f_f - no_figure) & 0x07; v <<= 1; v += (p->f_c - empty) & 01; --p; while (p->f_c == empty) { v <<= 4; --p; } } while (p->f_c != border); } # if 1 /* checking against packed board */ if (bp->b_packed.pb_long[i] != v) { panic("pacb[%d]: %08x should be %08x", i, bp->b_packed.pb_long[i], v); } # endif mynode->mn_board[i] = v; # if 0 /* simple */ h ^= v; h += 0x55555555; # else /* better */ h2 <<= 3; /* h2 ^= (h & 07); */ /* h2 ^= (h & 0x77); */ /* h2 ^= (h & 0xfff); */ h2 ^= h; /**/ /* h2 += 0x32323232; */ h >>= 3; h ^= v; /* h += 0x55555555; */ /* h += 0x5a6b3c15; */ h += 0x5a5a5a5a; /**/ # endif } } #endif /* 0 */ /* * Packing and Hashing */ #define PK_WITHtom 1 /* CF: whether to include tomove */ #define PK_EPdirect 1 /* CF: whether directly use bp->b_ep */ #if WITH_ZHASH # define ACM_USE_ZHASH 1 /* (tunable) whether we use b_zhash */ #else # define ACM_USE_ZHASH 0 /* as there is no b_zhash, we cannot use it */ #endif #define ACM__HUPD0(h,v) ((h) ^= (v), (h) += 0x5a5a5a5a) #define ACM__HUPD_(h,v,h2) \ ((h2) <<= 3, (h2) ^= (h), (h) >>= 3, ACM__HUPD0(h,v)) #if PK_WITHtom # define ACM__XBtom(xb,tom) ((xb) <<= 1, (xb) += (tom)) #else # define ACM__XBtom(xb,tom) 0/*empty*/ /* lint: null effect */ #endif #if PK_EPdirect # define ACM__XBep(xb,ep) ((xb) <<= 4, (xb) += (ep)) #else # define ACM__XBep(xb,ep) ((xb) <<= 4, (xb) += (no_pos(ep)?0x0f:COL(ep))) #endif #define ACM__XBcastle(xb,castle) \ ((xb) <<= 4, (xb) |= ((castle)[black] << 2) | (castle)[white]) #define ACM__XB(xb,tom,ep,castle) \ ( (xb) = 0, \ ACM__XBtom(xb,tom), \ ACM__XBep(xb,ep), \ ACM__XBcastle(xb,castle) \ ) /* we must avoid a zero hash value (is unused slot) */ #if ACM_USE_ZHASH # define ACM__HASH(h,xb,ip,tom,ep,castle,h2,zh) \ ( (h) = (zh), \ ACM__XB(xb,tom,ep,castle), \ (xb) = (uint16)(xb), \ (h) ^= (xb), \ (h) = ((h) ? (h) : 1) \ ) # define ACM_MK_HASH(h,xb,ip,tom,ep,castle,zh) \ { \ ACM__HASH(h,xb,ip,tom,ep,castle,h2,zh); \ } #else /* ! ACM_USE_ZHASH */ # define ACM__HASH(h,xb,ip,tom,ep,castle,h2,zh) \ ( (h) = 0, (h2) = 0, \ ACM__HUPD0(h,(ip)[0]), \ ACM__HUPD_(h,(ip)[1],h2), \ ACM__HUPD_(h,(ip)[2],h2), \ ACM__HUPD_(h,(ip)[3],h2), \ ACM__HUPD_(h,(ip)[4],h2), \ ACM__HUPD_(h,(ip)[5],h2), \ ACM__HUPD_(h,(ip)[6],h2), \ ACM__HUPD_(h,(ip)[7],h2), \ (h) ^= (h2), \ ACM__XB(xb,tom,ep,castle), \ (xb) = (uint16)(xb), \ (h) ^= (xb), \ (h) = ((h) ? (h) : 1) \ ) # define ACM_MK_HASH(h,xb,ip,tom,ep,castle,zh) \ { \ register AcmHash h2; \ ACM__HASH(h,xb,ip,tom,ep,castle,h2,zh); \ } #endif /* ! ACM_USE_ZHASH */ #define ACM__MATCH(ip,h,xb,np) \ ( ((h ) == (np)->mn_hash ) \ && ((xb) == (np)->mn_xboard) \ && ( scinc(sc_cmp), \ ( ((np)->mn_board[0] == ip[0]) \ && ((np)->mn_board[1] == ip[1]) \ && ((np)->mn_board[2] == ip[2]) \ && ((np)->mn_board[3] == ip[3]) \ && ((np)->mn_board[4] == ip[4]) \ && ((np)->mn_board[5] == ip[5]) \ && ((np)->mn_board[6] == ip[6]) \ && ((np)->mn_board[7] == ip[7]) \ ) \ ) \ ) /* * acm_search() * The specified board showed up for analysis. * Search the packed version via its hashcode (coputed here), * search it, and return the found or created node, * with the reference count incremented (locked). */ Eximpl AcmNode * acm_search(const Board * bp) { register AcmHash h; register const uint32 *ip; register unsigned xb; scinc(sc_search[0]); ip = &(bp->b_packed.pb_long[0]); ACM_MK_HASH(h, xb, ip, bp->b_tomove, bp->b_ep, bp->b_castle, bp->b_zhash); { register AcmNode *np; register AcmNode *nq; register AcmInx slot; register int xtest; np = &(allslots[slot = acm_slotnum(h)]); if (!np->mn_hash) { /* unused slot */ goto enter; /* so use it now */ } if (ACM__MATCH(ip, h, xb, np)) { /* equal, found */ ++(np->mn_refcnt); IFDBG(1, printf("acm_search FOUND:\n"); acm_1show(np, 1); ) scinc(sc_found[0]); return np; /* the found one */ } IFDBG(0, ACM_COLL_TELL("acm_search", h, ip, xb, np)) nq = 0; if (!np->mn_refcnt) { nq = np; /* remember first unlocked */ } for (xtest = 0; xtest < ACM_XTEST; ++xtest) { slot += (xtest ? xtest : acm_slotoff(h)); if (slot >= ACM_EFF_SLOTS) { if ((slot -= ACM_EFF_SLOTS) >= ACM_EFF_SLOTS) { slot %= ACM_EFF_SLOTS; } } np = &(allslots[slot]); if (!np->mn_hash) { /* not in use */ goto enter; /* so use it now */ } if (ACM__MATCH(ip, h, xb, np)) { /* equal, found */ ++(np->mn_refcnt); IFDBG(1, printf("acm_search FOUND %d:\n", xtest + 1); acm_1show(np, 1); ) scinc(sc_found[0]); return np; /* the found one */ } IFDBG(0, ACM_COLL_TELL("acm_search", h, ip, xb, np)) if (!nq && !np->mn_refcnt) { nq = np; /* remember first unlocked */ } } /* for xtest */ /* Not found, so far. Now we try to delete one of them, and reuse * its slot. It must be unlocked, for that. We choose between the * last (np) and the first unlocked (nq). */ if (!nq) { /* have seen only locked nodes */ IFDBG(1, printf("acm_search FAIL:\n"); acm_1show(np, 1); ) return (AcmNode *) 0; /* sorry */ } /* we have a first unlocked one */ if (np->mn_refcnt) { /* last is locked */ np = nq; /* so use first */ } else { /* both are not locked */ if (nq->mn_info <= np->mn_info) { np = nq; /* use first */ } } /* forget the old (unlocked) node */ IFDBG(1, printf("acm_search UNLINK:\n"); acm_1show(np, 1); ) scinc(sc_unlink); scinc(sc_iforg[np->mn_info]); enter: ; /* We have either found an empty node at 'np', or made it free. * Hence, fill the node with our data ... */ np->mn_hash = h; np->mn_board[0] = ip[0]; np->mn_board[1] = ip[1]; np->mn_board[2] = ip[2]; np->mn_board[3] = ip[3]; np->mn_board[4] = ip[4]; np->mn_board[5] = ip[5]; np->mn_board[6] = ip[6]; np->mn_board[7] = ip[7]; np->mn_xboard = xb; np->mn_info = 0; np->mn_refcnt = 1; scinc(sc_entered); IFDBG(1, printf("acm_search CREATED:\n"); acm_1show(np, 1); ) return np; } } /* * acm_snoop() * The specified board showed up for defender analysis. * The question is, whether we know already the board that * would show up after execution of the indicated move. * If so, return the (old) node, else return NIL. * NIL may be returned just for lazyness. * In no case a new acm entry is invented. */ Eximpl AcmNode * acm_snoop(const Board * bp, const Move * mp) { #if 0 /* disabled */ return (AcmNode *) 0; #else /* enabled */ Position epinfo; Castle castle[2]; uint32 pkboard[8]; register AcmHash h; register uint32 *ip; register unsigned xb; scinc(sc_search[1]); ip = pkboard; h = move_snoop(bp, mp, ip, &epinfo, castle); ACM_MK_HASH(h, xb, ip, opp_colour(bp->b_tomove), epinfo, castle, h); { register AcmNode *np; register AcmInx slot; register int xtest; np = &(allslots[slot = acm_slotnum(h)]); if (!np->mn_hash) { /* not in use */ goto fail; /* so we fail */ } if (ACM__MATCH(ip, h, xb, np)) { /* equal, found */ ++(np->mn_refcnt); IFDBG(1, printf("acm_snoop FOUND:\n"); acm_1show(np, 1); ) scinc(sc_found[1]); return np; /* the found one */ } IFDBG(0, ACM_COLL_TELL("acm_snoop", h, ip, xb, np)) for (xtest = 0; xtest < ACM_XTEST; ++xtest) { slot += (xtest ? xtest : acm_slotoff(h)); if (slot >= ACM_EFF_SLOTS) { if ((slot -= ACM_EFF_SLOTS) >= ACM_EFF_SLOTS) { slot %= ACM_EFF_SLOTS; } } np = &(allslots[slot]); if (!np->mn_hash) { /* not in use */ goto fail; /* so we fail */ } if (ACM__MATCH(ip, h, xb, np)) { /* equal, found */ ++(np->mn_refcnt); IFDBG(1, printf("acm_snoop FOUND %d:\n", xtest + 1); acm_1show(np, 1); ) scinc(sc_found[1]); return np; /* the found one */ } IFDBG(0, ACM_COLL_TELL("acm_snoop", h, ip, xb, np)) } /* for xtest */ } fail:; IFDBG(1, printf("acm_snoop NOT found.\n"); ) return (AcmNode *) 0; #endif /* enabled */ } /* * acm_release() * Note that the user of this module stops using (one incarnation of) * the specified pointer to a node. */ Eximpl void acm_release(AcmNode * np) { if (np != (AcmNode *) 0) { np->mn_refcnt -= 1; IFDBG(1, printf("acm_release:\n"); acm_1show(np, 1); ) } } static void acm_ppp(register AcmNode * np) { if (np && ACM_IRES(np->mn_info) && (f_pppsol > 0) && (np->mn_info >= ppp_info)) { if (np->mn_info > ppp_info) { ppp_info = np->mn_info; ppp_icnt = 0; } if (++ppp_icnt <= f_pppsol) { printf("PPP %3d+ [%2u] for\n", ACM_IDEP(np->mn_info), ppp_icnt); acm_1show(np, FALSE); /* FFS: put_pk_fen_eng */ if (ACM_IDEP(np->mn_info) >= 6) { fflush(stdout); } } if (ppp_icnt >= f_pppsol) { ppp_info = ACM_INFO(1 + ACM_IDEP(ppp_info), TRUE); ppp_icnt = 0; } } } /* * acm_note() * The specified info has been computed with the specified costs. */ Eximpl void acm_note(register AcmNode * np, uint8 info, AnaCost cost) { if (np != (AcmNode *) 0) { /* We could check here, whether the new info is allowed to appear * after the old one. Anyhow, it should be different. */ IFDBG(1, printf("acm_note: [%u] (%u,%.0f)\n", np->mn_info, info, (double) cost); acm_1show(np, 1); ) if (info > np->mn_info) { sum_icost[info] += cost; cnt_icost[info] += 1; /* FFS: overflow: halve both? */ if (np->mn_info) { /* upgr[0] == entered */ scinc(sc_iupgr[np->mn_info]); } scinc(sc_imade[info]); np->mn_info = info; #if 1 if (ACM_IRES(info) && (f_pppsol > 0) && (info >= ppp_info)) { acm_ppp(np); } #endif } } } /* * acm_used() * From the specified node the specified info has been used. * This may be less than could have been used. */ Eximpl void acm_used(const AcmNode * np /* ARGSUSED */ , uint8 info) { register Counter c; scinc(sc_iused[info]); if ((c = cnt_icost[info])) { apx_saved += sum_icost[info] / c; } else { apx_saved += 1; } } /* * acm_init() * Initialize this module. */ Eximpl void acm_init(void) { register int i; #if ACM_DBG if (f_xdebug > acm_dbg) acm_dbg = f_xdebug; #endif for (i = 0; i < 256; ++i) { /* all info values */ sum_icost[i] = 0; cnt_icost[i] = 0; } #if ACM_STATS sc_entered = 0; sc_unlink = 0; sc_search[0] = 0; sc_search[1] = 0; sc_found[0] = 0; sc_found[1] = 0; sc_cmp = 0; for (i = 0; i < 256; ++i) { /* all info values */ sc_imade[i] = 0; sc_iused[i] = 0; sc_iupgr[i] = 0; sc_iforg[i] = 0; } #endif ppp_info = ACM_INFO(2, TRUE); /* min needed */ ppp_icnt = 0; /* already printed */ } static Bool like_prime(register AcmInx nodes) { register AcmInx p; for (p = 3; p < 1000; p += 2) { if ((nodes % p) == 0) return FALSE; } return TRUE; } static AcmInx dec_to_prime(register AcmInx nodes) { if (nodes > 2) { for (nodes -= !(nodes % 2); !like_prime(nodes); nodes -= 2); } return nodes; } Eximpl Bool acm_start(int tomove, int jobtype) { Bool needclear = FALSE; #if ACM_DYN if (!acm__ptr) { /* needs to allocate some memory */ AcmInx megs; AcmInx n; size_t siz; AcmNode *p; n = 0; if (f_megs_want == -1) {/* default requested */ # if defined(ACM_MEGS) megs = ACM_MEGS; # else n = ACM_SLOTS; # endif } else { megs = f_megs_want; } if (!n) { /* map megs --> n (#nodes) */ IFDBG(0, printf("ACM: %lu MB requested\n", (long) megs); ) while ((((siz = megs), siz <<= 20) >> 20) != megs) { megs /= 2; } n = siz / sizeof(AcmNode); } IFDBG(0, printf("ACM: %lu nodes requested\n", (long) n); ) while (((siz = n * sizeof(AcmNode)) / sizeof(AcmNode)) != n) { n /= 2; } n = dec_to_prime(n); if (n >= ACM_MIN_SLOTS) { /* otherwise meaningless */ do { /* try allocation */ IFDBG(0, printf("ACM: try allo %lu nodes\n", (long) n); ) siz = n * sizeof(AcmNode); # if ACM_CALLOC p = (AcmNode *) calloc((size_t) n, sizeof(AcmNode)); # else p = (AcmNode *) malloc(siz); # endif if (!p) n = dec_to_prime(n / 2); } while (!p && (n >= ACM_MIN_SLOTS)); if (p) { /* allocation success */ acm__ptr = p; acm__slots = n; IFDBG(0, printf("ACM: did allo %lu nodes (%.1fMB)\n", (long) n, (double) siz / (1024. * 1024.)); ) } } if (!acm__ptr) { /* allocation did not succeed */ acm__slots = 0; /* to be consistent */ return FALSE; /* sorry, cannot help it */ } # if ! ACM_CALLOC needclear = TRUE; /* since newly allocated */ # endif } #endif /* ACM_DYN */ #if ! PK_WITHtom needclear |= ((g_acm_tomove != tomove) && (g_acm_tomove != -1)); #endif needclear |= ((g_acm_jobtype != jobtype) && (g_acm_jobtype != -1)); if (needclear) { IFDBG(0, printf("ACM: clearing...\n"); fflush(stdout); ) #if 0 /* FFS */ bzero(allslots, ACM_EFF_SLOTS * sizeof(AcmNode)); #else { register AcmInx slot; register AcmNode *arr; arr = allslots; for (slot = 0; slot < ACM_EFF_SLOTS; ++slot) { arr[slot].mn_hash = 0; /* now unused */ } } #endif IFDBG(0, printf("ACM: clearing ready...\n"); fflush(stdout); ) } g_acm_tomove = tomove; g_acm_jobtype = jobtype; return TRUE; /* ok */ }