bit.c

さて、また変なものを書きやがって、と思う人もいるかもしれませんが、
これはtwitterに(個人的に)必要なものです。
このbit.cでは、0または1を格納するbitという型を定義して、(実質はcharなので、メモリは無駄)
bit列→charに変換したり、char*から任意のbit数だけbit列に格納できるようにしています。
これを使うと、base64.cがわかりやすく作れる、はずです。
#ifndef _BIT
#define _BIT

typedef char bit;

char btoc(bit *b, int len);
void ctob(bit *b, char *c, int ofst, int len);
bit bitat(char *c, int ofst);

//bit sequence(from 1 to 8) to char
char btoc(bit *b, int len){
   int i;
   char c = 0;
   for(i = 0; i < len; ++i){c <<= 1; c |= b[i];}
   return c;
}

//read bit sequence from *c + ofst for len (in bit)
void ctob(bit *b, char *c, int ofst, int len){
   int k;
   for(k = 0; k < len; ++k) b[k] = bitat(c, ofst + k);
}

//read bit at *c + ofst (in bit)
bit bitat(char *c, int ofst){
   c += ofst / 8;
   return ((*c) >> (7 - ofst % 8)) & 1;
}

#endif
いやあ、何もインクルードしなくていいなんて、素晴らしい。
ではひとつずつ関数の説明を。

btoc関数はbit列と、その列で読む長さを受け取って、charとして返すものです。
例えば
#include <stdio.h>
#include "bit.c"

int main(){
   bit b[8] = {1,0,0,0,1,0,1,0};
   printf("%d\n", (unsigned char)btoc(b, 8)); // 10001010
   printf("%d\n", btoc(b, 4)); // 1000
   return 0;
}

というプログラムを作って実行すると、

138
8

と帰ってきます。
8bitの場合charだと1bit目が-符号と取られてちとややこしくなるので、unsigned charでキャストしてますが、
10001010 => 128 + 8 + 2 = 138
1000 => 8
となり、確かに指定された数ビット列を読み込めていることがわかります。

次にbitat関数。
これはchar*とオフセット(bit数で)を受け取り、char*の指す場所からオフセットだけ離れた場所のbitを返します。
よって8以上だと8ごとに読むバイトを変え、
8で割ったあまりによってそのバイトの中からうまいことシフト演算で読むべきbitを取り出しています。

これを使ってできるのが、ctob関数。
charのポインタを受け取って、その住所からofstビット離れた場所からlenビット読み取り、bit列に格納します。
この関数については説明はいらないでしょう。

これらを使えば、例えばリトルエンディアンかビッグエンディアンかなど、判別できます。

#include <stdio.h>
#include "bit.c"

int main(){
   int n = 1 + 2 + 256;
   char *c = (char *)&n;
   bit b[8 * sizeof(int)];
   ctob(b, c, 0, 8 * sizeof(int));
   
   int k, l;
   for(k = 0; k < sizeof(int); ++k){
      for(l = 0; l < 8; ++l) printf("%d ", b[k * 8 + l]);
      printf("\n");
   }
   return 0;
}

と、intの先頭のアドレスをchar *に変換して渡してやり、そのbit列を見てみると、

0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0

と、小さい数の方のバイトが先にあることがわかります。
これを、リトルエンディアンといいます。
普通に生活してきた私達的にはその逆のビッグエンディアンの方が自然ですが、
どうやらパソコンはこっちのほうが処理しやすいようです。
どうしてかは、まだ知りませんが…