Los caracteres deben codificarse en bits de alguna manera. La mayoría de las cadenas en Internet, incluida esta publicación en Habré, están codificadas en UTF-8. El formato UTF-8 representa "caracteres" en uno, dos, tres o cuatro bytes. Esta es una generalización del estándar ASCII, que usa solo un byte por carácter. Es decir, la cadena ASCII también es una cadena UTF-8.
En realidad, es un poco más complicado porque técnicamente UTF-8 describe puntos de código. Un carácter visible como un emoji puede constar de varios puntos de código ... pero la mayoría de los programadores no necesitan estas palabras pedantes.
También hay otros estándares. Algunos lenguajes de programación más antiguos como C # y Java se basan en UTF-16. Utiliza dos o cuatro bytes por carácter. Parecía una buena idea en ese momento, pero ahora el consenso se está moviendo hacia el uso de UTF-8 en cualquier momento y en cualquier lugar.
La mayoría de las codificaciones tienen restricciones aplicables. En otras palabras, ninguna secuencia aleatoria de bits puede entrar en UTF-8. Por lo tanto, debe validar las cadenas; verifique que realmente sea UTF-8.
¿Que importa? Excelente. Por ejemplo, el servidor web de Microsoft tiene tal vulnerabilidad: acepta un URI que parece ser válido y seguro, pero cuando es interpretado por el servidor, le da al atacante acceso remoto al disco. Incluso dejando de lado las preocupaciones de seguridad, es casi seguro que no desee almacenar filas no válidas en su base de datos.
Por lo tanto, los lenguajes de programación, los servidores web, los navegadores y los motores de base de datos están validando constantemente UTF-8.
Si sus cadenas son en su mayoría ASCII, entonces las verificaciones son bastante rápidas y la verificación UTF-8 no es un problema. Atrás quedaron los días en que la mayoría de las cadenas estaban codificadas en ASCII. Vivimos en un mundo de emojis y muchos alfabetos nacionales.
En 2018, me pregunté:¿ Qué tan rápido se pueden validar las cadenas UTF-8 ? En ese momento, encontré una opción de validación con varios ciclos de CPU por símbolo. Uno podría calmarse con esto, pero esta respuesta no me satisfizo.
El trabajo llevó años, pero parece que ahora tenemos una versión cercana a la ideal. El nuevo algoritmo es un orden de magnitud más rápido que otras opciones de búsqueda rápida. Hemos preparado un informe técnico : "Validación UTF-8 en menos de una instrucción por byte" (que se publicará en Software: Practice and Experience ) y también se publicó una utilidad de evaluación comparativa .
Todos los detalles se explican en un artículo científico, por lo que no entraremos en detalles aquí, solo consideraremos brevemente la esencia. La parte principal de la validación de UTF-8 se realiza buscando pares de bytes consecutivos. Después de verificar todos los pares de bytes e identificar las posibles violaciones que se pueden encontrar a partir de esta información, queda relativamente poco por hacer.
Todos los procesadores tienen instrucciones SIMD rápidas. Trabajan con registros amplios (128 bits, 256 bits, etc.). La mayoría de los conjuntos tienen una instrucción de "búsqueda vectorizada" que toma, digamos, valores de 16 bytes (que van de 0 a 16) y los busca en una tabla de 16 bytes. En procesadores Intel y AMD, esta descripción corresponde a la instrucción
pshufb... Un valor entre 0 y 16 a veces se denomina nibble y abarca 4 bits. El byte se compone de dos nibble (bajo y alto).
En nuestro algoritmo de búsqueda, la instrucción de búsqueda vectorizada se llama tres veces: una para un nibble bajo, una vez para un nibble alto y una vez para un nibble alto para el siguiente byte. Tenemos tres tablas de búsqueda de 16 bytes correspondientes. Si los elige correctamente, el AND bit a bit de las tres búsquedas encuentra cualquier error.
Consulte el artículo científico para obtener más detalles , pero en última instancia, la validación UTF-8 casi completa se realiza con solo cinco líneas de código C ++ rápido sin ramificaciones ... y esas cinco líneas verifican bloques de hasta 32 bytes a la vez ...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Si bien no es obvio de inmediato, esta validación es suficiente y 100% segura. Realmente lo es . Solo quedan unos pocos pasos técnicos adicionales económicos.
Como resultado, en los procesadores Intel / AMD recientes, se necesita un poco menos de una instrucción por byte para verificar incluso la entrada aleatoria más basura. Dado que el código está extremadamente optimizado, puede ir hasta tres instrucciones por ciclo, e incluso más. Es decir, usamos una pequeña parte del ciclo (menos de un tercio) por byte de entrada en una CPU moderna. Por tanto, la velocidad de procesamiento se mantiene de forma fiable a más de 12 GB / s.
La lección es que las tablas de búsqueda regulares son útiles, pero las tablas vectorizadas son los bloques de construcción fundamentales para los algoritmos de alta velocidad.
Si necesita utilizar la función de validación rápida UTF-8 en producción, le recomendamos la biblioteca simdjson (versión 0.5 o superior). Está bien probado y tiene funciones integradas útiles, como el despacho en tiempo de ejecución. Aunque la biblioteca está diseñada para analizar JSON, puede usarla únicamente para la validación UTF-8, incluso si no hay JSON en absoluto. Admite procesadores ARM de 64 bits y x64, y también tiene procesamiento de reserva para otras CPU. Lo empaquetamos en un archivo de encabezado junto con un archivo de origen; para que pueda ponerlo en su proyecto C ++.
Trabajo previo... El principal mérito de popularizar el método de clasificación vectorizado, clave del algoritmo de búsqueda, es de Mula. Hasta donde yo sé, Keizer fue el primero en proponer nuestra estrategia de búsqueda triple. El primer algoritmo práctico de validación UTF-8 basado en SIMD fue creado por K. Willets. Varias personas, incluido Z. Wegner, hicieron mejoras en él. A Travis Downs se le ocurrieron ideas inteligentes sobre cómo acelerar los algoritmos convencionales.
Leer más . Si disfruta de este trabajo, es posible que le gusten otros artículos sobre temas relacionados: "Codificación y decodificación de Base64 a una velocidad casi de copia en memoria" (Software: práctica y experiencia, 50 (2), 2020) y "Análisis de gigabytes de JSON por segundo" ( Revista VLDB, 28 (6), 2019).