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