Westwood SHP Format (Dune II)

Westwood SHP Format (Dune II)

Format type	Tileset
Hardware	VGA
Max tile count	Technically 65535, but limited by addressing size in v1
Palette	Shared
Tile names?	No
Minimum tile size (pixels)	1x1
Maximum tile size (pixels)	65535×255
Plane count	1
Plane arrangement	Linear
Transparent pixels?	Palette-based
Hitmap pixels?	No
Metadata?	None
Supports sub-tilesets?	No
Compressed tiles?	Yes
Hidden data?	Yes
Games	Dune II Lands of Lore: The Throne of Chaos The Legend of Kyrandia 2: The Hand of Fate The Legend of Kyrandia 3: Malcolm's Revenge Command & Conquer Monopoly Command & Conquer: Sole Survivor Command & Conquer: Red Alert

The sprite format used in Dune II and the Legend of Kyrandia games is a collection of compressed 8-bit frames, where each frame can have its own set of dimensions. The format is also used for the mouse cursors in the early Command & Conquer games.

File format

The format comes in two versions; one used in v1.00 of Dune II, the other in the patched v1.07. The difference between the two types is that the newer type uses UINT32LE addressing, whereas the older version uses UINT16LE. Sadly, there is no clear version indicator in the header, meaning the type has to be derived from the data itself.

The frame data itself is compressed in two ways: first, the Westwood RLE-Zero algorithm (a flag-based RLE) is used to collapse all transparent background pixels. Then, this data is optionally compressed using the LCW algorithm.

Header

Offset	Data type	Name	Description
0x00	UINT16LE	NrOfFrames	The number of frames in the file.
0x02	UINTXXLE[NrOFFrames+1]	FrameOffsets	List of offsets to the headers of each frame. As mentioned, these are either UINT16LE or UINT32LE, depending on the version. In the v1.00 format, these offsets are relative to the beginning of the file. In v1.07, however, they are relative to the beginning of the FrameOffsets array.

As you see, the array has one more entry than the amount of frames. This last offset points to the end of the file. As noted, in v1.07 this is relative to the start of the FrameOffsets array, meaning the value in there will be two bytes less than the actual file size.

A classic check to distinguish the two types is to see if the 5th and 6th bytes in the file are zero; in a 16-bit array this would be the address of the second frame, while in 32-bit mode this would be the higher-than-0xFFFF part of the very first frame, which would require a ridiculously high frame count in the file to be anything else than zero.

Since the final entry in the array always equals the file size, this can also be used as version test. This check should test v1.00 first; even though chances are really small, it is technically possible that data NumImages*2 bytes into the file data behind the FrameOffsets array happens to contain data exactly matching the file end address. However, in 32-bit addressing, it is impossible for either the first or second half of a valid offset halfway down the array to ever match the file end value, since that should only occur once, at the end of the array.

Frames

Each of the addresses in the header (except for the last one) points to a frame, which is comprised of a header followed by compressed image data. The following sections will show how to interpret that data.

The final image data is a classic compact array of 8-bit data, with a stride equalling the frame width. It needs one of the game's included 6-bit RGB colour palettes to visualise it.

Header

Offset	Data type	Name	Description
0x00	BYTE[2]	Flags	A series of bit flags that give extra options on how to handle the data. The three flags are HasRemapTable (bit 1), NoLCW (bit 2) and CustomSizeRemap (bit 3). Bit 3 should never be enabled if bit 1 isn't.
0x02	UINT8	Slices	The format's transparency-collapsing compression works per row. This indicates the number of rows. This value should always match the frame height.
0x03	UINT16LE	Width	The frame width.
0x05	UINT8	Height	The frame height.
0x06	UINT16LE	Filesize	The full size of the frame's data in the file, including this header.
0x08	UINT16LE	ZeroCompressedSize	Size of the data before RLE transparency decompression. If the NoLCW flag is not enabled, this gives the amount of space that needs to be reserved for the LCW decompression process. Otherwise it just equals the image data size behind the header.
0x0A	UINT8	RemapSize	This byte is only added if the CustomSizeRemap flag is enabled. If not, RemapSize defaults to 16.
0x0A or 0x0B	UINT8[RemapSize]	RemapTable	This table is only added if the HasRemapTable flag is enabled.

Image data decompression

This header is followed by the actual image data, which should first be decompressed using LCW (unless NoLCW is enabled), and then expanded using the Dune II version of the Westwood RLE-Zero algorithm.

Remapping

If a remap table is present, the image data has to be transformed with a simple remapping operation, in which every byte value p in the final uncompressed image data is replaced by RemapTable[p], compacting the used entries to small consecutive numbers. This remapping serves no purpose for the compression, but is required for the games' colour remapping system, so graphics that need to be remapped to different colours in the game (like the infantry and vehicles in Dune II) need to contain such a remap table.

Remap tables always contain a reference for all colour indices used in the image. If there are more than 16 used colours, the extra bit in the header is enabled to make the table longer. The tables are always created in the order the colours are found in the image data, with the exception that if index 0 appears anywhere in the image, it always needs to be on the first index, since trailing zeroes at the end of the remap range (in the normal up-to-16-entries mode) indicate the end of the table.

Optimisation

Being a pure indexed format, the Dune II SHP format can benefit from index deduplication; if two frames are identical, and are both saved in the same way in terms of compression and remapping, then the FrameOffsets array can simply refer to the same frame twice, which avoids saving identical duplicates.

This system does not seem to be used in the SHP files in Dune II, but it is used in the game's font format, and in the CPS-embedded variant of the format used in Lands of Lore. Note that this system always works, even if not explicitly supported, since the games that use the SHP format will simply follow the references in the FrameOffsets array without any extra checks.

Tools

The following tools are able to work with files in this format.

Name	Platform	View images in this format?	Convert/export to another file/format?	Import from another file/format?	Access hidden data?	Edit metadata?	Notes
Engie File Converter	Windows	Yes	Yes	Yes	No	N/A	Supports viewing, reading, and writing, including the remapping tables.
d2shpset	Windows (command line)	No	No	Yes	No	N/A	A small Dune II SHP writing utility written by OmniBlade of the Chronoshift (formerly RedAlert++) team to help Dune II mod makers. It supports generating the remap tables the game needs for applying house colours.
Red Horizon Utilities	Java (command line)	No	Yes	Yes	No	N/A	Support for Dune II SHP in it is experimental, and apparently it works better in certain older versions than in the newest ones. Original site is defunct. Backups of the tools can be found here.
XCC Mixer	Windows	Yes	Yes	No	No	N/A	Only supports viewing the format and converting it to frames. Has no support for creating files of this type.