Strz type support for UTF-16 and UTF-32

[dreckard]

This issue is very similar to #13 and there is a lot of relevant discussion there.

Observed

• If strz is used with UTF-16 or UTF-32 then a single null byte is enough to result in termination rather than 2 (U16) or 4 (U32) bytes.

Expected

• If the encoding is given as UTF-16 or UTF-32 then the strz parse only terminates when the corresponding number of consecutive null bytes appear.

To describe the use case, I am writing a descriptor for the output of an internal Windows tool which reserves a fixed length for the string then null terminates it. While this practice is a bit inefficient and I can't point to any widely used formats that do the same I suspect that it is not uncommon for Windows programs since it is analogous to doing so with UTF-8 in a cross-platform or Unix scenario.

On Windows, an example C struct might look like this:

struct TextBlob
{
	UCHAR DataPrefix[n];
	WCHAR WideString[64];
	UCHAR DataSuffix[n];
};

For an example data blob and ksy file that that minimally reproduce the issue (at least with the web IDE) please see the following zip:
utf16_test.zip

[GreyCat]

Ok, to collect all the arguments that were mentioned in previous discussions on this topic in one place:

• Implementing "read until a combination of multiple bytes is encountered" is non-trivial. For example, none of our supported languages have such a method in stdlib (but note almost everyone includes something like "read until a byte is encountered").
• Actually, "read until a sequence of 00 00 is encountered" is plain wrong for this case. Namely, "01 00 00 02 00 00" should be read as two UTF-16LE chars "\u0001\u0200", not as just "\u0001". I.e. "00 00" much appear as whole character, 2-byte aligned.
• It's totally possible (although not really usual) to get this kind of problem outside of C + Windows world. Although majority of applications don't seem to use strings of zero-terminated wide chars family of functions, stuff like wcslen, wcscat, etc (akin to much more popular strlen, strcat, etc) technically exists in C since C99 standard.
• No popular (and publically available) format have been found using this so far.
• Looks like this issue is only relevant to UTF-16 representation of strings, and probably 99.9% of the time it is used on actually a fixed string to trim remaining garbage, i.e. it should be solved around bytes_terminate function, but probably applied in somewhat different manner.

Current archetypical application generates something like that:

foo = bytes_to_str(
    bytes_terminate(
        bytes_strip_right(
            io.read_bytes(20),
            43 // padding byte
        ),
        64, // terminator byte
        false
    ),
    "UTF-8"
);

Obviously, applying a function like "bytes_terminate" which operates on strings (not just byte arrays) requires us to convert byte array to string first with "bytes_to_str", i.e. executing something like that:

foo = str_terminate(
    bytes_to_str(
        io.read_bytes(20),
    ),
    0x0000, // terminator char
);

The big catch is that actually trailing garbage might have something that will be invalid in chosen encoding. Unfortunately, contrary to popular opinion, this is true even for UTF16. For example, if we're working with C++ or PHP (and iconv-based implementation, which converts everything that should be treated as string internally to UTF-8), this string will trigger an error on conversion:

61 00|00 00|00 D8 61 00

Although we would expect result a (as 0x61 is ASCII code for "a", and then string terminates with 00 00), it will trigger something like InvalidByteSequenceError. This is because 00 D8 61 00 is not a valid UTF16 character: 00 D8 is a lead of surrogate pair, and it must be followed by tail of surrogate pair, and 61 00 is illegal here.

[sirg3]

No popular (and publically available) format have been found using this so far.

Windows version info resources, found in executables and .res files, use them.

[GreyCat]

VS_VERSIONINFO per se has no variable-length strings. However, it includes StringFileInfo → StringTable → String, which actually includes them.

What's even more peculiar, actually, it seems that there are literally double-null strings to store two-level lists: https://devblogs.microsoft.com/oldnewthing/20091008-00/?p=16443 — I believe they effectively become quad-null terminated strings when laid out in UTF-16. Can anyone confirm/deny that?

[dreckard]

Good clarification on the byte alignment requirement. I believe that is correct regarding the quad-null termination for WCHAR string lists. The only other documentation I have seen is in some of the APIs that return data in this style such as GetLogicalDriveStrings, but I don't see any other way it could be interpreted.

The Windows KUSER_SHARED_DATA struct's NtSystemRoot is another example of a null terminated UTF-16 (single) string. The struct is fairly commonly parsed in memory dump analysis at least.

typedef struct _KUSER_SHARED_DATA
{
     ULONG TickCountLowDeprecated;
     ULONG TickCountMultiplier;
     KSYSTEM_TIME InterruptTime;
     KSYSTEM_TIME SystemTime;
     KSYSTEM_TIME TimeZoneBias;
     WORD ImageNumberLow;
     WORD ImageNumberHigh;
     WCHAR NtSystemRoot[260];
     ULONG MaxStackTraceDepth;
     ...
}

http://www.geoffchappell.com/studies/windows/km/ntoskrnl/structs/kuser_shared_data.htm

[GreyCat]

I've implemented simple Windows resource parser as an excercise: https://github.com/kaitai-io/windows_resource_file.ksy/blob/master/windows_resource_file.ksy — now it uses a hack to parse strings (especially because there's an extra twist there — same byte space is used to designate numeric and string IDs).

While doing so, I've noticed that there are at least 2 very distinct cases we're talking here:

1. Pure "read until double 00 terminator, convert to string" — encountered at least in NAME and TYPE fields of
2. "Read fixed number of bytes, then trim it using double 00 terminator logic, then convert to string"

That means my original proposal is wrong. We indeed need both (1) and (2) implemented, not only (2).

[arekbulski]

Construct has both (fixed-length string with filler, and c-string). Admittedly it took me 2 years to get it implemented. I have never seen a protocol that actually used the first either, and I cant even imagine why would anyone design such a protocol in the first place, but it was requested on Construct forum more than once, so I guess someone out there actually needs it, so here we are.

@GreyCat If you give me a go, I will add 2 methods to Python runtime to effectuate this, but you would need to update the compiler (translator). I could update C# then too. Restriction is, these 2 methods need to know what encoding it is, or rather what is the unit size (2 for UTF16, 4 for UTF32, 1 for UTF8).

[GreyCat]

Let's start with inventing some ksy syntax that covers all the cases discussed in this ticket.

[arekbulski]

Fixed string: "type: str, size: N, terminator: 0, encoding: utf16, [unitsize: T=2]" (EDIT, added terminator)

Reads N bytes, then successively strips last T bytes if they are null, down to empty string. If encoding is recognizable like UTF*, unitsize can be inferred. N must be multiple of T.

CString: "type: str, terminator: 0, encoding: utf16, [unitsize: T=2]"
CString: "type: strz, encoding: utf16, [unitsize: T=2]"

Reads T bytes at a time, until that chunk is all null bytes. If first chunk is nulls, its an empty string. If encoding is recognizable like UTF*, unitsize can be inferred. Terminator other than 0 should be compile error, because at least UTF encodings support only one way of terminating it.

By recognizable encodings I mean those:

construct.possiblestringencodings = {'U16': 2, 'utf_8': 1, 'utf32': 4, 'utf_32_le': 4, 'utf8': 1, 'utf_32_be': 4, 'utf_32': 4, 'utf_16_be': 2, 'U32': 4, 'utf16': 2, 'ascii': 1, 'utf_16': 2, 'utf_16_le': 2, 'U8': 1}¶

[arekbulski]

There is also a problem when both size and terminator are used.

meta:
  id: test1
seq:
  - id: value
    type: str
    terminator: 0
    size: 10
    encoding: utf-8

Compiles into following. Problem is, bytes_terminate only supports single characters bytes.

(KaitaiStream.bytes_terminate(self._io.read_bytes(10), 0, False)).decode(u"utf-8")

Extract from the runtime:

    def bytes_terminate(data, term, include_term):
        new_len = 0
        max_len = len(data)
        while new_len < max_len and data[new_len] != term:  #<--- indexing not slicing
            new_len += 1   #<--- non variable
        if include_term and new_len < max_len:
            new_len += 1
        return data[:new_len]

[GreyCat]

bytes_terminate, as its name suggest does not support any characters at all, only bytes. What problem do you see here?

[arekbulski]

To support UTF16/32, bytes_terminate would need to slice data[newlen:newlen+unit] and then increment like newlen += unit. In other words, current implementation would not support UTF16/32. Thats what this issue is about. And by characters I meant single bytes, sorry.

[GreyCat]

It doesn't, that's true. My main concern here is that technically we should not deal with bytes at all: if we're dealing with encodings like UTF16, for example, in C++, that would call for char16_t type instead of uint8_t and relevant reinterpret cast.

If we'll stick with bytes-centric implementation, however, from runtime's point of view, we can probably cover all possible cases by specifying something like byte_terminate_multi, something like that:

byte[] bytesTerminateMulti(byte[] bytes, byte[] term, int unitSize, boolean includeTerm)

and the same thing about bytes_strip_right_multi:

public static byte[] bytesStripRight(byte[] bytes, int unitSize, byte[] padBytes) {

[arekbulski]

Good idea, it would be better to have a separate (multi) method instead of generalizing the existing (single) method, because multi will have less performance than single.

Would unitsize parameter be actually needed? I think its just len(term) and len(padbytes).