Tagged: C++

Static and extern keywords in C

These keywords used to literally haunt my dreams back in the day, when I was a freshman at BUT. I was just getting grips with C at that time and whenever I tried to use them, I got it all wrong. I’m talking about the magic keywords — static and extern. Both of them have multiple uses in C code and slightly different behavior in each case. For a beginner it might seem like a total anarchy, but it will start to make sense at some point. So, let’s get to the point …

Both of these modifiers have something to do with memory allocation and linking of your code. C standard[3] refers to them as storage-class specifiers. Using those allows you to specify when to allocate memory for your object and/or how to link it with the rest of the code.  Let’s have look on what exactly is there to specify first.

Linking in C

There are three types of linkage — external, internal and none. Each declared object in your program (i.e. variable or function) has some kind of linkage — usually specified by the circumstances of the declaration. Linkage of an object says how is the object propagated through the whole program. Linkage can be modified by both keywords extern and static.

External Linkage

Objects with external linkage can be seen (and accessed) through the whole program across the modules. Anything you declare at file (or global) scope has external linkage by default. All global variables and all functions have external linkage by default.

Internal Linkage

Variables and functions with internal linkage are accessible only from one compilation unit — the one they were defined in. Objects with internal linkage are private to a single module.

None Linkage

None linkage makes the objects completely private to the scope they were defined in. As the name suggests, no linking is done. This applies to all local variables and function parameters, that are only accessible from within the function body, nowhere else.

Storage duration

Another area affected by these keywords is storage duration, i.e. the lifetime of the object through the program run time. There are two types of storage duration in C — static and automatic.

Objects with static storage duration are initialized on program startup and remain available through the whole runtime. All objects with external and internal linkage have also static storage duration. Automatic storage duration is default for objects with no linkage. These objects are allocated upon entry to the block in which they were defined and removed when the execution of the block is ended. Storage duration can be modified by the keyword static.

Static

There are two different uses of this keyword in C language. In the first case, static modifies linkage of a variable or function. The ANSI standard states:

If the declaration of an identifier for an object or a function has file scope and contains the storage-class specifier static, the identifier has internal linkage.

This means if you use the static keyword on a file level (i.e. not in a function), it will change the object’s linkage to internal, making it private only for the file or more precisely, compilation unit.

/* This is file scope */

int one; /* External linkage. */
static int two; /* Internal linkage. */

/* External linkage. */
int f_one()
{
    return one;
}

/* Internal linkage. */
static void f_two()
{
    two = 2;
}

int main(void)
{
    int three = 0; /* No linkage. */

    one = 1;
    f_two();

    three = f_one() + two;

    return 0;
}

The variable and function() will have internal linkage and won’t be visible from any other module.

The other use of static keyword in C is to specify storage duration. The keyword can be used to change automatic storage duration to static. A static variable inside a function is allocated only once (at program startup) and therefore it keeps its value between invocations. See the example from Stack Overflow[2].

#include <stdio.h>

void foo()
{
    int a = 10;
    static int sa = 10;

    a += 5;
    sa += 5;

    printf("a = %d, sa = %d\n", a, sa);
}

int main()
{
    int i;

    for (i = 0; i < 10; ++i)
        foo();
}

The output will look like this:

a = 15, sa = 15
a = 15, sa = 20
a = 15, sa = 25
a = 15, sa = 30
a = 15, sa = 35
a = 15, sa = 40
a = 15, sa = 45
a = 15, sa = 50
a = 15, sa = 55
a = 15, sa = 60

Extern

The extern keyword denotes, that “this identifier is declared here, but is defined elsewhere”. In other words, you tell the compiler that some variable  will be available, but its memory is allocated somewhere else.

The thing is, where? Let’s have a look at the difference between declaration and definition of some object first. By declaring a variable, you say what type the variable is and what name it goes by later in your program. For instance you can do the following:

extern int i; /* Declaration. */
extern int i; /* Another declaration. */

The variable virtually doesn’t exist until you define it (i.e. allocate memory for it). The definition of a variable looks like this:

int i = 0; /* Definition. */

You can put as many declaration as you want into your program, but only one definition within one scope. Here is an example that comes from the C standard:

/*  definition, external linkage */
int i1 = 1;
/*  definition, internal linkage */
static int i2 = 2;
/*  tentative definition, external linkage */
int i3;

/*  valid tentative definition, refers to previous */
int i1;
/*  valid tenative definition, refers to previous */
static int i2;
/*  valid tentative definition, refers to previous */
int i3 = 3;

/* refers to previous, whose linkage is external */
extern int i1;
/* refers to previous, whose linkage is internal */
extern int i2;
/* refers to previous, whose linkage is external */
extern int i4;

int main(void) { return 0; }

This will compile without errors.

Summary

Remember that static — the storage-class specifier and static storage duration are two different things. Storage duration is a attribute of objects that in some cases can be modified by static, but the keyword has multiple uses.

Also the extern keyword and external linkage represent two different areas of interest. External linkage is an object attribute saying that it can be accessed from anywhere in the program. The keyword on the other hand denotes, that the object declared is not defined here, but someplace else.

Sources

Design Patterns: Bridge

Today I’m going to write some examples of Bridge. The design pattern not the game. Bridge is a structural pattern that decouples abstraction from the implementation of some component so the two can vary independently. The bridge pattern can also be thought of as two layers of abstraction[3].

Bridge pattern is useful in times when you need to switch between multiple implementations at runtime. Another great case for using bridge is when you need to couple pool of interfaces with a pool of implementations (e.g. 5 different interfaces for different clients and 3 different implementations for different platforms). You need to make sure, that there’s a solution for every type of client on each platform. This could lead to very large number of classes in the inheritance hierarchy doing virtually the same thing. The implementation of the abstraction is moved one step back and hidden behind another interface. This allows you to outsource the implementation into another (orthogonal) inheritance hierarchy behind another interface. The original inheritance tree uses implementation through the bridge interface. Let’s have a look at diagram in Figure 1.

Bridge pattern UML diagram

Figure1: Bridge pattern UML diagram

As you can see, there are two orthogonal inheritance hierarchies. The first one is behind ImplementationInterface. This implementation is injected using aggregation through Bridge class into the second hierarchy under the AbstractInterface. This allows having multiple cases coupled with multiple underlying implementations. The Client then uses objects through AbstractInterface. Let’s see it in code.

C++

/* Implemented interface. */
class AbstractInterface
{
    public:
        virtual void someFunctionality() = 0;
};

/* Interface for internal implementation that Bridge uses. */
class ImplementationInterface
{
    public:
        virtual void anotherFunctionality() = 0;
};

/* The Bridge */
class Bridge : public AbstractInterface
{
    protected:
        ImplementationInterface* implementation;

    public:
        Bridge(ImplementationInterface* backend)
        {
            implementation = backend;
        }
};

/* Different special cases of the interface. */

class UseCase1 : public Bridge
{
    public:
        UseCase1(ImplementationInterface* backend)
          : Bridge(backend)
        {}

        void someFunctionality()
        {
            std::cout << "UseCase1 on ";
            implementation->anotherFunctionality();
        }
};

class UseCase2 : public Bridge
{
    public:
        UseCase2(ImplementationInterface* backend)
          : Bridge(backend)
        {}

        void someFunctionality()
        {
            std::cout << "UseCase2 on ";
            implementation->anotherFunctionality();
        }
};

/* Different background implementations. */

class Windows : public ImplementationInterface
{
    public:
        void anotherFunctionality()
        {
            std::cout << "Windows" << std::endl;
        }
};

class Linux : public ImplementationInterface
{
    public:
        void anotherFunctionality()
        {
            std::cout << "Linux!" << std::endl;
        }
};

int main()
{
    AbstractInterface *useCase = 0;
    ImplementationInterface *osWindows = new Windows;
    ImplementationInterface *osLinux = new Linux;

    /* First case */
    useCase = new UseCase1(osWindows);
    useCase->someFunctionality();

    useCase = new UseCase1(osLinux);
    useCase->someFunctionality();

    /* Second case */
    useCase = new UseCase2(osWindows);
    useCase->someFunctionality();

    useCase = new UseCase2(osLinux);
    useCase->someFunctionality();

    return 0;
}

Download complete source file from github.

Python


class AbstractInterface:

    """ Target interface.

    This is the target interface, that clients use.
    """

    def someFunctionality(self):
        raise NotImplemented()

class Bridge(AbstractInterface):

    """ Bridge class.
    
    This class forms a bridge between the target
    interface and background implementation.
    """

    def __init__(self):
        self.__implementation = None

class UseCase1(Bridge):

    """ Variant of the target interface.

    This is a variant of the target Abstract interface.
    It can do something little differently and it can
    also use various background implementations through
    the bridge.
    """
    
    def __init__(self, implementation):
        self.__implementation = implementation

    def someFunctionality(self):
        print "UseCase1: ",
        self.__implementation.anotherFunctionality()

class UseCase2(Bridge):
    def __init__(self, implementation):
        self.__implementation = implementation

    def someFunctionality(self):
        print "UseCase2: ",
        self.__implementation.anotherFunctionality()

class ImplementationInterface:
    
    """ Interface for the background implementation.

    This class defines how the Bridge communicates
    with various background implementations.
    """

    def anotherFunctionality(self):
        raise NotImplemented

class Linux(ImplementationInterface):

    """ Concrete background implementation.

    A variant of background implementation, in this
    case for Linux!
    """

    def anotherFunctionality(self):
        print "Linux!"

class Windows(ImplementationInterface):
    def anotherFunctionality(self):
        print "Windows."

def main():
    linux = Linux()
    windows = Windows()

    # Couple of variants under a couple
    # of operating systems.
    useCase = UseCase1(linux)
    useCase.someFunctionality()

    useCase = UseCase1(windows)
    useCase.someFunctionality()

    useCase = UseCase2(linux)
    useCase.someFunctionality()

    useCase = UseCase2(windows)
    useCase.someFunctionality()

Download complete source file from github.

Summary

The Bridge pattern is very close to the Adapter by it’s structure, but there’s a huge difference in semantics. Bridge is designed up-front to let the abstraction and the implementation vary independently. Adapter is retrofitted to make unrelated classes work together [1].

Sources

  1. http://sourcemaking.com/design_patterns/bridge
  2. http://www.oodesign.com/bridge-pattern.html
  3. http://en.wikipedia.org/wiki/Bridge_pattern

Design Patterns: Adapter

And back to design patterns! Today it’s time to start with structural patterns, since I have finished all the creational patterns. What are those structural patterns anyway?

In Software Engineering, Structural Design Patterns are Design Patterns that ease the design by identifying a simple way to realize relationships between entities.

The first among the structural design patterns is Adapter. The name for it is totally appropriate, because it does exactly what any other real-life thing called adapter does. It converts some attribute of one device so it is usable together with another one. Most common adapters are between various types of electrical sockets. The adapters usually convert the voltage and/or the shape of the connector so you can plug-in different devices.

The software adapters work exactly like the outlet adapters. Imagine having (possibly a third-party) class or module you need to use in your application. It’s poorly coded and it would pollute your nicely designed code. But there’s no other way, you need it’s functionality and don’t have time to write it from scratch. The best practice is to write your own adapter and wrap the old code inside of it. Then you can use your own interface and therefore reduce your dependence on the old ugly code.

Especially, when the code comes from a third-party module you have no control on whatsoever. They could change something which would result in breaking your code on many places. That’s just unacceptable.

Adapter pattern example

UML example of adapter pattern

Here is an example class diagram of adapter use. You see there is some old interface which the adapter uses. On the other end, there is new target interface that the adapter implements. The client (i.e. your app) then uses the daisy fresh new interface. For more explanation see the source code examples bellow.

C++

typedef int Cable; // wire with electrons

/* Adaptee (source) interface */
class EuropeanSocketInterface
{
    public:
        virtual int voltage() = 0;

        virtual Cable live() = 0;
        virtual Cable neutral() = 0;
        virtual Cable earth() = 0;
};

/* Adaptee */
class Socket : public EuropeanSocketInterface
{
    public:
        int voltage() { return 230; }

        Cable live() { return 1; }
        Cable neutral() { return -1; }
        Cable earth() { return 0; }
};

/* Target interface */
class USASocketInterface
{
    public:
        virtual int voltage() = 0;

        virtual Cable live() = 0;
        virtual Cable neutral() = 0;
};

/* The Adapter */
class Adapter : public USASocketInterface
{
    EuropeanSocketInterface* socket;

    public:
        void plugIn(EuropeanSocketInterface* outlet)
        {
            socket = outlet;
        }

        int voltage() { return 110; }
        Cable live() { return socket->live(); }
        Cable neutral() { return socket->neutral(); }
};

/* Client */
class ElectricKettle
{
    USASocketInterface* power;

    public:
        void plugIn(USASocketInterface* supply)
        {
            power = supply;
        }

        void boil()
        {
            if (power->voltage() > 110)
            {
                std::cout << "Kettle is on fire!" << std::endl;
                return;
            }

            if (power->live() == 1 && power->neutral() == -1)
            {
                std::cout << "Coffee time!" << std::endl;
            }
        }
};

int main()
{
    Socket* socket = new Socket;
    Adapter* adapter = new Adapter;
    ElectricKettle* kettle = new ElectricKettle;

    /* Pluging in. */
    adapter->plugIn(socket);
    kettle->plugIn(adapter);

    /* Having coffee */
    kettle->boil();

    return 0;
}

Download example from Github.

Python

# Adaptee (source) interface
class EuropeanSocketInterface:
    def voltage(self): pass

    def live(self): pass
    def neutral(self): pass
    def earth(self): pass

# Adaptee
class Socket(EuropeanSocketInterface):
    def voltage(self):
        return 230

    def live(self):
        return 1

    def neutral(self):
        return -1

    def earth(self):
        return 0

# Target interface
class USASocketInterface:
    def voltage(self): pass

    def live(self): pass
    def neutral(self): pass

# The Adapter
class Adapter(USASocketInterface):
    __socket = None

    def __init__(self, socket):
        self.__socket = socket

    def voltage(self):
        return 110

    def live(self):
        return self.__socket.live()

    def neutral(self):
        return self.__socket.neutral()

# Client
class ElectricKettle:
    __power = None

    def __init__(self, power):
        self.__power = power

    def boil(self):
        if self.__power.voltage() > 110:
            print "Kettle on fire!"
        else:
            if self.__power.live() == 1 and \
               self.__power.neutral() == -1:
                print "Coffee time!"
            else:
                print "No power."

def main():
    # Plug in
    socket = Socket()
    adapter = Adapter(socket)
    kettle = ElectricKettle(adapter)

    # Make coffee
    kettle.boil()

    return 0

if __name__ == "__main__":
    main()

Download example from Github.

Summary

The adapter uses the old rusty interface of a class or a module and maps it’s functionality to a new interface that is used by the clients. It’s kind of wrapper for the crappy code so it doesn’t get your code dirty.

Sources

Interface Segregation Principle in Software Design

ISP, not Internet Service Provider, but Interface Segregation Principle is the last of the famous principles of SOLID object-oriented software design. It was introduced by Robert C. Martin in his series of articles in 1996. Intention of this principle is to avoid creation of “fat” interfaces.

A fat (or polluted) interface comes from extending current interface with some functionality that is useful only to a subset of entities that depends on it. This phenomenon leads eventually to creation of dummy methods just to be able to use the interface. And that’s bad. Dummy methods are dangerous and also violate the LSP. The ISP as wrote the author declares that

Clients should not be forced to depend upon interfaces that they do not use.

Each interface should have clearly defined purpose and make reasonable abstraction of a part of the current problem. The best practice (in my opinion) is to use multiple inheritance when implementing the interfaces. This method will separate things that don’t logically belong together on the abstraction level and clean wrong dependencies in our code. But it also allow us to couple them back together in objects, that cover multiple things and work on the same data.

Let me show an example of how it should not look like. This is an interface for a car.

/* Bad example */
class CarOperation
{
    public:
        virtual void steer(int degrees) = 0;
        virtual void pullHandbrake() = 0;
        virtual void accelerate() = 0;

        virtual void shift(int gear) = 0;

        virtual void toggleAirConditioning() = 0;
};

There are a couple common things you can do with a car. Every car usually has a steering wheel, an acceleration pedal and possibly even a handbrake. But what about those cars with automatic transmission? They don’t allow the driver to shift gears, so what should they do with the shift method? The interface enforces it’s implementaion. And again with air conditioning. Some cars don’t have an air conditioner. The way here is to split CarOperationinterface into a couple smaller ones.

class BasicCarOperation
{
    public:
        virtual void steer(int degrees) = 0;
        virtual void pullHandbrake() = 0;
        virtual void accelerate() = 0;
};

class GearboxCarOperation
{
    public:
        virtual void shift(int gear) = 0;
};

class AirConditioningCarOperation
{
    public:
        virtual void toggleAirConditioning() = 0;
};

class AlfaRomeo166 : public BasicCarOperation, GearboxCarOperation, AirConditioningCarOperation
{
    /* Implementation of all the interfaces. */
};

class SkodaFavorit136L : public BasicCarOperation, GearboxCarOperation
{
    /* No air conditioning for old cars. */
};

The clients that will use the concrete cars won’t look at them directly as AlfaRomeo166 or SkodaFavorit136L. They will operate them through the interfaces. If some client function wants to turn on a air-conditioning it will look like this

void beCool(AirConditioningCarOperation* vehicle)
{
    vehicle->toggleAirConditioning();
}

That’s the beauty of interface segregation principle. You get exactly what you need, nothing more and nothing less, which makes the code easier to maintain, reuse and saves you from a cascade of unpredictable errors, when you decide to modify existing code.

Sources

Dependency Inversion Principle

DIP or Dependency Inversion Principle is yet another guideline for the software designers that work in object-oriented environment. It’s the D in SOLID and it has one huge advantage over the other principles: in case it doesn’t work for you, you can always get some tortilla chips to help (they work wonderfully with dip ;-)).

This principle was introduced by Robert C. Martin in his article in 1996. He points out that the usual way of dependency design among software project is to make general high-level modules dependent on the low-level utilities and mechanism that do the hard (and in most cases also not very interesting) work. This way of dependency makes the high level modules very hard to reuse without many modifications (and people often thing “why the hell didn’t I wrote it again”). And this is wrong.

The high-level modules are key part of the application. That’s where the heart of the application actually is. The algorithm that knows how to use the lower-level modules to achieve the desired functionality of our application. And we want to reuse that without having to modify every third line, so what do we do?

Mr. Martin proposes the Dependency Inversion Principle, which says

A. High level modules should not depend upon low level modules. Both should depend upon abstractions.
B. Abstractions should not depend upon details. Details should depend upon abstractions.

It’s a little tough one to understand at first, so let me explain. The principle states, that there should be some additional layer between high and low level modules — the layer of abstractions. The author says, that there should be an interface (or abstraction) defined between those two modules on whom should both depend. That way high level modules don’t work directly with the low level classes. Low level classes implement the interfaces. In case you’d like to take some module out and use it elsewhere, you don’t need to touch anything inside that module. You simply take it out and implement the interfaces upon which the module depends. Isn’t that awesome?

The second part (part B.) makes clear that the abstractions (or interfaces) should not be designed according to the low level modules (the details). That’s something that might come naturally to a lazy coder “yeah, I’ll just duplicate the header file, make all methods pure virtual and I’m good to go”, no. The interfaces have to be implemented on the same level of abstraction as the high level module otherwise they’re more than useless.

Example of Dependency Inversion

That would be the principle in theory. Let’s see some examples from user interfaces. We’ll have a Window class with two buttons.

class Button
{
    public:
        void makeVisible();
};

class Window
{
    Button* okButton;
    Button* cancelButton;

    Window()
    {
        okButton = new Button;
        okButton->makeVisible();

        cancelButton = new Button;
        cancelButton->makeVisible();
    }

};

The problem here is, that if the Button implementation changes, we’ll have to go here and change the constructor as well. We don’t want that, because the Window class were a subject of a lot of tests, it passed and any additional messing around in it might introduce errors into the class. Using the abstraction layer the situation would look like this

class IButton
{
    public:
        static virtual IButton* getInstance() = 0; // factory method
        virtual void show() = 0;
};

class Window
{
    IButton* okButton;
    IButton* cancelButton;

    public:
        Window()
        {
            okButton = IButton::getInstance();
            okButton->show();

            cancelButton = IButton::getInstance();
            cancelButton->show();
        }
};

class Button : public IButton
{
    public:
        void show();
};

Now, as you can see, there’s an interface IButton and both Button and Window depend on this interface. And that’s the dream. You can take the window and the interface place into an another application, implement the interface and you’re good to go! Note the factory method I used to be able to get the correct instance of buttons.

Sources

Design Patterns: Renderer

This post about design patterns will be a little unusual. To this day, I was going through a generally recognized set of design patterns that was introduced by the Gang of Four in Design Patterns: Elements of Reusable Object-Oriented Software. But today I want to introduce to you a useful design bit I came up with, while I was working on my bachelor’s thesis. I call it Renderer.

The problem I had was simple — unbelievable mess in my application’s source code. I was working on a procedural approach to rendering cities. And believe me, a city is kind of big-ass model to draw. There’s awful lot of rendering of different things on different places. And when it comes together it’s a giant blob of instructions. So I needed some way of structuring this rendering code and making it readable and if-I-got-lucky also extensible (don’t judge me, the due date was really haunting me in my sleep at the time). Finally I came up with a tree-like data structure.

What is a Renderer?

Glad you asked! It’s a class that renders stuff. The concept is reeeeeally simple, but it’s very powerful when you need to structure your code properly. The definition of the class is as simple like this

class Renderer
{
    public:
        virtual void render();
};

It’s actually more like interface. Every Renderer must implement this interface. The render() routine renders the content of the current renderer. The beauty of this concept is in the fact, that you can organize your renderers into a tree. The top-level renderer will render the object by delegating rendering of different parts to other renderers. This makes your code nicely structured as well as modular and reusable. Take for instance rendering of a car.

Cars can be visually relatively complex objects and it wouldn’t be nice to have all the rendering code in one class. If you wanted to draw a different car you’d have to write everything again even though that wheels are virtually the same in both models. But with using the renderer pattern, things would look like this

class CarRenderer : public Renderer
{
    CarBodyRenderer *body;
    WheelRenderer *wheels[4];
    WindowRenderer windshield;

    public:
        void render()
        {
            body->render();
            windshield->render();

            for (int i = 0; i < 4; i++)             {                 wheels[i]->render();
            }
        }
};

class CarBodyRenderer : public Renderer
{
    SpoilerRenderer* spoiler;
    HoodRenderer* hood;
    SkeletonRenderer* skeleton;
    DoorRenderer* doors[5];
    public:
         void render();
};

I guess you get the idea. You decompose the object into a set of smaller entities and render them instead. This decomposition can go on virtually forever, in extreme cases you could be able to render a car from pixels using this design pattern and still be able to look at your code and understand it. Anyway, let me know if you find this pattern useful!

Sources

Design Patterns: Object Pool

Last one from the family of creational patterns is Object Pool. The main purpose of object pool and why designers choose to incorporate to the software is a performance boost. Construction and destruction of object can become very expensive operation in some cases (especially if it occurs very often). Constant building and throwing away instances may significantly slow down your application. Object Pool pattern offers a solution to this problem.

Object pool is a managed set of reusable objects. Clients then “check out” objects from the pool return them back when they don’t need them any more. But it’s not that easy as it sounds. The manager of the pool has to deal with various problems.

  • What happens if the pool is empty and a client asks for an object?
    Some implementations work with growing pool of objects. That means if there’s no object available at the time of the request the pool manager creates one more. The manager can also destroy objects periodically when they’re not used. But what was the initial goal? Performance boost? Well, with this amount of overhead it might not be as fast. Another solution to the problem is simply to decline a client’s request if the pool is empty. This also slows down your system, because clients needs to do things right now and not wait for someone else to free up resources.
  • When the reservation expires?
    The other problem is dealing with errors. Every client must explicitly free up the resource when he’s done. But programmers are also only humans (well, in most cases) and there will be errors and your pool can easily become a hole full of zombies. So you might need to implement an algorithm for detecting and freeing expired reservations on resources in order to make stuff work properly.
  • Synchronization in multi-threaded applications
    Multi-threading brings into the game a whole other aspect. Two processes asking for resources at the same time. Some synchronization tools might be necessary as well.

As you can see, there are some serious drawbacks in this pattern. It’s a huge amount of work in the first place, if you decide to implement all the above. You need to consider every aspect very carefully before you implement the object pool and evaluate whether it really is, what you need.

The resource manager can be implemented many ways. Static class or singleton will work. I personally chose singleton. Here is my implementation of object pool:

C++

/*
 * Example of `object pool' design pattern
 * Copyright (C) 2011 Radek Pazdera
 */

class Resource
{
    int value;

    public:
        Resource()
        {
            value = 0;
        }

        void reset()
        {
            value = 0;
        }

        int getValue()
        {
            return value;
        }

        void setValue(int number)
        {
            value = number;
        }
};

/* Note, that this class is a singleton. */
class ObjectPool
{
    private:
        std::list<Resource*> resources;
        
        static ObjectPool* instance;
        ObjectPool() {}

    public:
        /**
         * Static method for accessing class instance.
         * Part of Singleton design pattern.
         *
         * @return ObjectPool instance.
         */
        static ObjectPool* getInstance()
        {
            if (instance == 0)
            {
                instance = new ObjectPool;
            }
            return instance;
        }

        /**
         * Returns instance of Resource.
         * 
         * New resource will be created if all the resources
         * were used at the time of the request.
         *
         * @return Resource instance.
         */
        Resource* getResource()
        {
            if (resources.empty())
            {
                std::cout << "Creating new." << std::endl;
                return new Resource;
            }
            else
            {
                std::cout << "Reusing existing." << std::endl;
                Resource* resource = resources.front();
                resources.pop_front();
                return resource;
            }
        }

        /**
         * Return resource back to the pool.
         *
         * The resource must be initialized back to
         * the default settings before someone else
         * attempts to use it.
         *
         * @param object Resource instance.
         * @return void
         */
        void returnResource(Resource* object)
        {
            object->reset();
            resources.push_back(object);
        }
};

int main()
{
    ObjectPool* pool = ObjectPool::getInstance();
    Resource* one;
    Resource* two;

    /* Resources will be created. */
    one = pool->getResource();
    one->setValue(10);
    std::cout << "one = " << one->getValue() << " [" << one << "]" << std::endl;

    two = pool->getResource();
    two->setValue(20);
    std::cout << "two = " << two->getValue() << " [" << two << "]" << std::endl;

    pool->returnResource(one);
    pool->returnResource(two);

    /* Resources will be reused. 
     * Notice that the value of both resources were reset back to zero.
     */
    one = pool->getResource();
    std::cout << "one = " << one->getValue() << " [" << one << "]" << std::endl;

    two = pool->getResource();
    std::cout << "two = " << two->getValue() << " [" << two << "]" << std::endl;
   
    return 0;
}

Download the fully working example from github.

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Example of `object pool' design pattern
# Copyright (C) 2011 Radek Pazdera

class Resource:

    """ Some resource, that clients need to use.
    
    The resources usualy have a very complex and expensive
    construction process, which is definitely not a case
    of this Resource class in my example.
    """

    __value = 0

    def reset(self):
        """ Put resource back into default setting. """
        self.__value = 0

    def setValue(self, number):
        self.__value = number

    def getValue(self):
        return self.__value


class ObjectPool:
    
    """ Resource manager.

    Handles checking out and returning resources from clients.
    It's a singleton class.
    """

    __instance = None
    __resources = list()

    def __init__(self):
        if ObjectPool.__instance != None:
            raise NotImplemented("This is a singleton class.")

    @staticmethod
    def getInstance():
        if ObjectPool.__instance == None:
            ObjectPool.__instance = ObjectPool()

        return ObjectPool.__instance

    def getResource(self):
        if len(self.__resources) > 0:
            print "Using existing resource."
            return self.__resources.pop(0)
        else:
            print "Creating new resource."
            return Resource()

    def returnResource(self, resource):
        resource.reset()
        self.__resources.append(resource)

def main():
    pool = ObjectPool.getInstance()

    # These will be created
    one = pool.getResource()
    two = pool.getResource()

    one.setValue(10)
    two.setValue(20)

    print "%s = %d" % (one, one.getValue())
    print "%s = %d" % (two, two.getValue())

    pool.returnResource(one)
    pool.returnResource(two)

    one = None
    two = None

    # These resources will be reused
    one = pool.getResource()
    two = pool.getResource()
    print "%s = %d" % (one, one.getValue())
    print "%s = %d" % (two, two.getValue())

Download the fully working example from github.

Sources

Brute-Force String Generation in C

Earlier this week, I posted an article about string generation for brute-force attacks and a couple of example solutions. I emphasized, that the key aspect of brute-force is speed. We want to try as many combinations of input data as possible in the minimum amount of time. And part of this is also efficient algorithm that will generate input combinations. But the examples I posted were written in Python, which is kind of a high level scripting language, not nearly as fast as C.

Hence, here is my implementation of the same in C:

/*
 * Basic string generation for brute-force attacks
 * Copyright (C) 2011 Radek Pazdera
 */

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

/* I chose to use an one way linked list data structure
 * to avoid restrictions on the generated string length.
 * The thing is, the list must be converted to string so
 * it could be used. This conversion have to happen in
 * each cycle and causes unnecessary slowdown.
 * 
 * Faster solution would be to implement the generation
 * directly on some staticaly allocated string with fixed
 * size (20 characters are more than enough).
 */
typedef struct charlist charlist_t;
struct charlist
{
    unsigned char character;
    charlist_t* next;
};

/* Return new initialized charlist_t element.
 *
 * Elements are initialized
 * @return charlist_t
 */
charlist_t* new_charlist_element()
{
    charlist_t* element;

    if ((element = malloc(sizeof(charlist_t))) != 0)
    {
        element->character = 0;
        element->next = NULL;
    }
    else
    {
        perror("malloc() failed.");
    }

    return element;
}

/* Free memory allocated by charlist.
 *
 * @param list Pointer at the first element.
 * @return void
 */
void free_charlist(charlist_t* list)
{
    charlist_t* current = list;
    charlist_t* next;

    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
}

/* Print the charlist_t data structure.
 *
 * Iterates through the whole list and prints all characters
 * in the list including any '\0'.
 * 
 * @param list Input list of characters.
 * @return void
 */
void print_charlist(charlist_t* list)
{
    charlist_t* next = list;
    while (next != NULL)
    {
        printf("%d ", next->character);
        next = next->next;
    }
    printf("\n");
}

/* Get next character sequence.
 *
 * It treats characters as numbers (0-255). Function tries to
 * increment character in the first position. If it fails,
 * new character is added to the back of the list.
 *
 * It's basicaly a number with base = 256.
 *
 * @param list A pointer to charlist_t.
 * @return void
 */
void next(charlist_t* list)
{
    list->character++;
    if (list->character == 0)
    {
        if (list->next == NULL)
        {
            list->next = new_charlist_element();
        }
        else
        {
            next(list->next);
        }
    }
}

int main()
{
    charlist_t* sequence;
    sequence = new_charlist_element();

    while (1)
    {
        next(sequence);
        print_charlist(sequence);
    }

    free_charlist(sequence);
}

Download the fully working code from github.

Design Patterns: Prototype

Prototype is one of the easier to understand design patterns. The intent of prototype is to create new instances of classes by cloning a prototype instance, rather than building them from scratch. This is particularly useful when the initialization of the objects is very expensive and very similar among the majority of created instances.

Take this for instance, you have some data stored on a remote server. You need them to initialize 1000 instances of some class during your program runtime. This data are static and very unlikely to be changed during the runtime of your application. You see, that downloading the data during initialization in constructor is pretty ineffective. Design like that would lead to exactly 999 pointless connections to the server and a lot of unnecessary network traffic, which is a gigantic waste of resources and time. If you use prototype instead, the application will download the data just once and the 1000 more instances will be cloned from the first one, saving us all the trouble.

There are three participants in the prototype pattern:

  • Client – creates a new object by asking a prototype to clone itself.
  • Prototype – declares an interface for cloning itself.
  • Concrete Prototype – implements the operation for cloning itself.

You also need a place where all the prototypes will be stored. A good practice is using a factory class that will cover the initial prototype setup  and will handle the cloning operations. This might remind you of the abstract factory design pattern. This is because they both are creational patterns and can be used to achieve the same behavior. The thing about prototype is that, you can dynamically change the prototype instance during the runtime and begin constructing something completely different with the same factory without sub-classing it.

Another way of dynamic handling a lot of prototype instances is prototype manager. A class that stores a pool of prototypes and makes decisions on which one to instantiate based on some parameters. This is particularly useful when the amount of prototypes isn’t fixed.

Now, let’s proceed to the code examples. I went with the first variant — a factory class for storing the prototypes.

C++

/*
* Example of `prototype' design pattern.
* Copyright (C) 2011 Radek Pazdera
*/

#include <iostream>
#include <string>

/* Prototype base class. */
class Prototype
{
    protected:
        std::string type;
        int value;

    public:
        virtual Prototype* clone() = 0;

        std::string getType()
        {
            return type;
        }

        int getValue()
        {
            return value;
        }
};

class ConcretePrototype1 : public Prototype
{
    public:
        ConcretePrototype1(int number)
        {
            type  = "Type1";
            value = number;
        }
        
        Prototype* clone()
        {
            return new ConcretePrototype1(*this);
        }
};

class ConcretePrototype2 : public Prototype
{
    public:
        ConcretePrototype2(int number)
        {
            type  = "Type2";
            value = number;
        }

        Prototype* clone()
        {
            return new ConcretePrototype2(*this);
        }
};

/* Factory that manages prorotype instances and produces their clones. */
class ObjectFactory
{
    static Prototype* type1value1;
    static Prototype* type1value2;
    static Prototype* type2value1;
    static Prototype* type2value2;

    public:
        static void  initialize()
        {
            type1value1 = new ConcretePrototype1(1);
            type2value1 = new ConcretePrototype2(1);
        }

        static Prototype* getType1Value1()
        {
            return type1value1->clone();
        }

        static Prototype* getType2Value1()
        {
            return type2value1->clone();
        }
};

int main()
{
    ObjectFactory::initialize();
    Prototype* object;

    /* All the object were created by cloning the prototypes. */
    object = ObjectFactory::getType1Value1();
    std::cout << object->getType() << ": " << object->getValue() << std::endl;

    object = ObjectFactory::getType2Value1();
    std::cout << object->getType() << ": " << object->getValue() << std::endl;

    return 0;
}

Download the fully working example from github.

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Example of `prototype' design pattern
# Copyright (C) 2011 Radek Pazdera

import copy

class Prototype:

    """ Object, that can be cloned.

    This is just a base class, so the clone() method
    is not implemented. But all subclasses have to
    override it.
    """

    _type  = None
    _value = None

    def clone(self):
        pass

    def getType(self):
        return self._type

    def getValue(self):
        return self._value

class Type1(Prototype):

    """ Concrete prototype.
    
    Implementation of Prototype. Important part is the
    clone() method.
    """

    def __init__(self, number):
        self._type = "Type1"
        self._value = number

    def clone(self):
        return copy.copy(self)

class Type2(Prototype):
    """ Concrete prototype. """

    def __init__(self, number):
        self._type = "Type2"
        self._value = number

    def clone(self):
        return copy.copy(self)

class ObjectFactory:

    """ Manages prototypes.

    Static factory, that encapsulates prototype
    initialization and then allows instatiation
    of the classes from these prototypes.
    """

    __type1Value1 = None
    __type2Value1 = None

    @staticmethod
    def initialize():
        ObjectFactory.__type1Value1 = Type1(1)
        ObjectFactory.__type2Value1 = Type2(1)
        
    @staticmethod
    def getType1Value1():
        return ObjectFactory.__type1Value1.clone()

    @staticmethod
    def getType2Value1():
        return ObjectFactory.__type2Value1.clone()


def main():
    ObjectFactory.initialize()

    instance = ObjectFactory.getType1Value1()
    print "%s: %s" % (instance.getType(), instance.getValue())

    instance = ObjectFactory.getType2Value1()
    print "%s: %s" % (instance.getType(), instance.getValue())

Download the fully working example from github.

Sources

String Generation for Brute-force Attacks

Everyone knows what a brute-force attack is. One of the most trivial (and yet pretty useful) methods of cracking passwords and breaking access keys. The idea is simply trying all possible sequences of input characters, until you guess the right combination. The thing is, that it might take some time. Actually, sometimes it might take literally ages, due to large number of possible outcomes. The faster our machines (and algorithms!) get, the lesser time it takes to break in using brute-force attack.

One of the key components in this technique is an algorithm that generates the input combinations. It’s run every time in the main loop. Well, the loop is pretty much generate a password, try it and try again. This article will present a couple of simple implementations of string sequence generators in various languages.

Python implementation

Here is code for a most basic example in Python. It’s a simple recursive function that is able to generate strings up to infinite length. I use a list instad of string in this example, because strings in python are immutable. You need to convert it to string ("".join(list)).

def next(string):
    if len(string)
        string.append(chr(0))
    else:
        string[0] = chr((ord(string[0]) + 1) % 256)
        if ord(string[0]) is 0:
            return list(string[0]) + next(string[1:])
    return string

Download the whole example from github.

This example is simple. It tries every possible combination which takes it’s success rate up to 100 percent. You just can’t miss anything if you try them all, right? But a lot of the characters from ASCII table are non-printable, weird and people don’t use them for passwords. So you spend a great amount of time by trying out combinations that are extremely unlikely to ever occur. It would be pretty awesome if there was some way of saying what characters can be part of a password string and use only them. The number of possible outcomes lowers a lot by this optimization while the chance to miss is still almost zero. I made a some alternations to the next() function above:

import string
ALLOWED_CHARACTERS = string.printable
NUMBER_OF_CHARACTERS = len(ALLOWED_CHARACTERS)

def characterToIndex(char):
    return ALLOWED_CHARACTERS.index(char)

def indexToCharacter(index):
    if NUMBER_OF_CHARACTERS
        raise ValueError("Index out of range.")
    else:
        return ALLOWED_CHARACTERS[index]

def next(string):
    if len(string)
        string.append(indexToCharacter(0))
    else:
        string[0] = indexToCharacter((characterToIndex(string[0]) + 1) % NUMBER_OF_CHARACTERS)
        if characterToIndex(string[0]) is 0:
            return list(string[0]) + next(string[1:])
    return string

This snippet above works only with printable characters (as specified in python’s string module). You can also change the subset of characters it works with by changing the value of ALLOWED_CHARACTERS constant. The whole source is again available at github.

Next time I’ll look into a C implementation of the technique and a comparison of speed between the two languages.