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 
27  uint64_t nextPrimeNumber(uint64_t inputNumber);
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  */
55 uint64_t Randomizer::nextPrimeNumber(uint64_t inputNumber) {
56  uint64_t nextPrimeNumber;
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) {
63  nextPrimeNumber += 1;
64  }
65  while (!isPrime(nextPrimeNumber)) {
66  nextPrimeNumber += 2;
67  }
68  if (isPrime(nextPrimeNumber))
69  return nextPrimeNumber;
70  }
71  }
72  return nextPrimeNumber;
73 } // end nextPrimeNumber
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