#ifndef BROMBERG_SL2_HASH_MATRIX_H
#define BROMBERG_SL2_HASH_MATRIX_H

#include <stdint.h>
#include <stdbool.h>

// 128-bit unsigned integer for intermediate calculations
typedef __uint128_t uint128_t;

// 2x2 matrix over F_p where p = 2^63 - 1
// Layout: [[m[0], m[1]], [m[2], m[3]]]
typedef struct {
    uint64_t m[4];
} hash_matrix_t;

// Prime p = 2^63 - 1 (Mersenne prime)
#define P (((uint64_t)1 << 63) - 1)

// Generator matrices and identity
extern const hash_matrix_t MATRIX_I;  // Identity
extern const hash_matrix_t MATRIX_A;  // [[1,2],[0,1]]
extern const hash_matrix_t MATRIX_B;  // [[1,0],[2,1]]

// 64-bit multiplication: x * y -> 128-bit result
uint128_t mul_u64(uint64_t x, uint64_t y);

// 128-bit addition
uint128_t add_u128(uint128_t x, uint128_t y);

// Modular reduction mod p = 2^63 - 1
uint64_t mod_p(uint128_t n);

// Matrix multiplication mod p
hash_matrix_t matmul(hash_matrix_t a, hash_matrix_t b);

// Compare two matrices for equality
bool hash_matrix_eq(const hash_matrix_t* a, const hash_matrix_t* b);

#endif
