1ww.h(3) Library Functions Manual ww.h(3)
2
3
4
6 ww.h - Слова конечной длины
7
8
10 #include 'bee2/defs.h'
11 #include 'bee2/core/safe.h'
12 #include 'bee2/core/u32.h'
13
14
15 Макросы
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
25 Функции
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
93 Двоичное слово задается массивом машинных слов: word w[n].
94
95 Разряды слова w[0] нумеруются от 0 (младший) до B_PER_W - 1 (старший),
96 разряды w[1] -- от B_PER_W (младший) до 2 * B_PER_W - 1 (старший) и
97 т.д.
98
99 Запись [n]w означает, что слово w состоит из n машинных слов.
100
101 Предусловие
102 Все входные указатели действительны.
103
104 В функциях работы со словами по адресам памяти для слов
105 зарезервировано ясное из конекста либо уточняемое в описаниях
106 функций число машинных слов.
107
109 #define wwIsDisjoint(a, b, n) memIsDisjoint(a, b, O_OF_W(n))
110 Буферы слов [n]a и [n]b не пересекаются?
111
112 #define wwIsDisjoint2(a, n, b, m) memIsDisjoint2(a, O_OF_W(n), b,
113 O_OF_W(m))
114 Буферы слов [n]a и [m]b не пересекаются?
115
116 #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
120 #define wwIsSameOrDisjoint(a, b, n) memIsSameOrDisjoint(a, b, O_OF_W(n))
121 Буферы слов [n]a и [n]b совпадают или не пересекаются?
122
123 #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
131 Прим.
132 Размер пустого (n == 0) или нулевого слов равняется 0.
133
134 Если wwBitSize(a, n) == m > 0, то для a как числа выполняется 2^{m
135 - 1} < a <= 2^m - 1.
136
137 Возвращает
138 Размер значащей части.
139
140 Регулярность
141 Функция нерегулярна.
142
143 Аргументы
144 a слово
145 n длина a в машинных словах
146
147 int wwCmp (const word a[], const word b[], size_t n)
148 Cлова [n]a и [n]b сравниваются обратно-лексикографически.
149
150 Прим.
151 a > b, если a[n - 1] == b[n - 1],..., a[i] == b[i], a[i] > b[i].
152
153 Возвращает
154 1, если a > b, или -1, если a < b, или 0, если a == b.
155
156 Регулярность
157 Имеется ускоренная нерегулярная редакция.
158
159 Аргументы
160 a первое слово
161 b второе слово
162 n длина a и b в машинных словах
163
164 int wwCmp2 (const word a[], size_t n, const word b[], size_t m)
165 Cлова [n]a и [m]b сравниваются обратно-лексикографически (см. wwCmp())
166 после дополнения нулями до слов одинаковой длины.
167
168 Возвращает
169 1, если a > b, или -1, если a < b, или 0, если a == b.
170
171 Регулярность
172 Имеется ускоренная нерегулярная редакция.
173
174 Аргументы
175 a первое слово
176 n длина a в машинных словах
177 b второе слово
178 m длина b в машинных словах
179
180 int wwCmpW (const word a[], size_t n, register word w)
181 Слово [n]a сравнивается с машинным словом w.
182
183 Возвращает
184 1, если a > w, или -1, если a < w, или 0, если a == w.
185
186 Регулярность
187 Имеется ускоренная нерегулярная редакция.
188
189 Аргументы
190 a сравниваемое слово
191 n длина a в машинных словах
192 w машинное слово
193
194 void wwCopy (word b[], const word a[], size_t n)
195 Cлово [n]a переписывается в [n]b:
196
197 b <- a.
198
199
200 Предусловие
201 Буфер b либо не пересекается, либо совпадает с буфером a.
202
203 Аргументы
204 b приемник
205 a источник
206 n длина a в машинных словах
207
208 bool_t wwEq (const word a[], const word b[], size_t n)
209 Проверяется совпадение слов [n]a и [n]b.
210
211 Возвращает
212 Признак сопадения.
213
214 Регулярность
215 Имеется ускоренная нерегулярная редакция.
216
217 Аргументы
218 a первое слово
219 b второе слово
220 n длина a и b в машинных словах
221
222 void wwFlipBit (word a[], size_t pos)
223 В слове a инвертируется разряд с номером pos.
224
225 Предусловие
226 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
227
228 Аргументы
229 a слово
230 pos номер разряда
231
232 word wwGetBits (const word a[], size_t pos, size_t width)
233 В слове a определяется разряды с номерами pos,..., pos + width - 1.
234
235 Предусловие
236 По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
237
238 width <= B_PER_W.
239
240 Возвращает
241 Машинное слово, составленное из разрядов a с номерами pos
242 (младший), pos + 1,..., pos + width -1 (старший).
243
244 Аргументы
245 a слово
246 pos номер первого разряда
247 width число разрядов
248
249 size_t wwHiZeroBits (const word a[], size_t n)
250 Определяется длина серии из нулевых битов в конце слова [n]a.
251
252 Возвращает
253 Длина серии.
254
255 Регулярность
256 Функция нерегулярна.
257
258 Аргументы
259 a слово
260 n длина a в машинных словах
261
262 bool_t wwIsRepW (const word a[], size_t n, register word w)
263 Проверяется, что все машинные слова [n]a принимают значение w:
264
265 a[0] == w && a[1] == w && ... && a[n - 1] == w?
266
267
268 Прим.
269 В пустом слове (n == 0) повторяется значение 0.
270
271 Возвращает
272 TRUE, если a составлено из w, и FALSE в противном случае.
273
274 Регулярность
275 Имеется ускоренная нерегулярная редакция.
276
277 Аргументы
278 a проверяемое слово
279 n длина a в машинных словах
280 w значение
281
282 bool_t wwIsW (const word a[], size_t n, register word w)
283 Проверяется, что слово [n]a принимает значение w, которое является
284 машинным словом:
285
286 a[0] == w && a[1] == ... == a[n - 1] == 0?
287
288
289 Прим.
290 Пустое слово (n == 0) принимает значение 0.
291
292 Возвращает
293 TRUE, если a = w, и FALSE в противном случае.
294
295 Регулярность
296 Имеется ускоренная нерегулярная редакция.
297
298 Аргументы
299 a проверяемое слово
300 n длина a в машинных словах
301 w значение
302
303 bool_t wwIsZero (const word a[], size_t n)
304 Проверяется, что слово [n]a нулевое.
305
306 Возвращает
307 TRUE, если a - нулевое, и FALSE в противном случае.
308
309 Регулярность
310 Имеется ускоренная нерегулярная редакция.
311
312 Аргументы
313 a проверяемое слово
314 n длина a в машинных словах
315
316 size_t wwLoZeroBits (const word a[], size_t n)
317 Определяется длина серии из нулевых битов в начале слова [n]a.
318
319 Возвращает
320 Длина серии.
321
322 Регулярность
323 Функция нерегулярна.
324
325 Аргументы
326 a слово
327 n длина a в машинных словах
328
329 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
334 Прим.
335 NAF(a, w) представляет собой последовательность символов (a_0,
336 a_1,..., a_{l-1}) такую, что
337
338 • a_i ∈ {0, ± 1, ± 3, ..., ± 2^{w-1} - 1};
339
340 • если a != 0, то a_{l-1} != 0;
341
342 • a как число равняется \sum {i=0}^{l-1} a_i 2^i;
343
344 • среди любых w последовательных символов a_i только один
345 ненулевой.
346
347 Известно, что l - длина NAF - не превосходит wwBitSize(a) + 1.
348
349 Кодирование символов состоит в следующем (<b> -- двоичная запись
350 числа b):
351
352 • нулевые a_i представляются одним двоичным символом 0;
353
354 • положительные a_i представляются w двоичными символами 0<a_i>;
355
356 • отрицательные a_i представляются w двоичными символами 1<|a_i|>;
357
358 • кодированное представление - это конкатенация кода a_{l-1}
359 (первые символы), ...., кода a_1, кода a_0 (последние символы).
360
361 Для кодирования w последовательных элементов a_i потребуется не
362 более (w - 1) * 1 + 1 * w = 2 * w - 1 битов. Поэтому при w <
363 B_PER_W для хранения всего кодового представления потребуется не
364 более 2 * n + 1 слов.
365
366 Если при расчете 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
372 Предусловие
373 2 <= w < B_PER_W.
374
375 Буфер naf не пересекается с буфером a.
376
377 Возвращает
378 Размер naf (число символов l).
379
380 Регулярность
381 Функция нерегулярна.
382
383 Аргументы
384 naf знаковая форма
385 a слово
386 n длина a в машинных словах
387 w длина окна
388
389 size_t wwOctetSize (const word a[], size_t n)
390 Определяется размер значащей части слова [n]a. Размер полагается равным
391 индексу последнего ненулевого октета, увеличенному на единицу.
392
393 Прим.
394 Размер пустого (n == 0) или нулевого слов равняется 0.
395
396 Регулярность
397 Функция нерегулярна.
398
399 Аргументы
400 a слово
401 n длина a в машинных словах
402
403 void wwRepW (word a[], size_t n, register word w)
404 Всем машинным словам [n]a присваивается значение w:
405
406 a[0] <- w, a[1] <- w, ..., a[n - 1] <- w.
407
408
409 Предусловие
410 n > 0 или w == 0.
411
412 Аргументы
413 a слово
414 n длина a в машинных словах
415 w значение
416
417 void wwSetBit (word a[], size_t pos, register bool_t val)
418 В слове a разряду с номером pos присваивается значение val.
419
420 Предусловие
421 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
422
423 val == FALSE || val == TRUE.
424
425 Аргументы
426 a обрабатываемое слово
427 pos номер разряда
428 val устанавливаемое значение
429
430 void wwSetBits (word a[], size_t pos, size_t width, register word val)
431 В слове a определяется разряды с номерами pos,..., pos + width - 1
432 устанавливаются равными последовательным разрядам val (от младшего к
433 старшему).
434
435 Предусловие
436 По адресу a зарезервировано W_OF_B(pos + width) машинных слов.
437
438 width <= B_PER_W.
439
440 Аргументы
441 a слово
442 pos номер первого разряда
443 width число разрядов
444 val значение разрядов
445
446 void wwSetW (word a[], size_t n, register word w)
447 Слову [n]a присваивается значение w, которое является машинным словом:
448
449 a[0] <- w, a[1] <- 0, ..., a[n - 1] <- 0.
450
451
452 Предусловие
453 n > 0 или w == 0.
454
455 Аргументы
456 a слово
457 n длина a в машинных словах
458 w значение
459
460 void wwSetZero (word a[], size_t n)
461 Слово [n]a обнуляется:
462
463 a <- 0.
464
465
466 Аргументы
467 a слово
468 n длина a в машинных словах
469
470 void wwShHi (word a[], size_t n, size_t shift)
471 Слово [n]a сдвигается на shift позиций в сторону последних разрядов.
472 Освободившиеся разряды заполняются нулями.
473
474 Прим.
475 При интерпретации слов как чисел сдвиг означает умножение на число
476 2^shift с приведением результата mod 2^{n * B_PER_W}.
477
478 Аргументы
479 a сдвигаемое слово
480 n длина a в машинных словах
481 shift величина сдвига
482
483 word wwShHiCarry (word a[], size_t n, size_t shift, word carry)
484 Слово [n]a сдвигается на shift позиций в сторону последних разрядов.
485 Освободившиеся разряды заполняются разрядами carry.
486
487 Возвращает
488 Машинное слово, составленное из вытесненных последними разрядов.
489
490 Аргументы
491 a сдвигаемое слово
492 n длина a в машинных словах
493 shift величина сдвига
494 carry машинное слово заема
495
496 void wwShLo (word a[], size_t n, size_t shift)
497 Слово [n]a сдвигается на shift позиций в сторону первых разрядов.
498 Освободившиеся разряды заполняются нулями.
499
500 Прим.
501 При интерпретации слов как чисел сдвиг означает деление на число
502 2^shift с приведением результата mod 2^{n * B_PER_W}.
503
504 Аргументы
505 a сдвигаемое слово
506 n длина a в машинных словах
507 shift величина сдвига
508
509 word wwShLoCarry (word a[], size_t n, size_t shift, word carry)
510 Слово [n]a сдвигается на shift позиций в сторону первых разрядов.
511 Освободившиеся разряды заполняются разрядами carry.
512
513 Возвращает
514 Машинное слово, составленное из вытесненных последними разрядов.
515
516 Аргументы
517 a сдвигаемое слово
518 n длина a в машинных словах
519 shift величина сдвига
520 carry машинное слово заема
521
522 void wwSwap (word a[], word b[], size_t n)
523 Cлова [n]a и [n]b меняются местами:
524
525 a <-> b.
526
527
528 Предусловие
529 Буфер b не пересекается с буфером a.
530
531 Аргументы
532 a первое слово
533 b второе слово
534 n длина a и b в машинных словах
535
536 bool_t wwTestBit (const word a[], size_t pos)
537 В слове a определяется разряд с номером pos.
538
539 Предусловие
540 По адресу a зарезервировано W_OF_B(pos + 1) машинных слов.
541
542 Возвращает
543 TRUE, если бит ненулевой, и FALSE в противном случае.
544
545 Аргументы
546 a слово
547 pos номер разряда
548
549 void wwTrimHi (word a[], size_t n, size_t pos)
550 В слове [n]a обнуляются разряды с номерами pos, pos + 1,...., n *
551 B_PER_W - 1.
552
553 Прим.
554 При pos >= n * B_PER_W никаких действий не выполняется.
555
556 При интерпретации слов как чисел отбрасывание разрядов означает
557 приведение mod 2^pos.
558
559 Аргументы
560 a обрабатываемое слово
561 n длина a в машинных словах
562 pos номер первого обнуляемого разряда
563
564 void wwTrimLo (word a[], size_t n, size_t pos)
565 В слове [n]a обнуляются разряды с номерами 0, 1,..., min(pos, n *
566 B_PER_W) - 1.
567
568 Аргументы
569 a обрабатываемое слово
570 n длина a в машинных словах
571 pos граница обнуляемых разрядов
572
573 size_t wwWordSize (const word a[], size_t n)
574 Определяется размер значащей части слова [n]a. Размер полагается равным
575 индексу последнего ненулевого машинного слова, увеличенному на единицу.
576
577 Прим.
578 Размер пустого (n == 0) или нулевого слов равняется 0.
579
580 Регулярность
581 Функция нерегулярна.
582
583 Аргументы
584 a слово
585 n длина a в машинных словах
586
587 void wwXor (word c[], const word a[], const word b[], size_t n)
588 Определяется поразрядная по модулю 2 сумма [n]с слов [n]a и [n]b:
589
590 c <- a ^ b.
591
592
593 Предусловие
594 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
595 b.
596
597 Аргументы
598 c сумма
599 a первое слагаемое
600 b второе слагаемое
601 n длина a и b в машинных словах
602
603 void wwXor2 (word b[], const word a[], size_t n)
604 К слову [n]b добавляется слово [n]a. Сложение выполняется поразрядно по
605 модулю 2:
606
607 b <- a ^ b.
608
609
610 Предусловие
611 Буфер b либо не пересекается, либо совпадает с буфером a.
612
613 Аргументы
614 b второе слагаемое / сумма
615 a первое слагаемое
616 n длина a в машинных словах
617
619 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
620
621
622
623Библиотека Bee2 Ср 19 Июл 2023 00:00:00 ww.h(3)