これよりも3に4バイトのパッキングのためのより良い方法は何ですか?
-
12-09-2019 - |
質問
私はすべてのウェルの範囲内の値0の配列を持っている - 63、および値のみ6ビットを必要とするので、私は3にすべての4つのバイトを詰めることができ、私は最初の2ビットを記憶するために余分な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;
}
}
解決
だから、これは右、ちょっと コード-ゴルフののようなものです?
<時間>#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;
}
他のヒント
'Base16、Base32とBase64でデータエンコーディング' のIETF RFC 4648 にチェックしてくださいます。
部分的なコードの批判ます:
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);
浮動小数点のものを使用しないでください - ちょうど整数を使用。そして、 'size_tの価値観を印刷するには、「%zを」を使用 - あなたはC99のライブラリを持っていると仮定します。
。size_t pl = ((dl + 3) / 4) * 3;
私はあなたのループはあなたが余っ部分ユニットを持ってまで、3バイトの入力単位を扱う、その後、特殊な例として、1または2バイトの残りの部分を扱うことにより、簡素化することができると思います。私は、参照標準は、あなたが最後にパッドに1または2「=」印を使用することを述べていることに注意します。
私はそれの一部を行うのBase64エンコーダとデコーダを持っています。あなたの梱包コードとして - Base64でコードがちょうど3に格納すべきデータの4つのバイトを持っている - あなたは、Base64の「復号」の部分を記述しています。 Base64のエンコーダは、あなたが必要となりますアンパックに対応します。
ベース64デコーダ
注:base_64_invは256の値、各可能な入力バイト値のための1つのアレイです。それは、各符号化されたバイトの正しい復号値を定義します。 3/4ゼロ - Base64エンコーディングでは、これは疎な配列です。同様に、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);
}
ベース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));
}
Iはまた、Base64エンコードのための変異体のアルファベットを使用し、製品に対処することによって生命を複雑にしないパッドデータを管理する - 「ヌルパディング」または「=ゼロとすることができる(したがって、「パッド」引数「標準的なパディングのために。 『base_64_map』配列は、範囲0 63 6ビット値に使用するアルファベットが含まれています。
それを行うためのもう一つの簡単な方法は、ビットフィールドを使用することです。 Cのstruct
構文のあまり知られていないコーナーの一つは、大きなフィールドです。あなたは次のような構造を持っているとしましょう。
struct packed_bytes {
byte chunk1 : 6;
byte chunk2 : 6;
byte chunk3 : 6;
byte chunk4 : 6;
};
この構造では、最大6ビットを取るタイプのchunk1
を持っているだけにしchunk2
、chunk3
、chunk4
、およびbyte
を宣言します。結果は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
の配列を持っています。
の代わりにあなたは、単にすでにあなたが直接シフト・オフセットを導き出すことができ、そこから現在のバイト、で、あなたは次のバイトにオーバーフローするか否かに使用されているどのように多くのビットカウンタを使用することができるステートマシンを使用します。
エンディアンについて:限り、あなたは、単一のデータ型を使用して(つまり、あなたが異なるサイズの種類を指すポインタを再解釈していない(例えばint* a =...;short* b=(short*) a;
)は、
DigitalRossのコンパクトなコード、グリズリーの提案、そして私自身のコードの要素を取って、私は最後に私自身の答えを書かれています。 DigitalRossを理解せずに使用可能な作業の答え、それの私の使用を提供していますが、何かを学習するのと同じ満足を提供していません。このような理由から、私は私の元のコードの上に私の答えをベースにすることを選択した。
私はまた、ジョナサンレフラーは、パックされたデータの長さの計算のために浮動小数点演算を使用しないようにできますアドバイスを無視することを選択しました。所定の推奨される方法の両方 - 同じDigitalRossも使用は、同じくらい3としてバイトでパックされたデータの長さを増加させます。確かにこれはあまりありませんが、浮動小数点演算の使用によっても回避されます。
ここで、批判がコード歓迎されます:
/* 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;
}