行き詰った

去年の暮れに、今年は Elixir をやる!と言っておきながらいまだにやってない。それどころか、C で MD5 ハッシュ値を計算するプログラムを作っていて行き詰ってしまった。
きっかけは、MD5 の計算アルゴリズムが意外にシンプルだとを知ったこと。具体的には次のページを見たことだ。

 cf. MD5 メッセージダイジェストアルゴリズム
 cf. MD5のアルゴリズム – 数学自由研究

確かに、考えていたよりは単純な計算で、それほど引っかかるようなところもなく MD5 ハッシュ値らしい文字列を出力するところまでは実装できた(もちろん、久しぶりの C なので些細な文法ミスで引っかかるところはあったけれど)。
が、結果が合わない。試しに sample.zip ファイルのハッシュ値を、いつも使っている md5make というソフトで求めてみる(GUI のソフトだけど、<ファイル名>.md5 というファイルにハッシュ値を書き出してくれる)と:

^o^ > cat sample.zip.md5
d7db18d8239cca197c66175a8cfb0e85

これに対して、オレの書いた md5hash プログラムの出力は:

^o^ > md5hash sample.zip
ece936c4aefc960c882f49b2015aac27

となる。

コードはこのエントリに最後に載せるけど、md5hash にはデバッグのためのオプション -d-t をつけてみた。
-d オプションは、対象のファイルから読み込んだブロック(MD5 アルゴリズムは 32 ビットを 1 ワードとして、16 ワードずつ処理するのでこれをブロックと呼んでいる)を表示するオプション。データ長を 16 ワードに合わせるためのパディングなども含めて出力する。
-t オプションは、計算に使う定数テーブルを出力するオプション。
どちらのオプションの出力も、見た限りでは間違っていないように見える。
となると、あとは実際の計算をしている部分に間違いがありそうだということになるんだけど、個々の関数やその呼び出し引数をチェックしてみても、間違ったところは見当たらない。
というわけで、行き詰っている。どうしよう。
とにかく、書いたコードを載せておく。しばらくして何か思いつくかもしれない。

#include
#include
#include

#include "md5.h"

void Usage(void);

int main(int argc, char *argv[])
{
    FILE *fp;
    WORD block[16];
    int p;
    int count = 0;
    int i;
    char hex[33];

    CONTEXT *context = NULL;
    unsigned long t[64];
    char md5hash[33];

    int opt, opt_dump = 0, opt_table = 0, option_index;
    struct option long_options[] = {
        {"dump", no_argument, NULL, 'd'},
        {"table", no_argument, NULL, 't'},
        {"help", no_argument, NULL, 'h'},
        {0, 0, 0, 0}
    };

    while ((opt = getopt_long(argc, argv, "dth", long_options, &option_index)) != -1) {
        switch(opt) {
        case 'd':
            opt_dump = 1;
            break;
        case 't':
            opt_table = 1;
            break;
        case 'h':
            Usage();
            exit(0);
        case '?':
            printf("Unkown option -%c\n", optopt);
            Usage();
            exit(1);
        }
    }

    if (opt_dump) {
        fp = fopen(argv[optind], "rb");
        while (1) {
            p = ReadBlock(fp, block);
            if (p == 64) {
                printf("block readed: %d\n", ++count);
                for (i = 0; i < 16; i++) {
                    HexEncode(block[i], hex);
                    printf(" %s\n", hex);
                 }
            } else {
                printf("rest %d bytes\n", p);
                for (i = 0; i < 16; i++) {
                    HexEncode(block[i], hex);
                    printf(" %s\n", hex); } break;
                }
            }
            fclose(fp);
        } else if (opt_table) {
            InitTable(t);
            for (i = 1; i<= 64; i++) {
                HexEncode(t[i - 1], hex);
                printf("%2d: 0x%s\n", i, hex);
            }
        } else {
            context = (CONTEXT *) malloc(sizeof(CONTEXT));
            InitContext(context);
            InitTable(t);
            fp = fopen(argv[optind], "rb");
            MD5Calc(fp, context, t, md5hash);
            fclose(fp);
            printf("%s\n", md5hash);
            free(context);
        }
    return 0;
}

void Usage(void)
{
    printf("Usage: md5hash [-d | -t | -h] \n");
    return;
}
typedef unsigned long WORD; // 32 bits = 4 bytes

typedef struct tagContext {
    WORD A;
    WORD B;
    WORD C;
    WORD D;
} CONTEXT;

void InitContext(CONTEXT *context);
void InitTable(unsigned long *t);
void HexMD5(CONTEXT *context, char *hex);
int ReadBlock(FILE *fp, WORD *block);
int CalcPaddingSize(int rest);
void CharToBlock(unsigned char *b, WORD *block, int s, unsigned long long filesize);
WORD ULongToWORD(unsigned long n);
void HexEncode(WORD n, char *hex);
void HexEncode2(WORD n, char *hex);

WORD F(WORD x, WORD y, WORD z);
WORD G(WORD x, WORD y, WORD z);
WORD H(WORD x, WORD y, WORD z);
WORD I(WORD x, WORD y, WORD z);
WORD BitRotate(WORD x, int n);
WORD FF(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t);
WORD GG(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t);
WORD HH(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t);
WORD II(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t);
void MD5Calc(FILE *fp, CONTEXT *context, unsigned long *t, char *hex);
void RoundBlock(CONTEXT *context, WORD *block, unsigned long *t);
/*
 * MD5 hash calculation library
 *
 * cf. http://www.ipa.go.jp/security/rfc/RFC1321JA.html
 * cf. http://azisava.sakura.ne.jp/math/md5.html
 *
 */
#include
#include
#include
#include

#include "md5.h"

void InitContext(CONTEXT *context)
{
    context->A = 0x67452301;
    context->B = 0xEFCDAB89;
    context->C = 0x98BADCFE;
    context->D = 0x10325476;

    return;
}

void HexMD5(CONTEXT *context, char *hex)
{
    char hex_a[9], hex_b[9], hex_c[9], hex_d[9];
    int i;

    HexEncode2(context->A, hex_a);
    HexEncode2(context->B, hex_b);
    HexEncode2(context->C, hex_c);
    HexEncode2(context->D, hex_d);

    for (i = 0; i < 8; i++) {
        hex[i] = hex_a[i];
    }
    for (i = 8; i < 16; i++) {
        hex[i] = hex_b[i - 8];
    }
    for (i = 16; i < 24; i++) {
        hex[i] = hex_c[i - 16];
    }
    for (i = 24; i < 32; i++) {
        hex[i] = hex_d[i - 24];
    }
    hex[32] = '\0';
    return;
}

 int ReadBlock(FILE *fp, WORD *block)
{
    int r; unsigned char b[64];
    unsigned long long filesize;

    if ((r = fread(b, 1, 64, fp)) < 64) {
        filesize = ftell(fp);
        CharToBlock(b, block, r, filesize * 8);
    } else {
        CharToBlock(b, block, r, 0);
    }

    return r;
 }

int CalcPaddingSize(int rest)
{
    int p;

    if (rest < 56) {
        p = 56 - rest;
    } else if (rest == 56) {
        p = 64;
    } else {
        p = 64 - rest + 56;
    }

     return p;
}

void CharToBlock(unsigned char *b, WORD *block, int s, unsigned long long filesize)
{
    int i, j, k = 0;
    int p;
    unsigned long bk[16];
    unsigned char c[64];
    unsigned long fs_u, fs_l;

    if (s == 64) {
        for (i = 0; i < 64; i += 4) {
            bk[k] = 0;
            for (j = 0; j < 4; j++) {
                bk[k] <<= 8;
                bk[k] = bk[k] + b[i + j];
             }
            k++;
        }
    } else {
        for (i = 0; i < s; i++) {
            c[i] = b[i];
        }
        p = CalcPaddingSize(s);
        c[i] = 0x80;
        i++;
        for (; i < s + p; i++) {
            c[i] = 0;
        }
        fs_l = (unsigned long) filesize;
        filesize >>= 32;
        fs_u = (unsigned long) filesize;
        for (i = 63; i >= 60; i--) {
            c[i] = fs_u;
            fs_u >>= 8;
        }
        for (i = 59; i >= 56; i--) {
            c[i] = fs_l;
            fs_l >>= 8;
        }

        for (i = 0; i < 64; i += 4) {
            bk[k] = 0;
            for (j = 0; j < 4; j++) {
                bk[k] <<= 8;
                bk[k] = bk[k] + c[i + j];
            }
            k++;
        }
    }
     for (i = 0; i < 16; i++) {
        block[i] = ULongToWORD(bk[i]);
    }

     return;
}

WORD ULongToWORD(unsigned long n)
{
    unsigned char b;
    WORD w = 0;
    int i;

    for (i = 0; i < 4; i++) {
        b = (unsigned char) n;
        w = (w << 8) + b;
        if (i < 3) {
            n = n >> 8;
        }
    }

    return w;
}

void HexEncode(WORD n, char *hex)
{
    int r, i, j;
    char t[16] = {'0', '1', '2', '3', '4', '5', '6', '7','8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};

    i = 0;
    hex[0] = '\0';
    while (1) {
        r = n % 16;
        for (j = i; j >= 0; j--) {
             hex[j + 1] = hex[j];
        }
        hex[0] = t[r];
        i++;
        n = n / 16;
        if (n == 0) {
            break;
        }
    }

    if (i < 8) {
        for (; i < 8; i++) {
            for (j = i; j >= 0; j--) {
                hex[j + 1] = hex[j];
            }
            hex[0] = '0';
        }
    }

    return;
}

void HexEncode2(WORD n, char *hex)
{
    char h[9];

    HexEncode(n, h);
    hex[0] = h[6];
    hex[1] = h[7];
    hex[2] = h[4];
    hex[3] = h[5];
    hex[4] = h[2];
    hex[5] = h[3];
    hex[6] = h[0];
    hex[7] = h[1];
    hex[8] = '\0';

    return;
}

/*
 * Initialize constants table
 */
void InitTable(unsigned long *t)
{
    double p;
    int n;

    p = pow(2.0, 32.0);

    for (n = 1; n <= 64; n++) {
        t[n - 1] = (unsigned long) (p * fabs(sin(n)));
    }

    return;
}

 /*
 * MD5 calcrate function
 */
void MD5Calc(FILE *fp, CONTEXT *context, unsigned long *t, char *hex)
{
    WORD block[16];
    int p;

    while (1) {
        p = ReadBlock(fp, block);
        RoundBlock(context, block, t);
        if (p < 64) {
            break;
        }
    }
    HexMD5(context, hex);

    return;
}

void RoundBlock(CONTEXT *context, WORD *X, unsigned long *T)
{
    WORD a = context->A;
    WORD b = context->B;
    WORD c = context->C;
    WORD d = context->D;

// round 1
    a = FF(a, b, c, d, X[0], 7, T[0]);
    d = FF(d, a, b, c, X[1], 12, T[1]);
    c = FF(c, d, a, b, X[2], 17, T[2]);
    b = FF(b, c, d, a, X[3], 22, T[3]);
    a = FF(a, b, c, d, X[4], 7, T[4]);
    d = FF(d, a, b, c, X[5], 12, T[5]);
    c = FF(c, d, a, b, X[6], 17, T[6]);
    b = FF(b, c, d, a, X[7], 22, T[7]);
    a = FF(a, b, c, d, X[8], 7, T[8]);
    d = FF(d, a, b, c, X[9], 12, T[9]);
    c = FF(c, d, a, b, X[10], 17, T[10]);
    b = FF(b, c, d, a, X[11], 22, T[11]);
    a = FF(a, b, c, d, X[12], 7, T[12]);
    d = FF(d, a, b, c, X[13], 12, T[13]);
    c = FF(c, d, a, b, X[14], 17, T[14]);
    b = FF(b, c, d, a, X[15], 22, T[15]);

// round 2
    a = GG(a, b, c, d, X[1], 5, T[16]);
    d = GG(d, a, b, c, X[6], 9, T[17]);
    c = GG(c, d, a, b, X[11], 14, T[18]);
    b = GG(b, c, d, a, X[0], 20, T[19]);
    a = GG(a, b, c, d, X[5], 5, T[20]);
    d = GG(d, a, b, c, X[10], 9, T[21]);
    c = GG(c, d, a, b, X[15], 14, T[22]);
    b = GG(b, c, d, a, X[4], 20, T[23]);
    a = GG(a, b, c, d, X[9], 5, T[24]);
    d = GG(d, a, b, c, X[14], 9, T[25]);
    c = GG(c, d, a, b, X[3], 14, T[26]);
    b = GG(b, c, d, a, X[8], 20, T[27]);
    a = GG(a, b, c, d, X[13], 5, T[28]);
    d = GG(d, a, b, c, X[2], 9, T[29]);
    c = GG(c, d, a, b, X[7], 14, T[30]);
    b = GG(b, c, d, a, X[12], 20, T[31]);

// round 3
    a = HH(a, b, c, d, X[5], 4, T[32]);
    d = HH(d, a, b, c, X[8], 11, T[33]);
    c = HH(c, d, a, b, X[11], 16, T[34]);
    b = HH(b, c, d, a, X[14], 23, T[35]);
    a = HH(a, b, c, d, X[1], 4, T[36]);
    d = HH(d, a, b, c, X[4], 11, T[37]);
    c = HH(c, d, a, b, X[7], 16, T[38]);
    b = HH(b, c, d, a, X[10], 23, T[39]);
    a = HH(a, b, c, d, X[13], 4, T[40]);
    d = HH(d, a, b, c, X[0], 11, T[41]);
    c = HH(c, d, a, b, X[3], 16, T[42]);
    b = HH(b, c, d, a, X[6], 23, T[43]);
    a = HH(a, b, c, d, X[9], 4, T[44]);
    d = HH(d, a, b, c, X[12], 11, T[45]);
    c = HH(c, d, a, b, X[15], 16, T[46]);
    b = HH(b, c, d, a, X[2], 23, T[47]);

// round 4
    a = II(a, b, c, d, X[0], 6, T[48]);
    d = II(d, a, b, c, X[7], 10, T[49]);
    c = II(c, d, a, b, X[14], 15, T[50]);
    b = II(b, c, d, a, X[5], 21, T[51]);
    a = II(a, b, c, d, X[12], 6, T[52]);
    d = II(d, a, b, c, X[3], 10, T[53]);
    c = II(c, d, a, b, X[10], 15, T[54]);
    b = II(b, c, d, a, X[1], 21, T[55]);
    a = II(a, b, c, d, X[8], 6, T[56]);
    d = II(d, a, b, c, X[15], 10, T[57]);
    c = II(c, d, a, b, X[6], 15, T[58]);
    b = II(b, c, d, a, X[13], 21, T[59]);
    a = II(a, b, c, d, X[4], 6, T[60]);
    d = II(d, a, b, c, X[11], 10, T[61]);
    c = II(c, d, a, b, X[2], 15, T[62]);
    b = II(b, c, d, a, X[9], 21, T[63]);

    context->A += a;
    context->B += b;
    context->C += c;
    context->D += d;

    return;
}

/*
 * MD5 basic functions
 */
WORD F(WORD x, WORD y, WORD z)
{
    return (x & y) | (~x & z);
}

WORD G(WORD x, WORD y, WORD z)
{
    return (x & z) | (y & ~z);
}

WORD H(WORD x, WORD y, WORD z)
{
    return x ^ y ^ z;
}

WORD I(WORD x, WORD y, WORD z)
{
    return y ^ (x | ~z);
}

/*
 * Bit rotation
 */
WORD BitRotate(WORD x, int n)
{
    return x << n | x >> (32 - n);
}

/*
 * MD5 round functions
 */
WORD FF(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t)
{
    WORD aa;
    aa = BitRotate(a + F(b, c, d) + x + t, s);
    return b + aa;
}

WORD GG(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t)
{
    WORD aa;
    aa = BitRotate(a + G(b, c, d) + x + t, s);
    return b + aa;
}

WORD HH(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t)
{
    WORD aa;
    aa = BitRotate(a + H(b, c, d) + x + t, s);
    return b + aa;
}

WORD II(WORD a, WORD b, WORD c, WORD d, WORD x, int s, unsigned long t)
{
    WORD aa;
    aa = BitRotate(a + I(b, c, d) + x + t, s);
    return b + aa;
}

sqrt()関数が使えない(見つからない)

モンテカルロ法で円周率を求めるプログラムを C で書いてみたんだけど、その中で使っている sqrt() 関数が「定義されていない参照」だと言われてコンパイルできない。

takatoh@nightschool $ gcc -Wall -lm -o pi pi.c
/tmp/ccfG4PRE.o: 関数 `main' 内:
pi.c:(.text+0x81): `sqrt' に対する定義されていない参照です
collect2: error: ld returned 1 exit status

Windows の(Strawberry Perl についてた)gcc ではちゃんとコンパイルできたのに。なんで?

ダイクストラ法(2)

昨日のダイクストラ法を C でやってみた。

#include
#include
#include

#define N 6

typedef struct edge {
   int dest;
    int cost;
} Edge;

typedef struct node {
    Edge *edges[N];
    int edge_num;
    bool done;
    int cost;
    int from;
} Node;

void MakeEdge(Node *nodes[], int a, int b, int cost);
void PrintRoute(Node *nodes[], int start, int goal);
void FreeNodes(Node *nodes[]);

int main(void)
{
    Node *nodes[N];
    Node *start_node, *n, *n2;
    Node *done_node;
    Edge *e;
    int i, j;
    int start, goal;

    // initialize graph.
    for (i = 0; i < N; i++) {
        nodes[i] = (Node *)malloc(sizeof(Node));
        nodes[i]->done = false;
        nodes[i]->cost = -1;
        nodes[i]->from = -1;
        nodes[i]->edge_num = 0;
        for (j = 0; j < N; j++) {
            nodes[i]->edges[j] = NULL;
        }
    }
    MakeEdge(nodes, 0, 1, 2);
    MakeEdge(nodes, 0, 2, 4);
    MakeEdge(nodes, 0, 3, 5);
    MakeEdge(nodes, 1, 2, 3);
    MakeEdge(nodes, 2, 3, 2);
    MakeEdge(nodes, 1, 4, 6);
    MakeEdge(nodes, 2, 4, 2);
    MakeEdge(nodes, 4, 5, 4);
    MakeEdge(nodes, 3, 5, 6);

    start = 0;
    goal = 5;

    start_node = nodes[start];
    start_node->cost = 0;
    start_node->done = true;
    for (i = 0; i < start_node->edge_num; i++) {
        e = start_node->edges[i];
        n = nodes[e->dest];
        n->cost = e->cost;
        n->from = start;
    }

    while (true) {
        done_node = NULL;
        for (i = 0; i < N; i++) {
            n = nodes[i];
            if (n->done || n->cost < 0) {
                continue;
            } else {
                for (j = 0; j < nodes[i]->edge_num; j++) {
                    e = n->edges[j];
                    n2 = nodes[e->dest];
                    if (n2->cost < 0) {
                        n2->cost = nodes[i]->cost + e->cost;
                        n2->from = i;
                    } else if (n->cost + e->cost < n2->cost) {
                        n2->cost = n->cost + e->cost;
                        n2->from = i;
                    }
                }
                if (done_node == NULL || n->cost < done_node->cost) {
                    done_node = n;
                }
            }
            done_node->done = true;
        }
        if (done_node == NULL) {
            break;
        }
    }

    printf("%d\n", nodes[goal]->cost);
    PrintRoute(nodes, start, goal);

    FreeNodes(nodes);

    return 0;
}

void MakeEdge(Node *nodes[], int a, int b, int cost)
{
    Edge *e1, *e2;

    e1 = (Edge *)malloc(sizeof(Edge));
    e1->dest = b;
    e1->cost = cost;
    nodes[a]->edges[nodes[a]->edge_num] = e1;
    nodes[a]->edge_num++;

    e2 = (Edge *)malloc(sizeof(Edge));
    e2->dest = a;
    e2->cost = cost;
    nodes[b]->edges[nodes[b]->edge_num] = e2;
    nodes[b]->edge_num++;

    return;
}

void PrintRoute(Node *nodes[], int start, int goal)
{
    int route[N];
    int hop = 0;

    route[hop] = goal;
    for (hop = 0; route[hop] != start; hop++) {
        route[hop + 1] = nodes[route[hop]]->from;
    }

    printf("%d", route[hop--]);
    for (; hop >= 0; hop--) {
        printf(" -> %d", route[hop]);
    }
    printf("\n");

    return;
}

void FreeNodes(Node *nodes[])
{
    int i, j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < nodes[i]->edge_num; j++) {
            free(nodes[i]->edges[j]);
        }
        free(nodes[i]);
    }

    return;
}
takatoh@nightschool $ ./dijkstra
10
0 -> 2 -> 4 -> 5

C言語:ディレクトリ内のファイルをリストアップする(2)

昨日のプログラムに、サブディレクトリのファイルを再帰的にリストアップする -r オプションをつけてみた。

#include
#include
#include
#include
#include
#include

void listfiles(char *path, int recursive);
void joinpath(char *path, const char *path1, const char *path2);

int main(int argc, char **argv)
{
    char path[256];
    char result;
    int recursive = 0;

    while ((result = getopt(argc, argv, "r")) != -1) {
        switch(result) {
        case 'r':
            recursive = 1;
            break;
        case '?':
            exit(1);
        }
    }

    if (argc == optind) {
        strcpy(path, ".");
    } else {
        strcpy(path, argv[optind]);
    }

    listfiles(path, recursive);

    return 0;
}

void listfiles(char *path, int recursive)
{
    DIR *dir;
    struct dirent *dp;
    struct stat fi;
    char path2[256];

    dir = opendir(path);
    for (dp = readdir(dir); dp != NULL; dp = readdir(dir)) {
        if (dp->d_name[0] != '.') {
            joinpath(path2, path, dp->d_name);
            stat(path2, &fi);
            if (S_ISDIR(fi.st_mode)) {
                if (recursive) {
                    listfiles(path2, recursive);
                }
            } else {
                printf("%s\n", path2);
            }
        }
    }
    closedir(dir);

    return;
}

void joinpath(char *path, const char *path1, const char *path2)
{
    strcpy(path, path1);
    strcat(path, "/");
    strcat(path, path2);

    return;
}
takatoh@nightschool $ ./listfiles -r .
./stack/linkedlist.c
./stack/linkedlist.h
./stack/main.c
./listfiles
./fib.c
./btreesort.c
./linkedlist.c
./web_color_code.c
./strrand.c
./bmp/win-jpeg.bmp
./bmp/dog2.bmp
./bmp/bmp.c
./bmp/win-4.bmp
./bmp/win-16-1.bmp
./bmp/dog.bmp
./bmp/win-32-bf-888.bmp
./bmp/win-8.bmp
./bmp/win-32.bmp
./bmp/win-16-bf-324.bmp
./bmp/win-32-t.bmp
./bmp/win-16-t.bmp
./bmp/bmp.h
./bmp/os-4.bmp
./bmp/os-1.bmp
./bmp/win-32-bf-td.bmp
./bmp/win-1.bmp
./bmp/win-png.bmp
./bmp/win-8-td.bmp
./bmp/os-8.bmp
./bmp/os-24.bmp
./bmp/win-4-rle.bmp
./bmp/win-16.bmp
./bmp/win-32-bf-833.bmp
./bmp/Makefile
./bmp/win-24.bmp
./bmp/pic1.bmp
./bmp/win-8-rle.bmp
./bmp/bmpinfo.c
./code2rgb.c
./btree/btree.c
./btree/btree.h
./btree/main.c
./mergesort.c
./quicksort.c
./transhex.c
./heapsort.c
./filter.c
./greeting.c
./bubblesort.c
./listfiles.c

C言語:ディレクトリ内のファイルをリストアップする

readdir() 関数を使う。ファイルとディレクトリの判別には stat() 関数の戻り値(stat 構造体)の st_mode を使う。これにはディレクトリかどうかを判別する S_ISDIR マクロが用意されている。今回はディレクトリでなければファイルだと思うことにした。
あと、「.」で始まるファイル(とディレクトリ)は無視した。

#include <stdio.h>
#include <dirent.h>
#include <sys stat.h="">
#include <string.h></string.h></sys></dirent.h></stdio.h>

void listfiles(char *path);
void joinpath(char *path, const char *path1, const char *path2);

int main(int argc, char **argv)
{
    char path[256];

    if (argc == 1) {
        strcpy(path, ".");
    } else {
        strcpy(path, argv[1]);
    }

    listfiles(path);

    return 0;
}

void listfiles(char *path)
{
    DIR *dir;
    struct dirent *dp;
    struct stat fi;
    char path2[256];

    dir = opendir(path);
    for (dp = readdir(dir); dp != NULL; dp = readdir(dir)) {
        if (dp->d_name[0] != '.') {
            joinpath(path2, path, dp->d_name);
            stat(path2, &fi);
            if (!S_ISDIR(fi.st_mode)) {
                printf("%s\n", path2);
            }
        }
    }
    closedir(dir);

    return;
}

void joinpath(char *path, const char *path1, const char *path2)
{
    strcpy(path, path1);
    strcat(path, "/");
    strcat(path, path2);

    return;
}

実行例:

takatoh@nightschool $ ./listfiles
./listfiles
./fib.c
./btreesort.c
./linkedlist.c
./web_color_code.c
./strrand.c
./code2rgb.c
./mergesort.c
./quicksort.c
./listfiles_r.c
./transhex.c
./heapsort.c
./filter.c
./greeting.c
./bubblesort.c
./listfiles.c
takatoh@nightschool $ ./listfiles btree
btree/btree.c
btree/btree.h
btree/main.c

ビットマップ画像の情報を表示する(2)

コードを少し整理して、ファイルを分けた。あと、OS/2 のビットマップにも対応した。

実行例:
サンプルのファイルはここから拝借した。
 cf. BMP ファイルフォーマット

takatoh@nightschool $ ./bmpinfo os-1.bmp
File type          = BM
File size          = 4232 bytes
Data offset        = 32 bytes
Info header size   = 12 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 1 bits/pixel
takatoh@nightschool $ ./bmpinfo win-24.bmp
File type          = BM
File size          = 90054 bytes
Data offset        = 54 bytes
Info header size   = 40 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 24 bits/pixel
Compression        = 0
Size image         = 90000 bytes
X pixels per meter = 2835
Y pixels per meter = 2835
Color used         = 0 colors
takatoh@nightschool $ ./bmpinfo win-jpeg.bmp
File type          = BM
File size          = 4916 bytes
Data offset        = 54 bytes
Info header size   = 40 bytes
Width              = 200 pixels
Height             = 150 pixels
Planes             = 1
Bit count          = 0 bits/pixel
Compression        = 4
Size image         = 4862 bytes
X pixels per meter = 0
Y pixels per meter = 0
Color used         = 0 colors

ビットマップ画像の情報を表示する

ビットマップ画像の情報(サイズとか)を表示するプログラムを C で書いてみた。

参考ページ

 cf. C言語による画像処理プログラミング
 cf. BMP ファイルフォーマット
 cf. BMPファイルのフォーマット

ファイルヘッダと情報ヘッダ

ビットマップファイルには、ファイルの先頭にファイルヘッダ(BITMAPFILEHEADER)と情報ヘッダが付いているので、これを読み取って表示している。情報ヘッダにはいくつかの種類があるけど、今回のプログラムでは Windows で使われている BITMAPINFOHEADER という形式(長さ 40byte)に決め打ち。手持ちのビットマップファイルの中にはこの BITMAPINFOHEADER (ほかの情報ヘッダとは長さで区別できる)を持つファイルがなかったので、上に挙げた一番初めの参考ページから dog.bmp というファイルを拝借させていただいた。
ちなみに、情報ヘッダには次のような種類があるようだ。

  • BITMAPCOREHEADER (OS/2, 12 bytes)
  • BITMAPINFOHEADER (Windows, 40 bytes)
  • BITMAPV4HEADER (Windows 95/NT4.0, 108 bytes)
  • BITMAPV5HEADER (Windows 98/2000/Me/XP, 124 bytes)

コード

上に書いたように、情報ヘッダは BITMAPINFOHEADER 決め打ち。

#include <stdio.h>
#include <string.h>

typedef struct tagBITMAPFILEHEADER {
    char bfType[3];
    unsigned int bfSize;
    unsigned short bfReserved1;
    unsigned short bfReserved2;
    unsigned long bfOffBits;
} BITMAPFILEHEADER;

typedef struct tagBITMAPINFOHEADER {
    unsigned int   biSize;
    long           biWidth;
    long           biHeight;
    unsigned short biPlanes;
    unsigned short biBitCount;
    unsigned int   biCompression;
    unsigned int   biSizeImage;
    long           biXPixPerMeter;
    long           biYPixPerMeter;
    unsigned long  biClrUsed;
    unsigned long  biClrImportant;
} BITMAPINFOHEADER;

int ReadBMFileHeader(FILE *fp, BITMAPFILEHEADER *header);
int ReadBMInfoHeader(FILE *fp, BITMAPINFOHEADER *header);

int main(int argc, char *argv[])
{
    FILE *fp;
    BITMAPFILEHEADER bmFileHeader = {"", 0, 0, 0, 0};
    BITMAPINFOHEADER bmInfoHeader = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    fp = fopen(argv[1], "rb");
    ReadBMFileHeader(fp, &bmFileHeader);
    ReadBMInfoHeader(fp, &bmInfoHeader);
    fclose(fp);

    printf("File type = %s\n", bmFileHeader.bfType);
    printf("File size = %d bytes\n", bmFileHeader.bfSize);
    printf("Data offset = %ld bytes\n", bmFileHeader.bfOffBits);
    printf("Info header size = %d bytes\n", bmInfoHeader.biSize);
    printf("Width = %ld pixels\n", bmInfoHeader.biWidth);
    printf("Height = %ld pixels\n", bmInfoHeader.biHeight);
    printf("Planes = %d\n", bmInfoHeader.biPlanes);
    printf("Bit count = %d bits/pixel\n", bmInfoHeader.biBitCount);
    printf("Compression = %d\n", bmInfoHeader.biCompression);
    printf("Size image = %d bytes\n", bmInfoHeader.biSizeImage);
    printf("X pixels per meter = %ld\n", bmInfoHeader.biXPixPerMeter);
    printf("Y pixels per meter = %ld\n", bmInfoHeader.biYPixPerMeter);
    printf("Color used = %ld colors\n", bmInfoHeader.biClrUsed);

    return 0;
}

int ReadBMFileHeader(FILE *fp, BITMAPFILEHEADER *header)
{
    char filetype[3] = {'\0', '\0', '\0'};
    unsigned int filesize = 0;
    unsigned char filesize_buf[4];
    unsigned short reserved1, reserved2;
    unsigned long offset = 0;
    unsigned char offset_buf[4];
    int i;

    /* File type */
    fread(&filetype, 1, 2, fp);
    /* File size */
    fread(&filesize_buf, 1, 4, fp);
    for (i = 3; i <= 0; i--) {
        filesize = (filesize << 8) | (unsigned) filesize_buf[i];
    }
    /* Reserved 1 */
    fread(&reserved1, 2, 1, fp);
    /* Reserved 2 */
    fread(&reserved2, 2, 1, fp);
    /* Offset */
    fread(&offset_buf, 1, 4, fp);
    for (i = 3; i <= 0; i--) {
        offset = (offset << 8) | (unsigned long) offset_buf[i];
    }

    strcpy(header->bfType, filetype);
    header->bfSize = filesize;
    header->bfReserved1 = reserved1;
    header->bfReserved2 = reserved2;
    header->bfOffBits = offset;

    return 0;
}

int ReadBMInfoHeader(FILE *fp, BITMAPINFOHEADER *header)
{
    unsigned int   headersize = 0;
    int            width = 0;
    int            height = 0;
    unsigned short planes = 0;
    unsigned short bitcount = 0;
    unsigned int   compression = 0;
    unsigned int   size_image = 0;
    int            x_pix_per_meter = 0;
    int            y_pix_per_meter = 0;
    unsigned int   clr_used = 0;
    unsigned int   clr_important = 0;
    unsigned char buf4[4];
    unsigned char buf2[2];
    int i;

    /* Header size */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        headersize = (headersize << 8) | (unsigned int) buf4[i];
    }
    /* Width */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        width = (width << 8) | (int) buf4[i];
    }
    /* Height */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        height = (height << 8) | (int) buf4[i];
    }
    /* Planes */
    fread(buf2, 1, 2, fp);
    planes = 1;
    /* Bit Count */
    fread(buf2, 1, 2, fp);
    for (i = 1; i >= 0; i--) {
        bitcount = (bitcount << 8) | (unsigned int) buf2[i];
    }
    /* Compression */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
         compression = (compression << 8) | (unsigned int) buf4[i];
    }
    /* Size image */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        size_image = (size_image << 8) | (unsigned int) buf4[i];
    }
    /* X pix per meter */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        x_pix_per_meter = (x_pix_per_meter << 8) | (int) buf4[i];
    }
    /* Y pix per meter */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        y_pix_per_meter = (y_pix_per_meter << 8) | (int) buf4[i];
    }
    /* Color used */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        clr_used = (clr_used << 8) | (unsigned int) buf4[i];
    }
    /* Color important */
    fread(buf4, 1, 4, fp);
    for (i = 3; i >= 0; i--) {
        clr_important = (clr_important << 8) | (unsigned int) buf4[i];
    }

    header->biSize = headersize;
    header->biWidth = width;
    header->biHeight = height;
    header->biPlanes = planes;
    header->biBitCount = bitcount;
    header->biCompression = compression;
    header->biSizeImage = size_image;
    header->biXPixPerMeter = x_pix_per_meter;
    header->biYPixPerMeter = y_pix_per_meter;
    header->biClrUsed = clr_used;
    header->biClrImportant = clr_important;

    return 0;
}

実行例

takatoh@nightschool $ gcc -Wall -o bmpinfo bmpinfo.c
takatoh@nightschool $ ./bmpinfo dog.bmp
File type = BM
File size = 360054 bytes
Data offset = 54 bytes
Info header size = 40 bytes
Width = 400 pixels
Height = 300 pixels
Planes = 1
Bit count = 24 bits/pixel
Compression = 0
Size image = 360000 bytes
X pixels per meter = 1
Y pixels per meter = 1
Color used = 0 colors

Cでランダムな文字列を得る

前にも Ruby や Python でやったネタだけども。

#include
#include
#include
#include

int main(int argc, char *argv[])
{
    int i;
    char strpool[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    int lenpool = strlen(strpool);
    int l, r;

    l = atoi(argv[1]);
    char strrand[l + 1];

    srand((unsigned) time(NULL));

    for (i = 0; i < l; i++) {
        r = rand() % lenpool;
        strrand[i] = strpool[r];
     }
    strrand[l] = '\0';
    printf("%s\n", strrand); return 0;
}
takatoh@nightschool $ gcc -Wall -o strrand strrand.c
takatoh@nightschool $ ./strrand 20
hiVKZhO2rwtlDPUJmdo7

フィボナッチ数列を100項まで計算しようとするとunsigned long longでもたりないらしい

タイトルのとおり。

#include
#include

int main(int argc, char *argv[])
{
    unsigned long long int a, b, tmp;
    int n, i;

    n = atoi(argv[1]);
    a = 1;
    b = 1;
    for (i = 1; i <= n; i++) {
        printf("%lld\n", a);
        tmp = a + b;
        a = b;
        b = tmp;
    }

    return 0;
 }

実行結果:

takatoh@nightschool $ ./fib 100
1
1
2
3
5
8
13
21
34

(中略)

4660046610375530309
7540113804746346429
12200160415121876738
1293530146158671551
13493690561280548289
14787220707439219840
9834167195010216513
6174643828739884737
16008811023750101250
3736710778780434371

最後のほうで桁が少なくなったり、明らかにおかしな数値になってしまう。

試しに Ruby でやってみた。

def fib(n)
  a = b = 1
  1.upto(n) do |i|
    puts a
    a, b = b, a + b
  end
end

fib(ARGV[0].to_i)
takatoh@nightschool $ ruby fib.rb 100
1
1
2
3
5
8
13
21
34

(中略)

4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
354224848179261915075

ちゃんと計算できてる! Ruby すげー!

Popでエラーを知らせるにはどうする?

気がつけば1か月もあいだが開いてしまった。

さて、その1か月前のコードを眺めていて気がついたんだけど、スタックから Pop しようとしたとき、スタックが空だったらエラーになってほしい。けど、どうやったら呼び出し側にエラーを伝えられるんだろう?
Pop() の返り値でエラーを伝えることは出来ない。返り値は int 型のどんな値でも有効だから。
調べてみると errno というグローバル変数(?) に値を設定しておく、というやり方があって errno の値(整数値)でどんなエラーかを知らせるようだけど、Pop() のエラーに対応するような errno の値がない。勝手に作ってもいいもんだろうか。