js_randomness_predictor/
chrome_predictor.rs

1use crate::{Predictor, errors::InitError};
2use std::error::Error;
3use z3::{self, Config, Context, SatResult, Solver, ast::*};
4
5pub struct ChromePredictor {
6  sequence: Vec<f64>,
7  internal_sequence: Vec<f64>,
8  is_solved: bool,
9  conc_state_0: u64,
10  conc_state_1: u64,
11}
12
13impl Predictor for ChromePredictor {
14  fn predict_next(&mut self) -> Result<f64, Box<dyn Error>> {
15    self.solve_symbolic_state()?; // if solving fails, error is returned early
16    let v = self.xor_shift_128_plus_concrete();
17    return Ok(self.to_double(v));
18  }
19}
20
21impl ChromePredictor {
22  const SS_0_STR: &str = "sym_state_0";
23  const SS_1_STR: &str = "sym_state_1";
24
25  pub fn new(seq: Vec<f64>) -> Self {
26    let mut iseq = seq.clone();
27    iseq.reverse();
28
29    return ChromePredictor {
30      internal_sequence: iseq,
31      sequence: seq,
32      is_solved: false,
33      conc_state_0: 0,
34      conc_state_1: 0,
35    };
36  }
37
38  #[allow(dead_code)]
39  pub fn sequence(&self) -> &[f64] {
40    return &self.sequence;
41  }
42
43  // So consumers don't have to import the Predictor trait as well as the struct.
44  pub fn predict_next(&mut self) -> Result<f64, Box<dyn Error>> {
45    return <Self as Predictor>::predict_next(self);
46  }
47
48  // Performs XORShift in reverse.
49  fn xor_shift_128_plus_concrete(&mut self) -> u64 {
50    let result = self.conc_state_0;
51    let temp1 = self.conc_state_0;
52    let mut temp0 = self.conc_state_1 ^ (self.conc_state_0 >> 26);
53    temp0 ^= self.conc_state_0;
54    temp0 ^= (temp0 >> 17) ^ (temp0 >> 34) ^ (temp0 >> 51);
55    temp0 ^= (temp0 << 23) ^ (temp0 << 46);
56    self.conc_state_0 = temp0;
57    self.conc_state_1 = temp1;
58    return result;
59  }
60
61  fn to_double(&self, value: u64) -> f64 {
62    return (value >> 11) as f64 / (1u64 << 53) as f64;
63  }
64
65  fn solve_symbolic_state(&mut self) -> Result<(), InitError> {
66    if self.is_solved {
67      return Ok(());
68    }
69
70    let config = Config::new();
71    let context = Context::new(&config);
72    let solver = Solver::new(&context);
73
74    let mut sym_state_0 = BV::new_const(&context, Self::SS_0_STR, 64);
75    let mut sym_state_1 = BV::new_const(&context, Self::SS_1_STR, 64);
76
77    for &observed in &self.internal_sequence {
78      Self::xor_shift_128_plus_symbolic(&context, &mut sym_state_0, &mut sym_state_1);
79      Self::constrain_mantissa(observed, &context, &solver, &sym_state_0);
80    }
81
82    if solver.check() != SatResult::Sat {
83      return Err(InitError::Unsat);
84    }
85
86    let model = solver.get_model().ok_or(InitError::MissingModel)?;
87
88    self.conc_state_0 = model
89      .eval(&sym_state_0, true)
90      .ok_or(InitError::EvalFailed(Self::SS_0_STR))?
91      .as_u64()
92      .ok_or(InitError::ConvertFailed(Self::SS_0_STR))?;
93
94    self.conc_state_1 = model
95      .eval(&sym_state_1, true)
96      .ok_or(InitError::EvalFailed(Self::SS_1_STR))?
97      .as_u64()
98      .ok_or(InitError::ConvertFailed(Self::SS_1_STR))?;
99
100    for _ in 0..self.internal_sequence.len() {
101      self.xor_shift_128_plus_concrete();
102    }
103
104    self.is_solved = true;
105    return Ok(());
106  }
107
108  // Static 'helper' method
109  fn xor_shift_128_plus_symbolic<'a>(
110    context: &'a Context,
111    state_0: &mut BV<'a>,
112    state_1: &mut BV<'a>,
113  ) {
114    let state_0_shifted_left = state_0.bvshl(&BV::from_u64(context, 23, 64));
115    let mut s1 = &*state_0 ^ state_0_shifted_left;
116    let s1_shifted_right = s1.bvlshr(&BV::from_u64(context, 17, 64));
117
118    s1 ^= s1_shifted_right;
119    s1 ^= state_1.clone();
120    s1 ^= state_1.bvlshr(&BV::from_u64(context, 26, 64));
121
122    std::mem::swap(state_0, state_1);
123    *state_1 = s1;
124  }
125
126  // Static 'helper' method
127  fn constrain_mantissa(value: f64, context: &Context, solver: &Solver, state_0: &BV) {
128    // Recover mantissa
129    let mantissa = (value * (1u64 << 53) as f64) as u64;
130    // Add mantissa constraint
131    solver.assert(
132      &state_0
133        .bvlshr(&BV::from_u64(context, 11, 64))
134        ._eq(&BV::from_u64(context, mantissa, 64)),
135    );
136  }
137}
138
139#[cfg(test)]
140mod tests {
141  use std::error::Error;
142
143  #[test]
144  fn correctly_predicts_sequence() -> Result<(), Box<dyn Error>> {
145    let sequence = vec![
146      0.32096095967729477,
147      0.3940071672626849,
148      0.3363374923027722,
149      0.7518761096243554,
150      0.44201420586496387,
151    ];
152    let expected = vec![
153      0.8199006769436774,
154      0.6250240806313154,
155      0.9101975676132608,
156      0.5889203398264599,
157      0.5571161440436232,
158      0.9619184649129092,
159      0.8385620929536599,
160      0.3822042053588621,
161      0.5040552869863579,
162      0.12014019399083042,
163      0.44332968383610927,
164      0.37830079319230936,
165      0.542449069899975,
166      0.0659240460476268,
167      0.9589494984837686,
168      0.007621633090565627,
169      0.14119301022498787,
170      0.9964718645470699,
171      0.14527130036353442,
172      0.6260597083849548,
173      0.86354903522581,
174      0.7245123107811886,
175      0.6565323828155891,
176      0.3636039851663503,
177      0.5799453712253447,
178    ];
179
180    let mut cp = crate::ChromePredictor::new(sequence);
181    let mut predictions = vec![];
182
183    for _ in 0..expected.len() {
184      let prediction = cp.predict_next()?;
185      predictions.push(prediction);
186    }
187
188    assert_eq!(predictions, expected);
189    return Ok(());
190  }
191}
js_randomness_predictor/chrome_predictor.rs

js_randomness_predictor/
chrome_predictor.rs
