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
Coordinate()37 Coordinate::Coordinate()
38 {
39 dim = DIM_X;
40 ord = 0;
41 }
42
Coordinate(enum Dim dim,INT_32 n)43 Coordinate::Coordinate(enum Dim dim, INT_32 n)
44 {
45 set(dim, n);
46 }
47
set(enum Dim d,INT_32 n)48 VOID Coordinate::set(enum Dim d, INT_32 n)
49 {
50 dim = d;
51 ord = static_cast<INT_8>(n);
52 }
53
ison(const UINT_32 * coords) const54 UINT_32 Coordinate::ison(const UINT_32 *coords) const
55 {
56 UINT_32 bit = static_cast<UINT_32>(1ull << static_cast<UINT_32>(ord));
57
58 return (coords[dim] & bit) ? 1 : 0;
59 }
60
getdim()61 enum Dim Coordinate::getdim()
62 {
63 return dim;
64 }
65
getord()66 INT_8 Coordinate::getord()
67 {
68 return ord;
69 }
70
operator ==(const Coordinate & b)71 BOOL_32 Coordinate::operator==(const Coordinate& b)
72 {
73 return (dim == b.dim) && (ord == b.ord);
74 }
75
operator <(const Coordinate & b)76 BOOL_32 Coordinate::operator<(const Coordinate& b)
77 {
78 BOOL_32 ret;
79
80 if (dim == b.dim)
81 {
82 ret = ord < b.ord;
83 }
84 else
85 {
86 if (dim == DIM_S || b.dim == DIM_M)
87 {
88 ret = TRUE;
89 }
90 else if (b.dim == DIM_S || dim == DIM_M)
91 {
92 ret = FALSE;
93 }
94 else if (ord == b.ord)
95 {
96 ret = dim < b.dim;
97 }
98 else
99 {
100 ret = ord < b.ord;
101 }
102 }
103
104 return ret;
105 }
106
operator >(const Coordinate & b)107 BOOL_32 Coordinate::operator>(const Coordinate& b)
108 {
109 BOOL_32 lt = *this < b;
110 BOOL_32 eq = *this == b;
111 return !lt && !eq;
112 }
113
operator <=(const Coordinate & b)114 BOOL_32 Coordinate::operator<=(const Coordinate& b)
115 {
116 return (*this < b) || (*this == b);
117 }
118
operator >=(const Coordinate & b)119 BOOL_32 Coordinate::operator>=(const Coordinate& b)
120 {
121 return !(*this < b);
122 }
123
operator !=(const Coordinate & b)124 BOOL_32 Coordinate::operator!=(const Coordinate& b)
125 {
126 return !(*this == b);
127 }
128
operator ++(INT_32)129 Coordinate& Coordinate::operator++(INT_32)
130 {
131 ord++;
132 return *this;
133 }
134
135 // CoordTerm
136
CoordTerm()137 CoordTerm::CoordTerm()
138 {
139 num_coords = 0;
140 }
141
Clear()142 VOID CoordTerm::Clear()
143 {
144 num_coords = 0;
145 }
146
add(Coordinate & co)147 VOID CoordTerm::add(Coordinate& co)
148 {
149 // This function adds a coordinate INT_32o the list
150 // It will prevent the same coordinate from appearing,
151 // and will keep the list ordered from smallest to largest
152 UINT_32 i;
153
154 for (i = 0; i < num_coords; i++)
155 {
156 if (m_coord[i] == co)
157 {
158 break;
159 }
160 if (m_coord[i] > co)
161 {
162 for (UINT_32 j = num_coords; j > i; j--)
163 {
164 m_coord[j] = m_coord[j - 1];
165 }
166 m_coord[i] = co;
167 num_coords++;
168 break;
169 }
170 }
171
172 if (i == num_coords)
173 {
174 m_coord[num_coords] = co;
175 num_coords++;
176 }
177 }
178
add(CoordTerm & cl)179 VOID CoordTerm::add(CoordTerm& cl)
180 {
181 for (UINT_32 i = 0; i < cl.num_coords; i++)
182 {
183 add(cl.m_coord[i]);
184 }
185 }
186
remove(Coordinate & co)187 BOOL_32 CoordTerm::remove(Coordinate& co)
188 {
189 BOOL_32 remove = FALSE;
190 for (UINT_32 i = 0; i < num_coords; i++)
191 {
192 if (m_coord[i] == co)
193 {
194 remove = TRUE;
195 num_coords--;
196 }
197
198 if (remove)
199 {
200 m_coord[i] = m_coord[i + 1];
201 }
202 }
203 return remove;
204 }
205
Exists(Coordinate & co)206 BOOL_32 CoordTerm::Exists(Coordinate& co)
207 {
208 BOOL_32 exists = FALSE;
209 for (UINT_32 i = 0; i < num_coords; i++)
210 {
211 if (m_coord[i] == co)
212 {
213 exists = TRUE;
214 break;
215 }
216 }
217 return exists;
218 }
219
copyto(CoordTerm & cl)220 VOID CoordTerm::copyto(CoordTerm& cl)
221 {
222 cl.num_coords = num_coords;
223 for (UINT_32 i = 0; i < num_coords; i++)
224 {
225 cl.m_coord[i] = m_coord[i];
226 }
227 }
228
getsize()229 UINT_32 CoordTerm::getsize()
230 {
231 return num_coords;
232 }
233
getxor(const UINT_32 * coords) const234 UINT_32 CoordTerm::getxor(const UINT_32 *coords) const
235 {
236 UINT_32 out = 0;
237 for (UINT_32 i = 0; i < num_coords; i++)
238 {
239 out = out ^ m_coord[i].ison(coords);
240 }
241 return out;
242 }
243
getsmallest(Coordinate & co)244 VOID CoordTerm::getsmallest(Coordinate& co)
245 {
246 co = m_coord[0];
247 }
248
Filter(INT_8 f,Coordinate & co,UINT_32 start,enum Dim axis)249 UINT_32 CoordTerm::Filter(INT_8 f, Coordinate& co, UINT_32 start, enum Dim axis)
250 {
251 for (UINT_32 i = start; i < num_coords;)
252 {
253 if (((f == '<' && m_coord[i] < co) ||
254 (f == '>' && m_coord[i] > co) ||
255 (f == '=' && m_coord[i] == co)) &&
256 (axis == NUM_DIMS || axis == m_coord[i].getdim()))
257 {
258 for (UINT_32 j = i; j < num_coords - 1; j++)
259 {
260 m_coord[j] = m_coord[j + 1];
261 }
262 num_coords--;
263 }
264 else
265 {
266 i++;
267 }
268 }
269 return num_coords;
270 }
271
operator [](UINT_32 i)272 Coordinate& CoordTerm::operator[](UINT_32 i)
273 {
274 return m_coord[i];
275 }
276
operator ==(const CoordTerm & b)277 BOOL_32 CoordTerm::operator==(const CoordTerm& b)
278 {
279 BOOL_32 ret = TRUE;
280
281 if (num_coords != b.num_coords)
282 {
283 ret = FALSE;
284 }
285 else
286 {
287 for (UINT_32 i = 0; i < num_coords; i++)
288 {
289 // Note: the lists will always be in order, so we can compare the two lists at time
290 if (m_coord[i] != b.m_coord[i])
291 {
292 ret = FALSE;
293 break;
294 }
295 }
296 }
297 return ret;
298 }
299
operator !=(const CoordTerm & b)300 BOOL_32 CoordTerm::operator!=(const CoordTerm& b)
301 {
302 return !(*this == b);
303 }
304
exceedRange(const UINT_32 * ranges)305 BOOL_32 CoordTerm::exceedRange(const UINT_32 *ranges)
306 {
307 BOOL_32 exceed = FALSE;
308 for (UINT_32 i = 0; (i < num_coords) && (exceed == FALSE); i++)
309 {
310 exceed = ((1u << m_coord[i].getord()) <= ranges[m_coord[i].getdim()]);
311 }
312
313 return exceed;
314 }
315
316 // coordeq
CoordEq()317 CoordEq::CoordEq()
318 {
319 m_numBits = 0;
320 }
321
remove(Coordinate & co)322 VOID CoordEq::remove(Coordinate& co)
323 {
324 for (UINT_32 i = 0; i < m_numBits; i++)
325 {
326 m_eq[i].remove(co);
327 }
328 }
329
Exists(Coordinate & co)330 BOOL_32 CoordEq::Exists(Coordinate& co)
331 {
332 BOOL_32 exists = FALSE;
333
334 for (UINT_32 i = 0; i < m_numBits; i++)
335 {
336 if (m_eq[i].Exists(co))
337 {
338 exists = TRUE;
339 }
340 }
341 return exists;
342 }
343
resize(UINT_32 n)344 VOID CoordEq::resize(UINT_32 n)
345 {
346 if (n > m_numBits)
347 {
348 for (UINT_32 i = m_numBits; i < n; i++)
349 {
350 m_eq[i].Clear();
351 }
352 }
353 m_numBits = n;
354 }
355
getsize()356 UINT_32 CoordEq::getsize()
357 {
358 return m_numBits;
359 }
360
solve(const UINT_32 * coords) const361 UINT_64 CoordEq::solve(const UINT_32 *coords) const
362 {
363 UINT_64 out = 0;
364 for (UINT_32 i = 0; i < m_numBits; i++)
365 {
366 out |= static_cast<UINT_64>(m_eq[i].getxor(coords)) << i;
367 }
368 return out;
369 }
370
solveAddr(UINT_64 addr,UINT_32 sliceInM,UINT_32 * coords) const371 VOID CoordEq::solveAddr(
372 UINT_64 addr, UINT_32 sliceInM,
373 UINT_32 *coords) const
374 {
375 UINT_32 BitsValid[NUM_DIMS] = {0};
376
377 CoordEq temp = *this;
378
379 memset(coords, 0, NUM_DIMS * sizeof(coords[0]));
380
381 UINT_32 bitsLeft = 0;
382
383 for (UINT_32 i = 0; i < temp.m_numBits; i++)
384 {
385 UINT_32 termSize = temp.m_eq[i].getsize();
386
387 if (termSize == 1)
388 {
389 INT_8 bit = (addr >> i) & 1;
390 enum Dim dim = temp.m_eq[i][0].getdim();
391 INT_8 ord = temp.m_eq[i][0].getord();
392
393 ADDR_ASSERT((ord < 32) || (bit == 0));
394
395 BitsValid[dim] |= 1u << ord;
396 coords[dim] |= bit << ord;
397
398 temp.m_eq[i].Clear();
399 }
400 else if (termSize > 1)
401 {
402 bitsLeft++;
403 }
404 }
405
406 if (bitsLeft > 0)
407 {
408 if (sliceInM != 0)
409 {
410 coords[DIM_Z] = coords[DIM_M] / sliceInM;
411 BitsValid[DIM_Z] = 0xffffffff;
412 }
413
414 do
415 {
416 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 enum Dim 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 ADDR_ASSERT(dim < DIM_S);
430
431 BitsValid[dim] |= 1u << ord;
432 coords[dim] |= bit << ord;
433
434 temp.m_eq[i].Clear();
435 }
436 else if (termSize > 1)
437 {
438 CoordTerm tmpTerm = temp.m_eq[i];
439
440 for (UINT_32 j = 0; j < termSize; j++)
441 {
442 enum Dim dim = temp.m_eq[i][j].getdim();
443 INT_8 ord = temp.m_eq[i][j].getord();
444
445 ADDR_ASSERT(dim < DIM_S);
446
447 if (BitsValid[dim] & (1u << ord))
448 {
449 UINT_32 v = (((coords[dim] >> ord) & 1) << i);
450 addr ^= static_cast<UINT_64>(v);
451 tmpTerm.remove(temp.m_eq[i][j]);
452 }
453 }
454
455 temp.m_eq[i] = tmpTerm;
456
457 bitsLeft++;
458 }
459 }
460 } while (bitsLeft > 0);
461 }
462 }
463
copy(CoordEq & o,UINT_32 start,UINT_32 num)464 VOID CoordEq::copy(CoordEq& o, UINT_32 start, UINT_32 num)
465 {
466 o.m_numBits = (num == 0xFFFFFFFF) ? m_numBits : num;
467 for (UINT_32 i = 0; i < o.m_numBits; i++)
468 {
469 m_eq[start + i].copyto(o.m_eq[i]);
470 }
471 }
472
reverse(UINT_32 start,UINT_32 num)473 VOID CoordEq::reverse(UINT_32 start, UINT_32 num)
474 {
475 UINT_32 n = (num == 0xFFFFFFFF) ? m_numBits : num;
476
477 for (UINT_32 i = 0; i < n / 2; i++)
478 {
479 CoordTerm temp;
480 m_eq[start + i].copyto(temp);
481 m_eq[start + n - 1 - i].copyto(m_eq[start + i]);
482 temp.copyto(m_eq[start + n - 1 - i]);
483 }
484 }
485
xorin(CoordEq & x,UINT_32 start)486 VOID CoordEq::xorin(CoordEq& x, UINT_32 start)
487 {
488 UINT_32 n = ((m_numBits - start) < x.m_numBits) ? (m_numBits - start) : x.m_numBits;
489 for (UINT_32 i = 0; i < n; i++)
490 {
491 m_eq[start + i].add(x.m_eq[i]);
492 }
493 }
494
Filter(INT_8 f,Coordinate & co,UINT_32 start,enum Dim axis)495 UINT_32 CoordEq::Filter(INT_8 f, Coordinate& co, UINT_32 start, enum Dim axis)
496 {
497 for (UINT_32 i = start; i < m_numBits;)
498 {
499 UINT_32 m = m_eq[i].Filter(f, co, 0, axis);
500 if (m == 0)
501 {
502 for (UINT_32 j = i; j < m_numBits - 1; j++)
503 {
504 m_eq[j] = m_eq[j + 1];
505 }
506 m_numBits--;
507 }
508 else
509 {
510 i++;
511 }
512 }
513 return m_numBits;
514 }
515
shift(INT_32 amount,INT_32 start)516 VOID CoordEq::shift(INT_32 amount, INT_32 start)
517 {
518 if (amount != 0)
519 {
520 INT_32 numBits = static_cast<INT_32>(m_numBits);
521 amount = -amount;
522 INT_32 inc = (amount < 0) ? -1 : 1;
523 INT_32 i = (amount < 0) ? numBits - 1 : start;
524 INT_32 end = (amount < 0) ? start - 1 : numBits;
525 for (; (inc > 0) ? i < end : i > end; i += inc)
526 {
527 if ((i + amount < start) || (i + amount >= numBits))
528 {
529 m_eq[i].Clear();
530 }
531 else
532 {
533 m_eq[i + amount].copyto(m_eq[i]);
534 }
535 }
536 }
537 }
538
operator [](UINT_32 i)539 CoordTerm& CoordEq::operator[](UINT_32 i)
540 {
541 return m_eq[i];
542 }
543
mort2d(Coordinate & c0,Coordinate & c1,UINT_32 start,UINT_32 end)544 VOID CoordEq::mort2d(Coordinate& c0, Coordinate& c1, UINT_32 start, UINT_32 end)
545 {
546 if (end == 0)
547 {
548 ADDR_ASSERT(m_numBits > 0);
549 end = m_numBits - 1;
550 }
551 for (UINT_32 i = start; i <= end; i++)
552 {
553 UINT_32 select = (i - start) % 2;
554 Coordinate& c = (select == 0) ? c0 : c1;
555 m_eq[i].add(c);
556 c++;
557 }
558 }
559
mort3d(Coordinate & c0,Coordinate & c1,Coordinate & c2,UINT_32 start,UINT_32 end)560 VOID CoordEq::mort3d(Coordinate& c0, Coordinate& c1, Coordinate& c2, UINT_32 start, UINT_32 end)
561 {
562 if (end == 0)
563 {
564 ADDR_ASSERT(m_numBits > 0);
565 end = m_numBits - 1;
566 }
567 for (UINT_32 i = start; i <= end; i++)
568 {
569 UINT_32 select = (i - start) % 3;
570 Coordinate& c = (select == 0) ? c0 : ((select == 1) ? c1 : c2);
571 m_eq[i].add(c);
572 c++;
573 }
574 }
575
operator ==(const CoordEq & b)576 BOOL_32 CoordEq::operator==(const CoordEq& b)
577 {
578 BOOL_32 ret = TRUE;
579
580 if (m_numBits != b.m_numBits)
581 {
582 ret = FALSE;
583 }
584 else
585 {
586 for (UINT_32 i = 0; i < m_numBits; i++)
587 {
588 if (m_eq[i] != b.m_eq[i])
589 {
590 ret = FALSE;
591 break;
592 }
593 }
594 }
595 return ret;
596 }
597
operator !=(const CoordEq & b)598 BOOL_32 CoordEq::operator!=(const CoordEq& b)
599 {
600 return !(*this == b);
601 }
602
603 } // V2
604 } // Addr
605