1use num_integer::Roots;
2
3#[derive(Debug)]
4pub enum PairingError {
5 Overflow,
6}
7
8pub fn compute_cantor_pair(l: u64, r: u64) -> Result<u64, PairingError> {
9 let sum = l.checked_add(r).ok_or(PairingError::Overflow)?;
10 let product = sum.checked_mul(sum + 1).ok_or(PairingError::Overflow)?;
11 let half = product.checked_div(2).ok_or(PairingError::Overflow)?;
12 half.checked_add(r).ok_or(PairingError::Overflow)
13}
14
15pub fn compute_cantor_unpair(p: u64) -> Result<(u64, u64), PairingError> {
16 let w = ((8 * p + 1).sqrt() - 1) / 2;
17 let t = (w * (w + 1)) / 2;
18 let r = p - t;
19 let l = w - r;
20 Ok((l, r))
21}
22
23pub fn compute_peter_pair(l: u64, r: u64) -> Result<u64, PairingError> {
24 let (shell, step) = if l > r { (l, r) } else { (r, l) };
25 let flag = if step == r { 0 } else { 1 };
26 let shell_squared = shell.checked_mul(shell).ok_or(PairingError::Overflow)?;
27 let step_doubled = step.checked_mul(2).ok_or(PairingError::Overflow)?;
28 shell_squared
29 .checked_add(step_doubled)
30 .and_then(|v| v.checked_add(flag))
31 .ok_or(PairingError::Overflow)
32}
33
34pub fn compute_peter_unpair(p: u64) -> Result<(u64, u64), PairingError> {
35 let shell = p.sqrt();
36 let step = (p - shell.pow(2)) / 2;
37 if p % 2 == 0 {
38 Ok((shell, step))
39 } else {
40 Ok((step, shell))
41 }
42}
43
44pub fn compute_rosenberg_strong_pair(l: u64, r: u64) -> Result<u64, PairingError> {
45 let shell = l.max(r);
46 let shell_squared = shell.checked_mul(shell).ok_or(PairingError::Overflow)?;
47 shell_squared
48 .checked_add(shell)
49 .and_then(|v| v.checked_add(l))
50 .and_then(|v| v.checked_sub(r))
51 .ok_or(PairingError::Overflow)
52}
53
54pub fn compute_rosenberg_strong_unpair(p: u64) -> Result<(u64, u64), PairingError> {
55 let shell = p.sqrt();
56 let step = p - shell.pow(2);
57 if step < shell {
58 Ok((step, shell))
59 } else {
60 Ok((shell, 2 * shell - step))
61 }
62}
63
64pub fn compute_szudzik_pair(l: u64, r: u64) -> Result<u64, PairingError> {
65 if l != l.max(r) {
66 let r_squared = r.checked_mul(r).ok_or(PairingError::Overflow)?;
67 r_squared.checked_add(l).ok_or(PairingError::Overflow)
68 } else {
69 let l_squared = l.checked_mul(l).ok_or(PairingError::Overflow)?;
70 l_squared
71 .checked_add(l)
72 .and_then(|v| v.checked_add(r))
73 .ok_or(PairingError::Overflow)
74 }
75}
76
77pub fn compute_szudzik_unpair(p: u64) -> Result<(u64, u64), PairingError> {
78 let sqrt_p = p.sqrt();
79 if p - sqrt_p.pow(2) < sqrt_p {
80 Ok((p - sqrt_p.pow(2), sqrt_p))
81 } else {
82 Ok((sqrt_p, p - sqrt_p.pow(2) - sqrt_p))
83 }
84}
85
86pub fn compute_hagen_pair(l: u64, r: u64) -> Result<u64, PairingError> {
87 let (shell, step) = if l > r { (l, r) } else { (r, l) };
88 let flag = match (shell % 2, step) {
89 (0, s) if s == l => 0,
90 (1, s) if s == r => 0,
91 _ => 1,
92 };
93 let shell_squared = shell.checked_mul(shell).ok_or(PairingError::Overflow)?;
94 let step_doubled = step.checked_mul(2).ok_or(PairingError::Overflow)?;
95 shell_squared
96 .checked_add(step_doubled)
97 .and_then(|v| v.checked_add(flag))
98 .ok_or(PairingError::Overflow)
99}
100
101pub fn compute_hagen_unpair(p: u64) -> Result<(u64, u64), PairingError> {
102 let shell = p.sqrt();
103 let step = (p - shell.pow(2)) / 2;
104 if p % 2 == 0 {
105 Ok((step, shell))
106 } else {
107 Ok((shell, step))
108 }
109}
110
111#[cfg(test)]
112mod tests {
113 use super::*;
114
115 #[test]
116 fn test_cantor_pair() {
117 let pairs = vec![
118 (1958, 1962),
119 (1958, 1970),
120 (1958, 1994),
121 (1958, 2002),
122 (1962, 1970),
123 (1962, 1994),
124 (1962, 2002),
125 (1970, 1994),
126 (1970, 2002),
127 (1994, 2002),
128 ];
129 let expected = vec![
130 7687122, 7718526, 7813122, 7844782, 7734248, 7828940, 7860632, 7860624, 7892380,
131 7988008,
132 ];
133 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
134 let p = compute_cantor_pair(*l, *r).unwrap();
135 assert_eq!(p, *expected);
136 }
137 }
138
139 #[test]
140 fn test_cantor_unpair() {
141 let pairs = vec![
142 (1958, 1962),
143 (1958, 1970),
144 (1958, 1994),
145 (1958, 2002),
146 (1962, 1970),
147 (1962, 1994),
148 (1962, 2002),
149 (1970, 1994),
150 (1970, 2002),
151 (1994, 2002),
152 ];
153 let expected = vec![
154 7687122, 7718526, 7813122, 7844782, 7734248, 7828940, 7860632, 7860624, 7892380,
155 7988008,
156 ];
157 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
158 let (ul, ur) = compute_cantor_unpair(*expected).unwrap();
159 assert_eq!((*l, *r), (ul, ur));
160 }
161 }
162
163 #[test]
164 fn test_peter_pair() {
165 let pairs = vec![
166 (1958, 1962),
167 (1958, 1970),
168 (1958, 1994),
169 (1958, 2002),
170 (1962, 1970),
171 (1962, 1994),
172 (1962, 2002),
173 (1970, 1994),
174 (1970, 2002),
175 (1994, 2002),
176 ];
177 let expected = vec![
178 3853361, 3884817, 3979953, 4011921, 3884825, 3979961, 4011929, 3979977, 4011945,
179 4011993,
180 ];
181 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
182 let p = compute_peter_pair(*l, *r).unwrap();
183 assert_eq!(p, *expected);
184 }
185 }
186
187 #[test]
188 fn test_peter_unpair() {
189 let pairs = vec![
190 (1958, 1962),
191 (1958, 1970),
192 (1958, 1994),
193 (1958, 2002),
194 (1962, 1970),
195 (1962, 1994),
196 (1962, 2002),
197 (1970, 1994),
198 (1970, 2002),
199 (1994, 2002),
200 ];
201 let expected = vec![
202 3853361, 3884817, 3979953, 4011921, 3884825, 3979961, 4011929, 3979977, 4011945,
203 4011993,
204 ];
205 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
206 let (ul, ur) = compute_peter_unpair(*expected).unwrap();
207 assert_eq!((*l, *r), (ul, ur));
208 }
209 }
210
211 #[test]
212 fn test_rosenberg_strong_pair() {
213 let pairs = vec![
214 (1958, 1962),
215 (1958, 1970),
216 (1958, 1994),
217 (1958, 2002),
218 (1962, 1970),
219 (1962, 1994),
220 (1962, 2002),
221 (1970, 1994),
222 (1970, 2002),
223 (1994, 2002),
224 ];
225 let expected = vec![
226 3851402, 3882858, 3977994, 4009962, 3882862, 3977998, 4009966, 3978006, 4009974,
227 4009998,
228 ];
229 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
230 let p = compute_rosenberg_strong_pair(*l, *r).unwrap();
231 assert_eq!(p, *expected);
232 }
233 }
234
235 #[test]
236 fn test_rosenberg_strong_unpair() {
237 let pairs = vec![
238 (1958, 1962),
239 (1958, 1970),
240 (1958, 1994),
241 (1958, 2002),
242 (1962, 1970),
243 (1962, 1994),
244 (1962, 2002),
245 (1970, 1994),
246 (1970, 2002),
247 (1994, 2002),
248 ];
249 let expected = vec![
250 3851402, 3882858, 3977994, 4009962, 3882862, 3977998, 4009966, 3978006, 4009974,
251 4009998,
252 ];
253 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
254 let (ul, ur) = compute_rosenberg_strong_unpair(*expected).unwrap();
255 assert_eq!((*l, *r), (ul, ur));
256 }
257 }
258
259 #[test]
260 fn test_szudzik_pair() {
261 let pairs = vec![
262 (1958, 1962),
263 (1958, 1970),
264 (1958, 1994),
265 (1958, 2002),
266 (1962, 1970),
267 (1962, 1994),
268 (1962, 2002),
269 (1970, 1994),
270 (1970, 2002),
271 (1994, 2002),
272 ];
273 let expected = vec![
274 3851402, 3882858, 3977994, 4009962, 3882862, 3977998, 4009966, 3978006, 4009974,
275 4009998,
276 ];
277 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
278 let p = compute_szudzik_pair(*l, *r).unwrap();
279 assert_eq!(p, *expected);
280 }
281 }
282
283 #[test]
284 fn test_szudzik_unpair() {
285 let pairs = vec![
286 (1958, 1962),
287 (1958, 1970),
288 (1958, 1994),
289 (1958, 2002),
290 (1962, 1970),
291 (1962, 1994),
292 (1962, 2002),
293 (1970, 1994),
294 (1970, 2002),
295 (1994, 2002),
296 ];
297 let expected = vec![
298 3851402, 3882858, 3977994, 4009962, 3882862, 3977998, 4009966, 3978006, 4009974,
299 4009998,
300 ];
301 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
302 let (ul, ur) = compute_szudzik_unpair(*expected).unwrap();
303 assert_eq!((*l, *r), (ul, ur));
304 }
305 }
306
307 #[test]
308 fn test_hagen_pair() {
309 let pairs = vec![
310 (1958, 1962),
311 (1958, 1970),
312 (1958, 1994),
313 (1958, 2002),
314 (1962, 1970),
315 (1962, 1994),
316 (1962, 2002),
317 (1970, 1994),
318 (1970, 2002),
319 (1994, 2002),
320 ];
321 let expected = vec![
322 3853360, 3884816, 3979952, 4011920, 3884824, 3979960, 4011928, 3979976, 4011944,
323 4011992,
324 ];
325 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
326 let p = compute_hagen_pair(*l, *r).unwrap();
327 assert_eq!(p, *expected);
328 }
329 }
330
331 #[test]
332 fn test_hagen_unpair() {
333 let pairs = vec![
334 (1958, 1962),
335 (1958, 1970),
336 (1958, 1994),
337 (1958, 2002),
338 (1962, 1970),
339 (1962, 1994),
340 (1962, 2002),
341 (1970, 1994),
342 (1970, 2002),
343 (1994, 2002),
344 ];
345 let expected = vec![
346 3853360, 3884816, 3979952, 4011920, 3884824, 3979960, 4011928, 3979976, 4011944,
347 4011992,
348 ];
349 for ((l, r), expected) in pairs.iter().zip(expected.iter()) {
350 let (ul, ur) = compute_hagen_unpair(*expected).unwrap();
351 assert_eq!((*l, *r), (ul, ur));
352 }
353 }
354
355 #[test]
356 fn test_cantor_overflow() {
357 assert!(compute_cantor_pair(u64::MAX, u64::MAX).is_err());
358 }
359
360 #[test]
361 fn test_peter_overflow() {
362 assert!(compute_peter_pair(u64::MAX, u64::MAX).is_err());
363 }
364
365 #[test]
366 fn test_rosenberg_strong_overflow() {
367 assert!(compute_rosenberg_strong_pair(u64::MAX, u64::MAX).is_err());
368 }
369
370 #[test]
371 fn test_szudzik_overflow() {
372 assert!(compute_szudzik_pair(u64::MAX, u64::MAX).is_err());
373 }
374
375 #[test]
376 fn test_hagen_overflow() {
377 assert!(compute_hagen_pair(u64::MAX, u64::MAX).is_err());
378 }
379}