pattern.c

   1 #define DEBUG
   2 #include <assert.h>
   3 #include <ctype.h>
   4 #include <inttypes.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "pattern.h"
  11 #include "patternsp.h"
  12 #include "patternprob.h"
  13 #include "tactics/ladder.h"
  14 #include "tactics/selfatari.h"
  15 #include "tactics/util.h"
  16
  17 #define CAPTURE_COUNTSTONES_MAX ((1 << CAPTURE_COUNTSTONES_PAYLOAD_SIZE) - 1)
  18
  19
  20 struct pattern_config DEFAULT_PATTERN_CONFIG = {
  21         .bdist_max = 4,
  22
  23         .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
  24         .spat_largest = true,
  25 };
  26
  27 #define PF_MATCH 15
  28
  29 pattern_spec PATTERN_SPEC_MATCH_DEFAULT = {
  30         [FEAT_CAPTURE] = ~0,
  31         [FEAT_AESCAPE] = ~0,
  32         [FEAT_SELFATARI] = ~0,
  33         [FEAT_ATARI] = ~0,
  34         [FEAT_BORDER] = ~0,
  35         [FEAT_CONTIGUITY] = 0,
  36         [FEAT_SPATIAL] = ~0,
  37 };
  38
  39 static const struct feature_info {
  40         char *name;
  41         int payloads;
  42 } features[FEAT_MAX] = {
  43         [FEAT_CAPTURE] = { .name = "capture", .payloads = 64 },
  44         [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 16 },
  45         [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 4 },
  46         [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
  47         [FEAT_BORDER] = { .name = "border", .payloads = -1 },
  48         [FEAT_CONTIGUITY] = { .name = "cont", .payloads = 2 },
  49         [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
  50 };
  51
  52 char *
  53 feature2str(char *str, struct feature *f)
  54 {
  55         return str + sprintf(str + strlen(str), "%s:%d", features[f->id].name, f->payload);
  56 }
  57
  58 char *
  59 str2feature(char *str, struct feature *f)
  60 {
  61         while (isspace(*str)) str++;
  62
  63         int unsigned flen = strcspn(str, ":");
  64         for (unsigned int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
  65                 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
  66                         f->id = i;
  67                         goto found;
  68                 }
  69         fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
  70         exit(EXIT_FAILURE);
  71
  72 found:
  73         str += flen + 1;
  74         f->payload = strtoull(str, &str, 10);
  75         return str;
  76 }
  77
  78 char *
  79 feature_name(enum feature_id f)
  80 {
  81         return features[f].name;
  82 }
  83
  84 int
  85 feature_payloads(struct pattern_setup *pat, enum feature_id f)
  86 {
  87         switch (f) {
  88                 int payloads;
  89                 case FEAT_CAPTURE:
  90                         payloads = features[f].payloads;
  91                         if (pat->ps[FEAT_CAPTURE] & (1<<PF_CAPTURE_COUNTSTONES))
  92                                 payloads *= CAPTURE_COUNTSTONES_MAX + 1;
  93                         return payloads;
  94                 case FEAT_SPATIAL:
  95                         assert(features[f].payloads < 0);
  96                         return pat->pc.spat_dict->nspatials;
  97                 case FEAT_BORDER:
  98                         assert(features[f].payloads < 0);
  99                         return pat->pc.bdist_max + 1;
 100                 default:
 101                         assert(features[f].payloads > 0);
 102                         return features[f].payloads;
 103         }
 104 }
 105
 106
 107 void
 108 patterns_init(struct pattern_setup *pat, char *arg, bool will_append, bool load_prob)
 109 {
 110         char *pdict_file = NULL;
 111
 112         memset(pat, 0, sizeof(*pat));
 113
 114         pat->pc = DEFAULT_PATTERN_CONFIG;
 115         pat->pc.spat_dict = spatial_dict_init(will_append, !load_prob);
 116
 117         memcpy(&pat->ps, PATTERN_SPEC_MATCH_DEFAULT, sizeof(pattern_spec));
 118
 119         if (arg) {
 120                 char *optspec, *next = arg;
 121                 while (*next) {
 122                         optspec = next;
 123                         next += strcspn(next, ":");
 124                         if (*next) { *next++ = 0; } else { *next = 0; }
 125
 126                         char *optname = optspec;
 127                         char *optval = strchr(optspec, '=');
 128                         if (optval) *optval++ = 0;
 129
 130                         /* See pattern.h:pattern_config for description and
 131                          * pattern.c:DEFAULT_PATTERN_CONFIG for default values
 132                          * of the following options. */
 133                         if (!strcasecmp(optname, "bdist_max") && optval) {
 134                                 pat->pc.bdist_max = atoi(optval);
 135                         } else if (!strcasecmp(optname, "spat_min") && optval) {
 136                                 pat->pc.spat_min = atoi(optval);
 137                         } else if (!strcasecmp(optname, "spat_max") && optval) {
 138                                 pat->pc.spat_max = atoi(optval);
 139                         } else if (!strcasecmp(optname, "spat_largest")) {
 140                                 pat->pc.spat_largest = !optval || atoi(optval);
 141
 142                         } else if (!strcasecmp(optname, "pdict_file") && optval) {
 143                                 pdict_file = optval;
 144
 145                         } else {
 146                                 fprintf(stderr, "patterns: Invalid argument %s or missing value\n", optname);
 147                                 exit(EXIT_FAILURE);
 148                         }
 149                 }
 150         }
 151
 152         if (load_prob && pat->pc.spat_dict) {
 153                 pat->pd = pattern_pdict_init(pdict_file, &pat->pc);
 154         }
 155 }
 156
 157
 158 /* pattern_spec helpers */
 159 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
 160 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
 161
 162 static struct feature *
 163 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
 164                       struct pattern *p, struct feature *f,
 165                       struct board *b, struct move *m)
 166 {
 167         f->id = FEAT_CAPTURE; f->payload = 0;
 168 #ifdef BOARD_TRAITS
 169         if (!trait_at(b, m->coord, m->color).cap)
 170                 return f;
 171         /* Capturable! */
 172         if ((ps[FEAT_CAPTURE] & ~(1<<PF_CAPTURE_1STONE | 1<<PF_CAPTURE_TRAPPED | 1<<PF_CAPTURE_CONNECTION)) == 1<<PF_MATCH) {
 173                 if (PS_PF(CAPTURE, 1STONE))
 174                         f->payload |= (trait_at(b, m->coord, m->color).cap1 == trait_at(b, m->coord, m->color).cap) << PF_CAPTURE_1STONE;
 175                 if (PS_PF(CAPTURE, TRAPPED))
 176                         f->payload |= (!trait_at(b, m->coord, stone_other(m->color)).safe) << PF_CAPTURE_TRAPPED;
 177                 if (PS_PF(CAPTURE, CONNECTION))
 178                         f->payload |= (trait_at(b, m->coord, m->color).cap < neighbor_count_at(b, m->coord, stone_other(m->color))) << PF_CAPTURE_CONNECTION;
 179                 (f++, p->n++);
 180                 return f;
 181         }
 182         /* We need to know details, so we still have to go through
 183          * the neighbors. */
 184 #endif
 185
 186         /* We look at neighboring groups we could capture, and also if the
 187          * opponent could save them. */
 188         /* This is very similar in spirit to board_safe_to_play(), and almost
 189          * a color inverse of pattern_match_aescape(). */
 190
 191         /* Whether an escape move would be safe for the opponent. */
 192         int captures = 0;
 193         coord_t onelib = -1;
 194         int extra_libs = 0, connectable_groups = 0;
 195         bool onestone = false, multistone = false;
 196         int captured_stones = 0;
 197
 198         foreach_neighbor(b, m->coord, {
 199                 if (board_at(b, c) != stone_other(m->color)) {
 200                         if (board_at(b, c) == S_NONE)
 201                                 extra_libs++; // free point
 202                         else if (board_at(b, c) == m->color && board_group_info(b, group_at(b, c)).libs == 1)
 203                                 extra_libs += 2; // capturable enemy group
 204                         continue;
 205                 }
 206
 207                 group_t g = group_at(b, c); assert(g);
 208                 if (board_group_info(b, g).libs > 1) {
 209                         connectable_groups++;
 210                         if (board_group_info(b, g).libs > 2) {
 211                                 extra_libs += 2; // connected out
 212                         } else {
 213                                 /* This is a bit tricky; we connect our 2-lib
 214                                  * group to another 2-lib group, which counts
 215                                  * as one liberty, but only if the other lib
 216                                  * is not shared too. */
 217                                 if (onelib == -1) {
 218                                         onelib = board_group_other_lib(b, g, c);
 219                                         extra_libs++;
 220                                 } else {
 221                                         if (c == onelib)
 222                                                 extra_libs--; // take that back
 223                                         else
 224                                                 extra_libs++;
 225                                 }
 226                         }
 227                         continue;
 228                 }
 229
 230                 /* Capture! */
 231                 captures++;
 232
 233                 if (PS_PF(CAPTURE, LADDER))
 234                         f->payload |= is_ladder(b, m->coord, g, true) << PF_CAPTURE_LADDER;
 235                 /* TODO: is_ladder() is too conservative in some
 236                  * very obvious situations, look at complete.gtp. */
 237
 238                 if (PS_PF(CAPTURE, ATARIDEF))
 239                 foreach_in_group(b, g) {
 240                         foreach_neighbor(b, c, {
 241                                 assert(board_at(b, c) != S_NONE || c == m->coord);
 242                                 if (board_at(b, c) != m->color)
 243                                         continue;
 244                                 group_t g = group_at(b, c);
 245                                 if (!g || board_group_info(b, g).libs != 1)
 246                                         continue;
 247                                 /* A neighboring group of ours is in atari. */
 248                                 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
 249                         });
 250                 } foreach_in_group_end;
 251
 252                 if (PS_PF(CAPTURE, KO)
 253                     && group_is_onestone(b, g)
 254                     && neighbor_count_at(b, m->coord, stone_other(m->color))
 255                        + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
 256                         f->payload |= 1 << PF_CAPTURE_KO;
 257
 258                 if (PS_PF(CAPTURE, COUNTSTONES)
 259                     && captured_stones < CAPTURE_COUNTSTONES_MAX)
 260                         captured_stones += group_stone_count(b, g, CAPTURE_COUNTSTONES_MAX - captured_stones);
 261
 262                 if (group_is_onestone(b, g))
 263                         onestone = true;
 264                 else
 265                         multistone = true;
 266         });
 267
 268         if (captures > 0) {
 269                 if (PS_PF(CAPTURE, 1STONE))
 270                         f->payload |= (onestone && !multistone) << PF_CAPTURE_1STONE;
 271                 if (PS_PF(CAPTURE, TRAPPED))
 272                         f->payload |= (extra_libs < 2) << PF_CAPTURE_TRAPPED;
 273                 if (PS_PF(CAPTURE, CONNECTION))
 274                         f->payload |= (connectable_groups > 0) << PF_CAPTURE_CONNECTION;
 275                 if (PS_PF(CAPTURE, COUNTSTONES))
 276                         f->payload |= captured_stones << PF_CAPTURE_COUNTSTONES;
 277                 (f++, p->n++);
 278         }
 279         return f;
 280 }
 281
 282 static struct feature *
 283 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
 284                       struct pattern *p, struct feature *f,
 285                       struct board *b, struct move *m)
 286 {
 287         f->id = FEAT_AESCAPE; f->payload = 0;
 288 #ifdef BOARD_TRAITS
 289         if (!trait_at(b, m->coord, stone_other(m->color)).cap)
 290                 return f;
 291         /* Opponent can capture something! */
 292         if ((ps[FEAT_AESCAPE] & ~(1<<PF_AESCAPE_1STONE | 1<<PF_AESCAPE_TRAPPED | 1<<PF_AESCAPE_CONNECTION)) == 1<<PF_MATCH) {
 293                 if (PS_PF(AESCAPE, 1STONE))
 294                         f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap1 == trait_at(b, m->coord, stone_other(m->color)).cap) << PF_AESCAPE_1STONE;
 295                 if (PS_PF(AESCAPE, TRAPPED))
 296                         f->payload |= (!trait_at(b, m->coord, m->color).safe) << PF_AESCAPE_TRAPPED;
 297                 if (PS_PF(AESCAPE, CONNECTION))
 298                         f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap < neighbor_count_at(b, m->coord, m->color)) << PF_AESCAPE_CONNECTION;
 299                 (f++, p->n++);
 300                 return f;
 301         }
 302         /* We need to know details, so we still have to go through
 303          * the neighbors. */
 304 #endif
 305
 306         /* Find if a neighboring group of ours is in atari, AND that we provide
 307          * a liberty to connect out. XXX: No connect-and-die check. */
 308         /* This is very similar in spirit to board_safe_to_play(). */
 309         group_t in_atari = -1;
 310         coord_t onelib = -1;
 311         int extra_libs = 0, connectable_groups = 0;
 312         bool onestone = false, multistone = false;
 313
 314         foreach_neighbor(b, m->coord, {
 315                 if (board_at(b, c) != m->color) {
 316                         if (board_at(b, c) == S_NONE)
 317                                 extra_libs++; // free point
 318                         else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1) {
 319                                 extra_libs += 2; // capturable enemy group
 320                                 /* XXX: We just consider this move safe
 321                                  * unconditionally. */
 322                         }
 323                         continue;
 324                 }
 325                 group_t g = group_at(b, c); assert(g);
 326                 if (board_group_info(b, g).libs > 1) {
 327                         connectable_groups++;
 328                         if (board_group_info(b, g).libs > 2) {
 329                                 extra_libs += 2; // connected out
 330                         } else {
 331                                 /* This is a bit tricky; we connect our 2-lib
 332                                  * group to another 2-lib group, which counts
 333                                  * as one liberty, but only if the other lib
 334                                  * is not shared too. */
 335                                 if (onelib == -1) {
 336                                         onelib = board_group_other_lib(b, g, c);
 337                                         extra_libs++;
 338                                 } else {
 339                                         if (c == onelib)
 340                                                 extra_libs--; // take that back
 341                                         else
 342                                                 extra_libs++;
 343                                 }
 344                         }
 345                         continue;
 346                 }
 347
 348                 /* In atari! */
 349                 in_atari = g;
 350
 351                 if (PS_PF(AESCAPE, LADDER))
 352                         f->payload |= is_ladder(b, m->coord, g, true) << PF_AESCAPE_LADDER;
 353                 /* TODO: is_ladder() is too conservative in some
 354                  * very obvious situations, look at complete.gtp. */
 355
 356                 if (group_is_onestone(b, g))
 357                         onestone = true;
 358                 else
 359                         multistone = true;
 360         });
 361
 362         if (in_atari >= 0) {
 363                 if (PS_PF(AESCAPE, 1STONE))
 364                         f->payload |= (onestone && !multistone) << PF_AESCAPE_1STONE;
 365                 if (PS_PF(AESCAPE, TRAPPED))
 366                         f->payload |= (extra_libs < 2) << PF_AESCAPE_TRAPPED;
 367                 if (PS_PF(AESCAPE, CONNECTION))
 368                         f->payload |= (connectable_groups > 0) << PF_AESCAPE_CONNECTION;
 369                 (f++, p->n++);
 370         }
 371         return f;
 372 }
 373
 374 static struct feature *
 375 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
 376                     struct pattern *p, struct feature *f,
 377                     struct board *b, struct move *m)
 378 {
 379         foreach_neighbor(b, m->coord, {
 380                 if (board_at(b, c) != stone_other(m->color))
 381                         continue;
 382                 group_t g = group_at(b, c);
 383                 if (!g || board_group_info(b, g).libs != 2)
 384                         continue;
 385
 386                 /* Can atari! */
 387                 f->id = FEAT_ATARI; f->payload = 0;
 388
 389                 if (PS_PF(ATARI, LADDER)) {
 390                         /* Opponent will escape by the other lib. */
 391                         coord_t lib = board_group_other_lib(b, g, m->coord);
 392                         /* TODO: is_ladder() is too conservative in some
 393                          * very obvious situations, look at complete.gtp. */
 394                         f->payload |= wouldbe_ladder(b, g, lib, m->coord, stone_other(m->color)) << PF_ATARI_LADDER;
 395                 }
 396
 397                 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
 398                         f->payload |= 1 << PF_ATARI_KO;
 399
 400                 (f++, p->n++);
 401         });
 402         return f;
 403 }
 404
 405 #ifndef BOARD_SPATHASH
 406 #undef BOARD_SPATHASH_MAXD
 407 #define BOARD_SPATHASH_MAXD 1
 408 #endif
 409
 410 /* Match spatial features that are too distant to be pre-matched
 411  * incrementally. */
 412 struct feature *
 413 pattern_match_spatial_outer(struct pattern_config *pc, pattern_spec ps,
 414                             struct pattern *p, struct feature *f,
 415                             struct board *b, struct move *m, hash_t h)
 416 {
 417         /* We record all spatial patterns black-to-play; simply
 418          * reverse all colors if we are white-to-play. */
 419         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 420         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 421         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 422
 423         for (unsigned int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
 424                 /* Recompute missing outer circles:
 425                  * Go through all points in given distance. */
 426                 for (unsigned int j = ptind[d]; j < ptind[d + 1]; j++) {
 427                         ptcoords_at(x, y, m->coord, b, j);
 428                         h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
 429                 }
 430                 if (d < pc->spat_min)
 431                         continue;
 432                 /* Record spatial feature, one per distance. */
 433                 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 434                 if (sid > 0) {
 435                         f->id = FEAT_SPATIAL;
 436                         f->payload = sid;
 437                         if (!pc->spat_largest)
 438                                 (f++, p->n++);
 439                 } /* else not found, ignore */
 440         }
 441         return f;
 442 }
 443
 444 struct feature *
 445 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
 446                       struct pattern *p, struct feature *f,
 447                       struct board *b, struct move *m)
 448 {
 449         /* XXX: This is partially duplicated from spatial_from_board(), but
 450          * we build a hash instead of spatial record. */
 451
 452         assert(pc->spat_min > 0);
 453         f->id = -1;
 454
 455         hash_t h = pthashes[0][0][S_NONE];
 456 #ifdef BOARD_SPATHASH
 457         bool w_to_play = m->color == S_WHITE;
 458         for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
 459                 /* Reuse all incrementally matched data. */
 460                 h ^= b->spathash[m->coord][d - 1][w_to_play];
 461                 if (d < pc->spat_min)
 462                         continue;
 463                 /* Record spatial feature, one per distance. */
 464                 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 465                 if (sid > 0) {
 466                         f->id = FEAT_SPATIAL;
 467                         f->payload = sid;
 468                         if (!pc->spat_largest)
 469                                 (f++, p->n++);
 470                 } /* else not found, ignore */
 471         }
 472 #else
 473         assert(BOARD_SPATHASH_MAXD < 2);
 474 #endif
 475         if (unlikely(pc->spat_max > BOARD_SPATHASH_MAXD))
 476                 f = pattern_match_spatial_outer(pc, ps, p, f, b, m, h);
 477         if (pc->spat_largest && f->id == FEAT_SPATIAL)
 478                 (f++, p->n++);
 479         return f;
 480 }
 481
 482
 483 void
 484 pattern_match(struct pattern_config *pc, pattern_spec ps,
 485               struct pattern *p, struct board *b, struct move *m)
 486 {
 487         p->n = 0;
 488         struct feature *f = &p->f[0];
 489
 490         /* TODO: We should match pretty much all of these features
 491          * incrementally. */
 492
 493         if (PS_ANY(CAPTURE)) {
 494                 f = pattern_match_capture(pc, ps, p, f, b, m);
 495         }
 496
 497         if (PS_ANY(AESCAPE)) {
 498                 f = pattern_match_aescape(pc, ps, p, f, b, m);
 499         }
 500
 501         if (PS_ANY(SELFATARI)) {
 502                 bool simple = false;
 503                 if (PS_PF(SELFATARI, STUPID)) {
 504 #ifdef BOARD_TRAITS
 505                         if (!b->precise_selfatari)
 506                                 simple = !trait_at(b, m->coord, m->color).safe;
 507                         else
 508 #endif
 509                         simple = !board_safe_to_play(b, m->coord, m->color);
 510                 }
 511                 bool thorough = false;
 512                 if (PS_PF(SELFATARI, SMART)) {
 513 #ifdef BOARD_TRAITS
 514                         if (b->precise_selfatari)
 515                                 thorough = !trait_at(b, m->coord, m->color).safe;
 516                         else
 517 #endif
 518                         thorough = is_bad_selfatari(b, m->color, m->coord);
 519                 }
 520                 if (simple || thorough) {
 521                         f->id = FEAT_SELFATARI;
 522                         f->payload = simple << PF_SELFATARI_STUPID;
 523                         f->payload |= thorough << PF_SELFATARI_SMART;
 524                         (f++, p->n++);
 525                 }
 526         }
 527
 528         if (PS_ANY(ATARI)) {
 529                 f = pattern_match_atari(pc, ps, p, f, b, m);
 530         }
 531
 532         if (PS_ANY(BORDER)) {
 533                 unsigned int bdist = coord_edge_distance(m->coord, b);
 534                 if (bdist <= pc->bdist_max) {
 535                         f->id = FEAT_BORDER;
 536                         f->payload = bdist;
 537                         (f++, p->n++);
 538                 }
 539         }
 540
 541         if (PS_ANY(CONTIGUITY) && !is_pass(b->last_move.coord)
 542             && coord_is_8adjecent(m->coord, b->last_move.coord, b)) {
 543                 f->id = FEAT_CONTIGUITY;
 544                 f->payload = 1;
 545                 (f++, p->n++);
 546         }
 547
 548         if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
 549                 f = pattern_match_spatial(pc, ps, p, f, b, m);
 550         }
 551 }
 552
 553 char *
 554 pattern2str(char *str, struct pattern *p)
 555 {
 556         str = stpcpy(str, "(");
 557         for (int i = 0; i < p->n; i++) {
 558                 if (i > 0) str = stpcpy(str, " ");
 559                 str = feature2str(str, &p->f[i]);
 560         }
 561         str = stpcpy(str, ")");
 562         return str;
 563 }
 564
 565 char *
 566 str2pattern(char *str, struct pattern *p)
 567 {
 568         p->n = 0;
 569         while (isspace(*str)) str++;
 570         if (*str++ != '(') {
 571                 fprintf(stderr, "invalid patternspec: %s\n", str);
 572                 exit(EXIT_FAILURE);
 573         }
 574
 575         while (*str != ')') {
 576                 str = str2feature(str, &p->f[p->n++]);
 577         }
 578
 579         str++;
 580         return str;
 581 }