The Coming Software Apocalypse

[WIckedWitch]

OK - Here's how to find out what macros a C compiler predefines.

A predefined macro affects user-written code in at most two ways:

1. It can be tested to control conditional compilation.
2. It can supply a value that it used by the programmer.

The trick to discover inbuilt predefined macros is to scan all of the C compilers header files and extract from them (e.g. by using awk) a list of all items that match the syntactic pattern of a preprocessor identifier. Then you create a program of the following form;

#include <stdio.h>
int main(void)
{
#ifdef identifier-1
printf("identifier-1 has value ");
printf(#identifier-1);
printf("\n");
#endif

// then repeat the above ifdef/endif pattern for all the identifiers you have listed

return 0;
}

Assuming I've remembered the # stringify operator correctly, [*** - I HADN'T - SEE CORRECTION IN POST BELOW ***] running this program under given compiler options then tells you what predefined macros are given under those options and what their values are. I've used this technique successfully on some big code audits - one of them for forensic use in a large international litigation..

BUT

this is, alas, only a partial algorithm. It correctly identifies the values of all predefined macros from among identifiers that exist in the texts of header files but this does not do the whole job with gcc, which constructs predefined identifiers on-the-fly, so that they may not appear explicitly in those header files.

Various further ploys can be used to do the job completely for gcc, but they are all variations on the above pattern applied to different search domains.

Simples!

[WIckedWitch]

And now, folks, another one:

Write C code to determine the maximum of two integers without using an if, or other conditional statement.

OK. Here is the solution. I've done it both as a macro and a function. A decent optimising compiler will eliminate the two comparisons of a with 0 and produce pretty fast code for this.

Code: Select all

#include <stdio.h>

#define OPABS(a) ((a) * (((a)>=0) - ((a)<0)))

int opabs (int a) ( return a * ((a>=0) - (a<0)); } 

int main(void)
{
	printf("opabs(%i) = %i\n",  1, opabs( 1));
	printf("opabs(%i) = %i\n", -1, opabs(-1));
	
	printf("OPABS(%i) = %i\n",  1, OPABS( 1));
	printf("OPABS(%i) = %i\n", -1, OPABS(-1));
	
	return 0;
}

It's not perfect and could be tweaked a little further to help less powerful optimisers generate fast code from it.

The key thing, however, is that, at least at the source code level, there is just one single path through the code. Minimising the number of branches in the code is an extremely important thing in embedded systems that have to be shipped with test instrumentation in the finished product, as is required by some levels of DO 178.

An just for good measure, here is a clipping function done the same way:

Code: Select all

#include <stdio.h>

int opclip1(int a, int b, int i)
{
	return a*(i<a) + i*((i>=a)&&(i<=b)) + b*(i>b);
}

int opclip2(int a, int b, int i)
{
	int temparray[3] = {a, i, b};
	
	return temparray[((i>=a)&&(i<=b)) + ((i>b)<<1)];
}

int main(void)
{
	printf("opclip1(%i, %i, %i) = %i\n", 1, 3,  2, opclip1(1, 3,  2));
 	printf("opclip1(%i, %i, %i) = %i\n", 1, 3, -1, opclip1(1, 3, -1));
	printf("opclip1(%i, %i, %i) = %i\n", 1, 3,  4, opclip1(1, 3,  4));
	
	printf("\n");
	
	printf("opclip2(%i, %i, %i) = %i\n", 1, 3,  2, opclip2(1, 3,  2));
 	printf("opclip2(%i, %i, %i) = %i\n", 1, 3, -1, opclip2(1, 3, -1));
	printf("opclip2(%i, %i, %i) = %i\n", 1, 3,  4, opclip2(1, 3,  4));	

	return 0;
}

The first two arguments specify bounds. If the third argument is less than the lower bound, the function returns the lower bound. If the third argument exceeds the upper bound, then the function returns the upper bound. Otherwise the function returns the value of the third argument. Again, there are several different ways of doing this.

And finally, max and min functions in the same vein.

Code: Select all

#include <stdio.h>

int opmax(int a, int b)
{
	return ((a<b)*b + (!(a<b))*a);
}

int opmin(int a, int b)
{
	return ((a<b)*a + (!(a<b))*b);
}

int main(void)
{
	printf("\nMaximum of %i and %i is %i\n", 2, 3, opmax(2,3));
	printf("\nMinimum of %i and %i is %i\n", 2, 3, opmin(2,3));
	
	return 0;
}

Coding patterns like this can achieve huge reductions in path counts in embedded signal processing software. Radical limitation of path counts makes critical code much easier to test thoroughly. With one-path designs you can focus on the stronger forms of boundary-value testing without having to worry whether you've achieved full coverage on test metrics based on the control flow graph.


It's quite instructive to compare these coding patterns with the C snippets that technosaurus posted for fast/small static apps. Just goes to show how different are the results you get when you are focusing on different kinds of non-functional requirement. Technosaurus has given us fast code. My efforts focus on maximising the ease of strenuous testing for critical systems.

... we should probably both try to get out a little more ...

[WIckedWitch]

And yet another one:

Write an ISO C conforming program to determine whether char is signed or unsigned. It's not difficult but it tests your understanding of the ISO C standard ...

... oh, and just for good measure, make the program work for any conforming compiler conforming to any version of the ISO C standard - and that's a hint as to the kind of coding trick you need.

Code: Select all

#include <stdio.h>

int main(void)
{
	char 	ch1			= 	(char)1;
	char 	ch2			= 	(char)5;
	int		charbits	=	2;

	while (ch1 != ch2)
	{
		// keep left shifting and adding 1 until ch1 and ch2 are equal
		// increment count of no. of bits by 2 each time round the loop
		// NOTE: *** This assumes that no. of bits in char is even ***
	
		ch1 = (ch1 << 2) + 1;
		ch2 = (ch2 << 2) + 1;
		charbits += 2;
	}
	
	printf("\nPlain char is ");
	
	// now shift ch1 left by 1 to put a 1 in the sign bit position
	// - BUT NOTE THAT ch1 DOES NOT CONTAIN ALL ONES - V.I. -
	// and test whether it now has a negative value - if so plain
	// char is signed and charbits says how many bits a char has
	
	if ((ch1 << 1) < 0)
	{
		printf("signed ");
	}
	else
	{
		printf("unsigned ");
	}
	
	printf("and has %i bits\n", charbits);
	
	return 0;
}
	

The key trick here is not to set all ones in the char variables you are manipulating. The reason for this is that, on targets using 1's complement integer representation, the C standard does not guarantee that something computed to be all ones is not stored as all zeros when actually assigned to a variable ('cos 1's complement has 2 representations of zero).

Happidaze, folks!

[WIckedWitch]

AND FOR THE (POINTLESS) GRAND FINALE:

Not one-path programming but one-statement programming - a function that computes greatest common divisors and contains only a single return statement, all wrapped-up in a program whose main function itself contains only a single return statement.

Code: Select all

#include <stdio.h>

// one-liner function to compute gcd of two positive integers 
int gcd (int p, int q)
{	
	return (p % q == 0 ? q : gcd(q, p%q));	// assumes that p >= q > 0
}

int main(void)
{
	return printf("\ngcd(%i, %i) = %i\n", 35, 21, gcd(35, 21));
}

Wholly unsuitable for anything critical because of the recursion - but yet another merry example of one-x programming, whatever you choose x to be.

[WIckedWitch]

Here's a correction to my post about discovering C predefined macros:

the program should contain the defines;

Code: Select all

#define stringify_aux(s) #s
#define stringify(s) stringify_aux(s)

and then the pattern of each print statement should be;

Code: Select all

printf("<macro-name> = %s\n", stringify(<macro-name>));

Sorry for the cock-up. It comes from using several different languages. In the original incorrect example, I had used the C # operator absent mindedly as though it worked like $ in Tcl. Mea culpa.

I originally wrote this macro-discovery program almost 20 years ago and am now working on a revamp of it with the aim of making it work, as far as possible, for any C compiler on any platform.

Watch this space but don't hold your breath

[nosystemdthanks]

as far as i know 6502 (and its nice to find you here again) the provability of programs was proven to be ultimately unprovable, no?

the halting problem, godels incompleteness theorems-- im just throwing out names, happy to leave this to people who are way better at math.

though whether the proof of unprovability defeats itself and merely shows that its impossible to prove that provability (even if you have your doubts...) yep, godel can take that one off our hands too... actually he cant, but we still cant prove it. and this is exactly why i struggled with math in school... probably.

[WIckedWitch]

as far as i know 6502 (and its nice to find you here again) the provability of programs was proven to be ultimately unprovable, no?

the halting problem, godels incompleteness theorems-- im just throwing out names, happy to leave this to people who are way better at math.

though whether the proof of unprovability defeats itself and merely shows that its impossible to prove that provability (even if you have your doubts...) yep, godel can take that one off our hands too... actually he cant, but we still cant prove it. and this is exactly why i struggled with math in school... probably.

Undecidability/unsolvability theorems generally do not undermine themselves because they work by examining the formal systems that they consider and, with suitably restricted principles of inference, show that the assumption of decidability/solvability leads to a contradiction. This is most easily seen in Turing's 1936 paper about the undecidability of the halting problem and that paper is relatively easy to follow, even by people who don't regard themselves as strong in mathematics.

Godel's proofs are harder but there is a gem of a booklet on them in the (sadly now defunct) Soviet/Russian series called, "The Little Mathematics Library". Getting beyond that into the later work of Tarski, things do get more demanding on the grey cells, so, unless you can't help yourslef, leave it at Turing and Godel.

Modern static analysis tools that try to produce correctness proofs for programs generally rely on restricted logical calculi that have tractable decision problems or on some form of bounded model checking.

SPARK Ada proof tools can now prove freedom from run-time error of 100k LOC in around two hours, AFAI recall. The top-end C static checkers also now use theorem provers but I don't have any verifiable performance data on them.

Th price of provability is that you must stick to a tractably verifiable subset of the programming language used. Obviously the SPARK prover requires restriction to the SPARK Ada language. For C programs you need to restrict to something stricter than MISRA C. Strengthening MISRA C by restricting it to a single-assignment programming style is probably the easiest approach here,

There are public-domain C static analysis tools developed by the Frama-C project in France if anyone is interested.