ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/ambient.c
(Generate patch)

Comparing ray/src/rt/ambient.c (file contents):
Revision 1.13 by greg, Thu Jun 6 10:48:50 1991 UTC vs.
Revision 2.110 by greg, Fri Feb 19 22:05:46 2021 UTC

# Line 1 | Line 1
1 < /* Copyright (c) 1986 Regents of the University of California */
2 <
3 < #ifndef lint
4 < static char SCCSid[] = "$SunId$ LBL";
5 < #endif
6 <
1 > static const char       RCSid[] = "$Id$";
2   /*
3   *  ambient.c - routines dealing with ambient (inter-reflected) component.
4   *
5 < *  The macro AMBFLUSH (if defined) is the number of ambient values
11 < *      to wait before flushing to the ambient file.
12 < *
13 < *     5/9/86
5 > *  Declarations of external symbols in ambient.h
6   */
7  
8 < #include  "ray.h"
8 > #include "copyright.h"
9  
10 < #include  "octree.h"
10 > #include <string.h>
11  
12 + #include  "platform.h"
13 + #include  "ray.h"
14   #include  "otypes.h"
15 <
15 > #include  "otspecial.h"
16 > #include  "resolu.h"
17 > #include  "ambient.h"
18   #include  "random.h"
19 + #include  "pmapamb.h"
20  
21 < #define  OCTSCALE       0.5     /* ceil((valid rad.)/(cube size)) */
21 > #ifndef  OCTSCALE
22 > #define  OCTSCALE       1.0     /* ceil((valid rad.)/(cube size)) */
23 > #endif
24  
25 < extern CUBE  thescene;          /* contains space boundaries */
25 > extern char  *shm_boundary;     /* memory sharing boundary */
26  
27 < extern COLOR  ambval;           /* global ambient component */
28 < extern double  ambacc;          /* ambient accuracy */
29 < extern int  ambres;             /* ambient resolution */
30 < extern int  ambdiv;             /* number of divisions for calculation */
32 < extern int  ambssamp;           /* number of super-samples */
33 < extern int  ambounce;           /* number of ambient bounces */
34 < extern char  *amblist[];        /* ambient include/exclude list */
35 < extern int  ambincl;            /* include == 1, exclude == 0 */
27 > #ifndef  MAXASET
28 > #define  MAXASET        4095    /* maximum number of elements in ambient set */
29 > #endif
30 > OBJECT  ambset[MAXASET+1]={0};  /* ambient include/exclude set */
31  
32 < #define  MAXASET        511     /* maximum number of elements in ambient set */
33 < OBJECT  ambset[MAXASET+1]={0};  /* ambient include/exclude set */
32 > double  maxarad;                /* maximum ambient radius */
33 > double  minarad;                /* minimum ambient radius */
34  
35 < double  maxarad;                /* maximum ambient radius */
41 < double  minarad;                /* minimum ambient radius */
35 > static AMBTREE  atrunk;         /* our ambient trunk node */
36  
37 < /*
38 < * Since we've defined our vectors as float below to save space,
45 < * watch out for changes in the definitions of VCOPY() and DOT().
46 < */
47 < typedef struct ambval {
48 <        float  pos[3];          /* position in space */
49 <        float  dir[3];          /* normal direction */
50 <        int  lvl;               /* recursion level of parent ray */
51 <        float  weight;          /* weight of parent ray */
52 <        COLOR  val;             /* computed ambient value */
53 <        float  rad;             /* validity radius */
54 <        struct ambval  *next;   /* next in list */
55 < }  AMBVAL;                      /* ambient value */
37 > static FILE  *ambfp = NULL;     /* ambient file pointer */
38 > static int  nunflshed = 0;      /* number of unflushed ambient values */
39  
40 < typedef struct ambtree {
41 <        AMBVAL  *alist;         /* ambient value list */
42 <        struct ambtree  *kid;   /* 8 child nodes */
43 < }  AMBTREE;                     /* ambient octree */
40 > #ifndef SORT_THRESH
41 > #ifdef SMLMEM
42 > #define SORT_THRESH     ((16L<<20)/sizeof(AMBVAL))
43 > #else
44 > #define SORT_THRESH     ((64L<<20)/sizeof(AMBVAL))
45 > #endif
46 > #endif
47 > #ifndef SORT_INTVL
48 > #define SORT_INTVL      (SORT_THRESH<<1)
49 > #endif
50 > #ifndef MAX_SORT_INTVL
51 > #define MAX_SORT_INTVL  (SORT_INTVL<<6)
52 > #endif
53  
62 typedef struct {
63        float  k;               /* error contribution per sample */
64        COLOR  v;               /* ray sum */
65        int  n;                 /* number of samples */
66        short  t, p;            /* theta, phi indices */
67 }  AMBSAMP;                     /* ambient sample */
54  
55 < static AMBTREE  atrunk;         /* our ambient trunk node */
55 > static double  avsum = 0.;              /* computed ambient value sum (log) */
56 > static unsigned int  navsum = 0;        /* number of values in avsum */
57 > static unsigned int  nambvals = 0;      /* total number of indirect values */
58 > static unsigned int  nambshare = 0;     /* number of values from file */
59 > static unsigned long  ambclock = 0;     /* ambient access clock */
60 > static unsigned long  lastsort = 0;     /* time of last value sort */
61 > static long  sortintvl = SORT_INTVL;    /* time until next sort */
62 > static FILE  *ambinp = NULL;            /* auxiliary file for input */
63 > static long  lastpos = -1;              /* last flush position */
64  
65 < static FILE  *ambfp = NULL;     /* ambient file pointer */
65 > #define MAXACLOCK       (1L<<30)        /* clock turnover value */
66 >        /*
67 >         * Track access times unless we are sharing ambient values
68 >         * through memory on a multiprocessor, when we want to avoid
69 >         * claiming our own memory (copy on write).  Go ahead anyway
70 >         * if more than two thirds of our values are unshared.
71 >         * Compile with -Dtracktime=0 to turn this code off.
72 >         */
73 > #ifndef tracktime
74 > #define tracktime       (shm_boundary == NULL || nambvals > 3*nambshare)
75 > #endif
76  
77 < #define  newambval()    (AMBVAL *)bmalloc(sizeof(AMBVAL))
77 > #define  AMBFLUSH       (BUFSIZ/AMBVALSIZ)
78  
79 < #define  newambtree()   (AMBTREE *)calloc(8, sizeof(AMBTREE))
79 > #define  newambval()    (AMBVAL *)malloc(sizeof(AMBVAL))
80  
81 < double  sumambient(), doambient(), makeambient();
81 > #define  tfunc(lwr, x, upr)     (((x)-(lwr))/((upr)-(lwr)))
82  
83 + static void initambfile(int creat);
84 + static void avsave(AMBVAL *av);
85 + static AMBVAL *avstore(AMBVAL  *aval);
86 + static AMBTREE *newambtree(void);
87 + static void freeambtree(AMBTREE  *atp);
88  
89 < setambient(afile)                       /* initialize calculation */
90 < char  *afile;
89 > typedef void unloadtf_t(AMBVAL *);
90 > static unloadtf_t avinsert;
91 > static unloadtf_t av2list;
92 > static unloadtf_t avfree;
93 > static void unloadatree(AMBTREE  *at, unloadtf_t *f);
94 >
95 > static int aposcmp(const void *avp1, const void *avp2);
96 > static int avlmemi(AMBVAL *avaddr);
97 > static void sortambvals(int always);
98 >
99 > static int      plugaleak(RAY *r, AMBVAL *ap, FVECT anorm, double ang);
100 > static double   sumambient(COLOR acol, RAY *r, FVECT rn, int al,
101 >                                AMBTREE *at, FVECT c0, double s);
102 > static int      makeambient(COLOR acol, RAY *r, FVECT rn, int al);
103 > static int      extambient(COLOR cr, AMBVAL *ap, FVECT pv, FVECT nv,
104 >                                FVECT uvw[3]);
105 >
106 > #ifdef  F_SETLKW
107 > static void aflock(int  typ);
108 > #endif
109 >
110 >
111 > void
112 > setambres(                              /* set ambient resolution */
113 >        int  ar
114 > )
115   {
116 <        long  ftell();
117 <        AMBVAL  amb;
116 >        ambres = ar < 0 ? 0 : ar;               /* may be done already */
117 >                                                /* set min & max radii */
118 >        if (ar <= 0) {
119 >                minarad = 0;
120 >                maxarad = thescene.cusize*0.2;
121 >        } else {
122 >                minarad = thescene.cusize / ar;
123 >                maxarad = 64.0 * minarad;               /* heuristic */
124 >                if (maxarad > thescene.cusize*0.2)
125 >                        maxarad = thescene.cusize*0.2;
126 >        }
127 >        if (minarad <= FTINY)
128 >                minarad = 10.0*FTINY;
129 >        if (maxarad <= minarad)
130 >                maxarad = 64.0 * minarad;
131 > }
132  
86        maxarad = thescene.cusize / 2.0;                /* maximum radius */
87                                                        /* minimum radius */
88        minarad = ambres > 0 ? thescene.cusize/ambres : 0.0;
133  
134 <                                        /* open ambient file */
135 <        if (afile != NULL)
136 <                if ((ambfp = fopen(afile, "r+")) != NULL) {
137 <                        while (fread((char *)&amb,sizeof(AMBVAL),1,ambfp) == 1)
138 <                                avinsert(&amb, &atrunk, thescene.cuorg,
139 <                                                thescene.cusize);
140 <                                                        /* align */
141 <                        fseek(ambfp, -(ftell(ambfp)%sizeof(AMBVAL)), 1);
142 <                } else if ((ambfp = fopen(afile, "w")) == NULL) {
143 <                        sprintf(errmsg, "cannot open ambient file \"%s\"",
144 <                                        afile);
145 <                        error(SYSTEM, errmsg);
134 > void
135 > setambacc(                              /* set ambient accuracy */
136 >        double  newa
137 > )
138 > {
139 >        static double   olda;           /* remember previous setting here */
140 >        
141 >        newa *= (newa > 0);
142 >        if (fabs(newa - olda) >= .05*(newa + olda)) {
143 >                ambacc = newa;
144 >                if (ambacc > FTINY && nambvals > 0)
145 >                        sortambvals(1);         /* rebuild tree */
146 >        }
147 > }
148 >
149 >
150 > void
151 > setambient(void)                                /* initialize calculation */
152 > {
153 >        int     readonly = 0;
154 >        long    flen;
155 >        AMBVAL  amb;
156 >                                                /* make sure we're fresh */
157 >        ambdone();
158 >                                                /* init ambient limits */
159 >        setambres(ambres);
160 >        setambacc(ambacc);
161 >        if (ambfile == NULL || !ambfile[0])
162 >                return;
163 >        if (ambacc <= FTINY) {
164 >                sprintf(errmsg, "zero ambient accuracy so \"%s\" not opened",
165 >                                ambfile);
166 >                error(WARNING, errmsg);
167 >                return;
168 >        }
169 >                                                /* open ambient file */
170 >        if ((ambfp = fopen(ambfile, "r+")) == NULL)
171 >                readonly = (ambfp = fopen(ambfile, "r")) != NULL;
172 >        if (ambfp != NULL) {
173 >                initambfile(0);                 /* file exists */
174 >                lastpos = ftell(ambfp);
175 >                while (readambval(&amb, ambfp))
176 >                        avstore(&amb);
177 >                nambshare = nambvals;           /* share loaded values */
178 >                if (readonly) {
179 >                        sprintf(errmsg,
180 >                                "loaded %u values from read-only ambient file",
181 >                                        nambvals);
182 >                        error(WARNING, errmsg);
183 >                        fclose(ambfp);          /* close file so no writes */
184 >                        ambfp = NULL;
185 >                        return;                 /* avoid ambsync() */
186                  }
187 +                                                /* align file pointer */
188 +                lastpos += (long)nambvals*AMBVALSIZ;
189 +                flen = lseek(fileno(ambfp), (off_t)0, SEEK_END);
190 +                if (flen != lastpos) {
191 +                        sprintf(errmsg,
192 +                        "ignoring last %ld values in ambient file (corrupted)",
193 +                                        (flen - lastpos)/AMBVALSIZ);
194 +                        error(WARNING, errmsg);
195 +                        fseek(ambfp, lastpos, SEEK_SET);
196 +                        ftruncate(fileno(ambfp), (off_t)lastpos);
197 +                }
198 +        } else if ((ambfp = fopen(ambfile, "w+")) != NULL) {
199 +                initambfile(1);                 /* else create new file */
200 +                fflush(ambfp);
201 +                lastpos = ftell(ambfp);
202 +        } else {
203 +                sprintf(errmsg, "cannot open ambient file \"%s\"", ambfile);
204 +                error(SYSTEM, errmsg);
205 +        }
206 + #ifdef  F_SETLKW
207 +        aflock(F_UNLCK);                        /* release file */
208 + #endif
209   }
210  
211  
212 < ambnotify(obj)                  /* record new modifier */
213 < OBJECT  obj;
212 > void
213 > ambdone(void)                   /* close ambient file and free memory */
214   {
215 +        if (ambfp != NULL) {            /* close ambient file */
216 +                ambsync();
217 +                fclose(ambfp);
218 +                ambfp = NULL;
219 +                if (ambinp != NULL) {  
220 +                        fclose(ambinp);
221 +                        ambinp = NULL;
222 +                }
223 +                lastpos = -1;
224 +        }
225 +                                        /* free ambient tree */
226 +        unloadatree(&atrunk, avfree);
227 +                                        /* reset state variables */
228 +        avsum = 0.;
229 +        navsum = 0;
230 +        nambvals = 0;
231 +        nambshare = 0;
232 +        ambclock = 0;
233 +        lastsort = 0;
234 +        sortintvl = SORT_INTVL;
235 + }
236 +
237 +
238 + void
239 + ambnotify(                      /* record new modifier */
240 +        OBJECT  obj
241 + )
242 + {
243          static int  hitlimit = 0;
244 <        register OBJREC  *o = objptr(obj);
245 <        register char  **amblp;
244 >        OBJREC   *o;
245 >        char  **amblp;
246  
247 +        if (obj == OVOID) {             /* starting over */
248 +                ambset[0] = 0;
249 +                hitlimit = 0;
250 +                return;
251 +        }
252 +        o = objptr(obj);
253          if (hitlimit || !ismodifier(o->otype))
254                  return;
255          for (amblp = amblist; *amblp != NULL; amblp++)
# Line 125 | Line 265 | OBJECT  obj;
265   }
266  
267  
268 < ambient(acol, r)                /* compute ambient component for ray */
269 < COLOR  acol;
270 < register RAY  *r;
268 > void
269 > multambient(            /* compute ambient component & multiply by coef. */
270 >        COLOR  aval,
271 >        RAY  *r,
272 >        FVECT  nrm
273 > )
274   {
275          static int  rdepth = 0;                 /* ambient recursion */
276 <        double  wsum;
276 >        COLOR   acol, caustic;
277 >        int     i, ok;
278 >        double  d, l;
279  
280 <        rdepth++;                               /* increment level */
280 >        /* PMAP: Factor in ambient from photon map, if enabled and ray is
281 >         * ambient. Return as all ambient components accounted for, else
282 >         * continue. */
283 >        if (ambPmap(aval, r, rdepth))
284 >                return;
285  
286 +        /* PMAP: Factor in specular-diffuse ambient (caustics) from photon
287 +         * map, if enabled and ray is primary, else caustic is zero.  Continue
288 +         * with RADIANCE ambient calculation */
289 +        copycolor(caustic, aval);
290 +        ambPmapCaustic(caustic, r, rdepth);
291 +        
292          if (ambdiv <= 0)                        /* no ambient calculation */
293                  goto dumbamb;
294                                                  /* check number of bounces */
295 <        if (rdepth > ambounce)
295 >        if (rdepth >= ambounce)
296                  goto dumbamb;
297                                                  /* check ambient list */
298          if (ambincl != -1 && r->ro != NULL &&
# Line 145 | Line 300 | register RAY  *r;
300                  goto dumbamb;
301  
302          if (ambacc <= FTINY) {                  /* no ambient storage */
303 <                if (doambient(acol, r) == 0.0)
303 >                FVECT   uvd[2];
304 >                float   dgrad[2], *dgp = NULL;
305 >
306 >                if (nrm != r->ron && DOT(nrm,r->ron) < 0.9999)
307 >                        dgp = dgrad;            /* compute rotational grad. */
308 >                copycolor(acol, aval);
309 >                rdepth++;
310 >                ok = doambient(acol, r, r->rweight,
311 >                                uvd, NULL, NULL, dgp, NULL);
312 >                rdepth--;
313 >                if (!ok)
314                          goto dumbamb;
315 <                goto done;
315 >                if ((ok > 0) & (dgp != NULL)) { /* apply texture */
316 >                        FVECT   v1;
317 >                        VCROSS(v1, r->ron, nrm);
318 >                        d = 1.0;
319 >                        for (i = 3; i--; )
320 >                                d += v1[i] * (dgp[0]*uvd[0][i] + dgp[1]*uvd[1][i]);
321 >                        if (d >= 0.05)
322 >                                scalecolor(acol, d);
323 >                }
324 >                copycolor(aval, acol);
325 >
326 >                /* PMAP: add in caustic */
327 >                addcolor(aval, caustic);
328 >                return;
329          }
330 <                                                /* get ambient value */
330 >
331 >        if (tracktime)                          /* sort to minimize thrashing */
332 >                sortambvals(0);
333 >                                                /* interpolate ambient value */
334          setcolor(acol, 0.0, 0.0, 0.0);
335 <        wsum = sumambient(acol, r, &atrunk, thescene.cuorg, thescene.cusize);
336 <        if (wsum > FTINY)
337 <                scalecolor(acol, 1.0/wsum);
338 <        else if (makeambient(acol, r) == 0.0)
339 <                goto dumbamb;
340 <        goto done;
335 >        d = sumambient(acol, r, nrm, rdepth,
336 >                        &atrunk, thescene.cuorg, thescene.cusize);
337 >                        
338 >        if (d > FTINY) {
339 >                d = 1.0/d;
340 >                scalecolor(acol, d);
341 >                multcolor(aval, acol);
342  
343 < dumbamb:                                        /* return global value */
344 <        copycolor(acol, ambval);
345 < done:                                           /* must finish here! */
343 >                /* PMAP: add in caustic */
344 >                addcolor(aval, caustic);
345 >                return;
346 >        }
347 >        
348 >        rdepth++;                               /* need to cache new value */
349 >        ok = makeambient(acol, r, nrm, rdepth-1);
350          rdepth--;
351 +        
352 +        if (ok) {
353 +                multcolor(aval, acol);          /* computed new value */
354 +
355 +                /* PMAP: add in caustic */
356 +                addcolor(aval, caustic);
357 +                return;
358 +        }
359 +        
360 + dumbamb:                                        /* return global value */
361 +        if ((ambvwt <= 0) | (navsum == 0)) {
362 +                multcolor(aval, ambval);
363 +                
364 +                /* PMAP: add in caustic */
365 +                addcolor(aval, caustic);
366 +                return;
367 +        }
368 +        
369 +        l = bright(ambval);                     /* average in computations */  
370 +        if (l > FTINY) {
371 +                d = (log(l)*(double)ambvwt + avsum) /
372 +                                (double)(ambvwt + navsum);
373 +                d = exp(d) / l;
374 +                scalecolor(aval, d);
375 +                multcolor(aval, ambval);        /* apply color of ambval */
376 +        } else {
377 +                d = exp( avsum / (double)navsum );
378 +                scalecolor(aval, d);            /* neutral color */
379 +        }
380   }
381  
382  
383 < double
384 < sumambient(acol, r, at, c0, s)          /* get interpolated ambient value */
385 < COLOR  acol;
171 < register RAY  *r;
172 < AMBTREE  *at;
173 < FVECT  c0;
174 < double  s;
383 > /* Plug a potential leak where ambient cache value is occluded */
384 > static int
385 > plugaleak(RAY *r, AMBVAL *ap, FVECT anorm, double ang)
386   {
387 <        extern double  sqrt();
388 <        double  d, e1, e2, wt, wsum;
389 <        COLOR  ct;
390 <        FVECT  ck0;
391 <        int  i;
392 <        register int  j;
393 <        register AMBVAL  *av;
394 <                                        /* do this node */
395 <        wsum = 0.0;
387 >        const double    cost70sq = 0.1169778;   /* cos(70deg)^2 */
388 >        RAY             rtst;
389 >        FVECT           vdif;
390 >        double          normdot, ndotd, nadotd;
391 >        double          a, b, c, t[2];
392 >
393 >        ang += 2.*PI*(ang < 0);                 /* check direction flags */
394 >        if ( !(ap->corral>>(int)(ang*(16./PI)) & 1) )
395 >                return(0);
396 >        /*
397 >         * Generate test ray, targeting 20 degrees above sample point plane
398 >         * along surface normal from cache position.  This should be high
399 >         * enough to miss local geometry we don't really care about.
400 >         */
401 >        VSUB(vdif, ap->pos, r->rop);
402 >        normdot = DOT(anorm, r->ron);
403 >        ndotd = DOT(vdif, r->ron);
404 >        nadotd = DOT(vdif, anorm);
405 >        a = normdot*normdot - cost70sq;
406 >        b = 2.0*(normdot*ndotd - nadotd*cost70sq);
407 >        c = ndotd*ndotd - DOT(vdif,vdif)*cost70sq;
408 >        if (quadratic(t, a, b, c) != 2)
409 >                return(1);                      /* should rarely happen */
410 >        if (t[1] <= FTINY)
411 >                return(0);                      /* should fail behind test */
412 >        rayorigin(&rtst, SHADOW, r, NULL);
413 >        VSUM(rtst.rdir, vdif, anorm, t[1]);     /* further dist. > plane */
414 >        rtst.rmax = normalize(rtst.rdir);       /* short ray test */
415 >        while (localhit(&rtst, &thescene)) {    /* check for occluder */
416 >                OBJREC  *m = findmaterial(rtst.ro);
417 >                if (m != NULL && !istransp(m->otype) && !isBSDFproxy(m) &&
418 >                                (rtst.clipset == NULL ||
419 >                                        !inset(rtst.clipset, rtst.ro->omod)))
420 >                        return(1);              /* plug light leak */
421 >                VCOPY(rtst.rorg, rtst.rop);     /* skip invisible surface */
422 >                rtst.rmax -= rtst.rot;
423 >                rayclear(&rtst);
424 >        }
425 >        return(0);                              /* seems we're OK */
426 > }
427 >
428 >
429 > static double
430 > sumambient(             /* get interpolated ambient value */
431 >        COLOR  acol,
432 >        RAY  *r,
433 >        FVECT  rn,
434 >        int  al,
435 >        AMBTREE  *at,
436 >        FVECT  c0,
437 >        double  s
438 > )
439 > {                       /* initial limit is 10 degrees plus ambacc radians */
440 >        const double    minangle = 10.0 * PI/180.;
441 >        double          maxangle = minangle + ambacc;
442 >        double          wsum = 0.0;
443 >        FVECT           ck0;
444 >        int             i, j;
445 >        AMBVAL          *av;
446 >
447 >        if (at->kid != NULL) {          /* sum children first */                                
448 >                s *= 0.5;
449 >                for (i = 0; i < 8; i++) {
450 >                        for (j = 0; j < 3; j++) {
451 >                                ck0[j] = c0[j];
452 >                                if (1<<j & i)
453 >                                        ck0[j] += s;
454 >                                if (r->rop[j] < ck0[j] - OCTSCALE*s)
455 >                                        break;
456 >                                if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
457 >                                        break;
458 >                        }
459 >                        if (j == 3)
460 >                                wsum += sumambient(acol, r, rn, al,
461 >                                                        at->kid+i, ck0, s);
462 >                }
463 >                                        /* good enough? */
464 >                if (wsum >= 0.05 && s > minarad*10.0)
465 >                        return(wsum);
466 >        }
467 >                                        /* adjust maximum angle */
468 >        if (at->alist != NULL && (at->alist->lvl <= al) & (r->rweight < 0.6))
469 >                maxangle = (maxangle - PI/2.)*pow(r->rweight,0.13) + PI/2.;
470 >                                        /* sum this node */
471          for (av = at->alist; av != NULL; av = av->next) {
472 +                double  u, v, d, delta_r2, delta_t2;
473 +                COLOR   ct;
474 +                FVECT   uvw[3];
475 +                                        /* record access */
476 +                if (tracktime)
477 +                        av->latick = ambclock;
478                  /*
479 <                 *  Ray strength test.
479 >                 *  Ambient level test
480                   */
481 <                if (av->lvl > r->rlvl || av->weight < r->rweight-FTINY)
481 >                if (av->lvl > al ||     /* list sorted, so this works */
482 >                                (av->lvl == al) & (av->weight < 0.9*r->rweight))
483 >                        break;
484 >                /*
485 >                 *  Direction test using unperturbed normal
486 >                 */
487 >                decodedir(uvw[2], av->ndir);
488 >                d = DOT(uvw[2], r->ron);
489 >                if (d <= 0.0)           /* >= 90 degrees */
490                          continue;
491 +                delta_r2 = 2.0 - 2.0*d; /* approx. radians^2 */
492 +                if (delta_r2 >= maxangle*maxangle)
493 +                        continue;
494                  /*
495 <                 *  Ambient radius test.
495 >                 *  Modified ray behind test
496                   */
497 <                e1 = 0.0;
498 <                for (j = 0; j < 3; j++) {
499 <                        d = av->pos[j] - r->rop[j];
197 <                        e1 += d * d;
198 <                }
199 <                e1 /= av->rad * av->rad;
200 <                if (e1 > ambacc*ambacc*1.21)
497 >                VSUB(ck0, r->rop, av->pos);
498 >                d = DOT(ck0, uvw[2]);
499 >                if (d < -minarad*ambacc-.001)
500                          continue;
501 +                d /= av->rad[0];
502 +                delta_t2 = d*d;
503 +                if (delta_t2 >= ambacc*ambacc)
504 +                        continue;
505                  /*
506 <                 *  Normal direction test.
506 >                 *  Elliptical radii test based on Hessian
507                   */
508 <                e2 = (1.0 - DOT(av->dir, r->ron)) * r->rweight;
509 <                if (e2 < 0.0) e2 = 0.0;
510 <                if (e1 + e2 > ambacc*ambacc*1.21)
508 >                decodedir(uvw[0], av->udir);
509 >                VCROSS(uvw[1], uvw[2], uvw[0]);
510 >                d = (u = DOT(ck0, uvw[0])) / av->rad[0];
511 >                delta_t2 += d*d;
512 >                d = (v = DOT(ck0, uvw[1])) / av->rad[1];
513 >                delta_t2 += d*d;
514 >                if (delta_t2 >= ambacc*ambacc)
515                          continue;
516                  /*
517 <                 *  Ray behind test.
517 >                 *  Test for potential light leak
518                   */
519 <                d = 0.0;
213 <                for (j = 0; j < 3; j++)
214 <                        d += (r->rop[j] - av->pos[j]) *
215 <                                        (av->dir[j] + r->ron[j]);
216 <                if (d*0.5 < -minarad*ambacc)
519 >                if (av->corral && plugaleak(r, av, uvw[2], atan2a(v,u)))
520                          continue;
521                  /*
522 <                 *  Jittering final test reduces image artifacts.
522 >                 *  Extrapolate value and compute final weight (hat function)
523                   */
524 <                wt = sqrt(e1) + sqrt(e2);
222 <                wt *= .9 + .2*frandom();
223 <                if (wt > ambacc)
524 >                if (!extambient(ct, av, r->rop, rn, uvw))
525                          continue;
526 <                if (wt <= 1e-3)
527 <                        wt = 1e3;
528 <                else
228 <                        wt = 1.0 / wt;
229 <                wsum += wt;
230 <                copycolor(ct, av->val);
231 <                scalecolor(ct, wt);
526 >                d = tfunc(maxangle, sqrt(delta_r2), 0.0) *
527 >                        tfunc(ambacc, sqrt(delta_t2), 0.0);
528 >                scalecolor(ct, d);
529                  addcolor(acol, ct);
530 +                wsum += d;
531          }
234        if (at->kid == NULL)
235                return(wsum);
236                                        /* do children */
237        s *= 0.5;
238        for (i = 0; i < 8; i++) {
239                for (j = 0; j < 3; j++) {
240                        ck0[j] = c0[j];
241                        if (1<<j & i)
242                                ck0[j] += s;
243                        if (r->rop[j] < ck0[j] - OCTSCALE*s)
244                                break;
245                        if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
246                                break;
247                }
248                if (j == 3)
249                        wsum += sumambient(acol, r, at->kid+i, ck0, s);
250        }
532          return(wsum);
533   }
534  
535  
536 < double
537 < makeambient(acol, r)            /* make a new ambient value */
538 < COLOR  acol;
539 < register RAY  *r;
536 > static int
537 > makeambient(            /* make a new ambient value for storage */
538 >        COLOR  acol,
539 >        RAY  *r,
540 >        FVECT  rn,
541 >        int  al
542 > )
543   {
544 <        AMBVAL  amb;
544 >        AMBVAL  amb;
545 >        FVECT   uvw[3];
546 >        int     i;
547  
548 <        amb.rad = doambient(acol, r);           /* compute ambient */
549 <        if (amb.rad == 0.0)
550 <                return(0.0);
551 <                                                /* store it */
548 >        amb.weight = 1.0;                       /* compute weight */
549 >        for (i = al; i-- > 0; )
550 >                amb.weight *= AVGREFL;
551 >        if (r->rweight < 0.1*amb.weight)        /* heuristic override */
552 >                amb.weight = 1.25*r->rweight;
553 >        setcolor(acol, AVGREFL, AVGREFL, AVGREFL);
554 >                                                /* compute ambient */
555 >        i = doambient(acol, r, amb.weight,
556 >                        uvw, amb.rad, amb.gpos, amb.gdir, &amb.corral);
557 >        scalecolor(acol, 1./AVGREFL);           /* undo assumed reflectance */
558 >        if (i <= 0 || amb.rad[0] <= FTINY)      /* no Hessian or zero radius */
559 >                return(i);
560 >                                                /* store value */
561          VCOPY(amb.pos, r->rop);
562 <        VCOPY(amb.dir, r->ron);
563 <        amb.lvl = r->rlvl;
564 <        amb.weight = r->rweight;
562 >        amb.ndir = encodedir(r->ron);
563 >        amb.udir = encodedir(uvw[0]);
564 >        amb.lvl = al;
565          copycolor(amb.val, acol);
566                                                  /* insert into tree */
567 <        avinsert(&amb, &atrunk, thescene.cuorg, thescene.cusize);
568 <        avsave(&amb);                           /* write to file */
569 <        return(amb.rad);
567 >        avsave(&amb);                           /* and save to file */
568 >        if (rn != r->ron) {                     /* texture */
569 >                VCOPY(uvw[2], r->ron);
570 >                extambient(acol, &amb, r->rop, rn, uvw);
571 >        }
572 >        return(1);
573   }
574  
575  
576 < double
577 < doambient(acol, r)                      /* compute ambient component */
578 < COLOR  acol;
579 < register RAY  *r;
576 > static int
577 > extambient(             /* extrapolate value at pv, nv */
578 >        COLOR  cr,
579 >        AMBVAL   *ap,
580 >        FVECT  pv,
581 >        FVECT  nv,
582 >        FVECT  uvw[3]
583 > )
584   {
585 <        extern int  ambcmp();
586 <        extern double  sin(), cos(), sqrt();
587 <        int  hlist[4];
588 <        double  phi, xd, yd, zd;
589 <        double  b, b2;
590 <        register AMBSAMP  *div;
289 <        AMBSAMP  dnew;
290 <        RAY  ar;
291 <        FVECT  ux, uy;
292 <        double  arad;
293 <        int  ndivs, nt, np, ns, ne, i, j;
294 <        register int  k;
585 >        const double    min_d = 0.05;
586 >        const double    max_d = 20.;
587 >        static FVECT    my_uvw[3];
588 >        FVECT           v1;
589 >        int             i;
590 >        double          d = 1.0;        /* zeroeth order */
591  
592 <        setcolor(acol, 0.0, 0.0, 0.0);
593 <                                        /* set number of divisions */
594 <        nt = sqrt(ambdiv * r->rweight * 0.5) + 0.5;
595 <        np = 2 * nt;
596 <        ndivs = nt * np;
301 <                                        /* check first */
302 <        if (ndivs == 0 || rayorigin(&ar, r, AMBIENT, 0.5) < 0)
303 <                return(0.0);
304 <                                        /* set number of super-samples */
305 <        ns = ambssamp * r->rweight + 0.5;
306 <        if (ns > 0) {
307 <                div = (AMBSAMP *)malloc(ndivs*sizeof(AMBSAMP));
308 <                if (div == NULL)
309 <                        error(SYSTEM, "out of memory in doambient");
310 <        } else
311 <                div = NULL;
312 <                                        /* make axes */
313 <        uy[0] = uy[1] = uy[2] = 0.0;
314 <        for (k = 0; k < 3; k++)
315 <                if (r->ron[k] < 0.6 && r->ron[k] > -0.6)
316 <                        break;
317 <        uy[k] = 1.0;
318 <        fcross(ux, r->ron, uy);
319 <        normalize(ux);
320 <        fcross(uy, ux, r->ron);
321 <                                        /* set up urand */
322 <        hlist[0] = r->rno;
323 <                                                /* sample divisions */
324 <        arad = 0.0;
325 <        ne = 0;
326 <        for (i = 0; i < nt; i++) {
327 <                hlist[1] = i;
328 <                for (j = 0; j < np; j++) {
329 <                        rayorigin(&ar, r, AMBIENT, 0.5);        /* pretested */
330 <                        hlist[2] = j;
331 <                        hlist[3] = 0;
332 <                        zd = sqrt((i+urand(ilhash(hlist,4)))/nt);
333 <                        hlist[3] = 1;
334 <                        phi = 2.0*PI * (j+urand(ilhash(hlist,4)))/np;
335 <                        xd = cos(phi) * zd;
336 <                        yd = sin(phi) * zd;
337 <                        zd = sqrt(1.0 - zd*zd);
338 <                        for (k = 0; k < 3; k++)
339 <                                ar.rdir[k] = xd*ux[k]+yd*uy[k]+zd*r->ron[k];
340 <                        dimlist[ndims++] = i*np + j + 38813;
341 <                        rayvalue(&ar);
342 <                        ndims--;
343 <                        if (ar.rot < FHUGE)
344 <                                arad += 1.0 / ar.rot;
345 <                        if (div != NULL) {              /* save division */
346 <                                div[ne].k = 0.0;
347 <                                copycolor(div[ne].v, ar.rcol);
348 <                                div[ne].n = 0;
349 <                                div[ne].t = i; div[ne].p = j;
350 <                                                        /* sum errors */
351 <                                b = bright(ar.rcol);
352 <                                if (i > 0) {            /* from above */
353 <                                        b2 = bright(div[ne-np].v) - b;
354 <                                        b2 *= b2 * 0.25;
355 <                                        div[ne].k += b2;
356 <                                        div[ne].n++;
357 <                                        div[ne-np].k += b2;
358 <                                        div[ne-np].n++;
359 <                                }
360 <                                if (j > 0) {            /* from behind */
361 <                                        b2 = bright(div[ne-1].v) - b;
362 <                                        b2 *= b2 * 0.25;
363 <                                        div[ne].k += b2;
364 <                                        div[ne].n++;
365 <                                        div[ne-1].k += b2;
366 <                                        div[ne-1].n++;
367 <                                }
368 <                                if (j == np-1) {        /* around */
369 <                                        b2 = bright(div[ne-(np-1)].v) - b;
370 <                                        b2 *= b2 * 0.25;
371 <                                        div[ne].k += b2;
372 <                                        div[ne].n++;
373 <                                        div[ne-(np-1)].k += b2;
374 <                                        div[ne-(np-1)].n++;
375 <                                }
376 <                                ne++;
377 <                        } else
378 <                                addcolor(acol, ar.rcol);
379 <                }
592 >        if (uvw == NULL) {              /* need local coordinates? */
593 >                decodedir(my_uvw[2], ap->ndir);
594 >                decodedir(my_uvw[0], ap->udir);
595 >                VCROSS(my_uvw[1], my_uvw[2], my_uvw[0]);
596 >                uvw = my_uvw;
597          }
598 <        for (k = 0; k < ne; k++) {              /* compute errors */
599 <                if (div[k].n > 1)
600 <                        div[k].k /= div[k].n;
384 <                div[k].n = 1;
385 <        }
386 <                                                /* sort the divisions */
387 <        qsort(div, ne, sizeof(AMBSAMP), ambcmp);
388 <                                                /* skim excess */
389 <        while (ne > ns) {
390 <                ne--;
391 <                addcolor(acol, div[ne].v);
392 <        }
393 <                                                /* super-sample */
394 <        for (i = ns; i > 0; i--) {
395 <                rayorigin(&ar, r, AMBIENT, 0.5);        /* pretested */
396 <                hlist[1] = div[0].t;
397 <                hlist[2] = div[0].p;
398 <                hlist[3] = 0;
399 <                zd = sqrt((div[0].t+urand(ilhash(hlist,4)+div[0].n))/nt);
400 <                hlist[3] = 1;
401 <                phi = 2.0*PI * (div[0].p+urand(ilhash(hlist,4)+div[0].n))/np;
402 <                xd = cos(phi) * zd;
403 <                yd = sin(phi) * zd;
404 <                zd = sqrt(1.0 - zd*zd);
405 <                for (k = 0; k < 3; k++)
406 <                        ar.rdir[k] = xd*ux[k]+yd*uy[k]+zd*r->ron[k];
407 <                dimlist[ndims++] = div[0].t*np + div[0].p + 38813;
408 <                rayvalue(&ar);
409 <                ndims--;
410 <                rayvalue(&ar);
411 <                if (ar.rot < FHUGE)
412 <                        arad += 1.0 / ar.rot;
413 <                                                /* recompute error */
414 <                copycolor(dnew.v, div[0].v);
415 <                addcolor(dnew.v, ar.rcol);
416 <                dnew.n = div[0].n + 1;
417 <                dnew.t = div[0].t; dnew.p = div[0].p;
418 <                b2 = bright(dnew.v)/dnew.n - bright(ar.rcol);
419 <                b2 = b2*b2 + div[0].k*(div[0].n*div[0].n);
420 <                dnew.k = b2/(dnew.n*dnew.n);
421 <                                                /* reinsert */
422 <                for (k = 0; k < ne-1 && dnew.k < div[k+1].k; k++)
423 <                        copystruct(&div[k], &div[k+1]);
424 <                copystruct(&div[k], &dnew);
598 >        for (i = 3; i--; )              /* gradient due to translation */
599 >                d += (pv[i] - ap->pos[i]) *
600 >                        (ap->gpos[0]*uvw[0][i] + ap->gpos[1]*uvw[1][i]);
601  
602 <                if (ne >= i) {          /* extract darkest division */
603 <                        ne--;
604 <                        if (div[ne].n > 1) {
605 <                                b = 1.0/div[ne].n;
606 <                                scalecolor(div[ne].v, b);
607 <                                div[ne].n = 1;
602 >        VCROSS(v1, uvw[2], nv);         /* gradient due to rotation */
603 >        for (i = 3; i--; )
604 >                d += v1[i] * (ap->gdir[0]*uvw[0][i] + ap->gdir[1]*uvw[1][i]);
605 >        
606 >        if (d < min_d)                  /* clamp min/max scaling */
607 >                d = min_d;
608 >        else if (d > max_d)
609 >                d = max_d;
610 >        copycolor(cr, ap->val);
611 >        scalecolor(cr, d);
612 >        return(d > min_d);
613 > }
614 >
615 >
616 > static void
617 > avinsert(                               /* insert ambient value in our tree */
618 >        AMBVAL *av
619 > )
620 > {
621 >        AMBTREE  *at;
622 >        AMBVAL  *ap;
623 >        AMBVAL  avh;
624 >        FVECT  ck0;
625 >        double  s;
626 >        int  branch;
627 >        int  i;
628 >
629 >        if (av->rad[0] <= FTINY)
630 >                error(CONSISTENCY, "zero ambient radius in avinsert");
631 >        at = &atrunk;
632 >        VCOPY(ck0, thescene.cuorg);
633 >        s = thescene.cusize;
634 >        while (s*(OCTSCALE/2) > av->rad[1]*ambacc) {
635 >                if (at->kid == NULL)
636 >                        if ((at->kid = newambtree()) == NULL)
637 >                                error(SYSTEM, "out of memory in avinsert");
638 >                s *= 0.5;
639 >                branch = 0;
640 >                for (i = 0; i < 3; i++)
641 >                        if (av->pos[i] > ck0[i] + s) {
642 >                                ck0[i] += s;
643 >                                branch |= 1 << i;
644                          }
645 <                        addcolor(acol, div[ne].v);
434 <                }
645 >                at = at->kid + branch;
646          }
647 <        scalecolor(acol, 1.0/ndivs);
648 <        if (arad <= FTINY)
649 <                arad = FHUGE;
650 <        else
651 <                arad = (ndivs+ns) / arad / sqrt(r->rweight);
652 <        if (arad > maxarad)
653 <                arad = maxarad;
654 <        else if (arad < minarad)
655 <                arad = minarad;
445 <        if (div != NULL)
446 <                free((char *)div);
447 <        return(arad);
647 >        avh.next = at->alist;           /* order by increasing level */
648 >        for (ap = &avh; ap->next != NULL; ap = ap->next)
649 >                if ( ap->next->lvl > av->lvl ||
650 >                                (ap->next->lvl == av->lvl) &
651 >                                (ap->next->weight <= av->weight) )
652 >                        break;
653 >        av->next = ap->next;
654 >        ap->next = (AMBVAL*)av;
655 >        at->alist = avh.next;
656   }
657  
658  
659 < static int
660 < ambcmp(d1, d2)                          /* decreasing order */
661 < AMBSAMP  *d1, *d2;
659 > static void
660 > initambfile(            /* initialize ambient file */
661 >        int  cre8
662 > )
663   {
664 <        if (d1->k < d2->k)
665 <                return(1);
666 <        if (d1->k > d2->k)
667 <                return(-1);
668 <        return(0);
664 >        extern char  *progname, *octname;
665 >        static char  *mybuf = NULL;
666 >
667 > #ifdef  F_SETLKW
668 >        aflock(cre8 ? F_WRLCK : F_RDLCK);
669 > #endif
670 >        SET_FILE_BINARY(ambfp);
671 >        if (mybuf == NULL)
672 >                mybuf = (char *)bmalloc(BUFSIZ+8);
673 >        setbuf(ambfp, mybuf);
674 >        if (cre8) {                     /* new file */
675 >                newheader("RADIANCE", ambfp);
676 >                fprintf(ambfp, "%s -av %g %g %g -aw %d -ab %d -aa %g ",
677 >                                progname, colval(ambval,RED),
678 >                                colval(ambval,GRN), colval(ambval,BLU),
679 >                                ambvwt, ambounce, ambacc);
680 >                fprintf(ambfp, "-ad %d -as %d -ar %d ",
681 >                                ambdiv, ambssamp, ambres);
682 >                if (octname != NULL)
683 >                        fputs(octname, ambfp);
684 >                fputc('\n', ambfp);
685 >                fprintf(ambfp, "SOFTWARE= %s\n", VersionID);
686 >                fputnow(ambfp);
687 >                fputformat(AMBFMT, ambfp);
688 >                fputc('\n', ambfp);
689 >                putambmagic(ambfp);
690 >        } else if (checkheader(ambfp, AMBFMT, NULL) < 0 || !hasambmagic(ambfp))
691 >                error(USER, "bad ambient file");
692   }
693  
694  
695 < static
696 < avsave(av)                              /* save an ambient value */
697 < AMBVAL  *av;
695 > static void
696 > avsave(                         /* insert and save an ambient value */
697 >        AMBVAL  *av
698 > )
699   {
700 < #ifdef  AMBFLUSH
468 <        static int  nunflshed = 0;
469 < #endif
700 >        avstore(av);
701          if (ambfp == NULL)
702                  return;
703 <        if (fwrite((char *)av, sizeof(AMBVAL), 1, ambfp) != 1)
703 >        if (writambval(av, ambfp) < 0)
704                  goto writerr;
705 < #ifdef  AMBFLUSH
706 <        if (++nunflshed >= AMBFLUSH) {
476 <                if (fflush(ambfp) == EOF)
705 >        if (++nunflshed >= AMBFLUSH)
706 >                if (ambsync() == EOF)
707                          goto writerr;
478                nunflshed = 0;
479        }
480 #endif
708          return;
709   writerr:
710 <        error(SYSTEM, "error writing ambient file");
710 >        error(SYSTEM, "error writing to ambient file");
711   }
712  
713  
714 < static
715 < avinsert(aval, at, c0, s)               /* insert ambient value in a tree */
716 < AMBVAL  *aval;
717 < register AMBTREE  *at;
491 < FVECT  c0;
492 < double  s;
714 > static AMBVAL *
715 > avstore(                                /* allocate memory and save aval */
716 >        AMBVAL  *aval
717 > )
718   {
719 <        FVECT  ck0;
720 <        int  branch;
496 <        register AMBVAL  *av;
497 <        register int  i;
719 >        AMBVAL  *av;
720 >        double  d;
721  
722          if ((av = newambval()) == NULL)
723 <                goto memerr;
724 <        copystruct(av, aval);
725 <        VCOPY(ck0, c0);
726 <        while (s*(OCTSCALE/2) > av->rad*ambacc) {
727 <                if (at->kid == NULL)
728 <                        if ((at->kid = newambtree()) == NULL)
729 <                                goto memerr;
730 <                s *= 0.5;
731 <                branch = 0;
732 <                for (i = 0; i < 3; i++)
733 <                        if (av->pos[i] > ck0[i] + s) {
734 <                                ck0[i] += s;
735 <                                branch |= 1 << i;
723 >                error(SYSTEM, "out of memory in avstore");
724 >        *av = *aval;
725 >        av->latick = ambclock;
726 >        av->next = NULL;
727 >        nambvals++;
728 >        d = bright(av->val);
729 >        if (d > FTINY) {                /* add to log sum for averaging */
730 >                avsum += log(d);
731 >                navsum++;
732 >        }
733 >        avinsert(av);                   /* insert in our cache tree */
734 >        return(av);
735 > }
736 >
737 >
738 > #define ATALLOCSZ       512             /* #/8 trees to allocate at once */
739 >
740 > static AMBTREE  *atfreelist = NULL;     /* free ambient tree structures */
741 >
742 >
743 > static AMBTREE *
744 > newambtree(void)                                /* allocate 8 ambient tree structs */
745 > {
746 >        AMBTREE  *atp, *upperlim;
747 >
748 >        if (atfreelist == NULL) {       /* get more nodes */
749 >                atfreelist = (AMBTREE *)malloc(ATALLOCSZ*8*sizeof(AMBTREE));
750 >                if (atfreelist == NULL)
751 >                        return(NULL);
752 >                                        /* link new free list */
753 >                upperlim = atfreelist + 8*(ATALLOCSZ-1);
754 >                for (atp = atfreelist; atp < upperlim; atp += 8)
755 >                        atp->kid = atp + 8;
756 >                atp->kid = NULL;
757 >        }
758 >        atp = atfreelist;
759 >        atfreelist = atp->kid;
760 >        memset(atp, 0, 8*sizeof(AMBTREE));
761 >        return(atp);
762 > }
763 >
764 >
765 > static void
766 > freeambtree(                    /* free 8 ambient tree structs */
767 >        AMBTREE  *atp
768 > )
769 > {
770 >        atp->kid = atfreelist;
771 >        atfreelist = atp;
772 > }
773 >
774 >
775 > static void
776 > unloadatree(                    /* unload an ambient value tree */
777 >        AMBTREE  *at,
778 >        unloadtf_t *f
779 > )
780 > {
781 >        AMBVAL  *av;
782 >        int  i;
783 >                                        /* transfer values at this node */
784 >        for (av = at->alist; av != NULL; av = at->alist) {
785 >                at->alist = av->next;
786 >                av->next = NULL;
787 >                (*f)(av);
788 >        }
789 >        if (at->kid == NULL)
790 >                return;
791 >        for (i = 0; i < 8; i++)         /* transfer and free children */
792 >                unloadatree(at->kid+i, f);
793 >        freeambtree(at->kid);
794 >        at->kid = NULL;
795 > }
796 >
797 >
798 > static struct avl {
799 >        AMBVAL  *p;
800 >        unsigned long   t;
801 > }       *avlist1;                       /* ambient value list with ticks */
802 > static AMBVAL   **avlist2;              /* memory positions for sorting */
803 > static int      i_avlist;               /* index for lists */
804 >
805 > static int alatcmp(const void *av1, const void *av2);
806 >
807 > static void
808 > avfree(AMBVAL *av)
809 > {
810 >        free(av);
811 > }
812 >
813 > static void
814 > av2list(
815 >        AMBVAL *av
816 > )
817 > {
818 > #ifdef DEBUG
819 >        if (i_avlist >= nambvals)
820 >                error(CONSISTENCY, "too many ambient values in av2list1");
821 > #endif
822 >        avlist1[i_avlist].p = avlist2[i_avlist] = (AMBVAL*)av;
823 >        avlist1[i_avlist++].t = av->latick;
824 > }
825 >
826 >
827 > static int
828 > alatcmp(                        /* compare ambient values for MRA */
829 >        const void *av1,
830 >        const void *av2
831 > )
832 > {
833 >        long  lc = ((struct avl *)av2)->t - ((struct avl *)av1)->t;
834 >        return(lc<0 ? -1 : lc>0 ? 1 : 0);
835 > }
836 >
837 >
838 > /* GW NOTE 2002/10/3:
839 > * I used to compare AMBVAL pointers, but found that this was the
840 > * cause of a serious consistency error with gcc, since the optimizer
841 > * uses some dangerous trick in pointer subtraction that
842 > * assumes pointers differ by exact struct size increments.
843 > */
844 > static int
845 > aposcmp(                        /* compare ambient value positions */
846 >        const void      *avp1,
847 >        const void      *avp2
848 > )
849 > {
850 >        long    diff = *(char * const *)avp1 - *(char * const *)avp2;
851 >        if (diff < 0)
852 >                return(-1);
853 >        return(diff > 0);
854 > }
855 >
856 >
857 > static int
858 > avlmemi(                                /* find list position from address */
859 >        AMBVAL  *avaddr
860 > )
861 > {
862 >        AMBVAL  **avlpp;
863 >
864 >        avlpp = (AMBVAL **)bsearch(&avaddr, avlist2,
865 >                        nambvals, sizeof(AMBVAL *), aposcmp);
866 >        if (avlpp == NULL)
867 >                error(CONSISTENCY, "address not found in avlmemi");
868 >        return(avlpp - avlist2);
869 > }
870 >
871 >
872 > static void
873 > sortambvals(                    /* resort ambient values */
874 >        int     always
875 > )
876 > {
877 >        AMBTREE  oldatrunk;
878 >        AMBVAL  tav, *tap, *pnext;
879 >        int     i, j;
880 >                                        /* see if it's time yet */
881 >        if (!always && (ambclock++ < lastsort+sortintvl ||
882 >                        nambvals < SORT_THRESH))
883 >                return;
884 >        /*
885 >         * The idea here is to minimize memory thrashing
886 >         * in VM systems by improving reference locality.
887 >         * We do this by periodically sorting our stored ambient
888 >         * values in memory in order of most recently to least
889 >         * recently accessed.  This ordering was chosen so that new
890 >         * ambient values (which tend to be less important) go into
891 >         * higher memory with the infrequently accessed values.
892 >         *      Since we expect our values to need sorting less
893 >         * frequently as the process continues, we double our
894 >         * waiting interval after each call.
895 >         *      This routine is also called by setambacc() with
896 >         * the "always" parameter set to 1 so that the ambient
897 >         * tree will be rebuilt with the new accuracy parameter.
898 >         */
899 >        if (tracktime) {                /* allocate pointer arrays to sort */
900 >                avlist2 = (AMBVAL **)malloc(nambvals*sizeof(AMBVAL *));
901 >                avlist1 = (struct avl *)malloc(nambvals*sizeof(struct avl));
902 >        } else {
903 >                avlist2 = NULL;
904 >                avlist1 = NULL;
905 >        }
906 >        if (avlist1 == NULL) {          /* no time tracking -- rebuild tree? */
907 >                if (avlist2 != NULL)
908 >                        free(avlist2);
909 >                if (always) {           /* rebuild without sorting */
910 >                        oldatrunk = atrunk;
911 >                        atrunk.alist = NULL;
912 >                        atrunk.kid = NULL;
913 >                        unloadatree(&oldatrunk, avinsert);
914 >                }
915 >        } else {                        /* sort memory by last access time */
916 >                /*
917 >                 * Sorting memory is tricky because it isn't contiguous.
918 >                 * We have to sort an array of pointers by MRA and also
919 >                 * by memory position.  We then copy values in "loops"
920 >                 * to minimize memory hits.  Nevertheless, we will visit
921 >                 * everyone at least twice, and this is an expensive process
922 >                 * when we're thrashing, which is when we need to do it.
923 >                 */
924 > #ifdef DEBUG
925 >                sprintf(errmsg, "sorting %u ambient values at ambclock=%lu...",
926 >                                nambvals, ambclock);
927 >                eputs(errmsg);
928 > #endif
929 >                i_avlist = 0;
930 >                unloadatree(&atrunk, av2list);  /* empty current tree */
931 > #ifdef DEBUG
932 >                if (i_avlist < nambvals)
933 >                        error(CONSISTENCY, "missing ambient values in sortambvals");
934 > #endif
935 >                qsort(avlist1, nambvals, sizeof(struct avl), alatcmp);
936 >                qsort(avlist2, nambvals, sizeof(AMBVAL *), aposcmp);
937 >                for (i = 0; i < nambvals; i++) {
938 >                        if (avlist1[i].p == NULL)
939 >                                continue;
940 >                        tap = avlist2[i];
941 >                        tav = *tap;
942 >                        for (j = i; (pnext = avlist1[j].p) != tap;
943 >                                        j = avlmemi(pnext)) {
944 >                                *(avlist2[j]) = *pnext;
945 >                                avinsert(avlist2[j]);
946 >                                avlist1[j].p = NULL;
947                          }
948 <                at = at->kid + branch;
948 >                        *(avlist2[j]) = tav;
949 >                        avinsert(avlist2[j]);
950 >                        avlist1[j].p = NULL;
951 >                }
952 >                free(avlist1);
953 >                free(avlist2);
954 >                                                /* compute new sort interval */
955 >                sortintvl = ambclock - lastsort;
956 >                if (sortintvl >= MAX_SORT_INTVL/2)
957 >                        sortintvl = MAX_SORT_INTVL;
958 >                else
959 >                        sortintvl <<= 1;        /* wait twice as long next */
960 > #ifdef DEBUG
961 >                eputs("done\n");
962 > #endif
963          }
964 <        av->next = at->alist;
965 <        at->alist = av;
966 <        return;
519 < memerr:
520 <        error(SYSTEM, "out of memory in avinsert");
964 >        if (ambclock >= MAXACLOCK)
965 >                ambclock = MAXACLOCK/2;
966 >        lastsort = ambclock;
967   }
968 +
969 +
970 + #ifdef  F_SETLKW
971 +
972 + static void
973 + aflock(                 /* lock/unlock ambient file */
974 +        int  typ
975 + )
976 + {
977 +        static struct flock  fls;       /* static so initialized to zeroes */
978 +
979 +        if (typ == fls.l_type)          /* already called? */
980 +                return;
981 +
982 +        fls.l_type = typ;
983 +        do
984 +                if (fcntl(fileno(ambfp), F_SETLKW, &fls) != -1)
985 +                        return;
986 +        while (errno == EINTR);
987 +        
988 +        error(SYSTEM, "cannot (un)lock ambient file");
989 + }
990 +
991 +
992 + int
993 + ambsync(void)                   /* synchronize ambient file */
994 + {
995 +        long  flen;
996 +        AMBVAL  avs;
997 +        int  n;
998 +
999 +        if (ambfp == NULL)      /* no ambient file? */
1000 +                return(0);
1001 +                                /* gain appropriate access */
1002 +        aflock(nunflshed ? F_WRLCK : F_RDLCK);
1003 +                                /* see if file has grown */
1004 +        if ((flen = lseek(fileno(ambfp), (off_t)0, SEEK_END)) < 0)
1005 +                goto seekerr;
1006 +        if ((n = flen - lastpos) > 0) {         /* file has grown */
1007 +                if (ambinp == NULL) {           /* get new file pointer */
1008 +                        ambinp = fopen(ambfile, "rb");
1009 +                        if (ambinp == NULL)
1010 +                                error(SYSTEM, "fopen failed in ambsync");
1011 +                }
1012 +                if (fseek(ambinp, lastpos, SEEK_SET) < 0)
1013 +                        goto seekerr;
1014 +                while (n >= AMBVALSIZ) {        /* load contributed values */
1015 +                        if (!readambval(&avs, ambinp)) {
1016 +                                sprintf(errmsg,
1017 +                        "ambient file \"%s\" corrupted near character %ld",
1018 +                                                ambfile, flen - n);
1019 +                                error(WARNING, errmsg);
1020 +                                break;
1021 +                        }
1022 +                        avstore(&avs);
1023 +                        n -= AMBVALSIZ;
1024 +                }
1025 +                lastpos = flen - n;             /* check alignment */
1026 +                if (n && lseek(fileno(ambfp), (off_t)lastpos, SEEK_SET) < 0)
1027 +                        goto seekerr;
1028 +        }
1029 +        n = fflush(ambfp);                      /* calls write() at last */
1030 +        lastpos += (long)nunflshed*AMBVALSIZ;
1031 +        aflock(F_UNLCK);                        /* release file */
1032 +        nunflshed = 0;
1033 +        return(n);
1034 + seekerr:
1035 +        error(SYSTEM, "seek failed in ambsync");
1036 +        return(EOF);    /* pro forma return */
1037 + }
1038 +
1039 + #else   /* ! F_SETLKW */
1040 +
1041 + int
1042 + ambsync(void)                   /* flush ambient file */
1043 + {
1044 +        if (ambfp == NULL)
1045 +                return(0);
1046 +        nunflshed = 0;
1047 +        return(fflush(ambfp));
1048 + }
1049 +
1050 + #endif  /* ! F_SETLKW */

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines