Easy way to merge (put together) several pdf files into single one in Linux

I've noticed, that convert utility from ImageMagick is a great tool to union PDF's into single one:
convert 1.pdf 2.pdf 3.pdf single.pdf

Using fsync and fsync_range with directories

There is a non-obvious difference between possible fd argument for fsync() and fsync_range(). In Linux and NetBSD you can use fsync() to sync directory. In NetBSD there is also fsync_range() which can't be used for directories, because it expects writable fd. Originally I thought that if fsync_range() can't, then fsync() can't too, but it can.

Example below shows how to obtain file descriptor for directory to use it with fsync:

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

#include <dirent.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>


int main() {
    int fd;
    DIR *dirp;
    int error;
    char path[] = "test_dir";

    if ((dirp = opendir(path)) == 0) {
        printf("Failed to open dir: %d\n", errno);
        return -1;
    }
    fd = dirfd(dirp);
    if (fd == -1) {
        printf("Failed to open: %d\n", errno);
        return -1;
    }

    if (fsync(fd) == -1) {
        printf("fsync_range failed: %d\n", errno);
        return -1;
    }
    return 0;
}

On the transparent conversion of Indirect (mutual) recursion to "no nested calls"

In a previous post I've shown how to implement functions in recursion-like style without nested call (real recursion). Implementing algorithms this way helps to save some memory (stack).
It made me wonder if we can convert/optimize mutual recursion in a way transparent to users. As basic example I chose following code:

int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}

Like in previous example I decided to use context manipulations plus function wrappers for even() and odd().
Unfortunately there is no way to wrap functions (symbols) referenced in same file as the symbol (check this). It gives some limitations: in our case even() and odd() should be separated into different source files. In common case our approach will not work with normal recursion (a()->a()) without source modification (not just recompiling with wrapper library as I wanted). Note, that if even() and odd() are in the shared library (most likely), then you can use LD_PRELOAD to wrap these functions and it will work just fine.

even.c:

int odd(int);

int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

odd.c:

int even(int);

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}

wrapped.c:

int __real_even(int n);
int __real_odd(int n);

volatile int even_odd_arg;
int (*volatile fp)(int);
volatile int even_odd_res;


void dispatch(ucontext_t *_return_context) {
    static ucontext_t *return_context = 0;
    if (return_context == NULL) {
        return_context = _return_context;
    }
    even_odd_res = fp(even_odd_arg);

    setcontext(return_context);
}

ucontext_t* get_dispatcher_context(ucontext_t* return_context)
{
    static ucontext_t dispatcher_context;
    static char iterator_stack[SIGSTKSZ];
    static initialized = 0;

    if (initialized)
        return &dispatcher_context;

    dispatcher_context.uc_stack.ss_sp   = iterator_stack;
    dispatcher_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&dispatcher_context);

    makecontext(&dispatcher_context, (void (*)(void)) dispatch,
                1, return_context);

    return &dispatcher_context;
}

int __wrap_even(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_even;
    swapcontext(&this_context, get_dispatcher_context(&this_context));

    return even_odd_res;
}


int __wrap_odd(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_odd;
    swapcontext(&this_context, get_dispatcher_context(&this_context));
    return even_odd_res;
}

main.c:

int even(int);

int main()
{
    int i;
    for (i = 0; i <= 10; i++) {
        int is_even = even(i);
        if (is_even)
            printf("%d is even\n", i);
        else
            printf("%d is odd\n", i);
    }
    return 0;
}

To compile use "gcc -c -O0 *.c; gcc *.o -Wl,-wrap,even -Wl,-wrap,odd -o test_mut_rec".

Mutual recursion without nested function calls in C

My friend Ryukzak has implemented mutual recursion library to use it without nested calls and thus memory overhead (stack). I decided I can do the same using ucontext. Here is a prototype (not generic) to calculate factorial:

struct Fac_state {
    int n;
    int acc;
};

void fac_times2(ucontext_t *other_context, ucontext_t *this_context,
               struct Fac_state *fstate)
{
    while (1) {
        fstate->acc *= fstate->n;
        fstate->n--;
        swapcontext(this_context, other_context);
    }
}


int factorial(int n)
{
    char iterator_stack[SIGSTKSZ];
    struct Fac_state fstate = {n, 1};

    ucontext_t this_context, other_context;

    other_context.uc_stack.ss_sp   = iterator_stack;
    other_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&other_context);

    makecontext(&other_context, (void (*)(void)) fac_times2,
                3, &this_context, &other_context, &fstate);

    while (1) {
        if (fstate.n == 0)
            break;
        swapcontext(&this_context, &other_context);
    }
    return fstate.acc;
}

One more example in my next post.

How to wrap/overwrite/override function in C (gcc and clang)

Today I was tinkering with executing some code right before main() in C. I found a good description in this post. Here is some code similar to the code in that post:

__attribute__((constructor)) void before() {
    printf("Before main\n");
}

int main() {
    printf("Main\n");
    return 0;
}

Another task was to access to the argc and argv outside main(). The reason is that I reimplement some library and can't modify its users. With wrap option available both in gcc and clang I can at first execute my version of main (which can store argc and argv somewhere) and then call real main. Code below can be compiled with "clang sample.c -Wl,-wrap,main" or "gcc sample.c -Wl,-wrap,main":

int __real_main(int argc, char* argv[]);

int __wrap_main(int argc, char* argv[])
{
    printf("Wrapped main\n");
    return __real_main(argc, argv);
}

int main(int argc, char* argv[])
{
    printf("Main\n");
    return 0;
}

A good addition to the "LD_PRELOAD" trick with shared libraries.

CGA programming in C

CGA (Color Graphics Adapter) is an ancient graphical adapter from IBM introduced in 1981. It was IBM's first color graphical card and supported several graphical modes. I will describe programming in 640x200 black/white (monochrome) mode.

Each pixel can be accessed independently (but you still can address just bytes, so each time you can modify 8 pixels).
All lines divided into even and odd. Memory of even lines located at 0xB8000. 80 bytes used for each line, thus you need 8000 bytes for each bank of lines.
Because of performance extra 192 bytes added to each bank (8192 is a power of 2), so odd lines start at 0xBA000.
The code below used to put/clear pixel from the sceen:

#define EVEN_LINES 0xB8000
#define ODD_LINES 0xBA000

unsigned char *mem[] = {(unsigned char*) EVEN_LINES,
                        (unsigned char*) ODD_LINES};

static void drv_put_pixel(int x, int y, unsigned int color)
{
    unsigned char mask = 0x80 >> (x % 8);
    int offset = y/2 * 640/8 + x/8;
    if (color)
        *(mem[y % 2] + offset) |= mask;
    else
        *(mem[y % 2] + offset) &= ~mask;
}

Before you put any pixel you should activate this video mode (BIOS interrupt 10 to set video mode 6):

int video_init()
{
    __asm__("\
                mov $0, %ah;\
                mov $6, %al;\
                int $0x10;\
            ");
}

In this graphical mode pixel aspect ratio of 1:2.4, so if you just plot pixels as you always do with any high level drawing library you might get following picture:

To fix this issue you can use framebuffer to plot pixels in application's memory:

#define FB_LENGTH       (SCREEN_WIDTH*SCREEN_HEIGHT)
#define DRAW_PIXEL(x, y, colour) frame_buffer[(y)*SCREEN_WIDTH + (x)] =\
                                                                    (colour)
color_t frame_buffer[FB_LENGTH];

Then use following code to copy from framebuffer to video memory:

void fb_to_screen() {
    int x, y, Yfb;

    for (y = 0, Yfb = 0; Yfb < SCREEN_HEIGHT; y++, Yfb += 2) {
        for (x = 0; x < SCREEN_WIDTH; x++) {
            color_t pixel1 = frame_buffer[Yfb * SCREEN_WIDTH + x];
            if (Yfb != 0) {
                color_t pixel0 = frame_buffer[(Yfb - 1) * SCREEN_WIDTH + x];
                color_t pixel2 = frame_buffer[(Yfb + 1) * SCREEN_WIDTH + x];
                if (pixel0 == pixel2 && pixel0 != pixel1) {
                        drv_put_pixel(x, y, pixel1);
                } else {
                        /* "Merge" line1 and line2 */
                        drv_put_pixel(x, y, pixel2);
                }
            } else {
                drv_put_pixel(x, y, pixel1);
            }
        }
    }
}

It might be a good idea to optimize routine above, e.g. to sync only modified sections of the screen (or at least just modified lines). Now the picture looks fine (for algorithm you may refer to the code). and also you got some extra drawing space (not shown on the picture) because of scaling:

The problem with CGA programming is that int 10h is forbidden in modern operating systems (like access to the video memory). AFAIK it can be done in MS-DOS only (that nifty real mode applications), thus you need to compile the code into 16-byte dos application and run it under dos, or in windows dos compatible mode or in DOSBox (recommended). Following excellent VGA-programming tutorial is based on DJGPP 2.0 or Borland C, Turbo C. I failed to execute in Windows XP their binary produced by DJPP, but it worked fine in DOSBox with csdpmi5b unpacked to the app directory. In next article I will shortly describe running 32-bit windows applications in DOS. If you write in ASM you can use tasm and probably masm. To learn how to draw primiteves I recommend David Brackeen's "256-Color VGA Programming in C" mentined earlier.

270 days of summers

It became a tradition, that every summer dramatically changes my life.

In 2008 my engineering skills were too low for real development, but I had been accepted into Google Summer of Code and it changed my vision of what development and engineering are. I understood that programming languages are mostly like human one: most important is what you say and not just speaking style. You can know language well, but you can have nothing to say.

At the same time I had very strong family problems: cancer started to kill my lovely granny, who was my best friend and mentor all my life. Now I see, all that pain made me much stronger and I studied a lesson, that every day is important in our life and nobody knows what can happen tomorrow.

Nothing as important as people who love us and whom we love, and it's stupid to waste the time fighting for good reputation and status in "gangs" you don't respect and who never will understand you. The only thing you should do is to build your own word, but not to try to change our big blue sphere whining why most part of people have forgotten what is love, friendship, honor and adherence to the principles. Lieutenant colonel Dmitry Razymovskiy (Vympel, Russian FSB/FSS) sayed: "If a person is not your friend, he is not there for you, if an enemy - he should not exist at all".


To the beginning of summer 2009 I was fully broken: granny just died, I failed to cancel academical vacation and to start next course in university (started the same I had before vocation). The only good thing I had was an offer from Professor Tanenbaum to hack on MINIX 3. It was the thing which helped me to survive after everything that happened. My two projects I've done for MINIX 3 (FPU hardware support and ext2 file server), the team (especially Ben Gras, Thomas Veerman, David van Moolenbroek — the people on whom I want to be like) protected me from the thoughts about past. I enjoyed implementing interesting things (ext2 project was very challenging project for me). It's unforgettable time.


Summer 2010. Just finished ext2, was waiting for a new project from Prof. Tanenbaum.
During summer I met two girls, who gave me good lessons:

1. It's OK if somebody loves you and you don't — it's just a normal situation and the only thing to take care about is not to hurt another one. Good thing is that I was the person who didn't love. This helps when you get into situation which is vice verse: then you don't say "Why???", you just say "Damn!" :-)

2. When you have a real love, the whole courting phase is not the same as seduction of a girl you want, but it's a part of romantic relationships, a very pleasant part which full of spiritual experiences, dreaming, suffering and joys. When you have a true love you become : not only the result is important, but all the "technology" in general. You don't fall into "I want just sex with this pretty girl", wanting her means wanting to know what kind of person she is, what she's doing every day. You need, no, you have to know her plans, thoughts and dreams.

At the same time I was "studying" second lesson, I got an offer from an IT corporation which does data storage. And I had to do a tough choice: freelancing on Prof. Tanenbaum or full day work in a good US company. Regular financial problems and at some point that girl forced me to leave MINIX 3 and start working at the office. I miss MINIX 3 and the team, but I'm happy: not only finances fixed, but everyday I meet interesting people whom I respect for their engineering skills and high technical level. Office is better than mailing lists and IRC. I'm working three weeks already and already hacking (Yai, bash scripting!). The only thing which I'm worried about is feeling, that I can do my job much better than now and to have my day better organized.


What was this all about? Life is an amazing thing and it worth living. We have to do choices very often, but many random events affect our decisions. A big mistake some geeks do is trying to find manual to factorize everything and to get full control: you can't, stop searching that mythical man pages and start living.
Don't learn to live, live to learn! :-) Build your own world with your own community and don't fuck with the rest.

P.S. From summer 2009 I have two unclosed issues: I want AST to sign me a book and to to treat Ben drinking. Well it seems I have to travel to Amsterdam :D