プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

もっともシンプルなmalloc,freeの実装と理解

mallocはOSからメモリを動的に確保する?

 mallocをするとOSからメモリを確保出来る。

 mallocで確保したメモリはfreeでOSに返される。

 一体どこの誰だ、こんな嘘の解説を世に出したのはぁ!

 こんな説明がまかり通っているから、初心者の脳内メモリイメージが何だかよく分からない、お花畑な状態になってしまうのだ。

 なんかOSっていうスゲーのが何かしてるらしい。よくわからないけど、なんか駄目って言われてるから2回解放したら駄目らしい。使ったら解放しないと駄目って言うから解放したけど、何か動かない。なんか駄目って言われたから、やっちゃ駄目なことは分かるけど、逆に何をしても良いのか実はわかってない。

 どうも、こんな感じのイメージになっているっぽい。

 

 同じ嘘をつくなら、mallocはOSからメモリを確保しない、freeはOSにメモリを返さないと説明した方がまだマシである。

 なぜなら、mallocはOSから動的にメモリを確保する場合もあるが、動的にメモリを確保しない場合もある。そして後者の方が、理解に圧倒的に重要な項目だからだ。

 

 この記事では、OSから一切動的にメモリを確保しない極シンプルなmalloc、freeを作る。なんだかmalloc,freeがよく分からない、と思っている初心者の方々の理解の手助けになれば良いと思う。

 とにかく簡単な物が、どう動くのかを理解することが、一番手っ取り早い理解だ。

 

 

OSからメモリを動的に確保しないmallocを作ろう

 mallocにまつわる技術は中々に奥深い物があるのだが、そんな物を解説したって混乱するだけである。とにかく、ヒープだのなんだのを全て排除した、簡単で、機能としては十分なmallocとfreeを作ることを目標としよう。

 まず、一番簡単でかつ、仕様を満たすmallocとfreeの実装は以下だ。

int* my_malloc(int size)
{
  return 0;
}

void my_free(int* ptr)
{
}

 今回はわかりやすさを最優先する為に、全てをintの単位で管理する。sizeも何int分かを表すとします。voidポインタなんてまだキミ達には早すぎる。実際のmallocのsizeと今回のmy_mallocのsizeは単位が違うことだけを認識しておいて欲しい。

 さて、これは完全で一切バグのないmalloc、freeだ。決して問題を起こすことはない。そして、このmalloc、freeにOSは一切絡んでいないことは納得して頂けるだろう。(OSどころか、処理すらないのだから!)

 とはいえ、10という入力が来たら、長さ10のメモリのアドレスを返さなければ、流石に実用に耐えない。追加の実装が必要だ。

( ・Д・)「あ、そこでOSからメモリを持ってく…………

 持ってきません。この記事は最後までOS絡みません。

 

グローバル変数でメモリを管理

 さて、OSからメモリを取ってこないと言っても、どこかにメモリは必要。ということで、以下の様にグローバル変数memoryを用意しよう。

int memory[20];

 10個分のメモリが欲しいと言われたら、このmemoryから10個分返してあげれば、別にOSに頼らなくてもメモリを10個動的に確保したのと同じだ。

 というわけで、memoryを返してあげよう。

int memory[20];
int* my_malloc(int size)
{
  return memory;
}
void my_free(int* ptr)
{
}

 

 完璧である。さぁ、実際に使ってみよう。

 

int main(int argc, char *argv[])
{
  int *a = my_malloc(10),*b = my_malloc(10);
  a[0] = 1;    a[1] = 2;
  b[0] = 10;   b[1] = 20;
  printf("a[0]=%d,a[1]=%d,b[0]=%d,b[1]=%d\n",a[0],a[1],b[0],b[1] );
  my_free(a);  my_free(b);
  return 0;
}

 

 まぁ、言うまでもなく、これの結果は以下の様になる。

a[0]=10,a[1]=20,b[0]=10,b[1]=20

 問題は1回目のmy_mallocも2回目も、同じポインタを返しているから、同じ場所を書き換えてしまうのだ。

f:id:nodamushi:20181211214648p:plain
a,bのアドレスと範囲

使用した場所を記録する

 毎回違う場所を返せる様にするには、いったい何処が使われているか記録しておかなければならない。

 グローバル変数usedを用意し、そこに使っているか使っていないかの状態を保存しよう。usedの値が0なら未使用、1なら使用中である。

 size分の領域が必要な場合、0番目から1つ1つ、使われているかいないかを確認し、使われていなければ、使用中(1)をマークして返す。

int memory[20];
int used[20]={0};

int* my_malloc(int size)
{
  if( size <= 0 || size > 20) return 0;
  
  for(int i=0;i < 21-size;i++){
    if(!used[i]){
      //size分の領域が連続して空かを確認してから返す
      int not_used=1;

      for(int k=0;k<size;k++)
        if(used[i+k]) not_used=0;

      if(not_used){
        for(int k=0;k<size;k++)  used[i+k] = 1; //使用中をマーク
        return memory + i;
      }
    }
  }
  return 0;
}

 (gotoを使う誘惑に駆られたが、わかりやすさ優先の為に我慢した)

 これで、先ほどのmainを実行してみると………

a[0]=1,a[1]=2,b[0]=10,b[1]=20

 エクセレンッ!完璧である。

f:id:nodamushi:20181211215029p:plain
usedのお陰で、aとbが違う場所に割り当てられた

 と、言いたいところだが、まだ問題がある。freeが実装されていない。

 このままだと、以下のコードでcの確保に失敗してしまう。

int main(int argc, char *argv[])
{
  int *a = my_malloc(10),*b = my_malloc(10);
  my_free(a);
  int *c = my_malloc(10);// 0が返ってしまう
  return 0;
}

 cを確保する前に同じサイズのaをfreeしているので、cは確保出来て当然だろう。

 というわけで、freeを実装したいのだが………

void my_free(int* ptr)
{
  if(!ptr) return;

  int index = ptr-memory;
  for(int i =0; i <    /* ????? */   ;i++)
    used[index + i] = 0; // 未使用に
}

 ちょっと待って、何メモリ分を解放すれば良いのか分からない。for文の条件式が作れない。

 

使用量も保存し、freeを実装

 どうやらusedをクリアする為には、ptrがどれだけの大きさのブロックなのかを保存する必要もあるらしい。

 size配列を用意しても良いが、勿体ないので、usedに使用サイズも保存しよう。

int memory[20];
int used[20]={0};

int* my_malloc(int size)
{
  if( size <= 0 || size > 20) return 0;
  
  for(int i=0;i < 21-size;i++){
    if(!used[i]){
      int not_used=1;

      for(int k=0;k<size;k++)
        if(used[i+k]) not_used=0;

      if(not_used){
        for(int k=0;k<size;k++)
          used[i+k] = size-k; // 終わりまでの距離を保存
        return memory + i;
      }
    }
  }
  return 0;
}
void my_free(int* ptr)
{
  if(!ptr) return;
  
  int index = ptr-memory;
  int size  = used[index];
  for(int i = 0; i <size ;i++)
    used[i+index] = 0;
}

 これでmallocとfreeの実装は完成だ。  

 さて、実際にサンプルコードを動かしてみよう。

int main(int argc, char *argv[])
{
  int *a = my_malloc(10),*b = my_malloc(10);
  printf("a address=%d,b address = %d\n",a,b);

  my_free(a);
  int *c = my_malloc(10);
  int *d = my_malloc(10);//足りないので0
  printf("c address=%d,d address = %d\n",c,d);
  return 0;
}

 結果は下の様になり、完璧な動作をしている。

a address=4225504,b address = 4225544
c address=4225504,d address = 0

f:id:nodamushi:20181211220015p:plain
c,bがmemoryに割り当てられている

 

malloc , freeを理解する

 さて、どうだっただろうか?実に簡単だったと思う。

 無論、今回作ったmalloc,freeは実用には全く耐えない。(しかも、わざとすぐに問題を起こせる様にしてある)

 しかし、メモリの確保、解放がなんなのかを理解するに十分である。

 ここまで見てきた様に、メモリを動的に割り当てる、解放する行為にOSは一切関係ない

 OSからメモリを確保する、返すというのは、次の段階の話だ。キミ達が先ず理解しなくてはならないのは、OSレベルの話ではなく、アプリケーションレイヤーでの話なのだ。

 例えば、メモリ確保直後の値はどうなっているのだろう?初期化されているだろうか?

 否である。mallocやfree関数内でmemory配列に対して一切の操作はしていない。誰かが使った後だと、使いっぱなしで、次に渡される。

 

 例えば、NULL(0)の解放をするとどうなるだろう?問題が何か起こるだろうか?

my_free(0);
my_free(NULL);

 これは、実は何も問題を起こさない。なぜなら、1行目で即座にreturnしているからだ。 別に私が気を利かしたのではなく、freeがそういう定義だからである。

void my_free(int* ptr)
{
  if(!ptr) return;

 

 

 じゃぁ、0が大丈夫なら1は?

my_free(1);

void my_free(int* ptr)//ptr = 1
{
  if(!ptr) return;
  
  int index = ptr-memory; // ここが負になる
  int size  = used[index];
  for(int i = 0; i <size ;i++)
    used[i+index] = 0;  // used [ 0 + 負 = 負 ]  = 0;という処理になる
}

 実装に依存するが、今回の実装では明らかに問題が起こる。つまり、やってはならないと分かるだろう。

 なら、次はmallocで確保した領域を途中から開放した場合はどうなるだろう。

int *a = my_malloc(10);
my_free(a + 5);
int *b = my_malloc(10);
my_free(a);
int *c = my_malloc(10);

 今回作ったmallocはとても簡単だ。動きをゆっくり追ってみて欲しい。(そのために、役に立たない簡単なmallocを作ったのだから。)

  1. aが0番目に割り当てられる
  2. my_free(a+5) を解放しようとする。used[5]=5なので、5,6,7,8,9を未使用に変更する
  3. 5~14が未使用なのでbが5番目に割り当てられる
  4. my_free(a)でused[0]=10なので、0~9を未使用に変更する
  5. 0~9が未使用なのでcが0番目に割り当てられる

 最終的には以下の図の様になる。酷い有様だ。

f:id:nodamushi:20181211220851p:plain
b,cが中途半端に重なる

 途中から解放したり、mallocで取得したアドレスをなくしたら困ると分かるだろう。

 

 では、二回解放をするとどうなるだろう。今回の実装では、直ちに影響はない。だが、暫くすると影響がある。

int *a = my_malloc(5);
int *b = my_malloc(5);
my_free(a);
my_free(b);
my_free(a);//特に問題は起こさない
int *c = my_malloc(10);

my_free(b);// cを半分解放する
int *d = my_malloc(10);

 最終的にこれは以下の図の様なメモリ配置になる。やっぱり酷い有様だ。

f:id:nodamushi:20181211222515p:plain
bの2回解放の所為で、c,dが重なっている

 小さなメモリを何度も取るとどうなるだろう。

int *a = my_malloc(5);//残り容量 15
int *b = my_malloc(5);//残り容量 10
int *c = my_malloc(5);//残り容量 5
my_free(b);//残り容量 10

int *d = my_malloc(10); // 失敗

 残り容量は10なのに、dの確保に失敗する。これは空き容量の断片化が起こるからだ。

f:id:nodamushi:20181211222836p:plain
容量は足りていてもdを確保出来ない

 

 gccとかのmallocは、私が作ったのに比べずっと賢いが、基本的にはmalloc,freeは頻繁に行わず、大きな単位で行った方が良い。

 実行環境にも依存するが、小さいオブジェクトなら、普通にスタックに置けば良い(ローカル変数で定義すれば良い)。SPの移動でメモリの解放がされるので0コストだ。(組み込みだとSRAMが小さくて、すぐパンクする可能性があるので気をつけたし)

 

 

まとめ

 

 さて、malloc,freeの大事なところを理解するのに、OSからメモリを確保とか糞みたいなどうでも良いことだと理解して貰えただろうか。

 mallocをするとOSからメモリを確保出来る………。確かにその通りではある。

 だが、その話を鵜呑みにして、OSからメモリがご降臨されて、OSにメモリがご帰還なさっていく様なふんわりしたイメージをいつまでも持っていると、大事なことが理解出来ない。

 メモリの確保が行われるのは、mallocが管理しているリソースが足りなくなった時だ。常にOSからメモリを確保している訳ではない。

 mallocはOSからメモリを確保しないし、freeはOSにメモリを解放しないと覚えていた方がまだマシだ。

 今日から「mallocとfreeはメモリを確保、解放しない」と念仏の様に唱えてC言語を捨て、RustやC++を完全に理解しよう。

 

参考文献:glibcのmalloc実装

 実際のmallocがどういう実装になっているのかに興味が湧いたら、以下の記事を読んでみると良いでしょう

Glibc malloc internal

あなたのメモリはどこから来てる?malloc入門 - Qiita

 あと、今回は説明事項から省いたsizeofに関する話など。

sizeof演算子にまつわるアレコレ - Qiita

侍エンジニア塾のC言語のサンプルがヤバすぎる。 - Qiita

Cの本

 楽してとか、わかる、とか、そういうタイトルで良い本だったことはない

苦しんで覚えるC言語

苦しんで覚えるC言語

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

プログラミング言語C 第2版 ANSI規格準拠

プログラミング言語C 第2版 ANSI規格準拠

(古いのであまりお勧めはしないけど)

コンピューターの起源:ジャカード織機の仕組み

 富岡製糸場然り、工業の近代化において、衣服にまつわる技術は多く世に貢献してきた。

 さて、私たちが今扱っているコンピュータも元を辿っていくと、実はジャカード織機という織機に辿り着く。

 いわゆるパンチカードによるプログラミングの原型とも言えるべき機械で、パンチカードの穴の並びで布の縦糸をどう動かすかを決めることが出来た。これによって、一気に複雑な模様を短時間で作れる様になったらしい。

 

 で、そうは言われても、じゃぁ、どういう風に動くのか日本語で調べたりしてもよく分かってなかったんだけど、偶然素晴らしい動画を見つけて、よーく理解出来た。

www.youtube.com

 こういうデカい機械が、がっしょんがっしょん動くのは、いつになっても浪漫がある。

 

 さて、動画に全てを任せても良いけど、簡単に解説。

 まず、一般には縦糸と横糸を交互に上下に交差させることで布のを編む。これが平織。

f:id:nodamushi:20181209212951p:plain:w320
平織り

 これを、交互ではなくすると、模様になる。図では隙間のせいで模様に見えないけど、布にする時には隙間は詰めるので、交点の部分しか表面からは見えない。

f:id:nodamushi:20181209213134p:plain:w320
ジャカード織

 

   ジャカード織機はパンチカードの情報から、自動的にこのパターンを作り出す。

 パンチカードが無い、もしくはパンチカードの穴が開いたところでは、縦糸を動かす針が上下に動く装置に引っかかり、同じように上下に動く。(縦糸が横糸の上になる)

f:id:nodamushi:20181209211803p:plain:w320
パンチカードが無い状態

 一方で、パンチカードがあって、穴がない場合は、押し込まれ、引っかからなくなり、上下に動作しなくなる。(縦糸が横糸よりも下になる)

f:id:nodamushi:20181209213705p:plain:w320
パンチカードがある状態

   こうやって全ての縦糸を一本ずつ操作し、縦糸と横糸の上下を組み合わせて目的の模様を自動的に作り出す。すごいね。

 ていうか、模様の図からパンチカードに変換する職人もスゴイと思うわ。

ExcelやWordに判子の無駄はなくならない

「証明書が必要だって言うから、証明書取りに行くじゃん?」

「せやな?」

「で、その証明書を発行するのに判子が必要だっていう。」

「よくあるな。」

「しゃーないから、判子持ってって証明書もらうじゃん?」

「うん」

「で、その証明書持ってったら、また判子が必要だって。」

 日本でよくある光景。そんな日本で、より頭が痛くなる記事を見つけた。

forest.watch.impress.co.jp

 Lhaplusが根強く1位を保ってるのも驚き(その上、7-zipが14位でだいぶ離されている)だが、こんなソフトが出てることも、そしてそれのダウロード数が増える日本も頭が痛い。もう一週回って、こういう判子を押せる様に、親切にしてあげるエンジニアの方が悪いんじゃないのかという気がしてきた。

 未だに、こんな↓判子の画像をWordとかExcelとかに普通に貼らせるからね。自分がこの都市伝説の様な作業をするとき、軽く興奮すら覚える。

f:id:nodamushi:20181208224130p:plain

 しかも、普通の企業なら、提出ファイルは誰がチェックしたかとか残るシステムが入ってるから、完全に冗長。加えて、判子がないと差し戻された暁には、軽く絶頂を迎え、アヘ顔を晒すことも辞さない。実に気持ちが良い。

 判子に限らず、印刷することを目的にして、こんな↓感じに面倒くさく表組みされたExcelやWordファイルへの記入とかも、都市伝説じゃなくて、至って極普通のことだ。

f:id:nodamushi:20181208231122p:plain:w320

 ご丁寧に判子を貼る場所も用意されている。見覚えがある人なら何処に貼るか分かるだろう。

 

言うだけ無駄で、変わることはない

 情報処理をする人からすると、こういった不合理や無駄は非常に阿呆らしく見える。役所仕事だの批判の対象になることも多い。

 だが、断言しよう。変わらない。言うだけ無駄である。むしろ、言うだけ白い目で見られるだけだ。ネ申エクセルもなくなることは無いだろう。問題視する方がキモイのだ。

 

 例えば、判子画像は単純にやめれば良いだけだ。まともな企業なら、情報の管理をする義務がある以上、こういった提出物の承認フローを管理するシステムが導入されているはずだ。判子なんていくらでも複製可能なデータに信頼性はない。

 社外秘、みたいな判子についても必要ない。タイトル部分などに社外秘、NDAなどと書いておけば十分だ。画像であれ何であれ暗号化されていない電子データなどいくらでも改変出来るのだから、それをもって変更されていないかどうかなど分からない。

 それどころか、むしろ画像の様に後から処理しにくいデータで管理するべきではない。社外秘、NDAなどの文字情報の状態なら、PDF化する際に処理を加えて、たとえばフォントの中に情報を埋め込むことも容易だ。判子画像の状態でも不可能とは言わないが、難易度は上がる。管理する情報は平易である程良い。

japan.cnet.com

 ということを、上の人間が納得しないといけないので、日本では絶対に後数十年はなくならない。彼らは、判子があれば信用出来るなんて甘いことは当然考えてはいないが、判子がない物はそもそも視界に入らない。なんせ、日本のトップ達はパソコンなんて下賤なもの触ったこともないが、指示を出すのは天才な高貴なお方達なのだから。  

 さて、上の人間は承知しないだろうが、それでも判子に関しては割と納得してくれる人はいる。(白い目では見られるが)

 しかし、こっちが問題だと納得してくれた一般人は未だ誰一人いない。

f:id:nodamushi:20181208231122p:plain:w320

 

 私が思う問題点は大きく以下の二つである。

  1. 入力が面倒くさい
  2. プログラムで情報を抜き出すのが面倒くさい

 このフォーマットは基本的に、「読む側」の事しか考えておらず、書く、プログラムで処理するということが面倒くさい=コストとなる。

 まず、入力が面倒くさい点について。例えば、少しでも面倒くさくない入力はこういう状態だ。

f:id:nodamushi:20181208233331p:plain

 先ほどと違って、上から下に入力するだけである。横に見る必要はないし、構成の意味を考える必要が無い。とにかく、上から下に入力していけば良い。見逃すことも少ない。

 しかし、普通の人は、元の表組み状態を面倒くさいと思わないので、この理屈は通じない。むしろ、縦スクロールが入る分、面倒くさいと感じたり、冷たいと感じる様だ。

 次に、プログラムで情報を抜き出すのが面倒くさい、に関してだが、普通の人間はそもそもプログラムはおろか、情報処理をしない。だから、この書き方は後で情報処理したい時にきっと困ることになる、と言っても、「ふーん、で?」で終わりである。関係ないのだ。

 しかも、実際、殆どの書類は今後何らかの情報処理されることもなく、どこぞのフォルダの文鎮と化してお終いである。一回見られてお終いなのだ。効率化というのは、何度も行われるからこそ意味を成す。実装に1日、効率化は一人1分(しかも1回しかやらない)なんかだと、500人は入力しないとペイしない。実に無駄な効率化だ。

 さらに、こういうことを実現しようと思えば、やってくれる人が居るならそれでいいが、誰もいないなら、そのための余計な勉強までしなくてはならない。

 そもそも最近はパソコンなんて、時代遅れな骨董品を使える方が稀だ。ただでさえ、社会に出たら強制的に使わされる苦痛を味わされるのに、更にまだ勉強しろというのは、流石にちょっと拷問に近い行為だとは思う。(感覚が分からないなら、80年代のワークステーションを強制的に使わされて、かつ、BASICやCOBOL、ないしパンチカードを覚えさせられると考えてみよう。吐き気がしてくるはずだ。)

 誰が、そんな将来役にも立たない(っていうか淘汰される)パソコンの勉強をするというのだ。それぐらいなら、速記や会計の勉強をした方がマシである。

 

 というわけで、言うだけ無駄である。今後も変わらないであろう。パソコンは手書きの清書機械でしかないのだ。

 むしろ、機械学習の性能が上がって手書き文字認識精度が上がったせいで、書類は手書きに回帰する可能性すらあると言って良い。

Shell(Bash,Power Shell)でバージョンソート

x.y.z形式のバージョンをソート

 バージョンの形式は、「接頭辞x.y.z」とする。これのソートは割と簡単。(接頭辞はvとかver.とか)

 

Shell(Bash)

※最初のVERSIONは、各行にversion情報がある情報を、パイプに流すコマンドなど

VERSION   | sed 's/^接頭辞//' | sort -n -t . -k 1,1 -k 2,2 -k 3,3 | sed 's/^/接頭辞/'

 sedで一度接頭辞を削除した後、「.」で文字を区切って数値としてsortし、最後に接頭辞をsedで再度付加する。

Power Shell

※最初のVERSIONは、各行にversion情報がある情報を、パイプに流すコマンドなど

VERSION |  sort {[Version]$_.Replace('接頭辞','')} 

 接頭辞を削除した文字列をSystem.Versionとしてソート。PowerShellの方が簡単だと…

 

x.y.z-αをソートしたい

 「接頭辞x.y.z」で済めば良いのだが、v0.1.2を複数作りたい(alpha版やらbeta版やら)とかなると面倒。しかも、-αの部分はあったりなかったりすることもよくある。

 ここでは、何もなし「接頭辞x.y.z」、日付「接頭辞x.y.z-YYYYMMDD」、ベータ版「接頭辞x.y.z-b0」、アルファ版「接頭辞x.y.z-a0」の順に並べる。

 

Shell(Bash)

上手い方法は思いつかなかったので、もうAWKでa,b,日付をゴリゴリと数値に変換した。

※最初のVERSIONは、各行にversion情報がある情報を、パイプに流すコマンドなど

VERSION | \
gawk 'match($0, /([0-9]+)\.([0-9]+)\.([0-9]+)(-([ab])?([0-9]+))?/, v){
  if(v[4]==""){v[5] = 0;v[6]=0;}
  else if(v[5]==""){v[5] = 1;}
  else if(v[5]=="b"){v[5] = 2;}
  else if(v[5]=="a"){v[5] = 3;}
  printf "%3s%3s%3s%s%8s@%s\n",v[1],v[2],v[3],v[5],v[6],$0;}' |\
sort  | sed 's/^.*@//'

 AWKで無理矢理-αの部分を数値の形式に変換している。格好いい事なんてせずに、もうベタベタの変換だ。

 -α部分が何もなければ「0.0」に、日付なら「1.日付」に、ベータ、アルファならそれぞれ2,3の番号を振った。RCやら色々増やすなら、if文を追加すれば良いでしょう。

 最後にprintfで成形して出力する。%3sなんかの文字列長は好きな様にすれば良いんじゃないかな。お好みなら%03dでもいいね。適当な区切り文字(@)で$0も保存して、後で取り出せるようにもしてある。(文字数カウントしても良いけど、面倒くさいし)

 後は、sortで並び替えて、sedで@以降を取り出す。

 

PowerShell

 やっぱゴリった。誰か上手い方法を教えて。

※VERSIONは、各行にversion情報がある情報を、パイプに流すコマンドなど

$version_regex=[regex]"(\d+\.\d+\.\d+)(-([ab])?(\d+))?"
function Get-VersionKey($x){
    If($x -match $version_regex){
        $s = $Matches[1]
        If(!$Matches[2]){
            $s = $s+"0.0"
        }ElseIf(!$Matches[3]){
            $s = $s+"1." +$Matches[4].PadLeft(8,"0")
        }ElseIf($Matches[3] -eq "a"){
            $s = $s + "3."+$Matches[4].PadLeft(8,"0")
        }ElseIf($Matches[3] -eq "b"){
            $s = $s + "2."+$Matches[4].PadLeft(8,"0")
        }
        return [Version]$s
    }
}

VERSION | sort { Get-VersionKey($_) }

 やり方はさっきとBashとほぼ一緒。一度"x.y.zα.n"という形に変換した後(日付のYYYYMMDDが8文字なので、PadLeftで全て8文字にしてある。変換される型はint32なので、ギリギリ入る。)、System.Versionに変換、それを元にソートする。

 

参考

PowerShell実践ガイドブック ~クロスプラットフォーム対応の次世代シェルを徹底解説~

PowerShell実践ガイドブック ~クロスプラットフォーム対応の次世代シェルを徹底解説~

「シェル芸」に効く!AWK処方箋

「シェル芸」に効く!AWK処方箋

SystemVerilog: ビット長拡張(符号拡張)の書き方

 Mbitの信号をNbitに符号拡張したい、0fillしてビット長を変更したい場合、Verilogは書くのが面倒くさい。でも、SystemVerilogなら短く書けた。

結論

 以下のコードで符号拡張、ビット長拡張が出来る。S,Dはパラメータでも、直値(数値)でも良い。

logic [S-1:0] src;
logic [D-1:0] dst_unsigned  ,  dst_signed;

assign dst_unsigned = D'(unsigned'(src));
assign dst_signed   = D'(signed'(src));

 これ、assignで何やってるかというと、srcのキャストである。以下の様にキャストされてdstに接続される。

  1. unsigned'(src)、signed'(src) でsrcをunsigned型、signed型にキャスト
  2. D'(x)でxをDbitにサイズをキャスト

 サイズをキャストする際には、符号が考慮される。unsignedは必要はないはずだが、明示した方がいいと思う。こう、暗黙って嫌いなんです。

 詳細はSystemVerilog 3.1a Language Reference Manualを参照して欲しい。27p(PDFビューア上では43p)辺りである。

 一応、Verilatorによるシミュレーション、Cadenceのツールによる合成で確認しています。あと、Quartus PrimeでElaborateは通った(ピンアサインとか面倒くさいし、合成はしてない)

 

Verilogでのよくある書き方

 例えば、以下の記事の様に一般的な書き方をするとこうなる。

logic [S-1:0] src;
logic [D-1:0] dst_unsigned,dst_signed;

assign dst_unsigned = { {D-S{1'b0}} , src };
assign dst_signed   = { {D-S{src[S-1]}} , src };

 これ、問題があってD,Sがパラメタライズされていて、さらにD-S が0になるとき、処理系によってはエラーになるのだ。糞言語め

 先に示したキャストを使わずに、D=Sの問題を何とか回避しようとすると、以下の様にならざるを得ない。

always_comb begin
  dst_unsigned = {S{1'b0}};
  dst_signed   = {S{src[S-1]}};
  dst_unsigned[S-1:0] = src;
  dst_signed[S-1:0]   = src;
end

//もしくはfor文
always_comb begin
  int i;
  for(i = S; i < D ; i = i + 1)begin
    dst_unsigned[i] = 1'b0;
    dst_signed[i]   = src[S-1];
  end
  dst_unsigned[S-1:0] = src;
  dst_signed[S-1:0]   = src;
end

 うーん、まぁ、合成は出来るだろうけど、綺麗じゃないよねぇ。

参考URL

GitBucketにorg-mode追加するPlugin作った

 事の発端はこのたけぞうさんのツイートとブログ記事。

 このツイートに反応して、Excelプラグイン使いたいと呟いたついでに、ウッカリこれを呟いたのが間抜けだった。

 

というわけで、作った

 というわけで、本当はVS Codeの俺様用Emacsプラグインを作ろうと思ってたはずだったのに、何故かGitBucketのプラグインを作ってしまっていた。どういうことだってばよ。

gitbucket-org-pandoc-plugin

gitbucket-org-js-plugin

 何故か二つある。どういうことだってばよ。

 片方はpandocを使って変換する。つまり、サーバー側で変換処理を負担する。サーバー側にpandocコマンドが使える様になっていないと使えない点には注意。編集画面作るのが怠かったのでやらなかったが、いつか、pandocのフィルタを管理者が設定できるようにしたい。

 もう一方はmooz様のorg-jsを使って変換する。つまり、変換はブラウザ側が負担する。

 好きな方を選んで下さい。

org-pandoc版

org-js版

なんで二つ作ったの?

 ぶっちゃけ、JavaScript触りたくなかったから。

 あと、プラグインにリソースを含める方法が分からなかったから、pandocなら入れなくて良いなって。

 しかし、実際に作ってみたら、結局CSSを入れる必要があって、四苦八苦して入れた。 だったら、もうorg-js版も作っちゃえと。

 はい、そんな感じです。馬鹿じゃねぇの?タヒねば、と罵られても仕方ないですね。すいませんでした。

 では。

 個人的にはPadToolsプラグインが一番欲しいかな。なおぶろさんに許可とって作ってみようかな。

Eclipse プラグイン開発:TM4Eによるエディタ開発

Eclipse プラグイン開発 目次


 本記事ではEclipse Photon以降のEclipseで、TM4Eを使った場合のシンタックスハイライト、インデントの実装について解説する。 TM4EはEclipse Photonで追加されたRustなどにも使われている。

 本記事ではContents Assist(補完機能)については触れないが、Eclipse Photon以降であれば、LSP4E(Language Server Protocol for Eclipse)を用いるのが良いだろう。

目次

下準備:開発する言語の内容

 今回はサンプルなので、非常に単純な仮想言語HOGEの実装をする。ファイルの拡張子は.hogeである。

 仮想言語HOGEはサンプルなので厳密な定義をする気はないが、こんな感じの構文とする。

    // コメント
    fn name int:value{
      string piyo = "piyopiyo"
      if value == 1 {
        piyo = "moge"
      }else if value == 2{
        piyo = "hoge\!"
      }
      return piyo
    }
    name 10

ざっくりしたルール

  1. {}でブロックを生成する
  2. 複数行にわたる構文はサポートしない
  3. fn [a-z]+[ type:name]*で関数定義
  4. キーワードはif,else,=,,return
  5. 型はintとstringのみ
  6. ""でstring。
  7. 数値は10進数整数のみ
  8. 関数呼び出しは name 引数
  9. if,fnの後は必ず{}によるブロックが必要
  10. //で文末までコメントアウト

TM4E(TextMate support in Eclipse IDE)

 Eclipse Photonからシンタックスハイライト等を実装するのに、TextMate構文(.tmLanguage)を使うことが出来るプラグインTM4Eが、公式で提供される様になった。 .tmLanguageはVisual Studio Codeもサポートしており、汎用的な定義と言える。というか、TM4Eがそもそも、VS Codeのvscode-textmateから作られている。

 Eclipse専用に開発するよりずっとエコで、Eclipseの謎仕様を追いかける精神的苦痛からも解放される。

 現段階ではややバギーではある(執筆時はv0.2)が、おおよそは動くので、TM4Eを使うという選択肢は十分にありだろう。

 デフォルトの状態ではTM4Eはインストールされていないので、開発を開始する前に、インストールをしておく。

 Menu:Help→New Install Software…を開き、公式アップデートサイトを選択し、TextMateをチェックする。検索ボックスにTextMateと打ち込むと、探しやすい。

 選択したら、Nextを押す。次の画面でもNextを押す。

 ライセンスに同意して、インストールを開始する。インストール完了後、再起動をする。

Dependencies

 plugin.xmlを開き、依存関係に、以下を追加する。

  • org.eclipse.ui
  • org.eclipse.core.runtime
  • org.eclipse.ui.genericeditor
  • org.eclipse.tm4e.core
  • org.eclipse.tm4e.languageconfiguration
  • org.eclipse.tm4e.registory
  • org.eclipse.tm4e.ui

Content Type

 まずは.hogeファイルをEclipseに認識させる為に、Content Typeを定義する必要がある。

 

  1. plugin.xmlのExtensions(拡張)タブを開く
  2. Add(追加)ボタンを押して、org.eclipse.core.contenttype.contentTypesを追加する。
  3. org.eclipse.core.contenttype.contentTypesを右クリックし、ポップアップからNew→content-typeを選択し、content-typeを追加する。
  4. 以下の表の内容を設定する

 

項目 内容 説明
id editor.sample.hoge ID. 全てのプラグインを含めて、ユニークな名前である必要がある。
name HOGE Language File 人が読める名前
base-type org.eclipse.core.runtime.text このファイル情報の継承元。特にない場合はorg.eclipse.core.runtime.textにする
file-extensions hoge ファイル拡張子

 この段階で、このプラグインを導入したEclipseを起動し(図の赤く囲ったボタンで起動可能)、.hogeファイルを適当に生成し、プロパティを見てみよう。 TypeのところがFile (HOGE Language File)となっていて、上記の設定が認識されている。

Generic Editor

 次に、.hogeを開いた時に使用するエディタを設定する。  かつては自分でエディタを作成し、エディタを登録し、そのエディタを使う様に設定するという面倒くさい作業が必要だったが、 TM4Eを使う場合は単にGenericEditorでよい。素晴らしい。

 

  1. plugin.xmlのExtensions(拡張)タブを開く
  2. Add(追加)ボタンを押してorg.eclipse.ui.editorsを追加する。
  3. org.eclipse.ui.editorsを右クリックし、ポップアップからNew→editorContentTypeBindingを選択し、追加する。
  4. 以下の表の内容を設定する。書くのが面倒なら、右のBrowse…から検索すると良い。

 

項目 内容 説明
contentTypeId editor.sample.hoge Content Typeで設定したidを指定する。
editorId org.eclipse.ui.genericeditor.GenericEditor どのエディタで開くか指定する。

.tmLanguageを作成

 .tmLanguageを実際に作成していく。

 最初に、プラグインを配布する際のバイナリに、構文ファイルが追加される様にしておこう。

  1. grammar/hoge.tmLanguage.jsonを作成する
  2. build.propertiesを開く
  3. 「Binary Build」に「grammar」ディレクトリにチェックを入れる

 grammarディレクトリが不都合なら、別なディレクトリ名にしても良い。 なお、今回はjsonにしたが、tmLanguage形式が良い場合やexsdで書きたい場合は、それに変更する。 どの形式が良いのかは正直よく分からないが、jsonにしておけば、何処でも使えそうな雰囲気はある。後ブログでシンタックスハイライトしやすい。

 

 次に、.hogeファイルと、grammar/hoge.tmLanguage.jsonを結びつける設定をする。

  1. plugin.xmlを開き、Extensionsタブに移動する
  2. Addボタンを押し、org.eclipse.tm4e.registry.grammarsを追加する
  3. org.eclipse.tm4e.registry.grammarsを右クリックし、ポップアップメニューからNew→grammarを選択し、追加する。
  4. 同じくポップアップメニューからNew→scopeNameContentTypeを選択し、追加する。
  5. grammarとscopeNameContentTypeを以下の内容で設定する

 

grammar:

項目 内容 説明
scopeName source.hoge スコープ名。source.言語名にしとけばいいのかな
path grammar/hoge.tmLanguage.json 構文ファイルのパス

scopeNameContentType:

項目 内容 説明
scopeName source.hoge grammarのscopeNameを指定する
contentTypeId editor.sample.hoge Content Typeを指定する。

 これでgrammar/hoge.tmLanguage.jsonがhogeファイルを開いた時に取りこまれる様になる。

 最後に、TM4Eが提供するPresentation Reconcilerを.hogeファイルに登録すればお終いだ。 Presentation Reconcilerはドキュメントが変更された時の領域分割や色の設定をするクラスで、EclipseのAPIを叩いてプログラムするとかなり面倒くさい。泣きたくなる。

 

  1. plugin.xmlを開き、Extensionsタブに移動する
  2. Addボタンを押し、org.eclipse.ui.genericeditor.presentationReconcilersを追加する
  3. presentationReconcilerを以下の内容で設定する。

 

項目 内容 説明
class org.eclipse.tm4e.ui.text.TMPresentationReconciler IPresentationReconcilerの実装
contentType editor.sample.hoge Content Type

tmLanguageの書き方はTextMate Language Grammarsを参照せよ。JSONで書く場合は、単にJSONに直すだけである。

{ 
  "scopeName" : "source.hoge",
  "name" : "HOGE Language",
  "fileTypes":[".hoge"],
  "uuid" : "a75f98cf-a3d0-4606-b1e5-1067590c0618",

  "patterns" : [
    {
      "name"  : "string.quoted.double.hoge",
      "begin" : "\"",
      "end"   : "\"",
      "patterns" : [
        { 
          "name" : "constant.character.escape.hoge",
          "match" : "\\."
        }
      ]
    },

    {
      "name" : "storage.type.hoge",
      "match" : "\\b(int|string)\\b"
    },
    {
      "name" : "keyword.control.hoge",
      "match" : "\\b(return|if|else|fn)\\b"
    },
    {
      "name" : "comment.line.double-slash.hoge",
      "begin" : "//",
      "end" : "(?=$)"
    },
    {
      "name": "keyword.operator.hoge",
      "match" : "==|!="
    },
    {
      "name" : "constant.numeric.hoge",
      "match" : "-?[0-9]+"
    }
  ]
}

 UUIDはWELLHATで生成した。

 これでsample.hogeに冒頭のサンプルコードを打ち込んでみよう。(起動時にファイルを開いてしまっている場合は、一旦閉じてから、再度開く)

f:id:nodamushi:20181008200728p:plain

 簡単にシンタックスハイライトをすることができた。

 ところで、たまに何故か「// コメント」が文字化けするという現象にぶち当たった。

f:id:nodamushi:20181008223652p:plain

 これ、毎回じゃなくて、なったりならなかったりだ。しかも、// aコメントとかすると直る。(aを外すと化ける)。 どうやら、フォントのエラーっぽい。Eclipseでコメントだけ文字化けした場合は、フォントを確認しよう。

language-configuration.json

 VS CodeのLanguage Configuration(の一部)を使うことが出来る。 これによって、{を書くと自動的に閉じたり、インデントをさせたりといったことが可能になる。 随分楽だ。

language-configurations/language-configuration.jsonに以下を記述する。

{
   "comments": {
     "lineComment": "//"
   },
   "brackets": [
     ["{", "}"]
   ],
   "autoClosingPairs": [
     { "open": "{", "close": "}", "notIn": ["string"]  },
     { "open": "\"", "close": "\"", "notIn": ["string"] }
   ],
   "surroundingPairs": [
       ["{", "}"],
       ["\"", "\""]
   ]
}

 

 括弧{}のインデントと、{や"を入力すると自動で閉じる、対応するペアを選択する機能が、これだけで実装された。

 後は、これをTM4Eが認識できるようにする。

  1. build.propertiesを開く
  2. Binary Buildのlanguage-configurationsにチェックを入れる
  3. plugin.xmlを開き、Extensionsタブに移動する
  4. Addボタンを押し、org.eclipse.tm4e.languageconfiguration.languageConfigurationsを追加する
  5. languageConfigurationを以下の内容で設定する。

 

項目 内容 説明
path language-configurations/language-configuration.json 設定ファイルのpath
contentTypeId editor.sample.hoge Content Type

 

 たしかにこれで、何か良い感じには動くのだが、割とBuggyである。 例えば、文字列の閉じ"で、次の文字列の開始"が選択されたり、文字列の中でも"や{の自動クローズされたり、 インデントが揃ってないところで{の後に改行すると}の位置が変だったりする。(インデント計算がn*4でしか発生してないっぽい)

f:id:nodamushi:20181008211527p:plain

 まぁ、執筆時はv0.2だし、まだまだこれから。たぶん。

まとめ

 Eclipseのエディタ開発をするのは、かなりの重労働だった。しかし、TM4Eを用いれば、非常に簡単にハイライト機能、インデント機能などを実装することが出来る。  今回は全くJavaによるプログラミングをせずに済んだ。

 LSP4Eと組み合わせれば、VS Code対応すれば、Eclipse対応も大してコストがかからなくなる。いずれ、実装が面倒くさいというEclipseの欠点は、間違いなく解消されるだろう。

 でも、まだまだBuggyである点は注意する必要がある。

参考