1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
2 * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
3 * http://www.gnu.org/software/gnugo/ for more information. *
4 * *
5 * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
6 * 2008 and 2009 by the Free Software Foundation. *
7 * *
8 * This program is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU General Public License as *
10 * published by the Free Software Foundation - version 3 or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License in file COPYING for more details. *
17 * *
18 * You should have received a copy of the GNU General Public *
19 * License along with this program; if not, write to the Free *
20 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
21 * Boston, MA 02111, USA. *
22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
23
24 #include <stdio.h>
25 #include <stdarg.h>
26 #include <assert.h>
27
28 #include "gg_utils.h"
29 #include "random.h"
30
31 #ifdef HAVE_GLIB_H
32 #include <glib.h>
33 #endif
34
35 /* Avoid compiler warnings with unused parameters */
36 #define UNUSED(x) (void)x
37
38 /* Define TERMINFO or ANSI_COLOR to enable coloring of pieces.
39 * This is normally done in config.h.
40 */
41
42 /* enabling color */
43
44 /* linux console :
45 * 0=black
46 * 1=red
47 * 2=green
48 * 3=yellow/brown
49 * 4=blue
50 * 5=magenta
51 * 6=cyan
52 * 7=white
53 */
54
55 #ifdef TERMINFO
56
57 #ifdef _AIX
58 #define _TPARM_COMPAT
59 #endif
60
61 #if HAVE_CURSES_H
62 #include <curses.h>
63 #elif HAVE_NCURSES_CURSES_H
64 #include <ncurses/curses.h>
65 #else
66 #endif
67
68 #if HAVE_TERM_H
69 #include <term.h>
70 #elif HAVE_NCURSES_TERM_H
71 #include <ncurses/term.h>
72 #else
73 #endif
74
75
76 /* terminfo attributes */
77 static char *setaf; /* terminfo string to set color */
78 static char *op; /* terminfo string to reset colors */
79
80 static int init = 0;
81
82 #endif /* TERMINFO */
83
84 /* for gg_cputime */
85
86 #ifdef HAVE_UNISTD_H
87 #include <unistd.h>
88 #endif
89 #ifdef HAVE_SYS_TIMES_H
90 #include <sys/times.h>
91 #elif defined(WIN32)
92 #include <windows.h>
93 #endif
94
95 void
gg_init_color()96 gg_init_color()
97 {
98 #ifdef TERMINFO
99
100 /* compiler is set to make string literals const char *
101 * But system header files dont prototype things correctly.
102 * These are equivalent to a non-const string literals
103 */
104
105 static char setaf_literal[] = "setaf";
106 static char op_literal[] = "op";
107 static char empty_literal[] = "";
108
109 if (init)
110 return;
111
112 init = 1;
113
114 setupterm(NULL, 2, NULL);
115 setaf = tigetstr(setaf_literal);
116 if (!setaf)
117 setaf = empty_literal;
118 op = tigetstr(op_literal);
119 if (!op)
120 op = empty_literal;
121
122 #endif /* TERMINFO */
123 }
124
125
126
127 #ifdef WIN32
128 #ifdef VC
129 #include <crtdbg.h>
130
verifyW32(BOOL b)131 verifyW32(BOOL b)
132 {
133 if (!b) {
134 _ASSERTE(0 && "Win32 Error");
135 fprintf(stderr, "Win32 Err: %ld\n", GetLastError());
136 }
137 }
138
139 #else
140 /* mingw32 lacks crtdbg.h and _ASSERTE */
verifyW32(BOOL b)141 verifyW32(BOOL b)
142 {
143 if (!b) {
144 fprintf(stderr, "Win32 Err: %ld\n", GetLastError());
145 }
146 }
147
148 #endif
149
150 #endif
151
152 void
write_color_char_no_space(int c,int x)153 write_color_char_no_space(int c, int x)
154 {
155 #ifdef TERMINFO
156
157 fprintf(stderr, "%s%c", tparm(setaf, c, 0, 0, 0, 0, 0, 0, 0, 0), x);
158 fputs(tparm(op, 0, 0, 0, 0, 0, 0, 0, 0, 0), stderr);
159
160 #elif defined(ANSI_COLOR)
161
162 fprintf(stderr, "\033[%dm%c\033[0m", 30+c, x);
163
164 #elif defined(WIN32)
165
166 static HANDLE hStdErr = 0;
167 DWORD iCharsWritten;
168 BOOL succeed32;
169 CONSOLE_SCREEN_BUFFER_INFO bufInfo;
170 if (!hStdErr) {
171 hStdErr = GetStdHandle(STD_ERROR_HANDLE);
172 if (hStdErr == INVALID_HANDLE_VALUE) {
173 fprintf(stderr, "Unable to open stderr.\n");
174 }
175 }
176
177 /* Red & Blue are switched from what MS-Windows wants:
178 * FOREGROUND_BLUE 0x0001 // text color contains blue.
179 * FOREGROUND_GREEN 0x0002 // text color contains green.
180 * FOREGROUND_RED 0x0004 // text color contains red
181 * This magic switches the bits back:
182 */
183 c = (c & 1) * 4 + (c & 2) + (c & 4) / 4;
184 c += FOREGROUND_INTENSITY;
185 succeed32 = GetConsoleScreenBufferInfo(hStdErr, &bufInfo);
186 if (!succeed32) { /* Probably redirecting output, just give plain text. */
187 fprintf(stderr, "%c", x);
188 return;
189 }
190 verifyW32(SetConsoleTextAttribute(hStdErr, (WORD) c));
191 verifyW32(WriteConsole(hStdErr, &x, 1, &iCharsWritten, 0));
192 verifyW32(SetConsoleTextAttribute(hStdErr, bufInfo.wAttributes));
193
194 #else
195
196 fprintf(stderr, "%c", x);
197
198 #endif
199 }
200
201 void
write_color_string(int c,const char * str)202 write_color_string(int c, const char *str)
203 {
204 while (*str)
205 write_color_char_no_space(c, *str++);
206 }
207
208 void
write_color_char(int c,int x)209 write_color_char(int c, int x)
210 {
211 fprintf(stderr, " ");
212 write_color_char_no_space(c, x);
213 }
214
215 /*
216 * A wrapper around vsnprintf.
217 */
218
219 void
gg_vsnprintf(char * dest,unsigned long len,const char * fmt,va_list args)220 gg_vsnprintf(char *dest, unsigned long len, const char *fmt, va_list args)
221 {
222
223 #ifdef HAVE_VSNPRINTF
224 vsnprintf(dest, len, fmt, args);
225 #elif HAVE_G_VSNPRINTF
226 g_vsnprintf(dest, len, fmt, args);
227 #elif HAVE__VSNPRINTF
228 _vsnprintf(dest, len, fmt, args);
229 #else
230 UNUSED(len);
231 vsprintf(dest, fmt, args);
232 #endif
233
234 }
235
236 void
gg_snprintf(char * dest,unsigned long len,const char * fmt,...)237 gg_snprintf(char *dest, unsigned long len, const char *fmt, ...)
238 {
239 va_list args;
240 va_start(args, fmt);
241 gg_vsnprintf(dest, len, fmt, args);
242 va_end(args);
243 }
244
245 /* Get the time of day, calling gettimeofday from sys/time.h
246 * if available, otherwise substituting a workaround for portability.
247 */
248
249 double
gg_gettimeofday(void)250 gg_gettimeofday(void)
251 {
252 struct timeval tv;
253 #ifdef HAVE_GETTIMEOFDAY
254 gettimeofday(&tv, NULL);
255 #else
256 tv.tv_sec = time(NULL);
257 tv.tv_usec = 0;
258 #endif
259 return tv.tv_sec + 1.e-6 * tv.tv_usec;
260 }
261
262 const char *
gg_version(void)263 gg_version(void)
264 {
265 return VERSION;
266 }
267
268 /* return cputime used in secs */
269
270 double
gg_cputime(void)271 gg_cputime(void)
272 {
273 #if HAVE_SYS_TIMES_H && HAVE_TIMES && HAVE_UNISTD_H
274 struct tms t;
275 times(&t);
276 return (t.tms_utime + t.tms_stime + t.tms_cutime + t.tms_cstime)
277 / ((double) sysconf(_SC_CLK_TCK));
278 #elif defined(WIN32)
279 FILETIME creationTime, exitTime, kernelTime, userTime;
280 ULARGE_INTEGER uKernelTime, uUserTime, uElapsedTime;
281 GetProcessTimes(GetCurrentProcess(), &creationTime, &exitTime,
282 &kernelTime, &userTime);
283 uKernelTime.LowPart = kernelTime.dwLowDateTime;
284 uKernelTime.HighPart = kernelTime.dwHighDateTime;
285 uUserTime.LowPart = userTime.dwLowDateTime;
286 uUserTime.HighPart = userTime.dwHighDateTime;
287 uElapsedTime.QuadPart = uKernelTime.QuadPart + uUserTime.QuadPart;
288 /*_ASSERTE(0 && "Debug Times");*/
289 /* convert from multiples of 100nanosecs to seconds: */
290 return (signed __int64)(uElapsedTime.QuadPart) * 1.e-7;
291 #else
292 static int warned = 0;
293 if (!warned) {
294 fprintf(stderr, "CPU timing unavailable - returning wall time.");
295 warned = 1;
296 }
297 /* return wall clock seconds */
298 return gg_gettimeofday();
299 #endif
300 }
301
302 /* Before we sort floating point values (or just compare them) we
303 * may need to normalize them. This may sound cryptic but is
304 * required to avoid an obscure platform dependency.
305 *
306 * The underlying problem is that most fractional decimal numbers
307 * can't be represented exactly in a floating point number with base
308 * two. The error may be small but it is there. When such numbers
309 * are added or subtracted, the errors accumulate and even if the
310 * result (counting exactly) should be a number which can be
311 * represented exactly, this cannot be assumed to be the case.
312 *
313 * To give an example of this, the computation 0.3 + 0.05 - 0.35 may
314 * sum to 0, a small negative value, or a small positive value.
315 * Moreover, which case we encounter depends on the number of
316 * mantissa bits in the floating point type used and the exact
317 * details of the floating point arithmetic on the platform.
318 *
319 * In the context of sorting, assume that two values both should be
320 * 0.35, but one has been computed as 0.3 + 0.05 and the other
321 * directly assigned 0.35. Then it depends on the platform whether
322 * they compare as equal or one of them is larger than the other.
323 *
324 * This code normalizes the values to avoid this problem. It is
325 * assumed that all values encountered are integer multiples of a.
326 */
327 float
gg_normalize_float(float x,float a)328 gg_normalize_float(float x, float a)
329 {
330 return a * ((int) (0.5 + x / a));
331 }
332
333 int
gg_normalize_float2int(float x,float a)334 gg_normalize_float2int(float x, float a)
335 {
336 return ((int) (0.5 + x / a));
337 }
338
339 /* A sorting algorithm, call-compatible with the libc qsort() function.
340 *
341 * The reason to prefer this to standard qsort() is that quicksort is
342 * an unstable sorting algorithm, i.e. the relative ordering of
343 * elements with the same comparison value may change. Exactly how the
344 * ordering changes depends on implementation specific details like
345 * the strategy for choosing the pivot element. Thus a list with
346 * "equal" values may be sorted differently between platforms, which
347 * potentially can lead to significant differences in the move
348 * generation.
349 *
350 * This is an implementation of the combsort algorithm.
351 *
352 * Testing shows that it is faster than the GNU libc qsort() function
353 * on small data sets and within a factor of two slower for large
354 * random data sets. Its performance does not degenerate for common
355 * special cases (i.e. sorted or reversed data) but it seems to be
356 * susceptible to O(N^2) behavior for repetitive data with specific
357 * cycle lengths.
358 *
359 * Like qsort() this algorithm is unstable, but since the same
360 * implementation (this one) is used on all platforms, the reordering
361 * of equal elements will be consistent.
362 */
363 void
gg_sort(void * base,size_t nel,size_t width,int (* cmp)(const void *,const void *))364 gg_sort(void *base, size_t nel, size_t width,
365 int (*cmp)(const void *, const void *))
366 {
367 int gap = nel;
368 int swap_made;
369 char *end = (char *) base + width * (nel - 1);
370 do {
371 char *a, *b;
372 swap_made = 0;
373 gap = (10 * gap + 3) / 13;
374 for (a = base, b = a + gap * width; b <= end; a += width, b += width) {
375 if (cmp((void *) a, (void *) b) > 0) {
376 char *c = a;
377 char *d = b;
378 size_t size = width;
379 while (size-- > 0) {
380 char tmp = *c;
381 *c++ = *d;
382 *d++ = tmp;
383 }
384 swap_made = 1;
385 }
386 }
387 } while (gap > 1 || swap_made);
388 }
389
390
391 /* Linearly interpolate f(x) from the data given in interpolation_data. */
392 float
gg_interpolate(struct interpolation_data * f,float x)393 gg_interpolate(struct interpolation_data *f, float x)
394 {
395 int i;
396 float ratio;
397 float diff;
398 if (x < f->range_lowerbound)
399 return f->values[0];
400 else if (x > f->range_upperbound)
401 return f->values[f->sections];
402 else {
403 ratio = ((float) f->sections) * (x - f->range_lowerbound)
404 / (f->range_upperbound - f->range_lowerbound);
405 i = (int) ratio;
406 diff = ratio - ((float) i);
407 if (0)
408 fprintf(stderr, "Floating point Ratio: %f, integer: %d, diff %f",
409 ratio, i, diff);
410 return ((1 - diff) * f->values[i] + diff * f->values[i+1]);
411 }
412 }
413
414
415 /* This is the simplest function that returns appr. a when a is small,
416 * and approximately b when a is large.
417 */
418 float
soft_cap(float a,float b)419 soft_cap(float a, float b)
420 {
421 return ((a * b) / (a + b));
422 }
423
424
425 /* Reorientation of point (i, j) into (*ri, *rj) */
426 void
rotate(int i,int j,int * ri,int * rj,int bs,int rot)427 rotate(int i, int j, int *ri, int *rj, int bs, int rot)
428 {
429 int bs1;
430 assert(bs > 0);
431 assert(ri != NULL && rj != NULL);
432 assert(rot >= 0 && rot < 8);
433 /* PASS case */
434 if (i == -1 && j == -1) {
435 *ri = i;
436 *rj = j;
437 return;
438 }
439
440 assert(i >= 0 && i < bs);
441 assert(j >= 0 && j < bs);
442
443 bs1 = bs - 1;
444 if (rot == 0) {
445 /* identity map */
446 *ri = i;
447 *rj = j;
448 }
449 else if (rot == 1) {
450 /* rotation over 90 degrees */
451 *ri = bs1 - j;
452 *rj = i;
453 }
454 else if (rot == 2) {
455 /* rotation over 180 degrees */
456 *ri = bs1 - i;
457 *rj = bs1 - j;
458 }
459 else if (rot == 3) {
460 /* rotation over 270 degrees */
461 *ri = j;
462 *rj = bs1 - i;
463 }
464 else if (rot == 4) {
465 /* flip along diagonal */
466 *ri = j;
467 *rj = i;
468 }
469 else if (rot == 5) {
470 /* flip */
471 *ri = bs1 - i;
472 *rj = j;
473 }
474 else if (rot == 6) {
475 /* flip along diagonal */
476 *ri = bs1 - j;
477 *rj = bs1 - i;
478 }
479 else if (rot == 7) {
480 /* flip */
481 *ri = i;
482 *rj = bs1 - j;
483 }
484 }
485
486 /* inverse reorientation of reorientation rot */
487 void
inv_rotate(int i,int j,int * ri,int * rj,int bs,int rot)488 inv_rotate(int i, int j, int *ri, int *rj, int bs, int rot)
489 {
490 /* every reorientation is it's own inverse except rotations
491 over 90 and 270 degrees */
492 if (rot == 1)
493 rotate(i, j, ri, rj, bs, 3);
494 else if (rot == 3)
495 rotate(i, j, ri, rj, bs, 1);
496 else
497 rotate(i, j, ri, rj, bs, rot);
498 }
499
500
501 /* Intermediate layer to random.c. gg_srand() should only be called via the
502 * functions below.
503 */
504
505 /* Private variable remembering the random seed. */
506 static unsigned int random_seed;
507
508 unsigned int
get_random_seed()509 get_random_seed()
510 {
511 return random_seed;
512 }
513
514 void
set_random_seed(unsigned int seed)515 set_random_seed(unsigned int seed)
516 {
517 random_seed = seed;
518 gg_srand(seed);
519 }
520
521 /* Update the random seed. This should be called at the start of each
522 * new game.
523 * We reset the random seed before obtaining a new one, to make the
524 * next random seed depend deterministically on the old one.
525 */
526 void
update_random_seed(void)527 update_random_seed(void)
528 {
529 gg_srand(random_seed);
530 random_seed = gg_rand();
531 /* Since random seed 0 has a special interpretation when given as
532 * command line argument with the -r option, we make sure to avoid
533 * it.
534 */
535 if (random_seed == 0)
536 random_seed = 1;
537 gg_srand(random_seed);
538 }
539
540
541 /* Restart the pseudo-random sequence with the initialization given
542 * by the random seed. Should be called at each move.
543 */
544 void
reuse_random_seed()545 reuse_random_seed()
546 {
547 gg_srand(random_seed);
548 }
549
550
551
552 /*
553 * Local Variables:
554 * tab-width: 8
555 * c-basic-offset: 2
556 * End:
557 */
558