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