Transpose bits in byte using SIMD instructions

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):

1. fill vector with given byte
   [11010001] =>
   [11010001|11010001|11010001|11010001|11010001|11010001|11010001|11010001]
   
2. leave one bit per byte
   [10000000|01000000|00000000|00010000|00000000|00000000|00000000|00000001]
   
3. perform desired transposition ("move" bits around)
   [00000001|000000010|00000000|00001000|00000000|00000000|00000000|10000000]
   
4. 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

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

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

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

I use goto statements!

C++ main disfunctions

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

1. lack of local functions (called sometimes "nested")
2. 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

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. :)