The problem

I wanted to have a look at Melodia, a public-domain textbook to learn sight-reading. I thought it would be nice to read Melodia on an ebook reader, but the available PDF is a scan of a paper copy in 7 by 10 inches, and my Kobo Glo screen is only around 3.5 by 4.8 inches:

The obvious solution is to scale it down, but it would be too small to read. So wouldn't it be better if we could split each page into parts of the right size?

Of course, it's not that simple. When reading music you want to follow the lines from left to right, then from top to bottom. It's exactly like text, where the right way to reflow a page is:

One way to do this would be to do optical music recognition to transcribe the whole partition, and then re-render it to the right format. But that's not so fun, and I don't know if there are good implementations for this task which I can easily install (i.e., not expensive and Windows-only programs). Instead, let's go for a more ad-hoc but much simpler approach.

To split music, you need to be able to recognize the separate lines (i.e., staves, or systems). Then you need to find a way to cut them: typically at a measure bar line, to avoid splitting inside a bar. More subtly, for the result to look good, you want each split line in the output page to have exactly the same length, even if the bars on the input page did not, otherwise the result will look jagged. The naive solution would be to stretch each line, but it will look awful and distorted. Instead, you want to do something like seam carving: scale the "uninteresting parts" (e.g., empty space on the staff) while leaving the "important stuff" (notes, alterations, etc.) untouched. See:

What's more, because scaling is undesirable, you need to decide where to cut among all the bar lines. The goal is to avoid having lines that are too small and need to be resized by a large factor (leaving too much empty space). The naive way is to fit as many bars as possible on each line, but this can leave you with very short lines that are hard to format properly. This is a variant of the word wrapping problem

The solution

So I wrote some code to take care of these tasks for me. I called it songflower, as in something that (re)flows songs. The code is here. I don't expect it to be usable without significant tweaking, but there is a README and some documentation that allow to play with it and tweak the parameters.

So what does it do exactly? Glad you asked. :) Here are the steps:

• Burst the input PDF into a collection of bitmap images, one for each page
• Split each page into one image for each line on the page (i.e., staves, or systems)
• Split each line into a chunk, i.e., a sequence of consecutive bars having exactly the prescribed width. This involves:
  • Finding the bar lines
  • Splitting bars into chunks intelligently
  • Stretching the chunks to have exactly the right width
• Combine the chunks into output pages (laying them out nicely on the page) and combine those into the output PDF.

The first step is easy with convert from ImageMagick, although it is pretty long and for some reason and takes lots of RAM. The last step is also pretty routine: you just greedily put as many chunks on each page as you can, you need to compute the right spacing between the chunks to fill all available height in the layout, and then combining the result into a PDF is just convert again, plus pdftk. The harder steps are the two middle steps:

Step 1: Splitting pages into lines

This step is comparatively easy. The program just looks for rows of the picture that consist mostly of white pixels. It then smooths this by merging together consecutive white lines that are sufficiently close (to have some resilience to noise). Last, it cuts at the largest sets of consecutive white lines, up to some threshold. This is how the program sees a page of Melodia:

The yellow lines are the lines detected as white space, and the red lines are where the program decided to cut (there were enough consecutive empty lines). The green lines were not used to cut because they yielded a line that was too short. The result here is pretty OK, except that the program was a bit too eager and cut away a tie connecting two dotted minims on the 4th staff from the bottom. Apart from small problems of this kind, the approach is pretty robust on the Melodia dataset. The main problems involve slurs, staves that are too close together on a page, and lyrics which often get removed (this is fine for my needs but it might not be for yours).

Step 2: Splitting lines into chunks

This is the trickier part. Let's focus on the first line above:

This is how the program sees it:

OK, this requires some explaining. The program looks at columns of pixels and computes two things: the height of the column, and the weight of the column (smoothed over a small window). The height is just the maximal vertical distance between two non-white pixels on the column, and the weight is the sum of the pixel's distance to black. We are especially interested in columns that both have a minimal height and a minimal weight (excluding some outliers, with some thresholds, etc). Intuitively, these columns are points on the staff where nothing is happening. These are the purple parts on the picture above: the cyan parts have small weight but not height, the pink parts have small height but not weight, and the black parts satisfy neither criterion. (Sorry, these ugly colors are just what was the easiest to produce -- it's a debug output.)

We can see that both criteria are useful: if we look only at the height (pink and purple) then we still include columns of staff that are not empty. If we look only at weight, then we get fooled by some columns that include part of a note (bars 2 and 3). But when we look at both criteria, the purple parts are a reasonable approximation of the parts of the score where nothing is happening. (Note that floating stuff, e.g., the numbers 168 and 169, prevent parts of the staff from being detected as empty.)

Now, it's good to find where nothing is happening, but where can we find bar lines? The idea is that a bar line is a part of the staff which:

• is of minimal height but not of minimal weight (pink)
• is surrounded to the left and right by points of minimal height and weight (purple)
• is narrow, i.e., not too many pixels wide
• contains a column with high weight, i.e., significantly higher (by some factor) than the weight of columns where nothing happens.

This is a complicated collection of criteria, but I didn't have luck with more naive approaches. My initial idea was just to look for columns having a minimal height and high weight, but this is fooled by note stems, e.g., of the last crochet of bar 3. Still, this criterion is fragile, especially with minims as their notehead is sometimes not heavy enough to be detected; and you have to set some parameters correctly.

On the example above, this approach correctly detects all bars (vertical lines), except the double bar at the middle. The blue bar is where the program decided to cut the line (to fit the width I had requested), and the red lines were possible cuts that were not used. Here the choice of a cut is simple (take the closest to the middle), but in more complicated cases the program will try all possible approaches.

The last thing to do is stretching the chunks to the left and right of the blue line so that they have the exact same length -- which they currently don't (the left chunk is much longer than the right chunk). To do this, the program simply scales all purple regions. We get this (without the colors):

It's not perfect: the first bar is a bit off, because the program did not stretch around the "168".¹ Also, in a proper edition, the key would be repeated at the beginning of the second line, which my program doesn't dot, but well... Other than that, I think it's pretty seamless, and hard to notice that there was some work involved in bringing these two lines to the same width.

Of course, this example is a case where the program doesn't perform too badly. Sometimes, it has a harder time doing something reasonable:

One could think of more elaborate approaches to avoid problems, e.g., trying to identify floating things like "168" or lyrics or other things, process the staff without taking them into account, and then attach them back to the right place afterwards...

Wrapping up

There are a lot of corner cases and other subtleties in the code which I didn't get into. For instance, when the program doesn't detect enough bar lines, then it will fall back on cutting on spaces detected to be empty -- this is usually less disruptive. Performance is also an issue, as the code is in Python: to speed things up is, I use GNU parallel to process multiple pages and lines simultaneously.

Anyway: applying the process to Melodia, fixing a few glitches by tweaking the parameters on some pages (and adding a title, removing junk, etc.), I got the reflowed PDF I wanted. It's not perfect at all, and some of the later pages are quite wild, but well, I'll see to it when/if I get there. :)

You should be able at least to reflow Melodia to a different format by grabbing the code and running it. Other than that, I'd be happy to know if you have any luck applying this code to other files! I'm also interested in patches or ideas if you also find it fun to hack on this.

I had been meaning for a long time to try out Wayland, which is designed as a modern replacement for the Linux graphical stack, the X Window System. The main selling point of Wayland for me is that it is better designed in terms of security: processes don't have access to each other's events, unlike X where any process can listen to all events that happen on the server. The lack of security in the design of X is a real problem: no matter which other kind of sandboxing you put in place (e.g., separate users, containers, etc.), you can't prevent a rogue process (e.g., malicious JavaScript using a browser security vulnerability) to access all events and, e.g., log all keystrokes that happen elsewhere in the session.

It is possible to sandbox processes in X by running an X server within the X server, e.g., Xnest, or more commonly Xpra. The way this works is that Xpra acts both as a client for the running X server, and as an X server in which you can run the process that you wish to sandbox: Xpra does not give the running process access to all events of the X server, but only gives it the events that it needs. This is what is done by Subuser, and it is what I did in my old setup to sandbox Skype. However, this is a rather ugly hack, and my experience the performance of the applications running inside Xpra has always been quite bad -- usable for Skype, but not really usable for something like a web browser. (I had tested this long ago by compiling the latest version of Xpra, and I just tested it again with the version packaged by Debian: video playback in a Web browser is not smooth.)

Another solution is what is done by QubesOS, which I haven't tested yet, but seems difficult to separate from the rest of their system (which looks interesting, but I'm not ready to migrate there yet). They are also thinking about using Wayland.

Anyway, Wayland looked like a reasonable solution to the problem, especially as the window manager that I use, i3, has been faithfully adapted to Wayland: sway. So I tried it out, and after some hours it seems to be fairly usable (using the Wayland packaged by Debian testing). This blogpost documents what I did.

Installing sway and its dependencies

Use apt-get to install all requisite dependencies for sway, and its dependency wlroots. The list of the packages that I installed for this is here. We will also need a recent version of libjson-c, because the one packaged by Debian is too old.

Essentially it should be something like:

mkdir ~/apps
cd apps

git clone 'https://github.com/json-c/json-c'
cd json-c
sh autogen.sh
./configure
make
sudo make install
cd ..

git clone 'https://github.com/swaywm/wlroots'
cd wlroots
meson build
ninja -C build
sudo ninja -C build install
cd ..

git clone 'https://github.com/swaywm/sway'
cd sway
meson build
ninja -C build
sudo ninja -C build install

You can then copy your i3 config to sway:

mkdir -p ~/.config/sway
cp ~/.config/{i3,sway}/config

And then you can try running sway in a TTY and see what happens. For me, everything almost worked out of the box: I document here what needs to be adapted. You can also have a look at my sway configuration, with only minimal changes relative to my i3 configuration,

For some reason the font in window titles and in the sway bar was wrong, but this was simply fixed by changing the font names in the config file to "Terminus". I think this is essentially the only change I had to make. When using sway there are some very small differences with i3 (e.g., the formatting of window title bars, or the precise behavior), but honestly the difference is hardly noticeable and I'm rather impressed at how close the adaptation is.

Fixing the keyboard layout

I have my custom keyboard which adapts the US Dvorak layout with some key combinations to write French accented characters. I used to load it with xkbcomp, but this no longer works with Wayland.

What works instead is to write a keyboard description like this and put it in ~/.xkb/symbols. Note that this includes some external files, some of which are in in the systemwide /usr/share/X11/xkb/symbols folder, and others are applying my customizations (see, e.g., this) and they should also go in ~/.xkb/symbols. For some reason, trying to load this keyboard description by running setxkbmap a3nm will not work. However, it works to load the keyboard description in sway, by running XKB_DEFAULT_LAYOUT=a3nm sway or editing the sway configuration file to add an input * block containing the xkb_layout a3nm directive, i.e.:

input * {
  repeat_delay 250
  repeat_rate 50
  xkb_layout a3nm
}

Note that this is also where I configure the keyboard repeat delay and rate.

Many thanks to ManDay for helping me figure this out on the #sway IRC channel.

Switching to apps with native support for Wayland

Most applications do not yet support Wayland, but there is a compatibility layer to run them on Wayland, called XWayland. The way this works is that, when you run an application with no Wayland support (or where Wayland support is not enabled), it will instead be run in an X server that will display in Wayland. For me this worked fine, with no noticeable lags or performance loss. However, all X applications run in XWayland share the same instance (for now), so in terms of security these applications are not better isolated from one another than with X.

So what matters is that applications manipulating sensitive information (e.g., for me, terminal emulators) should not be run in XWayland. This means switching to a Wayland-compatible terminal emulator. My current terminal emulator, rxvt-unicode, is not. For now I just went back to gnome-terminal, which works. Suggestions of terminals to try out (which I haven't tested yet) include:

• Alacritty
• Germinal
• Kitty, which is packaged for Debian but the packaged version doesn't use Wayland (and I didn't find a way to convince it to do otherwise)
• Termite

Again, thanks for ManDay for suggestions here.

As for other applications I don't care much except for the Web browser. Experimental support for Wayland just landed in Firefox Nightly, you can download it here, uncompress it, and then run it with GDK_BACKEND=wayland ./firefox. This is promising, however from my tests it's still not very stable: opening a second window often made it hang or at least fail to redraw the window that was being manipulated. I hope that this will improve and eventually be available in the normal Firefox releases.

Tearing

Not a point to fix, but just a remark: one of the things that interested me in testing Wayland was that it is supposed to help reduce screen tearing. That said, it seems I'm no longer able to reproduce tearing on X either... Testing on some videos I didn't manage to see any noticeable difference between X and Wayland, so I can't really claim this as a benefit.

In terms of video playback: Debian's mpv in testing is able to use Wayland natively by running mpv --gpu-context=wayland. For me it worked fine but I couldn't see any difference with running it in XWayland. VLC, however, does not use Wayland (I couldn't figure out if there was a Wayland backend). In terms of performance (measured by CPU usage on the same file) for mpv and VLC:

• VLC on Wayland (in XWayland) or in X, and mpv with hardware acceleration (--hwdec=auto) and with the native Wayland backend or in X, are the most efficient (around 8% CPU)
• Running mpv with hardware acceleration and in XWayland is a bit worse (15% CPU)
• Without hardware acceleration, mpv is much less efficient at around 45% CPU, both in X and in Wayland (both for XWayland and for the native backend).

Disclaimer: enabling hardware acceleration for mpv is discouraged.

Taking screenshots

I used to take screenshots with scrot, but it is an X utility, so it will fail silently. Instead, you can use grim, as suggested in the sway wiki.

cd ~/apps

git clone 'https://github.com/emersion/grim'
cd grim
meson build
ninja -C build

You cannot invoke grim without specifying an output file. I preferred scrot's way of automatically generating a filename based on date and time, so you just have to write a wrapper script, e.g., this.

Changing the screen locker

It seems that my previous screen locker (xtrlock) worked with Wayland, but I thought it safer to switch to the one supplied with sway, i.e., swaylock. I customized it to the way I like, e.g., I like to have the possibility of locking my session without hiding what's on the screen (e.g., to monitor stuff). The result is here.

Sandboxing a process

With sway in place, sandboxing a process is rather easy. Let's say that the process to sandbox uses X (not Wayland natively), and that it is running as user sandbox. In Wayland, you just need to issue xhost +si:localuser:sandbox (which will set the access controls for the XWayland server), and then run the process with sudo -u sandbox process as usual: the process will display while running in XWayland, and will be indistinguishable from other performances, in particular I didn't notice any performance problems. (For instance, playing a video on Youtube in Firefox is hungry in terms of CPU, using around 120-150%, but that's the same figure as running Firefox under X.) The sandboxed process will have access to all events in other X applications that use XWayland, but it is not able to access the events of native Wayland applications, and these applications cannot access the events of one another.

You can use xinput test (running in XWayland) to see the events that are communicated to the XWayland X server. In fact, this is the easiest way I found to test if a window was running natively in Wayland or in XWayland.

Remaining issues

To me the main issues that remain with the setup are:

• General perceived sluggishness. It's hard to explain why but I get the impression that some things are less smooth in Wayland, in particular moving windows around (while in tiling mode), but even displaying text in a terminal emulator just feels a tiny bit slower. I'm not sure if I'm just imagining this, or I'll stop noticing this after a while, or if there's a way to improve performance, or if it will improve over time as the code of sway, wlroots, etc., improves. For now it's just a rather mild annoyance. We'll see whether I stick with Wayland nevertheless or if I get fed up with it and give up.
• Having to install programs (sway and dependencies) that are not packaged for Debian yet. That said, there has been some interest in packaging sway for Debian, and hopefully it will happen once sway reaches version 1.0, which doesn't seem so far away.
• Lack of native apps for Wayland, in particular having to go back to gnome-terminal or to try more experimental terminals.
• The realization that X applications are not isolated from one another as they are all running with the same XWayland server.
• I did not try using a projector yet. With X you use xrandr (see my guide here), but this doesn't work on Wayland. It looks like you should configure it instead with sway by specifying the coordinates of the various outputs. However, I don't know whether projectors would work fine, given that the list of modes that they support is often pretty erratic, whereas with my laptop's screen, for instance, sway only shows one available mode. Also, there is no support yet for showing the same content on two monitors, e.g., on the screen and on the projector.
• There is no support for the nm-applet icon to configure NetworkManager, see this issue.

A more subtle point is that there is no discernible benefit to the user in running Wayland: at best it works just like X. For me the main benefit is security, but this is a pretty hard benefit to notice...

Thanks to linkmauve for proofreading and suggestions.

I have just finished writing up a long document that tries to give a comprehensive list of problems affecting academic research.

Writing this document is something that I had been meaning to do for a very long time, almost since I got started in academia in 2012 with my master's internship. Many academic practices did not make any sense to me already at the time, e.g., hiding research articles behind paywalls rather than simply hosting them online. I tried to ignore these concerns for a while, and did my PhD without questioning too much the order of things: for some practices I eventually saw a justification, but for many others I did not, and they made me more and more uneasy. So I thought that I should eventually come back to these problems, to re-examine my beliefs about the way academia works. Hence this long list of all the problems that annoy me, which I will try to keep up-to-date as time passes and my experience evolves.

Of course, complaining is always easy, so I have also tried to give some thought in the document about ways to fix these problems. The document does not mention my own initiatives in this direction (e.g., refusing to review for closed-access venues), which I will eventually write up separately.

So I encourage you to have a look at the document, What's wrong with academia?, and share with me any feedback that you may have!

The DBLP service is a great bibliographical tool for computer science research. In this post, I explain how to use it to prepare the list of members of a research community. I will be using the theoretical database community, whose two conferences are PODS and ICDT.

The list of publications for one edition of a conference can be found on DBLP as XML, e.g., for ICDT'18. It is then easy to use xmlstarlet to find the list of people who have published at that conference:

curl -s 'https://dblp.uni-trier.de/db/conf/icdt/icdt2018.xml' |
  xmlstarlet sel -T -t -m "//inproceedings/author" -m . -c '.' -n |
  sort | uniq

For each person in the list, we can obtain detailed XML information, including its homepage, ORCID, etc., using the DBLP API again. (This also gives us a canonical form for the name, which may appear in different ways in various inproceedings entries.) This is just a bit more complicated than it should, because of a limitation of the DBLP search API: when queried with a name, sometimes the API inexplicably favors non-exact matches even in some cases where an exact match exist. So we must filter the matches ourselves to use an exact match if one exists, and a non-exact match otherwise. Of course, independently from this problem, you may be getting the wrong author, in particular because of homonyms, so these results should be taken with a grain of salt.

NAME="Antoine Amarilli"
ENAME=$(echo "$NAME" | sed 's/ /%20/g')
curl -s "https://dblp.org/search/author/api?h=1000&q=$ENAME" > matches.xml
URL=$(xmlstarlet sel -T -t -m "/result/hits/hit/info[author='$NAME']" \
    -c url -n < matches.xml | head -1)
if [[ -z "$URL" ]]
then
  URL=$(xmlstarlet sel -T -t -m /result/hits/hit/info/url \
      -c . -n < matches.xml | head -1)
fi
curl -L "${URL}.xml"

From there, we can use this to prepare a list of community members. Of course, any criterion for inclusion is completely arbitrary... My criterion to get a list of "active community members" is to select the who have published on three different years, with one publication in 2015 or later. Which gives:

Corrected one error in this list caused by the DBLP search API limitation

Another inclusion criterion for a "historical" list would be the list of people who are not necessarily still active but have published over a long period, say, 10 different (not necessarily contiguous) years. Here is the resulting list, sorted by the year where the person has last published in ICDT or PODS.

Another kind of statistics that can be computed in this way is the "neighboring" conferences, i.e., the other conferences where members of the community have published. Here is the list of the top neighboring conferences of PODS and ICDT, sorted by the number of active community members who have published at least once there since 2015 (with hyperlinks and descriptions added manually):

• 38: SIGMOD Conference, the practical database conference held jointly with PODS
• 34: AMW, the database theory workshop held in honor of Alberto O. Mendelzon (whom you may remember from the previous list)
• 29: IJCAI, an AI conference
• 28: ICALP, a theoretical CS conference on logics and automata
• 26: LICS, another theoretical CS conference about logics
• 20: SODA, a theoretical CS conference on algorithms
• 19: AAAI, another AI conference
• 19: EDBT, the practical database conference held jointly with ICDT
• 18: WWW, a conference about the World Wide Web
• 15: Description Logics, the workshop on description logics
• 15: ICDE, a practical data management conference
• 13: CIKM, an information and knowledge management conference
• 12: SEBD, the Italian conference on databases
• 12: STOC, a general-purpose theoretical computer science conference
• 11: KR, a conference on knowledge representation and reasoning
• 11: FOCS, another general-purpose theoretical computer science conference

It would be interesting to visualize this data differently, e.g., visualize a world map with the community members, but sadly the affiliation information in DBLP is too sparse for this to work.

Since version 0.26, the mail indexing tool that I use, notmuch, now makes it easy to index encrypted mail.

The original behavior was that notmuch did not index the contents of encrypted emails, as they were encrypted and it couldn't access them. This meant that you couldn't search inside encrypted emails (except for headers, e.g., the subject, recipient, etc.).

Now, notmuch is able to use gpg (and gpg-agent) to read and index the cleartext of encrypted emails. Of course, this means that notmuch's index can now be used to reconstruct encrypted emails; in particular, as notmuch stores the session keys for messages in its index, this means that any attacker who can access the index can decrypt the messages¹. For my use case, I think that this security risk is acceptable: I essentially see GPG as a tool to ensure that messages are not altered between the sender and recipient, my notmuch index is stored on an encrypted partition anyway, and my GPG passphrase is usually cached by gpg-agent so an attacker who has control over my machine would be able to access the plaintext of encrypted messages quite easily.

So, if you also use notmuch, if you also have your passphrase cached by gpg-agent at least part of the time, and if you want notmuch to index the cleartext of your encrypted emails, here is what you should do. First, you should make sure that you have notmuch 0.26 or a more recent version. Second, you should tell notmuch that you want it to index the cleartext of encrypted email:

notmuch config set index.decrypt true

Beware, this configuration flag lives only in the database, not in the config file; hence, e.g., it will not be synchronized across multiple machines if you synchronize your config files from one machine to another.

Then you should reindex all encrypted email that notmuch knows about but hasn't indexed yet (this took around 15 mins in my case):

notmuch reindex tag:encrypted and not property:index.decryption=success

Of course, you will be prompted for your GPG passphrase if it isn't cached (and also possibly for the passphrase of other keys that you have used in the past). Once this has completed, you should check the encrypted messages that notmuch was still unable to index:

notmuch search tag:encrypted and not property:index.decryption=success

In my case, there were only a few that couldn't be indexed -- and usually it was because they hadn't been encrypted for my key because the sender had made some mistake.

From now on, notmuch new should automatically index the cleartext of incoming messages when your GPG passphrase is cached by gpg-agent. The last step is the following: if your passphrase is not cached all the time, then you should arrange for the notmuch reindex command above to be executed regularly, so that encrypted messages will eventually be indexed.

The setup described in this post lead to unpleasant side effects where GPG invocations would hang, probably because notmuch tried to ask for a passphrase. To avoid this, I had to ensure that the notmuch reindex command, when run regularly, never tried to ask for a passphrase if it wasn't currently stored by the agent. I did this by setting PINENTRY_USER_DATA=none and modifying my custom pinentry script to handle properly this value. (Of course, this means that encrypted messages will not be correctly indexed when the GPG agent hasn't cached the passphrase, but the hope is that they will eventually be indexed.)

Another problem that I had is that notmuch reindex would waste CPU time by trying to reindex each time the emails where it had previously failed. To avoid this, I reviewed manually the mails that couldn't be indexed, tagged them with a special tag, and then excluded mails with that tag from the notmuch reindex command. I also added a crontab entry to review periodically the emails where indexing failed, so I will tag them appropriately if the failure is expected. A more elaborate idea would be to exclude from the notmuch reindex command the emails that are too ancient; or maybe script things so that when all GPG keys are available in the agent but notmuch cannot index a message then it should tag it so as not to try again.

I'm still having problems with pinentry misbehaving, i.e., either not showing up anymore because a pinentry-curses is waiting for input somewhere, or having pinentry-gtk popping up uninvited. I can live with it for now but at some point I should investigate this and tidy it up.