import numpy as np
from PIL import Image

def get_H():
    img = Image.open("output2g.png").convert("L")
    P = (np.array(img) < 128).astype(np.uint8)
    PT = P.T # 2048 x 16384
    I = np.eye(2048, dtype=np.uint8)
    H = np.hstack((PT, I)) # 2048 x 18432
    return H

def find_sparse_rows(H):
    # Try to find sparse linear combinations by Gaussian elimination
    m, n = H.shape
    A = H.copy()
    
    # Standard GF2 RREF
    rank = 0
    for j in range(n):
        if rank >= m: break
        pivot = -1
        for i in range(rank, m):
            if A[i, j] == 1:
                pivot = i
                break
        if pivot != -1:
            A[[rank, pivot]] = A[[pivot, rank]]
            for i in range(m):
                if i != rank and A[i, j] == 1:
                    A[i] ^= A[rank]
            rank += 1
            
            # Every 100 steps, check if any row is sparse
            if rank % 100 == 0:
                weights = np.sum(A, axis=1)
                min_w = np.min(weights[weights > 0])
                if min_w < 50:
                    print(f"Found sparse row! Weight {min_w} at rank {rank}")
                    return True
    
    weights = np.sum(A, axis=1)
    min_w = np.min(weights[weights > 0])
    print(f"Minimum row weight after RREF: {min_w}")
    return False

def main():
    print("Investigating if the code has a sparse Parity Check Matrix...")
    H = get_H()
    find_sparse_rows(H)

if __name__ == "__main__":
    main()
