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.
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:
If we have enough points stop.
Compute a random position (x, y) in [0, width; 0, height].
Read the pixel value at (x, y) in the input image, normalize it to [0, 1] and
invert it.
Compute a random brightness value between [0, 1].
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.
For each Voronoi cell move its central point to the darkest area.
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 …