Last active
August 29, 2015 14:03
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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