¿Cómo invierto una cadena UTF-8 en su lugar?

Question

Recientemente, alguien preguntó acerca de algorithm for reversing a string in place in C. La mayoría de las soluciones propuestas tenían problemas cuando se trata de cadenas que no son de un solo byte. Entonces, me preguntaba qué podría ser un buen algoritmo para tratar específicamente con cadenas de utf-8.

Se me ocurrió algo de código, que estoy publicando como respuesta, pero estaría encantado de ver las ideas o sugerencias de otras personas. Preferí usar el código actual, así que elegí C#, ya que parece ser uno de los idiomas más populares en este sitio, pero no me importa si tu código está en otro idioma, siempre que pueda ser razonable. entendido por cualquiera que esté familiarizado con un lenguaje imperativo. Y, como esto pretende ver cómo un algoritmo de este tipo podría implementarse a bajo nivel (por bajo nivel, me refiero a tratar con bytes), la idea es evitar el uso de bibliotecas para el código central.

Notas:

Estoy interesado en el propio algoritmo, su rendimiento y como no podía ser optimizado (me refiero a la optimización a nivel de algoritmo, no reemplazar i ++ ++ con I y tal, yo soy tampoco está realmente interesado en los puntos de referencia reales).

No me refiero a usarlo realmente en el código de producción o "reinventar la rueda". Esto es solo por curiosidad y como ejercicio.

Estoy usando matrices de bytes C, así que supongo que puedes obtener la longitud de la cadena sin ejecutar la cadena hasta que encuentres una NUL. Es decir, no estoy explicando la complejidad de encontrar la longitud de la cadena. Pero si estás usando C, por ejemplo, puedes factorizarlo usando strlen() antes de llamar al código central.

Editar:

Como Mike F señala, mi código (y el código de otras personas publicado aquí) no está tratando con caracteres compuestos. Algo de información sobre esos here. No estoy familiarizado con el concepto, pero si eso significa que hay "caracteres combinados", es decir, caracteres/puntos de código que solo son válidos en combinación con otros caracteres/puntos de código "base", una tabla de consulta de tales los caracteres se pueden usar para conservar el orden del carácter "global" ("base" + "combinación" de caracteres) al invertir.

Answer 1

Haría una pasada al invertir los bytes, luego una segunda pasada que invierte los bytes en cualquier carácter multibyte (que se detectan fácilmente en UTF8) de nuevo a su orden correcto.

Definitivamente puede manejar esto en línea en una sola pasada, pero no me molestaría a menos que la rutina se convirtiera en un cuello de botella.

Answer 2

Mi planteamiento inicial podría resumirse de esta manera por:

1) bytes inversas ingenuamente

2) Ejecutar la cadena hacia atrás y corregir las secuencias utf8 a medida que avanza.

Las secuencias ilegales se tratan en el segundo paso y en el primer paso, verificamos si la cadena está en "sincronización" (es decir, si comienza con un byte líder legal).

EDIT: mejora de la validación de dirigir byte en reversa()

class UTF8Utils { 


    public static void Reverse(byte[] str) { 
     int len = str.Length; 
     int i = 0; 
     int j = len - 1; 

     // first, check if the string is "synced", i.e., it starts 
     // with a valid leading character. Will check for illegal 
     // sequences thru the whole string later. 
     byte leadChar = str[0]; 

     // if it starts with 10xx xxx, it's a trailing char... 
     // if it starts with 1111 10xx or 1111 110x 
     // it's out of the 4 bytes range. 
    // EDIT: added validation for 7 bytes seq and 0xff 
     if((leadChar & 0xc0) == 0x80 || 
      (leadChar & 0xfc) == 0xf8 || 
      (leadChar & 0xfe) == 0xfc || 
     (leadChar & 0xff) == 0xfe || 
     leadChar == 0xff) { 

      throw new Exception("Illegal UTF-8 sequence"); 

     } 

     // reverse bytes in-place naïvely 
     while(i < j) { 
      byte tmp = str[i]; 
      str[i] = str[j]; 
      str[j] = tmp; 
      i++; 
      j--; 
     } 
     // now, run the string again to fix the multibyte sequences 
     UTF8Utils.ReverseMbSequences(str); 

    } 

    private static void ReverseMbSequences(byte[] str) { 
     int i = str.Length - 1; 
     byte leadChar = 0; 
     int nBytes = 0; 

     // loop backwards thru the reversed buffer 
     while(i >= 0) { 
      // since the first byte in the unreversed buffer is assumed to be 
      // the leading char of that byte, it seems safe to assume that the 
      // last byte is now the leading char. (Given that the string is 
      // not out of sync -- we checked that out already) 
      leadChar = str[i]; 

      // check how many bytes this sequence takes and validate against 
      // illegal sequences 
      if(leadChar < 0x80) { 
       nBytes = 1; 
      } else if((leadChar & 0xe0) == 0xc0) { 
       if((str[i-1] & 0xc0) != 0x80) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 2; 
      } else if ((leadChar & 0xf0) == 0xe0) { 
       if((str[i-1] & 0xc0) != 0x80 || 
        (str[i-2] & 0xc0) != 0x80) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 3; 
      } else if ((leadChar & 0xf8) == 0xf0) { 
       if((str[i-1] & 0xc0) != 0x80 || 
        (str[i-2] & 0xc0) != 0x80 || 
        (str[i-3] & 0xc0) != 0x80 ) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 4; 
      } else { 
       throw new Exception("Illegal UTF-8 sequence"); 
      } 

      // now, reverse the current sequence and then continue 
      // whith the next one 
      int back = i; 
      int front = back - nBytes + 1; 

      while(front < back) { 
       byte tmp = str[front]; 
       str[front] = str[back]; 
       str[back] = tmp; 
       front++; 
       back--; 
      } 
      i -= nBytes; 
     } 
    } 
} 

Answer 3

La mejor solución:

1. Convertir a una amplia cadena de carbón
2. Invertir la nueva cadena

Nunca, nunca, nunca, nunca trate bytes únicos como caracteres.

Answer 4

De acuerdo en que su enfoque es la única manera sensata de hacerlo en el lugar.

Personalmente, no me gusta revalidar UTF8 dentro de cada función que se ocupa de él, y generalmente solo hago lo que se necesita para evitar bloqueos; agrega mucho menos código. Dunno mucho C# así que aquí está en C:

(editado para eliminar STRLEN)

void reverse(char *start, char *end) 
{ 
    while(start < end) 
    { 
     char c = *start; 
     *start++ = *end; 
     *end-- = c; 
    } 
} 

char *reverse_char(char *start) 
{ 
    char *end = start; 
    while((end[1] & 0xC0) == 0x80) end++; 
    reverse(start, end); 
    return(end+1); 
} 

void reverse_string(char *string) 
{ 
    char *end = string; 
    while(*end) end = reverse_char(end); 
    reverse(string, end-1); 
} 

Answer 5

Este código se supone que la entrada de UTF-8 cadena es válida y bien formadas (es decir, en la mayoría de 4 bytes por varios bytes de caracteres):

#include "string.h" 

void utf8rev(char *str) 
{ 
    /* this assumes that str is valid UTF-8 */ 
    char *scanl, *scanr, *scanr2, c; 

    /* first reverse the string */ 
    for (scanl= str, scanr= str + strlen(str); scanl < scanr;) 
     c= *scanl, *scanl++= *--scanr, *scanr= c; 

    /* then scan all bytes and reverse each multibyte character */ 
    for (scanl= scanr= str; c= *scanr++;) { 
     if ((c & 0x80) == 0) // ASCII char 
      scanl= scanr; 
     else if ((c & 0xc0) == 0xc0) { // start of multibyte 
      scanr2= scanr; 
      switch (scanr - scanl) { 
       case 4: c= *scanl, *scanl++= *--scanr, *scanr= c; // fallthrough 
       case 3: // fallthrough 
       case 2: c= *scanl, *scanl++= *--scanr, *scanr= c; 
      } 
      scanr= scanl= scanr2; 
     } 
    } 
} 

// quick and dirty main for testing purposes 
#include "stdio.h" 

int main(int argc, char* argv[]) 
{ 
    char buffer[256]; 
    buffer[sizeof(buffer)-1]= '\0'; 

    while (--argc > 0) { 
     strncpy(buffer, argv[argc], sizeof(buffer)-1); // don't overwrite final null 
     printf("%s → ", buffer); 
     utf8rev(buffer); 
     printf("%s\n", buffer); 
    } 
    return 0; 
} 

Si compila este programa (ejemplo nombre: so199260.c) y ejecutarlo en un entorno UTF-8 (una instalación de Linux en este caso):

$ so199260 γεια και χαρά français АДЖИ a♠♡♢♣b 
a♠♡♢♣b → b♣♢♡♠a 
АДЖИ → ИЖДА 
français → siaçnarf 
χαρά → άραχ 
και → ιακ 
γεια → αιεγ 

Si el código es demasiado críptico, con mucho gusto lo aclararé.