Below are the 20 most recent journal entries recorded in aliakseis' LiveJournal:

[ << Previous 20 ]

Thursday, February 16th, 2012
11:19 pm	Yet another condvar exercise Here it is.. Briefly, there is no need to wake up a thread just to check a condition. And keyed events are quite handy here. (Comment on this)
Monday, February 13th, 2012
11:43 pm	Fast Levenshtein distance (was: Facebook Breathalyzer) #include <iostream> #include <fstream> #include <exception> #include <string> #include <vector> #include <map> #include <algorithm> #include <iterator> #include <climits> #include <stdio.h> //#include <assert.h> #define assert(x) ((void)0) #include <fcntl.h> #include <string.h> #include <omp.h> #ifdef _WIN32 #include <io.h> #define open _open #define lseek _lseek #define read _read #define close _close #else #undef _O_BINARY #define _O_BINARY 0 #endif #ifdef _MSC_VER #define __inline__ __forceinline #else #define _fgetc_nolock fgetc_unlocked //#define _fgetc_nolock fgetc #endif using std::cerr; using std::cout; using std::ifstream; using std::exception; using std::string; using std::getline; using std::vector; using std::map; using std::min; using std::max; using std::istream_iterator; static const signed char LogTable256[256] = { #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) }; inline int Log(unsigned int v) // 32-bit word to find the log of { int r; // r will be lg(v) unsigned int t, tt; // temporaries if (tt = v >> 16) { r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } return r; } struct Plex // Similar to MFC CPlex // warning variable length structure { Plex* pNext; int dwReserved[1]; // align on 8 byte boundary void* data() { return this+1; } // like 'calloc' but no zero fill // may throw memory exceptions static Plex* Create(Plex*& pHead, size_t nMax, size_t cbElement) { assert(nMax > 0 && cbElement > 0); Plex* p = (Plex*) operator new(sizeof(Plex) + nMax * cbElement); // may throw exception p->pNext = pHead; pHead = p; // change head (adds in reverse order for simplicity) return p; } void FreeDataChain() // free this one and links { Plex* p = this; while (p != 0) { void* bytes = p; p = p->pNext; operator delete(bytes); } } }; typedef unsigned int UINT; class FixedAlloc // Similar to MFC CFixedAlloc { // Constructors public: FixedAlloc(UINT nAllocSize, UINT nBlockSize = 64); // Attributes UINT GetAllocSize() { return m_nAllocSize; } // Operations public: void* Alloc(); // return a chunk of memory of nAllocSize void Free(void* p); // free chunk of memory returned from Alloc void FreeAll(); // free everything allocated from this allocator // Implementation public: ~FixedAlloc(); protected: struct CNode { CNode* pNext; // only valid when in free list }; UINT m_nAllocSize; // size of each block from Alloc UINT m_nBlockSize; // number of blocks to get at a time Plex* m_pBlocks; // linked list of blocks (is nBlocks*nAllocSize) CNode* m_pNodeFree; // first free node (0 if no free nodes) }; FixedAlloc::FixedAlloc(UINT nAllocSize, UINT nBlockSize) { assert(nAllocSize >= sizeof(CNode)); assert(nBlockSize > 1); if (nAllocSize < sizeof(CNode)) nAllocSize = sizeof(CNode); if (nBlockSize <= 1) nBlockSize = 64; m_nAllocSize = nAllocSize; m_nBlockSize = nBlockSize; m_pNodeFree = 0; m_pBlocks = 0; } FixedAlloc::~FixedAlloc() { FreeAll(); } void FixedAlloc::FreeAll() { m_pBlocks->FreeDataChain(); m_pBlocks = 0; m_pNodeFree = 0; } void* FixedAlloc::Alloc() { if (m_pNodeFree == 0) { // add another block Plex* pNewBlock = Plex::Create(m_pBlocks, m_nBlockSize, m_nAllocSize); // chain them into free list // free in reverse order to make it easier to debug char* pData = (char*) pNewBlock->data() + m_nAllocSize * (m_nBlockSize - 1); for (int i = m_nBlockSize; i > 0; i--, pData -= m_nAllocSize) { CNode* pNode = (CNode*) pData; pNode->pNext = m_pNodeFree; m_pNodeFree = pNode; } } assert(m_pNodeFree != 0); // we must have something // remove the first available node from the free list void* pNode = m_pNodeFree; m_pNodeFree = m_pNodeFree->pNext; return pNode; } void FixedAlloc::Free(void* p) { if (p != 0) { // simply return the node to the free list CNode* pNode = (CNode*)p; pNode->pNext = m_pNodeFree; m_pNodeFree = pNode; } } // http://www.drdobbs.com/184410528 struct Tnode { char splitchar; /*bool*/ char terminating; unsigned char maxLength, minLength; Tnode *eqkid, *hikid; Tnode(char ch) : splitchar(ch) , terminating(false) , maxLength(0) , minLength(255) , eqkid(0), hikid(0) { } void* operator new(size_t size) { assert(size == s_alloc.GetAllocSize()); return s_alloc.Alloc(); } void* operator new(size_t, void* p) { return p; } void operator delete(void* p) { s_alloc.Free(p); } protected: static FixedAlloc s_alloc; } ; FixedAlloc Tnode::s_alloc(sizeof(Tnode), 64); inline char ToLowerCase(char ch) { return ch | 0x20; } Tnode* insert_new(FILE *stream, int ch, unsigned int& length) { assert(ch & ~31); ch = ToLowerCase(ch); Tnode *p = new Tnode(ch); ch = _fgetc_nolock( stream ); if (0 == (ch & ~31) || EOF == ch) p->terminating = true; else { ++length; p->eqkid = insert_new(stream, ch, length); } p->maxLength = length; p->minLength = length; return p; } Tnode* insert(Tnode *p, FILE *stream, int ch, unsigned int& length) { assert(ch & ~31); ch = ToLowerCase(ch); if (p == 0) { p = new Tnode(ch); } assert(ch >= p->splitchar); if (ch == p->splitchar) { ch = _fgetc_nolock( stream ); if (0 == (ch & ~31) || EOF == ch) p->terminating = true; else { ++length; p->eqkid = insert(p->eqkid, stream, ch, length); } } else { Tnode* temp = insert_new(stream, ch, length); assert(0 == temp->hikid); temp->hikid = p; temp->minLength = p->minLength; temp->maxLength = p->maxLength; p = temp; } if (p->maxLength < length) p->maxLength = length; if (p->minLength > length) p->minLength = length; assert(p->minLength <= p->maxLength); return p; } const char seps[] = "\r\n"; const unsigned int ZERO_DISTANCE = 0xFFFFFFFF;//(unsigned int)-1; class Breathalyzer { private: enum { DISTANCE_THRESHOLD = 3 }; Tnode* wordList; unsigned int minLength;// = INT_MAX; unsigned int wordDim; __inline__ bool DoSearch(const Tnode* p, unsigned int* d, const string& s, const int offset, const unsigned int maxDistance, unsigned int& distance) { int threshold = int(s.size()); if (p->eqkid != 0) threshold -= p->eqkid->maxLength - offset; unsigned int* upLeft = d; unsigned int* downRight = upLeft + s.size() + 2; const char* i = s.data(); const char* dataEnd = i + s.size(); const char splitchar = p->splitchar; const unsigned int startDistance = distance; bool ok = (0 < threshold)? ((startDistance >> threshold) >= maxDistance) : (startDistance >= maxDistance); if (!ok) { const char* pThreshold = i + threshold - 1; for (; i < pThreshold; ++i, ++upLeft, ++downRight) { if (*i == splitchar) distance = *upLeft; else distance = (*upLeft | *(upLeft + 1) | distance) >> 1; *downRight = distance; if ((distance >> (pThreshold - i)) >= maxDistance) { goto ok_loop; } } for (;;) { if (*i == splitchar) distance = *upLeft; else distance = (*upLeft | *(upLeft + 1) | distance) >> 1; *downRight = distance; if (distance >= maxDistance) { goto ok_loop; } if (++i >= dataEnd) return false; ++upLeft; ++downRight; } return false; } else { for (;;) { if (*i == splitchar) distance = *upLeft; else distance = (*upLeft | *(upLeft + 1) | distance) >> 1; *downRight = distance; ok_loop: if (++i >= dataEnd) return true; ++upLeft; ++downRight; } return true; } } bool GetDistance(const Tnode* p, unsigned int* d, const string& s, int offset, int& maxDistance) { for (; p != 0; p = p->eqkid, ++offset, d += s.size() + 1) { if (int(s.length()) - p->maxLength > maxDistance) return false; if (p->minLength - int(s.length()) > maxDistance) return false; if (GetDistance(p->hikid, d, s, offset, maxDistance)) return true; if (0 == p->eqkid && !p->terminating) return false; //int distance(offset); unsigned int distance(ZERO_DISTANCE >> offset); const unsigned int expMaxDistance(ZERO_DISTANCE >> maxDistance); if (!DoSearch(p, d, s, offset, expMaxDistance, distance)) return false; if (p->terminating) { if (distance > expMaxDistance) { maxDistance = 31 - Log(distance); if (maxDistance <= DISTANCE_THRESHOLD) return true; } } } return false; } bool find0(const Tnode* p, const char* s) { for (; p != 0; p = p->eqkid) { while (p->splitchar > *s) { if (0 == p->hikid) { return false; } p = p->hikid; } if (p->splitchar < *s) { return false; } if (0 == *(++s)) { return p->terminating; } } return false; } bool find(const Tnode* p, unsigned int* d, const string& s, int offset, const int maxDistance) { for (; p != 0; p = p->eqkid, ++offset, d += s.size() + 1) { if (int(s.length()) - p->maxLength > maxDistance) return false; if (p->minLength - int(s.length()) > maxDistance) return false; if (find(p->hikid, d, s, offset, maxDistance)) return true; if (0 == p->eqkid && !p->terminating) return false; //int distance(offset); unsigned int distance(ZERO_DISTANCE >> offset); const unsigned int expMaxDistance(ZERO_DISTANCE >> maxDistance); if (!DoSearch(p, d, s, offset, expMaxDistance, distance)) return false; if (p->terminating) { if (distance >= expMaxDistance) return true; } } return false; } public: Breathalyzer() : wordList(0) { } void ReadWordList() { FILE *stream = fopen("/var/tmp/twl06.txt", "r"); for (;;) { int ch; do { ch = _fgetc_nolock( stream ); } while (0 == (ch & ~31)); if (EOF == ch) break; unsigned int length(1); wordList = insert(wordList, stream, ch, length); } fclose(stream); wordDim = wordList->maxLength + 1; minLength = wordList->minLength; } int GetDistance(const string& s) { if (find0(wordList, s.c_str())) return 0; enum { FAST_BUFFER_SIZE = 512 }; unsigned int sbuf[FAST_BUFFER_SIZE]; const size_t bufSize = wordDim * (s.size() + 1); unsigned int* d = (bufSize > FAST_BUFFER_SIZE)? new unsigned int[bufSize] : sbuf; for (unsigned int i = 0; i <= s.size(); ++i) d[i] = ZERO_DISTANCE >> i; for (unsigned int i = 1; i < wordDim; ++i) d[i * (s.size() + 1)] = ZERO_DISTANCE >> i; for (int result = 1; result < DISTANCE_THRESHOLD; ++result) if (find(wordList, &d[0], s, 1, result)) { if (d != sbuf) delete[] d; return result; } int result = max(minLength, (unsigned int) s.size()); GetDistance(wordList, &d[0], s, 1, result); if (d != sbuf) delete[] d; return result; } }; int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: breathalyzer input_file\n"; return 1; } try { Breathalyzer breathalyzer; typedef vector<std::pair<string, int> > Strings; Strings strings; #pragma omp parallel { #pragma omp sections { #pragma omp section { breathalyzer.ReadWordList(); } #pragma omp section { /* string path(argv[1]); if (string::npos == path.find_first_of("\\/")) { string dir(argv[0]); string::size_type pos = dir.find_last_of("\\/"); if (string::npos != pos) { path = dir.substr(0, pos + 1) + path; } } ifstream inFile(path.c_str()); //*/ ifstream inFile(argv[1]); map<string, int> counts; for (istream_iterator<string> iss(inFile), issEnd ; iss != issEnd ; ++iss) { ++counts[*iss]; } strings.assign(counts.begin(), counts.end()); } } } const int numStrings = strings.size(); int totalDistance = 0; int i; #pragma omp parallel for reduction(+:totalDistance) schedule (dynamic, 10) for (i = 0; i < numStrings; ++i) { Strings::iterator it = strings.begin() + i; const int distance = breathalyzer.GetDistance(it->first); totalDistance += distance * it->second; } cout << totalDistance << '\n'; } catch (exception& e) { cerr << e.what(); return 1; } return 0; } (1 Comment |Comment on this)
Monday, January 30th, 2012
11:24 pm	switch вместо побитового цикла Вдруг окажется новым и интересным - за основу для демонстрации удобно взять решение задачу про ящики отсюда. Вкрадце, есть N=20 ящиков с предопределенными весом и прочностью, и нужно посчитать, сколькими способами можно их поставить друг на друга. Типичная задачка на динамическое программирование. Вот решение автора задачи, которое используем в качестве отправной точки: #include <vector> #include <iostream> using namespace std; long long stack_qty(vector<int> weights, vector<int> durab) { int combs_n = 1 << weights.size(); vector<long long> comb(combs_n); comb[0] = 1; for(int cur_comb = 1; cur_comb < combs_n; cur_comb++) { int cur_comb_weight = 0, cur_box, cur_box_bit; for(cur_box = 0, cur_box_bit = 1; cur_box_bit <= cur_comb; cur_box++, cur_box_bit <<= 1) if(cur_comb & cur_box_bit) cur_comb_weight += weights[cur_box]; for(cur_box = 0, cur_box_bit = 1; cur_box_bit <= cur_comb; cur_box++, cur_box_bit <<= 1) { int cur_comb_no_cur_box = cur_comb ^ cur_box_bit; if(cur_comb_no_cur_box < cur_comb && cur_comb_weight - weights[cur_box] <= durab[cur_box]) comb[cur_comb] += comb[cur_comb_no_cur_box]; } } // main for return comb[combs_n - 1]; } const int N = 20; #if 0 const int weight[N] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; const int durab [N] = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, }; #endif const int weight[N] = { 15, 10, 13, 14, 15, 8, 91, 16, 9, 33, 31, 44, 71, 76, 9, 1, 4, 3, 12, 8 }; const int durab [N] = { 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79, 99, 76, 300, 654, 120 }; int main(int argc, char **argv) { vector<int> weight_vec(weight, weight + N); vector<int> durab_vec (durab , durab + N); cout << "Combination=" << stack_qty(weight_vec, durab_vec) << endl; return 0; } В результате получаем примерно следующее время: D:\solutions\boxes2\boxes2\Release>timeit boxes2.exe Combination=424284694368 Version Number: Windows NT 5.1 (Build 2600) Exit Time: 10:40 pm, Monday, January 30 2012 Elapsed Time: 0:00:00.359 Process Time: 0:00:00.343 System Calls: 4664 Context Switches: 2710 Page Faults: 6318 Bytes Read: 490506 Bytes Written: 16472 Bytes Other: 161220 Сначала проведем некоторую предварительную оптимизацию: #include <vector> #include <iostream> using namespace std; long long stack_qty(const int* const weights, const int* const durab, const int num) { const int combs_n = 1 << num; vector<long long> comb(combs_n); comb[0] = 1; int cur_comb_weight = 0; for(int cur_comb = 0; cur_comb < combs_n; cur_comb++) { int cur_box, cur_box_bit; if (cur_comb & 1) { cur_comb_weight += weights[0]; } else if (cur_comb & 2) { cur_comb_weight -= weights[0]; cur_comb_weight += weights[1]; } else { cur_comb_weight = 0; for(cur_box = 0, cur_box_bit = 1; cur_box_bit <= cur_comb; cur_box++, cur_box_bit <<= 1) if(cur_comb & cur_box_bit) cur_comb_weight += weights[cur_box]; } const int not_cur_comb = combs_n - 1 - cur_comb; for(cur_box = 0, cur_box_bit = 1; cur_box_bit <= not_cur_comb; cur_box++, cur_box_bit <<= 1) { if (not_cur_comb & cur_box_bit && cur_comb_weight <= durab[cur_box]) comb[cur_comb | cur_box_bit] += comb[cur_comb]; } } // main for return comb[combs_n - 1]; } const int N = 20; #if 0 const int weight[N] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; const int durab [N] = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, }; #endif const int weight[N] = { 15, 10, 13, 14, 15, 8, 91, 16, 9, 33, 31, 44, 71, 76, 9, 1, 4, 3, 12, 8 }; const int durab [N] = { 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79, 99, 76, 300, 654, 120 }; int main(int argc, char **argv) { vector<int> weight_vec(weight, weight + N); vector<int> durab_vec (durab , durab + N); cout << "Combination=" << stack_qty(&weight_vec[0], &durab_vec[0], N) << endl; return 0; } В результате получаем примерно следующее время: D:\solutions\boxes2_1\boxes2\Release>timeit boxes2.exe Combination=424284694368 Version Number: Windows NT 5.1 (Build 2600) Exit Time: 10:47 pm, Monday, January 30 2012 Elapsed Time: 0:00:00.218 Process Time: 0:00:00.218 System Calls: 2339 Context Switches: 866 Page Faults: 2509 Bytes Read: 41998 Bytes Written: 1680 Bytes Other: 4258 А теперь применяем switch вместо побитового цикла: #include <vector> #include <iostream> using namespace std; #define HANDLE_GROUPS_4(a, b, c, d) \ case (a * 64 + b * 16 + c * 4 + d): \ { \ enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \ HANDLE_FLAG(0); \ HANDLE_FLAG(1); \ HANDLE_FLAG(2); \ HANDLE_FLAG(3); \ HANDLE_FLAG(4); \ HANDLE_FLAG(5); \ HANDLE_FLAG(6); \ HANDLE_FLAG(7); \ break; \ } #define HANDLE_GROUPS_3(a, b, c) \ HANDLE_GROUPS_4(a, b, c, 0) \ HANDLE_GROUPS_4(a, b, c, 1) \ HANDLE_GROUPS_4(a, b, c, 2) \ HANDLE_GROUPS_4(a, b, c, 3) #define HANDLE_GROUPS_2(a, b) \ HANDLE_GROUPS_3(a, b, 0) \ HANDLE_GROUPS_3(a, b, 1) \ HANDLE_GROUPS_3(a, b, 2) \ HANDLE_GROUPS_3(a, b, 3) #define HANDLE_GROUPS_1(a) \ HANDLE_GROUPS_2(a, 0) \ HANDLE_GROUPS_2(a, 1) \ HANDLE_GROUPS_2(a, 2) \ HANDLE_GROUPS_2(a, 3) long long stack_qty(const int* const weights, const int* const durab, const int num) { const int combs_n = 1 << num; vector<long long> comb(combs_n); comb[0] = 1; int cur_comb_weight = 0; for(int cur_comb = 0; cur_comb < combs_n; cur_comb++) { #define HANDLE_FLAG(curPlace) \ if (flags & (1 << curPlace)) \ { \ cur_comb_weight += weights[cur_box + curPlace]; \ } if (cur_comb & 1) { cur_comb_weight += weights[0]; } else if (cur_comb & 2) { cur_comb_weight -= weights[0]; cur_comb_weight += weights[1]; } else { cur_comb_weight = 0; { const int cur_box = 0, cur_box_bit = 1; switch ((cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } { const int cur_box = 8, cur_box_bit = 1 << 8; switch ((cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } { const int cur_box = 16, cur_box_bit = 1 << 16; switch ((cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } } #undef HANDLE_FLAG #define HANDLE_FLAG(curPlace) \ if (flags & (1 << curPlace)) \ { \ if(cur_comb_weight <= durab[cur_box + curPlace]) { \ comb[cur_comb | (cur_box_bit << curPlace)] += comb[cur_comb]; \ } \ } const int not_cur_comb = combs_n - 1 - cur_comb; { const int cur_box = 0, cur_box_bit = 1; switch ((not_cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } { const int cur_box = 8, cur_box_bit = 1 << 8; switch ((not_cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } { const int cur_box = 16, cur_box_bit = 1 << 16; switch ((not_cur_comb >> cur_box) & 0xFF) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) HANDLE_GROUPS_1(2) HANDLE_GROUPS_1(3) } } } // main for return comb[combs_n - 1]; } const int N = 20; #if 0 const int weight[N] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; const int durab [N] = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, }; #endif const int weight[N] = { 15, 10, 13, 14, 15, 8, 91, 16, 9, 33, 31, 44, 71, 76, 9, 1, 4, 3, 12, 8 }; const int durab [N] = { 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79, 99, 76, 300, 654, 120 }; int main(int argc, char **argv) { vector<int> weight_vec(weight, weight + N); vector<int> durab_vec (durab , durab + N); cout << "Combination=" << stack_qty(&weight_vec[0], &durab_vec[0], N) << endl; return 0; } В результате получаем примерно следующее время: D:\solutions\boxes2_2\boxes2\Release>timeit boxes2.exe Combination=424284694368 Version Number: Windows NT 5.1 (Build 2600) Exit Time: 10:57 pm, Monday, January 30 2012 Elapsed Time: 0:00:00.109 Process Time: 0:00:00.109 System Calls: 2518 Context Switches: 730 Page Faults: 2526 Bytes Read: 11686 Bytes Written: 2064 Bytes Other: 5926 С g++ примерно та же картина. (1 Comment |Comment on this)
Sunday, February 13th, 2011
9:11 pm	Opus #15 #include <algorithm> #include <iostream> #include <time.h> using std::cout; using std::cerr; using std::endl; enum { MULTIPLIER = 7 }; #define ITER(stage) \ if (stage <= curPlace) \ { \ enum { OFFSET = (1 << stage) / 2 }; \ if (*(first + (OFFSET - 1) * MULTIPLIER) < val) \ first += OFFSET * MULTIPLIER; \ } template <int curPlace, typename I, typename V> inline I fast_lower_bound(I first, const V& val) { ITER(28) ITER(27) ITER(26) ITER(25) ITER(24) ITER(23) ITER(22) ITER(21) ITER(20) ITER(19) ITER(18) ITER(17) ITER(16) ITER(15) ITER(14) ITER(13) ITER(12) ITER(11) ITER(10) ITER(9) ITER(8) ITER(7) ITER(6) ITER(5) ITER(4) ITER(3) ITER(2) ITER(1) if (*(first - 1) < val) return first; if (*(first - 2) < val) return first - 1; if (*(first - 3) < val) return first - 2; if (*(first - 4) < val) return first - 3; if (*(first - 5) < val) return first - 4; if (*(first - 6) < val) return first - 5; return first - 6; } #define HANDLE_GROUPS_3(a, b, c) \ HANDLE_GROUPS_4(a, b, c, 0) \ HANDLE_GROUPS_4(a, b, c, 1) \ HANDLE_GROUPS_4(a, b, c, 2) \ HANDLE_GROUPS_4(a, b, c, 3) #define HANDLE_GROUPS_2(a, b) \ HANDLE_GROUPS_3(a, b, 0) \ HANDLE_GROUPS_3(a, b, 1) \ HANDLE_GROUPS_3(a, b, 2) \ HANDLE_GROUPS_3(a, b, 3) #define HANDLE_GROUPS_1(a) \ HANDLE_GROUPS_2(a, 0) \ HANDLE_GROUPS_2(a, 1) \ HANDLE_GROUPS_2(a, 2) \ HANDLE_GROUPS_2(a, 3) #define HANDLE_GROUPS_4(a, b, c, d) \ case (a * 64 + b * 16 + c * 4 + d): \ { \ enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \ HANDLE_FLAG(6); \ HANDLE_FLAG(5); \ HANDLE_FLAG(4); \ HANDLE_FLAG(3); \ HANDLE_FLAG(2); \ HANDLE_FLAG(1); \ HANDLE_FLAG(0); \ break; \ } #define HANDLE_FLAG(flag) \ { \ enum { curPlace = flag + SEGMENT * 7 }; \ if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \ first += (1 << curPlace) * MULTIPLIER; \ else \ return fast_lower_bound<curPlace>(first, val); \ if (flags & (1 << flag)) \ { \ if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \ first += (1 << curPlace) * MULTIPLIER; \ else \ return fast_lower_bound<curPlace>(first, val); \ } \ } template <typename I, int SEGMENT> struct bound_continue_helper { template<typename V> static I lower_bound_ex(I first, unsigned int distance, const V& val) { switch ((distance >> (SEGMENT * 7)) & 127) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) } return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val); } }; template <typename I> struct bound_continue_helper<I, -1> { template<typename V> static I lower_bound_ex(I first, unsigned int, const V&) { return first; } }; #undef HANDLE_GROUPS_4 #define HANDLE_GROUPS_4(a, b, c, d) \ case (a * 64 + b * 16 + c * 4 + d): \ { \ enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \ if (0 == flags) \ return bound_entry_helper<I, SEGMENT-1>::lower_bound_ex(first, distance, val); \ HANDLE_FLAG(6); \ HANDLE_FLAG(5); \ HANDLE_FLAG(4); \ HANDLE_FLAG(3); \ HANDLE_FLAG(2); \ HANDLE_FLAG(1); \ HANDLE_FLAG(0); \ break; \ } #undef HANDLE_FLAG #define HANDLE_FLAG(flag) \ if (flags >= (1 << (flag+1))) \ { \ enum { curPlace = flag + SEGMENT * 7 }; \ if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \ first += (1 << curPlace) * MULTIPLIER; \ else \ return fast_lower_bound<curPlace>(first, val); \ if (flags & (1 << flag)) \ { \ if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \ first += (1 << curPlace) * MULTIPLIER; \ else \ return fast_lower_bound<curPlace>(first, val); \ } \ } template <typename I, int SEGMENT> struct bound_entry_helper { template<typename V> static I lower_bound_ex(I first, unsigned int distance, const V& val) { switch ((distance >> (SEGMENT * 7)) & 127) { HANDLE_GROUPS_1(0) HANDLE_GROUPS_1(1) } return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val); } }; template <typename I> struct bound_entry_helper<I, -1> { template<typename V> static I lower_bound_ex(I first, unsigned int, const V&) { return first; } }; template<typename I, typename V> inline I lower_bound_ex(I first, I last, const V& val) { unsigned int distance = (unsigned int) (last - first) / MULTIPLIER; unsigned int flags = distance + 1; I result = (flags >= 0x00004000) ? bound_entry_helper<I, 3>::lower_bound_ex(first + MULTIPLIER - 1, flags, val) : bound_entry_helper<I, 1>::lower_bound_ex(first + MULTIPLIER - 1, flags, val); I temp = result - (MULTIPLIER - 1); if (first + distance * MULTIPLIER == temp) { result = temp; for (; result != last; ++result) if (!(*result < val)) return result; } return result; } unsigned int HashKey(int key) { return (key * 2654435761UL) >> 11; } int main(int argc, char* argv[]) { enum { SIZE = 512 * 1024, ITERATIONS = 10 }; int* arr = new int[SIZE]; for (int i = 0; i <= SIZE; ++i) arr[i] = i; clock_t start = clock(); for (int k = 0; k < ITERATIONS; ++k) for (int i = 0; i < SIZE; ++i) { int j = (HashKey(i) % SIZE); int* p = lower_bound_ex(arr, arr + SIZE - 1, j); if (j != *p) { cerr << "Erroneous lower_bound_ex test result: " << *p << " instead of " << j << endl; return 1; } } cout << "lower_bound_ex time: " << (double)(clock() - start) / CLOCKS_PER_SEC << " seconds" << endl; start = clock(); for (int k = 0; k < ITERATIONS; ++k) for (int i = 0; i < SIZE; ++i) { int j = (HashKey(i) % SIZE); int* p = std::lower_bound(arr, arr + SIZE - 1, j); if (j != *p) { cerr << "Erroneous std::lower_bound test result: " << *p << " instead of " << j << endl; return 1; } } cout << "std::lower_bound time: " << (double)(clock() - start) / CLOCKS_PER_SEC << " seconds" << endl; return 0; } (Comment on this)
Wednesday, February 2nd, 2011
11:21 pm	Если б не было так грустно ... Беларусь примет адекватные меры в ответ на решения Совета ЕС (ВИДЕО) Мясникович: Нужно привлечь студентов из европейских стран на обучение в Беларусь Австрийский студент-медик повесился в минском общежитии (Comment on this)
Saturday, December 25th, 2010
2:54 pm	19 Из старой детской книжки: Возьмите число, состоящее из любого количества девяток. Прибавьте к нему всего одну единицу. Все девятки превратятся в нули, а единица станет во главе. (Comment on this)
Friday, August 13th, 2010
7:40 pm	Opus #14 #pragma once #include <comdef.h> inline LPCTSTR DecorateNull(LPCTSTR psz) { return psz? psz : _T("<NULL>"); } // ADO_LOGGED_PARAMETER(Parameters) // ADO_LOGGED_PARAMETER(Fields) // ADO_LOGGED_PARAMETER(SearchDirection) // ADO_LOGGED_PARAMETER(FieldList) #define ADO_LOGGED_PARAMETERS \ ADO_LOGGED_PARAMETER(CommandText) \ ADO_LOGGED_PARAMETER(Index) \ ADO_LOGGED_PARAMETER(Name) \ ADO_LOGGED_PARAMETER(Type) \ ADO_LOGGED_PARAMETER(Direction) \ ADO_LOGGED_PARAMETER(Size) \ ADO_LOGGED_PARAMETER(Value) \ ADO_LOGGED_PARAMETER(pbstrName) \ ADO_LOGGED_PARAMETER(pbstr) \ ADO_LOGGED_PARAMETER(ConnectionString) \ ADO_LOGGED_PARAMETER(UserID) \ ADO_LOGGED_PARAMETER(Level) \ ADO_LOGGED_PARAMETER(plAttr) \ ADO_LOGGED_PARAMETER(plMode) \ ADO_LOGGED_PARAMETER(Schema) \ ADO_LOGGED_PARAMETER(Restrictions) \ ADO_LOGGED_PARAMETER(SchemaID) \ ADO_LOGGED_PARAMETER(pval) \ ADO_LOGGED_PARAMETER(plAttributes) \ ADO_LOGGED_PARAMETER(pl) \ ADO_LOGGED_PARAMETER(pfPrepared) \ ADO_LOGGED_PARAMETER(plTimeout) \ ADO_LOGGED_PARAMETER(plCursorLoc) \ ADO_LOGGED_PARAMETER(Source) \ ADO_LOGGED_PARAMETER(ActiveConnection) \ ADO_LOGGED_PARAMETER(CursorType) \ ADO_LOGGED_PARAMETER(LockType) \ ADO_LOGGED_PARAMETER(Options) \ ADO_LOGGED_PARAMETER(Object) \ ADO_LOGGED_PARAMETER(ppvObject) \ ADO_LOGGED_PARAMETER(RecordsAffected) \ ADO_LOGGED_PARAMETER(plCmdType) \ ADO_LOGGED_PARAMETER(Password) \ ADO_LOGGED_PARAMETER(pvar) \ ADO_LOGGED_PARAMETER(pvBookmark) \ ADO_LOGGED_PARAMETER(plLockType) \ ADO_LOGGED_PARAMETER(plMaxRecords) \ ADO_LOGGED_PARAMETER(pvSource) \ ADO_LOGGED_PARAMETER(Values) \ ADO_LOGGED_PARAMETER(AffectRecords) \ ADO_LOGGED_PARAMETER(Rows) \ ADO_LOGGED_PARAMETER(Start) \ ADO_LOGGED_PARAMETER(Criteria) \ ADO_LOGGED_PARAMETER(CursorOptions) \ ADO_LOGGED_PARAMETER(peMarshal) \ ADO_LOGGED_PARAMETER(SkipRecords) \ ADO_LOGGED_PARAMETER(ppunkDataSource) \ ADO_LOGGED_PARAMETER(FileName) \ ADO_LOGGED_PARAMETER(PersistFormat) \ ADO_LOGGED_PARAMETER(pbStayInSync) \ ADO_LOGGED_PARAMETER(StringFormat) \ ADO_LOGGED_PARAMETER(NumRows) \ ADO_LOGGED_PARAMETER(ColumnDelimeter) \ ADO_LOGGED_PARAMETER(RowDelimeter) \ ADO_LOGGED_PARAMETER(NullExpr) \ ADO_LOGGED_PARAMETER(pbstrDataMember) \ ADO_LOGGED_PARAMETER(Bookmark1) \ ADO_LOGGED_PARAMETER(Bookmark2) \ ADO_LOGGED_PARAMETER(ResyncValues) \ ADO_LOGGED_PARAMETER(KeyValues) \ ADO_LOGGED_PARAMETER(SeekOption) \ ADO_LOGGED_PARAMETER(pbstrIndex) \ ADO_LOGGED_PARAMETER(Destination) \ ADO_LOGGED_PARAMETER(DefinedSize) \ ADO_LOGGED_PARAMETER(Attrib) \ ADO_LOGGED_PARAMETER(FieldValue) \ ADO_LOGGED_PARAMETER(Data) \ ADO_LOGGED_PARAMETER(ppiDF) \ ADO_LOGGED_PARAMETER(pbPrecision) \ ADO_LOGGED_PARAMETER(pbNumericScale) \ ADO_LOGGED_PARAMETER(pDataType) \ ADO_LOGGED_PARAMETER(adReason) \ ADO_LOGGED_PARAMETER(cFields) \ ADO_LOGGED_PARAMETER(Val) \ ADO_LOGGED_PARAMETER(plParmAttribs) \ ADO_LOGGED_PARAMETER(pvStream) \ ADO_LOGGED_PARAMETER(pbScale) \ ADO_LOGGED_PARAMETER(psDataType) \ ADO_LOGGED_PARAMETER(plParmDirection) \ ADO_LOGGED_PARAMETER(pbstrDialect) \ ADO_LOGGED_PARAMETER(pfNamedParameters) \ ADO_LOGGED_PARAMETER(pError) \ ADO_LOGGED_PARAMETER(adStatus) \ ADO_LOGGED_PARAMETER(pCommand) \ ADO_LOGGED_PARAMETER(pConnection) \ ADO_LOGGED_PARAMETER(cRecords) \ ADO_LOGGED_PARAMETER(fMoreData) \ ADO_LOGGED_PARAMETER(Progress) \ ADO_LOGGED_PARAMETER(MaxProgress) \ ADO_LOGGED_PARAMETER(pDSO) \ ADO_LOGGED_PARAMETER(pSession) \ ADO_LOGGED_PARAMETER(UserName) \ ADO_LOGGED_PARAMETER(Async) \ ADO_LOGGED_PARAMETER(Mode) \ ADO_LOGGED_PARAMETER(CreateOptions) \ ADO_LOGGED_PARAMETER(pPos) \ ADO_LOGGED_PARAMETER(ptype) \ ADO_LOGGED_PARAMETER(pLS) \ ADO_LOGGED_PARAMETER(pMode) \ ADO_LOGGED_PARAMETER(pbstrCharset) \ ADO_LOGGED_PARAMETER(NumBytes) \ ADO_LOGGED_PARAMETER(Buffer) \ ADO_LOGGED_PARAMETER(DestStream) \ ADO_LOGGED_PARAMETER(CharNumber) \ ADO_LOGGED_PARAMETER(NumChars) \ ADO_LOGGED_PARAMETER(ppRow) \ ADO_LOGGED_PARAMETER(_arg1) \ ADO_LOGGED_PARAMETER(ppStm) \ ADO_LOGGED_PARAMETER(ppOLEDBCommand) \ ADO_LOGGED_PARAMETER(ppRowset) \ ADO_LOGGED_PARAMETER(plChapter) \ ADO_LOGGED_PARAMETER(ppRowPos) \ ADO_LOGGED_PARAMETER(Length) #define ADO_LOGGED_PARAMETER(name) name, enum AdoMissingParameters { ADO_LOGGED_PARAMETERS }; #undef ADO_LOGGED_PARAMETER inline CString AdoLoggingParameter(LPCSTR name, const _bstr_t& value) { CString result(name); result += ": "; result += DecorateNull(value); result += ", "; return result; } inline CString AdoLoggingParameter(LPCSTR name, const _variant_t& value) { CString result(name); result += ": "; try { result += DecorateNull((_bstr_t) value); } catch (...) { result += "<Error>"; } result += ", "; return result; } inline CString AdoLoggingParameter(LPCSTR name, int value) { CString result; result.Format("%s: %d, ", name, value); return result; } inline CString AdoLoggingParameter(LPCSTR name, long value) { CString result; result.Format("%s: %ld, ", name, value); return result; } inline CString AdoLoggingParameter(LPCSTR name, short value) { CString result; result.Format("%s: %d, ", name, (int) value); return result; } inline CString AdoLoggingParameter(LPCSTR name, void* value) { CString result; result.Format("%s: 0x%x, ", name, (DWORD) value); return result; } struct Empty {}; inline Empty AdoLoggingParameter(LPCSTR, AdoMissingParameters) { return Empty(); } inline const CString& operator + (const CString& str, const Empty&) { return str; } #define ADO_LOGGED_PARAMETER(name) + AdoLoggingParameter(#name, name) #define _com_issue_errorex(hr, pUnk, refiid) \ do { \ try { \ _com_issue_errorex((hr), (pUnk), (refiid)); \ } \ catch (...) { \ TRACE(CString() ADO_LOGGED_PARAMETERS + "Throwing exception ..."); \ throw; \ } \ } while (false) \ #pragma warning(push) #pragma warning(disable: 4146) #import <C:\Program Files\Common Files\System\ado\msado15.dll> no_namespace rename( "EOF", "adoEOF" ) #pragma warning(pop) #undef ADO_LOGGED_PARAMETER #undef ADO_LOGGED_PARAMETERS #undef _com_issue_errorex (Comment on this)
Sunday, July 4th, 2010
3:09 pm	Вести с полей Хозяйство Урожайность FaceBull 21.134 Find Sophie 34.877 Refrigerator Madness 367.966 We Are The Swarm 1423.756 Peak Traffic 1825.610 Breathalyzer 120.799 User Bin Crash 23.988 Gattaca 49.530 It's A Small World 568.933 Внесены изменения за период до 7 мая 2011 (17 Comments |Comment on this)
Friday, June 11th, 2010
5:31 pm	Opus #13 Нельзя не согласиться, Что нет на свете краше Державнейшей Отчизны, Страны Великой Нашей. А если кто посмеет И будет нам перечить, Мы подлеца сумеем Поймать и обезвредить. Добры мы по природе, Но нюни не разводим. Мы сразу покараем Такого негодяя, Такого негодяя На месте расстреляем. (Comment on this)
Monday, June 7th, 2010
11:53 am	Opus #12 create or replace package data_change_stat as TYPE t_nom_rec IS RECORD ( TABLENAME VARCHAR2(30 BYTE), FIELDNAME VARCHAR2(30 BYTE), MODIFYDATE DATE, MODIFYUID VARCHAR2(30 BYTE), ACTION VARCHAR2(1 BYTE), OLDVALUE VARCHAR2(400 BYTE), NEWVALUE VARCHAR2(400 BYTE) ); type master_table_t is table of t_nom_rec; FUNCTION AUDIT_ID_SEARCH(SCHEMA_NAME IN VARCHAR2, START_TIME IN DATE, MIN_ID_ IN NUMBER, MAX_ID_ IN NUMBER) RETURN NUMBER; function data_change(SCHEMA_NAME IN VARCHAR2, begin_date in DATE, end_date in DATE) return master_table_t pipelined; end data_change_stat; / create or replace package body data_change_stat as FUNCTION AUDIT_ID_SEARCH(SCHEMA_NAME IN VARCHAR2, START_TIME IN DATE, MIN_ID_ IN NUMBER, MAX_ID_ IN NUMBER) RETURN NUMBER IS PROBE_ID NUMBER; PROBE_TIME DATE; MIN_ID NUMBER; MAX_ID NUMBER; MEDIAN_ID NUMBER; BEGIN MIN_ID := MIN_ID_; MAX_ID := MAX_ID_; WHILE MIN_ID <= MAX_ID LOOP MEDIAN_ID := MIN_ID + FLOOR((MAX_ID - MIN_ID) / 2); BEGIN EXECUTE IMMEDIATE 'SELECT AUDITID, MODIFYDATE FROM ' || SCHEMA_NAME || '.AUDIT WHERE AUDITID = :0' INTO PROBE_ID, PROBE_TIME USING MEDIAN_ID; EXCEPTION WHEN NO_DATA_FOUND THEN EXECUTE IMMEDIATE 'SELECT AUDITID, MODIFYDATE FROM ' || SCHEMA_NAME || '.AUDIT WHERE AUDITID = (SELECT MIN(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT WHERE AUDITID >= :0)' INTO PROBE_ID, PROBE_TIME USING MEDIAN_ID; END; IF PROBE_TIME < START_TIME THEN MIN_ID := PROBE_ID + 1; ELSE MAX_ID := MEDIAN_ID - 1; END IF; END LOOP; RETURN MIN_ID; END AUDIT_ID_SEARCH; function data_change(SCHEMA_NAME IN VARCHAR2, begin_date in DATE, end_date in DATE) return master_table_t pipelined is r t_nom_rec; type cur_typ is ref cursor; cur cur_typ; MIN_ID NUMBER; MAX_ID NUMBER; begin EXECUTE IMMEDIATE 'SELECT MIN(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT' INTO MIN_ID; EXECUTE IMMEDIATE 'SELECT MAX(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT' INTO MAX_ID; MIN_ID := AUDIT_ID_SEARCH(SCHEMA_NAME, begin_date, MIN_ID, MAX_ID); MAX_ID := AUDIT_ID_SEARCH(SCHEMA_NAME, end_date, MIN_ID, MAX_ID); open cur for 'select TABLENAME, FIELDNAME, MODIFYDATE, MODIFYUID, ACTION, OLDVALUE, NEWVALUE from ' || SCHEMA_NAME || '.AUDIT where auditid between ' || MIN_ID || ' and ' || MAX_ID || ' ORDER BY MODIFYUID, TABLENAME, MODIFYDATE'; loop fetch cur into r; exit when cur%notfound; pipe row (r); end loop; return; end data_change; end data_change_stat; / (Comment on this)
Tuesday, May 18th, 2010
5:53 pm	I Believe In Cash When I'm waking up I hope my lucky day has come. When I go to sleep, I weep, because my dream has gone. Guess, I'm not the only one, who's feeling like I do. But I know that Cash 'sgonna make my dream come true, Ye-ah Cash, I believe in Cash, Everlasting Cash - For every one of us to share, ye-ah Cash, all I need is Cash, all I'm asking for - in every wish, in every prayer (Comment on this)
Tuesday, April 27th, 2010
2:23 pm	Is there any sense in such an "achievement" ? Here it is. "А мы тут, знаете, всё плюшками балуемся ..." (Comment on this)
Saturday, February 27th, 2010
2:12 pm	Austrian medical student hanged himself in Minsk hostel The Office of Public Prosecutor of the Moscow area of Minsk inspects upon death of a student from Austria who was found hung up in a bathroom of a hostel of medical university, the senior assistant to the public prosecutor of Minsk Sergey Balashev told "Interfax-West". "In a hostel of the Belarus state medical university, in a bathroom, the body of the first-year student, a citizen of Austria" was revealed, said S.Balashev. As he said, "the body in a loop, hanging in a bathroom, was found by neighbors in a hostel. The Office of Public Prosecutor of the Moscow area carries out a check". http://www.interfax.by/news/belarus/68380 (Comment on this)
Sunday, February 21st, 2010
1:05 pm	So much for "equal opportunities" On applying my resume to the Russian branch of SUN Microsystems, I got the next response: Dear Aliaksei, our export license conditions make our vacancies avaliable to Russian Citizens only. Are you a Russian citizen? thank you ******* ******* Recruitment Manager Ironically, even such a thing named "Union State of Russia and Belarus" kinda exists. They mention "the right to work and reside in both countries, without any of the standard immigration or work visa procedures required of foreign nationals". Life is all about barriers. (3 Comments |Comment on this)
Saturday, February 6th, 2010
2:36 pm	An excellent comment on Opus #2 Here it is. Thanks, ynamara! (Comment on this)
Saturday, August 22nd, 2009
1:28 pm	Opus #11 #define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers #ifndef _WIN32_WINNT #define _WIN32_WINNT 0x0400 #endif #include <windows.h> #include <Dbghelp.h> #include <tchar.h> #include <string> #include <vector> #pragma comment(lib, "Dbghelp.lib") #include <shlwapi.h> #pragma comment(lib, "shlwapi.lib") #include <Tlhelp32.h> #include <signal.h> using std::string; using std::vector; /////////////////////////////////////////////////////////////////////////////// // // bool GetPdbFileName(LPCTSTR FileName, LPTSTR DebugDir) // Adaptation of DebugDir example source code by Oleg Starodumov (www.debuginfo.com) // // /////////////////////////////////////////////////////////////////////////////// // Include files // #include <crtdbg.h> /////////////////////////////////////////////////////////////////////////////// // Helper macros // // Thanks to Matt Pietrek #define MakePtr( cast, ptr, addValue ) (cast)( (DWORD_PTR)(ptr) + (DWORD_PTR)(addValue)) /////////////////////////////////////////////////////////////////////////////// // CodeView debug information structures // #define CV_SIGNATURE_NB10 '01BN' #define CV_SIGNATURE_RSDS 'SDSR' // CodeView header struct CV_HEADER { DWORD CvSignature; // NBxx LONG Offset; // Always 0 for NB10 }; // CodeView NB10 debug information // (used when debug information is stored in a PDB 2.00 file) struct CV_INFO_PDB20 { CV_HEADER Header; DWORD Signature; // seconds since 01.01.1970 DWORD Age; // an always-incrementing value BYTE PdbFileName[1]; // zero terminated string with the name of the PDB file }; // CodeView RSDS debug information // (used when debug information is stored in a PDB 7.00 file) struct CV_INFO_PDB70 { DWORD CvSignature; GUID Signature; // unique identifier DWORD Age; // an always-incrementing value BYTE PdbFileName[1]; // zero terminated string with the name of the PDB file }; /////////////////////////////////////////////////////////////////////////////// // Functions // // // Check whether the specified IMAGE_OPTIONAL_HEADER belongs to // a PE32 or PE32+ file format // // Return value: "true" if succeeded (bPE32Plus contains "true" if the file // format is PE32+, and "false" if the file format is PE32), // "false" if failed // bool IsPE32Plus( PIMAGE_OPTIONAL_HEADER pOptionalHeader, bool& bPE32Plus ) { // Note: The function does not check the header for validity. // It assumes that the caller has performed all the necessary checks. // IMAGE_OPTIONAL_HEADER.Magic field contains the value that allows // to distinguish between PE32 and PE32+ formats if( pOptionalHeader->Magic == IMAGE_NT_OPTIONAL_HDR32_MAGIC ) { // PE32 bPE32Plus = false; } else if( pOptionalHeader->Magic == IMAGE_NT_OPTIONAL_HDR64_MAGIC ) { // PE32+ bPE32Plus = true; } else { // Unknown value -> Report an error bPE32Plus = false; return false; } return true; } // // Returns (in [out] parameters) the RVA and size of the debug directory, // using the information in IMAGE_OPTIONAL_HEADER.DebugDirectory[IMAGE_DIRECTORY_ENTRY_DEBUG] // // Return value: "true" if succeeded, "false" if failed // bool GetDebugDirectoryRVA( PIMAGE_OPTIONAL_HEADER pOptionalHeader, DWORD& DebugDirRva, DWORD& DebugDirSize ) { // Check parameters if( pOptionalHeader == 0 ) { _ASSERT( 0 ); return false; } // Determine the format of the PE executable bool bPE32Plus = false; if( !IsPE32Plus( pOptionalHeader, bPE32Plus ) ) { // Probably invalid IMAGE_OPTIONAL_HEADER.Magic return false; } // Obtain the debug directory RVA and size if( bPE32Plus ) { PIMAGE_OPTIONAL_HEADER64 pOptionalHeader64 = (PIMAGE_OPTIONAL_HEADER64)pOptionalHeader; DebugDirRva = pOptionalHeader64->DataDirectory[IMAGE_DIRECTORY_ENTRY_DEBUG].VirtualAddress; DebugDirSize = pOptionalHeader64->DataDirectory[IMAGE_DIRECTORY_ENTRY_DEBUG].Size; } else { PIMAGE_OPTIONAL_HEADER32 pOptionalHeader32 = (PIMAGE_OPTIONAL_HEADER32)pOptionalHeader; DebugDirRva = pOptionalHeader32->DataDirectory[IMAGE_DIRECTORY_ENTRY_DEBUG].VirtualAddress; DebugDirSize = pOptionalHeader32->DataDirectory[IMAGE_DIRECTORY_ENTRY_DEBUG].Size; } if( ( DebugDirRva == 0 ) && ( DebugDirSize == 0 ) ) { // No debug directory in the executable -> no debug information return true; } else if( ( DebugDirRva == 0 ) || ( DebugDirSize == 0 ) ) { // Inconsistent data in the data directory return false; } return true; } // // The function walks through the section headers, finds out the section // the given RVA belongs to, and uses the section header to determine // the file offset that corresponds to the given RVA // // Return value: "true" if succeeded, "false" if failed // bool GetFileOffsetFromRVA( PIMAGE_NT_HEADERS pNtHeaders, DWORD Rva, DWORD& FileOffset ) { // Check parameters if( pNtHeaders == 0 ) { _ASSERT( 0 ); return false; } // Look up the section the RVA belongs to bool bFound = false; PIMAGE_SECTION_HEADER pSectionHeader = IMAGE_FIRST_SECTION( pNtHeaders ); for( int i = 0; i < pNtHeaders->FileHeader.NumberOfSections; i++, pSectionHeader++ ) { DWORD SectionSize = pSectionHeader->Misc.VirtualSize; if( SectionSize == 0 ) // compensate for Watcom linker strangeness, according to Matt Pietrek pSectionHeader->SizeOfRawData; if( ( Rva >= pSectionHeader->VirtualAddress ) && ( Rva < pSectionHeader->VirtualAddress + SectionSize ) ) { // Yes, the RVA belongs to this section bFound = true; break; } } if( !bFound ) { // Section not found return false; } // Look up the file offset using the section header INT Diff = (INT)( pSectionHeader->VirtualAddress - pSectionHeader->PointerToRawData ); FileOffset = Rva - Diff; return true; } // // Display information about CodeView debug information block // bool DumpCodeViewDebugInfo( LPBYTE pDebugInfo, DWORD DebugInfoSize, LPTSTR DebugDir ) { // Check parameters if( ( pDebugInfo == 0 ) || ( DebugInfoSize == 0 ) ) return false; if( IsBadReadPtr( pDebugInfo, DebugInfoSize ) ) return false; if( DebugInfoSize < sizeof(DWORD) ) // size of the signature return false; // Determine the format of the information and display it accordingly DWORD CvSignature = *(DWORD*)pDebugInfo; if( CvSignature == CV_SIGNATURE_NB10 ) { // NB10 -> PDB 2.00 CV_INFO_PDB20* pCvInfo = (CV_INFO_PDB20*)pDebugInfo; if( IsBadReadPtr( pDebugInfo, sizeof(CV_INFO_PDB20) ) ) return false; if( IsBadStringPtrA( (CHAR*)pCvInfo->PdbFileName, UINT_MAX ) ) return false; strcpy(DebugDir, (const char*)pCvInfo->PdbFileName); return true; } else if( CvSignature == CV_SIGNATURE_RSDS ) { // RSDS -> PDB 7.00 CV_INFO_PDB70* pCvInfo = (CV_INFO_PDB70*)pDebugInfo; if( IsBadReadPtr( pDebugInfo, sizeof(CV_INFO_PDB70) ) ) return false; if( IsBadStringPtrA( (CHAR*)pCvInfo->PdbFileName, UINT_MAX ) ) return false; strcpy(DebugDir, (const char*)pCvInfo->PdbFileName); return true; } return false; } // // Display information about debug directory entry // bool DumpDebugDirectoryEntry( LPBYTE pImageBase, PIMAGE_DEBUG_DIRECTORY pDebugDir, LPTSTR DebugDir ) { // Check parameters if( pDebugDir == 0 ) { _ASSERT( 0 ); return false; } if( pImageBase == 0 ) { _ASSERT( 0 ); return false; } // Display additional information for some interesting debug information types LPBYTE pDebugInfo = pImageBase + pDebugDir->PointerToRawData; if( pDebugDir->Type == IMAGE_DEBUG_TYPE_CODEVIEW ) { return DumpCodeViewDebugInfo( pDebugInfo, pDebugDir->SizeOfData, DebugDir ); } return false; } // // Walk through each entry in the debug directory and display information about it // bool DumpDebugDirectoryEntries( LPBYTE pImageBase, PIMAGE_DEBUG_DIRECTORY pDebugDir, DWORD DebugDirSize, LPTSTR DebugDir ) { // Check parameters if( pImageBase == 0 ) { _ASSERT( 0 ); return false; } // Determine the number of entries in the debug directory int NumEntries = DebugDirSize / sizeof(IMAGE_DEBUG_DIRECTORY); if( NumEntries == 0 ) { _ASSERT( 0 ); return false; } // Display information about every entry for( int i = 1; i <= NumEntries; i++, pDebugDir++ ) { if (DumpDebugDirectoryEntry( pImageBase, pDebugDir, DebugDir )) return true; } return false; } /////////////////////////////////////////////////////////////////////////////// // main // bool GetPdbFileName(LPCTSTR FileName, LPTSTR DebugDir) { // Process the command line and obtain the file name if( FileName == 0 ) return 0; // Process the file HANDLE hFile = NULL; HANDLE hFileMap = NULL; LPVOID lpFileMem = 0; bool bOK = false; do { // Open the file and map it into memory hFile = CreateFile( FileName, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL ); if( ( hFile == INVALID_HANDLE_VALUE ) || ( hFile == NULL ) ) { break; } hFileMap = CreateFileMapping( hFile, NULL, PAGE_READONLY, 0, 0, NULL ); if( hFileMap == NULL ) { break; } lpFileMem = MapViewOfFile( hFileMap, FILE_MAP_READ, 0, 0, 0 ); if( lpFileMem == 0 ) { break; } PIMAGE_DOS_HEADER pDosHeader = (PIMAGE_DOS_HEADER)lpFileMem; PIMAGE_NT_HEADERS pNtHeaders = MakePtr( PIMAGE_NT_HEADERS, pDosHeader, pDosHeader->e_lfanew ); // Look up the debug directory DWORD DebugDirRva = 0; DWORD DebugDirSize = 0; if( !GetDebugDirectoryRVA( &pNtHeaders->OptionalHeader, DebugDirRva, DebugDirSize ) ) { break; } if( ( DebugDirRva == 0 ) || ( DebugDirSize == 0 ) ) { break; } DWORD DebugDirOffset = 0; if( !GetFileOffsetFromRVA( pNtHeaders, DebugDirRva, DebugDirOffset ) ) { break; } PIMAGE_DEBUG_DIRECTORY pDebugDir = MakePtr( PIMAGE_DEBUG_DIRECTORY, lpFileMem, DebugDirOffset ); // Display information about every entry in the debug directory if (!DumpDebugDirectoryEntries( (LPBYTE)lpFileMem, pDebugDir, DebugDirSize, DebugDir )) break; bOK = true; } while (false); // Cleanup if( lpFileMem != 0 ) { if( !UnmapViewOfFile( lpFileMem ) ) { _ASSERT( 0 ); } } if( hFileMap != NULL ) { if( !CloseHandle( hFileMap ) ) { _ASSERT( 0 ); } } if( ( hFile != NULL ) && ( hFile != INVALID_HANDLE_VALUE ) ) { if( !CloseHandle( hFile ) ) { _ASSERT( 0 ); } } // Complete return bOK; } /////////////////////////////////////////////////////////////////////////////// enum { MAXNAMELENGTH = 1024 }; // max name length for found symbols struct ModuleEntry { string imageName; string moduleName; DWORD64 baseAddress; DWORD size; }; typedef vector<ModuleEntry> ModuleList; bool GetModuleList(ModuleList& modules, DWORD pid) { HANDLE hSnap = CreateToolhelp32Snapshot( TH32CS_SNAPMODULE, pid ); if (hSnap == (HANDLE) -1) return false; MODULEENTRY32 me; me.dwSize = sizeof(me); for (BOOL ok = Module32First(hSnap, &me) ; ok ; ok = Module32Next(hSnap, &me)) { ModuleEntry e; e.imageName = me.szExePath; e.moduleName = me.szModule; e.baseAddress = (DWORD64) me.modBaseAddr; e.size = me.modBaseSize; modules.push_back(e); } CloseHandle(hSnap); return !modules.empty(); } std::string GetModuleDebugSearchPath(HMODULE hModule) { const int BUF_SIZE = 10000; CHAR tt[BUF_SIZE] = ""; string semicolon(";"); // build symbol search path from: string symSearchPath = ""; // current directory if ( GetCurrentDirectoryA( BUF_SIZE, tt ) ) symSearchPath += tt + semicolon; // dir with executable if ( GetModuleFileNameA( 0, tt, BUF_SIZE ) ) { PathRemoveFileSpec(tt); symSearchPath += tt + semicolon; } if ( GetEnvironmentVariableA( "_NT_SYMBOL_PATH", tt, BUF_SIZE ) ) symSearchPath += tt + semicolon; if ( GetEnvironmentVariableA( "_NT_ALTERNATE_SYMBOL_PATH", tt, BUF_SIZE ) ) symSearchPath += tt + semicolon; if ( GetEnvironmentVariableA( "SYSTEMROOT", tt, BUF_SIZE ) ) symSearchPath += tt + semicolon; if (hModule != NULL && GetModuleFileNameA(hModule, tt, BUF_SIZE) && GetPdbFileName(tt, tt)) { PathRemoveFileSpec(tt); symSearchPath += tt + semicolon; } if ( symSearchPath.size() > 0 ) // if we added anything, we have a trailing semicolon symSearchPath = symSearchPath.substr( 0, symSearchPath.size() - 1 ); return symSearchPath; } void EnumAndLoadModuleSymbols(HANDLE hProcess, DWORD pid) { ModuleList modules; // fill in module list GetModuleList(modules, pid); for (ModuleList::iterator it(modules.begin()); it != modules.end(); ++it) { string sPath = GetModuleDebugSearchPath((HMODULE)it->baseAddress); SymSetSearchPath(hProcess, const_cast<char*>(sPath.c_str())); DWORD64 addr = SymLoadModule64( hProcess, 0, const_cast<char*>(it->imageName.c_str()), const_cast<char*>(it->moduleName.c_str()), it->baseAddress, it->size ); } } HMODULE ModuleFromAddress(LPCVOID pv) { MEMORY_BASIC_INFORMATION mbi; return (VirtualQuery(pv, &mbi, sizeof(mbi)) != 0) ? (HMODULE) mbi.AllocationBase : NULL; } template <typename T> void DoStackTrace( HANDLE hThread, CONTEXT& c, const T fLogFile, HANDLE hSWProcess) { HANDLE hProcess = GetCurrentProcess(); struct { IMAGEHLP_SYMBOL64 sym; char name[MAXNAMELENGTH]; } symBuffer = {0}; IMAGEHLP_SYMBOL64* const pSym = &symBuffer.sym; IMAGEHLP_MODULE64 Module; IMAGEHLP_LINE64 Line; static bool bInitialized = false; if (!bInitialized) { HMODULE hModule = ModuleFromAddress(&ModuleFromAddress); string symSearchPath = GetModuleDebugSearchPath(hModule); if (!SymInitialize(hProcess, const_cast<char*>(symSearchPath.c_str()), false)) { _ftprintf(fLogFile, _T("SymInitialize(): GetLastError = %lu\n"), GetLastError()); return; } DWORD symOptions = SymGetOptions(); symOptions |= SYMOPT_LOAD_LINES; symOptions &= ~(SYMOPT_UNDNAME | SYMOPT_DEFERRED_LOADS); SymSetOptions( symOptions ); bInitialized = true; } EnumAndLoadModuleSymbols(hProcess, GetCurrentProcessId()); STACKFRAME64 s = {0}; // init STACKFRAME for first call #if defined(_M_IX86) s.AddrPC.Offset = c.Eip; s.AddrStack.Offset = c.Esp; s.AddrFrame.Offset = c.Ebp; #else s.AddrPC.Offset = c.Rip; s.AddrStack.Offset = c.Rsp; s.AddrFrame.Offset = c.Rbp; #endif s.AddrPC.Mode = AddrModeFlat; s.AddrStack.Mode = AddrModeFlat; s.AddrFrame.Mode = AddrModeFlat; pSym->SizeOfStruct = sizeof(IMAGEHLP_SYMBOL64); pSym->MaxNameLength = MAXNAMELENGTH; memset( &Line, '\0', sizeof Line ); Line.SizeOfStruct = sizeof Line; memset( &Module, '\0', sizeof Module ); Module.SizeOfStruct = sizeof Module; CONTEXT cCopy(c); do { if (!StackWalk64( #if defined(_M_IX86) IMAGE_FILE_MACHINE_I386, #else IMAGE_FILE_MACHINE_AMD64, #endif hSWProcess, hThread, &s, &cCopy, NULL, &SymFunctionTableAccess64, &SymGetModuleBase64, NULL)) { break; } HMODULE hModule = ModuleFromAddress((LPCVOID)s.AddrPC.Offset); char szModuleName[MAX_PATH] = ""; GetModuleFileName(hModule, szModuleName, MAX_PATH); if (s.AddrPC.Offset != 0) { char undecoratedName[MAXNAMELENGTH] = ""; DWORD64 offsetFromSymbol = 0; BOOL hasSymbols = SymGetSymFromAddr64(hProcess, s.AddrPC.Offset, &offsetFromSymbol, pSym); if (hasSymbols) UnDecorateSymbolName(pSym->Name, undecoratedName, MAXNAMELENGTH, UNDNAME_NAME_ONLY); DWORD offsetFromLine = 0; if ( ! SymGetLineFromAddr64( hProcess, s.AddrPC.Offset, &offsetFromLine, &Line ) ) { if (hasSymbols) _ftprintf(fLogFile, "%s: %s (+%d bytes)\n", szModuleName, undecoratedName, (long) offsetFromSymbol); else _ftprintf(fLogFile, "%s: (0x%08X + 0x%X bytes)\n", szModuleName, (DWORD)hModule, ((DWORD)s.AddrPC.Offset) - (DWORD)hModule); } else { _ftprintf(fLogFile, "%s(%lu): %+ld bytes (%s)\n", Line.FileName, Line.LineNumber, offsetFromLine, undecoratedName); } } } while (s.AddrReturn.Offset != 0); } struct CriticalSection : public CRITICAL_SECTION { CriticalSection() { InitializeCriticalSection(this); }; ~CriticalSection() { DeleteCriticalSection(this); }; }; static CriticalSection g_csStackTrace; template <typename T> void StackTrace( HANDLE hThread, CONTEXT& c, const T fLogFile, HANDLE hSWProcess) { EnterCriticalSection(&g_csStackTrace); DoStackTrace(hThread, c, fLogFile, hSWProcess) ; LeaveCriticalSection(&g_csStackTrace); } // OutputDebugExceptionStackTrace() implementation void _ftprintf(void (__stdcall * const OutputDebugStringFunc)(LPCTSTR), const TCHAR *format, ...) { enum { BUFFER_SIZE = 4000 }; TCHAR buffer[BUFFER_SIZE]; va_list vl; va_start(vl, format); _vsntprintf(buffer, BUFFER_SIZE - 1, format, vl); buffer[BUFFER_SIZE - 1] = 0; va_end(vl); OutputDebugStringFunc(buffer); } // See http://www.ddj.com/windows/184416600 #ifdef _MT extern "C" { // merged from VC 6, .NET and 2005 internal headers in CRT source code struct _tiddata { unsigned long _tid; /* thread ID */ #if _MSC_VER >= 1400 uintptr_t _thandle; /* thread handle */ #else unsigned long _thandle; /* thread handle */ #endif int _terrno; /* errno value */ unsigned long _tdoserrno; /* _doserrno value */ unsigned int _fpds; /* Floating Point data segment */ unsigned long _holdrand; /* rand() seed value */ char * _token; /* ptr to strtok() token */ wchar_t * _wtoken; /* ptr to wcstok() token */ unsigned char * _mtoken; /* ptr to _mbstok() token */ /* following pointers get malloc'd at runtime */ char * _errmsg; /* ptr to strerror()/_strerror() buff */ #if _MSC_VER >= 1300 wchar_t * _werrmsg; /* ptr to _wcserror()/__wcserror() buff */ #endif char * _namebuf0; /* ptr to tmpnam() buffer */ wchar_t * _wnamebuf0; /* ptr to _wtmpnam() buffer */ char * _namebuf1; /* ptr to tmpfile() buffer */ wchar_t * _wnamebuf1; /* ptr to _wtmpfile() buffer */ char * _asctimebuf; /* ptr to asctime() buffer */ wchar_t * _wasctimebuf; /* ptr to _wasctime() buffer */ void * _gmtimebuf; /* ptr to gmtime() structure */ char * _cvtbuf; /* ptr to ecvt()/fcvt buffer */ #if _MSC_VER >= 1400 unsigned char _con_ch_buf[MB_LEN_MAX]; /* ptr to putch() buffer */ unsigned short _ch_buf_used; /* if the _con_ch_buf is used */ #endif /* following fields are needed by _beginthread code */ void * _initaddr; /* initial user thread address */ void * _initarg; /* initial user thread argument */ /* following three fields are needed to support * signal handling and * runtime errors */ void * _pxcptacttab; /* ptr to exception-action table */ void * _tpxcptinfoptrs; /* ptr to exception info pointers*/ int _tfpecode; /* float point exception code */ #if _MSC_VER >= 1300 /* pointer to the copy of the multibyte character * information used by the thread */ /*pthreadmbcinfo*/ void * ptmbcinfo; /* pointer to the copy of the locale informaton * used by the thead */ /*pthreadlocinfo*/ void * ptlocinfo; #endif #if _MSC_VER >= 1400 int _ownlocale; /* if 1, this thread owns its own locale */ #endif /* following field is needed by NLG routines */ unsigned long _NLG_dwCode; #if _MSC_VER == 1200 && !defined(_DEBUG) && defined(_DLL) void *dummy1, *dummy2; // Weird misalignment in msvcrt.dll fixed #endif /* * Per-Thread data needed by C++ Exception Handling */ void * _terminate; /* terminate() routine */ void * _unexpected; /* unexpected() routine */ void * _translator; /* S.E. translator */ #if _MSC_VER >= 1400 void * _purecall; /* called when pure virtual happens */ #endif void * _curexception; /* current exception */ void * _curcontext; /* current exception context */ #if _MSC_VER >= 1300 int _ProcessingThrow; /* for uncaught_exception */ #endif }; typedef struct _tiddata * _ptiddata; _ptiddata __cdecl _getptd(); } #ifdef _DLL CONTEXT* GetCurrentExceptionContext() { _tiddata* pTiddata = (_tiddata*)(((BYTE*) __pxcptinfoptrs()) - offsetof(_tiddata, _tpxcptinfoptrs)); return (CONTEXT*) pTiddata->_curcontext; } #else CONTEXT* GetCurrentExceptionContext() { _tiddata* p = _getptd(); return (CONTEXT*) p->_curcontext; } #endif #else extern CONTEXT* _pCurrentExContext; CONTEXT* GetCurrentExceptionContext() { return _pCurrentExContext; } #endif void OutputDebugExceptionStackTrace() { CONTEXT* pEC = GetCurrentExceptionContext(); if (pEC != NULL) { HANDLE hThread = NULL; DuplicateHandle( GetCurrentProcess(), GetCurrentThread(), GetCurrentProcess(), &hThread, 0, false, DUPLICATE_SAME_ACCESS ); StackTrace( hThread, *pEC, OutputDebugString, GetCurrentProcess()); CloseHandle( hThread ); } } void GetTheAnswer() { throw 42; } int main(int argc, char* argv[]) { try { GetTheAnswer(); } catch (...) { OutputDebugExceptionStackTrace(); } return 0; } (Comment on this)
Friday, May 1st, 2009
2:04 pm	We are the champions! Study Brands Minsk Worst City In Europe (Comment on this)
Friday, April 10th, 2009
4:18 pm	Opus #10 from Outer Space #include <atldbcli.h> #include <OLEDBERR.H> #include <algorithm> #include <vector> // Generic numeric transformer from one radix to another. // Divides array elements one by one, // reverses output sequence to preserve order. // Modifies input data as well. template <typename TRAITS, typename INTYPE, typename OUTTYPE> inline void TransformRadix(OUTTYPE* out, int outSize, INTYPE* in, int inSize) { for (int j = outSize; j--; ) { unsigned long ulBuf = ((in[0] % TRAITS::EOutRadix) * TRAITS::EInRadix) + in[1]; in[0] /= TRAITS::EOutRadix; for (int i = 1; i < inSize - 1; ++i) { in[i] = static_cast<INTYPE>(ulBuf / TRAITS::EOutRadix); ulBuf = ((ulBuf % TRAITS::EOutRadix) * TRAITS::EInRadix) + in[i + 1]; } in[inSize - 1] = static_cast<INTYPE>(ulBuf / TRAITS::EOutRadix); out[j] = static_cast<OUTTYPE>(ulBuf % TRAITS::EOutRadix); } } struct TraitsB2A { enum { EInRadix = 0x00000100, EOutRadix = 10, }; }; inline void ThrowIfFailed(HRESULT hr, LPCSTR szExpr) { if (FAILED(hr)) { CString s; s.Format("Failure in %s: %d", szExpr, hr); throw s; } } #define CHECK_HR(expr) \ if (false); \ else for (HRESULT hr, b = true; b; ThrowIfFailed(hr, #expr), b = false) \ hr = expr #define CHECK_NOT_NULL(expr) \ if ((expr) != NULL); \ else throw CString(#expr " is null"); CString GetVarNumeric(IUnknown* res1, long columnOrdinal) // OLE DB column index starts with 1 { ADODB::ADORecordsetConstructionPtr adoRecordsetConstruction(res1); CHECK_NOT_NULL(adoRecordsetConstruction); CComQIPtr<IRowset> spIRowset(adoRecordsetConstruction->GetRowset()); CHECK_NOT_NULL(spIRowset); CComQIPtr<IColumnsInfo> spIColumnsInfo(spIRowset); CHECK_NOT_NULL(spIColumnsInfo); DBBINDING dbBinding; bool bOK = false; { ULONG cColumns; DBCOLUMNINFO * prgInfo; OLECHAR * pStringsBuffer; CHECK_HR(spIColumnsInfo->GetColumnInfo)(& cColumns, & prgInfo, & pStringsBuffer); // prgInfo[idx].wType will be DBTYPE_VARNUMERIC == 139 int idx; for (idx = cColumns; --idx >= 0; ) { if (columnOrdinal == prgInfo[idx].iOrdinal) break; } bOK = idx != -1 && DBTYPE_VARNUMERIC == prgInfo[idx].wType; if (bOK) { dbBinding.iOrdinal = prgInfo[idx].iOrdinal; dbBinding.obValue = 0; dbBinding.obLength = 0; dbBinding.obStatus = 0; dbBinding.pTypeInfo = NULL; dbBinding.pObject = NULL; dbBinding.pBindExt = NULL; dbBinding.dwPart = DBPART_VALUE; dbBinding.dwMemOwner = DBMEMOWNER_CLIENTOWNED; dbBinding.eParamIO = DBPARAMIO_NOTPARAM; dbBinding.cbMaxLen = prgInfo[idx].ulColumnSize; dbBinding.dwFlags = prgInfo[idx].dwFlags; dbBinding.wType = prgInfo[idx].wType; dbBinding.bPrecision = prgInfo[idx].bPrecision; dbBinding.bScale = prgInfo[idx].bScale; } CComPtr<IMalloc> spMalloc; if (SUCCEEDED(CoGetMalloc(1, &spMalloc)) && spMalloc != NULL) { spMalloc->Free( pStringsBuffer ); spMalloc->Free( prgInfo ); } } if (!bOK) throw CString("No DBTYPE_VARNUMERIC type column found"); CComQIPtr<IAccessor> spIAccessor(spIRowset); CHECK_NOT_NULL(spIAccessor); HACCESSOR hAccessor; DBBINDSTATUS DBBindStatus[2]; CHECK_HR(spIAccessor->CreateAccessor)(DBACCESSOR_ROWDATA, 1, &dbBinding, dbBinding.cbMaxLen, & hAccessor, DBBindStatus); CString value; try { HROW rghRows; CComQIPtr<IRowPosition> spRowPosition(adoRecordsetConstruction->GetRowPosition()); CHECK_NOT_NULL(spRowPosition); CHECK_HR(spRowPosition->GetRowPosition)(NULL, &rghRows, NULL); // add 3 bytes for precision, scale, and sign std::vector<BYTE> buffer(dbBinding.cbMaxLen + 3); CHECK_HR(spIRowset->GetData)(rghRows, hAccessor, &buffer[0]); DB_VARNUMERIC* pVar = (DB_VARNUMERIC*) &buffer[0]; int prec = ( int ) pVar->precision; int scale = ( int ) pVar->scale; std::reverse(pVar->val, pVar->val + dbBinding.cbMaxLen); LPTSTR buf = value.GetBuffer(prec); TransformRadix<TraitsB2A>(buf, prec, pVar->val, dbBinding.cbMaxLen); for (int i = 0; i < prec; ++i) buf[i] += '0'; buf[prec] = 0; // Ending zero value.ReleaseBuffer(); if (scale > 0 && scale <= prec) { value.Insert(prec - scale, '.'); } else if (scale != 0) { CString tmp(value); value.Format(".%se%d", tmp, prec - scale); } if (pVar->sign <= 0) value = '-' + value; } catch (...) { spIAccessor->ReleaseAccessor(hAccessor, NULL); throw; } spIAccessor->ReleaseAccessor(hAccessor, NULL); return value; } (Comment on this)
Monday, April 6th, 2009
4:22 pm	Opus #9 from Outer Space #include <stdlib.h> #include <assert.h> #include <vector> #include <algorithm> #include <iostream> typedef std::vector<unsigned int> LongNumber; LongNumber& operator *= (LongNumber& n1, int n2) { if (0 == n2) n1.clear(); else { __int64 buf = 0; for (LongNumber::iterator it(n1.begin()); it != n1.end(); ++it) { buf += (*it) * (__int64) n2; *it = (unsigned int) buf; buf >>= (sizeof(int) * 8); } if (buf != 0) n1.push_back((unsigned int) buf); } return n1; } LongNumber& operator /= (LongNumber& n1, int n2) { __int64 buf = 0; for (LongNumber::reverse_iterator it(n1.rbegin()); it != n1.rend(); ++it) { buf += (*it); (*it) = (unsigned int) (buf / n2); buf = (buf % n2) << (sizeof(int) * 8); } assert (0 == buf); size_t size = n1.size(); if (size != 0 && 0 == n1[size - 1]) n1.resize(size - 1); return n1; } LongNumber& operator += (LongNumber& n1, const LongNumber& n2) { if (n1.size() < n2.size()) n1.resize(n2.size()); __int64 buf = 0; LongNumber::iterator it1(n1.begin()); for (LongNumber::const_iterator it2(n2.begin()) ; it2 != n2.end(); ++it1, ++it2) { buf += (*it1); buf += (*it2); *it1 = (unsigned int) buf; buf >>= (sizeof(int) * 8); } for (; it1 != n1.end() && buf != 0; ++it1) { buf += (*it1); *it1 = (unsigned int) buf; buf >>= (sizeof(int) * 8); } if (buf != 0) n1.push_back((unsigned int) buf); return n1; } LongNumber& operator -= (LongNumber& n1, const LongNumber& n2) { assert(n1.size() >= n2.size()); __int64 buf = 0; LongNumber::iterator it1(n1.begin()); for (LongNumber::const_iterator it2(n2.begin()) ; it2 != n2.end(); ++it1, ++it2) { buf += (*it1); buf -= (*it2); *it1 = (unsigned int) buf; buf >>= (sizeof(int) * 8); } for (; it1 != n1.end() && buf != 0; ++it1) { buf += (*it1); *it1 = (unsigned int) buf; buf >>= (sizeof(int) * 8); } assert(0 == buf); LongNumber::reverse_iterator it(n1.rbegin()); for (; it != n1.rend(); ++it) if (0 != (*it)) { size_t delta = it - n1.rbegin(); if (delta != 0) { n1.resize(n1.size() - delta); it = n1.rbegin() + delta - 1; } break; } if (n1.rend() == it) n1.clear(); return n1; } bool operator < (const LongNumber& n1, const LongNumber& n2) { if (n1.size() < n2.size()) return true; if (n1.size() > n2.size()) return false; return std::lexicographical_compare( n1.rbegin(), n1.rend(), n2.rbegin(), n2.rend()); } enum { MEMBER_SIZE = 0x10000 }; template <typename T> class CombTemplate { public: void Process() { int m = static_cast<T*>(this)->GetSize(); LongNumber l; l.push_back(MEMBER_SIZE - 1); for (int i = 2; i <= m; ++i) { l *= (MEMBER_SIZE - i); l /= i; } int n = MEMBER_SIZE - 1; for (; m > 0; --m) { bool elementProcessed; do { elementProcessed = static_cast<T*>(this)->ElementProcessed(l, m - 1, n); l *= elementProcessed? m : (n - m); l /= n; --n; } while(!elementProcessed); } } }; class CombEncoder : public CombTemplate<CombEncoder> { int m_size; const unsigned short* m_pdata; LongNumber& m_encodedData; public: int GetSize() const { return m_size; } bool ElementProcessed(LongNumber& l, int m, int n) { if (m_pdata[m] == n) { m_encodedData += l; return true; } return false; } public: template <typename T> CombEncoder(const T& data, LongNumber& encodedData) : m_pdata(data), m_size(sizeof(data) / sizeof(data[0])) , m_encodedData(encodedData) {} }; class CombDecoder : public CombTemplate<CombDecoder> { int m_size; unsigned short* m_pdata; LongNumber& m_encodedData; public: int GetSize() const { return m_size; } bool ElementProcessed(LongNumber& l, int m, int n) { if (!(m_encodedData < l)) { m_encodedData -= l; m_pdata[m] = n; return true; } return false; } public: template <typename T> CombDecoder(T& data, LongNumber& encodedData) : m_pdata(data), m_size(sizeof(data) / sizeof(data[0])) , m_encodedData(encodedData) {} }; template<typename T> void Stuff(T& data) { unsigned int val = rand(); for (int i = 0; i < sizeof(data) / sizeof(data[0]); ++i) { unsigned short* p; do { val = (val << 15) + rand(); } while ((p = std::lower_bound(data, data+i, (unsigned short) val)) != data+i && *p == (unsigned short) val); memmove(p + 1, p, (data + i - p) * sizeof(unsigned short)); *p = (unsigned short) val; } } int main(int argc, char* argv[]) { typedef unsigned short BUFFER[30]; BUFFER data; Stuff(data); LongNumber encodedData; CombEncoder encoder(data, encodedData); encoder.Process(); std::cout << "Compressed set size is " << encodedData.size() * sizeof(int) << " bytes.\nDecoding "; BUFFER restoredData; CombDecoder decoder(restoredData, encodedData); decoder.Process(); std::cout << ((0 == memcmp(data, restoredData, sizeof(data))) ? "succeeded" : "failed") << ".\n"; return 0; } (Comment on this)
11:44 am	"Minsk - Out Of A Center Which Is Neither Dead Nor Alive" Paul McCartney wrote this. It's about a man who is considered a fool by others, but whose foolish demeanor is actually an indication of wisdom. An event which prompted this song happened when Paul was walking his dog Martha, on Primrose Hill one morning. As he watched the sun rise, he noticed that Martha was missing. Paul turned around to look for his dog, and there a man stood, who appeared on the hill without making a sound. The gentleman was dressed respectably, in a belted raincoat. Paul knew this man had not been there seconds earlier as he had looked in that direction for Martha. Paul and the stranger exchanged a greeting, and this man then spoke of what a beautiful view it was from the top of this hill that overlooked London. Within a few seconds, Paul looked around again, and the man was gone. He had vanished as he had appeared. A friend of McCartney's, Alistair Taylor, was present with Paul during this strange incident, and wrote of this event in his book, Yesterday. http://www.songfacts.com/detail.php?id=134 (Comment on this)