1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 */
10
11 #include "vecgf2.h"
12
13 #include "ariths.h"
14 #include "bits_intern.h"
15 #include "blister.h"
16 #include "bool.h"
17 #include "error.h"
18 #include "finfield.h"
19 #include "gvars.h"
20 #include "integer.h"
21 #include "lists.h"
22 #include "modules.h"
23 #include "opers.h"
24 #include "plist.h"
25 #include "precord.h"
26 #include "range.h"
27 #include "records.h"
28 #include "stats.h"
29 #include "vec8bit.h"
30
31 #include <gmp.h>
32
33
34 /****************************************************************************
35 **
36 *F * * * * * * * * * * * imported library variables * * * * * * * * * * * * *
37 */
38
39
40 /****************************************************************************
41 **
42 *V TYPE_LIST_GF2VEC . . . . . . . . . . . . . . type of a GF2 vector object
43 */
44 Obj TYPE_LIST_GF2VEC;
45
46
47 /****************************************************************************
48 **
49 *V TYPE_LIST_GF2VEC_LOCKED. . . . type of a mutable GF2 vector object
50 ** with locked representation
51 */
52 Obj TYPE_LIST_GF2VEC_LOCKED;
53
54
55 /****************************************************************************
56 **
57 *V TYPE_LIST_GF2VEC_IMM . . . . . . type of an immutable GF2 vector object
58 */
59 Obj TYPE_LIST_GF2VEC_IMM;
60
61 /****************************************************************************
62 **
63 *V TYPE_LIST_GF2VEC_IMM_LOCKED . . . type of an immutable GF2 vector object
64 ** with locked representation
65 */
66 Obj TYPE_LIST_GF2VEC_IMM_LOCKED;
67
68
69 /****************************************************************************
70 **
71 *V TYPE_LIST_GF2MAT . . . . . . . . . . . . . . type of a GF2 matrix object
72 */
73 Obj TYPE_LIST_GF2MAT;
74
75
76 /****************************************************************************
77 **
78 *V TYPE_LIST_GF2MAT_IMM . . . . . . type of an immutable GF2 matrix object
79 */
80 Obj TYPE_LIST_GF2MAT_IMM;
81
82
83 /****************************************************************************
84 **
85 *V IsGF2VectorRep . . . . . . . . . . . . . . . . . . . . . . . . . filter
86 */
87 Obj IsGF2VectorRep;
88
89
90 /****************************************************************************
91 **
92 *V GF2One . . . . . . . . . . . . . . . . . . . . . . . . . . . one of GF2
93 */
94 static Obj GF2One;
95
96
97 /****************************************************************************
98 **
99 *V GF2Zero . . . . . . . . . . . . . . . . . . . . . . . . . . . zero of GF2
100 */
101 static Obj GF2Zero;
102
103
104 /****************************************************************************
105 **
106 *F * * * * * * * * * * * * arithmetic operations * * * * * * * * * * * * * *
107 */
108
AddGF2VecToGF2Vec(UInt * ptS,const UInt * ptV,UInt len)109 static inline void AddGF2VecToGF2Vec(UInt * ptS, const UInt * ptV, UInt len)
110 {
111 register UInt ct;
112 ct = (len + BIPEB - 1) / BIPEB;
113 while (ct--) {
114 *ptS++ ^= *ptV++;
115 }
116 }
117
118 /****************************************************************************
119 **
120 *F AddCoeffsGF2VecGF2Vec( <sum>, <vec> ) . . . . . . . . add <vec> to <sum>
121 **
122 ** `AddCoeffsGF2VecGF2Vec' adds the entries of <vec> to <sum>. If the
123 ** length are not equal the missing entries are assumed to be zero. The
124 ** position of the rightmost Z(2) is returned.
125 */
126
RightMostOneGF2Vec(Obj vec)127 static UInt RightMostOneGF2Vec(Obj vec)
128 {
129 UInt len;
130
131 len = LEN_GF2VEC(vec);
132 while (0 < len) {
133 if (CONST_BLOCK_ELM_GF2VEC(vec, len) == 0)
134 len = BIPEB * ((len - 1) / BIPEB);
135 else if (BLOCK_ELM_GF2VEC(vec, len) & MASK_POS_GF2VEC(len))
136 break;
137 else
138 len--;
139 }
140 return len;
141 }
142
143
AddCoeffsGF2VecGF2Vec(Obj sum,Obj vec)144 static Obj AddCoeffsGF2VecGF2Vec(Obj sum, Obj vec)
145 {
146 UInt * ptS;
147 const UInt * ptV;
148 UInt len;
149
150 // get the length
151 len = LEN_GF2VEC(vec);
152
153 // grow <sum> is necessary
154 if (LEN_GF2VEC(sum) < len) {
155 ResizeWordSizedBag(sum, SIZE_PLEN_GF2VEC(len));
156 SET_LEN_GF2VEC(sum, len);
157 }
158
159 // add <vec> to <sum>
160 ptS = BLOCKS_GF2VEC(sum);
161 ptV = CONST_BLOCKS_GF2VEC(vec);
162 AddGF2VecToGF2Vec(ptS, ptV, len);
163 return INTOBJ_INT(RightMostOneGF2Vec(sum));
164 }
165
166
167 static inline void
CopySection_GF2Vecs(Obj src,Obj dest,UInt smin,UInt dmin,UInt nelts)168 CopySection_GF2Vecs(Obj src, Obj dest, UInt smin, UInt dmin, UInt nelts)
169 {
170 UInt soff;
171 UInt doff;
172 const UInt * sptr;
173 UInt * dptr;
174
175 // switch to zero-based indices and find the first blocks and so on
176 soff = (smin - 1) % BIPEB;
177 doff = (dmin - 1) % BIPEB;
178 sptr = CONST_BLOCKS_GF2VEC(src) + (smin - 1) / BIPEB;
179 dptr = BLOCKS_GF2VEC(dest) + (dmin - 1) / BIPEB;
180
181 CopyBits(sptr, soff, dptr, doff, nelts);
182 return;
183 }
184
185 /****************************************************************************
186 **
187 *F AddPartialGF2VecGF2Vec( <sum>, <vl>, <vr>, <n> ) . . . . . . partial sum
188 **
189 ** 'AddPartialGF2VecGF2Vec' adds the entries of <vl> and <vr> starting from
190 ** that block which is corresponding to the entry with number <n> and stores
191 ** the result in <sum>.
192 **
193 ** Note: The other entries are set to be zero. So use a higher value for <n>
194 ** only for vectors, which both have leading zero-entries.
195 **
196 ** You can use the parameter <n> for example for an gauss-algorithm on
197 ** gf2-matrices can be improved, because when using the gauss-algorithm,
198 ** you know that the leading entries of two vectors to be added are equal
199 ** zero. If <n> = 1 all entries are added.
200 **
201 ** Note that the caller has to ensure, that <sum> is a gf2-vector with the
202 ** correct size.
203 */
AddPartialGF2VecGF2Vec(Obj sum,Obj vl,Obj vr,UInt n)204 static Obj AddPartialGF2VecGF2Vec(Obj sum, Obj vl, Obj vr, UInt n)
205 {
206 const UInt * ptL; // bit field of <vl>
207 const UInt * ptR; // bit field of <vr>
208 UInt * ptS; // bit field of <sum>
209 UInt * end; // end marker
210 UInt len; // length of the list
211 UInt offset; // number of block to start adding
212 UInt x;
213
214
215 // both operands lie in the same field
216 len = LEN_GF2VEC(vl);
217 if (len != LEN_GF2VEC(vr)) {
218 ErrorMayQuit("Vector +: vectors must have the same length", 0L, 0L);
219 }
220
221
222 // calculate the offset for adding
223 if (n == 1) {
224 ptL = CONST_BLOCKS_GF2VEC(vl);
225 ptR = CONST_BLOCKS_GF2VEC(vr);
226 ptS = BLOCKS_GF2VEC(sum);
227 end = ptS + ((len + BIPEB - 1) / BIPEB);
228 }
229 else {
230 offset = (n - 1) / BIPEB;
231 ptL = CONST_BLOCKS_GF2VEC(vl) + offset;
232 ptR = CONST_BLOCKS_GF2VEC(vr) + offset;
233 ptS = BLOCKS_GF2VEC(sum) + offset;
234 end = ptS + ((len + BIPEB - 1) / BIPEB) - offset;
235 }
236
237 // loop over the entries and add
238 if (vl == sum)
239 while (ptS < end) {
240 // maybe remove this condition
241 if ((x = *ptR) != 0)
242 *ptS = *ptL ^ x;
243 ptL++;
244 ptS++;
245 ptR++;
246 }
247 else if (vr == sum)
248 while (ptS < end) {
249 // maybe remove this condition
250 if ((x = *ptL) != 0)
251 *ptS = *ptR ^ x;
252 ptL++;
253 ptS++;
254 ptR++;
255 }
256 else
257 while (ptS < end)
258 *ptS++ = *ptL++ ^ *ptR++;
259
260 // return the result
261 return sum;
262 }
263
264
265 /****************************************************************************
266 **
267 *F ProdGF2VecGF2Vec( <vl>, <vr> ) . . . . . . . product of two GF2 vectors
268 **
269 ** 'ProdVecGF2VecGF2' returns the product of the two GF2 vectors <vl> and
270 ** <vr>. The product is the folded sum of the corresponding entries of
271 ** <vl> and <vr>.
272 **
273 ** 'ProdVecGF2VecGF2' is an improved version of the general multiplication,
274 ** which does not call 'PROD' but uses bit operations instead. It will
275 ** always return either 'GF2One' or 'GF2Zero'.
276 */
277 #ifdef SYS_IS_64_BIT
278
279 #define PARITY_BLOCK(m) \
280 do { \
281 m = m ^ (m >> 32); \
282 m = m ^ (m >> 16); \
283 m = m ^ (m >> 8); \
284 m = m ^ (m >> 4); \
285 m = m ^ (m >> 2); \
286 m = m ^ (m >> 1); \
287 } while (0)
288
289 #else
290
291 #define PARITY_BLOCK(m) \
292 do { \
293 m = m ^ (m >> 16); \
294 m = m ^ (m >> 8); \
295 m = m ^ (m >> 4); \
296 m = m ^ (m >> 2); \
297 m = m ^ (m >> 1); \
298 } while (0)
299
300 #endif
301
ProdGF2VecGF2Vec(Obj vl,Obj vr)302 static Obj ProdGF2VecGF2Vec(Obj vl, Obj vr)
303 {
304 const UInt * ptL; // bit field of <vl>
305 const UInt * ptR; // bit field of <vr>
306 UInt lenL; // length of the list
307 UInt lenR; // length of the list
308 UInt len; // minimum of the lengths
309 UInt nrb; // number of whole blocks to use
310 UInt m; // number of bits in a block
311 UInt n; // number of bits in blist
312 UInt i; // loop variable
313 UInt mask; // bit selecting mask
314
315 // both operands lie in the same field
316 lenL = LEN_GF2VEC(vl);
317 lenR = LEN_GF2VEC(vr);
318 len = (lenL < lenR) ? lenL : lenR;
319
320 if (len == 0) {
321 ErrorMayQuit("Vector *: both vectors must have at least one entry",
322 (Int)0, (Int)0);
323 }
324
325 // loop over the entries and multiply
326 ptL = CONST_BLOCKS_GF2VEC(vl);
327 ptR = CONST_BLOCKS_GF2VEC(vr);
328 nrb = len / BIPEB;
329 n = 0;
330 for (i = nrb; i > 0; i--) {
331 m = (*ptL++) & (*ptR++);
332 PARITY_BLOCK(m);
333 n ^= m;
334 }
335 // now process the remaining bits
336
337 mask = 1;
338 for (i = 0; i < len % BIPEB; i++) {
339 n ^= (mask & *ptL & *ptR) >> i;
340 mask <<= 1;
341 }
342
343 // return the result
344 return (n & 1) ? GF2One : GF2Zero;
345 }
346
347
348 /****************************************************************************
349 **
350 *F ProdGF2VecGF2Mat( <vl>, <vr> ) . . product of GF2 vector and GF2 matrix
351 **
352 ** 'ProdGF2VecGF2Mat' returns the product of the GF2 vector <vl> and the
353 ** GF2 matrix <vr>. The product is the sum of the rows of <vr>, each
354 ** multiplied by the corresponding entry of <vl>. Note that the caller has
355 ** to ensure, that <vl> is a gf2-vector and <vr> is a gf2-matrix.
356 */
ProdGF2VecGF2Mat(Obj vl,Obj vr)357 static Obj ProdGF2VecGF2Mat(Obj vl, Obj vr)
358 {
359 UInt len; // length of the list
360 UInt stop;
361 UInt col; // length of the rows
362 UInt i; // loop variables
363 Obj prod; // product, result
364 Obj row1; // top row of matrix
365 UInt * start;
366 const UInt * ptL;
367 UInt mask;
368
369 // both operands lie in the same field
370 len = LEN_GF2VEC(vl);
371 if (len > LEN_GF2MAT(vr))
372 len = LEN_GF2MAT(vr);
373
374 // make the result vector
375 row1 = ELM_GF2MAT(vr, 1);
376 col = LEN_GF2VEC(row1);
377 NEW_GF2VEC(prod,
378 (IS_MUTABLE_OBJ(vl) || IS_MUTABLE_OBJ(row1))
379 ? TYPE_LIST_GF2VEC
380 : TYPE_LIST_GF2VEC_IMM,
381 col);
382
383 // get the start and end block
384 start = BLOCKS_GF2VEC(prod);
385 ptL = CONST_BLOCKS_GF2VEC(vl);
386
387 // loop over the vector
388 for (i = 1; i <= len; ptL++) {
389
390 // if the whole block is zero, get the next entry
391 if (*ptL == 0) {
392 i += BIPEB;
393 continue;
394 }
395
396 // run through the block
397 stop = i + BIPEB - 1;
398 if (len < stop)
399 stop = len;
400 for (mask = 1; i <= stop; i++, mask <<= 1) {
401
402 // if there is entry add the row to the result
403 if ((*ptL & mask) != 0) {
404 const UInt * ptRR = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(vr, i));
405 AddGF2VecToGF2Vec(start, ptRR, col);
406 }
407 }
408 }
409
410 // return the result
411 return prod;
412 }
413
414
415 /****************************************************************************
416 **
417 *F ProdGF2MatGF2Vec( <ml>, <vr> ) . . product of GF2 matrix and GF2 vector
418 **
419 ** 'ProdGF2MatGF2Vec' returns the product of the GF2 matrix <ml> and the
420 ** GF2 vector <vr>. The ith entry of the
421 ** product is the inner product of the ith row of <ml> with <vr>.
422 ** Note that the caller has
423 ** to ensure, that <ml> is a GF2 matrix and <vr> is a GF2 vector.
424 */
ProdGF2MatGF2Vec(Obj ml,Obj vr)425 static Obj ProdGF2MatGF2Vec(Obj ml, Obj vr)
426 {
427 UInt len; // length of the vector
428 UInt ln1; // length of the rows of the mx
429 UInt ln2; // length of the matrix
430 const UInt * ptL; // bit field of <ml>[j]
431 const UInt * ptR; // bit field of <vr>
432 UInt nrb; // number of blocks in blist
433 UInt m; // number of bits in a block
434 UInt n; // number of bits in blist
435 UInt i; // loop variable
436 UInt j; // loop variable
437 Obj prod; // result
438 UInt mask; // a one bit mask
439
440 // both operands lie in the same field
441 len = LEN_GF2VEC(vr);
442 ln2 = LEN_GF2MAT(ml);
443 if (0 == ln2) {
444 ErrorMayQuit("PROD: empty GF2 matrix * GF2 vector not allowed", 0, 0);
445 }
446
447 ln1 = LEN_GF2VEC(ELM_GF2MAT(ml, 1));
448 if (len > ln1) {
449 len = ln1;
450 }
451
452 // make the result vector
453 NEW_GF2VEC(prod,
454 (IS_MUTABLE_OBJ(ELM_GF2MAT(ml, 1)) || IS_MUTABLE_OBJ(vr))
455 ? TYPE_LIST_GF2VEC
456 : TYPE_LIST_GF2VEC_IMM,
457 ln2);
458
459 // loop over the entries and multiply
460 nrb = len / BIPEB;
461 for (j = 1; j <= ln2; j++) {
462 ptL = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, j));
463 ptR = CONST_BLOCKS_GF2VEC(vr);
464 n = 0;
465 for (i = 1; i <= nrb; i++) {
466 m = (*ptL++) & (*ptR++);
467 PARITY_BLOCK(m);
468 n ^= m;
469 }
470
471 mask = 1;
472 for (i = 0; i < len % BIPEB; i++) {
473 n ^= (mask & *ptL & *ptR) >> i;
474 mask <<= 1;
475 }
476
477
478 if (n & 1)
479 BLOCK_ELM_GF2VEC(prod, j) |= MASK_POS_GF2VEC(j);
480 }
481
482 // return the result
483 return prod;
484 }
485
486 /****************************************************************************
487 **
488 *F ProdGF2MatGF2MatSimple( <ml>, <mr> ) . . . . product of two GF2 matrices
489 *F ProdGF2MatGF2MatAdvanced( <ml>, <mr>, <greaselevel>, <blocksize> )
490 ** . . product of twp GF2 matrices
491 **
492 ** 'ProdGF2MatGF2MatSimple' returns the product of the GF2 matrix <ml> and
493 ** the GF2 matrix <mr>. This simply calls ProdGF2VecGF2Mat once on each row.
494 **
495 ** ProdGF2MatGF2MatAdvanced uses the specified grease and blocking to
496 ** accelerate larger matrix multiplies. In this case, the matrix dimensions
497 ** must be compatible.
498 */
499
ProdGF2MatGF2MatSimple(Obj ml,Obj mr)500 static Obj ProdGF2MatGF2MatSimple(Obj ml, Obj mr)
501 {
502 Obj prod;
503 UInt i;
504 UInt len;
505 Obj row;
506 Obj rtype;
507 len = LEN_GF2MAT(ml);
508 prod = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(len));
509 SET_LEN_GF2MAT(prod, len);
510 if (IS_MUTABLE_OBJ(ml) || IS_MUTABLE_OBJ(mr)) {
511 SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT);
512 if (IS_MUTABLE_OBJ(ELM_GF2MAT(ml, 1)) ||
513 IS_MUTABLE_OBJ(ELM_GF2MAT(mr, 1)))
514 rtype = TYPE_LIST_GF2VEC_LOCKED;
515 else
516 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
517 }
518 else {
519 SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT_IMM);
520 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
521 }
522 for (i = 1; i <= len; i++) {
523 row = ProdGF2VecGF2Mat(ELM_GF2MAT(ml, i), mr);
524
525 // Since I'm going to put this vector into a matrix, I must lock its
526 // representation, so that it doesn't get rewritten over GF(2^k)
527 SetTypeDatObj(row, rtype);
528 SET_ELM_GF2MAT(prod, i, row);
529 CHANGED_BAG(prod);
530 TakeInterrupt();
531 }
532 return prod;
533 }
534
535
536 // Utility functions for the advanced matrix multiply code below
537
538
539 // extract nbits bits starting from position from in vector vptr
540 // return them as the nbits least significant bits in a UInt.
541 // Bits are always numbered least-significant first
542
getbits(const UInt * vptr,UInt from,UInt nbits)543 static inline UInt getbits(const UInt * vptr, UInt from, UInt nbits)
544 {
545 UInt wno = (from - 1) / BIPEB;
546 UInt word1 = vptr[wno];
547 UInt shift1 = (from - 1) % BIPEB;
548 UInt lbit = shift1 + nbits;
549 UInt word2;
550 if (lbit <= BIPEB) {
551 // range is all in one word
552 word1 <<= BIPEB - lbit;
553 word1 >>= BIPEB - nbits;
554 }
555 else {
556 // range is split across two words
557 word1 >>= shift1;
558 lbit -= BIPEB;
559 word2 = vptr[wno + 1];
560 word2 <<= BIPEB - lbit;
561 word2 >>= shift1 - lbit;
562 word1 |= word2;
563 }
564 return word1;
565 }
566
567 // To avoid having a lot of arguments to the recursive getgreasedata function,
568 // we put the things that don't change in the recursive call into this
569 // structure
570
571 struct greaseinfo {
572 UInt * pgtags;
573 UInt * pgbuf;
574 UInt nblocks;
575 UInt * pgrules;
576 const UInt ** prrows;
577 };
578
579
580 // Make if necessary the grease row for bits controlled by the data in g.
581 // Recursive so can't be inlined
getgreasedata(struct greaseinfo * g,UInt bits)582 static const UInt * getgreasedata(struct greaseinfo * g, UInt bits)
583 {
584 UInt x, y;
585 const UInt * ps;
586 UInt * pd;
587 const UInt * ps2;
588 UInt i;
589 UInt * pd1;
590 switch (g->pgtags[bits]) {
591 case 0:
592 // Need to make the row
593 x = g->pgrules[bits];
594 y = bits ^ (1 << x);
595 // make it by adding row x to grease vector indexed y
596 ps = g->prrows[x];
597 ps2 = getgreasedata(g, y);
598 pd1 = g->pgbuf + (bits - 3) * g->nblocks;
599 pd = pd1;
600 // time critical inner loop
601 for (i = g->nblocks; i > 0; i--)
602 *pd++ = *ps++ ^ *ps2++;
603 // record that we made it
604 g->pgtags[bits] = 1;
605 return pd1;
606
607 case 1:
608 // we've made this one already, so just return it
609 return g->pgbuf + (bits - 3) * g->nblocks;
610
611 case 2:
612 // This one does not need making, bits actually
613 // has just a single 1 bit in it
614 return g->prrows[g->pgrules[bits]];
615 }
616 return (UInt *)0; // can't actually get here; include the return to
617 // pacify compiler
618 }
619
620
621 static Obj
ProdGF2MatGF2MatAdvanced(Obj ml,Obj mr,UInt greasesize,UInt blocksize)622 ProdGF2MatGF2MatAdvanced(Obj ml, Obj mr, UInt greasesize, UInt blocksize)
623 {
624 Obj prod; // Product Matrix
625 UInt i, j, k, b; // Loop counters
626 UInt gs; // Actual level of grease for current block
627 const UInt * rptr; // Pointer to current row of ml
628 UInt bits; // current chunk of current row, for lookup in grease tables
629 const UInt * v; // pointer to computed grease vector
630 UInt len, rlen, ilen; // len = length of ml, ilen = row length of ml =
631 // length of mr, rlen = row length of mr
632 Obj row; // current row of ml, or row of prod when it is being built
633 Obj rtype; // type of rows of prod
634 Obj gbuf = (Obj)0; // grease buffer
635 Obj gtags = (Obj)0; // grease tags (whether that row is known yet
636 Obj grules = (Obj)0; // rules for making new grease vectors
637 UInt * pgrules; // pointer to contents of grules
638 UInt * pgtags = (UInt *)0; // pointer to contents of gtags
639 UInt * pgbuf = (UInt *)0; // pointer to grease buffer
640 UInt nwords; // number of words in a row of mr
641 UInt glen; // 1 << greasesize
642 UInt bs; // actual size of current block
643 UInt * pprow; // pointer into current row of prod
644 Obj lrowptrs; // cache of direct pointers to rows of ml
645 const UInt ** plrows; // and a direct pointer to that cache
646 Obj rrowptrs; // and for mr
647 const UInt ** prrows;
648 Obj prowptrs; // and for prod
649 UInt ** pprows;
650 struct greaseinfo g;
651
652 len = LEN_GF2MAT(ml);
653 row = ELM_GF2MAT(mr, 1);
654 rlen = LEN_GF2VEC(row);
655 ilen = LEN_GF2MAT(mr);
656 nwords = NUMBER_BLOCKS_GF2VEC(row);
657
658 // Make a zero product matrix
659 prod = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(len));
660 SET_LEN_GF2MAT(prod, len);
661 if (IS_MUTABLE_OBJ(ml) || IS_MUTABLE_OBJ(mr)) {
662 SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT);
663 if (IS_MUTABLE_OBJ(ELM_GF2MAT(ml, 1)) ||
664 IS_MUTABLE_OBJ(ELM_GF2MAT(mr, 1)))
665 rtype = TYPE_LIST_GF2VEC_LOCKED;
666 else
667 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
668 }
669 else {
670 SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT_IMM);
671 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
672 }
673
674
675 for (i = 1; i <= len; i++) {
676 NEW_GF2VEC(row, rtype, rlen);
677 SET_ELM_GF2MAT(prod, i, row);
678 CHANGED_BAG(prod);
679 }
680
681 // Cap greasesize and blocksize by the actual length
682 if (ilen < greasesize)
683 greasesize = ilen;
684 if (ilen < greasesize * blocksize)
685 blocksize = (ilen + greasesize - 1) / greasesize;
686
687
688 // calculate glen
689 glen = 1 << greasesize;
690
691 // Allocate memory
692
693 lrowptrs = NewBag(T_DATOBJ, sizeof(UInt *) * len);
694 rrowptrs = NewBag(T_DATOBJ, sizeof(UInt *) * ilen);
695 prowptrs = NewBag(T_DATOBJ, sizeof(UInt *) * len);
696
697 if (greasesize >= 2) {
698 gbuf =
699 NewBag(T_DATOBJ, sizeof(UInt) * nwords * (glen - 3) * blocksize);
700 gtags = NewBag(T_DATOBJ, sizeof(UInt) * glen * blocksize);
701 grules = NewBag(T_DATOBJ, sizeof(Int) * glen);
702
703
704 // From here no garbage collections
705
706 pgtags = (UInt *)ADDR_OBJ(gtags);
707 pgrules = (UInt *)ADDR_OBJ(grules);
708 pgbuf = (UInt *)ADDR_OBJ(gbuf);
709
710
711 // Calculate the greasing rules
712 for (j = 3; j < glen; j++)
713 for (i = 0; i < greasesize; i++)
714 if ((j & (1 << i)) != 0) {
715 pgrules[j] = i;
716 break;
717 }
718 for (j = 0; j < greasesize; j++)
719 pgrules[1 << j] = j;
720
721 // fill in some more bits of g
722 g.pgrules = pgrules;
723 g.nblocks = nwords;
724 }
725
726 // Take direct pointers to all the parts of all the matrices to avoid
727 // multiple indirection overheads
728 plrows = (const UInt **)ADDR_OBJ(lrowptrs);
729 prrows = (const UInt **)ADDR_OBJ(rrowptrs);
730 pprows = (UInt **)ADDR_OBJ(prowptrs);
731
732 for (i = 0; i < len; i++) {
733 plrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, i + 1));
734 pprows[i] = BLOCKS_GF2VEC(ELM_GF2MAT(prod, i + 1));
735 }
736 for (i = 0; i < ilen; i++)
737 prrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mr, i + 1));
738
739
740 // OK, finally ready to start work
741 // loop over blocks
742 for (b = 1; b <= ilen; b += blocksize * greasesize) {
743 // last block may be a small one
744 bs = blocksize;
745 if ((b + bs * greasesize) > ilen)
746 bs = (ilen - b + greasesize) / greasesize;
747
748 // If we're greasing, start afresh
749 if (greasesize > 1) {
750 for (k = 0; k < bs; k++) {
751 for (j = 0; j < 1 << greasesize; j++)
752 pgtags[k * glen + j] = 0;
753 // powers of 2 correspond to rows of mr
754 for (j = 0; j < greasesize; j++)
755 pgtags[k * glen + (1 << j)] = 2;
756 }
757 }
758
759 // For each block, we run through rows of ml & prod
760 for (j = 1; j <= len; j++) {
761 // get pointers
762 rptr = plrows[j - 1];
763 pprow = pprows[j - 1];
764
765 // Now within the block, we have multiple grease-units, run
766 // through them
767 for (i = 0; i < bs; i++) {
768 // start of current grease unit
769 k = b + i * greasesize;
770
771 // last unit of last block may be short
772 gs = greasesize;
773 if (k + gs > ilen)
774 gs = ilen - k + 1;
775
776 // find the appropriate parts of grease tags
777 // grease buffer and mr. Store in g
778
779 if (gs > 1) {
780 g.pgtags = pgtags + glen * i;
781 g.pgbuf = pgbuf + (glen - 3) * nwords * i;
782 g.prrows = prrows + k - 1;
783 }
784
785 // get a chunk from a row of ml
786 bits = getbits(rptr, k, gs);
787
788 // 0 means nothing to do
789 if (bits == 0)
790 continue;
791 else if (bits == 1) // handle this one specially to speed
792 // up the greaselevel 1 case
793 v = prrows[k - 1]; // -1 is because k is 1-based index
794 else
795 v = getgreasedata(
796 &g, bits); // The main case
797 // This function should be inlined
798 AddGF2VecToGF2Vec(pprow, v, rlen);
799 }
800 }
801
802 // Allow GAP to respond to Ctrl-C
803 if (TakeInterrupt()) {
804 // Might have been a garbage collection, reload everything
805 if (greasesize >= 2) {
806 pgtags = (UInt *)ADDR_OBJ(gtags);
807 pgrules = (UInt *)ADDR_OBJ(grules);
808 pgbuf = (UInt *)ADDR_OBJ(gbuf);
809 // fill in some more bits of g
810 g.pgrules = pgrules;
811 g.nblocks = nwords;
812 }
813 plrows = (const UInt **)ADDR_OBJ(lrowptrs);
814 prrows = (const UInt **)ADDR_OBJ(rrowptrs);
815 pprows = (UInt **)ADDR_OBJ(prowptrs);
816 for (i = 0; i < len; i++) {
817 plrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, i + 1));
818 pprows[i] = BLOCKS_GF2VEC(ELM_GF2MAT(prod, i + 1));
819 }
820 for (i = 0; i < ilen; i++)
821 prrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mr, i + 1));
822 }
823 }
824 return prod;
825 }
826
827 /****************************************************************************
828 **
829 *F FuncPROD_GF2VEC_ANYMAT( <self>, <v>, <m>)
830 **
831 ** method to handle vector*plain list of GF2Vectors reasonably efficiently.
832 */
FuncPROD_GF2VEC_ANYMAT(Obj self,Obj vec,Obj mat)833 static Obj FuncPROD_GF2VEC_ANYMAT(Obj self, Obj vec, Obj mat)
834 {
835 Obj res;
836 UInt len;
837 UInt len1;
838 Obj row1;
839 UInt i;
840 UInt block = 0;
841
842 len = LEN_GF2VEC(vec);
843 if (len > LEN_PLIST(mat))
844 len = LEN_PLIST(mat);
845
846 // Get the first row, to establish the size of the result
847 row1 = ELM_PLIST(mat, 1);
848 if (!IS_GF2VEC_REP(row1))
849 return TRY_NEXT_METHOD;
850 len1 = LEN_GF2VEC(row1);
851
852 // create the result space
853 NEW_GF2VEC(res,
854 (IS_MUTABLE_OBJ(vec) || IS_MUTABLE_OBJ(row1))
855 ? TYPE_LIST_GF2VEC
856 : TYPE_LIST_GF2VEC_IMM,
857 len1);
858
859 // Finally, we start work
860 for (i = 1; i <= len; i++) {
861 if (i % BIPEB == 1)
862 block = CONST_BLOCK_ELM_GF2VEC(vec, i);
863 if (block & MASK_POS_GF2VEC(i)) {
864 row1 = ELM_PLIST(mat, i);
865 if (!IS_GF2VEC_REP(row1))
866 return TRY_NEXT_METHOD;
867 AddPartialGF2VecGF2Vec(res, res, row1, 1);
868 }
869 }
870 return res;
871 }
872
873 /****************************************************************************
874 **
875 *F InversePlistGF2VecsDesstructive( <list> )
876 **
877 ** This is intended to form the core of a method for InverseOp.
878 ** by this point it should be checked that list is a plain list of GF2
879 ** vectors of equal lengths.
880 */
InversePlistGF2VecsDesstructive(Obj list)881 static Obj InversePlistGF2VecsDesstructive(Obj list)
882 {
883 UInt len; // dimension
884 Obj inv; // result
885 Obj row; // row vector
886 Obj old; // row from <mat>
887 Obj tmp; // temporary
888 UInt * ptQ; // data block of <row>
889 const UInt * ptP; // data block of source row
890 const UInt * end; // end marker
891 const UInt * end2; // end marker
892 UInt i; // loop variable
893 UInt k; // loop variable
894
895 len = LEN_PLIST(list);
896
897 // create the identity matrix
898 tmp = NEW_PLIST(T_PLIST, len);
899 for (i = len; 0 < i; i--) {
900 NEW_GF2VEC(row, TYPE_LIST_GF2VEC, len);
901 BLOCK_ELM_GF2VEC(row, i) |= MASK_POS_GF2VEC(i);
902 SET_ELM_PLIST(tmp, i, row);
903 CHANGED_BAG(tmp);
904 }
905 SET_LEN_PLIST(tmp, len);
906 inv = tmp;
907
908 // now start with ( id | mat ) towards ( inv | id )
909 for (k = 1; k <= len; k++) {
910
911 // find a nonzero entry in column <k>
912 for (i = k; i <= len; i++) {
913 row = ELM_PLIST(list, i);
914 if (CONST_BLOCK_ELM_GF2VEC(row, k) & MASK_POS_GF2VEC(k))
915 break;
916 }
917 if (i > len) {
918 return Fail;
919 }
920 if (i != k) {
921 row = ELM_PLIST(list, i);
922 SET_ELM_PLIST(list, i, ELM_PLIST(list, k));
923 SET_ELM_PLIST(list, k, row);
924 row = ELM_PLIST(inv, i);
925 SET_ELM_PLIST(inv, i, ELM_PLIST(inv, k));
926 SET_ELM_PLIST(inv, k, row);
927 }
928
929 // clear entries
930 old = ELM_PLIST(list, k);
931 end = CONST_BLOCKS_GF2VEC(old) + ((len + BIPEB - 1) / BIPEB);
932 for (i = 1; i <= len; i++) {
933 if (i == k)
934 continue;
935 row = ELM_PLIST(list, i);
936 if (CONST_BLOCK_ELM_GF2VEC(row, k) & MASK_POS_GF2VEC(k)) {
937
938 // clear <mat>
939 ptQ = &(BLOCK_ELM_GF2VEC(row, k));
940 ptP = &(CONST_BLOCK_ELM_GF2VEC(old, k));
941 while (ptP < end) {
942 *ptQ++ ^= *ptP++;
943 }
944
945 // modify <inv>
946 row = ELM_PLIST(inv, i);
947 ptQ = BLOCKS_GF2VEC(row);
948 row = ELM_PLIST(inv, k);
949 ptP = CONST_BLOCKS_GF2VEC(row);
950 end2 = ptP + ((len + BIPEB - 1) / BIPEB);
951 while (ptP < end2) {
952 *ptQ++ ^= *ptP++;
953 }
954 }
955 }
956 TakeInterrupt();
957 }
958 return inv;
959 }
960
961
962 /****************************************************************************
963 **
964 *F InverseGF2Mat( <mat> ) . . . . . . . . . . . . . . inverse of GF2 matrix
965 **
966 ** This should be improved to work with mutable GF2 matrices
967 **
968 */
969
InverseGF2Mat(Obj mat,UInt mut)970 static Obj InverseGF2Mat(Obj mat, UInt mut)
971 {
972 UInt len; // dimension
973 Obj inv; // result
974 Obj row; // row vector
975 Obj tmp; // temporary
976 UInt i; // loop variable
977 Obj old; // row from <mat>
978 const UInt * ptQ; // data block of <row>
979 UInt * ptP; // data block of source row
980 UInt * end; // end marker
981 Obj rtype;
982
983 // make a structural copy of <mat> as list of GF2 vectors
984 len = LEN_GF2MAT(mat);
985
986 // special routes for very small matrices
987 if (len == 0) {
988 return CopyObj(mat, 1);
989 }
990 if (len == 1) {
991 row = ELM_GF2MAT(mat, 1);
992 if (CONST_BLOCKS_GF2VEC(row)[0] & 1) {
993 return CopyObj(mat, 1);
994 }
995 else
996 return Fail;
997 }
998
999 tmp = NEW_PLIST(T_PLIST, len);
1000 for (i = len; 0 < i; i--) {
1001 old = ELM_GF2MAT(mat, i);
1002 NEW_GF2VEC(row, TYPE_LIST_GF2VEC_IMM, len);
1003 ptQ = CONST_BLOCKS_GF2VEC(old);
1004 ptP = BLOCKS_GF2VEC(row);
1005 end = ptP + ((len + BIPEB - 1) / BIPEB);
1006 while (ptP < end)
1007 *ptP++ = *ptQ++;
1008 SET_ELM_PLIST(tmp, i, row);
1009 CHANGED_BAG(tmp);
1010 }
1011 SET_LEN_PLIST(tmp, len);
1012 inv = InversePlistGF2VecsDesstructive(tmp);
1013 if (inv == Fail)
1014 return inv;
1015
1016 // convert list <inv> into a matrix
1017 ResizeBag(inv, SIZE_PLEN_GF2MAT(len));
1018 if (mut == 2 || (mut == 1 && IS_MUTABLE_OBJ(mat) &&
1019 IS_MUTABLE_OBJ(ELM_GF2MAT(mat, 1))))
1020 rtype = TYPE_LIST_GF2VEC_LOCKED;
1021 else
1022 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
1023 for (i = len; 0 < i; i--) {
1024 row = ELM_PLIST(inv, i);
1025 SET_TYPE_POSOBJ(row, rtype);
1026 SET_ELM_GF2MAT(inv, i, row);
1027 }
1028 SET_LEN_GF2MAT(inv, len);
1029 RetypeBag(inv, T_POSOBJ);
1030 SET_TYPE_POSOBJ(inv, (mut == 2 || (mut == 1 && IS_MUTABLE_OBJ(mat)))
1031 ? TYPE_LIST_GF2MAT
1032 : TYPE_LIST_GF2MAT_IMM);
1033 return inv;
1034 }
1035
1036 /****************************************************************************
1037 **
1038 *F ShallowCopyVecGF2( <vec> )
1039 **
1040 */
1041
ShallowCopyVecGF2(Obj vec)1042 Obj ShallowCopyVecGF2(Obj vec)
1043 {
1044 Obj copy;
1045 UInt len;
1046 const UInt * ptrS;
1047 UInt * ptrD;
1048 len = LEN_GF2VEC(vec);
1049 NEW_GF2VEC(copy, TYPE_LIST_GF2VEC, len);
1050 ptrS = CONST_BLOCKS_GF2VEC(vec);
1051 ptrD = BLOCKS_GF2VEC(copy);
1052 memcpy(ptrD, ptrS, NUMBER_BLOCKS_GF2VEC(vec) * sizeof(UInt));
1053 return copy;
1054 }
1055
1056 /****************************************************************************
1057 **
1058 *F SemiEchelonPlistGF2Vecs( <mat>, <transformations-needed> )
1059 **
1060 ** The matrix needs to have mutable rows, so it can't be a GF2 mat
1061 **
1062 ** This has changed. There should now be a method for mutable GF2mats as
1063 ** well.
1064 **
1065 ** This function DOES NOT CHECK that the rows are all GF2 vectors
1066 **
1067 ** Does not copy the matrix, may destroy it, may include some
1068 ** of the rows among the returned vectors
1069 */
1070
1071
1072 static UInt RNheads, RNvectors, RNcoeffs, RNrelns;
1073
1074
SemiEchelonListGF2Vecs(Obj mat,UInt TransformationsNeeded)1075 static Obj SemiEchelonListGF2Vecs(Obj mat, UInt TransformationsNeeded)
1076 {
1077 UInt nrows, ncols;
1078 UInt i, j, h;
1079 Obj heads, vectors, coeffs = 0, relns = 0;
1080 UInt nvecs, nrels = 0;
1081 Obj coeffrow = 0;
1082 Obj row;
1083 UInt *rowp, *coeffrowp = 0;
1084 Obj res;
1085 nrows = LEN_PLIST(mat);
1086 ncols = LEN_GF2VEC(ELM_PLIST(mat, 1));
1087 heads = NEW_PLIST(T_PLIST_CYC, ncols);
1088 SET_LEN_PLIST(heads, ncols);
1089 vectors = NEW_PLIST(T_PLIST_TAB_RECT, nrows);
1090 nvecs = 0;
1091 if (TransformationsNeeded) {
1092 coeffs = NEW_PLIST(T_PLIST_TAB_RECT, nrows);
1093 relns = NEW_PLIST(T_PLIST_TAB_RECT, nrows);
1094 nrels = 0;
1095 }
1096 for (i = 1; i <= ncols; i++)
1097 SET_ELM_PLIST(heads, i, INTOBJ_INT(0));
1098 for (i = 1; i <= nrows; i++) {
1099 row = ELM_PLIST(mat, i);
1100 if (TransformationsNeeded) {
1101 NEW_GF2VEC(coeffrow, TYPE_LIST_GF2VEC, nrows);
1102 BLOCK_ELM_GF2VEC(coeffrow, i) |= MASK_POS_GF2VEC(i);
1103 }
1104
1105 // No garbage collection risk from here
1106 rowp = BLOCKS_GF2VEC(row);
1107 if (TransformationsNeeded)
1108 coeffrowp = BLOCKS_GF2VEC(coeffrow);
1109 for (j = 1; j <= ncols; j++) {
1110 h = INT_INTOBJ(ELM_PLIST(heads, j));
1111 if (h != 0) {
1112 if (rowp[(j - 1) / BIPEB] & MASK_POS_GF2VEC(j)) {
1113 AddGF2VecToGF2Vec(
1114 rowp, CONST_BLOCKS_GF2VEC(ELM_PLIST(vectors, h)),
1115 ncols);
1116 if (TransformationsNeeded)
1117 AddGF2VecToGF2Vec(
1118 coeffrowp,
1119 CONST_BLOCKS_GF2VEC(ELM_PLIST(coeffs, h)), nrows);
1120 }
1121 }
1122 }
1123 j = 1;
1124 while (j <= ncols && !*rowp) {
1125 j += BIPEB;
1126 rowp++;
1127 }
1128 while (j <= ncols && !(*rowp & MASK_POS_GF2VEC(j)))
1129 j++;
1130
1131 // garbage collection OK again after here
1132 if (j <= ncols) {
1133 SET_ELM_PLIST(vectors, ++nvecs, row);
1134 CHANGED_BAG(vectors); // Could be an old bag by now. Max.
1135 SET_LEN_PLIST(vectors, nvecs);
1136 SET_ELM_PLIST(heads, j, INTOBJ_INT(nvecs));
1137 if (TransformationsNeeded) {
1138 SET_ELM_PLIST(coeffs, nvecs, coeffrow);
1139 CHANGED_BAG(coeffs); // Could be an old bag by now. Max.
1140 SET_LEN_PLIST(coeffs, nvecs);
1141 }
1142 }
1143 else if (TransformationsNeeded) {
1144 SET_ELM_PLIST(relns, ++nrels, coeffrow);
1145 CHANGED_BAG(relns); // Could be an old bag by now. Max.
1146 SET_LEN_PLIST(relns, nrels);
1147 }
1148 TakeInterrupt();
1149 }
1150 if (RNheads == 0) {
1151 RNheads = RNamName("heads");
1152 RNvectors = RNamName("vectors");
1153 }
1154 res = NEW_PREC(TransformationsNeeded ? 4 : 2);
1155 AssPRec(res, RNheads, heads);
1156 AssPRec(res, RNvectors, vectors);
1157 if (LEN_PLIST(vectors) == 0)
1158 RetypeBag(vectors, T_PLIST_EMPTY);
1159 if (TransformationsNeeded) {
1160 if (RNcoeffs == 0) {
1161 RNcoeffs = RNamName("coeffs");
1162 RNrelns = RNamName("relations");
1163 }
1164 AssPRec(res, RNcoeffs, coeffs);
1165 if (LEN_PLIST(coeffs) == 0)
1166 RetypeBag(coeffs, T_PLIST_EMPTY);
1167 AssPRec(res, RNrelns, relns);
1168 if (LEN_PLIST(relns) == 0)
1169 RetypeBag(relns, T_PLIST_EMPTY);
1170 }
1171 SortPRecRNam(res, 0);
1172 return res;
1173 }
1174
1175 /****************************************************************************
1176 **
1177 *F UInt TriangulizeListGF2Vecs( <mat>, <clearup> ) -- returns the rank
1178 **
1179 ** Again should add a method to work with mutable GF2 matrices
1180 **
1181 */
1182
TriangulizeListGF2Vecs(Obj mat,UInt clearup)1183 static UInt TriangulizeListGF2Vecs(Obj mat, UInt clearup)
1184 {
1185 UInt nrows;
1186 UInt ncols;
1187 UInt workcol;
1188 UInt workrow;
1189 UInt rank;
1190 Obj row, row2;
1191 const UInt * rowp;
1192 UInt * row2p;
1193 UInt block;
1194 UInt mask;
1195 UInt j;
1196 nrows = LEN_PLIST(mat);
1197 ncols = LEN_GF2VEC(ELM_PLIST(mat, 1));
1198 rank = 0;
1199
1200 // Nothing here can cause a garbage collection
1201
1202 for (workcol = 1; workcol <= ncols; workcol++) {
1203 block = (workcol - 1) / BIPEB;
1204 mask = MASK_POS_GF2VEC(workcol);
1205 for (workrow = rank + 1;
1206 workrow <= nrows &&
1207 !(CONST_BLOCKS_GF2VEC(ELM_PLIST(mat, workrow))[block] & mask);
1208 workrow++)
1209 ;
1210 if (workrow <= nrows) {
1211 rank++;
1212 row = ELM_PLIST(mat, workrow);
1213 if (workrow != rank) {
1214 SET_ELM_PLIST(mat, workrow, ELM_PLIST(mat, rank));
1215 SET_ELM_PLIST(mat, rank, row);
1216 }
1217 rowp = CONST_BLOCKS_GF2VEC(row);
1218 if (clearup)
1219 for (j = 1; j < rank; j++) {
1220 row2 = ELM_PLIST(mat, j);
1221 row2p = BLOCKS_GF2VEC(row2);
1222 if (row2p[block] & mask)
1223 AddGF2VecToGF2Vec(row2p, rowp, ncols);
1224 }
1225 for (j = workrow + 1; j <= nrows; j++) {
1226 row2 = ELM_PLIST(mat, j);
1227 row2p = BLOCKS_GF2VEC(row2);
1228 if (row2p[block] & mask)
1229 AddGF2VecToGF2Vec(row2p, rowp, ncols);
1230 }
1231 }
1232 TakeInterrupt();
1233 }
1234 return rank;
1235 }
1236
1237 /****************************************************************************
1238 **
1239 *F * * * * * * * * * * * * conversion functions * * * * * * * * * * * * * *
1240 */
1241
1242
1243 /****************************************************************************
1244 **
1245 *F PlainGF2Vec( <list> ) . . . . convert a GF2 vector into an ordinary list
1246 **
1247 ** 'PlainGF2Vec' converts the GF2 vector <list> to a plain list.
1248 */
1249 static Obj IsLockedRepresentationVector;
1250
1251
PlainGF2Vec(Obj list)1252 static void PlainGF2Vec(Obj list)
1253 {
1254 Int len; // length of <list>
1255 UInt i; // loop variable
1256 Obj first = 0; // first entry
1257
1258 // check for representation lock
1259 if (True == DoFilter(IsLockedRepresentationVector, list))
1260 ErrorMayQuit("Cannot convert a locked GF2 vector into a plain list",
1261 0, 0);
1262
1263 // resize the list and retype it, in this order
1264 len = LEN_GF2VEC(list);
1265
1266 RetypeBagSM(list, (len == 0) ? T_PLIST_EMPTY : T_PLIST_FFE);
1267
1268 GROW_PLIST(list, (UInt)len);
1269 SET_LEN_PLIST(list, len);
1270
1271 // keep the first entry because setting the second destroys the first
1272 if (len == 0)
1273 SET_ELM_PLIST(list, 1, 0);
1274 else
1275 first = ELM_GF2VEC(list, 1);
1276
1277 // wipe out the first entry of the GF2 vector (which becomes the second
1278 // entry of the plain list, in case the list has length 1.
1279 if (len == 1)
1280 SET_ELM_PLIST(list, 2, 0);
1281
1282 // replace the bits by 'GF2One' or 'GF2Zero' as the case may be
1283 // this must of course be done from the end of the list backwards
1284 for (i = len; 1 < i; i--)
1285 SET_ELM_PLIST(list, i, ELM_GF2VEC(list, i));
1286 if (len != 0)
1287 SET_ELM_PLIST(list, 1, first);
1288
1289 CHANGED_BAG(list);
1290 }
1291
1292
1293 /****************************************************************************
1294 **
1295 *F PlainGF2Mat( <list> ) . . . . convert a GF2 matrix into an ordinary list
1296 **
1297 ** 'PlainGF2Mat' converts the GF2 matrix <list> to a plain list.
1298 */
PlainGF2Mat(Obj list)1299 static void PlainGF2Mat(Obj list)
1300 {
1301 Int len; // length of <list>
1302 UInt i; // loop variable
1303
1304 // resize the list and retype it, in this order
1305 len = LEN_GF2MAT(list);
1306 RetypeBagSM(list, T_PLIST);
1307 SET_LEN_PLIST(list, len);
1308
1309 // shift the entries to the left
1310 for (i = 1; i <= len; i++) {
1311 SET_ELM_PLIST(list, i, ELM_GF2MAT(list, i));
1312 }
1313 SHRINK_PLIST(list, len);
1314 CHANGED_BAG(list);
1315 }
1316
1317
1318 /****************************************************************************
1319 **
1320 *F ConvGF2Vec( <list> ) . . . . . . convert a list into a GF2 vector object
1321 */
ConvGF2Vec(Obj list)1322 static void ConvGF2Vec(Obj list)
1323 {
1324 Int len; // logical length of the vector
1325 Int i; // loop variable
1326 UInt block; // one block of the boolean list
1327 UInt bit; // one bit of a block
1328 Obj x;
1329
1330 // already in the correct representation
1331 if (IS_GF2VEC_REP(list)) {
1332 return;
1333 }
1334
1335 // Otherwise make it a plain list so that we will know where it keeps
1336 // its data -- could do much better in the case of GF(2^n) vectors that
1337 // actually lie over GF(2)
1338
1339 if (IS_VEC8BIT_REP(list))
1340 PlainVec8Bit(list);
1341 else
1342 PLAIN_LIST(list);
1343
1344 // change its representation
1345 len = LEN_PLIST(list);
1346
1347 // We may have to resize the bag now because a length 1
1348 // plain list is shorter than a length 1 GF2VEC
1349 if (SIZE_PLEN_GF2VEC(len) > SIZE_OBJ(list))
1350 ResizeBag(list, SIZE_PLEN_GF2VEC(len));
1351
1352 // now do the work
1353 block = 0;
1354 bit = 1;
1355 for (i = 1; i <= len; i++) {
1356 x = ELM_PLIST(list, i);
1357 if (x == GF2One)
1358 block |= bit;
1359 else if (x != GF2Zero) {
1360 // might be GF(2) elt written over bigger field
1361 if (EQ(x, GF2One))
1362 block |= bit;
1363 else if (!EQ(x, GF2Zero))
1364 ErrorMayQuit(
1365 "COPY_GF2VEC: argument must be a list of GF2 elements",
1366 0L, 0L);
1367 }
1368
1369 bit = bit << 1;
1370 if (bit == 0 || i == len) {
1371 BLOCK_ELM_GF2VEC(list, i) = block;
1372 block = 0;
1373 bit = 1;
1374 }
1375 }
1376
1377 // retype and resize bag
1378 ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(len));
1379 SET_LEN_GF2VEC(list, len);
1380 if (IS_PLIST_MUTABLE(list)) {
1381 SetTypeDatObj(list, TYPE_LIST_GF2VEC);
1382 }
1383 else {
1384 SetTypeDatObj(list, TYPE_LIST_GF2VEC_IMM);
1385 }
1386 RetypeBag(list, T_DATOBJ);
1387 }
1388
1389
1390 /****************************************************************************
1391 **
1392 *F FuncCONV_GF2VEC( <self>, <list> ) . . . . . convert into a GF2 vector rep
1393 */
FuncCONV_GF2VEC(Obj self,Obj list)1394 static Obj FuncCONV_GF2VEC(Obj self, Obj list)
1395 {
1396 // check whether <list> is a GF2 vector
1397 ConvGF2Vec(list);
1398
1399 // return nothing
1400 return 0;
1401 }
1402
1403
1404 /****************************************************************************
1405 **
1406 *F NewGF2Vec( <list> ) . . . . . . convert a list into a GF2 vector object
1407 **
1408 ** This is a non-destructive counterpart of ConvGF2Vec
1409 */
NewGF2Vec(Obj list)1410 static Obj NewGF2Vec(Obj list)
1411 {
1412 Int len; // logical length of the vector
1413 Int i; // loop variable
1414 UInt block; // one block of the boolean list
1415 UInt bit; // one bit of a block
1416 Obj x;
1417 Obj res; // resulting GF2 vector object
1418
1419 // already in the correct representation
1420 if (IS_GF2VEC_REP(list)) {
1421 res = ShallowCopyVecGF2(list);
1422 if (!IS_MUTABLE_OBJ(list))
1423 SetTypeDatObj(res, TYPE_LIST_GF2VEC_IMM);
1424 return res;
1425 }
1426
1427 if (!IS_LIST(list)) {
1428 ErrorMayQuit("COPY_GF2VEC: argument must be a list of GF2 elements",
1429 0L, 0L);
1430 }
1431 if (!IS_PLIST(list)) {
1432 list = SHALLOW_COPY_OBJ(list);
1433 // TODO: if list is in 8bit rep, we could do better
1434 if (IS_VEC8BIT_REP(list))
1435 PlainVec8Bit(list);
1436 else
1437 PLAIN_LIST(list);
1438 }
1439
1440 len = LEN_PLIST(list);
1441 NEW_GF2VEC(res, TYPE_LIST_GF2VEC, len);
1442
1443 // now do the work
1444 block = 0;
1445 bit = 1;
1446 for (i = 1; i <= len; i++) {
1447 x = ELM_PLIST(list, i);
1448 if (x == GF2One)
1449 block |= bit;
1450 else if (x != GF2Zero) {
1451 // might be GF(2) elt written over bigger field
1452 if (EQ(x, GF2One))
1453 block |= bit;
1454 else if (!EQ(x, GF2Zero))
1455 ErrorMayQuit(
1456 "COPY_GF2VEC: argument must be a list of GF2 elements",
1457 0L, 0L);
1458 }
1459
1460 bit = bit << 1;
1461 if (bit == 0 || i == len) {
1462 BLOCK_ELM_GF2VEC(res, i) = block; // only changed list to res
1463 block = 0;
1464 bit = 1;
1465 }
1466 }
1467
1468 // mutability should be inherited from the argument
1469 if (IS_PLIST_MUTABLE(list))
1470 SetTypeDatObj(res, TYPE_LIST_GF2VEC);
1471 else
1472 SetTypeDatObj(res, TYPE_LIST_GF2VEC_IMM);
1473
1474 return res;
1475 }
1476
1477
1478 /****************************************************************************
1479 **
1480 *F FuncCOPY_GF2VEC( <self>, <list> ) . . . . . convert into a GF2 vector rep
1481 **
1482 ** This is a non-destructive counterpart of FuncCONV_GF2VEC
1483 */
FuncCOPY_GF2VEC(Obj self,Obj list)1484 static Obj FuncCOPY_GF2VEC(Obj self, Obj list)
1485 {
1486 // check whether <list> is a GF2 vector
1487 list = NewGF2Vec(list);
1488
1489 return list;
1490 }
1491
1492 /****************************************************************************
1493 **
1494 *F FuncCONV_GF2MAT (<self>, <list> ) . . . convert into a GF2 matrix rep
1495 **
1496 ** <list> should be a a list of compressed GF2 vectors
1497 **
1498 */
FuncCONV_GF2MAT(Obj self,Obj list)1499 static Obj FuncCONV_GF2MAT(Obj self, Obj list)
1500 {
1501 UInt len, i;
1502 Obj tmp;
1503 UInt mut;
1504 len = LEN_LIST(list);
1505 if (len == 0)
1506 return (Obj)0;
1507
1508 PLAIN_LIST(list);
1509 GROW_PLIST(list, len + 1);
1510 for (i = len; i > 0; i--) {
1511 tmp = ELM_PLIST(list, i);
1512 if (!IS_GF2VEC_REP(tmp)) {
1513 int j;
1514 for (j = i + 1; j <= len; j++) {
1515 tmp = ELM_PLIST(list, j + 1);
1516 SET_ELM_PLIST(list, j, tmp);
1517 }
1518 ErrorMayQuit("CONV_GF2MAT: argument must be a list of compressed "
1519 "GF2 vectors",
1520 0L, 0L);
1521 }
1522 SetTypeDatObj(tmp, IS_MUTABLE_OBJ(tmp) ? TYPE_LIST_GF2VEC_LOCKED
1523 : TYPE_LIST_GF2VEC_IMM_LOCKED);
1524 SET_ELM_PLIST(list, i + 1, tmp);
1525 }
1526 SET_ELM_PLIST(list, 1, INTOBJ_INT(len));
1527 mut = IS_PLIST_MUTABLE(list);
1528 RetypeBag(list, T_POSOBJ);
1529 SET_TYPE_POSOBJ(list, mut ? TYPE_LIST_GF2MAT : TYPE_LIST_GF2MAT_IMM);
1530 return (Obj)0;
1531 }
1532
1533
1534 /****************************************************************************
1535 **
1536 *F FuncPLAIN_GF2VEC( <self>, <list> ) . . . convert back into ordinary list
1537 */
FuncPLAIN_GF2VEC(Obj self,Obj list)1538 static Obj FuncPLAIN_GF2VEC(Obj self, Obj list)
1539 {
1540 // check whether <list> is a GF2 vector
1541 if (!IS_GF2VEC_REP(list)) {
1542 RequireArgument("PLAIN_GF2VEC", list, "must be a GF2 vector");
1543 }
1544 PlainGF2Vec(list);
1545
1546 // return nothing
1547 return 0;
1548 }
1549
1550
1551 /****************************************************************************
1552 **
1553 *F revertbits -- utility function to reverse bit orders
1554 */
1555
1556
1557 // A list of flip values for bytes (i.e. ..xyz -> zyx..)
1558
1559 static const UInt1 revertlist[] = {
1560 0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
1561 8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
1562 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,
1563 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252,
1564 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242,
1565 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250,
1566 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246,
1567 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254,
1568 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241,
1569 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249,
1570 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245,
1571 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253,
1572 3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243,
1573 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251,
1574 7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247,
1575 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255
1576 };
1577
1578 // Takes an UInt a on n bits and returns the Uint obtained by reverting the
1579 // bits
revertbits(UInt a,Int n)1580 static UInt revertbits(UInt a, Int n)
1581 {
1582 UInt b, c;
1583 b = 0;
1584 while (n > 8) {
1585 c = a & 0xff; // last byte
1586 a = a >> 8;
1587 b = b << 8;
1588 b += (UInt)revertlist[(UInt1)c]; // add flipped
1589 n -= 8;
1590 }
1591 // cope with the last n bits
1592 a &= 0xff;
1593 b = b << n;
1594 c = (UInt)revertlist[(UInt1)a];
1595 c = c >> (8 - n);
1596 b += c;
1597 return b;
1598 }
1599
1600 /****************************************************************************
1601 **
1602 *F Cmp_GF2Vecs( <vl>, <vr> ) compare GF2 vectors -- internal
1603 ** returns -1, 0 or 1
1604 */
Cmp_GF2VEC_GF2VEC(Obj vl,Obj vr)1605 static Int Cmp_GF2VEC_GF2VEC(Obj vl, Obj vr)
1606 {
1607 UInt i; // loop variable
1608 const UInt * bl; // block of <vl>
1609 const UInt * br; // block of <vr>
1610 UInt len, lenl, lenr; // length of the list
1611 UInt a, b, nb;
1612
1613 // get and check the length
1614 lenl = LEN_GF2VEC(vl);
1615 lenr = LEN_GF2VEC(vr);
1616 nb = NUMBER_BLOCKS_GF2VEC(vl);
1617 a = NUMBER_BLOCKS_GF2VEC(vr);
1618 if (a < nb) {
1619 nb = a;
1620 }
1621
1622 // check all blocks
1623 bl = CONST_BLOCKS_GF2VEC(vl);
1624 br = CONST_BLOCKS_GF2VEC(vr);
1625 for (i = nb; 1 < i; i--, bl++, br++) {
1626 // comparison is numeric of the reverted lists
1627 if (*bl != *br) {
1628 a = revertbits(*bl, BIPEB);
1629 b = revertbits(*br, BIPEB);
1630 if (a < b)
1631 return -1;
1632 else
1633 return 1;
1634 }
1635 }
1636
1637
1638 // The last block remains
1639 len = lenl;
1640 if (len > lenr) {
1641 len = lenr;
1642 }
1643
1644 // are both vectors length 0?
1645 if (len == 0)
1646 return 0;
1647
1648 // is there still a full block in common?
1649 len = len % BIPEB;
1650 if (len == 0) {
1651 a = revertbits(*bl, BIPEB);
1652 b = revertbits(*br, BIPEB);
1653 }
1654 else {
1655 a = revertbits(*bl, len);
1656 b = revertbits(*br, len);
1657 }
1658
1659 if (a < b)
1660 return -1;
1661 if (a > b)
1662 return 1;
1663
1664 // blocks still the same --left length must be smaller to be true
1665 if (lenr > lenl)
1666 return -1;
1667 if (lenl > lenr)
1668 return 1;
1669
1670 return 0;
1671 }
1672
1673
1674 /****************************************************************************
1675 **
1676 *F FuncEQ_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) test equality of GF2 vectors
1677 */
FuncEQ_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)1678 static Obj FuncEQ_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
1679 {
1680 // we can do this case MUCH faster if we just want equality
1681 if (LEN_GF2VEC(vl) != LEN_GF2VEC(vr))
1682 return False;
1683 return (Cmp_GF2VEC_GF2VEC(vl, vr) == 0) ? True : False;
1684 }
1685
1686
1687 /****************************************************************************
1688 **
1689 *F FuncLEN_GF2VEC( <self>, <list> ) . . . . . . . . length of a GF2 vector
1690 */
FuncLEN_GF2VEC(Obj self,Obj list)1691 static Obj FuncLEN_GF2VEC(Obj self, Obj list)
1692 {
1693 return INTOBJ_INT(LEN_GF2VEC(list));
1694 }
1695
1696
1697 /****************************************************************************
1698 **
1699 *F FuncELM0_GF2VEC( <self>, <list>, <pos> ) . select an elm of a GF2 vector
1700 **
1701 ** 'ELM0_GF2VEC' returns the element at the position <pos> of the boolean
1702 ** list <list>, or `Fail' if <list> has no assigned object at <pos>. It is
1703 ** the responsibility of the caller to ensure that <pos> is a positive
1704 ** integer.
1705 */
FuncELM0_GF2VEC(Obj self,Obj list,Obj pos)1706 static Obj FuncELM0_GF2VEC(Obj self, Obj list, Obj pos)
1707 {
1708 UInt p = GetSmallInt("ELM0_GF2VEC", pos);
1709 if (LEN_GF2VEC(list) < p) {
1710 return Fail;
1711 }
1712 else {
1713 return ELM_GF2VEC(list, p);
1714 }
1715 }
1716
1717
1718 /****************************************************************************
1719 **
1720 *F FuncELM_GF2VEC( <self>, <list>, <pos> ) . . select an elm of a GF2 vector
1721 **
1722 ** 'ELM_GF2VEC' returns the element at the position <pos> of the GF2 vector
1723 ** <list>. An error is signalled if <pos> is not bound. It is the
1724 ** responsibility of the caller to ensure that <pos> is a positive integer.
1725 */
FuncELM_GF2VEC(Obj self,Obj list,Obj pos)1726 static Obj FuncELM_GF2VEC(Obj self, Obj list, Obj pos)
1727 {
1728 UInt p = GetSmallInt("ELM_GF2VEC", pos);
1729 if (LEN_GF2VEC(list) < p) {
1730 ErrorMayQuit("List Element: <list>[%d] must have an assigned value",
1731 p, 0);
1732 }
1733 else {
1734 return ELM_GF2VEC(list, p);
1735 }
1736 }
1737
1738
1739 /****************************************************************************
1740 **
1741 *F FuncELMS_GF2VEC( <self>, <list>, <poss> ) . . . sublist from a GF2 vector
1742 **
1743 ** 'ELMS_GF2VEC' returns a new list containing the elements at the position
1744 ** given in the list <poss> from the vector <list>. It is the
1745 ** responsibility of the caller to ensure that <poss> is dense and contains
1746 ** only positive integers. An error is signalled if an element of <poss> is
1747 ** larger than the length of <list>.
1748 */
FuncELMS_GF2VEC(Obj self,Obj list,Obj poss)1749 static Obj FuncELMS_GF2VEC(Obj self, Obj list, Obj poss)
1750 {
1751 Obj elms; // selected sublist, result
1752 Int lenList; // length of <list>
1753 Int lenPoss; // length of positions
1754 Int pos; // position as integer
1755 Int inc; // increment in a range
1756 Int i; // loop variable
1757 Obj apos;
1758
1759 // get the length of <list>
1760 lenList = LEN_GF2VEC(list);
1761
1762 // general code for arbritrary lists, which are ranges
1763 if (!IS_RANGE(poss)) {
1764
1765 // get the length of <positions>
1766 lenPoss = LEN_LIST(poss);
1767
1768 // make the result vector
1769 NEW_GF2VEC(elms, TYPE_LIST_GF2VEC, lenPoss);
1770
1771 // loop over the entries of <positions> and select
1772 for (i = 1; i <= lenPoss; i++) {
1773
1774 // get next position
1775
1776 apos = ELM0_LIST(poss, i);
1777 if (!apos || !IS_INTOBJ(apos))
1778 ErrorMayQuit("ELMS_GF2VEC: error at position %d in positions "
1779 "list, entry must be bound to a small integer",
1780 i, 0L);
1781 pos = INT_INTOBJ(apos);
1782 if (lenList < pos) {
1783 ErrorMayQuit("List Elements: <list>[%d] must have a value",
1784 pos, 0L);
1785 }
1786
1787 // assign the element into <elms>
1788 if (ELM_GF2VEC(list, pos) == GF2One) {
1789 BLOCK_ELM_GF2VEC(elms, i) |= MASK_POS_GF2VEC(i);
1790 }
1791 }
1792 }
1793
1794 // special code for ranges
1795 else {
1796
1797 // get the length of <positions>, the first elements, and the inc.
1798 lenPoss = GET_LEN_RANGE(poss);
1799 pos = GET_LOW_RANGE(poss);
1800 inc = GET_INC_RANGE(poss);
1801
1802 // check that no <position> is larger than <lenList>
1803 if (lenList < pos) {
1804 ErrorMayQuit("List Elements: <list>[%d] must have a value", pos,
1805 0L);
1806 }
1807 if (lenList < pos + (lenPoss - 1) * inc) {
1808 ErrorMayQuit("List Elements: <list>[%d] must have a value",
1809 pos + (lenPoss - 1) * inc, 0L);
1810 }
1811
1812 // make the result vector
1813 NEW_GF2VEC(elms, TYPE_LIST_GF2VEC, lenPoss);
1814
1815 // increment 1 ranges is a block copy
1816 if (inc == 1)
1817 CopySection_GF2Vecs(list, elms, pos, 1, lenPoss);
1818
1819 // loop over the entries of <positions> and select
1820 else {
1821 for (i = 1; i <= lenPoss; i++, pos += inc) {
1822 if (ELM_GF2VEC(list, pos) == GF2One) {
1823 BLOCK_ELM_GF2VEC(elms, i) |= MASK_POS_GF2VEC(i);
1824 }
1825 }
1826 }
1827 }
1828
1829 // return the result
1830 return elms;
1831 }
1832
1833
1834 /****************************************************************************
1835 **
1836 *F FuncASS_GF2VEC( <self>, <list>, <pos>, <elm> ) set an elm of a GF2 vector
1837 **
1838 ** 'ASS_GF2VEC' assigns the element <elm> at the position <pos> to the GF2
1839 ** vector <list>.
1840 **
1841 ** It is the responsibility of the caller to ensure that <pos> is positive,
1842 ** and that <elm> is not 0.
1843 */
1844
FuncASS_GF2VEC(Obj self,Obj list,Obj pos,Obj elm)1845 static Obj FuncASS_GF2VEC(Obj self, Obj list, Obj pos, Obj elm)
1846 {
1847 // check that <list> is mutable
1848 RequireMutable("List Assignment", list, "list");
1849
1850 // get the position
1851 UInt p = GetSmallInt("ASS_GF2VEC", pos);
1852
1853 // if <elm> is Z(2) or 0*Z(2) and the position is OK, keep rep
1854 if (p <= LEN_GF2VEC(list) + 1) {
1855 if (LEN_GF2VEC(list) + 1 == p) {
1856 if (DoFilter(IsLockedRepresentationVector, list) == True)
1857 ErrorMayQuit("Assignment forbidden beyond the end of locked "
1858 "GF2 vector",
1859 0, 0);
1860 ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(p));
1861 SET_LEN_GF2VEC(list, p);
1862 }
1863 if (EQ(GF2One, elm)) {
1864 BLOCK_ELM_GF2VEC(list, p) |= MASK_POS_GF2VEC(p);
1865 }
1866 else if (EQ(GF2Zero, elm)) {
1867 BLOCK_ELM_GF2VEC(list, p) &= ~MASK_POS_GF2VEC(p);
1868 }
1869 else if (IS_FFE(elm) && CHAR_FF(FLD_FFE(elm)) == 2 &&
1870 DEGR_FF(FLD_FFE(elm)) <= 8) {
1871 RewriteGF2Vec(list, SIZE_FF(FLD_FFE(elm)));
1872 ASS_VEC8BIT(list, pos, elm);
1873 }
1874 else {
1875 PlainGF2Vec(list);
1876 ASS_LIST(list, p, elm);
1877 }
1878 }
1879 else {
1880 PlainGF2Vec(list);
1881 ASS_LIST(list, p, elm);
1882 }
1883 return 0;
1884 }
1885
1886 /****************************************************************************
1887 **
1888 *F FuncPLAIN_GF2MAT( <self>, <list> ) . . . convert back into ordinary list
1889 */
FuncPLAIN_GF2MAT(Obj self,Obj list)1890 static Obj FuncPLAIN_GF2MAT(Obj self, Obj list)
1891 {
1892 PlainGF2Mat(list);
1893
1894 // return nothing
1895 return 0;
1896 }
1897
1898
1899 /****************************************************************************
1900 **
1901 *F FuncASS_GF2MAT( <self>, <list>, <pos>, <elm> ) set an elm of a GF2 matrix
1902 **
1903 ** 'ASS_GF2MAT' assigns the element <elm> at the position <pos> to the GF2
1904 ** matrix <list>.
1905 **
1906 ** It is the responsibility of the caller to ensure that <pos> is positive,
1907 ** and that <elm> is not 0.
1908 */
FuncASS_GF2MAT(Obj self,Obj list,Obj pos,Obj elm)1909 static Obj FuncASS_GF2MAT(Obj self, Obj list, Obj pos, Obj elm)
1910 {
1911 // check that <list> is mutable
1912 RequireMutable("List Assignment", list, "list");
1913
1914 // get the position
1915 UInt p = GetSmallInt("ASS_GF2MAT", pos);
1916
1917 // if <elm> is a GF2 vector and the length is OK, keep the rep
1918 if (!IS_GF2VEC_REP(elm)) {
1919 PlainGF2Mat(list);
1920 ASS_LIST(list, p, elm);
1921 }
1922 else if (p == 1 && 1 >= LEN_GF2MAT(list)) {
1923 ResizeBag(list, SIZE_PLEN_GF2MAT(p));
1924 SetTypeDatObj(elm, IS_MUTABLE_OBJ(elm) ? TYPE_LIST_GF2VEC_LOCKED
1925 : TYPE_LIST_GF2VEC_IMM_LOCKED);
1926 SET_ELM_GF2MAT(list, p, elm);
1927 CHANGED_BAG(list);
1928 }
1929 else if (p > LEN_GF2MAT(list) + 1) {
1930 PlainGF2Mat(list);
1931 ASS_LIST(list, p, elm);
1932 }
1933 else if (LEN_GF2VEC(elm) == LEN_GF2VEC(ELM_GF2MAT(list, 1))) {
1934 if (LEN_GF2MAT(list) + 1 == p) {
1935 ResizeBag(list, SIZE_PLEN_GF2MAT(p));
1936 SET_LEN_GF2MAT(list, p);
1937 }
1938 SetTypeDatObj(elm, IS_MUTABLE_OBJ(elm) ? TYPE_LIST_GF2VEC_LOCKED
1939 : TYPE_LIST_GF2VEC_IMM_LOCKED);
1940 SET_ELM_GF2MAT(list, p, elm);
1941 CHANGED_BAG(list);
1942 }
1943 else {
1944 PlainGF2Mat(list);
1945 ASS_LIST(list, p, elm);
1946 }
1947 return 0;
1948 }
1949
1950
1951 /****************************************************************************
1952 **
1953 *F FuncELM_GF2MAT( <self>, <mat>, <row> ) . . . select a row of a GF2 matrix
1954 **
1955 */
FuncELM_GF2MAT(Obj self,Obj mat,Obj row)1956 static Obj FuncELM_GF2MAT(Obj self, Obj mat, Obj row)
1957 {
1958 UInt r = GetSmallInt("ELM_GF2MAT", row);
1959 if (LEN_GF2MAT(mat) < r) {
1960 ErrorMayQuit("row index %d exceeds %d, the number of rows", r,
1961 LEN_GF2MAT(mat));
1962 }
1963 return ELM_GF2MAT(mat, r);
1964 }
1965
1966
1967 /****************************************************************************
1968 **
1969 *F FuncUNB_GF2VEC( <self>, <list>, <pos> ) . unbind position of a GF2 vector
1970 **
1971 ** 'UNB_GF2VEC' unbind the element at the position <pos> in a GF2 vector
1972 ** <list>.
1973 **
1974 ** It is the responsibility of the caller to ensure that <pos> is positive.
1975 */
FuncUNB_GF2VEC(Obj self,Obj list,Obj pos)1976 static Obj FuncUNB_GF2VEC(Obj self, Obj list, Obj pos)
1977 {
1978 // check that <list> is mutable
1979 RequireMutable("List Unbind", list, "vector");
1980
1981 if (DoFilter(IsLockedRepresentationVector, list) == True) {
1982 ErrorMayQuit("Unbind forbidden on locked GF2 vector", 0, 0);
1983 }
1984
1985 // get the position
1986 UInt p = GetSmallInt("UNB_GF2VEC", pos);
1987
1988 // if we unbind the last position keep the representation
1989 if (LEN_GF2VEC(list) < p) {
1990 ;
1991 }
1992 else if (LEN_GF2VEC(list) == p) {
1993 ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(p - 1));
1994 SET_LEN_GF2VEC(list, p - 1);
1995 }
1996 else {
1997 PlainGF2Vec(list);
1998 UNB_LIST(list, p);
1999 }
2000 return 0;
2001 }
2002
2003
2004 /****************************************************************************
2005 **
2006 *F FuncUNB_GF2MAT( <self>, <list>, <pos> ) . unbind position of a GF2 matrix
2007 **
2008 ** 'UNB_GF2VEC' unbind the element at the position <pos> in a GF2 matrix
2009 ** <list>.
2010 **
2011 ** It is the responsibility of the caller to ensure that <pos> is positive.
2012 */
FuncUNB_GF2MAT(Obj self,Obj list,Obj pos)2013 static Obj FuncUNB_GF2MAT(Obj self, Obj list, Obj pos)
2014 {
2015 // check that <list> is mutable
2016 RequireMutable("List Unbind", list, "matrix");
2017
2018 // get the position
2019 UInt p = GetSmallInt("UNB_GF2MAT", pos);
2020
2021 // if we unbind the last position keep the representation
2022 if (p > 1 && LEN_GF2MAT(list) < p) {
2023 ;
2024 }
2025 else if (LEN_GF2MAT(list) == p) {
2026 ResizeBag(list, SIZE_PLEN_GF2MAT(p - 1));
2027 SET_LEN_GF2MAT(list, p - 1);
2028 }
2029 else {
2030 PlainGF2Mat(list);
2031 UNB_LIST(list, p);
2032 }
2033 return 0;
2034 }
2035
2036
2037 /****************************************************************************
2038 **
2039 *F * * * * * * * * * * * * arithmetic operations * * * * * * * * * * * * * *
2040 */
2041
2042
2043 /****************************************************************************
2044 **
2045 *F FuncZERO_GF2VEC( <self>, <mat> ) . . . . . . . . . . . . zero GF2 vector
2046 **
2047 ** return the zero vector over GF2 of the same length as <mat>.
2048 */
FuncZERO_GF2VEC(Obj self,Obj mat)2049 static Obj FuncZERO_GF2VEC(Obj self, Obj mat)
2050 {
2051 Obj zero;
2052 UInt len;
2053
2054 // create a new GF2 vector
2055 len = LEN_GF2VEC(mat);
2056 NEW_GF2VEC(zero, TYPE_LIST_GF2VEC, len);
2057 return zero;
2058 }
2059
2060 /****************************************************************************
2061 **
2062 *F FuncZERO_GF2VEC_2( <self>, <len>) . . . . . . . . . zero GF2 vector
2063 **
2064 ** return the zero vector over GF2 of length <len>
2065 */
FuncZERO_GF2VEC_2(Obj self,Obj len)2066 static Obj FuncZERO_GF2VEC_2(Obj self, Obj len)
2067 {
2068 Obj zero;
2069
2070 // create a new GF2 vector
2071 if (!IS_INTOBJ(len))
2072 ErrorMayQuit("ZERO_GF2VEC2: length must be a small integer, not a %s",
2073 (Int)TNAM_OBJ(len), 0L);
2074
2075 NEW_GF2VEC(zero, TYPE_LIST_GF2VEC, INT_INTOBJ(len));
2076 return zero;
2077 }
2078
2079
2080 /****************************************************************************
2081 **
2082 *F FuncINV_GF2MAT_MUTABLE( <self>, <mat> ) . .. . . . . inverse GF2 matrix
2083 **
2084 ** This might now be redundant, a library method using
2085 ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE
2086 ** might do just as good a job
2087 */
FuncINV_GF2MAT_MUTABLE(Obj self,Obj mat)2088 static Obj FuncINV_GF2MAT_MUTABLE(Obj self, Obj mat)
2089 {
2090 UInt len;
2091
2092 len = LEN_GF2MAT(mat);
2093 if (len != 0) {
2094 if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
2095 ErrorMayQuit("<matrix> must be square", 0, 0);
2096 }
2097 }
2098 return InverseGF2Mat(mat, 2);
2099 }
2100
2101 /****************************************************************************
2102 **
2103 *F FuncINV_GF2MAT_SAME_MUTABILITY( <self>, <mat> ) . ... inverse GF2 matrix
2104 **
2105 ** This might now be redundant, a library method using
2106 ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE
2107 ** might do just as good a job
2108 */
FuncINV_GF2MAT_SAME_MUTABILITY(Obj self,Obj mat)2109 static Obj FuncINV_GF2MAT_SAME_MUTABILITY(Obj self, Obj mat)
2110 {
2111 UInt len;
2112
2113 len = LEN_GF2MAT(mat);
2114 if (len != 0) {
2115 if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
2116 ErrorMayQuit("<matrix> must be square", 0, 0);
2117 }
2118 }
2119 return InverseGF2Mat(mat, 1);
2120 }
2121
2122 /****************************************************************************
2123 **
2124 *F FuncINV_GF2MAT_IMMUTABLE( <self>, <mat> ) . .. . . . inverse GF2 matrix
2125 **
2126 ** This might now be redundant, a library method using
2127 ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE
2128 ** might do just as good a job
2129 */
FuncINV_GF2MAT_IMMUTABLE(Obj self,Obj mat)2130 static Obj FuncINV_GF2MAT_IMMUTABLE(Obj self, Obj mat)
2131 {
2132 UInt len;
2133
2134 len = LEN_GF2MAT(mat);
2135 if (len != 0) {
2136 if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
2137 ErrorMayQuit("<matrix> must be square", 0, 0);
2138 }
2139 }
2140 return InverseGF2Mat(mat, 0);
2141 }
2142
2143
2144 /****************************************************************************
2145 **
2146 *F FuncINV_PLIST_GF2VECS_DESTRUCTIVE( <self>, <list> )
2147 **
2148 ** invert possible GF2 matrix
2149 */
FuncINV_PLIST_GF2VECS_DESTRUCTIVE(Obj self,Obj list)2150 static Obj FuncINV_PLIST_GF2VECS_DESTRUCTIVE(Obj self, Obj list)
2151 {
2152 UInt len, i;
2153 Obj row;
2154 len = LEN_PLIST(list);
2155 for (i = 1; i <= len; i++) {
2156 row = ELM_PLIST(list, i);
2157 if (!IS_GF2VEC_REP(row) || LEN_GF2VEC(row) != len)
2158 return TRY_NEXT_METHOD;
2159 }
2160 if (len == 0) {
2161 return CopyObj(list, 1);
2162 }
2163 if (len == 1) {
2164 row = ELM_PLIST(list, 1);
2165 if (CONST_BLOCKS_GF2VEC(row)[0] & 1) {
2166 return CopyObj(list, 1);
2167 }
2168 else
2169 return Fail;
2170 }
2171 return InversePlistGF2VecsDesstructive(list);
2172 }
2173
2174
2175 /****************************************************************************
2176 **
2177 *F FuncSUM_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) . . . . . sum of GF2 vectors
2178 **
2179 ** 'FuncSUM_GF2VEC_GF2VEC' returns the sum of the two gf2-vectors <vl> and
2180 ** <vr>. The sum is a new gf2-vector, where each element is the sum of the
2181 ** corresponding entries of <vl> and <vr>. The major work is done in the
2182 ** routine 'AddPartialGF2VecGF2Vec' which is called from
2183 ** 'FuncSUM_GF2VEC_GF2VEC'.
2184 **
2185 ** 'FuncSUM_GF2VEC_GF2VEC' is an improved version of 'SumListList', which
2186 ** does not call 'SUM' but uses bit operations instead.
2187 */
FuncSUM_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)2188 static Obj FuncSUM_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
2189 {
2190 Obj sum; // sum, result
2191 UInt ll, lr;
2192
2193 ll = LEN_GF2VEC(vl);
2194 lr = LEN_GF2VEC(vr);
2195
2196
2197 if (ll < lr) {
2198 sum = ShallowCopyVecGF2(vr);
2199 AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sum), CONST_BLOCKS_GF2VEC(vl), ll);
2200 }
2201 else {
2202 sum = ShallowCopyVecGF2(vl);
2203 AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sum), CONST_BLOCKS_GF2VEC(vr), lr);
2204 }
2205
2206 if (!IS_MUTABLE_OBJ(vl) && !IS_MUTABLE_OBJ(vr))
2207 SET_TYPE_POSOBJ(sum, TYPE_LIST_GF2VEC_IMM);
2208
2209 return sum;
2210 }
2211
2212 /****************************************************************************
2213 **
2214 *F FuncMULT_VECTOR_GF2VECS_2( <self>, <vl>, <mul> )
2215 ** . . . . . sum of GF2 vectors
2216 **
2217 */
FuncMULT_VECTOR_GF2VECS_2(Obj self,Obj vl,Obj mul)2218 static Obj FuncMULT_VECTOR_GF2VECS_2(Obj self, Obj vl, Obj mul)
2219 {
2220 if (EQ(mul, GF2One))
2221 return (Obj)0;
2222 else if (EQ(mul, GF2Zero)) {
2223 AddCoeffsGF2VecGF2Vec(vl, vl);
2224 return (Obj)0;
2225 }
2226 else
2227 return TRY_NEXT_METHOD;
2228 }
2229
2230
2231 /****************************************************************************
2232 **
2233 *F FuncPROD_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) . . product of GF2 vectors
2234 **
2235 ** 'FuncPROD_GF2VEC_GF2VEC' returns the product of the two GF2 vectors <vl>
2236 ** and <vr>. The product is either `GF2One' or `GF2Zero'.
2237 */
FuncPROD_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)2238 static Obj FuncPROD_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
2239 {
2240 return ProdGF2VecGF2Vec(vl, vr);
2241 }
2242
2243
2244 /****************************************************************************
2245 **
2246 *F FuncPROD_GF2VEC_GF2MAT( <self>, <vl>, <vr> ) product of GF2 vector/matrix
2247 **
2248 ** 'FuncPROD_GF2VEC_GF2MAT' returns the product of the GF2 vectors <vl> and
2249 ** the GF2 matrix <vr>.
2250 **
2251 ** The product is again a GF2 vector. It is the responsibility of the
2252 ** caller to ensure that <vl> is a GF2 vector, <vr> a GF2 matrix.
2253 */
FuncPROD_GF2VEC_GF2MAT(Obj self,Obj vl,Obj vr)2254 static Obj FuncPROD_GF2VEC_GF2MAT(Obj self, Obj vl, Obj vr)
2255 {
2256 return ProdGF2VecGF2Mat(vl, vr);
2257 }
2258
2259 /****************************************************************************
2260 **
2261 *F FuncPROD_GF2MAT_GF2MAT( <self>, <ml>, <mr> ) product of GF2 vector/matrix
2262 **
2263 ** 'FuncPROD_GF2MAT_GF2MAT' returns the product of the GF2 matricess <ml>
2264 ** and <mr>.
2265 **
2266 ** The product is again a GF2 matrix. It is the responsibility of the
2267 ** caller to ensure that <ml> and <mr> are GF2 matrices
2268 */
FuncPROD_GF2MAT_GF2MAT(Obj self,Obj ml,Obj mr)2269 static Obj FuncPROD_GF2MAT_GF2MAT(Obj self, Obj ml, Obj mr)
2270 {
2271 UInt lenl = LEN_GF2MAT(ml);
2272 UInt lenm;
2273 if (lenl >= 128) {
2274 lenm = LEN_GF2VEC(ELM_GF2MAT(ml, 1));
2275 if (lenm >= 128 && lenm == LEN_GF2MAT(mr) &&
2276 LEN_GF2VEC(ELM_GF2MAT(mr, 1)) >= 128) {
2277 return ProdGF2MatGF2MatAdvanced(ml, mr, 8, (lenm + 255) / 256);
2278 }
2279 }
2280 return ProdGF2MatGF2MatSimple(ml, mr);
2281 }
2282
2283 /****************************************************************************
2284 **
2285 *F FuncPROD_GF2MAT_GF2MAT_SIMPLE( <self>, <ml>, <mr> )
2286 **
2287 ** 'FuncPROD_GF2MAT_GF2MAT' returns the product of the GF2 matricess <ml>
2288 ** and <mr>. It never uses grease or blocking.
2289 **
2290 ** The product is again a GF2 matrix. It is the responsibility of the
2291 ** caller to ensure that <ml> and <mr> are GF2 matrices
2292 */
FuncPROD_GF2MAT_GF2MAT_SIMPLE(Obj self,Obj ml,Obj mr)2293 static Obj FuncPROD_GF2MAT_GF2MAT_SIMPLE(Obj self, Obj ml, Obj mr)
2294 {
2295 return ProdGF2MatGF2MatSimple(ml, mr);
2296 }
2297
2298
2299 /****************************************************************************
2300 **
2301 *F FuncPROD_GF2MAT_GF2MAT_ADVANCED( <self>, <ml>, <mr>, <greaselevel>,
2302 ** <blocksize> )
2303 **
2304 ** 'FuncPROD_GF2MAT_GF2MAT_ADVANCED' returns the product of the GF2 matrices
2305 ** <ml> and <mr> using grease level <greaselevel> and block size <blocksize>
2306 **
2307 ** The product is again a GF2 matrix. It is the responsibility of the
2308 ** caller to ensure that <ml> and <mr> are GF2 matrices
2309 */
FuncPROD_GF2MAT_GF2MAT_ADVANCED(Obj self,Obj ml,Obj mr,Obj greaselevel,Obj blocksize)2310 static Obj FuncPROD_GF2MAT_GF2MAT_ADVANCED(
2311 Obj self, Obj ml, Obj mr, Obj greaselevel, Obj blocksize)
2312 {
2313 return ProdGF2MatGF2MatAdvanced(ml, mr, INT_INTOBJ(greaselevel),
2314 INT_INTOBJ(blocksize));
2315 }
2316
2317
2318 /****************************************************************************
2319 **
2320 *F FuncPROD_GF2MAT_GF2VEC( <self>, <vl>, <vr> ) product of GF2 matrix/vector
2321 **
2322 ** 'FuncPROD_GF2VEC_GF2MAT' returns the product of the GF2 matrix <vl> and
2323 ** the GF2 vector <vr>.
2324 **
2325 ** The product is again a GF2 vector. It is the responsibility of the
2326 ** caller to ensure that <vr> is a GF2 vector, <vl> a GF2 matrix.
2327 */
FuncPROD_GF2MAT_GF2VEC(Obj self,Obj vl,Obj vr)2328 static Obj FuncPROD_GF2MAT_GF2VEC(Obj self, Obj vl, Obj vr)
2329 {
2330 return ProdGF2MatGF2Vec(vl, vr);
2331 }
2332
2333
2334 /****************************************************************************
2335 **
2336 *F FuncADDCOEFFS_GF2VEC_GF2VEC_MULT( <self>, <vl>, <vr>, <mul> ) GF2 vectors
2337 */
FuncADDCOEFFS_GF2VEC_GF2VEC_MULT(Obj self,Obj vl,Obj vr,Obj mul)2338 static Obj FuncADDCOEFFS_GF2VEC_GF2VEC_MULT(Obj self, Obj vl, Obj vr, Obj mul)
2339 {
2340 // do nothing if <mul> is zero
2341 if (EQ(mul, GF2Zero)) {
2342 return INTOBJ_INT(RightMostOneGF2Vec(vl));
2343 }
2344
2345 // add if <mul> is one
2346 if (EQ(mul, GF2One)) {
2347 return AddCoeffsGF2VecGF2Vec(vl, vr);
2348 }
2349
2350 // try next method
2351 return TRY_NEXT_METHOD;
2352 }
2353
2354 /****************************************************************************
2355 **
2356 *F FuncADDCOEFFS_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) . . . . . . GF2 vectors
2357 */
FuncADDCOEFFS_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)2358 static Obj FuncADDCOEFFS_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
2359 {
2360 return AddCoeffsGF2VecGF2Vec(vl, vr);
2361 }
2362
2363
2364 /****************************************************************************
2365 **
2366 *F FuncSHRINKCOEFFS_GF2VEC( <self>, <vec> ) . . . . . remove trailing zeros
2367 */
FuncSHRINKCOEFFS_GF2VEC(Obj self,Obj vec)2368 static Obj FuncSHRINKCOEFFS_GF2VEC(Obj self, Obj vec)
2369 {
2370 UInt len;
2371 UInt nbb;
2372 UInt onbb;
2373 UInt * ptr;
2374 UInt off;
2375
2376 // get length and number of blocks
2377 len = LEN_GF2VEC(vec);
2378 if (len == 0) {
2379 return INTOBJ_INT(0);
2380 }
2381
2382 nbb = (len + BIPEB - 1) / BIPEB;
2383 onbb = nbb;
2384 ptr = BLOCKS_GF2VEC(vec) + (nbb - 1);
2385
2386 // number of insignificant bit positions in last word
2387 off = BIPEB - ((len - 1) % BIPEB + 1);
2388
2389 // mask out the last bits
2390 #ifdef SYS_IS_64_BIT
2391 *ptr &= 0xffffffffffffffff >> off;
2392 #else
2393 *ptr &= 0xffffffff >> off;
2394 #endif
2395
2396 // find last non-trivial block
2397 while (0 < nbb && !*ptr) {
2398 nbb--;
2399 ptr--;
2400 }
2401 // did the block number change?
2402 if (nbb < onbb) {
2403 len = nbb * BIPEB;
2404 }
2405
2406 // find position inside this block
2407 // we are guaranteed not to cross a block boundary !
2408 while (0 < len && !(*ptr & MASK_POS_GF2VEC(len))) {
2409 len--;
2410 }
2411 ResizeWordSizedBag(vec, SIZE_PLEN_GF2VEC(len));
2412 SET_LEN_GF2VEC(vec, len);
2413 return INTOBJ_INT(len);
2414 }
2415
2416 /****************************************************************************
2417 **
2418 *F FuncPOSITION_NONZERO_GF2VEC( <self>, <vec>, <zero>) ..find first non-zero
2419 **
2420 ** The pointless zero argument is because this is a method for PositionNot
2421 ** It is *not* used in the code and can be replaced by a dummy argument.
2422 */
2423
PositionNonZeroGF2Vec(Obj vec,UInt from)2424 static UInt PositionNonZeroGF2Vec(Obj vec, UInt from)
2425 {
2426 UInt len;
2427 UInt nbb;
2428 UInt nb;
2429 const UInt * ptr;
2430 UInt pos;
2431
2432 // get length and number of blocks
2433 len = LEN_GF2VEC(vec);
2434 if (len == 0) {
2435 return 1;
2436 }
2437
2438
2439 nbb = from / BIPEB;
2440 pos = from % BIPEB;
2441 ptr = CONST_BLOCKS_GF2VEC(vec) + nbb;
2442 if (pos) // partial block to check
2443 {
2444 pos = from + 1;
2445 while ((pos - 1) % BIPEB && pos <= len) {
2446 if ((*ptr) & MASK_POS_GF2VEC(pos))
2447 return (pos);
2448 pos++;
2449 }
2450 if (pos > len)
2451 return len + 1;
2452 nbb++;
2453 ptr++;
2454 }
2455 // find first non-trivial block
2456 nb = NUMBER_BLOCKS_GF2VEC(vec);
2457 while (nbb < nb && !*ptr) {
2458 nbb++;
2459 ptr++;
2460 }
2461
2462 // find position inside this block
2463 pos = nbb * BIPEB + 1;
2464 while (pos <= len && !(*ptr & MASK_POS_GF2VEC(pos))) {
2465 pos++;
2466 }
2467 // as the code is intended to run over, trailing 1's are innocent
2468 if (pos <= len)
2469 return pos;
2470 else
2471 return len + 1;
2472 }
2473
2474
FuncPOSITION_NONZERO_GF2VEC(Obj self,Obj vec,Obj zero)2475 static Obj FuncPOSITION_NONZERO_GF2VEC(Obj self, Obj vec, Obj zero)
2476 {
2477 return INTOBJ_INT(PositionNonZeroGF2Vec(vec, 0));
2478 }
2479
FuncPOSITION_NONZERO_GF2VEC3(Obj self,Obj vec,Obj zero,Obj from)2480 static Obj FuncPOSITION_NONZERO_GF2VEC3(Obj self, Obj vec, Obj zero, Obj from)
2481 {
2482 return INTOBJ_INT(PositionNonZeroGF2Vec(vec, INT_INTOBJ(from)));
2483 }
2484
2485
FuncCOPY_SECTION_GF2VECS(Obj self,Obj src,Obj dest,Obj from,Obj to,Obj howmany)2486 static Obj FuncCOPY_SECTION_GF2VECS(
2487 Obj self, Obj src, Obj dest, Obj from, Obj to, Obj howmany)
2488 {
2489 Int ifrom = GetPositiveSmallInt("COPY_SECTION_GF2VECS", from);
2490 Int ito = GetPositiveSmallInt("COPY_SECTION_GF2VECS", to);
2491 Int ihowmany = GetSmallInt("COPY_SECTION_GF2VECS", howmany);
2492
2493 if (!IS_GF2VEC_REP(src)) {
2494 RequireArgument("COPY_SECTION_GF2VECS", src, "must be a GF2 vector");
2495 }
2496 if (!IS_GF2VEC_REP(dest)) {
2497 RequireArgument("COPY_SECTION_GF2VECS", dest, "must be a GF2 vector");
2498 }
2499
2500 UInt lens = LEN_GF2VEC(src);
2501 UInt lend = LEN_GF2VEC(dest);
2502 if (ihowmany < 0 ||
2503 ifrom + ihowmany - 1 > lens || ito + ihowmany - 1 > lend)
2504 ErrorMayQuit("Bad argument values", 0, 0);
2505 RequireMutable("COPY_SECTION_GF2VECS", dest, "vector");
2506
2507 CopySection_GF2Vecs(src, dest, (UInt)ifrom, (UInt)ito, (UInt)ihowmany);
2508 return (Obj)0;
2509 }
2510
2511
2512 /****************************************************************************
2513 **
2514 *F FuncAPPEND_GF2VEC( <self>, <vecl>, <vecr> )
2515 **
2516 */
2517
FuncAPPEND_GF2VEC(Obj self,Obj vecl,Obj vecr)2518 static Obj FuncAPPEND_GF2VEC(Obj self, Obj vecl, Obj vecr)
2519 {
2520 UInt lenl, lenr;
2521 lenl = LEN_GF2VEC(vecl);
2522 lenr = LEN_GF2VEC(vecr);
2523 if (True == DoFilter(IsLockedRepresentationVector, vecl) && lenr > 0) {
2524 ErrorMayQuit("Append to locked compressed vector is forbidden", 0, 0);
2525 }
2526 ResizeWordSizedBag(vecl, SIZE_PLEN_GF2VEC(lenl + lenr));
2527 CopySection_GF2Vecs(vecr, vecl, 1, lenl + 1, lenr);
2528 SET_LEN_GF2VEC(vecl, lenl + lenr);
2529 return (Obj)0;
2530 }
2531
2532
2533 /****************************************************************************
2534 **
2535 *F FuncSHALLOWCOPY_GF2VEC( <self>, <vec> )
2536 **
2537 */
2538
FuncSHALLOWCOPY_GF2VEC(Obj self,Obj vec)2539 static Obj FuncSHALLOWCOPY_GF2VEC(Obj self, Obj vec)
2540 {
2541 return ShallowCopyVecGF2(vec);
2542 }
2543
2544 /****************************************************************************
2545 **
2546 *F FuncSUM_GF2MAT_GF2MAT( <self>, <matl>, <matr> )
2547 **
2548 */
2549
2550
FuncSUM_GF2MAT_GF2MAT(Obj self,Obj matl,Obj matr)2551 static Obj FuncSUM_GF2MAT_GF2MAT(Obj self, Obj matl, Obj matr)
2552 {
2553 UInt ll, lr, ls, lm, wl, wr, ws, wm;
2554 Obj sum;
2555 Obj vl, vr, sv;
2556 UInt i;
2557 Obj rtype;
2558 ll = LEN_GF2MAT(matl);
2559 lr = LEN_GF2MAT(matr);
2560 if (ll > lr) {
2561 ls = ll;
2562 lm = lr;
2563 }
2564 else {
2565 ls = lr;
2566 lm = ll;
2567 }
2568 wl = LEN_GF2VEC(ELM_GF2MAT(matl, 1));
2569 wr = LEN_GF2VEC(ELM_GF2MAT(matr, 1));
2570 if (wl > wr) {
2571 ws = wl;
2572 wm = wr;
2573 }
2574 else {
2575 ws = wr;
2576 wm = wl;
2577 }
2578
2579 // In this case, the result is not rectangular
2580
2581 if ((ll > lr && wr > wl) || (ll < lr && wr < wl))
2582 return TRY_NEXT_METHOD;
2583
2584
2585 sum = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(ls));
2586 if (IS_MUTABLE_OBJ(matl) || IS_MUTABLE_OBJ(matr)) {
2587 SET_TYPE_POSOBJ(sum, TYPE_LIST_GF2MAT);
2588 if (IS_MUTABLE_OBJ(ELM_GF2MAT(matl, 1)) ||
2589 IS_MUTABLE_OBJ(ELM_GF2MAT(matr, 1)))
2590 rtype = TYPE_LIST_GF2VEC_LOCKED;
2591 else
2592 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
2593 }
2594 else {
2595 SET_TYPE_POSOBJ(sum, TYPE_LIST_GF2MAT_IMM);
2596 rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
2597 }
2598
2599 SET_LEN_GF2MAT(sum, ls);
2600 for (i = 1; i <= lm; i++) {
2601
2602 // copy the longer vector and add the shorter
2603 if (wl == ws) {
2604 sv = ShallowCopyVecGF2(ELM_GF2MAT(matl, i));
2605 vr = ELM_GF2MAT(matr, i);
2606 AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sv), CONST_BLOCKS_GF2VEC(vr), wm);
2607 }
2608 else {
2609 sv = ShallowCopyVecGF2(ELM_GF2MAT(matr, i));
2610 vl = ELM_GF2MAT(matl, i);
2611 AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sv), CONST_BLOCKS_GF2VEC(vl), wm);
2612 }
2613
2614 SetTypeDatObj(sv, rtype);
2615 SET_ELM_GF2MAT(sum, i, sv);
2616 CHANGED_BAG(sum);
2617 }
2618 for (; i <= ls; i++) {
2619 if (ll > lr)
2620 sv = ELM_GF2MAT(matl, i);
2621 else
2622 sv = ELM_GF2MAT(matr, i);
2623
2624 if (rtype == TYPE_LIST_GF2VEC_LOCKED)
2625 sv = ShallowCopyVecGF2(sv);
2626
2627 SetTypeDatObj(sv, rtype);
2628 SET_ELM_GF2MAT(sum, i, sv);
2629 CHANGED_BAG(sum);
2630 }
2631 return sum;
2632 }
2633
2634
2635 /****************************************************************************
2636 **
2637 *F FuncTRANSPOSED_GF2MAT( <self>, <mat>)
2638 **
2639 */
FuncTRANSPOSED_GF2MAT(Obj self,Obj mat)2640 static Obj FuncTRANSPOSED_GF2MAT(Obj self, Obj mat)
2641 {
2642 UInt l, w;
2643 Obj tra, row;
2644 Obj typ, r1;
2645 UInt vals[BIPEB];
2646 UInt mask, val, bit;
2647 UInt imod, nrb, nstart;
2648 UInt i, j, k, n;
2649
2650 // check argument
2651 if (TNUM_OBJ(mat) != T_POSOBJ) {
2652 ErrorMayQuit("TRANSPOSED_GF2MAT: Need compressed matrix over GF(2)\n",
2653 0, 0);
2654 }
2655 // type for mat
2656 typ = TYPE_LIST_GF2MAT;
2657
2658
2659 // we assume here that there is a first row
2660 r1 = ELM_GF2MAT(mat, 1);
2661
2662 l = LEN_GF2MAT(mat);
2663 w = LEN_GF2VEC(r1);
2664 nrb = NUMBER_BLOCKS_GF2VEC(r1);
2665
2666 tra = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(w));
2667 SET_TYPE_POSOBJ(tra, typ);
2668
2669 // type for rows
2670 typ = TYPE_LIST_GF2VEC_LOCKED;
2671
2672 SET_LEN_GF2MAT(tra, w);
2673 // create new matrix
2674 for (i = 1; i <= w; i++) {
2675 NEW_GF2VEC(row, typ, l);
2676 SET_ELM_GF2MAT(tra, i, row);
2677 CHANGED_BAG(tra);
2678 }
2679 // set entries
2680 // run over BIPEB row chunks of the original matrix
2681 for (i = 1; i <= l; i = i + BIPEB) {
2682 imod = (i - 1) / BIPEB;
2683 // run through these rows in block chunks
2684 for (n = 0; n < nrb; n++) {
2685 for (j = 0; j < BIPEB; j++) {
2686 if ((i + j) > l) {
2687 vals[j] = 0; // outside matrix
2688 }
2689 else {
2690 const UInt * ptr =
2691 CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mat, i + j)) + n;
2692 vals[j] = *ptr;
2693 }
2694 }
2695 // write transposed values in new matrix
2696 mask = 1;
2697 nstart = n * BIPEB + 1;
2698 for (j = 0; j < BIPEB; j++) { // bit number = Row in transpose
2699 if ((nstart + j) <= w) {
2700 // still within matrix
2701 val = 0;
2702 bit = 1;
2703 for (k = 0; k < BIPEB; k++) {
2704 if (mask == (vals[k] & mask)) {
2705 val |= bit; // set bit
2706 }
2707 bit = bit << 1;
2708 }
2709 // set entry
2710 UInt * ptr =
2711 BLOCKS_GF2VEC(ELM_GF2MAT(tra, nstart + j)) + imod;
2712 *ptr = val;
2713 // next bit
2714 mask = mask << 1;
2715 }
2716 }
2717 }
2718 }
2719 return tra;
2720 }
2721
2722
2723 /****************************************************************************
2724 **
2725 *F FuncNUMBER_GF2VEC( <self>, <vect> )
2726 **
2727 */
FuncNUMBER_GF2VEC(Obj self,Obj vec)2728 static Obj FuncNUMBER_GF2VEC(Obj self, Obj vec)
2729 {
2730 UInt len, nd, i;
2731 UInt head, a;
2732 UInt off, off2; // 0 based
2733 Obj zahl; // the long number
2734 UInt * num2;
2735 mp_limb_t * vp;
2736 len = LEN_GF2VEC(vec);
2737 if (len == 0)
2738 return INTOBJ_INT(1);
2739 num2 = BLOCKS_GF2VEC(vec) + (len - 1) / BIPEB;
2740 off = (len - 1) % BIPEB + 1; // number of significant bits in last word
2741 off2 = BIPEB - off; // number of insignificant bits in last word
2742
2743 // mask out the last bits
2744 #ifdef SYS_IS_64_BIT
2745 *num2 &= 0xffffffffffffffff >> off2;
2746 #else
2747 *num2 &= 0xffffffff >> off2;
2748 #endif
2749
2750 if (len <= NR_SMALL_INT_BITS)
2751 // it still fits into a small integer
2752 return INTOBJ_INT(revertbits(*num2, len));
2753 else {
2754 // we might have to build a long integer
2755
2756 // the number of words (limbs) we need.
2757 nd = ((len - 1) / GMP_LIMB_BITS) + 1;
2758
2759 zahl = NewBag(T_INTPOS, nd * sizeof(UInt));
2760 // zahl = NewBag( T_INTPOS, (((nd+1)>>1)<<1)*sizeof(UInt) );
2761 // +1)>>1)<<1: round up to next even number
2762
2763 // garbage collection might lose pointer
2764 const UInt * num = CONST_BLOCKS_GF2VEC(vec) + (len - 1) / BIPEB;
2765
2766 vp = (mp_limb_t *)ADDR_OBJ(zahl); // the place we write to
2767 i = 1;
2768
2769 if (off != BIPEB) {
2770 head = revertbits(*num, off); // the last 'off' bits, reverted
2771 while (i < nd) {
2772 // next word
2773 num--;
2774 *vp = head; // the bits left from last word
2775 a = revertbits(*num, BIPEB); // the full word reverted
2776 head = a >> off2; // next head: trailing `off' bits
2777 a = a << off; // the rest of the word
2778 *vp |= a;
2779 vp++;
2780 i++;
2781 }
2782 *vp = head; // last head bits
2783 vp++;
2784 }
2785 else {
2786 while (i <= nd) {
2787 *vp = revertbits(*num--, BIPEB);
2788 vp++;
2789 i++;
2790 }
2791 }
2792
2793
2794 zahl = GMP_NORMALIZE(zahl);
2795 zahl = GMP_REDUCE(zahl);
2796
2797 return zahl;
2798 }
2799 }
2800
2801 /****************************************************************************
2802 **
2803 *F FuncLT_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) compare GF2 vectors
2804 */
FuncLT_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)2805 static Obj FuncLT_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
2806 {
2807 return (Cmp_GF2VEC_GF2VEC(vl, vr) < 0) ? True : False;
2808 }
2809
2810 /****************************************************************************
2811 **
2812 *F Cmp_GF2MAT_GF2MAT( <ml>, <mr> ) compare GF2 matrices
2813 */
2814
Cmp_GF2MAT_GF2MAT(Obj ml,Obj mr)2815 static Int Cmp_GF2MAT_GF2MAT(Obj ml, Obj mr)
2816 {
2817 UInt l1, l2, l, i;
2818 Int c;
2819 l1 = INT_INTOBJ(ELM_PLIST(ml, 1));
2820 l2 = INT_INTOBJ(ELM_PLIST(mr, 1));
2821 l = (l1 < l2) ? l1 : l2;
2822 for (i = 2; i <= l + 1; i++) {
2823 c = Cmp_GF2VEC_GF2VEC(ELM_PLIST(ml, i), ELM_PLIST(mr, i));
2824 if (c != 0)
2825 return c;
2826 }
2827 if (l1 < l2)
2828 return -1;
2829 if (l1 > l2)
2830 return 1;
2831 return 0;
2832 }
2833
2834 /****************************************************************************
2835 **
2836 *F FuncEQ_GF2MAT_GF2MAT( <ml>, <mr> ) compare GF2 matrices
2837 */
2838
FuncEQ_GF2MAT_GF2MAT(Obj self,Obj ml,Obj mr)2839 static Obj FuncEQ_GF2MAT_GF2MAT(Obj self, Obj ml, Obj mr)
2840 {
2841 if (ELM_PLIST(ml, 1) != ELM_PLIST(mr, 1))
2842 return False;
2843 return (0 == Cmp_GF2MAT_GF2MAT(ml, mr)) ? True : False;
2844 }
2845
2846 /****************************************************************************
2847 **
2848 *F FuncLT_GF2MAT_GF2MAT( <ml>, <mr> ) compare GF2 matrices
2849 */
2850
FuncLT_GF2MAT_GF2MAT(Obj self,Obj ml,Obj mr)2851 static Obj FuncLT_GF2MAT_GF2MAT(Obj self, Obj ml, Obj mr)
2852 {
2853 return (Cmp_GF2MAT_GF2MAT(ml, mr) < 0) ? True : False;
2854 }
2855
2856 /****************************************************************************
2857 **
2858 *F DistGF2Vecs( <ptL>, <ptR>, <len> )
2859 **
2860 ** computes the GF2-vector distance of two blocks in memory, pointed to by
2861 ** ptL and ptR for a GF(2) vector of <len> entries.
2862 **
2863 */
DistGF2Vecs(const UInt * ptL,const UInt * ptR,UInt len)2864 static UInt DistGF2Vecs(const UInt * ptL, const UInt * ptR, UInt len)
2865 {
2866 UInt sum, m;
2867 const UInt * end; // end marker
2868
2869 /*T this function will not work if the vectors have more than 2^28
2870 * entries */
2871
2872 end = ptL + ((len + BIPEB - 1) / BIPEB);
2873 sum = 0;
2874 // loop over the entries
2875 // T possibly unroll this loop
2876 while (ptL < end) {
2877 m = *ptL++ ^ *ptR++; // xor of bits, nr bits therein is difference
2878 sum += COUNT_TRUES_BLOCK(m);
2879 }
2880 return sum;
2881 }
2882
2883 /****************************************************************************
2884 **
2885 *F FuncDIST_GF2VEC_GF2VEC( <self>, <vl>, <vr> )
2886 **
2887 ** 'FuncDIST_GF2VEC_GF2VEC' returns the number of position in which two
2888 ** gf2-vectors <vl> and <vr> differ.
2889 */
FuncDIST_GF2VEC_GF2VEC(Obj self,Obj vl,Obj vr)2890 static Obj FuncDIST_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
2891 {
2892 UInt len; // length of the list
2893 UInt off; // bit offset at the end to clean out
2894 UInt * ptL; // bit field of <vl>
2895 UInt * ptR; // bit field of <vr>
2896 UInt * end; // pointer used to zero out end bit
2897 // get and check the length
2898 len = LEN_GF2VEC(vl);
2899
2900 if (len != LEN_GF2VEC(vr)) {
2901 ErrorMayQuit("DIST_GF2VEC_GF2VEC: vectors must have the same length",
2902 0L, 0L);
2903 }
2904
2905 // calculate the offsets
2906 ptL = BLOCKS_GF2VEC(vl);
2907 ptR = BLOCKS_GF2VEC(vr);
2908
2909 // mask out the last bits
2910 off = (len - 1) % BIPEB + 1; // number of significant bits in last word
2911 off = BIPEB - off; // number of insignificant bits in last word
2912 end = ptL + ((len - 1) / BIPEB);
2913 #ifdef SYS_IS_64_BIT
2914 *end &= 0xffffffffffffffff >> off;
2915 #else
2916 *end &= 0xffffffff >> off;
2917 #endif
2918 end = ptR + ((len - 1) / BIPEB);
2919 #ifdef SYS_IS_64_BIT
2920 *end &= 0xffffffffffffffff >> off;
2921 #else
2922 *end &= 0xffffffff >> off;
2923 #endif
2924
2925 return INTOBJ_INT(DistGF2Vecs(ptL, ptR, len));
2926 }
2927
2928
DistVecClosVec(Obj veclis,Obj ovec,Obj d,Obj osum,UInt pos,UInt l,UInt len)2929 static void DistVecClosVec(
2930 Obj veclis, // pointers to matrix vectors and their multiples
2931 Obj ovec, // vector we compute distance to
2932 Obj d, // distances list
2933 Obj osum, // position of the sum vector
2934 UInt pos, // recursion depth
2935 UInt l, // length of basis
2936 UInt len) // length of the involved vectors
2937 {
2938 UInt i;
2939 UInt di;
2940 Obj cnt;
2941 Obj vp;
2942 const UInt * vec;
2943 Obj one;
2944 Obj tmp;
2945
2946 vec = CONST_BLOCKS_GF2VEC(ovec);
2947 vp = ELM_PLIST(veclis, pos);
2948 one = INTOBJ_INT(1);
2949
2950 for (i = 0; i <= 1; i++) {
2951 if (pos < l) {
2952 DistVecClosVec(veclis, ovec, d, osum, pos + 1, l, len);
2953 }
2954 else {
2955 di = DistGF2Vecs(CONST_BLOCKS_GF2VEC(osum), vec, len);
2956
2957 cnt = ELM_PLIST(d, di + 1);
2958 if (IS_INTOBJ(cnt) && SUM_INTOBJS(tmp, cnt, one)) {
2959 cnt = tmp;
2960 SET_ELM_PLIST(d, di + 1, cnt);
2961 }
2962 else {
2963 cnt = SumInt(cnt, one);
2964 vec = CONST_BLOCKS_GF2VEC(ovec);
2965 SET_ELM_PLIST(d, di + 1, cnt);
2966 CHANGED_BAG(d);
2967 }
2968 }
2969 AddGF2VecToGF2Vec(BLOCKS_GF2VEC(osum),
2970 CONST_BLOCKS_GF2VEC(ELM_PLIST(vp, i + 1)), len);
2971 }
2972 }
2973
FuncDIST_VEC_CLOS_VEC(Obj self,Obj veclis,Obj vec,Obj d)2974 static Obj FuncDIST_VEC_CLOS_VEC(
2975 Obj self,
2976 Obj veclis, // pointers to matrix vectors and their multiples
2977 Obj vec, // vector we compute distance to
2978 Obj d) // distances list
2979
2980 {
2981 Obj sum; // sum vector
2982 UInt len;
2983
2984 len = LEN_GF2VEC(vec);
2985
2986 // get space for sum vector
2987 NEW_GF2VEC(sum, TYPE_LIST_GF2VEC, len);
2988
2989 // do the recursive work
2990 DistVecClosVec(veclis, vec, d, sum, 1, LEN_PLIST(veclis), len);
2991
2992 return (Obj)0;
2993 }
2994
2995 static UInt
AClosVec(Obj veclis,Obj ovec,Obj osum,UInt pos,UInt l,UInt len,UInt cnt,UInt stop,UInt bd,Obj obv,Obj coords,Obj bcoords)2996 AClosVec(Obj veclis, // pointers to matrix vectors and their multiples
2997 Obj ovec, // vector we compute distance to
2998 Obj osum, // position of the sum vector
2999 UInt pos, // recursion depth
3000 UInt l, // length of basis
3001 UInt len, // length of the involved vectors
3002 UInt cnt, // numbr of vectors used
3003 UInt stop, // stop value
3004 UInt bd, // best distance so far
3005 Obj obv, // best vector so far
3006 Obj coords, // coefficients to get current vector
3007 Obj bcoords // coefficients to get best vector
3008 )
3009 {
3010 UInt di;
3011 Obj vp;
3012 UInt * sum;
3013 UInt * bv;
3014 const UInt * vec;
3015 const UInt * end;
3016 const UInt * w;
3017
3018
3019 // maybe we don't add this basis vector -- if this leaves us enough
3020 // possibilitiies
3021 if (pos + cnt < l) {
3022 bd = AClosVec(veclis, ovec, osum, pos + 1, l, len, cnt, stop, bd, obv,
3023 coords, bcoords);
3024 if (bd <= stop) {
3025 return bd;
3026 }
3027 }
3028
3029
3030 // Otherwise we do
3031
3032 vec = CONST_BLOCKS_GF2VEC(ovec);
3033 sum = BLOCKS_GF2VEC(osum);
3034 vp = ELM_PLIST(veclis, pos);
3035 w = CONST_BLOCKS_GF2VEC(ELM_PLIST(vp, 1));
3036 AddGF2VecToGF2Vec(sum, w, len);
3037
3038 if (coords != (Obj)0) {
3039 SET_ELM_PLIST(coords, pos, INTOBJ_INT(1));
3040 }
3041
3042
3043 if (cnt == 0) // this is a candidate
3044 {
3045 di = DistGF2Vecs(sum, vec, len);
3046 if (di < bd) {
3047
3048 // store new result
3049 bd = di;
3050 bv = BLOCKS_GF2VEC(obv);
3051 end = bv + ((len + BIPEB - 1) / BIPEB);
3052 while (bv < end)
3053 *bv++ = *sum++;
3054 sum = BLOCKS_GF2VEC(osum);
3055 if (coords != (Obj)0) {
3056 UInt i;
3057 for (i = 1; i <= l; i++) {
3058 Obj x;
3059 x = ELM_PLIST(coords, i);
3060 SET_ELM_PLIST(bcoords, i, x);
3061 }
3062 }
3063 }
3064 }
3065 else // need to add in some more
3066 {
3067 bd = AClosVec(veclis, ovec, osum, pos + 1, l, len, cnt - 1, stop, bd,
3068 obv, coords, bcoords);
3069 if (bd <= stop) {
3070 return bd;
3071 }
3072 }
3073
3074 // reset component
3075 AddGF2VecToGF2Vec(sum, w, len);
3076 if (coords != (Obj)0) {
3077 SET_ELM_PLIST(coords, pos, INTOBJ_INT(0));
3078 }
3079
3080 TakeInterrupt();
3081 return bd;
3082 }
3083
3084
FuncA_CLOS_VEC(Obj self,Obj veclis,Obj vec,Obj cnt,Obj stop)3085 static Obj FuncA_CLOS_VEC(
3086 Obj self,
3087 Obj veclis, // pointers to matrix vectors and their multiples
3088 Obj vec, // vector we compute distance to
3089 Obj cnt, // distances list
3090 Obj stop) // distances list
3091
3092 {
3093 Obj sum; // sum vector
3094 Obj best; // best vector
3095 UInt len;
3096
3097 len = LEN_GF2VEC(vec);
3098
3099 if (!ARE_INTOBJS(cnt, stop))
3100 ErrorMayQuit("AClosVec: cnt and stop must be small integers, not a "
3101 "%s and a %s",
3102 (Int)TNAM_OBJ(cnt), (Int)TNAM_OBJ(stop));
3103
3104
3105 // get space for sum vector and zero out
3106 NEW_GF2VEC(sum, TYPE_LIST_GF2VEC, len);
3107 NEW_GF2VEC(best, TYPE_LIST_GF2VEC, len);
3108
3109 // do the recursive work
3110 AClosVec(veclis, vec, sum, 1, LEN_PLIST(veclis), len, INT_INTOBJ(cnt),
3111 INT_INTOBJ(stop), len + 1, // maximal value +1
3112 best, (Obj)0, (Obj)0);
3113
3114 return best;
3115 }
3116
FuncA_CLOS_VEC_COORDS(Obj self,Obj veclis,Obj vec,Obj cnt,Obj stop)3117 static Obj FuncA_CLOS_VEC_COORDS(
3118 Obj self,
3119 Obj veclis, // pointers to matrix vectors and their multiples
3120 Obj vec, // vector we compute distance to
3121 Obj cnt, // distances list
3122 Obj stop) // distances list
3123
3124 {
3125 Obj sum; // sum vector
3126 Obj best; // best vector
3127 Obj coords; // coefficients of mat to get current
3128 Obj bcoords; // coefficients of mat to get best
3129 Obj res; // length 2 plist for results
3130 UInt len, len2, i;
3131
3132 len = LEN_GF2VEC(vec);
3133 len2 = LEN_PLIST(veclis);
3134
3135 if (!ARE_INTOBJS(cnt, stop))
3136 ErrorMayQuit("AClosVec: cnt and stop must be small integers, not a "
3137 "%s and a %s",
3138 (Int)TNAM_OBJ(cnt), (Int)TNAM_OBJ(stop));
3139
3140
3141 // get space for sum vector and zero out
3142 NEW_GF2VEC(sum, TYPE_LIST_GF2VEC, len);
3143 NEW_GF2VEC(best, TYPE_LIST_GF2VEC, len);
3144
3145 coords = NEW_PLIST(T_PLIST_CYC, len2);
3146 SET_LEN_PLIST(coords, len2);
3147
3148 bcoords = NEW_PLIST(T_PLIST_CYC, len2);
3149 SET_LEN_PLIST(bcoords, len2);
3150
3151 for (i = 1; i <= len2; i++) {
3152 SET_ELM_PLIST(coords, i, INTOBJ_INT(0));
3153 SET_ELM_PLIST(bcoords, i, INTOBJ_INT(0));
3154 }
3155
3156 // do the recursive work
3157 AClosVec(veclis, vec, sum, 1, len2, len, INT_INTOBJ(cnt),
3158 INT_INTOBJ(stop), len + 1, // maximal value +1
3159 best, coords, bcoords);
3160
3161 res = NEW_PLIST(T_PLIST_DENSE_NHOM, 2);
3162 SET_LEN_PLIST(res, 2);
3163 SET_ELM_PLIST(res, 1, best);
3164 SET_ELM_PLIST(res, 2, bcoords);
3165 CHANGED_BAG(res);
3166 return res;
3167 }
3168
3169 /****************************************************************************
3170 **
3171 *F FuncCOSET_LEADERS_INNER_GF2(<self>,<veclis>,<weight>,<tofind>,<leaders>)
3172 **
3173 ** Search for new coset leaders of weight <weight>
3174 */
3175
CosetLeadersInnerGF2(Obj veclis,Obj v,Obj w,UInt weight,UInt pos,Obj leaders,UInt tofind)3176 static UInt CosetLeadersInnerGF2(
3177 Obj veclis, Obj v, Obj w, UInt weight, UInt pos, Obj leaders, UInt tofind)
3178 {
3179 UInt found = 0;
3180 UInt len = LEN_GF2VEC(v);
3181 UInt lenw = LEN_GF2VEC(w);
3182 UInt sy;
3183 UInt u0;
3184 Obj vc;
3185 UInt i;
3186
3187 // We know that the length of w does not exceed BIPEB -4 here
3188 // (or there would not be room in a PLIST for all the coset leaders).
3189 // We use this to do a lot of GF2 vector operations for w "in-place"
3190 //
3191 // Even more in this direction could be done, but this no longer
3192 // the rate-determining step for any feasible application
3193
3194 if (weight == 1) {
3195 for (i = pos; i <= len; i++) {
3196 u0 = CONST_BLOCKS_GF2VEC(ELM_PLIST(ELM_PLIST(veclis, i), 1))[0];
3197 BLOCKS_GF2VEC(w)[0] ^= u0;
3198 BLOCK_ELM_GF2VEC(v, i) |= MASK_POS_GF2VEC(i);
3199
3200 sy = revertbits(CONST_BLOCKS_GF2VEC(w)[0], lenw);
3201 if ((Obj)0 == ELM_PLIST(leaders, sy + 1)) {
3202 NEW_GF2VEC(vc, TYPE_LIST_GF2VEC_IMM, len);
3203 memcpy(BLOCKS_GF2VEC(vc), CONST_BLOCKS_GF2VEC(v),
3204 NUMBER_BLOCKS_GF2VEC(v) * sizeof(UInt));
3205 SET_ELM_PLIST(leaders, sy + 1, vc);
3206 CHANGED_BAG(leaders);
3207 if (++found == tofind)
3208 return found;
3209 }
3210 BLOCKS_GF2VEC(w)[0] ^= u0;
3211 BLOCK_ELM_GF2VEC(v, i) &= ~MASK_POS_GF2VEC(i);
3212 }
3213 }
3214 else {
3215 if (pos + weight <= len) {
3216 found += CosetLeadersInnerGF2(veclis, v, w, weight, pos + 1,
3217 leaders, tofind);
3218 if (found == tofind)
3219 return found;
3220 }
3221 u0 = CONST_BLOCKS_GF2VEC(ELM_PLIST(ELM_PLIST(veclis, pos), 1))[0];
3222 BLOCKS_GF2VEC(w)[0] ^= u0;
3223 BLOCK_ELM_GF2VEC(v, pos) |= MASK_POS_GF2VEC(pos);
3224 found += CosetLeadersInnerGF2(veclis, v, w, weight - 1, pos + 1,
3225 leaders, tofind - found);
3226 if (found == tofind)
3227 return found;
3228 BLOCKS_GF2VEC(w)[0] ^= u0;
3229 BLOCK_ELM_GF2VEC(v, pos) &= ~MASK_POS_GF2VEC(pos);
3230 }
3231 TakeInterrupt();
3232 return found;
3233 }
3234
3235
FuncCOSET_LEADERS_INNER_GF2(Obj self,Obj veclis,Obj weight,Obj tofind,Obj leaders)3236 static Obj FuncCOSET_LEADERS_INNER_GF2(
3237 Obj self, Obj veclis, Obj weight, Obj tofind, Obj leaders)
3238 {
3239 Obj v, w;
3240 UInt lenv, lenw;
3241
3242 if (!ARE_INTOBJS(weight, tofind))
3243 ErrorMayQuit("COSET_LEADERS_INNER_GF2: weight and tofind must be "
3244 "smal integers, not a %s and a %s",
3245 (Int)TNAM_OBJ(weight), (Int)TNAM_OBJ(tofind));
3246
3247 lenv = LEN_PLIST(veclis);
3248 NEW_GF2VEC(v, TYPE_LIST_GF2VEC, lenv);
3249 lenw = LEN_GF2VEC(ELM_PLIST(ELM_PLIST(veclis, 1), 1));
3250 NEW_GF2VEC(w, TYPE_LIST_GF2VEC, lenw);
3251 if (lenw > BIPEB - 4)
3252 ErrorMayQuit("COSET_LEADERS_INNER_GF2: too many cosets to return the "
3253 "leaders in a plain list",
3254 0, 0);
3255 return INTOBJ_INT(CosetLeadersInnerGF2(veclis, v, w, INT_INTOBJ(weight),
3256 1, leaders, INT_INTOBJ(tofind)));
3257 }
3258
3259 /****************************************************************************
3260 **
3261 *F Polynomial Arithmetic Support
3262 */
3263
3264
3265 /****************************************************************************
3266 **
3267 *F FuncRIGHTMOST_NONZERO_GF2VEC (<self>, <vec> )
3268 **
3269 */
3270
FuncRIGHTMOST_NONZERO_GF2VEC(Obj self,Obj vec)3271 static Obj FuncRIGHTMOST_NONZERO_GF2VEC(Obj self, Obj vec)
3272 {
3273 return INTOBJ_INT(RightMostOneGF2Vec(vec));
3274 }
3275
3276 /****************************************************************************
3277 **
3278 *F ResizeGF2Vec( <vec>, <newlen>, <clean> )
3279 **
3280 */
3281
ResizeGF2Vec(Obj vec,UInt newlen)3282 static void ResizeGF2Vec(Obj vec, UInt newlen)
3283 {
3284 UInt len;
3285 UInt * ptr;
3286 UInt * nptr;
3287 UInt off;
3288 len = LEN_GF2VEC(vec);
3289 if (len == newlen)
3290 return;
3291 if (True == DoFilter(IsLockedRepresentationVector, vec)) {
3292 ErrorMayQuit("Resize of locked compressed vector is forbidden", 0, 0);
3293 }
3294
3295
3296 if (newlen > len) {
3297 ResizeWordSizedBag(vec, SIZE_PLEN_GF2VEC(newlen));
3298
3299 // now clean remainder of last block
3300 if (len == 0)
3301 ptr = BLOCKS_GF2VEC(vec);
3302 else {
3303 ptr = BLOCKS_GF2VEC(vec) + (len - 1) / BIPEB;
3304 off = BIPEB - ((len - 1) % BIPEB +
3305 1); // number of insignificant bits in last word
3306 #ifdef SYS_IS_64_BIT
3307 *ptr &= 0xffffffffffffffff >> off;
3308 #else
3309 *ptr &= 0xffffffff >> off;
3310 #endif
3311 ptr++;
3312 }
3313
3314 // and clean new blocks -- shouldn't need to do this, but
3315 // it's very cheap
3316
3317 // newlen can't be zero here, since it is bigger than len
3318 nptr = BLOCKS_GF2VEC(vec) + (newlen - 1) / BIPEB;
3319 while (ptr <= nptr)
3320 *ptr++ = 0;
3321
3322 SET_LEN_GF2VEC(vec, newlen);
3323 return;
3324 }
3325 else {
3326 // clean remainder of new last block, if any
3327 if (newlen % BIPEB) {
3328 ptr = BLOCKS_GF2VEC(vec) + (newlen - 1) / BIPEB;
3329 off = BIPEB - ((newlen - 1) % BIPEB + 1);
3330 #ifdef SYS_IS_64_BIT
3331 *ptr &= 0xffffffffffffffff >> off;
3332 #else
3333 *ptr &= 0xffffffff >> off;
3334 #endif
3335 }
3336 SET_LEN_GF2VEC(vec, newlen);
3337 ResizeWordSizedBag(vec, SIZE_PLEN_GF2VEC(newlen));
3338 return;
3339 }
3340 }
3341
3342 /****************************************************************************
3343 **
3344 *F FuncRESIZE_GF2VEC( <self>, <vec>, <newlen> )
3345 **
3346 */
3347
FuncRESIZE_GF2VEC(Obj self,Obj vec,Obj newlen)3348 static Obj FuncRESIZE_GF2VEC(Obj self, Obj vec, Obj newlen)
3349 {
3350 RequireMutable("RESIZE_GF2VEC", vec, "vector");
3351 RequireNonnegativeSmallInt("RESIZE_GF2VEC", newlen);
3352 ResizeGF2Vec(vec, INT_INTOBJ(newlen));
3353 return (Obj)0;
3354 }
3355
3356
3357 /****************************************************************************
3358 **
3359 *F ShiftLeftGF2Vec( <vec>, <amount> )
3360 **
3361 */
3362
ShiftLeftGF2Vec(Obj vec,UInt amount)3363 static void ShiftLeftGF2Vec(Obj vec, UInt amount)
3364 {
3365 UInt len;
3366 UInt *ptr1, *ptr2;
3367 UInt i;
3368 UInt block;
3369 UInt off;
3370 if (amount == 0)
3371 return;
3372 len = LEN_GF2VEC(vec);
3373 if (amount >= len) {
3374 ResizeGF2Vec(vec, 0);
3375 return;
3376 }
3377 if (amount % BIPEB == 0) {
3378 ptr1 = BLOCKS_GF2VEC(vec);
3379 ptr2 = ptr1 + amount / BIPEB;
3380 for (i = 0; i < (len - amount + BIPEB - 1) / BIPEB; i++)
3381 *ptr1++ = *ptr2++;
3382 }
3383 else {
3384 ptr1 = BLOCKS_GF2VEC(vec);
3385 ptr2 = ptr1 + amount / BIPEB;
3386 off = amount % BIPEB;
3387 for (i = 0; i < (len - amount + BIPEB - 1) / BIPEB - 1; i++) {
3388 block = (*ptr2++) >> off;
3389 block |= (*ptr2) << (BIPEB - off);
3390 *ptr1++ = block;
3391 }
3392 // Handle last block seperately to avoid reading off end of Bag
3393 block = (*ptr2++) >> off;
3394 if (ptr2 < BLOCKS_GF2VEC(vec) + NUMBER_BLOCKS_GF2VEC(vec))
3395 block |= (*ptr2) << (BIPEB - off);
3396 *ptr1 = block;
3397 }
3398 ResizeGF2Vec(vec, len - amount);
3399 }
3400
3401 /****************************************************************************
3402 **
3403 *F FuncSHIFT_LEFT_GF2VEC(<self>, <vec>, <amount> )
3404 **
3405 */
3406
FuncSHIFT_LEFT_GF2VEC(Obj self,Obj vec,Obj amount)3407 static Obj FuncSHIFT_LEFT_GF2VEC(Obj self, Obj vec, Obj amount)
3408 {
3409 RequireMutable("SHIFT_LEFT_GF2VEC", vec, "vector");
3410 RequireNonnegativeSmallInt("SHIFT_LEFT_GF2VEC", amount);
3411 ShiftLeftGF2Vec(vec, INT_INTOBJ(amount));
3412 return (Obj)0;
3413 }
3414
3415 /****************************************************************************
3416 **
3417 *F ShiftRightGF2Vec( <vec>, <amount> )
3418 **
3419 */
3420
ShiftRightGF2Vec(Obj vec,UInt amount)3421 static void ShiftRightGF2Vec(Obj vec, UInt amount)
3422 {
3423 UInt len;
3424 UInt *ptr1, *ptr2, *ptr0;
3425 UInt i;
3426 UInt block;
3427 UInt off;
3428 if (amount == 0)
3429 return;
3430 len = LEN_GF2VEC(vec);
3431 ResizeGF2Vec(vec, len + amount);
3432 if (amount % BIPEB == 0) {
3433 // move the blocks
3434 ptr1 = BLOCKS_GF2VEC(vec) + (len - 1 + amount) / BIPEB;
3435 ptr2 = ptr1 - amount / BIPEB;
3436 for (i = 0; i < (len + BIPEB - 1) / BIPEB; i++)
3437 *ptr1-- = *ptr2--;
3438
3439 // and fill with zeroes
3440 ptr2 = BLOCKS_GF2VEC(vec);
3441 while (ptr1 >= ptr2)
3442 *ptr1-- = 0;
3443 }
3444 else {
3445 ptr1 = BLOCKS_GF2VEC(vec) + (len - 1 + amount) / BIPEB;
3446 ptr2 = ptr1 - amount / BIPEB; // this can sometimes be the block
3447 // AFTER the old last block, but this
3448 // must be OK
3449 off = amount % BIPEB;
3450 ptr0 = BLOCKS_GF2VEC(vec);
3451 while (1) {
3452 block = (*ptr2--) << off;
3453 if (ptr2 < ptr0)
3454 break;
3455 block |= (*ptr2) >> (BIPEB - off);
3456 *ptr1-- = block;
3457 }
3458 *ptr1-- = block;
3459 while (ptr1 >= ptr0)
3460 *ptr1-- = 0;
3461 }
3462 }
3463
3464 /****************************************************************************
3465 **
3466 *F FuncSHIFT_RIGHT_GF2VEC(<self>, <vec>, <amount> )
3467 **
3468 */
3469
FuncSHIFT_RIGHT_GF2VEC(Obj self,Obj vec,Obj amount)3470 static Obj FuncSHIFT_RIGHT_GF2VEC(Obj self, Obj vec, Obj amount)
3471 {
3472 RequireMutable("SHIFT_RIGHT_GF2VEC", vec, "vector");
3473 RequireNonnegativeSmallInt("SHIFT_RIGHT_GF2VEC", amount);
3474 ShiftRightGF2Vec(vec, INT_INTOBJ(amount));
3475 return (Obj)0;
3476 }
3477
3478 // ReduceCoeffs
3479
3480 /****************************************************************************
3481 **
3482 *F AddShiftedVecGF2VecGF2( <vec1>, <vec2>, <len2>, <off> )
3483 **
3484 */
3485
AddShiftedVecGF2VecGF2(Obj vec1,Obj vec2,UInt len2,UInt off)3486 static void AddShiftedVecGF2VecGF2(Obj vec1, Obj vec2, UInt len2, UInt off)
3487 {
3488 UInt * ptr1;
3489 const UInt * ptr2;
3490 UInt i;
3491 UInt block;
3492 UInt shift1, shift2;
3493 if (off % BIPEB == 0) {
3494 ptr1 = BLOCKS_GF2VEC(vec1) + off / BIPEB;
3495 ptr2 = CONST_BLOCKS_GF2VEC(vec2);
3496 for (i = 0; i < (len2 - 1) / BIPEB; i++)
3497 *ptr1++ ^= *ptr2++;
3498 block = *ptr2;
3499 #ifdef SYS_IS_64_BIT
3500 block &= (0xFFFFFFFFFFFFFFFF >> (BIPEB - (len2 - 1) % BIPEB - 1));
3501 #else
3502 block &= (0xFFFFFFFF >> (BIPEB - (len2 - 1) % BIPEB - 1));
3503 #endif
3504 *ptr1 ^= block;
3505 }
3506 else {
3507 ptr1 = BLOCKS_GF2VEC(vec1) + off / BIPEB;
3508 ptr2 = CONST_BLOCKS_GF2VEC(vec2);
3509 shift1 = off % BIPEB;
3510 shift2 = BIPEB - off % BIPEB;
3511 for (i = 0; i < len2 / BIPEB; i++) {
3512 *ptr1++ ^= *ptr2 << shift1;
3513 *ptr1 ^= *ptr2++ >> shift2;
3514 }
3515
3516 if (len2 % BIPEB) {
3517 block = *ptr2;
3518 #ifdef SYS_IS_64_BIT
3519 block &= 0xFFFFFFFFFFFFFFFF >> (BIPEB - (len2 - 1) % BIPEB - 1);
3520 #else
3521 block &= 0xFFFFFFFF >> (BIPEB - (len2 - 1) % BIPEB - 1);
3522 #endif
3523 *ptr1++ ^= block << shift1;
3524 if (len2 % BIPEB + off % BIPEB > BIPEB) {
3525 assert(ptr1 < BLOCKS_GF2VEC(vec1) +
3526 (LEN_GF2VEC(vec1) + BIPEB - 1) / BIPEB);
3527 *ptr1 ^= block >> shift2;
3528 }
3529 }
3530 }
3531 }
3532
3533 /****************************************************************************
3534 **
3535 *F FuncADD_GF2VEC_GF2VEC_SHIFTED( <self>, <vec1>, <vec2>, <len2>, <off> )
3536 **
3537 */
3538
3539 static Obj
FuncADD_GF2VEC_GF2VEC_SHIFTED(Obj self,Obj vec1,Obj vec2,Obj len2,Obj off)3540 FuncADD_GF2VEC_GF2VEC_SHIFTED(Obj self, Obj vec1, Obj vec2, Obj len2, Obj off)
3541 {
3542 RequireNonnegativeSmallInt("ADD_GF2VEC_GF2VEC_SHIFTED", off);
3543 RequireNonnegativeSmallInt("ADD_GF2VEC_GF2VEC_SHIFTED", len2);
3544 Int off1 = INT_INTOBJ(off);
3545 Int len2a = INT_INTOBJ(len2);
3546 if (len2a >= LEN_GF2VEC(vec2)) {
3547 ErrorMayQuit(
3548 "ADD_GF2VEC_GF2VEC_SHIFTED: <len2> must be a non-negative "
3549 "integer less than the actual length of the vector",
3550 0, 0);
3551 }
3552 if (len2a + off1 > LEN_GF2VEC(vec1))
3553 ResizeGF2Vec(vec1, len2a + off1);
3554 AddShiftedVecGF2VecGF2(vec1, vec2, len2a, off1);
3555 return (Obj)0;
3556 }
3557
3558 /****************************************************************************
3559 **
3560 *F ProductCoeffsGF2Vec( <vec1>, <len1>, <vec2>, <len2> )
3561 **
3562 */
3563
ProductCoeffsGF2Vec(Obj vec1,UInt len1,Obj vec2,UInt len2)3564 static Obj ProductCoeffsGF2Vec(Obj vec1, UInt len1, Obj vec2, UInt len2)
3565 {
3566 Obj prod;
3567 UInt i, e;
3568 const UInt * ptr;
3569 UInt block = 0;
3570 UInt len;
3571 if (len1 == 0 && len2 == 0)
3572 len = 0;
3573 else
3574 len = len1 + len2 - 1;
3575 NEW_GF2VEC(prod, TYPE_LIST_GF2VEC, len);
3576
3577 // better to do the longer loop on the inside
3578 if (len2 < len1) {
3579 UInt tmp;
3580 Obj tmpv;
3581 tmp = len1;
3582 len1 = len2;
3583 len2 = tmp;
3584 tmpv = vec1;
3585 vec1 = vec2;
3586 vec2 = tmpv;
3587 }
3588
3589 ptr = CONST_BLOCKS_GF2VEC(vec1);
3590 e = BIPEB;
3591 for (i = 0; i < len1; i++) {
3592 if (e == BIPEB) {
3593 block = *ptr++;
3594 e = 0;
3595 }
3596 if (block & ((UInt)1 << e++))
3597 AddShiftedVecGF2VecGF2(prod, vec2, len2, i);
3598 }
3599 return prod;
3600 }
3601
3602 /****************************************************************************
3603 **
3604 *F FuncPROD_COEFFS_GF2VEC( <self>, <vec1>, <len1>, <vec2>, <len2> )
3605 **
3606 */
3607
3608 static Obj
FuncPROD_COEFFS_GF2VEC(Obj self,Obj vec1,Obj len1,Obj vec2,Obj len2)3609 FuncPROD_COEFFS_GF2VEC(Obj self, Obj vec1, Obj len1, Obj vec2, Obj len2)
3610 {
3611 UInt len1a, len2a;
3612 Obj prod;
3613 UInt last;
3614 if (!ARE_INTOBJS(len1, len2))
3615 ErrorMayQuit("PROD_COEFFS_GF2VEC: vector lengths must be small "
3616 "integers, not a %s and a %s",
3617 (Int)TNAM_OBJ(len1), (Int)TNAM_OBJ(len2));
3618 len2a = INT_INTOBJ(len2);
3619 if (len2a > LEN_GF2VEC(vec2))
3620 ErrorMayQuit("PROD_COEFFS_GF2VEC: <len2> must not be more than the "
3621 "actual\nlength of the vector",
3622 0, 0);
3623 len1a = INT_INTOBJ(len1);
3624 if (len1a > LEN_GF2VEC(vec1))
3625 ErrorMayQuit("PROD_COEFFS_GF2VEC: <len1> must be not more than the "
3626 "actual\nlength of the vector",
3627 0, 0);
3628 prod = ProductCoeffsGF2Vec(vec1, len1a, vec2, len2a);
3629 last = RightMostOneGF2Vec(prod);
3630 if (last < LEN_GF2VEC(prod))
3631 ResizeGF2Vec(prod, last);
3632 return prod;
3633 }
3634
3635 /****************************************************************************
3636 **
3637 *F ReduceCoeffsGF2Vec(<vec1>, <vec2>, <len2>, <quotient> )
3638 **
3639 */
3640
ReduceCoeffsGF2Vec(Obj vec1,Obj vec2,UInt len2,Obj quotient)3641 static void ReduceCoeffsGF2Vec(Obj vec1, Obj vec2, UInt len2, Obj quotient)
3642 {
3643 UInt len1 = LEN_GF2VEC(vec1);
3644 UInt i, j, e;
3645 const UInt * ptr;
3646 UInt * qptr = (UInt *)0;
3647 if (len2 > len1)
3648 return;
3649 i = len1 - 1;
3650 e = (i % BIPEB);
3651 ptr = CONST_BLOCKS_GF2VEC(vec1) + (i / BIPEB);
3652 if (quotient != (Obj)0)
3653 qptr = BLOCKS_GF2VEC(quotient);
3654 j = len1 - len2 + 1;
3655 while (i + 1 >= len2) {
3656 if (*ptr & ((UInt)1 << e)) {
3657 AddShiftedVecGF2VecGF2(vec1, vec2, len2, i - len2 + 1);
3658 if (qptr)
3659 qptr[(j - 1) / BIPEB] |= MASK_POS_GF2VEC(j);
3660 }
3661 assert(!(*ptr & ((UInt)1 << e)));
3662 if (e == 0) {
3663 e = BIPEB - 1;
3664 ptr--;
3665 }
3666 else
3667 e--;
3668 i--;
3669 j--;
3670 }
3671 }
3672
3673 /****************************************************************************
3674 **
3675 *F FuncREDUCE_COEFFS_GF2VEC( <self>, <vec1>, <len1>, <vec2>, <len2> )
3676 **
3677 */
3678 static Obj
FuncREDUCE_COEFFS_GF2VEC(Obj self,Obj vec1,Obj len1,Obj vec2,Obj len2)3679 FuncREDUCE_COEFFS_GF2VEC(Obj self, Obj vec1, Obj len1, Obj vec2, Obj len2)
3680 {
3681 UInt last;
3682 Int len2a;
3683 RequireNonnegativeSmallInt("ReduceCoeffs", len1);
3684 RequireNonnegativeSmallInt("ReduceCoeffs", len2);
3685 if (INT_INTOBJ(len1) > LEN_GF2VEC(vec1))
3686 ErrorMayQuit("ReduceCoeffs: given length <len1> of left argt "
3687 "(%d)\nis longer than the argt (%d)",
3688 INT_INTOBJ(len1), LEN_GF2VEC(vec1));
3689 len2a = INT_INTOBJ(len2);
3690 if (len2a > LEN_GF2VEC(vec2))
3691 ErrorMayQuit("ReduceCoeffs: given length <len2> of right argt "
3692 "(%d)\nis longer than the argt (%d)",
3693 len2a, LEN_GF2VEC(vec2));
3694 ResizeGF2Vec(vec1, INT_INTOBJ(len1));
3695
3696 while (0 < len2a) {
3697 if (CONST_BLOCK_ELM_GF2VEC(vec2, len2a) == 0)
3698 len2a = BIPEB * ((len2a - 1) / BIPEB);
3699 else if (CONST_BLOCK_ELM_GF2VEC(vec2, len2a) & MASK_POS_GF2VEC(len2a))
3700 break;
3701 else
3702 len2a--;
3703 }
3704
3705 if (len2a == 0) {
3706 ErrorReturnVoid("ReduceCoeffs: second argument must not be zero", 0,
3707 0, "you may 'return;' to skip the reduction");
3708 return 0;
3709 }
3710
3711 ReduceCoeffsGF2Vec(vec1, vec2, len2a, (Obj)0);
3712 last = RightMostOneGF2Vec(vec1);
3713 ResizeGF2Vec(vec1, last);
3714 return INTOBJ_INT(last);
3715 }
3716
3717 /****************************************************************************
3718 **
3719 *F FuncQUOTREM_COEFFS_GF2VEC( <self>, <vec1>, <len1>, <vec2>, <len2> )
3720 **
3721 */
3722 static Obj
FuncQUOTREM_COEFFS_GF2VEC(Obj self,Obj vec1,Obj len1,Obj vec2,Obj len2)3723 FuncQUOTREM_COEFFS_GF2VEC(Obj self, Obj vec1, Obj len1, Obj vec2, Obj len2)
3724 {
3725 Int len2a;
3726 Int len1a = INT_INTOBJ(len1);
3727 Obj quotv, remv, ret;
3728 RequireNonnegativeSmallInt("QuotremCoeffs", len1);
3729 RequireNonnegativeSmallInt("QuotremCoeffs", len2);
3730 if (INT_INTOBJ(len1) > LEN_GF2VEC(vec1))
3731 ErrorMayQuit("QuotremCoeffs: given length <len1> of left argt "
3732 "(%d)\nis longer than the argt (%d)",
3733 INT_INTOBJ(len1), LEN_GF2VEC(vec1));
3734 len2a = INT_INTOBJ(len2);
3735 if (len2a > LEN_GF2VEC(vec2))
3736 ErrorMayQuit("QuotremCoeffs: given length <len2> of right argt "
3737 "(%d)\nis longer than the argt (%d)",
3738 len2a, LEN_GF2VEC(vec2));
3739
3740 while (0 < len2a) {
3741 if (CONST_BLOCK_ELM_GF2VEC(vec2, len2a) == 0)
3742 len2a = BIPEB * ((len2a - 1) / BIPEB);
3743 else if (CONST_BLOCK_ELM_GF2VEC(vec2, len2a) & MASK_POS_GF2VEC(len2a))
3744 break;
3745 else
3746 len2a--;
3747 }
3748 if (len2a == 0) {
3749 ErrorReturnVoid("QuotremCoeffs: second argument must not be zero", 0,
3750 0, "you may 'return;' to skip the reduction");
3751 return 0;
3752 }
3753
3754 NEW_GF2VEC(remv, TYPE_LIST_GF2VEC, len1a);
3755 memcpy(BLOCKS_GF2VEC(remv), CONST_BLOCKS_GF2VEC(vec1),
3756 ((len1a + BIPEB - 1) / BIPEB) * sizeof(UInt));
3757
3758 NEW_GF2VEC(quotv, TYPE_LIST_GF2VEC, len1a - len2a + 1);
3759 ReduceCoeffsGF2Vec(remv, vec2, len2a, quotv);
3760
3761 ret = NEW_PLIST(T_PLIST_TAB, 2);
3762 SET_LEN_PLIST(ret, 2);
3763
3764 SET_ELM_PLIST(ret, 1, quotv);
3765 SET_ELM_PLIST(ret, 2, remv);
3766
3767 CHANGED_BAG(ret);
3768
3769 return ret;
3770 }
3771
3772
3773 /****************************************************************************
3774 **
3775 *F FuncSEMIECHELON_LIST_GF2VECS( <self>, <mat> )
3776 **
3777 ** Method for SemiEchelonMat for plain lists of GF2 vectors
3778 **
3779 ** Method selection can guarantee us a plain list of characteristic 2
3780 ** vectors
3781 */
3782
FuncSEMIECHELON_LIST_GF2VECS(Obj self,Obj mat)3783 static Obj FuncSEMIECHELON_LIST_GF2VECS(Obj self, Obj mat)
3784 {
3785 UInt i, len;
3786 UInt width;
3787 Obj row;
3788 // check argts
3789 len = LEN_PLIST(mat);
3790 if (!len)
3791 return TRY_NEXT_METHOD;
3792 row = ELM_PLIST(mat, 1);
3793 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row))
3794 return TRY_NEXT_METHOD;
3795 width = LEN_GF2VEC(row);
3796 if (width == 0)
3797 return TRY_NEXT_METHOD;
3798 for (i = 2; i <= len; i++) {
3799 row = ELM_PLIST(mat, i);
3800 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
3801 LEN_GF2VEC(row) != width) {
3802 return TRY_NEXT_METHOD;
3803 }
3804 }
3805 return SemiEchelonListGF2Vecs(mat, 0);
3806 }
3807
3808 /****************************************************************************
3809 **
3810 *F FuncSEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS( <self>, <mat> )
3811 **
3812 ** Method for SemiEchelonMatTransformations for plain lists of GF2 vectors
3813 **
3814 ** Method selection can guarantee us a plain list of characteristic 2
3815 ** vectors
3816 */
3817
FuncSEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS(Obj self,Obj mat)3818 static Obj FuncSEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS(Obj self, Obj mat)
3819 {
3820 UInt i, len;
3821 UInt width;
3822 Obj row;
3823 // check argts
3824 len = LEN_PLIST(mat);
3825 if (!len)
3826 return TRY_NEXT_METHOD;
3827 row = ELM_PLIST(mat, 1);
3828 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row))
3829 return TRY_NEXT_METHOD;
3830 width = LEN_GF2VEC(row);
3831 if (width == 0)
3832 return TRY_NEXT_METHOD;
3833 for (i = 2; i <= len; i++) {
3834 row = ELM_PLIST(mat, i);
3835 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
3836 LEN_GF2VEC(row) != width) {
3837 return TRY_NEXT_METHOD;
3838 }
3839 }
3840 return SemiEchelonListGF2Vecs(mat, 1);
3841 }
3842
3843 /****************************************************************************
3844 **
3845 *F FuncTRIANGULIZE_LIST_GF2VECS( <self>, <mat> )
3846 **
3847 */
3848
FuncTRIANGULIZE_LIST_GF2VECS(Obj self,Obj mat)3849 static Obj FuncTRIANGULIZE_LIST_GF2VECS(Obj self, Obj mat)
3850 {
3851 UInt i, len;
3852 UInt width;
3853 Obj row;
3854 // check argts
3855 len = LEN_PLIST(mat);
3856 if (!len)
3857 return TRY_NEXT_METHOD;
3858 row = ELM_PLIST(mat, 1);
3859 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row))
3860 return TRY_NEXT_METHOD;
3861 width = LEN_GF2VEC(row);
3862 if (width == 0)
3863 return TRY_NEXT_METHOD;
3864 for (i = 2; i <= len; i++) {
3865 row = ELM_PLIST(mat, i);
3866 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
3867 LEN_GF2VEC(row) != width) {
3868 return TRY_NEXT_METHOD;
3869 }
3870 }
3871 TriangulizeListGF2Vecs(mat, 1);
3872 return (Obj)0;
3873 }
3874
3875 /****************************************************************************
3876 **
3877 *F FuncRANK_LIST_GF2VECS( <self>, <mat> )
3878 **
3879 */
3880
FuncRANK_LIST_GF2VECS(Obj self,Obj mat)3881 static Obj FuncRANK_LIST_GF2VECS(Obj self, Obj mat)
3882 {
3883 UInt i, len;
3884 UInt width;
3885 Obj row;
3886 // check argts
3887 len = LEN_PLIST(mat);
3888 if (!len)
3889 return TRY_NEXT_METHOD;
3890 row = ELM_PLIST(mat, 1);
3891 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row))
3892 return TRY_NEXT_METHOD;
3893 width = LEN_GF2VEC(row);
3894 if (width == 0)
3895 return TRY_NEXT_METHOD;
3896 for (i = 2; i <= len; i++) {
3897 row = ELM_PLIST(mat, i);
3898 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
3899 LEN_GF2VEC(row) != width) {
3900 return TRY_NEXT_METHOD;
3901 }
3902 }
3903 return INTOBJ_INT(TriangulizeListGF2Vecs(mat, 0));
3904 }
3905
3906 /****************************************************************************
3907 **
3908 *F FuncDETERMINANT_LIST_GF2VECS( <self>, <mat> )
3909 **
3910 */
3911
FuncDETERMINANT_LIST_GF2VECS(Obj self,Obj mat)3912 static Obj FuncDETERMINANT_LIST_GF2VECS(Obj self, Obj mat)
3913 {
3914 UInt i, len;
3915 UInt width;
3916 Obj row;
3917 // check argts
3918 len = LEN_PLIST(mat);
3919 if (!len)
3920 return TRY_NEXT_METHOD;
3921 row = ELM_PLIST(mat, 1);
3922 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row))
3923 return TRY_NEXT_METHOD;
3924 width = LEN_GF2VEC(row);
3925 if (width == 0)
3926 return TRY_NEXT_METHOD;
3927 for (i = 2; i <= len; i++) {
3928 row = ELM_PLIST(mat, i);
3929 if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
3930 LEN_GF2VEC(row) != width) {
3931 return TRY_NEXT_METHOD;
3932 }
3933 }
3934 return (len == TriangulizeListGF2Vecs(mat, 0)) ? GF2One : GF2Zero;
3935 }
3936
3937 /****************************************************************************
3938 **
3939 *F FuncKRONECKERPRODUCT_GF2MAT_GF2MAT( <self>, <matl>, <matr>)
3940 **
3941 */
3942
FuncKRONECKERPRODUCT_GF2MAT_GF2MAT(Obj self,Obj matl,Obj matr)3943 static Obj FuncKRONECKERPRODUCT_GF2MAT_GF2MAT(Obj self, Obj matl, Obj matr)
3944 {
3945 UInt nrowl, nrowr, nrowp, ncoll, ncolr, ncolp, ncol, i, j, k, l, mutable;
3946 Obj mat, type, row, shift[BIPEB];
3947 UInt * data;
3948 const UInt * datar;
3949
3950 nrowl = LEN_GF2MAT(matl);
3951 nrowr = LEN_GF2MAT(matr);
3952 nrowp = nrowl * nrowr;
3953 ncoll = LEN_GF2VEC(ELM_GF2MAT(matl, 1));
3954 ncolr = LEN_GF2VEC(ELM_GF2MAT(matr, 1));
3955 ncolp = ncoll * ncolr;
3956
3957 mutable = IS_MUTABLE_OBJ(matl) || IS_MUTABLE_OBJ(matr);
3958
3959 // create a matrix
3960 mat = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(nrowp));
3961 SET_LEN_GF2MAT(mat, nrowp);
3962 if (mutable) {
3963 SET_TYPE_POSOBJ(mat, TYPE_LIST_GF2MAT);
3964 type = TYPE_LIST_GF2VEC_LOCKED;
3965 }
3966 else {
3967 SET_TYPE_POSOBJ(mat, TYPE_LIST_GF2MAT_IMM);
3968 type = TYPE_LIST_GF2VEC_IMM_LOCKED;
3969 }
3970
3971 // allocate 0 matrix
3972
3973 for (i = 1; i <= nrowp; i++) {
3974 NEW_GF2VEC(row, type, ncolp);
3975 SET_ELM_GF2MAT(mat, i, row);
3976 CHANGED_BAG(mat);
3977 }
3978
3979 // allocate data for shifts of rows of matr
3980 for (i = 0; i < BIPEB; i++) {
3981 shift[i] = NewBag(T_DATOBJ, SIZE_PLEN_GF2VEC(ncolr + 2 * BIPEB));
3982 }
3983
3984 // fill in matrix
3985 for (j = 1; j <= nrowr; j++) {
3986 // create shifts of rows of matr
3987 data = (UInt *)ADDR_OBJ(shift[0]);
3988 datar = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(matr, j));
3989 for (k = 0; k < (ncolr + BIPEB - 1) / BIPEB; k++)
3990 data[k] = datar[k];
3991 data[k] = 0;
3992
3993 for (i = 1; i < BIPEB; i++) { // now shifts in [1..BIPEB-1]
3994 data = (UInt *)ADDR_OBJ(shift[i]);
3995 datar = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(matr, j));
3996 data[0] = datar[0] << i;
3997 for (k = 1; k < (ncolr + BIPEB - 1) / BIPEB; k++)
3998 data[k] = (datar[k] << i) | (datar[k - 1] >> (BIPEB - i));
3999 data[k] = datar[k - 1] >> (BIPEB - i);
4000 }
4001 for (i = 1; i <= nrowl; i++) {
4002 data = BLOCKS_GF2VEC(ELM_GF2MAT(mat, (i - 1) * nrowr + j));
4003 ncol = 0;
4004 for (k = 1; k <= ncoll; k++) {
4005 l = 0;
4006 if (CONST_BLOCK_ELM_GF2VEC(ELM_GF2MAT(matl, i), k) &
4007 MASK_POS_GF2VEC(k)) {
4008 // append shift[ncol%BIPEB] to data
4009 datar = (const UInt *)CONST_ADDR_OBJ(shift[ncol % BIPEB]);
4010 if (ncol % BIPEB) {
4011 data[-1] ^= *datar++;
4012 l = BIPEB - ncol % BIPEB;
4013 }
4014 for (; l < ncolr; l += BIPEB)
4015 *data++ = *datar++;
4016 }
4017 else {
4018 if (ncol % BIPEB)
4019 l = BIPEB - ncol % BIPEB;
4020 data += (ncolr + BIPEB - 1 - l) / BIPEB;
4021 }
4022 ncol += ncolr;
4023 }
4024 }
4025 }
4026
4027 return mat;
4028 }
4029
4030
4031 /****************************************************************************
4032 **
4033 *F FuncMAT_ELM_GF2MAT( <self>, <mat>, <row>, <col> )
4034 **
4035 */
FuncMAT_ELM_GF2MAT(Obj self,Obj mat,Obj row,Obj col)4036 static Obj FuncMAT_ELM_GF2MAT(Obj self, Obj mat, Obj row, Obj col)
4037 {
4038 UInt r = GetPositiveSmallInt("MAT_ELM_GF2MAT", row);
4039 UInt c = GetPositiveSmallInt("MAT_ELM_GF2MAT", col);
4040
4041 if (LEN_GF2MAT(mat) < r) {
4042 ErrorMayQuit("row index %d exceeds %d, the number of rows", r,
4043 LEN_GF2MAT(mat));
4044 }
4045
4046 Obj vec = ELM_GF2MAT(mat, r);
4047
4048 if (LEN_GF2VEC(vec) < c) {
4049 ErrorMayQuit("column index %d exceeds %d, the number of columns", c,
4050 LEN_GF2VEC(vec));
4051 }
4052
4053 return ELM_GF2VEC(vec, c);
4054 }
4055
4056
4057 /****************************************************************************
4058 **
4059 *F FuncSET_MAT_ELM_GF2MAT( <self>, <mat>, <row>, <col>, <elm> )
4060 **
4061 */
4062 static Obj
FuncSET_MAT_ELM_GF2MAT(Obj self,Obj mat,Obj row,Obj col,Obj elm)4063 FuncSET_MAT_ELM_GF2MAT(Obj self, Obj mat, Obj row, Obj col, Obj elm)
4064 {
4065 UInt r = GetPositiveSmallInt("SET_MAT_ELM_GF2MAT", row);
4066 UInt c = GetPositiveSmallInt("SET_MAT_ELM_GF2MAT", col);
4067
4068 if (LEN_GF2MAT(mat) < r) {
4069 ErrorMayQuit("row index %d exceeds %d, the number of rows", r,
4070 LEN_GF2MAT(mat));
4071 }
4072
4073 Obj vec = ELM_GF2MAT(mat, r);
4074 if (!IS_MUTABLE_OBJ(vec)) {
4075 ErrorMayQuit("row %d is immutable", r, 0);
4076 }
4077
4078 if (LEN_GF2VEC(vec) < c) {
4079 ErrorMayQuit("column index %d exceeds %d, the number of columns", c,
4080 LEN_GF2VEC(vec));
4081 }
4082
4083 if (EQ(GF2One, elm)) {
4084 BLOCK_ELM_GF2VEC(vec, c) |= MASK_POS_GF2VEC(c);
4085 }
4086 else if (EQ(GF2Zero, elm)) {
4087 BLOCK_ELM_GF2VEC(vec, c) &= ~MASK_POS_GF2VEC(c);
4088 }
4089 else {
4090 ErrorMayQuit("SET_MAT_ELM_GF2MAT: assigned element must be a GF(2) "
4091 "element, not a %s",
4092 (Int)TNAM_OBJ(elm), 0L);
4093 }
4094
4095 return 0;
4096 }
4097
4098
4099 /****************************************************************************
4100 **
4101 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
4102 */
4103
4104
4105 /****************************************************************************
4106 **
4107 *V GVarFuncs . . . . . . . . . . . . . . . . . . list of functions to export
4108 */
4109 static StructGVarFunc GVarFuncs[] = {
4110
4111 GVAR_FUNC(CONV_GF2VEC, 1, "list"),
4112 GVAR_FUNC(COPY_GF2VEC, 1, "list"),
4113 GVAR_FUNC(PLAIN_GF2VEC, 1, "gf2vec"),
4114 GVAR_FUNC(PLAIN_GF2MAT, 1, "gf2mat"),
4115 GVAR_FUNC(EQ_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4116 GVAR_FUNC(LT_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4117 GVAR_FUNC(EQ_GF2MAT_GF2MAT, 2, "gf2mat, gf2mat"),
4118 GVAR_FUNC(LT_GF2MAT_GF2MAT, 2, "gf2mat, gf2mat"),
4119 GVAR_FUNC(LEN_GF2VEC, 1, "gf2vec"),
4120 GVAR_FUNC(ELM0_GF2VEC, 2, "gf2vec, pos"),
4121 GVAR_FUNC(ELM_GF2VEC, 2, "gf2vec, pos"),
4122 GVAR_FUNC(ELMS_GF2VEC, 2, "gf2vec, poss"),
4123 GVAR_FUNC(ASS_GF2VEC, 3, "gf2vec, pos, elm"),
4124 GVAR_FUNC(ELM_GF2MAT, 2, "gf2mat, pos"),
4125 GVAR_FUNC(ASS_GF2MAT, 3, "gf2mat, pos, elm"),
4126 GVAR_FUNC(UNB_GF2VEC, 2, "gf2vec, pos"),
4127 GVAR_FUNC(UNB_GF2MAT, 2, "gf2mat, pos"),
4128 GVAR_FUNC(ZERO_GF2VEC, 1, "gf2vec"),
4129 GVAR_FUNC(ZERO_GF2VEC_2, 1, "len"),
4130 GVAR_FUNC(INV_GF2MAT_MUTABLE, 1, "gf2mat"),
4131 GVAR_FUNC(INV_GF2MAT_SAME_MUTABILITY, 1, "gf2mat"),
4132 GVAR_FUNC(INV_GF2MAT_IMMUTABLE, 1, "gf2mat"),
4133 GVAR_FUNC(INV_PLIST_GF2VECS_DESTRUCTIVE, 1, "list"),
4134 GVAR_FUNC(SUM_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4135 GVAR_FUNC(PROD_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4136 GVAR_FUNC(PROD_GF2VEC_GF2MAT, 2, "gf2vec, gf2mat"),
4137 GVAR_FUNC(PROD_GF2MAT_GF2VEC, 2, "gf2mat, gf2vec"),
4138 GVAR_FUNC(PROD_GF2MAT_GF2MAT, 2, "gf2matl, gf2matr"),
4139 GVAR_FUNC(PROD_GF2MAT_GF2MAT_SIMPLE, 2, "gf2matl, gf2matr"),
4140 GVAR_FUNC(PROD_GF2MAT_GF2MAT_ADVANCED,
4141 4,
4142 "gf2matl, gf2matr, greaselevel, blocklevel"),
4143 GVAR_FUNC(ADDCOEFFS_GF2VEC_GF2VEC_MULT, 3, "gf2vec, gf2vec, mul"),
4144 GVAR_FUNC(ADDCOEFFS_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4145 GVAR_FUNC(SHRINKCOEFFS_GF2VEC, 1, "gf2vec"),
4146 GVAR_FUNC(POSITION_NONZERO_GF2VEC, 2, "gf2vec, zero"),
4147 GVAR_FUNC(POSITION_NONZERO_GF2VEC3, 3, "gf2vec, zero, from"),
4148 GVAR_FUNC(MULT_VECTOR_GF2VECS_2, 2, "gf2vecl, mul"),
4149 GVAR_FUNC(APPEND_GF2VEC, 2, "gf2vecl, gf2vecr"),
4150 GVAR_FUNC(SHALLOWCOPY_GF2VEC, 1, "gf2vec"),
4151 GVAR_FUNC(NUMBER_GF2VEC, 1, "gf2vec"),
4152 GVAR_FUNC(TRANSPOSED_GF2MAT, 1, "gf2mat"),
4153 GVAR_FUNC(DIST_GF2VEC_GF2VEC, 2, "gf2vec, gf2vec"),
4154 GVAR_FUNC(DIST_VEC_CLOS_VEC, 3, "list, gf2vec, list"),
4155 GVAR_FUNC(SUM_GF2MAT_GF2MAT, 2, "matl, matr"),
4156 GVAR_FUNC(A_CLOS_VEC, 4, "list, gf2vec, int, int"),
4157 GVAR_FUNC(A_CLOS_VEC_COORDS, 4, "list, gf2vec, int, int"),
4158 GVAR_FUNC(COSET_LEADERS_INNER_GF2, 4, "veclis, weight, tofind, leaders"),
4159 GVAR_FUNC(CONV_GF2MAT, 1, "list"),
4160 GVAR_FUNC(PROD_GF2VEC_ANYMAT, 2, "vec, mat"),
4161 GVAR_FUNC(RIGHTMOST_NONZERO_GF2VEC, 1, "vec"),
4162 GVAR_FUNC(RESIZE_GF2VEC, 2, "vec, newlen"),
4163 GVAR_FUNC(SHIFT_LEFT_GF2VEC, 2, "vec, amount"),
4164 GVAR_FUNC(SHIFT_RIGHT_GF2VEC, 3, "vec, amount, zero"),
4165 GVAR_FUNC(ADD_GF2VEC_GF2VEC_SHIFTED, 4, "vec1, vec2,len2, off"),
4166 GVAR_FUNC(PROD_COEFFS_GF2VEC, 4, "vec1, len1, vec2,len2"),
4167 GVAR_FUNC(REDUCE_COEFFS_GF2VEC, 4, "vec1, len1, vec2,len2"),
4168 GVAR_FUNC(QUOTREM_COEFFS_GF2VEC, 4, "vec1, len1, vec2,len2"),
4169 GVAR_FUNC(SEMIECHELON_LIST_GF2VECS, 1, "mat"),
4170 GVAR_FUNC(SEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS, 1, "mat"),
4171 GVAR_FUNC(TRIANGULIZE_LIST_GF2VECS, 1, "mat"),
4172 GVAR_FUNC(DETERMINANT_LIST_GF2VECS, 1, "mat"),
4173 GVAR_FUNC(RANK_LIST_GF2VECS, 1, "mat"),
4174 GVAR_FUNC(KRONECKERPRODUCT_GF2MAT_GF2MAT, 2, "mat, mat"),
4175 GVAR_FUNC(COPY_SECTION_GF2VECS, 5, "src, dest, from, to, howmany"),
4176 GVAR_FUNC(MAT_ELM_GF2MAT, 3, "mat, row, col"),
4177 GVAR_FUNC(SET_MAT_ELM_GF2MAT, 4, "mat, row, col, elm"),
4178 { 0, 0, 0, 0, 0 }
4179
4180 };
4181
4182
4183 /****************************************************************************
4184 **
4185 *F InitKernel( <module> ) . . . . . . . . initialise kernel data structures
4186 */
InitKernel(StructInitInfo * module)4187 static Int InitKernel(StructInitInfo * module)
4188 {
4189 RNheads = 0;
4190 RNvectors = 0;
4191 RNcoeffs = 0;
4192 RNrelns = 0;
4193
4194 // import type functions
4195 ImportGVarFromLibrary("TYPE_LIST_GF2VEC", &TYPE_LIST_GF2VEC);
4196 ImportGVarFromLibrary("TYPE_LIST_GF2VEC_IMM", &TYPE_LIST_GF2VEC_IMM);
4197 ImportGVarFromLibrary("TYPE_LIST_GF2VEC_IMM_LOCKED",
4198 &TYPE_LIST_GF2VEC_IMM_LOCKED);
4199 ImportGVarFromLibrary("TYPE_LIST_GF2VEC_LOCKED",
4200 &TYPE_LIST_GF2VEC_LOCKED);
4201 ImportFuncFromLibrary("IsGF2VectorRep", &IsGF2VectorRep);
4202 ImportGVarFromLibrary("TYPE_LIST_GF2MAT", &TYPE_LIST_GF2MAT);
4203 ImportGVarFromLibrary("TYPE_LIST_GF2MAT_IMM", &TYPE_LIST_GF2MAT_IMM);
4204
4205 // initialize one and zero of GF2
4206 ImportGVarFromLibrary("GF2One", &GF2One);
4207 ImportGVarFromLibrary("GF2Zero", &GF2Zero);
4208
4209 // init filters and functions
4210 InitHdlrFuncsFromTable(GVarFuncs);
4211
4212 InitFopyGVar("IsLockedRepresentationVector",
4213 &IsLockedRepresentationVector);
4214
4215 // return success
4216 return 0;
4217 }
4218
4219
4220 /****************************************************************************
4221 **
4222 *F InitLibrary( <module> ) . . . . . . . initialise library data structures
4223 */
InitLibrary(StructInitInfo * module)4224 static Int InitLibrary(StructInitInfo * module)
4225 {
4226 // init filters and functions
4227 InitGVarFuncsFromTable(GVarFuncs);
4228
4229 // return success
4230 return 0;
4231 }
4232
4233
4234 /****************************************************************************
4235 **
4236 *F InitInfoGF2Vec() . . . . . . . . . . . . . . . . table of init functions
4237 */
4238 static StructInitInfo module = {
4239 // init struct using C99 designated initializers; for a full list of
4240 // fields, please refer to the definition of StructInitInfo
4241 .type = MODULE_BUILTIN,
4242 .name = "vecgf2",
4243 .initKernel = InitKernel,
4244 .initLibrary = InitLibrary,
4245 };
4246
InitInfoGF2Vec(void)4247 StructInitInfo * InitInfoGF2Vec(void)
4248 {
4249 return &module;
4250 }
4251