Month: December 2015

Home / Month: December 2015

Fibonacci Numbers in C\C++

December 11, 2015 | Article | No Comments

In mathematics, Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence:

fibonacci_1

or:

fibonacci_2

In mathematical terms, the Fibonacci sequence Fn is defined by the recurrence relation

fibonacci_3

with seed values

fibonacci_4

Our task is to write a function that returns Fn. Following are different methods to get the nth Fibonacci number

Method 1: Simple and Naive Recursion

A simple recursion that implementing the Fibonacci definition above.

int fib(int n)
{
    if (n <= 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Time complexity: T(n) = T(n-1) + T(n-2) which is exponential.

This implementation does a lot of repeated work (see below).

                         fib(5)   
                     /             \     
               fib(4)                fib(3)   
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Extra space: O(n) if we consider function call stack size. Otherwise O(1)

Method 2: Dynamic Programming – Top Down Approach

We can void the repeated work by storing the numbers calculated so far.

/* the real function to compute the fibonacci numbers */
int _fib(int * st, int n)
{
    /* if the value has not stored yet, computed it */
    if (st[n] == -1) {
        st[n] = _fib(st, n-1) + _fib(st, n-2);
    }

    return st[n];
}

/* a wrapper function */
int fib(int n)
{
    /* array to store the fibonacci numbers */
    int st[n+1];
    int res;
    int i;

    st[0] = 0;
    st[1] = 1;
    for (i=2; i<=n; i++) {
        st[i] = -1;
    }

    _fib(st, n);
    return st[n];
}

Time complexity: O(n)

Extra space: O(n)

Method 3: Dynamic Programming – Bottom Up Approach

Another approach which also store the calculated number so far.

int fib(int n)
{
    int st[n+1];
    int i;
    
    st[0] = 0;
    st[1] = 1;
    
    for (i=2; i<= n; i++)
    {
        st[i] = st[i-1] + st[i-2];
    }
    
    return st[n];
}

Time complexity: O(n)

Extra space: O(n)

Method 4: Dynamic Programming – Space Optimized Method 3

We can optimize the space used in method 3 by storing the previous two numbers only because that are all we need to get the next Fibonacci numbers.

int fib(int n)
{
    int a = 0, b = 1, c;
    int i;
    
    for (i=2; i<=n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Time complexity: O(n)

Extra space: O(1)

Method 5: Using Matrix

This method relies on 2-dimensional system of linear difference equations for Fibonacci sequence. If we n times multiply the matrix M = {{1,1}, {1,0}} to itself (in other word calculate power(M, n)) then we get the (n+1)th Fibonacci number as the element at row and column (0,0) in the resultant matrix.

fibonacci_5

Here is how we do that:

/* Helper functions */
void multiply(int F[2][2], int M[2][2]);
void power1(int F[2][2], int n);

int fib(int n)
{
    /* We don't need to compute the matrix for these values */
    if (n<2)
        return n;
    
    int F[2][2] = {{1,1}, {1,0}};
    
    power(F, n-1);
    return F[0][0];
}

/* multiply 2 matrices F and M of size 2*2 and puts the result back to F */
void multiply(int F[2][2], int M[2][2])
{
    int w = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int x = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int y = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][1];
    
    F[0][0] = w;
    F[0][1] = x;
    F[1][0] = y;
    F[1][1] = z;
}

/* designed for fib only */
void power(int F[2][2], int n)
{
    int i;
    int M[2][2] = {{1,1}, {1,0}};
    
    for (i=2; i<=n; i++)
    {
        multiply(F, M);
    }
}

Time complexity: O(n)

Extra space: O(1)

Method 6: Using Matrix – Optimized Method 5

The method 5 can be optimized to work in O(log n) time complexity. By implementing the Divide and Conquer to power and multiplication, we can do better.

/* Helper functions */
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);

int fib4(int n)
{
    if (n<2)
        return n;
    
    int F[2][2] = {{1,1}, {1,0}};
    
    power(F, n-1);
    return F[0][0];
}

/* multiply 2 matrices F and M of size 2*2 and puts the result back to F */
void multiply(int F[2][2], int M[2][2])
{
    int w = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int x = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int y = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][1];
    
    F[0][0] = w;
    F[0][1] = x;
    F[1][0] = y;
    F[1][1] = z;
}

/* designed for fib only, optimized it using Divide and Conquer */
void power(int F[2][2], int n)
{
    if (n==0 || n==1)
        return;
    int M[2][2] = {{1,1}, {1,0}};

    power(F, n/2);
    multiply(F, F);
    if (n%2) {
        multiply(F, M);
    }
}

Time complexity: O(log n)

Extra space: O(log n) if we consider the function call stack size, otherwise O(1)

Why Linux/Unix is Less Infected by Malware?

December 11, 2015 | Article | 1 Comment

Initially I wrote this as a reply to local group discussion with similar question. And then my friend said I should publish my answer as a post. Thanks for the advice, and here is our discussion.

First, what is malware?

Malicious software, is any software used to disrupt computer operation, gather sensitive information, or gain access to certain computer. It can appear in the form of executable code, script, active content, anything. From user perspective, any malware often called as virus but it’s not exactly true. Virus is one malware categories. Malware can be divided into some categories such as computer virus, worm, trojan horse, adware, rootkits etc. If we want to discuss about malware, it can be another topic so let’s limit our discussion to computer virus and worm.

There’s a myth, if you are using Linux you are immune to malware. This is partially true. Viruses and Worms are exists even in Unix world. You can read some list from Wikipedia.

Now, it comes to the real question, why Linux/Unix is less infected by malware? Some people might answer from user demographic (who use Linux and other OS). Personally I don’t choose this answer and rather go to more technical answer.

Please note that this is my own opinion and might be biased.

Distribution

From OS distribution, most operating system used worldwide is still Windows. I pick the statistics from W3schools, Linux and Unix got less than 10% each. Per September 2014, most operating system used are Windows 7.

Linux and Unix mostly used for server, embedded system, devices, etc although quite many people use Linux as their main operating system. As we know one who creating something must have specific goal or purpose. As the OS market share still dominated by Windows then no wonder malware for Windows are keep popping up. Mostly they are targeting users.

If by chance Linux dominating the market share, it should be obvious malware will sprung and targetting linux. This is natural.

The Insides

To determine the answer, first we need to look to inside of both OSs.

Windows

Why Windows sucks?

  1. Windows API – Windows has rich APIs. Some of Windows API (WIN32 API) can be executed by any user. Yes, you got the point. When one user make mistakes, boom! The system is in danger. Also, Windows is famous with its being want to be backward compatible as possible (hence, we have Windows 10 instead of Windows 9) which implicate that you can use that API.
  2. Access Control List – Yes, Windows have ACL. But how many of us knows, or using it? People don’t know and maybe not apply it. Without control, malware can spread freely. Yes, you can use ACL but by default each resource you have is not affected by ACL.
  3. Multiuser Design – Windows have common user and superuser (known as Administrator). But on most system, one user on the system is also a super user.
  4. Device Access – Literally! On some Windows, any program can access any devices connected if you program it. Life is easier.
  5. Registry system – Windows use a huge database for it’s global configuration, known as registry. Like I said in point (1), whoever you are, you can access registry. Also you can change configuration easily, you can even set the autostart entry in registry to call your malware.
  6. Extensions – Most worms used other extension to camouflage. For example, a worm might disguise itself as Word Document program, using the same icon as the Microsoft Word. User can be fooled by this appearance. Also, the extension itself is registered to registry. Windows will look registry and call the appropriate program for this extension.

Linux

Now let’s compare it to Linux.

  1. API – Linux also has API for some operations. But, the operation is guaranteed always complies with Access Control. You can do what you are given. Linux/Unix access control is often called as Discretionary Access Control and it is enforced in the kernel itself. You cannot do something which you are not privileged to.
  2. Access Control – The Discretionary Access Control used by Linux/Unix is describing read/write/execute access to resource (file, directory, nodes, etc). This strict rule is integrated to kernel. Also, as a Linux/Unix user you are always inform to follow Least Privilege principle. Least Privilege principle means any operation you do should be done as low privilege as possible, you might request more privilege if the previous privilege is not sufficient but you should not always use super user privilege. Often some Linux distribution limit yourself from using root access.
  3. Multiuser Design – Linux is multiuser and multitasking. However, Linux make clear separation of each users. Linux have term users and groups to separate system power. On every Linux/Unix system you have a superuser account (root) and you are obligated to create your own user account. Most distribution will enforce you to create and use your own user account. This account however is different with root so you are guaranteed to not harm your system by accident, unless you are doing so.
  4. Device Access – be a network interface, printer, scanner, or any device connected all are managed by kernel by udev or similar mechanism. And the good news is any node has specific privilege.
  5. Registry System – what is registry? Linux/Unix doesn’t know that. To configure a system globally, one should modify config files and most of them stored in privileged directory. Unless you are root or given access to it, you are powerless.
  6. Extensions – Linux recognize file not by extension but by their header. Every file format has header and something we called magic words to distinguish the format and other formats. Even if the extensions are changed, Linux/Unix can know what it is and still give you correct information.

Apart from above comparison, there is one thing extra you should know! Windows executable is using PE (Portable Execution) format while executable format in Linux is ELF (Executable and Linkable Format). So you cannot run Windows program natively, in case you don’t know 🙂

Getting Started to Microcontroller

December 11, 2015 | Article | No Comments

In this article we will discuss things we need to get started to microcontroller, especially programming and engineering a microcontroller.

All the things we need can be categorized into two:

  • Hardware
  • Software

The Hardware Part

Mostly we are facing hardware. In typical we will need following hardware:

  • Computer
  • In-System Programmer (ISP)
  • Target Board
  • Microcontroller

Computer

We need computer / laptop to write, edit, compile, and debugging the code before we send the program to the microcontroller. The requirements are not too much, at least it has spare resource to do our job. Any decent PC / laptop will do.

In-System Programmer (ISP)

We have our PC at one end with binary file ready to be written and a target board at another end. How can we transfer the program? For this we need a hardware called In-System Programmer or abbreviated as ISP (not Internet Service Provider). This devices programs the Microcontroller by burning the file (typically in hex format) into flash memory of microcontroller.

There are three type of ISP, according to the connector shape: Parallel programmer, Serial programmer, USB programmer. However, most ISP are now USB-based.

Parallel programmer – data is transferred through the parallel port of the PC. Technically the parallel port is called DB25 port as it has 25 pins. Any old school computer has this, usually referred as the “printer port”.

DB25

Serial programmer – The data is transferred throught the serial port of the PC. Technically the serial port is called DB9 port as it has 9 pins.

DB9

USB programmer – the data is transferred through the USB port of the PC. Typically, it use USB 2.0 standards.

SONY DSC

Target Board

Microcontroller cannot function on its own. If Microprocessor need motherboard to function, microcontroller need a board with an appropriate circuit to make it work. Sometimes we call it development board which have slot for the MCU to fit in, slots for other accessory drivers, ICs pins outlet of GPIO pins, etc.

There are many ready made development board out there. You can buy one of them or make them by yourself. It is always recommended for beginner to buy one or two different types of development board, but don’t go and buy random board. We need to consider the type of ISP and MCU and then choose the one according to our requirement and budget.

Microcontroller

Selecting the microcontroller is the biggest dilemma. There are more than 150 IC manufactures which manufacture MCUs, and each one of them can have more than dozens of different models in their account. So which one to choose?

By the popularity, there are two most popular microcontrollers: PIC by Microchip and AVR by Atmel.

When we are choosing microcontroller, we should consider many factors. But at least, we can consider following factors to decide what MCU we need:

  • Cost – A cheap MCU is always preferred. But many chips might offers competitive price with competitive features. Also remember that sometimes price and capability always been a tradeoff.
  • Speed – Speed of execution also matters. Running faster means accomplish work faster.
  • Ease of use – How ease of use means how many effort we need to learn the chip, assemble the system, maintain it or even upgrade the system if necessary.
  • Architecture – In simple words: RISC or CISC? There are two different categories of architecture, the Reduced Instruction Set Computing (RISC) and Complex Instruction Set Computing (CISC). In RISC, the instructions are highly optimized set of instructions rather than a more specialized set of instruction. While the CISC is the counterpart. In RISC less amount of instructions will result in more output, whereas in CISC more amount of instructions will result in less output. To do a particular job, RISC require lesser number of instruction than CISC. AVR and PIC are examples of RISC, while Intel 8051 and Motorola 68000 are based on CISC.
  • Compiler – Availability of compiler means ease our access to learn and code the microcontroller. Some manufacturer such as Atmel gives free compiler for their AVR, while other might charge it for some cost. Practically, they are more specific domain or specific purpose.
  • Durability – How long the microcontroller will last? How is the maximum or minimum constraint which tolerated by the microcontroller? This should be proven.

Choose any MCU you want.

The Software Part

In softwares, we have several subcategories:

  • Compiler
  • Debugger
  • Programmer

Compiler

We want to program the microcontroller. Like microprocessor, microcontroller only know machine code in some manners. They don’t understand human language. To bridge the gap, a programming language is created and a compiler is used to translate the programming language to the code known by the microcontroller. There are many different language and compilers available for different OS.

For programming language, C is preferred over other (such as BASIC), as it is more organized and gives us the power to do substantially more. Apart from this, C is a language which widely used in low level programming. It is powerful, like a sharp sword you should know what kind of weapon you are using.

Different microcontroller use different machine code and hence can have different compiler. You can use compiler for AVR to write a program for PIC microcontroller. You can however if there is a compiler which can translate our code to different target microcontroller.

Debugger

Debugger is a tool used to test and debug other program. Typically, the debugger will execute the instruction one by one and stop to whichever instruction interest us. The target program is the program written specifically for microcontroller.

Debugging process can be done in two different location: local and remote.

Debugging in local means the target program is run on our computer. We don’t upload the program to the microcontroller to know the execution, instead we let the debugger to run it in our system.

Remote debugging means the target program is run on the microcontroller. We connect our computer to debugging line of microcontroller and control the execution flow from our debugger. We then can set some register values, change the behavior, and stop at specific instructions.

Programmer

A programmer software is a bit confusing term. It is a special software used to utilize hardware programmer or ISP so we can transfer the program from our computer to the board. Most of the compilers have an inbuilt programmer. But sometimes people prefer to use a separate one because of greater flexibility it offers.

Some popular programmers are: PonyProg, avrdude, ProgISP.

Atmel Studio 6 and Arduino

December 11, 2015 | Article | No Comments

Atmel Studio, formerly known as AVR Studio, is a good development application to create program for Atmel’s processor (Atmel’s AVR and Atmel’s ARM). The 6th version promises to be better, faster, and easier to use than before. Here, we will discuss about the way to set up the platform for the use with Arduino.

In this article, I use:

  1. Windows 8.1 64-bit
  2. Atmel Studio 6.2
  3. Arduino 1.5.8 (BETA)

Our objective:

  1. Successfully create binary file for Arduino
  2. Successfully flash the image to Arduino
  3. Know some of Arduino core library

It is recommended that we install both Atmel Studio and Arduino IDE.

Introduction to Atmel Studio 6

This Integrated Development Platform is a rich feature development platform for developing and debugging Atmel ARM Cortex-M and Atmel AVR microcontroller (MCU) based application.

Atmel Studio 6 is released in 2011 and based on Microsoft Visual Studio. The latest version at the time of writing this article is Atmel Studio 6.2 which can be downloaded from here.

Atmel studio 6 is free of charge and is integrated with the Atmel Software Framework (ASF), a large library of free source code with 1600 ARM and AVR project examples. In summary, what Atmel Studio 6 offers in addition to creating new software for MCU:

  1. Facilitates reuse of existing software and, by doing so, enables design differentiation.
  2. Supports the product development process with easy access to integrated tools and software extensions through Atmel Gallery.
  3. Reduces time to market by providing advanced features, an extensible software eco-system, and powerful debug integration.

Why Switching from Arduino IDE to Atmel Studio 6?

Arduino is a great tools. But, it does so much under the hood that it can actually be quite limiting for experienced programmers. The lacks of compiler warnings and debugging capabilities make life hard when working on advanced projects. And here Atmel Studio comes to the rescue.

Atmel Studio is a huge step up from those limitations. If you have a big project, porting the entire thing to pure C can be a daunting task. Plus, some of those Arduino libraries are just so darn convenient.

So, why not have the best of both worlds? Arduino is basically a wrapper on top of C/C++, technically it’s possible to combine any Arduino sketch or library with your own custom code (and that it is). The trick is in setting up your project properly. Once accomplished, you can keep access to the huge Arduino user-contributed code library, but enjoy all the features of advanced AVR and a real IDE.

Arduino Core Library

Arduino is an open-source physical computing platform based on simple I/O board. Stripped the IDE part, Arduino has a library which consists of seberal things like: EEPROM, Esplora, Ethernet, Firmata, etc. But down to the innermost, Arduino has a set of library known as the Arduino core. This Arduino core is the software library which is compiled to any board of Arduino and make Arduino as Arduino.

The Arduino core can be found at “<ArduinoPath>\hardware\arduino\cores\arduino\” where <ArduinoPath> is the path you install Arduino IDE. Well, if you don’t install Arduino IDE, you can clone it from git

git clone git://github.com/arduino/Arduino

and head to “hardware\arduino\cores\arduino”. You can read the content of Arduino core library in the appendix A below.

In order to build Arduino projects, we need to grab the arduino core library. Normally, the Arduino IDE compiles this for us whenever we compile a sketch. To use it in Atmel Studio we need to compile it first.

Steps:

  1. Open Arduino IDE. Open preferences (File -> Preferences) and check on “compile” next to “Show verbose output during:”.
  2. Make sure Arduino IDE is set to whichever chip you want to use with Atmel Studio.
  3. Compile any example sketch, for example “01.Basics\Blink”. In output window at the bottom of the IDE window you should see information on where the IDE put the temporary build output. It will look something like this: “C:\Users\{Your User}\AppData\Local\Temp\build1249632912679374352.tmp”
  4. Copy the “core.a” file and paste it as “libcore.a” so Atmel Studio (and GCC toolchain) can recognizes it as a standard library.

Converting the Sketch

Now the sketch part. There are two things you can do:

  1. If you are converting an existing sketch called Sketch, open the Sketch.cpp file from temporary build directory in text editor. You can then simply copy-paste the code into AVR Studio project. This file is generated by Arduino from our sketch. Arduino automatically fix the messes for us, for example we can define function anywhere in the sketch but Arduino would make appropriate function prototype for us. This is a solution if you are compiling the sketch via Arduino IDE.
  2. Copy and paste the source code from sketch file into the project’s main .cpp file. You can also copy-paste the source from Arduino .pde sketch. If you do this, you should define the function prototypes by yourself. Adding function prototypes is easy actually. Remember to incluse prototypes for setup() and loop() and then add #include “Arduino.h” to the very beginning.

Compiler and Linker Setup

In this section we will setup the compiler and linker setup for any of our project. Our objective:

  • Define Symbols for compilation, especially F_CPU and Arduino software version.
  • Point additional Include directory.
  • Set some Optimization
  • Set Linker to include our libcore
atmel-arduino
Picture 1

Steps:

  1. Open the Project Properties (Project -> <ProjectName> Properties or press Alt+F7), then click on “Toolchain”. We need to setup a bunch of compiler options here. Select “All Configuration from the Configuration drop-down menu to modify both release and debug configuration at same time.
  2. Click on “Symbols” in the left-hand “AVR/GNU C++ Compiler” dropdown menu (see number 1 on picture 1). We need to tell some symbols to our compiler. To do it, click the green plus icon and then enter the symbol. Here is what you need to enter:
    • F_CPU=16000000L
    • ARDUINO=158
  3. Click on “Directories” in the same C++ Compiler menu (see number 2 on picture 1). We need to add the include directories, the directories that contain our Arduino core code and libraries. For any Arduino project, we’ll need to tell the compiler where to find “Arduino.h” and “pins_arduino.h”. In my case I install Arduino on C:\Arduino so the library should be on “C:\Arduino\hardware\arduino\cores\arduino” and “C:\Arduino\hardware\arduino\variants\standard”.
  4. Click on “Optimization” immediately after “Directories” (see number 3 on picture 1). Choose “Optimize for size” under “Optimization Level”. Add “-fdata-sections” to “other optimization flags” and check the box for “prepare functions for garbage collection”.
  5. Next click on “Miscellaneous” (see number 4 on picture 1). Add “-fno-exceptions” to the “Other flags” field.
  6. Now we will move to the linker. Click on “Libraries” in the left hand “AVR/GNU Linker” dropdown menu (see number 5 on picture 1).
    1. In the Libraries section you should already see an entry for “m” which is the AVR math library. Add an entry called core, which is our libcore.a file that we grabbed earlier.
    2. We also need to tell where to find the libcore.a, so add that directory path under “Library search path”
  7. Click on “Optimization” (see number 6 on picture 1) and check the box for “Garbage Collect unused sections (-Wl,-gc-sections)”. This tells the linker to leave out unused portions of each library, which reduces the final code size.

Build Project

Building process is similar like other project. Hit the “F7” button to build our solution and watch the output window.

AVRDude and Flashing

The instruction in this section is similar to other “Adding ISP Programmer to Atmel Studio”.

Once you have build the project, we need to upload it. We can achieve this using the similar method as the Arduino IDE. Arduino uses the avrdude utility to flash via serial, and we will do the same.

atmel-exttools
picture 2
atmel-exttools2
picture 3

Ignore entries other than Arduino on picture 3.

Steps:

  1. Open External Tools by clicking Tools -> External Tools (see picture 2)
  2. When the window popups, click “Add” (see number 1 on picture 3)
  3. Note which COM port Arduino uses and make the title like “Arduino on COM24” for easy identification (see number 2 on picture 3)
  4. In the “Command field” (see number 3 on picture 3), put the path to avrdude.exe in Arduino installation. For example in my case: “C:\arduino\hardware\tools\avr\bin\avrdude.exe” without the quotes.
  5. In the “Arguments” (see number 4 on picture 3), paste this line.
-CC:\arduino\hardware\tools\avr\etc\avrdude.conf -patmega328p -carduino -P\\.\COM24 -b57600 -D -Uflash:w:"$(ProjectDir)Debug\$(ItemFileName).hex":i

Edit the path to Arduino installation and change the COM port, chip target, and baud rate if necessary.

 

Appendix A: Arduino Core Library files

The Arduino core library is consists of following file:

utility function

Arduino.h
binary.h
main.cpp
new.cpp
new.h
Platform.h
WCharacter.h
WInterrupts.c
WMath.cpp
WString.cpp
WString.h

CDC communication.

CDC.cpp

Human Interface Device (HID) communication.

HID.cpp

Hardware serial, for serial communication capability.

HardwareSerial.cpp
HardwareSerial.h

Internetwork connection.

Client.h
IPAddress.cpp
IPAddress.h
Server.h
udp.h

Printing.

Print.cpp
Print.h
Printable.h

Stream oriented communication

Stream.cpp
Stream.h

USB serial communication.

USBAPI.h
USBCore.cpp
USBCore.h
USBDesc.h

Tone Generator.

Tone.cpp

Wiring project

wiring_analog.c
wiring_digital.c
wiring_private.h
wiring_pulse.c
wiring_shift.c

Linux udev Rule for AVR USB Programmer

December 11, 2015 | Article | No Comments

In previous article, we have discussed about AVR development in both Linux and Windows. As you might see, we are using software avrdude to write our binary code to avr chip.

Now, when executing avrdude on Linux, it may give an error such as

avrdude: error: usbtiny_transmit: error sending control message: Operation not permitted.

This problem arise when we run avrdude without root privilege.

We can quickly fix this by run avrdude as root or doing sudo. The other choice we have is creating an udev rule for certain programmer. And that’s what we will discuss in this article.

Create udev Rule

First, what is udev?

Any device attached to Unix (and its derivation) will be represented as a node in /dev directory.For each device, it will receive a (major, minor) pair of integers. In the old school way, we can call “mknod” to create device. Starting from kernel version 2.6, Linux use udev to provide a userspace solution for dynamic /dev directory with persistent device naming. With udev we won’t have hard time to manage all device.

We use udev to give us enough privilege to access to device node.

It’s easy to use udev. We need to create a file containing udev rule and save it to /etc/udev/rules.d/

Create file “/etc/udev/rules.d/99-avrprogrammer.rules” and write following this:

# /etc/udev/rules.d/99-avrprogrammer.rules
#
# Udev rules to make AVR programmers user-accessible

# USBtinyISP Programmer rules
SUBSYSTEMS=="usb", ATTRS{idVendor}=="1781", ATTRS{idProduct}=="0c9f", GROUP="users", MODE="0666"
SUBSYSTEMS=="usb", ATTRS{idVendor}=="16c0", ATTRS{idProduct}=="0479", GROUP="users", MODE="0666"

# USBasp Programmer rules http://www.fischl.de/usbasp/
SUBSYSTEMS=="usb", ATTRS{idVendor}=="16c0", ATTRS{idProduct}=="05dc", GROUP="users", MODE="0666"

# Mdfly.com Generic (SiLabs CP2102) 3.3v/5v USB VComm adapter
SUBSYSTEMS=="usb", ATTRS{idVendor}=="10c4", ATTRS{idProduct}=="ea60", GROUP="users", MODE="0666"

#Atmel AVR Dragon (dragon_isp) rules
SUBSYSTEM=="usb", ATTRS{idVendor}=="03eb", ATTRS{idProduct}=="2107", GROUP="users", MODE="0666"

#Atmel AVR JTAGICEMKII rules
SUBSYSTEM=="usb", ATTRS{idVendor}=="03eb", ATTRS{idProduct}=="2103", GROUP="users", MODE="0666"

#Atmel Corp. AVR ISP mkII
SUBSYSTEM=="usb", ATTRS{idVendor}=="03eb", ATTRS{idProduct}=="2104", GROUP="users", MODE="0666"

The above rules describe about six hardware programmers.

Creating Disk Image

December 11, 2015 | Article | No Comments

I remember creating one or two challenges for local forensic competition in my community. Ideally the image should be created from live hard drive or SD card. However, I’m not in condition to do that. The constraint I have is to create image as small as possible so we can distribute it across any media. Therefore I create a “disk image” by myself.

In this article we will use:

  1. Slackware64 14.1
  2. dd
  3. fdisk

We will create a small disk image, 50MB in size. It can be an image of a single partition, or even we can make it as if it was an image of a disk. Let’s say we will create “partition.img” and “disk.img”

Creating a Blank Image

The disk image is exactly a single file. It is a storage containing the complete contents and structure representing a data storage or device, such as hard drive, tape drive, optical disc, or USB flash drive. Creating a disk image is usually done by creating complete sector-by-sector copy of the source medium. Thereby perfect replicating the structure and contents of a storage device.

In our case, however, we are not copying real disk. We create it, literally. What we will do is creating an empty file with sufficient size before we do something to it.

If you have experience with Virtual Machine and ever creating disk image for particular VM (for example, VirtualBox VDI), you should know that it is slightly different thing. Yes, it is still a disk image, but we have extra metadata and various thing over it.

Now, to create our blank disk image of size 50MB, we invoke following command:

dd if=/dev/zero of=disk.img bs=512 count=97656

The dd utility is used with following argument:

  • if=/dev/zero, we specify the input is /dev/zero. This is a special node in Linux which generate a zero every time it is read.
  • of=disk.img, we specify the output will be a file named disk.img.
  • bs=512, we set the block size to 512 byte. Actually you can set the zie to any convenient number. Anything will do but I choose this number.
  • count=97656, we specify how many block we will write. So, in our case, we will have 97656 blocks or 97656 x512 byte = 49999872 bytes or around 50MB. I got the number by calculating 50*1000*1000/512.

Creating the partition.img is in similar manner.

Single Partitioned Disk Image

Having partition.img, we are ready to format the image into certain partition. I want an EXT4 format, so i use following command:

mkfs.ext4 partition.img

The command will take partition.img and format the partition with to EXT4 file system.

In general, we are attempting to imitate a partition. Later we can mount the partition by:

mount -o loop partition.img /mnt/partition

Now you can mount the partition and copy files tot he /mnt/partition and they will be written to our image file.

Multiple Partitioned Disk Image

In this section we will create a disk image with multiple partitions. In other words, we are trying to imitate the real disk.

The procedure is basically similar, but the image file must first be partitioned. So, more work involved here.

As in our case, we will create two partitions. First partition will occupy 10MB. The rest will be allocated to second partition.

fdisk disk.img

The fdisk utility is interactive program and quite clear. You just need to choose right option and enter right number for start and end of partition. Before you proceed, make sure you print current condition (using option p). Fdisk will display how many heads, sectors, and cylinders it recognized. It also print out the size of sector.

Here is what specification we need:

Partition 1:
primary partition
First sector = 2048
Last sector = 22527

Partition 2:
primary partition
First sector = 22528
Last sector = 97655

If you see the number 97655 and wonder it might have something to do with the count=97656 argument to dd, you are sharp! It is truly last sector of our disk image.

Now the formatting would be bit complicated. In short, we have to make a loop back device to point a partition inside our disk image and then do formatting.

losetup /dev/loop0 disk.img -o 2048
losetup /dev/loop1 disk.img -o 22528

mkfs.ext4 /dev/loop0
mkfs.ext4 /dev/loop1

To mount our disk image, you can follow this article: Mounting Partition from Raw Disk Image on Linux

For you who are not patient enough, here’s how we mont both partitions:

mount -o loop,offset=1048576 disk.img /mnt/disk1

mount -o loop,offset=11534336 disk.img /mnt/disk2

Builder Design Pattern

December 11, 2015 | Article | No Comments

Builder is a creational design pattern, used to separate the construction of a complex object from its representation so that the same construction process can create different objects representations.

Unlike the abstract factory pattern and the factory method pattern whose intention is to enable polymorphism, the intention of the builder pattern is to find a solution to the telescoping constructor anti-pattern.

Problem

We want to construct a complex object, however we do not want to have a complex constructor member or one that would need many arguments.

Solution

Define an intermediate object whose member functions define the desired object part by part before the object is available to the client. Builder pattern lets us defer the construction of the object until all the options for creation have been specified.

Example

#include <string>
#include <iostream>
using namespace std;

// "Product"
class Pizza {
	string m_dough;
	string m_sauce;
	string m_topping;
public:
	void setDough(const string& dough)
	{
		m_dough = dough;
	}
	void setSauce(const string& sauce)
	{
		m_sauce = sauce;
	}
	void setTopping(const string& topping)
	{
		m_topping = topping;
	}
	void open() const
	{
		cout <<  "Pizza with " << m_dough << " dough, " << m_sauce << 
			" sauce and " << m_topping << " topping. Mmm." << endl;
	}
};

// "Abstract Builder"
class PizzaBuilder {
public:
	Pizza* getPizza()
	{
		return m_pizza;
	}
		void createNewPizzaProduct()
	{
		m_pizza = new Pizza;
	}
	virtual void buildDough() = 0;
	virtual void buildSauce() = 0;
	virtual void buildTopping() = 0;
protected:
	Pizza* m_pizza;
};
//----------------------------------------------------------------
class HawaiianPizzaBuilder : public PizzaBuilder {
public:
	virtual void buildDough()
	{
		m_pizza->setDough("cross");
	}
	virtual void buildSauce()
	{
		m_pizza->setSauce("mild");
	}
	virtual void buildTopping()
	{
		m_pizza->setTopping("ham+pineapple");
	}
};
class SpicyPizzaBuilder : public PizzaBuilder {
public:
	virtual void buildDough()
	{
		m_pizza->setDough("pan baked");
	}
	virtual void buildSauce()
	{
		m_pizza->setSauce("hot");
	}
	virtual void buildTopping()
	{
		m_pizza->setTopping("pepperoni+salami");
	}
};
//----------------------------------------------------------------
class Cook {
	PizzaBuilder* m_pizzaBuilder;
public:
	void setPizzaBuilder(PizzaBuilder* pb)
	{
		m_pizzaBuilder = pb;
	}
	Pizza* getPizza()
	{
		return m_pizzaBuilder->getPizza();
	}
	void constructPizza()
	{
		m_pizzaBuilder->createNewPizzaProduct();
		m_pizzaBuilder->buildDough();
		m_pizzaBuilder->buildSauce();
		m_pizzaBuilder->buildTopping();
	}
};
int main() {
	Cook cook;
	PizzaBuilder* hawaiianPizzaBuilder = new HawaiianPizzaBuilder;
	PizzaBuilder* spicyPizzaBuilder = new SpicyPizzaBuilder;
	cook.setPizzaBuilder(hawaiianPizzaBuilder);
	cook.constructPizza();
	Pizza* hawaiian = cook.getPizza();
	hawaiian->open();
	cook.setPizzaBuilder(spicyPizzaBuilder);
	cook.constructPizza();
	Pizza* spicy = cook.getPizza();
	spicy->open();

	delete hawaiianPizzaBuilder;
	delete spicyPizzaBuilder;
	delete hawaiian;
	delete spicy;
}

Notes

Pattern in Action

Installing PostGIS From Source on Slackware64

December 11, 2015 | Article | No Comments

PostGIS is a spatial database extender for PostgreSQL object-relational database. It adds support for geographic objects allowing location queries to be run in SQL. In effect, PostGIS “spatially enables” the PostgreSQL server, allowing it to be used as a backend spatial database for geographic information systems (GIS).

PostGIS is a free open source project, licensed under GNU GPLv2.

In this article, we will discuss about how to install PostGIS on Slackware64. For this purpose, we will use following materials:

  1. Slackware64 14.0
  2. PostgreSQL 9.3.5
  3. GEOS 3.4.2
  4. GDAL 1.11
  5. Proj 4.8.0
  6. JSON-C 0.11
  7. PostGIS 2.1.3

Obtain Materials

PostgreSQL is a DBMS which can be freely downloaded from PostgreSQL. Or download the latest version 9.35 here.

GEOS is Geometry Engine – Open Source, a C++ post of the Java Topology Suite (JTS). To download it, go to GEOS page or download GEOS 3.4.2 from here.

GDAL is Geospatial Data Abstraction Library. To download it, go to GDAL page or download GDAL 1.11 from here.

PROJ4 is a cartographic projections library. To download it, go to PROJ4 page or download PROJ 4.8.0 from here.

JSON-C is a library to read/write JSON objects in C. To downloat it, download JSON-C directly from here.

Now, our main dish. Download PostGIS from PostGIS page, or download it directly from here.

In the end of this section, you should have:

  1. postgresql-9.3.5.tar.bz2
  2. geos-3.4.2.tar.bz2
  3. gdal-1.11.0.tar.xz
  4. proj-4.8.0.tar.gz
  5. json-c-0.11.tar.gz
  6. postgis-2.1.3.tar.gz

Install

Dependency

We will install all dependency in this order:

  1. PostgreSQL
  2. GEOS
  3. GDAL
  4. PROJ4
  5. JSON-C

All the installation procedure will require root privilege.

Installation of PostgreSQL has been discussed in different article. See here to read it. You can also skip it if you have already installed PostgreSQL.

Next, install GEOS.

tar -jxf geos-3.4.2.tar.bz2
cd geos-3.4.2
./configure
make -j4
make install

Next, install GDAL.

tar -Jxf gdal-1.11.0.tar.xz
cd gdal-1.11.0
./configure
make -j4
make install

Next, install PROJ4.

tar -zxf proj-4.8.0.tar.gz
cd proj-4.8.0
./configure
make -j4
make install

When building PROJ4, you might encounter error like this:

jniproj.c:52:26: fatal error: org_proj4_PJ.h: No such file or directory

To solve it, go to src directory and edit jniproj.c then change this line

#include "org_proj4_PJ.h"

to

#include "org_proj4_Projections.h"

then resume the installation.

Next, install JSON-C. There is option to use the JSON-C from their github, but when I try it, it would break as JSON-C has removed some macro and functions. So let’s use it as is.

tar -zxf json-c-0.11.tar.gz
cd json-c-0.11
./configure
make -j4
make install

Now we are ready to install PostGIS.

PostGIS

Installing PostGIS is straightforward.

tar -zxf postgis-2.1.3.tar.gz
cd postgis-2.1.3
./configure
make -j4
make install

Installation finished. You should have PostGIS installed and ready.

Configuration

Enabling PostGIS

PostGIS is an optional extension that must be enabled in each database you want to use it before you can use it. Installing the software is just the first step. And do not install it in the database called “postgres”.

Connect to database using psql. Run the following SQL:

-- Enable PostGIS (includes raster)
CREATE EXTENSION postgis;
-- Enable Topology
CREATE EXTENSION postgis_topology;
-- fuzzy matching needed for Tiger
CREATE EXTENSION fuzzystrmatch;
-- Enable US Tiger Geocoder
CREATE EXTENSION postgis_tiger_geocoder;

Example of Spatial SQL

-- Create table with spatial column
CREATE TABLE mytable ( 
  id SERIAL PRIMARY KEY,
  geom GEOMETRY(Point, 26910),
  name VARCHAR(128)
); 

-- Add a spatial index
CREATE INDEX mytable_gix
  ON mytable 
  USING GIST (geom); 

-- Add a point
INSERT INTO mytable (geom) VALUES (
  ST_GeomFromText('POINT(0 0)', 26910)
);

-- Query for nearby points
SELECT id, name
FROM mytable
WHERE ST_DWithin(
  geom, 
  ST_GeomFromText('POINT(0 0)', 26910),
  1000
);

PostgreSQL, often simply “Postgres”, is an object-relational database management system (ORDBMS) with an emphasis on extensibility and standards-compliance. With more than 15 years of development history, it is quickly becoming the de facto database for enterprise level open source solutions.

In this article we will discuss about how to install PostgreSQL from source on Slackware64. Our objective is to make PostgreSQL installed and running on our machine.

The PostgreSQL we will use is the PostgreSQL 9.3.5

Obtain Material

The PostgreSQL is freely distributed under open source flag. You can go to PostgreSQL download page to obtain the source code. For version 9.3.5, we can download directly from here.

Installation

Extract the source code and go to that directory.

tar -jxf postgresql-9.3.5.tar.bz2
cd postgresql-9.3.5

Installation is using usual procedure in unix family: configure, make, install. Note that we are using /usr/local as our installation directory (where the PostgreSQL will reside). You can change it to anything you like. Root privileges is not necessary for compilation process, however it is need to install it to our directory /usr/local. If you choose to install it to non-root privileged area, you can drop the “su -c” thing.

./configure --prefix=/usr/local
make -j4
su -c "make install"

At this point, PostgreSQL is installed, but can’t yet be operational. Let’s do configuration.

Configuration

PostgreSQL User Account

We need a “postgres” user and group prior to building PostgreSQL. Do this using root privilege.

groupadd postgres
useradd -d /var/lib/pgsql postgres
passwd postgres

PostgreSQL Data Directory

Now we need to create PostgreSQL data directory if not exist. The data directory should be owned by postgres user.

mkdir /var/lib/pgsql/data
chown -Rf postgres:postgres /var/lib/pgsql

Initialize the directory. Before we can start creating any PostgreSQL database, the empty directory created above should be initialized.

su - postgres
/usr/bin/initdb -D /var/lib/pgsql/data

Next, validate the PostgreSQL data directory. Make sure all Postgres DB configuration file are created under the data directory.

Start PostgreSQL database. There are two ways to do it: using postmaster to do it, or invoking script.

/usr/bin/postmaster -D /var/lib/pgsql/data

or

/etc/rc.d/rc/postgres start

PostgreSQL Service

To make PostgreSQL run as service, we should make the init script executable.

chmod +x /etc/rc.d/rc.postgres

First Login

Let’s try our fresh build PostgreSQL.

psql -U postgres

where postgres is user account we have created before.

Introduction to AVR Registers

December 11, 2015 | Article | No Comments

What is Register?

Micro controller operations mostly involve processing data. Registers is used to do operations in CPU.

Registers are special storages in CPU with capacity of certain bits. In 8-bit AVR, a register is 8 bits wide which can hold data of 8-bits (1 byte). In nutshell, they do like this:

7 6 5 4 3 2 1 0

Note the numeration of these bits: the least significant bit starts with zero (20 = 1).

A register can either store numbers from 0 to 255 (positive number, no negative values), or numbers from -128 to +127 (whole number with a sign bit in bit 7), or a value representing an ASCII-coded character (e.g. ‘A’), or just eight single bits that do not have something to do with each other (e.g. for eight single flags used to signal eight different yes/no decisions).

The special character of registers, compared to other storage sites, is that

  • they can be used directly in assembler commands,
  • operations with their content require only a single command word,
  • they are connected directly to the central processing unit called the accumulator,
  • they are source and target for calculations.

Registers are commonly divided into three categories:

  1. General purpose registers
  2. Control & Status registers
  3. Segment registers

A general purpose registers are registers which is used to hold data for operations. They can be used as operand which will be operated by ALU (Arithmetic & Logic Unit), or as result of the operations.

The Control and Status registers are used to control the micro controller. They are used to determine the control flow of the program. Many instructions involve comparisons and mathematical calculations. Those operations will changes some part of flags. Other conditional instruction test the value of these status flags to take the control to other location.

Segment registers are registers which is used to point different segment in the memory. Segments are specific areas defined in a program for containing data or instruction.

Registers in AVR

General Purpose Register

AVR micro controllers have 32 general purpose 8-bit registers, named R0 to R31. All arithmetic operations operate on those registers, only load and store instructions access RAM. A limited number of instruction operate on 16-bit register pairs. The lower-numbered register of the pair holds the least significant bits and must be even-numbered. The last three register pairs are used as pointer registers for memory addressing. They are known as X (R27:R26), Y (R29:R28) and Z (R31:R30). Postincrement and predecrement addressing modes are supported on all three. Y and Z also support a six-bit positive displacement.

Instructions which allow an immediate value are limited to registers R16–R31 (8-bit operations) or to register pairs R25:R24–R31:R30 (16-bit operations ADIW and SBIW). Some variants of the MUL operation are limited to eight registers, R16 through R23.

Control and Status Register

In addition to those 32 general-purpose registers, the CPU has a few special-purpose registers:

  • PC: 16- or 22-bit program counter
  • SP: 8- or 16-bit stack pointer
  • SREG: 8-bit status register

The status register bits are:

  1. C Carry flag. This is a borrow flag on subtracts.
  2. Z Zero flag. Set to 1 when an arithmetic result is zero.
  3. N Negative flag. Set to a copy of the most significant bit of an arithmetic result.
  4. V Overflow flag. Set in case of two’s complement overflow.
  5. S Sign flag. Unique to AVR, this is always N⊕V, and shows the true sign of a comparison.
  6. H Half carry. This is an internal carry from additions and is used to support BCD arithmetic.
  7. T Bit copy. Special bit load and bit store instructions use this bit.
  8. I Interrupt flag. Set when interrupts are enabled.

The Carry flag is used for shift and rotate instructions.

If the Global Interrupt Flag is set, the mcu will perform the Interrupt Service Routine corresponding to the interrupt that occurred.

Just remember: They are important for mathematical operations, and changing them between calculating a value and comparing it with something else might be fatal. That’s why Interrupt Service routines should preserve the SREG and any other registers they use (unless these registers are unused in normal code). An interrupt might occur between comparing two values with each other and a following branch – the ISR might change status flags and corrupt the flags the branch relies on.

Segment Registers

AVR micro controller has some 8-bits segment registers, named: RAMPX, RAMPY, RAMPZ, RAMPD, and EIND. These registers are prepended to 16-bit addresses in order to form 24-bit address; only available in parts with large address spaces.

You should remember that AVR use modified Harvard architecture which separate the instructions and the data.It is different to Intel x86 where instruction and data are stored in same memory.

Social media & sharing icons powered by UltimatelySocial