---

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Lab1_LFSR_Geffa
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.OutputEncoding = Encoding.UTF8;

            // Параметры для генератора Геффа (вариант 1)
            // LFSR1: (16,5,3,2,0)
            // LFSR2: (8,4,3,2,0)  
            // LFSR3: (32,7,6,2,0)

            var taps1 = new int[] { 16, 5, 3, 2, 0 };
            var taps2 = new int[] { 8, 4, 3, 2, 0 };
            var taps3 = new int[] { 32, 7, 6, 2, 0 };

            LFSR lfsr1 = new LFSR(taps1);
            LFSR lfsr2 = new LFSR(taps2);
            LFSR lfsr3 = new LFSR(taps3);

            GeffaGenerator geffa = new GeffaGenerator(lfsr1, lfsr2, lfsr3);

            // Определяем период = LCM(периодов LFSR)
            long period1 = (1L << taps1[0]) - 1; // 2^16 - 1
            long period2 = (1L << taps2[0]) - 1; // 2^8 - 1
            long period3 = (1L << taps3[0]) - 1; // 2^32 - 1
            long totalPeriod = Lcm(Lcm(period1, period2), period3);
            Console.WriteLine($"Теоретический период генератора: {totalPeriod} бит");
            Console.WriteLine($"Практически будет сгенерировано: {Math.Min(totalPeriod, 1000000)} бит (для тестов)");

            // Генерируем последовательность (для тестов берем 1 000 000 бит или период, если меньше)
            int n = (int)Math.Min(totalPeriod, 1000000);
            bool[] sequence = new bool[n];
            for (int i = 0; i < n; i++)
            {
                sequence[i] = geffa.NextBit();
            }

            // Запись в файл (бинарный)
            string fileName = "sequence_geffa.bin";
            using (FileStream fs = new FileStream(fileName, FileMode.Create))
            {
                byte[] bytes = new byte[(n + 7) / 8];
                for (int i = 0; i < n; i++)
                {
                    if (sequence[i])
                    {
                        bytes[i / 8] |= (byte)(1 << (7 - (i % 8)));
                    }
                }
                fs.Write(bytes, 0, bytes.Length);
            }
            Console.WriteLine($"Последовательность записана в файл {fileName}");

            // Статистические тесты
            Console.WriteLine("\n=== РЕЗУЛЬТАТЫ СТАТИСТИЧЕСКИХ ТЕСТОВ ===");
            Console.WriteLine($"Уровень значимости α = 0.05");

            // 1. Частотный тест
            double X1 = FrequencyTest(sequence);
            double chi1 = 3.8415; // χ²(1, 0.95)
            Console.WriteLine($"1. Частотный тест: X1 = {X1:F4}, порог = {chi1:F4} => {(X1 <= chi1 ? "ПРОЙДЕН" : "НЕ ПРОЙДЕН")}");

            // 2. Тест на серии
            double X2 = SeriesTest(sequence);
            double chi2 = 5.9915; // χ²(2, 0.95)
            Console.WriteLine($"2. Тест на серии: X2 = {X2:F4}, порог = {chi2:F4} => {(X2 <= chi2 ? "ПРОЙДЕН" : "НЕ ПРОЙДЕН")}");

            // 3. Обобщенный тест (m=3)
            double X3 = GeneralizedTest(sequence, 3);
            double chi3 = 14.0671; // χ²(7, 0.95)
            Console.WriteLine($"3. Обобщенный тест (m=3): X3 = {X3:F4}, порог = {chi3:F4} => {(X3 <= chi3 ? "ПРОЙДЕН" : "НЕ ПРОЙДЕН")}");

            // 4. Тест на последовательности
            double X4 = RunsTest(sequence);
            double chi4 = 9.4877; // χ²(4, 0.95)
            Console.WriteLine($"4. Тест на последовательности: X4 = {X4:F4}, порог = {chi4:F4} => {(X4 <= chi4 ? "ПРОЙДЕН" : "НЕ ПРОЙДЕН")}");

            // 5. Автокорреляционный тест (d = n/4)
            int d = n / 4;
            if (d < 1) d = 1;
            if (n - d >= 10)
            {
                double X5 = AutocorrelationTest(sequence, d);
                double threshold = 1.96; // N(0,1) при α=0.05
                Console.WriteLine($"5. Автокорреляционный тест (d={d}): X5 = {X5:F4}, порог = {threshold:F4} => {(Math.Abs(X5) <= threshold ? "ПРОЙДЕН" : "НЕ ПРОЙДЕН")}");
            }
            else
            {
                Console.WriteLine($"5. Автокорреляционный тест: n-d = {n-d} < 10, тест не применим");
            }

            Console.WriteLine("\nНажмите любую клавишу для выхода...");
            Console.ReadKey();
        }

        // LFSR класс
        class LFSR
        {
            private uint state;
            private int n;
            private int[] taps;

            public LFSR(int[] tapPositions)
            {
                taps = tapPositions;
                n = taps[0];
                state = 1; // инициализация
                // Убедимся, что состояние не нулевое
                if (n >= 32) state = 0xAAAAAAAA;
            }

            public bool NextBit()
            {
                uint newBit = 0;
                // XOR всех отводных битов
                foreach (int tap in taps)
                {
                    if (tap != n) // последний элемент всегда 0 (выходной бит)
                    {
                        newBit ^= (state >> (tap - 1)) & 1;
                    }
                }
                // Сдвиг вправо, новый бит становится старшим
                state = (state >> 1) | (newBit << (n - 1));
                // Возвращаем младший бит (выход)
                return (state & 1) == 1;
            }

            public void Reset()
            {
                state = 1;
            }
        }

        // Генератор Геффа
        class GeffaGenerator
        {
            private LFSR lfsr1, lfsr2, lfsr3;

            public GeffaGenerator(LFSR a, LFSR b, LFSR c)
            {
                lfsr1 = a;
                lfsr2 = b;
                lfsr3 = c;
            }

            public bool NextBit()
            {
                bool x1 = lfsr1.NextBit();
                bool x2 = lfsr2.NextBit();
                bool x3 = lfsr3.NextBit();
                // Функция большинства
                return (x1 & x2) ^ (x1 & x3) ^ (x2 & x3);
            }

            public void Reset()
            {
                lfsr1.Reset();
                lfsr2.Reset();
                lfsr3.Reset();
            }
        }

        // Вспомогательные функции для тестов

        // НОД
        static long Gcd(long a, long b)
        {
            while (b != 0)
            {
                long temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }

        // НОК
        static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }

        // 1. Частотный тест
        static double FrequencyTest(bool[] seq)
        {
            int n = seq.Length;
            int n0 = seq.Count(b => !b);
            int n1 = n - n0;
            return (double)((n0 - n1) * (n0 - n1)) / n;
        }

        // 2. Тест на серии (двухразрядный)
        static double SeriesTest(bool[] seq)
        {
            int n = seq.Length;
            if (n < 21) return 0;

            int n0 = seq.Count(b => !b);
            int n1 = n - n0;

            int n00 = 0, n01 = 0, n10 = 0, n11 = 0;
            for (int i = 0; i < n - 1; i++)
            {
                if (!seq[i] && !seq[i + 1]) n00++;
                else if (!seq[i] && seq[i + 1]) n01++;
                else if (seq[i] && !seq[i + 1]) n10++;
                else if (seq[i] && seq[i + 1]) n11++;
            }

            double sum = n00 * n00 + n01 * n01 + n10 * n10 + n11 * n11;
            double val = (4.0 / (n - 1)) * sum - (2.0 / n) * (n0 * n0 + n1 * n1) + 1;
            return val;
        }

        // 3. Обобщенный тест (m=3)
        static double GeneralizedTest(bool[] seq, int m)
        {
            int n = seq.Length;
            int k = n / m;
            if (k < 5 * (1 << m)) return 0;

            int patterns = 1 << m;
            int[] counts = new int[patterns];
            for (int i = 0; i < k; i++)
            {
                int idx = 0;
                for (int j = 0; j < m; j++)
                {
                    idx = (idx << 1) | (seq[i * m + j] ? 1 : 0);
                }
                counts[idx]++;
            }

            double sum = 0;
            for (int i = 0; i < patterns; i++)
            {
                sum += counts[i] * counts[i];
            }
            return (double)(patterns) / k * sum - k;
        }

        // 4. Тест на последовательности (Runs test)
        static double RunsTest(bool[] seq)
        {
            int n = seq.Length;
            // Определяем k - максимальное i, для которого e_i >= 5
            int k = 1;
            while (true)
            {
                double e = (n - k + 3) / Math.Pow(2, k + 2);
                if (e < 5) break;
                k++;
            }
            k = Math.Min(k, 10); // ограничим для производительности

            double result = 0;
            for (int i = 1; i <= k; i++)
            {
                double e = (n - i + 3) / Math.Pow(2, i + 2);
                int blocks = 0, gaps = 0;

                // Подсчет блоков (единиц) длины i
                int runLen = 0;
                for (int j = 0; j < n; j++)
                {
                    if (seq[j])
                    {
                        runLen++;
                    }
                    else
                    {
                        if (runLen == i) blocks++;
                        runLen = 0;
                    }
                }
                if (runLen == i) blocks++;

                // Подсчет промежутков (нулей) длины i
                runLen = 0;
                for (int j = 0; j < n; j++)
                {
                    if (!seq[j])
                    {
                        runLen++;
                    }
                    else
                    {
                        if (runLen == i) gaps++;
                        runLen = 0;
                    }
                }
                if (runLen == i) gaps++;

                result += (blocks - e) * (blocks - e) / e;
                result += (gaps - e) * (gaps - e) / e;
            }
            return result;
        }

        // 5. Автокорреляционный тест
        static double AutocorrelationTest(bool[] seq, int d)
        {
            int n = seq.Length;
            if (n - d < 10) return 0;

            int A = 0;
            for (int i = 0; i < n - d; i++)
            {
                if (seq[i] != seq[i + d]) A++;
            }
            return 2 * (A - (double)(n - d) / 2) / Math.Sqrt(n - d);
        }
    }
}