Notes on computers, programming and all the stuff

itoa on steroids

2011-10-27T21:23:00.000+02:00

Function itoa implemented with SSE instructions is about 3 times faster then scalar CPU version. Read more.

Embedded in Academia

2011-04-16T22:33:00.000+02:00

New link in blogroll -- blog of prof. John Regehr: low level code, bugs in C compilers and beautiful photos.

Regular expressions derivatives

2011-04-13T19:09:00.002+02:00

Have you ever heard about "regular expression derivatives"? No? Me too. This is very interseting idea, that have pratical usage in pattern matching.

Matthew Might wrote a sample program using the idea: A regular expression matcher in Scheme using derivatives. There is also a detailed paper on this topic: Regular-expression derivatives re-examined by Owens, Reppy and Turon.

Traversing DAGs

2011-04-13T19:08:00.000+02:00

If DAG has got one component, then the simplest traversing
method is depth-first-search, which could be easily implemented
recursively (using implicit stack).

struct DAGNode {
        // user data
        bool    visited;        // after construction = 0
}

void DFS_aux(DAGNode* node, const bool val) {
        if (node->visited != val) {
                // visit node

                node->visited = val;
                for (n in node.connected)
                        DFS_aux(n, val)
        }
}

void DFS(DAGNode node) {
        static val = true;
        DFS_aux(node, val);
        val = not val;
}

On every call of DFS() variable val is switched, and visited member is marked alternately with true or false.

There is just one problem — what if traversing method stop execution before visiting all nodes? Of course in such situation we have to visit DAG twice: on first pass reset (possibly many times) visited member to false, and then visit once each node.

But usually bool have at least 8 bits, so numbers could be used instead of boolean values 0 or 1. On each call of DFS() a reference number is incremented, thanks that even if previous call stopped in the middle procedure will work
correctly.

The only moment when visited markers have to be cleared is wrapping a reference numbers to zero. This happen every 256 calls if 8-bit values used; for wider counters (16, 32 bits)
max value is greater.

void DFS(DAGNode node) {
        static unsigned int val = 1;
        if (val == 0) {
                // set visited member of all nodes to 0
                val += 1;
        }
        DFS_aux(node, val);
        val += 1;
}

DAWG as dictionary? Yes!

2011-04-09T22:04:00.002+02:00

If you read Wikipedia entry about DAWG, then you find following sentence:

Because the terminal nodes of a DAWG can be reached by multiple paths, a DAWG is not suitable for storing auxiliary information relating to each path, e.g. a word's frequency in the English language. A trie would be more useful in such a case.

This isn't true!

There is a quite simple algorithm, that allow to perform two-way minimal perfect hashing (MPH), i.e. convert any path representing a word to a unique number, or back --- a number to a path (word). Values lie in range 1..n, where n is number of distinct words saved in DAWG.

The algorithm is described in Applications of Finite Automata Representing Large Vocabularies, by Claudio Lucchiesi and Tomasz Kowaltowski (preprint is freely available somewhere online).

The main part of the algorithm is assigning to each node a number of reachable words from a node; this can be easily done in one pass. Then these numbers are used to perform perfect hashing. Hashing algorithm is fast and simple, translation from pseudocode presented in the paper is straightforward.

Algorithm requires additional memory for numbers in each node and a table of size n to implement dictionary lookups.

I've updated pyDAWG to support MPH.

pyDAWG

2011-04-09T15:10:00.003+02:00

pyDAWG is a python module implementing Directed Acyclic Word Graph, that allow to store set of words in a compacted way. DAWGs are much smaller then tries, while sharing the main advantage of tries - linear time to check if word is present in a set.

The main module is a C extension, there is also a pure python code.

Python: C extensions - sequence-like object

2011-04-08T22:46:00.001+02:00

If class have to support standard len() function or operator in, then must be a sequence-like. This require variable of type PySequenceMethods, that store addresses of proper functions. Finally address of this structure have to be assigned to tp_as_sequence member of main PyTypeObject variable.

Here is sample code:

static PySequenceMethods class_seq;

static PyTypeObject class_type_dsc = {
 ...
};

ssize_t
classmeth_len(PyObject* self) {
 if (not error)
  return sequence_size;
 else
  return -1;
}

int
classmeth_contains(PyObject* self, PyObject* value) {
 if (not error) {
  if (value in self)
   return 1;
  else
   return 0;
 }
 else
  return -1;
}


PyMODINIT_FUNC
PyInit_module() {
 class_seq.sq_length   = classmeth_len;
 class_seq.sq_contains = classmeth_contains;

 class_type_dsc.tp_as_sequence = &class_seq;

 ...
}

pyahocorasick

2011-03-29T23:06:00.000+02:00

Python module implementing Aho-Corasick algorithm has been released. C extension (for Py3k) and pure python code are available.

Internal memory fragmentation

2011-03-28T21:58:00.000+02:00

In previous post I've advertised my text about trie representations.

Depending on particular representation internal memory fragmentation vary from 25% to 46% (in GNU libc). In other words if trie should occupy 100MB then in the worst case real memory usage is around 200MB. I've never suppose that fragmentation could be so significant.

When quite simple memory pools were used, then internal fragmentation has been cut down to 1-2%! Impressive.

Efficient trie representation

2011-03-26T17:39:00.000+01:00

While implementing Aho-Corasick algorithm I've checked several trie representations.

Python3: import antigravity

2011-02-27T16:08:00.000+01:00

Works fine!

Grafika komputerowa I

2011-02-23T21:17:00.000+01:00

Całkiem udany skrypt do grafiki komputerowej autorstwa Przemysława Kiciaka udostępnił UW w ramach swojego portalu z materiałami dydaktycznymi. Obszerna tematyka, więc miejscami skrótowo i ogólnikowo, ale ogólnie wygląda zachęcająco.

PIC Language

2010-10-10T21:28:00.001+02:00

Yesterday I made my first diagram with PIC (see Wikipedia) and... I felt in love. Language is just perfect, intuitive and powerful. Try it and you will never use any popular drawing software.

Xorg VESA driver - higher resolutions

2010-09-28T23:44:00.000+02:00

Default configuration of VESA driver allows resolutions 640x480 and 800x600.
It is quite simple to get higher resolutions - in section Monitor of /etc/X11/xorg.conf we have to set horizontal and vertical refresh rates. By default these values are set to lowest, safe area.

Here are my settings:

Section "Monitor"
        Identifier   "Monitor0"
        VendorName   "Monitor Vendor"
        ModelName    "Monitor Model"

        HorizSync    42.0 - 80.0
        VertRefresh  55.0 - 100.0 
EndSection

X.org is able to work at 1280x1024 with vertical refresh rate 75Hz. HTH

PostgrSQL: printf in PL/pgSQL

2010-08-24T09:38:00.001+02:00

PostgreSQL wiki has entry about sprintf - is is quite simple approach (and isn't marked as immutable), the main drawback is iterating over all chars of format string. Here is a version use strpos to locate % in format string, and it's faster around 2 times:

CREATE OR REPLACE FUNCTION printf2(fmt text, variadic args anyarray) RETURNS text
LANGUAGE plpgsql IMMUTABLE AS $$
   DECLARE
      argcnt  int  := 1;
      head    text := '';     -- result
      tail    text := fmt;    -- unprocessed part
      k       int;
   BEGIN
      LOOP
         k := strpos(tail, '%');
         IF k = 0 THEN
            -- no more '%'
            head := head || tail;
            EXIT;
         ELSE
            IF substring(tail, k+1, 1) = '%' THEN
               -- escape sequence '%%'
               head := head || substring(tail, 1, k);
               tail := substring(tail, k+2);
            ELSE
               -- insert argument
               head := head || substring(tail, 1, k-1) || COALESCE(args[argcnt]::text, '');
               tail := substring(tail, k+1);
               argcnt := argcnt + 1;
            END IF;
         END IF;
      END LOOP;
   RETURN head;
END;
$$;

SSSE3 population count vs hardware

2010-07-17T11:43:00.002+02:00

Peter Kankowski compared speed of SSE4.2 instructions crc32 and popcnt against software implementations. Hardware CRC32 is significantly faster, but population count is slightly slower than my SSSE3 popcount!

Branchless set mask if value greater or how to print hex values

2010-05-09T23:01:00.002+02:00

Suppose we need to get mask when nonnegative argument is greater then some constant value; in other words, we want to evaluate following expression:

if x > const_n then
   mask := 0xffffffff;
else
   mask := 0x00000000;

Portable branchless solution:

choose magic number M := (1 << (k-1)) - 1 - n, where k is a bit position, for example 31 if we operate on 32-bit words
calculate R := x + M
k-th bit of R is set if x > n
fill mask with this bit - see note Fill word with selected bit

The key to understand this trick is binary form of M: 0111..1111zzzz, where z is 0 or 1 depending on n value. When x is greater then n, then x + M has form 1000..000zzzz, because carry bit propagate through series of ones to k-th position of result.

Real world example - branchless converting hex digit to ASCII (M=0x7ffffff6 for k=31 and n=9).

; input:    eax - hex digit
; output:   eax - ASCII letter (0-9, A-F or a-f)
; destroys: ebx

        andl 0xf, %eax
        leal 0x7ffffff6(%eax), %ebx     ; MSB(ebx)=1 when eax >= 10
        sarl $31, %ebx                  ; ebx - mask
        andl  $7, %ebx                  ; ebx = 7 when eax >= 10 (for A-F letters)
        ;andl $39, %ebx                 ; ebx = 39 when eax >= 10 (for a-f letters)
        leal '0'(%eax, %ebx), %eax      ; eax = '0' + eax + ebx => ASCII letter

It is also possible to convert 4 hex digits in parallel using similar algorithm, but input data have to be correctly prepared. Moreover generating mask requires 3 instructon and one extra register (in scalar version just one arithmetic shift). I guess it wont be fast on x86, maybe this approach would be good for SIMD code, where similar code transforms more bytes at once.

; input: eax - four hex digits in form [0a0b0c0d]
; output: eax - four ascii letters
; destroys: ebx, ecx

        leal 0x76767676(%eax), %ebx        ; MSB of each byte is set when corresponding eax byte is >= 10
                                           ; (here: 0x7f - 9 = 0x76)
        andl $0x80808080, %ebx
        movl %ebx, %ecx
        shrl    $7, %ebx
        subl %ebx, %ecx                    ; ecx - byte-wise mask
        ;andl $0x07070707, %ecx            ; for ASCII letters A-F
        andl $0x27272727, %ecx             ; for ASCII letters a-f
        leal 0x30303030(%eax, %ecx), %eax  ; ecx - four ascii letters

See also: SSSE3: printing hex values (weird use of PSHUFB instruction)

Speedup reversing table of bytes

2010-05-01T23:06:00.003+02:00

With help of BSWAP instruction or SSE instructions (PSHUFD, PSHUFLW, PSHUFHW) or SSSE3 instruction (PSHUFB) reversing table can be faster. Speedup depends on three factors:

table size: larger=faster
table address: aligned=faster/much faster (15.5 speedup - possible! see chart)
CPU type

Read full article

Determining if an integer is a power of 2

2010-04-11T18:38:00.004+02:00

Method from Bit Twiddling Hacks: (x != 0) && (x & (x-1) == 0). GCC compiles this to following code:

; input/ouput: eax
; destroys: ebx

        test    %eax,  %eax     ; x == 0?
        jz      1f

        leal -1(%eax), %ebx     ; ebx := x-1
        test    %eax,  %ebx     ; ZF  := (eax & ebx == 0)

        setz     %al
        movzx    %al, %eax       ; eax := ZF
1:

We can use also BSF and BSR instructions, that determines position of first and last bit=1. If number is power of 2, then just one bit is set, and thus these positions are equal. BSx sets also ZF flag if input value is zero.

; input/output: eax
; destroys: ebx, edx

        bsf     %eax, %ebx      ; ebx := LSB's position if eax != 0, ZF = 1 if eax = 0
        jz      1f
        bsr     %eax, %edx      ; edx := MSB's position

        cmp     %ebx, %edx      ; ZF  := (ebx = edx)

        setz    %al
        movzx   %al, %eax       ; eax := ZF
1:

Brenchless conditional exchange

2010-04-08T21:56:00.001+02:00

Suppose we have to exchange (or just move) two registers A and B:

C := A xor B
C := 0 if condition is not true
A := A xor C
B := B xor C

If C is 0, then A and B left unchanged, else A and B are swapped. If only conditional move from B to A is needed, then step 4th have to be skipped.

Here is a sample x86 code, where condition is value of CF:

sbb edx, edx ; part of step 2. - edx = 0xffffff if CF=1, 0x000000 otherwise
mov ecx, eax
xor ecx, ebx ; step 1
and ecx, edx ; completed step 2. - now C is 0 or (A xor B)
xor eax, ecx ; step 3
xor ebx, ecx ; step 4

Branchless moves are possible in Pentium Pro and higher with instructions cmovcc.

See also XOR linked list.

STL: map with string as key - access speedup

2010-04-03T16:37:00.001+02:00

The idea is quite simple: we do not have a single stl::map<string, something>, but vector of maps, indexed with O(1) time - each map store keys sharing certain properties. Drawback: additional memory.

I've tested following grouping schemes:

length of string,
first letter of string (one level trie),
both length and first letter.

Third is the fastest - around 60% faster then plain std::map from gcc (red-black tree).

Tests: my program read plain text (I've used The Illiad from http://gutenberg.org), text is splitted into words (~190000) and then each words is inserted into dictonary (~28000 distinct words); then the same words are searched in dictionaries. Table below summarizes results on my computer (gcc 4.3.4 from cygwin).

+-------------+--------------------------------+--------------------------------+
|             |          running time [ms]     |            speedup [%]         |
| data struct +----------+----------+----------+----------+----------+----------+
|             |    min   |   avg    |   max    |   min    |   avg    |   max    |
+-------------+----------+----------+----------+----------+----------+----------+
|                                          inserting                            |
+-------------+----------+----------+----------+----------+----------+----------+
|  std::map   |    269   |   287    |   355    |   100    |   100    |   100    |
+-------------+----------+----------+----------+----------+----------+----------+
| first char  |    218   |   241    |   395    |    81    |    84    |   111    |
+-------------+----------+----------+----------+----------+----------+----------+
|   length    |    218   |   240    |   345    |    81    |    84    |    97    |
+-------------+----------+----------+----------+----------+----------+----------+
| len./char   |    165   |   172    |   207    |    61    |    60    |    58    |
+-------------+----------+----------+----------+----------+----------+----------+
|                                            finding                            |
+-------------+----------+----------+----------+----------+----------+----------+
|  std::map   |    295   |   322    |   483    |   100    |   100    |   100    |
+-------------+----------+----------+----------+----------+----------+----------+
| first char  |    243   |   263    |   460    |    82    |    82    |    95    |
+-------------+----------+----------+----------+----------+----------+----------+
|   length    |    238   |   248    |   292    |    80    |    77    |    60    |
+-------------+----------+----------+----------+----------+----------+----------+
| len./char   |    184   |   190    |   241    |    62    |    60    |    50    |
+-------------+----------+----------+----------+----------+----------+----------+

Download test program.

Branchless signum

2010-04-01T20:21:00.006+02:00

Problem: calculate value of sign(x):

-1 when x < 0
0 when x = 0,
+1 when x > 0.

My solution do not involve any hardaware specific things like ALU flags nor special instructions - just plain AND, OR, shifts.

 ; input: eax = X

 movl %eax, %ebx
 sarl $31, %eax  // eax = -1 if X less then zero, 0 otherwise

 andl $0x7fffffff, %ebx
 addl $0x7fffffff, %ebx // MSB is set if any lower bits were set
 shrl $31, $ebx  // eax = +1 if X greater then zero, 0 otherwise

 orl %ebx, %eax  // eax = result

C99 implementation:

int32_t sign(int32_t x) {
 int32_t y;
 y = (x & 0x7fffffff) + 0x7fffffff;
 return (x >> 31) | ((uint32_t)y >> 31);
}

Fill word with selected bit

2010-04-01T19:05:00.008+02:00

This is continuation of subproblem from previous post: we have a word (byte, dword, whatever) and want to fill it with selected bit.

1. The most general algorithm:

mask bit
[10111010] => [00010000]
clone word
a=[00010000], b=[00010000]
shift bit in first word to MSB, and to LSB in second word
a=[10000000], b=[00000001]
subtract c = a - b
c=[01111111]
add missing MSB c = c OR a
c=[11111111]

2. If arithmetic shifts are supported:

shift bit to MSB
a=[10000000]
arithmetic shift right
a=[11111111]

3. On processor 386+ we can copy selected bit from reg to carry flag (CF) with bt reg, reg and then clone CF with sbb reg, reg.

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

uint32_t fill1(uint32_t a, int bit) {
uint32_t b;

b = a = a & (1 << bit);

a <<= 31 - bit;
b >>= bit;

return (a - b) | a;
}

uint32_t fill2(uint32_t a, int bit) {
a <<= 31 - bit;
return (int32_t)(a) >> 31;
}

uint32_t fill386(uint32_t a, int bit) {
uint32_t result;             
__asm__ __volatile__ (
"bt  %1, %0\n"
"sbb %0, %0\n"
: "=r" (result)
: "r" (bit), "0" (a)
);
return result;
}

int main(int argc, char* argv[]) {
uint32_t x, i;
if (argc > 1)
x = (unsigned long)strtol(argv[1], NULL, 0);

printf("input = %08x\n", x);
for (i=0; i < 32; i++)
printf("bit %2d: fill1 = %08x, fill2 = %08x, fill386 = %08x\n",
i,
fill1(x, i),
fill2(x, i),
fill386(x, i)
);

return EXIT_SUCCESS;
}

Transpose bits in byte using SIMD instructions

2010-03-31T21:41:00.005+02:00

Method presented here allows to get any bit permutation, transposition is just one of possible operations. Lookup-based approach would be faster, but algorithm is worth to (re)show.

Algorithm outline for 8-byte vector (with SSE instruction it is possible to get 2 operations in parallel):

fill vector with given byte
[11010001] =>
[11010001|11010001|11010001|11010001|11010001|11010001|11010001|11010001]
leave one bit per byte
[10000000|01000000|00000000|00010000|00000000|00000000|00000000|00000001]
perform desired transposition ("move" bits around)
[00000001|000000010|00000000|00001000|00000000|00000000|00000000|10000000]
perform horizontal OR of all bytes
[10001011]

Here is my old MMX code (polish text); below SSE/SSE5 implementation details.

Ad 1. Series of punpcklbw/punpcklwb/shufps or pshufb if CPU supports SSSE3.

# 1.1
movd      %eax, %xmm0
shufps    $0x00, %xmm0, %xmm0
punpcklbw %xmm0, %xmm0
punpcklwd %xmm0, %xmm0

# 1.2
pxor      %xmm1, %xmm1
movd       %eax, %xmm0
pshufb    %xmm1, %xmm0

Ad 2. Simple pand with mask packed_qword(0x8040201008040201).

pand  MASK1, %xmm0

Ad 3. If plain SSE instructions are supported this step require some work. First each bit is populated to fill whole byte (using pcmpeq - we get negated result), then mask bits on desired positons.

SSE5 has powerful instruction protb that can do perform rotation of each byte with independent amount - so in this case just one instruction is needed.

# SSE
pcmpeq  %xmm1, %xmm0
pandn   MASK2, %xmm0

# SSE5
protb    ROT, %xmm0, %xmm0

Ad 4. Since bits are placed on distinct positions, we can use instruction psadbw, that calculate horizontal sums of bytewide differences from two registers (separately for low and high registers half). If one register is full of zeros, we get sum of bytes from other register.

psadbw  %xmm1, %xmm0
movd    %xmm0, %eax

Depending on instruction set three (SSE) or two (SSE5) additional tables are needed.

Opis biblioteki pthreads na Wikibooks

2010-03-31T18:56:00.005+02:00

W ramach głębszego poznawania biblioteki pthreads utworzyłem w serwisie wikibooks opis POSIX Threads, zawierający bardzo podstawowe informacje o większości funkcji tej biblioteki oraz nieco o rozszerzeniach Linuxowej implementacji. Integralną częścią są przykładowe programy.

(Wikibooks niestety nie zyskał takiej popularności, jak Wikipedia, a to całkiem wygodna platforma do tworzenia różnego rodzaju podręczników).

PostgreSQL: get selected rows with given order

2010-03-30T10:14:00.010+02:00

Suppose that database stores some kind of dictionary and user picks some items, but wants to keep order. For example dictionary has entries with id=0..10, and user picked 9, 2, 4 and 0. This simple query does the job (query splitted):

foo = SELECT (ARRAY[9,2,4,0])[i] AS index, i AS ord FROM  generate_series(1, 4) AS i;
SELECT * FROM dictionary INNER JOIN (foo) ON dictionary.id=foo.index ORDER BY foo.ord

Słowa mistrza

2009-11-14T21:45:00.004+01:00

Wczoraj późnym wieczorem czytałem jakiś wywiad z mistrzem Andrzejem Poniedzielskim, z którego wynotowałem następujące zdanie:

Dziś każdy pisze sobie muzykę i teksty, zapowiada, wykonuje, a telewizja sprawia wrażenie, że jeszcze ktoś oprócz niego samego się tym bawi.

Przed chwilą natomiast przypadkiem oglądnąłem Kabaretowy Klub Dwójki prowadzony przez liderów dwóch najpopularniejszych formacji... i właśnie tak mi się ten cytat z Poniedzielskiego skojarzył.

I'm not afraid

2009-09-21T12:36:00.001+02:00

I use goto statements!

C++ main disfunctions

2009-08-11T20:20:00.005+02:00

In my opinion there are two main disadvantages of C++:

lack of local functions (called sometimes "nested")
lack of pointers to class method ("delegates")

Ad 1. GotW #58 shows use of local class to simulate local functions, but this is partial solution - class has no direct access to objects existing in outer scope. This force programmer to manage many things manually (more work) and is place of potential error.

Ad 2. Borland has __closure extension (no portable code), there are some portable libraries that does the trick. But everything is not compatible with each other, we can forget about real code reuse.

Cytat dnia

2009-06-30T08:19:00.002+02:00

Naprawdę rozczulający cytat:

Zarządzanie pamięcią w C++ to podstawowy
wyróżnik języka i jedna z jego najmocniejszych
stron, jeśli się umie ją stosować.

Życzę zatem wszystkim programistom C++ udanego debug^Wdnia. :)

Napisał o mnie Witold Piecuch!

2009-06-04T18:26:00.006+02:00

Okres przedwyborczy to czas wyjątkowy, prawie jak Wigilia. Politycy mówią ludzkim głosem i to nie do kamer, tylko do ludzi!

Kandydat na europosła z ramienia partii demokraci.pzpr, pan Witold Piecuch, raczył wypowiedzieć się na temat mojej skromnej osoby. Niestety, nie są to słowa pochlebne - otóż wg pana Piecucha jestem niepoprawnym naiwniakiem, na dodatek dziwacznym, bo dającym sobie wciskać różne populistyczne i patriotyczne kity.

Na dowód pozwolę sobie zacytować fragment ulotki wyborczej w/w kandydata:

[...] Chcę udowodnić, że Podkarpacie nie musi być jakimś dziwacznym bastionem sił narodowo-populistycznych, wiecznie zwodzonym przez różnych cwaniaków.

Aż chciałoby się powiedzieć: "Diamencie stukaratowy. Madrość Twoja jak stąd do baobabu".

Dlaczego Polska pozostanie państwem pastewno-buraczanym?

2009-05-07T11:08:00.006+02:00

Najpierw fragment wypowiedzi profesora Łukasza Turskiego:

W krajach o tradycji anglosaskiej ściąganie praktycznie nie istnieje. Oczywiście ono się tam zdarza, bo tam nie żyją sami święci. Tyle, że tam brutalność karania za oszustwa szkolne jest niebywała. W Colorado jest szkoła pilotów amerykańskiej armii. Na jednym z najważniejszych egzaminów złapano tam uczniów na ściąganiu. I wywalono z uczelni cały rocznik, na którego szkolenie wydano wiele milionów dolarów. Zapamiętałem wypowiedź komendanta szkoły: „My oddajemy w ręce pilotów naszych sił zbrojnych niezwykle drogie urządzenia i musimy mieć do nich pełne zaufanie. Nas nie stać na to, żebyśmy powierzali bezpieczeństwo Stanów Zjednoczonych ludziom, którzy oszukują”. Tam naprawdę mało się ściąga, a jeśli już ktoś tak zrobi, to się za nim – jak z Edwardem Kennedym, który miał taką wpadkę jako młody człowiek – ciągnie to potem przez całe życie.

A teraz reklama serwowana na wykopie:

Czy nie czujecie się Państwo zażenowani, że jesteśmy takim zadupiem cywilizacyjnym?[1] Taka reklama przechodzi bez echa, a przecież serwis wykop jest jednym z popularniejszych w polskiej Sieci.

Dopóki będziemy przymykać oko na małe oszustwa (no, nie takie małe), dopóki kombinatorstwo," radzenie sobie", "siła przebicia", będą najwyższą cnotą Polaka, kraj nasz pozostanie pastewno-buraczanym, którego największym osiągnięciem tzw. high-tech będzie montownia komputerów marki Dell. Zaś minister edukacji, pani Hall, beż żenady będzie wygłaszała, że matematyka jest nam potrzebna do... numerowania domów przy ulicy.

([1] Wiem, że przeciętnego wykształciucha bardziej wstydzi "kurdupel Kaczor", względnie "krótkie rączki Gosiewskiego").

Polaris - Background stories

2009-04-27T17:00:00.003+02:00

Najnowsza płyta Polarisa pt. Background Stories właśnie doszła. Przesłuchałem już całą i mogę powiedzieć, że to kilkadziesiąt minut ciekawych i miłych dla ucha kompozycji.

Dopisek: Po całym dniu słuchania mogę tylko potwierdzić, że pierwsze wrażenia były trafne; warto mieć tę płytkę.

Nic nie umie, a wie wszystko!

2009-04-16T00:40:00.003+02:00

Są takie kierunki studiów, które wzbudzają we mnie autentyczne przerażenie, np. gender studies (że niby my faceci to coś mamy, a kobietom tego brakuje - albo odwrotnie). Ale kierunek pod tytułem europeistyka jest jakimś koszmarem, który chyba spełnia tę samą rolę co parę lat temu zarządzanie-i-marketing (na jednym wydechu mówimy!). Dlaczego o tym piszę? Otóż w radiowej Trójce kilka dni temu gościło dwóch studentów rzeczonej europeistyki i jeden z nich wypowiedział takie zdanie, przy którym żartobliwie proponowane przez Andrzeja Poniedzielskiego "emaile do Koryntian" są przysłowiowym pikusiem. Student ów, przypominam - europeistyki - wygłosił był następującą kwestię: "Ludzie nie powinni być indywiduami, ale działać bardziej na rzecz społeczeństwa". Tak, indywiduami, nie przesłyszałem się. Przepraszam bardzo, ale jest to błąd semantyczny na poziomie 4 klasy szkoły podstawowej; to tak jakby dewaluację pomylić z defloracją. Chorobą przybity do łoża boleści mogłem tylko zawyć z żałości i rzucić kilkoma indywiduami na ka i ha.

Wandale a ClueBot

2009-03-28T16:11:00.002+01:00

Wandale na Wikipedii to smutna rzecz, jednak większość z nich ma spryt rozwielitki (nie ujmując rozwielitkom). Zawsze bowiem bawi mnie, gdy widzę działania ClueBota - robota pracującego na Wikipedii, który automatycznie anuluje edycje wandali. Wykrywa takie edycje na podstawie jakiś w miarę prostych reguł i jeszcze nie widziałem, żeby się pomylił. To naprawdę przezabawne, gdy bezmyślny skrypt komputerowy jest w stanie "przechytrzyć" zdałoby się homo sapiens.

The C Book

2009-03-27T22:11:00.001+01:00

Online version of The C Book, second edition by Mike Banahan, Declan Brady and Mark Doran, originally published by Addison Wesley in 1991.

Re: more constraints

2009-03-23T20:53:00.002+01:00

I complained about C++'s lack of possibility to make some class members read-only on certain level of access protection (public, protected). Well, it is possible with references, but is just solution at syntax level - it needs additional storage, require two separate entities and proper initialization:


class Class {
 public:
  Class() : val(_val) {}

  const int& val; // const ref

  void set_val(int newval) {_val = newval;}

 private:
  int _val; // value
};

I don't like this code...

Nie mogę obronić się przed prawdziwą sztuką

2009-03-23T20:42:00.004+01:00

Trafiłem ostatnio na jakiś kabaret w TV, było całkiem nieźle, do czasu aż nie padło sakramentalne "k...a" (rzecz jasna zupełnie zbędne); oczywiście w telewizji publicznej owa "k...a" została starannie wypikana. Nie byli jednak w stanie wypikać mojego "wyp...", gdy przełączałem kanał.

Czy naprawdę nie da się zrobić skeczu bez "k...y"? To jakiś defekt mózgu? Bo zauważyłem, że kabarety coraz chętniej i bez oporów po "k...y" sięgają. Nie przeczę, że fanom z gimnazjów "k...a" rzucona na scenie może imponować, że na youtubie "k....jących" oglądnie cała masa, może nawet owa "k...a" stanie się kultowa.

Jednak na dłuższą metę takie prostactwo jest męczące i nie rokuje dobrze. Drodzy Twórcy Kabaretowi - nie idźcie tą drogą, na youtubie świat się nie kończy, zaś gimnazjaliści kiedyś wyrosną. I kto was będzie oglądał?

O wandalizmach na Wikipedii

2009-03-23T19:09:00.003+01:00

Bardzo celny komentarz ze strony prawica.net, autorstwa osoby podpisującej się jako Prawicowiec (dotyczący wandalizmu pt. Henryk Batuta):

Grupa Warszawiaków, która "postanowiła dokonać ciekawej prowokacji" przez wprowadzenie do Wikipedii fałszywego hasła postąpiła nieetycznie nadużywając zaufania redaktorów tej encyklopedii.

Nadużyła ta grupa durniów również zaufania czytelników, ponieważ normalny człowiek z reguły nie spodziewa się, że jacyś idioci będą wpisywać do Wikipedii wyssane z palca bzdury. Palant wpuszczający do Internetu fałszywki zachowuje się tak samo, jak ten, co rozsyła komputerowe wirusy nie przynoszące nikomu korzyści (poza zboczoną satysfakcją palanta), a mogące narobić wielu szkód.

Niestety, ludzie przyzwoici są na ogół bezradni wobec kretynów, którzy za nic sobie mają zasady wzajemnego zaufania i przyzwoitości obowiązujące w środowisku cywilizowanym i zanieczyszczają to środowisko wydzielinami swych pokrzywionych mózgów.

Mądrości Wschodu i Zachodu

2009-03-22T21:59:00.003+01:00

Na wykopie podano linkę do pewnej strony, a tam znalazłem absolutną perełkę nt różnic między buddystami a chrześcijanami:

Etyka buddyzmu
Buddysta w danej sytuacji może zachować się tak samo, jak zachowałby się chrześcijanin, ale też może zdarzyć się inaczej (M. Masny "Czy chrześcijanin może być buddystą").

Nie wiem jak dla Państwa, ale dla mnie bomba!

Neural Networks - A Systematic Introduction

2008-12-14T03:39:00.001+01:00

Book by Raul Rojas: http://page.mi.fu-berlin.de/rojas/neural/index.html.html.

Farscape

2008-12-11T22:28:00.002+01:00

Few weeks ago I heard part of a track from Farscape by Klaus Schulze & Lisa Gerrard. I've felt in love and decided to grab the CDs as fast as I can. Definitively one of the best piece of music I have ever heard... masterpiece.

Text algorithms - book

2008-10-19T22:24:00.006+02:00

Book by M. Crochemore and W.Rytter is available in a PostScript format:
~~http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html. I don't see any copyright/licensing notices, but we probably can assume that is free for private use.~~

Update (2011-04-14): book is freely available on M. Crochemore's site, in a PDF format, just click.

Demovibes Live

2008-10-17T01:50:00.003+02:00

What can I say? New demovibes set, live remixes is available. Thanks Willb.

"Wprowadzenie do grafiki komputerowej"

2008-10-05T22:01:00.007+02:00

Piszę o książce Foleya, van Dama, et al., w przekładzie prof. Jana Zabrodzkiego.

WNT wciąż sprzedaje i reklamuje ten podręcznik słowami "oto książka uznawana w świecie za najlepszą pozycję dotyczącą grafiki komputerowej". Nie mogę zaprzeczyć, że książka jest dobrą pozycją, np. rozdziały o modelu wirtualnej kamery, barwie, czy rasteryzacji są wyśmienite i "ponadczasowe" (fakt, rasteryzacją mało kto się teraz zajmuje, ale warto wiedzieć, może przyjdzie nam coś narysować na jakimś 8051?).

Proszę jednak pamiętać, że to jest przekład książki ukończonej w 1990 roku, czyli 18 lat temu; pierwsze polskie wydanie ukazało się w 1995. W międzyczasie postęp w dziedzinie informatyki nastąpił ogromny. Rozdziały o generowaniu fotorealistycznych obrazów mówią ledwie o podstawowych metodach, nie ma opisanych wielu modeli oświetlenia, nie ma bardziej zaawansowanych metod generowanie obrazów (path-tracing, bidirectional path-tracing, photon mapping, subsurface-scattering). Rozdział o krzywych i powierzchniach parametrycznych jest bardzo krótki, o wiele lepiej zaglądnąć do "Podstaw modelowania krzywych i powierzchni" P. Kiciaka (WNT 2005), choć to pozycja dość ciężka. O CSG są dosłownie dwie strony; z resztą wiele problemów jest wyłącznie zasygnalizowanych - np. antyaliasing przy rasteryzacji, budowanie drzew BSP i inne. (Jeśli chodzi o algorytmy graficzne to WNT wydało w 2006 świetną "Goemetrię obliczeniową" van Berga et al.).

Gdy kupiłem "Wprowadzenie..." chyba w 2000 roku, może wcześniej, wówczas o powszechnym dostępie do Internetu można było pomarzyć - książka to było coś, była - nie bójmy się tego określenia - oknem na świat. Poza tym raczej nie było alternatyw, no może poza jedną na wpół sensowną książką "Grafika PC bez tajemnic". Obecnie wszystko to można znaleźć po paru klikach w Sieci, choćby przez angielską Wikipedię, która zwykle ma bardzo ciekawe linki zewnętrzne. Przy okazji polecam dwie strony o grafice i krzywych.

Więc jeśli ktoś rozważa kupno tej pozycji to powiedziałbym tak: jeśli wydanie 60-70 złotych nie stanowi dużego problemu, warto mieć pod ręką. W przeciwnym razie lepiej wydać tę kwotę na wspomnianą "Geometrię..." albo "Podstawy...", bo ceny porównywalne.

VIPER - Visual Pascal InterpretER

2008-10-02T23:00:00.002+02:00

Nice on-line Pascal interpreter with data structures visualiztion (trees, linked lists, etc.). Link: http://viper.mimuw.edu.pl/.

WikiSpam

2008-09-27T00:46:00.003+02:00

Enlarge your Wikipedia for free.

Error Resilience in Compressed Data

2008-09-12T13:10:00.005+02:00

I've found very interesting PhD thesis "Error Resilience in Compressed Data — Selected Topics" by Marek Biskup; author concentrated on decoding broken messages encoded with Huffman codes. Additionally parallel decoding of Huffman-coded messages is shown.

Kompresja danych

2008-09-09T02:02:00.004+02:00

Zakupiłem ostatnio książkę Artura Przelaskowskiego "Kompresja danych" (BTC 2005). To co do tej pory przeczytałem robi bardzo dobre wrażenie, wydaje mi się jakoś bardziej przyjazne od "Wprowadzenie do kompresji" Adama Drozdka.

Jednakże jednej rzeczy mi brakuje: indeksu; to naprawdę ważna rzecz dla czytelnika, kiedy często sięga po pozycję. Poza tym wydaje mi się, że rezygnacja z wcięć akapitowych ekstrawagancka jest.

Informatyka na Wikipedii

2008-09-05T19:19:00.003+02:00

Kiedy w 2003 roku trafiłem na polską Wikipedię, był to projekt raczkujący, ledwie 20 tysięcy haseł (teraz 500 tysięcy i rośnie!). Wówczas wyczytałem na stronie jednej z osób, że jest informatykiem, ale zajmuje się innymi dziedzinami, bo "informatyka jest wyeksploatowana". To oczywista bzdura była i niestety jest nadal. Informatyka to bardzo zapuszczona działka. Przedwczoraj poprawiłem nieco hasło wątek - jego wcześniejsza wersja absolutnie nie dawała odpowiedzi na pytanie "czym jest wątek?". Nawet osoba, która raz w życiu napisała prosty program i od czasu do czasu "grepuje gzipy" nie byłaby w stanie skumać OCB, a cóż dopiero zwykły człowiek.

Moim marzeniem są hasła przystępnie napisane zarówno dla praktyków, teoretyków jak również zwykłych czytelników. Żeby ten ostatni przeczytał i mniej więcej wiedział czym jest to, o czym czytał, praktyk żeby widział jakie są podstawy teoretyczne, a teoretyk jakie zastosowania praktyczne.

Już niedługo Jerzy Ludwichowski poprowadzi dyskusję na konferencji Polskiego Towarzystwa Informatycznego właśnie na ten temat. Mam nadzieję, że m.in. dzięki temu Wikipedia przyciągnie większą liczbę profesjonalistów, nauczycieli akademickich, ażeby nasze wspólne dzieło było jak najlepsze.

BTW to ostatnie brzmi jak wyimek z manifestu Marksa, ale po prawdzie Wikipedia to najlepszy przykład an-archistycznego projektu. Wyobraźcie sobie jak wyglądałaby Wikipedia, gdyby w rządzie był minister do spraw Wikipedii, zaś budżet finansował serwery. Wyglądałoby to pewnie jak Polska Biblioteka Internetowa - 3 miliony złotych w plecy, bo funkcjonalność na poziomie Web 0,0001, zasoby biedne, skany kulawe. A na moje pytania ile w tym roku MSWiA wydało na PBI ministerialne biurwy nie odpowiedziały.

LZP - metoda kompresji

2008-08-30T22:04:00.003+02:00

Jeśli kiedyś będziecie potrzebowali wiedzieć jak działa algorytm LZP, to na coraz bardziej niezawodnej Wikipedii znajdziecie. Dla stron polskich G**gle zwraca 10 stron na krzyż.

Bylejakość

2008-08-26T21:36:00.013+02:00

Na pewnej popularnej stronie dla programistów czytamy (przez litość nie podaję linku):

Krzywa Beziera to krzywa wielomianowa trzeciego stopnia, czyli taka która może być definiowana za pomocą trzech wielomianów (odpowiednio dla współrzędnych x, y i z) z pewnym parametrem t.

Ludzie, co za kosmiczne bzdury! Wielomianowa krzywa Beziera nie ma ograniczonego stopnia, stopień wielomianów może być dowolny. Sama zaś krzywa Beziera jest krzywą parametryczną.

Z tego tekstu wynika, że liczba wielomianów potrzebnych do określenia krzywej jest równa stopniu wielomianu -- tak oczywiście nie jest. Liczba wielomianów zależy od liczby wymiarów przestrzeni w której określana jest krzywa, wielomiany mogą być dowolnego stopnia; np. można mieć krzywą przestrzenną (czyli 3 wielomiany) ale wielomiany stopnia 125.

Dalej, co to znaczy "wielomiany z pewnym parametrem"? Ja pamiętam jeszcze ze szkoły średniej zadania w rodzaju "dla jakiego parametru c wielomian jakiśtam nie ma pierwiastków", ale tutaj rzecz jasna nie chodzi o to. Mowa oczywiście o wielomianach jednej zmiennej, zwyczajowo argument jest tutaj oznaczany literką 't', a nie 'x' jak się przyzwyczailiśmy.

Dalej jest jeszcze jeden cymes:

Krzywe trzeciego stopnia są również krzywymi najniższego stopnia, które nie leżą w jednej płaszczyźnie w 3D.

Czyli, że co -- nie można określić w przestrzeni krzywej trzeciego stopnia, która leżałaby na płaszczyźnie? (Odpowiedź brzmi oczywiście: nie, na całe szczęście można). A poza tym "w jednej płaszczyźnie" -- ale z czym? Bez sensu kompletnie. O co więc chodzi: krzywa 3-stopnia opisywana jest 4 punktami kontrolnymi, i taka liczba punktów może być niewspółpłaszczyznowa, a co za tym idzie krzywa nie będzie płaska.

Dlaczego o tym piszę? Bo razi mnie taka bylejakość, a poza tym lubię się czasem przypieprzyć; na Wikipedii taki tekst by ~~chyba~~ na pewno nie przeszedł (z resztą mamy na wiki całkiem nieźle opracowany temat krzywych i powierzchni Beziera).

27.08.2008 - dwie drobne poprawki

Wrap me!

2008-08-24T13:52:00.007+02:00

Inheritance is fundamental way of creating new types in OOP. Apart of this, there is another important technique: composition, using many object to create higher level objects that provide interface to selected members of component objects. Inheritance is supported by many languages at syntax level, composition -- not!

Consider simple (real-world) example: we have GUI objects -- static label, and list box, we want another widget, labeled list box, a composition of these two simple widgets. We have to write tons of wrappers, that just call label or list methods. Here is example (C++):


class Label {
 public:
  void set_text(string s);
  string get_text();
};


class ListBox {
 public:
  void   clear();
  int    add_item(string s, bool uppercase);
  string get_item(int index);
};


class LabeledListBox {
 public:
  void   set_label(string s) {label.set_text(s);}
  string get_label() {return label.get_text();}

  void   clear() {box.clear();}
  int    add_item(string s) {return box.add_item(s, false);}
  int    add_item_uppercase(string s) {return box.add_item(s, true);}
  string get_item(int index) {return box.get_item(inex);}
 private:
  Label label;
  ListBox box;

};

Of course C++ compiler is able to inline LabeledListBox methods, but programmer have to write many lines of code that merely call another methods. He must know types of arguments, returned values and other. And if some class is changed, he must update classes that use this one. He must maintain all these stupid wrappers. Wrappers are evil.

Wrappers are so frequently used in programming, that I'm still don't know why syntax of popular languages do not reflect this state. This is my view of syntax, but I hope shows the intention -- simple things should remain simple on screen:


class LabeledListBox {
 public:
  method set_label is label.set_text; // rename
  method get_label is label.get_text; // rename

  method clear, get_item from box; // publish two methods of box object
  method add_item is box.add_item with uppercase=false;  // create simple wrappers
  method add_item_upperacase is box.add_item with uppercase=true; // with default arguments set to const

 private:
  Label label;
  ListBox box;
};

Coroutines in C++

2008-08-19T20:06:00.005+02:00

What a surprise, there is a portable library for coroutines written 9 years ago by Keld Helsgaun.

Today I compiled some examples using gcc (MinGW) and seems to work! Great! I will try to explore this library and show some additional examples.

More constraints, please

2008-08-15T18:58:00.004+02:00

In C++ classes have public, protected and private members. Variable member can be also declared as const or static const and it make such member read-only.

But it would be really great if we can select level of protection, and declare that some variable is const only when accessed at public or protected level. Here is a sample:


class C1 { // C++ - present
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
  int get_x() const { return x;}

 private:
  int x;
};

class C2 { // C++ - future?
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
 
 public const:
  int x;
}

Member x can be freely read/write within C2 member functions, but when accessed from outside, x is read only.

This is not as powerful as Borland's extension __property, which allow to declare property as alias for member variable, or setup getter/setter for a property. However I think proposed extension wouldn't bring much work for compilers authors.

With C++

2008-08-13T09:52:00.003+02:00

C++ has lack of everything useful, you won't find local functions for example. But I really miss Pascal with statement. I know people say that would confuse programmer or even compiler. Wait! Pascal programmers were not confused, Pascal compilers were able to deal with this. Moreover, C++ programmers are not confused with tons of nested name spaces, crazy visibility rules and other odds.

Here is a snippet from my program:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  if (data.measure_dist[i].active)
     find_crosspoints(
         data.measure_dist[i].point_1,
         data.measure_dist[i].point_2,
         outline,
         data.measure_dist[i].crosspoints
     );

Using with would make this much clearer:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  with (data.measure_dist[i]) {
     if (active)
         find_crosspoints(point_1, point_2, outline, crosspoints);
  }

Does anybody confused about this code? Does anybody don't know what above code do? I don't think so.

Lets continue. With could also accept more complex syntax and allow temporary rename different entities. This (inefficient!) code finds all intersection between two sets of segments:

double u, v; // parameters, lerp(A, B, u) = A + u*(B-A)
for (int i=0; i < data.points.inner.size() - 1; i++)
  for (int j=0; j < data.points.outer.size() - 1; j++) {
      bool b = intersection(
          data.outline.inner[i],
          data.outline.inner[i+1],
          data.outline.outer[j],
          data.outline.outer[j+1],
          u, v);

      if (b)
          crosspoints.add(lerp(data.outline.inner[i], data.outline.inner[i+1], u));
  }

Now compare with following code:

double u, v;
with (data.points) {
  with (inner as A, outer as B) {
      for (int i=0; i < A.size() - 1; i++)
          for (int j=0; j < B.size() - 1; j++)
              if (intersection(A[i], A[i+1], B[i], B[i+1]))
                  crosspoints.add(lerp(A[i], A[i+1], u));
      }
}

Code is easier, cleaner, compacted. In next posts I will show some other ideas.

demoscene.tv

2008-08-11T00:38:00.000+02:00

For a years I was big fan of demoscene. When I was young, demos and intros (some watched over and over, like "Jizz" by TBL) pushed me to learn many new things; moreover I still like to listen demoscene music; for example tracks from music disc "Ambrozia" released by group Pulse around 10 years ago still sound nice.

Now youtube is full of old and new demos uploaded by Good People. But on the net there are Much Better Good People, who created http://demoscene.tv - you can watch demos in high quality, yeah. BTW I love "Photon" by Purple.