Documenting .lin format used for some console titles

[landaire]

Over the past couple weeks I've been reverse engineering the .lin files used in Splinter Cell for the original Xbox and am currently in the process of writing a blog post about how cursed the format is. I saw some discussion in #104, but I thought that this might warrant a dedicated issue for documenting the format. I'll try to be succinct as not to overwhelm with info, and feel free to ask any clarifying questions for anything. I understand that some of this is known, but just to centralize everything I'll include everything anyways:

Some high-level notes about the format:

• File sizes are wrong
• Byte sizes are wrong
• Offsets are wrong
• Seeks are fake
• Data can only be read forward
• All data is load-order dependent

Each map directory contains at least two files:

• common.lin contains a file table and some shared data
• mapname.lin (like menu.lin) contains level-specific data.

The files (at least for SC1 on OG Xbox) have the following outer .lin structure:

u32 decompressed_data_len
u32 compressed_data_len
byte zlib_block[compressed_data_len]

For common.lin in this game, the first 4 independently-compressed zlib blocks are:

uncompressed_data_size: 0x648EEE
texture_cache_size (? - later used when calling D3DDevice_CreateTexture2): 0x1B0000
vertex_buffer_size (? - ditto, D3DDevice_CreateVertexBuffer2): 0x6740
index_buffer_size (? - ditto, XGSetIndexBufferHeader): 0xD38

The common.lin and mapname.lin values for these fields get added together after both are decoded.

The common.lin file has a file table not present in map-specific .lin files which looks something like:

/* ==== LIN-Specific Prefix ==== */

// These three, from research + reverse engineering, should not be considered
// as part of the "whole" file
uint32_t        maybe_load_address; // 5C 58 9E 13 in common.lin
compressed_int  name_length;        // 0 in common.lin
cstr            name;

/* ==== Begin "true" common.lin file header ==== */

uint32_t        magic;              // 0x9fe3c5a3 in little endian, i.e. A3 C5 E3 9F

// unk_address - load_address gives you the start of the file table, relative to the magic?
uint32_t        unk_address;        // B4 92 9B 13, suspiciously similar to maybe_load_address
uint32_t        load_address2;      // 5C 58 9E 13 same as maybe_load_address

uint8_t         unknown[8];         // 01 00 00 00 04 2A D6 FE
compressed_int  file_entry_count;

struct FileEntry {
    compressed_int  name_len;
    cstr            name;
    uint32_t        offset;
    uint32_t        len;
    uint32_t        unk;
}

Note: As far as I can tell the suspected load addresses never change for any .lin file. The load addresses don't matter anyways -- nothing gets mapped to these addresses at runtime and for reasons explained further down they're irrelevant.

The partial file table for SC1 is:

FileEntry {
    name: Maps\\menu\\menu.unr,
    offset: 0x0,
    len: 0xDEEE,
    unk: 0x0,
},
FileEntry {
    name: Maps\\1_1_0Tbilisi.unr,
    offset: 0xDEF0,
    len: 0x17C96D,
    unk: 0x0,
},
FileEntry {
    name: Maps\\1_1_1Tbilisi.unr,
    offset: 0x18A860,
    len: 0x213498,
    unk: 0x0,
},
FileEntry {
    name: Maps\\1_1_2Tbilisi.unr,
    offset: 0x39DD00,
    len: 0x196389,
    unk: 0x0,
},
FileEntry {
    name: Maps\\0_0_2_Training.unr,
    offset: 0x534090,
    len: 0xC9F0F,
    unk: 0x0,
},
FileEntry {
    name: Maps\\0_0_3_Training.unr,
    offset: 0x5FDFA0,
    len: 0x118648,
    unk: 0x0,
},
FileEntry {
    name: Maps\\1_2_1DefenseMinistry.unr,
    offset: 0x7165F0,
    len: 0x249AF6,
    unk: 0x0,
},
FileEntry {
    name: Maps\\1_2_2DefenseMinistry.unr,
    offset: 0x9600F0,
    len: 0x20F662,
    unk: 0x0,
},

The offsets and lengths in this table are not to be trusted. They are simply wrong. The last entry has an offset of 0x9600F0 which is very much outside of the range of the common.lin, and for known maps (like menu.lin) the data doesn't make sense no matter how you spin it. It's not at offset 0x0 in either file, and it's not 0xDEEE bytes long.

The offsets and byte sizes in this format do not matter because there are various tricks used to fake the sizes of data read and the file readers cannot seek.

Because the underlying data is compressed, you cannot easily map a decompressed offset to a compressed offset and partially decompress data. The game engine, through reverse engineering, treats a Seek() as a position property update and the underlying reader's Seek() is a no-op.

The data can only be read going forward and seeking never actually happens.

The file table is only read as a consequence of parsing the data before it, and the file that comes after the file table data is only read as a consequence of it always being the first file that's read. Without knowing the first file that's read, you can carve out all Unreal Engine Package files (magic 0x9E2A83C1), but those will have incorrect exports.

The first package in SC1 is Engine which has the following header (your lib parses this fine btw):

pub struct PackageHeader<'i> {
    pub version: u32,
    pub flags: u32,
    pub name_count: u32,
    pub name_offset: u32,
    pub export_count: u32,
    pub export_offset: u32,
    pub import_count: u32,
    pub import_offset: u32,

    // Note: this is not in the above documented description
    pub unk: u32,
    // Ditto.
    // Not shown: compressed int for length of this data at this position
    pub unknown_data: &'i [u8],

    pub guid_a: u32,
    pub guid_b: u32,
    pub guid_c: u32,
    pub guid_d: u32,
    // Not shown: compressed int for length of this data at this position.
    pub generations: Vec<GenerationInfo>,
}

PackageHeader {
    version: 0x110064,
    flags: 0x1,
    name_count: 0xE10,
    name_offset: 0x88,
    export_count: 0xFFA,
    export_offset: 0x117AF3,
    import_count: 0x4E,
    import_offset: 0x11783E,
    unk: 0xFF0ADDE,
    unknown_data: [
      ...
    ]
    guid_a: 0x0,
    guid_b: 0x0,
    guid_c: 0x0,
    guid_d: 0x0,
    generations: [
        GenerationInfo {
            export_count: 0xFFA,
            name_count: 0xE10,
        },
    ],
}

The described offsets are wrong. The counts are correct. If you just parse the data up to the end of the export table end, everything is fine.

For SC1 the first object that the engine attempts to resolve is Engine.GameEngine, which forces the System\Engine.u script to be loaded and the GameEngine export to be parsed. This of course requires resolving its super objects, which triggers a read of its parent types Engine.Engine, Core.Subsystem(? I think this is in Core), and Core.Class.

Since all of these are lazy-loaded, the exact load order is:

1. Engine.u header read/parse
2. Engine's GameEngine export lookup
3. Engine.Engine object lookup
4. Core.Subsystem object lookup
5. Core.u header read/parse
6. Core.Class object lookup
7. Core.Class property deserialization
8. Core.Subsystem property deserialization
9. Engine.Engine property deserialization
10. Engine.GameEngine property deserialization

Upon finishing deserializing an export, the game engine gets the stream position, calculates the delta from the recorded pre-serialization position, and asserts that the read size equals the export's SerialSize.

Some of these properties seem to trigger a seek to do reads (possibly to parse the property class type info?), which you'd think would throw off that logic. But those cases seem to restore their prior position when finishing their work. Since seeks are a nop, this causes the stream to advance but restores the position field used for the above logic, so the deserializer thinks that the accurate amount of data was read even if it wasn't.

This means however that for an export with an offset of 0x0 and size of 0x1c, the complete deserialization sequence may start at 0x0 and end at (random number here) 0x100 depending on what its properties contain, whether or not its parent types have been deserialized yet, and their properties as well.

This inherently means that this format is 100% load-order dependent. Successful deserialization of this data depends on examining which order the game itself loads data, or else your exports will be reading garbage data from incorrect positions.

IF this load order were obtained and documented (which I can do), this library might be able to enter into an "ignore seeks, they aren't real" mode that loads the exports in the exact sequence that the game loads them when entering a map. From there you can prune any unloaded exports/imports and statically reserialize the file with correct sizes/offsets. I don't know enough about your implementation to say how difficult this would be in practice.

Note that I've managed to dump some packages from the game by doing some binary patches and calling the serialization routine at runtime. These files do successfully load in UE Explorer.

I'll link the blog post once it's out which will have deeper technical details so that the work can be reproduced.

[landaire]

I forgot that I have the export load order defined already all the way up to the main menu load: https://gist.github.com/landaire/c1f516c43e0dd4dbc5c40029ff73d923

The data is serialized in this order:

properties = [class_index, super_index, package_index, object_name, object_flags, serial_size, serial_offset]

ida_kernwin.msg("Export data: " + ",".join(hex(n) for n in properties) +"\n")

[landaire]

My blog post: https://landaire.net/a-file-format-uncracked-for-20-years/

I guess to actually succinctly describe .lin files: every byte read from a normal file is written to the LIN file so that seeks do not need to occur. Data which is partially read, then re-read, may even be duplicated to accommodate.

For example, the "normal" representation of a byte sequence may be:

0xA, 0xB, 0xC, 0xD

Maybe the engine read the first two bytes and does some logic to determines it needs to read the other two as part of it too. So they do a two-byte read, reset position, then a 4-byte read creating this sequence of bytes read:

0xA, 0xB, [seek - 2] 0xA, 0xB, 0xC, 0xD

Resulting in the following bytes being written to the LIN file:

0xA, 0xB, 0xA, 0xB, 0xC, 0xD

Proper static parsing of LIN files would require matching the exact load behaviors of the engine.

[EliotVU]

Great development, thanks for sharing this with all of us!

I had intended to look at this myself, a while ago, but couldn't make much sense of it myself, it does seem that this format also appears to be used by the PS2 version of UT99 as well (no idea if the format differs)

[landaire]

I've tried a variety of things to cut corners to avoid having to actually parse the format completely but keep hitting roadblocks.

I think the only path forward is to re-implement parsing exactly as the game engine does down to the seek behavior and use information about load order from the title to guide unpacking.

For my most recent attempt I've written a QEMU plugin for the OG Xbox XEMU emulator, recorded I/O operations, and I'm actually able to use this information to rewrite the files with correct lengths/offsets using my own program. This approach hits some snags though with some types that use lazy arrays, such as UTexture. These encode offsets into the structure which breaks reading this back into UE Explorer.

This weekend I'm going to play around with reimplementing a lot of the deserializers in UELib into my own custom program with a focus on ensuring exact 1:1 I/O behavior and seeing how far that gets me.

I don't know how much effort it would take to make UE Lib support linking at load time and loading exports like this, so for now I'm going to experiment within my own codebase for rapid prototyping.

[EliotVU]

lazy arrays, such as UTexture. These encode offsets into the structure which breaks reading this back into UE Explorer.

Those damn lazy arrays are a curse :) Why'd they use an absolute file offset there?

I don't know how much effort it would take to make UE Lib support linking at load time and loading exports like this, so for now I'm going to experiment within my own codebase for rapid prototyping.

I do have some unpushed work towards this (actually working), perhaps this may be of use to you?

Nonetheless, I do recommend checking out the 'Next' branch, a much cleaner, and re-worked stream setup.

[landaire]

Nonetheless, I do recommend checking out the 'Next' branch, a much cleaner, and re-worked stream setup.

I'll check it out. I'd really hate to cause any fragmentation here from tools people already use.

Why'd they use an absolute file offset there?

I have no clue. The I/O behavior is kinda odd here. 0_0_Training_tex.utx for example has an offset of 0x4431C0.

The read operations are:

• 0x3A bytes as single-byte or 4-byte reads
• Read 0x4000
• Seek from current position (0x4471FA -- 0x403A from start), to 0x4431F7 (0x37 from data start)
• Seek BACK to 0x4471FA
• Continue reading

I noticed that with my current method of rewriting these files, this produces the following data. Note that the highlighted bit is the 0x4471FA offset. So it must have read the array, then seeked backwards then attempted to seek forward and skip over what it just read.

If I have my tool rewrite these to zero or the correct offset they load correctly (nvm, didn't realize there's actually an error here), but fail to load in UPK Explorer. Files dumped at runtime from the game load fine in UPK Explorer so this is definitely a me issue. Probably some other export of a different type with similar problems.

[EliotVU]

I think you can re-calculate the absolute position there on basis of the ElementCount that comes after it:

See the UELib implementation of this:

   int elementSize = Unsafe.SizeOf<TElement>();
   // ...
   // Absolute position in stream
   long skipOffset = stream.ReadInt32();
   // ...
   ElementCount = stream.ReadLength();

   // Occurs with SCCT_Versus
   if (skipOffset == 0)
   {
       StorageSize = ElementCount * elementSize;
       StorageOffset = stream.AbsolutePosition;

       stream.Position += StorageSize;

       return;
   }

   StorageSize = skipOffset - stream.AbsolutePosition;
   StorageOffset = stream.AbsolutePosition;

   stream.AbsolutePosition = skipOffset;

You can assume that elementSize is equivalent to 1 byte for UTexture so this can be directly re-used to calculate the absolute position as stream.Position + ElementCount, but beware that ElementCount can be a compact integer.

[landaire]

Yeah I noticed after writing that comment that I was using relative offsets, not stream absolute offsets. Fixed that and they load fine in UE Explorer, but not in UPK Explorer. It's rather odd because none of the other exports seem to throw exceptions, so I'm not sure why UPK Explorer is complaining.

[VendorX]

Do yourself a favor: don't bother with it. There are no "magic" bytes, only engine logics. A perfect understanding of how Unreal Engine works – just knowing the basics is not enough. Even having the source code of the gam will not solve the reading problem.

• The game engine stores all loaded packages and objects in memory (GObjObjects).
• Reading is a recourse operation,
• Not the entire files are loaded/reside in *.lin - only the necessary ones.

The reading order is a combination of processing the ExportMap (real objects) and ImportMap (dependencies) of each package. For example, the first package in a LevelName.lin file will be LevelName.unr, the second will be Engine.u, then Core.u, and so on. LIN stores only the objects necessary to build the level. This means that all content from .utx/.usx/etc. is split into *.lin packages, and all of them must be loaded to recreate the game comtent.

[landaire]

@VendorX yes, I know. Please read my blog post... or even this issue. Currently I can dump data at runtime with some decent success (some data changes between deserialization and re-serialization), or use runtime information to statically rewrite the files. The latter has success except for types which use lazy arrays, which I'm currently debugging.

A perfect understanding of how Unreal Engine works – just knowing the basics is not enough. Even having the source code of the gam will not solve the reading problem.

I have enough information from how the game conducts I/O at runtime to write tests which assert that an external reader processes the data in the exact same way.

This is not a technically challenging problem at this point.

[VendorX]

Good for you ... and good luck - you will need it.

[landaire]

@EliotVU sorry for the lazy question, but what changes in particular did you think would be useful from the next branch?

I took a look and I see at least two distinct architectural changes that would need to occur:

1. LoadStream should use the underlying buffer instead of a MemoryStream in UObject.LoadStream since the data is not guaranteed to be contiguous.
2. CreateObject on imports should trigger deserializing the package header for imports whose packages have not yet been loaded. CreateObject's event could maybe be hijacked for this purpose?

I've been experimenting in my own codebase and have managed to get decent parsing of the objects I've defined so far (it's a small subset so far but UStruct/fields are the biggest hurdle I imagine and I almost have those tackled?).

My approach has been to load dumped runtime metadata (you can find this here but please note this is ~100MB, so maybe just wget it), and use the metadata to guide deserialization.

For example, the metadata contains a top-level key raw_io_ops that looks like:

  {
    "Seek": {
      "to": 6917,
      "from": 67715
    }
  },
  {
    "Read": {
      "len": 1
    }
  },
  {
    "Read": {
      "len": 1
    }
  },
  {
    "Read": {
      "len": 1
    }
  },

This array contains each individual seek/read operation that occurs in the game engine when loading common.lin and then menu.lin. I constructed a custom Stream object which for each seek/read operation will remove the next item from this queue and ensure that the operations match. If any read/seek operation is performed which does not match what's expected an assertion is triggered in my case.

Note: this list does NOT contain seeks/reads from reading the package header. These are only from creating export objects.

There is also a top-level key called object_load_order which is an array like:

  "Engine.GameEngine",
  "Echelon.ECanvas",
  "Engine.Input",
  "Core.Function",
  "Core.Struct",
  "Core.Field",
  "Core.Const",
  "Core.TextBuffer",
  "Core.Enum",
  "Core.LinkerLoad",
  "Core.Linker",
  "Core.LinkerSave",
  "Core.Commandlet",
  "Core.Factory",
  "Core.TextBufferFactory",
  "Core.Language",
  "Core.ByteProperty",
  "Core.Property",
  "Core.IntProperty",
  "Core.BoolProperty",
  "Core.FloatProperty",
  "Core.ObjectProperty",
  "Core.ClassProperty",
  "Core.NameProperty",
  "Core.StrProperty",
  "Core.FixedArrayProperty",
  "Core.ArrayProperty",
  "Core.MapProperty",
  "Core.StructProperty",
  "Core.System",
  "Core.Package",
  "Core.State",
  "Core.Class",
...

These are the full names of each item passed to StaticLoadObject() at runtime which results in a successful load. I imagine that some of these are triggered by nature of loading dependencies, so I imagine some of these will objects will already be loaded.

None.MyLevel is in this list, and obviously None is not a valid module name. I think this is because the game passes some class to StaticLoadObject() which skips name resolution or something? I figured for this case there should only be one MyLevel export.

And finally there's file_load_order containing:

  "..\\System\\Engine.u",
  "..\\System\\Core.u",
  "..\\System\\Echelon.u",
  "..\\Textures\\HUD.utx",
  "..\\Sounds\\FisherFoley.uax",
  "..\\Sounds\\CommonMusic.uax",
  "..\\System\\EchelonEffect.u",
  "..\\Textures\\ETexSFX.utx",
  "..\\Textures\\2-1_CIA_tex.utx",
  "..\\Textures\\generic_shaders.utx",
  "..\\Textures\\LightGenTex.utx",
  "..\\Textures\\5_1_PresidentialPalace_tex.utx",
  "..\\Textures\\1_2_Def_Ministry_tex.utx",
  "..\\Textures\\EGO_Tex.utx",
  "..\\Textures\\ETexIngredient.utx",
  "..\\Textures\\1-1_TBilisi_tex.utx",
  "..\\Textures\\1_3_CaspianOilRefinery_TEX.utx",
  "..\\StaticMeshes\\EMeshSFX.usx",
  "..\\StaticMeshes\\EGO_OBJ.usx",
  "..\\Textures\\ETexCharacter.utx",
  "..\\Textures\\4_3_Chinese_Embassy_tex.utx",
  "..\\Textures\\4_3_0_Chinese_Embassy_tex.utx",
  "..\\Textures\\4_3_2_Chinese_Embassy_tex.utx",
...

This is a 1:1 mapping of the file name which triggered package load and can be used for reconstructing the filesystem layout.

[EliotVU]

sorry for the lazy question, but what changes in particular did you think would be useful from the next branch?

Generally it easier to follow through the serialization code, which would be useful for your 1:1 implementation.

Additionally, if one were to attempt to implement this format in UELib, the 'Next' branch refactoring of the IUnrealStream implementations attemps to ease the difficulty of processing the underlying data, such as decompressing etc.

1. LoadStream should use the underlying buffer instead of a MemoryStream in UObject.LoadStream since the data is not guaranteed to be contiguous.

Oh I see, so basically a single object's serialized format can be spread sporadically across the package stream? In that case, just directly instructing Deserialize(IUnrealSteam) with the package stream should do the trick.

2. CreateObject on imports should trigger deserializing the package header for imports whose packages have not yet been loaded. CreateObject's event could maybe be hijacked for this purpose?

Yes, done with the new package linking code UnrealPackageLinker.cs (which is also a prerequisite to make this format work)

a.t.m this is disabled, because it results in a stackoverflow on some packages such as UT99, but works fine on UT2004.

And furthermore, I'll also publish the code for .UMD (Unreal package module) support to the 'Next' branch.

[landaire]

Oh I see, so basically a single object's serialized format can be spread sporadically across the package stream? In that case, just directly instructing Deserialize(IUnrealSteam) with the package stream should do the trick.

Yeah so for instance when deserializing a field the engine deserializes its object index then attempts to load the object. The load will cause a seek + read but since the stream doesn't seek you end up a byte sequence starting with the object A's data, the field's object (object B) index, then object B's data IF it hasn't been loaded yet.

Sounds good though. I'll take a look at it this evening and see if I can port some of my stuff over.

[VendorX]

The Common packabe isn't a problem, in most of the cases it contain full / empty files with header only. To benefit from export offsets, it must be reconstructed. Different story is with LevelName.lin.

TIP: SCCT and SCDA are different (*.ulnc / *.hlnc), which makes it very easy to rebuild the original packet structure. However, there are many 'holes' because all packets were stripped of unused game components after they were shipped.

[landaire]

The Common packabe isn't a problem, in most of the cases it contain full / empty files with header only. To benefit from export offsets, it must be reconstructed. Different story is with LevelName.lin.

I'm not quite sure what you mean. I've only looked at SC1 so that's all I can speak to, but the engine has a list of things that it deterministically loads before loading the MyLevel object. All of these items are placed in common.lin.

Once all of these items are loaded, the engine loads MyLevel. This is what triggers loads from LevelName.lin and its dependencies. AFAIK any dependencies from packages whose headers are in common.lin that have not been loaded, including the "empty files with header only", are loaded from LevelName.lin if the level takes a dependency on that item.

For example, in SC1 the header for 0_0_Training_tex.utx is in common.lin but much of its data is in LevelName.lin. Similarly, Engine.u's header is the first thing in the file but none of the export data follows the header. Core.u immediately follows the header.

This is because the engine loads Engine.GameEngine which causes Engine.u's linker to be constructed, GameEngine's export to be resolved/parsed, which triggers a load of its dependencies first. The super class hierarchy eventually leads to loading data from Core.u, so the data layout is:

[ Lin Header ]
[ Lin File Table ]
[ Engine.u Header ]
[ Core.u Header ]
[ Core.u Dependencies for GameEngine ]
[ Engine.u Dependencies for GameEngine ]
[ GameEngine ]

[VendorX]

The problem is that CreateExport only creates an empty object, which will later (it will be placed on the stack in GObjectLoaded) be loaded by PostLoad. However, there are many factors that can trigger periodically its execution.

[landaire]

In SC1 as far as I can tell there are no lazy-loaded objects in scripts which actually trigger a Preload() at runtime. I did see this in the scripts, so it may be possible but it must be deterministic -- i.e. a completely playthrough of the game with load-order logging should suffice.

[VendorX]

This is a dead end ... and has nothing to do with Preload. Check the EndLoad which is responsible for calling PreLoad.

[landaire]

Check the EndLoad which is responsible for calling PostLoad.

I understand. My tooling handles this just fine.

[EliotVU]

Moving this to discussions. Looking forward to seeing how this progresses.

[ShadowLuigi]

late to responding to this here, but I did see progress awhile back on .lin in the case of the original Splinter Cell on OG Xbox. Really promising stuff, here's to more support being added for other Ubisoft UE2 titles that use stuff like .lin (even .umd too).