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