int walshspectrum(int * spectrum, int * sbox, int extractor, int dimension)
{
	int size = (1<<dimension);
	int i,j,k,tmp,lin;
	
	for (i=0;i<size;i++)
	{
		spectrum[i] = (__builtin_popcount(sbox[i] & extractor) % 2)
		            ? -1
		            : 1;
	}

	/* walsh spectrum */
	
	int step = 1;
	for (i=0;i<dimension;i++)
	{
		for (k=0;k<size;k+=(step<<1))
			for (j=0;j<step;j++)
			{
				tmp = spectrum[j+k] + spectrum[j+k+step];
				spectrum[j+k+step] = spectrum[j+k] - spectrum[j+k+step];
				spectrum[j+k] = tmp;
			}
         step <<= 1;
	}

	lin = 0;
	for (i=0;i<size;i++)
	{
		if (spectrum[i] < 0)
		{
			if (- spectrum[i] > lin) lin = - spectrum[i];
		}
		else
		{
			if (spectrum[i] > lin)   lin = spectrum[i];
		}
	}
	return lin;
}

// returns degree of the ANF

int anf(int * ANF, int * sbox, int extractor, int dimension, int verbose)
{
	int size = (1<<dimension);
	int M[size][dimension+1];
	int i, j, k, step;
	int w, max_deg = 0;

    for (i=0;i<size;i++)
	{
		M[i][0] = __builtin_popcount(sbox[i] & extractor) % 2;
	}

    /* ANF */

    step = 1;
    for (i=0;i<dimension;i++)
    {

        for (k=0;k<size;k+=(step<<1))
        {
            for (j=0;j<step;j++)
            {
                // printf("combining pair (%d,%d)\n",j+k,j+k+step); fflush (stdout);
                M[j+k     ][i+1] = M[j+k][i];
                M[j+k+step][i+1] = (M[j+k][i] + M[j+k+step][i]) % 2;
            }
        }

        step <<= 1;
    }
    
	if (verbose)
	{
		for (i=0;i<size;i++)
		{
			for (j=size/2;j>0;j>>=1)
				printf( (i&j) ? "1" : "0");
			for (j=0; j <= dimension; j++)
				printf(" & %3d ", M[i][j]);
			printf(" \\\\\n");
		}
	}
	
	for (i=0;i<size;i++)
	{
		ANF[i] = M[i][dimension];
		if (ANF[i])
		{
			w = __builtin_popcount(i);
			if (w > max_deg) max_deg = w;
		}
	}
	
	return max_deg;
	
}

int linearity(int * sbox, int dimension)
{
	int size = (1<<dimension);
	int i,maxlin=0;
	int spectrum[size];

	for (i=1;i<size;i++)
	{
		int lin = walshspectrum(spectrum, sbox, i, dimension);
		if (lin < 0) lin = -lin;
		if (lin > maxlin) maxlin = lin;
	}
	return maxlin;
}

void flippedbits(int * flips, int * counts, int * sbox, int dimension)
{
	int i,j;
	int size = 1<<dimension;
	int mask;
	
	for (i=0,mask=1; i<dimension; i++,mask<<=1)
	{
		flips[i] = dimension;
		counts[i] = 0;
		for (j=0;j<size;j++)
		{
			if (!(j & mask))
			{
				int flip = __builtin_popcount(sbox[j]^sbox[j|mask]);
				if (flip == flips[i]) counts[i]++;
				if (flip < flips[i]) { flips[i] = flip; counts[i] = 1; }
			}
		}
	}
}