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…

Compatibility out of the box

My current boss wanted to know if the LiveScratcher Script-to-DUI interface would work with Windows Live Messenger 8 too. I’d kept in mind that I wanted it compatible with WLM8, but hadn’t tested it yet. To my suprise, there were only two tiny (non-fatal) errors, and I could get the advertising removal script working with just one extra line.

Behold, the Windows Live Messenger 8 *and* 9 compatible advertisement patch:

//Compact method
function CL_onCreatedElement(resid, root) {
	if (resid=="mainContentResID") {
		var ads=root.FindDescendent("TabsAndAds") || root.FindDescendent("AdBanner");

//Verbose method
function Convo_onCreatedElement(resid, root) {
	if (resid=="convframeresid") {
		var adbannergutter=root.FindDescendent("adbannergutter");
		if (adbannergutter)

//Patches contained in this file
		id: "ContactListAdvert",
		name: "Remove Contact-list Advertisement",
		version: "1.0",
		author: "A. Nonymous",
		website: "http://www.google.com/",
		onCreatedElement: CL_onCreatedElement
		id: "ConvoTextAdvert",
		name: "Remove Conversation Text Advertising",
		version: "1.0",
		author: "A. Nonymous",
		website: "http://www.google.com/",
		onCreatedElement: Convo_onCreatedElement
//Register patches
for (var i in Patches) {

The whole thing started off as an extension to a DUI compatibility layer I wrote for Iminent, but with every hour I stick in I’m falling in love with it more 🙂

Messenger Addons

Since the new version of Messenger 9, none of the major Messenger add-ons have been updated to support it: I myself have attempted to port the current StuffPlug 3 code to WLM9, but concluded that there have been so many changes that for it to be fully compatible I’d have to do a re-write. Patchou had made a quick beta compatible with the earlier WLM9 beta, but he hasn’t posted anything on his own forums since December, and as far as I know his latest version of Plus! is not compatible with the (January released) WLM9 Release Candidate. Messenger Discovery only states “limited support for 9.0”, and to top it all off all current patches (with the notable exception of A-patch, who did a limited version) are not compatible with the new messenger file format.

Basically I think that the comment absorbation made on my earlier post was probably dead on: everyone seems to have moved on to other projects. I’ve seen my own interest in Messenger getting lower at times, resulting in no updates for StuffPlug, but now it’s not only me: even Patchou, the one person who’s kept updating Plus! for ages even when SP and MD would not, seems to be moving on to other projects.

I sometimes wonder how it is that old developers are moving on while no new ones are taking any interest in Messenger anymore. Is messenger development going too slow? too fast? is it because they completely abandoned all the APIs available? Is it because the messenger team has been more and more secretive, and the only real outwards communication being mainly focused on normal users while no longer appealing to developers? I’d really love to hear people’s opinions on this, and would be especially interested in hearing what people at Microsoft think of it. Please, if you read this and have any thoughts about this subject at all, share them with us through the comments below.

On a slightly different note, I’d like to comment on what warmth said in reply to an earlier post. Yes, StuffPlug currently is pretty much dead: the code I have is just no longer compatible with the changes in WLM9, and I’d have to start a re-write sometime. Problem is that most of StuffPlug’s features aren’t really relevant anymore on Messenger 9, and so trying to re-write the entire beast for WLM9 won’t really get me anywhere. I’d much rather start off with something small and build it up from there, much like StuffPlug was in the beginning. So if you have anything, anything at all, that bothers you about Messenger 9, please do tell me, and it might spark that required bit of passion to start working on something again.

As for helping development of other projects; I have actually helped and contributed to both Plus! and MD in the past, and if I can help them again I’d still love to, but setting up an environment for different people to work on the same (hobby) project takes time and effort, and I’m not sure either of us are really ready to make that kind of effort.

So, if you read this: please do leave a comment if you have any views on the whole lack of third-party development on Messenger 9, or if you have something that you’d like to see changed in Messenger 9 by a third-party add-on.

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…