char[]를 16진수 문자열로 변환

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

  •  09-06-2019
  •  | 
  •  

문제

다음은 현재 char*를 16진수 문자열로 변환하는 함수입니다.비트 조작 연습으로 썼습니다.AMD Athlon MP 2800+에서 1천만 바이트 배열을 16진수화하는 데 ~7ms가 걸립니다.내가 놓친 트릭이나 다른 방법이 있습니까?

어떻게 하면 더 빠르게 할 수 있나요?

g++에서 -O3으로 컴파일됨

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

업데이트

타이밍 코드 추가

브라이언 R.본디:std::string을 힙 할당 버퍼로 바꾸고 ofs*16을 ofs << 4로 변경합니다. 그러나 힙 할당 버퍼로 인해 속도가 느려지는 것 같습니까?- 결과 ~11ms

안티 시카리: 내부 루프를 다음으로 교체 

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

결과 ~8ms

로버트:바꾸다 _hex2asciiU_value 전체 256개 항목 테이블을 사용하면 메모리 공간이 희생되지만 결과는 ~7ms입니다!

호이호이:잘못된 결과가 나오는 것으로 나타났습니다.

도움이 되었습니까?

해결책

더 많은 메모리를 사용하면 16진수 코드의 전체 256개 항목 테이블을 만들 수 있습니다.

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

그런 다음 테이블에 직접 인덱스를 추가하면 비트 조작이 필요하지 않습니다.

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

다른 팁

이 어셈블리 기능(이전 게시물을 기반으로 하지만 실제로 작동하려면 개념을 약간 수정해야 함)은 Core 2 Conroe 3Ghz의 한 코어에서 초당 33억 개의 입력 문자(66억 개의 출력 문자)를 처리합니다.펜린이 더 빠를 것 같아요.

%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

x264 어셈블리 구문을 사용하므로 이식성이 더 높습니다(32비트와 64비트 등).이것을 원하는 구문으로 변환하는 것은 간단합니다.r0, r1, r2는 레지스터의 함수에 대한 세 가지 인수입니다.의사 코드와 약간 비슷합니다.아니면 x264 트리에서 common/x86/x86inc.asm을 가져와서 포함시켜 기본적으로 실행할 수도 있습니다.

추신스택오버플로, 이런 사소한 일에 시간을 낭비한 제가 잘못인가요?아니면 이게 굉장한 거야?

더 빠른 C 구현

이는 C++ 구현보다 거의 3배 빠르게 실행됩니다.꽤 비슷해서 왜인지는 모르겠습니다.제가 게시한 마지막 C++ 구현의 경우 2억 문자 배열을 실행하는 데 6.8초가 걸렸습니다.구현에는 단 2.2초밖에 걸리지 않았습니다. 

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

enter image description here

한 번에 32비트(4자)로 작업한 다음 필요한 경우 꼬리 부분을 처리합니다.URL 인코딩을 사용하여 이 연습을 수행했을 때 각 문자에 대한 전체 테이블 조회가 논리 구성보다 약간 빠르므로 캐싱 문제를 고려하기 위해 컨텍스트에서 이를 테스트할 수도 있습니다.

그것은 나를 위해 작동합니다 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"

우선, 다음을 곱하는 대신 16 ~을 하다 bitshift << 4

또한 std::string, 대신 힙에 버퍼를 만든 다음 delete 그것.문자열에서 필요한 객체 파괴보다 더 효율적입니다.

별로 달라질게 없을텐데...*pChar-(ofs*16)은 [*pCHar & 0x0F]로 수행할 수 있습니다.

이것은 OP 버전과 달리 내 버전입니다. std::basic_string 인접한 지역에 데이터가 있습니다.

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

나는 이것이 Windows + IA32라고 가정합니다.
두 개의 16진수 문자 대신 짧은 int를 사용해 보세요.

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

바꾸다

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

결과적으로 약 5%의 속도 향상이 발생합니다.

다음에서 제안한 대로 한 번에 2바이트 결과를 씁니다. 로버트 약 18%의 속도 향상을 가져옵니다.코드는 다음과 같이 변경됩니다.

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

필수 초기화:

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

한 번에 2바이트 또는 한 번에 4바이트를 수행하면 다음에서 지적한 대로 속도가 더 빨라질 수 있습니다. 앨런 윈드, 하지만 이상한 캐릭터를 처리해야 할 때 더 까다로워집니다.

모험심이 강하다면 적응하려고 노력할 수도 있습니다. 더프의 장치 이것을하기 위해.

결과는 Intel Core Duo 2 프로세서와 gcc -O3.

항상 측정 실제로 더 빠른 결과를 얻을 수 있습니다. 최적화인 척하는 비관적인 생각은 가치가 없습니다.

항상 테스트 올바른 결과를 얻으려면 최적화를 가장하는 버그가 매우 위험합니다.

그리고 항상 명심하세요 속도와 가독성 사이의 균형 - 읽을 수 없는 코드를 유지 관리하기에는 수명이 너무 짧습니다.

(필수 참조 코딩에 당신이 사는 곳을 아는 폭력적인 사이코패스.)

컴파일러 최적화가 가장 높은 작업 수준으로 켜져 있는지 확인하십시오.

아시다시피 gcc에는 '-O1'부터 '-03'까지의 플래그가 있습니다.

포인터 대신 배열에 인덱스를 사용하면 작업 속도가 빨라질 수 있다는 것을 발견했습니다.그것은 모두 컴파일러가 최적화를 선택하는 방법에 따라 다릅니다.핵심은 프로세서에 단일 명령으로 [i*2+1]과 같은 복잡한 작업을 수행하는 명령이 있다는 것입니다.

여기서 속도에 다소 집착하는 경우 다음을 수행할 수 있습니다.

각 문자는 2개의 16진수 값을 나타내는 1바이트입니다.따라서 각 문자는 실제로 두 개의 4비트 값입니다.

따라서 다음을 수행할 수 있습니다.

  1. 곱셈이나 유사한 명령어를 사용하여 4비트 값을 8비트 값으로 압축 해제합니다.
  2. SSSE3 명령인 pshufb를 사용하십시오(Core2에만 해당).16개의 8비트 입력 값 배열을 가져와 두 번째 벡터의 16개 8비트 인덱스를 기반으로 섞습니다.가능한 문자는 16개뿐이므로 이는 완벽하게 들어맞습니다.입력 배열은 0부터 F까지의 문자로 구성된 벡터이고, 인덱스 배열은 압축이 풀린 4비트 값 배열입니다.

따라서, 단일 명령, 당신은 공연했을 것입니다 16개의 테이블 조회 일반적으로 단 하나의 작업을 수행하는 데 걸리는 것보다 더 적은 클럭으로 수행됩니다(pshufb는 Penryn에서 1 클럭 대기 시간입니다).

따라서 계산 단계에서는 다음과 같습니다.

  1. A B C D E F G H I J K L M N O P(입력 값의 64비트 벡터, "벡터 A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P(인덱스의 128비트 벡터, "벡터 B").가장 쉬운 방법은 아마도 두 개의 64비트 곱셈일 것입니다.
  2. pshub [0123456789ABCDEF], 벡터 B

한 번에 더 많은 바이트를 수행하는 것이 더 나을지는 잘 모르겠습니다.아마도 수많은 캐시 미스가 발생하고 속도가 크게 느려질 것입니다.

당신이 시도할 수 있는 것은 루프를 풀고, 루프를 통해 매번 더 큰 단계를 수행하고 더 많은 문자를 수행하여 루프 오버헤드의 일부를 제거하는 것입니다.

내 Athlon 64 4200+에서 지속적으로 ~4ms를 얻습니다(원본 코드에서는 ~7ms).

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

이 글을 작성할 때 표시된 함수는 _hex2asciiU_value가 완전히 지정된 경우에도 잘못된 출력을 생성합니다.다음 코드는 작동하며 내 2.33GHz Macbook Pro에서 2억 문자에 대해 약 1.9초 만에 실행됩니다. 

#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";
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top