package umontreal.iro.lecuyer.hups;
/* *
* Title:
* Description:
* Copyright: Copyright (c)
* Company:
* @author
* @version 1.0
*/
import java.io.*;
import java.util.*;
/**
* This class implements methods and fields needed by the classes
* {@link umontreal.iro.lecuyer.hups.F2wNetLFSR F2wNetLFSR},
* {@link umontreal.iro.lecuyer.hups.F2wNetPolyLCG F2wNetPolyLCG},
* {@link umontreal.iro.lecuyer.hups.F2wCycleBasedLFSR F2wCycleBasedLFSR} and
* {@link umontreal.iro.lecuyer.hups.F2wCycleBasedPolyLCG F2wCycleBasedPolyLCG}.
* It also stores the parameters of these point sets which will contain
* 2rw points (see the meaning of r and w below).
* The parameters can be stored as a polynomial P(z) over
*
* F2w[z]
*
*
*
* P(z) = zr + ∑i=1rbizr-i
*
* where
* bi∈F2w for
* i = 1,…, r.
* Let ζ be the root of an irreducible polynomial
*
* Q(z)∈F2[z]. It is well known
* that ζ is a generator of the finite field
*
* F2w.
* The elements of
* F2w are
* represented using the polynomial ordered
* basis
* (1, ζ,…, ζw-1).
*
*
* In this class, only the non-zero coefficients of P(z) are stored.
* It is stored as
*
*
*
* P(z) = zr + ∑i=0nbcoeffcoeff[i]znocoeff[i]
*
* where the coefficients in coeff[] represent the non-zero
* coefficients bi of P(z) using the polynomial basis.
* The finite field
* F2w used is
* defined by the polynomial
*
*
*
* Q(z) = zw + ∑i=1waizw-i
*
* where
* ai∈F2,
* for
* i = 1,…, w. Polynomial Q is
* stored as the bit vector modQ =
* (aw,…, a1).
*
*
* The class also stores the parameter step that is used by the classes
* {@link umontreal.iro.lecuyer.hups.F2wNetLFSR F2wNetLFSR},
* {@link umontreal.iro.lecuyer.hups.F2wNetPolyLCG F2wNetPolyLCG},
* {@link umontreal.iro.lecuyer.hups.F2wCycleBasedLFSR F2wCycleBasedLFSR} and
* {@link umontreal.iro.lecuyer.hups.F2wCycleBasedPolyLCG F2wCycleBasedPolyLCG}.
* This parameter is such that the implementation of the recurrence
* will output a value at every step iterations.
*
*/
public class F2wStructure {
private final int ALLONES = 2147483647; // 2^31-1 --> 01111...1
int w;
int r;
int numBits;
private int modQ;
private int step;
private int[] coeff;
private int[] nocoeff;
private int nbcoeff;
int S;
private int maskw;
private int maskrw;
private int maskZrm1;
private int mask31;
private int t;
private int masktrw;
private int[] maskv;
int state;
int output; // augmented state
double normFactor;
double EpsilonHalf;
final static int MBL = 140; //maximum of bytes in 1 line
//92 bytes for a number of coeff = 15
private void init (int w, int r, int modQ, int step,
int nbcoeff, int coeff[], int nocoeff[])
{
normFactor = 1.0 / (1L << 31); // 4.65661287307739258e-10;
EpsilonHalf = 0.5*normFactor;
numBits = 31;
this.step = step;
this.w = w;
this.r = r;
S = 31 - r * w;
mask31 = ~(1 << 31);
maskw = (1 << w) - 1;
maskrw = ((1 << (r * w)) - 1) << S;
maskZrm1 = (ALLONES >> (r * w)) ^ (ALLONES >> ((r - 1) * w));
this.modQ = modQ;
this.nbcoeff = nbcoeff;
this.nocoeff = new int[nbcoeff];
this.coeff = new int[nbcoeff];
for (int j = 0; j < nbcoeff; j++) {
this.nocoeff[j] = nocoeff[j];
this.coeff[j] = coeff[j];
}
}
void initParamLFSR ()
{
t = (31 - r * w) / w;
masktrw = (~0) << (31 - (t + r) * w) & mask31;
maskv = new int[r];
for (int j = 0; j < r; j++) {
maskv[j] = maskw << (S + ((r - 1 - j) * w));
}
}
/**
* Constructs a F2wStructure object that contains the parameters of a
* polynomial in
* F2w[z],
* as well as a stepping parameter.
*
*/
F2wStructure (int w, int r, int modQ, int step, int nbcoeff,
int coeff[], int nocoeff[])
{
init (w, r, modQ, step, nbcoeff, coeff, nocoeff);
}
/**
* Constructs a polynomial in
* F2w[z]
* after reading its parameters from file filename;
* the parameters of this polynomial are stored at line number
* no of filename.
* The files are kept in different
* directories depending on the criteria used in the searches for the
* parameters defining the polynomials. The different criteria for the
* searches and the theory behind it are described in.
* The existing files and the number of polynomials they contain are
* given in the following tables.
* The first table below contains files in subdirectory
* LFSR_equid_max. The name of each
* file indicates the value of r and w for the polynomials.
* For example, file f2wR2_W5.dat in directory
* LFSR_equid_max contains the parameters of 2358
* polynomials with r = 2 and w = 5. For example, to use the 5-th
* polynomial of file f2wR2_W5.dat, one may call
* F2wStructure("f2wR2_W5.dat", 5).
* The files of parameters have been stored at the address
* http://www.iro.umontreal.ca/~simardr/ssj-1/dataF2w/.
*
*/
F2wStructure (String filename, int no)
{
// If filename can be found starting from the program's directory,
// it will be used; otherwise, the filename in the Jar archive will
// be used.
BufferedReader input;
try {
if ((new File (filename)).exists()) {
input = new BufferedReader (new FileReader (filename));
} else {
DataInputStream dataInput;
dataInput = new DataInputStream (
F2wStructure.class.getClassLoader().getResourceAsStream (
"umontreal/iro/lecuyer/hups/dataF2w/" + filename));
input = new BufferedReader (new InputStreamReader (dataInput));
}
initFromReader (filename, input, no);
input.close ();
} catch (Exception e) {
System.out.println ("IO Error: problems finding file " + filename);
System.exit (1);
}
}
private int multiplyz (int a, int k)
{
int i;
if (k == 0)
return a & maskw;
else {
for (i = 0; i < k; i++) {
if ((1 & a) == 1) {
a = (a >> 1) ^ modQ;
} else
a = a >> 1;
}
return a & maskw;
}
}
/**
* This method returns the product rw.
*
*/
int getLog2N ()
{
return r * w;
}
/**
* Method that multiplies two elements in
*
* F2w.
*
*/
int multiply (int a, int b)
{
int i;
int res = 0, verif = 1;
for (i = 0; i < w; i++) {
if ((b & verif) == verif)
res ^= multiplyz (a, w - 1 - i);
verif <<= 1;
}
return res & maskw;
}
void initF2wLFSR () // Initialisation de l'etat d'un LFSR
{
int v, d = 0;
int tempState;
tempState = state << S;
output = tempState;
for (int i = 1; i <= t; i++) {
d = 0;
for (int j = 0; j < nbcoeff; j++) {
v = (tempState & maskv[nocoeff[j]]) >>
(S + (r - 1 - nocoeff[j]) * w);
d ^= multiply (coeff[j], v);
}
output |= d << (S - i * w);
tempState = (output << (i * w)) & maskrw;
}
}
void F2wLFSR () // Une iteration d'un LFSR
{
int v, d = 0;
int tempState;
for (int i = 0; i < step; i++) {
tempState = (output << (t * w)) & maskrw;
d = 0;
for (int j = 0; j < nbcoeff; j++) {
v = (tempState & maskv[nocoeff[j]]) >>
(S + (r - 1 - nocoeff[j]) * w);
d ^= multiply (coeff[j], v);
}
output = ((output << w) & masktrw) |
(d << (31 - (r + t) * w));
}
state = (output & maskrw) >> S;
}
int F2wPolyLCG () // Une iteration d'un PolyLCG
{
int Zrm1, d;
for (int i = 0; i < step; i++) {
Zrm1 = (state & maskZrm1) >> S;
state = (state >> w) & maskrw;
for (int j = 0; j < nbcoeff; j++)
state ^=
multiply (coeff[j], Zrm1) << (S + (r - 1 - nocoeff[j]) * w);
}
return state;
}
/**
* Prints the content of file filename. See the constructor
* above for the conditions on filename.
*
*/
public static void print (String filename)
{
BufferedReader input;
try {
if ((new File (filename)).exists()) {
input = new BufferedReader (new FileReader (filename));
} else {
DataInputStream dataInput;
dataInput = new DataInputStream (
F2wStructure.class.getClassLoader().getResourceAsStream (
"umontreal/iro/lecuyer/hups/dataF2w/" + filename));
input = new BufferedReader (new InputStreamReader (dataInput));
}
String s;
for (int i = 0; i < 4; i++)
input.readLine ();
while ((s = input.readLine ()) != null)
System.out.println (s);
input.close ();
} catch (Exception e) {
System.out.println ("IO Error: problems reading file " + filename);
System.exit (1);
}
}
/**
* This method returns a string containing the polynomial P(z) and
* the stepping parameter.
*
*/
public String toString ()
{
StringBuffer sb = new StringBuffer ("z^");
sb.append (r);
for (int j = nbcoeff - 1; j >= 0; j--)
sb.append (" + (" + coeff[j] + ") z^" + nocoeff[j]);
sb.append (" modQ = " + modQ + " w = " + w + " step = " + step);
return sb.toString ();
}
private void initFromReader (String filename, BufferedReader input, int no)
{
int w, r, modQ, step, nbcoeff;
int coeff[], nocoeff[];
StringTokenizer line;
int nl = no + 4;
try {
for (int j = 1; j < nl ; j++)
input.readLine ();
line = new StringTokenizer (input.readLine ());
w = Integer.parseInt (line.nextToken ());
r = Integer.parseInt (line.nextToken ());
modQ = Integer.parseInt (line.nextToken ());
step = Integer.parseInt (line.nextToken ());
nbcoeff = Integer.parseInt (line.nextToken ());
nocoeff = new int[nbcoeff];
coeff = new int[nbcoeff];
for (int i = 0; i < nbcoeff; i++) {
coeff[i] = Integer.parseInt (line.nextToken ());
nocoeff[i] = Integer.parseInt (line.nextToken ());
}
init (w, r, modQ, step, nbcoeff, coeff, nocoeff);
input.close ();
} catch (Exception e) {
System.out.println ("Input Error: problems reading file " + filename);
System.exit (1);
}
}
}
/**
* .
*
*
*
* Directory LFSR_equid_max
* Filename
* Num of poly.
* f2wR2_W5.dat
* 2358
* f2wR2_W6.dat
* 1618
* f2wR2_W7.dat
* 507
* f2wR2_W8.dat
* 26
* f2wR2_W9.dat
* 3
* f2wR3_W4.dat
* 369
* f2wR3_W5.dat
* 26
* f2wR3_W6.dat
* 1
* f2wR4_W3.dat
* 117
* f2wR4_W4.dat
* 1
* f2wR5_W2.dat
* 165
* f2wR5_W3.dat
* 1
* f2wR6_W2.dat
* 36
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 10
* f2wR8_W2.dat
* 11
* f2wR9_W2.dat
* 1
*
*
*
* Directory LFSR_equid_sum
* Filename
* Num of poly.
* f2wR2_W5.dat
* 2276
* f2wR2_W6.dat
* 1121
* f2wR2_W7.dat
* 474
* f2wR2_W8.dat
* 37
* f2wR2_W9.dat
* 6
* f2wR3_W4.dat
* 381
* f2wR3_W5.dat
* 65
* f2wR3_W6.dat
* 7
* f2wR4_W3.dat
* 154
* f2wR4_W4.dat
* 2
* f2wR5_W2.dat
* 688
* f2wR5_W3.dat
* 5
* f2wR6_W2.dat
* 70
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 9
* f2wR8_W2.dat
* 3
* f2wR9_W2.dat
* 3
*
*
*
*
*
*
* Directory LFSR_mindist_max
* Filename
* Num of poly.
* f2wR2_W5.dat
* 1
* f2wR2_W6.dat
* 1
* f2wR2_W7.dat
* 2
* f2wR2_W8.dat
* 2
* f2wR2_W9.dat
* 1
* f2wR3_W4.dat
* 2
* f2wR3_W5.dat
* 2
* f2wR3_W6.dat
* 1
* f2wR4_W3.dat
* 1
* f2wR4_W4.dat
* 1
* f2wR5_W2.dat
* 2
* f2wR5_W3.dat
* 1
* f2wR6_W2.dat
* 4
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 1
* f2wR8_W2.dat
* 1
* f2wR9_W2.dat
* 1
*
*
*
* Directory LFSR_mindist_sum
* Filename
* Num of poly.
* f2wR2_W5.dat
* 1
* f2wR2_W6.dat
* 1
* f2wR2_W7.dat
* 1
* f2wR2_W8.dat
* 1
* f2wR2_W9.dat
* 1
* f2wR3_W4.dat
* 1
* f2wR3_W5.dat
* 1
* f2wR3_W6.dat
* 1
* f2wR4_W3.dat
* 1
* f2wR4_W4.dat
* 2
* f2wR5_W2.dat
* 2
* f2wR5_W3.dat
* 2
* f2wR6_W2.dat
* 1
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 2
* f2wR8_W2.dat
* 1
* f2wR9_W2.dat
* 2
*
*
*
*
*
*
* Directory LFSR_tvalue_max
* Filename
* Num of poly.
* f2wR2_W5.dat
* 7
* f2wR2_W6.dat
* 1
* f2wR2_W7.dat
* 1
* f2wR2_W8.dat
* 1
* f2wR2_W9.dat
* 1
* f2wR3_W4.dat
* 1
* f2wR3_W5.dat
* 1
* f2wR3_W6.dat
* 1
* f2wR4_W3.dat
* 2
* f2wR4_W4.dat
* 1
* f2wR5_W2.dat
* 14
* f2wR5_W3.dat
* 1
* f2wR6_W2.dat
* 2
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 1
* f2wR8_W2.dat
* 1
* f2wR9_W2.dat
* 1
*
*
*
* Directory LFSR_tvalue_sum
* Filename
* Num of poly.
* f2wR2_W5.dat
* 15
* f2wR2_W6.dat
* 1
* f2wR2_W7.dat
* 1
* f2wR2_W8.dat
* 2
* f2wR2_W9.dat
* 1
* f2wR3_W4.dat
* 1
* f2wR3_W5.dat
* 1
* f2wR3_W6.dat
* 1
* f2wR4_W3.dat
* 2
* f2wR4_W4.dat
* 1
* f2wR5_W2.dat
* 13
* f2wR5_W3.dat
* 2
* f2wR6_W2.dat
* 12
* f2wR6_W3.dat
* 1
* f2wR7_W2.dat
* 1
* f2wR8_W2.dat
* 1
* f2wR9_W2.dat
* 1
*
*/
Ads help maintain this website.