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