F2wStructure.java

/*
 * Class:        F2wStructure
 * Description:  Tools for point sets and sequences based on field F_{2^w}
 * Environment:  Java
 * Software:     SSJ
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author
 * @since
 *
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
package umontreal.ssj.hups;
 
import java.io.*;
import java.util.*;

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));
      }
   }

   F2wStructure(int w, int r, int modQ, int step, int nbcoeff, int coeff[], int nocoeff[]) {
      init(w, r, modQ, step, nbcoeff, coeff, nocoeff);
   }

   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 {
            // does not work anymore since the files and directories have been removed
            // from package hups and put instead on the WWW page.
            // Should be read with protocol http as in class DigitalNetFromFile
            DataInputStream dataInput;
            dataInput = new DataInputStream(F2wStructure.class.getClassLoader()
                  .getResourceAsStream("umontreal/ssj/hups/dataF2w/Panneton/" + 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;
      }
   }

   int getLog2N() {
      return r * w;
   }

   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;
   }

   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/ssj/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);
      }
   }

   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);
      }
   }
}