TODO, FIXME, etc in Vim

Add this to .vimrc:

noremap <F6> <ESC>:vimgrep /\C\(TODO\\|FIXME\\|XXX\\|BUG\)/ ./**/*.c<CR>:copen<CR>:cc<CR><CR>

Small and fast build tools: SVMK, NINJA

There are many build tools. One of them tracks dependencies and build result output via special file with dependencies-tree description, another generates such file from universal format (Premake, Bakefile, CMake, etc.). There are 2 big classes of such tools: with special syntax in its' Makefiles, and with supporting of some general-purpose language (Waf, Scoons, etc.). Difference is that in the 2nd kind you can solve absolutely any tasks without writing special plugins (sometimes is impossible to extend "Makefile" in natural way, only with command line utilities)...

If you want very small and fast build tools (and not Make:) you can see next: Ninja and Tcl-based Svmk. Another Tcl-based make tools are here.

Ninja

Ninja is very simple and fast. It have not functions, if-else-for-while operators, nothing, only variables, rules... But it can be used to process automatically generated "Makefile". Example:

DMD = c:/dmd2/windows/bin/dmd.exe
LINK = c:/dmd2/windows/bin/link.exe

INC = -Ic:/dmd2/src/phobos -Ic:/dmd2/src/druntime/import

rule mkprj
    command = $DMD -I$PKGDIR $INC -of$out $in
    description = Compile D program $out

PKGDIR = misc/scripts
build $PKGDIR/email.exe: mkprj $PKGDIR/characterencodings.d $PKGDIR/email.d

Save it in build.ninja, call ninja misc/scripts/email.exe and you will get result: email.exe in misc/scripts directory. rule creates rule which has attribute command to call when it's applied. build set dependency: email.exe will be built from 2 .d files with mkprj rule by calling it command. Nothing else. Simple, fast. ninja is only ONE FILE: ninja.exe and is about 800Kb! If no target (misc/scripts/email.exe), then ninja will build it.

Svmk

It's Tcl-based make alternatives. So you have all power of Tcl (use Tclkit Shell!) in one little Tcl-script: svmk.tcl. Example of the same:

# vi:set ft=tcl:

set DHOME c:/dmd2/windows/bin
set DMD $DHOME/dmd.exe

proc dcomp {out in {dflags ""}} {
    global DMD
    if [llength $dflags] {
        system $DMD $dflags -of$out {*}$in
    } else {
        system $DMD -of$out {*}$in
    }
}

target email.exe {
    cd misc/scripts
    set SRC "characterencodings.d email.d"
    depend $SRC {
        dcomp email.exe $SRC
    }
}

We create dcomp procedure for compiling of D applications. Then create rule "email.exe" which is PHONY :) Common usage is target TARGET { depend DEPENDENCIES { commands... } }. You can see: we can use any Tcl commands, even download something via Net :) All what you need is: tclkitsh.exe: 740Kb, svmk.tcl: 10Kb!
To run:

tclkitsh.exe svmk.tcl email.exe

And sure you can (and have) to use original D build tool (if we are talking about D;) - dub.

Installation and trying D

First, download ZIP-archive with D compiler. Then unpack it into... for example c:/dmd2. You need directories: html and man (documentation), samples, src (for including), windows (binary, libraries) and README.TXT. Create somewhere test file, for example a.d:

import std.stdio;

int main(string[] args) {
    int[string] d;

    d["qwe"] = 12;
    d["asd"] = 13;
    d["zxc"] = 14;
    writef("%d\n", d["asd"]);

    int i = 10;
    typeof(i) j = 90;
    writef("%d", j);
    return 0;
}

Then create dmd.conf file (or sc.ini) with next content:

[Environment]
LIB="c:\dmd2\windows\lib"

DFLAGS="-Ic:\dmd2\src\phobos" "-Ic:\dmd2\src\druntime\import"
LINKCMD="c:\dmd2\windows\bin\link"
DDOCFILE=mysettings.ddoc

Now create Makefile:

DBIN=c:/dmd2/windows/bin
LINK=$(DBIN)/link
DMD=$(DBIN)/dmd
RM=rm -rf

DFLAGS=
LFLAGS=

SRC=a.d
OBJS=$(SRC:.d=.o)
EXES=$(SRC:.d=.exe)

.SUFFIXES: .d
.d.o:
 $(DMD) $(DFLAGS) -c $< -of$@


clean:
 $(RM) $(OBJS) $(EXES)

######################################################################
a: a.o
 $(LINK) $(LFLAGS) $<

Now you can compile first D program:

make a

and run it:

a.exe
13
90

Multiplication of big numbers represented as strings

This is the usual task in interview: solve multiplication of integer numbers presented as strings, for ex., "25" * "25" = "625". Length of these strings may be any (not 16 bits or 32 bits only).
Implementation will use school way of multiplication of numbers (sign is ignored), see:

   1856
   1856
   ----
  11136
  9280
14848
1856
=======
3444736

So, "1856" * "1856" = "3444736", we multiply each digit of second number on each digit of first one, shift result number by one to left, summarize them and don't forget about carry. Carry is of 2 kinds: carry of multiplication and carry of sum. Algorithm is:

• multiply last digit of 2nd number by last digit of 1st one
• write result (only low digit) in result string at LAST POSITION
• if resulting number is > 10, save carry (divided by 10)
• make the same with the 2nd digit of 2nd number, but instead of saving resulting digit, make summation: with carry of multiplication AND carry of sum
• don't forget to make shifting to left when go to next digit of 1nd number

So, each "saving" of result digit should make summation and there are not number 9280 in middle result but sum of 11136 and 9280 ("103936"). Implementation on C looks like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "algutils.h"

#define ASCII2I(CH) ((CH)?((CH)-'0'):0)
#define I2ASCII(I) ((I)+'0')

char* mul(const char *s1, const char *s2, char *res, int reslen)
{
    int r, // index in result string
        i, // index in s1
        _i, // offset (to left) of next middle number
        j, // index in s2
        len1 = strlen(s1), len2 = strlen(s2);
    int d1, // digit in s1
        d2, // digit in s2
        ts, // temporary summ
        c, // curry in multiplication
        cs; // curry in summation
    memset(res, 0, reslen);
    for (i=len2-1, _i=0, cs=0; i>=0; i--, _i++) {
        d2 = ASCII2I(s2[i]);
        r = reslen - 2 - _i;
        for (j=len1-1, c=0; j>=0; j--) {
            d1 = ASCII2I(s1[j]);
            d1 = d1*d2 + c;
            ts = ASCII2I(res[r]) + (d1%10) + cs;
            res[r] = I2ASCII(ts%10);
            cs = ts/10;
            c = d1/10;
            r--;
        }
        do {
            // do rest of sum (high digits)
            ts = ASCII2I(res[r]) + (c%10) + cs;
            if (!ts) break;
            res[r] = I2ASCII(ts%10);
            cs = ts/10;
            r--;
        } while (cs);
    }
    return (res + r + 1);
}

///////////////////////////////////////////////
//              Main: tests
///////////////////////////////////////////////

#define RND(N) (srand(time(NULL)), rand()%(N))

int main(void)
{
    char _res[32], *res;
    char s1[32] = {0};
    char s2[32] = {0};
    int n1, n2, rn, resn, chk;

    //printf("%s\n", mul("1856", "1856", _res, sizeofarray(_res)));
    //return 0;

    for (int i=0; i<100; i++) {
        sprintf(s1, "%d", RND(9999999));
        sprintf(s2, "%d", 1+RND(9999999));
        printf("STR: %s * %s = %s\n", s1, s2, (res=mul(s1, s2, _res, sizeofarray(_res))));
        n1 = atoi(s1); n2 = atoi(s2); rn = n1*n2; resn = atoi(res);
        printf("CTR: %d * %d = %d\n", n1, n2, rn);
        printf("verify <%d>: %d (%d ? %d)\n", i, (chk=(resn==rn)), rn, resn);
        if (!chk) { printf("FAILED!\n"); return (1); }
        else printf("\n\n");
    }
    printf("All tests are passed\n");
    return (0);
}

Tests are cycle of multiplication of random numbers. If test is failed, cycle is break.

In-place non-recursive Merge Sort

Merge sorting is a good known algorithm, but usually is used recursive implementation with additional array. This is an another version: without recursive and without usage of additional array.
Merge sorting idea is to sort small parts (pairs) than longer (4 items) and etc, but each next sort phase is MERGE of previous sorted parts. Merging of 2 sorted parts should saves order of items:

1,5 merging 2,3 is 1,2,3,5.

If we avoid recursive implementation then we should generate indexes of all parts (2 items, 4 items...). This sub-task will be done in mergesort() function. Another sub-task is to merge 2 sorted parts into new one, but sorted too. This is implemented in _merge() function, which avoid additional array of result by using of swapping of items: we has 2 arrays with 2 indexes and compare both items (from one array and another, indexed by these 2 indexes). If they need reordering then we swap items. Index of lesser item is incremented (see code below).
Main problem is to calculate middle index (for splitting input array into 2 parts for merging). Next formula is used:

mid = lev*2 + pielen*pie;

if (pielen > len || mid > len-1) mid = lastleft;

where lev is the level of pseudo-recursion, pielen is the length of pie (part) = {2, 4, 8...}. len is the length of input array, lastleft is the index of left bound of previous "level". So, we should to get something like this:
lev=0 left=0   mid=0   right=2
lev=0 left=2   mid=2   right=4
lev=0 left=4   mid=4   right=6
lev=0 left=6   mid=6   right=8
lev=0 left=8   mid=8   right=10
lev=0 left=10 mid=10 right=12
lev=1 left=0   mid=2   right=4
lev=1 left=4   mid=6   right=8
lev=1 left=8   mid=10 right=12
lev=2 left=0   mid=4   right=8
lev=2 left=8   mid=8   right=12
lev=3 left=0   mid=8   right=12
So, this is the code:

#include <stdio.h>
#include "algutils.h"

template<typename>
static inline void _merge(T *arr, int left, int mid, int right)
{
    T tmp, // tmp item needed for inserting if head position on shift
      *larr, // left subarray
      *rarr; // right subarray
    int llen, // length of left subarray
        rlen; // length of right subarray
    int l, r; // indexes of compared items in left, right subarrays

    l = r = 0;
    larr = &arr[left];
    if (mid==left) {
        // When len==2 swapping is more preferable
        rarr = &arr[mid+1];
        llen = mid - left + 1;
        rlen = right - mid - 1;
    } else {
        // Common case
        rarr = &arr[mid];
        llen = mid - left;
        rlen = right - mid;
    }
    // Index in left subarray is limited by "right" index
    while ((larr+l < rarr+r) && r < rlen) {
        if (larr[l] > rarr[r]) {
            tmp = rarr[r];
            RSHIFT_ARR(larr+l, llen-(l-r), 1);
            larr[l] = tmp;
            r++;
        }
        l++;
    }
}

template<typename>
int mergsort(T* arr, int len)
{
    int lev, // level of "recursion"
        pie, // number of subarray (of part)
        pielen, // subarray length: 2, 4, 8...
        left, right, // bounds (right is not included)
        mid, // middle point for splitting - is the same as left bound of subarray but on prev. level
        lastleft; // last left index

    if (!arr||!len) return (0);

    lev = 0;
    pielen = 2;
    while (pielen < 2*len) {
        pie = 0;
        do {
            left = pie*pielen;
            right = left + pielen;
            if (right > len) right = len;
            mid = lev*2 + pielen*pie;
            if (pielen > len || mid > len-1) mid = lastleft; //mid = len-2;
            _merge(arr, left, mid, right);
            pie++;
        } while (right < len-1);
        pielen *= 2;
        lev++;
        lastleft = left;
    }
    return (1);
}


/*****************************************
                   main
 ****************************************/
int main(void)
{
    int arr1[] = {10, 19, 1, 2, 10, 450, 6, 7, 8, 100, 120, 121};
    mergsort(arr1, sizeofarray(arr1));
    PRINTARR(arr1, "%d");
    return (0);
}

Macros RSHIFT_ARR() is trivial:

/// Shift array @a ARR of length @a LEN by @a N positions to right
#define RSHIFT_ARR(ARR, LEN, N) do { \
    register int _rshift_arr_i_; \
    for (_rshift_arr_i_=(N)+(LEN)-1; \
         _rshift_arr_i_>(N)-1; \
         _rshift_arr_i_--) \
    { \
        *((ARR)+_rshift_arr_i_) = *((ARR)+(_rshift_arr_i_-(N))); \
    } \
} while (0)

IMSH: Convert to black and white. SIOD interfacing

See more http://chiselapp.com/user/p4v31/repository/imsh/home

This is the example of "converting to black and white" algorithm (dummy implementation). It uses threahold value of RGB-vector length to "decide" what color to use: white or black:

int algo_bw(IMG *img, int threshold)
{
    RGBQUAD rgb;
    unsigned int row, col, width, height;
    double rgbl, maxrgbl;

    width = FreeImage_GetWidth(img);
    height = FreeImage_GetHeight(img);

    assert(img && width && height);

    maxrgbl = sqrt(255.*255. + 255.*255. + 255.*255.);

    for (row = 0; row < height; row++) {
        for (col = 0; col < width; col++) {
            FreeImage_GetPixelColor(img, col, row, &rgb);
            rgbl = RGBLEN(&rgb);
            if (rgbl*100/maxrgbl > threshold) {
                // light
                FreeImage_SetPixelColor(img, col, row, (RGBQUAD*)&RGB_WHITE);
            } else {
                // dark
                FreeImage_SetPixelColor(img, col, row, (RGBQUAD*)&RGB_BLACK);
            }
        }
    }
    return (0);
}

It uses FreeImage library. Idea is simple: detect length of RGB vector then compares it with some threshold value and set output pixel to white (if length of vector is less then threshold) or to black value. Here is example how to use SIOD. First, we create some wrapper:

LISP img_bw(LISP img, LISP threshold)
{
    IMG *_img = NULL;
    long _threshold;

    _img = LISP2IMG(img);
    _threshold = get_c_long(threshold);
    if (!algo_bw(_img, (int)_threshold))
        return (a_true_value());
    else return (NIL);
}

LISP2IMG is converter of LISP object into IMG C structure:

static IMG* LISP2IMG(LISP ptr)
{
    if (NTYPEP(ptr, tc_img)) err("not a IMG", ptr);
    if (!ptr->storage_as.string.data) err("IMG deallocated", ptr);
    else return ((IMG*)ptr->storage_as.string.data);
}

IMG is typedef of FIBITMAP (FreeImage type for images). Then we should register it as SIOD function:

init_subr_2("img_bw", img_bw);

but only after initialization of SIOD library:

long _kind;
tc_img = allocate_user_tc();
set_gc_hooks(tc_img, NULL, NULL, NULL, _img_gc_free, &_kind);
set_print_hooks(tc_img, _img_print);
init_storage();
init_subrs();
init_trace();

And then we can use it in SIOD-Scheme script:

(define b (img_open "pic1.jpg"))
(img_bw b)
(img_save b "out/bw.jpg")

Saving and loading of images are implemented as:

LISP img_open(LISP fname)
{
    IMG *img = NULL;
    LISP res;
    long intflag;
    char *_fname;
    FREE_IMAGE_FORMAT fif;

    _fname = get_c_string(fname);

    intflag = no_interrupt(1);
    fif = FreeImage_GetFileType(_fname, 0);
    if (fif == FIF_UNKNOWN) {
        fif = FreeImage_GetFIFFromFilename(_fname);
        if (fif == FIF_UNKNOWN) {
            // fif can not be determined
            res = err(__func__, llast_c_errmsg(-1));
            goto end;
        }
    }
    img = FreeImage_Load(fif, _fname, 0);
    if (!img) {
        res = err(__func__, llast_c_errmsg(-1));
    } else {
        res = cons(NIL, NIL);
        res->type = tc_img;
        res->storage_as.string.data = (char*)img;
    }
end:
    no_interrupt(intflag);
    return (res);
}

/** Save IMG to file
*/
LISP img_save(LISP img, LISP fname)
{
    IMG *_img = NULL;
    LISP res;
    long intflag;
    char *_fname;
    FREE_IMAGE_FORMAT fif;

    _img = LISP2IMG(img);
    _fname = get_c_string(fname);

    intflag = no_interrupt(1);
    fif = FreeImage_GetFIFFromFilename(_fname);
    if (fif == FIF_UNKNOWN) {
        res = err(__func__, llast_c_errmsg(-1));
        goto end;
    }
    if (!FreeImage_Save(fif, _img, _fname, 0)) {
        res = err(__func__, llast_c_errmsg(-1));
        goto end;
    } else {
        res = a_true_value();
    }
end:
    no_interrupt(intflag);
    return (res);
}

How to return value from C macro

Usually I use variable name in C macro as out parameter (it's standard way in Tcl, for example). But there is another way, something like in functional languages, with expression. See:

#define GETX(X) ({ \
        int x = (X)*2; \
        x; \
        })

void main()
{
    printf("%d\n", GETX(56));
}

This example shows hot to return value from GETX(), which really is expression. Works in GCC :)

Debug messages support for C, ver 2

This C module support debug/logging system with custom levels of messages. Suppressing of some level/levels are possible via DBG_LEVEL macro variable. Each custom level is created with DBG_LEVEL_ALIAS() macro. USer can define own print/dump implementations via DBG_PRN_IMPL/DBG_DUMP_IMPL.

#ifndef __DBG_H
#define __DBG_H

#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>

#define DBG_LEVEL_ALIAS(L) (1<<(L))

#ifndef DBG_LEVEL
#define DBG_LEVEL 0
#endif

#ifndef DBG_LEVEL_FMT
#define DBG_LEVEL_FMT "%s: "
#endif

#define _DBG_PRN_IMPL_L(L, F, ...) printf(F, L, __VA_ARGS__)
#define _DBG_PRN_IMPL(F, ...) printf(F, __VA_ARGS__)
#define _DBG_DUMP_IMPL_L(L, p, sz) do { \
    int i; \
    for (i=0; i<(sz); i++) { \
        if (0 == i%16) { \
            DBG_PRN_IMPL("", "%s%s%08" PRIXPTR ": %02X "/*"%s%s%08lX: %02X "*/, i?"\n":"", \
                    16*i/16 + (uintptr_t)p, (uint8_t)(p)[i]); \
        } else if (0 == (i-7)%16) { \
            DBG_PRN_IMPL("", "%s%02X|", (uint8_t)(p)[i]); \
        } else { \
            DBG_PRN_IMPL("", "%s%02X ", (uint8_t)(p)[i]); \
        } \
    } \
    DBG_PRN_IMPL("", "%s%s", "\n"); \
} while (0)
#define _DBG_DUMP_IMPL(p, sz) do { \
    int i; \
    for (i=0; i<(sz); i++) { \
        if (0 == i%16) { \
            DBG_PRN_IMPL("%s%08" PRIXPTR ": %02X "/*"%s%08lX: %02X "*/, i?"\n":"", \
                    16*i/16 + (uintptr_t)p, (uint8_t)(p)[i]); \
        } else if (0 == (i-7)%16) { \
            DBG_PRN_IMPL("%02X|", (uint8_t)(p)[i]); \
        } else { \
            DBG_PRN_IMPL("%02X ", (uint8_t)(p)[i]); \
        } \
    } \
    DBG_PRN_IMPL("%s", "\n"); \
} while (0)

#ifdef DBG_LEVEL_IS_ARG

#ifndef DBG_PRN_IMPL
#define DBG_PRN_IMPL _DBG_PRN_IMPL_L
#endif
#ifndef DBG_DUMP_IMPL
#define DBG_DUMP_IMPL _DBG_DUMP_IMPL_L
#endif

#define DBG_PRN(L, F, ...) if ((DBG_LEVEL) & (L)) DBG_PRN_IMPL(#L, DBG_LEVEL_FMT F, __VA_ARGS__)
#define DBG_DUMP(L, ...) if ((DBG_LEVEL) & (L)) DBG_DUMP_IMPL(#L, __VA_ARGS__)

#else

#ifndef DBG_PRN_IMPL
#define DBG_PRN_IMPL _DBG_PRN_IMPL
#endif
#ifndef DBG_DUMP_IMPL
#define DBG_DUMP_IMPL _DBG_DUMP_IMPL
#endif

#define DBG_PRN(L, ...) if ((DBG_LEVEL) & (L)) DBG_PRN_IMPL(__VA_ARGS__)
#define DBG_DUMP(L, ...) if ((DBG_LEVEL) & (L)) DBG_DUMP_IMPL(__VA_ARGS__)

#endif

/// Print without level
#define DBG_PRN_UL(L, F, ...) if ((DBG_LEVEL) & (L)) DBG_PRN_IMPL("", "%s" F, __VA_ARGS__)

#endif /* EOF */

Usage:

#include <string.h>

// use level name as 1st argument of out DBG_PRN_IMPL
#define DBG_LEVEL_IS_ARG
#define DBG_LEVEL_FMT "[%s] "
#include "dbg.h"

// define levels
#define HARDWARE_LEVEL   DBG_LEVEL_ALIAS(1)
#define WRAPPER_LEVEL   DBG_LEVEL_ALIAS(2)
#define APP_LEVEL       DBG_LEVEL_ALIAS(3)

#undef DBG_LEVEL
#define DBG_LEVEL (HARDWARE_LEVEL|APP_LEVEL)

void main() {
    char dim[] = "0123456789Hello World!";
    DBG_PRN(HARDWARE_LEVEL, "There %d\n", 1);
    DBG_PRN(WRAPPER_LEVEL, "There %d\n", 2);
    DBG_PRN(APP_LEVEL, "There %d\n", 3);
    DBG_DUMP(APP_LEVEL, dim, strlen(dim));
    DBG_PRN_UL(APP_LEVEL, "%s\n", "Done.");
}

Output:

[HARDWARE_LEVEL] There 1
[APP_LEVEL] There 3
0022FEF5: 30 31 32 33 34 35 36 37 38|39 48 65 6C 6C 6F 20
0022FF05: 57 6F 72 6C 64 21
Done.

Dithering algorithm implemented for IMSH

Today I implemented Dithering algorithms for IMSH (IMage SHell) - see Project WiKi - Dithering. They are: general purpose (see matrixes in imsh.scm library) and special purpose: Atkinson, Floyd-Steinberg, Ordered, Random, General Sierra, General Sierra Two Rows, General Sierra Low, General Floyd-Steinberg, General False Floyd-Steinberg, General Jarvis, General Stucki, General Atkinson, General Burkes.