#C: fast string to hex string

following this post, i have also added a method to convert a char* buffer to a char* buffer which holds the hex values of each input character.

e.g.:
HelloWorld -> 48656c6c6f576f726c64

a branchless method with a lookup table is used again. it works for any type of data (e.g. UTF-16, UTF-8, etc.) as long as sizeof(char) is 1 byte, as is in the standard.

the cfg2 C library now includes the function cfg_char_to_hex(), which can be found here.
it's effectively the reverse of cfg_hex_to_char().

--

#C: fast parsing of hex strings to char buffers

the C library for parsing INI file syntax (cfg2) that i'm hobby-maintaining has recently been improved quite a lot. supports sections, the parser should be much better now, improved API and so on.

one of the features i've added is to be able to store HEX strings of binary data in the text file that can be optionally parsed into memory char buffers.

for example:

some_key=48656c6c6f77576f726c64

where the HEX string equals "HelloWorld".

problems at hand:
1) detect bad length
2) detect bad characters
3) support case-insensitive input

of course, most programmers can immediately start writing a solution for this type of parser and solve all 3 problems, but the question is - how to write this to be as efficient as possible?

solving 1) is quite easy. since we are working with 8 bit characters, we are going to have 256 values per character or a maximum of 0xFF (255). but instead of parsing bad characters we are strict and require the HEX string length to be divisible by 2:

if (len % 2)
    goto error;

one would approach solving 2) with "if, then, else" branches to see if a character in the HEX string is in the 0-9,A-F range of the ASCII table.

3) can be solved with toupper()/tolower()

but instead, a lookup table can be used to solve both 2) and 3) in a single pass. this lookup table could have 256 indexes, where most are filled with zero, while the valid indexes are filled with values of interested.

the table can be seen in this source file - named "hex_to_char_lookup".

so, when we first traverse the example HEX string we reach a couple of characters "48".
the first one "4" - this character has an ASCII decimal value of 52. the lookup table has mapped this value at index 52 as 5. the reason for 5 instead of 4 is that i wanted the table to look pretty, filled with zeroes and thus i increased each value by one so that "0" is mapped to 1, "1" is mapped to 2 and so on. this can be removed for a small optimization [1], but then one has to fill the table with values such as -1.

"8" which is mapped to ASCII index 56 in the table and a value 9 is returned.

if we reach a bad character, 0 will be returned in which case the program should return an error with the bad character position in the HEX string.

at some point in the example string, "c" will be reached and here we could have a case-sensitivity issue, but the lookup table has mapped both the ASCII "c" and "C" to return the same value which is 13 or the 12th index in hexadecimal, plus 1.

0 1 2 3 4 5 6 7 8 9 A B C D E F
                        ^ (12 + 1 = 13)

now, to obtain the resulting C char we have to form a hexadecimal value combining the two decimal values, as follows:

first = table[52]; // 5
second = table[56]; // 9
if (!first || !second)
    goto error;
first--; second--; // 4, 8; possible optimization [1]
unsigned char result = first * 16 + second; // 72 = "H"

and then the result can be written to the output char buffer.

that's all!
TMK, this parsing method would work for any string encoding UTF-8, UTF-16, etc. as long as sizeof(char) == 1, which should be very much true as it's in the ISO C standard.
 --

#libmodplugw

here is a small (wrapper / extension) library that can be used to manipulate libmodplug decoded buffers in terms of rows and patterns with sample accuracy:

https://github.com/neolit123/libmodplugw

--

#fast IEEE 754 double to int32 @ music-dsp

at the music-dsp mailing list there was a short discussion about a "double -> int" rounding hack present in the JUCE library. i've posted an alternative solution that does the same without IEE 754 arithmetic. i'm sure similar solutions can be found in libraries and for CPU's that don't have a floating point co-processor unit. code is for c99.

http://music.columbia.edu/pipermail/music-dsp/2013-September/071572.html

can be summarized into:
1) separate double into mantissa, exponent, sign bit
2) depending on exponent value shift the mantissa left or right by the difference of the exponent and the amount of bits in the mantissa
3) truncate and receive a 32bit integer, while applying the original double's sign

--

#bulls and cows: open source game in ANSI C

here is an open source "bulls and cows" game written in ANSI C:
download

pre-compiled win32 executable included.

i wrote that after a simple challenge proposed by some of my friends, and now apparently they even play it from time to time.

if you are a C programmer, try guessing out why the 0xDA special case happens and how volatile it is.
--

#CFG2 - an INI-like parser

i wrote a simple INI-like parser some time ago called CFG2.
it's released in the "public domain" with source code at http://github.com/neolit123/cfg2.

--

#win32: a tool to set the keyboard repeat rate

i have a windows 7 machine and every time it exits sleep mode it (re)sets the keyboard repeat rate to a very low value (i normally set the value to high). i believe this could be due to a small driver issue.

here is a command line tool that can be used to get/set the kb rate value (source code included):
setkbrate.zip

usage:
setkbrate n
where n is a number between 0 (slowest) and 31 (fastest).
calling with no arguments will output the current rate.

the way to use it when the system exits sleep mode is to set a new task scheduler task:

1) control panel -> system and security -> administrative tools -> task scheduler
2) right click the task list -> create basic task
3) for triggers, one way would be to try to capture the system "exit sleep mode" event:
- set trigger mode to "on an event", log: "system",  source: "power-troubleshooter", id: "1" (should be 1, but  has to be verified in the event log)
4) for the action select "start a program" then browse and set to "setkbrate.exe", while adding a numeric argument of 0-31.

--

#"elevated" demo explained

at Breakpoint 2009 (a demoscene convention), two groups RGBA and TBC released a demo, called "Elevated", which won the 4k (4 kilobytes) competition. the demo consisted of a terrain generation algorithm with shading, texturing, camera manipulation, synth based music and more. this demo is considered "the-best-ever" in this category by many people...

youtube video

i'm quite late, but apparently, one of the people involved in the project - Inigo "IQ" Quilez, the same year did a presentation on some of the techniques used for the demo. here is the PDF file for his presentation:
presentation

very impressive stuff, a portion of which is clearly for GFX gurus only.

--

#articles on object-oriented design in c

here are, a couple of articles by Neil Brown (from june this year @ lwn.net), that explain some of the methods used in the linux kernel to provide virtual function tables and data inheritance in c.

Object-oriented design patterns in the kernel, part 1
Object-oriented design patterns in the kernel, part 2


--

#fast sse tanh written in c

here is fast hyperbolic tangent approximation based on continued fractions.
written in ansi c. works with gcc and msvc.

provides some flexibility in regard of speed / accuracy.

link

--

#iso c99: some 64bit integer printing fun

a small article that gives tips on writing portable code for printing 64bit integers (printf):

i64_printf

source code for download is included

#iso c/c++: runtime and static assertion for gcc 4.4.0+

re: axonlib
we've made some very good progress on the library. v.0.1.0 is about to be released soon. we now have image transparency, scalable images, a lot of widgets, a custom set of stdlib routines for string and memory, a rather fragmenting but fast custom memory allocator and other. also we are now not using heavy c++ types such as 'vector' any more, while 'iostream' is only used for debug builds.

i have made a little page to write some articles on programming methods, optimization techniques, assembler trick and other things i've learned over the years or just recently.

http://sites.google.com/site/neolit123/

as far as programming goes i may be focusing more on assembler and c over c++ and higher level languages.

the first article that is done now is about assertion:
http://sites.google.com/site/neolit123/home/lassert

the original methods are part of axonlib but i release these to the public (under a fairly permissive license) as _none_ of the examples in the internet that i've tried out of interest worked properly and gave errors / warnings for either c or c++ code with the gcc compiler.

[edit] actually the following seems to work as well with not much overhead:


#define STATIC_ASSERT(e) switch(0) { case 0: case (e): ; }
/*
resulting in two errors:
file:line: error: duplicate case value
file:line: error: previously used here
*/


..and is a portable solution, but not very useful because the macro will expand to a switch call but in the same time (e) has to be a constant.

#gcc: speed-tests, inline assembly & volatile declarations

here are some quick tests with gcc (3.x / 4.x) and axonlib.
note: "axAbs" (alt: fabs) and "axExp" (alt: expf) are part of "axMath.h"

[*] gcc speed comparison (win32)

gcc-3.4.2 is the official mingw build, while gcc-4.4.1 is an unofficial build.

test::

n of iterations:
10e+6

calculation:
expf(axAbs(-3.141592))

flag: -O2
gcc-3.4.2: 143 ms
gcc-4.4.1: 6 ms

flag: -O3
gcc-3.4.2: 130ms
gcc-4.4.1: 5ms

conclusion:
gcc-4.4.1 generates faster code.

[*] gcc: macros vs inline functions.

an article with some more in depth information.

test::

n of iterations:
10e+6

calculation:
axAbs(x) in the forms of macro vs inline and expf(x) for weight.


#define t0(x) \
({ \
  register float _x; \
  __asm__ ( "andl $0x7fffffff, %0;" : "=r" (_x) : "0" ((float)x) ); \
  expf(_x); \
})

// -- vs --

inline float t1(float x)
{
  __asm__ ( "andl $0x7fffffff, %0;" : "=r" (x) : "0" (x) );
  return expf(x);
}


flag:
-O2

gcc-3.4.2:
macro: 143ms
inline: 145ms

gcc-4.4.1:
macro: 5ms
inline: 6ms

conclusion:
inline functions are safer. not much difference in performance.

[*] gcc: to "volatile" or not and its impact on performance.

a volatile declared function or variable will not be optimized.

quote:
(on writing code for hardware control) Any self-respecting optimizing compiler would notice that the loop tests the same memory address over and over again. It would almost certainly arrange to reference memory once only, and copy the value into a hardware register, thus speeding up the loop. This is, of course, exactly what we don't want; this is one of the few places where we must look at the place where the pointer points, every time around the loop.

test:::
asm volatile (..) vs asm (..)

calculation:
axExp(x)

n of iterations:
10e+7

flag::
-O2

gcc-4.4.1:
asm volatile: 298ms
asm: 2ms

gcc-3.4.2:
asm volatile: 291ms
asm: 13ms

flag::
-O3

gcc-4.4.1:
asm volatile: 297ms
asm: 2ms

gcc-3.4.2:
asm volatile: 290ms
asm: 12ms

conclusion:
functions declared as "volatile" perform much slower from both compilers.

----------
tested with athlon xp 1800+

lubomir