Skip to content

Instantly share code, notes, and snippets.

@tkroman
Last active August 29, 2015 14:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tkroman/2524433b65dc881a53a5 to your computer and use it in GitHub Desktop.
Save tkroman/2524433b65dc881a53a5 to your computer and use it in GitHub Desktop.
I don't know whether this piece is correct or not, neither do I know if it works at all, but this is definitely the most complete version I managed to find in my code clutter.
import java.util.Arrays;
import java.util.stream.IntStream;
public class Main {
final static int GMOD = 0x8000;
final static int MOD = 0x8003;
final static int DEG = 15;
final static int[] f1 = new int[GMOD];
static int[][] wf1;
final static int pow1 = (1 << 7) + 1;
// final static int pow1 = 257;
final static int[] f2 = new int[GMOD];
static int[][] wf2;
final static int pow2 = (1 << 5) + 1;
// final static int pow2 = 513;
static {
for (int x = 0; x < GMOD; x++) {
f1[x] = pow(x, pow1, MOD);
f2[x] = pow(x, pow2, MOD);
}
wf1 = fftWmod(f1);
wf2 = fftWmod(f2);
}
static int mul(int a, int b, int mod) {
int c = 0;
for (int i = 14; i > 0; i--) {
if (((b >> i) & 1) != 0) {
c ^= a;
}
c <<= 1;
if ((c & GMOD) != 0) {
c ^= mod;
}
}
if ((b & 1) != 0) {
c ^= a;
}
return c;
}
static int deg(int a) {
return a == 0 ? 0 : 63 - Long.numberOfLeadingZeros(a);
}
static int pow(int x, int m, int mod) {
int a = 1;
int j;
for (j = 14; j >= 0; --j) {
a = mul(a, a, mod);
if (((m >>> j) & 1) != 0) {
a = mul(a, x, mod);
}
}
return a;
}
static int mod(int q, int p) {
int k = deg(q);
int n = deg(p);
while (k >= n) {
k = deg(q);
q ^= p << (k - n);
}
return q;
}
static int add(int a, int b) {
return a ^ b;
}
static int s(String val) {
return Integer.parseInt(val, 2);
}
static double maxDiffPr(int[] f) {
int globalMax = 0;
for (int a = 1; a < GMOD; a++) {
int[] b = new int[GMOD];
for (int x = 0; x < GMOD; x++) {
b[f[x] ^ f[x ^ a]]++;
}
globalMax = Math.max(globalMax, IntStream.of(b).parallel().max().getAsInt());
}
return globalMax;
}
static int[][] fftWmod(int[] f) {
int[][] coeffs = new int[DEG][GMOD];
for (int i = 0; i < DEG; i++) {
coeffs[i] = new int[GMOD];
}
for (int x = 0; x < GMOD; x++) {
for(int i = 0; i < DEG; i++) {
coeffs[i][x] = ((f[x] >>> i) & 1) != 0 ? -1 : 1;
}
}
for (int i = 0, mask = 1; i < DEG; i++, mask <<= 1) {
for (int x = 0; x < GMOD; x++) {
if ((x & mask) != 0) {
for (int j = 0; j < DEG; j++) {
coeffs[j][x ^ mask] = coeffs[j][x ^ mask] + coeffs[j][x];
coeffs[j][x] = coeffs[j][x ^ mask] - 2 * coeffs[j][x];
}
}
}
}
return coeffs;
}
static void spreadFac(int[] f) {
int[][] k = new int[DEG][DEG];
for (int i = 0; i < DEG; i++) {
k[i] = new int[DEG];
}
for (int x = 0; x < GMOD; x++) {
for (int j = 0; j < DEG; j++) {
for (int i = 0; i < DEG; i++) {
k[j][i] += ((f[x] ^ f[x ^ (1 << i)]) >> j) & 1;
}
}
}
for (int i = 0; i < DEG; i++) {
System.out.printf("ES[%d]: %s\n", i, Arrays.toString(k[i]));
}
}
static void disbal(int[] f) {
int[] disb = new int[DEG];
for (int i = 0; i < GMOD; ++i) {
for (int j = 0; j < DEG; ++j) {
disb[j] += ((f[i] >> j) & 1);
}
}
for (int j = 0; j < DEG; ++j) {
System.out.printf("d[%d] = %d\n", j, Math.abs(2 * disb[j] - GMOD));
}
}
static int[] disbalXor(int[] f, int a) {
int[] disb = new int[DEG];
for (int i = 0; i < GMOD; ++i) {
for (int j = 0; j < DEG; ++j) {
disb[j] += ((f[i] >> j) & 1) ^ ((f[i ^ a] >> j) & 1);
}
}
for (int j = 0; j < DEG; ++j) {
disb[j] = Math.abs(2 * disb[j] - GMOD);
}
return disb;
}
static void avgSprFac(int[] f) {
int[] k = new int[DEG];
for (int x = 0; x < GMOD; x++) {
for (int j = 0; j < DEG; j++) {
k[j] += Integer.bitCount(f[x] ^ f[x ^ (1 << j)]);
}
}
for (int i = 0; i < DEG; i++) {
System.out.printf("AE[%d] = %d\n", i, k[i]);
}
}
static int[] zhCfts(int[] f) {
int[] coeffs = Arrays.copyOf(f, GMOD);
for (int i = 0, mask = 1; i < DEG; i++, mask <<= 1) {
for (int x = 0; x < GMOD; x++) {
if ((x & mask) != 0) {
coeffs[x] = coeffs[x ^ mask] ^ coeffs[x];
}
}
}
return coeffs;
}
static int zhDeg(int[] zhCoeffs) {
if(zhCoeffs[GMOD - 1] != 0) {
return DEG;
}
for(int i = 0, mask = 1; i < DEG; i++, mask <<= 1) {
if(zhCoeffs[(GMOD - 1) ^ mask] != 0) {
return DEG - 1;
}
}
int max = 0;
for(int x = 0; x < GMOD - 1; x++) {
int pop = Integer.bitCount(x);
if(zhCoeffs[x] != 0 && pop > max) {
max = pop;
}
}
return max;
}
static void nl(int[][] wf) {
for (int i = 0; i < DEG; i++) {
int max = 0;
for (int x = 0; x < GMOD; x++) {
if (max < wf[i][x]) {
max = wf[i][x];
}
}
System.out.printf("nl[%d] = %d\n", i, (GMOD - max) >>> 1);
}
}
static void corrImm(int[/*DEG*/][/*GMOD*/] wf) {
for (int i = 0; i < DEG; i++) { // i-th coord. fn
int k;
boolean isK = true;
for (k = 0; k < DEG && isK; k++) {
for (int w = 0; w < GMOD && isK; w++) {
if (Integer.bitCount(w) >= 1 && Integer.bitCount(w) <= k) {
if (wf[i][w] != 0) {
isK = false;
}
}
}
if (!isK) {
System.out.printf("f[%d]: %d\n", i, k - 1);
}
}
}
}
static void strictAvlCrit(int[] f) {
boolean[] satisfies = new boolean[DEG];
for (int a = 1; a < GMOD; a <<= 1) {
int[] disbal = disbalXor(f, a);
for (int i = 0; i < DEG; i++) {
satisfies[i] = (disbal[i] == 0);
}
}
for (int i = 0; i < DEG; i++) {
System.out.println(i + " satisfies ? " + satisfies[i]);
}
}
public static void main(String[] args) {
System.out.println("дисбаланс f1");
disbal(f1);
System.out.println("дисбаланс f2");
disbal(f2);
System.out.println("распространение ошибки f1");
spreadFac(f1);
System.out.println("распространение ошибки f2");
spreadFac(f2);
System.out.println("стр. ЛК в ср. f1");
avgSprFac(f1);
System.out.println("стр. ЛК в ср. f2");
avgSprFac(f2);
System.out.println("макс. дифф. вер-сть f1");
System.out.println(maxDiffPr(f1));
System.out.println("макс. дифф. вер-сть f2");
System.out.println(maxDiffPr(f2));
System.out.println("ст. п-ма Ж-на f1");
System.out.println(zhDeg(zhCfts(f1)));
System.out.println("ст. п-ма Ж-на f2");
System.out.println(zhDeg(zhCfts(f2)));
System.out.println("нелинейность f1");
nl(wf1);
System.out.println("нелинейность f2");
nl(wf2);
System.out.println("корр. имм-т f1");
corrImm(wf1);
System.out.println("корр. имм-т f2");
corrImm(wf2);
System.out.println("стр. лав. крит. f1");
strictAvlCrit(f1);
System.out.println("стр. лав. крит. f2");
strictAvlCrit(f2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment