Update UTF-8 decoder to detect more special cases.

src/unicode.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 //
 // This file was generated at 2014-10-08 15:25:47.940335
 
 #include "src/unicode-inl.h"
 #include <stdio.h>
 #include <stdlib.h>
 
@@ skipping 172 matching lines @@
           return 0;
       }
       return -1;
     }
   } else {
     return 0;
   }
 }
 
 
-uchar Utf8::CalculateValue(const byte* str, size_t length, size_t* cursor) {
-  // We only get called for non-ASCII characters.
-  if (length == 1) {
+static inline size_t NonASCIISequenceLength(byte first) {
+  static const uint8_t lengths[256] = {
+      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+      2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+      4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

[vogelheim, 2015/05/21 16:58:38]

The table is difficult to read. It also leaves me rather confused.

- I take it the purpose is to determine the length of an UTF-8 sequence from
it's first byte.
  I'm seeing: 128 x 0, 96 x 2, 16 x 3, 5 x 4, 11 x 0.
  Shouldn't this be: 192 x 0, 32 x 2, 16 x 3, 8 x 4, 8 x 0 ?

- In particular:
  - I don't understand why you count the continuation characters (0b10xxxxxx) as
'2'.
  - I don't understand why you count some of the 4-byte prefixes as
    0/error (0b11110101 + 0b1111011x)

- I'd find an 16x16 layout probably more readable.

[jochen (gone - plz use gerrit), 2015/05/22 12:38:12]

I updated the matrix to be 16 x 16, and added comments
fixed
the code points those would encode are outside of the unicode range
done

+  return lengths[first];
+}
+
+
+uchar Utf8::CalculateValue(const byte* str, size_t max_length, size_t* cursor) {

[vogelheim, 2015/05/21 16:58:38]

This might also benefit from a unit test that will try some of the edge cases
this is meant to fix.

[vogelheim, 2015/05/21 16:58:38]

I believe this deserves some commentary, and if only that it's meant to be
consistent with Blink's UTF decoder.

[jochen (gone - plz use gerrit), 2015/05/22 12:38:12]

yeah, actually, it's supposed to be consistent with the definition of UTF-8
which the previous version was not :-/

there are tests, and they fail now. I'll update them

+  DCHECK((str[0] & 0x80) == 0x80);
+  size_t length = NonASCIISequenceLength(str[0]);
+  if (length == 0 || max_length < length) {
     *cursor += 1;
     return kBadChar;
   }
-  byte first = str[0];
-  byte second = str[1] ^ 0x80;
-  if (second & 0xC0) {
-    *cursor += 1;
-    return kBadChar;
-  }
-  if (first < 0xE0) {
-    if (first < 0xC0) {
+  if (length == 2) {

[vogelheim, 2015/05/21 16:58:38]

I was trying to figure out *why* these characters are restricted. It seems
ECMAScript specs explicitly allow pretty much all of them. 

"All Unicode code point values from U+0000 to U+10FFFF, including surrogate code
points, may occur in source text where permitted by the ECMAScript grammars."
[From an ES6 draft. ES5 final has similar text.]

[vogelheim, 2015/05/21 16:58:38]

I find the code below to be somewhat confusing. If I get this correctly, the
code below either does the default UTF-8 processing, or for some 'special' code
point ranges it does additional checks.

Maybe an alternative would be to fold the dispatching of all those 'special'
checks into the length matrix above.

I.e., for the code block starting with 0xE0, make lengths[0xE0] == 0xE0, etc.
Then these blocks below would all look like this:

switch (NonASCIISequenceLength[str[0]) {
  case 0: ... error:
  case 2..4: normal UTF-8 processing
  case 0xE0: extra check, then UTF-8 processing.
  ....
  default: UNREACHABLE();
}

[jochen (gone - plz use gerrit), 2015/05/22 12:38:12]

right. It's just that UTF-8 cannot encode all of unicode, in particular not
U+D800 through U+DFFF.

+    DCHECK(str[0] <= 0xDF);
+    if (str[0] < 0xC2) {
       *cursor += 1;
       return kBadChar;
     }
-    uchar code_point = ((first << 6) | second) & kMaxTwoByteChar;
-    if (code_point <= kMaxOneByteChar) {
+    if (str[1] < 0x80 || str[1] > 0xBF) {
       *cursor += 1;
       return kBadChar;
     }
     *cursor += 2;
-    return code_point;
+    return ((str[0] << 6) + str[1]) - 0x00003080;
   }
-  if (length == 2) {
-    *cursor += 1;
-    return kBadChar;
-  }
-  byte third = str[2] ^ 0x80;
-  if (third & 0xC0) {
-    *cursor += 1;
-    return kBadChar;
-  }
-  if (first < 0xF0) {
-    uchar code_point = ((((first << 6) | second) << 6) | third)
-        & kMaxThreeByteChar;
-    if (code_point <= kMaxTwoByteChar) {
+  if (length == 3) {
+    DCHECK(str[0] >= 0xE0 && str[0] <= 0xEF);
+    switch (str[0]) {
+      case 0xE0:
+        if (str[1] < 0xA0 || str[1] > 0xBF) {
+          *cursor += 1;
+          return kBadChar;
+        }
+        break;
+      case 0xED:
+        if (str[1] < 0x80 || str[1] > 0x9F) {
+          *cursor += 1;
+          return kBadChar;
+        }
+        break;
+      default:
+        if (str[1] < 0x80 || str[1] > 0xBF) {
+          *cursor += 1;
+          return kBadChar;
+        }
+    }
+    if (str[2] < 0x80 || str[2] > 0xBF) {
       *cursor += 1;
       return kBadChar;
     }
     *cursor += 3;
-    return code_point;
+    return ((str[0] << 12) + (str[1] << 6) + str[2]) - 0x000E2080;
   }
-  if (length == 3) {
+  DCHECK(length == 4);
+  DCHECK(str[0] >= 0xF0 && str[0] <= 0xF4);
+  switch (str[0]) {
+    case 0xF0:
+      if (str[1] < 0x90 || str[1] > 0xBF) {
+        *cursor += 1;
+        return kBadChar;
+      }
+      break;
+    case 0xF4:
+      if (str[1] < 0x80 || str[1] > 0x8F) {
+        *cursor += 1;
+        return kBadChar;
+      }
+      break;
+    default:
+      if (str[1] < 0x80 || str[1] > 0xBF) {
+        *cursor += 1;
+        return kBadChar;
+      }
+  }
+  if (str[2] < 0x80 || str[2] > 0xBF) {
     *cursor += 1;
     return kBadChar;
   }
-  byte fourth = str[3] ^ 0x80;
-  if (fourth & 0xC0) {
+  if (str[3] < 0x80 || str[3] > 0xBF) {
     *cursor += 1;
     return kBadChar;
   }
-  if (first < 0xF8) {
-    uchar code_point = (((((first << 6 | second) << 6) | third) << 6) | fourth)
-        & kMaxFourByteChar;
-    if (code_point <= kMaxThreeByteChar) {
-      *cursor += 1;
-      return kBadChar;
-    }
-    *cursor += 4;
-    return code_point;
-  }
-  *cursor += 1;
-  return kBadChar;
+  *cursor += 4;
+  return ((str[0] << 18) + (str[1] << 12) + (str[2] << 6) + str[3]) -
+         0x03C82080;
 }
 
 
 // Uppercase:            point.category == 'Lu'
 
 static const uint16_t kUppercaseTable0Size = 455;
 static const int32_t kUppercaseTable0[455] = {
     1073741889, 90,         1073742016, 214,
     1073742040, 222,        256,        258,  // NOLINT
     260,        262,        264,        266,
@@ skipping 3117 matching lines @@
              sizeof(MultiCharacterSpecialCase<1>)  // NOLINT
          +
          kCanonicalizationRangeMultiStrings1Size *
              sizeof(MultiCharacterSpecialCase<1>)  // NOLINT
          +
          kCanonicalizationRangeMultiStrings7Size *
              sizeof(MultiCharacterSpecialCase<1>);  // NOLINT
 }
 
 }  // namespace unibrow