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:
Looking at that formula, the complexity is clearly O().
Now let express P' iteratively:
or ....
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)
vendredi 19 avril 2013
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
>dumpbin.exe path_to_executable.exe /HEADERS
And on linux, just use file
>file path_to_executable
samedi 6 avril 2013
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).
I put the map focus somewhere .... using latitude and longitude coordinate (48.13199070073399, -1.6228169202804565).
jeudi 31 janvier 2013
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.....
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/
- 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 offset in the process memory
, &vec[0], and the number of bytes, vec size * 8(size of double)
processmemdumper.exe PID offset nbbytes out.bin
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; } |
mercredi 19 décembre 2012
The annoying push_back.....
Maybe you know, but maybe not,
but one of the really nice feature coming in the C++11 standard is the "initializer list".
In fact with C++11, you can now write:
std:vector vec = {"blog", "msg"};
see http://en.wikipedia.org/wiki/C%2B%2B11#Core_language_usability_enhancements
But if you are still using the old C++, you can at least try to avoid the push_back usage...
Instead of writing
std:vector vec;
vec.push_back("blog");
vec.push_back("msg");
let's use Boost/Assign to offer a += operator supporting variable number of arguments
#include "boost/assign.hpp"
std:vector vec;
vec += "blog", "msg";
but one of the really nice feature coming in the C++11 standard is the "initializer list".
In fact with C++11, you can now write:
std:vector
see http://en.wikipedia.org/wiki/C%2B%2B11#Core_language_usability_enhancements
But if you are still using the old C++, you can at least try to avoid the push_back usage...
Instead of writing
std:vector
vec.push_back("blog");
vec.push_back("msg");
let's use Boost/Assign to offer a += operator supporting variable number of arguments
#include "boost/assign.hpp"
std:vector
vec += "blog", "msg";
jeudi 8 novembre 2012
When compiler act as Static Analyzer
Today i goes through a strange compiler behavior while compiling a source code with GCC/G++. You may or not be aware of the importance of Security and Sanity checking on the code you write, but it's a fact that in the last decade the "Static Code Analysis" come from space, fly, nuclear domain and is now use in game and all professional development.
For a good introduction to "Static Analysis" take a look at http://www.altdevblogaday.com/2011/12/24/static-code-analysis/ where John Carmack present a review of several existing tools.
But here I try to explain why sometimes a good compiler like GCC "can" act as a static code checker. To demonstrate and explain it, lets talk about the code below.
I mainly code using Visual Studio IDE (08,10 at work and 12 at home for now...) but hopefully i also use GCC and we will see why just below. As you can see, i coded 2 buffer overrun by calling "func(myTab, 8)" and "myTab[8]".
stl_usage.cpp(22): warning : C6201: Index '8' is out of valid index range '0' to '3' for possibly stack allocated buffer 'myTab'.
stl_usage.cpp(22): warning : C6385: Reading invalid data from 'myTab': the readable size is '16' bytes, but '36' bytes may be read.
g++ -Wall -Wextra -Werror -O3 ./gcc-static-analys.cpp
I got the following error:
./gcc-static-analys.cpp: In function âint main(int, char**)â:
./gcc-static-analys.cpp:17: error: âmyTab[8]â is used uninitialized in this function [-Werror=uninitialized]
./gcc-static-analys.cpp:20: error: âmyTab[8]â is used uninitialized in this function [-Werror=uninitialized]
cc1plus: all warnings being treated as errors
But why GCC can detect these 2 buffer overrun at compile-time. For the direct and invalid access to myTab[8] it should be easy but for "func(8)", it's a bit tricky. In fact if you had a look at the 2 comment line 4 and 5, you may have guess that it's mainly come from the "inlining" of "func".
Depending of the optimization level you used GCC can decide to inline some function by itself and in fact case he can detect some error and act as a Stactic Analyzer preventing use to let something wrong (a security issue) in our code.
For a good introduction to "Static Analysis" take a look at http://www.altdevblogaday.com/2011/12/24/static-code-analysis/ where John Carmack present a review of several existing tools.
But here I try to explain why sometimes a good compiler like GCC "can" act as a static code checker. To demonstrate and explain it, lets talk about the code below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <iostream> #include <string> //inline int func(int tab[], bool toSwitch) //force inline. //__attribute__ ((noinline)) int func(int tab[], bool toSwitch) //prevent inline. int func(int tab[], int idx) //let compiler inline based on its own logic and optimization parameters. { return tab[idx]; } int main(int argc, char* argv[]) { std::cout << argc << " " << std::string(argv[0]) << std::endl; int myTab[4] = {1,2,3,4}; //int myTab[10] = {1,2,3,4,5,6,7,8,9,10}; std::cout << func(myTab, 0) << std::endl; std::cout << func(myTab, 8) << std::endl; //At least the line is detected by VS'12 Static Analyzer.... std::cout << myTab[8] << std::endl; return 0; } |
I mainly code using Visual Studio IDE (08,10 at work and 12 at home for now...) but hopefully i also use GCC and we will see why just below. As you can see, i coded 2 buffer overrun by calling "func(myTab, 8)" and "myTab[8]".
- Visual Studio 2012
//At least the line is detected by VS'12 Static Analyzer.... std::cout << myTab[8] << std::endl;
stl_usage.cpp(22): warning : C6201: Index '8' is out of valid index range '0' to '3' for possibly stack allocated buffer 'myTab'.
stl_usage.cpp(22): warning : C6385: Reading invalid data from 'myTab': the readable size is '16' bytes, but '36' bytes may be read.
- GCC
g++ -Wall -Wextra -Werror -O3 ./gcc-static-analys.cpp
I got the following error:
./gcc-static-analys.cpp: In function âint main(int, char**)â:
./gcc-static-analys.cpp:17: error: âmyTab[8]â is used uninitialized in this function [-Werror=uninitialized]
./gcc-static-analys.cpp:20: error: âmyTab[8]â is used uninitialized in this function [-Werror=uninitialized]
cc1plus: all warnings being treated as errors
But why GCC can detect these 2 buffer overrun at compile-time. For the direct and invalid access to myTab[8] it should be easy but for "func(8)", it's a bit tricky. In fact if you had a look at the 2 comment line 4 and 5, you may have guess that it's mainly come from the "inlining" of "func".
Depending of the optimization level you used GCC can decide to inline some function by itself and in fact case he can detect some error and act as a Stactic Analyzer preventing use to let something wrong (a security issue) in our code.
mardi 23 octobre 2012
why you should prefer std::algorithm...
Today i worked on a huge legacy code base when i meet (1x more) the following kind of loop:
I was wondering why some developer always try to reinvent the wheel ?
C++ comes with a tons of useful algorithm to do that kind of stuff, and with an explicit name. In example that code can be rewrite with:
it's shorter and more explicit...
Note for C++11 users:
std::vector<int> vec; ... int max_value = 0; for ( int i=0 ; i<(int)vec.size() ; i++ ) { if (vec[i] > max_value) { max_value = vec[i]; } }
I was wondering why some developer always try to reinvent the wheel ?
C++ comes with a tons of useful algorithm to do that kind of stuff, and with an explicit name. In example that code can be rewrite with:
#include <algorithm> ... std::vector<int> vec; ... int max_value = *std::max_element<std::vector<int>::iterator >(vec.begin(), vec.end());
it's shorter and more explicit...
Note for C++11 users:
auto max_value = *std::max_element<std::vector<int>::iterator >(begin(vec), end(vec));
Inscription à :
Articles
(
Atom
)