tudocomp – The TU Dortmund Compression Framework
Randomizer.hpp
Go to the documentation of this file.
1 #pragma once
2
3 #include <cstdint>
4 #include <iostream>
5
6 namespace tdc { namespace lz78 {
7
8 class Randomizer {
9 public:
10  Randomizer(uint64_t universeSize);
11
12  ~Randomizer();
13
14  inline uint64_t hash(uint64_t key) const {
15  return ((key % _prime) * _a) % _prime;
16  }
17
18  inline uint64_t invertHash(uint64_t hash) const {
19  return (hash * _aInv) % _prime;
20  }
21
22  const uint64_t _prime;
23 private:
24  // hashfunction
25  uint64_t getModInverse(uint64_t a, uint64_t prime);
26
28
29  bool isPrime(uint64_t input);
30
31  void euclAlgorithm(uint64_t prime);
32
33  uint64_t _universeSize;
34  uint64_t _a; // some magic number, depends on prime
35  uint64_t _aInv; // a^(-1). used to get original key from quotient
36 };
37
38
39 Randomizer::Randomizer(uint64_t universeSize)
40  : _prime(nextPrimeNumber(universeSize - 1)) {
41  _universeSize = universeSize;
42 // _prime = nextPrimeNumber(universeSize - 1);
43  euclAlgorithm(_prime); // would calculate some random number 'a' & its inverse 'aInv'
44 }
45
47
48 }
49
50
51
52 /*
53  * Function for determining the next prime number
54  */
57  if (inputNumber <= 0) {
58  std::cout << "The number you have entered is zero or negative.\n";
59  } else {
60  while (inputNumber != 0) { //TODO: WHY????
61  nextPrimeNumber = inputNumber + 1;
62  if (nextPrimeNumber % 2 == 0 && nextPrimeNumber != 2) {
64  }
67  }
70  }
71  }
74
75 /* Function that checks whether or not a given number is
76  * a prime number or not.
77  */
78 bool Randomizer::isPrime(uint64_t input) {
79  uint64_t i;
80  bool prime = true;
81
82  if (input == 2) {
83  return true;
84  }
85
86  if (input % 2 == 0 || input <= 1) {
87  prime = false;
88  } else {
89  for (i = 3; i <= sqrt(input); i += 2) {
90  if (input % i == 0) {
91  prime = false;
92  }
93  }
94  }
95  return prime;
96 } // end isPrime
97
98 // A naive method to find modulor multiplicative inverse of
99 // 'a' under modulo 'm'
100 uint64_t Randomizer::getModInverse(uint64_t a, uint64_t prime) {
101  a = a % prime;
102  for (uint64_t x = 1; x < prime; x++)
103  if ((a * x) % prime == 1)
104  return x;
105  return prime;
106 }
107
108 void Randomizer::euclAlgorithm(uint64_t prime) {
109  long long aTemp = (long long) (0.66 * (double) prime);
110  long long aInvTemp = prime;
111  while (true) {
112  aInvTemp = getModInverse(aTemp, prime);
113  if (aInvTemp == prime)
114  aTemp++;
115  else
116  break;
117  }
118  _a = aTemp; // TODO: aTemp is 'long long int', meaning signed. a is 'unsigned int64'
119  _aInv = aInvTemp; // TODO: the same
120 }
121
122 }}//ns
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
Randomizer(uint64_t universeSize)
Definition: Randomizer.hpp:39
uint64_t hash(uint64_t key) const
Definition: Randomizer.hpp:14
const uint64_t _prime
Definition: Randomizer.hpp:22
uint64_t invertHash(uint64_t hash) const
Definition: Randomizer.hpp:18