5
\$\begingroup\$

Given a UTF-16 string, test its endianness.

Rules:

  1. As long as the input is in UTF-16 without BOM, its type doesn't matter. In C++ on Windows, it can be std::wstring or std::u16string. In Haskell, it can be [Int16] or [Word16].

  2. The endianness is tested by noncharacters. If the input contains a noncharacter, it is in wrong endianness.

  3. If the original version and the endianness-swapped version both or neither contain a noncharacter, the test is inconclusive.

  4. The type of the output must be well-ordered. Output 1 (or an equivalent enumerator) when the input is in right endianness, or -1 (or an equivalent enumerator) when the input must be endianness-swapped, or 0 (or an equivalent enumerator) when the test is inconclusive. For example, in Haskell, Ordering is a valid output type.

  5. Wrong UTF-16 sequences are also treated as noncharacters. (So the noncharacters are: Encodings of code point from U+FDD0 to U+FDEF, encodings of code point U+XXFFFE and U+XXFFFF with XX from 00 to 10, and unpaired surrogates.)

  6. As this is a code golf, the shortest code in bytes wins.

Examples:

Assume we're in Haskell, the system is a big-endian, and Ordering is the output type. When given the following byte sequence:

00 00 DB FF DF FE

Because it encodes the noncharacter U+10FFFE, the output must be:

LT

For the following byte sequence:

00 00 00 00 00 00

The output must be:

EQ

For the following byte sequence:

FE FF

Since the endianness-swapped version encodes the noncharacter U+FFFE, the output must be:

GT
\$\endgroup\$
6
  • \$\begingroup\$ @JoKing We output 0 when the test is inconclusive (see Rule #3). A non-UTF character is treated as a noncharacter also in the flipped version (see Rule #5). \$\endgroup\$ Oct 2, 2019 at 1:03
  • 4
    \$\begingroup\$ Some more test cases would be good \$\endgroup\$
    – Jo King
    Oct 2, 2019 at 1:14
  • 3
    \$\begingroup\$ You should include a description of noncharacters and invalid UTF-16 sequences in your challenge, or at least point to the specification. \$\endgroup\$
    – nwellnhof
    Oct 2, 2019 at 14:59
  • 1
    \$\begingroup\$ @nwellnhof I improved the question accordingly. Now vote for reopen, please? \$\endgroup\$ Oct 2, 2019 at 23:52
  • \$\begingroup\$ How does 00 00 DB FF DF FE encode U+10FFFE? I don't see 10 FF FE. \$\endgroup\$
    – GirkovArpa
    Jul 20, 2020 at 18:24

1 Answer 1

5
+50
\$\begingroup\$

ARM Thumb-2, 108 90 84 bytes

Machine code:

b5f2 2300 f000 f822 9900 000a 3a02 5a84
ba64 5284 d1fa 425b f000 f818 bdf2 5a44
f64f 56d0 1ba7 2f20 d313 0ae7 2f1b d10a
b179 3902 0ae7 d30c 5a42 0a97 2f36 d108
3209 eb04 2482 b227 3702 d202 3902 d5e6
3b01 4770

Commented assembly:

        .syntax unified
        .arch armv6t2
        .text
        .thumb
        .globl check_utf16
        .thumb_func
        // r0: string, r1: len in BYTES
        // The string will be clobbered as an internal buffer.
        // Returns in r3.
check_utf16:
        push    {r1, r4, r7, lr}
        // Set starting return value to 0. This will accumulate both results.
        movs    r3, #0
        // First, check little endian.
        // Yes, I did bl to the middle of a function. :P
        bl      .Ltest.entry
        // Reload the length, as test clobbered it.
        ldr     r1, [sp]
        // Byteswap the string.
        movs    r2, r1
.Lbswap_loop:
        // Looping backwards...
        subs    r2, #2
        // Load a halfword to r4,
        ldrh    r4, [r0, r2]
        // do a 16-bit byteswap,
        rev16   r4, r4
        // and store it back.
        strh    r4, [r0, r2]
        bne     .Lbswap_loop
.Lbswap_loop.end:
        // Negate r3 to make the start return value from native endianness positive.
        // Then, we subtract the big endian version from this to get the -1/0/1 result.
        negs    r3, r3
        // and call test again to check big endian
        bl      .Ltest.entry
        pop     {r1, r4, r7, pc}

.Ltest_loop:
        // Read the next character
        ldrh    r4, [r0, r1]
        // Check for FDD0-FDEF.
        // First we subtract 0xFDD0...
        movw    r2, #0xFDD0
        subs    r7, r4, r2
        // ...and if it is (unsigned) less than 0x20, it is
        // bad. Return false.
        cmp     r7, #0x20
        blo     .Lfalse

        // Is it a surrogate?
        // Equivalent to (r4 & 0xF800) != 0xD800
        lsrs    r7, r4, #11
        cmp     r7, #0xD800 >> 11
        bne     .Lnot_surrogate

        // NOTE: We are looping backwards, that is why we check
        // trail surrogates first.
.Lis_surrogate:
        // Beginning of string == unpaired surrogate == bad
        cbz     r1, .Lfalse
        // Decrement r1
        subs    r1, #2

        // Is it a trail surrogate? We already know it is
        // a surrogate, so we only check the trail bit.
        // Uses lsrs's carry flag to test the 10th bit.
        // Equivalent to (r4 & 0x400) == 0
        lsrs    r7, r4, #11
        bcc     .Lfalse

        // Load the preceeding (hopefully) lead surrogate to r2.
        ldrh    r2, [r0, r1]
        // Is it a lead surrogate?
        // Equivalent to (r2 & 0xFC00) != 0xD800
        lsrs    r7, r2, #10
        cmp     r7, #0xD800 >> 10
        bne     .Lfalse

        // We have two surrogates, let's merge them into a
        // full codepoint.
        //
        // Just kidding. We only need the low 16 bits, so we can take
        // a huge shortcut and let sxth correct any overflow.
        //
        // utfcpp showed us that converting a UTF-16 pair to UTF-32
        // is simply this:
        //     0xfca02400 + trail + (lead << 10)
        // where 0xfca02400 is the constant fold of this:
        //     0x10000 - (LEAD_SURROGATE_MIN << 10) - TRAIL_SURROGATE_MIN
        //
        // Since we are only using 16 bits, we can just add 0x2400
        // instead. That saves 4 bytes, as we can do a wide add.
        //
        // HOWEVER, we can do even better: 0x2400 has the low 10 bits
        // clear, and since we need to shift the lead surrogate 10
        // bits to the left, we can just add 0x2400 >> 10 (or 0x09)
        // to the lead surrogate, then do trail + (lead << 10).
        //
        // This means that instead of generating a 32-bit constant
        // into a register, we can use the immediate narrow form of
        // adds, saving 6 bytes (4 for literal, 2 for ldr).
        adds    r2, #0x2400 >> 10
        add.w   r4, r4, r2, lsl #10
.Lnot_surrogate:
        // At this point, r4 contains the low 16 bits of the
        // codepoint, and the upper bits are garbage.

        // Check for xxFFFE/F by sign extending and adding 2.
        // If it was, there will be a carry.
        // The act of sign extending eliminates all of those
        // garbage bits for us, allowing laziness in the surrogate
        // code.
        sxth    r7, r4
        adds    r7, #2
        bcs     .Lfalse

        .thumb_func
        // We actually bl here, so we can subtract first
        // on the first iteration.
        // The possibilities of assembly are endless.
.Ltest.entry:
        // Loop while we still have data.
        subs    r1, #2
        bpl     .Ltest_loop
.Ltrue:
        // Subtract 1 for true. This is negated for native endianness, and it
        // cancels out on both true.
        subs    r3, #1
.Lfalse:
        // return
        bx      lr

Test suite:

        .syntax unified
        .arch armv6t2
        .thumb
        // W+X because PIE sucks.
        .section ".writeable_text","awx",%progbits

.macro $TEST expected:req, argc:req, argv:vararg
        // Load string buffer into r0
        adr     r0, 1f
        // Convert element count to size in bytes by doubling.
        movs    r1, #\argc * 2
        // Skip over our constant pool
        b       3f
1:
        // The UTF-16 string 
        .short \argv
        .align 2
2:
        // blatant abuse of macro stringification to avoid a printf loop :P
        .asciz "\argv"
        .align 2
3:
        // Call check_utf16
        bl      check_utf16
        // Stringified version of the UTF-16 string
        adr     r1, 2b
        // Expected
        movs    r2, #\expected
        // r3 is already in place
        adr     r0, .Lprintf_str
        // printf("{ %s } -> expected: %d, got: %d\n", STR(arr), expected, retval)
        bl      printf
.endm

        .globl main
        .thumb_func
main:
        push    {r4, lr}
        // Original test cases
        $TEST   -1, 3, 0x0000, 0xDBFF, 0xDFFE
        $TEST    0, 3, 0x0000, 0x0000, 0x0000
        $TEST    1, 1, 0xFEFF
        
        // I've added more test cases, feel free to take them
        // 1: D3FD becomes FDD3 when swapped, which is bad
        $TEST    1, 3, 0xD3FD, 0xD83D, 0xDE0F
        // 0: proper string with surrogates both ways
        $TEST    0, 3, 0x0A00, 0xD83D, 0xDE0F
        // -1: DF10 is a lone trail surrogate
        $TEST   -1, 1, 0xDF10
        // 1: D9E0 is a lone head surrogate
        $TEST    1, 1, 0xE0D9
        // 0: 0xffff is invalid in both endiannesses
        $TEST    0, 2, 0x0314, 0xFFFF
        pop     {r4, pc}
.Lprintf_str:
        .asciz "{ %s } -> expected: %d, got: %d\n"

Try it online! (sorta)

Has the following pseudo-signature:

int check_utf16(uint16_t *ptr, size_t length_in_bytes);

However, it is NOT C-callable, it returns in r3 instead of r0.

Returns -1 if we need an endian swap, 0 if ambiguous, or 1 if we don't need an endian swap.

lsrs is the real MVP here. (☞^o^) ☞

Specifically, lsrs/lsls can do most usages of ands without setting up a constant or using a wide instruction. All of the "masking" operations can just be done by shifting right. This also lets us use a narrow cmp, as narrow cmp can only check 0-255.

Additionally, I do a really dirty trick here: I only calculate the low 16 bits of a surrogate pair codepoint.

The optimized UTF-16 to UTF-32 conversion algorithm is this (magic number explained in comments):

uint32_t codepoint = 0xfca02400 + trail + (lead << 10);

However, 0xfca02400 is a 6 byte constant, 2 bytes for ldr and 4 bytes for the literal pool.

One thing to note is that I immediately discard the upper 16 bits of the codepoint by sign extending. Therefore, we only need to add the low 16 bits of the magic number, 0x2400.

int16_t codepoint = 0x2400 + trail + (lead << 10);

This is much better, as we can do an immediate add.w instruction, saving 4 bytes.

However, 0x2400 has 10 trailing zero bits: it is simply 9 << 10.

Therefore, we can do another optimization with the distributive property:

int16_t codepoint = trail + ((lead + (0x2400 >> 10)) << 10);
// int16_t codepoint = trail + ((lead + 9) << 10);

That is even better: we no longer need add.w, 9 fits perfectly into an immediate narrow adds, saving a total of 6 bytes!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.