Как вращать центрированный шестиугольный битборд? - PullRequest
Новая
       65

Как вращать центрированный шестиугольный битборд?

0 голосов
/ 01 сентября 2018

Рассмотрим следующее центрированное гексагональное представление битборда (заполнение выделено жирным шрифтом): 

                <b>56</b>
            <b>55</b>      <b>49</b>
        <b>54</b>      48      <b>42</b>
    <b>53</b>      47      41      <b>35</b>
<b>52</b>      46      40      34      <b>28</b>
    45      39      33      27
<b>44</b>      38      32      26      <b>20</b>
    37      31      25      19
<b>36</b>      30      24      18      <b>12</b>
    29      23      17      11
<b>28</b>      22      16      10      <b>04</b>
    21      15      09      03
<b>20</b>      14      08      02      <b>60</b>
    <b>13</b>      07      01      <b>59</b>
        <b>06</b>      00      <b>58</b>
            <b>63</b>      <b>57</b>
                <b>56</b>

Это представление вписывается в 64-разрядное целое число и позволяет легко перемещаться в 6 шестиугольных направлениях, поворачивая биты 1, 7 или 8 пробелов вправо или влево соответственно. Если это помогает с визуализацией, вы можете деформировать этот шестиугольник в квадрат: 

<b>42</b>  <b>43</b>  <b>44</b>  45  46  47  48

<b>35</b>  <b>36</b>  37  38  39  40  41

<b>28</b>  29  30  31  32  33  34

21  22  23  24  25  26  27

14  15  16  17  18  19  <b>20</b>

07  08  09  10  11  <b>12</b>  <b>13</b>

00  01  02  03  <b>04</b>  <b>05</b>  <b>06</b>

Теперь я хочу повернуть этот битборд на 60 & deg; по часовой стрелке, так что треугольник [45,46,47,38,39,31] становится треугольником [48,41,34,40,33,32] и т. д. Как мне это сделать?

1 Ответ

0 голосов
/ 02 сентября 2018

Эта перестановка является своего рода беспорядком, причем каждый соответствующий бит имеет определенное расстояние перемещения. Диаграмма перестановок выглядит следующим образом (выводится верхняя строка):

perm diagram

Это предполагает некоторые подходы, хотя. Если мы посмотрим ближе к вершине, каждая «группа» формируется путем сбора некоторых битов из ввода в порядке возрастания, так что это можно сделать с помощью 7 compress_right операций, также известных как PEXT, которые эффективен на Intel (пока не так эффективен на AMD). На самом деле все сводится к выборке из вертикальных столбцов, поэтому выборка битов происходит с шагом 8.

Так что, если PEXT приемлемо, это можно сделать следующим образом (не проверено): 

uint64_t g0 = _pext_u64(in, 0x8080808);
uint64_t g1 = _pext_u64(in, 0x404040404);
uint64_t g2 = _pext_u64(in, 0x20202020202);
uint64_t g3 = _pext_u64(in, 0x1010101010101);
uint64_t g4 = _pext_u64(in, 0x808080808080);
uint64_t g5 = _pext_u64(in, 0x404040404000);
uint64_t g6 = _pext_u64(in, 0x202020200000);
uint64_t out = g0 |  (g1 << 7) |  (g2 << 14) | (g3 << 21) |
               (g4 << 28) | (g5 << 35) | (g6 << 42);

Эта перестановка не маршрутизируется сетью бабочек, но сети Бенеша универсальны, так что они будут работать.

Таким образом, это можно сделать с помощью 11 из этих шагов перестановки, также известных как дельта-свопы: 

word bit_permute_step(word source, word mask, int shift) {
  word t;
  t = ((source >> shift) ^ source) & mask;
  return (source ^ t) ^ (t << shift);
  }

Существует несколько вариантов создания точных масок, но это работает: 

x = bit_permute_step(x, 0x1001400550054005, 1);
x = bit_permute_step(x, 0x2213223111023221, 2);
x = bit_permute_step(x, 0x01010B020104090E, 4);
x = bit_permute_step(x, 0x002900C400A7007B, 8);
x = bit_permute_step(x, 0x00000A0400002691, 16);
x = bit_permute_step(x, 0x0000000040203CAD, 32);
x = bit_permute_step(x, 0x0000530800001CE0, 16);
x = bit_permute_step(x, 0x000C001400250009, 8);
x = bit_permute_step(x, 0x0C00010403080104, 4);
x = bit_permute_step(x, 0x2012000011100100, 2);
x = bit_permute_step(x, 0x0141040000000010, 1);
...