I hate leaving my main desktop turned on at night. I’m pretty sure it has something to do with the fact that it’s: a) noisy, b) in the same room I sleep in, and I: c) can’t sleep with a lot of noise or light in my room. This is why I have a seperate computer (without monitor that is) in another room that does all the stuff I’d want to be doing at night. It used to record from the TV channel, but dutch television sucks when it comes to good series, so a while ago I put a torrent client on there. Here’s a description of my old setup, and how I set it up today.
Continue reading My rtorrent setup
Category: Personal
Aho-Corasick with wildcards
A lot of Messenger plugins, addons, and scripts nowadays use some form of memory patching. Some are quick patches like disabling the nudge limit, others like the chat-only name of StuffPlug 3 are much more complicated. But no matter how simple or complicated, they all have the same downsides: the location of the patch changes with almost every new release (even minor ones) of Messenger. Most developers simply keep a small table of locations in different versions, but this forces you to update your software with each and every messenger update. With StuffPlug 3 I opted to write a quick search routine that would search the messenger executable for specific patterns, and would find patch locations using that. This pretty much garantueed StuffPlug to keep working with minor messenger
updates, and sometimes even major updates.
One of the downsides of my implementation in StuffPlug 3 was however that the search routine was pretty simple and as such slow. With each new pattern that needed to be looked for, the time it took to search increased, and at some point this reached a full 3 seconds on my machine (which is pretty high-end compared to my average user). I solved this partially with caching, but for some patterns I needed all hits and caching was not possible. In the end the searching generally took 1 second, or 3 if you just updated messenger. Now even though 1 second (or possibly 5 on slower PCs) doesn’t sound like a lot, it bothered me, and it hasn’t even stopped bothering me. I’ve always wanted to look into other algorithms to speed this up, but generally I had other priorities or didn’t have time at all.
Somehow that changed a week or so ago, when we revisited string matching algorithms in my current course. I just had to try, and I did. As I’m looking for multiple patterns at once, Aho-Corasick should be the ideal approach. One downside: I need wildcards (characters that match anything) in my patterns, and Aho-Corasick wasn’t really made for it. I did see a suggestion somewhere to simply split your search string on the wildcards and search for the constant sub-patterns, but this sounded a bit silly. Especially as there was no motivation about why this was the best approach, I felt I could do better. And today, I thought I had. I had an Aho-Corasick implementation working, with wildcards and everything.
Or so I thought. Yes, the algorithm works. Yes, it can take a wildcard or two. But once you add a few more wildcards, the number of states in the state tree just explodes. With just two memory patterns (38 characters in total, of which 12 wildcards) needed a whopping 7007 nodes, and generating the tree alone took a full 12 seconds. I also tried with all 20 patterns in StuffPlug 3, but that just didn’t seem to finish, ever.
In conclusion: For Aho-Corasick with wildcards, just use the suggested technique of splitting the patterns up. It is possible to adjust the algorithm itself for wildcards, but the number of states needed gets so big that it’s no longer feasible, and will most likely not run on any current computer when you use more than 5 wildcards in total.
I’m not giving up though 🙂 I’m currently working on the Aho-Corasick bit with splitting up, and I have another tree/state-machine based approach in my head that I want to try. At least if I finish this I can truthfully say that I can’t possibly make that part of StuffPlug any faster…
JavaScript madness
There’s quite a lot of people out there that absolutely hate JavaScript or ECMAScript, mostly because the different DOM/DHTML implementations in browsers are often incompatible. Yet it appears there are also people out there that love the dynamic nature of the language itself, and I think I’m becoming one of them. To me it’s a language that allows you to hack small things together relatively easy (when writing some exercises that were supposed to be written in pseudo code in JS a professor noted that it resembled pseudo-code really closely, and I should recommend it to the lecturer), whereas you’re also able to write bigger projects by leveraging the OO capabilities.
Anyway, enough about that, ever since I started using Google’s V8 engine in LiveScratcher for the scripting I’ve been experimenting with JS, and after having done some Data structures exercises with it, I started getting passionate about implementing some data structures in JavaScript. I’ve currently written a Heap (with a PriorityQueue using it), and have just finished an AVLTree implementation (which I will use for a map), and will probably move on to implement all structures from my book 🙂 I’m not sure if I’ll ever release this into the wild, or if it’s even worth releasing into the wild, but I’m pretty proud of it so far, and it forces me to learn more about the data structures involved, as well as keeps my JS skills up to par.
On a different note: I’ve set up a website for LiveScratcher with a wiki and an installer for an alpha version. Check it out at http://www.livescratcher.com/
Atheism gone mad
I know most of the previous posts have been technical, but I started this blog as something where I just write anything that I felt like sharing. That also includes non-technical stuff, and today that includes religion.
I’m not religious. My mother has been raised a protestant, I’m not sure about my dad, but from an early age I’ve basically been raised with a general idea of not doing to someone else what you would not want to happen to yourself. The laws and morals in the Netherlands are highly based on christianity, and I agree with almost everything that’s still part of those. That’s about how far my grasp of religion goes: I’ve never attended church, and I’m just not sure if there’s anything out there. Maybe there is, maybe the christians are right, maybe there is a god. But hey, maybe the buddhists are right, or maybe the muslims. I could’ve picked any of those, but I’d rather just admit that I don’t know and will most likely never know.
Now, lately I’ve been reading a lot of articles on reddit.com, and someone the whole thing about atheism keeps popping up. I totally agree on opposing proposition 8, and I am completely against trying to spread faith. And that’s what most atheists are saying: Just let people make their own decisions, be it gay or heterosexual, christian or muslim, religious or not religious. It’s their own decision, and who the hell are you to judge that ?
What does however piss me off about this whole atheist hype nowadays is how they’re not acting as they’re preaching. For example, I’ve been watching “Religulous” today, and it just pissed me off. Yes, Bill Maher has a valid point. Yes, I totally agree with his point of view. But I don’t like how he’s almost attacking each and every religious person he’s interviewing. Take the jew-turned-to-jesus guy for example[1], he says that he’s seen some miracles and to him that is enough prove that there is in fact a god or a jesus. Surely we can accept that? Not Bill though, he asks what kind of miracles and, instead of simply having a few side-notes or a small monologue afterwards, actually tells the guy that his “bar for miracles is pretty low”. Come on? He believes in God, that’s his constitutional right, just as it’s your right not to, you have every right to disagree with him, but it’s just nasty to attack him like that.
If Religulous would have been a movie looking at christianity, proof of some of the flaws in the bible, and proof of other theories, it would’ve been all right with me.
However, going around publicly ridiculing everyone is something that I, for one, do not condone. Sorry Bill Maher, but this is one hell of a crappy documentary. I highly doubt that it’s done anything else than simply insult a whole lot of people.
[1] If you haven’t seen it, google it, it’s all over the web.
Work and Hobby
When I started StuffPlug, it was my hobby. Messing around with messenger was something I liked doing, and getting a useful program out of it was simply a pleasant side effect. However, lately my interest in messenger hasn’t been what it used to be, and as such no real update on StuffPlug has taken place. I sometimes feel I should try and force myself to work on it just for the sake of getting out a WLM9 compatible version and keeping it alive.
At the same time I’m currently working for Iminent on a temporary consulting job, and today I suddenly realised the whole “but I want StuffPlug to stay a hobby or else it won’t be StuffPlug”-feeling that I’ve carried around since my parents have been pushing me to commercialize it wasn’t just a feeling: Whenever you specifically work on a project, your goal is to get out the product. If you have to cut corners, you’ll do so. If you need some specific research, you’ll probably only research as much as you need. But this goes directly against how StuffPlug started: I’d do some research, mostly for fun, and stumble upon things I could use. Sometimes I’d dig in a little deeper with a specific purpose, but I’ve always just researched stuff for fun, instead of with a specific feature in mind.
I’m doubting now about StuffPlug. Should I just push myself to write something for WLM9 that resembles StuffPlug and try to replicate features, or should I just let it be until something new triggers my interest? I’m afraid that with the first option I’ll never be able to make StuffPlug in what it used to be, simply because I’d be doing it with a completely different mindset…
Making the switch
I love the GNU and Linux philosophy. I love the command-line. Yet, I’m still running Windows Vista.
I’ve tried, honestly. A few days before last year’s Biton LAN Party, I decided to switch to Ubuntu. I liked it at first, but then things started to piss me off: I couldn’t find a proper replacement for Visual Studio, Wine failed to produce any sound, and as soon as I wanted something slightly different, something in Ubuntu would fail. After a day at the LAN without any gaming done, I gave up an just booted to Vista. After all, what’s a LAN party without games ?
At least 6 months have passed since then, and I still long for a Linux desktop. My recent adventures with setting up a MythBuntu server at home and playing around with an ArchLinux Gaming LiveDVD have only made that longing stronger. So I’ve decided that once I’m back in the Netherlands, I’m going to give it another try. And this time slightly more prepared.
So I’ve taken the time to make a little list stating things I should investigate before making the plunge, and I’ll try to tackle them one at a time later on. So here goes:
- Which distribution? Ubuntu sounds simple, but once you start messing in the configuration it breaks horribly. And there are so many around nowadays, why not look a bit further?
- KDE or Gnome? or even XFCE?
- What apps do I rely on, and what are their Linux counterparts?
- If counterparts are not available for a specific app, will it work under Wine or a VM ?
- My hardware should all work (especially my networked HP Laserjet 4000 printer, which was failing last time in Ubuntu)
For now, that’s all I can think of. I’ll try to maintain that todo list, and occasionally post about some of the things I found out.
Introduction
Hi,
If you’re reading this, chances are that you probably already know me. However, for the occasional passer-by that came in through google, here’s a quick introduction.
As of writing this, I am a 21 year old computer programmer. Still busy with my Computer Science study at Utrecht University, although currently I am having a small (5 months) break from my studies and am working for a Parisian company called “Iminent“.
As my study has probably already suggested, I have a passion for programming, and am especially challenged by algorithmic contests like the NWERC (and all related contests like the UKP, BAPC). I also have a deep passion for finding out “how things work”, and as thoroughly enjoy the act of reverse engineering.
Of all the progamming languages I know, I enjoy working in C++ and x86 Assembly the most.
Currently my best known work is an add-on for Windows Live Messenger named StuffPlug, that targets it’s (what I experience as) shortcomings and glitches, and apparently even today it’s downloaded several thousand times per day. Apart from that, I also enjoy working on numerous smaller projects, but they’re too many to all list here.
This blog will be a place for me to share technical stories, challenges, examples, or anything else technical I feel should be public. Oh, and the occasional rambling, probably.
If there is anything I failed to mention in this introductory post, please let me know through a comment. At this time I have comments restricted to registered users to prevent comment-spam, but it shouldn’t be too difficult to register at all. In the future I might opt for guest-posting with a filter to comment-spam…