Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 | |
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 | ||
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 */ | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 * | |
263 | gg_version(void) | |
264 | { | |
265 | return VERSION; | |
266 | } | |
267 | ||
268 | /* return cputime used in secs */ | |
269 | ||
270 | double | |
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 | |
328 | gg_normalize_float(float x, float a) | |
329 | { | |
330 | return a * ((int) (0.5 + x / a)); | |
331 | } | |
332 | ||
333 | int | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
509 | get_random_seed() | |
510 | { | |
511 | return random_seed; | |
512 | } | |
513 | ||
514 | void | |
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 | |
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 | |
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 | */ |