modelchecker/coord.c

   1 #include <argp.h>
   2 #include <inttypes.h>
   3 #include <locale.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <sys/time.h>
   8
   9 #ifdef HAVE_PROFILER
  10 #include <gperftools/profiler.h>
  11 #endif
  12
  13 #include <sylvan.h>
  14 #include <llmsset.h>
  15 #include <lace.h>
  16
  17 #include "coord.h"
  18 #include "sokoban.h"
  19
  20 typedef struct {
  21         int x;
  22         int y;
  23 } xy;
  24
  25 typedef struct {
  26         int var[3];
  27 } bddvar;
  28
  29 typedef struct {
  30         xy key;
  31         bddvar value;
  32         UT_hash_handle hh;
  33 } xy_bddvar_map;
  34
  35 typedef struct {
  36         int key;
  37         xy value;
  38         UT_hash_handle hh;
  39 } bddvar_xy_map;
  40
  41 typedef struct {
  42         xy_bddvar_map f;
  43         bddvar_xy_map t;
  44 } bimap;
  45
  46 xy_bddvar_map *getxy(int x, int y, xy_bddvar_map *map)
  47 {
  48         xy_bddvar_map k, *r = NULL;
  49         memset(&k, 0, sizeof(xy_bddvar_map));
  50         k.key.x = x;
  51         k.key.y = y;
  52         HASH_FIND(hh, map, &k.key, sizeof(xy), r);
  53         return r;
  54 }
  55
  56 bddvar_xy_map *getbdd(int key, bddvar_xy_map *map)
  57 {
  58         bddvar_xy_map k, *r = NULL;
  59         memset(&k, 0, sizeof(bddvar_xy_map));
  60         k.key = key;
  61         HASH_FIND(hh, map, &k.key, sizeof(int), r);
  62         return r;
  63 }
  64
  65 xy_bddvar_map *create_xy_bddvar_map(sokoban_screen *screen)
  66 {
  67         int varcount = 0;
  68         sokoban_screen *r;
  69         xy_bddvar_map *xybdd = NULL;
  70         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
  71                 xy_bddvar_map *f = NULL;
  72                 //bddvar_xy_map *t = NULL;
  73
  74                 f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
  75                 memset(f, 0, sizeof(xy_bddvar_map));
  76                 f->key.x = r->coord.x;
  77                 f->key.y = r->coord.y;
  78                 printf("test!: %d %d\n", r->coord.x, r->coord.y);
  79                 f->value.var[0] = varcount;
  80                 f->value.var[1] = varcount + 1;
  81                 f->value.var[2] = varcount + 2;
  82                 HASH_ADD(hh, xybdd, key, sizeof(xy), f);
  83                 varcount = varcount + 3;
  84         }
  85         return xybdd;
  86 }
  87
  88 bddvar_xy_map *create_bddvar_xy_map(sokoban_screen *screen)
  89 {
  90         int varcount = 0;
  91         sokoban_screen *r;
  92         bddvar_xy_map *bddxy = NULL;
  93         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
  94                 for (int i = 0; i <3; i++){
  95                         bddvar_xy_map *f = NULL;
  96                         //bddvar_xy_map *t = NULL;
  97
  98                         f = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
  99                         memset(f, 0, sizeof(bddvar_xy_map));
 100                         f->key = varcount + i;
 101                         f->value.x = r->coord.x;
 102                         f->value.y = r->coord.y;
 103                         HASH_ADD(hh, bddxy, key, sizeof(int), f);
 104                 }
 105                 varcount = varcount + 3;
 106         }
 107         return bddxy;
 108 }
 109
 110 /*
 111  * Each coordinate has three related boolean variables. The combination of those boolean variables
 112  * defines tiles:
 113  * 000: Wall
 114  * 001: Free
 115  * 010: Box
 116  * 100: Box on target
 117  * 011: Target
 118  * 101: Agent
 119  * 110: Agent on target
 120  * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
 121  * tiles in the shrinked screen.
 122  * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
 123  * directly in transition relations.
 124  */
 125
 126 BDD encode_screen(sokoban_screen *screen)
 127 {
 128         BDD state = sylvan_false;
 129         int tile_index = 0;
 130         sokoban_screen *r;
 131         LACE_ME;
 132         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
 133                 switch(r->tile){
 134                 case FREE:
 135                         if (state == sylvan_false){
 136                                 state = sylvan_not(sylvan_ithvar(tile_index));
 137                                 tile_index++;
 138                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 139                                 tile_index++;
 140                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 141                                 tile_index++;
 142                         }
 143                         else {
 144                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 145                                 tile_index++;
 146                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 147                                 tile_index++;
 148                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 149                                 tile_index++;
 150                         }
 151                         break;
 152                 case WALL:
 153                         if (state == sylvan_false){
 154                                 state = sylvan_not(sylvan_ithvar(tile_index));
 155                                 tile_index++;
 156                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 157                                 tile_index++;
 158                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 159                                 tile_index++;
 160                         }
 161                         else {
 162                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 163                                 tile_index++;
 164                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 165                                 tile_index++;
 166                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 167                                 tile_index++;
 168                         }
 169                         break;
 170                 case BOX:
 171                         if (state == sylvan_false){
 172                                 state = sylvan_not(sylvan_ithvar(tile_index));
 173                                 tile_index++;
 174                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 175                                 tile_index++;
 176                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 177                                 tile_index++;
 178                         }
 179                         else {
 180                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 181                                 tile_index++;
 182                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 183                                 tile_index++;
 184                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 185                                 tile_index++;
 186                         }
 187                         break;
 188                 case TARGET:
 189                         if (state == sylvan_false){
 190                                 state = sylvan_not(sylvan_ithvar(tile_index));
 191                                 tile_index++;
 192                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 193                                 tile_index++;
 194                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 195                                 tile_index++;
 196                         }
 197                         else {
 198                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 199                                 tile_index++;
 200                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 201                                 tile_index++;
 202                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 203                                 tile_index++;
 204                         }
 205                         break;
 206                 case AGENT:
 207                         if (state == sylvan_false){
 208                                 state = sylvan_ithvar(tile_index);
 209                                 tile_index++;
 210                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 211                                 tile_index++;
 212                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 213                                 tile_index++;
 214                         }
 215                         else {
 216                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 217                                 tile_index++;
 218                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 219                                 tile_index++;
 220                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 221                                 tile_index++;
 222                         }
 223                         break;
 224                 case TARGAGENT:
 225                         if (state == sylvan_false){
 226                                 state = sylvan_ithvar(tile_index);
 227                                 tile_index++;
 228                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 229                                 tile_index++;
 230                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 231                                 tile_index++;
 232                         }
 233                         else {
 234                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 235                                 tile_index++;
 236                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 237                                 tile_index++;
 238                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 239                                 tile_index++;
 240                         }
 241                         break;
 242                 case TARGBOX:
 243                         if (state == sylvan_false){
 244                                 state = sylvan_ithvar(tile_index);
 245                                 tile_index++;
 246                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 247                                 tile_index++;
 248                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 249                                 tile_index++;
 250                         }
 251                         else {
 252                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 253                                 tile_index++;
 254                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 255                                 tile_index++;
 256                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 257                                 tile_index++;
 258                         }
 259                         break;
 260                 }
 261         }
 262         /*
 263         xy_bddvar_map *map = NULL;
 264         map = create_xy_bddvar_map(screen);
 265         xy_bddvar_map *m = getxy(1, 1, map);
 266         bddvar_xy_map *map2 = NULL;
 267         map2 = create_bddvar_xy_map(screen);
 268         bddvar_xy_map *m2 = getbdd(2, map2);
 269         printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
 270         printf("Test2: %d %d\n", m2->value.x, m2->value.y);
 271         */
 272         printf("%d tiles were encoded\n", tile_index);
 273         return state;
 274 }
 275
 276 BDD encode_rel(sokoban_screen *screen)
 277 {
 278         int num_tiles;
 279         num_tiles = HASH_COUNT(screen);
 280         printf("Number of tiles: %d\n", num_tiles);
 281         return sylvan_true;
 282 }
 283
 284 void test()
 285 {
 286
 287         printf("Test!\n");
 288         BDD a = sylvan_true;
 289         BDD b = sylvan_not(a);
 290         if (b == sylvan_false){
 291                 printf("BDD works!\n");
 292         } else {
 293                 printf("BDD does not work!\n");
 294         }
 295         LACE_ME;
 296         BDD c = sylvan_ithvar(1);
 297         if (sylvan_high(c) == sylvan_true && sylvan_low(c) == sylvan_false) printf("VAR works 1\n");
 298         if (sylvan_var(c) == 1) printf("Var works 2\n");
 299 }