埋め込みバイナリ形式

これは TZF 埋め込みバイナリ形式の簡潔なリファレンスです。対象は、ringsaturn/tzf-dist から各 v2 実装へ境界データを届ける .tzb と .tzm のファイルです。ディスク上のレイアウトと、ファイルを安全に読み取って tzf のタイムゾーン検索結果を再現するための規則を記載します。

この形式は v2 で protobuf を置き換えました。インプレースでのクエリに対応しています。ディレクトリは固定幅のレコードであり、ジオメトリは各階層でバウンディングボックスを持ち、読み手はそのクエリが必要とするバイトだけを読んで応答できます。

このページがこの形式の公開リファレンスです。参照実装は tzf リポジトリの internal/embedbin です。

1. 表記の約束

• マジック：TZFB
• 形式バージョン：1.1（format_major 1、format_minor 1）
• バイト順：すべての固定幅整数はリトルエンディアン
• 座標：符号付き int32、度に 100000 を乗じた値
• 座標の順序：経度、次に緯度
• バウンディングボックスの順序：min_lng, min_lat, max_lng, max_lat
• 点ストリーム内の符号付き値：zigzag エンコード後、符号なし LEB128 エンコード
• LEB128 の値：最小限のエンコード、最大 5 バイト
• セクションのオフセットと固定幅レコード：4 バイト境界に整列
• 最大ファイルサイズ：4 GiB 未満

格納される座標とバウンディングボックスは次の範囲内である必要があります。

longitude: -18000000..18000000
latitude:   -9000000..9000000

2. プロファイル

形式 1.1 は、ヘッダの最初の予約バイト（オフセット 48）を profile として割り当てます。2 つのプロファイルが 1 つのコンテナを共有します。

1.1 より前に書き出されたファイルはこのオフセットに 0 を持つため、形式 1.0 のファイルはすべて遡って有効な E プロファイルのファイルとなります。読み手は未知のプロファイル値を拒否する必要があります。

必須セクションはプロファイルごとに定義されます。

プロファイルをまたぐセクション種別は拒否されます。NAMES、TZDIR、POLYDIR、GRID、FUZZY は両プロファイルでバイト単位で同一であり、これにより .tzb から .tzm への変換ではこれらをそのままコピーできます。

M プロファイルは、それを使用するホスト上で tzf の cmd/tzb2tzm により生成します。出力は M プロファイルをソースからエンコードした場合とバイト単位で同一です。M プロファイルを読み込むのは Go の実装のみで、tzf-rs はこの形式のファイルに対して Error::Profile を返します。

3. 全体のレイアウト

Header                 64 bytes
Section table          section_count * 16 bytes
NAMES                  type 1
TZDIR                  type 2
POLYDIR                type 3
RINGDIR                type 4     E profile
RINGOPS                type 5     E profile
GROUPDIR               type 6     E profile
CHUNKDIR               type 7     E profile
GRID                   type 8     optional
FUZZY                  type 10    optional
FLATPOINTS             type 12    M profile
FLATRINGDIR            type 13    M profile
YSTRIPES               type 14    M profile, optional, not emitted today
POINTS                 type 9     E profile, last
CRC32 footer           4 bytes

書き手はこの順序でセクションを出力し、容量の大きいジオメトリを最後に置きます。読み手はセクションテーブルを使ってセクションを特定し、未知の種別をスキップします。形式 1.0 の読み手が FUZZY セクションを無視できるのはこの仕組みによります。

セクション種別 11（META）は割り当て済みですが予約されています。

3.1 ヘッダ

フラグ：

3.2 セクションテーブル

セクションテーブルはヘッダの直後から始まります。各エントリは 16 バイトです。

既知のセクション種別は一意である必要があります。セクションは範囲内に収まり、ヘッダ、セクションテーブル、フッタ、他のセクションと重なってはなりません。

3.3 フッタ

末尾 4 バイトには、バイト範囲 [0, file_size - 4) に対する IEEE CRC32 が入ります。ファイルは最初のクエリの前に検証する必要があります。デバイスでは、ファイルを信頼できるストレージに配置する時点でこの検証を一度だけ行う運用も可能です。

4. 共通セクション

ディレクトリのインデックスは 0 始まりです。first と count の組は、常に参照先セクション内の連続した範囲を選択します。

4.1 NAMES、種別 1

u32 blob_len
u32 offsets[tz_count + 1]
u8  blob[blob_len]

タイムゾーン名 i は blob[offsets[i] : offsets[i + 1]] です。名前は NUL バイトを含まない空でない UTF-8 文字列です。offsets は単調非減少で、offsets[0] は 0、offsets[tz_count] は blob_len と一致します。タイムゾーンのインデックスは NAMES、TZDIR、GRID、FUZZY で同じ意味を持ちます。

4.2 TZDIR、種別 2

tz_count 個のレコードで、各 24 バイトです。

4.3 POLYDIR、種別 3

24 バイトのレコードです。

最初のリングが外周で、残りは第 1 階層の穴です。この形式は入れ子の穴を表現できません。

4.4 GRID、種別 8（任意）

1° × 1° の密な候補インデックスです。

i16 lng_min
i16 lat_min
u16 lng_cells
u16 lat_cells
u32 cand_count
u32 cells[lng_cells * lat_cells]
u16 candidates[cand_count]

入力座標に対して次のように計算します。

cx = floor(lng) - lng_min
cy = floor(lat) - lat_min
cell_index = cy * lng_cells + cx

範囲外のセルには候補がありません。セルのワードは次のようにエンコードされます。

count  = cells[cell_index] >> 28
offset = cells[cell_index] & 0x0fffffff

候補リストは candidates[offset : offset + count] で、昇順のタイムゾーンインデックスを保持します。リストはセル間で共有される場合があります。グリッドのキーはクエリ領域より 1 セル分外側に及ぶことがあります（lng_min: -181..180、lat_min: -91..90）。上流の浮動小数点インデックスからコピーされる場合があるためです。各セルの候補は最大 15 個、cand_count は 2²⁸ 未満、すべての候補は tz_count 未満です。GRID がない場合、読み手は TZDIR を走査します。

4.5 FUZZY、種別 10（任意）

タイルプレインデックスを、ソート済みのタイル ID 配列 1 つとして格納します。これは、大部分の単一名クエリを point-in-polygon なしで解決する高速パスです。

u8  idx_zoom
u8  agg_zoom               // agg_zoom <= idx_zoom
u16 reserved (0)
u32 tile_count
u32 multi_group_count
u32 multi_value_count
u64 keys[tile_count]       // packed TileID, strictly ascending
u16 values[tile_count]
u16 multi_dir[multi_group_count * 2]   // (first, count) pairs
u16 multi_values[multi_value_count]    // NAMES indices
(zero padding to 4-byte alignment)

キーは uint64(z) << 56 | uint64(x) << 28 | uint64(y) としてパックされます。値のビット 15 が 0 の場合、ビット 0 から 14 は NAMES のインデックスです。ビット 15 が 1 の場合、ビット 0 から 14 は multi_dir へのインデックスであり、複数のタイムゾーンを指すタイルに使用されます。このセクションは 8 バイト境界に整列している必要があり、keys はセクションのオフセット 16 から始まります。

上限値：

2026c データセットでは 87,572 個のタイルを保持し、そのうち 156 個が 2 つのタイムゾーンを指し、エンコード後のサイズは約 880 KB です。FUZZY を出力するエンコーダは、プレインデックスのバージョン、ジオメトリのバージョン、ヘッダの data_version がすべて一致することを検証する必要があります。

5. E プロファイルのジオメトリ

5.1 RINGDIR、種別 4

28 バイトのレコードです。

リングは開いた形式で 3 点以上を含みます。その操作列は閉路を成し、接合点の頂点を共有します。各巡回ペアについて、前の操作のリング順における出口点が、次の操作のリング順における入口点と一致します。格納されるカウントは次の関係を満たします。

ring.point_count = sum(referenced_group.point_count) - ring.op_count

5.2 RINGOPS、種別 5

u32 ワードの配列です。

bit 31:     reversed
bits 0..30: group index into GROUPDIR

このフラグはリング順の走査方向を表し、エンコーダは共有エッジに対してのみ設定します。point-in-polygon の評価はすべてのグループを順方向に走査してかまいません。レイ交差の偶奇はセグメントの集合に依存し、セグメントの順序には依存しないためです。

5.3 GROUPDIR、種別 6

44 バイトのレコードです。

グループは共有エッジか、統合されたインラインの連続区間のいずれかで、どちらも同じ表現を持ちます。2 点以上を保持し、両端点を格納し、内部に連続する重複点を持ちません。単一操作の閉じたリングでは first == last となる場合があります。順方向の操作では入口が first、出口が last で、逆方向の操作ではこれが入れ替わります。

共有エッジの重複排除はこのセクションで表現されます。2 つのタイムゾーンの間の境界はグループとして一度だけ格納され、両方のリングから順方向と逆方向に 1 回ずつ参照されます。

5.4 CHUNKDIR、種別 7

24 バイトのレコードです。

グループのチャンクは連続かつ順序付けられており、そのグループの点を分割します。すべてのグループは 1 つ以上のチャンクを持ち、すべてのチャンクは 1 つ以上の点を持ちます。point_off の値は CHUNKDIR 全体で狭義単調増加であり、チャンクのバイト範囲は次のチャンクの point_off で終わります。最後のチャンクは POINTS の終端で終わります。

チャンクのバウンディングボックスは、チャンク内の連続する点の間のセグメントに加えて、同一グループ内に次のチャンクがある場合はその最後の点から次のチャンクの最初の点までのセグメントを含みます。これにより読み手はチャンクをデコードせずにスキップできます。

デコーダはチャンクのバイト範囲内で正確に point_count 個の点を消費します。最後の緯度 varint の後、カーソルは範囲の終端と一致している必要があります。範囲の境界を越えることや、末尾にバイトが残ることはエラーです。

5.5 POINTS、種別 9

POINTS は、独立してデコード可能なチャンクストリームの連結です。

zigzag-LEB128 absolute_lng
zigzag-LEB128 absolute_lat

repeat point_count - 1 times:
    zigzag-LEB128 delta_lng
    zigzag-LEB128 delta_lat

各チャンクは絶対座標の点から始まるため、チャンクは独立してスキップできます。差分は int32 のオーバーフロー検査付きの加算でデコードします。int32 の値 v に対する zigzag エンコードは uint32((v << 1) ^ (v >> 31)) です。

6. M プロファイルのジオメトリ

M プロファイルはチャンクの仕組みを 2 つのセクションに置き換えます。これによりオープン時のデコードがなくなり、リングのストレージがマップされたファイルを直接参照します。

6.1 FLATPOINTS、種別 12

(int32 lng, int32 lat) ペアのリトルエンディアン配列で、すべてのリングの開いた点列を連結したものです。接合点の重複は展開済みです。ペア数はセクション長を 8 で割った値です。このセクションは 8 バイト境界に整列し、長さは 8 の倍数である必要があります。

6.2 FLATRINGDIR、種別 13

24 バイトのレコードです。

6.3 YSTRIPES、種別 14（割り当て済み、未出力）

リングごとの水平ストライプによる point-in-polygon インデックスのシリアライズ形式です。

RINGSTRIPEDIR[ring_count]   (24-byte records, parallel to FLATRINGDIR):
    u32 stripe_first     // into STRIPES, absolute
    u32 stripe_count     // 0 -> no index for this ring (linear scan)
    u32 index_first      // into INDEXES, absolute
    u32 index_count
    i32 min_y
    i32 height
STRIPES:  (u32 start, u32 count) pairs; start relative to index_first
INDEXES:  u32 segment indices, packed by stripe

格納される内容は、tzf の geom.buildYStripes が生成するものとビット単位で同一である必要があります。M プロファイルの最初のリリースではこのセクションを出力しません。lite データセットでは 10 MB のファイルに推定 6 から 10 MB を追加する一方、オープン時のインデックス再構築はマルチコアのホストで約 5 ms です。ここで仕様を定めておくことで、後から追加する場合も format_minor の増加で収まります。シングルコアの CPU クォータ下におけるこの再構築のオープン時間コストは Finder の選択に記載しています。

6.4 サイズの内訳

lite 2026c、M プロファイル、YSTRIPES なしの場合：

完全精度データセットを同じ方法で展開すると 8,377,299 ペア、約 67 MB になります。full.tzm は配布されません。

7. 検索の意味論

1. NaN、無限大、-180..180 の範囲外の経度、-90..90 の範囲外の緯度を拒否します。
2. 丸めずに一度だけスケールします。x = float64(lng) * 100000.0、y = float64(lat) * 100000.0。
3. GRID から候補を読みます。GRID がない場合は TZDIR を走査します。
4. グリッドのセルが候補を 1 つだけ持ち、NO_SHORTCUT が立っておらず、-179 < lng < 179 かつ -89 < lat < 89 であれば、その候補を直接返します。
5. それ以外の場合は、格納順（昇順）で候補を検査し、ジオメトリをデコードする前にタイムゾーン、ポリゴン、リング、グループ、チャンクのバウンディングボックスを適用します。
6. ポリゴンが点を含むのは、外周が点を含み、かつどの穴も点を含まない場合です。
7. 最初に点を含む候補を返します。どの候補も含まない場合は結果なしを返します。

E プロファイルの point-in-polygon 評価では、reversed フラグにかかわらず参照先グループの格納された点を順方向に走査し、連続するチャンクを結ぶセグメントを評価します。各巡回操作の接合点については、出口と入口を GROUPDIR から導出します。両端点が等しい場合はセグメントを追加せず、異なる場合は出口から入口へのセグメントを評価します。

グループまたはチャンクは次の条件でスキップできます。

y < min_lat
y > max_lat
max_lng < x

複数結果の検索では単一候補のショートカットを無効にし、すべての候補を評価し、一致した結果を符号なし UTF-8 のバイト列による辞書順でソートします。

境界の扱い

タイムゾーンのポリゴンは隙間なく地球全体を覆うため、共有境界上のクエリは同時に 2 つのポリゴン上に位置します。v2 のランタイムは境界上を内包として扱う判定を使用します。外周リングは自身のセグメント上の点を含まれるものとして扱い、穴のリングは扱いません。したがって、共有境界上の地点は接するすべてのポリゴンに属します。

この形式の以前の版には、リングのセグメント上の点をそのリングの外側とみなす規則が記載されていました。これは tzf#216 より前のものです。現在の規則は、このページに記載した実装の挙動です。

8. 検証と互換性

読み手は、パニック、範囲外読み取り、整数オーバーフロー、未定義動作を起こすことなく構造的なエラーを拒否する必要があります。オープン時には、少なくとも次を検証します。

• マジック、メジャーバージョン、ヘッダサイズ、座標スケール、プロファイル、実際のファイルサイズ
• 幅の広い演算によるセクションテーブルの範囲
• そのプロファイルで必須のセクションの存在と一意性、およびプロファイルをまたぐセクション種別が存在しないこと
• GRID_PRESENT と GRID セクションの整合
• セクションの整列、範囲、非重複
• レコード幅に対するディレクトリセクションの長さ
• NAMES のオフセットと文字列の妥当性
• GRID の寸法、セクション長、座標キーの範囲
• 宣言されたカウントに対する FUZZY のセクション長

ディレクトリの範囲、グループとリングの点数の合計、操作のインデックス、チャンクのオフセット、varint の正確な終端、バウンディングボックスの順序、候補のインデックス、差分のオーバーフローは、オープン時または最初の使用前のいずれかで検査する必要があります。

予約フィールドと予約ビットはゼロで書き出され、読み取り時には無視されます。読み手は未知のセクション種別も無視します。非互換なレイアウトの変更では format_major を増やします。追加的な変更では format_minor を増やし、セクション種別、フラグビット、予約フィールドの意味を追加できます。形式 1.1 はこの仕組みを使って、プロファイルバイトと FUZZY、FLATPOINTS、FLATRINGDIR、YSTRIPES の各種別を追加しました。

意味論に踏み込んだ検査（バウンディングボックスの包含関係、格納されたグループの端点、接合点の連結性、ジオメトリの偶奇）は、エンコーダとビルドパイプラインの責務です。CRC は検証済みの成果物を偶発的な破損から保護します。

data_version は、形式バージョンとは独立にタイムゾーンデータセットを識別します。

9. 公開されている成果物

3 つとも FUZZY セクションと同じ data_version を持ちます。full.tzm は公開されていません。必要な場合は cmd/tzb2tzm でローカルに生成します。