src/amd/addrlib/src/core/coord.cpp

   1
   2 /*
   3  * Copyright © 2007-2019 Advanced Micro Devices, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  16  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  17  * NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS, AUTHORS
  18  * AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  20  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  21  * USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  *
  23  * The above copyright notice and this permission notice (including the
  24  * next paragraph) shall be included in all copies or substantial portions
  25  * of the Software.
  26  */
  27
  28 // Coordinate class implementation
  29 #include "addrcommon.h"
  30 #include "coord.h"
  31
  32 namespace Addr
  33 {
  34 namespace V2
  35 {
  36
  37 Coordinate::Coordinate()
  38 {
  39     dim = 'x';
  40     ord = 0;
  41 }
  42
  43 Coordinate::Coordinate(INT_8 c, INT_32 n)
  44 {
  45     set(c, n);
  46 }
  47
  48 VOID Coordinate::set(INT_8 c, INT_32 n)
  49 {
  50     dim = c;
  51     ord = static_cast<INT_8>(n);
  52 }
  53
  54 UINT_32 Coordinate::ison(UINT_32 x, UINT_32 y, UINT_32 z, UINT_32 s, UINT_32 m) const
  55 {
  56     UINT_32 bit = static_cast<UINT_32>(1ull << static_cast<UINT_32>(ord));
  57     UINT_32 out = 0;
  58
  59     switch (dim)
  60     {
  61     case 'm': out = m & bit; break;
  62     case 's': out = s & bit; break;
  63     case 'x': out = x & bit; break;
  64     case 'y': out = y & bit; break;
  65     case 'z': out = z & bit; break;
  66     }
  67     return (out != 0) ? 1 : 0;
  68 }
  69
  70 INT_8 Coordinate::getdim()
  71 {
  72     return dim;
  73 }
  74
  75 INT_8 Coordinate::getord()
  76 {
  77     return ord;
  78 }
  79
  80 BOOL_32 Coordinate::operator==(const Coordinate& b)
  81 {
  82     return (dim == b.dim) && (ord == b.ord);
  83 }
  84
  85 BOOL_32 Coordinate::operator<(const Coordinate& b)
  86 {
  87     BOOL_32 ret;
  88
  89     if (dim == b.dim)
  90     {
  91         ret = ord < b.ord;
  92     }
  93     else
  94     {
  95         if (dim == 's' || b.dim == 'm')
  96         {
  97             ret = TRUE;
  98         }
  99         else if (b.dim == 's' || dim == 'm')
 100         {
 101             ret = FALSE;
 102         }
 103         else if (ord == b.ord)
 104         {
 105             ret = dim < b.dim;
 106         }
 107         else
 108         {
 109             ret = ord < b.ord;
 110         }
 111     }
 112
 113     return ret;
 114 }
 115
 116 BOOL_32 Coordinate::operator>(const Coordinate& b)
 117 {
 118     BOOL_32 lt = *this < b;
 119     BOOL_32 eq = *this == b;
 120     return !lt && !eq;
 121 }
 122
 123 BOOL_32 Coordinate::operator<=(const Coordinate& b)
 124 {
 125     return (*this < b) || (*this == b);
 126 }
 127
 128 BOOL_32 Coordinate::operator>=(const Coordinate& b)
 129 {
 130     return !(*this < b);
 131 }
 132
 133 BOOL_32 Coordinate::operator!=(const Coordinate& b)
 134 {
 135     return !(*this == b);
 136 }
 137
 138 Coordinate& Coordinate::operator++(INT_32)
 139 {
 140     ord++;
 141     return *this;
 142 }
 143
 144 // CoordTerm
 145
 146 CoordTerm::CoordTerm()
 147 {
 148     num_coords = 0;
 149 }
 150
 151 VOID CoordTerm::Clear()
 152 {
 153     num_coords = 0;
 154 }
 155
 156 VOID CoordTerm::add(Coordinate& co)
 157 {
 158     // This function adds a coordinate INT_32o the list
 159     // It will prevent the same coordinate from appearing,
 160     // and will keep the list ordered from smallest to largest
 161     UINT_32 i;
 162
 163     for (i = 0; i < num_coords; i++)
 164     {
 165         if (m_coord[i] == co)
 166         {
 167             break;
 168         }
 169         if (m_coord[i] > co)
 170         {
 171             for (UINT_32 j = num_coords; j > i; j--)
 172             {
 173                 m_coord[j] = m_coord[j - 1];
 174             }
 175             m_coord[i] = co;
 176             num_coords++;
 177             break;
 178         }
 179     }
 180
 181     if (i == num_coords)
 182     {
 183         m_coord[num_coords] = co;
 184         num_coords++;
 185     }
 186 }
 187
 188 VOID CoordTerm::add(CoordTerm& cl)
 189 {
 190     for (UINT_32 i = 0; i < cl.num_coords; i++)
 191     {
 192         add(cl.m_coord[i]);
 193     }
 194 }
 195
 196 BOOL_32 CoordTerm::remove(Coordinate& co)
 197 {
 198     BOOL_32 remove = FALSE;
 199     for (UINT_32 i = 0; i < num_coords; i++)
 200     {
 201         if (m_coord[i] == co)
 202         {
 203             remove = TRUE;
 204             num_coords--;
 205         }
 206
 207         if (remove)
 208         {
 209             m_coord[i] = m_coord[i + 1];
 210         }
 211     }
 212     return remove;
 213 }
 214
 215 BOOL_32 CoordTerm::Exists(Coordinate& co)
 216 {
 217     BOOL_32 exists = FALSE;
 218     for (UINT_32 i = 0; i < num_coords; i++)
 219     {
 220         if (m_coord[i] == co)
 221         {
 222             exists = TRUE;
 223             break;
 224         }
 225     }
 226     return exists;
 227 }
 228
 229 VOID CoordTerm::copyto(CoordTerm& cl)
 230 {
 231     cl.num_coords = num_coords;
 232     for (UINT_32 i = 0; i < num_coords; i++)
 233     {
 234         cl.m_coord[i] = m_coord[i];
 235     }
 236 }
 237
 238 UINT_32 CoordTerm::getsize()
 239 {
 240     return num_coords;
 241 }
 242
 243 UINT_32 CoordTerm::getxor(UINT_32 x, UINT_32 y, UINT_32 z, UINT_32 s, UINT_32 m) const
 244 {
 245     UINT_32 out = 0;
 246     for (UINT_32 i = 0; i < num_coords; i++)
 247     {
 248         out = out ^ m_coord[i].ison(x, y, z, s, m);
 249     }
 250     return out;
 251 }
 252
 253 VOID CoordTerm::getsmallest(Coordinate& co)
 254 {
 255     co = m_coord[0];
 256 }
 257
 258 UINT_32 CoordTerm::Filter(INT_8 f, Coordinate& co, UINT_32 start, INT_8 axis)
 259 {
 260     for (UINT_32 i = start;  i < num_coords;)
 261     {
 262         if (((f == '<' && m_coord[i] < co) ||
 263              (f == '>' && m_coord[i] > co) ||
 264              (f == '=' && m_coord[i] == co)) &&
 265             (axis == '\0' || axis == m_coord[i].getdim()))
 266         {
 267             for (UINT_32 j = i; j < num_coords - 1; j++)
 268             {
 269                 m_coord[j] = m_coord[j + 1];
 270             }
 271             num_coords--;
 272         }
 273         else
 274         {
 275             i++;
 276         }
 277     }
 278     return num_coords;
 279 }
 280
 281 Coordinate& CoordTerm::operator[](UINT_32 i)
 282 {
 283     return m_coord[i];
 284 }
 285
 286 BOOL_32 CoordTerm::operator==(const CoordTerm& b)
 287 {
 288     BOOL_32 ret = TRUE;
 289
 290     if (num_coords != b.num_coords)
 291     {
 292         ret = FALSE;
 293     }
 294     else
 295     {
 296         for (UINT_32 i = 0; i < num_coords; i++)
 297         {
 298             // Note: the lists will always be in order, so we can compare the two lists at time
 299             if (m_coord[i] != b.m_coord[i])
 300             {
 301                 ret = FALSE;
 302                 break;
 303             }
 304         }
 305     }
 306     return ret;
 307 }
 308
 309 BOOL_32 CoordTerm::operator!=(const CoordTerm& b)
 310 {
 311     return !(*this == b);
 312 }
 313
 314 BOOL_32 CoordTerm::exceedRange(UINT_32 xRange, UINT_32 yRange, UINT_32 zRange, UINT_32 sRange)
 315 {
 316     BOOL_32 exceed = FALSE;
 317     for (UINT_32 i = 0; (i < num_coords) && (exceed == FALSE); i++)
 318     {
 319         UINT_32 subject;
 320         switch (m_coord[i].getdim())
 321         {
 322             case 'x':
 323                 subject = xRange;
 324                 break;
 325             case 'y':
 326                 subject = yRange;
 327                 break;
 328             case 'z':
 329                 subject = zRange;
 330                 break;
 331             case 's':
 332                 subject = sRange;
 333                 break;
 334             case 'm':
 335                 subject = 0;
 336                 break;
 337             default:
 338                 // Invalid input!
 339                 ADDR_ASSERT_ALWAYS();
 340                 subject = 0;
 341                 break;
 342         }
 343
 344         exceed = ((1u << m_coord[i].getord()) <= subject);
 345     }
 346
 347     return exceed;
 348 }
 349
 350 // coordeq
 351 CoordEq::CoordEq()
 352 {
 353     m_numBits = 0;
 354 }
 355
 356 VOID CoordEq::remove(Coordinate& co)
 357 {
 358     for (UINT_32 i = 0; i < m_numBits; i++)
 359     {
 360         m_eq[i].remove(co);
 361     }
 362 }
 363
 364 BOOL_32 CoordEq::Exists(Coordinate& co)
 365 {
 366     BOOL_32 exists = FALSE;
 367
 368     for (UINT_32 i = 0; i < m_numBits; i++)
 369     {
 370         if (m_eq[i].Exists(co))
 371         {
 372             exists = TRUE;
 373         }
 374     }
 375     return exists;
 376 }
 377
 378 VOID CoordEq::resize(UINT_32 n)
 379 {
 380     if (n > m_numBits)
 381     {
 382         for (UINT_32 i = m_numBits; i < n; i++)
 383         {
 384             m_eq[i].Clear();
 385         }
 386     }
 387     m_numBits = n;
 388 }
 389
 390 UINT_32 CoordEq::getsize()
 391 {
 392     return m_numBits;
 393 }
 394
 395 UINT_64 CoordEq::solve(UINT_32 x, UINT_32 y, UINT_32 z, UINT_32 s, UINT_32 m) const
 396 {
 397     UINT_64 out = 0;
 398     for (UINT_32 i = 0; i < m_numBits; i++)
 399     {
 400         if (m_eq[i].getxor(x, y, z, s, m) != 0)
 401         {
 402             out |= (1ULL << i);
 403         }
 404     }
 405     return out;
 406 }
 407
 408 VOID CoordEq::solveAddr(
 409     UINT_64 addr, UINT_32 sliceInM,
 410     UINT_32& x, UINT_32& y, UINT_32& z, UINT_32& s, UINT_32& m) const
 411 {
 412     UINT_32 xBitsValid = 0;
 413     UINT_32 yBitsValid = 0;
 414     UINT_32 zBitsValid = 0;
 415     UINT_32 sBitsValid = 0;
 416     UINT_32 mBitsValid = 0;
 417
 418     CoordEq temp = *this;
 419
 420     x = y = z = s = m = 0;
 421
 422     UINT_32 bitsLeft = 0;
 423
 424     for (UINT_32 i = 0; i < temp.m_numBits; i++)
 425     {
 426         UINT_32 termSize = temp.m_eq[i].getsize();
 427
 428         if (termSize == 1)
 429         {
 430             INT_8 bit = (addr >> i) & 1;
 431             INT_8 dim = temp.m_eq[i][0].getdim();
 432             INT_8 ord = temp.m_eq[i][0].getord();
 433
 434             ADDR_ASSERT((ord < 32) || (bit == 0));
 435
 436             switch (dim)
 437             {
 438                 case 'x':
 439                     xBitsValid |= (1 << ord);
 440                     x |= (bit << ord);
 441                     break;
 442                 case 'y':
 443                     yBitsValid |= (1 << ord);
 444                     y |= (bit << ord);
 445                     break;
 446                 case 'z':
 447                     zBitsValid |= (1 << ord);
 448                     z |= (bit << ord);
 449                     break;
 450                 case 's':
 451                     sBitsValid |= (1 << ord);
 452                     s |= (bit << ord);
 453                     break;
 454                 case 'm':
 455                     mBitsValid |= (1 << ord);
 456                     m |= (bit << ord);
 457                     break;
 458                 default:
 459                     break;
 460             }
 461
 462             temp.m_eq[i].Clear();
 463         }
 464         else if (termSize > 1)
 465         {
 466             bitsLeft++;
 467         }
 468     }
 469
 470     if (bitsLeft > 0)
 471     {
 472         if (sliceInM != 0)
 473         {
 474             z = m / sliceInM;
 475             zBitsValid = 0xffffffff;
 476         }
 477
 478         do
 479         {
 480             bitsLeft = 0;
 481
 482             for (UINT_32 i = 0; i < temp.m_numBits; i++)
 483             {
 484                 UINT_32 termSize = temp.m_eq[i].getsize();
 485
 486                 if (termSize == 1)
 487                 {
 488                     INT_8 bit = (addr >> i) & 1;
 489                     INT_8 dim = temp.m_eq[i][0].getdim();
 490                     INT_8 ord = temp.m_eq[i][0].getord();
 491
 492                     ADDR_ASSERT((ord < 32) || (bit == 0));
 493
 494                     switch (dim)
 495                     {
 496                         case 'x':
 497                             xBitsValid |= (1 << ord);
 498                             x |= (bit << ord);
 499                             break;
 500                         case 'y':
 501                             yBitsValid |= (1 << ord);
 502                             y |= (bit << ord);
 503                             break;
 504                         case 'z':
 505                             zBitsValid |= (1 << ord);
 506                             z |= (bit << ord);
 507                             break;
 508                         case 's':
 509                             ADDR_ASSERT_ALWAYS();
 510                             break;
 511                         case 'm':
 512                             ADDR_ASSERT_ALWAYS();
 513                             break;
 514                         default:
 515                             break;
 516                     }
 517
 518                     temp.m_eq[i].Clear();
 519                 }
 520                 else if (termSize > 1)
 521                 {
 522                     CoordTerm tmpTerm = temp.m_eq[i];
 523
 524                     for (UINT_32 j = 0; j < termSize; j++)
 525                     {
 526                         INT_8 dim = temp.m_eq[i][j].getdim();
 527                         INT_8 ord = temp.m_eq[i][j].getord();
 528
 529                         switch (dim)
 530                         {
 531                             case 'x':
 532                                 if (xBitsValid & (1 << ord))
 533                                 {
 534                                     UINT_32 v = (((x >> ord) & 1) << i);
 535                                     addr ^= static_cast<UINT_64>(v);
 536                                     tmpTerm.remove(temp.m_eq[i][j]);
 537                                 }
 538                                 break;
 539                             case 'y':
 540                                 if (yBitsValid & (1 << ord))
 541                                 {
 542                                     UINT_32 v = (((y >> ord) & 1) << i);
 543                                     addr ^= static_cast<UINT_64>(v);
 544                                     tmpTerm.remove(temp.m_eq[i][j]);
 545                                 }
 546                                 break;
 547                             case 'z':
 548                                 if (zBitsValid & (1 << ord))
 549                                 {
 550                                     UINT_32 v = (((z >> ord) & 1) << i);
 551                                     addr ^= static_cast<UINT_64>(v);
 552                                     tmpTerm.remove(temp.m_eq[i][j]);
 553                                 }
 554                                 break;
 555                             case 's':
 556                                 ADDR_ASSERT_ALWAYS();
 557                                 break;
 558                             case 'm':
 559                                 ADDR_ASSERT_ALWAYS();
 560                                 break;
 561                             default:
 562                                 break;
 563                         }
 564                     }
 565
 566                     temp.m_eq[i] = tmpTerm;
 567
 568                     bitsLeft++;
 569                 }
 570             }
 571         } while (bitsLeft > 0);
 572     }
 573 }
 574
 575 VOID CoordEq::copy(CoordEq& o, UINT_32 start, UINT_32 num)
 576 {
 577     o.m_numBits = (num == 0xFFFFFFFF) ? m_numBits : num;
 578     for (UINT_32 i = 0; i < o.m_numBits; i++)
 579     {
 580         m_eq[start + i].copyto(o.m_eq[i]);
 581     }
 582 }
 583
 584 VOID CoordEq::reverse(UINT_32 start, UINT_32 num)
 585 {
 586     UINT_32 n = (num == 0xFFFFFFFF) ? m_numBits : num;
 587
 588     for (UINT_32 i = 0; i < n / 2; i++)
 589     {
 590         CoordTerm temp;
 591         m_eq[start + i].copyto(temp);
 592         m_eq[start + n - 1 - i].copyto(m_eq[start + i]);
 593         temp.copyto(m_eq[start + n - 1 - i]);
 594     }
 595 }
 596
 597 VOID CoordEq::xorin(CoordEq& x, UINT_32 start)
 598 {
 599     UINT_32 n = ((m_numBits - start) < x.m_numBits) ? (m_numBits - start) : x.m_numBits;
 600     for (UINT_32 i = 0; i < n; i++)
 601     {
 602         m_eq[start + i].add(x.m_eq[i]);
 603     }
 604 }
 605
 606 UINT_32 CoordEq::Filter(INT_8 f, Coordinate& co, UINT_32 start, INT_8 axis)
 607 {
 608     for (UINT_32 i = start; i < m_numBits;)
 609     {
 610         UINT_32 m = m_eq[i].Filter(f, co, 0, axis);
 611         if (m == 0)
 612         {
 613             for (UINT_32 j = i; j < m_numBits - 1; j++)
 614             {
 615                 m_eq[j] = m_eq[j + 1];
 616             }
 617             m_numBits--;
 618         }
 619         else
 620         {
 621             i++;
 622         }
 623     }
 624     return m_numBits;
 625 }
 626
 627 VOID CoordEq::shift(INT_32 amount, INT_32 start)
 628 {
 629     if (amount != 0)
 630     {
 631         INT_32 numBits = static_cast<INT_32>(m_numBits);
 632         amount = -amount;
 633         INT_32 inc = (amount < 0) ? -1 : 1;
 634         INT_32 i = (amount < 0) ? numBits - 1 : start;
 635         INT_32 end = (amount < 0) ? start - 1 : numBits;
 636         for (; (inc > 0) ? i < end : i > end; i += inc)
 637         {
 638             if ((i + amount < start) || (i + amount >= numBits))
 639             {
 640                 m_eq[i].Clear();
 641             }
 642             else
 643             {
 644                 m_eq[i + amount].copyto(m_eq[i]);
 645             }
 646         }
 647     }
 648 }
 649
 650 CoordTerm& CoordEq::operator[](UINT_32 i)
 651 {
 652     return m_eq[i];
 653 }
 654
 655 VOID CoordEq::mort2d(Coordinate& c0, Coordinate& c1, UINT_32 start, UINT_32 end)
 656 {
 657     if (end == 0)
 658     {
 659         ADDR_ASSERT(m_numBits > 0);
 660         end = m_numBits - 1;
 661     }
 662     for (UINT_32 i = start; i <= end; i++)
 663     {
 664         UINT_32 select = (i - start) % 2;
 665         Coordinate& c = (select == 0) ? c0 : c1;
 666         m_eq[i].add(c);
 667         c++;
 668     }
 669 }
 670
 671 VOID CoordEq::mort3d(Coordinate& c0, Coordinate& c1, Coordinate& c2, UINT_32 start, UINT_32 end)
 672 {
 673     if (end == 0)
 674     {
 675         ADDR_ASSERT(m_numBits > 0);
 676         end = m_numBits - 1;
 677     }
 678     for (UINT_32 i = start; i <= end; i++)
 679     {
 680         UINT_32 select = (i - start) % 3;
 681         Coordinate& c = (select == 0) ? c0 : ((select == 1) ? c1 : c2);
 682         m_eq[i].add(c);
 683         c++;
 684     }
 685 }
 686
 687 BOOL_32 CoordEq::operator==(const CoordEq& b)
 688 {
 689     BOOL_32 ret = TRUE;
 690
 691     if (m_numBits != b.m_numBits)
 692     {
 693         ret = FALSE;
 694     }
 695     else
 696     {
 697         for (UINT_32 i = 0; i < m_numBits; i++)
 698         {
 699             if (m_eq[i] != b.m_eq[i])
 700             {
 701                 ret = FALSE;
 702                 break;
 703             }
 704         }
 705     }
 706     return ret;
 707 }
 708
 709 BOOL_32 CoordEq::operator!=(const CoordEq& b)
 710 {
 711     return !(*this == b);
 712 }
 713
 714 } // V2
 715 } // Addr