1 ```/* ``` 2 ```******************************************************************************* ``` 3 ```\file gf2.c ``` 4 ```\brief Binary fields ``` 5 ```\project bee2 [cryptographic library] ``` 6 ```\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}] ``` 7 ```\created 2012.04.17 ``` 8 ```\version 2015.11.03 ``` 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/blob.h" ``` 15 ```#include "bee2/core/mem.h" ``` 16 ```#include "bee2/core/stack.h" ``` 17 ```#include "bee2/core/util.h" ``` 18 ```#include "bee2/math/gf2.h" ``` 19 ```#include "bee2/math/pp.h" ``` 20 ```#include "bee2/math/ww.h" ``` 21 22 ```/* ``` 23 ```******************************************************************************* ``` 24 ```Ускоренные варианты ppRedTrinomial ``` 25 26 ```Предварительно рассчитываются числа bm, wm, bk, wk. ``` 27 28 ```gf2RedTrinomial0: bk == 0. ``` 29 ```gf2RedTrinomial1: bk != 0. ``` 30 ```******************************************************************************* ``` 31 ```*/ ``` 32 33 ```typedef struct ``` 34 ```{ ``` 35 ``` size_t m; /*< степень трехчлена */ ``` 36 ``` size_t k; /*< степень среднего монома */ ``` 37 ``` size_t l; /*< здесь должен быть 0 */ ``` 38 ``` size_t l1; /*< здесь должен быть 0 */ ``` 39 ``` size_t bm; /*< m % B_PER_W */ ``` 40 ``` size_t wm; /*< m / B_PER_W */ ``` 41 ``` size_t bk; /*< (m - k) % B_PER_W */ ``` 42 ``` size_t wk; /*< (m - k) / B_PER_W */ ``` 43 ```} gf2_trinom_st; ``` 44 45 0 ```static void gf2RedTrinomial0(word a[], size_t n, const gf2_trinom_st* p) ``` 46 ```{ ``` 47 ``` register word hi; ``` 48 ``` // pre ``` 49 0 ``` ASSERT(wwIsValid(a, 2 * n)); ``` 50 0 ``` ASSERT(memIsValid(p, sizeof(*p))); ``` 51 0 ``` ASSERT(p->m % 8 != 0); ``` 52 0 ``` ASSERT(p->m > p->k && p->k > 0); ``` 53 0 ``` ASSERT(p->m - p->k >= B_PER_W); ``` 54 0 ``` ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); ``` 55 0 ``` ASSERT(p->m == p->wm * B_PER_W + p->bm); ``` 56 0 ``` ASSERT(p->m == p->k + p->wk * B_PER_W + p->bk); ``` 57 0 ``` ASSERT(n == W_OF_B(p->m)); ``` 58 0 ``` ASSERT(p->bk == 0); ``` 59 ``` // обработать старшие слова ``` 60 0 ``` n *= 2; ``` 61 0 ``` while (--n > p->wm) ``` 62 ``` { ``` 63 0 ``` hi = a[n]; ``` 64 0 ``` a[n - p->wm - 1] ^= hi << (B_PER_W - p->bm); ``` 65 0 ``` a[n - p->wm] ^= hi >> p->bm; ``` 66 0 ``` a[n - p->wk] ^= hi; ``` 67 ``` } ``` 68 ``` // слово, на которое попадает моном x^m ``` 69 0 ``` ASSERT(n == p->wm); ``` 70 0 ``` hi = a[n] >> p->bm; ``` 71 0 ``` a[0] ^= hi; ``` 72 0 ``` hi <<= p->bm; ``` 73 0 ``` a[n - p->wk] ^= hi; ``` 74 0 ``` a[n] ^= hi; ``` 75 ``` // очистка ``` 76 0 ``` hi = 0; ``` 77 ```} ``` 78 79 1 ```static void gf2RedTrinomial1(word a[], size_t n, const gf2_trinom_st* p) ``` 80 ```{ ``` 81 ``` register word hi; ``` 82 ``` // pre ``` 83 1 ``` ASSERT(wwIsValid(a, 2 * n)); ``` 84 1 ``` ASSERT(memIsValid(p, sizeof(*p))); ``` 85 1 ``` ASSERT(p->m % 8 != 0); ``` 86 1 ``` ASSERT(p->m > p->k && p->k > 0); ``` 87 1 ``` ASSERT(p->m - p->k >= B_PER_W); ``` 88 1 ``` ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); ``` 89 1 ``` ASSERT(p->m == p->wm * B_PER_W + p->bm); ``` 90 1 ``` ASSERT(p->m == p->k + p->wk * B_PER_W + p->bk); ``` 91 1 ``` ASSERT(n == W_OF_B(p->m)); ``` 92 1 ``` ASSERT(p->bk != 0); ``` 93 ``` // обработать старшие слова ``` 94 1 ``` n *= 2; ``` 95 1 ``` while (--n > p->wm) ``` 96 ``` { ``` 97 1 ``` hi = a[n]; ``` 98 1 ``` a[n - p->wm - 1] ^= hi << (B_PER_W - p->bm); ``` 99 1 ``` a[n - p->wm] ^= hi >> p->bm; ``` 100 1 ``` a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); ``` 101 1 ``` a[n - p->wk] ^= hi >> p->bk; ``` 102 ``` } ``` 103 ``` // слово, на которое попадает моном x^m ``` 104 1 ``` ASSERT(n == p->wm); ``` 105 1 ``` hi = a[n] >> p->bm; ``` 106 1 ``` a[0] ^= hi; ``` 107 1 ``` hi <<= p->bm; ``` 108 1 ``` if (p->wk < n) ``` 109 1 ``` a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); ``` 110 1 ``` a[n - p->wk] ^= hi >> p->bk; ``` 111 1 ``` a[n] ^= hi; ``` 112 ``` // очистка ``` 113 1 ``` hi = 0; ``` 114 ```} ``` 115 116 ```/* ``` 117 ```******************************************************************************* ``` 118 ```Ускоренные варианты ppRedPentanomial ``` 119 120 ```Предварительно рассчитываются числа bm, wm, bk, wk, wl, bl, wl1, bl1. ``` 121 122 ```Набор (bm, bk, bl, bl1) не может быть нулевым -- соответствующий многочлен ``` 123 ```не является неприводимым. ``` 124 125 ```\todo 15 функций gf2RedPentanomial[bm|bk|bl|bl1]. ``` 126 ```******************************************************************************* ``` 127 ```*/ ``` 128 129 ```typedef struct ``` 130 ```{ ``` 131 ``` size_t m; /*< степень пятичлена */ ``` 132 ``` size_t k; /*< степень старшего из средних мономов */ ``` 133 ``` size_t l; /*< степень среднего из средних мономов */ ``` 134 ``` size_t l1; /*< степень младшего из средних мономов */ ``` 135 ``` size_t bm; /*< m % B_PER_W */ ``` 136 ``` size_t wm; /*< m / B_PER_W */ ``` 137 ``` size_t bk; /*< (m - k) % B_PER_W */ ``` 138 ``` size_t wk; /*< (m - k) / B_PER_W */ ``` 139 ``` size_t bl; /*< (m - l) % B_PER_W */ ``` 140 ``` size_t wl; /*< (m - l) / B_PER_W */ ``` 141 ``` size_t bl1; /*< (m - l1) % B_PER_W */ ``` 142 ``` size_t wl1; /*< (m - l1) / B_PER_W */ ``` 143 ```} gf2_pentanom_st; ``` 144 145 1 ```static void gf2RedPentanomial(word a[], size_t n, const gf2_pentanom_st* p) ``` 146 ```{ ``` 147 ``` register word hi; ``` 148 ``` // pre ``` 149 1 ``` ASSERT(wwIsValid(a, 2 * n)); ``` 150 1 ``` ASSERT(memIsValid(p, sizeof(*p))); ``` 151 1 ``` ASSERT(p->m > p->k && p->k > p->l && p->l > p->l1 && p->l1 > 0); ``` 152 1 ``` ASSERT(p->k < B_PER_W); ``` 153 1 ``` ASSERT(p->m - p->k >= B_PER_W); ``` 154 1 ``` ASSERT(p->bm < B_PER_W && p->bk < B_PER_W); ``` 155 1 ``` ASSERT(p->bl < B_PER_W && p->bl1 < B_PER_W); ``` 156 1 ``` ASSERT(p->m == B_PER_W * p->wm + p->bm); ``` 157 1 ``` ASSERT(p->m == p->k + B_PER_W * p->wk + p->bk); ``` 158 1 ``` ASSERT(p->m == p->l + B_PER_W * p->wl + p->bl); ``` 159 1 ``` ASSERT(p->m == p->l1 + B_PER_W * p->wl1 + p->bl1); ``` 160 1 ``` ASSERT(n == W_OF_B(p->m)); ``` 161 ``` // обрабатываем старшие слова ``` 162 1 ``` n *= 2; ``` 163 1 ``` while (--n > p->wm) ``` 164 ``` { ``` 165 1 ``` hi = a[n]; ``` 166 1 ``` a[n - p->wm - 1] ^= p->bm ? hi << (B_PER_W - p->bm) : 0; ``` 167 1 ``` a[n - p->wm] ^= hi >> p->bm; ``` 168 1 ``` a[n - p->wl1 - 1] ^= p->bl1 ? hi << (B_PER_W - p->bl1) : 0; ``` 169 1 ``` a[n - p->wl1] ^= hi >> p->bl1; ``` 170 1 ``` a[n - p->wl - 1] ^= p->bl ? hi << (B_PER_W - p->bl) : 0; ``` 171 1 ``` a[n - p->wl] ^= hi >> p->bl; ``` 172 1 ``` a[n - p->wk - 1] ^= p->bk ? hi << (B_PER_W - p->bk) : 0; ``` 173 1 ``` a[n - p->wk] ^= hi >> p->bk; ``` 174 ``` } ``` 175 ``` // слово, на которое попадает моном x^m ``` 176 1 ``` ASSERT(n == p->wm); ``` 177 1 ``` hi = a[n] >> p->bm; ``` 178 1 ``` a[0] ^= hi; ``` 179 1 ``` hi <<= p->bm; ``` 180 1 ``` if (p->wl1 < n && p->bl1) ``` 181 0 ``` a[n - p->wl1 - 1] ^= hi << (B_PER_W - p->bl1); ``` 182 1 ``` a[n - p->wl1] ^= hi >> p->bl1; ``` 183 1 ``` if (p->wl < n && p->bl) ``` 184 0 ``` a[n - p->wl - 1] ^= hi << (B_PER_W - p->bl); ``` 185 1 ``` a[n - p->wl] ^= hi >> p->bl; ``` 186 1 ``` if (p->wk < n && p->bk) ``` 187 0 ``` a[n - p->wk - 1] ^= hi << (B_PER_W - p->bk); ``` 188 1 ``` a[n - p->wk] ^= hi >> p->bk; ``` 189 1 ``` a[n] ^= hi; ``` 190 ``` // очистка ``` 191 1 ``` hi = 0; ``` 192 ```} ``` 193 194 ```/* ``` 195 ```******************************************************************************* ``` 196 ```Реализация интерфейсов qr_XXX_t ``` 197 198 ```Если степень расширения m кратна B_PER_W, то модуль задается n + 1 словом, ``` 199 ```а элементы поля -- n словами. Поэтому в функциях gf2From(), gf2Inv(), ``` 200 ```gf2Div() случай m % B_PER_W == 0 обрабатывается особенным образом. ``` 201 ```******************************************************************************* ``` 202 ```*/ ``` 203 204 1 ```static bool_t gf2From(word b[], const octet a[], const qr_o* f, void* stack) ``` 205 ```{ ``` 206 1 ``` ASSERT(gf2IsOperable(f)); ``` 207 1 ``` wwFrom(b, a, f->no); ``` 208 1 ``` return gf2IsIn(b, f); ``` 209 ```} ``` 210 211 1 ```static void gf2To(octet b[], const word a[], const qr_o* f, void* stack) ``` 212 ```{ ``` 213 1 ``` ASSERT(gf2IsOperable(f)); ``` 214 1 ``` ASSERT(gf2IsIn(a, f)); ``` 215 1 ``` wwTo(b, f->no, a); ``` 216 ```} ``` 217 218 0 ```static void gf2Add3(word c[], const word a[], const word b[], const qr_o* f) ``` 219 ```{ ``` 220 0 ``` ASSERT(gf2IsOperable(f)); ``` 221 0 ``` ASSERT(gf2IsIn(a, f)); ``` 222 0 ``` ASSERT(gf2IsIn(b, f)); ``` 223 0 ``` wwXor(c, a, b, f->n); ``` 224 ```} ``` 225 226 0 ```static void gf2Neg2(word b[], const word a[], const qr_o* f) ``` 227 ```{ ``` 228 0 ``` ASSERT(gf2IsOperable(f)); ``` 229 0 ``` ASSERT(gf2IsIn(a, f)); ``` 230 0 ``` wwCopy(b, a, f->n); ``` 231 ```} ``` 232 233 0 ```static void gf2MulTrinomial0(word c[], const word a[], const word b[], ``` 234 ``` const qr_o* f, void* stack) ``` 235 ```{ ``` 236 0 ``` word* prod = (word*)stack; ``` 237 0 ``` stack = prod + 2 * f->n; ``` 238 0 ``` ASSERT(gf2IsOperable(f)); ``` 239 0 ``` ASSERT(gf2IsIn(a, f)); ``` 240 0 ``` ASSERT(gf2IsIn(b, f)); ``` 241 0 ``` ppMul(prod, a, f->n, b, f->n, stack); ``` 242 0 ``` gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params); ``` 243 0 ``` wwCopy(c, prod, f->n); ``` 244 ```} ``` 245 246 1 ```static size_t gf2MulTrinomial0_deep(size_t n) ``` 247 ```{ ``` 248 1 ``` return ppMul_deep(n, n); ``` 249 ```} ``` 250 251 1 ```static void gf2MulTrinomial1(word c[], const word a[], const word b[], ``` 252 ``` const qr_o* f, void* stack) ``` 253 ```{ ``` 254 1 ``` word* prod = (word*)stack; ``` 255 1 ``` stack = prod + 2 * f->n; ``` 256 1 ``` ASSERT(gf2IsOperable(f)); ``` 257 1 ``` ASSERT(gf2IsIn(a, f)); ``` 258 1 ``` ASSERT(gf2IsIn(b, f)); ``` 259 1 ``` ppMul(prod, a, f->n, b, f->n, stack); ``` 260 1 ``` gf2RedTrinomial1(prod, f->n, (const gf2_trinom_st*)f->params); ``` 261 1 ``` wwCopy(c, prod, f->n); ``` 262 ```} ``` 263 264 1 ```static size_t gf2MulTrinomial1_deep(size_t n) ``` 265 ```{ ``` 266 1 ``` return ppMul_deep(n, n); ``` 267 ```} ``` 268 269 1 ```static void gf2MulPentanomial(word c[], const word a[], const word b[], ``` 270 ``` const qr_o* f, void* stack) ``` 271 ```{ ``` 272 1 ``` word* prod = (word*)stack; ``` 273 1 ``` stack = prod + 2 * f->n; ``` 274 1 ``` ASSERT(gf2IsOperable(f)); ``` 275 1 ``` ASSERT(gf2IsIn(a, f)); ``` 276 1 ``` ASSERT(gf2IsIn(b, f)); ``` 277 1 ``` ppMul(prod, a, f->n, b, f->n, stack); ``` 278 1 ``` gf2RedPentanomial(prod, f->n, (const gf2_pentanom_st*)f->params); ``` 279 1 ``` wwCopy(c, prod, f->n); ``` 280 ```} ``` 281 282 1 ```static size_t gf2MulPentanomial_deep(size_t n) ``` 283 ```{ ``` 284 1 ``` return ppMul_deep(n, n); ``` 285 ```} ``` 286 287 0 ```static void gf2SqrTrinomial0(word b[], const word a[], const qr_o* f, ``` 288 ``` void* stack) ``` 289 ```{ ``` 290 0 ``` word* prod = (word*)stack; ``` 291 0 ``` stack = prod + 2 * f->n; ``` 292 0 ``` ASSERT(gf2IsOperable(f)); ``` 293 0 ``` ASSERT(gf2IsIn(a, f)); ``` 294 0 ``` ppSqr(prod, a, f->n, stack); ``` 295 0 ``` gf2RedTrinomial0(prod, f->n, (const gf2_trinom_st*)f->params); ``` 296 0 ``` wwCopy(b, prod, f->n); ``` 297 ```} ``` 298 299 1 ```static size_t gf2SqrTrinomial0_deep(size_t n) ``` 300 ```{ ``` 301 1 ``` return ppSqr_deep(n); ``` 302 ```} ``` 303 304 1 ```static void gf2SqrTrinomial1(word b[], const word a[], const qr_o* f, ``` 305 ``` void* stack) ``` 306 ```{ ``` 307 1 ``` word* prod = (word*)stack; ``` 308 1 ``` stack = prod + 2 * f->n; ``` 309 1 ``` ASSERT(gf2IsOperable(f)); ``` 310 1 ``` ASSERT(gf2IsIn(a, f)); ``` 311 1 ``` ppSqr(prod, a, f->n, stack); ``` 312 1 ``` gf2RedTrinomial1(prod, f->n, (const gf2_trinom_st*)f->params); ``` 313 1 ``` wwCopy(b, prod, f->n); ``` 314 ```} ``` 315 316 1 ```static size_t gf2SqrTrinomial1_deep(size_t n) ``` 317 ```{ ``` 318 1 ``` return ppSqr_deep(n); ``` 319 ```} ``` 320 321 1 ```static void gf2SqrPentanomial(word b[], const word a[], const qr_o* f, ``` 322 ``` void* stack) ``` 323 ```{ ``` 324 1 ``` word* prod = (word*)stack; ``` 325 1 ``` stack = prod + 2 * f->n; ``` 326 1 ``` ASSERT(gf2IsOperable(f)); ``` 327 1 ``` ASSERT(gf2IsIn(a, f)); ``` 328 1 ``` ppSqr(prod, a, f->n, stack); ``` 329 1 ``` gf2RedPentanomial(prod, f->n, (const gf2_pentanom_st*)f->params); ``` 330 1 ``` wwCopy(b, prod, f->n); ``` 331 ```} ``` 332 333 1 ```static size_t gf2SqrPentanomial_deep(size_t n) ``` 334 ```{ ``` 335 1 ``` return ppSqr_deep(n); ``` 336 ```} ``` 337 338 1 ```static void gf2Inv(word b[], const word a[], const qr_o* f, void* stack) ``` 339 ```{ ``` 340 1 ``` ASSERT(gf2IsOperable(f)); ``` 341 1 ``` ASSERT(gf2IsIn(a, f)); ``` 342 1 ``` if (gf2Deg(f) % B_PER_W == 0) ``` 343 ``` { ``` 344 0 ``` word* c = (word*)stack; ``` 345 0 ``` stack = c + f->n + 1; ``` 346 0 ``` ppInvMod(c, a, f->mod, f->n + 1, stack); ``` 347 0 ``` ASSERT(c[f->n] == 0); ``` 348 0 ``` wwCopy(b, c, f->n); ``` 349 ``` } ``` 350 ``` else ``` 351 1 ``` ppInvMod(b, a, f->mod, f->n, stack); ``` 352 ```} ``` 353 354 1 ```static size_t gf2Inv_deep(size_t n) ``` 355 ```{ ``` 356 1 ``` return O_OF_W(n + 1) + ppInvMod_deep(n + 1); ``` 357 ```} ``` 358 359 1 ```static void gf2Div(word b[], const word divident[], const word a[], ``` 360 ``` const qr_o* f, void* stack) ``` 361 ```{ ``` 362 1 ``` ASSERT(gf2IsOperable(f)); ``` 363 1 ``` ASSERT(gf2IsIn(divident, f)); ``` 364 1 ``` ASSERT(gf2IsIn(a, f)); ``` 365 1 ``` if (gf2Deg(f) % B_PER_W == 0) ``` 366 ``` { ``` 367 0 ``` word* c = (word*)stack; ``` 368 0 ``` stack = c + f->n + 1; ``` 369 0 ``` ppDivMod(c, divident, a, f->mod, f->n + 1, stack); ``` 370 0 ``` ASSERT(c[f->n] == 0); ``` 371 0 ``` wwCopy(b, c, f->n); ``` 372 ``` } ``` 373 ``` else ``` 374 1 ``` ppDivMod(b, divident, a, f->mod, f->n, stack); ``` 375 ```} ``` 376 377 1 ```static size_t gf2Div_deep(size_t n) ``` 378 ```{ ``` 379 1 ``` return O_OF_W(n + 1) + ppDivMod_deep(n + 1); ``` 380 ```} ``` 381 382 ```/* ``` 383 ```******************************************************************************* ``` 384 ```Управление описанием поля ``` 385 ```******************************************************************************* ``` 386 ```*/ ``` 387 388 1 ```bool_t gf2Create(qr_o* f, const size_t p[4], void* stack) ``` 389 ```{ ``` 390 1 ``` ASSERT(memIsValid(f, sizeof(qr_o))); ``` 391 1 ``` ASSERT(memIsValid(p, 4 * sizeof(size_t))); ``` 392 ``` // нормальный базис? ``` 393 1 ``` if (p[1] == 0) ``` 394 ``` { ``` 395 ``` // todo: реализовать ``` 396 0 ``` return FALSE; ``` 397 ``` } ``` 398 ``` // трехчлен? ``` 399 1 ``` else if (p[2] == 0) ``` 400 ``` { ``` 401 ``` gf2_trinom_st* t; ``` 402 ``` size_t n1; ``` 403 ``` // нарушены соглашения? ``` 404 1 ``` if (p[2] != 0 || p[3] != 0) ``` 405 0 ``` return FALSE; ``` 406 ``` // нарушены условия функции ppRedTrinomial? ``` 407 1 ``` if (p[0] % 8 == 0 || p[1] >= p[0] || p[0] - p[1] < B_PER_W) ``` 408 0 ``` return FALSE; ``` 409 ``` // зафиксировать размерность ``` 410 1 ``` f->n = W_OF_B(p[0]); ``` 411 1 ``` n1 = f->n + (p[0] % B_PER_W == 0); ``` 412 1 ``` f->no = O_OF_B(p[0]); ``` 413 ``` // сформировать mod ``` 414 1 ``` f->mod = (word*)f->descr; ``` 415 1 ``` wwSetZero(f->mod, n1); ``` 416 1 ``` wwSetBit(f->mod, p[0], 1); ``` 417 1 ``` wwSetBit(f->mod, p[1], 1); ``` 418 1 ``` wwSetBit(f->mod, 0, 1); ``` 419 ``` // сформировать unity ``` 420 1 ``` f->unity = f->mod + n1; ``` 421 1 ``` wwSetW(f->unity, f->n, 1); ``` 422 ``` // сформировать params ``` 423 1 ``` f->params = (size_t*)(f->unity + f->n); ``` 424 1 ``` t = (gf2_trinom_st*)f->params; ``` 425 1 ``` t->m = p[0]; ``` 426 1 ``` t->k = p[1]; ``` 427 1 ``` t->l = t->l1 = 0; ``` 428 1 ``` t->bm = p[0] % B_PER_W; ``` 429 1 ``` t->wm = p[0] / B_PER_W; ``` 430 1 ``` t->bk = (p[0] - p[1]) % B_PER_W; ``` 431 1 ``` t->wk = (p[0] - p[1]) / B_PER_W; ``` 432 ``` // настроить интерфейсы ``` 433 1 ``` f->from = gf2From; ``` 434 1 ``` f->to = gf2To; ``` 435 1 ``` f->add = gf2Add3; ``` 436 1 ``` f->sub = gf2Add3; ``` 437 1 ``` f->neg = gf2Neg2; ``` 438 1 ``` f->mul = t->bk == 0 ? gf2MulTrinomial0 : gf2MulTrinomial1; ``` 439 1 ``` f->sqr = t->bk == 0 ? gf2SqrTrinomial0 : gf2SqrTrinomial1; ``` 440 1 ``` f->inv = gf2Inv; ``` 441 1 ``` f->div = gf2Div; ``` 442 ``` // заголовок ``` 443 1 ``` f->hdr.keep = sizeof(qr_o) + O_OF_W(n1 + f->n) + sizeof(gf2_trinom_st); ``` 444 1 ``` f->hdr.p_count = 3; ``` 445 1 ``` f->hdr.o_count = 0; ``` 446 ``` // глубина стека ``` 447 1 ``` if (t->bk == 0) ``` 448 0 ``` f->deep = utilMax(4, ``` 449 ``` gf2MulTrinomial0_deep(f->n), ``` 450 ``` gf2SqrTrinomial0_deep(f->n), ``` 451 ``` gf2Inv_deep(f->n), ``` 452 ``` gf2Div_deep(f->n)); ``` 453 ``` else ``` 454 1 ``` f->deep = utilMax(4, ``` 455 ``` gf2MulTrinomial1_deep(f->n), ``` 456 ``` gf2SqrTrinomial1_deep(f->n), ``` 457 ``` gf2Inv_deep(f->n), ``` 458 ``` gf2Div_deep(f->n)); ``` 459 ``` } ``` 460 ``` // пятичлен? ``` 461 ``` else ``` 462 ``` { ``` 463 ``` gf2_pentanom_st* t; ``` 464 ``` size_t n1; ``` 465 ``` // нарушены соглашения? ``` 466 1 ``` if (p[3] == 0) ``` 467 0 ``` return FALSE; ``` 468 ``` // нарушены условия функции ppRedPentanomial? ``` 469 1 ``` if (p[1] >= p[0] || p[2] >= p[1] || p[3] >= p[2] || p[3] == 0 || ``` 470 1 ``` p[0] - p[1] < B_PER_W || p[1] >= B_PER_W) ``` 471 0 ``` return FALSE; ``` 472 ``` // зафиксировать размерность ``` 473 1 ``` f->n = W_OF_B(p[0]); ``` 474 1 ``` n1 = f->n + (p[0] % B_PER_W == 0); ``` 475 1 ``` f->no = O_OF_B(p[0]); ``` 476 ``` // сформировать mod ``` 477 1 ``` f->mod = (word*)f->descr; ``` 478 1 ``` wwSetZero(f->mod, n1); ``` 479 1 ``` wwSetBit(f->mod, p[0], 1); ``` 480 1 ``` wwSetBit(f->mod, p[1], 1); ``` 481 1 ``` wwSetBit(f->mod, p[2], 1); ``` 482 1 ``` wwSetBit(f->mod, p[3], 1); ``` 483 1 ``` wwSetBit(f->mod, 0, 1); ``` 484 ``` // сформировать unity ``` 485 1 ``` f->unity = f->mod + n1; ``` 486 1 ``` wwSetW(f->unity, f->n, 1); ``` 487 ``` // сформировать params ``` 488 1 ``` f->params = (size_t*)(f->unity + f->n); ``` 489 1 ``` t = (gf2_pentanom_st*)f->params; ``` 490 1 ``` t->m = p[0]; ``` 491 1 ``` t->k = p[1]; ``` 492 1 ``` t->l = p[2]; ``` 493 1 ``` t->l1 = p[3]; ``` 494 1 ``` t->bm = p[0] % B_PER_W; ``` 495 1 ``` t->wm = p[0] / B_PER_W; ``` 496 1 ``` t->bk = (p[0] - p[1]) % B_PER_W; ``` 497 1 ``` t->wk = (p[0] - p[1]) / B_PER_W; ``` 498 1 ``` t->bl = (p[0] - p[2]) % B_PER_W; ``` 499 1 ``` t->wl = (p[0] - p[2]) / B_PER_W; ``` 500 1 ``` t->bl1 = (p[0] - p[3]) % B_PER_W; ``` 501 1 ``` t->wl1 = (p[0] - p[3]) / B_PER_W; ``` 502 ``` // настроить интерфейсы ``` 503 1 ``` f->from = gf2From; ``` 504 1 ``` f->to = gf2To; ``` 505 1 ``` f->add = gf2Add3; ``` 506 1 ``` f->sub = gf2Add3; ``` 507 1 ``` f->neg = gf2Neg2; ``` 508 1 ``` f->mul = gf2MulPentanomial; ``` 509 1 ``` f->sqr = gf2SqrPentanomial; ``` 510 1 ``` f->inv = gf2Inv; ``` 511 1 ``` f->div = gf2Div; ``` 512 ``` // заголовок ``` 513 1 ``` f->hdr.keep = sizeof(qr_o) + O_OF_W(n1 + f->n) + ``` 514 ``` sizeof(gf2_pentanom_st); ``` 515 1 ``` f->hdr.p_count = 3; ``` 516 1 ``` f->hdr.o_count = 0; ``` 517 ``` // глубина стека ``` 518 1 ``` f->deep = utilMax(4, ``` 519 ``` gf2MulPentanomial_deep(f->n), ``` 520 ``` gf2SqrPentanomial_deep(f->n), ``` 521 ``` gf2Inv_deep(f->n), ``` 522 ``` gf2Div_deep(f->n)); ``` 523 ``` } ``` 524 1 ``` return TRUE; ``` 525 ```} ``` 526 527 1 ```size_t gf2Create_keep(size_t m) ``` 528 ```{ ``` 529 1 ``` const size_t n = W_OF_B(m); ``` 530 1 ``` const size_t n1 = n + (m % B_PER_W == 0); ``` 531 1 ``` return sizeof(qr_o) + O_OF_W(n1 + n) + ``` 532 1 ``` utilMax(2, ``` 533 ``` sizeof(gf2_trinom_st), ``` 534 ``` sizeof(gf2_pentanom_st)); ``` 535 ```} ``` 536 537 1 ```size_t gf2Create_deep(size_t m) ``` 538 ```{ ``` 539 1 ``` const size_t n = W_OF_B(m); ``` 540 1 ``` return utilMax(8, ``` 541 ``` gf2MulTrinomial0_deep(n), ``` 542 ``` gf2SqrTrinomial0_deep(n), ``` 543 ``` gf2MulTrinomial1_deep(n), ``` 544 ``` gf2SqrTrinomial1_deep(n), ``` 545 ``` gf2MulPentanomial_deep(n), ``` 546 ``` gf2SqrPentanomial_deep(n), ``` 547 ``` gf2Inv_deep(n), ``` 548 ``` gf2Div_deep(n)); ``` 549 ```} ``` 550 551 1 ```bool_t gf2IsOperable(const qr_o* f) ``` 552 ```{ ``` 553 ``` const size_t* p; ``` 554 ``` size_t n1; ``` 555 1 ``` if (!qrIsOperable(f) || ``` 556 1 ``` !memIsValid(f->params, 4 * sizeof(size_t))) ``` 557 0 ``` return FALSE; ``` 558 ``` // проверить описание многочлена ``` 559 1 ``` p = (size_t*)f->params; ``` 560 1 ``` if (p[0] <= p[1] || p[1] < p[2] || p[2] < p[3] || ``` 561 1 ``` (p[2] > 0 && (p[1] == p[2] || p[2] == p[3] || p[3] == 0)) || ``` 562 1 ``` f->n != W_OF_B(p[0]) || f->no != O_OF_B(p[0])) ``` 563 0 ``` return FALSE; ``` 564 ``` // проверить модуль ``` 565 1 ``` n1 = f->n + (p[0] % B_PER_W == 0); ``` 566 1 ``` if (!wwIsValid(f->mod, n1) || f->mod[n1 - 1] == 0) ``` 567 0 ``` return FALSE; ``` 568 ``` // все нормально ``` 569 1 ``` return TRUE; ``` 570 ```} ``` 571 572 1 ```bool_t gf2IsValid(const qr_o* f, void* stack) ``` 573 ```{ ``` 574 ``` const size_t* p; ``` 575 1 ``` if (!gf2IsOperable(f)) ``` 576 0 ``` return FALSE; ``` 577 1 ``` p = (const size_t*)f->params; ``` 578 1 ``` if (p[1] > 0) ``` 579 ``` { ``` 580 ``` // согласованность ``` 581 1 ``` const size_t n1 = f->n + (p[0] % B_PER_W == 0); ``` 582 1 ``` word* mod = (word*)stack; ``` 583 1 ``` wwSetZero(mod, n1); ``` 584 1 ``` wwSetBit(mod, p[0], 1); ``` 585 1 ``` wwSetBit(mod, p[1], 1); ``` 586 1 ``` wwSetBit(mod, p[2], 1); ``` 587 1 ``` wwSetBit(mod, p[3], 1); ``` 588 1 ``` wwSetBit(mod, 0, 1); ``` 589 1 ``` if (!wwEq(mod, f->mod, n1)) ``` 590 0 ``` return FALSE; ``` 591 ``` // неприводимость ``` 592 1 ``` return ppIsIrred(f->mod, n1, stack); ``` 593 ``` } ``` 594 0 ``` return TRUE; ``` 595 ```} ``` 596 597 1 ```size_t gf2IsValid_deep(size_t n) ``` 598 ```{ ``` 599 1 ``` return O_OF_W(n + 1) + ppIsIrred_deep(n + 1); ``` 600 ```} ``` 601 602 1 ```size_t gf2Deg(const qr_o* f) ``` 603 ```{ ``` 604 1 ``` ASSERT(gf2IsOperable(f)); ``` 605 1 ``` return ((size_t*)f->params)[0]; ``` 606 ```} ``` 607 608 ```/* ``` 609 ```******************************************************************************* ``` 610 ```Дополнительные функции ``` 611 612 ```В gf2QSolve() реализован алгоритм из раздела 6.7 ДСТУ 4145-2002. ``` 613 ```******************************************************************************* ``` 614 ```*/ ``` 615 616 1 ```bool_t gf2Tr(const word a[], const qr_o* f, void* stack) ``` 617 ```{ ``` 618 1 ``` size_t m = gf2Deg(f); ``` 619 1 ``` word* t = (word*)stack; ``` 620 1 ``` stack = t + f->n; ``` 621 ``` // pre ``` 622 1 ``` ASSERT(gf2IsOperable(f)); ``` 623 1 ``` ASSERT(gf2IsIn(a, f)); ``` 624 ``` // t <- sum_{i = 0}^{m - 1} a^{2^i} ``` 625 1 ``` qrCopy(t, a, f); ``` 626 1 ``` while (--m) ``` 627 ``` { ``` 628 1 ``` qrSqr(t, t, f, stack); ``` 629 1 ``` gf2Add2(t, a, f); ``` 630 ``` } ``` 631 ``` // t == 0? ``` 632 1 ``` if (qrIsZero(t, f)) ``` 633 1 ``` return FALSE; ``` 634 ``` // t == 1? ``` 635 1 ``` ASSERT(qrIsUnity(t, f)); ``` 636 1 ``` return TRUE; ``` 637 ```} ``` 638 639 1 ```size_t gf2Tr_deep(size_t n, size_t f_deep) ``` 640 ```{ ``` 641 1 ``` return O_OF_W(n) + f_deep; ``` 642 ```} ``` 643 644 1 ```bool_t gf2QSolve(word x[], const word a[], const word b[], ``` 645 ``` const qr_o* f, void* stack) ``` 646 ```{ ``` 647 1 ``` size_t m = gf2Deg(f); ``` 648 1 ``` word* t = (word*)stack; ``` 649 1 ``` stack = t + f->n; ``` 650 ``` // pre ``` 651 1 ``` ASSERT(gf2IsOperable(f)); ``` 652 1 ``` ASSERT(gf2IsIn(a, f)); ``` 653 1 ``` ASSERT(gf2IsIn(b, f)); ``` 654 1 ``` ASSERT(x + f->n <= a || x >= a + f->n); ``` 655 1 ``` ASSERT(m % 2); ``` 656 ``` // a == 0? ``` 657 1 ``` if (qrIsZero(a, f)) ``` 658 ``` { ``` 659 ``` // x <- b^{2^{m - 1}} ``` 660 0 ``` qrCopy(x, b, f); ``` 661 0 ``` while (--m) ``` 662 0 ``` qrSqr(x, x, f, stack); ``` 663 0 ``` return TRUE; ``` 664 ``` } ``` 665 ``` // a != 0, b == 0? ``` 666 1 ``` if (qrIsZero(b, f)) ``` 667 ``` { ``` 668 0 ``` qrSetZero(x, f); ``` 669 0 ``` return TRUE; ``` 670 ``` } ``` 671 ``` // t <- ba^{-2} ``` 672 1 ``` qrSqr(t, a, f, stack); ``` 673 1 ``` qrDiv(t, b, t, f, stack); ``` 674 ``` // tr(t) == 1? ``` 675 1 ``` if (gf2Tr(t, f, stack)) ``` 676 1 ``` return FALSE; ``` 677 ``` // x <- htr(t) (полуслед) ``` 678 1 ``` qrCopy(x, t, f); ``` 679 1 ``` m = (m - 1) / 2; ``` 680 1 ``` while (m--) ``` 681 ``` { ``` 682 1 ``` qrSqr(x, x, f, stack); ``` 683 1 ``` qrSqr(x, x, f, stack); ``` 684 1 ``` gf2Add2(x, t, f); ``` 685 ``` } ``` 686 ``` // x <- x * a ``` 687 1 ``` qrMul(x, x, a, f, stack); ``` 688 ``` // решение есть ``` 689 1 ``` return TRUE; ``` 690 ```} ``` 691 692 1 ```size_t gf2QSolve_deep(size_t n, size_t f_deep) ``` 693 ```{ ``` 694 1 ``` return O_OF_W(n) + f_deep; ``` 695 ```} ```

Read our documentation on viewing source code .