acl4の開発ログ
- 最近の過去ログ:
- a4_log08(2026.03.14(土)#0~2026.03.17(火)#2): プリプロセッサ的な置換ルールだけで、コンパイラの大半の処理をやってしまえば、コンパイラはすごく作りやすくなるかもしれないという構想を思いつく。→ミニコンパイラ構想。および試作。
- a4_log09(2026.03.18(水)#0~2026.03.26(木)#5): 有理数型を作ろうと思ったけど、途中から浮動小数点数から近い有理数を探すアルゴリズムに注目。
- a4_log10(2026.03.27(金)#0~2026.04.10(金)#3): プリプロセッサの連鎖でコンパイラを構成するやり方を引き続き試作。
2026.04.11(土) #0
- 今後の予定:
- ソースコードを少しだけ整えたあとで、以下のことをやりたいです。
- [1] tt0003b.c (2026.03.17(火)#2→a4_log08) で作ったミニコンパイラと今回作った typedDef 付きのプリプロセッサ関数で、簡易Cインタプリタを試作したい。
- [2] 同様にミニコンパイラと適当な定義ファイルで、x86用の簡易Cコンパイラを試作したい。
- [3] 同様にミニコンパイラと適当な定義ファイルで、簡易JITコンパイラを試作したい。
2026.04.11(土) #1
- 今ふと思ったんですが、プリプロセッサのマクロって面白いですよね。
- 普通のプログラムだと、変数への代入順序はとても重要です。
a=1;
b=2;
c=a+b;
printf("%d\n", c);
- これがプリプロセッサだと逆順に書いてもうまくいってしまうのです。
#define c a+b
#define b 2
#define a 1
printf("%d\n", c);
- 当たり前なんだけど、なんだかおもしろいです。
- (ちなみに逆順に限らず、3行のdefineはどんな順序で書いても問題なく動きます。)
2026.04.11(土) #2
- acl4をたくさん使ってだんだんわかってきたので、もっと使いやすくするために、全面的に書き換えたいなという気分になってきました。
- 上記の簡易Cインタプリタ・簡易Cコンパイラ・簡易C-JITコンパイラができたら、acl4v1に移行しようかなと検討中です。
- メモリリーク発見機能が大活躍なので、もうちょっと強化したい。
- プログラムの部品化の粒度を見直したい。
2026.04.12(日) #0
- なんか気分が乗ってきたので、全面書き直しのほうを先にやってみました。・・・ってまだ半分くらいしかできていませんが。
- 旧acl4では、メモリリークの一覧が簡単に見えてとても便利でしたが、acl4v1では、それに加えて init はしたけど deinit はしてないオブジェクトの一覧が出ます。これがもう「うきょー」って言いたくなるくらい便利です(笑)。
- 例えば以下は、a4_0005に書いたt0005b.cを改造したものです。
// tt0005a.c
#define a_Version 1
#include <acl4v1.c>
class_(Data) { SetElm elm[2]; int age; };
int main()
{
Set0 index[2]; char *k;
Set0_ini(_a_ &index[0], NULL);
Set0_ini(_a_ &index[1], NULL);
// nameだけではなく、phoneでもデータを検索できるようにした例.
Data data[4], *p; int i;
data[0].elm[0].k = "Kawai"; data[0].age = 20; data[0].elm[1].k = "090-8765-4321";
data[1].elm[0].k = "Suzuki"; data[1].age = 22; data[1].elm[1].k = "0X0-XXXX-XXXX";
data[2].elm[0].k = "Tanaka"; data[2].age = 25; data[2].elm[1].k = "0Y0-YYYY-YYYY";
data[3].elm[0].k = "Yamamoto"; data[3].age = 30; data[3].elm[1].k = "0Z0-ZZZZ-ZZZZ";
for (i = 0; i < 4; i++) {
data[i].elm[0].n = strlen(data[i].elm[0].k);
data[i].elm[1].n = strlen(data[i].elm[1].k);
Set0_add(&index[0], &data[i].elm[0]);
Set0_add(&index[1], &data[i].elm[1]);
}
k = "Tanaka"; p = Set0_findKn(&index[0], k, strlen(k));
if (p == NULL) printf("name(key)=%s: not found\n", k);
if (p != NULL) printf("name=%s age=%d phone=%s\n", (char *) p->elm[0].k, p->age, (char *) p->elm[1].k);
k = "0X0-XXXX-XXXX"; p = ptrSub(Set0_findKn(&index[1], k, strlen(k)), sizeof (SetElm));
if (p == NULL) printf("name(key)=%s: not found\n", k);
if (p != NULL) printf("name=%s age=%d phone=%s\n", (char *) p->elm[0].k, p->age, (char *) p->elm[1].k);
Set0_din(_a_ &index[0]);
// Set0_din(_a_ &index[1]); // わざとdeinitを忘れてみる.
a_malloc_debugList(_a);
a_DbgObjInfTbl_debugList(_a);
return 0;
}
// 実行結果.
>tt0005a
name=Tanaka age=25 phone=0Y0-YYYY-YYYY
name=Suzuki age=22 phone=0X0-XXXX-XXXX
tt0005a.c(35): malloc_debugList()
[p:00afccf0 sz:24 / a4_0016.c(345)] ← [註]従来からのメモリリーク情報表示
tt0005a.c(36): DbgObjInfTbl_debugList()
[VecChr / a4_0016.c(402)] ← [註]acl4v1のオブジェクトリーク情報表示(new)
[Set0 / tt0005a.c(10)] ← [註]acl4v1のオブジェクトリーク情報表示(new)
- 今までは、 malloc_debugList しかありませんでした。だから「24バイトのメモリリークがあって、それは a4_0016.c の345行目に由来する」ということしかわかりませんでした。
- ちなみに a4_0016.c の345行目は VecChr_reserve() の中です。だからまあ、 VecChr に関係ありそうですが、 tt0005a.c の中には VecChr を明示的に使っている部分はないので、やっぱりよくわからないわけです。
- 一方で、 acl4v1 から見えるようになった DbgObjInfTbl_debugList を見ると、 VecChr が deinit されていないという情報だけではなく、 Set0 が deinit されていないことが分かります。しかも行番号で10行目だとわかるので index[1] のほうだとすぐにわかります。
- これはデバッグがはかどります!
- (ちなみに、 Set0 が VecChr を内部で使っているのでした。)
- 「うきょー」って言いたくなる気持ちが伝わったでしょうか・・・。
2026.04.13(月) #0
- ちなみに今は「どのオブジェクトなのかを特定するために、initを呼んだ行番号を表示」という方式を採用していますが、かつてはこの方法ではありませんでした。
- メモリリークやオブジェクトに関するエラー表示について、最初に考えた方法は「malloc/initするときに名前を付ける」という方法でした。5年くらい前のことです。
- まず、この方法は基本的にはうまくいきました。どのオブジェクトが悪いのかを簡単に見分けられました。
- しかし問題もありました。それは名前を付けるのが面倒ということです。そもそも名前なんてなくてもエラーさえなければ問題はないのです。
- ・・・それで名前を省略したり、同じ名前を適当に連発したりすることになります。しかしそうするとエラーが出たときに結局どのオブジェクトのことなのかよくわからなくなるのです。
- そうなってから名前を付けなおしてデバッグするわけですが、なんかあまり便利な感じではなく、printfデバッグと大差ないような使用感でした。
- __LINE__とか__FILE__を書けば行番号表示に必要な情報が取れることは前から知っていましたが、それがオブジェクト名の代わりにできるということにはずっと気づきませんでした。
- また、このマクロ変数は目立つし長いので、ソースコードに書くのは嫌だとも思っていました。
- 2026年になって、メモリリークを検出する機構をacl4用にまた1から作ろうと思ったとき、名前を付ける方式はもうやめようと思いました。名前がなくてもサイズが分かればそれでいいかなと思ったのです。
- 一方で実行時エラーを表示するために、関数を呼び出した行番号は欲しいと思いました。でも__LINE__とかを関数の引数として書くのは嫌だったので、マクロでうまく隠す方法を採用しました。
- やってみてわかったこと: サイズだけではよくわからない。でもmalloc時の行番号が分かれば十分にデバッグの役に立つ。・・・それでmalloc/freeだけではなくinit/deinitに対しても同様のチェック機構をつけることにしました。それがacl4v1です。
2026.04.13(月) #1
- 私は、VecChrで作った可変長配列の中にオブジェクトを並べていくことが時々あります。
- たとえば、"apple", "banana", "grape", "lemon", "melon", "orange", "peach" みたいなサイズが不ぞろいの単語の配列を動的に作る場合、とりあえずこうします(動的ではないなら普通の配列にすればいいのですが)。
VecChr array[1], *p; VecChr_ini(_a_ array);
p = VecChr_stkAdd(array, sizeof (VecChr)); VecChr_iniCpy0(_a_ p, "apple", -1); // 長さが-1の場合、strlenして長さを設定してくれる.
p = VecChr_stkAdd(array, sizeof (VecChr)); VecChr_iniCpy0(_a_ p, "banana", -1);
p = VecChr_stkAdd(array, sizeof (VecChr)); VecChr_iniCpy0(_a_ p, "grape", -1);
// stkAdd()は、指定されたサイズだけarrayを拡張し、その先頭アドレスを返してくれます.
// そこを VecChr で init して、 文字列をコピーしているのです。
- 一方で、VecChrはサイズの拡大のために realloc() を使っています。だから array の中のVecChrオブジェクトは、メモリアドレスが変わることがあり得るわけです。
- もしもメモリアドレスが変わらないなら、オブジェクトをリンクリストでつないだり外したりするだけで、deinitしていないオブジェクトの一覧を作ることができます。実際mallocのメモリブロックはそうやって管理しています。これならメモリブロック1つ当たりの管理コストは O(1) です。
- でもメモリアドレスが変わるなら、リンクリストでつなぐ方式は使えません。ここが苦労ポイントでした。でも頑張って O(1) でできるようになりました。
- オブジェクトのアドレスは変わってもいいようにします。
- 上記例でたとえばarrayの中身をdeinitせず、親のarrayのみをdeinitしてしまうバグもあり得ます。その場合、メモリが解放されてしまうので、もう個々のVecChrにはアクセスできませんしするべきではありません。それでもdeinitし忘れたことを行番号とともにレポートできるべきです。
- デバッグモードとはいえ、速いほうが望ましいのでできれば O(1) で(1オブジェクトあたりの管理コストが)。
2026.04.15(水) #0
- リファクタリングをすると、そういえばここも直したいって思うところが見つかって、気分がいいです。
- 大半の記述は直す必要はないので、コピー&ペーストしてきて、気になるところ直して、エラーやリークが無くなれば次に進む、みたいな感じなので、さくさく進みます。
2026.04.15(水) #1
2026.04.16(木) #0
- [Q] 結局 acl4 って何ができますか?
- [A1] デバッグレベルの提供
- 一般にCコンパイラには、最適化レベルとデバッグ情報(シンボル情報)の有無程度しか選択肢がありません。最適化レベルを最低にしても、それは単に工夫のないコード生成をしてコードサイズが冗長になり、実行速度が下がってコンパイル時間が短くなる程度で、それ以上のメリットはありません。
- acl4は違います。デバッグレベル2以上にすれば(=これをデバッグモードと言っています)、ライブラリは不適切な引数で呼び出されてはいないかとチェックするようになり、デバッグがやりやすくなります。具体的なチェック内容については以下で説明します。
- なお、デバッグモードではなくても「ファイルオープンのエラー」や「メモリ不足でmallocに失敗した」などのエラーチェックは省略せずに行います。これらはプログラムにバグがなくても起こりうるエラーだからです。デバッグレベルで制御するのは、プログラム内のバグに起因するエラーチェックのみです。
- デバッグモードはプリプロセッサ制御で実現しています。リリースモード時にはデバッグチェックのためのコードはソースコードから消された状態でコンパイラに渡されるので、コンパイラの最適化能力によらず、デバッグチェックのためのコードが実行ファイルに残ることはありません。
- このようにデバッグチェックがリリースモード時の実行速度や実行ファイルサイズに悪影響を与えることがないと保証されているので、チェックは遠慮なく念入りに行うことができています。
- [A2] デバッグモードで提供される機能(メモリ管理支援など)
- mallocしたけどfreeしてないメモリを一覧形式で表示する関数があります。メモリリークのバグを見つけるのにとても重宝します(その際には、プログラムの何行目のmallocで確保したメモリなのかも教えてくれます)。
- mallocしてないメモリをfreeしてしまった(もしくは二重にfreeしてしまった)場合は、エラーメッセージを表示してすぐに終了します。問題のfreeがどこにあるのかもわかります。
- freeしたりreallocでサイズを小さくすると、解放された部分はゼロクリアされます。これでfreeしたメモリを誤って読みだそうとするようなバグはすぐに見つかることになります。
- initしたけどdeinitはしていないオブジェクトの一覧も見られます。メモリリークの原因はたいていこれでわかります。
- また同じオブジェクトに対してinitを2度してしまったとか、initしてないのにdeinitを呼び出したなど、明らかにおかしいバグがあった場合も、エラーメッセージを表示してすぐに終了します。
- これらのサポート機能のおかげで、私は自分の作ったプログラムにバグは残ってないと確信することができるようになりました。
- [A3] 動的可変長配列のクラス VecChr の提供
- C++には vector<T> という動的可変長配列があります。これと同じではないものの、近いものがあれば便利だと思って、 VecChr というクラスを作りました(vector<char>を意識して命名しました)。
- 動的可変長配列があれば事前にサイズを決めておく必要はなくなるので、 acl4 内のいろんなところで多用されています。
- [A4] プリプロセッサを作るための一通りの機能を提供
- プリプロセッサで処理したいソースコードをC言語の文字列で用意すれば(当然VecChrでも可)、プリプロセッサで処理した後の結果をC言語の文字列で返すプリプロセッサ関数があります。
- 基本的にすべてオンメモリで処理するので高速ですし、一時ファイルなどを作らないのでディスクを汚しません。オンメモリで処理するとは言っても、includeでファイルを読み込ませる処理がある場合は、ちゃんとファイルアクセスもします。
- プリプロセッサ関数はより細分化された細かい関数で構成されているので、カスタマイズしたプリプロセッサ関数を作ることも可能です。
- [A5] Cコンパイラ・Cインタプリタを作るための機能を提供(予定)
- Cコンパイラなどの言語を作ることを考えると、結局はソースコードを次々と別の形式に変換していって、最終的にアセンブラか中間コードか機械語に変換することだとわかります。
- この「変換」は実はプリプロセッサが得意とするところなので、プリプロセッサで言語機能の大半を記述し、プリプロセッサで書けない部分だけをC言語で書くようにしたら、従来よりもはるかに少ない手間で言語が作れるのではないかと考えました。
- acl4 では既にプリプロセッサ処理は好きなだけ利用できる状態になっているので、これを活用して、実際に言語を作ってみて、どんな感じになるか確かめています。
2026.04.17(金) #0
- プリプロセッサが、文字列リテラルに対してstrlenできるようになったら(=結果を定数で返せたら)、いろいろ便利になりそうな気がしてきました。
2026.04.17(金) #1
- acl4 → acl4v1 での主な改善点:
- DbgObjInf が入ったので、init/deinit に関するバグを簡単に見つけられます。
- VecChr の sizeof が「ポインタ1つ分」になりました。 VecChr の配列とかを作ってもアクセスが速そうです。 acl4 では「ポインタ3つ分」でした。
- parseArgs() を使いやすくするために結果の渡し方を改良しました。
- Preprocessor_Eval で、演算子や特殊な変数や関数の追加などのカスタマイズの余地を入れました。
- プリプロセッサの機能が密結合になっていた部分があったので、そこを直してより改造しやすくします(予定)。
- typedDef と普通の define の処理ルーチンを統合します(予定)。
2026.04.18(土) #0
- やっと、acl4v1でもプリプロセッサが動きましたー。でもまだdefineは動きません。それ以外は動きます。
- そのテストの時に、デバッグモードにするとやたらと低速になる現象が起きました。「まあデバッグモードだから遅くなってもしょうがないかな」と最初は思いましたが、でも原因くらいは確認するべきだろうと思って調べたら、init/deinitの管理部分のバグでした。直したらデバッグモードでも十分に速くなりました。よかったー。
2026.04.20(月) #0
- mallocでメモリを確保したり、reallocでメモリを拡張したりすると、なんか適当な値が雑に書かれたメモリが手に入ります。そのことそのものに問題はないのですが、しかしデバッグするときにこれを見て「初期化をしてないからこの値なのか」「初期化をしたからこの値なのか」よくわからない気分になります。だから自作mallocと自作reallocに手を加えてデバッグモードの時はメモリを適当な値で塗りつぶして渡すという仕組みを作ることにしました。
- とりあえず簡単のためにmemset()で塗りつぶすことにして、ではどんな値で塗りつぶすかということを考えました。
- 0x00: これで塗りつぶすと明らかに「何も書いてない」感じになります。それはとても良いですが、そもそもプログラムのほうで初期化する際も 0x00 で塗りつぶすことが多く、つまりこれだと初期化を忘れてもかえって気づきにくい、初期化し忘れているのにデバッグモードだと正常に動いちゃう、という問題があります(リリースモードでは動かない)。0x00にしたいのならプログラムが自分でやるべきです。mallocやreallocを当てにされては困ります。
- 0xff: 0x00が一番きれいなのだとしたら、じゃあ一番汚いのは何か?それは0xffだよね、と考えました。数値的にも255は0から一番遠い値で、未初期化だと最も気づきやすそうです。・・・しかし、非常によく使われる符号付き整数で考えれば、0xffは8bitの-1でもあります。0xffffは16bitの-1、0xffffffffは32bitの-1です。つまり未初期化で値を取り出すと-1が読めてしまうわけです。-1なんて0にかなり近い数値です。初期化を忘れていても、「なんかちょっとだけおかしいかもしれないけど、まあでもこんなものかな?」で見過ごされる可能性があります。だからもっと明らかにおかしい値にするべきです。
- 0x80: では符号付きの整数で、0x00から最も遠い値にしたらどうかと考えました。8bitの0x80は-128、16bitの0x8080は-32640、32bitの0x80808080は-2139062144です。これはちょっと普通では出てこない数値でしょう。しかし、だからこそ、invalidな値として初期値で使われる場合もあります(私自身もやったことがあります)。・・・それだと初期化忘れを見逃す原因にもなりうるのです。
- 0x87: それでは、この1バイトの中の「0」のビットと「1」のビットを同数にすることにして、それで0x00から最も遠い値というのを考えてみました。「0のビットと1のビットを同数にする」というのは、メモリチェックパターンの0x55aaとかでも使われている考え方です。今回はメモリチェックとは全く関係ない文脈ですが、オールゼロやオールワンが真っ先にダメだというのなら、いっそのこと半々にしてしまえ、という安易な発想です。・・・0x87や0x8787などを初期値として採用するケースはまず考えられないですし、異常値っぽさは十分にあります。ということで今回はこれで行くことにします。
2026.04.20(月) #1
- acl4v1でもdefine機能が使えるようになりました。でもまだtypedDefがうまく動いていません。
2026.04.20(月) #2
- なんか最近このwikiが不安定な気がします。よしxreaからcoreserverに移行しよう!
2026.04.21(火) #0
2026.04.21(火) #1
- 移行できたと思います。無事に安定して表示できるといいなあ。
2026.04.21(火) #2
- さっきバグって、ポインタが変な値になっていました。当然、セグメンテーションフォルトで落ちたわけですが、なんでだ?と思ってポインタ値をprintfしてみたら、なんと 0x87878787 !
- ・・・うお、いきなりこれかー(笑)。つまり初期化してないポインタがあって、そこを読んだわけですね。なんてわかりやすい!
- ということで30秒くらい、くくく・・・と笑ってしまいました。
- [註] 2026.04.20(月)#0 で自分が仕掛けたバグ発見用のトラップに、さっそくはまって原因が分かった、という事例です(笑)。
- いや、これに限らず、私は毎日何度も自分の仕込んだデバッグトラップを踏んでいます。
- まあなんとも情けないわけですが、でもそのうちの多くはデバッグトラップがなくてもすぐに直せただろうとは思います。
- ただなんというか、私のデバッグトラップたちが優秀すぎて(?)、私が頑張る前に先にバグを見つけてしまうんです。
- ありがたい!! acl4 は私に合っている!!
2026.04.22(水) #0
- a4_0001~a4_0014のリファクタリングが完了しました。次はミニコンパイラをacl4v1用に直します。
2026.04.24(金) #0
- やっと、何を作ったらプリプロセッサの良さが伝わるかが分かったので、頑張って作ります。たぶん明日か明後日にはできます!
2026.04.25(土) #0
- できました!
- a4_p0007: プリプロセッサ処理をする関数を作ったら、いろんな言語が簡単に作れるかもしれない可能性が出てきました!
- a4_i01のページを改装中です。
2026.04.26(日) #0
2026.04.27(月) #0
- a4_p0007のページにダウンロード用のzipファイルを追加しました。これで、35.0KBってホントにできるの?って言われずに済みます。
- x86-32でコンパイルしないと、35.0KBにはなりません。あと /Da_DbgLv=0 をつけて、リリースモードにする必要もあります。
- さて、次にやるべきは配列変数のサポートです。配列変数が使えるようになれば、kcubeが動かせるようになるはずです。
- とにかくこの「プリプロセッサで置換する方式」でどこまで行けるのか確かめたいです。
2026.04.28(火) #0
- a4_t0002 は Windows 専用になっていますが、かつて X11 でのグラフィックのやり方を勉強したので、それを思い出せば、 Linux 版も作れそうだとは思っています。
2026.04.30(木) #0
- 考えがうまくまとまらないので、とりあえずシンプルにやります。
- たぶん設計がまとまらないのは、それを設計するだけの知識が揃っていないのだと思います。そんなときに無理しても駄作になって結局作り直すことになるので、背伸びはせず、単純明快にできるところまでをやります。
2026.05.01(金) #0
- A4vm_eval0()のEnter命令の仕様:
- Ent_III(i, j, k)
- i: 整数レジスタ数, j: 浮動小数点数レジスタ数, k: 関数呼び出しのための予約メモリ
- 今回追加する引数:
- Ent_IIIII(i, j, k, l, m)
- l: ポインタレジスタ数, m: スタック変数のための領域サイズ
2026.05.01(金) #1
- そうかー! 構造体をどうしたらいいかなって考えるよりも先に、プリプロセッサの力でJITコンパイラが作れるのか試すべきです。
- もしうまくできたら、「これでもう将来どんなCPUが主流になっても、簡単に移植できるよー」って言えるようになるはずです。
2026.05.01(金) #2
2026.05.01(金) #3
2026.05.01(金) #4
- まだ printf しかできないですが、とにかくJITコンパイラはできました。ちゃんとx86の機械語に変換されて動いています。
- [追記] その後、for文もできました。簡単すぎて楽しいです。
- [追記] さらに1時間くらいやったら、 p0007h.txt が動くくらいになりました!( mandel )。やっぱりJITコンパイラは実行が速いです。
- やっぱりプリプロセッサは偉大だなあー。
2026.05.03(日) #0
- 今、 p0008a.c っていうJITコンパイラを作っているのですが、その中身は Cコンパイラ+アセンブラ になっています。
- そのアセンブラ部分は、 #define RET() DB(0xC3) みたいなのを50行くらい書いただけでしかないのですが、命令によってはこのDB命令は連続するので DB(a, b); みたいな形式もサポートしたいなって思いました。
- でもなあ、複数の引数をサポートするのは面倒だよなあ、まあだから現状のままでいいかー、2回書けばいいだけだし・・・とか思って妥協していました。
- でもさっき、思いつきました。あれ?もしかして、 #define DB(a, b) DB(a); DB(b) っていう1行を追加しておけばいいだけなんじゃないの?
- その通りでした。こうして DB() 命令は複数の引数に対応できたのでした。
- こんなに楽していいのかな?(笑)
- 上記で、平気なふりして「#define を50行くらい書くだけで、アセンブラができた」みたいなことを書いていますが、これも結構とんでもなくて、今まで何度かアセンブラを作ってきた私としては「今までの苦労は一体なんだったのか・・・」という気持ちになっています。
- まあ進歩ってそういうものですよね。
2026.05.04(月) #0
2026.05.04(月) #1
- a4_t0003 を書きました。現行のミニコンパイラを補助ライブラリとしてまとめて、何度もコピー&ペーストしないでもいいようにしました。
2026.05.04(月) #2
2026.05.06(水) #0
- 「新しい言語の作り方」という12ページのスライド資料をなんとなく作りました。
2026.05.10(日) #0
- 運よくプレゼン機会があったので、上記の「新しい言語の作り方」でLTをしてきました(昨日)。
- 好評でたくさんコメントをもらえたので、それを加筆したバージョンを作ろうと思います。
2026.05.13(水) #0
- [1] 第1層(a4_0016)
- デバッグに便利な機能が付いた malloc/realloc/free を整備。
- [2] 第2層(a4_0017~a4_0019)
- 第1層の成果を使って、vector<char> を参考にして作った VecChr クラス(動的可変長配列)、簡単な Key-Value Store を提供する Set0 クラスを整備。
- さらにトークンを切り出す Token0/Token1 クラス、かっこでくくられた構造を切り分ける parseArgs などを整備。
- [3] 第3層(a4_0020)
- 第2層の成果を使って、式の評価クラスを整備。文字列で式を与えれば、計算して答えを返します。
- [4] 第4層(a4_0021~a4_0022)
- 第3層までの成果を使って、プリプロセッサ関数を整備。
- [5] 第5層(a4_0023~)
- ということで、まずAを作り、そのAを利用してBを作り、そのBを利用してCを作り・・・というのを繰り返して、どんどん自分の開発力をアップさせようというたくらみは、今のところ順調に進んでいます!
2026.05.16(土) #0
- 何となく自分が納得できる程度の memmem() ができたのでここに書きます。
- まず memmem() が何かというと strstr() の仲間みたいなものです。ゼロ終端文字列ではなくて、メモリブロックの中からメモリブロックを探すのです。
- GNU拡張なので、標準の <string.h> には入っていません。私はとっても便利な関数だと思っていますが。
- 普通に作っても面白くないので、ちょっとだけ工夫をして高速化してあります。
- 説明用のバージョン:
a_static char *a_memmem0(const char *t, intptr_t tn, const char *p, intptr_t pn)
{
if (pn <= 0) return (char *) t;
if (tn < pn) return NULL;
intptr_t i = pn - 1;
const char *t1 = t + tn - pn, c0 = p[0];
for (t--;;) {
nxt:
t = memchr(t + 1, c0, t1 - t);
if (t == NULL) return NULL;
if (t[i] == p[i]) {
for (i = 1; i < pn; i++) {
if (t[i] != p[i]) goto nxt;
}
return (char *) t;
}
}
}
- まず memchr() で0バイト目が一致している場所を見つけてきます。無事に見つかったら、i番目についても比較します。それも一致したら、全部比較します。
- 全部比較するときに memcmp() を使えばいいし、比較だけならたぶんそのほうが速いのですが、不一致だった場合に何バイト目で食い違ったのかを知りたいので、自前ループしています。
- 普通、この手のストリング検索では、 Boyer–Moore の有名なアルゴリズムを使って高速化します。しかしそれは事前解析処理が面倒だったので今回はやらないで、不一致の場合に速く気付くことを目指してこのアルゴリズムを思いつきました。まあシンプルなので、たぶん車輪の再発明だろうと思います(笑)。
- 最初に t--; して、次に t+1 から memchr() するのは一見すると無駄なのですが、不一致になって戻ってきたときに t+1 してくれるのは便利なのです。だから最初に t--; してでも、この構造にしたかったのです。
- でもこのバージョンをそのまま使うと、 memchr() があまり速くありません。こういうストリング系の関数は自前実装しても性能がよくなることはほとんどないと言われていますが、私はそんなうわさ程度じゃあきらめません。そもそもここに書くことになったということは、自前実装でも十分に速くなったから書いているのです(笑)。
- ちゃんと高速化したバージョン:
a_static char *a_memmem(const char *t, intptr_t tn, const char *p, intptr_t pn)
{
if (pn <= 0) return (char *) t;
if (tn < pn) return NULL;
intptr_t i = pn - 1;
const char *t1 = t + tn - pn, *t16 = t1 - 16, c0 = p[0];
for (t--;;) {
nxt:
t++;
for (;;) {
if (t <= t16) {
if (t[0] == c0) goto t0;
if (t[1] == c0) goto t1;
if (t[2] == c0) goto t2;
if (t[3] == c0) goto t3;
if (t[4] == c0) goto t4;
if (t[5] == c0) goto t5;
if (t[6] == c0) goto t6;
if (t[7] == c0) goto t7;
if (t[8] == c0) goto t8;
if (t[9] == c0) goto t9;
if (t[10] == c0) goto t10;
if (t[11] == c0) goto t11;
if (t[12] == c0) goto t12;
if (t[13] == c0) goto t13;
if (t[14] == c0) goto t14;
if (t[15] == c0) goto t15;
t += 16;
continue;
}
if (t > t1) return NULL;
if (t[0] == c0) goto t0;
t++;
}
t15: t++;
t14: t++;
t13: t++;
t12: t += 12; goto t0;
t11: t++;
t10: t++;
t9: t++;
t8: t += 8; goto t0;
t7: t++;
t6: t++;
t5: t++;
t4: t += 4; goto t0;
t3: t++;
t2: t++;
t1: t++;
t0:
if (t[i] == p[i]) {
for (i = 1; i < pn; i++) {
if (t[i] != p[i]) goto nxt;
}
return (char *) t;
}
}
}
- さあ、久しぶりに「キモイい」プログラムになりました。
- この改造の趣旨は、とにかくtを加算したり、tnとの比較をしたりする頻度を下げたかったのです。だから16回に1度だけ加算&比較するようにしました。
- それで一致した場所が見つかった場合は、tをその分だけ加算しなければつじつまがあわないので、t++;が連続しているところのどこかへ分岐させています。
- やっていることはそれだけです。
- 芸のないベンチマーク:
#include <acl4v1.c>
#include "t0003a.c" // ここにa_memmem()があります.
int main(void)
{
char *s = malloc(900 * 1024 * 1024); // 900MB.
int i, j = 0;
for (i = 0; i <= 100000000; i++) // とりあえず1億.
j += sprintf(s + j, "%d ", i);
printf("j=%d\n", j);
clock_t t0, t1, t2;
t0 = clock();
int rs = (int) strstr(s, " 100000000");
t1 = clock();
int rm = (int) a_memmem(s, j, " 100000000", 10);
t2 = clock();
printf("strstr=%x\n", rs);
printf("a_memmem=%x\n", rm);
printf("t1-t0=%d t2-t1=%d\n", t1-t0, t2-t1);
return 0;
}
- 次に、 a_memmem() が少し有利になりそうなベンチマークです。いつも最初の数文字が一致しているようなパターンです。
#include <acl4v1.c>
#include "t0003a.c"
int main(void)
{
char *s = malloc(140 * 1024 * 1024); // 140MB.
int i, j = 0;
for (i = 0; i <= 10000000; i++) // とりあえず100万.
j += sprintf(s + j, "count=%d ", i);
printf("j=%d\n", j);
clock_t t0, t1, t2;
t0 = clock();
int rs = (int) strstr(s, "count=10000000");
t1 = clock();
int rm = (int) a_memmem(s, j, "count=10000000", 14);
t2 = clock();
printf("strstr=%x\n", rs);
printf("a_memmem=%x\n", rm);
printf("t1-t0=%d t2-t1=%d\n", t1 - t0, t2 - t1);
return 0;
}
2026.05.22(金) #0
- 最近は、SecHack365の選考に忙殺されていて、acl4があまり進んでいません。
- あ、でも、昨日は buntan-pc のuchanさんと、CPUにこんな命令があったら便利になるかもしれないっていう話をたくさんしました。私は CPU の自作を気軽にやったりはできないのですが(勉強不足で)、仮想マシンとしてそういう命令を持たせることなら余裕でできるので、いつか試すかもしれません。
- 考えていた内容は、たとえば整数演算でゼロ割しても例外を起こさずに商を 0x800...000 として処理を続行してくれて、またNULLポインタでメモリライトしても無視してくれて、NULLポインタでメモリリードしたら 0x800...000 が読みだされて続行されるような、そんな命令体系です。どの場合も、問題が起きて対処した場合はフラグレジスタ内のエラーフラグを1にするくらいはしてもいいかなと思っています。加減算などでもオーバーフローを検出したら値を 0x800...000 にするモード(モードというか新設命令)があってもいいと思っています。
- この命令体系だとプログラミングのパラダイムが変わるかもしれなくて、今までは演算する前に入力値が正常の範囲に収まっているかチェックしながら演算してきました。そうでないと例外を踏まされるからです。でもこの命令体系なら、値はおかしくなるもののとにかく処理は問題なく続行できるので、最後にエラーフラグをみてエラー処理するだけで済みます。結果的にif文が減ると思うので高速化するかもしれません。
2026.05.26(火) #0
- 4bitあれば 0000~1111 の16通りの表現があります。これをAパターン(a通り)とBパターン(b通り)に分けます。a+b=16とします。
- Bパターンが来たら、そこで終了です。これで 0~(b-1) を表現できます。
- Aパターンが来たら、Bパターンが来るまで繰り返してから終了します。ABの場合 0~(ab-1)を表現できます。AAAB形式なら 0~(aaab-1) です。
- hh4の単純形式の場合、a=b=8になっていて、だから 8/64/512...と拡張していくことができます。
- 拡張形式として、10+6=16 みたいなものを考えることができます。4bitで0~5、8bitで0~59、12bitで0~599、16bitで0~5999が表現できます。8+8=16と比べると、4bit形式は7→5、8bit形式は63→59と犠牲になりますが、12bitは511→599となって少し増えます。
- 表にしてみます。
| 8+8=16型 | 8 | 64 | 512 | 4096 |
| 10+6=16型 | 6 | 60 | 600 | 6000 |
| 7+9=16型 | 9 | 63 | 441 | 3087 |
| 6+10=16型 | 10 | 60 | 360 | 2160 |
| 5+11=16型 | 11 | 55 | 275 | 1375 |
| 4+12=16型 | 12 | 48 | 192 | 768 |
- この中だと4+12=16はかなり魅力的に見えます。
こめんと欄