Преобразование 128-битной шестнадцатеричной строки в строку base-36

Question

У меня есть 128-разрядное число в шестнадцатеричном формате, хранящееся в строке (из md5, безопасность здесь не проблема), которую я бы хотел преобразовать в базовую строку, 36 строк. Если бы это было 64-битное или меньшее число, я бы преобразовал его в 64-битное целое число, а затем использовал алгоритм, который я нашел для преобразования целых чисел в строки базы 36, но это число слишком велико для этого, поэтому я вроде как потеря для того, как подойти к этому. Любые рекомендации будут оценены.

Редактировать: После того, как Роланд Иллиг указал на хлопот о том, чтобы говорить 0/O и 1/l по телефону и не набирать большую плотность данных по гексагону, я думаю, что я могу остаться с шестнадцатеричным. Мне все же интересно, хотя, если существует относительно простой способ преобразования шестнадцатеричной строки произвольной длины в строку base-36.

Answer 1

Для кодирования базы-36 требуется 6 бит для хранения каждого токена. То же, что и base-64, но не используя 28 доступных токенов. Решение 36^n> = 2^128 дает n> = log (2^128)/log (36) или 25 токенов для кодирования значения.

Кодирование с базой-64 также требует 6 бит, используются все возможные значения токена. Решение 64^n> = 2^128 дает n> = log (2^128)/log (64) или 22 токена для кодирования значения.

Для вычисления кодировки base-36 требуется деление на 36. Нет простых сокращений, вам нужен алгоритм деления, который может работать со 128-битными значениями. Кодирование base-64 намного проще вычислять, так как оно является степенью 2. Просто возьмите 6 бит за раз и сдвиньте на 6, всего 22 раза, чтобы потреблять все 128 бит.

Почему вы хотите использовать базу-36? Стандартные кодировщики Base-64. Если у вас действительно есть ограничение на токеновое пространство (вы не должны, ASCII rulez), то, по крайней мере, используйте кодировку base-32. Или любая сила 2, base-16 - hex.

Answer 2

Если единственное, что не хватает является поддержка 128 битовых целых чисел без знака, здесь для вас решение:

#include <stdio.h> 
#include <inttypes.h> 

typedef struct { 
     uint32_t v3, v2, v1, v0; 
} uint128; 

static void 
uint128_divmod(uint128 *out_div, uint32_t *out_mod, const uint128 *in_num, uint32_t in_den) 
{ 
     uint64_t x = 0; 

     x = (x << 32) + in_num->v3; 
     out_div->v3 = x/in_den; 
     x %= in_den; 
     x = (x << 32) + in_num->v2; 
     out_div->v2 = x/in_den; 
     x %= in_den; 
     x = (x << 32) + in_num->v1; 
     out_div->v1 = x/in_den; 
     x %= in_den; 
     x = (x << 32) + in_num->v0; 
     out_div->v0 = x/in_den; 
     x %= in_den; 

     *out_mod = x; 
} 

int 
main(void) 
{ 
     uint128 x = { 0x12345678, 0x12345678, 0x12345678, 0x12345678 }; 
     uint128 result; 
     uint32_t mod; 

     uint128_divmod(&result, &mod, &x, 16); 
     fprintf(stdout, "%08"PRIx32" %08"PRIx32" %08"PRIx32" %08"PRIx32" rest %08"PRIx32"\n", result.v3, result.v2, result.v1, result.v0, mod); 

     return 0; 
} 

С помощью этой функции вы можете повторно вычислить мод-36 результат, который ведет к числу, закодированному как основание-36.

Answer 3

Если вы используете C++ с .NET 4, вы всегда можете использовать класс System.Numerics.BigInteger. Вы можете попытаться вызвать один из переопределений toString, чтобы вы могли попасть на базу 36.

Альтернативно можно посмотреть на одну из многих библиотек большого целого, например. Matt McCutchen's C++ Big Integer Library хотя вы, возможно, придется смотреть в depths of the classes использовать пользовательскую базу, такие как 36.

Answer 4

две вещи:
1. Это на самом деле не так уж трудно разделить строку байт на 36. Но если вы можете» Не следует беспокоиться о том, чтобы реализовать это, вы можете использовать кодировку base-32, для которой потребуется 26 байт вместо 25.
2. Если вы хотите, чтобы вы могли прочитать результат по телефону людям, вы абсолютно должны добавить простой контрольная сумма к вашей строке, которая будет стоить один или два байта, но избавит вас от огромного количества хлопот китайского шепота от клиентов с затрудненным слухом.