» Tinkering with meta tools

January 20, 2017 | english linux opinion | Adrian Kummerländer

If the contents of this website are of interest to you chances are that you also know how easy it is to spend large parts of one's leisure time tinkering with computer systems and improving workflows while losing sight of what one actually wants to accomplish. I am going to use this article to document parts of my current personal computing setup in an attempt to summarize and refocus my efforts in this direction in addition to articulating some of my thoughts in this context.

Working with computers is my job to the extend that computers are the machines that my software developing self instructs to - hopefully - solve actual problems in the real world™. This means that configuring and optimizing my personal computing environments is not only a leisure time activity but can be considered a productive activity within certain boundaries1. If I think of time consuming optimization-activties that are definitely yielding payoff in my day to day work a few things come to mind: Learning and mastering a single powerful text editor2, switching to an open operating system and using open source software wherever possible, using a tiling window manager, version control everything, maintaining a private internet archive, frequently experimenting with new programming languages and paradigms as well as studying mathematics. I am going to use the following sections to further explore some of these activities.

Text editing

Plain text is still the most used format for expressing and storing program instructions for all common and nearly all uncommon languages out there. Although the simplicity and thus flexibility of plain text continues to cause distracting discussions around topics such as tabs-vs-spaces3 there sadly are no usable alternative in the vein of e.g. generalized tree encodings available at this point in time. S-Expressions could probably be used as a foundation for such an alternative but alas we don't live in the alternative time line where the adoption of a LISP as the internet's scripting language instead of the quickly hacked together thing that is JavaScript caused a widespread rise of LISP-like languages culminating in all common languages being LISP-dialects and thus being expressible in sexprs.

To return the topic at hand: plain text it is and will continue to be for the foreseeable future. If one looks for powerful, widely available and extensible text editors the choice will in most cases come down to the still reigning giants Vim and Emacs 4.
When I stood before this decision nearly half a lifetime ago5 my choice fell on Vim. If one only considers the default editing interface this definitely was the right choice for me as I would not trade Vim's modal text manipulation language for overly long default Emacs key chords. But I have to admit that I regularly take wistful looks at some of the applications available inside Emacs such as Org-mode. Had I already discovered the joys of LISP when I was trying to decide between the two editors I probably would have chosen Emacs. Luckily one can always alter such decisions - sooner or later I will probably settle on some kind of Evil based setup just to be able to use the text based operating system that is Emacs.

a Vim session in its natural environment

Altough the 122 lines including comments that currently make up most of my Vim configuration are not much by most standards I have invested quite some time in setting the editor up to my taste - not the least by writing my very own color scheme to match the rest of my primary desktop environment.

Over time I have grown so accustomed to Vim's keybindings that I now use them wherever possible including but not restricted to: my web browser, PDF reader, various IDEs, image viewer and window manager of choice.

Operating system and desktop environment

ArchLinux continues to be the Linux distribution of choice for most of my computing devices. It offers most of the flexibility of Gentoo if one needs it while preserving fast installation and frequent updates of most of the software I require. The only feature I currently miss and that will probably lead me switch distributions sooner or later is declarative package management as offered by NixOS or GuixSD. A fully declarative configuration of my Linux installation in a plain-text and thus easily version controllable file would be the logical conclusion of my current efforts in managing system configurations: /etc is tracked using etckeeper, various dotfiles are tracked using plain git and GNU stow for symlink management.

Example of a basic i3 session

My choice of desktop environment has converged on a custom setup built around the i3 tiling window manager over the last couple of years. I have adopted the tiling concept to such a degree that I struggle to think of a single advantage a common - purely floating - window manager might hold over tiling window managers. This holds especially true if your workflow is similar to mine, i.e. you have lots and lots of terminals and a few full screen applications running at most times as well as a fondness for using the keyboard instead of shoving around a mouse.

More complex unstaged example of a i3 session

What I like about i3 in particular is that it doesn't enforce a set of layouts to toggle between like some other tiling WMs but allows you full control over the tree structure representing its layout. Another nice feature is that it lends itself to Vim-style keybindings as well as offering good support for multi monitor setups.

Compared to a desktop environment such as KDE a custom setup built around a window manager obviously requires much more configuration. In exchange for that I gained full control over my workflow in addition to basically instantaneous interaction with the system and its applications.

I find it very useful to have a certain set of information available at all times. Examples for such information are dictionary definitions, language and framework documentation, login credentials and notes. For this purpose I wrote a set of scripts that enable me to query a local dict daemon6, note folders and passman entries using the dmenu-replacement Rofi. In addition to that i3's scratchpad feature is very useful for keeping Zeal and Vim instances running in the background while preserving accessability in every context by displaying them in a floating window overlaying the current workspace.

Archiving, web browsing and note taking

An important purpose of the tool we call Computer is accessing information on the Internet. This task is achieved primarily using a web browser - in fact there is an argument to be made that web browsers are some of the most complex applications the average users comes into contact with.
I sometimes frown at the wasteful complexity many of today's websites contain even if their actual contents still consist of mostly plaintext and some pictures. It is no longer the exception but the rule that a single load of common websites pulls more data over the wire than would be required to encode a whole book while often containing far less content. These are the moments where I wish that Gopher had gained wider usage or that something in the vein of ipfs will grow to encompass most of the sources I commonly use7.

Current Pentadactyl, TreeStyleTabs and ScrapBook X augmented Firefox setup

As one can see in the screeshot above the current browser setup I use to deal with this rather unsatisfying state of things is a quite customized version of Firefox. This is achieved using Pentadactyl, TreeStyleTabs and ScrapBook X.

Pentadactyl transforms Firefox into a fully keyboard driven browser with Vim-like keybindings and looks as well as the possibility of configuring the browser using a single dotfile .pentadactylrc.

TreeStyleTabs allows me to better manage my workflow of keeping all tabs related to my current projects and interests opened as well as grouped in a tree structure. While Vim-like keybindings can be configured in other browsers, usable TreeStyleTabs like tab management is currently only available on Firefox.

ScrapBook X is my current answer to a question I have spent quite some time thinking about: How to best archive and organize interesting documents on the web. ScrapBook allows reasonably good offline archival of websites, organizing archived pages in a folder structure and exporting a HTML version of itself for hosting a private Internet Archive. It doesn't work perfectly on all websites and uses plain file mirroring instad of the more suitable WARC format but it is the best solution I was able to find short of investing most of my time into attemting to develop something more to my taste.
For now it is good enough and fullfills my primary use cases: Having access to most of my sources independent of network availability8, preventing the unpleasant situation of wanting to consult a vaguely remembered source only to find that it is not available anymore as well as full text search over all interesting pages I visited.

Archiving the web ties into the last section of this article: note taking. While I write all my lecture notes and excercise sheet solutions using pen input on one of Microsoft's Surface9 devices I like to capture project and research notes as well as general thoughts using a keyboard on my normal computer.
When taking notes as plain text I preferably want to do so using Vim which rules out most of the already relatively limited selection of open source desktop wiki software. After quite some time using VimWiki I currently use markdown files stored in a flat directory structure. Desktop integration is solved using a background Vim instance running in a i3 scratchpad as well as a Rofi based note selection dialog that communicates with Vim using remote commands. Advanced markdown features, syntax highlighting and conversion is based on pandoc integration plugins.
In addition to that I also now and then play around with Emacs' Org-mode which can probably fulfill most of my requirements but requires considerable upfront configuration efforts to make it work consistently with Evil for Vim-style usage.

Vision

While the setup outlined above is workable I definitely do not consider it a permanent solution. Even more so I feel that there is much unexplored potential in augmenting not just note taking but formal and exploratory thinking in general using computers. What I mean by that are systems as they were envisioned in the form of the Memex or as described by Engelbart in Augmenting Human Intellect10.

Such a system would not only encompass note taking and knowledge management but form an intergral part of the user facing operating system. Everything you see on a screen should be explorable in the vein of Lisp Machines or Smalltalk instances, annotatable in a fully interlinkable and version controlled knowledge base that transparently integrates information from the Internet in a uniform fashion as well as shareable with other beings where required.
Formal verification software could look over the figurative shoulder of the user and point out possible fallacies and formal errors. Even a single component of such a system like for example a math environment that pulls up appropriate definitions, theorems and examples depending on the current context or a literate development environment that automatically pulls up documentation, stackexchange threads and debugging output would be of great help.
Usage tracking similar to Gnome Zeitgeist in conjunction with full text archival of all visited websites and fully reproducible tracking of the desktop state would also complement such a system.

In conclusion: My current setup doesn't even scratch the surface of what should be possible. Tinkering with my computing systems and workflow-optimization will continue to be an unbounded but at least somewhat productive leisure time sink.

  1. ...that I have probably crossed frequently

  2. Section 16, Power Editing, The Pragmatic Programmer.

  3. Tabs for indentation, spaces for alignment it is for me - this is probably the reason for my dislike of whitespace-dependent languages that tend to interfere with this personal preference of mine.

  4. Desktop-only text editors - especially those Electron based ones written in HTML and JavaScript of all things - are not an alternative for my use cases. Although at least VSCode is developing nicely into a usable cross platform IDE.

  5. Luckily not that long in my case :-)

  6. Serving a collection of freely available dictionaries such as Webster's 1913 and Wordnet

  7. Note to self: Make the raw markdown sources (?) of this blog available on ipfs

  8. e.g. when riding the black forest train from Karlsruhe to my home village in the Hegau.

  9. The only non-Linux device I regularly use. Pen input on tablet devices has reached a point of general viability (concerning power usage and form factor) in recent years. I am actually very satisfied with my Surface 4 and Windows 10 as both a note taking and tablet device. For tinkering and security reasons I still hope to one day be able to use an open operating system and open note taking software on such a device but for now it is a workable solution for my use case of studying (mostly) paperless.

  10. AUGMENTING HUMAN INTELLECT : A Conceptual Framework., October 1962, D. C. Engelbart

» Visualisierung von Metriken in Voronoi-Diagrammen

May 22, 2016 | cpp development german math | Adrian Kummerländer

In der Analysis 2 Vorlesung meines Mathematik Studiums beschäftigen wir uns derzeit mit Normen und Metriken in endlich dimensionalen Vektorräumen, welche wiederum die Grundlage für die Übertragung der, aus Analysis 1 bekannten, Konvergenz und Stetigkeitsbegriffe in höhere Dimensionen schaffen. Während der Bearbeitung der entsprechenden Übungsblätter habe ich dabei nach Visualisierungsmöglichkeiten recherchiert, um eine bessere Intuition für diese Begriffe zu erlangen. Voronoi-Diagramme sind eine solche Möglichkeit, deren Grundlagen und Generierung ich in diesem Artikel zwischen Theorie und Praxis näher erläutern möchte.

Normen und Metriken in endlichdimensionalen Vektorräumen

In der herkömmlichen Schulmathematik sowie alltäglichen Rechnungen definieren wir Begriffe wie die Größe einer Zahl und den Abstand zwischen zwei Zahlen implizit über deren Betrag beziehungsweise die Differenz ab\vert a-b \vert mit a,bRa, b \in \mathbb{R} 1. Diese implizite, ja intuitive Definition der genannten Begriffe reicht für vieles aus, gelangt aber schnell an ihre Grenzen, wenn wir das Ganze, im Rahmen der mathematischen Arbeit des Beweisens, auf formale Grundlagen stellen und als Fundament für Aussagen in anderen Mengen als den herkömmlichen Zahlen nutzen wollen.

Mit nicht herkömmlichen Zahlen meine ich dabei Elemente aus Vektorräumen2 wie R2\mathbb{R}^2. Zumindest für diesen, mittels eines Kartesischen Koordinatensystems als zweidimensionale Ebene darstellbaren, Vektorraum, haben wir in der Schule eine Vorstellung bekommen. Dies trifft sich gut, da sich auch die Visualisierung von Metriken mittels Voronoi-Diagrammen in diesem Raum abspielen wird.

Betrachten wir zunächst den Begriff der Größe oder auch des Betrags einer Zahl. Dieser wird für Elemente eines Vektorraums, also Vektoren, über Normen beschrieben. Eine Norm ist dabei formal eine Abbildung :VR0\| \cdot \| : V \rightarrow \mathbb{R}_{\geq0}, also eine Funktion, die Elementen aus einem K\mathbb{K}-Vektorraum VV3 einen reellen Wert größer oder gleich Null zuordnet.
Diese Funktion darf dabei nicht vollkommen beliebig definiert sein, sondern muss für x,yVx, y \in V sowie αK\alpha \in \mathbb{K} die folgenden Bedingungen erfüllen:

Definitheit x=0x=0\|x\|=0 \Leftrightarrow x=0
Homogenität αx=αx\|\alpha * x\|=\alpha * \|x\|
Dreiecksungleichung x+yx+y\|x+y\| \leq \|x\| + \|y\|

Diese Anforderungen bedeuten, dass eine Funktion genau dann als Norm gesehen werden kann, wenn sie nur den Nullvektor auf die reelle Null abbildet, Skalare analog zu linearen Ausrücken herausgezogen werden können und ein Umweg zwischen zwei Punkten nie kürzer ist, als der direkte Verbindungsweg.

Betrachten wir an dieser Stelle die Defintion der häufig verwendeten Klasse der p-Normen:

xp:=(i=1nxip)1pmitxRn,pR1\displaystyle \|x\|_p := \left(\displaystyle\sum_{i=1}^{n} \vert x_i \vert ^p\right)^\frac{1}{p} \; \text{mit} \; x \in \mathbb{R}^n ,\; p \in \mathbb{R_{\geq1}}

Beachtenswerter Weise geht aus dieser Norm für p=1p=1 die Betragsnorm, also die Aufsummierung aller Komponentenbeträge des gegebenen Vektors, sowie für p=2p=2 die sogenannte Euklidische Norm hervor. Durch Verschieben von pp im Intervall [1,][1, \infty] lässt sich dabei die charakteristische Rautenform der Einheitskugel4 der Betragsnorm über die tatsächlich kugelförmige Einheitskugel der Euklidischen Norm in die quadratische Form der Maximumsnorm überführen (pp \rightarrow \infty).

Veränderung der abgeschlossenen Einheitskugel unter der p-Norm für p zwischen 1 und 3

Kommen wir nun zum Begriff des Abstands zwischen zwei Zahlen, welcher in Form von Metriken auf algebraische Strukturen wie Vektorräume übertragen wird. Wie in der Einführung dieses Abschnits beschrieben, haben wir den Abstand zwischen Zahlen schon in der Schule über den Betrag der Differenz beschrieben. Wir kennen an dieser Stelle in Form des Satz des Pythagoras auch schon eine sinnvolle Definition für den Abstand zwischen Punkten in R2\mathbb{R}^2:

d(x,y):=x1x22y1y22mitx,yR2\displaystyle d(x,y) := \sqrt{\vert x_1-x_2 \vert ^2 - \vert y_1-y_2 \vert ^2} \; \text{mit} \; x, y \in \mathbb{R}^2

Diese Metrik über dem zweidimensionalen reellen Vektorraum lässt sich, auf folgende naheliegende Art und Weise, in eine Metrik für alle endlich dimensionalen R\mathbb{R}-Vektorräume erweitern:

d(x,y):=i=1nxiyi2mitx,yRn\displaystyle d(x,y) := \sqrt{\displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert ^2} \; \text{mit} \; x, y \in \mathbb{R}^n

Diese Metrik auf Grundlage des Satz des Pythagoras wird als Euklidische Metrik bezeichnet. Sie ist eine der Metriken, welche wir im weiteren Verlauf dieses Artikels in Voronoi-Diagrammen visualisieren werden.

Die Definition solcher Metriken als Abbildungen der Form d(x,y):V×VR0d(x,y) : V \times V \rightarrow \mathbb{R}_{\geq0} beinhaltet eine Menge von Axiomen, welche von der Metrik-Abbildung erfüllt sein müssen.

Positive Definitheit d(x,y)0d(x,y)=0x=yd(x,y) \geq 0 \land d(x,y)=0 \Leftrightarrow x=y
Symmetrie d(x,y)=d(y,x)d(x,y) = d(y,x)
Dreiecksungleichung d(x,z)d(x,y)+d(y,z)d(x,z) \leq d(x,y) + d(y,z)

Wir fordern also, dass der Abstand zwischen beliebigen Punkten immer größer gleich Null sein muss, ein Nullabstand äquivalent zur Gleichheit der Punkte ist, die Reihenfolge der Punkte für den Abstand irrelevant ist und das der direkte Abstand zwischen zwei Punkten kleiner gleich einem Umweg über weitere Punkte ist.

Bei der Betrachtung der Definitionen von p-Norm und Euklidischer Metrik fällt auf, dass diese sich zu ähneln scheinen. Dies ist kein Zufall, denn Metriken können aus Normen induziert werden. So folgt die Euklidische Metrik mit d(x,y):=xy2d(x,y) := \|x-y\|_2 direkt aus der 2-Norm.

Es liegt also Nahe, dass auch aus die Betragsnorm mit p=1p=1 eine Metrik induziert - die sogenannte Mannheimer-Metrik:

d(x,y):=i=1nxiyimitx,yRn\displaystyle d(x,y) := \displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert \; \text{mit} \; x, y \in \mathbb{R}^n

Die Bezeichnung dieser Metrik als Mannheimer-, Manhattan oder auch Taxi-Metrik wird nachvollziehbar, wenn wir uns bewusst machen, dass sie die Betragsdifferenzen der Punkte aufsummiert und somit den Weg beschreibt, den ein Taxi in einem Straßenraster nachvollziehen müsste, wie es in Mannheim und zahlreichen nordamerikanischen Städten üblich ist, um von A nach B zu gelangen.

Wir haben also nun zwei Metriken kennengelernt, die beide für verschiedene pp aus der gleichen p-Norm hervorgehen. Die Mathematik charakterisierende Suche nach gemeinsamen Mustern in abstrakten Strukturen legt nahe, dass so, wie die Betragsnorm und die Euklidische Norm Varianten der allgemeineren Klasse der p-Normen sind, auch die Mannheimer und Euklidische Metrik Varianten einer allgemeineren Klasse von Metriken sind. Diese allgemeinere Klasse beschreiben wir in Form der Minkowski-Metrik:

d(x,y):=(i=1nxiyip)1pmitx,yRn,pR+\displaystyle d(x,y) := \left(\displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert ^p\right)^\frac{1}{p} \; \text{mit} \; x, y \in \mathbb{R}^n ,\; p \in \mathbb{R_+}

Die Beschreibung der Euklidischen und Mannheimer-Metrik als Varianten der Minkowski-Metrik ist damit gerechtfertigt, dass diese für p=1p=1 beziehungsweise p=2p=2 aus ihr hervorgehen.

Besonders interessant ist im Kontext der Visualisierung von Metriken, dass die Minkowski-Metrik für p[1,2]p \in [1, 2] einen stetigen Übergang von der Mannheimer in die Euklidische Metrik ermöglicht. Dies ergibt schöne, flüssige Voronoi-Diagramme, wie wir im Abschnitt zu bewegten Bildern sehen werden.

Voronoi-Diagramme

Nachdem wir uns im vorangehenden Abschnitt einen groben Überblick über Normen und Metriken in endlich dimensionalen reellen Vektorräumen gemacht haben, können wir uns nun dem eigentlichen Thema dieses Artikels zuwenden: der Visualisierung von Metriken in Voronoi-Diagrammen.

Unter Voronoi-Diagrammen verstehen wir die Aufteilung der Euklidischen Ebene in disjunkte Teilflächen abhängig der Distanz zu einer gegebenen Menge von Punkten und gekennzeichnet durch entsprechende Einfärbung entsprechend des jeweils nächsten Punktes.

Im Falle der Euklidischen Metrik, d.h. der Minkowski-Metrik mit p=2p=2, ergeben sich somit Grafiken wie die folgende:

Voronoi-Diagramm der Minkowski-Metrik mit p=2

Während wir die Definitionen der Metriken bisher im Speziellen für R2\mathbb{R}^2 betrachtet haben, gerät der zugrundeliegende Körper R\mathbb{R} mit der konkreten Generierung von Voronoi-Diagrammen als Pixelgrafiken in Konflikt, da wir offensichtlich nicht alle Punkte der Teilflächen bzw. Mengen darstellen können. Die naheliegendste Lösung für dieses Problem ist, die Metriken nur auf Z2\mathbb{Z}^2 zu betrachten. Dies ist einfach möglich, da Z2\mathbb{Z}^2 eine echte Teilmenge von R2\mathbb{R}^2 ist und eine triviale Bijektion zwischen Punkten in Z2\mathbb{Z}^2 und Pixeln auf einem Bildschirm existiert.

Voronoi-Diagramm der Minkowski-Metrik mit p=1

Die konkrete Generierung von Voronoi-Diagrammen ist dann einfach möglich - es müssen nur die Punkte der, dem gewünschten Sichtbereich entsprechenden, Teilmenge von Z2\mathbb{Z}^2 durchlaufen und abhängig ihrer Distanz zu den Referenzpunkten unter der gewünschten Metrik eingefärbt werden.

double minkowski_metric(
    const double         p,
    const imgen::vector& a,
    const imgen::vector& b
) {
    return std::pow(
          std::pow(std::abs(std::get<0>(a) - std::get<0>(b)), p)
        + std::pow(std::abs(std::get<1>(a) - std::get<1>(b)), p),
        1.0 / p
    );
}

Zur Approximation der Bildmenge R0\mathbb{R}_{\geq 0} der Metrik-Funktionen verwenden wir double Werte, während die Ursprungsmenge R2×R2\mathbb{R}^2 \times \mathbb{R}^2 über zwei Tupel des Typs std::tuple<std::ptrdiff_t, std::ptrdiff_t> in unserer Implementierung abgebildet wird.

Die obige Implementierung der Minkowski Metrik in C++ genügt zusammen mit folgendem, auf einer kleinen PPM Grafikbibliothek basierendem, Listing zur Generierung von Voronoi-Diagrammen über einer fixen reference_vectors Punktmenge für beliebige pp.

std::pair<double, imgen::colored_vector> get_distance_to_nearest(
    const std::function<double(imgen::vector, imgen::vector)>& metric,
    const imgen::vector a
) {
    constexpr std::array<imgen::colored_vector, 9> reference_vectors{
        imgen::colored_vector{   0,    0, imgen::red()                },
        imgen::colored_vector{ 240,  200, imgen::color{220, 220, 220} },
        imgen::colored_vector{-100,  230, imgen::color{ 94, 113, 106} },
        imgen::colored_vector{ 120, -100, imgen::color{140, 146, 172} },
        imgen::colored_vector{ -42, -200, imgen::color{128, 128, 128} },
        imgen::colored_vector{ 120,   40, imgen::color{ 16,  20,  22} },
        imgen::colored_vector{-150,   50, imgen::color{192, 192, 192} },
        imgen::colored_vector{  60, -128, imgen::color{178, 190, 181} },
        imgen::colored_vector{-240,  -20, imgen::color{ 54,  69,  79} }
    };

    // [...] Bestimmung des nächsten Referenzvektors unter der gegebenen Metrik

    return std::make_pair(*minimal_distance, nearest);
}

void generate_minkowski_voronoi(const double p) {
    const auto metric{[p](const imgen::vector a, const imgen::vector b) -> 
    double {
        return minkowski_metric(p, a, b);
    }};

    imgen::write_ppm(
        "voronoi_" + std::to_string(p) + ".ppm",
        512,
        512,
        [&metric](std::ptrdiff_t x, std::ptrdiff_t y) -> imgen::color {
            const auto& nearest = get_distance_to_nearest(
                metric,
                imgen::vector{x, y}
            );

            if ( nearest.first <= 5.0 ) {
                return imgen::black();
            } else {
                return std::get<2>(nearest.second);
            }
        }
    );
}

Die Punktmenge ist dabei die, welche in obigen Beispiel Diagrammen zu betrachten ist. Alles, was wir an dieser Stelle über die zentrale Funktion imgen::write_ppm wissen müssen, ist, dass diese formell ein Bild über der Menge M:={(x,y)Z2x[w2,w2]y[h2,h2]}M := \{(x, y) \in \mathbb{Z}^2 \vert \: x \in [-\frac{w}{2}, \frac{w}{2}] \land y \in [-\frac{h}{2}, \frac{h}{2}]\} mit Höhe hh und Breite ww aufspannt und für (x,y)M\forall \: (x, y) \in M die gegebene Funktion Z×Z[255]×[255]×[255]\mathbb{Z} \times \mathbb{Z} \rightarrow [255] \times [255] \times [255] aufruft, wobei die Tupel ihrer Bildmenge als Farben interpretiert werden.

Zur Kennzeichnung der Referenzvektoren wird jeweils eine abgeschlossene Kugel unter der verwendeten Metrik mit Radius 5 gezogen. Dies hat den schönen Nebeneffekt, dass wir anhand der Form der Punktmarkierungen schon Rückschlüsse auf die zur Generierung verwendete Metrik ziehen können, da die Markierungen nur skalierte Versionen der Einheitskugel sind, welche wir im vorangehenden Abschnitt besprochen haben.

Der komplette Quellcode der aufgeführten Beispiele ist auf Github und cgit unter der MIT Lizenz frei verfügbar und kann so zur Generierung eigener Voronoi Diagramme herangezogen werden.

Minimalistische Generierung von Pixelgrafiken in C++

Wie bereits angedeutet, basiert der hier gewählte Weg zur Generierung von Voronoi-Diagrammen auf einer minimalistischen C++ Grafikbibliothek, welche im Rahmen meiner Experimente zu diesem Thema entstanden ist. Die Ursache dafür war, dass ich von vornherein nur einfache Pixelgrafiken generieren wollte und keinerlei Bedarf für die Vielfalt an Funktionalität hatte, wie sie von Grafikbibliotheken wie Cairo dargeboten wird. In solchen Situationen empfielt es sich, dass entstehende Program nicht mit Abhängigkeiten zu großen Frameworks zu überfrachten, sondern das Problem auf das Essenzielle zu reduzieren. In unserem Fall also die Iteration über eine gegebene Bildmenge und die Zuweisung von Farben zu Punkten. Andere Probleme wie Kompression und Animation in GIF Grafiken sind dann besser spezialisierten Werkzeugen wie Imagemagick überlassen.

Eines der wohl einfachsten Dateiformate für Pixelgrafiken ist das Portable PixMap Format, dass nur aus der magischen Zahl P6 gefolgt von Zeilenumbruch-separierter Breite und Höhe sowie einem Stream der Bildpunkte bestehend aus je drei Bytes für Rot, Grün und Blau in dieser Reihenfolge besteht. Dieses primitive Format führt dazu, dass die im Beispiel verwendete imgen::write_ppm Funktion sehr einfach zu implementieren ist:

void write_ppm(
    const std::string&                                   path,
    const std::size_t                                    width,
    const std::size_t                                    height,
    std::function<color(std::ptrdiff_t, std::ptrdiff_t)> generator
) {
    ppm_pixel_stream file(path, width, height);

    const std::ptrdiff_t min_y = height / 2 * -1;
    const std::ptrdiff_t max_y = height / 2;
    const std::ptrdiff_t min_x = width  / 2 * -1;
    const std::ptrdiff_t max_x = width  / 2;

    for ( std::ptrdiff_t posY = max_y; posY > min_y; --posY ) {
        for ( std::ptrdiff_t posX = min_x; posX < max_x; ++posX ) {
            file << generator(posX, posY);
        }
    }
}

Den inhärenten Mehraufwand der Verwendung von std::function zur Übergabe der Callbacks für Generierung und Metriken und der Ausgabestreams des Standards in imgen sowie der eigentlichen Diagram-Generierung akteptiere ich an dieser Stelle der Klarheit und des Vertrauens in den Compiler wegen. Weiterhin lässt sich die Performance von vielen repetiven Generierungen - die ohnehin nicht an der Ein-Ausgabe-Performance sondern an den konkreten Berechnungen hängt - über Multithreading in verkraftbare Schranken weisen.

Bewegte Bilder

Das in meinen Augen schönste Resultat dieses Artikels ist die Visualisierung der Transformation von der Mannheimer in die Euklidische Metrik in Form der folgenden GIF Animation:

Übergang von der Mannheimer in die Euklidische Metrik und zurück

Diese Grafik kann dabei vollautomatisch über das, auf Imagemagick basierende, Script voronoi.sh rekonstruiert werden. Da die Generierung der für die Animation notwendigen zahlreichen Einzelbilder von Voronoi-Diagrammen mit langsam ansteigendem pp etwas Zeit kosten kann, lohnt sich die Optimierung durch Aufteilen des Arbeitsaufwands auf mehrere Verarbeitungsstränge. Dies ist einfach möglich, da wir keinerlei veränderliche Daten zwischen einzelnen Voronoi-Diagrammen teilen müssen. Da der Standard mittlerweile schon seit einigen Jahren Unterstützung für Multithreading bietet, gestaltet sich auch die konkrete Umsetzung dieser Optimierung erfreulich kompakt.

void generate_parallel_minkowski_voronoi(
    const unsigned int thread_count,
    const double       lower,
    const double       upper,
    const double       epsilon
) {
    std::vector<std::thread> threads;

    const double step = ( upper - lower ) / thread_count;
    double offset     = lower;

    while ( threads.size() < thread_count ) {
        threads.emplace_back([offset, step, epsilon]{
            generate_minkowski_voronoi(
                offset,
                offset + step,
                epsilon
            );
        });

        offset += step;
    }

    generate_minkowski_voronoi(upper);

    for ( auto& thread : threads ) {
        thread.join();
    }
}

Rückblick

Hiermit sind wir am Ende meines ersten textuellen Ausflugs an die Schnittstelle zwischen Mathematik und Software angelangt. Ich hoffe an dieser Stelle, dass die Ausführungen und Beispiele verständlich waren und ich mich, am Anfang meines Studiums der Mathematik stehend, nicht in formelle Fehler verstrickt habe.

Grundsätzlich finde ich Voronoi-Diagramme hilfreich, um eine visuelle Intuition für die Auswirkungen verschiedener Metriken zu gewinnen - gleichwohl diese in höheren Dimensionen schnell in ihrem Nutzen schwindet. Aber auch abgesehen vom praktischen Aspekten sind diese Diagramme eine schöne Möglichkeit in etwas anschaulicherem Kontext mit Mathematik zu spielen und schöne Bilder zu erzeugen.

Ansätze zum Ausbau der im Rahmen dieses Artikels entstandenen Programme - an dieser Stelle noch einmal der Hinweis auf die Quellen bei Github und cgit - sind verschiedene Metriken in einem Diagramm zu mischen oder zu gewichten sowie sich praktische Einsatzszenarien für Voronoi-Diagramme anzuschauen. Wenn die Grafiken beispielweise bei dem ein oder anderen meiner Leser die Erinnerung an Strukturen in der Natur wie Bienenwaben oder aufeinandertreffende Seifenblasen geweckt haben, dann liegt das daran, dass sich Prozesse dieser Art tatsächlich über Voronoi-Diagramme betrachten lassen. Der entsprechende Wikipedia-Artikel liefert hier als Abschluss eine Auflistung zahlreicher Anwendungsbeispiele.

  1. R\mathbb{R} könnte an dieser Stelle auch die Menge N\mathbb{N} der natürlichen Zahlen, die Menge C\mathbb{C} der komplexen Zahlen oder ein beliebiger anderer Körper sein, für den der Betrag definiert ist.

  2. Ein Vektorraum ist eine Menge von Vektoren gleicher Dimension, für welche die Operationen der Vektoraddition und Skalarmultiplikation sinnvoll definiert sind. Eine sinnvolle Definition dieser Operationen schließt neben einigen Rechenregeln mit ein, dass ein unter der Addition neutrales Element, der Nullvektor, sowie ein unter der Skalarmultiplikation neutraler Skalar, das Einselement, existieren. Zusätzlich muss zu jedem Vektor ein bezüglich der Addition inverses Element existieren, d.h. ein vVv \in V mit v+v=0v + -v = 0. Zusammenfassend führen diese Anforderungen dazu, dass innerhalb eines Vektorraums in weitgehend gewohnter Art und Weise gerechnet werden kann.

  3. Der Begriff K\mathbb{K}-Vektorraum sagt aus, dass alle Komponenten der enthaltenen Vektoren Elemente aus dem Körper K\mathbb{K} sind. Im Falle eines R\mathbb{R}-Vektorraums sind also beispielsweise alle Komponenten aller Vektoren reelle Zahlen. Der Körper ist dabei auch die Menge, aus der die Skalare für die Skalarmultiplikation gegriffen werden.

  4. Die abgeschlossene Einheitskugel ist die Menge B(1,0):={xVx1}\overline{B}(1,0) := \{x \in V \vert \|x\| \leq 1 \} - also die Menge aller Vektoren mit Länge kleiner gleich Eins. Die Visualisierung dieser Kugel kann zur Charakterisierung von Normen herangezogen werden.

» Notes on function interposition in C++

February 21, 2016 | cpp development english | Adrian Kummerländer

To counterbalance the vastly increased amount of time I am spending on purely theoretical topics since I started studying mathematics, my most recent leisure time project was to familiarize myself with function interposition in C++ on Linux. This article will document some of the ins and outs of using this technique in an actual project in addition to describing how the acquisition of the interposed function's pointer may be reasonably abstracted by a function template.

Basics

Most if not all of the applications and services one commonly uses are not monolithic executables that one could execute on the bare metal but depend on a number of separate libraries that provide useful abstractions the actual application is built upon. As most application share a common set of library dependencies it would be quite wasteful to package each application with its own separate copy of a given library. This is why most libraries are commonly linked dynamically which means that e.g. a call to random library function f is not resolved during compilation by replacing it with the library provided source code or a fixed reference to the implementation of f but resolved respectively linked at runtime. For Linux applications this dynamic resolution is commonly performed by the dynamic linker ld.so.

Instance specific configuration of this library is possible via a set of environment variables. One of these variables is LD_PRELOAD which enables us to provide "[...] a list of additional, user-specified, ELF shared objects to be loaded before all others that can be used to selectively override functions in other shared objects." (ld.so manpage, section on LD_PRELOAD).

This feature is what is commonly referred to as function interposition and is what will be discussed in the following sections. Other options for intercepting function calls such as ptrace are not covered by this particular article.

Use case

Function interposition is useful in various practical scenarios such as providing custom memory allocators as drop in replacements for the appropriate standard library functions as well as monitoring the function calls of a application as an additional debugging avenue. Furthermore LD_PRELOAD's nature of replacing library functions with custom logic in a not necessarily obvious manner makes it a security risk which is why it is disabled for e.g. setuid applications. But even with this restriction it may be used as a foundation for userland rootkits - for instance one could hijack the library functions used to interface with the file system and change what certain applications see. Such shenanigans could then in turn be used to manipulate the source code of an application during compilation while continuing to display the unchanged source code to the user via her chosen text editor and file hashing tool. More information on this kind of attack can be obtained e.g. in the 31c3 talk on reproducible builds which is where I was first confronted with this risk.

However the use case that led me to dive into this topic was to develop a tool to be dropped in front of any LD_PRELOAD supported program that would then monitor all relevant file system interactions and generate a nice summary of what was changed to be used for documentation purposes. The result of this undertaking is available on Github and cgit.

Requirements for successful interposition

To interpose a given function the library provided to the dynamic linker via LD_PRELOAD simply needs to contain a function symbol of the same name and signature.While this is not a problem in C it can be problematic in C++ as the compiler per default performs name mangling to convert a given function signature to a plain string1. Luckily this can be prevented by enclosing the functions to be interposed in an external "C" block.

Note that this only applies if we want to specifically interpose C functions from C++. There is nothing stopping us from interposing any function in a shared library as long as we can get the compiler to generate the correct symbol name. Accordingly this also works for C++ class member functions or functions of libraries written in other languages such as D.

To check if the symbols are exported correctly we can use nm which ĺists the symbols in ELF object files.

> nm libChangeLog.so | grep "open\|write"
000000000009e866 T open
000000000009e99b T write
000000000009ea5d T writev
000000000009f61a W _Z11track_writei
000000000009f6ec W 
_Z11track_writeRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
[...]

As we can see interposing this library would lead to the application calling the library's open, write and writev functions instead of the standard C library's. Note that the C++ source additionally needs to be compiled as position-independent code to be usable as a shared library at all. If one uses clang or g++ this is easily achieved by adding the -fPIC option.

Acquiring a pointer to the actual function

Although we can now replace functions in a target application with our own logic the goal remains to merely interpose a function which means that we have to call the actual function at some point. The dynamic linker library offers a function to acquire the address of the next symbol with a given name in the resolution stack in the form of dlsym. This function is defined in the dlfcn.h header and requires the interposed library to be linked to ld.so.

void* dlsym(void* handle, const char* symbol);

While handle can be used to restrict the resolution to a specific shared library we pass a special pseudo-handle RTLD_NEXT which instructs the function to return the address of the next symbol whose name equals the null-terminated symbol parameter.

Note that RTLD_NEXT is only defined by dlfcn.h if _GNU_SOURCE is defined during preprocessing - i.e. before the header is included. This may happen implicitly if features.h is included. If this should not be the case a plain #define _GNU_SOURCE satisfies the requirement.

If we were working in C we could directly assign the returned pointer of type void* to a function pointer of the function's signature. However this sort of cast is not allowed in C++ which is why we need to manually copy the address of the symbol into a function pointer. This may be achieved using std::memcpy.

const void* symbol_address{ dlsym(RTLD_NEXT, "write") };
ssize_t (actual_function*)(int, const void*, size_t){};

std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));

To prevent dlsym from being unneccessarily called more than once for a given symbol name one probably wants to persist the function pointer to e.g. a static variable local to the function body.

static ssize_t (actual_function*)(int, const void*, size_t){};

if ( !actual_function ) {
    const void* symbol_address{ dlsym(RTLD_NEXT, "write") };

    std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));
}

This logic should be placed in the function body and not for instance in a global initialization function as it is not guaranteed that such a function will be executed prior to any calls to interposed functions. The next section will describe an approach to reduce unneccessary code duplication in this context.

Abstracting function pointer handling

The most straight forward approach to abstracting the usage of dlsym is to wrap it in a more C++-like function template. To prevent unneccessary duplication of the functions return and parameter types as well as to hide the strange syntax of function pointer declaration we first define a template alias as follows:

template <class Result, typename... Arguments>
using ptr = Result(*)(Arguments...);

This allows us to define function pointers in a fashion simmilar to std::function and can be used as the template parameter of our actual dlsym abstraction.

template <typename FunctionPtr>
FunctionPtr get_ptr(const std::string& symbol_name) {
    const void* symbol_address{ dlsym(RTLD_NEXT, symbol_name.c_str()) };

    FunctionPtr actual_function{};
    std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));

    return actual_function;
}

This extraction of all dlsym calls into a single function template will come in handy during the section on problems in practice. Furthermore it allows us to write the exemplary interposition of the write library function in the following way which I for one find to be more maintainable and overall nicer looking than its c-style equivalent.

ssize_t write(int fd, const void* buffer, size_t count) {
    static actual::ptr<ssize_t, int, const void*, size_t> actual_write{};

    if ( !actual_write ) {
        actual_write = actual::get_ptr<decltype(actual_write)>("write");
    }

    // <-- custom logic to be interposed in all `write` calls

    return actual_write(fd, buffer, count);
}

Problems in practice

The approach detailed in the sections above was enough to develop my transparent file system change tracking tool to a point where it could monitor the actions of the core utilities as well as generate diffs of files edited in vim. But while checking out the current state of the neovim project I discovered that interposing libChangeLog.so led to a deadlock during startup.

This deadlock was caused by the custom memory allocation library jemalloc used by neovim because it calls mmap during its initialization phase. The problem with this is that it already leads to executing libChangeLog’s mmap version whose static actual_mmap function pointer is not initialized at this point in time. This is detected by our current logic and leads to a call to dlsym to remedy this situation. Sadly dlsym in turn requires memory allocation via calloc which leads us back to initializing jemalloc and as such to a deadlock.

I first saw this as a bug in jemalloc which seemed to be confirmed by a short search in my search engine of choice. This prompted me to create an appropriate bug report which was dismissed as a problem in the way mmap was interposed and not as a problem in the library. Thus it seems to be accepted practice that it is not the responsibility of a preloaded library to cater to the needs of other libraries relying on function interposition. This is of course a valid position as the whole issue is a kind of chicken and egg problem where both sides can be argued.

Issues of this kind are common when implementing interpositions of low level c-library functions as they are not only used everywhere but are also non-monolithic and may easily depend on each other if they are augmented by custom logic. If we want to interpose more than a single function or add logic depending on other library calls it is quite certain that we will run into issues simmilar to the one detailed in this section. While those issues can be fixed this can easily require the interposition of further functions which can possibly quickly spin out of control.

Implementing a static memory allocator

To return to our issue at hand I was left with the only option of working around the deadlock by adapting libChangeLog to call dlsym without relying on the wrapped application’s memory allocator of choice. The most straight forward way to do this is to provide another custom memory allocator alongside the payload function interpositions of mmap and friends.

Such a static memory allocator is implemented by libChangeLog in commit af756d and basically consists of a statically sized array allocated in the object file itself alongside a stacked allocation "algorithm" without any support for releasing and reusing memory of the static buffer once allocated.

This custom allocation logic is then selectively called by interpositions of free, malloc and calloc. The choice between using the real allocator and the static allocator depends on a dlsym recursion counter maintained by a init::dlsymContext scope guard helper class. As we already abstracted all usage of dlsym to a single function template the introduction of a static allocator for dlsym required only small changes to the existing function interpositions.

Summary

As a conclusion one could say that function interposition is useful for both debugging applications and building programs that monitor other processes on such a low level that one doesn't need to care about the language they are written in nor needs to customize the monitoring logic for specific applications as long as everything works as expected. Furthermore it is a nice approach to familiarizing oneself with the lower level workings of Linux userland applications.

Although this approach depends on interfacing with C code it can be reasonably abstracted using C++ and as such can also make use of the higher level functionality offered by this language.

One should however expect to dive deeper into C library internals and debug lower level issues while actually wanting to implement higher level functionality. Furthermore we probably will not get away with just implementing an interposition of the function we are interested in but also other functions that depend on it in some fashion in some wrapped applications. Definitely exepect quite a few coredumps and deadlocks during development.

For a real world example of how function interposition using LD_PRELOAD and C++ may be used to build a small but hopefully useful application feel free to check out change on Github or cgit.

  1. This is required to e.g. support function overloading which is not available in C. Of course this also means that our interposed functions can not be overloaded. Function names may be demangled via the --demangle option of nm.