Category: C

My trial by Windows Defender is over

My trial by Windows Defender is over

Posted on by David
EXpression opf irritation!
Image by prettysleepy1 from Pixabay

There’s nothing wrong with this short C program, which is in my ebook and which I was compiling to test it.

#include <stdio.h>

int main() {

	int a = 10;
	for (int i = 0; i < 5; i++) {
		a--;
		printf("i = %d\n", i);
		if (a == 8) break;
	}
}

Nothing wrong, except Windows Defender went ape-shit every time I compiled it! Talk about annoying. This was in Visual Studio. I’m fairly scrupulous about keeping nasties off my PC but if you believed Defender I had some weird Trojan.

I did a search and found an unanswered question on StackOverflow from someone with the same reported trojan. So I answered it!

Thankfully there was an update from Windows Defender last night and they have quashed this false positive. If the worst came to the worst, I’d hop on to Hyper-V and compile it in Ubuntu or Raspberry Pi OS with clang. But still a bit irritating!

A very small sort in C

A very small sort in C

Posted on by David

Tiniest sort in CI came across this article on efforts to make the smallest sort function in C.  Being cynical I did wonder if it would compile and run. I mean 56 bytes is kind of short!

To get it to compile in VS 2019 I had to add a couple of changes, mainly ints and the void. This is it wrapped in a program. The screenshot shows it running and the output at the bottom. Very clever!

The sort function is that void s(… at the top.

 

#include <stdio.h>

void s(int *a, int n) { n-- > 1 ? s(a, n), s(a + 1, n), 
     n = *a, * a = a[1], a[n > * a] = n : 0; }

int arr[10] = { 9,1,2,6,8,11,45,-1,6,4 };
int main() {
	s(arr, 10);
	for (int i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

What I didn’t show you is the number of times Windows defender went ape and declared it a trojan, every time it compiled! My PC is kept pretty bug free and this is a false positive…

A trojan

Looking at Intrinsics in C

Looking at Intrinsics in C

Posted on by David
AVX Registers
From WikiMedia. https://commons.wikimedia.org/wiki/File:AVX_registers.svg

This post probably has the most mystifying title yet. Here’s a little background. Modern CPUs have some hardware that can speed up operations like addition or multiplication by doing them in parallel. The words SIMD (short for Single Instruction Multiple Data) and vectorization apply.

These are very processor specific. Even something like x86-64 CPUS have a whole raft of alphabet soup. SSE, MMX, AVX. Intel even have a website so you can see what instructions are supported with examples in C.

My i5930K CPU supports AVX so if you tick the AVX box on the left hand side of the Intel intrinsics guide, you  can see can there are something like 12,000+ instructions and variants listed. If you tick one of the categories, it filters out the instructions to those applicable to that category.

Click one of the instructions on the right and you’ll see a rough equivalent in C to what it does. Also the header that it is found in, typically

#include <immintrin.h>

which  Visual C++ is happy to compile. An intrinsic is a special C instruction that gives you access to these low level vectorization instructions without you having to drop into assembler.

On a Raspberry Pi, the ARM processor supports a similar type of scheme but it’s called NEON.

If you are interested in finding out more, take a look at Microsoft’s intrinsics documentation which covers both Intel and ARM.

 

Developing a game for the SNES

Developing a game for the SNES

Posted on by David

Yoyo Shjuriken home made SNES gameThis isn’t about me for a change, but I thought it well worth a mention. For those who have never played with a SNES, it’s a Nintendo console from the early 90s. All the games were cartridge based and I loved games like Super Mario World, Legend of Zelda (I finished that) and Secret of Mana.

There are emulators around now’ I have one that runs on an Orange Pi (Chinese brand of Raspberry -Pi compatibles) and if you can get the SNES game roms (mostly illegal BTW!), you can play those games on it.

The reason I mention it, unlike older SNES games which were programmed in 65816 assembler, the developer (Dr Ludos) programmed it in C. Apparently there is only one C compiler that you can use called tcc816 and it needs PVSNESLIB. I’m not sure which of those two links has the better tcc816 though I suspect it’s PVSNESLIB.

This bloke also made his own cartridges which is pretty amazing. I used to know somebody who worked in a firm where they developed SNES games and apparently Nintendo’s quality control was such that the completed game had to include video of 27 hours of play to show that the game wouldn’t crash.  Given the cost of producing the thousands of cartridges, it’s understandable.

Cartridges stopped people copying them and had a higher profit margin, but its kind of ironic now that a 1,000 SNES games can easily fit on a minuscule SD card.

 

 

 

Function pointers in C and understanding them

Function pointers in C and understanding them

Posted on by David
function pointers
Image by 준원 서 from Pixabay

In theory function pointers are straightforward. You have a pointer which is assigned to a function. You then make a call indirectly to that function. But, it’s when the function has parameters passed in and returns things that the definition  gets messy. Reading them is hard enough but trying to get it right when you are writing them can waste a lot of time.

Most days I read various websites and one of those is the C programming forum on reddit.com.  This has either articles or links to articles an one that was recently posted is about C function pointers and includes a very extensive list of definitions and what they mean with nearly 40 different examples of both legal and not legal examples. The examples are handy; just make sure you don’t use an illegal one. It won’t compile!

Progress on the Match Three game

Progress on the Match Three game

Posted on by David

Match Three game Having a week off work has let me work on this game a bit more. I’ve put in about eight hours and it is now correctly dropping.

I’d never programmed one of these before so my first version used a board of pieces plus a secondary array for holding “transitions”. A transition was a struct that held information about two pieces being swapped and the current coordinates of each piece.  It seemed to be quite messy code and was quite buggy with pieces on top of other pieces.

So I then switched to a system where each board cell had a pointer to a struct for a piece (held in an array).  If the piece wasn’t moving the program calculated its pixel coordinates from the board coordinates and drew it there. If it was moving, it would no longer have board coordinates and would use the pixel coordinates to draw it.

That was better but then I thought why not just have the board just be a 2D array of structs with one struct for each piece.

This is the struct for each piece.

 

struct Cell {
	int piece;
	int moving;
	int scEndX, scEndY;
	float scCurrentX, scCurrentY;
	float velY, velX;
	int bdEndX;
	int bdEndY;
	int angle;
	int lock;  //1 = locked. Display padlock
	int size; // used when killing to diminish size
};

SDL2 does rotation very nicely; you don’t need to pre-render shapes just call SDL_RenderCopyEx instead of SDL_RenderCopy and specify the angle and one or two other parameters. When a piece is removed, it animates for about a half-second, rotating and shrinking in place. That’s the purpose of the angle and size fields.

If the lock value is 1 then the piece stays in place and won’t drop. You have to remove the lock by forming a line that includes the locked piece. When the line is removed, all locked pieces in the line remain but without the lock.

So far the game is currently about 800 lines of code. There’s no game level structure, high-score table, sounds, bonus pieces or even a basic piece matching algorithm. I’ve been testing by just randomly removing three vertical or horizontal pieces and then having unlocked pieces above fall down.

This 3rd version does not suffer from the Mexican-wave problem that the first and second version had. Sometimes when a column of pieces moved down, instead of all pieces moving together they moved one-by-one. New pieces get added in when the top row piece finishes dropping away.

So now on with the book and the next part of the game.

An interesting way to find a bug

An interesting way to find a bug

Posted on by David
Disassembly
Image by Free-Photos from Pixabay

Here’s a bit of code with a very subtle bug. It wasn’t ever setting the size file (an int field in a struct). So I took a look at the assembly generated and spotted it. In retrospect it was a bit obvious!

void DoRotateAndDie() {
	for (int i = 0; i < 10; i++) {
		while(1) {
			int x = Random(MAXBOARDWIDTH) - 1;
			int y = Random(MAXBOARDHEIGHT) - 1;
			pBoardPiece ppiece = board[y][x].ppiece;
			if (!ppiece) continue;
			if (ppiece->size != 0) continue; // Not this one
			ppiece->size == 64;
			break;
		}
	}
}

It’s somewhat stupid. The line just before the break is meant to be an assignment but there’s double ==. Stranbgely enough the C compiler In Visual Studio didn’t generate a warning or error. When I put a break point on the line, it hit the break instead.

I was curious to see what code was generated. Here’s the disassembly.


			if (ppiece->size != 0) continue; // Not this one
00124892  mov         eax,dword ptr [ebp-2Ch]  
00124895  cmp         dword ptr [eax+30h],0  
00124899  je          DoRotateAndDie+8Dh (012489Dh)  
0012489B  jmp         DoRotateAndDie+40h (0124850h)  
			ppiece->size == 64;
			break;
0012489D  jmp         DoRotateAndDie+91h (01248A1h)

So it doesn’t generate any code at all for that assignment of 64, it’s just two jmps with no assignment! But fixing it and checking the code this time produces this:

			if (ppiece->size != 0) continue; // Not this one
00144895  cmp         dword ptr [eax+30h],0  
00144899  je          DoRotateAndDie+8Dh (014489Dh)  
0014489B  jmp         DoRotateAndDie+40h (0144850h)  
			ppiece->size = 64;
0014489D  mov         eax,dword ptr [ebp-2Ch]  
001448A0  mov         dword ptr [eax+30h],40h

Those last two lines assign 64 (40h in assembly).

Normally I pick up these type of bugs just by visual inspection. If it isn’t obvious then there are two other techniques to try. The first is get a colleague, or if one isn’t handy a teddy bear or toy duck will do. Now explain to the colleague/teddy bear/duck how the code works. Explicitly say it out loud, do not just think it. It’s amazing how often that works. The process of explaining it forces your brain to do a bit more work then if you just mentally walked the code.

The other method is to disassemble the code and look at it from a different point of view. If the compiler sees the code differently than how you think it should be, it might provide a clue. Here I found out that putting an expression in code instead of a statement, generates no code. Normally with =/== it’s the opposite, putting in an assignment instead of a comparison.

Array vs pointer in C

Array vs pointer in C

Posted on by David
Grid array
Image by Anja🤗#helpinghands #solidarity#stays healthy🙏 from Pixabay

A common pattern (I use the word loosely) in my C programs is to have an array of structs to hold things like asteroids and bullets in the game. There are two ways to process an array:

  1. As an array e.g. asteroids[index].
  2. As a pointer to an individual array element. Asteroid * pAsteroid = &(asteroids[index]); then refer to pAsteroid ->

One of the tents of software design though not that often said is that the easier the code is to read, the easier it is to understand. Programmers spend a lot of time reading code. Anything that lightens the cognitive load is good. I suspect it might also be faster, but not by a great deal.

Of course pointers make some programmers nervous. To me though they simplify the code. There is however another way to simplify the code. Use #define so you might have something like this:

#define table asteroids[index]

So everywhere you have a asteroids[index]., you put in table instead.
This for example from Chapter 36 DrawAsteroids()

	for (int i = 0; i<MAXASTEROIDS; i++) {
		if (asteroids[i].active) {
			numAsteroids++;                    // keep track of how many onscreen
			int sizeIndex = asteroids[i].size; // 0-3
			int asize = sizes[sizeIndex];      // asteroid size 280,140, 70,35
			target.h = asize;
			target.w = asize;
			asteroidRect.h = asize;
			asteroidRect.w = asize;
			asteroidRect.x = asize * asteroids[i].rotdir;
			target.x = (int)asteroids[i].x;
			target.y = (int)asteroids[i].y;

Would become

	for (int i = 0; i<MAXASTEROIDS; i++) {
		if (table.active) {
			numAsteroids++;                    // keep track of how many onscreen
			int sizeIndex = table.size; // 0-3
			int asize = sizes[sizeIndex];      // asteroid size 280,140, 70,35
			target.h = asize;
			target.w = asize;
			asteroidRect.h = asize;
			asteroidRect.w = asize;
			asteroidRect.x = asize * table.rotdir;
			target.x = (int)table.x;
			target.y = (int)table.y;

What do you think?

My encryption code is now live on GitHub

My encryption code is now live on GitHub

Posted on by David
Crptography Word list
Image by tumbledore from Pixabay

I developed Pivot initially on Windows, (a Linux version will follow) though the differences are fairly small. I used the Windows _sopen_s for reading and writing files.  There shouldn’t be too much differen otherwise, though I guess I’ll find out when I compile it on Ubuntu or Raspberry Pi.

The program itself is around 450 lines of C in just one file. It can encrypt around 6 MB/s on my five year old i7 5930K PC and decrypt at around 10 MB/s.

If anyone could try this, I’d be very happy. It has one minor issue that I will resolve. Because it processes files in blocks of 64 bytes, it tends to round the output file when decrypting and adds a few 0s on the end. I will get it sorted

I’ve given it a very liberal MIT license, you can do what you want with it. Instructions on using it are provided on that link to GitHub.

This BTW is the encryption code at the heart of it.

        int bit = 128;
        for (int bi = 0; bi < 8; bi++) {
            for (int b = 0; b < NUMSTREAMS; b++) {
                dataout[b] = (dataout[b] >> 1) | (data[b] & bit);
                data[b] <<= 1;
            }
        }
             
        // Now alter the order of bytes according to the key
        for (int i = 0; i < NUMSTREAMS; i++) {
           data[i] = dataout[_key[i]];
        }

The first double for loop slices 64 bytes into 64 bit streams. It’s pivoting the bits if you like, hence the name. The second for loop is what does the donkey work of encrypting it. It uses a 64 byte key (made up of 64 numbers 0-63- shuffled). As there are 1.2688693e+89 different ways of arranging these 64 numbers, if you lose the key it might take you a while to brute force it!

So I believe that it is an original encryption algorithm, but I am not an expert in cryptography so I might be making a fool of myself! Whether there are any possible attacks against it, I don’t know, but it will be interesting to see!

A fast random number generator in C

A fast random number generator in C

Posted on by David

Random numbersIf you are using RNGs (Random Number Generators) for cryptography then you need one that has been validated for sufficient randomness. For example the libsodium library.

But if you want a fast one for general purpose use, then xoshiro256++ is a fast one.  It’s actually that short that I can list it here. Just call next() and mod it (%) with the highest value+1. E.G. for a dice roll,

int diceroll= (next() %6) +1;

This algorithm is very fast, typically on the order of nano-seconds 10-9 seconds.

#include <stdint.h>
uint64_t rngstate[4];

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

// Returns a Uint64 random number
uint64_t next(void) {
    const uint64_t result = rotl(rngstate[0] + rngstate[3], 23) + rngstate[0];
    const uint64_t t = rngstate[1] << 17;
    rngstate[2] ^= rngstate[0];
    rngstate[3] ^= rngstate[1];
    rngstate[1] ^= rngstate[2];
    rngstate[0] ^= rngstate[3];
    rngstate[2] ^= t;
    rngstate[3] = rotl(rngstate[3], 45);
    return result;
}