Pastebins are the next step in the evolution of a software developer, right after finishing hello worlds and static site generators. They are limited terms of features (or not … ahem) but require some form of dynamisms in order to receive and store user input and make it available upon request. Of course, everyone has different ideas what a pastebin should do and in what language it should be written. And because I am in no way different, I had to write my own: the wastebin pastebin that ticks the following boxes:

• Written in Rust for ease of deployment.
• SQLite instead of a full-fledged database server or flat files.
• Paste expiration.
• Minimalist appearance.
• Syntax highlighting.
• Line numbers.

bin – from which wastebin takes huge inspiration in terms of UI – was almost there but the lack of expiration and flat-file storage was a no-go. Moreover, I sincerely think axum has a more solid foundation than Rocket. Enough reasons to do it myself.

One of Rust’s nice properties is producing statically linked binaries making deployment simple and straightforward. In some cases this is not enough and additional data is required for proper function, for example static data for web servers. With dependencies such as include_dir and mime_guess this is a piece of cake to integrate into axum though.

Using include_dir we first declare variable that represents the data currently located in the static directory:

use include_dir::{include_dir, Dir};

static STATIC_DIR: Dir<'_> = include_dir!("$CARGO_MANIFEST_DIR/static");

Now we define the static data route, passing *path to denote we want to match the entire remaining path.

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let app = axum::Router::new()
        .route("/static/*path", get(static_path));

    let addr = std::net::SocketAddr::from(([0, 0, 0, 0], 3000));

    axum::Server::bind(&addr)
        .serve(app.into_make_service())
        .await?;

    Ok(())
}

Note that we cannot use the newly added typed path functionality in axum-extra. Now onto the actual route handler:

async fn static_path(Path(path): Path<String>) -> impl IntoResponse {
    let path = path.trim_start_matches('/');
    let mime_type = mime_guess::from_path(path).first_or_text_plain();

    match STATIC_DIR.get_file(path) {
        None => Response::builder()
            .status(StatusCode::NOT_FOUND)
            .body(body::boxed(Empty::new()))
            .unwrap(),
        Some(file) => Response::builder()
            .status(StatusCode::OK)
            .header(
                header::CONTENT_TYPE,
                HeaderValue::from_str(mime_type.as_ref()).unwrap(),
            )
            .body(body::boxed(Full::from(file.contents())))
            .unwrap(),
    }
}

As you can see we first strip the initial slash and then use the mime_guess crate to guess a MIME type from it. If we are not able to do so, just assume text/plain however wrong that is. Then we try to locate the file path and either return a 404 or a 200 with the actual file contents. Easy as pie.

Eight years ago (ouch …) I published a little tool to interactively cherry-pick commits from a branch. It’s still useful to me but ever so often I forget about the urwid dependency when re-installing it. Yada yada, so of course team Rewrite-in-Rust strikes again which means I can simply drop the statically linked binary into $PATH and not have to worry about Python and ncurses dependencies anymore.

And for the price of one you now get even two tools. Since I have to create a lot of feature, bugfix and whatnot branches, deleting them becomes painful as well even with tab-completion and fzf integration. So, in a similar vein to git pick the git prune-branches (git prune is a plumbing command to remove unreachable objects from the Git database) allows you to select a bunch of branches interactively and delete them in one go.

A friend of mine asked me to join him in a small side project that combines both art, programming and hardware. The latter is still in the design phase, so let me tell you about the art and programming part first. The principal idea is to generate art (random, really generative or from existing data) and let it being drawn in real life by a machine. We wanted to start simple and just process existing bitmap images and turn them into nice looking paths that can be drawn by the “machine”.

My initial idea was to generate a path from a random walk with a probability density that matches the surrounding pixel density of the current position. While that works in a way, the result is hardly legible. After some researching we came to the conclusion to do what in general is known as TSP art.

TSP art

TSP as in the Travelling Salesman Problem is a two-step problem. In a first step, for given number of points, we find a set of points that approximates the pixel density of the input image. In a second step, we determine a path that connects all points exactly once.

Sampling points

Because (photographic) image formation is a stochastic process one can do the reverse and use the brightness of each input image pixel as the probability that light hit the sensor. Since we want to have more points for darker areas, we have to use the inverse though. That and simple rejection sampling leads us to a basic point sampling algorithm:

1. If we have enough points stop.
2. Compute a random position (x, y) in [0, width; 0, height].
3. Read the pixel value at (x, y) in the input image, normalize it to [0, 1] and invert it.
4. Compute a random brightness value between [0, 1].
5. If the random brightness value is larger than the pixel value accept it.

This works wonderfully but due to the stochastic nature requires many samples which is detrimental to the path finding step. In the following image you can see the result for 10000 and 100000 points:

Luckily there are various approaches to approximate the density with less points the same way a human would draw an image using a pencil.

Weighted Voronoi stippling

Weighted Voronoi Stippling is such an approach. The basic idea in layman’s terms is as follows:

1. Sample a set of points randomly or use the algorithm from above.
2. Compute the Voronoi diagram for the point set.
3. For each Voronoi cell move its central point to the darkest area.
4. Continue until you are satisfied.

The following image shows you the result for 10000 and 30000 points and 5 as well as 100 iterations:

Note though that there are no major improvements past the 50 iterations mark.

Solving the Travelling Salesman Problem

Now that we have a good set of points we want to connect them and ideally visit each point only once. Sounds familiar? Yes, it’s the infamous Travelling Salesman Problem which is NP-complete, meaning you won’t find the best solution in a reasonable amount of time for a larger number of points. So again a bit of research and the most straightforward algorithm is again two-fold, first we compute an initial path using the Nearest Neighbor algorithm and then iteratively improve that path using the 2-opt algorithm. Here are two results for 10000 and 30000 points respectively:

inkdrop

All of the images have generated by a small Rust tool called inkdrop. It is split into a core library that implements the algorithms as well as some data structures and two binaries to drive them via command line or a GTK 4 user interface. The primary output data format is SVG which is super simple and matches the problem very well. To generate Voronoi diagrams I used the wonderful Voronator library which wraps the Delaunator library I tried to use before but gave me too many headaches.

Long-time readers will know that GTK is nothing new for me but GTK 4 is. And I must admit, I love the on-going work of the Gtk-rs team that provides usable GTK 4 bindings at this early stage as well as the GTK team itself. GTK 4 finally improves quite a few pain points for me and surprised me positively with the addition of layout managers and declarative property bindings. This allows one to write even less code and declare more UI facts in the builder file itself. Neat.

So, here is part one of our generative art adventure.

Update: The Rust bindings to GTK4 are now stable. Yay!

Stoneshard is a turn-based RPG with nice 2D pixel art and an elaborate role-playing system. Unfortunately, the Linux support is a bit messy and if you happen to play it on Ubuntu 20.04, it will tell you it cannot find libcrypto.so.1.0.0. Common advice is to symlink libcrypto.so.1.1.0 however that is neither a good idea nor even necessary because the game does not even depend on it. Hence, the cleaner way is just to patch the game binary, for example using patchelf:

$ git clone https://github.com/NixOS/patchelf && cd patchelf
$ ./bootstrap.sh && ./configure && make && sudo make install
$ patchelf --remove-needed libcrypto.so.1.0.0 <path-to-stoneshard>/game/StoneShard
$ patchelf --remove-needed libssl.so.1.0.0 <path-to-stoneshard>/game/StoneShard

With that done, you can run the game just fine. I still wonder what the crappy build system of that game is doing though …