char [] для шестнадцатеричного упражнения

Question

Ниже моя текущая функция char * to hex. Я написал это как упражнение в манипуляциях с битами. На AMD Athlon MP 2800+ требуется около 7 мс, чтобы зашифровать массив из 10 миллионов байт. Есть какой-то трюк или другой способ, который я пропускаю?

Как я могу сделать это быстрее?

Скомпилировано с -O3 в 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;
}

Обновление

Добавлен временный код

Brian R. Bondy : замените std :: string буфером кучи на распределении и измените с * 16 на of << 4 - однако выделенный из кучи буфер, кажется, замедляет его? - результат ~ 11мс </p>

Antti Sykäri : заменить внутренний цикл на

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

результат ~ 8мс

Роберт : замените _hex2asciiU_value на полную таблицу из 256 записей, пожертвовав памятью, но в результате получите ~ 7 мс!

HoyHoy : заметил, что он дает неправильные результаты

Answer 1

Эта функция сборки (основанная на моем предыдущем посте здесь, но мне пришлось немного изменить концепцию, чтобы заставить ее работать) обрабатывает 3,3 миллиарда входных символов в секунду (6,6 миллиарда выходных символов) на одном ядре Core 2 Конроу 3Ghz. Пенрин, наверное, быстрее.

%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 - это три аргумента для функций в регистрах. Это немного похоже на псевдокод. Или вы можете просто получить файл common / x86 / x86inc.asm из дерева x264 и включить его для собственного запуска.

P.S. Переполнение стека, я не прав, чтобы тратить время на такую ​​банальную вещь? Или это круто?

Answer 2

За счет увеличения объема памяти вы можете создать полную таблицу из 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];

Answer 3

Быстрее C Имплментация

Это работает почти в 3 раза быстрее, чем реализация C ++. Не уверен, почему, поскольку это довольно похоже. Для последней реализованной мной реализации C ++ потребовалось 6,8 секунды, чтобы пройти массив из 200 000 000 символов. Реализация заняла всего 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));
}

Answer 4

У меня работает с 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"

Answer 5

Работайте с 32 битами за раз (4 символа), затем, если необходимо, работайте с хвостом. Когда я выполнял это упражнение с URL-кодированием, полный просмотр таблицы для каждого символа был немного быстрее, чем логические конструкции, поэтому вы можете проверить это и в контексте, чтобы учесть проблемы с кэшированием.

Answer 6

Для одного вместо умножения на 16 сделайте bitshift << 4

Также не используйте std::string, вместо этого просто создайте буфер в куче, а затем delete. Это будет более эффективно, чем уничтожение объекта, которое необходимо из строки.

Answer 7

Я предполагаю, что это Windows + IA32.
Попробуйте использовать короткий 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();

Answer 8

Изменение

    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%.

Запись результата двумя байтами за раз, как предлагает Роберт , приводит к ускорению примерно на 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.

Всегда измеряйте , что вы на самом деле получаете более быстрые результаты & mdash; пессимизация, притворяющаяся оптимизмом, не имеет смысла.

Всегда проверяйте , что вы получаете правильные результаты & mdash; ошибка, изображающая оптимизацию, совершенно опасна.

И всегда помните компромисс между скоростью и удобочитаемостью & mdash; жизнь слишком коротка, чтобы кто-то мог поддерживать нечитаемый код.

( Обязательное указание на кодирование насильственного психопата, который знает, где вы живете .)

Answer 9

Это моя версия, которая, в отличие от версии ОП, не предполагает, что 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;
}

Answer 10

не будет иметь большого значения ... * pChar- (ofs * 16) можно сделать с помощью [* pCHar & 0x0F]