Thoughtlessly Thought Thoughts

Wer sich vom Lernen mit etwas Kurzweiligen, Profanem und doch ,,mathematischem” vertreiben will, dem sei die MathSciNet Autorensuche ans Herz gelegt.

Warum? Nun, sie erlaubt die Berechnung der Erdös Zahl über ein paar Klicks.

So geht es:

• Auf diese Seite gehen (aus dem Uninetz sofern man nicht ACM-Mitglied ist, etwa per VPN)
• Namen eines Mathematikers/Informatikers oder sonst wem eingeben (etwa dem geliebten/verhassten Matheprof aus dem ersten Semester)
• Auf den “Suche” Knopf klicken
• Den Mauszeiger über den gemeinten Autor bewegen, im aufklappenden Menü “Collaboration Distance” auswählen
• Im erscheinenden Formular rechts neben dem zweiten Feld auf “Erdös einsetzen” klicken
• Voilá

Ulkig, die Theoretiker unter den Dozenten in meinem Studium haben als höchstes eine Erdös-Zahl von 3, selbst die Praktiker haben eine Einstellige.

Momentan zerreißen sich ja Anbieter von digitalisierter Musik sowie Hersteller von DRM-Mechanismen das Maul über das Thema ,,geistiges Eigentum”. Um in guter Gesellschaft zu sein möchte auch ich an dieser gegebenen Stelle einmal meinen Beitrag leisten:

Wer so viel geistiges Eigentum hat, der kann gerne mal etwas Fair Share betreiben.

Das Bild kommt übrigens von Flickr und nicht aus meiner Wohnung.

One of the nicest feature of Os X is the Keychain. The Keychain allows you to store passwords (and arbitrary text) in password protected, encrypted files.

The Keychain is used by the Os X stock applications like Safari and Mail.app but also third party programs like Cyberduck use it to store the entered passwords in the Keychain instead of rolling their own secure password storage system. I would even consider Keychain support to be an essential feature for sufficient Os X integration.

Mac Os X provides a straight API to the Keychain Service for C, Objective C and Java. Swell! What happens if there is not wrapper for your favourite programming language? For example, I could not find wrappers for Python or Ruby via Google¹.

Hm, what other programming language do I use regularly? The Shell! After all, Os X is based on BSD and provides equivalents to a lot of its UI tools as simple command line programs. The program we are searching for is known as security (man security yields a good documentation).

Creating a Keychain

We should create a new key chain for our experiments so we do not damage existing passwords. You can create a new key chain called Keys with the following command:

$> security create-keychain -P Keys.keychain

Note that you have to provide the file extension .keychain. The parameter -P will make the SecurityAgent service ask you for the password fo rthis keychain. The new keychain will be available as ~/Library/Keychains/Keys.keychain.

After creating the key chain we can open Keychain Access.app in /Applications/Utilities and add our key chain to it by selecting “Edit” > “Keychain List” in the main Menu.

Afterwards, we will see the keys - none at the moment - in our key chain.

Writing a Password

What’s next? Well, let’s add a password to the key chain:

$> security add-generic-password -a manuel -s example.com \
     -p password Keys.keychain

This will add a new password for the user manuel with the service example.com to the key chain Keys.keychain. If you do not specify a key chain then the password will be added your login key chain.

Note that specifying the password on the command line propably is not a very good idea since it will be visible to every user via ps ax while it is running. There currently is no way to make security prompt for the password so propably the best idea is to set the password using the Keychain Access.app again.

Reading a Password

Reading a password is propably the most oftenly used action - you will only want to set passwords once. Passwords are seemingly retrieved with the find-generic-password command:

$> security find-generic-password -a manuel -s example.com Keys.keychain

If you execute this command then you will get the following output:

keychain: "/Users/manuel/Library/Keychains/Keys.keychain"
class: "genp"
attributes:
...

Well, this is pretty uninteresting. We wanted the password! So we read up the manual of security once more and see that we have to specify the -g password to make security print the actual password. So, let’s try it again. When entering

$> security find-generic-password -g -a manuel \
     -s example.com Keys.keychain

then a window will pop up and ask us for the password of our key chain. After entering the password, we will get the following output:

keychain: "/Users/manuel/Library/Keychains/Keys.keychain"
class: "genp"
attributes:
...
password: "password"

As we find out here, the last line is written to stderr (what the hack?) and the rest is written to stdout. So we tell bash to redirect the output of the stderr to a copy of the stdout file handle and redirect the old stdout to /dev/null (note that the order of the 2>&1 and >/dev/null is important):

$> security 2>&1 >/dev/null find-generic-password -g \
     -a manuel -s example.com Keys.keychain

We are only interested in the password so pipe the output through sed and put the whole stuff into a bash function:

get_password () {
  security 2>&1 >/dev/null find-generic-password -g \
    -a manuel -s example.com Keys.keychain \
  | sed 's/password: "\(.*\)"/\1/'
}

So the next time we need a password, we can simply use $(get_password) to get it from the keychain. For example:

#!/bin/sh

get_password () {
  security 2>&1 >/dev/null find-generic-password -g \
    -a manuel -s example.com Keys.keychain \
  | sed 's/password: "\(.*\)"/\1/'
}

# We said passing passwords on the command line was bad above. We
# only do this here for the sake of a simple example.
wget --user=manuel --password=$(get_password) http://example.com

This is part 1 of 2. The second part deals with how to integrate the Keychain into your Ruby application (and shows how to do this with Capistrano). I will publish the second part soon.

¹ Of course there are Cocoa bindings for Python and Ruby but aren’t those a bit heavyweight for using so simple as the Keychain Service?

Not every algorithm and data structure that is fast and elegant has to be highly sophisticated. Sometimes, there are solutions to problems that are very simple and the hard thing is to realize of effective they despite their simplicity.

Free lists are a very good example of this. Free lists are linked lists that are stored inside your data structures that keep track of unused entries.

Let us consider a simple example to introduce them. Suppose we have a data structure that allows us to store the name and the address of a customer (hopefully correct C98):

 1 struct customer_s
 2 {
 3   char[100] name;
 4   char[200] address;
 5 };

Now we want to manage an arbitrary number of instances of this data structure. So the obvious thing to do is to define an array of it:

#define MAX_CUSTOMER 1000000
struct data_s arr[] = malloc(MAX_CUSTOMER * sizeof(struct data_s));

We now have an array of our data structure and can fill it. However, as soon as we start to use this array we notice that we cannot decide whether an entry of the array is actually used. So we add a flag to the data structure that stores whether the entry is used. Of course we have to initialize our new array:

 1  struct customer_s
 2  {
 3    int used;
 4    char[100] name;
 5    char[200] address;
 6  };
 7
 8  struct data_s customers[] = malloc(MAX_CUSTOMER * sizeof(struct data_s));
 9
10  for (int i = 0; i < MAX_CUSTOMER; i++) arr[i].used = FALSE;

Jolly good! We can now start to use our customer array. However, after having written our customer management application we realize that it is very slow. Search customers is slow but we expected this for they are not ordered.

However, inserting a new entry is also very slow! We run our code through a profiler and determine the root of all evil in the function that inserts a new customer:

 1  /* search free array entry */
 2  int next_customer = -1;
 3  for (int i = 0; i < MAX_CUSTOMER; i++) {
 4    if (!customers[i].used) {
 5      next_customer = i;
 6      break;
 7    }
 8  }

When we have a lot of customers in our array then inserting a new one forces us to look at each existing customer entry! We can certainly speed this up a bit. Consider the improved data structures:

 1  struct customer_s
 2  {
 3    int used;
 4    int next;
 5
 6    char[100] name;
 7    char[200] address;
 8  };
 9
10  struct customer_arr_s
11  {
12    int first_free;
13
14    struct customer_s arr[];
15  }
16
17  struct customer_list_s customer_list;
18
19  /* initialization */
20  function create_customer_arr(struct customer_arr_s *customer_list)
21  {
22    customer_list->arr = malloc(MAX_CUSTOMER * sizeof(customer_s));
23
24    for (int i = 0; i < MAX_CUSTOMER; i++) {
25      customer_list->arr[i].used = FALSE;
26      customer_list->arr[i].next = i + 1;
27    }
28    customer_list_s->arr[MAX_CUSTOMER - 1].next = -1;
29
30    customer_list->first_free = 0;
31  }
32
33  int main(/* … */) {
34    struct customer_arr_s customer_arr;
35
36    create_customer_arr(&customer_arr);
37  }

What’s happening? First, look at struct customer_s. We have extended the data struct by one value: next. This value stores the index of the next element in the free list. The elements in this list are the entries of the customer array which are currently not used. The last element in the list has no next element so it’s next value will be -1.

How do we get the first element of the list? We introduce the data structure customer_arr_s which contains the actual array of customer_s elements and also stores the index of the first unused element.

Now the code to allocate the next free element in the list looks as follows:

int next_free = customer_arr.first_free;
customer_arr.first_free = customer_arr.arr[customer_arr.first_free].next;

Thus, we can guarantee that allocating a new entry in the list takes constant time. Freeing the ithe element is possible in constant time, too:

customer_arr.arr[i].next = customer_arr.first_free;
customer_arr.first_free = i;

Of course, free lists may seem superficial if you are used to dynamic high level like Python or Ruby since you can simply remove elements in the middle of “Array” etc.

But remember that there are places where plain C-style arrays make sense: In operating systems, embedded applications and generally all other places where memory usage and speed is essential.

Bzw. ich lasse das mein Lieblings-D-Sternchen machen:

Kudos an Jochen!