# ekaragoz77/polyinv architecture

> Architecture diagram of the GitHub repository ekaragoz77/polyinv, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-05-12). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/ekaragoz77/polyinv
- Repository: https://github.com/ekaragoz77/polyinv

## Overview

##### Project type and purpose
- This is an open-source C library plus a set of command-line benchmarking/testing tools for implementing and comparing constant-time polynomial inversion algorithms in GF(2)[x]/(x^r−1) for post-quantum cryptography.
- Core deliverables:
- A reusable library (“gf2x”) providing polynomial arithmetic (add, multiply, square, reduction, random generation, printing)
- Five inversion algorithm modules (BYI, FLT, CEA, TYT, SAC) each in its own .c file
- A benchmarking harness (bench.c/.h) to measure cycle-counts and function-call counts
- Three test programs (test_inv.c, test_count.c, test_speed.c) invoked by shell scripts for correctness, call-counting, and speed tests

##### File structure
- Top‐level build & metadata: Makefile, .gitignore, LICENSE, AUTHORS
- Configuration headers: config.h (build switches), params.h (predefined primes & EXTDEG macro)
- Library headers: gf2x.h (API), bench.h (benchmark API)
- Core arithmetic modules (gf2x_add.c, gf2x_mul.c, gf2x_sqr.c, gf2x_red.c, gf2x_base.c, bench.c)
- Inversion modules: gf2x_inv_byi.c, gf2x_inv_flt.c, gf2x_inv_cea.c, gf2x_inv_sac.c, gf2x_inv_tyt.c
- Utility / support: gf2x_print.c, gf2x_rand.c
- Test programs: test_inv.c, test_count.c, test_speed.c
- Runner scripts: run_test_inv.sh, run_test_count.sh, run_test_speed.sh

##### README for additional insights
- Describes each inversion algorithm’s underlying math (Extended Euclidean vs FLT variants)
- Explains the use of EXTDEG for polynomial degree and lists primes in params.h
- Documents how Makefile orchestrates compilation (GCC + -O3 + march=native)
- Clarifies that benchmark metrics include cycle-counts and # of low-level calls

##### Components
a. Core Library Layer (“gf2x”):
- Polynomial arithmetic sub-modules (add, mul, sqr, red, base)
- Utility sub-modules (rand, print)
b. Inversion Algorithm Layer:
- Five algorithm modules, each depending on the arithmetic API in gf2x.h
c. Benchmarking Layer:
- bench.c/.h providing timing (rdtsc) and function-call instrumentation
d. Test Harness Layer:
- test_inv (correctness), test_count (call counts), test_speed (performance)
- Each test program links against core library + bench harness + chosen inversion modules
e. Orchestration Layer:
- Shell scripts (run_test_*.sh) that invoke `make` and then run the corresponding test binary over all configured primes and EXTDEG values
f. Build & Config Layer:
- Makefile (compilation rules, dependency graph)
- config.h & params.h (macro flags, prime parameters)

##### Relationships and interactions
- Test scripts → call Test programs
- Test programs → link to and call:
- Benchmark harness (bench API) for timing/counters
- Inversion modules → which call core arithmetic APIs
- Core arithmetic modules → may call lower‐level base operations and utilities
- Makefile coordinates compiling all .c files into static library or object files, then linking tests

##### Architectural patterns & design principles
- Layered modular design: clear separation between (1) arithmetic kernel, (2) inversion strategies, (3) benchmarking instrumentation, (4) test drivers, (5) orchestration scripts
- Single-responsibility modules: each .c file implements one algorithm or one group of operations
- Extensibility point: new inversion algorithms or new primes can be added by creating a new .c file and updating params.h/scripts

##### Detailed capture of essential elements
- Every .c/.h module group is represented, or aggregate small utilities where appropriate
- Clearly separate compile-time configuration (Makefile, headers) from runtime flow (scripts → binaries → library calls)
- Avoid clutter by grouping related modules (e.g., all gf2x_*.c under “Core Arithmetic Library”) but keep algorithm modules separate

## Diagram (Mermaid)

```mermaid
graph TD
    %% Build & Configuration Layer
    subgraph "Build & Configuration" 
        MF["Makefile"] 
        CH["config.h"] 
        PH["params.h"] 
        RD["README.md"] 
        AU["AUTHORS"] 
        LI["LICENSE"] 
        GI[".gitignore"]
    end

    %% Core Library Layer
    subgraph "Core Library (gf2x)" 
        API["gf2x.h"]
        subgraph "Arithmetic Modules"
            ADD["gf2x_add.c"]
            MUL["gf2x_mul.c"]
            SQR["gf2x_sqr.c"]
            RED["gf2x_red.c"]
            BASE["gf2x_base.c"]
        end
        subgraph "Utilities"
            RAND["gf2x_rand.c"]
            PRINT["gf2x_print.c"]
        end
    end

    %% Inversion Algorithm Layer
    subgraph "Inversion Algorithms"
        BYI["gf2x_inv_byi.c"]
        FLT["gf2x_inv_flt.c"]
        CEA["gf2x_inv_cea.c"]
        SAC["gf2x_inv_sac.c"]
        TYT["gf2x_inv_tyt.c"]
    end

    %% Benchmarking Harness
    subgraph "Benchmarking Harness"
        BH["bench.h"]
        BC["bench.c"]
    end

    %% Test Harness Layer
    subgraph "Test Binaries"
        TI["test_inv.c"]
        TC["test_count.c"]
        TS["test_speed.c"]
    end

    %% Orchestration Layer
    subgraph "Orchestration Scripts"
        RINV["run_test_inv.sh"]
        RCOUNT["run_test_count.sh"]
        RSPEED["run_test_speed.sh"]
    end

    %% Relationships
    MF -->|includes config & params| CH
    MF -->|includes config & params| PH

    RINV -->|invoke| TI
    RCOUNT -->|invoke| TC
    RSPEED -->|invoke| TS

    TI -->|"uses bench API"| BH
    TC -->|"uses bench API"| BH
    TS -->|"uses bench API"| BH

    TI -->|"calls inversion"| BYI
    TI -->|"calls inversion"| FLT
    TI -->|"calls inversion"| CEA
    TI -->|"calls inversion"| SAC
    TI -->|"calls inversion"| TYT

    TC -->|"calls inversion"| BYI
    TC -->|"calls inversion"| FLT
    TC -->|"calls inversion"| CEA
    TC -->|"calls inversion"| SAC
    TC -->|"calls inversion"| TYT

    TS -->|"calls inversion"| BYI
    TS -->|"calls inversion"| FLT
    TS -->|"calls inversion"| CEA
    TS -->|"calls inversion"| SAC
    TS -->|"calls inversion"| TYT

    BYI -->|"calls API"| API
    FLT -->|"calls API"| API
    CEA -->|"calls API"| API
    SAC -->|"calls API"| API
    TYT -->|"calls API"| API

    API -->|"implements arithmetic"| ADD
    API -->|"implements arithmetic"| MUL
    API -->|"implements arithmetic"| SQR
    API -->|"implements arithmetic"| RED
    API -->|"implements arithmetic"| BASE

    ADD -->|"base ops"| BASE
    MUL -->|"base ops"| BASE
    SQR -->|"base ops"| BASE
    RED -->|"base ops"| BASE

    API -->|"provides utilities"| RAND
    API -->|"provides utilities"| PRINT

    BH -->|"instrumentation uses rdtsc"| BC

    %% Click Events
    click API "https://github.com/ekaragoz77/polyinv/blob/main/gf2x.h"
    click CH "https://github.com/ekaragoz77/polyinv/blob/main/config.h"
    click PH "https://github.com/ekaragoz77/polyinv/blob/main/params.h"
    click MF "https://github.com/ekaragoz77/polyinv/tree/main/Makefile"
    click ADD "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_add.c"
    click MUL "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_mul.c"
    click SQR "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_sqr.c"
    click RED "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_red.c"
    click BASE "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_base.c"
    click RAND "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_rand.c"
    click PRINT "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_print.c"
    click BYI "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_inv_byi.c"
    click FLT "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_inv_flt.c"
    click CEA "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_inv_cea.c"
    click SAC "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_inv_sac.c"
    click TYT "https://github.com/ekaragoz77/polyinv/blob/main/gf2x_inv_tyt.c"
    click BH "https://github.com/ekaragoz77/polyinv/blob/main/bench.h"
    click BC "https://github.com/ekaragoz77/polyinv/blob/main/bench.c"
    click TI "https://github.com/ekaragoz77/polyinv/blob/main/test_inv.c"
    click TC "https://github.com/ekaragoz77/polyinv/blob/main/test_count.c"
    click TS "https://github.com/ekaragoz77/polyinv/blob/main/test_speed.c"
    click RINV "https://github.com/ekaragoz77/polyinv/blob/main/run_test_inv.sh"
    click RCOUNT "https://github.com/ekaragoz77/polyinv/blob/main/run_test_count.sh"
    click RSPEED "https://github.com/ekaragoz77/polyinv/blob/main/run_test_speed.sh"
    click RD "https://github.com/ekaragoz77/polyinv/blob/main/README.md"
    click AU "https://github.com/ekaragoz77/polyinv/tree/main/AUTHORS"
    click LI "https://github.com/ekaragoz77/polyinv/tree/main/LICENSE"
    click GI "https://github.com/ekaragoz77/polyinv/blob/main/.gitignore"

    %% Styles
    classDef build fill:#cccccc,stroke:#333,stroke-width:1px
    classDef core fill:#a8d0e6,stroke:#333,stroke-width:1px
    classDef inv fill:#a8e6a1,stroke:#333,stroke-width:1px
    classDef bench fill:#ffe156,stroke:#333,stroke-width:1px
    classDef test fill:#ffad69,stroke:#333,stroke-width:1px

    class MF,CH,PH,RD,AU,LI,GI build
    class API,ADD,MUL,SQR,RED,BASE,RAND,PRINT core
    class BYI,FLT,CEA,SAC,TYT inv
    class BH,BC bench
    class TI,TC,TS test
```
