nsz Git - libfirm/blob - ir/lpp/lpp.c

   1 /*
   2  * Copyright (C) 2005-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @author  Daniel Grund
  23  */
  24 #include "config.h"
  25
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include <string.h>
  29
  30 #include "assert.h"
  31 #include "obst.h"
  32 #include "hashptr.h"
  33 #include "debug.h"
  34 #include "set.h"
  35
  36 #include "sp_matrix.h"
  37 #include "mps.h"
  38 #include "lpp_t.h"
  39 #include "lpp_comm.h"
  40 #include "lpp_solvers.h"
  41 #include "lpp_net.h"
  42
  43 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
  44
  45 static firm_dbg_module_t *dbg = NULL;
  46
  47 static inline char *obst_xstrdup(struct obstack *obst, const char *str)
  48 {
  49         return obstack_copy0(obst, str, strlen(str));
  50 }
  51
  52 static int cmp_name_t(const void *x, const void *y, size_t size)
  53 {
  54         const lpp_name_t *n = x;
  55         const lpp_name_t *m = y;
  56         (void)size;
  57         return strcmp(n->name, m->name);
  58 }
  59
  60 /**
  61  * Update statistic information about matrix usage.
  62  */
  63 static void update_stats(lpp_t *lpp)
  64 {
  65         lpp->n_elems    = matrix_get_entries(lpp->m);
  66         lpp->matrix_mem = lpp->n_elems * matrix_get_elem_size();
  67         lpp->density    = (double)lpp->n_elems / (double)(lpp->cst_next * lpp->var_next) * 100.0;
  68 }
  69
  70 lpp_t *new_lpp(const char *name, lpp_opt_t opt_type)
  71 {
  72         return new_lpp_userdef(name, opt_type, 64, 64, 2.0);
  73 }
  74
  75 lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type,
  76                            int estimated_vars, int estimated_csts, double grow_factor)
  77 {
  78         lpp_t *lpp;
  79         int   idx;
  80
  81         dbg = firm_dbg_register("lpp");
  82         lpp = XMALLOCZ(lpp_t);
  83         obstack_init(&lpp->obst);
  84
  85         lpp->name        = obst_xstrdup(&lpp->obst, name);
  86         lpp->opt_type    = opt_type;
  87         lpp->grow_factor = grow_factor;
  88         lpp->cst2nr      = new_set(cmp_name_t, estimated_csts);
  89         lpp->var2nr      = new_set(cmp_name_t, estimated_vars);
  90         lpp->cst_size    = estimated_csts;
  91         lpp->var_size    = estimated_vars;
  92         lpp->csts        = XMALLOCNZ(lpp_name_t *, estimated_csts);
  93         lpp->vars        = XMALLOCNZ(lpp_name_t *, estimated_vars);
  94         lpp->m           = new_matrix(estimated_csts, estimated_vars);
  95         lpp->emphasis    = lpp_balanced;
  96         idx              = lpp_add_cst(lpp, "obj", lpp_objective, 0);
  97         assert(idx == 0);
  98         idx              = lpp_add_var(lpp, "rhs", lpp_rhs, 0);
  99         assert(idx == 0);
 100
 101         return lpp;
 102 }
 103
 104 void free_lpp_matrix(lpp_t *lpp)
 105 {
 106         del_matrix(lpp->m);
 107         lpp->m = NULL;
 108 }
 109
 110 void free_lpp(lpp_t *lpp)
 111 {
 112         obstack_free(&lpp->obst, NULL);
 113
 114         del_set(lpp->cst2nr);
 115         del_set(lpp->var2nr);
 116
 117         /* matrix might have been already deleted */
 118         if (lpp->m)
 119                 del_matrix(lpp->m);
 120
 121         free(lpp->csts);
 122         free(lpp->vars);
 123
 124         free(lpp);
 125 }
 126
 127 double lpp_get_fix_costs(lpp_t *lpp)
 128 {
 129         return matrix_get(lpp->m, 0, 0);
 130 }
 131
 132 void lpp_set_fix_costs(lpp_t *lpp, double value)
 133 {
 134         matrix_set(lpp->m, 0, 0, value);
 135 }
 136
 137 static int name2nr(set *where, const char *name)
 138 {
 139         lpp_name_t find, *found;
 140         find.name = name;
 141         found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
 142         return (found ? found->nr : -1);
 143 }
 144
 145 static int cst_nr(const lpp_t *lpp, const char *name)
 146 {
 147         return name2nr(lpp->cst2nr, name);
 148 }
 149
 150 static int var_nr(const lpp_t *lpp, const char *name)
 151 {
 152         return name2nr(lpp->var2nr, name);
 153 }
 154
 155 static inline char *get_next_name(lpp_t *lpp)
 156 {
 157         char *res = obstack_alloc(&lpp->obst, 12);
 158         snprintf(res, 12, "_%u", lpp->next_name_number++);
 159         return res;
 160 }
 161
 162 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
 163 {
 164         lpp_name_t n, *inner;
 165
 166         DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
 167
 168         if (cst_name && cst_name[0] == '_')
 169                 return ERR_NAME_NOT_ALLOWED;
 170
 171         if (cst_name)
 172                 n.name = obst_xstrdup(&lpp->obst, cst_name);
 173         else
 174                 n.name = get_next_name(lpp);
 175
 176         n.nr  = -1;
 177         inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
 178         assert(inner);
 179
 180         if (inner->nr == -1) {
 181                 inner->value_kind    = lpp_none;
 182                 inner->value         = 0.0;
 183                 inner->nr            = lpp->cst_next;
 184                 inner->type.cst_type = cst_type;
 185
 186                 if (lpp->cst_next == lpp->cst_size) {
 187                         lpp->cst_size = (int)((double)lpp->cst_size * lpp->grow_factor) + 1;
 188                         lpp->csts     = XREALLOC(lpp->csts, lpp_name_t *, lpp->cst_size);
 189                 }
 190
 191                 lpp->csts[lpp->cst_next] = inner;
 192                 lpp->cst_next++;
 193                 matrix_set(lpp->m, inner->nr, 0, rhs);
 194         }
 195
 196         update_stats(lpp);
 197         return inner->nr;
 198 }
 199
 200 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs)
 201 {
 202         if (cst_name) {
 203                 lpp_name_t n;
 204
 205                 n.name = cst_name;
 206                 n.nr   = -1;
 207                 assert(!set_find(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n)) &&
 208                     "constraint already exists");
 209         }
 210         return lpp_add_cst(lpp, cst_name, cst_type, rhs);
 211 }
 212
 213 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name)
 214 {
 215         DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
 216         return cst_nr(lpp, cst_name);
 217 }
 218
 219 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
 220 {
 221         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
 222         strncpy(buf, lpp->csts[index]->name, buf_size);
 223 }
 224
 225 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval)
 226 {
 227         int val;
 228
 229         val = lpp_add_var(lpp, var_name, var_type, obj);
 230         lpp_set_start_value(lpp, val, startval);
 231
 232         return val;
 233 }
 234
 235 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj)
 236 {
 237         lpp_name_t n, *inner;
 238
 239         DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
 240
 241         assert(var_type != lpp_invalid && "invalid is for internal use only");
 242
 243         if (var_name && var_name[0] == '_')
 244                 return ERR_NAME_NOT_ALLOWED;
 245
 246         if (var_name)
 247                 n.name = obst_xstrdup(&lpp->obst, var_name);
 248         else
 249                 n.name = get_next_name(lpp);
 250
 251         n.nr  = -1;
 252         inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
 253         assert(inner);
 254
 255         if (inner->nr == -1) {
 256                 inner->nr            = lpp->var_next;
 257                 inner->value_kind    = 0;
 258                 inner->value         = 0;
 259                 inner->type.var_type = var_type;
 260
 261                 if (lpp->var_next == lpp->var_size) {
 262                         lpp->var_size = (int)((double)lpp->var_size * lpp->grow_factor) + 1;
 263                         lpp->vars     = XREALLOC(lpp->vars, lpp_name_t *, lpp->var_size);
 264                 }
 265
 266                 lpp->vars[lpp->var_next] = inner;
 267                 lpp->var_next++;
 268                 matrix_set(lpp->m, 0, inner->nr, obj);
 269         }
 270
 271         update_stats(lpp);
 272         return inner->nr;
 273 }
 274
 275 int lpp_get_var_idx(lpp_t *lpp, const char *var_name)
 276 {
 277         DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
 278         return var_nr(lpp, var_name);
 279 }
 280
 281 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size)
 282 {
 283         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
 284         strncpy(buf, lpp->vars[index]->name, buf_size);
 285 }
 286
 287 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value)
 288 {
 289         int cst, var;
 290
 291         cst = cst_nr(lpp, cst_name);
 292         var = var_nr(lpp, var_name);
 293         assert(cst != -1 && var != -1);
 294         DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
 295         matrix_set(lpp->m, cst, var, value);
 296         update_stats(lpp);
 297         return 0;
 298 }
 299
 300 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value)
 301 {
 302         assert(cst_idx >= 0 && var_idx >= 0);
 303         assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
 304         DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", lpp->csts[cst_idx]->name, cst_idx, lpp->vars[var_idx]->name, var_idx, value));
 305         matrix_set(lpp->m, cst_idx, var_idx, value);
 306         update_stats(lpp);
 307         return 0;
 308 }
 309
 310 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value)
 311 {
 312         assert(cst_idx >= 0 && cst_idx < lpp->cst_next);
 313         assert(num_vars < lpp->var_next);
 314         DBG((dbg, LEVEL_2, "row %s[%d] %d vars %g\n", lpp->csts[cst_idx]->name, cst_idx, num_vars, value));
 315         matrix_set_row_bulk(lpp->m, cst_idx, var_idx, num_vars, value);
 316         update_stats(lpp);
 317         return 0;
 318 }
 319
 320 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value)
 321 {
 322         assert(var_idx > 0 && var_idx < lpp->var_next);
 323         DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
 324         lpp->vars[var_idx]->value = value;
 325         lpp->vars[var_idx]->value_kind = lpp_value_start;
 326 }
 327
 328 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end)
 329 {
 330         int i;
 331
 332         if (lpp->sol_state < lpp_feasible)
 333                 return lpp->sol_state;
 334
 335         /* here we are feasible or optimal */
 336         for (i = 0; i < end - begin + 1; ++i)
 337                 values[i] = lpp->vars[begin + i]->value;
 338
 339         return lpp->sol_state;
 340 }
 341
 342 void lpp_check_startvals(lpp_t *lpp)
 343 {
 344         int cst_idx;
 345
 346         for (cst_idx = 1; cst_idx < lpp->cst_next; ++cst_idx) {
 347                 double     sum     = 0.0;
 348                 lpp_name_t *cst    = lpp->csts[cst_idx];
 349                 double     cst_val = matrix_get(lpp->m, cst_idx, 0);
 350                 int        var_idx;
 351
 352                 for (var_idx = 1; var_idx < lpp->var_next; ++var_idx) {
 353                                 if (lpp->vars[var_idx]->value_kind != lpp_value_start)
 354                                         goto next;
 355
 356                                 sum += lpp->vars[var_idx]->value *
 357                                         matrix_get(lpp->m, cst_idx, var_idx);
 358                 }
 359                 switch(cst->type.cst_type) {
 360                         case lpp_equal:
 361                                 if(sum != cst_val) {
 362                                         fprintf(stderr, "constraint %s unsatisfied: %g != %g\n", cst->name, sum, cst_val);
 363                                 }
 364                                 break;
 365                         case lpp_less:
 366                                 if(sum > cst_val) {
 367                                         fprintf(stderr, "constraint %s unsatisfied: %g > %g\n", cst->name, sum, cst_val);
 368                                 }
 369                                 break;
 370                         case lpp_greater:
 371                                 if(sum < cst_val) {
 372                                         fprintf(stderr, "constraint %s unsatisfied: %g < %g\n", cst->name, sum, cst_val);
 373                                 }
 374                                 break;
 375                         default:
 376                                 assert(0 && "unknown constraint type");
 377                 }
 378 next: ;
 379         }
 380 }
 381
 382 void lpp_dump(lpp_t *lpp, const char *filename)
 383 {
 384         FILE *out = fopen(filename, "wt");
 385         mps_write_mps(lpp, s_mps_fixed, out);
 386         fclose(out);
 387 }
 388
 389 void lpp_set_log(lpp_t *lpp, FILE *log)
 390 {
 391         lpp->log = log;
 392 }
 393
 394
 395 static const char *lpp_cst_op_to_str(lpp_cst_t cst)
 396 {
 397         switch(cst) {
 398         case lpp_equal:
 399                 return "=";
 400         case lpp_less:
 401                 return "<=";
 402         case lpp_greater:
 403                 return ">=";
 404         default:
 405                 return "";
 406         }
 407 }
 408
 409 void lpp_dump_plain(lpp_t *lpp, FILE *f)
 410 {
 411         int i;
 412
 413         for(i = 0; i < lpp->cst_next; ++i) {
 414                 const matrix_elem_t *elm;
 415                 lpp_name_t *cst = lpp->csts[i];
 416
 417                 fprintf(f, "%16s: ", cst->name);
 418                 matrix_foreach_in_row(lpp->m, cst->nr, elm) {
 419                         lpp_name_t *var = lpp->vars[elm->col];
 420                         /* TODO Perhaps better a define LPP_COL_RHS */
 421                         if(elm->col > 0)
 422                                 fprintf(f, "%+4.1f*%-16s ", elm->val, var->name);
 423                 }
 424
 425                 fprintf(f, "%3s %+4.1f\n",
 426                                 lpp_cst_op_to_str(cst->type.cst_type), matrix_get(lpp->m, cst->nr, 0));
 427         }
 428 }
 429
 430 /**
 431  * Serialize a lpp to a file descriptor.
 432  * @param comm The file descriptor.
 433  * @param lpp The lpp.
 434  */
 435 void lpp_serialize(lpp_comm_t *comm, const lpp_t *lpp, int with_names)
 436 {
 437         int n, i;
 438
 439         lpp_writel(comm, with_names);
 440         lpp_writel(comm, lpp->cst_next);
 441         lpp_writel(comm, lpp->var_next);
 442         lpp_writel(comm, lpp->opt_type);
 443         lpp_writes(comm, lpp->name);
 444
 445         /* write options */
 446         lpp_writel(comm, lpp->set_bound);
 447         lpp_writed(comm, lpp->bound);
 448         lpp_writed(comm, lpp->time_limit_secs);
 449         lpp_writed(comm, lpp->emphasis);
 450
 451         for(i = 0; i < lpp->cst_next; ++i) {
 452                 lpp_name_t *name = lpp->csts[i];
 453                 lpp_writel(comm, name->nr);
 454                 lpp_writel(comm, name->value_kind);
 455                 lpp_writel(comm, name->type.cst_type);
 456
 457                 if(with_names)
 458                         lpp_writes(comm, name->name);
 459         }
 460
 461         for(i = 0; i < lpp->var_next; ++i) {
 462                 lpp_name_t *name = lpp->vars[i];
 463                 lpp_writel(comm, name->nr);
 464                 lpp_writel(comm, name->value_kind);
 465                 lpp_writel(comm, name->type.var_type);
 466
 467                 if(with_names)
 468                         lpp_writes(comm, name->name);
 469         }
 470
 471         {
 472                 const matrix_elem_t *elm;
 473                 n = 0;
 474
 475                 matrix_foreach(lpp->m, elm)
 476                         n++;
 477
 478                 assert(n == matrix_get_entries(lpp->m));
 479                 lpp_writel(comm, n);
 480                 matrix_foreach(lpp->m, elm) {
 481                         lpp_writel(comm, elm->row);
 482                         lpp_writel(comm, elm->col);
 483                         lpp_writed(comm, elm->val);
 484                 }
 485         }
 486 }
 487
 488 /**
 489  * Deserialize an lpp from a file descriptor.
 490  * @param comm The file descriptor.
 491  * @return The Problem.
 492  */
 493 lpp_t *lpp_deserialize(lpp_comm_t *comm)
 494 {
 495         int i, n;
 496         int with_names;
 497
 498         lpp_t *lpp = XMALLOCZ(lpp_t);
 499
 500         /* read general settings */
 501         with_names    = lpp_readl(comm);
 502         lpp->cst_next = lpp_readl(comm);
 503         lpp->var_next = lpp_readl(comm);
 504         lpp->opt_type = lpp_readl(comm);
 505         lpp->name     = lpp_reads(comm);
 506
 507         /* read options */
 508         lpp->set_bound       = lpp_readl(comm);
 509         lpp->bound           = lpp_readd(comm);
 510         lpp->time_limit_secs = lpp_readd(comm);
 511         lpp->emphasis        = lpp_readd(comm);
 512
 513         lpp->cst_size = lpp->cst_next;
 514         lpp->var_size = lpp->var_next;
 515
 516         lpp->cst2nr   = new_set(cmp_name_t, lpp->cst_next);
 517         lpp->var2nr   = new_set(cmp_name_t, lpp->var_next);
 518
 519         lpp->csts     = XMALLOCNZ(lpp_name_t*, lpp->cst_next);
 520         lpp->vars     = XMALLOCNZ(lpp_name_t*, lpp->var_next);
 521         lpp->m        = new_matrix(lpp->cst_next, lpp->var_next);
 522
 523         for(i = 0; i < lpp->cst_next; ++i) {
 524                 lpp_name_t name, *res;
 525
 526                 name.nr            = lpp_readl(comm);
 527                 name.value_kind    = lpp_readl(comm);
 528                 name.type.cst_type = lpp_readl(comm);
 529
 530                 if(with_names) {
 531                         name.name = lpp_reads(comm);
 532                 } else {
 533                         char* buf = XMALLOCN(char, 32);
 534                         snprintf(buf, 32, "c%d\n", name.nr);
 535                         name.name = buf;
 536                 }
 537
 538                 res = set_insert(lpp->cst2nr, &name, sizeof(name), HASH_NAME_T(&name));
 539                 lpp->csts[name.nr] = res;
 540         }
 541
 542         for(i = 0; i < lpp->var_next; ++i) {
 543                 lpp_name_t name, *res;
 544
 545                 name.nr            = lpp_readl(comm);
 546                 name.value_kind    = lpp_readl(comm);
 547                 name.type.var_type = lpp_readl(comm);
 548
 549                 if(with_names) {
 550                         name.name = lpp_reads(comm);
 551                 } else {
 552                         char* buf = XMALLOCN(char, 32);
 553                         snprintf(buf, 32, "v%d\n", name.nr);
 554                         name.name = buf;
 555                 }
 556
 557                 res = set_insert(lpp->var2nr, &name, sizeof(name), HASH_NAME_T(&name));
 558                 lpp->vars[name.nr] = res;
 559         }
 560
 561         n = lpp_readl(comm);
 562         for(i = 0; i < n; ++i) {
 563                 matrix_elem_t elm;
 564                 elm.row = lpp_readl(comm);
 565                 elm.col = lpp_readl(comm);
 566                 elm.val = lpp_readd(comm);
 567                 matrix_set(lpp->m, elm.row, elm.col, elm.val);
 568         }
 569
 570         return lpp;
 571 }
 572
 573 void lpp_serialize_values(lpp_comm_t *comm, const lpp_t *lpp, lpp_value_kind_t value_kind)
 574 {
 575         int i, n;
 576
 577         for(i = 0, n = 0; i < lpp->var_next; ++i)
 578                 n += lpp->vars[i]->value_kind == value_kind;
 579
 580         /* Write the number of values to expect */
 581         lpp_writel(comm, n);
 582
 583         /* send the values */
 584         for(i = 0, n = lpp->var_next; i < n; ++i) {
 585                 const lpp_name_t *name = lpp->vars[i];
 586                 if(name->value_kind == value_kind) {
 587                         lpp_writel(comm, name->nr);
 588                         lpp_writed(comm, name->value);
 589                 }
 590         }
 591 }
 592
 593 void lpp_deserialize_values(lpp_comm_t *comm, lpp_t *lpp, lpp_value_kind_t value_kind)
 594 {
 595         int i, n;
 596
 597         /* Get the number of values to read */
 598         n = lpp_readl(comm);
 599
 600         for(i = 0; i < n; ++i) {
 601                 int nr = lpp_readl(comm);
 602                 lpp_name_t *name = lpp->vars[nr];
 603
 604                 name->value_kind = value_kind;
 605                 name->value = lpp_readd(comm);
 606         }
 607 }
 608
 609 void lpp_serialize_stats(lpp_comm_t *comm, const lpp_t *lpp)
 610 {
 611         lpp_writel(comm, lpp->sol_state);
 612         lpp_writel(comm, lpp->iterations);
 613         lpp_writed(comm, lpp->sol_time);
 614         lpp_writed(comm, lpp->objval);
 615         lpp_writed(comm, lpp->best_bound);
 616 }
 617
 618 void lpp_deserialize_stats(lpp_comm_t *comm, lpp_t *lpp)
 619 {
 620         lpp->sol_state  = lpp_readl(comm);
 621         lpp->iterations = lpp_readl(comm);
 622         lpp->sol_time   = lpp_readd(comm);
 623         lpp->objval     = lpp_readd(comm);
 624         lpp->best_bound = lpp_readd(comm);
 625 }
 626
 627 void lpp_solve(lpp_t *lpp, const char* host, const char* solver)
 628 {
 629         if (host == NULL || strlen(host) == 0) {
 630                 lpp_solver_func_t* f = lpp_find_solver(solver);
 631                 if (f != NULL)
 632                         f(lpp);
 633         } else {
 634                 lpp_solve_net(lpp, host, solver);
 635         }
 636 }
 637