Arthur's Dev Blog

The blog of a distracted programmer

[arthur-dev]

Cheap and dead simple Arduino game controller

Hey there imaginary readers, so haven’t been very active lately... or ever... but whatever, might as well write this blog now. If this project sounds too easy, it’s because it is. Just something I made in under half an hour in the middle of the night cause I felt like it.

I want to emphasize first and foremost that this controller won’t be a usb keyboard, as I made it with an UNO and I was too lazy to reprogram its

Requirements (total cost: €4.30)

An Arduino UNO (I’m using this knockoff)

Some kind of button pad/shield/something with buttons, I went with the JoySTIck shield V1.a (link here)

Code can be found here

Step 1:

Complicated hardware assembly... we put the shield on the Arduino

Fascinating stuff right there.

Step 2: Arduino programming

We want to be able to control the computer with our board, however we’re using an Arduino UNO, which out of the box only has a normal Serial connection to talk to the computer.

To cause key presses I decided to go for a very simple event based system. Only sending ‘key events’ to the computer as they happened, that is, on key press and key release, and let the computer figure out what that means.

The only problem here is the joystick, which also uses analog pins. Meaning 1024 options. In the end I decided to just map options to 3 values to indicate a resting, positive or negative motion and modeled it like the other buttons.

Step 3: PC based programming (Python)

Since I wanted to create something quick, I hacked together a python script using the lovely pyautogui and pyserial packages, which provide key presses and serial communication respectively.

Installation instructions here:

python3 download page

pyautogui instructions

pyserial instructions

The script simply reads which event happened, and creates a key press based on the mapping present in the script.

Do note that in my script, I open /dev/ttyUSB0, which is the port my arduino connects to. On windows, this would be something like COM1 instead.

Step 4: Playing some sweet games

In the end I just ran retroarch, an emulation front end and specified how it should react to the buttons on my controller.

NOTE: on linux, the pyautogui library hooks into the x-server, meaning that retroarch should pull key events from there, not udev.

[arthur-dev]

Python Tutorials

So I’m helping organise this python based course at my university, and because students requested it, also made some how-to’s on some data structures

Thought I’d share here as well, would be great if it could be used again

https://github.com/WorkOfArtiz/IRPython

Its just the basics of some structures, nothing too fancy

[arthur-dev]

MACRO FUN :D

So I haven’t written anything for some time. So here’s a small fun thing, variadic C macro’s :D (beginners guide to metaprogramming in C)

In C you can define macro’s in the following manner:

#define MACRO_NAME replace_macro_with_this #define WITH_ARGS(arg) replace_macro_with this

The problem however arrises when you want to do something like function overloading like is done in Java/C++/any modern language

Basically if you want 3 functions:

do_thing(void) do_thing(int i) do_thing(char *v)

Now, this can partially be solved with whats called a variadic macro, the exception being the second and third case. We can't distinguish between arguments of different types. We can however select based on different arguments.

As an example I will use a new macro for_range which will transform into something like:

for (var = initial; var < end; var += step)

So we need 4 arguments, but usually we want defaults for this, so that we end up with the next 4 functions.

for_range(var, end) => begin = 0, step = 1 for_range(var, begin, end) => step = 1 for_range(var, begin, end, step)

So let's define them:

#define FOR_RANGE4(Var, Begin, End, Step) for(Var = Begin; Var < End; Var += Step) #define FOR_RANGE3(Var, Begin, End) FOR_RANGE4(Var, Begin, End, 1) #define FOR_RANGE2(Var, End) FOR_RANGE3(Var, 0, End)

Note that this is an easy example, you could ofcourse go wild with the additions to this. For now let's just focus on implementing this with variadic macros.

To do this we create a selection macro

#define GET_MACRO4(_1, _2, _3, _4, Name, ...) Name

Which we will use in the following manner:

#define for_range(...) \ GET_MACRO4(__VA_ARGS__, FOR_RANGE4, FOR_RANGE3, FOR_RANGE2)(__VA_ARGS__)

So to understand this we must first look at variadic macros in general. When it says macro(...) this means the macro can take an arbitrary amount of arguments. But then we need something to access these arguments with. This is what __VA_ARGS__ is for, this expands back.

The way it works is that in GET_MACRO4 the extra arguments push out the FOR_RANGEX arguments. Imagine you have 2 arguments x and y.

This will resolve into:

for_range(x,y) => GET_MACRO4(x, y, FOR_RANGE4, FOR_RANGE3, FOR_RANGE2)(x, y) => FOR_RANGE2(x, y) => FOR_RANGE3(x, 0, y) => FOR_RANGE4(x, 0, y, 1) => for (x = 0; x < y; x += 1)

So this is some basic usage for this

for_range(i, 20) { printf("nr:%d\n", i); }

I'll post some other variadic macro stuff soon as well.

Until then :)

[arthur-dev]

Clever facebook

So Im finally done and thought: “talking’s too much work, I need to outsource”.

And thus, I made a small cleverbot port for facebook conversations (without app codes ofc)

Source available here:

[Facebook cleverbot github](https://gist.github.com/WorkOfArtiz/c874bd3c371805db5710b4ca5363b0fe)

Credits to Facebook, fbchat (python module), Cleverbot and cleverbot (python module)

[cipherface-deactivated20200224]

Illegal numbers

Between the time when the oceans drank Atlantis, and the rise of Silicon Valley, there was an age undreamed of…

Movies were sold on big reels of tape, wound up inside little plastic boxes.

And played on machines called VCRs.

And if you wanted to create a copy of a movie, you could hook two of these machines together and do it with no problem. In fact, it was ruled in a court of law that it was a fair use of someone elses copyrighted movie to make yourself an archival copy, so that if your tape broke, or the machine ‘ate it’ you wouldn’t have to buy another one.

Hollywood didn’t care for this.

So, when the digital age dawned, someone came up with the bright idea of selling movies on DVDs. And one of the big selling points, so far as Hollywood was concerned, was that you could encrypt the data of the movie on the disc, and put hardware to decrypt it in the DVD player, in such a way that it wouldn’t play if two DVD players were hooked together, and so that someone who put a DVD into a computer couldn’t copy it.

Techies and hackers didn’t care for this.

So, they started trying to figure out how to cryptanalyze the DVDs, which were encrypted with a tech called CSS, for Content Scrambling System. And they didn’t have much luck, because crypto is hard, and breaking it is harder. And then one day they caught a lucky break.

Some manufacturers of DVD players, from Taiwan iirc, put out a new product, one of which was bought by a hacker somewhere, who tinkered with it and realized that the makers had made a mistake. They hadn’t properly protected the chips that contained the CSS decryption key, which allowed this guy to get access to it and copy it. He then created a program called DeCSS, which would allow you to put a DVD in a computer and then ‘rip’ the data to your hard drive, then write it to another DVD. He posted it online, and within hours the news, and copies of the key and code, had spread all over the world.

Hollywood flipped their shit over this.

They brought the legal hammer down on this guy, and it ended up in court. He said he had a right, as per the previous Fair Use ruling, regarding VHS tapes, to copy DVDs as well. When people had previously complained that encryption was stripping them of their rights, Hollywood had argued that there was nothing in the law that said they had to make copying easy, and basically challenged them to figure out how to break it. In the court case, Hollywood argued that under a new law that had passed, the Digital Millenium Copyright Act, it was illegal to circumvent an DRM, or Digital Rights Management system. The plaintiffs counter-argued that they hadn’t really reversed engineered anything, that the dumb machines had been built wrong, that they had a right to tinker with it and see how it worked.

So, sitting between these parties was a judge who… to put it kindly, was probably in over his head. Probably some old guy, the kind of guy who still owned a VCR with the clocking blinking 12:00 PM because he didn’t know how to adjust the time. An old grandpa sorta guy. Maybe not a bad guy, just clueless about how tech works. So, when Hollywood argued that there should be some sort of injunction against the spread of the DeCSS software online, that it should be illegal for people to host it, or for others to download it, or to tell people how it worked, or even to link to it, gramps said, “Sure, why not? Here you go, here’s an order that says it’s illegal to possess this software.”

Well, the tech people freaked out about this, because it contradicted a number of already established precedents. Like Phil Zimmermann publishing the source code of PGP and shipping the books containing it to Europe, despite the fact that the encryption tech it contained had been ruled a munition that couldn’t be sold overseas. The precedent, that code was speech, and therefore subject to first amendment protections, seemed to be being thwarted in the DeCSS case. And the tech/hacker community wanted to make it clear that they weren’t going to stand for that.

So, some bright person somewhere, went out and got himself a shirt made, that had the source code of DeCSS printed on it, along with some quote from the order basically saying that it was illegal to buy or own this shirt, then started selling them on his website. This clever idea opened a floodgate of people coming up with unique ways to spread the source code of DeCSS, in a way that was tempting the court to try to stop them, on the grounds that the ruling would then go to a higher court and be turned over on first amendment grounds.

“Take t5’s low byte (AND t5 with two hundred fifty five) to put it

in the ith byte of the vector called k.  Now shift t5 right eight bits;

store the result in t5 again.  Now that’s the last step in the loop.

No sooner have we finished that loop than we’ll start another; no rest

for the wicked nor those innocents whom lawyers serve with paperwork.”

Quote from a long haiku that gives step by step instructions for implementing DeCSS

One of these people, Phil Carmody, raised an interesting argument. He said that software is just numbers. In fact, every piece of software is a single number, that is also a infinite number of numbers (or practically so) as there are nearly an infinite number of mathematical conversions or encodings you can perform on a number. So he wrote a little script version of DeCSS, then converted it to a number, then started to look to see if this number was the same as another somewhere. Was it hidden somewhere in pi? Or the Golden Ratio? What if you doubled it? or added 1 to it?

And after some searching, he found a list of the largest known prime numbers, wherein the 19th largest prime that had been found by that time, was the same as his code for DeCSS. So he posted this info online, and said, “If you go to this website, take this prime number, and save it in a file, then compile it, the output is this piece of software that is illegal to possess, transmit, or share information about.” Here it is, by the way:

485650789657397829309841894694286137707442087351357924019652073668698513401047237446968797439926117510973777701027447528049058831384037549709987909653955227011712157025974666993240226834596619606034851742497735846851885567457025712547499964821941846557100841190862597169479707991520048667099759235960613207259737979936188606316914473588300245336972781813914797955513399949394882899846917836100182597890103160196183503434489568705384520853804584241565482488933380474758711283395989685223254460840897111977127694120795862440547161321005006459820176961771809478113622002723448272249323259547234688002927776497906148129840428345720146348968547169082354737835661972186224969431622716663939055430241564732924855248991225739466548627140482117138124388217717602984125524464744505583462814488335631902725319590439283873764073916891257924055015620889787163375999107887084908159097548019285768451988596305323823490558092032999603234471140776019847163531161713078576084862236370283570104961259568184678596533310077017991614674472549272833486916000647585917462781212690073518309241530106302893295665843662000800476778967984382090797619859493646309380586336721469695975027968771205724996666980561453382074120315933770309949152746918356593762102220068126798273445760938020304479122774980917955938387121000588766689258448700470772552497060444652127130404321182610103591186476662963858495087448497373476861420880529443

Carmody argued, if the ruling that it’s illegal to do these things with the DeCSS software holds up, then it’s also illegal to possess, transmit, or share information about this prime number.  It will become an illegal number. It would have to be redacted from websites, and whatever books it might appear in. People searching for new primes, or any other number, will have to worry about sharing them online, that they are on some list of illegal numbers somewhere. The lists will grow exponentially, as the precedent that this software is forbidden to possess or share, will lead others to demand that software, and numbers, they don’t care for be made illegal as well.

And then… I forget the rest. Whether it was finally ruled in the favor of common sense, or if the case simply petered out and nothing more was ever heard about it. I do know that no one was ever brought up on charges for possessing a number, and DeCSS has been widely available ever since the day it was first posted online (if you’ve ever used a movie ripping software like ffmpeg, you’ve used DeCSS or it’s descendents.)

[memelovingbot]

More info. Also, this is now a crypto history blog, deal with it

[arthur-dev]

Been busy

I have been quiet for quite some time now due to working on my bsc. project (attacking the linux kernel). The project will soon come to an end, and i’ll have time to write some more stuff again.

For now I wanted to share this small fiddle I made (ridiculously low quality bcs tumblrs primary file format, the gif, is still not fully supported)

Source and better quality image as always, on Github

[arthur-dev]

Teads Sponsored Contest

Also on codingame is another challenge, which might land you a job at Teads, some software company in France.

The challenge is simple, you recieve n (a number of edges) and n bi-directional edges in the form “<nr> <nr>“. The graph that it represents is a connected tree (no cycles, every node is reachable).

They want if the optimal root node is chosen in how many steps it can broadcast to any node. With their own picture:

If 1 is chosen as root, it will reach 2 in 1 step, 3 in 2 steps, 4 and 7 in 3 steps and 5,6 and 8 in 4 steps. If 3 is chosen as root however, it will reach every node in just 2 steps.

So when I looked at the problem, I realised that the cost is ceil(longest_path / 2). In my head dijkstra seemed like the best choice, so I went ahead and made a C-implementation of dijkstra using an n x n matrix (n = nr of nodes). I would be able to extract the max path by just taking the max of the matrix.

I then ran it, and to my surprise... too slow with 500 nodes (with tests going until a couple of thousand). And it wasn’t even my memory usage, the algorithm itself took too long. Even after I had optimised it a bit, it was still too slow.

I went back to the drawing board and thought whether the longest path might be calculated more easily because of the nature of the graph. And then I realised, if you just construct a tree with an arbitrary root node n, we can just calculate the max depth of all the children. If we take the 2 children with the maximum depth and add the depths, we’ll get the cost of the longest path.

The cost of the ideal tree is then simply (cost / 2 + cost % 2) or ceil(cost / 2.0)

Code source here

[arthur-dev]

Bender - Algorithmic Complexity

So a while ago I was introduced to this great website with lots of challenges called CodinGame.com. This is one of those challenges.

So the challenge is simple enough, you get a number of 2d-vectors (x and y coordinates). Which resemble the input size n of an algorithm and the time it takes to execute it respectively. They then ask you to classify what complexity class it is with the options: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^2 log n), O(n^3), O(2^n)

What I immediately realized is that the Pearson Coefficient would be wildly useful here. (It measures the correlation between 2 distributions). In the picture below the Pearson coefficients would be 1, -1 and 0

The coeffient itself seemed to be implemented in numpy already in the form numpy.corrcoef(X, Y)[0, 1] see here

If we have a vector of all X values and all Y values, we could in basis create a qqplot and then measure how good the fit is. So just compare the following values:

pearson(X, X * Y) for O(1)

pearson(log(X), Y) for O(log n)

pearson(X, Y) for O(n)

pearson(X * log(X), Y) for O(n log n)

etc.

After this there was a small hickup (also my font seems to have changed), pearson(X, X * Y) always seemed to have a massively high correlation. Since the distribution was constant to begin with, I could easily get away with this modification: pearson(X, X * reverse(Y))

Source is available here

[arthur-dev]

Here we are, I have finally decided I have postponed making a computer science/programming blog for long enough. I will be posting some of my work here (explanations / code / links) and just general stuff. Also this blog is meant mostly for me, if you're interested, please read it but don't expect me responding to every message.