Knyffen
b9645f15ff
The text and pattern are now streamed directly (skipping saving them to strings). Knowing exactly what string was matched has now been delegated to the Rabin_fingerprint_process.
60 lines
1.7 KiB
C++
60 lines
1.7 KiB
C++
#include "processes.hpp"
|
|
|
|
Rabin_fingerprint_process::Rabin_fingerprint_process(uint32_t irr_poly, size_t window_size_in_bits)
|
|
: window_size_in_bits(window_size_in_bits),
|
|
phi(irr_poly, window_size_in_bits)
|
|
{}
|
|
|
|
void Rabin_fingerprint_process::stream_char(char c) {
|
|
std::bitset<8> b(c);
|
|
for (char i = 7; i >= 0; i--) {
|
|
stream_bit((bool)b[i]);
|
|
}
|
|
}
|
|
|
|
void Rabin_fingerprint_process::stream_bit(bool b) {
|
|
if (window.size() == window_size_in_bits) {
|
|
window.push(b);
|
|
bool b_out = window.front();
|
|
window.pop();
|
|
phi.slide_bit(b, b_out);
|
|
} else {
|
|
window.push(b);
|
|
phi.push_bit(b);
|
|
}
|
|
}
|
|
|
|
uint32_t Rabin_fingerprint_process::get_fingerprint() {
|
|
return phi.get_fingerprint();
|
|
}
|
|
|
|
std::string Rabin_fingerprint_process::get_string_in_window() {
|
|
// check if window contains a whole number of chars
|
|
if ((window_size_in_bits & 0b111) != 0)
|
|
throw std::logic_error("The fingerprinting window doesn't contain a whole number of chars (counting the bits), so it doesn't make sense to return it as a string.");
|
|
|
|
#ifndef NDEBUG
|
|
if (window.size() != window_size_in_bits)
|
|
throw std::logic_error("False match! The sliding window isn't even filled yet, which means you matched the pattern of a substring shorter than the pattern. This case should be handled/avoided elsewhere, so we throw an error.");
|
|
#endif
|
|
|
|
std::ostringstream os;
|
|
for (size_t i = 0; i < window.size()>>3; i++) {
|
|
// cycle the char
|
|
char c = 0;
|
|
for (size_t j = 0; j < 8; j++) {
|
|
bool b = window.front();
|
|
window.pop();
|
|
window.push(b);
|
|
c <<= 1;
|
|
c |= b;
|
|
}
|
|
|
|
os << c;
|
|
}
|
|
|
|
std::string s = os.str();
|
|
|
|
return s;
|
|
}
|