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