Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #82746 > unrolled thread

Can anyone improve this ?

Back to article view | Back to comp.lang.c++

Contents

  Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 09:08 +0100
    Re: Can anyone improve this ? Juha Nieminen <nospam@thanks.invalid> - 2022-01-11 09:50 +0000
      Re: Can anyone improve this ? Juha Nieminen <nospam@thanks.invalid> - 2022-01-11 11:07 +0000
      Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-11 11:08 +0000
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 18:28 +0100
        Re: Can anyone improve this ? Christian Gollwitzer <auriocus@gmx.de> - 2022-01-11 18:41 +0100
          Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 19:36 +0100
        Re: Can anyone improve this ? Öö Tiib <ootiib@hot.ee> - 2022-01-11 21:54 -0800
    Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 21:51 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 14:19 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 14:20 +0100
        Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-12 14:14 +0000
          Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 17:20 +0100
            Re: Can anyone improve this ? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2022-01-12 08:38 -0800
            Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-12 16:55 +0000
          Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-16 12:09 -0800
          Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-16 12:12 -0800
            Re: Can anyone improve this ? Öö Tiib <ootiib@hot.ee> - 2022-01-16 13:00 -0800
              Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 10:13 -0800
    Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 10:28 -0800
      Re: Can anyone improve this ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-01-17 21:51 +0100
        Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 16:16 -0800
        Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 22:43 -0800
          Re: Can anyone improve this ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-01-18 12:09 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-18 09:18 +0100

Page 1 of 2  [1] 2  Next page →

#82746 — Can anyone improve this ?

I had an idea how to write a fast UTF-8 strlen, here it is:

size_t utf8Strlen( char const *str )
{
     struct encode_t { size_t lenIncr, strIncr; };
     static encode_t const encodes[] =
     {
         { 1, 1 },
         { 0, 0 },
         { 1, 2 },
         { 1, 3 },
         { 1, 4 },
         { 0, 0 },
         { 0, 0 },
         { 0, 0 },
         { 0, 0 }
     };
     size_t len = 0;
     for( unsigned char c; (c = *str); )
     {
         encode_t const &enc = encodes[(size_t)countl_zero<unsigned 
char>( ~c )];
         if( !enc.lenIncr ) [[unlikely]]
             return -1;
         len += enc.lenIncr;
         for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
             if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
                 return -1;
     }
     return len;
}

Has anyone further ideas to improve this ?

[toc] | [next] | [standalone]

#82747

Bonita Montero <Bonita.Montero@gmail.com> wrote:
> I had an idea how to write a fast UTF-8 strlen, here it is:
> 
> size_t utf8Strlen( char const *str )
> {
>     struct encode_t { size_t lenIncr, strIncr; };
>     static encode_t const encodes[] =
>     {
>         { 1, 1 },
>         { 0, 0 },
>         { 1, 2 },
>         { 1, 3 },
>         { 1, 4 },
>         { 0, 0 },
>         { 0, 0 },
>         { 0, 0 },
>         { 0, 0 }
>     };
>     size_t len = 0;
>     for( unsigned char c; (c = *str); )
>     {
>         encode_t const &enc = encodes[(size_t)countl_zero<unsigned 
> char>( ~c )];
>         if( !enc.lenIncr ) [[unlikely]]
>             return -1;
>         len += enc.lenIncr;
>         for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>             if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>                 return -1;
>     }
>     return len;
> }
> 
> Has anyone further ideas to improve this ?

How does it compare to the more straightforward:

std::size_t utf8Strlen(const char *str)
{
    std::size_t length = 0;
    for(std::size_t index = 0; str[index]; ++index, ++length)
        if((str[index] & 0xC0) == 0xC0)
            while((str[index+1] & 0xC0) == 0x80)
                ++index;
    return length;
}

[toc] | [prev] | [next] | [standalone]

#82748

Juha Nieminen <nospam@thanks.invalid> wrote:
> How does it compare to the more straightforward:
> 
> std::size_t utf8Strlen(const char *str)
> {
>     std::size_t length = 0;
>     for(std::size_t index = 0; str[index]; ++index, ++length)
>         if((str[index] & 0xC0) == 0xC0)
>             while((str[index+1] & 0xC0) == 0x80)
>                 ++index;
>     return length;
> }

Actually there's an even simpler way:

std::size_t utf8Strlen(const char *str)
{
    std::size_t length = 0;
    for(std::size_t index = 0; str[index]; ++index)
        length += (str[index] & 0xC0) != 0x80;
    return length;
}

[toc] | [prev] | [next] | [standalone]

#82749

Juha Nieminen <nospam@thanks.invalid> writes:

> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I had an idea how to write a fast UTF-8 strlen, here it is:
>> 
>> size_t utf8Strlen( char const *str )
>> {
>>     struct encode_t { size_t lenIncr, strIncr; };
>>     static encode_t const encodes[] =
>>     {
>>         { 1, 1 },
>>         { 0, 0 },
>>         { 1, 2 },
>>         { 1, 3 },
>>         { 1, 4 },
>>         { 0, 0 },
>>         { 0, 0 },
>>         { 0, 0 },
>>         { 0, 0 }
>>     };
>>     size_t len = 0;
>>     for( unsigned char c; (c = *str); )
>>     {
>>         encode_t const &enc = encodes[(size_t)countl_zero<unsigned 
>> char>( ~c )];
>>         if( !enc.lenIncr ) [[unlikely]]
>>             return -1;
>>         len += enc.lenIncr;
>>         for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>>             if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>                 return -1;
>>     }
>>     return len;
>> }
>> 
>> Has anyone further ideas to improve this ?
>
> How does it compare to the more straightforward:
>
> std::size_t utf8Strlen(const char *str)
> {
>     std::size_t length = 0;
>     for(std::size_t index = 0; str[index]; ++index, ++length)
>         if((str[index] & 0xC0) == 0xC0)
>             while((str[index+1] & 0xC0) == 0x80)
>                 ++index;
>     return length;
> }

Or the even more straightforward:

  size_t ustrlen(char *s)
  {
       size_t len = 0;
       while (*s) len += (*s++ & 0xc0) != 0x80;
       return len;
  }

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#82750

Am 11.01.2022 um 10:50 schrieb Juha Nieminen:
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I had an idea how to write a fast UTF-8 strlen, here it is:
>>
>> size_t utf8Strlen( char const *str )
>> {
>>      struct encode_t { size_t lenIncr, strIncr; };
>>      static encode_t const encodes[] =
>>      {
>>          { 1, 1 },
>>          { 0, 0 },
>>          { 1, 2 },
>>          { 1, 3 },
>>          { 1, 4 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 }
>>      };
>>      size_t len = 0;
>>      for( unsigned char c; (c = *str); )
>>      {
>>          encode_t const &enc = encodes[(size_t)countl_zero<unsigned
>> char>( ~c )];
>>          if( !enc.lenIncr ) [[unlikely]]
>>              return -1;
>>          len += enc.lenIncr;
>>          for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>>              if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>                  return -1;
>>      }
>>      return len;
>> }
>>
>> Has anyone further ideas to improve this ?
> 
> How does it compare to the more straightforward:
> 
> std::size_t utf8Strlen(const char *str)
> {
>      std::size_t length = 0;
>      for(std::size_t index = 0; str[index]; ++index, ++length)
>          if((str[index] & 0xC0) == 0xC0)
>              while((str[index+1] & 0xC0) == 0x80)
>                  ++index;
>      return length;
> }

The issue with that solution is that it doesn't correctly detect
any kind of mis-formatted UTF-8-string. I get the number of chars
preceding a header-char from the table and check if there are an
according number of 0x80-headered chars.

[toc] | [prev] | [next] | [standalone]

#82751

Am 11.01.22 um 18:28 schrieb Bonita Montero:
> Am 11.01.2022 um 10:50 schrieb Juha Nieminen:
>> How does it compare to the more straightforward:
>>
>> std::size_t utf8Strlen(const char *str)
>> {
>>      std::size_t length = 0;
>>      for(std::size_t index = 0; str[index]; ++index, ++length)
>>          if((str[index] & 0xC0) == 0xC0)
>>              while((str[index+1] & 0xC0) == 0x80)
>>                  ++index;
>>      return length;
>> }
> 
> The issue with that solution is that it doesn't correctly detect
> any kind of mis-formatted UTF-8-string. I get the number of chars
> preceding a header-char from the table and check if there are an
> according number of 0x80-headered chars.
> 

I wrote this code once to check, if a string is valid UTF-8 - actually, 
I used this platform to test-drive it: 
https://leetcode.com/problems/utf-8-validation/ and it came off as the 
fastest solution handed in so far:

==================================================================
enum utf8token { utf8lowbyte = 1, utf8doublet = 2, utf8triplet = 3, 
utf8quadruplet = 4, utf8highbyte, utf8fail };

static utf8token utf8classify(unsigned char data) {
     if ((data & 0x80) == 0) { return utf8lowbyte; }
     if ((data & 0xC0) == 0x80) { return utf8highbyte;}
     if ((data & 0xE0) == 0xC0) { return utf8doublet; }
     if ((data & 0xF0) == 0xE0) { return utf8triplet; }
     if ((data & 0xF8) == 0xF0) { return utf8quadruplet; }
     return utf8fail;
}

static bool valid_utf8(const char* data, std::size_t dataSize) {
     for (std::size_t i = 0; i < dataSize; i++) {
         int codelength = utf8classify(static_cast<unsigned char>(data[i]));
         if (codelength == utf8highbyte || codelength == utf8fail)
             return false;

         for (int j = 1; j<codelength; j++) {
             // check for premature end of input
             i++;
             if (i >= dataSize) return false;

             if (utf8classify(static_cast<unsigned char>(data[i])) != 
utf8highbyte)
                 return false;
         }
     }

     return true;
}
==========================================================

It only returns true or false according to the problem definition, but I 
think you can easily rework it to count the number of characters. I 
believe all you have to do is increase a counter for every turn of the 
outer loop.

     Christian

[toc] | [prev] | [next] | [standalone]

#82752

Am 11.01.2022 um 18:41 schrieb Christian Gollwitzer:
> Am 11.01.22 um 18:28 schrieb Bonita Montero:
>> Am 11.01.2022 um 10:50 schrieb Juha Nieminen:
>>> How does it compare to the more straightforward:
>>>
>>> std::size_t utf8Strlen(const char *str)
>>> {
>>>      std::size_t length = 0;
>>>      for(std::size_t index = 0; str[index]; ++index, ++length)
>>>          if((str[index] & 0xC0) == 0xC0)
>>>              while((str[index+1] & 0xC0) == 0x80)
>>>                  ++index;
>>>      return length;
>>> }
>>
>> The issue with that solution is that it doesn't correctly detect
>> any kind of mis-formatted UTF-8-string. I get the number of chars
>> preceding a header-char from the table and check if there are an
>> according number of 0x80-headered chars.
>>
> 
> I wrote this code once to check, if a string is valid UTF-8 - actually, 
> I used this platform to test-drive it: 
> https://leetcode.com/problems/utf-8-validation/ and it came off as the 
> fastest solution handed in so far:
> 
> ==================================================================
> enum utf8token { utf8lowbyte = 1, utf8doublet = 2, utf8triplet = 3, 
> utf8quadruplet = 4, utf8highbyte, utf8fail };
> 
> static utf8token utf8classify(unsigned char data) {
>      if ((data & 0x80) == 0) { return utf8lowbyte; }
>      if ((data & 0xC0) == 0x80) { return utf8highbyte;}
>      if ((data & 0xE0) == 0xC0) { return utf8doublet; }
>      if ((data & 0xF0) == 0xE0) { return utf8triplet; }
>      if ((data & 0xF8) == 0xF0) { return utf8quadruplet; }
>      return utf8fail;
> }

Sorry, that makes a lot of unprecitible branches.
That's while I used a table.

[toc] | [prev] | [next] | [standalone]

#82754

On Tuesday, 11 January 2022 at 19:29:19 UTC+2, Bonita Montero wrote:
> Am 11.01.2022 um 10:50 schrieb Juha Nieminen: 
> > Bonita Montero <Bonita....@gmail.com> wrote: 
> >> I had an idea how to write a fast UTF-8 strlen, here it is: 
> >> 
> >> size_t utf8Strlen( char const *str ) 
> >> { 
> >> struct encode_t { size_t lenIncr, strIncr; }; 
> >> static encode_t const encodes[] = 
> >> { 
> >> { 1, 1 }, 
> >> { 0, 0 }, 
> >> { 1, 2 }, 
> >> { 1, 3 }, 
> >> { 1, 4 }, 
> >> { 0, 0 }, 
> >> { 0, 0 }, 
> >> { 0, 0 }, 
> >> { 0, 0 } 
> >> }; 
> >> size_t len = 0; 
> >> for( unsigned char c; (c = *str); ) 
> >> { 
> >> encode_t const &enc = encodes[(size_t)countl_zero<unsigned 
> >> char>( ~c )]; 
> >> if( !enc.lenIncr ) [[unlikely]] 
> >> return -1; 
> >> len += enc.lenIncr; 
> >> for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; ) 
> >> if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]] 
> >> return -1; 
> >> } 
> >> return len; 
> >> } 
> >> 
> >> Has anyone further ideas to improve this ? 
> > 
> > How does it compare to the more straightforward: 
> > 
> > std::size_t utf8Strlen(const char *str) 
> > { 
> > std::size_t length = 0; 
> > for(std::size_t index = 0; str[index]; ++index, ++length) 
> > if((str[index] & 0xC0) == 0xC0) 
> > while((str[index+1] & 0xC0) == 0x80) 
> > ++index; 
> > return length; 
> > }
> The issue with that solution is that it doesn't correctly detect 
> any kind of mis-formatted UTF-8-string. I get the number of chars 
> preceding a header-char from the table and check if there are an 
> according number of 0x80-headered chars.

Yes, your code indeed detects some possible errors in encoding,
but it does not detect overlong encodings and sequences that 
decode to an invalid code point. So both are only safe to use with
guaranteed clean data and with it the outcome is same.
 

[toc] | [prev] | [next] | [standalone]

#82753

I think that's even simpler:

size_t utf8Strlen( char const *str )
{
	static bool const isHeader[8] = { true, false, true, true, true, false, 
false, false };
	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
	size_t len = 0;
	for( unsigned char c; (c = *str); )
	{
		size_t headerClass = countl_zero<unsigned char>( ~c );
		if( !isHeader[headerClass] ) [[unlikely]]
			return -1;
		++len;
		for( char const *cpEnd = str + sizes[headerClass]; ++str != cpEnd; )
			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
				return -1;
	}
	return len;
}

[toc] | [prev] | [next] | [standalone]

#82755

The ultimately simple solution:

size_t utf8Strlen( char const *str )
{
	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
	size_t len = 0;
	for( unsigned char c; (c = *str); )
	{
		size_t size = sizes[countl_zero<unsigned char>( ~c )];
		if( !sizes ) [[unlikely]]
			return -1;
		++len;
		for( char const *cpEnd = str + size; ++str != cpEnd; )
			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
				return -1;
	}
	return len;
}

[toc] | [prev] | [next] | [standalone]

#82756

sizes instead of size; corrected:

size_t utf8Strlen( char const *str )
{
	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
	size_t len = 0;
	for( unsigned char c; (c = *str); )
	{
		size_t size = sizes[countl_zero<unsigned char>( ~c )];
		if( !size ) [[unlikely]]
			return -1;
		++len;
		for( char const *cpEnd = str + size; ++str != cpEnd; )
			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
				return -1;
	}
	return len;
}

[toc] | [prev] | [next] | [standalone]

#82757

Bonita Montero <Bonita.Montero@gmail.com> writes:

> sizes instead of size; corrected:
>
> size_t utf8Strlen( char const *str )
> {
> 	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
> 	size_t len = 0;
> 	for( unsigned char c; (c = *str); )
> 	{
> 		size_t size = sizes[countl_zero<unsigned char>( ~c )];
> 		if( !size ) [[unlikely]]
> 			return -1;
> 		++len;
> 		for( char const *cpEnd = str + size; ++str != cpEnd; )
> 			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
> 				return -1;
> 	}
> 	return len;
> }

You reject simpler solutions because they don't detect the one error you
have decided to look for.  There are other encoding errors that this
code won't catch.  Seems a bit arbitrary to me.  I'd want a fast
utf8-strlen for external strings that have been validated and for
strings internally generated by valid code, or a slower one that caught
all invalid encodings.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#82758

Am 12.01.2022 um 15:14 schrieb Ben Bacarisse:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
> 
>> sizes instead of size; corrected:
>>
>> size_t utf8Strlen( char const *str )
>> {
>> 	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
>> 	size_t len = 0;
>> 	for( unsigned char c; (c = *str); )
>> 	{
>> 		size_t size = sizes[countl_zero<unsigned char>( ~c )];
>> 		if( !size ) [[unlikely]]
>> 			return -1;
>> 		++len;
>> 		for( char const *cpEnd = str + size; ++str != cpEnd; )
>> 			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>> 				return -1;
>> 	}
>> 	return len;
>> }
> 
> You reject simpler solutions because they don't detect the one error you
> have decided to look for. ...

I think that's ok

> There are other encoding errors that this code won't catch.

Not at the UTF-8 level.

[toc] | [prev] | [next] | [standalone]

#82761

On Wednesday, January 12, 2022 at 11:20:55 AM UTC-5, Bonita Montero wrote:
> Am 12.01.2022 um 15:14 schrieb Ben Bacarisse: 
...
> > There are other encoding errors that this code won't catch.
> Not at the UTF-8 level.

"... it does not detect overlong encodings and sequences that decode to an
invalid code point." To what level do you assign those errors, if not at the
UTF-8 level? It's the specification of UTF-8 itself which identifies those as
errors.

[toc] | [prev] | [next] | [standalone]

#82762

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 12.01.2022 um 15:14 schrieb Ben Bacarisse:
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>> 
>>> sizes instead of size; corrected:
>>>
>>> size_t utf8Strlen( char const *str )
>>> {
>>> 	static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
>>> 	size_t len = 0;
>>> 	for( unsigned char c; (c = *str); )
>>> 	{
>>> 		size_t size = sizes[countl_zero<unsigned char>( ~c )];
>>> 		if( !size ) [[unlikely]]
>>> 			return -1;
>>> 		++len;
>>> 		for( char const *cpEnd = str + size; ++str != cpEnd; )
>>> 			if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>> 				return -1;
>>> 	}
>>> 	return len;
>>> }
>> You reject simpler solutions because they don't detect the one error you
>> have decided to look for. ...
>
> I think that's ok

Obviously.

>> There are other encoding errors that this code won't catch.
>
> Not at the UTF-8 level.

Not so.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#82784

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> sizes instead of size;  corrected:
>>
>> size_t utf8Strlen( char const *str )
>> {
>>   static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
>>   size_t len = 0;
>>   for( unsigned char c; (c = *str); )
>>   {
>>     size_t size = sizes[countl_zero<unsigned char>( ~c )];
>>     if( !size ) [[unlikely]]
>>       return -1;
>>     ++len;
>>     for( char const *cpEnd = str + size; ++str != cpEnd; )
>>       if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>         return -1;
>>   }
>>   return len;
>> }
>
> You reject simpler solutions because they don't detect the one error
> you have decided to look for.  There are other encoding errors that
> this code won't catch.  Seems a bit arbitrary to me.  [...]

I wouldn't say arbitrary.  The function verifies that its input is
syntactically well-formed while ignoring the question of whether it
is semantically well-formed.  That choice may not be an ideal choice but I
don't think it is an unreasonable one.

[toc] | [prev] | [next] | [standalone]

#82785

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Bonita Montero <Bonita.Montero@gmail.com> writes:
>
>> sizes instead of size;  corrected:
>>
>> size_t utf8Strlen( char const *str )
>> {
>>   static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
>>   size_t len = 0;
>>   for( unsigned char c; (c = *str); )
>>   {
>>     size_t size = sizes[countl_zero<unsigned char>( ~c )];
>>     if( !size ) [[unlikely]]
>>       return -1;
>>     ++len;
>>     for( char const *cpEnd = str + size; ++str != cpEnd; )
>>       if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>         return -1;
>>   }
>>   return len;
>> }
>
> You reject simpler solutions because they don't detect the one error
> you have decided to look for.  There are other encoding errors that
> this code won't catch.  Seems a bit arbitrary to me.  [...]

(Sorry, accidental send)

I wouldn't say arbitrary.  The function verifies that its input is
syntactically well-formed while ignoring the question of whether it
is semantically well-formed.  That choice may not be ideal but I
don't think it's totally unreasonable.

[toc] | [prev] | [next] | [standalone]

#82788

On Sunday, 16 January 2022 at 22:13:01 UTC+2, Tim Rentsch wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> writes: 
> 
> > Bonita Montero <Bonita....@gmail.com> writes: 
> > 
> >> sizes instead of size; corrected: 
> >> 
> >> size_t utf8Strlen( char const *str ) 
> >> { 
> >> static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 }; 
> >> size_t len = 0; 
> >> for( unsigned char c; (c = *str); ) 
> >> { 
> >> size_t size = sizes[countl_zero<unsigned char>( ~c )]; 
> >> if( !size ) [[unlikely]] 
> >> return -1; 
> >> ++len; 
> >> for( char const *cpEnd = str + size; ++str != cpEnd; ) 
> >> if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]] 
> >> return -1; 
> >> } 
> >> return len; 
> >> } 
> > 
> > You reject simpler solutions because they don't detect the one error 
> > you have decided to look for. There are other encoding errors that
> > this code won't catch. Seems a bit arbitrary to me. [...] 
> 
> (Sorry, accidental send)
> I wouldn't say arbitrary. The function verifies that its input is 
> syntactically well-formed while ignoring the question of whether it
> is semantically well-formed. That choice may not be ideal but I 
> don't think it's totally unreasonable.

With complicated syntax and semantics it makes sense
as the issues are easier to reason about in separation and the
expectations of users to diagnostics are also quite high. 

UTF-8 is usually produced by software. It takes not too lot of
code to detect all issues in it. Usually the symbol � is shown
as "diagnostic" for any issue in Unicode. Articles like that 
<https://arxiv.org/pdf/2010.03090.pdf> claim that whole
UTF-8 validation is doable with less than one instruction
per byte validated. 

So if some problem involving UTF-8 needs only half of error
checking then it is fair to expect it been said in problem
description. 

[toc] | [prev] | [next] | [standalone]

#82799

Tiib <ootiib@hot.ee> writes:

> On Sunday, 16 January 2022 at 22:13:01 UTC+2, Tim Rentsch wrote:
>
>> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>>
>>> Bonita Montero <Bonita....@gmail.com> writes:
>>>
>>>> sizes instead of size;  corrected:
>>>>
>>>> size_t utf8Strlen( char const *str )
>>>> {
>>>> static size_t const sizes[8] = { 1, 0, 2, 3, 4, 0, 0, 0 };
>>>> size_t len = 0;
>>>> for( unsigned char c; (c = *str); )
>>>> {
>>>> size_t size = sizes[countl_zero<unsigned char>( ~c )];
>>>> if( !size ) [[unlikely]]
>>>> return -1;
>>>> ++len;
>>>> for( char const *cpEnd = str + size; ++str != cpEnd; )
>>>> if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>>> return -1;
>>>> }
>>>> return len;
>>>> }
>>>
>>> You reject simpler solutions because they don't detect the one error
>>> you have decided to look for.  There are other encoding errors that
>>> this code won't catch.  Seems a bit arbitrary to me.  [...]
>>
>> (Sorry, accidental send)
>> I wouldn't say arbitrary.  The function verifies that its input is
>> syntactically well-formed while ignoring the question of whether it
>> is semantically well-formed.  That choice may not be ideal but I
>> don't think it's totally unreasonable.
>
> With complicated syntax and semantics it makes sense
> as the issues are easier to reason about in separation and the
> expectations of users to diagnostics are also quite high.
>
> UTF-8 is usually produced by software.  It takes not too lot of
> code to detect all issues in it.  Usually the symbol ? is shown
> as "diagnostic" for any issue in Unicode. [...]
>
> So if some problem involving UTF-8 needs only half of error
> checking then it is fair to expect it been said in problem
> description.

Yes, I know you have no shortage of strong opinions.

[toc] | [prev] | [next] | [standalone]

#82802

Bonita Montero <Bonita.Montero@gmail.com> writes:

> I had an idea how to write a fast UTF-8 strlen, here it is:
>
> size_t utf8Strlen( char const *str )
> {
>     struct encode_t { size_t lenIncr, strIncr; };
>     static encode_t const encodes[] =
>     {
>         { 1, 1 },
>         { 0, 0 },
>         { 1, 2 },
>         { 1, 3 },
>         { 1, 4 },
>         { 0, 0 },
>         { 0, 0 },
>         { 0, 0 },
>         { 0, 0 }
>     };
>     size_t len = 0;
>     for( unsigned char c; (c = *str); )
>     {
>         encode_t const &enc =
>            encodes[(size_t)countl_zero<unsigned char>( ~c )];
>         if( !enc.lenIncr ) [[unlikely]]
>             return -1;
>         len += enc.lenIncr;
>         for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>             if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>                 return -1;
>     }
>     return len;
> }
>
> Has anyone further ideas to improve this ?

Just for fun -

size_t
utf8_units_two( const char *s ){
    size_t r = -1;
    unsigned char c;

  next:
    switch(  r++,  c = *s++,  c >> 3  ){
	cases(16,17,18,19,20,21,22,23,31):			return  -1;

	cases(30):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
	cases(28,29):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
	cases(24,25,26,27):	if(  c = *s++,  c >> 6 != 2  )	return  -1;
	cases(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15):		goto  next;

	cases(0):		if(  c != 0  )			goto  next;
    }

    return  r;
}


(Note:  the cases() macro produces one 'case X:' for each
argument X except the last one where the ':' is omitted,
written using the standard C preprocessor, and left as an
exercise for any ambitious readers.)

Incidentally, this code provides the only example I remember
where using 'goto' is pretty much unavoidable, in that any
re-writing without 'goto' seems awkward or inferior in some
other way.  I guess I should say, at least not that I could
find, maybe someone else can do better.

This code also has the interesting property that along the main
code path there are no conditional branches (as compiled by gcc
under -O2).

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web