import turtle
import math


class GaloisField:
    """Helper class for Reed-Solomon error correction calculations"""
    
    def __init__(self, prime_poly=0x11D, field_size=256):
        self.prime_poly = prime_poly
        self.field_size = field_size
        self.exp = [0] * (field_size * 2)
        self.log = [0] * field_size
        
        # Initialize tables
        x = 1
        for i in range(field_size - 1):
            self.exp[i] = x
            self.log[x] = i
            x = self._multiply_noLUT(x, 2)
        
        # Extend the exponent table for easy calculations
        for i in range(field_size - 1, field_size * 2 - 2):
            self.exp[i] = self.exp[i - (field_size - 1)]
    
    def _multiply_noLUT(self, x, y):
        """Multiply two numbers in the Galois Field without lookup tables"""
        p = 0
        while y:
            if y & 1:
                p ^= x
            y >>= 1
            x <<= 1
            if x & self.field_size:
                x ^= self.prime_poly
        return p
    
    def multiply(self, x, y):
        """Multiply two numbers in the Galois Field using lookup tables"""
        if x == 0 or y == 0:
            return 0
        return self.exp[(self.log[x] + self.log[y]) % (self.field_size - 1)]
    
    def divide(self, x, y):
        """Divide x by y in the Galois Field"""
        if y == 0:
            raise ZeroDivisionError("Division by zero in Galois Field")
        if x == 0:
            return 0
        return self.exp[(self.log[x] + self.field_size - 1 - self.log[y]) % (self.field_size - 1)]




class QRCode:
    def __init__(self, data, error_correction="M", mask=None, enable_ec=True):
        """Initialize QR code with data, error correction level, and optional mask (0-7)"""
        self.data = data
        self.error_correction = error_correction
        self.mask = mask  # None means no mask
        self.size = 25  # Version 2 QR code is 25x25 modules
        self.matrix = [[0 for _ in range(self.size)] for _ in range(self.size)]
        self.ec_codewords = {"L": 10, "M": 16, "Q": 22, "H": 28}
        self.data_capacity = {"L": 34, "M": 28, "Q": 22, "H": 16}
        self.gf = GaloisField()  # Initialize Galois Field for Reed-Solomon
        self.enable_ec = enable_ec  # Enable or disable error correction

    def generate(self):
        """Generate QR code matrix"""
        # 1. Add finder patterns
        self._add_finder_patterns()

        # 2. Add alignment pattern
        self._add_alignment_pattern()

        # 3. Add timing patterns
        self._add_timing_patterns()

        # 4. Add format information area (reserved)
        self._add_format_info()

        # 5. Encode data
        data_bits = self._encode_data()

        print(f"Data bits: {data_bits}")

        # 6. Place data bits in matrix
        self._place_data(data_bits)

        # 7. Apply masking if specified
        if self.mask is not None:
            self._apply_mask(self.mask)

        # 8. Add format information
        self._add_real_format_info()

        return self.matrix

    def _add_finder_patterns(self):
        """Add the three finder patterns to the QR code matrix"""
        # Pattern for each finder pattern (7x7)
        pattern = [
            [1, 1, 1, 1, 1, 1, 1],
            [1, 0, 0, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 0, 1],
            [1, 0, 1, 1, 1, 0, 1],
            [1, 0, 1, 1, 1, 0, 1],
            [1, 0, 0, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1],
        ]

        # Top-left finder pattern
        for i in range(7):
            for j in range(7):
                self.matrix[i][j] = pattern[i][j]

        # Top-right finder pattern
        for i in range(7):
            for j in range(self.size - 7, self.size):
                self.matrix[i][j] = pattern[i][j - (self.size - 7)]

        # Bottom-left finder pattern
        for i in range(self.size - 7, self.size):
            for j in range(7):
                self.matrix[i][j] = pattern[i - (self.size - 7)][j]

        # Add separator (white border)
        for i in range(8):
            # Top-left separators
            self.matrix[i][7] = 0
            self.matrix[7][i] = 0

            # Top-right separators
            self.matrix[i][self.size - 8] = 0

            # Bottom-left separators
            if i > 0:  # Avoid overwriting top-left
                self.matrix[self.size - i][7] = 0
                self.matrix[self.size - 8][i] = 0

    def _add_alignment_pattern(self):
        """Add alignment pattern for version 2 QR code"""
        # Position for version 2 is at (18, 18)
        pattern = [
            [1, 1, 1, 1, 1],
            [1, 0, 0, 0, 1],
            [1, 0, 1, 0, 1],
            [1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1],
        ]

        row, col = 16, 16  # Alignment pattern position for version 2

        for i in range(5):
            for j in range(5):
                self.matrix[row + i][col + j] = pattern[i][j]

    def _add_timing_patterns(self):
        """Add horizontal and vertical timing patterns"""
        # Horizontal timing pattern
        for i in range(8, self.size - 8):
            self.matrix[6][i] = 1 if i % 2 == 0 else 0

        # Vertical timing pattern
        for i in range(8, self.size - 8):
            self.matrix[i][6] = 1 if i % 2 == 0 else 0

    def _add_format_info(self):
        """Reserve space for format information"""
        # Around top-left finder pattern
        for i in range(9):
            if i != 6:  # Skip timing pattern
                self.matrix[i][8] = -1

        for i in range(8):
            if i != 6:  # Skip timing pattern
                self.matrix[8][i] = -1

        # Around top-right finder pattern and bottom-left finder pattern
        for i in range(8):
            self.matrix[8][self.size - i - 1] = -1
            self.matrix[self.size - i - 1][8] = -1

        # Dark module
        self.matrix[self.size - 8][8] = 1

    def _reed_solomon_encode(self, data_codewords, ec_count):
        """Generate Reed-Solomon error correction codewords"""
        # Generator polynomials for different error correction levels
        # Maps number of error correction codewords to generator polynomial coefficients
        generator_polynomials = {
            7: [1, 127, 122, 154, 164, 11, 68, 117],
            10: [1, 216, 194, 159, 111, 199, 94, 95, 113, 157, 193],
            13: [1, 137, 73, 227, 17, 177, 17, 52, 13, 46, 43, 83, 132, 120],
            15: [1, 29, 196, 111, 163, 112, 74, 10, 105, 103, 104, 101, 108, 200, 107, 96],
            16: [1, 59, 13, 104, 189, 68, 209, 30, 8, 163, 65, 41, 229, 98, 50, 36, 59],
            17: [1, 119, 66, 83, 120, 119, 22, 197, 83, 249, 41, 143, 134, 85, 53, 125, 99, 79],
            18: [1, 239, 251, 183, 113, 149, 175, 199, 215, 240, 220, 73, 82, 173, 75, 32, 67, 217, 146],
            20: [1, 152, 185, 240, 5, 111, 99, 6, 220, 112, 150, 69, 36, 187, 22, 228, 198, 121, 121, 165, 174],
            22: [1, 89, 179, 131, 176, 182, 244, 19, 189, 69, 40, 28, 137, 29, 123, 67, 253, 86, 218, 230, 26, 145, 245],
            24: [1, 122, 118, 169, 70, 178, 237, 216, 102, 115, 150, 229, 73, 130, 72, 61, 43, 206, 1, 237, 247, 127, 217, 144, 117],
            26: [1, 246, 51, 183, 4, 136, 98, 199, 152, 77, 56, 206, 24, 145, 40, 209, 117, 233, 42, 135, 68, 70, 144, 146, 77, 43, 94],
            28: [1, 252, 9, 28, 13, 18, 251, 208, 150, 103, 174, 100, 41, 167, 12, 247, 56, 117, 119, 233, 127, 181, 100, 121, 147, 176, 74, 58, 197],
            30: [1, 212, 246, 77, 73, 195, 192, 75, 98, 5, 70, 103, 177, 22, 217, 138, 51, 181, 246, 72, 25, 18, 46, 228, 74, 216, 195, 11, 106, 130, 150]
        }

        # Get the generator polynomial for the specified number of EC codewords
        generator = generator_polynomials.get(ec_count)
        if not generator:
            raise ValueError(f"No generator polynomial available for {ec_count} error correction codewords")

        # Initialize the message polynomial
        message_polynomial = data_codewords + [0] * ec_count
        
        # Perform polynomial division
        for i in range(len(data_codewords)):
            if message_polynomial[i] != 0:
                lead_term = self.gf.log[message_polynomial[i]]
                for j in range(len(generator)):
                    if generator[j] != 0:
                        message_polynomial[i + j] ^= self.gf.exp[(self.gf.log[generator[j]] + lead_term) % 255]

        # Return only the error correction part
        return message_polynomial[len(data_codewords):]

    def _encode_data(self):
        """Encode data in byte mode and add Reed-Solomon error correction"""
        # Convert string to bytes
        data_bytes = self.data.encode("ascii")
        data_length = len(data_bytes)

        # Check if data fits
        if data_length > self.data_capacity[self.error_correction]:
            raise ValueError(
                f"Data too long for version 2 QR code with {self.error_correction} error correction"
            )

        # 1. Create the data codewords
        
        # Start with byte mode indicator (0100) and length
        bit_stream = "0100"  # Mode indicator for byte mode
        
        # For version 2, length is 8 bits
        bit_stream += format(data_length, "08b")
        
        # Add data bytes
        for byte in data_bytes:
            bit_stream += format(byte, "08b")
            
        # Calculate required data bits for this version and EC level
        data_codeword_count = self.data_capacity[self.error_correction] - self.ec_codewords[self.error_correction]
        data_bits_needed = 8 * data_codeword_count
        
        # Add terminator if needed (up to 4 bits)
        terminator_length = min(4, data_bits_needed - len(bit_stream))
        bit_stream += "0" * terminator_length
        
        # Pad to byte boundary
        while len(bit_stream) % 8 != 0:
            bit_stream += "0"
            
        # Add pad bytes until required data length
        pad_bytes = ["11101100", "00010001"]  # Alternating padding bytes
        pad_index = 0
        
        while len(bit_stream) < data_bits_needed:
            bit_stream += pad_bytes[pad_index]
            pad_index = (pad_index + 1) % 2
            
        # Convert bit stream to codewords (bytes)
        data_codewords = []
        for i in range(0, len(bit_stream), 8):
            byte_str = bit_stream[i:i+8]
            data_codewords.append(int(byte_str, 2))
            
        print(f"Data codewords: {data_codewords}")
        
        # 2. Generate error correction codewords using Reed-Solomon or zeros
        ec_count = self.ec_codewords[self.error_correction]
        
        # Initialize ec_codewords before conditional block
        if self.enable_ec:
            # Use Reed-Solomon error correction
            ec_codewords = self._reed_solomon_encode(data_codewords, ec_count)
            print(f"EC codewords: {ec_codewords} (Reed-Solomon)")
        else:
            # Use zeros for error correction bits (educational purpose only)
            ec_codewords = [0] * ec_count
            print(f