sdcc/support/regression/tests/bug-3129.c

   1 /*
   2    bug-3129.c
   3    Based on an error in the stdcbench self-test.
   4  */
   5
   6 #include <testfwk.h>
   7
   8 #ifdef __SDCC
   9 #pragma disable_warning 85
  10 #endif
  11
  12 #if !defined(__SDCC_pdk14) && !defined(__SDCC_pdk15) && !defined(__SDCC_mcs51) && !defined(__SDCC_ds390) // Lack of memory
  13 extern const char stdcbench_name_version_string[];
  14
  15 unsigned long stdcbench(void);
  16
  17 void stdcbench_error(const char *message);
  18
  19 union stdcbench_buffer
  20 {
  21         unsigned char unsigned_char [1536];
  22         char basic_char [1536];
  23         signed int signed_int [32];
  24 };
  25
  26 extern union stdcbench_buffer stdcbench_buffer;
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <stdio.h>
  31
  32 #include <stdbool.h>
  33 #include <stdint.h>
  34 typedef uint_least8_t node_t; // Needs to be an unsigned integer type, that has a maximum value >= MAX_N.
  35 typedef uint_fast8_t count_t; // Needs to be an unsigned type, that has a maximum value >= 2^MAX_K.
  36
  37 #define MAX_K 4
  38 #define MAX_N 8
  39
  40 bool ref_adjacency_matrix[MAX_N][MAX_N];
  41 node_t ref_n;
  42 node_t max_k;
  43
  44 bool check_lnlc(bool);
  45
  46
  47 static bool adjacency_matrix[MAX_N][MAX_N];
  48 static node_t n;
  49 static node_t node_degrees[MAX_N];
  50 static node_t degree_list[MAX_N];
  51 static node_t num_edges;
  52
  53 static node_t k;
  54 static node_t node_colors[MAX_N];
  55
  56 bool ref_adjacency_matrix[MAX_N][MAX_N];
  57 node_t ref_n;
  58 static node_t ref_node_degrees[MAX_N];
  59 static node_t ref_degree_list[MAX_N];
  60 static node_t ref_mindeg, ref_maxdeg;
  61 static node_t ref_num_edges;
  62 static node_t ref_neighbour_degrees[MAX_N];
  63
  64 node_t max_k;
  65
  66 static char *instructions; /* Should point to a buffer of size at least MAX_N^2 * 80 + MAX_N * MAX_K to get instructions or 0 if those are not needed. */
  67
  68 bool add(void);
  69 bool recolor(void);
  70 bool test(void);
  71
  72 /* Add a new, colored node, connect it to a subset of existing colors. */
  73 bool add(void) __reentrant
  74 {
  75         bool ret = false;
  76         node_t sum, ref_sum;
  77         node_t i;
  78         node_t new_node_color; /* Color of new node */
  79         count_t connect_colors; /* Colors new node is connected to (bitmask) */
  80
  81         node_t node_degrees_backup[MAX_N];
  82         node_t degree_list_backup[MAX_N];
  83         node_t num_edges_backup;
  84
  85         memcpy(node_degrees_backup, node_degrees, MAX_N * sizeof(node_t)); /* Copying fixed size is more efficient than copying only the part needed. */
  86         memcpy(degree_list_backup, degree_list, MAX_N * sizeof(node_t));
  87         num_edges_backup = num_edges;
  88
  89         for(connect_colors = 0; connect_colors < (1 << k) && !ret; connect_colors++) /* New node can connect to any subset of existing colors. */
  90         {
  91                 node_degrees[n] = 0;
  92                 n++;
  93                 memset(adjacency_matrix[n - 1], 0, (n - 1) * sizeof(bool)); /* Doing it once here is faster than having an else branch in the loop below. */
  94
  95                 /* Connect new node to existing nodes. */
  96                 for(i = 0; i < n - 1; i++)
  97                         if (connect_colors & (1 << node_colors[i]))
  98                         {
  99                                 num_edges++;
 100                                 if(num_edges + (ref_n - n) * ref_mindeg / 2 > ref_num_edges) /* Early abort when there are too many edges already. */
 101                                         goto tried;
 102                                 if(num_edges - num_edges_backup > ref_maxdeg) /* Early abort when there are too many edges at the new node already. */
 103                                         goto tried;
 104
 105                                 adjacency_matrix[n - 1][i] = true;
 106
 107                                 degree_list[node_degrees[i]]--;
 108                                 node_degrees[i]++;
 109                                 degree_list[node_degrees[i]]++;
 110
 111                                 node_degrees[n - 1]++;
 112                         }
 113                 degree_list[node_degrees[n - 1]]++;
 114
 115                 if(num_edges + (ref_n - n) * ref_maxdeg < ref_num_edges) /* Early abort when there are too few edges still. */
 116                         goto tried;
 117
 118                 if(n == ref_n)
 119                 {
 120                         if(test())
 121                         {
 122                                 if(instructions)
 123                                 {
 124                                         instructions += sprintf(instructions, "Add node %d of color 0, connect it to nodes of the following colors: ", n - 1);
 125                                         for(i = 0; i < k; i++)
 126                                                 if (connect_colors & (1 << i))
 127                                                         instructions += sprintf(instructions, "%d ", i);
 128                                         instructions += sprintf(instructions, "\n");
 129                                 }
 130
 131                                 ret = true;
 132                         }
 133                         goto tried;
 134                 }
 135
 136                 /* Early abort when degrees are too high. */
 137                 sum = 0;
 138                 ref_sum = 0;
 139                 for(i = ref_n - 1; i > 0; i--)
 140                 {
 141                         sum += degree_list[i];
 142                         ref_sum += ref_degree_list[i];
 143                         if(sum > ref_sum)
 144                                 goto tried;
 145                 }
 146
 147                 for(new_node_color = 0; new_node_color <= k && new_node_color < max_k; new_node_color++) /* New node uses existing color, or exactly one above. */
 148                 {
 149                         node_t k_backup = k;
 150
 151                         if(new_node_color == k)
 152                                 k++;
 153
 154                         node_colors[n - 1] = new_node_color;
 155
 156                         /* Recurse to recoloring. */
 157                         if(recolor())
 158                         {
 159                                 if(instructions)
 160                                 {
 161                                         instructions += sprintf(instructions, "Add node %d of color %d, connect it to nodes of the following colors: ", n - 1, new_node_color);
 162                                         for(i = 0; i < k; i++)
 163                                                 if (connect_colors & (1 << i))
 164                                                         instructions += sprintf(instructions, "%d ", i);
 165                                         instructions +=  sprintf(instructions, "\n");
 166                                 }
 167
 168                                 ret = true;
 169
 170                                 goto tried;
 171                         }
 172
 173                         k = k_backup;
 174                 }
 175
 176 tried:
 177                 n--;
 178                 degree_list[n] = 0;
 179                 memcpy(degree_list, degree_list_backup, MAX_N * sizeof(node_t));
 180                 memcpy(node_degrees, node_degrees_backup, MAX_N * sizeof(node_t));
 181                 num_edges = num_edges_backup;
 182         }
 183
 184         return(ret);
 185 }
 186
 187 static node_t recolormap[MAX_K];
 188
 189 bool do_recolor(void)  __reentrant
 190 {
 191         bool ret = false;
 192         node_t i;
 193         node_t node_colors_backup[MAX_N];
 194         bool used_colors[MAX_N];
 195         node_t k_backup;
 196
 197         /* Skip colorings that would recolor the most recently added node - it could have been added with target color in the first place instead. */
 198         if(recolormap[node_colors[n - 1]] != node_colors[n - 1] &&
 199                 recolormap[node_colors[n - 1]] == recolormap[recolormap[node_colors[n - 1]]]) /* Recoloring the new node just for closing gaps created by recoloring of other nodes is ok. */
 200                 return(false);
 201
 202         k_backup = k;
 203         memcpy(node_colors_backup, node_colors, MAX_N * sizeof(node_t));
 204
 205         /* Check coloring */
 206         memset(used_colors, 0, MAX_N * sizeof(bool));
 207         k = 0;
 208         for(i = 0; i < k_backup; i++)
 209         {
 210                 used_colors[recolormap[i]] = true;
 211                 if(recolormap[i] >= k)
 212                         k = recolormap[i] + 1;
 213         }
 214         /* Do not allow gaps in colors. */
 215         for(i = 0; i < k; i++)
 216                 if(!used_colors[i])
 217                         goto tried;
 218
 219         /* Recolor graph. */
 220         for(i = 0; i < n; i++)
 221                 node_colors[i] = recolormap[node_colors[i]];
 222
 223         /* Recurse to node addition. */
 224         if(ret = add())
 225         {
 226                 for(i = 0; i < n; i++)
 227                         if (node_colors[i] != node_colors_backup[i] && instructions)
 228                                 instructions += sprintf(instructions, "Recolor node %d from %d to %d\n", i, node_colors_backup[i], node_colors[i]);
 229         }
 230
 231 tried:
 232         memcpy(node_colors, node_colors_backup, MAX_N * sizeof(node_t));
 233         k = k_backup;
 234
 235         return(ret);
 236 }
 237
 238 bool maprecolor(node_t i)  __reentrant
 239 {
 240         node_t j;
 241
 242         if (i == k) /* Recurse in graph construction algorithm. */
 243                 return(do_recolor());
 244         else /* Recurse in recoloring construction algorithm. */
 245                 for(j = 0; j <= i; j++) /* Never consider higher colors for recoloring. */
 246                 {
 247                         recolormap[i] = j;
 248                         if(maprecolor(i + 1))
 249                                 return(true);
 250                 }
 251         return(false);
 252 }
 253
 254 /* Recolor nodes. */
 255 bool recolor(void)  __reentrant
 256 {
 257         return(maprecolor(0));
 258 }
 259
 260 static node_t testperm[MAX_N];
 261
 262 /* Recursively generate permutations for isomorphism test. */
 263 bool permtest(node_t i) __reentrant
 264 {
 265         node_t j;
 266
 267         /* Check that all edges to the most recently considered node are ok. */
 268         for(j = 0; j + 2 < i; j++)
 269                 if((testperm[i - 1] > testperm[j] ? adjacency_matrix[testperm[i - 1]][testperm[j]] : adjacency_matrix[testperm[j]][testperm[i - 1]]) != ref_adjacency_matrix[i - 1][j])
 270                         return(false);
 271
 272         if(i == n)
 273                 return(true);
 274
 275         for(j = i; j < n; j++)
 276         {
 277                 node_t t;
 278
 279                 if (node_degrees[testperm[j]] != ref_node_degrees[i]) /* Do not try permutations where degrees do not match. */
 280                         continue;
 281
 282                 t = testperm[i];
 283                 testperm[i] = testperm[j];
 284                 testperm[j] = t;
 285
 286                 if(permtest(i + 1))
 287                         return(true);
 288
 289                 t = testperm[i];
 290                 testperm[i] = testperm[j];
 291                 testperm[j] = t;
 292         }
 293
 294         return(false);
 295 }
 296
 297 int cmp(const void *l, const void *r) __reentrant
 298 {
 299         return *((node_t*)r) - *((node_t *)l);
 300 }
 301
 302 void calc_neighbour_degrees(node_t *restrict neighbour_degrees, bool (*adjacency_matrix)[MAX_N], const node_t *restrict degrees)
 303 {
 304         node_t i, j;
 305
 306         memset(neighbour_degrees, 0, MAX_N);
 307         for(i = 0; i < ref_n; i++)
 308                 for(j = 0; j < i; j++)
 309                         if(adjacency_matrix[i][j])
 310                         {
 311                                 neighbour_degrees[i] += (1 << (degrees[j] - 1));
 312                                 neighbour_degrees[j] += (1 << (degrees[i] - 1));
 313                         }
 314         qsort(neighbour_degrees, ref_n, sizeof(node_t), cmp);
 315 }
 316
 317 /* Isomorphism test */
 318 bool test(void)
 319 {
 320         node_t i;
 321         node_t neighbour_degrees[MAX_N];
 322
 323         /* Compare degree list first. */
 324         if (memcmp(ref_degree_list, degree_list, n * sizeof(node_t)))
 325                 return(false);
 326
 327         /* Compare degrees of neighbours next. */
 328         calc_neighbour_degrees(neighbour_degrees, adjacency_matrix, node_degrees);
 329         if (memcmp(ref_neighbour_degrees, neighbour_degrees, n * sizeof(node_t)))
 330                 return(false);
 331
 332         for(i = 0; i < n; i++)
 333                 testperm[i] = i;
 334
 335         return(permtest(0));
 336 }
 337
 338
 339 /* Has the graph ref_adjacency_matrix of ref_n nodes linear nlc-width at most k? */
 340 bool check_lnlc(bool output_instructions)
 341 {
 342         bool ret;
 343         char *startinstructions;
 344         char *outinstructions = stdcbench_buffer.basic_char;
 345         node_t i, j;
 346
 347         if(!ref_n)
 348                 return(true);
 349
 350         memset(ref_node_degrees, 0, MAX_N * sizeof(node_t));
 351         memset(ref_degree_list + 1, 0, (MAX_N - 1) * sizeof(node_t));
 352         ref_degree_list[0] = ref_n;
 353         ref_num_edges = 0;
 354         for(i = 0; i < ref_n; i++)
 355                 for(j = 0; j < i; j++)
 356                         if(ref_adjacency_matrix[i][j])
 357                         {
 358                                 ref_degree_list[ref_node_degrees[i]]--;
 359                                 ref_node_degrees[i]++;
 360                                 ref_degree_list[ref_node_degrees[i]]++;
 361                                 ref_degree_list[ref_node_degrees[j]]--;
 362                                 ref_node_degrees[j]++;
 363                                 ref_degree_list[ref_node_degrees[j]]++;
 364                                 ref_num_edges++;
 365                         }
 366
 367         for(i = 1, ref_mindeg = ref_maxdeg = ref_node_degrees[0]; i < ref_n; i++)
 368         {
 369                 node_t ref_deg = ref_node_degrees[i];
 370                 if (ref_deg < ref_mindeg)
 371                         ref_mindeg = ref_deg;
 372                 if (ref_deg > ref_maxdeg)
 373                         ref_maxdeg = ref_deg;
 374         }
 375
 376         calc_neighbour_degrees(ref_neighbour_degrees, ref_adjacency_matrix, ref_node_degrees);
 377
 378         memset(degree_list, 0, MAX_N * sizeof(node_t));
 379         num_edges = 0;
 380         k = 0;
 381
 382         if(output_instructions)
 383         {
 384                 if(!(startinstructions = instructions = malloc (60 + (ref_n) * (72 + max_k / 8 * 2) + (ref_n - 1) * (ref_n - 2) / 2 * 28)))
 385                         stdcbench_error("c90lib c90lib_lnlc(): malloc() failed\n");
 386                 else
 387                         startinstructions[0] = 0;
 388         }
 389         else
 390                 startinstructions = instructions = 0;
 391
 392         ret = add();
 393
 394         if (ret && startinstructions)
 395         {
 396                 char *c;
 397
 398                 outinstructions += sprintf(outinstructions, "Instructions for constructing the graph:");
 399
 400                 while(c = strrchr(startinstructions, '\n'))
 401                 {
 402                         outinstructions += sprintf(outinstructions, c);
 403                         *c = 0;
 404                 }
 405                 outinstructions += sprintf(outinstructions, "\n%s\n", startinstructions);
 406         }
 407
 408         free(startinstructions);
 409
 410         return(ret);
 411 }
 412
 413 static const char resultinstructions[] =
 414         "Instructions for constructing the graph:\n"
 415         "\n"
 416         "Add node 0 of color 0, connect it to nodes of the following colors: \n"
 417         "Add node 1 of color 1, connect it to nodes of the following colors: \n"
 418         "Add node 2 of color 2, connect it to nodes of the following colors: 0 1 \n"
 419         "Add node 3 of color 1, connect it to nodes of the following colors: 0 \n"
 420         "Add node 4 of color 0, connect it to nodes of the following colors: 0 1 \n"
 421         "Recolor node 2 from 2 to 1\n"
 422         "Add node 5 of color 0, connect it to nodes of the following colors: 1 \n";
 423
 424 static volatile const bool prism[6][6] =
 425         {{0, 1, 1, 1, 0, 0},
 426         {1, 0, 1, 0, 1, 0},
 427         {1, 1, 0, 0, 0, 1},
 428         {1, 0, 0, 0, 1, 1},
 429         {0, 1, 0, 1, 0, 1},
 430         {0, 0, 1, 1, 1, 0}};
 431
 432 void c90lib_lnlc(void)
 433 {
 434         node_t i, j;
 435
 436         ref_n = 6;
 437         for(i = 0; i < ref_n; i++)
 438                 for(j = 0; j < ref_n; j++)
 439                         ref_adjacency_matrix[i][j] = prism[i][j];
 440
 441         for(max_k = 0; max_k <= MAX_K; max_k++)
 442                 if(check_lnlc(true))
 443                         break;
 444
 445         if(k != 1 || strcmp(stdcbench_buffer.basic_char, resultinstructions))
 446                 stdcbench_error("c90lib c90lib_lnlc(): Result validation failed");
 447 }
 448
 449 #define REG(addr, reg)  __sfr __at(addr) reg
 450
 451 void stdcbench_error(const char *message)
 452 {
 453         ASSERT(0);
 454 }
 455
 456 extern void c90lib_lnlc(void);
 457
 458 union stdcbench_buffer stdcbench_buffer;
 459
 460 const char stdcbench_name_version_string[] = "stdcbench 0.6";
 461 #endif
 462
 463 void
 464 testBug(void)
 465 {
 466 #if !defined(__SDCC_mos6502) && !defined(__SDCC_mos65c02) // insufficient stack space
 467 #if !defined(__SDCC_pdk14) && !defined(__SDCC_pdk15) && !defined(__SDCC_mcs51) && !defined(__SDCC_ds390) // Lack of memory
 468         c90lib_lnlc();
 469 #endif
 470 #endif
 471 }
 472