ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/tonemap.c
Revision: 3.19
Committed: Tue Nov 15 06:53:00 2005 UTC (18 years, 5 months ago) by greg
Content type: text/plain
Branch: MAIN
Changes since 3.18: +17 -1 lines
Log Message:
Added tmCvLuminance() call

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: tonemap.c,v 3.18 2005/01/07 22:05:30 greg Exp $";
3 #endif
4 /*
5 * Tone mapping functions.
6 * See tonemap.h for detailed function descriptions.
7 * Added von Kries white-balance calculations 10/01 (GW).
8 *
9 * Externals declared in tonemap.h
10 */
11
12 #include "copyright.h"
13
14 #include <stdio.h>
15 #include <math.h>
16 #include "tmprivat.h"
17 #include "tmerrmsg.h"
18
19 #define exp10(x) exp(M_LN10*(x))
20
21 /* our list of conversion packages */
22 struct tmPackage *tmPkg[TM_MAXPKG];
23 int tmNumPkgs = 0; /* number of registered packages */
24
25
26 TMstruct *
27 tmInit( /* initialize new tone mapping */
28 int flags,
29 RGBPRIMP monpri,
30 double gamval
31 )
32 {
33 COLORMAT cmat;
34 TMstruct *tmnew;
35 int i;
36 /* allocate structure */
37 tmnew = (TMstruct *)malloc(sizeof(TMstruct));
38 if (tmnew == NULL)
39 return(NULL);
40
41 tmnew->flags = flags & ~TM_F_UNIMPL;
42 if (tmnew->flags & TM_F_BW)
43 tmnew->flags &= ~TM_F_MESOPIC;
44 /* set monitor transform */
45 if (monpri == NULL || monpri == stdprims || tmnew->flags & TM_F_BW) {
46 tmnew->monpri = stdprims;
47 tmnew->clf[RED] = rgb2xyzmat[1][0];
48 tmnew->clf[GRN] = rgb2xyzmat[1][1];
49 tmnew->clf[BLU] = rgb2xyzmat[1][2];
50 } else {
51 comprgb2xyzWBmat(cmat, tmnew->monpri=monpri);
52 tmnew->clf[RED] = cmat[1][0];
53 tmnew->clf[GRN] = cmat[1][1];
54 tmnew->clf[BLU] = cmat[1][2];
55 }
56 /* set gamma value */
57 if (gamval < MINGAM)
58 tmnew->mongam = DEFGAM;
59 else
60 tmnew->mongam = gamval;
61 /* set color divisors */
62 for (i = 0; i < 3; i++)
63 tmnew->cdiv[i] = 256.*pow(tmnew->clf[i], 1./tmnew->mongam);
64
65 /* set input transform */
66 tmnew->inppri = tmnew->monpri;
67 tmnew->cmat[0][0] = tmnew->cmat[1][1] = tmnew->cmat[2][2] =
68 tmnew->inpsf = WHTEFFICACY;
69 tmnew->cmat[0][1] = tmnew->cmat[0][2] = tmnew->cmat[1][0] =
70 tmnew->cmat[1][2] = tmnew->cmat[2][0] = tmnew->cmat[2][1] = 0.;
71 tmnew->inpdat = NULL;
72 tmnew->hbrmin = 10; tmnew->hbrmax = -10;
73 tmnew->histo = NULL;
74 tmnew->mbrmin = 10; tmnew->mbrmax = -10;
75 tmnew->lumap = NULL;
76 /* zero private data */
77 for (i = TM_MAXPKG; i--; )
78 tmnew->pd[i] = NULL;
79 tmnew->lastError = TM_E_OK;
80 tmnew->lastFunc = "NoErr";
81 /* return new TMstruct */
82 return(tmnew);
83 }
84
85
86 int
87 tmSetSpace( /* set input color space for conversions */
88 TMstruct *tms,
89 RGBPRIMP pri,
90 double sf,
91 MEM_PTR dat
92 )
93 {
94 static const char funcName[] = "tmSetSpace";
95 int i, j;
96 /* error check */
97 if (tms == NULL)
98 returnErr(TM_E_TMINVAL);
99 if (sf <= 1e-12)
100 returnErr(TM_E_ILLEGAL);
101 /* check if no change */
102 if (pri == tms->inppri && FEQ(sf, tms->inpsf) && dat == tms->inpdat)
103 returnOK;
104 tms->inppri = pri; /* let's set it */
105 tms->inpsf = sf;
106 tms->inpdat = dat;
107
108 if (tms->flags & TM_F_BW) { /* color doesn't matter */
109 tms->monpri = tms->inppri; /* eliminate xform */
110 if (tms->inppri == TM_XYZPRIM) {
111 tms->clf[CIEX] = tms->clf[CIEZ] = 0.;
112 tms->clf[CIEY] = 1.;
113 } else {
114 comprgb2xyzWBmat(tms->cmat, tms->monpri);
115 tms->clf[RED] = tms->cmat[1][0];
116 tms->clf[GRN] = tms->cmat[1][1];
117 tms->clf[BLU] = tms->cmat[1][2];
118 }
119 tms->cmat[0][0] = tms->cmat[1][1] = tms->cmat[2][2] =
120 tms->inpsf;
121 tms->cmat[0][1] = tms->cmat[0][2] = tms->cmat[1][0] =
122 tms->cmat[1][2] = tms->cmat[2][0] = tms->cmat[2][1] = 0.;
123
124 } else if (tms->inppri == TM_XYZPRIM) /* input is XYZ */
125 compxyz2rgbWBmat(tms->cmat, tms->monpri);
126
127 else { /* input is RGB */
128 if (tms->inppri != tms->monpri &&
129 PRIMEQ(tms->inppri, tms->monpri))
130 tms->inppri = tms->monpri; /* no xform */
131 comprgb2rgbWBmat(tms->cmat, tms->inppri, tms->monpri);
132 }
133 for (i = 0; i < 3; i++)
134 for (j = 0; j < 3; j++)
135 tms->cmat[i][j] *= tms->inpsf;
136 /* set color divisors */
137 for (i = 0; i < 3; i++)
138 if (tms->clf[i] > .001)
139 tms->cdiv[i] =
140 256.*pow(tms->clf[i], 1./tms->mongam);
141 else
142 tms->cdiv[i] = 1;
143 /* notify packages */
144 for (i = tmNumPkgs; i--; )
145 if (tms->pd[i] != NULL && tmPkg[i]->NewSpace != NULL)
146 (*tmPkg[i]->NewSpace)(tms);
147 returnOK;
148 }
149
150
151 void
152 tmClearHisto( /* clear current histogram */
153 TMstruct *tms
154 )
155 {
156 if (tms == NULL || tms->histo == NULL)
157 return;
158 free((MEM_PTR)tms->histo);
159 tms->histo = NULL;
160 }
161
162
163 int
164 tmCvColors( /* convert float colors */
165 TMstruct *tms,
166 TMbright *ls,
167 BYTE *cs,
168 COLOR *scan,
169 int len
170 )
171 {
172 static const char funcName[] = "tmCvColors";
173 static COLOR csmall = {.5*MINLUM, .5*MINLUM, .5*MINLUM};
174 COLOR cmon;
175 double lum, slum;
176 double d;
177 int i;
178
179 if (tms == NULL)
180 returnErr(TM_E_TMINVAL);
181 if ((ls == NULL) | (scan == NULL) | (len < 0))
182 returnErr(TM_E_ILLEGAL);
183 for (i = len; i--; ) {
184 if (tmNeedMatrix(tms)) { /* get monitor RGB */
185 colortrans(cmon, tms->cmat, scan[i]);
186 } else {
187 cmon[RED] = tms->inpsf*scan[i][RED];
188 cmon[GRN] = tms->inpsf*scan[i][GRN];
189 cmon[BLU] = tms->inpsf*scan[i][BLU];
190 }
191 /* world luminance */
192 lum = tms->clf[RED]*cmon[RED] +
193 tms->clf[GRN]*cmon[GRN] +
194 tms->clf[BLU]*cmon[BLU] ;
195 /* check range */
196 if (clipgamut(cmon, lum, CGAMUT_LOWER, csmall, cwhite))
197 lum = tms->clf[RED]*cmon[RED] +
198 tms->clf[GRN]*cmon[GRN] +
199 tms->clf[BLU]*cmon[BLU] ;
200 if (lum < MINLUM) {
201 ls[i] = MINBRT-1; /* bogus value */
202 lum = MINLUM;
203 } else {
204 d = TM_BRTSCALE*log(lum); /* encode it */
205 ls[i] = d>0. ? (int)(d+.5) : (int)(d-.5);
206 }
207 if (cs == TM_NOCHROM) /* no color? */
208 continue;
209 if (tms->flags & TM_F_MESOPIC && lum < LMESUPPER) {
210 slum = scotlum(cmon); /* mesopic adj. */
211 if (lum < LMESLOWER)
212 cmon[RED] = cmon[GRN] = cmon[BLU] = slum;
213 else {
214 d = (lum - LMESLOWER)/(LMESUPPER - LMESLOWER);
215 if (tms->flags & TM_F_BW)
216 cmon[RED] = cmon[GRN] =
217 cmon[BLU] = d*lum;
218 else
219 scalecolor(cmon, d);
220 d = (1.-d)*slum;
221 cmon[RED] += d;
222 cmon[GRN] += d;
223 cmon[BLU] += d;
224 }
225 } else if (tms->flags & TM_F_BW) {
226 cmon[RED] = cmon[GRN] = cmon[BLU] = lum;
227 }
228 d = tms->clf[RED]*cmon[RED]/lum;
229 cs[3*i ] = d>=.999 ? 255 :
230 (int)(256.*pow(d, 1./tms->mongam));
231 d = tms->clf[GRN]*cmon[GRN]/lum;
232 cs[3*i+1] = d>=.999 ? 255 :
233 (int)(256.*pow(d, 1./tms->mongam));
234 d = tms->clf[BLU]*cmon[BLU]/lum;
235 cs[3*i+2] = d>=.999 ? 255 :
236 (int)(256.*pow(d, 1./tms->mongam));
237 }
238 returnOK;
239 }
240
241
242 TMbright
243 tmCvLuminance( /* convert a single luminance */
244 double lum
245 )
246 {
247 double d;
248
249 if (lum <= TM_NOLUM)
250 return(TM_NOBRT);
251 d = TM_BRTSCALE*log(lum);
252 if (d > 0.)
253 return((TMbright)(d+.5));
254 return((TMbright)(d-.5));
255 }
256
257
258 int
259 tmCvGrays( /* convert float gray values */
260 TMstruct *tms,
261 TMbright *ls,
262 float *scan,
263 int len
264 )
265 {
266 static const char funcName[] = "tmCvGrays";
267 double d;
268 int i;
269
270 if (tms == NULL)
271 returnErr(TM_E_TMINVAL);
272 if ((ls == NULL) | (scan == NULL) | (len < 0))
273 returnErr(TM_E_ILLEGAL);
274 for (i = len; i--; )
275 if (scan[i] <= TM_NOLUM) {
276 ls[i] = TM_NOBRT; /* bogus value */
277 } else {
278 d = TM_BRTSCALE*log(scan[i]); /* encode it */
279 ls[i] = d>0. ? (int)(d+.5) : (int)(d-.5);
280 }
281 returnOK;
282 }
283
284
285 int
286 tmAddHisto( /* add values to histogram */
287 TMstruct *tms,
288 TMbright *ls,
289 int len,
290 int wt
291 )
292 {
293 static const char funcName[] = "tmAddHisto";
294 int oldorig=0, oldlen, horig, hlen;
295 int i, j;
296
297 if (tms == NULL)
298 returnErr(TM_E_TMINVAL);
299 if (len < 0)
300 returnErr(TM_E_ILLEGAL);
301 if (len == 0)
302 returnOK;
303 /* first, grow limits */
304 if (tms->histo == NULL) {
305 for (i = len; i-- && ls[i] < MINBRT; )
306 ;
307 if (i < 0)
308 returnOK;
309 tms->hbrmin = tms->hbrmax = ls[i];
310 oldlen = 0;
311 } else {
312 oldorig = (tms->hbrmin-MINBRT)/HISTEP;
313 oldlen = (tms->hbrmax-MINBRT)/HISTEP + 1 - oldorig;
314 }
315 for (i = len; i--; ) {
316 if ((j = ls[i]) < MINBRT)
317 continue;
318 if (j < tms->hbrmin)
319 tms->hbrmin = j;
320 else if (j > tms->hbrmax)
321 tms->hbrmax = j;
322 }
323 horig = (tms->hbrmin-MINBRT)/HISTEP;
324 hlen = (tms->hbrmax-MINBRT)/HISTEP + 1 - horig;
325 if (hlen > oldlen) { /* (re)allocate histogram */
326 int *newhist = (int *)calloc(hlen, sizeof(int));
327 if (newhist == NULL)
328 returnErr(TM_E_NOMEM);
329 if (oldlen) { /* copy and free old */
330 for (i = oldlen, j = i+oldorig-horig; i; )
331 newhist[--j] = tms->histo[--i];
332 free((MEM_PTR)tms->histo);
333 }
334 tms->histo = newhist;
335 }
336 if (wt == 0)
337 returnOK;
338 for (i = len; i--; ) /* add in new counts */
339 if (ls[i] >= MINBRT)
340 tms->histo[ (ls[i]-MINBRT)/HISTEP - horig ] += wt;
341 returnOK;
342 }
343
344
345 static double
346 htcontrs( /* human threshold contrast sensitivity, dL(La) */
347 double La
348 )
349 {
350 double l10La, l10dL;
351 /* formula taken from Ferwerda et al. [SG96] */
352 if (La < 1.148e-4)
353 return(1.38e-3);
354 l10La = log10(La);
355 if (l10La < -1.44) /* rod response regime */
356 l10dL = pow(.405*l10La + 1.6, 2.18) - 2.86;
357 else if (l10La < -.0184)
358 l10dL = l10La - .395;
359 else if (l10La < 1.9) /* cone response regime */
360 l10dL = pow(.249*l10La + .65, 2.7) - .72;
361 else
362 l10dL = l10La - 1.255;
363
364 return(exp10(l10dL));
365 }
366
367
368 static int
369 tmNewMap( /* allocate new tone-mapping array */
370 TMstruct *tms
371 )
372 {
373 if (tms->lumap != NULL && (tms->mbrmax - tms->mbrmin) !=
374 (tms->hbrmax - tms->hbrmin)) {
375 free((MEM_PTR)tms->lumap);
376 tms->lumap = NULL;
377 }
378 tms->mbrmin = tms->hbrmin;
379 tms->mbrmax = tms->hbrmax;
380 if (tms->mbrmin > tms->mbrmax)
381 return 0;
382 if (tms->lumap == NULL)
383 tms->lumap = (unsigned short *)malloc(sizeof(unsigned short)*
384 (tms->mbrmax-tms->mbrmin+1));
385 return(tms->lumap != NULL);
386 }
387
388
389 int
390 tmFixedMapping( /* compute fixed, linear tone-mapping */
391 TMstruct *tms,
392 double expmult,
393 double gamval
394 )
395 {
396 static const char funcName[] = "tmFixedMapping";
397 double d;
398 int i;
399
400 if (!tmNewMap(tms))
401 returnErr(TM_E_NOMEM);
402 if (expmult <= .0)
403 expmult = 1.;
404 if (gamval < MINGAM)
405 gamval = tms->mongam;
406 d = log(expmult/tms->inpsf);
407 for (i = tms->mbrmax-tms->mbrmin+1; i--; )
408 tms->lumap[i] = 256. * exp(
409 ( d + (tms->mbrmin+i)*(1./TM_BRTSCALE) )
410 / gamval );
411 returnOK;
412 }
413
414
415 int
416 tmComputeMapping( /* compute histogram tone-mapping */
417 TMstruct *tms,
418 double gamval,
419 double Lddyn,
420 double Ldmax
421 )
422 {
423 static const char funcName[] = "tmComputeMapping";
424 int *histo;
425 float *cumf;
426 int brt0, histlen, threshold, ceiling, trimmings;
427 double logLddyn, Ldmin, Ldavg, Lwavg, Tr, Lw, Ld;
428 int32 histot;
429 double sum;
430 double d;
431 int i, j;
432
433 if (tms == NULL || tms->histo == NULL)
434 returnErr(TM_E_TMINVAL);
435 /* check arguments */
436 if (Lddyn < MINLDDYN) Lddyn = DEFLDDYN;
437 if (Ldmax < MINLDMAX) Ldmax = DEFLDMAX;
438 if (gamval < MINGAM) gamval = tms->mongam;
439 /* compute handy values */
440 Ldmin = Ldmax/Lddyn;
441 logLddyn = log(Lddyn);
442 Ldavg = sqrt(Ldmax*Ldmin);
443 i = (tms->hbrmin-MINBRT)/HISTEP;
444 brt0 = MINBRT + HISTEP/2 + i*HISTEP;
445 histlen = (tms->hbrmax-MINBRT)/HISTEP + 1 - i;
446 /* histogram total and mean */
447 histot = 0; sum = 0;
448 j = brt0 + histlen*HISTEP;
449 for (i = histlen; i--; ) {
450 histot += tms->histo[i];
451 sum += (j -= HISTEP) * tms->histo[i];
452 }
453 threshold = histot*0.005 + .5;
454 if (threshold < 4)
455 returnErr(TM_E_TMFAIL);
456 Lwavg = tmLuminance( (double)sum / histot );
457 /* allocate space for mapping */
458 if (!tmNewMap(tms))
459 returnErr(TM_E_NOMEM);
460 /* use linear tone mapping? */
461 if (tms->flags & TM_F_LINEAR)
462 goto linearmap;
463 /* clamp histogram */
464 histo = (int *)malloc(histlen*sizeof(int));
465 cumf = (float *)malloc((histlen+2)*sizeof(float));
466 if ((histo == NULL) | (cumf == NULL))
467 returnErr(TM_E_NOMEM);
468 cumf[histlen+1] = 1.; /* guard for assignment code */
469 for (i = histlen; i--; ) /* make malleable copy */
470 histo[i] = tms->histo[i];
471 do { /* iterate to solution */
472 sum = 0; /* cumulative probability */
473 for (i = 0; i < histlen; i++) {
474 cumf[i] = (double)sum/histot;
475 sum += histo[i];
476 }
477 cumf[histlen] = 1.;
478 Tr = histot * (double)(tms->hbrmax - tms->hbrmin) /
479 ((double)histlen*TM_BRTSCALE) / logLddyn;
480 ceiling = Tr + 1.;
481 trimmings = 0; /* clip to envelope */
482 for (i = histlen; i--; ) {
483 if (tms->flags & TM_F_HCONTR) {
484 Lw = tmLuminance(brt0 + i*HISTEP);
485 Ld = Ldmin * exp( logLddyn *
486 .5*(cumf[i]+cumf[i+1]) );
487 ceiling = Tr * (htcontrs(Ld) * Lw) /
488 (htcontrs(Lw) * Ld) + 1.;
489 }
490 if (histo[i] > ceiling) {
491 trimmings += histo[i] - ceiling;
492 histo[i] = ceiling;
493 }
494 }
495 /* check if we're out of data */
496 if ((histot -= trimmings) <= threshold) {
497 free((MEM_PTR)histo);
498 free((MEM_PTR)cumf);
499 goto linearmap;
500 }
501 } while (trimmings > threshold);
502 /* assign tone-mapping */
503 for (i = tms->mbrmax-tms->mbrmin+1; i--; ) {
504 j = d = (double)i/(tms->mbrmax-tms->mbrmin)*histlen;
505 d -= (double)j;
506 Ld = Ldmin*exp(logLddyn*((1.-d)*cumf[j]+d*cumf[j+1]));
507 d = (Ld - Ldmin)/(Ldmax - Ldmin);
508 tms->lumap[i] = 256.*pow(d, 1./gamval);
509 }
510 free((MEM_PTR)histo); /* clean up and return */
511 free((MEM_PTR)cumf);
512 returnOK;
513 linearmap: /* linear tone-mapping */
514 if (tms->flags & TM_F_HCONTR)
515 d = htcontrs(Ldavg) / htcontrs(Lwavg);
516 else
517 d = Ldavg / Lwavg;
518 return(tmFixedMapping(tms, tms->inpsf*d/Ldmax, gamval));
519 }
520
521
522 int
523 tmMapPixels( /* apply tone-mapping to pixel(s) */
524 TMstruct *tms,
525 BYTE *ps,
526 TMbright *ls,
527 BYTE *cs,
528 int len
529 )
530 {
531 static const char funcName[] = "tmMapPixels";
532 int32 li, pv;
533
534 if (tms == NULL || tms->lumap == NULL)
535 returnErr(TM_E_TMINVAL);
536 if ((ps == NULL) | (ls == NULL) | (len < 0))
537 returnErr(TM_E_ILLEGAL);
538 while (len--) {
539 if ((li = *ls++) < tms->mbrmin) {
540 li = 0;
541 } else {
542 if (li > tms->mbrmax)
543 li = tms->mbrmax;
544 li = tms->lumap[li - tms->mbrmin];
545 }
546 if (cs == TM_NOCHROM)
547 *ps++ = li>255 ? 255 : li;
548 else {
549 pv = *cs++ * li / tms->cdiv[RED];
550 *ps++ = pv>255 ? 255 : pv;
551 pv = *cs++ * li / tms->cdiv[GRN];
552 *ps++ = pv>255 ? 255 : pv;
553 pv = *cs++ * li / tms->cdiv[BLU];
554 *ps++ = pv>255 ? 255 : pv;
555 }
556 }
557 returnOK;
558 }
559
560
561
562
563 TMstruct *
564 tmDup( /* duplicate top tone mapping */
565 TMstruct *tms
566 )
567 {
568 int len;
569 int i;
570 TMstruct *tmnew;
571
572 if (tms == NULL) /* anything to duplicate? */
573 return(NULL);
574 tmnew = (TMstruct *)malloc(sizeof(TMstruct));
575 if (tmnew == NULL)
576 return(NULL);
577 *tmnew = *tms; /* copy everything */
578 if (tmnew->histo != NULL) { /* duplicate histogram */
579 len = (tmnew->hbrmax-MINBRT)/HISTEP + 1 -
580 (tmnew->hbrmin-MINBRT)/HISTEP;
581 tmnew->histo = (int *)malloc(len*sizeof(int));
582 if (tmnew->histo != NULL)
583 for (i = len; i--; )
584 tmnew->histo[i] = tms->histo[i];
585 }
586 if (tmnew->lumap != NULL) { /* duplicate luminance mapping */
587 len = tmnew->mbrmax-tmnew->mbrmin+1;
588 tmnew->lumap = (unsigned short *)malloc(
589 len*sizeof(unsigned short) );
590 if (tmnew->lumap != NULL)
591 for (i = len; i--; )
592 tmnew->lumap[i] = tms->lumap[i];
593 }
594 /* clear package data */
595 for (i = tmNumPkgs; i--; )
596 tmnew->pd[i] = NULL;
597 /* return copy */
598 return(tmnew);
599 }
600
601
602 void
603 tmDone(tms) /* done with tone mapping -- destroy it */
604 TMstruct *tms;
605 {
606 int i;
607 /* NULL arg. is equiv. to tms */
608 if (tms == NULL)
609 return;
610 /* free tables */
611 if (tms->histo != NULL)
612 free((MEM_PTR)tms->histo);
613 if (tms->lumap != NULL)
614 free((MEM_PTR)tms->lumap);
615 /* free private data */
616 for (i = tmNumPkgs; i--; )
617 if (tms->pd[i] != NULL)
618 (*tmPkg[i]->Free)(tms->pd[i]);
619 free((MEM_PTR)tms); /* free basic structure */
620 }
621
622 /******************** Shared but Private library routines *********************/
623
624 BYTE tmMesofact[BMESUPPER-BMESLOWER];
625
626 void
627 tmMkMesofact() /* build mesopic lookup factor table */
628 {
629 int i;
630
631 if (tmMesofact[BMESUPPER-BMESLOWER-1])
632 return;
633
634 for (i = BMESLOWER; i < BMESUPPER; i++)
635 tmMesofact[i-BMESLOWER] = 256. *
636 (tmLuminance(i) - LMESLOWER) /
637 (LMESUPPER - LMESLOWER);
638 }
639
640
641 int
642 tmErrorReturn( /* error return (with message) */
643 const char *func,
644 TMstruct *tms,
645 int err
646 )
647 {
648 if (tms != NULL) {
649 tms->lastFunc = func;
650 tms->lastError = err;
651 if (tms->flags & TM_F_NOSTDERR)
652 return(err);
653 }
654 fputs(func, stderr);
655 fputs(": ", stderr);
656 fputs(tmErrorMessage[err], stderr);
657 fputs("!\n", stderr);
658 return(err);
659 }