#define MOD_ADLER 65521
#define ADLER_DECLVARS(var1,var2) size_t var1 = 1, var2 = 0
#define ADLER_ITER(var1,var2,val) var1 += val; var2 += var1
#define ADLER_COMPUTE(var1,var2) (var1 %= MOD_ADLER, var2 %= MOD_ADLER, ((var2 % MOD_ADLER) << 16) | (var1 % MOD_ADLER))
class CString {
public:
CString()
: _beg(NULL), _len(0) {
}
~CString() {
_dealloc(_beg);
}
CString(const char* text, const unsigned short& len)
: _beg(NULL), _len(0) {
assign(text, len);
}
CString(const CString& cpy) {
assign(cpy.c_str(), cpy.length());
}
CString& operator= (const CString& rhs) {
if (this != &rhs)
assign(rhs.c_str(), rhs.length());
return *this;
}
void assign(const char* text, const unsigned short& len) {
if (_beg != NULL) {
if (length() != len) {
_dealloc(_beg);
_beg = _alloc(len + 1);
}
} else
_beg = _alloc(len + 1);
_len = len;
if (_len)
_copy(text, len);
*(_beg + _len) = '\0';
}
size_t length() const {
return _len;
}
const char* c_str() const {
if (_beg != NULL)
return _beg;
return "";
}
bool operator== (const CString& rhs) const {
return (_len == rhs._len && memcmp(_beg, rhs._beg, _len) == 0);
}
char* detach() {
char* p = _beg;
_beg = NULL;
_len = 0;
return p;
}
void attach_detach(CString& oref) {
if (_beg != NULL)
_dealloc(_beg);
_len = oref._len;
_beg = oref.detach();
}
private:
char* _beg;
unsigned short _len;
static HANDLE _hprocheap;
static char* _alloc(const size_t& len) {
return static_cast<char*>(HeapAlloc(_hprocheap, HEAP_NO_SERIALIZE, len));
}
static void _dealloc(char* data) {
if (data)
HeapFree(_hprocheap, HEAP_NO_SERIALIZE, data);
}
void _copy(const char* text, const unsigned short& len) {
memcpy(_beg, text, len);
}
};
class CFile {
public:
struct CLine {
CString line;
size_t adler32;
CLine(char* buf, const unsigned short& len, const size_t& adler32_)
: adler32(adler32_) {
line.assign(buf, len);
}
bool operator== (const CLine& rhs) const {
return adler32 == rhs.adler32;
}
};
CFile() :
_blen(0), _boff(-1), _hfile(INVALID_HANDLE_VALUE), _filelen(0), _lineno(0), _foff(-1) {
_block = (char*)HeapAlloc(GetProcessHeap(), HEAP_NO_SERIALIZE, BLOCK_SIZE);
}
~CFile() {
close();
HeapFree(GetProcessHeap(), HEAP_NO_SERIALIZE, _block);
}
bool open(char* filename, const size_t& windowmax) {
_windowmax = windowmax;
_lineno = 0;
_hfile = CreateFile(filename, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL);
_foff = 0;
if (_hfile == INVALID_HANDLE_VALUE)
return false;
_filelen = GetFileSize(_hfile, NULL);
return true;
}
void close() {
if (_hfile != INVALID_HANDLE_VALUE) {
CloseHandle(_hfile);
_hfile = INVALID_HANDLE_VALUE;
}
}
bool window_load() {
char buf[MAX_LINE_LEN];
size_t n = _window.size();
unsigned short len;
size_t adler32;
while (_window.size() < _windowmax) {
if (_getline(buf, MAX_LINE_LEN - 1, len, adler32))
_window.push_back(new CLine(buf, len, adler32));
else
break;
}
return _window.size() != n;
}
size_t window_size() const {
return _window.size();
}
CLine& operator[] (const size_t& index) {
return *_window[index];
}
bool window_rmline(CString* pline, size_t* plineno) {
if (_window.size()) {
if (pline)
pline->attach_detach(_window[0]->line);
delete _window.front();
_window.erase(_window.begin());
*plineno = ++_lineno;
return true;
}
return false;
}
size_t& lineno() {
return _lineno;
}
private:
long _foff;
size_t _lineno;
size_t _windowmax;
std::vector<CLine*> _window;
long _boff;
size_t _blen;
char* _block;
HANDLE _hfile;
DWORD _filelen;
bool _getline(char* buf, size_t size, unsigned short& len, size_t& adler32) {
char* pbuf = buf;
bool eol = false;
ADLER_DECLVARS(a, b);
do {
if (_foff >= _filelen || ! _readblock(_foff + 1))
return false;
char* beg = _block + (_foff % BLOCK_SIZE);
char* pin = beg;
char* end = _block + _blen;
while (size-- && !eol && pin != end) {
if (*pin != '\r') {
*pbuf = *pin;
ADLER_ITER(a, b, *pbuf++);
}
if (*pin++ == '\n')
eol = true;
}
_foff += pin - beg;
} while (!eol && size);
*pbuf = '\0';
len = pbuf - buf;
adler32 = ADLER_COMPUTE(a, b);
return true;
}
bool _readblock(const size_t& foff) {
size_t new_boff = (foff / BLOCK_SIZE) * BLOCK_SIZE;
if (new_boff != _boff) {
_boff = new_boff;
SetFilePointer(_hfile, _boff, NULL, FILE_BEGIN);
DWORD nread = 0;
ReadFile(_hfile, _block, BLOCK_SIZE, &nread, NULL);
_blen = nread;
return _blen > 0;
}
return true;
}
};
class CPerfCounter {
public:
CPerfCounter() {
m_begin.HighPart = m_begin.LowPart = 0;
QueryPerformanceFrequency(&m_freq);
}
void Start() {
QueryPerformanceCounter(&m_begin);
}
double Stop() {
QueryPerformanceCounter(&m_end);
return (double)(m_end.QuadPart - m_begin.QuadPart) / (double)m_freq.QuadPart;
}
double StopStart() {
double stop = Stop();
Start();
return stop;
}
private:
LARGE_INTEGER m_freq, m_begin, m_end;
};
template <class T>
class C2DVector {
T* _pv;
const size_t _nr;
const size_t _nc;
public:
C2DVector(size_t rows, size_t cols)
: _nr(rows), _nc(cols) {
_pv = static_cast<T*>(HeapAlloc(procheap, HEAP_NO_SERIALIZE, _nr * _nc * sizeof(T)));
}
~C2DVector() {
HeapFree(procheap, HEAP_NO_SERIALIZE, _pv);
}
T& at(const size_t& row, const size_t& col) {
return _pv[row * _nc + col];
}
const size_t& rows() const {
return _nr;
}
const size_t& cols() const {
return _nc;
}
void fill(const T& val) {
for (size_t e = 0; e < _nr * _nc; ++e)
_pv[e] = val;
}
void zerofill() {
memset(_pv, 0, _nr * _nc * sizeof(T));
}
};
class CFileComp {
CFile f1;
CFile f2;
int last_report;
int nmatches;
public:
CFileComp()
: last_report(0), nmatches(0) {
}
void reportInsert() {
if (last_report != 1)
printf("\n");
last_report = 1;
CString line;
size_t ln;
f2.window_rmline(&line, &ln);
printf("----- %5d : %s", ln, line.c_str());
}
void reportDelete() {
if (last_report != 2)
printf("\n");
last_report = 2;
CString line;
size_t ln;
f1.window_rmline(&line, &ln);
printf("%5d ----- : %s", ln, line.c_str());
}
void reportCopy() {
CString line;
size_t ln1, ln2;
f1.window_rmline(&line, &ln1);
f2.window_rmline(NULL, &ln2);
last_report = 3;
nmatches++;
}
void showMatrix(int NW1, int NW2, C2DVector<int>& LCS, C2DVector<bool>& match) {
for (int i1=0; i1<=NW1; i1++) {
std::string s="";
for (int i2=0; i2<=NW2; i2++) {
char buf[20];
sprintf(buf, "%d", LCS.at(i1, i2));
s += std::string(" ") + std::string((match.at(i1, i2) ? "=" : " ")) + std::string(buf);
}
printf("%s\n", s.c_str());
}
}
int exec(char* file1, char* file2) {
const size_t windowmax = 30;
int nloops = 0;
if (! f1.open(file1, windowmax) || ! f2.open(file2, windowmax))
return 1;
bool slidingWindowTooSmall = false;
while (++nloops) {
bool load1 = f1.window_load();
bool load2 = f2.window_load();
bool moreDataLoaded = load1 || load2;
size_t w1 = f1.window_size();
size_t w2 = f2.window_size();
if (w1 + w2 == 0)
break;
bool matchsome = false;
while (f1.window_size() >= 2 && f2.window_size() >= 2 &&
f1[0] == f2[0] && f1[1] == f2[1]) {
reportCopy();
matchsome = true;
}
C2DVector<int> LCS(windowmax + 1, windowmax + 1);
C2DVector<bool> match(windowmax + 1, windowmax + 1);
if (! matchsome) {
int i1, i2;
match.zerofill();
for (i2 = 0; i2 <= w2; i2++)
LCS.at(w1, i2) = 0;
for (i1 = 0; i1 <= w1; i1++)
LCS.at(i1, w1) = 0;
for (i1 = w1 - 1; i1 >= 0; i1--) {
for (i2 = w2 - 1; i2 >= 0; i2--) {
if (f1[i1] == f2[i2]) {
LCS.at(i1, i2) = LCS.at(i1 + 1, i2 + 1) + 1;
match.at(i1, i2) = true;
} else {
if (LCS.at(i1, i2 + 1) > LCS.at(i1 + 1, i2))
LCS.at(i1, i2) = LCS.at(i1, i2 + 1);
else
LCS.at(i1, i2) = LCS.at(i1 + 1, i2);
}
}
}
int matchinglines = LCS.at(0, 0);
if (matchinglines == 0) {
while (f1.window_size() != 0)
reportDelete();
while (f2.window_size() != 0)
reportInsert();
if (! moreDataLoaded)
break;
if (! slidingWindowTooSmall) {
slidingWindowTooSmall=true;
}
} else {
for (int i1 = 0, i2 = 0; ;) {
if (match.at(i1, i2)) {
reportCopy();
i1++;
i2++;
if (--matchinglines <= 0)
break;
} else if (matchinglines == LCS.at(i1, i2+1)) {
reportInsert();
i2++;
} else {
reportDelete();
i1++;
}
}
}
}
}
do {
while (f1.window_size() != 0)
reportDelete();
} while (f1.window_load());
do {
while (f2.window_size() != 0)
reportInsert();
} while (f2.window_load());
return 0;
}
};
int main(int argc, char* argv[])
{
int n = 0;
CPerfCounter pc;
pc.Start();
if (argc > 2 && strcmp(argv[1], argv[2])) {
CFileComp fc;
n = fc.exec(argv[1], argv[2]);
}
printf("%f seconds\n", pc.Stop());
if (argc == 4 || argc == 1)
Sleep(INFINITE);
return n;
}
|
Submit an article or tip