14
\$\begingroup\$

I'm writing a validator function that receives a byte[] and checks whether it represents a valid UTF-8 byte sequence, according to this table.

Is my approach correct? So far it has worked fine with my tests, but I'm worried that I might be missing some edge case, or that the way I'm handling bytes is off.

And more importantly, how can I improve the conditions using bit-twiddling? I'm a bit rusty here, and I think that a comparison such as this:

if ((b & 0xFF) >> 1 == (byte) 0b1111110)

can be expressed in a simpler, more idiomatic way.

public static boolean validate(byte[] bytes) {

    int length = bytes.length;

    if (length < 1 || length > 6)
        return false;

    byte b = bytes[0];

    if (length == 1)
        return (b & (1 << 7)) == 0;

    int n;

    if ((b & 0xFF) >> 1 == (byte) 0b1111110)
        n = 5;
    else if ((b & 0xFF) >> 2 == (byte) 0b111110)
        n = 4;
    else if ((b & 0xFF) >> 3 == (byte) 0b11110)
        n = 3;
    else if ((b & 0xFF) >> 4 == (byte) 0b1110)
        n = 2;
    else if ((b & 0xFF) >> 5 == (byte) 0b110)
        n = 1;
    else
        return false;

    if (length-1 != n)
        return false;

    for (int i = 1; i < length; i++)
        if ((bytes[i] & 0xFF) >> 6 != (byte) 0b10)
            return false;

    return true;

}

And these are some tests to try it out:

byte[] bytes1 = {(byte) 0b11001111, (byte) 0b10111111};
System.out.println(validate(bytes1)); // true

byte[] bytes2 = {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b10111111};
System.out.println(validate(bytes2)); // true

byte[] bytes3 = {(byte) 0b10001111, (byte) 0b10111111};
System.out.println(validate(bytes3)); // false

byte[] bytes4 = {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b00111111};
System.out.println(validate(bytes4)); // false
\$\endgroup\$
4
  • \$\begingroup\$ Perhaps you already know it, but you're reinventing the wheel. Java NIO already has this capability. You could go look at NIO's code to see how Oracle did it: java.nio.charset.CharsetDecoder \$\endgroup\$ Oct 2, 2015 at 14:50
  • \$\begingroup\$ @james.garriss this was a programming exercise, not production code... but actually, I didn't know about that functionality in CharsetDecoder, so thanks for the heads-up :) \$\endgroup\$ Oct 2, 2015 at 15:13
  • 1
    \$\begingroup\$ A wee bit of sample code to get you going: CoderResult result = StandardCharsets.UTF_8.newDecoder().onMalformedInput(CodingErrorAction.REPORT).onUnmappableCharacter(CodingErrorAction.REPORT).decode(ByteBuffer.wrap(bytesToTest), CharBuffer.allocate(1024), true); \$\endgroup\$ Oct 2, 2015 at 17:12
  • \$\begingroup\$ Lengths of UTF-8 sequences beyond 4 are illegal in Unicode. No need to check after that. \$\endgroup\$ Aug 25, 2017 at 15:54

2 Answers 2

14
\$\begingroup\$

Logic

Never omit the optional braces like that. Think of yourself as a contributing factor to a future coding accident. If you really want to omit braces, then put the statement on the same line, so that there is no possibility of misinterpretation.

The function does not check for overlong encodings, invalid byte sequences, or invalid code points. Those caveats should be declared in JavaDoc.

I would eliminate the length > 6 check, as 6 is a magic number. You don't need that special case anyway.

I would also incorporate the length == 1 special case into the regular logic.

In general, text is more likely to contain shorter UTF-8 sequences than longer ones, so you might as well handle the shorter cases first to save a few CPU cycles.

Rather than setting n to be the number of trailing bytes, set it to be the expected length of the array. I'd rename nexpectedLen to be more descriptive. That makes the code more readable (and saves one pointless subtraction).

Eliminate the bit-shifting. Just AND with the bitmask to specify which bits you are interested in inspecting.

public static boolean validate(byte[] bytes) {
    int expectedLen;
    if      (bytes.length == 0)                     return false;
    else if ((bytes[0] & 0b10000000) == 0b00000000) expectedLen = 1;
    else if ((bytes[0] & 0b11100000) == 0b11000000) expectedLen = 2;
    else if ((bytes[0] & 0b11110000) == 0b11100000) expectedLen = 3;
    else if ((bytes[0] & 0b11111000) == 0b11110000) expectedLen = 4;
    else if ((bytes[0] & 0b11111100) == 0b11111000) expectedLen = 5;
    else if ((bytes[0] & 0b11111110) == 0b11111100) expectedLen = 6;
    else    return false;

    if (expectedLen != bytes.length) return false;

    for (int i = 1; i < bytes.length; i++) {
        if ((bytes[i] & 0b11000000) != 0b10000000) {
            return false;
        }
    }

    return true;
}

Interface design

It's rarely useful to validate a single character: usually, you'll want to validate a whole string. You should name your function to avoid giving the impression that it checks for multi-character strings.

In Java, functions that perform a test and return a boolean are conventionally named isSomething() or hasSomething(). A function named validate() suggests that it performs an action as a side-effect, perhaps throwing an exception on failure.

Therefore, I'd rename your function to isValidChar(byte[] bytes).

So, what if I need to validate a string? I'd have to somehow chunk it up into right-sized byte arrays first. That's not really possible without examining the string using similar logic to what is in the function itself. Even then, it would be wasteful to construct a byte array just for the function call. Therefore, I think that it would be more useful to provide a function that validates a string. To go further, you could make such a function return something more informative than just a boolean.

/**
 * Returns the number of UTF-8 characters, or -1 if the array
 * does not contain a valid UTF-8 string.  Overlong encodings,
 * null characters, invalid Unicode values, and surrogates are
 * accepted.
 */
public static int charLength(byte[] bytes) {
    int charCount = 0, expectedLen;

    for (int i = 0; i < bytes.length; i++) {
        charCount++;
        // Lead byte analysis
        if      ((bytes[i] & 0b10000000) == 0b00000000) continue;
        else if ((bytes[i] & 0b11100000) == 0b11000000) expectedLen = 2;
        else if ((bytes[i] & 0b11110000) == 0b11100000) expectedLen = 3;
        else if ((bytes[i] & 0b11111000) == 0b11110000) expectedLen = 4;
        else if ((bytes[i] & 0b11111100) == 0b11111000) expectedLen = 5;
        else if ((bytes[i] & 0b11111110) == 0b11111100) expectedLen = 6;
        else    return -1;

        // Count trailing bytes
        while (--expectedLen > 0) {
            if (++i >= bytes.length) {
                return -1;
            }
            if ((bytes[i] & 0b11000000) != 0b10000000) {
                return -1;
            }
        }
    }
    return charCount;
}

That's a more versatile function, for about the same amount of code.

\$\endgroup\$
1
  • \$\begingroup\$ Lengths of UTF-8 sequences beyond 4 are illegal in Unicode. No need to check after that. \$\endgroup\$ Aug 25, 2017 at 15:52
4
\$\begingroup\$

this is in addition to 200_success's answer,

Better Test Cases

byte[] bytes1 = {(byte) 0b11001111, (byte) 0b10111111};
System.out.println(validate(bytes1)); // true

byte[] bytes2 = {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b10111111};
System.out.println(validate(bytes2)); // true

You are using simple print statements for testing, instead you can use mature Unit Testing Framework such as JUnit. JUnit can simplify the the process of unit testing greatly. And also instead of simply commenting the expected results you can test against them.

Writing unit test code is labor-intensive, hence it is often not done as an integral part of programming. However, unit testing is a practical approach to increasing the correctness and quality of software; for example, the Extreme Programming approach relies on frequent unit testing [1].

Additionally I sense that you are repeating yourself in the test cases. Therefore making it harder for you to add new unit tests later [2].

In software engineering, don't repeat yourself (DRY) is a principle of software development, aimed at reducing repetition of information of all kinds [3].

You can also consider adding string based unit tests as well.

private static final String[] stringTests = {
    "A",
    "Z",
    "Because I'm Batman"
};

You can use an array to store all your strings and then loop through it.

private static final Charset UTF8_CHARSET = Charset.forName("UTF-8");

using a constant UTF8_CHARSET (thanks Vogel612).

private static final byte[][] byteTests = {
    {(byte) 0b11001111, (byte) 0b10111111},
    {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b10111111},
    {(byte) 0b10001111, (byte) 0b10111111},
    {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b00111111}
};

private static final boolean[] byteTestsExpectedResults = {
    true,
    true,
    false,
    false
};

You can store the expected results and byte arrays in arrays, which you can easily loop and access the values.

Eventually I created this unit test

import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import org.junit.Assert;
import org.junit.Test;

/**
 * Test ValidateUtf8
 */
public class ValidateUtf8Test {

    //for byte based tests
    private static final byte[][] byteTests = {
        {(byte) 0b11001111, (byte) 0b10111111},
        {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b10111111},
        {(byte) 0b10001111, (byte) 0b10111111},
        {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b00111111}
    };

    private static final boolean[] byteTestsExpectedResults = {
        true,
        true,
        false,
        false
    };

    //for string based tests       
    private static final Charset UTF8_CHARSET = Charset.forName("UTF-8");

    private static final String[] stringTests = {
        "A",
        "Z",
        "Because I'm Batman"
    };

    @Test
    public void testValidate() {
        for (int i = 0; i < byteTests.length; i++) {
            Assert.assertEquals(String.format("validate(byteTests[%d])", i),
                    ValidateUtf8.validate(byteTests[i]),
                    byteTestsExpectedResults[i]);
        }
    }

    @Test
    public void testValidateFromString() throws UnsupportedEncodingException {

        for (String toTest : stringTests) {
            Assert.assertTrue(String.format("validate('%s')", toTest),
                    ValidateUtf8.validate(
                            toTest.getBytes(UTF8_CHARSET)));
        }

    }

    @Test
    public void testCharLengthFromString() throws UnsupportedEncodingException {
        for (String toTest : stringTests) {
            Assert.assertEquals(String.format("charLength('%s')", toTest),
                    ValidateUtf8.charLength(toTest.getBytes(UTF8_CHARSET)),
                    toTest.length());
        }
    }

}

I decided to write a validate() method based on the charLength() method by 200_success.

public static boolean validate(byte[] bytes) {
    return (charLength(bytes) != -1);
}

and finally ValidateUtf8 class

public class ValidateUtf8 {

    /**
     * Returns the number of UTF-8 characters, or -1 if the array does not
     * contain a valid UTF-8 string. Overlong encodings, null characters,
     * invalid Unicode values, and surrogates are accepted.
     *
     * @param bytes byte array to check length
     * @return length
     */
    public static int charLength(byte[] bytes) {
        int charCount = 0, expectedLen;

        for (int i = 0; i < bytes.length; i++) {
            charCount++;
            // Lead byte analysis
            if ((bytes[i] & 0b10000000) == 0b00000000) {
                continue;
            } else if ((bytes[i] & 0b11100000) == 0b11000000) {
                expectedLen = 2;
            } else if ((bytes[i] & 0b11110000) == 0b11100000) {
                expectedLen = 3;
            } else if ((bytes[i] & 0b11111000) == 0b11110000) {
                expectedLen = 4;
            } else if ((bytes[i] & 0b11111100) == 0b11111000) {
                expectedLen = 5;
            } else if ((bytes[i] & 0b11111110) == 0b11111100) {
                expectedLen = 6;
            } else {
                return -1;
            }

            // Count trailing bytes
            while (--expectedLen > 0) {
                if (++i >= bytes.length) {
                    return -1;
                }
                if ((bytes[i] & 0b11000000) != 0b10000000) {
                    return -1;
                }
            }
        }
        return charCount;
    }

    /**
     * Validate a UTF-8 byte array
     *
     * @param bytes byte array to validate
     * @return true if UTF-8
     */
    public static boolean validate(byte[] bytes) {
        return (charLength(bytes) != -1);
    }
}

After running test cases

testcases

All the test cases will pass


[1]Y. Cheon and G. Leavens, “A Simple and Practical Approach to Unit Testing: The JML and JUnit Way,” in ECOOP 2002 — Object-Oriented Programming, vol. 2374, B. Magnusson, Ed. Springer Berlin Heidelberg, 2002, pp. 231–255.

[2]“Match Simple Sentence or Partial Sentence.” [Online]. Available: Match Simple Sentence or Partial Sentence. [Accessed: 27-Aug-2014].

[3]“Don’t repeat yourself,” Wikipedia, the free encyclopedia. 24-Aug-2014.

\$\endgroup\$
1
  • \$\begingroup\$ Lengths of UTF-8 sequences beyond 4 are illegal in Unicode. No need to check after that. \$\endgroup\$ Aug 25, 2017 at 15:53

Your Answer

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

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