rusqsieve 0.2.1

High-performance SIQS integer factorization for native Rust and WebAssembly
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

//! Deterministic bounded work packets shared by all schedulers.
use crate::f2::{MatrixOperation, SparseBinaryMatrix};
use crate::qs::{RawRelation, SieveContext, SieveScratch};
use core::fmt;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct JobHeader {
    pub job_id: u64,
    pub generation: u64,
    pub context_id: u64,
}
#[derive(Clone, Debug)]
pub enum WorkJob {
    Sieve(SieveJob),
    MatrixMultiply(MatrixMultiplyJob),
}
#[derive(Clone, Debug)]
pub struct SieveJob {
    pub header: JobHeader,
    pub family: u64,
    pub first_polynomial: u32,
    pub polynomial_count: u32,
}
#[derive(Clone, Debug)]
pub struct MatrixMultiplyJob {
    pub header: JobHeader,
    pub operation: MatrixOperation,
    pub output_start: u32,
    pub output_end: u32,
    pub input: Box<[u64]>,
}
#[derive(Debug)]
pub enum WorkResult<const P: usize = 16> {
    Sieve(SieveResult<P>),
    MatrixMultiply(MatrixMultiplyResult),
    Failed(WorkFailure),
}
#[derive(Clone, Debug)]
pub struct WorkFailure {
    pub header: JobHeader,
    pub message: String,
}
#[derive(Clone, Copy, Debug, Default)]
pub struct SieveJobMetrics {
    pub polynomial_families: u64,
    pub polynomials: u64,
    pub sieve_positions: u64,
    pub candidates_tested: u64,
    pub full_relations: u64,
    pub single_large_prime_relations: u64,
    pub double_large_prime_relations: u64,
}
#[derive(Debug)]
pub struct SieveResult<const P: usize = 16> {
    pub header: JobHeader,
    pub relations: Vec<RawRelation<P>>,
    pub metrics: SieveJobMetrics,
}
#[derive(Clone, Copy, Debug, Default)]
pub struct MatrixJobMetrics {
    pub output_items: u64,
    pub nonzeros_visited: u64,
}
#[derive(Debug)]
pub struct MatrixMultiplyResult {
    pub header: JobHeader,
    pub output_start: u32,
    pub words: Box<[u64]>,
    pub metrics: MatrixJobMetrics,
}
#[derive(Default)]
pub struct MatrixScratch {
    pub words: Vec<u64>,
}
#[derive(Default)]
pub struct ArithmeticScratch {
    pub words: Vec<u64>,
}
#[derive(Default)]
pub struct WorkerScratch {
    pub sieve: SieveScratch,
    pub matrix: MatrixScratch,
    pub arithmetic: ArithmeticScratch,
}
pub struct KernelContexts<const P: usize> {
    pub sieve: Option<SieveContext<P>>,
    pub matrix: Option<SparseBinaryMatrix>,
}
impl<const P: usize> Default for KernelContexts<P> {
    fn default() -> Self {
        Self {
            sieve: None,
            matrix: None,
        }
    }
}
#[derive(Clone, Debug)]
pub enum KernelError {
    MissingContext,
    ContextMismatch,
    Range,
    Worker(String),
}
impl fmt::Display for KernelError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "worker kernel error: {self:?}")
    }
}
impl std::error::Error for KernelError {}
pub fn execute_job<const P: usize>(
    contexts: &KernelContexts<P>,
    job: WorkJob,
    scratch: &mut WorkerScratch,
) -> Result<WorkResult<P>, KernelError> {
    match job {
        WorkJob::Sieve(job) => {
            let ctx = contexts.sieve.as_ref().ok_or(KernelError::MissingContext)?;
            if job.header.context_id != ctx.context_id() {
                return Err(KernelError::ContextMismatch);
            }
            Ok(WorkResult::Sieve(crate::qs::sieve_job(
                ctx,
                &job,
                &mut scratch.sieve,
            )))
        }
        WorkJob::MatrixMultiply(job) => {
            let matrix = contexts
                .matrix
                .as_ref()
                .ok_or(KernelError::MissingContext)?;
            let start = job.output_start as usize;
            let end = job.output_end as usize;
            if start > end {
                return Err(KernelError::Range);
            }
            let mut words = vec![0; end - start];
            match job.operation {
                MatrixOperation::Matrix => matrix.mul_m_rows(&job.input, start..end, &mut words),
                MatrixOperation::Transpose => {
                    matrix.mul_mt_columns(&job.input, start..end, &mut words)
                }
            }
            Ok(WorkResult::MatrixMultiply(MatrixMultiplyResult {
                header: job.header,
                output_start: job.output_start,
                words: words.into_boxed_slice(),
                metrics: MatrixJobMetrics {
                    output_items: (end - start) as u64,
                    nonzeros_visited: 0,
                },
            }))
        }
    }
}