Gynvael’s mission PL-008

This is a solution of a “mission” created by Gynvael Coldwind and presented on the YouTube video. The actual mission text (in polish)
Solution code (in GO this time): https://github.com/jzakrzewski/gyn-pl-008
Translation would be something along this:

SCAN DRONE v0.17.3
CLASSIFIED DATA. FOR YOUR EYES ONLY.

— Operator’s Manual
1. Drone is equipped with a spinning LIDAR.
2. Drone automatically scans each new position with the LIDAR.
3. The scan is made in 10-degree interval; the results are in meters.
4. 0-degree angle means north.
5. There may be some imprecision, especially in tight passages.
6. The LIDAR has 50m range. Everything above that returns “inf”.
7. The scan is made at constant height of 1m above the ground.
8. Drone always moves exactly 1m.
9. Drone reports its position in meters on the W-E and N-S axis. The position
is relative to a (fixed) sender.
10. Drone can only move in the E/W/N/S direction.

— Data Format
SCAN DRONE v0.17.3
DRONES_POSITION_X DRONES_POSITION_Y
DISTANCE_ON_ANGLE_0
DISTANCE_ON_ANGLE_10
DISTANCE_ON_ANGLE_20

DISTANCE_ON_ANGLE_350
MOVE_EAST: ADDRESS_MOVING_EAST_OR_”not possible”
MOVE_WEST: ADDRESS_MOVING_WEST_OR_”not possible”
MOVE_SOUTH: ADDRESS_MOVING_SOUTH_OR_”not possible”
MOVE_NORTH: ADDRESS_MOVING_NORTH_OR_”not possible”

–Data
START

The “START” is actually the link to the first portion of data.

The task (or what do we really have to do)

As in every mission the objective is to find a secret passphrase. So probably the best idea is to visualise the data. This would be our second task.
The first thing to do is to actually get the data.

The tools (and why)

Even though I’d be perfectly capable of writing some C(++) and using curl to get the files (I do such things on a daily basis), I decided to give the go language a try. I’m trying to learn it (I still suck, what is clearly visible in the code) and thought it’d be fun. Additionally I took a sneak peek at KrzaQ’s solution (PL) just to have an idea if I’d have had enough time and I’ve learned that I shouldn’t try to solve it without parallelism 😉 So GO it is.

Downloading

I wanted to achieve parallel download. The problem was that every example I have found had its data set known in advance. Our must be discovered on the fly. My solution involves two channels, a WaitGroup, a Mutex and a map. (Warning! Ugly code ahead):

scans = make(map[string]Scan)
dwQueue = make(chan string, maxParallel*4)

for i := 0; i < maxParallel; i++ {
    go func() {
        downloadWorker(wd)
    }()
}

queueScanDownload("68eb1a7625837e38d55c54dc99257a17.txt")
wg.Wait()

for i := 0; i < maxParallel; i++ {
    dwEnd <- 0
}

So here I basically create all the workers, kick off the download, wait until everything is downloaded and send the signal to the workers to finish. BTW: I had a stupid mistake here where I had only sent 1 item to the dwEnd channel. I have debugged it for an hour trying to figure out why doesn’t it finish…
Anyway, the trickiest part has been to synchronise it correctly.

func downloadWorker(dest string) {
    for {
        select {
        case id := <-dwQueue:
            if err := downloadScan(id, dest); err != nil {
                panic(err)
            }
        case <-dwEnd:
            return
        }
    }
}

func queueScanDownload(id string) {
    mux.Lock()
    _, exists := scans[id]
    if !exists {
        scans[id] = Scan{} // block the spot
    }
    mux.Unlock()
    if !exists {
        wg.Add(1)
        go func() {
            dwQueue <- id
        }() // avoiding deadlock by delegating to yet another coroutine
    }
}

The particularly difficult to place was the incrementing and decrementing the WaitGroup (wg), and adding the id to dwQueue. (FYI: the decrementing of wg must be placed after all the move links from current download are queued.

It has downloaded 187812 scan files. Over 95 megabytes of data…

Anyway, this part has been more like my fight with the new language.

Primary task solution

Parsing the data from the disk has been done in similar manner (also parallel). Nothing really interesting. The last part is mostly some basic geometry math:

pts := make([]point, len(scans)*36) // max points
rad := float64(math.Pi / 180.0)
type sincos struct {
    sin float64
    cos float64
}
sc := make([]sincos, 36)
for i := 0; i < 36; i++ {
    sin, cos := math.Sincos(rad * float64(i*10))
    sc[i] = sincos{sin, cos}
}

var mx float64 = 0.0
var my float64 = 0.0

factor := 1.0
pos := 0
for _, s := range scans {
    for i, d := range s.dist {
        if !math.IsInf(d, 0) {
            p := point{
                x: factor * (s.pos.x + sc[i].sin*d),
                y: factor * (s.pos.y - sc[i].cos*d),
            }
            pts[pos] = p
            pos++
            if p.x > mx {
                mx = p.x
            }
            if p.y > my {
                my = p.y
            }
        }
    }
}

w := int(mx + 10)
h := int(my + 10)
fmt.Println("w: ", w, " h: ", h)
out := make([]byte, w*h)
for _, p := range pts {
    out[int(int(p.y)*w+int(p.x))] = byte(255)
}

err := ioutil.WriteFile("/tmp/map.data", out, 0644)
if err != nil {
    panic(err)
}

fmt.Println("Done")

So I precompute a table of sine and cosine then compute absolute point coordinates. The factor lets me scale the result. At 1.0 (100%) it’s however readable enough.
The hack when computing w and h is there to counteract the problems with float rounding. Without it you’ll get index out of bounds.
The last part just saves a raw bitmap on the disk. Ad because I’m lazy, it’s white-on-black. GIMP rendered this:
map Can you find the password?

Bonus

The bonus task was to create some kind of visualisation. For this. I have an amazing idea ( ;P ) but no time at the moment. I may however do this later, in which case I’ll share it here.

Gynvael’s mission 006 [en]

This time a mission from an English stream. As usual we have to discover a hidden message. This time we got this.

Now I must admit I had a lot of luck here. Being after technical studies with a lot of maths, that looked just like some vectors. So the first thought was to draw them as if they were points.

Since it’s too much work by hand, I’ve written a piece of terrible c code to do it for me (warning – no error checking):

#include <stdio.h>
#include <string.h>

int main(int argc, char** argv) {

    unsigned char buf[25*25];
    memset(buf, 0xff, 25*25);

    FILE* f = fopen(argv[1], "r");
    int x,y;
    while(fscanf(f, "[%d, %d]\n", &x, &y) == 2) {
        buf[25*y + x] = 0x0;
    }
    fclose(f);

    f = fopen("out.data", "w");
    fwrite(buf, 1, 25*25, f);
    fclose(f);

    return 0;
}

When compiled with gcc main.c -o mission006 and run like ./mission006 039e996d075c6ef746d4558fb4bd7f0dfc493198_mission006.data.txt, this will produce a raw bitmap with 8 bits/pixel. The 25*25 comes from a quick inspection of the file – values are exclusively between 0 and 24.
Then I opened it in GIMP, set mode to grey scale and size to 25×25 and saw…

flipped
At which point I grabbed my phone and scanned it. Turns out it encodes:

Mirrored QR? Seriously?!
One thing though. If you know the QR well or if you’re like me and you used the opportunity to do some reading, you’ll notice soon enough that this image is actually flipped horizontally. (Well you could also get a hint from the solution if you’re smarter than me…). It seems that my scanner doesn’t care but to be completely correct one should just flip it in GIMP or change line 12 of the code to say

buf[25*y + 24-x] = 0x0;

instead. Then you’ll get this:

qr

Gynvael’s mission 004 – the weird way ;)

The mission description is here. It’s in Polish, but it doesn’t really matter. We just have to figure out the password from this code:

#include
int check(char*b){char*p;for(p=b;*p;p++);if(((p-b)^42)!=47)return(
~0xffffffff);unsigned long long ch=0x1451723121264133ULL;for(p=b;*
p;p++)ch=((ch<<9)|(ch>>55))^*p;return!!(14422328074577807877ULL==
ch);}int main(void){char buf[1234];scanf("%1233s",buf);puts("nope"
"\0good"+check(buf)*(6-1));return 0;}

which is simply an obfuscated C.
First: formatting:

#include <stdio.h>

int check(char* b)
{
    char* p;
    for ( p = b; *p; p++ )
        ;

    if ( ( ( p - b ) ^ 42 ) != 47 )
        return ( ~0xffffffff );

    unsigned long long ch = 0x1451723121264133ULL;
    for ( p = b; *p; p++ )
        ch = ( ( ch << 9 ) | ( ch >> 55 ) ) ^ *p;

    return !!( 14422328074577807877ULL == ch );
}

int main(void)
{
    char buf[1234];
    scanf("%1233s", buf);
    puts( "nope\0good" + check( buf ) * ( 6 - 1 ) );
    return 0;
}

Now things that are pure noise:

#include <stdio.h>
#include <string.h>

int check(char* b)
{
    if ( ( strlen( b ) ^ 42 ) != 47 )
        return 0;

    unsigned long long ch = 0x1451723121264133ULL;
    for ( char* p = b; *p; p++ )
        ch = ( ( ch << 9 ) | ( ch >> 55 ) ) ^ *p;

    return 0xC82666F8975A8A05ULL == ch;
}

int main(void)
{
    char buf[1234];
    scanf("%1233s", buf);
    puts( "nope\0good" + check( buf ) * 5 );
    return 0;
}

Let's check what the return value of check should be. We can rewrite this line:

puts( "nope\0good" + check( buf ) * 5 );

to

puts( check( buf ) == 1 ? "good" : "nope" );

so it returns 1 for a good password.
In the check itself we have two return statements. The first one is a length restriction. There’s some nice XOR; and what do we know about XOR?
a ^ b = c ==&gt; c ^ b = a, thus our password length is 47 ^ 42 = 5.

What about the bit shifting magic? That one came to me as a surprise. I took a look at the generated assembly and it’s simply a rotate-left by 9 bits. So each time we rotate the magic value by 9 and then XOR the last 8 bits (sizeof char). At the end we check if the result is another magic constant.

Because we never modify the same bits twice we can just rotate ch once by 45 bits. With that knowledge we can rewrite the code a bit:

int check(char* b)
{
    if ( strlen( b ) != 5 )
        return 0;

    unsigned long long ch = 0xC826628A2E462424ULL;
    unsigned long long pw = 0x0ULL;

    for ( char* p = b; *p; p++ )
        pw = ( ( pw << 9 ) | *p );

    return ( pw ^ ch ) == 0xC82666F8975A8A05ULL;
}

And there is the XOR! Time to recover the password from the already known formula:

#include <stdio.h>

int main(void)
{
    unsigned long long ch    = 0xC826628A2E462424ULL;
    unsigned long long magic = 0xC82666F8975A8A05ULL;
    unsigned long long pw = ( magic ^ ch );
    for( int i = 45; i >= 0; i -= 9 )
        putchar( (char)(pw >> i) );

    return 0;
}

This code prints GWGW! when executed.

VLC on Gentoo and no subtitles

gentoo_vlc_hutThe VLC media player is both – hated and loved. I tend to like it because it plays a lot of different formats and broken files pretty well in my experience.

Recently I set up a new Gentoo-based PC. I’ve emerged vlc with the recommended flags (see VLC media player for Gentoo Linux) and everything seemd well till I tried to play something with subtitles. It didn’t really matter if those were SRT, MicroDVD or any other. They just didn’t work. Funny thing though – the OSD as such worked. The file name has been displayed on playback start. As was other information like time, volume, etc. Continue reading

Raspberry Pi as remote print and scan server for SCX-4200

I am a happy owner of a Samsung SCX-4200 printer/scanner combo. It’s already pretty old but serves me well and I’m not going to replace it only because of its age.
However useful it is for me, I have no place on my desk for it. It’s simply too big. So I’ve put in the corner of my room with other stuff. The downside was wherever I wanted to print or scan something, I had to take my laptop there to connect it via USB cable. Enough is enough, let’s make the Raspberry Pi useful 😉
Continue reading

Migrating Raspberry Pi to version 2.

Logo of Raspberry Pi 2Back in 2012 I’ve bought myself Raspberry Pi model B. I’m not really keen on playing with electronics and all those GPIO pins could be non-existent as far as I’m concerned. The only thing I wanted was a low-power linux server to manage my network and provide some additional services. My router has been pretty much useless as it forced me to choose between static IP configuration and DHCP. With RPi I’ve got both and more.

Just about a week ago I’ve read about Raspberry Pi v2. has been released. Quad-core and 1 GB of RAM should make my GitLab installation usable at the very least. Without much thinking I’ve bought it and today I’ve decided to replace the hardware.
Continue reading