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
|
<?php
namespace MediaWiki\User\TempUser;
use LogicException;
use OutOfBoundsException;
use RuntimeException;
/**
* A mapping which converts sequential input into an output sequence that looks
* pseudo-random, but preserves the base-10 length of the input number.
*
* Take a sequence generated by multiplying the previous element of the
* sequence by a fixed number "g", then applying the modulus "p":
*
* X(0) = 1
* X(i) = ( g X(i-1) ) mod p
*
* If g is a primitive root modulo p, then this sequence will cover all values
* from 1 to p-1 before it repeats. X(i) is a modular exponential function
* (g^i mod p) and algorithms are available to calculate it efficiently.
*
* Loosely speaking, we choose a sequence based on the number of digits N in the
* input, with the period being approximately 10^N, so that the number of digits
* in the output will be approximately the same.
*
* More precisely, after offsetting the subsequent sequences to avoid colliding
* with the previous sequences, the period ends up being about 0.9 * 10^N
*
* The modulo p is always a prime number because that makes the maths easier.
* We use a value for g close to p/sqrt(3) since that seems to stir the digits
* better than the largest or smallest primitive root.
*
* @internal
*/
class ScrambleMapping implements SerialMapping {
/**
* Appropriately sized prime moduli and primitive roots. Generated with
* this GP/PARI script:
* s=0; \
* for(q = 2, 10, \
* p=precprime(10^q - s); \
* s = s + p; \
* forstep(i = floor(p/sqrt(3)), 1, -1, \
* if(znorder(Mod(i, p)) == p-1, \
* print("[ ", i, ", ", p, " ],"); \
* break )))
*/
private const GENERATORS = [
[ 56, 97 ],
[ 511, 887 ],
[ 5203, 9013 ],
[ 51947, 90001 ],
[ 519612, 900001 ],
[ 5196144, 8999993 ],
[ 51961523, 89999999 ],
[ 519615218, 899999963 ],
[ 5196152444, 9000000043 ],
];
/** @var int */
private $offset;
/** @var bool */
private $hasGmp;
/** @var bool */
private $hasBcm;
public function __construct( $config ) {
$this->offset = $config['offset'] ?? 0;
$this->hasGmp = extension_loaded( 'gmp' );
$this->hasBcm = extension_loaded( 'bcmath' );
if ( !$this->hasGmp && !$this->hasBcm ) {
throw new RuntimeException( __CLASS__ . ' requires the bcmath or gmp extension' );
}
}
public function getSerialIdForIndex( int $index ): string {
if ( $index <= 0 ) {
return (string)$index;
}
$offset = $this->offset;
if ( $index - $offset < 0 ) {
throw new OutOfBoundsException( __METHOD__ . ": The configured offset $offset is too large." );
}
foreach ( self::GENERATORS as [ $g, $p ] ) {
if ( $index - $offset < $p ) {
return (string)( $offset + $this->powmod( $g, $index - $offset, $p ) );
}
$offset += $p - 1;
}
throw new RuntimeException( __METHOD__ . ": The index $index is too large" );
}
private function powmod( int $num, int $exponent, int $modulus ): int {
if ( $this->hasGmp ) {
return \gmp_intval( \gmp_powm( $num, $exponent, $modulus ) );
} elseif ( $this->hasBcm ) {
return (int)\bcpowmod( (string)$num, (string)$exponent, (string)$modulus );
} else {
throw new LogicException( __CLASS__ . ' requires the bcmath or gmp extension' );
}
}
}
|
