1This directory contains files related to storage of TZ S2 data files used for offline geolocation 2time zone detection. 3 4High level file structure 5========================= 6 7 * `src/readonly/` - host + device code for reading TZ S2 data files 8 * `src/write/` - host code for writing TZ S2 data files 9 * `src/test/` - host tests for readonly/ and write/ code 10 * `tools/` - host tooling to support generation / debugging / testing of TZ S2 data 11 files. 12 13Block file format information 14============================= 15 16A "block file" is a general-purpose file format containing a small amount of header information, 17blocks of data, and metadata about those blocks. All types are big-endian / network byte ordered. 18 19Blocks are assigned contiguous IDs which are numbered from zero. 20 211. The file header has a type-identifying magic, and a version. 222. Next are the block infos, which hold metadata about all blocks in the file such as their ID, 23a type ID, (optional) arbitrary "extra" bytes, and size / offset information for the block. 243. Lastly, come the blocks of data themselves. Blocks can be zero-length, in which case they take up 25no space in the file. 26 27Packed tables 28============= 29 30Packed tables are a way of arranging block data to store tables of key-ordered key / value pairs in 31a compact way. Each entry in the table takes up a fixed number of bytes. 32 33Packed tables may contain some (optional) shared information that applies to all records in the 34table. Then they contain one or more fixed length `{key}`/`{value}` records of `{R}` bits sorted by 35`{key}`. The table data is easily memory mapped and each record can be randomly accessed by 36`{key}`. 37 38TZ S2 data file format information 39================================== 40 41The TZ S2 data file is a type of block file that uses packed tables. It overlays additional rules, 42block types, etc. on top of the general block file format. 43 44High level description 45---------------------- 46 47The TZ S2 data file format is intended to be language neutral (e.g. Java or C code could easily be 48written to read it with minimal dependencies), providing a good balance between file size, 49extensibility and memory usage at runtime. 50 51It is designed to be flexible and parameterized / self describing: the header block contains format 52information needed to locate and interpret the data storage blocks. 53 54The file stores time zone geolocation data at a single S2 level. Logically, the data consists of: 55 56``` 57{start S2 cell ID (inclusive)}, {end S2 cell ID (exclusive)}, {time zone IDs} 58``` 59 60The main usecase of the file is to lookup the time zone ID(s) (if any) for a given S2 cell ID. 61 62General storage approach 63------------------------ 64 65To keep the file size to a minimum, the format avoids storing 64-bit S2 cell IDs directly. Instead, 66the logical input data is mapped to a data structure that allows the individual S2 cell IDs to be 67stored using only a subset of the bits needed to store a full S2 cell ID. 68 69Each logical S2 range data described above is subdivided into ranges with a common S2 cell ID 70prefix. Any ranges in the source data that span a prefix are split into smaller ranges to preserve 71the "same prefix" property. All ranges with a common prefix can be stored in one "suffix table". 72 73The time zone ID strings are also only stored once and are referenced indirectly, avoiding repeated 74storage of common strings. 75 76TZ S2 data lookup 77----------------- 78 79Suffix table block IDs are calculated by taking the prefix of the S2 cell ID being sought and 80applying a fixed offset. The block info and block data for the cell's suffix table can be accessed 81directly using the block's ID. 82 83Specifically: 84 85The `{prefix}` is computed by extracting the first `{X}` bits of the S2 cell ID. The `{prefix}` is 86used to obtain the `{block ID}` of the block used to store the suffix table. The `{block ID}` is 87calculated by adding a fixed offset (obtained from the header block) to the cell ID `{prefix}`. 88 89The `{block ID}` is first used to look lookup the block info. If the length of the block with 90`{block ID}` is zero, the lookup stops at this point as it means there are no ranges for `{prefix}`. 91 92When the `{block ID}` block is non-zero length, the block is interpreted as a packed table 93(described above) which stores the suffix table's entries. 94 95The `{suffix}`, the final `{Y}` bits of the search S2 cell ID, is used to seek for a record 96containing the s2 range holding that cell ID, if any. The `{suffix}` will match either no records or 97only one record in the table. 98 99For more information on suffix table storage, see the Suffix Table Blocks section below. 100 101The Header Block 102---------------- 103 104The header block is always required to be block zero and have the expected type 105ID (1). 106 107The header contains format information needed to address the suffix table blocks 108and the block format information needed to interpret those blocks. It also 109contains information shared by all blocks such as the TZ ID sets. 110 111TZ ID Sets storage 112------------------ 113 114Sets of one or more time zone IDs are referenced by every range stored in the TZ S2 data file. 115 116Individual time zone IDs are strings like "America/Los_Angeles" that should only be stored once to 117conserve space. 118 119Further, the time zone IDs are referenced as sets, e.g. one cell range may reference 120"Europe/London", another may reference "Europe/Paris" and another may reference 121both "Europe/London" and "Europe/Paris". 122 123It is important to keep the number of bits used in each suffix table entry to a 124minimum because there are hundreds of thousands of ranges globally and hundreds 125of distinct sets. To do this we make use of "banking", which leverages 126properties of the data. 127 128For example: 129 1301. Several ranges with S2 cell IDs close together may reference the same set - e.g. there 131will be several range entries that reference "Europe/London". 1322. There is unlikely to a single S2 cell that needs to reference both "America/Los_Angeles" and 133"Europe/London", since the areas covered by those time zone IDs are geographically separate. 134 135Consequently: 136 137Every time zone ID string referenced in the file is assigned a numeric ID. The string is stored once 138in the file in the header block. All references to time zone IDs are made via the numeric ID. 139 140e.g. 141``` 1421: Europe/London 1432: Europe/Paris 1443: ... 145``` 146 147Every TZ S2 data file has one or more "set banks". Each bank contains an array of `{set of time zone 148IDs}`. 149 150A bank may contain many sets, which various combinations of TZ IDs: 151``` 1521: {1} - meaning the set {"Europe/London"} 1532: {2} - meaning the set {"Europe/Paris"} 1543: {1,2} - meaning the set {"Europe/London", "Europe/Paris"} 155... 156``` 157 158Via this indirection and banking, each range entry can address a set of time zone ID strings using 159only a numeric bank ID and a numeric set ID. The bank ID is the same for all entries in suffix 160table, so this means that it can be stored once per table and only the (small) `{TZ IDs set ID}` 161needs to be stored with each entry. 162 163Suffix Table Blocks 164------------------- 165 166The suffix table block is a packed table with shared information and one or more entries. 167 168The shared information consists of: 169 170``` 171{TZ IDs set bank} - the bank ID of the TZ IDs set bank used when looking up time zone set IDs 172 referenced by all table entries. 173``` 174 175Each record in the suffix table logically holds entries consisting of: 176``` 177{start S2 cell ID (inclusive)}, {end S2 cell ID (exclusive)}, {time zone IDs}` 178``` 179 180As with any packed table, each record in the packed table has a fixed width of `{R}` bits. The first 181`{M}` bits of every record are used to store the (ordered) `{key}`. 182 183The `{key}` for an entry contains only the `{suffix}` bits from the `{start S2 cell ID 184(inclusive)}`. To reconstruct the `{start S2 cell ID (inclusive)}` it's only necessary to know 185the `{prefix}` for the table and the `{key}`. 186 187The remaining (`{R-M}`) bits are used to store the ``{value}``. The ``{value}`` is further 188sub-divided into two: the `{end S2 cell ID offset}` and the `{TZ IDs set ID}`. 189 190The `{end S2 cell ID offset}` is a transformation of the `{end S2 cell ID (exclusive)}`. The `{end 191S2 cell ID}` can be calculated by adding the `{end S2 cell ID offset}` to the `{start S2 cell ID 192(inclusive)}`. 193 194When searching for an S2 cell ID, the prefix is used to locate the correct suffix table. The suffix 195bits from the S2 cell ID can be extracted. Since all data in the table is held at a single S2 level, 196the suffix bits can be used to binary search the suffix table entries by looking for an entry 197containing the suffix bits, i.e. by comparing the suffix bits against the `{key}` and `{key}` + 198`{end S2 cell ID offset}` value. 199 200If an entry is found, the `{TZ set ID}` indirectly leads to the `{time zone IDs}` for the range. For 201more information see TZ ID Sets storage above. 202