Dissecting a Shader Quine

I'm not normally very interested in quines, but today I saw one that that really made me sit down and study it carefully. It was a quine in the form of a shadertoy. Here it is:

For those that might be wondering, the impressive thing about this is that GLSL doesn't really have a concept of text, or fonts, or anything that could be used to put human-readable messages on the screen. The output of a pixel shader is just a color, and that's it. So how does this thing manage to display its own source code and be so compact? That's what I set out to learn.

Diving In

I started by transforming the shader into a more understandable form by adding formatting. Here is the formatted version for your convenience:

int y;
ivec2 d;

uint[] c = uint[ 151](0x007a995eu,0x0083f840u,0x009a9c40u,0x006e5840u,0x0043f4dcu,    
0x006659c0u,0x0066595eu,0x000c5661u,0x006a595au,0x007a9a66u,0x00f14938u,0x0062493fu,0x00924918u,    
0x00fe4918u,0x00a2cb18u,0x00145f84u,0x3813813cu,0x0003d100u,0x0087f840u,0x0066bb5au,0x0085e000u,    
0x00330604u,0x00010800u,0x00020000u,0x00624918u,0x00f2081cu,0x00024784u,0x0001e840u,0x0085e100u,    
0x000047a1u,0x00014800u,0x00894200u,0x00214880u,0x0023e208u,0x00008208u,0x00f2081cu,0x00024784u,    
0x0087f000u,0x0003f840u,0x00918624u,0x000ccc00u,0x00916724u,0x00a3b9d8u,0x00514514u,0x00310a24u,    
0x00e0423cu,0x001a9080u,0x00024000u,0x00c766e3u,0x00c8d17fu,0x0052ca00u,0x0083f040u,0x0003f000u,    
0x0000413cu,0x00000000u,0x00000000u,0x2cd9ab51u,0x0c39545eu,0x1978dd82u,0x2695ab51u,0x36af6336u,    
0x256ad459u,0x26045076u,0xfefbefd4u,0x2d45979bu,0x1950ed9au,0x0bd9ab51u,0x1a3b571bu,0x0cdadd59u,    
0x208262e5u,0x299d7354u,0x2c5cd846u,0x019c0a9bu,0x1165d799u,0x145766adu,0x0ad9ab51u,0x366ad456u,    
0x1ab5158bu,0x1171b3f6u,0x2b4766adu,0x3678a8acu,0x3565a3b5u,0x007d1dadu,0x0b811d34u,0x1902702eu,    
0x253143afu,0x0f845a11u,0x30460826u,0x00a86a45u,0x1b64f0e7u,0x2d45975eu,0x1b52dd9au,0x366ad45cu,    
0x038acad1u,0x11ad8586u,0x35782070u,0x2dd5968eu,0x3401f476u,0x01811db4u,0x00b80048u,0x18bd9027u,    
0x0eb80aebu,0x19027014u,0x2bad8bdbu,0x0050eb81u,0x1b6470a7u,0x01aeb62fu,0x0050eb80u,0x1b6430a7u,    
0x01aeb62fu,0x0050eb81u,0x1b646067u,0x253143afu,0x26081a11u,0x14da0836u,0x1b622254u,0x2ad9b129u,    
0x1b64f9c0u,0x1161575eu,0x11290d8du,0x132904adu,0x1a65850eu,0x0430e576u,0x0e5562b6u,0x1b2f608cu,    
0x2bb172dcu,0x18c8ec51u,0x1845a673u,0x0b8ac5edu,0x2b35eb17u,0x0230e551u,0x2c79b2d4u,0x289d736bu,    
0x17354845u,0x296c8a2cu,0x3035e189u,0x0c39546bu,0x08585502u,0x15aca79bu,0x0d50430eu,0x34160b17u,    
0x209d72f4u,0x2e5c0204u,0x2f6409c0u,0x03580515u,0x1b185585u,0x216d4b61u,0x04201515u,0x010c4587u,    
0x1b6c4196u,0xfefbf75eu);

uint e(uint b){
  return c[b]>>(d.x*6+d.y)&0x1u;
}

uint v(int a,int b,int f) {
  int i=y-a;
  return i<0||i>b?0x0u:e(c[i/5+f]>>i%5*6&0x3fu);
}

uint n() {
  int i=y-36,o=i%12;
  return i<0||i>1810 ? 0x0u : o==0?e(0x0u):o==1?e(0x27u):o==10?e(0x23u):o==11?e(0x16u):e(c[i/12] >> ((9-o)*4) & 0xfu);
}

void mainImage(out vec4 a,vec2 b){
  b.y=iResolution.y-b.y;
  d=ivec2(b);
  y=d.x/5+(d.y/8)*96;
  d%=ivec2(5,8);
  a=vec4(d.y>5||b.x>480. ? 0x0u : v(0,35,56)+n()+v(1847,431,64));
}

As I expected, adding whitespace, changing variable names or adding statements to functions did not change the output at all. The data for the pixels that the shader displays is all hidden in the array c. That's an easy guess to make, but how exactly is it encoded? I want to know the gory details.

Let's proceed by looking at the mainImage function. The first argument is the color of the output pixel and the second is the pixel coordinate - this is standard for shadertoy. The first line of the function just inverts the y axis so that b now contains the coordinates of the pixel relative to the top left corner. The next line, d=ivec2(b), converts the pixel's coordinates to integers assigns the result to d.

The following line, y=d.x/5+(d.y/8)*96, gave me a pause. I tried changing the value 96 and that caused the text to kind of slide around, which gave me an idea. I counted the number of characters per line in the unformatted version and it turned out to be exactly 96! Furthermore, careful examination with GIMP showed that 5 and 8 are roughly the width and height of the characters (with padding). So, considering that d is the integer coordinate of the current pixel, y must be the index of the current character that is being drawn!

This theory is further confirmed by the next line, d%=ivec2(5,8) which sets d to the relative coordinate of the pixel within the glyph.

Adding Up Pixels

Next up, we have the computation of the final output: a=vec4(d.y>5||b.x>480. ? 0x0u : v(0,35,56)+n()+v(1847,431,64)).

There's a lot to unpack here. For starters, it immediately jumps out that every sixth row of pixels, as well as the entire area to the left of 480th column of pixels will be black: that's what the condition of the ternary operator guarantees. But then we have those three function calls and six magic numbers! By playing with the constants you can kind of figure out what some of them do. For example, changing 35 or 431 to smaller values makes the initial and final parts of the shader in the output shorter. This suggests the idea that the rendering of the final picture is broken down into 3 parts. To make the explanation easier, let's look at this illustration:

The first call to v() returns 1 in the area marked red, and returns 0 everywhere else. The call to n() returns 1 in the blue area and returns 0 everywhere else. The second call to v() returns 1 in the green area, and returns 0 everywhere else. Summed together, the results of these calls give the complete picture. So, v() is responsible for displaying parts of the output that are *not* the array elements, and n() displays the array itself!

Displaying the Middle

Let's look at n() then. It begins by declaring a variable i and assigning its value to be y-36. Recall that y is the index of the current character. Incidentally, 36 is exactly the length of the "prefix" part of the shader, i.e. the part immediately preceding the array (including the opening paren). Thus, i must be the relative index of the character within the array substring.

Each element of the array is exactly 12 characters long (counting the comma), so the next variable, o, is the index of the character within the substring corresponding to the current array element. At this point, it should be easy to see through the code's next trick: the really long series of nested ternary operators. Here they are, rewritten for readability:

uint n() {
  int i=y-36,o=i%12;
  if(i<0||i>1810) {
    return 0x0u;
  } else if (o==0) {
    return e(0x0u);
  } else if(o==1) {
    return e(0x27u);
  } else if (o==10) {
    return e(0x23u);
  } else if(o==11) {
    return e(0x16u);
  } else {
    return e(c[i/12] >> ((9-o)*4) & 0xfu);
  }
}

This makes it obvious that when our position within the element substring is at 0, 1, 10 or 11 we return the e() of some hardcoded values. I am reasonably certain that these values correspond to characters "0", "x", "u" and "," :-). In all the remaining cases we bit-shift the current array element to get the corresponding nibble all the way to the right and then obtain its value with a bitwise AND operation. Then we return the e() of that value.

At this point all signs point to e() being the function that is responsible for visualising a given character. It is given a character ID and returns 0 or 1 depending on whether the current pixel should be black or white if we want to draw the given character. The implementation of this function tells us a lot about how the data in the array is encoded.

The first few elements of the array are used to store the font - one 32-bit element per glyph. Each 6 bits of a font element represent one pixel column of the glyph - this is easy to verify if you take the first element of the array, convert it to binary using a calculator and write out each six-bit subsequence as a column. The function e() extracts the necessary pixel by shifting the corresponding bit all the way to the right then ANDing the result with 1.

Displaying the Beginning and the End

The final piece of the puzzle is the v() function. As mentioned earlier, it is responsible for drawing the non-array substrings of the shader. The first parameter is the index of the character at which the substring starts and the second parameter is very obviously its length. The third one is an offset at which the substring data (i.e. character IDs) is stored in the array.

The 0x3f bitmask suggests that each character ID is represented with six bits (since its binary representation is six ones). Indeed, in the first call, the offset is 56 (suggesting that the font data occupies 56 elements; by the way you need at least six bits to address that many... conincidence? I think not!), and in the second one the offset is 64. 64-56 = 8 32-bit ints, or 256 bits. We know that the length of the first segment is 36 chars. 36*6=216, which, when rounded up is 256, thus confirming the theory!

So, to summarize: the displayed picture is encoded in the giant array. The first 56 elements are bitmaps of font glyphs, and the rest are six-bit character IDs packed into 32-bit ints. The rest of the code figures out the correct glyph for a given pixel and the exact position within that glyph, and extracts the pixel value with some bit twiddling.

I'll leave you with the full version of the shadertoy rewritten for readability:

int character_idx;

ivec2 pixel_offset;

uint[] data = uint[ 151](0x007a995eu,0x0083f840u,0x009a9c40u,0x006e5840u,0x0043f4dcu,    
0x006659c0u,0x0066595eu,0x000c5661u,0x006a595au,0x007a9a66u,0x00f14938u,0x0062493fu,0x00924918u,    
0x00fe4918u,0x00a2cb18u,0x00145f84u,0x3813813cu,0x0003d100u,0x0087f840u,0x0066bb5au,0x0085e000u,    
0x00330604u,0x00010800u,0x00020000u,0x00624918u,0x00f2081cu,0x00024784u,0x0001e840u,0x0085e100u,    
0x000047a1u,0x00014800u,0x00894200u,0x00214880u,0x0023e208u,0x00008208u,0x00f2081cu,0x00024784u,    
0x0087f000u,0x0003f840u,0x00918624u,0x000ccc00u,0x00916724u,0x00a3b9d8u,0x00514514u,0x00310a24u,    
0x00e0423cu,0x001a9080u,0x00024000u,0x00c766e3u,0x00c8d17fu,0x0052ca00u,0x0083f040u,0x0003f000u,    
0x0000413cu,0x00000000u,0x00000000u,0x2cd9ab51u,0x0c39545eu,0x1978dd82u,0x2695ab51u,0x36af6336u,    
0x256ad459u,0x26045076u,0xfefbefd4u,0x2d45979bu,0x1950ed9au,0x0bd9ab51u,0x1a3b571bu,0x0cdadd59u,    
0x208262e5u,0x299d7354u,0x2c5cd846u,0x019c0a9bu,0x1165d799u,0x145766adu,0x0ad9ab51u,0x366ad456u,    
0x1ab5158bu,0x1171b3f6u,0x2b4766adu,0x3678a8acu,0x3565a3b5u,0x007d1dadu,0x0b811d34u,0x1902702eu,    
0x253143afu,0x0f845a11u,0x30460826u,0x00a86a45u,0x1b64f0e7u,0x2d45975eu,0x1b52dd9au,0x366ad45cu,    
0x038acad1u,0x11ad8586u,0x35782070u,0x2dd5968eu,0x3401f476u,0x01811db4u,0x00b80048u,0x18bd9027u,    
0x0eb80aebu,0x19027014u,0x2bad8bdbu,0x0050eb81u,0x1b6470a7u,0x01aeb62fu,0x0050eb80u,0x1b6430a7u,    
0x01aeb62fu,0x0050eb81u,0x1b646067u,0x253143afu,0x26081a11u,0x14da0836u,0x1b622254u,0x2ad9b129u,    
0x1b64f9c0u,0x1161575eu,0x11290d8du,0x132904adu,0x1a65850eu,0x0430e576u,0x0e5562b6u,0x1b2f608cu,    
0x2bb172dcu,0x18c8ec51u,0x1845a673u,0x0b8ac5edu,0x2b35eb17u,0x0230e551u,0x2c79b2d4u,0x289d736bu,    
0x17354845u,0x296c8a2cu,0x3035e189u,0x0c39546bu,0x08585502u,0x15aca79bu,0x0d50430eu,0x34160b17u,    
0x209d72f4u,0x2e5c0204u,0x2f6409c0u,0x03580515u,0x1b185585u,0x216d4b61u,0x04201515u,0x010c4587u,    
0x1b6c4196u,0xfefbf75eu);

uint glyph(uint id){
  int shift_amount = pixel_offset.x * 6 + pixel_offset.y;
  return data[id]>>shift_amount & 0x1u;
}

uint text_segment(int start, int len, int offset) {
  int i = character_idx - start;
  if (i < 0 || i > len) { return 0u; }
  else {
    uint element_data = data[i/5 + offset];
    uint glyph_id = element_data >> i%5*6&0x3fu;
	return glyph(glyph_id);
  }
}

#define ARRAY_ELEMENT_STRING_LEN 12
#define PREFIX_LEN 36
uint array_segment() {
  int i = character_idx - PREFIX_LEN,   // relative position in array
      o = i % ARRAY_ELEMENT_STRING_LEN; // relative position in array element
  if(i<0||i>1810) {
    return 0x0u;
  } else if (o==0) {
    return glyph(0x0u); // 0
  } else if(o==1) {
    return glyph(0x27u); // 1
  } else if (o==10) {
    return glyph(0x23u); //u
  } else if(o==11) {
    return glyph(0x16u); //,
  } else {
    int elem_idx = i/12;
    return glyph(data[elem_idx] >> ((9-o)*4) & 0xfu);
  }
}

void mainImage(out vec4 fragColor, vec2 fragCoord){
  fragCoord.y=iResolution.y-fragCoord.y;
  ivec2 pixel_coord =ivec2(fragCoord);
  character_idx = pixel_coord.x/5+(pixel_coord.y/8)*96;
  pixel_offset = pixel_coord % ivec2(5,8);
  if (pixel_offset.y > 5 || fragCoord.x > 480.) {
      fragColor = vec4(.0);
  
  } else {
    fragColor = vec4(text_segment(0,35,56) + 
                     array_segment() + 
                     text_segment(1847,431,64));
  }
}

Like this post? Follow this blog on Twitter for more!