Анимация
JavaScript


Главная  Библионтека 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [ 72 ] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

стоянию в, после чего считываем очередные два бита слова s. Аналогично, вторая строка табл. 14.2 означает, что если текзоцим состоянием является А, а сканированная пара битов S равна 01, то на выходе мы получаем (0,1) и остаемся в состоянии А.

Получаемые на выходе биты накапливаются в порядке слева направо. Когда s оказывается сканированным до конца, мы получаем на выходе и-битовые величины д: и у. Предположим в качестве примера, что и=3и.у=110100. Поскольку процесс начинается в состоянии А и первые сканированные биты равны И, мы получаем на выходе (1,0) и переходим в состояние D (четвертая строка табл. 14.2). Затем, находясь в состоянии D и получая очередную пару битов s, равную 01, в соответствии с 14-й строкой табл. 14.2 мы получаем на выходе (0,1) и остаемся в состоянии D. И наконец, последняя пара битов 00 дает нам на выходе (1,1) и переводит нас в состояние С (хотя, поскольку строка s сканирована до конца, это состояние не играет никакой роли).

Итак, в результате сканирования и переходов получена пара (101,011), т.е. х=5 и у=3.

Реализующая описанный алгоритм программа на языке программирования С приведена в листинге 14.3. В этой программе текзацее состояние представлено целым числом из диапазона 0-3, соответствующего состояниям A-D. В присвоении переменной row текущее состояние объединяется с очередными двумя битами s, давая целое число от О до 15, которое представляет собой номер строки в табл. 14.2. Переменная row используется при обращении к целым числам, которые представляют собой два правых столбца табл. 14.2, т.е., по сути, осуществляется табличный поиск в регистре. В используемых шестнадцатеричных значениях биты слева направо соответствуют значениям табл. 14.2, просматриваемым снизу вверх.

Листинг 14.3. Программа для вычисления д: и у по значению s

void hil xy from s(unsigned s, int n,

unsigned *xp, unsigned *yp)

int i;

unsigned state, x, y, row;

state =0; Инициализация

X = у = 0;

for (i = 2*n - 2; i >= 0; i -= 2) Выполнить n раз {

row = 4*state (s >> i) Ь 3; Строка в таблице X = (х « 1) I (ОхЭЗбС » row) Ь 1; у = (у << 1) I (ОхЗЭСб » row) Ь 1; state = I

(0ХЗЕ6В94С1 » 2*row) Ь 3; Новое состояние

*хр = X; Возврат *УР = У; результатов

В [44] приводится несколько иной алгоритм. В отличие от алгоритма из листинга 14.3, он сканирует биты s справа налево. Алгоритм базируется на том, что можно отобразить младшие значащие биты s на (д:,у), основываясь на кривой Гильберта первого

порядка, после чего переходить к тестированию следующей пары битов s. Если они равны 00, то только что вычисленные значения (д:,у) должны поменяться местами (что соответствует отражению относительно прямой д:=у (см. рис. 14.1, кривые первого и второго порядка). Если эти биты равны 01 или 10, то значения д: и у остаются неизменными.



и наконец, если значение пары битов равно 11, то значенияхиу обмениваются и к ним применяется операция дополнения. Те же правила применяются и при дальнейшем сканировании битовой строки S. Этот алгоритм схематично представлен в табл. 14.3, а реализующий его код - в листинге 14.4. Интересно, что сначала можно добаблять биты к х и у, а уже затем выполнять операции обмена и дополнения над полученными значениями, включающими только что добавленные биты; результат окажется тем же, что и при добавлении битов после обмена и дополнения.

Таблица 14.3. Метод вычисления (х,у) по значению s [44]

Если следующие два бита s слева равны

и добавляем спереди к {д:,у)

Обмениваем хиу

(0,0)

Оставляем д: и у без изменений

(0,1)

Оставляем д: и у без изменений

(1,1)

Обмениваем д: и у и выполняем операцию дополнения

(1,0)

Листинг 14.4. Метод вычисления {х,у) по значению s [44]

void hil xy from s (unsigned s, int n,

unsigned *xp, unsigned *yp)

int i, sa, sb;

unsigned x, y, temp;

for (i = 0; i < 2*n; i += 2) {

sa = (s >> (i+l>) Ь 1; Бит i+1 строки s

sb = (s » i) Ь 1;

if ((sa {

sb> == 0)

temp = X; X = y*(-sa); у = temp*(-sa);

(X, » 1) I (sa « 31); У = (y » 1) I

( (sa " sb) « 31)

*xp = X » (32 - n) ; *yp = у » (32 - n>;

Бит i строки s

Если sa,sb = 00 или 11, обмениваем хиу и, если sa = 1, дополняем их

Добавляем sa к х и

(sa*sb) к у (спереди)

Выравниваем хиу вправо и возвращаем их

Переменные х и у в листинге 14.4 не инициализированы, что в некоторых компиляторах может привести к сообщению об ошибке. Однако приведенный код корректно функционирует независимо от того, какие значения имели переменные хиу изначально.

Условного перехода в цикле в листинге 14.4 можно избежать, если воспользоваться рассматривавшимся в разделе 2.19 приемом "трех исключающих или". Блок if при этом можно заменить следующим кодом (здесь swap и cmpl - беззнаковые целые переменные):



swap = (sa * sb) - 1;

Если требуется обмен, -1; в противном случае О

cmpl = -(sa & sb);

Если требуется дополнение, -1; S противном случае О

X = X У;

у = у * (X Ь swap) X = X * у;

cmpl;

Однако при этом требуется выполнение девяти команд, в то время как при использовании условного перехода достаточно только двух или шести, в зависимости от выполнения условия, так что, возможно, отказ от условного перехода в данном случае - не лучший выбор.

Идея "обмена и дополнения" из [44] подсказывает логическую схему для построения кривой Гильберта. Идея, лежащая в основе описываемой далее схемы, состоит в том, чтобы, проходя вдоль кривой и-го порядка, вы отображали пары битов s в координаты (х,у) в соответствии с отображением А из табл. 14.1. При прохождении различных областей координаты, полученные в результате отображения, могут меняться местами, дополняться либо над ними могут выполняться обе эти операции. Схема, показанная на рис. 14.3, отслеживает необходимость выполнения данных операций на каждом шаге, использует соответствующее отображение двух битов .у на (л:,,у,) и генерирует сигналы

обмена и дополнения для следующего шага.

"211-1 °2п-2

21*1 2i.

Ci.i-

Si So

Xi Yi

i=b».®M.i)]®C,,, y,=b<®*2,4i®M4i)]®C,,

Рис. 14.3. Логическая схема для увеличения {х,у) на один шаг вдоль кривой Гильберта

Предположим, что имеется регистр, содержащий длину пути s вдоль кривой Гильберта и схемы для ее увеличения. Тогда для поиска следующей точки кривой Гильберта следует сначала увеличить значение s, а затем преобразовать его так, как показано в табл. 14.4. Преобразования s в таблице вьшолняются слева направо, что создает определенные трудности, так как увеличение s- процесс, затрагивающий биты в порядке справа налево. Таким образом, время, необходимое для генерации очередной точки кривой Гильберта и-го порядка, пропорционально 2и (для увеличения s) плюс и (для преобразования S в пару координат (х,у)).



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [ 72 ] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87