Monthly Archives: August 2013

Linking C Static Libraries With Duplicate Symbols

3 Replies

I came across some interesting linker behaviour today. I was vehemently stating to a colleague that: if I have two static libraries which both contain a symbol “foo” and I try to link those libraries into an executable, I will get a symbol clash and the link should fail. Interestingly, in the test program I wrote this did not happen. I read through “man ld” and it seemed to me like the link should fail so I set about figuring out why my test program linked. I am using GCC 4.6.1 running on Ubuntu 11.10 x64 for all of these results.

Follows are 5 small source files:

/* foo1.c */
int foo(int x)
{
return x;
}
 
/* foo2a.c */
int foo(int x)
{
return x + 1;
}
 
/* foo2b.c */
int foo(int x)
{
return x + 1;
}
int bar(int x)
{
return x + 10;
}
 
/* test2a.c */
#include <stdio.h>
#include <stdlib.h>
extern int foo(int x);
int main(int argc, char *argv[])
{
int x = foo(5);
printf("%d\n", x);
exit(0);
}
 
/* test2b.c */
#include <stdio.h>
#include <stdlib.h>
extern int foo(int x);
extern int bar(int x);
int main(int argc, char *argv[])
{
int x = foo(bar(5));
printf("%d\n", x);
exit(0);
}

foo1.c, foo2a.c and foo2b.c should be archived as follows:

gcc -c foo1.c -o foo1.o
ar rcs libfoo1.a foo1.o
gcc -c foo2a.c -o foo2a.o
ar rcs libfoo2a.a foo2a.o
gcc -c foo2b.c -o foo2b.o
ar rcs libfoo2b.a foo2b.o

This creates three libraries:

  • libfoo1.a – contains an implementation of the function foo() which returns the argument.
  • libfoo2a.a – contains an implementation of the function foo() which returns the argument plus one.
  • libfoo2b.a – contains an implementation of the function foo() which returns the argument plus one as well as a function bar() which returns the argument plus ten.

All of the libraries contain the symbol “foo” so I would expect the linker to fail in any case where I link more than one of these libraries.

The first test program calls foo(5) and prints the return value. For t1, the executable is linked first with libfoo1 then libfoo2a. For t2, libfoo2a then libfoo1.

gcc -c foo1.c -o foo1.o
nappleton@nickvm:~/Desktop$ gcc -c testa.c -o testa.o
nappleton@nickvm:~/Desktop$ gcc -o t1 testa.o -L. -lfoo1 -lfoo2a && ./t1
5
nappleton@nickvm:~/Desktop$ gcc -o t2 testa.o -L. -lfoo2a -lfoo1 && ./t2
6

This is exactly the test setup which I ran for my colleague. It shows that the program does in-fact link and that the ordering of the libraries matters. The first library specified on the command line is the one with the foo() implementation which will be used. The second one appears to be ignored.

The second test case is more interesting. The program calls foo(bar(5)) and prints the value. For t3, the executable is linked first with libfoo1 then libfoo2b. For t4, libfoo2b is linked first then libfoo1.

nappleton@nickvm:~/Desktop$ gcc -c testb.c -o testb.o
nappleton@nickvm:~/Desktop$ gcc -o t3 testb.o -L. -lfoo1 -lfoo2b && ./t3
./libfoo2b.a(foo2b.o): In function `foo':
foo2b.c:(.text+0x0): multiple definition of `foo'
./libfoo1.a(foo1.o):foo1.c:(.text+0x0): first defined here
collect2: ld returned 1 exit status
nappleton@nickvm:~/Desktop$ gcc -o t4 testb.o -L. -lfoo2b -lfoo1 && ./t4
16

Based on these results, I am guessing that the linker stops searching libraries once all unresolved symbols have been found. This behaviour would explain why t1, t2 and t4 build successfully without multiple definition errors. t3 fails to build because after linking against libfoo1, foo is found but bar is still unresolved; foo2b is then searched, foo is found again and the linker explodes.

I’m not sure if the behaviour is necessarily bad. It seems reasonable for a linker to stop searching once all symbols have been found. However, it would be nice to have an option to be informed when I am doing something which is likely to be stupid. A warning “libraries x, y and z were not searched because all symbols were already resolved” might be nice.

An interesting note: on OS X, if the -all_load flag is passed to the linker, all of these programs fail to build as the linker tries to add all symbols from all libraries even if all of the unresolved symbols have been found.

Derivation of fast DCT-4 algorithm based on DFT

2 Replies

It’s well known that an N point DCT-4 can be computed using an N/2 point complex FFT. Although the algorithm is widespread, the texts which I have read on the subject have not provided the details as to how it works. I’ve been trying to understand this for a while (I tend not to use algorithms until I understand them) and finally figured it out and thought I would share (please provide comments/links if you can find a better or shorter explanation – this is as good as I could get).

Start with the definition:

    \[ X_k = \displaystyle\sum\limits_{n=0}^{N-1} x_n \cos \frac{ \pi \left( n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N} \]

Trig functions are hard to manipulate in expressions (for me anyway), so knowing that x_n is real, we change the \cos into a complex exponential and obtain the following:

    \[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N-1} x_n \mathrm{e}^{\frac{\mathrm{j} \pi \left( n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \right\} \]

It is worth noting that the sign of the exponent is irrelevant.

We then split the expression up to operate over two half-length sequences composed of x_{2n} and x_{N-1-2n}. The second sequence is reversed and decimated because when the n is replaced by N-1-2n in the n + \frac{1}{2} term of the exponential, the expression is negated rather than the offset being modified. We move the N term into another exponential which becomes trivial as N cancels the denominator. i.e.:

    \[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} + x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \mathrm{e}^{\mathrm{j} \pi \left( k + \frac{1}{2} \right)} \right\} \]

Or:

    \[ X_k = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} + \mathrm{j} {\left( -1 \right)}^{k} x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( k + \frac{1}{2} \right) }{N}} \right\} \]

The exponentials still contain no term which resembles an DFT (over length N/2 anyway). To get one, we break up X_k into the terms X_{2k} and X_{N-1-2k}. Again we choose to reverse the second sequence because it will keep the exponential terms in a similar but negated form.

    \[ X_{2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} x_{2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} + \mathrm{j} x_{N-1-2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]

    \[ X_{N-1-2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \mathrm{j} x_{2n} \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} - x_{N-1-2n} \mathrm{e}^{\frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]

Now because we are only interested in the real terms, we can ignore or conjugate anything which contributes to the imaginary term of the above expressions. This means that we can conjugate the exponentials when they are only modulating a real term. Doing this, we obtain:

    \[ X_{2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]

    \[ X_{N-1-2k} = \Re \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( \mathrm{j} x_{2n} - x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]

Almost there, but to obtain the full benefit we need the inner terms to be the same. If we now multiply the X_{N-1-2k} term by - \mathrm{j}, we get:

    \[ X_{N-1-2k} = - \Im \left\{ \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2n + \frac{1}{2} \right) \left( 2k + \frac{1}{2} \right) }{N}} \right\} \]

Done. If we expand out the X_{2k} and X_{N-1-2k} terms completely we get:

    \[ X_{2k} = \Re \left\{ \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2k + \frac{1}{2} \right) }{2N}} \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi n}{N}} \mathrm{e}^{- \frac{\mathrm{j} 2 \pi n k }{N/2}} \right\} \]

    \[ X_{N-1-2k} = - \Im \left\{ \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2k + \frac{1}{2} \right) }{2N}} \displaystyle\sum\limits_{n=0}^{N/2-1} \left( x_{2n} + \mathrm{j} x_{N-1-2n} \right) \mathrm{e}^{- \frac{\mathrm{j} \pi n}{N}} \mathrm{e}^{- \frac{\mathrm{j} 2 \pi n k }{N/2}} \right\} \]

Which give us the steps for a DFT based DCT-4 algorithm:

  • Transform the N point real sequence x_n into the N/2 point complex sequence y_n = x_{2n} + \mathrm{j} x_{N-1-2n}.
  • Multiply each element of the sequence y_n by \mathrm{e}^{- \frac{\mathrm{j} \pi n}{N}}.
  • Find Y, the DFT of the sequence y.
  • Multiply each element of Y_k by \mathrm{e}^{- \frac{\mathrm{j} \pi \left( 2k + \frac{1}{2} \right) }{2N}}.
  • The DCT-4 outputs are given by:

        \[ X_k = \left\{ \begin{array}{l l} \Re \left\{ Y_{k/2} \right\} & \quad \text{for even $k$} \\ - \Im \left\{ Y_{(N-1-k)/2} \right\} & \quad \text{for odd $k$} \end{array} \right. \]