sys/src/cmd/5c/mul.c

   1 #include "gc.h"
   2
   3 /*
   4  * code sequences for multiply by constant.
   5  * [a-l][0-3]
   6  *      lsl     $(A-'a'),r0,r1
   7  * [+][0-7]
   8  *      add     r0,r1,r2
   9  * [-][0-7]
  10  *      sub     r0,r1,r2
  11  */
  12
  13 static  int     maxmulops = 3;  /* max # of ops to replace mul with */
  14 static  int     multabp;
  15 static  long    mulval;
  16 static  char*   mulcp;
  17 static  long    valmax;
  18 static  int     shmax;
  19
  20 static int      docode(char *hp, char *cp, int r0, int r1);
  21 static int      gen1(int len);
  22 static int      gen2(int len, long r1);
  23 static int      gen3(int len, long r0, long r1, int flag);
  24 enum
  25 {
  26         SR1     = 1<<0,         /* r1 has been shifted */
  27         SR0     = 1<<1,         /* r0 has been shifted */
  28         UR1     = 1<<2,         /* r1 has not been used */
  29         UR0     = 1<<3,         /* r0 has not been used */
  30 };
  31
  32 Multab*
  33 mulcon0(long v)
  34 {
  35         int a1, a2, g;
  36         Multab *m, *m1;
  37         char hint[10];
  38
  39         if(v < 0)
  40                 v = -v;
  41
  42         /*
  43          * look in cache
  44          */
  45         m = multab;
  46         for(g=0; g<nelem(multab); g++) {
  47                 if(m->val == v) {
  48                         if(m->code[0] == 0)
  49                                 return 0;
  50                         return m;
  51                 }
  52                 m++;
  53         }
  54
  55         /*
  56          * select a spot in cache to overwrite
  57          */
  58         multabp++;
  59         if(multabp < 0 || multabp >= nelem(multab))
  60                 multabp = 0;
  61         m = multab+multabp;
  62         m->val = v;
  63         mulval = v;
  64
  65         /*
  66          * look in execption hint table
  67          */
  68         a1 = 0;
  69         a2 = hintabsize;
  70         for(;;) {
  71                 if(a1 >= a2)
  72                         goto no;
  73                 g = (a2 + a1)/2;
  74                 if(v < hintab[g].val) {
  75                         a2 = g;
  76                         continue;
  77                 }
  78                 if(v > hintab[g].val) {
  79                         a1 = g+1;
  80                         continue;
  81                 }
  82                 break;
  83         }
  84
  85         if(docode(hintab[g].hint, m->code, 1, 0))
  86                 return m;
  87         print("multiply table failure %ld\n", v);
  88         m->code[0] = 0;
  89         return 0;
  90
  91 no:
  92         /*
  93          * try to search
  94          */
  95         hint[0] = 0;
  96         for(g=1; g<=maxmulops; g++) {
  97                 if(g >= maxmulops && v >= 65535)
  98                         break;
  99                 mulcp = hint+g;
 100                 *mulcp = 0;
 101                 if(gen1(g)) {
 102                         if(docode(hint, m->code, 1, 0))
 103                                 return m;
 104                         print("multiply table failure %ld\n", v);
 105                         break;
 106                 }
 107         }
 108
 109         /*
 110          * try a recur followed by a shift
 111          */
 112         g = 0;
 113         while(!(v & 1)) {
 114                 g++;
 115                 v >>= 1;
 116         }
 117         if(g) {
 118                 m1 = mulcon0(v);
 119                 if(m1) {
 120                         strcpy(m->code, m1->code);
 121                         sprint(strchr(m->code, 0), "%c0", g+'a');
 122                         return m;
 123                 }
 124         }
 125         m->code[0] = 0;
 126         return 0;
 127 }
 128
 129 static int
 130 docode(char *hp, char *cp, int r0, int r1)
 131 {
 132         int c, i;
 133
 134         c = *hp++;
 135         *cp = c;
 136         cp += 2;
 137         switch(c) {
 138         default:
 139                 c -= 'a';
 140                 if(c < 1 || c >= 30)
 141                         break;
 142                 for(i=0; i<4; i++) {
 143                         switch(i) {
 144                         case 0:
 145                                 if(docode(hp, cp, r0<<c, r1))
 146                                         goto out;
 147                                 break;
 148                         case 1:
 149                                 if(docode(hp, cp, r1<<c, r1))
 150                                         goto out;
 151                                 break;
 152                         case 2:
 153                                 if(docode(hp, cp, r0, r0<<c))
 154                                         goto out;
 155                                 break;
 156                         case 3:
 157                                 if(docode(hp, cp, r0, r1<<c))
 158                                         goto out;
 159                                 break;
 160                         }
 161                 }
 162                 break;
 163
 164         case '+':
 165                 for(i=0; i<8; i++) {
 166                         cp[-1] = i+'0';
 167                         switch(i) {
 168                         case 1:
 169                                 if(docode(hp, cp, r0+r1, r1))
 170                                         goto out;
 171                                 break;
 172                         case 5:
 173                                 if(docode(hp, cp, r0, r0+r1))
 174                                         goto out;
 175                                 break;
 176                         }
 177                 }
 178                 break;
 179
 180         case '-':
 181                 for(i=0; i<8; i++) {
 182                         cp[-1] = i+'0';
 183                         switch(i) {
 184                         case 1:
 185                                 if(docode(hp, cp, r0-r1, r1))
 186                                         goto out;
 187                                 break;
 188                         case 2:
 189                                 if(docode(hp, cp, r1-r0, r1))
 190                                         goto out;
 191                                 break;
 192                         case 5:
 193                                 if(docode(hp, cp, r0, r0-r1))
 194                                         goto out;
 195                                 break;
 196                         case 6:
 197                                 if(docode(hp, cp, r0, r1-r0))
 198                                         goto out;
 199                                 break;
 200                         }
 201                 }
 202                 break;
 203
 204         case 0:
 205                 if(r0 == mulval)
 206                         return 1;
 207         }
 208         return 0;
 209
 210 out:
 211         cp[-1] = i+'0';
 212         return 1;
 213 }
 214
 215 static int
 216 gen1(int len)
 217 {
 218         int i;
 219
 220         for(shmax=1; shmax<30; shmax++) {
 221                 valmax = 1<<shmax;
 222                 if(valmax >= mulval)
 223                         break;
 224         }
 225         if(mulval == 1)
 226                 return 1;
 227
 228         len--;
 229         for(i=1; i<=shmax; i++)
 230                 if(gen2(len, 1<<i)) {
 231                         *--mulcp = 'a'+i;
 232                         return 1;
 233                 }
 234         return 0;
 235 }
 236
 237 static int
 238 gen2(int len, long r1)
 239 {
 240         int i;
 241
 242         if(len <= 0) {
 243                 if(r1 == mulval)
 244                         return 1;
 245                 return 0;
 246         }
 247
 248         len--;
 249         if(len == 0)
 250                 goto calcr0;
 251
 252         if(gen3(len, r1, r1+1, UR1)) {
 253                 i = '+';
 254                 goto out;
 255         }
 256         if(gen3(len, r1-1, r1, UR0)) {
 257                 i = '-';
 258                 goto out;
 259         }
 260         if(gen3(len, 1, r1+1, UR1)) {
 261                 i = '+';
 262                 goto out;
 263         }
 264         if(gen3(len, 1, r1-1, UR1)) {
 265                 i = '-';
 266                 goto out;
 267         }
 268
 269         return 0;
 270
 271 calcr0:
 272         if(mulval == r1+1) {
 273                 i = '+';
 274                 goto out;
 275         }
 276         if(mulval == r1-1) {
 277                 i = '-';
 278                 goto out;
 279         }
 280         return 0;
 281
 282 out:
 283         *--mulcp = i;
 284         return 1;
 285 }
 286
 287 static int
 288 gen3(int len, long r0, long r1, int flag)
 289 {
 290         int i, f1, f2;
 291         long x;
 292
 293         if(r0 <= 0 ||
 294            r0 >= r1 ||
 295            r1 > valmax)
 296                 return 0;
 297
 298         len--;
 299         if(len == 0)
 300                 goto calcr0;
 301
 302         if(!(flag & UR1)) {
 303                 f1 = UR1|SR1;
 304                 for(i=1; i<=shmax; i++) {
 305                         x = r0<<i;
 306                         if(x > valmax)
 307                                 break;
 308                         if(gen3(len, r0, x, f1)) {
 309                                 i += 'a';
 310                                 goto out;
 311                         }
 312                 }
 313         }
 314
 315         if(!(flag & UR0)) {
 316                 f1 = UR1|SR1;
 317                 for(i=1; i<=shmax; i++) {
 318                         x = r1<<i;
 319                         if(x > valmax)
 320                                 break;
 321                         if(gen3(len, r1, x, f1)) {
 322                                 i += 'a';
 323                                 goto out;
 324                         }
 325                 }
 326         }
 327
 328         if(!(flag & SR1)) {
 329                 f1 = UR1|SR1|(flag&UR0);
 330                 for(i=1; i<=shmax; i++) {
 331                         x = r1<<i;
 332                         if(x > valmax)
 333                                 break;
 334                         if(gen3(len, r0, x, f1)) {
 335                                 i += 'a';
 336                                 goto out;
 337                         }
 338                 }
 339         }
 340
 341         if(!(flag & SR0)) {
 342                 f1 = UR0|SR0|(flag&(SR1|UR1));
 343
 344                 f2 = UR1|SR1;
 345                 if(flag & UR1)
 346                         f2 |= UR0;
 347                 if(flag & SR1)
 348                         f2 |= SR0;
 349
 350                 for(i=1; i<=shmax; i++) {
 351                         x = r0<<i;
 352                         if(x > valmax)
 353                                 break;
 354                         if(x > r1) {
 355                                 if(gen3(len, r1, x, f2)) {
 356                                         i += 'a';
 357                                         goto out;
 358                                 }
 359                         } else
 360                                 if(gen3(len, x, r1, f1)) {
 361                                         i += 'a';
 362                                         goto out;
 363                                 }
 364                 }
 365         }
 366
 367         x = r1+r0;
 368         if(gen3(len, r0, x, UR1)) {
 369                 i = '+';
 370                 goto out;
 371         }
 372
 373         if(gen3(len, r1, x, UR1)) {
 374                 i = '+';
 375                 goto out;
 376         }
 377
 378         x = r1-r0;
 379         if(gen3(len, x, r1, UR0)) {
 380                 i = '-';
 381                 goto out;
 382         }
 383
 384         if(x > r0) {
 385                 if(gen3(len, r0, x, UR1)) {
 386                         i = '-';
 387                         goto out;
 388                 }
 389         } else
 390                 if(gen3(len, x, r0, UR0)) {
 391                         i = '-';
 392                         goto out;
 393                 }
 394
 395         return 0;
 396
 397 calcr0:
 398         f1 = flag & (UR0|UR1);
 399         if(f1 == UR1) {
 400                 for(i=1; i<=shmax; i++) {
 401                         x = r1<<i;
 402                         if(x >= mulval) {
 403                                 if(x == mulval) {
 404                                         i += 'a';
 405                                         goto out;
 406                                 }
 407                                 break;
 408                         }
 409                 }
 410         }
 411
 412         if(mulval == r1+r0) {
 413                 i = '+';
 414                 goto out;
 415         }
 416         if(mulval == r1-r0) {
 417                 i = '-';
 418                 goto out;
 419         }
 420
 421         return 0;
 422
 423 out:
 424         *--mulcp = i;
 425         return 1;
 426 }
 427
 428 /*
 429  * hint table has numbers that
 430  * the search algorithm fails on.
 431  * <1000:
 432  *      all numbers
 433  * <5000:
 434  *      ÷ by 5
 435  * <10000:
 436  *      ÷ by 50
 437  * <65536:
 438  *      ÷ by 250
 439  */
 440 Hintab  hintab[] =
 441 {
 442         683,    "b++d+e+",
 443         687,    "b+e++e-",
 444         691,    "b++d+e+",
 445         731,    "b++d+e+",
 446         811,    "b++d+i+",
 447         821,    "b++e+e+",
 448         843,    "b+d++e+",
 449         851,    "b+f-+e-",
 450         853,    "b++e+e+",
 451         877,    "c++++g-",
 452         933,    "b+c++g-",
 453         981,    "c-+e-d+",
 454         1375,   "b+c+b+h-",
 455         1675,   "d+b++h+",
 456         2425,   "c++f-e+",
 457         2675,   "c+d++f-",
 458         2750,   "b+d-b+h-",
 459         2775,   "c-+g-e-",
 460         3125,   "b++e+g+",
 461         3275,   "b+c+g+e+",
 462         3350,   "c++++i+",
 463         3475,   "c-+e-f-",
 464         3525,   "c-+d+g-",
 465         3625,   "c-+e-j+",
 466         3675,   "b+d+d+e+",
 467         3725,   "b+d-+h+",
 468         3925,   "b+d+f-d-",
 469         4275,   "b+g++e+",
 470         4325,   "b+h-+d+",
 471         4425,   "b+b+g-j-",
 472         4525,   "b+d-d+f+",
 473         4675,   "c++d-g+",
 474         4775,   "b+d+b+g-",
 475         4825,   "c+c-+i-",
 476         4850,   "c++++i-",
 477         4925,   "b++e-g-",
 478         4975,   "c+f++e-",
 479         5500,   "b+g-c+d+",
 480         6700,   "d+b++i+",
 481         9700,   "d++++j-",
 482         11000,  "b+f-c-h-",
 483         11750,  "b+d+g+j-",
 484         12500,  "b+c+e-k+",
 485         13250,  "b+d+e-f+",
 486         13750,  "b+h-c-d+",
 487         14250,  "b+g-c+e-",
 488         14500,  "c+f+j-d-",
 489         14750,  "d-g--f+",
 490         16750,  "b+e-d-n+",
 491         17750,  "c+h-b+e+",
 492         18250,  "d+b+h-d+",
 493         18750,  "b+g-++f+",
 494         19250,  "b+e+b+h+",
 495         19750,  "b++h--f-",
 496         20250,  "b+e-l-c+",
 497         20750,  "c++bi+e-",
 498         21250,  "b+i+l+c+",
 499         22000,  "b+e+d-g-",
 500         22250,  "b+d-h+k-",
 501         22750,  "b+d-e-g+",
 502         23250,  "b+c+h+e-",
 503         23500,  "b+g-c-g-",
 504         23750,  "b+g-b+h-",
 505         24250,  "c++g+m-",
 506         24750,  "b+e+e+j-",
 507         25000,  "b++dh+g+",
 508         25250,  "b+e+d-g-",
 509         25750,  "b+e+b+j+",
 510         26250,  "b+h+c+e+",
 511         26500,  "b+h+c+g+",
 512         26750,  "b+d+e+g-",
 513         27250,  "b+e+e+f+",
 514         27500,  "c-i-c-d+",
 515         27750,  "b+bd++j+",
 516         28250,  "d-d-++i-",
 517         28500,  "c+c-h-e-",
 518         29000,  "b+g-d-f+",
 519         29500,  "c+h+++e-",
 520         29750,  "b+g+f-c+",
 521         30250,  "b+f-g-c+",
 522         33500,  "c-f-d-n+",
 523         33750,  "b+d-b+j-",
 524         34250,  "c+e+++i+",
 525         35250,  "e+b+d+k+",
 526         35500,  "c+e+d-g-",
 527         35750,  "c+i-++e+",
 528         36250,  "b+bh-d+e+",
 529         36500,  "c+c-h-e-",
 530         36750,  "d+e--i+",
 531         37250,  "b+g+g+b+",
 532         37500,  "b+h-b+f+",
 533         37750,  "c+be++j-",
 534         38500,  "b+e+b+i+",
 535         38750,  "d+i-b+d+",
 536         39250,  "b+g-l-+d+",
 537         39500,  "b+g-c+g-",
 538         39750,  "b+bh-c+f-",
 539         40250,  "b+bf+d+g-",
 540         40500,  "b+g-c+g+",
 541         40750,  "c+b+i-e+",
 542         41250,  "d++bf+h+",
 543         41500,  "b+j+c+d-",
 544         41750,  "c+f+b+h-",
 545         42500,  "c+h++g+",
 546         42750,  "b+g+d-f-",
 547         43250,  "b+l-e+d-",
 548         43750,  "c+bd+h+f-",
 549         44000,  "b+f+g-d-",
 550         44250,  "b+d-g--f+",
 551         44500,  "c+e+c+h+",
 552         44750,  "b+e+d-h-",
 553         45250,  "b++g+j-g+",
 554         45500,  "c+d+e-g+",
 555         45750,  "b+d-h-e-",
 556         46250,  "c+bd++j+",
 557         46500,  "b+d-c-j-",
 558         46750,  "e-e-b+g-",
 559         47000,  "b+c+d-j-",
 560         47250,  "b+e+e-g-",
 561         47500,  "b+g-c-h-",
 562         47750,  "b+f-c+h-",
 563         48250,  "d--h+n-",
 564         48500,  "b+c-g+m-",
 565         48750,  "b+e+e-g+",
 566         49500,  "c-f+e+j-",
 567         49750,  "c+c+g++f-",
 568         50000,  "b+e+e+k+",
 569         50250,  "b++i++g+",
 570         50500,  "c+g+f-i+",
 571         50750,  "b+e+d+k-",
 572         51500,  "b+i+c-f+",
 573         51750,  "b+bd+g-e-",
 574         52250,  "b+d+g-j+",
 575         52500,  "c+c+f+g+",
 576         52750,  "b+c+e+i+",
 577         53000,  "b+i+c+g+",
 578         53500,  "c+g+g-n+",
 579         53750,  "b+j+d-c+",
 580         54250,  "b+d-g-j-",
 581         54500,  "c-f+e+f+",
 582         54750,  "b+f-+c+g+",
 583         55000,  "b+g-d-g-",
 584         55250,  "b+e+e+g+",
 585         55500,  "b+cd++j+",
 586         55750,  "b+bh-d-f-",
 587         56250,  "c+d-b+j-",
 588         56500,  "c+d+c+i+",
 589         56750,  "b+e+d++h-",
 590         57000,  "b+d+g-f+",
 591         57250,  "b+f-m+d-",
 592         57750,  "b+i+c+e-",
 593         58000,  "b+e+d+h+",
 594         58250,  "c+b+g+g+",
 595         58750,  "d-e-j--e+",
 596         59000,  "d-i-+e+",
 597         59250,  "e--h-m+",
 598         59500,  "c+c-h+f-",
 599         59750,  "b+bh-e+i-",
 600         60250,  "b+bh-e-e-",
 601         60500,  "c+c-g-g-",
 602         60750,  "b+e-l-e-",
 603         61250,  "b+g-g-c+",
 604         61750,  "b+g-c+g+",
 605         62250,  "f--+c-i-",
 606         62750,  "e+f--+g+",
 607         64750,  "b+f+d+p-",
 608 };
 609 int     hintabsize      = nelem(hintab);