Convertir une chaîne hexadécimale de 128 bits en chaîne base-36

Question

J'ai un nombre de 128 bits en hexadécimal stocké dans une chaîne (de md5, la sécurité n'est pas un problème ici) que je voudrais convertir en base- 36 cordes. Si c'était un nombre de 64 bits ou moins, je le convertirais en un entier de 64 bits, puis utiliser un algorithme que j'ai trouvé pour convertir des entiers en chaînes de base 36, mais ce nombre est trop grand pour cela, donc je suis en quelque sorte une perte pour la façon d'aborder cela. Toute orientation serait appréciée. Edit: Après que Roland Illig a souligné les tracas de dire 0/O et 1/l sur le téléphone et ne pas gagner beaucoup de densité de données sur hex, je pense que je peux finir par rester avec hex. Je suis toujours curieux de savoir s'il existe un moyen relativement simple de convertir une chaîne hexadécimale de longueur arbitraire en une chaîne de base 36.

Answer 1

Un codage en base 36 nécessite 6 bits pour stocker chaque jeton. Identique à base 64 mais n'utilisant pas 28 des jetons disponibles. La résolution de 36^n> = 2^128 donne n> = log (2^128)/log (36) ou 25 jetons pour encoder la valeur.

Un codage en base 64 nécessite également 6 bits, toutes les valeurs de jeton possibles sont utilisées. La résolution 64^n> = 2^128 donne n> = log (2^128)/log (64) ou 22 jetons pour encoder la valeur.

Le calcul de l'encodage en base 36 nécessite une division par des puissances de 36. Pas de raccourcis faciles, vous avez besoin d'un algorithme de division qui peut fonctionner avec des valeurs de 128 bits. L'encodage base-64 est beaucoup plus facile à calculer car il est une puissance de 2. Prenez 6 bits à la fois et passez de 6, au total 22 fois pour consommer tous les 128 bits.

Pourquoi voulez-vous utiliser base-36? Les codeurs Base-64 sont standard. Si vous avez vraiment une contrainte sur l'espace de jeton (vous ne devriez pas, rulez ASCII) alors utilisez au moins un encodage base-32. Ou toute puissance de 2, la base 16 est hex.

Answer 2

Si la seule chose qui manque est le support de 128 bits entiers non signés, voici la solution pour vous:

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

Cette fonction vous pouvez calculer à plusieurs reprises le mod-36 résultat, ce qui vous conduit au nombre codé comme base-36.

Answer 3

Si vous utilisez C++ avec .NET 4, vous pouvez toujours utiliser la classe System.Numerics.BigInteger. Vous pouvez essayer d'appeler l'une des substitutions toString pour accéder à la base 36.

Vous pouvez également consulter l'une des nombreuses bibliothèques Big Integer, par exemple. Matt McCutchen's C++ Big Integer Library bien que vous pourriez avoir à regarder dans le depths of the classes d'utiliser une base personnalisée telle que 36.

Answer 4

Deux choses:
1. Il est vraiment pas difficile de diviser une chaîne d'octets par 36. Mais si vous le pouvez » Pour être implémenté, vous pouvez utiliser l'encodage base-32, qui aurait besoin de 26 octets au lieu de 25.
2. Si vous voulez pouvoir lire le résultat par téléphone pour les humains, vous devez absolument ajouter un simple Somme de contrôle à votre chaîne, ce qui coûtera un ou deux octets, mais vous permettra d'économiser une énorme quantité de tracas «chuchotements chinois» des clients malentendants.