Was ist eine bessere Methode 4 Bytes in 3 als dies für die Verpackung?

Question

Ich habe ein Array von Werten alle gut im Bereich von 0 bis 63, und beschlossen, ich konnte alle 4 Bytes in 3 packen, da nur die Werte 6 Bits erfordern, und ich konnte die zusätzlichen 2 Bits verwenden, um die ersten 2 Bits des speichern nächster Wert und so weiter.

Nachdem dies nie getan, bevor ich die switch Anweisung und eine nextbit Variable (eine Zustandsmaschine wie Gerät) verwendet, um die Verpackung zu tun und zu verfolgen, das Startbit. Ich bin jedoch davon überzeugt, es muss ein besserer Weg geben.

Anregungen / Hinweise bitte, aber nicht ruinieren meinen Spaß; -)

All Portabilität Probleme bei großem / Little-Endian?

btw: Ich habe diesen Code verifiziert funktioniert, indem Sie es erneut und Vergleich mit dem Eingang auszupacken. Und nein ist es nicht Hausaufgaben, nur eine Übung, die ich mir selbst gesetzt habe.

/* 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;
    }
}

Answer 1

Also, das ist ein bisschen wie Code-golf , nicht wahr?

---

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

Answer 2

Schauen Sie sich die IETF RFC 4648 für 'The Base16, Base32 und Base64 Daten Codierungen' .

Teilcode Kritik:

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);

Verwenden Sie die Floating-Point-Sachen nicht - nur ganze Zahlen verwenden. Und verwenden Sie ‚% z‘ drucken ‚size_t‘ Werte -. Vorausgesetzt, Sie eine C99-Bibliothek haben

size_t pl = ((dl + 3) / 4) * 3;

ich denke, Ihre Schleife durch den Umgang mit 3-Byte-Eingabeeinheiten vereinfacht werden könnte, bis Sie eine Teileinheit übrig, haben und dann mit einem Rest von 1 oder 2 Bytes als Sonderfälle handelt. Ich nehme zur Kenntnis, dass der Standard sagt verwiesen, dass Sie verwenden ein oder zwei ‚=‘ Zeichen auf Kissen am Ende.

Ich habe einen Base64-Encoder und Decodierung, die einige das tut. Sie beschreiben die ‚decode‘ Teil Base64 - wo der Base64-Code 4 Byte Daten hat, die in nur 3 gespeichert werden sollen - als Verpackungscode. Der Base64 Encoder entspricht der Entpacker Sie benötigen.

Base-64-Decoder

Hinweis: base_64_inv ist ein Array von 256 Werten, einer für jede mögliche Eingabe Bytewert; Sie definiert die korrekte dekodierte Wert für jedes codierte Byte. In der Base64-Kodierung, ist dies eine sparse array - 3/4 Nullen. In ähnlicher Weise ist das base_64_map Mapping zwischen einem Wert 0..63 und dem entsprechenden Speicherwert.

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

ich das Leben erschweren, indem sie mit einem Produkt zu tun haben, die eine Variante Alphabet für die Base64-Codierung verwendet und auch nicht zu Pad-Daten verwaltet - daher das ‚Pad‘ Argumente (die Null für ‚Null padding‘ sein kann oder ‚= 'für Standard-padding. die 'base_64_map' Array enthält, das Alphabet zu verwenden, für die 6-Bit-Werte im Bereich 0..63.

Answer 3

Ein weiterer einfacher Weg, es zu tun wäre Bit-Felder zu verwenden. Eines der weniger bekannten Ecken C struct Syntax ist das große Feld. Angenommen, Sie haben die folgende Struktur:

struct packed_bytes {
    byte chunk1 : 6;
    byte chunk2 : 6;
    byte chunk3 : 6;
    byte chunk4 : 6;
};

Dies erklärt chunk1, chunk2, chunk3 und chunk4 den Typen byte zu haben, aber nur nehmen 6 Bits in der Struktur. Das Ergebnis ist, dass sizeof(struct packed_bytes) == 3. Alles was Sie jetzt brauchen, ist eine kleine Funktion Array zu nehmen und es in die Struktur Dump wie folgt:

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

Dort gehen Sie, haben Sie jetzt eine Reihe von struct packed_bytes haben, die Sie leicht unter Verwendung der obigen Struktur lesen kann.

Answer 4

Statt einen State verwenden, können Sie einfach einen Zähler für verwenden, wie viele Bits sind bereits im aktuellen Byte verwendet wird, von dem aus Sie direkt auf das Shift-Offsets ableiten können und ob Sie in das nächste Byte überlaufen. die Endianess in Bezug auf: Solange Sie nur einen einzigen Datentyp verwenden (dh Sie nicht über Zeiger auf Typen unterschiedlicher Größe neu zu interpretieren (z int* a =...;short* b=(short*) a;) keine Probleme mit Endianess in den meisten Fällen

bekommen sollten

Answer 5

Elemente DigitalRoss kompakten Code machen, Grizzly Vorschlag, und meinen eigenen Code, ich habe meine eigene Antwort zuletzt geschrieben. Obwohl DigitalRoss eine brauchbare Arbeits Antwort liefert, würde meine Nutzung davon, ohne zu verstehen, hat nicht die gleiche Befriedigung wie das Lernen etwas zur Verfügung gestellt. Aus diesem Grund habe ich beschlossen, meine Antwort auf meiner ursprünglichen Code-Basis.

Ich habe auch den Rat Jonathon Leffler gibt zu ignorieren gewählt Gleitkomma-Arithmetik für die Berechnung der gepackten Datenlänge zu vermeiden, mit. Sowohl die empfohlene Methode gegeben - das gleiche DigitalRoss auch verwendet, erhöht sich die Länge der gepackten Daten um bis zu drei Bytes. Zugegeben das ist nicht viel, ist aber durch die Verwendung von Gleitkommamathematik auch vermeidbar.

Hier ist der Code, Kritik willkommen:

/* 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;
}