Wojciech Muła --- website

AVX2 has added support for 256-bit arguments for many operations on packed integers, although not all.

Introduction Informal specification: __m128i mask_lower(const unsigned n) { assert(n < 16); /* __m128i result = 0; for (unsigned int i=0; i < n; i++) { result.byte[i] = 0xff; } */ switch (n) {…

Introduction SSE procedure can convert 16- and 32-digits inputs producing 8- and 16-bytes results.

PMADDWD details This instruction is specialized and I guess isn't often used.

Introduction Naive parsing of unsigned decimal numbers can be coded as: uint32_t parse(char* s) { uint32_t result = 0; while (*s) { const uint8_t digit = *s++; result = result * 10 + (digit - '0'); } return result; } T…

Naive conversion from an ASCII digit to a value could be coded with a switch instruction or a lookup table — too simple, right?

Suppose we have a string containing ASCII zeros and ones, for example "11100100", and we want to interpret this text as a binary number and get value (0xe4).

Introduction Conversion to octal isn't very computer-friendly, each digit occupy 3 bits, it isn't power of two.

"Limited" means a value where at most one bit is set.

The idea is simple: precondition: x is not zero; isolate lowest bit set: x & -x; check if this number is equal to x: x == (x & -x).

There are some places where a low-level programmer can beat a compiler.

Introduction Interpolation search is the modification of binary search, where the index of a "middle" key is obtained from linear interpolation of values at start & end of a processed range: a := start b := end key := searched key while a <= b loop t…

Introduction PDEP is a new instruction from BMI2 (Bit Manipulation Instruction), pseudocode for 32-bit PDEP variant: src - a source word mask - a mask result := 0 k := 0 for i := 0 .. 31 loop if mask.bit[i] then result.bit[i] := src.bit[…

Branchless converting single nibble For a nibble (0..15) stored in a byte conversion could be coded in this way: char nibble_to_hex(uint8_t byte) { assert(byte >= 0 && byte <= 15); char c = byte + '0'; if (byte > 9) c += 'a' - '0' - 1…

Converting byte — SWAR version 1 Algorithm Populate byte v (bits: abcdefgh) in a 64-bit word: const uint64_t r1 = v * 0x0101010101010101 ┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐ │abcdefgh│abcdefgh│abcdefgh│abcdefgh│abcdef…

The C++ bitset conserves a memory, but at cost of speed access.

Yes, definitely.

Recently I needed to synchronize my local repository with a remote machine, just for full backup.

Sample implementation C function for 32-bit numbers: #include <stdint.h> uint32_t movmask(const uint32_t input) { assert((input & 0x7f7f7f7f) == 0); const uint32_t mult = 0x02040810; const uint64_t result = (uint64_t)input * mult; ret…

First we read: 21.4.1 basic_string general requirements [string.require] [...] 3 No erase() or pop_back() member function shall throw any exceptions. ... a few pages later: 21.4.6.5 basic_string::erase [string::erase] basic_string<charT,traits, Allocator>&

Algorithm Rabin-Karp algorithm uses a weak hash function to locate possible substring positions.

Starting from GCC 4.5 the asm statement has new form: asm goto.

The description of Determine if a word has a zero byte from "Bit Twiddling Hacks" says about haszero(v): "the result is the high bits set where the bytes in v were zero".

Fast calculate ceil(log10x) of an unsigned number is described on Bit Twiddling Hacks, this text show the SIMD solution for 32-bit numbers.

I've observed that some patterns issued to strstr cause significant slowdown.

Introduction SSE provides not widely known control register, called MXCSR.

Detailed results Whole table as txt file. instruction count % mov 5934098 37.63% call 1414355 8.97% lea 1071501 6.79% movl 760677 4.82% push 655921 4.16% jmp 611540 3.88% add 560517 3.55% je 490250 3.11% test 475899 3.02% pop 441608 2.80% sub 366228 2.32%…

I needed to iterate through all values of 32-bit unsigned integer, so I wrote: #include <stdint.h> for (uint32_t i=0; i <= UINT32_MAX; i++) { // whatever } Is it ok?

Presented algorithm works properly for any normalized floating point value, examples are given for double precision numbers (64-bit).

This short article shows how a normalized floating point value could be safely converted to an integer value without assistance of FPU/SSE.

It's not clear how function fopen applied to a directory should behave, manual pages don't say anything about this.

Intel announced new extension to SSE: instructions accelerating calculating hashes SHA-1 and SHA256.

The size of an integer in PHP depends on machine, it has 32 bits on 32-bit architectures, and 64 on 64-bit architectures.

Introduction Russ Cox wrote very interesting article about algorithms behind service Google Code Search.

Sample sources Sources are available at github.

Here is a simple PostgreSQL type: CREATE TYPE foo_t AS ( id integer, total bigint ); and a simple query wrapped in a stored procedure: CREATE FUNCTION group_foo() RETURNS SETOF foo_t LANGUAGE "SQL" AS $$ SELECT…

Introduction "Static table" means that data is changed rarely, in my case it's a cache for some reporting system.

PostgreSQL wiki has entry about sprintf — is is quite simple approach (and isn't marked as immutable).

Introduction Trie is a multiway tree where each edge is labelled by a letter; such trees are used as dictionaries.

Introduction Detecting intersection of convex polygons is a common problem in a wide range of problems.

PHP is very funny language.

Sample program Following python script verifies both methods (for 8-bit integers) bits = 8 # unsigned width mask = (1 << bits) - 1 MSB = (1 << (bits - 1)) def base(a, b): return (a + b)/2 def safe1(a, b): LSB_carry = (a & b & 1) return…

Introduction PostgreSQL executing queries with construct like '%text%' can't use any system index (I guess none of existing SQL servers have such feature).

Introduction With SSE2 instructions it's possible to convert up to four numbers in range 0..9999_9999 and get 32 decimal digits results.

If a DAG has got one component, then the simplest traversing method is depth-first-search, which could be easily implemented recursively (using an implicit stack). struct DAGNode { // user data bool visited; // after construction…

If you read the 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…

If a class has to support standard len() function or operator in, then must be a sequence-like.

Introduction Each node of a tree store two kinds of data: user data and trie-related data.

def isiterable(obj) try: iter(obj) return True except TypeError: return False

Introduction Obvious traversal algorithms require O(logn) memory, i.e. an explicit or an implicit stack or a queue.