GeoGuessr World Cup 2024 観戦旅行記

この記事は mstdn.maud.io Advent Calendar 2024 14 日目の記事です。昨日は localmin さんの にわかskebファン でした。

こんにちは、sh-mug です。末代鯖三年目になります。私ごとですが、先日 VRChat をやってみたところ、30 分くらいでめちゃくちゃに酔いました。みなさん酔いにどう対処しているのか気になっています。それはそうと、よろしくお願いします～。

GeoGuessr はいいぞ

さて、「みんなの『すき』を自由に書き連ねて発信してください」ということで、GeoGuessr について書いてみようと思います。12/5 の記事とネタ被ってすみません！！（あと、おつよんさん、ぜひ対戦しましょう！）

あわせてこちらの記事もお読みください

GeoGuessr はリリースされた 2013 年から何度か流行の波が来ているので、長年コンピュータのオタクをされている皆様におかれましては、一度は見かけたことのある方も多いのではないでしょうか。

そんな息の長い GeoGuessr ですが、攻略情報（いわゆる「メタ」）の発展や、競技シーンの活発化など、数年前には想像もできなかったような進化を遂げており、いま非常に盛り上がっています🔥🔥

特に、今年 9 月にスウェーデン・ストックホルムで開催された GeoGuessr World Cup 2024 はそんな GeoGuessr の盛り上がりを凝縮したような大会でした。世界中の選手が圧倒的な技量をぶつけ合うなか、特に決勝戦は試合運びも含め非常に見応えがあり、個人的には過去最高の一戦でした。

The Greatest GeoGuessr Game Of All time - Grand Finals 24

実はこの大会、私も現地に行って観戦してきました。今回はその旅行の思い出を、写真とともに振り返りたいと思います。

旅行記

2024-03: 旅行前

何気なく Twitter（旧 X）を見ていると、GeoGuessr World Cup 2024 の告知が流れてきました。なんと、早くにチケットを購入するとチケットが 4 割引で 40 ユーロも安いとのこと。なんてお得なんだ！ と思い、0.5 秒くらい熟考したあとに購入しました。

買っちゃったからにはもう...ネ...

冷静に考えると、チケットが 40 ユーロ安くなったところで、ヨーロッパと往復するだけで 20 万円近くするんだよな……。

ちなみに、一人旅で海外に行くのは初めてです。せっかく高い航空券を買ってヨーロッパに行くならということで、大会のあるストックホルム以外の都市もめぐることにしました。旅行の日程は 9/10 から 9/15 までの 6 日間で、ミラノ → チューリッヒ → コペンハーゲン → ストックホルムというルートで旅行してきました。

知人に「ミラノからストックホルムに行くよ！」という話をしたら、「めっちゃ離れてるけど地図確認した？」と心配されました。はい、私は GeoGuessr プレイヤーなので毎日地図を見ています。

2024-09-10 (Tue): ミラノ（イタリア）

ミラノ中央駅

朝 9 時ごろ、ミラノ中央駅に到着しました。この写真を撮っていると知らないおじさんが近付いてきたので、白いリンゴの周りをぐるぐる走って逃げていました。こわいね。

そうこうしているうちに、Anu さんと合流しました。Anu さんはミラノに住んでいる、仲のいい GeoGuessr プレイヤーです。ミラノとの時差は 8 時間ありますが、日本の生活習慣崩壊オタクと、ミラノの正常なオタクで、ちょうど遊ぶ時間が一緒になるってワケですね。

Anu さんには、今日 1 日ミラノを案内してもらえることになっています。やったー！

Anu さんとエンカ

クロワッサンとコーヒー

ややお腹が空いていると話すと、スターバックスに連れてきてくれました。スターバックスと言っても、リザーブロースタリーというちょっと特別な店舗で、焙煎とか色々違うらしいです。

スタバではマグカップを買って、クロワッサンとコーヒーをいただきました。パンは近くの有名なパン屋さんとのコラボだそうです。美味しかったです。

ドゥオーモ広場

近くのドゥオーモ広場に来ました。ミラノで一番有名な観光地です。ハトが尋常じゃない数たむろしていました。Anu 情報によると、観光客がエサをやるせいで繁殖しているそうです。

ヴィットーリオ・エマヌエーレ2世のガッレリア

すぐ隣の「ヴィットーリオ・エマヌエーレ2世のガッレリア」に来ました。名前なげえ。ここは高級ブランドの店が並ぶアーケード街です。

Anu 情報によれば、クリスマスシーズンになると、アーケードの中心にある巨大クリスマスツリーの入札を巡って有名ブランドが競り合うらしいです。見てみたかったなあ。

ミラノ盛り合わせ

歩いているときに見つけた、イタリアのナンバープレート（県コード MI 付き）、ミラノの市外局番 02、イタリアの特徴である黒い標識裏、ドメイン .it の GeoGuessr メタ盛り合わせです。この写真すごくないですか？？

ちなみに、ナンバープレートに県コードを入れるかどうかは任意らしく、ミラノの車（特に自動車）は入れないことが多いそうです。ミラノを含むイタリア北部は比較的裕福なため、ナンバープレートから地域がわかると車を狙われるリスクが高まるらしいです。世知辛い。

イタリアの横断歩道標識

みんな大好き、イタリアの横断歩道標識もありました。イタリアの歩行者マークは手足も丸っこくてかわいいね。

そんなこんなで色々巡りつつ、夕食までの時間をつぶすために近代美術館に入りました。Anu さんに解説してもらいながら展示を見て回ったのですが、ここがすごく面白かったので、いくつか印象に残っている作品を紹介します。

『空間における連続性の唯一の形態』

これは未来派という芸術運動のなかで、1910 年代に作られた彫刻です。未来派の作品は、動きや速度感を表現することに特徴があるそうです（違ったらすみません）。勢いがありますね。

謎

これはかわいい感じの……なんだっけ？

Dance First, Think Later

Dance First, Think Later. いい標語ですね。

ミラノ風カツレツ

最後に、予約してもらったレストランでイタリア料理をいただきました。写真はミラノ名物のカツレツです。写真にはないんですが、パスタも絶品でした。もうここに住みたい。

夕食の後は、ミラノ中央駅で Anu さんと別れ、ホテルに戻りました。すごく楽しい 1 日でした。明日はチューリッヒに向かいます。

ボラード（画面左側）

ホテルでニュースを見ていたら、ボラードが出てきました。「ボラードを現地で見る」実績を解除です（それでええんか）

2024-09-11 (Wed): ミラノ → チューリッヒ（スイス）→ コペンハーゲン（デンマーク）

ミラノ中央駅

朝 8 時すぎの列車に乗って、チューリッヒに向かいます。1 人旅になると寂しいね。

カプチーノ

車内販売でカプチーノをいただきました。さすが国際列車、カップにも多言語表記です。

完全に余談ですが、今回の旅行で現金を使ったのはここだけでした。あとは全部クレジットカードのタッチ決済です。旅行客としてはめちゃくちゃ便利でよかったです。

車窓

残念ながら、この日の天気はあいにくの曇り模様で、期待していたアルプス山脈の景色はほとんど見えませんでした。でも、雨の中の景色もまた一興です。とはいえ、いつか機会があれば晴れた日にリベンジしたい。

ちなみにジオゲプレイヤー向け情報ですが、湖畔の線路と道路が並走する区間でスイスのボラードを観察することができます。ぜひ乗車して探してみてください。

チューリッヒの街並み

チューリッヒは小雨の似合う街かもしれません。ミラノとはまた違った雰囲気で、ここもまたいいですね。それはそうと、30 ℃ だった昨日のミラノとは打って変わって、チューリッヒは 10 ℃ 前後でめちゃくちゃ寒かったです。

スイスの横断歩行標識

スイスの標識といえば 7 本線の横断歩道標識ですね。かなり探し回って見つけました。

"I WANT $2,000,000.00"

刃物屋の壁に 200 万ドル欲しい！と落書きしてあった。俺も 200 万ドル欲しい。

この日は飛行機でコペンハーゲンに移動して終了です。

2024-09-12 (Thu): コペンハーゲン→夜行列車

デンマークの横断歩道標識

おはようございます。これはコペンハーゲン中央駅前の横断歩道標識です。反射板タイプのノーマルな横断歩道標識を探していましたが、ライト内蔵タイプしか見つかりませんでした。

人魚姫の像

「世界三大がっかり」と言われがちな人魚姫の像。でも、大量の観光客に囲まれているおかげか、何だか立派な像に見えます。

デンマークの標識

個人的には、人魚姫像近くの駐車場にシェブロンと案内標識があって激アツでした。郊外に行かないと見られないと思ってた。ここ、コペンハーゲンの観光スポットです！！

コペンハーゲンの街並み、奥にラウンドタワーを望む

まじめな感想を書くと、コペンハーゲンは景色の色合いというか、雰囲気がとても素敵な街でした。歴史的な建造物も多く、無限に歩けます（これで脚が破壊されました）。

ラーメン

夕飯は日本料理屋でラーメンをいただきました。ここだけの話、自分は海外でどんな日本料理が作られているのか興味があります。異文化圏の方が日本料理を解釈して、ローカライズされた味付けの料理に落とし込むんですよ。どんな料理ができるか気になりませんか？

このラーメンも、メンマの代わりにニンジンが載っていて、愛しいですね。味は、その………勉強になりました。

ストックホルム行きの夜行列車

今晩のお宿は、最終目的地、ストックホルム行きの夜行列車です。かっけ〜

スウェーデン国鉄の検索画面

完全に雑談ですが、「コペンハーゲン」は英語 (Copenhagen)、デンマーク語 (København)、スウェーデン語 (Köpenhamn) で全部綴りが違うんですよね。これを知らずに列車の予約に苦労しました。なんで綴りが全部こんなに違うんだ。

2024-09-13 (Fri, World Cup 前日): ストックホルム（スウェーデン）

おはようございます。朝 6 時です。早起きして車窓を楽しむぞと意気込んでいたはずが、目が覚めたらストックホルム中央駅に到着していました。

赤と黄色のスウェーデン標識

駅前には赤黄の標識がたくさんあって、いよいよスウェーデンに来たんだなという気持ちになります。今更ながら、ストリートビューでしか見たことのない標識が目の前に存在しているのが不思議です。

https://www.sj.se/en/about-the-journey/food-and-drinks/food-on-sj-night-train を翻訳して引用

とりあえず朝食を食べに行きます。自分が乗ったストックホルム〜マルメ線の場合、近くのホテルで朝食ビュッフェを食べられるそうですが、本当かな。この Web ページ以外に情報がないんだけど……。あと翻訳もなんか変だし……。

朝食会場 (Scandic Continental)

本当でした。最高。ここまでずっと物価が狂っていたので、無料の朝食は本当にありがたく感じ〼。モリモリ食べ〼。

Odenplan

おでんプラン🍢

krämbulle とリンゴジュース

スウェーデンの伝統菓子、セムラで有名なパン屋にきました。セムラといえば、そう、ブルーアーカイブのイベント『-ive aLIVE!』に出てくるスイーツですね！！！（というかセムラって実在するんですね）

セムラは春のお菓子ということで、残念ながら 9 月には売っておらず、その代わりに krämbulle というクリームパンをいただきました。美味しい。この直後に蜂に襲われました。

ミートボール

食べ物の話 4 連続ですみません。ランチはスウェーデン料理、ミートボールをいただきました。例えが下手くそで申し訳ないんですが、小さいハンバーグみたいで美味しかったです。

このレストランから、予選に参加していた選手（sp4ghet さん、しいなさん）と、日本からの World Cup 観戦勢に合流しました。実はこのレストランも、ほかの観戦勢の方に予約していただいた場所です。ありがとうございます！

他のみんなは 9/11, 12 の予選も観戦・参加していたので、その時の話を聞いたりしていました。試合のあのラウンドの guess はどういうことを考えていたとか、そういう裏話がいっぱい出てきて面白かったです。

Hop-on Hop-off Boat

他の方の提案で、ボートでストックホルムの街を回りました。これはかなりいい体験でした。

GeoGuessr 本社（画面中央）

あのガラス張りの建物に GeoGuessr 本社があるそうです。選手のお二人はアジア予選の際に訪問したことがあるとか。いいなあ。

GeoGuessr Community Meet-Up

夜は、World Cup の前夜祭的なイベントがありました。有名配信者や、この大会に招待された選手がそこら中を歩いており、すごい空間でした。rainbolt って実在したんだ……。

会場の Duels コーナー

ちなみに会場の一角に Duels コーナーが用意されていたのですが、ここの人口密度が一番高かったです。左奥の席に Kodiak（ドイツ代表）っぽい人が参戦してました。

2024-09-14 (Sat, World Cup 当日): スウェーデン・ストックホルム

この日は、昼から観戦勢の 4 人でスカンセンという屋外博物館に来ました。スウェーデンっぽい建築のエリアと、動物園のエリアで半々くらいです。

ホッキョクギツネの分布

動物園エリアでは、北欧の動物が飼われていました。看板に分布図が描いてあって、plonk it のあれじゃん！！と盛り上がってました。arctic fox meta、いつか使える日は来るんでしょうか。

https://images.squarespace-cdn.com/content/v1/60f6054f4e76b03092956de8/0d1c7ac1-9425-4106-8f79-432dc0dacded/fjall.png?format=1500w
参考画像：plonk it のあれ（https://www.plonkit.net/sweden より引用）

ちなみに柵の中にキツネはいませんでした。見たかったね……😢

スウェーデンの横断歩道標識

あとは横断歩道の標識を再現したりして、はしゃいでました。

GeoGuessr World Cup 2024

World Cup 入場ゲート

ついに今回の旅の目的地、GeoGuessr World Cup 2024 の会場に来ました！ といっても、試合の内容については YouTube で見られるのと、自分の浅い知識であれこれ書くとマサカリが飛んできそうなので、あまり触れません。会場の雰囲気などを中心に書こうと思います。

ストックホルム市庁舎内観

今年の会場はストックホルム市庁舎です。ノーベル賞の晩餐会とかを行う格式高い建物なのですが、こんなゲームの大会に使っちゃっていいんだ。

ホールの中の空間はかなりうまく使われていて、たとえばホール後方に 1 階と 2 階をつなぐ階段があるのですが、選手は登場時にここを降りてくるようになっていて、かなり盛り上がる演出になっていました。（文字で書くとあんまり伝わらないなあ……）

とにかく、会場の一体感や声援の熱気、生でこの試合を見ているんだという興奮は、やはり会場でしか味わえないなと感じました。ここまで見にきて本当によかったです。

ポーランドのリージョンゲス情報を教えてくれる二人組

会場では応援用の手旗が配られていたのですが、途中から大喜利大会になっていました。大喜利連携プレーも発生していてアツかったです。

The Greatest GeoGuessr Game Of All time - Grand Finals 24

すみません、やっぱり決勝だけちょっとだけ紹介させてください。決勝は、膨大な知識量に裏打ちされた圧倒的ピンポイント力のフランス代表 Blinky 選手と、即 guess という超攻撃的なプレイスタイルが武器のアメリカ代表 MK 選手（MK の平均 guess time は 20 秒で、Blinky の 40 秒の半分）の対決でした。ある意味で対極的な 2 人が繰り広げた試合は、これ以上ないほどの緊張感と興奮の連続でした。しかし対極とはいえさすが World Cup 決勝、どちらの選手も guess の精度はとんでもなくて、国当てとか州当てというレベルではなく、道単位で寄せて勝つラウンドもお互いありました。試合運びもまた手に汗握る展開で、これが決勝の面白さの 7 割くらいを担っているのですが、これ以上のネタバレを回避しつつ面白さを伝える文章は自分には書けないので、ここで筆を置きます。

ぜひ決勝だけでも観ていただきたいですが、とはいえ 56 分あるから勧めづらいんだよなー。でもフルで観る方が多分面白い……。心がふたつある～（強いて一部分を選ぶとしたら、12:30～14:30 あたりの Blinky が強すぎて面白いのでオススメです）

大会終了後の市庁舎

大会終了後も試合の興奮を忘れられず、ホテルに戻るまでずっと試合の感想を話していました。

2024-09-15 (Sun): 帰国日

あっというまに帰国日になってしまいました。寂しい。

GeoGuessr World Cup 2023 会場周辺

朝早く目が覚めてしまったので、なんとなく去年の World Cup 会場を見に来ました。来年はどこでやるんでしょうか。楽しみです。

お土産の帽子

アバター

会場の物販で買った、GeoGuessr アバターとお揃いの帽子をかぶって帰りました。旅行はこれで終わりです。

おわりに

や〜〜楽しかった。間違いなく一生の思い出です。ちなみに、来年の World Cup 出場権を争う戦いはすでに始まっていて、日本代表として 4 人の選手が参加しています。今後の活躍を楽しみにしています！

明日は、ぬぬ299 さんの『VRChat末期中毒患者が、知識ゼロから1年で英語が話せるようになった話』です。お楽しみに！

blog.numemo.com

Python 3.13 から「兆」が 10 の 6 乗になっている

この記事は 2024 TSG Advent Calendar 3日目の記事です。昨日の記事は @__dAi00 さんの記事 AivisSpeechを使ったDiscordボットの作成　①AivisSpeechをGoogle Cloud Runにデプロイする でした。12/5 公開予定の続編も楽しみです。

今回は、初日に公開した以下の記事の副産物です。

import unicodedata

# Python 3.12 まで 1000000000000.0
# Python 3.13 から 1000000.0
print(unicodedata.numeric("å…†"))

大変だ。Python 3.13 から「5000 兆円」が 50 億円になってしまう（？）

unicodedata.numeric メソッドと Unicode

例によって Unicode が関係してきます。前編でも触れたとおり、Unicode はそれぞれの文字がどんな性質を持つのかを「Unicode 文字データベース (UCD)」1 に記録しています。データベースには「絵文字かどうか (Emoji)」や「大文字かどうか (Uppercase)」といった属性が文字ごとに記録されています。

今回の記事で鍵になる情報は Numeric_Value プロパティ2 です。このプロパティは、文字がどういう数を表しているかを示したものです。Python の unicodedata.numeric メソッドは、文字データベースに Numeric_Value プロパティの登録があった場合にその値を返します3。

漢字の Numeric_Value を決めるのは、Unicode の CJK 統合漢字の性質を管理する Unihan データベースの kPrimaryNumeric プロパティです。ひとつの漢字に複数の kPrimaryNumeric が登録されている場合、Numeric_Value には最初の値が採用されます4。

kPrimaryNumeric

... If an ideograph has more than one numeric value, the first one is to be considered the most common one, and that first value is used for the Numeric_Value property of the ideograph.

なぜ変わったのか？

Python 3.13 から unicodedata.numeric("兆") の結果が変わったのは、Unicode 15.1 で「兆」(U+5146) の kPrimaryNumeric が変更されたためです。参考までに、Unicode 15.05 と Unicode 15.16 での Unihan データベースで「兆」の扱いを掲載しておきます。

バージョン kPrimaryNumeric Numeric_Value
15.0 1000000000000 1000000000000
15.1 1000000 1000000000000 1000000

106 が新しく追加されたのは、「兆」を 106 として扱う中国やベトナムなどのでの慣例がもとになっています7。なお、中国では現在でも SI 接頭語の「メガ」を表す漢字として使われているようです8。

これは日本における 1012 を表す「兆」の用例とは衝突しますが、こういった場合は中国本土における中国語の用例が優先される傾向があるようです9。おそらく中国語での用例が優先された結果、「兆」の Numeric_Value が 106 に上書きされたと考えられます。

  1. Unicode® Standard Annex #44 - Unicode Character Database、参照日: 2024-11-17↩
  2. Unicode Character Database - Numeric_Value、参照日: 2024-12-02↩
  3. unicodedata --- Unicode Database、参照日: 2024-11-23↩
  4. Unicode® Standard Annex #38 - Unicode Han Database (Unihan)、参照日: 2024-11-23↩
  5. DerivedNumericValues-15.0.0.txt、参照日: 2024-11-24↩
  6. DerivedNumericValues-15.1.0.txt、参照日: 2024-11-24↩
  7. L2/22-223: Proposed Updates and Expansions of Unihan Numeric Fields、参照日: 2024-11-17↩
  8. 国务院关于在我国统一实行法定计量单位的命令、参照日: 2024-12-02↩
  9. Twitter、参照日: 2024-11-24↩

Python の isnumeric() の謎を追う："兆" は True、"垓" は False？

この記事は 2024 TSG Advent Calendar 初日の記事です。

…………🤔❓

Python の数値文字列判定ロジックを探る

str.isnumeric() メソッドとは？

Python の str.isnumeric() メソッドは、文字列内のすべての文字が数値を表すものであれば True を、そうでなければ False を返します。*1 まず、このメソッドの基本的な動作を見てみましょう。

# Python の isnumeric() の動作例
print("123".isnumeric())   # True; 1, 2, 3 は数字
print("123a".isnumeric())  # False; a は数字ではない
print("五千万".isnumeric()) # True; 五、千、万 は数値

漢数字にも対応しており、一見よさそうに見えます。ところが……

print("å…†".isnumeric()) # True
print("åž“".isnumeric()) # False

「兆」と「垓」はどちらも漢数字に使われる文字なのに、なぜ Python の str.isnumeric() は異なる結果を返すのでしょうか？

Python と Unicode 文字データベース

Python の文字列メソッド str.isnumeric() は、内部的に Unicode の情報を活用しています。Unicode とは、世界中の文字を一元管理するための国際的な規格で、それぞれの文字がどんな性質を持つのかを「Unicode 文字データベース (UCD)」1 という形で記録しています。データベースには「絵文字かどうか (Emoji)」や「大文字かどうか (Uppercase)」といった属性が文字ごとに記録されています。

その中で、この記事で鍵になる情報は Numeric_Type プロパティ です。このプロパティは、文字が「数値」として扱われるかを示したもので、Python の str.isnumeric() もこの情報を元に判断を行っています。

Numeric_Type プロパティには以下の 4 種類があります。str.isnumeric() の正式な仕様2 には、文字がこのうち Decimal, Digit, Numeric のいずれかである場合に True を返す、というふうに定めてあります。

Numeric_Type 説明 例
Decimal 十進法 (0～9) で使われる基本的な数字 U+0030～U+0039（アラビア数字 "0"～"9"）
U+0660～U+0669（アラビア語の数字）
Digit 数字として機能するが、十進法の桁として直接使用されない特殊な数字 U+2070（上付きゼロ "⁰"）
U+2460（丸付き数字 "①"）
Numeric それ以外の数値を表す文字。整数や分数、負の数など幅広い数値が含まれる U+2155（1/5の分数 "⅕"）
U+4E00（漢数字 "一"）
None 上記に該当しない文字 U+0041（ラテン文字 "A"）
U+3042（ひらがな "あ"）

実際に数詞の Numeric_Type を見てみる

では、これをふまえて、「兆」「垓」を含む日本語の数詞の Numeric_Type をまとめてデータベース3 で確認してみましょう。

文字 Unicode Numeric_Type str.isnumeric()
万 U+4E07 Numeric True
å„„ U+5104 Numeric True
å…† U+5146 Numeric True
京 U+4EAC Numeric True
åž“ U+5793 None False
𥝱 U+25771 None False
ç©£ U+7A63 None False
溝 U+6E9D None False
æ¾— U+6F97 None False
æ­£ U+6B63 None False
載 U+8F09 None False
極 U+6975 None False

すると確かに、「兆」は Numeric_Type=Numeric に分類されている一方、「垓」は分類されていないことがわかります。これが、Python の str.isnumeric() メソッドが「兆」と「垓」で異なる結果を返すことへの直接的な理由です！

……しかしながら、上の表を見ていると、新たに一つの疑問が沸き上がってきます。なぜ、Unicode は「垓」以上の数詞に Numeric_Type を割り当てていないのでしょうか？この謎を解くため、Unicode の数詞の扱いについてもう少し掘り下げていきます。

Coffee break ☕ 「京」の扱いが変わった？ すこし面白いのは「京」の扱いです。「京」(U+4EAC) は、Unicode 15.1 で Numeric_Type が None から Numeric に変更されました。この変更が Python 3.13 から取り入れられたため4、これ以降のバージョンで "京".isnumeric() が True を返すようになりました。 
# Python 3.12 以前なら False
# Python 3.13 以降なら True
print("京".isnumeric())

「京」と「垓」を分けた Unicode の判断を探る

現行の Unicode は「京」までの数詞に Numeric_Type を付与しているのにも関わらず、「垓」以上の数詞には付与していません。この線引きは、どのような基準で決まったのでしょうか？ それを知るためにも、まずは Unicode における漢字と Numeric_Type の関係を知っておく必要があります。

漢字の Numeric_Type を決める仕組み

Unicode の漢字（CJK 統合漢字）に関する情報は、UCD とは別の Unicode Han Database (Unihan)5 というデータベースに収録されています。このデータベースには、各漢字の読みや意味、部首だけでなく、数値に関する情報も格納されています。

Unihan には kPrimaryNumeric という項目があり、ここにはその漢字が表す数値（たとえば「万」は104）が定義されています。 ある漢字に kPrimaryNumeric が付与されると、それに対応して UCD で Numeric_Type=Numeric が設定される、つまりその漢字が 「数を表す文字」として扱われる仕組みになっています。

Coffee break ☕ Unihan と Numeric_Type 漢字に Numeric_Type を付与する仕組みは、実際はもう少しいろいろあります。Unihan には kPrimaryNumeric の他にも
  • kAccountingNumeric: 領収書などで使われる「壱」「弐」「参」などの文字
  • kOtherNumeric: 数字として扱うのが一般的でない「幺」「㠪」などの文字

などの数値に関するフィールドがいくつかあり、これらのどれかが設定されている場合に Numeric_Type=Numeric が付与される、という仕組みになっています。

「京」と「垓」の境界線：L2/22-223 提案と Unicode 技術委員会の判断

つい最近の Unicode 15.0（2022 年 9 月制定）まで、「万」「億」「兆」までが Numeric_Type を持つ数詞として扱われ、「京」「垓」以降の数詞は Numeric_Type が付与されていませんでした。

ここでターニングポイントとなるのが、2022 年 10 月に Unicode 技術委員会 (UTC) に提出された L2/22-2236 という提案です。L2/22-223 は、Unihan の数値フィールドに関する様々な修正を提案しています。

特にその中で、「京」以上の数詞（京、垓、𥝱、穣、溝、澗）などの文字 にも日本語で数値としての用例があることから、kPrimaryNumeric プロパティを追加する、すなわち新たに Numeric_Type を付与することを提案しているのです！ 下の表の太字は、実際に L2/22-223 で追加が提案された kPrimaryNumeric の値です。

文字 Unicode kPrimaryNumeric（提案は太字）
å…† U+5146 1012, 106 *2
京 U+4EAC 1016
åž“ U+5793 1020
𥝱 U+25771 1024
ç©£ U+7A63 1028
溝 U+6E9D 1032
æ¾— U+6F97 1036

そして、この L2/22-223 提案をとりまとめた UTC の CJK & Unihan 作業部会も、UTC に対して上表のすべてを受け入れるよう勧告しました7。

しかしながら、最終的な UTC での議論の結果8、「兆」の 106 と「京」の 1016 のみが Unicode 15.1 に追加され、他の数詞への kPrimaryNumeric 付与は見送られることとなりました。この決定により、「京」(U+4EAC) が数値として扱われる最後の文字として認められ、それ以上の数詞（垓、𥝱など）は対象外となってしまいました。

[173-A45] Action Item for John Jenkins, CJK: Apply the adjustments to the kAccountingNumeric, kOtherNumeric, and kPrimaryNumeric properties, based on document L2/22-223, as amended in Section 11 of document L2/22-247, and excluding any property values greater than that for U+4EAC, for Unicode Version 15.1.

結局、なぜ「京」だけが追加されたのか？

「京」までが採用された顛末について、公開資料から読み取れるのはここまでです。しかし、これらの記録を読んでも、具体的に「なぜ『垓』以降が除外されたのか？」という理由は記されていません。

そこで、この疑問を解消するために、Unicode の専門家であり、先ほどの勧告を行った CJK & Unihan 作業部会の議長でもある Ken Lunde 博士に直接問い合わせを行いました。氏の返信によれば、「京」(10000000000000000) より上の数詞が除外された理由は、オーバーフローの懸念にあるとのことです。以下は博士からの返信の引用です：

このような判断が行われた背景には、Unicode が幅広いシステムや環境で採用されていることが影響しています。オーバーフローのリスクを抱える値を Numeric_Type に含めると、数値処理を行う多くの実装に影響を及ぼす可能性がある、という判断がなされたと考えることができます。

実際、64 bit 符号なし整数型が表現できる 0～264 -1（およそ 1.8×1019）の上界は「京」(1016) と「垓」(1020) の間に位置します。さらに、一部のシステムでは数値を倍精度浮動小数点数型で表現しますが、この型で安全に整数を表現できる上限 *3 は約 9×1015 です。この範囲を超える「京」(1016) が Numeric_Type を持つのは、この制約を直接反映したものではないかもしれませんが、それでも比較的小さな値として許容された可能性はあります。

あくまで推測ですが、128 bit 整数や任意精度演算が一般的になるような環境が普及すれば、「垓」以降の数詞にも Numeric_Type が付与される可能性があるかもしれません。たとえば、128 bit 符号なし整数を使えば、およそ 3.4×1038 までの値を安全に表現できます。この範囲なら「澗」(1036) も含めることができます。Unicode における数詞の扱いも変わっていくには、すなわち Python の str.isnumeric() が「垓」以降の数詞を数値として扱うようになるには、さらなる計算機環境の進化を待つ必要があるかもしれません。

まとめ

Python の str.isnumeric() メソッドは、文字列内のすべての文字が「数を表す文字」であるかを判定しますが、"兆" には True、"垓" には False を返します。この理由は、Unicode の Numeric_Type プロパティが「垓」以上の数詞には付与されていないことにありました。

さらにその理由を探ると、「垓」～「澗」に対する Unicode の数値フィールド修正の提案があったものの、オーバーフローのリスクを懸念して「京」までの数詞のみが採用されたことがわかりました。

Unicode のプロパティ設定には文字の意味以上に、技術的制約など多様な観点から仕様が検討されているのです。

謝辞

本記事の執筆にあたり、Ken Lunde 博士から貴重な情報提供をいただきました。特に、Unicode の数値扱いに関する技術的な背景についての理解を深めることができましたことに感謝しています。また、Unicode 議事録のサーベイなどに、幅広く助力していただいた hakatashi 氏にもここに謝意を表します。

▶おまけ

ゴママヨコーナー

気軽に読める記事を目指していたのに、すごくまじめな内容になってしまったので、ゴママヨ*4 コーナーで中和したいと思います。

  • 「垓」以上 ←⁉
  • Numeric_Type プロパティ ←⁉

他に見つけたらぜひ教えてください。

2024 年 12 月 8 日追記

読者から他のゴママヨを教えていただきました。ありがとうございます！

  • 「垓」以降
  • ここまでです
  • hakatashi 氏
  • "åž“".isnumeric()
  • "京".isnumeric()
  • 表す数値
  • with the（英語ゴママヨ）
  • excluded due（英語ゴママヨ）
  • まじめな内容
  1. Unicode® Standard Annex #44 - Unicode Character Database、参照日: 2024-11-17↩
  2. Python documentation - Built-in Types、参照日: 2024-11-17↩
  3. Unicode Character Database - Numeric_Type、参照日: 2024-11-17↩
  4. What's New in Python 3.13 - unicodedata、参照日: 2024-11-17↩
  5. Unicode® Standard Annex #38 - Unicode Han Database (Unihan)、参照日: 2024-11-17↩
  6. L2/22-223: Proposed Updates and Expansions of Unihan Numeric Fields、参照日: 2024-11-17↩
  7. L2/22-247: CJK & Unihan Group Recommendations for UTC #173 Meeting、参照日: 2024-11-17↩
  8. UTC #173 Minutes、参照日: 2024-11-17↩

*1:つまり、文字列全体が数の表現として正しいかとは無関係です。たとえば、"123.45".isnumeric() は False、"兆兆".isnumeric() は True を返します。

*2:中国やベトナムで 106 を「兆」と書く慣習があり、現在でも中国本土で SI 接頭辞 106 を表す文字として「兆」を使うようです。

*3:JavaScript の Number.MAX_SAFE_INTEGER のことだと思ってください。

*4:ある単語の末尾と、それに後続する単語の先頭の発音が一致するような単語の並びのこと。

SystemVerilog の struct packed は Verilator にどうマッピングされるか

この記事は TSG Advent Calendar 2023 2 日目のエントリです。 昨日の記事は Verilator + GoogleTest で SystemVerilog のモジュールを単体テストする - ﾏｸﾞﾏｸﾞ (起動音) でした。

小ネタですが、検索しても出てこなかったのでメモとして残しておきます。 たとえば、以下のような SystemVerilog の struct packed があったとします。

typedef struct packed {
    logic a;
    logic b;
    logic [3:0] c;
} my_struct_t;

SystemVerilog の構造体は定義した順に下位ビットからメンバが並びますが、 C++ の構造体は定義した順に上位ビットからメンバが並びます。

したがって、Verilator で C++ ライブラリに変換するときには、逆順にメンバを並べる必要があります。 以下のようなビットフィールドのメンバが定義された構造体を用いれば、 SystemVerilog の struct packed と同じメモリマッピングになります。

struct my_struct_t {
    uint32_t c : 4;
    uint32_t b : 1;
    uint32_t a : 1;
} __attribute__((packed));

あとは適宜 std::memcpy などを使って、SystemVerilog の struct packed と C++ の構造体の間でデータをコピーすれば OK です。

Verilator + GoogleTest で SystemVerilog のモジュールを単体テストする

この記事は TSG Advent Calendar 2023 初日のエントリです。

Verilog/SystemVerilog で書かれたモジュールをテストする方法として VUnit や cocotb がありますが、 普段から C++ を書いている自分としては、RTL のテストを C++ で完結させたいという欲求があり、C++ で RTL をテストする方法を探していました。

そこで、C++ 用のテストフレームワークである GoogleTest を Verilator と組み合わせて使う方法を試してみました。 これが意外と簡単にできたので紹介します。需要は謎です。

TL;DR

GitHub - sh-mug/verilog-unittest-sample のサンプルコードを見てくれ！

テスト対象のモジュール

テスト対象のモジュールとして、inst に応じて、a と b を演算して rslt に結果を出力する ALU を用意しました。 この ALU が意図した動作をしているかをテストします。

`timescale 1ns / 1ps

module alu (
    input [2:0] inst,
    input [31:0] a,
    input [31:0] b,
    output logic [31:0] rslt
);
  logic [4:0] shamt;
  logic alu_lt;
  logic alu_ltu;
  logic [31:0] alu_add;
  logic [31:0] alu_sll;
  logic [31:0] alu_xor;
  logic [31:0] alu_srl;
  logic [31:0] alu_or;
  logic [31:0] alu_and;

  always_comb begin
    shamt   = b[4:0];

    alu_lt  = $signed(a) < $signed(b);
    alu_ltu = a < b;
    alu_add = a + b;
    alu_sll = a << shamt;
    alu_xor = a ^ b;
    alu_srl = a >> shamt;
    alu_or  = a | b;
    alu_and = a & b;

    case (inst)
      3'b000:  rslt = alu_add;
      3'b001:  rslt = alu_sll;
      3'b010:  rslt = {31'b0, alu_lt};
      3'b011:  rslt = {31'b0, alu_ltu};
      3'b100:  rslt = alu_xor;
      3'b101:  rslt = alu_srl;
      3'b110:  rslt = alu_or;
      3'b111:  rslt = alu_and;
      default: rslt = 0;
    endcase
  end
endmodule : alu

テストコード

テストコードは、GoogleTest の TEST_F マクロを使って書きます。 まず、テストフィクスチャ（テストのセットアップやクリーンアップを行うクラス）を作成し、その中で Verilator とモジュールのシミュレーションを初期化します。以下は、テストフィクスチャと1つのテストケースの例です。

テストフィクスチャ TestAlu

テストクラス TestAlu では、テストケース間で共通の設定を行います。具体的には、テスト用の ValuForTest インスタンスをセットアップし、テスト後にクリーンアップを行っています。

class TestAlu : public ::testing::Test {
   protected:
    TestAlu()
        : engine(seed_gen()), dist_int(INT_MIN, INT_MAX), dist_5bit(0, 31) {}
    ValuForTest *dut;

    std::random_device seed_gen;
    std::mt19937_64 engine;
    std::uniform_int_distribution<int> dist_int;
    std::uniform_int_distribution<unsigned char> dist_5bit;

    int inst;
    int a;
    int b;

    void SetUp() override { dut = new ValuForTest(); }

    void TearDown() override {
        dut->final();
        delete dut;
    }
};

また、演算実行の一連の流れを exec メソッドとして定義するため、Verilator で生成された Valu クラスを継承して ValuForTest クラスを定義しています。

void ValuForTest::exec(const int &_inst, const int &_a, const int &_b) {
    inst = _inst;
    a = _a;
    b = _b;
    eval();
}

テストケース例 TEST_F(TestAlu, ADD)

テストケースの一つとして、 TEST_F(TestAlu, ADD) で inst が ADD 演算の場合のテストを行います。具体的には、N 回ランダムな整数 a と b を生成し、これを SystemVerilog モジュールに与えて計算結果が期待通りかどうかを ASSERT_EQ マクロを使用して検証しています。

const unsigned N = 1000000;

TEST_F(TestAlu, ADD) {
    inst = 0b000;
    for (unsigned i = 0; i < N; ++i) {
        a = dist_int(engine);
        b = dist_int(engine);
        dut->exec(inst, a, b);
        ASSERT_EQ(dut->rslt, a + b);
    }
}

この例では ADD 演算のみを示していますが、他の演算子に対するテストケースも同様の構造で追加できます。これにより、テスト対象の SystemVerilog モジュールが期待通りに動作しているかを確認できます。

テスト実行

SystemVerilog モジュールの単体テストを実行するために、CMake を使用してテストベンチをビルドし、実行結果を確認します。

CMake を使用したテストベンチのビルド

まず、テストベンチのビルドには以下の CMakeLists.txt を使用します。このファイルでは、Verilator と GoogleTest をプロジェクトに取り込み、テスト実行用のバイナリをビルドします。必要な部分を抜き出しています。

cmake_minimum_required(VERSION 3.14)
project(verilog_unittest_sample)

# ... Verilator と GoogleTest の取り込み（省略）

# Test フォルダ内のソースファイルを含むテスト実行用のバイナリを定義
enable_testing()
add_executable(test_all
  test/test_alu.cpp
  test/main.cpp
)
target_link_libraries(
  test_all
  PRIVATE
  GTest::gtest_main
)

# テストバイナリのプロパティを設定
set_target_properties(test_all PROPERTIES
  CXX_STANDARD 17
  CXX_STANDARD_REQUIRED ON
  COMPILE_FLAGS "-Wall -g -fsanitize=address"
  LINK_FLAGS "-fsanitize=address"
)

# GoogleTest によるテストの自動検出
include(GoogleTest)
gtest_discover_tests(test_all)

# Verilate を使用して Verilog モジュールをビルド
verilate(test_all
  INCLUDE_DIRS "src"
  SOURCES
  src/alu.sv
  PREFIX Valu
)

このCMakeLists.txtでは、add_executable でテスト用のバイナリを定義しています。また、Verilate を使用して SystemVerilog モジュールをビルドするために verilate を設定しています。

テストベンチのビルドと実行

以下のコマンドで CMake を使用してプロジェクトをビルドします。

$ cmake -S . -B build -G Ninja
$ ninja -C build

ビルドが完了したら、以下のコマンドでテストを実行します。

$ build/test_all

これにより、GoogleTest がテストを自動的に検出し、SystemVerilog モジュールの単体テストが実行されます。 そうすると、以下のような結果が表示され、ALU の各演算子に対するテストが実行されたことがわかります。

[==========] Running 8 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 8 tests from TestAlu
[ RUN      ] TestAlu.ADD
[       OK ] TestAlu.ADD (337 ms)
[ RUN      ] TestAlu.SLL
[       OK ] TestAlu.SLL (278 ms)
[ RUN      ] TestAlu.SLT
[       OK ] TestAlu.SLT (272 ms)
[ RUN      ] TestAlu.SLTU
[       OK ] TestAlu.SLTU (281 ms)
[ RUN      ] TestAlu.XOR
[       OK ] TestAlu.XOR (267 ms)
[ RUN      ] TestAlu.SRL
[       OK ] TestAlu.SRL (279 ms)
[ RUN      ] TestAlu.OR
[       OK ] TestAlu.OR (260 ms)
[ RUN      ] TestAlu.AND
[       OK ] TestAlu.AND (273 ms)
[----------] 8 tests from TestAlu (2252 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test suite ran. (2252 ms total)
[  PASSED  ] 8 tests.

試しに、ALU の演算結果が期待通りにならないように alu.sv を修正してみます。 たとえば、加算命令実行時に alu_add の代わりに alu_xor を出力するようにしてみます。

-      3'b000:  rslt = alu_add;
+      3'b000:  rslt = alu_xor;

この状態で再度テストを実行すると、以下のように加算命令のテストが失敗することがわかります。

[==========] Running 8 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 8 tests from TestAlu
[ RUN      ] TestAlu.ADD
/home/mug/verilog-unittest-sample/test/test_alu.cpp:49: Failure
Expected equality of these values:
  dut->rslt
    Which is: 481875563
  a + b
    Which is: 549918315

[  FAILED  ] TestAlu.ADD (61 ms)
...（以下略）
[----------] 8 tests from TestAlu (1958 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test suite ran. (1958 ms total)
[  PASSED  ] 7 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] TestAlu.ADD

 1 FAILED TEST

おまけ：GitHub Actions での自動テスト

上で生成したテストバイナリを用いれば、GitHub Actions で自動テストを行うこともできます。記事が長くなってしまったので詳細は省略しますが、hdlc/verilator というありがたいコンテナイメージがあります。このコンテナ上で新しいバージョンの Verilator を利用でき（2023 年 12 月 1 日現在では v5.018）、GitHub Actions で簡単にテストを実行できます。

まとめ

Verilator と GoogleTest を組み合わせて、SystemVerilog のモジュールを単体テストする方法を紹介しました。 GoogleTest のテストフィクスチャを用いることで、RTL の単体テストを簡単に書くことが出来そうです。 ここまでで紹介したサンプルコードは、GitHub - sh-mug/verilog-unittest-sample で公開しています。

現状の方法では単体テストを行うモジュールごとに Verilator でライブラリを生成する必要があるので、これの改善方法を考えていきたいと思います。

RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）解説

AHC022 お疲れ様でした。相対スコア 1,604,106,037,513 点で 1063 人中 48 位でした。長期コンテストで 2 桁順位を取れたのは初めてなので、記念に解法記事を書きます。

ビジュアライザ seed=0

問題概要

ワームホールの入口と出口が N 個ずつありますが、その対応付けは分かっていません。ワームホールの出口周辺の気温情報を頼りに、対応付けを推定してください。ただし、最初に一回だけ出口セルがある空間の温度を自由に設定できます。

atcoder.jp

基本方針

基本的には以下の方針で解き、パラメータの値によって方針を多少変化させました。

  • 配置パート
    • 適当な順序で出口セルに温度 0, P, 2P, \cdots , (N-1)P を割り当て、その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定する
  • 計測パート
    • ワームホールは出力の確信度合いが最も低いものを選ぶ
    • 移動量は予想される出力の分散が最も大きいものを選ぶ
  • 回答パート
    • 全体の尤度が最大になるように (0, 1, ... , N-1) の順列を選択し、回答する

配置パート

基本

まず適当な出口セルの温度を 0 に設定し、この出口セルからマンハッタン距離の近い順に温度 P, 2P, … , (N-1)P を割り当てます。温度を 0 にするセルは、もっとも配置コストが小さくなるように選びます。 P は L, N, S の値から適当に決めます。

その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定します。ボロノイ図のような感じで温度を適当に埋めてから、出口セルの温度だけ固定してガウシアンぼかしを繰り返し適用すると、右のように盤面全体で滑らかな温度勾配を得られます。

左に繰り返しガウシアンぼかしを適用すると、右を得られる

S, N が大きい場合：極端な温度のセルを作る

S, N が大きい場合、基本方針だけでは近い出口セル同士の区別がつかず、正答率が下がってしまいます。その対策として、極端な温度を持つセルを 1, 2 個つくると、各出口セルの位置推定が容易になり、 S が非常に大きいケースの正解率が上昇します。（という理屈が働いていると思うのですが、本当かどうかはわかりません……）

seed=8 (L=30 N=87 S=784) の場合は極端な温度のセルを 2 個用意する

計測パート

前提となる確率計算

ワームホール i に関する観測情報の集合 \mathbf{\theta}_i=(\mathbf{\theta}_{i1},\mathbf{\theta}_{i2},\cdots,\mathbf{\theta}_{im_i}) をもとに、対応する出口が j である確率 P(p_{ij}\mid\theta_i) を計算することができます。ワームホールの入り口と出口の対応がランダムであることを利用すると、ベイズの定理より以下が成り立ちます。

P(p_{ij}\mid\theta_i)=\displaystyle\frac{P(\theta_i\mid p_{ij})}{\sum_{j'=0}^{N-1} P(\theta_i\mid p_{ij'})}

ところで、右辺に登場する P(\theta_i\mid p_{ij}) は計算で求めることができます。ワームホール i の出口が j であると仮定すると、そこから (y,x) だけ移動したセルの位置と、そこで観測できる温度の確率分布が決まります。したがって、各観測情報 \theta_{ik} から P(\theta_{ik}\mid p_{ij}) は計算可能なので、そこから以下が得られます。

P(\theta_i\mid p_{ij})=\displaystyle\prod_{k=1}^{m_i} P(\theta_{ik}\mid p_{ij})

基本

ワームホールの選び方

\max_j P(p_{ij}\mid\theta_i) を、ワームホール i と出口セルとの対応付けの確信度合いとみなします。全部のワームホールで自信を持って回答するため、確信度合いが最も低いワームホール i を都度選択しました。確信度合いの最小値が一定値を超えると計測パートを終了し、回答に移ります。

移動量の選び方

ワームホールを選択した後、観測地点の出口セルからの移動量を決定します。このとき、もっとも出口セルを判別しやすい場所として、観測される温度の予測値の分散が最も大きくなる地点を選択します。

S, N が小さい場合：移動量を制限する

S, N が小さい場合は移動量 (y,x) を制限しても全問正解することができます。計測コストは 1 回あたり 100\times (10+|y|+|x|) かかるため、移動量を制限して計測コストを下げることが可能です。

回答パート

回答パートでは、全体の尤度 \prod_{i=0}^{N-1} P(p_{iE_i}\mid\theta_i) が最大になるような (0, 1, ... , N-1) の順列 (E_0, E_1, ... , E_{N-1}) を選択し、出力しました。この最大化問題は以下のグラフの最小費用流問題に帰着して解くことが可能です。

最小費用流問題に帰着して順列を推定する形にすると、他のワームホールに関する観測情報も加味して出口セルを推定できるのがメリットですが、出口セルの推定を一度に 2 個間違えてしまう可能性があるのが難点です。全体的な正解率は最小費用流を使用したほうが高かったため、採用しました。

提出

以上をすべて実装したのが以下の提出になります。詳細なパラメータや、具体的な計算方法などはこちらを参考にしてください。

atcoder.jp

感想

最初は問題文の読解に手こずり、難しそうな問題だなと思っていたのですが、いざ取り組んでみると各パートで工夫のしがいがあって面白く、ビジュアライザも見映えがあって楽しい問題でした。

長期の AHC に本腰を入れて取り組んだのは（多分）初めてなので、普段よりよい順位を取れてよかったです。観測・回答パートでは統計の知識がかなり役立った感じがあります。一方で、 S, N が大きい場合の配置パートに関しては考察不足でした。どうせ S が大きいと各出口セルの温度は比較的どうでもよくなるのですが、 S, N が小さい場合から大きく方針を変えるのは思い至りませんでした。最後の数日はパラメータ調整ばかりやっていたので、もう少し方針転換について考えてもよかったかもしれません。

SECCON CTF 2022 Quals Writeups

SECCON CTF 2022 Quals にチーム TSG で参加し、this_is_not_lsb と noiseccon (実装パートのみ; アイデアは mikit さんから) の 2 問を解きました。以下はその writeup です。

this_is_not_lsb

Tired of difficult problems? Ok, I give you a simple LSB Padding Oracle problem. Ah, my magic has exploded... Sorry

問題概要

  • N …… 2 つの 512 bit ç´ æ•° p, q の積
  • e=65537
  • flag_length …… flag のビット長
  • c …… 暗号文

上の情報に加えて、任意の暗号文を復号した結果の1014～1023ビット目が 0011111111 かどうかをサーバーから得られる。そこから flag を推測すればよい。

解法

通常の LSB Padding Oracle problem では復号結果の下位 1 bit を得られるが、この問題では代わりに上位 10 bit のパターンが 0011111111 かどうか知ることができる。

以下、平文を m とする。 LSB が与えられる通常の問題と同様に、本問題も Ke c を復号して得られる Km の性質から解ける。 この問題の場合は Km が 0b0011111111<<1014 以上 0b0100000000<<1014 未満かどうか知ることができるので、これを満たすような K の下界を二分探索し、そこから m を計算すればよい。

flag の形式が SECCON{[\x20-\x7e]+} であることを利用して適切に二分探索の探索範囲を絞っておくと、K の値の上界を気にせず探索できる。

SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

▶ソルバー（クリックで展開） gist.github.com

noiseccon

Noise! Noise! Noise!

問題概要

サーバーに scaleX, scaleY の 2 種類の値を渡すと、サーバーはランダムなシードで生成された 2 次元パーリンノイズの中から (offsetX, offsetY) を左上端とした 12.8×12.8 の領域を切り抜き、 256×256 ピクセルへと 20 倍に引き延ばして返す。

なお、offsetX, offsetY は index.js 内で以下のように定義されている。

const offsetX = div(flagInt, scaleX);
const offsetY = div(flagInt, scaleY);

また div は以下の通り実装されている。要するに div(x,y) は浮動小数点演算 x/y の結果から小数点以下を 4 bit、上を 32 bit だけ残して返す関数である。

const div = (x, y) => {
  const p = 4;
  return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
};

ここから flagInt を推測すればよい。

解法

アイデア

パーリンノイズは格子点を基準にテクスチャを生成するため、格子点には何らかの特徴がある。この特徴をもとに、サーバーが返す画像から格子点の位置を復元できれば offsetX, offsetY の小数点以下が分かる。

各オフセットは小数点 4 bit の情報を残しているので、scaleX, scaleY の両方を適切に設定すると 1 枚の画像からフラグ 1 文字分の情報を得られそうである。

実装

1 枚の画像からフラグの i 文字目を得るためには、offsetY, offsetX の小数点以下 4 bit (以下、hi, lo とする) がそれぞれ i 文字目の上位/下位 4 bit を表すようにすればよく、以下のように scaleX, scaleY を設定するとよい。

scaleX = 1 << (8 * (total_length - pad_length - idx) - 4)
scaleY = 1 << (8 * (total_length - pad_length - idx))

index.js の実装より、パーリンノイズの格子点に相当するピクセルの色はすべて #808080 になっているはずである。 (hi, lo) = (0, 0), (0, 1), ... , (15, 15) とそれぞれ仮定を置き、その場合の格子点の推定位置のピクセルの色が #808080 からどれだけ離れているかを残差平方和で表すと、この残差平方和を最小にするような (hi, lo) の組が求めたい情報になっている。

SECCON{p3RLin_W0r1d!}

フラグ 0 文字目を得るためのノイズ画像 (左)、そこから推測した (hi, lo) (右)

▶ソルバー（クリックで展開） gist.github.com