Month: May 2020

Working on the Match Three game

Working on the Match Three game

Match three gameThe second game is Match Three and I’d made some good progress. You can view some .mp4s from earlier this month here. The first one (MatchThree) shows rotations, something I’d never realised SDL is very good at doing. Graphics are from the excellent Dutch website (it’s in English) Kenney.nl.

The second mp4 (transitions) shows some animations. And the MatchThreeDropping shows pieces both being removed (first rotating and shrinking) and pieces dropping. However it also shows a flaw.  Sometimes all the pieces move together, other times (and this is the flaw) it shows them dropping one by one- Mexican wave-like, rather than all moving together.

My original algorithm, which I am now scrapping, had a transitions table. When the space or spaces below a piece became blank, a transition was created which had start and end positions. The piece was removed from the board (a simple 2d array) and reinstated in the board when it had finished moving to the end pixel position.

I think I have a much better method now, I still use a board but each element has a pointer to a piece in a big array of piece structs. I track both the coordinates in the board (0-9,0-9) and in pixels as each piece is 64 x 64. When a space is created in the board, all the pointers are shuffled and each piece is told to move from it’s old pixel position to its new one.

The move algorithm operates purely on the all pieces in the piece array not the board. The flawed algorithm worked on both the board and transition array and was quite messy. Sometimes you have to start with a clean slate than try and fix code that is working correctly.

Array vs pointer in C

Array vs pointer in C

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?

On apt vs apt-get

On apt vs apt-get

Linux
Image by Donald Clark from Pixabay

This is the command you use to update your system, fetch and install software. Some people use apt-get, others plain apt and the two appear interchangeable but they are NOT the same. As it’s making a change to the system, you almost always have to run it via sudo.

They are different?

Well yes. Try these.

apt --help

apt-get --help

Those give different help messages. And as for these:

apt check

apt-get check

It’s curious that apt-get check works, but apt check gives an invalid operation! I’m not sure why they are so similar yet subtly different. If anyone knows, drop me a line.

Having created this post, I subsequently did find out the differences- explained on this page. The simplified version is the apt is a simpler subset and also shows a progress bar when you do sudo apt upgrade. Try sudo apt-get upgrade next time to see it without the progress bar!

 

My encryption code is now live on GitHub

My encryption code is now live on GitHub

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!

Hex Editor for Raspberry-Pi

Hex Editor for Raspberry-Pi

Hex Editor Raspberry PiSometimes you just need to view or maybe a binary file and here I’ve done that on the compiled file for asteroids.

I can’t recommend doing that, but I wanted to try hexedit on the Raspberry Pi. I ran it against the asteroids compiled program and found the text.

If you look I’ve changed the d in starfield (first line of text) to an e. Then I saved it. The program, not unreasonably crashed when run with an error in the errolog.txt file: Couldn’t open images/starfiele.png

You install hexedit with

sudo apt install hexedit

and run with the file you want to view/edit.

hexedit asteroids

To view all the command press F1. It displays the man page for hexedit. Have fun!

A fast random number generator in C

A fast random number generator in C

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;
}
Binary editors – Useful tools

Binary editors – Useful tools

HxD - Binary editorAt some time or other you are going to need a binary editor, to let you look in files and see what they contain.

One I can recommend is HxD which is shown here.

This not only lets you look at the contents of a binary file (in hex and decoded as text)  but you can change them.

It also includes file tools so you can split files, combine them (i.e. append) and securely wipe them. And very handy, the ability to compare two binary files, shown below.

It also lets you export binary files as data  for any of these languages (Pascal,C C#, Java, VisualBasic.net, HTML, rich text and some other formats). Here’s what the top file looks like exported into C.

/* D:\development\pivot\pivot\Debug\l.key (11/05/2020 12:03:32)
StartOffset(h): 00000000, EndOffset(h): 0000003F, Length(h): 00000040 */

unsigned char rawData[64] = {
0x18, 0x3C, 0x2B, 0x11, 0x24, 0x1E, 0x17, 0x26, 0x1C, 0x15, 0x04, 0x19,
0x23, 0x28, 0x08, 0x07, 0x35, 0x0F, 0x34, 0x37, 0x32, 0x05, 0x20, 0x27,
0x3E, 0x0A, 0x3B, 0x2E, 0x1F, 0x29, 0x21, 0x25, 0x2F, 0x14, 0x2D, 0x1A,
0x1D, 0x0C, 0x33, 0x01, 0x39, 0x2A, 0x1B, 0x00, 0x36, 0x06, 0x22, 0x31,
0x38, 0x3A, 0x3D, 0x2C, 0x16, 0x0D, 0x03, 0x00, 0x09, 0x12, 0x13, 0x02,
0x0B, 0x0E, 0x30, 0x10
};

In truth there are many binary file editors. You can find them under hex editors as well. But this is a particularly nice one; recommended.

A remarkable piece of C code

A remarkable piece of C code

What do you think this outputs?

unsigned char c = 241;
long bits = (c * 01001001001ULL & 042104210421ULL) % 017;
printf("Bits = %lu\n",bits);

Remarkably it calculates the number of bits in c and should output “Bits = 5”.

If you don’t believe me, try this program to show all 256 values and the count. If you use c in the for loop instead of i, it never finishes. Well not with Visual C++ 2019!

#include <stdio.h>

int main()
{
    for (int i = 0; i < 256; i++){
        unsigned char c = i % 256;
        long bits = (c * 01001001001ULL & 042104210421ULL) % 017;
        printf("c %d #Bits = %lu\n",c, bits);
    }
    return 0;
}

You can try this out online on one of the various online C compilers.
Count bitsHere’s it on repl.it.

Build Android apps in C

Build Android apps in C

Android phone image
Image by mohamed Hassan from Pixabay

Now this isn’t something I’m going to do but I thought it worth the mention. Android development is done in Java mostly but increasingly in Kotlin. But someone has figured out how to do it in C and published it on GitHub.

You still need to install the free Android Studio to get this to work and I’m not really sure I’d want to write a complete mobile app in C, but it would probably outperform many Java/Kotlin apps.

Using printf type variable parameters in your function

Using printf type variable parameters in your function

The C programming languagI needed this in a bit of debug code. I wanted it to work like printf where there’s a format string containing one or more % format specifications and then write this into a buffer and dump it where ever.

C has a library stdarg which lets you do this. It’s not the most intuitive but it’s definitely worth understanding.

What I’m wanting to do is a function that does something like this (assume s1,s2 and s3 are char *).

sprintf(buffer,"Some string values %s %s %s",s1,s2,s3);
doSomething(buffer);

But in my own function and with the ability to have 0,1,2 or how ever many parameters without having to write a separate function for each. Kind of what printf does.

Here’s the code:

 

#include <stdarg.h>
void op(char* s, ...) {
	char buffer[50];
	va_list argptr;
	va_start(argptr, s);
	vsprintf_s(buffer,sizeof(buffer),s,argptr);
	OutputDebugStringA(buffer);
	va_end(argptr);
}

The … represent the variable number of parameters. it’s called the variadic operator. To access the actual parameters needs the various va_ macros and types. For instance va_list is a type that manages the list of parameters. The va_start macro takes the list and the parameter before the list. vsprintf_s is the Microsoft secure version of vsprintf. Both are the variable parameter equivalent of sprintf/sprintf_s.

OutputDebugString is the Windows debug string function. Finally the va_end tidies up everything.

So you use this just like printf, except the output goes to the Debug channel and can be picked up in Visual Studio (if debugging) or by running the SysInternals free DebugView utility.

Note, the original version of this used OutputDebugString but I found it was outputting gibberish. I correctly guessed that it was linking to OutputDebugStringW ; the MBCS version and changing it to OutputDebugStringA (the ASCII version) fixed it. Something to watch out for on Windows.