/**************************************************************************** ** ** 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
*/
/**************************************************************************** ** ** *H There is a representations of GFQ vectors with entries packed into ** bytes, called IsVec8BitRep, which inherits from IsDataObjectRep ** The 1st 4 bytes stores the actual vector length (in field elements) ** as a C integer. The 2nd component stores the field size as a C integer ** The data bytes begin at the 3rd component. ** ** In addition, this file defines format and access for the fieldinfo ** objects which contain the meat-axe tables for the arithmetics. ** ** There is a special representation for matrices, all of whose rows ** are immutable packed GFQ vectors over the same q, which is a positional ** representation Is8BitMatrixRep. Some special methods for such matrices ** are included here. **
*/
/**************************************************************************** ** *V FieldInfo8Bit . . . . . . . . . . .plain list (length 256) of field info ** ** This list caches the field info used for the fast arithmetic
*/
static Obj TypeMat8Bit(UInt q, UInt mut)
{
UInt col = mut ? 1 : 2;
Obj type; #ifdef HPCGAP
type = ELM0_LIST(ELM0_LIST(TYPES_MAT8BIT, col), q); #else
type = ELM_PLIST(ELM_PLIST(TYPES_MAT8BIT, col), q); #endif if (type == 0) return CALL_2ARGS(TYPE_MAT8BIT, INTOBJ_INT(q), mut ? True : False); else return type;
}
/**************************************************************************** ** *V TYPE_FIELDINFO_8BIT ** ** A type of data object with essentially no GAP visible semantics at all **
*/
/**************************************************************************** ** *V GetFieldInfo( <q> ) . .make or recover the meataxe table for a field ** always call this, as the tables are lost by ** save/restore. It's very cheap if the table already ** exists **
*/
staticvoid MakeFieldInfo8Bit(UInt q)
{
FF gfq; // the field
UInt p; // characteristic
UInt d; // degree
UInt i, j, k, l; // loop variables
UInt e; // number of elements per byte
UInt pows[7]; // table of powers of q for packing and unpacking bytes
Obj info; // The table being constructed
FFV mult; // multiplier for scalar product
FFV prod; // used in scalar product
UInt val; // used to build up some answers
UInt val0;
UInt elt, el1, el2; // used to build up some answers const FFV * succ;
p = (UInt)PbyQ[q];
d = (UInt)DbyQ[q];
gfq = FiniteField(p, d);
e = 0; for (i = 1; i <= 256; i *= q)
pows[e++] = i;
pows[e] = i; // simplifies things to have one more
e--;
GAP_ASSERT(e <= 5);
info = NewWordSizedBag(T_DATOBJ, sizeof(struct FieldInfo8Bit));
SetTypeDatObj(info, TYPE_FIELDINFO_8BIT);
succ = SUCC_FF(gfq);
// from here to the end, no garbage collections should happen
FieldInfo8BitPtr fi = FIELDINFO_8BIT(info);
fi->q = q;
fi->p = p;
fi->d = d;
fi->e = e;
// conversion tables FFV to/from our numbering // we assume that 0 and 1 are always the zero and one // of the field. In char 2, we assume that xor corresponds // to addition, otherwise, the order doesn't matter
UInt1 * convtab = fi->FELT_FFE; if (p != 2) for (i = 0; i < q; i++)
convtab[i] = (UInt1)i; else for (i = 0; i < q; i++)
convtab[i] = Char2Lookup[d][i];
// simply invert the permutation to get the other one for (i = 0; i < q; i++) {
j = convtab[i];
fi->FFE_FELT[j] = NEW_FFE(gfq, i);
}
// Now we need to store the position in Elements(GF(q)) of each field // element for the sake of NumberFFVector // // The rules for < between finite field elements make this a bit // complex for non-prime fields
// deal with zero and one
fi->GAPSEQ[0] = INTOBJ_INT(0);
fi->GAPSEQ[fi->FELT_FFE[1]] = INTOBJ_INT(1);
if (q != 2) { if (d == 1) for (i = 2; i < q; i++)
fi->GAPSEQ[i] = INTOBJ_INT(i); else { // run through subfields, filling in entry for all the new // elements of each field in turn
UInt q1 = 1;
UInt pos = 2; for (i = 1; i <= d; i++) {
q1 *= p; if (d % i == 0) { for (j = 2; j < q1; j++) {
UInt place =
fi->FELT_FFE[1 + (j - 1) * (q - 1) / (q1 - 1)]; if (fi->GAPSEQ[place] == 0) {
fi->GAPSEQ[place] = INTOBJ_INT(pos);
pos++;
}
}
}
}
}
}
// entry setting table SETELT...[(i*e+j)*256 +k] is the result // of overwriting the jth element with i in the byte k for (i = 0; i < q; i++) for (j = 0; j < e; j++) { Int iej_cache = (i * e + j) * 256; for (k = 0; k < 256; k++)
fi->SETELT[iej_cache + k] =
(UInt1)((k / pows[j + 1]) * pows[j + 1] + i * pows[j] +
(k % pows[j]));
}
// entry access GETELT...[i*256+j] recovers the ith entry from the // byte j for (i = 0; i < e; i++) for (j = 0; j < 256; j++)
fi->GETELT[i * 256 + j] = (UInt1)(j / pows[i]) % q;
// scalar * vector multiply SCALAR...[i*256+j] is the scalar // product of the byte j with the felt i for (i = 0; i < q; i++) {
mult = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(info, i)); for (j = 0; j < 256; j++) {
val = 0; for (k = 0; k < e; k++) {
elt = VAL_FFE(
FFE_FELT_FIELDINFO_8BIT(info, fi->GETELT[k * 256 + j]));
prod = PROD_FFV(elt, mult, succ);
val += pows[k] * FELT_FFE_FIELDINFO_8BIT(info)[prod];
}
fi->SCALAR[i * 256 + j] = val;
}
}
// inner product INNER...[i+256*j] is a byte whose LS entry is the // contribution to the inner product of bytes i and j for (i = 0; i < 256; i++) for (j = i; j < 256; j++) {
val = 0; for (k = 0; k < e; k++) {
el1 = VAL_FFE(
FFE_FELT_FIELDINFO_8BIT(info, fi->GETELT[k * 256 + i]));
el2 = VAL_FFE(
FFE_FELT_FIELDINFO_8BIT(info, fi->GETELT[k * 256 + j]));
elt = PROD_FFV(el1, el2, succ);
val = SUM_FFV(val, elt, succ);
}
val = fi->SETELT[256 * e * FELT_FFE_FIELDINFO_8BIT(info)[val]];
fi->INNER[i + 256 * j] = val;
fi->INNER[j + 256 * i] = val;
}
// PMULL and PMULU are the lower and upper bytes of the product // of single-byte polynomials for (i = 0; i < 256; i++) for (j = i; j < 256; j++) {
val0 = 0; for (k = 0; k < e; k++) {
val = 0; for (l = 0; l <= k; l++) {
el1 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[l * 256 + i]));
el2 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[(k - l) * 256 + j]));
elt = PROD_FFV(el1, el2, succ);
val = SUM_FFV(val, elt, succ);
}
val0 += pows[k] * FELT_FFE_FIELDINFO_8BIT(info)[val];
}
fi->PMULL[i + 256 * j] = val0;
fi->PMULL[j + 256 * i] = val0;
// if there is just one entry per byte then we don't need the // upper half if (ELS_BYTE_FIELDINFO_8BIT(info) > 1) {
val0 = 0; for (k = e; k < 2 * e - 1; k++) {
val = 0; for (l = k - e + 1; l < e; l++) {
el1 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[l * 256 + i]));
el2 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[(k - l) * 256 + j]));
elt = PROD_FFV(el1, el2, succ);
val = SUM_FFV(val, elt, succ);
}
val0 += pows[k - e] * FELT_FFE_FIELDINFO_8BIT(info)[val];
}
fi->PMULU[i + 256 * j] = val0;
fi->PMULU[j + 256 * i] = val0;
}
}
// In odd characteristic, we need the addition table // ADD...[i*256+j] is the vector sum of bytes i and j if (p != 2) { for (i = 0; i < 256; i++) for (j = i; j < 256; j++) {
val = 0; for (k = 0; k < e; k++) {
el1 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[k * 256 + i]));
el2 = VAL_FFE(FFE_FELT_FIELDINFO_8BIT(
info, fi->GETELT[k * 256 + j]));
val += pows[k] * FELT_FFE_FIELDINFO_8BIT(
info)[SUM_FFV(el1, el2, succ)];
}
fi->ADD[i + 256 * j] = val;
fi->ADD[j + 256 * i] = val;
}
}
#ifdef HPCGAP
MakeBagReadOnly(info); #endif // remember the result #ifdef HPCGAP
ATOMIC_SET_ELM_PLIST_ONCE(FieldInfo8Bit, q, info); #else
SET_ELM_PLIST(FieldInfo8Bit, q, info); #endif
CHANGED_BAG(FieldInfo8Bit);
}
Obj GetFieldInfo8Bit(UInt q)
{
Obj info;
GAP_ASSERT(2 < q && q <= 256); #ifdef HPCGAP
info = ATOMIC_ELM_PLIST(FieldInfo8Bit, q); if (info == 0) {
MakeFieldInfo8Bit(q);
info = ATOMIC_ELM_PLIST(FieldInfo8Bit, q);
} #else
info = ELM_PLIST(FieldInfo8Bit, q); if (info == 0) {
MakeFieldInfo8Bit(q);
info = ELM_PLIST(FieldInfo8Bit, q);
} #endif return info;
}
/**************************************************************************** ** *F RewriteVec8Bit( <vec>, <q> ) . . . . . . . . . . rewrite <vec> over GF(q) ** ** <vec> should be an 8 bit vector over a smaller field of the same ** characteristic
*/
if (q < q1) {
ErrorMayQuit("Cannot convert a vector compressed over GF(%d) to " "small field GF(%d)",
q1, q);
}
if (((q - 1) % (q1 - 1)) != 0) {
ErrorMayQuit( "Cannot convert a vector compressed over GF(%d) to GF(%d)", q1,
q);
}
if (DoFilter(IsLockedRepresentationVector, vec) == True) {
ErrorMayQuit("Cannot convert a locked vector compressed over " "GF(%d) to GF(%d)",
q1, q);
}
// extract the required info
len = LEN_VEC8BIT(vec);
info = GetFieldInfo8Bit(q);
info1 = GetFieldInfo8Bit(q1);
GAP_ASSERT(P_FIELDINFO_8BIT(info) == P_FIELDINFO_8BIT(info1));
GAP_ASSERT(!(D_FIELDINFO_8BIT(info) % D_FIELDINFO_8BIT(info1)));
els = ELS_BYTE_FIELDINFO_8BIT(info);
els1 = ELS_BYTE_FIELDINFO_8BIT(info1);
if (len == 0) {
SET_FIELD_VEC8BIT(vec, q); return;
}
// enlarge the bag
ResizeWordSizedBag(vec, SIZE_VEC8BIT(len, els));
mult = (q - 1) / (q1 - 1); while (i >= 0) {
val = VAL_FFE(convtab1[gettab1[byte1 + 256 * (i % els1)]]); if (val != 0)
val = 1 + (val - 1) * mult;
byte = settab[byte + 256 * (i % els + els * convtab[val])]; if (0 == i % els) {
*ptr-- = byte;
byte = 0;
} if (0 == i % els1)
byte1 = *--ptr1;
i--;
}
SET_FIELD_VEC8BIT(vec, q);
}
/**************************************************************************** ** *F RewriteGF2Vec( <vec>, <q> ) . . . . . . . . . . rewrite <vec> over GF(q) ** ** <vec> should be a GF2 vector and q a larger power of 2 ** ** This function uses the interface in vecgf2.h
*/
if (DoFilter(IsLockedRepresentationVector, vec) == True) {
ErrorMayQuit("Cannot convert a locked vector compressed over " "GF(2) to GF(%d)",
q, 0);
}
// extract the required info
len = LEN_GF2VEC(vec);
info = GetFieldInfo8Bit(q);
els = ELS_BYTE_FIELDINFO_8BIT(info);
// enlarge the bag
ResizeWordSizedBag(vec, SIZE_VEC8BIT(len, els));
settab = SETELT_FIELDINFO_8BIT(info);
convtab = FELT_FFE_FIELDINFO_8BIT(info);
zero = convtab[0];
one = convtab[1];
ptr1 = CONST_BLOCKS_GF2VEC(vec) + NUMBER_BLOCKS_GF2VEC(vec) - 1;
block = *ptr1;
ptr = BYTES_VEC8BIT(vec) + (len - 1) / els;
byte = 0;
i = len - 1;
while (i >= 0) {
byte = settab[byte +
256 * (i % els + els * ((block & MASK_POS_GF2VEC(i + 1))
? one
: zero))]; if (0 == i % els) {
*ptr-- = byte;
byte = 0;
} if (0 == i % BIPEB)
block = *--ptr1;
i--;
}
SET_FIELD_VEC8BIT(vec, q);
SET_LEN_VEC8BIT(vec, len);
type = TypeVec8Bit(q, mut);
SET_TYPE_POSOBJ(vec, type);
}
/**************************************************************************** ** *F ConvVec8Bit( <list>, <q> ) . . . convert a list into 8bit vector object
*/
staticvoid ConvVec8Bit(Obj list, UInt q)
{ Int len; // logical length of the vector Int i; // loop variable
UInt p; // char
UInt d; // degree
FF f; // field
Obj info; // field info object
UInt elts; // elements per byte const UInt1 * settab; // element setting table const UInt1 * convtab; // FFE -> FELT conversion table
Obj firstthree[3]; // the first three entries may get clobbered my the // early bytes
UInt e; // loop variable
UInt1 byte; // byte under construction
UInt1 * ptr; // place to put byte
Obj elt;
UInt val;
UInt nsize;
Obj type;
if (q > 256)
ErrorQuit("Field size %d is too much for 8 bits", q, 0); if (q == 2)
ErrorQuit("GF2 has its own representation", 0, 0);
// already in the correct representation if (IS_VEC8BIT_REP(list)) {
UInt q1 = FIELD_VEC8BIT(list); if (q1 == q) return; elseif (q1 < q && ((q - 1) % (q1 - 1)) == 0) {
RewriteVec8Bit(list, q); return;
} // remaining case is list is written over too large a field // pass through to the generic code
} elseif (IS_GF2VEC_REP(list)) {
RewriteGF2Vec(list, q); return;
}
len = LEN_LIST(list);
// OK, so now we know which field we want, set up data
info = GetFieldInfo8Bit(q);
p = P_FIELDINFO_8BIT(info);
d = D_FIELDINFO_8BIT(info);
f = FiniteField(p, d);
elts = ELS_BYTE_FIELDINFO_8BIT(info);
// We may need to resize first, as small lists get BIGGER // in this process
nsize = SIZE_VEC8BIT(len, elts); if (nsize > SIZE_OBJ(list))
ResizeWordSizedBag(list, nsize);
// writing the first byte may clobber the third list entry // before we have read it, so we take a copy
firstthree[0] = ELM0_LIST(list, 1);
firstthree[1] = ELM0_LIST(list, 2);
firstthree[2] = ELM0_LIST(list, 3);
// main loop -- e is the element within byte
e = 0;
byte = 0;
ptr = BYTES_VEC8BIT(list); for (i = 1; i <= len; i++) {
elt = (i <= 3) ? firstthree[i - 1] : ELM_LIST(list, i);
GAP_ASSERT(CHAR_FF(FLD_FFE(elt)) == p);
GAP_ASSERT(d % DegreeFFE(elt) == 0);
val = VAL_FFE(elt); if (val != 0 && FLD_FFE(elt) != f) {
val = 1 + (val - 1) * (q - 1) / (SIZE_FF(FLD_FFE(elt)) - 1);
} // Must get these afresh after every list access, just in case this is // a virtual list whose accesses might cause a garbage collection
settab = SETELT_FIELDINFO_8BIT(info);
convtab = FELT_FFE_FIELDINFO_8BIT(info);
byte = settab[(e + elts * convtab[val]) * 256 + byte]; if (++e == elts || i == len) {
*ptr++ = byte;
byte = 0;
e = 0;
}
}
// it can happen that the few bytes after the end of the data are // not zero, because they had data in them in the old version of the list // In most cases this doesn't matter, but in characteristic 2, we must // clear up to the end of the word, so that AddCoeffs behaves correctly. // // SL -- lets do this in all characteristics, it can never hurt
while ((ptr - BYTES_VEC8BIT(list)) % sizeof(UInt))
*ptr++ = 0;
// retype and resize bag if (nsize != SIZE_OBJ(list))
ResizeWordSizedBag(list, nsize);
SET_LEN_VEC8BIT(list, len);
SET_FIELD_VEC8BIT(list, q);
type = TypeVec8Bit(q, IS_MUTABLE_OBJ(list));
SetTypeDatObj(list, type);
RetypeBag(list, T_DATOBJ);
}
static UInt LcmDegree(UInt d, UInt d1)
{
UInt x, y, g;
x = d;
y = d1; while (x != 0 && y != 0) { if (x <= y)
y = y % x; else
x = x % y;
} if (x == 0)
g = y; else
g = x; return (d * d1) / g;
}
/**************************************************************************** ** *F NewVec8Bit( <list>, <q> ) . . . convert a list into 8bit vector object ** ** This is a non-destructive counterpart of ConvVec8Bit
*/
static Obj NewVec8Bit(Obj list, UInt q)
{ Int len; // logical length of the vector Int i; // loop variable
UInt p; // char
UInt d; // degree
FF f; // field
Obj info; // field info object
UInt elts; // elements per byte const UInt1 * settab; // element setting table const UInt1 * convtab; // FFE -> FELT conversion table
UInt e; // loop variable
UInt1 byte; // byte under construction
UInt1 * ptr; // place to put byte
Obj elt;
UInt val;
UInt nsize;
Obj type;
Obj res; // resulting 8bit vector object
if (q > 256)
ErrorQuit("Field size %d is too much for 8 bits", q, 0); if (q == 2)
ErrorQuit("GF2 has its own representation", 0, 0);
// already in the correct representation if (IS_VEC8BIT_REP(list)) {
UInt q1 = FIELD_VEC8BIT(list); if (q1 == q) {
res = CopyVec8Bit(list, 1); if (!IS_MUTABLE_OBJ(list)) // index 0 is for immutable vectors
SetTypeDatObj(res, TypeVec8Bit(q, 0)); return res;
} elseif (q1 < q && ((q - 1) % (q1 - 1)) == 0) { // rewriting to a larger field
res = CopyVec8Bit(list, 1);
RewriteVec8Bit(res, q); // TODO: rework RewriteVec8Bit and avoid calling CopyVec8Bit if (!IS_MUTABLE_OBJ(list))
SetTypeDatObj(res, TypeVec8Bit(q, 0)); return res;
} // remaining case is list is written over too large a field // pass through to the generic code
} elseif (IS_GF2VEC_REP(list)) {
res = ShallowCopyVecGF2(list);
RewriteGF2Vec(res, q); // TODO: rework RewriteGF2Vec and avoid calling ShallowCopyVecGF2 if (!IS_MUTABLE_OBJ(list))
SetTypeDatObj(res, TypeVec8Bit(q, 0)); return res;
}
// OK, so now we know which field we want, set up data
info = GetFieldInfo8Bit(q);
p = P_FIELDINFO_8BIT(info);
d = D_FIELDINFO_8BIT(info);
f = FiniteField(p, d);
// determine the size and create a new bag
len = LEN_LIST(list);
elts = ELS_BYTE_FIELDINFO_8BIT(info);
nsize = SIZE_VEC8BIT(len, elts);
res = NewWordSizedBag(T_DATOBJ, nsize);
// main loop -- e is the element within byte
e = 0;
byte = 0;
ptr = BYTES_VEC8BIT(res); for (i = 1; i <= len; i++) {
elt = ELM_LIST(list, i);
GAP_ASSERT(CHAR_FF(FLD_FFE(elt)) == p);
GAP_ASSERT(d % DegreeFFE(elt) == 0);
val = VAL_FFE(elt); if (val != 0 && FLD_FFE(elt) != f) {
val = 1 + (val - 1) * (q - 1) / (SIZE_FF(FLD_FFE(elt)) - 1);
} // Must get these afresh after every list access, just in case this is // a virtual list whose accesses might cause a garbage collection
settab = SETELT_FIELDINFO_8BIT(info);
convtab = FELT_FFE_FIELDINFO_8BIT(info);
byte = settab[(e + elts * convtab[val]) * 256 + byte]; if (++e == elts || i == len) {
*ptr++ = byte;
byte = 0;
e = 0;
}
}
// retype bag
SET_LEN_VEC8BIT(res, len);
SET_FIELD_VEC8BIT(res, q);
type = TypeVec8Bit(q, IS_MUTABLE_OBJ(list));
SetTypeDatObj(res, type);
return res;
}
/**************************************************************************** ** *F FuncCOPY_VEC8BIT( <self>, <list> ) . . . . . convert into 8bit vector rep ** ** This is a non-destructive counterpart of FuncCOPY_GF2VEC
*/ static Obj FuncCOPY_VEC8BIT(Obj self, Obj list, Obj q)
{
UInt iq = GetPositiveSmallInt(SELF_NAME, q); return NewVec8Bit(list, iq);
}
/**************************************************************************** ** *F PlainVec8Bit( <list> ) . . . convert an 8bit vector into an ordinary list ** ** 'PlainVec8Bit' converts the vector <list> to a plain list.
*/
// resize the list and retype it, in this order if (True == DoFilter(IsLockedRepresentationVector, list)) {
ErrorMayQuit( "Attempt to convert locked compressed vector to plain list", 0,
0);
}
len = LEN_VEC8BIT(list);
q = FIELD_VEC8BIT(list);
info = GetFieldInfo8Bit(q);
elts = ELS_BYTE_FIELDINFO_8BIT(info);
if (len != 0) {
gettab = GETELT_FIELDINFO_8BIT(info); // keep the first two entries // because setting the third destroys them
first = FFE_FELT_FIELDINFO_8BIT(info,
gettab[CONST_BYTES_VEC8BIT(list)[0]]); if (len > 1)
second = FFE_FELT_FIELDINFO_8BIT(
info, gettab[256 * (1 % elts) +
CONST_BYTES_VEC8BIT(list)[1 / elts]]);
// replace the bits by FF elts as the case may be // this must of course be done from the end of the list backwards for (i = len; 2 < i; i--) {
fieldobj = FFE_FELT_FIELDINFO_8BIT(
info, gettab[256 * ((i - 1) % elts) +
CONST_BYTES_VEC8BIT(list)[(i - 1) / elts]]);
SET_ELM_PLIST(list, i, fieldobj);
} if (len > 1)
SET_ELM_PLIST(list, 2, second);
SET_ELM_PLIST(list, 1, first);
} // Null out any entries after the end of valid data // As the size of the VEC8BIT might not evenly divide sizeof(Int), we // cannot use PLIST methods to set the end of the list to zero
startblank = (Char *)(PTR_BAG(list) + (len + 1));
endblank = (Char *)PTR_BAG(list) + SIZE_BAG(list);
memset(startblank, 0, endblank - startblank);
CHANGED_BAG(list);
}
/**************************************************************************** ** *F FuncPLAIN_VEC8BIT( <self>, <list> ) . . . . convert back into plain list
*/ static Obj FuncPLAIN_VEC8BIT(Obj self, Obj list)
{ if (!IS_VEC8BIT_REP(list)) {
RequireArgument(SELF_NAME, list, "must be an 8bit vector");
} if (DoFilter(IsLockedRepresentationVector, list) == True) {
ErrorMayQuit("Cannot convert a locked vector compressed over " "GF(%d) to a plain list",
FIELD_VEC8BIT(list), 0);
}
PlainVec8Bit(list);
/**************************************************************************** ** *F AddVec8BitVec8BitInner( <sum>, <vl>, <vr>, <start>, <stop> ) ** ** This is the real vector add routine. Others are all calls to this ** one. ** Addition is done from THE BLOCK containing <start> to the one ** containing <stop> INCLUSIVE. The remainder of <sum> is unchanged. ** <sum> may be the same vector as <vl> or ** <vr>. <vl> and <vr> must be over the same field and <sum> must be ** initialized as a vector over this field of length at least <stop>. **
*/
// Maybe there's nothing to do if (!stop) return;
info = GetFieldInfo8Bit(FIELD_VEC8BIT(sum));
GAP_ASSERT(Q_FIELDINFO_8BIT(info) == FIELD_VEC8BIT(vl));
GAP_ASSERT(Q_FIELDINFO_8BIT(info) == FIELD_VEC8BIT(vr));
GAP_ASSERT(LEN_VEC8BIT(sum) >= stop);
GAP_ASSERT(LEN_VEC8BIT(vl) >= stop);
GAP_ASSERT(LEN_VEC8BIT(vr) >= stop);
p = P_FIELDINFO_8BIT(info);
elts = ELS_BYTE_FIELDINFO_8BIT(info); // Convert from 1 based to zero based addressing
start--;
stop--; if (p == 2) { const UInt * ptrL2; const UInt * ptrR2;
UInt * ptrS2;
UInt * endS2; // HPCGAP: Make sure to only check read guards for vl & vr.
ptrL2 = CONST_BLOCKS_VEC8BIT(vl) + start / (sizeof(UInt) * elts);
ptrR2 = CONST_BLOCKS_VEC8BIT(vr) + start / (sizeof(UInt) * elts);
ptrS2 = BLOCKS_VEC8BIT(sum) + start / (sizeof(UInt) * elts);
endS2 = BLOCKS_VEC8BIT(sum) + stop / (sizeof(UInt) * elts) + 1; if (sum == vl) { while (ptrS2 < endS2) {
*ptrS2 ^= *ptrR2;
ptrS2++;
ptrR2++;
}
} elseif (sum == vr) { while (ptrS2 < endS2) {
*ptrS2 ^= *ptrL2;
ptrL2++;
ptrS2++;
}
} else while (ptrS2 < endS2)
*ptrS2++ = *ptrL2++ ^ *ptrR2++;
} else { const UInt1 * ptrL; const UInt1 * ptrR;
UInt1 * ptrS;
UInt1 * endS;
UInt x; const UInt1 * addtab = ADD_FIELDINFO_8BIT(info); // HPCGAP: Make sure to only check read guards for vl & vr.
ptrL = CONST_BYTES_VEC8BIT(vl) + start / elts;
ptrR = CONST_BYTES_VEC8BIT(vr) + start / elts;
ptrS = BYTES_VEC8BIT(sum) + start / elts;
endS = BYTES_VEC8BIT(sum) + stop / elts + 1; if (vl == sum) { while (ptrS < endS) {
x = *ptrR; if (x != 0)
*ptrS = addtab[256 * (*ptrS) + x];
ptrR++;
ptrS++;
}
} elseif (vr == sum) { while (ptrS < endS) {
x = *ptrL; if (x != 0)
*ptrS = addtab[256 * (x) + *ptrS];
ptrS++;
ptrL++;
}
} else while (ptrS < endS)
*ptrS++ = addtab[256 * (*ptrL++) + *ptrR++];
}
}
/**************************************************************************** ** *F SumVec8BitVec8Bit( <vl>, <vr> ) ** ** This is perhaps the simplest wrapper for the Add..Inner function ** it allocates a new vector for the result, and adds the whole vectors into ** it. No checking is done. The result follows the new mutability convention ** (mutable if either argument is).
*/
q = FIELD_VEC8BIT(vl);
len = LEN_VEC8BIT(vl);
info = GetFieldInfo8Bit(q);
elts = ELS_BYTE_FIELDINFO_8BIT(info);
sum = NewWordSizedBag(T_DATOBJ, SIZE_VEC8BIT(len, elts));
SET_LEN_VEC8BIT(sum, len);
type = TypeVec8Bit(q, IS_MUTABLE_OBJ(vl) || IS_MUTABLE_OBJ(vr));
SetTypeDatObj(sum, type);
SET_FIELD_VEC8BIT(sum, q);
CHANGED_BAG(sum);
AddVec8BitVec8BitInner(sum, vl, vr, 1, len); return sum;
}
/**************************************************************************** ** *F FuncSUM_VEC8BIT_VEC8BIT( <self>, <vl>, <vr> ) ** ** This is the GAP callable method for +. The method installation should ** ensure that we have matching characteristics, but we may not have a common ** field or the same lengths **
*/
static Obj ConvertToVectorRep; // BH: changed to static
/**************************************************************************** ** *F MultVec8BitFFEInner( <prod>, <vec>, <scal>, <start>, <stop> ) ** ** This is the real vector * scalar routine. Others are all calls to this ** one. ** Multiplication is done from THE BLOCK containing <start> to the one ** containing <stop> INCLUSIVE. The remainder of <prod> is unchanged. ** <prod> may be the same vector as <vec> ** <scal> must be written over the field of <vec> and ** <prod> must be ** initialized as a vector over this field of length at least <stop>. **
*/
/**************************************************************************** ** *F MultVec8BitFFE( <vec>, <scal> ) . . . simple scalar multiply ** ** This is a basic wrapper for Mult...Inner. It allocates space for ** the result, promotes the scalar to the proper field if necessary and ** runs over the whole vector **
*/
/**************************************************************************** ** *F FuncPROD_VEC8BIT_FFE( <self>, <vec>, <ffe> ) ** ** This is the GAP callable method for *. The method installation should ** ensure that we have matching characteristics, but we may not have a common ** field **
*/
/**************************************************************************** ** *F FuncPROD_FFE_VEC8BIT( <self>, <ffe>, <vec> ) ** ** This is the GAP callable method for *. The method installation should ** ensure that we have matching characteristics, but we may not have a common ** field ** ** Here we can fall back on the method above.
*/
/**************************************************************************** ** *F AddVec8BitVec8BitMultInner( <sum>, <vl>, <vr>, <mult> <start>, <stop> ) ** ** This is the real vector add multiple routine. Others are all calls to ** this one. It adds <mult>*<vr> to <vl> leaving the result in <sum> ** ** Addition is done from THE BLOCK containing <start> to the one ** containing <stop> INCLUSIVE. The remainder of <sum> is unchanged. ** <sum> may be the same vector as <vl> or ** <vr>. <vl> and <vr> must be over the same field and <sum> must be ** initialized as a vector over this field of length at least <stop>. ** ** <mult> is assumed to be over the correct field and may not be zero **
*/
// Now check the field of <mul> if (q != SIZE_FF(FLD_FFE(mul))) {
Obj info;
UInt d, d1;
FFV val;
info = GetFieldInfo8Bit(q);
d = D_FIELDINFO_8BIT(info);
d1 = DegreeFFE(mul); if (d % d1) return TRY_NEXT_METHOD;
val = VAL_FFE(mul); if (val != 0)
val = 1 + (val - 1) * (q - 1) / (SIZE_FF(FLD_FFE(mul)) - 1);
mul = NEW_FFE(FiniteField(P_FIELDINFO_8BIT(info), d), val);
}
MultVec8BitFFEInner(vec, vec, mul, 1, LEN_VEC8BIT(vec)); return (Obj)0;
}
/**************************************************************************** ** *F FuncADD_ROWVECTOR_VEC8BITS_5( <self>, <vl>, <vr>, <mul>, <from>, <to> ) ** ** The three argument method for AddRowVector **
*/
static Obj AddRowVector;
static Obj FuncADD_ROWVECTOR_VEC8BITS_5(
Obj self, Obj vl, Obj vr, Obj mul, Obj from, Obj to)
{
UInt q;
UInt len;
len = LEN_VEC8BIT(vl); // There may be nothing to do if (LT(to, from)) return (Obj)0;
if (len != LEN_VEC8BIT(vr)) {
ErrorMayQuit("AddRowVector: and must be " "vectors of the same length",
0, 0);
} if (LT(INTOBJ_INT(len), to)) {
ErrorMayQuit("AddRowVector: (%d) is greater than the " "length of the vectors (%d)",
INT_INTOBJ(to), len);
} if (LT(to, from)) return (Obj)0;
// Now we know that the characteristics must match, but not the fields
q = FIELD_VEC8BIT(vl);
// fix up fields if necessary if (q != FIELD_VEC8BIT(vr) || q != SIZE_FF(FLD_FFE(mul))) {
Obj info, info1;
UInt d, d1, q1, d2, d0, q0, p, i;
FFV val;
// find a common field
info = GetFieldInfo8Bit(q);
d = D_FIELDINFO_8BIT(info);
q1 = FIELD_VEC8BIT(vr);
info1 = GetFieldInfo8Bit(q1);
d1 = D_FIELDINFO_8BIT(info1);
d2 = DegreeFFE(mul);
d0 = LcmDegree(d, d1);
d0 = LcmDegree(d0, d2);
p = P_FIELDINFO_8BIT(info);
GAP_ASSERT(p == P_FIELDINFO_8BIT(info1));
GAP_ASSERT(p == CHAR_FF(FLD_FFE(mul)));
q0 = 1; for (i = 0; i < d0; i++)
q0 *= p;
// if the exponent is bigger than 31, overflow changes the value to 0 if (d0 > 8 || q0 > 256) return TRY_NEXT_METHOD; if ((q0 > q && DoFilter(IsLockedRepresentationVector, vl) == True) ||
(q0 > q1 && DoFilter(IsLockedRepresentationVector, vr) == True)) return TRY_NEXT_METHOD;
RewriteVec8Bit(vl, q0);
RewriteVec8Bit(vr, q0);
val = VAL_FFE(mul); if (val != 0)
val = 1 + (val - 1) * (q0 - 1) / (SIZE_FF(FLD_FFE(mul)) - 1);
mul = NEW_FFE(FiniteField(p, d0), val);
}
/**************************************************************************** ** *F FuncADD_ROWVECTOR_VEC8BITS_3( <self>, <vl>, <vr>, <mul> ) ** ** The three argument method for AddRowVector **
*/
static Obj FuncADD_ROWVECTOR_VEC8BITS_3(Obj self, Obj vl, Obj vr, Obj mul)
{
UInt q; if (LEN_VEC8BIT(vl) != LEN_VEC8BIT(vr)) {
ErrorMayQuit( "SUM: and must be vectors of the same length", 0,
0);
} // Now we know that the characteristics must match, but not the fields
q = FIELD_VEC8BIT(vl);
// fix up fields if necessary if (q != FIELD_VEC8BIT(vr) || q != SIZE_FF(FLD_FFE(mul))) {
Obj info, info1;
UInt d, d1, q1, d2, d0, q0, p, i;
FFV val; // find a common field
info = GetFieldInfo8Bit(q);
d = D_FIELDINFO_8BIT(info);
q1 = FIELD_VEC8BIT(vr);
info1 = GetFieldInfo8Bit(q1);
d1 = D_FIELDINFO_8BIT(info1);
d2 = DegreeFFE(mul);
d0 = LcmDegree(d, d1);
d0 = LcmDegree(d0, d2);
p = P_FIELDINFO_8BIT(info);
GAP_ASSERT(p == P_FIELDINFO_8BIT(info1));
GAP_ASSERT(p == CHAR_FF(FLD_FFE(mul)));
q0 = 1; for (i = 0; i < d0; i++)
q0 *= p;
// if the exponent is bigger than 31, overflow changes the value to 0 if (d0 > 8 || q0 > 256) return TRY_NEXT_METHOD; if ((q0 > q &&
CALL_1ARGS(IsLockedRepresentationVector, vl) == True) ||
(q0 > q1 && CALL_1ARGS(IsLockedRepresentationVector, vr) == True)) return TRY_NEXT_METHOD;
RewriteVec8Bit(vl, q0);
RewriteVec8Bit(vr, q0);
val = VAL_FFE(mul); if (val != 0)
val = 1 + (val - 1) * (q0 - 1) / (SIZE_FF(FLD_FFE(mul)) - 1);
mul = NEW_FFE(FiniteField(p, d0), val);
}
AddVec8BitVec8BitMultInner(vl, vl, vr, mul, 1, LEN_VEC8BIT(vl)); return (Obj)0;
}
/**************************************************************************** ** *F FuncADD_ROWVECTOR_VEC8BITS_2( <self>, <vl>, <vr>) ** ** The two argument method for AddRowVector **
*/
static Obj FuncADD_ROWVECTOR_VEC8BITS_2(Obj self, Obj vl, Obj vr)
{
UInt q; if (LEN_VEC8BIT(vl) != LEN_VEC8BIT(vr)) {
ErrorMayQuit( "SUM: and must be vectors of the same length", 0,
0);
} // Now we know that the characteristics must match, but not the fields
q = FIELD_VEC8BIT(vl); // fix up fields if necessary if (q != FIELD_VEC8BIT(vr)) {
Obj info1;
Obj info;
UInt d, d1, q1, d0, q0, p, i; // find a common field
info = GetFieldInfo8Bit(q);
d = D_FIELDINFO_8BIT(info);
q1 = FIELD_VEC8BIT(vr);
info1 = GetFieldInfo8Bit(q1);
d1 = D_FIELDINFO_8BIT(info1);
d0 = LcmDegree(d, d1);
p = P_FIELDINFO_8BIT(info);
GAP_ASSERT(p == P_FIELDINFO_8BIT(info1));
q0 = 1; for (i = 0; i < d0; i++)
q0 *= p;
// if the exponent is bigger than 31, overflow changes the value to 0 if (d0 > 8 || q0 > 256) return TRY_NEXT_METHOD; if ((q0 > q &&
CALL_1ARGS(IsLockedRepresentationVector, vl) == True) ||
(q0 > q1 && CALL_1ARGS(IsLockedRepresentationVector, vr) == True)) return TRY_NEXT_METHOD;
RewriteVec8Bit(vl, q0);
RewriteVec8Bit(vr, q0);
q = q0;
}
AddVec8BitVec8BitInner(vl, vl, vr, 1, LEN_VEC8BIT(vl)); return (Obj)0;
}
/**************************************************************************** ** *F SumVec8BitVec8BitMult( <vl>, <vr>, <mult> ) ** ** This is perhaps the simplest wrapper for the Add..MultInner function ** it allocates a new vector for the result, and adds the whole vectors into ** it. Mult is promoted to the proper field if necessary. ** The result follows the new mutability convention ** (mutable if either argument is).
*/
if (FIELD_VEC8BIT(vl) != FIELD_VEC8BIT(vr)) {
UInt ql = FIELD_VEC8BIT(vl), qr = FIELD_VEC8BIT(vr);
Obj infol = GetFieldInfo8Bit(ql), infor = GetFieldInfo8Bit(qr);
UInt newd =
LcmDegree(D_FIELDINFO_8BIT(infol), D_FIELDINFO_8BIT(infor));
UInt p, newq;
UInt i;
p = P_FIELDINFO_8BIT(infol);
GAP_ASSERT(p == P_FIELDINFO_8BIT(infor));
newq = 1; for (i = 0; i < newd; i++)
newq *= p; // if the exponent is bigger than 31, overflow changes the value to 0 if (newd > 8 || newq > 256 ||
(ql != newq && True == CALL_1ARGS(IsLockedRepresentationVector, vl)) ||
(qr != newq && True == CALL_1ARGS(IsLockedRepresentationVector, vr))) {
diff = DiffListList(vl, vr);
CALL_1ARGS(ConvertToVectorRep, diff); return diff;
} else {
RewriteVec8Bit(vl, newq);
RewriteVec8Bit(vr, newq);
}
}
// Finally the main line return DiffVec8BitVec8Bit(vl, vr);
}
/**************************************************************************** ** *F CmpVec8BitVec8Bit( <vl>, <vr> ) .. comparison, returns -1, 0 or 1 ** ** characteristic and field should have been checked outside, but we must ** deal with length variations
*/
// we stop a little short, so as to handle the final byte separately
endL = ptrL + lenl / elts;
endR = ptrR + lenr / elts;
gettab = GETELT_FIELDINFO_8BIT(info);
ffe_elt = CONST_FFE_FELT_FIELDINFO_8BIT(info); while (ptrL < endL && ptrR < endR) { if (*ptrL == *ptrR) {
ptrL++;
ptrR++;
} else { for (e = 0; e < elts; e++) {
vall = gettab[*ptrL + 256 * e];
valr = gettab[*ptrR + 256 * e]; if (vall != valr) { if (LT(ffe_elt[vall], ffe_elt[valr])) return -1; else return 1;
}
}
ErrorQuit("panic: bytes differed but all entries the same", 0, 0);
}
} // now the final byte if (lenl < lenr)
len = lenl; else
len = lenr;
// look first at the shared part for (e = 0; e < (len % elts); e++) {
vall = gettab[*ptrL + 256 * e];
valr = gettab[*ptrR + 256 * e]; if (vall != valr) { if (LT(ffe_elt[vall], ffe_elt[valr])) return -1; else return 1;
}
} // if that didn't decide then the longer list is bigger if (lenr > lenl) return -1; elseif (lenr == lenl) return 0; else return 1;
}
/**************************************************************************** ** *F ScalarProductVec8Bits( <vl>, <vr> ) scalar product of vectors ** ** Assumes that length and field match **
*/
¤ 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.42Bemerkung:
(vorverarbeitet)
¤
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.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
