LBX X Consortium Algorithms

X Version 11, Release 7.7

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Table of Contents

Introduction
Streaming Compression
Bitmap Compression
Pixmap Compression
Colormap Algorithm
Extensions

Introduction

The Low Bandwidth X extension allows for negotiating various algorithms used by
LBX. This document describes the algorithms used in the Consortium
implementation of LBX in the X11 Release 6.4.

Streaming Compression

LBX negotiates the use of a stream compressor. The consortium implementation
defines a stream compressor named XC-ZLIB, which is based on the Zlib version
1.0 compression library by Gailly & Adler.

The XC-ZLIB compressor is presented with a simple byte stream - the X and LBX
message boundaries are not apparent. The data is broken up into fixed sized
blocks. Each block is compressed using zlib, then a two byte header is
prepended, and then the entire packet is transmitted. The header has the
following information:

     out[0] (length & 0xfff) >> 8 | ((compflag) ? 0x80 : 0);
     out[1] = length & 0xff;

If the compflag is false, then the contents of the block are not compressed.

Bitmap Compression

LBX also negotiates for bitmap compression. The consortium implementation
defines a bitmap compressor named XC-FaxG42D, which uses the CCITT Group 4 2D
compression algorithm.

Pixmap Compression

LBX allows for the negotiation of pixmap compression. The consortium
implementation does not define a pixmap compression algorithm. (A run-length
encoding algorithm was proposed, but experimentation proved it was less
efficient than allowing the stream compressor to compress the image.

Colormap Algorithm

LBX negotiates for use of a colormap algorithm, used for color matching when
the proxy allocates pixels in a grabbed colormap. The consortium implementation
defines an algorithm named XC-CMAP. This algorithm consists of three parts,
resolving to a hardware color, finding the closest existing color, and what
free cell to allocate.

The XC-CMAP algorithm resolves a color to a hardware color in the following
manner:

#define RESCALE(x, nbits) (x >> (16 - nbits)) * 65535 / ((1 << nbits) - 1)
#define GRAY(r, g, b) (30L * r + 59L * g + 11L * b) / 100

sigbits = pVisual->bitsPerRGB;

switch (pVisual->class) {
   case PseudoColor:
   case DirectColor:
   case StaticColor:
   /* rescale to rgb bits */
      *red = RESCALE(*red, sigbits);
      *green = RESCALE(*green, sigbits);
      *blue = RESCALE(*blue, sigbits);
      break;
   case GrayScale:
     /* rescale to gray then rgb bits */
     *blue = *green = *red = RESCALE(GRAY(*red, *green, *blue), sigbits);
      break;
   case StaticGray:
     /* rescale to gray then [0..limg] then [0..65535] then rgb bits */
     *blue = *green = *red = RESCALE(RESCALE(GRAY(*red, *green, *blue),
pVisual>numPixelBits), sigbits);
      break;
    case TrueColor:
      /* rescale to [0..limN] then [0..65535] then rgb bits */
      *red = RESCALE(RESCALE(*red, pVisual->numRedBits), sigbits);
      *green = RESCALE(RESCALE(*green, pVisual->numGreenBits), sigbits);
      *blue = RESCALE(RESCALE(*blue, pVisual->numBlueBits), sigbits);
      break;
  }

The XC-CMAP algorithm matches a color to an existing pixel in static visuals by
finding the pixel with the lowest color match error, computed as follows:

error = errRed * errRed + errGreen * errGreen + errBlue * errBlue

The XC-CMAP algorithm selects a free pixel to allocate by selecting the free
pixel with the lowest index from the free pixels known to the proxy. For direct
visuals, it uses the lowest free or matching pixel subfield known to the proxy
for each color.

Extensions

LBX allows for extensions to LBX to enable additional compression or
short-circuiting. The consortium implementation does not define any extensions
to LBX.