Jayson Explains CMake

As men­tioned in the pre­vi­ous entry, my good buddy Jayson is going to con­tribute addi­tional programming/technical/geeky arti­cles on the blog. Below is his first such arti­cle. Enjoy!

Today’s arti­cle is going to be about CMake. I started using this at work recently. It took a bit of time for me to get it work­ing with my setup at work; fig­ur­ing out how it oper­ates. So I’m here to pro­vide hints so that maybe if you’re start­ing out using CMake, you can have a bet­ter clue as to how to use it.

This guide is going to be generic and assume a gcc devel­op­ment envi­ron­ment; be that MinGW inside Win­dows or gcc inside Linux.

First and fore­most, as their doc­u­men­ta­tion states, you need a CMakeLists.txt file in each direc­tory you’re going to do some com­pil­ing in.

For just a sim­ple basic sin­gle file appli­ca­tion, you would have this as your direc­tory and file structure:

$ ls
CMakeLists.txt  main.c

Now, the CMakeLists.txt file is pretty sim­ple for this:

$ cat CMakeLists.txt
cmake_minimum_required(VERSION 2.6)
project(mini)

add_executable(mini main.c)

And our main.c file is rather drafty as well:

#include <stdio.h>

int main() {
printf(“Hello, world!\n);
return (0);
}

Now, on a Linux sys­tem, this is what I typed at the com­mand line to gen­er­ate Unix Make files: cmake –G “Unix Makefiles”

The above com­mand will then parse through the CMakeLists.txt file and gen­er­ate every­thing needed to build the project. After it com­pletes, all that is needed is to type make at the com­mand line. Actu­ally, from here on out, if you were to add other source files to the project, all you’d need to do is type make. The only time you ever need to run the cmake com­mand directly is the first time you run it. Every other time, you can sim­ply type make.

Now, the above small lit­tle project isn’t exactly using any­thing use­ful. Most of the time, if you’re doing a project, you’re using other libraries. CMake includes search func­tions for a lot of libraries. The syn­tax for search­ing for each library is fairly sim­i­lar, so I’m only going to give some exam­ples for a couple[1].

First, we’ll high­light using the wxWid­gets library. We’ll start with the struc­ture in the CMakeLists.txt file as to how to search for wx.

$ cat CMakeLists.txt
cmake_minimum_required(VERSION 2.6)
project(first_wx)

find_package(wxWid­gets COMPONENTS base core aui REQUIRED)
include(${wxWidgets_USE_FILE})

set(FIRST_WX_SRC app.cpp)

add_executable(first_wx ${FIRST_WX_SRC})
target_link_libraries(first_wx ${wxWidgets_LIBRARIES})

Now, this is still pretty sim­ple, but I’ve added a few things that I’d like to elab­o­rate upon. First, find_package(). Shipped with CMake are, as men­tioned above, some func­tions to search for pop­u­lar libraries. To use these, just call find_package() with the library name, some COMPONENTS you’d like to use from the library, and whether those com­po­nents are REQUIRED. What this does is searches the sys­tem for the pack­age, and the sub-components. If it finds them, the com­po­nents listed are auto­mat­i­cally added to the link stage. How­ever, as the code states below the find_package() call, you still need to explic­ity add the include and link direc­to­ries. Each library may have dif­fer­ent syn­tax for these vari­ables, so don’t blindly assume they are all the same.[1][2]

Next I add a vari­able to store the source files in. I just use this as a con­ve­nience, so that just in case I use it in mul­ti­ple places, I only have to type the variable.

Our direc­tory struc­ture is flat, for now:

$ ls
CMakeLists.txt  app.cpp  app.h

Our app.h and app.cpp files are simple:

#ifn­def __app_file_h_included__
#define __app_file_h_included__

#include “wx/app.h“

class app : pub­lic wxApp
{
pub­lic:
bool OnInit();
int OnExit();
};

#endif
#include “app.h“

#include <wx/frame.h>
#include <wx/intl.h>

IMPLEMENT_APP(app)

bool app::OnInit()
{
wxFrame* frame = new wxFrame (0L, wxID_ANY, _(“Hello, World!”));
if (!frame) {
return (false);
}
frame-&gt;Show ();
return (true);
}

int app::OnExit()
{
return (0);
}

Now that we have that work­ing, we’ll move on to add boost to our pro­gram. We’ll still not have it be very elab­o­rate. We’ll take one of the asio demo’s, so that we can use actual libraries; in addi­tion to some header only stuff.[3]

The lay­out stays the same, but here’s the mod­i­fied CMakeLists.txt file:

$ cat CMakeLists.txt
cmake_minimum_required(VERSION 2.6)
project(wx_boost)

find_package(wxWid­gets COMPONENTS base core aui REQUIRED)
include(${wxWidgets_USE_FILE})

set(Boost_USE_MULTITHREADED ON)
find_package(Boost 1.39.0 COMPONENTS date_time thread sys­tem)
include(${Boost_INCLUDE_DIRS})

set(FIRST_WX_SRC app.cpp)

add_executable(wx_boost ${FIRST_WX_SRC})
target_link_libraries(wx_boost ${wxWidgets_LIBRARIES} ${Boost_LIBRARIES})

The app.h file was not mod­i­fied, but here’s the changed app.cpp:

#include “app.h“

#include <wx/frame.h>
#include <wx/intl.h>
#include <wx/msgdlg.h>

#include <boost/asio.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>

IMPLEMENT_APP(app)

sta­tic wxFrame* frame = 0;

void popup(const boost::sys­tem::error_cc lang=“c”&amp; /*e*/)
{
wxMes­sage­Box (_(“Pop up!”), _(“Box”), wxOK, frame);
}

bool app::OnInit()
{
frame = new wxFrame (0L, wxID_ANY, _(“Hello, World!”));
if (!frame) {
return (false);
}
boost::asio::io_service io;

frame-&gt;Show ();
boost::asio::deadline_timer t (io, boost::posix_time::sec­onds(5));
t.async_wait (popup);

io.run ();
return (true);
}

int app::OnExit()
{
return (0);
}

So, now that we’ve seen how to imple­ment a cou­ple libraries into an exe­cutable, I’ll go through a handy set­ting for the install() function.

install() is as it states[2], it will install things to the des­ig­nated loca­tions. When using cmake to build libraries, I found the fol­low­ing to be very handy:

install(DIRECTORY   DESTINATION ${}
FILES MATCHING PATTERN “*.h“
PATTERN “.svn” EXCLUDE
)

Now, the above will copy all the header files in the direc­tory list­ing, exclud­ing the .svn direc­tory. With­out the exclude, the .svn direc­tory would get copied to the instal­la­tion path. That will han­dle include pathing for your own cus­tom library, but the instal­la­tion of the library itsel would go like this:

add_library(  STATIC )
install(TARGETS     ARCHIVE DESTINATION lib)

This would cre­ate a sta­tic library [.a|.lib] for your project and then copy it to the lib direc­tory on the DESTINATION path. This path can be set up by set­ting the following:

set(MY_LIB_INSTALL_PATH ${CMAKE_INSTALL_PREFIX}/lib)

[1] The wiki page for Find­ing Libraries on your system

[2] The offi­cial doc­u­ment page for CMake detail­ing _every_ avail­able call

[3] The full source list­ing for the Boost only ASIO code

Auditing NTFS Permissions

Recently I’ve wanted to review the account per­mis­sions on my home server that I use for backup. It has some­times served as a sand­box of sorts; not best prac­tice, but real­ity for hardware/monetary lim­its. Rather than spend the time right-clicking and check­ing the per­mis­sions on each folder I thought it’d be nice to write a WMI script to gen­er­ate a report.

I knew this had to have been done before, and after some quick googlefu I can across this script by Amine Abdelka­der that basi­cally did every­thing I wanted.

I didn’t like the HTML out­put though, I want CSV so that it can be eas­ily sorted, fil­tered, manip­u­lated in Excel. I also wanted to con­trol the depth of the search into sub­fold­ers and the total num­ber of fold­ers it would report on.

The script, mod­i­fied for these changes, is listed below:

‘========================================================================================
’ Orig­i­nal Author:  Abdelka­der, Amine
’ Orig­i­nal Date: 10/03/2006
’ Orig­i­nal Ouput: HTML File

’ Mod­i­fied by: Randy Armknecht
’ Mod­i­fied Date: 2009-11-05
’ Mod­i­fied Out­put:  CSV File, with abil­ity to con­trol depth of sub­folder search (depth)
’           and abil­ity to con­trol total num­ber of fold­ers reported on (max_seen)
’          
’========================================================================================
Const For­Read­ing = 1, For­Writ­ing = 2, ForAp­pend­ing = 8

Const Ful­lAc­cess­Mask = 2032127, Mod­i­fy­Ac­cess­Mask = 1245631, WriteAc­cess­Mask = 118009
Const ROAc­cess­Mask = 1179817



str­Com­puter = “.“
sPar­ent­Folder = Input­Box(“Please Enter folder to gather infor­ma­tion on”, “Par­ent Folder”)
SParentFoldern=replace(sParentFolder,”\”,””)
SParentFoldern=replace(sParentFoldern,”:”,””)

max_seen = 1000
depth = 1
count = 0


Set fso = Cre­ateOb­ject(“Scripting.FileSystemObject”)
’File name Same As Folder Name with­out spe­cial Car­ac­teres
fullfilename=SParentFoldern&”.csv“
’WScript.echo full­file­name

Set fsOut = fso.OpenTextFile(fullfilename, ForAp­pend­ing, True)

On Error Resume Next

    fsOut.Writeline “Folder, User Name, Per­mis­sion“

fsOut.Close



Show­Sub­Fold­ers FSO.GetFolder(sParentFolder),fullfilename

Out­put­Folder­Info sPar­ent­Folder, full­file­name

Set fsOut = fso.OpenTextFile(fullfilename, ForAp­pend­ing, True)
fsOut.Writeline strTable­Foot
fsOut.Close
Msg­Box “Done “
WScript.Quit

Pub­lic Sub OutputFolderInfo(FolderName , sOut­file)
    Const Ful­lAc­cess­Mask = 2032127, Mod­i­fy­Ac­cess­Mask = 1245631, WriteAc­cess­Mask = 1180095
    Const ROAc­cess­Mask = 1179817
    Const For­Read­ing = 1, For­Writ­ing = 2, ForAp­pend­ing = 8
   
    str­Com­puter = “.“

    ‘Build the path to the folder because it requites 2 back­slashes
    fold­er­path = Replace(FolderName, “\”, “\\”)

    object­path = “winmgmts:Win32_LogicalFileSecuritySetting.path=’” & fold­er­path & “‘“

    ‘Get the secu­rity set for the object
    Set wmi­FileSec­Set­ting = GetO­b­ject(object­path)

    ‘ver­ify that the get was suc­cess­ful
    Ret­Val = wmiFileSecSetting.GetSecurityDescriptor(wmiSecurityDescriptor)
    If Err Then
        ‘Msg­Box (“Get­Se­cu­ri­ty­De­scrip­tor failed” & vbCrLf & Err.Number & vbCrLf & Err.Description)
        Err.Clear
    End If

    Set objWMIS­er­vice = GetO­b­ject(“win­mgmts:” & “{impersonationLevel=impersonate}!\\” & str­Com­puter & “\root\cimv2”)
    Set col­Fold­ers = objWMIService.ExecQuery(“SELECT * FROM Win32_Directory WHERE Name =’” & fold­er­path & “‘”)

    For Each obj­Folder In col­Fold­ers
        ’ Retrieve the DACL array of Win32_ACE objects.
        DACL = wmiSecurityDescriptor.DACL

        Set fso = Cre­ateOb­ject(“Scripting.FileSystemObject”)
        Set fsOut = fso.OpenTextFile(sOutfile, ForAp­pend­ing, True)
   

        For Each wmi­Ace In DACL
            ’ Get Win32_Trustee object from ACE
            Set Trustee = wmiAce.Trustee
           
            fsOut.Write objFolder.Name&”,”&Trustee.Domain&”\”&Trustee.Name&”,“

            FoundAc­cess­Mask = False
            Cus­tom­Ac­cess­Mask = Flase
           
            While Not FoundAc­cess­Mask And Not Cus­tom­Ac­cess­Mask
                If wmiAce.AccessMask = Ful­lAc­cess­Mask Then
                    AccessType = “Full Con­trol“
                    FoundAc­cess­Mask = True
                End If
                If wmiAce.AccessMask = Mod­i­fy­Ac­cess­Mask Then
                    AccessType = “Mod­ify“
                    FoundAc­cess­Mask = True
                End If
                If wmiAce.AccessMask = WriteAc­cess­Mask Then
                    AccessType = “Read/Write Con­trol“
                    FoundAc­cess­Mask = True
                End If
                If wmiAce.AccessMask = ROAc­cess­Mask Then
                    AccessType = “Read Only“
                    FoundAc­cess­Mask = True
                Else
                    Cus­tom­Ac­cess­Mask = True
                End If
            Wend
     
            If FoundAc­cess­Mask Then
                fsOut.Write AccessType&vbCrLf
            Else
                fsOut.Write “Cus­tom”&vbCrLf
            End If
        Next

        Set fsOut = Noth­ing
        Set fso = Noth­ing
    Next

    Set fsOut = Noth­ing
    Set fso = Noth­ing
end Sub

Sub Show­Sub­Fold­ers (Folder,fname)
    On Error Resume Next
        If count < depth then
            count = count + 1
            total_seen = 0
            For Each Sub­folder in Folder.SubFolders
            if total_seen < max_seen then
                total_seen = total_seen + 1
                Call OutputFolderInfo(Subfolder.Path,fname)
                ‘Wscript.Echo Subfolder.Path
                call Show­Sub­Fold­ers (Subfolder,fname)
            end if
            Next
        end if
End Sub

Problem #53

This prob­lem over at Project Euler turned out to be a lot sim­pler than expected.  Forty-Three other prob­lems have been solved more times than this one; yet, it was dead sim­ple. Really, there is noth­ing inter­est­ing in its solu­tion, unlike Prob­lem #97 that I posted about yes­ter­day.

It’s straight com­bi­na­torics and fac­to­ri­als. So read the prob­lem page and be amazed at what a gimme this one is :)

Result: [snip]
Time: 0.321524143219

#!/usr/bin/python
import time
def fac­to­r­ial(n):
    if n > 1:
        return n * fac­to­r­ial(n–1)
    else:
        return 1

def com­bi­na­tions(r,n):
    return fac­to­r­ial(n)/(fac­to­r­ial(r)*fac­to­r­ial(n-r))

total = 0
start = time.time()
for n in range (1,101):
    for r in range(1, n+1):
        if com­bi­na­tions(r,n) > 1000000:
            total += 1
stop = time.time()
print “Result:”, total
print “Time:”, str(stop-start)

Problem #97

Now this prob­lem was inter­est­ing! It asked for us to find the last 10 dig­its of a very large Mersenne Prime dis­cov­ered in 2004 of the form 28433×27830457+1.

I solved this prob­lem three dif­fer­ent ways. The first was by my own logic, the other two, due to some research. My thought was that cal­cu­lat­ing 2n can be done in a loop that mul­ti­plies the pre­vi­ous value by 2 on each iter­a­tion. Rais­ing it to the 7,830,457th power though would not only take for­ever, but could be hard to store in mem­ory. So I fig­ured that we really only care about the last 10 dig­its. This meant I could mul­ti­ple the pre­vi­ous value by 2 on each iter­a­tion, but store for the next iter­a­tion a con­sist­ing of only the last ten dig­its. Python’s list syn­tax of [-10:] came in mighty handy for this.

My Method
==============
Result: 8739992577
Time: 9.89434504509

def my_method():
    print ““
    print “My Method“
    print “==============“
    last=“2”
    start = time.time()
    for p in range(2,7830458):
        last = str(int(last)*2)
        last = last[-10:]
    result =  str(28433*int(last)+1)
    stop = time.time()
    print “Result: “+result[-10:]
    print “Time: “+str(stop-start)

It was fairly quick, sub 10 sec­onds, but not as fast as it could be.

The next method I tried was to uti­lize the bit­wise shift oper­a­tor. I saw this for a C++ solu­tion in the forums after solv­ing it and won­dered if Python had a bit­wise shift. Turns out it does. Hav­ing a base of 2 for the pow­ers is what makes this pos­si­ble. Rather than mul­ti­ply­ing a num­ber by 2, we can shift it’s binary value to the left by one posi­tion for the same affect. CPU’s are typ­i­cally faster at bit shift­ing than they are at mul­ti­ply­ing. This solu­tion took less than 2 sec­onds! That’s quite an improvement.

Bit­wise Method
==============
Result: 8739992577
Time: 1.6119530201

def bit­wise():
    print ““
    print “Bit­wise Method“
    print “==============“
    start = time.time()
    ans = 1
    for n in range(1,7830458):
        ans = ans « 1
        ans = ans % 10000000000
    ans = ans * 28433
    ans = ans % 10000000000
    ans = ans + 1
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

I’m not sure how, but I ended up read­ing this arti­cle on OSIX about quickly cal­cu­lat­ing inte­ger pow­ers. It pro­posed a func­tion in C# that used recur­sion to cal­cu­late a power in O(logn) time rather than the O(n) time that the first two meth­ods imple­mented. I trans­lated the code to Python, and sure enough, it solves this prob­lem in less than half of a second!

Power Method
==============
Result: 8739992577
Time: 0.471854925156

def get_power(a,n): # a^n
    if n==0:
        return 1
    if a==0:
        return 0
    if n%2==0:
        return get_power(a*a, n/2)
    else:
        return a*get_power(a*a, n/2)
    return 0

def power():
    print ““
    print “Power Method“
    print “==============“
    start = time.time()
    value = get_power(2,7830457)
    ans = 28433*value+1
    ans = ans % 10000000000
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

Problem #42

Another prob­lem solved! This prob­lem intro­duced me to some util­ity func­tions in python that I did not pre­vi­ously know about. It involved the gen­er­a­tion of two lists, check­ing if a list con­tains a spe­cific value, read­ing a file, con­vert­ing a char­ac­ter into it’s ASCII num­ber, and keep­ing track of time inter­nal to the program.

Check­ing a List for Items
I searched and came across this expla­na­tion of the in oper­a­tor. Some­how I either missed it or haven’t had enough caf­feine today. I use in all the time with loop­ing con­structs like for line in file but never real­ized that it pro­duced a Boolean output.

ASCII Val­ues of Char­ac­ters
This prob­lem required the abil­ity to assign a numer­i­cal value to each let­ter. To do this I used a stan­dard func­tion named ord.

ord(“A”) # Returns 65 — the base10 ASCII Value

Con­vert­ing it to hex is sim­ple with the func­tion named hex

hex(ord(“A”)) # Returns ‘0x41’

Below is the code:

#!/usr/bin/python

import time

# Glob­als
tri_numbers = []
total = 0

def calc_value(word):
    value = 0
    for chr in list(word):
        value += ord(chr)64
    return value

def populate_triangle_numbers(max):
    for n in range(1,max+1):
        tri_numbers.append(0.5*n*(n+1))

start = time.time()
populate_triangle_numbers(1000)

file = open(“words.txt”)
words = file.read­line().split(”,”)

for word in words:
    word = word.replace(\”, “”)
    value = calc_value(word)
    if value in tri_numbers:
        total += 1
stop = time.time()

print “Count: ” + str(total)
print “Run­time: ” + str(stop — start)

Problem #40

Solved another Project Euler prob­lem today.  From the site:

An irra­tional dec­i­mal frac­tion is cre­ated by con­cate­nat­ing the pos­i­tive integers:

0.123456789101112131415161718192021…

It can be seen that the 12^(th) digit of the frac­tional part is 1.

If d_(n) rep­re­sents the n^(th) digit of the frac­tional part, find the value of the fol­low­ing expression.

d_(1) × d_(10) × d_(100) × d_(1000) × d_(10000) × d_(100000) × d_(1000000

My orig­i­nal inten­tions were to fig­ure out an ele­gant for­mula for deriv­ing dn given some n. I thought about it for a few min­utes and fig­ured it’d be inter­est­ing to see if the straight brute force solu­tion was quick enough. So I quickly coded it up in python, and sure enough, it’s sub-second and there­fore eas­ily quick enough.

[email protected]:~/proj_euler$ time python prob40.py
210

real 0m0.906s
user 0m0.724s
sys 0m0.044s

#!/usr/bin/python

list =””

for n in range(1,1000001):
    list += str(n)

answers = [list[0], list[9], list[99], list[999], list[9999], list[99999], list[999999]]
prod = 1
for n in answers:
    prod = prod * int(n)

print prod

Problem #19

Another Project Euler prob­lem has been solved! This one almost made me feel guilty as I put the high level libraries of Python to use.

How many Sun­days fell on the first of the month dur­ing the twen­ti­eth cen­tury (1 Jan 1901 to 31 Dec 2000)?

My code was short and sweet:

#!/usr/bin/python
from date­time import date­time

d = date­time(1901,1,1)

total_sundays = 0

for yr in range(1901,2001):
    d = d.replace(year=yr)
    for m in range(1,13):
        d = d.replace(month=m)
        if(d.week­day() == 6):
            total_sundays += 1

print total_sundays

Sur­pris­ingly, the code was also very fast:

[email protected]:~$ time python prob19.py
[[answer snip]]
real 0m0.086s
user 0m0.012s
sys 0m0.000s
[email protected]:~$