- Every comical image ever imagined
- Encoding image in path
- FUSE (Filesystem in userspace)
- My FUSE client
Every comical image ever imagined
A co-worker of mine launched the idea that provided a few limitations, all comical images ever imaginable isn’t an infinite set.
The limitations to impose would be
- use of a limited set of color values (let’s choose 16 value grayscale)
- use of a limited resolution (let’s choose 60*60 pixels)
Encoding image in path
Given those restrictions, the amount of possible unique images would be limited :). 4 bits would be required per pixel, so we’ll need 60*60*4 bits (14400 bits, or 1800 bytes) to describe an image without compression.
Most people, including me would argue that the 2^14400 images is way to many go through manually, or even store on your file system. The part about too many to go through manually holds. But the part about not being possible to have all those images on your file system is false. It really is possible to fill your filesystem with all those images. The only requirement I suggest is that you use fuse (filesystem in Userspace), and encode the image information in the path to the image. It may be cheating, but any tool, program or even you wouldn’t see the difference between your fuse filesystem and a humongous disk actually storing all those images.
First things first. Encoding an image requiring 1800 bytes in a file name is quite an odd task. Some information about filename length limits on linux could be found on stackoverflow. Basically, we will have to pass two limits. One for the filename length, and one for the path length. First, we can check our system headers (linux/limits.h)
In addition to that, those limits could be reduced further by the filesystem you are currently using. There is a convenient way to get hold of the limits for a mounted filesystem. Just use
getconf. I queried my etx4 filesystem, whith these results:
I.e. my filesystem didn’t limit the filename and paths any more than the system headers. I don’t expect fuse to restrict those limits additionally.
To avoid having to reinvent the wheel, I thought that we simply could use base64 for encoding the 1800 bytes we need for an image into its path. Turns out that there are way more variants of encoding base64 than I could have imagined. They differ in areas such as maximum encoded line lengths, line separators, use of padding and use of crc. Additionally, I counted seven different combinations in use for the last two characters which encode index 62 and 63. Most of them actually used the path separator
/ for one of the indexes, so I just chosed “a random URL-safe encoding I liked”. The code is using 64 characters: A-Z, a-z, 0-9, as well as - and _. Those characters encode 6 bits of information in a single character. The table below shows a bit of the encoding alphabet.
Due to the filename length limit (and the inconvenience of having too many files in the same directory), the plan is to split those bytes needed to encode the image along different subdirectories as well as the final file name. 1800 bytes, or 14400 bits encoded using base64 requires 2400 characters, which mean that we’ll have excessively long paths to each image, but there really is no way around it.
Using two chars for each directory and for each filename, we end up with a filesystem 1200 levels deep to encode
our all 60*60 pixel images.
FUSE (Filesystem in userspace)
It turns out that it’s pretty simple to use fuse. The best documentation I’ve found so far was CS135 FUSE Documentation. It was aimed a people writing their first fuse client.
Since I’m running on ubuntu:
- I made sure that I had fuse installed
sudo apt-get install fuse libfuse2 libfuse-dev.
- I downloaded a matching source package of fuse from the fuse project page on sourceforge.
(If you are running ubuntu 14.04, you can easily download ubuntus source code for that package using
apt-get source fuse. Note that it will download a bunch of files in your current directory).
The README file in the source package made everything sound really simple:
Here’s how to create your very own virtual filesystem in five easy steps (after installing FUSE):
1) Edit the file example/fusexmp.c to do whatever you want…
2) Build the fusexmp program
3) run ‘example/fusexmp /mnt/fuse -d’
4) ls -al /mnt/fuse
5) Be glad
If it doesn’t work out, please ask! Also see the file ‘include/fuse.h’ for detailed documentation of the library interface.
My FUSE client
Since my file system is read only, I ended up having to implement only these four fuse operations:
I’ve added the source code below in case anybody would be interrested in playing around with this (or just want to take a look at FUSE). Should compile without warnings for at least gcc 4.8.2.