char [], um Hex-String Übung

StackOverflow https://stackoverflow.com/questions/69115

  •  09-06-2019
  •  | 
  •  

Frage

Im Folgenden finden Sie meine aktuellen char * zu Hex-String-Funktion. Ich schrieb es als eine Übung in Bit-Manipulation. Es dauert ~ 7ms auf einem AMD Athlon MP 2800+ einen 10 Millionen Byte-Array hexify. Gibt es einen Trick oder eine andere Art und Weise, die ich fehle?

Wie kann ich das schneller machen?

Zusammengestellt mit O3 in 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;
}

Updates

Added Timing Code

Brian R. Bondy : Ersetzen Sie die std :: string mit einem Heap alloc'd Puffer und ofs ändern * 16 bis ofs << 4 - aber der Heap zugewiesenen Puffer es zu langsam scheint nach unten? - Ergebnis ~ 11ms

Antti Sykäri : ersetzen innere Schleife mit 

 int upper = *pChar >> 4;
 int lower = *pChar & 0x0f;
 pszHex[0] = pHex[upper];
 pszHex[1] = pHex[lower];

Ergebnis ~ 8ms

Robert : ersetzen _hex2asciiU_value mit einer vollen 256-Eintragstabelle, Speicherraum zu opfern, sondern Ergebnis ~ 7ms !

HoyHoy : Notiert es falsche Ergebnisse produziert

War es hilfreich?

Lösung

Auf Kosten von mehr Speicher können Sie eine vollständige 256-Eintragstabelle der Hex-Codes erstellen: 

static const char _hex2asciiU_value[256][2] =
    { {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };

Dann direkter Index in die Tabelle, das Hantieren kein Bit erforderlich. 

const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];

Andere Tipps

Diese Baugruppe Funktion (basierend hier meinen vorherigen Post ab, aber ich hatte das Konzept ein wenig zu ändern, um es tatsächlich die Arbeit an) verarbeitet 3,3 Milliarden Eingänge Zeichen pro Sekunde (6,6 Milliarden ausgegebenen Zeichen) auf einem Kern eines Core 2 Conroe 3Ghz. Penryn ist wahrscheinlich schneller. 

%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

Beachten Sie es x264 Montage-Syntax verwendet, die es mehr tragbar (32-Bit vs 64-Bit, etc.) macht. So wandeln diese in die Syntax Ihrer Wahl ist trivial: r0, r1, r2 sind die drei Argumente an die Funktionen in den Registern. Es ist ein bisschen wie Pseudo-Code. Oder Sie können einfach erhalten common / x86 / x86inc.asm vom x264 Baum und beinhalten, dass es nativ ausgeführt werden.

P. S. Stack-Überlauf, bin ich falsch für die Zeit auf eine solche triviale Sache zu verschwenden? Oder ist das genial?

Schneller C implmentation

Das läuft fast 3x schneller als die C ++ Implementierung. Nicht sicher, warum, wie es ziemlich ähnlich ist. Für die letzte C ++ Implementierung, die ich gepostet es dauerte 6,8 Sekunden durch ein 200.000.000 Zeichenfeld laufen. Die Umsetzung dauerte nur 2,2 Sekunden. 

#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));
}

eingeben Bild Beschreibung hier

Operate auf 32 Bits zu einem Zeitpunkt (4 Zeichen), dann mit dem Schwanz umgehen, wenn nötig. Als ich diese Übung mit tat URL-Codierung eine vollständige Tabellensuche für jeden char war etwas schneller als logische Konstrukte, so dass Sie auch in Zusammenhang mögen dies testen Caching-Probleme zu berücksichtigen.

Es funktioniert für mich mit 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"

Für eine statt durch 16 Multiplikation eines bitshift << 4 tun

Auch benutzen Sie nicht die std::string, erstellen, anstatt nur einen Puffer auf dem Heap und delete es dann. Es wird effizienter als das Objekt der Zerstörung, die aus der Zeichenfolge benötigt wird.

wird nicht viel Unterschied machen ... * pChar- (ofs * 16) kann mit [* pChar & 0x0F]

erfolgen

Dies ist meine Version, die, im Gegensatz zu der Version des OP, geht nicht davon aus, dass std::basic_string seine Daten in zusammenhängendem Bereich hat: 

#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;
}

Ich nehme an, dies ist die Windows + IA32.
Versuchen Sie short int anstelle der beiden hexadezimalen Buchstaben zu verwenden. 

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();

Ändern 

    ofs = *pChar >> 4;
    pszHex[0] = pHex[ofs];
    pszHex[1] = pHex[*pChar-(ofs*16)];


    int upper = *pChar >> 4;
    int lower = *pChar & 0x0f;
    pszHex[0] = pHex[upper];
    pszHex[1] = pHex[lower];

Ergebnisse in etwa 5% Speedup.

Das Schreiben das Ergebnis zwei Bytes zum Zeitpunkt wie von Robert Ergebnisse legten nahe, in etwa 18% Speedup. Der Code ändert sich an: 

_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];
}

Erforderlich Initialisierung: 

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];
}

Doing it 2 Byte zu einem Zeitpunkt oder 4 Bytes zu einer Zeit, wahrscheinlich in noch größeren Beschleunigungen führen wird, wie Allan Wind , aber dann wird es schwieriger, wenn Sie mit den ungeraden Zeichen zu tun haben.

Wenn Sie etwas Zeit mitbringen, Sie könnten versuchen, Duff Gerät anzupassen dies tun.

Die Ergebnisse sind auf einem Intel Core Duo 2 Prozessor und gcc -O3.

Immer messen , dass Sie tatsächlich schnelle Ergebnisse erzielen -. Eine Pessimierung vorgibt, eine Optimierung zu sein, ist weniger als wertlos

Testen Sie immer , dass Sie die richtigen Ergebnisse erhalten -. Einen Fehler vorgibt, eine Optimierung zu sein, geradezu gefährlich ist

und immer im Auge behalten der Kompromiss zwischen Geschwindigkeit und Lesbarkeit -. Leben ist zu kurz für jedermann lesbar Code zu pflegen

( obligatorische Referenz Codierung für die heftigen Psychopathen, der weiß, wo Sie leben .)

Stellen Sie sicher, Ihre Compiler-Optimierung ist auf die höchste Arbeitsebene eingeschaltet.

Sie wissen, Flaggen wie '-O1' auf '-03' in gcc.

Ich habe festgestellt, dass ein Index in einem Array, anstatt einen Zeiger, die Dinge beschleunigen eine Zecke kann. Es hängt alles davon ab, wie Ihr Compiler wählt zu optimieren. Der Schlüssel ist, dass der Prozessor Befehle hat wie komplexe Dinge zu tun [i * 2 + 1] in einem einzigen Befehl.

Wenn Sie eher obsessiv sind hier, um Geschwindigkeit, können Sie wie folgt vor:

Jedes Zeichen ist ein Byte, die zwei Hex-Werte. Somit ist jeder Charakter wirklich zwei Vier-Bit-Werte.

So können Sie wie folgt vor:

  1. Packen Sie die vier-Bit-Werte in 8-Bit-Werte eine Multiplikation oder eine ähnliche Anweisung verwendet wird.
  2. Verwenden Sie pshufb, die SSSE3 Anweisung (Core2-only obwohl). Es nimmt eine Reihe von 16 8-Bit-Eingangswerte aus und mischt diese auf der Grundlage der 16 8-Bit-Indizes in einem zweiten Vektor. Da Sie nur 16 mögliche Zeichen haben, passt das perfekt; der Eingangs-Array ist ein Vektor von 0 bis F-Zeichen, und der Index-Array ist Ihre entpackten Array von 4-Bit-Werten.

So wird in einer Single Instruction , haben Sie durchgeführt 16 Tabelle Lookups in weniger Takte, als es normalerweise nur eine zu tun, nimmt (pshufb ist 1 Uhr Latenz auf Penryn ).

Also, in Rechenschritten:

  1. A B C D E F G H I J K L M N O P (64-Bit-Vektor von Eingabewerten, "Vector A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (128-Bit-Vektor von Indizes, "Vector B"). Der einfachste Weg ist wahrscheinlich zwei 64-Bit-Multiplikationen.
  2. pshub [0123456789ABCDEF], Vektor B

Ich bin mir nicht sicher, dass es mehr Bytes zu einer Zeit tun wird besser sein ... Sie werden wahrscheinlich bekommen Tonnen Cache-Misses gerade und langsam es deutlich nach unten.

Was Sie könnten versuchen, ist die Schleife obwohl entrollen, größere Schritte und mehr Zeichen jedes Mal durch die Schleife zu tun, einige der Schleife Overhead zu entfernen.

Konsequent immer ~ 4 ms auf meinem Athlon 64 4200+ (~ 7ms mit Original-Code) 

for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
    const char* pchars = _hex2asciiU_value[*pChar];
    *pszHex++ = *pchars++;
    *pszHex++ = *pchars;
}

Die Funktion, wie es gezeigt wird, wenn ich schreibe diese falsche Ausgabe erzeugt, auch wenn _hex2asciiU_value vollständig spezifiziert ist. Der folgende Code funktioniert, und auf meinem 2,33 GHz MacBook Pro läuft in etwa 1,9 Sekunden 200.000.000 Millionen Zeichen. 

#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";
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top