1ww.h(3) Library Functions Manual ww.h(3)
2
6 ww.h - Слова конечной длины
7
10 #include 'bee2/defs.h'
11 #include 'bee2/core/safe.h'
12 #include 'bee2/core/u32.h'
13 Макросы
16 #define wwIsValid(a, n) memIsValid((a), O_OF_W(n))
17 #define wwIsDisjoint(a, b, n) memIsDisjoint(a, b, O_OF_W(n))
18 #define wwIsSameOrDisjoint(a, b, n) memIsSameOrDisjoint(a, b,
19 O_OF_W(n))
20 #define wwIsDisjoint2(a, n, b, m) memIsDisjoint2(a, O_OF_W(n), b,
21 O_OF_W(m))
22 #define wwIsDisjoint3(a, n, b, m, c, k) memIsDisjoint3(a,
23 O_OF_W(n), b, O_OF_W(m), c, O_OF_W(k))
24 Функции
26 void wwCopy (word b[], const word a[], size_t n)
27 Копирование слов
28 void wwSwap (word a[], word b[], size_t n)
29 Перестановка слов
30 bool_t wwEq (const word a[], const word b[], size_t n)
31 Проверка совпадения слов
32 int wwCmp (const word a[], const word b[], size_t n)
33 Сравнение слов
34 int wwCmp2 (const word a[], size_t n, const word b[], size_t m)
35 Сравнение слов разной длины
36 int wwCmpW (const word a[], size_t n, register word w)
37 Сравнение слова c машинным словом
38 void wwXor (word c[], const word a[], const word b[], size_t n)
39 Cложение слов по модулю 2.
40 void wwXor2 (word b[], const word a[], size_t n)
41 Добавление слова по модулю 2.
42 void wwSetZero (word a[], size_t n)
43 Обнуление слова
44 void wwSetW (word a[], size_t n, register word w)
45 Присвоение слову значения -- машинного слова
46 void wwRepW (word a[], size_t n, register word w)
47 Заполнение слова машинным словом
48 bool_t wwIsZero (const word a[], size_t n)
49 Нулевое слово?
50 bool_t wwIsW (const word a[], size_t n, register word w)
51 Принимает значение -- машинное слово?
52 bool_t wwIsRepW (const word a[], size_t n, register word w)
53 Повтор машинного слова?
54 size_t wwWordSize (const word a[], size_t n)
55 Размер значащей части слова в машинных словах
56 size_t wwOctetSize (const word a[], size_t n)
57 Размер значащей части слова в октетах
58 bool_t wwTestBit (const word a[], size_t pos)
59 Проверить разряд слова
60 word wwGetBits (const word a[], size_t pos, size_t width)
61 Получить разряды слова
62 void wwSetBit (word a[], size_t pos, register bool_t val)
63 Установить разряд слова
64 void wwSetBits (word a[], size_t pos, size_t width, register word val)
65 Установить разряды слова
66 void wwFlipBit (word a[], size_t pos)
67 Инвертировать разряд слова
68 size_t wwLoZeroBits (const word a[], size_t n)
69 Количество первых (младших) нулевых битов
70 size_t wwHiZeroBits (const word a[], size_t n)
71 Количество последних (старших) нулевых битов
72 size_t wwBitSize (const word a[], size_t n)
73 Размер значащей части слова в битах
74 size_t wwNAF (word naf[], const word a[], size_t n, size_t w)
75 Расчет NAF.
76 void wwShLo (word a[], size_t n, size_t shift)
77 Сдвиг в сторону первых (младших) разрядов
78 word wwShLoCarry (word a[], size_t n, size_t shift, word carry)
79 Сдвиг в сторону первых (младших) разрядов с заемом
80 void wwShHi (word a[], size_t n, size_t shift)
81 Сдвиг в сторону последних (старших) разрядов
82 word wwShHiCarry (word a[], size_t n, size_t shift, word carry)
83 Сдвиг в сторону последних (старших) разрядов с заемом
84 void wwTrimLo (word a[], size_t n, size_t pos)
85 Отбросить первые (младшие) разряды слова
86 void wwTrimHi (word a[], size_t n, size_t pos)
87 Отбросить последние (старшие) разряды слова
88
90 Реализованы операции с двоичными словами произвольной конечной длины,
91 т.е. элементами {0,1}*.
92 Двоичное слово задается массивом машинных слов: word w[n].
94 Разряды слова w[0] нумеруются от 0 (младший) до B_PER_W - 1 (старший),
96 разряды w[1] -- от B_PER_W (младший) до 2 * B_PER_W - 1 (старший) и
97 т.д.
98 Запись [n]w означает, что слово w состоит из n машинных слов.
100 Предусловие
102 Все входные указатели действительны.
103 В функциях работы со словами по адресам памяти для слов
105 зарезервировано ясное из конекста либо уточняемое в описаниях
106 функций число машинных слов.
107
109 #define wwIsDisjoint(a, b, n) memIsDisjoint(a, b, O_OF_W(n))
110 Буферы слов [n]a и [n]b не пересекаются?
111 #define wwIsDisjoint2(a, n, b, m) memIsDisjoint2(a, O_OF_W(n), b,
113 O_OF_W(m))
114 Буферы слов [n]a и [m]b не пересекаются?
115 #define wwIsDisjoint3(a, n, b, m, c, k) memIsDisjoint3(a, O_OF_W(n),
117 b, O_OF_W(m), c, O_OF_W(k))
118 Буферы слов [n]a, [m]b и [k]c не пересекаются?
119 #define wwIsSameOrDisjoint(a, b, n) memIsSameOrDisjoint(a, b, O_OF_W(n))
121 Буферы слов [n]a и [n]b совпадают или не пересекаются?
122 #define wwIsValid(a, n) memIsValid((a), O_OF_W(n))
124 Корректное слово [n]a?
125
127 size_t wwBitSize (const word a[], size_t n)
128 Определяется размер значащей части слова [n]a. Размер полагается равным
129 индексу последнего ненулевого разряда, увеличенному на единицу.
130 Прим.
132 Размер пустого (n == 0) или нулевого слов равняется 0.
133 Если wwBitSize(a, n) == m > 0, то для a как числа выполняется 2^{m
135 - 1} < a <= 2^m - 1.
136 Возвращает
138 Размер значащей части.
139 Регулярность
141 Функция нерегулярна.
142 Аргументы
144 a слово
145 n длина a в машинных словах
146 int wwCmp (const word a[], const word b[], size_t n)
148 Cлова [n]a и [n]b сравниваются обратно-лексикографически.
149 Прим.
151 a > b, если a[n - 1] == b[n - 1],..., a[i] == b[i], a[i] > b[i].
152 Возвращает
154 1, если a > b, или -1, если a < b, или 0, если a == b.
155 Регулярность
157 Имеется ускоренная нерегулярная редакция.
158 Аргументы
160 a первое слово
161 b второе слово
162 n длина a и b в машинных словах
163 int wwCmp2 (const word a[], size_t n, const word b[], size_t m)
165 Cлова [n]a и [m]b сравниваются обратно-лексикографически (см. wwCmp())
166 после дополнения нулями до слов одинаковой длины.
167 Возвращает
169 1, если a > b, или -1, если a < b, или 0, если a == b.
170 Регулярность
172 Имеется ускоренная нерегулярная редакция.
173 Аргументы
175 a первое слово
176 n длина a в машинных словах
177 b второе слово
178 m длина b в машинных словах
179 int wwCmpW (const word a[], size_t n, register word w)
181 Слово [n]a сравнивается с машинным словом w.
182 Возвращает
184 1, если a > w, или -1, если a < w, или 0, если a == w.
185 Регулярность
187 Имеется ускоренная нерегулярная редакция.
188 Аргументы
190 a сравниваемое слово
191 n длина a в машинных словах
192 w машинное слово
193 void wwCopy (word b[], const word a[], size_t n)
195 Cлово [n]a переписывается в [n]b:
196 b <- a.
198 Предусловие
201 Буфер b либо не пересекается, либо совпадает с буфером a.
202 Аргументы
204 b приемник
205 a источник
206 n длина a в машинных словах
207 bool_t wwEq (const word a[], const word b[], size_t n)
209 Проверяется совпадение слов [n]a и [n]b.
210 Возвращает
212 Признак сопадения.
213 Регулярность
215 Имеется ускоренная нерегулярная редакция.
216 Аргументы
218 a первое слово
219 b второе слово
220 n длина a и b в машинных словах
221 void wwFlipBit (word a[], size_t pos)
223 В слове a инвертируется разряд с номером pos.
224 Предусловие
226 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
227 Аргументы
229 a слово
230 pos номер разряда
231 word wwGetBits (const word a[], size_t pos, size_t width)
233 В слове a определяется разряды с номерами pos,..., pos + width - 1.
234 Предусловие
236 По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
237 width <= B_PER_W.
239 Возвращает
241 Машинное слово, составленное из разрядов a с номерами pos
242 (младший), pos + 1,..., pos + width -1 (старший).
243 Аргументы
245 a слово
246 pos номер первого разряда
247 width число разрядов
248 size_t wwHiZeroBits (const word a[], size_t n)
250 Определяется длина серии из нулевых битов в конце слова [n]a.
251 Возвращает
253 Длина серии.
254 Регулярность
256 Функция нерегулярна.
257 Аргументы
259 a слово
260 n длина a в машинных словах
261 bool_t wwIsRepW (const word a[], size_t n, register word w)
263 Проверяется, что все машинные слова [n]a принимают значение w:
264 a[0] == w && a[1] == w && ... && a[n - 1] == w?
266 Прим.
269 В пустом слове (n == 0) повторяется значение 0.
270 Возвращает
272 TRUE, если a составлено из w, и FALSE в противном случае.
273 Регулярность
275 Имеется ускоренная нерегулярная редакция.
276 Аргументы
278 a проверяемое слово
279 n длина a в машинных словах
280 w значение
281 bool_t wwIsW (const word a[], size_t n, register word w)
283 Проверяется, что слово [n]a принимает значение w, которое является
284 машинным словом:
285 a[0] == w && a[1] == ... == a[n - 1] == 0?
287 Прим.
290 Пустое слово (n == 0) принимает значение 0.
291 Возвращает
293 TRUE, если a = w, и FALSE в противном случае.
294 Регулярность
296 Имеется ускоренная нерегулярная редакция.
297 Аргументы
299 a проверяемое слово
300 n длина a в машинных словах
301 w значение
302 bool_t wwIsZero (const word a[], size_t n)
304 Проверяется, что слово [n]a нулевое.
305 Возвращает
307 TRUE, если a - нулевое, и FALSE в противном случае.
308 Регулярность
310 Имеется ускоренная нерегулярная редакция.
311 Аргументы
313 a проверяемое слово
314 n длина a в машинных словах
315 size_t wwLoZeroBits (const word a[], size_t n)
317 Определяется длина серии из нулевых битов в начале слова [n]a.
318 Возвращает
320 Длина серии.
321 Регулярность
323 Функция нерегулярна.
324 Аргументы
326 a слово
327 n длина a в машинных словах
328 size_t wwNAF (word naf[], const word a[], size_t n, size_t w)
330 В [2n + 1]naf помещается кодированное представление оптимальной
331 знаковой формы (NAF) слова [n]a. Рассчитывается оконная NAF с размером
332 окна w.
333 Прим.
335 NAF(a, w) представляет собой последовательность символов (a_0,
336 a_1,..., a_{l-1}) такую, что
337 • a_i ∈ {0, ± 1, ± 3, ..., ± 2^{w-1} - 1};
339 • если a != 0, то a_{l-1} != 0;
341 • a как число равняется \sum {i=0}^{l-1} a_i 2^i;
343 • среди любых w последовательных символов a_i только один
345 ненулевой.
346 Известно, что l - длина NAF - не превосходит wwBitSize(a) + 1.
348 Кодирование символов состоит в следующем (<b> -- двоичная запись
350 числа b):
351 • нулевые a_i представляются одним двоичным символом 0;
353 • положительные a_i представляются w двоичными символами 0<a_i>;
355 • отрицательные a_i представляются w двоичными символами 1<|a_i|>;
357 • кодированное представление - это конкатенация кода a_{l-1}
359 (первые символы), ...., кода a_1, кода a_0 (последние символы).
360 Для кодирования w последовательных элементов a_i потребуется не
362 более (w - 1) * 1 + 1 * w = 2 * w - 1 битов. Поэтому при w <
363 B_PER_W для хранения всего кодового представления потребуется не
364 более 2 * n + 1 слов.
365 Если при расчете NAF получен суффикс α, 0,..., 0, 1, в котором w -
367 1 нулей и α < 0, то этот суффикс заменяется на β, 0,..., 0, 1, в
368 котором w - 2 нулей и β = 2^{w - 1} + α > 0. Суффиксы описывают
369 одинаковые числа: 2^w + α = 2^{w - 1} + β. Длина второго суффикса и
370 соответствующей NAF на единицу меньше.
371 Предусловие
373 2 <= w < B_PER_W.
374 Буфер naf не пересекается с буфером a.
376 Возвращает
378 Размер naf (число символов l).
379 Регулярность
381 Функция нерегулярна.
382 Аргументы
384 naf знаковая форма
385 a слово
386 n длина a в машинных словах
387 w длина окна
388 size_t wwOctetSize (const word a[], size_t n)
390 Определяется размер значащей части слова [n]a. Размер полагается равным
391 индексу последнего ненулевого октета, увеличенному на единицу.
392 Прим.
394 Размер пустого (n == 0) или нулевого слов равняется 0.
395 Регулярность
397 Функция нерегулярна.
398 Аргументы
400 a слово
401 n длина a в машинных словах
402 void wwRepW (word a[], size_t n, register word w)
404 Всем машинным словам [n]a присваивается значение w:
405 a[0] <- w, a[1] <- w, ..., a[n - 1] <- w.
407 Предусловие
410 n > 0 или w == 0.
411 Аргументы
413 a слово
414 n длина a в машинных словах
415 w значение
416 void wwSetBit (word a[], size_t pos, register bool_t val)
418 В слове a разряду с номером pos присваивается значение val.
419 Предусловие
421 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
422 val == FALSE || val == TRUE.
424 Аргументы
426 a обрабатываемое слово
427 pos номер разряда
428 val устанавливаемое значение
429 void wwSetBits (word a[], size_t pos, size_t width, register word val)
431 В слове a определяется разряды с номерами pos,..., pos + width - 1
432 устанавливаются равными последовательным разрядам val (от младшего к
433 старшему).
434 Предусловие
436 По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
437 width <= B_PER_W.
439 Аргументы
441 a слово
442 pos номер первого разряда
443 width число разрядов
444 val значение разрядов
445 void wwSetW (word a[], size_t n, register word w)
447 Слову [n]a присваивается значение w, которое является машинным словом:
448 a[0] <- w, a[1] <- 0, ..., a[n - 1] <- 0.
450 Предусловие
453 n > 0 или w == 0.
454 Аргументы
456 a слово
457 n длина a в машинных словах
458 w значение
459 void wwSetZero (word a[], size_t n)
461 Слово [n]a обнуляется:
462 a <- 0.
464 Аргументы
467 a слово
468 n длина a в машинных словах
469 void wwShHi (word a[], size_t n, size_t shift)
471 Слово [n]a сдвигается на shift позиций в сторону последних разрядов.
472 Освободившиеся разряды заполняются нулями.
473 Прим.
475 При интерпретации слов как чисел сдвиг означает умножение на число
476 2^shift с приведением результата mod 2^{n * B_PER_W}.
477 Аргументы
479 a сдвигаемое слово
480 n длина a в машинных словах
481 shift величина сдвига
482 word wwShHiCarry (word a[], size_t n, size_t shift, word carry)
484 Слово [n]a сдвигается на shift позиций в сторону последних разрядов.
485 Освободившиеся разряды заполняются разрядами carry.
486 Возвращает
488 Машинное слово, составленное из вытесненных последними разрядов.
489 Аргументы
491 a сдвигаемое слово
492 n длина a в машинных словах
493 shift величина сдвига
494 carry машинное слово заема
495 void wwShLo (word a[], size_t n, size_t shift)
497 Слово [n]a сдвигается на shift позиций в сторону первых разрядов.
498 Освободившиеся разряды заполняются нулями.
499 Прим.
501 При интерпретации слов как чисел сдвиг означает деление на число
502 2^shift с приведением результата mod 2^{n * B_PER_W}.
503 Аргументы
505 a сдвигаемое слово
506 n длина a в машинных словах
507 shift величина сдвига
508 word wwShLoCarry (word a[], size_t n, size_t shift, word carry)
510 Слово [n]a сдвигается на shift позиций в сторону первых разрядов.
511 Освободившиеся разряды заполняются разрядами carry.
512 Возвращает
514 Машинное слово, составленное из вытесненных последними разрядов.
515 Аргументы
517 a сдвигаемое слово
518 n длина a в машинных словах
519 shift величина сдвига
520 carry машинное слово заема
521 void wwSwap (word a[], word b[], size_t n)
523 Cлова [n]a и [n]b меняются местами:
524 a <-> b.
526 Предусловие
529 Буфер b не пересекается с буфером a.
530 Аргументы
532 a первое слово
533 b второе слово
534 n длина a и b в машинных словах
535 bool_t wwTestBit (const word a[], size_t pos)
537 В слове a определяется разряд с номером pos.
538 Предусловие
540 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
541 Возвращает
543 TRUE, если бит ненулевой, и FALSE в противном случае.
544 Аргументы
546 a слово
547 pos номер разряда
548 void wwTrimHi (word a[], size_t n, size_t pos)
550 В слове [n]a обнуляются разряды с номерами pos, pos + 1,...., n *
551 B_PER_W - 1.
552 Прим.
554 При pos >= n * B_PER_W никаких действий не выполняется.
555 При интерпретации слов как чисел отбрасывание разрядов означает
557 приведение mod 2^pos.
558 Аргументы
560 a обрабатываемое слово
561 n длина a в машинных словах
562 pos номер первого обнуляемого разряда
563 void wwTrimLo (word a[], size_t n, size_t pos)
565 В слове [n]a обнуляются разряды с номерами 0, 1,..., min(pos, n *
566 B_PER_W) - 1.
567 Аргументы
569 a обрабатываемое слово
570 n длина a в машинных словах
571 pos граница обнуляемых разрядов
572 size_t wwWordSize (const word a[], size_t n)
574 Определяется размер значащей части слова [n]a. Размер полагается равным
575 индексу последнего ненулевого машинного слова, увеличенному на единицу.
576 Прим.
578 Размер пустого (n == 0) или нулевого слов равняется 0.
579 Регулярность
581 Функция нерегулярна.
582 Аргументы
584 a слово
585 n длина a в машинных словах
586 void wwXor (word c[], const word a[], const word b[], size_t n)
588 Определяется поразрядная по модулю 2 сумма [n]с слов [n]a и [n]b:
589 c <- a ^ b.
591 Предусловие
594 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
595 b.
596 Аргументы
598 c сумма
599 a первое слагаемое
600 b второе слагаемое
601 n длина a и b в машинных словах
602 void wwXor2 (word b[], const word a[], size_t n)
604 К слову [n]b добавляется слово [n]a. Сложение выполняется поразрядно по
605 модулю 2:
606 b <- a ^ b.
608 Предусловие
611 Буфер b либо не пересекается, либо совпадает с буфером a.
612 Аргументы
614 b второе слагаемое / сумма
615 a первое слагаемое
616 n длина a в машинных словах
617
619 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
620Библиотека Bee2 Пт 23 Июн 2023 ww.h(3)