ww.h - Man Page
Слова конечной длины
Synopsis
#include 'bee2/defs.h'
#include 'bee2/core/safe.h'
#include 'bee2/core/u32.h'
Макросы
#define wwIsValid(a, n) memIsValid((a), O_OF_W(n))
#define wwIsDisjoint(a, b, n) memIsDisjoint(a, b, O_OF_W(n))
#define wwIsSameOrDisjoint(a, b, n) memIsSameOrDisjoint(a, b, O_OF_W(n))
#define wwIsDisjoint2(a, n, b, m) memIsDisjoint2(a, O_OF_W(n), b, O_OF_W(m))
#define wwIsDisjoint3(a, n, b, m, c, k) memIsDisjoint3(a, O_OF_W(n), b, O_OF_W(m), c, O_OF_W(k))
Функции
void wwCopy (word b[], const word a[], size_t n)
Копирование слов
void wwSwap (word a[], word b[], size_t n)
Перестановка слов
bool_t wwEq (const word a[], const word b[], size_t n)
Проверка совпадения слов
int wwCmp (const word a[], const word b[], size_t n)
Сравнение слов
int wwCmp2 (const word a[], size_t n, const word b[], size_t m)
Сравнение слов разной длины
int wwCmpW (const word a[], size_t n, register word w)
Сравнение слова c машинным словом
void wwXor (word c[], const word a[], const word b[], size_t n)
Cложение слов по модулю 2.
void wwXor2 (word b[], const word a[], size_t n)
Добавление слова по модулю 2.
void wwSetZero (word a[], size_t n)
Обнуление слова
void wwSetW (word a[], size_t n, register word w)
Присвоение слову значения -- машинного слова
void wwRepW (word a[], size_t n, register word w)
Заполнение слова машинным словом
bool_t wwIsZero (const word a[], size_t n)
Нулевое слово?
bool_t wwIsW (const word a[], size_t n, register word w)
Принимает значение -- машинное слово?
bool_t wwIsRepW (const word a[], size_t n, register word w)
Повтор машинного слова?
size_t wwWordSize (const word a[], size_t n)
Размер значащей части слова в машинных словах
size_t wwOctetSize (const word a[], size_t n)
Размер значащей части слова в октетах
bool_t wwTestBit (const word a[], size_t pos)
Проверить разряд слова
word wwGetBits (const word a[], size_t pos, size_t width)
Получить разряды слова
void wwSetBit (word a[], size_t pos, register bool_t val)
Установить разряд слова
void wwSetBits (word a[], size_t pos, size_t width, register word val)
Установить разряды слова
void wwFlipBit (word a[], size_t pos)
Инвертировать разряд слова
size_t wwLoZeroBits (const word a[], size_t n)
Количество первых (младших) нулевых битов
size_t wwHiZeroBits (const word a[], size_t n)
Количество последних (старших) нулевых битов
size_t wwBitSize (const word a[], size_t n)
Размер значащей части слова в битах
size_t wwNAF (word naf[], const word a[], size_t n, size_t w)
Расчет NAF.
void wwShLo (word a[], size_t n, size_t shift)
Сдвиг в сторону первых (младших) разрядов
word wwShLoCarry (word a[], size_t n, size_t shift, word carry)
Сдвиг в сторону первых (младших) разрядов с заемом
void wwShHi (word a[], size_t n, size_t shift)
Сдвиг в сторону последних (старших) разрядов
word wwShHiCarry (word a[], size_t n, size_t shift, word carry)
Сдвиг в сторону последних (старших) разрядов с заемом
void wwTrimLo (word a[], size_t n, size_t pos)
Отбросить первые (младшие) разряды слова
void wwTrimHi (word a[], size_t n, size_t pos)
Отбросить последние (старшие) разряды слова
Подробное описание
Реализованы операции с двоичными словами произвольной конечной длины, т.е. элементами {0,1}*.
Двоичное слово задается массивом машинных слов: word w[n].
Разряды слова w[0] нумеруются от 0 (младший) до B_PER_W - 1 (старший), разряды w[1] -- от B_PER_W (младший) до 2 * B_PER_W - 1 (старший) и т.д.
Запись [n]w означает, что слово w состоит из n машинных слов.
Предусловие
Все входные указатели действительны.
В функциях работы со словами по адресам памяти для слов зарезервировано ясное из конекста либо уточняемое в описаниях функций число машинных слов.
Макросы
#define wwIsDisjoint(a, b, n) memIsDisjoint(a, b, O_OF_W(n))
Буферы слов [n]a и [n]b не пересекаются?
#define wwIsDisjoint2(a, n, b, m) memIsDisjoint2(a, O_OF_W(n), b, O_OF_W(m))
Буферы слов [n]a и [m]b не пересекаются?
#define wwIsDisjoint3(a, n, b, m, c, k) memIsDisjoint3(a, O_OF_W(n), b, O_OF_W(m), c, O_OF_W(k))
Буферы слов [n]a, [m]b и [k]c не пересекаются?
#define wwIsSameOrDisjoint(a, b, n) memIsSameOrDisjoint(a, b, O_OF_W(n))
Буферы слов [n]a и [n]b совпадают или не пересекаются?
#define wwIsValid(a, n) memIsValid((a), O_OF_W(n))
Корректное слово [n]a?
Функции
size_t wwBitSize (const word a[], size_t n)
Определяется размер значащей части слова [n]a. Размер полагается равным индексу последнего ненулевого разряда, увеличенному на единицу.
Прим.
Размер пустого (n == 0) или нулевого слов равняется 0.
Если wwBitSize(a, n) == m > 0, то для a как числа выполняется 2^{m - 1} < a <= 2^m - 1.
Возвращает
Размер значащей части.
Регулярность
Функция нерегулярна.
- Аргументы
a слово
n длина a в машинных словах
int FAST wwCmp (const word a[], const word b[], size_t n)
Cлова [n]a и [n]b сравниваются обратно-лексикографически.
- Прим.
a > b, если a[n - 1] == b[n - 1],..., a[i] == b[i], a[i] > b[i].
Возвращает
1, если a > b, или -1, если a < b, или 0, если a == b.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a первое слово
b второе слово
n длина a и b в машинных словах
int FAST wwCmp2 (const word a[], size_t n, const word b[], size_t m)
Cлова [n]a и [m]b сравниваются обратно-лексикографически (см. wwCmp()) после дополнения нулями до слов одинаковой длины.
Возвращает
1, если a > b, или -1, если a < b, или 0, если a == b.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a первое слово
n длина a в машинных словах
b второе слово
m длина b в машинных словах
int FAST wwCmpW (const word a[], size_t n, register word w)
Слово [n]a сравнивается с машинным словом w.
Возвращает
1, если a > w, или -1, если a < w, или 0, если a == w.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a сравниваемое слово
n длина a в машинных словах
w машинное слово
void wwCopy (word b[], const word a[], size_t n)
Cлово [n]a переписывается в [n]b:
b <- a.
Предусловие
Буфер b либо не пересекается, либо совпадает с буфером a.
- Аргументы
b приемник
a источник
n длина a в машинных словах
bool_t FAST wwEq (const word a[], const word b[], size_t n)
Проверяется совпадение слов [n]a и [n]b.
Возвращает
Признак сопадения.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a первое слово
b второе слово
n длина a и b в машинных словах
void wwFlipBit (word a[], size_t pos)
В слове a инвертируется разряд с номером pos.
Предусловие
По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
- Аргументы
a слово
pos номер разряда
word wwGetBits (const word a[], size_t pos, size_t width)
В слове a определяется разряды с номерами pos,..., pos + width - 1.
Предусловие
По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
width <= B_PER_W.
Возвращает
Машинное слово, составленное из разрядов a с номерами pos (младший), pos + 1,..., pos + width -1 (старший).
- Аргументы
a слово
pos номер первого разряда
width число разрядов
size_t wwHiZeroBits (const word a[], size_t n)
Определяется длина серии из нулевых битов в конце слова [n]a.
Возвращает
Длина серии.
Регулярность
Функция нерегулярна.
- Аргументы
a слово
n длина a в машинных словах
bool_t FAST wwIsRepW (const word a[], size_t n, register word w)
Проверяется, что все машинные слова [n]a принимают значение w:
a[0] == w && a[1] == w && ... && a[n - 1] == w?
Прим.
В пустом слове (n == 0) повторяется значение 0.
- Возвращает
TRUE, если a составлено из w, и FALSE в противном случае.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a проверяемое слово
n длина a в машинных словах
w значение
bool_t FAST wwIsW (const word a[], size_t n, register word w)
Проверяется, что слово [n]a принимает значение w, которое является машинным словом:
a[0] == w && a[1] == ... == a[n - 1] == 0?
Прим.
Пустое слово (n == 0) принимает значение 0.
- Возвращает
TRUE, если a = w, и FALSE в противном случае.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a проверяемое слово
n длина a в машинных словах
w значение
bool_t FAST wwIsZero (const word a[], size_t n)
Проверяется, что слово [n]a нулевое.
- Возвращает
TRUE, если a - нулевое, и FALSE в противном случае.
Регулярность
Имеется ускоренная нерегулярная редакция.
- Аргументы
a проверяемое слово
n длина a в машинных словах
size_t wwLoZeroBits (const word a[], size_t n)
Определяется длина серии из нулевых битов в начале слова [n]a.
Возвращает
Длина серии.
Регулярность
Функция нерегулярна.
- Аргументы
a слово
n длина a в машинных словах
size_t wwNAF (word naf[], const word a[], size_t n, size_t w)
В [2n + 1]naf помещается кодированное представление оптимальной знаковой формы (NAF) слова [n]a. Рассчитывается оконная NAF с размером окна w.
- Прим.
NAF(a, w) представляет собой последовательность символов (a_0, a_1,..., a_{l-1}) такую, что
- a_i ∈ {0, ± 1, ± 3, ..., ± 2^{w-1} - 1};
- если a != 0, то a_{l-1} != 0;
- a как число равняется \sum {i=0}^{l-1} a_i 2^i;
- среди любых w последовательных символов a_i только один ненулевой.
Известно, что l - длина NAF - не превосходит wwBitSize(a) + 1.
Кодирование символов состоит в следующем (<b> -- двоичная запись числа b):
- нулевые a_i представляются одним двоичным символом 0;
- положительные a_i представляются w двоичными символами 0<a_i>;
- отрицательные a_i представляются w двоичными символами 1<|a_i|>;
- кодированное представление - это конкатенация кода a_{l-1} (первые символы), ...., кода a_1, кода a_0 (последние символы).
Для кодирования w последовательных элементов a_i потребуется не более (w - 1) * 1 + 1 * w = 2 * w - 1 битов. Поэтому при w < B_PER_W для хранения всего кодового представления потребуется не более 2 * n + 1 слов.
Если при расчете NAF получен суффикс α, 0,..., 0, 1, в котором w - 1 нулей и α < 0, то этот суффикс заменяется на β, 0,..., 0, 1, в котором w - 2 нулей и β = 2^{w - 1} + α > 0. Суффиксы описывают одинаковые числа: 2^w + α = 2^{w - 1} + β. Длина второго суффикса и соответствующей NAF на единицу меньше.
Предусловие
2 <= w < B_PER_W.
Буфер naf не пересекается с буфером a.
Возвращает
Размер naf (число символов l).
Регулярность
Функция нерегулярна.
- Аргументы
naf знаковая форма
a слово
n длина a в машинных словах
w длина окна
size_t wwOctetSize (const word a[], size_t n)
Определяется размер значащей части слова [n]a. Размер полагается равным индексу последнего ненулевого октета, увеличенному на единицу.
Прим.
Размер пустого (n == 0) или нулевого слов равняется 0.
Регулярность
Функция нерегулярна.
- Аргументы
a слово
n длина a в машинных словах
void wwRepW (word a[], size_t n, register word w)
Всем машинным словам [n]a присваивается значение w:
a[0] <- w, a[1] <- w, ..., a[n - 1] <- w.
- Предусловие
n > 0 или w == 0.
- Аргументы
a слово
n длина a в машинных словах
w значение
void wwSetBit (word a[], size_t pos, register bool_t val)
В слове a разряду с номером pos присваивается значение val.
Предусловие
По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
val == FALSE || val == TRUE.
- Аргументы
a обрабатываемое слово
pos номер разряда
val устанавливаемое значение
void wwSetBits (word a[], size_t pos, size_t width, register word val)
В слове a определяется разряды с номерами pos,..., pos + width - 1 устанавливаются равными последовательным разрядам val (от младшего к старшему).
Предусловие
По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
width <= B_PER_W.
- Аргументы
a слово
pos номер первого разряда
width число разрядов
val значение разрядов
void wwSetW (word a[], size_t n, register word w)
Слову [n]a присваивается значение w, которое является машинным словом:
a[0] <- w, a[1] <- 0, ..., a[n - 1] <- 0.
- Предусловие
n > 0 или w == 0.
- Аргументы
a слово
n длина a в машинных словах
w значение
void wwSetZero (word a[], size_t n)
Слово [n]a обнуляется:
a <- 0.
- Аргументы
a слово
n длина a в машинных словах
void wwShHi (word a[], size_t n, size_t shift)
Слово [n]a сдвигается на shift позиций в сторону последних разрядов. Освободившиеся разряды заполняются нулями.
Прим.
При интерпретации слов как чисел сдвиг означает умножение на число 2^shift с приведением результата mod 2^{n * B_PER_W}.
- Аргументы
a сдвигаемое слово
n длина a в машинных словах
shift величина сдвига
word wwShHiCarry (word a[], size_t n, size_t shift, word carry)
Слово [n]a сдвигается на shift позиций в сторону последних разрядов. Освободившиеся разряды заполняются разрядами carry.
Возвращает
Машинное слово, составленное из вытесненных последними разрядов.
- Аргументы
a сдвигаемое слово
n длина a в машинных словах
shift величина сдвига
carry машинное слово заема
void wwShLo (word a[], size_t n, size_t shift)
Слово [n]a сдвигается на shift позиций в сторону первых разрядов. Освободившиеся разряды заполняются нулями.
Прим.
При интерпретации слов как чисел сдвиг означает деление на число 2^shift с приведением результата mod 2^{n * B_PER_W}.
- Аргументы
a сдвигаемое слово
n длина a в машинных словах
shift величина сдвига
word wwShLoCarry (word a[], size_t n, size_t shift, word carry)
Слово [n]a сдвигается на shift позиций в сторону первых разрядов. Освободившиеся разряды заполняются разрядами carry.
Возвращает
Машинное слово, составленное из вытесненных последними разрядов.
- Аргументы
a сдвигаемое слово
n длина a в машинных словах
shift величина сдвига
carry машинное слово заема
void wwSwap (word a[], word b[], size_t n)
Cлова [n]a и [n]b меняются местами:
a <-> b.
Предусловие
Буфер b не пересекается с буфером a.
- Аргументы
a первое слово
b второе слово
n длина a и b в машинных словах
bool_t wwTestBit (const word a[], size_t pos)
В слове a определяется разряд с номером pos.
Предусловие
По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
- Возвращает
TRUE, если бит ненулевой, и FALSE в противном случае.
- Аргументы
a слово
pos номер разряда
void wwTrimHi (word a[], size_t n, size_t pos)
В слове [n]a обнуляются разряды с номерами pos, pos + 1,...., n * B_PER_W - 1.
Прим.
При pos >= n * B_PER_W никаких действий не выполняется.
При интерпретации слов как чисел отбрасывание разрядов означает приведение mod 2^pos.
- Аргументы
a обрабатываемое слово
n длина a в машинных словах
pos номер первого обнуляемого разряда
void wwTrimLo (word a[], size_t n, size_t pos)
В слове [n]a обнуляются разряды с номерами 0, 1,..., min(pos, n * B_PER_W) - 1.
- Аргументы
a обрабатываемое слово
n длина a в машинных словах
pos граница обнуляемых разрядов
size_t wwWordSize (const word a[], size_t n)
Определяется размер значащей части слова [n]a. Размер полагается равным индексу последнего ненулевого машинного слова, увеличенному на единицу.
Прим.
Размер пустого (n == 0) или нулевого слов равняется 0.
Регулярность
Функция нерегулярна.
- Аргументы
a слово
n длина a в машинных словах
void wwXor (word c[], const word a[], const word b[], size_t n)
Определяется поразрядная по модулю 2 сумма [n]с слов [n]a и [n]b:
c <- a ^ b.
Предусловие
Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.
- Аргументы
c сумма
a первое слагаемое
b второе слагаемое
n длина a и b в машинных словах
void wwXor2 (word b[], const word a[], size_t n)
К слову [n]b добавляется слово [n]a. Сложение выполняется поразрядно по модулю 2:
b <- a ^ b.
Предусловие
Буфер b либо не пересекается, либо совпадает с буфером a.
- Аргументы
b второе слагаемое / сумма
a первое слагаемое
n длина a в машинных словах
Автор
Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.