去年も ふりかえり だけはしていたので今年も。

食事

自炊率が圧倒的に下がった。 週に多くても土日の夕飯を作って2回とか。 バリエーションは オムライス/鯖バーグ/野菜炒め/焼きそば。

仕事

いろいろやっていた。 相変わらずWebぽくない案件が多い. C++ を書く機会が一番多かった気がする。

かといって、特に C++ に詳しくなれた気もしないけれど。

相変わらず労働環境も良い。

お金

貯金も少し増えてきたために財布の紐が緩くなって、去年比で見ると出費が増えている気もする。

先月の電気代が15000円で驚いた。電気代は暖房機の消し忘れが複数回起こったことによるものだけれど。

アニメ

animetick で視聴管理をしているので、それで確認した。

各年の視聴本数(完走数)を数えてみる(分割Nクールは分割毎に1本とカウント)と以下のようになった。

• 2014年: 46本
• 2015年: 40本

だいたい平均して各期10本くらい視聴していた。

2015年の個人的なベストは のんのんびより(2期) 。 劇伴、合間合間のギャグ、キャラクター、OP/ED などいろいろなものがほぼ自分好みなので見ていて気持ちよかった。 BOXが出たら買います。

ちなみに2014年は ばらかもん 。

プログラミング言語

スクリプト言語による効率的ゲーム開発 C/C++へのLua組込み実践 という本を買っていたので、 この本を読みつつ、去年は Lua をやろうとしたが、あまり書けなかった。

Lua を書く機会が何度かあったけど、最終的には他の言語で書いてた記憶がある。 スクリプトから少し重たい外部コマンドを複数回実行などして その結果を加工するような用途の時に使ってみたけど、そのケースでは外部コマンドの起動オーバーヘッドが ruby と比較してかなり大きくてダメだった。最終的に go に置き換えたりしたし。

そのせいもあって、昔は Lua が最も高速なスクリプト言語である、という文言をよく見た気がしたけど ruby と比較してそこまで早くないなぁと思った。

C++のアプリケーションからLuaのスクリプトをリロードして動作を変えるのはやってて面白かった、というより爽快だった。 コンパイルしないのは最高。

本

読んだ本

• コンピュータの構成と設計(3版)下巻
  • 感想
• CPUの創りかた
  • 感想
• スクリプト言語による効率的ゲーム開発 C/C++へのLua組込み実践
• 統計学が最強の学問である
  • 感想覚えてない..
• めぞん一刻
  • 続きが気になるので最後まで読めた

読んでる途中の本/積んでる本

• 深層学習
  • Chapter.7 で止まってる. そのうち読み終わると思う.
• 圏論
  • 1章末尾の練習問題を解いている所で止まってる.
• “数学ができる”人の思考法~数学体幹トレーニング60問
  • 魔がさした時の暇つぶしに最適
• セキュリティコンテストチャレンジブック

来年

最近肩とか腰とか痛いので、すこやかににすごしたい。

当日は別の遊ぶ予定があったが無理やり数十分くらい時間をもらって参加したのだけど 満足に１つも解けず…。

もうちょっとやるならやるでちゃんと時間をとってやるべきだった( ；´Д｀)

本戦がかなり難しかったらしく面白そうだが、そもそも自分からしたら予選で難しいので、予選を解いてみた

D. 庭園

300x300のセルが与えられて、各セルに整数(負数を含む)が与えられており、 セルの中で長方形を二つ選んだ時に、各長方形の整数の和が最大になるように選ぶ問題。

簡単に考えられるのは事前に各行/各列で累積和を計算しておいて、あとは長方形を全列挙するという 方針の解き方で累積和の計算に O(H*W)、長方形の列挙に O(H^2*W^2)

あとは二つ選ばないといけないので、組み合わせを試すために列挙した長方形の端っこの x座標とy座標とコストのペアを覚えておいて重ならないように組み合わせを試した

http://dwango2016-prelims.contest.atcoder.jp/submissions/632337

で、結局 O(H^2 *W^2) がとれないので解説を読む。

O(H * W^2) でコスト最大の長方形を探索するが、その際にx座標でどこからどこまでの情報とコストのペアが 得られるので、(x座標で見て)重ならない組み合わせが列挙できて、あとはセルを転置して同じことをする、だった

http://dwango2016-prelims.contest.atcoder.jp/submissions/637939

ちょっと前に OpenH264 というエンコーダに小さなプルリクを出した時のメモが以下のように今も残ってた。

この Mac のデフォルトのメモ帳は要素を増やすとそれなりに動作が緩慢になっていくので消そうと思ったけど ただ消すのも忍びないので書き残しておくことにした。

メモでは色々調べていたけど、作業的には 小さなもの だった。

ことの発端としてはこういうサイト を見ながら、小さなSIMDプログラムを書く機会があったが、本当に小さくてすぐ終わってしまったので 他にも何かしらで書けないかと考えた時についでにOSSにプルリク投げてみるか、という機運が高まったことから始まった。 最終的にSIMDコード書けてないわけだけど…。

さらに、SIMDは intrinsics で書きたかったのだけれど、 SIMDはどこもアセンブラで、メモを見返してみるとアセンブラについて調べた部分がいくらかあった。

書いてて思い出してきたが AVX2の開発も受け付けてるという記述があり、書こうと思ったら そもそもAVX2がプログラム内で有効であるか検出する機構がないので、とりあえずそれを書いたという流れだったと思う。

コミットログを眺めてみたけどぱっと見AVX2コードは入ってなさそう。今はあんまりやる気がない..。

もう書くことがないので、あとはつらつらメモの残りを羅列することにする。 プロジェクトを何も知らない人が読んでも意味がわからず、メモ同士の関連性も低く 本当に有用にするには補助的な文章が必要だろうけど面倒くさいのでしない。

あと、ここに書いてあることの正しさは保証してませんので予めご了承。

OpenH264の解析

ISVCEncoder

空っぽのクラス。抽象クラス。 具象クラスは CWelsH264SVCEncoder になる。メインのでかいクラス。 WelsCreateSVCEncoder() は encoder/plus/src/welsEncoderExt.cpp にある。

エントリーポイント

codec/console/enc/src/welsenc.cpp にコンソール版の main() がある。

• ISVCEncoder を初期化
• ProcessEncoding でエンコードを発火
  • ISVCEncoder, SEncParamExt, SFrameBSInfo
    • SFrameBSInfo の実際のデータを持ってるのは SLayerBSInfo
      • Layer の概念がわからない..
  • SSourcePicture
    • ffmpeg の AVFrame とほぼ同じ
      • iStride = { luma_stride, chroma_stride }
      • pData = { luma_ptr, chroma_ptr }
  • fread で1枚ずつ読む
  • ISVCEncoder->EncodeFrame(SSourcePicture, SFrameBSInfo)

EncodeFrame

EncodeFrameInternalを呼び出す。入力がI420じゃない場合は中断。

EncodeFrameInternal

• WelsEncoderEncodeExt() // 1枚のフレームのエンコード発火
• UpdateStatistics() // 統計情報更新

WelsEncoderEncodeExt

メインな関数。色々呼び出す。分かったものだけ記述。

• DecideFrameType()
  • フレームタイプ決定
• BuildSpatialPicList()
  • とりあえず入力がこのリストに入る
• AnalyzePictureComplexity()
  • ここでの計算がレート制御と関係あるっぽい
• iEncodeNal()
  • NALをつくってる

DecideFrameType

フレームタイプを決定する。x264にも似た名前の関数があるけど、x264と違ってここから探索が発生することはなさそう

• イントラ周期ならIDRにするとか
• InterだけどSKIPフラグがあればSKIPにするとか
• シーンチェンジ検出 (IDRにする)

Intra予測の関数

• WelsMdIntraMb
  • WelsMdI16x16
  • WelsMdI4x4
  • WelsMdI4x4Fast
    • こっちの方がなぜか行数は長い
  • WelsMdIntraChroma
  • WelsMdIntraSecondaryModesEnc

MEはどこ/MEはどこから発火する?

svc_motion_estimate.cpp:WelsMotionEstimateSearch[Static|Scrolled]

encoder_ext において pFuncList->pfMotionSearch に代入されている。 代入後 core/src/svc_base_layer_md で利用されている。

• 4種類 (16x16, 8x16, 16x8, 8x8) 存在
• どれも SATD を返す

WelsMotionEstimateSearch は内部で pFuncList->pfCalculateSatd を呼び出す

• pfCalculateSatd の実行時引数には sSampleDealingFuncs.pfSampleSatd[BlockSize] を指定して呼び出す
  • 計算の実装はこちらに
• sSampleDealingFuncs.pfSampleSatd はどこで関数が設定されるのか
  • core/src/sample:WelsInitSampleSadFunc で設定
  • Sad という名前だけど Satd の関数も設定されうる
  • cpuid で分岐し SIMD 版も設定している

WelsMdP16x16 はどこから呼ばれる

• svc_base_layer_md
  • WelsMdInterMb (mode-decision inter macroblock)
    • P16x16 だけ試す？
  • WelsMdInterSecondaryModesEnc (refinement)
    • ちゃんと他の予測タイプも試す
    • core/src/md
      • MeRefineFracPixel (hpel)
      • MeRefineQuarPixel (qpel)
  • WelsMdInterEncode
    • WelsInterMbEncode
      • WelsDctMb
      • WelsEncInterY
    • WelsPMbChromaEncode
      • pFunc->pfDctFourT4() (CbCrのために2回呼ぶ)
      • WelsEncRecUV() (CbCrbのために2回呼ぶ)

WelsMdInterMb と WelsMdInterMbEnhancelayer の違い

• Enhancelayer
  • step(3) とあるので 流れは通常の WelsMdInterMb と同じものを汲んでいるぽい
  • 1, まずSKIPにできるか試す
    • WelsMdInterJudgePskip の結果を見ている (boolean)
    • できそうならば WelsMdInterDecidedPskip をコールして終了
  • 2, Intraが選択できない場合
    • とりあえず WelsMdInterP16x16 にしてしまう.
    • WelsMdInterSecondaryModesEnc();
  • 3, 2でIntraが選択できた場合
    • とりあえず I_16x16 にしてしまう
    • スキップが有効ならばスキップに
    • WelsMdInterDecidedPskip をコールして終了
    • そうでない場合は WeldMdIntraSecondaryModesEnc
• 分岐条件
  • svc_encode_slice.cpp: 670 の (kbBaseAvail && kbHighestSpatial) で分岐

アセンブラ

読む上で気をつけたこと。

• 各命令実行後のレジスタの状態
  • フラグレジスタなど
  • SIMD命令の場合は無視して良い？
• 呼出し規約

データの処理単位

• b: byte(8bit)
• w: word(16bit)
• d: double word(32bit)
• q: quad word(64bit)
• dq: double quad word(128bit)

セミコロンの前の文字はよく命令の suffix についている。

メモってあった頻出命令

mov[d|q|dqa|dqu|sxd]

• movd
  • move double word : オペランドに xmmレジスタなども取れるが 32bit転送命令
• movq
  • move quad word : 64bit 転送命令
• movdqa
  • アラインメントあり128bit転送命令
• movdqu
  • アラインメントなし128bit転送命令
• movsxd
  • double word(32bit)を quad word(64bit)に符号拡張して転送

lea

アドレス計算命令。フラグレジスタが変更されない。アドレス自体の演算に利用。

pxor

ビット単位の xor を実行。オペランドには 64bit同士、128bit同士を指定することができる。

psub[b|w|d]

オペランドに64bit同士、128bit同士をとれる。 suffix がそれぞれ byte, word, double-word を指すので 8bit/16bit/32bit スロットでの演算となる。

pmax[s|u][|b|w|d]

レジスタを2つとり、スロット毎に比較して最大値を格納する。 値を評価する場合に符号あり・なしとスロットの大きさで命令が分かれる。

psadbw

符号なし8bit整数で絶対値誤差の合計値を計算して格納レジスタの下位16bitに書き込む。 オペランドに64bit/128bitレジスタ同士を取る。

shufps

名前的にはシャッフルを押すほどのシャッフルでもないけど確かにシャッフル可能な命令。 オペランドを3つとり(うちSIMDレジスタが2つ)、スロットを32bitで評価してそれぞれの SIMDレジスタから2つのスロットを格納先へ書き込む。

pmaddubsw

Multiply-ADD Unsigned Byte, Signed Word

乗算はオペランドレジスタを符号なし8bit整数スロットで評価し、 次のオペランドレジスタは符号あり8bitで評価。 乗算の結果を2つずつ和にして16bitスロットとして格納先レジスタへ書き込む。

movehl_ps

各 hi-64bit を2つのSIMDレジスタからとって merge。

YASM/NASM

用いられているアセンブラ。

codec/common/x86/inc_asm.asm に共通マクロがある。

わかったものだけ。

• WELS_EXTERN
  • global 宣言
• SIGN_EXTENSION
  • movsxd で符号拡張してコピー
• WELSEMMS
  • emms 命令
• PUSH_XMM
  • SIMDレジスタ退避マクロ
• POP_XMM
  • PUSH_XMM と対になるマクロ
• retrd
  • 戻り値レジスタの alias で主に eax
  • retrq なんてのもあった

AVX2の検出

• eax=0 で cpuid 命令を実行後に eax に入る値(基本機能の最大機能番号)が7以上
  • eax=7 で cpuid 命令を実行後に ebx & 0x20 が 1 である時AVX2が有効

AVXの検出

• eax=1 で cpuid 命令を実行後に (ecx & 0x18000000) == 0x18000000 である
  • xgetbv が有効で xgetbv を実行後に (eax & 0x6) == 0x6 である時AVXが有効

OpenH264のアセンブラ関数

あんまり調べてない。

WelsSampleSadFourWxH

4つ分計算する。この4つ分は上下左右の1pixelだけずれたものを計算している。

WelsSampleSad4x4_mmx

ナイーブに実装されている。mmxなのでレジスタ長が64bitなので8bit*8で2line分まで入るので よしなにロードして2回 psadbw するだけ。

WelsSampleSad16x16_sse2

128bitSAD命令で 4x16 を4回呼ぶ構成。

場所

codec/common/x86/satd_sad.asm

例によって、連休中は記事にまとめることにする。

基本的に、あまり外出の予定はない。

4/27

前日の飲み会で久しぶりにお酒を沢山飲んだせいなのか、 昼頃起きてから頭痛がひどくて基本的に動きたくなかったし動けなかった。

が、前日まで同期を家に泊めていたので、それらの片付けとか部屋の掃除とかをした。

4/28

http://mtgwiki.com/wiki/ブースタードラフト

これで遊んでた。6時間くらい。

4/29

オブジェクト指向入門 第2版 方法論・実践 を少し読んでは寝てを繰り返してた。

同期に誘われて買い物に出かける。少し高い(4kくらい)ドライヤーを買った。 ドライヤーの風速が2倍弱くらいになってだいぶ髪が乾くのが早くなって良い感じ。

4/30

朝飯にオムライスを作る。

メイヤー本を読み進める。やっと300/800ページくらいまで進んだ。連休中の目標としてはなんとか読み終えたいと思っていた。 これが読み終わると積んでる紙の技術書がなくなるので kindle と iPad air2 を買って電子書籍に移行したい。

openh264のコードリーディングをする。ビルドして出来た実行バイナリでYUVファイルをエンコードしてみようと思ったけど なんかうまくコマンドラインオプションがパースされない。コンフィングファイルでオプション値指定をやってもうまくいかない。エンコード結果がおかしくなる。 なぜか出力解像度が縦横半分くらいになってしまう。それにオプションがx264と互換性がない(当たり前だけど.)し細かいのでよくわからない。

最終的に vagrant で Ubuntu を用意して Qiitaにあるやり方で ffmpeg に組み込んだ形でなんとか普通のエンコードができた。

と思ってたけど、コンフィグファイルのやり方で普通にエンコードできた。LayerCfgで”layer”(よくわからない概念)用のcfgファイルも用意して動いた。でもなんかフレームレートがおかしい。

5/1

具合があまり良くないので多分横になってた時間が長かった。気がする。

5/2

AtCoder Regular Contest 038に参加したけど1問しか解けなかった。

解き直した。ゲーム系の問題の解き方が良くわかってなかった。Grundy数の「今の状態から一手で行ける状態のGrundy数に含まれていない最小の非不の整数が 今の状態のGrundy数」っていうのややこしいけどわかった気がする。

5/3

覚えてない..

結果 o o - -

提出 url

A

両端から1文字ずつ付き合わせていって4パターンで分岐。

1. ’*’ と ‘*’ なら OK
2. ’*’ と ‘[a-z]’ なら OK
3. ‘[a-z]’ と ‘*’ なら OK
4. ‘[a-z]’ と ‘[a-z]’ なら一致していれば OK そうでないなら NO

文字列長が奇数なら真ん中を省く。

B

貪欲にTiの小さいものから処理する。

実際にシミュレーションしてペナルティを計算する。

あとは階上どうしの掛け算をする。剰余の分配法則的なものはあまり知らないけど

ll bs = 1;
for (ll i = 1; i <= 10000; i++)
{
  bs = (bs * i) % mod;
  pw[i] = bs;
}

これで問題なかった。

C

最初のワーシャルフロイドはOKだけど、クエリ毎に打つことはできなくて けどO(V^2)でテーブル更新可能だった。解説スライドでたしかにという感じだった。気づかなかった。

無駄にワーシャルフロイドと更新部分のループをSIMDで描いたら200msくらい早くなった。

この記事にもあるように intrinsicsはSSE2まで使えるぽい。例にならってSSE4.1の_mm_min_epi32の代わりをインラインアセンブラで書いた。 AtCoder環境はどのバージョンのSIMDまでサポートしてるんだろう。

D

実際の値はいらないけどに大小比較をする場合は log が使えることを知った。

あと log(a*b)=log(a)+log(b) log(a/b)=log(a)-log(b) とか久しぶりだった。

BITの更新をするときに変位を足すのではなくて任意の値にしたい場合は負の加算でリセットすることでなんとかなることを知った。