コグノスケ

Might and Magic Book One TAS US版の世界記録を更新

目次: Might and Magicファミコン版

Might and MagicのTASですが、US版でもやってみました。現在のTASVideosの世界記録（8m 06s）はYouTubeで見ることができます（[TAS] NES Might and Magic: Secret of the Inner Sanctum "item glitch" by Dammit in 08:06.91）。

ほぼ初挑戦にも関わらず、現在の記録を34秒も大幅に更新できました（7m 32s）。解説をつけた動画をアップロードしましたので、ニコニコ動画へのリンクも張っておきます（【TAS】US版Might and Magic Book One 7分32秒 マップ付き）。

いきなり大幅更新できた要因は「JP版での積み重ね」でしょうね。

JP版のTAS動画作成にあたって、エンカウントの仕組みやマップの解析など色々調べました。実はこれらの知識はUS版でも通用します。なのでMAPは見放題、エンカウント予測もできます。苦労して見つけたメッセージスキップ、1.5倍速入力などもタイム短縮に役立ちました。

JP版とUS版の大きな違い

US版はJP版の2年後に発売されました。日本語→英語に変更するいわゆる普通のローカライズの他に、操作性がイマイチだったユーザーインタフェースを改修したようです。ところが改修にしくじったらしく、ひどいバグ（特定操作でアイテムが変化する）も追加されています……。

アイテム変化バグを突くと重要なイベントアイテムをゴミから捏造できて、真のアラマー王のクエストだけ達成すれば、あとはアストラルに特攻してゲームクリアです……。手紙、ゾム・ザム兄弟、オーラ、ボルカノ神殿、デューム城、などなどメインクエストは完全無視。ひどいなこれは。

てなわけでUS版はクリアタイムがめちゃくちゃ早いです。アイテム化けバグがなく正規ルートを通らざるを得ないJP版では達成できないと思います。

メモ: 技術系の話はFacebookから転記しておくことにした。大幅に修正。

PulseAudioで簡易リモート再生

目次: ALSA

遠くの部屋にあるPCで再生した音声を手元のスピーカーで聞きたい場合、スピーカーの線を延々と伸ばすよりリモート再生したほうが楽です。

リモート再生の方法はいくつかありますが、最近のLinuxディストリビューションであれば大抵はPulseAudioがインストールされていると思うので、PulseAudioのTCP送信機能を使うのが楽でしょう。

Cookieの設定

クライアントとサーバーが同じ内容のCookie（~/.config/pulse/cookieにある）を持っていないと、下記のようにAccess deniedといわれて接続できません。

$ PULSE_SERVER=192.168.1.10 speaker-test -D pulse

speaker-test 1.2.9

Playback device is pulse
Stream parameters are 48000Hz, S16_LE, 1 channels
Using 16 octaves of pink noise
ALSA lib pulse.c:242:(pulse_connect) PulseAudio: Unable to connect: Access denied

Playback open error: -111,Connection refused

クライアントにCookieファイルをコピーできない場合は、module-native-protocol-tcpにauth-anonymous=1を渡すと良いそうです。

サーバー側

サーバー側は音声を受け取ってスピーカーなどに送る役目を果たします。私はスピーカーの横にRaspberry Piを置いてサーバーにしています。PulseAudioの設定は簡単で、

# vi /etc/pulse/default.pa 

load-module module-native-protocol-tcp

既にPulseAudioが起動している場合があるので、一度終了させます。

$ pacmd

Welcome to PulseAudio 12.2! Use "help" for usage information.

>>> exit

# PulseAudioの再起動をします。

$ pulseaudio -D

PulseAudioの設定テストを行う場合は-Dなし（フォアグラウンド実行）すると良いです。Crtl-Cで終了できますので、起動＆終了が素早くできて楽です。

クライアント側

クライアント側はMP3などをデコードし、音声をサーバーに送る役目を果たします。使い方は環境変数PULSE_SERVERを指定して再生するだけです。

$ export PULSE_SERVER=192.168.1.10    # ★★PulseAudioサーバー側のIPアドレス★★
$ mplayer --no-video test.mp3

本当はmodule-zeroconf-discoverを正しく設定すれば環境変数をいちいち設定する必要はなく、PulseAudioの設定GUIから出力先の一つとして選択できるようになるはずです。が、どうも私の環境だとうまく動いてくれなくて挫折しました……。

glibcのスレッドとスタック

目次: C言語とlibc

誰も興味ないglibcの話シリーズ、スレッドのスタックはどうやって確保するのか？を追います。

ソースコードはglibc-2.35を見ています。pthread_create() の実体はいくつかありますが、2.34以降ならば __pthread_create_2_1() という関数が実体です。

// glibc/nptl/pthread_create.c

versioned_symbol (libc, __pthread_create_2_1, pthread_create, GLIBC_2_34);
libc_hidden_ver (__pthread_create_2_1, __pthread_create)
#ifndef SHARED
strong_alias (__pthread_create_2_1, __pthread_create)
#endif

主要な関数としては、スタックを確保するallocate_stack() とclone() を呼ぶcreate_thread() です。スレッド属性も見てますが、今回は特に使わないので無視します。

__pthread_create_2_1
  allocate_stack
    get_cached_stack
  create_thread

スレッドのスタックは2通りの確保方法があります。1つはキャッシュ、もう1つはmmap() です。

// glibc/nptl/pthread_create.c

static int
allocate_stack (const struct pthread_attr *attr, struct pthread **pdp,
		void **stack, size_t *stacksize)
{

  //...

      /* Try to get a stack from the cache.  */
      reqsize = size;
      pd = get_cached_stack (&size, &mem);
      if (pd == NULL)    //★★キャッシュがなければこのif文が成立してmmapでメモリ確保★★
	{
	  /* If a guard page is required, avoid committing memory by first
	     allocate with PROT_NONE and then reserve with required permission
	     excluding the guard page.  */
	  mem = __mmap (NULL, size, (guardsize == 0) ? prot : PROT_NONE,
			MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0);

  //...

    retval = create_thread (pd, iattr, &stopped_start, stackaddr,
			    stacksize, &thread_ran);

  //...

このget_cached_stack() がNULLを返す＝失敗＝キャッシュからスタックを確保できなかった、という意味です。確保できない場合はmmap() を呼んでカーネルから匿名ページを確保し、スタック領域として使います。

キャッシュに追加する人は誰？

キャッシュからスタックを確保できる場合は何か？というと、既に終了したスレッドのスタック領域がキャッシュにある場合です。スレッドの回収pthread_join() が終わった後のスレッドのスタックにアクセスしてはいけません。つまり誰もアクセスしない領域です。

スタック領域をカーネルに返しても良いですが、カーネルからメモリを確保したり解放するのは一般的に遅い処理のため、別のスレッドのスタックとして再利用してカーネルからのメモリ確保＆解放の回数を減らし、効率を上げる仕組みと思われます。

まずは読み出す側であるget_cached_stack() 関数のコードから見ます。ちなみにコード内に頻出するtcbという単語はThread Controll Blockの略だそうです。

// glibc/nptl/allocatestack.c

static struct pthread *
get_cached_stack (size_t *sizep, void **memp)
{
  size_t size = *sizep;
  struct pthread *result = NULL;
  list_t *entry;

  lll_lock (GL (dl_stack_cache_lock), LLL_PRIVATE);

  /* Search the cache for a matching entry.  We search for the
     smallest stack which has at least the required size.  Note that
     in normal situations the size of all allocated stacks is the
     same.  As the very least there are only a few different sizes.
     Therefore this loop will exit early most of the time with an
     exact match.  */
  list_for_each (entry, &GL (dl_stack_cache))    //★★キャッシュのリストを全部調べる★★
    {
      struct pthread *curr;

      curr = list_entry (entry, struct pthread, list);
      if (__nptl_stack_in_use (curr) && curr->stackblock_size >= size)
	{
	  if (curr->stackblock_size == size)    //★★一致するサイズのスタックがあれば使う★★
	    {
	      result = curr;
	      break;
	    }

	  if (result == NULL
	      || result->stackblock_size > curr->stackblock_size)
	    result = curr;
	}
    }

  //...

カギを握るのはdl_stack_cacheというスタック領域をキャッシュするリストのようです。先程も言いましたが、このリストに要素が追加されるタイミングの1つはpthread_join() です。pthread_join() からコードを追います。

// glibc/nptl/pthread_join.c

int
___pthread_join (pthread_t threadid, void **thread_return)    //★★pthread_join() の実体★★
{
  return __pthread_clockjoin_ex (threadid, thread_return, 0 /* Ignored */,
				 NULL, true);
}
versioned_symbol (libc, ___pthread_join, pthread_join, GLIBC_2_34);


// glibc/nptl/pthread_join_common.c

int
__pthread_clockjoin_ex (pthread_t threadid, void **thread_return,
                        clockid_t clockid,
                        const struct __timespec64 *abstime, bool block)
{
  struct pthread *pd = (struct pthread *) threadid;

  //...

  void *pd_result = pd->result;
  if (__glibc_likely (result == 0))
    {
      /* We mark the thread as terminated and as joined.  */
      pd->tid = -1;

      /* Store the return value if the caller is interested.  */
      if (thread_return != NULL)
	*thread_return = pd_result;

      /* Free the TCB.  */
      __nptl_free_tcb (pd);    //★★これ★★
    }
  else
    pd->joinid = NULL;

  //...


// glibc/nptl/nptl_free_tcb.c

void
__nptl_free_tcb (struct pthread *pd)
{
  /* The thread is exiting now.  */
  if (atomic_bit_test_set (&pd->cancelhandling, TERMINATED_BIT) == 0)
    {
      /* Free TPP data.  */
      if (pd->tpp != NULL)    //★余談TPP = Thread Priority Protectだそうです★
        {
          struct priority_protection_data *tpp = pd->tpp;

          pd->tpp = NULL;
          free (tpp);
        }

      /* Queue the stack memory block for reuse and exit the process.  The
         kernel will signal via writing to the address returned by
         QUEUE-STACK when the stack is available.  */
      __nptl_deallocate_stack (pd);    //★★これ★★
    }
}
libc_hidden_def (__nptl_free_tcb)


// glibc/nptl/nptl-stack.c

void
__nptl_deallocate_stack (struct pthread *pd)
{
  lll_lock (GL (dl_stack_cache_lock), LLL_PRIVATE);

  /* Remove the thread from the list of threads with user defined
     stacks.  */
  __nptl_stack_list_del (&pd->list);

  /* Not much to do.  Just free the mmap()ed memory.  Note that we do
     not reset the 'used' flag in the 'tid' field.  This is done by
     the kernel.  If no thread has been created yet this field is
     still zero.  */
  if (__glibc_likely (! pd->user_stack))
    (void) queue_stack (pd);    //★★これ★★
  else
    /* Free the memory associated with the ELF TLS.  */
    _dl_deallocate_tls (TLS_TPADJ (pd), false);

  lll_unlock (GL (dl_stack_cache_lock), LLL_PRIVATE);
}
libc_hidden_def (__nptl_deallocate_stack)


/* Add a stack frame which is not used anymore to the stack.  Must be
   called with the cache lock held.  */
static inline void
__attribute ((always_inline))
queue_stack (struct pthread *stack)
{
  /* We unconditionally add the stack to the list.  The memory may
     still be in use but it will not be reused until the kernel marks
     the stack as not used anymore.  */
  __nptl_stack_list_add (&stack->list, &GL (dl_stack_cache));  //★★キャッシュのリストに追加★★

  GL (dl_stack_cache_actsize) += stack->stackblock_size;
  if (__glibc_unlikely (GL (dl_stack_cache_actsize)
			> __nptl_stack_cache_maxsize))
    __nptl_free_stacks (__nptl_stack_cache_maxsize);
}

やっとリストdl_stack_cacheにスタック領域を追加している場所まで来ました。もっとあっさりかと思いましたが、意外と呼び出しが深かったです……。

ほとんど見かけないSI接頭辞デカ（da）

何かの量を表すときは数字＋単位（例: 100m）で表します。余りにも桁が多くなり見づらい場合は適切な接頭辞を付けて数字の桁を減らして表すことが多いです（例: 100000m → 100km）。接頭辞はSI（国際単位系）で定義されており、1/1000を表すミリ（m）や1000倍を表すキロ（k）などがあります。これらは良く見かける接頭辞だと思います。

しかしSI接頭辞として定義されているものの、あまり使われない接頭辞もあります。顕著な物はデシ（d）、ヘクト（h）やデカ（da）辺りでしょう。デシとヘクトは少ないながらも見かけますが、デカは使われているところを見たことがありません。

ルールとしてはSI単位であれば、どのSI接頭辞を付けても間違いではない（ヘクトメートルhmも正しい）ですが、非SI単位はSI接頭辞を付けてはいけない場合があります。良く見かける組み合わせを表にしてみました。

各単位の簡単な解説です。

• m: メートル、長さのSI基本単位
• g: グラム、質量のSI基本単位（正確にはkgがSI基本単位）
• Pa: パスカル、圧力のSI組立単位
• Hz: ヘルツ、周波数のSI組立単位
• B: ベル、比を表す単位
• L: リットル、体積の非SI単位、1000cm^3
• a: アール、面積の非SI単位（aは廃止され、haのみが残っている）、100m^2

デカを良く使う単位があれば、是非お目に掛かりたいところです……。