ejercicio char[] a cadena hexadecimal
https://stackoverflow.com/questions/69115
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
A continuación se muestra mi función actual de cadena char* a hexadecimal.Lo escribí como un ejercicio de manipulación de bits.Se necesitan ~7 ms en un AMD Athlon MP 2800+ para hexificar una matriz de 10 millones de bytes.¿Hay algún truco u otra forma que me falta?
¿Cómo puedo hacer esto más rápido?
Compilado con -O3 en g++
static const char _hex2asciiU_value[256][2] =
{ {'0','0'}, {'0','1'}, /* snip..., */ {'F','E'},{'F','F'} };
std::string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
std::string str;
str.resize(_len*2);
char* pszHex = &str[0];
const unsigned char* pEnd = _pArray + _len;
clock_t stick, etick;
stick = clock();
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
pszHex[0] = _hex2asciiU_value[*pChar][0];
pszHex[1] = _hex2asciiU_value[*pChar][1];
}
etick = clock();
std::cout << "ticks to hexify " << etick - stick << std::endl;
return str;
}
Actualizaciones
Código de tiempo agregado
Brian R.Bondy:reemplace std::string con un búfer asignado al montón y cambie ofs*16 a ofs << 4; sin embargo, ¿el búfer asignado al montón parece ralentizarlo?- resultado ~11ms
Antti Sykäri:reemplace el bucle interior con
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
resultado ~8ms
Roberto:reemplazar _hex2asciiU_value con una tabla completa de 256 entradas, sacrificando espacio de memoria pero con un resultado de ~7ms.
hoyhoy:Noté que estaba produciendo resultados incorrectos.
Solución
A costa de más memoria, puede crear una tabla completa de 256 entradas de códigos hexadecimales:
static const char _hex2asciiU_value[256][2] =
{ {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };
Luego, dirija el índice a la tabla, sin necesidad de manipular un poco.
const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];
Otros consejos
Esta función de ensamblaje (basada en mi publicación anterior aquí, pero tuve que modificar un poco el concepto para que realmente funcionara) procesa 3,3 mil millones de caracteres de entrada por segundo (6,6 mil millones de caracteres de salida) en un núcleo de un Core 2 Conroe 3Ghz.Penryn probablemente sea más rápido.
%include "x86inc.asm"
SECTION_RODATA
pb_f0: times 16 db 0xf0
pb_0f: times 16 db 0x0f
pb_hex: db 48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70
SECTION .text
; int convert_string_to_hex( char *input, char *output, int len )
cglobal _convert_string_to_hex,3,3
movdqa xmm6, [pb_f0 GLOBAL]
movdqa xmm7, [pb_0f GLOBAL]
.loop:
movdqa xmm5, [pb_hex GLOBAL]
movdqa xmm4, [pb_hex GLOBAL]
movq xmm0, [r0+r2-8]
movq xmm2, [r0+r2-16]
movq xmm1, xmm0
movq xmm3, xmm2
pand xmm0, xmm6 ;high bits
pand xmm2, xmm6
psrlq xmm0, 4
psrlq xmm2, 4
pand xmm1, xmm7 ;low bits
pand xmm3, xmm7
punpcklbw xmm0, xmm1
punpcklbw xmm2, xmm3
pshufb xmm4, xmm0
pshufb xmm5, xmm2
movdqa [r1+r2*2-16], xmm4
movdqa [r1+r2*2-32], xmm5
sub r2, 16
jg .loop
REP_RET
Tenga en cuenta que utiliza sintaxis ensambladora x264, lo que lo hace más portátil (a 32 bits frente a 64 bits, etc.).Convertir esto a la sintaxis de su elección es trivial:r0, r1, r2 son los tres argumentos de las funciones en los registros.Es un poco como un pseudocódigo.O simplemente puede obtener common/x86/x86inc.asm del árbol x264 e incluirlo para ejecutarlo de forma nativa.
PDStack Overflow, ¿me equivoco al perder el tiempo en algo tan trivial?¿O es esto asombroso?
Implementación de C más rápida
Esto se ejecuta casi 3 veces más rápido que la implementación de C++.No estoy seguro de por qué, ya que es bastante similar.Para la última implementación de C++ que publiqué, tomó 6,8 segundos ejecutar una matriz de 200.000.000 de caracteres.La implementación tomó sólo 2,2 segundos.
#include <stdio.h>
#include <stdlib.h>
char* char_to_hex(const unsigned char* p_array,
unsigned int p_array_len,
char** hex2ascii)
{
unsigned char* str = malloc(p_array_len*2+1);
const unsigned char* p_end = p_array + p_array_len;
size_t pos=0;
const unsigned char* p;
for( p = p_array; p != p_end; p++, pos+=2 ) {
str[pos] = hex2ascii[*p][0];
str[pos+1] = hex2ascii[*p][1];
}
return (char*)str;
}
int main()
{
size_t hex2ascii_len = 256;
char** hex2ascii;
int i;
hex2ascii = malloc(hex2ascii_len*sizeof(char*));
for(i=0; i<hex2ascii_len; i++) {
hex2ascii[i] = malloc(3*sizeof(char));
snprintf(hex2ascii[i], 3,"%02X", i);
}
size_t len = 8;
const unsigned char a[] = "DO NOT WANT";
printf("%s\n", char_to_hex((const unsigned char*)a, len, (char**)hex2ascii));
}
Opere con 32 bits a la vez (4 caracteres), luego ocúpese de la cola si es necesario.Cuando hice este ejercicio con codificación de URL, una búsqueda completa en la tabla para cada carácter fue un poco más rápida que las construcciones lógicas, por lo que es posible que quieras probar esto en contexto también para tener en cuenta los problemas de almacenamiento en caché.
Me funciona con unsigned char:
unsigned char c1 = byteVal >> 4;
unsigned char c2 = byteVal & 0x0f;
c1 += c1 <= 9 ? '0' : ('a' - 10);
c2 += c2 <= 9 ? '0' : ('a' - 10);
std::string sHex(" ");
sHex[0] = c1 ;
sHex[1] = c2 ;
//sHex - contain what we need. For example "0f"
Por un lado, en lugar de multiplicar por 16 hacer un bitshift << 4
Tampoco utilices el std::string, en su lugar simplemente cree un búfer en el montón y luego delete él.Será más eficiente que la destrucción del objeto que se necesita desde la cadena.
no va a hacer mucha diferencia...*pChar-(ofs*16) se puede hacer con [*pCHar & 0x0F]
Esta es mi versión, que, a diferencia de la versión del OP, no asume que std::basic_string tiene sus datos en la región contigua:
#include <string>
using std::string;
static char const* digits("0123456789ABCDEF");
string
tohex(string const& data)
{
string result(data.size() * 2, 0);
string::iterator ptr(result.begin());
for (string::const_iterator cur(data.begin()), end(data.end()); cur != end; ++cur) {
unsigned char c(*cur);
*ptr++ = digits[c >> 4];
*ptr++ = digits[c & 15];
}
return result;
}
Supongo que esto es Windows+IA32.
Intente utilizar short int en lugar de las dos letras hexadecimales.
short int hex_table[256] = {'0'*256+'0', '1'*256+'0', '2'*256+'0', ..., 'E'*256+'F', 'F'*256+'F'};
unsigned short int* pszHex = &str[0];
stick = clock();
for (const unsigned char* pChar = _pArray; pChar != pEnd; pChar++)
*pszHex++ = hex_table[*pChar];
etick = clock();
Cambiando
ofs = *pChar >> 4;
pszHex[0] = pHex[ofs];
pszHex[1] = pHex[*pChar-(ofs*16)];
a
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
da como resultado aproximadamente un 5% de aceleración.
Escribir el resultado dos bytes a la vez como lo sugiere Roberto da como resultado aproximadamente un 18% de aceleración.El código cambia a:
_result.resize(_len*2);
short* pszHex = (short*) &_result[0];
const unsigned char* pEnd = _pArray + _len;
const char* pHex = _hex2asciiU_value;
for(const unsigned char* pChar = _pArray;
pChar != pEnd;
pChar++, ++pszHex )
{
*pszHex = bytes_to_chars[*pChar];
}
Inicialización requerida:
short short_table[256];
for (int i = 0; i < 256; ++i)
{
char* pc = (char*) &short_table[i];
pc[0] = _hex2asciiU_value[i >> 4];
pc[1] = _hex2asciiU_value[i & 0x0f];
}
Hacerlo 2 bytes a la vez o 4 bytes a la vez probablemente dará como resultado aceleraciones aún mayores, como lo señala Allan viento, pero luego se vuelve más complicado cuando tienes que lidiar con personajes extraños.
Si te sientes aventurero, puedes intentar adaptarte. El dispositivo de Duff. para hacer esto.
Los resultados están en un procesador Intel Core Duo 2 y gcc -O3.
Mide siempre que en realidad se obtienen resultados más rápidos: una pesimización que pretende ser una optimización no tiene ningún valor.
Siempre prueba que obtenga los resultados correctos: un error que pretende ser una optimización es francamente peligroso.
Y siempre ten en cuenta el equilibrio entre velocidad y legibilidad: la vida es demasiado corta para que cualquiera pueda mantener un código ilegible.
(Referencia obligatoria a codificar para el psicópata violento que sabe dónde vives.)
Asegúrese de que la optimización de su compilador esté activada al nivel de trabajo más alto.
Ya sabes, banderas como '-O1' a '-03' en gcc.
Descubrí que usar un índice en una matriz, en lugar de un puntero, puede acelerar las cosas.Todo depende de cómo elija optimizar su compilador.La clave es que el procesador tiene instrucciones para hacer cosas complejas como [i*2+1] en una sola instrucción.
Si estás bastante obsesionado con la velocidad aquí, puedes hacer lo siguiente:
Cada carácter es un byte y representa dos valores hexadecimales.Por tanto, cada carácter son en realidad dos valores de cuatro bits.
Entonces, puedes hacer lo siguiente:
- Desempaquete los valores de cuatro bits en valores de 8 bits usando una multiplicación o una instrucción similar.
- Utilice pshufb, la instrucción SSSE3 (aunque solo para Core2).Toma una matriz de 16 valores de entrada de 8 bits y los mezcla según los 16 índices de 8 bits en un segundo vector.Como sólo tienes 16 personajes posibles, esto encaja perfectamente;la matriz de entrada es un vector de caracteres del 0 al F, y la matriz de índice es la matriz desempaquetada de valores de 4 bits.
Así, en un instrucción única, habrás realizado 16 búsquedas de tablas en menos relojes de los que normalmente se necesitan para hacer solo uno (pshufb tiene una latencia de 1 reloj en Penryn).
Entonces, en pasos computacionales:
- A B C D E F G H I J K L M N O P (vector de valores de entrada de 64 bits, "Vector A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (vector de índices de 128 bits, "Vector B").La forma más sencilla es probablemente dos multiplicaciones de 64 bits.
- pshub [0123456789ABCDEF], vector B
No estoy seguro de que hacerlo con más bytes a la vez sea mejor...probablemente obtendrá toneladas de errores de caché y lo ralentizará significativamente.
Sin embargo, lo que podría intentar es desenrollar el bucle, dar pasos más grandes y hacer más caracteres cada vez a través del bucle, para eliminar parte de la sobrecarga del bucle.
Obteniendo constantemente ~4ms en mi Athlon 64 4200+ (~7ms con el código original)
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
const char* pchars = _hex2asciiU_value[*pChar];
*pszHex++ = *pchars++;
*pszHex++ = *pchars;
}
La función tal como se muestra cuando escribo esto produce una salida incorrecta incluso cuando _hex2asciiU_value está completamente especificado.El siguiente código funciona y en mi Macbook Pro de 2,33 GHz se ejecuta en aproximadamente 1,9 segundos para 200.000.000 millones de caracteres.
#include <iostream>
using namespace std;
static const size_t _h2alen = 256;
static char _hex2asciiU_value[_h2alen][3];
string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
string str;
str.resize(_len*2);
char* pszHex = &str[0];
const unsigned char* pEnd = _pArray + _len;
const char* pHex = _hex2asciiU_value[0];
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
pszHex[0] = _hex2asciiU_value[*pChar][0];
pszHex[1] = _hex2asciiU_value[*pChar][1];
}
return str;
}
int main() {
for(int i=0; i<_h2alen; i++) {
snprintf(_hex2asciiU_value[i], 3,"%02X", i);
}
size_t len = 200000000;
char* a = new char[len];
string t1;
string t2;
clock_t start;
srand(time(NULL));
for(int i=0; i<len; i++) a[i] = rand()&0xFF;
start = clock();
t1=char_to_hex((const unsigned char*)a, len);
cout << "char_to_hex conversion took ---> " << (clock() - start)/(double)CLOCKS_PER_SEC << " seconds\n";
}
