Tiny bitfield based text renderer

Just a funny alias i am using for my demoscene stuff, it is related to the Orz alien species of my favorite adventure game : Star Control 2

Due to size constraint i stayed with a simple 3x3 monospaced font which seemed readable enough for the three letters i am focusing with.

This article focus heavily on rendering the pretty boring typeface above but i also explored some way to render stylized fonts without much size impact by using the wire-frame renderer (see below) and adding a notion of line weight to do the fill style.

An easy way to stylize the font would be to alter the way it is rendered, doing it in perspective (bit like Star Wars scroll text) or skipping some pixels for example, many bbstro in the early 90s did that.

Another approach is to render the text somewhere and to render it again by reading it back but with modulation or compositing (fastest way to render text on DOS, also because of VGA text mode and VGA fonts), most obvious would be to render it again but with an offset and dimmed, it could perhaps be applied on a per glyph basis, the renderer could perhaps be altered as well but this may be difficult for scalability.

Another approach would be to use feedback or perhaps drive it through diffusion (Laplace or Poisson equation; basis of the old-school fire effect as seen below), a cellular automaton or a chaos process or a free running Lindenmayer system.

See also the PETSCII art scene for huge amount of creative logos, found out that many of them are stylistically impressive due to PETSCII constraints.

Bit Hell by jendo

SV23WE LOGO by xeen

the tower of code by sensenstahl

Many cheap decoration could also be added to beautify the logo such as a mirror effect + watery effect through distortion of the reflected image.

Doing curve rendering may be interesting although the bytes cost might be high.

Here is some stylized rendering example which can be done in ~256 bytes :

rendered as pseudo 3d (cube renderer is very small !) with diffusion process on the right (also small)

different kind of diffusion for a neon style (also very small !)

easy one

Packing data into a bit field (e.g. using bits as an array where a bit represent a glyph pixel) was quite mandatory to save space, 9-bit is required to encode a glyph since it is a 3x3 font so ones can just use a single 32-bit value to represent 3 glyph at a time (or a 64-bit value to represent 7 glyph etc.), saving space.

Another advantage is that the data fit into a CPU register so there is no needs to access memory which may be quite heavy performances wise and also space wise.

A string could fit into a register or a set of registers, longer strings could be done with or without memory access, a stack could also be used.

Anyway, what does a string such as "ORZ" packed naively into a bit field looks like ?

11-bit rows packing

There is several ways to encode this, ones could let it as is and pack each row as a single 16-bit value, this waste a bit of space though.

The data could also be packed into a single 32-bit value, the issue is that the data above actually require 33 bits to be encoded (due to spaces) so there would be one glyph block left over... this can be mitigated if the missing block is actually an empty one but this is dodgy and it wouldn't suit all cases.

A better solution is to remove the space between each glyph from the bit field so a row would be 9-bit wide instead of 11, this would fit but the space between each glyph would have to be handled by the rendering code.

9-bit rows packing

111111110 -> 510


The representation is less readable but it save space, now to encode this as a single 32-bit value is easy, just take the value of each rows and pack it with this formula (where << is a logical left shift and v is a bitwise disjunction) : (483 << 18) ∨ (354 << 9) ∨ 510


Accessing data

Alternatives

If one don't mind about readability there is another way to encode the data by encoding a whole glyph linearly instead of each row, this affect the rendering code. (see Renderer #2 below)

There is also variations on the packing such as row / glyph orientation in the bit field which may affect optimizations. (see Renderer #2 below)

Another way would be to use some kind of run-length encoding but this is only advantageous for some set of glyph, perhaps it would work in combination ?

Usage in < 256 bytes intros

The usage of bit fields is quite common in small intros as a form of data compression such as the RSI logo in Centurio 256 bytes DOS intro, the top left logo make uses of 8x8 text blocks (it calls DOS API / interrupt putch) and is packed into a single 32-bit value, the whole code for the logo is about 30 bytes :

Centurio, a 256 bytes DOS intro by Baudsurfer / RSI; cubes are also made of characters

Here is the whole Centurio x86 assembly text renderer (fasm syntax) :

All of this is not limited to text rendering of course, bit fields can be used to encode all sort of things, boolean values (known as flags), volumetric data, tiny pixels art that you upscale on render just like a glyph so ones can make some tiny sprites or background. I'd bet that many intros are doing this for the geometry of some shapes, then they change colors (or even the representation so that it is less blocky, see the fancy fonts below) with some algorithm at runtime.

Another useful use case is also doing tiny textures by sampling the bitfield instead of using the common XOR patterns you see in small intros.

beyond the belt of hope, lilia and sammie 256 bytes by Sensenstahl; probably not bitfield based but the "sprites" could be !

Another idea would be to render tiles and modifying the tiles content by just modulating the bit fields or map a set of tiles differently or do simple transforms using bitwise operations such as mirroring, once you have a complete set of tile operations you can combine them to compose detailed patterns / images, ones could also animate tiles individually by switching values in a cyclic fashion (or just modifying a palette if using indexed color), this might give all sorts of cool patterns ? This is perhaps the way the impressive 256 bytes intro MEMS by Digimind works although just pure speculation. (didn't look at the code)

MEMS, a 256 bytes DOS intro by Digimind

Renderer : Introduction

Renderer #1

function setup() {
  pixelDensity(1)
  createCanvas(960, 540)
 
  background(0)
}

function draw() {
  loadPixels()

  const rowHeight = 90
 
  // row area to scan
  const pstart = width * 4 * 32
  const pend = pstart+(width * rowHeight)
  // iterate over a whole row
  for (let i = pstart; i < pend; i += 1) {
    const xOffset = 128
    const x = i % width - xOffset

    const bi = x >> 6 // bit field index
    
    // 1.
    // string rows
    const line1 = 887
    const line2 = 533
    const line3 = 1559
    // get a row bit from given index and make it either white (256) or black (0) with << 8 (note : in C this would be a multiply because of overflowing issues, there is also a trick by using negative numbers instead of a multiply)
    b1 = ((line1 >> bi) & 1) << 8
    b2 = ((line2 >> bi) & 1) << 8
    b3 = ((line3 >> bi) & 1) << 8
    
    // 2. non generic variant with single 32-bit value
    //    only works if you don't care about the last glyph block
/*
    let logo1 = 2245045111
    b1 = (((logo1 & 2047) >> bi) & 1) << 8
    b2 = ((((logo1 >> 11) & 2047) >> bi) & 1) << 8
    b3 = ((((logo1 >> 22) & 2047) >> bi) & 1) << 8
*/  
    // 3. generic with single 32-bit value
    //    not encoding spaces
/*
    let logo2 = 104667903
    b1 = (((logo2 & 511) >> bi) & 0x1) << 8
    b2 = ((((logo2 >> 9) & 511) >> bi) & 0x1) << 8
    b3 = ((((logo2 >> 18) & 511) >> bi) & 0x1) << 8
*/

    // first row
    let index = i * 4
    pixels[index + 0] = b1
    pixels[index + 1] = b1
    pixels[index + 2] = b1
    // second row
    index += width * rowHeight * 4
    pixels[index + 0] = b2
    pixels[index + 1] = b2
    pixels[index + 2] = b2
    // third row
    index += width * rowHeight * 4
    pixels[index + 0] = b3
    pixels[index + 1] = b3
    pixels[index + 2] = b3
  }
  updatePixels()
}


The conditional and x / y computation can be avoided by introducing an additional loop. ~94 bytes of x86 code generated by GCC.

A variation of this algorithm might render the glyph per column so the logo is encoded per column instead of per row, this help for optimization and avoid some computation and shrink the x86 code to ~86 bytes :

The glyph loop can be split in two loop to avoid computation and the first loop can be a for loop which help to shrink it to ~83 bytes of x86 code :

This can be optimized furthermore by encoding the logo backward and using negative number as a way to avoid masking (~77 bytes) :

Here is a size optimized version of the C code above (adapted for 1920xN resolution), this beat GCC output:

63 bytes, this was my first try.

Note : esp point to the target buffer in this case.

Using extensions

Here is a 62 bytes version which use BMI2 (Bit Manipulation Instruction) set (shlx) to free CL register so it can be used to replace a loop with loop instruction, advantage is that it is also fast since it doesn't output black values (loopne):

There is also the BEXTR instruction specifically made for extracting a bit field but didn't find it useful for my case yet.

Smallest "generic" so far (59 bytes)

Here is a 59 bytes version, i realized that the shifting can be replaced by a simple bit test which set the carry flag and the sbb instruction can be used to avoid a jump by setting a register to either -1 (full white) or 0 (black) depending on the carry result:

Not really satisfied by how the spacing is handled on all the generic ones since it fail with higher start position, it is also quite costly. (7 bytes) Perhaps there is a better way ?

With encoded spaces (52 bytes)

This section is about rendering wire-frame text; glyph made of lines. A simple renderer would just take care of drawing each lines, this is efficient for few characters:

Result is 79 bytes of x86 code (assume a 1920x768 buffer at esp, the text is centered):

Many memory access / big constants is quite costly although there is a lot of symmetry and repetition to exploit, this could be handled by swapping registers or adjusting values in a second loop to save some bytes.

Here is a 72 bytes (70 bytes with artifacts) version which group the top / bottom / vertical lines as single memory access with a loop:

Generic ?

A generic tiny wire-frame text renderer may also use a bit field which would encode 'commands' like some sort of simplified Logo language (see Turtle graphics), the data could be a 4-bit value (or 2-bit if ones don't need variable length lines) where 2-bit would be the line length and 2-bit would encode the direction and axis so ones can encode 8 lines in a single 32 bits value (16 lines if ones drop the variable length line!). Would be quite effective at rendering any types of outline and could be optimized for special cases.

There is some attempts in the demoscene of peoples doing something like this, CAFe'2019 DOS intro by Georgy Lomsadze which draw the logo outline progressively, it also poke into the palette so the colors rotate giving some nice retro touch, i don't know which algorithm this intro use but it seems to do well to pack a lot of lines in few bytes.

256 bytes DOS intro CAFe'2019; 175 bytes of code, 79 bytes of data

Curves ?

My version of a 'generic' wire-frame text renderer

// p5js code
let lineLength = 64
let index = 0

function computeStartPosition() {
  // compute start drawing position given as a precomputed index (a single instruction on x86)
  let x = width / 2 - lineLength * 5 / 2 + lineLength
  let y = height / 2 + lineLength / 2
 
  // fix the pixels to the grid
  x = Math.floor(x)
  y = Math.floor(y)

  index = (x + y * width) * 4
  //
}

function setup() {
  createCanvas(512, 512);
 
  background(0);
 
  computeStartPosition()
 
  drawOnce()
}

function drawOnce() {
  let commands = [-width, -1, width, 1, 0, -width, 1, 0, 1, width - 1, 1]
  loadPixels()
  for (let l = 0; l < commands.length; l += 1) {
    let r = commands[l]

    let c = abs(r) << 8
    // draw line
    for (let i = 0; i < lineLength; i += 1) {
      pixels[index + 0] = c
      pixels[index + 1] = c
      pixels[index + 2] = c

      if (r == 0) {
        index += 4
      } else {
        index += r * 4
      }
    }
  }
  updatePixels()
}

function draw() {

}


The high level code is quite small and could probably be smaller with some more optimizations.

The x86 hand assembly optimized version of this code use the stack to store the index increments data which result in very small code of ~52 bytes ! It is also very flexible.

Here is the whole x86 code which draw the ORZ logo:

~52 bytes, flexible, stack based data

The code above could be adapted to do way more and still stay small, for example adding support for variable length line is easy if ones push the line length along the increment data into the stack (ones could also pack both data as a pair of 16 bits value with values fetched by shifting the register), ones can also pack line weight for cheap stylized fonts.

The stack could be replaced by a combination of static data and perhaps lodsw instruction to fetch it but i didn't try as i felt 52 bytes was enough.

One of the disadvantage of the code above is when there is alot of line data; there is a lot of bytes wasted by the push instruction.

Thus i also tried an implementation which use a bitfield and 2-bit data (axis, direction) to draw the lines, ones could encode 16 lines as a single 32 bit value with this! It will also stay quite small with only ~59 bytes of code.

Disadvantage of this code is a loss of flexibility although ones could do variable line length / diagonals by using more bits for each line. The other option is to handle them as special cases with jump / compare instructions but this only works for few letters.

Note that this code draw 4 lines for each characters so there is some wasted data for characters such as "R" by going "back and forth" on the final line, this also happen for "Z".

~59 bytes but does not handle diagonals

I also had an idea (didn't try yet) to encode the letters by taking an intersection points and draw the associated two lines and jump to the next in zigzag (with y being flipped), there would be a default pattern (of two lines) that is carried over with orientation flip and the data indicate which of the side to draw, this may reduce the amount of data (as low as 1-bit depending on text) by exploiting the symmetry of the letters such as ones above with instruction tricks, may have some limitation in glyph type though.

Stylized wire-frame ?

A fairly cheap idea to obtain stylized wire-frame text is to transform / project the content such as with Axonometric projection. (see above how Axon intro handle stylized text, this can serve as a base for further transform such as the one shown below)

projected lines

Blocky font and cheap fancy fonts with the wire-frame renderer ?

Perhaps blocks could also be taken by taking parts of an offseted sierpinsky or munching square.

result with operators : + | -

Also, an interesting approach would be to use an algorithm to generate all possible combinations of pixels (guess it work best for 2x3 font since there is 64 possibilities only), perhaps the index can be encoded efficiently with some scheme since you only want a tiny subset of characters.

Here is some LUA code (TIC-80) which render a scaled "ORZ" using the combinations / index method, the function can be used to render all combinations for the given grid setup (3x3 here) by calling it for all index values (c), render code is not that different than the code shown in this article actually...

The interesting property is that each letters can be encoded into 8 bits by using a tiny subset of all the combination (offset + modulo) :

The code above are from the smallest / aggressively optimized ones but there is other type of renderer i didn't mention which may be all found here (warning: code might be a mess!), they tend to produce a bit heavier x86 code.