/**************************************************************************** ** ** This file is part of GAP, a system for computational discrete algebra. ** ** Copyright of GAP belongs to its developers, whose names are too numerous ** to list here. Please refer to the COPYRIGHT file for details. ** ** SPDX-License-Identifier: GPL-2.0-or-later
*/
/**************************************************************************** ** *F AddCoeffsGF2VecGF2Vec( <sum>, <vec> ) . . . . . . . . add <vec> to <sum> ** ** `AddCoeffsGF2VecGF2Vec' adds the entries of <vec> to <sum>. If the ** length are not equal the missing entries are assumed to be zero. The ** position of the rightmost Z(2) is returned.
*/
/**************************************************************************** ** *F AddPartialGF2VecGF2Vec( <sum>, <vl>, <vr>, <n> ) . . . . . . partial sum ** ** 'AddPartialGF2VecGF2Vec' adds the entries of <vl> and <vr> starting from ** that block which is corresponding to the entry with number <n> and stores ** the result in <sum>. ** ** Note: The other entries are set to be zero. So use a higher value for <n> ** only for vectors, which both have leading zero-entries. ** ** You can use the parameter <n> for example for an gauss-algorithm on ** gf2-matrices can be improved, because when using the gauss-algorithm, ** you know that the leading entries of two vectors to be added are equal ** zero. If <n> = 1 all entries are added. ** ** Note that the caller has to ensure, that <sum> is a gf2-vector with the ** correct size.
*/ static Obj AddPartialGF2VecGF2Vec(Obj sum, Obj vl, Obj vr, UInt n)
{ const UInt * ptL; // bit field of <vl> const UInt * ptR; // bit field of <vr>
UInt * ptS; // bit field of <sum>
UInt * end; // end marker
UInt len; // length of the list
UInt offset; // number of block to start adding
UInt x;
// both operands lie in the same field
len = LEN_GF2VEC(vl); if (len != LEN_GF2VEC(vr)) {
ErrorMayQuit("Vector +: vectors must have the same length", 0, 0);
}
// loop over the entries and add if (vl == sum) while (ptS < end) { // maybe remove this condition if ((x = *ptR) != 0)
*ptS = *ptL ^ x;
ptL++;
ptS++;
ptR++;
} elseif (vr == sum) while (ptS < end) { // maybe remove this condition if ((x = *ptL) != 0)
*ptS = *ptR ^ x;
ptL++;
ptS++;
ptR++;
} else while (ptS < end)
*ptS++ = *ptL++ ^ *ptR++;
return sum;
}
/**************************************************************************** ** *F ProdGF2VecGF2Vec( <vl>, <vr> ) . . . . . . . product of two GF2 vectors ** ** 'ProdVecGF2VecGF2' returns the product of the two GF2 vectors <vl> and ** <vr>. The product is the folded sum of the corresponding entries of ** <vl> and <vr>. ** ** 'ProdVecGF2VecGF2' is an improved version of the general multiplication, ** which does not call 'PROD' but uses bit operations instead. It will ** always return either 'GF2One' or 'GF2Zero'.
*/ #ifdef SYS_IS_64_BIT
#define PARITY_BLOCK(m) \ do { \
m = m ^ (m >> 32); \
m = m ^ (m >> 16); \
m = m ^ (m >> 8); \
m = m ^ (m >> 4); \
m = m ^ (m >> 2); \
m = m ^ (m >> 1); \
} while (0)
#else
#define PARITY_BLOCK(m) \ do { \
m = m ^ (m >> 16); \
m = m ^ (m >> 8); \
m = m ^ (m >> 4); \
m = m ^ (m >> 2); \
m = m ^ (m >> 1); \
} while (0)
#endif
static Obj ProdGF2VecGF2Vec(Obj vl, Obj vr)
{ const UInt * ptL; // bit field of <vl> const UInt * ptR; // bit field of <vr>
UInt lenL; // length of the list
UInt lenR; // length of the list
UInt len; // minimum of the lengths
UInt nrb; // number of whole blocks to use
UInt m; // number of bits in a block
UInt n; // number of bits in blist
UInt i; // loop variable
UInt mask; // bit selecting mask
// both operands lie in the same field
lenL = LEN_GF2VEC(vl);
lenR = LEN_GF2VEC(vr);
len = (lenL < lenR) ? lenL : lenR;
if (len == 0) {
ErrorMayQuit("Vector *: both vectors must have at least one entry",
(Int)0, (Int)0);
}
// loop over the entries and multiply
ptL = CONST_BLOCKS_GF2VEC(vl);
ptR = CONST_BLOCKS_GF2VEC(vr);
nrb = len / BIPEB;
n = 0; for (i = nrb; i > 0; i--) {
m = (*ptL++) & (*ptR++);
PARITY_BLOCK(m);
n ^= m;
} // now process the remaining bits
mask = 1; for (i = 0; i < len % BIPEB; i++) {
n ^= (mask & *ptL & *ptR) >> i;
mask <<= 1;
}
return (n & 1) ? GF2One : GF2Zero;
}
/**************************************************************************** ** *F ProdGF2VecGF2Mat( <vl>, <vr> ) . . product of GF2 vector and GF2 matrix ** ** 'ProdGF2VecGF2Mat' returns the product of the GF2 vector <vl> and the ** GF2 matrix <vr>. The product is the sum of the rows of <vr>, each ** multiplied by the corresponding entry of <vl>. Note that the caller has ** to ensure, that <vl> is a gf2-vector and <vr> is a gf2-matrix.
*/ static Obj ProdGF2VecGF2Mat(Obj vl, Obj vr)
{
UInt len; // length of the list
UInt stop;
UInt col; // length of the rows
UInt i; // loop variables
Obj prod; // product, result
Obj row1; // top row of matrix
UInt * start; const UInt * ptL;
UInt mask;
// both operands lie in the same field
len = LEN_GF2VEC(vl); if (len > LEN_GF2MAT(vr))
len = LEN_GF2MAT(vr);
// make the result vector
row1 = ELM_GF2MAT(vr, 1);
col = LEN_GF2VEC(row1);
NEW_GF2VEC(prod,
(IS_MUTABLE_OBJ(vl) || IS_MUTABLE_OBJ(row1))
? TYPE_LIST_GF2VEC
: TYPE_LIST_GF2VEC_IMM,
col);
// get the start and end block
start = BLOCKS_GF2VEC(prod);
ptL = CONST_BLOCKS_GF2VEC(vl);
// loop over the vector for (i = 1; i <= len; ptL++) {
// if the whole block is zero, get the next entry if (*ptL == 0) {
i += BIPEB; continue;
}
// run through the block
stop = i + BIPEB - 1; if (len < stop)
stop = len; for (mask = 1; i <= stop; i++, mask <<= 1) {
// if there is entry add the row to the result if ((*ptL & mask) != 0) { const UInt * ptRR = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(vr, i));
AddGF2VecToGF2Vec(start, ptRR, col);
}
}
}
return prod;
}
/**************************************************************************** ** *F ProdGF2MatGF2Vec( <ml>, <vr> ) . . product of GF2 matrix and GF2 vector ** ** 'ProdGF2MatGF2Vec' returns the product of the GF2 matrix <ml> and the ** GF2 vector <vr>. The ith entry of the ** product is the inner product of the ith row of <ml> with <vr>. ** Note that the caller has ** to ensure, that <ml> is a GF2 matrix and <vr> is a GF2 vector.
*/ static Obj ProdGF2MatGF2Vec(Obj ml, Obj vr)
{
UInt len; // length of the vector
UInt ln1; // length of the rows of the mx
UInt ln2; // length of the matrix const UInt * ptL; // bit field of <ml>[j] const UInt * ptR; // bit field of <vr>
UInt nrb; // number of blocks in blist
UInt m; // number of bits in a block
UInt n; // number of bits in blist
UInt i; // loop variable
UInt j; // loop variable
Obj prod; // result
UInt mask; // a one bit mask
// both operands lie in the same field
len = LEN_GF2VEC(vr);
ln2 = LEN_GF2MAT(ml); if (0 == ln2) {
ErrorMayQuit("PROD: empty GF2 matrix * GF2 vector not allowed", 0, 0);
}
ln1 = LEN_GF2VEC(ELM_GF2MAT(ml, 1)); if (len > ln1) {
len = ln1;
}
// make the result vector
NEW_GF2VEC(prod,
(IS_MUTABLE_OBJ(ELM_GF2MAT(ml, 1)) || IS_MUTABLE_OBJ(vr))
? TYPE_LIST_GF2VEC
: TYPE_LIST_GF2VEC_IMM,
ln2);
// loop over the entries and multiply
nrb = len / BIPEB; for (j = 1; j <= ln2; j++) {
ptL = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, j));
ptR = CONST_BLOCKS_GF2VEC(vr);
n = 0; for (i = 1; i <= nrb; i++) {
m = (*ptL++) & (*ptR++);
PARITY_BLOCK(m);
n ^= m;
}
mask = 1; for (i = 0; i < len % BIPEB; i++) {
n ^= (mask & *ptL & *ptR) >> i;
mask <<= 1;
}
if (n & 1)
BLOCK_ELM_GF2VEC(prod, j) |= MASK_POS_GF2VEC(j);
}
return prod;
}
/**************************************************************************** ** *F ProdGF2MatGF2MatSimple( <ml>, <mr> ) . . . . product of two GF2 matrices *F ProdGF2MatGF2MatAdvanced( <ml>, <mr>, <greaselevel>, <blocksize> ) ** . . product of twp GF2 matrices ** ** 'ProdGF2MatGF2MatSimple' returns the product of the GF2 matrix <ml> and ** the GF2 matrix <mr>. This simply calls ProdGF2VecGF2Mat once on each row. ** ** ProdGF2MatGF2MatAdvanced uses the specified grease and blocking to ** accelerate larger matrix multiplies. In this case, the matrix dimensions ** must be compatible.
*/
// Since I'm going to put this vector into a matrix, I must lock its // representation, so that it doesn't get rewritten over GF(2^k)
SetTypeDatObj(row, rtype);
SET_ELM_GF2MAT(prod, i, row);
CHANGED_BAG(prod);
TakeInterrupt();
} return prod;
}
// Utility functions for the advanced matrix multiply code below
// extract nbits bits starting from position from in vector vptr // return them as the nbits least significant bits in a UInt. // Bits are always numbered least-significant first
staticinline UInt getbits(const UInt * vptr, UInt from, UInt nbits)
{
UInt wno = (from - 1) / BIPEB;
UInt word1 = vptr[wno];
UInt shift1 = (from - 1) % BIPEB;
UInt lbit = shift1 + nbits;
UInt word2; if (lbit <= BIPEB) { // range is all in one word
word1 <<= BIPEB - lbit;
word1 >>= BIPEB - nbits;
} else { // range is split across two words
word1 >>= shift1;
lbit -= BIPEB;
word2 = vptr[wno + 1];
word2 <<= BIPEB - lbit;
word2 >>= shift1 - lbit;
word1 |= word2;
} return word1;
}
// To avoid having a lot of arguments to the recursive getgreasedata function, // we put the things that don't change in the recursive call into this // structure
// Make if necessary the grease row for bits controlled by the data in g. // Recursive so can't be inlined staticconst UInt * getgreasedata(struct greaseinfo * g, UInt bits)
{
UInt x, y; const UInt * ps;
UInt * pd; const UInt * ps2;
UInt i;
UInt * pd1; switch (g->pgtags[bits]) { case0: // Need to make the row
x = g->pgrules[bits];
y = bits ^ (1 << x); // make it by adding row x to grease vector indexed y
ps = g->prrows[x];
ps2 = getgreasedata(g, y);
pd1 = g->pgbuf + (bits - 3) * g->nblocks;
pd = pd1; // time critical inner loop for (i = g->nblocks; i > 0; i--)
*pd++ = *ps++ ^ *ps2++; // record that we made it
g->pgtags[bits] = 1; return pd1;
case1: // we've made this one already, so just return it return g->pgbuf + (bits - 3) * g->nblocks;
case2: // This one does not need making, bits actually // has just a single 1 bit in it return g->prrows[g->pgrules[bits]];
} return (UInt *)0; // can't actually get here; include the return to // pacify compiler
}
static Obj
ProdGF2MatGF2MatAdvanced(Obj ml, Obj mr, UInt greasesize, UInt blocksize)
{
Obj prod; // Product Matrix
UInt i, j, k, b; // Loop counters
UInt gs; // Actual level of grease for current block const UInt * rptr; // Pointer to current row of ml
UInt bits; // current chunk of current row, for lookup in grease tables const UInt * v; // pointer to computed grease vector
UInt len, rlen, ilen; // len = length of ml, ilen = row length of ml = // length of mr, rlen = row length of mr
Obj row; // current row of ml, or row of prod when it is being built
Obj rtype; // type of rows of prod
Obj gbuf = (Obj)0; // grease buffer
Obj gtags = (Obj)0; // grease tags (whether that row is known yet
Obj grules = (Obj)0; // rules for making new grease vectors
UInt * pgrules; // pointer to contents of grules
UInt * pgtags = (UInt *)0; // pointer to contents of gtags
UInt * pgbuf = (UInt *)0; // pointer to grease buffer
UInt nwords; // number of words in a row of mr
UInt glen; // 1 << greasesize
UInt bs; // actual size of current block
UInt * pprow; // pointer into current row of prod
Obj lrowptrs; // cache of direct pointers to rows of ml const UInt ** plrows; // and a direct pointer to that cache
Obj rrowptrs; // and for mr const UInt ** prrows;
Obj prowptrs; // and for prod
UInt ** pprows; struct greaseinfo g;
// Make a zero product matrix
prod = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(len));
SET_LEN_GF2MAT(prod, len); if (IS_MUTABLE_OBJ(ml) || IS_MUTABLE_OBJ(mr)) {
SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT); if (IS_MUTABLE_OBJ(ELM_GF2MAT(ml, 1)) ||
IS_MUTABLE_OBJ(ELM_GF2MAT(mr, 1)))
rtype = TYPE_LIST_GF2VEC_LOCKED; else
rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
} else {
SET_TYPE_POSOBJ(prod, TYPE_LIST_GF2MAT_IMM);
rtype = TYPE_LIST_GF2VEC_IMM_LOCKED;
}
for (i = 1; i <= len; i++) {
NEW_GF2VEC(row, rtype, rlen);
SET_ELM_GF2MAT(prod, i, row);
CHANGED_BAG(prod);
}
// Cap greasesize and blocksize by the actual length if (ilen < greasesize)
greasesize = ilen; if (ilen < greasesize * blocksize)
blocksize = (ilen + greasesize - 1) / greasesize;
// Calculate the greasing rules for (j = 3; j < glen; j++) for (i = 0; i < greasesize; i++) if ((j & (1 << i)) != 0) {
pgrules[j] = i; break;
} for (j = 0; j < greasesize; j++)
pgrules[1 << j] = j;
// fill in some more bits of g
g.pgrules = pgrules;
g.nblocks = nwords;
}
// Take direct pointers to all the parts of all the matrices to avoid // multiple indirection overheads
plrows = (const UInt **)ADDR_OBJ(lrowptrs);
prrows = (const UInt **)ADDR_OBJ(rrowptrs);
pprows = (UInt **)ADDR_OBJ(prowptrs);
for (i = 0; i < len; i++) {
plrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, i + 1));
pprows[i] = BLOCKS_GF2VEC(ELM_GF2MAT(prod, i + 1));
} for (i = 0; i < ilen; i++)
prrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mr, i + 1));
// OK, finally ready to start work // loop over blocks for (b = 1; b <= ilen; b += blocksize * greasesize) { // last block may be a small one
bs = blocksize; if ((b + bs * greasesize) > ilen)
bs = (ilen - b + greasesize) / greasesize;
// If we're greasing, start afresh if (greasesize > 1) { for (k = 0; k < bs; k++) { for (j = 0; j < 1 << greasesize; j++)
pgtags[k * glen + j] = 0; // powers of 2 correspond to rows of mr for (j = 0; j < greasesize; j++)
pgtags[k * glen + (1 << j)] = 2;
}
}
// For each block, we run through rows of ml & prod for (j = 1; j <= len; j++) { // get pointers
rptr = plrows[j - 1];
pprow = pprows[j - 1];
// Now within the block, we have multiple grease-units, run // through them for (i = 0; i < bs; i++) { // start of current grease unit
k = b + i * greasesize;
// last unit of last block may be short
gs = greasesize; if (k + gs > ilen)
gs = ilen - k + 1;
// find the appropriate parts of grease tags // grease buffer and mr. Store in g
// get a chunk from a row of ml
bits = getbits(rptr, k, gs);
// 0 means nothing to do if (bits == 0) continue; elseif (bits == 1) // handle this one specially to speed // up the greaselevel 1 case
v = prrows[k - 1]; // -1 is because k is 1-based index else
v = getgreasedata(
&g, bits); // The main case // This function should be inlined
AddGF2VecToGF2Vec(pprow, v, rlen);
}
}
// Allow GAP to respond to Ctrl-C if (TakeInterrupt()) { // Might have been a garbage collection, reload everything if (greasesize >= 2) {
pgtags = (UInt *)ADDR_OBJ(gtags);
pgrules = (UInt *)ADDR_OBJ(grules);
pgbuf = (UInt *)ADDR_OBJ(gbuf); // fill in some more bits of g
g.pgrules = pgrules;
g.nblocks = nwords;
}
plrows = (const UInt **)ADDR_OBJ(lrowptrs);
prrows = (const UInt **)ADDR_OBJ(rrowptrs);
pprows = (UInt **)ADDR_OBJ(prowptrs); for (i = 0; i < len; i++) {
plrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(ml, i + 1));
pprows[i] = BLOCKS_GF2VEC(ELM_GF2MAT(prod, i + 1));
} for (i = 0; i < ilen; i++)
prrows[i] = CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mr, i + 1));
}
} return prod;
}
len = LEN_GF2VEC(vec); if (len > LEN_PLIST(mat))
len = LEN_PLIST(mat);
// Get the first row, to establish the size of the result
row1 = ELM_PLIST(mat, 1); if (!IS_GF2VEC_REP(row1)) return TRY_NEXT_METHOD;
len1 = LEN_GF2VEC(row1);
// create the result space
NEW_GF2VEC(res,
(IS_MUTABLE_OBJ(vec) || IS_MUTABLE_OBJ(row1))
? TYPE_LIST_GF2VEC
: TYPE_LIST_GF2VEC_IMM,
len1);
// Finally, we start work for (i = 1; i <= len; i++) { if (i % BIPEB == 1)
block = CONST_BLOCK_ELM_GF2VEC(vec, i); if (block & MASK_POS_GF2VEC(i)) {
row1 = ELM_PLIST(mat, i); if (!IS_GF2VEC_REP(row1)) return TRY_NEXT_METHOD;
AddPartialGF2VecGF2Vec(res, res, row1, 1);
}
} return res;
}
/**************************************************************************** ** *F InversePlistGF2VecsDesstructive( <list> ) ** ** This is intended to form the core of a method for InverseOp. ** by this point it should be checked that list is a plain list of GF2 ** vectors of equal lengths.
*/ static Obj InversePlistGF2VecsDesstructive(Obj list)
{
UInt len; // dimension
Obj inv; // result
Obj row; // row vector
Obj old; // row from <mat>
Obj tmp; // temporary
UInt * ptQ; // data block of <row> const UInt * ptP; // data block of source row const UInt * end; // end marker const UInt * end2; // end marker
UInt i; // loop variable
UInt k; // loop variable
len = LEN_PLIST(list);
// create the identity matrix
tmp = NEW_PLIST(T_PLIST, len); for (i = len; 0 < i; i--) {
NEW_GF2VEC(row, TYPE_LIST_GF2VEC, len);
BLOCK_ELM_GF2VEC(row, i) |= MASK_POS_GF2VEC(i);
SET_ELM_PLIST(tmp, i, row);
CHANGED_BAG(tmp);
}
SET_LEN_PLIST(tmp, len);
inv = tmp;
// now start with ( id | mat ) towards ( inv | id ) for (k = 1; k <= len; k++) {
// find a nonzero entry in column <k> for (i = k; i <= len; i++) {
row = ELM_PLIST(list, i); if (CONST_BLOCK_ELM_GF2VEC(row, k) & MASK_POS_GF2VEC(k)) break;
} if (i > len) { return Fail;
} if (i != k) {
row = ELM_PLIST(list, i);
SET_ELM_PLIST(list, i, ELM_PLIST(list, k));
SET_ELM_PLIST(list, k, row);
row = ELM_PLIST(inv, i);
SET_ELM_PLIST(inv, i, ELM_PLIST(inv, k));
SET_ELM_PLIST(inv, k, row);
}
// clear entries
old = ELM_PLIST(list, k);
end = CONST_BLOCKS_GF2VEC(old) + ((len + BIPEB - 1) / BIPEB); for (i = 1; i <= len; i++) { if (i == k) continue;
row = ELM_PLIST(list, i); if (CONST_BLOCK_ELM_GF2VEC(row, k) & MASK_POS_GF2VEC(k)) {
/**************************************************************************** ** *F SemiEchelonPlistGF2Vecs( <mat>, <transformations-needed> ) ** ** The matrix needs to have mutable rows, so it can't be a GF2 mat ** ** This has changed. There should now be a method for mutable GF2mats as ** well. ** ** This function DOES NOT CHECK that the rows are all GF2 vectors ** ** Does not copy the matrix, may destroy it, may include some ** of the rows among the returned vectors
*/
// No garbage collection risk from here
rowp = BLOCKS_GF2VEC(row); if (TransformationsNeeded)
coeffrowp = BLOCKS_GF2VEC(coeffrow); for (j = 1; j <= ncols; j++) {
h = INT_INTOBJ(ELM_PLIST(heads, j)); if (h != 0) { if (rowp[(j - 1) / BIPEB] & MASK_POS_GF2VEC(j)) {
AddGF2VecToGF2Vec(
rowp, CONST_BLOCKS_GF2VEC(ELM_PLIST(vectors, h)),
ncols); if (TransformationsNeeded)
AddGF2VecToGF2Vec(
coeffrowp,
CONST_BLOCKS_GF2VEC(ELM_PLIST(coeffs, h)), nrows);
}
}
}
j = 1; while (j <= ncols && !*rowp) {
j += BIPEB;
rowp++;
} while (j <= ncols && !(*rowp & MASK_POS_GF2VEC(j)))
j++;
// garbage collection OK again after here if (j <= ncols) {
SET_ELM_PLIST(vectors, ++nvecs, row);
CHANGED_BAG(vectors); // Could be an old bag by now. Max.
SET_LEN_PLIST(vectors, nvecs);
SET_ELM_PLIST(heads, j, INTOBJ_INT(nvecs)); if (TransformationsNeeded) {
SET_ELM_PLIST(coeffs, nvecs, coeffrow);
CHANGED_BAG(coeffs); // Could be an old bag by now. Max.
SET_LEN_PLIST(coeffs, nvecs);
}
} elseif (TransformationsNeeded) {
SET_ELM_PLIST(relns, ++nrels, coeffrow);
CHANGED_BAG(relns); // Could be an old bag by now. Max.
SET_LEN_PLIST(relns, nrels);
}
TakeInterrupt();
} if (RNheads == 0) {
RNheads = RNamName("heads");
RNvectors = RNamName("vectors");
}
res = NEW_PREC(TransformationsNeeded ? 4 : 2);
AssPRec(res, RNheads, heads);
AssPRec(res, RNvectors, vectors); if (LEN_PLIST(vectors) == 0)
RetypeBag(vectors, T_PLIST_EMPTY); if (TransformationsNeeded) { if (RNcoeffs == 0) {
RNcoeffs = RNamName("coeffs");
RNrelns = RNamName("relations");
}
AssPRec(res, RNcoeffs, coeffs); if (LEN_PLIST(coeffs) == 0)
RetypeBag(coeffs, T_PLIST_EMPTY);
AssPRec(res, RNrelns, relns); if (LEN_PLIST(relns) == 0)
RetypeBag(relns, T_PLIST_EMPTY);
}
SortPRecRNam(res); return res;
}
/**************************************************************************** ** *F UInt TriangulizeListGF2Vecs( <mat>, <clearup> ) -- returns the rank ** ** Again should add a method to work with mutable GF2 matrices **
*/
/**************************************************************************** ** *F PlainGF2Vec( <list> ) . . . . convert a GF2 vector into an ordinary list ** ** 'PlainGF2Vec' converts the GF2 vector <list> to a plain list.
*/ static Obj IsLockedRepresentationVector;
staticvoid PlainGF2Vec(Obj list)
{ Int len; // length of <list>
UInt i; // loop variable
Obj first = 0; // first entry
// check for representation lock if (True == DoFilter(IsLockedRepresentationVector, list))
ErrorMayQuit("Cannot convert a locked GF2 vector into a plain list", 0, 0);
// resize the list and retype it, in this order
len = LEN_GF2VEC(list);
// keep the first entry because setting the second destroys the first if (len == 0)
SET_ELM_PLIST(list, 1, 0); else
first = ELM_GF2VEC(list, 1);
// wipe out the first entry of the GF2 vector (which becomes the second // entry of the plain list, in case the list has length 1. if (len == 1)
SET_ELM_PLIST(list, 2, 0);
// replace the bits by 'GF2One' or 'GF2Zero' as the case may be // this must of course be done from the end of the list backwards for (i = len; 1 < i; i--)
SET_ELM_PLIST(list, i, ELM_GF2VEC(list, i)); if (len != 0)
SET_ELM_PLIST(list, 1, first);
CHANGED_BAG(list);
}
/**************************************************************************** ** *F PlainGF2Mat( <list> ) . . . . convert a GF2 matrix into an ordinary list ** ** 'PlainGF2Mat' converts the GF2 matrix <list> to a plain list.
*/ staticvoid PlainGF2Mat(Obj list)
{ Int len; // length of <list>
UInt i; // loop variable
// resize the list and retype it, in this order
len = LEN_GF2MAT(list);
RetypeBagSM(list, T_PLIST);
SET_LEN_PLIST(list, len);
// shift the entries to the left for (i = 1; i <= len; i++) {
SET_ELM_PLIST(list, i, ELM_GF2MAT(list, i));
}
SHRINK_PLIST(list, len);
CHANGED_BAG(list);
}
/**************************************************************************** ** *F ConvGF2Vec( <list> ) . . . . . . convert a list into a GF2 vector object
*/ staticvoid ConvGF2Vec(Obj list)
{ Int len; // logical length of the vector Int i; // loop variable
UInt block; // one block of the boolean list
UInt bit; // one bit of a block
Obj x;
// already in the correct representation if (IS_GF2VEC_REP(list)) { return;
}
// Otherwise make it a plain list so that we will know where it keeps // its data -- could do much better in the case of GF(2^n) vectors that // actually lie over GF(2)
if (IS_VEC8BIT_REP(list))
PlainVec8Bit(list); else
PLAIN_LIST(list);
// change its representation
len = LEN_PLIST(list);
// We may have to resize the bag now because a length 1 // plain list is shorter than a length 1 GF2VEC if (SIZE_PLEN_GF2VEC(len) > SIZE_OBJ(list))
ResizeBag(list, SIZE_PLEN_GF2VEC(len));
// now do the work
block = 0;
bit = 1; for (i = 1; i <= len; i++) {
x = ELM_PLIST(list, i); if (x == GF2One)
block |= bit; elseif (x != GF2Zero) { // might be GF(2) elt written over bigger field if (EQ(x, GF2One))
block |= bit; elseif (!EQ(x, GF2Zero))
ErrorMayQuit( "COPY_GF2VEC: argument must be a list of GF2 elements", 0, 0);
}
bit = bit << 1; if (bit == 0 || i == len) {
BLOCK_ELM_GF2VEC(list, i) = block;
block = 0;
bit = 1;
}
}
// retype and resize bag
ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(len));
SET_LEN_GF2VEC(list, len); if (IS_PLIST_MUTABLE(list)) {
SetTypeDatObj(list, TYPE_LIST_GF2VEC);
} else {
SetTypeDatObj(list, TYPE_LIST_GF2VEC_IMM);
}
RetypeBag(list, T_DATOBJ);
}
/**************************************************************************** ** *F NewGF2Vec( <list> ) . . . . . . convert a list into a GF2 vector object ** ** This is a non-destructive counterpart of ConvGF2Vec
*/ static Obj NewGF2Vec(Obj list)
{ Int len; // logical length of the vector Int i; // loop variable
UInt block; // one block of the boolean list
UInt bit; // one bit of a block
Obj x;
Obj res; // resulting GF2 vector object
// already in the correct representation if (IS_GF2VEC_REP(list)) {
res = ShallowCopyVecGF2(list); if (!IS_MUTABLE_OBJ(list))
SetTypeDatObj(res, TYPE_LIST_GF2VEC_IMM); return res;
}
if (!IS_LIST(list)) {
ErrorMayQuit("COPY_GF2VEC: argument must be a list of GF2 elements", 0, 0);
} if (!IS_PLIST(list)) {
list = SHALLOW_COPY_OBJ(list); // TODO: if list is in 8bit rep, we could do better if (IS_VEC8BIT_REP(list))
PlainVec8Bit(list); else
PLAIN_LIST(list);
}
len = LEN_PLIST(list);
NEW_GF2VEC(res, TYPE_LIST_GF2VEC, len);
// now do the work
block = 0;
bit = 1; for (i = 1; i <= len; i++) {
x = ELM_PLIST(list, i); if (x == GF2One)
block |= bit; elseif (x != GF2Zero) { // might be GF(2) elt written over bigger field if (EQ(x, GF2One))
block |= bit; elseif (!EQ(x, GF2Zero))
ErrorMayQuit( "COPY_GF2VEC: argument must be a list of GF2 elements", 0, 0);
}
bit = bit << 1; if (bit == 0 || i == len) {
BLOCK_ELM_GF2VEC(res, i) = block; // only changed list to res
block = 0;
bit = 1;
}
}
// mutability should be inherited from the argument if (IS_PLIST_MUTABLE(list))
SetTypeDatObj(res, TYPE_LIST_GF2VEC); else
SetTypeDatObj(res, TYPE_LIST_GF2VEC_IMM);
return res;
}
/**************************************************************************** ** *F FuncCOPY_GF2VEC( <self>, <list> ) . . . . . convert into a GF2 vector rep ** ** This is a non-destructive counterpart of FuncCONV_GF2VEC
*/ static Obj FuncCOPY_GF2VEC(Obj self, Obj list)
{
list = NewGF2Vec(list); return list;
}
/**************************************************************************** ** *F FuncCONV_GF2MAT (<self>, <list> ) . . . convert into a GF2 matrix rep ** ** <list> should be a list of compressed GF2 vectors **
*/ static Obj FuncCONV_GF2MAT(Obj self, Obj list)
{
UInt len, i;
Obj tmp;
UInt mut;
len = LEN_LIST(list); if (len == 0) return (Obj)0;
PLAIN_LIST(list);
GROW_PLIST(list, len + 1); for (i = len; i > 0; i--) {
tmp = ELM_PLIST(list, i); if (!IS_GF2VEC_REP(tmp)) { int j; for (j = i + 1; j <= len; j++) {
tmp = ELM_PLIST(list, j + 1);
SET_ELM_PLIST(list, j, tmp);
}
ErrorMayQuit("CONV_GF2MAT: argument must be a list of compressed " "GF2 vectors", 0, 0);
}
SetTypeDatObj(tmp, IS_MUTABLE_OBJ(tmp) ? TYPE_LIST_GF2VEC_LOCKED
: TYPE_LIST_GF2VEC_IMM_LOCKED);
SET_ELM_PLIST(list, i + 1, tmp);
}
SET_ELM_PLIST(list, 1, INTOBJ_INT(len));
mut = IS_PLIST_MUTABLE(list);
RetypeBag(list, T_POSOBJ);
SET_TYPE_POSOBJ(list, mut ? TYPE_LIST_GF2MAT : TYPE_LIST_GF2MAT_IMM); return (Obj)0;
}
/**************************************************************************** ** *F FuncPLAIN_GF2VEC( <self>, <list> ) . . . convert back into ordinary list
*/ static Obj FuncPLAIN_GF2VEC(Obj self, Obj list)
{ if (!IS_GF2VEC_REP(list)) {
RequireArgument(SELF_NAME, list, "must be a GF2 vector");
}
PlainGF2Vec(list); return0;
}
/**************************************************************************** ** *F revertbits -- utility function to reverse bit orders
*/
// Takes an UInt a on n bits and returns the Uint obtained by reverting the // bits static UInt revertbits(UInt a, Int n)
{
UInt b, c;
b = 0; while (n > 8) {
c = a & 0xff; // last byte
a = a >> 8;
b = b << 8;
b += (UInt)revertlist[(UInt1)c]; // add flipped
n -= 8;
} // cope with the last n bits
a &= 0xff;
b = b << n;
c = (UInt)revertlist[(UInt1)a];
c = c >> (8 - n);
b += c; return b;
}
/**************************************************************************** ** *F Cmp_GF2Vecs( <vl>, <vr> ) compare GF2 vectors -- internal ** returns -1, 0 or 1
*/ staticInt Cmp_GF2VEC_GF2VEC(Obj vl, Obj vr)
{
UInt i; // loop variable const UInt * bl; // block of <vl> const UInt * br; // block of <vr>
UInt len, lenl, lenr; // length of the list
UInt a, b, nb;
// get and check the length
lenl = LEN_GF2VEC(vl);
lenr = LEN_GF2VEC(vr);
nb = NUMBER_BLOCKS_GF2VEC(vl);
a = NUMBER_BLOCKS_GF2VEC(vr); if (a < nb) {
nb = a;
}
// check all blocks
bl = CONST_BLOCKS_GF2VEC(vl);
br = CONST_BLOCKS_GF2VEC(vr); for (i = nb; 1 < i; i--, bl++, br++) { // comparison is numeric of the reverted lists if (*bl != *br) {
a = revertbits(*bl, BIPEB);
b = revertbits(*br, BIPEB); if (a < b) return -1; else return1;
}
}
// The last block remains
len = lenl; if (len > lenr) {
len = lenr;
}
// are both vectors length 0? if (len == 0) return0;
// is there still a full block in common?
len = len % BIPEB; if (len == 0) {
a = revertbits(*bl, BIPEB);
b = revertbits(*br, BIPEB);
} else {
a = revertbits(*bl, len);
b = revertbits(*br, len);
}
if (a < b) return -1; if (a > b) return1;
// blocks still the same --left length must be smaller to be true if (lenr > lenl) return -1; if (lenl > lenr) return1;
return0;
}
/**************************************************************************** ** *F FuncEQ_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) test equality of GF2 vectors
*/ static Obj FuncEQ_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
{ // we can do this case MUCH faster if we just want equality if (LEN_GF2VEC(vl) != LEN_GF2VEC(vr)) returnFalse; return (Cmp_GF2VEC_GF2VEC(vl, vr) == 0) ? True : False;
}
/**************************************************************************** ** *F FuncELM0_GF2VEC( <self>, <list>, <pos> ) . select an elm of a GF2 vector ** ** 'ELM0_GF2VEC' returns the element at the position <pos> of the boolean ** list <list>, or `Fail' if <list> has no assigned object at <pos>. It is ** the responsibility of the caller to ensure that <pos> is a positive ** integer.
*/ static Obj FuncELM0_GF2VEC(Obj self, Obj list, Obj pos)
{
UInt p = GetSmallInt(SELF_NAME, pos); if (LEN_GF2VEC(list) < p) { return Fail;
} else { return ELM_GF2VEC(list, p);
}
}
/**************************************************************************** ** *F FuncELM_GF2VEC( <self>, <list>, <pos> ) . . select an elm of a GF2 vector ** ** 'ELM_GF2VEC' returns the element at the position <pos> of the GF2 vector ** <list>. An error is signalled if <pos> is not bound. It is the ** responsibility of the caller to ensure that <pos> is a positive integer.
*/ static Obj FuncELM_GF2VEC(Obj self, Obj list, Obj pos)
{
UInt p = GetSmallInt(SELF_NAME, pos); if (LEN_GF2VEC(list) < p) {
ErrorMayQuit("List Element: <list>[%d] must have an assigned value",
p, 0);
} else { return ELM_GF2VEC(list, p);
}
}
/**************************************************************************** ** *F FuncELMS_GF2VEC( <self>, <list>, <poss> ) . . . sublist from a GF2 vector ** ** 'ELMS_GF2VEC' returns a new list containing the elements at the position ** given in the list <poss> from the vector <list>. It is the ** responsibility of the caller to ensure that <poss> is dense and contains ** only positive integers. An error is signalled if an element of <poss> is ** larger than the length of <list>.
*/ static Obj FuncELMS_GF2VEC(Obj self, Obj list, Obj poss)
{
Obj elms; // selected sublist, result Int lenList; // length of <list> Int lenPoss; // length of positions Int pos; // position as integer Int inc; // increment in a range Int i; // loop variable
Obj apos;
// get the length of <list>
lenList = LEN_GF2VEC(list);
// general code for arbitrary lists, which are ranges if (!IS_RANGE(poss)) {
// get the length of <positions>
lenPoss = LEN_LIST(poss);
// make the result vector
NEW_GF2VEC(elms, TYPE_LIST_GF2VEC, lenPoss);
// loop over the entries of <positions> and select for (i = 1; i <= lenPoss; i++) {
// get next position
apos = ELM0_LIST(poss, i); if (!apos || !IS_INTOBJ(apos))
ErrorMayQuit("ELMS_GF2VEC: error at position %d in positions " "list, entry must be bound to a small integer",
i, 0);
pos = INT_INTOBJ(apos); if (lenList < pos) {
ErrorMayQuit("List Elements: <list>[%d] must have a value",
pos, 0);
}
// assign the element into <elms> if (ELM_GF2VEC(list, pos) == GF2One) {
BLOCK_ELM_GF2VEC(elms, i) |= MASK_POS_GF2VEC(i);
}
}
}
// special code for ranges else {
// get the length of <positions>, the first elements, and the inc.
lenPoss = GET_LEN_RANGE(poss);
pos = GET_LOW_RANGE(poss);
inc = GET_INC_RANGE(poss);
// check that no <position> is larger than <lenList> if (lenList < pos) {
ErrorMayQuit("List Elements: <list>[%d] must have a value", pos, 0);
} if (lenList < pos + (lenPoss - 1) * inc) {
ErrorMayQuit("List Elements: <list>[%d] must have a value",
pos + (lenPoss - 1) * inc, 0);
}
// make the result vector
NEW_GF2VEC(elms, TYPE_LIST_GF2VEC, lenPoss);
// increment 1 ranges is a block copy if (inc == 1)
CopySection_GF2Vecs(list, elms, pos, 1, lenPoss);
// loop over the entries of <positions> and select else { for (i = 1; i <= lenPoss; i++, pos += inc) { if (ELM_GF2VEC(list, pos) == GF2One) {
BLOCK_ELM_GF2VEC(elms, i) |= MASK_POS_GF2VEC(i);
}
}
}
}
return elms;
}
/**************************************************************************** ** *F FuncASS_GF2VEC( <self>, <list>, <pos>, <elm> ) set an elm of a GF2 vector ** ** 'ASS_GF2VEC' assigns the element <elm> at the position <pos> to the GF2 ** vector <list>. ** ** It is the responsibility of the caller to ensure that <pos> is positive, ** and that <elm> is not 0.
*/
// get the position
UInt p = GetSmallInt(SELF_NAME, pos);
// if <elm> is Z(2) or 0*Z(2) and the position is OK, keep rep if (p <= LEN_GF2VEC(list) + 1) { if (LEN_GF2VEC(list) + 1 == p) { if (DoFilter(IsLockedRepresentationVector, list) == True)
ErrorMayQuit("Assignment forbidden beyond the end of locked " "GF2 vector", 0, 0);
ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(p));
SET_LEN_GF2VEC(list, p);
} if (EQ(GF2One, elm)) {
BLOCK_ELM_GF2VEC(list, p) |= MASK_POS_GF2VEC(p);
} elseif (EQ(GF2Zero, elm)) {
BLOCK_ELM_GF2VEC(list, p) &= ~MASK_POS_GF2VEC(p);
} elseif (IS_FFE(elm) && CHAR_FF(FLD_FFE(elm)) == 2 &&
DEGR_FF(FLD_FFE(elm)) <= 8) {
RewriteGF2Vec(list, SIZE_FF(FLD_FFE(elm)));
ASS_VEC8BIT(list, pos, elm);
} else {
PlainGF2Vec(list);
ASS_LIST(list, p, elm);
}
} else {
PlainGF2Vec(list);
ASS_LIST(list, p, elm);
} return0;
}
/**************************************************************************** ** *F FuncPLAIN_GF2MAT( <self>, <list> ) . . . convert back into ordinary list
*/ static Obj FuncPLAIN_GF2MAT(Obj self, Obj list)
{
PlainGF2Mat(list); return0;
}
/**************************************************************************** ** *F FuncASS_GF2MAT( <self>, <list>, <pos>, <elm> ) set an elm of a GF2 matrix ** ** 'ASS_GF2MAT' assigns the element <elm> at the position <pos> to the GF2 ** matrix <list>. ** ** It is the responsibility of the caller to ensure that <pos> is positive, ** and that <elm> is not 0.
*/ static Obj FuncASS_GF2MAT(Obj self, Obj list, Obj pos, Obj elm)
{ // check that <list> is mutable
RequireMutable("List Assignment", list, "list");
// get the position
UInt p = GetSmallInt(SELF_NAME, pos);
UInt r1 = GetSmallInt(SELF_NAME, row1);
UInt r2 = GetSmallInt(SELF_NAME, row2);
UInt m = LEN_GF2MAT(mat); if (m < r1) {
ErrorMayQuit("row index %d exceeds %d, the number of rows", r1, m);
} if (m < r2) {
ErrorMayQuit("row index %d exceeds %d, the number of rows", r2, m);
}
Obj a = ELM_GF2MAT(mat, r1);
Obj b = ELM_GF2MAT(mat, r2);
UInt n = LEN_GF2VEC(ELM_GF2MAT(mat, 1)); if (n < c1) {
ErrorMayQuit("column index %d exceeds %d, the number of columns", c1, n);
} if (n < c2) {
ErrorMayQuit("column index %d exceeds %d, the number of columns", c2, n);
}
for (UInt i = 1; i <= m; ++i) {
Obj vec = ELM_GF2MAT(mat, i); if (!IS_MUTABLE_OBJ(vec)) {
ErrorMayQuit("row %d is immutable", i, 0);
} if (LEN_GF2VEC(vec) != n) {
ErrorMayQuit("row length mismatch, %d versus %d", n, LEN_GF2VEC(vec));
}
Obj a = ELM_GF2VEC(vec, c1);
Obj b = ELM_GF2VEC(vec, c2); if (a != b) { // one entry is 1, the other is 0; so to switch them, // we can simply flip each individually
BLOCK_ELM_GF2VEC(vec, c1) ^= MASK_POS_GF2VEC(c1);
BLOCK_ELM_GF2VEC(vec, c2) ^= MASK_POS_GF2VEC(c2);
}
}
return0;
}
/**************************************************************************** ** *F FuncUNB_GF2VEC( <self>, <list>, <pos> ) . unbind position of a GF2 vector ** ** 'UNB_GF2VEC' unbind the element at the position <pos> in a GF2 vector ** <list>. ** ** It is the responsibility of the caller to ensure that <pos> is positive.
*/ static Obj FuncUNB_GF2VEC(Obj self, Obj list, Obj pos)
{ // check that <list> is mutable
RequireMutable("List Unbind", list, "vector");
if (DoFilter(IsLockedRepresentationVector, list) == True) {
ErrorMayQuit("Unbind forbidden on locked GF2 vector", 0, 0);
}
// get the position
UInt p = GetSmallInt(SELF_NAME, pos);
// if we unbind the last position keep the representation if (LEN_GF2VEC(list) < p) {
;
} elseif (LEN_GF2VEC(list) == p) {
ResizeWordSizedBag(list, SIZE_PLEN_GF2VEC(p - 1));
SET_LEN_GF2VEC(list, p - 1);
} else {
PlainGF2Vec(list);
UNB_LIST(list, p);
} return0;
}
/**************************************************************************** ** *F FuncUNB_GF2MAT( <self>, <list>, <pos> ) . unbind position of a GF2 matrix ** ** 'UNB_GF2VEC' unbind the element at the position <pos> in a GF2 matrix ** <list>. ** ** It is the responsibility of the caller to ensure that <pos> is positive.
*/ static Obj FuncUNB_GF2MAT(Obj self, Obj list, Obj pos)
{ // check that <list> is mutable
RequireMutable("List Unbind", list, "matrix");
// get the position
UInt p = GetSmallInt(SELF_NAME, pos);
// if we unbind the last position keep the representation if (p > 1 && LEN_GF2MAT(list) < p) {
;
} elseif (LEN_GF2MAT(list) == p) {
ResizeBag(list, SIZE_PLEN_GF2MAT(p - 1));
SET_LEN_GF2MAT(list, p - 1);
} else {
PlainGF2Mat(list);
UNB_LIST(list, p);
} return0;
}
/**************************************************************************** ** *F FuncZERO_GF2VEC( <self>, <mat> ) . . . . . . . . . . . . zero GF2 vector ** ** return the zero vector over GF2 of the same length as <mat>.
*/ static Obj FuncZERO_GF2VEC(Obj self, Obj mat)
{
Obj zero;
UInt len;
// create a new GF2 vector
len = LEN_GF2VEC(mat);
NEW_GF2VEC(zero, TYPE_LIST_GF2VEC, len); return zero;
}
/**************************************************************************** ** *F FuncZERO_GF2VEC_2( <self>, <len>) . . . . . . . . . zero GF2 vector ** ** return the zero vector over GF2 of length <len>
*/ static Obj FuncZERO_GF2VEC_2(Obj self, Obj len)
{
Obj zero;
RequireNonnegativeSmallInt(SELF_NAME, len);
NEW_GF2VEC(zero, TYPE_LIST_GF2VEC, INT_INTOBJ(len)); return zero;
}
/**************************************************************************** ** *F FuncINV_GF2MAT_MUTABLE( <self>, <mat> ) . .. . . . . inverse GF2 matrix ** ** This might now be redundant, a library method using ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE ** might do just as good a job
*/ static Obj FuncINV_GF2MAT_MUTABLE(Obj self, Obj mat)
{
UInt len;
len = LEN_GF2MAT(mat); if (len != 0) { if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
ErrorMayQuit("<matrix> must be square", 0, 0);
}
} return InverseGF2Mat(mat, 2);
}
/**************************************************************************** ** *F FuncINV_GF2MAT_SAME_MUTABILITY( <self>, <mat> ) . ... inverse GF2 matrix ** ** This might now be redundant, a library method using ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE ** might do just as good a job
*/ static Obj FuncINV_GF2MAT_SAME_MUTABILITY(Obj self, Obj mat)
{
UInt len;
len = LEN_GF2MAT(mat); if (len != 0) { if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
ErrorMayQuit("<matrix> must be square", 0, 0);
}
} return InverseGF2Mat(mat, 1);
}
/**************************************************************************** ** *F FuncINV_GF2MAT_IMMUTABLE( <self>, <mat> ) . .. . . . inverse GF2 matrix ** ** This might now be redundant, a library method using ** INVERSE_PLIST_GF2VECS_DESTRUCTIVE ** might do just as good a job
*/ static Obj FuncINV_GF2MAT_IMMUTABLE(Obj self, Obj mat)
{
UInt len;
len = LEN_GF2MAT(mat); if (len != 0) { if (len != LEN_GF2VEC(ELM_GF2MAT(mat, 1))) {
ErrorMayQuit("<matrix> must be square", 0, 0);
}
} return InverseGF2Mat(mat, 0);
}
/**************************************************************************** ** *F FuncINV_PLIST_GF2VECS_DESTRUCTIVE( <self>, <list> ) ** ** invert possible GF2 matrix
*/ static Obj FuncINV_PLIST_GF2VECS_DESTRUCTIVE(Obj self, Obj list)
{
UInt len, i;
Obj row;
len = LEN_PLIST(list); for (i = 1; i <= len; i++) {
row = ELM_PLIST(list, i); if (!IS_GF2VEC_REP(row) || LEN_GF2VEC(row) != len) return TRY_NEXT_METHOD;
} if (len == 0) { return CopyObj(list, 1);
} if (len == 1) {
row = ELM_PLIST(list, 1); if (CONST_BLOCKS_GF2VEC(row)[0] & 1) { return CopyObj(list, 1);
} else return Fail;
} return InversePlistGF2VecsDesstructive(list);
}
/**************************************************************************** ** *F FuncSUM_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) . . . . . sum of GF2 vectors ** ** 'FuncSUM_GF2VEC_GF2VEC' returns the sum of the two gf2-vectors <vl> and ** <vr>. The sum is a new gf2-vector, where each element is the sum of the ** corresponding entries of <vl> and <vr>. The major work is done in the ** routine 'AddPartialGF2VecGF2Vec' which is called from ** 'FuncSUM_GF2VEC_GF2VEC'. ** ** 'FuncSUM_GF2VEC_GF2VEC' is an improved version of 'SumListList', which ** does not call 'SUM' but uses bit operations instead.
*/ static Obj FuncSUM_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
{
Obj sum; // sum, result
UInt ll, lr;
ll = LEN_GF2VEC(vl);
lr = LEN_GF2VEC(vr);
if (ll < lr) {
sum = ShallowCopyVecGF2(vr);
AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sum), CONST_BLOCKS_GF2VEC(vl), ll);
} else {
sum = ShallowCopyVecGF2(vl);
AddGF2VecToGF2Vec(BLOCKS_GF2VEC(sum), CONST_BLOCKS_GF2VEC(vr), lr);
}
if (!IS_MUTABLE_OBJ(vl) && !IS_MUTABLE_OBJ(vr))
SET_TYPE_POSOBJ(sum, TYPE_LIST_GF2VEC_IMM);
/**************************************************************************** ** *F FuncPROD_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) . . product of GF2 vectors ** ** 'FuncPROD_GF2VEC_GF2VEC' returns the product of the two GF2 vectors <vl> ** and <vr>. The product is either `GF2One' or `GF2Zero'.
*/ static Obj FuncPROD_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
{ return ProdGF2VecGF2Vec(vl, vr);
}
/**************************************************************************** ** *F FuncPROD_GF2VEC_GF2MAT( <self>, <vl>, <vr> ) product of GF2 vector/matrix ** ** 'FuncPROD_GF2VEC_GF2MAT' returns the product of the GF2 vectors <vl> and ** the GF2 matrix <vr>. ** ** The product is again a GF2 vector. It is the responsibility of the ** caller to ensure that <vl> is a GF2 vector, <vr> a GF2 matrix.
*/ static Obj FuncPROD_GF2VEC_GF2MAT(Obj self, Obj vl, Obj vr)
{ return ProdGF2VecGF2Mat(vl, vr);
}
/**************************************************************************** ** *F FuncPROD_GF2MAT_GF2MAT( <self>, <ml>, <mr> ) product of GF2 vector/matrix ** ** 'FuncPROD_GF2MAT_GF2MAT' returns the product of the GF2 matricess <ml> ** and <mr>. ** ** The product is again a GF2 matrix. It is the responsibility of the ** caller to ensure that <ml> and <mr> are GF2 matrices
*/ static Obj FuncPROD_GF2MAT_GF2MAT(Obj self, Obj ml, Obj mr)
{
UInt lenl = LEN_GF2MAT(ml);
UInt lenm; if (lenl >= 128) {
lenm = LEN_GF2VEC(ELM_GF2MAT(ml, 1)); if (lenm >= 128 && lenm == LEN_GF2MAT(mr) &&
LEN_GF2VEC(ELM_GF2MAT(mr, 1)) >= 128) { return ProdGF2MatGF2MatAdvanced(ml, mr, 8, (lenm + 255) / 256);
}
} return ProdGF2MatGF2MatSimple(ml, mr);
}
/**************************************************************************** ** *F FuncPROD_GF2MAT_GF2MAT_SIMPLE( <self>, <ml>, <mr> ) ** ** 'FuncPROD_GF2MAT_GF2MAT' returns the product of the GF2 matricess <ml> ** and <mr>. It never uses grease or blocking. ** ** The product is again a GF2 matrix. It is the responsibility of the ** caller to ensure that <ml> and <mr> are GF2 matrices
*/ static Obj FuncPROD_GF2MAT_GF2MAT_SIMPLE(Obj self, Obj ml, Obj mr)
{ return ProdGF2MatGF2MatSimple(ml, mr);
}
/**************************************************************************** ** *F FuncPROD_GF2MAT_GF2MAT_ADVANCED( <self>, <ml>, <mr>, <greaselevel>, ** <blocksize> ) ** ** 'FuncPROD_GF2MAT_GF2MAT_ADVANCED' returns the product of the GF2 matrices ** <ml> and <mr> using grease level <greaselevel> and block size <blocksize> ** ** The product is again a GF2 matrix. It is the responsibility of the ** caller to ensure that <ml> and <mr> are GF2 matrices
*/ static Obj FuncPROD_GF2MAT_GF2MAT_ADVANCED(
Obj self, Obj ml, Obj mr, Obj greaselevel, Obj blocksize)
{ return ProdGF2MatGF2MatAdvanced(ml, mr, INT_INTOBJ(greaselevel),
INT_INTOBJ(blocksize));
}
/**************************************************************************** ** *F FuncPROD_GF2MAT_GF2VEC( <self>, <vl>, <vr> ) product of GF2 matrix/vector ** ** 'FuncPROD_GF2VEC_GF2MAT' returns the product of the GF2 matrix <vl> and ** the GF2 vector <vr>. ** ** The product is again a GF2 vector. It is the responsibility of the ** caller to ensure that <vr> is a GF2 vector, <vl> a GF2 matrix.
*/ static Obj FuncPROD_GF2MAT_GF2VEC(Obj self, Obj vl, Obj vr)
{ return ProdGF2MatGF2Vec(vl, vr);
}
/**************************************************************************** ** *F FuncADDCOEFFS_GF2VEC_GF2VEC_MULT( <self>, <vl>, <vr>, <mul> ) GF2 vectors
*/ static Obj FuncADDCOEFFS_GF2VEC_GF2VEC_MULT(Obj self, Obj vl, Obj vr, Obj mul)
{ // do nothing if <mul> is zero if (EQ(mul, GF2Zero)) { return INTOBJ_INT(RightMostOneGF2Vec(vl));
}
// add if <mul> is one if (EQ(mul, GF2One)) { return AddCoeffsGF2VecGF2Vec(vl, vr);
}
// number of insignificant bit positions in last word
off = BIPEB - ((len - 1) % BIPEB + 1);
// mask out the last bits
*ptr &= ALL_BITS_UINT >> off;
// find last non-trivial block while (0 < nbb && !*ptr) {
nbb--;
ptr--;
} // did the block number change? if (nbb < onbb) {
len = nbb * BIPEB;
}
// find position inside this block // we are guaranteed not to cross a block boundary ! while (0 < len && !(*ptr & MASK_POS_GF2VEC(len))) {
len--;
}
ResizeWordSizedBag(vec, SIZE_PLEN_GF2VEC(len));
SET_LEN_GF2VEC(vec, len); return INTOBJ_INT(len);
}
/**************************************************************************** ** *F FuncPOSITION_NONZERO_GF2VEC( <self>, <vec>, <zero>) ..find first non-zero ** ** The pointless zero argument is because this is a method for PositionNot ** It is *not* used in the code and can be replaced by a dummy argument.
*/
// get length and number of blocks
len = LEN_GF2VEC(vec); if (len == 0) { return1;
}
nbb = from / BIPEB;
pos = from % BIPEB;
ptr = CONST_BLOCKS_GF2VEC(vec) + nbb; if (pos) // partial block to check
{
pos = from + 1; while ((pos - 1) % BIPEB && pos <= len) { if ((*ptr) & MASK_POS_GF2VEC(pos)) return (pos);
pos++;
} if (pos > len) return len + 1;
nbb++;
ptr++;
} // find first non-trivial block
nb = NUMBER_BLOCKS_GF2VEC(vec); while (nbb < nb && !*ptr) {
nbb++;
ptr++;
}
// find position inside this block
pos = nbb * BIPEB + 1; while (pos <= len && !(*ptr & MASK_POS_GF2VEC(pos))) {
pos++;
} // as the code is intended to run over, trailing 1's are innocent if (pos <= len) return pos; else return len + 1;
}
static Obj FuncCOPY_SECTION_GF2VECS(
Obj self, Obj src, Obj dest, Obj from, Obj to, Obj howmany)
{ Int ifrom = GetPositiveSmallInt(SELF_NAME, from); Int ito = GetPositiveSmallInt(SELF_NAME, to); Int ihowmany = GetSmallInt(SELF_NAME, howmany);
if (!IS_GF2VEC_REP(src)) {
RequireArgument(SELF_NAME, src, "must be a GF2 vector");
} if (!IS_GF2VEC_REP(dest)) {
RequireArgument(SELF_NAME, dest, "must be a GF2 vector");
}
if (TNUM_OBJ(mat) != T_POSOBJ) {
ErrorMayQuit("TRANSPOSED_GF2MAT: Need compressed matrix over GF(2)", 0, 0);
} // type for mat
typ = TYPE_LIST_GF2MAT;
// we assume here that there is a first row
r1 = ELM_GF2MAT(mat, 1);
l = LEN_GF2MAT(mat);
w = LEN_GF2VEC(r1);
nrb = NUMBER_BLOCKS_GF2VEC(r1);
tra = NewBag(T_POSOBJ, SIZE_PLEN_GF2MAT(w));
SET_TYPE_POSOBJ(tra, typ);
// type for rows
typ = TYPE_LIST_GF2VEC_LOCKED;
SET_LEN_GF2MAT(tra, w); // create new matrix for (i = 1; i <= w; i++) {
NEW_GF2VEC(row, typ, l);
SET_ELM_GF2MAT(tra, i, row);
CHANGED_BAG(tra);
} // set entries // run over BIPEB row chunks of the original matrix for (i = 1; i <= l; i = i + BIPEB) {
imod = (i - 1) / BIPEB; // run through these rows in block chunks for (n = 0; n < nrb; n++) { for (j = 0; j < BIPEB; j++) { if ((i + j) > l) {
vals[j] = 0; // outside matrix
} else { const UInt * ptr =
CONST_BLOCKS_GF2VEC(ELM_GF2MAT(mat, i + j)) + n;
vals[j] = *ptr;
}
} // write transposed values in new matrix
mask = 1;
nstart = n * BIPEB + 1; for (j = 0; j < BIPEB; j++) { // bit number = Row in transpose if ((nstart + j) <= w) { // still within matrix
val = 0;
bit = 1; for (k = 0; k < BIPEB; k++) { if (mask == (vals[k] & mask)) {
val |= bit; // set bit
}
bit = bit << 1;
} // set entry
UInt * ptr =
BLOCKS_GF2VEC(ELM_GF2MAT(tra, nstart + j)) + imod;
*ptr = val; // next bit
mask = mask << 1;
}
}
}
} return tra;
}
/**************************************************************************** ** *F FuncNUMBER_GF2VEC( <self>, <vect> ) **
*/ static Obj FuncNUMBER_GF2VEC(Obj self, Obj vec)
{
UInt len, nd, i;
UInt head, a;
UInt off, off2; // 0 based
Obj zahl; // the long number
UInt * num2;
mp_limb_t * vp;
len = LEN_GF2VEC(vec); if (len == 0) return INTOBJ_INT(1);
num2 = BLOCKS_GF2VEC(vec) + (len - 1) / BIPEB;
off = (len - 1) % BIPEB + 1; // number of significant bits in last word
off2 = BIPEB - off; // number of insignificant bits in last word
// mask out the last bits
*num2 &= ALL_BITS_UINT >> off2;
if (len <= NR_SMALL_INT_BITS) // it still fits into a small integer return INTOBJ_INT(revertbits(*num2, len)); else { // we might have to build a long integer
// the number of words (limbs) we need.
nd = ((len - 1) / GMP_LIMB_BITS) + 1;
vp = (mp_limb_t *)ADDR_OBJ(zahl); // the place we write to
i = 1;
if (off != BIPEB) {
head = revertbits(*num, off); // the last 'off' bits, reverted while (i < nd) { // next word
num--;
*vp = head; // the bits left from last word
a = revertbits(*num, BIPEB); // the full word reverted
head = a >> off2; // next head: trailing `off' bits
a = a << off; // the rest of the word
*vp |= a;
vp++;
i++;
}
*vp = head; // last head bits
vp++;
} else { while (i <= nd) {
*vp = revertbits(*num--, BIPEB);
vp++;
i++;
}
}
/**************************************************************************** ** *F DistGF2Vecs( <ptL>, <ptR>, <len> ) ** ** computes the GF2-vector distance of two blocks in memory, pointed to by ** ptL and ptR for a GF(2) vector of <len> entries. **
*/ static UInt DistGF2Vecs(const UInt * ptL, const UInt * ptR, UInt len)
{
UInt sum, m; const UInt * end; // end marker
// TODO: this function will not work if the vectors have more than 2^28 // entries
end = ptL + ((len + BIPEB - 1) / BIPEB);
sum = 0; // loop over the entries while (ptL < end) {
m = *ptL++ ^ *ptR++; // xor of bits, nr bits therein is difference
sum += COUNT_TRUES_BLOCK(m);
} return sum;
}
/**************************************************************************** ** *F FuncDIST_GF2VEC_GF2VEC( <self>, <vl>, <vr> ) ** ** 'FuncDIST_GF2VEC_GF2VEC' returns the number of position in which two ** gf2-vectors <vl> and <vr> differ.
*/ static Obj FuncDIST_GF2VEC_GF2VEC(Obj self, Obj vl, Obj vr)
{
UInt len; // length of the list
UInt off; // bit offset at the end to clean out
UInt * ptL; // bit field of <vl>
UInt * ptR; // bit field of <vr>
UInt * end; // pointer used to zero out end bit // get and check the length
len = LEN_GF2VEC(vl);
if (len != LEN_GF2VEC(vr)) {
ErrorMayQuit("DIST_GF2VEC_GF2VEC: vectors must have the same length", 0, 0);
}
// calculate the offsets
ptL = BLOCKS_GF2VEC(vl);
ptR = BLOCKS_GF2VEC(vr);
// mask out the last bits
off = (len - 1) % BIPEB + 1; // number of significant bits in last word
off = BIPEB - off; // number of insignificant bits in last word
end = ptL + ((len - 1) / BIPEB);
*end &= ALL_BITS_UINT >> off;
end = ptR + ((len - 1) / BIPEB);
*end &= ALL_BITS_UINT >> off;
return INTOBJ_INT(DistGF2Vecs(ptL, ptR, len));
}
staticvoid DistVecClosVec(
Obj veclis, // pointers to matrix vectors and their multiples
Obj ovec, // vector we compute distance to
Obj d, // distances list
Obj osum, // position of the sum vector
UInt pos, // recursion depth
UInt l, // length of basis
UInt len) // length of the involved vectors
{
UInt i;
UInt di;
Obj cnt;
Obj vp; const UInt * vec;
Obj one;
Obj tmp;
vec = CONST_BLOCKS_GF2VEC(ovec);
vp = ELM_PLIST(veclis, pos);
one = INTOBJ_INT(1);
for (i = 0; i <= 1; i++) { if (pos < l) {
DistVecClosVec(veclis, ovec, d, osum, pos + 1, l, len);
} else {
di = DistGF2Vecs(CONST_BLOCKS_GF2VEC(osum), vec, len);
cnt = ELM_PLIST(d, di + 1); if (IS_INTOBJ(cnt) && SUM_INTOBJS(tmp, cnt, one)) {
cnt = tmp;
SET_ELM_PLIST(d, di + 1, cnt);
} else {
cnt = SumInt(cnt, one);
vec = CONST_BLOCKS_GF2VEC(ovec);
SET_ELM_PLIST(d, di + 1, cnt);
CHANGED_BAG(d);
}
}
AddGF2VecToGF2Vec(BLOCKS_GF2VEC(osum),
CONST_BLOCKS_GF2VEC(ELM_PLIST(vp, i + 1)), len);
}
}
static Obj FuncDIST_VEC_CLOS_VEC(
Obj self,
Obj veclis, // pointers to matrix vectors and their multiples
Obj vec, // vector we compute distance to
Obj d) // distances list
{
Obj sum; // sum vector
UInt len;
len = LEN_GF2VEC(vec);
// get space for sum vector
NEW_GF2VEC(sum, TYPE_LIST_GF2VEC, len);
// do the recursive work
DistVecClosVec(veclis, vec, d, sum, 1, LEN_PLIST(veclis), len);
return (Obj)0;
}
static UInt
AClosVec(Obj veclis, // pointers to matrix vectors and their multiples
Obj ovec, // vector we compute distance to
Obj osum, // position of the sum vector
UInt pos, // recursion depth
UInt l, // length of basis
UInt len, // length of the involved vectors
UInt cnt, // numbr of vectors used
UInt stop, // stop value
UInt bd, // best distance so far
Obj obv, // best vector so far
Obj coords, // coefficients to get current vector
Obj bcoords // coefficients to get best vector
)
{
UInt di;
Obj vp;
UInt * sum;
UInt * bv; const UInt * vec; const UInt * end; const UInt * w;
// maybe we don't add this basis vector -- if this leaves us enough // possibilitiies if (pos + cnt < l) {
bd = AClosVec(veclis, ovec, osum, pos + 1, l, len, cnt, stop, bd, obv,
coords, bcoords); if (bd <= stop) { return bd;
}
}
// Otherwise we do
vec = CONST_BLOCKS_GF2VEC(ovec);
sum = BLOCKS_GF2VEC(osum);
vp = ELM_PLIST(veclis, pos);
w = CONST_BLOCKS_GF2VEC(ELM_PLIST(vp, 1));
AddGF2VecToGF2Vec(sum, w, len);
if (coords != (Obj)0) {
SET_ELM_PLIST(coords, pos, INTOBJ_INT(1));
}
if (cnt == 0) // this is a candidate
{
di = DistGF2Vecs(sum, vec, len); if (di < bd) {
// store new result
bd = di;
bv = BLOCKS_GF2VEC(obv);
end = bv + ((len + BIPEB - 1) / BIPEB); while (bv < end)
*bv++ = *sum++;
sum = BLOCKS_GF2VEC(osum); if (coords != (Obj)0) {
UInt i; for (i = 1; i <= l; i++) {
Obj x;
x = ELM_PLIST(coords, i);
SET_ELM_PLIST(bcoords, i, x);
}
}
}
} else// need to add in some more
{
bd = AClosVec(veclis, ovec, osum, pos + 1, l, len, cnt - 1, stop, bd,
obv, coords, bcoords); if (bd <= stop) { return bd;
}
}
static Obj FuncA_CLOS_VEC(
Obj self,
Obj veclis, // pointers to matrix vectors and their multiples
Obj vec, // vector we compute distance to
Obj cnt, // distances list
Obj stop) // distances list
{
Obj sum; // sum vector
Obj best; // best vector
UInt len;
// get space for sum vector and zero out
NEW_GF2VEC(sum, TYPE_LIST_GF2VEC, len);
NEW_GF2VEC(best, TYPE_LIST_GF2VEC, len);
// do the recursive work
AClosVec(veclis, vec, sum, 1, LEN_PLIST(veclis), len, INT_INTOBJ(cnt),
INT_INTOBJ(stop), len + 1, // maximal value +1
best, (Obj)0, (Obj)0);
return best;
}
static Obj FuncA_CLOS_VEC_COORDS(
Obj self,
Obj veclis, // pointers to matrix vectors and their multiples
Obj vec, // vector we compute distance to
Obj cnt, // distances list
Obj stop) // distances list
{
Obj sum; // sum vector
Obj best; // best vector
Obj coords; // coefficients of mat to get current
Obj bcoords; // coefficients of mat to get best
Obj res; // length 2 plist for results
UInt len, len2, i;
for (i = 1; i <= len2; i++) {
SET_ELM_PLIST(coords, i, INTOBJ_INT(0));
SET_ELM_PLIST(bcoords, i, INTOBJ_INT(0));
}
// do the recursive work
AClosVec(veclis, vec, sum, 1, len2, len, INT_INTOBJ(cnt),
INT_INTOBJ(stop), len + 1, // maximal value +1
best, coords, bcoords);
/**************************************************************************** ** *F FuncCOSET_LEADERS_INNER_GF2(<self>,<veclis>,<weight>,<tofind>,<leaders>) ** ** Search for new coset leaders of weight <weight>
*/
// We know that the length of w does not exceed BIPEB -4 here // (or there would not be room in a PLIST for all the coset leaders). // We use this to do a lot of GF2 vector operations for w "in-place" // // Even more in this direction could be done, but this no longer // the rate-determining step for any feasible application
if (weight == 1) { for (i = pos; i <= len; i++) {
u0 = CONST_BLOCKS_GF2VEC(ELM_PLIST(ELM_PLIST(veclis, i), 1))[0];
BLOCKS_GF2VEC(w)[0] ^= u0;
BLOCK_ELM_GF2VEC(v, i) |= MASK_POS_GF2VEC(i);
staticvoid ShiftRightGF2Vec(Obj vec, UInt amount)
{
UInt len;
UInt *ptr1, *ptr2, *ptr0;
UInt i;
UInt block;
UInt off; if (amount == 0) return;
len = LEN_GF2VEC(vec);
ResizeGF2Vec(vec, len + amount); if (amount % BIPEB == 0) { // move the blocks
ptr1 = BLOCKS_GF2VEC(vec) + (len - 1 + amount) / BIPEB;
ptr2 = ptr1 - amount / BIPEB; for (i = 0; i < (len + BIPEB - 1) / BIPEB; i++)
*ptr1-- = *ptr2--;
// and fill with zeroes
ptr2 = BLOCKS_GF2VEC(vec); while (ptr1 >= ptr2)
*ptr1-- = 0;
} else {
ptr1 = BLOCKS_GF2VEC(vec) + (len - 1 + amount) / BIPEB;
ptr2 = ptr1 - amount / BIPEB; // this can sometimes be the block // AFTER the old last block, but this // must be OK
off = amount % BIPEB;
ptr0 = BLOCKS_GF2VEC(vec); while (1) {
block = (*ptr2--) << off; if (ptr2 < ptr0) break;
block |= (*ptr2) >> (BIPEB - off);
*ptr1-- = block;
}
*ptr1-- = block; while (ptr1 >= ptr0)
*ptr1-- = 0;
}
}
RequireSmallInt(SELF_NAME, len1);
RequireSmallInt(SELF_NAME, len2);
len2a = INT_INTOBJ(len2); if (len2a > LEN_GF2VEC(vec2))
ErrorMayQuit("PROD_COEFFS_GF2VEC: <len2> must not be more than the " "actual\nlength of the vector", 0, 0);
len1a = INT_INTOBJ(len1); if (len1a > LEN_GF2VEC(vec1))
ErrorMayQuit("PROD_COEFFS_GF2VEC: <len1> must be not more than the " "actual\nlength of the vector", 0, 0);
prod = ProductCoeffsGF2Vec(vec1, len1a, vec2, len2a);
last = RightMostOneGF2Vec(prod); if (last < LEN_GF2VEC(prod))
ResizeGF2Vec(prod, last); return prod;
}
/**************************************************************************** ** *F FuncSEMIECHELON_LIST_GF2VECS( <self>, <mat> ) ** ** Method for SemiEchelonMat for plain lists of GF2 vectors ** ** Method selection can guarantee us a plain list of characteristic 2 ** vectors
*/
static Obj FuncSEMIECHELON_LIST_GF2VECS(Obj self, Obj mat)
{
UInt i, len;
UInt width;
Obj row;
len = LEN_PLIST(mat); if (!len) return TRY_NEXT_METHOD;
row = ELM_PLIST(mat, 1); if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row)) return TRY_NEXT_METHOD;
width = LEN_GF2VEC(row); if (width == 0) return TRY_NEXT_METHOD; for (i = 2; i <= len; i++) {
row = ELM_PLIST(mat, i); if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
LEN_GF2VEC(row) != width) { return TRY_NEXT_METHOD;
}
} return SemiEchelonListGF2Vecs(mat, 0);
}
/**************************************************************************** ** *F FuncSEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS( <self>, <mat> ) ** ** Method for SemiEchelonMatTransformations for plain lists of GF2 vectors ** ** Method selection can guarantee us a plain list of characteristic 2 ** vectors
*/
static Obj FuncSEMIECHELON_LIST_GF2VECS_TRANSFORMATIONS(Obj self, Obj mat)
{
UInt i, len;
UInt width;
Obj row;
len = LEN_PLIST(mat); if (!len) return TRY_NEXT_METHOD;
row = ELM_PLIST(mat, 1); if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row)) return TRY_NEXT_METHOD;
width = LEN_GF2VEC(row); if (width == 0) return TRY_NEXT_METHOD; for (i = 2; i <= len; i++) {
row = ELM_PLIST(mat, i); if (!IS_MUTABLE_OBJ(row) || !IS_GF2VEC_REP(row) ||
LEN_GF2VEC(row) != width) { return TRY_NEXT_METHOD;
}
} return SemiEchelonListGF2Vecs(mat, 1);
}
if (LEN_GF2MAT(mat) < r) {
ErrorMayQuit("row index %d exceeds %d, the number of rows", r,
LEN_GF2MAT(mat));
}
Obj vec = ELM_GF2MAT(mat, r); if (!IS_MUTABLE_OBJ(vec)) {
ErrorMayQuit("row %d is immutable", r, 0);
}
if (LEN_GF2VEC(vec) < c) {
ErrorMayQuit("column index %d exceeds %d, the number of columns", c,
LEN_GF2VEC(vec));
}
if (EQ(GF2One, elm)) {
BLOCK_ELM_GF2VEC(vec, c) |= MASK_POS_GF2VEC(c);
} elseif (EQ(GF2Zero, elm)) {
BLOCK_ELM_GF2VEC(vec, c) &= ~MASK_POS_GF2VEC(c);
} else {
RequireArgumentEx(SELF_NAME, elm, 0, "assigned element must be a GF(2) element");
}
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.116Bemerkung:
(vorverarbeitet am 2026-06-06)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Angebot
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
