Code Kata: Project Euler #3 + CMake distributions

md — Sun, 13 Apr 2008 17:26:31 +0000

This weekend, I tackled the Project Euler problem #3:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Pretty straightforward: Just test and recurse. The core of the implementation is here: std::set Problem3::_findFactor(ull number, ull startFactor ) { std::set retval; for( ull factor = startFactor; factor < = number; factor += 1) { if (number % factor == 0) { retval.insert(factor); std::set recursive = _findFactor(number / factor, factor); retval.insert(recursive.begin(), recursive.end()); break; } } return retval; } Please note that "ull" is a typedef for unsigned long long. For increasing integers, I test whether it is a factor of the given number. If yes, add it to the set of result values and descent one level into the recursion. In addition, I extended my CMake infrastructure: You can now roll distributions based on CPack. In my oppinion you should start having a distribution target as early as possible within your development cycle. This way, you're always ready to ship/deploy your software, i.e. for beta testers. Ship early, ship often... And of course automatically. When I type "make release", CMake builds the software in release mode ("-O3") and rolls several distributions. This is the output: Run CPack packaging tool... CPack: Create package using PackageMaker CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package Building in backwards compatible mode Preverifying PROBLEM3 Preverifying PROBLEM3 Checking bundle identifiers Checking package configuration Checking contents Loading contents Checking for ZeroLink Building PROBLEM3 Building PROBLEM3 Creating shell Copying scripts Writing description Writing bundle versions Copying resources Creating Requirements Creating permission hierarchy Creating Bill-of-Materials file Archiving files Creating Info.plist CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.dmg generated. CPack: Create package using STGZ CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.sh generated. CPack: Create package using TGZ CPack: Install projects CPack: - Run preinstall target for: PROBLEM3 CPack: - Install project: PROBLEM3 CPack: Compress package CPack: Finalize package CPack: Package /Users/gonium/Projects/project-euler/trunk/problem3/build/PROBLEM3-0.2.0-Darwin.tar.gz generated. As you can see, a DMG image, a self-extracting shell installer and a tar.gz are built. The DMG contains all metadata for a nice MacOS installer - for Windows, a NSIS-based installer would have been created. CPack reuses the dependency information from my CMakeLists.txt files, so I don't have to maintain another place and avoid duplication. You simply add CPack to your toplevel CMakeLists.txt: # add some files to the installation target INSTALL(FILES README.txt COPYRIGHT.txt DESTINATION share/PROBLEM3/doc) # CPACK packaging INCLUDE(InstallRequiredSystemLibraries) SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY "Project Euler Problem 3") SET(CPACK_PACKAGE_VENDOR "Mathias Dalheimer") SET(CPACK_PACKAGE_DESCRIPTION_FILE "${CMAKE_CURRENT_SOURCE_DIR}/README.txt") SET(CPACK_RESOURCE_FILE_LICENSE"${CMAKE_CURRENT_SOURCE_DIR}/COPYRIGHT.txt") SET(CPACK_PACKAGE_VERSION_MAJOR ${V_MAJOR}) SET(CPACK_PACKAGE_VERSION_MINOR ${V_MINOR}) SET(CPACK_PACKAGE_VERSION_PATCH ${V_PATCH}) SET(CPACK_PACKAGE_INSTALL_DIRECTORY "CMake ${CMake_VERSION_MAJOR}.${CMake_VERSION_MINOR}") SET(CPACK_PACKAGE_EXECUTABLES "pe-problem3" "Solves Project Euler problem 3") INCLUDE(CPack) I choose to add the resulting binary in a subsequent CMakeLists.txt where the binary is compiled: INSTALL(PROGRAMS ${PROBLEM3_BINARY_DIR}/src/pe-problem3 DESTINATION bin) Pretty easy and maintainable :-) You can get the source package from the download page. Picture taken by 8#X and CCed on flickr.

Code Kata: Project Euler #2 with CMake

md — Sun, 06 Apr 2008 10:41:35 +0000

Recently, I started to use the autotools for building a project. But I am really unhappy with it – although a lot of special cases can be handled by the toolchain, it is extremely complex to use and prone to user errors. Auto-Hell, I guess… So, this code kata is dedicated to the alternative CMake package. I have written a simple C++ program to solve problem #2 of Project Euler. The autotools toolchain attempts to solve two problems:

Configuration: On the compile system, where do libraries etc live?
Build: How is the software built?

The configuration step is the famous “./configure” everyone comes across when installing software on unix systems. The autotools employ a mix of SH, Commandline-Magic, M4 and fairy dust to handle this. It generates Makefiles so that one can use make to build the software. Additional make targets such as make dist or make install help during deployment of the software. The problem lies in the complexity of the toolchain: in the mixture of tools that build upon other tools, M4 macros and shell scripts, it is extremely difficult to find errors. If your buildsystem is as complex as the software you’re developing, something is wrong. In addition, the autotools are not really portable to other systems such as windows, at least not straightforward. For these reasons the KDE project moved away from the autotools. They evaluated many different buildsystems and choose CMake. I played a little bit with it and I am quite happy. Of course, one needs to asses such a system in a bigger scenario in order to judge it, but at a first glance it really does the trick. There are plenty of articles around – to get you started I suggest Tanner Lovelace’s introduction. In addition, the following resources are helpful:

Mal ausspannen (German, Linux-Magazin 02/2007)
Cross-Platform Software Development Using CMake (Linux Magazine)
The KDE subversion provides also a nice collection of CMake scripts which might give you some ideas.
The CMake manpage, highly readable reference.

But now, on to building the software. My project directory has the following structure:


.
|-- CMakeLists.txt
|-- Makefile
|-- Modules/
|   `-- FindLog4Cxx.cmake
|-- common/
|   |-- CMakeLists.txt
|   |-- common.h
|   `-- config.h.in
|-- problem2/
|   |-- CMakeLists.txt
|   |-- problem2.cpp
|   `-- problem2.hpp
|-- src/
|   |-- CMakeLists.txt
|   `-- main.cpp
`-- timer/
    |-- CMakeLists.txt
    |-- clock.cpp
    `-- clock.hpp

In order to keep things interesting I moved the code for solving the Project Euler task to the problem2 library. There’s a common library that defines project-wide settings. In timer, there’s a little routine for measuring execution times. The main routine lives in the src directory. The CMakeList.txt files define the tasks to be done by CMake – this can be seen as the equivalent to the Makefile.am files. But you can define much more stuff in there. Here’s the top-level CMakeList.txt file: # Define project name and version numbers. project (PROBLEM2) set(V_MAJOR 0) set(V_MINOR 1) set(V_PATCH 1) # add a path where some libraries might be stored set(CMAKE_INCLUDE_PATH ${CMAKE_INCLUDE_PATH} /opt/local/include) set(CMAKE_LIBRARY_PATH ${CMAKE_LIBRARY_PATH} /opt/local/lib) # look for the external log4cxx library set(LOG4CXX_FIND_REQUIRED true) include(modules/FindLog4Cxx.cmake) OPTION(ENABLE_LOGGING “Build the project with logging enabled” ON) if(ENABLE_LOGGING) message(STATUS “Building with logging enabled.”) endif(ENABLE_LOGGING) # Make sure all subdirectories include correctly include_directories(${CMAKE_CURRENT_BINARY_DIR}) # process the subdirectories in the right order. add_subdirectory (common) add_subdirectory (problem2) add_subdirectory (timer) add_subdirectory (src) I wanted to create a template which can be used as a staring point for later projects. I tend to use the Apache Log4CXX library for producing log messages. In order to discover the include and library directories, I created a CMake module – the equivalent of an Autotools M4 macro. CMake comes with lots of example modules for detecting libraries. But it is also easy to write your own modules. In contrast to the Autotools, all modules are specified in CMake’s own language. Typically, you want to be able to deactivate all logging during the build process, e.g. prior to shipping the release version. You can define Options which can be set with various GUI tools. On Unix platforms, a curses-based GUI allows you to select your options. In this example, the ENABLE_LOGGING variable gets processed by the CMakeList.txt in the common directory: set(lib_src config.h common.h) # create autotools-like config.h file from template. config.h will be # generated in the build directory – add a global include so that we can # find the config.h. In addition, copy the header-only common.h file to # the build tree. configure_file(config.h.in ${CMAKE_CURRENT_BINARY_DIR}/config.h) configure_file(common.h ${CMAKE_CURRENT_BINARY_DIR}/common.h COPYONLY) This generates a config.h file and copies it to the right location in the build directory. The config.h.in file defines some variables that will be replaced based on the values determined by CMake during the build step. Altogether, I like CMake. It is as powerful as the Autotools but without the quirks of the latter. You can download the example from the download page. There are other tools in the CMake package, namely CTest for testing software – but I’ll save this for another sunday ;-) Finally, the Project Euler task is to solve the following problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The code to solve this problem is pretty easy: unsigned long long sum, tmp = 1; current = 2; previous = 1; while (current < _max) { if (current % 2 == 0) sum += current; tmp=current; current = current + previous; previous = tmp; } The heaven or hell picture was CC'ed by karmablue.

gonium.net » cmake

Code Kata: Project Euler #3 + CMake distributions

Code Kata: Project Euler #2 with CMake