Use Iterator to decouple your algorithm from your container...

Today, I had to implement a function to check error between data contains in different kind of container. Typically the data type can be int, float or double, store in std::vector or boost::numeric::ublas vector and matrix.

It's here that template and iterator pattern have to be use to decouple the algorithm/function implementation of the container implementation.

template<class InputIteratorT1, typename InputIteratorT2> void CheckEqualForGivenAccuracy( InputIteratorT1 first_left, InputIteratorT1 last_left, InputIteratorT2 first_right, InputIteratorT2 last_right, double tstEspilon = (double)std::numeric_limits<typename InputIteratorT1::value_type>::epsilon(), std::ostream& stream = null_ostream )

{

  CHECK(std::distance(first_left, last_left) && std::distance(first_right, last_right));

  stream << std::string(__FUNCTION__) << " of " << std::distance(first_left, last_left) << " elements with epsilon = " << tstEspilon << std::endl;

 

  unsigned int nb_error = 0;

  double sum_abs_diff = 0.0;

  double max_diff = 0.0;

  double min_diff = 0.0;

  while(first_left != last_left)

  {

    if(fabs((double)*first_left - (double)*first_right) > tstEspilon)

    {

      nb_error++;

      double diff = (double)*first_left - (double)*first_right;

      sum_abs_diff += std::abs<double>(diff);

      max_diff = std::max(max_diff, diff);

      min_diff = std::min(min_diff, diff);     

    }

    first_left++; first_right++;

  }

  if(nb_error > 0)

  {

    stream << std::string(__FUNCTION__) << " error= " << nb_error << " sum_abs_diff = " << sum_abs_diff << " max_diff = " << max_diff << " min_diff = " << min_diff << std::endl;

  }

 

  CHECK(nb_error == 0);

}

That implementation is range-based, the 2 data type can be different ((internally a promotion to double is made), and we have 2 optional parameters, one to specify the error limit and the second to log message. By default the error limit use the standard epsilon value from the numeric type_trait class, and the ostream my implementation of a /dev/null output.

I like Javascript .....

I'm not a Javascript expert, but the thing I really like with Javascript and our modern Web-Browser is that they allow you to customize your web exeprience....

Today the 'most important news' for me was that the 1st Thor 2 trailer was release, but while clicking on the link i had in my RSS feed, I got a "da.feedsportal.com" before going on my real target !

Hopefully there is link where you can click on the skip that 'ad'.
So now just let Javascript perform the click for you...

Using greasemonkey (Firefox & Chrome) and the following script, you can skip those 'ad' ...

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

 // ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

Provide your own allocator for std::vector or boost storage

If you plan to write some optimized code (SIMD code like SSE or MMX) using memory coming from a standard container (std::vector or boost::numeric::ublas::unbounded_array), your may be interested by the following.


#include <stdlib.h>//linux aligned malloc
#include <malloc.h>
#if defined(WIN32) || defined(WIN64)
#define simd_alloc(alignment, len) _aligned_malloc(len, alignment)
#define simd_free _aligned_free
#else
#define simd_alloc(alignment, len) memalign(alignment, len)
#define simd_free free
#endif

template<typename T>
class aligned_allocator : public std::allocator<T>
{
public:
void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
simd_free(_Ptr);
}

pointer allocate(size_type _Count)
{ // allocate array of _Count elements
return (T*)simd_alloc(16, _Count*sizeof(T));
}
};



using that allocator class, you can create a vector like:


template struct myType
{
typedef boost::numeric::ublas::vector<T, boost::numeric::ublas::unbounded_array<T, aligned_allocator<T> > > boost_vector;
typedef std::vector<T, aligned_allocator<T> > std_vector;
};


An interview question

I had an job interview, and the interviewer had a cool technical and language agnostic question.... He just put the focus on algorithms and their complexity.

The problem was: What is the original complexity of the following function, how to optimize it and what is the resulting complexity.

The function was a common box filter where each output pixel is the sum of the each input pixel around him in a KxK area. And just add some 'noise' in the reflexion he said that the 2-dimensional image was a WxH plane.

So let use some math notation to express that:

$$P\text{'}(x,y)=\sum _{i=\frac{-k}{2}}^{\frac{k}{2}}\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+i,y+j)$$

Looking at that formula, the complexity is clearly O($$k^2$$).

Now let express P' iteratively:
$$\begin{array}{l}P\text{'}(x+1,y)=\sum _{i=\frac{-k}{2}}^{\frac{k}{2}}\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+i,y+j)+\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+1+\frac{k}{2},y+j)-\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x-\frac{k}{2},y+j)\\ \end{array}$$
or ....
$$P\text{'}(x+1,y)=P\text{'}(x,y)+\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x+1+\frac{k}{2},y+j)-\sum _{j=\frac{-k}{2}}^{\frac{k}{2}}P(x-\frac{k}{2},y+j)$$

So now the complexity is O(2k)! and if you use a k-vector store the sum of each column, and use that sliding window process, a correct implementation will be in O(k+1)

How to check if an executable is 32bit or 64bit

On windows, using dumpbin.exe what you should have in your PATH if you launch a Visual studio command line or if you run the vsvars.bat ("C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\Tools\vsvars32.bat")

>dumpbin.exe path_to_executable.exe /HEADERS

And on linux, just use file

>file path_to_executable

Google API is really easy to use ....

2 weeks ago i spend 1 or 2 hour looking how work the Google Map API (http://hpneo.github.io/gmaps/). The Example page provide helpful piece of code as below.
I put the map focus somewhere .... using latitude and longitude coordinate (48.13199070073399, -1.6228169202804565).

Debugging Tips: Exporting a bunch of memory without instrumenting thecode!

Context and problem:

In the last 3 weeks, I worked on aligning a C/C++ code with its Matlab equivalent. During that task I came across the following problem.... I had to compare the data and the program state from C/C++ and Matlab code during 2 parallel debugging session,. So how can we debug and save at any time a C++ vector as binary file without adding noisy instrumentation code?

1 2 3 4

std::vector<double> vec(10); std::ofstream output("out.bin", std::ios::binary|std::ios::out); output.write(reinterpret_cast<char*>(&vec[0]), vec.size()*sizeof(vec[0])); output.close();

 And when the file is ready, write in Matlab (for example):
vec_from_c_code = read(open('out.bin'), 'double');
sum(abs(vec_from_c_code - vec_in_matlab))

It could be a debugger feature:

That's why as usual, I first googled it, but I didn't find something ready to use.....

• http://www.codeproject.com/Articles/177344/VSDebugHelper-Capture-memory-snapshot-of-a-debugge

• http://stackoverflow.com/questions/4155624/save-data-from-visual-studio-memory-window
• http://stackoverflow.com/questions/1301251/dump-only-a-portion-of-memory-in-vs-2005

I used Visual Studio 2008 IDE to develop and debug, and it's a really good tools, but it doesn't contain that feature. Using the "memory windows" developer can just see the program memory in hexadecimal and eventually copy a part of it as Text.

With WinDbg, you should have access to a ".writemem" function, and it looks like some extension for VS'2010 to support that syntax from the "Immediate console".... So if its your case, search on http://visualstudiogallery.msdn.microsoft.com/

In another hand Matlab come with an API to directly feed in realtime data from C/C++ (and maybe others languages) in a Matlab session for vizualisation, etc.... But it's something I would found in a production code.

So I build it by myself based on some informations found in the previous page, my own command line.

A solution:

The code below is a simple usage of the 2 function win32 API, OpenProcess and ReadProcessMemory (more details on MSDN). I call this tool a ProcessMemDumper....  evolutions of this code, using a Write function can be made to replace the memory of the program with data coming from file during a debugging session.
Using your debugger, your are going step-by-step through your program, you found for example a "std::vector vec;" that you want to see in another tools (Matlab in my case). You need 3 things, pickup from a simple debugger watch:

• the offset in the process memory , &vec[0],
• and the number of bytes, vec size * 8(size of double)

Also get the process PID, and  call from a command line:

• processmemdumper.exe PID offset nbbytes  out.bin

 Really more efficient than adding export source code everywhere....

Source code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

// ProcessMemDumper.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <windows.h> #include <string> #include <iostream> #include <fstream> #include <vector> #include <stdexcept> #include <sstream> #include "boost/shared_ptr.hpp" void delete_HANDLE(HANDLE p) { std::cout << "Releasing Handle ...." << std::endl; CloseHandle(p); }; int _tmain(int argc, _TCHAR* argv[]) { try { unsigned int procPID = atoi(argv[1]); std::string procAddressHexa = std::string(argv[2]); std::stringstream hexToInt; hexToInt << std::hex << procAddressHexa; unsigned int procAddress = 0; hexToInt >> procAddress; unsigned int nbbytetoRead = atoi(argv[3]); std::string targetFileName = std::string(argv[4]); boost::shared_ptr<void> procHandle(OpenProcess(PROCESS_VM_READ, false, DWORD(procPID)), &::delete_HANDLE); if(procHandle) { std::vector<char> memCopyofProcMem(nbbytetoRead); SIZE_T NumberOfBytesRead = 0; if(ReadProcessMemory(procHandle.get(), LPCVOID(procAddress), LPVOID(&memCopyofProcMem[0]), SIZE_T(nbbytetoRead), &NumberOfBytesRead) && NumberOfBytesRead == nbbytetoRead) { std::ofstream targetFile(targetFileName, std::ios::binary|std::ios::out); targetFile.write(&memCopyofProcMem[0], nbbytetoRead); targetFile.close(); } else { std::cout << "ReadProcessMemory return false, or NumberOfBytesRead != of the requested number of byte." << std::endl; return -1; } } } catch (const std::exception& e) { std::cout << "std::exception: " << e.what() << std::endl; return -1; } catch (...) { std::cout << "unknown exception: " << std::endl; return -1; } return 0; }