¿Qué es un método mejor para el embalaje de 4 bytes en 3 que esto?
https://stackoverflow.com/questions/1664563
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo una matriz de valores todo bien dentro del Rango 0 - 63, y decidí que podía empaquetar cada 4 bytes en 3 porque los valores sólo requieren 6 bits y que podía usar el 2bits adicionales para almacenar los primeros 2 bits de la valor siguiente y así sucesivamente.
Como nunca había hecho esto antes He utilizado la declaración switch y una variable nextbit (una máquina de estados como el dispositivo) para hacer el embalaje y realizar un seguimiento del bit de arranque. Estoy convencido, sin embargo, tiene que haber una mejor manera.
Sugerencias / pistas favor, pero no arruinar mi diversión; -)
Cualquier problema de portabilidad con respecto a little endian grande /?
BTW: He verificado el código está trabajando, descomprimiéndolo nuevo y comparando con la entrada. Y no, no es la tarea, sólo un ejercicio que he puesto yo mismo.
/* 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;
}
}
Solución
Por lo tanto, esto es un poco como código de golf , ¿verdad?
#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;
}
Otros consejos
Salida del IETF RFC 4648 para 'El Base16, Base32 y Base64 datos codificaciones' .
Código de la crítica parcial:
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);
No utilizar el material de punto flotante - sólo tiene que utilizar números enteros. Y utilizar '% z' imprimir 'size_t' valores -. Asumiendo que tienes una biblioteca C99
size_t pl = ((dl + 3) / 4) * 3;
Creo que el bucle se podría simplificar tratar con unidades de entrada de 3 bytes hasta que haya logrado una unidad parcial de sobra, y luego tratar con un resto de 1 o 2 bytes como casos especiales. Tomo nota de que la norma referenciada dice que utiliza uno o dos signos '=' para rellenar al final.
Tengo un codificador Base64 y decodificar el que hace algo de eso. Usted está describiendo la parte 'decodificación' de base 64 - donde el código de base 64 tiene 4 bytes de datos que deben ser almacenados en sólo 3 - por ejemplo el código de embalaje. El codificador de base 64 corresponde a la desencajonadora va a necesitar.
Base-64 Decoder
Nota: base_64_inv es una matriz de 256 valores, uno para cada valor de byte de entrada posible; define el valor decodificado correcto para cada byte codificado. En la codificación Base64, esta es una matriz dispersa - 3/4 ceros. Del mismo modo, base_64_map es el mapeo entre un valor 0..63 y el valor de almacenamiento correspondiente.
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 Encoder
/* 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));
}
I complicar la vida por tener que tratar con un producto que utiliza un alfabeto variante para la codificación Base64, y también gestiona no a los datos de pad - por lo tanto, el argumento 'almohadilla' (que puede ser cero para 'padding nulo' o '= 'para el relleno estándar. el 'array base_64_map' contiene el alfabeto de usar para los valores de 6 bits en el rango 0..63.
Otra manera más sencilla de hacerlo sería utilizar los campos de bits. Uno de los rincones menos conocidos de la sintaxis struct C es el campo grande. Digamos que usted tiene la siguiente estructura:
struct packed_bytes {
byte chunk1 : 6;
byte chunk2 : 6;
byte chunk3 : 6;
byte chunk4 : 6;
};
Esto declara chunk1, chunk2, chunk3 y chunk4 tener el tipo byte pero sólo para tomar hasta 6 bits en la estructura. El resultado es que sizeof(struct packed_bytes) == 3. Ahora todo lo que necesita es un poco de función para tomar su matriz y lo descarga en la estructura de este modo:
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];
}
}
Hay que ir, ahora tiene una serie de struct packed_bytes que se puede leer fácilmente mediante el uso de la estructura anterior.
En lugar de utilizar un StateMachine puede simplemente usar un contador para el número de bits que ya se utilizan en el byte actual, desde donde se puede derivar directamente los turnos de compensaciones y si está o no desbordar en el siguiente byte.
En cuanto a la endianess: Mientras se utiliza un solo tipo de datos (que es no reinterpretar puntero a tipos de diferente tamaño (por ejemplo int* a =...;short* b=(short*) a;) que no debería tener problemas con endianess en la mayoría de los casos
Tomando elementos de código de DigitalRoss compacta, la sugerencia de Grizzly, y mi propio código, he escrito mi propia respuesta al fin. Aunque DigitalRoss proporciona una respuesta de trabajo utilizable, mi uso de ella sin entender, no habría proporcionado la misma satisfacción que para aprender algo. Por esta razón he decidido basar mi respuesta en mi código original.
También he optado por ignorar el consejo Jonathan Leffler da a evitar el uso de aritmética de punto flotante para el cálculo de la longitud de los datos de relleno. Tanto el método recomendado dado - la misma DigitalRoss utiliza también, aumenta la longitud de los datos empaquetados por tanto como tres bytes. Por supuesto esto no es mucho, pero también se puede evitar mediante el uso de cálculos de coma flotante.
Este es el código, las críticas dan la bienvenida:
/* 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;
}
