Есть много способов решить этот вопрос, которые используют некоторую арифметику для преобразования из диапазонов символов ascii 0-9 и a-f (или A-F) в двоичный файл. Я хотел найти решение, которое использует только таблицу соответствия и сравнивает ее с решением, в котором вместо этого используется арифметика. Как ни странно, ни один из ответов выше не реализует чисто арифметическое решение, а некоторые ответы даже предполагают, что «преобразование в двоичное» означает преобразование в строку символов ascii «0» и «1».
Давайте сначала сделаем несколько настроек. Во-первых, мы хотим хранить в памяти все данные теста, чтобы избежать влияния дискового ввода-вывода на тест. Вот как я создаю заголовок с массивом символов «testdata» размером 104857600 байт, примерно 105 МБ. Поскольку вопрос заключался в том, как конвертировать файлы, наша реализация должна быть быстрой для больших данных.
$ { printf "char *testdata =\""; cat /dev/urandom \
| tr -d -c "0123456789abcdefABCDEF" \
| dd count=100 iflag=fullblock bs=1M; printf "\";\n" } > testdata.h
Далее мы создаем таблицы поиска. Я вижу два возможных способа решить эту проблему с помощью справочной таблицы. Либо таблица соответствия отображает отдельные шестнадцатеричные символы ascii в половину байтов, либо она отображает два шестнадцатеричных символа в полный байт. В первом случае таблица поиска должна иметь 256 записей. В последнем случае таблица поиска должна иметь 256 * 256 = 65536 записей. Мы можем уменьшить размер последнего, понимая, что первый бит первого байта никогда не будет использован. Таким образом, нам нужна только таблица поиска из 128 * 256 = 32768 записей. Поскольку это решение также требует дополнительного шага вычисления (применение битовой маски), мы будем тестировать оба. В итоге мы получим следующие тестовые примеры:
- арифметическое решение
- 256 записей таблицы поиска
- 32768 записей справочной таблицы
- 65536 записей справочной таблицы
Первая таблица поиска легко генерируется с помощью некоторого Python:
#!/usr/bin/env python
import sys,struct
sys.stdout.write("unsigned char base16_decoding_table1[256] = {\n")
for i in xrange(256):
try:
j = str(int(chr(i), 16))
except:
j = '0'
sys.stdout.write(j+',')
sys.stdout.write("};\n")
sys.stdout.write("\n")
l = 128*256*["0"]
for a in ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F']:
for b in ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F']:
l[struct.unpack("<H", a+b)[0]] = str(int(a+b, 16))
line = "unsigned char base16_decoding_table2[%d] = {"%(128*256)
for e in l:
line += e+","
if len(line) > 70:
sys.stdout.write(line+"\n")
line = ""
sys.stdout.write(line+"};\n")
sys.stdout.write("\n")
l = 256*256*["0"]
for a in ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F']:
for b in ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F']:
l[struct.unpack("<H", a+b)[0]] = str(int(a+b, 16))
line = "unsigned char base16_decoding_table3[%d] = {"%(256*256)
for e in l:
line += e+","
if len(line) > 70:
sys.stdout.write(line+"\n")
line = ""
sys.stdout.write(line+"};\n")
А потом:
python gen.py > base16_decoding_table.h
Теперь мы можем написать код для тестирования.
#include <stdio.h>
#include <time.h>
#include <inttypes.h>
#include "testdata.h"
#include "base16_decoding_table.h"
#define TESTDATALEN 104857600
/* the resulting binary string is half the size of the input hex string
* because every two hex characters map to one byte */
unsigned char result[TESTDATALEN/2];
void test1()
{
size_t i;
char cur;
unsigned char val;
for (i = 0; i < TESTDATALEN; i++) {
cur = testdata[i];
if (cur >= 97) {
val = cur - 97 + 10;
} else if (cur >= 65) {
val = cur - 65 + 10;
} else {
val = cur - 48;
}
/* even characters are the first half, odd characters the second half
* of the current output byte */
if (i%2 == 0) {
result[i/2] = val << 4;
} else {
result[i/2] |= val;
}
}
}
void test2()
{
size_t i;
char cur;
unsigned char val;
for (i = 0; i < TESTDATALEN; i++) {
cur = testdata[i];
val = base16_decoding_table1[(int)cur];
/* even characters are the first half, odd characters the second half
* of the current output byte */
if (i%2 == 0) {
result[i/2] = val << 4;
} else {
result[i/2] |= val;
}
}
}
void test3()
{
size_t i;
uint16_t *cur;
unsigned char val;
for (i = 0; i < TESTDATALEN; i+=2) {
cur = (uint16_t*)(testdata+i);
// apply bitmask to make sure that the first bit is zero
val = base16_decoding_table2[*cur & 0x7fff];
result[i/2] = val;
}
}
void test4()
{
size_t i;
uint16_t *cur;
unsigned char val;
for (i = 0; i < TESTDATALEN; i+=2) {
cur = (uint16_t*)(testdata+i);
val = base16_decoding_table3[*cur];
result[i/2] = val;
}
}
#define NUMTESTS 1000
int main() {
struct timespec before, after;
unsigned long long checksum;
int i;
double elapsed;
clock_gettime(CLOCK_MONOTONIC, &before);
for (i = 0; i < NUMTESTS; i++) {
test1();
}
clock_gettime(CLOCK_MONOTONIC, &after);
checksum = 0;
for (i = 0; i < TESTDATALEN/2; i++) {
checksum += result[i];
}
printf("checksum: %llu\n", checksum);
elapsed = difftime(after.tv_sec, before.tv_sec) + (after.tv_nsec - before.tv_nsec)/1.0e9;
printf("arithmetic solution took %f seconds\n", elapsed);
clock_gettime(CLOCK_MONOTONIC, &before);
for (i = 0; i < NUMTESTS; i++) {
test2();
}
clock_gettime(CLOCK_MONOTONIC, &after);
checksum = 0;
for (i = 0; i < TESTDATALEN/2; i++) {
checksum += result[i];
}
printf("checksum: %llu\n", checksum);
elapsed = difftime(after.tv_sec, before.tv_sec) + (after.tv_nsec - before.tv_nsec)/1.0e9;
printf("256 entries table took %f seconds\n", elapsed);
clock_gettime(CLOCK_MONOTONIC, &before);
for (i = 0; i < NUMTESTS; i++) {
test3();
}
clock_gettime(CLOCK_MONOTONIC, &after);
checksum = 0;
for (i = 0; i < TESTDATALEN/2; i++) {
checksum += result[i];
}
printf("checksum: %llu\n", checksum);
elapsed = difftime(after.tv_sec, before.tv_sec) + (after.tv_nsec - before.tv_nsec)/1.0e9;
printf("32768 entries table took %f seconds\n", elapsed);
clock_gettime(CLOCK_MONOTONIC, &before);
for (i = 0; i < NUMTESTS; i++) {
test4();
}
clock_gettime(CLOCK_MONOTONIC, &after);
checksum = 0;
for (i = 0; i < TESTDATALEN/2; i++) {
checksum += result[i];
}
printf("checksum: %llu\n", checksum);
elapsed = difftime(after.tv_sec, before.tv_sec) + (after.tv_nsec - before.tv_nsec)/1.0e9;
printf("65536 entries table took %f seconds\n", elapsed);
return 0;
}
Позволяет скомпилировать вещь:
$ gcc -O3 -g -Wall -Wextra test.c
И запустить его:
$ ./a.out
Результат:
- арифметическое решение: 437,17 с
- 256 записей таблицы поиска: 117.80 с
- 32768: 52,33 с
- 65536: 44,66 с
Таким образом, мы можем заключить, что справочные таблицы в любое время превосходят арифметические решения, и что потеря памяти для больших справочных таблиц может стоить дополнительного времени выполнения.