import numpy as np
from PIL import Image

def get_G():
    img = Image.open("output2g.png").convert("L")
    P = (np.array(img) < 128).astype(np.uint8)
    # G = [I | P]
    return P

def find_sparse_h(P):
    # Null space of G = [I | P] is spanned by rows of H = [P^T | I]
    # We want to find sparse linear combinations of rows of H.
    # Each row of H is [Column_j_of_P^T | Unit_vector_j]
    # But wait, P is 16384 x 2048.
    # P^T is 2048 x 16384.
    # H = [P^T | I_2048].
    # H has 2048 rows. Length 18432.
    
    # We use a randomized algorithm to find sparse rows (similar to Lee-Brickell or ISD).
    # But for LDPC, Gaussian elimination usually reveals them if they are in the basis.
    # We already tried RREF and it gave weight 512.
    
    # Wait! If the code is QC-LDPC, then H is also QC.
    # H = [H_1, H_2, ..., H_72] where each H_i is 256x256 circulant.
    # And there should be a VERY sparse row in H.
    
    # Let's check the row weight of G again.
    # Row weight 1022.
    # If G [H1 | H2 | ... | H72]^T = 0
    # Then sum d_i H_i^T = 0.
    
    # Actually, I'll try to find if any column of P has a sparse relationship with other columns.
    # If P = H2^-1 H1, then H2 P = H1.
    # If H1 and H2 are sparse, then H2 P - H1 = 0.
    # This means some sparse combination of rows of P is sparse!
    
    print("Searching for sparse linear combinations of rows of P...")
    m, n = P.shape # 16384 x 2048
    
    # Try XORing rows within a block
    for b in range(64):
        block_rows = P[b*256 : (b+1)*256]
        # Check if any two rows in a block XOR to something sparse
        for i in range(10):
            for j in range(i+1, 10):
                w = np.sum(block_rows[i] ^ block_rows[j])
                if w < 100:
                    print(f"Found sparse row diff in block {b}: weight {w}")
    
    # Try XORing rows across blocks
    for i in range(10):
        for j in range(i+1, 10):
            w = np.sum(P[i*256] ^ P[j*256])
            if w < 100:
                print(f"Found sparse row diff across blocks {i},{j}: weight {w}")

    print("No immediate sparse rows found by simple XOR.")

if __name__ == "__main__":
    P = get_G()
    find_sparse_h(P)
