Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / lazarus / 2015-08

Improving UTF8CharacterLength?

15 messages · 3 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Jürgen Hestermann

I just had a closer look at the function UTF8CharacterLength in unit LazUTF8. To me it looks as if it can be improved (made faster) because it checks too many things.

According to https://de.wikipedia.org/wiki/UTF-8 the number of bytes of an UTF-8-character should be computable by the first byte only. So it seems not to be neccessary to check for any following bytes (which also bears the danger of accessing bytes out of the range of the string). Isn't it enough to just do it like this:

------------------------------
if p=nil then
    exit(0);
if (ord(p^) and %10000000)=%00000000 then // First bit is not set ==> 1 byte
    exit(1);
if (ord(p^) and %11100000)=%11000000 then // First 2 (of first 3) bits are set ==> 2 byte
    exit(2);
if (ord(p^) and %11110000)=%11100000 then // First 3 (of first 4) bits are set ==> 3 byte
    exit(3);
if (ord(p^) and %11111000)=%11110000 then // First 4 (of first 5) bits are set ==> 4 byte
    exit(4);
exit(0); // invalid UTF-8 character
-------------------------------

Currently, further bytes are checked even when
the first byte already determines the number of bytes. But if the following bytes would not be as expected it would not be a valid UTF-8-character.
But should this be checked by the UTF8CharacterLength function? There is no error condition in the result of the function anyway. I think errors should be checked when accessing the character as a whole. Or is there any reason for handling invalid UTF-8-bytes more fault-tolerant?

Reply by email

Jürgen Hestermann
to Jürgen Hestermann
J?rgen Hestermann wrote 32 lines
I just had a closer look at the function UTF8CharacterLength in unit LazUTF8. To me it looks as if it can be improved (made faster) because it checks too many things. According to https://de.wikipedia.org/wiki/UTF-8 the number of bytes of an UTF-8-character should be computable by the first byte only. So it seems not to be neccessary to check for any following bytes (which also bears the danger of accessing bytes out of the range of the string). Isn't it enough to just do it like this: ------------------------------ if p=nil then exit(0); if (ord(p^) and %10000000)=%00000000 then // First bit is not set ==> 1 byte exit(1); if (ord(p^) and %11100000)=%11000000 then // First 2 (of first 3) bits are set ==> 2 byte exit(2); if (ord(p^) and %11110000)=%11100000 then // First 3 (of first 4) bits are set ==> 3 byte exit(3); if (ord(p^) and %11111000)=%11110000 then // First 4 (of first 5) bits are set ==> 4 byte exit(4); exit(0); // invalid UTF-8 character ------------------------------- Currently, further bytes are checked even when the first byte already determines the number of bytes. But if the following bytes would not be as expected it would not be a valid UTF-8-character. But should this be checked by the UTF8CharacterLength function? There is no error condition in the result of the function anyway. I think errors should be checked when accessing the character as a whole. Or is there any reason for handling invalid UTF-8-bytes more fault-tolerant?

Realy nobody has has an opinion to this topic?
Strange.
Well, I take this as an implicit answer that I did not make any error in reasoning. I am now using my own "UTF8CharacterLength" but I thought others could make use of it too.

Reply by email

Mattias Gaertner
to Jürgen Hestermann: I just had a closer look at the function UTF8CharacterLength in unit LazUTF8. To me it…
Show quoted text 5 lines
I just had a closer look at the function UTF8CharacterLength in unit LazUTF8. To me it looks as if it can be improved (made faster) because it checks too many things. According to https://de.wikipedia.org/wiki/UTF-8 the number of bytes of an UTF-8-character should be computable by the first byte only.

True.

So it seems not to be neccessary to check for any following bytes (which also bears the danger of accessing bytes out of the range of the string).

A string always ends with a #0, so checking byte by byte makes sure you stay within range.
If you only read the first byte of a codepoint to determine its length, you must check the length of the string.

The UTF8CharacterLength function handles invalid UTF-8 gracefully. If you know that you have a valid UTF-8 string you can simply use the first byte of each codepoint (as you pointed out). So, for that case a faster function can be added.
Maybe UTF8QuickCharLen or something like that.

Show quoted text 15 lines
Isn't it enough to just do it like this: ------------------------------ if p=nil then exit(0); if (ord(p^) and %10000000)=%00000000 then // First bit is not set ==> 1 byte exit(1); if (ord(p^) and %11100000)=%11000000 then // First 2 (of first 3) bits are set ==> 2 byte exit(2); if (ord(p^) and %11110000)=%11100000 then // First 3 (of first 4) bits are set ==> 3 byte exit(3); if (ord(p^) and %11111000)=%11110000 then // First 4 (of first 5) bits are set ==> 4 byte exit(4); exit(0); // invalid UTF-8 character -------------------------------

Yes, although afaik the compiler can optimize a CASE better than a series of IFs.

case p^ of
#0..#127: exit(1);
#192..#223: exit(2);
#224..#239: exit(3);
#240..#247: exit(4);
else exit(0); // invalid UTF-8 character, should never happen
end;

Note: because it is an optimized version the check for p=nil can be omitted.

Show quoted text 8 lines
Currently, further bytes are checked even when the first byte already determines the number of bytes. But if the following bytes would not be as expected it would not be a valid UTF-8-character. But should this be checked by the UTF8CharacterLength function? There is no error condition in the result of the function anyway. I think errors should be checked when accessing the character as a whole. Or is there any reason for handling invalid UTF-8-bytes more fault-tolerant?

The last, more fault-tolerant.

This allows to use the function like this:

while p^#0 do begin
  CharLen:=UTF8CharacterLength(p);
  // ...
  inc(p,CharLen);
end;

This works even with invalid UTF8.

Mattias

Reply by email

Jürgen Hestermann
to Mattias Gaertner
Mattias Gaertner wrote
A string always ends with a #0, so checking byte by byte makes sure you stay within range.

Not quite true:
------------
if ((ord(p^) and %11110000) = %11100000) then

    begin  // could be 3 byte character
    if ((ord(p[1]) and %11000000) = %10000000) and
       ((ord(p[2]) and %11000000) = %10000000) then ...
    ...

------------
In the above (current) code 3 bytes are accessed which may step behind the zero byte. UTF8CharacterLength raises an exception in this case because it does not check for string length (zero byte).

If you only read the first byte of a codepoint to determine its length, you must check the length of the string.

Thats something that needs to be checked in all cases anyway. So it's double code (in UTF8CharacterLength and in my program). Also, as stated at the beginning, the code in UTF8CharacterLength does not prevent from accessing bytes behind the last (zero) byte.

The UTF8CharacterLength function handles invalid UTF-8 gracefully.

Not realy (see above).

If you know that you have a valid UTF-8 string you can simply use the first byte of each codepoint (as you pointed out). So, for that case a faster function can be added. Maybe UTF8QuickCharLen or something like that.

Determining the character length of a invalid UTF-8 string is quite useless. What do you do with such a result? IMO the UTF8CharacterLength funtion should always assume a valid UTF-8 string. Using this function on invalid UTF-8 strings lets you run into problems anyway.

Show quoted text 24 lines
> > Isn't it enough to just do it like this: > > > > ------------------------------ > > if p=nil then > > exit(0); > > if (ord(p^) and %10000000)=%00000000 then // First bit is not set ==> 1 byte > > exit(1); > > if (ord(p^) and %11100000)=%11000000 then // First 2 (of first 3) bits are set ==> 2 byte > > exit(2); > > if (ord(p^) and %11110000)=%11100000 then // First 3 (of first 4) bits are set ==> 3 byte > > exit(3); > > if (ord(p^) and %11111000)=%11110000 then // First 4 (of first 5) bits are set ==> 4 byte > > exit(4); > > exit(0); // invalid UTF-8 character > > ------------------------------- Yes, although afaik the compiler can optimize a CASE better than a series of IFs. case p^ of #0..#127: exit(1); #192..#223: exit(2); #224..#239: exit(3); #240..#247: exit(4); else exit(0); // invalid UTF-8 character, should never happen end;

Realy? With the if statements only constants are used. In the case statement you have ranges and I think that more code is necessary to determine whether a value is whithin a range than only checking whether it is a certain constant (or not). But I don't know how far the compiler can optimze which cases (which may also depend on the optimisation opition used).

Note: because it is an optimized version the check for p=nil can be omitted.

Yes.

Show quoted text 9 lines
> > Or is there any reason for handling invalid UTF-8-bytes more fault-tolerant? The last, more fault-tolerant. This allows to use the function like this: while p^#0 do begin CharLen:=UTF8CharacterLength(p); // ... inc(p,CharLen); end; This works even with invalid UTF8.

Not true (as stated at the beginning).
You may already get an exception within UTF8CharacterLength.

It makes no sense if you try to compensate one error (invalid UTF-8 string) by another error (giving back wrong results of UTF8CharacterLength). It will never result in a proper program.

Reply by email

Michael Van Canneyt
to Jürgen Hestermann
J?rgen Hestermann wrote 8 lines
Am 2015-08-13 um 11:55 schrieb Mattias Gaertner: > If you know that you have a valid UTF-8 string you can simply use the > first byte of each codepoint (as you pointed out). So, for that case a > faster function can be added. > Maybe UTF8QuickCharLen or something like that. Determining the character length of a invalid UTF-8 string is quite useless.

Because it's not about getting a correct result then, but about not crashing due to invalid memory access.

Many safety leaks are due to invalid memory access.

Michael.

Reply by email

Mattias Gaertner
to Jürgen Hestermann: Not quite true: ------------ if ((ord(p^) and %11110000) = %11100000) then begin //…
Show quoted text 13 lines
Am 2015-08-13 um 11:55 schrieb Mattias Gaertner: > A string always ends with a #0, so checking byte by byte makes sure you > stay within range. Not quite true: ------------ if ((ord(p^) and %11110000) = %11100000) then begin // could be 3 byte character if ((ord(p[1]) and %11000000) = %10000000) and ((ord(p[2]) and %11000000) = %10000000) then ... ... ------------ In the above (current) code 3 bytes are accessed which may step behind the zero byte.

The "and" operator stops evaluating if left side is already false.

Thats something that needs to be checked in all cases anyway.

No.
That's the advantage of PChar and ASCIIZ.

Show quoted text 8 lines
[...] > If you know that you have a valid UTF-8 string you can simply use the > first byte of each codepoint (as you pointed out). So, for that case a > faster function can be added. > Maybe UTF8QuickCharLen or something like that. Determining the character length of a invalid UTF-8 string is quite useless. What do you do with such a result?

Skip.

IMO the UTF8CharacterLength funtion should always assume a valid UTF-8 string. Using this function on invalid UTF-8 strings lets you run into problems anyway.

It is already used this way in many places. If you need a function with a different behavior you need to add new one.

Show quoted text 5 lines
[...] > Yes, although afaik the compiler can optimize a CASE better than a series of IFs [...] Realy?

Look at the produced assembler or do some benchmarking.

[...]

Mattias

Reply by email

Jürgen Hestermann
to Michael Van Canneyt: Because it's not about getting a correct result then, but about not crashing due to…
Michael Van Canneyt wrote 7 lines
On Thu, 13 Aug 2015, J?rgen Hestermann wrote: > Determining the character length of a invalid UTF-8 string is quite useless. Because it's not about getting a correct result then, but about not crashing due to invalid memory access.

But invalid memory access takes place anyway (within UTF8CharacterLength). So what is gained?

Reply by email

Jürgen Hestermann
to Mattias Gaertner: On Thu, 13 Aug 2015 12:38:00 +0200 The "and" operator stops evaluating if left side is…
Mattias Gaertner wrote 15 lines
On Thu, 13 Aug 2015 12:38:00 +0200 J?rgen Hestermann wrote: > Am 2015-08-13 um 11:55 schrieb Mattias Gaertner: > > A string always ends with a #0, so checking byte by byte makes sure you > > stay within range. > Not quite true: > ------------ > if ((ord(p^) and %11110000) = %11100000) then > begin // could be 3 byte character > if ((ord(p[1]) and %11000000) = %10000000) and > ((ord(p[2]) and %11000000) = %10000000) then ... > ... > ------------ > In the above (current) code 3 bytes are accessed which may step behind the zero byte. The "and" operator stops evaluating if left side is already false.

Only if you have a valid UTF-8 string.
I thought we are talking about *invalid* UTF-8 strings where it can happen that p[2] is accessed although it is not part of the string.

Reply by email

Michael Van Canneyt
to Jürgen Hestermann: But invalid memory access takes place anyway (within UTF8CharacterLength). So what is…
J?rgen Hestermann wrote 12 lines
Am 2015-08-13 um 12:59 schrieb Michael Van Canneyt: > > > On Thu, 13 Aug 2015, J?rgen Hestermann wrote: > >> Determining the character length of a invalid UTF-8 string is quite >> useless. > > Because it's not about getting a correct result then, but about not > crashing due to invalid memory access. But invalid memory access takes place anyway (within UTF8CharacterLength).

Why do you say so ?
Unless you give a really bogus pointer, one of p[0] till p[3] is guaranteed to have #0 in it. In such a case, no scan of the next byte is done ?

Michael.

Reply by email

Jürgen Hestermann
to Michael Van Canneyt
Michael Van Canneyt wrote 17 lines
On Thu, 13 Aug 2015, J?rgen Hestermann wrote: > Am 2015-08-13 um 12:59 schrieb Michael Van Canneyt: >> >> >> On Thu, 13 Aug 2015, J?rgen Hestermann wrote: >> >>> Determining the character length of a invalid UTF-8 string is quite useless. >> >> Because it's not about getting a correct result then, but about not crashing due to invalid memory access. > > But invalid memory access takes place anyway (within UTF8CharacterLength). Why do you say so ? Unless you give a really bogus pointer, one of p[0] till p[3] is guaranteed to have #0 in it. In such a case, no scan of the next byte is done ?

Sorry, I missinterpreted the code.
You are right.
I now see that the zero byte would stop any futher access to bytes after it.

Reply by email

Mattias Gaertner
to Jürgen Hestermann: Only if you have a valid UTF-8 string. I thought we are talking about *invalid* UTF-8…
Show quoted text 11 lines
[...] >> if ((ord(p^) and %11110000) = %11100000) then >> begin // could be 3 byte character >> if ((ord(p[1]) and %11000000) = %10000000) and >> ((ord(p[2]) and %11000000) = %10000000) then ... >> ... >> ------------ >> In the above (current) code 3 bytes are accessed which may step behind the zero byte. > The "and" operator stops evaluating if left side is already false. Only if you have a valid UTF-8 string.

I can't follow you here. If the string is valid UTF-8 then p[1] and p[2] are not zero.

I thought we are talking about *invalid* UTF-8 strings where it can happen that p[2] is accessed although it is not part of the string.

I can't follow you here. If p[2] is not part of the string, then p[1] must be #0.

Mattias

Reply by email

Jürgen Hestermann
to Mattias Gaertner: On Thu, 13 Aug 2015 12:38:00 +0200 The "and" operator stops evaluating if left side is…
Mattias Gaertner wrote 17 lines
On Thu, 13 Aug 2015 12:38:00 +0200 J?rgen Hestermann wrote: > Am 2015-08-13 um 11:55 schrieb Mattias Gaertner: > > A string always ends with a #0, so checking byte by byte makes sure you > > stay within range. > > Not quite true: > ------------ > if ((ord(p^) and %11110000) = %11100000) then > begin // could be 3 byte character > if ((ord(p[1]) and %11000000) = %10000000) and > ((ord(p[2]) and %11000000) = %10000000) then ... > ... > ------------ > In the above (current) code 3 bytes are accessed which may step behind the zero byte. The "and" operator stops evaluating if left side is already false.

Yes, I see now that I somehow missinterpreted the code. You are right that for the case that a zero byte exists it would not access further bytes within UTF8CharacterLength.

Still I think it would be better to give back 3 in case the byte actually means 3 because 1 byte does not form a valid UTF-8 character. If I rely on this result I would try to use this 1 byte as a valid UTF-8 character which would be wrong so I have to apply further checks to cope with this situation anyway. Then I can also check whether the 3 or 4 bytes of the correct result exist. I would not loose anything for invalid UTF-8 strings but I would gain performance if I can guarantee valid UTF-8 string.

And if no zero byte exists (for whatever reason) it currently fails anyway.

Reply by email

Mattias Gaertner
to Jürgen Hestermann
Show quoted text 5 lines
[...] Still I think it would be better to give back 3 in case the byte actually means 3 because 1 byte does not form a valid UTF-8 character. If I rely on this result I would try to use this 1 byte as a valid UTF-8 character which would be wrong so I have to apply further checks to cope with this situation anyway.

Do you mean like UTF8CharacterStrictLength?

Then I can also check whether the 3 or 4 bytes of the correct result exist. I would not loose anything for invalid UTF-8 strings but I would gain performance if I can guarantee valid UTF-8 string.

For this the UTF8QuickCharLen function would suffice, would it not?

And if no zero byte exists (for whatever reason) it currently fails anyway.

Till now the Lazarus code didn't have such a case.

Mattias

Reply by email

Jürgen Hestermann
to Mattias Gaertner
Mattias Gaertner wrote 7 lines
On Thu, 13 Aug 2015 14:05:19 +0200 J?rgen Hestermann wrote: > Still I think it would be better to give back 3 in case the byte actually > means 3 because 1 byte does not form a valid UTF-8 character. > If I rely on this result I would try to use this 1 byte as a valid UTF-8 character > which would be wrong so I have to apply further checks to cope with this situation anyway. Do you mean like UTF8CharacterStrictLength?

I did not know that yet another quite similar function like UTF8CharacterStrictLength exists. So many functions doing nearly the same thing is very confusing....

If I am right (after a quick look) then UTF8CharacterStrictLength gives back 0 in cases where UTF8CharacterLength would give back 1.

IMO this does not change the underlying problem that if you have an invalid UTF-8 string then you cannot fix this situation within functions like UTF8CharacterLength or UTF8CharacterStrictLength. There is no way around it other than:

1.) Make sure your strings are all valid UTF-8 or
2.) Do error checking and error handling in your program yourself

In both cases I think no further error handling is needed within such helper routines.

> Then I can also check whether the 3 or 4 bytes of the correct result exist. > I would not loose anything for invalid UTF-8 strings but I would gain performance if > I can guarantee valid UTF-8 string. For this the UTF8QuickCharLen function would suffice, would it not?

Yes, of course.
Although I am wondering whether yet another function needs to be added. To have an overview over all the UTF-8 functions is already quite complex and I still think that error checking should not be part of such helper functions so that only one is needed.

> And if no zero byte exists (for whatever reason) it currently fails anyway. Till now the Lazarus code didn't have such a case.

Yes, maybe it's quite unlikely to have such a situation. If a pchar pointer points to arbitrary data it will be impossible to cope with this situation anyway.

Reply by email

Mattias Gaertner
to Jürgen Hestermann
[...] If I am right (after a quick look) then UTF8CharacterStrictLength gives back 0 in cases where UTF8CharacterLength would give back 1.

Yes.

IMO this does not change the underlying problem that if you have an invalid UTF-8 string then you cannot fix this situation within functions like UTF8CharacterLength or UTF8CharacterStrictLength.

They should not fix it. If you want to fix a string you can use the UTF8FixBroken function.

There is no way around it other than: 1.) Make sure your strings are all valid UTF-8 or 2.) Do error checking and error handling in your program yourself

3.) Skip invalid chars.

Mattias

Reply by email