Source Code for Module rekall.algo

 1  # Rekall Memory Forensics 
 2  # Copyright 2015 Google Inc. All Rights Reserved. 
 3  # 
 4  # This program is free software; you can redistribute it and/or modify 
 5  # it under the terms of the GNU General Public License as published by 
 6  # the Free Software Foundation; either version 2 of the License, or (at 
 7  # your option) any later version. 
 8  # 
 9  # This program is distributed in the hope that it will be useful, but 
10  # WITHOUT ANY WARRANTY; without even the implied warranty of 
11  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
12  # General Public License for more details. 
13  # 
14  # You should have received a copy of the GNU General Public License 
15  # along with this program; if not, write to the Free Software 
16  # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 
17  # 
18   
19  """This module contains general-purpose algorithms and data structures.""" 
20   
21  __author__ = "Adam Sindelar <adamsh@google.com>" 
22   
23   
24 -def EulersDecimals(): 
25      """Yields decimals of Euler's number, using continued fractions. 
26   
27      This is used to generate random looking, but deterministic series of digits 
28      for testing purposes. Unlike PRNGs, the output is always guaranteed to be 
29      the same and is implementation-independent. 
30   
31      For explanation of how this works see (for example) here: 
32      http://mathworld.wolfram.com/eContinuedFraction.html 
33      """ 
34   
35      def e_continued_fraction(): 
36          """Continued fraction for Euler's. 
37   
38          This is the series 1, 0, 1, 1, 2, 1, 1, 4... 
39          """ 
40          yield 1 
41          k = 0 
42          while True: 
43              yield k 
44              k += 2 
45              yield 1 
46              yield 1 
47   
48      def yield_digits(p, q): 
49          while p > 0: 
50              if p > q: 
51                  d = p // q 
52                  p = p - q * d 
53              else: 
54                  d = (10 * p) // q 
55                  p = 10 * p - q * d 
56   
57              yield d 
58   
59      def z(fraction, a=1, b=0, c=0, d=1): 
60          for x in fraction: 
61              while a > 0 and b > 0 and c > 0 and d > 0: 
62                  # Lowest and highest possible value of the next digit - 
63                  # we yield the digit once they're equivalent. 
64                  t = a // c 
65                  t_ = b // d 
66                  if t != t_: 
67                      break 
68   
69                  yield t 
70                  a = (10 * (a - c * t)) 
71                  b = (10 * (b - d * t)) 
72              a, b = x * a + b, a 
73              c, d = x * c + d, c 
74   
75          for digit in yield_digits(a, c): 
76              yield digit 
77   
78      return z(e_continued_fraction()) 
79