Sunday, June 21, 2015

How to return array from function

We want function which dynamically creates array of integers, so no static declaration is possible because we do not know how big array needs to be.


We print address of dynamically allocated array in function and in main to be sure it points to the same place and use it to show it is usable. We must use pointer to integer in main because expression

int i[] = allocator(2);

is illegal initializer. It doesn't prevent us from using pointer to integer later as array. Finally we free allocated memory. That what we did is called manual memory allocation and such memory is placed on heap. If we want to use pointer arithmetic we will do something like this:

*i = 1;
*(i + 1) = 2;
printf ("%d, %d\n", *i, *(i+1));

Please note that *(i + 1) is not the same as *i + 1 even if it produces the same output in our example. Dereferencing pointer got higher order of precedence than addition. Because of precedence we are using braces. What if we need two-dimensional array? Two-dimensional array is array of arrays and we will need pointer to pointer.


As we see allocating is more complicated and feeing also. It goes in two steps, first we allocate array of rows and after that we allocate arrays of columns. As in previous case we can use array syntax. Now we can go mixing pointer arithmetic and array syntax or go completely pointer arithmetic


Maybe to add that *(*i+1) corresponds to i[0][1]. That was how to do it, now how not to do it. Going heroic and forcing through pointer to array as return type.


This compiles and executes with few warnings, if we change fun return type by adding another pointer int* (*fun())[], that also works. If something looks difficult, like returning address of array, than design needs additional work. For example


this is much nicer and easy to understand. Please note that returning static array is perfectly fine and that we do not use free on it. Statically declared variables are allocated automatically and available through execution of program. If we forget to declare array as static than we will return dangling pointer, local variable goes out of scope and returned pointer points to who knows what.

Tuesday, June 16, 2015

bgfx

Not sure into which category falls this blog entry, maybe review? I never did any 3D programming, so tutorial is out of question. Anyway I was fiddling with bgfx library and here are my experiences.
According to author, Branimir Karadzic, bgfx is cross-platform, graphics API agnostic, "Bring Your Own Engine/Framework" style rendering library. Since it works on Linux I was interested to take a look at it. Best way to get info on project is to visit https://github.com/bkaradzic/bgfx and read README.md. If you are curious to try it you will need also https://github.com/bkaradzic/bx to build it. Library uses custom tool GENie so that is reason why bx is needed, we will need it for projects as well. I have built it and attempted running examples. Some were working, some not. I was attempting to run them from directory where compiled assemblies are but they need runtime. So to run examples go to /examples/runtime and execute ../../.build/linux64_gcc/bin/example-00-helloworldDebug.
How to generate project make files or codeblocks or codelite projects. Since this is cross-platform tool Windows and Mac OS X targets are supported but I will focus on Linux only. Go to bgfx project root and run

../bx/tools/bin/linux/genie --help

To generate make files, do

../bx/tools/bin/linux/genie --gcc=linux-gcc --with-tools gmake

That will produce examples as targets plus tools, like shaderc. Now cd to .build/projects/gmake-linux and execute make help to see options. For 64 bit Linux we may build using this command:

make config=debug64 example-XY-name/nothing for all

If we are using IDE, we go to .build/projects/codeblocks or codelite, open generated project set target and build it. Now we are ready to start fiddling with provided examples.
For somebody who never did any 3D coding, like me, examples provided with bgfx are too complicated so I dumbed them down.



This is example-00-helloworld reduced to creating and showing blue window. There is huge amount of plumbing code which makes those examples work in very few lines of code. For example entry::processEvents. In original shape example will print some text and place image on the screen.
Next to be slaughtered is cubes example. It draws now single triangle:


Naturally I didn't touch shaders. If we remove completely shaders from code, instances of program, triangle will become black, new achievements of hacking. I also did square, here is the relevant code:


Everything else is the same as for triangle. I hope my experience helps somebody to get started. After I spent eternity in programming there are still areas completely unknown to me. If I didn't get friendly suggestion to use identity as view and orthogonal matrix as projection I would stay on Hello World/blue window.

Saturday, June 13, 2015

Thread-Specific Data API

Last time it was making function thread safe or reentrant via thread local storage, now more complicated thread-specific data. Everything happens on Linux but should be applicable on any UNIX since we are using POSIX.
This one is also called thread-private data API. It creates per thread and per reentrant function storage. Process starts with key creation when thread for the first time calls function, any thread. In order to have key created once pthread_once is used. Then, once we got key, pthread_getspecific and pthread_setspecific are used to deal with thread-specific data. Here is example:


To compile it the following is used:

gcc -o tsdexample tsdexample.c -pthread

Result of execution is:

Main message: Message is 'Hello from main!'
From thread: Message is 'Hello I am lumberjack!'
Again thread: Message is 'Hello I am lumberjack!'
Main message: Message is 'I am not lumberjack!'


In order to init static variable once, macro  PTHREAD_ONCE_INIT is used. During key creation destructor, ordinary free, is passed as parameter to pthread_key_create. Main thread and another thread then are calling reentrant function and setting and retrieving messages which are thread specific, what is expected. If we want to delete key it looks like this:


Though in example program it is static variable and it will go out of scope together with program.

Thursday, June 11, 2015

Thread safety

Before I start with thread safety, evolving design, if something can be improved don't be lazy.
Now I remembered that GCC supports 128 bit integers and that Fibonacci numbers can be calculated up to forty digits. There is problem with printing those 128 bit integers but somebody already offered utility function to convert them to string, that was Perkins . I only added zero case to his solution.


Now we can go up to 186th Fibonacci number without overflow.

Threads

There is few buzz words which people are using in job ads, related to threads, but usually they fail to define them. For example multithreading, concurrency, thread safety, reentrant function and similar.
What is reentrant function or thread safe function? That would be such function that does not use statically allocated or global variables and result depends only on input arguments. For example:


is not reentrant or threadsafe. If more than one thread calls that function in the same time, that is concurrency, it will produce unpredictable result. Even if it is called sequentially result will be influenced by previous calls, possibly from different thread. We are on Linux and we are using POSIX threads. So, here is example where two threads are calling nonreentrant function:


To compile it I used:

gcc -o notreentrant -g -gdwarf-2 notreentrant.c -pthread

That -gdwarf-2 story is distraction, I am using gcc version 4.9.2 built from source on old Mint based on Ubuntu 12.04 and new gcc outputs by default debug info which gdb doesn’t understand. If you just built new gcc and gdb doesn't work as expected, that is cure. Linker switch -pthread is required.
Example output from execution looks like this:

thread 1 call 1 = 2, expecting 2
thread 1 call 2 = 7, expecting 4
thread 1 call 3 = 9, expecting 6
thread 1 call 4 = 11, expecting 8
thread 2 call 1 = 5, expecting 3
thread 2 call 2 = 14, expecting 6
thread 2 call 3 = 17, expecting 9
thread 2 call 4 = 20, expecting 12
thread 1 exit code 1
thread 2 exit code 2


How do we remedy that? We make increase reentrant or thread safe:


We requested thread local storage, available since kernel 2.6 and supported by gcc 3.3 and higher. When thread terminates and goes out of scope, local thread storage does to. We could make function reentrant via using thread specific data, but that is much more code, maybe next time.

Saturday, June 6, 2015

Similarities and differences between Java and C

As almost everybody knows Java was intended to be sort of C without pointers and to be used in smart home appliances. And then Gosling and his co-workers were drinking too much coffee and it come out more like C++ without pointers, resource management and multiple inheritance. So, how really different can be coding the same task in C and Java. Practically we are addressing just resource management part, we will not try to go OO in C. We implement fast Fibonacci algorithm in Java.


It is really very fast, logarithmic fast. Now we try to do the same in C, we will skip BigInteger and use long. The first thing which wont work in C is array allocation, declaring them like that will create local variable. So we create function to allocate our arrays in order to return them to caller:


Those Q and I arrays can be global variables and we are ready to go, almost. We can not declare t as array since initializer can't be function call. Not big deal, we will use pointer to long but that introduces another problem. That pointer may point to global variables Q and I or allocated variables. Again we can check to what it points and if it doesn't point to Q or I we can call free. Already we have feeling that those arrays returned by squaring function are somehow polymorphic and in Java they were not like that. Allocating and freeing arrays on every step of recursion and checking should we free or not doesn't look right. Attempt to literally translate Java code may look something like this:


If Q and I arrays are created using malloc we could do reassignments of initial array and free it at the end of calculation. So no global Q and I but they will be allocated on the heap and serve all recursive calls.


Now if we run valgrind on our program it will report:

==18896== HEAP SUMMARY:
==18896==     in use at exit: 0 bytes in 0 blocks
==18896==   total heap usage: 93 allocs, 93 frees, 1,488 bytes allocated
==18896== 
==18896== All heap blocks were freed -- no leaks are possible


Looking now at initial Java solution, it also could benefit from array reuse instead of allocating new ones on every step. Garbage collector is nice thing but not thinking at all about resource management may result in lower quality of code.

Friday, June 5, 2015

Functions, pointers, nested functions, clojures

While ago GCC introduced nested functions which are allowing easy solution of funargs problem. With funargs problem solved C can accommodate closures and provide everything what different modern languages can, except funny syntax. In order to demonstrate that we need function pointers and they are not part of modern languages derived from C. So, we start with function pointers refresher.

Function pointers

They are more cryptic than other pointers and they scare away younger generations of programmers. We will declare function and pointer to it:


We have return type, variable name in brackets and type list for parameters. We could also use address of operator during assignment. How we pass it as parameter?


How we return it, write function which is returning function pointer? There is user friendly way, we declare typedef for function pointer:


But there is also user unfriendly way:


Return type of return type goes in front, inside first pair of brackets name and own parameters, inside the second pair of brackets list of parameter types of return type. And just for those who value extreme programming above all, pointer to function which returns function which returns function:


Nested Functions

Those are GCC specifics and they are just ordinary functions but inside another function. Standard C will not let you define function within function. To demonstrate we can do trampolining of one notoriously recursive function.


Here nested function is accessing variables which are host scoped and returns self or NULL. We got whole function back but we are not really using it, except to exit while loop if it is NULL. To remedy that we will dispatch those nested functions out of host function.


Here we have struct which is global variable, it is not really closure but just named like that, and one function generator. If we pass zero to generator we get one function back and for non zero the other one. Both nested functions now operating on global variable. In previous example we were working on variables belonging to host function, in this case if we try the same we will have problems since host's variables went out of scope.

Funarg problem

This one is related to functional languages and nested functions. If we pass nested function as argument to another function that is called downward funarg problem. Returning nested function to caller is upwards funarg problem. If any of passed or returned functions references variable from scope of declarer, those must be available to nested function so it can be executed. Passing nested function as argument to another function is not problem in C since all local variables of declarer are alive.


Returning nested function is more problematic because declarer went out of scope. That could be addressed like in Java, if anonymous function uses some declarer's variable, that variable must be final. In C there is even more options, we can use static variables or allocate them on the heap.


It is easier to use static than malloc and free. Removing static from counter declaration will result in exception during execution of program. So, funargs problem is not problem for C in GCC version. This makes C almost functional language, functional with few extras.

Tuesday, May 26, 2015

Recursive Squaring

This one neatly solves problem of log n multiplications to calculate nth power of of some number. It goes in two stages, calls self recursively with half power until it reaches power 0 or 1 and then squares results. If power was not even correction is required, additional multiplication with base.


If we want to see how it works and how many times it calls self we can insert debug code:


Should have been included it in previous blog entries about recursion but better late than never.