Stephan Sokolow's Blog

A.K.A.: How to write what human intuition actually expects substring matching to be

While the changes aren’t yet ready to be pushed, I’ve been working on one of my hobby projects quite a bit over the last few days and I just thought I’d share a little something I stumbled upon while implementing a result filter box.

Systems with advanced string searching will often let you choose between prefix or substring matching, but I’ve found that both have glaring flaws when you’re implementing something like a “find as you type” launcher, where the goal is a fast match that’s “good enough”.

With substring matching, you quickly realize that computers are much better than humans at finding substrings in the darndest of places, making substring matching very counter-intuitive. (I get the impression that it has to do with humans thinking in syllables while computers don’t, so it’d be interesting to see how the effect changes in non-alphabetic writing systems, like Kanji or Hangul.)

By contrast, prefix matching is often overly specific and ill-suited to situations where many titles may begin with the same article (A, The, etc.) or the name of a series with many entries. Unfortunately, splitting off the articles, then moving them to the end, as Steam does, also has the potential to trip people up, so there’s no perfect solution.

The solution I developed, almost by accident, is essentially a half-way point between prefix matching and the full-blown keyword-based approach a search engine takes:

Use case-insensitive matching and require that substring matches begin at a word boundary.

This has the following desirable characteristics for a find-as-you-type solution:

• It minimizes the need to press modifier keys, which require costly muscle synchronization:
  • It’s case-insensitive
  • There’s no need for users to quote literals to avoid them being reordered as would be necessary with a full-blown keyword search grammar (ie. “pirates of” won’t match “of pirates”)
• It’s robust against variations in title formatting:
  • A search for “bri” will match both “The Bridge” and “Bridge, The” without also returning spurious results like “Abrix the robot”.
  • A search for “pir” will return “Space Quest III: The Pirates of Pestulon” without concern for how many Space Quest games sort earlier in the results, whether the title was transcribed using “3” or “III”, or “]|[“, whether the subtitle begins with “The”, or whether the separator is “: ” or ” – “.
• It lacks the over-broadness that you find with substring matching, where “pir” will match “Drascula: The Vampire Strikes Back” and “Spirits”.

It’s also simple to implement:

• For typical regexp searching, just prepend \b to the pattern and set the case-insensitive flag. (If your engine lacks \b, then use (^|\s) instead.)
• For literal string matching on top of a regexp engine, just escape the pattern and follow my instructions for a regexp search.
• For CMD.EXE-style wildcard matching, escape the pattern, then replace \? with . and \* with .* before prepending the \b.
• For a manual implementation of literal-string matching on titles with normalized whitespace, just check whether it matches at the beginning (eg. title.lower().startswith(pattern.lower())) and then prepend a space and search within. (eg. (title.lower().index(' ' + pattern.lower())) >= 0)

UPDATE 2016-10-02: The \b word boundary token doesn’t consider parentheses to be part of a word, which I’ve found to be a confusing surprise in day-to-day use, so you’ll want to use (^|\b|\s) instead of \b. This will allow both “(Eng” and “Eng” to match “(English)” in typical usage for maximum intuitiveness.

In case you want to play around with this, here’s a quick sampling of how to regex-escape a string in various popular environments:

• Glib: g_regex_escape_string(pattern_string, length)
• Go: regexp.QuoteMeta(pattern_string)
• Java: java.util.regex.Pattern.quote(pattern_string)
• JavaScript: See escapeRegExp on MDN
• .NET: Regex.Escape(pattern_string) from System.Text.RegularExpressions
• Objective-C and Swift: escapedPattern in NSRegularExpression
• Perl: quotemeta($pattern_string)
• PHP: preg_quote($pattern_string, "/")
• Python: re.escape(pattern_string)
• Qt: QRegExp::escape or QRegularExpression::escape
• Ruby: Regexp.escape(pattern_string)
• Rust: regex::quote(pattern_string)

TL;DR: Install OpenCV-Python, download this script and follow the instructions in the script’s --help output.

While I like The Young Turks, they’ve recently started adding the same two or three carnival barker-esque appeals for subscribers to the end of all of their videos. That gets very annoying very quickly.

Since I don’t believe in rewarding bad behaviour (like forcing avid viewers to see the same couple of annoying ads a million times), I refuse to let them nag me into being a member. However, I still need something to occupy my mind while doing boring tasks, so I needed a solution.

As such, here’s a Python OpenCV script which will find the time offset of the first last occurrence of a frame in a video file (eg. a screenshot of the TYT title card that appears between the content and the ad) in a video file and then write an MPV EDL (Edit Decision List) file which will play only the portion of the video prior to the matched frame.

UPDATE: Hint: Put this script, your videos, and one or more screenshots (to be matched in a fallback chain, sorted by name) into the same folder and you can just double-click it.

I’ve also done the preliminary research to fuzzy-match the audio of those two or three naggy bits in case they decide to try to render this ineffective by moving the title card to the very end… partly because it would also give a more accurate cut point if used with the current clips.

(As is, I tend to lose the last 500 to 1500 milliseconds of actual content due to variations in how how they cut the pieces of each clip together… but, even if I lost an entire clip every now and then, it’d be an acceptable sacrifice to avoid those annoying nags. Current clips are cut together such that stopping at the last frame of the end-title card removes the nag perfectly.)

The Pidgin developers apparently haven’t thought things through very well when it comes to TLS/SSL support because, if you want to connect to a network which uses a self-signed cert, they’ll present you with a permission dialog every time you connect (no “remember” option) and, last time I reported this, they considered it “WONTFIX: self-signed certs are a bug”.

They seem to think that it will force network operators to get proper certificates but, in reality, they don’t have that kind of leverage when every other IRC client allows you to ignore cert errors, so it just forces people to either turn off SSL or desensitizes them to the warning dialogs.

This is especially problematic for me because one of the networks I connect to is encrypted-only, managed by someone who doesn’t trust Let’s Encrypt and, if the Pidgin SSL handshake times out, it remembers the failure rather than re-displaying the prompt on reconnect. Because I have no idea how long the timeout is but it always seems too short, that trained me to punch “allow” on the annoying dialog as quickly as possible without wasting time reading the prompt… never a good sign.

So, today, I’m going to teach you how to get the best of both worlds: How to use stunnel to trick Pidgin into using self-signed SSL without complaining. (And, as a bonus, stunnel makes it easy to verify a self-signed cert without adding it to the system-wide cert store, so it can actually be more secure than the certs the Pidgin developers want you to use.)

First, install stunnel and set it to run on startup. On Debian-based distros like Ubuntu and Mint, this is as simple as running sudo apt-get install stunnel and then setting ENABLED=1 in /etc/default/stunnel4.

Next, we need to write a config file so that, when your client connects to a stunnel server on localhost without encryption, it will make an encrypted connection to the IRC server in question.

The key lines are as follows:

; Maximize security
; NOTE: See the manpage or sample config file for implications
chroot = /var/lib/stunnel4/
setuid = stunnel4
setgid = stunnel4

; Needed for stunnel to work properly
; (Prefix the contents of the chroot line if not using chroot)
pid = /stunnel4.pid

; Disable support for insecure SSLv2 protocol
options = NO_SSLv2

; Define the actual proxy service
[irc-your-network]
client = yes
accept = 127.0.0.1:6612
connect = irc.your-network.com:6697

Now, at this point, you’ve matched what you got from putting up with Pidgin’s security dialog:

1. Put those lines into /etc/stunnel/whatever_you_want.conf
2. Start stunnel (sudo /etc/init.d/stunnel4 start if you’re on Ubuntu 14.04 LTS or older)
3. Set Pidgin to connect to the address in the accept line.

Pidgin will think it’s connecting to an un-encrypted IRC server and the connection will be encrypted between stunnel and the server.

However, we can do one better. If we can get the server certificate in PEM format, we can have stunnel verify it, preventing man-in-the-middle attacks.

The ideal solution would be to download the PEM file through a trusted channel but, as a stop-gap, let’s replicate the “trust whatever we see first” behaviour that SSH uses. Fill in your IRC server’s details in the following command and run it to dump the server cert:

openssl s_client -showcerts -connect irc.your-network.com:6697 </dev/null 2>/dev/null|openssl x509 -outform PEM >your-irc-network.pem

Now, copy the resulting your-irc-network.pem file into /etc/stunnel/ and add the following lines to your whatever_you_want.conf file:

verify=3
CAfile = /etc/stunnel/your-irc-network.pem

You’ll probably also want to add these lines temporarily so you can see what’s going wrong if the verification fails:

debug = 7
output = /stunnel.log

…and, that’s it. Just restart stunnel, reconnect with your IRC client, and, barring verification errors, you should have an encrypted connection which verifies the self-signed certificate.

(I say “should” because, as of this writing, the self-signed cert I’m testing against is expired, so I can’t get all the way through the verification process to confirm.)

TL;DR:

1. Disable 3D acceleration for the guest
2. export CPU_MHZ=2000
3. find ~/.steam/steam/ubuntu12_32/steam-runtime/ -iname '*libstdc++.so*' -execdir mv {} {}.bak \;

Since GOG has introduced GOG Connect, I decided I might as well try to turn some worse-than-worthless unredeemed Steam keys into actual GOG-owned games.

Now, given that I don’t trust the Steam client, that means quarantining it inside a VirtualBox VM that can see the public Internet, but not my LAN.

Unfortunately, whoever wrote it most definitely doesn’t code defensively (It’s like driving defensively. Assume Murphy’s Law and code accordingly.), because the /usr/bin/steam wrapper ignores common options like --help and -v and, in my VM, it exits without showing an error message and without actually starting up.

In order to track down what was going wrong, I had to rely on my skills as a developer:

1. Run file "`which steam`" to verify that I’m dealing with a wrapper script
2. Run bash -x "`which steam`" to get a readout of what’s actually being executed.
3. Run bash -x /home/user/.local/share/Steam/steam.sh to see what’s happening in the actual wrapper.
4. Finally see the “Unable to determine CPU Frequency. Try defining CPU_MHZ.” message.
5. Run export CPU_MHZ=2000; steam and then wait for it to download its updates.
6. Wait several minutes after it stops producing output while it appears to do nothing, then Ctrl+C out of it.
7. Try previous steps again and discover an error message getting covered up by the outer wrapper.
8. Search up results for said error and discover that none of the suggested commands reference paths used in this version of Steam.
9. Manually craft a new version of them: find .steam/steam/ubuntu12_32/steam-runtime/ -iname '*libstdc++.so*' -execdir mv {} {}.bak \;
10. Finally get a helpful error message, advising me to turn off VirtualBox’s 3D acceleration to make Steam work.
11. Restart the VM with 3D acceleration disabled and try re-setting CPU_MHZ and re-running steam.

I have a family member who has grown used to pausing Audacious Media Player with a quick press on their XF86AudioPlay key, but half of what they listen to is video files, so I wrote a quick shell script to work around SMPlayer‘s lack of global hotkey support.

Instructions:

1. Install xdotool (on Debian/Ubuntu/Mint)
2. Put the script somewhere and set it executable
3. Use your desktop’s global hotkey support or a utility like xbindkeys to run the script whenever something like Ctrl+XF86AudioPlay is pressed.

If you want it to do something other than play/pause, the simplest solution is probably to replace space with "$@"  (including quotes) inside the script, save it under a name like smplayer_remote.sh, and then set up associations like these:

• XF86AudioPlay → smplayer_remote.sh space
• XF86AudioRewind → smplayer_remote.sh Left
• XF86AudioForward → smplayer_remote.sh Right

(You can find the keysym names using the xev tool (on Debian/Ubuntu/Mint) and man xdotool will tell you how to specify modifier keys like Ctrl and Alt)

I initially tried to make it behave exactly like a real global hotkey would, but xdotool seems to have an unavoidable race condition and no way to force a 100ms delay after using the windowfocus command… so, instead, this will momentarily switch window focus, then restore whatever you were working on before.

It should be possible to do it properly if I were willing to either patch xdotool or drop down and write against the bare X11 APIs, but I just don’t have the time for either and this is Good Enough™ for the intended use case.