Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
75.00% covered (warning)
75.00%
15 / 20
0.00% covered (danger)
0.00%
0 / 3
 CRAP
0.00% covered (danger)
0.00%
0 / 1
ScrambleMapping
75.00% covered (warning)
75.00%
15 / 20
0.00% covered (danger)
0.00%
0 / 3
 12.89
0.00% covered (danger)
0.00%
0 / 1
 __construct
80.00% covered (warning)
80.00%
4 / 5
0.00% covered (danger)
0.00%
0 / 1
 3.07
 getSerialIdForIndex
90.00% covered (success)
90.00%
9 / 10
0.00% covered (danger)
0.00%
0 / 1
 5.03
 powmod
40.00% covered (danger)
40.00%
2 / 5
0.00% covered (danger)
0.00%
0 / 1
 4.94
1<?php
2
3namespace MediaWiki\User\TempUser;
4
5use LogicException;
6use OutOfBoundsException;
7use RuntimeException;
8
9/**
10 * A mapping which converts sequential input into an output sequence that looks
11 * pseudo-random, but preserves the base-10 length of the input number.
12 *
13 * Take a sequence generated by multiplying the previous element of the
14 * sequence by a fixed number "g", then applying the modulus "p":
15 *
16 *   X(0) = 1
17 *   X(i) = ( g X(i-1) ) mod p
18 *
19 * If g is a primitive root modulo p, then this sequence will cover all values
20 * from 1 to p-1 before it repeats. X(i) is a modular exponential function
21 * (g^i mod p) and algorithms are available to calculate it efficiently.
22 *
23 * Loosely speaking, we choose a sequence based on the number of digits N in the
24 * input, with the period being approximately 10^N, so that the number of digits
25 * in the output will be approximately the same.
26 *
27 * More precisely, after offsetting the subsequent sequences to avoid colliding
28 * with the previous sequences, the period ends up being about 0.9 * 10^N
29 *
30 * The modulo p is always a prime number because that makes the maths easier.
31 * We use a value for g close to p/sqrt(3) since that seems to stir the digits
32 * better than the largest or smallest primitive root.
33 *
34 * @internal
35 */
36class ScrambleMapping implements SerialMapping {
37    /**
38     * Appropriately sized prime moduli and primitive roots. Generated with
39     * this GP/PARI script:
40     * s=0; \
41     * for(q = 2, 10, \
42     *   p=precprime(10^q - s); \
43     *   s = s + p; \
44     *   forstep(i = floor(p/sqrt(3)), 1, -1, \
45     *     if(znorder(Mod(i, p)) == p-1, \
46     *     print("[ ", i, ", ", p, " ],"); \
47     *     break )))
48     */
49    private const GENERATORS = [
50        [ 56, 97 ],
51        [ 511, 887 ],
52        [ 5203, 9013 ],
53        [ 51947, 90001 ],
54        [ 519612, 900001 ],
55        [ 5196144, 8999993 ],
56        [ 51961523, 89999999 ],
57        [ 519615218, 899999963 ],
58        [ 5196152444, 9000000043 ],
59    ];
60
61    /** @var int */
62    private $offset;
63
64    /** @var bool */
65    private $hasGmp;
66    /** @var bool */
67    private $hasBcm;
68
69    public function __construct( array $config ) {
70        $this->offset = $config['offset'] ?? 0;
71        $this->hasGmp = extension_loaded( 'gmp' );
72        $this->hasBcm = extension_loaded( 'bcmath' );
73        if ( !$this->hasGmp && !$this->hasBcm ) {
74            throw new RuntimeException( __CLASS__ . ' requires the bcmath or gmp extension' );
75        }
76    }
77
78    public function getSerialIdForIndex( int $index ): string {
79        if ( $index <= 0 ) {
80            return (string)$index;
81        }
82        $offset = $this->offset;
83        if ( $index - $offset < 0 ) {
84            throw new OutOfBoundsException( __METHOD__ . ": The configured offset $offset is too large." );
85        }
86        foreach ( self::GENERATORS as [ $g, $p ] ) {
87            if ( $index - $offset < $p ) {
88                return (string)( $offset + $this->powmod( $g, $index - $offset, $p ) );
89            }
90            $offset += $p - 1;
91        }
92        throw new RuntimeException( __METHOD__ . ": The index $index is too large" );
93    }
94
95    private function powmod( int $num, int $exponent, int $modulus ): int {
96        if ( $this->hasGmp ) {
97            return \gmp_intval( \gmp_powm( $num, $exponent, $modulus ) );
98        } elseif ( $this->hasBcm ) {
99            return (int)\bcpowmod( (string)$num, (string)$exponent, (string)$modulus );
100        } else {
101            throw new LogicException( __CLASS__ . ' requires the bcmath or gmp extension' );
102        }
103    }
104}