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:
/* 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;
/* Define palette */
$pal = Array(0x080000,0x201A0B,0x432817,0x492910,
/* 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);
$g = (int)($color['green'] + $map_value * $thresholds);
$b = (int)($color['blue'] + $map_value * $thresholds);
/* Plot using the palette index with color that is closest to this value */
ImageSetPixel($im, $x,$y, ImageColorClosest($im, $r,$g,$b));
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:
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.