ما هي طريقة أفضل لتعبئة 4 بايت في 3 من هذا؟

Question

لدي مجموعة من القيم بشكل جيد خلال النطاق 0 - 63، وقررت أن أقوم بحزم كل 4 بايت في 3 لأن القيم تتطلب فقط 6 بت ويمكنني استخدام 2 مليار إضافية لتخزين البتات الأولى من القيمة التالية هكذا.

بعد أن فعلت هذا قبل أن استخدمت switch بيان و nextbit متغير (آلة الحالة مثل الجهاز) للقيام بالتعبئة والتتبع لتسجيل البداية. ومع ذلك، أنا مقتنع، يجب أن يكون هناك طريقة أفضل.

اقتراحات / أدلة من فضلك، ولكن لا تدمر المرح ؛-)

أي مشاكل في إمكانية النقل فيما يتعلق بنديان كبير / صغير؟

راجع للشغل: لقد تحققت هذا الرمز يعمل، من خلال تفريغه مرة أخرى ومقارنة مع المدخلات. ولا ليس من الواجبات المنزلية، مجرد تمرين قمت بتعيين نفسي.

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

لذلك، هذا هو كيندا مثل كود-جولف, ، الصحيح؟

---

#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

تحقق من ietf RFC 4648. لترميزات بيانات البيانات Base16 و Pase32 و Base64.

نقد رمز جزئي:

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

لا تستخدم الأشياء العائمة للنقطة - فقط استخدم الأعداد الصحيحة. واستخدام "٪ Z" لطباعة قيم "Size_T" - على افتراض أنك حصلت على مكتبة C99.

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

أعتقد أن حلقةك يمكن تبسيطها عن طريق التعامل مع وحدات الإدخال 3 بايت حتى تحصل على وحدة جزئية متبقية، ثم التعامل مع ما تبقى من 1 أو 2 بايت كحالات خاصة. لاحظ أن المعيار المشار إليه يقول أنك تستخدم علامات واحدة أو اثنين "=" علامات للوحة في النهاية.

لدي تشفير Base64 و فكيبها الذي يفعل بعض ذلك. أنت تصف الجزء "فك تشفير" من Base64 - حيث يحتوي رمز Base64 على 4 بايت من البيانات التي يجب تخزينها في 3 - كتعبئة التعبئة. تشفير Base64 يتوافق مع unpacker ستحتاج.

BASE-64 فك

ملاحظة: BASE_64_INV هي صفيفة من 256 قيما، واحدة لكل قيمة بايت الإدخال ممكن؛ يحدد القيمة المنفجرة الصحيحة لكل بايت مشفرة. في ترميز Base64، هذا هو صفيف متفرق - 3/4 الأصفار. وبالمثل، فإن base_64_map هو التعيين بين القيمة 0..63 وقيمة التخزين المقابلة.

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 التشفير

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

أعقد الحياة من خلال الاضطرار إلى التعامل مع منتج يستخدم الأبجدية المتنوعة لترميز Base64، وكذلك يدير أيضا بيانات الوسادة - وبالتالي فإن وسيطة "الوسادة" (والتي يمكن أن تكون صفرية ل "الحشو" أو "=" لمعيار حشوة. تحتوي مجموعة "base_64_map" على الأبجدية لاستخدامها لقيم 6 بت في النطاق 0..63.

Answer 3

طريقة أبسط أخرى للقيام بذلك سيكون استخدام حقول بت. واحد من الزوايا الأقل شهرة من ج struct بناء الجملة هو الحقل الكبير. دعنا نقول أن لديك الهيكل التالي:

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

هذا يعلن chunk1, chunk2, chunk3, ، و chunk4 للحصول على النوع byte ولكن لاتخاذ 6 بت فقط في الهيكل. والنتيجة هي أن sizeof(struct packed_bytes) == 3. وبعد الآن كل ما تحتاجه هو وظيفة صغيرة لأخذ صفيفك وتفريغها في هيكل ذلك مثل ذلك:

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

هناك تذهب، لديك الآن مجموعة من struct packed_bytes أنه يمكنك قراءة بسهولة باستخدام الهيكل أعلاه.

Answer 4

بدلا من استخدام Statemachine، يمكنك ببساطة استخدام عداد لك عدد البتات المستخدمة بالفعل في البايت الحالي، والتي يمكنك من خلالها أن تستمد مباشرة من إزاحة التحول وما إذا كنت تتجاوز في البايت التالي أم لا. فيما يتعلق بالأندرينس: طالما كنت تستخدم نوع بيانات واحد فقط (لا يمكنك إعادة تفسير مؤشر إلى أنواع مختلفة الحجم (على سبيل المثال int* a =...;short* b=(short*) a;) يجب أن لا تحصل على مشاكل مع نبيذ في معظم الحالات

Answer 5

تناول عناصر التعليمات البرمجية المدمجة في DigitalRoss، واقتراح Grizzly، والرمز الخاص بي، لقد كتبت إجابتي الخاصة في النهاية. على الرغم من أن DigitalRoss يوفر إجابة عمل صالحة للاستعمال، فإن استخدامي لها دون فهم، لن يوفر نفس الرضا عن تعلم شيء ما. لهذا السبب اخترت أن أساعد إجابتي على التعليمات البرمجية الأصلية.

لقد اخترت أيضا تجاهل النصيحة Jonathon Leffler تقدم لتجنب استخدام الحساب الفاتح العائم لحساب طول البيانات المعبأ. تستخدم كل من الأسلوب الموصى به - نفس DigitalRoss أيضا، يزيد من طول البيانات المعبأة بقدر ثلاثة بايت. منح هذا ليس كثيرا، ولكنه يمكن تجنبه أيضا من خلال استخدام الرياضيات المرحلة العائمة.

هنا هو الكود، والنقد موضع ترحيب:

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