1
/*
2
*******************************************************************************
3
\file ww.c
4
\brief Arbitrary length words
5
\project bee2 [cryptographic library]
6
\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}]
7
\created 2012.04.18
8
\version 2016.05.27
9
\license This program is released under the GNU General Public License 
10
version 3. See Copyright Notices in bee2/info.h.
11
*******************************************************************************
12
*/
13

14
#include "bee2/core/mem.h"
15
#include "bee2/core/util.h"
16
#include "bee2/core/word.h"
17
#include "bee2/math/ww.h"
18

19
/*
20
*******************************************************************************
21
Копирование, логические операции
22
*******************************************************************************
23
*/
24

25 1
void wwCopy(word b[], const word a[], size_t n)
26
{
27 1
	ASSERT(wwIsSameOrDisjoint(a, b, n));
28 1
	while (n--)
29 1
		b[n] = a[n];
30
}
31

32 1
void wwSwap(word a[], word b[], size_t n)
33
{
34 1
	ASSERT(wwIsDisjoint(a, b, n));
35 1
	while (n--)
36 1
		SWAP(a[n], b[n]);
37
}
38

39 1
bool_t SAFE(wwEq)(const word a[], const word b[], size_t n)
40
{
41 1
	register word diff = 0;
42 1
	ASSERT(wwIsValid(a, n) && wwIsValid(b, n));
43 1
	while (n--)
44 1
		diff |= a[n] ^ b[n];
45 1
	return wordEq(diff, 0);
46
}
47

48 1
bool_t FAST(wwEq)(const word a[], const word b[], size_t n)
49
{
50 1
	ASSERT(wwIsValid(a, n) && wwIsValid(b, n));
51 1
	while (n--)
52 1
		if (a[n] != b[n])
53 0
			return FALSE;
54 1
	return TRUE;
55
}
56

57 1
int SAFE(wwCmp)(const word a[], const word b[], size_t n)
58
{
59 1
	register word less = 0;
60 1
	register word greater = 0;
61 1
	ASSERT(wwIsValid(a, n) && wwIsValid(b, n));
62 1
	while (n--)
63
	{
64 1
		less |= ~greater & wordLess01(a[n], b[n]);
65 1
		greater |= ~less & wordGreater01(a[n], b[n]);
66
	}
67 1
	return (wordEq(less, 0) - 1) | wordNeq(greater, 0);
68
}
69

70 1
int FAST(wwCmp)(const word a[], const word b[], size_t n)
71
{
72 1
	ASSERT(wwIsValid(a, n) && wwIsValid(b, n));
73 1
	while (n--)
74 1
		if (a[n] > b[n])
75 1
			return 1;
76 1
		else if (a[n] < b[n])
77 1
			return -1;
78 1
	return 0;
79
}
80

81 1
int SAFE(wwCmp2)(const word a[], size_t n, const word b[], size_t m)
82
{
83
	register int ret;
84 1
	ASSERT(wwIsValid(a, n) && wwIsValid(b, m));
85 1
	if (n > m)
86
	{
87 1
		register int z = wwIsZero(a + m, n - m);
88 1
		ret = wwCmp(a, b, m);
89 1
		ret = -z & ret | (z - 1) & 1;
90 1
		z = 0;
91
	}
92 1
	else if (n < m)
93
	{
94 1
		register int z = wwIsZero(b + n, m - n);
95 1
		ret = wwCmp(a, b, n);
96 1
		ret = -z & ret | (z - 1) & -1;
97 1
		z = 0;
98
	}
99
	else
100 1
		ret = wwCmp(a, b, n);
101 1
	return ret;
102
}
103

104 0
int FAST(wwCmp2)(const word a[], size_t n, const word b[], size_t m)
105
{
106 0
	ASSERT(wwIsValid(a, n) && wwIsValid(b, m));
107 0
	if (n > m)
108 0
		return FAST(wwIsZero)(a + m, n - m) ? FAST(wwCmp)(a, b, m) : 1;
109 0
	else if (n < m)
110 0
		return FAST(wwIsZero)(b + n, m - n) ? FAST(wwCmp)(a, b, n) : -1;
111 0
	return FAST(wwCmp)(a, b, m);
112
}
113

114 1
int SAFE(wwCmpW)(const word a[], size_t n, register word w)
115
{
116
	register int ret;
117 1
	ASSERT(wwIsValid(a, n));
118 1
	if (n == 0)
119 0
		ret = wordEq(w, 0) - 1;
120
	else
121
	{
122 1
		register int z = wwIsZero(a + 1, n - 1);
123 1
		ret = -wordLess(a[0], w) & -1 | -wordGreater(a[0], w) & 1;
124 1
		ret = -z & ret | (z - 1) & 1;
125 1
		z = 0;
126
	}
127 1
	w = 0;
128 1
	return ret;
129
}
130

131 0
int FAST(wwCmpW)(const word a[], size_t n, register word w)
132
{
133
	register int cmp;
134 0
	ASSERT(wwIsValid(a, n));
135 0
	if (n == 0)
136 0
		cmp = (w ? -1 : 0);
137
	else
138
	{
139 0
		cmp = 0;
140 0
		while (--n && cmp == 0)
141 0
			cmp = (a[n] == 0 ? 0 : 1);
142 0
		if (cmp == 0)
143
		{
144 0
			if (a[0] < w)
145 0
				cmp = -1;
146 0
			else if (a[0] > w)
147 0
				cmp = 1;
148
		}
149
	}
150 0
	w = 0;
151 0
	return cmp;
152
}
153

154 1
void wwXor(word c[], const word a[], const word b[], size_t n)
155
{
156 1
	ASSERT(wwIsSameOrDisjoint(a, c, n));
157 1
	ASSERT(wwIsSameOrDisjoint(b, c, n));
158 1
	while (n--)
159 1
		c[n] = a[n] ^ b[n];
160
}
161

162 1
void wwXor2(word b[], const word a[], size_t n)
163
{
164 1
	ASSERT(wwIsSameOrDisjoint(a, b, n));
165 1
	while (n--)
166 1
		b[n] ^= a[n];
167
}
168

169 1
void wwSetZero(word a[], size_t n)
170
{
171 1
	ASSERT(wwIsValid(a, n));
172 1
	while (n--)
173 1
		a[n] = 0;
174
}
175

176 1
void wwSetW(word a[], size_t n, register word w)
177
{
178 1
	ASSERT(wwIsValid(a, n));
179 1
	if (n)
180 1
		for (a[0] = w; --n; a[n] = 0);
181
	else
182 0
		ASSERT(w == 0);
183 1
	w = 0;
184
}
185

186 1
void wwRepW(word a[], size_t n, register word w)
187
{
188 1
	ASSERT(wwIsValid(a, n));
189 1
	if (n)
190 1
		for (; n--; a[n] = w);
191
	else
192 0
		ASSERT(w == 0);
193 1
	w = 0;
194
}
195

196 1
bool_t SAFE(wwIsZero)(const word a[], size_t n)
197
{
198 1
	register word diff = 0;
199 1
	ASSERT(wwIsValid(a, n));
200 1
	while (n--)
201 1
		diff |= a[n];
202 1
	return wordEq(diff, 0);
203
}
204

205 1
bool_t FAST(wwIsZero)(const word a[], size_t n)
206
{
207 1
	ASSERT(wwIsValid(a, n));
208 1
	while (n--)
209 1
		if (a[n])
210 0
			return FALSE;
211 1
	return TRUE;
212
}
213

214 1
bool_t SAFE(wwIsW)(const word a[], size_t n, register word w)
215
{
216
	register bool_t ret;
217 1
	ASSERT(wwIsValid(a, n));
218 1
	if (n == 0)
219 0
		ret = wordEq(w, 0);
220
	else
221
	{
222 1
		ret = wordEq(a[0], w);
223 1
		while (--n)
224 1
			ret &= wordEq(a[n], 0);
225
	}
226 1
	w = 0;
227 1
	return ret;
228
}
229

230 0
bool_t FAST(wwIsW)(const word a[], size_t n, register word w)
231
{
232
	register bool_t ret;
233 0
	ASSERT(wwIsValid(a, n));
234 0
	if (n == 0)
235 0
		ret = (w == 0);
236
	else
237
	{
238 0
		ret = (a[0] == w);
239 0
		while (ret && --n)
240 0
			ret = (a[n] == 0);
241
	}
242 0
	w = 0;
243 0
	return ret;
244
}
245

246 1
bool_t SAFE(wwIsRepW)(const word a[], size_t n, register word w)
247
{
248
	register bool_t ret;
249 1
	ASSERT(wwIsValid(a, n));
250 1
	if (n == 0)
251 0
		ret = wordEq(w, 0);
252
	else
253
	{
254 1
		ret = wordEq(a[0], w);
255 1
		while (--n)
256 1
			ret &= wordEq(a[n], w);
257
	}
258 1
	w = 0;
259 1
	return ret;
260
}
261

262 0
bool_t FAST(wwIsRepW)(const word a[], size_t n, register word w)
263
{
264
	register bool_t ret;
265 0
	ASSERT(wwIsValid(a, n));
266 0
	if (n == 0)
267 0
		ret = (w == 0);
268
	else
269
	{
270
		do
271 0
			ret = (a[--n] == w);
272 0
		while (ret && n);
273
	}
274 0
	w = 0;
275 0
	return ret;
276
}
277

278 1
size_t wwWordSize(const word a[], size_t n)
279
{
280 1
	ASSERT(wwIsValid(a, n));
281 1
	while (n-- && a[n] == 0);
282 1
	return n + 1;
283
}
284

285 1
size_t wwOctetSize(const word a[], size_t n)
286
{
287 1
	ASSERT(wwIsValid(a, n));
288 1
	while (n-- && a[n] == 0);
289 1
	if (n == SIZE_MAX)
290 0
		return 0;
291
	{
292 1
		size_t pos = O_PER_W - 1;
293 1
		word mask = (word)0xFF << 8 * pos;
294 1
		while ((a[n] & mask) == 0)
295 1
			--pos, mask >>= 8;
296 1
		return n * O_PER_W + pos + 1;
297
	}
298
}
299

300
/*
301
*******************************************************************************
302
Операции с отдельными битами, кодирование
303

304
\remark В wwSetBit() использован трюк из работы
305
	Andersen S.A. Bit Twidding Hacks. Avail. at:
306
	http://graphics.stanford.edu/~seander/bithacks.html, 1997-2005
307
[conditionally set or clear bits without branching].
308
*******************************************************************************
309
*/
310

311 1
bool_t wwTestBit(const word a[], size_t pos)
312
{
313 1
	ASSERT(wwIsValid(a, W_OF_B(pos + 1)));
314 1
	return (a[pos / B_PER_W] & WORD_BIT_POS(pos % B_PER_W)) != 0;
315
}
316

317 1
word wwGetBits(const word a[], size_t pos, size_t width)
318
{
319
	register word ret;
320 1
	size_t n = pos / B_PER_W;
321 1
	ASSERT(wwIsValid(a, W_OF_B(pos + width)));
322 1
	pos %= B_PER_W;
323
	// биты a[n]
324 1
	ret = a[n] >> pos;
325
	// биты a[n + 1]
326 1
	if (pos + width > B_PER_W)
327 1
		ret |= a[n + 1] << (B_PER_W - pos);
328
	// только width битов
329 1
	ASSERT(width <= B_PER_W);
330 1
	if (width < B_PER_W)
331 1
		ret &= WORD_BIT_POS(width) - 1;
332 1
	return ret;
333
}
334

335 1
void wwSetBit(word a[], size_t pos, register bool_t val)
336
{
337
	register word f;
338 1
	ASSERT(wwIsValid(a, W_OF_B(pos + 1)));
339 1
	ASSERT(val == TRUE || val == FALSE);
340 1
	f = WORD_0 - (word)val;
341 1
	a[pos / B_PER_W] ^= (f ^ a[pos / B_PER_W]) & WORD_BIT_POS(pos % B_PER_W);
342 1
	f = 0;
343
}
344

345 1
void wwSetBits(word a[], size_t pos, size_t width, register word val)
346
{
347 1
	word mask = WORD_MAX;
348 1
	size_t n = pos / B_PER_W;
349 1
	ASSERT(wwIsValid(a, W_OF_B(pos + width)));
350 1
	ASSERT(width <= B_PER_W);
351
	// маска
352 1
	if (width < B_PER_W)
353
	{
354 1
		mask <<= B_PER_W - width;
355 1
		mask >>= B_PER_W - width;
356
	}
357
	// биты a[n]
358 1
	pos %= B_PER_W;
359 1
	a[n] &= ~(mask << pos);
360 1
	a[n] ^= (val & mask) << pos;
361
	// биты a[n + 1]
362 1
	if (pos + width > B_PER_W)
363
	{
364 0
		a[n + 1] &= mask << pos;
365 0
		a[n + 1] ^= (val & mask) >> (B_PER_W - pos);
366
	}
367
}
368

369 1
void wwFlipBit(word a[], size_t pos)
370
{
371 1
	ASSERT(wwIsValid(a, W_OF_B(pos + 1)));
372 1
	a[pos / B_PER_W] ^= WORD_BIT_POS(pos % B_PER_W);
373
}
374

375 1
size_t wwLoZeroBits(const word a[], size_t n)
376
{
377
	register size_t i;
378 1
	ASSERT(wwIsValid(a, n));
379
	// поиск младшего ненулевого машинного слова
380 1
	for (i = 0; i < n && a[i] == 0; ++i);
381
	// нулевое слово?
382 1
	if (i == n)
383 0
		return n * B_PER_W;
384
	// ...ненулевое
385 1
	return i * B_PER_W + wordCTZ(a[i]);
386
}
387

388 1
size_t wwHiZeroBits(const word a[], size_t n)
389
{
390 1
	register size_t i = n;
391 1
	ASSERT(wwIsValid(a, n));
392
	// поиск старшего ненулевого машинного слова
393 1
	while (i-- && a[i] == 0);
394
	// нулевое слово?
395 1
	if (i == SIZE_MAX)
396 0
		return n * B_PER_W;
397
	// ... ненулевое
398 1
	return (n - i - 1) * B_PER_W + wordCLZ(a[i]);
399
}
400

401 1
size_t wwBitSize(const word a[], size_t n)
402
{
403 1
	ASSERT(wwIsValid(a, n));
404 1
	return n * B_PER_W - wwHiZeroBits(a, n);
405
}
406

407 1
size_t wwNAF(word naf[], const word a[], size_t n, size_t w)
408
{
409 1
	const word next_bit = WORD_BIT_POS(w);
410 1
	const word hi_bit = next_bit >> 1;
411 1
	const word mask = hi_bit - 1;
412
	register word window;
413
	register word digit;
414 1
	register size_t naf_len = 0;
415 1
	register size_t naf_size = 0;
416 1
	register size_t a_len = wwBitSize(a, n);
417
	size_t i;
418
	// pre
419 1
	ASSERT(wwIsDisjoint2(a, n, naf, 2 * n + 1));
420 1
	ASSERT(2 <= w && w < B_PER_W);
421
	// naf <- 0
422 1
	wwSetZero(naf, 2 * n + 1);
423
	// a == 0?
424 1
	if (wwIsZero(a, n))
425 0
		return 0;
426
	// window <- a mod 2^w
427 1
	window = wwGetBits(a, 0, w);
428
	// расчет NAF
429 1
	for (i = w; window || i < a_len; ++i)
430
	{
431
		// ненулевой символ?
432 1
		if (window & 1)
433
		{
434
			// кодирование отрицательного символа
435 1
			if (window & hi_bit)
436
			{
437
				// модифицировать отрицательный символ суффикса NAF...
438 1
				if (i >= a_len)
439
					// ...сделать его положительным
440 1
					digit = window & mask,
441
					// window <- window - digit
442 1
					window = hi_bit;
443
				else
444
					// digit <- |window|
445 1
					digit = (0 - window) & mask,
446
					// digit <- 1||digit
447 1
					digit ^= hi_bit,
448
					// window <- window - digit
449 1
					window = next_bit;
450
			}
451
			else
452
				// кодирование положительного символа
453 1
				digit = window,
454
				// window <- window - digit
455 1
				window = 0;
456
			// запись ненулевого символа
457 1
			wwShHi(naf, W_OF_B(naf_len + w), w);
458 1
			wwSetBits(naf, 0, w, digit);
459 1
			naf_len += w;
460
		}
461
		else
462
			// кодирование нулевого символа
463 1
			wwShHi(naf, W_OF_B(++naf_len), 1);
464
		// увеличить размер naf
465 1
		++naf_size;
466
		// сдвиг окна
467 1
		window >>= 1;
468 1
		if (i < a_len)
469 1
			window += hi_bit * wwTestBit(a, i);
470
	}
471 1
	digit = window = 0;
472 1
	naf_len = a_len = 0;
473 1
	return naf_size;
474
}
475

476
/*
477
*******************************************************************************
478
Сдвиги и очистка
479

480
\todo Функции wwShLoCarry(), wwShHiCarry() перегружены. Оценить их
481
востребованность. Для размышления. В архитектуре i386 при сдвиге регистра
482
более чем на 1 позицию флаг переноса формально не определен.
483

484
\todo Проверить wwTrimLo().
485
*******************************************************************************
486
*/
487

488 1
void wwShLo(word a[], size_t n, size_t shift)
489
{
490 1
	ASSERT(wwIsValid(a, n));
491 1
	if (shift < B_PER_W * n)
492
	{
493 1
		size_t wshift = shift / B_PER_W, pos;
494
		// величина сдвига не кратна длине слова?
495 1
		if (shift %= B_PER_W)
496
		{
497
			// сдвиг всех слов, кроме последнего
498 1
			for (pos = 0; pos + wshift + 1 < n; pos++)
499 1
				a[pos] = a[pos + wshift] >> shift |
500 1
					a[pos + wshift + 1] << (B_PER_W - shift);
501
			// последнее слово
502 1
			ASSERT(pos + wshift < n);
503 1
			a[pos] = a[pos + wshift] >> shift;
504 1
			++pos;
505
		}
506
		// величина сдвига кратна длине слова
507 1
		else for (pos = 0; pos + wshift < n; pos++)
508 1
			a[pos] = a[pos + wshift];
509
		// обнуление последних слов
510 1
		for (; pos < n; a[pos++] = 0);
511
	}
512
	else
513 0
		wwSetZero(a, n);
514
}
515

516 1
word wwShLoCarry(word a[], size_t n, size_t shift, word carry)
517
{
518 1
	register word ret = 0;
519 1
	ASSERT(wwIsValid(a, n));
520 1
	if (shift < B_PER_W * (n + 1))
521
	{
522 1
		size_t wshift = shift / B_PER_W, pos;
523 1
		shift %= B_PER_W;
524
		// сохраняем вытесняемые разряды
525 1
		if (wshift)
526 0
			ret = a[wshift - 1] >> shift;
527
		// величина сдвига не кратна длине слова?
528 1
		if (shift)
529
		{
530
			// дополнительные вытесняемые разряды
531 1
			if (wshift < n)
532 1
				ret |= a[wshift] << (B_PER_W - shift);
533
			else
534 0
				ret |= carry << (B_PER_W - shift);
535
			// сдвиг всех слов, кроме последнего
536 1
			for (pos = 0; pos + wshift + 1 < n; pos++)
537 1
				a[pos] = a[pos + wshift] >> shift |
538 1
					a[pos + wshift + 1] << (B_PER_W - shift);
539
			// предпоследнее слово
540 1
			if (pos + wshift < n)
541
			{
542 1
				a[pos] = a[pos + wshift] >> shift | carry << (B_PER_W - shift);
543 1
				++pos;
544
			}
545
		}
546
		// величина сдвига кратна длине слова
547
		else
548
		{
549 0
			for (pos = 0; pos + wshift < n; pos++)
550 0
				a[pos] = a[pos + wshift];
551
		}
552
		// последние слова
553 1
		if (pos < n)
554 0
			a[pos++] = carry >> shift;
555 1
		for (; pos < n; a[pos++] = 0);
556
	}
557
	else
558
	{
559 0
		wwSetZero(a, n);
560 0
		shift -= B_PER_W * (n + 1);
561 0
		if (shift < B_PER_W)
562 0
			ret = carry >> shift;
563
	}
564 1
	return ret;
565
}
566

567 1
void wwShHi(word a[], size_t n, size_t shift)
568
{
569 1
	ASSERT(wwIsValid(a, n));
570 1
	if (shift < B_PER_W * n)
571
	{
572 1
		size_t wshift = shift / B_PER_W, pos;
573
		// величина сдвига не кратна длине слова?
574 1
		if (shift %= B_PER_W)
575
		{
576
			// сдвиг всех слов, кроме первого
577 1
			for (pos = n - 1; pos > wshift; pos--)
578 1
				a[pos] = a[pos - wshift] << shift |
579 1
					a[pos - wshift - 1] >> (B_PER_W - shift);
580
			// первое слово
581 1
			a[pos] = a[pos - wshift] << shift;
582 1
			--pos;
583
		}
584
		// величина сдвига кратна длине слова
585 1
		else for (pos = n - 1; pos + 1 > wshift; pos--)
586 1
				a[pos] = a[pos - wshift];
587
		// обнуление первых слов
588 1
		for (; pos != SIZE_MAX; a[pos--] = 0);
589
	}
590
	else
591 0
		wwSetZero(a, n);
592
}
593

594 0
word wwShHiCarry(word a[], size_t n, size_t shift, word carry)
595
{
596 0
	register word ret = 0;
597 0
	ASSERT(wwIsValid(a, n));
598 0
	if (shift < B_PER_W * (n + 1))
599
	{
600 0
		size_t wshift = shift / B_PER_W;
601
		size_t pos;
602 0
		shift %= B_PER_W;
603
		// сохраняем вытесняемые разряды
604 0
		if (wshift)
605 0
			ret = a[n - wshift] << shift;
606
		// величина сдвига не кратна длине слова?
607 0
		if (shift)
608
		{
609
			// дополнительные вытесняемые разряды
610 0
			if (wshift < n)
611 0
				ret |= a[n - wshift - 1] >> (B_PER_W - shift);
612
			else
613 0
				ret |= carry >> (B_PER_W - shift);
614
			// сдвиг всех слов, кроме первого
615 0
			for (pos = n - 1; pos != SIZE_MAX && pos > wshift; pos--)
616 0
				a[pos] = a[pos - wshift] << shift | 
617 0
					a[pos - wshift - 1] >> (B_PER_W - shift);
618
			// второе слово
619 0
			if (pos != SIZE_MAX && pos + 1 > wshift)
620
			{
621 0
				a[pos] = a[pos - wshift] << shift | carry >> (B_PER_W - shift);
622 0
				--pos;
623
			}
624
		}
625
		// величина сдвига кратна длине слова
626
		else
627
		{
628 0
			for (pos = n - 1; pos != SIZE_MAX && pos + 1 > wshift; pos--)
629 0
				a[pos] = a[pos - wshift];
630
		}
631
		// первые слова
632 0
		if (pos != SIZE_MAX)
633 0
			a[pos--] = carry << shift;
634 0
		for (; pos != SIZE_MAX; a[pos--] = 0);
635
	}
636
	else
637
	{
638 0
		wwSetZero(a, n);
639 0
		shift -= B_PER_W * (n + 1);
640 0
		if (shift < B_PER_W)
641 0
			ret = carry << shift;
642

643
	}
644 0
	return ret;
645
}
646

647 0
void wwTrimLo(word a[], size_t n, size_t pos)
648
{
649 0
	size_t i = pos / B_PER_W;
650 0
	ASSERT(wwIsValid(a, n));
651 0
	if (i < n)
652
	{
653
		// очистить биты слова a[i]
654 0
		if (pos %= B_PER_W)
655 0
			a[i] >>= pos, a[i] <<= pos;
656
	}
657 0
	else if (i > n)
658 0
		i = n;
659
	// очистить остальные слова
660 0
	while (i)
661 0
		a[--i] = 0;
662
}
663

664 1
void wwTrimHi(word a[], size_t n, size_t pos)
665
{
666 1
	size_t i = pos / B_PER_W;
667 1
	ASSERT(wwIsValid(a, n));
668 1
	if (i < n)
669
	{
670 1
		pos = B_PER_W - pos % B_PER_W;
671
		// очистить биты слова a[i]
672 1
		if (pos == B_PER_W)
673 1
			a[i] = 0;
674
		else
675 1
			a[i] <<= pos, a[i] >>= pos;
676
		// очистить остальные слова
677 1
		while (++i < n)
678 1
			a[i] = 0;
679
	}
680
}

Read our documentation on viewing source code .

Loading