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

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