• Every comical image ever imagined
• Encoding image in path
• FUSE (Filesystem in userspace)
• My FUSE client
  • Source code:

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)

#define NAME_MAX         255    /* # chars in a file name */
#define PATH_MAX        4096    /* # chars in a path name including nul */

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:

$ getconf PATH_MAX /
4096
$ getconf NAME_MAX /
255

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:

• .getattr
• .readdir
• .open
• .read

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.

Source code:

/*
  filename: all_images_fuse.c

  FUSE Client example.

  Sets up a read-only filesystem, containing every imaginable 
  60*60 pixel image with 16 gray levels. Image content is encoded
  in the file path of each image.

  Copyright (c) 2014 Simon Gustafsson

  Prepare development environment:
  sudo apt-get install fuse libfuse2 libfuse-dev

  Compile:
  gcc -Wall all_images_fuse.c `pkg-config fuse --cflags --libs` -o all_images_fuse

  Mount filesystem:
  ./all_images_fuse path_to_mount_point
  
  Unmount filesystem:
  fusermount -u path_to_mount_point
*/

#define FUSE_USE_VERSION 26

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#ifdef linux
/* For pread()/pwrite() */
#define _XOPEN_SOURCE 500
#endif

#include <fuse.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <dirent.h>
#include <errno.h>
#include <sys/time.h>
#ifdef HAVE_SETXATTR
#include <sys/xattr.h>
#endif

const char base64url[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

/** @warning caller should have allocated at least 3 bytes for dest. */
static void tobase64(int val, char* dest)
{
	dest[0] = base64url[ val & 63];
	dest[1] = base64url[ (val >> 6) & 63];
	dest[2] = 0;
}

static int frombase64(const char* twoChars)
{
	int retval = 0;
	int i;
	char* offset;
	for (i = 0; i < 2; i++)
	{
		offset = strchr(base64url, twoChars[i]);
		retval |= (offset - base64url) << 6*i;
	}
	return retval;
}

static int getDepth(const char* path)
{
	int i;
	int depth = 0;
	int path_len = strlen(path);
	
	for (i = 0; i < path_len; i++)
	{
		if (path[i] == '/') {
			depth++;
		}
	}
	return depth;
}

static int xmp_getattr(const char *path, struct stat *stbuf)
{
	int depth = getDepth(path);
	
	memset(stbuf, 0, sizeof(struct stat));
	
	if (depth < 1200) {
		stbuf->st_mode = S_IFDIR | 0755;
		stbuf->st_nlink = 2;
	} else {
		stbuf->st_mode = S_IFREG | 0444;
		stbuf->st_nlink = 1;
		stbuf->st_size = 60*60 + strlen("P5\n60 60\n250\n");
	}

	return 0;
}


static int xmp_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
		       off_t offset, struct fuse_file_info *fi)
{
	int depth = getDepth(path);
	int i;
	(void) fi;

	for (i = 0; i < 4096; i++)
	{
		struct stat st;
		char name[3+4];
		memset(&st, 0, sizeof(st));
		if (depth == 1200) {
			st.st_mode = S_IFREG | 0444;
			tobase64(i, name);
			name[2] = '.';
			name[3] = 'p';
			name[4] = 'g';
			name[5] = 'm';
			name[6] = 0;
			//strcpy(name+2, ".pgm");
		} else {
			st.st_mode = S_IFDIR | 0755;
			tobase64(i, name);
		}
		if (filler(buf, name, &st, 0))
			break;
	}

	return 0;
}


static int xmp_open(const char *path, struct fuse_file_info *fi)
{
	if (getDepth(path) == 1200)
		return 0;
	else
		return -ENOENT;
}


static char* generate_image(const char* path)
{
	char* data = malloc(60*60 + strlen("P5\n60 60\n250\n"));	
	int i;
	int bits = 0;
	int val = 0;
	char* w;
	strcpy(data, "P5\n60 60\n250\n");
	w = data + strlen(data);
	
	for (i = 0; i < 1200; i++)
	{
		val |= frombase64(&path[1 + i*3]) << bits;
		bits += 12;
		while ( bits >= 4)
		{
			*(w++) = (val & 0x0F) * 16;
			val = val >> 4;
			bits -= 4;
		}
	}
	
	return data;
}


static int xmp_read(const char *path, char *buf, size_t size, off_t offset,
		    struct fuse_file_info *fi)
{
	char* data = generate_image(path);
	int length = 60*60 + strlen("P5\n60 60\n250\n");

	if (offset >= length)
	{
		free(data);
		return 0;
	}
	
	if (size + offset > length)
	{
		size = length - offset;
	}

	memcpy(buf, data+offset, size);
	free(data);
	
	return size;
}

static struct fuse_operations xmp_oper = {
	.getattr	= xmp_getattr,
	.readdir	= xmp_readdir,
	.open		= xmp_open,
	.read		= xmp_read,
};

int main(int argc, char *argv[])
{	
	umask(0);
	return fuse_main(argc, argv, &xmp_oper, NULL);
}