Antoine Amarilli's blog

Customizing your keyboard layout with xkbcomp

— updated

This is really going to be a poor excuse for a tutorial, it is just aimed at covering my current setup and nothing else, but maybe it is useful to someone.

I type using the Dvorak Simplified Keyboard (though I'm not especially convinced it has any intrinsic benefits, but that's another story). However, as I type French (but don't use a French Dvorak or the Bépo layout -- another complicated story), I need to have mappings to type the diacritics used in French. (French keyboard mappings provide the diacritics at the expense of some characters being relegated to AltGr combinations, and they have 105 keys, one more than Qwerty keyboards, with the additional key at the bottom right being used for '<' and '>'.)

Debian provides the Dvorak Simplified Keyboard, along with an international option that allows you to have AltGr combinations to invoke dead keys for common diacritics, you can obtain it using the following invocation. (Note that in all of this I am thinking of the X server world, not the ttys, which I don't use and which use a different mechanism, see loadkeys.)

setxkbmap -layout dvorak -variant intl -model pc105

However, those combinations are not especially convenient (AltGr-6 for the circumflex, for instance...), so it is tempting to modify them. I used to carry an entire dump of the keyboard configuration, that I edited haphazardly and loaded with xkbcomp ~/.xmodmaprc $DISPLAY. I now figured out by skimming through some documentation (mostly this) how to do so more cleanly.

Let me assume that the configuration will be stored in config/xkb. First create a file map to load your current configuration. In my case, I issued:

setxkbmap -layout dvorak -variant intl -model pc105 -option compose:caps -print > map 

You should be able to load this file by issuing xkbcomp ~/config/xkb/map $DISPLAY. Next, create a subfolder symbols that will contain the various files storing the customizations. I have altgr that sets up AltGr (the right alt key) to be used as a modifier, space that sets up a combination to make non-breaking spaces (both AltGr and Maj as I don't want to make them accidentally), and a file accents that stores all of the accents that I need: both dead keys, and shortcuts to make the most common accented characters directly. On Debian systems, see package x11proto-core-dev, file /usr/include/X11/keysymdef.h, for the possible symbols.

Now, you can add to the "xkb_symbols" line of the map file a reference to your extension files: separated by spaces, first the name of the file and then between brackets the name of the stanza (they match in my examples). This gives the final map file.

Last, you need to be able to invoke it. You need to specify where to search for the extension files, so the complete invocation is:

xkbcomp -I$HOME/config/xkb ~/config/xkb/map $DISPLAY

Do not worry about the many warnings. I run this script at the start of my X session to set up the layout (and to set the delay and rate for typematic (the delay after which keys repeat when you keep them pressed) to something that's reasonably fast).

A cute allocation problem

— updated

In the spirit of something I already did, I'm going to discuss a cute problem that suggested itself spontaneously over dinner, except this time I will study its complexity from a theoretical angle.

The problem is as follows. You applied to a number of companies, and each company's board issued a list of the candidates ranked by their order of preference. You know, for each company, how many people they will hire, and you know that they will take the highest ranked people who accept the job. Your hope is to get a job at any of the companies. Maybe you are ranked sufficiently high at some company to be sure to get a job there, in which case you've won; but maybe you aren't, and you hope that some of the people ranked higher than you will not accept their offer(s) so that you can be selected instead.

Of course, you always have some hope that everyone will desist and that you will get what you want. A harder question is: can you be sure that you will get a position, even though you are not ranked well enough to be sure to have any position? If you think about it, the answer is clearly yes in some situations, assuming that other candidates can only accept at most one position. If some super-strong guy is ranked first at all positions, then he'll take only one of them at most, so if there are two positions where you're the first candidate below the bar, then you're sure to get one of them no matter what happens.

The problem is now to decide this algorithmically. Given as input the list of candidates that beat you at each company, given the number of people recruited by each company, can you decide efficiently whether you are sure to get a job at any of the companies?

It might seem that this problem is NP-hard (computationally intractable) because it looks a lot like the set cover problem or the Boolean satisfiability problem, but actually you can determine in polynomial time whether you are sure to get some job.

The method is to encode the problem as a flow problem. Build a graph that has a source vertex s, a target vertex t, one vertex ci for each candidate i, one vertex lj for each list j, and consider the graph with one edge from s to every ci (with capacity 1), one edge from each ci to the lists lj where candidate i appears before you (with capacity 1), and one edge from each lj to t whose capacity is the number of positions offered by company j (in other words, the number of candidates that need to accept a position at this company for you not to get the job).

Now, we ask whether the maximal flow of this graph saturates all the edges to t. If it does, and if the flow is integral, then observe that the flow gives you a way to allocate candidates to lists so that you do not get any job (the one saturated edge leaving ci tells you which job candidate i accepts). Conversely, if there is such an allocation, then there is a maximal flow saturating all edges to t. But now, the integral flow theorem ensures that there is always a maximal flow that is integral. It remains to observe that the maximum flow problem can be solved in polynomial time to conclude that the same is true of our problem.

This implies the tractability of the following (equivalent) rephrasing of this problem in terms of satisfiability. You have a set of variables (xi) which can each be assigned a value from a domain Di (so, multivalued variables). You have a conjunction of clauses which are sets of equalities between such variables and a constant from their domain. For each clause Cj you have a number nj and you say that the clause is true if at least nj of its litterals are true. This is of course much worse than the usual NP-hard Boolean satisfiability problem, except that you require that the same equality (between a variable and a constant) can never occur in two different clauses. Now, by the above, this restriction makes the satisfiability problem tractable.

New GPG key

— updated

It's a bit of a pain, but it turns out that my old OpenPGP key was using suboptimal settings, and so I've regenerated a new one.

I did this after reading this fine best practices tutorial (for which I incidentally wrote a French translation). The gist of it is (1.) that you should set up GPG correctly to fetch keys from key servers (there's the parcimonie-related paranoia, but there's the very embarrassing fact that by default it seems that GPG never manages to talk to a key server; and (2.) that you should check that your key is secure by issuing the following and checking for things in red:

sudo apt-get install hopenpgp-tools
# FINGERPRINT is the actual fingerprint, not a key ID
hkt export-pubkeys "FINGERPRINT" | hokey lint

Generating a new key isn't especially hard but here is a reminder of what you have to do. You then have to re-sign the keys that you had signed with the old key, using the new one...

The formal transition statement signed by both keys is here, so that you can sign the new key if you had signed the old one.

SVG rendering in Gecko and Webkit

— updated

Did you know that Gecko and Webkit's implementation of SVG disagree on fairly basic points of the spec? For instance, this SVG image should be rendered differently depending on which engine you are using.

The trick is that one of both texts is hidden using a gradient calculated relative to the bounding box of a path with control points going outside of the path, which is computed differently by Webkit and Gecko. See the source of the image for a bit more detail.

It seems that Inkscape is also working like Gecko, and its way of computing bounding boxes makes more sense, so this is probably a Webkit bug, however a quick search didn't turn up the relevant bug (though this is probably well-known).

I devised this SVG with the help of Marc Jeanmougin who has had a good reason to investigate SVG implementations in browsers lately.

Review of the Lenovo IdeaPad Yoga 13 (59384174)

— updated

To replace my dead laptop, I just bought a Lenovo IdeaPad Yoga 13, often identified with the code 59384174 although the official model number seems to be 2191; the EAN13 code is 0887942530297. Here are my impressions about the device. I am using Debian Testing amd64, kernel version is 3.13.1-amd64 as of this writing.

I wanted a laptop with at least 13 inches (feels too cramped otherwise), with an SSD (and no SSD/HDD hybrid, I dislike mechanical drives for laptops and would not trust the controller's caching policy), with a screen resolution better than the default WXGA 1366 by 768 resolution of cheap 13 inch laptop screens, and I wanted the device to be light and slim (the Yoga 13 is 17 mm thick and weighs 1.5 kgs). Oh, and I wanted reasonable battery life.
Windows refund
The machine came with a preinstalled Windows 8. I contacted Lenovo France to get it refunded. However, the only option that their customer service offer to get a Windows refund is to refund the entire laptop... this is really sad.
I managed to buy the device for 590 euros: it was priced at 700 euros by Cdiscount (may not apply anymore as of this writing), 10 euros could be recouped if paying via Buyster, and 100 euros could be recouped from Lenovo France as of this writing through a special offer. From all the devices that I reviewed, this was the cheapest one to satisfy all my criteria, by a fairly large margin. This price not include a putative Windows 8 refund.
The charger is pleasantly slim and outputs 20V. The plug for the power slot in the device is a rectangular but reversible plug.
Power button
Note that if you need to power down the device during the Windows setup phase (because, say, you inadvertently entered it), long-pressing the power button will suspend the computer, not power it off. You need to continue pressing the button after that to turn the computer down.
The screen looks very nice, though a bit glossy. The 1600 by 900 resolution is pleasant. The viewing angle is very wide (no noticeable hue shift except when you start looking at it diagonally). Screen backlighting can be controlled (even disabled outright) through /sys/devices/pci0000:00/0000:00:02.0/drm/card0/card0-LVDS-1/intel_backlight/brightness. By default there is some tearing during video playback, I tried to fix it with this method, not sure how much it helps.
The main selling point of the Yoga series is that the screen folds 360 degrees to a tablet-like configuration. I only wanted to buy a laptop and have little plans to use this functionality (also for the reason that I wouldn't know which operating system to use to work as a tablet yet give me a suitable environment for a regular laptop), so that's just a bonus. Trying out the mechanism out of curiosity, it makes a fairly heavy and strange tablet, and having the keyboard behind is fairly bizarre. The rotation is achieved by a double-hinge mechanism: a standard hinge system works up to 180 degrees, and then those hinges rotate in a second hinge to go all the way to 360. The mechanism doesn't look especially solid and I wouldn't trust it not to break if used regularly, however for less than 180 degrees the standard hinge mechanism seems OK... A related complaint is that some magnets are used to make the 0 degrees (closed lid) and 360 degrees (tablet configuration) stable, and for 0 degrees those magnets are a bit too strong, so that it is a bit hard to open the laptop. On Linux, of course, if you use the Yoga in trestle mode, almost fully folded and reversed, which can be convenient e.g. to watch movies without having the keyboard in the way, you will have to take care of reversing the display with xrandr but also of reversing the input if you want to use the touchscreen. Here's a script to do this for you.
Orientation sensor
From the existence of a hardware button to lock screen rotation (see below), I imagine that the device must include an accelerometer, but it doesn't seem to be supported by the Linux kernel. Nothing relevant shows up in /proc/bus/input/devices or in /dev/input.
Interestingly, speakers are on the rear and the integrated microphone is on the side, probably because they must be usable both in laptop and tablet configuration. Sound quality is not especially good but not especially bad either, given the form factor.
The device features one minijack port (combined microphone and headphones), one eSATA-USB hybrid port, one USB port, one HDMI port, the power supply connector, one USB port, one SDcard-MMC reader, and that's it. Of course, no Ethernet port because the device is too thin. I bought a cheap USB-Ethernet adapter which was detected out of the box by Linux and seems to work.
The keyboard is pleasant enough, the keys are fairly high and have a reasonable size. The Left control is at the bottom left of the keyboard with the Fn button is at its right, which is how it should be (some laptops have the reverse). There is only a Super_L modifier (Windows key), not Super_R, but that's OK. Keys are positioned reasonably except that PageUp and PageDown are not quite at the position where I would have expected them (I would have expected them to be one row higher). By default, the F1-F12 keys can only be reached with Fn and the special (Volume, etc) fonctionalities being the default, but fortunately this can be changed in BIOS. The F1-F12 keys have the following additional features:
  1. Mute, generating XF86AudioMute.
  2. Volume down, generating XF86AudioLowerVolume.
  3. Volume up, generating XF86AudioRaiseVolume.
  4. Cross key, generating an Alt-F4 sequence (Windows keyboard shortcut to close a window).
  5. Refresh key, generating F5 (so doubles with the default behavior of the key.
  6. Disable touchpad key, exposes no events in xev but reports the following in dmesg: atkbd serio0: Unknown key pressed (translated set 2, code 0xbe on isa0060/serio0). Use 'setkeycodes e03e <keycode>' to make it known.
  7. Plane mode key, generating XF86WLAN, and from the dmesg it seems like the Wifi driver is seeing this also and disassociates, but nothing seems to be seen in rfkill.
  8. Three rectangles key, generating a Ctrl_L-Alt_L-Tab sequence (probably a Windows keyboard shortcut to switch application or something).
  9. Screen off key, toggles backlighting on and off (preempts the status in intel_backlight, no xev or dmesg event.
  10. Screen whatever key, generates a Super_L press? (Nothing more shows up, maybe things would be different if I had an external screen plugged in, but I have none to test this hypothesis).
  11. Brightness down key, generates XF86MonBrightnessDown (my i3 config uses xbacklight to handle this)
  12. Brightness up key, generates XF86MonBrightnessUp (ditto)
Additional keys
The laptop comes with a bunch of strange additional buttons, in addition to the keyboard. There is a button with a Windows logo (annoying, that) below the screen, which must be intended to be used in tablet mode with Windows; from xev it seems to simulate a press on Super_L (the windows key on keyboards), but only when released (it generates both the KeyPress and KeyRelease events when released). On the left side are two volume keys generating XF86AudioLowerVolume and XF86AudioRaiseVolume. On the right side is a button to lock screen rotation, which seems to emit the sequence Super_L+o (the Windows hotkey to do this, it seems). Last comes the power button and a small button on the left that can only be pressed with a pen or such; the documentation refers to it as the Novo button. It generates XF86Launch2.
Secure boot
Secure boot can be disabled in BIOS, whatever that is. BIOS offers both UEFI and legacy BIOS boot, legacy boot is not too fast. Interestingly trying to boot a Debian install USB key with UEFI will work except that the screen display will be garbled, this is fixed using legacy boot.
To get Bluetooth to work, install the driver and load the module. Now, here is how I get my Bose Mini SoundLink speakers to work. First, reset those speakers and put them in discoverable mode. Install the bluetooth daemon (Debian package blueetoth) and pulseaudio-module-bluetooth, try to issue pactl load-module module-bluetooth-discover. Ensure in rfkill that the hci0 device exists and isn't blocked. Then, retrieve their address by issuing sudo hcitool scan. Issue bluez-simple-agent hci0 ADDRESS and then bluez-test-audio connect ADDRESS. The speakers should indicate that pairing succeded. Now, check in pacmd list-sinks that a sink exists for the speakers, and use pavuctl to connect your music player to the right sink.
SD card reader
The reader appears as /dev/sdb, not /dev/mmcblk*, and inserting a card will not do anything until you try accessing it with fdisk -l /dev/sdb, at which point the partition files /dev/sdb* should be created. I haven't tried if booting off the SD card reader was possible.
The touchpad has an anti-feature: the button press zones are tactile, meaning that, by default, your pointer will move when trying to just click, this is extremely annoying. You can use synclient to set AreaBottomEdge when using the synaptics driver, but this has another downside: it means you cannot click and drag because clicking locks the pointer. I got much better results by installing xserver-xorg-input-mtrack and enabling it in xorg.conf: clicking at the bottom locks the mouse pointer except past a certain move threshold, which is the right thing to do. It is fairly annoying, however, that I couldn't get mtrack's ButtonZonesEnable feature to work, so to do a right click I have to click with one other finger touching the pad (and when left-clicking I mustn't leave another finger on the pad). I tend to touch the pad while typing, the IgnorePalm option seems to help a bit to ignore that.
Webcam works.
Ambient light sensor
The device has an ambient light sensor on the screen that can be made to work with the Zenbook driver (clone, make, insmod als.ko, requires linux-headers etc.; the value ranges from 0 in total darkness to 40000 in maximum light, with a value in the 1500-2000 range in normal indoor lighting conditions. I didn't try to write a script to adjust screen brightness automatically based on ambient light.
CPU and memory
/proc/meminfo reports 3938992 kB RAM.I haven't checked but there should be one RAM slot with non-soldered RAM, upgradeable by replacing by an 8 GB DDR3 module in SO-DIMM 204 pins packaging (costing about 75 euros as of this writing). /proc/cpuinfo reports the CPU as a Intel(R) Core(TM) i3-3227U CPU @ 1.90GHz. CPU frequency scaling is available, but cpufreq-info reports that it uses the intel_pstate driver, and that only the performance and powersave governors are available, with powersave being used by default. Loading the performance driver doesn't seem to make much of a difference. From cpufreq-aperf it looks like the CPU frequency increases up to the maximum 1.9 Ghz under load, even with the powersave governor (so it isn't locking the frequency to the lowest possible value).
Battery status can be read with ACPI as expected. From a quick test, during reasonable usage (browsing, investigating hotkeys, partitioning, etc.), and with phone plugged in (to tether and work around a Wifi glitch), battery life was around 4:30.
The entire case is closed with Torx-looking screws, and it seems that nothing is intended to be user-serviceable. In particular, you are probably not expected to replace the battery yourself. Of course, people have succeeded in opening their device, and a cursory search suggests that replacement batteries may still be available.
Fan and temperature
Two fans evacuate heat at the back of the unit. Four temperature sensors are detected by libsensors, one under acpitz-virtual-0 and two under coretemp-isa-0000. Temperatures are about 40 degrees in standard usage, with the fans spinning. Annoyingly I found no way to retrieve the fan RPM or to control the fans, and I find it sad that the fans seem to be always spinning even when temperature is low; they are not too noisy but total silence would be perfect, and that's just wasteful in terms of battery life. Temperatures reach 50 degrees and the fans speed up a bit under heavy load.
SSD is a Samsung MZMTD256, 238.47 GiB. Surprisingly it seems that if you are willing to open up your unit you can install a second mSATA SSD in a vacant slot. The default partition layout is surreal, with a whopping 7 partitions: WINRE_DRV, a 1000 MiB NTFS partition, SYSTEM_DRRRV, a 260 MiB bootable FAT32 partition, LRS_ESP, a 1000 MiB FAT32 partition, a 128 MiB msftres unknown partition, the main Windows partition (which is the only one that isn't hidden), and from memory a 4 GB partition and a 12 GB partition for obscure recovery purposes. I didn't touch the first four ones because they don't take up that much space and I'm afraid of making the device unbootable (that's probably an unrealistic fear, but who knows...), but I removed the Windows partition and the two last recovery partitions to install Debian instead. No problems in using GRUB (though I haven't tried booting anything except Debian).
Wifi does not work out of the box, and the absence of an Ethernet port means that Debian installation may be painful. A possible workaround is to use an USB-Ethernet adapter (not tested), or to tether a mobile phone's Wifi connection (Debian install knows how to use such connections) The Wifi chip has USB ID 0bda:1724, and to make it work, for now, you should compile and install the rtl8723au driver. It is painless and works. However, it doesn't seem like changing the MAC address is supported; sudo ifconfig wlan0 hw ether whatever doesn't fail but doesn't change anything, even if the interface is down and even if it is rfkilled. I haven't tried very hard yet or investigated whether the driver had a specific option for this. It does not look like activating monitor mode for airodump-ng works either. It looks like the driver was merged in Linux 3.15, so whenever this kernel version starts shipping with Debian, Wifi should work out of the box.
pm-suspend seems to work, taking about 1 second to suspend and resume. pm-hibernate works but I had to configure the hibernate swap partition manually. Hibernating takes around 10 seconds, booting and resuming from hibernate takes about 16 seconds.

All in all, I am pretty satisfied with the device so far.