Таблица 14.4. Логика вычислений (х,у) по значению s

На рис. 14.3 эти вычисления показаны в виде логической схемы (5 обозначает сигнал обмена, а С - сигнал дополнения).

В схеме на рис. 14.3 предлагается другой путь вычисления (х,у) по значению s. Обратите внимание на то, как сигналы обмена и дополнения распространяются слева направо через и стадий. Таким образом, здесь можно применить метод параллельного префикса для быстрого (не за «-1, а за logj« шагов) распространения информации об обмене и дополнении по всем стадиям, а затем использовать некоторые побитовые операции для вычисления j; и у с использованием приведенных на рис. 14.3 уравнений. Значения д: и у перемешаны, и их биты находятся в четных и нечетных позициях слова, так что их следует извлечь оттуда с использованием информации из раздела 7.2. Это может показаться несколько сложным и окупающимся только для больших значений и, однако давайте посмотрим, как все происходит на самом деле.

Процедура, реализующая описанную операцию, приведена в листинге 14.5 [19]. Эта процедура оперирует с величинами, представляющими собой полные слова, так что сначала входное значение s дополняется слева битами 01 (эта битовая комбинация не влияет на количество обменов и дополнений). Затем вычисляется величина cs (complement-swap, дополнение-обмен). ЭЫ слово имеет вид cscs...cs, где каждый отдельный бит с, будучи 1, означает, что соответствующая пара битов должна быть дополнена, а s - что соответствующая пара битов должна быть обменена в соответствии с табл. 14.3. Другими словами, каждая пара битов s отображается в пару cs следующим образом:

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

Листинг 14.5. Метод параллельного префикса для вычисления (х,у) . по значению s

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

unsigned *xp, unsigned *yp)

unsigned comp, swap, cs, t, sr;

s = s I (0x55555555 << 2*n); Заполняем s слева парами

sr = (s >> 1) Ь 0x55555555; 01 (без изменений)

cs = ((s & 0x55555555) + sr) Вычисляем пары дополнений

" 0x55555555; и обменов

Операция PP-XOR распространяет информацию о дополнениях и обменах слева направо, парами (шаг cs *= cs » 1 отсутствует), что дает в результате две операции параллельного префикса над двумя чередующимися множествами из 16 битов каждое cs = cs * (cs >> 2); cs = cs * (cs » 4) ; cs = cs * (cs » 8); cs = cs * (cs » 16);

swap = cs & 0x55555555; Разделяем биты обмена

comp = (cs » 1) Ь 0x55555555; и дополнения t = (s ь swap) * comp; Вычисляем x и у в

s = s * sr * t * (t << 1); нечетных и четных

позициях

s = s Ь ((1 << 2*n) - 1); Убираем лишние биты слева

Разделяем значения хиу

t = (s * (s » D) Ь 0X22222222; s = s * t * (t « 1) t = (s * (s >> 2)) Ь OXOCOCOCOC; s = s * t * (t « 2) t = (s * (s » 4)) Ь OxOOFOOOFO; s = s * t * (t « 4) t = (s * (s » 8)) Ь OXOOOOFFOO; s = s * t * (t « 8) *xp = s >> 16; Присваиваем переменным значения *yp = s Ь OxFFFF; хиу

Оба сигнала (дополнения и обмена) распространяются одной и той же операцией PP-XOR.

Следующие четыре присвоения транслируют каждую пу битов s в значения (х,у), где X состоит из битов, находящихся в нечетных (левых) позициях, а у - из битов в четных позициях. Хотя сама логика может показаться и непонятной, не так уж сложно убедиться в том, что каждая пара битов s преобразуется в соответствии с первыми двумя уравнениями на рис. 14.3 (указание: рассмотрите отдельно преобразования битов в четных и нечетных позициях, не забывая о том, что в нечетных позициях биты t и sr равны 0).

Оставшаяся часть процедуры очевидна. Всего она требует выполнения 66 базовых RISC-команд (без ветвлений), в то время как код из листинга 14.2 требует в среднем выполнения 19п + 10 команд (вычислено на основе скомпилированного кода). Таким образом, уже при п > 3 метод параллельного префикса оказывается более быстрым.

14.3. Преобразование координат в расстояние вдоль кривой Гильберта

Если заданы координаты точки на кривой Гильберта, то расстояние до данной точки вдоль кривой от ее начала можно вычислить при помощи таблицы переходов состояний, подобной табл. 14.2. Для нашей задачи такой таблицей переходов является табл. 14.5.

Таблица 14.5. Таблица переходов состояний для вычисления s по значениям (х,у)

Работа с этой таблицей аналогична работе с таблицей переходов состояний в предыдущем разделе. Сначала значения д: и у должны быть дополнены слева ведущими нулевыми битами с тем, чтобы длина битовых строк, представляющих эти величины, стала равной п, где и - порядок рассматриваемой кривой Гильберта. Затем биты д: и у сканируются слева направо, и значение s строится в том же направлении.

Программа на языке программирования С, реализующая эти действия, представлена в листинге 14.6.

Листинг 14.6. Программа для вычисления s по значениям (х,у)

unsigned hil s from xy(unsigned х,

unsigned у, int n)

int i;

unsigned state, s, row; state = 0; s = 0;

for (i = n - 1; i >= 0; i--) {

row = 4*state 2*((x » i) b 1) (y » i) ь 1;

S = (S << 2) I (0X361E9CB4 >> 2*row) Ь 3; State = (0X8FE65831 » 2*row) Ь 3;

return s;

Инициализация