Sixty-Four Squared, in Fix15

The Unit libmypaint Thinks In

libmypaint never sees a canvas. It sees tiles. When a dab lands, the engine works out which tiles the dab's box overlaps and asks its host for each one, by tile coordinate, through a request that says whether it only wants to read. The host lends a buffer; libmypaint blends into it; the host gets it back. Everything else about Ariandel's pixels follows from the shape of that buffer, so it is worth knowing it cold.

A tile is 64×64 pixels (MYPAINT_TILE_SIZE, set to 64 in libmypaint's mypaint-config.h), four channels per pixel, RGBA, premultiplied, and every channel is a uint16_t in 15-bit fixed point: 0 is nothing, and 1.0 is 1 << 15, which is 32,768. Ariandel's C bridge names the three numbers once, in ariandel_surface.h: ARD_TILE_SIZE 64, ARD_TILE_VALUES (64 × 64 × 4), and ARD_FIX15_ONE (1 << 15). The Swift side mirrors them in a Tile enum whose size is read from the C macro, so there is exactly one place the size is decided.

Do the arithmetic once and keep it: 16,384 values per tile, two bytes each, 32,768 bytes, 32 KiB, per tile. A 4096×4096 layer is 64 × 64 = 4,096 tiles, so if every tile is painted, that one layer is 128 MiB of native pixels. Hold that number. It is the whole of the third lesson.

Sparse by Construction

Each layer's pixels live in a TileStore, a dictionary from TileKey to buffer. An absent key means a transparent tile, so an empty layer costs nothing and a sketch in one corner of a huge canvas costs only the corner. The store keeps itself sparse: setTile drops a buffer that is fully transparent instead of storing it, and at the end of every stroke the painter calls prune on the tiles it touched, because libmypaint asks for every tile a dab's box overlaps and an eraser can leave some of them empty.

One small piece of care is worth copying. TileKey(containingPixelX:y:) floors negative coordinates instead of truncating them toward zero, so pixel −1 lands in tile −1, not tile 0. Symmetry and clone offsets can put a dab left of the origin, and a truncating division would quietly paint it into the wrong tile.

Why Fifteen Bits and Not Sixteen

Read libmypaint's ordinary blend (the second code block) and the choice explains itself. For each pixel, the dab's strength becomes opa_a, the remainder becomes opa_b = (1<<15) - opa_a, and every channel is (opa_a*top + opa_b*bottom) / (1<<15). Because 1.0 is a power of two, that divide is a shift. Because each factor is at most 2¹⁵ and the two weights sum to 2¹⁵, the whole numerator stays at or below 2³⁰, comfortably inside a 32-bit unsigned integer. And 32,768 itself fits in a uint16_t, so fully opaque is exactly representable. Make 1.0 the next power of two, 65,536, and it no longer fits in a uint16_t; make it 65,535 instead and you lose the shift and the headroom together: the divide becomes a real division, and the numerator climbs to within a hair of 2³². Those are properties of the arithmetic you can read off the page, not a quote from libmypaint's authors.

Integers also do not drift in storage. A value written is the value read back, and Ariandel's package stores these tiles losslessly, in this very format, which is why its file format can promise that a reopened artwork is bit-identical.

Why Premultiplied

Premultiplied means each color channel is already multiplied by alpha. That is what makes the blend above a single multiply-add per channel: result = top + (1 − top alpha) × bottom, alpha included, with no division. Straight alpha needs a divide by the resulting alpha to get back to a color. Premultiplied also gives transparency one representation: a pixel with zero alpha has zero color, which is why Ariandel's ard_fix15_is_transparent only has to look at the alpha channel to decide a tile can be dropped.

Leaving Fix15: Two Exits, One Rounding

Nothing outside the engine speaks fix15, so pixels leave through small C loops in ariandel_pixels.c. Two matter here. ard_fix15_to_rgba8_premultiplied feeds the GPU's display mirror: each value becomes (v * 255 + 16384) >> 15, which is round-to-nearest, clamped. ard_fix15_to_rgba8_straight feeds PSD layer channels and layer thumbnails: it first un-premultiplies in fix15, ((c << 15) + a / 2) / a, clamped to one, and only then rescales to 8 bits with the same rounding. A pixel with zero alpha becomes all zeros.

The order matters, and the sketch below shows why. A warm orange at 1% alpha is 262, 66, 33, 328 in fix15. Through the straight exit it comes out as 204, 51, 26: the orange survives. Through the premultiplied 8-bit exit it becomes 2, 1, 0 at alpha 3, and if anyone later divides that back out, the color reads 170, 85, 0. Eight bits of premultiplied color simply do not have room for a faint pixel's hue. That is fine for a picture on a screen. It is fatal for anything that would write pixels back into a layer, and Ariandel learned that the hard way (lesson three, and Track 6's merge story).

Store pixels in the format your hottest math wants, and convert only at the edges. libmypaint blends every pixel under every dab, so the tile is shaped for the blend: premultiplied, power-of-two fixed point, integer all the way. Display, files and Pippa's look each convert on the way out, and none of them is ever allowed to become the source.

Code

Ariandel's tile geometry (AriandelEngine/Tiles.swift, verbatim)·swift

/// Tile geometry shared with libmypaint.
public enum Tile {
    /// Edge length in pixels (libmypaint's MYPAINT_TILE_SIZE).
    public static let size = Int(ARD_TILE_SIZE)
    /// UInt16 values per tile (premultiplied RGBA, 15-bit fixed point).
    public static let valueCount = size * size * 4
    /// Pixels per tile.
    public static let pixelCount = size * size
    /// Bytes per tile in the engine's native format.
    public static let byteCount = valueCount * MemoryLayout<UInt16>.stride
    /// Fixed-point one.
    public static let fix15One: UInt16 = 1 << 15

libmypaint's Normal blend: premultiplied 'over' in 15-bit integers (brushmodes.c, verbatim)·c

void draw_dab_pixels_BlendMode_Normal (uint16_t * mask,
                                       uint16_t * rgba,
                                       uint16_t color_r,
                                       uint16_t color_g,
                                       uint16_t color_b,
                                       uint16_t opacity) {

  while (1) {
    for (; mask[0]; mask++, rgba+=4) {
      uint32_t opa_a = mask[0]*(uint32_t)opacity/(1<<15); // topAlpha
      uint32_t opa_b = (1<<15)-opa_a; // bottomAlpha
      rgba[3] = opa_a + opa_b * rgba[3] / (1<<15);
      rgba[0] = (opa_a*color_r + opa_b*rgba[0])/(1<<15);
      rgba[1] = (opa_a*color_g + opa_b*rgba[1])/(1<<15);
      rgba[2] = (opa_a*color_b + opa_b*rgba[2])/(1<<15);

    }
    if (!mask[1]) break;
    rgba += mask[1];
    mask += 2;
  }
};

A minimal sketch: fix15 premultiplied to 8-bit, with the exact rounding of ard_fix15_to_rgba8_straight and ard_fix15_to_rgba8_premultiplied (compiled and run with clang)·c

#include <stdint.h>
#include <stdio.h>

#define FIX15_ONE 32768u
#define FIX15_HALF 16384u

static uint32_t clamp_u32(uint32_t v, uint32_t max) { return v > max ? max : v; }

/* Premultiplied fix15 -> straight 8-bit, the same arithmetic as
 * Ariandel's ard_fix15_to_rgba8_straight (PNG/PSD channels). */
static void to_straight8(const uint16_t *src, uint8_t *dst) {
    const uint32_t a = clamp_u32(src[3], FIX15_ONE);
    if (a == 0) { dst[0] = dst[1] = dst[2] = dst[3] = 0; return; }
    for (int c = 0; c < 3; c++) {
        /* un-premultiply in fix15, rounding to nearest */
        const uint32_t straight = clamp_u32((((uint32_t)src[c] << 15) + a / 2) / a, FIX15_ONE);
        /* rescale 0..32768 to 0..255, rounding to nearest */
        dst[c] = (uint8_t)((straight * 255u + FIX15_HALF) >> 15);
    }
    dst[3] = (uint8_t)((a * 255u + FIX15_HALF) >> 15);
}

/* Premultiplied fix15 -> premultiplied 8-bit, as
 * ard_fix15_to_rgba8_premultiplied (the display mirror). */
static void to_premul8(const uint16_t *src, uint8_t *dst) {
    for (int i = 0; i < 4; i++)
        dst[i] = (uint8_t)clamp_u32(((uint32_t)src[i] * 255u + FIX15_HALF) >> 15, 255u);
}

/* Store a straight color (0...1) at alpha a, premultiplied, in fix15. */
static void make_pixel(uint16_t *px, double r, double g, double b, double a) {
    px[0] = (uint16_t)(r * a * FIX15_ONE + 0.5);
    px[1] = (uint16_t)(g * a * FIX15_ONE + 0.5);
    px[2] = (uint16_t)(b * a * FIX15_ONE + 0.5);
    px[3] = (uint16_t)(a * FIX15_ONE + 0.5);
}

static void show(const char *name, double alpha) {
    uint16_t px[4];
    uint8_t s[4], p[4];
    make_pixel(px, 0.80, 0.20, 0.10, alpha); /* a warm orange */
    to_straight8(px, s);
    to_premul8(px, p);
    printf("%-6s fix15 %5u %5u %5u %5u | straight8 %3u %3u %3u a=%3u | premul8 %3u %3u %3u a=%3u",
           name, px[0], px[1], px[2], px[3], s[0], s[1], s[2], s[3], p[0], p[1], p[2], p[3]);
    if (p[3]) /* what the 8-bit premultiplied value says the color was */
        printf(" -> back to straight %3u %3u %3u", p[0] * 255u / p[3], p[1] * 255u / p[3], p[2] * 255u / p[3]);
    printf("\n");
}

int main(void) {
    show("solid", 1.00);
    show("half", 0.50);
    show("faint", 0.01);
    return 0;
}

/* Output (clang, -std=c99 -O2):
 * solid  fix15 26214  6554  3277 32768 | straight8 204  51  26 a=255 | premul8 204  51  26 a=255 -> back to straight 204  51  26
 * half   fix15 13107  3277  1638 16384 | straight8 204  51  25 a=128 | premul8 102  26  13 a=128 -> back to straight 203  51  25
 * faint  fix15   262    66    33   328 | straight8 204  51  26 a=  3 | premul8   2   1   0 a=  3 -> back to straight 170  85   0
 */

Exercise

Compile the sketch, then pick a color you actually paint with and change make_pixel's arguments to it. Lower the alpha step by step (0.5, 0.2, 0.1, 0.05, 0.02, 0.01) and record the 'back to straight' color from the premultiplied 8-bit path at each step. Find the alpha at which any channel first drifts by more than two steps out of 255 from the straight path's answer. That alpha is where an 8-bit premultiplied buffer stops being able to carry your color.

Hint

Dark and saturated colors fail earliest, because their small channels round to zero first. If your color survives down to 1%, try one with a channel below 0.1, such as a deep blue, and watch that channel vanish while the others shift.

The Unit libmypaint Thinks In

Sparse by Construction

Why Fifteen Bits and Not Sixteen

Why Premultiplied

Leaving Fix15: Two Exits, One Rounding

Code

External links

Exercise

Progress

Comments 0