What algorithm did Microsoft use to dither colour in early versions of Windows?

Basically, Windows used the basic 16-color CGA palette, which included 4 shades of monochrome, and 12 basic colors (two each of red, green, blue, yellow, purple, and teal), which later formed the basis of the "web safe palette" that became popular during the early days of the Internet.

The algorithm used back then was known as the Bayer dithering technique, otherwise referred to as ordered dithering. The basic idea was to generate a grid of threshold values in a mathematical arrangement that favors nearly consistent values equal distances from each other, which is what produces the cross-hatch effect.

This article basically describes the pseudocode algorithm:

Threshold = COLOR(256/4, 256/4, 256/4); /* Estimated precision of the palette */
For each pixel, Input, in the original picture:
Factor  = ThresholdMatrix[xcoordinate % X][ycoordinate % Y];
Attempt = Input + Factor * Threshold
Color = FindClosestColorFrom(Palette, Attempt)
Draw pixel using Color

And they also included some example source code written in PHP:

<?php

/* Create a 8x8 threshold map */
$map = array_map(function($p)
                 {
                   $q = $p ^ ($p >> 3);
                   return ((($p & 4) >> 2) | (($q & 4) >> 1)
                         | (($p & 2) << 1) | (($q & 2) << 2)
                         | (($p & 1) << 4) | (($q & 1) << 5)) / 64.0;
                 }, range(0,63));

/* Define palette */
$pal = Array(0x080000,0x201A0B,0x432817,0x492910,  
             0x234309,0x5D4F1E,0x9C6B20,0xA9220F,
             0x2B347C,0x2B7409,0xD0CA40,0xE8A077,
             0x6A94AB,0xD5C4B3,0xFCE76E,0xFCFAE2);

/* Read input image */
$srcim = ImageCreateFromPng('scene.png');
$w = ImageSx($srcim);
$h = ImageSy($srcim);

/* Create paletted image */
$im = ImageCreate($w,$h);
foreach($pal as $c) ImageColorAllocate($im, $c>>16, ($c>>8)&0xFF, $c&0xFF);

$thresholds = Array(256/4, 256/4, 256/4);

/* Render the paletted image by converting each input pixel using the threshold map. */
for($y=0; $y<$h; ++$y)
  for($x=0; $x<$w; ++$x)
  {
    $map_value = $map[($x & 7) + (($y & 7) << 3)]; 
    $color = ImageColorsForIndex($srcim, ImageColorAt($srcim, $x,$y));
    $r = (int)($color['red']   + $map_value * $thresholds[0]);
    $g = (int)($color['green'] + $map_value * $thresholds[1]);
    $b = (int)($color['blue']  + $map_value * $thresholds[2]);
    /* Plot using the palette index with color that is closest to this value */     
    ImageSetPixel($im, $x,$y, ImageColorClosest($im, $r,$g,$b));
  }
ImagePng($im, 'scenebayer0.png');

Basically, the entire thing was dreamed up by Bayer, and this algorithm dominated the market during the 4-bit era of computer graphics.

You can read more about ordered dithering from DITHER.TXT, which basically explains different algorithms and sample implementations.

Note that your source images should be in full 256 color or better, and your palette should consist of these colors:

#000000 #808080
#800000 #FF0000
#008000 #00FF00
#808000 #FFFF00
#000080 #0000FF
#800080 #FF00FF
#008080 #00FFFF
#C0C0C0 #FFFFFF

Always dither from a full-color image, otherwise it'll probably look even worse than you intended. Dithering in realtime is trivial for modern systems, as even classic 33mhz systems that ran Windows had no trouble implementing the Bayer dithering pattern.

As @phyrfox mentions, it is ordered dithering using a bayer matrix.

I recently was trying to find a 16x16 bayer matrix (256 discrete values) but all the ones I could find were 8x8 max, so I derived the algorithm. It's actually a pretty simple recursion: (Python)

def InitBayer(x, y, size, value, step,
              matrix = [[]]):
    if matrix == [[]]:
        matrix = [[0 for i in range(size)]for i in range(size)]

    if (size == 1):
        matrix[y][x] = value
        return

    half = size/2

    #subdivide into quad tree and call recursively
    #pattern is TL, BR, TR, BL
    InitBayer(x,      y,      half, value+(step*0), step*4, matrix)
    InitBayer(x+half, y+half, half, value+(step*1), step*4, matrix)
    InitBayer(x+half, y,      half, value+(step*2), step*4, matrix)
    InitBayer(x,      y+half, half, value+(step*3), step*4, matrix)
    return matrix

PNG images for the threshold matrix are located here:

https://github.com/tromero/BayerMatrix

As I recall, the Windows code did have some special cases.

• If you asked for #C0C0C0 you would of course get solid #C0C0C0. This was a special case; if you asked for #BFBFBF then you would get a chequerboard dither using #808080 and #FFFFFF.
• I think Windows used an 8×4 matrix, so it would only approximate 15-bit colour.
• If all channels had a value of #80 or less then it would dither using a palette of the seven dark colours and #000000.
• If at least one channel had a value of greater than #80 then it would dither using a palette of the seven bright colours, plus #808080 and #000000.

Best way to get a basic color palette is to start from RGB.

White: 255.255.255, Black: 0,0,0, Red: 255.0.0, Green: 0.255.0, Blue: 0.0.255

You have 5 colors there.

Then combine the pairs: RG ->> yellow (255.255.0) GB --> cyan (0.255.255) RB --> magenta (255.0.255)

Now they are 8

Then repeat with 127 instead of 255, you get 7 more (with mid-grey 127.127.127). Then add another grey if you need and you have 16.

That should cover the basics. If you want 32 colors, make the values 63 and then combine 255s with 127s to get another set of intermediary colors (i.e. 255.127.0 will give you orange).