Quelle est la meilleure méthode pour l'emballage 4 octets dans 3 que cela?
https://stackoverflow.com/questions/1664563
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un tableau de toutes les valeurs dans la fourchette 0 - 63, et décidé que je pouvais emballer tous les 4 octets en 3 parce que les valeurs ne nécessitent que 6 bits et je pouvais utiliser les 2bits supplémentaires pour stocker les 2 premiers bits du la valeur suivante et ainsi de suite.
Après avoir jamais fait cela auparavant je la déclaration de switch et une variable de nextbit (une machine d'état comme l'appareil) pour faire l'emballage et garder une trace du bit de départ. Je suis convaincu cependant, il doit y avoir une meilleure façon.
Suggestions / indices s'il vous plaît, mais ne pas gâcher mon plaisir; -)
Les problèmes de portabilité concernant grand / petit-boutiste?
BTW: J'ai vérifié ce code fonctionne, par le déballer à nouveau et la comparaison avec l'entrée. Et non, ce n'est pas devoirs, juste un exercice que je me suis fixé.
/* build with gcc -std=c99 -Wconversion */
#define ASZ 400
typedef unsigned char uc_;
uc_ data[ASZ];
int i;
for (i = 0; i < ASZ; ++i) {
data[i] = (uc_)(i % 0x40);
}
size_t dl = sizeof(data);
printf("sizeof(data):%z\n",dl);
float fpl = ((float)dl / 4.0f) * 3.0f;
size_t pl = (size_t)(fpl > (float)((int)fpl) ? fpl + 1 : fpl);
printf("length of packed data:%z\n",pl);
for (i = 0; i < dl; ++i)
printf("%02d ", data[i]);
printf("\n");
uc_ * packeddata = calloc(pl, sizeof(uc_));
uc_ * byte = packeddata;
uc_ nextbit = 1;
for (int i = 0; i < dl; ++i) {
uc_ m = (uc_)(data[i] & 0x3f);
switch(nextbit) {
case 1:
/* all 6 bits of m into first 6 bits of byte: */
*byte = m;
nextbit = 7;
break;
case 3:
/* all 6 bits of m into last 6 bits of byte: */
*byte++ = (uc_)(*byte | (m << 2));
nextbit = 1;
break;
case 5:
/* 1st 4 bits of m into last 4 bits of byte: */
*byte++ = (uc_)(*byte | ((m & 0x0f) << 4));
/* 5th and 6th bits of m into 1st and 2nd bits of byte: */
*byte = (uc_)(*byte | ((m & 0x30) >> 4));
nextbit = 3;
break;
case 7:
/* 1st 2 bits of m into last 2 bits of byte: */
*byte++ = (uc_)(*byte | ((m & 0x03) << 6));
/* next (last) 4 bits of m into 1st 4 bits of byte: */
*byte = (uc_)((m & 0x3c) >> 2);
nextbit = 5;
break;
}
}
La solution
Alors, c'est un peu comme code de golf , droit?
#include <stdlib.h>
#include <string.h>
static void pack2(unsigned char *r, unsigned char *n) {
unsigned v = n[0] + (n[1] << 6) + (n[2] << 12) + (n[3] << 18);
*r++ = v;
*r++ = v >> 8;
*r++ = v >> 16;
}
unsigned char *apack(const unsigned char *s, int len) {
unsigned char *s_end = s + len,
*r, *result = malloc(len/4*3+3),
lastones[4] = { 0 };
if (result == NULL)
return NULL;
for(r = result; s + 4 <= s_end; s += 4, r += 3)
pack2(r, s);
memcpy(lastones, s, s_end - s);
pack2(r, lastones);
return result;
}
Autres conseils
Consultez l'IETF RFC 4648 pour 'Le Base16, Base32 et Base64 données codages' .
critique de code partiel:
size_t dl = sizeof(data);
printf("sizeof(data):%d\n",dl);
float fpl = ((float)dl / 4.0f) * 3.0f;
size_t pl = (size_t)(fpl > (float)((int)fpl) ? fpl + 1 : fpl);
printf("length of packed data:%d\n",pl);
Ne pas utiliser les choses à virgule flottante - il suffit d'utiliser des entiers. Et utiliser « % z » imprimer « size_t » valeurs -. En supposant que vous avez une bibliothèque C99
size_t pl = ((dl + 3) / 4) * 3;
Je pense que votre boucle pourrait être simplifié en traitant avec des unités d'entrée de 3 octets jusqu'à ce que vous avez une unité partielle reste, et traiter ensuite avec un reste de 1 ou 2 octets comme des cas particuliers. Je note que la norme de référence dit que vous utilisez un ou deux signes « = » à pad à la fin.
J'ai un encodeur base64 et decode qui fait partie de cela. Vous décrivez la partie « décodage » de base64 - où le code base64 dispose de 4 octets de données qui doivent être stockées en seulement 3 - comme votre code d'emballage. Le codeur base64 correspond à la décompresseur vous aurez besoin.
Base-64 Décodeur
Note: base_64_inv est un tableau de 256 valeurs, une pour chaque valeur de l'octet d'entrée possible; il définit la valeur décodée correcte pour chaque octet codé. Dans l'encodage base64, c'est un tableau clairsemé - 3/4 zéros. De même, base_64_map est la correspondance entre une valeur 0..63 et la valeur de stockage correspondant.
enum { DC_PAD = -1, DC_ERR = -2 };
static int decode_b64(int c)
{
int b64 = base_64_inv[c];
if (c == base64_pad)
b64 = DC_PAD;
else if (b64 == 0 && c != base_64_map[0])
b64 = DC_ERR;
return(b64);
}
/* Decode 4 bytes into 3 */
static int decode_quad(const char *b64_data, char *bin_data)
{
int b0 = decode_b64(b64_data[0]);
int b1 = decode_b64(b64_data[1]);
int b2 = decode_b64(b64_data[2]);
int b3 = decode_b64(b64_data[3]);
int bytes;
if (b0 < 0 || b1 < 0 || b2 == DC_ERR || b3 == DC_ERR || (b2 == DC_PAD && b3 != DC_PAD))
return(B64_ERR_INVALID_ENCODED_DATA);
if (b2 == DC_PAD && (b1 & 0x0F) != 0)
/* 3rd byte is '='; 2nd byte must end with 4 zero bits */
return(B64_ERR_INVALID_TRAILING_BYTE);
if (b2 >= 0 && b3 == DC_PAD && (b2 & 0x03) != 0)
/* 4th byte is '='; 3rd byte is not '=' and must end with 2 zero bits */
return(B64_ERR_INVALID_TRAILING_BYTE);
bin_data[0] = (b0 << 2) | (b1 >> 4);
bytes = 1;
if (b2 >= 0)
{
bin_data[1] = ((b1 & 0x0F) << 4) | (b2 >> 2);
bytes = 2;
}
if (b3 >= 0)
{
bin_data[2] = ((b2 & 0x03) << 6) | (b3);
bytes = 3;
}
return(bytes);
}
/* Decode input Base-64 string to original data. Output length returned, or negative error */
int base64_decode(const char *data, size_t datalen, char *buffer, size_t buflen)
{
size_t outlen = 0;
if (datalen % 4 != 0)
return(B64_ERR_INVALID_ENCODED_LENGTH);
if (BASE64_DECLENGTH(datalen) > buflen)
return(B64_ERR_OUTPUT_BUFFER_TOO_SMALL);
while (datalen >= 4)
{
int nbytes = decode_quad(data, buffer + outlen);
if (nbytes < 0)
return(nbytes);
outlen += nbytes;
data += 4;
datalen -= 4;
}
assert(datalen == 0); /* By virtue of the %4 check earlier */
return(outlen);
}
Base-64 Encodeur
/* Encode 3 bytes of data into 4 */
static void encode_triplet(const char *triplet, char *quad)
{
quad[0] = base_64_map[(triplet[0] >> 2) & 0x3F];
quad[1] = base_64_map[((triplet[0] & 0x03) << 4) | ((triplet[1] >> 4) & 0x0F)];
quad[2] = base_64_map[((triplet[1] & 0x0F) << 2) | ((triplet[2] >> 6) & 0x03)];
quad[3] = base_64_map[triplet[2] & 0x3F];
}
/* Encode 2 bytes of data into 4 */
static void encode_doublet(const char *doublet, char *quad, char pad)
{
quad[0] = base_64_map[(doublet[0] >> 2) & 0x3F];
quad[1] = base_64_map[((doublet[0] & 0x03) << 4) | ((doublet[1] >> 4) & 0x0F)];
quad[2] = base_64_map[((doublet[1] & 0x0F) << 2)];
quad[3] = pad;
}
/* Encode 1 byte of data into 4 */
static void encode_singlet(const char *singlet, char *quad, char pad)
{
quad[0] = base_64_map[(singlet[0] >> 2) & 0x3F];
quad[1] = base_64_map[((singlet[0] & 0x03) << 4)];
quad[2] = pad;
quad[3] = pad;
}
/* Encode input data as Base-64 string. Output length returned, or negative error */
static int base64_encode_internal(const char *data, size_t datalen, char *buffer, size_t buflen, char pad)
{
size_t outlen = BASE64_ENCLENGTH(datalen);
const char *bin_data = (const void *)data;
char *b64_data = (void *)buffer;
if (outlen > buflen)
return(B64_ERR_OUTPUT_BUFFER_TOO_SMALL);
while (datalen >= 3)
{
encode_triplet(bin_data, b64_data);
bin_data += 3;
b64_data += 4;
datalen -= 3;
}
b64_data[0] = '\0';
if (datalen == 2)
encode_doublet(bin_data, b64_data, pad);
else if (datalen == 1)
encode_singlet(bin_data, b64_data, pad);
b64_data[4] = '\0';
return((b64_data - buffer) + strlen(b64_data));
}
Je compliquer la vie en avoir à traiter avec un produit qui utilise un alphabet variante pour le codage base64, et gère pas non plus aux données pad - d'où l'argument « pad » (qui peut être zéro pour « padding null » ou « = 'pour le rembourrage standard. le « réseau de base_64_map » contient l'alphabet à utiliser pour les valeurs de 6 bits dans la gamme 0..63.
Une autre façon plus simple de le faire serait d'utiliser des champs de bits. L'un des coins moins connus de la syntaxe C struct est le grand champ. Disons que vous avez la structure suivante:
struct packed_bytes {
byte chunk1 : 6;
byte chunk2 : 6;
byte chunk3 : 6;
byte chunk4 : 6;
};
déclare chunk1, chunk2, chunk3 et chunk4 d'avoir le type byte mais pour ne prendre que jusqu'à 6 bits dans la structure. Le résultat est que sizeof(struct packed_bytes) == 3. Maintenant, tout ce dont vous avez besoin est une petite fonction pour prendre votre tableau et le jeter dans la structure comme ceci:
void
dump_to_struct(byte *in, struct packed_bytes *out, int count)
{
int i, j;
for (i = 0; i < (count / 4); ++i) {
out[i].chunk1 = in[i * 4];
out[i].chunk2 = in[i * 4 + 1];
out[i].chunk3 = in[i * 4 + 2];
out[i].chunk4 = in[i * 4 + 3];
}
// Finish up
switch(struct % 4) {
case 3:
out[count / 4].chunk3 = in[(count / 4) * 4 + 2];
case 2:
out[count / 4].chunk2 = in[(count / 4) * 4 + 1];
case 1:
out[count / 4].chunk1 = in[(count / 4) * 4];
}
}
Voilà, vous avez maintenant un tableau de struct packed_bytes que vous pouvez facilement lire en utilisant le struct ci-dessus.
Au lieu d'utiliser un StateMachine vous pouvez simplement utiliser un compteur pour combien de bits sont déjà utilisés dans l'octet courant, à partir duquel vous pouvez directement dériver les quarts décalages et si oui ou non vous déborder dans l'octet suivant.
En ce qui concerne la endianess: Tant que vous utilisez uniquement un seul type de données (qui vous ne réinterprétez pas pointeur sur les types de tailles différentes (par exemple int* a =...;short* b=(short*) a;) vous ne devriez pas avoir des problèmes avec endianess dans la plupart des cas
En prenant des éléments de code compact DigitalRoss, la suggestion de Grizzly, et mon propre code, j'ai écrit ma propre réponse à la fin. Bien que DigitalRoss apporte une réponse de travail utilisable, mon utilisation de celui-ci sans comprendre, n'aurait pas fourni la même satisfaction à apprendre quelque chose. Pour cette raison, je l'ai choisi de fonder ma réponse sur mon code d'origine.
J'ai aussi choisi d'ignorer les conseils Jonathon Leffler donne à éviter d'utiliser l'arithmétique en virgule flottante pour le calcul de la longueur des données emballé. Tant la méthode recommandée donnée - même DigitalRoss utilise également, augmente la longueur des données emballés par jusqu'à trois octets. Certes ce n'est pas beaucoup, mais est aussi évitable par l'utilisation des mathématiques à virgule flottante.
Voici le code, les critiques welcome:
/* built with gcc -std=c99 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned char *
pack(const unsigned char * data, size_t len, size_t * packedlen)
{
float fpl = ((float)len / 4.0f) * 3.0f;
*packedlen = (size_t)(fpl > (float)((int)fpl) ? fpl + 1 : fpl);
unsigned char * packed = malloc(*packedlen);
if (!packed)
return 0;
const unsigned char * in = data;
const unsigned char * in_end = in + len;
unsigned char * out;
for (out = packed; in + 4 <= in_end; in += 4) {
*out++ = in[0] | ((in[1] & 0x03) << 6);
*out++ = ((in[1] & 0x3c) >> 2) | ((in[2] & 0x0f) << 4);
*out++ = ((in[2] & 0x30) >> 4) | (in[3] << 2);
}
size_t lastlen = in_end - in;
if (lastlen > 0) {
*out = in[0];
if (lastlen > 1) {
*out++ |= ((in[1] & 0x03) << 6);
*out = ((in[1] & 0x3c) >> 2);
if (lastlen > 2) {
*out++ |= ((in[2] & 0x0f) << 4);
*out = ((in[2] & 0x30) >> 4);
if (lastlen > 3)
*out |= (in[3] << 2);
}
}
}
return packed;
}
int main()
{
size_t i;
unsigned char data[] = {
12, 15, 40, 18,
26, 32, 50, 3,
7, 19, 46, 10,
25, 37, 2, 39,
60, 59, 0, 17,
9, 29, 13, 54,
5, 6, 47, 32
};
size_t datalen = sizeof(data);
printf("unpacked datalen: %td\nunpacked data\n", datalen);
for (i = 0; i < datalen; ++i)
printf("%02d ", data[i]);
printf("\n");
size_t packedlen;
unsigned char * packed = pack(data, sizeof(data), &packedlen);
if (!packed) {
fprintf(stderr, "Packing failed!\n");
return EXIT_FAILURE;
}
printf("packedlen: %td\npacked data\n", packedlen);
for (i = 0; i < packedlen; ++i)
printf("0x%02x ", packed[i]);
printf("\n");
free(packed);
return EXIT_SUCCESS;
}
