27 8 / 2014

Random Maze Generator

Was playing around with generating random mazes

  1. choose a size of the maze, for example 64x64
  2. pick a starting position of the maze, for example 0x0
  3. push that position or “room” into a list called backlog
  4. pick a random room from the backlog, if the backlog is empty go to step 10
  5. if all walls of that room has been set to either open or closed, remove from blacklog and go to step 4
  6. pick a random wall from the room that hasn’t yet been determined as open or closed yet.
  7. if the room on the other side of the wall is in the backlog, set the wall to “closed” and go to step 4
  8. set the wall to open between the two rooms and push the next room into the backlog.
  9. go to step 4
  10. done

You can try a live version of this maze generator at http://creamdog.se/maze/

Anyway here is the quick and dirty javascript


// Array helper function to remove item by reference
Array.prototype.remove = function(item) {
    for(var index = 0; index < this.length; index++) {
        if(this[index] === item) {
            this.splice(index, 1);
            return;
        }
    }
}

// random helper function
function nextInt(max) {
    return Math.floor(Math.random() * max);
}


// Room class, represents a single section of the maze
// Used by Maze class
function Room(x, y) {
    var _self = this;
    // coordinates of room in maze
    _self.x = x;
    _self.y = y;
    // top, right, bottom, left
    // -1 = uninitialized, 0 = open, 1 = closed
    _self.walls = [-1,-1,-1,-1];
    // indicates if any wall has been set to open or closed
    _self.isInitialized = function() {
        return _self.walls[0] >= 0 || _self.walls[1] >= 0 || _self.walls[2] >= 0 || _self.walls[3] >= 0;
    }
    // indicates if all walls has been set to open or closed
    _self.isConstructed = function() {
        return _self.walls[0] >= 0 && _self.walls[1] >= 0 && _self.walls[2] >= 0 && _self.walls[3] >= 0;
    }
}

// Maze class, initialize with the size of the maze you want
function Maze(rows, columns) {

    var _self       = this;
    _self.rows      = rows;
    _self.columns   = columns;
    // this holds all the rooms ina two dimensional array
    // see _self.initialize and _self.construct
    _self.map       = [];

    // initializes the maze map with empty rooms
    _self.initialize = function() {
        for(var y=0;y<_self.rows;y++) {
            _self.map.push([]);
            for(var x=0;x<_self.columns;x++) {
                _self.map[y].push(new Room(x, y));
            }
        }
    }
    
    // constructs the maze
    _self.construct = function() {

        // backlog is an array of unfinished rooms from wich we "grow" the maze
        var backlog = [_self.map[0][0]];

        // keep looping until the backlog is empty
        while(backlog.length > 0) {

            // pick a random room
            var room = backlog[nextInt(backlog.length)];

            // remove room from backlog if all walls have been constructed
            if(room.isConstructed()) {
                backlog.remove(room);
                continue;
            }

            // populate an array with indexes of uninitalized walls for the current room
            var wallIndexes = [];
            for(var i=0;i<room.walls.length;i++) {
                if(room.walls[i] < 0)
                    wallIndexes.push(i);
            }

            // pick a random wall
            var wallIndex = wallIndexes[nextInt(wallIndexes.length)];

            // variable for next room
            var nextRoom = null;

            switch(wallIndex) {
                // top wall
                case 0:
                    // outside of map or picked room is already initialized and in the backlog
                    if(room.y == 0 || _self.map[room.y-1][room.x].isInitialized()) {
                        // set wall to closed
                        room.walls[wallIndex] = 1;
                        continue;
                    }
                    nextRoom = _self.map[room.y-1][room.x];
                break;
                // right wall
                case 1:
                    // outside of map or picked room is already initialized and in the backlog
                    if(room.x == _self.columns - 1 || _self.map[room.y][room.x + 1].isInitialized()) {
                        // set wall to closed
                        room.walls[wallIndex] = 1;
                        continue;
                    }
                    nextRoom = _self.map[room.y][room.x+1];
                break;
                // bottom wall
                case 2:
                    // outside of map or picked room is already initialized and in the backlog
                    if(room.y == _self.rows - 1 || _self.map[room.y+1][room.x].isInitialized()) {
                        // set wall to closed
                        room.walls[wallIndex] = 1;
                        continue;
                    }
                    nextRoom = _self.map[room.y+1][room.x];
                break;
                // left wall
                case 3:
                    // outside of map or picked room is already initialized and in the backlog
                    if(room.x == 0 || _self.map[room.y][room.x-1].isInitialized()) {
                        // set wall to closed
                        room.walls[wallIndex] = 1;
                        continue;
                    }
                    nextRoom = _self.map[room.y][room.x-1];
                break;
                default:
                    throw "dafuc";
                break;
            }

            // find wall index of next room leading to the current room
            var nextRoomWallIndex = 0;
            switch(wallIndex) {
                // top wall -> bottom wall
                case 0:
                    nextRoomWallIndex = 2;
                break;
                // right wall -> left wall
                case 1:
                    nextRoomWallIndex = 3;
                break;
                // bottom wall -> top wall
                case 2:
                    nextRoomWallIndex = 0;
                break;
                // left wall -> right wall
                case 3:
                    nextRoomWallIndex = 1;
                break;
                default:
                    throw "dafuc";
                break;
            }           

            // set walls between rooms to open
            room.walls[wallIndex] = 0;
            nextRoom.walls[nextRoomWallIndex] = 0;
            // add next room to backlog
            backlog.push(nextRoom);
        }

    }

    // prints maze using console.log
    _self.print = function() {
        console.log(new Array(_self.columns+1).join(" _"));
        for(var y=0;y<_self.rows;y++) {
            var str = "";
            for(var x=0;x<_self.columns;x++) {
                str += x == 0 ? "|" : "";
                str += _self.map[y][x].walls[2] == 1 ? "_" : " ";
                str += _self.map[y][x].walls[1] == 1 ? "|" : " ";
            }   
            console.log(str);
        }
    }

    _self.initialize();
    _self.construct();
}

// generate a 32x32 maze and print it
var myAmazingMaze = new Maze(32,32);
myAmazingMaze.print();


.

Running the code will output something like this.

18 8 / 2014

Brute force password cracking using word scoring

For reasons I needed to brute force a piece of plain text that was encrypted using a secret key, as it would be an exhaustive search I would need some way to automatically “score” the text and only display results that where probable candidates.

As I’m not a linguist this was an interesting exercise, I was kind of pressed on time but I can say that I was successful in recovering the plain text in the end.

I devised a quick and dirty approach of brute forcing my way to finding the correct “secret key” and it proved to be fairly effective.

  1. loop through every possible “secret key”
  2. decode text using each secret key
  3. split decoded text into words
  4. score every word where the highest score means it “looks like english”
  5. calculate average score of the text and use that do determine if it is a candidate or not
  6. display results

For this I wrote a quick and dirty JavaScript, below is a “cleaned up” version with an example string being scrambled using a random secret and then brute forced using word scoring.


    // characters valid in readable text, used for scoring
    var validCharacters = [];
    validCharacters.push(/[\w\s\t\n\r\.\,\-\:\;\"\'\'\`\´]+/ig);

    // a list of regular expressions matching invalid character combinations
    // adjust when needed
    var incompatibleCombinations = [];
    incompatibleCombinations.push(/[tqzj][xljpqmngd]/ig);
    incompatibleCombinations.push(/[thqzj][xljpqmgd]/ig);
    incompatibleCombinations.push(/[tqzj][xljpqmngd]/ig);
    incompatibleCombinations.push(/[hmf][wk]/ig);
    incompatibleCombinations.push(/[hf][m]/ig);
    incompatibleCombinations.push(/[n][wmk]/ig);
    incompatibleCombinations.push(/[ljhd][fh]/ig);
    incompatibleCombinations.push(/[ljh][s]/ig);
    incompatibleCombinations.push(/[jfh][gh]/ig);
    incompatibleCombinations.push(/[kf][ds]/ig);
    incompatibleCombinations.push(/[g][f]/ig);
    incompatibleCombinations.push(/[k][j]/ig);
    incompatibleCombinations.push(/[w][w]/ig);
    incompatibleCombinations.push(/[h][r]/ig);
    incompatibleCombinations.push(/[ld][x]/ig);
    incompatibleCombinations.push(/[kim][j]/ig);
    incompatibleCombinations.push(/[ms][q]/ig);
    incompatibleCombinations.push(/[g][d]/ig);
    incompatibleCombinations.push(/[xz][w]/ig);
    incompatibleCombinations.push(/[b][p]/ig);
    incompatibleCombinations.push(/[d][k]/ig);
    incompatibleCombinations.push(/[jk][f]/ig);
    incompatibleCombinations.push(/[srfg][z]/ig);
    incompatibleCombinations.push(/[fkpn][cx]/ig);

    // just an array prototype that matches the supplied input
    // each of its own elements, assumes they are regular expressions
    // return first match
    Array.prototype.findMatch = function(input) {
        for(var i=0;i<this.length;i++) {
            var result = input.match(this[i]);
            if(result != null) {
                return result;
            }
        }
        return null;
    }

    // just returns sum of numbers in array
    Array.prototype.sum = function() {
        return this.length == 0 ? 0 : this.reduce(function(left, right){ return left + right;}, 0);
    }

    // returns a score up to to text.length that indicates
    // the probability that this text is readable by a human
    String.prototype.getScore = function() {
        var score = 0;
        for(var i=0;i<this.length;i++) {
            var char = this[i];
            // determine if this is a valid plain text English character
            if(validCharacters.findMatch(char) == null) {
                //console.log('"'+char+'"', 'invalid character');
                score--;
                continue;
            }
            // we're at the final character of this string
            if(i == this.length - 1) {
                score++;
                continue;
            }
            // peek next character in this string
            var peek = this[i+1];
            var combo = char+peek;
            // evaluate the combination of this character and the next character
            var invalid = incompatibleCombinations.findMatch(combo) != null;
            score += invalid ? -1 : 1;
        }
        return score;
    }

    //fetch next word token from string
    String.prototype.nextWord = function(token) {
        token = typeof token == 'undefined' ? {position:0, word: ''} : token;
        token.word = '';
        for(;token.position<this.length;token.position++) {
            var character = this[token.position];
            
            if(character.match(/[^a-z]/ig) != null) {
                if(token.word.length == 0) {
                    continue;
                } else {
                    return token;
                }
            } else {
                token.word += character;
            }
        }
        return token;
    }

    //fetch an array of words from string
    String.prototype.getWords = function() {
        var words = [];
        var token = this.nextWord();
        do {
            words.push(token.word);
            token = this.nextWord(token);
        } while(token.word.length > 0);  
        return words;
    }

    String.prototype.Scramble = function(secret) {
        var txt = '';
        for(var i=0;i<this.length;i++) {
            txt += String.fromCharCode(this.charCodeAt(i) + secret);
        }
        return txt;
    }

    // example text to scramble using a random 'secret' and then unscramble using brute force
    var txt = "the secret password for our super secret safe is 123456";
    var scrambled = txt.Scramble(Math.floor(Math.random() * 1000));

    // we're guessing that the password is a number between 0 to 1000
    for(var i=0;i<1000;i++) {

        // unscramble
        var unscrambled = scrambled.Scramble(-i);

        // get words
        var words = unscrambled.getWords();

        // we don't care about words shorter than 2 characters
        words = words.filter(function(word) {
            return word.length > 2;
        });

        // we are looking text with more than two words
        if(words.length < 3) {
            continue;
        }

        // get a list of scores for every word
        var scores = words.map(function(word) {
            var score = word.getScore();
            var percentage = (score / word.length) * 100;
            return percentage;
        });

        // we are not interested in displaying results for average scores beneath 98 percent
        var averageScorePercentage = scores.sum() / (words.length == 0 ? 1 : words.length);
        if(averageScorePercentage < 98) {
            continue;
        }

        // print secret, unscrambled text and score
        console.log('secret =', i ,unscrambled, averageScorePercentage);
    }


.

Running the above script will output something like


    PS D:\Dropbox\Projects> node .\scoreText.js
    secret = 42 the secret password for our super secret safe is 123456 100
    secret = 74 THE SECRET PASSWORD FOR OUR SUPER SECRET SAFE IS ◄↕‼¶§▬ 100

.

Running the script with another plain text might result in something like the output below, you can reduce the number of garbage results by adjusting the array of invalid character combinations until you narrow the result down into a manageable amount of candidates.


    PS D:\Dropbox\Projects> node .\scoreText.js
    secret = 717 ?⌂?0sq~0?ut?su0?xu0~?}ru?0⌂v0wq?rqwu0?u??|??0r?0qtz???y~w0?xu0q??q?0⌂v0y~?q|yt0sxq?qs?u?0s⌂}ry~q?y⌂~? 100
    secret = 720 ?|?-pn{-⌂rq?pr-?ur-{?zor⌂-|s-tn⌂ontr-⌂r??y??-o?-nqw???v{t-?ur-n⌂⌂n?-|s-v{?nyvq-pun⌂np?r⌂-p|zov{n?v|{? 100
    secret = 733 you can reduce the number of garbage results by adjusting the array of invalid character combinations 100
    secret = 745 mci¶WUb¶fYXiWY¶h\Y¶biaVYf¶cZ¶[UfVU[Y¶fYgi`hg¶Vm¶UX^igh]b[¶h\Y¶UffUm¶cZ¶]bjU`]X¶W\UfUWhYf¶WcaV]bUh]cbg 100
    secret = 765 YOU CAN REDUCE THE NUMBER OF GARBAGE RESULTS BY ADJUSTING THE ARRAY OF INVALID CHARACTER COMBINATIONS 100
    secret = 777 MCI?75B?F98I79?HIGH=B;?H

.

This just illustrates how easy it is with todays computer power to break low entropy cryptos but it could also be used for other things such as detecting that a user has submitted garbage using a online form.

02 3 / 2014

mallius:

16d7h50m

mallius:

16d7h50m

(via mallius)

Permalink 7,714 notes

15 2 / 2014

About Flappy Bike Saga

Click here to play Flappy Bike Saga

Flappy Bike Saga is a HTML5 (canvas) game I made, took me maybe a day or so. You can play it by clicking on the image above, it should work fine in Firefox, Chrome or IE9/10. I suck at drawing stuff so it is simple vector graphics, also features excellent sound generated with Bfxr

The goal of the game is to bike as far as possible and avoid hitting rocks and trees, getting the highest score possible. The original idea comes from the BMX part of California Games back from when I played it on the Atari 2600. The name is inspired by Flappy Bird and the current King.com spectacle

Stop reading, go play some Flappy Bike Saga :)

26 1 / 2014

Arachnid: Windows GUI development using .NET, Chromium, CefSharp and Nancy

I have done quite a bit of GUI development using .NET and Winforms and lately I’ve been building an application using WPF instead, but it doesn’t fit quite right with me.

What bugs me the most is how bloated and abstract everything is, it is as if you took something already over-engineered and handed it to a engineer who loved over-engineering and refactor stuff into oblivion. This, of course, is my own opinion and I’m sure you can create awesome applications using WPF as easily as you can write awful applications using Clojure or Elixir.

So I started thinking “wouldn’t it be possible to do front end stuff using regular html/javascript and css but still keep the feeling of a native app?”

So I decided to try it out by writing a simple text editor with a front end using html, css and javascript in an embedded browser that communicates with an embedded REST server.

Finding a suitable embedded browser

I started looking around after some good embedded browser solution for .NET and found this one called CefSharp that is a nice Winforms/WPF wrapper for the Chromium Embedded Framework. I did put some effort in finding a suitable wrapper for Mono but didn’t find anything apparently suitable.

Okay, so using CefSharp I could now create a simple Winforms application with a window and a single docked browser window in witch to display my application. CefSharp is available as a convenient nuget package so getting that into your project would be a breeze if it would not be dependent on non-managed binaries from the Chromium Embedded Framework so you will need to download the binary release for windows, unzip, include and mark them as “copy always” in your solution including the “locales” folder.

Nancy as a self hosted server

I’ve done a lot of stuff using Nancy and it is easy as pie to get a self hosted server up and running using Nancy in a .NET application. All you need to do is grab it from nuget using the package Nancy.Hosting.Self and look up the documentation on how to kickstart it.

Next is choosing what port to run the server at, it would be nice to just let the OS choose a random free port to use but I soon realized this would get kind of awkward because of Namespace Reservations so I just picked port 8686 for now.

Of course if you want to do so anyway you can grab a free port using something like


    static int GetFreeTcpPort()
    {
        // passing port 0 lets the OS choose a random free port
        var listener = new TcpListener(IPAddress.Loopback, 0);
        listener.Start();
        var port = ((IPEndPoint)listener.LocalEndpoint).Port;
        listener.Stop();
        return port;
    }

The server is created/started in the Winforms initialization method and a reference to the current form is passed into the server so it can be registered and later used for I/O and dialog stuff.

Front End (GUI stuff)

For the GUI parts of this application I’m using JQuery for general stuff, Twitter Bootstrap for basic layout/components/css and Ace that is a javascript based text editor with syntax highlighting and stuff.

The GUI is pretty basic, a dropdown menu for opening, saving files and exiting the application. All I/O call are AJAX requests to the embedded REST server.

As this application launches an embedded Nancy web server the html/javascript and css stuff can be developed with the help of a regular browser if you want to use firebug or whatever debugger.

Wrapping it up

One thing to keep in mind doing stuff like this is threading, REST requests coming in are all on a different thread from the Winforms/Window instance and can cause troubles when working dialogs and such. This is why we are passing the reference of our Winforms instance when creating the Nancy self hosted server. Using this we can invoke stuff on the Winforms (ui) thread.


    public class Default : NancyModule
    {
        public Default(Form applicationForm)
        {
            Get["/openfile"] = _ =>
            {
                var dialog = new OpenFileDialog();
                var result = applicationForm.Invoke(new Func((d) => d.ShowDialog()), dialog);
                if ((DialogResult)result == DialogResult.OK)
                {
                    var response = (
                    File.Exists(dialog.FileName)
                    ? new StreamResponse(File.OpenRead(dialog.FileName))
                    : Response.AsText(string.Empty)
                    )
                    .WithHeader("X-File-Path", dialog.FileName);
                    return response;
                }
                return Negotiate.WithStatusCode(HttpStatusCode.ClientClosedRequest).WithReasonPhrase("");
            };
        }
    }

.

In the all in all it is fully possible to write a complete native application using these components. All this is missing is a reliable webkit/chromium/gecko wrapper for Mono/GTK# and this would get instant cross platform.

Here is a quick and dirty video of the app running both native and in a browser.

..

Source Code

You can find and download the source for Arachnid demo here

Make sure you set x86 as the target platform when building.

13 1 / 2014

C# Fluently Pattern

Once again I was setting up log4net in a application client I’m writing using in code configuration and thought I would spice it up a bit using a fluent pattern.

Instead of writing some kind of FluentLog4Net library I went for a more generic class wrapper using the pattern:

  • with<some instance>
  • do<some an arbitrary actions with the instance>
  • done<return instance>

At the moment the implementation of this fluent pattern is


    public class Fluently
    {
        public static Fluently<T> With<T>(T obj)
        {
            return Fluently<T>.With(obj);
        }

        public static Fluently With(Func f)
        {
            return Fluently<T>.With(f());
        }
    }

    public class Fluently<T> : Fluently
    {
        private readonly T _obj;
        private Fluently(T obj)
        {
            _obj = obj;
        }

        public static new Fluently<T2> With<T2>(T2 obj)
        {
            return new Fluently<T2>(obj);
        }

        public Fluently<T2> Cast<T2>() where T2 : class
        {
            return new Fluently<T2>(_obj as T2);
        }

        public Fluently<T> Do(Action<T> action)
        {
            action(_obj);
            return this;
        }

        public T Done()
        {
            return _obj;
        }
    }

.

Here is an example of configuring log4net using the Fluently implementation using a rolling file and memory appender.


    public void ApplicationStartup()
    {
        Fluently.With(LogManager.GetRepository() as Hierarchy)
        .Do(repo => repo.Root.AddAppender(
            Fluently.With(new RollingFileAppender())
            .Do(appender => appender.File = "logfile.txt")
            .Do(appender => appender.AppendToFile = true)
            .Do(appender => appender.StaticLogFileName = true)
            .Do(appender => appender.MaxSizeRollBackups = 10)
            .Do(appender => appender.MaximumFileSize = "10MB")
            .Do(appender => appender.RollingStyle = RollingFileAppender.RollingMode.Size)
            .Do(appender => appender.Layout = 
                Fluently.With(new PatternLayout())
                .Do(layout => layout.ConversionPattern = "%date [%thread] %-5level %logger - %message%newline")
                .Do(layout => layout.ActivateOptions())
                .Done())
            .Do(appender => appender.ActivateOptions())
            .Done()))
        .Do(repo => repo.Root.AddAppender(
            Fluently.With(new MemoryAppender())
            .Do(memory => memory.ActivateOptions())
            .Done()))
        .Do(repo => repo.Root.Level = Level.Info)
        .Do(repo => repo.Configured = true)
        .Done();
    }

.

And then you can just go ahead and log stuff as usual using log4net in your application.


    public class Foo
    {
        private static readonly ILog log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);

        public void Bar() 
        {
            log.Info("Foo Bar");
        }
    }

17 11 / 2013

Games are not only fun and play

I was born in 1980, my first video game system was an Atari 2600 and on that system I played some great games. Games like Kangaroo, Vanguard, River Raid, Mario Bros and Defender. From that point on I was hooked and have both owned and played games on the majority of systems released up until now. Systems like MasterSystem, GameGear, Megadrive, Dreamcast, CD32, Jaguar, NES, Gameboy, SNES, Gamecube, GBA, DS, Wii, WiiU, Playstation, PS2, PS3. PS4, (Ouya..) and so on.

The games I played where and is an important part of my life and who I am. You can learn a lot from games but the memories of games also stick with you for the rest of your life and are bound to pop up whilst you least expect it. It can give you a feeling of recognition, approval or fear and disgust. Games are part of what help shape your thoughts and the actions you later take in life, much in the way literature or music does the same.

My opinion is that games are part of what help shape our minds and defines us as much as books, music or movies. They are equally important.

Everyone growing up playing games make them part of their thought process and occasional points of reference throughout their lives.

This is why it is so important that the makers of games realize this and also for those who fight for or against certain content in games.

In conclusion, games are made to be fun but they also impact a lot of lives and the choices we and future generations make.

Games are powerful and they empower us.

08 11 / 2013

A tale of when shit hit the fan

This is a tale from many many years ago, early in my career as a software engineer.

Many years ago I was part of a team of software engineers, project leaders and art directors. Our country was at the verge of a historic shift in information and communication technology.

In order to prepare for the onslaught of the looming demand of virtually every household in the country we where set to the task to construct a product and order management system accompanied by a website and integrated online-shop.

Using all of the latest and stable technologies available in .NET and with a SOA architecture we created something powerful, versatile and in our opinion rock solid. Our system was integrated with several business systems, payment providers, logistic providers and data warehouses. It featured a UX focused web interface for customer support making it super easy to find customers, orders and check the state and status of absolutely everything.

I also wrote a customized retailer application which was distributed to the thousands of retailer locations around the country. This with a authentication and authorization system allowing us to tailor fit who sold what where and for what.

After a few months after endless functionality and penetration testing, everything was put into production and we were pretty confident in this complex system and the punishment it could take.

Only that after a few days the system came crashing down, hard! And we had no idea of why. I was woken up by a phone call in the morning telling me that the shit was failing and fast! When logging on to the webservers I immediately noticed that the CPU was running at 100% and a quick glance at the access logs told me that this was some form of a DDOS attack.

Something else I noticed was that the IP ranges of the source addresses was insanely wide, it was like every single citizen of Sweden (and some outside) where part of this. All of these requests was a GET for a fairly large dynamic resource that wasn’t cached, it was also not part of the website and so it would not be requested by normal website visitors.

Project managers and upper management were screaming over the phones in endless discussions of where blame should be placed and who could fix this. heads where going to roll. I kept out of this as much as I could, trying to figure out what exactly was happening. What was causing all of this? Could it be some kind of distributed attack using a flash banner or something? turns out that it was!

The company we built this system for was running an ad-campaign at the top of one of Swedens most read online newspapers. The ad was a flash-banner that loaded data from our website at every page load and reload on the newspaper site. This of course resulted in millions and millions of requests as every visitor to the newspaper website resulted in a request to our website and a database query.

We temporarily removed the dynamic resource and a few phone calls later the banner was removed and later replaced with a better behaving version. The downtime was around 10 hours.

The system was running fine after this and as far as I know is still in use today.

What did I learn from all of this?

  1. Flash banners are evil
  2. Advertising agencies use shit coders
  3. Our system was not scaled to meet the demand of a million simultaneous users
  4. Never hand out your private phone numbers to project managers
  5. One cool head is better than 10 hot ones

26 10 / 2013

Getting started with Go

Note: go and golang are different names for the same thing.

This describes how to set up a golang project in Windows but you can use this setup on any platform you like that golang supports, just follow this guide and install the requirements in the “What do I need to get started?” section for your operating system and this will work just fine.

You can quickly get your own golang project up and running using the skeleton example.

What is go?

Go is a compiled language created by some guys over at Google in 2007. It has since then matured and gotten somewhat of a following (me included).

The syntax has the feel and looks of a dynamic language but Go is statically-typed. It is compiled into a statically linked native binary with a built in garbage collector. you do not need to worry about allocating and freeing up memory.

It has a built in package management system and the compile times are quite fast. Go is great for multi-threaded applications as it has strong mechanisms for thread safety and concurrency.

Not to mention the excellent work they are doing maintaining the online package documentation http://golang.org/pkg/

In my opinion Go is great for tooling and that is what I use it for.

What do I need to get started?

For my setup I use GNU Make as it is cross platform and your projects will build on Linux/OSX/Windows without modifications and it actually describes all the manual steps for those who are interested. You will also need to install GIT as this example uses a third party package hosted on Github. See https://code.google.com/p/go-wiki/wiki/GoGetTools for the list of all supported version control tools

  1. Go http://golang.org/doc/install
  2. GNU Make http://gnuwin32.sourceforge.net/packages/make.htm
  3. GIT http://git-scm.com/

1) First of all you need to install Go, obviously since this is the whole point of this. Also make sure to add the Go bin/ directory to your system PATH variable. On my system Go installs to C:\Go\bin

2) Secondly you will need to install GNU Make by following the above link. After this is done make sure to add the GNU bin directory to your system PATH. On my computer GNU installs to C:\Program Files (x86)\GnuWin32\bin

3) Lastly, install GIT by following the above link. Like the rest make sure to add the GIT bin/ directory to your system PATH variable. On my system GIT install to C:\Program Files (x86)\Git\bin

Make sure everything is set up correctly by starting a command prompt and verify that it can find the following commands: go, make and git

Setting up your project

You can get this basic skeleton project on github : https://github.com/creamdog/golang.skeleton

The project directory will look like this.


PS D:\Projects\skeleton> ls

    Directory: D:\Projects\skeleton

Mode                LastWriteTime     Length Name
----                -------------     ------ ----
d----        2013-10-26     08:14            src
-a---        2013-10-25     15:10         70 main.go
-a---        2013-10-25     15:10        164 makefile

PS D:\Projects\skeleton>

.

The src/ directory is where you will put your own code that you do not want in main.go. it is also where third party sources ends up and where go looks for additional source files/packages for this project.

The main.go is the application entry point, it contains the main function and is where you set everything up. here is an example:


    package main

    import  (
                "log"
                "github.com/nu7hatch/gouuid"
            )

    func main() {
        uuid, _ := uuid.NewV4()
        log.Printf(uuid.String())
    }


.

As you can see it imports the standard Go log package and the third party package github.com/nu7hatch/gouuid

How do we get that package you say? This is where the makefile comes in.

The makefile is where you set up all your build targets and where you tell Go what to do. here is the example project makefile:



    export GOPATH=$(CURDIR)

    default: main.go
        go build -v -o skeleton.exe

    run: default
        skeleton.exe

    dep-install:
        go get github.com/nu7hatch/gouuid


.

The first line of this makefile is very important. export GOPATH=$(CURDIR) makes sure to set the system variable GOPATH to the current directory before calling any Go functions. This makes sure that go knows where to look for our source code and where to install third party packages for this project.

The default target basically compiles the project using go build with a verbose flag and specific output file.

The run target first compiles and then runs the compiled executable.

The dep-install downloads any third party packages we want for this project using go get

If you want to use additional third party packages you can just add them as a new line under the makefile target dep-install

So, with this you can install all dependencies by calling the make target make dep-install and then build the project by calling make and lastly run the executable by calling make run


    PS D:\Projects\skeleton> make dep-install
    go get github.com/nu7hatch/gouuid
    PS D:\Projects\skeleton> make
    go build -v -o skeleton.exe
    _/D_/Projects/skeleton
    PS D:\Projects\skeleton> make run
    go build -v -o skeleton.exe
    _/D_/Projects/skeleton
    skeleton.exe
    2013/10/26 08:50:32 e730395b-254e-4e43-55aa-b2eb4ba323fd
    PS D:\Projects\skeleton>

.

Wrapping it up

With this basic structure as your launch pad you can go ahead and write awesome applications of your own in golang using your favorite editor. I myself use http://www.sublimetext.com

You can find and download the example skeleton project at my github https://github.com/creamdog/golang.skeleton

14 9 / 2013

generating ten million unique alphanumeric codes in random order without collisions

Thought I should follow up and do some collision checking and stuff regarding my previous post cyclic alphanumeric code generation using quadratic residue

So I wrote the following up real quick and ran it using Node.js and it found no collisions in that set of ten million codes.

sidenote: I really like Node.js to write experiments like this in as it has like no boilerplate and very little ceremony if any at all. /endsidenote

It generates 10 000 000 codes in random order using the fairly large prime number 685420678114303 and outputs them like the following:


    5LCR4QPB7SU8W
    5LANR471ERDC8
    5LAWMK1O0940G
    5LB5HZWALQUOO
    5LBEDFQX78LCW
    5LBN8VLJSQBK4
    5LBROLIV3H6O4
    5LC0K1DHOYXCC
    5LC9FH84AGO0K
    5LCIAX2QVYEOS
    5LCR6CXDHG5C0
    5LANSQF3OEOGC
    5LAWO69Q9WF4K
    5LB5JM4CVE5SS

,

By picking the prime number 685420678114303 I am making sure I can generate 685420678114303 unique codes in seemingly random order. if you need to generate a smaller or larger set of codes you only need to pick any fitting prime.

The prime (P) you pick needs to satisfy P ≡ 3 mod 4

Also, in the example below I generate 10000000 codes from a set of 685420678114303 possible codes starting at index 0. you can start from any index you want or change the number of codes to generate to anything that fits within the range of your chosen prime.

You can also generate say, the first 10 codes (0 to 10) and later generate (10 to 20), the generated codes for each index are always the same based on what prime number you are using.

And here’s the code, enjoy!


    // Shuffled Unique Number Sequence Generator
    // Author: Christian Westman 2013
    // the following javascript program will generate ten million unique codes - 
    // in seemingly random order using quadratic residue permutation.
    // it checks if any generated code has been generated before and throws - 
    // an exception that halts execution if that is the case

    // a nice large prime from http://primes.utm.edu/primes/lists/all.txt
    var prime = 685420678114303;

    // baseCode: used as a base for your generated code
    // should be at least one character longer than the length of (prime) in base 36
    // nice to have if you wish to pad all codes to the same length
    var baseCode = '5A89FG89D5KAL';

    // the magic quadratic residue permutation algorithm
    function permutate(i, prime) {
        var i2 = prime - i;
        if(i2 < 0) {
            return i;
        }
        var num = Math.pow(i2, 2) % prime;
        num = i2 <= prime/2 ? num : prime - num;
        return num;
    }

    // converts num back into a base 10 number
    // snips N+1 characters at the tail of base where N is the length of (prime) in base 36
    // converts the snippet to base 10, adds num and converts result back into base 36
    // returns result padded with head
    function base36addition(prime, base, num) {
        var inputNumber = parseInt(num, 36);
        var head = base.substring(0, base.length-prime.toString(36).length-1);
        var tail = parseInt(base.split("").reverse().join("").substring(0, prime.toString(36).length+1), 36);
        return head + (tail += inputNumber).toString(36).toUpperCase();
    }

    // code below will loop from 0 to ten million -
    // and check if any generated code has been generated before.
    // throw an exception that halts execution if that is the case.
    var collisionObject = {};
    var outputBuffer = [];
    var startIndex = 0;
    var codesToGenerate = 10000000;
    for(var i=startIndex;i<startIndex+codesToGenerate; i++) {
        
        var n36 = permutate(i, prime).toString(36);
        var code = n36.length < baseCode.length ? base36addition(prime, baseCode, n36) : n36.toUpperCase();

        if(collisionObject[code] === true) {
            throw 'collision! code: '+code+', index: '+i;
        } else collisionObject[code] = true;

        outputBuffer.push(i+': '+code);

        if(outputBuffer.length > 32768) {
            console.log(outputBuffer.join('\n'));
            outputBuffer.length = 0;
        }
    }

    // flush buffer to console
    if(outputBuffer.length > 0) {
        console.log(outputBuffer.join('\n'));
        outputBuffer.length = 0;
    }