paleolimbot commented on code in PR #981:
URL: https://github.com/apache/arrow-nanoarrow/pull/981#discussion_r4341144399
##########
src/nanoarrow/common/array.c:
##########
@@ -2123,6 +2123,155 @@ static int ArrowAssertInt8In(struct ArrowBufferView
view, const int8_t* values,
return NANOARROW_OK;
}
+// Returns the length of the longest prefix of data that is valid UTF-8 (RFC
3629), so
+// data is valid UTF-8 if and only if the result is size_bytes. Overlong
encodings,
+// surrogates (U+D800 to U+DFFF), code points above U+10FFFF, stray
continuation bytes
+// and truncated sequences are all invalid.
+static int64_t ArrowUtf8ValidPrefix(const uint8_t* data, int64_t size_bytes) {
+ int64_t i = 0;
+ while (i < size_bytes) {
+ const uint8_t lead = data[i];
+
+ if (lead < 0x80) {
+ // After an ASCII byte, skip any further ASCII eight bytes at a time
+ i++;
+ while (size_bytes - i >= 8) {
+ uint64_t word;
+ memcpy(&word, data + i, sizeof(word));
+ if ((word & 0x8080808080808080ULL) != 0) {
+ break;
+ }
+ i += 8;
+ }
+ continue;
+ }
+
+ if (lead < 0xE0) {
+ // Two bytes (U+0080 to U+07FF); 0xC0 and 0xC1 would be overlong
+ if (lead < 0xC2 || size_bytes - i < 2 || (data[i + 1] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 2;
+ continue;
+ }
+
+ if (lead < 0xF0) {
+ // Three bytes (U+0800 to U+FFFF), excluding overlong encodings (0xE0
followed
+ // by less than 0xA0) and surrogates (0xED followed by 0xA0 or more)
+ if (size_bytes - i < 3) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xE0 ? 0xA0 : 0x80;
+ const uint8_t second_max = lead == 0xED ? 0x9F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0)
!= 0x80) {
+ return i;
+ }
+ i += 3;
+ continue;
+ }
+
+ // Four bytes (U+10000 to U+10FFFF), excluding overlong encodings (0xF0
followed by
+ // less than 0x90) and code points above U+10FFFF (0xF4 followed by 0x90
or more, or
+ // a lead byte above 0xF4)
+ if (lead > 0xF4 || size_bytes - i < 4) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xF0 ? 0x90 : 0x80;
+ const uint8_t second_max = lead == 0xF4 ? 0x8F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0) !=
0x80 ||
+ (data[i + 3] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 4;
+ }
+
+ return size_bytes;
+}
+
+static int64_t ArrowArrayViewGetOffsetUnsafe(const struct ArrowArrayView*
array_view,
+ int64_t i) {
+ if (array_view->layout.element_size_bits[1] == 32) {
+ return ArrowBufferViewGetInt32Unsafe(&array_view->buffer_views[1], i);
+ } else {
+ return ArrowBufferViewGetInt64Unsafe(&array_view->buffer_views[1], i);
+ }
+}
+
+static int ArrowArrayViewValidateUtf8Element(const struct ArrowArrayView*
array_view,
+ int64_t i, const uint8_t* value,
+ int64_t size_bytes,
+ struct ArrowError* error) {
+ if (size_bytes == 0) {
+ return NANOARROW_OK;
+ }
+
+ int64_t valid_bytes = ArrowUtf8ValidPrefix(value, size_bytes);
+ if (valid_bytes != size_bytes) {
+ ArrowErrorSet(error,
+ "[%" PRId64
+ "] Expected valid UTF-8 %s value but found invalid "
+ "sequence at byte %" PRId64,
+ i, ArrowTypeString(array_view->storage_type), valid_bytes);
+ return EINVAL;
+ }
+
+ return NANOARROW_OK;
+}
+
+// Check that every non-null value of a string or large string array is valid
UTF-8.
+// Like Arrow C++, values are checked one at a time (a code point split across
two
+// values is invalid) and the bytes of null values are not checked.
+static int ArrowArrayViewValidateUtf8(const struct ArrowArrayView* array_view,
+ struct ArrowError* error) {
+ // The offsets buffer of a zero-length array may be empty
+ if (array_view->length == 0) {
+ return NANOARROW_OK;
+ }
+
+ const uint8_t* data = array_view->buffer_views[2].data.as_uint8;
+
+ // The values (including those of null slots) are the contiguous range of
bytes
+ // between the first and last offsets. If that whole range is valid and
every value
+ // begins on a code point boundary (i.e., not with a continuation byte),
every value is
+ // valid, which avoids validating short values one at a time. Otherwise,
check the
+ // non-null values one at a time to find (and report) the first invalid one.
+ {
+ int64_t first = ArrowArrayViewGetOffsetUnsafe(array_view,
array_view->offset);
+ int64_t last = ArrowArrayViewGetOffsetUnsafe(array_view,
+ array_view->offset +
array_view->length);
+ if (first == last) {
+ return NANOARROW_OK;
+ }
+
+ int ok = ArrowUtf8ValidPrefix(data + first, last - first) == last - first;
+ for (int64_t i = 1; ok && i < array_view->length; i++) {
+ int64_t start = ArrowArrayViewGetOffsetUnsafe(array_view,
array_view->offset + i);
+ ok = start == last || (data[start] & 0xC0) != 0x80;
+ }
+
+ if (ok) {
+ return NANOARROW_OK;
+ }
+ }
+
+ for (int64_t i = 0; i < array_view->length; i++) {
+ if (ArrowArrayViewIsNull(array_view, i)) {
+ continue;
+ }
+
+ int64_t start = ArrowArrayViewGetOffsetUnsafe(array_view,
array_view->offset + i);
+ int64_t end = ArrowArrayViewGetOffsetUnsafe(array_view, array_view->offset
+ i + 1);
+ if (end > start) {
+ NANOARROW_RETURN_NOT_OK(ArrowArrayViewValidateUtf8Element(
+ array_view, i, data + start, end - start, error));
+ }
+ }
Review Comment:
`ArrowArrayViewGetStringUnsafe()` would handle the view case as well, but
might be slower. If I were trying to make the iteration go as fast as possible
here I would write a separate loop for the string, large string, and string
view cases (but worth benchmarking).
##########
src/nanoarrow/common/array.c:
##########
@@ -2123,6 +2123,155 @@ static int ArrowAssertInt8In(struct ArrowBufferView
view, const int8_t* values,
return NANOARROW_OK;
}
+// Returns the length of the longest prefix of data that is valid UTF-8 (RFC
3629), so
+// data is valid UTF-8 if and only if the result is size_bytes. Overlong
encodings,
+// surrogates (U+D800 to U+DFFF), code points above U+10FFFF, stray
continuation bytes
+// and truncated sequences are all invalid.
+static int64_t ArrowUtf8ValidPrefix(const uint8_t* data, int64_t size_bytes) {
+ int64_t i = 0;
+ while (i < size_bytes) {
+ const uint8_t lead = data[i];
+
+ if (lead < 0x80) {
+ // After an ASCII byte, skip any further ASCII eight bytes at a time
+ i++;
+ while (size_bytes - i >= 8) {
+ uint64_t word;
+ memcpy(&word, data + i, sizeof(word));
+ if ((word & 0x8080808080808080ULL) != 0) {
+ break;
+ }
+ i += 8;
+ }
+ continue;
+ }
+
+ if (lead < 0xE0) {
+ // Two bytes (U+0080 to U+07FF); 0xC0 and 0xC1 would be overlong
+ if (lead < 0xC2 || size_bytes - i < 2 || (data[i + 1] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 2;
+ continue;
+ }
+
+ if (lead < 0xF0) {
+ // Three bytes (U+0800 to U+FFFF), excluding overlong encodings (0xE0
followed
+ // by less than 0xA0) and surrogates (0xED followed by 0xA0 or more)
+ if (size_bytes - i < 3) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xE0 ? 0xA0 : 0x80;
+ const uint8_t second_max = lead == 0xED ? 0x9F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0)
!= 0x80) {
+ return i;
+ }
+ i += 3;
+ continue;
+ }
+
+ // Four bytes (U+10000 to U+10FFFF), excluding overlong encodings (0xF0
followed by
+ // less than 0x90) and code points above U+10FFFF (0xF4 followed by 0x90
or more, or
+ // a lead byte above 0xF4)
+ if (lead > 0xF4 || size_bytes - i < 4) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xF0 ? 0x90 : 0x80;
+ const uint8_t second_max = lead == 0xF4 ? 0x8F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0) !=
0x80 ||
+ (data[i + 3] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 4;
+ }
+
+ return size_bytes;
+}
+
+static int64_t ArrowArrayViewGetOffsetUnsafe(const struct ArrowArrayView*
array_view,
+ int64_t i) {
+ if (array_view->layout.element_size_bits[1] == 32) {
+ return ArrowBufferViewGetInt32Unsafe(&array_view->buffer_views[1], i);
+ } else {
+ return ArrowBufferViewGetInt64Unsafe(&array_view->buffer_views[1], i);
+ }
+}
+
+static int ArrowArrayViewValidateUtf8Element(const struct ArrowArrayView*
array_view,
+ int64_t i, const uint8_t* value,
+ int64_t size_bytes,
+ struct ArrowError* error) {
+ if (size_bytes == 0) {
+ return NANOARROW_OK;
+ }
+
+ int64_t valid_bytes = ArrowUtf8ValidPrefix(value, size_bytes);
+ if (valid_bytes != size_bytes) {
+ ArrowErrorSet(error,
+ "[%" PRId64
+ "] Expected valid UTF-8 %s value but found invalid "
+ "sequence at byte %" PRId64,
+ i, ArrowTypeString(array_view->storage_type), valid_bytes);
+ return EINVAL;
+ }
+
+ return NANOARROW_OK;
+}
+
+// Check that every non-null value of a string or large string array is valid
UTF-8.
+// Like Arrow C++, values are checked one at a time (a code point split across
two
+// values is invalid) and the bytes of null values are not checked.
+static int ArrowArrayViewValidateUtf8(const struct ArrowArrayView* array_view,
+ struct ArrowError* error) {
+ // The offsets buffer of a zero-length array may be empty
+ if (array_view->length == 0) {
+ return NANOARROW_OK;
+ }
+
+ const uint8_t* data = array_view->buffer_views[2].data.as_uint8;
+
+ // The values (including those of null slots) are the contiguous range of
bytes
+ // between the first and last offsets. If that whole range is valid and
every value
+ // begins on a code point boundary (i.e., not with a continuation byte),
every value is
+ // valid, which avoids validating short values one at a time. Otherwise,
check the
+ // non-null values one at a time to find (and report) the first invalid one.
+ {
+ int64_t first = ArrowArrayViewGetOffsetUnsafe(array_view,
array_view->offset);
+ int64_t last = ArrowArrayViewGetOffsetUnsafe(array_view,
+ array_view->offset +
array_view->length);
+ if (first == last) {
+ return NANOARROW_OK;
+ }
+
+ int ok = ArrowUtf8ValidPrefix(data + first, last - first) == last - first;
+ for (int64_t i = 1; ok && i < array_view->length; i++) {
+ int64_t start = ArrowArrayViewGetOffsetUnsafe(array_view,
array_view->offset + i);
+ ok = start == last || (data[start] & 0xC0) != 0x80;
+ }
Review Comment:
It may be worth writing two loops here to avoid the branch in
ArrowArrayViewGetOffsetUnsafe (maybe the optimizer does this anyway). Views
probably don't benefit from this sort of treatment and can fall back to the
generic path.
##########
src/nanoarrow/common/array.c:
##########
@@ -2123,6 +2123,155 @@ static int ArrowAssertInt8In(struct ArrowBufferView
view, const int8_t* values,
return NANOARROW_OK;
}
+// Returns the length of the longest prefix of data that is valid UTF-8 (RFC
3629), so
+// data is valid UTF-8 if and only if the result is size_bytes. Overlong
encodings,
+// surrogates (U+D800 to U+DFFF), code points above U+10FFFF, stray
continuation bytes
+// and truncated sequences are all invalid.
+static int64_t ArrowUtf8ValidPrefix(const uint8_t* data, int64_t size_bytes) {
+ int64_t i = 0;
+ while (i < size_bytes) {
+ const uint8_t lead = data[i];
+
+ if (lead < 0x80) {
+ // After an ASCII byte, skip any further ASCII eight bytes at a time
+ i++;
+ while (size_bytes - i >= 8) {
+ uint64_t word;
+ memcpy(&word, data + i, sizeof(word));
+ if ((word & 0x8080808080808080ULL) != 0) {
+ break;
+ }
+ i += 8;
+ }
+ continue;
+ }
+
+ if (lead < 0xE0) {
+ // Two bytes (U+0080 to U+07FF); 0xC0 and 0xC1 would be overlong
+ if (lead < 0xC2 || size_bytes - i < 2 || (data[i + 1] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 2;
+ continue;
+ }
+
+ if (lead < 0xF0) {
+ // Three bytes (U+0800 to U+FFFF), excluding overlong encodings (0xE0
followed
+ // by less than 0xA0) and surrogates (0xED followed by 0xA0 or more)
+ if (size_bytes - i < 3) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xE0 ? 0xA0 : 0x80;
+ const uint8_t second_max = lead == 0xED ? 0x9F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0)
!= 0x80) {
+ return i;
+ }
+ i += 3;
+ continue;
+ }
+
+ // Four bytes (U+10000 to U+10FFFF), excluding overlong encodings (0xF0
followed by
+ // less than 0x90) and code points above U+10FFFF (0xF4 followed by 0x90
or more, or
+ // a lead byte above 0xF4)
+ if (lead > 0xF4 || size_bytes - i < 4) {
+ return i;
+ }
+ const uint8_t second = data[i + 1];
+ const uint8_t second_min = lead == 0xF0 ? 0x90 : 0x80;
+ const uint8_t second_max = lead == 0xF4 ? 0x8F : 0xBF;
+ if (second < second_min || second > second_max || (data[i + 2] & 0xC0) !=
0x80 ||
+ (data[i + 3] & 0xC0) != 0x80) {
+ return i;
+ }
+ i += 4;
+ }
+
+ return size_bytes;
+}
+
+static int64_t ArrowArrayViewGetOffsetUnsafe(const struct ArrowArrayView*
array_view,
+ int64_t i) {
+ if (array_view->layout.element_size_bits[1] == 32) {
+ return ArrowBufferViewGetInt32Unsafe(&array_view->buffer_views[1], i);
+ } else {
+ return ArrowBufferViewGetInt64Unsafe(&array_view->buffer_views[1], i);
+ }
+}
+
+static int ArrowArrayViewValidateUtf8Element(const struct ArrowArrayView*
array_view,
+ int64_t i, const uint8_t* value,
+ int64_t size_bytes,
+ struct ArrowError* error) {
+ if (size_bytes == 0) {
+ return NANOARROW_OK;
+ }
+
+ int64_t valid_bytes = ArrowUtf8ValidPrefix(value, size_bytes);
+ if (valid_bytes != size_bytes) {
+ ArrowErrorSet(error,
+ "[%" PRId64
+ "] Expected valid UTF-8 %s value but found invalid "
+ "sequence at byte %" PRId64,
+ i, ArrowTypeString(array_view->storage_type), valid_bytes);
+ return EINVAL;
+ }
+
+ return NANOARROW_OK;
+}
+
+// Check that every non-null value of a string or large string array is valid
UTF-8.
+// Like Arrow C++, values are checked one at a time (a code point split across
two
+// values is invalid) and the bytes of null values are not checked.
Review Comment:
Should probably update this to reflect what actually happens here (null
values are checked, but invalid utf8 in a null slot doesn't fail validation)
##########
src/nanoarrow/common/array.c:
##########
@@ -2123,6 +2123,155 @@ static int ArrowAssertInt8In(struct ArrowBufferView
view, const int8_t* values,
return NANOARROW_OK;
}
+// Returns the length of the longest prefix of data that is valid UTF-8 (RFC
3629), so
+// data is valid UTF-8 if and only if the result is size_bytes. Overlong
encodings,
+// surrogates (U+D800 to U+DFFF), code points above U+10FFFF, stray
continuation bytes
+// and truncated sequences are all invalid.
+static int64_t ArrowUtf8ValidPrefix(const uint8_t* data, int64_t size_bytes) {
Review Comment:
Can you add a reference to the Arrow C++ source from which this was derived
(or another source if it came from somewhere else?)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
