2010-06-27

How to enable bitmap fonts on Ubuntu Karmic and Ubuntu Lucid?

This blog post gives instructions to enable bitmap fonts for GNOME and other Xft X11 applications. The instructions given have been tested on Ubuntu Karmic and Ubuntu Lucid, but they might work on other Unix systems as well with minor modifications. The reason for enabling bitmap fonts is to get crisp font rendering in dialog boxes, menus and window titles.

Run these commands to install some bitmap fonts from package:

$ sudo apt-get install xfonts-mplus xfonts-bitmap-mule xfonts-base
$ sudo apt-get install xfonts-75dpi{,-transcoded} xfonts-100dpi{,-transcoded}

Run the command to install some Microsoft vector fonts (e.g. Times New Roman, Arial, Courier New, Verdana). Installation might take a few minutes, because the font files have to be downloaded form an external site.

$ sudo apt-get install msttcorefonts

If you are using Ubuntu Karmic or earlier (not Ubuntu Lucid or later), then run these commands to install some QT configuration tools (needed for Skype):

$ sudo apt-get install qt3-qtconfig qt4-qtconfig

Run these commands to install some useful fonts (fixedsc is the classic 6x13 xterm monospaced bitmap font helpfully renamed to FixedSC, and helxetica is the Helvetica bitmap font helpfully renamed to Helxetica, for QT):

$ wget -qO- https://raw.githubusercontent.com/pts/fonts/master/helxetica.tgz |
       (cd / && sudo tar xzv)
$ wget -qO- https://raw.githubusercontent.com/pts/fonts/master/fixedsc.tgz  |
       (cd / && sudo tar xzv)

Enable bitmap fonts (this works in Ubuntu Hardy, Ubuntu Intrepid, Ubuntu Jaunty as well as in Ubuntu Karmic and Ubuntu Lucid):

$ sudo rm -f /etc/fonts/conf.d/70-{yes,no,force}-bitmaps.conf
$ if test -f /usr/share/fontconfig/conf.avail/70-force-bitmaps.conf
  then sudo ln -s /usr/share/fontconfig/conf.avail/70-force-bitmaps.conf /etc/fonts/conf.d/70-force-bitmaps.conf
  elif test -f /etc/fonts/conf.avail/70-force-bitmaps.conf
  then sudo ln -s {../conf.avail,/etc/fonts/conf.d}/70-force-bitmaps.conf
  else sudo ln -s {../conf.avail,/etc/fonts/conf.d}/70-yes-bitmaps.conf
  fi

The if above is needed, because /etc/fonts/conf.avail/70-force-bitmaps.conf has been introduced and /etc/fonts/conf.avail/70-yes-bitmaps.conf was made almost empty in Ubuntu Lucid. The correct (non-empty) contents are:

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
<!-- Accept bitmap fonts -->
 <selectfont>
  <acceptfont>
   <pattern>
     <patelt name="scalable"><bool>false</bool></patelt>
   </pattern>
  </acceptfont>
 </selectfont>
</fontconfig>

Run these commands to rebuild the font filename cache (so it will find all bitmap fonts, including the newly installed fonts):

$ sudo rm -f /var/cache/fontconfig/*
$ rm -rf "$HOME/.fontconfig"
$ sudo fc-cache
$ fc-cache
$ fc-list | grep -E 'Helxetica|FixedSC' | sort
FixedSC:style=Bold
FixedSC:style=Regular
Helxetica:style=Bold
Helxetica:style=Bold Oblique
Helxetica:style=Oblique
Helxetica:style=Regular

To have crisp fonts in dialog boxes, menus an window titles, then in System / Preferences / Appearance / Fonts, set the following font settings (on Ubuntu Lucid, use Helxetica instead of Helvetica):

  • Application font: Helvetica | 9
  • Document font: Arial | 10
  • Desktop font: Helvetica | 9
  • Window title font: Helvetica Bold | 9
  • Fixed width font: FixedSC | 10

To make the GNOME Panel reload its menu font, you have to restart it. Run

$ killall gnome-panel

In Applications / Accessories / Terminal / Edit / Profile preferences, make sure the Use the system fixed width font is ticked.

On Ubuntu Karmic and earlier, press Alt-F2, type qtconfig-qt3, press Enter, then wait for the Qt Configuration window to appear. In the tab Fonts, change the Family: to Helxetica (sic, it's not Helvetica), and the Point Size: to 9. In the menu, choose File / Save, then File / Exit.

On Ubuntu Karmic and earlier, repeat the previous paragraph with qtconfig-qt4 instead of qtconfig-qt3.

Notes:

  • There is no need to log out, restart Skype, restart Firefox restart Nautilus, restart the GNOME Terminal or restart the GNOME Panel. All these applications pick up the font changes immediately.
  • The Fixed (6x13) had to be renamed to FixedSC, because the original 6x13 font has the tag semicondensed, which makes it impossible to select in the GNOME font selection dialog (or in any fontconfig-based app).
  • The Helvetica bitmap font had to be renamed to Helxetica, because QT4 applications (such as Skype 2.1) cannot render non-latin-1 characters properly (they will find a substitution font for those characters, even though the characters are available in the Helvetica font).

2010-06-20

Does Btrfs survive silent disk data corruption in RAID1 mode?

Some of my experimenting with Btrfs in Linux 2.6.34 yielded the following results:

  • If only one disk (out of two) contains corrupt data, then Btrfs detects some checksum failures, and then recovers (overwriting the corrupt data with the corresponding good data from the other disk). This works even if the corruption happened while the filesystem was mounted.
  • If both disks contain corrupt data (but not at the same location), then Btrfs detects some checksum failures, then recovers some data, but it won't recover all of it: some files continue to have I/O errors when reading, and the syslog will contain checksum failures again and again. The explanation for this behavior may be that in Btrfs RAID 1 mode the two copies of a block of data might be at a different offset on the two disks.

Here is how I did the experiment:

  • I had a Linux 2.6.34 system.
  • I had 2 partitions of size 2000061 KB each. (1 KB == 1 << 10 bytes.)
  • # mkfs.btrfs -m raid1 -d raid1 /dev/sdc1 /dev/sdb1
  • # mount /dev/sdb1 /mnt/p
  • I copied /var/lib/dpkg (7248 small files of 36.93 MB) recursively to /mnt/p.
  • I copied 4 large files of 1517.98 MB in total to /mnt/p. (So the filesystem became >75% full.)
  • I created 10000 empty files.
  • I calculated the checksum of all files in /mnt/p with a userspace tool.
  • I introduced the single-disk corruption by running dd if=/dev/zero of=/dev/sdb1 bs=1M count=1600 seek=200
  • I calculated the checksum of all files again. At this point the kernel reported some block checksum mismatches in the syslog, but eventually Btrfs has recovered all the data, and the file checksums matched with the previous run.
  • I introduced the non-ovarlapping multi-disk corruption by running dd if=/dev/zero of=/dev/sdb1 bs=1M count=800 seek=200 && dd if=/dev/zero of=/dev/sdc1 bs=1M count=800 seek=1000
  • I calculated the checksum of all files again. At this point the kernel reported some block checksum mismatches in the syslog, and it could reover some blocks, but not all, and some files yielded an I/O error, but the checksum of the non-erroneous files matched with the previous run.

2010-06-18

How to use the ssh-agent programmatically for RSA signing

This blog post explains what an SSH agent does, and then gives initial hints and presents some example code using the ssh-agent wire protocol (the SSH2 version of it, as implemented by OpenSSH) for listing the public keys added to the agent, and for signing a message with an RSA key. The motivation for this blog post is to teach the reader how to use ssh-agent to sign a message with RSA. Currently there is no command-line tool for that.

The SSH agent (started as the ssh-agent command in Unix, or usually as Pageant in Windows) is a background application which can store in its process memory some SSH public key pairs in unencrypted form, for the convenience of the user. When logging in, ssh-agent is usually started for the user; the user then calls ssh-add (or a similar GUI application) to add his key pairs (e.g. $HOME/.ssh/id*) to the agent, typing the key passphrases if necessary. Afterwards, the user initiates SSH connections, for which the keys used for authentication are taken from the currently running agent. The SSH agent provides the convenience for the user that the user doesn't have to type the key passphrases multiple time, plus that if agent forwarding is enabled (ForwardAgent yes is present in $HOME/.ssh/config), then the agent is available in SSH connections initiated from SSH connections (of arbitrary depth). The agent forwarding feature of ssh-agent is unique, because other in-memory key stores such as gpg-agent don't have that feature, so the keys stored there are available only locally, and not within SSH sessions.

The SSH agent stores both the public and the private keys of a key pair (and the comment as well), but it only ever discloses the public keys to applications connecting to it. The public keys can be queried (displayed) with the ssh-add -L command. But to the ssh-agent can prove to the external world that it knows the private keys (without revealing the keys themselves), because it offers a service to sign the SHA-1 checksum (hash) of any string. SSH uses public-key cryptography, which has the basic assumption that a party can sign a message with a key only he knows the private key; but anyone who knows the public key can verify the signature.

ssh-add uses the SSH_AUTH_SOCK environment variable (containing the pathname of a Unix domain socket) to figure out which ssh-agent to connect to. The permissions for the socket pathname are set up so that only the rightful owner (or root) can connect, other users get a Permission denied.

For more information about how SSH uses public-key cryptography and agents, please read this excellent article.

Below there is an example wire dump of an application using the SSH agent protocol to ask the list of public keys added to an ssh-agent (just like ssh-add -L), and to ask the ssh-agent to sign a message with an RSA key added to it. The sign request is usually sent when an SSH client (ssh(1)) is authenticating itself to an SSH server, when establishing a connection.

To understand the wire dump below, one has to know that in the RSA public-key cryptography system the public key consists of a modulus and a public exponent, the modulus being a very large integer (2048 bits or longer), the exponent being positive a small or large integer, smaller than the modulus. Verifying a signature consits of interpreting a signature as a large integer, exponentiating it to the public exponent, taking the result modulo the modulus, and comparing that result with the original message (or, in case of SSH, the SHA-1 checksum of the original message). Please read the article linked above for a full definition and the operation of RSA.

# The client connects to the agent.
client.connect_to_agent()

# The clients lists the key pairs added to the agent.
client.write("\0\0\0\1")  # request_size == 1
  client.write("\v")  # 11 == SSH2_AGENTC_REQUEST_IDENTITIES
agent.write("\0\0\3\5")  # response_size == 773
  agent.write("\f")  # 12 == SSH2_AGENT_IDENTITIES_ANSWER
  agent.write("\0\0\0\2")  # num_entries == 2
    agent.write("\0\0\1\261")  # entry[0].key_size == 433
      agent.write("\0\0\0\7")  # key_type_size == 7
        agent.write("ssh-dss")
      agent.write("...")  # 443-4-7 bytes of the DSA key
    agent.write("\0\0\0\25")  # entry[0].comment_size == 21
    agent.write("/home/foo/.ssh/id_dsa")
    agent.write("\0\0\1\25")  # entry[1].key_size == 275
      agent.write("\0\0\0\7")  # key_type_size == 7
        agent.write("ssh-rsa")
      agent.write("\0\0\0\1")  # public_exponent_size == 1
        agent.write("#")  # public_exponent == 35
      agent.write("\0\0\1\1")  # modulus_size == 257
        agent.write("\0...")  # p * q in MSBFirst order
    agent.write("\0\0\0\25")  # entry[1].comment_size == 21
    agent.write("/home/foo/.ssh/id_rsa")

# The client gets the agent sign some data.
data = "..."  # 356 arbitrary bytes to get signed.
client.write("\0\0\2\206")  # request_size == 646
  client.write("\r")  # 13 == SSH2_AGENTC_SIGN_REQUEST
  client.write("\0\0\1\25")  # key_size == 277
    client.write("\0\0\0\7")  # key_type_size == 7
      client.write("ssh-rsa")
    client.write("\0\0\0\1")  # public_exponent_size == 1
      client.write("#")  # public_exponent == 35
    client.write("\0\0\1\1")  # modulus_size == 257
      client.write("\0...")  # p * q in MSBFirst order
  client.write("\0\0\1d")  # data_size == 356
    client.write(data)  # arbitary bytes to sign
  client.write("\0\0\0\0")  # flags == 0
agent.write("\0\0\1\24")  # response_size == 276
  agent.write("\16")  # 14 == SSH2_AGENT_SIGN_RESPONSE  (could be 5 == SSH_AGENT_FAILURE)
  agent.write("\0\0\1\17")  # signature_size == 271
    agent.write("\0\0\0\7")  # key_type_size == 7
      agent.write("ssh-rsa")
    agent.write("\0\0\1\0")  # signed_value_size == 256
      agent.write("...")  # MSBFirst order

# The client closes the SSH connection.
client.close()
agent.read("")  # EOF

Below there is an example Python script which acts as a client to ssh-agent, listing the keys added (similarly to ssh-add -L), selecting a key, asking ssh-agent to sign a message with an RSA key, and finally verifying the signature. View and download the latest version of the script here.

#! /usr/bin/python2.4
import cStringIO
import os
import re
import sha
import socket
import struct
import sys

SSH2_AGENTC_REQUEST_IDENTITIES = 11
SSH2_AGENT_IDENTITIES_ANSWER = 12
SSH2_AGENTC_SIGN_REQUEST = 13
SSH2_AGENT_SIGN_RESPONSE = 14
SSH_AGENT_FAILURE = 5

def RecvAll(sock, size):
  if size == 0:
    return ''
  assert size >= 0
  if hasattr(sock, 'recv'):
    recv = sock.recv
  else:
    recv = sock.read
  data = recv(size)
  if len(data) >= size:
    return data
  assert data, 'unexpected EOF'
  output = [data]
  size -= len(data)
  while size > 0:
    output.append(recv(size))
    assert output[-1], 'unexpected EOF'
    size -= len(output[-1])
  return ''.join(output)

def RecvU32(sock):
  return struct.unpack('>L', RecvAll(sock, 4))[0]

def RecvStr(sock):
  return RecvAll(sock, RecvU32(sock))

def AppendStr(ary, data):
  assert isinstance(data, str)
  ary.append(struct.pack('>L', len(data)))
  ary.append(data)

if __name__ == '__main__':
  if len(sys.argv) > 1 and sys.argv[1]:
    ssh_key_comment = sys.argv[1]
  else:
    # We won't open this file, but we will use the file name to select the key
    # added to the SSH agent.
    ssh_key_comment = '%s/.ssh/id_rsa' % os.getenv('HOME')

  if len(sys.argv) > 2:
    # There is no limitation on the message size (because ssh-agent will
    # SHA-1 it before signing anywa).
    msg_to_sign = sys.argv[2]
  else:
    msg_to_sign = 'Hello, World! Test message to sign.'

  # Connect to ssh-agent.
  assert 'SSH_AUTH_SOCK' in os.environ, (
      'ssh-agent not found, set SSH_AUTH_SOCK')
  sock = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM, 0)
  sock.connect(os.getenv('SSH_AUTH_SOCK'))

  # Get list of public keys, and find our key.
  sock.sendall('\0\0\0\1\v') # SSH2_AGENTC_REQUEST_IDENTITIES
  response = RecvStr(sock)
  resf = cStringIO.StringIO(response)
  assert RecvAll(resf, 1) == chr(SSH2_AGENT_IDENTITIES_ANSWER)
  num_keys = RecvU32(resf)
  assert num_keys < 2000  # A quick sanity check.
  assert num_keys, 'no keys have_been added to ssh-agent'
  matching_keys = []
  for i in xrange(num_keys):
    key = RecvStr(resf)
    comment = RecvStr(resf)
    if comment == ssh_key_comment:
      matching_keys.append(key)
  assert '' == resf.read(1), 'EOF expected in resf'
  assert matching_keys, 'no keys in ssh-agent with comment %r' % ssh_key_comment
  assert len(matching_keys) == 1, (
      'multiple keys in ssh-agent with comment %r' % ssh_key_comment)
  assert matching_keys[0].startswith('\x00\x00\x00\x07ssh-rsa\x00\x00'), (
      'non-RSA key in ssh-agent with comment %r' % ssh_key_comment)
  keyf = cStringIO.StringIO(matching_keys[0][11:])
  public_exponent = int(RecvStr(keyf).encode('hex'), 16)
  modulus_str = RecvStr(keyf)
  modulus = int(modulus_str.encode('hex'), 16)
  assert '' == keyf.read(1), 'EOF expected in keyf'

  # Ask ssh-agent to sign with our key.
  request_output = [chr(SSH2_AGENTC_SIGN_REQUEST)]
  AppendStr(request_output, matching_keys[0])
  AppendStr(request_output, msg_to_sign)
  request_output.append(struct.pack('>L', 0))  # flags == 0
  full_request_output = []
  AppendStr(full_request_output, ''.join(request_output))
  full_request_str = ''.join(full_request_output)
  sock.sendall(full_request_str)
  response = RecvStr(sock)
  resf = cStringIO.StringIO(response)
  assert RecvAll(resf, 1) == chr(SSH2_AGENT_SIGN_RESPONSE)
  signature = RecvStr(resf)
  assert '' == resf.read(1), 'EOF expected in resf'
  assert signature.startswith('\0\0\0\7ssh-rsa\0\0')
  sigf = cStringIO.StringIO(signature[11:])
  signed_value = int(RecvStr(sigf).encode('hex'), 16)
  assert '' == sigf.read(1), 'EOF expected in sigf'

  # Verify the signature.
  decoded_value = pow(signed_value, public_exponent, modulus)
  decoded_hex = '%x' % decoded_value
  if len(decoded_hex) & 1:
    decoded_hex = '0' + decoded_hex
  decoded_str = decoded_hex.decode('hex')
  assert len(decoded_str) == len(modulus_str) - 2  # e.g. (255, 257)
  assert re.match(r'\x01\xFF+\Z', decoded_str[:-36]), 'bad padding found'
  expected_sha1_hex = decoded_hex[-40:]
  msg_sha1_hex = sha.sha(msg_to_sign).hexdigest()
  assert expected_sha1_hex == msg_sha1_hex, 'bad signature (SHA1 mismatch)'
  print >>sys.stderr, 'info: good signature'

The wire dump above was created by attaching to a running ssh-agent with strace. The Python example code was written by understanding the ssh-agent.c in the OpenSSH codebase.

2010-06-14

How to fix printing with HP LaserJet 1018 on Ubuntu Lucid and Karmic

This blog post explains how to fix CUPS printing for HP LaserJet 1018. The instructions and the shell script presented have been tested on Ubuntu Lucid and Ubuntu Karmic, but they might work on other Linux systems as well with minor modifications.

The first method to make the HP LaserJet 1018 work is running

$ sudo apt-get install hplip
$ sudo hp-setup

, and following the instructions, and running hp-setup again if necessary. This method seemed to work for me (I could print a test page), but I haven't tested it excessively, and the printer got the margins wrong, because it assumed that I'm printing to Letter paper, but I was printing to A4.

The second method (recommended) is the following. Download and run this script: http://pts-mini-gpl.googlecode.com/svn/trunk/pts-hplj1018/fix_hplj1018.sh.

The script download and install the printer firmware, it will ask you to install some packages (such as cups and foo2zjs), and to connect and disconnect the printer. It will also install the printer, remove (cancel) all pending jobs, and change the CUPS printer state to ready. Run this script each time you can't print anymore (e.g. because of a system upgrade).

The script has the A4 page size (used in Europe) hard-wired. If your printer supports the Letter page size (used in the USA), replace all occurrences of the word A4 in the script by the word Letter.

Setting up the printer is tricky because all settings have to be correct (otherwise the printer will just ignore jobs sent to it), and Ubuntu gets many settings wrong. The script fixes these settings:

  • The updated firmware (as required by foo2zjs) has to be present in /usr/share/foo2zjs/firmware/sihp1018.dl. Ubuntu doesn't have a package containing this file. The script downloads, extracts and installs the firmware.
  • The correct udev rules have to be in place so /usr/sbin/hplj1018 is run (and uploads the firmware) when the printer is connected. Ubuntu Lucid has a wrong (non-matching) udev rule in /lib/udev/rules.d/85-hplj10xx.rules. The script fixes to udev rule.
  • The correct PPD file must be present with the correct page size. The default file /usr/share/ppd/foo2zjs/HP-LaserJet_1018.ppd.gz in Ubuntu has the Letter size, which the script changes to A4 in the file /etc/cups/ppd/HP_LaserJet_1018_pts.ppd.
  • No printing jobs must be active or pending when the printer gets connected (so the firmware has a chance to upload). Ubuntu doesn't care about this. The script makes sure that CUPS is not running when the printer gets connected, and it also removes all pending jobs.
  • On Ubuntu Lucid there is a conflict between the usblp and the usb drivers: the newest CUPS uses usb to drive USB printers (while older CUPS versions used usblp), but usblp claims the printer first, so CUPS has no chance to actually use it. The solution is to modify the DeviceURI in /etc/cups/printers.conf to parallel:///dev/usb/lp0

2010-06-12

How to create a custom keyboard layout for X.Org on Ubuntu

This blog post gives an overview of the steps needed for creating and installing a new custom keyboard layout for X.Org (X11). The steps outlined here have been tested on Ubuntu Karmic and Ubuntu Lucid, but they should work on other Linux systems as well with minor modifications. The designer of a custom keyboard layout can assign (almost) Unicode characters and other keyboard symbols (such as F1 or Insert) arbitrarily to keys and key combinations (with modifiers like Shift and Ctrl). You are encouraged to create a custom keyboard layout for yourself if some useful symbols are missing from your favorite keyboard layout, or you can work with your own custom key mapping much faster with the default layouts, or you need a blend of two layouts with AltGr (right Alt) as the modifier key for selecting the alternative layout for 1 keypress.

All the keyboard layouts are managed by the XKB subsystem. For simplicity, we assume that you run both your X server and clients (at least GNOME and the setxkbmap command) on the same machine. The keyboard layouts are defined in the text files /usr/share/X11/xkb/symbols/*, e.g. the file /usr/share/X11/xkb/symbols/us contains the definition of the US English keyboard layout (and a few of its the variants). Edit one of these files (us. in the example) as root, adding your entry, e.g.

partial alphanumeric_keys modifier_keys
xkb_symbols "my_layout" {
    // A comment here.
    name[Group1]= "USA - my layout";
    key <....> { ... };
    ...
};

As soon as you save your changes, you are able to load the new layout with

$ setxkbmap 'us(my_layout)'

Please note that the command above is a bit dangerous, because if you load an incomplete or bad layout, you may have to log out (using the mouse) and log in again to make your keyboard useful. Another option is to copy the following command (which restores the US English keyboard layout) with its trailing newline to the clipboard before changing the layout, and then pasting it to a terminal emulator when things go wrong:

$ setxkbmap us

You can load multiple layouts and then use GNOME's keyboard switching applet to switch between them. For example, the following command loads the French layout by default, with an option to switch to your custom layout, and the default English layout as well:

$ setxkbmap 'fr,us(my_layout),us'

Once your layout is ready, you may want to make it selectable from the GNOME keyboard preferences dialog box (get it from System / Preferences / Keyboard / Layouts / Add, or start it with gnome-keyboard-properties, and then select Layouts / Add). To do so, you have to add your layout to the files /usr/share/X11/xkb/rules/*.{xml,lst}, close the GNOME keyboard preferences dialog box, reopen it, and then add a new layout which is yours. There is no need to log out or to restart the system. Ubuntu Karmic and Ubuntu Lucid look at evdev.xml and evdev.lst (as reported by running $ strace -e open -o key.log gnome-keyboard-properties), other systems might look at some other files, especially base.xml and base.lst.

As an example, see http://code.google.com/p/pts-mini-gpl/source/browse/trunk/pts-magyar/us.pts_magyar.sh, which is an installer shell script, which installs the us(pts_magyar) keyboard layout, modifying files /usr/share/X11/xkb/symbols/us and /usr/share/X11/xkb/rules/{evdev,base}.{xml,lst}. Here is how to install it easily:

$ wget -O- https://raw.githubusercontent.com/pts/pts-magyar/master/us.pts_magyar.sh | bash

FYI It is possible to load the config files from /usr/share/X11/xkb/symbols on one machine, and to apply it on any X server (as identified by the $DISPLAY variable). To do so, run this on the machine with the config file:

setxkbmap us -print | xkbcomp - "$DISPLAY"

2010-06-11

How to determine if two line segments intersect (in 2D)?

This blog post gives the C++ implementation of the fast schoolbook algorithm for determining if two (finite) line segments on a 2D plane intersect (cross).

static bool IsOnSegment(double xi, double yi, double xj, double yj,
                        double xk, double yk) {
  return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
         (yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}

static char ComputeDirection(double xi, double yi, double xj, double yj,
                             double xk, double yk) {
  double a = (xk - xi) * (yj - yi);
  double b = (xj - xi) * (yk - yi);
  return a < b ? -1 : a > b ? 1 : 0;
}

/** Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? */
bool DoLineSegmentsIntersect(double x1, double y1, double x2, double y2,
                             double x3, double y3, double x4, double y4) {
  char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
  char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
  char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
  char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
  return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
          ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
         (d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
         (d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
         (d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
         (d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}

The algorithm above does 8 multiplications, 16 subtractions and 52 comparisons in the worst case. But it doesn't do any divisions or square roots. If the input coordinates are integers, and the multiplications and subtractions don't yield an overflow, then the whole algorithm can be performed only with integer arithmetic.

The algorithm above doesn't return the coordinates of the intersection point. To find the intersection point of two intersecting line segments, see the formula on http://en.wikipedia.org/wiki/Line-line_intersection.

If there are many line segments and we are interested in all intersections, calling the above algorithm for all pairs is slow (quadratic). See faster algorithms (O(n*log(n))) on http://en.wikipedia.org/wiki/Line_segment_intersection

2010-06-07

How to disable the login sound and other sounds in Ubuntu Karmic

This blog post explains how to disable the login sounds and other sounds for the default GDM and the GNOME session. The solution presented here was tested on Ubuntu Karmic Koala, but there is a little probability that some parts of it would work in other versions of Ubuntu or other Linux systems.

How to disable the login drum sound and the beep sound before logging in

Run this command in a terminal window (without the $ signs):

$ sudo -u gdm gconftool-2 --type=bool --set /desktop/gnome/sound/event_sounds false
Please note that many non-working solution attempts are available on the net, some of them involving the key /apps/gdm/simple-greeter/settings-manager-plugins/sound/active or /apps/gnome_settings_daemon/plugins/sound/active, but those don't work in Ubuntu Karmic.

The sudo -u gdm part in this solution is essential, because the sound is played by GDM, which looks at the settings for the user gdm. Without that part (or with only a simple sudo) it wouldn't have any effect.

The annoying drum sound file is /usr/share/sounds/ubuntu/stereo/system-ready.ogg . Some solutions on the net suggest removing this file (and also bell.ogg). There is no need to do so.

How to disable the welcome sound after logging in

In the menu bar on the top of the screen, select System / Preferences / Startup Applications. In the appearing dialog box, scroll down to find GNOME Login Sound. Untick it. Click on the Close button.

As an alternative, it is possible to disable this sound from the command-line as well:

$ perl -pi -0777 -e 's@^X-GNOME-Autostart-enabled=.*\n@@mg;
       s@\n*\Z(?!\n)@\nX-GNOME-Autostart-enabled=false\n@' \
       ~/.config/autostart/libcanberra-login-sound.desktop

How to disable the Skype login sound after logging in

Start Skype, find its Options dialog box. Select the Notifications tab. In the tab, select Skype Login. Untick Enable Event. Click on the Apply button.

How to disable system sounds (e.g. on mouse clicks)

Run this command in a terminal window (without the $ signs):
$ gconftool-2 --type=bool --set /desktop/gnome/sound/event_sounds false
The following commands don't seem to make any difference, but they wouldn't hurt:
$ gconftool-2 --type=bool --set /apps/gnome_settings_daemon/plugins/sound/active false
$ gconftool-2 --type=bool --set \
  /apps/gdm/simple-greeter/settings-manager-plugins/sound/active false
false

How to disable application sounds (e.g. notifications and game sounds)

Run this command in a terminal window (without the $ signs):
$ gconftool-2 --type=bool --set /apps/empathy/sounds/sounds_enabled false
$ gconftool-2 --type=bool --set /apps/gnobots2/preferences/enable_sound false
$ gconftool-2 --type=bool --set /apps/gnome-power-manager/ui/enable_sound false
$ gconftool-2 --type=bool --set /apps/aisleriot/sound false
$ gconftool-2 --type=string --set /apps/nautilus/preferences/preview_sound never
$ gconftool-2 --type=bool --set /apps/gnibbles/preferences/sound false
$ gconftool-2 --type=bool --set /apps/iagno/sound false
$ gconftool-2 --type=bool --set /apps/gnect/sound false
$ gconftool-2 --type=bool --set /apps/evolution/eplugin/mail-notification/sound-enabled false
$ gconftool-2 --type=bool --set /apps/evolution/eplugin/evolution_indicator/play_sound false
The following commands don't seem to make any difference, but they wouldn't hurt:
$ gconftool-2 --type=bool --set /apps/gnome_settings_daemon/plugins/sound/active false
$ gconftool-2 --type=bool --set \
  /apps/gdm/simple-greeter/settings-manager-plugins/sound/active false

Your system might have more sounds settings if you have non-default applications installed. To find these settings, start gconf-editor, select the Edit / Find menu item, tick the box to search in keys, type sound, and click on the Search button. At the bottom of the main gconf-editor window, you'll find the matches. Browse them and disable them.

2010-06-06

How to disable the user list at the GDM login screen in Ubuntu Karmic

This blog post explains how to disable the user list at the GDM login screen. The solution presented here was tested on Ubuntu Karmic Koala, but it might work on other Ubuntu versions as well (Hardy, Interpid, Jaunty, Karmic and Lucid).

To disable the user list, run this command in a terminal window (without the $ signs):

$ sudo -u gdm gconftool-2 --type=bool --set /apps/gdm/simple-greeter/disable_user_list true

Logout and login again. You have to type your user name from now on.

How to disable Compiz Fusion and enable Metacity on Ubuntu Karmic

This blog post explains how to disable Compiz Fusion (3D desktop effects), and enable Metacity (2D) as the window manager for a GNOME session, for a single user. The solution presented here was tested on Ubuntu Karmic Koala, but it might work on other Ubuntu versions as well (Hardy, Interpid, Jaunty, Karmic and Lucid).

To disable Compiz and enable Metacity, run these commands in a terminal window (without the $ signs):

$ gconftool-2 --type=string --set \
  /desktop/gnome/applications/window_manager/current /usr/bin/metacity
$ gconftool-2 --type=string --set \
  /desktop/gnome/applications/window_manager/default /usr/bin/metacity

Logout and login again. Metacity should be running.

FYI the old setting was /usr/bin/compiz.

2010-06-02

How to add the VirtualBox keyring to Debian and Ubuntu

This blog post explains how to add the Sun and Oracle VirtualBox keyring to Debian and Ubuntu, to prevent apt-get update from complaining.

If apt-get update gives you a warning with NO_PUBKEY 54422A4B98AB5139, then do this to fix it:

$ wget -q http://download.virtualbox.org/virtualbox/debian/sun_vbox.asc -O- |
  sudo apt-key add -
$ wget -q http://download.virtualbox.org/virtualbox/debian/oracle_vbox.asc -O- |
  sudo apt-key add -
$ sudo apt-get update