A Practical Example For HoledRange

Someone asked me a non mathematical example of using the Domain thing, so here goes.

Let's imagine I am writing a network mapper or a load balancer of some description. I have a range of IPs that are available and I want to pick a few from them, or check that an IP is in a white or black list that's handled by ranges.

First I have to define what an IP address is (I went IPV4 because it's shorter): a group of 4 numbers from 0 to 255 (0 and 255 are "special", but it only affects a tiny portion of the code). I want to build them from that representation, strings (because we love strings) and a 32 bits number because that's what it ultimately is:

struct IPAddress {
    var group1: UInt8
    var group2: UInt8
    var group3: UInt8
    var group4: UInt8
    
    init(_ c1: UInt8, _ c2: UInt8, _ c3: UInt8, _ c4: UInt8) {
        group1 = c1
        group2 = c2
        group3 = c3
        group4 = c4
    }
    
    init?(_ s: String) {
        let comps = s.components(separatedBy: ".")
        if comps.count != 4 { return nil }
        if let c1 = UInt8(comps[0]), let c2 = UInt8(comps[1]), let c3 = UInt8(comps[2]), let c4 = UInt8(comps[3]) {
            group1 = c1
            group2 = c2
            group3 = c3
            group4 = c4
        } else {
            return nil
        }
    }
    
    init(_ ip: UInt32) {
        let c1 = ip >> 24
        let c2 = (ip >> 16) & 0x00ff
        let c3 = (ip >> 8) & 0x0000ff
        let c4 = ip & 0x000000ff
        group1 = UInt8(c1)
        group2 = UInt8(c2)
        group3 = UInt8(c3)
        group4 = UInt8(c4)
    }
    
    var asString : String {
        return "\(group1).\(group2).\(group3).\(group4)"
    }
    
    var asUInt32 : UInt32 {
        let c1 = UInt32(group1) << 24
        let c2 = UInt32(group2) << 16
        let c3 = UInt32(group3) << 8
        let c4 = UInt32(group4)
        
        return c1 | c2 | c3 | c4
    }
}

I also included to string and to 32 bits because I could, and because it's generally good practice to be able to output what you accept as input.

If I want to make a domain out of that, they need to be Hashable, and Comparable:

extension IPAddress : Equatable, Comparable, Hashable {
    static func == (lhs : Self, rhs : Self) -> Bool {
        return lhs.group1 == rhs.group1 && lhs.group2 == rhs.group2 && lhs.group2 == rhs.group3 && lhs.group4 == rhs.group4
    }
    static func != (lhs : Self, rhs : Self) -> Bool {
        return !(lhs == rhs)
    }
    static func < (lhs : Self, rhs : Self) -> Bool {
        if lhs.group1 < rhs.group1 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 < rhs.group2 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 == rhs.group2 && lhs.group3 < rhs.group3 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 == rhs.group2 && lhs.group3 == rhs.group3 && lhs.group4 < rhs.group4 { return true }
        else { return false }
    }
    static func <= (lhs : Self, rhs : Self) -> Bool {
        return lhs == rhs || lhs < rhs
    }
    static func > (lhs : Self, rhs : Self) -> Bool {
        if lhs.group1 > rhs.group1 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 > rhs.group2 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 == rhs.group2 && lhs.group3 > rhs.group3 { return true }
        else if lhs.group1 == rhs.group1 && lhs.group2 == rhs.group2 && lhs.group3 == rhs.group3 && lhs.group4 > rhs.group4 { return true }
        else { return false }
        
    }
    static func >= (lhs : Self, rhs : Self) -> Bool {
        return lhs == rhs || lhs > rhs
    }
    
    func hash(into: inout Hasher) {
        into.combine(group1)
        into.combine(group2)
        into.combine(group3)
        into.combine(group4)
    }
    
    var hashValue: Int {
        return Int(self.asUInt32)
    }
}

This stuff isn't quite boilerplate, but not very far from it. Comparing two IP addresses is about comparing the 4 groups of numbers, in order of importance.

Finally, because I want to sample my ranges, I'd like a Randomizable implementation as well, which is more interesting than it seemed at first glance:

extension IPAddress : Randomizable {
    static func randomElement() -> IPAddress? {
        
        let c1 = UInt8.random(in: 1...254)
        let c2 = UInt8.random(in: 1...254)
        let c3 = UInt8.random(in: 1...254)
        let c4 = UInt8.random(in: 1...254)
        
        return IPAddress(c1,c2,c3,c4)
        
    }
    static func randomElement(in r: ClosedRange<IPAddress>) -> IPAddress? {
        let lb = r.lowerBound
        let ub = r.upperBound
        
        if lb == ub { return lb }
        if ub < lb { return nil }
        
        let c1 = UInt8.random(in: lb.group1...ub.group1)
        let c2: UInt8
        let c3 : UInt8
        let c4 : UInt8
        
        if c1 == lb.group1 || c1 == ub.group1 { // special case , because we have to check the more minor parts of the group as well
            if c1 == lb.group1 && c1 == ub.group1 { // same group 1 for upper and lower bounds
                c2 = UInt8.random(in: lb.group2...ub.group2)
            } else if c1 == lb.group1 {
                c2 = UInt8.random(in: lb.group2...254)
            } else { //  if c1 == ub.group1
                c2 = UInt8.random(in: 1...ub.group2)
            }
            // same problem, again
            if c2 == lb.group2 || c2 == ub.group2 {
                if c2 == lb.group2 && c2 == ub.group2 {
                    c3 = UInt8.random(in: lb.group3...ub.group3)
                } else if c2 == lb.group2 {
                    c3 = UInt8.random(in: lb.group3...254)
                } else {
                    c3 = UInt8.random(in: 1...ub.group3)
                }
                // and finally
                if c3 == lb.group3 || c3 == ub.group3 {
                    if c3 == lb.group3 && c3 == ub.group3 {
                        c4 = UInt8.random(in: lb.group4...ub.group4)
                    } else if c3 == lb.group3 {
                        c4 = UInt8.random(in: lb.group4...254)
                    } else {
                        c4 = UInt8.random(in: 1...ub.group4)
                    }
                } else {
                     c4 = UInt8.random(in: 1...254)
                }
            } else {
                c3 = UInt8.random(in: 1...254)
                c4 = UInt8.random(in: 1...254)
            }
        } else {
            c2 = UInt8.random(in: 1...254)
            c3 = UInt8.random(in: 1...254)
            c4 = UInt8.random(in: 1...254)
            
        }
        
        return IPAddress(c1, c2, c3, c4)
    }
}

As for why random IPs don't contain 0 or 255, it's because they are special in some cases and I wanted to spare myself the headache. Note the hierarchy of groups as well for randomization...

Finally a test program:

       if let ip = IPAddress.randomElement(), let ip2 = IPAddress.randomElement() {
            let mi = min(ip,ip2)
            let ma = max(ip,ip2)
            let d = Domain(mi...ma)
            if let ip3 = d.randomSample(5) {
                print("["+ip.asString+";"+ip2.asString+"] => \(ip3.map({ $0.asString }))")
            }
        }

        let d = Domain(IPAddress(192,168,125,1)...IPAddress(192,168,125,10))
        if let ip3 = d.randomSample(5) {
            print("["+d.lowerBound!.asString+";"+d.upperBound!.asString+"] => \(ip3.map({ $0.asString }))")
        }
[58.47.159.20;110.200.52.86] => ["92.196.40.9", "89.184.245.202", "69.19.204.59", "101.41.128.20", "74.231.21.246"]
[192.168.125.1;192.168.125.10] => ["192.168.125.4", "192.168.125.1", "192.168.125.9", "192.168.125.3", "192.168.125.10"]

Seems legit.

An Update on Script Kiddies

Roughly a year later, the script kiddies are still very much active. Over the first 11 months of 2019, there were 8500 attempts (most of them triggering a ban, temporary or otherwise) to access non-existant php files on this blog.

That's 773 attempts a month, a bit more than 23 attempts a day, from distinct IPs.

So, yea, for a site as active as this, as as popular as this, and as critical for a whole lot of services as this, that's definitely a worthwhile investment...

That's a Nice Range! Can I Poke Holes In It?

Because of various Machine Learning and brain teaser problems I focused on, I have been developing for my own use an "extension" to the standard swift type Range that allowed for a very particular behavior: having holes.

TL;DR: Grab the code/package on the github repo

Why?!? 😳

I need this class for two scenarii (that's the plural of scenario, deal with it):

  • Being able to sample continuous data sets (eg "I want a value between 0 and 1, but not between 0.45 and 0.55 because the middle sucks")
  • Being able to reconcile continuous data sets (eg "This tells me it can be between 0 and 1, and this tells me it can be between 10 and 11")

In both instances, I ended up writing a lot of uninteresting and similar code, so I decided to put it all under a single umbrella.

A little bit of personal history and maths 🤕

Practictionners of the dart art known as maths entertain a love/hate relationship with "domains". It's one of these caveats in otherwise universal rules and theorems that restrict the use of all these wonderful tools, and both helps with proofs and hinders usage.

Some functions have a domain definition (eg 1/x exists for every value but x=0. No, infinity isn't the answer), some have a resulting domain (eg is always positive), and some functions have a really weird set of both.

The main problem with maths is that, for a lot of people, it isn't very... permissive, shall we say. There seems to be more "don't"s than "do"s, and the practical application of all these wonderful theorems seems out of reach.

But it's not true that maths is counter-intuitive. I am a firm believer that the "intelligence" we humans exhibit, as opposed to our genetic relatives on the tree of life, is strongly related to our brain's ability to do maths. If I have 4 apples today and eat one per day, I'd better find a supply for apples very shortly, because I won't have any apple left soon. That ability to extrapolate numbers and trends is what differentiates us from, say, our forager ancestors who went looking for food when they were hungry, and didn't plan much ahead.

It is my humble opinion that language exists because of our ability to do maths, and not the other way around. Of course, you might argue that advanced maths is in itself a new language, and quite disconnected from my need to find some apples for next week, but to me, it looks like parallel evolution rather than anything else.

Our brains are wired to count, extrapolate, share, split, combine, and calculate. The rest is a strategy to ensure that I have an infinite supply of apples. Maybe my offspring too, if they behave nicely.

Because of my special condition, maths isn't any less intuitive than driving or drawing. It's just a matter of practice.

The more immediate problem 🙄

Let's say I have a data set that tells me that a variable can be either negative or positive, but that its absolute value can't be beyond 10, and it can't be 0.

[-10;0[ ∪ ]0;10]

That's easy right? Every time I update that variable, I can always use something like:

v = min(10,max(-10,v)) // for constraints
if v == 0 { // ?
}

What if it's something more complicated? Something that exists between 0 and 1 or between 10 and 11, or between 100 and 101?

[0;1] ∪ [10;11] ∪ [100;101]

My list of min and max calls and if/else or switch statements will become very complicated very soon...

What if it's the intersection of two sets of ranges like the one above? Think marketing segmentation, where you are interested in age groups intersected over two different statistical analyses...

What if it's a large range excluding certain values or ranges?

Of course, because we are dealing with computers, we have the other problem to contend with: infinity does not exist

Implementation choices 🤓

In maths, compound ranges are a collection of open and closed ranges linked together by unions. In swift, Range and ClosedRange are distinct unrelated types. Having a collection that contains both is painful for standard operations like unions and merging and symmetric difference, because it implies changing the type of object depending on the operations:

]0;1[ ∩ [-1;0.5] = ]0;0.5]

(please note the changes in inclusion and exclusion of the bounds)

I decided to go with ClosedRange and a touch of excluded values to deal with open ranges. The reasoning behind that is that it also allows me to exclude single values easily, which is one of the main uses of this library.

Most of the standard operations are fairly easy to implement (adding or unioning two ranges is just adding a new item to the collection of ranges, removing ranges means changing the bounds, etc), but they often require an optimizitation pass, which is algorithmically complex: I need to merge overlapping ranges to keep the list as small as possible.

Intersection is pretty straightforward as well: you "just" remove the ranges that aren't common. It is implemented in two steps:

  • find the ranges that share values (overlaps)
  • shrink the result to the common values with min and max

The most interesting one (for me) is the symmetric difference of two ranges: elements that are in either range, but not in both (good old XOR).
The idea here is pretty similar: we have to find the intersection (the common elements) and remove them from the union (all the elements of both ranges).

The problem lies, of course, in the details. Because my Bound type conforms to Comparable and my range needs to satisfy lowerBound <= upperBound, I need to check how the ranges overlap. Is one containing the other? Is one straddling the bound of the other one? Draw it on a piece of paper and you'll see we have a lot of different scenarii (AGAIN!)

What's next? 😱

I don't know. This library works for my current purposes. I will probably continue to add stuff to it as time passes. I have in the back of my mind an idea of how to use this for a constraint solver engine. Maybe.

If you find it useful or want to add stuff to it, feel free!  I'm sure there are some bugs and edge cases I havent' taken into account. I tried to document it fully and provide the unit tests that I thought were appropriate, so if you decide to contribute, please carry on with those two good habits.

A Return To The Island Of Myst

Every time a new version of Blender came out, I kicked its tires and made a Thing™. This time around, with the biggest update in a long long time, I found myself swamped, incapable of finding time to spend time with one of my favorite pieces of software. So I dredged up my own white whale and started working again a few minutes here and there on my hi-res Myst Island.

Why the... why?

I write software for a living. I have done so for two decades straight. I'm quite decent at it. But, see, the fun part is, and has always been, learning new things and challenging myself. And there is one thing I know I will always suck at: drawing. I just don't have the knack for it. Something's not wired properly in my brain and the image I have in my head always ends up like someone very ill tried to scribble something before passing out.

Soooooooo. I know computers, right? And I have images in my head, yea? Why not use the computer to do some drawing?

And it works, more or less. I'm definitely no genius with the tool, but I end up doing things that at least look like something.

Case in point:

The library, from the top of the circuit breaker

Pieces are still missing (spot the tree placeholder), and some stuff definitely need some tweaking (hello supernova in the atrium), but hey, a few hours here or there in a year...

Myst? That old thing?

I wasn't in the biz' back in 1993 when Myst came out. I had to wait quite a few years before I stumbled upon this weird gem. You see, Myst had never been a technical marvel, or a genre-defining game. It's its own thing.

But it's a game that resonates on a personal level for a lot of people at wits' end about the world. You're trapped on an island full of wonderful things, and you have nothing to do. The plot could be as easy as this: you find yourself on an island full of books and memories and mechanisms. You enjoy the simple life there. The end. Or you can just play with the stuff forever, or escape, or try to solve mysteries ,or bring justice for people who have been wronged. There's no time limit. No order to do things. Nothing dangerous.

For some people, it's a boring game. It lacks "action" and "tension". For me, it's comforting.

The gory details

At this point in time, most of the island has been reconstructed. It lacks a bit of vegetation, and a lot of texturing. I'm not happy with the light, nor with the lack of atmosphere.

It sits at 4.5 billion polygons. It's a 400MB blender file (which is not small). And it renders a frame in roughly 1h at 1920x1080. But I can go to 4K (about 3h) or 8K (about 5h) on a whim. Sorta.

It's got PBR textures and subsurface scattering. 95% of the textures are procedural rather than photographic, for enhance-and-zoom glory. It's got details so fine you can almost infinitely zoom on them. It's got 20 or so varieties of plants. And millions of grass blades. And it's a good way to pass an hour away from the worries and the stress. It's kind of home.

The pool and the library

Back To School

With 10.15, my old and dependable workhorse of a machine - a souped up Mac Pro "Cheesegrater" from 2010, upgraded in every possible way - will have to retire. Catalina, Swift UI, and I suspect most of the ML stuff, now require AVX instructions in the processor, and there is no replacement that I could find that would slot in the socket.

I don't consider it to be "planned obsolescence" or anything of this ilk, given that this computer has been my home office's principal work station - and game station, mostly on Kerbal Space Program - for almost a decade. It will live on as my test Linux server, and I will slot a bunch of cheap video cards in it to run my ML farm, so it will probably see another decade of service.

However, the question of replacement arose. You see, I'm an avid Blender enthusiast, and I often run ML stuff on it, which nowadays means I need a decent video card that I can upgrade. The new Mac Pro would be perfect for that, but it's on the expensive side, given that I mostly use the high end capacity of the cards for personal projects or for self-education.

I settled on a 2018 mac mini with tons of ram and a small 512GB internal drive. The 16TB of disks I had now live in a USB 3.1 external bay, and the video card will reside in a eGPU box. That way, if and when I need to change the mac again, All I have to do is change the mac mini... hopefully.

Since the sound setup is of some importance to me (my bird/JBL setup has been with me forever), and I sometimes need to plug old USB/FireWire stuff, I dusted my Belkin Express Dock, and plugged everything in it.

The thing is, every migration is an opportunity for change. I've been very satisfied with my OmniFocus/Tyme combo for task management, but the thing I've always wanted to do and was never able to due to lack of time was managing my Gitlab issues outside of a web browser. I've been working on a couple of projects this summer, with lots of issues on the board, and I have old issues in old projects that I keep finding by accident.

As far as I can tell, there is no reliable way to sync that kind of stuff in an offline fashion. This trend has been going on for a long time, and color me a fossil, but I don't live on the web. I like having a twitter client that still works offline, I like managing my tasks and timers and whatever offline if I need to, "the web" coming in only as a sync service.

This migration (with its cavalcade of old software refusing to work, or working poorly under new management) will force me to write some software to bridge that gap (again). The web is cool and all, but I need unobtrusive, integrated, and performant tools to do my work. 78 opened tabs with IFTTT/Zapier/... integrations to copy data from one service to another won't cut it.